ref: be417f7391b034f397df39eb157ea212bfb46b1a
parent: e018b56413a42bf186383b0d1185c6d4db1323f6
author: 9ferno <gophone2015@gmail.com>
date: Tue Nov 29 16:49:01 EST 2022
fix find and used
--- a/9p.c
+++ b/9p.c
@@ -632,6 +632,7 @@
}
dchild->qpath = dchild->path = newqpath();
dchild->version = 0;
+ dchild->namelen = strlen(req->ifcall.name);
strncpy(dchild->name, req->ifcall.name, Namelen);
fid->qid = (Qid){dchild->path, 0, (perm&DMDIR) ? QTDIR : QTFILE};
aux->dblkno = cbuf->blkno;
--- a/TODO
+++ b/TODO
@@ -1,3 +1,4 @@
+test recovery from crash or improper shutdown
address the fragmentation of memunits
sort extents by size
does that help?
--- a/find.c
+++ b/find.c
@@ -8,19 +8,28 @@
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;
-u64 parents[Ndir];
+Parent parents[Ndir] = {0};
u64 findblkno;
-void walkdirectory(u64 blkno, s8 depth);
-void walkfile(u64 blkno, s8 depth);
+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)
@@ -30,9 +39,27 @@
}
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;
+ u64 size, nblocks;
ARGBEGIN{
default: usage();
@@ -52,6 +79,7 @@
exits(nil);
}
+print("findblkno %llud\n", findblkno);
if(devfile == nil)
sysfatal("no disk file");
@@ -61,109 +89,57 @@
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);
-
- walkdirectory(Bdroot, 0);
- exits(0);
-}
-
-void
-showparents(void)
-{
- s8 i;
-
- for(i =0; i<Ndir-1 && parents[i] != 0; i++){
- print("%d %llud\n", i, parents[i]);
+ if(findblkno >= nblocks){
+ fprint(2, "searching for block %llud >= nblocks %llud\n", findblkno, nblocks);
+ exits(nil);
}
-}
-
-int
-checkvalid(u64 blkno, u8 dtag, u64 dpath, u8 tag, u64 qpath, u16 len)
-{
- int ret = 1;
-
- 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, "used: %llud\n", blkno);
- ret=0;
- }/*else
- print("%llud\n", blkno);*/
- if(blkno <= findblkno || findblkno < blkno+len){
- showparents();
+ if(issearchblock(Bdmagic, Metadataunits)){
+ fprint(1, "magic block number %llud\n", findblkno);
exits(nil);
}
- return ret;
+ if(walkdirectory(0, Bdroot)){
+ showparents();
+ }else{
+ fprint(2, "unused block %llud\n", findblkno);
+ }
+ exits(nil);
}
void
-walkindir(u64 blkno, u8 tag, u8 bottomtag, u64 qpath, s8 depth)
+showdepth(s8 depth, u64 blkno, char *name)
{
- u8 buf[Metadatablocksize], *cbuf;
- Indirect *t;
- Data *ct;
- u64 cblkno, *bufa;
int i;
- devread(blkno, buf, Metadataunits);
- t = (Indirect*)buf;
- if(checkvalid(blkno, t->tagi, t->path, tag, qpath, Metadataunits)){
- if(t->tagi == Tind0){
- bufa = (u64*)buf;
- for(i = 0; i<Nindperblock; i++){
- cblkno = bufa[i];
- if(cblkno == 0)
- return;
- if(Tdentry == bottomtag)
- /* another directory */
- walkdirectory(cblkno, depth);
- else{
- cbuf = malloc(Blocksize);
- devread(cblkno, cbuf, 1);
- ct = (Data*)cbuf;
- checkvalid(cblkno, ct->tag, ct->path, bottomtag, qpath, ct->len);
- free(cbuf);
- }
- }
- }else{
- for(i = 0; i<Nindperblock; i++){
- cblkno = t->bufa[i];
- if(cblkno == 0)
- return;
- /* check tag */
- walkindir(cblkno, tag-1, bottomtag, qpath, depth);
- }
- }
- }
- return;
+ for(i = 0; i<depth; i++)
+ print(" ");
+ print("%llud:%s\n", blkno, name);
}
void
-addparent(s8 depth, u64 dblkno)
+addparent(s8 depth, u64 dblkno, s8 *name, u8 namelen)
{
s8 i;
for(i =Ndir-1; i>depth; i--){
- parents[i] = 0;
+ parents[i].blkno = 0;
+ memset(parents[i].name, 0, Namelen);
}
- parents[depth] = dblkno;
-}
+ parents[depth].blkno = dblkno;
+ if(namelen == 0)
+ strncpy(parents[depth].name, name, Namelen);
+ else
+ strncpy(parents[depth].name, name, namelen);
-void
-showdepth(s8 depth)
-{
- int i;
-
- for(i = 0; i<depth; i++)
- print(" ");
}
-void
-walkdirectory(u64 blkno, s8 depth)
+u8
+walkdirectory(s8 depth, u64 blkno)
{
- u8 buf[Metadatablocksize], *cbuf;
+ u8 buf[Metadatablocksize], cbuf[Metadatablocksize];
Dentry *d, *cd;
Indirect *ct;
u64 cblkno;
@@ -170,55 +146,119 @@
int i;
devread(blkno, buf, Metadataunits);
- d = (Dentry*)buf;
- showdepth(depth);
- print("%llud:%s\n", blkno, d->name);
+ recentmetadata(buf, &d, nil);
if(debug)
- print("walkdentry %llud tag %s name %s d->qpath %llud\n",
+ 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("walkdentry invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
+ 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\n", blkno);*/
- addparent(depth, blkno);
+ print("%llud name %s namelen %d\n", blkno, d->name, d->namelen);*/
+ addparent(depth, blkno, d->name, d->namelen);
+ if(issearchblock(blkno, Metadataunits))
+ return Found;
for(i = 0; i<Ndblock; i++){
cblkno = d->dblocks[i];
if(cblkno == 0)
- return;
- cbuf = malloc(Metadatablocksize);
+ return Notfound;
devread(cblkno, cbuf, Metadataunits);
- cd = (Dentry*)cbuf;
- if((cd->mode & DMDIR) > 0)
- walkdirectory(cblkno, depth+1);
- else
- walkfile(cblkno, depth+1);
- free(cbuf);
+ recentmetadata(cbuf, &cd, nil);
+ 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;
+ }
+ }
}
- cbuf = malloc(Metadatablocksize);
for(i = 0; i<Niblock; i++){
cblkno = d->iblocks[i];
if(cblkno == 0)
- return;
+ return Notfound;
devread(cblkno, cbuf, Metadataunits);
- ct = (Indirect*)cbuf;
+ recentmetadata(cbuf, &ct, nil);
if(ct->tagi == Tind0+i){
- walkindir(cblkno, Tind0+i, Tdentry, d->qpath, depth);
+ 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);
}
}
- free(cbuf);
- return;
+ return Notfound;
}
-void
-walkfile(u64 blkno, s8 depth)
+/* returns 0 for invalid, 1 for valid blocks */
+u8
+checkvalid(u64 blkno, u8 dtag, u64 dpath, u8 tag, u64 qpath, u16 len)
{
- u8 buf[Metadatablocksize], *cbuf;
+ 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[Metadatablocksize], cbuf[Metadatablocksize];
+ Indirect *t;
+ Data *ct;
+ u64 cblkno;
+ int i;
+
+ devread(blkno, buf, Metadataunits);
+ if(issearchblock(blkno, Metadataunits))
+ return Found;
+ recentmetadata(buf, &t, nil);
+ if(checkvalid(blkno, t->tagi, t->path, tag, qpath, Metadataunits)){
+ 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;
+ if(checkvalid(cblkno, ct->tag, ct->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[Metadatablocksize], cbuf[Metadatablocksize];
Dentry *d;
Data *ct;
Indirect *it;
@@ -226,46 +266,47 @@
int i;
devread(blkno, buf, Metadataunits);
- d = (Dentry*)buf;
- showdepth(depth);
- print("%llud:%s\n", blkno, d->name);
+ recentmetadata(buf, &d, nil);
if(debug)
- print("walkfile %llud tag %s name %s d->qid.path %llud\n",
+ 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("walkdentry invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
+ 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);
+ addparent(depth, blkno, d->name, d->namelen);
+ if(issearchblock(blkno, Metadataunits))
+ return Found;
if(d->size <= Ddatasize)
- return;
+ return Notfound;
for(i = 0; i<Ndblock; i++){
cblkno = d->dblocks[i];
if(cblkno == 0)
- return;
- cbuf = malloc(Metadatablocksize);
- devread(cblkno, cbuf, Metadataunits);
+ return Notfound;
+ devread(cblkno, cbuf, 1);
ct = (Data*)cbuf;
- checkvalid(cblkno, ct->tag, ct->path, Tdata, d->qpath, ct->len);
- free(cbuf);
+ if(checkvalid(cblkno, ct->tag, ct->path, Tdata, d->qpath, ct->len) &&
+ issearchblock(cblkno, ct->len))
+ return Found;
}
- cbuf = malloc(Metadatablocksize);
for(i = 0; i<Niblock; i++){
cblkno = d->iblocks[i];
if(cblkno == 0)
- return;
+ return Notfound;
devread(cblkno, cbuf, Metadataunits);
- it = (Indirect*)cbuf;
+ recentmetadata(cbuf, &it, nil);
if(it->tagi == Tind0+i){
- walkindir(cblkno, Tind0+i, Tdata, d->qpath, depth);
+ 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);
}
}
- free(cbuf);
- return;
+ return Notfound;
}
--- a/used.c
+++ b/used.c
@@ -87,10 +87,11 @@
return checkvalid(blkno, d->tag, d->path, tag, qpath, Metadataunits);
}
+/* not checking the ending path as it would take too long */
void
walkindir(u64 blkno, u16 tag, u16 bottomtag, u64 qpath)
{
- u8 buf[Metadatablocksize], *cbuf;
+ u8 buf[Metadatablocksize], cbuf[Metadatablocksize];
Indirect *t;
Data *da;
u64 cblkno;
@@ -106,7 +107,6 @@
if(cblkno == 0)
return;
if(bottomtag == Tdentry){
- cbuf = malloc(Metadatablocksize);
devread(cblkno, cbuf, Metadataunits);
recentmetadata(cbuf, &cd, nil);
if((cd->mode & DMDIR) > 0)
@@ -113,13 +113,10 @@
walkdirectory(cblkno);
else
walkfile(cblkno);
- free(cbuf);
}else{
- cbuf = malloc(Maxdatablockunits*Blocksize);
devread(cblkno, cbuf, 1);
da = (Data*)cbuf;
checkvalid(cblkno, da->tag, da->path, Tdata, da->path, da->len);
- free(cbuf);
}
}
}else{
@@ -137,7 +134,7 @@
void
walkdirectory(u64 blkno)
{
- u8 buf[Metadatablocksize], *cbuf;
+ u8 buf[Metadatablocksize], cbuf[Metadatablocksize];
Dentry *d, *cd;
Indirect *it;
u64 cblkno;
@@ -165,7 +162,6 @@
cblkno = d->dblocks[i];
if(cblkno == 0)
return;
- cbuf = malloc(Metadatablocksize);
devread(cblkno, cbuf, Metadataunits);
recentmetadata(cbuf, &cd, nil);
if((cd->mode & DMDIR) > 0)
@@ -172,9 +168,7 @@
walkdirectory(cblkno);
else
walkfile(cblkno);
- free(cbuf);
}
- cbuf = malloc(Metadatablocksize);
for(i = 0; i<Niblock; i++){
cblkno = d->iblocks[i];
if(cblkno == 0)
@@ -188,13 +182,70 @@
fprint(2, "%llud\n", cblkno);
}
}
- free(cbuf);
return;
}
+/* not checking the ending path as it would take too long */
void
walkfile(u64 blkno)
{
+ u8 buf[Metadatablocksize], cbuf[Metadatablocksize];
+ Dentry *d;
+ Data *ct;
+ Indirect *it;
+ u64 cblkno;
+ int i;
+
+ devread(blkno, buf, Metadataunits);
+ recentmetadata(buf, &d, nil);
+ if(chatty9p)
+ print("walkfile %llud tag %s name %s d->qid.path %llud\n",
+ blkno, tagnames[d->tag], d->name, d->qpath);
+ if(d->tag != Tdentry || d->path != d->qpath){
+ if(chatty9p)
+ 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);
+ add(&useds, blkno, Metadataunits);
+ }
+ /* do not list the data blocks used by /adm/frees
+ as they are considered to be free blocks */
+ if(blkno == Bdfrees)
+ return;
+ if(d->size <= Ddatasize)
+ return;
+
+ for(i = 0; i<Ndblock; i++){
+ cblkno = d->dblocks[i];
+ if(cblkno == 0)
+ return;
+ devread(cblkno, cbuf, 1);
+ ct = (Data*)cbuf;
+ checkvalid(cblkno, ct->tag, ct->path, Tdata, d->qpath, ct->len);
+ }
+ for(i = 0; i<Niblock; i++){
+ cblkno = d->iblocks[i];
+ if(cblkno == 0)
+ return;
+ devread(cblkno, cbuf, Metadataunits);
+ recentmetadata(cbuf, &it, nil);
+ if(it->tagi == Tind0+i){
+ walkindir(cblkno, Tind0+i, Tdata, d->qpath);
+ }else{
+ fprint(2, "invalid indir tag of block %llud %d %s\n",
+ cblkno, it->tagi, tagnames[it->tagi]);
+ fprint(2, "%llud\n", cblkno);
+ }
+ }
+ return;
+}
+
+/* checks the ending path and takes too long */
+void
+walkfileproper(u64 blkno)
+{
u8 buf[Metadatablocksize], *cbuf;
Dentry *d;
Data *ct;
@@ -241,14 +292,61 @@
return;
}
devread(cblkno, cbuf, Metadataunits);
- recentmetadata(buf, &it, nil);
+ recentmetadata(cbuf, &it, nil);
if(it->tagi == Tind0+i){
walkindir(cblkno, Tind0+i, Tdata, d->qpath);
}else{
- fprint(2, "invalid indir tag %llud\n", cblkno);
+ fprint(2, "invalid indir tag of block %llud\n", cblkno);
fprint(2, "%llud\n", cblkno);
}
}
free(cbuf);
+ return;
+}
+
+void
+walkindirproper(u64 blkno, u16 tag, u16 bottomtag, u64 qpath)
+{
+ u8 buf[Metadatablocksize], *cbuf;
+ Indirect *t;
+ Data *da;
+ u64 cblkno;
+ int i;
+ Dentry *cd;
+
+ devread(blkno, buf, Metadataunits);
+ recentmetadata(buf, &t, nil);
+ if(checkvalid(blkno, t->tagi, t->path, tag, qpath, Metadataunits)){
+ if(tag == Tind0){
+ for(i = 0; i<Nindperblock; i++){
+ cblkno = t->bufa[i];
+ if(cblkno == 0)
+ return;
+ if(bottomtag == Tdentry){
+ cbuf = malloc(Metadatablocksize);
+ devread(cblkno, cbuf, Metadataunits);
+ recentmetadata(cbuf, &cd, nil);
+ if((cd->mode & DMDIR) > 0)
+ walkdirectory(cblkno);
+ else
+ walkfile(cblkno);
+ free(cbuf);
+ }else{
+ cbuf = malloc(Maxdatablockunits*Blocksize);
+ devread(cblkno, cbuf, 1);
+ da = (Data*)cbuf;
+ checkvalid(cblkno, da->tag, da->path, Tdata, da->path, da->len);
+ free(cbuf);
+ }
+ }
+ }else{
+ for(i = 0; i<Nindperblock; i++){
+ cblkno = t->bufa[i];
+ if(cblkno == 0)
+ return;
+ walkindir(cblkno, tag-1, bottomtag, qpath);
+ }
+ }
+ }
return;
}