Back to index

lightning-sunbird  0.9+nobinonly
jsarena.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is Mozilla Communicator client code, released
00017  * March 31, 1998.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 1998
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 /*
00041  * Lifetime-based fast allocation, inspired by much prior art, including
00042  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
00043  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
00044  */
00045 #include "jsstddef.h"
00046 #include <stdlib.h>
00047 #include <string.h>
00048 #include "jstypes.h"
00049 #include "jsbit.h"
00050 #include "jsarena.h" /* Added by JSIFY */
00051 #include "jsutil.h" /* Added by JSIFY */
00052 
00053 #ifdef JS_ARENAMETER
00054 static JSArenaStats *arena_stats_list;
00055 
00056 #define COUNT(pool,what)  (pool)->stats.what++
00057 #else
00058 #define COUNT(pool,what)  /* nothing */
00059 #endif
00060 
00061 #define JS_ARENA_DEFAULT_ALIGN  sizeof(double)
00062 
00063 JS_PUBLIC_API(void)
00064 JS_InitArenaPool(JSArenaPool *pool, const char *name, size_t size, size_t align)
00065 {
00066     if (align == 0)
00067         align = JS_ARENA_DEFAULT_ALIGN;
00068     pool->mask = JS_BITMASK(JS_CeilingLog2(align));
00069     pool->first.next = NULL;
00070     pool->first.base = pool->first.avail = pool->first.limit =
00071         JS_ARENA_ALIGN(pool, &pool->first + 1);
00072     pool->current = &pool->first;
00073     pool->arenasize = size;
00074 #ifdef JS_ARENAMETER
00075     memset(&pool->stats, 0, sizeof pool->stats);
00076     pool->stats.name = strdup(name);
00077     pool->stats.next = arena_stats_list;
00078     arena_stats_list = &pool->stats;
00079 #endif
00080 }
00081 
00082 /*
00083  * An allocation that consumes more than pool->arenasize also has a header
00084  * pointing back to its previous arena's next member.  This header is not
00085  * included in [a->base, a->limit), so its space can't be wrongly claimed.
00086  *
00087  * As the header is a pointer, it must be well-aligned.  If pool->mask is
00088  * greater than or equal to POINTER_MASK, the header just preceding a->base
00089  * for an oversized arena a is well-aligned, because a->base is well-aligned.
00090  * However, we may need to add more space to pad the JSArena ** back-pointer
00091  * so that it lies just behind a->base, because a might not be aligned such
00092  * that (jsuword)(a + 1) is on a pointer boundary.
00093  *
00094  * By how much must we pad?  Let M be the alignment modulus for pool and P
00095  * the modulus for a pointer.  Given M >= P, the base of an oversized arena
00096  * that satisfies M is well-aligned for P.
00097  *
00098  * On the other hand, if M < P, we must include enough space in the header
00099  * size to align the back-pointer on a P boundary so that it can be found by
00100  * subtracting P from a->base.  This means a->base must be on a P boundary,
00101  * even though subsequent allocations from a may be aligned on a lesser (M)
00102  * boundary.  Given powers of two M and P as above, the extra space needed
00103  * when M < P is P-M or POINTER_MASK - pool->mask.
00104  *
00105  * The size of a header including padding is given by the HEADER_SIZE macro,
00106  * below, for any pool (for any value of M).
00107  *
00108  * The mask to align a->base for any pool is (pool->mask | POINTER_MASK), or
00109  * HEADER_BASE_MASK(pool).
00110  *
00111  * PTR_TO_HEADER computes the address of the back-pointer, given an oversized
00112  * allocation at p.  By definition, p must be a->base for the arena a that
00113  * contains p.  GET_HEADER and SET_HEADER operate on an oversized arena a, in
00114  * the case of SET_HEADER with back-pointer ap.
00115  */
00116 #define POINTER_MASK            ((jsuword)(JS_ALIGN_OF_POINTER - 1))
00117 #define HEADER_SIZE(pool)       (sizeof(JSArena **)                           \
00118                                  + (((pool)->mask < POINTER_MASK)             \
00119                                     ? POINTER_MASK - (pool)->mask             \
00120                                     : 0))
00121 #define HEADER_BASE_MASK(pool)  ((pool)->mask | POINTER_MASK)
00122 #define PTR_TO_HEADER(pool,p)   (JS_ASSERT(((jsuword)(p)                      \
00123                                             & HEADER_BASE_MASK(pool))         \
00124                                            == 0),                             \
00125                                  (JSArena ***)(p) - 1)
00126 #define GET_HEADER(pool,a)      (*PTR_TO_HEADER(pool, (a)->base))
00127 #define SET_HEADER(pool,a,ap)   (*PTR_TO_HEADER(pool, (a)->base) = (ap))
00128 
00129 JS_PUBLIC_API(void *)
00130 JS_ArenaAllocate(JSArenaPool *pool, size_t nb)
00131 {
00132     JSArena **ap, *a, *b;
00133     jsuword extra, hdrsz, gross;
00134     void *p;
00135 
00136     /*
00137      * Search pool from current forward till we find or make enough space.
00138      *
00139      * NB: subtract nb from a->limit in the loop condition, instead of adding
00140      * nb to a->avail, to avoid overflowing a 32-bit address space (possible
00141      * when running a 32-bit program on a 64-bit system where the kernel maps
00142      * the heap up against the top of the 32-bit address space).
00143      *
00144      * Thanks to Juergen Kreileder <jk@blackdown.de>, who brought this up in
00145      * https://bugzilla.mozilla.org/show_bug.cgi?id=279273.
00146      */
00147     JS_ASSERT((nb & pool->mask) == 0);
00148     for (a = pool->current; nb > a->limit || a->avail > a->limit - nb;
00149          pool->current = a) {
00150         ap = &a->next;
00151         if (!*ap) {
00152             /* Not enough space in pool, so we must malloc. */
00153             extra = (nb > pool->arenasize) ? HEADER_SIZE(pool) : 0;
00154             hdrsz = sizeof *a + extra + pool->mask;
00155             gross = hdrsz + JS_MAX(nb, pool->arenasize);
00156             if (gross < nb)
00157                 return NULL;
00158             b = (JSArena *) malloc(gross);
00159             if (!b)
00160                 return NULL;
00161             b->next = NULL;
00162             b->limit = (jsuword)b + gross;
00163             JS_COUNT_ARENA(pool,++);
00164             COUNT(pool, nmallocs);
00165 
00166             /* If oversized, store ap in the header, just before a->base. */
00167             *ap = a = b;
00168             JS_ASSERT(gross <= JS_UPTRDIFF(a->limit, a));
00169             if (extra) {
00170                 a->base = a->avail =
00171                     ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
00172                 SET_HEADER(pool, a, ap);
00173             } else {
00174                 a->base = a->avail = JS_ARENA_ALIGN(pool, a + 1);
00175             }
00176             continue;
00177         }
00178         a = *ap;                                /* move to next arena */
00179     }
00180 
00181     p = (void *)a->avail;
00182     a->avail += nb;
00183     JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00184     return p;
00185 }
00186 
00187 JS_PUBLIC_API(void *)
00188 JS_ArenaRealloc(JSArenaPool *pool, void *p, size_t size, size_t incr)
00189 {
00190     JSArena **ap, *a, *b;
00191     jsuword boff, aoff, extra, hdrsz, gross;
00192 
00193     /*
00194      * Use the oversized-single-allocation header to avoid searching for ap.
00195      * See JS_ArenaAllocate, the SET_HEADER call.
00196      */
00197     if (size > pool->arenasize) {
00198         ap = *PTR_TO_HEADER(pool, p);
00199         a = *ap;
00200     } else {
00201         ap = &pool->first.next;
00202         while ((a = *ap) != pool->current)
00203             ap = &a->next;
00204     }
00205 
00206     JS_ASSERT(a->base == (jsuword)p);
00207     boff = JS_UPTRDIFF(a->base, a);
00208     aoff = JS_ARENA_ALIGN(pool, size + incr);
00209     JS_ASSERT(aoff > pool->arenasize);
00210     extra = HEADER_SIZE(pool);                  /* oversized header holds ap */
00211     hdrsz = sizeof *a + extra + pool->mask;     /* header and alignment slop */
00212     gross = hdrsz + aoff;
00213     JS_ASSERT(gross > aoff);
00214     a = (JSArena *) realloc(a, gross);
00215     if (!a)
00216         return NULL;
00217 #ifdef JS_ARENAMETER
00218     pool->stats.nreallocs++;
00219 #endif
00220 
00221     if (a != *ap) {
00222         /* Oops, realloc moved the allocation: update other pointers to a. */
00223         if (pool->current == *ap)
00224             pool->current = a;
00225         b = a->next;
00226         if (b && b->avail - b->base > pool->arenasize) {
00227             JS_ASSERT(GET_HEADER(pool, b) == &(*ap)->next);
00228             SET_HEADER(pool, b, &a->next);
00229         }
00230 
00231         /* Now update *ap, the next link of the arena before a. */
00232         *ap = a;
00233     }
00234 
00235     a->base = ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
00236     a->limit = (jsuword)a + gross;
00237     a->avail = a->base + aoff;
00238     JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00239 
00240     /* Check whether realloc aligned differently, and copy if necessary. */
00241     if (boff != JS_UPTRDIFF(a->base, a))
00242         memmove((void *)a->base, (char *)a + boff, size);
00243 
00244     /* Store ap in the oversized-load arena header. */
00245     SET_HEADER(pool, a, ap);
00246     return (void *)a->base;
00247 }
00248 
00249 JS_PUBLIC_API(void *)
00250 JS_ArenaGrow(JSArenaPool *pool, void *p, size_t size, size_t incr)
00251 {
00252     void *newp;
00253 
00254     /*
00255      * If p points to an oversized allocation, it owns an entire arena, so we
00256      * can simply realloc the arena.
00257      */
00258     if (size > pool->arenasize)
00259         return JS_ArenaRealloc(pool, p, size, incr);
00260 
00261     JS_ARENA_ALLOCATE(newp, pool, size + incr);
00262     if (newp)
00263         memcpy(newp, p, size);
00264     return newp;
00265 }
00266 
00267 /*
00268  * Free tail arenas linked after head, which may not be the true list head.
00269  * Reset pool->current to point to head in case it pointed at a tail arena.
00270  */
00271 static void
00272 FreeArenaList(JSArenaPool *pool, JSArena *head)
00273 {
00274     JSArena **ap, *a;
00275 
00276     ap = &head->next;
00277     a = *ap;
00278     if (!a)
00279         return;
00280 
00281 #ifdef DEBUG
00282     do {
00283         JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00284         a->avail = a->base;
00285         JS_CLEAR_UNUSED(a);
00286     } while ((a = a->next) != NULL);
00287     a = *ap;
00288 #endif
00289 
00290     do {
00291         *ap = a->next;
00292         JS_CLEAR_ARENA(a);
00293         JS_COUNT_ARENA(pool,--);
00294         free(a);
00295     } while ((a = *ap) != NULL);
00296 
00297     pool->current = head;
00298 }
00299 
00300 JS_PUBLIC_API(void)
00301 JS_ArenaRelease(JSArenaPool *pool, char *mark)
00302 {
00303     JSArena *a;
00304 
00305     for (a = &pool->first; a; a = a->next) {
00306         JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00307 
00308         if (JS_UPTRDIFF(mark, a->base) <= JS_UPTRDIFF(a->avail, a->base)) {
00309             a->avail = JS_ARENA_ALIGN(pool, mark);
00310             JS_ASSERT(a->avail <= a->limit);
00311             FreeArenaList(pool, a);
00312             return;
00313         }
00314     }
00315 }
00316 
00317 JS_PUBLIC_API(void)
00318 JS_ArenaFreeAllocation(JSArenaPool *pool, void *p, size_t size)
00319 {
00320     JSArena **ap, *a, *b;
00321     jsuword q;
00322 
00323     /*
00324      * If the allocation is oversized, it consumes an entire arena, and it has
00325      * a header just before the allocation pointing back to its predecessor's
00326      * next member.  Otherwise, we have to search pool for a.
00327      */
00328     if (size > pool->arenasize) {
00329         ap = *PTR_TO_HEADER(pool, p);
00330         a = *ap;
00331     } else {
00332         q = (jsuword)p + size;
00333         q = JS_ARENA_ALIGN(pool, q);
00334         ap = &pool->first.next;
00335         while ((a = *ap) != NULL) {
00336             JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00337 
00338             if (a->avail == q) {
00339                 /*
00340                  * If a is consumed by the allocation at p, we can free it to
00341                  * the malloc heap.
00342                  */
00343                 if (a->base == (jsuword)p)
00344                     break;
00345 
00346                 /*
00347                  * We can't free a, but we can "retract" its avail cursor --
00348                  * whether there are others after it in pool.
00349                  */
00350                 a->avail = (jsuword)p;
00351                 return;
00352             }
00353             ap = &a->next;
00354         }
00355     }
00356 
00357     /*
00358      * At this point, a is doomed, so ensure that pool->current doesn't point
00359      * at it.  We must preserve LIFO order of mark/release cursors, so we use
00360      * the oversized-allocation arena's back pointer (or if not oversized, we
00361      * use the result of searching the entire pool) to compute the address of
00362      * the arena that precedes a.
00363      */
00364     if (pool->current == a)
00365         pool->current = (JSArena *) ((char *)ap - offsetof(JSArena, next));
00366 
00367     /*
00368      * This is a non-LIFO deallocation, so take care to fix up a->next's back
00369      * pointer in its header, if a->next is oversized.
00370      */
00371     *ap = b = a->next;
00372     if (b && b->avail - b->base > pool->arenasize) {
00373         JS_ASSERT(GET_HEADER(pool, b) == &a->next);
00374         SET_HEADER(pool, b, ap);
00375     }
00376     JS_CLEAR_ARENA(a);
00377     JS_COUNT_ARENA(pool,--);
00378     free(a);
00379 }
00380 
00381 JS_PUBLIC_API(void)
00382 JS_FreeArenaPool(JSArenaPool *pool)
00383 {
00384     FreeArenaList(pool, &pool->first);
00385     COUNT(pool, ndeallocs);
00386 }
00387 
00388 JS_PUBLIC_API(void)
00389 JS_FinishArenaPool(JSArenaPool *pool)
00390 {
00391     FreeArenaList(pool, &pool->first);
00392 #ifdef JS_ARENAMETER
00393     {
00394         JSArenaStats *stats, **statsp;
00395 
00396         if (pool->stats.name)
00397             free(pool->stats.name);
00398         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
00399              statsp = &stats->next) {
00400             if (stats == &pool->stats) {
00401                 *statsp = stats->next;
00402                 return;
00403             }
00404         }
00405     }
00406 #endif
00407 }
00408 
00409 JS_PUBLIC_API(void)
00410 JS_ArenaFinish()
00411 {
00412 }
00413 
00414 JS_PUBLIC_API(void)
00415 JS_ArenaShutDown(void)
00416 {
00417 }
00418 
00419 #ifdef JS_ARENAMETER
00420 JS_PUBLIC_API(void)
00421 JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb)
00422 {
00423     pool->stats.nallocs++;
00424     pool->stats.nbytes += nb;
00425     if (nb > pool->stats.maxalloc)
00426         pool->stats.maxalloc = nb;
00427     pool->stats.variance += nb * nb;
00428 }
00429 
00430 JS_PUBLIC_API(void)
00431 JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr)
00432 {
00433     pool->stats.ninplace++;
00434 }
00435 
00436 JS_PUBLIC_API(void)
00437 JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t incr)
00438 {
00439     pool->stats.ngrows++;
00440     pool->stats.nbytes += incr;
00441     pool->stats.variance -= size * size;
00442     size += incr;
00443     if (size > pool->stats.maxalloc)
00444         pool->stats.maxalloc = size;
00445     pool->stats.variance += size * size;
00446 }
00447 
00448 JS_PUBLIC_API(void)
00449 JS_ArenaCountRelease(JSArenaPool *pool, char *mark)
00450 {
00451     pool->stats.nreleases++;
00452 }
00453 
00454 JS_PUBLIC_API(void)
00455 JS_ArenaCountRetract(JSArenaPool *pool, char *mark)
00456 {
00457     pool->stats.nfastrels++;
00458 }
00459 
00460 #include <math.h>
00461 #include <stdio.h>
00462 
00463 JS_PUBLIC_API(void)
00464 JS_DumpArenaStats(FILE *fp)
00465 {
00466     JSArenaStats *stats;
00467     uint32 nallocs, nbytes;
00468     double mean, variance, sigma;
00469 
00470     for (stats = arena_stats_list; stats; stats = stats->next) {
00471         nallocs = stats->nallocs;
00472         if (nallocs != 0) {
00473             nbytes = stats->nbytes;
00474             mean = (double)nbytes / nallocs;
00475             variance = stats->variance * nallocs - nbytes * nbytes;
00476             if (variance < 0 || nallocs == 1)
00477                 variance = 0;
00478             else
00479                 variance /= nallocs * (nallocs - 1);
00480             sigma = sqrt(variance);
00481         } else {
00482             mean = variance = sigma = 0;
00483         }
00484 
00485         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
00486         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
00487         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
00488         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
00489         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
00490         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
00491         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
00492         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
00493         fprintf(fp, " number of realloc'ing growths: %u\n", stats->nreallocs);
00494         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
00495         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
00496         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
00497         fprintf(fp, "          mean allocation size: %g\n", mean);
00498         fprintf(fp, "            standard deviation: %g\n", sigma);
00499         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
00500     }
00501 }
00502 #endif /* JS_ARENAMETER */