In this tree a file can have at most 268 blocks: 12 whose numbers sit in the
inode itself, and 256 more listed in one indirect block.
At 1024 bytes a block, that is 268 KiB, and write refuses to go further. In this lab you
give the inode one more level: a doubly-indirect block that lists 256 indirect blocks,
each listing 256 data blocks. One direct slot is traded for it, so the on-disk inode keeps
its size, and the limit grows to 11 + 256 + 65,536 = 65,803 blocks, a little over 64 MiB.
The change to bmap is about thirty lines. What makes the lab worth doing is everything those
lines touch. Each new level is a block that must be allocated inside a
transaction, zeroed, recorded in its parent and logged, or a crash (or
just the buffer cache running out of room) loses part of the file.
itrunc must free a three-level tree, in an order that is safe while other
harts allocate blocks. The log’s fixed budget per system call, sized for one
level of indirection, has to be recounted. The disk itself must grow from 2000 to 70,000
blocks for a maximum-size file to fit, which changes the layout that
mkfs computes. And because the meaning of one inode slot changes, every old
fs.img is misread by the new kernel, and even written to wrongly.
The recount finds a real problem: the deeper tree lets one operation log more blocks than
the log promised, and on this kernel a broken promise ends in panic: bget: no buffers.
So the budget is raised too. The reference solution is eight small commits. With it, a
6580-block file (24 times the old limit) is written, read back and freed in about 40
seconds on an otherwise idle computer, and usertests’ writebig writes a full
65,803-block file.
How a file’s block number becomes a disk block number through a tree of block-number tables, and how the arithmetic of bmap (subtract, divide, take the remainder) maps 65,803 file blocks onto 11 direct slots, one indirect block and a two-level tree.
Why the on-disk inode must keep its exact size (64 bytes, 16 per block), what checks that, and why changing what one slot means still changes the on-disk format, so fs.img must be rebuilt.
How a block is allocated inside a transaction: balloc marks the bitmap and zeroes the block, both through log_write, and the parent that records the new number must be logged too. What happens, on a real run and after a power cut, when one log_write is missing.
Why a partially grown file is always consistent after a crash: each chunk of a write is one transaction, and recovery replays it whole or not at all (shown on a real crash).
How to count the blocks one system call can log, and what to do when the count outgrows the budget: how many blocks can one chunk of a write, and one unlink, log now? What happens when a group commit fills the log, given that the buffer cache is exactly as large as the log and every logged block is pinned in it?
What FSSIZE controls (bitmap size, where data starts, how much fits) and what mkfs derives from it.
git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-bigfile 06aad25 # start your own
git diff 06aad25 origin/ext/22-bigfile # only when you want the answer
1. The spec
Behaviour. A file can grow to MAXFILE = 65,803 blocks (67,382,272 bytes). File blocks
0 to 10 are named directly by addrs[0..10] of the inode, blocks 11 to 266 through the
singly-indirect block named by addrs[11], and blocks 267 to 65,802 through the
doubly-indirect block named by addrs[12]: its entry i names an indirect block whose
entry j names file block 267 + 256i + j. A write that would go past MAXFILE
fails. Unlinking a file (or truncating it with O_TRUNC) frees every block of the tree.
Crash safety: every block that a write changes is part of the same transaction as
the bitmap bits and the inode, as before.
The file system must be large enough for usertests’ writebig, which writes exactly
MAXFILE blocks. usertests -q must print ALL TESTS PASSED on 3 harts.
mkfs must keep producing a valid image (it only builds small files).
The test program, bigfiletest (not bigfile: usertests’ partial_write creates and
removes a file of that name, user/usertests.c:2897), and a test-only system call
freeblocks() that counts the clear bits in the free-block bitmap:
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: size: OK
bigfiletest: blocks used 6607 = 6580 data + 27 indirect
bigfiletest: block count: OK
bigfiletest: read back: OK
bigfiletest: unlink: OK
bigfiletest: free blocks 68930 before, 68930 after
bigfiletest: all blocks freed: OK
bigfiletest: ALL OK
write / size: 6580 blocks of 1024 bytes, each one write; stat must report
6,737,920 bytes. Every block starts with its own number and then a pattern that differs
from block to block, so two file blocks that share a disk block are caught.
block count: the number of free blocks must drop by exactly 6580 + 27: one
singly-indirect block, the doubly-indirect block and 25 indirect blocks below it.
read back: every block is read and compared byte by byte.
all blocks freed: after unlink, the free count is back to the value taken just
after the (empty) file was created.
bigfiletest n uses n blocks; with n = 65803 it also checks that one more block cannot
be written. bigfiletest -w n writes a file and keeps it, bigfiletest -r checks a file
left by an earlier boot: the tools for the crash experiments below.
2. Think first
Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.
1Where does the extra block number come from?
An inode on disk is a struct dinode: four shorts, a size, and 13 block numbers
(kernel/fs.h:32). The doubly-indirect block needs a slot of its own. You can make
the array one entry longer, or give up one of the 12 direct slots. Which do you choose,
and what exactly breaks with the other choice? Commit to an answer before the hints.
2 + 2 + 2 + 2 + 4 + 13 × 4 = 64 bytes, and 1024 / 64 = 16 inodes per block with nothing left over. Inode i is found by arithmetic alone, so every inode’s position depends on that size, in the kernel and in mkfs alike.
Hint 3.
Keep 13 entries and lower NDIRECT to 11: slot 11 stays the singly-indirect block, slot 12 becomes the doubly-indirect one. The in-memory struct inode has its own copy of the array and must change the same way.
The reference design
Give up a direct slot. With 14 entries struct dinode would be 68 bytes. 1024 is not a
multiple of 68, so IPB would be 15 with 4 bytes wasted per block, and mkfs refuses to
run at all: its assert((BSIZE % sizeof(struct dinode)) == 0) fails. Even if you padded
the inode to 128 bytes to keep the division exact, IPB would halve, every inode would
move, and the 200 inodes would need 26 blocks instead of 13.
Keeping 13 entries keeps the inode at 64 bytes and 16 per block; only the meaning of
the slots changes:
slot
before
after
addrs[0..10]
direct
direct
addrs[11]
direct (file block 11)
singly-indirect block
addrs[12]
singly-indirect block
doubly-indirect block
The cost is small: a file of exactly 12 blocks now needs the indirect block for its
last one. The in-memory copy, struct inode in kernel/file.h, must get the same
13-entry array: ilock and iupdate copy sizeof(ip->addrs) bytes between the two
with memmove.
One thing does break: the format. On an image made by the old mkfs, addrs[11] holds a
data block, which the new kernel reads as a table of block numbers. Clinic 6 shows what a
new kernel does with an old fs.img.
Check yourself
1warm-upType a number
How many bytes is struct dinode in this tree (four shorts, a uint size and 13
uint block numbers)? The kernel and mkfs both depend on it.
A learner lowers NDIRECT to 11 but leaves uint addrs[NDIRECT + 1] in both structs,
so the array has 12 entries. They run make qemu. What happens first?
2How far can a file grow, and where does block n live?
With 11 direct slots, one singly-indirect block and one doubly-indirect block, how many
blocks can a file have? Given a file block number bn, how do you find the entry of the
doubly-indirect block, and the entry of the indirect block below it, that hold its disk
block number? Which file block is the first to need the doubly-indirect block?
Hint 1.
NINDIRECT (kernel/fs.h:27) is how many block numbers fit in one block. Look at how bmap turns bn into an index in the singly-indirect block (kernel/fs.c:435).
Hint 2.
Each level multiplies the reach by 256. An index into a table must be relative to the first file block that table covers, so the ranges before it must be subtracted first.
Hint 3.
Subtract NDIRECT, then NINDIRECT; what is left is a number from 0 to 65,535. Its quotient by 256 picks the indirect block, its remainder the entry in it.
The reference design
11 + 256 + 256 × 256 = 65,803 blocks, 67,382,272 bytes. writei checks
off + n > MAXFILE * BSIZE: off + n is 32-bit (its overflow is caught by the test
off + n < off just before), and MAXFILE * BSIZE is a 64-bit size_t because
NINDIRECT is computed with sizeof. Either way the largest offset, 67,382,272, is far
below 4 GiB, and so is the uint size in the inode.
The ranges:
file block
found through
0 to 10
addrs[bn]
11 to 266
singly-indirect block, entry bn - 11
267 to 65,802
doubly-indirect block, entry (bn - 267) / 256, then that indirect block’s entry (bn - 267) % 256
So file block 267 (byte offset 273,408) is the first to need the doubly-indirect block,
and block 523 the first to need a second indirect block under it. The last block of the
6580-block test file, 6579, is entry 6312 / 256 = 24 of the doubly-indirect block and
entry 6312 % 256 = 168 of indirect block 24.
The same subtract-then-compare shape as the existing code keeps each range check honest:
every comparison is bn < size of this range, with bn already relative to the range’s
start. Clinic 2 shows what one <= does instead.
Check yourself
1warm-upType a number
With NDIRECT = 11, one singly-indirect and one doubly-indirect block of 256 entries
each, what is MAXFILE, in blocks?
decimal, 0x hex or 0b binary
2solidType a number
File block 6579 is the last block of bigfiletest’s file. Which entry (counting
from 0) of the doubly-indirect block names the indirect block that maps it?
decimal, 0x hex or 0b binary
3solidMatch the pairs
Match each file block with where the new bmap finds its disk block number.
3Allocating a path of blocks inside a transaction
Writing file block 267 of a growing file needs three new disk blocks: the
doubly-indirect block, indirect block 0 under it, and the data block. Each new block
has a bit in the free bitmap and contents of its own, and each parent must record its
child’s number. Which blocks must be logged with log_write? Does the order of
those calls matter? And if the machine loses power halfway through a large write,
what can the file look like after the reboot?
For each level: read the number from the parent; if it is 0, balloc a block (bitmap bit and zeroed contents, both logged), store the number in the parent and log_write the parent. The inode’s own slot is saved by iupdate at the end of writei. A write that filewrite splits into chunks is several transactions.
The reference design
Every block whose contents change must be logged: the bitmap block (by balloc),
each new block (zeroed and logged by bzero), each parent whose entry changed (the
doubly-indirect block when a new indirect block is added, the indirect block when a new
data block is added), the data block itself (by writei), and the inode’s block (by
iupdate, which also saves addrs[12]). Then the whole path from the inode to the
data appears after a crash, or none of it does.
The order of the log_write calls inside one transaction does not matter for crash
safety: the commit writes all logged blocks to the log, then the header, then installs
them, and it copies each block’s current cached contents at commit time
(Tour 31: The log: begin_op, commit and group commit). What matters is completeness, plus one rule about content: a new
indirect block must be zeroed, because 0 is how bmap recognizes “not allocated
yet”. A table of leftover numbers from a freed block would send later writes into
blocks owned by other files.
A large write is not one transaction: filewrite splits it into chunks of at most
3 blocks, each with its own begin_op / end_op (kernel/file.c:160-kernel/file.c:165),
and bigfiletest writes one block per write anyway. So after a crash the file ends at
some transaction boundary, and everything up to there is intact. We tested it: QEMU was
killed 13 seconds into bigfiletest -w 6580. On the next boot the log held a committed
transaction and recovery replayed it (recovering tail 0 dst 55 … dst 43), and
bigfiletest -r found a 555-block file with every block correct and exactly
555 + 4 blocks fewer free than on a fresh image. Five more kills at other moments gave
the same kind of result (reveal step 7).
Check yourself
1solidTrue or false, and why
True or false: inside one transaction, bmap must call log_write on a newly
allocated indirect block before it stores that block’s number in the parent;
otherwise a crash could leave the parent pointing at a block of garbage.
Why?
2solidChoose one
The power fails in the middle of bigfiletest -w 6580 (one block per write). After
the reboot, what can bigtest.dat look like on the reference branch?
4How many blocks can one chunk of a write log now?
Every file-system system call promises to log at most MAXOPBLOCKS = 10 blocks, and
begin_op admits operations on that promise (kernel/log.c:138). filewrite keeps
its side of it by writing at most ((MAXOPBLOCKS - 1 - 1 - 2) / 2) * BSIZE = 3 blocks
per transaction (kernel/file.c:149-kernel/file.c:153); the comment says what the
formula budgets for. That budget was made for one level of indirection. Recount it for
the new tree: what is the largest number of distinct blocks one 3-block chunk can log
now? Is the promise still kept?
Hint 1.
Read the comment above the formula, and how log_write treats a block that is already in the transaction (kernel/log.c:234-kernel/log.c:242). A chunk that starts in the middle of a block touches 4 blocks.
Hint 2.
A new data block in the doubly-indirect range can need up to two extra allocations: the doubly-indirect block (once per file) and an indirect block (once per 256 data blocks). Each allocation sets a bit in some bitmap block, and balloc takes the lowest free block, which on a fragmented disk can be in a different bitmap block every time.
Hint 3.
Take the chunk that crosses from file block 266 into 267 and count by kind: the inode’s block; 4 data blocks; the singly-indirect, doubly-indirect and indirect blocks; and one bitmap block per allocation in the worst case.
The reference design
The old formula budgets 1 inode block + 1 indirect block + 2 blocks of slop + 2 per
data block (the block and its bitmap block): 3 data blocks. Count the worst chunk now, an
unaligned 3072-byte chunk covering file blocks 264 (already there) to 267:
bitmap blocks: 5 allocations (265, 266, the two tables, 267)
1 to 5
On a fresh disk the 5 allocations are consecutive blocks, so 1 or 2 bitmap blocks: 9 or
10 in all, just inside the promise. But balloc takes the lowest free block each time.
On a disk with one free block in each of the first five bitmap blocks, the five
allocations land in five different bitmap blocks: 13. We built that disk (a scratch
program, frag13, that leaves one hole in each of bitmap blocks 0 to 4) and printed
every large commit in a copy of the kernel. One write logged:
Data 264 and 265 (1457, 1458), the singly-indirect block (1203), data 266 (9684), the
doubly-indirect block (17910), indirect block 0 (26136), data 267 (34362), five bitmap
blocks (55 to 59) and the inode block (43). (This was measured on the finished branch,
where the bitmap starts at block 55; see think 6 for why it moved.)
So the promise is broken: a write can log 13 blocks while begin_op reserved 10. The
general count, for a chunk of m data blocks: 1 inode + up to 3 tables + the bitmap
blocks of 2 new tables + 1 existing data block at an unaligned start + 2 per new data
block = 2m + 7. Think 6 counts the other operation the new tree enlarges, and then
decides what to do about both.
Check yourself
1solidType a number
On a deliberately fragmented disk (one free block in each of the first five bitmap
blocks), how many distinct blocks did one 3-block chunk of a write log, crossing
from the singly- into the doubly-indirect range?
decimal, 0x hex or 0b binary
2deepChoose all that apply
Which of these blocks are in the transaction of the chunk that writes file blocks 264
to 267 (the doubly-indirect block does not exist yet)?
5How big must the disk be, and what follows from its size?
usertests’ writebig writes exactly MAXFILE blocks to one file
(user/usertests.c:583), and it is one of the quick tests. The disk is FSSIZE =
2000 blocks. What must change, what in the disk layout follows from FSSIZE, and does
the kernel need to know the new size?
One bitmap block has a bit for each of BPB = 8192 blocks. A 65,803-block file also needs its indirect blocks, and mkfs has already used about a thousand blocks for the programs.
Hint 3.
65,803 + 258 indirect blocks + what mkfs uses, rounded up generously. Then work out nbitmap and the first data block for that size; the kernel needs no change at all.
The reference design
A maximum-size file needs 65,803 data blocks + 1 singly-indirect + 1 doubly-indirect +
256 indirect blocks = 66,061 blocks. The reference sets FSSIZE to 70,000. What mkfs
derives from it:
FSSIZE 2000
FSSIZE 70,000
the finished branch (log grown, think 6)
bitmap blocks (FSSIZE / BPB + 1)
1
9
9
metadata (boot, super, log, 13 inode, bitmap)
47 (31-block log)
55 (31-block log)
64 (40-block log)
first data block
47
55
64
free after mkfs, with bigfiletest on the disk
947
68,939
68,930
fs.img
2 MB
70 MB
70 MB
On the finished branch 68,930 free blocks leave 2869 to spare when writebig runs. The kernel reads the size
from the superblock (kernel/fs.c:44), and balloc loops over sb.size in steps of
BPB, reading one bitmap block per step: nine instead of one, with no code change.
Two costs come with it. mkfs writes all 70,000 blocks of zeros to create the image, and
balloc always scans from bitmap block 0: late in writebig, every allocation first
walks about 65,000 set bits in eight full bitmap blocks (cached, but still a loop).
Without the change, writebig stops at balloc: out of blocks after 933 blocks, which
with its 5 indirect blocks is exactly the 938 blocks free on the finished branch’s
2000-block image (clinic 5). And since fs.h and
param.h changed, make rebuilds mkfs and fs.img (Makefile:123); an old image
kept around by hand is a different format (clinic 6).
Check yourself
1warm-upType a number
With FSSIZE = 70,000, how many bitmap blocks does mkfs reserve
(nbitmap = FSSIZE / BPB + 1, with BPB = 8192)?
30intnlog=LOGBLOCKS+1;// Header followed by LOGBLOCKS data blocks.
31intnmeta;// Number of meta blocks (boot, sb, nlog, inode, bitmap)
decimal, 0x hex or 0b binary
2solidChoose one
You implement the doubly-indirect block correctly but leave FSSIZE at 2000. What
does usertests -q do?
6Freeing a tree, and re-budgeting the log
When the last link to a file is removed and nobody has it open, iput calls
itrunc (kernel/fs.c:365). For the doubly-indirect tree, what must be freed, and
in what order? Then count: unlinking writebig’s 65,803-block file, how many distinct
blocks does that one system call log? With this count and think 4’s, is
MAXOPBLOCKS = 10 still a promise the kernel keeps, what happens if it is not, and what
should change?
Hint 1.
Read bfree: what does it change, and what does it leave alone? Then think about another hart running balloc in a concurrent transaction.
Hint 2.
Once a block’s bit is clear, another process may allocate it and zero it at any moment. And every bfree writes only a bitmap block: log absorption keeps each one once, however many blocks are freed in it.
Hint 3.
For each nonzero entry of the doubly-indirect block: read that indirect block, free every nonzero entry, release it, then free it. Last, free the doubly-indirect block itself and clear addrs[12]. For the count: which bitmap blocks does a 66,061-block file starting near block 1070 span? For the consequences: compare LOGBLOCKS and NBUF in kernel/param.h, and see what log_write does to every buffer it logs (kernel/log.c:240).
The reference design
Free every block the tree contains, reading each table before freeing it: data blocks
listed in an indirect block, then the indirect block, and, after all 256 entries, the
doubly-indirect block. bfree does not change the freed block, but once its bit is
clear another hart’s balloc may hand it out and bzero it in another transaction. A
table read after its own bfree could come back as zeros, and its data blocks would
leak. Order within the transaction does not matter for crashes (the whole unlink
commits at once); it matters for this concurrency.
The count. Every bfree logs a bitmap block, and log absorption keeps each one once,
so freeing any number of blocks costs one logged block per bitmap block they span. A
maximum-size file occupies 66,061 consecutive blocks on a fresh disk, from about block
1070 to 67,130: bitmap blocks 0 to 8, all nine. Add the directory block whose entry is
cleared, the directory’s inode block and the file’s inode block: unlink logs
nbitmap + 3 = 12 blocks. A copy of the kernel that prints large commits recorded
exactly that during usertests -q (writebig runs alone, so the commit is that one
operation). In the original tree a file had at most 269 blocks (268 data + 1 indirect)
on a disk with a single bitmap block, so this never happened.
Why a broken promise is fatal.begin_op admits a new operation only while
lh.n + (outstanding + 1) * MAXOPBLOCKS <= LOGBLOCKS (kernel/log.c:138): the log
is never promised more than 30 blocks. And NBUF, the size of the buffer cache, is
also 30 (3 * MAXOPBLOCKS, kernel/param.h). That matters because log_write
pins every logged buffer in the cache until the commit has installed it
(kernel/log.c:240): if one group commit logs 30 distinct blocks, all 30 buffers are
pinned, and commit, which must bread a log block to copy each one into, finds
no buffer to reuse. bget panics bget: no buffers (kernel/bio.c:87).
With operations that overrun, 30 is reachable. A race test, lograce, builds one
group commit of four operations: a write that crosses
into the doubly-indirect range (8 blocks after absorption), two small overwrites (5
each), and the unlink of a 9-block file whose blocks lie in 9 different bitmap blocks
(12). begin_op admits the unlink because 10 + 2 × 10 ≤ 30; together they log
10 + 12 + 8 = 30. Clinic 7 shows the panic, on the branch with MAXOPBLOCKS left at 10.
Re-budget. The reference raises MAXOPBLOCKS to 13, which covers both counts: a
write chunk is at most 2m + 7 = 13 for m = 3, so filewrite's formula is
rewritten term by term as (MAXOPBLOCKS - 1 - 3 - 2 - 1) / 2 and still gives 3 blocks;
and an unlink is at most nbitmap + 3 = 12, which mkfs now checks
(assert(nbitmap + 3 <= MAXOPBLOCKS)), because a bigger disk would need a bigger
budget. LOGBLOCKS and NBUF follow as 39. The cost: a 40-block log (9 more blocks of
metadata, so the inodes, bitmap and data all start 9 blocks later) and 9 more buffers
in the cache. With it, lograce produces the same kind of group commit and survives.
The alternative fix, truncating a large file over several transactions, scales to any
disk size (and ireclaim would make a crash halfway through safe), but every caller
of iput runs inside someone else’s transaction; it is a stretch goal.
Check yourself
1solidPut in order
Put the reference itrunc's work on the doubly-indirect tree in order, for a file
with two indirect blocks under it.
free the doubly-indirect block and clear addrs[12]
read indirect block 1, free its data blocks, then free it
write the inode back with size 0 (iupdate)
read indirect block 0 and free every data block it lists
read the doubly-indirect block
free indirect block 0
2deepType a number
usertests’s writebig writes a 65,803-block file on a fresh 70,000-block disk and
unlinks it. How many distinct blocks did that unlink’s transaction log, as measured?
decimal, 0x hex or 0b binary
7How do you prove the blocks came back?
Reading the file back proves that the data is there. It cannot prove that unlinking
freed every block, including the 27 indirect ones. What would, from a user program, and
what could make such a check lie?
Creating a file can allocate a block that is not the file’s: the directory may grow. And on 3 harts, another process may allocate between two counts.
Hint 3.
A small system call that counts the clear bits through the buffer cache; take the first count after open(O_CREATE), require that the write used exactly n data + the expected indirect blocks, and that the count after unlink equals the first.
The reference design
Count the free blocks. The reference adds a test-only system call, freeblocks(), that
reads each bitmap block with bread and counts clear bits. It reads through the buffer
cache, so it sees changes of transactions that have not committed yet; that is what a
test running alone wants.
bigfiletest then checks two equalities. After writing n blocks, the free count must
have dropped by exactly n + the number of indirect blocks: 0 up to 11 blocks, 1 up to
267, and 2 + ⌈(n − 267) / 256⌉ above that (27 for 6580, 258 for 65,803). This catches a
kernel that allocates too many or too few tables, or maps two file blocks to one disk
block (clinic 2 fails here). And after unlink, the count must equal the first one
(clinic 3 fails here).
Where it could lie: the first count is taken after creating the empty file, because
create may add a block to the directory, which unlink does not give back. And
nothing locks the bitmap between two counts, so another process writing at the same
time would change them: the comment on the kernel function says the count can be stale,
and the test assumes it runs alone.
Check yourself
1warm-upType a number
How many indirect blocks (singly-indirect, doubly-indirect and the indirect blocks
under it) does a 6580-block file use?
decimal, 0x hex or 0b binary
2deepType a number
A kernel whose itrunc forgets the doubly-indirect tree runs bigfiletest
(6580 blocks). By how many blocks is the free count after unlink lower than
before the write?
decimal, 0x hex or 0b binary
3. Build it
Start.
git checkout -b my-bigfile 06aad25
Write your test program first (user/bigfiletest.c, added to UPROGS in the Makefile).
Do not call it bigfile: usertests’ partial_write overwrites and deletes a file of that
name, and your program would vanish after the first usertests run. To count free blocks
you need a small system call (the usual five places: syscall.h, syscall.c,
sysfile.c, user.h, usys.pl) and a function in fs.c that counts clear bits in the
bitmap. On the unmodified kernel, bigfiletest -w 300 must report wrote 268 blocks:
that is the old limit, and your test seeing it.
Milestones, in an order that keeps the system bootable after each one.
The inode layout.NDIRECT 11, addrs[NDIRECT + 2] in struct dinodeandstruct inode. MAXFILE stays NDIRECT + NINDIRECT (now 267). make rebuilds mkfs
and fs.img. Test: boot, ls, usertests -q (writebig now writes 267 blocks, all
through the old code paths).
bmap. The third range. Nothing reaches it yet. Test: it compiles; reread the
index arithmetic against the table in think 2.
itrunc. The tree, children first. Test: still nothing reaches it; usertests -q.
FSSIZE. 70,000. Look at mkfs’s output line nmeta 55 (boot, super, log blocks 31, inode blocks 13, bitmap blocks 9) blocks 69945 total 70000. Test: boot, usertests -q.
Flip the switch: MAXFILE. Add the doubly-indirect range, and make mkfs’s own
assertion say what it supports (NDIRECT + NINDIRECT). Test: bigfiletest 300 first
(one indirect block under the doubly-indirect block, quick), then bigfiletest, then
usertests -q, then bigfiletest again.
Recount, then re-budget the log. Work through think 4 and think 6, then raise
MAXOPBLOCKS to cover the worst cases, rewrite filewrite's formula term by term,
and give mkfs an assertion that ties the bitmap size to the budget. Test: usertests -q; if you can, a race like the one in clinic 7.
What to expect. On an otherwise idle computer bigfiletest took 37 seconds and
usertests -q 7 minutes (421 s; the original kernel takes 43 s). Measured while the
computer was busy with other work, they took 114 s and 57 minutes; timings on QEMU depend
on what else the computer is doing, so yours will differ. Most of it is writebig: 65,803 one-block
writes, each its own transaction. While you iterate, use bigfiletest 300 and
usertests writebig.
Debugging advice. Start QEMU halted with make qemu-gdb (it picks its own gdb port
and writes it into .gdbinit), and set breakpoints before the first continue.
The interesting moments are rare, so break on lines, not functions: tbreak fs.c:<line of the doubly-indirect balloc> fires once per file. bmap and balloc are not inlined in
this build, so breakpoints inside them work. With -O, gdb can show wrong values for
bn (both bn and bn@entry; we saw bn=4294967029 where it was 0): print
ip->addrs and the table contents, or work bn out from writei’s off.
p ip->addrs shows the whole inode slot array; p *(uint (*)[256])bp->data shows a
table block in the cache.
p 'log.c'::log.lh shows how many blocks the current transaction has logged and which.
A panic log_write outside of trans from readi means bmap tried to allocate
while reading: some table on disk lacks an entry your write put in the cache (clinic 1).
balloc: out of blocks from writebig means the disk is too small or blocks leaked:
compare freeblocks() before and after.
After any change to fs.h or param.h, check that make rebuilt fs.img. A kernel run
on an image of the other format fails in ways that look like anything but a format
problem (clinics 4 and 6).
4. Debugging clinic
Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.
1The doubly-indirect block is changed but not logged
In bmap, the new indirect block’s number is stored in the doubly-indirect block, but
that buffer is never passed to log_write:
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: size: OK
bigfiletest: blocks used 6607 = 6580 data + 27 indirect
bigfiletest: block count: OK
panic: log_write outside of trans
# a fresh image: write the file, then cut the power (no sync, QEMU killed):
$ bigfiletest -w 6580
bigfiletest: wrote 6580 blocks
$ echo off
off
# next boot, same fs.img:
$ bigfiletest -r
panic: log_write outside of trans
# that image booted again, with gdb and a breakpoint on panic; it printed
# the hart and noff, then bt:
hart 1 noff 1
#0 panic (s=s@entry=0x80007548 "log_write outside of trans") at kernel/printk.c:139
#1 0x00000000800040c4 in log_write (b=b@entry=0x80016508 <bcache+3360>) at kernel/log.c:232
#2 0x0000000080002e38 in balloc (dev=1) at kernel/fs.c:80
#3 0x000000008000302c in bmap (ip=ip@entry=0x80020708 <itable+296>, warning: left shift count is negative
warning: right shift count is negative
bn=256, bn@entry=0) at kernel/fs.c:493
#4 0x0000000080003870 in readi (ip=0x80020708 <itable+296>, user_dst=user_dst@entry=1, dst=dst@entry=15136, off=535552, n=n@entry=1024) at kernel/fs.c:599
#5 0x00000000800044ac in fileread (f=0x80022238 <ftable+64>, addr=15136, n=1024) at kernel/file.c:122
[...]
# p bn, p ip->inum, p ip->size, p ip->addrs[12], p 'log.c'::log.outstanding in frame 3:
$1 = 256
$2 = 25
$3 = 6737920
$4 = 1338
$5 = 0
Writing worked and the block count was right: every new indirect block was allocated,
zeroed, logged and filled. What was lost is the doubly-indirect block’s record of
them. That change lived only in the buffer cache.
Why entry 0 survived: the first indirect block is allocated in the same transaction as
the doubly-indirect block itself, which bzero had just logged. commit copies each
logged block’s cached contents at commit time, so entry 0 rode along. Entries 1 to 24
were set in later transactions in which the doubly-indirect block (number 1338) was not
logged. During the write it stayed in the cache, because every block’s bmap used it
and the cache evicts the least recently used buffer. Reading the file from the start
does not touch it for 267 blocks, long enough for the 39-buffer cache to evict it
(reasoned; we did not trace the first run). When bmap needed it again it reread
block 1338 from disk, found an entry 0 and did what it does with a missing block:
allocate one. The gdb run shows where: file block 523 (byte 535,552, bn = 256 in the
doubly-indirect range, entry 1). readi runs outside any transaction
(log.outstanding = 0), so the first log_write, in balloc, panics
(kernel/log.c:231).
After the power cut it is the same story with nothing cached: the disk never had entries
1 to 24. sync would not have helped. bigfiletest runs alone, so each of its
end_ops is the last outstanding one and commits before returning (kernel/log.c:163):
sync has nothing to flush, and a block that was never logged is in no transaction at
all. Indirect blocks 1 to 24 and the 6057 data blocks under them are
marked in use in the bitmap and reachable from nowhere: 6081 blocks that no itrunc
will ever free.
Without the panic (a kernel whose readi did not allocate) the read would have
returned zeros or another file’s data. The rule: every block you change, you log, in the
same transaction.
2Off by one at the end of the singly-indirect range
bn -= NDIRECT;
- if (bn < NINDIRECT) {
+ if (bn <= NINDIRECT) {
// Load indirect block, allocating if necessary.
File block 267 (bn = 256 after the subtraction) now goes to the singly-indirect
branch, which reads and writes a[256]: four bytes past the end of the block’s
1024-byte data array.
What happened when we ran it
$ bigfiletest 300
bigfiletest: 300 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: size: OK
bigfiletest: blocks used 302 = 300 data + 3 indirect
bigfiletest: block count: FAIL
bigfiletest: SOME TESTS FAILED
$ echo off
off
# QEMU killed, then booted again on the same fs.img:
xv6 kernel is booting
hart 1 starting
hart 2 starting
panic: invalid file system
# a fresh image, gdb breaking at `if ((addr = a[bn]) == 0)` when bn == 256;
# printed: bp->blockno, bp - bcache.buf, sizeof(struct buf), &a[bn],
# &bcache.buf[that + 1], &bcache.head, a[bn], bcache.buf[that + 1].valid,
# bcache.buf[that + 1].blockno
# first `bigfiletest 300` (writing file block 267):
$1 = 1081
$2 = 26
$3 = 1112
$4 = (uint *) 0x8001cd48 <bcache+30048>
$5 = (struct buf *) 0x8001cd48 <bcache+30048>
$6 = (struct buf *) 0x80020168 <bcache+43392>
$7 = 1
$8 = 1
$9 = 1330
# second `bigfiletest 300` (writing file block 267):
$10 = 1081
$11 = 16
$12 = 1112
$13 = (uint *) 0x8001a1d8 <bcache+18928>
$14 = (struct buf *) 0x8001a1d8 <bcache+18928>
$15 = (struct buf *) 0x80020168 <bcache+43392>
$16 = 1
$17 = 1
$18 = 1334
# the three runs' output:
bigfiletest: blocks used 302 = 300 data + 3 indirect
bigfiletest: block count: FAIL
[...]
bigfiletest: blocks used 302 = 300 data + 3 indirect
bigfiletest: block count: FAIL
[...]
bigfiletest: blocks used 6606 = 6580 data + 27 indirect
bigfiletest: block count: FAIL
a[256] is not in the indirect block. The buffer’s data array is the last field of
struct buf (1112 bytes), and the cache’s buffers sit next to each other in
bcache.buf[], so the four bytes after data are the valid field of the next
buffer (or of bcache.head after the last one). gdb shows exactly that: &a[256]
equals &bcache.buf[27] when the singly-indirect block (1081) was in slot 26, and
&bcache.buf[17] when it was in slot 16. What the bug does depends on what that
neighbouring field holds:
Next buffer valid (a[256] reads 1): bmap believes file block 267 is already
allocated, at disk block 1, the superblock. No block is
allocated (302 instead of 303), and the file’s data for block 267 is logged and
installed over the superblock. The running kernel does not notice, since it read the
superblock at boot; the next boot finds the magic number gone: panic: invalid file system.
Next buffer not valid (a[256] reads 0): a block is allocated and its number
written into the neighbour’s valid field. The count is then right, but itrunc
frees only a[0..255], so that block leaks. All three traced runs on the finished
branch found a valid neighbour; with a 30-buffer cache (before commit 6 raises
NBUF) the indirect block once sat in the last slot, next to bcache.head, whose valid is 0,
and bigfiletest 300 then passed its count and reported one block lost after
unlink.
All three runs failed the count, 302 for 300 and 6606 for 6580. A related slip, forgetting bn -= NINDIRECT before the doubly-indirect
range, passes bigfiletest completely (every block shifts by one table, consistently)
and dies only in usertests: test writebig: panic: bmap: out of range, when the
shifted index runs off the end 256 blocks early. Boundary blocks 266, 267 and 523, and a
run up to MAXFILE, are the tests that matter.
3itrunc does not free the doubly-indirect tree
itrunc is left as it was: it frees the direct blocks and the singly-indirect tree,
and never looks at addrs[NDIRECT + 1]:
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: size: OK
bigfiletest: blocks used 6607 = 6580 data + 27 indirect
bigfiletest: block count: OK
bigfiletest: read back: OK
bigfiletest: unlink: OK
bigfiletest: free blocks 68930 before, 62591 after
bigfiletest: all blocks freed: FAIL
bigfiletest: SOME TESTS FAILED
$ usertests -q
usertests starting
test copyin: OK
[...]
test writebig: balloc: out of blocks
writebig: error: write big file failed i=62346
FAILED
SOME TESTS FAILED
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
balloc: out of blocks
bigfiletest: write: FAIL
bigfiletest: SOME TESTS FAILED
Everything reachable only through addrs[12] stays marked in use: 6313 data blocks, 25
indirect blocks and the doubly-indirect block, 6339 blocks, exactly 68930 − 62591.
Nothing else notices. The inode is freed and reused (its slot array is cleared by
ialloc), so the blocks are reachable from nowhere, and no tool in xv6 rebuilds the
bitmap from the inodes; the leak survives every reboot.
It shows up as lost capacity. writebig then needs 65,803 + 258 blocks but only 62,591
are free: it stops at block 62,346, and 62,346 data + 245 indirect blocks is exactly
62,591. Its failed test leaves the partial file behind, the disk is full, and the next
bigfiletest cannot even start writing. On a 70,000-block disk one leaked large file
is enough to make usertests fail; that is how a learner usually finds this bug, long
after making it. The free-block count in the test finds it at once.
4NDIRECT lowered, but the arrays not lengthened
NDIRECT becomes 11, but both arrays keep their old declaration, which now means 12
entries:
#define NDIRECT 11 // addrs[NDIRECT] is singly, addrs[NDIRECT+1] doubly indirect
...
uint addrs[NDIRECT + 1]; // in struct dinode, and the same in struct inode
bmap and itrunc are as in the reference, so they use addrs[NDIRECT + 1], one
past the end of the array.
What happened when we ran it
# make fs.img (mkfs is built with the host's compiler; macOS's assert message):
mkfs/mkfs fs.img README user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie user/_logstress user/_forphan user/_dorphan user/_sync user/_bigfiletest
Assertion failed: ((BSIZE % sizeof(struct dinode)) == 0), function main, file mkfs.c, line 88.
make: *** [fs.img] Abort trap: 6
# the kernel itself compiled without a warning; booted on an image made by the
# reference mkfs (64-byte inodes):
xv6 kernel is booting
hart 1 starting
hart 2 starting
ireclaim: orphaned inode 4
panic: freeing free block
With 12 entries, struct dinode is 2 × 4 + 4 + 12 × 4 = 60 bytes, and 1024 is not a
multiple of 60: mkfs’s first check stops the build (the message format is macOS’s
assert; Linux prints the same condition differently). The C compiler is no help:
ip->addrs[NDIRECT + 1] on a 12-entry array compiles silently, even with -Wall -Werror.
Suppose an image is around anyway, made with 64-byte inodes. The buggy kernel computes
IPB = 1024 / 60 = 17 and looks for inode i at offset (i % 17) * 60. At boot,
ireclaim scans all inodes for “allocated but no links”. Decoding the image with the
buggy layout, inode 4 lands at byte 240 of the first inode block, which is the tail of
the real inode 3 (its addrs[9] to addrs[12]) and the start of inode 4. The kernel
reads type = 77 (the low half of block number 77), nlink = 0: an orphan. Reclaiming
it, itrunc frees its “blocks”: 2 (the log’s header block, whose bit is set, so it is
cleared without complaint), then 65,536, a block that is free: panic: freeing free block.
A different sizeof(struct dinode) in two programs that share a disk is a format
mismatch, and its symptoms point everywhere except at the cause. Keep the array at 13.
5FSSIZE left at 2000
Everything as in the reference, except kernel/param.h:
-#define FSSIZE 70000 // size of file system in blocks
+#define FSSIZE 2000 // size of file system in blocks
What happened when we ran it
$ usertests -q
usertests starting
test copyin: OK
[...]
test writetest: OK
test writebig: balloc: out of blocks
writebig: error: write big file failed i=933
FAILED
SOME TESTS FAILED
# a fresh image:
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
balloc: out of blocks
bigfiletest: write: FAIL
bigfiletest: SOME TESTS FAILED
The doubly-indirect code works; the disk is too small. mkfs made 2000 blocks, used 1062
of them (56 of metadata, the rest for the programs), and left 938 free. writebig
wrote 933 blocks, which with their 5 indirect blocks (one singly-indirect, the
doubly-indirect block and 3 under it) is exactly 938, and the 934th write found nothing:
balloc printed its message and returned 0, writei stopped, write returned
less than asked.
MAXFILE and FSSIZE are independent: the first is how many blocks an inode can name,
the second how many the disk has. A test that writes MAXFILE blocks needs both.
6Running the new kernel on an old fs.img
The reference kernel, booted on an fs.img built by the original mkfs (NDIRECT 12,
2000 blocks), for example a copy kept from before the lab.
What happened when we ran it
xv6 kernel is booting
hart 1 starting
hart 2 starting
init: starting sh
$ ls
exec ls
failed
$ echo hi
exec echo hi
failed
It boots, which is the dangerous part. The superblock describes a valid 2000-block file
system and the inodes are where the kernel expects them (the inode size did not change).
Only the meaning of addrs[11] and addrs[12] changed: in the old image addrs[11]
is file block 11 of data, and the new kernel reads that data block as a table of block
numbers.
exec reads only the parts of a program file that are loaded, and for init (text at
file offset 0x1000, 2.5 KiB, data at 0x2000) those are all in blocks 0 to 10. So
init runs. sh has its 16 bytes of initialized data, whitespace and symbols, at
file offset 0x3000: file block 12, which the new kernel finds as entry 1 of the
“indirect block” addrs[11]. In the old image that is the second word of one of sh’s
own data blocks, and it is 0 (we decoded the image). So bmap allocates a fresh zero
block, inside exec’s transaction, and records its number at file offset 0x2C04 of
sh: ELF padding between the text (which ends at 0x23d9) and the data at 0x3000,
which the old kernel never loads (we booted the original kernel on this image
afterwards: ls and echo hi worked). What the old format really loses
is that block: marked in use, reachable from nothing. sh runs with whitespace = “”:
it no longer treats the newline as whitespace, so it tries to run a program called
"ls\n", which does not exist.
The lesson: changing what a field means is a format change even when no size changes.
make rebuilds fs.img because the fs.img rule depends on mkfs, and mkfs on fs.h
and param.h (Makefile:123). Any image kept outside that rule must be rebuilt by
hand.
7MAXOPBLOCKS left at 10
Everything as in the reference except commit 6: MAXOPBLOCKS stays 10 (so LOGBLOCKS
and NBUF stay 30), filewrite keeps its old formula, and mkfs has no
nbitmap + 3 check:
-#define MAXOPBLOCKS 13 // max # of blocks any FS op writes
+#define MAXOPBLOCKS 10 // max # of blocks any FS op writes
The trigger is lograce, a separate test program (not part of the branch). It sets
up files so that one group commit holds four operations:
a 3-block write W to a file f across file blocks 264 to 267, which begin_op
admits and which then waits for f’s inode lock (a child is reading all of f); two
3-block overwrites of other files that finish meanwhile; and the unlink of a 9-block
file whose blocks lie in 9 different bitmap blocks. It repeats this 12 times with
different timings.
What happened when we ran it
$ lograce
lograce: g inode 32
[...]
lograce: setup done, 3086 free
panic: bget: no buffers
# the reference kernel (MAXOPBLOCKS 13) with commit printing and a count of free
# buffers, same program, first attempt:
commit: 30 blocks: 1192 1193 1194 1195 44 1196 1197 1198 1199 45 1200 42 46 55 56 57 58 59 60 61 62 63 67275 1201 67021 9427 17653 25879 34105 47
bcache: min free buffers 10
bcache: min free buffers 8
lograce: attempt 1 (spin 200000) survived
[...]
lograce: attempt 12 (spin 2400000) survived
The two overwrites log 5 blocks each (4 data blocks and an inode block): lh.n = 10.
The unlink begins next; begin_op admits it because 10 + (1 + 1) × 10 ≤ 30, counting
on it to log at most 10. It logs 12: the directory block, two inode blocks and nine
bitmap blocks. Then W gets its lock and logs 8 more (its bitmap writes are absorbed
into the unlink’s nine). That is the 30-block commit the instrumented reference kernel
printed: 10 + 12 + 8 = LOGBLOCKS.
Thirty is not too many for the log, but it is too many for the cache. log_write
pins every logged buffer (kernel/log.c:240), and NBUF is also 30, so all 30
buffers are pinned when commit starts. Its first step, write_log, must
bread log block 1 to copy a logged block into it; bget finds no buffer with
refcnt 0 and panics (kernel/bio.c:87). Without the unlink’s overrun of 2 the
same group peaks at 28 and survives.
On the reference, the same 30-block group leaves 9 of 39 buffers free (8 at the lowest,
while write_log holds one), and all 12 attempts survive; so do 12 attempts on the
uninstrumented reference kernel. The lesson of think 4 and think 6: when a change
makes operations log more, recount every operation’s worst case and raise the budget
that admission control relies on, or the kernel’s promise to itself fails in a place
far from the code you changed.
5. The reference solution
Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:
On the branch (ext/22-bigfile, 8 commits; each commit builds, and mkfs runs, on its own),
built with the project toolchain and run on 3 harts (-smp 3 -m 128M), on a fresh
fs.img:
$ bigfiletest
bigfiletest: 6580 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: size: OK
bigfiletest: blocks used 6607 = 6580 data + 27 indirect
bigfiletest: block count: OK
bigfiletest: read back: OK
bigfiletest: unlink: OK
bigfiletest: free blocks 68930 before, 68930 after
bigfiletest: all blocks freed: OK
bigfiletest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test writebig: OK
[...]
test kernmem: usertrap(): unexpected scause 0xd pid=6477
sepc=0x1b64 stval=0x80000000
[...]
ALL TESTS PASSED
$ bigfiletest
[...]
bigfiletest: blocks used 6607 = 6580 data + 27 indirect
bigfiletest: block count: OK
bigfiletest: read back: OK
bigfiletest: unlink: OK
bigfiletest: free blocks 68927 before, 68927 after
bigfiletest: all blocks freed: OK
bigfiletest: ALL OK
The usertrap() lines are kernmem checking that user code cannot read kernel memory:
expected kills. writebig now writes and reads back a 65,803-block file and unlinks it,
and everything else in the suite (truncation, unlinking open files, concurrent writers
in fourfiles and sharedfd) still works. The second bigfiletest starts from 68,927
free blocks, 3 fewer, as on the original kernel (948 before usertests, 945 after):
usertests leaves a few small files (x, junk, bigarg-ok, stopforking) and a
grown root directory behind. What matters is that before and after are equal.
The full-size case, on a fresh image:
$ bigfiletest 65803
bigfiletest: 65803 blocks (old limit 268, new limit 65803)
bigfiletest: create: OK
bigfiletest: write: OK
bigfiletest: write past MAXFILE fails: OK
bigfiletest: size: OK
bigfiletest: blocks used 66061 = 65803 data + 258 indirect
bigfiletest: block count: OK
bigfiletest: read back: OK
bigfiletest: unlink: OK
bigfiletest: free blocks 68930 before, 68930 after
bigfiletest: all blocks freed: OK
bigfiletest: ALL OK
On the original kernel (with only freeblocks and the test added), bigfiletest -w 300
prints bigfiletest: wrote 268 blocks, and bigfiletest 268 passes with blocks used 269 = 268 data + 1 indirect: the old limit, measured with the same tool. Six power cuts during
bigfiletest -w 6580 all left a consistent file (reveal step 7).
All numbers from recorded runs (QEMU 10.2.1, 3 harts), except where a row says “from
mkfs”. Timings on QEMU depend on what else the computer is doing: “quiet” times were
measured on an otherwise idle computer, “busy” ones while it was busy with other work;
your times will differ. Ranges are over our runs.
original (06aad25)
this branch
largest file
268 blocks, 274,432 bytes
65,803 blocks, 67,382,272 bytes
struct dinode, inodes per block
64 bytes, 16
64 bytes, 16
FSSIZE, image size (from mkfs)
2000 blocks, 2 MB
70,000 blocks, 70 MB
log, buffer cache (MAXOPBLOCKS × 3)
30 blocks, 30 buffers
39 blocks, 39 buffers
metadata, first data block (from mkfs)
47
64
free blocks on a fresh image (with the test program)
948 at the first count
68,930
bigfiletest 268: write, read back, unlink
1.5 s
1.5 s
bigfiletest (6580 blocks)
not possible
36.8 s quiet; 114 s with the computer busy
bigfiletest 65803
not possible
384 s quiet; 3157 s busy
usertests -q
43.0 s, 45.1 s
421 s quiet; 3390 s busy
Metadata cost. 27 indirect blocks for 6580 data blocks, 258 for 65,803: 0.4% either
way. One table block per 256 data blocks, plus two.
What the log sees. A copy of each kernel printed every commit of 9 or more blocks
during usertests -q, and the copy of the branch also kept the lowest number of free
buffers it ever saw:
original
this branch
commits of 9 or more blocks
11, 10 (sharedfd); 11, 13, 9 (fourfiles)
12 (writebig); 15 (sharedfd)
largest commit of a single operation
under 9 (none printed)
12, writebig’s unlink
fewest free buffers
not measured
23 of 39
lograce (clinic 7)
(with MAXOPBLOCKS 10:) panic: bget: no buffers
a 30-block group commit, 8 of 39 buffers free at the lowest; 12 of 12 attempts survive
one write chunk on a fragmented disk (frag13)
not possible
13 blocks
The sharedfd and fourfiles commits are group commits: several processes write at once
and their operations share one transaction. With the larger budget more operations fit
in one group, so the branch’s sharedfd commit is larger. The 12-block one is a single
operation: writebig runs alone, and its unlink logged 64 42 43 55 56 57 58 59 60 61 62 63, the directory block, two inode blocks and all nine bitmap blocks.
Time.usertests -q takes about ten times longer. The only quick test whose work
grew is writebig, which now writes, reads and frees 65,803 blocks instead of 268, one
transaction per block, so the difference is its (reasoned; we timed the suite, not each
test). bigfiletest 268 takes the same 1.5 s on both kernels: the new code only adds
work beyond block 266 (on the branch the 268-block file already has 3 table blocks
instead of 1, which costs nothing measurable). Every one-block write is a transaction
of its own: typically 4 logged blocks (bitmap, indirect block, data, inode), so 10 disk
writes at commit (4 to the log, the header, 4 installs, the header again; commit).
7. Go further
Truncate in pieces. The unlink bound is nbitmap + 3, so the reference’s budget of
13 only works up to 10 bitmap blocks, about 80,000 blocks of disk; mkfs refuses more.
Free a large tree a few bitmap blocks at a time, each part in its own transaction, so the
budget no longer grows with the disk. Work out why this is crash-safe in this tree
(ireclaim finishes an unlinked inode at the next boot), what a reader of the
half-truncated file could see, and how O_TRUNC in sys_open and every other caller of
iput (each already inside someone’s transaction) must change.
A version number for the format. Clinic 6 shows the new kernel silently misreading
an old image. Change FSMAGIC (or add a version field to the superblock) whenever the
meaning of addrs[] changes, so that an old image stops at panic: invalid file system
instead.
One spare buffer. With NBUF == LOGBLOCKS, a group commit that really logs
LOGBLOCKS distinct blocks still pins every buffer, and commit cannot read a log
block (the original xv6 has the same edge at 30). Give the cache a few more buffers than
the log and argue that no admitted group can then exhaust it.
A smarter balloc. Remember where the last search ended and start there. Measure
bigfiletest 65803 before and after on a quiet machine; the late allocations of a large
file currently scan eight full bitmap blocks each.
Extents. Replace the block tree with a list of (start, length) runs, as ext4 does.
Compare the metadata blocks and the number of block reads per bmap for a file written
sequentially, and think about what fragmentation does to it.
mkfs, too. Teach iappend the doubly-indirect level and put a file of more
than 267 blocks into fs.img. Two implementations of one format must agree; write a test
that would catch them disagreeing.