#include <u.h>#include <libc.h>#include "system.h"#ifdef Plan9#include <libg.h>#endif# include "stdio.h"/* compile-time features   IALLOC use all blocks given to ialloc, otherwise ignore unordered blocks   MSTATS enable statistics    debug enable assertion checking   longdebug full arena checks at every transaction*/#ifdef longdebug#define debug 1#endif#ifdef debug#include <stdio.h>#define ASSERT(p) if(!(p))botch(__LINE__);elsestaticbotch(n){	fprintf(stderr,"bad arena, malloc.c line %d\n" ,n);	abort();}#else#define ASSERT(p)#endif /*	C storage allocator *	circular first-fit strategy *	works with noncontiguous, but monotonically linked, arena *	each block is preceded by a ptr to the (pointer of)  *	the next following block *	blocks are exact number of words long  *	aligned to the data type requirements of ALIGN *	pointers to blocks must have BUSY bit 0 *	bit in ptr is 1 for busy, 0 for idle *	gaps in arena are merely noted as busy blocks *	last block of arena is empty and *	has a pointer to first *	idle blocks are coalesced during space search * *	a different implementation may need to redefine *	ALIGN, NALIGN, BLOCK, BUSY, INT *	where INT is integer type to which a pointer can be cast*/#define INT int#define ALIGN int#define NALIGN 1#define WORD sizeof(union store)#define BLOCK 4096#define BUSY 1#define testbusy(p) ((INT)(p)&BUSY)#define setbusy(p) (union store *)((INT)(p)|BUSY)#define clearbusy(p) (union store *)((INT)(p)&~BUSY) union store {	      union store *ptr;	      ALIGN dummy[NALIGN];	      int calloc;	/*calloc clears an array of integers*/}; /* alloca should have type union store. * The funny business gets it initialized without complaint*/#define addr(a) (union store*)&astatic	char *alloca = (char*)&alloca + BUSY;	/* initial arena */static	union store *allocb = addr(alloca);	/*arena base*/static	union store *allocc = addr(alloca);	/*all prev blocks known busy*/static	union store *allocp = addr(alloca);	/*search ptr*/static	union store *alloct = addr(alloca);	/*top cell*/static	union store *allocx;	/*for benefit of realloc*/extern	char *sbrk(); /* a cache list of frequently-used sizes is maintained. From each * cache entry hangs a chain of available blocks  * malloc(0) shuts off caching (to keep freed data clean)*/#define CACHEMAX 50	/* largest block to be cached (in words) */#define CACHESIZ 13	/* number of entries (prime) */ static union store *cache[CACHESIZ];static char *stdmalloc(unsigned);static draincache(void);void ialloc(char *, unsigned);static stdfree(union store *); #ifdef MSTATS#define Mstats(e) estatic long nmalloc, nrealloc, nfree;	/* call statistics */static long walloc, wfree;		/* space statistics */static long chit, ccoll, cdrain, cavail;	/* cache statistics */#else#define Mstats(e)#endif void *malloc(long nbytes){	register union store *p;	register nw;	register union store **cp; 	nw = (nbytes+WORD+WORD-1)/WORD;	Mstats((nmalloc++, walloc += nw));	if(nw<CACHEMAX && nw>=2) {		cp = &cache[nw%CACHESIZ];		p = *cp;		if(p && nw==clearbusy(p->ptr)-p) {			ASSERT(testbusy(p->ptr));			*cp = (++p)->ptr;			Mstats((chit++, cavail--));			return (char*)p;		}	}	return stdmalloc(nw);} static char *stdmalloc(unsigned nw){	register union store *p, *q;	register temp;	ASSERT(allock(allocp));	for(; ; ) {	/* done at most thrice */		p = allocp;		for(temp=0; ; ) {			if(!testbusy(p->ptr)) {				allocp = p;				while(!testbusy((q=p->ptr)->ptr)) {					ASSERT(q>p);					p->ptr = q->ptr;				}				if(q>=p+nw && p+nw>=p)					goto found;			}			q = p;			p = clearbusy(p->ptr);			if(p <= q) {				ASSERT(p==allocb&&q==alloct);				if(++temp>1)					break;				ASSERT(allock(allocc));				p = allocc;			}		}		p = (union store *)sbrk(0);		temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);		do {			if(p+temp > p) {	/*check wrap*/				q = (union store *)sbrk(temp*WORD);				if((INT)q != -1)					goto mextend;			}			temp -= (temp-nw)/2;		} while(temp-nw > 1);		if(draincache())			continue;		return(NULL);mextend:		draincache();		ialloc((char *)q, (unsigned)temp*WORD);	}found:	allocp += nw;	if(q>allocp) {		allocx = allocp->ptr;		allocp->ptr = p->ptr;	}	p->ptr = setbusy(allocp);	if(p<=allocc) {		ASSERT(p==allocc);		while(testbusy(allocc->ptr)		     && (q=clearbusy(allocc->ptr))>allocc)			allocc = q;	}	return((char *)(p+1));}voidfree(void *ap){	register union store *p = (union store *)ap, *q;	register nw;	register union store **cp; 	if(p==NULL)		return;	--p;	ASSERT(allock(p));	ASSERT(testbusy(p->ptr));	ASSERT(!cached(p));	nw = clearbusy(p->ptr) - p;	Mstats((nfree++, wfree += nw));	ASSERT(nw>0);	if(nw<CACHEMAX && nw>=2) {		cp = &cache[nw%CACHESIZ];		q = *cp;		if(!q || nw==clearbusy(q->ptr)-q) {			p[1].ptr = q;			*cp = p;			Mstats(cavail++);			return;		} else Mstats(q && ccoll++);	}	stdfree(p+1);} /*	freeing strategy tuned for LIFO allocation*/staticstdfree(union store *p){	allocp = --p;	if(p < allocc)		allocc = p;	ASSERT(allock(allocp));	p->ptr = clearbusy(p->ptr);	ASSERT(p->ptr > allocp);} staticdraincache(void){	register union store **cp = cache+CACHESIZ;	register union store *q;	int anyfreed = 0;	while(--cp>=cache) {		while(q = *cp) {			ASSERT(testbusy(q->ptr));			ASSERT((clearbusy(q->ptr)-q)%CACHESIZ==cp-cache);			ASSERT(q>=allocb&&q<=alloct);			stdfree(++q);			anyfreed++;			*cp = q->ptr;		}	}	Mstats((cdrain+=anyfreed, cavail=0));	return anyfreed;} /* ialloc(q, nbytes) inserts a block that did not come * from malloc into the arena * * q points to new block * r points to last of new block * p points to last cell of arena before new block * s points to first cell of arena after new block*/voidialloc(char *qq, unsigned nbytes){	register union store *p, *q, *s;	union store *r; 	q = (union store *)qq;	r = q + (nbytes/WORD) - 1;	q->ptr = r;	if(q > alloct) {		p = alloct;		s = allocb;		alloct = r;	} else {#ifdef IALLOC	/* useful only in small address spaces */		for(p=allocb; ; p=s) {			s = clearbusy(p->ptr);			if(s==allocb)				break;			ASSERT(s>p);			if(s>r) {				if(p<q)					break;				else					ASSERT(p>r);			}		}		if(allocb > q)			allocb = q;		if(allocc > q)			allocc = q;		allocp = allocc;#else		return;#endif	}	p->ptr = q==p+1? q: setbusy(q);	r->ptr = s==r+1? s: setbusy(s);	while(testbusy(allocc->ptr))		allocc = clearbusy(allocc->ptr);} /*	realloc(p, nbytes) reallocates a block obtained from malloc() *	and freed since last call of malloc() *	to have new size nbytes, and old content *	returns new location, or 0 on failure*/ void *realloc(void *pp, long nbytes){	register union store *p = (union store *)pp;	register union store *s, *t;	register union store *q;	register unsigned nw;	unsigned onw; 	Mstats(nrealloc++);	if(p==NULL)		return malloc(nbytes);	ASSERT(allock(p-1));	if(testbusy(p[-1].ptr))		stdfree(p);	onw = p[-1].ptr - p;	nw = (nbytes+WORD-1)/WORD;	q = (union store *)stdmalloc(nw+1);	if(q==NULL || q==p)		return((char *)q);	ASSERT(q<p||q>p[-1].ptr);	if(nw<onw) {		Mstats(wfree += onw-nw);		onw = nw;	} else Mstats(walloc += nw-onw);	for(s=p, t=q; onw--!=0; )		*t++ = *s++;	ASSERT(clearbusy(q[-1].ptr)-q==nw);	if(q<p && q+nw>=p)		(q+(q+nw-p))->ptr = allocx;	ASSERT(allock(q-1));	return((char *)q);} #ifdef debugstaticallock(union store *q){#ifdef longdebug	register union store *p, *r;	register union store **cp;	int x, y;	for(cp=cache+CACHESIZ; --cp>=cache; ) {		if((p= *cp)==0)			continue;		x = clearbusy(p->ptr) - p;		ASSERT(x%CACHESIZ==cp-cache);		for( ; p; p = p[1].ptr) {			ASSERT(testbusy(p->ptr));			ASSERT(clearbusy(p->ptr)-p==x);		}	}	x = 0, y = 0;	p = allocb;	for( ; (r=clearbusy(p->ptr)) > p; p=r) {		if(p==allocc)			y++;		ASSERT(y||testbusy(p->ptr));		if(p==q)			x++;	}	ASSERT(r==allocb);	ASSERT(x==1||p==q);	ASSERT(y||p==allocc);	return(1);#else	ASSERT((unsigned)q/WORD*WORD==(unsigned)q);	ASSERT(q>=allocb&&q<=alloct);#endif}#endif mstats(){#ifdef MSTATS#ifndef stderr#include <stdio.h>#endif	fprintf(stderr, "Malloc statistics, including overhead bytes\n");	fprintf(stderr, "Arena: bottom %ld, top %ld\n",		(long)clearbusy(alloca), (long)alloct);	fprintf(stderr, "Calls: malloc %ld, realloc %ld, free %ld\n",		nmalloc, nrealloc, nfree);	fprintf(stderr, "Bytes: allocated or extended %ld, ",		walloc*WORD);	fprintf(stderr, "freed or cut %ld\n", wfree*WORD);	fprintf(stderr,"Cache: hits %ld, collisions %ld, discards %ld, avail %ld\n",		chit, ccoll, cdrain, cavail);#endif} #ifdef debugcached(union store *p){	union store *q = cache[(clearbusy(p->ptr)-p)%CACHESIZ];	for( ; q; q=q[1].ptr)		ASSERT(p!=q);	return 0;}#endif