ref: eda51ffbd5c5697bf0578eaff6874133a6d480d8
parent: bcdbd28d00321d615839e60d46d61bc7352d2fb4
author: 9ferno <[email protected]>
date: Wed Dec 21 14: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);