OSX/libsecurity_asn1/lib/plarena.c

   1 /*
   2  * Copyright (c) 2003-2006,2008,2010-2012 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*
  24  * The contents of this file are subject to the Mozilla Public
  25  * License Version 1.1 (the "License"); you may not use this file
  26  * except in compliance with the License. You may obtain a copy of
  27  * the License at http://www.mozilla.org/MPL/
  28  *
  29  * Software distributed under the License is distributed on an "AS
  30  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
  31  * implied. See the License for the specific language governing
  32  * rights and limitations under the License.
  33  *
  34  * The Original Code is the Netscape Portable Runtime (NSPR).
  35  *
  36  * The Initial Developer of the Original Code is Netscape
  37  * Communications Corporation.  Portions created by Netscape are
  38  * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
  39  * Rights Reserved.
  40  *
  41  * Contributor(s):
  42  *
  43  * Alternatively, the contents of this file may be used under the
  44  * terms of the GNU General Public License Version 2 or later (the
  45  * "GPL"), in which case the provisions of the GPL are applicable
  46  * instead of those above.  If you wish to allow use of your
  47  * version of this file only under the terms of the GPL and not to
  48  * allow others to use your version of this file under the MPL,
  49  * indicate your decision by deleting the provisions above and
  50  * replace them with the notice and other provisions required by
  51  * the GPL.  If you do not delete the provisions above, a recipient
  52  * may use your version of this file under either the MPL or the
  53  * GPL.
  54  */
  55
  56 /*
  57  * Lifetime-based fast allocation, inspired by much prior art, including
  58  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
  59  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
  60  */
  61 #include <stdlib.h>
  62 #include <string.h>
  63 #include "plarena.h"
  64 #include "prmem.h"
  65 #include "prbit.h"
  66 #include "prlog.h"
  67 #include "prinit.h"
  68
  69 #ifdef PL_ARENAMETER
  70 static PLArenaStats *arena_stats_list;
  71
  72 #define COUNT(pool,what)  (pool)->stats.what++
  73 #else
  74 #define COUNT(pool,what)  /* nothing */
  75 #endif
  76
  77 #define PL_ARENA_DEFAULT_ALIGN  sizeof(double)
  78
  79 PR_IMPLEMENT(void) PL_InitArenaPool(
  80     PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
  81 {
  82 #if !defined (__GNUC__)
  83 #pragma unused (name)
  84 #endif
  85
  86     if (align == 0)
  87         align = PL_ARENA_DEFAULT_ALIGN;
  88     pool->mask = PR_BITMASK(PR_CeilingLog2(align));
  89     pool->first.next = NULL;
  90     pool->first.base = pool->first.avail = pool->first.limit =
  91         (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
  92     pool->current = &pool->first;
  93     pool->arenasize = size;
  94 #ifdef PL_ARENAMETER
  95     memset(&pool->stats, 0, sizeof pool->stats);
  96     pool->stats.name = strdup(name);
  97     pool->stats.next = arena_stats_list;
  98     arena_stats_list = &pool->stats;
  99 #endif
 100 }
 101
 102 #if __APPLE__
 103 #define MAX_SIZE (PR_UINT32_MAX >> 1)
 104 #endif
 105
 106 /*
 107 ** PL_ArenaAllocate() -- allocate space from an arena pool
 108 **
 109 ** Description: PL_ArenaAllocate() allocates space from an arena
 110 ** pool.
 111 **
 112 ** First, try to satisfy the request from arenas starting at
 113 ** pool->current. Then try to allocate a new arena from the heap.
 114 **
 115 ** Returns: pointer to allocated space or NULL
 116 **
 117 ** Notes: The original implementation had some difficult to
 118 ** solve bugs; the code was difficult to read. Sometimes it's
 119 ** just easier to rewrite it. I did that. larryh.
 120 **
 121 ** See also: bugzilla: 45343.
 122 **
 123 */
 124
 125 PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
 126 {
 127     PLArena *a;
 128     char *rp;     /* returned pointer */
 129     PRUint32 nbOld;
 130
 131     PR_ASSERT((nb & pool->mask) == 0);
 132     nbOld = nb;
 133 #ifdef __APPLE__
 134     nb = PL_ARENA_ALIGN(pool, nb); /* force alignment, cast is useless/causes warning. */
 135 #else
 136     nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
 137 #endif
 138     /* ensure that alignment didn't cause overflow */
 139     if (nb < nbOld)
 140         return NULL;
 141
 142     /* attempt to allocate from arenas at pool->current */
 143     {
 144         a = pool->current;
 145         do {
 146             if ( nb <= a->limit - a->avail )  {
 147                 pool->current = a;
 148                 rp = (char *)a->avail;
 149                 a->avail += nb;
 150                 return rp;
 151             }
 152         } while( NULL != (a = a->next) );
 153     }
 154
 155     /* attempt to allocate from the heap */
 156     {
 157         PRUint32 sz = PR_MAX(pool->arenasize, nb);
 158         if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
 159             a = NULL;
 160         } else {
 161             sz += sizeof *a + pool->mask;  /* header and alignment slop */
 162             a = (PLArena*)PR_MALLOC(sz);
 163         }
 164 #ifdef __APPLE__
 165         // Check for integer overflow on a->avail += nb
 166         PRUword a_avail_tmp=(PRUword)PL_ARENA_ALIGN(pool, a + 1);
 167         if (a_avail_tmp + nb < a_avail_tmp)
 168         {
 169             PR_FREEIF(a); // Set a back to NULL
 170         }
 171 #endif
 172         if ( NULL != a )  {
 173             a->limit = (PRUword)a + sz;
 174 #ifdef __APPLE__
 175             a->base = a->avail = a_avail_tmp;
 176 #else
 177             a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
 178 #endif
 179             rp = (char *)a->avail;
 180             a->avail += nb;
 181             /* the newly allocated arena is linked after pool->current
 182             *  and becomes pool->current */
 183             a->next = pool->current->next;
 184             pool->current->next = a;
 185             pool->current = a;
 186             if ( NULL == pool->first.next )
 187                 pool->first.next = a;
 188             PL_COUNT_ARENA(pool,++);
 189             COUNT(pool, nmallocs);
 190             return(rp);
 191         }
 192     }
 193
 194     /* we got to here, and there's no memory to allocate */
 195     return(NULL);
 196 } /* --- end PL_ArenaAllocate() --- */
 197
 198 /*
 199  * Grow, a.k.a. realloc. The PL_ARENA_GROW macro has already handled
 200  * the possible grow-in-place action in which the current PLArena is the
 201  * source of the incoming pointer, and there is room in that arena for
 202  * the requested size.
 203  */
 204 PR_IMPLEMENT(void *) PL_ArenaGrow(
 205     PLArenaPool *pool, void *p, PRUint32 origSize, PRUint32 incr)
 206 {
 207     void *newp;
 208         PLArena *thisArena;
 209         PLArena *lastArena;
 210         PRUint32 origAlignSize;         // bytes currently reserved for caller
 211         PRUint32 newSize;                       // bytes actually mallocd here
 212
 213     // Enforce maximal size before any potential implicit truncation
 214     if (origSize>=MAX_SIZE || incr>=MAX_SIZE) {
 215         return NULL;
 216     }
 217         origAlignSize = PL_ARENA_ALIGN(pool, origSize);
 218     if (origAlignSize>=MAX_SIZE) {
 219         return NULL;
 220     }
 221
 222     /* expand at least by 2x */
 223     newSize = PR_MAX(origAlignSize+incr, 2*origAlignSize);
 224     newSize = PL_ARENA_ALIGN(pool, newSize);
 225
 226     if (newSize>=MAX_SIZE) {
 227         return NULL;
 228     }
 229
 230     PL_ARENA_ALLOCATE(newp, pool, newSize);
 231     if (newp == NULL) {
 232         return NULL;
 233     }
 234         /*
 235          * Trim back the memory we just allocated to the amount our caller really
 236          * needs, leaving the remainder for grow-in-place on subsequent calls
 237          * to PL_ARENA_GROW.
 238          */
 239         PRUint32 newAlignSize = PL_ARENA_ALIGN(pool, origSize+incr);
 240         PR_ASSERT(pool->current->avail == ((PRUword)newp + newSize));
 241         pool->current->avail = (PRUword)newp + newAlignSize;
 242         PR_ASSERT(pool->current->avail <= pool->current->limit);
 243
 244         /* "realloc" */
 245         memcpy(newp, p, origSize);
 246
 247         /*
 248          * Free old memory only if it's the entire outstanding allocated
 249          * memory associated with one of our known PLArenas.
 250          */
 251         lastArena = &pool->first;                       /* pool->first always empty */
 252         thisArena = lastArena->next;            /* so, start here */
 253
 254         PRUword origPtr = (PRUword)p;
 255         while(thisArena != NULL) {
 256                 if(origPtr == thisArena->base) {
 257                         if((origPtr + origAlignSize) == thisArena->avail) {
 258                                 /* unlink */
 259                                 lastArena->next = thisArena->next;
 260
 261                                 /* and free */
 262                                 PL_CLEAR_ARENA(thisArena);
 263                                 PL_COUNT_ARENA(pool,--);
 264                                 PR_DELETE(thisArena);
 265                                 break;
 266                         }
 267                 }
 268                 lastArena = thisArena;
 269                 thisArena = thisArena->next;
 270         }
 271         /*
 272          * Note: inability to free is not an error; it just causes a temporary leak
 273          * of the old buffer (until the arena pool is freed, of course).
 274          */
 275     return newp;
 276 }
 277
 278 static void ClearArenaList(PLArena *a, PRInt32 pattern)
 279 {
 280
 281     for (; a; a = a->next) {
 282         PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
 283         a->avail = a->base;
 284         PL_CLEAR_UNUSED_PATTERN(a, pattern);
 285     }
 286 }
 287
 288 PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
 289 {
 290     ClearArenaList(pool->first.next, pattern);
 291 }
 292
 293 /*
 294  * Free tail arenas linked after head, which may not be the true list head.
 295  * Reset pool->current to point to head in case it pointed at a tail arena.
 296  */
 297 static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
 298 {
 299     PLArena **ap, *a;
 300
 301     ap = &head->next;
 302     a = *ap;
 303     if (!a)
 304         return;
 305
 306         do {
 307                 *ap = a->next;
 308                 PL_CLEAR_ARENA(a);
 309                 PL_COUNT_ARENA(pool,--);
 310                 PR_DELETE(a);
 311         } while ((a = *ap) != 0);
 312
 313     pool->current = head;
 314 }
 315
 316 PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
 317 {
 318         #if ARENA_MARK_ENABLE
 319     PLArena *a;
 320
 321     for (a = pool->first.next; a; a = a->next) {
 322         if (PR_UPTRDIFF(mark, a->base) < PR_UPTRDIFF(a->avail, a->base)) {
 323             a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
 324             FreeArenaList(pool, a, PR_FALSE);
 325             return;
 326         }
 327     }
 328         #endif  /* ARENA_MARK_ENABLE */
 329 }
 330
 331 PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
 332 {
 333     FreeArenaList(pool, &pool->first, PR_FALSE);
 334     COUNT(pool, ndeallocs);
 335 }
 336
 337 PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
 338 {
 339     FreeArenaList(pool, &pool->first, PR_TRUE);
 340 #ifdef PL_ARENAMETER
 341     {
 342         PLArenaStats *stats, **statsp;
 343
 344         if (pool->stats.name)
 345             PR_DELETE(pool->stats.name);
 346         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
 347              statsp = &stats->next) {
 348             if (stats == &pool->stats) {
 349                 *statsp = stats->next;
 350                 return;
 351             }
 352         }
 353     }
 354 #endif
 355 }
 356
 357 PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
 358 {
 359 }
 360
 361 PR_IMPLEMENT(void) PL_ArenaFinish(void)
 362 {
 363 }
 364
 365 #ifdef PL_ARENAMETER
 366 PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
 367 {
 368     pool->stats.nallocs++;
 369     pool->stats.nbytes += nb;
 370     if (nb > pool->stats.maxalloc)
 371         pool->stats.maxalloc = nb;
 372     pool->stats.variance += nb * nb;
 373 }
 374
 375 PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
 376     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
 377 {
 378     pool->stats.ninplace++;
 379 }
 380
 381 PR_IMPLEMENT(void) PL_ArenaCountGrowth(
 382     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
 383 {
 384     pool->stats.ngrows++;
 385     pool->stats.nbytes += incr;
 386     pool->stats.variance -= size * size;
 387     size += incr;
 388     if (size > pool->stats.maxalloc)
 389         pool->stats.maxalloc = size;
 390     pool->stats.variance += size * size;
 391 }
 392
 393 PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
 394 {
 395     pool->stats.nreleases++;
 396 }
 397
 398 PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
 399 {
 400     pool->stats.nfastrels++;
 401 }
 402
 403 #include <math.h>
 404 #include <stdio.h>
 405
 406 PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
 407 {
 408     PLArenaStats *stats;
 409     double mean, variance;
 410
 411     for (stats = arena_stats_list; stats; stats = stats->next) {
 412         if (stats->nallocs != 0) {
 413             mean = (double)stats->nbytes / stats->nallocs;
 414             variance = fabs(stats->variance / stats->nallocs - mean * mean);
 415         } else {
 416             mean = variance = 0;
 417         }
 418
 419         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
 420         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
 421         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
 422         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
 423         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
 424         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
 425         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
 426         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
 427         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
 428         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
 429         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
 430         fprintf(fp, "          mean allocation size: %g\n", mean);
 431         fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
 432         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
 433     }
 434 }
 435 #endif /* PL_ARENAMETER */