kernel/fs.h

Two basic constants

ROOTINO is the inode number of the root directory /. Inode numbers start at 1, and number 0 is never used: in a directory entry, inode number 0 marks an empty slot. mkfs allocates the root first, so it gets number 1, and asserts that it did.

BSIZE is the size of a file system block, 1024 bytes. The disk hardware works in 512-byte sectors, so one block is two sectors, which the driver accounts for (kernel/virtio_disk.c:218). (The comment “1 fs block = 1 disk sector” in mkfs/mkfs.c is therefore not true of the device; it is true only of mkfs’s own file I/O, which writes fs.img in 1024-byte units.)

The disk layout

The disk is a sequence of numbered 1024-byte blocks, divided into regions in this order. mkfs decides how big each region is and records the boundaries in the superblock. For the default fs.img (FSSIZE = 2000 blocks, 200 inodes, LOGBLOCKS = 30) mkfs prints nmeta 47 (boot, super, log blocks 31, inode blocks 13, bitmap blocks 1) blocks 1953 total 2000, which gives:

block:  0      1       2 ........ 32   33 ...... 45    46       47 ............ 1999
      +------+-------+-------------+---------------+--------+---------------------+
      | boot | super |     log     |    inodes     | bitmap |     data blocks     |
      +------+-------+-------------+---------------+--------+---------------------+
                       1 header +    13 blocks of    1 block     1953 blocks
                       30 blocks     16 inodes       (2000 bits
                                                     used)

• Block 0, the boot block, is not used: QEMU loads the kernel directly from the kernel file, not from this disk.
• Block 1, the superblock, describes the layout (below).
• Blocks 2–32, the log: one header block and 30 blocks for logged block contents (kernel/log.c).
• Blocks 33–45, the inodes: 200 / 16 + 1 = 13 blocks of 16 dinode structures. That is room for 208; numbers 1–199 are usable (ialloc searches below ninodes, and inode 0 is never allocated).
• Block 46, the free bitmap: one bit per block of the whole disk, 1 meaning “in use”. One block holds 8192 bits, enough for 2000 blocks. mkfs marks all the metadata blocks, and the data blocks it filled, as in use.
• Blocks 47–1999, data blocks: file contents, directory contents and indirect blocks.

All of these numbers can be read back from fs.img: its block 1 holds the superblock fields 2000, 1953, 200, 31, 2, 33 and 46.

The superblock

Block 1 of the disk holds this struct (in its first 32 bytes). It is how the kernel learns the layout instead of hard-coding it: readsb reads it at boot, fsinit checks the magic number, and the rest of the file system uses the global copy sb. See superblock.

For the default fs.img the values are: size 2000, nblocks 1953, ninodes 200, nlog 31, logstart 2, inodestart 33, bmapstart 46.

There is no field for where the data blocks start; it follows from the others (bmapstart plus the number of bitmap blocks). balloc does not need it, because every metadata block is already marked in use in the bitmap.

The magic number

mkfs writes 0x10203040 into the superblock’s magic field, and fsinit panics with “invalid file system” if it does not find it. It catches a disk that does not hold an xv6 file system at all. The value is arbitrary; it only needs to be unlikely to appear by accident.

How big a file can be

An inode holds NDIRECT (12) block numbers directly, plus the number of one indirect block, a block filled with further block numbers. A block number is a 4-byte uint, so an indirect block holds NINDIRECT = 1024 / 4 = 256 of them.

So a file has at most MAXFILE = 12 + 256 = 268 blocks, which is 274,432 bytes (268 KiB). writei refuses to write past that (kernel/fs.c:551).

NLINK_MAX is the largest value a short can hold, 32767. nlink in dinode is a short, so sys_link and create refuse to add a link that would make it overflow (kernel/sysfile.c:145).

The on-disk inode

Every file, directory and device has one dinode in the inode region; its inode number is its index there. This is the on-disk form; the kernel keeps an in-memory copy with extra bookkeeping in struct inode (kernel/file.h). See dinode (on-disk inode).

The struct is 2 + 2 + 2 + 2 + 4 + 13 × 4 = 64 bytes with no padding, so 1024 / 64 = 16 fit exactly in one block, and none straddles a block boundary. mkfs asserts that BSIZE is a multiple of the struct’s size.

type 0 means the inode is free. The other values (T_DIR, T_FILE, T_DEVICE) are in kernel/stat.h.

Find the block holding an inode

IPB is the number of inodes per block: 1024 / 64 = 16.

IBLOCK gives the disk block that contains inode i: the inodes are stored in order starting at block sb.inodestart, 16 per block, so inode i is in block i / 16 + 33 (for the default image). Within that block it is entry i % IPB, which is how ialloc and iupdate find it (kernel/fs.c:209).

The macro writes sb.inodestart, so its second argument must be a struct (like the kernel’s global sb), not a pointer to one. The parentheses around i keep an argument such as inum + 1 from being split by operator precedence.

Find the bitmap bit for a block

BPB is the number of bits in one bitmap block: 1024 × 8 = 8192. Bit b of the bitmap (counting from the start of the first bitmap block) records whether block b of the disk is in use.

BBLOCK gives the bitmap block that contains block b’s bit. With 2000 blocks it is always block 46, sb.bmapstart. Within that block the bit is number b % BPB, which balloc and bfree address as byte bi / 8, bit bi % 8.

Directory entries

A directory is stored like a file: its data blocks contain an array of dirent records. Each maps a name to an inode number. See directory.

Each entry is 16 bytes: a 2-byte inode number and a 14-byte name, so 64 entries fit in a block. inum == 0 marks an unused slot (inode 0 is never allocated), which is how dirlink finds room for a new entry and dirlookup skips empty slots.

Names are at most DIRSIZ (14) characters. As the comment says, a name of exactly 14 characters fills the array and has no terminating NUL, so code must never treat name as an ordinary C string; namecmp compares with strncmp limited to DIRSIZ. The attribute nonstring tells GCC the same thing, so it does not warn when strncpy fills the array without a NUL.