tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

plarena.c (9413B)

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