Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
/*
"Small" chunks are stored in circular doubly-linked lists, and look
like this:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Larger chunks are kept in a form of bitwise digital trees (aka tries)
keyed on chunksizes, in which
* As seen as trees, they contains no duplicates (i.e., no
duplicate sizes). If a chunk with the same size an an existing
node is inserted, it is linked off the existing node using
pointers that work in the same way as fd/bk pointers
of small chunks
* The decision to go left or right when searching is based on a
sliding bit, starting at the most significant bit distinguishing
sizes in the tree, and sliding right each level. All left
children of a node are smaller than all right children, but not
necessarily smaller than the node.
The worst case number of steps to add or remove a node is thus
bounded by the number of bits differentiating chunks within
bins. Under current bin calculations, this ranges from 6 up to 21
(for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
is of course much better.
Tree chunks are overlaid in the same way as small chunks. Because
malloc_tree_chunks are only for free chunks greater than 256 bytes, their
zie doesn;t impose any constraints on user chunk sizes.
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk of same size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk of same size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to left child (child[0]) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to right child (child[1]) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pointer to parent |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| bin index of this chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*/
struct malloc_tree_chunk {
INTERNAL_SIZE_T prev_size; /* same as in malloc_chunk */
INTERNAL_SIZE_T size;
struct malloc_tree_chunk* fd; /* double links -- used only if free. */
struct malloc_tree_chunk* bk;
struct malloc_tree_chunk* child[2];
struct malloc_tree_chunk* parent;
bin_index_t index;
};
typedef struct malloc_tree_chunk* tchunkptr;
typedef struct malloc_tree_chunk* tbinptr;
/*
-------------------- Internal data structures --------------------
All internal state is held in an instance of malloc_state defined
below. There are no other static variables, except in two optional
cases:
* If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
* If HAVE_MMAP is true, but mmap doesn't support
MAP_ANONYMOUS, a dummy file descriptor for mmap.
Beware of lots of tricks that minimize the total bookkeeping space
requirements. The result is a little under 1K bytes (for 4byte
pointers and size_t.)
*/
/*
SmallBins
An array of bin headers for free chunks. Most bins hold sizes that are
unusual as malloc request sizes, but are more usual for fragments
and consolidated sets of chunks, which is what these bins hold, so
they can be found quickly. All procedures maintain the invariant
that no consolidated chunk physically borders another one, so each
chunk in a list is known to be preceeded and followed by either
inuse chunks or the ends of memory.
To simplify use in double-linked lists, each bin header acts as a
malloc_chunk pointing to the real first node, if it exists (else
juct pointing to itself). This avoids special-casing for headers.
But to conserve space and improve locality, we allocate only the
fd/bk pointers of bins, and then use repositioning tricks to treat
these as the fields of a malloc_chunk*.
*/
typedef struct malloc_chunk* mbinptr;
/* addressing */
#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
/* analog of ++bin */
#define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
/* inverse of bin_at */
#define bin2idx(m, b) \
( ((int) (((char*)(b)) - (char*)(bin_at(m,0)))) / (2 * sizeof(mchunkptr)))
/*
Indexing
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
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 */
p = h->bk;
while (p != h) {
assert(p->child[0] == 0);
assert(p->child[1] == 0);
assert(p->parent == 0);
assert(chunksize(p) == chunksize(h));
total += check_tree_fields(p);
p = p->bk;
}
if (h->child[0] != 0) {
assert(h->child[0]->parent == h);
total += do_check_tree(h->child[0]);
}
if (h->child[1] != 0) {
assert(h->child[1]->parent == h);
total += do_check_tree(h->child[1]);
}
return total;
}
static void do_check_links(mchunkptr p) {
if (in_smallbin_range(chunksize(p))) {
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 */
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
for (i = 0; i < NFASTBINS; ++i) {
p = av->fastbins[i];
/* all bins past max_fast are empty */
if (i > max_fast_bin)
assert(p == 0);
while (p != 0) {
/* each chunk claims to be inuse */
do_check_inuse_chunk(p);
total += chunksize(p);
/* chunk belongs in this bin */
assert(fastbin_index(chunksize(p)) == i);
p = p->fd;
}
}
/* sanity checks for statistics */
assert(total <= (CHUNK_SIZE_T)(av->max_total_mem));
assert(av->n_mmaps >= 0);
assert(av->n_mmaps <= av->n_mmaps_max);
assert(av->n_mmaps <= av->max_n_mmaps);
assert((CHUNK_SIZE_T)(av->sbrked_mem) <=
(CHUNK_SIZE_T)(av->max_sbrked_mem));
assert((CHUNK_SIZE_T)(av->mmapped_mem) <=
(CHUNK_SIZE_T)(av->max_mmapped_mem));
assert((CHUNK_SIZE_T)(av->max_total_mem) >=
(CHUNK_SIZE_T)(av->mmapped_mem) + (CHUNK_SIZE_T)(av->sbrked_mem));
}
#endif
/*
----------- Operations on trees -----------
*/
/*
Insert chunk into corresponding list or tree
*/
static void insert_treenode(mstate av, tchunkptr x,
CHUNK_SIZE_T nb) {
bin_index_t idx = treebin_index(nb);
tbinptr* bin = tbin_at(av, idx);
tchunkptr t = *bin;
x->child[0] = 0;
x->child[1] = 0;
x->index = idx;
if (t == 0) {
av->treebits |= idx2bit(idx);
*bin = x;
x->parent = (tchunkptr)bin;
x->fd = x;
x->bk = x;
}
else {
bin_index_t shift = bitshift_for_index(idx);
tchunkptr b;
check_tree(t);
while (chunksize(t) != nb) {
tchunkptr* pchild = &(t->child[(nb >> shift--) & 1]);
if (*pchild != 0) {
t = *pchild;
}
else {
*pchild = x;
x->parent = t;
x->fd = x;
x->bk = x;
return;
}
}
/* Link in same-sized node */
b = t->bk;
x->parent = 0;
x->fd = t;
x->bk = b;
b->fd = t->bk = x;
}
}
static void transfer_tree_links(tchunkptr oldt, tchunkptr newt) {
tchunkptr p = oldt->parent;
newt->parent = p;
if (p->child[0] == oldt)
p->child[0] = newt;
else if (p->child[1] == oldt)
p->child[1] = newt;
else
*((tbinptr*)p) = newt;
if ( (newt->child[0] = oldt->child[0]) != 0)
newt->child[0]->parent = newt;
if ( (newt->child[1] = oldt->child[1]) != 0)
newt->child[1]->parent = newt;
}
static tchunkptr find_replacement(tchunkptr t) {
/*
Unless t is itself a leaf node, we must replace t with a leaf
node (not merely one with an open left or right, as with binary
search trees), to make sure that lefts and rights of descendents
correspond properly to bit masks. We use the leftmost leaf of
right child, or, if there is no right child, the rightmost leaf
of left child. We could use any other leaf, but these choices
will tend to maintain nicer trees.
*/
tchunkptr* cp;
tchunkptr c;
if ((c = *(cp = &(t->child[1]))) == 0)
if ((c = *(cp = &(t->child[0]->child[1]))) == 0)
c = *(cp = &(t->child[0]));
assert(c != 0);
for (;;) {
if (c->child[0] != 0)
c = *(cp = &(c->child[0]));
else if (c->child[1] != 0)
c = *(cp = &(c->child[1]));
else {
*cp = 0; /* unlink from parent */
return c;
}
}
}
static void unlink_leaf_node(mstate av, tchunkptr t) {
tchunkptr p = t->parent;
if (p->child[0] == t)
p->child[0] = 0;
else if (p->child[1] == t)
p->child[1] = 0;
else {
assert(is_tbin(av, p));
*((tbinptr*)p) = 0;
av->treebits &= ~idx2bit(t->index);
}
}
static void unlink_chained_node(tchunkptr t) {
tchunkptr bck = t->bk;
tchunkptr fwd = t->fd;
fwd->bk = bck;
bck->fd = fwd;
/* t's parent is nonnull if t was head of chain */
if (t->parent != 0)
transfer_tree_links(t, fwd);
check_tree(fwd);
}
/*
----------- other helper functions -----------
We expect these to be inlined
*/
static void insert_small_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb) {
bin_index_t idx = smallbin_index(nb);
mchunkptr bck = bin_at(av, idx);
mchunkptr fwd = bck->fd;
mark_smallbin(av, idx);
p->fd = fwd;
p->bk = bck;
fwd->bk = bck->fd = p;
assert(in_smallbin_range(nb));
}
static void insert_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb) {
if (in_smallbin_range(nb))
insert_small_chunk(av, p, nb);
else
insert_treenode(av, (tchunkptr)p, nb);
}
static mchunkptr take_from_smallbin(mstate av, mchunkptr bin, bitmap_t bit) {
mchunkptr p = bin->bk;
mchunkptr bck = p->bk;
assert(p != bin);
bin->bk = bck;
bck->fd = bin;
if (bck == bin)
av->smallbits &= ~bit;
return p;
}
static void unlink_chunk(mstate av, mchunkptr q, CHUNK_SIZE_T size) {
mchunkptr fwd = q->fd;
mchunkptr bck = q->bk;
fwd->bk = bck;
bck->fd = fwd;
if (fwd == bck && in_smallbin_range(size)) {
clear_smallbin(av, smallbin_index(size));
}
else if (!in_smallbin_range(size)) {
tchunkptr t = (tchunkptr)q;
tchunkptr c = (tchunkptr)fwd;
if (c == t) {
if (t->child[0] == t->child[1]) {
unlink_leaf_node(av, t);
return;
}
else {
c = find_replacement(t);
}
}
else {
if (t->parent == 0) {
return;
}
}
transfer_tree_links(t, c);
check_tree(c);
}
}
static Void_t* use_treechunk(mstate av,
CHUNK_SIZE_T nb,
tchunkptr bestchunk,
CHUNK_SIZE_T bestsize,
tchunkptr leaf) {
CHUNK_SIZE_T rsize;
if (bestchunk->bk != bestchunk)
unlink_chained_node(bestchunk);
else {
unlink_leaf_node(av, leaf);
if (leaf != bestchunk)
transfer_tree_links(bestchunk, leaf);
}
rsize = bestsize - nb;
if (rsize >= MINSIZE) {
mchunkptr rem = chunk_at_offset(bestchunk, nb);
set_head(bestchunk, nb | PREV_INUSE);
set_head(rem, rsize | PREV_INUSE);
set_foot(rem, rsize);
insert_chunk(av, rem, rsize);
}
else {
set_inuse_bit_at_offset(bestchunk, bestsize);
}
check_malloced_chunk((mchunkptr)(bestchunk), nb);
return chunk2mem(bestchunk);
}
/*
------------------------------ malloc ------------------------------
*/
Void_t* mALLOc(size_t bytes) {
mstate av = get_malloc_state();
CHUNK_SIZE_T nb;
checked_request2size(bytes, nb);
if (nb <= (CHUNK_SIZE_T)(av->max_fast)) {
mfastbinptr* fb = &(av->fastbins[(fastbin_index(nb))]);
mchunkptr fp = *fb;
if (fp != 0) {
*fb = fp->fd;
check_remalloced_chunk(fp, nb);
return chunk2mem(fp);
}
}
src/judy-1.0.5/test/malloc-pre2.8a.c view on Meta::CPAN
for (;;) {
if (in_smallbin_range(nb)) {
bin_index_t sidx = smallbin_index(nb);
bitmap_t sbit = idx2bit(sidx);
if (sbit <= av->smallbits) {
mchunkptr p;
if ((sbit & av->smallbits) != 0) {
p = take_from_smallbin(av, bin_at(av,sidx), sbit);
set_inuse_bit_at_offset(p, nb);
}
else {
bitmap_t nbit = least_bit(left_bits(sbit) & av->smallbits);
bin_index_t nidx = bit2idx(nbit);
CHUNK_SIZE_T psize = size_for_smallindex(nidx);
CHUNK_SIZE_T qsize = psize - nb;
p = take_from_smallbin(av, bin_at(av, nidx), nbit);
if (qsize < MINSIZE) {
set_inuse_bit_at_offset(p, psize);
}
else {
mchunkptr q = chunk_at_offset(p, nb);
set_head(p, nb | PREV_INUSE);
set_head(q, qsize | PREV_INUSE);
set_foot(q, qsize);
insert_small_chunk(av, q, qsize);
}
}
check_malloced_chunk(p, nb);
return chunk2mem(p);
}
if (av->treebits != 0) {
bitmap_t vbit = least_bit(av->treebits);
bin_index_t vidx = bit2idx(vbit);
tbinptr* vbin = tbin_at(av, vidx);
tchunkptr bestchunk = *vbin;
tchunkptr c = leftmost_child(bestchunk);
CHUNK_SIZE_T bestsize = chunksize(bestchunk);
tchunkptr leaf;
CHUNK_SIZE_T rsize;
/* Fast path if remainder will replace bestchunk */
if (c == 0) {
rsize = bestsize - nb;
leaf = bestchunk;
if (rsize >= minsize_for_treeindex(vidx) &&
bestchunk->bk == bestchunk) {
tchunkptr r = (tchunkptr)(chunk_at_offset(bestchunk, nb));
set_head(bestchunk, nb | PREV_INUSE);
set_head(r, rsize | PREV_INUSE);
set_foot(r, rsize);
*vbin = r;
r->fd = r;
r->bk = r;
r->child[0] = 0;
r->child[1] = 0;
r->parent = (tchunkptr)vbin;
r->index = vidx;
check_malloced_chunk((mchunkptr)bestchunk, nb);
return chunk2mem(bestchunk);
}
}
else {
do {
CHUNK_SIZE_T csize = chunksize(c);
if (csize < bestsize) {
bestchunk = c;
bestsize = csize;
}
leaf = c;
c = leftmost_child(c);
} while (c != 0);
}
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
}
}
else {
bin_index_t tidx = treebin_index(nb);
bitmap_t tbit = idx2bit(tidx);
if (tbit <= av->treebits) {
tchunkptr bestchunk = 0;
CHUNK_SIZE_T bestsize = MAX_CHUNK_SIZE;
tchunkptr leaf;
bitmap_t vbit;
for (;;) {
if ((tbit & av->treebits) != 0) {
tchunkptr t = *tbin_at(av, tidx);
bin_index_t shift = bitshift_for_index(tidx);
for (;;) {
int dir;
CHUNK_SIZE_T tsize = chunksize(t);
leaf = t;
if (tsize >= nb && tsize < bestsize) {
bestchunk = t;
bestsize = tsize;
if (tsize == nb && t->bk != t)
break;
}
dir = (shift == 0)? 0 : (nb >> shift--) & 1;
t = leaf->child[dir];
if (t == 0) {
shift = 0; /* if forced right, go leftmost from now on */
t = leaf->child[1-dir];
if (t == 0)
break;
}
}
if (bestchunk != 0)
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
}
if (have_fastchunks(av))
malloc_consolidate(av);
else
break;
( run in 0.363 second using v1.01-cache-2.11-cpan-2398b32b56e )