ref: f290dc94ee82b06b7c46822ccffea1c4d120d495
parent: 892eb4b8d46fe804aa9560542e6dd3b5b45963c3
author: 9ferno <gophone2015@gmail.com>
date: Sun Nov 6 17:51:59 EST 2022
use a circular linked list of least recently used units instead of one
--- a/TODO
+++ b/TODO
@@ -7,9 +7,6 @@
more consistent use of tree lock.
not using the tree lock for reads - replace RWlock with a Qlock sl
RWlock is better than the Qlock. Just need to enforce it better.
-file system checker
- fsck will be a different user space program
- update /adm/frees block from disk/used
EXCL files - maintain a list of locks in the tree
APPEND files
ORCLOSE
@@ -25,3 +22,4 @@
man/mafs.4 man/mafs.8
Add EXAMPLES
Add mafs.pdf as a resource
+Test that removed directories do not show up in the directory listing
--- a/dat.h
+++ b/dat.h
@@ -270,6 +270,7 @@
{Nworks = 1024, /* make this a parameter? */
Nprocs = 32, /* make this a parameter? */
+ Nlru = 32,
};
/*
--- a/docs/mafs.ms
+++ b/docs/mafs.ms
@@ -783,41 +783,54 @@
.sp
.ne 4
.ft B
-Free blocks - Extents
+Free blocks
.ft R
.sp
Free blocks are managed using Extents. The list of free blocks is stored to the disk when shutting down. If this state is not written, then the file system needs to be checked and the list of free blocks should be updated.
.sp
-When shutting down, the Extents are written to free blocks. This information is written to /adm/frees. Also, fsok in the super block is set to 1. When fsok = 0, run an fsck (filesystem checker) to correct any inconsistencies on the disk.
+When shutting down, the Extents are written to free blocks. This information can be accessed from /adm/frees. Also, fsok in the super block is set to 1. Mafs does not start until fsok is 1. When fsok = 0, run the sanity check that the unused blocks and the free blocks in /adm/frees match up. disk/reconcile identifies any missing blocks or blocks that are marked as both used and free.
.sp
+This process of fixing issues and setting fsok to 1 is manual. There is no automatic file system checker as in other file systems. This document aims to empower you with the knowledge to fix your file system issues instead of entrusting your precious data to an arbitrary decision maker such as the file system checker.
+.sp
A tag of Tfree and Qpnone represent a free block. If a directory entry is removed, the parent will have a zero'ed out child directory entry (Qid.path = 0) and a tag of Tdentry and Qpnone.
.sp
-.ne 14
-Algorithm to allocate blocks from Extents:
-.in 3n
-.br
-.ti 0
-1. Of all the Extents with the length we need, pick the Extent with the lowest block number (blkno).
-.br
-.ti 0
-2. If no Extent of the length we need is available, then break up the smallest extent.
-.in 0
.sp
+.ne 4
+.ft B
+Extents
+.ft R
+.sp
+Free blocks and memory are managed using Extents, an abstraction used to manage a continuous list of items.
+.sp
+An Extent represents a continuous list of items. An Extents is a list of such Extent's.
+.sp
.nf
struct Extent {struct Extent *low, *high; /* sorted by start */
- u64 start; /* where this extent starts from */
- u64 len; /* how many units in this extent */
+ u64 start; /* where this extent starts from */
+ u64 len; /* how many units in this extent */
+
+ /*
+ circular least recently used linked list
+ limited to Nlru items
+ */
+ struct Extent *prev, *next;
};
struct Extents {- Extent *lru; /* least recently used extent */
- Extent *head; /* find the first block in a jiffy */
+ Extent *head; /* find the first block in a jiffy */
QLock lck;
u32 n; /* number of extents */
Rendez isempty; /* fully used, nothing available */
+
+ u8 nlru; /* number of items in the lru linked list */
+ Extent *lru; /* least recently used extent in the circular lru linked list */
};
.fi
.sp
+To allocate n items from Extents, we find the lowest (by block number or memory address) extent that can satisfy our request. If a bigger Extent is available, slice it and take the portion we need.
+.sp
+If there is no available Extent to satisfy our request, panic().
+.sp
allocblock() and freeblock() use balloc() and bfree() respectively. balloc() assigns blocks from an extent and bfree() adds them to an extent for next allocation.
.sp
.PS
@@ -1083,10 +1096,12 @@
l a .
Program Description
_
-disk/mafs Start mafs on a disk
-disk/free List the free blocks
-disk/used List the used blocks
-disk/block Show the contents of a block
+disk/mafs Start mafs on a disk.
+disk/free List the free blocks. It reads the contents of /adm/frees.
+disk/used List the used blocks by traversing all directory entries.
+disk/block Show the contents of a block.
+disk/unused Given a list of used blocks, lists the unused blocks.
+disk/updatefrees update the contents of /adm/frees.
.TE
.sp
.TS
@@ -1221,33 +1236,31 @@
.sp
disk/find disk.file blocknumber
.sp
-.ne 5
-Build the list of free blocks.
+.ne 3
+Find the total number of blocks on a disk.
.sp
.nf
- disk/used /dev/sdF1/fs > used.blocks
- sort -n used.blocks -o used.blocks.sorted
- disk/unused used.blocks.sorted 11721040049 # 11721040049 is the total number of disk blocks
+ dd -if /dev/sdF1/fs -bs 512 -iseek 1 -count 1 -quiet 1 | awk '$1 == "nblocks" { print $2 }'.fi
.sp
-.ne 3
-Find the total number of blocks on a disk.
+.ne 5
+Build the list of free blocks. This should match the contents of /adm/frees.
.sp
.nf
- dd -if /dev/sdF1/fs -bs 512 -iseek 1 -count 1 -quiet 1 | awk '$1 == "nblocks" { print $2 }'+ disk/unused <{disk/used /dev/sdF1/fs} 11721040049 # 11721040049 is the total number of disk blocks+ disk/unused <{disk/used test.0/disk} 32 # 32 is the total number of disk blocks.fi
.sp
.ne 5
-Change /adm/frees.
+Change the contents of /adm/frees.
.sp
.nf
- disk/unused <{disk/used tests/test.0/disk} 32 | tr -d ' ' > unused.blocks- # cat unused.blocks
- disk/updatefrees tests/test.0/disk unused.blocks
+ disk/updatefrees tests/test.0/disk <{disk/unused <{disk/used tests/test.0/disk} 32 | tr -d ' '}+ disk/updatefrees /dev/sdF1/fs <{disk/unused <{disk/used /dev/sdF1/fs} 11721040049 | tr -d ' '}.fi
.sp
.ne 5
-A test of disk/used, disk/unused and disk/free programs. $nblocks is the total number of disk blocks. $disk is the disk.
+A sanity check that the file system is not corrupt by comparing that the unused blocks and free blocks match up. $nblocks is the total number of disk blocks. $disk is the disk.
.sp
.nf
diff <{disk/unused -l <{disk/used $disk} $nblocks}} <{disk/free $disk}@@ -1315,7 +1328,9 @@
tests/test.9 examples used by this document
tests/test.a write, read and delete a 100MB file
tests/test.b duplicate of test.2 but seeded with random data
+_
tests/test.d seed with random data and do mkdir -p a/b/c/d/e/f/g/h
+tests/test.e seed with random data and test that directory and file deletions
.TE
.sp
.TS
--- a/extents.c
+++ b/extents.c
@@ -17,7 +17,118 @@
void showextent(int fd, char *pre, Extent *e);
+s64
+belongs(Extent *e, u64 start, u64 len)
+{+ if(e == nil)
+ sysfatal("belongs: e == nil");+ if(start+len == e->start || start == e->start+e->len)
+ return 0;
+ if(start >= e->start && start <= e->start+e->len)
+ panic("belongs: inconsistent"+ " e->start %llud e->len %llud"
+ " start %llud len %llud\n",
+ e->start, e->len, start, len);
+ return start+len-e->start;
+}
+
Extent *
+searchlrus(Extents *es, u64 blkno, u64 len, s64 *closest)
+{+ Extent *e, *eclosest;
+ s64 howclose;
+
+ if(es->lru == nil)
+ panic("searchlrus: should not happen");;+
+ eclosest = e = es->lru;
+ *closest = belongs(e, blkno, len);
+ if(closest == 0)
+ return es->lru;
+ for(e = e->next; e != es->lru; e = e->next){+ howclose = belongs(e, blkno, len);
+ if(abs(howclose) < abs(*closest)){+ eclosest = e;
+ *closest = howclose;
+ }
+ }
+ return eclosest;
+}
+
+void
+removefromlrus(Extents *es, Extent *e)
+{+ Extent *z, *a;
+
+ if(e == nil || es == nil)
+ return;
+
+ /* only entry in the lru linked list */
+ if(e->prev == e->next){+ e->prev = e->next = es->lru = nil;
+ es->nlru = 0;
+ return;
+ }
+
+ /* z e a => z a */
+ z = e->prev;
+ a = e->next;
+
+ z->next = a;
+ a->prev = z;
+ es->nlru--;
+
+ if(es->lru == e)
+ es->lru = a;
+}
+
+void
+intolrus(Extents *es, Extent *e)
+{+ Extent *y, *z;
+
+ if(e == nil || es == nil)
+ return;
+
+ if(e->prev != nil)
+ removefromlrus(es, e);
+
+ if(es->lru == nil){+ es->lru = e->prev = e->next = e;
+ }else if(es->nlru >= Nlru){+ /*
+ y z lru
+ to
+ y e lru
+ then make e the lru
+ */
+ z = es->lru->prev;
+ y = z->prev;
+ z->prev = z->next = nil;
+
+ e->prev = y;
+ y->next = e;
+
+ e->next = es->lru;
+ es->lru->prev = e;
+ }else{+ /*
+ z lru
+ to
+ z e lru
+ then make e the lru
+ */
+ z = es->lru->prev;
+ z->next = e;
+ e->prev = z;
+ e->next = es->lru;
+ es->lru->prev = e;
+ es->nlru++;
+ }
+ es->lru = e;
+}
+
+Extent *
lowest(Extents *es)
{Extent *e;
@@ -51,7 +162,7 @@
c->len = len;
es->n++;
if(chatty9p > 7)
- print(" +%llud .. %llud\n", start, start+len-1);+ print(" +%llud %llud %llud\n", start, start+len-1, len); if(start < e->start){/* e->low e =>
@@ -64,7 +175,7 @@
c->low = e->low;
e->low = c;
c->high = e;
- es->lru = c;
+ intolrus(es, c);
return c;
}
if(start > e->start){@@ -76,7 +187,7 @@
c->high = e->high;
e->high = c;
c->low = e;
- es->lru = c;
+ intolrus(es, c);
return c;
}
print("addextent: should not be here e->start"@@ -114,9 +225,10 @@
g->low = e;
e->high = g;
+ removefromlrus(es, f);
free(f);
es->n--;
- es->lru = e;
+ intolrus(es, e);
return e;
}
return e;
@@ -149,9 +261,10 @@
if(f != nil)
f->low = d;
+ removefromlrus(es, e);
free(e);
es->n--;
- es->lru = d;
+ intolrus(es, d);
return d;
}
return e;
@@ -162,7 +275,7 @@
{if(e == nil)
return e;
- es->lru = e;
+ intolrus(es, e);
if(start+len == e->start){e->start = start;
e->len += len;
@@ -179,21 +292,6 @@
return e;
}
-s64
-belongs(Extent *e, u64 start, u64 len)
-{- if(e == nil)
- sysfatal("belongs: e == nil");- if(start+len == e->start || start == e->start+e->len)
- return 0;
- if(start >= e->start && start <= e->start+e->len)
- panic("belongs: inconsistent"- " e->start %llud e->len %llud"
- " start %llud len %llud\n",
- e->start, e->len, start, len);
- return start+len-e->start;
-}
-
/*
print("between e->prev %llud .. %llud and e %llud .. %llud\n",e->prev->start, e->prev->start+e->prev->n-1,
@@ -212,48 +310,61 @@
e->low = e->high = nil;
e->start = start;
e->len = len;
- es->lru = es->head = e;
+ es->lru = es->head = e->prev = e->next = e;
es->n = 1;
return e;
}
/* using the previously used extent */
- eprev = e = es->lru;
- dir = belongs(es->lru, start, len);
+ eprev = e = searchlrus(es, start, len, &dir);
+ if(e == nil)
+ panic("doadd: e == nil"); if(chatty9p > 7){- print(" belongs(e %llud %llud start %llud .. %llud) %lld\n",- e->start, e->start+e->len-1, start, start+len-1, dir);
+ print(" belongs(e %llud %llud %llud %p %p start %llud %llud %llud) %lld\n",+ e->start, e->start+e->len-1, e->len, e->low, e->high,
+ start, start+len-1, len, dir);
}
if(dir < 0){- while(e->low != nil && (dir = belongs(e, start, len)) < 0){+ while((dir = belongs(e, start, len)) < 0){eprev = e;
e = e->low;
+ if(e == nil)
+ break;
}
- es->lru = eprev;
- /* e->low e es->lru */
+ if(chatty9p > 7){+ print(" belongs(e %llud %llud %llud %p %p start %llud %llud %llud) %lld\n",+ e->start, e->start+e->len-1, e->len, e->low, e->high,
+ start, start+len-1, len, dir);
+ }
+ /* e->low e eprev */
if(dir == 0)
return increment(es, e, start, len);
- if(e->low == nil)
+ if(e == nil)
/* at the lowest extent, add below or above */
- return addextent(es, e, start, len);
+ return addextent(es, eprev, start, len);
- /* dir(e) > 0, hence, e < start < es->lru */
- return addextent(es, es->lru, start, len);
+ /* dir(e) > 0, hence, e < start < eprev */
+ return addextent(es, eprev, start, len);
}else if(dir > 0){- while(e->high != nil && (dir = belongs(e, start, len)) > 0){+ while((dir = belongs(e, start, len)) > 0){eprev = e;
e = e->high;
+ if(e == nil)
+ break;
}
- es->lru = eprev;
- /* es->lru e e->high */
+ if(chatty9p > 7){+ print(" belongs(e %llud %llud %llud start %llud %llud %llud) %lld\n",+ e->start, e->start+e->len-1, e->len, start, start+len-1, len, dir);
+ }
+ /* eprev e e->high */
if(dir == 0)
return increment(es, e, start, len);
- if(e->high == nil)
+ if(e == nil)
/* at the highest extent, add below or above */
- return addextent(es, e, start, len);
+ return addextent(es, eprev, start, len);
- /* dir(e) < 0, hence, es->lru < start < e */
- return addextent(es, es->lru, start, len);
+ /* dir(e) < 0, hence, eprev < start < e */
+ return addextent(es, eprev, start, len);
}
/* dir == 0 */
@@ -265,14 +376,14 @@
{Extent *e;
-/* if(chatty9p > 7){+ if(chatty9p > 7){showextents(2, " before\n", es);
fprint(2, " +%llud %llud\n", start, len);
- }*/
+ }
e = doadd(es, start, len);
es->lru = e;
-/* if(chatty9p > 7)
- showextents(2, " after\n", es);*/
+ if(chatty9p > 7)
+ showextents(2, " after\n", es);
return e;
}
@@ -287,9 +398,10 @@
/* if e is the only entry in es */
if(e->low == nil && e->high == nil){- es->lru = es->head = nil;
+ es->head = nil;
es->n = 0;
start = e->start;
+ removefromlrus(es, e);
free(e);
return start;
}
@@ -298,11 +410,12 @@
/* d e f => d f */
dlow = e->low;
fhigh = e->high;
+ removefromlrus(es, e);
/* d e nil => d nil */
if(fhigh == nil){dlow->high = nil;
- es->lru = dlow;
+ intolrus(es, dlow);
es->n--;
}
@@ -309,7 +422,8 @@
/* nil e f => nil f */
if(dlow == nil){fhigh->low = nil;
- es->lru = es->head = fhigh;
+ es->head = fhigh;
+ intolrus(es, fhigh);
es->n--;
}
@@ -316,7 +430,7 @@
if(dlow != nil && fhigh != nil){dlow->high = fhigh;
fhigh->low = dlow;
- es->lru = fhigh;
+ intolrus(es, fhigh);
es->n--;
}
start = e->start;
@@ -420,8 +534,8 @@
qlock(&es->lck);
used = 0;
for(e = lowest(es); e != nil; e = e->high){- n = snprint(tmp, 128, "%llud .. %llud\n",
- e->start, e->start+e->len-1);
+ n = snprint(tmp, 128, "%llud %llud %llud\n",
+ e->start, e->start+e->len-1, e->len);
if(n == 128)
panic("saveextents(): increase tmp size");used += n;
@@ -442,8 +556,8 @@
qlock(&es->lck);
used = 0;
for(e = lowest(es); e != nil; e = e->high){- n = snprint(tmp, 128, "%llud .. %llud\n",
- e->start, e->start+e->len-1);
+ n = snprint(tmp, 128, "%llud %llud %llud\n",
+ e->start, e->start+e->len-1, e->len);
if(n == 128)
panic("saveextents(): increase tmp size"); if(used+n > nbuf){@@ -467,7 +581,7 @@
loadextents(Extents *es, s8 *buf, u32 nbuf)
{s8 *p, *ep;
- u64 sstart, estart, nblocks;
+ u64 start, end, nblocks;
p = buf;
if(es->lru != nil || es->n != 0){@@ -475,18 +589,28 @@
" TODO make loadextents() be called multiple times\n");
}
while(*p != 0 && p-buf < nbuf){- sstart = strtoull(p, &ep, 10);
+ start = strtoull(p, &ep, 10);
if(p == ep)
panic("could not read");+
p = ep;
- p += 4; /* skip over ' .. ' */
- estart = strtoull(p, &ep, 10);
+ p += 1; /* skip over the space */
+ end = strtoull(p, &ep, 10);
if(p == ep)
panic("could not read");- nblocks = estart - sstart+1;
+
p = ep;
+ p += 1; /* skip over the space */
+ nblocks = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+ if(end-start+1 != nblocks)
+ panic("loadextents does not match up: start %llud end %llud nblocks %llud",+ start, end, nblocks);
+
+ p = ep;
p++; /* to skip over the new line */
- bfree(es, sstart, nblocks);
+ bfree(es, start, nblocks);
}
return es->n;
}
@@ -505,7 +629,7 @@
fprint(fd, "%s", msg);
for(e = lowest(es); e != nil; e = e->high){- fprint(fd, " %llud .. %llud", e->start, e->start+e->len-1);
+ fprint(fd, "%llud %llud %llud", e->start, e->start+e->len-1, e->len);
// showextent(fd, " ", e);
fprint(fd, "\n");
}
--- a/extents.h
+++ b/extents.h
@@ -15,13 +15,21 @@
struct Extent *low, *high; /* sorted by start */
u64 start; /* where this extent starts from */
u64 len; /* how many units in this extent */
+
+ /*
+ circular least recently used linked list
+ limited to Nlru items
+ */
+ struct Extent *prev, *next;
};
struct Extents {- Extent *lru; /* least recently used extent */
- Extent *head; /* find the first block in a jiffy */
+ Extent *head; /* find the first block in a jiffy */
QLock lck;
- u32 n; /* number of extents */
+ u32 n; /* number of extents */
Rendez isempty; /* fully used, nothing available */
+
+ u8 nlru; /* number of items in the lru linked list */
+ Extent *lru; /* least recently used extent in the circular lru linked list */
};
extern int chatty9p;
--- a/free.c
+++ b/free.c
@@ -52,8 +52,8 @@
checkblock(Bdfrees, Tdentry, Qpfrees);
initextents(&frees);
getfrees(Bdfrees);
-// showextents("after getfrees", &frees);- showblocknos(1, &frees);
+ showextents(1, "", &frees);
+ // showblocknos(1, &frees);
close(devfd);
exits(0);
}
--- a/mkfile
+++ b/mkfile
@@ -41,7 +41,7 @@
$O.unused: dat.$O dev.$O extents.$O unused.$O misc.$O
$LD $LDFLAGS -o $target $prereq
-$O.used: blk.$O dat.$O dev.$O misc.$O used.$O
+$O.used: blk.$O dat.$O dev.$O extents.$O misc.$O used.$O
$LD $LDFLAGS -o $target $prereq
$O.free: dat.$O dev.$O extents.$O free.$O misc.$O
--- a/reconcile.c
+++ b/reconcile.c
@@ -107,12 +107,16 @@
missing(u64 nblocks, Stream *u, Stream *f)
{u64 i;
+ u8 header = 0;
- print("missing: "); for(i = 0; i < nblocks; i++){- if(find(u->es, i) == 0 && find(f->es, i) == 0)
+ if(find(u->es, i) == 0 && find(f->es, i) == 0){+ if(header++ == 0)
+ print("missing: "); print(" %llud", i);+ }
}
+ if(header)
print("\n");}
@@ -121,8 +125,8 @@
{Extent *e;
u64 bno;
+ u8 header = 0;
- print("common: "); if(u == nil || u->es == nil){ print("common: no used extents\n");return;
@@ -129,10 +133,14 @@
}
for(e = lowest(u->es); e != nil; e=e->high){ for(bno = e->start; bno<e->start+e->len; bno++){- if(find(f->es, bno) == 1)
+ if(find(f->es, bno) == 1){+ if(header++ == 0)
+ print("common: "); print(" %llud", bno);+ }
}
}
+ if(header)
print("\n");}
@@ -151,7 +159,8 @@
void
collect(Stream * s)
{- u64 bno;
+ s8 *p, *ep;
+ u64 start, end, nblocks;
if(debug)
print("collect %s ", s->name);@@ -158,8 +167,27 @@
s->es = emalloc(sizeof(Extents));
initextents(s->es);
while((s->buf = Brdstr(&s->bp, '\n', 1)) != nil) {- bno = atoll(s->buf);
- add(s->es, bno, 1);
+ p = s->buf;
+ start = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+
+ p = ep;
+ p += 1; /* skip over the space */
+ end = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+
+ p = ep;
+ p += 1; /* skip over the space */
+ nblocks = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+ if(end-start+1 != nblocks)
+ panic("loadextents does not match up: start %llud end %llud nblocks %llud",+ start, end, nblocks);
+
+ add(s->es, start, nblocks);
// show(s);
}
if(debug)
--- a/tests/check.rc
+++ b/tests/check.rc
@@ -25,5 +25,5 @@
echo reconcile $disk $nblocks
disk/reconcile -u <{disk/used $disk} -F <{disk/free $disk} $nblocks-diff <{disk/unused -l <{disk/used $disk} $nblocks}} \- <{disk/free $disk}+diff <{disk/unused <{disk/used $disk} $nblocks} \+ <{disk/free $disk} || echo unused and free do not match up--- a/tests/extents/addabove/output
+++ b/tests/extents/addabove/output
@@ -1,2 +1,2 @@
- 20 .. 22
- 40 .. 43
+20 22 3
+40 43 4
--- a/tests/extents/addabove1/output
+++ b/tests/extents/addabove1/output
@@ -1,2 +1,2 @@
- 180 .. 183
- 250 .. 253
+180 183 4
+250 253 4
--- a/tests/extents/addbelow/output
+++ b/tests/extents/addbelow/output
@@ -1,2 +1,2 @@
- 180 .. 183
- 250 .. 253
+180 183 4
+250 253 4
--- a/tests/extents/addbelow1/output
+++ b/tests/extents/addbelow1/output
@@ -1,3 +1,3 @@
- 100 .. 100
- 180 .. 183
- 250 .. 253
+100 100 1
+180 183 4
+250 253 4
--- /dev/null
+++ b/tests/extents/addbelow2/input
@@ -1,0 +1,24 @@
+0 1
+3 1
+4 1
+9 1
+10 1
+31 1
+11 1
+30 1
+12 1
+29 1
+13 1
+24 1
+14 1
+23 1
+15 1
+22 1
+5 1
+1 1
+16 1
+6 1
+2 1
+7 1
+8 1
+17 1
--- /dev/null
+++ b/tests/extents/addbelow2/output
@@ -1,0 +1,3 @@
+0 17 18
+22 24 3
+29 31 3
--- a/tests/extents/mergeabove/output
+++ b/tests/extents/mergeabove/output
@@ -1,1 +1,1 @@
- 100 .. 112
+100 112 13
--- a/tests/extents/mergenext/output
+++ b/tests/extents/mergenext/output
@@ -1,1 +1,1 @@
- 101 .. 108
+101 108 8
--- a/tests/extents/mergeprevious/output
+++ b/tests/extents/mergeprevious/output
@@ -1,1 +1,1 @@
- 101 .. 108
+101 108 8
--- a/tests/test.0/blocks/17
+++ b/tests/test.0/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666329177416394129
--- a/tests/test.0/blocks/18
+++ b/tests/test.0/blocks/18
@@ -1,3 +1,3 @@
Tdata 15
-18 .. 21
-25 .. 28
+18 21 4
+25 28 4
--- a/tests/test.1/blocks/17
+++ b/tests/test.1/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666331995204020564
--- a/tests/test.1/blocks/21
+++ b/tests/test.1/blocks/21
@@ -1,3 +1,3 @@
Tdata 15
-21 .. 21
-25 .. 28
+21 21 1
+25 28 4
--- a/tests/test.2/blocks/17
+++ b/tests/test.2/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666332448772732576
--- a/tests/test.2/blocks/19
+++ b/tests/test.2/blocks/19
@@ -1,3 +1,3 @@
Tdata 15
-19 .. 25
-29 .. 36
+19 25 7
+29 36 8
--- a/tests/test.3/blocks/17
+++ b/tests/test.3/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 28
+size 34
pdblkno 4
pqpath 5
mtime 1666355307752040277
--- a/tests/test.6/blocks/17
+++ b/tests/test.6/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666333075061395120
--- a/tests/test.6/blocks/21
+++ b/tests/test.6/blocks/21
@@ -1,3 +1,3 @@
Tdata 15
-21 .. 21
-25 .. 28
+21 21 1
+25 28 4
--- a/tests/test.8/blocks/17
+++ b/tests/test.8/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666333569449739119
--- a/tests/test.b/blocks/17
+++ b/tests/test.b/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 19
+size 17
pdblkno 4
pqpath 5
mtime 1666359857958456895
--- a/tests/test.b/blocks/21
+++ b/tests/test.b/blocks/21
@@ -1,3 +1,3 @@
Tdata 15
-21 .. 21
-25 .. 28
+21 21 1
+25 28 4
--- a/tests/test.d/blocks/17
+++ b/tests/test.d/blocks/17
@@ -1,7 +1,7 @@
Tdentry 15
qid.version 0
qid.path 15
-size 10
+size 9
pdblkno 4
pqpath 5
mtime 1666359868040073037
--- a/unused.c
+++ b/unused.c
@@ -130,7 +130,8 @@
void
collect(Stream * s)
{- u64 bno;
+ s8 *p, *ep;
+ u64 start, end, nblocks;
if(debug)
print("collect %s ", s->name);@@ -137,8 +138,27 @@
s->es = emalloc(sizeof(Extents));
initextents(s->es);
while((s->buf = Brdstr(&s->bp, '\n', 1)) != nil) {- bno = atoll(s->buf);
- add(s->es, bno, 1);
+ p = s->buf;
+ start = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+
+ p = ep;
+ p += 1; /* skip over the space */
+ end = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+
+ p = ep;
+ p += 1; /* skip over the space */
+ nblocks = strtoull(p, &ep, 10);
+ if(p == ep)
+ panic("could not read");+ if(end-start+1 != nblocks)
+ panic("loadextents does not match up: start %llud end %llud nblocks %llud",+ start, end, nblocks);
+
+ add(s->es, start, nblocks);
// show(s);
}
if(debug)
--- a/used.c
+++ b/used.c
@@ -10,7 +10,8 @@
Starting from root, walk down each dentry printing out the linked blocks with invalid tags
*/
-int debug = 0;
+Extents useds = {0};+int chatty9p = 0;
char *devfile = nil;
void walkdentry(u64 blkno);
int checkblock(u64 blkno, s16 tag, u64 qpath);
@@ -29,7 +30,8 @@
ARGBEGIN{default: usage();
- case 'D': debug++; break;
+ case 'D': chatty9p= 8
+ ; break;
}ARGEND
if(argc != 1)
@@ -45,12 +47,14 @@
size = devinit(devfile);
if(size == 0)
panic("null size %s", devfile);- if(debug)
+ if(chatty9p)
print("%s %llud bytes %llud blocks\n", devfile, size, size/Rawblocksize);+ initextents(&useds);
checkblock(Bmagicb, Tmagic, Qpmagic);
walkdentry(Broot);
close(devfd);
+ showextents(1, "", &useds);
exits(0);
}
@@ -58,15 +62,16 @@
checkvalid(u64 blkno, Content *t, s16 tagtype, u64 qpath)
{ if(t->type != tagtype || t->path != qpath){- /* if(debug) */
+ /* if(chatty9p) */
fprint(2, "checkblock invalid %llud tag/path expected %s/%llud actual %s/%llud\n",
blkno, tagnames[tagtype], qpath, tagnames[t->type], t->path);
fprint(2, "used: %llud\n", blkno);
return 0;
}
- if(debug)
+ if(chatty9p)
print("blkno %llud tag %s\n", blkno, tagnames[t->type]);- print("%llud\n", blkno);+ // print("%llud\n", blkno);+ add(&useds, blkno, 1);
return 1;
}
@@ -138,16 +143,18 @@
t = (Content*)buf;
d = (Dentry*)buf;
isdir = (d->mode & DMDIR) > 0;
- if(debug)
+ if(chatty9p)
print("walkdentry %llud tag %s name %s d->qid.path %llud\n",blkno, tagnames[t->type], d->name, d->qid.path);
if(t->type != Tdentry || t->path != d->qid.path){- if(debug)
+ if(chatty9p)
print("walkdentry invalid %llud tag/path expected %s/%llud actual %s/%llud\n",blkno, tagnames[Tdentry], d->qid.path, tagnames[t->type], t->path);
fprint(2, "%llud\n", blkno);
- }else
- print("%llud\n", blkno);+ }else{+ // print("%llud\n", blkno);+ add(&useds, blkno, 1);
+ }
/* do not list the data blocks used by /adm/frees
as they are considered to be free blocks */
if(blkno == Bdfrees)