alloc.c

一个开放源代码的 AT&T 的 Korn Shell 的复制品, 支持大多数 ksh89 的特性。

/*
 * area-based allocation built on malloc/free
 */

#include "sh.h"

#ifdef TEST_ALLOC
# define shellf	printf
# ifndef DEBUG_ALLOC
#  define DEBUG_ALLOC
# endif /* DEBUG_ALLOC */
#endif /* TEST_ALLOC */

#ifdef MEM_DEBUG

/*
 * Special versions of alloc routines if doing mem_debug
 */
Area *
_chmem_ainit(ap, file, line)
	Area *ap;
	const char *file;
	int line;
{
	ap->freelist = (struct Block *) _chmem_newpool("ainit", (char *) 0, -1,
						file, line);
	if (!ap->freelist)
	    aerror(ap, "ainit failed (ie, newpool)");
	return ap;
}

/* free all object in Area */
void
_chmem_afreeall(ap, file, line)
	Area *ap;
	const char *file;
	int line;
{
	_chmem_delpool((Chmem_poolp) ap->freelist, 0, file, line);
	/* Kind of ugly, but it works */
	_chmem_ainit(ap, file, line);
}

/* allocate object from Area */
void *
_chmem_alloc(size, ap, file, line)
	size_t size;
	Area *ap;
	const char *file;
	int line;
{
	return _chmem_mallocp((Chmem_poolp) ap->freelist, size, file, line);
}

/* change size of object -- like realloc */
void *
_chmem_aresize(ptr, size, ap, file, line)
	void *ptr;
	size_t size;
	Area *ap;
	const char *file;
	int line;
{
	if (!ptr)
		/* Done as realloc(0, size) is not portable */
		return _chmem_mallocp((Chmem_poolp) ap->freelist, size,
					file, line);
	else
		return _chmem_reallocp((Chmem_poolp) ap->freelist, ptr, size,
					file, line);
}

void
_chmem_afree(ptr, ap, file, line)
	void *ptr;
	Area *ap;
	const char *file;
	int line;
{
	return _chmem_freep((Chmem_poolp) ap->freelist, ptr, file, line);
}

#else /* MEM_DEBUG */

# 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)