ref: e96b9e14a06a019e20988fa6a80b8871d0db2c44
dir: /extents.c/
#include <u.h>
#include <libc.h>
#include "extents.h"
Extent *sortbysize(Extents *es, Extent *e);
void showextent(int fd, char *pre, Extent *e);
static int extentsfd = -1;
static Extent *
emalloc(void* (*malloc)(u32 sz))
{
return (Extent *) malloc(sizeof(Extent));
}
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)
es->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)
es->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
es->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)
es->panic("arrangebysize es == nil");
if(es->log && es->loglevel)
es->log(es->logfd, "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->log && es->loglevel)
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)
es->panic("addbysize: e == nil");
if(es->log && es->loglevel)
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(es->log && es->loglevel)
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(es->log && es->loglevel)
print("addbysize after scroll down eprev start %llud len %llud\n", eprev->start, eprev->len);
if(es->log && es->loglevel){
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(es->malloc);
c->start = start;
c->len = len;
addbysize(es, c);
es->n++;
if(es->log && es->loglevel)
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)
es->panic("mergeboth: should not be happening\n");;
if(e->start+e->len != start || start+len != f->start)
es->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)
es->panic("mergeprevious: should not be happening\n");;
if(e->start+e->len != start)
es->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)
es->panic("mergenext: should not be happening\n");;
if(start+len != e->start)
es->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)
es->panic("add es == nil");
if(es->n == 0){
e = emalloc(es->malloc);
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)
es->panic("doadd: e == nil");
if(es->log && es->loglevel){
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(es->log && es->loglevel){
showextents(2, " before\n", es);
es->log(es->logfd, " +%llud %llud\n", start, len);
}
e = intolrus(es, doadd(es, start, len));
if(es->log && es->loglevel)
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)
es->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(es->logfd, "slice() es->panic\n", es);
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 a status. start has a block number if allocated */
s8
ualloc(Extents *es, u64 n, u64 *start)
{
Extent *e, *euse;
char msg[64];
s64 dir;
if(es == nil)
es->panic("ualloc: es == nil");
qlock(&es->lck);
if(es->n == 0)
goto Empty;
if(es->loglevel == Everbose){
es->log(es->logfd, "ualloc() %llud blocks:\n", n);
}else if(es->loglevel == Edebug){
snprint(msg, 64, "ualloc() %llud blocks:\n", n);
showextentslists(es->logfd, msg, es);
}
again:
e = euse = searchlrusbysize(es, n, &dir);
if(es->log && es->loglevel)
es->log(es->logfd, "ualloc() 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){
Empty:
if(es->flush){
qunlock(&es->lck);
(*es->flush)();
qlock(&es->lck);
}else{
if(es->linger){
snprint(msg, 64, "ualloc() %llud %s: waiting\n", n, es->name);
showextents(2, msg, es);
rsleep(&es->isempty);
}else{
qunlock(&es->lck);
return 0;
}
}
goto again;
}
else if(e->len == n)
*start = pluck(es, e);
else{ /* found something bigger */
*start = slice(es, e, n);
}
if(es->log && es->loglevel == Everbose){
es->log(es->logfd, "ualloc()'ed start %llud len %llud blocks:\n", *start, n);
}else if(es->log && es->loglevel == Edebug){
snprint(msg, 64, "ualloc() %llud blocks:\n", n);
showextentslists(es->logfd, msg, es);
}
qunlock(&es->lck);
/* use to generate test cases of unforeseen behaviour */
if(es->log && es->loglevel)
es->log(es->logfd, "%s-%llud %llud\n", es->name, *start, n);
return 1;
}
/*
reallocate n blocks to nnew blocks and return that block number
It is upto the caller to copy the contents and qfree() 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
ufree(Extents *es, u64 start, u64 len)
{
char msg[64];
if(es == nil)
es->panic("qfree: es == nil");
if(len <= 0)
es->panic("qfree: len <= 0");
/* use to generate test cases of unforeseen behaviour */
if(es->log && es->loglevel)
es->log(es->logfd, "%s+%llud %llud\n", es->name, start, len);
qlock(&es->lck);
add(es, start, len);
if(es->log && es->loglevel == Everbose){
es->log(es->logfd, "qfree()d start %llud len %llud blocks:\n", start, len);
}else if(es->log && es->loglevel == Edebug){
snprint(msg, 64, "qfree()d start %llud len %llud blocks:\n", start, len);
showextentslists(es->logfd, msg, es);
}
// if(es->n == 1) the sleeper could just be waiting for a different len block
rwakeup(&es->isempty);
if(es->n == 0) /* should never happen */
es->panic("qfree 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)
es->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
sizeoftxtextents(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)
es->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
savetxtextents(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){
es->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
loadtxtextents(Extents *es, s8 *buf, u32 nbuf)
{
s8 *p, *ep;
u64 start, end, nblocks;
p = buf;
if(es->lru != nil || es->n != 0){
es->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)
es->panic("could not read");
p = ep;
p += 1; /* skip over the space */
end = strtoull(p, &ep, 10);
if(p == ep)
es->panic("could not read");
p = ep;
p += 1; /* skip over the space */
nblocks = strtoull(p, &ep, 10);
if(p == ep)
es->panic("could not read");
if(end-start+1 != nblocks)
es->panic("loadextents does not match up: start %llud end %llud nblocks %llud",
start, end, nblocks);
p = ep;
p++; /* to skip over the new line */
ufree(es, start, nblocks);
}
return es->n;
}
s32
sizeofextents(Extents *es)
{
/* Do I need a lock? */
return es->n*3*sizeof(u64);
}
/*
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 *p, *sp;
Extent *e;
sp = p = (u64*)buf;
qlock(&es->lck);
if(es->n*3*sizeof(u64) < nbuf){
qunlock(&es->lck);
return -1;
}
for(e = lowest(es); e != nil; e = e->high){
*p = e->start; p++;
*p = e->start+e->len-1; p++;
*p = e->len; p++;
}
qunlock(&es->lck);
return (s32)(p-sp);
}
/* 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)
{
u64 *p, *sp;
u64 start, end, nunits, n;
sp = p = (u64*)buf;
if(es->lru != nil || es->n != 0){
es->panic("extents already loaded.\n"
" Do I need to make loadextents() be called multiple times?");
}
for(n = nbuf/(3*sizeof(u64)); n>0; n--){
start = *p; p++;
end = *p; p++;
if(start == 0 && end == 0)
es->panic("loadextents(): nil extent");
nunits = *p; p++;
ufree(es, start, nunits);
}
return (s32)(p-sp);
}
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
initextents(Extents *es, char *name, u8 linger, u8 loglevel, u32 logfd, void (*flush)(void), int (*log)(int fd, char *fmt, ...), void (*panic)(char *fmt, ...), void *(*malloc)(u32 sz))
{
es->isempty.l = &es->lck;
if(name == nil)
es->name[0] = '\0';
else
strncpy(es->name, name, 32);
es->loglevel = loglevel;
es->logfd = logfd;
es->flush = flush;
es->linger = linger;
es->log = log;
es->panic = panic;
es->malloc = malloc;
}
void
freeextents(Extents *es)
{
Extent *e, *eh;
qlock(&es->lck);
for(e = eh = es->lowest; eh != nil; e = eh){
eh = e->high;
free(e);
}
free(es);
}
/*
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;
ufree(inv, start, e->high->start-start);
}
return inv;
}