code: mafs

ref: 61ab76ca10766edc8728de5cc6e1d0972c99ebc9
dir: /find.c/

View raw version
#include <u.h>
#include <libc.h>
#include "dat.h"
#include "fns.h"

/*
	for an invalid used block, show the directory tree leading to it

	BUG: if the block is a Dentry, does not find it?
 */
enum
{
	Notfound = 0,
	Found,
	Ndir = 128,
};

typedef	struct Parent Parent;
struct Parent
{
	u64 blkno;
	s8 name[Namelen];
};

int debug = 0;
char *devfile = nil;
Parent parents[Ndir] = {0};
u64 findblkno;

u8 walkfile(s8 depth, u64 blkno);
u8 walkdirectory(s8 depth, u64 blkno);
u8 walkindir(s8 depth, u64 blkno, u8 tag, u8 bottomtag, u64 qpath);

static void
usage(void)
{
	fprint(2, "usage: used [-D ] fsfile blkno\n");
	exits("usage");
}

void
showparents(void)
{
	s8 i;

	for(i =0; i<Ndir-1 && parents[i].blkno != 0; i++){
		print("%d %llud %s\n", i, parents[i].blkno, parents[i].name);
	}
}

u8
issearchblock(u64 blkno, u16 len)
{
	if(blkno <= findblkno && findblkno < blkno+len)
		return Found;
	return Notfound;
}

void
main(int argc, char *argv[])
{
	u64 size, nblocks;

	ARGBEGIN{
	default:	usage();
	case 'D':	debug++; break;
	}ARGEND

	if(argc != 2)
		usage();

	devfile = argv[0];
	if(devfile == nil)
		sysfatal("no disk file");

	findblkno = atoll(argv[1]);
	if(findblkno == 0){
		fprint(2, "invalid block number %llud\n", findblkno);
		exits(nil);
	}

	if(devfile == nil)
		sysfatal("no disk file");

	if (access(devfile, AREAD) == -1)
		sysfatal("%s cannot access device", devfile);

	size = devinit(devfile);
	if(size == 0)
		panic("null size %s", devfile);

	nblocks = size/Blocksize;
	if(debug)
		print("%s %llud bytes %llud blocks\n", devfile, size, size/Blocksize);
	if(findblkno >= nblocks){
		fprint(2, "searching for block %llud >= nblocks %llud\n", findblkno, nblocks);
		exits(nil);
	}
	if(issearchblock(Bdmagic, 1)){
		fprint(1, "magic block number %llud\n", findblkno);
		exits(nil);
	}
	if(walkdirectory(0, Bdroot)){
		showparents();
	}else{
		fprint(2, "unused block %llud\n", findblkno);
	}
	exits(nil);
}

void
showdepth(s8 depth, u64 blkno, char *name)
{
	int i;

	for(i = 0; i<depth; i++)
		print(" ");
	print("%llud:%s\n", blkno, name);
}

void
addparent(s8 depth, u64 dblkno, s8 *name, u8 namelen)
{
	s8 i;

	for(i =Ndir-1; i>depth; i--){
		parents[i].blkno = 0;
		memset(parents[i].name, 0, Namelen);
	}
	parents[depth].blkno = dblkno;
	if(namelen == 0)
		strncpy(parents[depth].name, name, Namelen);
	else
		strncpy(parents[depth].name, name, namelen);

}

u8
walkdirectory(s8 depth, u64 blkno)
{
	u8 buf[Blocksize], cbuf[Blocksize];
	Dentry *d, *cd;
	Indirect *ct;
	u64 cblkno;
	int i;

	devread(blkno, buf, 1);
	d = (Dentry*)buf;
	if(debug)
		print("walkdirectory %llud tag %s name %s d->qpath %llud\n",
				blkno, tagnames[d->tag], d->name, d->qpath);
	if(debug)
		showdepth(depth, blkno, d->name);
	if(d->tag != Tdentry || d->path != d->qpath){
		if(debug)
			print("walkdirectory invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
					blkno, tagnames[Tdentry], d->qpath, tagnames[d->tag], d->path);
		fprint(2, "%llud\n", blkno);
	}/*else
		print("%llud name %s namelen %d\n", blkno, d->name, d->namelen);*/
	addparent(depth, blkno, d->name, d->namelen);
	if(issearchblock(blkno, 1))
		return Found;
	for(i = 0; i<Ndblock; i++){
		cblkno = d->dblocks[i];
		if(cblkno == 0)
			return Notfound;
		devread(cblkno, cbuf, 1);
		cd = (Dentry*)cbuf;
		if((cd->mode & DMDIR) > 0){
			if(walkdirectory(depth+1, cblkno))
				return Found;
		}else{
			if(walkfile(depth+1, cblkno)){
			print("walkdirectory: walkfile returning Found\n");
				return Found;
			}
		}
	}
	for(i = 0; i<Niblock; i++){
		cblkno = d->iblocks[i];
		if(cblkno == 0)
			return Notfound;
		devread(cblkno, cbuf, 1);
		ct = (Indirect*)cbuf;
		if(ct->tagi == Tind0+i){
			if(walkindir(depth, cblkno, Tind0+i, Tdentry, d->qpath))
				return Found;
		}else{
			fprint(2, "invalid indir tag %llud\n", cblkno);
			fprint(2, "%llud\n", cblkno);
		}
	}
	return Notfound;
}

/* returns 0 for invalid, 1 for valid blocks */
u8
checkvalid(u64 blkno, u8 dtag, u64 dpath, u8 tag, u64 qpath, u16 len)
{
	if(dtag != tag || dpath != qpath){
		/* if(debug) */
			fprint(2, "checkvalid invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
					blkno, tagnames[tag], qpath, tagnames[dtag], dpath);
		fprint(2, "invalid used: %llud\n", blkno);
		return 0;
	}else if(debug)
		print("valid block %llud %llud %ud\n", blkno, blkno+len, len);
	return 1;
}

u8
walkindir(s8 depth, u64 blkno, u8 tag, u8 bottomtag, u64 qpath)
{
	u8 buf[Blocksize], cbuf[Blocksize];
	u64 ebuf[Nu64perblock];
	Indirect *t;
	Data *ct;
	u64 cblkno, path;
	int i;

	devread(blkno, buf, 1);
	if(issearchblock(blkno, 1))
		return Found;
	t = (Indirect*)buf;
	if(checkvalid(blkno, t->tagi, t->pathi, tag, qpath, 1)){
		if(t->tagi == Tind0){
			for(i = 0; i<Nindperblock; i++){
				cblkno = t->bufa[i];
				if(cblkno == 0)
					return Notfound;
				if(bottomtag == Tdentry)
					/* another directory */
					if(walkdirectory(depth, cblkno))
						return Found;
				else{
					devread(cblkno, cbuf, 1);
					ct = (Data*)cbuf;
					devread(cblkno+ct->len-1, ebuf, 1);
					path = ebuf[Dpathidx];
					if(checkvalid(cblkno, ct->tag, path, bottomtag, qpath, ct->len) &&
						issearchblock(cblkno, ct->len))
						return Found;
				}
			}
		}else{
			for(i = 0; i<Nindperblock; i++){
				cblkno = t->bufa[i];
				if(cblkno == 0)
					return Notfound;
				/* check tag */
				if(walkindir(depth, cblkno, tag-1,  bottomtag, qpath))
					return Found;
			}
		}
	}
	return Notfound;
}

u8
walkfile(s8 depth, u64 blkno)
{
	u8 buf[Blocksize], cbuf[Blocksize];
	u64 ebuf[Nu64perblock];
	Dentry *d;
	Data *ct;
	Indirect *it;
	u64 cblkno, path;
	int i;

	devread(blkno, buf, 1);
	d = (Dentry*)buf;
	if(debug)
		print("walkfile %llud tag %s name %s d->qpath %llud\n",
				blkno, tagnames[d->tag], d->name, d->qpath);
	if(debug)
		showdepth(depth, blkno, d->name);
	if(d->tag != Tdentry || d->path != d->qpath){
		if(debug)
			print("walkfile invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
					blkno, tagnames[Tdentry], d->qpath, tagnames[d->tag], d->path);
		fprint(2, "%llud\n", blkno);
	}/*else
		print("%llud\n", blkno);*/
	addparent(depth, blkno, d->name, d->namelen);
	if(issearchblock(blkno, 1))
		return Found;
	if(d->size <= Ddatasize)
		return Notfound;
	for(i = 0; i<Ndblock; i++){
		cblkno = d->dblocks[i];
		if(cblkno == 0)
			return Notfound;
		devread(cblkno, cbuf, 1);
		ct = (Data*)cbuf;
		devread(cblkno+ct->len-1, ebuf, 1);
		path = ebuf[Dpathidx];
		if(checkvalid(cblkno, ct->tag, path,
						Tdata, d->qpath, ct->len) &&
			issearchblock(cblkno, ct->len))
			return Found;
	}
	for(i = 0; i<Niblock; i++){
		cblkno = d->iblocks[i];
		if(cblkno == 0)
			return Notfound;
		devread(cblkno, cbuf, 1);
		it=(Indirect*)cbuf;
		if(it->tagi == Tind0+i){
			if(walkindir(depth, cblkno, Tind0+i, Tdata, d->qpath))
				return Found;
		}else{
			fprint(2, "invalid indir tag %llud\n", cblkno);
			fprint(2, "%llud\n", cblkno);
		}
	}
	return Notfound;
}