Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
Overuse of independent_comalloc can increase overall memory usage,
since it cannot reuse existing noncontiguous small chunks that
might be available for some of the elements.
*/
Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
/*
pvalloc(size_t n);
Equivalent to valloc(minimum-page-that-holds(n)), that is,
round up n to nearest pagesize.
*/
Void_t* public_pVALLOc(size_t);
/*
cfree(Void_t* p);
Equivalent to free(p).
cfree is needed/defined on some systems that pair it with calloc,
for odd historical reasons (such as: cfree is used in example
code in the first edition of K&R).
*/
void public_cFREe(Void_t*);
/*
malloc_trim(size_t pad);
If possible, gives memory back to the system (via negative
arguments to sbrk) if there is unused memory at the `high' end of
the malloc pool. You can call this after freeing large blocks of
memory to potentially reduce the system-level memory requirements
of a program. However, it cannot guarantee to reduce memory. Under
some allocation patterns, some large free blocks of memory will be
locked between two used chunks, so they cannot be given back to
the system.
The `pad' argument to malloc_trim represents the amount of free
trailing space to leave untrimmed. If this argument is zero,
only the minimum amount of memory to maintain internal data
structures will be left (one page or less). Non-zero arguments
can be supplied to maintain enough trailing space to service
future expected allocations without having to re-obtain memory
from the system.
Malloc_trim returns 1 if it actually released any memory, else 0.
On systems that do not support "negative sbrks", it will always
rreturn 0.
*/
int public_mTRIm(size_t);
/*
malloc_usable_size(Void_t* p);
Returns the number of bytes you can actually use in
an allocated chunk, which may be more than you requested (although
often not) due to alignment and minimum size constraints.
You can use this many bytes without worrying about
overwriting other allocated objects. This is not a particularly great
programming practice. malloc_usable_size can be more useful in
debugging and assertions, for example:
p = malloc(n);
assert(malloc_usable_size(p) >= 256);
*/
size_t public_mUSABLe(Void_t*);
/*
malloc_stats();
Prints on stderr the amount of space obtained from the system (both
via sbrk and mmap), the maximum amount (which may be more than
current if malloc_trim and/or munmap got called), and the current
number of bytes allocated via malloc (or realloc, etc) but not yet
freed. Note that this is the number of bytes allocated, not the
number requested. It will be larger than the number requested
because of alignment and bookkeeping overhead. Because it includes
alignment wastage as being in use, this figure may be greater than
zero even when no user-level chunks are allocated.
The reported current and maximum system memory can be inaccurate if
a program makes other calls to system memory allocation functions
(normally sbrk) outside of malloc.
malloc_stats prints only the most commonly interesting statistics.
More information can be obtained by calling mallinfo.
*/
void public_mSTATs();
/* mallopt tuning options */
/*
M_MXFAST is the maximum request size used for "fastbins", special bins
that hold returned chunks without consolidating their spaces. This
enables future requests for chunks of the same size to be handled
very quickly, but can increase fragmentation, and thus increase the
overall memory footprint of a program.
This malloc manages fastbins very conservatively yet still
efficiently, so fragmentation is rarely a problem for values less
than or equal to the default. The maximum supported value of MXFAST
is 64 (also the default). You wouldn't want it any higher than this
anyway. Fastbins are designed especially for use with many small
structs, objects or strings -- the default handles
structs/objects/arrays with sizes up to 16 4byte fields, or small
strings representing words, tokens, etc. Using fastbins for larger
objects normally worsens fragmentation without improving speed.
M_MXFAST is set in REQUEST size units. It is internally used in
chunksize units, which adds padding and alignment. You can reduce
M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
algorithm to be a closer approximation of fifo-best-fit in all cases,
not just for larger requests, but will generally cause it to be
slower.
*/
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST 1
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
if (p == x)
return p;
else if (p == t)
return 0;
else
p = p->bk;
}
}
if (((nb >> shift) & 1) == 0) {
t = t->child[0];
}
else {
t = t->child[1];
allbits |= 1U << shift;
}
--shift;
}
return 0;
}
/*
Properties of all chunks
*/
static void do_check_chunk(mchunkptr p) {
mstate av = get_malloc_state();
CHUNK_SIZE_T sz = chunksize(p);
/* min and max possible addresses assuming contiguous allocation */
char* max_address = (char*)(av->top) + chunksize(av->top);
char* min_address = max_address - av->sbrked_mem;
if (!chunk_is_mmapped(p)) {
/* Has legal address ... */
if (p != av->top) {
if (contiguous(av)) {
assert(((char*)p) >= min_address);
assert(((char*)p + sz) <= ((char*)(av->top)));
}
}
else {
/* top size is always at least MINSIZE */
assert((CHUNK_SIZE_T)(sz) >= MINSIZE);
/* top predecessor always marked inuse */
assert(prev_inuse(p));
}
}
else {
#if HAVE_MMAP
/* address is outside main heap */
if (contiguous(av) && av->top != (mchunkptr)(&(av->initial_top))) {
assert(((char*)p) < min_address || ((char*)p) > max_address);
}
/* chunk is page-aligned */
assert(((p->prev_size + sz) & (av->pagesize-1)) == 0);
/* mem is aligned */
assert(aligned_OK(chunk2mem(p)));
#else
/* force an appropriate assert violation if debug set */
assert(!chunk_is_mmapped(p));
#endif
}
}
static void check_all_less(tchunkptr t, CHUNK_SIZE_T nb) {
if (t == 0)
return;
assert(chunksize(t) < nb);
check_all_less(t->child[0], nb);
check_all_less(t->child[1], nb);
}
static void check_all_greater(tchunkptr t, CHUNK_SIZE_T nb) {
if (t == 0)
return;
assert(chunksize(t) >= nb);
check_all_greater(t->child[0], nb);
check_all_greater(t->child[1], nb);
}
static INTERNAL_SIZE_T check_tree_fields(tchunkptr t) {
INTERNAL_SIZE_T size = chunksize(t);
assert(size >= MIN_TREEBIN_SIZE);
do_check_chunk(((mchunkptr)t));
assert(!inuse(t));
assert(t->fd->bk == t);
assert(t->bk->fd == t);
assert(t->parent != t);
assert(t->child[0] != t);
assert(t->child[1] != t);
if (t->child[0] != 0 && t->child[1] != 0) {
check_all_less(t->child[0], chunksize(t->child[1]));
check_all_greater(t->child[1], chunksize(t->child[0]));
}
return size;
}
static INTERNAL_SIZE_T do_check_tree(tchunkptr t) {
tchunkptr p;
tchunkptr h;
INTERNAL_SIZE_T total = check_tree_fields(t);
/* If t is on a same-sized list, another node on list must have a parent */
if (t->parent == 0) {
h = t->bk;
while (h != t && h->parent == 0)
h = h->bk;
assert(h != t);
}
else
h = t;
assert (h->parent->child[0] == h ||
h->parent->child[1] == h ||
*((tbinptr*)(h->parent)) == h);
/* only one node on a same-sized list has parent or children */
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
assert(p->fd->bk == p);
assert(p->bk->fd == p);
}
else {
do_check_tree((tchunkptr)p);
}
}
/*
Properties of free chunks
*/
static void do_check_free_chunk(mchunkptr p) {
mstate av = get_malloc_state();
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
mchunkptr next = chunk_at_offset(p, sz);
do_check_chunk(p);
/* Chunk must claim to be free ... */
assert(!inuse(p));
assert (!chunk_is_mmapped(p));
/* Unless a special marker, must have OK fields */
if ((CHUNK_SIZE_T)(sz) >= MINSIZE)
{
assert((sz & MALLOC_ALIGN_MASK) == 0);
assert(aligned_OK(chunk2mem(p)));
/* ... matching footer field */
assert(next->prev_size == sz);
/* ... and is fully consolidated */
assert(prev_inuse(p));
assert (next == av->top || inuse(next));
do_check_links(p);
}
else /* markers are always of size SIZE_SZ */
assert(sz == SIZE_SZ);
}
/*
Properties of inuse chunks
*/
static void do_check_inuse_chunk(mchunkptr p) {
mstate av = get_malloc_state();
mchunkptr next;
do_check_chunk(p);
if (chunk_is_mmapped(p))
return; /* mmapped chunks have no next/prev */
/* Check whether it claims to be in use ... */
assert(inuse(p));
next = next_chunk(p);
/* ... and is surrounded by OK chunks.
Since more things can be checked with free chunks than inuse ones,
if an inuse chunk borders them and debug is on, it's worth doing them.
*/
if (!prev_inuse(p)) {
/* Note that we cannot even look at prev unless it is not inuse */
mchunkptr prv = prev_chunk(p);
assert(next_chunk(prv) == p);
do_check_free_chunk(prv);
}
if (next == av->top) {
assert(prev_inuse(next));
assert(chunksize(next) >= MINSIZE);
}
else if (!inuse(next))
do_check_free_chunk(next);
}
static void do_check_remalloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) {
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
do_check_inuse_chunk(p);
/* Legal size ... */
assert((sz & MALLOC_ALIGN_MASK) == 0);
assert((CHUNK_SIZE_T)(sz) >= MINSIZE);
/* ... and alignment */
assert(aligned_OK(chunk2mem(p)));
/* chunk is less than MINSIZE more than request */
assert((long)(sz) - (long)(s) >= 0);
assert((long)(sz) - (long)(s + MINSIZE) < 0);
}
/*
Properties of nonrecycled chunks at the point they are malloced
*/
static void do_check_malloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) {
/* same as recycled case ... */
do_check_remalloced_chunk(p, s);
#if 0
do_check_malloc_state(get_malloc_state());
#endif
/*
... plus, must obey implementation invariant that prev_inuse is
always true of any allocated chunk; i.e., that each allocated
chunk borders either a previously allocated and still in-use
chunk, or the base of its memory arena. This is ensured
by making all allocations from the the `lowest' part of any found
chunk.
*/
assert(prev_inuse(p));
}
static CHUNK_SIZE_T do_check_smallbin(mstate av, int i, mbinptr b) {
mchunkptr p = b->bk;
mchunkptr q;
bin_index_t idx;
INTERNAL_SIZE_T size;
CHUNK_SIZE_T total = 0;
unsigned int empty = (av->smallbits & (1 << i)) == 0;
if (i >= 2) {
if (empty)
assert(p == b);
if (p == b)
assert(empty);
if (p != b)
assert(!empty);
}
for (; p != b; p = p->bk) {
/* each chunk claims to be free */
do_check_free_chunk(p);
size = chunksize(p);
total += size;
if (i >= 2) {
/* chunk belongs in bin */
idx = smallbin_index(size);
assert(idx == i);
assert(p->bk == b ||
(CHUNK_SIZE_T)chunksize(p->bk) ==
(CHUNK_SIZE_T)chunksize(p));
}
/* chunk is followed by a legal chain of inuse chunks */
for (q = next_chunk(p);
(q != av->top && inuse(q) &&
(CHUNK_SIZE_T)(chunksize(q)) >= MINSIZE);
q = next_chunk(q))
do_check_inuse_chunk(q);
}
return total;
}
/*
Properties of malloc_state.
This may be useful for debugging malloc, as well as detecting user
programmer errors that somehow write into malloc_state.
If you are extending or experimenting with this malloc, you can
probably figure out how to hack this routine to print out or
display chunk addresses, sizes, bins, and other instrumentation.
*/
static void do_check_malloc_state(mstate av) {
int i;
mbinptr b;
CHUNK_SIZE_T total = 0;
tchunkptr t;
unsigned int empty;
tbinptr* tb;
int max_fast_bin;
mchunkptr p;
/* internal size_t must be no wider than pointer type */
assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
/* alignment is a power of 2 */
assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
/* cannot run remaining checks until fully initialized */
if (av->top == 0 || av->top == (mchunkptr)(&(av->initial_top)))
return;
/* pagesize is a power of 2 */
assert((av->pagesize & (av->pagesize-1)) == 0);
/* check smallbins */
for (i = 1; i < NBINS; ++i) {
b = bin_at(av, i);
total += do_check_smallbin(av, i, b);
}
/* check treebins */
for (i = 0; i < NBINS; ++i) {
tb = tbin_at(av, i);
t = *tb;
empty = (av->treebits & (1 << i)) == 0;
if (t == 0)
assert(empty);
else if (t != 0) {
assert(!empty);
total += do_check_tree(t);
}
}
/* top chunk is OK */
check_chunk(av->top);
/* top not in tree */
if (!in_smallbin_range(chunksize(av->top)))
assert(tree_find((tchunkptr)(av->top)) == 0);
/* max_fast is in allowed range */
assert(get_max_fast(av) <= request2size(MAX_FAST_SIZE));
max_fast_bin = fastbin_index(av->max_fast);
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
* Introduce independent_comalloc and independent_calloc.
Thanks to Michael Pachos for motivation and help.
* Make optional .h file available
* Allow > 2GB requests on 32bit systems.
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
and Anonymous.
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
helping test this.)
* memalign: check alignment arg
* realloc: don't try to shift chunks backwards, since this
leads to more fragmentation in some programs and doesn't
seem to help in any others.
* Collect all cases in malloc requiring system memory into sysmalloc
* Use mmap as backup to sbrk
* Place all internal state in malloc_state
* Introduce fastbins (although similar to 2.5.1)
* Many minor tunings and cosmetic improvements
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
* Include errno.h to support default failure action.
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
* return null for negative arguments
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
(e.g. WIN32 platforms)
* Cleanup header file inclusion for WIN32 platforms
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
memory allocation routines
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
usage of 'assert' in non-WIN32 code
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
avoid infinite loop
* Always call 'fREe()' rather than 'free()'
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
* Fixed ordering problem with boundary-stamping
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
* Added pvalloc, as recommended by H.J. Liu
* Added 64bit pointer support mainly from Wolfram Gloger
* Added anonymously donated WIN32 sbrk emulation
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
* malloc_extend_top: fix mask error that caused wastage after
foreign sbrks
* Add linux mremap support code from HJ Liu
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
* Integrated most documentation with the code.
* Add support for mmap, with help from
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
* Use last_remainder in more cases.
* Pack bins using idea from colin@nyx10.cs.du.edu
* Use ordered bins instead of best-fit threshhold
* Eliminate block-local decls to simplify tracing and debugging.
* Support another case of realloc via move into top
* Fix error occuring when initial sbrk_base not word-aligned.
* Rely on page size for units instead of SBRK_UNIT to
avoid surprises about sbrk alignment conventions.
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
(raymond@es.ele.tue.nl) for the suggestion.
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
* More precautions for cases where other routines call sbrk,
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
* Added macros etc., allowing use in linux libc from
H.J. Lu (hjl@gnu.ai.mit.edu)
* Inverted this history list
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
* Removed all preallocation code since under current scheme
the work required to undo bad preallocations exceeds
the work saved in good cases for most test programs.
* No longer use return list or unconsolidated bins since
no scheme using them consistently outperforms those that don't
given above changes.
* Use best fit for very large chunks to prevent some worst-cases.
* Added some support for debugging
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
* Removed footers when chunks are in use. Thanks to
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
* Added malloc_trim, with help from Wolfram Gloger
(wmglo@Dent.MED.Uni-Muenchen.DE).
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
* realloc: try to expand in both directions
* malloc: swap order of clean-bin strategy;
* realloc: only conditionally expand backwards
* Try not to scavenge used bins
* Use bin counts as a guide to preallocation
* Occasionally bin return list chunks in first scan
* Add a few optimizations from colin@nyx10.cs.du.edu
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
* faster bin computation & slightly different binning
* merged all consolidations to one part of malloc proper
(eliminating old malloc_find_space & malloc_clean_bin)
* Scan 2 returns chunks (not just 1)
* Propagate failure in realloc if malloc returns 0
* Add stuff to allow compilation on non-ANSI compilers
from kpv@research.att.com
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
* removed potential for odd address access in prev_chunk
* removed dependency on getpagesize.h
* misc cosmetics and a bit more internal documentation
* anticosmetics: mangled names in macros to evade debugger strangeness
* tested on sparc, hp-700, dec-mips, rs6000
with gcc & native cc (hp, dec only) allowing
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
structure of old version, but most details differ.)
*/
( run in 0.389 second using v1.01-cache-2.11-cpan-f6376fbd888 )