ref: 333ae58f37c2c8f79f7d7078283a30e42c4d7a27
dir: /check.c/
#include "stdinc.h"
#include "dat.h"
#include "fns.h"
static void checkDirs(Fsck*);
static void checkEpochs(Fsck*);
static void checkLeak(Fsck*);
static void closenop(Fsck*, Block*, u32int);
static void clrenop(Fsck*, Block*, int);
static void clrinop(Fsck*, char*, MetaBlock*, int, Block*);
static void error(Fsck*, char*, ...);
static int getBit(uchar*, u32int);
static int printnop(char*, ...);
static void setBit(uchar*, u32int);
static int walkEpoch(Fsck *chk, Block *b, uchar score[VtScoreSize],
int type, u32int tag, u32int epoch);
static void warn(Fsck*, char*, ...);
#pragma varargck argpos error 2
#pragma varargck argpos printnop 1
#pragma varargck argpos warn 2
static Fsck*
checkInit(Fsck *chk)
{
chk->cache = chk->fs->cache;
chk->nblocks = cacheLocalSize(chk->cache, PartData);;
chk->bsize = chk->fs->blockSize;
chk->walkdepth = 0;
chk->hint = 0;
chk->quantum = chk->nblocks/100;
if(chk->quantum == 0)
chk->quantum = 1;
if(chk->print == nil)
chk->print = printnop;
if(chk->clre == nil)
chk->clre = clrenop;
if(chk->close == nil)
chk->close = closenop;
if(chk->clri == nil)
chk->clri = clrinop;
return chk;
}
/*
* BUG: Should merge checkEpochs and checkDirs so that
* bad blocks are only reported once, and so that errors in checkEpochs
* can have the affected file names attached, and so that the file system
* is only read once.
*
* Also should summarize the errors instead of printing for every one
* (e.g., XXX bad or unreachable blocks in /active/usr/rsc/foo).
*/
void
fsCheck(Fsck *chk)
{
Block *b;
Super super;
checkInit(chk);
b = superGet(chk->cache, &super);
if(b == nil){
chk->print("could not load super block: %r");
return;
}
blockPut(b);
chk->hint = super.active;
checkEpochs(chk);
chk->smap = vtmallocz(chk->nblocks/8+1);
checkDirs(chk);
vtfree(chk->smap);
}
static void checkEpoch(Fsck*, u32int);
/*
* Walk through all the blocks in the write buffer.
* Then we can look for ones we missed -- those are leaks.
*/
static void
checkEpochs(Fsck *chk)
{
u32int e;
uint nb;
nb = chk->nblocks;
chk->amap = vtmallocz(nb/8+1);
chk->emap = vtmallocz(nb/8+1);
chk->xmap = vtmallocz(nb/8+1);
chk->errmap = vtmallocz(nb/8+1);
for(e = chk->fs->ehi; e >= chk->fs->elo; e--){
memset(chk->emap, 0, chk->nblocks/8+1);
memset(chk->xmap, 0, chk->nblocks/8+1);
checkEpoch(chk, e);
}
checkLeak(chk);
vtfree(chk->amap);
vtfree(chk->emap);
vtfree(chk->xmap);
vtfree(chk->errmap);
}
static void
checkEpoch(Fsck *chk, u32int epoch)
{
u32int a;
Block *b;
Entry e;
Label l;
chk->print("checking epoch %ud...\n", epoch);
for(a=0; a<chk->nblocks; a++){
if(!readLabel(chk->cache, &l, (a+chk->hint)%chk->nblocks)){
error(chk, "could not read label for addr 0x%.8#ux", a);
continue;
}
if(l.tag == RootTag && l.epoch == epoch)
break;
}
if(a == chk->nblocks){
chk->print("could not find root block for epoch %ud", epoch);
return;
}
a = (a+chk->hint)%chk->nblocks;
b = cacheLocalData(chk->cache, a, BtDir, RootTag, OReadOnly, 0);
if(b == nil){
error(chk, "could not read root block 0x%.8#ux: %r", a);
return;
}
/* no one should point at root blocks */
setBit(chk->amap, a);
setBit(chk->emap, a);
setBit(chk->xmap, a);
/*
* First entry is the rest of the file system.
* Second entry is link to previous epoch root,
* just a convenience to help the search.
*/
if(!entryUnpack(&e, b->data, 0)){
error(chk, "could not unpack root block 0x%.8#ux: %r", a);
blockPut(b);
return;
}
walkEpoch(chk, b, e.score, BtDir, e.tag, epoch);
if(entryUnpack(&e, b->data, 1))
chk->hint = globalToLocal(e.score);
blockPut(b);
}
/*
* When b points at bb, need to check:
*
* (i) b.e in [bb.e, bb.eClose)
* (ii) if b.e==bb.e, then no other b' in e points at bb.
* (iii) if !(b.state&Copied) and b.e==bb.e then no other b' points at bb.
* (iv) if b is active then no other active b' points at bb.
* (v) if b is a past life of b' then only one of b and b' is active
* (too hard to check)
*/
static int
walkEpoch(Fsck *chk, Block *b, uchar score[VtScoreSize], int type, u32int tag,
u32int epoch)
{
int i, ret;
u32int addr, ep;
Block *bb;
Entry e;
if(b && chk->walkdepth == 0 && chk->printblocks)
chk->print("%V %d %#.8ux %#.8ux\n", b->score, b->l.type,
b->l.tag, b->l.epoch);
if(!chk->useventi && globalToLocal(score) == NilBlock)
return 1;
chk->walkdepth++;
bb = cacheGlobal(chk->cache, score, type, tag, OReadOnly);
if(bb == nil){
error(chk, "could not load block %V type %d tag %ux: %r",
score, type, tag);
chk->walkdepth--;
return 0;
}
if(chk->printblocks)
chk->print("%*s%V %d %#.8ux %#.8ux\n", chk->walkdepth*2, "",
score, type, tag, bb->l.epoch);
ret = 0;
addr = globalToLocal(score);
if(addr == NilBlock){
ret = 1;
goto Exit;
}
if(b){
/* (i) */
if(b->l.epoch < bb->l.epoch || bb->l.epochClose <= b->l.epoch){
error(chk, "walk: block %#ux [%ud, %ud) points at %#ux [%ud, %ud)",
b->addr, b->l.epoch, b->l.epochClose,
bb->addr, bb->l.epoch, bb->l.epochClose);
goto Exit;
}
/* (ii) */
if(b->l.epoch == epoch && bb->l.epoch == epoch){
if(getBit(chk->emap, addr)){
error(chk, "walk: epoch join detected: addr %#ux %L",
bb->addr, &bb->l);
goto Exit;
}
setBit(chk->emap, addr);
}
/* (iii) */
if(!(b->l.state&BsCopied) && b->l.epoch == bb->l.epoch){
if(getBit(chk->xmap, addr)){
error(chk, "walk: copy join detected; addr %#ux %L",
bb->addr, &bb->l);
goto Exit;
}
setBit(chk->xmap, addr);
}
}
/* (iv) */
if(epoch == chk->fs->ehi){
/*
* since epoch==fs->ehi is first, amap is same as
* ``have seen active''
*/
if(getBit(chk->amap, addr)){
error(chk, "walk: active join detected: addr %#ux %L",
bb->addr, &bb->l);
goto Exit;
}
if(bb->l.state&BsClosed)
error(chk, "walk: addr %#ux: block is in active tree but is closed",
addr);
}else
if(!getBit(chk->amap, addr))
if(!(bb->l.state&BsClosed)){
// error(chk, "walk: addr %#ux: block is not in active tree, not closed (%d)",
// addr, bb->l.epochClose);
chk->close(chk, bb, epoch+1);
chk->nclose++;
}
if(getBit(chk->amap, addr)){
ret = 1;
goto Exit;
}
setBit(chk->amap, addr);
if(chk->nseen++%chk->quantum == 0)
chk->print("check: visited %d/%d blocks (%.0f%%)\n",
chk->nseen, chk->nblocks, chk->nseen*100./chk->nblocks);
b = nil; /* make sure no more refs to parent */
USED(b);
switch(type){
default:
/* pointer block */
for(i = 0; i < chk->bsize/VtScoreSize; i++)
if(!walkEpoch(chk, bb, bb->data + i*VtScoreSize,
type-1, tag, epoch)){
setBit(chk->errmap, bb->addr);
chk->clrp(chk, bb, i);
chk->nclrp++;
}
break;
case BtData:
break;
case BtDir:
for(i = 0; i < chk->bsize/VtEntrySize; i++){
if(!entryUnpack(&e, bb->data, i)){
// error(chk, "walk: could not unpack entry: %ux[%d]: %r",
// addr, i);
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, i);
chk->nclre++;
continue;
}
if(!(e.flags & VtEntryActive))
continue;
if(0) fprint(2, "%x[%d] tag=%x snap=%d score=%V\n",
addr, i, e.tag, e.snap, e.score);
ep = epoch;
if(e.snap != 0){
if(e.snap >= epoch){
// error(chk, "bad snap in entry: %ux[%d] snap = %ud: epoch = %ud",
// addr, i, e.snap, epoch);
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, i);
chk->nclre++;
continue;
}
continue;
}
if(e.flags & VtEntryLocal){
if(e.tag < UserTag)
if(e.tag != RootTag || tag != RootTag || i != 1){
// error(chk, "bad tag in entry: %ux[%d] tag = %ux",
// addr, i, e.tag);
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, i);
chk->nclre++;
continue;
}
}else
if(e.tag != 0){
// error(chk, "bad tag in entry: %ux[%d] tag = %ux",
// addr, i, e.tag);
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, i);
chk->nclre++;
continue;
}
if(!walkEpoch(chk, bb, e.score, entryType(&e),
e.tag, ep)){
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, i);
chk->nclre++;
}
}
break;
}
ret = 1;
Exit:
chk->walkdepth--;
blockPut(bb);
return ret;
}
/*
* We've just walked the whole write buffer. Notice blocks that
* aren't marked available but that we didn't visit. They are lost.
*/
static void
checkLeak(Fsck *chk)
{
u32int a, nfree, nlost;
Block *b;
Label l;
nfree = 0;
nlost = 0;
for(a = 0; a < chk->nblocks; a++){
if(!readLabel(chk->cache, &l, a)){
error(chk, "could not read label: addr 0x%ux %d %d: %r",
a, l.type, l.state);
continue;
}
if(getBit(chk->amap, a))
continue;
if(l.state == BsFree || l.epochClose <= chk->fs->elo ||
l.epochClose == l.epoch){
nfree++;
setBit(chk->amap, a);
continue;
}
if(l.state&BsClosed)
continue;
nlost++;
// warn(chk, "unreachable block: addr 0x%ux type %d tag 0x%ux "
// "state %s epoch %ud close %ud", a, l.type, l.tag,
// bsStr(l.state), l.epoch, l.epochClose);
b = cacheLocal(chk->cache, PartData, a, OReadOnly);
if(b == nil){
error(chk, "could not read block 0x%#.8ux", a);
continue;
}
chk->close(chk, b, 0);
chk->nclose++;
setBit(chk->amap, a);
blockPut(b);
}
chk->print("fsys blocks: total=%ud used=%ud(%.1f%%) free=%ud(%.1f%%) lost=%ud(%.1f%%)\n",
chk->nblocks,
chk->nblocks - nfree-nlost,
100.*(chk->nblocks - nfree - nlost)/chk->nblocks,
nfree, 100.*nfree/chk->nblocks,
nlost, 100.*nlost/chk->nblocks);
}
/*
* Check that all sources in the tree are accessible.
*/
static Source *
openSource(Fsck *chk, Source *s, char *name, uchar *bm, u32int offset,
u32int gen, int dir, MetaBlock *mb, int i, Block *b)
{
Source *r;
r = nil;
if(getBit(bm, offset)){
warn(chk, "multiple references to source: %s -> %d",
name, offset);
goto Err;
}
setBit(bm, offset);
r = sourceOpen(s, offset, OReadOnly, 0);
if(r == nil){
warn(chk, "could not open source: %s -> %d: %r", name, offset);
goto Err;
}
if(r->gen != gen){
warn(chk, "source has been removed: %s -> %d", name, offset);
goto Err;
}
if(r->dir != dir){
warn(chk, "dir mismatch: %s -> %d", name, offset);
goto Err;
}
return r;
Err:
chk->clri(chk, name, mb, i, b);
chk->nclri++;
if(r)
sourceClose(r);
return nil;
}
typedef struct MetaChunk MetaChunk;
struct MetaChunk {
ushort offset;
ushort size;
ushort index;
};
static int
offsetCmp(void *s0, void *s1)
{
MetaChunk *mc0, *mc1;
mc0 = s0;
mc1 = s1;
if(mc0->offset < mc1->offset)
return -1;
if(mc0->offset > mc1->offset)
return 1;
return 0;
}
/*
* Fsck that MetaBlock has reasonable header, sorted entries,
*/
static int
chkMetaBlock(MetaBlock *mb)
{
MetaChunk *mc;
int oo, o, n, i;
uchar *p;
mc = vtmalloc(mb->nindex*sizeof(MetaChunk));
p = mb->buf + MetaHeaderSize;
for(i = 0; i < mb->nindex; i++){
mc[i].offset = p[0]<<8 | p[1];
mc[i].size = p[2]<<8 | p[3];
mc[i].index = i;
p += MetaIndexSize;
}
qsort(mc, mb->nindex, sizeof(MetaChunk), offsetCmp);
/* check block looks ok */
oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
o = oo;
n = 0;
for(i = 0; i < mb->nindex; i++){
o = mc[i].offset;
n = mc[i].size;
if(o < oo)
goto Err;
oo += n;
}
if(o+n > mb->size || mb->size - oo != mb->free)
goto Err;
vtfree(mc);
return 1;
Err:
if(0){
fprint(2, "metaChunks failed!\n");
oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
for(i=0; i<mb->nindex; i++){
fprint(2, "\t%d: %d %d\n", i, mc[i].offset,
mc[i].offset + mc[i].size);
oo += mc[i].size;
}
fprint(2, "\tused=%d size=%d free=%d free2=%d\n",
oo, mb->size, mb->free, mb->size - oo);
}
vtfree(mc);
return 0;
}
static void
scanSource(Fsck *chk, char *name, Source *r)
{
u32int a, nb, o;
Block *b;
Entry e;
if(!chk->useventi && globalToLocal(r->score)==NilBlock)
return;
if(!sourceGetEntry(r, &e)){
error(chk, "could not get entry for %s", name);
return;
}
a = globalToLocal(e.score);
if(!chk->useventi && a==NilBlock)
return;
if(getBit(chk->smap, a))
return;
setBit(chk->smap, a);
nb = (sourceGetSize(r) + r->dsize-1) / r->dsize;
for(o = 0; o < nb; o++){
b = sourceBlock(r, o, OReadOnly);
if(b == nil){
error(chk, "could not read block in data file %s", name);
continue;
}
if(b->addr != NilBlock && getBit(chk->errmap, b->addr)){
warn(chk, "previously reported error in block %ux is in file %s",
b->addr, name);
}
blockPut(b);
}
}
/*
* Walk the source tree making sure that the BtData
* sources containing directory entries are okay.
*/
static void
chkDir(Fsck *chk, char *name, Source *source, Source *meta)
{
int i;
u32int a1, a2, nb, o;
char *s, *nn;
uchar *bm;
Block *b, *bb;
DirEntry de;
Entry e1, e2;
MetaBlock mb;
MetaEntry me;
Source *r, *mr;
if(!chk->useventi && globalToLocal(source->score)==NilBlock &&
globalToLocal(meta->score)==NilBlock)
return;
if(!sourceLock2(source, meta, OReadOnly)){
warn(chk, "could not lock sources for %s: %r", name);
return;
}
if(!sourceGetEntry(source, &e1) || !sourceGetEntry(meta, &e2)){
warn(chk, "could not load entries for %s: %r", name);
return;
}
a1 = globalToLocal(e1.score);
a2 = globalToLocal(e2.score);
if((!chk->useventi && a1==NilBlock && a2==NilBlock)
|| (getBit(chk->smap, a1) && getBit(chk->smap, a2))){
sourceUnlock(source);
sourceUnlock(meta);
return;
}
setBit(chk->smap, a1);
setBit(chk->smap, a2);
bm = vtmallocz(sourceGetDirSize(source)/8 + 1);
nb = (sourceGetSize(meta) + meta->dsize - 1)/meta->dsize;
for(o = 0; o < nb; o++){
b = sourceBlock(meta, o, OReadOnly);
if(b == nil){
error(chk, "could not read block in meta file: %s[%ud]: %r",
name, o);
continue;
}
if(0) fprint(2, "source %V:%d block %d addr %d\n", source->score,
source->offset, o, b->addr);
if(b->addr != NilBlock && getBit(chk->errmap, b->addr))
warn(chk, "previously reported error in block %ux is in %s",
b->addr, name);
if(!mbUnpack(&mb, b->data, meta->dsize)){
error(chk, "could not unpack meta block: %s[%ud]: %r",
name, o);
blockPut(b);
continue;
}
if(!chkMetaBlock(&mb)){
error(chk, "bad meta block: %s[%ud]: %r", name, o);
blockPut(b);
continue;
}
s = nil;
for(i=mb.nindex-1; i>=0; i--){
meUnpack(&me, &mb, i);
if(!deUnpack(&de, &me)){
error(chk,
"could not unpack dir entry: %s[%ud][%d]: %r",
name, o, i);
continue;
}
if(s && strcmp(s, de.elem) <= 0)
error(chk,
"dir entry out of order: %s[%ud][%d] = %s last = %s",
name, o, i, de.elem, s);
vtfree(s);
s = vtstrdup(de.elem);
nn = smprint("%s/%s", name, de.elem);
if(nn == nil){
error(chk, "out of memory");
continue;
}
if(chk->printdirs)
if(de.mode&ModeDir)
chk->print("%s/\n", nn);
if(chk->printfiles)
if(!(de.mode&ModeDir))
chk->print("%s\n", nn);
if(!(de.mode & ModeDir)){
r = openSource(chk, source, nn, bm, de.entry,
de.gen, 0, &mb, i, b);
if(r != nil){
if(sourceLock(r, OReadOnly)){
scanSource(chk, nn, r);
sourceUnlock(r);
}
sourceClose(r);
}
deCleanup(&de);
free(nn);
continue;
}
r = openSource(chk, source, nn, bm, de.entry,
de.gen, 1, &mb, i, b);
if(r == nil){
deCleanup(&de);
free(nn);
continue;
}
mr = openSource(chk, source, nn, bm, de.mentry,
de.mgen, 0, &mb, i, b);
if(mr == nil){
sourceClose(r);
deCleanup(&de);
free(nn);
continue;
}
if(!(de.mode&ModeSnapshot) || chk->walksnapshots)
chkDir(chk, nn, r, mr);
sourceClose(mr);
sourceClose(r);
deCleanup(&de);
free(nn);
deCleanup(&de);
}
vtfree(s);
blockPut(b);
}
nb = sourceGetDirSize(source);
for(o=0; o<nb; o++){
if(getBit(bm, o))
continue;
r = sourceOpen(source, o, OReadOnly, 0);
if(r == nil)
continue;
warn(chk, "non referenced entry in source %s[%d]", name, o);
if((bb = sourceBlock(source, o/(source->dsize/VtEntrySize),
OReadOnly)) != nil){
if(bb->addr != NilBlock){
setBit(chk->errmap, bb->addr);
chk->clre(chk, bb, o%(source->dsize/VtEntrySize));
chk->nclre++;
}
blockPut(bb);
}
sourceClose(r);
}
sourceUnlock(source);
sourceUnlock(meta);
vtfree(bm);
}
static void
checkDirs(Fsck *chk)
{
Source *r, *mr;
sourceLock(chk->fs->source, OReadOnly);
r = sourceOpen(chk->fs->source, 0, OReadOnly, 0);
mr = sourceOpen(chk->fs->source, 1, OReadOnly, 0);
sourceUnlock(chk->fs->source);
chkDir(chk, "", r, mr);
sourceClose(r);
sourceClose(mr);
}
static void
setBit(uchar *bmap, u32int addr)
{
if(addr == NilBlock)
return;
bmap[addr>>3] |= 1 << (addr & 7);
}
static int
getBit(uchar *bmap, u32int addr)
{
if(addr == NilBlock)
return 0;
return (bmap[addr>>3] >> (addr & 7)) & 1;
}
static void
error(Fsck *chk, char *fmt, ...)
{
char buf[256];
va_list arg;
static int nerr;
va_start(arg, fmt);
vseprint(buf, buf+sizeof buf, fmt, arg);
va_end(arg);
chk->print("error: %s\n", buf);
// if(nerr++ > 20)
// sysfatal("too many errors");
}
static void
warn(Fsck *chk, char *fmt, ...)
{
char buf[256];
va_list arg;
static int nerr;
va_start(arg, fmt);
vseprint(buf, buf+sizeof buf, fmt, arg);
va_end(arg);
chk->print("error: %s\n", buf);
}
static void
clrenop(Fsck*, Block*, int)
{
}
static void
closenop(Fsck*, Block*, u32int)
{
}
static void
clrinop(Fsck*, char*, MetaBlock*, int, Block*)
{
}
static int
printnop(char*, ...)
{
return 0;
}