ref: 5f15f2246d0fdac0fa98a0a910d40827edfaf68f
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.
*/
void showextent(int fd, char *pre, Extent *e);
s64
belongs(Extent *e, u64 start, u64 len)
{
if(e == nil)
sysfatal("belongs: e == nil");
if(start+len == e->start || start == e->start+e->len)
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;
}
Extent *
searchlrus(Extents *es, u64 blkno, u64 len, s64 *closest)
{
Extent *e, *eclosest;
s64 howclose;
if(es->lru == nil)
panic("searchlrus: should not happen");;
eclosest = e = es->lru;
*closest = belongs(e, blkno, len);
if(closest == 0)
return es->lru;
for(e = e->next; e != es->lru; e = e->next){
howclose = belongs(e, blkno, len);
if(abs(howclose) < abs(*closest)){
eclosest = e;
*closest = howclose;
}
}
return eclosest;
}
void
removefromlrus(Extents *es, Extent *e)
{
Extent *z, *a;
if(e == nil || es == nil)
return;
/* only entry in the lru linked list */
if(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;
z->next = a;
a->prev = z;
es->nlru--;
if(es->lru == e)
es->lru = a;
}
void
intolrus(Extents *es, Extent *e)
{
Extent *y, *z;
if(e == nil || es == nil)
return;
if(e->prev != nil)
removefromlrus(es, e);
if(es->lru == nil){
es->lru = e->prev = e->next = e;
}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;
}
Extent *
lowest(Extents *es)
{
Extent *e;
if(es == nil || es->lru == nil || es->head == nil)
return nil;
for(e = es->head; e!= nil && e->low != nil; e=e->low)
;
return e;
}
Extent *
highest(Extents *es)
{
Extent *e;
if(es == nil || es->lru == nil)
return nil;
for(e = es->lru; e!=nil && e->high != nil; e=e->high)
;
return e;
}
Extent *
addextent(Extents *es, Extent *e, u64 start, u64 len)
{
Extent *c;
c = emalloc(sizeof(Extent));
c->start = start;
c->len = len;
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->head = c;
else
e->low->high = c;
c->low = e->low;
e->low = c;
c->high = e;
intolrus(es, c);
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;
intolrus(es, c);
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;
}
/*
in d e f g
e = e+f
becomes d e g
*/
Extent *
mergenext(Extents *es, Extent *e)
{
Extent *f, *g;
if(e == nil)
return e;
/* at the highest extent */
if(e->high == nil)
return e;
if(e->start + e->len == e->high->start){
f = e->high;
if(f != nil)
g = f->high;
else
g = nil;
/* skipping f */
e->len += f->len;
if(g != nil)
g->low = e;
e->high = g;
removefromlrus(es, f);
free(f);
es->n--;
intolrus(es, e);
return e;
}
return e;
}
/*
in c d e f
d = d+e
becomes c d f
*/
Extent *
mergeprevious(Extents *es, Extent *e)
{
Extent *d, *f;
if(e == nil)
return e;
/* at the lowest extent */
if(e->low == nil)
return e;
if(e->low->start+e->low->len == e->start){
d = e->low;
f = e->high;
/* skipping e */
if(d != nil){
d->len += e->len;
d->high = f;
}
if(f != nil)
f->low = d;
removefromlrus(es, e);
free(e);
es->n--;
intolrus(es, d);
return d;
}
return e;
}
Extent *
increment(Extents *es, Extent *e, u64 start, u64 len)
{
if(e == nil)
return e;
intolrus(es, e);
if(start+len == e->start){
e->start = start;
e->len += len;
return mergeprevious(es, e);
}
if(start == e->start+e->len){
e->len += len;
return 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();
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, *eprev;
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->head = e->prev = e->next = e;
es->n = 1;
return e;
}
/* using the previously used extent */
eprev = e = searchlrus(es, start, len, &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",
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;
e = e->low;
if(e == nil)
break;
}
if(chatty9p > 7){
print(" belongs(e %llud %llud %llud %p %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);
}
/* 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);
/* 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 = e->high;
if(e == nil)
break;
}
if(chatty9p > 7){
print(" belongs(e %llud %llud %llud start %llud %llud %llud) %lld\n",
e->start, e->start+e->len-1, e->len, start, start+len-1, len, dir);
}
/* 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);
/* dir(e) < 0, hence, eprev < start < e */
return addextent(es, eprev, start, len);
}
/* dir == 0 */
return increment(es, e, 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 = doadd(es, start, len);
es->lru = e;
if(chatty9p > 7)
showextents(2, " after\n", es);
return e;
}
static u64
pluck(Extents *es, Extent *e)
{
Extent *dlow, *fhigh;
u64 start;
if(es == nil || e == nil || es->lru == nil)
panic("pluck(): should not happen");
/* if e is the only entry in es */
if(e->low == nil && e->high == nil){
es->head = nil;
es->n = 0;
start = e->start;
removefromlrus(es, e);
free(e);
return start;
}
/* there are atleast 2 elements in the list */
/* d e f => d f */
dlow = e->low;
fhigh = e->high;
removefromlrus(es, e);
/* d e nil => d nil */
if(fhigh == nil){
dlow->high = nil;
intolrus(es, dlow);
es->n--;
}
/* nil e f => nil f */
if(dlow == nil){
fhigh->low = nil;
es->head = fhigh;
intolrus(es, fhigh);
es->n--;
}
if(dlow != nil && fhigh != nil){
dlow->high = fhigh;
fhigh->low = dlow;
intolrus(es, fhigh);
es->n--;
}
start = e->start;
free(e);
return start;
}
u64
slice(Extents *es, Extent *e, u64 len)
{
u64 oldstart, oldlen;
if(es == nil || e == nil || es->lru == nil || len == 0 || e->len <= len)
panic("pluck(): should not happen");
oldlen = e->len;
oldstart = pluck(es, e);
add(es, oldstart+len, oldlen - len);
return oldstart;
}
/* allocate n blocks and return that block number */
u64
balloc(Extents *es, u64 n)
{
Extent *e;
u64 start;
// char msg[64];
if(es == nil)
panic("balloc: es == nil");
start = 0;
qlock(&es->lck);
if(es->n == 0)
rsleep(&es->isempty);
/* if(chatty9p > 7){
snprint(msg, 64, "balloc() %llud blocks:\n", n);
showextents(2, msg, es);
}*/
for(e = lowest(es); e != nil && e->len < n; e = e->high)
;
if(e == nil){
// snprint(msg, 64, "balloc() %llud blocks:\n", n);
// showextents(fd, msg, es);
panic("balloc: out of free blocks");
}
else if(e->len == n)
start = pluck(es, e);
else /* found something bigger */
start = slice(es, e, n);
qunlock(&es->lck);
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)
{
if(es == nil)
panic("bfree: es == nil");
qlock(&es->lck);
add(es, start, len);
if(es->n == 1)
rwakeup(&es->isempty);
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;
qlock(&es->lck);
used = 0;
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("saveextents(): increase tmp size");
used += n;
}
// keep it locked?
qunlock(&es->lck);
return used;
}
/* write to *buf return the length written */
s32
saveextents(Extents *es, s8 *buf, u32 nbuf)
{
u64 n, used;
s8 tmp[128];
Extent *e;
s32 ret;
qlock(&es->lck);
used = 0;
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("saveextents(): increase tmp size");
if(used+n > nbuf){
ret = -1; /* increase buf size */
goto end;
}
snprint(buf+used, nbuf-used, "%s", tmp);
used += n;
}
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\n");
}
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 low %8#p e %8#p %llud %llud high %8#p",
pre, e->low, e, e->start, e->len, e->high);
}
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;
}
s8
find(Extents *es, u64 bno)
{
Extent *e;
if(es == nil || es->lru == nil)
return 0;
for(e = lowest(es); e != nil; e=e->high){
if(e->start == bno)
return 1;
if(e->start < bno && bno < e->start+e->len)
return 1;
}
return 0;
}
void
initextents(Extents *es)
{
es->isempty.l = &es->lck;
}
/* obsolete */
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->head = 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;
}