kernel/log.c

Headers

The log works on buffers (kernel/buf.h), reads the superblock’s layout fields (kernel/fs.h), and uses a spinlock plus the sleep/wakeup functions declared in kernel/defs.h.

The design, in the source's words

This comment is an accurate summary of the protocol. Two points deserve emphasis.

Group commit. A transaction is not one system call. Several file system calls can run at the same time, and their changes all go into one transaction, which commits when the last of them ends. Because the log only commits when no call is in progress, a commit never contains half of a system call’s changes.

A redo log of whole blocks. The log stores the new contents of each modified block, never the old ones. Recovery can only finish a committed transaction (redo it), never undo one, so nothing may reach a block’s home location before the transaction is committed. That is why the file system calls log_write instead of bwrite.

“Log appends are synchronous” means that commit waits for each disk write to finish before starting the next (bwrite returns only when the device reports completion), so the order of writes on disk is the order in the code.

The log header

The header records which blocks the log contains: n blocks, whose home block numbers are block[0] … block[n-1]. The copy of block block[i] is stored in log block log.start + 1 + i, right after the header block.

The same struct serves twice: as the layout of the header block on disk, and as the in-memory list of blocks the current transaction has modified (log.lh).

With LOGBLOCKS = 30 it is 4 + 30 × 4 = 124 bytes, well within one 1024-byte block (checked by initlog). On disk the log occupies 31 blocks, 2 to 32: mkfs sets nlog to LOGBLOCKS + 1.

The log's in-memory state

One global log for the one disk. lock (a spinlock) protects outstanding, committing, ncommit and the in-memory header lh while operations are running.

outstanding counts the file system calls between begin_op and end_op. committing is 1 while commit runs; new operations wait until it is 0. ncommit counts finished commits, so that sys_sync can wait for “the next commit”. start and dev say where the log is on disk.

Forward declarations

initlog and end_op call these static functions, which are defined further down the file. The empty parentheses of commit() are an old-style declaration.

initlog(): find the log and recover

Called by fsinit (kernel/fs.c:47) right after the superblock has been read, in the first process, before any file system call can run. It copies the log’s location from the superblock and then runs crash recovery.

The size check is a guard for anyone who raises LOGBLOCKS: the header must fit in one block, or write_head would write beyond the buffer’s data.

install_trans(): copy logged blocks to their home locations

For each block in the header, read its copy from the log, copy the bytes into the buffer for its home block, and write that buffer to disk.

It runs in two situations, told apart by recovering:

• After a commit (recovering == 0, from commit). The home block’s buffer is still in the cache, pinned by log_write, and already holds the new data, so the memmove copies identical bytes. The important part is bwrite. Afterward bunpin drops the pin, so the buffer can be recycled.
• During recovery (recovering == 1, from recover_from_log). The cache holds none of the logged blocks yet (only the superblock and the log header have been read), so the copy from the log is what puts the new data in place. Nothing was pinned, so there is nothing to unpin. Each block replayed is printed.

Running it twice for the same header has the same effect as running it once, which is what makes a crash during installation or recovery harmless.

read_head(): load the header from disk

Reads the log’s header block (log.start) and copies the count and block numbers into log.lh. The cast treats the buffer’s raw bytes as a logheader, the same layout write_head wrote.

write_head(): the commit point

Copies the in-memory header into the header block and writes it to disk, waiting until the write completes.

This one write is what decides, after a crash, whether a transaction happened. Before it, the header on disk says n == 0 and recovery ignores the log. After it, the header lists the logged blocks and recovery installs them all. The same function also clears the log, by writing a header with n == 0 once the blocks are installed.

The argument relies on the header write being all-or-nothing: after a crash, the disk holds either the old header or the new one, never a mix. The bytes that matter (124 of them, see lines 35–38) lie in the block’s first 512-byte sector, and a disk is normally assumed to write a single sector atomically. (Simplified: xv6 does not state or check this assumption.)

recover_from_log(): finish a committed transaction

Read the header; install whatever it lists (nothing, if n is 0); then write an empty header, so that the log is clear before new transactions start.

If the system crashed after a commit but before (or during) installation, the home locations get the new contents now. If it crashed before the commit point, n is 0 and the half-written log blocks are ignored. Either way the file system is left with all of the last transaction’s changes or none of them.

begin_op(): join the current transaction

Called at the start of every file system operation that may write to the disk (for example in sys_link, kernel/sysfile.c:132, and also by kexec, by kexit when it releases the current directory, and by ireclaim). Calls that only read, like read, do not use the log. It waits in two cases, then registers the caller as one more outstanding operation.

• A commit is in progress. Changes made now would mix with blocks being written to the log, so the caller waits for the next transaction.
• The log might overflow. Each operation is assumed to write at most MAXOPBLOCKS (10) distinct blocks. The check reserves that much for every outstanding operation plus this one, on top of the log.lh.n blocks already logged, and waits if the total would exceed LOGBLOCKS (30). With an empty log, at most three operations can run at once. The estimate is conservative: blocks already logged by the running operations are counted in both lh.n and their reservation.

Both waits use sleep and wakeup on the channel &log: sleep_prepare while log.lock is held, then release, then sleep, so a wakeup between the release and the sleep is not lost. end_op issues the wakeups. After waking, the loop checks both conditions again.

end_op(): leave the transaction, and commit if last

Called at the end of every operation that called begin_op. It decrements outstanding; the panic checks that no commit is running, which begin_op guarantees.

If this was the last outstanding operation, this process becomes the committer: it sets committing (so new operations wait in begin_op) and, after releasing log.lock, calls commit. The lock must be released first because commit reads and writes the disk and so sleeps, and a process must not sleep holding a spinlock. No lock is needed during the commit: with committing set and no operations outstanding, nobody else changes log.lh.

When the commit is done, it clears committing, counts the commit and wakes everyone waiting on &log: operations waiting in begin_op and callers of sys_sync.

If other operations are still running, nothing is committed yet; this one’s reserved log space is released, so it wakes begin_op callers that may now fit. Note what that means: when a file system call returns, its changes are committed only if it was the last outstanding operation. Otherwise they are committed later, when the last one ends.

write_log(): copy modified blocks into the log area

For each block number in the header, take the modified block from the cache and write a copy into the next log block on disk. The home block is still pinned in the cache, so bread(log.dev, log.lh.block[tail]) finds it there without reading the disk. bread for the log block itself may read that block from disk first, though its old contents are immediately overwritten.

Writing the log does not commit anything: until write_head writes the header, the disk’s header still says n == 0, so a crash here leaves these blocks ignored.

A sizing remark: NBUF equals LOGBLOCKS (both 30). If a transaction ever logged 30 blocks, all 30 buffers would be pinned, and the bread of a log block here would find no free buffer and panic in bget. xv6 relies on operations writing far fewer blocks than their reservation allows.

commit(): the four steps

The heart of the protocol, run with no operations outstanding:

1. write_log: the new block contents go to the log area. A crash now loses the transaction, cleanly: nothing has reached a home location.
2. write_head: the header with n > 0 goes to disk. The transaction is now committed. A crash from here on is repaired by recovery at the next boot.
3. install_trans: each block goes to its home location. A crash in the middle is repaired by recovery, which redoes all of them.
4. n = 0 and write_head again: the log is empty. Without this step, the header on disk would still list the old transaction while the next transaction’s write_log overwrote the log blocks; a crash at that moment would make recovery copy the new, uncommitted data to the old blocks’ home locations. A crash before this write only means recovery re-installs blocks that are already in place.

The order matters at every step. Swapping steps 1 and 2 could commit a header that points at log blocks that were never written; installing before the header is written could leave half a transaction in place after a crash, with nothing in the log to finish it. The order on disk equals the order in the code because every bwrite waits for the device to report completion. (Simplified: xv6 assumes that a write the device has reported complete will survive a crash.)

log_write(): record a modified block in the transaction

The file system’s replacement for bwrite, used as the comment shows: modify the buffer, call log_write, then brelse. It writes nothing to disk. It records the block number in log.lh and pins the buffer so it stays in the cache, with its changes, until install_trans has written it home.

Absorption. If the block is already in the list (because this operation, or another one in the same transaction, modified it earlier), nothing new is added. The block is logged once, with its latest contents, no matter how many times it is changed. This matters for blocks that many operations touch, such as the free bitmap and inode blocks, and it keeps the log from filling up.

The two panics catch a transaction that has outgrown the log and a call made outside begin_op/end_op. The first check comes before the absorption search, so it would also fire for a block already in a full log; that is conservative, not wrong.

sys_sync(): wait until earlier changes are on disk

The sync system call (user program user/sync.c). When a file system call returns, its changes may not be committed yet, because the transaction it joined commits only when the last concurrent operation ends (end_op). sync waits for that commit.

If nothing is outstanding or committing, every finished operation’s changes are already on disk and it returns at once. Otherwise it waits for the next commit to finish, by remembering the commit count it must reach and sleeping on &log until end_op increments ncommit past it. That next commit includes every operation currently in progress: a running commit has no outstanding operations, and a pending one includes all operations outstanding now.

It returns 0, as the system-call convention expects from a call that cannot fail.