1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 *
3 * ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 *
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
10 *
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
15 *
16 * The Original Code is Mozilla Communicator client code, released
17 * March 31, 1998.
18 *
19 * The Initial Developer of the Original Code is
20 * Netscape Communications Corporation.
21 * Portions created by the Initial Developer are Copyright (C) 1998
22 * the Initial Developer. All Rights Reserved.
23 *
24 * Contributor(s):
25 *
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
37 *
38 * ***** END LICENSE BLOCK ***** */
40 #ifndef jsarena_h___
41 #define jsarena_h___
42 /*
43 * Lifetime-based fast allocation, inspired by much prior art, including
44 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
45 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
46 *
47 * Also supports LIFO allocation (JS_ARENA_MARK/JS_ARENA_RELEASE).
48 */
49 #include <stdlib.h>
50 #include "jstypes.h"
51 #include "jscompat.h"
53 JS_BEGIN_EXTERN_C
55 typedef struct JSArena JSArena;
56 typedef struct JSArenaPool JSArenaPool;
58 struct JSArena {
59 JSArena *next; /* next arena for this lifetime */
60 jsuword base; /* aligned base address, follows this header */
61 jsuword limit; /* one beyond last byte in arena */
62 jsuword avail; /* points to next available byte */
63 };
65 #ifdef JS_ARENAMETER
66 typedef struct JSArenaStats JSArenaStats;
68 struct JSArenaStats {
69 JSArenaStats *next; /* next in arenaStats list */
70 char *name; /* name for debugging */
71 uint32 narenas; /* number of arenas in pool */
72 uint32 nallocs; /* number of JS_ARENA_ALLOCATE() calls */
73 uint32 nreclaims; /* number of reclaims from freeArenas */
74 uint32 nmallocs; /* number of malloc() calls */
75 uint32 ndeallocs; /* number of lifetime deallocations */
76 uint32 ngrows; /* number of JS_ARENA_GROW() calls */
77 uint32 ninplace; /* number of in-place growths */
78 uint32 nreallocs; /* number of arena grow extending reallocs */
79 uint32 nreleases; /* number of JS_ARENA_RELEASE() calls */
80 uint32 nfastrels; /* number of "fast path" releases */
81 size_t nbytes; /* total bytes allocated */
82 size_t maxalloc; /* maximum allocation size in bytes */
83 double variance; /* size variance accumulator */
84 };
85 #endif
87 struct JSArenaPool {
88 JSArena first; /* first arena in pool list */
89 JSArena *current; /* arena from which to allocate space */
90 size_t arenasize; /* net exact size of a new arena */
91 jsuword mask; /* alignment mask (power-of-2 - 1) */
92 #ifdef JS_ARENAMETER
93 JSArenaStats stats;
94 #endif
95 };
97 /*
98 * If the including .c file uses only one power-of-2 alignment, it may define
99 * JS_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
100 * per ALLOCATE and GROW.
101 */
102 #ifdef JS_ARENA_CONST_ALIGN_MASK
103 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + JS_ARENA_CONST_ALIGN_MASK) \
104 & ~(jsuword)JS_ARENA_CONST_ALIGN_MASK)
106 #define JS_INIT_ARENA_POOL(pool, name, size) \
107 JS_InitArenaPool(pool, name, size, JS_ARENA_CONST_ALIGN_MASK + 1)
108 #else
109 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + (pool)->mask) & ~(pool)->mask)
110 #endif
112 #define JS_ARENA_ALLOCATE(p, pool, nb) \
113 JS_ARENA_ALLOCATE_CAST(p, void *, pool, nb)
115 #define JS_ARENA_ALLOCATE_TYPE(p, type, pool) \
116 JS_ARENA_ALLOCATE_CAST(p, type *, pool, sizeof(type))
118 #define JS_ARENA_ALLOCATE_CAST(p, type, pool, nb) \
119 JS_BEGIN_MACRO \
120 JSArena *_a = (pool)->current; \
121 size_t _nb = JS_ARENA_ALIGN(pool, nb); \
122 jsuword _p = _a->avail; \
123 jsuword _q = _p + _nb; \
124 JS_ASSERT(_q >= _p); \
125 if (_q > _a->limit) \
126 _p = (jsuword)JS_ArenaAllocate(pool, _nb); \
127 else \
128 _a->avail = _q; \
129 p = (type) _p; \
130 JS_ArenaCountAllocation(pool, nb); \
131 JS_END_MACRO
133 #define JS_ARENA_GROW(p, pool, size, incr) \
134 JS_ARENA_GROW_CAST(p, void *, pool, size, incr)
136 #define JS_ARENA_GROW_CAST(p, type, pool, size, incr) \
137 JS_BEGIN_MACRO \
138 JSArena *_a = (pool)->current; \
139 if (_a->avail == (jsuword)(p) + JS_ARENA_ALIGN(pool, size)) { \
140 size_t _nb = (size) + (incr); \
141 jsuword _q = (jsuword)(p) + JS_ARENA_ALIGN(pool, _nb); \
142 if (_q <= _a->limit) { \
143 _a->avail = _q; \
144 JS_ArenaCountInplaceGrowth(pool, size, incr); \
145 } else if ((jsuword)(p) == _a->base) { \
146 p = (type) JS_ArenaRealloc(pool, p, size, incr); \
147 } else { \
148 p = (type) JS_ArenaGrow(pool, p, size, incr); \
149 } \
150 } else { \
151 p = (type) JS_ArenaGrow(pool, p, size, incr); \
152 } \
153 JS_ArenaCountGrowth(pool, size, incr); \
154 JS_END_MACRO
156 #define JS_ARENA_MARK(pool) ((void *) (pool)->current->avail)
157 #define JS_UPTRDIFF(p,q) ((jsuword)(p) - (jsuword)(q))
159 #ifdef DEBUG
160 #define JS_FREE_PATTERN 0xDA
161 #define JS_CLEAR_UNUSED(a) (JS_ASSERT((a)->avail <= (a)->limit), \
162 memset((void*)(a)->avail, JS_FREE_PATTERN, \
163 (a)->limit - (a)->avail))
164 #define JS_CLEAR_ARENA(a) memset((void*)(a), JS_FREE_PATTERN, \
165 (a)->limit - (jsuword)(a))
166 #else
167 #define JS_CLEAR_UNUSED(a) /* nothing */
168 #define JS_CLEAR_ARENA(a) /* nothing */
169 #endif
171 #define JS_ARENA_RELEASE(pool, mark) \
172 JS_BEGIN_MACRO \
173 char *_m = (char *)(mark); \
174 JSArena *_a = (pool)->current; \
175 if (_a != &(pool)->first && \
176 JS_UPTRDIFF(_m, _a->base) <= JS_UPTRDIFF(_a->avail, _a->base)) { \
177 _a->avail = (jsuword)JS_ARENA_ALIGN(pool, _m); \
178 JS_ASSERT(_a->avail <= _a->limit); \
179 JS_CLEAR_UNUSED(_a); \
180 JS_ArenaCountRetract(pool, _m); \
181 } else { \
182 JS_ArenaRelease(pool, _m); \
183 } \
184 JS_ArenaCountRelease(pool, _m); \
185 JS_END_MACRO
187 #ifdef JS_ARENAMETER
188 #define JS_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
189 #else
190 #define JS_COUNT_ARENA(pool,op)
191 #endif
193 #define JS_ARENA_DESTROY(pool, a, pnext) \
194 JS_BEGIN_MACRO \
195 JS_COUNT_ARENA(pool,--); \
196 if ((pool)->current == (a)) (pool)->current = &(pool)->first; \
197 *(pnext) = (a)->next; \
198 JS_CLEAR_ARENA(a); \
199 free(a); \
200 (a) = NULL; \
201 JS_END_MACRO
203 /*
204 * Initialize an arena pool with the given name for debugging and metering,
205 * with a minimum size per arena of size bytes.
206 */
207 extern JS_PUBLIC_API(void)
208 JS_InitArenaPool(JSArenaPool *pool, const char *name, size_t size,
209 size_t align);
211 /*
212 * Free the arenas in pool. The user may continue to allocate from pool
213 * after calling this function. There is no need to call JS_InitArenaPool()
214 * again unless JS_FinishArenaPool(pool) has been called.
215 */
216 extern JS_PUBLIC_API(void)
217 JS_FreeArenaPool(JSArenaPool *pool);
219 /*
220 * Free the arenas in pool and finish using it altogether.
221 */
222 extern JS_PUBLIC_API(void)
223 JS_FinishArenaPool(JSArenaPool *pool);
225 /*
226 * Finish using arenas, freeing all memory associated with them except for
227 * any locks needed for thread safety.
228 */
229 extern JS_PUBLIC_API(void)
230 JS_ArenaFinish(void);
232 /*
233 * Free any locks or other memory needed for thread safety, just before
234 * shutting down. At that point, we must be called by a single thread.
235 *
236 * After shutting down, the next thread to call JS_InitArenaPool must not
237 * race with any other thread. Once a pool has been initialized, threads
238 * may safely call jsarena.c functions on thread-local pools. The upshot
239 * is that pools are per-thread, but the underlying global freelist is
240 * thread-safe, provided that both the first pool initialization and the
241 * shut-down call are single-threaded.
242 */
243 extern JS_PUBLIC_API(void)
244 JS_ArenaShutDown(void);
246 /*
247 * Friend functions used by the JS_ARENA_*() macros.
248 */
249 extern JS_PUBLIC_API(void *)
250 JS_ArenaAllocate(JSArenaPool *pool, size_t nb);
252 extern JS_PUBLIC_API(void *)
253 JS_ArenaRealloc(JSArenaPool *pool, void *p, size_t size, size_t incr);
255 extern JS_PUBLIC_API(void *)
256 JS_ArenaGrow(JSArenaPool *pool, void *p, size_t size, size_t incr);
258 extern JS_PUBLIC_API(void)
259 JS_ArenaRelease(JSArenaPool *pool, char *mark);
261 /*
262 * Function to be used directly when an allocation has likely grown to consume
263 * an entire JSArena, in which case the arena is returned to the malloc heap.
264 */
265 extern JS_PUBLIC_API(void)
266 JS_ArenaFreeAllocation(JSArenaPool *pool, void *p, size_t size);
268 #ifdef JS_ARENAMETER
270 #include <stdio.h>
272 extern JS_PUBLIC_API(void)
273 JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb);
275 extern JS_PUBLIC_API(void)
276 JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr);
278 extern JS_PUBLIC_API(void)
279 JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t incr);
281 extern JS_PUBLIC_API(void)
282 JS_ArenaCountRelease(JSArenaPool *pool, char *mark);
284 extern JS_PUBLIC_API(void)
285 JS_ArenaCountRetract(JSArenaPool *pool, char *mark);
287 extern JS_PUBLIC_API(void)
288 JS_DumpArenaStats(FILE *fp);
290 #else /* !JS_ARENAMETER */
292 #define JS_ArenaCountAllocation(ap, nb) /* nothing */
293 #define JS_ArenaCountInplaceGrowth(ap, size, incr) /* nothing */
294 #define JS_ArenaCountGrowth(ap, size, incr) /* nothing */
295 #define JS_ArenaCountRelease(ap, mark) /* nothing */
296 #define JS_ArenaCountRetract(ap, mark) /* nothing */
298 #endif /* !JS_ARENAMETER */
300 JS_END_EXTERN_C
302 #endif /* jsarena_h___ */