14 File system
A file system is a mechanism by which the raw bytes of a storage device are managed meaningfully. A group of bytes at specific locations on the device is allocated for a purpose, e.g. storing an ASCII document, and later exactly those bytes can be retrieved. A file system manages many such groups of bytes. It is helpful to think of a file system as a database that maps high-level information to specific locations on a disk, in the same way that a business record is mapped to a specific row of a table. The high-level information that a file system deals with is organized as files and directories.
| A database table | A file system |
|---|---|
| a row holds one record | a file holds one document, program, image… |
| each row has a primary key | each file has an inode number |
| columns describe the record (name, date, owner) | metadata describes the file (size, owner, timestamps) |
| the data lives in pages of a fixed size on disk | the content lives in blocks of a fixed size on disk |
| an index maps keys to pages | a directory maps names to inode numbers, an inode maps the file to its blocks |
| a catalog describes the tables themselves | a superblock describes the file system itself |
| a query language finds records | a path like /bin/hello finds a file |
A file is an entity with two components: metadata and the actual raw data. Metadata is the information that describes the properties of the raw data associated with the file; the raw data is the real content of the file. A directory is a file that holds a group of files and child directories. Together, they create the file hierarchy familiar from Windows or Linux.
14.1 Example: the ext2 file system
Many file systems exist, and they differ enormously: FAT, which every
USB stick carries, keeps the “which blocks belong to this file”
information in one big table at the start of the disk; NTFS and ext4
keep journals so that a power failure leaves the disk consistent; ZFS
and Btrfs checksum everything and never overwrite data in place. In this
chapter we implement a reader for ext2, the second extended
file system, the Linux file system of the 1990s and the ancestor of
ext3 and ext4. We choose it because it is simple, because it is
documented in one readable document, and because the tools to create and
inspect it (mke2fs, debugfs,
dumpe2fs, from the e2fsprogs package) are on
every Linux machine and in our container. A kernel that reads ext2 can
read a disk prepared by Linux, which is a satisfying thing to be able to
say.
This chapter closes the loop that Part II opened. In chapter 7,
Bootloader, and chapter 9, Protected mode and x86 descriptors, the BIOS
read the kernel from disk for us. In chapter 13, Processes, the kernel
ran user programs, but they were compiled into the kernel image, in a
special .user section, because the kernel had no other way
to get at them. By the end of this chapter the kernel reads the disk
itself, finds /bin/hello on an ext2 file system, loads it
as an ELF file, the way chapter 5, The Anatomy of a Program, described
the format, and runs it in ring 3. Three layers are stacked for that: a
disk driver, a file system, and a program loader. We build them
bottom-up. Then, because a file system that cannot be written to is only
half of one, the kernel writes a file of its own, and we let the real
e2fsck judge the result.
14.1.1 Running this chapter’s code
The code is in code/chapter14/os of the book’s
repository. Everything runs in the toolchain container of chapter 0 and
appendix A, started from the root of the repository so that the test
script in tools/ is reachable:
$ docker run --rm -it --user "$(id -u):$(id -g)" --security-opt seccomp=unconfined -v "$PWD":/work -w /work/code/chapter14/os os01Inside it, make builds the bootloader, the kernel, the
two user programs and build/disk.img, an 8 MiB disk image
with an ext2 file system on it. make qemu boots the image
with the CPU stopped at its first instruction and a gdb stub on port
26000; make gdb in a second terminal (a second
docker exec into the same container) connects to it, loads
the kernel’s symbols and breaks at kmain.
make test is what the book’s continuous integration runs:
it boots the image headless with the serial port captured to a file,
waits for the greeting of the user program, for the line the kernel
reads back from the file it wrote, and for the kernel’s final message,
then runs e2fsck on the file system to check that what the
kernel wrote is a file system Linux would mount. make clean
removes build/.
14.2 Talking to the disk: ATA
14.2.1 A little history
The hard disk interface of the PC comes from the IBM PC/AT of 1984,
whose disk controller card lived at I/O ports
0x1F0-0x1F7. In 1986, Compaq and Western
Digital moved the controller onto the drive itself, which is why the
interface was called IDE, Integrated Drive Electronics, and the
cable that remained between the drive and the motherboard carried the
same register interface as the old card. ANSI standardized it in 1994 as
ATA, AT Attachment; ATAPI added a way to send
SCSI-style packets to CD-ROM drives over the same cable; the revisions
up to ATA/ATAPI-7 added faster transfer modes, 48-bit addressing and
DMA. Serial ATA replaced the 40-pin ribbon cable with a thin serial link
in 2003, and today’s NVMe drives do not speak ATA at all. But the
register interface of 1984 is still the one a PC emulates when it boots,
and it is what QEMU gives us, so it is what we program. The
specification we refer to is ATA/ATAPI-6 (ANSI INCITS
361-2002), freely available as the T13 committee’s working draft; the
register descriptions are its section 7 and the commands its section 8.
The OSDev wiki page “ATA PIO Mode” is a compact practical summary and is
the second reference the code cites.
14.2.2 The registers
An ATA bus (or channel) has at most two drives, master and slave, and a PC has traditionally two buses, primary and secondary. Each bus is driven through two small groups of I/O ports: the command block, eight consecutive ports, and the control block, one port. For the primary bus the legacy addresses are:
| Port | Read | Write |
|---|---|---|
0x1F0 |
data (16-bit) | data (16-bit) |
0x1F1 |
error | features |
0x1F2 |
sector count | sector count |
0x1F3 |
LBA bits 7:0 | LBA bits 7:0 |
0x1F4 |
LBA bits 15:8 | LBA bits 15:8 |
0x1F5 |
LBA bits 23:16 | LBA bits 23:16 |
0x1F6 |
drive/head | drive/head |
0x1F7 |
status | command |
0x3F6 |
alternate status | device control |
The same port has a different meaning when read and when written:
writing 0x1F7 sends a command, reading it returns
the status. The specification calls
0x1F3-0x1F5 the Sector Number, Cylinder Low
and Cylinder High registers, their names from the days of
cylinder/head/sector addressing (chapter 7); in LBA mode they simply
hold three bytes of the block address, with the top four bits of a
28-bit address in the low nibble of the drive/head register
(ATA/ATAPI-6, section 7.7, “Device register”). 28 bits of 512-byte
sectors is 128 GiB; the 48-bit addressing of larger disks uses the same
registers twice and we do not need it.
The status register (section 7.15.6) is the one we read most. Its bits:
| Bit | Name | Meaning |
|---|---|---|
| 7 | BSY |
busy: the drive is working, no other bit is valid |
| 6 | DRDY |
drive ready |
| 5 | DF |
device fault |
| 4 | DSC |
obsolete (seek complete), still set by most drives |
| 3 | DRQ |
data request: the drive is ready to transfer data |
| 0 | ERR |
error: the error register says what went wrong |
Reading the status register has a side effect: it clears the
interrupt the drive raised when it finished a command. The alternate
status register at 0x3F6 returns the same byte without
that side effect (section 7.3), which is why the driver reads it to
waste time and reads 0x1F7 only when it means it.
PIO mode, Programmed Input/Output, means that the CPU moves
the data itself, one 16-bit word at a time through the data register at
0x1F0: 256 in instructions for one sector.
This is the slowest way to read a disk; real kernels program the
controller’s DMA engine and let it write memory directly, then wait for
an interrupt. PIO needs no controller setup, no interrupt and no DMA
buffer, which is why every bootloader and most teaching kernels use it,
and why we do.
14.2.3 Port I/O for a
sector at a time: insw
Chapter 10, Talking to devices, wrote inb and
outb in io.h. Reading 256 words with a loop of
inw works, but x86 has a string instruction for exactly
this: rep insw reads ECX words from the port
in DX into memory at ES:EDI, incrementing
EDI as it goes (Intel SDM Volume 2A, “INS/INSB/INSW/INSD”).
One line is added to io.h:
os/io.h (addition)
/* REP INSW reads `count` 16-bit words from `port` into memory at ES:EDI,
advancing EDI (Intel SDM Vol. 2A, "INS/INSB/INSW/INSD"). The ATA data
register is read this way, 256 words per sector (chapter 14). "D" is
the EDI register, "c" ECX; "+" says the registers are both read and
modified, so the compiler does not reuse their old values. */
static inline void insw(uint16_t port, void *buf, uint32_t count)
{
asm volatile("rep insw"
: "+D"(buf), "+c"(count)
: "d"(port)
: "memory");
}The constraints matter. "+D" and "+c" put
buf in EDI and count in
ECX and tell gcc that the instruction changes
both, so it does not assume they still hold the old values afterwards.
"memory" tells it that memory was written behind its back:
without it the compiler could keep a stale copy of the buffer in a
register. ES is the kernel data segment, as every segment
register has been since chapter 9.
14.2.4 The driver: ata.c
The driver is one file, 233 lines. Its header promises three functions:
os/ata.h
#ifndef ATA_H
#define ATA_H
#include <stdint.h>
/* Parallel ATA driver for the master drive of the primary bus, in PIO
mode: the CPU moves every word through the data register itself. Slow,
but the simplest way to read a disk and the only one every PC since 1986
understands (ATA/ATAPI-6 specification; OSDev wiki: "ATA PIO Mode"). */
#define ATA_SECTOR_SIZE 512
/* Send IDENTIFY DEVICE, print the model and size. Returns 0 when a drive
answered, -1 when the bus is empty or the device is not ATA. */
int ata_identify(void);
/* Read `count` sectors (1..255) starting at logical block address `lba`
(28-bit) into `buf`. Returns 0 on success, -1 on a drive error. */
int ata_read_sectors(uint32_t lba, uint8_t count, void *buf);
/* Write `count` sectors from `buf` to the disk starting at `lba`, then
flush the drive's write cache so that the data is on the platters when
the function returns. Returns 0 on success, -1 on a drive error. */
int ata_write_sectors(uint32_t lba, uint8_t count, const void *buf);
#endifThe first part of ata.c gives names to the table
above:
os/ata.c (part 1)
/* ata.c -- ATA PIO on the primary bus (I/O ports 0x1F0-0x1F7 and 0x3F6).
*
* The register names and bits come from the ATA/ATAPI-6 specification
* (section 7, "Register descriptions"); the port numbers are the legacy
* PC assignment for the primary bus (OSDev wiki: "ATA PIO Mode").
*/
#include "ata.h"
#include "io.h"
#include "printf.h"
/* Command block registers, ATA/ATAPI-6 section 7.2 (names for a read). */
#define ATA_DATA 0x1F0 /* 16-bit data register */
#define ATA_ERROR 0x1F1 /* error bits after a failed command */
#define ATA_SECTOR_COUNT 0x1F2
#define ATA_LBA_LOW 0x1F3 /* LBA bits 7:0 */
#define ATA_LBA_MID 0x1F4 /* LBA bits 15:8 */
#define ATA_LBA_HIGH 0x1F5 /* LBA bits 23:16 */
#define ATA_DRIVE_HEAD 0x1F6 /* drive select, LBA bits 27:24 */
#define ATA_STATUS 0x1F7 /* read: status; write: command */
#define ATA_COMMAND 0x1F7
/* Control block register: reading it gives the status without clearing
a pending interrupt ("alternate status"), ATA/ATAPI-6 section 7.3. */
#define ATA_ALT_STATUS 0x3F6
/* Status register bits, ATA/ATAPI-6 section 7.15.6. */
#define ATA_SR_ERR 0x01 /* an error occurred; see the error register */
#define ATA_SR_DRQ 0x08 /* data request: the drive wants to transfer data */
#define ATA_SR_DF 0x20 /* device fault */
#define ATA_SR_RDY 0x40 /* device ready */
#define ATA_SR_BSY 0x80 /* busy: the other bits are not valid */
/* Drive/head register, ATA/ATAPI-6 section 7.7: bit 7 and 5 are always
1 (obsolete), bit 6 = 1 selects LBA addressing, bit 4 = drive (0 master,
1 slave), bits 3:0 = LBA bits 27:24. */
#define ATA_DH_MASTER_LBA 0xE0
#define ATA_DH_MASTER_CHS 0xA0
/* Commands, ATA/ATAPI-6 section 8. */
#define ATA_CMD_READ_SECTORS 0x20 /* 8.34 READ SECTOR(S), PIO data-in, LBA28 */
#define ATA_CMD_WRITE_SECTORS 0x30 /* 8.62 WRITE SECTOR(S), PIO data-out, LBA28 */
#define ATA_CMD_FLUSH_CACHE 0xE7 /* 8.12 FLUSH CACHE, non-data */
#define ATA_CMD_IDENTIFY 0xEC /* 8.15 IDENTIFY DEVICE */
/* REP OUTSW is the mirror image of the insw of io.h: it writes `count`
16-bit words from memory at DS:ESI to the port in DX (Intel SDM Vol.
2B, "OUTS/OUTSB/OUTSW/OUTSD"). "S" is the ESI register. The buffer
is only read, so there is no "memory" clobber to declare. */
static inline void outsw(uint16_t port, const void *buf, uint32_t count)
{
asm volatile("rep outsw"
: "+S"(buf), "+c"(count)
: "d"(port));
}
/* The spec asks the host to wait 400 ns after writing the device or
command register before it reads the status, and says the wait "may be
accomplished by reading the Alternate Status register and ignoring the
result" (ATA/ATAPI-6 section 9.5 and 9.6, "Check_Status"); one port
read takes about 100 ns, so read it four times (OSDev wiki: "ATA PIO
Mode", "400ns delays"). */
static void ata_delay_400ns(void)
{
inb(ATA_ALT_STATUS); inb(ATA_ALT_STATUS);
inb(ATA_ALT_STATUS); inb(ATA_ALT_STATUS);
}
/* Wait until BSY clears, then until DRQ is set or ERR/DF reported.
Returns the status, or 0 after too many tries (no drive at all). */
static uint8_t ata_wait_data(void)
{
uint32_t tries;
uint8_t status = 0;
for (tries = 0; tries < 1000000; tries++) {
status = inb(ATA_STATUS);
if (status & ATA_SR_BSY)
continue;
if (status & (ATA_SR_DRQ | ATA_SR_ERR | ATA_SR_DF))
return status;
}
return status;
}
/* Wait until BSY clears, whatever the other bits: the end of a command
that transfers no data (FLUSH CACHE), or of the last sector of a write. */
static uint8_t ata_wait_idle(void)
{
uint32_t tries;
uint8_t status = 0;
for (tries = 0; tries < 1000000; tries++) {
status = inb(ATA_STATUS);
if (!(status & ATA_SR_BSY))
break;
}
return status;
}The drive/head register deserves a second look. Its value
0xE0 is 1110 0000: bits 7 and 5 are relics
that must be 1, bit 6 selects LBA addressing, bit 4 clear selects the
master, and the low nibble is free for LBA bits 27:24. 0xA0
is the same with bit 6 clear, CHS mode, which is what the specification
says to use for IDENTIFY DEVICE. After selecting a drive, the
specification requires a 400 ns pause before the status is valid; the
traditional way to wait that long is to read the alternate status
register four times, since an ISA-speed port read takes about 100 ns,
and QEMU honors the convention.
ata_wait_data is the polling loop that every PIO driver
has: while BSY is set nothing else in the byte means
anything, so spin; once BSY is clear, return as soon as the
drive either wants to transfer data (DRQ) or reports
trouble (ERR, DF). The counter is a safety net
for a bus where nothing answers at all, so that a missing disk produces
an error message rather than a hang. ata_wait_idle is the
same loop for a command that transfers nothing, so that DRQ
never comes: it waits for BSY alone. It and
outsw, the mirror image of insw, serve the
write path of the section “Writing to the file system” below.
14.2.5 IDENTIFY DEVICE
IDENTIFY DEVICE (command 0xEC, ATA/ATAPI-6
section 8.15) asks the drive to describe itself: it answers with one
512-byte sector of 256 16-bit words, whose meaning is listed
word by word in the specification. We use two pieces: words 27-46 hold
the model name as 40 ASCII characters, two per word, and words 60-61
hold the number of addressable sectors in LBA28 mode as a 32-bit
little-endian value split in two words.
os/ata.c (part 2)
int ata_identify(void)
{
uint16_t id[256];
char model[41];
uint8_t status;
int i;
outb(ATA_DRIVE_HEAD, ATA_DH_MASTER_CHS);
ata_delay_400ns();
outb(ATA_SECTOR_COUNT, 0);
outb(ATA_LBA_LOW, 0);
outb(ATA_LBA_MID, 0);
outb(ATA_LBA_HIGH, 0);
outb(ATA_COMMAND, ATA_CMD_IDENTIFY);
/* A status of 0 (or 0xFF: floating bus) means nothing is there. */
status = inb(ATA_STATUS);
if (status == 0 || status == 0xFF) {
kprintf("ata: no drive on the primary bus (status 0x%x)\n", status);
return -1;
}
status = ata_wait_data();
/* An ATAPI device (CD-ROM) aborts IDENTIFY DEVICE and leaves its
signature 0x14, 0xEB in the LBA mid/high registers. */
if ((status & ATA_SR_ERR) || inb(ATA_LBA_MID) != 0 || inb(ATA_LBA_HIGH) != 0) {
kprintf("ata: primary master is not an ATA disk (status 0x%x)\n", status);
return -1;
}
if (!(status & ATA_SR_DRQ)) {
kprintf("ata: IDENTIFY timed out (status 0x%x)\n", status);
return -1;
}
insw(ATA_DATA, id, 256);
/* Words 27-46 hold the model string, two characters per word with
the first character in the high byte (ATA/ATAPI-6 section 3.2.9,
"Words 27-46: Model number"). */
for (i = 0; i < 20; i++) {
model[2 * i] = id[27 + i] >> 8;
model[2 * i + 1] = id[27 + i] & 0xFF;
}
model[40] = '\0';
for (i = 39; i >= 0 && model[i] == ' '; i--)
model[i] = '\0'; /* strip the padding */
/* Words 60-61: total number of addressable sectors in LBA28 mode
(section 8.15.26, "Words 60-61: Total number of user addressable
sectors"). */
kprintf("ata: primary master \"%s\", %u sectors (%u KiB)\n", model,
id[60] | ((uint32_t)id[61] << 16),
(id[60] | ((uint32_t)id[61] << 16)) / 2);
return 0;
}Three things can go wrong, and the function distinguishes them,
because each needs a different fix. A status of 0x00 or
0xFF right after the command means that no device decoded
the port at all: an open bus floats to all ones, and a controller with
no drive attached answers zeros. An ERR after the wait, or
a non-zero value in the LBA mid and high registers, means that
something answered but it is not an ATA disk: an ATAPI device
such as a CD-ROM rejects IDENTIFY DEVICE and leaves its
signature 0x14, 0xEB in those two registers,
so that the driver knows to send IDENTIFY PACKET DEVICE
instead, which we do not. Only when DRQ is set do 256 words
wait in the data register.
The model string is the classic ATA byte-swap puzzle. The
specification says each word holds two characters, “with the first
character in the high byte”, because the string was defined in terms of
16-bit words before anyone worried about which byte came first on the
wire. Reading the words with insw on a little-endian
machine therefore puts the characters pairwise in the wrong order, and
the loop swaps them back. Forget this, and QEMU HARDDISK
prints as EQUMH RADDSI K.
14.2.6 READ SECTORS
Reading is the same choreography with a different command: select the
drive and give it the top four address bits, write the sector count and
the other 24 address bits, write the command, then for every sector wait
for DRQ and pull 256 words.
os/ata.c (part 3)
int ata_read_sectors(uint32_t lba, uint8_t count, void *buf)
{
uint8_t *p = buf;
uint8_t status;
int i;
/* Select the master drive in LBA mode and hand it the address split
over four registers; then the command. The drive raises DRQ for
each sector in turn; we poll instead of using IRQ 14. */
outb(ATA_DRIVE_HEAD, ATA_DH_MASTER_LBA | ((lba >> 24) & 0x0F));
ata_delay_400ns();
outb(ATA_SECTOR_COUNT, count);
outb(ATA_LBA_LOW, lba & 0xFF);
outb(ATA_LBA_MID, (lba >> 8) & 0xFF);
outb(ATA_LBA_HIGH, (lba >> 16) & 0xFF);
outb(ATA_COMMAND, ATA_CMD_READ_SECTORS);
for (i = 0; i < count; i++) {
status = ata_wait_data();
if (!(status & ATA_SR_DRQ) || (status & (ATA_SR_ERR | ATA_SR_DF))) {
kprintf("ata: read error at LBA %u (status 0x%x, error 0x%x)\n",
lba + i, status, inb(ATA_ERROR));
return -1;
}
insw(ATA_DATA, p, ATA_SECTOR_SIZE / 2);
p += ATA_SECTOR_SIZE;
ata_delay_400ns();
}
return 0;
}READ SECTOR(S) (command 0x20, section 8.34)
transfers up to 256 sectors; a count of 0 means 256, which is why the
parameter is a uint8_t and the header says 1..255. The
drive raises DRQ once per sector, so the loop waits before
each insw; between sectors the 400 ns pause lets the status
settle before we read it again. The drive would also raise IRQ 14 after
each sector, and a kernel that has other things to do would sleep until
then instead of spinning on the status register; our tasks are not that
busy, and the interrupt stays masked in the PIC from chapter 11,
Interrupts.
Example 14.1. Where does LBA 2050, the first sector
the file system code asks for, go? 2050 = 0x802. Bits 27:24
are 0, so the drive/head register gets 0xE0 | 0 = 0xE0. LBA
low gets 0x02, LBA mid 0x08, LBA high
0x00. With a count of 2, the port writes are
0x1F6 <- 0xE0, 0x1F2 <- 2,
0x1F3 <- 0x02, 0x1F4 <- 0x08,
0x1F5 <- 0x00, 0x1F7 <- 0x20. We will
watch exactly this sequence in the debugger at the end of the
chapter.
14.2.7 Why q35 needs a PIIX3
When this driver first ran, it printed
ata: no drive on the primary bus (status 0xff). The kernel
was booted from the disk, so the disk existed; INT 13h had
just read 244 sectors from it. The bus was floating all the same. The
reason is the machine we emulate. Every chapter uses
-machine q35, QEMU’s model of a 2009-era Intel chipset
whose southbridge, the ICH9, has no parallel ATA controller: its disk
controller is AHCI, the SATA host controller interface, and
when we attach a drive with -drive if=ide QEMU puts it on
that controller. AHCI is a different programming model altogether: a PCI
device whose registers are memory-mapped through a BAR, with per-port
command lists in memory and Frame Information Structures
instead of eight ports and a status byte (Intel’s “Serial ATA Advanced
Host Controller Interface” specification, revision 1.3.1; OSDev wiki:
“AHCI”). It does not decode ports 0x1F0-0x1F7
at all, hence 0xFF. The BIOS had no problem because SeaBIOS
carries an AHCI driver.
Two fixes are possible. -machine pc models the older
i440FX chipset with a PIIX3 southbridge, which contains the legacy IDE
controller, and the driver works there unchanged. We prefer to keep q35,
which the whole of Part III uses, and add a PIIX3 IDE
controller to its PCI bus; QEMU allows that, and SeaBIOS boots from it.
This is the one change to the QEMU command line in this chapter, and the
Makefile explains it:
Makefile (excerpt)
# How the disk is attached to QEMU. The ATA driver (os/ata.c) talks to
# the legacy IDE ports 0x1F0-0x1F7. On the q35 machine `-drive if=ide`
# puts the disk on the ICH9 AHCI (SATA) controller, which does not decode
# those ports at all (reading them gives 0xFF: nothing answers), so we add
# a PIIX3 IDE controller to the PCI bus and attach the disk to it; SeaBIOS
# still boots from it. `-machine pc` (i440FX + PIIX3) would have the same
# controller built in, but q35 is what every other chapter uses.
QEMU_MACHINE=q35
QEMU_DRIVE_ARGS=-device piix3-ide,id=ide \
-drive id=disk,format=raw,file=$(DISK_IMG),if=none \
-device ide-hd,drive=disk,bus=ide.0-drive ... if=none defines the disk image without
attaching it anywhere; -device piix3-ide,id=ide adds the
controller; -device ide-hd,drive=disk,bus=ide.0 plugs the
disk into its primary bus as the master. You can see all three outcomes
for yourself. With the chapter’s command line the driver finds the disk;
with plain -drive if=ide on q35 it panics, as it
should:
$ qemu-system-i386 -machine q35 -drive format=raw,file=build/disk.img,if=ide -serial stdio -display none
Hello World from the kernel!
ata: no drive on the primary bus (status 0xff)
KERNEL PANIC: no ATA disk: see the comment on QEMU_DRIVE_ARGS in the Makefileand with -machine pc and the same plain
-drive it runs to the end, since the PIIX3 is built in.
Exercise 14.5 continues this comparison. The lesson is the one chapter 9
drew when the bootloader switched from CHS to LBA: the BIOS hides the
disk controller behind INT 13h, and the moment a kernel
drives the hardware itself, it has to know which hardware it is.
14.3 ext2 on disk
14.3.1 The reference and the layout
The ext2 on-disk format is described in “The Second Extended File
System: Internal Layout” by Dave Poirier, a free document maintained at
nongnu.org. Its chapter 3, “Disk Organization”, describes the superblock
(table 3.3, “Superblock Structure”), the block group descriptor table
(table 3.12), the bitmaps and the inode table (table 3.13, “Inode
Structure”), and its section “Locating an Inode” gives the arithmetic we
need. Its chapter 4, “Directory Structure”, describes the linked-list
directory format (table 4.1, “Linked Directory Entry Structure”) that
our disk uses. Have it open; ext2.h uses its field names
and cites it.
Everything in ext2 is measured in blocks of 1, 2 or 4 KiB;
the size is a parameter written in the superblock, and ours is 1 KiB,
the smallest, so that structures are not drowned in padding when we dump
them. Block numbers count from the start of the file system, not of the
disk: our file system starts at sector 2048 of the disk image (1 MiB in,
after the bootloader and kernel, see the disk layout table in
code/README.md), so block b is at sector
2048 + 2b. The layout of the file system, from its
beginning:
| Bytes | Block (1 KiB blocks) | Contents |
|---|---|---|
| 0 – 1023 | 0 | boot record, unused by ext2 |
| 1024 – 2047 | 1 | superblock |
| 2048 – | 2 | block group descriptor table (one descriptor per group) |
| 3 – 29 | reserved for growing the descriptor table
(resize_inode) |
|
| 30 | block bitmap of group 0 | |
| 31 | inode bitmap of group 0 | |
| 32 – 479 | inode table of group 0 | |
| 480 – 7167 | data blocks |
The superblock is always at byte 1024, whatever the block
size; with 4 KiB blocks it sits in the middle of block 0. The disk is
divided into block groups of 8192 blocks (8 MiB), each with its
own bitmaps and inode table, so that a file’s inode and data tend to be
close together; a 7 MiB file system has a single group, which keeps the
chapter simple without making the code wrong for larger disks. The
numbers in the right column are not from the document, they are what
mke2fs chose for our image, and we will read them back from
the disk.
14.3.2 The superblock
os/ext2.h (part 1)
#ifndef EXT2_H
#define EXT2_H
#include <stdint.h>
/* A small ext2: read any file, write new or existing regular files that
fit in the inode's direct blocks. Structures and field names follow
"The Second Extended File System: Internal Layout" by Dave Poirier
(section numbers in the comments); offsets are in bytes from the start
of each structure. */
/* The filesystem starts at this sector of the disk (code/README.md,
"Disk image layout"); block numbers are relative to it. */
#define EXT2_PARTITION_LBA 2048
/* Superblock, section 3.1: always at byte 1024 of the filesystem, 1024
bytes long. Only the fields up to s_volume_name are named here. */
struct ext2_superblock {
uint32_t s_inodes_count; /* 0 */
uint32_t s_blocks_count; /* 4 */
uint32_t s_r_blocks_count; /* 8 reserved for the superuser */
uint32_t s_free_blocks_count; /* 12 */
uint32_t s_free_inodes_count; /* 16 */
uint32_t s_first_data_block; /* 20 block holding the superblock: 1 if
the block size is 1 KiB, else 0 */
uint32_t s_log_block_size; /* 24 block size = 1024 << this */
uint32_t s_log_frag_size; /* 28 */
uint32_t s_blocks_per_group; /* 32 */
uint32_t s_frags_per_group; /* 36 */
uint32_t s_inodes_per_group; /* 40 */
uint32_t s_mtime; /* 44 */
uint32_t s_wtime; /* 48 */
uint16_t s_mnt_count; /* 52 */
uint16_t s_max_mnt_count; /* 54 */
uint16_t s_magic; /* 56 EXT2_SUPER_MAGIC */
uint16_t s_state; /* 58 */
uint16_t s_errors; /* 60 */
uint16_t s_minor_rev_level; /* 62 */
uint32_t s_lastcheck; /* 64 */
uint32_t s_checkinterval; /* 68 */
uint32_t s_creator_os; /* 72 */
uint32_t s_rev_level; /* 76 0 = original, 1 = dynamic */
uint16_t s_def_resuid; /* 80 */
uint16_t s_def_resgid; /* 82 */
/* EXT2_DYNAMIC_REV (revision 1) only: */
uint32_t s_first_ino; /* 84 first inode for ordinary files */
uint16_t s_inode_size; /* 88 size of an inode structure */
uint16_t s_block_group_nr; /* 90 */
uint32_t s_feature_compat; /* 92 */
uint32_t s_feature_incompat; /* 96 */
uint32_t s_feature_ro_compat; /* 100 */
uint8_t s_uuid[16]; /* 104 */
char s_volume_name[16]; /* 120 */
} __attribute__((packed));
#define EXT2_SUPER_MAGIC 0xEF53
#define EXT2_ROOT_INO 2As with the GDT entry in chapter 9, the structure is table 3.3 of the
document transcribed member by member, with the byte offsets in the
comments so that you can check it against a hexdump. We only name the
fields up to the volume name; the real superblock is 1024 bytes and the
rest concerns journaling, hashing and features we do not use. Of these
fields the kernel uses five: s_magic, to be sure this is
ext2 at all; s_log_block_size, the block size as a power of
two times 1 KiB; s_first_data_block, which is where the
group descriptor table is found (the block after it);
s_inodes_per_group and s_inode_size, to locate
an inode. Revision 0 file systems have no s_inode_size
field, every inode being 128 bytes; revision 1, the “dynamic” revision
that mke2fs has created for decades, stores the size, and
current versions choose 256 bytes to make room for nanosecond timestamps
and extended attributes. A reader that assumed 128 would find garbage
from the second inode on.
The bytes are easy to see for yourself. Build the chapter
(make), then dump the file system’s second kilobyte, which
is at byte 1048576 + 1024 of the disk image:
$ hexdump -C -s 1049600 -n 128 build/disk.img
00100400 00 07 00 00 00 1c 00 00 66 01 00 00 09 1a 00 00 |........f.......|
00100410 f0 06 00 00 01 00 00 00 00 00 00 00 00 00 00 00 |................|
00100420 00 20 00 00 00 20 00 00 00 07 00 00 00 00 00 00 |. ... ..........|
00100430 df c7 c9 6a 00 00 ff ff 53 ef 01 00 01 00 00 00 |...j....S.......|
00100440 df c7 c9 6a 00 00 00 00 00 00 00 00 01 00 00 00 |...j............|
00100450 00 00 00 00 0b 00 00 00 00 01 00 00 18 00 00 00 |................|
00100460 02 00 00 00 03 00 00 00 54 d0 af 21 8c 82 42 9d |........T..!..B.|
00100470 88 e8 51 71 cc 6e ad 08 6f 73 30 31 00 00 00 00 |..Qq.n..os01....|Example 14.2. Let us decode this with the structure
in hand, remembering that every number is little-endian. Offset 0:
00 07 00 00 is 0x700 = 1792 inodes. Offset 4:
0x1c00 = 7168 blocks. Offset 8: 0x166 = 358
blocks reserved for root (5%). Offsets 12 and 16: 6665 free blocks, 1776
free inodes. Offset 20: s_first_data_block = 1, as expected
with 1 KiB blocks. Offset 24: s_log_block_size = 0, so the
block size is 1024 << 0 = 1024. Offsets 32 and 40:
8192 blocks and 1792 inodes per group. Offset 48 (0x430):
df c7 c9 6a is the last write time, a Unix timestamp.
Offset 54: ff ff, a maximum mount count of -1 (never force
a check). Offset 56 (0x438): 53 ef, which read
as a little-endian 16-bit number is 0xEF53, the magic.
Offsets 58 and 60: state 1 (clean) and errors 1 (continue). Offset 76
(0x44c): revision 1. Offset 84 (0x454):
s_first_ino = 11, so inodes 1-10 are reserved and the first
file created gets inode 11; offset 88: 00 01 is
s_inode_size = 256. Offset 92:
s_feature_compat = 0x18; offset 96:
s_feature_incompat = 0x02, the filetype
feature, which puts a type byte in every directory entry (we will use
it); offset 100: s_feature_ro_compat = 0x03,
sparse_super and large_file. Offset 104: 16
bytes of UUID, different on every build. Offset 120:
6f 73 30 31, “os01”, the volume name.
The e2fsprogs tools decode the same bytes for you.
dumpe2fs -h prints the superblock; it expects a file that
starts with the file system, so we first extract the 7 MiB that follow
the first MiB of the image (debugfs, used below, accepts a
?offset= suffix instead):
$ dd if=build/disk.img of=build/fs.img bs=512 skip=2048 status=none
$ dumpe2fs -h build/fs.img
dumpe2fs 1.47.2 (1-Jan-2025)
Filesystem volume name: os01
Last mounted on: <not available>
Filesystem UUID: 54d0af21-8c82-429d-88e8-5171cc6ead08
Filesystem magic number: 0xEF53
Filesystem revision #: 1 (dynamic)
Filesystem features: ext_attr resize_inode filetype sparse_super large_file
Filesystem flags: signed_directory_hash
Default mount options: user_xattr acl
Filesystem state: clean
Errors behavior: Continue
Filesystem OS type: Linux
Inode count: 1792
Block count: 7168
Reserved block count: 358
Overhead clusters: 480
Free blocks: 6665
Free inodes: 1776
First block: 1
Block size: 1024
Fragment size: 1024
Reserved GDT blocks: 27
Blocks per group: 8192
Fragments per group: 8192
Inodes per group: 1792
Inode blocks per group: 448
Filesystem created: Sat Oct 10 05:06:39 2026
Last mount time: n/a
Last write time: Sat Oct 10 05:06:39 2026
Mount count: 0
Maximum mount count: -1
Last checked: Sat Oct 10 05:06:39 2026
Check interval: 0 (<none>)
Reserved blocks uid: 0 (user root)
Reserved blocks gid: 0 (group root)
First inode: 11
Inode size: 256
Required extra isize: 32
Desired extra isize: 32
Default directory hash: half_md4
Directory Hash Seed: 4165972e-5a15-4008-a71f-7c20834faf08Every line matches a field we just decoded (the UUID, hash seed and
times change at every build). “Inode blocks per group: 448” is
1792 * 256 / 1024: the inode table of our one group is 448
blocks long, which with the bitmaps and the reserved descriptor blocks
explains why the first data block is 480, the “Overhead clusters”
figure.
14.3.3 Block group descriptors
Right after the superblock, in block 2, starts the block group descriptor table: one 32-byte entry per group saying where that group’s bitmaps and inode table are.
os/ext2.h (part 2)
/* Block group descriptor, section 3.2: 32 bytes, one per block group,
stored in the block(s) right after the superblock. */
struct ext2_group_desc {
uint32_t bg_block_bitmap; /* 0 */
uint32_t bg_inode_bitmap; /* 4 */
uint32_t bg_inode_table; /* 8 first block of the inode table */
uint16_t bg_free_blocks_count; /* 12 */
uint16_t bg_free_inodes_count; /* 14 */
uint16_t bg_used_dirs_count; /* 16 */
uint16_t bg_pad; /* 18 */
uint8_t bg_reserved[12]; /* 20 */
} __attribute__((packed));$ hexdump -C -s 2048 -n 32 build/fs.img
00000800 1e 00 00 00 1f 00 00 00 20 00 00 00 09 1a f0 06 |........ .......|
00000810 04 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|Block bitmap at 30, inode bitmap at 31, inode table at 32, 6665 free
blocks, 1776 free inodes, 4 directories. dumpe2fs without
-h prints the same thing per group:
$ dumpe2fs build/fs.img | sed -n '/^Group 0/,$p'
Group 0: (Blocks 1-7167)
Primary superblock at 1, Group descriptors at 2-2
Reserved GDT blocks at 3-29
Block bitmap at 30 (+29)
Inode bitmap at 31 (+30)
Inode table at 32-479 (+31)
6665 free blocks, 1776 free inodes, 4 directories
Free blocks: 503-7167
Free inodes: 17-1792The bitmaps are what a writing implementation needs: one bit per block and per inode, 1 for used. A read-only kernel never looks at them; ours will, in the section “Writing to the file system”, and the two numbers 6665 and 1776 will each go down by one.
14.3.4 Inodes
An inode is the metadata of one file: its type and
permissions, owner, size, timestamps, and above all the list of blocks
that hold its content. A file’s name is not in its inode; names live in
directories, and several names may point to the same inode (hard links,
counted in i_links_count). Inodes are numbered from 1 and
stored back to back in the inode table of their group.
os/ext2.h (part 3)
/* Inode, section 3.3: 128 bytes (s_inode_size in revision 1). */
struct ext2_inode {
uint16_t i_mode; /* 0 file type and permissions */
uint16_t i_uid; /* 2 */
uint32_t i_size; /* 4 size in bytes (low 32 bits) */
uint32_t i_atime; /* 8 */
uint32_t i_ctime; /* 12 */
uint32_t i_mtime; /* 16 */
uint32_t i_dtime; /* 20 */
uint16_t i_gid; /* 24 */
uint16_t i_links_count; /* 26 */
uint32_t i_blocks; /* 28 in 512-byte units */
uint32_t i_flags; /* 32 */
uint32_t i_osd1; /* 36 */
uint32_t i_block[15]; /* 40 0-11 direct, 12 singly indirect,
13 doubly, 14 triply indirect */
uint32_t i_generation; /* 100 */
uint32_t i_file_acl; /* 104 */
uint32_t i_dir_acl; /* 108 */
uint32_t i_faddr; /* 112 */
uint8_t i_osd2[12]; /* 116 */
} __attribute__((packed));
/* i_mode, section 3.3 "i_mode": the high 4 bits are the file type, the
low 12 the permissions, in the same bit positions as Unix's st_mode. */
#define EXT2_S_IFMT 0xF000
#define EXT2_S_IFREG 0x8000
#define EXT2_S_IFDIR 0x4000
#define EXT2_S_PERM_644 0x01A4 /* rw-r--r-- (octal 0644) */The structure is 128 bytes; with s_inode_size = 256 each
inode is followed by 128 bytes of extra fields we ignore, which is why
the kernel must step through the table by s_inode_size, not
by sizeof(struct ext2_inode). The low 12 bits of
i_mode are the permission bits of Unix, in the same
positions as in st_mode: EXT2_S_PERM_644 is
rw-r--r--, the mode of the file the kernel will create.
The heart of the inode is i_block, fifteen block
numbers. The first twelve are direct: i_block[0]
is the block that holds bytes 0-1023 of the file,
i_block[1] bytes 1024-2047, and so on, 12 KiB in all.
Beyond that, i_block[12] is a singly indirect
block: it does not hold file data but 256 more block numbers (1024 bytes
/ 4), covering the next 256 KiB. i_block[13] is doubly
indirect, a block of 256 numbers of singly indirect blocks (64
MiB), and i_block[14] triply indirect (16 GiB). The scheme
is the classic Unix one from the 1970s: small files, the vast majority,
need no extra block at all, and the tree grows only as far as the file
does. Our files are 2.5 KiB, three direct blocks; ext2.c
implements the singly indirect level too, and leaves the other two to
exercise 14.1.
A block number of 0 in i_block has a special meaning:
there is no block, and that part of the file reads as zeros. Such a
hole is how a sparse file is stored. We learned this
the hard way: the first version of the user programs was linked with 4
KiB of zero padding between the ELF headers and the code,
mke2fs noticed the all-zero blocks and did not allocate
them, and the loader, which had read the inode with
i_block[1] == 0 and happily asked the disk for block 0,
loaded the superblock’s neighbor instead of the program. Block 0 holds
the boot record and is never a data block, so the convention is
unambiguous.
Finding an inode is the arithmetic of the document’s section
“Locating an Inode” (its table 3.20 has worked examples): inode numbers
are global, so subtract 1 (they start at 1), divide by
s_inodes_per_group to get the group, take the remainder as
the index in that group’s table, multiply by s_inode_size
to get a byte offset from bg_inode_table.
Example 14.3. /bin/hello is inode 14.
(14 - 1) / 1792 = 0: group 0.
(14 - 1) % 1792 = 13: the 14th slot.
13 * 256 = 3328 bytes into the inode table, which starts at
block 32: 3328 / 1024 = 3 blocks further, at offset
3328 % 1024 = 256. So the inode is at block 35, byte 256.
debugfs agrees:
$ debugfs -R "imap <14>" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
Inode 14 is part of block group 0
located at block 35, offset 0x0100And here are the bytes, at 35 * 1024 + 256 = 36096:
$ hexdump -C -s 36096 -n 128 build/fs.img
00008d00 ed 81 e8 03 e4 09 00 00 df c7 c9 6a df c7 c9 6a |...........j...j|
00008d10 df c7 c9 6a 00 00 00 00 e8 03 01 00 06 00 00 00 |...j............|
00008d20 00 00 00 00 00 00 00 00 f2 01 00 00 f3 01 00 00 |................|
00008d30 f4 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00008d40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
*
00008d80i_mode = 0x81ed: the high nibble 8 is
EXT2_S_IFREG, a regular file, and
0x1ed = 0755, the permissions.
i_uid = 0x3e8 = 1000, the user who ran make.
i_size = 0x9e4 = 2532 bytes. Three timestamps, then
i_dtime = 0 (not deleted), i_gid = 1000,
i_links_count = 1, i_blocks = 6 (in 512-byte
sectors: 3 KiB). At offset 40:
i_block[0..2] = 0x1f2, 0x1f3, 0x1f4 = 498, 499, 500, three
consecutive data blocks, and zeros from i_block[3] on.
debugfs -R "stat /bin/hello" prints the same inode in
words; its BLOCKS: (0-2):498-500 line is
i_block decoded.
14.3.5 Directories
A directory is a file whose content is a list of
(name, inode number) pairs; its inode has
EXT2_S_IFDIR in i_mode and its data blocks are
read through i_block like any file’s. In the original,
linked list format (chapter 4 of the document, “Linked List
Directory”), each block holds a sequence of variable-length entries:
os/ext2.h (part 4)
/* Linked directory entry, section 4.1.2. rec_len gives the offset of the
next entry, so the name is padded to a 4-byte boundary and the last
entry of a block stretches to its end. */
struct ext2_dir_entry {
uint32_t inode; /* 0: inode number, 0 = unused entry */
uint16_t rec_len; /* 4: displacement to the next entry */
uint8_t name_len; /* 6 */
uint8_t file_type; /* 7: EXT2_FT_* */
char name[]; /* 8: not NUL-terminated */
} __attribute__((packed));
#define EXT2_FT_REG_FILE 1
#define EXT2_FT_DIR 2
int ext2_mount(void);
uint32_t ext2_block_size(void);
const struct ext2_superblock *ext2_superblock(void);
int ext2_read_inode(uint32_t ino, struct ext2_inode *inode);
/* Inode number of an absolute path, or 0 when it does not exist. */
uint32_t ext2_lookup(const char *path);
/* Copy up to `size` bytes of the file into `buf`; returns the number of
bytes copied or -1 on a disk error. */
int ext2_read_file(const struct ext2_inode *inode, void *buf, uint32_t size);
/* Print the entries of a directory. */
void ext2_list_dir(const char *path);
/* Writing. Only regular files, only the 12 direct blocks of the inode
(12 KiB with 1 KiB blocks), and only directories that still have room
in their existing blocks. Every function writes its changes to the
disk before returning: there is no cache. */
/* Store the inode back into the inode table. Returns 0 or -1. */
int ext2_write_inode(uint32_t ino, const struct ext2_inode *inode);
/* Create an empty regular file with the permissions `mode` (the low 12
bits of i_mode) and return its inode number, or 0 when the parent
directory does not exist, the name exists already, or the disk is
full. */
uint32_t ext2_create(const char *path, uint16_t mode);
/* Replace the contents of the file at `path` by `len` bytes of `data`,
creating it (mode 0644) if it does not exist. Returns the number of
bytes written or -1. */
int ext2_write_file(const char *path, const void *data, uint32_t len);
#endifname[] is a flexible array member: the
structure has no fixed size, the name follows the 8-byte header and
rec_len says where the next entry begins. The name is not
NUL-terminated, name_len gives its length, and
rec_len is rounded up to a multiple of 4; the last entry of
a block has a rec_len that reaches the end of the block, so
that the entries of one block always add up to exactly the block size.
Deleting a file is done by growing the previous entry’s
rec_len over the deleted one, which is why the list is
“linked”. file_type exists because of the
filetype feature flag we saw in the superblock; it saves
reading the inode just to know whether a name is a directory. Modern
ext2/3/4 can also index large directories with a hash tree (the
document’s “Indexed Directory Format”); mke2fs was told
-O ^dir_index to keep that off, since the linked list is
what we parse. The last three prototypes are the write side of the file
system, explained in their own section once reading works.
The root directory is always inode 2. Here is its only block, block 480:
$ hexdump -C -s 491520 -n 96 build/fs.img
00078000 02 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
00078010 0c 00 02 02 2e 2e 00 00 0b 00 00 00 14 00 0a 02 |................|
00078020 6c 6f 73 74 2b 66 6f 75 6e 64 00 00 0c 00 00 00 |................|
00078030 0c 00 03 02 62 69 6e 00 0f 00 00 00 c8 03 03 02 |....bin.........|
00078040 65 74 63 00 00 00 00 00 00 00 00 00 00 00 00 00 |etc.............|
00078050 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|Example 14.4. Entry by entry: inode 2,
rec_len 12, name_len 1, type 2 (directory),
name . (2e) padded to 4 bytes; inode 2,
rec_len 12, name_len 2, type 2,
.. (the root is its own parent); inode 11,
rec_len 0x14 = 20, name_len 10,
type 2, lost+found, 10 characters padded to 12; inode 12,
rec_len 12, name_len 3, type 2,
bin; inode 15, rec_len
0x3c8 = 968, name_len 3, type 2,
etc. 12 + 12 + 20 + 12 + 968 = 1024: the last
entry stretches to the end of the block. lost+found is
created by mke2fs for fsck to put orphaned
files in, and it is inode 11, the s_first_ino we decoded.
debugfs -R "ls -l /" prints this list in words, with the
mode, owner and size read from each inode.
14.3.6 ext2.c: mounting
The read side is the first 224 lines of ext2.c. It keeps
the superblock, the block size and the first block of the group
descriptor table in static variables, and reaches the disk through two
functions of which only the first is used for now:
os/ext2.c (part 1)
/* ext2.c -- just enough ext2 to find a file by name, read it, and write
* a small one.
*
* Everything on the disk is reached through "blocks" of block_size bytes
* (1 KiB here), numbered from the start of the filesystem. Blocks are
* read and written with the ATA driver, block_size / 512 sectors at a
* time.
*/
#include "ext2.h"
#include "ata.h"
#include "rtc.h"
#include "printf.h"
#include "string.h"
#define MAX_BLOCK_SIZE 4096
static struct ext2_superblock sb;
static uint8_t sb_raw[1024]; /* the whole superblock */
static uint32_t block_size;
static uint32_t sectors_per_block;
static uint8_t group_table[MAX_BLOCK_SIZE]; /* first block of descriptors */
static int read_block(uint32_t block, void *buf)
{
return ata_read_sectors(EXT2_PARTITION_LBA + block * sectors_per_block,
sectors_per_block, buf);
}
static int write_block(uint32_t block, const void *buf)
{
return ata_write_sectors(EXT2_PARTITION_LBA + block * sectors_per_block,
sectors_per_block, buf);
}
int ext2_mount(void)
{
/* The superblock is at byte 1024 whatever the block size: sector 2
and 3 of the partition. The first KiB is left for a boot sector.
All 1024 bytes are kept, because they will be written back one
day and we only decode the first 136 of them. */
if (ata_read_sectors(EXT2_PARTITION_LBA + 2, 2, sb_raw) < 0)
return -1;
memcpy(&sb, sb_raw, sizeof(sb));
if (sb.s_magic != EXT2_SUPER_MAGIC) {
kprintf("ext2: bad magic 0x%x\n", sb.s_magic);
return -1;
}
block_size = 1024 << sb.s_log_block_size;
sectors_per_block = block_size / ATA_SECTOR_SIZE;
if (block_size > MAX_BLOCK_SIZE) {
kprintf("ext2: block size %u not supported\n", block_size);
return -1;
}
if (sb.s_rev_level == 0)
sb.s_inode_size = 128; /* revision 0 has no s_inode_size field */
/* The block group descriptor table starts in the block after the
superblock (section 3.2). One block of it is enough here: 32
descriptors of 32 bytes cover 32 groups of 8 MiB. */
return read_block(sb.s_first_data_block + 1, group_table);
}
uint32_t ext2_block_size(void)
{
return block_size;
}
const struct ext2_superblock *ext2_superblock(void)
{
return &sb;
}read_block is the translation from the file system’s
world to the disk’s: block b of a file system that starts at
sector EXT2_PARTITION_LBA with
sectors_per_block sectors per block is at sector
EXT2_PARTITION_LBA + b * sectors_per_block. Everything
above this function thinks in blocks. The order in
ext2_mount is forced by the format: the superblock has to
be read before the block size is known, so it is read as two raw sectors
at a fixed place, into sb_raw, which keeps all 1024 bytes
because the write side will need to put them back; only then can the
group descriptor table be read as a block. With 1 KiB blocks it is block
2, with larger blocks it is block 1, which is what
s_first_data_block + 1 expresses. One block of descriptors
is 32 of them, enough for a 256 MiB disk; a bigger one would need the
table to be read in full, a change of a few lines.
14.3.7 ext2.c:
inodes and file blocks
os/ext2.c (part 2)
/* Inode numbers start at 1. Section 3.3 gives the arithmetic: the group
from s_inodes_per_group, then the index inside that group's inode
table, which is s_inode_size bytes per inode. */
int ext2_read_inode(uint32_t ino, struct ext2_inode *inode)
{
uint8_t buf[MAX_BLOCK_SIZE];
uint32_t group = (ino - 1) / sb.s_inodes_per_group;
uint32_t index = (ino - 1) % sb.s_inodes_per_group;
uint32_t offset = index * sb.s_inode_size;
const struct ext2_group_desc *gd =
(const struct ext2_group_desc *)group_table + group;
if (ino == 0 || ino > sb.s_inodes_count)
return -1;
if (read_block(gd->bg_inode_table + offset / block_size, buf) < 0)
return -1;
memcpy(inode, buf + offset % block_size, sizeof(*inode));
return 0;
}
/* Block number of the n-th block of a file: the first 12 are listed in
the inode, the next block_size / 4 in the singly indirect block that
i_block[12] points to (section 3.3 "i_block"). Larger files would
need the doubly and triply indirect blocks; 12 + 256 KiB is enough for
our programs. Returns 0 when out of range, and also when the block was
never allocated: a "hole" in a sparse file, which reads as zeros (block
0 holds the boot record and is never a data block). */
static uint32_t file_block(const struct ext2_inode *inode, uint32_t n)
{
static uint32_t indirect[MAX_BLOCK_SIZE / 4];
static uint32_t indirect_block_cached;
if (n < 12)
return inode->i_block[n];
n -= 12;
if (n >= block_size / 4 || inode->i_block[12] == 0)
return 0;
if (indirect_block_cached != inode->i_block[12]) {
if (read_block(inode->i_block[12], indirect) < 0)
return 0;
indirect_block_cached = inode->i_block[12];
}
return indirect[n];
}
int ext2_read_file(const struct ext2_inode *inode, void *buf, uint32_t size)
{
uint8_t block[MAX_BLOCK_SIZE];
uint32_t done = 0, n;
if (size > inode->i_size)
size = inode->i_size;
for (n = 0; done < size; n++) {
uint32_t chunk = size - done < block_size ? size - done : block_size;
uint32_t b = file_block(inode, n);
if (b == 0)
memset(block, 0, chunk); /* a hole */
else if (read_block(b, block) < 0)
return -1;
memcpy((uint8_t *)buf + done, block, chunk);
done += chunk;
}
return (int)done;
}ext2_read_inode is example 14.3 in C: group, index, byte
offset, then the block of the inode table that holds it and the offset
within that block. It copies only the first 128 bytes of the 256-byte
slot, since that is all struct ext2_inode describes.
file_block answers the question “which disk block holds
the n-th kilobyte of this file?”, and it is the only place that
knows about the shape of i_block. For
n < 12 the answer is in the inode. Beyond, it reads the
singly indirect block, a block of 256 little-endian 32-bit block
numbers, and indexes it; the one-entry cache avoids reading the indirect
block again for every kilobyte of a large file. A result of 0 means “no
block”: past the end of what we support, or a hole, and
ext2_read_file turns it into zeros. With that,
ext2_read_file is a loop over the blocks of the file,
reading each into a bounce buffer and copying out the part that is
wanted, with the last block possibly partial.
14.3.8 ext2.c:
directories and paths
os/ext2.c (part 3)
/* Look for `name` (of `len` characters) in the directory `dir`; returns
its inode number or 0. Directory entries are a linked list inside
each block (section 4.1). */
static uint32_t dir_find(const struct ext2_inode *dir, const char *name, uint32_t len)
{
uint8_t block[MAX_BLOCK_SIZE];
uint32_t n, off;
for (n = 0; n * block_size < dir->i_size; n++) {
uint32_t b = file_block(dir, n);
if (b == 0 || read_block(b, block) < 0)
return 0;
for (off = 0; off < block_size; ) {
const struct ext2_dir_entry *e = (const struct ext2_dir_entry *)(block + off);
if (e->rec_len == 0)
return 0; /* corrupt block */
if (e->inode != 0 && e->name_len == len
&& memcmp(e->name, name, len) == 0)
return e->inode;
off += e->rec_len;
}
}
return 0;
}
uint32_t ext2_lookup(const char *path)
{
struct ext2_inode inode;
uint32_t ino = EXT2_ROOT_INO;
if (*path != '/')
return 0;
while (*path != '\0') {
const char *start;
while (*path == '/')
path++;
if (*path == '\0')
break;
for (start = path; *path != '\0' && *path != '/'; path++)
;
if (ext2_read_inode(ino, &inode) < 0)
return 0;
if ((inode.i_mode & EXT2_S_IFMT) != EXT2_S_IFDIR)
return 0; /* "a/b" where a is a file */
ino = dir_find(&inode, start, path - start);
if (ino == 0)
return 0;
}
return ino;
}dir_find walks the entries of every block of a directory
the way example 14.4 did by hand: start at offset 0, compare the name
(length first, then bytes, with the memcmp added to
string.c this chapter), advance by rec_len. An
entry with inode == 0 is a deleted or never-used slot and
is skipped. A rec_len of 0 would loop forever, so it is
treated as corruption. ext2_lookup is the path walk: start
at inode 2, and for each component between slashes, check that the
current inode is a directory and look the component up in it.
/bin/hello is thus two directory reads and three inode
reads. ext2_list_dir, the last function of the read side,
is dir_find with kprintf instead of a
comparison; its output is in the make test listing
below.
14.4 Building the disk image
The image is built by one rule of the top-level Makefile:
Makefile (excerpt)
# 16384 sectors x 512 bytes = 8 MiB. conv=notrunc keeps the image size.
# The filesystem is created in place by mke2fs: -E offset= skips the first
# MiB (bootloader and kernel), "7M" is its size, -d fills it from the
# staging directory, -F -q keep it from asking questions. -b 1024 is the
# block size the book's examples use (os/ext2.c reads it from the
# superblock anyway), -L the volume name, ^dir_index keeps directories
# in the plain linked-list format of the ext2 specification.
bootdisk: bootloader os user
rm -rf $(ROOTFS)
mkdir -p $(ROOTFS)/bin
cp -r rootfs/. $(ROOTFS)/
cp $(BUILD_DIR)/user/hello $(BUILD_DIR)/user/count $(ROOTFS)/bin/
dd if=/dev/zero of=$(DISK_IMG) bs=512 count=16384 status=none
dd conv=notrunc if=$(BOOTLOADER) of=$(DISK_IMG) bs=512 count=1 seek=0 status=none
dd conv=notrunc if=$(OS) of=$(DISK_IMG) bs=512 seek=1 status=none
mke2fs -F -q -t ext2 -b 1024 -O ^dir_index -L os01 -d $(ROOTFS) \
-E offset=1048576 $(DISK_IMG) 7MThe first four lines assemble a staging directory,
build/rootfs, that looks exactly like the root of the
future file system: the checked-in rootfs/ (which holds
etc/motd, a two-line text file) plus bin/hello
and bin/count from the user build. The two dd
lines are the ones from chapter 9, with the image grown from 4 to 8 MiB;
the kernel is 124760 bytes, 244 sectors, far from the 2047 it may use.
Then mke2fs creates the file system in place:
-E offset=1048576 makes it start 1 MiB into the image,
7M is its size, and -d $(ROOTFS) copies the
staging directory into it, which is how a file system is populated
without root and without mounting anything.
-F -q suppress the “this is not a block device, proceed?”
question and the chatter; -t ext2 asks for ext2 rather than
ext4; -b 1024 picks the block size; -L os01
sets the volume name; -O ^dir_index turns off hashed
directories. We do not pass -I 128 to get the old inode
size: e2fsprogs 1.47 warns that 128-byte inodes are
deprecated, and reading s_inode_size from the superblock is
the right thing anyway.
The staging directory is one of the few places where “what the file
system contains” is decided, and it is worth knowing what
mke2fs -d does with it: it creates inodes in the order it
meets the files, which is why bin is inode 12,
count 13, hello 14, etc 15 and
motd 16; it copies the owner and permissions of the host
files (hence uid 1000); and, as we saw, it leaves holes
where a file contains whole blocks of zeros.
debugfs is the tool to look at the result without
booting it. Here it reads the image directly, with the offset of the
file system appended to the file name:
$ debugfs -R "ls -l /bin" "build/disk.img?offset=1048576"
debugfs 1.47.2 (1-Jan-2025)
12 40755 (2) 1000 1000 1024 10-Oct-2026 05:06 .
2 40755 (2) 0 0 1024 10-Oct-2026 05:06 ..
13 100755 (1) 1000 1000 2528 10-Oct-2026 05:06 count
14 100755 (1) 1000 1000 2532 10-Oct-2026 05:06 hello
$ debugfs -R "stat /bin/hello" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
Inode: 14 Type: regular Mode: 0755 Flags: 0x0
Generation: 0 Version: 0x00000000:00000000
User: 1000 Group: 1000 Project: 0 Size: 2532
File ACL: 0
Links: 1 Blockcount: 6
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x6ac9c7df:00000000 -- Sat Oct 10 05:06:39 2026
atime: 0x6ac9c7df:00000000 -- Sat Oct 10 05:06:39 2026
mtime: 0x6ac9c7df:00000000 -- Sat Oct 10 05:06:39 2026
crtime: 0x6ac9c7df:00000000 -- Sat Oct 10 05:06:39 2026
Size of extra inode fields: 32
BLOCKS:
(0-2):498-500
TOTAL: 3
TOTAL: 1The columns of ls -l are the inode number, the mode in
octal (100755: 0x81ed from example 14.3, in
the other base), the file type in parentheses, uid, gid, size, date and
name. Compare stat with the hexdump of example 14.3 field
by field; the kernel will print
inode 14 file 2532 bytes hello from the same bytes.
14.5 Writing to the file system
Reading a file system is a matter of following pointers: superblock
to descriptor to inode table to inode to block. Writing one means
choosing where things go, which is what the bitmaps are for,
and leaving every structure consistent with every other: a directory
entry must point to an inode that is marked used, the inode to blocks
that are marked used, and the free counts must agree with the bitmaps.
This section adds the smallest write path that satisfies
e2fsck: a WRITE SECTOR(S) command in the
driver, allocation of blocks and inodes, and the creation of a regular
file in an existing directory. The kernel then uses it to keep a file,
/log.txt, that counts how many times the disk image has
booted, which is the simplest possible proof that something was written:
the number is different the next time.
14.5.1 WRITE SECTORS and FLUSH CACHE
WRITE SECTOR(S) is command 0x30
(ATA/ATAPI-6 section 8.62). Its inputs are the same registers with the
same meaning as for READ SECTOR(S): a sector count and a
28-bit address spread over four registers. What differs is the direction
of the data and the protocol, “PIO data-out” (section 9.6): after the
command, the drive raises DRQ when it is ready to
receive 256 words, the host writes them to the data register,
and the drive goes busy while it stores them, then raises
DRQ again for the next sector. The host state diagram of
section 9.6 (figure 27) says exactly when the status may be read: after
writing the command, “the host shall wait 400 ns before reading the
Status register”, and after a data block, one PIO transfer cycle; “the
wait may be accomplished by reading the Alternate Status register and
ignoring the result”. That sentence is the origin of the four reads in
ata_delay_400ns, and it applies to reads and writes
alike.
os/ata.c (part 4)
int ata_write_sectors(uint32_t lba, uint8_t count, const void *buf)
{
const uint8_t *p = buf;
uint8_t status;
int i;
/* Same registers, same address, the other command (ATA/ATAPI-6
section 8.62, protocol "PIO data-out", section 9.6). */
outb(ATA_DRIVE_HEAD, ATA_DH_MASTER_LBA | ((lba >> 24) & 0x0F));
ata_delay_400ns();
outb(ATA_SECTOR_COUNT, count);
outb(ATA_LBA_LOW, lba & 0xFF);
outb(ATA_LBA_MID, (lba >> 8) & 0xFF);
outb(ATA_LBA_HIGH, (lba >> 16) & 0xFF);
outb(ATA_COMMAND, ATA_CMD_WRITE_SECTORS);
/* For each sector the drive raises DRQ when it is ready to take 256
words; after the last one it stays BSY while it stores them. */
for (i = 0; i < count; i++) {
status = ata_wait_data();
if (!(status & ATA_SR_DRQ) || (status & (ATA_SR_ERR | ATA_SR_DF))) {
kprintf("ata: write error at LBA %u (status 0x%x, error 0x%x)\n",
lba + i, status, inb(ATA_ERROR));
return -1;
}
outsw(ATA_DATA, p, ATA_SECTOR_SIZE / 2);
p += ATA_SECTOR_SIZE;
ata_delay_400ns();
}
status = ata_wait_idle();
if (status & (ATA_SR_ERR | ATA_SR_DF)) {
kprintf("ata: write failed at LBA %u (status 0x%x, error 0x%x)\n",
lba, status, inb(ATA_ERROR));
return -1;
}
/* A drive may acknowledge a write as soon as the data is in its own
cache. FLUSH CACHE (section 8.12) returns only once everything in
that cache is on the medium: without it, "the write succeeded"
would not mean "the data survives a power cut". */
outb(ATA_COMMAND, ATA_CMD_FLUSH_CACHE);
ata_delay_400ns();
status = ata_wait_idle();
if (status & (ATA_SR_ERR | ATA_SR_DF)) {
kprintf("ata: FLUSH CACHE failed (status 0x%x, error 0x%x)\n",
status, inb(ATA_ERROR));
return -1;
}
return 0;
}Line by line, the function is ata_read_sectors with the
command byte changed and insw replaced by
outsw, the rep outsw of part 1 which pushes
ECX words from DS:ESI to the port in
DX (Intel SDM Volume 2B, “OUTS/OUTSB/OUTSW/OUTSD”).
outsw lives in ata.c rather than
io.h because the driver is its only user; its constraints
are those of insw with "S" (ESI)
for the source instead of "D" (EDI) for the
destination, and no "memory" clobber, since the buffer is
only read. Then come two things the read path does not have. After the
last sector the drive is still busy writing, and the specification
forbids sending another command while BSY is set, so
ata_wait_idle spins until it clears and checks for an error
reported at the end. And then FLUSH CACHE.
A modern drive, and QEMU’s emulation of one, has a write
cache: it reports a write as complete as soon as the data is in its
RAM, and commits it to the medium later, in whatever order suits it. For
throughput this is excellent; for a file system that chooses the order
of its writes carefully, as the next sections do, it is a trap, because
the drive may reorder them. FLUSH CACHE (command
0xE7, section 8.12, a “non-data” command: no
DRQ, just BSY until it is done) tells the
drive to write everything in its cache to the medium and to answer only
when that is done. Issuing it after every write is the slow, safe
choice, and it is what makes “the function returned 0” mean “the data
would survive a power cut now”. Linux issues it far more rarely, at the
barriers its file systems request, which is one reason a Linux
kernel writes a disk hundreds of times faster than ours will.
The symmetry with the read path is worth stating as a rule, because
every PIO device works this way: select, address, command, then for each
block of data wait for the device to say DRQ, move the
data, and let the status settle before looking at it again. A driver for
the floppy controller, a parallel port or a serial EEPROM has the same
skeleton.
14.5.2 Allocating a block and an inode
Everything above the driver reads and writes whole blocks, so
ext2.c gains write_block, the twin of
read_block shown in part 1, and the allocation code is
written in terms of it. The decisions about order are explained
in the comment at the top of the write side, and we will see them at
work in gdb:
os/ext2.c (part 4)
/* ---- Writing ----------------------------------------------------------
*
* The order in which things reach the disk is chosen so that a crash in
* the middle leaves a filesystem fsck can repair without losing data that
* was already there: first mark a block or inode used in its bitmap, then
* fill it, then make it reachable (the inode from the directory, the
* blocks from the inode). The free counts in the group descriptor and
* the superblock are written last; they are only hints, fsck recounts
* them from the bitmaps. */
/* Seconds since 1970 (UTC) for the timestamps, from the real-time clock
of rtc.c. The day count uses the "days from civil" formula (Howard
Hinnant, "chrono-Compatible Low-Level Date Algorithms"), with the year
starting in March so that the leap day is the last day of the year. */
static uint32_t now(void)
{
struct rtc_time t;
uint32_t y, era, yoe, doy, doe;
rtc_read(&t);
y = t.month <= 2 ? t.year - 1 : t.year;
era = y / 400;
yoe = y - era * 400; /* year of era, 0-399 */
doy = (153 * (t.month > 2 ? t.month - 3 : t.month + 9) + 2) / 5 + t.day - 1;
doe = yoe * 365 + yoe / 4 - yoe / 100 + doy; /* day of era, 0-146096 */
return (era * 146097 + doe - 719468) * 86400
+ t.hour * 3600 + t.minute * 60 + t.second;
}
static int write_superblock(void)
{
sb.s_wtime = now();
memcpy(sb_raw, &sb, sizeof(sb));
return ata_write_sectors(EXT2_PARTITION_LBA + 2, 2, sb_raw);
}
static int write_group_table(void)
{
return write_block(sb.s_first_data_block + 1, group_table);
}
/* The bitmaps (section 3.2, "Block Bitmap" and "Inode Bitmap"): one bit
per block or inode of the group, 1 = used, bit 0 of byte 0 first.
Find the first clear bit among `nbits`, set it, return its index, or
-1 when every bit is set. */
static int bitmap_alloc(uint8_t *bitmap, uint32_t nbits)
{
uint32_t i;
for (i = 0; i < nbits; i++) {
if (!(bitmap[i / 8] & (1 << (i % 8)))) {
bitmap[i / 8] |= 1 << (i % 8);
return (int)i;
}
}
return -1;
}
/* Allocate one data block: find a group with a free block, take the
first free bit of its block bitmap and write the bitmap back. Bit n
of group g is block s_first_data_block + g * s_blocks_per_group + n.
Returns the block number, or 0 when the disk is full. */
static uint32_t alloc_block(void)
{
uint8_t bitmap[MAX_BLOCK_SIZE];
uint32_t groups = (sb.s_blocks_count - sb.s_first_data_block
+ sb.s_blocks_per_group - 1) / sb.s_blocks_per_group;
uint32_t g;
for (g = 0; g < groups; g++) {
struct ext2_group_desc *gd = (struct ext2_group_desc *)group_table + g;
uint32_t first = sb.s_first_data_block + g * sb.s_blocks_per_group;
uint32_t nbits = sb.s_blocks_count - first;
int bit;
if (nbits > sb.s_blocks_per_group)
nbits = sb.s_blocks_per_group; /* the last group is shorter */
if (gd->bg_free_blocks_count == 0)
continue;
if (read_block(gd->bg_block_bitmap, bitmap) < 0)
return 0;
bit = bitmap_alloc(bitmap, nbits);
if (bit < 0)
continue; /* the count lied; next group */
if (write_block(gd->bg_block_bitmap, bitmap) < 0)
return 0;
gd->bg_free_blocks_count--;
sb.s_free_blocks_count--;
return first + bit;
}
kprintf("ext2: no free block\n");
return 0;
}
/* The inverse: clear the block's bit and give it back to the counts. The
block's contents stay on the disk, which is what undelete tools rely on. */
static int free_block(uint32_t block)
{
uint8_t bitmap[MAX_BLOCK_SIZE];
uint32_t g = (block - sb.s_first_data_block) / sb.s_blocks_per_group;
uint32_t bit = (block - sb.s_first_data_block) % sb.s_blocks_per_group;
struct ext2_group_desc *gd = (struct ext2_group_desc *)group_table + g;
if (read_block(gd->bg_block_bitmap, bitmap) < 0)
return -1;
bitmap[bit / 8] &= ~(1 << (bit % 8));
if (write_block(gd->bg_block_bitmap, bitmap) < 0)
return -1;
gd->bg_free_blocks_count++;
sb.s_free_blocks_count++;
return 0;
}
/* Allocate an inode the same way. Bit n of group g is inode number
g * s_inodes_per_group + n + 1: inode numbers start at 1 (section 3.2,
"Inode Bitmap"). Returns 0 when there is none left. */
static uint32_t alloc_inode(void)
{
uint8_t bitmap[MAX_BLOCK_SIZE];
uint32_t groups = sb.s_inodes_count / sb.s_inodes_per_group;
uint32_t g;
for (g = 0; g < groups; g++) {
struct ext2_group_desc *gd = (struct ext2_group_desc *)group_table + g;
int bit;
if (gd->bg_free_inodes_count == 0)
continue;
if (read_block(gd->bg_inode_bitmap, bitmap) < 0)
return 0;
bit = bitmap_alloc(bitmap, sb.s_inodes_per_group);
if (bit < 0)
continue;
if (write_block(gd->bg_inode_bitmap, bitmap) < 0)
return 0;
gd->bg_free_inodes_count--;
sb.s_free_inodes_count--;
return g * sb.s_inodes_per_group + bit + 1;
}
kprintf("ext2: no free inode\n");
return 0;
}The bitmaps were described, and dumped, in the section on block group
descriptors. Their format (document section 3.2, “Block Bitmap” and
“Inode Bitmap”) is one bit per block or inode, bit 0 of byte 0 first, 1
for used, and bitmap_alloc is the whole algorithm: scan for
the first 0 bit, set it, return its index. What the index means
is the only subtle part, and it differs between the two bitmaps. For
blocks, bit n of group g is block
s_first_data_block + g * s_blocks_per_group + n: with 1 KiB
blocks s_first_data_block is 1, so bit 0 is block 1, the
superblock. For inodes, bit n of group g is inode
g * s_inodes_per_group + n + 1, because inode numbers start
at 1 and “the first bit in the first block group’s inode bitmap
represents inode number 1”. alloc_block also limits the
scan to the blocks the group really has, since the last group of a disk
is shorter than s_blocks_per_group; mke2fs
sets the bits past the end to 1 so that the scan would stop anyway, but
relying on that is the kind of thing that works until a differently made
disk comes along.
Example 14.5. Before the kernel writes anything,
dumpe2fs reports Free blocks: 503-7167 and
Free inodes: 17-1792. The first free block is 503, which is
bit 503 - 1 = 502 of the block bitmap: byte
502 / 8 = 62, bit 502 % 8 = 6. The first free
inode is 17, bit 17 - 1 = 16: byte 2, bit 0. After
alloc_block and alloc_inode have each run
once, byte 62 of the block bitmap must have changed from
0x3f (bits 0-5) to 0x7f (bits 0-6), and byte 2
of the inode bitmap from 0x00 to 0x01. We
check this below.
now() is a digression that every file system needs: the
inode timestamps are seconds since 1970 in UTC, the real-time clock of
the PC gives a calendar date, and the conversion is the one every libc
hides in mktime; the trick of starting the year in March
makes the leap day the last day of the year and the month lengths a
simple formula. Each allocation writes its bitmap back to the disk at
once, and only adjusts the counts in the in-memory copies of the group
descriptor and the superblock; write_group_table and
write_superblock put those on the disk later, once per file
operation. There is a reason for this asymmetry, and it is the first
lesson about ordering. The bitmap is the truth about which
blocks are in use; the counts are a summary of it, kept so that
a kernel can find a group with free space without scanning bitmaps. If
the power fails after the bitmap write and before the counts are
written, the disk holds a block that is marked used and a count that is
one too high. That is a harmless inconsistency: e2fsck
recomputes every count from the bitmaps in its pass 5 and prints
Free blocks count wrong for group #0 (6665, counted=6664). Fix?.
The reverse order could produce a count that promises a block the bitmap
does not have, which is still harmless, but imagine instead that we
wrote an inode pointing to block 503 before the bitmap: a crash
in between leaves a block that is in use and marked free, and the next
allocation hands it out again, to a second file, silently. That is data
loss, and the rule that avoids it is the one in the comment: mark first,
use afterwards.
free_block is the inverse, and the comment makes a point
that surprises people: freeing a block does not touch the block. The
data stays on the disk until something else is allocated there, which is
why “undelete” tools exist, why a disk that held secrets is wiped rather
than reformatted, and why ext2_write_file below clears the
tail of a partially filled block instead of leaving whatever was in the
buffer.
14.5.3 Writing an inode and a directory entry
os/ext2.c (part 5)
/* The same arithmetic as ext2_read_inode, and a read-modify-write of the
block, because it holds other inodes too (four of them with 256-byte
inodes and 1 KiB blocks). */
int ext2_write_inode(uint32_t ino, const struct ext2_inode *inode)
{
uint8_t buf[MAX_BLOCK_SIZE];
uint32_t group = (ino - 1) / sb.s_inodes_per_group;
uint32_t index = (ino - 1) % sb.s_inodes_per_group;
uint32_t offset = index * sb.s_inode_size;
const struct ext2_group_desc *gd =
(const struct ext2_group_desc *)group_table + group;
uint32_t b = gd->bg_inode_table + offset / block_size;
if (ino == 0 || ino > sb.s_inodes_count)
return -1;
if (read_block(b, buf) < 0)
return -1;
memcpy(buf + offset % block_size, inode, sizeof(*inode));
return write_block(b, buf);
}
/* Add the name to a directory (section 4.1, "Linked List Directory").
Each entry owns rec_len bytes but only needs 8 + name_len, rounded up
to 4; the slack, which is largest in the last entry of a block since
it stretches to the end, is where new entries go: the old entry's
rec_len shrinks to what it needs and the new one takes the rest. An
entry with inode 0 is free space in its entirety. Returns -1 when no
block of the directory has room: we do not grow directories. */
static int dir_add_entry(const struct ext2_inode *dir, const char *name,
uint32_t len, uint32_t ino, uint8_t type)
{
uint8_t block[MAX_BLOCK_SIZE];
uint32_t need = (8 + len + 3) & ~3u;
uint32_t n, off;
for (n = 0; n * block_size < dir->i_size; n++) {
uint32_t b = file_block(dir, n);
if (b == 0 || read_block(b, block) < 0)
return -1;
for (off = 0; off < block_size; ) {
struct ext2_dir_entry *e = (struct ext2_dir_entry *)(block + off);
struct ext2_dir_entry *new;
uint32_t used, rest;
if (e->rec_len == 0)
return -1; /* corrupt block */
used = e->inode == 0 ? 0 : (8 + e->name_len + 3) & ~3u;
rest = e->rec_len - used;
if (rest < need) {
off += e->rec_len;
continue;
}
new = (struct ext2_dir_entry *)(block + off + used);
if (used != 0)
e->rec_len = used;
new->inode = ino;
new->rec_len = rest;
new->name_len = len;
new->file_type = type;
memcpy(new->name, name, len);
return write_block(b, block);
}
}
kprintf("ext2: directory is full\n");
return -1;
}
/* Split "/a/b/name" into the inode of "/a/b" and the name. Returns the
directory's inode number, or 0. */
static uint32_t split_path(const char *path, const char **name, uint32_t *len)
{
char parent[256];
uint32_t last = 0, i;
if (*path != '/' || strlen(path) >= sizeof(parent))
return 0;
for (i = 0; path[i] != '\0'; i++)
if (path[i] == '/')
last = i;
*name = path + last + 1;
*len = strlen(*name);
if (*len == 0 || *len > 255)
return 0;
memcpy(parent, path, last + 1); /* up to and including the / */
parent[last + 1] = '\0';
return ext2_lookup(parent);
}ext2_write_inode repeats the arithmetic of
ext2_read_inode and example 14.3 to find the block of the
inode table and the offset in it, then does what every write of
something smaller than a block must do: read the block, change the 128
bytes, write the block back. With 256-byte inodes a block of the inode
table holds four of them, and the other three must come back unharmed.
The 128 bytes after our structure, the “extra” fields of the large
inode, are left as they were: zero in a slot that was never used, since
mke2fs zeroes the inode table.
dir_add_entry is the part that needs example 14.4 fresh
in mind. An entry of the linked list owns rec_len bytes but
needs only 8 + name_len, rounded up to a multiple of 4, and
the difference is free space. Most entries have none (.
needs 12 bytes and owns 12), but the last entry of a block owns
everything up to the end of the block: in the root directory,
etc owned 968 bytes for a 12-byte need. This is why ext2
pads the last entry rather than storing a count of entries somewhere:
the padding is the free list, and inserting a name is a matter
of splitting one entry in two. The old entry’s rec_len
shrinks to what it uses, the new entry starts right after it and takes
the rest, so that the rec_lens of a block still add up to
the block size, which is the invariant e2fsck checks in its
pass 2 and the one dir_find relies on to stop at the end of
a block. An entry whose inode is 0 is free in its entirety
(used = 0), so a deleted name’s space is reused too. What
the function does not do is add a block to the directory when every
block is full; our directories have 1024 bytes and we add one 16-byte
name.
Example 14.6. Inserting log.txt (7
characters: 8 + 7 = 15, rounded up to 16 bytes) into the
root directory of example 14.4. The entries .,
.., lost+found and bin have no
slack. etc at offset 0x40 has
rec_len = 968 and used = 12, so
rest = 956 >= 16. Its rec_len becomes 12;
the new entry goes at 0x40 + 12 = 0x4c with
inode = 17, rec_len = 956 = 0x3bc,
name_len = 7, file_type = 1 (regular file) and
the name; 12 + 12 + 20 + 12 + 12 + 956 = 1024. Here is the
block after the kernel has done it:
$ hexdump -C -s 491520 -n 112 build/fs.img
00078000 02 00 00 00 0c 00 01 02 2e 00 00 00 02 00 00 00 |................|
00078010 0c 00 02 02 2e 2e 00 00 0b 00 00 00 14 00 0a 02 |................|
00078020 6c 6f 73 74 2b 66 6f 75 6e 64 00 00 0c 00 00 00 |lost+found......|
00078030 0c 00 03 02 62 69 6e 00 0f 00 00 00 0c 00 03 02 |....bin.........|
00078040 65 74 63 00 11 00 00 00 bc 03 07 01 6c 6f 67 2e |etc.........log.|
00078050 74 78 74 00 00 00 00 00 00 00 00 00 00 00 00 00 |txt.............|
00078060 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|At 0x4c: 11 00 00 00 is inode 17,
bc 03 is 956, 07 and 01 the name
length and type, then log.txt and one byte of padding.
split_path is the small piece of string handling that
turns /log.txt into the inode of / plus the
name log.txt, using ext2_lookup on the
directory part.
14.5.4 Creating and writing a file
os/ext2.c (part 6)
uint32_t ext2_create(const char *path, uint16_t mode)
{
struct ext2_inode dir, inode;
const char *name;
uint32_t len, dir_ino, ino;
dir_ino = split_path(path, &name, &len);
if (dir_ino == 0 || ext2_read_inode(dir_ino, &dir) < 0
|| (dir.i_mode & EXT2_S_IFMT) != EXT2_S_IFDIR) {
kprintf("%s: no such directory\n", path);
return 0;
}
if (dir_find(&dir, name, len) != 0) {
kprintf("%s: exists\n", path);
return 0;
}
ino = alloc_inode();
if (ino == 0)
return 0;
/* A new, empty regular file: one link (the directory entry we are
about to add), no blocks, three timestamps set to "now". */
memset(&inode, 0, sizeof(inode));
inode.i_mode = EXT2_S_IFREG | (mode & 0x0FFF);
inode.i_links_count = 1;
inode.i_atime = inode.i_ctime = inode.i_mtime = now();
if (ext2_write_inode(ino, &inode) < 0)
return 0;
/* Only now does a name point to it. The directory's own mtime
changes too: a directory is a file whose content we just edited. */
if (dir_add_entry(&dir, name, len, ino, EXT2_FT_REG_FILE) < 0)
return 0;
dir.i_mtime = dir.i_ctime = now();
if (ext2_write_inode(dir_ino, &dir) < 0)
return 0;
if (write_group_table() < 0 || write_superblock() < 0)
return 0;
return ino;
}
int ext2_write_file(const char *path, const void *data, uint32_t len)
{
uint8_t block[MAX_BLOCK_SIZE];
struct ext2_inode inode;
uint32_t ino, needed = (len + block_size - 1) / block_size, n;
if (needed > 12) {
kprintf("%s: %u bytes do not fit in 12 direct blocks\n", path, len);
return -1;
}
ino = ext2_lookup(path);
if (ino == 0)
ino = ext2_create(path, EXT2_S_PERM_644);
if (ino == 0 || ext2_read_inode(ino, &inode) < 0)
return -1;
if ((inode.i_mode & EXT2_S_IFMT) != EXT2_S_IFREG) {
kprintf("%s: not a regular file\n", path);
return -1;
}
if (inode.i_block[12] != 0) {
kprintf("%s: has indirect blocks, which we cannot free\n", path);
return -1;
}
/* Block by block: reuse the block the file already has at that
position, allocate one if there is none, write the data. The last
block is padded with zeros rather than left with whatever was in
the buffer: the bytes past i_size are on the disk for anyone to
read with debugfs. */
for (n = 0; n < needed; n++) {
uint32_t chunk = len - n * block_size;
if (chunk > block_size)
chunk = block_size;
if (inode.i_block[n] == 0) {
inode.i_block[n] = alloc_block();
if (inode.i_block[n] == 0)
return -1;
}
memcpy(block, (const uint8_t *)data + n * block_size, chunk);
memset(block + chunk, 0, block_size - chunk);
if (write_block(inode.i_block[n], block) < 0)
return -1;
}
/* Blocks the old contents used beyond the new size go back to the
bitmap, so that i_size, i_blocks and i_block agree. */
for (n = needed; n < 12; n++) {
if (inode.i_block[n] != 0 && free_block(inode.i_block[n]) < 0)
return -1;
inode.i_block[n] = 0;
}
inode.i_size = len;
inode.i_blocks = needed * sectors_per_block; /* 512-byte units */
inode.i_mtime = inode.i_ctime = now();
if (ext2_write_inode(ino, &inode) < 0)
return -1;
if (write_group_table() < 0 || write_superblock() < 0)
return -1;
return (int)len;
}ext2_create makes an empty regular file. Its inode is
built from nothing: i_mode is the type
EXT2_S_IFREG plus the permissions,
i_links_count is 1 because exactly one directory entry is
about to point to it, i_size and i_blocks are
0, i_block is all zeros, and the three timestamps are set
to now(), the Unix time computed from the real-time clock
of rtc.c; debugfs will show the date and time.
The order is the second lesson about ordering, and it is the
mirror image of the first: allocate the inode (its bitmap bit is set),
write the inode, and only then write the directory entry that
makes it reachable. A crash before the last step leaves an inode that is
marked used, filled in, and pointed to by nothing; e2fsck
finds it in pass 4, “Checking reference counts”, and offers to connect
it to lost+found, the directory mke2fs created
for exactly this purpose. The other order would risk a name pointing at
an inode full of garbage. The directory’s own inode is written last, for
its modification time: a directory is a file, and we just changed its
content.
ext2_write_file replaces the contents of a file,
creating it when it does not exist. It works one block at a time,
reusing a block the file already has at that position and allocating one
otherwise, which makes it serve both for a new file and for rewriting an
existing one; blocks beyond the new size are given back, so that
i_size, i_blocks and i_block tell
the same story (e2fsck pass 1, “Checking inodes, blocks,
and sizes”, compares them). i_blocks is in 512-byte units
whatever the block size, a convention inherited from the
st_blocks of Unix’s stat: 2 per block here.
The limit of 12 direct blocks, 12 KiB, is a limit of this function and
not of the format; a file that needs a thirteenth block needs
i_block[12] to point to an indirect block which must itself
be allocated and filled with block numbers, and freeing it on rewrite is
the same work backwards. That is exercise 14.8’s territory.
The data block is written before the inode that points to it, by the
same rule as above: at the moment the inode goes to the disk, everything
it refers to is already there. Here is the complete sequence of disk
writes of a first boot, recorded with a breakpoint in
ata_write_sectors that prints three frames of the stack and
continues; the command file is a few lines of gdb:
writes.gdb
b ata_write_sectors
commands
silent
bt 3
c
end#0 ata_write_sectors (lba=2110, count=2 '\002', buf=0x8dcd0) at ata.c:186
#1 0x00011376 in write_block (block=31, buf=0x8dcd0) at ext2.c:31
#2 0x00011f49 in alloc_inode () at ext2.c:359
#0 ata_write_sectors (lba=2120, count=2 '\002', buf=0x8dcbc) at ata.c:186
#1 0x00011376 in write_block (block=36, buf=0x8dcbc) at ext2.c:31
#2 0x0001209c in ext2_write_inode (ino=17, inode=0x8ed08) at ext2.c:387
#0 ata_write_sectors (lba=3008, count=2 '\002', buf=0x8dca0) at ata.c:186
#1 0x00011376 in write_block (block=480, buf=0x8dca0) at ext2.c:31
#2 0x00012203 in dir_add_entry (dir=0x8ed88, name=0x15982 "log.txt", len=7, ino=17, type=1 '\001') at ext2.c:430
#0 ata_write_sectors (lba=2112, count=2 '\002', buf=0x8dcbc) at ata.c:186
#1 0x00011376 in write_block (block=32, buf=0x8dcbc) at ext2.c:31
#2 0x0001209c in ext2_write_inode (ino=2, inode=0x8ed88) at ext2.c:387
#0 ata_write_sectors (lba=2052, count=2 '\002', buf=0x174c0 <group_table>) at ata.c:186
#1 0x00011376 in write_block (block=2, buf=0x174c0 <group_table>) at ext2.c:31
#2 0x00011be8 in write_group_table () at ext2.c:264
#0 ata_write_sectors (lba=2050, count=2 '\002', buf=0x170a0 <sb_raw>) at ata.c:186
#1 0x00011bc7 in write_superblock () at ext2.c:259
#2 0x00012501 in ext2_create (path=0x15981 "/log.txt", mode=420) at ext2.c:494
#0 ata_write_sectors (lba=2108, count=2 '\002', buf=0x8de08) at ata.c:186
#1 0x00011376 in write_block (block=30, buf=0x8de08) at ext2.c:31
#2 0x00011d53 in alloc_block () at ext2.c:310
#0 ata_write_sectors (lba=3054, count=2 '\002', buf=0x8eeb0) at ata.c:186
#1 0x00011376 in write_block (block=503, buf=0x8eeb0) at ext2.c:31
#2 0x000126e0 in ext2_write_file (path=0x15981 "/log.txt", data=0x8ff6c, len=46) at ext2.c:540
#0 ata_write_sectors (lba=2120, count=2 '\002', buf=0x8ddfc) at ata.c:186
#1 0x00011376 in write_block (block=36, buf=0x8ddfc) at ext2.c:31
#2 0x0001209c in ext2_write_inode (ino=17, inode=0x8ee30) at ext2.c:387
#0 ata_write_sectors (lba=2052, count=2 '\002', buf=0x174c0 <group_table>) at ata.c:186
#1 0x00011376 in write_block (block=2, buf=0x174c0 <group_table>) at ext2.c:31
#2 0x00011be8 in write_group_table () at ext2.c:264
#0 ata_write_sectors (lba=2050, count=2 '\002', buf=0x170a0 <sb_raw>) at ata.c:186
#1 0x00011bc7 in write_superblock () at ext2.c:259
#2 0x000127b9 in ext2_write_file (path=0x15981 "/log.txt", data=0x8ff6c, len=46) at ext2.c:555
Breakpoint 3, kmain () at kernel.c:128
128 elf_exec("/bin/hello");Eleven writes of two sectors each. Read them against the layout table
of the section “The reference and the layout”, remembering that block
b is at sector 2048 + 2b: 2110 is block 31, the
inode bitmap; 2120 is block 36, the inode table block that holds inode
17 ((17 - 1) * 256 / 1024 = 4 blocks after 32); 3008 is
block 480, the root directory; 2112 is block 32, where inode 2 lives;
2052 is block 2, the group descriptor table; 2050 is the superblock.
That is ext2_create. Then ext2_write_file
takes over: 2108 is block 30, the block bitmap; 3054 is block 503, the
data; the inode again, now with a size and a block; the descriptors and
the superblock again. Nothing is written that was not marked used first,
and nothing points to anything that was not written first.
14.5.5 Something that survives a reboot
The kernel’s use of all this is a function that writes
/log.txt with a boot number and the tick count, where the
boot number comes from the previous content of the file:
os/kernel.c (excerpt)
/* Append the decimal digits of `v` at `p`; returns the position after. */
static char *put_number(char *p, uint32_t v)
{
char digits[10];
int n = 0;
do {
digits[n++] = '0' + v % 10;
v /= 10;
} while (v > 0);
while (n > 0)
*p++ = digits[--n];
return p;
}
/* Write a line to /log.txt saying how many times this disk image has
booted: the previous line, if the file exists, holds the count. */
static void log_boot(void)
{
char line[64], *p = line;
struct ext2_inode inode;
uint32_t ino = ext2_lookup("/log.txt"), boot = 1, i;
int n;
if (ino != 0 && ext2_read_inode(ino, &inode) == 0
&& (n = ext2_read_file(&inode, line, sizeof(line) - 1)) > 0) {
line[n] = '\0';
for (boot = 0, i = 5; line[i] >= '0' && line[i] <= '9'; i++)
boot = boot * 10 + (line[i] - '0'); /* "boot N, ..." */
boot++;
}
memcpy(p, "boot ", 5);
p = put_number(p + 5, boot);
memcpy(p, " of this disk image, written at tick ", 37);
p = put_number(p + 37, ticks);
*p++ = '\n';
n = ext2_write_file("/log.txt", line, p - line);
kprintf("ext2: wrote %d bytes to /log.txt\n", n);
}put_number exists because kprintf prints to
the console and there is no snprintf in the kernel; the
parsing loop is the inverse, reading the digits after boot.
kmain calls log_boot, then
cat("/log.txt") to read the file back through the read path
of the first half of the chapter, and lists / again, so
that the directory entry shows. On the first boot of a freshly built
image, the serial output has:
ext2: wrote 45 bytes to /log.txt
/log.txt (45 bytes):
boot 1 of this disk image, written at tick 2
/:
inode 2 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 11 dir 12288 bytes lost+found
inode 12 dir 1024 bytes bin
inode 15 dir 1024 bytes etc
inode 17 file 45 bytes log.txtInode 17, as s_first_ino = 11 and the six inodes
mke2fs created (11 to 16) predicted; 45 bytes. The tick
count is small because the disk is read and written in a few
milliseconds of emulated time. Now the part that cannot be shown with a
read-only file system. make test rebuilds the image every
time, so to boot the same image a second time we run QEMU by hand, with
the command line of the Makefile and a timeout to end
it:
$ timeout 10 qemu-system-i386 -machine q35 -device piix3-ide,id=ide \
-drive id=disk,format=raw,file=build/disk.img,if=none \
-device ide-hd,drive=disk,bus=ide.0 -serial stdio -display none -monitor none
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
ata: primary master "QEMU HARDDISK", 16384 sectors (8192 KiB)
ext2: volume "os01", block size 1024, 1792 inodes, 7168 blocks, revision 1
/:
inode 2 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 11 dir 12288 bytes lost+found
inode 12 dir 1024 bytes bin
inode 15 dir 1024 bytes etc
inode 17 file 45 bytes log.txt
/bin:
inode 12 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 13 file 2528 bytes count
inode 14 file 2532 bytes hello
/etc/motd (98 bytes):
Welcome to the os01 kernel, chapter 14.
This text was read from /etc/motd on the ext2 filesystem.
ext2: wrote 45 bytes to /log.txt
/log.txt (45 bytes):
boot 2 of this disk image, written at tick 2
/:
inode 2 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 11 dir 12288 bytes lost+found
inode 12 dir 1024 bytes bin
inode 15 dir 1024 bytes etc
inode 17 file 45 bytes log.txt
exec /bin/hello: segment 0 at 0x08048000, 343 bytes in file, 343 in memory
exec /bin/count: segment 0 at 0x08048000, 331 bytes in file, 331 in memory
Hello from user space, pid 1
[task 1 (/bin/hello) exited with status 0]
count: 1
count: 2
count: 3
count: 4
count: 5
[task 2 (/bin/count) exited with status 0]
all processes finished, 32443 frames free
qemu-system-i386: terminating on signal 15 from pid 180 (timeout)boot 2. The first boot’s line was read, parsed and
replaced, and the root listing printed before anything was written
already shows log.txt, 45 bytes, inode 17. The number
increases at every boot for as long as the image is not rebuilt.
14.5.6 What e2fsck thinks
of it
The kernel reading back its own writes proves little: a file system
that is wrong in the same way twice reads fine. The test that matters is
whether the tools that define ext2 accept the disk. debugfs
prints the file, and e2fsck -f checks the file system from
top to bottom even though it is marked clean (-n answers no
to every repair, and makes the exit status 0 only if there was nothing
to repair):
$ dd if=build/disk.img of=build/fs.img bs=512 skip=2048 status=none
$ debugfs -R "cat /log.txt" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
boot 2 of this disk image, written at tick 2
$ e2fsck -fn build/fs.img
e2fsck 1.47.2 (1-Jan-2025)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
os01: 17/1792 files (0.0% non-contiguous), 504/7168 blocksFive passes and a summary line: 17 inodes used of 1792, 504 blocks of
7168, one more of each than before the kernel ran, and no complaint.
This is why the chapter’s make test ends with these two
commands rather than with the serial output:
Makefile (excerpt)
# Boot headless with COM1 captured to a file and wait for the user
# program's greeting, the line the kernel read back from the file it
# wrote, and the kernel's final message. Then let the host's tools judge
# what the kernel wrote: e2fsck checks the whole filesystem (-f even if it
# is marked clean, -n without changing anything; it exits 0 only when
# nothing is wrong) and debugfs prints the file. Both want a file that
# starts with the filesystem, hence the dd that strips the first MiB.
FS_IMG=$(BUILD_DIR)/fs.img
test: bootdisk
QEMU_MACHINE="$(QEMU_MACHINE)" QEMU_DRIVE_ARGS="$(QEMU_DRIVE_ARGS)" \
../../../tools/serial-test.sh $(DISK_IMG) "Hello from user space" 20 \
"boot 1 of this disk image" "all processes finished"
dd if=$(DISK_IMG) of=$(FS_IMG) bs=512 skip=2048 status=none
e2fsck -fn $(FS_IMG)
debugfs -R "cat /log.txt" $(FS_IMG)What the check covers is worth spelling out, pass by pass, because
each pass is one of the invariants we maintained by hand. Pass 1 walks
every inode in use and checks that its blocks are in range, used by no
other inode, and consistent with i_size and
i_blocks. Pass 2 walks every directory block and checks
that the rec_lens add up, that the names are sane and that
every entry points to an inode in use. Pass 3 checks that every
directory is reachable from the root. Pass 4 compares the
i_links_count of each inode with the number of entries
found pointing to it, and this is where an inode without a name is sent
to lost+found. Pass 5 recomputes the bitmaps and the free
counts from what the first four passes saw, and compares them with the
bitmaps and counts on the disk. Corrupt any of the eleven writes above
and one of the five passes names it; exercise 14.9 does this on
purpose.
debugfs lets us compare the kernel’s work with
mke2fs’s, field by field:
$ debugfs -R "stat /log.txt" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
Inode: 17 Type: regular Mode: 0644 Flags: 0x0
Generation: 0 Version: 0x00000000
User: 0 Group: 0 Size: 45
File ACL: 0
Links: 1 Blockcount: 2
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x6ac9c7e9 -- Sat Oct 10 05:06:49 2026
atime: 0x6ac9c7df -- Sat Oct 10 05:06:39 2026
mtime: 0x6ac9c7e9 -- Sat Oct 10 05:06:49 2026
Size of extra inode fields: 0
BLOCKS:
(0):503
TOTAL: 1
TOTAL: 1
$ debugfs -R "ls -l /" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
2 40755 (2) 0 0 1024 10-Oct-2026 05:06 .
2 40755 (2) 0 0 1024 10-Oct-2026 05:06 ..
11 40700 (2) 0 0 12288 10-Oct-2026 05:06 lost+found
12 40755 (2) 1000 1000 1024 10-Oct-2026 05:06 bin
15 40755 (2) 1000 1000 1024 10-Oct-2026 05:06 etc
17 100644 (1) 0 0 45 10-Oct-2026 05:06 log.txtMode 0644, one link, 45 bytes, two 512-byte sectors,
block 503, and timestamps in UTC from the real-time clock:
atime is from the first boot, when ext2_create
set all three, ctime and mtime are ten seconds
later, from the second boot’s rewrite. The root directory
(. and ..) carries the time the kernel added
the entry, in i_mtime.
Size of extra inode fields: 0 is the 128 bytes we left zero
where mke2fs writes 32. Finally example 14.5’s prediction
about the bitmaps:
$ hexdump -C -s 30720 -n 80 build/fs.img
00007800 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
*
00007830 ff ff ff ff ff ff ff ff ff ff ff ff ff ff 7f 00 |................|
00007840 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00007850
$ hexdump -C -s 31744 -n 16 build/fs.img
00007c00 ff ff 01 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00007c10Byte 62 (0x7800 + 0x3e) of the block bitmap is
7f, byte 2 of the inode bitmap is 01, and
debugfs reads the same bits:
$ debugfs -R "testb 503" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
Block 503 marked in use
$ debugfs -R "testi <17>" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
Inode 17 is marked in useThe disk image a Linux kernel would mount, and e2fsck
passes, is the only certificate a file system implementation can get.
From here, every missing feature, listed in “Where this leaves us”, is a
matter of more of the same.
14.6 Loading a program from disk
14.6.1 The user side
A program on the disk cannot share anything with the kernel: no
headers, no library, no linker script. The user/ directory
therefore holds a tiny, self-contained world. Its C runtime is three
instructions:
user/crt0.asm
;******************************************************************************
; crt0.asm -- the C runtime of our user space: 3 instructions.
;
; The kernel enters the program at _start (e_entry in the ELF header) in
; ring 3 with ESP at the top of the user stack. A real crt0 would set up
; argc/argv and call global constructors; ours just calls main() and
; turns its return value into exit(status) with INT 0x80 (SYS_EXIT = 3,
; see syscall.h): a program must never "return" from _start, there is no
; caller to return to.
;******************************************************************************
bits 32
section .text
global _start
extern main
_start:
call main
mov ebx, eax ; exit status = return value of main
mov eax, 3 ; SYS_EXIT
int 0x80
.hang:
jmp .hang ; not reached: exit() does not returncrt0 is the traditional name (“C runtime, zero”) of the
object that gcc links in front of every program and that
calls main; chapter 5 met _start in the hosted
hello, where it is glibc’s and does a great
deal more. Ours passes the return value of main to
exit, which is what the C standard promises:
return 0; from main and exit(0)
are the same thing. The kernel enters the program at _start
with the stack pointer at the top of a fresh page and nothing on the
stack, so there is nowhere to return to; the int 0x80 never
comes back, and the jmp after it is a belt to go with the
braces.
The system call wrappers are the same int 0x80
convention as chapter 13, with the number in EAX, arguments
in EBX, ECX, EDX and the result
in EAX; write now passes the length of the
string, which the kernel checks before reading a byte of it, and
gettime and sleep are two calls that
hello and count do not use yet:
user/syscall.h
#ifndef USER_SYSCALL_H
#define USER_SYSCALL_H
/* The system call interface as a user program sees it. The numbers and
the register convention (EAX = number, EBX/ECX/EDX = arguments, EAX =
result, INT 0x80) must match os/syscall.h; this file is deliberately
self-contained because user programs do not include kernel headers. */
#define SYS_WRITE 1
#define SYS_YIELD 2
#define SYS_EXIT 3
#define SYS_GETPID 4
#define SYS_GETTIME 5
#define SYS_SLEEP 6
static inline int syscall3(int number, int arg1, int arg2, int arg3)
{
int result;
asm volatile("int $0x80"
: "=a"(result)
: "a"(number), "b"(arg1), "c"(arg2), "d"(arg3)
: "memory");
return result;
}
/* write(buf, len) is what the kernel offers (chapter 13, "Validating what
user mode hands us"); this wrapper counts the string for the caller. */
static inline int write(const char *s)
{
int len = 0;
while (s[len] != '\0')
len++;
return syscall3(SYS_WRITE, (int)s, len, 0);
}
static inline void yield(void)
{
syscall3(SYS_YIELD, 0, 0, 0);
}
static inline void exit(int status)
{
syscall3(SYS_EXIT, status, 0, 0);
}
static inline int getpid(void)
{
return syscall3(SYS_GETPID, 0, 0, 0);
}
/* Timer ticks since boot, 100 per second. */
static inline unsigned gettime(void)
{
return (unsigned)syscall3(SYS_GETTIME, 0, 0, 0);
}
/* Do not come back before `nticks` ticks have passed. */
static inline void sleep(int nticks)
{
syscall3(SYS_SLEEP, nticks, 0, 0);
}
#endifThis file is the system programming interface of chapter 9’s
introduction, made concrete: a user program includes it and calls
write() without knowing or caring how the kernel does it.
The duplication of the SYS_ numbers with
os/syscall.h is deliberate; on a real system the two copies
are the kernel’s unistd.h and the C library’s, and they
must agree in the same way.
The two programs:
user/hello.c
/* hello.c -- the first program that is not part of the kernel. */
#include "syscall.h"
int main(void)
{
char msg[] = "Hello from user space, pid ?\n";
msg[27] = '0' + getpid();
write(msg);
return 0;
}user/count.c
/* count.c -- counts to 5, giving the CPU away between numbers. */
#include "syscall.h"
int main(void)
{
char msg[] = "count: ?\n";
int i;
for (i = 1; i <= 5; i++) {
msg[7] = '0' + i;
write(msg);
yield();
}
return 0;
}There is no printf and no %d; patching one
character into a local array is what passes for formatting without a
library. Note that msg is a local array, initialized on the
stack by main itself, so that the program has no
.data section at all; we will see the consequence in
readelf.
14.6.2 Where a user program lives
The linker script decides where in the 4 GiB virtual address space
the program is placed, and the choice is constrained by chapter 12,
Memory management, and chapter 13: the kernel identity-maps physical
memory up to PMM_MAX_MEMORY, 128 MiB, in every address
space, and places the user stack just below 0x80000000, so
a program must go between the two. Linux put its i386 executables at
0x08048000 for twenty years, 128 MiB plus a little, and the
same number suits us.
user/user.lds
/* Linker script for user programs. 0x08048000 is where Linux i386
executables have always been linked (128 MiB + 0x48000, a historical
SVR4 convention) and it suits us: our kernel identity-maps at most the
first 128 MiB, so nothing of the kernel is mapped there.
The ELF header and program headers are part of the first segment, as
in the executables chapter 5 took apart: the segment starts at
0x08048000 and the code right after the headers. Without
"+ SIZEOF_HEADERS", ld would have to pad the file to the next page to
keep file offsets and addresses congruent. */
ENTRY(_start);
SECTIONS
{
. = 0x08048000 + SIZEOF_HEADERS;
.text : { *(.text .text.*) }
.rodata : { *(.rodata .rodata.*) }
.data : { *(.data .data.*) }
.bss : { *(.bss .bss.*) *(COMMON) }
/DISCARD/ : { *(.eh_frame) *(.note.*) *(.comment) }
}SIZEOF_HEADERS is the size of the ELF header plus the
program header table, which ld knows once it has decided
how many program headers to emit. Starting .text right
after them, as chapter 8, Linking and loading on bare metal, did for the
kernel, makes the first LOAD segment start at file offset 0
and virtual address 0x08048000 with the headers inside it,
and the code at offset 0x80. The alternative,
. = 0x08048000; with .text on the next page
boundary, costs 4 KiB of zeros in every file, and is what produced the
sparse file of the hole story above.
user/Makefile
BUILD_DIR=../build/user
PROGRAMS=$(BUILD_DIR)/hello $(BUILD_DIR)/count
# The same freestanding flags as the kernel: no libc, no PIE, no stack
# protector, no CET instructions. -O0 keeps the code readable in gdb.
CFLAGS=-ffreestanding -nostdlib -m32 -no-pie -fno-pie -fno-stack-protector \
-fcf-protection=none -fno-asynchronous-unwind-tables -O0 -g -Wall -Wextra
all: $(PROGRAMS)
$(BUILD_DIR)/crt0.o: crt0.asm
mkdir -p $(BUILD_DIR)
nasm -f elf32 -F dwarf -g $< -o $@
$(BUILD_DIR)/%.o: %.c syscall.h
mkdir -p $(BUILD_DIR)
gcc $(CFLAGS) -c $< -o $@
# crt0.o first so that _start is the first instruction of .text.
# -z noseparate-code: let the ELF header and the code share a page, so the
# file is not padded to a 4 KiB boundary (the loader does not care, but a
# 6 KiB file for 200 bytes of code looks silly in a listing).
$(BUILD_DIR)/%: $(BUILD_DIR)/crt0.o $(BUILD_DIR)/%.o user.lds
ld -m elf_i386 --no-warn-rwx-segments -z noseparate-code -T user.lds $(BUILD_DIR)/crt0.o $(BUILD_DIR)/$*.o -o $@
clean:
rm -rf $(BUILD_DIR)The flags are the bare-metal set of chapter 0 and appendix A, for the
same reasons as the kernel: no C library exists here, and no runtime
support for position-independent code, stack canaries or control-flow
enforcement. -z noseparate-code tells ld not
to put code and headers in separate pages, which modern binutils do by
default for security (so that no page is both writable and executable,
and headers are not executable); with the linker script above, it makes
the difference between a 2532-byte file and a 6 KiB one. What
ld produced:
$ readelf -l build/user/hello
Elf file type is EXEC (Executable file)
Entry point 0x8048080
There are 2 program headers, starting at offset 52
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x000000 0x08048000 0x08048000 0x00157 0x00157 R E 0x1000
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x10
Section to Segment mapping:
Segment Sections...
00 .text
01 Compare with example 5.19 in chapter 5, which had 14 program headers;
we have two, and only the LOAD one matters to a loader:
“copy 0x157 bytes from file offset 0 to virtual address
0x08048000, make them readable and executable”.
FileSiz equals MemSiz because there is no
.bss: hello has no global variables at all.
The entry point is 0x08048080: 0x08048000 + 52
bytes of ELF header + 2 * 32 bytes of program headers
= 0x08048074, rounded up to the 16-byte alignment of
.text. The GNU_STACK header is a note to the
Linux kernel about stack permissions, and elf.c ignores
anything that is not PT_LOAD. The rest of the 2532-byte
file, from offset 0x157 on, is DWARF debugging information
and symbol tables, which readelf -S lists and which no
loader reads: it is what lets gdb show hello.c
source lines once the program runs.
$ objdump -d -M intel build/user/hello
build/user/hello: file format elf32-i386
Disassembly of section .text:
08048080 <_start>:
8048080: e8 77 00 00 00 call 80480fc <main>
8048085: 89 c3 mov ebx,eax
8048087: b8 03 00 00 00 mov eax,0x3
804808c: cd 80 int 0x80
0804808e <_start.hang>:
804808e: eb fe jmp 804808e <_start.hang>
08048090 <syscall3>:
8048090: 55 push ebp
8048091: 89 e5 mov ebp,esp
8048093: 53 push ebx
8048094: 83 ec 10 sub esp,0x10
8048097: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
804809a: 8b 5d 0c mov ebx,DWORD PTR [ebp+0xc]
804809d: 8b 4d 10 mov ecx,DWORD PTR [ebp+0x10]
80480a0: 8b 55 14 mov edx,DWORD PTR [ebp+0x14]
80480a3: cd 80 int 0x80
80480a5: 89 45 f8 mov DWORD PTR [ebp-0x8],eax
80480a8: 8b 45 f8 mov eax,DWORD PTR [ebp-0x8]
80480ab: 8b 5d fc mov ebx,DWORD PTR [ebp-0x4]
80480ae: c9 leave
80480af: c3 ret
080480b0 <write>:
80480b0: 55 push ebp
80480b1: 89 e5 mov ebp,esp
80480b3: 83 ec 10 sub esp,0x10
80480b6: c7 45 fc 00 00 00 00 mov DWORD PTR [ebp-0x4],0x0
80480bd: eb 04 jmp 80480c3 <write+0x13>
80480bf: 83 45 fc 01 add DWORD PTR [ebp-0x4],0x1
80480c3: 8b 55 fc mov edx,DWORD PTR [ebp-0x4]
80480c6: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
80480c9: 01 d0 add eax,edx
80480cb: 0f b6 00 movzx eax,BYTE PTR [eax]
80480ce: 84 c0 test al,al
80480d0: 75 ed jne 80480bf <write+0xf>
80480d2: 8b 45 08 mov eax,DWORD PTR [ebp+0x8]
80480d5: 6a 00 push 0x0
80480d7: ff 75 fc push DWORD PTR [ebp-0x4]
80480da: 50 push eax
80480db: 6a 01 push 0x1
80480dd: e8 ae ff ff ff call 8048090 <syscall3>
80480e2: 83 c4 10 add esp,0x10
80480e5: c9 leave
80480e6: c3 ret
080480e7 <getpid>:
80480e7: 55 push ebp
80480e8: 89 e5 mov ebp,esp
80480ea: 6a 00 push 0x0
80480ec: 6a 00 push 0x0
80480ee: 6a 00 push 0x0
80480f0: 6a 04 push 0x4
80480f2: e8 99 ff ff ff call 8048090 <syscall3>
80480f7: 83 c4 10 add esp,0x10
80480fa: c9 leave
80480fb: c3 ret
080480fc <main>:
80480fc: 55 push ebp
80480fd: 89 e5 mov ebp,esp
80480ff: 83 ec 20 sub esp,0x20
8048102: c7 45 e2 48 65 6c 6c mov DWORD PTR [ebp-0x1e],0x6c6c6548
8048109: c7 45 e6 6f 20 66 72 mov DWORD PTR [ebp-0x1a],0x7266206f
8048110: c7 45 ea 6f 6d 20 75 mov DWORD PTR [ebp-0x16],0x75206d6f
8048117: c7 45 ee 73 65 72 20 mov DWORD PTR [ebp-0x12],0x20726573
804811e: c7 45 f2 73 70 61 63 mov DWORD PTR [ebp-0xe],0x63617073
8048125: c7 45 f6 65 2c 20 70 mov DWORD PTR [ebp-0xa],0x70202c65
804812c: c7 45 fa 69 64 20 3f mov DWORD PTR [ebp-0x6],0x3f206469
8048133: 66 c7 45 fe 0a 00 mov WORD PTR [ebp-0x2],0xa
8048139: e8 a9 ff ff ff call 80480e7 <getpid>
804813e: 83 c0 30 add eax,0x30
8048141: 88 45 fd mov BYTE PTR [ebp-0x3],al
8048144: 8d 45 e2 lea eax,[ebp-0x1e]
8048147: 50 push eax
8048148: e8 63 ff ff ff call 80480b0 <write>
804814d: 83 c4 04 add esp,0x4
8048150: b8 00 00 00 00 mov eax,0x0
8048155: c9 leave
8048156: c3 retThe whole program is 215 bytes of code (0x157 - 0x80),
and all of it is in front of you: _start, the generic
wrapper syscall3 with its int 0x80 at
0x80480a3, the two wrappers the program uses
(write, whose loop counts the string before the call, and
getpid; yield and exit are
static inline and unused, so gcc emitted
nothing for them), and main, which builds its string four
bytes at a time with mov immediates
(0x6c6c6548 is “Hell” backwards: little-endian again) and
then patches the byte at [ebp-0x3], which is
msg[27]. These are the addresses that gdb will
show when we stop inside the program.
14.6.3 The loader: elf.c
The loader is the mirror image of chapter 5. There we read the headers to understand a file; here the kernel reads them to build a process. The header file declares the two structures with the names of the ELF specification (Tool Interface Standard, “Executable and Linking Format (ELF) Specification”, version 1.2, sections “ELF Header” and “Program Header”):
os/elf.h
#ifndef ELF_H
#define ELF_H
#include <stdint.h>
#include "task.h"
/* ELF32 file and program headers, with the field names of the ELF
specification (Tool Interface Standard, "Executable and Linking Format
(ELF) Specification", version 1.2: "ELF Header", "Program Header"). */
#define EI_NIDENT 16
struct elf32_ehdr {
uint8_t e_ident[EI_NIDENT]; /* magic, class, data encoding... */
uint16_t e_type; /* ET_EXEC for an executable */
uint16_t e_machine; /* EM_386 */
uint32_t e_version;
uint32_t e_entry; /* virtual address of the first instruction */
uint32_t e_phoff; /* file offset of the program header table */
uint32_t e_shoff;
uint32_t e_flags;
uint16_t e_ehsize;
uint16_t e_phentsize; /* size of one program header */
uint16_t e_phnum; /* number of program headers */
uint16_t e_shentsize;
uint16_t e_shnum;
uint16_t e_shstrndx;
} __attribute__((packed));
struct elf32_phdr {
uint32_t p_type; /* PT_LOAD: copy this segment into memory */
uint32_t p_offset; /* where the segment starts in the file */
uint32_t p_vaddr; /* where it goes in memory */
uint32_t p_paddr;
uint32_t p_filesz; /* bytes in the file... */
uint32_t p_memsz; /* ...and in memory; the rest is zeroed (.bss) */
uint32_t p_flags; /* PF_X, PF_W, PF_R */
uint32_t p_align;
} __attribute__((packed));
#define ELFMAG0 0x7F
#define ELFCLASS32 1 /* e_ident[EI_CLASS] */
#define EI_CLASS 4
#define ET_EXEC 2
#define EM_386 3
#define PT_LOAD 1
/* Load the executable at `path` from the filesystem into a new page
directory and create a user task for it. Returns 0 on failure. */
struct task *elf_exec(const char *path);
#endifThe loader needs five fields of the ELF header (e_ident
for the checks, e_entry, e_phoff,
e_phentsize, e_phnum) and five of each program
header (p_type, p_offset,
p_vaddr, p_filesz, p_memsz).
Section headers, which chapter 5 spent most of its time on, are not read
at all: a loader works with segments, as that chapter said.
os/elf.c (part 1)
/* elf.c -- load a user program from an ELF file into its own address space.
*
* Chapter 5 took ELF files apart; this is the other direction. Only the
* program headers matter to a loader: each PT_LOAD segment says "put
* p_filesz bytes from file offset p_offset at virtual address p_vaddr,
* then zero up to p_memsz". The pages come from the frame allocator and
* are mapped with the USER bit in a directory cloned from the kernel's;
* the kernel copies into them through their physical (identity-mapped)
* address, since the user addresses are not mapped in the directory that
* is active now.
*/
#include "elf.h"
#include "ext2.h"
#include "paging.h"
#include "pmm.h"
#include "heap.h"
#include "printf.h"
#include "string.h"
/* User programs live above the identity-mapped RAM (at most PMM_MAX_MEMORY)
and below the user stack. */
#define USER_SPACE_START PMM_MAX_MEMORY
/* Make sure every page of [virt, virt + size) is mapped in `dir`, with a
fresh zeroed frame where there was none. */
static int map_range(uint32_t *dir, uint32_t virt, uint32_t size)
{
uint32_t addr, end = PAGE_ALIGN_UP(virt + size);
for (addr = PAGE_ALIGN_DOWN(virt); addr < end; addr += PAGE_SIZE) {
uint32_t frame;
if (paging_lookup(dir, addr) != 0)
continue; /* shared with a previous segment */
frame = pmm_alloc_frame();
if (frame == 0)
return -1;
memset((void *)frame, 0, PAGE_SIZE); /* this is what zeroes .bss */
paging_map_in(dir, addr, frame, PAGE_WRITE | PAGE_USER);
}
return 0;
}
/* memcpy into another address space, one page at a time. */
static void copy_to_dir(uint32_t *dir, uint32_t virt, const void *src, uint32_t len)
{
const uint8_t *s = src;
while (len > 0) {
uint32_t frame = paging_lookup(dir, virt);
uint32_t offset = virt & (PAGE_SIZE - 1);
uint32_t chunk = PAGE_SIZE - offset < len ? PAGE_SIZE - offset : len;
memcpy((void *)(frame + offset), s, chunk);
virt += chunk;
s += chunk;
len -= chunk;
}
}The subtle point of a loader is that it builds an address space
it is not running in. The program’s pages must appear at
0x08048000 in the new task’s page directory, but the kernel
is executing with its own directory in CR3, where
0x08048000 is not mapped; we saw in chapter 12 that
touching such an address is a page fault. The two helpers deal with this
by never using user addresses: map_range allocates frames
and enters them into the other directory with
paging_map_in, the chapter 13 function that takes the
directory as a parameter, and copy_to_dir writes the file’s
bytes through the physical address of each frame, which the
kernel can always use because all of RAM is identity-mapped.
paging_lookup, the one function added to
paging.c this chapter, walks the directory and page table
to find that physical address:
os/paging.c (addition)
uint32_t paging_lookup(uint32_t *dir, uint32_t virt)
{
uint32_t pde = dir[PAGE_DIR_INDEX(virt)], pte;
if (!(pde & PAGE_PRESENT))
return 0;
pte = ((uint32_t *)(pde & PAGE_FRAME))[PAGE_TABLE_INDEX(virt)];
return (pte & PAGE_PRESENT) ? (pte & PAGE_FRAME) : 0;
}This is the page walk of the Intel SDM Volume 3A, section 5.3, done in software: bits 31:22 index the directory, the entry gives the page table, bits 21:12 index the table, the entry gives the frame. We will do the same walk by hand in gdb.
map_range also does the job that
p_memsz > p_filesz asks for. The ELF specification says
that the bytes between p_filesz and p_memsz
must be zero: that is where .bss, the uninitialized data,
lives, and it is why a program with a megabyte of zero-initialized
arrays is a small file. Since every frame is cleared with
memset before it is mapped, and the file is only copied
over the first p_filesz bytes, the rest is zero by
construction; chapter 8’s _start had to clear the kernel’s
.bss itself because nobody had done it for it.
os/elf.c (part 2)
struct task *elf_exec(const char *path)
{
struct ext2_inode inode;
struct elf32_ehdr *eh;
uint32_t ino = ext2_lookup(path), *dir;
uint8_t *file;
int i;
if (ino == 0 || ext2_read_inode(ino, &inode) < 0
|| (inode.i_mode & EXT2_S_IFMT) != EXT2_S_IFREG) {
kprintf("exec %s: no such file\n", path);
return 0;
}
file = kmalloc(inode.i_size);
if (ext2_read_file(&inode, file, inode.i_size) < 0) {
kprintf("exec %s: read error\n", path);
kfree(file);
return 0;
}
eh = (struct elf32_ehdr *)file;
if (inode.i_size < sizeof(*eh) || eh->e_ident[0] != ELFMAG0
|| memcmp(eh->e_ident + 1, "ELF", 3) != 0
|| eh->e_ident[EI_CLASS] != ELFCLASS32
|| eh->e_type != ET_EXEC || eh->e_machine != EM_386) {
kprintf("exec %s: not a 32-bit x86 ELF executable\n", path);
kfree(file);
return 0;
}
dir = paging_clone_kernel_directory();
for (i = 0; i < eh->e_phnum; i++) {
struct elf32_phdr *ph =
(struct elf32_phdr *)(file + eh->e_phoff + i * eh->e_phentsize);
if (ph->p_type != PT_LOAD)
continue;
if (ph->p_vaddr < USER_SPACE_START
|| ph->p_vaddr + ph->p_memsz > USER_STACK_TOP - USER_STACK_SIZE
|| ph->p_offset + ph->p_filesz > inode.i_size) {
kprintf("exec %s: segment %d outside user space\n", path, i);
paging_free_directory(dir);
kfree(file);
return 0;
}
kprintf("exec %s: segment %d at %p, %u bytes in file, %u in memory\n",
path, i, (void *)ph->p_vaddr, ph->p_filesz, ph->p_memsz);
if (map_range(dir, ph->p_vaddr, ph->p_memsz) < 0) {
kprintf("exec %s: out of memory\n", path);
paging_free_directory(dir);
kfree(file);
return 0;
}
copy_to_dir(dir, ph->p_vaddr, file + ph->p_offset, ph->p_filesz);
}
kfree(file);
return task_create_user_in(path, dir, eh->e_entry);
}Read elf_exec top to bottom and it is the chapter in one
function. Find the file (ext2_lookup,
ext2_read_inode), refuse directories; read it whole into
the kernel heap (2.5 KiB, we can afford it; a real loader reads segments
on demand, or maps the file and lets page faults do the reading). Check
that it is an ELF file (0x7F, E,
L, F), 32-bit, an executable rather than an
object or a shared library, and for the i386; a kernel that skipped
these checks would happily jump into a text file. Clone the kernel’s
page directory, so that the kernel is present (supervisor-only) in the
new address space, as it must be for the system call handler to run.
Then, for each PT_LOAD program header, check that the
segment lies in user space, map it, copy it. The check against
USER_SPACE_START, which is PMM_MAX_MEMORY, is
a security check, not a formality: a program linked at
0x10000 would ask the loader to map user-accessible pages
over the kernel’s own code, and map_range would skip the
allocation because the address is already mapped and
copy_to_dir would overwrite the kernel. The upper bound
keeps the program below the user stack, and the third condition stops a
header that points outside the file.
The last line hands the finished address space to the scheduler.
task_create_user of chapter 13 both built the directory and
created the task; chapter 14 splits it, and the chapter 13 function now
wraps the new one:
os/task.c (changed part)
struct task *task_create_user_in(const char *name, uint32_t *dir, uint32_t entry)
{
uint32_t frame;
struct task *t;
/* One page of user stack, in a fresh frame. */
frame = pmm_alloc_frame();
if (frame == 0)
panic("task_create_user: out of frames");
paging_map_in(dir, USER_STACK_TOP - USER_STACK_SIZE, frame, PAGE_WRITE | PAGE_USER);
t = task_alloc(name, (void (*)(void))entry, user_task_start, dir);
t->user_stack_top = USER_STACK_TOP;
return t;
}
struct task *task_create_user(const char *name, void (*entry)(void))
{
uint32_t *dir = paging_clone_kernel_directory();
uint32_t addr;
/* The user program's code and data are part of the kernel image
(os.lds collects userprog.c into the page-aligned .user section);
giving those pages the USER bit is what lets ring 3 execute them.
Every other kernel page stays supervisor-only. */
for (addr = (uint32_t)__user_start; addr < (uint32_t)__user_end; addr += PAGE_SIZE)
paging_map_in(dir, addr, addr, PAGE_WRITE | PAGE_USER);
return task_create_user_in(name, dir, (uint32_t)entry);
}task_create_user_in adds the one thing the ELF file does
not describe, the stack: a page at 0x7FFFF000, and from
there everything is as in chapter 13: task_alloc builds the
kernel stack of the task so that the first context switch “returns” into
user_task_start, which does the iret into ring
3 at entry, the e_entry of the file, with
ESP at USER_STACK_TOP. The old
task_create_user and userprog.c are still
compiled, though kmain no longer calls them; the comparison
between the two functions is the whole difference between a program
baked into the kernel and a program loaded from disk.
One more small change closes the loop with crt0.asm:
SYS_EXIT now takes the exit status in EBX and
the kernel prints it:
os/syscall.c (changed part)
case SYS_EXIT:
kprintf("[task %d (%s) exited with status %d]\n",
current_task->id, current_task->name, (int)regs->ebx);
task_exit();A real kernel would keep the status in the task structure for the
parent to collect with wait(); ours has no parent
processes, so printing it is all the use it gets.
14.7 The kernel
os/kernel.c (excerpt)
/* Print a text file from the filesystem. */
static void cat(const char *path)
{
struct ext2_inode inode;
uint32_t ino = ext2_lookup(path);
char *text;
if (ino == 0 || ext2_read_inode(ino, &inode) < 0) {
kprintf("%s: not found\n", path);
return;
}
text = kmalloc(inode.i_size + 1);
if (ext2_read_file(&inode, text, inode.i_size) < 0) {
kprintf("%s: read error\n", path);
} else {
text[inode.i_size] = '\0';
kprintf("%s (%u bytes):\n%s", path, inode.i_size, text);
}
kfree(text);
}put_number and log_boot, quoted in the
section “Something that survives a reboot”, come next in the file; then
kmain:
void kmain(void)
{
const struct ext2_superblock *sb;
gdt_init();
console_init();
idt_init();
pic_init();
pit_init(TIMER_HZ);
keyboard_init();
asm volatile("sti");
kprintf("Hello World from the kernel!\n");
cpuid_print();
pmm_init();
paging_init();
heap_init();
tss_init();
syscall_init();
task_init();
/* 1. The disk and the filesystem on it. */
if (ata_identify() < 0)
panic("no ATA disk: see the comment on QEMU_DRIVE_ARGS in the Makefile");
if (ext2_mount() < 0)
panic("no ext2 filesystem at sector 2048");
sb = ext2_superblock();
kprintf("ext2: volume \"%s\", block size %u, %u inodes, %u blocks, revision %u\n",
sb->s_volume_name, ext2_block_size(), sb->s_inodes_count,
sb->s_blocks_count, sb->s_rev_level);
ext2_list_dir("/");
ext2_list_dir("/bin");
cat("/etc/motd");
/* 2. Something that survives the next boot. */
log_boot();
cat("/log.txt");
ext2_list_dir("/");
/* 3. Programs that were never part of the kernel image. */
elf_exec("/bin/hello");
elf_exec("/bin/count");
/* 4. kmain is the idle task again, until they are all gone. */
for (;;) {
if (task_reap() == 0)
break;
asm volatile("hlt");
}
kprintf("all processes finished, %u frames free\n", pmm_free_frames_count());
for (;;)
asm volatile("hlt");
}The initialization sequence is that of chapter 13 up to
task_init, plus cpuid_print, which names the
processor. Then the layers of this chapter are exercised in order:
identify the disk, mount the file system, list two directories, print a
text file with cat, a dozen lines that would be the start
of a shell; write /log.txt and read it back, as the section
“Writing to the file system” showed. elf_exec is called
twice, which creates two tasks; they run when kmain gives
up the CPU with hlt and the timer interrupt calls the
scheduler, exactly as in chapter 13, and kmain reaps them
as they exit. make test boots the image headless, checks
the serial output for the user program’s greeting, the line read back
from /log.txt and the kernel’s last line, then checks the
file system on the host:
$ make test
....build output omitted....
QEMU_MACHINE="q35" QEMU_DRIVE_ARGS="-device piix3-ide,id=ide -drive id=disk,format=raw,file=build/disk.img,if=none -device ide-hd,drive=disk,bus=ide.0" \
../../../tools/serial-test.sh build/disk.img "Hello from user space" 20 \
"boot 1 of this disk image" "all processes finished"
serial-test: ok, found "Hello from user space" and "boot 1 of this disk image" and "all processes finished"
--- serial output ---
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
ata: primary master "QEMU HARDDISK", 16384 sectors (8192 KiB)
ext2: volume "os01", block size 1024, 1792 inodes, 7168 blocks, revision 1
/:
inode 2 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 11 dir 12288 bytes lost+found
inode 12 dir 1024 bytes bin
inode 15 dir 1024 bytes etc
/bin:
inode 12 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 13 file 2528 bytes count
inode 14 file 2532 bytes hello
/etc/motd (98 bytes):
Welcome to the os01 kernel, chapter 14.
This text was read from /etc/motd on the ext2 filesystem.
ext2: wrote 45 bytes to /log.txt
/log.txt (45 bytes):
boot 1 of this disk image, written at tick 2
/:
inode 2 dir 1024 bytes .
inode 2 dir 1024 bytes ..
inode 11 dir 12288 bytes lost+found
inode 12 dir 1024 bytes bin
inode 15 dir 1024 bytes etc
inode 17 file 45 bytes log.txt
exec /bin/hello: segment 0 at 0x08048000, 343 bytes in file, 343 in memory
exec /bin/count: segment 0 at 0x08048000, 331 bytes in file, 331 in memory
Hello from user space, pid 1
[task 1 (/bin/hello) exited with status 0]
count: 1
count: 2
count: 3
count: 4
count: 5
[task 2 (/bin/count) exited with status 0]
all processes finished, 32443 frames free
qemu-system-i386: terminating on signal 15 from pid 160 (/bin/sh)
dd if=build/disk.img of=build/fs.img bs=512 skip=2048 status=none
e2fsck -fn build/fs.img
e2fsck 1.47.2 (1-Jan-2025)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
os01: 17/1792 files (0.0% non-contiguous), 504/7168 blocks
debugfs -R "cat /log.txt" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
boot 1 of this disk image, written at tick 2Every line comes from something we decoded by hand.
IDENTIFY DEVICE returned “QEMU HARDDISK” in words 27-46 and
16384 in words 60-61: 8 MiB, the size of build/disk.img.
The ext2: line is the superblock of example 14.2. The two
listings are the directory blocks of example 14.4 and its
/bin counterpart, with the sizes read from each inode
(lost+found is preallocated with 12 blocks, hence 12288
bytes). /etc/motd is the 98 bytes of
rootfs/etc/motd. The three groups of lines about
/log.txt were explained in the section “Writing to the file
system”. The two exec lines are the LOAD
program headers of readelf -l: 343 is 0x157.
Then the programs run: hello is task 1, prints and exits
with the 0 that main returned; count is task 2
and its yield() calls hand the CPU to a run queue where
nothing else is ready, so its five lines come out in order. Finally the
frame count: 32443 free frames of the 32768 that make up 128 MiB. The
debugger session below measures 32447 just before the first
elf_exec; the four frames of difference are heap pages that
kmalloc took for the task structures, kernel stacks and
file buffers and keeps, as in chapter 13. After QEMU is killed,
e2fsck and debugfs say that the disk is
consistent and holds the line the kernel wrote. The frames of the
programs themselves, a page directory, a page table, a code page and a
stack page for each task, all came back through task_reap
and paging_free_directory.
One limitation to know about: kprintf is not atomic. If
two tasks print at the same time and the timer interrupt switches
between them in the middle of a line, their characters interleave. The
programs of this chapter avoid it by yielding only between whole lines,
and exercise 14.3 will make it visible.
14.8 A debugger session
The session follows one sector from the ATA ports to a running
process, and stops on the way at the first sector the kernel writes.
Start make qemu in one terminal and make gdb
in another; the chapter’s .gdbinit connects, loads the
kernel’s symbols and breaks at kmain. The first disk read
after kmain is the superblock:
(gdb) b ata_read_sectors
Breakpoint 2 at 0x10699: file ata.c, line 155.
(gdb) c
Breakpoint 2, ata_read_sectors (lba=2050, count=2 '\002', buf=0x170a0 <sb_raw>) at ata.c:155
155 uint8_t *p = buf;
(gdb) x/16i $pc
=> 0x10699 <ata_read_sectors+13>: mov eax,DWORD PTR [ebp+0x10]
0x1069c <ata_read_sectors+16>: mov DWORD PTR [ebp-0xc],eax
0x1069f <ata_read_sectors+19>: mov eax,DWORD PTR [ebp+0x8]
0x106a2 <ata_read_sectors+22>: shr eax,0x18
0x106a5 <ata_read_sectors+25>: and eax,0xf
0x106a8 <ata_read_sectors+28>: or eax,0xffffffe0
0x106ab <ata_read_sectors+31>: movzx eax,al
0x106ae <ata_read_sectors+34>: push eax
0x106af <ata_read_sectors+35>: push 0x1f6
0x106b4 <ata_read_sectors+40>: call 0x102f7 <outb>
0x106b9 <ata_read_sectors+45>: add esp,0x8
0x106bc <ata_read_sectors+48>: call 0x1039b <ata_delay_400ns>
0x106c1 <ata_read_sectors+53>: movzx eax,BYTE PTR [ebp-0x1c]
0x106c5 <ata_read_sectors+57>: push eax
0x106c6 <ata_read_sectors+58>: push 0x1f2
0x106cb <ata_read_sectors+63>: call 0x102f7 <outb>LBA 2050, two sectors: ext2_mount reading the superblock
into sb_raw, as example 14.1 predicted. At -O0
the inline outb is a real call, so the port writes are easy
to read: lba >> 24, masked to 4 bits, or-ed with
0xE0, pushed with 0x1f6; then the count with
0x1f2, and so on through the address bytes to the
command:
(gdb) b ata.c:168
Breakpoint 3 at 0x10715: file ata.c, line 168.
(gdb) c
Breakpoint 3, ata_read_sectors (lba=2050, count=2 '\002', buf=0x170a0 <sb_raw>) at ata.c:168
168 outb(ATA_COMMAND, ATA_CMD_READ_SECTORS);
(gdb) x/6i $pc
=> 0x10715 <ata_read_sectors+137>: push 0x20
0x10717 <ata_read_sectors+139>: push 0x1f7
0x1071c <ata_read_sectors+144>: call 0x102f7 <outb>
0x10721 <ata_read_sectors+149>: add esp,0x8
0x10724 <ata_read_sectors+152>: mov DWORD PTR [ebp-0x10],0x0
0x1072b <ata_read_sectors+159>: jmp 0x107a6 <ata_read_sectors+282>
(gdb) b ata.c:177
Breakpoint 4 at 0x1077e: file ata.c, line 177.
(gdb) c
Breakpoint 4, ata_read_sectors (lba=2050, count=2 '\002', buf=0x170a0 <sb_raw>) at ata.c:177
177 insw(ATA_DATA, p, ATA_SECTOR_SIZE / 2);
(gdb) p/x status
$1 = 0x580x20 to port 0x1F7:
READ SECTOR(S). When the loop reaches the
insw, the status the drive answered with is
0x58 = 0101 1000: DRDY, DSC and
DRQ set, BSY and ERR clear. The
drive has the first sector and wants us to take it. Let the function
finish and look at what arrived in ext2_mount’s buffer:
(gdb) delete 4
(gdb) finish
0x00011395 in ext2_mount () at ext2.c:41
41 if (ata_read_sectors(EXT2_PARTITION_LBA + 2, 2, sb_raw) < 0)
Value returned is $2 = 0
(gdb) x/8xh sb_raw
0x170a0 <sb_raw>: 0x0700 0x0000 0x1c00 0x0000 0x0166 0x0000 0x1a09 0x0000The first words of the superblock: 0x700 inodes,
0x1c00 blocks, 0x166 reserved,
0x1a09 free, the hexdump of example 14.2 arriving through
port 0x1F0. Next, the inode of /bin/hello,
with a conditional breakpoint at the end of
ext2_read_inode:
(gdb) delete
(gdb) b ext2.c:89 if ino == 14
Breakpoint 5 at 0x11520: file ext2.c, line 89.
(gdb) c
Breakpoint 5, ext2_read_inode (ino=14, inode=0x8ee98) at ext2.c:89
89 memcpy(inode, buf + offset % block_size, sizeof(*inode));
(gdb) p group
$3 = 0
(gdb) p index
$4 = 13
(gdb) p offset
$5 = 3328
(gdb) p gd->bg_inode_table
$6 = 32
(gdb) p gd->bg_inode_table + offset / block_size
$7 = 35
(gdb) p offset % block_size
$8 = 256
(gdb) p/x inode->i_mode
$9 = 0x81ed
(gdb) p inode->i_size
$10 = 2532
(gdb) p inode->i_blocks
$11 = 6
(gdb) p inode->i_block
$12 = {498, 499, 500, 0 <repeats 12 times>}Group 0, index 13, offset 3328, block 35 at offset 256: example 14.3,
computed by the kernel, and the inode that debugfs stat
printed. The first write comes a little later, when
log_boot runs:
(gdb) delete
(gdb) b ata_write_sectors
Breakpoint 6 at 0x107ca: file ata.c, line 186.
(gdb) c
Breakpoint 6, ata_write_sectors (lba=2110, count=2 '\002', buf=0x8dcd0) at ata.c:186
186 const uint8_t *p = buf;
(gdb) bt
#0 ata_write_sectors (lba=2110, count=2 '\002', buf=0x8dcd0) at ata.c:186
#1 0x00011376 in write_block (block=31, buf=0x8dcd0) at ext2.c:31
#2 0x00011f49 in alloc_inode () at ext2.c:359
#3 0x000123fe in ext2_create (path=0x15981 "/log.txt", mode=420) at ext2.c:474
#4 0x00012585 in ext2_write_file (path=0x15981 "/log.txt", data=0x8ff6c, len=46) at ext2.c:511
#5 0x000130ec in log_boot () at kernel.c:84
#6 0x00013205 in kmain () at kernel.c:123
#7 0x0001011b in _start () at entry.asm:30
(gdb) p/x *(uint8_t *)buf@4
$13 = {0xff, 0xff, 0x1, 0x0}
(gdb) finish
0x00011376 in write_block (block=31, buf=0x8dcd0) at ext2.c:31
31 return ata_write_sectors(EXT2_PARTITION_LBA + block * sectors_per_block,
Value returned is $14 = 0
(gdb) p/x *(uint8_t *)buf@4
$15 = {0xff, 0xff, 0x1, 0x0}The backtrace is the whole write path in one picture, from
kmain down to the port: log_boot calls
ext2_write_file, which finds no /log.txt and
calls ext2_create, whose first act is
alloc_inode, which writes the inode bitmap, block 31,
through write_block and ata_write_sectors, at
LBA 2048 + 2 * 31 = 2110. The first four bytes of the
buffer are ff ff 01 00: inodes 1 to 16 used, and bit 0 of
byte 2, inode 17, just set by bitmap_alloc. After
finish the buffer is unchanged, as a write should leave it,
and the return value is 0. Before the loader runs, note how many frames
are free; we come back to the number at the end:
(gdb) delete
(gdb) b kernel.c:128
Breakpoint 7 at 0x13225: file kernel.c, line 128.
(gdb) c
Breakpoint 7, kmain () at kernel.c:128
128 elf_exec("/bin/hello");
(gdb) p pmm_free_frames_count()
$16 = 32447Now the loader. Stop when the headers have been checked and look at them in the kernel’s copy of the file:
(gdb) delete
(gdb) b elf.c:92
Breakpoint 8 at 0x11185: file elf.c, line 92.
(gdb) c
Breakpoint 8, elf_exec (path=0x15ab2 "/bin/hello") at elf.c:92
92 for (i = 0; i < eh->e_phnum; i++) {
(gdb) p/x eh->e_ident
$17 = {0x7f, 0x45, 0x4c, 0x46, 0x1, 0x1, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}
(gdb) p *eh
$18 = {e_ident = "\177ELF\001\001\001\000\000\000\000\000\000\000\000", e_type = 2, e_machine = 3, e_version = 1, e_entry = 134512768, e_phoff = 52, e_shoff = 2052, e_flags = 0, e_ehsize = 52, e_phentsize = 32, e_phnum = 2, e_shentsize = 40, e_shnum = 12, e_shstrndx = 11}
(gdb) p/x *(struct elf32_phdr *)(file + eh->e_phoff)
$19 = {p_type = 0x1, p_offset = 0x0, p_vaddr = 0x8048000, p_paddr = 0x8048000, p_filesz = 0x157, p_memsz = 0x157, p_flags = 0x5, p_align = 0x1000}
(gdb) p/x *(struct elf32_phdr *)(file + eh->e_phoff + 32)
$20 = {p_type = 0x6474e551, p_offset = 0x0, p_vaddr = 0x0, p_paddr = 0x0, p_filesz = 0x0, p_memsz = 0x0, p_flags = 0x6, p_align = 0x10}This is readelf -h and readelf -l read from
memory: e_type = 2 (ET_EXEC),
e_machine = 3 (EM_386),
e_entry = 134512768 = 0x8048080, two program headers of 32
bytes at offset 52. The first is PT_LOAD
(p_type = 1), with p_flags = 5 for read and
execute; the second has p_type = 0x6474e551, which is
PT_GNU_STACK, and the loop skips it. After the segment has
been mapped and copied, do the page walk by hand in the new
directory:
(gdb) b elf.c:117
Breakpoint 9 at 0x11301: file elf.c, line 117.
(gdb) c
Breakpoint 9, elf_exec (path=0x15ab2 "/bin/hello") at elf.c:117
117 return task_create_user_in(path, dir, eh->e_entry);
(gdb) p dir
$21 = (uint32_t *) 0x121000
(gdb) p/x dir[0x08048000 >> 22]
$22 = 0x123007
(gdb) set $pt = (uint32_t *)(dir[0x08048000 >> 22] & 0xfffff000)
(gdb) p/x $pt[(0x08048000 >> 12) & 0x3ff]
$23 = 0x122007
(gdb) set $frame = $pt[(0x08048000 >> 12) & 0x3ff] & 0xfffff000
(gdb) x/4xb $frame
0x122000: 0x7f 0x45 0x4c 0x46
(gdb) x/4i $frame + 0x80
0x122080: call 0x1220fc
0x122085: mov ebx,eax
0x122087: mov eax,0x3
0x12208c: int 0x80
(gdb) x/4xb 0x08048000
0x8048000: Cannot access memory at address 0x8048000
(gdb) p/x $cr3
$24 = 0x1b000The new directory is at 0x121000. Its entry for
0x08048000 (index 0x20) is
0x123007: a page table at 0x123000 with flags
P, R/W and U/S all set, the
7. The table’s entry 0x48 is
0x122007: frame 0x122000, same flags. At that
physical address are the bytes 7f 45 4c 46, the ELF header,
and at +0x80 the four instructions of _start.
gdb disassembles the call as going to 0x1220fc
because the instruction is relative and we are looking at it from its
physical address; once the page is at 0x08048000 the same
bytes mean call 0x80480fc, main. Reading
0x08048000 itself fails: CR3 is still
0x1b000, the kernel’s directory, in which that address does
not exist, which is the whole reason copy_to_dir went
through physical addresses. Now let the program run. The chapter’s
.gdbinit has a note about this:
add-symbol-file loads the user program’s symbols at the
addresses its sections already carry.
(gdb) delete
(gdb) add-symbol-file build/user/hello
add symbol table from file "build/user/hello"
(gdb) b main
Breakpoint 10 at 0x80480fc: file hello.c, line 5.
(gdb) c
Breakpoint 10, main () at hello.c:5
5 {
(gdb) info registers eip esp cs ss
eip 0x80480fc 0x80480fc <main>
esp 0x7ffffffc 0x7ffffffc
cs 0x1b 27
ss 0x23 35
(gdb) p/x $cr3
$25 = 0x121000
(gdb) x/4xb 0x08048000
0x8048000: 0x7f 0x45 0x4c 0x46
(gdb) bt
#0 main () at hello.c:5We are in ring 3: CS is 0x1b, the user code
selector of example 9.2, SS is 0x23,
EIP is the main of the objdump
listing, ESP is 0x7ffffffc (the top of the
stack page, minus the return address that _start’s
call pushed), and CR3 is now
0x121000, the directory we walked, so that
0x08048000 reads fine. The backtrace stops at
main because _start has no frame. The first
system call the program makes is getpid:
(gdb) b syscall_handler
Breakpoint 11 at 0x147f9: file syscall.c, line 58.
(gdb) c
Breakpoint 11, syscall_handler (regs=0xc0001fc4) at syscall.c:58
58 switch (regs->eax) {
(gdb) p/x regs->eax
$26 = 0x4
(gdb) p/x regs->eip
$27 = 0x80480a5
(gdb) p/x regs->cs
$28 = 0x1b
(gdb) p current_task->name
$29 = 0x15ab2 "/bin/hello"EAX = 4, SYS_GETPID; the saved
EIP is 0x80480a5, the instruction after the
int 0x80 in syscall3, where iret
will resume; the saved CS is 0x1b; and
regs itself lives at 0xc0001fc4, in the task’s
kernel stack on the kernel heap, where the CPU switched stacks on the
way from ring 3 to ring 0 using the TSS of chapter 13. Finally, the
end:
(gdb) delete
(gdb) b kernel.c:137
Breakpoint 12 at 0x13252: file kernel.c, line 137.
(gdb) c
Breakpoint 12, kmain () at kernel.c:137
137 kprintf("all processes finished, %u frames free\n", pmm_free_frames_count());
(gdb) p pmm_free_frames_count()
$30 = 32443Four frames fewer than the 32447 before elf_exec: the
heap pages, as explained after the make test listing.
Everything the two programs owned has been freed.
14.9 Where this leaves us
The kernel now has the shape of a real one: hardware drivers at the bottom, a file system in the middle, processes on top, and a system call boundary between the processes and everything else. It is worth being precise about what is missing, because the gaps are where the next thirty years of operating systems research went.
The file system can be written, but barely. Files are limited to the
12 direct blocks, because ext2_write_file never allocates
an indirect block (i_block[12]), nor frees one. Nothing can
be deleted: unlink means removing the name by growing the
previous entry’s rec_len over it, decrementing
i_links_count, and when it reaches 0 setting
i_dtime, freeing every block the inode has, and clearing
its bit in the inode bitmap; everything needed is in this chapter, in
the other direction. There is no truncate as an operation
of its own, only the side effect of a rewrite, and no
append: a write replaces the whole file. A directory cannot
grow past the blocks it has, so a 1 KiB directory holds some 60 short
names and then dir_add_entry gives up; adding a block to a
directory is the same alloc_block plus a new last entry
that spans the whole block. There is no mkdir, which is
ext2_create with a directory inode, a first block holding
. and .., a link count of 2, and
bg_used_dirs_count incremented. And there is no owner:
every file the kernel creates belongs to uid 0.
The deeper limitation is what happens when the power fails between
two of the eleven writes. The order we chose guarantees that
e2fsck can always repair the disk without losing old data,
and that is the best a file system of this design can do; it is what
Unix file systems did until the 1990s, and what every machine’s boot
sequence looked like: a full fsck after every crash,
minutes for a disk of the time, hours for a disk of today, since every
inode and every directory block has to be read. ext3 (1999-2001) added a
journal to this exact on-disk format, as a compatible feature
flag and a hidden file (s_journal_inum in the superblock):
before touching the bitmaps, inodes and directories, the kernel writes a
description of the whole change to the journal, a circular log, and
flushes it; only then does it write the structures themselves. After a
crash, the kernel replays the journal’s complete entries and discards
the incomplete ones, in seconds, and no fsck is needed. The
same idea under the name write-ahead logging is how databases
have worked since the 1970s; copy-on-write file systems (ZFS, Btrfs)
avoid the problem differently, by never overwriting a live structure,
and switching a single root pointer at the end.
There is no cache. Every ext2_read_inode reads a block
from the disk, so listing /bin costs a dozen sector reads
for data that was read a moment ago. Real kernels keep a buffer
cache (or page cache) of disk blocks in memory, read
through it, write back through it lazily, and the cache is where most of
a kernel’s memory goes.
There is one file system. A real kernel has a virtual file
system (VFS) layer: the struct file_operations table
of function pointers from chapter 9’s introduction, through which
open, read and write reach ext4,
FAT, NFS, /proc or a pipe without the caller knowing which.
Mounting one file system on a directory of another, file descriptors,
the current directory, permissions: all of that lives in the VFS, above
any particular on-disk format. Our ext2_lookup(path) is the
whole VFS for now.
User programs cannot open files, because there is no
SYS_OPEN and no SYS_READ: the kernel reads
files, user programs only print. There is no SYS_EXEC
either, so a shell cannot be written. Both are a few dozen lines on top
of what exists; SYS_OPEN and SYS_READ are the
first exercises below, and chapter 15, Address spaces: fork and exec,
adds exec.
The disk is driven by polling, in PIO mode, on a controller interface
from 1984. A kernel for a current machine would speak AHCI or NVMe, use
DMA and interrupts, and would discover its controller by enumerating the
PCI bus rather than assuming port 0x1F0. Chapter 17,
Epilogue, says what changes for 64-bit, UEFI and multiprocessor
machines, and where to read about it.
14.10 Exercises
Exercise 14.1. file_block stops at the
singly indirect block, 268 KiB. Add the doubly indirect level
(i_block[13]): a block of block numbers of blocks of block
numbers. To test it you need a file larger than 268 KiB in
rootfs/; create one with dd from
/dev/urandom (so that mke2fs cannot make
holes), print its first and last bytes from kmain, and
compare with xxd on the host.
debugfs -R "stat /big" shows which blocks are the indirect
ones: (IND):, (DIND):.
Exercise 14.2. Add SYS_OPEN and
SYS_READ so that a user program can read
/etc/motd itself. The kernel needs a table of open files
per task (an inode and a current offset are enough) and a file
descriptor number as the handle; read(fd, buf, n) copies at
most n bytes at the current offset into the user’s buffer,
after checking the buffer with user_range_ok in
syscall.c, as write does. Write
user/cat.c with them. Why must the kernel not trust
n?
Exercise 14.3. Add SYS_EXEC, which
takes a path and replaces nothing (unlike Unix’s execve)
but creates a new task running that program, as elf_exec
does from kmain. The path is a pointer from ring 3: check
it with user_range_ok before ext2_lookup reads
a byte of it. Then write user/twice.c, a program that calls
exec("/bin/count") two times and exits, and look at the
interleaving of the two outputs: this is where kprintf not
being atomic becomes visible. What is the smallest change that keeps
lines whole? (A shell on top of exec is the milestone
project of chapter 15.)
Exercise 14.4. Relink hello with
. = 0x08048000 + SIZEOF_HEADERS; . = ALIGN(0x1000); before
.text in user.lds, so that the code starts on
the next page and the file holds a run of zeros. Check the size with
ls -l and the segments with readelf -l,
rebuild the image and run debugfs -R "stat /bin/hello" on
it: which of i_block[0..5] are zero? Then temporarily
remove the if (b == 0) branch from
ext2_read_file and explain what the kernel loads instead of
the program, and why it is the superblock’s neighborhood.
Exercise 14.5. Boot the same disk.img
with
qemu-system-i386 -machine pc -drive format=raw,file=build/disk.img,if=ide ...
and it works without -device piix3-ide. Add
-device isa-ide instead of piix3-ide on q35
and see what happens. Use QEMU’s monitor (info pci,
info qtree) under each configuration to find where the disk
is attached and which controller decodes ports
0x1F0-0x1F7. Read the OSDev page “PCI” and
write the twenty lines that enumerate the PCI bus and print the vendor
and device identifiers of every device: the IDE controller has class
0x01, subclass 0x01, and the AHCI one subclass
0x06.
Exercise 14.6. Corrupt the magic number with
printf '\x00\x00' | dd of=build/disk.img bs=1 seek=$((1048576 + 1024 + 56)) conv=notrunc
and boot. Which line does the kernel print and why does it panic rather
than continue? Then corrupt s_log_block_size to 2 instead
and explain, from ext2_mount, what the kernel reads as the
group descriptor table and what ext2_list_dir("/") prints.
e2fsck -n build/fs.img on the extracted file system tells
you how the real tools diagnose both.
Exercise 14.7. Count the disk accesses. Add a
counter of sectors read to ata_read_sectors and print it
from kmain before and after cat("/etc/motd"),
then before and after elf_exec("/bin/hello"). Explain every
sector of the first number from the structures of this chapter:
superblock, group descriptor table, inode of /, its
directory block, inode of etc, its block, inode of
motd, its data. Then add a one-block cache to
read_block (remember the last block number and its
contents) and measure again. How much does the inode table’s layout help
a cache? Do the same for the writes of log_boot and explain
why a write-back cache would have to be careful about the order of the
section “Allocating a block and an inode”.
Exercise 14.8. Add
ext2_append(path, data, len), which adds bytes at the end
of an existing file instead of replacing it. The last block of the file
is usually partly full: read it, fill it, write it back, then allocate
blocks for the rest; i_size grows, i_blocks
only when a block was added. Make log_boot append its line
instead of replacing it, so that /log.txt becomes a real
log, and boot the same image a few times. Then let it grow past 12 KiB
(append a longer line, or boot it 300 times with a shell loop around
timeout 10 qemu-system-i386 ...) and implement the singly
indirect block, which file_block already knows how to read:
allocate it, zero it, and store the block numbers in it.
debugfs -R "stat /log.txt" shows it as (IND):.
Check with e2fsck -fn after every step.
Exercise 14.9. Add ext2_unlink(path).
First make the mistake on purpose: remove only the directory entry, by
giving the previous entry’s rec_len the deleted entry’s
bytes (or setting its inode to 0 if it is the first in its
block), reboot, and run e2fsck -fn build/fs.img. Which pass
complains, with which message, and what does
debugfs -R "ls -l /lost+found" show after
e2fsck -fy? Then do it right: decrement
i_links_count, and when it reaches 0, set
i_dtime, free the blocks with free_block,
clear the inode’s bit in the inode bitmap and fix the counts. Verify
with debugfs -R "testb 503", testi <17>
and a clean e2fsck -fn. In which order must these writes
happen so that a crash halfway leaves at worst a leaked block, never a
shared one?
14.11 Check your understanding
ata_wait_datareturns as soon asDRQ,ERRorDFis set onceBSYis clear. Why can the bits other thanBSYnot be trusted whileBSYis set, and what would go wrong inata_read_sectorsif the loop checkedDRQfirst?- The chapter’s driver sends
FLUSH CACHEafter every write. What would be lost by omitting it, in what circumstances exactly, and why does Linux not do the same? - Reading the superblock takes two raw sectors at a fixed place, but the group descriptor table is read as a block. Why can the superblock not be read as a block, and what changes in both reads when the block size is 4 KiB?
i_block[1] == 0in the inode of a 3 KiB file. What does the kernel return for bytes 1024 to 2047, why is block 0 never a legitimate answer, and how did this convention bite the first version of the user programs?alloc_inodewrites the inode bitmap at once but only updatesbg_free_inodes_countin memory, to be written later. Explain which of the two a crash in between corrupts, howe2fsckrepairs it, and why the opposite choice (counts first) would be no worse. Then explain why “inode first, bitmap later” would be worse.dir_add_entryfound 956 spare bytes in theetcentry. If the root directory instead contained 60 short names and no slack at all, what would happen, and what two writes would a version that grows directories have to add?ext2_write_filefrees the blocks of the old content beyond the new size. What woulde2fsckreport if it did not, and why does the kernel not get the same complaint forlost+found, whose size is 12288 bytes?- A user program in chapter 13 could not open a file because there was
no
SYS_OPEN. Suppose you add one that returns the inode number as the file descriptor. What goes wrong when two tasks read the same file, and what structure does a real kernel keep between the descriptor and the inode?