1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/nsprpub/lib/ds/plarena.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,442 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +/*
1.10 + * Lifetime-based fast allocation, inspired by much prior art, including
1.11 + * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
1.12 + * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
1.13 + */
1.14 +#include <stdlib.h>
1.15 +#include <string.h>
1.16 +#include "plarena.h"
1.17 +#include "prmem.h"
1.18 +#include "prbit.h"
1.19 +#include "prlog.h"
1.20 +#include "prlock.h"
1.21 +#include "prinit.h"
1.22 +
1.23 +static PLArena *arena_freelist;
1.24 +
1.25 +#ifdef PL_ARENAMETER
1.26 +static PLArenaStats *arena_stats_list;
1.27 +
1.28 +#define COUNT(pool,what) (pool)->stats.what++
1.29 +#else
1.30 +#define COUNT(pool,what) /* nothing */
1.31 +#endif
1.32 +
1.33 +#define PL_ARENA_DEFAULT_ALIGN sizeof(double)
1.34 +
1.35 +static PRLock *arenaLock;
1.36 +static PRCallOnceType once;
1.37 +static const PRCallOnceType pristineCallOnce;
1.38 +
1.39 +/*
1.40 +** InitializeArenas() -- Initialize arena operations.
1.41 +**
1.42 +** InitializeArenas() is called exactly once and only once from
1.43 +** LockArena(). This function creates the arena protection
1.44 +** lock: arenaLock.
1.45 +**
1.46 +** Note: If the arenaLock cannot be created, InitializeArenas()
1.47 +** fails quietly, returning only PR_FAILURE. This percolates up
1.48 +** to the application using the Arena API. He gets no arena
1.49 +** from PL_ArenaAllocate(). It's up to him to fail gracefully
1.50 +** or recover.
1.51 +**
1.52 +*/
1.53 +static PRStatus InitializeArenas( void )
1.54 +{
1.55 + PR_ASSERT( arenaLock == NULL );
1.56 + arenaLock = PR_NewLock();
1.57 + if ( arenaLock == NULL )
1.58 + return PR_FAILURE;
1.59 + else
1.60 + return PR_SUCCESS;
1.61 +} /* end ArenaInitialize() */
1.62 +
1.63 +static PRStatus LockArena( void )
1.64 +{
1.65 + PRStatus rc = PR_CallOnce( &once, InitializeArenas );
1.66 +
1.67 + if ( PR_FAILURE != rc )
1.68 + PR_Lock( arenaLock );
1.69 + return(rc);
1.70 +} /* end LockArena() */
1.71 +
1.72 +static void UnlockArena( void )
1.73 +{
1.74 + PR_Unlock( arenaLock );
1.75 + return;
1.76 +} /* end UnlockArena() */
1.77 +
1.78 +PR_IMPLEMENT(void) PL_InitArenaPool(
1.79 + PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
1.80 +{
1.81 + /*
1.82 + * Look-up table of PR_BITMASK(PR_CeilingLog2(align)) values for
1.83 + * align = 1 to 32.
1.84 + */
1.85 + static const PRUint8 pmasks[33] = {
1.86 + 0, /* not used */
1.87 + 0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,15, /* 1 ... 16 */
1.88 + 31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}; /* 17 ... 32 */
1.89 +
1.90 + if (align == 0)
1.91 + align = PL_ARENA_DEFAULT_ALIGN;
1.92 +
1.93 + if (align < sizeof(pmasks)/sizeof(pmasks[0]))
1.94 + pool->mask = pmasks[align];
1.95 + else
1.96 + pool->mask = PR_BITMASK(PR_CeilingLog2(align));
1.97 +
1.98 + pool->first.next = NULL;
1.99 + pool->first.base = pool->first.avail = pool->first.limit =
1.100 + (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
1.101 + pool->current = &pool->first;
1.102 + /*
1.103 + * Compute the net size so that each arena's gross size is |size|.
1.104 + * sizeof(PLArena) + pool->mask is the header and alignment slop
1.105 + * that PL_ArenaAllocate adds to the net size.
1.106 + */
1.107 + if (size > sizeof(PLArena) + pool->mask)
1.108 + pool->arenasize = size - (sizeof(PLArena) + pool->mask);
1.109 + else
1.110 + pool->arenasize = size;
1.111 +#ifdef PL_ARENAMETER
1.112 + memset(&pool->stats, 0, sizeof pool->stats);
1.113 + pool->stats.name = strdup(name);
1.114 + pool->stats.next = arena_stats_list;
1.115 + arena_stats_list = &pool->stats;
1.116 +#endif
1.117 +}
1.118 +
1.119 +
1.120 +/*
1.121 +** PL_ArenaAllocate() -- allocate space from an arena pool
1.122 +**
1.123 +** Description: PL_ArenaAllocate() allocates space from an arena
1.124 +** pool.
1.125 +**
1.126 +** First, try to satisfy the request from arenas starting at
1.127 +** pool->current.
1.128 +**
1.129 +** If there is not enough space in the arena pool->current, try
1.130 +** to claim an arena, on a first fit basis, from the global
1.131 +** freelist (arena_freelist).
1.132 +**
1.133 +** If no arena in arena_freelist is suitable, then try to
1.134 +** allocate a new arena from the heap.
1.135 +**
1.136 +** Returns: pointer to allocated space or NULL
1.137 +**
1.138 +** Notes: The original implementation had some difficult to
1.139 +** solve bugs; the code was difficult to read. Sometimes it's
1.140 +** just easier to rewrite it. I did that. larryh.
1.141 +**
1.142 +** See also: bugzilla: 45343.
1.143 +**
1.144 +*/
1.145 +
1.146 +PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
1.147 +{
1.148 + PLArena *a;
1.149 + char *rp; /* returned pointer */
1.150 +
1.151 + PR_ASSERT((nb & pool->mask) == 0);
1.152 +
1.153 + nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
1.154 +
1.155 + /* attempt to allocate from arenas at pool->current */
1.156 + {
1.157 + a = pool->current;
1.158 + do {
1.159 + if ( nb <= a->limit - a->avail ) {
1.160 + pool->current = a;
1.161 + rp = (char *)a->avail;
1.162 + a->avail += nb;
1.163 + return rp;
1.164 + }
1.165 + } while( NULL != (a = a->next) );
1.166 + }
1.167 +
1.168 + /* attempt to allocate from arena_freelist */
1.169 + {
1.170 + PLArena *p; /* previous pointer, for unlinking from freelist */
1.171 +
1.172 + /* lock the arena_freelist. Make access to the freelist MT-Safe */
1.173 + if ( PR_FAILURE == LockArena())
1.174 + return(0);
1.175 +
1.176 + for ( a = arena_freelist, p = NULL; a != NULL ; p = a, a = a->next ) {
1.177 + if ( nb <= a->limit - a->base ) {
1.178 + if ( p == NULL )
1.179 + arena_freelist = a->next;
1.180 + else
1.181 + p->next = a->next;
1.182 + UnlockArena();
1.183 + a->avail = a->base;
1.184 + rp = (char *)a->avail;
1.185 + a->avail += nb;
1.186 + /* the newly allocated arena is linked after pool->current
1.187 + * and becomes pool->current */
1.188 + a->next = pool->current->next;
1.189 + pool->current->next = a;
1.190 + pool->current = a;
1.191 + if ( NULL == pool->first.next )
1.192 + pool->first.next = a;
1.193 + return(rp);
1.194 + }
1.195 + }
1.196 + UnlockArena();
1.197 + }
1.198 +
1.199 + /* attempt to allocate from the heap */
1.200 + {
1.201 + PRUint32 sz = PR_MAX(pool->arenasize, nb);
1.202 + if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
1.203 + a = NULL;
1.204 + } else {
1.205 + sz += sizeof *a + pool->mask; /* header and alignment slop */
1.206 + a = (PLArena*)PR_MALLOC(sz);
1.207 + }
1.208 + if ( NULL != a ) {
1.209 + a->limit = (PRUword)a + sz;
1.210 + a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
1.211 + PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
1.212 + rp = (char *)a->avail;
1.213 + a->avail += nb;
1.214 + /* the newly allocated arena is linked after pool->current
1.215 + * and becomes pool->current */
1.216 + a->next = pool->current->next;
1.217 + pool->current->next = a;
1.218 + pool->current = a;
1.219 + if ( NULL == pool->first.next )
1.220 + pool->first.next = a;
1.221 + PL_COUNT_ARENA(pool,++);
1.222 + COUNT(pool, nmallocs);
1.223 + return(rp);
1.224 + }
1.225 + }
1.226 +
1.227 + /* we got to here, and there's no memory to allocate */
1.228 + return(NULL);
1.229 +} /* --- end PL_ArenaAllocate() --- */
1.230 +
1.231 +PR_IMPLEMENT(void *) PL_ArenaGrow(
1.232 + PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr)
1.233 +{
1.234 + void *newp;
1.235 +
1.236 + PL_ARENA_ALLOCATE(newp, pool, size + incr);
1.237 + if (newp)
1.238 + memcpy(newp, p, size);
1.239 + return newp;
1.240 +}
1.241 +
1.242 +static void ClearArenaList(PLArena *a, PRInt32 pattern)
1.243 +{
1.244 +
1.245 + for (; a; a = a->next) {
1.246 + PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
1.247 + a->avail = a->base;
1.248 + PL_CLEAR_UNUSED_PATTERN(a, pattern);
1.249 + PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
1.250 + }
1.251 +}
1.252 +
1.253 +PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
1.254 +{
1.255 + ClearArenaList(pool->first.next, pattern);
1.256 +}
1.257 +
1.258 +/*
1.259 + * Free tail arenas linked after head, which may not be the true list head.
1.260 + * Reset pool->current to point to head in case it pointed at a tail arena.
1.261 + */
1.262 +static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
1.263 +{
1.264 + PLArena **ap, *a;
1.265 +
1.266 + ap = &head->next;
1.267 + a = *ap;
1.268 + if (!a)
1.269 + return;
1.270 +
1.271 +#ifdef DEBUG
1.272 + ClearArenaList(a, PL_FREE_PATTERN);
1.273 +#endif
1.274 +
1.275 + if (reallyFree) {
1.276 + do {
1.277 + *ap = a->next;
1.278 + PL_CLEAR_ARENA(a);
1.279 + PL_COUNT_ARENA(pool,--);
1.280 + PR_DELETE(a);
1.281 + } while ((a = *ap) != 0);
1.282 + } else {
1.283 + /* Insert the whole arena chain at the front of the freelist. */
1.284 + do {
1.285 + PL_MAKE_MEM_NOACCESS((void*)(*ap)->base,
1.286 + (*ap)->limit - (*ap)->base);
1.287 + ap = &(*ap)->next;
1.288 + } while (*ap);
1.289 + LockArena();
1.290 + *ap = arena_freelist;
1.291 + arena_freelist = a;
1.292 + head->next = 0;
1.293 + UnlockArena();
1.294 + }
1.295 +
1.296 + pool->current = head;
1.297 +}
1.298 +
1.299 +PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
1.300 +{
1.301 + PLArena *a;
1.302 +
1.303 + for (a = &pool->first; a; a = a->next) {
1.304 + if (PR_UPTRDIFF(mark, a->base) <= PR_UPTRDIFF(a->avail, a->base)) {
1.305 + a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
1.306 + FreeArenaList(pool, a, PR_FALSE);
1.307 + return;
1.308 + }
1.309 + }
1.310 +}
1.311 +
1.312 +PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
1.313 +{
1.314 + FreeArenaList(pool, &pool->first, PR_FALSE);
1.315 + COUNT(pool, ndeallocs);
1.316 +}
1.317 +
1.318 +PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
1.319 +{
1.320 + FreeArenaList(pool, &pool->first, PR_TRUE);
1.321 +#ifdef PL_ARENAMETER
1.322 + {
1.323 + PLArenaStats *stats, **statsp;
1.324 +
1.325 + if (pool->stats.name)
1.326 + PR_DELETE(pool->stats.name);
1.327 + for (statsp = &arena_stats_list; (stats = *statsp) != 0;
1.328 + statsp = &stats->next) {
1.329 + if (stats == &pool->stats) {
1.330 + *statsp = stats->next;
1.331 + return;
1.332 + }
1.333 + }
1.334 + }
1.335 +#endif
1.336 +}
1.337 +
1.338 +PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
1.339 +{
1.340 +}
1.341 +
1.342 +PR_IMPLEMENT(void) PL_ArenaFinish(void)
1.343 +{
1.344 + PLArena *a, *next;
1.345 +
1.346 + for (a = arena_freelist; a; a = next) {
1.347 + next = a->next;
1.348 + PR_DELETE(a);
1.349 + }
1.350 + arena_freelist = NULL;
1.351 +
1.352 + if (arenaLock) {
1.353 + PR_DestroyLock(arenaLock);
1.354 + arenaLock = NULL;
1.355 + }
1.356 + once = pristineCallOnce;
1.357 +}
1.358 +
1.359 +PR_IMPLEMENT(size_t) PL_SizeOfArenaPoolExcludingPool(
1.360 + const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf)
1.361 +{
1.362 + /*
1.363 + * The first PLArena is within |pool|, so don't measure it. Subsequent
1.364 + * PLArenas are separate and must be measured.
1.365 + */
1.366 + size_t size = 0;
1.367 + const PLArena *arena = pool->first.next;
1.368 + while (arena) {
1.369 + size += mallocSizeOf(arena);
1.370 + arena = arena->next;
1.371 + }
1.372 + return size;
1.373 +}
1.374 +
1.375 +#ifdef PL_ARENAMETER
1.376 +PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
1.377 +{
1.378 + pool->stats.nallocs++;
1.379 + pool->stats.nbytes += nb;
1.380 + if (nb > pool->stats.maxalloc)
1.381 + pool->stats.maxalloc = nb;
1.382 + pool->stats.variance += nb * nb;
1.383 +}
1.384 +
1.385 +PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
1.386 + PLArenaPool *pool, PRUint32 size, PRUint32 incr)
1.387 +{
1.388 + pool->stats.ninplace++;
1.389 +}
1.390 +
1.391 +PR_IMPLEMENT(void) PL_ArenaCountGrowth(
1.392 + PLArenaPool *pool, PRUint32 size, PRUint32 incr)
1.393 +{
1.394 + pool->stats.ngrows++;
1.395 + pool->stats.nbytes += incr;
1.396 + pool->stats.variance -= size * size;
1.397 + size += incr;
1.398 + if (size > pool->stats.maxalloc)
1.399 + pool->stats.maxalloc = size;
1.400 + pool->stats.variance += size * size;
1.401 +}
1.402 +
1.403 +PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
1.404 +{
1.405 + pool->stats.nreleases++;
1.406 +}
1.407 +
1.408 +PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
1.409 +{
1.410 + pool->stats.nfastrels++;
1.411 +}
1.412 +
1.413 +#include <math.h>
1.414 +#include <stdio.h>
1.415 +
1.416 +PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
1.417 +{
1.418 + PLArenaStats *stats;
1.419 + double mean, variance;
1.420 +
1.421 + for (stats = arena_stats_list; stats; stats = stats->next) {
1.422 + if (stats->nallocs != 0) {
1.423 + mean = (double)stats->nbytes / stats->nallocs;
1.424 + variance = fabs(stats->variance / stats->nallocs - mean * mean);
1.425 + } else {
1.426 + mean = variance = 0;
1.427 + }
1.428 +
1.429 + fprintf(fp, "\n%s allocation statistics:\n", stats->name);
1.430 + fprintf(fp, " number of arenas: %u\n", stats->narenas);
1.431 + fprintf(fp, " number of allocations: %u\n", stats->nallocs);
1.432 + fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
1.433 + fprintf(fp, " number of malloc calls: %u\n", stats->nmallocs);
1.434 + fprintf(fp, " number of deallocations: %u\n", stats->ndeallocs);
1.435 + fprintf(fp, " number of allocation growths: %u\n", stats->ngrows);
1.436 + fprintf(fp, " number of in-place growths: %u\n", stats->ninplace);
1.437 + fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
1.438 + fprintf(fp, " number of fast releases: %u\n", stats->nfastrels);
1.439 + fprintf(fp, " total bytes allocated: %u\n", stats->nbytes);
1.440 + fprintf(fp, " mean allocation size: %g\n", mean);
1.441 + fprintf(fp, " standard deviation: %g\n", sqrt(variance));
1.442 + fprintf(fp, " maximum allocation size: %u\n", stats->maxalloc);
1.443 + }
1.444 +}
1.445 +#endif /* PL_ARENAMETER */
