plarena.h (11644B)
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* This Source Code Form is subject to the terms of the Mozilla Public 3 * License, v. 2.0. If a copy of the MPL was not distributed with this 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 5 6 #ifndef plarena_h___ 7 #define plarena_h___ 8 /* 9 * Lifetime-based fast allocation, inspired by much prior art, including 10 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes" 11 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1). 12 * 13 * Also supports LIFO allocation (PL_ARENA_MARK/PL_ARENA_RELEASE). 14 */ 15 #include "prtypes.h" 16 17 PR_BEGIN_EXTERN_C 18 19 typedef struct PLArena PLArena; 20 21 struct PLArena { 22 PLArena *next; /* next arena for this lifetime */ 23 PRUword base; /* aligned base address, follows this header */ 24 PRUword limit; /* one beyond last byte in arena */ 25 PRUword avail; /* points to next available byte */ 26 }; 27 28 #ifdef PL_ARENAMETER 29 typedef struct PLArenaStats PLArenaStats; 30 31 struct PLArenaStats { 32 PLArenaStats *next; /* next in arenaStats list */ 33 char *name; /* name for debugging */ 34 PRUint32 narenas; /* number of arenas in pool */ 35 PRUint32 nallocs; /* number of PL_ARENA_ALLOCATE() calls */ 36 PRUint32 nreclaims; /* number of reclaims from freeArenas */ 37 PRUint32 nmallocs; /* number of malloc() calls */ 38 PRUint32 ndeallocs; /* number of lifetime deallocations */ 39 PRUint32 ngrows; /* number of PL_ARENA_GROW() calls */ 40 PRUint32 ninplace; /* number of in-place growths */ 41 PRUint32 nreleases; /* number of PL_ARENA_RELEASE() calls */ 42 PRUint32 nfastrels; /* number of "fast path" releases */ 43 PRUint32 nbytes; /* total bytes allocated */ 44 PRUint32 maxalloc; /* maximum allocation size in bytes */ 45 PRFloat64 variance; /* size variance accumulator */ 46 }; 47 #endif 48 49 typedef struct PLArenaPool PLArenaPool; 50 51 struct PLArenaPool { 52 PLArena first; /* first arena in pool list */ 53 PLArena *current; /* arena from which to allocate space */ 54 PRUint32 arenasize; /* net exact size of a new arena */ 55 PRUword mask; /* alignment mask (power-of-2 - 1) */ 56 #ifdef PL_ARENAMETER 57 PLArenaStats stats; 58 #endif 59 }; 60 61 /* 62 * WARNING: The PL_MAKE_MEM_ macros are for internal use by NSPR. Do NOT use 63 * them in your code. 64 * 65 * NOTE: Valgrind support to be added. 66 * 67 * The PL_MAKE_MEM_ macros are modeled after the MOZ_MAKE_MEM_ macros in 68 * Mozilla's mfbt/MemoryChecking.h. Only AddressSanitizer is supported now. 69 * 70 * Provides a common interface to the ASan (AddressSanitizer) and Valgrind 71 * functions used to mark memory in certain ways. In detail, the following 72 * three macros are provided: 73 * 74 * PL_MAKE_MEM_NOACCESS - Mark memory as unsafe to access (e.g. freed) 75 * PL_MAKE_MEM_UNDEFINED - Mark memory as accessible, with content undefined 76 * PL_MAKE_MEM_DEFINED - Mark memory as accessible, with content defined 77 * 78 * With Valgrind in use, these directly map to the three respective Valgrind 79 * macros. With ASan in use, the NOACCESS macro maps to poisoning the memory, 80 * while the UNDEFINED/DEFINED macros unpoison memory. 81 * 82 * With no memory checker available, all macros expand to the empty statement. 83 */ 84 85 /* WARNING: PL_SANITIZE_ADDRESS is for internal use by this header. Do NOT 86 * define or test this macro in your code. 87 */ 88 #if defined(__has_feature) 89 #if __has_feature(address_sanitizer) 90 #define PL_SANITIZE_ADDRESS 1 91 #endif 92 #elif defined(__SANITIZE_ADDRESS__) 93 #define PL_SANITIZE_ADDRESS 1 94 #endif 95 96 #if defined(PL_SANITIZE_ADDRESS) 97 98 #if defined(_MSC_VER) 99 /* We can't use dllimport due to DLL linkage mismatch with 100 * sanitizer/asan_interface.h. 101 */ 102 #define PL_ASAN_VISIBILITY(type_) type_ 103 #else 104 #define PL_ASAN_VISIBILITY(type_) PR_IMPORT(type_) 105 #endif 106 107 /* These definitions are usually provided through the 108 * sanitizer/asan_interface.h header installed by ASan. 109 * See https://github.com/google/sanitizers/wiki/AddressSanitizerManualPoisoning 110 */ 111 112 PL_ASAN_VISIBILITY(void) __asan_poison_memory_region( 113 void const volatile *addr, size_t size); 114 PL_ASAN_VISIBILITY(void) __asan_unpoison_memory_region( 115 void const volatile *addr, size_t size); 116 117 #define PL_MAKE_MEM_NOACCESS(addr, size) \ 118 __asan_poison_memory_region((addr), (size)) 119 120 #define PL_MAKE_MEM_UNDEFINED(addr, size) \ 121 __asan_unpoison_memory_region((addr), (size)) 122 123 #define PL_MAKE_MEM_DEFINED(addr, size) \ 124 __asan_unpoison_memory_region((addr), (size)) 125 126 #else 127 128 #define PL_MAKE_MEM_NOACCESS(addr, size) 129 #define PL_MAKE_MEM_UNDEFINED(addr, size) 130 #define PL_MAKE_MEM_DEFINED(addr, size) 131 132 #endif 133 134 /* 135 * If the including .c file uses only one power-of-2 alignment, it may define 136 * PL_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions 137 * per ALLOCATE and GROW. 138 */ 139 #ifdef PL_ARENA_CONST_ALIGN_MASK 140 #define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + PL_ARENA_CONST_ALIGN_MASK) \ 141 & ~PL_ARENA_CONST_ALIGN_MASK) 142 143 #define PL_INIT_ARENA_POOL(pool, name, size) \ 144 PL_InitArenaPool(pool, name, size, PL_ARENA_CONST_ALIGN_MASK + 1) 145 #else 146 #define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + (pool)->mask) & ~(pool)->mask) 147 #endif 148 149 #define PL_ARENA_ALLOCATE(p, pool, nb) \ 150 PR_BEGIN_MACRO \ 151 PLArena *_a = (pool)->current; \ 152 PRUint32 _nb = PL_ARENA_ALIGN(pool, (PRUint32)nb); \ 153 PRUword _p = _a->avail; \ 154 if (_nb < (PRUint32)nb) { \ 155 _p = 0; \ 156 } else if (_nb > (_a->limit - _a->avail)) { \ 157 _p = (PRUword)PL_ArenaAllocate(pool, _nb); \ 158 } else { \ 159 _a->avail += _nb; \ 160 } \ 161 p = (void *)_p; \ 162 if (p) { \ 163 PL_MAKE_MEM_UNDEFINED(p, (PRUint32)nb); \ 164 PL_ArenaCountAllocation(pool, (PRUint32)nb); \ 165 } \ 166 PR_END_MACRO 167 168 #define PL_ARENA_GROW(p, pool, size, incr) \ 169 PR_BEGIN_MACRO \ 170 PLArena *_a = (pool)->current; \ 171 PRUint32 _incr = PL_ARENA_ALIGN(pool, (PRUint32)incr); \ 172 if (_incr < (PRUint32)incr) { \ 173 p = NULL; \ 174 } else if (_a->avail == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \ 175 _incr <= (_a->limit - _a->avail)) { \ 176 PL_MAKE_MEM_UNDEFINED((unsigned char *)(p) + size, (PRUint32)incr); \ 177 _a->avail += _incr; \ 178 PL_ArenaCountInplaceGrowth(pool, size, (PRUint32)incr); \ 179 } else { \ 180 p = PL_ArenaGrow(pool, p, size, (PRUint32)incr); \ 181 } \ 182 if (p) {\ 183 PL_ArenaCountGrowth(pool, size, (PRUint32)incr); \ 184 } \ 185 PR_END_MACRO 186 187 #define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail) 188 #define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q)) 189 190 #define PL_CLEAR_UNUSED_PATTERN(a, pattern) \ 191 PR_BEGIN_MACRO \ 192 PR_ASSERT((a)->avail <= (a)->limit); \ 193 PL_MAKE_MEM_UNDEFINED((void*)(a)->avail, (a)->limit - (a)->avail); \ 194 memset((void*)(a)->avail, (pattern), (a)->limit - (a)->avail); \ 195 PR_END_MACRO 196 #ifdef DEBUG 197 #define PL_FREE_PATTERN 0xDA 198 #define PL_CLEAR_UNUSED(a) PL_CLEAR_UNUSED_PATTERN((a), PL_FREE_PATTERN) 199 #define PL_CLEAR_ARENA(a) \ 200 PR_BEGIN_MACRO \ 201 PL_MAKE_MEM_UNDEFINED((void*)(a), (a)->limit - (PRUword)(a)); \ 202 memset((void*)(a), PL_FREE_PATTERN, (a)->limit - (PRUword)(a)); \ 203 PR_END_MACRO 204 #else 205 #define PL_CLEAR_UNUSED(a) 206 #define PL_CLEAR_ARENA(a) 207 #endif 208 209 #define PL_ARENA_RELEASE(pool, mark) \ 210 PR_BEGIN_MACRO \ 211 char *_m = (char *)(mark); \ 212 PLArena *_a = (pool)->current; \ 213 if (PR_UPTRDIFF(_m, _a->base) <= PR_UPTRDIFF(_a->avail, _a->base)) { \ 214 _a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \ 215 PL_CLEAR_UNUSED(_a); \ 216 PL_MAKE_MEM_NOACCESS((void*)_a->avail, _a->limit - _a->avail); \ 217 PL_ArenaCountRetract(pool, _m); \ 218 } else { \ 219 PL_ArenaRelease(pool, _m); \ 220 } \ 221 PL_ArenaCountRelease(pool, _m); \ 222 PR_END_MACRO 223 224 #ifdef PL_ARENAMETER 225 #define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op) 226 #else 227 #define PL_COUNT_ARENA(pool,op) 228 #endif 229 230 #define PL_ARENA_DESTROY(pool, a, pnext) \ 231 PR_BEGIN_MACRO \ 232 PL_COUNT_ARENA(pool,--); \ 233 if ((pool)->current == (a)) (pool)->current = &(pool)->first; \ 234 *(pnext) = (a)->next; \ 235 PL_CLEAR_ARENA(a); \ 236 free(a); \ 237 (a) = 0; \ 238 PR_END_MACRO 239 240 /* 241 ** Initialize an arena pool with the given name for debugging and metering, 242 ** with a minimum gross size per arena of size bytes. The net size per arena 243 ** is smaller than the gross size by a header of four pointers plus any 244 ** necessary padding for alignment. 245 ** 246 ** Note: choose a gross size that's a power of two to avoid the heap allocator 247 ** rounding the size up. 248 **/ 249 PR_EXTERN(void) PL_InitArenaPool( 250 PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align); 251 252 /* 253 ** Finish using arenas, freeing all memory associated with them. 254 ** NOTE: this function is now a no-op. If you want to free a single 255 ** PLArenaPoolUse use PL_FreeArenaPool() or PL_FinishArenaPool(). 256 **/ 257 PR_EXTERN(void) PL_ArenaFinish(void); 258 259 /* 260 ** Free the arenas in pool. The user may continue to allocate from pool 261 ** after calling this function. There is no need to call PL_InitArenaPool() 262 ** again unless PL_FinishArenaPool(pool) has been called. 263 **/ 264 PR_EXTERN(void) PL_FreeArenaPool(PLArenaPool *pool); 265 266 /* 267 ** Free the arenas in pool and finish using it altogether. 268 **/ 269 PR_EXTERN(void) PL_FinishArenaPool(PLArenaPool *pool); 270 271 /* 272 ** Compact all of the arenas in a pool so that no space is wasted. 273 ** NOT IMPLEMENTED. Do not use. 274 **/ 275 PR_EXTERN(void) PL_CompactArenaPool(PLArenaPool *pool); 276 277 /* 278 ** Friend functions used by the PL_ARENA_*() macros. 279 ** 280 ** WARNING: do not call these functions directly. Always use the 281 ** PL_ARENA_*() macros. 282 **/ 283 PR_EXTERN(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb); 284 285 PR_EXTERN(void *) PL_ArenaGrow( 286 PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr); 287 288 PR_EXTERN(void) PL_ArenaRelease(PLArenaPool *pool, char *mark); 289 290 /* 291 ** memset contents of all arenas in pool to pattern 292 */ 293 PR_EXTERN(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern); 294 295 /* 296 ** A function like malloc_size() or malloc_usable_size() that measures the 297 ** size of a heap block. 298 */ 299 typedef size_t (*PLMallocSizeFn)(const void *ptr); 300 301 /* 302 ** Measure all memory used by a PLArenaPool, excluding the PLArenaPool 303 ** structure. 304 */ 305 PR_EXTERN(size_t) PL_SizeOfArenaPoolExcludingPool( 306 const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf); 307 308 #ifdef PL_ARENAMETER 309 310 #include <stdio.h> 311 312 PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb); 313 314 PR_EXTERN(void) PL_ArenaCountInplaceGrowth( 315 PLArenaPool *pool, PRUint32 size, PRUint32 incr); 316 317 PR_EXTERN(void) PL_ArenaCountGrowth( 318 PLArenaPool *pool, PRUint32 size, PRUint32 incr); 319 320 PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark); 321 322 PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark); 323 324 PR_EXTERN(void) PL_DumpArenaStats(FILE *fp); 325 326 #else /* !PL_ARENAMETER */ 327 328 #define PL_ArenaCountAllocation(ap, nb) /* nothing */ 329 #define PL_ArenaCountInplaceGrowth(ap, size, incr) /* nothing */ 330 #define PL_ArenaCountGrowth(ap, size, incr) /* nothing */ 331 #define PL_ArenaCountRelease(ap, mark) /* nothing */ 332 #define PL_ArenaCountRetract(ap, mark) /* nothing */ 333 334 #endif /* !PL_ARENAMETER */ 335 336 PR_END_EXTERN_C 337 338 #endif /* plarena_h___ */