ref: 61ab76ca10766edc8728de5cc6e1d0972c99ebc9
dir: /find.c/
#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;
}