/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 1985-2012 AT&T Intellectual Property *
* and is licensed under the *
* Eclipse Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.eclipse.org/org/documents/epl-v10.html *
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
* *
* Information and Software Systems Research *
* AT&T Research *
* Florham Park NJ *
* *
* Glenn Fowler <gsf@research.att.com> *
* David Korn <dgk@research.att.com> *
* Phong Vo <kpv@research.att.com> *
* *
***********************************************************************/
#if defined(_UWIN) && defined(_BLD_ast)
void _STUB_vmbest(){}
#else
#include "vmhdr.h"
/* Best-fit allocation method. This is based on a best-fit strategy
** using a splay tree for storage of lists of free blocks of the same
** size. Recent free blocks may be cached for fast reuse.
**
** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
*/
#ifdef DEBUG
static int N_free; /* # of free calls */
static int N_alloc; /* # of alloc calls */
static int N_resize; /* # of resize calls */
static int N_wild; /* # allocated from the wild block */
static int N_last; /* # allocated from last free block */
static int N_reclaim; /* # of bestreclaim calls */
#endif /*DEBUG*/
#define COMPACT 8 /* factor to decide when to compact */
/* Check to see if a block is in the free tree */
#if __STD_C
static int vmintree(Block_t* node, Block_t* b)
#else
static int vmintree(node,b)
Block_t* node;
Block_t* b;
#endif
{ Block_t* t;
for(t = node; t; t = LINK(t))
if(t == b)
return 1;
if(LEFT(node) && vmintree(LEFT(node),b))
return 1;
if(RIGHT(node) && vmintree(RIGHT(node),b))
return 1;
return 0;
}
#if __STD_C
static int vmonlist(Block_t* list, Block_t* b)
#else
static int vmonlist(list,b)
Block_t* list;
Block_t* b;
#endif
{
for(; list; list = LINK(list))
if(list == b)
return 1;
return 0;
}
/* Check to see if a block is known to be free */
#if __STD_C
static int vmisfree(Vmdata_t* vd, Block_t* b)
#else
static int vmisfree(vd,b)
Vmdata_t* vd;
Block_t* b;
#endif
{
if(SIZE(b) & (BUSY|JUNK|PFREE))
return 0;
if(b == vd->wild)
return 1;
if(SIZE(b) < MAXTINY)
return vmonlist(TINY(vd)[INDEX(SIZE(b))], b);
if(vd->root)
return vmintree(vd->root, b);
return 0;
}
/* Check to see if a block is known to be junked */
#if __STD_C
static int vmisjunk(Vmdata_t* vd, Block_t* b)
#else
static int vmisjunk(vd,b)
Vmdata_t* vd;
Block_t* b;
#endif
{
Block_t* t;
if((SIZE(b)&BUSY) == 0 || (SIZE(b)&JUNK) == 0)
return 0;
if(b == vd->free) /* recently freed */
return 1;
/* check the list that b is supposed to be in */
for(t = CACHE(vd)[C_INDEX(SIZE(b))]; t; t = LINK(t))
if(t == b)
return 1;
/* on occasions, b may be put onto the catch-all list */
if(C_INDEX(SIZE(b)) < S_CACHE)
for(t = CACHE(vd)[S_CACHE]; t; t = LINK(t))
if(t == b)
return 1;
return 0;
}
/* check to see if the free tree is in good shape */
#if __STD_C
static int vmchktree(Block_t* node)
#else
static int vmchktree(node)
Block_t* node;
#endif
{ Block_t* t;
if(SIZE(node) & BITS)
{ /**/ASSERT(0); return -1; }
for(t = LINK(node); t; t = LINK(t))
if(SIZE(t) != SIZE(node))
{ /**/ASSERT(0); return -1; }
if((t = LEFT(node)) )
{ if(SIZE(t) >= SIZE(node) )
{ /**/ASSERT(0); return -1; }
else return vmchktree(t);
}
if((t = RIGHT(node)) )
{ if(SIZE(t) <= SIZE(node) )
{ /**/ASSERT(0); return -1; }
else return vmchktree(t);
}
return 0;
}
#if __STD_C
int _vmbestcheck(Vmdata_t* vd, Block_t* freeb)
#else
int _vmbestcheck(vd, freeb)
Vmdata_t* vd;
Block_t* freeb; /* known to be free but not on any free list */
#endif
{
reg Seg_t *seg;
reg Block_t *b, *endb, *nextb;
int rv = 0;
if(!CHECK())
return 0;
/* make sure the free tree is still in shape */
if(vd->root && vmchktree(vd->root) < 0 )
{ rv = -1; /**/ASSERT(0); }
for(seg = vd->seg; seg && rv == 0; seg = seg->next)
{ b = SEGBLOCK(seg);
endb = (Block_t*)(seg->baddr - sizeof(Head_t));
for(; b < endb && rv == 0; b = nextb)
{ nextb = (Block_t*)((Vmuchar_t*)DATA(b) + (SIZE(b)&~BITS) );
if(!ISBUSY(SIZE(b)) ) /* a completely free block */
{ /* there should be no marked bits of any type */
if(SIZE(b) & (BUSY|JUNK|PFREE) )
{ rv = -1; /**/ASSERT(0); }
/* next block must be busy and marked PFREE */
if(!ISBUSY(SIZE(nextb)) || !ISPFREE(SIZE(nextb)) )
{ rv = -1; /**/ASSERT(0); }
/* must have a self-reference pointer */
if(SELF(b) != b)
{ rv = -1; /**/ASSERT(0); }
/* segment pointer should be well-defined */
if(!TINIEST(b) && SEG(b) != seg)
{ rv = -1; /**/ASSERT(0); }
/* must be on a free list */
if(b != freeb && !vmisfree(vd, b) )
{ rv = -1; /**/ASSERT(0); }
}
else
{ /* segment pointer should be well-defined */
if(SEG(b) != seg)
{ rv = -1; /**/ASSERT(0); }
/* next block should not be marked PFREE */
if(ISPFREE(SIZE(nextb)) )
{ rv = -1; /**/ASSERT(0); }
/* if PFREE, last block should be free */
if(ISPFREE(SIZE(b)) && LAST(b) != freeb &&
!vmisfree(vd, LAST(b)) )
{ rv = -1; /**/ASSERT(0); }
/* if free but unreclaimed, should be junk */
if(ISJUNK(SIZE(b)) && !vmisjunk(vd, b))
{ rv = -1; /**/ASSERT(0); }
}
}
}
return rv;
}
/* Tree rotation functions */
#define RROTATE(x,y) (LEFT(x) = RIGHT(y), RIGHT(y) = (x), (x) = (y))
#define LROTATE(x,y) (RIGHT(x) = LEFT(y), LEFT(y) = (x), (x) = (y))
#define RLINK(s,x) ((s) = LEFT(s) = (x))
#define LLINK(s,x) ((s) = RIGHT(s) = (x))
/* Find and delete a suitable element in the free tree. */
#if __STD_C
static Block_t* bestsearch(Vmdata_t* vd, reg size_t size, Block_t* wanted)
#else
static Block_t* bestsearch(vd, size, wanted)
Vmdata_t* vd;
reg size_t size;
Block_t* wanted;
#endif
{
reg size_t s;
reg Block_t *t, *root, *l, *r;
Block_t link;
/* extracting a tiniest block from its list */
if((root = wanted) && size == TINYSIZE)
{ reg Seg_t* seg;
l = TLEFT(root);
if((r = LINK(root)) )
TLEFT(r) = l;
if(l)
LINK(l) = r;
else TINY(vd)[0] = r;
seg = vd->seg;
if(!seg->next)
SEG(root) = seg;
else for(;; seg = seg->next)
{ if((Vmuchar_t*)root > (Vmuchar_t*)seg->addr &&
(Vmuchar_t*)root < seg->baddr)
{ SEG(root) = seg;
break;
}
}
return root;
}
/**/ASSERT(!vd->root || vmchktree(vd->root) == 0);
/* find the right one to delete */
l = r = &link;
if((root = vd->root) ) do
{ /**/ ASSERT(!ISBITS(size) && !ISBITS(SIZE(root)));
if(size == (s = SIZE(root)) )
break;
if(size < s)
{ if((t = LEFT(root)) )
{ if(size <= (s = SIZE(t)) )
{ RROTATE(root,t);
if(size == s)
break;
t = LEFT(root);
}
else
{ LLINK(l,t);
t = RIGHT(t);
}
}
RLINK(r,root);
}
else
{ if((t = RIGHT(root)) )
{ if(size >= (s = SIZE(t)) )
{ LROTATE(root,t);
if(size == s)
break;
t = RIGHT(root);
}
else
{ RLINK(r,t);
t = LEFT(t);
}
}
LLINK(l,root);
}
/**/ ASSERT(root != t);
} while((root = t) );
if(root) /* found it, now isolate it */
{ RIGHT(l) = LEFT(root);
LEFT(r) = RIGHT(root);
}
else /* nothing exactly fit */
{ LEFT(r) = NIL(Block_t*);
RIGHT(l) = NIL(Block_t*);
/* grab the least one from the right tree */
if((root = LEFT(&link)) )
{ while((t = LEFT(root)) )
RROTATE(root,t);
LEFT(&link) = RIGHT(root);
}
}
if(root && (r = LINK(root)) )
{ /* head of a link list, use next one for root */
LEFT(r) = RIGHT(&link);
RIGHT(r) = LEFT(&link);
}
else if(!(r = LEFT(&link)) )
r = RIGHT(&link);
else /* graft left tree to right tree */
{ while((t = LEFT(r)) )
RROTATE(r,t);
LEFT(r) = RIGHT(&link);
}
vd->root = r; /**/ASSERT(!r || !ISBITS(SIZE(r)));
/**/ASSERT(!vd->root || vmchktree(vd->root) == 0);
/**/ASSERT(!wanted || wanted == root);
return root;
}
/* Reclaim all delayed free blocks into the free tree */
#if __STD_C
static int bestreclaim(reg Vmdata_t* vd, Block_t* wanted, int c)
#else
static int bestreclaim(vd, wanted, c)
reg Vmdata_t* vd;
Block_t* wanted;
int c;
#endif
{
reg size_t size, s;
reg Block_t *fp, *np, *t, *list;
reg int n, saw_wanted;
/**/COUNT(N_reclaim);
/**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
if((fp = vd->free) )
{ LINK(fp) = CACHE(vd)[S_CACHE]; CACHE(vd)[S_CACHE] = fp;
vd->free = NIL(Block_t*);
}
saw_wanted = wanted ? 0 : 1;
for(n = S_CACHE; n >= c; --n)
{ list = CACHE(vd)[n]; CACHE(vd)[n] = NIL(Block_t*);
while((fp = list) )
{ /* Note that below here we allow ISJUNK blocks to be
** forward-merged even though they are not removed from
** the list immediately. In this way, the list is
** scanned only once. It works because the LINK and SIZE
** fields are not destroyed during the merging. This can
** be seen by observing that a tiniest block has a 2-word
** header and a 2-word body. Merging a tiniest block
** (1seg) and the next block (2seg) looks like this:
** 1seg size link left 2seg size link left ....
** 1seg size link left rite xxxx xxxx .... self
** After the merge, the 2seg word is replaced by the RIGHT
** pointer of the new block and somewhere beyond the
** two xxxx fields, the SELF pointer will replace some
** other word. The important part is that the two xxxx
** fields are kept intact.
*/
list = LINK(list); /**/ASSERT(!vmonlist(list,fp));
size = SIZE(fp);
if(!ISJUNK(size)) /* already done */
continue;
if(ISPFREE(size)) /* backward merge */
{ fp = LAST(fp);
s = SIZE(fp); /**/ASSERT(!(s&BITS));
REMOVE(vd,fp,INDEX(s),t,bestsearch);
size = (size&~BITS) + s + sizeof(Head_t);
}
else size &= ~BITS;
for(;;) /* forward merge */
{ np = (Block_t*)((Vmuchar_t*)fp+size+sizeof(Head_t));
s = SIZE(np); /**/ASSERT(s > 0);
if(!ISBUSY(s))
{ /**/ASSERT((s&BITS) == 0);
if(np == vd->wild)
vd->wild = NIL(Block_t*);
else REMOVE(vd,np,INDEX(s),t,bestsearch);
}
else if(ISJUNK(s))
{ /* reclaim any touched junk list */
if((int)C_INDEX(s) < c)
c = (int)C_INDEX(s);
SIZE(np) = 0;
CLRBITS(s);
}
else break;
size += s + sizeof(Head_t);
}
SIZE(fp) = size;
/* tell next block that this one is free */
np = NEXT(fp); /**/ASSERT(ISBUSY(SIZE(np)));
/**/ASSERT(!ISJUNK(SIZE(np)));
SETPFREE(SIZE(np));
SELF(fp) = fp;
if(fp == wanted) /* to be consumed soon */
{ /**/ASSERT(!saw_wanted); /* should be seen just once */
saw_wanted = 1;
continue;
}
/* wilderness preservation */
if(np->body.data >= vd->seg->baddr)
{ vd->wild = fp;
continue;
}
/* tiny block goes to tiny list */
if(size < MAXTINY)
{ s = INDEX(size);
np = LINK(fp) = TINY(vd)[s];
if(s == 0) /* TINIEST block */
{ if(np)
TLEFT(np) = fp;
TLEFT(fp) = NIL(Block_t*);
}
else
{ if(np)
LEFT(np) = fp;
LEFT(fp) = NIL(Block_t*);
SETLINK(fp);
}
TINY(vd)[s] = fp;
continue;
}
LEFT(fp) = RIGHT(fp) = LINK(fp) = NIL(Block_t*);
if(!(np = vd->root) ) /* inserting into an empty tree */
{ vd->root = fp;
continue;
}
size = SIZE(fp);
while(1) /* leaf insertion */
{ /**/ASSERT(np != fp);
if((s = SIZE(np)) > size)
{ if((t = LEFT(np)) )
{ /**/ ASSERT(np != t);
np = t;
}
else
{ LEFT(np) = fp;
break;
}
}
else if(s < size)
{ if((t = RIGHT(np)) )
{ /**/ ASSERT(np != t);
np = t;
}
else
{ RIGHT(np) = fp;
break;
}
}
else /* s == size */
{ if((t = LINK(np)) )
{ LINK(fp) = t;
LEFT(t) = fp;
}
LINK(np) = fp;
LEFT(fp) = np;
SETLINK(fp);
break;
}
}
}
}
/**/ASSERT(!wanted || saw_wanted == 1);
/**/ASSERT(_vmbestcheck(vd, wanted) == 0);
return saw_wanted;
}
#if __STD_C
static int bestcompact(Vmalloc_t* vm, int local)
#else
static int bestcompact(vm, local)
Vmalloc_t* vm;
int local;
#endif
{
reg Seg_t *seg, *next;
reg Block_t *bp, *tp;
reg size_t size, segsize, round;
reg Vmdata_t* vd = vm->data;
SETLOCK(vm, local);
bestreclaim(vd,NIL(Block_t*),0);
for(seg = vd->seg; seg; seg = next)
{ next = seg->next;
bp = BLOCK(seg->baddr);
if(!ISPFREE(SIZE(bp)) )
continue;
bp = LAST(bp); /**/ASSERT(vmisfree(vd,bp));
size = SIZE(bp);
if(bp == vd->wild)
{ /* During large block allocations, _Vmextend might
** have been enlarged the rounding factor. Reducing
** it a bit help avoiding getting large raw memory.
*/
if((round = vm->disc->round) == 0)
round = _Vmpagesize;
if(size > COMPACT*vd->incr && vd->incr > round)
vd->incr /= 2;
/* for the bottom segment, we don't necessarily want
** to return raw memory too early. vd->pool has an
** approximation of the average size of recently freed
** blocks. If this is large, the application is managing
** large blocks so we throttle back memory chopping
** to avoid thrashing the underlying memory system.
*/
if(size <= COMPACT*vd->incr || size <= COMPACT*vd->pool)
continue;
vd->wild = NIL(Block_t*);
vd->pool = 0;
}
else REMOVE(vd,bp,INDEX(size),tp,bestsearch);
tp = NEXT(bp); /* avoid strict-aliasing pun */
CLRPFREE(SIZE(tp));
if(size < (segsize = seg->size))
size += sizeof(Head_t);
if((size = (*_Vmtruncate)(vm,seg,size,0)) > 0)
{ if(size >= segsize) /* entire segment deleted */
continue;
/**/ASSERT(SEG(BLOCK(seg->baddr)) == seg);
if((size = (seg->baddr - ((Vmuchar_t*)bp) - sizeof(Head_t))) > 0)
SIZE(bp) = size - sizeof(Head_t);
else bp = NIL(Block_t*);
}
if(bp)
{ /**/ ASSERT(SIZE(bp) >= BODYSIZE);
/**/ ASSERT(SEGWILD(bp));
/**/ ASSERT(!vd->root || !vmintree(vd->root,bp));
SIZE(bp) |= BUSY|JUNK;
LINK(bp) = CACHE(vd)[C_INDEX(SIZE(bp))];
CACHE(vd)[C_INDEX(SIZE(bp))] = bp;
}
}
if(!local && _Vmtrace && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST)
(*_Vmtrace)(vm, (Vmuchar_t*)0, (Vmuchar_t*)0, 0, 0);
CLRLOCK(vm, local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
return 0;
}
#if __STD_C
static Void_t* bestalloc(Vmalloc_t* vm, size_t size , int local)
#else
static Void_t* bestalloc(vm, size, local)
Vmalloc_t* vm; /* region allocating from */
size_t size; /* desired block size */
int local; /* internal call */
#endif
{
reg Vmdata_t* vd = vm->data;
reg size_t s;
reg int n;
reg Block_t *tp, *np, *ap;
size_t orgsize = size;
/**/COUNT(N_alloc);
/**/ASSERT(local ? (vd->lock == 1) : 1 );
SETLOCK(vm,local);
/**/ ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
/**/ ASSERT(HEADSIZE == sizeof(Head_t));
/**/ ASSERT(BODYSIZE == sizeof(Body_t));
/**/ ASSERT((ALIGN%(BITS+1)) == 0 );
/**/ ASSERT((sizeof(Head_t)%ALIGN) == 0 );
/**/ ASSERT((sizeof(Body_t)%ALIGN) == 0 );
/**/ ASSERT((BODYSIZE%ALIGN) == 0 );
/**/ ASSERT(sizeof(Block_t) == (sizeof(Body_t)+sizeof(Head_t)) );
/* for ANSI requirement that malloc(0) returns non-NULL pointer */
size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN);
if((tp = vd->free) ) /* reuse last free piece if appropriate */
{ /**/ASSERT(ISBUSY(SIZE(tp)) );
/**/ASSERT(ISJUNK(SIZE(tp)) );
/**/COUNT(N_last);
vd->free = NIL(Block_t*);
if((s = SIZE(tp)) >= size && s < (size << 1) )
{ if(s >= size + (sizeof(Head_t)+BODYSIZE) )
{ SIZE(tp) = size;
np = NEXT(tp);
SEG(np) = SEG(tp);
SIZE(np) = ((s&~BITS) - (size+sizeof(Head_t)))|JUNK|BUSY;
vd->free = np;
SIZE(tp) |= s&BITS;
}
CLRJUNK(SIZE(tp));
goto done;
}
LINK(tp) = CACHE(vd)[S_CACHE];
CACHE(vd)[S_CACHE] = tp;
}
for(n = S_CACHE; n >= 0; --n) /* best-fit except for coalescing */
{ bestreclaim(vd,NIL(Block_t*),n);
if(vd->root && (tp = bestsearch(vd,size,NIL(Block_t*))) )
goto got_block;
}
/**/ASSERT(!vd->free);
if((tp = vd->wild) && SIZE(tp) >= size)
{ /**/COUNT(N_wild);
vd->wild = NIL(Block_t*);
goto got_block;
}
/* need to extend the arena */
KPVCOMPACT(vm,bestcompact);
if((tp = (*_Vmextend)(vm,size,bestsearch)) )
{ got_block:
/**/ ASSERT(!ISBITS(SIZE(tp)));
/**/ ASSERT(SIZE(tp) >= size);
/**/ ASSERT((SIZE(tp)%ALIGN) == 0);
/**/ ASSERT(!vd->free);
/* tell next block that we are no longer a free block */
np = NEXT(tp);
CLRPFREE(SIZE(np)); /**/ ASSERT(ISBUSY(SIZE(np)));
if((s = SIZE(tp)-size) >= (sizeof(Head_t)+BODYSIZE) )
{ SIZE(tp) = size;
np = NEXT(tp);
SEG(np) = SEG(tp);
SIZE(np) = (s - sizeof(Head_t)) | BUSY|JUNK;
if(VMWILD(vd,np))
{ SIZE(np) &= ~BITS;
SELF(np) = np;
ap = NEXT(np); /**/ASSERT(ISBUSY(SIZE(ap)));
SETPFREE(SIZE(ap));
vd->wild = np;
}
else vd->free = np;
}
SETBUSY(SIZE(tp));
}
done:
if(tp && !local && (vd->mode&VM_TRACE) && _Vmtrace && VMETHOD(vd) == VM_MTBEST)
(*_Vmtrace)(vm,NIL(Vmuchar_t*),(Vmuchar_t*)DATA(tp),orgsize,0);
CLRLOCK(vm,local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
return tp ? DATA(tp) : NIL(Void_t*);
}
#if __STD_C
static long bestaddr(Vmalloc_t* vm, Void_t* addr, int local )
#else
static long bestaddr(vm, addr, local)
Vmalloc_t* vm; /* region allocating from */
Void_t* addr; /* address to check */
int local;
#endif
{
reg Seg_t* seg;
reg Block_t *b, *endb;
reg long offset;
reg Vmdata_t* vd = vm->data;
/**/ASSERT(local ? (vd->lock == 1) : 1 );
SETLOCK(vm, local);
offset = -1L; b = endb = NIL(Block_t*);
for(seg = vd->seg; seg; seg = seg->next)
{ b = SEGBLOCK(seg);
endb = (Block_t*)(seg->baddr - sizeof(Head_t));
if((Vmuchar_t*)addr > (Vmuchar_t*)b &&
(Vmuchar_t*)addr < (Vmuchar_t*)endb)
break;
}
if(local ) /* from bestfree or bestresize */
{ b = BLOCK(addr);
if(seg && SEG(b) == seg && ISBUSY(SIZE(b)) && !ISJUNK(SIZE(b)) )
offset = 0;
}
else if(seg)
{ while(b < endb)
{ reg Vmuchar_t* data = (Vmuchar_t*)DATA(b);
reg size_t size = SIZE(b)&~BITS;
if((Vmuchar_t*)addr >= data && (Vmuchar_t*)addr < data+size)
{ if(ISJUNK(SIZE(b)) || !ISBUSY(SIZE(b)))
offset = -1L;
else offset = (long)((Vmuchar_t*)addr - data);
goto done;
}
b = (Block_t*)((Vmuchar_t*)DATA(b) + size);
}
}
done:
CLRLOCK(vm,local);
return offset;
}
#if __STD_C
static int bestfree(Vmalloc_t* vm, Void_t* data, int local )
#else
static int bestfree(vm, data, local )
Vmalloc_t* vm;
Void_t* data;
int local;
#endif
{
reg Vmdata_t* vd = vm->data;
reg Block_t *bp;
reg size_t s;
#ifdef DEBUG
if(((char*)data - (char*)0) <= 1)
{ _Vmassert |= VM_check;
_vmbestcheck(vd, NIL(Block_t*));
if (!data)
_Vmassert &= ~VM_check;
return 0;
}
#else
if(!data) /* ANSI-ism */
return 0;
#endif
/**/COUNT(N_free);
/**/ASSERT(local ? (vd->lock == 1) : 1 );
SETLOCK(vm, local);
/**/ASSERT(KPVADDR(vm, data, bestaddr) == 0);
/**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
bp = BLOCK(data); s = SIZE(bp);
/* Keep an approximate average free block size.
** This is used in bestcompact() to decide when to release
** raw memory back to the underlying memory system.
*/
vd->pool = (vd->pool + (s&~BITS))/2;
if(ISBUSY(s) && !ISJUNK(s))
{ SETJUNK(SIZE(bp));
if(s < MAXCACHE)
{ /**/ASSERT(!vmonlist(CACHE(vd)[INDEX(s)], bp) );
LINK(bp) = CACHE(vd)[INDEX(s)];
CACHE(vd)[INDEX(s)] = bp;
}
else if(!vd->free)
vd->free = bp;
else
{ /**/ASSERT(!vmonlist(CACHE(vd)[S_CACHE], bp) );
LINK(bp) = CACHE(vd)[S_CACHE];
CACHE(vd)[S_CACHE] = bp;
}
/* coalesce on freeing large blocks to avoid fragmentation */
if(SIZE(bp) >= 2*vd->incr)
{ bestreclaim(vd,NIL(Block_t*),0);
if(vd->wild && SIZE(vd->wild) >= COMPACT*vd->incr)
KPVCOMPACT(vm,bestcompact);
}
}
if(!local && _Vmtrace && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST )
(*_Vmtrace)(vm,(Vmuchar_t*)data,NIL(Vmuchar_t*), (s&~BITS), 0);
CLRLOCK(vm, local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
return 0;
}
#if __STD_C
static Void_t* bestresize(Vmalloc_t* vm, Void_t* data, reg size_t size, int type, int local)
#else
static Void_t* bestresize(vm, data, size, type, local)
Vmalloc_t* vm; /* region allocating from */
Void_t* data; /* old block of data */
reg size_t size; /* new size */
int type; /* !=0 to move, <0 for not copy */
int local;
#endif
{
reg Block_t *rp, *np, *t;
size_t s, bs;
size_t oldz = 0, orgsize = size;
Void_t *oldd = 0, *orgdata = data;
Vmdata_t *vd = vm->data;
/**/COUNT(N_resize);
/**/ASSERT(local ? (vd->lock == 1) : 1);
if(!data) /* resizing a NULL block is the same as allocating */
{ data = bestalloc(vm, size, local);
if(data && (type&VM_RSZERO) )
memset((Void_t*)data, 0, size);
return data;
}
if(size == 0) /* resizing to zero size is the same as freeing */
{ (void)bestfree(vm, data, local);
return NIL(Void_t*);
}
SETLOCK(vm, local);
/**/ASSERT(KPVADDR(vm, data, bestaddr) == 0);
/**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN);
rp = BLOCK(data); /**/ASSERT(ISBUSY(SIZE(rp)) && !ISJUNK(SIZE(rp)));
oldz = SIZE(rp); CLRBITS(oldz);
if(oldz < size)
{ np = (Block_t*)((Vmuchar_t*)rp + oldz + sizeof(Head_t));
do /* forward merge as much as possible */
{ s = SIZE(np); /**/ASSERT(!ISPFREE(s));
if(np == vd->free)
{ vd->free = NIL(Block_t*);
CLRBITS(s);
}
else if(ISJUNK(s) )
{ if(!bestreclaim(vd,np,(int)C_INDEX(s)) )
/**/ASSERT(0); /* oops: did not see np! */
s = SIZE(np); /**/ASSERT(s%ALIGN == 0);
}
else if(!ISBUSY(s) )
{ if(np == vd->wild)
vd->wild = NIL(Block_t*);
else REMOVE(vd,np,INDEX(s),t,bestsearch);
}
else break;
SIZE(rp) += (s += sizeof(Head_t)); /**/ASSERT((s%ALIGN) == 0);
np = (Block_t*)((Vmuchar_t*)np + s);
CLRPFREE(SIZE(np));
} while(SIZE(rp) < size);
if(SIZE(rp) < size && size > vd->incr && SEGWILD(rp) )
{ reg Seg_t* seg;
s = (size - SIZE(rp)) + sizeof(Head_t); s = ROUND(s,vd->incr);
seg = SEG(rp);
if((*vm->disc->memoryf)(vm,seg->addr,seg->extent,seg->extent+s,
vm->disc) == seg->addr )
{ SIZE(rp) += s;
seg->extent += s;
seg->size += s;
seg->baddr += s;
s = (SIZE(rp)&~BITS) + sizeof(Head_t);
np = (Block_t*)((Vmuchar_t*)rp + s);
SEG(np) = seg;
SIZE(np) = BUSY;
}
}
}
if((s = SIZE(rp)) >= (size + (BODYSIZE+sizeof(Head_t))) )
{ SIZE(rp) = size;
np = NEXT(rp);
SEG(np) = SEG(rp);
SIZE(np) = (((s&~BITS)-size) - sizeof(Head_t))|BUSY|JUNK;
CPYBITS(SIZE(rp),s);
rp = np;
goto do_free;
}
else if((bs = s&~BITS) < size)
{ if(!(type&(VM_RSMOVE|VM_RSCOPY)) )
data = NIL(Void_t*); /* old data is not moveable */
else
{ oldd = data;
if((data = KPVALLOC(vm,size,bestalloc)) )
{ if(type&VM_RSCOPY)
memcpy(data, oldd, bs);
do_free: /* reclaim these right away */
SETJUNK(SIZE(rp));
LINK(rp) = CACHE(vd)[S_CACHE];
CACHE(vd)[S_CACHE] = rp;
bestreclaim(vd, NIL(Block_t*), S_CACHE);
}
}
}
if(data && (type&VM_RSZERO) && (size = SIZE(BLOCK(data))&~BITS) > oldz )
memset((Void_t*)((Vmuchar_t*)data + oldz), 0, size-oldz);
if(!local && _Vmtrace && data && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST)
(*_Vmtrace)(vm, (Vmuchar_t*)orgdata, (Vmuchar_t*)data, orgsize, 0);
CLRLOCK(vm, local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
return data;
}
#if __STD_C
static long bestsize(Vmalloc_t* vm, Void_t* addr, int local )
#else
static long bestsize(vm, addr, local)
Vmalloc_t* vm; /* region allocating from */
Void_t* addr; /* address to check */
int local;
#endif
{
Seg_t *seg;
Block_t *b, *endb;
long size;
Vmdata_t *vd = vm->data;
SETLOCK(vm, local);
size = -1L;
for(seg = vd->seg; seg; seg = seg->next)
{ b = SEGBLOCK(seg);
endb = (Block_t*)(seg->baddr - sizeof(Head_t));
if((Vmuchar_t*)addr <= (Vmuchar_t*)b ||
(Vmuchar_t*)addr >= (Vmuchar_t*)endb)
continue;
while(b < endb)
{ if(addr == DATA(b))
{ if(!ISBUSY(SIZE(b)) || ISJUNK(SIZE(b)) )
size = -1L;
else size = (long)SIZE(b)&~BITS;
goto done;
}
else if((Vmuchar_t*)addr <= (Vmuchar_t*)b)
break;
b = (Block_t*)((Vmuchar_t*)DATA(b) + (SIZE(b)&~BITS) );
}
}
done:
CLRLOCK(vm, local);
return size;
}
#if __STD_C
static Void_t* bestalign(Vmalloc_t* vm, size_t size, size_t align, int local)
#else
static Void_t* bestalign(vm, size, align, local)
Vmalloc_t* vm;
size_t size;
size_t align;
int local;
#endif
{
Vmuchar_t *data;
Block_t *tp, *np;
Seg_t *seg;
size_t s, extra;
size_t orgsize = size, orgalign = align;
Vmdata_t *vd = vm->data;
if(size <= 0 || align <= 0)
return NIL(Void_t*);
SETLOCK(vm, local);
/**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN);
align = MULTIPLE(align,ALIGN);
/* hack so that dbalign() can store header data */
if(VMETHOD(vd) != VM_MTDEBUG)
extra = 0;
else
{ extra = DB_HEAD;
while(align < extra || (align - extra) < sizeof(Block_t))
align *= 2;
}
/* reclaim all free blocks now to avoid fragmentation */
bestreclaim(vd,NIL(Block_t*),0);
s = size + 2*(align+sizeof(Head_t)+extra);
if(!(data = (Vmuchar_t*)KPVALLOC(vm,s,bestalloc)) )
goto done;
tp = BLOCK(data);
seg = SEG(tp);
/* get an aligned address that we can live with */
if((s = (size_t)((VLONG(data)+extra)%align)) != 0)
data += align-s; /**/ASSERT(((VLONG(data)+extra)%align) == 0);
if((np = BLOCK(data)) != tp ) /* need to free left part */
{ if(((Vmuchar_t*)np - (Vmuchar_t*)tp) < (ssize_t)(sizeof(Block_t)+extra) )
{ data += align;
np = BLOCK(data);
} /**/ASSERT(((VLONG(data)+extra)%align) == 0);
s = (Vmuchar_t*)np - (Vmuchar_t*)tp;
SIZE(np) = ((SIZE(tp)&~BITS) - s)|BUSY;
SEG(np) = seg;
SIZE(tp) = (s - sizeof(Head_t)) | (SIZE(tp)&BITS) | JUNK;
/**/ ASSERT(SIZE(tp) >= sizeof(Body_t) );
LINK(tp) = CACHE(vd)[C_INDEX(SIZE(tp))];
CACHE(vd)[C_INDEX(SIZE(tp))] = tp;
}
/* free left-over if too big */
if((s = SIZE(np) - size) >= sizeof(Block_t))
{ SIZE(np) = size;
tp = NEXT(np);
SIZE(tp) = ((s & ~BITS) - sizeof(Head_t)) | BUSY | JUNK;
SEG(tp) = seg;
LINK(tp) = CACHE(vd)[C_INDEX(SIZE(tp))];
CACHE(vd)[C_INDEX(SIZE(tp))] = tp;
SIZE(np) |= s&BITS;
}
bestreclaim(vd,NIL(Block_t*),0); /* coalesce all free blocks */
if(!local && _Vmtrace && (vd->mode&VM_TRACE) )
(*_Vmtrace)(vm,NIL(Vmuchar_t*),data,orgsize,orgalign);
done:
CLRLOCK(vm, local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
return (Void_t*)data;
}
/* The below implements the discipline Vmdcsbrk and the heap region Vmheap.
** There are 5 alternative ways to get raw memory:
** win32, sbrk, mmap_anon, mmap_zero and reusing the native malloc
** The selection of method done here is to enable our malloc implementation
** to work with concurrent threads. The sbrk/brk interface is unfortunately
** not atomic. Thus, we prefer mmap_anon or mmap_zero if they are available.
*/
#if _mem_win32
#undef _mem_mmap_anon
#undef _mem_mmap_zero
#undef _mem_sbrk
#endif
#if _mem_mmap_anon
#undef _mem_mmap_zero
#if !_PACKAGE_ast
#undef _mem_sbrk
#endif
#endif
#if _mem_mmap_zero
#if !_PACKAGE_ast
#undef _mem_sbrk
#endif
#endif
#if __linux__
/* make sure that allocated memory is addressable */
#include <signal.h>
typedef void (*Sig_f)(int);
static int Gotsegv = 0;
static void sigsegv(int sig)
{
if(sig == SIGSEGV)
Gotsegv = 1;
}
static int chkaddr(Vmuchar_t* addr, size_t nsize)
{
Sig_f segv;
int rv;
Gotsegv = 0; /* catch segment fault */
segv = signal(SIGSEGV, sigsegv);
rv = *(addr+nsize-1);
rv = Gotsegv ? -1 : rv;
signal(SIGSEGV, segv); /* restore signal catcher */
Gotsegv = 0;
return rv;
}
#else
/* known !__linux__ guarantee that brk-addresses are valid */
#define chkaddr(a,n) (0)
#endif /*__linux__*/
#if _mem_win32 /* getting memory on a window system */
#if _PACKAGE_ast
#include <ast_windows.h>
#else
#include <windows.h>
#endif
static Void_t* win32mem(Void_t* caddr, size_t csize, size_t nsize)
{ /**/ ASSERT(csize > 0 || nsize > 0)
if(csize == 0)
{ caddr = (Void_t*)VirtualAlloc(0,nsize,MEM_COMMIT,PAGE_READWRITE);
return caddr;
}
else if(nsize == 0)
{ (void)VirtualFree((LPVOID)caddr,0,MEM_RELEASE);
return caddr;
}
else return NIL(Void_t*);
}
#endif /* _mem_win32 */
#if _mem_sbrk /* getting space via brk/sbrk - not concurrent-ready */
static Void_t* sbrkmem(Void_t* caddr, size_t csize, size_t nsize)
{
Vmuchar_t *addr = (Vmuchar_t*)sbrk(0);
if(!addr || addr == (Vmuchar_t*)(-1) )
return NIL(Void_t*);
if(csize > 0 && addr != (Vmuchar_t*)caddr+csize)
return NIL(Void_t*);
else if(csize == 0)
caddr = addr;
/**/ASSERT(addr == (Vmuchar_t*)caddr+csize);
if(nsize < csize)
addr -= csize-nsize;
else if((addr += nsize-csize) < (Vmuchar_t*)caddr )
return NIL(Void_t*);
if(brk(addr) != 0 )
return NIL(Void_t*);
else if(nsize > csize && chkaddr(caddr, nsize) < 0 )
{ (void)brk((Vmuchar_t*)caddr+csize);
return NIL(Void_t*);
}
else return caddr;
}
#endif /* _mem_sbrk */
#if _mem_mmap_anon || _mem_mmap_zero /* get space using mmap */
#include <fcntl.h>
#include <sys/mman.h>
#ifndef MAP_ANON
#ifdef MAP_ANONYMOUS
#define MAP_ANON MAP_ANONYMOUS
#else
#define MAP_ANON 0
#endif
#endif /*MAP_ANON*/
#ifndef OPEN_MAX
#define OPEN_MAX 64
#endif
#define FD_INIT (-1) /* uninitialized file desc */
#define FD_NONE (-2) /* no mapping with file desc */
typedef struct _mmdisc_s
{ Vmdisc_t disc;
int fd;
off_t offset;
} Mmdisc_t;
static Void_t* mmapmem(Void_t* caddr, size_t csize, size_t nsize, Mmdisc_t* mmdc)
{
#if _mem_mmap_zero
if(mmdc) /* /dev/zero mapping */
{ if(mmdc->fd == FD_INIT ) /* open /dev/zero for mapping */
{ int fd;
if((fd = open("/dev/zero", O_RDONLY)) < 0 )
{ mmdc->fd = FD_NONE;
return NIL(Void_t*);
}
mmdc->fd = _vmfd(fd);
}
if(mmdc->fd == FD_NONE)
return NIL(Void_t*);
}
#endif /* _mem_mmap_zero */
/**/ASSERT(csize > 0 || nsize > 0);
if(csize == 0)
{ nsize = ROUND(nsize, _Vmpagesize);
caddr = NIL(Void_t*);
#if _mem_mmap_zero
if(mmdc && mmdc->fd >= 0 )
caddr = mmap(0, nsize, PROT_READ|PROT_WRITE, MAP_PRIVATE, mmdc->fd, mmdc->offset);
#endif
#if _mem_mmap_anon
if(!mmdc )
caddr = mmap(0, nsize, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#endif
if(!caddr || caddr == (Void_t*)(-1))
return NIL(Void_t*);
else if(chkaddr((Vmuchar_t*)caddr, nsize) < 0 )
{ (void)munmap(caddr, nsize);
return NIL(Void_t*);
}
else
{ if(mmdc)
mmdc->offset += nsize;
return caddr;
}
}
else if(nsize == 0)
{ Vmuchar_t *addr = (Vmuchar_t*)sbrk(0);
if(addr < (Vmuchar_t*)caddr ) /* in sbrk space */
return NIL(Void_t*);
else
{ (void)munmap(caddr, csize);
return caddr;
}
}
else return NIL(Void_t*);
}
#endif /* _mem_map_anon || _mem_mmap_zero */
#if _std_malloc /* using native malloc as a last resource */
static Void_t* mallocmem(Void_t* caddr, size_t csize, size_t nsize)
{
/**/ASSERT(csize > 0 || nsize > 0);
if(csize == 0)
return (Void_t*)malloc(nsize);
else if(nsize == 0)
{ free(caddr);
return caddr;
}
else return NIL(Void_t*);
}
#endif
/* A discipline to get raw memory using VirtualAlloc/mmap/sbrk */
static Void_t* getmemory(Vmalloc_t* vm, Void_t* caddr, size_t csize, size_t nsize, Vmdisc_t* disc)
{
Vmuchar_t *addr;
if((csize > 0 && !caddr) || (csize == 0 && nsize == 0) )
return NIL(Void_t*);
#if _mem_win32
if((addr = win32mem(caddr, csize, nsize)) )
return (Void_t*)addr;
#endif
#if _mem_sbrk
#if 1 /* no sbrk() unless explicit VM_break */
if((_Vmassert & VM_break) && (addr = sbrkmem(caddr, csize, nsize)) )
#else /* asoinit(0,0,0)==0 => the application did not request a specific aso method => sbrk() ok */
if(((_Vmassert & VM_break) || !(_Vmassert & VM_mmap) && !asoinit(0, 0, 0)) && (addr = sbrkmem(caddr, csize, nsize)) )
#endif
return (Void_t*)addr;
#endif
#if _mem_mmap_anon
if((addr = mmapmem(caddr, csize, nsize, (Mmdisc_t*)0)) )
return (Void_t*)addr;
#endif
#if _mem_mmap_zero
if((addr = mmapmem(caddr, csize, nsize, (Mmdisc_t*)disc)) )
return (Void_t*)addr;
#endif
#if _mem_sbrk
if(!(_Vmassert & VM_break) && (addr = sbrkmem(caddr, csize, nsize)) )
return (Void_t*)addr;
#endif
#if _std_malloc
if((addr = mallocmem(caddr, csize, nsize)) )
return (Void_t*)addr;
#endif
return NIL(Void_t*);
}
#if _mem_mmap_zero || _mem_mmap_anon
static Mmdisc_t _Vmdcsystem = { { getmemory, NIL(Vmexcept_f), 64*1024, sizeof(Mmdisc_t) }, FD_INIT, 0 };
#else
static Vmdisc_t _Vmdcsystem = { getmemory, NIL(Vmexcept_f), 0, sizeof(Vmdisc_t) };
#endif
static Vmethod_t _Vmbest =
{
bestalloc,
bestresize,
bestfree,
bestaddr,
bestsize,
bestcompact,
bestalign,
VM_MTBEST
};
/* The heap region */
static Vmdata_t _Vmdata =
{
0, /* lock */
VM_MTBEST|VM_SHARE, /* mode */
0, /* incr */
0, /* pool */
NIL(Seg_t*), /* seg */
NIL(Block_t*), /* free */
NIL(Block_t*), /* wild */
NIL(Block_t*) /* root */
/* tiny[] */
/* cache[] */
};
Vmalloc_t _Vmheap =
{
{ bestalloc,
bestresize,
bestfree,
bestaddr,
bestsize,
bestcompact,
bestalign,
VM_MTBEST
},
NIL(char*), /* file */
0, /* line */
0, /* func */
(Vmdisc_t*)(&_Vmdcsystem), /* disc */
&_Vmdata, /* data */
NIL(Vmalloc_t*) /* next */
};
__DEFINE__(Vmalloc_t*, Vmheap, &_Vmheap);
__DEFINE__(Vmalloc_t*, Vmregion, &_Vmheap);
__DEFINE__(Vmethod_t*, Vmbest, &_Vmbest);
__DEFINE__(Vmdisc_t*, Vmdcsystem, (Vmdisc_t*)(&_Vmdcsystem) );
__DEFINE__(Vmdisc_t*, Vmdcsbrk, (Vmdisc_t*)(&_Vmdcsystem) );
#ifdef NoF
NoF(vmbest)
#endif
#endif