Subversion Repositories planix.SVN

/*

 * 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