| OLD | NEW |
|---|
| (Empty) |
| 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 /* | |
| 7 * Lifetime-based fast allocation, inspired by much prior art, including | |
| 8 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes" | |
| 9 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1). | |
| 10 */ | |
| 11 #include <stdlib.h> | |
| 12 #include <string.h> | |
| 13 #include "plarena.h" | |
| 14 #include "prmem.h" | |
| 15 #include "prbit.h" | |
| 16 #include "prlog.h" | |
| 17 #include "prlock.h" | |
| 18 #include "prinit.h" | |
| 19 | |
| 20 static PLArena *arena_freelist; | |
| 21 | |
| 22 #ifdef PL_ARENAMETER | |
| 23 static PLArenaStats *arena_stats_list; | |
| 24 | |
| 25 #define COUNT(pool,what) (pool)->stats.what++ | |
| 26 #else | |
| 27 #define COUNT(pool,what) /* nothing */ | |
| 28 #endif | |
| 29 | |
| 30 #define PL_ARENA_DEFAULT_ALIGN sizeof(double) | |
| 31 | |
| 32 static PRLock *arenaLock; | |
| 33 static PRCallOnceType once; | |
| 34 static const PRCallOnceType pristineCallOnce; | |
| 35 | |
| 36 /* | |
| 37 ** InitializeArenas() -- Initialize arena operations. | |
| 38 ** | |
| 39 ** InitializeArenas() is called exactly once and only once from | |
| 40 ** LockArena(). This function creates the arena protection | |
| 41 ** lock: arenaLock. | |
| 42 ** | |
| 43 ** Note: If the arenaLock cannot be created, InitializeArenas() | |
| 44 ** fails quietly, returning only PR_FAILURE. This percolates up | |
| 45 ** to the application using the Arena API. He gets no arena | |
| 46 ** from PL_ArenaAllocate(). It's up to him to fail gracefully | |
| 47 ** or recover. | |
| 48 ** | |
| 49 */ | |
| 50 static PRStatus InitializeArenas( void ) | |
| 51 { | |
| 52 PR_ASSERT( arenaLock == NULL ); | |
| 53 arenaLock = PR_NewLock(); | |
| 54 if ( arenaLock == NULL ) | |
| 55 return PR_FAILURE; | |
| 56 else | |
| 57 return PR_SUCCESS; | |
| 58 } /* end ArenaInitialize() */ | |
| 59 | |
| 60 static PRStatus LockArena( void ) | |
| 61 { | |
| 62 PRStatus rc = PR_CallOnce( &once, InitializeArenas ); | |
| 63 | |
| 64 if ( PR_FAILURE != rc ) | |
| 65 PR_Lock( arenaLock ); | |
| 66 return(rc); | |
| 67 } /* end LockArena() */ | |
| 68 | |
| 69 static void UnlockArena( void ) | |
| 70 { | |
| 71 PR_Unlock( arenaLock ); | |
| 72 return; | |
| 73 } /* end UnlockArena() */ | |
| 74 | |
| 75 PR_IMPLEMENT(void) PL_InitArenaPool( | |
| 76 PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align) | |
| 77 { | |
| 78 /* | |
| 79 * Look-up table of PR_BITMASK(PR_CeilingLog2(align)) values for | |
| 80 * align = 1 to 32. | |
| 81 */ | |
| 82 static const PRUint8 pmasks[33] = { | |
| 83 0, /* not used */ | |
| 84 0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,15, /* 1 ... 16 */ | |
| 85 31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}; /* 17 ... 32 */ | |
| 86 | |
| 87 if (align == 0) | |
| 88 align = PL_ARENA_DEFAULT_ALIGN; | |
| 89 | |
| 90 if (align < sizeof(pmasks)/sizeof(pmasks[0])) | |
| 91 pool->mask = pmasks[align]; | |
| 92 else | |
| 93 pool->mask = PR_BITMASK(PR_CeilingLog2(align)); | |
| 94 | |
| 95 pool->first.next = NULL; | |
| 96 pool->first.base = pool->first.avail = pool->first.limit = | |
| 97 (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1); | |
| 98 pool->current = &pool->first; | |
| 99 /* | |
| 100 * Compute the net size so that each arena's gross size is |size|. | |
| 101 * sizeof(PLArena) + pool->mask is the header and alignment slop | |
| 102 * that PL_ArenaAllocate adds to the net size. | |
| 103 */ | |
| 104 if (size > sizeof(PLArena) + pool->mask) | |
| 105 pool->arenasize = size - (sizeof(PLArena) + pool->mask); | |
| 106 else | |
| 107 pool->arenasize = size; | |
| 108 #ifdef PL_ARENAMETER | |
| 109 memset(&pool->stats, 0, sizeof pool->stats); | |
| 110 pool->stats.name = strdup(name); | |
| 111 pool->stats.next = arena_stats_list; | |
| 112 arena_stats_list = &pool->stats; | |
| 113 #endif | |
| 114 } | |
| 115 | |
| 116 | |
| 117 /* | |
| 118 ** PL_ArenaAllocate() -- allocate space from an arena pool | |
| 119 ** | |
| 120 ** Description: PL_ArenaAllocate() allocates space from an arena | |
| 121 ** pool. | |
| 122 ** | |
| 123 ** First, try to satisfy the request from arenas starting at | |
| 124 ** pool->current. | |
| 125 ** | |
| 126 ** If there is not enough space in the arena pool->current, try | |
| 127 ** to claim an arena, on a first fit basis, from the global | |
| 128 ** freelist (arena_freelist). | |
| 129 ** | |
| 130 ** If no arena in arena_freelist is suitable, then try to | |
| 131 ** allocate a new arena from the heap. | |
| 132 ** | |
| 133 ** Returns: pointer to allocated space or NULL | |
| 134 ** | |
| 135 ** Notes: The original implementation had some difficult to | |
| 136 ** solve bugs; the code was difficult to read. Sometimes it's | |
| 137 ** just easier to rewrite it. I did that. larryh. | |
| 138 ** | |
| 139 ** See also: bugzilla: 45343. | |
| 140 ** | |
| 141 */ | |
| 142 | |
| 143 PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb) | |
| 144 { | |
| 145 PLArena *a; | |
| 146 char *rp; /* returned pointer */ | |
| 147 | |
| 148 PR_ASSERT((nb & pool->mask) == 0); | |
| 149 | |
| 150 nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */ | |
| 151 | |
| 152 /* attempt to allocate from arenas at pool->current */ | |
| 153 { | |
| 154 a = pool->current; | |
| 155 do { | |
| 156 if ( a->avail +nb <= a->limit ) { | |
| 157 pool->current = a; | |
| 158 rp = (char *)a->avail; | |
| 159 a->avail += nb; | |
| 160 return rp; | |
| 161 } | |
| 162 } while( NULL != (a = a->next) ); | |
| 163 } | |
| 164 | |
| 165 /* attempt to allocate from arena_freelist */ | |
| 166 { | |
| 167 PLArena *p; /* previous pointer, for unlinking from freelist */ | |
| 168 | |
| 169 /* lock the arena_freelist. Make access to the freelist MT-Safe */ | |
| 170 if ( PR_FAILURE == LockArena()) | |
| 171 return(0); | |
| 172 | |
| 173 for ( a = arena_freelist, p = NULL; a != NULL ; p = a, a = a->next ) { | |
| 174 if ( a->base +nb <= a->limit ) { | |
| 175 if ( p == NULL ) | |
| 176 arena_freelist = a->next; | |
| 177 else | |
| 178 p->next = a->next; | |
| 179 UnlockArena(); | |
| 180 a->avail = a->base; | |
| 181 rp = (char *)a->avail; | |
| 182 a->avail += nb; | |
| 183 /* the newly allocated arena is linked after pool->current | |
| 184 * and becomes pool->current */ | |
| 185 a->next = pool->current->next; | |
| 186 pool->current->next = a; | |
| 187 pool->current = a; | |
| 188 if ( NULL == pool->first.next ) | |
| 189 pool->first.next = a; | |
| 190 return(rp); | |
| 191 } | |
| 192 } | |
| 193 UnlockArena(); | |
| 194 } | |
| 195 | |
| 196 /* attempt to allocate from the heap */ | |
| 197 { | |
| 198 PRUint32 sz = PR_MAX(pool->arenasize, nb); | |
| 199 sz += sizeof *a + pool->mask; /* header and alignment slop */ | |
| 200 a = (PLArena*)PR_MALLOC(sz); | |
| 201 if ( NULL != a ) { | |
| 202 a->limit = (PRUword)a + sz; | |
| 203 a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1); | |
| 204 rp = (char *)a->avail; | |
| 205 a->avail += nb; | |
| 206 /* the newly allocated arena is linked after pool->current | |
| 207 * and becomes pool->current */ | |
| 208 a->next = pool->current->next; | |
| 209 pool->current->next = a; | |
| 210 pool->current = a; | |
| 211 if ( NULL == pool->first.next ) | |
| 212 pool->first.next = a; | |
| 213 PL_COUNT_ARENA(pool,++); | |
| 214 COUNT(pool, nmallocs); | |
| 215 return(rp); | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 /* we got to here, and there's no memory to allocate */ | |
| 220 return(NULL); | |
| 221 } /* --- end PL_ArenaAllocate() --- */ | |
| 222 | |
| 223 PR_IMPLEMENT(void *) PL_ArenaGrow( | |
| 224 PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr) | |
| 225 { | |
| 226 void *newp; | |
| 227 | |
| 228 PL_ARENA_ALLOCATE(newp, pool, size + incr); | |
| 229 if (newp) | |
| 230 memcpy(newp, p, size); | |
| 231 return newp; | |
| 232 } | |
| 233 | |
| 234 static void ClearArenaList(PLArena *a, PRInt32 pattern) | |
| 235 { | |
| 236 | |
| 237 for (; a; a = a->next) { | |
| 238 PR_ASSERT(a->base <= a->avail && a->avail <= a->limit); | |
| 239 a->avail = a->base; | |
| 240 PL_CLEAR_UNUSED_PATTERN(a, pattern); | |
| 241 } | |
| 242 } | |
| 243 | |
| 244 PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern) | |
| 245 { | |
| 246 ClearArenaList(pool->first.next, pattern); | |
| 247 } | |
| 248 | |
| 249 /* | |
| 250 * Free tail arenas linked after head, which may not be the true list head. | |
| 251 * Reset pool->current to point to head in case it pointed at a tail arena. | |
| 252 */ | |
| 253 static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree) | |
| 254 { | |
| 255 PLArena **ap, *a; | |
| 256 | |
| 257 ap = &head->next; | |
| 258 a = *ap; | |
| 259 if (!a) | |
| 260 return; | |
| 261 | |
| 262 #ifdef DEBUG | |
| 263 ClearArenaList(a, PL_FREE_PATTERN); | |
| 264 #endif | |
| 265 | |
| 266 if (reallyFree) { | |
| 267 do { | |
| 268 *ap = a->next; | |
| 269 PL_CLEAR_ARENA(a); | |
| 270 PL_COUNT_ARENA(pool,--); | |
| 271 PR_DELETE(a); | |
| 272 } while ((a = *ap) != 0); | |
| 273 } else { | |
| 274 /* Insert the whole arena chain at the front of the freelist. */ | |
| 275 do { | |
| 276 ap = &(*ap)->next; | |
| 277 } while (*ap); | |
| 278 LockArena(); | |
| 279 *ap = arena_freelist; | |
| 280 arena_freelist = a; | |
| 281 head->next = 0; | |
| 282 UnlockArena(); | |
| 283 } | |
| 284 | |
| 285 pool->current = head; | |
| 286 } | |
| 287 | |
| 288 PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark) | |
| 289 { | |
| 290 PLArena *a; | |
| 291 | |
| 292 for (a = &pool->first; a; a = a->next) { | |
| 293 if (PR_UPTRDIFF(mark, a->base) <= PR_UPTRDIFF(a->avail, a->base)) { | |
| 294 a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark); | |
| 295 FreeArenaList(pool, a, PR_FALSE); | |
| 296 return; | |
| 297 } | |
| 298 } | |
| 299 } | |
| 300 | |
| 301 PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool) | |
| 302 { | |
| 303 FreeArenaList(pool, &pool->first, PR_FALSE); | |
| 304 COUNT(pool, ndeallocs); | |
| 305 } | |
| 306 | |
| 307 PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool) | |
| 308 { | |
| 309 FreeArenaList(pool, &pool->first, PR_TRUE); | |
| 310 #ifdef PL_ARENAMETER | |
| 311 { | |
| 312 PLArenaStats *stats, **statsp; | |
| 313 | |
| 314 if (pool->stats.name) | |
| 315 PR_DELETE(pool->stats.name); | |
| 316 for (statsp = &arena_stats_list; (stats = *statsp) != 0; | |
| 317 statsp = &stats->next) { | |
| 318 if (stats == &pool->stats) { | |
| 319 *statsp = stats->next; | |
| 320 return; | |
| 321 } | |
| 322 } | |
| 323 } | |
| 324 #endif | |
| 325 } | |
| 326 | |
| 327 PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap) | |
| 328 { | |
| 329 } | |
| 330 | |
| 331 PR_IMPLEMENT(void) PL_ArenaFinish(void) | |
| 332 { | |
| 333 PLArena *a, *next; | |
| 334 | |
| 335 for (a = arena_freelist; a; a = next) { | |
| 336 next = a->next; | |
| 337 PR_DELETE(a); | |
| 338 } | |
| 339 arena_freelist = NULL; | |
| 340 | |
| 341 if (arenaLock) { | |
| 342 PR_DestroyLock(arenaLock); | |
| 343 arenaLock = NULL; | |
| 344 } | |
| 345 once = pristineCallOnce; | |
| 346 } | |
| 347 | |
| 348 #ifdef PL_ARENAMETER | |
| 349 PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb) | |
| 350 { | |
| 351 pool->stats.nallocs++; | |
| 352 pool->stats.nbytes += nb; | |
| 353 if (nb > pool->stats.maxalloc) | |
| 354 pool->stats.maxalloc = nb; | |
| 355 pool->stats.variance += nb * nb; | |
| 356 } | |
| 357 | |
| 358 PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth( | |
| 359 PLArenaPool *pool, PRUint32 size, PRUint32 incr) | |
| 360 { | |
| 361 pool->stats.ninplace++; | |
| 362 } | |
| 363 | |
| 364 PR_IMPLEMENT(void) PL_ArenaCountGrowth( | |
| 365 PLArenaPool *pool, PRUint32 size, PRUint32 incr) | |
| 366 { | |
| 367 pool->stats.ngrows++; | |
| 368 pool->stats.nbytes += incr; | |
| 369 pool->stats.variance -= size * size; | |
| 370 size += incr; | |
| 371 if (size > pool->stats.maxalloc) | |
| 372 pool->stats.maxalloc = size; | |
| 373 pool->stats.variance += size * size; | |
| 374 } | |
| 375 | |
| 376 PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark) | |
| 377 { | |
| 378 pool->stats.nreleases++; | |
| 379 } | |
| 380 | |
| 381 PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark) | |
| 382 { | |
| 383 pool->stats.nfastrels++; | |
| 384 } | |
| 385 | |
| 386 #include <math.h> | |
| 387 #include <stdio.h> | |
| 388 | |
| 389 PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp) | |
| 390 { | |
| 391 PLArenaStats *stats; | |
| 392 double mean, variance; | |
| 393 | |
| 394 for (stats = arena_stats_list; stats; stats = stats->next) { | |
| 395 if (stats->nallocs != 0) { | |
| 396 mean = (double)stats->nbytes / stats->nallocs; | |
| 397 variance = fabs(stats->variance / stats->nallocs - mean * mean); | |
| 398 } else { | |
| 399 mean = variance = 0; | |
| 400 } | |
| 401 | |
| 402 fprintf(fp, "\n%s allocation statistics:\n", stats->name); | |
| 403 fprintf(fp, " number of arenas: %u\n", stats->narenas); | |
| 404 fprintf(fp, " number of allocations: %u\n", stats->nallocs); | |
| 405 fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims); | |
| 406 fprintf(fp, " number of malloc calls: %u\n", stats->nmallocs); | |
| 407 fprintf(fp, " number of deallocations: %u\n", stats->ndeallocs); | |
| 408 fprintf(fp, " number of allocation growths: %u\n", stats->ngrows); | |
| 409 fprintf(fp, " number of in-place growths: %u\n", stats->ninplace); | |
| 410 fprintf(fp, "number of released allocations: %u\n", stats->nreleases); | |
| 411 fprintf(fp, " number of fast releases: %u\n", stats->nfastrels); | |
| 412 fprintf(fp, " total bytes allocated: %u\n", stats->nbytes); | |
| 413 fprintf(fp, " mean allocation size: %g\n", mean); | |
| 414 fprintf(fp, " standard deviation: %g\n", sqrt(variance)); | |
| 415 fprintf(fp, " maximum allocation size: %u\n", stats->maxalloc); | |
| 416 } | |
| 417 } | |
| 418 #endif /* PL_ARENAMETER */ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 14249009:
Change the NSS and NSPR source tree to the new directory structure to be (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/deps/third_party/nss/