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 Mozilla Public
4 * License Version 1.1 (the "License"); you may not use this file
5 * except in compliance with the License. You may obtain a copy of
6 * the License at http://www.mozilla.org/MPL/
7 *
8 * Software distributed under the License is distributed on an "AS
9 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
10 * implied. See the License for the specific language governing
11 * rights and limitations under the License.
12 *
13 * The Original Code is the Netscape Portable Runtime (NSPR).
14 *
15 * The Initial Developer of the Original Code is Netscape
16 * Communications Corporation.  Portions created by Netscape are
17 * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
18 * Rights Reserved.
19 *
20 * Contributor(s):
21 *
22 * Alternatively, the contents of this file may be used under the
23 * terms of the GNU General Public License Version 2 or later (the
24 * "GPL"), in which case the provisions of the GPL are applicable
25 * instead of those above.  If you wish to allow use of your
26 * version of this file only under the terms of the GPL and not to
27 * allow others to use your version of this file under the MPL,
28 * indicate your decision by deleting the provisions above and
29 * replace them with the notice and other provisions required by
30 * the GPL.  If you do not delete the provisions above, a recipient
31 * may use your version of this file under either the MPL or the
32 * GPL.
33 */
34
35#ifndef plarena_h___
36#define plarena_h___
37/*
38 * Lifetime-based fast allocation, inspired by much prior art, including
39 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
40 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
41 *
42 * Also supports LIFO allocation (PL_ARENA_MARK/PL_ARENA_RELEASE).
43 */
44#include "prtypes.h"
45#include "plarenas.h"
46
47PR_BEGIN_EXTERN_C
48
49typedef struct PLArena          PLArena;
50
51struct PLArena {
52    PLArena     *next;          /* next arena for this lifetime */
53    PRUword     base;           /* aligned base address, follows this header */
54    PRUword     limit;          /* one beyond last byte in arena */
55    PRUword     avail;          /* points to next available byte */
56};
57
58#ifdef PL_ARENAMETER
59typedef struct PLArenaStats PLArenaStats;
60
61struct PLArenaStats {
62    PLArenaStats  *next;        /* next in arenaStats list */
63    char          *name;        /* name for debugging */
64    PRUint32      narenas;      /* number of arenas in pool */
65    PRUint32      nallocs;      /* number of PL_ARENA_ALLOCATE() calls */
66    PRUint32      nreclaims;    /* number of reclaims from freeArenas */
67    PRUint32      nmallocs;     /* number of malloc() calls */
68    PRUint32      ndeallocs;    /* number of lifetime deallocations */
69    PRUint32      ngrows;       /* number of PL_ARENA_GROW() calls */
70    PRUint32      ninplace;     /* number of in-place growths */
71    PRUint32      nreleases;    /* number of PL_ARENA_RELEASE() calls */
72    PRUint32      nfastrels;    /* number of "fast path" releases */
73    PRUint32      nbytes;       /* total bytes allocated */
74    PRUint32      maxalloc;     /* maximum allocation size in bytes */
75    PRFloat64     variance;     /* size variance accumulator */
76};
77#endif
78
79struct PLArenaPool {
80    PLArena     first;          /* first arena in pool list */
81    PLArena     *current;       /* arena from which to allocate space */
82    PRSize      arenasize;      /* net exact size of a new arena */
83    PRUword     mask;           /* alignment mask (power-of-2 - 1) */
84#ifdef PL_ARENAMETER
85    PLArenaStats stats;
86#endif
87};
88
89/*
90 * If the including .c file uses only one power-of-2 alignment, it may define
91 * PL_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
92 * per ALLOCATE and GROW.
93 */
94#ifdef PL_ARENA_CONST_ALIGN_MASK
95#define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + PL_ARENA_CONST_ALIGN_MASK) \
96                                & ~PL_ARENA_CONST_ALIGN_MASK)
97
98#define PL_INIT_ARENA_POOL(pool, name, size) \
99        PL_InitArenaPool(pool, name, size, PL_ARENA_CONST_ALIGN_MASK + 1)
100#else
101#define PL_ARENA_ALIGN(pool, n) (typeof(n))(((PRUword)(n) + (pool)->mask) & ~(pool)->mask)
102#endif
103
104#define PL_ARENA_ALLOCATE(p, pool, nb) \
105    PR_BEGIN_MACRO \
106        PLArena *_a = (pool)->current; \
107        PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \
108        PRUword _p = _a->avail; \
109        PRUword _q = _p + _nb; \
110        if (_q > _a->limit) \
111            _p = (PRUword)PL_ArenaAllocate(pool, _nb); \
112        else \
113            _a->avail = _q; \
114        p = (void *)_p; \
115        PL_ArenaCountAllocation(pool, nb); \
116    PR_END_MACRO
117
118#define PL_ARENA_GROW(p, pool, size, incr) \
119    PR_BEGIN_MACRO \
120        PLArena *_a = (pool)->current; \
121        PRUword _p = _a->avail; \
122        PRUword _q = (PRUword)p + size + incr; \
123        if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
124            _q <= _a->limit) { \
125            _a->avail = PL_ARENA_ALIGN(pool, _q); \
126            PL_ArenaCountInplaceGrowth(pool, size, incr); \
127        } else { \
128            p = PL_ArenaGrow(pool, p, size, incr); \
129        } \
130        PL_ArenaCountGrowth(pool, size, incr); \
131    PR_END_MACRO
132
133#define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail)
134#define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q))
135
136#ifdef DEBUG
137#define PL_FREE_PATTERN 0xDA
138#define PL_CLEAR_UNUSED(a) (PR_ASSERT((a)->avail <= (a)->limit), \
139                           memset((void*)(a)->avail, PL_FREE_PATTERN, \
140                           (a)->limit - (a)->avail))
141#define PL_CLEAR_ARENA(a)  memset((void*)(a), PL_FREE_PATTERN, \
142                           (a)->limit - (PRUword)(a))
143#else
144#define PL_CLEAR_UNUSED(a)
145#define PL_CLEAR_ARENA(a)
146#endif
147
148#if ARENA_MARK_ENABLE
149
150#define PL_ARENA_RELEASE(pool, mark) \
151    PR_BEGIN_MACRO \
152        char *_m = (char *)(mark); \
153        PLArena *_a = (pool)->current; \
154        if (PR_UPTRDIFF(_m, _a->base) <= PR_UPTRDIFF(_a->avail, _a->base)) { \
155            _a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \
156            PL_CLEAR_UNUSED(_a); \
157            PL_ArenaCountRetract(pool, _m); \
158        } else { \
159            PL_ArenaRelease(pool, _m); \
160        } \
161        PL_ArenaCountRelease(pool, _m); \
162    PR_END_MACRO
163
164#else	/* !ARENA_MARK_ENABLE */
165
166#define PL_ARENA_RELEASE(pool, mark)
167
168#endif	/* ARENA_MARK_ENABLE */
169
170#ifdef PL_ARENAMETER
171#define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
172#else
173#define PL_COUNT_ARENA(pool,op)
174#endif
175
176#define PL_ARENA_DESTROY(pool, a, pnext) \
177    PR_BEGIN_MACRO \
178        PL_COUNT_ARENA(pool,--); \
179        if ((pool)->current == (a)) (pool)->current = &(pool)->first; \
180        *(pnext) = (a)->next; \
181        PL_CLEAR_ARENA(a); \
182        free(a); \
183        (a) = 0; \
184    PR_END_MACRO
185
186#ifdef PL_ARENAMETER
187
188#include <stdio.h>
189
190PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb);
191
192PR_EXTERN(void) PL_ArenaCountInplaceGrowth(
193    PLArenaPool *pool, PRUint32 size, PRUint32 incr);
194
195PR_EXTERN(void) PL_ArenaCountGrowth(
196    PLArenaPool *pool, PRUint32 size, PRUint32 incr);
197
198PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark);
199
200PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark);
201
202PR_EXTERN(void) PL_DumpArenaStats(FILE *fp);
203
204#else  /* !PL_ARENAMETER */
205
206#define PL_ArenaCountAllocation(ap, nb)                 /* nothing */
207#define PL_ArenaCountInplaceGrowth(ap, size, incr)      /* nothing */
208#define PL_ArenaCountGrowth(ap, size, incr)             /* nothing */
209#define PL_ArenaCountRelease(ap, mark)                  /* nothing */
210#define PL_ArenaCountRetract(ap, mark)                  /* nothing */
211
212#endif /* !PL_ARENAMETER */
213
214PR_END_EXTERN_C
215
216#endif /* plarena_h___ */
217