alloc.c

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

			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 /* DEBUG_ALLOC */

# ifdef TEST_ALLOC

Area a;
FILE *myout;

int
main(int argc, char **argv)
{
	char buf[1024];
	struct info {
		int size;
		void *value;
	};
	struct info info[1024 * 2];
	int size, ident;
	int lineno = 0;

	myout = stdout;
	ainit(&a);
	while (fgets(buf, sizeof(buf), stdin)) {
		lineno++;
		if (buf[0] == '\n' || buf[0] == '#')
			continue;
		if (sscanf(buf, " alloc %d = i%d", &size, &ident) == 2) {
			if (ident < 0 || ident > NELEM(info)) {
				fprintf(stderr, "bad ident (%d) on line %d\n",
					ident, lineno);
				exit(1);
			}
			info[ident].value = alloc(info[ident].size = size, &a);
			printf("%p = alloc(%d) [%d,i%d]\n", 
				info[ident].value, info[ident].size,
				lineno, ident);
			memset(info[ident].value, 1, size);
			continue;
		}
		if (sscanf(buf, " afree i%d", &ident) == 1) {
			if (ident < 0 || ident > NELEM(info)) {
				fprintf(stderr, "bad ident (%d) on line %d\n",
					ident, lineno);
				exit(1);
			}
			afree(info[ident].value, &a);
			printf("afree(%p) [%d,i%d]\n", info[ident].value,
				lineno, ident);
			continue;
		}
		if (sscanf(buf, " aresize i%d , %d", &ident, &size) == 2) {
			void *value;
			if (ident < 0 || ident > NELEM(info)) {
				fprintf(stderr, "bad ident (%d) on line %d\n",
					ident, lineno);
				exit(1);
			}
			value = info[ident].value;
			info[ident].value = aresize(value,
						    info[ident].size = size,
						    &a);
			printf("%p = aresize(%p, %d) [%d,i%d]\n", 
				info[ident].value, value, info[ident].size,
				lineno, ident);
			memset(info[ident].value, 1, size);
			continue;
		}
		if (sscanf(buf, " aprint i%d , %d", &ident, &size) == 2) {
			if (ident < 0 || ident > NELEM(info)) {
				fprintf(stderr, "bad ident (%d) on line %d\n",
					ident, lineno);
				exit(1);
			}
			printf("aprint(%p, %d) [%d,i%d]\n",
				info[ident].value, size, lineno, ident);
			aprint(&a, info[ident].value, size);
			continue;
		}
		if (sscanf(buf, " aprint %d", &ident) == 1) {
			if (ident < 0 || ident > NELEM(info)) {
				fprintf(stderr, "bad ident (%d) on line %d\n",
					ident, lineno);
				exit(1);
			}
			printf("aprint(0, 0) [%d]\n", lineno);
			aprint(&a, 0, 0);
			continue;
		}
		if (sscanf(buf, " afreeall %d", &ident) == 1) {
			printf("afreeall() [%d]\n", lineno);
			afreeall(&a);
			memset(info, 0, sizeof(info));
			continue;
		}
		fprintf(stderr, "unrecognized line (line %d)\n",
			lineno);
		exit(1);
	}
	return 0;
}

void
aerror(Area *ap, const char *msg)
{
	printf("aerror: %s\n", msg);
	fflush(stdout);
	abort();
}

# endif /* TEST_ALLOC */

#endif /* MEM_DEBUG */