1 #include "lib9.h" 2 #include "logfs.h" 3 #include "local.h" 4 #include "fcall.h" 5 6 typedef struct PathEnt { 7 ulong path; 8 long block; 9 } PathEnt; 10 11 typedef struct GenInfo { 12 long start; 13 long end; 14 int gaps; 15 } GenInfo; 16 17 static int 18 dataorder(ulong p1, ulong p2) 19 { 20 int o; 21 o = dataseqof(p1) - dataseqof(p2); 22 if(o != 0) 23 return o; 24 return copygenof(p1) - copygenof(p2); 25 } 26 27 static int 28 logorder(ulong p1, ulong p2) 29 { 30 int o; 31 o = loggenof(p1) - loggenof(p2); 32 if(o != 0) 33 return o; 34 o = logseqof(p1) - logseqof(p2); 35 if(o != 0) 36 return o; 37 return copygenof(p1) - copygenof(p2); 38 } 39 40 static void 41 insert(PathEnt *pathmap, long entries, ulong path, long block, int (*order)(ulong p1, ulong p2)) 42 { 43 long i; 44 for(i = 0; i < entries; i++) 45 if((*order)(path, pathmap[i].path) < 0) 46 break; 47 memmove(&pathmap[i + 1], &pathmap[i], (entries - i) * sizeof(PathEnt)); 48 pathmap[i].path = path; 49 pathmap[i].block = block; 50 } 51 52 static void 53 populate(LogSegment *seg, int gen, long unsweptblockindex, long curblockindex, PathEnt *pathent) 54 { 55 long i; 56 seg->gen = gen; 57 seg->unsweptblockindex = unsweptblockindex; 58 seg->curblockindex = curblockindex; 59 for(i = unsweptblockindex; i <= curblockindex; i++) { 60 // print("populate %d: %d\n", i, pathent[i - unsweptblockindex].block); 61 seg->blockmap[i] = pathent->block; 62 pathent++; 63 } 64 } 65 66 static int 67 dataduplicate(PathEnt *p1, PathEnt *p2) 68 { 69 return dataseqof(p2->path) == dataseqof(p1->path) 70 && copygenof(p2->path) == copygensucc(copygenof(p1->path)); 71 } 72 73 static char * 74 eliminateduplicates(LogfsServer *server, char *name, PathEnt *map, long *entriesp) 75 { 76 long i; 77 long k = *entriesp; 78 for(i = 0; i < k;) { 79 PathEnt *prev = &map[i - 1]; 80 PathEnt *this = &map[i]; 81 if(i > 0 && dataduplicate(prev, this)) { 82 print("%s duplicate detected\n", name); 83 if(i + 1 < k && dataduplicate(this, &map[i + 1])) 84 return "three or more copies of same block"; 85 /* 86 * check that the copy generations are in order 87 */ 88 if(copygensucc(copygenof(this->path)) == copygenof(prev->path)) { 89 PathEnt m; 90 /* 91 * previous entry is newer, so swap 92 */ 93 m = *this; 94 *this = *prev; 95 *prev = m; 96 } 97 else if(copygensucc(copygenof(prev->path)) != copygenof(this->path)) 98 return "duplicate blocks but copy generations not sequential"; 99 /* erase and format previous block */ 100 logfsbootfettleblock(server->lb, prev->block, LogfsTnone, ~0, nil); 101 /* 102 * remove entry from table 103 */ 104 memmove(prev, this, sizeof(PathEnt) * (k - i)); 105 k--; 106 continue; 107 } 108 i++; 109 } 110 *entriesp = k; 111 return nil; 112 } 113 114 char * 115 logfsscan(LogfsServer *server) 116 { 117 LogfsLowLevel *ll = server->ll; 118 long b; 119 long i; 120 long logfound = 0; 121 long datafound = 0; 122 PathEnt *logpathmap, *datapathmap; 123 GenInfo geninfo[1 << L2LogSweeps]; 124 int gensfound, lastgenfound; 125 int g0, g1; 126 char *errmsg; 127 //print("logfsscan %ld blocks\n", server->ll->blocks); 128 logpathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks); 129 datapathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks); 130 if(logpathmap == nil || datapathmap == nil) 131 return Enomem; 132 for(b = 0; b < ll->blocks; b++) { 133 short tag = (*ll->getblocktag)(ll, b); 134 ulong path = (*ll->getblockpath)(ll, b); 135 //print("scan: %ld: %d %ld\n", b, tag, path); 136 switch(tag) { 137 case LogfsTlog: 138 insert(logpathmap, logfound++, path, b, logorder); 139 break; 140 case LogfsTdata: 141 insert(datapathmap, datafound++, path, b, dataorder); 142 break; 143 } 144 } 145 if(server->trace > 1) { 146 for(i = 0; i < logfound; i++) 147 print("log gen %lud seq %lud copygen %lud block %ld\n", 148 loggenof(logpathmap[i].path), logseqof(logpathmap[i].path), copygenof(datapathmap[i].path), logpathmap[i].block); 149 for(i = 0; i < datafound; i++) 150 print("data seq %lud copygen %lud block %ld\n", 151 dataseqof(datapathmap[i].path), copygenof(datapathmap[i].path), datapathmap[i].block); 152 } 153 /* 154 * sort out data first 155 */ 156 errmsg = eliminateduplicates(server, "data", datapathmap, &datafound); 157 if(errmsg) 158 goto fail; 159 /* 160 * data blocks guaranteed to be ordered 161 */ 162 if(datafound) 163 server->ndatablocks = dataseqof(datapathmap[datafound - 1].path) + 1; 164 else 165 server->ndatablocks = 0; 166 for(i = 0; i < server->ndatablocks; i++) 167 server->datablock[i].block = -1; 168 for(i = 0; i < datafound; i++) { 169 long j; 170 j = dataseqof(datapathmap[i].path); 171 server->datablock[j].path = datapathmap[i].path; 172 server->datablock[j].block = datapathmap[i].block; 173 /* 174 * mark pages as free and dirty, which indicates they cannot be used 175 */ 176 server->datablock[j].dirty = server->datablock[j].free = logfsdatapagemask(1 << ll->l2pagesperblock, 0); 177 } 178 /* 179 * find how many generations are present, and whether there are any gaps 180 */ 181 errmsg = eliminateduplicates(server, "log", logpathmap, &logfound); 182 if(errmsg) 183 goto fail; 184 gensfound = 0; 185 lastgenfound = -1; 186 for(i = 0; i < nelem(geninfo); i++) 187 geninfo[i].start = -1; 188 for(i = 0; i < logfound; i++) { 189 int gen; 190 gen = loggenof(logpathmap[i].path); 191 if(geninfo[gen].start < 0) { 192 if(lastgenfound >= 0) 193 geninfo[lastgenfound].end = i; 194 geninfo[gen].start = i; 195 lastgenfound = gen; 196 geninfo[gen].gaps = 0; 197 gensfound++; 198 } 199 else if(!geninfo[lastgenfound].gaps && logseqof(logpathmap[i - 1].path) + 1 != logseqof(logpathmap[i].path)) { 200 geninfo[lastgenfound].gaps = 1; 201 print("generation %d has gaps (%lud, %lud)\n", lastgenfound, 202 logseqof(logpathmap[i - 1].path), logseqof(logpathmap[i].path)); 203 } 204 } 205 if(lastgenfound >= 0) 206 geninfo[lastgenfound].end = i; 207 if(server->trace > 1) { 208 for(i = 0; i < nelem(geninfo); i++) 209 print("geninfo: %ld: start %ld end %ld gaps %d\n", i, geninfo[i].start, geninfo[i].end, geninfo[i].gaps); 210 } 211 switch(gensfound) { 212 case 0: 213 /* active log - empty */ 214 break; 215 case 1: 216 /* 217 * one log, active 218 */ 219 for(g0 = 0; g0 < nelem(geninfo); g0++) 220 if(geninfo[g0].start >= 0) 221 break; 222 if(geninfo[g0].gaps || geninfo[g0].start != 0) { 223 errmsg = "missing log blocks"; 224 goto fail; 225 } 226 populate(server->activelog, g0, 0, geninfo[g0].end - geninfo[g0].start - 1, logpathmap + geninfo[g0].start); 227 break; 228 case 2: 229 /* 230 * two logs, active, swept 231 */ 232 g0 = -1; 233 for(g1 = 0; g1 < nelem(geninfo); g1++) 234 if(geninfo[g1].start >= 0) { 235 if(g0 < 0) 236 g0 = g1; 237 else 238 break; 239 } 240 if(geninfo[g0].gaps || geninfo[g1].gaps) { 241 errmsg = "missing log blocks"; 242 goto fail; 243 } 244 if(g0 == loggensucc(g1)) { 245 int tmp = g0; 246 g0 = g1; 247 g1 = tmp; 248 } 249 else if(g1 != loggensucc(g0)) { 250 errmsg = "nonsequential generations in log"; 251 goto fail; 252 } 253 if(logseqof(logpathmap[geninfo[g1].start].path) != 0) { 254 errmsg = "swept log does not start at 0"; 255 goto fail; 256 } 257 if(logseqof(logpathmap[geninfo[g0].start].path) == logseqof(logpathmap[geninfo[g1].end - 1].path)) { 258 /* 259 * duplicate block 260 * as the log never gets bigger, information from active[n] is either entirely in swept[n], 261 * or split between swept[n-1] and swept[n]. we can safely remove swept[n]. this might 262 * leave some duplication between swept[n - 1] and active[n], but this is always true 263 * for a partially swept log 264 */ 265 logfsbootfettleblock(server->lb, logpathmap[geninfo[g1].end - 1].block, LogfsTnone, ~0, nil); 266 geninfo[g1].end--; 267 } 268 if(logseqof(logpathmap[geninfo[g0].start].path) < logseqof(logpathmap[geninfo[g1].end - 1].path)) { 269 errmsg = "active log overlaps end of swept log"; 270 goto fail; 271 } 272 populate(server->activelog, g0, logseqof(logpathmap[geninfo[g0].start].path), 273 logseqof(logpathmap[geninfo[g0].end - 1].path), logpathmap + geninfo[g0].start); 274 if(server->sweptlog == nil) { 275 errmsg = logfslogsegmentnew(server, g1, &server->sweptlog); 276 if(errmsg) 277 goto fail; 278 } 279 populate(server->sweptlog, g1, logseqof(logpathmap[geninfo[g1].start].path), 280 logseqof(logpathmap[geninfo[g1].end - 1].path), logpathmap + geninfo[g1].start); 281 break; 282 default: 283 errmsg = "more than two generations in log"; 284 goto fail; 285 } 286 goto ok; 287 fail: 288 logfslogsegmentfree(&server->sweptlog); 289 ok: 290 logfsfreemem(logpathmap); 291 logfsfreemem(datapathmap); 292 return errmsg; 293 } 294