ref: 75c92428225428c8fde2d015f010e608a0b12f1d
dir: purgatorio/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;
}