mkfs/mkfs.c

The host's C library

These are your computer’s own headers, from its C library: stdio.h for printf and perror, unistd.h for lseek, read, write and close, fcntl.h for open and its O_ flags, assert.h for assert. None of them exist inside xv6; that alone tells you this program is built for the host. string.h also brings in the old BSD functions bzero, bcopy and index used below (on both glibc and macOS it includes strings.h, where they are declared).

Borrow the on-disk format from the kernel

kernel/types.h supplies uint, ushort and uchar; kernel/fs.h the layout constants and the structs superblock, dinode and dirent; kernel/stat.h the inode types T_DIR and T_FILE; kernel/param.h the sizes FSSIZE and LOGBLOCKS. Because mkfs and the kernel compile the very same definitions, they cannot disagree about where a field sits on disk (as long as the host’s int is 4 bytes, which line 81 checks).

A fallback for static_assert

static_assert checks a condition at compile time. With C11 or C17, <assert.h> defines static_assert as a macro for _Static_assert (Apple’s headers do this even in C23 mode; you can see it with gcc -E), so #ifndef static_assert is false and lines 15–20 are skipped.

In C23 static_assert became a keyword, and glibc no longer defines a macro for it when GCC 13 or later compiles in C23 mode, which is GCC 15’s default. So on a current Linux system (including the Ubuntu CI job) the replacement below is what actually runs, as it also would with a pre-C11 compiler; defining a macro with a keyword’s name is allowed, because the preprocessor runs first. The replacement is a classic trick: switch (0) with two labels, case 0: and case (a):. If the condition a is true, the second label is case 1: and the code compiles (and does nothing when run). If a is false, it becomes a second case 0:, and duplicate case labels are a compile error (“duplicate case value”), which is the assertion failing. The message b is ignored, and because the trick is a statement, it only works inside a function, which is where line 81 uses it. The do { ... } while (0) makes the macro behave as one statement followed by a semicolon.

How many inodes

The image gets room for 200 inodes, so xv6 can hold at most 199 files and directories (inode 0 is never used). This number ends up in the superblock’s ninodes, which the kernel’s ialloc uses as its limit.

The size of each region

The comment lists the regions of the disk layout (xv6 file system) in order, the same picture as in kernel/fs.h:7. These globals compute how many blocks each region needs. With the default parameters:

Global initializers in C must be constant expressions; these are, because every name in them is a macro. nmeta and nblocks are computed at run time in main (lines 96–97).

The + 1 in the first two is a cheap way to round up, but it always adds a block, even when the division is exact. With these numbers nothing is lost except some unused space: 13 inode blocks hold 208 inodes, of which only 200 are counted.

The state of the image being built

• fsfd is the host file descriptor of the open fs.img.
• sb is the superblock, filled in by main and also used by winode and rinode through IBLOCK, which reads sb.inodestart.
• zeroes is one block of zero bytes (a global array is zero-initialized).
• freeinode is the next inode number to hand out. It starts at 1, so the first inode allocated, the root directory, gets ROOTINO.
• freeblock is the next data block to hand out; main sets it to the first block after the metadata.

Together freeinode and freeblock are the whole allocator: mkfs only ever counts upward. That is enough because it creates files once and never deletes anything.

Forward declarations

Prototypes for the helpers defined after main, so that main can call them with their argument types checked. Note that these are mkfs’s own balloc and ialloc, unrelated to the kernel functions of the same names (balloc, ialloc); this is a separate program, so the names do not clash.

xshort: store a 16-bit number in RISC-V byte order

The kernel will read fs.img on a little-endian RISC-V machine, so every number mkfs writes must be laid out little-endian: low byte first. See byte order (endianness).

Rather than test which kind of machine it is running on, xshort builds the result byte by byte. a points at the two bytes of y; byte 0 gets the low 8 bits of x (the assignment to a uchar keeps only those), byte 1 gets the high 8 bits. Whatever the host’s own byte order, y now sits in memory in little-endian order, which is what gets copied into the image.

On a little-endian host (x86-64, ARM Macs, almost every computer today), y ends up equal to x and the function changes nothing. On a big-endian host it swaps the two bytes. The same function also converts back: iappend calls xint on values read from the image to get host numbers.

xint: store a 32-bit number in RISC-V byte order

The 4-byte version of xshort: byte 0 of y gets bits 0–7 of x, byte 1 bits 8–15, byte 2 bits 16–23, byte 3 bits 24–31. Swapping is its own inverse, so the same function converts a host number to disk order and a disk number back to host order.

The conversion is not applied everywhere it would be needed on a big-endian host: sb.magic (line 99) is stored without it, and IBLOCK in winode and rinode, and wsect(sb.bmapstart, ...) in balloc, use the converted superblock fields as if they were host numbers. On a big-endian host the image would therefore come out wrong. On the little-endian hosts everyone actually uses, every conversion is the identity and none of this matters.

main: local variables

argv[1] is the image to create and argv[2] onward are the files to copy into it. buf holds one block at a time, de one directory entry (dirent), din one on-disk inode (dinode). rootino will be the root directory’s inode number, inum each file’s, off a byte offset.

Insist on 4-byte ints

The on-disk structures use uint, which kernel/types.h defines as unsigned int, and the kernel’s uint is 4 bytes. If the host’s int were a different size, superblock and dinode would have a different layout in mkfs than in the kernel, and xint would only handle part of each number. This refuses to compile in that case instead of writing a corrupt image.

Check the command line

At least the image name is required. With only that, mkfs would build a file system containing nothing but an empty root directory.

Inodes and directory entries must tile a block

A dinode is 64 bytes and a dirent 16, so both divide 1024 evenly: a block holds exactly 16 inodes or 64 directory entries, and none straddles two blocks. winode and rinode read one block and index into it, which would break if an inode could cross a block boundary, and the kernel’s IBLOCK makes the same assumption. These are run-time asserts, checked when mkfs runs, although the compiler could have checked them too.

Create the image file

This is the host’s open: create fs.img if it does not exist (O_CREAT), empty it if it does (O_TRUNC), open it for reading and writing (O_RDWR, because rsect reads back what wsect wrote). 0666 is the permission for a new file, reduced by your umask (usually to 0644). On failure die prints the reason, such as “Permission denied”.

Count the metadata blocks

nmeta is everything before the data region: the boot block and superblock (2), the log, the inode blocks and the bitmap. With the defaults that is 2 + 31 + 13 + 1 = 47, leaving nblocks = 2000 − 47 = 1953 data blocks.

The comment on line 95 is misleading. A file system block is 1024 bytes and the disk device uses 512-byte sectors, so one block is two sectors; the kernel’s driver multiplies by 2 (kernel/virtio_disk.c:218). What is true is that mkfs’s own helpers, despite being called wsect and rsect, work in 1024-byte blocks.

Fill in the superblock

These are the fields readsb will read at boot, describing the layout (see superblock). For the default image:

Each value is passed through xint to put it in RISC-V byte order, except magic (see the note on xint for why that is harmless in practice). Running mkfs and reading back block 1 of the image gives exactly these numbers.

Report the layout

mkfs prints one line during make:

nmeta 47 (boot, super, log blocks 31, inode blocks 13, bitmap blocks 1) blocks 1953 total 2000

It is worth reading when you change FSSIZE, LOGBLOCKS or NINODES: it shows how the regions moved.

Data allocation starts after the metadata

Block 47 is the first data block, so it is the first one iappend hands out. Since blocks are allocated in order and never freed, after mkfs is done the blocks in use are exactly 0 to freeblock − 1, which is what balloc relies on at the end.

Zero the whole image

Write 2000 blocks of zeros. This does two jobs. It makes fs.img exactly 2000 × 1024 = 2,048,000 bytes, the size QEMU presents as the disk. And it gives every block known contents: later, rsect reads blocks that have not been written yet (a fresh data block, a fresh indirect block) and relies on them being zero. Without this loop such reads would run past the end of the file, return fewer than 1024 bytes, and mkfs would stop with “read”. Zero also means “free” everywhere in the format: a zero inode type is a free inode, a zero block address is “no block yet”.

Block 0, the boot block, is left as zeros forever; xv6 does not use it.

Write the superblock into block 1

The struct is only 32 bytes, but wsect always writes a whole block, so it is copied into the start of a zeroed 1024-byte buffer first. Copying sb straight to the disk would also have written 992 bytes of whatever followed it in memory.

Create the root directory's inode

The first ialloc call gets inode number 1, which the kernel expects to be the root directory / (ROOTINO); namex starts every absolute path there. The assert documents and enforces that ordering: if someone allocated another inode first, mkfs would stop instead of producing an image whose / is a regular file.

Give the root its "." and ".." entries

A directory is a file whose content is an array of dirent records (a 2-byte inode number and a 14-byte name). Every xv6 directory starts with two entries: ., naming the directory itself, and .., naming its parent. The root has no parent, so both point at inode 1; cd .. in / stays in /. The kernel creates the same two entries for a new directory in create (kernel/sysfile.c:302), and isdirempty skips them when deciding whether a directory can be removed.

bzero clears the whole entry first, so the bytes after the name are zero (the kernel compares names with namecmp, which stops at a NUL or after 14 bytes). xshort puts the inode number in disk byte order. iappend adds the 16 bytes at the end of the root directory’s content; the first call allocates block 47 for it.

Copy each file into the image

The loop handles every remaining argument: README and the user programs user/_cat, user/_sh, and so on (UPROGS).

Names in the image have no directory part. All files go straight into /, because mkfs has no code for creating subdirectories. So the user/ prefix is dropped, and the assert stops mkfs if a name still contains a / (for example if someone added user/tests/_x to the Makefile). index is the old BSD name of strchr: it returns a pointer to the first /, or 0 if there is none.

open(argv[i], 0) opens the host file read-only (O_RDONLY is 0). Note that the original name, with user/, is the one opened: only the name written into the image is shortened.

Drop the leading underscore

As the comment says, the Makefile names the compiled programs _cat, _rm and so on (Makefile:106) so that, on your computer, nothing (a shell, a script) mistakes user/_rm for the system’s rm. Inside xv6 the program is called rm, so the _ is removed here. shortname += 1 moves the pointer past the first character.

The name must then fit in DIRSIZ (14) characters, the size of the name field of a dirent. Exactly 14 is allowed: the name is then stored without a terminating NUL, which the kernel handles (see kernel/fs.h:56).

Allocate the file's inode and link it into /

ialloc creates a regular-file inode (T_FILE) with link count (nlink) 1: the one directory entry added right after. The entry is built like the . and .. entries and appended to the root directory. strncpy copies at most 14 bytes and, because de was zeroed, a shorter name is NUL-padded.

With the default build, the files get inode numbers in command-line order: README is 2, cat 3, echo 4, and so on up to sync, 22.

Copy the file's contents

Read the host file 1024 bytes at a time and append each chunk to the new inode with iappend, until read returns 0 (end of file). The last chunk is usually shorter; cc is the byte count actually read, so the file’s size in the image is exactly its size on your computer. A read error (-1) also ends the loop, silently.

Round the root directory's size up to a whole block

After the loop the root directory holds 2 + 21 entries of 16 bytes, so its size is 368. These lines round size up to the end of its block, 1024. The slots beyond the real entries are zero, and an entry with inode number 0 means “empty slot” to the kernel. So / now looks like a directory with 41 free slots, and dirlink, which scans 0 .. size for an empty slot before appending (kernel/fs.c:633), fills them before growing the directory. xv6 does not say why it does this; the kernel would work without it, since it writes at offset size when no slot is free.

The formula always adds a block: if the entries had exactly filled a block, size would grow past the blocks actually allocated. With 64 entries per block that does not happen with the default file list.

rinode and winode read and write the inode, and xint converts the size both ways.

Write the free bitmap and finish

All allocation is done, so balloc can mark blocks 0 to freeblock − 1 as used in the free bitmap. With the user programs built here mkfs prints balloc: first 1006 blocks have been allocated: 47 metadata blocks and 959 blocks of directory, file data and indirect blocks. The exact count depends on how large your compiler makes the programs.

exit(0) closes fsfd and tells make that the image was built.

wsect: write one block of the image

Writes 1024 bytes from buf as block number sec: move the file offset to sec × 1024 with lseek (the 0 is SEEK_SET, “from the start of the file”), then write. Despite the name, sec is a file system block number, not a disk sector. Any failure, including a short write, stops mkfs through die; there is no point continuing with a damaged image.

The kernel’s equivalent is bwrite, which goes through the buffer cache and the disk driver. mkfs needs none of that: the disk is an ordinary file on the host.

winode: write one on-disk inode

An inode is only 64 bytes, but the image is read and written in whole blocks, so writing one inode is read-modify-write: IBLOCK finds the block holding inode inum (inum / 16 + 33 by default), rsect reads it, the inode is copied into slot inum % 16, and wsect writes the block back. Reading first is what keeps the other 15 inodes in that block intact.

ip must already be in disk byte order; callers convert the fields with xint/xshort before calling. The kernel does the same job in iupdate.

rinode: read one on-disk inode

The reverse of winode: read the block that holds inode inum and copy the 64 bytes of slot inum % 16 out. The result is still in disk byte order, which is why callers wrap its fields in xint.

rsect: read one block of the image

The reading twin of wsect: seek to sec × 1024 and read 1024 bytes into buf. A short read means the block lies beyond the end of the file, which cannot happen once main has zeroed all 2000 blocks; if it did, mkfs stops with “read”.

ialloc: hand out the next inode

Takes the next unused inode number and writes a fresh dinode for it: the given type, link count (nlink) 1, size 0, and (from bzero) no data blocks and device numbers 0. Each field is converted to disk byte order.

There is no check against NINODES. A file that got inode number 200 or more would lie beyond the ninodes the superblock declares (the kernel’s ialloc and ireclaim only look below it), and from number 208 on its inode would be written into the bitmap block. With 22 inodes used by default this is far away.

Compare the kernel’s ialloc, which has to search the inode blocks for one whose type is 0, because inodes are freed and reused at run time.

balloc: write the free bitmap

Called once, at the end, with the number of blocks used. Because mkfs allocates blocks strictly in order, “used” is exactly the blocks 0 .. used − 1: the metadata plus everything iappend handed out. The loop sets bit i % 8 of byte i / 8 for each of them, the same bit numbering the kernel’s balloc and bfree use (kernel/fs.c:77). So the kernel will never allocate a block that already holds metadata or file data.

Only one bitmap block is written, at sb.bmapstart (46). The assert checks that one is enough: a block has BPB = 8192 bits. The rest of the bitmap is zero (free) from the initial zeroing.

Despite its name, this is not an allocator like the kernel’s balloc; the allocating is done by freeblock++ in iappend.

A min macro

The smaller of two values, used by iappend. Each argument is parenthesized so that expressions like (fbn + 1) * BSIZE - off are evaluated as a whole. As with any such macro, an argument is evaluated twice, so it must not have side effects.

iappend: add bytes at the end of a file

Appends n bytes from xp to the end of inode inum, allocating blocks as needed. Every write into the image (directory entries and file contents) goes through here.

It reads the inode once into din and works on that copy, updating din.addrs as it allocates blocks, and writes it back once at the end. off is the current file size, which is where the new bytes go. indirect is exactly one block in size (256 four-byte block numbers), so a whole indirect block can be read into it.

Find (or allocate) the block for the current offset

Each pass of the loop handles the part of the data that falls in one file block. fbn (“file block number”) is which block of the file the offset off is in; the job is to turn it into a block number on the disk, x. This is the same mapping the kernel’s bmap does, written for mkfs.

• Blocks 0–11 (NDIRECT) are listed directly in din.addrs[fbn]. A 0 entry means the block has not been allocated, so the next free block is taken.
• Blocks 12–267 are listed in the indirect block, whose own number is in din.addrs[NDIRECT]. That block is allocated the first time it is needed (it is already zero from the initial zeroing, so it starts out as 256 empty entries). Then it is read, and if entry fbn − 12 is 0, a data block is allocated and the updated indirect block written back at once.

The assert stops at MAXFILE = 268 blocks (274,432 bytes), the largest file the format can describe. The biggest program, usertests, needs 205 blocks.

Because of the allocation order, a large file is laid out as 12 data blocks, then its indirect block, then the rest of its data. In the default image, README gets blocks 48–50, cat blocks 51–62, its indirect block is 63, and its remaining data starts at 64. Comparing entries with 0 needs no xint, since 0 is 0 in either byte order.

Copy into that block

n1 is how many bytes go into this block: all that is left (n), or the room up to the end of the block, (fbn + 1) × 1024 − off, whichever is smaller. The block is read, the bytes are copied in at offset off − fbn × 1024 within it, and it is written back. Reading first matters when the append starts in the middle of a block that already holds data, as with the second and later directory entries.

bcopy(src, dst, n) is the old BSD form of memmove with the source and destination swapped. Then the counters advance and the loop handles the next block, if any.

Save the new size and block list

Write the inode back with the new size and any block numbers added to din.addrs. (Numbers added to the indirect block were already written by line 286.)

die: report a host error and stop

perror prints s, a colon and the description of the last failed system call (from errno), for example fs.img: Permission denied. Exiting with status 1 makes make stop and report that building fs.img failed. The partly written image is left behind (make deletes a failed target only if the Makefile asks for that with .DELETE_ON_ERROR, and xv6’s does not). Because that file is newer than its inputs, a second make may consider it up to date; rm fs.img forces a rebuild.