Step 1 of 20

wc reads 512 bytes at a time

wc opened README as descriptor 3 and loops on read(fd, buf, 512) until it returns 0. It never says where to read from. The kernel remembers the position, in the open file (struct file) that descriptor 3 points to: f->off, starting at 0.

README is 2441 bytes, so the reads return 512, 512, 512, 512, 393, and then 0. That is six read system calls, and the output is 48 336 2441 README.

Step 2 of 20

sys_read finds the open file

sys_read fetches the user buffer’s address and the count from the trapframe and turns descriptor 3 into a struct file with argfd (Tour 5: Life of a system call and Tour 6: System-call arguments and user pointers cover these). Then fileread.

No transaction: reading never changes the disk. Compare sys_write's path, where filewrite opens one per chunk.

wc is now on its kernel stack (The stacks of xv6): uservec saved its user sp in the trapframe and loaded the top of this empty page (kernel/trampoline.S:76). wc’s user stack waits, untouched, until the read returns.

Step 3 of 20

The offset is read and advanced under the inode lock

For an FD_INODE file, fileread is three lines: ilock, readi at f->off, then f->off += r, iunlock.

f->off is a field of the struct file, not of the inode, and it has no lock of its own. It is protected by the inode’s sleep-lock: it is read and updated only while the inode is locked. That matters when a struct file is shared, as after fork or dup: two processes reading through it each get the next 512 bytes, never the same 512 twice (step 18 shows the write side).

The inode lock also makes the read see a consistent file: a writer on another hart cannot change size or addrs[] halfway through this readi.

The irq strip still reads noff 0: a sleep-lock is not a push_off level, so interrupts stay on, and a timer interrupt may even make wc yield the hart while it holds the inode lock. Anyone else who wants the inode then sleeps instead of spinning (Locks and interrupt state).

Step 4 of 20

readi clamps the request to the file

readi first trims the request to what exists:

• off > size, or off + n wrapping around a 32-bit uint: return 0.
• off + n > size: shorten n.

On the fifth read, off = 2048 and n = 512, so n becomes 2441 − 2048 = 393. On the sixth, off = 2441 = size, n becomes 0, the loop does not run, and readi returns 0: end of file. There is no “EOF flag” anywhere; end of file is simply the offset reaching size.

Step 5 of 20

One block at a time, copied straight to user memory

Each loop iteration handles the part of the request inside one 1024-byte block:

1. bmap(ip, off / BSIZE): which disk block holds this part? For off = 0, file block 0, which is disk block 48.
2. bread: the block, locked, from the buffer cache (or the disk, Tour 29: A disk read, end to end).
3. m = the smaller of “bytes still wanted” and “bytes left in this block”.
4. either_copyout with user_dst = 1: copyout into wc’s buf, walking wc’s page table by hand (Tour 28: Crossing the user/kernel boundary in memory).
5. brelse.

For a 512-byte read inside one block the loop runs once. A read that straddles a block boundary, say 512 bytes at offset 768, runs twice: 256 bytes from one block, 256 from the next.

If the user address is bad, copyout fails and readi returns -1. The kernel does not crash; the program gets an error.

Notice where the 512 bytes do not go: wc’s kernel stack. copyout moves them straight from the cached block into buf, which is a global array in wc’s user memory. A kernel stack is a single 4 KiB page, so xv6 keeps what it puts there small (the biggest locals are path copies like sys_open’s 128-byte path); on this read path the locals are only a few words.

Step 6 of 20

bmap, the direct case

bmap answers “where is block bn of this file?”. For bn < 12 (NDIRECT), the answer is in the inode itself: ip->addrs[bn]. README’s are 48, 49, 50, and then zeros. No disk access is needed: ilock already copied addrs[] into memory.

If the entry is 0, bmap allocates a block. During a read that cannot happen in xv6: writei refuses to write past the end of a file (step 10), so every block below size has been allocated. The allocation branch is for writes, which come next.

Step 7 of 20

echo writes two bytes

Now echo hi > f. The shell’s child created f (inode 24, empty, no blocks) as descriptor 1 and then execed echo (Tour 35: Creating and naming files). echo makes two calls: write(1, "hi", 2) and write(1, "\n", 1).

Each will be its own system call, its own transaction, its own commit. Our trace:

[commit pid 4 n=3: 46 1006 34]
[commit pid 4 n=2: 1006 34]

The first allocates a data block (bitmap block 46, data block 1006) and updates the inode (block 34). The second only adds a byte to block 1006 and grows the size.

The bytes hi are on echo’s user stack. When the shell’s child execed echo, kexec copied each argument string to the top of the new user stack (kernel/exec.c:101–kernel/exec.c:106) and passed main pointers to them, so argv[1] points into the stack page. The write below copies two bytes from there into the kernel.

Step 8 of 20

filewrite cuts writes into 3072-byte pieces

For an FD_INODE file, filewrite computes max = ((10 − 1 − 1 − 2) / 2) × 1024 = 3072 bytes. Where does that come from? A transaction may write at most MAXOPBLOCKS = 10 blocks, because begin_op reserves that much log space per operation (Tour 31: The log: begin_op, commit and group commit). A write of 3072 bytes can dirty:

4 + 4 + 1 + 1 = 10. The source writes it as 1 (inode) + 1 (indirect) + 3 × 2 (data + bitmap) + 2 “slop for non-aligned writes”: the slop is the fourth data block and the new indirect block’s bitmap update, not a fourth new data block with its own bitmap block. A write that starts on a block boundary touches only 3 data blocks, so it needs at most 9. (In this build there is only one bitmap block, so all the bitmap updates land in one block; the formula is the general worst case.)

Our n = 2 is far below 3072, so the loop runs once.

Step 9 of 20

One transaction per piece

Each piece is begin_op, ilock, writei at f->off, f->off += r, iunlock, end_op. The order is fixed: the transaction is begun before the inode is locked. begin_op may sleep (kernel/log.c:138) when the log has no room for one more operation, until the current transaction commits, and that commit cannot start until every operation already in it has called end_op. If echo held f’s inode lock while sleeping there, and a process B already in the transaction were waiting in ilock for that same inode, then echo would wait for the commit, the commit for B’s end_op, and B for echo: a deadlock.

A write of 10,000 bytes is therefore four transactions (3072 + 3072 + 3072 + 784). Two consequences:

• Not atomic on disk. A crash after the second commit leaves 6144 bytes written and the rest not. Each piece is atomic; the write is not.
• Not atomic in the file. Between pieces the inode is unlocked, so another writer’s piece can land in between (step 19).

If writei writes less than asked (disk full, bad user address), the loop stops, and filewrite returns -1, though some bytes may have been written.

A sleep in begin_op costs no hart. echo’s frames (usertrap … filewrite, begin_op, sleep, sched) wait on its kernel stack, and swtch moves hart 1 to its scheduler stack (kernel/swtch.S:26) until the commit wakes echo up, on whichever hart runs it next.

Step 10 of 20

writei refuses holes and huge files

writei checks two things before writing:

• off > size: writing beyond the end would leave a gap (“hole”). xv6 does not support holes, so this fails. Our write is at off = 0 = size: allowed, it appends.
• off + n > MAXFILE * BSIZE: the largest file is MAXFILE = 12 + 256 = 268 blocks, 274,432 bytes. Beyond that there is nowhere to record a block number.

Because writes always start at or before the end, a file’s blocks below size are always allocated, which is what let step 6 say reads never allocate.

Step 11 of 20

bmap allocates block 0 of f

writei asks bmap for file block 0 of f. ip->addrs[0] is 0: there is no block yet. So bmap calls balloc, and records the answer, 1006, in ip->addrs[0].

Notice what bmap does not do: write the inode. addrs[0] changed only in memory. It relies on its caller to call iupdate, and writei always does, at the end, whether or not the size changed (the comment at line 573 says exactly this). Forgetting it would leave a block marked used in the bitmap that no inode points to.

If the disk is full, balloc returns 0 and so does bmap; writei stops early and reports a short write.

Step 12 of 20

balloc finds a free bit

The free bitmap has one bit per block of the disk, 8192 per bitmap block (BPB). This disk has 2000 blocks, so one bitmap block, 46, is enough.

balloc reads it and tests bits from 0 upward. mkfs reported balloc: first 1006 blocks have been allocated: blocks 0–1005 (metadata, then the programs’ data) are marked used. Bit 1006, bit 6 of byte 125, is the first 0. balloc sets it, log_writes block 46, releases it, and zeroes block 1006 before returning it.

Like the inode allocator (Tour 35: Creating and naming files), there is no allocator lock: the bitmap block’s buffer sleep-lock, held from the test to the set, is what makes the allocation atomic.

Step 13 of 20

bzero, so old data never leaks

A free block may still hold the content of a file deleted earlier. bzero fills the cached block 1006 with zeros and log_writes it.

Why bother, when writei is about to overwrite the bytes it needs?

• Strictly, a data block would not need it: xv6 has no holes, so the 1022 bytes past hi can only become part of f by being written first, and readi never reads past size. But balloc doesn’t know what the block is for, and…
• The same balloc provides indirect blocks, and there a zero entry means “no block”. Garbage would be read as block numbers.

And why through the log, instead of a direct disk write? Because the zeros must reach the disk in the same transaction as the bitmap bit. Then writei’s own log_write of block 1006 is absorbed into this one: the block is logged once.

Step 14 of 20

Copy from user space into the block, and log it

The loop mirrors readi's: bread block 1006, compute how much fits, and either_copyin two bytes, "hi", from echo’s memory into the buffer at offset 0. Then log_write instead of bwrite: the block is pinned and listed for the commit, not written now (Tour 31: The log: begin_op, commit and group commit).

If the copy fails halfway (a bad user pointer partway through), lines 560–564 still call log_write: copyin may already have changed part of the buffer. A changed buffer that is not in the log is not pinned, so it could be evicted and the change silently lost, leaving the cache and the disk telling different stories about the same block. Logging it keeps the cache and the log consistent.

Step 15 of 20

Grow the size, write the inode, commit

off is now 2, past the old size of 0, so size = 2. iupdate copies the in-memory inode (with addrs[0] = 1006 and size = 2) into block 34 and logs it.

Back in filewrite, f->off += 2, iunlock, end_op. echo is the only operation in the transaction, so it commits: blocks 46, 1006, 34, as the trace showed. The bitmap bit, the data and the inode that points to the data reach the disk together, or not at all.

Step 16 of 20

The second write appends, because the offset moved

write(1, "\n", 1): writei at f->off = 2. bmap(0) finds 1006 already there, so no allocation. One byte is copied at offset 2, size becomes 3, and the commit holds just two blocks: 1006 and 34. cat f prints hi.

This is what “appending” means in xv6: writing at an offset that has reached the end. There is no O_APPEND. The shell’s >> opens with O_WRONLY | O_CREATE, without O_TRUNC (user/sh.c:398), and the offset starts at 0. So >> overwrites from the beginning. We tried it:

$ echo xy >> README
$ wc README
49 336 2441 README

The size is still 2441, but there is one more line: the first three bytes, xv6, became xy and a newline.

Step 17 of 20

Past twelve blocks, the indirect block

f will never need it, but a file longer than 12 blocks (12,288 bytes) does. For bn >= 12, bmap subtracts 12 and looks in the indirect block, whose address is addrs[12]:

1. No indirect block yet? balloc one (zeroed, so all 256 entries mean “none”).
2. bread it, and look up entry bn − 12.
3. Entry 0? balloc a data block and store its number in the entry. The indirect block itself changed, so it is log_writen right here (line 451), unlike addrs[], which waits for iupdate.

On this disk, usertests (inode 15, 209,552 bytes = 205 blocks) has its first 12 blocks at 517–528 and its indirect block at 529, listing the other 193.

Every access to blocks 12 and up costs one extra block read, of the indirect block, usually a cache hit. A new block there can dirty four blocks in one go: the indirect block, the bitmap, the data block, and later the inode; which is why filewrite's budget counts the indirect block.

Step 18 of 20

Two processes, one file descriptor

We ran (echo aaa &; echo bbb) > out. The subshell opens out once, then forks both echos; they inherit descriptor 1 pointing at one struct file, one f->off. Each echo makes two writes ("aaa", then "\n"). What can the file look like?

The inode lock covers reading f->off, writing at it, and advancing it. So each write (each piece, for big ones) is placed at a fresh offset; no two can land at the same place, and no byte is lost. But between writes the lock is free:

Result: aaabbb\n\n, 8 bytes. In our four runs we always got aaa\nbbb\n (the first echo is forked first and usually finishes first), but the code permits any interleaving of the four writes that keeps each process’s two in order: aaa\nbbb\n, aaabbb\n\n, bbbaaa\n\n or bbb\naaa\n. The size is always 8.

Step 19 of 20

What a big write looks like to a second writer

Make the writes bigger: two processes sharing a descriptor each write 10,000 bytes. Each write is four pieces, and each piece takes and releases the inode lock (and is its own transaction). So the file can end up as

with the two 10,000-byte writes interleaved in 3072-byte pieces. (We have not observed this; it follows from the loop.) Each piece is placed atomically at a fresh offset, so the total is still exactly 20,000 bytes with no overlap.

The same split shows up after a crash: Tour 32: Crash recovery's logstress test wrote 2000-byte pieces from six processes, and recovery installed one transaction containing blocks from several of them.

Step 20 of 20

What a read and a write cost

wc README: six system calls, six inode lock/unlock pairs, five block reads (all cache hits after the first of each block), five copies to user memory, no disk writes.

echo hi > f’s two writes: two transactions; the first scanned 1007 bitmap bits, zeroed a block, and logged 3 blocks (8 disk writes at commit), the second logged 2 (6 writes). Three bytes of data cost 14 synchronous disk writes. Batching, in user space or by group commit, is what makes real workloads affordable.

The ideas:

• A position in a file becomes a disk block through bmap: 12 direct entries, then one indirect block of 256.
• Allocation is test-and-set under a buffer lock, in balloc as in ialloc, and every new block is zeroed in the same transaction.
• The offset lives in the open file, but the inode lock protects it, which makes each read or write piece atomic with respect to other users of the same descriptor.
• Big writes are split to fit the log, so they are neither atomic on disk nor atomic in the file.