Subversion Repositories planix.SVN

#include	"u.h"

#include	"../port/lib.h"

#include	"mem.h"

#include	"pool.h"

#include	"dat.h"

#include	"fns.h"

#include	"error.h"

#define left	u.s.bhl

#define right	u.s.bhr

#define fwd	u.s.bhf

#define prev	u.s.bhv

#define parent	u.s.bhp

typedef struct Bhdr	Bhdr;

struct Bhdr {

	ulong	magic;

	ulong	size;

};

enum {

	NOT_MAGIC = 0xdeadfa11,

};

struct Pool

{

	char*	name;

	ulong	maxsize;

	int	quanta;

	int	chunk;

	ulong	cursize;

	ulong	arenasize;

	ulong	hw;

	Lock	l;

	Bhdr*	root;

	Bhdr*	chain;

	int	nalloc;

	int	nfree;

	int	nbrk;

	int	lastfree;

	void	(*move)(void*, void*);

};

struct

{

	int	n;

	Pool	pool[MAXPOOL];

	Lock	l;

} table = {

	2,

	{

		{ "Main",	 4*1024*1024, 31,  128*1024 },

		{ "Image",	 16*1024*1024, 31, 2*1024*1024 },

	}

};

Pool*	mainmem = &table.pool[0];

Pool*	imagmem = &table.pool[1];

int	poolcompact(Pool*);

Bhdr*

poolchain(Pool *p)

{

	return p->chain;

}

void

pooldel(Pool *p, Bhdr *t)

{

	Bhdr *s, *f, *rp, *q;

	if(t->parent == nil && p->root != t) {

		t->prev->fwd = t->fwd;

		t->fwd->prev = t->prev;

		return;

	}

	if(t->fwd != t) {

		f = t->fwd;

		s = t->parent;

		f->parent = s;

		if(s == nil)

			p->root = f;

		else {

			if(s->left == t)

				s->left = f;

			else

				s->right = f;

		}

		rp = t->left;

		f->left = rp;

		if(rp != nil)

			rp->parent = f;

		rp = t->right;

		f->right = rp;

		if(rp != nil)

			rp->parent = f;

		t->prev->fwd = t->fwd;

		t->fwd->prev = t->prev;

		return;

	}

	if(t->left == nil)

		rp = t->right;

	else {

		if(t->right == nil)

			rp = t->left;

		else {

			f = t;

			rp = t->right;

			s = rp->left;

			while(s != nil) {

				f = rp;

				rp = s;

				s = rp->left;

			}

			if(f != t) {

				s = rp->right;

				f->left = s;

				if(s != nil)

					s->parent = f;

				s = t->right;

				rp->right = s;

				if(s != nil)

					s->parent = rp;

			}

			s = t->left;

			rp->left = s;

			s->parent = rp;

		}

	}

	q = t->parent;

	if(q == nil)

		p->root = rp;

	else {

		if(t == q->left)

			q->left = rp;

		else

			q->right = rp;

	}

	if(rp != nil)

		rp->parent = q;

}

void

pooladd(Pool *p, Bhdr *q)

{

	int size;

	Bhdr *tp, *t;

	q->magic = MAGIC_F;

	q->left = nil;

	q->right = nil;

	q->parent = nil;

	q->fwd = q;

	q->prev = q;

	t = p->root;

	if(t == nil) {

		p->root = q;

		return;

	}

	size = q->size;

	tp = nil;

	while(t != nil) {

		if(size == t->size) {

			q->fwd = t->fwd;

			q->fwd->prev = q;

			q->prev = t;

			t->fwd = q;

			return;

		}

		tp = t;

		if(size < t->size)

			t = t->left;

		else

			t = t->right;

	}

	q->parent = tp;

	if(size < tp->size)

		tp->left = q;

	else

		tp->right = q;

}

void*

poolalloc(Pool *p, int size)

{

	Bhdr *q, *t;

	int alloc, ldr, ns, frag;

	if(size < 0 || size >= 1024*1024*1024)	/* for sanity and to avoid overflow */

		return nil;

	size = (size + BHDRSIZE + p->quanta) & ~(p->quanta);

	ilock(&p->l);

	p->nalloc++;

	t = p->root;

	q = nil;

	while(t) {

		if(t->size == size) {

			pooldel(p, t);

			t->magic = MAGIC_A;

			p->cursize += t->size;

			if(p->cursize > p->hw)

				p->hw = p->cursize;

			iunlock(&p->l);

			return B2D(t);

		}

		if(size < t->size) {

			q = t;

			t = t->left;

		}

		else

			t = t->right;

	}

	if(q != nil) {

		pooldel(p, q);

		q->magic = MAGIC_A;

		frag = q->size - size;

		if(frag < (size>>2)) {

			p->cursize += q->size;

			if(p->cursize > p->hw)

				p->hw = p->cursize;

			iunlock(&p->l);

			return B2D(q);

		}

		/* Split */

		ns = q->size - size;

		q->size = size;

		B2T(q)->hdr = q;

		t = B2NB(q);

		t->size = ns;

		B2T(t)->hdr = t;

		pooladd(p, t);

		p->cursize += q->size;

		if(p->cursize > p->hw)

			p->hw = p->cursize;

		iunlock(&p->l);

		return B2D(q);

	}

	ns = p->chunk;

	if(size > ns)

		ns = size;

	ldr = p->quanta+1;

	alloc = ns+ldr+sizeof(t->magic);

	p->arenasize += alloc;

	if(p->arenasize > p->maxsize) {

		p->arenasize -= alloc;

		if(poolcompact(p)) {

			iunlock(&p->l);

			return poolalloc(p, size);

		}

		iunlock(&p->l);

		print("%s arena too large: size %d cursize %lud arenasize %lud maxsize %lud\n",

			 p->name, size, p->cursize, p->arenasize, p->maxsize);

		return nil;

	}

	p->nbrk++;

	t = xalloc(alloc);

	if(t == nil) {

		iunlock(&p->l);

		return nil;

	}

	t->magic = MAGIC_E;		/* Make a leader */

	t->size = ldr;

	t->csize = ns+ldr;

	t->clink = p->chain;

	p->chain = t;

	B2T(t)->hdr = t;

	t = B2NB(t);

	t->magic = MAGIC_A;		/* Make the block we are going to return */

	t->size = size;

	B2T(t)->hdr = t;

	q = t;

	ns -= size;			/* Free the rest */

	if(ns > 0) {

		q = B2NB(t);

		q->size = ns;

		B2T(q)->hdr = q;

		pooladd(p, q);

	}

	B2NB(q)->magic = MAGIC_E;	/* Mark the end of the chunk */

	p->cursize += t->size;

	if(p->cursize > p->hw)

		p->hw = p->cursize;

	iunlock(&p->l);

	return B2D(t);

}

void

poolfree(Pool *p, void *v)

{

	Bhdr *b, *c;

	D2B(b, v);

	ilock(&p->l);

	p->nfree++;

	p->cursize -= b->size;

	c = B2NB(b);

	if(c->magic == MAGIC_F) {	/* Join forward */

		pooldel(p, c);

		c->magic = 0;

		b->size += c->size;

		B2T(b)->hdr = b;

	}

	c = B2PT(b)->hdr;

	if(c->magic == MAGIC_F) {	/* Join backward */

		pooldel(p, c);

		b->magic = 0;

		c->size += b->size;

		b = c;

		B2T(b)->hdr = b;

	}

	pooladd(p, b);

	iunlock(&p->l);

}

int

poolread(char *va, int count, ulong offset)

{

	Pool *p;

	int n, i, signed_off;

	n = 0;

	signed_off = offset;

	for(i = 0; i < table.n; i++) {

		p = &table.pool[i];

		n += snprint(va+n, count-n, "%11lud %11lud %11lud %11d %11d %11d %s\n",

			p->cursize,

			p->maxsize,

			p->hw,

			p->nalloc,

			p->nfree,

			p->nbrk,

			p->name);

		if(signed_off > 0) {

			signed_off -= n;

			if(signed_off < 0) {

				memmove(va, va+n+signed_off, -signed_off);

				n = -signed_off;

			}

			else

				n = 0;

		}

	}

	return n;

}

Lock pcxlock;

struct {

	ulong	n;

	ulong	pc;

} pcx[1024];

static void

remember(ulong pc, void *v)

{

	Bhdr *b;

	int i;

	if(v == nil)

		return;

	D2B(b, v);

	if((b->size>>5) != 2)

		return;

	ilock(&pcxlock);

	B2T(b)->pad = 0;

	for(i = 0; i < 1024; i++)

		if(pcx[i].pc == pc || pcx[i].pc == 0){

			pcx[i].pc = pc;

			pcx[i].n++;

			B2T(b)->pad = i;

			break;

		}

	iunlock(&pcxlock);

}

static void

forget(void *v)

{

	Bhdr *b;

	if(v == nil)

		return;

	D2B(b, v);

	if((b->size>>5) != 2)

		return;

	ilock(&pcxlock);

	pcx[B2T(b)->pad].n--;

	iunlock(&pcxlock);

}

void*

malloc(ulong size)

{

	void *v;

	v = poolalloc(mainmem, size);

remember(getcallerpc(&size), v);

	if(v != nil)

		memset(v, 0, size);

	return v;

}

void*

smalloc(ulong size)

{

	void *v;

	for(;;) {

		v = poolalloc(mainmem, size);

remember(getcallerpc(&size), v);

		if(v != nil)

			break;

		tsleep(&up->sleep, return0, 0, 100);

	}

	memset(v, 0, size);

	return v;

}

void*

mallocz(ulong size, int clr)

{

	void *v;

	v = poolalloc(mainmem, size);

remember(getcallerpc(&size), v);

	if(clr && v != nil)

		memset(v, 0, size);

	return v;

}

void

free(void *v)

{

	Bhdr *b;

	if(v != nil) {

forget(v);

		D2B(b, v);

		poolfree(mainmem, v);

	}

}

void*

realloc(void *v, ulong size)

{

	Bhdr *b;

	void *nv;

	int osize;

	if(v == nil)

		return malloc(size);

	D2B(b, v);

	osize = b->size - BHDRSIZE;

	if(osize >= size)

		return v;

	nv = poolalloc(mainmem, size);

remember(getcallerpc(&v), nv);

	if(nv != nil) {

		memmove(nv, v, osize);

		free(v);

	}

	return nv;

}

int

msize(void *v)

{

	Bhdr *b;

	D2B(b, v);

	return b->size - BHDRSIZE;

}

void*

calloc(ulong n, ulong szelem)

{

	return malloc(n*szelem);

}

/*

void

pooldump(Bhdr *b, int d, int c)

{

	Bhdr *t;

	if(b == nil)

		return;

	print("%.8lux %.8lux %.8lux %c %4d %d (f %.8lux p %.8lux)\n",

		b, b->left, b->right, c, d, b->size, b->fwd, b->prev);

	d++;

	for(t = b->fwd; t != b; t = t->fwd)

		print("\t%.8lux %.8lux %.8lux\n", t, t->prev, t->fwd);

	pooldump(b->left, d, 'l');

	pooldump(b->right, d, 'r');

}

void

poolshow(void)

{

	int i;

	for(i = 0; i < table.n; i++) {

		print("Arena: %s root=%.8lux\n", table.pool[i].name, table.pool[i].root);

		pooldump(table.pool[i].root, 0, 'R');

	}

}

*/

void

poolsummary(void)

{

	int i;

	for(i = 0; i < table.n; i++)

		print("Arena: %s cursize=%lud; maxsize=%lud\n",

			table.pool[i].name,

			table.pool[i].cursize,

			table.pool[i].maxsize);

}

/*

void

pooldump(Pool *p)

{

	Bhdr *b, *base, *limit, *ptr;

	b = p->chain;

	if(b == nil)

		return;

	base = b;

	ptr = b;

	limit = B2LIMIT(b);

	while(base != nil) {

		print("\tbase #%.8lux ptr #%.8lux", base, ptr);

		if(ptr->magic == MAGIC_A)

			print("\tA%.5d\n", ptr->size);

		else if(ptr->magic == MAGIC_E)

			print("\tE\tL#%.8lux\tS#%.8lux\n", ptr->clink, ptr->csize);

		else

			print("\tF%.5d\tL#%.8lux\tR#%.8lux\tF#%.8lux\tP#%.8lux\tT#%.8lux\n",

				ptr->size, ptr->left, ptr->right, ptr->fwd, ptr->prev, ptr->parent);

		ptr = B2NB(ptr);

		if(ptr >= limit) {

			print("link to #%.8lux\n", base->clink);

			base = base->clink;

			if(base == nil)

				break;

			ptr = base;

			limit = B2LIMIT(base);

		}

	}

	return;

}

*/

void

poolsetcompact(Pool *p, void (*move)(void*, void*))

{

	p->move = move;

}

void

poolsetparam(char *name, ulong maxsize, int quanta, int chunk)

{

	Pool *p;

	int i;

	for(i=0; i<table.n; i++){

		p = &table.pool[i];

		if(strcmp(name, p->name) == 0){

			if(maxsize)

				p->maxsize = maxsize;

			if(quanta)

				p->quanta = quanta;

			if(chunk)

				p->chunk = chunk;

			return;

		}

	}

}

int

poolcompact(Pool *pool)

{

	Bhdr *base, *limit, *ptr, *end, *next;

	int compacted, recov, nb;

	if(pool->move == nil || pool->lastfree == pool->nfree)

		return 0;

	pool->lastfree = pool->nfree;

	base = pool->chain;

	ptr = B2NB(base);	/* First Block in arena has clink */

	limit = B2LIMIT(base);

	compacted = 0;

	pool->root = nil;

	end = ptr;

	recov = 0;

	while(base != nil) {

		next = B2NB(ptr);

		if(ptr->magic == MAGIC_A) {

			if(ptr != end) {

				memmove(end, ptr, ptr->size);

				pool->move(B2D(ptr), B2D(end));

				recov = (uchar*)ptr - (uchar*)end;

				compacted = 1;

			}

			end = B2NB(end);

		}

		if(next >= limit) {

			nb = (uchar*)limit - (uchar*)end;

			//print("recovered %d bytes\n", recov);

			//print("%d bytes at end\n", nb);

			USED(recov);

			if(nb > 0){

				if(nb < pool->quanta+1)

					panic("poolcompact: leftover too small\n");

				end->size = nb;

				pooladd(pool, end);

			}

			base = base->clink;

			if(base == nil)

				break;

			ptr = B2NB(base);

			end = ptr;	/* could do better by copying between chains */

			limit = B2LIMIT(base);

			recov = 0;

		} else

			ptr = next;

	}

	return compacted;

}

int

recur(Bhdr *t)

{

	if(t == 0)

		return 1;

	if((uintptr)t < KZERO || (uintptr)t - KZERO > 0x10000000)

		return 0;

	return recur(t->right) && recur(t->left);

}