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