/* * malloc * *	Uses Quickfit (see SIGPLAN Notices October 1988) *	with allocator from Kernighan & Ritchie */ #include <u.h>#include <libc.h> enum{	DEBUG=	0,	DEBUGX=	1,}; typedef double Align; typedef union Header Header; union Header {	struct {		Header*	next;		uint	size;	} s;	Align	al;};#define	NUNITS(n) (((n)+sizeof(Header)-1)/sizeof(Header) + 1)#define	BRKSIZE	(8192/sizeof(Header)) #define	NQUICK	((512/sizeof(Header))+1) typedef struct Alloclist Alloclist;struct Alloclist {	Lock	lk;	Header	h;}; static	Header	*quicklist[NQUICK+1];static	Header	misclist;static	Header	*rover;static	unsigned tailsize;static	Header	*tailptr;static	Header	checkval;static	int	morecore(unsigned);static	void	badalloc(void*);static	int	malloctrace = 0;void	qmallocdump(void);void	qfree(void*); static Lock mainlock;#define	LOCK	lock(&mainlock)#define	UNLOCK	unlock(&mainlock) void	*sbrk(ulong); #define	tailalloc(p,n) ((p)=tailptr, tailsize -= (n), tailptr+=(n),\			 (p)->s.size=(n), (p)->s.next = &checkval) void *qmalloc(ulong nbytes){	Header *p, *q;	uint nunits; 	if(DEBUGX && malloctrace>1)		fprint(2, "malloc %lud\n", nbytes);	LOCK;	nunits = NUNITS(nbytes);	if(nunits <= NQUICK &&	    (p = quicklist[nunits]) != nil) {		quicklist[nunits] = p->s.next;		p->s.next = &checkval;		UNLOCK;		return p+1;	}	if(nunits > tailsize) {		/* hard way */		if((q = rover) != nil)			do {				p = q->s.next;				if(p->s.size >= nunits) {					if(malloctrace)						write(2, "%", 1);					if(p->s.size > nunits) {						p->s.size -= nunits;						p += p->s.size;						p->s.size = nunits;					} else						q->s.next = p->s.next;					p->s.next = &checkval;					rover = q;					UNLOCK;					return (char *)(p+1);				}			} while((q = p) != rover);		if(!morecore(nunits)){			UNLOCK;			return nil;		}	}	if(malloctrace)		write(2, "+", 1);	tailalloc(p, nunits);	UNLOCK;	return p+1;} static intmorecore(uint nunits){	char *cp; 	if(malloctrace) {		write(2, ".", 1);		if(DEBUG){			static int done;			if(done == 0) {				done = 1;				fprint(2, "\n");				atexit(qmallocdump);			}		}	}	if(nunits < BRKSIZE)		nunits = BRKSIZE;	cp = sbrk(nunits * sizeof(Header));	if(cp == (char *)~0)		return 0;	if(tailsize != 0) {		Header *p = tailptr; 		if(p+tailsize == (Header *)cp) {			/* new block follows tail: combine */			tailsize += nunits;			return 1;		}		/* there is a gap: must free existing tail space */		p->s.size = tailsize;		p->s.next = &checkval;		tailsize = 0;		tailptr = nil;		qfree(p+1);	}	tailptr = (Header*)cp;	tailsize = nunits;	return 1;} voidqfree(void *ap){	Header *p, *q;	uint nunits; 	if(ap == nil)		return;	p = (Header*)ap - 1;	if((nunits = p->s.size) == 0 || p->s.next != &checkval)		badalloc(ap);	if(DEBUG && malloctrace>1)		fprint(2, "free %d at %p\n", nunits, p);	if(tailptr != nil && p+nunits == tailptr) {		/* block before tail */		tailptr = p;		tailsize += nunits;		return;	}	if(nunits <= NQUICK) {		Header **fp;		fp = &quicklist[nunits];		p->s.next = *fp;		*fp = p;		return;	}	if((q = rover) == nil) {		q = &misclist;		q->s.size = 0;		q->s.next = q;	}	for(; !(p > q && p < q->s.next); q = q->s.next)		if(q >= q->s.next && (p > q || p < q->s.next))			break;	if(p+p->s.size == q->s.next) {		p->s.size += q->s.next->s.size;		p->s.next = q->s.next->s.next;	} else		p->s.next = q->s.next;	if(q+q->s.size == p) {		q->s.size += p->s.size;		q->s.next = p->s.next;	} else		q->s.next = p;	rover = q;} void*qrealloc(void *ap, ulong nbytes){	char *dp;	uint nunits, osize;	Header *p; 	if((p = ap) == nil)		return qmalloc(nbytes);	if(nbytes == 0) {		free(p);		return nil;	}	if((osize = (--p)->s.size) == 0 || p->s.next != &checkval)		badalloc(ap);	nunits = NUNITS(nbytes);	if(p->s.size == nunits)		return ap;	if(DEBUG && malloctrace>1)		fprint(2, "tail %p %ud %p %ud\n", tailptr, tailsize, p, p->s.size);	if((dp = qmalloc(nbytes)) != nil && dp != ap) {		osize = (osize-1)*sizeof(Header);		if(nbytes < osize)			osize = nbytes;		memmove(dp, ap, osize);	}	free(ap);	return dp;} static voidbadalloc(void *ap){	USED(ap);	write(2, "malloc: corrupt allocation arena\n", 34);	abort();} /* * special function for use by valloc */void_free_mem(void *cp, ulong nbytes){	uint nunits;	Header *p; 	p = cp;	nunits = nbytes/sizeof(Header);	if(nunits > 1) {		p->s.size = nunits;		p->s.next = &checkval;		qfree(p+1);	} } voidqmallocdump(void){	int n;	Header *q; 	for(n=0; n<=NQUICK; n++) {		for(q = quicklist[n]; q != nil; q = q->s.next)			fprint(2, "q%d\t%p\t%ud\n", n, q, q->s.size);	}	if((q = rover) != nil)		do {			fprint(2, "m%d\t%p\t%ud\n", n, q, q->s.size);		} while((q = q->s.next) != rover);} void*malloc(ulong n){	void *p; 	p = qmalloc(n);	if(p != nil)		memset(p, 0, n);	return p;} voidfree(void *p){	LOCK;	qfree(p);	UNLOCK;} void*calloc(ulong m, ulong n){	void *p; 	n *= m;	p = qmalloc(n);	memset(p, 0, n);	return p;} voidsetmalloctag(void*, ulong){}