ref: d1540c7f666e3c5d636b48c956b444205b50502d
dir: /liblogfs/scan.c/
#include "logfsos.h" #include "logfs.h" #include "local.h" #include "fcall.h" typedef struct PathEnt { ulong path; long block; } PathEnt; typedef struct GenInfo { long start; long end; int gaps; } GenInfo; static int dataorder(ulong p1, ulong p2) { int o; o = dataseqof(p1) - dataseqof(p2); if(o != 0) return o; return copygenof(p1) - copygenof(p2); } static int logorder(ulong p1, ulong p2) { int o; o = loggenof(p1) - loggenof(p2); if(o != 0) return o; o = logseqof(p1) - logseqof(p2); if(o != 0) return o; return copygenof(p1) - copygenof(p2); } static void insert(PathEnt *pathmap, long entries, ulong path, long block, int (*order)(ulong p1, ulong p2)) { long i; for(i = 0; i < entries; i++) if((*order)(path, pathmap[i].path) < 0) break; memmove(&pathmap[i + 1], &pathmap[i], (entries - i) * sizeof(PathEnt)); pathmap[i].path = path; pathmap[i].block = block; } static void populate(LogSegment *seg, int gen, long unsweptblockindex, long curblockindex, PathEnt *pathent) { long i; seg->gen = gen; seg->unsweptblockindex = unsweptblockindex; seg->curblockindex = curblockindex; for(i = unsweptblockindex; i <= curblockindex; i++) { // print("populate %d: %d\n", i, pathent[i - unsweptblockindex].block); seg->blockmap[i] = pathent->block; pathent++; } } static int dataduplicate(PathEnt *p1, PathEnt *p2) { return dataseqof(p2->path) == dataseqof(p1->path) && copygenof(p2->path) == copygensucc(copygenof(p1->path)); } static char * eliminateduplicates(LogfsServer *server, char *name, PathEnt *map, long *entriesp) { long i; long k = *entriesp; for(i = 0; i < k;) { PathEnt *prev = &map[i - 1]; PathEnt *this = &map[i]; if(i > 0 && dataduplicate(prev, this)) { print("%s duplicate detected\n", name); if(i + 1 < k && dataduplicate(this, &map[i + 1])) return "three or more copies of same block"; /* * check that the copy generations are in order */ if(copygensucc(copygenof(this->path)) == copygenof(prev->path)) { PathEnt m; /* * previous entry is newer, so swap */ m = *this; *this = *prev; *prev = m; } else if(copygensucc(copygenof(prev->path)) != copygenof(this->path)) return "duplicate blocks but copy generations not sequential"; /* erase and format previous block */ logfsbootfettleblock(server->lb, prev->block, LogfsTnone, ~0, nil); /* * remove entry from table */ memmove(prev, this, sizeof(PathEnt) * (k - i)); k--; continue; } i++; } *entriesp = k; return nil; } char * logfsscan(LogfsServer *server) { LogfsLowLevel *ll = server->ll; long b; long i; long logfound = 0; long datafound = 0; PathEnt *logpathmap, *datapathmap; GenInfo geninfo[1 << L2LogSweeps]; int gensfound, lastgenfound; int g0, g1; char *errmsg; //print("logfsscan %ld blocks\n", server->ll->blocks); logpathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks); datapathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks); if(logpathmap == nil || datapathmap == nil) return Enomem; for(b = 0; b < ll->blocks; b++) { short tag = (*ll->getblocktag)(ll, b); ulong path = (*ll->getblockpath)(ll, b); //print("scan: %ld: %d %ld\n", b, tag, path); switch(tag) { case LogfsTlog: insert(logpathmap, logfound++, path, b, logorder); break; case LogfsTdata: insert(datapathmap, datafound++, path, b, dataorder); break; } } if(server->trace > 1) { for(i = 0; i < logfound; i++) print("log gen %lud seq %lud copygen %lud block %ld\n", loggenof(logpathmap[i].path), logseqof(logpathmap[i].path), copygenof(datapathmap[i].path), logpathmap[i].block); for(i = 0; i < datafound; i++) print("data seq %lud copygen %lud block %ld\n", dataseqof(datapathmap[i].path), copygenof(datapathmap[i].path), datapathmap[i].block); } /* * sort out data first */ errmsg = eliminateduplicates(server, "data", datapathmap, &datafound); if(errmsg) goto fail; /* * data blocks guaranteed to be ordered */ if(datafound) server->ndatablocks = dataseqof(datapathmap[datafound - 1].path) + 1; else server->ndatablocks = 0; for(i = 0; i < server->ndatablocks; i++) server->datablock[i].block = -1; for(i = 0; i < datafound; i++) { long j; j = dataseqof(datapathmap[i].path); server->datablock[j].path = datapathmap[i].path; server->datablock[j].block = datapathmap[i].block; /* * mark pages as free and dirty, which indicates they cannot be used */ server->datablock[j].dirty = server->datablock[j].free = logfsdatapagemask(1 << ll->l2pagesperblock, 0); } /* * find how many generations are present, and whether there are any gaps */ errmsg = eliminateduplicates(server, "log", logpathmap, &logfound); if(errmsg) goto fail; gensfound = 0; lastgenfound = -1; for(i = 0; i < nelem(geninfo); i++) geninfo[i].start = -1; for(i = 0; i < logfound; i++) { int gen; gen = loggenof(logpathmap[i].path); if(geninfo[gen].start < 0) { if(lastgenfound >= 0) geninfo[lastgenfound].end = i; geninfo[gen].start = i; lastgenfound = gen; geninfo[gen].gaps = 0; gensfound++; } else if(!geninfo[lastgenfound].gaps && logseqof(logpathmap[i - 1].path) + 1 != logseqof(logpathmap[i].path)) { geninfo[lastgenfound].gaps = 1; print("generation %d has gaps (%lud, %lud)\n", lastgenfound, logseqof(logpathmap[i - 1].path), logseqof(logpathmap[i].path)); } } if(lastgenfound >= 0) geninfo[lastgenfound].end = i; if(server->trace > 1) { for(i = 0; i < nelem(geninfo); i++) print("geninfo: %ld: start %ld end %ld gaps %d\n", i, geninfo[i].start, geninfo[i].end, geninfo[i].gaps); } switch(gensfound) { case 0: /* active log - empty */ break; case 1: /* * one log, active */ for(g0 = 0; g0 < nelem(geninfo); g0++) if(geninfo[g0].start >= 0) break; if(geninfo[g0].gaps || geninfo[g0].start != 0) { errmsg = "missing log blocks"; goto fail; } populate(server->activelog, g0, 0, geninfo[g0].end - geninfo[g0].start - 1, logpathmap + geninfo[g0].start); break; case 2: /* * two logs, active, swept */ g0 = -1; for(g1 = 0; g1 < nelem(geninfo); g1++) if(geninfo[g1].start >= 0) { if(g0 < 0) g0 = g1; else break; } if(geninfo[g0].gaps || geninfo[g1].gaps) { errmsg = "missing log blocks"; goto fail; } if(g0 == loggensucc(g1)) { int tmp = g0; g0 = g1; g1 = tmp; } else if(g1 != loggensucc(g0)) { errmsg = "nonsequential generations in log"; goto fail; } if(logseqof(logpathmap[geninfo[g1].start].path) != 0) { errmsg = "swept log does not start at 0"; goto fail; } if(logseqof(logpathmap[geninfo[g0].start].path) == logseqof(logpathmap[geninfo[g1].end - 1].path)) { /* * duplicate block * as the log never gets bigger, information from active[n] is either entirely in swept[n], * or split between swept[n-1] and swept[n]. we can safely remove swept[n]. this might * leave some duplication between swept[n - 1] and active[n], but this is always true * for a partially swept log */ logfsbootfettleblock(server->lb, logpathmap[geninfo[g1].end - 1].block, LogfsTnone, ~0, nil); geninfo[g1].end--; } if(logseqof(logpathmap[geninfo[g0].start].path) < logseqof(logpathmap[geninfo[g1].end - 1].path)) { errmsg = "active log overlaps end of swept log"; goto fail; } populate(server->activelog, g0, logseqof(logpathmap[geninfo[g0].start].path), logseqof(logpathmap[geninfo[g0].end - 1].path), logpathmap + geninfo[g0].start); if(server->sweptlog == nil) { errmsg = logfslogsegmentnew(server, g1, &server->sweptlog); if(errmsg) goto fail; } populate(server->sweptlog, g1, logseqof(logpathmap[geninfo[g1].start].path), logseqof(logpathmap[geninfo[g1].end - 1].path), logpathmap + geninfo[g1].start); break; default: errmsg = "more than two generations in log"; goto fail; } goto ok; fail: logfslogsegmentfree(&server->sweptlog); ok: logfsfreemem(logpathmap); logfsfreemem(datapathmap); return errmsg; }