nsprpub/lib/ds/plarena.c

   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 #ifdef PL_ARENAMETER
  21 static PLArenaStats *arena_stats_list;
  22
  23 #define COUNT(pool,what)  (pool)->stats.what++
  24 #else
  25 #define COUNT(pool,what)  /* nothing */
  26 #endif
  27
  28 #define PL_ARENA_DEFAULT_ALIGN  sizeof(double)
  29
  30 PR_IMPLEMENT(void) PL_InitArenaPool(
  31     PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
  32 {
  33     /*
  34      * Look-up table of PR_BITMASK(PR_CeilingLog2(align)) values for
  35      * align = 1 to 32.
  36      */
  37     static const PRUint8 pmasks[33] = {
  38         0,                                               /*  not used */
  39         0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,15,  /*  1 ... 16 */
  40         31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31   /* 17 ... 32 */
  41     };
  42
  43     if (align == 0) {
  44         align = PL_ARENA_DEFAULT_ALIGN;
  45     }
  46
  47     if (align < sizeof(pmasks)/sizeof(pmasks[0])) {
  48         pool->mask = pmasks[align];
  49     }
  50     else {
  51         pool->mask = PR_BITMASK(PR_CeilingLog2(align));
  52     }
  53
  54     pool->first.next = NULL;
  55     /* Set all three addresses in pool->first to the same dummy value.
  56      * These addresses are only compared with each other, but never
  57      * dereferenced. */
  58     pool->first.base = pool->first.avail = pool->first.limit =
  59             (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
  60     pool->current = &pool->first;
  61     /*
  62      * Compute the net size so that each arena's gross size is |size|.
  63      * sizeof(PLArena) + pool->mask is the header and alignment slop
  64      * that PL_ArenaAllocate adds to the net size.
  65      */
  66     if (size > sizeof(PLArena) + pool->mask) {
  67         pool->arenasize = size - (sizeof(PLArena) + pool->mask);
  68     }
  69     else {
  70         pool->arenasize = size;
  71     }
  72 #ifdef PL_ARENAMETER
  73     memset(&pool->stats, 0, sizeof pool->stats);
  74     pool->stats.name = strdup(name);
  75     pool->stats.next = arena_stats_list;
  76     arena_stats_list = &pool->stats;
  77 #endif
  78 }
  79
  80
  81 /*
  82 ** PL_ArenaAllocate() -- allocate space from an arena pool
  83 **
  84 ** Description: PL_ArenaAllocate() allocates space from an arena
  85 ** pool.
  86 **
  87 ** First, try to satisfy the request from arenas starting at
  88 ** pool->current. Then try to allocate a new arena from the heap.
  89 **
  90 ** Returns: pointer to allocated space or NULL
  91 **
  92 ** Notes: The original implementation had some difficult to
  93 ** solve bugs; the code was difficult to read. Sometimes it's
  94 ** just easier to rewrite it. I did that. larryh.
  95 **
  96 ** See also: bugzilla: 45343.
  97 **
  98 */
  99
 100 PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
 101 {
 102     PLArena *a;
 103     char *rp;     /* returned pointer */
 104     PRUint32 nbOld;
 105
 106     PR_ASSERT((nb & pool->mask) == 0);
 107
 108     nbOld = nb;
 109     nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
 110     if (nb < nbOld) {
 111         return NULL;
 112     }
 113
 114     /* attempt to allocate from arenas at pool->current */
 115     {
 116         a = pool->current;
 117         do {
 118             if ( nb <= a->limit - a->avail )  {
 119                 pool->current = a;
 120                 rp = (char *)a->avail;
 121                 a->avail += nb;
 122                 return rp;
 123             }
 124         } while( NULL != (a = a->next) );
 125     }
 126
 127     /* attempt to allocate from the heap */
 128     {
 129         PRUint32 sz = PR_MAX(pool->arenasize, nb);
 130         if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
 131             a = NULL;
 132         } else {
 133             sz += sizeof *a + pool->mask;  /* header and alignment slop */
 134             a = (PLArena*)PR_MALLOC(sz);
 135         }
 136         if ( NULL != a )  {
 137             a->limit = (PRUword)a + sz;
 138             a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
 139             PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
 140             rp = (char *)a->avail;
 141             a->avail += nb;
 142             PR_ASSERT(a->avail <= a->limit);
 143             /* the newly allocated arena is linked after pool->current
 144             *  and becomes pool->current */
 145             a->next = pool->current->next;
 146             pool->current->next = a;
 147             pool->current = a;
 148             if ( NULL == pool->first.next ) {
 149                 pool->first.next = a;
 150             }
 151             PL_COUNT_ARENA(pool,++);
 152             COUNT(pool, nmallocs);
 153             return(rp);
 154         }
 155     }
 156
 157     /* we got to here, and there's no memory to allocate */
 158     return(NULL);
 159 } /* --- end PL_ArenaAllocate() --- */
 160
 161 PR_IMPLEMENT(void *) PL_ArenaGrow(
 162     PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr)
 163 {
 164     void *newp;
 165
 166     if (PR_UINT32_MAX - size < incr) {
 167         return NULL;
 168     }
 169     PL_ARENA_ALLOCATE(newp, pool, size + incr);
 170     if (newp) {
 171         memcpy(newp, p, size);
 172     }
 173     return newp;
 174 }
 175
 176 PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
 177 {
 178     PLArena *a;
 179
 180     for (a = pool->first.next; a; a = a->next) {
 181         PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
 182         a->avail = a->base;
 183         PL_CLEAR_UNUSED_PATTERN(a, pattern);
 184         PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
 185     }
 186 }
 187
 188 /*
 189  * Free tail arenas linked after head, which may not be the true list head.
 190  * Reset pool->current to point to head in case it pointed at a tail arena.
 191  */
 192 static void FreeArenaList(PLArenaPool *pool, PLArena *head)
 193 {
 194     PLArena *a = head->next;
 195     if (!a) {
 196         return;
 197     }
 198
 199     head->next = NULL;
 200
 201     do {
 202         PLArena *tmp = a;
 203         a = a->next;
 204         PL_CLEAR_ARENA(tmp);
 205         PL_COUNT_ARENA(pool,--);
 206         PR_DELETE(tmp);
 207     } while (a);
 208
 209     pool->current = head;
 210 }
 211
 212 PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
 213 {
 214     PLArena *a;
 215
 216     for (a = &pool->first; a; a = a->next) {
 217         if (PR_UPTRDIFF(mark, a->base) <= PR_UPTRDIFF(a->avail, a->base)) {
 218             a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
 219             FreeArenaList(pool, a);
 220             return;
 221         }
 222     }
 223 }
 224
 225 PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
 226 {
 227     FreeArenaList(pool, &pool->first);
 228     COUNT(pool, ndeallocs);
 229 }
 230
 231 PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
 232 {
 233     FreeArenaList(pool, &pool->first);
 234 #ifdef PL_ARENAMETER
 235     {
 236         PLArenaStats *stats, **statsp;
 237
 238         if (pool->stats.name) {
 239             PR_DELETE(pool->stats.name);
 240         }
 241         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
 242              statsp = &stats->next) {
 243             if (stats == &pool->stats) {
 244                 *statsp = stats->next;
 245                 return;
 246             }
 247         }
 248     }
 249 #endif
 250 }
 251
 252 PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
 253 {
 254 }
 255
 256 PR_IMPLEMENT(void) PL_ArenaFinish(void)
 257 {
 258 }
 259
 260 PR_IMPLEMENT(size_t) PL_SizeOfArenaPoolExcludingPool(
 261     const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf)
 262 {
 263     /*
 264      * The first PLArena is within |pool|, so don't measure it.  Subsequent
 265      * PLArenas are separate and must be measured.
 266      */
 267     size_t size = 0;
 268     const PLArena *arena = pool->first.next;
 269     while (arena) {
 270         size += mallocSizeOf(arena);
 271         arena = arena->next;
 272     }
 273     return size;
 274 }
 275
 276 #ifdef PL_ARENAMETER
 277 PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
 278 {
 279     pool->stats.nallocs++;
 280     pool->stats.nbytes += nb;
 281     if (nb > pool->stats.maxalloc) {
 282         pool->stats.maxalloc = nb;
 283     }
 284     pool->stats.variance += nb * nb;
 285 }
 286
 287 PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
 288     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
 289 {
 290     pool->stats.ninplace++;
 291 }
 292
 293 PR_IMPLEMENT(void) PL_ArenaCountGrowth(
 294     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
 295 {
 296     pool->stats.ngrows++;
 297     pool->stats.nbytes += incr;
 298     pool->stats.variance -= size * size;
 299     size += incr;
 300     if (size > pool->stats.maxalloc) {
 301         pool->stats.maxalloc = size;
 302     }
 303     pool->stats.variance += size * size;
 304 }
 305
 306 PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
 307 {
 308     pool->stats.nreleases++;
 309 }
 310
 311 PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
 312 {
 313     pool->stats.nfastrels++;
 314 }
 315
 316 #include <math.h>
 317 #include <stdio.h>
 318
 319 PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
 320 {
 321     PLArenaStats *stats;
 322     double mean, variance;
 323
 324     for (stats = arena_stats_list; stats; stats = stats->next) {
 325         if (stats->nallocs != 0) {
 326             mean = (double)stats->nbytes / stats->nallocs;
 327             variance = fabs(stats->variance / stats->nallocs - mean * mean);
 328         } else {
 329             mean = variance = 0;
 330         }
 331
 332         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
 333         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
 334         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
 335         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
 336         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
 337         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
 338         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
 339         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
 340         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
 341         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
 342         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
 343         fprintf(fp, "          mean allocation size: %g\n", mean);
 344         fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
 345         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
 346     }
 347 }
 348 #endif /* PL_ARENAMETER */