Rev 2 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* area-based allocation built on malloc/free
*/
#include "sh.h"
# if DEBUG_ALLOC
void acheck ARGS((Area *ap));
# define ACHECK(ap) acheck(ap)
# else /* DEBUG_ALLOC */
# define ACHECK(ap)
# endif /* DEBUG_ALLOC */
#define ICELLS 200 /* number of Cells in small Block */
typedef union Cell Cell;
typedef struct Block Block;
/*
* The Cells in a Block are organized as a set of objects.
* Each object (pointed to by dp) begins with the block it is in
* (dp-2)->block, then has a size in (dp-1)->size, which is
* followed with "size" data Cells. Free objects are
* linked together via dp->next.
*/
#define NOBJECT_FIELDS 2 /* the block and size `fields' */
union Cell {
size_t size;
Cell *next;
Block *block;
struct {int _;} junk; /* alignment */
double djunk; /* alignment */
};
struct Block {
Block *next; /* list of Blocks in Area */
Block *prev; /* previous block in list */
Cell *freelist; /* object free list */
Cell *last; /* &b.cell[size] */
Cell cell [1]; /* [size] Cells for allocation */
};
static Block aempty = {&aempty, &aempty, aempty.cell, aempty.cell};
static void ablockfree ARGS((Block *bp, Area *ap));
static void *asplit ARGS((Area *ap, Block *bp, Cell *fp, Cell *fpp, int cells));
/* create empty Area */
Area *
ainit(ap)
register Area *ap;
{
ap->freelist = &aempty;
ACHECK(ap);
return ap;
}
/* free all object in Area */
void
afreeall(ap)
register Area *ap;
{
register Block *bp;
register Block *tmp;
ACHECK(ap);
bp = ap->freelist;
if (bp != NULL && bp != &aempty) {
do {
tmp = bp;
bp = bp->next;
free((void*)tmp);
} while (bp != ap->freelist);
ap->freelist = &aempty;
}
ACHECK(ap);
}
/* allocate object from Area */
void *
alloc(size, ap)
size_t size;
register Area *ap;
{
int cells, acells;
Block *bp = 0;
Cell *fp = 0, *fpp = 0;
ACHECK(ap);
if (size <= 0)
aerror(ap, "allocate bad size");
cells = (unsigned)(size + sizeof(Cell) - 1) / sizeof(Cell);
/* allocate at least this many cells */
acells = cells + NOBJECT_FIELDS;
/*
* Only attempt to track small objects - let malloc deal
* with larger objects. (this way we don't have to deal with
* coalescing memory, or with releasing it to the system)
*/
if (cells <= ICELLS) {
/* find free Cell large enough */
for (bp = ap->freelist; ; bp = bp->next) {
for (fpp = NULL, fp = bp->freelist;
fp != bp->last; fpp = fp, fp = fp->next)
{
if ((fp-1)->size >= cells)
goto Found;
}
/* wrapped around Block list, create new Block */
if (bp->next == ap->freelist) {
bp = 0;
break;
}
}
/* Not much free space left? Allocate a big object this time */
acells += ICELLS;
}
if (bp == 0) {
bp = (Block*) malloc(offsetof(Block, cell[acells]));
if (bp == NULL)
aerror(ap, "cannot allocate");
if (ap->freelist == &aempty) {
ap->freelist = bp->next = bp->prev = bp;
} else {
bp->next = ap->freelist->next;
ap->freelist->next->prev = bp;
ap->freelist->next = bp;
bp->prev = ap->freelist;
}
bp->last = bp->cell + acells;
/* initial free list */
fp = bp->freelist = bp->cell + NOBJECT_FIELDS;
(fp-1)->size = acells - NOBJECT_FIELDS;
(fp-2)->block = bp;
fp->next = bp->last;
fpp = NULL;
}
Found:
return asplit(ap, bp, fp, fpp, cells);
}
/* Do the work of splitting an object into allocated and (possibly) unallocated
* objects. Returns the `allocated' object.
*/
static void *
asplit(ap, bp, fp, fpp, cells)
Area *ap;
Block *bp;
Cell *fp;
Cell *fpp;
int cells;
{
Cell *dp = fp; /* allocated object */
int split = (fp-1)->size - cells;
ACHECK(ap);
if (split < 0)
aerror(ap, "allocated object too small");
if (split <= NOBJECT_FIELDS) { /* allocate all */
fp = fp->next;
} else { /* allocate head, free tail */
Cell *next = fp->next; /* needed, as cells may be 0 */
ap->freelist = bp; /* next time, start looking for space here */
(fp-1)->size = cells;
fp += cells + NOBJECT_FIELDS;
(fp-1)->size = split - NOBJECT_FIELDS;
(fp-2)->block = bp;
fp->next = next;
}
if (fpp == NULL)
bp->freelist = fp;
else
fpp->next = fp;
ACHECK(ap);
return (void*) dp;
}
/* change size of object -- like realloc */
void *
aresize(ptr, size, ap)
register void *ptr;
size_t size;
Area *ap;
{
int cells;
Cell *dp = (Cell*) ptr;
int oldcells = dp ? (dp-1)->size : 0;
ACHECK(ap);
if (size <= 0)
aerror(ap, "allocate bad size");
/* New size (in cells) */
cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
/* Is this a large object? If so, let malloc deal with it
* directly (unless we are crossing the ICELLS border, in
* which case the alloc/free below handles it - this should
* cut down on fragmentation, and will also keep the code
* working (as it assumes size < ICELLS means it is not
* a `large object').
*/
if (oldcells > ICELLS && cells > ICELLS) {
Block *bp = (dp-2)->block;
Block *nbp;
/* Saved in case realloc fails.. */
Block *next = bp->next, *prev = bp->prev;
if (bp->freelist != bp->last)
aerror(ap, "allocation resizing free pointer");
nbp = realloc((void *) bp,
offsetof(Block, cell[cells + NOBJECT_FIELDS]));
if (!nbp) {
/* Have to clean up... */
/* NOTE: If this code changes, similar changes may be
* needed in ablockfree().
*/
if (next == bp) /* only block */
ap->freelist = &aempty;
else {
next->prev = prev;
prev->next = next;
if (ap->freelist == bp)
ap->freelist = next;
}
aerror(ap, "cannot re-allocate");
}
/* If location changed, keep pointers straight... */
if (nbp != bp) {
if (next == bp) /* only one block */
nbp->next = nbp->prev = nbp;
else {
next->prev = nbp;
prev->next = nbp;
}
if (ap->freelist == bp)
ap->freelist = nbp;
dp = nbp->cell + NOBJECT_FIELDS;
(dp-2)->block = nbp;
}
(dp-1)->size = cells;
nbp->last = nbp->cell + cells + NOBJECT_FIELDS;
nbp->freelist = nbp->last;
ACHECK(ap);
return (void*) dp;
}
/* Check if we can just grow this cell
* (need to check that cells < ICELLS so we don't make an
* object a `large' - that would mess everything up).
*/
if (dp && cells > oldcells && cells <= ICELLS) {
Cell *fp, *fpp;
Block *bp = (dp-2)->block;
int need = cells - oldcells - NOBJECT_FIELDS;
/* XXX if we had a flag in an object indicating
* if the object was free/allocated, we could
* avoid this loop (perhaps)
*/
for (fpp = NULL, fp = bp->freelist;
fp != bp->last
&& dp + oldcells + NOBJECT_FIELDS <= fp
; fpp = fp, fp = fp->next)
{
if (dp + oldcells + NOBJECT_FIELDS == fp
&& (fp-1)->size >= need)
{
Cell *np = asplit(ap, bp, fp, fpp, need);
/* May get more than we need here */
(dp-1)->size += (np-1)->size + NOBJECT_FIELDS;
ACHECK(ap);
return ptr;
}
}
}
/* Check if we can just shrink this cell
* (if oldcells > ICELLS, this is a large object and we leave
* it to malloc...)
* Note: this also handles cells == oldcells (a no-op).
*/
if (dp && cells <= oldcells && oldcells <= ICELLS) {
int split;
split = oldcells - cells;
if (split <= NOBJECT_FIELDS) /* cannot split */
;
else { /* shrink head, free tail */
Block *bp = (dp-2)->block;
(dp-1)->size = cells;
dp += cells + NOBJECT_FIELDS;
(dp-1)->size = split - NOBJECT_FIELDS;
(dp-2)->block = bp;
afree((void*)dp, ap);
}
/* ACHECK() done in afree() */
return ptr;
}
/* Have to do it the hard way... */
ptr = alloc(size, ap);
if (dp != NULL) {
size_t s = (dp-1)->size * sizeof(Cell);
if (s > size)
s = size;
memcpy(ptr, dp, s);
afree((void *) dp, ap);
}
/* ACHECK() done in alloc()/afree() */
return ptr;
}
void
afree(ptr, ap)
void *ptr;
register Area *ap;
{
register Block *bp;
register Cell *fp, *fpp;
register Cell *dp = (Cell*)ptr;
ACHECK(ap);
if (ptr == 0)
aerror(ap, "freeing null pointer");
bp = (dp-2)->block;
/* If this is a large object, just free it up... */
/* Release object... */
if ((dp-1)->size > ICELLS) {
ablockfree(bp, ap);
ACHECK(ap);
return;
}
if (dp < &bp->cell[NOBJECT_FIELDS] || dp >= bp->last)
aerror(ap, "freeing memory outside of block (corrupted?)");
/* find position in free list */
/* XXX if we had prev/next pointers for objects, this loop could go */
for (fpp = NULL, fp = bp->freelist; fp < dp; fpp = fp, fp = fp->next)
;
if (fp == dp)
aerror(ap, "freeing free object");
/* join object with next */
if (dp + (dp-1)->size == fp-NOBJECT_FIELDS) { /* adjacent */
(dp-1)->size += (fp-1)->size + NOBJECT_FIELDS;
dp->next = fp->next;
} else /* non-adjacent */
dp->next = fp;
/* join previous with object */
if (fpp == NULL)
bp->freelist = dp;
else if (fpp + (fpp-1)->size == dp-NOBJECT_FIELDS) { /* adjacent */
(fpp-1)->size += (dp-1)->size + NOBJECT_FIELDS;
fpp->next = dp->next;
} else /* non-adjacent */
fpp->next = dp;
/* If whole block is free (and we have some other blocks
* around), release this block back to the system...
*/
if (bp->next != bp && bp->freelist == bp->cell + NOBJECT_FIELDS
&& bp->freelist + (bp->freelist-1)->size == bp->last
/* XXX and the other block has some free memory? */
)
ablockfree(bp, ap);
ACHECK(ap);
}
static void
ablockfree(bp, ap)
Block *bp;
Area *ap;
{
/* NOTE: If this code changes, similar changes may be
* needed in alloc() (where realloc fails).
*/
if (bp->next == bp) /* only block */
ap->freelist = &aempty;
else {
bp->next->prev = bp->prev;
bp->prev->next = bp->next;
if (ap->freelist == bp)
ap->freelist = bp->next;
}
free((void*) bp);
}
# if DEBUG_ALLOC
void
acheck(ap)
Area *ap;
{
Block *bp, *bpp;
Cell *dp, *dptmp, *fp;
int ok = 1;
int isfree;
static int disabled;
if (disabled)
return;
if (!ap) {
disabled = 1;
aerror(ap, "acheck: null area pointer");
}
bp = ap->freelist;
if (!bp) {
disabled = 1;
aerror(ap, "acheck: null area freelist");
}
/* Nothing to check... */
if (bp == &aempty)
return;
bpp = ap->freelist->prev;
while (1) {
if (bp->prev != bpp) {
shellf("acheck: bp->prev != previous\n");
ok = 0;
}
fp = bp->freelist;
for (dp = &bp->cell[NOBJECT_FIELDS]; dp != bp->last; ) {
if ((dp-2)->block != bp) {
shellf("acheck: fragment's block is wrong\n");
ok = 0;
}
isfree = dp == fp;
if ((dp-1)->size == 0 && isfree) {
shellf("acheck: 0 size frag\n");
ok = 0;
}
if ((dp-1)->size > ICELLS
&& !isfree
&& (dp != &bp->cell[NOBJECT_FIELDS]
|| dp + (dp-1)->size != bp->last))
{
shellf("acheck: big cell doesn't make up whole block\n");
ok = 0;
}
if (isfree) {
if (dp->next <= dp) {
shellf("acheck: free fragment's next <= self\n");
ok = 0;
}
if (dp->next > bp->last) {
shellf("acheck: free fragment's next > last\n");
ok = 0;
}
fp = dp->next;
}
dptmp = dp + (dp-1)->size;
if (dptmp > bp->last) {
shellf("acheck: next frag out of range\n");
ok = 0;
break;
} else if (dptmp != bp->last) {
dptmp += NOBJECT_FIELDS;
if (dptmp > bp->last) {
shellf("acheck: next frag just out of range\n");
ok = 0;
break;
}
}
if (isfree && dptmp == fp && dptmp != bp->last) {
shellf("acheck: adjacent free frags\n");
ok = 0;
} else if (dptmp > fp) {
shellf("acheck: free frag list messed up\n");
ok = 0;
}
dp = dptmp;
}
bpp = bp;
bp = bp->next;
if (bp == ap->freelist)
break;
}
if (!ok) {
disabled = 1;
aerror(ap, "acheck failed");
}
}
void
aprint(ap, ptr, size)
register Area *ap;
void *ptr;
size_t size;
{
Block *bp;
if (!ap)
shellf("aprint: null area pointer\n");
else if (!(bp = ap->freelist))
shellf("aprint: null area freelist\n");
else if (bp == &aempty)
shellf("aprint: area is empty\n");
else {
int i;
Cell *dp, *fp;
Block *bpp;
bpp = ap->freelist->prev;
for (i = 0; ; i++) {
if (ptr) {
void *eptr = (void *) (((char *) ptr) + size);
/* print block only if it overlaps ptr/size */
if (!((ptr >= (void *) bp
&& ptr <= (void *) bp->last)
|| (eptr >= (void *) bp
&& eptr <= (void *) bp->last)))
continue;
shellf("aprint: overlap of 0x%p .. 0x%p\n",
ptr, eptr);
}
if (bp->prev != bpp || bp->next->prev != bp)
shellf(
"aprint: BAD prev pointer: bp %p, bp->prev %p, bp->next %p, bpp=%p\n",
bp, bp->prev, bp->next, bpp);
shellf("aprint: block %2d (p=%p,%p,n=%p): 0x%p .. 0x%p (%ld)\n", i,
bp->prev, bp, bp->next,
bp->cell, bp->last,
(long) ((char *) bp->last - (char *) bp->cell));
fp = bp->freelist;
if (bp->last <= bp->cell + NOBJECT_FIELDS)
shellf(
"aprint: BAD bp->last too small: %p <= %p\n",
bp->last, bp->cell + NOBJECT_FIELDS);
if (bp->freelist < bp->cell + NOBJECT_FIELDS
|| bp->freelist > bp->last)
shellf(
"aprint: BAD bp->freelist %p out of range: %p .. %p\n",
bp->freelist,
bp->cell + NOBJECT_FIELDS, bp->last);
for (dp = bp->cell; dp != bp->last ; ) {
dp += NOBJECT_FIELDS;
shellf(
"aprint: 0x%p .. 0x%p (%ld) %s\n",
(dp-NOBJECT_FIELDS),
(dp-NOBJECT_FIELDS) + (dp-1)->size
+ NOBJECT_FIELDS,
(long) ((dp-1)->size + NOBJECT_FIELDS)
* sizeof(Cell),
dp == fp ? "free" : "allocated");
if ((dp-2)->block != bp)
shellf(
"aprint: BAD dp->block %p != bp %p\n",
(dp-2)->block, bp);
if (dp > bp->last)
shellf(
"aprint: BAD dp gone past block: %p > %p\n",
dp, bp->last);
if (dp > fp)
shellf(
"aprint: BAD dp gone past free: %p > %p\n",
dp, fp);
if (dp == fp) {
fp = fp->next;
if (fp < dp || fp > bp->last)
shellf(
"aprint: BAD free object %p out of range: %p .. %p\n",
fp,
dp, bp->last);
}
dp += (dp-1)->size;
}
bpp = bp;
bp = bp->next;
if (bp == ap->freelist)
break;
}
}
}
#endif