code: mafs

ref: a6e9ab0ced8523fb8099afa4547dc27793e27462
dir: /extents.c/

#include <u.h>
#include <libc.h>
#include "dat.h"
#include "fns.h"
#include "extents.h"

/*
 * Extents are used to manage memory space and disk space. The space is
 * is split into units of the same size.
 *
 * All space is split into a sequence of units. Each such sequence of units
 * is called an Extent. The data structure Extents is used to contain this
 * information. Space is added to the Extents using bfree() and allocated
 * using balloc(). When freed, adjacent extents are coalesced to create a
 * large extent, if they are continuous.
 */

Extent *sortbysize(Extents *es, Extent *e);
void	showextent(int fd, char *pre, Extent *e);
static int extentsfd = -1;

s64
belongs(Extent *e, u64 start)
{
	if(e == nil)
		sysfatal("belongs: e == nil");
	if(e->start+e->len == start)
		return 0;
	return start-e->start;
}

Extent *
searchlrus(Extents *es, u64 blkno, s64 *closest)
{
	Extent *e, *eclosest;
	s64 howclose;

	if(es == nil || es->lowest == nil)
		panic("searchlrus: should not happen");

	if(es->lru == nil){
		*closest = belongs(es->lowest, blkno);
		return es->lowest;
	}

	eclosest = e = es->lru;
	*closest = belongs(e, blkno);
	if(*closest == 0)
		return eclosest;
	for(e = e->next; e != es->lru; e = e->next){
		howclose = belongs(e, blkno);
		if(abs(howclose) < abs(*closest)){
			eclosest = e;
			*closest = howclose;
			if(howclose == 0)
				break;
		}
	}
	return eclosest;
}

/* TODO? check len and start and not just len */
Extent *
searchlrusbysize(Extents *es, u64 len, s64 *closest)
{
	Extent *e, *eclosest;
	s64 howclose;

	if(es == nil || es->lowest == nil)
		panic("searchlrusbysize: should not happen");

	// print("searchlrusbysize len %llud e->len %llud\n", len, e->len);
	if(es->lru == nil){
		*closest = len - es->lowest->len;
		return es->lowest;
	}

	eclosest = e = es->lru;
	*closest = len - e->len;
	if(closest == 0)
		return eclosest;
	for(e = e->next; e != es->lru; e = e->next){
		howclose = len - e->len;
		if(abs(howclose) < abs(*closest)){
			eclosest = e;
			*closest = howclose;
			if(howclose == 0)
				break;
		}
	}
	return eclosest;
}

void
removefromlrus(Extents *es, Extent *e)
{
	Extent *d, *f;

	if(e == nil || es == nil)
		return;

//	print("removefromlrus e start %llud len %llud\n", e->start, e->len);
	/* only entry in the lru linked list */
	if(e == e->prev && e->prev == e->next){
		e->prev = e->next = es->lru = nil;
		es->nlru = 0;
		return;
	}

	/* d e f => d f */
	d = e->prev;
	f = e->next;

	if(d != nil)
		d->next = f;
	if(f != nil)
		f->prev = d;
	es->nlru--;
	e->prev = e->next = nil;

	if(es->lru == e)
		if(f != nil)
			es->lru = f;
		else if(d != nil)
			es->lru = d;
		else
			panic("removefromlrus(): should not be happening\n");
			// es->lru = nil;
}

Extent *
intolrus(Extents *es, Extent *e)
{
	Extent *y, *z;

	if(e == nil || es == nil)
		return nil;

	if(e->prev != nil || e->next != nil)
		removefromlrus(es, e);

	if(es->lru == nil){
		e->prev = e->next = e;
		es->nlru = 1;
	}else if(es->nlru >= Nlru){
		/*
			y z lru
				to
			y e lru
			then make e the lru
		 */
		z = es->lru->prev;
		y = z->prev;
		z->prev = z->next = nil;

		e->prev = y;
		y->next = e;

		e->next = es->lru;
		es->lru->prev = e;
	}else{
		/*
			z lru
				to
			z e lru
			then make e the lru
		 */
		z = es->lru->prev;
		z->next = e;
		e->prev = z;
		e->next = es->lru;
		es->lru->prev = e;
		es->nlru++;
	}
	es->lru = e;
	return e;
}

Extent *
smallest(Extents *es)
{
	Extent *e;

	if(es == nil)
		return nil;
	for(e = es->lru ? es->lru : es->lowest;
		e!=nil && e->small != nil; e=e->small)
		;
	return e;
}

Extent *
biggest(Extents *es)
{
	Extent *e;

	if(es == nil)
		return nil;
	for(e = es->lru ? es->lru : es->lowest;
		e!=nil && e->big != nil; e=e->big)
		;
	return e;
}

Extent *
lowest(Extents *es)
{
	if(es == nil)
		return nil;
	return es->lowest;
}

Extent *
highest(Extents *es)
{
	Extent *e;

	if(es == nil)
		return nil;
	for(e = es->lru ? es->lru : es->lowest;
		e!=nil && e->high != nil; e=e->high)
		;
	return e;
}

Extent *
addbysize(Extents *es, Extent *e)
{

	s64 dir = 0;
	Extent *eprev, *euse, *dsmall, *fbig;

	if(es == nil)
		panic("arrangebysize es == nil");
	if(chatty9p > 7)
	fprint(2, "addbysize es->lowest %8#p e %8#p es->n %llud es->lru %8#p\n", es->lowest, e, es->n, es->lru);
//	showextents(2, "addbysize\n", es);

	if(chatty9p > 7)
		print("addbysize es->n %llud e->start %llud e->len %llud\n", es->n, e->start, e->len);

	/* using the lru of extents to find the closest.
		dir = e->len - es->lru->len */
	eprev = euse = searchlrusbysize(es, e->len, &dir);
	if(e == nil || euse == nil)
		panic("addbysize: e == nil");
	if(chatty9p > 7)
		print("addbysize dir %lld euse start %llud len %llud\n", dir, euse->start, euse->len);
	if(dir < 0){
		/*	e->len - es->lru->len < 0
			find a same sized extent by scrolling down */
		while(euse != nil && e->len < euse->len){
			eprev = euse;
			euse = euse->small;
		}
		/*	euse e eprev
				euse->len <= e->len
				e->len < eprev->len
		 */
		if(euse == nil){
			/* at the smallest extent, add below */
			eprev->small = e;
			e->big = eprev;
			e->small = nil;
			return e;
		}else if(euse->len < e->len){
			/* if different sized euse, close it */
			eprev->small = e;
			e->big = eprev;
			e->small = euse;
			euse->big = e;
			return e;
		}
		euse = eprev;
	}else if(dir > 0){
		/*	 e->len - es->lru->len > 0
			find a same sized extent by scrolling up */
		while(euse != nil && e->len > euse->len){
			eprev = euse;
			euse = euse->big;
		}
		/*	eprev e euse
				e->len <= euse->len
				eprev->len < e->len
		 */
		if(euse == nil){
			/* at the biggest extent, add above */
			eprev->big = e;
			e->small = eprev;
			e->big = nil;
			return e;
		}else if(e->len < euse->len){
			/* if different sized euse, close it */
			eprev->big = e;
			e->small = eprev;
			euse->small = e;
			e->big = euse;
			return e;
		}
		euse = eprev;
	}
	/* dir == 0
		find position using the block number as long as size matches
		search up by block number */
	while(euse != nil && e->len == euse->len && euse->start < e->start){
		eprev = euse;
		euse = euse->big;
	}
	euse = eprev;
	if(chatty9p > 7)
	print("addbysize after scroll up eprev start %llud len %llud\n", eprev->start, eprev->len);
	/* search down by block number */
	while(euse != nil && e->len == euse->len && e->start < euse->start){
		eprev = euse;
		euse = euse->small;
	}
	/* euse e eprev */
	if(e->len < eprev->len ||
		(e->len == eprev-> len && e->start < eprev->start)){
		fbig = eprev;
		dsmall = eprev->small;
	}else{
		dsmall = eprev;
		fbig = eprev->big;
	}

	if(chatty9p > 7)
	print("addbysize after scroll down eprev start %llud len %llud\n", eprev->start, eprev->len);
	if(chatty9p > 7){
		print("addbysize e start %llud len %llud\n", e->start, e->len);
		if(dsmall == nil)
			print("addbysize dsmall nil\n");
		else
			print("addbysize dsmall start %llud len %llud\n", dsmall->start, dsmall->len);
		if(fbig == nil)
			print("addbysize fbig nil\n");
		else
			print("addbysize fbig start %llud len %llud\n", fbig->start, fbig->len);
	}
	if(fbig != nil)
		fbig->small = e;
	e->big = fbig;
	if(dsmall != nil)
		dsmall->big = e;
	e->small = dsmall;
	return e;
}

Extent *
addextent(Extents *es, Extent *e, u64 start, u64 len)
{
	Extent *c;

	c = emalloc(sizeof(Extent));
	c->start = start;
	c->len = len;
	addbysize(es, c);
	es->n++;
	if(chatty9p > 7)
		print("	+%llud %llud %llud\n", start, start+len-1, len);

	if(start < e->start){
		/* e->low e =>
			e->low c e
		  */
		if(e->low == nil)
			es->lowest = c;
		else
			e->low->high = c;
		c->low = e->low;
		e->low = c;
		c->high = e;
		return c;
	}
	if(start > e->start){
		/* e e->high =>
			e c e->high
		  */
		if(e->high != nil)
			e->high->low = c;
		c->high = e->high;
		e->high = c;
		c->low = e;
		return c;
	}
	print("addextent: should not be here e->start"
			" %llud .. %llud start %llud len %llud\n",
			e->start, e->start+e->len-1, start, len);
	abort();
	return nil;
}

/* e start f => e+start+f */
Extent *
mergeboth(Extents *es, Extent *e, u64 start, u64 len, Extent *f)
{
	Extent *small, *big;

	if(es == nil || e == nil || f == nil)
		panic("mergeboth: should not be happening\n");;
	if(e->start+e->len != start || start+len != f->start)
		panic("mergeboth the caller is wrong\n");

	/* skip e in size lru
		small e big => small big
	 */
	small = e->small;
	big = e->big;
	if(small != nil)
		small->big = big;
	if(big != nil)
		big->small = small;
	e->small = e->big = nil;

	/* skip f in size lru
		small f big => small big
	 */
	small = f->small;
	big = f->big;
	if(small != nil)
		small->big = big;
	if(big != nil)
		big->small = small;
	f->small = f->big = nil;

	e->len += len+f->len;
	e->high = f->high;
	if(f->high != nil)
		f->high->low = e;
	removefromlrus(es, f);
	es->n--;

	while(big != nil &&
			(big->len < e->len ||
			(big->len == e->len && big->start < e->start))){
		small = big;
		big = big->big;
	}
	e->small = small;
	e->big = big;
	if(small != nil)
		small->big = e;
	if(big != nil)
		big->small = e;
	return e;
}

/* e start f => e+start f */
Extent *
mergeprevious(Extents *es, Extent *e, u64 start, u64 len)
{
	Extent *small, *big;

	if(es == nil || e == nil)
		panic("mergeprevious: should not be happening\n");;
	if(e->start+e->len != start)
		panic("mergeprevious the caller is wrong\n");

	/* skip e in size lru
		small e big => small big
	 */
	small = e->small;
	big = e->big;
	if(small != nil)
		small->big = big;
	if(big != nil)
		big->small = small;
	e->small = e->big = nil;

	e->len += len;
	if(e->low == nil)
		es->lowest = e;

	while(big != nil &&
			(big->len < e->len ||
			(big->len == e->len && big->start < e->start))){
		small = big;
		big = big->big;
	}
	e->small = small;
	e->big = big;
	if(small != nil)
		small->big = e;
	if(big != nil)
		big->small = e;
	return e;
}

/* start e => start+e */
Extent *
mergenext(Extents *es, Extent *e, u64 start, u64 len)
{
	Extent *small, *big;

	if(es == nil || e == nil)
		panic("mergenext: should not be happening\n");;
	if(start+len != e->start)
		panic("mergenext the caller is wrong\n");

	/* skip e in size lru
		small e big => small big
	 */
	small = e->small;
	big = e->big;
	if(small != nil)
		small->big = big;
	if(big != nil)
		big->small = small;
	e->small = e->big = nil;

	e->start = start;
	e->len += len;
	while(big != nil &&
			(big->len < e->len ||
			(big->len == e->len && big->start < e->start))){
		small = big;
		big = big->big;
	}
	e->small = small;
	e->big = big;
	if(small != nil)
		small->big = e;
	if(big != nil)
		big->small = e;
	return e;
}

/*
print("between e->prev %llud .. %llud and e %llud .. %llud\n",
	 e->prev->start, e->prev->start+e->prev->n-1,
	 e->start, e->start+e->len-1);
 */
Extent *
doadd(Extents *es, u64 start, u64 len)
{
	s64 dir;
	Extent *e, *d, *f;

	if(es == nil)
		panic("add es == nil");
	if(es->n == 0){
		e = emalloc(sizeof(Extent));
		e->low = e->high = e->small = e->big = nil;
		e->start = start;
		e->len = len;
		es->lowest = e;
		es->n = 1;
		return e;
	}

	/* using the previously used extents */
	d = f = e = searchlrus(es, start, &dir);
	if(e == nil)
		panic("doadd: e == nil");
	if(chatty9p > 7){
		print(" 	belongs(e %llud %llud %llud low %p high %p start %llud %llud %llud) %lld\n",
				 e->start, e->start+e->len-1, e->len, e->low, e->high,
				 start, start+len-1, len, dir);
	}

	if(dir == 0){	/* perfect, e->star+e->len == start */
		if(e->high != nil &&
			e->start+e->len == start &&
			start+len == e->high->start)
			return mergeboth(es, e, start, len, e->high);
		else
			return mergeprevious(es, e, start, len);
	}
	else if(dir < 0){	/* start < e->start */
		while(e != nil && start < e->start){
			f = e;
			e = e->low;
		}
		/* e start f => e+start+f */
		if(e != nil && f != nil &&
			e->start+e->len == start &&
			start+len == f->start)
			return mergeboth(es, e, start, len, f);

		/* e start f => e+start f */
		if(e != nil && e->start+e->len == start)
			return mergeprevious(es, e, start, len);

		/* e start f => e start+f */
		if(f != nil && start+len == f->start)
			return mergenext(es, f, start, len);

		if(e == nil)/* start f */
			return addextent(es, f, start, len);
		else		/* e start f */
			return addextent(es, e, start, len);

	}else /* if(dir > 0) */{	/* start > e->start */
		while(e != nil && start > e->start){
			d = e;
			e = e->high;
		}
		/* d start e => e+start+f */
		if(d != nil && e != nil &&
			d->start+d->len == start &&
			start+len == e->start)
			return mergeboth(es, d, start, len, e);

		/* d start e => d+start e */
		if(d != nil && d->start+d->len == start)
			return mergeprevious(es, d, start, len);

		/* d start e => d start+e */
		if(e != nil && start+len == e->start)
			return mergenext(es, e, start, len);

		return addextent(es, d, start, len);
	}
}

Extent *
add(Extents *es, u64 start, u64 len)
{
	Extent *e;

	if(chatty9p > 7){
		showextents(2, "		before\n", es);
		fprint(2, " +%llud %llud\n", start, len);
	}
	e = intolrus(es, doadd(es, start, len));
	if(chatty9p > 7)
		showextents(2, "		after\n", es);
	return e;
}

/*
	remove from all the linked lists: lru's, start's, len's
	change Extents.lowest if it is the lowest
 */
static u64
pluck(Extents *es, Extent *e)
{
	Extent *dlow, *fhigh, *dsmall, *fbig;
	u64 start;

	if(es == nil || e == nil || es->lowest == nil)
		panic("pluck(): should not happen");

	removefromlrus(es, e);

	/* if e is the only entry in es */
	if(e->low == nil && e->high == nil){
		es->lowest = nil;
		es->n = 0;
		start = e->start;
		free(e);
		return start;
	}

	/* there are atleast 2 elements in the list */
	if(es->lowest == e)
		es->lowest = e->high;

	/* d e f => d f */
	dlow = e->low;
	fhigh = e->high;
	dsmall = e->small;
	fbig = e->big;

	/* d e nil => d nil */
	if(fhigh == nil)
		dlow->high = nil;
	if(fbig == nil)
		dsmall->big = nil;

	/* nil e f => nil f */
	if(dlow == nil)
		fhigh->low = nil;
	if(dsmall == nil)
		fbig->small = nil;

	if(dlow != nil && fhigh != nil){
		dlow->high = fhigh;
		fhigh->low = dlow;
	}
	if(dsmall != nil && fbig != nil){
		dsmall->big = fbig;
		fbig->small = dsmall;
	}
	start = e->start;
	es->n--;
	free(e);
	return start;
}

/* leave the position in the lrus and starts the same */
u64
slice(Extents *es, Extent *e, u64 len)
{
	u64 oldstart;
	Extent *d, *f;

	if(es == nil || e == nil || es->lowest == nil || len == 0 || e->len <= len){
		showextentslists(2, "slice() panic\n", es);
		panic("slice(): should not happen es %8#p e %8#p es->lru %8#p len %llud e->len %llud",
				es, e, es->lru, len, e->len);
	}
	oldstart = e->start;
	e->start += len;
	e->len -= len;

	/* this is the only extent, nothing more to do */
	if(es->n == 1)
		goto Sliced;

	/*
		change position in the size linked list
		d e f => d f, add e somewhere below d where it belongs
	 */
	d = e->small;
	f = e->big;
	/* already the smallest, nothing more to do */
	if(d == nil)
		goto Sliced;
	d->big = f;
	if(f != nil)
		f->small = d;
	/*
		removed e from the sized linked list.
		Now, move it below
	 */
	while(d != nil &&
			(e->len < d->len ||
			(e->len == d->len && e->start < d->start))){
		f = d;
		d = d->small;
	}
	e->small = d;
	e->big = f;
	if(d != nil)
		d->big = e;
	if(f != nil)
		f->small = e;

Sliced:
	intolrus(es, e);
	return oldstart;
}

/* allocate n blocks and return that block number */
u64
balloc(Extents *es, u64 n)
{
	Extent *e, *euse;
	u64 start;
	char msg[64];
	s64 dir;

	if(es == nil)
		panic("balloc: es == nil");
	if(es->n == 0)
		panic("balloc entering es->n == 0\n");
	start = 0;
	USED(start);
	qlock(&es->lck);
	if(es->n == 0)
		rsleep(&es->isempty);
	if(chatty9p > 7){
		snprint(msg, 64, "balloc() %llud blocks:\n", n);
		showextentslists(2, msg, es);
	}
again:
	e = euse = searchlrusbysize(es, n, &dir);
	if(chatty9p > 7)
		fprint(2, "balloc() searchlrusbysize() euse %8#p dir %lld \n", euse, dir);
	if(dir == 0){
		while(e != nil && n == e->len){
			euse = e;
			e = e->small;
		}
		e = euse;
	}else if(dir < 0){
		while(e != nil && n <= e->len){
			euse = e;
			e = e->small;
		}
		e = euse;
	}else /* if(dir > 0) */{
		while(e != nil && n > e->len){
			e = e->big;
		}
		/* e == nil when nothing is available */
	}
/*	for(e = lowest(es); e != nil && e->len < n; e = e->high)
		; */
	if(e == nil){
		snprint(msg, 64, "balloc() %llud %s: waiting\n", n, es->name);
		showextents(2, msg, es);
		if(es->flush){
			qunlock(&es->lck);
			(*es->flush)();
			qlock(&es->lck);
		}else
			rsleep(&es->isempty);
		goto again;
	}
	else if(e->len == n)
		start = pluck(es, e);
	else /* found something bigger */
		start = slice(es, e, n);

//		snprint(msg, 64, "balloc()'ed start %llud len %llud blocks:\n", start, n);
//		showextentswithsize(2, msg, es);
	if(es->n == 0)
		panic("balloc exiting es->n == 0\n");
	qunlock(&es->lck);
	/* uncomment the below line and the other in bfree() for
		generating test cases of unforeseen behaviour */
	if(extentsfd > 0)
		fprint(extentsfd, "%s-%llud %llud\n", es->name, start, n);
	return start;
}

/*
 reallocate n blocks to nnew blocks and return that block number
   It is upto the caller to copy the contents and bfree() the old
   block number if the returned block number <> old block number.
   Not providing brealloc() as we would need access to the contents
   to copy stuff over.
 free n blocks allocated at block number
 */
void
bfree(Extents *es, u64 start, u64 len)
{
//	char msg[64];

	if(es == nil)
		panic("bfree: es == nil");
	if(len <= 0)
		panic("bfree: len <= 0");
	/* uncomment the below line and the other in balloc() for
		generating test cases of unforeseen behaviour */
	if(extentsfd > 0)
		fprint(extentsfd, "%s+%llud %llud\n", es->name, start, len);
	qlock(&es->lck);
	add(es, start, len);
//		snprint(msg, 64, "bfree()d start %llud len %llud blocks:\n", start, len);
//		showextentswithsize(2, msg, es);
//	if(es->n == 1) the sleeper could just be waiting for a different len block
		rwakeup(&es->isempty);
	if(es->n == 0)
		panic("bfree exiting es->n == 0\n");
	qunlock(&es->lck);
}

/* count the total number of free blocks */
u64
nfrees(Extents *es)
{
	u64 n = 0;
	Extent *e;

	if(es == nil)
		panic("nfrees: es == nil");
	qlock(&es->lck);
	for(e = lowest(es); e != nil; e = e->high){
		n += e->len;
	}
	qunlock(&es->lck);
	return n;
}

/* string length when the extents are written as a string */
s32
sizeofextents(Extents *es)
{
	u64 n, used;
	s8 tmp[128];
	Extent *e;

	used = 0;
	qlock(&es->lck);
	for(e = lowest(es); e != nil; e = e->high){
		n = snprint(tmp, 128, "%llud %llud %llud\n",
						e->start, e->start+e->len-1, e->len);
		if(n == 128)
			panic("sizeofextents(): increase tmp size");
		used += n;
	}
	// keep it locked?
	qunlock(&es->lck);
	return used;
}
/*
	write to *buf returns the length written.
	Ensure that nbuf has an extra byte at the end
	as snprint() alway places a terminating NUL byte.
	If there is no extra byte, the content gets trimmed.
 */
s32
saveextents(Extents *es, s8 *buf, u32 nbuf)
{
	u64 used;
	Extent *e;
	s32 ret;

	used = 0;
	qlock(&es->lck);
	for(e = lowest(es); e != nil; e = e->high){
		used += snprint(buf+used, nbuf-used,
						"%llud %llud %llud\n",
						e->start, e->start+e->len-1, e->len);
		if(used >= nbuf){
			panic("saveextents(): increase buf size");
			ret = -1;	/* increase buf size */
			goto end;
		}
	}
	ret = used;
	// keep it locked?
end:
	qunlock(&es->lck);
	return ret;
}

/* load the extents from buf of length nbuf */
/* make this be called multiple times to add more extents - not needed now */
/* assumes that the input is in ascending order of block numbers */
s32
loadextents(Extents *es, s8 *buf, u32 nbuf)
{
	s8 *p, *ep;
	u64 start, end, nblocks;

	p = buf;
	if(es->lru != nil || es->n != 0){
		panic("extents already loaded.\n"
			"	TODO make loadextents() be called multiple times");
	}
	while(*p != 0 && p-buf < nbuf){
		start = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");

		p = ep;
		p += 1; /* skip over the space */
		end = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");

		p = ep;
		p += 1; /* skip over the space */
		nblocks = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");
		if(end-start+1 != nblocks)
			panic("loadextents does not match up: start %llud end %llud nblocks %llud",
					start, end, nblocks);

		p = ep;
		p++; /* to skip over the new line */
		bfree(es, start, nblocks);
	}
	return es->n;
}

void
showextent(int fd, char *pre, Extent *e)
{
//	fprint(fd, "%s	prev %8#p small %8#p low %8#p	e %8#p %llud len %llud	next %8#p high %8#p big %8#p",
//			pre, e->prev, e->small, e->low, e, e->start, e->len, e->next, e->high, e->big);
	fprint(fd, "%s%llud %llud %llud"
				"		e %8#p"
				"		%8#p lru %8#p"
				"		%8#p start %8#p"
				"		%8#p len %8#p\n",
			pre, e->start, e->start+e->len-1, e->len,
			e,
			e->prev, e->next,
			e->low, e->high,
			e->small, e->big);
}

void
showextentspointers(int fd, char *msg, Extents *es)
{
	Extent *e;

	fprint(fd, "%s", msg);
	fprint(fd, "Extents %s n %llud lowest %8#p lru %8#p nlru %d\n",
				es->name, es->n, es->lowest, es->lru, es->nlru);
	fprint(fd, "by blkno:\n");
	for(e = lowest(es); e != nil; e = e->high){
		fprint(fd, "%llud %llud %llud\n", e->start, e->start+e->len-1, e->len);
		// showextent(fd, "	", e);
	}
}

void
showextentslists(int fd, char *msg, Extents *es)
{
	Extent *e;

	fprint(fd, "%s", msg);
	fprint(fd, "Extents %s n %llud", es->name, es->n);
	if(es->lowest)
		fprint(fd, " lowest (%llud %llud %llud)",
				es->lowest->start,
				es->lowest->start+es->lowest->len-1,
				es->lowest->len);
	else
		fprint(fd, " lowest %8#p", es->lowest);

	if(es->lru)
		fprint(fd, " lru (%llud %llud %llud) ",
				es->lru->start,
				es->lru->start+es->lru->len-1,
				es->lru->len);
	else
		fprint(fd, " lru %8#p ", es->lru);
	fprint(fd, "nlru %d\n", es->nlru);

	fprint(fd, "by blkno:\n");
	for(e = lowest(es); e != nil; e = e->high){
		fprint(fd, "%llud %llud %llud\n", e->start, e->start+e->len-1, e->len);
		// showextent(fd, "	", e);
	}
	if(es->lowest != nil){
		fprint(fd, "by size:\n");
		for(e = smallest(es); e != nil; e = e->big){
			fprint(fd, "%llud %llud %llud\n", e->start, e->start+e->len-1, e->len);
			// showextent(fd, "	", e);
		}
	}
	if(es->lru != nil){
		fprint(fd, "lru:\n");
		e = es->lru;
		do{
			fprint(fd, "%llud %llud %llud\n", e->start, e->start+e->len-1, e->len);
			e=e->next;
		}while(e != nil && e != es->lru);
	}
}

void
showextents(int fd, char *msg, Extents *es)
{
	Extent *e;

	fprint(fd, "%s", msg);
	for(e = lowest(es); e != nil; e = e->high){
		fprint(fd, "%llud %llud %llud", e->start, e->start+e->len-1, e->len);
		// showextent(fd, "	", e);
		fprint(fd, "\n");
	}
}

void
showblocknos(int fd, Extents *es)
{
	Extent *e;
	u64 i;

	for(e = lowest(es); e != nil; e = e->high)
		for(i = e->start; i<e->start+e->len; i++)
			fprint(fd, "%llud\n", i);
}

void *
emalloc(u32 sz)
{
	void *v;

	if((v = mallocz(sz, 1)) == nil)
		sysfatal("emalloc: %r");

	setmalloctag(v, getcallerpc(&sz));
	return v;
}

s8 *
estrdup(s8 *s)
{
	s8 *p;

	p = strdup(s);
	if(p == nil)
		sysfatal("estrdup: %r");
	setmalloctag(p, getcallerpc(&s));
	return p;
}

void
initextents(Extents *es, char *name, void (*flush)(void))
{
/*	if(extentsfd < 1)
		extentsfd = open("/mnt/term/tmp/extents.raw", OWRITE);*/

	es->isempty.l = &es->lck;
	if(name != nil)
		strncpy(es->name, name, 32);
	es->flush = flush;
}

/*
	Prepare an extents with the holes of es.
	Given used blocks, shows the free blocks.
 */
Extents *
holes(Extents *es, Extents *inv)
{
	Extent *e;
	u64 start;

	if(es == nil || inv == nil)
		return nil;
	for(e=lowest(es); e!=nil && e->high != nil; e=e->high){
		start = e->start+e->len;
		bfree(inv, start, e->high->start-start);
	}
	return inv;
}