[apple/security.git] / OSX / libsecurity_asn1 / lib / plarena.h

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* 
 * The contents of this file are subject to the Mozilla Public
 * License Version 1.1 (the "License"); you may not use this file
 * except in compliance with the License. You may obtain a copy of
 * the License at http://www.mozilla.org/MPL/
 * 
 * Software distributed under the License is distributed on an "AS
 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * rights and limitations under the License.
 * 
 * The Original Code is the Netscape Portable Runtime (NSPR).
 * 
 * The Initial Developer of the Original Code is Netscape
 * Communications Corporation.  Portions created by Netscape are 
 * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
 * Rights Reserved.
 * 
 * Contributor(s):
 * 
 * Alternatively, the contents of this file may be used under the
 * terms of the GNU General Public License Version 2 or later (the
 * "GPL"), in which case the provisions of the GPL are applicable 
 * instead of those above.  If you wish to allow use of your 
 * version of this file only under the terms of the GPL and not to
 * allow others to use your version of this file under the MPL,
 * indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by
 * the GPL.  If you do not delete the provisions above, a recipient
 * may use your version of this file under either the MPL or the
 * GPL.
 */

#ifndef plarena_h___
#define plarena_h___
/*
 * Lifetime-based fast allocation, inspired by much prior art, including
 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
 *
 * Also supports LIFO allocation (PL_ARENA_MARK/PL_ARENA_RELEASE).
 */
#include "prtypes.h"
#include "plarenas.h"

PR_BEGIN_EXTERN_C

typedef struct PLArena          PLArena;

struct PLArena {
    PLArena     *next;          /* next arena for this lifetime */
    PRUword     base;           /* aligned base address, follows this header */
    PRUword     limit;          /* one beyond last byte in arena */
    PRUword     avail;          /* points to next available byte */
};

#ifdef PL_ARENAMETER
typedef struct PLArenaStats PLArenaStats;

struct PLArenaStats {
    PLArenaStats  *next;        /* next in arenaStats list */
    char          *name;        /* name for debugging */
    PRUint32      narenas;      /* number of arenas in pool */
    PRUint32      nallocs;      /* number of PL_ARENA_ALLOCATE() calls */
    PRUint32      nreclaims;    /* number of reclaims from freeArenas */
    PRUint32      nmallocs;     /* number of malloc() calls */
    PRUint32      ndeallocs;    /* number of lifetime deallocations */
    PRUint32      ngrows;       /* number of PL_ARENA_GROW() calls */
    PRUint32      ninplace;     /* number of in-place growths */
    PRUint32      nreleases;    /* number of PL_ARENA_RELEASE() calls */
    PRUint32      nfastrels;    /* number of "fast path" releases */
    PRUint32      nbytes;       /* total bytes allocated */
    PRUint32      maxalloc;     /* maximum allocation size in bytes */
    PRFloat64     variance;     /* size variance accumulator */
};
#endif

struct PLArenaPool {
    PLArena     first;          /* first arena in pool list */
    PLArena     *current;       /* arena from which to allocate space */
    PRUint32    arenasize;      /* net exact size of a new arena */
    PRUword     mask;           /* alignment mask (power-of-2 - 1) */
#ifdef PL_ARENAMETER
    PLArenaStats stats;
#endif
};

/*
 * If the including .c file uses only one power-of-2 alignment, it may define
 * PL_ARENA_CONST_ALIGN_MASK to the alignment mask and save a few instructions
 * per ALLOCATE and GROW.
 */
#ifdef PL_ARENA_CONST_ALIGN_MASK
#define PL_ARENA_ALIGN(pool, n) (((PRUword)(n) + PL_ARENA_CONST_ALIGN_MASK) \
                                & ~PL_ARENA_CONST_ALIGN_MASK)

#define PL_INIT_ARENA_POOL(pool, name, size) \
        PL_InitArenaPool(pool, name, size, PL_ARENA_CONST_ALIGN_MASK + 1)
#else
#define PL_ARENA_ALIGN(pool, n) (typeof(n))(((PRUword)(n) + (pool)->mask) & ~(pool)->mask)
#endif

#define PL_ARENA_ALLOCATE(p, pool, nb) \
    PR_BEGIN_MACRO \
        PLArena *_a = (pool)->current; \
        typeof((nb)) _nb = PL_ARENA_ALIGN(pool, nb); /* __APPLE__ more to be generic */ \
        PRUword _p = _a->avail; \
        if (_nb < nb) {\
            _p = 0; \
        } else if (_nb > (_a->limit - _a->avail)) { \
            _p = (PRUword)PL_ArenaAllocate(pool, _nb); \
        } else { \
            _a->avail += _nb; \
        } \
        p = (void *)_p; \
        if(p) { \
        PL_ArenaCountAllocation(pool, nb); \
        } \
    PR_END_MACRO

#define PL_ARENA_GROW(p, pool, size, incr) \
    PR_BEGIN_MACRO \
        PLArena *_a = (pool)->current; \
        PRUword _q = (PRUword)p + size + incr;  /*__APPLE__ */ \
        if ((p < p + size) && (_q > (PRUword)p) &&  (_q > (PRUword)p + size) && /*__APPLE__ avoid overflow in _q*/ \
            _a->avail == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
            _q <= PL_ARENA_ALIGN(pool,_q) && /*__APPLE__ avoid overflow from alignment*/ \
            _a->limit >= PL_ARENA_ALIGN(pool,_q)) { /* __APPLE__ expanded buffer within arena*/ \
            _a->avail = PL_ARENA_ALIGN(pool, _q); /*__APPLE__ expand buffer*/ \
            PL_ArenaCountInplaceGrowth(pool, size, incr); \
        } else { \
            p = PL_ArenaGrow(pool, p, size, incr); \
        } \
        PL_ArenaCountGrowth(pool, size, incr); \
    PR_END_MACRO

#define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail)
#define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q))

#define PL_CLEAR_UNUSED_PATTERN(a, pattern) \
    PR_BEGIN_MACRO \
        PR_ASSERT((a)->avail <= (a)->limit); \
        memset((void*)(a)->avail, (pattern), (a)->limit - (a)->avail); \
    PR_END_MACRO
#ifdef DEBUG
#define PL_FREE_PATTERN 0xDA
#define PL_CLEAR_UNUSED(a) PL_CLEAR_UNUSED_PATTERN((a), PL_FREE_PATTERN)
#define PL_CLEAR_ARENA(a) \
    PR_BEGIN_MACRO \
        memset((void*)(a), PL_FREE_PATTERN, (a)->limit - (PRUword)(a)); \
    PR_END_MACRO
#else
#define PL_CLEAR_UNUSED(a)
#define PL_CLEAR_ARENA(a)
#endif

#if ARENA_MARK_ENABLE

#define PL_ARENA_RELEASE(pool, mark) \
    PR_BEGIN_MACRO \
        char *_m = (char *)(mark); \
        PLArena *_a = (pool)->current; \
        if (PR_UPTRDIFF(_m, _a->base) <= PR_UPTRDIFF(_a->avail, _a->base)) { \
            _a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \
            PL_CLEAR_UNUSED(_a); \
            PL_ArenaCountRetract(pool, _m); \
        } else { \
            PL_ArenaRelease(pool, _m); \
        } \
        PL_ArenaCountRelease(pool, _m); \
    PR_END_MACRO

#else	/* !ARENA_MARK_ENABLE */

#define PL_ARENA_RELEASE(pool, mark)

#endif	/* ARENA_MARK_ENABLE */

#ifdef PL_ARENAMETER
#define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
#else
#define PL_COUNT_ARENA(pool,op)
#endif

#define PL_ARENA_DESTROY(pool, a, pnext) \
    PR_BEGIN_MACRO \
        PL_COUNT_ARENA(pool,--); \
        if ((pool)->current == (a)) (pool)->current = &(pool)->first; \
        *(pnext) = (a)->next; \
        PL_CLEAR_ARENA(a); \
        free(a); \
        (a) = 0; \
    PR_END_MACRO

#ifdef PL_ARENAMETER

#include <stdio.h>

PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb);

PR_EXTERN(void) PL_ArenaCountInplaceGrowth(
    PLArenaPool *pool, PRUint32 size, PRUint32 incr);

PR_EXTERN(void) PL_ArenaCountGrowth(
    PLArenaPool *pool, PRUint32 size, PRUint32 incr);

PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark);

PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark);

PR_EXTERN(void) PL_DumpArenaStats(FILE *fp);

#else  /* !PL_ARENAMETER */

#define PL_ArenaCountAllocation(ap, nb)                 /* nothing */
#define PL_ArenaCountInplaceGrowth(ap, size, incr)      /* nothing */
#define PL_ArenaCountGrowth(ap, size, incr)             /* nothing */
#define PL_ArenaCountRelease(ap, mark)                  /* nothing */
#define PL_ArenaCountRetract(ap, mark)                  /* nothing */

#endif /* !PL_ARENAMETER */

PR_END_EXTERN_C

#endif /* plarena_h___ */
Commit	Line	Data
b1ab9ed8 A	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
	47	PR_BEGIN_EXTERN_C
	48
	49	typedef struct PLArena PLArena;
	50
	51	struct 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
	59	typedef struct PLArenaStats PLArenaStats;
	60
	61	struct 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
79	struct PLArenaPool {
80	PLArena first; /* first arena in pool list */
81	PLArena current; / arena from which to allocate space */
60c433a9	82	PRUint32 arenasize; /* net exact size of a new arena */
b1ab9ed8 A	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; \
60c433a9	107	typeof((nb)) _nb = PL_ARENA_ALIGN(pool, nb); /* __APPLE__ more to be generic */ \
b1ab9ed8	108	PRUword _p = _a->avail; \
e0e0d90e A	109	if (_nb < nb) {\
	110	_p = 0; \
	111	} else if (_nb > (_a->limit - _a->avail)) { \
b1ab9ed8	112	_p = (PRUword)PL_ArenaAllocate(pool, _nb); \
60c433a9	113	} else { \
e0e0d90e	114	_a->avail += _nb; \
60c433a9	115	} \
b1ab9ed8	116	p = (void *)_p; \
e0e0d90e	117	if(p) { \
b1ab9ed8	118	PL_ArenaCountAllocation(pool, nb); \
e0e0d90e	119	} \
b1ab9ed8 A	120	PR_END_MACRO
	121
	122	#define PL_ARENA_GROW(p, pool, size, incr) \
	123	PR_BEGIN_MACRO \
	124	PLArena *_a = (pool)->current; \
5dd5f9ec	125	PRUword _q = (PRUword)p + size + incr; /__APPLE__ / \
fa7225c8	126	if ((p < p + size) && (_q > (PRUword)p) && (_q > (PRUword)p + size) && /__APPLE__ avoid overflow in _q/ \
e0e0d90e A	127	_a->avail == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
	128	_q <= PL_ARENA_ALIGN(pool,_q) && /__APPLE__ avoid overflow from alignment/ \
	129	_a->limit >= PL_ARENA_ALIGN(pool,_q)) { /* __APPLE__ expanded buffer within arena*/ \
	130	_a->avail = PL_ARENA_ALIGN(pool, _q); /__APPLE__ expand buffer/ \
b1ab9ed8 A	131	PL_ArenaCountInplaceGrowth(pool, size, incr); \
	132	} else { \
	133	p = PL_ArenaGrow(pool, p, size, incr); \
	134	} \
	135	PL_ArenaCountGrowth(pool, size, incr); \
	136	PR_END_MACRO
	137
	138	#define PL_ARENA_MARK(pool) ((void *) (pool)->current->avail)
	139	#define PR_UPTRDIFF(p,q) ((PRUword)(p) - (PRUword)(q))
	140
60c433a9 A	141	#define PL_CLEAR_UNUSED_PATTERN(a, pattern) \
	142	PR_BEGIN_MACRO \
	143	PR_ASSERT((a)->avail <= (a)->limit); \
	144	memset((void*)(a)->avail, (pattern), (a)->limit - (a)->avail); \
	145	PR_END_MACRO
b1ab9ed8 A	146	#ifdef DEBUG
b1ab9ed8 A	147	#define PL_FREE_PATTERN 0xDA
60c433a9 A	148	#define PL_CLEAR_UNUSED(a) PL_CLEAR_UNUSED_PATTERN((a), PL_FREE_PATTERN)
	149	#define PL_CLEAR_ARENA(a) \
	150	PR_BEGIN_MACRO \
	151	memset((void*)(a), PL_FREE_PATTERN, (a)->limit - (PRUword)(a)); \
	152	PR_END_MACRO
b1ab9ed8 A	153	#else
	154	#define PL_CLEAR_UNUSED(a)
	155	#define PL_CLEAR_ARENA(a)
	156	#endif
	157
	158	#if ARENA_MARK_ENABLE
	159
	160	#define PL_ARENA_RELEASE(pool, mark) \
	161	PR_BEGIN_MACRO \
	162	char _m = (char )(mark); \
	163	PLArena *_a = (pool)->current; \
	164	if (PR_UPTRDIFF(_m, _a->base) <= PR_UPTRDIFF(_a->avail, _a->base)) { \
	165	_a->avail = (PRUword)PL_ARENA_ALIGN(pool, _m); \
	166	PL_CLEAR_UNUSED(_a); \
	167	PL_ArenaCountRetract(pool, _m); \
	168	} else { \
	169	PL_ArenaRelease(pool, _m); \
	170	} \
	171	PL_ArenaCountRelease(pool, _m); \
	172	PR_END_MACRO
	173
	174	#else /* !ARENA_MARK_ENABLE */
	175
	176	#define PL_ARENA_RELEASE(pool, mark)
	177
	178	#endif /* ARENA_MARK_ENABLE */
	179
	180	#ifdef PL_ARENAMETER
	181	#define PL_COUNT_ARENA(pool,op) ((pool)->stats.narenas op)
	182	#else
	183	#define PL_COUNT_ARENA(pool,op)
	184	#endif
	185
	186	#define PL_ARENA_DESTROY(pool, a, pnext) \
	187	PR_BEGIN_MACRO \
	188	PL_COUNT_ARENA(pool,--); \
	189	if ((pool)->current == (a)) (pool)->current = &(pool)->first; \
	190	*(pnext) = (a)->next; \
	191	PL_CLEAR_ARENA(a); \
	192	free(a); \
	193	(a) = 0; \
	194	PR_END_MACRO
	195
	196	#ifdef PL_ARENAMETER
	197
	198	#include <stdio.h>
	199
	200	PR_EXTERN(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb);
	201
	202	PR_EXTERN(void) PL_ArenaCountInplaceGrowth(
	203	PLArenaPool *pool, PRUint32 size, PRUint32 incr);
	204
	205	PR_EXTERN(void) PL_ArenaCountGrowth(
	206	PLArenaPool *pool, PRUint32 size, PRUint32 incr);
	207
	208	PR_EXTERN(void) PL_ArenaCountRelease(PLArenaPool pool, char mark);
	209
	210	PR_EXTERN(void) PL_ArenaCountRetract(PLArenaPool pool, char mark);
	211
	212	PR_EXTERN(void) PL_DumpArenaStats(FILE *fp);
	213
	214	#else /* !PL_ARENAMETER */
	215
	216	#define PL_ArenaCountAllocation(ap, nb) /* nothing */
217	#define PL_ArenaCountInplaceGrowth(ap, size, incr) /* nothing */
218	#define PL_ArenaCountGrowth(ap, size, incr) /* nothing */
219	#define PL_ArenaCountRelease(ap, mark) /* nothing */
220	#define PL_ArenaCountRetract(ap, mark) /* nothing */
221
222	#endif /* !PL_ARENAMETER */
223
224	PR_END_EXTERN_C
225
226	#endif /* plarena_h___ */