pool.c

著名操作系统Plan 9的第三版的部分核心源代码。现在很难找到了。Plan 9是bell实验室开发的Unix后继者。

{
	Bhdr *bbot, *btop;
	Btail *t;

	blockcheck(p, bot);
	blockcheck(p, top);
	assert(bot->aup == top && top > bot);

	if(p->merge == nil || p->merge(bot, top) == 0)
		return nil;

	/* remove top from list */
	if(bot->aup = top->aup)	/* assign = */
		bot->aup->down = bot;
	else
		p->arenalist = bot;
	
	/* save ptrs to last block in bot, first block in top */
	t = B2PT(A2TB(bot));
	bbot = T2HDR(t);
	btop = A2B(top);
	blockcheck(p, bbot);
	blockcheck(p, btop);

	/* grow bottom arena to encompass top */
	arenasetsize(bot, top->asize + ((uchar*)top - (uchar*)bot));

	/* grow bottom block to encompass space between arenas */
	blockgrow(p, bbot, (uchar*)btop-(uchar*)bbot);
	blockcheck(p, bbot);
	return bot;
}

/* dumpblock: print block's vital stats */
static void
dumpblock(Pool *p, Bhdr *b)
{
	ulong *dp;
	ulong dsize;
	uchar *cp;

	dp = (ulong*)b;
	p->print(p, "pool %s block %p\nhdr %.8lux %.8lux %.8lux %.8lux %.8lux %.8lux\n",
		p->name, b, dp[0], dp[1], dp[2], dp[3], dp[4], dp[5], dp[6]);

	if(b->size >= 1024*1024*1024)	/* tail pointer corrupt; printing tail will fault */
		return;
	dp = (ulong*)B2T(b);
	p->print(p, "tail %.8lux %.8lux %.8lux %.8lux %.8lux %.8lux\n",
		dp[-6], dp[-5], dp[-4], dp[-3], dp[-2], dp[-1]);

	if(b->magic == KEMPT_MAGIC){
		dsize = getdsize((Alloc*)b);
		if(dsize >= b->size)	/* user data size corrupt */
			return;

		cp = (uchar*)_B2D(b)+dsize;
		p->print(p, "user data ");
		p->print(p, "%.2ux %.2ux %.2ux %.2ux  %.2ux %.2ux %.2ux %.2ux",
			cp[-8], cp[-7], cp[-6], cp[-5], cp[-4], cp[-3], cp[-2], cp[-1]);
		p->print(p, " | %.2ux %.2ux %.2ux %.2ux  %.2ux %.2ux %.2ux %.2ux\n",
			cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
	}
}

static void
printblock(Pool *p, Bhdr *b, char *msg)
{
	p->print(p, "%s\n", msg);
	dumpblock(p, b);
}

static void
panicblock(Pool *p, Bhdr *b, char *msg)
{
	p->print(p, "%s\n", msg);
	dumpblock(p, b);
	p->panic(p, "pool panic");
}

/* blockcheck: ensure a block consistent with our expectations */
/* should only be called when holding pool lock */
static void
blockcheck(Pool *p, Bhdr *b)
{
	Alloc *a;
	Btail *t;
	uchar *q, *bq, *eq;
	ulong dsize;

	switch(b->magic) {
	default:
		panicblock(p, b, "bad magic");
	case FREE_MAGIC:
	case UNKEMPT_MAGIC:
	 	t = B2T(b);
		if(t->magic0 != TAIL_MAGIC0 || t->magic1 != TAIL_MAGIC1)
			panicblock(p, b, "corrupt tail magic");
		if(T2HDR(t) != b)
			panicblock(p, b, "corrupt tail ptr");
		break;
	case ARENA_MAGIC:
		b = A2TB((Arena*)b);
		if(b->magic != ARENATAIL_MAGIC)
			panicblock(p, b, "bad arena size");
		/* fall through */
	case ARENATAIL_MAGIC:
		if(b->size != 0)
			panicblock(p, b, "bad arena tail size");
		break;
	case KEMPT_MAGIC:
		a = (Alloc*)b;
		if(a->size > 1024*1024*1024)
			panicblock(p, b, "block too big");

	 	t = B2T(b);
		dsize = getdsize(a);
		bq = (uchar*)_B2D(a)+dsize;
		eq = (uchar*)t;

		if(t->magic0 != TAIL_MAGIC0){
			/* if someone wrote exactly one byte over and it was a NUL, we sometimes only complain. */
			if((p->flags & POOL_TOLERANCE) && bq == eq && t->magic0 == 0)
				printblock(p, b, "mem user overflow (magic0)");
			else
				panicblock(p, b, "corrupt tail magic0");
		}

		if(t->magic1 != TAIL_MAGIC1)
			panicblock(p, b, "corrupt tail magic1");
		if(T2HDR(t) != b)
			panicblock(p, b, "corrupt tail ptr");

		if(dsize2bsize(p, dsize)  > a->size)
			panicblock(p, b, "too much block data");

		if(eq > bq+4)
			eq = bq+4;
		for(q=bq; q<eq; q++){
			if(*q != datamagic[((ulong)q)%nelem(datamagic)]){
				if(q == bq && *q == 0 && (p->flags & POOL_TOLERANCE)){
					printblock(p, b, "mem user overflow");
					continue;
				}
				panicblock(p, b, "mem user overflow");
			}
		}
		break;
	}
}

/*
 * compact an arena by shifting all the free blocks to the end.
 * assumes pool lock is held.
 */
enum {
	FLOATING_MAGIC = 0xCBCBCBCB,	/* temporarily neither allocated nor in the free tree */
};

static int
arenacompact(Pool *p, Arena *a)
{
	Bhdr *b, *wb, *eb, *nxt;
	int compacted;

	if(p->move == nil)
		p->panic(p, "don't call me when pool->move is nil\n");

	poolcheckarena(p, a);
	eb = A2TB(a);
	compacted = 0;
	for(b=wb=A2B(a); b && b < eb; b=nxt) {
		nxt = B2NB(b);
		switch(b->magic) {
		case FREE_MAGIC:
			pooldel(p, (Free*)b);
			b->magic = FLOATING_MAGIC;
			break;
		case KEMPT_MAGIC:
			if(wb != b) {
				memmove(wb, b, b->size);
				p->move(_B2D(b), _B2D(wb));
				compacted = 1;
			}
			wb = B2NB(wb);
			break;
		}
	}

	/*
	 * the only free data is now at the end of the arena, pointed
	 * at by wb.  all we need to do is set its size and get out.
	 */
	if(wb < eb) {
		wb->magic = UNKEMPT_MAGIC;
		blocksetsize(wb, (uchar*)eb-(uchar*)wb);
		pooladd(p, (Alloc*)wb);
	}

	return compacted;		
}

/*
 * compact a pool by compacting each individual arena.
 * 'twould be nice to shift blocks from one arena to the
 * next but it's a pain to code.
 */
static int
poolcompactl(Pool *pool)
{
	Arena *a;
	int compacted;

	if(pool->move == nil || pool->lastcompact == pool->nfree)
		return 0;

	pool->lastcompact = pool->nfree;
	compacted = 0;
	for(a=pool->arenalist; a; a=a->down)
		compacted |= arenacompact(pool, a);
	return compacted;
}

/*
static int
poolcompactl(Pool*)
{
	return 0;
}
*/

/*
 * Actual allocators
 */

/*
static void*
_B2D(void *a)
{
	return (uchar*)a+sizeof(Bhdr);
}
*/

static void*
B2D(Pool *p, Alloc *a)
{
	if(a->magic != KEMPT_MAGIC)
		p->panic(p, "B2D called on unworthy block");
	return _B2D(a);
}

/*
static void*
_D2B(void *v)
{
	Alloc *a;
	a = (Alloc*)((uchar*)v-sizeof(Bhdr));
	return a;
}
*/

static Alloc*
D2B(Pool *p, void *v)
{
	Alloc *a;
	a = _D2B(v);
	if(a->magic != KEMPT_MAGIC)
		p->panic(p, "D2B called on non-block %p", v);
	return a;
}

/* poolallocl: attempt to allocate block to hold dsize user bytes; assumes lock held */
static void*
poolallocl(Pool *p, ulong dsize)
{
	ulong bsize;
	Free *fb;
	Alloc *ab;

	if(dsize < 0 || dsize >= 0x80000000UL)	/* for sanity, overflow */
		return nil;

	bsize = dsize2bsize(p, dsize);

	fb = treelookupgt(p->freeroot, bsize);
	if(fb == nil) {
		poolnewarena(p, bsize2asize(p, bsize));
		if((fb = treelookupgt(p->freeroot, bsize)) == nil) {
			/* assume poolnewarena failed and set %r */
			return nil;
		}
	}

	ab = kemb(p, pooldel(p, fb), dsize);
	p->curalloc += ab->size;
	return B2D(p, ab);
}

/* poolreallocl: attempt to grow v to ndsize bytes; assumes lock held */
static void*
poolreallocl(Pool *p, void *v, ulong ndsize)
{
	Alloc *a;
	Bhdr *left, *right, *newb;
	Btail *t;
	ulong nbsize;
	ulong odsize;
	ulong obsize;
	void *nv;

	if(v == nil)	/* for ANSI */
		return poolallocl(p, ndsize);
	if(ndsize == 0) {
		poolfreel(p, v);
		return nil;
	}
	a = D2B(p, v);
	blockcheck(p, a);
	odsize = getdsize(a);
	obsize = a->size;

	/* can reuse the same block? */
	nbsize = dsize2bsize(p, ndsize);
	if(nbsize <= a->size) {
	Returnblock:
		if(v != _B2D(a))
			memmove(_B2D(a), v, odsize);
		a = kemb(p, a, ndsize);
		p->curalloc -= obsize;
		p->curalloc += a->size;
		v = B2D(p, a);
		return v;
	}

	/* can merge with surrounding blocks? */
	right = B2NB(a);
	if(right->magic == FREE_MAGIC && a->size+right->size >= nbsize) {
		a = blockmerge(p, a, right);
		goto Returnblock;
	}

	t = B2PT(a);
	left = T2HDR(t);
	if(left->magic == FREE_MAGIC && left->size+a->size >= nbsize) {
		a = blockmerge(p, left, a);
		goto Returnblock;
	}

	if(left->magic == FREE_MAGIC && right->magic == FREE_MAGIC
	&& left->size+a->size+right->size >= nbsize) {
		a = blockmerge(p, blockmerge(p, left, a), right);
		goto Returnblock;
	}

	if((nv = poolallocl(p, ndsize)) == nil)
		return nil;

	/* maybe the new block is next to us; if so, merge */
	left = T2HDR(B2PT(a));
	right = B2NB(a);
	newb = D2B(p, nv);
	if(left == newb || right == newb) {
		if(left == newb || left->magic == FREE_MAGIC)
			a = blockmerge(p, left, a);
		if(right == newb || right->magic == FREE_MAGIC)
			a = blockmerge(p, a, right);
		assert(a->size >= nbsize);
		goto Returnblock;
	}

	/* enough cleverness */
	memmove(nv, v, odsize);
	poolfreel(p, v);
	return nv;
}

/* poolfree: free block obtained from poolalloc; assumes lock held */
static void
poolfreel(Pool *p, void *v)
{
	Alloc *ab;
	Bhdr *back, *fwd;

	if(v == nil)	/* for ANSI */
		return;

	ab = D2B(p, v);
	blockcheck(p, ab);

	p->nfree++;
	p->curalloc -= ab->size;
	back = T2HDR(B2PT(ab));
	if(back->magic == FREE_MAGIC)
		ab = blockmerge(p, back, ab);

	fwd = B2NB(ab);
	if(fwd->magic == FREE_MAGIC)
		ab = blockmerge(p, ab, fwd);

	pooladd(p, ab);
}

void*
poolalloc(Pool *p, ulong n)
{
	void *v;

	p->lock(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	v = poolallocl(p, n);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p);
	LOG(p, "poolalloc %p %lud = %p\n", p, n, v);
	p->unlock(p);
	return v;
}

int
poolcompact(Pool *p)
{
	int rv;

	p->lock(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	rv = poolcompactl(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	LOG(p, "poolcompact %p\n", p);
	p->unlock(p);
	return rv;
}

void*
poolrealloc(Pool *p, void *v, ulong n)
{
	void *nv;

	p->lock(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	nv = poolreallocl(p, v, n);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p);
	LOG(p, "poolrealloc %p %p %ld = %p\n", p, v, n, nv);
	p->unlock(p);
	return nv;
}

void
poolfree(Pool *p, void *v)
{
	p->lock(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	poolfreel(p, v);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p);
	LOG(p, "poolfree %p %p\n", p, v);
	p->unlock(p);
}

/*
 * Return the real size of a block, and let the user use it. 
 */
ulong
poolmsize(Pool *p, void *v)
{
	Alloc *b;
	ulong dsize;

	p->lock(p);
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	if(v == nil)	/* consistency with other braindead ANSI-ness */
		dsize = 0;
	else {
		b = D2B(p, v);
		dsize = (b->size&~(p->quantum-1)) - sizeof(Bhdr) - sizeof(Btail);
		assert(dsize >= getdsize(b));
		blocksetdsize(p, b, dsize);
	}
	paranoia {
		poolcheckl(p);
	}
	verbosity {
		pooldumpl(p);
	}
	if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p);
	LOG(p, "poolmsize %p %p = %ld\n", p, v, dsize);
	p->unlock(p);
	return dsize;
}

/*
 * Debugging 
 */

static void
poolcheckarena(Pool *p, Arena *a)
{
	Bhdr *b;
	Bhdr *atail;

	atail = A2TB(a);
	for(b=a; b->magic != ARENATAIL_MAGIC && b<atail; b=B2NB(b))
		blockcheck(p, b);
	blockcheck(p, b);
	if(b != atail)
		p->panic(p, "found wrong tail");
}

static void
poolcheckl(Pool *p)
{
	Arena *a;

	for(a=p->arenalist; a; a=a->down)
		poolcheckarena(p, a);
}

void
poolcheck(Pool *p)
{
	p->lock(p);
	poolcheckl(p);
	p->unlock(p);
}

void
poolblockcheck(Pool *p, void *v)
{
	if(v == nil)
		return;

	p->lock(p);
	blockcheck(p, D2B(p, v));
	p->unlock(p);
}

static void
pooldumpl(Pool *p)
{
	Arena *a;

	p->print(p, "pool %p %s\n", p, p->name);
	for(a=p->arenalist; a; a=a->down)
		pooldumparena(p, a);
}

void
pooldump(Pool *p)
{
	p->lock(p);
	pooldumpl(p);
	p->unlock(p);
}

static void
pooldumparena(Pool *p, Arena *a)
{
	Bhdr *b;

	for(b=a; b->magic != ARENATAIL_MAGIC; b=B2NB(b))
		p->print(p, "(%p %.8lux %lud)", b, b->magic, b->size);
	p->print(p, "\n");
}

/*
 * mark the memory in such a way that we know who marked it
 * (via the signature) and we know where the marking started.
 */
static void
memmark(void *v, int sig, ulong size)
{
	uchar *p, *ep;
	ulong *lp, *elp;
	lp = v;
	elp = lp+size/4;
	while(lp < elp)
		*lp++ = (sig<<24) ^ (long)v;
	p = (uchar*)lp;
	ep = (uchar*)v+size;
	while(p<ep)
		*p++ = sig;
}