plan 9 kernel history: overview | file list | diff list

1992/0707/port/alloc.c (diff list | history)

1992/0618/sys/src/9/port/alloc.c:3,20 – 1992/0619/sys/src/9/port/alloc.c:3,27 (short | long)
1992/0618    
#include	"mem.h" 
#include	"dat.h" 
#include	"fns.h" 
#define	nil	((void*)0) 
#define datoff	((int)&((Xhdr*)0)->data)
1992/0619    
#define	nil		((void*)0) 
#define datoff		((ulong)&((Xhdr*)0)->data) 
#define bdatoff		((ulong)&((Bucket*)0)->data)
1992/0618    
enum 
{ 
	Nhole	= 128, 
	Magic	= 0xDeadBabe,
1992/0619    
	Maxpow		= 16, 
	Nhole		= 128, 
	Magichole	= 0xDeadBabe, 
	Magic2n		= 0xBadC0c0a,
1992/0618    
}; 
 
typedef struct Hole Hole; 
typedef struct Xalloc Xalloc; 
typedef struct Xhdr Xhdr;
1992/0619    
typedef struct Bucket Bucket; 
typedef struct Arena Arena;
1992/0618    
struct Hole 
{ 
	ulong	addr;
1992/0618/sys/src/9/port/alloc.c:38,99 – 1992/0619/sys/src/9/port/alloc.c:45,139
1992/0618    
	Hole	*table; 
}; 
 
Xalloc	xlists;
1992/0619    
struct Bucket 
{ 
	int	size; 
	int	magic; 
	Bucket	*next; 
	char	data[1]; 
};
1992/0618    
1992/0619    
struct Arena 
{ 
	Lock; 
	Bucket	*btab[Maxpow];	 
}; 
 
static Arena	arena; 
static Xalloc	xlists; 
 
void* 
ialloc(ulong size, int align) 
{ 
	ulong p; 
 
	if(align) { 
		size += BY2PG; 
		p = (ulong)xalloc(size); 
		p += BY2PG; 
		p &= ~(BY2PG-1); 
		return (void*)p; 
	} 
 
	return xalloc(size); 
} 
 
void* 
iallocspan(ulong size, int quanta, ulong span) 
{ 
	return ialloc(size, quanta); 
}
1992/0618    
void 
xinit(void) 
{
1992/0619    
	ulong ktop;
1992/0618    
	Hole *h, *eh;
1992/0619    
	int up, np0, np1;
1992/0618    
 
	eh = &xlists.hole[Nhole-1]; 
	for(h = xlists.hole; h < eh; h++) 
		h->link = h+1; 
 
	xlists.flist = h; 
}
1992/0619    
	xlists.flist = xlists.hole;
1992/0618    
 
void 
xhole(ulong addr, ulong size) 
{ 
	Hole *h, **l;
1992/0619    
	ktop = PGROUND((ulong)end); 
	ktop = PADDR(ktop); 
	conf.npage0 -= ktop/BY2PG; 
	conf.base0 += ktop;
1992/0618    
 
	lock(&xlists); 
	l = &xlists.table; 
	for(h = *l; h; h = h->link) { 
		if(h->top == addr) { 
			h->size += size; 
			h->top = h->addr+h->size; 
			unlock(&xlists); 
			return; 
		} 
		if(h->addr > addr) 
			break; 
		l = &h->link; 
	}
1992/0619    
	up = conf.upages; 
	np1 = up; 
	if(np1 > conf.npage1) 
		np1 = conf.npage1;
1992/0618    
 
	if(xlists.flist == nil) { 
		print("xfree: no free holes, leaked %d bytes\n", size); 
		unlock(&xlists); 
		return; 
	}
1992/0619    
	palloc.p1 = conf.base1; 
	conf.base1 += np1*BY2PG; 
	conf.npage1 -= np1; 
	xhole(conf.base1, conf.npage1*BY2PG); 
	up -= np1;
1992/0618    
 
	h = xlists.flist; 
	xlists.flist = h->link; 
	h->addr = addr; 
	h->top = addr+size; 
	h->size = size; 
	h->link = *l; 
	*l = h; 
	unlock(&xlists);
1992/0619    
	np0 = up; 
	if(np0 > conf.npage0) 
		np0 = conf.npage0; 
 
	palloc.p0 = conf.base0; 
	conf.base0 += np0*BY2PG; 
	conf.npage0 -= np0; 
	xhole(conf.base0, conf.npage0*BY2PG); 
 
	palloc.np0 = np0; 
	palloc.np1 = np1;
1992/0618    
} 
 
void* 
xalloc(ulong size) 
{ 
	Hole *h, **l; 
	Xhdr *p;
1992/0619    
	Hole *h, **l;
1992/0618    
 
	size += sizeof(Xhdr);
1992/0619    
	size += BY2WD + sizeof(Xhdr); 
	size &= ~(BY2WD-1);
1992/0618    
 
	lock(&xlists); 
	l = &xlists.table;
1992/0618/sys/src/9/port/alloc.c:107,113 – 1992/0619/sys/src/9/port/alloc.c:147,155
1992/0618    
				h->link = xlists.flist; 
				xlists.flist = h; 
			} 
			p->magix = Magic;
1992/0619    
			p = KADDR(p); 
			memset(p, 0, size); 
			p->magix = Magichole;
1992/0618    
			p->size = size; 
			unlock(&xlists); 
			return p->data;
1992/0618/sys/src/9/port/alloc.c:124,136 – 1992/0619/sys/src/9/port/alloc.c:166,232
1992/0618    
	Xhdr *x; 
 
	x = (Xhdr*)((ulong)p - datoff); 
	if(x->magix != Magic)
1992/0619    
	if(x->magix != Magichole)
1992/0618    
		panic("xfree"); 
 
	xhole((ulong)x, x->size);
1992/0619    
	xhole(PADDR(x), x->size);
1992/0618    
} 
 
void
1992/0619    
xhole(ulong addr, ulong size) 
{ 
	ulong top; 
	Hole *h, *c, **l; 
 
	if(size == 0) 
		return; 
 
	top = addr + size; 
	lock(&xlists); 
	l = &xlists.table; 
	for(h = *l; h; h = h->link) { 
		if(h->top == addr) { 
			h->size += size; 
			h->top = h->addr+h->size; 
			c = h->link; 
			if(c && h->top == c->addr) { 
				h->top += c->size; 
				h->size += c->size; 
				h->link = c->link; 
				c->link = xlists.flist; 
				xlists.flist = c; 
			} 
			unlock(&xlists); 
			return; 
		} 
		if(h->addr > addr) 
			break; 
		l = &h->link; 
	} 
	if(h && top == h->addr) { 
		h->addr -= size; 
		h->size += size; 
		unlock(&xlists); 
		return; 
	} 
 
	if(xlists.flist == nil) { 
		unlock(&xlists); 
		print("xfree: no free holes, leaked %d bytes\n", size); 
		return; 
	} 
 
	h = xlists.flist; 
	xlists.flist = h->link; 
	h->addr = addr; 
	h->top = top; 
	h->size = size; 
	h->link = *l; 
	*l = h; 
	unlock(&xlists); 
} 
 
void
1992/0618    
xsummary(void) 
{ 
	int i;
1992/0618/sys/src/9/port/alloc.c:143,150 – 1992/0619/sys/src/9/port/alloc.c:239,312
1992/0618    
	print("%d holes free\n", i); 
	i = 0; 
	for(h = xlists.table; h; h = h->link) { 
		print("%lux %lux %d\n", h->addr, h->top, h->size);
1992/0619    
		print("%.8lux %.8lux %d\n", h->addr, h->top, h->size);
1992/0618    
		i += h->size; 
	} 
	print("%d bytes free\n", i);
1992/0619    
} 
 
void* 
malloc(ulong size) 
{ 
	int pow; 
	Bucket *bp; 
 
	for(pow = 1; pow < Maxpow; pow++) 
		if(size <= (1<<pow)) 
			goto good; 
 
	return nil; 
good: 
	/* Allocate off this list */ 
	lock(&arena); 
	bp = arena.btab[pow]; 
	if(bp) { 
		arena.btab[pow] = bp->next; 
		unlock(&arena); 
 
		if(bp->magic != 0) 
			panic("malloc"); 
 
		bp->magic = Magic2n; 
 
		memset(bp->data, 0,  size); 
		return  bp->data; 
	} 
	unlock(&arena); 
	size = sizeof(Bucket)+(1<<pow); 
	bp = xalloc(size); 
	if(bp == nil) 
		return nil; 
 
	bp->size = pow; 
	bp->magic = Magic2n; 
	return bp->data; 
} 
 
void* 
smalloc(ulong size) 
{ 
	void *p; 
 
	p = malloc(size); 
	if(p == nil) 
		panic("smalloc should sleep"); 
	return p; 
} 
 
void 
free(void *ptr) 
{ 
	Bucket *bp, **l; 
 
	bp = (Bucket*)((ulong)ptr - bdatoff); 
	if(bp->magic != Magic2n) 
		panic("free"); 
 
	bp->magic = 0; 
	lock(&arena); 
	l = &arena.btab[bp->size]; 
	bp->next = *l; 
	*l = bp; 
	unlock(&arena);
1992/0618    
}
1992/0619/sys/src/9/port/alloc.c:13,19 – 1992/0620/sys/src/9/port/alloc.c:13,19 (short | long)
1992/0619    
	Maxpow		= 16, 
	Nhole		= 128, 
	Magichole	= 0xDeadBabe, 
	Magic2n		= 0xBadC0c0a,
1992/0620    
	Magic2n		= 0xFeedBeef,
1992/0618    
}; 
 
typedef struct Hole Hole;
1992/0619/sys/src/9/port/alloc.c:56,62 – 1992/0620/sys/src/9/port/alloc.c:56,63
1992/0619    
struct Arena 
{ 
	Lock; 
	Bucket	*btab[Maxpow];
1992/0620    
	Bucket	*btab[Maxpow]; 
	int	nbuck[Maxpow];
1992/0619    
}; 
 
static Arena	arena;
1992/0619/sys/src/9/port/alloc.c:226,250 – 1992/0620/sys/src/9/port/alloc.c:227,232
1992/0619    
	unlock(&xlists); 
} 
 
void
1992/0618    
xsummary(void) 
{ 
	int i; 
	Hole *h; 
                 
	i = 0; 
	for(h = xlists.flist; h; h = h->link) 
		i++; 
                 
	print("%d holes free\n", i); 
	i = 0; 
	for(h = xlists.table; h; h = h->link) {
1992/0619    
		print("%.8lux %.8lux %d\n", h->addr, h->top, h->size);
1992/0618    
		i += h->size; 
	} 
	print("%d bytes free\n", i);
1992/0619    
} 
                 
void* 
malloc(ulong size) 
{
1992/0619/sys/src/9/port/alloc.c:251,257 – 1992/0620/sys/src/9/port/alloc.c:233,239
1992/0619    
	int pow; 
	Bucket *bp; 
 
	for(pow = 1; pow < Maxpow; pow++)
1992/0620    
	for(pow = 3; pow < Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow)) 
			goto good;
1992/0619/sys/src/9/port/alloc.c:272,277 – 1992/0620/sys/src/9/port/alloc.c:254,260
1992/0619    
		memset(bp->data, 0,  size); 
		return  bp->data; 
	}
1992/0620    
	arena.nbuck[pow]++;
1992/0619    
	unlock(&arena); 
	size = sizeof(Bucket)+(1<<pow); 
	bp = xalloc(size);
1992/0619/sys/src/9/port/alloc.c:309,312 – 1992/0620/sys/src/9/port/alloc.c:292,323
1992/0619    
	bp->next = *l; 
	*l = bp; 
	unlock(&arena);
1992/0620    
} 
 
void 
xsummary(void) 
{ 
	Hole *h; 
	Bucket *k; 
	int i, nfree; 
 
	i = 0; 
	for(h = xlists.flist; h; h = h->link) 
		i++; 
 
	print("%d holes free\n", i); 
	i = 0; 
	for(h = xlists.table; h; h = h->link) { 
		print("%.8lux %.8lux %d\n", h->addr, h->top, h->size); 
		i += h->size; 
	} 
	print("%d bytes free\n", i); 
	for(i = 3; i < Maxpow; i++) { 
		if(arena.btab[i] == 0 && arena.nbuck[i] == 0) 
			continue; 
		nfree = 0; 
		for(k = arena.btab[i]; k; k = k->next) 
			nfree++; 
		print("%8d %4d %4d\n", 1<<i, arena.nbuck[i], nfree); 
	}
1992/0618    
}
1992/0620/sys/src/9/port/alloc.c:4,12 – 1992/0621/sys/src/9/port/alloc.c:4,21 (short | long)
1992/0618    
#include	"dat.h" 
#include	"fns.h"
1992/0621    
/* 
 * Plan 9 has two kernel allocators, the x... routines provide a first 
 * fit hole allocator which should be used for permanent or large structures. 
 * Routines are provided to allocate aligned memory which does not cross 
 * arbitrary 2^n boundaries. A second allocator malloc, smalloc, free is 
 * a 2n bucket allocator which steals from the x routines. This should 
 * be used for small frequently used structures. 
 */
1992/0619    
#define	nil		((void*)0) 
#define datoff		((ulong)&((Xhdr*)0)->data) 
#define bdatoff		((ulong)&((Bucket*)0)->data)
1992/0621    
#define datoff		((ulong)((Xhdr*)0)->data) 
#define bdatoff		((ulong)((Bucket*)0)->data)
1992/0619    
1992/0618    
enum 
{
1992/0620/sys/src/9/port/alloc.c:14,19 – 1992/0621/sys/src/9/port/alloc.c:23,29
1992/0619    
	Nhole		= 128, 
	Magichole	= 0xDeadBabe,
1992/0620    
	Magic2n		= 0xFeedBeef,
1992/0621    
	Spanlist	= 64,
1992/0618    
}; 
 
typedef struct Hole Hole;
1992/0620/sys/src/9/port/alloc.c:75,90 – 1992/0621/sys/src/9/port/alloc.c:85,93
1992/0619    
		p &= ~(BY2PG-1); 
		return (void*)p; 
	} 
                 
	return xalloc(size);
1992/0621    
	return xalloc(size);;
1992/0619    
} 
 
void* 
iallocspan(ulong size, int quanta, ulong span) 
{ 
	return ialloc(size, quanta); 
} 
                 
1992/0618    
void 
xinit(void) 
{
1992/0620/sys/src/9/port/alloc.c:125,130 – 1992/0621/sys/src/9/port/alloc.c:128,163
1992/0619    
 
	palloc.np0 = np0; 
	palloc.np1 = np1;
1992/0621    
} 
 
/* 
 * NB. spanalloc memory will cause a panic if free'd 
 */ 
void* 
xspanalloc(ulong size, int align, ulong span) 
{ 
	int i, j; 
	ulong a, p; 
	ulong ptr[Spanlist]; 
 
	span = ~(span-1); 
	for(i = 0; i < Spanlist; i++) { 
		p = (ulong)xalloc(size+align); 
		if(p == 0) 
			panic("xspanalloc: size %d align %d span %d", size, align, span); 
 
		a = p+align; 
		a &= ~(align-1); 
		if((a&span) == ((a+size)&span)) { 
			for(j = 0; j < i; j++) 
				xfree((void*)ptr[j]); 
 
			return (void*)a; 
		} 
		ptr[i] = p; 
	} 
	panic("xspanalloc: spanlist");		 
	return 0;
1992/0618    
} 
 
void*
1992/0621/sys/src/9/port/alloc.c:73,93 – 1992/0622/sys/src/9/port/alloc.c:73,78 (short | long)
1992/0619    
static Arena	arena; 
static Xalloc	xlists; 
 
void* 
ialloc(ulong size, int align) 
{ 
	ulong p; 
                 
	if(align) { 
		size += BY2PG; 
		p = (ulong)xalloc(size); 
		p += BY2PG; 
		p &= ~(BY2PG-1); 
		return (void*)p; 
	}
1992/0621    
	return xalloc(size);;
1992/0619    
} 
                 
1992/0618    
void 
xinit(void) 
{
1992/0621/sys/src/9/port/alloc.c:305,312 – 1992/0622/sys/src/9/port/alloc.c:290,300
1992/0619    
	void *p; 
 
	p = malloc(size); 
	if(p == nil)
1992/0622    
	if(p == nil) { 
		print("asking for %d\n", size); 
		xsummary();
1992/0619    
		panic("smalloc should sleep");
1992/0622    
	}
1992/0619    
	return p; 
}
1992/0622/sys/src/9/port/alloc.c:166,176 – 1992/0623/sys/src/9/port/alloc.c:166,176 (short | long)
1992/0618    
				h->link = xlists.flist; 
				xlists.flist = h; 
			}
1992/0623    
			unlock(&xlists);
1992/0619    
			p = KADDR(p); 
			memset(p, 0, size); 
			p->magix = Magichole;
1992/0618    
			p->size = size; 
			unlock(&xlists); 
			return p->data; 
		} 
		l = &h->link;
1992/0622/sys/src/9/port/alloc.c:296,301 – 1992/0623/sys/src/9/port/alloc.c:296,312
1992/0619    
		panic("smalloc should sleep");
1992/0622    
	}
1992/0619    
	return p;
1992/0623    
} 
 
int 
msize(void *ptr) 
{ 
	Bucket *bp; 
 
	bp = (Bucket*)((ulong)ptr - bdatoff); 
	if(bp->magic != Magic2n) 
		panic("msize"); 
	return 1<<bp->size;
1992/0619    
} 
 
void
1992/0623/sys/src/9/port/alloc.c:68,73 – 1992/0625/sys/src/9/port/alloc.c:68,75 (short | long)
1992/0619    
	Lock;
1992/0620    
	Bucket	*btab[Maxpow]; 
	int	nbuck[Maxpow];
1992/0625    
	QLock	rq; 
	Rendez	r;
1992/0619    
}; 
 
static Arena	arena;
1992/0623/sys/src/9/port/alloc.c:100,105 – 1992/0625/sys/src/9/port/alloc.c:102,108
1992/0619    
	conf.base1 += np1*BY2PG; 
	conf.npage1 -= np1; 
	xhole(conf.base1, conf.npage1*BY2PG);
1992/0625    
	conf.npage1 = conf.base1+(conf.npage1*BY2PG);
1992/0619    
	up -= np1;
1992/0618    
1992/0619    
	np0 = up;
1992/0623/sys/src/9/port/alloc.c:110,118 – 1992/0625/sys/src/9/port/alloc.c:113,127
1992/0619    
	conf.base0 += np0*BY2PG; 
	conf.npage0 -= np0; 
	xhole(conf.base0, conf.npage0*BY2PG);
1992/0625    
	conf.npage0 = conf.base0+(conf.npage0*BY2PG);
1992/0619    
 
	palloc.np0 = np0; 
	palloc.np1 = np1;
1992/0625    
	/* Save the bounds of kernel alloc memory for kernel mmu mapping (NeXT) */ 
	conf.base0 = (ulong)KADDR(conf.base0); 
	conf.base1 = (ulong)KADDR(conf.base1); 
	conf.npage0 = (ulong)KADDR(conf.npage0); 
	conf.npage1 = (ulong)KADDR(conf.npage1);
1992/0621    
} 
 
/*
1992/0623/sys/src/9/port/alloc.c:287,299 – 1992/0625/sys/src/9/port/alloc.c:296,317
1992/0619    
void* 
smalloc(ulong size) 
{
1992/0625    
	char *s;
1992/0619    
	void *p; 
 
	p = malloc(size);
1992/0622    
	if(p == nil) { 
		print("asking for %d\n", size); 
		xsummary();
1992/0619    
		panic("smalloc should sleep");
1992/0625    
	for(;;) { 
		p = malloc(size); 
		if(p != nil) 
			return p; 
		s = u->p->psstate; 
		u->p->psstate = "Malloc"; 
		qlock(&arena.rq); 
		while(waserror()) 
			; 
		sleep(&arena.r, return0, nil); 
		poperror(); 
		qunlock(&arena.rq); 
		u->p->psstate = s;
1992/0622    
	}
1992/0619    
	return p;
1992/0623    
}
1992/0623/sys/src/9/port/alloc.c:324,329 – 1992/0625/sys/src/9/port/alloc.c:342,349
1992/0619    
	bp->next = *l; 
	*l = bp; 
	unlock(&arena);
1992/0625    
	if(arena.r.p) 
		wakeup(&arena.r);
1992/0620    
} 
 
void
1992/0625/sys/src/9/port/alloc.c:3,8 – 1992/0707/sys/src/9/port/alloc.c:3,9 (short | long)
1992/0618    
#include	"mem.h" 
#include	"dat.h" 
#include	"fns.h"
1992/0707    
#include	"error.h"
1992/0618    
1992/0621    
/* 
 * Plan 9 has two kernel allocators, the x... routines provide a first
1992/0625/sys/src/9/port/alloc.c:19,25 – 1992/0707/sys/src/9/port/alloc.c:20,26
1992/0619    
1992/0618    
enum 
{
1992/0619    
	Maxpow		= 16,
1992/0707    
	Maxpow		= 18,
1992/0619    
	Nhole		= 128, 
	Magichole	= 0xDeadBabe,
1992/0620    
	Magic2n		= 0xFeedBeef,
1992/0625/sys/src/9/port/alloc.c:260,266 – 1992/0707/sys/src/9/port/alloc.c:261,267
1992/0619    
	int pow; 
	Bucket *bp;
1992/0620    
	for(pow = 3; pow < Maxpow; pow++)
1992/0707    
	for(pow = 3; pow <= Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow)) 
			goto good;
1992/0625/sys/src/9/port/alloc.c:298,305 – 1992/0707/sys/src/9/port/alloc.c:299,307
1992/0619    
{
1992/0625    
	char *s;
1992/0619    
	void *p;
1992/0707    
	int attempt;
1992/0619    
1992/0625    
	for(;;) {
1992/0707    
	for(attempt = 0; attempt < 1000; attempt++) {
1992/0625    
		p = malloc(size); 
		if(p != nil) 
			return p;
1992/0625/sys/src/9/port/alloc.c:313,319 – 1992/0707/sys/src/9/port/alloc.c:315,322
1992/0625    
		qunlock(&arena.rq); 
		u->p->psstate = s;
1992/0622    
	}
1992/0619    
	return p;
1992/0707    
	pexit(Enomem, 1); 
	return 0;
1992/0623    
} 
 
int
1992/0707/sys/src/9/port/alloc.c:132,156 – 1992/0708/sys/src/9/port/alloc.c:132,160 (short | long)
1992/0621    
xspanalloc(ulong size, int align, ulong span) 
{ 
	int i, j; 
	ulong a, p;
1992/0708    
	ulong a, p, sinc;
1992/0621    
	ulong ptr[Spanlist];
1992/0708    
	sinc = span/8;
1992/0621    
	span = ~(span-1); 
	for(i = 0; i < Spanlist; i++) { 
		p = (ulong)xalloc(size+align); 
		if(p == 0) 
			panic("xspanalloc: size %d align %d span %d", size, align, span);
1992/0708    
			panic("xspanalloc: size %d align %d span %lux", size, align, span);
1992/0621    
 
		a = p+align; 
		a &= ~(align-1); 
		if((a&span) == ((a+size)&span)) { 
			for(j = 0; j < i; j++) 
				xfree((void*)ptr[j]);
1992/0708    
				if(ptr[j]) 
					xfree((void*)ptr[j]);
1992/0621    
 
			return (void*)a; 
		} 
		ptr[i] = p;
1992/0708    
		xfree((void*)p); 
		ptr[i] = (ulong)xalloc(sinc);
1992/0621    
	}
1992/0708    
	USED(sinc);
1992/0621    
	panic("xspanalloc: spanlist");		 
	return 0;
1992/0618    
}
1992/0708/sys/src/9/port/alloc.c:79,85 – 1992/0715/sys/src/9/port/alloc.c:79,84 (short | long)
1992/0618    
void 
xinit(void) 
{
1992/0619    
	ulong ktop;
1992/0618    
	Hole *h, *eh;
1992/0619    
	int up, np0, np1;
1992/0618    
1992/0708/sys/src/9/port/alloc.c:88,98 – 1992/0715/sys/src/9/port/alloc.c:87,92
1992/0618    
		h->link = h+1;
1992/0619    
	xlists.flist = xlists.hole;
1992/0618    
                 
1992/0619    
	ktop = PGROUND((ulong)end); 
	ktop = PADDR(ktop); 
	conf.npage0 -= ktop/BY2PG; 
	conf.base0 += ktop;
1992/0618    
1992/0619    
	up = conf.upages; 
	np1 = up;
1992/0715/sys/src/9/port/alloc.c:21,26 – 1992/0720/sys/src/9/port/alloc.c:21,27 (short | long)
1992/0618    
enum 
{
1992/0707    
	Maxpow		= 18,
1992/0720    
	CUTOFF		= 12,
1992/0619    
	Nhole		= 128, 
	Magichole	= 0xDeadBabe,
1992/0620    
	Magic2n		= 0xFeedBeef,
1992/0715/sys/src/9/port/alloc.c:134,140 – 1992/0720/sys/src/9/port/alloc.c:135,141
1992/0621    
	for(i = 0; i < Spanlist; i++) { 
		p = (ulong)xalloc(size+align); 
		if(p == 0)
1992/0708    
			panic("xspanalloc: size %d align %d span %lux", size, align, span);
1992/0720    
			panic("xspanalloc: %d %d %lux", size, align, span);
1992/0621    
 
		a = p+align; 
		a &= ~(align-1);
1992/0715/sys/src/9/port/alloc.c:256,263 – 1992/0720/sys/src/9/port/alloc.c:257,265
1992/0619    
void* 
malloc(ulong size) 
{ 
	int pow; 
	Bucket *bp;
1992/0720    
	ulong next; 
	int pow, n; 
	Bucket *bp, *nbp;
1992/0619    
1992/0707    
	for(pow = 3; pow <= Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow))
1992/0715/sys/src/9/port/alloc.c:280,291 – 1992/0720/sys/src/9/port/alloc.c:282,318
1992/0619    
		memset(bp->data, 0,  size); 
		return  bp->data; 
	}
1992/0620    
	arena.nbuck[pow]++;
1992/0619    
	unlock(&arena);
1992/0720    
1992/0619    
	size = sizeof(Bucket)+(1<<pow); 
	bp = xalloc(size); 
	if(bp == nil) 
		return nil;
1992/0720    
	size += 3; 
	size &= ~3; 
 
	if(pow < CUTOFF) { 
		n = (CUTOFF-pow)+2; 
		bp = xalloc(size*n); 
		if(bp == nil) 
			return nil; 
 
		next = (ulong)bp+size; 
		nbp = (Bucket*)next; 
		lock(&arena); 
		arena.btab[pow] = nbp; 
		arena.nbuck[pow] += n; 
		for(n -= 2; n; n--) { 
			next = (ulong)nbp+size; 
			nbp->next = (Bucket*)next; 
			nbp->size = pow; 
			nbp = nbp->next; 
		} 
		nbp->size = pow; 
		unlock(&arena); 
	} 
	else { 
		bp = xalloc(size); 
		if(bp == nil) 
			return nil; 
	}
1992/0619    
 
	bp->size = pow; 
	bp->magic = Magic2n;
1992/0720/sys/src/9/port/alloc.c:113,119 – 1992/0726/sys/src/9/port/alloc.c:113,119 (short | long)
1992/0619    
 
	palloc.np0 = np0; 
	palloc.np1 = np1;
1992/0625    
	/* Save the bounds of kernel alloc memory for kernel mmu mapping (NeXT) */
1992/0726    
	/* Save the bounds of kernel alloc memory for kernel mmu mapping */
1992/0625    
	conf.base0 = (ulong)KADDR(conf.base0); 
	conf.base1 = (ulong)KADDR(conf.base1); 
	conf.npage0 = (ulong)KADDR(conf.npage0);
1992/0726/sys/src/9/port/alloc.c:130,141 – 1992/0729/sys/src/9/port/alloc.c:130,141 (short | long)
1992/0708    
	ulong a, p, sinc;
1992/0621    
	ulong ptr[Spanlist];
1992/0708    
	sinc = span/8;
1992/0729    
	sinc = size/8;
1992/0621    
	span = ~(span-1); 
	for(i = 0; i < Spanlist; i++) { 
		p = (ulong)xalloc(size+align); 
		if(p == 0)
1992/0720    
			panic("xspanalloc: %d %d %lux", size, align, span);
1992/0729    
			break;
1992/0621    
 
		a = p+align; 
		a &= ~(align-1);
1992/0726/sys/src/9/port/alloc.c:150,156 – 1992/0729/sys/src/9/port/alloc.c:150,157
1992/0708    
		ptr[i] = (ulong)xalloc(sinc);
1992/0621    
	}
1992/0708    
	USED(sinc);
1992/0621    
	panic("xspanalloc: spanlist");
1992/0729    
	xsummary(); 
	panic("xspanalloc: %d %d %lux\n", size, align, span);
1992/0621    
	return 0;
1992/0618    
}
1992/0729/sys/src/9/port/alloc.c:380,386 – 1992/0912/sys/src/9/port/alloc.c:380,386 (short | long)
1992/0620    
{ 
	Hole *h; 
	Bucket *k; 
	int i, nfree;
1992/0912    
	int i, nfree, nused;
1992/0620    
 
	i = 0; 
	for(h = xlists.flist; h; h = h->link)
1992/0729/sys/src/9/port/alloc.c:393,404 – 1992/0912/sys/src/9/port/alloc.c:393,407
1992/0620    
		i += h->size; 
	} 
	print("%d bytes free\n", i);
1992/0912    
	nused = 0;
1992/0620    
	for(i = 3; i < Maxpow; i++) { 
		if(arena.btab[i] == 0 && arena.nbuck[i] == 0) 
			continue;
1992/0912    
		nused += arena.nbuck[i]*(1<<i);
1992/0620    
		nfree = 0; 
		for(k = arena.btab[i]; k; k = k->next) 
			nfree++; 
		print("%8d %4d %4d\n", 1<<i, arena.nbuck[i], nfree); 
	}
1992/0912    
	print("%d bytes in pool\n", nused);
1992/0618    
}
1992/0912/sys/src/9/port/alloc.c:5,10 – 1992/0913/sys/src/9/port/alloc.c:5,11 (short | long)
1992/0618    
#include	"fns.h"
1992/0707    
#include	"error.h"
1992/0618    
1992/0913    
1992/0621    
/* 
 * Plan 9 has two kernel allocators, the x... routines provide a first 
 * fit hole allocator which should be used for permanent or large structures.
1992/0912/sys/src/9/port/alloc.c:313,318 – 1992/0913/sys/src/9/port/alloc.c:314,321
1992/0720    
		bp = xalloc(size); 
		if(bp == nil) 
			return nil;
1992/0913    
 
		arena.nbuck[pow]++;
1992/0720    
	}
1992/0619    
 
	bp->size = pow;
1992/0913/sys/src/9/port/alloc.c:277,283 – 1993/0116/sys/src/9/port/alloc.c:277,283 (short | long)
1992/0619    
		unlock(&arena); 
 
		if(bp->magic != 0) 
			panic("malloc");
1993/0116    
			panic("malloc %lux", bp->magic);
1992/0619    
 
		bp->magic = Magic2n;
1992/0913/sys/src/9/port/alloc.c:365,376 – 1993/0116/sys/src/9/port/alloc.c:365,376
1992/0619    
	Bucket *bp, **l; 
 
	bp = (Bucket*)((ulong)ptr - bdatoff);
1993/0116    
	l = &arena.btab[bp->size]; 
 
	lock(&arena);
1992/0619    
	if(bp->magic != Magic2n) 
		panic("free"); 
                 
	bp->magic = 0; 
	lock(&arena); 
	l = &arena.btab[bp->size]; 
	bp->next = *l; 
	*l = bp; 
	unlock(&arena);
1993/0116/sys/src/9/port/alloc.c:263,269 – 1993/0120/sys/src/9/port/alloc.c:263,269 (short | long)
1992/0720    
	int pow, n; 
	Bucket *bp, *nbp;
1992/0619    
1992/0707    
	for(pow = 3; pow <= Maxpow; pow++)
1993/0120    
	for(pow = 3; pow < Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow)) 
			goto good;
1993/0116/sys/src/9/port/alloc.c:296,313 – 1993/0120/sys/src/9/port/alloc.c:296,311
1992/0720    
		if(bp == nil) 
			return nil; 
 
		next = (ulong)bp+size; 
		nbp = (Bucket*)next;
1993/0120    
		nbp = bp;
1992/0720    
		lock(&arena); 
		arena.btab[pow] = nbp; 
		arena.nbuck[pow] += n; 
		for(n -= 2; n; n--) {
1993/0120    
		while(--n) {
1992/0720    
			next = (ulong)nbp+size; 
			nbp->next = (Bucket*)next;
1993/0120    
			nbp = (Bucket*)next;
1992/0720    
			nbp->size = pow; 
			nbp = nbp->next;
1993/0120    
			nbp->next = arena.btab[pow]; 
			arena.btab[pow] = nbp;
1992/0720    
		} 
		nbp->size = pow; 
		unlock(&arena); 
	} 
	else {
1993/0116/sys/src/9/port/alloc.c:315,321 – 1993/0120/sys/src/9/port/alloc.c:313,321
1992/0720    
		if(bp == nil) 
			return nil;
1992/0913    
1993/0120    
		lock(&arena);
1992/0913    
		arena.nbuck[pow]++;
1993/0120    
		unlock(&arena);
1992/0720    
	}
1992/0619    
 
	bp->size = pow;
1993/0120/sys/src/9/port/alloc.c:276,287 – 1993/0121/sys/src/9/port/alloc.c:276,288 (short | long)
1992/0619    
		arena.btab[pow] = bp->next; 
		unlock(&arena); 
 
		if(bp->magic != 0)
1993/0116    
			panic("malloc %lux", bp->magic);
1993/0121    
		if(bp->magic != 0 || bp->size != pow) 
			panic("malloc bp %lux magic %lux size %d next %lux pow %d", bp, 
				bp->magic, bp->size, bp->next, pow);
1992/0619    
 
		bp->magic = Magic2n; 
 
		memset(bp->data, 0,  size);
1993/0121    
		memset(bp->data, 0, size);
1992/0619    
		return  bp->data; 
	} 
	unlock(&arena);
1993/0121/sys/src/9/port/alloc.c:274,286 – 1993/0205/sys/src/9/port/alloc.c:274,286 (short | long)
1992/0619    
	bp = arena.btab[pow]; 
	if(bp) { 
		arena.btab[pow] = bp->next; 
		unlock(&arena); 
                 
1993/0121    
		if(bp->magic != 0 || bp->size != pow)
1993/0205    
		if(bp->magic != 0 || bp->size != pow){ 
			unlock(&arena);
1993/0121    
			panic("malloc bp %lux magic %lux size %d next %lux pow %d", bp, 
				bp->magic, bp->size, bp->next, pow);
1992/0619    
                 
1993/0205    
		}
1992/0619    
		bp->magic = Magic2n;
1993/0205    
		unlock(&arena);
1992/0619    
1993/0121    
		memset(bp->data, 0, size);
1992/0619    
		return  bp->data;
1993/0121/sys/src/9/port/alloc.c:314,322 – 1993/0205/sys/src/9/port/alloc.c:314,320
1992/0720    
		if(bp == nil) 
			return nil;
1992/0913    
1993/0120    
		lock(&arena);
1992/0913    
		arena.nbuck[pow]++;
1993/0120    
		unlock(&arena);
1992/0720    
	}
1992/0619    
 
	bp->size = pow;
1993/0205/sys/src/9/port/alloc.c:263,269 – 1993/0501/sys/src/9/port/alloc.c:263,269 (short | long)
1992/0720    
	int pow, n; 
	Bucket *bp, *nbp;
1992/0619    
1993/0120    
	for(pow = 3; pow < Maxpow; pow++)
1993/0501    
	for(pow = 3; pow <= Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow)) 
			goto good;
1993/0205/sys/src/9/port/alloc.c:274,288 – 1993/0501/sys/src/9/port/alloc.c:274,287
1992/0619    
	bp = arena.btab[pow]; 
	if(bp) { 
		arena.btab[pow] = bp->next;
1993/0205    
		if(bp->magic != 0 || bp->size != pow){ 
			unlock(&arena);
1993/0121    
			panic("malloc bp %lux magic %lux size %d next %lux pow %d", bp, 
				bp->magic, bp->size, bp->next, pow);
1993/0205    
		}
1992/0619    
		bp->magic = Magic2n;
1993/0205    
		unlock(&arena);
1992/0619    
1993/0121    
		memset(bp->data, 0, size);
1993/0501    
		if(bp->magic != 0) 
			panic("malloc"); 
 
		bp->magic = Magic2n; 
 
		memset(bp->data, 0,  size);
1992/0619    
		return  bp->data; 
	} 
	unlock(&arena);
1993/0205/sys/src/9/port/alloc.c:297,312 – 1993/0501/sys/src/9/port/alloc.c:296,313
1992/0720    
		if(bp == nil) 
			return nil;
1993/0120    
		nbp = bp;
1993/0501    
		next = (ulong)bp+size; 
		nbp = (Bucket*)next;
1992/0720    
		lock(&arena);
1993/0501    
		arena.btab[pow] = nbp;
1992/0720    
		arena.nbuck[pow] += n;
1993/0120    
		while(--n) {
1993/0501    
		for(n -= 2; n; n--) {
1992/0720    
			next = (ulong)nbp+size;
1993/0120    
			nbp = (Bucket*)next;
1993/0501    
			nbp->next = (Bucket*)next;
1992/0720    
			nbp->size = pow;
1993/0120    
			nbp->next = arena.btab[pow]; 
			arena.btab[pow] = nbp;
1993/0501    
			nbp = nbp->next;
1992/0720    
		}
1993/0501    
		nbp->size = pow;
1992/0720    
		unlock(&arena); 
	} 
	else {
1993/0205/sys/src/9/port/alloc.c:333,340 – 1993/0501/sys/src/9/port/alloc.c:334,341
1992/0625    
		p = malloc(size); 
		if(p != nil) 
			return p; 
		s = u->p->psstate; 
		u->p->psstate = "Malloc";
1993/0501    
		s = up->psstate; 
		up->psstate = "Malloc";
1992/0625    
		qlock(&arena.rq); 
		while(waserror()) 
			;
1993/0205/sys/src/9/port/alloc.c:341,347 – 1993/0501/sys/src/9/port/alloc.c:342,348
1992/0625    
		sleep(&arena.r, return0, nil); 
		poperror(); 
		qunlock(&arena.rq); 
		u->p->psstate = s;
1993/0501    
		up->psstate = s;
1992/0622    
	}
1992/0707    
	pexit(Enomem, 1); 
	return 0;
1993/0205/sys/src/9/port/alloc.c:364,375 – 1993/0501/sys/src/9/port/alloc.c:365,376
1992/0619    
	Bucket *bp, **l; 
 
	bp = (Bucket*)((ulong)ptr - bdatoff);
1993/0116    
	l = &arena.btab[bp->size]; 
                 
	lock(&arena);
1992/0619    
	if(bp->magic != Magic2n) 
		panic("free");
1993/0501    
1992/0619    
	bp->magic = 0;
1993/0501    
	lock(&arena); 
	l = &arena.btab[bp->size];
1992/0619    
	bp->next = *l; 
	*l = bp; 
	unlock(&arena);
1993/0501/sys/src/9/port/alloc.c:95,102 – 1993/0515/sys/src/9/port/alloc.c:95,101 (short | long)
1992/0619    
	if(np1 > conf.npage1) 
		np1 = conf.npage1;
1992/0618    
1992/0619    
	palloc.p1 = conf.base1; 
	conf.base1 += np1*BY2PG;
1993/0515    
	palloc.p1 = conf.base1 + (conf.npage1 - np1)*BY2PG;
1992/0619    
	conf.npage1 -= np1; 
	xhole(conf.base1, conf.npage1*BY2PG);
1992/0625    
	conf.npage1 = conf.base1+(conf.npage1*BY2PG);
1993/0501/sys/src/9/port/alloc.c:106,113 – 1993/0515/sys/src/9/port/alloc.c:105,111
1992/0619    
	if(np0 > conf.npage0) 
		np0 = conf.npage0; 
 
	palloc.p0 = conf.base0; 
	conf.base0 += np0*BY2PG;
1993/0515    
	palloc.p0 = conf.base0 + (conf.npage0 - np0)*BY2PG;
1992/0619    
	conf.npage0 -= np0; 
	xhole(conf.base0, conf.npage0*BY2PG);
1992/0625    
	conf.npage0 = conf.base0+(conf.npage0*BY2PG);
1993/0515/sys/src/9/port/alloc.c:63,68 – 1993/1121/sys/src/9/port/alloc.c:63,69 (short | long)
1992/0619    
	int	size; 
	int	magic; 
	Bucket	*next;
1993/1121    
	ulong	pc;
1992/0619    
	char	data[1]; 
};
1992/0618    
1993/0515/sys/src/9/port/alloc.c:260,265 – 1993/1121/sys/src/9/port/alloc.c:261,268
1992/0720    
	ulong next; 
	int pow, n; 
	Bucket *bp, *nbp;
1993/1121    
ulong pc; 
pc = getcallerpc(0);
1992/0619    
1993/0501    
	for(pow = 3; pow <= Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow))
1993/0515/sys/src/9/port/alloc.c:278,284 – 1993/1121/sys/src/9/port/alloc.c:281,287
1993/0501    
			panic("malloc"); 
 
		bp->magic = Magic2n; 
                 
1993/1121    
bp->pc = pc;
1993/0501    
		memset(bp->data, 0,  size);
1992/0619    
		return  bp->data; 
	}
1993/0515/sys/src/9/port/alloc.c:318,323 – 1993/1121/sys/src/9/port/alloc.c:321,327
1992/0619    
 
	bp->size = pow; 
	bp->magic = Magic2n;
1993/1121    
bp->pc = pc;
1992/0619    
	return bp->data; 
}
1993/1121/sys/src/9/port/alloc.c:261,268 – 1993/1125/sys/src/9/port/alloc.c:261,266 (short | long)
1992/0720    
	ulong next; 
	int pow, n; 
	Bucket *bp, *nbp;
1993/1121    
ulong pc; 
pc = getcallerpc(0);
1992/0619    
1993/0501    
	for(pow = 3; pow <= Maxpow; pow++)
1992/0619    
		if(size <= (1<<pow))
1993/1121/sys/src/9/port/alloc.c:281,287 – 1993/1125/sys/src/9/port/alloc.c:279,285
1993/0501    
			panic("malloc"); 
 
		bp->magic = Magic2n;
1993/1121    
bp->pc = pc;
1993/1125    
		bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
1993/0501    
		memset(bp->data, 0,  size);
1992/0619    
		return  bp->data; 
	}
1993/1121/sys/src/9/port/alloc.c:321,327 – 1993/1125/sys/src/9/port/alloc.c:319,325
1992/0619    
 
	bp->size = pow; 
	bp->magic = Magic2n;
1993/1121    
bp->pc = pc;
1993/1125    
	bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
1992/0619    
	return bp->data; 
}
1993/1121/sys/src/9/port/alloc.c:331,341 – 1993/1125/sys/src/9/port/alloc.c:329,343
1992/0625    
	char *s;
1992/0619    
	void *p;
1992/0707    
	int attempt;
1993/1125    
	Bucket *bp;
1992/0619    
1992/0707    
	for(attempt = 0; attempt < 1000; attempt++) {
1992/0625    
		p = malloc(size); 
		if(p != nil)
1993/1125    
		if(p != nil) { 
			bp = (Bucket*)((ulong)p - bdatoff); 
			bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
1992/0625    
			return p;
1993/1125    
		}
1993/0501    
		s = up->psstate; 
		up->psstate = "Malloc";
1992/0625    
		qlock(&arena.rq);
1993/1125/sys/src/9/port/alloc.c:126,158 – 1993/1231/sys/src/9/port/alloc.c:126,153 (short | long)
1992/0621    
void* 
xspanalloc(ulong size, int align, ulong span) 
{ 
	int i, j;
1992/0708    
	ulong a, p, sinc;
1992/0621    
	ulong ptr[Spanlist];
1993/1231    
	ulong a, v, t;
1992/0621    
1992/0729    
	sinc = size/8;
1992/0621    
	span = ~(span-1); 
	for(i = 0; i < Spanlist; i++) { 
		p = (ulong)xalloc(size+align); 
		if(p == 0)
1992/0729    
			break;
1993/1231    
	a = (ulong)xalloc(size+align+span); 
	if(a == 0) 
		panic("xspanalloc: %d %d %lux\n", size, align, span);
1992/0621    
 
		a = p+align; 
		a &= ~(align-1); 
		if((a&span) == ((a+size)&span)) { 
			for(j = 0; j < i; j++)
1992/0708    
				if(ptr[j]) 
					xfree((void*)ptr[j]);
1992/0621    
                 
			return (void*)a; 
		}
1992/0708    
		xfree((void*)p); 
		ptr[i] = (ulong)xalloc(sinc);
1993/1231    
	if(span > 2) { 
		v = (a + span) & ~(span-1); 
		t = v - a; 
		if(t > 0) 
			xhole(PADDR(a), t); 
		t = a + span - v; 
		if(t > 0) 
			xhole(PADDR(v+size+align), t);
1992/0621    
	}
1992/0708    
	USED(sinc);
1992/0729    
	xsummary(); 
	panic("xspanalloc: %d %d %lux\n", size, align, span);
1992/0621    
	return 0;
1993/1231    
	else 
		v = a; 
 
	if(align > 1) 
		v = (v + align) & ~(align-1); 
 
	return (void*)v;
1992/0618    
} 
 
void*
1993/1231/sys/src/9/port/alloc.c:118,123 – 1994/0208/sys/src/9/port/alloc.c:118,126 (short | long)
1992/0625    
	conf.base1 = (ulong)KADDR(conf.base1); 
	conf.npage0 = (ulong)KADDR(conf.npage0); 
	conf.npage1 = (ulong)KADDR(conf.npage1);
1994/0208    
 
	/* setup initial memory allocations for interrupt time */ 
	qinit();
1992/0621    
} 
 
/*
1994/0208/sys/src/9/port/alloc.c:274,280 – 1994/0222/sys/src/9/port/alloc.c:274,280 (short | long)
1993/0205    
		unlock(&arena);
1992/0619    
1993/0501    
		if(bp->magic != 0) 
			panic("malloc");
1994/0222    
			panic("malloc %lux %lux", bp->magic, bp->pc);
1993/0501    
 
		bp->magic = Magic2n;
1993/1125    
		bp->pc = getcallerpc(((uchar*)&size) - sizeof(size));
1994/0208/sys/src/9/port/alloc.c:368,374 – 1994/0222/sys/src/9/port/alloc.c:368,374
1992/0619    
 
	bp = (Bucket*)((ulong)ptr - bdatoff); 
	if(bp->magic != Magic2n) 
		panic("free");
1994/0222    
		panic("free %lux %lux", bp->magic, bp->pc);
1993/0501    
1992/0619    
	bp->magic = 0;
1993/0501    
	lock(&arena);
Too many diffs (26 > 25). Stopping.


source code copyright © 1990-2005 Lucent Technologies; see license
Plan 9 distribution
comments to russ cox (rsc@swtch.com)