123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279 |
- #include "logfsos.h"
- #include "logfs.h"
- #include "local.h"
- typedef struct ExtentNode ExtentNode;
- struct ExtentNode {
- Extent e;
- ExtentNode *next;
- };
- struct ExtentList {
- ExtentNode *head;
- };
- char *
- logfsextentlistnew(ExtentList **ep)
- {
- ExtentList *l;
- l = logfsrealloc(nil, sizeof(*l));
- if(l == nil)
- return Enomem;
- *ep = l;
- return nil;
- }
- void
- logfsextentlistreset(ExtentList *l)
- {
- ExtentNode *n;
- n = l->head;
- while(n) {
- ExtentNode *next;
- next = n->next;
- logfsfreemem(n);
- n = next;
- }
- l->head = nil;
- }
- void
- logfsextentlistfree(ExtentList **lp)
- {
- ExtentList *l;
- if(lp == nil || (l = *lp) == nil)
- return;
- logfsextentlistreset(l);
- logfsfreemem(l);
- *lp = nil;
- }
- char *
- logfsextentlistinsert(ExtentList *l, Extent *add, Extent **new)
- {
- ExtentNode *old, *prev;
- ExtentNode *saved = nil;
- if(l == nil)
- return "nil extentlist";
- /* initially a's extents are non-empty, disjoint and sorted */
- old = l->head;
- prev = nil;
- while(old) {
- ExtentNode *next = old->next;
- if(add->max <= old->e.min)
- break;
- if(old->e.min < add->max && add->min < old->e.max) { /* they intersect */
- if(add->min <= old->e.min) {
- /* add overlaps front of old */
- if(add->max < old->e.max) {
- int trimmed;
- /* but doesn't overlap end */
- /* retain tail of old */
- if(saved == nil){
- saved = logfsrealloc(nil, sizeof(*saved));
- if(saved == nil)
- return Enomem;
- }
- trimmed = add->max - old->e.min;
- old->e.min += trimmed;
- old->e.flashaddr += trimmed;
- /* can't touch any further extents, so... */
- break;
- }
- /* add.min ≤ old.min < old.max ≤ add.max ⇒ add completely covers old */
- /* delete old */
- if(prev)
- prev->next = next;
- else
- l->head = next;
- /* stash the deleted extent, so we can reuse it */
- if(saved == nil)
- saved = old;
- else
- logfsfreemem(old);
- old = next;
- continue;
- }
- else {
- /* add.min > old.min, so overlaps end of old or splits it */
- if(add->max < old->e.max) { /* add inside old, splitting it */
- ExtentNode *frag;
- /*
- * will need at most two add extents, so ensure
- * enough store exists before changing data structures
- */
- if(saved == nil)
- saved = logfsrealloc(nil, sizeof(*saved));
- frag = logfsrealloc(nil, sizeof(*frag));
- if(saved == nil || frag == nil)
- return Enomem;
- frag->next = next;
- old->next = frag;
- frag->e.min = add->max;
- frag->e.max = old->e.max;
- frag->e.flashaddr = old->e.flashaddr + (add->max - old->e.min);
- old->e.max = add->min;
- prev = old;
- break;
- }
- else {
- /*
- * will need at most one add extent, so create one
- * now before changing data structures
- */
- if(saved == nil){
- saved = logfsrealloc(nil, sizeof(*saved));
- if(saved == nil)
- return Enomem;
- }
- old->e.max = add->min; /* retain start of old */
- }
- /* old.max <= add.max ⇒ add covers tail of old */
- }
- }
- prev = old;
- old = next;
- }
- /*
- * if here, and saved == nil, then there was no overlap
- */
- if(saved == nil){
- saved = logfsrealloc(nil, sizeof(*saved));
- if(saved == nil)
- return Enomem;
- }
- saved->e = *add;
- if(prev) {
- saved->next = prev->next;
- prev->next = saved;
- }
- else {
- saved->next = l->head;
- l->head = saved;
- }
- if(new)
- *new = &saved->e;
- return nil;
- }
- Extent *
- logfsextentlistmatch(ExtentList *l, Extent *e)
- {
- ExtentNode *m;
- u32int flashmax;
- if(l == nil)
- return nil;
- flashmax = e->flashaddr + (e->max - e->min);
- for(m = l->head; m; m = m->next) {
- u32int l = m->e.max - m->e.min;
- if(e->min < m->e.max && m->e.min < e->max /* they intersect */
- && m->e.flashaddr < flashmax && e->flashaddr < m->e.flashaddr + l) /* the store intersects */
- return &(m->e);
- }
- return nil;
- }
- int
- logfsextentlistmatchall(ExtentList *l, int (*func)(void *magic, Extent *), void *magic, Extent *e)
- {
- ExtentNode *m;
- u32int flashmax;
- if(l == nil)
- return 1;
- flashmax = e->flashaddr + (e->max - e->min);
- for(m = l->head; m; m = m->next) {
- u32int l;
- if(m->e.min >= e->max)
- return 1;
- l = m->e.max - m->e.min;
- if(e->min < m->e.max /* they intersect */
- && m->e.flashaddr < flashmax && e->flashaddr < m->e.flashaddr + l) {
- /* the store intersects */
- int rv = (*func)(magic, &(m->e));
- if(rv <= 0)
- return rv;
- }
- }
- return 1;
- }
- int
- logfsextentlistwalk(ExtentList *l, int (*func)(void *magic, Extent *, int hole), void *magic)
- {
- ExtentNode *n;
- u32int last = 0;
- if(l == nil)
- return 1;
- for(n = l->head; n; n = n->next) {
- int rv;
- if(last < n->e.min) {
- Extent hole;
- hole.min = last;
- hole.max = n->e.min;
- hole.flashaddr = ~0;
- rv = (*func)(magic, &hole, 1);
- if(rv <= 0)
- return rv;
- }
- rv = (*func)(magic, &n->e, 0);
- if(rv <= 0)
- return rv;
- last = n->e.max;
- }
- return 1;
- }
- int
- logfsextentlistwalkrange(ExtentList *l, int (*func)(void *magic, u32int baseoffset, u32int limitoffset, Extent *, u32int extentoffset), void *magic, u32int base, u32int limit)
- {
- ExtentNode *n;
- u32int last = 0;
- if(l == nil)
- return 1;
- for(n = l->head; n; n = n->next) {
- Extent hole;
- Extent *e;
- if(last < n->e.min) {
- hole.min = last;
- hole.max = n->e.min;
- e = &hole;
- }
- else {
- again:
- e = &n->e;
- }
- if(e->min >= limit)
- return 1;
- //print("walkrange %ud .. %ud\n", e->min, e->max);
- if(e->max > base) {
- ulong rangebase, rangelimit, extentoffset;
- int rv;
- rangebase = e->min;
- if(rangebase < base) {
- extentoffset = base - rangebase;
- rangebase += extentoffset;
- }
- else
- extentoffset = 0;
- rangelimit = e->max;
- if(rangelimit > limit)
- rangelimit = limit;
- rv = (*func)(magic, rangebase - base, rangelimit - base, e == &hole ? nil : e, extentoffset);
- if(rv <= 0)
- return rv;
- }
- last = e->max;
- if(e == &hole)
- goto again;
- }
- return 1;
- }
|