Back to index

lightning-sunbird  0.9+nobinonly
jsarena.h
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is Mozilla Communicator client code, released
00017  * March 31, 1998.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 1998
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #ifndef jsarena_h___
00041 #define jsarena_h___
00042 /*
00043  * Lifetime-based fast allocation, inspired by much prior art, including
00044  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
00045  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
00046  *
00047  * Also supports LIFO allocation (JS_ARENA_MARK/JS_ARENA_RELEASE).
00048  */
00049 #include <stdlib.h>
00050 #include "jstypes.h"
00051 #include "jscompat.h"
00052 
00053 JS_BEGIN_EXTERN_C
00054 
00055 typedef struct JSArena JSArena;
00056 typedef struct JSArenaPool JSArenaPool;
00057 
00058 struct JSArena {
00059     JSArena     *next;          /* next arena for this lifetime */
00060     jsuword     base;           /* aligned base address, follows this header */
00061     jsuword     limit;          /* one beyond last byte in arena */
00062     jsuword     avail;          /* points to next available byte */
00063 };
00064 
00065 #ifdef JS_ARENAMETER
00066 typedef struct JSArenaStats JSArenaStats;
00067 
00068 struct JSArenaStats {
00069     JSArenaStats *next;         /* next in arenaStats list */
00070     char        *name;          /* name for debugging */
00071     uint32      narenas;        /* number of arenas in pool */
00072     uint32      nallocs;        /* number of JS_ARENA_ALLOCATE() calls */
00073     uint32      nmallocs;       /* number of malloc() calls */
00074     uint32      ndeallocs;      /* number of lifetime deallocations */
00075     uint32      ngrows;         /* number of JS_ARENA_GROW() calls */
00076     uint32      ninplace;       /* number of in-place growths */
00077     uint32      nreallocs;      /* number of arena grow extending reallocs */
00078     uint32      nreleases;      /* number of JS_ARENA_RELEASE() calls */
00079     uint32      nfastrels;      /* number of "fast path" releases */
00080     size_t      nbytes;         /* total bytes allocated */
00081     size_t      maxalloc;       /* maximum allocation size in bytes */
00082     double      variance;       /* size variance accumulator */
00083 };
00084 #endif
00085 
00086 struct JSArenaPool {
00087     JSArena     first;          /* first arena in pool list */
00088     JSArena     *current;       /* arena from which to allocate space */
00089     size_t      arenasize;      /* net exact size of a new arena */
00090     jsuword     mask;           /* alignment mask (power-of-2 - 1) */
00091 #ifdef JS_ARENAMETER
00092     JSArenaStats stats;
00093 #endif
00094 };
00095 
00096 /*
00097  * If the including .c file uses only one power-of-2 alignment, it may define
00098  * JS_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
00099  * per ALLOCATE and GROW.
00100  */
00101 #ifdef JS_ARENA_CONST_ALIGN_MASK
00102 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + JS_ARENA_CONST_ALIGN_MASK)   \
00103                                  & ~(jsuword)JS_ARENA_CONST_ALIGN_MASK)
00104 
00105 #define JS_INIT_ARENA_POOL(pool, name, size) \
00106         JS_InitArenaPool(pool, name, size, JS_ARENA_CONST_ALIGN_MASK + 1)
00107 #else
00108 #define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + (pool)->mask) & ~(pool)->mask)
00109 #endif
00110 
00111 #define JS_ARENA_ALLOCATE(p, pool, nb)                                        \
00112     JS_ARENA_ALLOCATE_CAST(p, void *, pool, nb)
00113 
00114 #define JS_ARENA_ALLOCATE_TYPE(p, type, pool)                                 \
00115     JS_ARENA_ALLOCATE_COMMON(p, type *, pool, sizeof(type), 0)
00116 
00117 #define JS_ARENA_ALLOCATE_CAST(p, type, pool, nb)                             \
00118     JS_ARENA_ALLOCATE_COMMON(p, type, pool, nb, _nb > _a->limit)
00119 
00120 /*
00121  * NB: In JS_ARENA_ALLOCATE_CAST and JS_ARENA_GROW_CAST, always subtract _nb
00122  * from a->limit rather than adding _nb to _p, to avoid overflowing a 32-bit
00123  * address space (possible when running a 32-bit program on a 64-bit system
00124  * where the kernel maps the heap up against the top of the 32-bit address
00125  * space).
00126  *
00127  * Thanks to Juergen Kreileder <jk@blackdown.de>, who brought this up in
00128  * https://bugzilla.mozilla.org/show_bug.cgi?id=279273.
00129  */
00130 #define JS_ARENA_ALLOCATE_COMMON(p, type, pool, nb, guard)                    \
00131     JS_BEGIN_MACRO                                                            \
00132         JSArena *_a = (pool)->current;                                        \
00133         size_t _nb = JS_ARENA_ALIGN(pool, nb);                                \
00134         jsuword _p = _a->avail;                                               \
00135         if ((guard) || _p > _a->limit - _nb)                                  \
00136             _p = (jsuword)JS_ArenaAllocate(pool, _nb);                        \
00137         else                                                                  \
00138             _a->avail = _p + _nb;                                             \
00139         p = (type) _p;                                                        \
00140         JS_ArenaCountAllocation(pool, nb);                                    \
00141     JS_END_MACRO
00142 
00143 #define JS_ARENA_GROW(p, pool, size, incr)                                    \
00144     JS_ARENA_GROW_CAST(p, void *, pool, size, incr)
00145 
00146 #define JS_ARENA_GROW_CAST(p, type, pool, size, incr)                         \
00147     JS_BEGIN_MACRO                                                            \
00148         JSArena *_a = (pool)->current;                                        \
00149         if (_a->avail == (jsuword)(p) + JS_ARENA_ALIGN(pool, size)) {         \
00150             size_t _nb = (size) + (incr);                                     \
00151             _nb = JS_ARENA_ALIGN(pool, _nb);                                  \
00152             if (_a->limit >= _nb && (jsuword)(p) <= _a->limit - _nb) {        \
00153                 _a->avail = (jsuword)(p) + _nb;                               \
00154                 JS_ArenaCountInplaceGrowth(pool, size, incr);                 \
00155             } else if ((jsuword)(p) == _a->base) {                            \
00156                 p = (type) JS_ArenaRealloc(pool, p, size, incr);              \
00157             } else {                                                          \
00158                 p = (type) JS_ArenaGrow(pool, p, size, incr);                 \
00159             }                                                                 \
00160         } else {                                                              \
00161             p = (type) JS_ArenaGrow(pool, p, size, incr);                     \
00162         }                                                                     \
00163         JS_ArenaCountGrowth(pool, size, incr);                                \
00164     JS_END_MACRO
00165 
00166 #define JS_ARENA_MARK(pool)     ((void *) (pool)->current->avail)
00167 #define JS_UPTRDIFF(p,q)        ((jsuword)(p) - (jsuword)(q))
00168 
00169 #ifdef DEBUG
00170 #define JS_FREE_PATTERN         0xDA
00171 #define JS_CLEAR_UNUSED(a)      (JS_ASSERT((a)->avail <= (a)->limit),         \
00172                                  memset((void*)(a)->avail, JS_FREE_PATTERN,   \
00173                                         (a)->limit - (a)->avail))
00174 #define JS_CLEAR_ARENA(a)       memset((void*)(a), JS_FREE_PATTERN,           \
00175                                        (a)->limit - (jsuword)(a))
00176 #else
00177 #define JS_CLEAR_UNUSED(a)      /* nothing */
00178 #define JS_CLEAR_ARENA(a)       /* nothing */
00179 #endif
00180 
00181 #define JS_ARENA_RELEASE(pool, mark)                                          \
00182     JS_BEGIN_MACRO                                                            \
00183         char *_m = (char *)(mark);                                            \
00184         JSArena *_a = (pool)->current;                                        \
00185         if (_a != &(pool)->first &&                                           \
00186             JS_UPTRDIFF(_m, _a->base) <= JS_UPTRDIFF(_a->avail, _a->base)) {  \
00187             _a->avail = (jsuword)JS_ARENA_ALIGN(pool, _m);                    \
00188             JS_ASSERT(_a->avail <= _a->limit);                                \
00189             JS_CLEAR_UNUSED(_a);                                              \
00190             JS_ArenaCountRetract(pool, _m);                                   \
00191         } else {                                                              \
00192             JS_ArenaRelease(pool, _m);                                        \
00193         }                                                                     \
00194         JS_ArenaCountRelease(pool, _m);                                       \
00195     JS_END_MACRO
00196 
00197 #ifdef JS_ARENAMETER
00198 #define JS_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
00199 #else
00200 #define JS_COUNT_ARENA(pool,op)
00201 #endif
00202 
00203 #define JS_ARENA_DESTROY(pool, a, pnext)                                      \
00204     JS_BEGIN_MACRO                                                            \
00205         JS_COUNT_ARENA(pool,--);                                              \
00206         if ((pool)->current == (a)) (pool)->current = &(pool)->first;         \
00207         *(pnext) = (a)->next;                                                 \
00208         JS_CLEAR_ARENA(a);                                                    \
00209         free(a);                                                              \
00210         (a) = NULL;                                                           \
00211     JS_END_MACRO
00212 
00213 /*
00214  * Initialize an arena pool with the given name for debugging and metering,
00215  * with a minimum size per arena of size bytes.
00216  */
00217 extern JS_PUBLIC_API(void)
00218 JS_InitArenaPool(JSArenaPool *pool, const char *name, size_t size,
00219                  size_t align);
00220 
00221 /*
00222  * Free the arenas in pool.  The user may continue to allocate from pool
00223  * after calling this function.  There is no need to call JS_InitArenaPool()
00224  * again unless JS_FinishArenaPool(pool) has been called.
00225  */
00226 extern JS_PUBLIC_API(void)
00227 JS_FreeArenaPool(JSArenaPool *pool);
00228 
00229 /*
00230  * Free the arenas in pool and finish using it altogether.
00231  */
00232 extern JS_PUBLIC_API(void)
00233 JS_FinishArenaPool(JSArenaPool *pool);
00234 
00235 /*
00236  * Deprecated do-nothing function.
00237  */
00238 extern JS_PUBLIC_API(void)
00239 JS_ArenaFinish(void);
00240 
00241 /*
00242  * Deprecated do-nothing function.
00243  */
00244 extern JS_PUBLIC_API(void)
00245 JS_ArenaShutDown(void);
00246 
00247 /*
00248  * Friend functions used by the JS_ARENA_*() macros.
00249  */
00250 extern JS_PUBLIC_API(void *)
00251 JS_ArenaAllocate(JSArenaPool *pool, size_t nb);
00252 
00253 extern JS_PUBLIC_API(void *)
00254 JS_ArenaRealloc(JSArenaPool *pool, void *p, size_t size, size_t incr);
00255 
00256 extern JS_PUBLIC_API(void *)
00257 JS_ArenaGrow(JSArenaPool *pool, void *p, size_t size, size_t incr);
00258 
00259 extern JS_PUBLIC_API(void)
00260 JS_ArenaRelease(JSArenaPool *pool, char *mark);
00261 
00262 /*
00263  * Function to be used directly when an allocation has likely grown to consume
00264  * an entire JSArena, in which case the arena is returned to the malloc heap.
00265  */
00266 extern JS_PUBLIC_API(void)
00267 JS_ArenaFreeAllocation(JSArenaPool *pool, void *p, size_t size);
00268 
00269 #ifdef JS_ARENAMETER
00270 
00271 #include <stdio.h>
00272 
00273 extern JS_PUBLIC_API(void)
00274 JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb);
00275 
00276 extern JS_PUBLIC_API(void)
00277 JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr);
00278 
00279 extern JS_PUBLIC_API(void)
00280 JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t incr);
00281 
00282 extern JS_PUBLIC_API(void)
00283 JS_ArenaCountRelease(JSArenaPool *pool, char *mark);
00284 
00285 extern JS_PUBLIC_API(void)
00286 JS_ArenaCountRetract(JSArenaPool *pool, char *mark);
00287 
00288 extern JS_PUBLIC_API(void)
00289 JS_DumpArenaStats(FILE *fp);
00290 
00291 #else  /* !JS_ARENAMETER */
00292 
00293 #define JS_ArenaCountAllocation(ap, nb)                 /* nothing */
00294 #define JS_ArenaCountInplaceGrowth(ap, size, incr)      /* nothing */
00295 #define JS_ArenaCountGrowth(ap, size, incr)             /* nothing */
00296 #define JS_ArenaCountRelease(ap, mark)                  /* nothing */
00297 #define JS_ArenaCountRetract(ap, mark)                  /* nothing */
00298 
00299 #endif /* !JS_ARENAMETER */
00300 
00301 JS_END_EXTERN_C
00302 
00303 #endif /* jsarena_h___ */