nsprpub/lib/ds/plarena.c

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