Step 1 of 18

Three children, three files, three writes

logstress exists to stress exactly this code. Each child opens its own file and tries to write 2000 bytes 250 times. (It never gets there: the largest xv6 file is MAXFILE × BSIZE = 274,432 bytes, so each child’s 138th write fails and the program prints write failed -1 three times. The first 137 writes per child are plenty of load for the log.) We follow the first write of each child.

2000 bytes starting at offset 0 of an empty file covers file blocks 0 and 1, so each write must allocate two data blocks, fill them, and record them in the inode. On disk, that means changing:

• the bitmap (block 46), twice;
• two new data blocks, each zeroed and then written;
• the inode block holding the file’s inode (block 34 for all three files).

None of the three children shares a file or an inode lock with the others. But all three will change block 46 and block 34. The log has to combine their changes correctly and make them durable together.

Step 2 of 18

filewrite brackets each chunk with begin_op and end_op

For an inode, filewrite splits the write into chunks of at most ((MAXOPBLOCKS - 1 - 1 - 2) / 2) * BSIZE = ((10 - 4) / 2) * 1024 = 3072 bytes. Each chunk is one transaction: begin_op, lock the inode, writei, unlock, end_op.

The arithmetic is a promise. MAXOPBLOCKS = 10 is the most blocks one transaction may change. The comment budgets for the inode block, an indirect block, two blocks of slack for unaligned writes, and the rest split between data blocks and bitmap blocks. Our 2000-byte write fits in one chunk, so it is one transaction.

Notice that begin_op comes before ilock. A process waiting in begin_op holds no inode lock, so it cannot block anyone who is trying to finish a transaction.

Step 3 of 18

The log's state

The in-memory log structure, protected by log.lock:

lh doubles as the on-disk header format (logheader): when it is written to block 2, the disk learns which blocks the log holds.

The log area is 31 blocks: the header at block 2, then 30 log blocks at 3–32 (sb.nlog = 31 in this image). Log block i holds the new contents of lh.block[i].

Step 4 of 18

Child A is admitted

begin_op takes log.lock and checks two things:

1. Is a commit in progress? Then wait: a commit is writing the log area, and a new transaction’s blocks must not mix into it.
2. Is there room? The test is lh.n + (outstanding + 1) * MAXOPBLOCKS > LOGBLOCKS. Every running transaction might log up to 10 more blocks, so begin_op reserves 10 for each one, plus 10 for the newcomer, on top of what is already logged.

For child A: 0 + (0 + 1) * 10 = 10 ≤ 30. Admitted: outstanding = 1, release the lock, return.

Child B on hart 1 arrives right after: 0 + (1 + 1) * 10 = 20 ≤ 30. Admitted, outstanding = 2.

Step 5 of 18

Child A logs the bitmap

Inside writei, balloc reads the bitmap, sets the bit for block 1006, and calls log_write instead of writing the block to disk.

log_write takes log.lock, checks the transaction is not over-full and that the caller is really inside one (outstanding ≥ 1), and searches lh.block[] for 46. It is not there, so it becomes lh.block[0] = 46, lh.n = 1, and bpin pins the buffer in the cache so it cannot be recycled before the commit (Tour 30: The buffer cache). For those few instructions hart 0 holds two spinlocks, log.lock and then bcache.lock (noff 2): one edge of the kernel’s lock order (Locks and interrupt state).

Nothing has been written to disk. The change to the bitmap exists only in the cached buffer, and the log header in memory now says “block 46 is part of this transaction”. That is the whole idea of log_write: record, don’t write.

Step 6 of 18

Child C must wait for room

Child C reaches begin_op on hart 2 just after A logged the bitmap: 1 + (2 + 1) * 10 = 31 > 30. There is not enough guaranteed room, so C registers on channel &log with sleep_prepare, releases log.lock, and sleeps.

Three transactions can be admitted together only when the log is completely empty: 0 + 3 * 10 = 30. (In our illustrative interleaving C arrives just too late. In the traced run, all three children were in fact admitted together while the log was still empty, and after that a third transaction usually waited: 444 waits for room in one logstress f1 f2 f3.)

While it waits, C’s write is parked on C’s kernel stack: usertrap, syscall, sys_write, filewrite, begin_op, sleep, sched, with p->context saved by swtch and hart 2 gone to its scheduler stack (kernel/swtch.S:26). Nothing else is stuck with it: no lock, no inode, no buffer.

The reservation is pessimistic. A and B will each touch 4 blocks (and B adds only 2 new log slots, since 46 and 34 are already there), not 10. But begin_op cannot know that in advance, and running out of log space in the middle of a transaction would have no good recovery (log_write simply panics). Waiting at the door is the safe choice.

Step 7 of 18

Absorption, twenty-one calls become eight blocks

Child A keeps going. For its 2000 bytes, it calls log_write 7 times:

(This sequence of log_write calls, 46, 1006, 1006, 46, 1007, 1007, 34, is exactly what a trace of logstress in this build shows for the first write. The set of logged blocks it leaves is 46, 1006, 1007, 34.)

Absorption (lines 234–237): if the block is already in the transaction, nothing is added. The log holds block numbers, and the cached buffer always holds the latest contents, so the commit will write whatever the block contains at commit time. Seven calls, four log slots.

In our illustrative interleaving, B and C repeat the pattern with 1008–1009 and 1010–1011. Their bitmap and inode-block changes land in blocks 46 and 34, which are already in the transaction. So all three writes together make 21 log_write calls but log only 8 blocks: 46, 1006, 1007, 34, 1008, 1009, 1010, 1011.

Step 8 of 18

One inode block, three files

At the end of its writei, child B calls iupdate to copy f2’s new size (2000) and its block list (1008, 1009) into the on-disk inode. Inodes are 64 bytes, 16 to a block, and inodes 24, 25 and 26 all live in block 34, in slots 8, 9 and 10 of it (inum % IPB, byte offsets 512, 576 and 640).

So B breads block 34, a cache hit on the buffer A already modified and pinned. It sees A’s update to inode 24 already there, writes inode 25 next to it, and calls log_write: absorbed. When the transaction commits, one write of block 34 carries both files’ new inodes, and C’s too.

This is why the buffer cache’s “one copy per block” rule matters to the log. The log can merge three processes’ changes to block 34 only because all three made them, one at a time under the buffer’s sleep-lock, to the same cached copy.

Step 9 of 18

end_op, but not the last

Child A finishes writei, unlocks its inode, and calls end_op. Under log.lock, outstanding drops from 2 to 1. B is still running, so A must not commit: B’s half-done changes are mixed into the same buffers (block 34 and 46), and committing now would put a partial transaction on disk.

So A just calls wakeup(&log): decreasing outstanding freed 10 blocks of reservation, and someone © may be waiting for exactly that. Then A returns to user space. Its write is done, but its data is not yet on disk: it is in the cache, pinned, waiting for the group commit.

The panic("log.committing") check can never fire in correct code: committing is set only when outstanding reaches 0, and while it is set, begin_op admits nobody, so nobody can be between begin_op and end_op to call this.

Step 10 of 18

The last end_op commits for everyone

B ends next (outstanding 1), and suppose A has not yet come back. Then C, finishing its own writei, calls end_op and takes outstanding to 0. C is the last one out, so C commits: it sets do_commit = 1 and log.committing = 1 under log.lock, releases the lock, and calls commit.

C will now do the disk work for all three children: 8 blocks, 3 files. That is group commit. A and B returned to user space long ago, so their kernel stacks are empty again (a process in user mode has nothing on its kernel stack); all the remaining work happens on C’s kernel stack. Committing once for several system calls saves disk writes (block 46 and block 34 go through the log once, not three times) and keeps transactions from interleaving on disk.

The price is fairness: C’s write takes as long as the whole commit, while A’s and B’s returned at memory speed. (And until the commit finishes, A’s and B’s data is in memory only. A crash now would lose it, cleanly: the disk would still show three empty files.)

Step 11 of 18

Why commit runs without log.lock

The comment says it: commit writes to the disk, and every disk write sleeps (Tour 29: A disk read, end to end). Sleeping while holding a spinlock is forbidden, so log.lock must be released first. The rule is enforced: sched panics with sched locks unless noff is exactly 1, the process’s own p->lock. The buffers commit holds while it sleeps are sleep-locks, which noff does not count (Locks and interrupt state).

What protects the log’s state during the commit, then? The committing flag, set under the lock, acts as a lock of its own:

• begin_op sees committing == 1 and sleeps, so no new transaction starts.
• outstanding is 0, so nobody is between begin_op and end_op, and therefore nobody can call log_write and change lh.

So commit reads log.lh.n and log.lh.block[] without the lock, and that is safe: no other code can be writing them. This is a common pattern: a spinlock guards a flag, and the flag guards a long operation that can sleep.

Step 12 of 18

Step 1: copy the blocks into the log

write_log goes through the 8 logged blocks in order. For tail = 0..7:

• to = bread(log.dev, 2 + tail + 1): log blocks 3, 4, …, 10.
• from = bread(log.dev, lh.block[tail]): the cached home block (46, 1006, …), a guaranteed cache hit because it is pinned.
• Copy 1024 bytes and bwrite the log block. The home locations are not touched yet.

One inefficiency is visible here: bread of a log block reads it from disk first if it is not cached, only to overwrite all of it. The trace in this build shows exactly that for the first commit after boot (read block 3, write block 3, read block 4, …).

If the machine crashes during this step, nothing is lost or damaged: the header on disk still says n = 0, so recovery ignores the half-written log, and the home blocks still hold the old, consistent state.

Every bwrite here goes through virtio_disk_rw and sleeps until the disk finishes (Tour 29: A disk read, end to end), so C normally goes to sleep and wakes up again for each of these 8 writes (and for each log-block bread that misses). Each time, C’s system call is parked on C’s kernel stack (The stacks of xv6):

child C's kernel stack, during one log write
  top ─► usertrap · syscall · sys_write · filewrite
         end_op (commit and write_log are inlined into it in this build)
         bwrite · virtio_disk_rw · sleep · sched   ← p->context.sp

C may wake on a different hart each time; the stack goes with the process, not the hart.

Step 13 of 18

Step 2: the commit point

write_head copies the in-memory header into block 2, n = 8 and the list 46, 1006, 1007, 34, 1008, 1009, 1010, 1011, and writes it.

This one disk write is the commit. Before it completes, a crash leaves n = 0 on disk and the transaction never happened. After it, a crash is repaired at boot: recover_from_log finds n = 8 and copies the 8 log blocks to their homes (Tour 32: Crash recovery). Either all three files get their data, bitmap bits and inodes, or none do.

That relies on the header write itself being all-or-nothing. The header is 4 + 30 * 4 = 124 bytes, so it lies entirely within the first 512-byte sector of block 2; xv6 assumes the disk writes a sector atomically.

Step 14 of 18

Step 3: install, and unpin

Now install_trans writes each block to its home location: read log block 3 + tail (normally a cache hit, since write_log just used it), read the home block (also cached), copy, and bwrite the home block: 46, then 1006, and so on.

Strictly, the copy is redundant during a normal commit: the cached home buffer already holds exactly what was copied into the log. The same function is used for crash recovery, where the cache is empty and the log on disk is the only copy.

With recovering == 0, each home buffer is then bunpinned: its change is on disk at last, so it may be recycled. After both brelses, its refcnt drops to 0 and it moves to the front of the LRU list (Tour 30: The buffer cache).

A crash during this step is harmless: the header still says n = 8, so recovery repeats the whole installation. Writing a block twice with the same contents is fine; the log is a redo log, and redoing is idempotent.

Step 15 of 18

Step 4: erase the transaction

Finally commit sets lh.n = 0 and calls write_head again, writing n = 0 to block 2. The log is empty on disk too; a crash from now on recovers nothing, which is correct, since everything is already home.

Count the disk writes for this commit: 8 log blocks + 1 header + 8 home blocks + 1 header = 18 writes, plus whatever log blocks had to be read first. Every write is synchronous: C sleeps through each one (Tour 29: A disk read, end to end). Without the log, the same changes would be 8 writes. Without group commit, three separate commits would have sent the bitmap and the inode block through the log three times each.

commit first checks lh.n > 0. Many transactions log nothing at all (an open of an existing file for reading still calls begin_op/end_op), and those commits do no I/O. The trace shows several such empty commits during every boot, and one for each exec that runs alone (its transaction reads the program but changes nothing; close and exit are similar).

Step 16 of 18

Reopening the door

Back in end_op, C re-takes log.lock, clears committing, increments ncommit, and calls wakeup(&log).

Everyone sleeping on &log wakes: A and B, if they are back with their next writes in begin_op, and any sync caller (next step). logstress’s parent and the shell are asleep in wait on a different channel and are not disturbed. Each re-checks the conditions in the while loop under log.lock. That is why begin_op is a loop: a wakeup means “something changed”, not “you may go”. The first two or three to re-check get in; the rest go back to sleep.

Only now does C’s write return to user space, 2000 bytes written and, unlike A’s and B’s a moment ago, already durable.

Step 17 of 18

sync waits for the commit in flight

Suppose you had started logstress f1 f2 f3 & in the background, and you type sync while it is still running. sys_sync takes log.lock:

• If nothing is running and nothing is committing, every finished transaction is already on disk (xv6 commits whenever outstanding reaches 0), so sync returns at once.
• Otherwise it records n = ncommit + 1 and sleeps on &log until ncommit reaches n: until the transaction that is running (or committing) now has been committed.

So after sync returns, every write that had returned before sync was called is durable. In our scenario, A’s and B’s writes returned before the commit; sync guarantees they are on disk.

It is woken by the same wakeup(&log) as begin_op, so it re-checks in a loop too.

Step 18 of 18

What group commit bought

Three write calls on three harts, 6,000 bytes of data. The log turned 21 log_write calls into 8 logged blocks, committed them with one header write, and did all the disk work on one hart, holding no spinlock (only the sleep-locks of the one or two buffers it is copying).

The key ideas:

• Record, don’t write. Inside a transaction, log_write only notes the block number and pins the buffer. The cache holds the changes.
• Admission reserves space: 10 blocks per running transaction. Three can run together only into an empty log; otherwise the newcomer waits.
• Absorption: a block changed many times, or by many processes, is logged once.
• Group commit: the last end_op commits everyone’s changes together; earlier ones return immediately, not yet durable.
• The commit point is one header write. Before it, nothing happened; after it, recovery will finish the job.
• committing, a flag guarded by log.lock, does a lock’s job during the commit, so the long, sleeping commit holds no spinlock.