1 #include "logfsos.h" 2 #include "logfs.h" 3 #include "local.h" 4 5 typedef struct ExtentNode ExtentNode; 6 7 struct ExtentNode { 8 Extent e; 9 ExtentNode *next; 10 }; 11 12 struct ExtentList { 13 ExtentNode *head; 14 }; 15 16 char * 17 logfsextentlistnew(ExtentList **ep) 18 { 19 ExtentList *l; 20 l = logfsrealloc(nil, sizeof(*l)); 21 if(l == nil) 22 return Enomem; 23 *ep = l; 24 return nil; 25 } 26 27 void 28 logfsextentlistreset(ExtentList *l) 29 { 30 ExtentNode *n; 31 n = l->head; 32 while(n) { 33 ExtentNode *next; 34 next = n->next; 35 logfsfreemem(n); 36 n = next; 37 } 38 l->head = nil; 39 } 40 41 void 42 logfsextentlistfree(ExtentList **lp) 43 { 44 ExtentList *l; 45 if(lp == nil || (l = *lp) == nil) 46 return; 47 logfsextentlistreset(l); 48 logfsfreemem(l); 49 *lp = nil; 50 } 51 52 char * 53 logfsextentlistinsert(ExtentList *l, Extent *add, Extent **new) 54 { 55 ExtentNode *old, *prev; 56 ExtentNode *saved = nil; 57 58 if(l == nil) 59 return "nil extentlist"; 60 61 /* initially a's extents are non-empty, disjoint and sorted */ 62 old = l->head; 63 prev = nil; 64 while(old) { 65 ExtentNode *next = old->next; 66 if(add->max <= old->e.min) 67 break; 68 if(old->e.min < add->max && add->min < old->e.max) { /* they intersect */ 69 if(add->min <= old->e.min) { 70 /* add overlaps front of old */ 71 if(add->max < old->e.max) { 72 int trimmed; 73 /* but doesn't overlap end */ 74 /* retain tail of old */ 75 if(saved == nil){ 76 saved = logfsrealloc(nil, sizeof(*saved)); 77 if(saved == nil) 78 return Enomem; 79 } 80 trimmed = add->max - old->e.min; 81 old->e.min += trimmed; 82 old->e.flashaddr += trimmed; 83 /* can't touch any further extents, so... */ 84 break; 85 } 86 /* add.min ≤ old.min < old.max ≤ add.max ⇒ add completely covers old */ 87 /* delete old */ 88 if(prev) 89 prev->next = next; 90 else 91 l->head = next; 92 /* stash the deleted extent, so we can reuse it */ 93 if(saved == nil) 94 saved = old; 95 else 96 logfsfreemem(old); 97 old = next; 98 continue; 99 } 100 else { 101 /* add.min > old.min, so overlaps end of old or splits it */ 102 if(add->max < old->e.max) { /* add inside old, splitting it */ 103 ExtentNode *frag; 104 /* 105 * will need at most two add extents, so ensure 106 * enough store exists before changing data structures 107 */ 108 if(saved == nil) 109 saved = logfsrealloc(nil, sizeof(*saved)); 110 frag = logfsrealloc(nil, sizeof(*frag)); 111 if(saved == nil || frag == nil) 112 return Enomem; 113 frag->next = next; 114 old->next = frag; 115 frag->e.min = add->max; 116 frag->e.max = old->e.max; 117 frag->e.flashaddr = old->e.flashaddr + (add->max - old->e.min); 118 old->e.max = add->min; 119 prev = old; 120 break; 121 } 122 else { 123 /* 124 * will need at most one add extent, so create one 125 * now before changing data structures 126 */ 127 if(saved == nil){ 128 saved = logfsrealloc(nil, sizeof(*saved)); 129 if(saved == nil) 130 return Enomem; 131 } 132 old->e.max = add->min; /* retain start of old */ 133 } 134 /* old.max <= add.max ⇒ add covers tail of old */ 135 } 136 } 137 prev = old; 138 old = next; 139 } 140 /* 141 * if here, and saved == nil, then there was no overlap 142 */ 143 if(saved == nil){ 144 saved = logfsrealloc(nil, sizeof(*saved)); 145 if(saved == nil) 146 return Enomem; 147 } 148 saved->e = *add; 149 if(prev) { 150 saved->next = prev->next; 151 prev->next = saved; 152 } 153 else { 154 saved->next = l->head; 155 l->head = saved; 156 } 157 if(new) 158 *new = &saved->e; 159 return nil; 160 } 161 162 Extent * 163 logfsextentlistmatch(ExtentList *l, Extent *e) 164 { 165 ExtentNode *m; 166 u32int flashmax; 167 168 if(l == nil) 169 return nil; 170 171 flashmax = e->flashaddr + (e->max - e->min); 172 173 for(m = l->head; m; m = m->next) { 174 u32int l = m->e.max - m->e.min; 175 if(e->min < m->e.max && m->e.min < e->max /* they intersect */ 176 && m->e.flashaddr < flashmax && e->flashaddr < m->e.flashaddr + l) /* the store intersects */ 177 return &(m->e); 178 } 179 return nil; 180 } 181 182 int 183 logfsextentlistmatchall(ExtentList *l, int (*func)(void *magic, Extent *), void *magic, Extent *e) 184 { 185 ExtentNode *m; 186 u32int flashmax; 187 188 if(l == nil) 189 return 1; 190 191 flashmax = e->flashaddr + (e->max - e->min); 192 193 for(m = l->head; m; m = m->next) { 194 u32int l; 195 if(m->e.min >= e->max) 196 return 1; 197 l = m->e.max - m->e.min; 198 if(e->min < m->e.max /* they intersect */ 199 && m->e.flashaddr < flashmax && e->flashaddr < m->e.flashaddr + l) { 200 /* the store intersects */ 201 int rv = (*func)(magic, &(m->e)); 202 if(rv <= 0) 203 return rv; 204 } 205 } 206 return 1; 207 } 208 209 int 210 logfsextentlistwalk(ExtentList *l, int (*func)(void *magic, Extent *, int hole), void *magic) 211 { 212 ExtentNode *n; 213 u32int last = 0; 214 if(l == nil) 215 return 1; 216 for(n = l->head; n; n = n->next) { 217 int rv; 218 if(last < n->e.min) { 219 Extent hole; 220 hole.min = last; 221 hole.max = n->e.min; 222 hole.flashaddr = ~0; 223 rv = (*func)(magic, &hole, 1); 224 if(rv <= 0) 225 return rv; 226 } 227 rv = (*func)(magic, &n->e, 0); 228 if(rv <= 0) 229 return rv; 230 last = n->e.max; 231 } 232 return 1; 233 } 234 235 int 236 logfsextentlistwalkrange(ExtentList *l, int (*func)(void *magic, u32int baseoffset, u32int limitoffset, Extent *, u32int extentoffset), void *magic, u32int base, u32int limit) 237 { 238 ExtentNode *n; 239 u32int last = 0; 240 if(l == nil) 241 return 1; 242 for(n = l->head; n; n = n->next) { 243 Extent hole; 244 Extent *e; 245 if(last < n->e.min) { 246 hole.min = last; 247 hole.max = n->e.min; 248 e = &hole; 249 } 250 else { 251 again: 252 e = &n->e; 253 } 254 if(e->min >= limit) 255 return 1; 256 //print("walkrange %ud .. %ud\n", e->min, e->max); 257 if(e->max > base) { 258 ulong rangebase, rangelimit, extentoffset; 259 int rv; 260 rangebase = e->min; 261 if(rangebase < base) { 262 extentoffset = base - rangebase; 263 rangebase += extentoffset; 264 } 265 else 266 extentoffset = 0; 267 rangelimit = e->max; 268 if(rangelimit > limit) 269 rangelimit = limit; 270 rv = (*func)(magic, rangebase - base, rangelimit - base, e == &hole ? nil : e, extentoffset); 271 if(rv <= 0) 272 return rv; 273 } 274 last = e->max; 275 if(e == &hole) 276 goto again; 277 } 278 return 1; 279 } 280