harvey/sys/src/cmd/fossil/check.c

/*
 * This file is part of the UCB release of Plan 9. It is subject to the license
 * terms in the LICENSE file found in the top-level directory of this
 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
 * part of the UCB release of Plan 9, including this file, may be copied,
 * modified, propagated, or distributed except according to the terms contained
 * in the LICENSE file.
 */

#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*, uint32_t);
static void	clrenop(Fsck*, Block*, int);
static void	clrinop(Fsck*, char*, MetaBlock*, int, Block*);
static void	error(Fsck*, char*, ...);
static int	getBit(uint8_t*, uint32_t);
static int	printnop(char*, ...);
static void	setBit(uint8_t*, uint32_t);
static int	walkEpoch(Fsck *chk, Block *b, uint8_t score[VtScoreSize],
			int type, uint32_t tag, uint32_t 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 = vtMemAllocZ(chk->nblocks/8+1);
	checkDirs(chk);
	vtMemFree(chk->smap);
}

static void checkEpoch(Fsck*, uint32_t);

/*
 * 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)
{
	uint32_t e;
	uint nb;

	nb = chk->nblocks;
	chk->amap = vtMemAllocZ(nb/8+1);
	chk->emap = vtMemAllocZ(nb/8+1);
	chk->xmap = vtMemAllocZ(nb/8+1);
	chk->errmap = vtMemAllocZ(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);
	vtMemFree(chk->amap);
	vtMemFree(chk->emap);
	vtMemFree(chk->xmap);
	vtMemFree(chk->errmap);
}

static void
checkEpoch(Fsck *chk, uint32_t epoch)
{
	uint32_t a;
	Block *b;
	Entry e;
	Label l;

	chk->print("checking epoch %u...\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 %u", 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, uint8_t score[VtScoreSize], int type,
	  uint32_t tag,
	uint32_t epoch)
{
	int i, ret;
	uint32_t 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 %x: %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 %#x [%u, %u) points at %#x [%u, %u)",
				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 %#x %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 %#x %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 %#x %L",
				bb->addr, &bb->l);
			goto Exit;
		}
		if(bb->l.state&BsClosed)
			error(chk, "walk: addr %#x: block is in active tree but is closed",
				addr);
	}else
		if(!getBit(chk->amap, addr))
			if(!(bb->l.state&BsClosed)){
				// error(chk, "walk: addr %#x: 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: %x[%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: %x[%d] snap = %u: epoch = %u",
					//	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: %x[%d] tag = %x",
					//	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: %x[%d] tag = %x",
					//	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)
{
	uint32_t 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%x %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%x type %d tag 0x%x "
//			"state %s epoch %u close %u", 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=%u used=%u(%.1f%%) free=%u(%.1f%%) lost=%u(%.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, uint8_t *bm, uint32_t offset,
	uint32_t 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 {
	uint16_t	offset;
	uint16_t	size;
	uint16_t	index;
};

static int
offsetCmp(const void *s0, const void *s1)
{
	const 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;
	uint8_t *p;

	mc = vtMemAlloc(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;

	vtMemFree(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);
}
	vtMemFree(mc);
	return 0;
}

static void
scanSource(Fsck *chk, char *name, Source *r)
{
	uint32_t 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 %x 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;
	uint32_t a1, a2, nb, o;
	char *s, *nn;
	uint8_t *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 = vtMemAllocZ(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[%u]: %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 %x is in %s",
				b->addr, name);

		if(!mbUnpack(&mb, b->data, meta->dsize)){
			error(chk, "could not unpack meta block: %s[%u]: %R",
				name, o);
			blockPut(b);
			continue;
		}
		if(!chkMetaBlock(&mb)){
			error(chk, "bad meta block: %s[%u]: %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[%u][%d]: %R",
					name, o, i);
				continue;
			}
			if(s && strcmp(s, de.elem) <= 0)
				error(chk,
			   "dir entry out of order: %s[%u][%d] = %s last = %s",
					name, o, i, de.elem, s);
			vtMemFree(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);

		}
		vtMemFree(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);
	vtMemFree(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(uint8_t *bmap, uint32_t addr)
{
	if(addr == NilBlock)
		return;

	bmap[addr>>3] |= 1 << (addr & 7);
}

static int
getBit(uint8_t *bmap, uint32_t 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)
//		vtFatal("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 *f, Block *b, int i)
{
}

static void
closenop(Fsck *f, Block *b, uint32_t u)
{
}

static void
clrinop(Fsck *f, char *c, MetaBlock *m, int i, Block *b)
{
}

static int
printnop(char *c, ...)
{
	return 0;
}