code: mafs

Download patch

ref: eda51ffbd5c5697bf0578eaff6874133a6d480d8
parent: bcdbd28d00321d615839e60d46d61bc7352d2fb4
author: 9ferno <gophone2015@gmail.com>
date: Wed Dec 21 21:34:36 EST 2022

extents also sorted by size

--- a/extents.c
+++ b/extents.c
@@ -15,7 +15,7 @@
  * large extent, if they are continuous.
  */
 
-/* Extent *sortbysize(Extents *es, Extent *e); */
+Extent *sortbysize(Extents *es, Extent *e);
 void	showextent(int fd, char *pre, Extent *e);
 
 s64
@@ -51,45 +51,87 @@
 		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");
+	if(es->lru == nil){
+		*closest = len - es->lowest->len;
+		return es->lowest;
+	}
+
+	eclosest = e = es->lru;
+	*closest = len - e->len;
+	// print("searchlrusbysize len %llud e->len %llud\n", len, e->len);
+	if(closest == 0)
+		return es->lru;
+	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 *z, *a;
+	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->prev == e->next){
+	if(e == e->prev && e->prev == e->next){
 		e->prev = e->next = es->lru = nil;
 		es->nlru = 0;
 		return;
 	}
 
-	/* z e a => z a */
-	z = e->prev;
-	a = e->next;
+	/* d e f => d f */
+	d = e->prev;
+	f = e->next;
 
-	z->next = a;
-	a->prev = z;
+	if(d != nil)
+		d->next = f;
+	if(f != nil)
+		f->prev = d;
 	es->nlru--;
+	e->prev = e->next = nil;
 
 	if(es->lru == e)
-		es->lru = a;
+		if(f != nil)
+			es->lru = f;
+		else if(d != nil)
+			es->lru = d;
+		else
+			es->lru = nil;
 }
 
-void
+Extent *
 intolrus(Extents *es, Extent *e)
 {
 	Extent *y, *z;
 
 	if(e == nil || es == nil)
-		return;
+		return nil;
 
 	if(e->prev != nil)
 		removefromlrus(es, e);
@@ -127,9 +169,9 @@
 		es->nlru++;
 	}
 	es->lru = e;
+	return e;
 }
 
-/*
 Extent *
 smallest(Extents *es)
 {
@@ -152,18 +194,14 @@
 	for(e = es->lru; e!=nil && e->big != nil; e=e->big)
 		;
 	return e;
-} */
+}
 
 Extent *
 lowest(Extents *es)
 {
-	Extent *e;
-
-	if(es == nil || es->lru == nil || es->head == nil)
+	if(es == nil)
 		return nil;
-	for(e = es->head; e!= nil && e->low != nil; e=e->low)
-		;
-	return e;
+	return es->lowest;
 }
 
 Extent *
@@ -179,6 +217,158 @@
 }
 
 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 %ud 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){
+		/* the only extent */
+		e->small = e->big = nil;
+		return e;
+	}
+
+	if(chatty9p > 7)
+		print("addbysize es->n %ud 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(fbig != nil)
+		fbig->small = e;
+	e->big = fbig;
+	if(dsmall != nil)
+		dsmall->big = e;
+	e->small = dsmall;
+	return e;
+}
+
+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;
@@ -195,14 +385,13 @@
 			e->low c e
 		  */
 		if(e->low == nil)
-			es->head = c;
+			es->lowest = c;
 		else
 			e->low->high = c;
 		c->low = e->low;
 		e->low = c;
 		c->high = e;
-		intolrus(es, c);
-		return c;
+		return intolrus(es, addbysize(es, c));
 	}
 	if(start > e->start){
 		/* e e->high =>
@@ -213,8 +402,7 @@
 		c->high = e->high;
 		e->high = c;
 		c->low = e;
-		intolrus(es, c);
-		return c;
+		return intolrus(es, addbysize(es, c));
 	}
 	print("addextent: should not be here e->start"
 			" %llud .. %llud start %llud len %llud\n",
@@ -231,7 +419,7 @@
 Extent *
 mergenext(Extents *es, Extent *e)
 {
-	Extent *f, *g;
+	Extent *f, *g, *fsmall, *fbig;
 
 	if(e == nil)
 		return e;
@@ -241,6 +429,8 @@
 		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
@@ -250,11 +440,14 @@
 		if(g != nil)
 			g->low = e;
 		e->high = g;
+		if(fsmall != nil)
+			fsmall->big = fbig;
+		if(fbig != nil)
+			fbig->small = fsmall;
 
 		removefromlrus(es, f);
 		free(f);
 		es->n--;
-		intolrus(es, e);
 		return e;
 	}
 	return e;
@@ -268,17 +461,21 @@
 Extent *
 mergeprevious(Extents *es, Extent *e)
 {
-	Extent *d, *f;
+	Extent *d, *f, *dsmall, *fbig;
 
 	if(e == nil)
 		return e;
 
 	/* at the lowest extent */
-	if(e->low == nil)
+	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;
@@ -286,11 +483,17 @@
 		}
 		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--;
-		intolrus(es, d);
+		if(d->low == nil)
+			es->lowest = d;
 		return d;
 	}
 	return e;
@@ -299,17 +502,22 @@
 Extent *
 increment(Extents *es, Extent *e, u64 start, u64 len)
 {
+	Extent *d;
+
 	if(e == nil)
 		return e;
-	intolrus(es, e);
+	removefromlrus(es, e);
 	if(start+len == e->start){
 		e->start = start;
 		e->len += len;
-		return mergeprevious(es, e);
+		d = mergeprevious(es, e);
+		if(d != e)
+			removefromlrus(es, d);
+		return intolrus(es, arrangebysize(es, d));
 	}
 	if(start == e->start+e->len){
 		e->len += len;
-		return mergenext(es, e);
+		return intolrus(es, arrangebysize(es, mergenext(es, e)));
 	}
 	print("increment: should not be here"
 		" e->start %llud .. %llud start %llud len %llud\n",
@@ -333,10 +541,10 @@
 		panic("add es == nil");
 	if(es->lru == nil){
 		e = emalloc(sizeof(Extent));
-		e->low = e->high = nil;
+		e->low = e->high = e->small = e->big = nil;
 		e->start = start;
 		e->len = len;
-		es->lru = es->head = e->prev = e->next = e;
+		es->lru = es->lowest = e->prev = e->next = e;
 		es->n = 1;
 		return e;
 	}
@@ -407,15 +615,18 @@
 static u64
 pluck(Extents *es, Extent *e)
 {
-	Extent *dlow, *fhigh;
+	Extent *dlow, *fhigh, *dsmall, *fbig;
 	u64 start;
 
 	if(es == nil || e == nil || es->lru == nil)
 		panic("pluck(): should not happen");
 
+	if(es->lowest == e)
+		es->lowest = e->high;
+
 	/* if e is the only entry in es */
 	if(e->low == nil && e->high == nil){
-		es->head = nil;
+		es->lowest = nil;
 		es->n = 0;
 		start = e->start;
 		removefromlrus(es, e);
@@ -426,7 +637,9 @@
 	/* there are atleast 2 elements in the list */
 	/* d e f => d f */
 	dlow = e->low;
+	dsmall = e->small;
 	fhigh = e->high;
+	fbig = e->big;
 	removefromlrus(es, e);
 
 	/* d e nil => d nil */
@@ -435,14 +648,18 @@
 		intolrus(es, dlow);
 		es->n--;
 	}
+	if(fbig == nil)
+		dsmall->big = nil;
 
 	/* nil e f => nil f */
 	if(dlow == nil){
 		fhigh->low = nil;
-		es->head = fhigh;
+		es->lowest = fhigh;
 		intolrus(es, fhigh);
 		es->n--;
 	}
+	if(dsmall == nil)
+		fbig->small = nil;
 
 	if(dlow != nil && fhigh != nil){
 		dlow->high = fhigh;
@@ -450,6 +667,10 @@
 		intolrus(es, fhigh);
 		es->n--;
 	}
+	if(dsmall != nil && fbig != nil){
+		dsmall->big = fbig;
+		fbig->small = dsmall;
+	}
 	start = e->start;
 	free(e);
 	return start;
@@ -460,8 +681,11 @@
 {
 	u64 oldstart, oldlen;
 
-	if(es == nil || e == nil || es->lru == nil || len == 0 || e->len <= len)
-		panic("pluck(): should not happen");
+	if(es == nil || e == nil || es->lru == 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",
+				es, e, es->lru, len, e->len);
+	}
 	oldlen = e->len;
 	oldstart = pluck(es, e);
 	add(es, oldstart+len, oldlen - len);
@@ -472,9 +696,10 @@
 u64
 balloc(Extents *es, u64 n)
 {
-	Extent *e;
+	Extent *e, *euse;
 	u64 start;
 	char msg[64];
+	s64 dir;
 
 	if(es == nil)
 		panic("balloc: es == nil");
@@ -483,13 +708,38 @@
 	qlock(&es->lck);
 	if(es->n == 0)
 		rsleep(&es->isempty);
-/*	if(chatty9p > 7){
+	if(chatty9p > 7){
 		snprint(msg, 64, "balloc() %llud blocks:\n", n);
-		showextents(2, msg, es);
-	}*/
+		showextentswithsize(2, msg, es);
+	}
 again:
-	for(e = lowest(es); e != nil && e->len < n; e = e->high)
-		;
+	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){
+			euse = e;
+			e = e->big;
+		}
+		if(e == nil) /* nothing available */
+			euse = nil;
+		else
+			euse = e;
+	}
+/*	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);
@@ -646,11 +896,32 @@
 void
 showextent(int fd, char *pre, Extent *e)
 {
-	fprint(fd, "%s	low %8#p	e %8#p %llud %p len %llud	high %8#p",
-			pre, e->low, e, e->start, e->start, e->len, e->high);
+	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);
 }
 
 void
+showextentswithsize(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");
+	}
+	if(es->lowest != nil){
+		fprint(fd, "by size:\n");
+		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");
+		}
+	}
+}
+
+void
 showextents(int fd, char *msg, Extents *es)
 {
 	Extent *e;
@@ -658,7 +929,7 @@
 	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);
+		// showextent(fd, "	", e);
 		fprint(fd, "\n");
 	}
 }
@@ -753,7 +1024,7 @@
 	return 0;
 } */
 
-/* obsolete */
+/* obsolete, blows up the stack */
 Extent *
 doadd_recursive(Extents *es, u64 start, u64 len)
 {
@@ -767,7 +1038,7 @@
 		e->low = e->high = nil;
 		e->start = start;
 		e->len = len;
-		es->lru = es->head = e;
+		es->lru = es->lowest = e;
 		es->n = 1;
 		return e;
 	}
--- a/extents.h
+++ b/extents.h
@@ -14,7 +14,7 @@
 */
 struct Extent {
 	struct Extent *low, *high;	/* sorted by start */
-	/*struct Extent *small, *big;*//* sorted by the number of blocks in this extent */
+	struct Extent *small, *big;	/* sorted by the number of blocks in this extent */
 	u64 start;					/* where this extent starts from */
 	u64 len; 					/* how many units in this extent */
 
@@ -22,7 +22,7 @@
 	struct Extent *prev, *next;
 };
 struct Extents {
-	Extent *head;	/* find the first block in a jiffy */
+	Extent *lowest;	/* find the first block number in a jiffy */
 	QLock lck;
 	u32 n;			/* number of extents */
 	Rendez isempty; /* fully used, nothing available */
@@ -44,6 +44,7 @@
 
 void	showblocknos(int fd, Extents *es);
 void	showextents(int fd, char *msg, Extents *es);
+void	showextentswithsize(int fd, char *msg, Extents *es);
 s32	sizeofextents(Extents *es);
 s32	saveextents(Extents *es, s8 *buf, u32 nbuf);
 s32	loadextents(Extents *es, s8 *buf, u32 nbuf);
--- a/reconcile.c
+++ b/reconcile.c
@@ -112,8 +112,8 @@
 	u8 header = 0;
 	Extent *ue, *fe;
 
-	ue = u->es->head;
-	fe = f->es->head;
+	ue = u->es->lowest;
+	fe = f->es->lowest;
 	for(i = 0; i < nblocks; i++){
 		if(ue != nil && ue->start <= i && i < ue->start+ue->len){
 			if(i == ue->start+ue->len-1)
@@ -142,8 +142,8 @@
 	u8 header = 0;
 	Extent *ue, *fe;
 
-	ue = u->es->head;
-	fe = f->es->head;
+	ue = u->es->lowest;
+	fe = f->es->lowest;
 	if(fe == nil)	/* disk is full */
 		return;
 	for(i = 0; i < nblocks; i++){
--- a/tests/extents/addabove/output
+++ b/tests/extents/addabove/output
@@ -1,2 +1,5 @@
 20 22 3
 40 43 4
+by size:
+20 22 3
+40 43 4
--- a/tests/extents/addabove1/output
+++ b/tests/extents/addabove1/output
@@ -1,2 +1,5 @@
 180 183 4
 250 253 4
+by size:
+180 183 4
+250 253 4
--- a/tests/extents/addbelow/output
+++ b/tests/extents/addbelow/output
@@ -1,2 +1,5 @@
 180 183 4
 250 253 4
+by size:
+180 183 4
+250 253 4
--- a/tests/extents/addbelow1/output
+++ b/tests/extents/addbelow1/output
@@ -1,3 +1,7 @@
 100 100 1
 180 183 4
 250 253 4
+by size:
+100 100 1
+180 183 4
+250 253 4
--- a/tests/extents/addbelow2/output
+++ b/tests/extents/addbelow2/output
@@ -1,3 +1,7 @@
 0 17 18
 22 24 3
 29 31 3
+by size:
+22 24 3
+29 31 3
+0 17 18
--- a/tests/extents/mergeabove/output
+++ b/tests/extents/mergeabove/output
@@ -1,1 +1,3 @@
 100 112 13
+by size:
+100 112 13
--- a/tests/extents/mergenext/output
+++ b/tests/extents/mergenext/output
@@ -1,1 +1,3 @@
 101 108 8
+by size:
+101 108 8
--- a/tests/extents/mergeprevious/output
+++ b/tests/extents/mergeprevious/output
@@ -1,1 +1,3 @@
 101 108 8
+by size:
+101 108 8
--- a/tests/testextents.c
+++ b/tests/testextents.c
@@ -46,7 +46,7 @@
 		free(line);
 	}
 
-	showextents(1, "", &es);
+	showextentswithsize(1, "", &es);
 
 	/* why bother? just exits(nil) as cinap suggests */
 	Bterm(bp);