ref: 4bd088833fc84c5c9df381c842c03f7a59c13561
parent: 7b55de41c328b9ec8222ab3a9f2fd407e4ca2c59
author: 9ferno <gophone2015@gmail.com>
date: Tue Jan 3 21:15:56 EST 2023
compiling extents library
--- a/extents.c
+++ b/extents.c
@@ -2,21 +2,16 @@
#include <libc.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.
- */
-
Extent *sortbysize(Extents *es, Extent *e);
void showextent(int fd, char *pre, Extent *e);
static int extentsfd = -1;
+Extent *
+emalloc(void* (*malloc)(u32 sz))
+{+ return (Extent *) malloc(sizeof(Extent));
+}
+
s64
belongs(Extent *e, u64 start)
{@@ -34,7 +29,7 @@
s64 howclose;
if(es == nil || es->lowest == nil)
- panic("searchlrus: should not happen");+ es->panic("searchlrus: should not happen"); if(es->lru == nil){*closest = belongs(es->lowest, blkno);
@@ -65,7 +60,7 @@
s64 howclose;
if(es == nil || es->lowest == nil)
- panic("searchlrusbysize: should not happen");+ es->panic("searchlrusbysize: should not happen"); // print("searchlrusbysize len %llud e->len %llud\n", len, e->len); if(es->lru == nil){@@ -122,7 +117,7 @@
else if(d != nil)
es->lru = d;
else
- panic("removefromlrus(): should not be happening\n");+ es->panic("removefromlrus(): should not be happening\n");// es->lru = nil;
}
@@ -229,12 +224,12 @@
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 %llud es->lru %8#p\n", es->lowest, e, es->n, es->lru);
+ 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(chatty9p > 7)
+ 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.
@@ -241,8 +236,8 @@
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)
+ 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
@@ -305,7 +300,7 @@
euse = euse->big;
}
euse = eprev;
- if(chatty9p > 7)
+ 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){@@ -322,9 +317,9 @@
fbig = eprev->big;
}
- if(chatty9p > 7)
+ if(es->log && es->loglevel)
print("addbysize after scroll down eprev start %llud len %llud\n", eprev->start, eprev->len);- if(chatty9p > 7){+ 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");@@ -349,12 +344,12 @@
{Extent *c;
- c = emalloc(sizeof(Extent));
+ c = emalloc(es->malloc);
c->start = start;
c->len = len;
addbysize(es, c);
es->n++;
- if(chatty9p > 7)
+ if(es->log && es->loglevel)
print(" +%llud %llud %llud\n", start, start+len-1, len); if(start < e->start){@@ -395,9 +390,9 @@
Extent *small, *big;
if(es == nil || e == nil || f == nil)
- panic("mergeboth: should not be happening\n");;+ es->panic("mergeboth: should not be happening\n");;if(e->start+e->len != start || start+len != f->start)
- panic("mergeboth the caller is wrong\n");+ es->panic("mergeboth the caller is wrong\n");/* skip e in size lru
small e big => small big
@@ -450,9 +445,9 @@
Extent *small, *big;
if(es == nil || e == nil)
- panic("mergeprevious: should not be happening\n");;+ es->panic("mergeprevious: should not be happening\n");;if(e->start+e->len != start)
- panic("mergeprevious the caller is wrong\n");+ es->panic("mergeprevious the caller is wrong\n");/* skip e in size lru
small e big => small big
@@ -491,9 +486,9 @@
Extent *small, *big;
if(es == nil || e == nil)
- panic("mergenext: should not be happening\n");;+ es->panic("mergenext: should not be happening\n");;if(start+len != e->start)
- panic("mergenext the caller is wrong\n");+ es->panic("mergenext the caller is wrong\n");/* skip e in size lru
small e big => small big
@@ -535,9 +530,9 @@
Extent *e, *d, *f;
if(es == nil)
- panic("add es == nil");+ es->panic("add es == nil"); if(es->n == 0){- e = emalloc(sizeof(Extent));
+ e = emalloc(es->malloc);
e->low = e->high = e->small = e->big = nil;
e->start = start;
e->len = len;
@@ -549,8 +544,8 @@
/* using the previously used extents */
d = f = e = searchlrus(es, start, &dir);
if(e == nil)
- panic("doadd: e == nil");- if(chatty9p > 7){+ 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);
@@ -616,12 +611,12 @@
{Extent *e;
- if(chatty9p > 7){+ if(es->log && es->loglevel){showextents(2, " before\n", es);
- fprint(2, " +%llud %llud\n", start, len);
+ es->log(es->logfd, " +%llud %llud\n", start, len);
}
e = intolrus(es, doadd(es, start, len));
- if(chatty9p > 7)
+ if(es->log && es->loglevel)
showextents(2, " after\n", es);
return e;
}
@@ -637,7 +632,7 @@
u64 start;
if(es == nil || e == nil || es->lowest == nil)
- panic("pluck(): should not happen");+ es->panic("pluck(): should not happen");removefromlrus(es, e);
@@ -694,8 +689,8 @@
Extent *d, *f;
if(es == nil || e == nil || es->lowest == nil || len == 0 || e->len <= len){- showextentslists(2, "slice() panic\n", es);
- panic("slice(): should not happen es %8#p e %8#p es->lru %8#p len %llud e->len %llud",+ 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;
@@ -742,7 +737,7 @@
/* allocate n blocks and return that block number */
u64
-balloc(Extents *es, u64 n)
+qalloc(Extents *es, u64 n)
{Extent *e, *euse;
u64 start;
@@ -750,22 +745,24 @@
s64 dir;
if(es == nil)
- panic("balloc: es == nil");+ es->panic("qalloc: es == nil");if(es->n == 0)
- panic("balloc entering es->n == 0\n");+ es->panic("qalloc entering es->n == 0\n");start = 0;
USED(start);
qlock(&es->lck);
if(es->n == 0)
rsleep(&es->isempty);
- if(chatty9p > 7){- snprint(msg, 64, "balloc() %llud blocks:\n", n);
- showextentslists(2, msg, es);
+ if(es->loglevel == Everbose){+ es->log(es->logfd, "qalloc() %llud blocks:\n", n);
+ }else if(es->loglevel == Edebug){+ snprint(msg, 64, "qalloc() %llud blocks:\n", n);
+ showextentslists(es->logfd, msg, es);
}
again:
e = euse = searchlrusbysize(es, n, &dir);
- if(chatty9p > 7)
- fprint(2, "balloc() searchlrusbysize() euse %8#p dir %lld \n", euse, dir);
+ if(es->log && es->loglevel)
+ es->log(es->logfd, "qalloc() searchlrusbysize() euse %8#p dir %lld \n", euse, dir);
if(dir == 0){ while(e != nil && n == e->len){euse = e;
@@ -787,7 +784,7 @@
/* 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);
+ snprint(msg, 64, "qalloc() %llud %s: waiting\n", n, es->name);
showextents(2, msg, es);
if(es->flush){qunlock(&es->lck);
@@ -802,21 +799,25 @@
else /* found something bigger */
start = slice(es, e, n);
-// snprint(msg, 64, "balloc()'ed start %llud len %llud blocks:\n", start, n);
-// showextentswithsize(2, msg, es);
+ if(es->log && es->loglevel == Everbose){+ es->log(es->logfd, "qalloc()'ed start %llud len %llud blocks:\n", start, n);
+ }else if(es->log && es->loglevel == Edebug){+ snprint(msg, 64, "qalloc() %llud blocks:\n", n);
+ showextentslists(es->logfd, msg, es);
+ }
if(es->n == 0)
- panic("balloc exiting es->n == 0\n");+ es->panic("qalloc exiting es->n == 0\n");qunlock(&es->lck);
- /* uncomment the below line and the other in bfree() for
+ /* uncomment the below line and the other in qfree() for
generating test cases of unforeseen behaviour */
- if(extentsfd > 0)
- fprint(extentsfd, "%s-%llud %llud\n", es->name, start, n);
+ if(es->log && es->loglevel)
+ es->log(es->logfd, "%s-%llud %llud\n", es->name, start, n);
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
+ 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.
@@ -823,26 +824,30 @@
free n blocks allocated at block number
*/
void
-bfree(Extents *es, u64 start, u64 len)
+qfree(Extents *es, u64 start, u64 len)
{-// char msg[64];
+ char msg[64];
if(es == nil)
- panic("bfree: es == nil");+ es->panic("qfree: es == nil");if(len <= 0)
- panic("bfree: len <= 0");- /* uncomment the below line and the other in balloc() for
+ es->panic("qfree: len <= 0");+ /* uncomment the below line and the other in qalloc() for
generating test cases of unforeseen behaviour */
- if(extentsfd > 0)
- fprint(extentsfd, "%s+%llud %llud\n", es->name, start, len);
+ if(es->log && es->loglevel)
+ es->log(es->logfd, "%s+%llud %llud\n", es->name, start, len);
qlock(&es->lck);
add(es, start, len);
-// snprint(msg, 64, "bfree()d start %llud len %llud blocks:\n", start, len);
-// showextentswithsize(2, msg, es);
+ 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)
- panic("bfree exiting es->n == 0\n");+ es->panic("qfree exiting es->n == 0\n");qunlock(&es->lck);
}
@@ -854,7 +859,7 @@
Extent *e;
if(es == nil)
- panic("nfrees: es == nil");+ es->panic("nfrees: es == nil");qlock(&es->lck);
for(e = lowest(es); e != nil; e = e->high){n += e->len;
@@ -877,7 +882,7 @@
n = snprint(tmp, 128, "%llud %llud %llud\n",
e->start, e->start+e->len-1, e->len);
if(n == 128)
- panic("sizeofextents(): increase tmp size");+ es->panic("sizeofextents(): increase tmp size");used += n;
}
// keep it locked?
@@ -904,7 +909,7 @@
"%llud %llud %llud\n",
e->start, e->start+e->len-1, e->len);
if(used >= nbuf){- panic("saveextents(): increase buf size");+ es->panic("saveextents(): increase buf size");ret = -1; /* increase buf size */
goto end;
}
@@ -927,32 +932,32 @@
p = buf;
if(es->lru != nil || es->n != 0){- panic("extents already loaded.\n"+ 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)
- panic("could not read");+ es->panic("could not read");p = ep;
p += 1; /* skip over the space */
end = strtoull(p, &ep, 10);
if(p == ep)
- panic("could not read");+ es->panic("could not read");p = ep;
p += 1; /* skip over the space */
nblocks = strtoull(p, &ep, 10);
if(p == ep)
- panic("could not read");+ es->panic("could not read");if(end-start+1 != nblocks)
- panic("loadextents does not match up: start %llud end %llud nblocks %llud",+ 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 */
- bfree(es, start, nblocks);
+ qfree(es, start, nblocks);
}
return es->n;
}
@@ -1059,40 +1064,19 @@
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;
-}
-
void
-initextents(Extents *es, char *name, void (*flush)(void))
+initextents(Extents *es, char *name, u64 quantum, u8 loglevel, u32 logfd, void (*flush)(void), void (*log)(int fd, char *fmt, ...), void (*panic)(char *fmt, ...), void *(*malloc)(u32 sz))
{-/* if(extentsfd < 1)
- extentsfd = open("/mnt/term/tmp/extents.raw", OWRITE);*/-
es->isempty.l = &es->lck;
if(name != nil)
strncpy(es->name, name, 32);
+ es->quantum = quantum;
+ es->loglevel = loglevel;
+ es->logfd = logfd;
es->flush = flush;
+ es->log = log;
+ es->panic = panic;
+ es->malloc = malloc;
}
/*
@@ -1109,7 +1093,7 @@
return nil;
for(e=lowest(es); e!=nil && e->high != nil; e=e->high){start = e->start+e->len;
- bfree(inv, start, e->high->start-start);
+ qfree(inv, start, e->high->start-start);
}
return inv;
}
--- a/extents.h
+++ b/extents.h
@@ -2,10 +2,29 @@
An ordered linked list sorted by block number (->low, ->high).
->big or ->small sorted by size and then block number.
This is similar in functionality to pool(2).
+
+ Extents are used to manage contiguous space (such as memory space and disk space).
+ The space is is split into units of the same size (quantum).
+
+ 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.
+
+ Debugging
+
+ Verbosity induces the dumping of the pool via p->print at each lock operation.
+ By default, only one line is logged for each qalloc and qfree.
*/
+
enum
{Nlru = 32,
+
+ /* flags */
+ Everbose = 1,
+ Edebug = 2,
};
typedef signed char s8;
@@ -42,6 +61,15 @@
char name[32];
u64 quantum; /* allocations are a multiple of quantum */
+ void (*flush)(void); /* flush when nothing is available */
+
+ u8 loglevel; /* Everbose or Edebug */
+ u32 logfd;
+ void (*log)(int fd, char *fmt, ...);
+ void (*panic)(char *fmt, ...);
+ void *(*malloc)(u32 sz);
+
+ /* private stuff */
Extent *lowest; /* find the first block number in a jiffy */
QLock lck;
u64 n; /* number of extents */
@@ -49,18 +77,8 @@
u8 nlru; /* number of items in the lru linked list */
Extent *lru; /* least recently used extent in the circular lru linked list */
-
- void (*flush)(void);
};
-extern int chatty9p;
-void *emalloc(u32 sz);
-s8 *estrdup(s8 *s);
-void panic(char *fmt, ...);
-s8 find(Extents *es, u64 bno);
-Extent *add(Extents *es, u64 blkno, u64 len);
-Extents *holes(Extents *es, Extents *inv);
-
void showblocknos(int fd, Extents *es);
void showextents(int fd, char *msg, Extents *es);
void showextentslists(int fd, char *msg, Extents *es);
@@ -69,9 +87,9 @@
s32 saveextents(Extents *es, s8 *buf, u32 nbuf);
s32 loadextents(Extents *es, s8 *buf, u32 nbuf);
-u64 balloc(Extents *es, u64 len); /* allocate len*quantum */
-void bfree(Extents *es, u64 start, u64 len);/* free len*quantum starting from start */
+u64 qalloc(Extents *es, u64 len); /* allocate len*quantum */
+void qfree(Extents *es, u64 start, u64 len);/* free len*quantum starting from start */
u64 nfrees(Extents *es);
+Extents *holes(Extents *es, Extents *inv);
-Extent *lowest(Extents *es);
-void initextents(Extents *es, char *name, void (*flush)(void));
+void initextents(Extents *es, char *name, u64 quantum, u8 loglevel, u32 logfd, void (*flush)(void), void (*log)(int fd, char *fmt, ...), void (*panic)(char *fmt, ...), void *(*malloc)(u32 sz));
--- a/mkfile
+++ b/mkfile
@@ -1,6 +1,6 @@
</$objtype/mkfile
-P=extent
+P=extents
LIB=lib$P.$O.a
OFILES=$P.$O
--- a/testextents.c
+++ b/testextents.c
@@ -18,6 +18,36 @@
}
void
+panic(char *fmt, ...)
+{+ char buf[8192], *s;
+ va_list arg;
+
+
+ s = buf;
+ s += sprint(s, "%s %d: ", argv0, getpid());
+ va_start(arg, fmt);
+ s = vseprint(s, buf + sizeof(buf) / sizeof(*buf), fmt, arg);
+ va_end(arg);
+ *s++ = '\n';
+ write(2, buf, s - buf);
+ abort();
+ exits(buf);
+}
+
+static void *
+emalloc(u32 sz)
+{+ void *v;
+
+ if((v = mallocz(sz, 1)) == nil)
+ sysfatal("emalloc: %r");+
+ setmalloctag(v, getcallerpc(&sz));
+ return v;
+}
+
+void
main(int argc, char *argv[])
{Extents es;
@@ -37,17 +67,17 @@
bp = Bfdopen(0, OREAD);
Blethal(bp, nil);
- initextents(&es, "testextents", nil);
+ initextents(&es, "testextents", 1, 0, 1, nil, nil, panic, emalloc);
while((line = Brdstr(bp, '\n', 1)) != nil) {act = line[0];
if(act == '-'){len = strtoull(line+1, nil, 10);
- balloc(&es, len);
+ qalloc(&es, len);
}else{bno = strtoull(line, &p, 10);
p++; /* for the space */
len = strtoull(p, nil, 10);
- bfree(&es, bno, len);
+ qfree(&es, bno, len);
}
free(line);
}