code: mafs

Download patch

ref: 2384cc1cb309d0759ad6790eea79f903d04ebad5
parent: eda51ffbd5c5697bf0578eaff6874133a6d480d8
author: 9ferno <gophone2015@gmail.com>
date: Sat Dec 24 18:09:31 EST 2022 

cleaned up the extents code

diff: cannot open b/tests/extents/0//null: file does not exist: 'b/tests/extents/0//null' diff: cannot open b/tests/extents/1//null: file does not exist: 'b/tests/extents/1//null' 
--- a/TODO
+++ b/TODO
@@ -1,9 +1,9 @@
+update mafs.ms document
+install from cd, use mafs as a root fs
+
 write Dentry blocks using text instead of using binary
 	similar to showblock() but the other way, writeblock()
 address the fragmentation of memunits
-sort extents by size
-	does that help?
-		finds stuff quicker - really, by how much?
 disk/used
 	check that the file size is matched by the number of blocks
 test exclusive use file access
--- a/extents.c
+++ b/extents.c
@@ -19,22 +19,17 @@
 void	showextent(int fd, char *pre, Extent *e);
 
 s64
-belongs(Extent *e, u64 start, u64 len)
+belongs(Extent *e, u64 start)
 {
 	if(e == nil)
 		sysfatal("belongs: e == nil");
-	if(start+len == e->start || start == e->start+e->len)
+	if(e->start+e->len == start)
 		return 0;
-	if(start >= e->start && start <= e->start+e->len)
-		panic("belongs: inconsistent"
-				" e->start %llud e->len %llud"
-				" start %llud len %llud\n",
-				e->start, e->len, start, len);
-	return start+len-e->start;
+	return start-e->start;
 }
 
 Extent *
-searchlrus(Extents *es, u64 blkno, u64 len, s64 *closest)
+searchlrus(Extents *es, u64 blkno, s64 *closest)
 {
 	Extent *e, *eclosest;
 	s64 howclose;
@@ -43,11 +38,11 @@
 		panic("searchlrus: should not happen");;
 
 	eclosest = e = es->lru;
-	*closest = belongs(e, blkno, len);
-	if(closest == 0)
+	*closest = belongs(e, blkno);
+	if(*closest == 0)
 		return es->lru;
 	for(e = e->next; e != es->lru; e = e->next){
-		howclose = belongs(e, blkno, len);
+		howclose = belongs(e, blkno);
 		if(abs(howclose) < abs(*closest)){
 			eclosest = e;
 			*closest = howclose;
@@ -58,7 +53,7 @@
 	return eclosest;
 }
 
-/* TODO check len and start and not just len */
+/* TODO? check len and start and not just len */
 Extent *
 searchlrusbysize(Extents *es, u64 len, s64 *closest)
 {
@@ -122,7 +117,8 @@
 		else if(d != nil)
 			es->lru = d;
 		else
-			es->lru = nil;
+			panic("removefromlrus(): should not be happening\n");
+			// es->lru = nil;
 }
 
 Extent *
@@ -137,7 +133,8 @@
 		removefromlrus(es, e);
 
 	if(es->lru == nil){
-		es->lru = e->prev = e->next = e;
+		e->prev = e->next = e;
+		es->nlru = 1;
 	}else if(es->nlru >= Nlru){
 		/*
 			y z lru
@@ -226,7 +223,7 @@
 	if(es == nil)
 		panic("arrangebysize es == nil");
 	if(chatty9p > 7)
-	fprint(2, "addbysize es->lowest %8#p e %8#p es->n %ud es->lru %8#p\n", es->lowest, e, es->n, es->lru);
+	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(es->lowest == e && es->n == 1 &&
 		e->low == nil && e->high == nil){
@@ -236,7 +233,7 @@
 	}
 
 	if(chatty9p > 7)
-		print("addbysize es->n %ud e->start %llud e->len %llud\n", es->n, e->start, e->len);
+		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 */
@@ -337,38 +334,6 @@
 }
 
 Extent *
-arrangebysize(Extents *es, Extent *e)
-{
-	Extent *dsmall, *fbig;
-
-	if(es == nil || e == nil)
-		panic("arrangebysize es == nil");
-	if(es->lowest == e && es->n == 1 &&
-		e->low == nil && e->high == nil){
-		/* the only extent */
-		e->small = e->big = nil;
-	}
-	if(chatty9p > 7){
-		print("arrangebysize %llud %llud\n", e->start, e->len);
-		showextents(1, "arrangebysize\n", es);
-	}
-	/* d e f => d f */
-	dsmall = e->small;
-	fbig = e->big;
-	if(dsmall != nil && fbig != nil){
-		fbig->small = dsmall;
-		dsmall->big = fbig;
-	}else if(dsmall == nil && fbig != nil)
-		fbig->small = nil;
-	else if(dsmall != nil && fbig == nil)
-		dsmall->big = nil;
-	e->small = e->big = nil;
-	if(chatty9p > 7)
-	showextents(1, "arrangebysize before addbysize\n", es);
-	return addbysize(es, e);
-}
-
-Extent *
 addextent(Extents *es, Extent *e, u64 start, u64 len)
 {
 	Extent *c;
@@ -391,7 +356,7 @@
 		c->low = e->low;
 		e->low = c;
 		c->high = e;
-		return intolrus(es, addbysize(es, c));
+		return addbysize(es, c);
 	}
 	if(start > e->start){
 		/* e e->high =>
@@ -402,7 +367,7 @@
 		c->high = e->high;
 		e->high = c;
 		c->low = e;
-		return intolrus(es, addbysize(es, c));
+		return addbysize(es, c);
 	}
 	print("addextent: should not be here e->start"
 			" %llud .. %llud start %llud len %llud\n",
@@ -411,118 +376,138 @@
 	return nil;
 }
 
-/*
-	in d e f g
-		e = e+f
-	becomes d e g
- */
+/* e start f => e+start+f */
 Extent *
-mergenext(Extents *es, Extent *e)
+mergeboth(Extents *es, Extent *e, u64 start, u64 len, Extent *f)
 {
-	Extent *f, *g, *fsmall, *fbig;
+	Extent *small, *big;
 
-	if(e == nil)
-		return e;
+	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");
 
-	/* at the highest extent */
-	if(e->high == nil)
-		return e;
-	if(e->start + e->len == e->high->start){
-		f = e->high;
-		fsmall = f->small;
-		fbig = f->big;
-		if(f != nil)
-			g = f->high;
-		else
-			g = nil;
-		/* skipping f */
-		e->len += f->len;
-		if(g != nil)
-			g->low = e;
-		e->high = g;
-		if(fsmall != nil)
-			fsmall->big = fbig;
-		if(fbig != nil)
-			fbig->small = fsmall;
+	/* 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;
 
-		removefromlrus(es, f);
-		free(f);
-		es->n--;
-		return e;
+	/* 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;
 }
 
-/*
-	in c d e f
-		d = d+e
-	becomes c d f
- */
+/* e start f => e+start f */
 Extent *
-mergeprevious(Extents *es, Extent *e)
+mergeprevious(Extents *es, Extent *e, u64 start, u64 len)
 {
-	Extent *d, *f, *dsmall, *fbig;
+	Extent *small, *big;
 
-	if(e == nil)
-		return e;
+	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");
 
-	/* at the lowest extent */
-	if(e->low == nil){
+	/* 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;
-		return e;
-	}
-	if(e->low->start+e->low->len == e->start){
-		d = e->low;
-		f = e->high;
-		dsmall = e->small;
-		fbig = e->big;
-		/* skipping e */
-		if(d != nil){
-			d->len += e->len;
-			d->high = f;
-		}
-		if(f != nil)
-			f->low = d;
-		/* skipping e */
-		if(dsmall != nil)
-			dsmall->big = fbig;
-		if(fbig != nil)
-			fbig->small = dsmall;
 
-		removefromlrus(es, e);
-		free(e);
-		es->n--;
-		if(d->low == nil)
-			es->lowest = d;
-		return d;
+	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 *
-increment(Extents *es, Extent *e, u64 start, u64 len)
+mergenext(Extents *es, Extent *e, u64 start, u64 len)
 {
-	Extent *d;
+	Extent *small, *big;
 
-	if(e == nil)
-		return e;
-	removefromlrus(es, e);
-	if(start+len == e->start){
-		e->start = start;
-		e->len += len;
-		d = mergeprevious(es, e);
-		if(d != e)
-			removefromlrus(es, d);
-		return intolrus(es, arrangebysize(es, d));
+	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;
 	}
-	if(start == e->start+e->len){
-		e->len += len;
-		return intolrus(es, arrangebysize(es, mergenext(es, e)));
-	}
-	print("increment: should not be here"
-		" e->start %llud .. %llud start %llud len %llud\n",
-		e->start, e->start+e->len-1, start, len);
-	abort();
+	e->small = small;
+	e->big = big;
+	if(small != nil)
+		small->big = e;
+	if(big != nil)
+		big->small = e;
 	return e;
 }
 
@@ -535,65 +520,83 @@
 doadd(Extents *es, u64 start, u64 len)
 {
 	s64 dir;
-	Extent *e, *eprev;
+	Extent *e, *d, *f;
 
 	if(es == nil)
 		panic("add es == nil");
-	if(es->lru == 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->lru = es->lowest = e->prev = e->next = e;
+		es->lowest = e;
 		es->n = 1;
 		return e;
 	}
 
-	/* using the previously used extent */
-	eprev = e = searchlrus(es, start, len, &dir);
+	/* 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 %p %p start %llud %llud %llud) %lld\n",
+		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){
-		while((dir = belongs(e, start, len)) < 0){
-			eprev = e;
+
+	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;
-			if(e == nil)
-				break;
 		}
-		/* e->low e eprev */
-		if(dir == 0)
-			return increment(es, e, start, len);
-		if(e == nil)
-			/* at the lowest extent, add below or above */
-			return addextent(es, eprev, start, len);
+		/* 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);
 
-		/* dir(e) > 0, hence, e < start < eprev */
-		return addextent(es, eprev, start, len);
-	}else if(dir > 0){
-		while((dir = belongs(e, start, len)) > 0){
-			eprev = e;
+		/* 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;
-			if(e == nil)
-				break;
 		}
-		/* eprev e e->high */
-		if(dir == 0)
-			return increment(es, e, start, len);
-		if(e == nil)
-			/* at the highest extent, add below or above */
-			return addextent(es, eprev, start, len);
+		/* 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);
 
-		/* dir(e) < 0, hence, eprev < start < e */
-		return addextent(es, eprev, start, len);
-	}
+		/* d start e => d+start e */
+		if(d != nil && d->start+d->len == start)
+			return mergeprevious(es, d, start, len);
 
-	/* dir == 0 */
-	return increment(es, e, 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 *
@@ -605,13 +608,16 @@
 		showextents(2, "		before\n", es);
 		fprint(2, " +%llud %llud\n", start, len);
 	}
-	e = doadd(es, start, len);
-	es->lru = e;
+	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)
 {
@@ -618,11 +624,10 @@
 	Extent *dlow, *fhigh, *dsmall, *fbig;
 	u64 start;
 
-	if(es == nil || e == nil || es->lru == nil)
+	if(es == nil || e == nil || es->lowest == nil)
 		panic("pluck(): should not happen");
 
-	if(es->lowest == e)
-		es->lowest = e->high;
+	removefromlrus(es, e);
 
 	/* if e is the only entry in es */
 	if(e->low == nil && e->high == nil){
@@ -629,35 +634,29 @@
 		es->lowest = nil;
 		es->n = 0;
 		start = e->start;
-		removefromlrus(es, e);
 		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;
-	dsmall = e->small;
 	fhigh = e->high;
+	dsmall = e->small;
 	fbig = e->big;
-	removefromlrus(es, e);
 
 	/* d e nil => d nil */
-	if(fhigh == nil){
+	if(fhigh == nil)
 		dlow->high = nil;
-		intolrus(es, dlow);
-		es->n--;
-	}
 	if(fbig == nil)
 		dsmall->big = nil;
 
 	/* nil e f => nil f */
-	if(dlow == nil){
+	if(dlow == nil)
 		fhigh->low = nil;
-		es->lowest = fhigh;
-		intolrus(es, fhigh);
-		es->n--;
-	}
 	if(dsmall == nil)
 		fbig->small = nil;
 
@@ -664,8 +663,6 @@
 	if(dlow != nil && fhigh != nil){
 		dlow->high = fhigh;
 		fhigh->low = dlow;
-		intolrus(es, fhigh);
-		es->n--;
 	}
 	if(dsmall != nil && fbig != nil){
 		dsmall->big = fbig;
@@ -672,23 +669,60 @@
 		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, oldlen;
+	u64 oldstart;
+	Extent *d, *f;
 
-	if(es == nil || e == nil || es->lru == nil || len == 0 || e->len <= len){
+	if(es == nil || e == nil || es->lowest == nil || len == 0 || e->len <= len){
 		showextentswithsize(2, "slice() panic\n", es);
-		panic("pluck(): should not happen es %8#p e %8#p es->lru %8#p len %llud e->len %llud",
+		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);
 	}
-	oldlen = e->len;
-	oldstart = pluck(es, e);
-	add(es, oldstart+len, oldlen - len);
+	oldstart = e->start;
+	e->start += len;
+	e->len -= len;
+
+	/* this is the only extent, nothing more to do */
+	if(es->n == 1)
+		return oldstart;
+
+	/*
+		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)
+		return oldstart;
+	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;
+	intolrus(es, e);
 	return oldstart;
 }
 
@@ -730,13 +764,9 @@
 		e = euse;
 	}else /* if(dir > 0) */{
 		while(e != nil && n > e->len){
-			euse = e;
 			e = e->big;
 		}
-		if(e == nil) /* nothing available */
-			euse = nil;
-		else
-			euse = e;
+		/* e == nil when nothing is available */
 	}
 /*	for(e = lowest(es); e != nil && e->len < n; e = e->high)
 		; */
@@ -756,6 +786,8 @@
 	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);
 	qunlock(&es->lck);
 	return start;
 }
@@ -771,6 +803,8 @@
 void
 bfree(Extents *es, u64 start, u64 len)
 {
+	char msg[64];
+
 	if(es == nil)
 		panic("bfree: es == nil");
 	if(len <= 0)
@@ -777,6 +811,8 @@
 		panic("bfree: len <= 0");
 	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);
 	qunlock(&es->lck);
@@ -896,8 +932,18 @@
 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	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
@@ -906,10 +952,11 @@
 	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);
 	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");
 	}
 	if(es->lowest != nil){
 		fprint(fd, "by size:\n");
@@ -916,7 +963,6 @@
 		for(e = smallest(es); e != nil; e = e->big){
 			// fprint(fd, "%llud %llud %llud", e->start, e->start+e->len-1, e->len);
 			showextent(fd, "	", e);
-			fprint(fd, "\n");
 		}
 	}
 }
@@ -1023,69 +1069,3 @@
 	}
 	return 0;
 } */
-
-/* obsolete, blows up the stack */
-Extent *
-doadd_recursive(Extents *es, u64 start, u64 len)
-{
-	s64 dir;
-	Extent *e;
-
-	if(es == nil)
-		panic("add es == nil");
-	if(es->lru == nil){
-		e = emalloc(sizeof(Extent));
-		e->low = e->high = nil;
-		e->start = start;
-		e->len = len;
-		es->lru = es->lowest = e;
-		es->n = 1;
-		return e;
-	}
-
-	/* using the previously used extent */
-	e = es->lru;
-	dir = belongs(es->lru, start, len);
-	if(chatty9p > 7){
-		print(" 	belongs(e %llud %llud start %llud .. %llud) %lld\n",
-			 e->start, e->start+e->len-1, start, start+len-1, dir);
-	}
-	if(dir == 0)
-		return increment(es, e, start, len);
-	else if(dir < 0){
-		if(e->low == nil)
-			/* at the lowest extent, add a prev */
-			return addextent(es, e, start, len);
-		else if(e->low->start+e->low->len == start)
-			/* belongs in the ->low extent */
-			return increment(es, e->low, start, len);
-		else if(e->low->start+e->low->len < start)
-			/* between the e->low and e */
-			return addextent(es, e->low, start, len);
-		else{
-			/* search from e->low */
-			es->lru = e->low;
-			return doadd(es, start, len);
-		}
-	}else if(dir > 0){
-		if(e->high == nil)
-			/* at the highest extent, add the next */
-			return addextent(es, e, start, len);
-		else if(start+len == e->high->start)
-			/* belongs in the ->high extent */
-			return increment(es, e->high, start, len);
-		else if(start+len < e->high->start)
-			/* between e and e->high */
-			return addextent(es, e, start, len);
-		else{
-			es->lru = e->high;
-			/* search from e->high */
-			return doadd(es, start, len);
-		}
-	}
-	/* dir == 0 */
-	sysfatal("add: should not be here"
-		 " e->start %llud .. %llud start %llud len %llud\n",
-		  e->start, e->start+e->len-1, start, len);
-	return e;
-}
--- a/extents.h
+++ b/extents.h
@@ -24,7 +24,7 @@
 struct Extents {
 	Extent *lowest;	/* find the first block number in a jiffy */
 	QLock lck;
-	u32 n;			/* number of extents */
+	u64 n;			/* number of extents */
 	Rendez isempty; /* fully used, nothing available */
 
 	u8 nlru;		/* number of items in the lru linked list */
--- /dev/null
+++ b/tests/extents/0/input
@@ -1,0 +1,9 @@
+1 13
+16399 2048
+20495 2048
+26639 2048
+30735 2048
+55311 2048
+59407 2048
+63503 2033
+18447 2048
--- /dev/null
+++ b/tests/extents/0/output
@@ -1,0 +1,16 @@
+Extents testextents n 7 lowest 0x409238 lru 0x409298 nlru 7
+	1 13 13		e 0x409238		0x409358 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x4094d8
+	16399 22542 6144		e 0x409298		0x409238 lru 0x4094d8		0x409238 start 0x409358		0x409478 len      0x0
+	26639 28686 2048		e 0x409358		0x4093b8 lru 0x409238		0x409298 start 0x4093b8		0x4094d8 len 0x4093b8
+	30735 32782 2048		e 0x4093b8		0x409418 lru 0x409358		0x409358 start 0x409418		0x409358 len 0x409418
+	55311 57358 2048		e 0x409418		0x409478 lru 0x4093b8		0x4093b8 start 0x409478		0x4093b8 len 0x409478
+	59407 61454 2048		e 0x409478		0x4094d8 lru 0x409418		0x409418 start 0x4094d8		0x409418 len 0x409298
+	63503 65535 2033		e 0x4094d8		0x409298 lru 0x409478		0x409478 start      0x0		0x409238 len 0x409358
+by size:
+	1 13 13		e 0x409238		0x409358 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x4094d8
+	63503 65535 2033		e 0x4094d8		0x409298 lru 0x409478		0x409478 start      0x0		0x409238 len 0x409358
+	26639 28686 2048		e 0x409358		0x4093b8 lru 0x409238		0x409298 start 0x4093b8		0x4094d8 len 0x4093b8
+	30735 32782 2048		e 0x4093b8		0x409418 lru 0x409358		0x409358 start 0x409418		0x409358 len 0x409418
+	55311 57358 2048		e 0x409418		0x409478 lru 0x4093b8		0x4093b8 start 0x409478		0x4093b8 len 0x409478
+	59407 61454 2048		e 0x409478		0x4094d8 lru 0x409418		0x409418 start 0x4094d8		0x409418 len 0x409298
+	16399 22542 6144		e 0x409298		0x409238 lru 0x4094d8		0x409238 start 0x409358		0x409478 len      0x0
--- /dev/null
+++ b/tests/extents/1/input
@@ -1,0 +1,12 @@
+0 2
+3 11
+6159 2048
+10255 4096
+16399 2048
+20495 2048
+24591 2048
+40975 2048
+59407 2048
+64649 887
+14351 2048
+2 1
--- /dev/null
+++ b/tests/extents/1/output
@@ -1,0 +1,18 @@
+Extents testextents n 8 lowest 0x409238 lru 0x409238 nlru 8
+	0 13 14		e 0x409238		0x4092f8 lru 0x409358		     0x0 start 0x4092f8		     0x0 len 0x409598
+	6159 8206 2048		e 0x4092f8		0x409418 lru 0x409238		0x409238 start 0x409358		0x409598 len 0x409418
+	10255 18446 8192		e 0x409358		0x409238 lru 0x409598		0x4092f8 start 0x409418		0x409538 len      0x0
+	20495 22542 2048		e 0x409418		0x409478 lru 0x4092f8		0x409358 start 0x409478		0x4092f8 len 0x409478
+	24591 26638 2048		e 0x409478		0x4094d8 lru 0x409418		0x409418 start 0x4094d8		0x409418 len 0x4094d8
+	40975 43022 2048		e 0x4094d8		0x409538 lru 0x409478		0x409478 start 0x409538		0x409478 len 0x409538
+	59407 61454 2048		e 0x409538		0x409598 lru 0x4094d8		0x4094d8 start 0x409598		0x4094d8 len 0x409358
+	64649 65535 887		e 0x409598		0x409358 lru 0x409538		0x409538 start      0x0		0x409238 len 0x4092f8
+by size:
+	0 13 14		e 0x409238		0x4092f8 lru 0x409358		     0x0 start 0x4092f8		     0x0 len 0x409598
+	64649 65535 887		e 0x409598		0x409358 lru 0x409538		0x409538 start      0x0		0x409238 len 0x4092f8
+	6159 8206 2048		e 0x4092f8		0x409418 lru 0x409238		0x409238 start 0x409358		0x409598 len 0x409418
+	20495 22542 2048		e 0x409418		0x409478 lru 0x4092f8		0x409358 start 0x409478		0x4092f8 len 0x409478
+	24591 26638 2048		e 0x409478		0x4094d8 lru 0x409418		0x409418 start 0x4094d8		0x409418 len 0x4094d8
+	40975 43022 2048		e 0x4094d8		0x409538 lru 0x409478		0x409478 start 0x409538		0x409478 len 0x409538
+	59407 61454 2048		e 0x409538		0x409598 lru 0x4094d8		0x4094d8 start 0x409598		0x4094d8 len 0x409358
+	10255 18446 8192		e 0x409358		0x409238 lru 0x409598		0x4092f8 start 0x409418		0x409538 len      0x0
--- a/tests/extents/addabove/output
+++ b/tests/extents/addabove/output
@@ -1,5 +1,6 @@
-20 22 3
-40 43 4
+Extents testextents n 2 lowest 0x409238 lru 0x409298 nlru 2
+	20 22 3		e 0x409238		0x409298 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	40 43 4		e 0x409298		0x409238 lru 0x409238		0x409238 start      0x0		0x409238 len      0x0
 by size:
-20 22 3
-40 43 4
+	20 22 3		e 0x409238		0x409298 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	40 43 4		e 0x409298		0x409238 lru 0x409238		0x409238 start      0x0		0x409238 len      0x0
--- a/tests/extents/addabove1/output
+++ b/tests/extents/addabove1/output
@@ -1,5 +1,6 @@
-180 183 4
-250 253 4
+Extents testextents n 2 lowest 0x409238 lru 0x409298 nlru 2
+	180 183 4		e 0x409238		0x409298 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	250 253 4		e 0x409298		0x409238 lru 0x409238		0x409238 start      0x0		0x409238 len      0x0
 by size:
-180 183 4
-250 253 4
+	180 183 4		e 0x409238		0x409298 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	250 253 4		e 0x409298		0x409238 lru 0x409238		0x409238 start      0x0		0x409238 len      0x0
--- a/tests/extents/addbelow/output
+++ b/tests/extents/addbelow/output
@@ -1,5 +1,6 @@
-180 183 4
-250 253 4
+Extents testextents n 2 lowest 0x409298 lru 0x409298 nlru 2
+	180 183 4		e 0x409298		0x409238 lru 0x409238		     0x0 start 0x409238		     0x0 len 0x409238
+	250 253 4		e 0x409238		0x409298 lru 0x409298		0x409298 start      0x0		0x409298 len      0x0
 by size:
-180 183 4
-250 253 4
+	180 183 4		e 0x409298		0x409238 lru 0x409238		     0x0 start 0x409238		     0x0 len 0x409238
+	250 253 4		e 0x409238		0x409298 lru 0x409298		0x409298 start      0x0		0x409298 len      0x0
--- a/tests/extents/addbelow1/output
+++ b/tests/extents/addbelow1/output
@@ -1,7 +1,8 @@
-100 100 1
-180 183 4
-250 253 4
+Extents testextents n 3 lowest 0x4092f8 lru 0x4092f8 nlru 3
+	100 100 1		e 0x4092f8		0x409238 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	180 183 4		e 0x409298		0x4092f8 lru 0x409238		0x4092f8 start 0x409238		0x4092f8 len 0x409238
+	250 253 4		e 0x409238		0x409298 lru 0x4092f8		0x409298 start      0x0		0x409298 len      0x0
 by size:
-100 100 1
-180 183 4
-250 253 4
+	100 100 1		e 0x4092f8		0x409238 lru 0x409298		     0x0 start 0x409298		     0x0 len 0x409298
+	180 183 4		e 0x409298		0x4092f8 lru 0x409238		0x4092f8 start 0x409238		0x4092f8 len 0x409238
+	250 253 4		e 0x409238		0x409298 lru 0x4092f8		0x409298 start      0x0		0x409298 len      0x0
--- a/tests/extents/addbelow2/output
+++ b/tests/extents/addbelow2/output
@@ -1,7 +1,8 @@
-0 17 18
-22 24 3
-29 31 3
+Extents testextents n 3 lowest 0x409238 lru 0x409238 nlru 3
+	0 17 18		e 0x409238		0x409358 lru 0x4093b8		     0x0 start 0x4093b8		0x409358 len      0x0
+	22 24 3		e 0x4093b8		0x409238 lru 0x409358		0x409238 start 0x409358		     0x0 len 0x409358
+	29 31 3		e 0x409358		0x4093b8 lru 0x409238		0x4093b8 start      0x0		0x4093b8 len 0x409238
 by size:
-22 24 3
-29 31 3
-0 17 18
+	22 24 3		e 0x4093b8		0x409238 lru 0x409358		0x409238 start 0x409358		     0x0 len 0x409358
+	29 31 3		e 0x409358		0x4093b8 lru 0x409238		0x4093b8 start      0x0		0x4093b8 len 0x409238
+	0 17 18		e 0x409238		0x409358 lru 0x4093b8		     0x0 start 0x4093b8		0x409358 len      0x0
--- a/tests/extents/mergeabove/output
+++ b/tests/extents/mergeabove/output
@@ -1,3 +1,4 @@
-100 112 13
+Extents testextents n 1 lowest 0x409238 lru 0x409238 nlru 1
+	100 112 13		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0
 by size:
-100 112 13
+	100 112 13		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0
--- a/tests/extents/mergenext/output
+++ b/tests/extents/mergenext/output
@@ -1,3 +1,4 @@
-101 108 8
+Extents testextents n 1 lowest 0x409238 lru 0x409238 nlru 1
+	101 108 8		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0
 by size:
-101 108 8
+	101 108 8		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0
--- a/tests/extents/mergeprevious/output
+++ b/tests/extents/mergeprevious/output
@@ -1,3 +1,4 @@
-101 108 8
+Extents testextents n 1 lowest 0x409238 lru 0x409238 nlru 1
+	101 108 8		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0
 by size:
-101 108 8
+	101 108 8		e 0x409238		0x409238 lru 0x409238		     0x0 start      0x0		     0x0 len      0x0