Step 1 of 18 · commit 1: Give the inode a slot for a doubly-indirect block

Thirteen slots, new meanings

The story of this tour was recorded in one run on the finished branch, on three harts, with gdb attached: bigfiletest 300 (pid 3, file bigtest.dat, inode 25) writes 300 blocks, reads them back and unlinks the file. 300 blocks is enough to need the doubly-indirect block and one indirect block under it; the later steps follow file block 267, the first one in the new range.

Commit 1 makes room. NDIRECT drops from 12 to 11 and the array is declared addrs[NDIRECT + 2]: still 13 entries, so struct dinode is still 64 bytes, IPB is still 16, and inode 25 is still at offset (25 % 16) * 64 = 576 of the second inode block (block 43 on the finished branch, whose larger log pushes the inodes back). What changes is the meaning of two slots: addrs[11] was a data block and is now the singly-indirect block; addrs[12] was the singly-indirect block and will be the doubly-indirect one.

MAXFILE is still NDIRECT + NINDIRECT, now 267 blocks, one fewer than before: nothing can reach slot 12 yet, so the kernel works at every commit of this branch. But this is already an on-disk format change. An image made by the old mkfs has data where the new kernel expects a table (clinic 6). make rebuilds mkfs and fs.img because both depend on this header.

Step 2 of 18 · commit 1: Give the inode a slot for a doubly-indirect block

The in-memory inode must agree

struct inode is the kernel’s cached copy of an inode, one of the 50 entries in itable. Its addrs array is separate from the on-disk one, and the two are connected only by memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)) in ilock and the reverse in iupdate (kernel/fs.c:313, kernel/fs.c:240). Both copy the in-memory array’s size. Lengthen one array and not the other and the copy silently drops or invents a slot; that is why this line changes in the same commit.

The fields “below lock” in this struct are protected by ip->lock, a sleep-lock: bmap and itrunc change ip->addrs[] and are only ever called with it held (Locks and interrupt state). Nothing in this lab needs a new lock. Every new block is reached from one inode, and that inode’s sleep-lock serializes everything done to its tree; the shared pieces (the bitmap blocks, the log) already have their own locks.

Step 3 of 18 · commit 2: Map blocks through the doubly-indirect block in bmap

bmap, third range: the doubly-indirect block

The new range follows the shape of the singly-indirect one: subtract the size of the range just passed (bn -= NINDIRECT, line 459), then compare with the size of this one. After both subtractions bn is 0 to 65,535.

This is the moment gdb recorded, on hart 2: writei was called with off = 273,408, file block 267, so bn is 0 here. The inode’s slots were {1070, ..., 1080, 1081, 0}: 11 direct blocks, the singly-indirect block 1081, and no doubly-indirect block yet. So line 464 calls balloc, which will return 1338, the next free block on this disk, and line 467 stores it in the in-memory inode. That store is not logged here and does not need to be: writei ends with iupdate, which copies ip->addrs into the inode’s block and logs it, in this same transaction.

State: a write system call, so interrupts are on (sstatus = 0x200000022, SIE set) and no spinlock is held (noff 0). The process holds inode 25’s sleep-lock, taken by filewrite through ilock. The transaction is open (log.outstanding = 1) and has logged nothing yet (log.lh.n = 0).

Step 4 of 18 · commit 2: Map blocks through the doubly-indirect block in bmap

Allocating a block inside the transaction

balloc is unchanged by this lab, but every level of the tree goes through it, so it is worth seeing what one allocation logs. (The state shown is for the first call, from line 464, which allocates the doubly-indirect block itself, so no table buffer is held yet; for the later levels the parent table’s buffer is held too.) It finds the first clear bit in the bitmap, sets it, and logs the bitmap block (line 80). Then bzero (lines 52-61) reads the new block, fills it with zeros and logs it too. Two logged blocks per allocation, and the zeroing is essential for tables: 0 is how bmap recognizes an empty entry.

bzero reads the block from disk only to overwrite it. On a cache miss that is a real disk read, and the process sleeps in virtio_disk_rw until the interrupt: allowed, because only sleep-locks are held. A process that sleeps (or is made to yield by a timer interrupt, which kerneltrap does whenever no spinlock is held) may resume on another hart. In the recorded run it did: bmap started on hart 2, was on hart 1 after the first two allocations and on hart 0 after the third, always with the same kernel stack (sp = 0x3fffff9e80 each time). That is why this step says “any”.

After the doubly-indirect block and the first indirect block are allocated, gdb showed log.lh.n = 3: bitmap block 55, block 1338 and block 1339, each logged once although the bitmap block was changed twice (log_write absorbs repeats).

Step 5 of 18 · commit 2: Map blocks through the doubly-indirect block in bmap

The middle level, logged with its parent

The doubly-indirect block (1338) is read into the cache and its entry bn / NINDIRECT = 0 is examined. It is 0, so a new indirect block is allocated (1339), its number stored in entry 0, and the doubly-indirect block logged (line 476). gdb at line 475, on hart 1: addr = 1339, bp->blockno = 1338, the buffer locked, refcnt 2 (this bread plus the pin that log_write put on it when bzero logged it), and ip->addrs[12] = 1338.

Line 476 is the line clinic 1 deletes. In this first transaction its absence would go unnoticed, because block 1338 is already in the transaction (bzero logged it) and the commit copies its current contents. For indirect blocks 1 to 24, allocated in later transactions, it is the only thing that puts the change on disk.

Only one table buffer is held at a time: the doubly-indirect block is released (line 479) before the indirect block is read (483). During balloc at line 473, though, it is held while balloc locks the bitmap block and then the new block that bzero reads: always the table first, like the singly-indirect code. balloc holds no table’s lock, so the order is never reversed.

Step 6 of 18 · commit 2: Map blocks through the doubly-indirect block in bmap

The bottom level, and the data block

The indirect block (1339) is read, entry bn % NINDIRECT = 0 examined, a data block allocated (1340), stored, and the indirect block logged. gdb at line 488 recorded hart 0 (the process moved again while bzero read block 1340), addr = 1340, bp->blockno = 1339, and log.lh.n = 4: the transaction now holds bitmap block 55 and blocks 1338, 1339 and 1340. (gdb printed bn = 4294967029 here: with -O, gdb’s view of bn is wrong at this line; writei’s off says it is 0.)

The function returns 1340 to writei, which reads the block, copies the user’s 1024 bytes into it and logs it (absorbed: it is in the transaction already), and then iupdate logs inode block 43: five blocks in this write’s transaction, counted from the code. File block 268 will cost far less: only entry 1 of block 1339 changes, plus the bitmap, the data block and the inode block.

If balloc fails at any level, bmap returns 0 and writei stops. A table allocated before the failure stays allocated and recorded (its parent was logged), empty; itrunc frees it later like any other.

Step 7 of 18 · commit 2: Map blocks through the doubly-indirect block in bmap

Why a crash leaves a consistent file

Everything the previous steps changed belongs to one transaction: bitmap bits, the two new tables, the parent entries, the data, and (line 614) the inode with its new size and addrs[12]. filewrite opened it with begin_op and will close it with end_op right after this function returns, and end_op commits before returning (Tour 31: The log: begin_op, commit and group commit). There is no moment at which the disk shows a block marked in use but not reachable, or a pointer to a block not marked in use.

So a crash during a long write loses at most the chunk in progress. We cut the power between 9 and 17 seconds into bigfiletest -w 6580 (one block per write), six times, on fresh images. Every next boot found a consistent file: 357, 452, 555, 568, 693 and 808 good blocks, each time with the free count exactly n data + nindirect(n) below 68,930. Once (13 seconds) the kill landed after a commit point and before the installation finished, and the boot replayed the log:

recovering tail 0 dst 55
recovering tail 1 dst 1628
recovering tail 2 dst 1596
recovering tail 3 dst 43

That is the bitmap block, the data block for file block 554, indirect block 1 (1596), which received its entry, and the inode block. bigfiletest -r then reported bigtest.dat has 555 good blocks, 68371 blocks free: 68,930 − 555 data − 4 tables. Nothing leaked, nothing dangled.

Step 8 of 18 · commit 3: Free the doubly-indirect tree in itrunc

itrunc: children first, root last

Now the end of the scenario: unlink("bigtest.dat"). The new block mirrors bmap's tree. For each nonzero entry of the doubly-indirect block, read that indirect block, free every data block it lists, release it, free it. Then free the doubly-indirect block and clear the slot. gdb stopped at line 540 on hart 2 with i = 0, a[0] = 1339, bp->blockno = 1338 and bp2->blockno = 1339 (both buffers still held: line 540 is the brelse), and log.lh.n = 4.

Why read before free: bfree only clears a bit. But the moment it is clear, another process on another hart may balloc that block and bzero it. Freeing indirect block 1339 before reading it could let its 256 entries turn into zeros under us, and their data blocks would leak. So each table is used, released, and only then freed (line 541).

The zero test on line 531 matters too: a file of 300 blocks uses one indirect block, so 255 of the 256 entries are empty and skipped, without reading anything.

Step 9 of 18 · commit 3: Free the doubly-indirect tree in itrunc

One transaction for the whole truncation

itrunc is called from iput when the last reference to an unlinked inode goes away, here inside unlink’s transaction. gdb at itrunc's entry: hart 1, log.outstanding = 1, log.lh.n = 3, ip->size = 307,200 and slots {1070, ..., 1081, 1338}. By the code, those 3 logged blocks are the directory’s data block (the cleared entry), the directory’s inode block and the file’s inode block (nlink 0), all logged by sys_unlink before it let go of the inode.

itrunc runs with the inode’s sleep-lock (taken at line 362) and no spinlock: iput released itable.lock at line 363, because freeing may sleep on disk reads.

How big does this transaction get? Each bfree logs one bitmap block, absorbed after the first time. For this 303-block file that is one block (all its blocks are in bitmap block 0): 4 logged blocks in all. For writebig’s 66,061 blocks it is nine bitmap blocks, 12 logged blocks in all: more than the original budget of 10, within the 13 of commit 6 (think 6). The original tree never had this problem: its largest file was 268 data blocks + 1 indirect block, on a disk with a single bitmap block.

After itrunc, ifree clears the type (line 377), in the same transaction: the inode and all its blocks become free at one commit. If the machine crashed before that commit, the next boot would find the file still linked, untouched.

Step 10 of 18 · commit 4: Grow the file system to 70000 blocks

FSSIZE, the size of the disk

FSSIZE is the number of 1024-byte blocks in fs.img. The kernel never uses this constant: it reads sb.size from the superblock at boot. mkfs is the one that uses it, to size the image and lay out the metadata.

The three lines above it tie the log to the buffer cache: MAXOPBLOCKS = 10 blocks per operation, LOGBLOCKS = 30 in the on-disk log, NBUF = 30 buffers. They do not change in this commit; commit 6 raises all three, after think 4 and think 6 have recounted what one operation can log with the new tree.

70,000 holds one maximum-size file (66,061 blocks with its tables) plus the roughly 1000 blocks that mkfs fills with programs. The image grows from 2 MB to 70 MB.

Step 11 of 18 · commit 4: Grow the file system to 70000 blocks

What mkfs derives from FSSIZE

mkfs runs on your computer during make, and its output shows the new layout:

nmeta 55 (boot, super, log blocks 31, inode blocks 13, bitmap blocks 9) blocks 69945 total 70000
balloc: first 1014 blocks have been allocated

nbitmap = 70,000 / 8192 + 1 = 9 (line 28), so the metadata is 2 + 31 + 13 + 9 = 55 blocks and the first data block is 55, where it was 47. The superblock written at line 119 records each region’s start (bmapstart is still 46: the bitmap comes after the log and the inodes, so only what follows it moves). Line 114 writes all 70,000 blocks of zeros, which is why the image is 70 MB on disk.

Then mkfs copies the programs in: 1014 blocks in use when it is done at this commit. (On the finished branch, with a 40-block log and bigfiletest on the disk: nmeta 64, 1070 in use, 68,930 free, the before number bigfiletest prints.) mkfs’s own balloc marks the first bits in the first bitmap block only (and asserts that they fit in it); the other eight bitmap blocks stay zero, which means free.

Step 12 of 18 · commit 4: Grow the file system to 70000 blocks

balloc scans every bitmap block, from the start

The kernel side needs no change: the outer loop runs b over sb.size in steps of BPB = 8192, reading one bitmap block per step with BBLOCK(b, sb), nine of them now.

But look at the cost. Every call starts at block 0. Late in writebig, with 65,000 blocks in use, each allocation reads eight full bitmap blocks (from the cache: they are used on every allocation, so they stay recently used) and tests some 65,000 bits before it finds a clear one, each block’s sleep-lock held while it is scanned (and the indirect block being filled held throughout, since bmap calls balloc with it locked). That is a loop of 65,000 iterations per allocated block, reasoned from the code; we did not measure what it costs. A hint (“start looking where the last search ended”) would remove it; see the stretch goals.

Step 13 of 18 · commit 5: Raise MAXFILE to 11 + 256 + 65536 blocks

The switch: MAXFILE

With every piece in place, one line lets writei use them: MAXFILE = 11 + 256 + 65,536 = 65,803. writei's guard off + n > MAXFILE * BSIZE (kernel/fs.c:551) now allows offsets up to 67,382,272, and the 65,804th block is refused there, before bmap could reach its panic("bmap: out of range"). bigfiletest 65803 checks exactly that: write past MAXFILE fails: OK.

MAXFILE is also used by user programs: usertests includes this header, so writebig and diskfull now write 65,803-block files. That is the reason FSSIZE had to come first: at commit 4 nothing used the bigger disk yet; from here on, usertests -q needs it.

Step 14 of 18 · commit 5: Raise MAXFILE to 11 + 256 + 65536 blocks

mkfs keeps its own, smaller limit

mkfs has its own implementation of the block map in iappend: direct slots and the singly-indirect block, nothing more. Its assertion used to say fbn < MAXFILE, which was true when MAXFILE was exactly what this code handles. With the new MAXFILE, a 300-block program would pass the assertion and the else branch would index indirect[fbn - NDIRECT] past the end of its 256-entry array on mkfs’s stack.

The files mkfs copies are far smaller (usertests is the largest: 209,624 bytes, 205 blocks), so instead of teaching mkfs the new level, the assertion now states the limit this code really has. Two programs that write the same format with two implementations: when one changes, the other’s assumptions must be checked.

Step 15 of 18 · commit 6: Recount the log budget for the doubly-indirect tree

Re-budget the log: MAXOPBLOCKS 13

Think 4 and think 6 recounted what one operation can log with the new tree: a 3-block write chunk up to 13 blocks (measured on a fragmented disk), an unlink up to nbitmap + 3 = 12 (measured for writebig). The old promise, 10, is what begin_op’s admission test relies on, so this commit raises it to 13, and LOGBLOCKS and NBUF follow as 39.

Why NBUF must follow: log_write pins every logged buffer until the commit has installed it, and commit then needs a free buffer for each log block it reads. With NBUF equal to LOGBLOCKS, a group commit that really logs LOGBLOCKS distinct blocks leaves no buffer at all, and bget panics bget: no buffers. That is exactly what clinic 7 shows on the branch without this commit: a four-operation group commit that reached 30 blocks because one unlink logged 12 where 10 were reserved. With the new budget the same 30-block group leaves 9 of 39 buffers free.

The cost is a log of 40 blocks instead of 31. mkfs puts the log before the inodes, so everything after it moves 9 blocks: the inodes now start at block 42, the bitmap at 55, and data at 64 (nmeta 64).

Step 16 of 18 · commit 6: Recount the log budget for the doubly-indirect tree

The write chunk, recounted term by term

The formula now lists what think 4 counted: the inode block (1), up to 3 table blocks (singly-indirect, doubly-indirect, an indirect block), the bitmap blocks of 2 new tables (2), one existing data block at an unaligned start (1), and 2 per new data block. With MAXOPBLOCKS = 13 that is (13 - 1 - 3 - 2 - 1) / 2 = 3 blocks per chunk, the same chunk size as before, so writes cost no more transactions than they did.

The measured worst case fits exactly. On a disk with one free block in each of the first five bitmap blocks, one chunk crossing into the doubly-indirect range logged:

commit: 13 blocks: 1457 55 1458 1203 56 9684 57 17910 58 26136 59 34362 43

The ordinary case is much smaller: bigfiletest writes one block per call, which by the code logs at most 6 blocks, and the instrumented runs printed no commit of 9 or more during it.

mkfs gets the matching check for the other operation: assert(nbitmap + 3 <= MAXOPBLOCKS), so a larger FSSIZE (more bitmap blocks than an unlink can log within the budget) is refused at build time instead of panicking someday at run time.

Step 17 of 18 · commit 7: Add freeblocks, a system call that counts free blocks

A system call to count free blocks

A test-only addition: nfreeblocks walks the bitmap exactly as balloc does and counts clear bits; sys_freeblocks in sysfile.c calls it for the root device. It runs outside any transaction. That is fine because it only reads: bread returns the cached bitmap blocks, including bits changed by transactions not yet committed, and holds each block’s sleep-lock while counting, so it never sees a half-updated byte.

What it cannot promise is that the count is still true when the program uses it: nothing stops another process from allocating right after brelse. The comment says so, and bigfiletest runs alone. On a fresh image it returns 68,930.

Step 18 of 18 · commit 8: Add bigfiletest, a test program for large files

The test

The test follows the think questions. The first free count is taken right after open(O_CREATE) (line 128), so a directory block that create might add is not counted against the file. Each block is written with its own number and a pattern (fill), so two file blocks mapped to one disk block, or a block mapped to the superblock (clinic 2), cannot both read back correctly.

The block count is checked exactly: used == n + nindirect(n), 6580 + 27. This is the check that caught clinic 2’s missing allocation (302 for 300), and the final comparison caught clinic 3’s leak (68930 before, 62591 after). The size comes from stat, the contents from reading every byte back.

With n = MAXFILE, one more 1024-byte write must fail. The -w and -r modes write a file and stop, or check an existing one: what the crash experiments in this lab used.