kernel/fs.c

A map of the file system's layers

xv6’s own overview. Use it as a map, but notice that only three of the five layers are implemented in this file:

• “Blocks” is split: kernel/bio.c caches and reads blocks, while balloc and bfree here decide which blocks are in use.
• “Log” is entirely in kernel/log.c. This file only calls log_write where it would otherwise write a block directly.
• “Files” (inodes), “Directories” and “Names” are here.

One more layer sits on top and is not listed: open files and file descriptors, in kernel/file.c and kernel/sysfile.c.

Headers

Besides the usual kernel headers, this file needs kernel/fs.h (the on-disk structures: superblock, dinode, dirent), kernel/buf.h (the cached block, struct buf), kernel/file.h (the in-memory struct inode), kernel/stat.h (the T_DIR/T_FILE/T_DEVICE type codes), and the two lock headers, because every inode carries a sleep lock and the inode table a spinlock. kernel/proc.h is here for myproc, used to find the current directory.

The in-memory copy of the super block

min is a helper macro used by readi and writei.

sb is the kernel’s copy of the superblock: the disk’s size and where each region (log, inodes, bitmap, data) starts. readsb fills it once at boot and nothing changes it afterwards. The macros IBLOCK and BBLOCK from kernel/fs.h take a superblock argument, and every call in this file passes this global, sb.

As the comment says, a real system would keep one per mounted disk; xv6 has exactly one file-system disk, device ROOTDEV.

readsb(): read the super block from block 1

The disk layout (xv6 file system) puts the boot block at block 0 and the super block at block 1. bread returns a locked, cached copy of block 1; the first sizeof(*sb) bytes are a struct superblock written by mkfs when it built fs.img, so a memmove copies them into the caller’s structure. brelse then gives the buffer back to the cache.

For the default fs.img the values are: size 2000 blocks, 1953 data blocks, 200 inodes, 31 log blocks starting at block 2, inode blocks starting at 33, and the bitmap at block 46 (mkfs/mkfs.c computes them from FSSIZE, LOGBLOCKS and its NINODES).

fsinit(): bring the file system up at boot

Called once, by the first process, from forkret (kernel/proc.c:528). It cannot run from main because reading the disk puts the caller to sleep until the disk interrupt arrives, and only a process can sleep.

The three steps must happen in this order:

1. Read the superblock and check its magic number, FSMAGIC (0x10203040). Any other value means the disk does not hold an xv6 file system, and continuing would interpret random bytes as file-system structures.
2. initlog performs crash recovery: if the previous run crashed after a transaction committed but before it was fully written, the log replays it.
3. ireclaim frees “orphaned” inodes, files that were deleted but still open when the machine went down. It must come after recovery so that it sees the disk in a consistent state.

bzero(): fill a block with zeros

Used only by balloc, so that a newly allocated block never contains leftover data from a file that used it before. The case that needs it is a new indirect block: there a zero entry means “no block”, and leftover bytes would be read as garbage block numbers. balloc does not know what the block will be used for, so it zeroes every block. (For a data block, the old bytes could never be read anyway: xv6 files have no holes, so every byte below size was written first, and readi never reads past size.)

The zeroing happens in the cached copy and is recorded with log_write, not written to disk directly: it becomes part of the current transaction, like every other modification in this file. Note that this bzero is xv6’s own, unrelated to the C library function of the same name.

balloc(): find a free block in the bitmap and claim it

The free bitmap has one bit per block on the disk, including the metadata blocks: bit b is 1 if block b is in use. mkfs/mkfs.c sets the bits of all metadata blocks and of the blocks it filled with files, so a scan from block 0 can never hand out the boot block, the log or an inode block.

One bitmap block holds BPB = 1024 × 8 = 8192 bits. The outer loop steps through the disk 8192 blocks at a time, reading the bitmap block that covers them (BBLOCK); the inner loop tests each bit. The default disk has only 2000 blocks, so there is a single bitmap block and the outer loop runs once.

What stops two processes from claiming the same free block at the same time? The buffer’s sleep lock: bread returns the bitmap block locked, so the test on line 78 and the set on line 79 happen with no other process able to look at that block in between.

Block number 0 doubles as “failure”, which is safe because block 0 is the boot block and is never free.

bfree(): mark a block free again

The inverse of balloc: find the bitmap bit for block b and clear it. b % BPB is the block’s position within its bitmap block; the byte and bit within the byte are computed exactly as in balloc.

Freeing a block that is already free means the file system’s bookkeeping is corrupt (for example, two inodes listing the same block), so the kernel stops with a panic instead of making things worse. bfree does not erase the block’s contents; balloc zeroes blocks when they are handed out again.

Like every change in this file, this one goes through log_write, so the caller must be inside a transaction. Its only caller is itrunc.

What an inode is, and the inode table

An inode is the file system’s record for one file, directory or device. It has no name: names live in directories, which map a name to an inode number. The record holds the type, size, link count (nlink) and the list of blocks with the content, in the on-disk form struct dinode, 64 bytes, 16 per block, starting at block sb.inodestart.

When a process uses an inode, the kernel keeps a copy in memory: a struct inode in the table itable below. The in-memory copy adds fields that are not on disk: ref (how many kernel pointers refer to this entry) and valid (whether the on-disk fields have been read in yet).

The life of an inode, as xv6 describes it

xv6’s comment separates four independent facts about an inode. Keeping them apart is the key to reading the rest of the file:

The typical sequence on lines 152–156 is the pattern you will see everywhere in kernel/sysfile.c. Getting a reference and locking are separate steps on purpose: an open file keeps its reference for as long as it is open but locks the inode only during each read or write, and path lookup (namex) can hold a reference to a directory without holding its lock, which avoids deadlocks (see namex).

One detail is imprecise: lines 131–132 say iput frees the inode when “the reference and link counts have fallen to zero”. The check is made while the caller’s reference is still counted, so the condition is ref == 1 (the caller’s own reference is the last one) and nlink == 0; see line 357.

Lines 144–145 are inaccurate: iput clears valid only when it deletes the inode (line 366, inside if (last)). After an ordinary last iput the entry keeps valid == 1 with ref == 0; iget resets valid when it reuses the entry (line 275).

Which lock protects which field

Two kinds of lock guard the inode table, and each protects different fields:

• itable.lock, a spinlock, protects ref, dev and inum of every entry. These decide which entry holds which inode and whether an entry is free, so they must be read and changed atomically with the search in iget. It is held only for a few instructions and never across disk I/O.
• ip->lock, a sleep lock in each entry, protects everything else: valid and the copy of the on-disk fields (type, size, nlink, addrs…). It may be held for a long time, across disk reads and writes, which is why it must be a lock that sleeps rather than spins.

Holding ip->lock also protects the inode’s content: readi and writei require it, so two writes to the same file never interleave inside one call.

The inode table

NINODE = 50 entries, plus the spinlock that guards their allocation. This bounds how many distinct inodes can be in use at once (open files, current directories, inodes being looked up); iget panics if all 50 are taken.

Despite looking like a cache, it does not keep inodes around after their last reference is dropped: iget only matches entries whose ref is above 0. Repeated lookups are still cheap because the inode blocks stay in the buffer cache.

iinit(): initialize the table's locks

Called once by hart 0 from main. The table itself is in .bss, so every entry already starts with ref == 0 (free) and valid == 0; only the locks need setting up: the table’s spinlock and one sleep lock per entry.

Forward declaration of iget

ialloc below calls iget, which is defined later and is static (private to this file), so it is declared here first.

ialloc(): allocate a fresh inode on disk

Called by create in kernel/sysfile.c when a new file, directory or device is made. It scans the on-disk inodes for one whose type is 0 (free), claims it by writing the new type, and returns an in-memory reference to it.

The scan starts at inode number 1: inode 0 is never used, because a directory entry with inum == 0 means “empty slot”. ROOTINO = 1 is the root directory, which mkfs/mkfs.c allocates first.

As in balloc, the buffer’s sleeplock makes the test and the claim atomic: while this process holds the inode block, no other ialloc can see the same free entry.

The returned inode is referenced but not locked and not yet loaded (valid == 0). The caller’s ilock reads the new contents back from the cached block. Running out of inodes is reported with a message and a return value of 0, and create fails cleanly.

iupdate(): write the in-memory inode back

The in-memory inode is a copy; changing ip->size or ip->nlink does nothing to the disk by itself, and nothing writes the copy back automatically when the entry is recycled. So every function that changes an on-disk field calls iupdate afterwards: writei, itrunc, and sys_link, sys_unlink and create when they change link counts.

It finds the inode’s block with IBLOCK, copies every on-disk field into the dinode slot, and records the block with log_write, so the change becomes part of the caller’s transaction. The caller must hold ip->lock, so that no one changes the fields while they are being copied.

iget(): find or create the table entry for an inode

Returns a pointer to the itable entry for inode inum on device dev, with one more reference counted. It neither locks the inode nor reads it from disk. That keeps iget short enough to run entirely under the itable.lock spinlock, and lets callers like namex and dirlookup obtain a reference without the risk of deadlock that taking the inode’s lock would bring.

In one pass over the table under the spinlock it either finds an entry already in use for this inode, and shares it, or remembers the first free entry (ref == 0) and recycles it. Because the search and the claim happen under the same lock, two processes looking up the same inode at the same time are guaranteed to get the same entry; they can never end up with two separate copies whose fields disagree.

A recycled entry gets valid = 0, so its old contents (from whatever inode it held before) are ignored and the next ilock reads the real ones.

idup(): take one more reference

Adds a reference to an inode the caller already holds a reference to. kfork uses it so the child shares the parent’s current directory (kernel/proc.c:288), and namex uses it to start a relative path lookup from the current directory. The increment is done under itable.lock because ref is one of the fields that lock protects. Returning ip allows the one-line idiom np->cwd = idup(p->cwd).

ilock(): lock an inode, loading it from disk if needed

After ilock returns, the caller has exclusive access to the inode’s fields and content, and those fields are guaranteed to hold the on-disk values.

The lock is a sleep lock because the next lines may wait for the disk, and because callers keep holding it across readi and writei, which do too. If another process holds the lock, acquiresleep puts this one to sleep until it is released.

The first time anyone locks an entry since iget filled it (valid == 0), ilock copies the dinode from its block into the in-memory fields. Doing this here, rather than in iget, means the disk is read only by a process that holds the lock, so two processes never load the same entry at once.

iunlock(): release the inode's lock

Releases the sleeplock, waking any process waiting in ilock. The checks catch callers that unlock an inode they do not hold locked (holdingsleep also checks that the current process is the holder) or that has no references left; both are kernel bugs, so the response is a panic.

ifree(): mark an inode free on disk

Writes type = 0 into the inode’s on-disk slot. From that moment the inode number is free: the next ialloc that scans past it can claim it. Only iput calls this, as the very last step of deleting a file, after itrunc has already released the data blocks. The other on-disk fields are left as they are; ialloc zeroes the whole slot when it reuses it.

iput(): drop a reference, and maybe delete the file

Every iget, idup, ialloc or dirlookup reference is eventually given back with iput. Usually that only decrements ref. But if this was the last reference and no directory entry names the inode any more (nlink == 0), the file has become unreachable: no one has it open and no path leads to it. Then iput frees its data blocks and the inode itself.

That is how a file deleted with rm while some process still has it open survives until the last close: sys_unlink drops nlink to 0, but the open file’s reference keeps ref above 1, so the deletion waits for the final iput.

Because iput may write to the disk, every call must be inside a transaction (begin_op … end_op), even calls that look like plain cleanup, such as in fileclose or kexit.

Truncate first, free the inode number last

The function works in two phases.

Decide (lines 352–358, under itable.lock). Is this the last reference to an unlinked inode? Save dev and inum in local variables for later.

Delete (only if so). Lock the inode, drop the spinlock (the next step sleeps on the disk), and free the data blocks with itrunc. Then take the spinlock again, drop the reference, and only after that clear the on-disk type with ifree.

The order of the last two steps fixes a real bug (xv6 commit d7e85f1). Earlier versions set type = 0 before decrementing ref. In that window another process could ialloc the same inode number, its iget would find this entry, still referenced, and share it, and the two processes’ reference counts would get tangled: the new file could later be deleted with ref still above 1, so its inode was never freed. It stayed allocated but unreachable until a reboot ran ireclaim. Now the inode number becomes allocatable only once this entry is no longer in use.

Everything happens inside the caller’s transaction, so after a crash either all of the deletion is on disk or none of it is.

iunlockput(): the usual way to finish with an inode

Most code paths end with an inode both locked and referenced, so this pair is combined. The order matters: iput may need to lock the inode itself (and assumes no one holds the lock when ref == 1), so the caller’s lock must be released first.

ireclaim(): free inodes orphaned by a crash

Called from fsinit at boot, after log recovery. It looks for inodes that are allocated (type != 0) but have no links (nlink == 0). Such an inode is unreachable and would leak forever. The usual cause is a file that was deleted while still open (see iput) when the machine crashed or was shut down: the unlink was committed, but the final iput that would have freed it never ran. The user programs user/forphan.c and user/dorphan.c create exactly this situation for testing.

For each orphan it reproduces a final close: take a reference with iget, lock it once so that valid becomes 1 (which iput's “last reference” test requires), unlock, and iput. Since ref == 1 and nlink == 0, iput truncates and frees it. Each orphan gets its own transaction.

Note the order on lines 397–399: the inode block is released with brelse before ilock runs, because ilock reads that same block, and a process that tried to lock a buffer it already holds would wait for itself forever.

Where a file's data blocks are listed

A file’s content is a sequence of blocks numbered 0, 1, 2… within the file (its “logical” block numbers). The inode records which disk block holds each one:

• addrs[0] to addrs[11] (NDIRECT = 12 entries) give the disk addresses of the first 12 blocks directly.
• addrs[12] points to an indirect block, a whole disk block filled with NINDIRECT = 1024 / 4 = 256 more block numbers, for logical blocks 12 to 267.

So the largest file is MAXFILE = 268 blocks = 274,432 bytes (268 KiB). An address of 0 means “no block allocated yet”.

bmap(): which disk block holds block bn of this file?

Translates a logical block number bn into a disk block number, allocating blocks on the way if they do not exist yet. readi and writei call it once per block they touch. The caller holds ip->lock and, if allocation may happen, a transaction.

For bn < 12 the answer is in ip->addrs[bn]. Otherwise bn is reduced by 12 to an index into the indirect block, which is itself allocated the first time a file grows past 12 blocks, and then read to find (or record) the data block’s address.

Two kinds of change need recording differently. The indirect block lives in its own disk block, so writing an entry into it needs log_write right here. A change to ip->addrs[] only changes the in-memory inode; bmap does not call iupdate, and relies on its caller to do so (writei always does, see line 573).

When the disk is full, balloc returns 0 and bmap passes the 0 up so the write can stop with a short count.

In practice readi never makes bmap allocate: xv6 files have no holes (see writei), so every block below the file’s size already exists. That matters, because fileread calls readi outside any transaction.

itrunc(): free all of a file's data blocks

Releases every block the inode uses and sets its size to 0. Called by iput when a file is deleted, and by sys_open for O_TRUNC (opening an existing file to overwrite it).

It frees the direct blocks first, then each block listed in the indirect block, then the indirect block itself. The indirect block must be read before it is freed, since it holds the list. Every entry is reset to 0 so the inode no longer claims blocks that may soon belong to another file, and iupdate writes the emptied inode back.

All of this is one transaction, so it is crash-safe: either all of the free bitmap updates and the new inode reach the disk or none do. It stays small on the default disk because the single bitmap block is logged only once, however many bits change (the log’s “absorption” of repeated writes to a block).

stati(): fill in a struct stat

Copies the inode’s public metadata into a struct stat, the structure the fstat system call returns to user programs (filestat). Note that the device numbers major/minor and the block list are not included. The caller holds the lock, so the five fields are a consistent snapshot.

readi(): read bytes from a file

Reads up to n bytes starting at byte offset off of the inode, into either a user address (for read) or a kernel address (for dirlookup and kexec). It returns the number of bytes read, 0 at or past the end of the file, or -1 if copying to the destination failed.

The loop handles one block per iteration. The first and last blocks may be partial: a read of 100 bytes at offset 1000 takes 24 bytes from the end of block 0 and 76 from the start of block 1. For each block it maps the logical block to a disk block (bmap), gets it from the buffer cache, copies the needed piece with either_copyout, and releases the buffer at once, so the loop never holds more than one buffer.

writei(): write bytes into a file

The mirror image of readi, with three differences:

• It may grow the file: bmap allocates missing blocks, and line 571 extends the size. It can write at the end of the file but not past it (line 549), so a file never has holes, gaps of unallocated blocks below its size.
• Every modified block goes to log_write rather than to the disk, so the caller must be inside a transaction, and the transaction must have room for all the blocks one call can touch. That is why filewrite splits large writes into chunks.
• It reports partial success: it returns how many bytes it wrote, which is less than n if the disk filled up or the source address was bad. Callers treat a short count as an error.

The caller holds ip->lock, which keeps two writers from interleaving inside the same file and keeps the size consistent.

namecmp(): compare two file names

Directory entry names are at most DIRSIZ = 14 bytes and are not NUL-terminated when they use all 14 (see dirent). strncmp with a limit of DIRSIZ handles both cases: it stops at a NUL or after 14 characters, whichever comes first. A consequence is that names are only compared on their first 14 characters, so abcdefghijklmnop and abcdefghijklmnXY count as the same name.

dirlookup(): find a name in a directory

A directory is an ordinary inode of type T_DIR whose content is an array of 16-byte dirent records: a 2-byte inode number and a 14-byte name. Looking up a name means reading the records one by one with readi and comparing names. Records with inum == 0 are empty slots left by deleted entries.

On a match it returns the named inode via iget: referenced but not locked. The caller holds dp’s lock, and the name might be ., which refers to dp itself; locking the result here would then deadlock. If poff is not null, the entry’s byte offset is stored there, which sys_unlink uses to erase the entry.

The caller must hold dp’s lock. Directory sizes are always a multiple of 16 bytes, so a short read means the directory is corrupt and the kernel panics.

dirlink(): add a name to a directory

Adds the entry (name, inum) to directory dp. Used by create (for the new name and, in a new directory, for . and ..) and by sys_link.

1. Refuse duplicates: if the name is already there, give back the reference that dirlookup took and fail.
2. Find a slot: the first empty entry (inum == 0), or, if there is none, the offset just past the end, off == dp->size.
3. Write the entry with writei. Writing at the end grows the directory by 16 bytes, which may allocate a new block; if the disk is full, writei returns a short count and dirlink fails instead of panicking.

dirlink does not touch the target inode’s link count (nlink); its callers adjust nlink themselves. The caller must hold dp’s lock and be inside a transaction.

skipelem(): split off the next path element

A path name like /a/bb/c is a sequence of elements separated by slashes. skipelem copies the next element into name and returns the rest of the path with the separating slashes removed. xv6’s examples, plus two more:

Because trailing slashes are skipped, the caller can test *path == '\0' to know that the element just copied was the last one; namex relies on this.

Elements longer than DIRSIZ are silently cut to 14 bytes and then fill name completely, with no terminating NUL. That is why name must have room for DIRSIZ bytes and why names are compared with namecmp, which never reads past 14.

namex(): walk a path, one directory at a time

The engine behind namei and nameiparent. It starts at the root directory (absolute path) or the current directory (relative path), and for each element locks the current directory, checks it, looks up the element, and moves to the result. Following /a/b: start at /, find a in it, find b in a, return b.

Notice the hand-over on lines 716–721: dirlookup returns next referenced but unlocked, then the current directory is unlocked and released before next is locked on the following iteration. The walk never holds two inode locks at once, and that avoids two deadlocks:

• Looking up . returns the directory itself. Locking next while still holding ip’s lock would mean waiting for a lock this process already holds.
• Looking up .. goes from child to parent, the opposite order of a process walking down from parent to child. If both held one lock and waited for the other, neither could proceed.

The reference that dirlookup took on next is what keeps it safe in the gap: while referenced, its table entry cannot be recycled and its blocks cannot be freed.

With nameiparent set, the walk stops one level early and returns the parent directory, with the final element left in name. Callers that create or remove a name (create, sys_unlink, sys_link) need exactly that.

Its iput calls may free an inode, so namex must run inside a transaction. The one exception is userinit's namei("/") at boot, which returns before any iput.

namei() and nameiparent(): the public entry points

namei returns the inode a path names, referenced and unlocked, or 0 if any part of the path does not exist or is not a directory. It still needs a buffer for the elements namex copies out, so it provides a local one of DIRSIZ bytes.

nameiparent returns the inode of the directory that would contain the path’s last element, and copies that element into the caller’s name, which must have room for DIRSIZ bytes. For /a/b it returns /a and sets name to b.