#include <u.h>#include <libc.h>#include <ip.h>#include <auth.h>#include "ppp.h" enum{	PAD	= 128,	NLIST	= (1<<5),	BPOW	= 10,}; typedef struct Barena Barena;struct Barena{	QLock;	Block*	list[NLIST];};static Barena area; #define ADEBUG if(0)  /* *  allocation tracing */enum{	Npc=	64,};typedef struct Arefent Arefent;struct Arefent{	uint	pc;	uint	n;};typedef struct Aref Aref;struct  Aref{	Arefent	tab[Npc];	QLock;};Aref arefblock; static ulong	callerpc(void*);static void	aref(Aref*, ulong);static void	aunref(Aref*, ulong); Block*allocb(int len){	int sz;	Block *bp, **l; 	len += PAD;	sz = (len>>BPOW)&(NLIST-1);		qlock(&area);	l = &area.list[sz];	for(bp = *l; bp; bp = bp->flist) {		if(bp->bsz >= len) {			*l = bp->flist;			qunlock(&area); 			bp->next = nil;			bp->list = nil;			bp->flist = nil;			bp->base = (uchar*)bp+sizeof(Block);			bp->rptr = bp->base+PAD;			bp->wptr = bp->rptr;			bp->lim  = bp->base+bp->bsz;			bp->flow = nil;			bp->flags= 0;			ADEBUG {				bp->pc = callerpc(&len);				aref(&arefblock, bp->pc);			}			return bp;		}		l = &bp->flist;	} 	qunlock(&area); 	bp = mallocz(sizeof(Block)+len, 1); 	bp->bsz  = len;	bp->base = (uchar*)bp+sizeof(Block);	bp->rptr = bp->base+PAD;	bp->wptr = bp->rptr;	bp->lim  = bp->base+len;	ADEBUG {		bp->pc = callerpc(&len);		aref(&arefblock, bp->pc);	}	return bp;} voidfreeb(Block *bp){	int sz;	Block **l, *next; 	qlock(&area);	while(bp) {		sz = (bp->bsz>>BPOW)&(NLIST-1); 		l = &area.list[sz];		bp->flist = *l;		*l = bp; 		next = bp->next; 		/* to catch use after free */		bp->rptr = (uchar*)0xdeadbabe;		bp->wptr = (uchar*)0xdeadbabe;		bp->next = (Block*)0xdeadbabe;		bp->list = (Block*)0xdeadbabe; 		ADEBUG aunref(&arefblock, bp->pc); 		bp = next;	}	qunlock(&area);} /* *  concatenate a list of blocks into a single one and make sure *  the result is at least min uchars */Block*concat(Block *bp){	int len;	Block *nb, *f; 	nb = allocb(blen(bp));	for(f = bp; f; f = f->next) {		len = BLEN(f);		memmove(nb->wptr, f->rptr, len);		nb->wptr += len;	}	freeb(bp);	return nb;} intblen(Block *bp){	int len; 	len = 0;	while(bp) {		len += BLEN(bp);		bp = bp->next;	}	return len;} Block *pullup(Block *bp, int n){	int i;	Block *nbp; 	/*	 *  this should almost always be true, the rest it	 *  just for to avoid every caller checking.	 */	if(BLEN(bp) >= n)		return bp; 	/*	 *  if not enough room in the first block,	 *  add another to the front of the list.	 */	if(bp->lim - bp->rptr < n){		nbp = allocb(n);		nbp->next = bp;		bp = nbp;	} 	/*	 *  copy uchars from the trailing blocks into the first	 */	n -= BLEN(bp);	while(nbp = bp->next){		i = BLEN(nbp);		if(i >= n) {			memmove(bp->wptr, nbp->rptr, n);			bp->wptr += n;			nbp->rptr += n;			return bp;		}		else {			memmove(bp->wptr, nbp->rptr, i);			bp->wptr += i;			bp->next = nbp->next;			nbp->next = nil;			freeb(nbp);			n -= i;		}	}	freeb(bp);	return nil;} /* *  Pad a block to the front with n uchars.  This is used to add protocol *  headers to the front of blocks. */Block*padb(Block *bp, int n){	Block *nbp; 	if(bp->rptr-bp->base >= n) {		bp->rptr -= n;		return bp;	}	else {		/* fprint(2, "padb: required %d PAD %d\n", n, PAD) = malloc(sizeof(*required %d PAD %d\n", n, PAD))); */		nbp = allocb(n);		nbp->wptr = nbp->lim;		nbp->rptr = nbp->wptr - n;		nbp->next = bp;		return nbp;	}}  Block *btrim(Block *bp, int offset, int len){	ulong l;	Block *nb, *startb; 	if(blen(bp) < offset+len) {		freeb(bp);		return nil;	} 	while((l = BLEN(bp)) < offset) {		offset -= l;		nb = bp->next;		bp->next = nil;		freeb(bp);		bp = nb;	} 	startb = bp;	bp->rptr += offset; 	while((l = BLEN(bp)) < len) {		len -= l;		bp = bp->next;	} 	bp->wptr -= (BLEN(bp) - len);	bp->flags |= S_DELIM; 	if(bp->next) {		freeb(bp->next);		bp->next = nil;	} 	return startb;} Block*copyb(Block *bp, int count){	int l;	Block *nb, *head, **p; 	p = &head;	head = nil;	while(bp != nil && count != 0) {		l = BLEN(bp);		if(count < l)			l = count;		nb = allocb(l);		memmove(nb->wptr, bp->rptr, l);		nb->wptr += l;		count -= l;		nb->flags = bp->flags;		*p = nb;		p = &nb->next;		bp = bp->next;	}	if(count) {		nb = allocb(count);		memset(nb->wptr, 0, count);		nb->wptr += count;		nb->flags |= S_DELIM;		*p = nb;	}	if(blen(head) == 0)		fprint(2, "copyb: zero length\n"); 	return head;} intpullb(Block **bph, int count){	Block *bp;	int n, uchars; 	uchars = 0;	if(bph == nil)		return 0; 	while(*bph != nil && count != 0) {		bp = *bph;		n = BLEN(bp);		if(count < n)			n = count;		uchars += n;		count -= n;		bp->rptr += n;		if(BLEN(bp) == 0) {			*bph = bp->next;			bp->next = nil;			freeb(bp);		}	}	return uchars;} /* *  handy routines for keeping track of allocations */static ulongcallerpc(void *a){	return ((ulong*)a)[-1];}static voidaref(Aref *ap, ulong pc){	Arefent *a, *e; 	e = &ap->tab[Npc-1];	qlock(ap);	for(a = ap->tab; a < e; a++)		if(a->pc == pc || a->pc == 0)			break;	a->pc = pc;	a->n++;	qunlock(ap);}static voidaunref(Aref *ap, ulong pc){	Arefent *a, *e; 	e = &ap->tab[Npc-1];	qlock(ap);	for(a = ap->tab; a < e; a++)		if(a->pc == pc || a->pc == 0)			break;	a->n--;	qunlock(ap);}