home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / lib / ds / plarena.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  8.6 KB  |  300 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. /*
  20.  * Lifetime-based fast allocation, inspired by much prior art, including
  21.  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
  22.  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
  23.  */
  24. #include <stdlib.h>
  25. #include <string.h>
  26. #include "plarena.h"
  27. #include "prmem.h"
  28. #include "prbit.h"
  29. #include "prlog.h"
  30.  
  31. static PLArena *arena_freelist;
  32.  
  33. #ifdef PL_ARENAMETER
  34. static PLArenaStats *arena_stats_list;
  35.  
  36. #define COUNT(pool,what)  (pool)->stats.what++
  37. #else
  38. #define COUNT(pool,what)  /* nothing */
  39. #endif
  40.  
  41. #define PL_ARENA_DEFAULT_ALIGN  sizeof(double)
  42.  
  43. PR_IMPLEMENT(void) PL_InitArenaPool(
  44.     PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
  45. {
  46. #if defined(XP_MAC)
  47. #pragma unused (name)
  48. #endif
  49.  
  50.     if (align == 0)
  51.         align = PL_ARENA_DEFAULT_ALIGN;
  52.     pool->mask = PR_BITMASK(PR_CeilingLog2(align));
  53.     pool->first.next = NULL;
  54.     pool->first.base = pool->first.avail = pool->first.limit =
  55.         (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
  56.     pool->current = &pool->first;
  57.     pool->arenasize = size;
  58. #ifdef PL_ARENAMETER
  59.     memset(&pool->stats, 0, sizeof pool->stats);
  60.     pool->stats.name = strdup(name);
  61.     pool->stats.next = arena_stats_list;
  62.     arena_stats_list = &pool->stats;
  63. #endif
  64. }
  65.  
  66. PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
  67. {
  68.     PLArena **ap, *a, *b;
  69.     PRUint32 sz;
  70.     void *p;
  71.  
  72.     PR_ASSERT((nb & pool->mask) == 0);
  73. #if defined(WIN16)
  74.     if (nb >= 60000U)
  75.         return 0;
  76. #endif  /* WIN16 */
  77.     ap = &arena_freelist;
  78.     for (a = pool->current; a->avail + nb > a->limit; pool->current = a) {
  79.         if (a->next) {                          /* move to next arena */
  80.             a = a->next;
  81.             continue;
  82.         }
  83.         while ((b = *ap) != 0) {                /* reclaim a free arena */
  84.             if (b->limit - b->base == pool->arenasize) {
  85.                 *ap = b->next;
  86.                 b->next = 0;
  87.                 a = a->next = b;
  88.                 COUNT(pool, nreclaims);
  89.                 goto claim;
  90.             }
  91.             ap = &b->next;
  92.         }
  93.         sz = PR_MAX(pool->arenasize, nb);        /* allocate a new arena */
  94.         sz += sizeof *a + pool->mask;           /* header and alignment slop */
  95.         b = (PLArena*)PR_MALLOC(sz);
  96.         if (!b)
  97.             return 0;
  98.         a = a->next = b;
  99.         a->next = 0;
  100.         a->limit = (PRUword)a + sz;
  101.         PL_COUNT_ARENA(pool,++);
  102.         COUNT(pool, nmallocs);
  103.     claim:
  104.         a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
  105.     }
  106.     p = (void *)a->avail;
  107.     a->avail += nb;
  108.     return p;
  109. }
  110.  
  111. PR_IMPLEMENT(void *) PL_ArenaGrow(
  112.     PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr)
  113. {
  114.     void *newp;
  115.  
  116.     PL_ARENA_ALLOCATE(newp, pool, size + incr);
  117.     if (newp)
  118.         memcpy(newp, p, size);
  119.     return newp;
  120. }
  121.  
  122. /*
  123.  * Free tail arenas linked after head, which may not be the true list head.
  124.  * Reset pool->current to point to head in case it pointed at a tail arena.
  125.  */
  126. static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
  127. {
  128.     PLArena **ap, *a;
  129.  
  130.     ap = &head->next;
  131.     a = *ap;
  132.     if (!a)
  133.         return;
  134.  
  135. #ifdef DEBUG
  136.     do {
  137.         PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
  138.         a->avail = a->base;
  139.         PL_CLEAR_UNUSED(a);
  140.     } while ((a = a->next) != 0);
  141.     a = *ap;
  142. #endif
  143.  
  144.     if (reallyFree) {
  145.         do {
  146.             *ap = a->next;
  147.             PL_CLEAR_ARENA(a);
  148.             PL_COUNT_ARENA(pool,--);
  149.             PR_DELETE(a);
  150.         } while ((a = *ap) != 0);
  151.     } else {
  152.         /* Insert the whole arena chain at the front of the freelist. */
  153.         do {
  154.             ap = &(*ap)->next;
  155.         } while (*ap);
  156.         *ap = arena_freelist;
  157.         arena_freelist = a;
  158.         head->next = 0;
  159.     }
  160.  
  161.     pool->current = head;
  162. }
  163.  
  164. PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
  165. {
  166.     PLArena *a;
  167.  
  168.     for (a = pool->first.next; a; a = a->next) {
  169.         if (PR_UPTRDIFF(mark, a) < PR_UPTRDIFF(a->avail, a)) {
  170.             a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
  171.             FreeArenaList(pool, a, PR_TRUE);
  172.             return;
  173.         }
  174.     }
  175. }
  176.  
  177. PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
  178. {
  179.     FreeArenaList(pool, &pool->first, PR_FALSE);
  180.     COUNT(pool, ndeallocs);
  181. }
  182.  
  183. PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
  184. {
  185.     FreeArenaList(pool, &pool->first, PR_TRUE);
  186. #ifdef PL_ARENAMETER
  187.     {
  188.         PLArenaStats *stats, **statsp;
  189.  
  190.         if (pool->stats.name)
  191.             PR_DELETE(pool->stats.name);
  192.         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
  193.              statsp = &stats->next) {
  194.             if (stats == &pool->stats) {
  195.                 *statsp = stats->next;
  196.                 return;
  197.             }
  198.         }
  199.     }
  200. #endif
  201. }
  202.  
  203. PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
  204. {
  205. #if XP_MAC
  206. #pragma unused (ap)
  207. #if 0
  208.     PRArena *curr = &(ap->first);
  209.     while (curr) {
  210.         reallocSmaller(curr, curr->avail - (uprword_t)curr);
  211.         curr->limit = curr->avail;
  212.         curr = curr->next;
  213.     }
  214. #endif
  215. #endif
  216. }
  217.  
  218. PR_IMPLEMENT(void) PL_ArenaFinish()
  219. {
  220.     PLArena *a, *next;
  221.  
  222.     for (a = arena_freelist; a; a = next) {
  223.         next = a->next;
  224.         PR_DELETE(a);
  225.     }
  226.     arena_freelist = NULL;
  227. }
  228.  
  229. #ifdef PL_ARENAMETER
  230. PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
  231. {
  232.     pool->stats.nallocs++;
  233.     pool->stats.nbytes += nb;
  234.     if (nb > pool->stats.maxalloc)
  235.         pool->stats.maxalloc = nb;
  236.     pool->stats.variance += nb * nb;
  237. }
  238.  
  239. PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
  240.     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
  241. {
  242.     pool->stats.ninplace++;
  243. }
  244.  
  245. PR_IMPLEMENT(void) PL_ArenaCountGrowth(
  246.     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
  247. {
  248.     pool->stats.ngrows++;
  249.     pool->stats.nbytes += incr;
  250.     pool->stats.variance -= size * size;
  251.     size += incr;
  252.     if (size > pool->stats.maxalloc)
  253.         pool->stats.maxalloc = size;
  254.     pool->stats.variance += size * size;
  255. }
  256.  
  257. PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
  258. {
  259.     pool->stats.nreleases++;
  260. }
  261.  
  262. PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
  263. {
  264.     pool->stats.nfastrels++;
  265. }
  266.  
  267. #include <math.h>
  268. #include <stdio.h>
  269.  
  270. PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
  271. {
  272.     PLArenaStats *stats;
  273.     double mean, variance;
  274.  
  275.     for (stats = arena_stats_list; stats; stats = stats->next) {
  276.         if (stats->nallocs != 0) {
  277.             mean = (double)stats->nbytes / stats->nallocs;
  278.             variance = fabs(stats->variance / stats->nallocs - mean * mean);
  279.         } else {
  280.             mean = variance = 0;
  281.         }
  282.  
  283.         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
  284.         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
  285.         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
  286.         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
  287.         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
  288.         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
  289.         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
  290.         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
  291.         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
  292.         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
  293.         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
  294.         fprintf(fp, "          mean allocation size: %g\n", mean);
  295.         fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
  296.         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
  297.     }
  298. }
  299. #endif /* PL_ARENAMETER */
  300.