ref: e82f565015fd0b75085d8d2a4f1aaca53e875f64
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);
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\n", start, start+len-1);
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;
es->lru = 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;
es->lru = 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;
free(f);
es->n--;
es->lru = 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;
free(e);
es->n--;
es->lru = d;
return d;
}
return e;
}
Extent *
increment(Extents *es, Extent *e, u64 start, u64 len)
{
if(e == nil)
return e;
es->lru = 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;
}
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;
}
/*
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;
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){
while(e->low != nil && (dir = belongs(e, start, len)) < 0){
es->lru = e;
e = e->low;
}
/* e->low e es->lru */
if(dir == 0)
return increment(es, e, start, len);
if(e->low == nil)
/* at the lowest extent, add below or above */
return addextent(es, e, start, len);
/* dir(e) > 0, hence, e < start < es->lru */
return addextent(es, es->lru, start, len);
}else if(dir > 0){
while(e->high != nil && (dir = belongs(e, start, len)) > 0){
es->lru = e;
e = e->high;
}
/* es->lru e e->high */
if(dir == 0)
return increment(es, e, start, len);
if(e->high == nil)
/* at the highest extent, add below or above */
return addextent(es, e, start, len);
/* dir(e) < 0, hence, es->lru < start < e */
return addextent(es, es->lru, 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->lru = es->head = nil;
es->n = 0;
start = e->start;
free(e);
return start;
}
/* there are atleast 2 elements in the list */
/* d e f => d f */
dlow = e->low;
fhigh = e->high;
/* d e nil => d nil */
if(fhigh == nil){
dlow->high = nil;
es->lru = dlow;
es->n--;
}
/* nil e f => nil f */
if(dlow == nil){
fhigh->low = nil;
es->lru = es->head = fhigh;
es->n--;
}
if(dlow != nil && fhigh != nil){
dlow->high = fhigh;
fhigh->low = dlow;
es->lru = 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\n",
e->start, e->start+e->len-1);
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\n",
e->start, e->start+e->len-1);
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 sstart, estart, 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){
sstart = strtoull(p, &ep, 10);
if(p == ep)
panic("could not read");
p = ep;
p += 4; /* skip over ' .. ' */
estart = strtoull(p, &ep, 10);
if(p == ep)
panic("could not read");
nblocks = estart - sstart+1;
p = ep;
p++; /* to skip over the new line */
bfree(es, sstart, 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", e->start, e->start+e->len-1);
// 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;
}