12 Memory management

The kernel of chapter 11, Interrupts, can react to the world, but it has no idea what the world is made of. It runs at 0x10000 because the bootloader put it there, its stack grows down from 0x90000 because code/README.md says so, and every pointer it uses is a physical address that we chose by hand. It does not know how much memory the machine has, it has no way of handing a piece of that memory to anyone, and nothing stops a stray write from landing on the IDT. This chapter adds the three pieces that every kernel has and that chapter 13, Processes, cannot do without: a map of the physical memory, obtained from the BIOS; an allocator that hands out that memory in 4 KiB frames; and paging, the mechanism of the x86 that puts a translation layer between the addresses a program uses and the addresses the memory bus sees. On top of the frames we build a small kmalloc, and with paging on, the kernel meets its first page fault and reports it instead of rebooting. Before the code, the concepts, which the first edition introduced and which we keep here.

Running this chapter’s code

The code is in code/chapter12/os: the chapter 11 kernel plus the four modules and the bootloader step described below. From the root of the repository, in the chapter 0 container:

$ docker run --rm --user "$(id -u):$(id -g)" --security-opt seccomp=unconfined -v "$PWD":/work -w /work/code/chapter12/os os01 make test

make builds the kernel, the bootloader and build/disk.img. make qemu and make gdb, in two terminals, are the pair of chapter 11: QEMU stopped at its first instruction with the serial port on the terminal and a gdb stub on port 26000, and gdb connected to it with a breakpoint at kmain. Every debugger session of this chapter starts from there; b paging_init, c and finish stop just after paging is turned on. make test runs tools/serial-test.sh and waits for the string Page fault at 0xdeadbeef: the kernel of this chapter ends, on purpose, with a page fault, and the test checks that the fault is reported on the serial port instead of rebooting the machine.

12.1 Address space and virtual memory

An address space is the set of all addressable memory locations. In a PC there are two of them: the memory address space, 4 GiB wide on a 32-bit CPU, reached by every mov with a memory operand, and the I/O address space, 64 KiB wide, reached only by in and out, which chapter 10, Talking to devices: the serial port and the VGA text console, used for the serial port. This chapter is about the first one.

Physical memory is a contiguous set of memory locations with a simple mapping between a physical address and the corresponding location in a memory chip, decoded by the memory controller. Virtual memory, on the other hand, does not have a direct mapping between an address and a physical location, even though it appears contiguous from the point of view of a program. Instead, a virtual address is translated, by hardware configured by the OS, into an actual physical address. For that reason, two addresses that are next to each other in virtual memory may be scattered anywhere in physical memory, and each process can have its own address space to do what it wants with, as long as the physical memory is not exhausted.

Why is virtual memory needed? Because it reduces the complexity of programming, by giving each program the illusion that it has its own separate “physical” memory to work with. Without virtual memory, programs must know about each other and agree on their memory regions so as not to destroy each other. Picture two programs, both linked, as gcc links every program, to start at the same address, and both wanting to keep a variable at 0x1000:

Without translation the two programs cannot run at the same time, and the only way out is to relink one of them for a different address, which is what MS-DOS programs and the relocation records of chapter 8, Linking and loading on bare metal, used to do. With translation, each program keeps its 0x1000, the OS points each one to a different frame, and neither can even name the other’s memory.

Virtual memory also enables a more secure OS: application programs cannot manipulate main memory directly, so a malicious or buggy program cannot wreck the kernel, another program or a device’s memory-mapped registers, because the only physical memory it can reach is what the OS mapped for it.

Another benefit is that virtual memory can extend beyond physical memory, by storing some of its contents on disk. By swapping out unused memory, for instance the inactive pages of a sleeping process, the system gains free memory to continue running, so no data is destroyed; otherwise the OS would be forced to kill a process to free memory, and you could lose unsaved work. Swapping can slow the whole system down dramatically, because a disk is thousands of times slower than RAM; in the old days, when memory was scarce, it was nevertheless indispensable. Our kernel will not swap, but the page-fault mechanism that makes swapping possible is exactly the one we install at the end of this chapter.

12.2 What this chapter adds

The kernel grows by four modules and the bootloader by one step:

$ diff -rq -x build ../../chapter11/os .
Files ../../chapter11/os/.gdbinit and ./.gdbinit differ
Files ../../chapter11/os/Makefile and ./Makefile differ
Files ../../chapter11/os/bootloader/bootloader.asm and ./bootloader/bootloader.asm differ
Only in ./os: e820.c
Only in ./os: e820.h
Only in ./os: heap.c
Only in ./os: heap.h
Files ../../chapter11/os/os/kernel.c and ./os/kernel.c differ
Files ../../chapter11/os/os/os.lds and ./os/os.lds differ
Only in ./os: paging.c
Only in ./os: paging.h
Only in ./os: pmm.c
Only in ./os: pmm.h

Here is what the finished kernel prints on the serial port, and the rest of the chapter explains it line by line:

$ make test
...output omitted...
serial-test: ok, found "Page fault at 0xdeadbeef"
--- serial output ---
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
BIOS memory map (8 entries):
  base                 length               type
  0x0000000000000000   0x000000000009fc00   Usable
  0x000000000009fc00   0x0000000000000400   Reserved
  0x00000000000f0000   0x0000000000010000   Reserved
  0x0000000000100000   0x0000000007edf000   Usable
  0x0000000007fdf000   0x0000000000021000   Reserved
  0x00000000b0000000   0x0000000010000000   Reserved
  0x00000000fed1c000   0x0000000000004000   Reserved
  0x00000000fffc0000   0x0000000000040000   Reserved
usable memory: 130555 KiB
frame allocator: 32735 frames below 0x07fdf000, 32479 free (129916 KiB)
paging enabled, page directory at 0x00014000, 32448 frames free
virtual 0x30000000 -> physical 0x0011f000: wrote 0xcafebabe, read back 0xcafebabe, the frame holds 0xcafebabe
kmalloc: a=0xc0000010 b=0xc0000088 c=0xc0000868 (heap 4096 bytes)
after kfree(b), kmalloc(1000) = 0xc0000088 (reuses b's block)
32445 frames free
reading unmapped address 0xdeadbeef...

Page fault at 0xdeadbeef: page not present, read, kernel mode, eip=0x00011069 (error code 0x0)

KERNEL PANIC: unhandled page fault
qemu-system-i386: terminating on signal 15 from pid 238 (/bin/sh)

The driver of it all is kmain, which now reads as a table of contents:

kernel.c

/* kernel.c -- chapter 12: the kernel manages memory. */
#include <stdint.h>
#include "gdt.h"
#include "idt.h"
#include "isr.h"
#include "pic.h"
#include "pit.h"
#include "keyboard.h"
#include "console.h"
#include "printf.h"
#include "cpuid.h"
#include "e820.h"
#include "pmm.h"
#include "paging.h"
#include "heap.h"

#define TIMER_HZ 100

void kmain(void)
{
    uint32_t frame, cr3;
    volatile uint32_t *window;
    void *a, *b, *c, *d;

    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();

    /* 1. What memory is there?  The bootloader asked the BIOS for us. */
    e820_print();
    kprintf("usable memory: %u KiB\n", e820_usable_kib());

    /* 2. Physical frames. */
    pmm_init();
    kprintf("frame allocator: %u frames below %p, %u free (%u KiB)\n",
            pmm_memory_top() / PAGE_SIZE, (void *)pmm_memory_top(),
            pmm_free_frames_count(), pmm_free_frames_count() * 4);

    /* 3. Paging.  Nothing visible changes: the kernel is identity-mapped. */
    paging_init();
    asm volatile("mov %%cr3, %0" : "=r"(cr3));
    kprintf("paging enabled, page directory at %p, %u frames free\n",
            (void *)cr3, pmm_free_frames_count());

The order is, again, the order of dependencies: the memory map is read by the frame allocator, the frame allocator is used by paging to build its tables, and the heap uses both. We take them in that order.

12.3 How much memory is there?

The kernel cannot find out by itself. There is no instruction that returns the amount of RAM: the memory controller in the chipset knows, and the only software that talked to the chipset is the firmware. Worse, physical memory is not one block. The first megabyte of a PC is riddled with holes inherited from 1981: the VGA frame buffer at 0xA0000, option ROMs, the BIOS ROM at 0xF0000. Above it, the chipset carves out ranges for the ACPI tables, for memory-mapped PCI devices, for its own registers, and the firmware keeps a few pages for itself at the top of RAM. Writing into one of those ranges because “it is below the RAM size” overwrites a table the kernel needs later, or talks to a device. The one piece of software that knows the whole picture is the BIOS, and it is willing to tell.

12.3.1 The BIOS E820 service

The service is INT 15h with EAX = E820h, and its specification is not in the Intel manual but in the ACPI specification, chapter 15 “System Address Map Interfaces”, section 15.1 “INT 15H, E820H, Query System Address Map”, with the layout of one entry in the table “Address Range Descriptor Structure” and the meaning of its type field in “Address Range Types”. The OSDev wiki page “Detecting Memory (x86)” is a practical summary with the quirks of real BIOSes. The service returns the map one entry at a time: each call fills a buffer that the caller provides, and returns a continuation value that the caller passes back to get the next entry. An entry is 20 bytes, or 24 since ACPI 3.0:

Base and length are 64 bits, because a PC may have more than 4 GiB of RAM even when its CPU is running 32-bit code, and because the firmware maps its flash just under 4 GiB. The register protocol, from the specification: on input EAX = E820h, EDX = the ASCII signature 'SMAP' (0x534D4150), ECX = the size of the buffer, ES:DI = its address, EBX = the continuation value, 0 on the first call. On output EAX = 'SMAP' again (if it does not, the BIOS does not support the service), ECX = the number of bytes written, EBX = the next continuation value, and CF set means an error, which some BIOSes use to mean “no more entries”. EBX = 0 after a call means that this was the last entry.

The catch is in the first word of the service’s name: INT 15h is a BIOS call, and the BIOS is 16-bit real-mode code. Once the bootloader has switched to protected mode, there is no BIOS any more: the interrupt vector table at address 0 is replaced by our IDT, and the BIOS code would not run in a 32-bit segment anyway. So the map has to be collected by the bootloader, before the switch, and left somewhere for the kernel to find. That somewhere is the boot information block at physical address 0x500, listed in code/README.md: the first 1 KiB of memory is the real-mode IVT and the BIOS data area, the block starts right after it, and it ends well below the bootloader’s stack at 0x7C00.

12.3.2 The bootloader loop

The step is inserted between reading the kernel and enabling A20, as step 3, and uses these constants:

bootloader/bootloader.asm

; Boot information block (code/README.md, "Memory map"), read by the kernel
; in e820.c.  The layout must match struct bootinfo there.
BOOTINFO        equ 0x500
E820_COUNT      equ BOOTINFO + 0    ; uint32_t: number of entries stored
E820_ENTRIES    equ BOOTINFO + 8    ; 24-byte entries, one after the other
E820_MAX        equ 32              ; the block ends well before our stack
E820_ENTRY_SIZE equ 24
SMAP            equ 0x534d4150      ; 'SMAP' signature, see below

The count is a 32-bit word at 0x500, and the entries start at 0x508, not 0x504, so that the 64-bit fields inside them are 8-byte aligned; 32 entries of 24 bytes end at 0x808. Then the loop:

;------------------------------------------------------------------------------
; 3. Memory map.
;    INT 15h, EAX=E820h returns the physical memory map one entry at a
;    time: each call fills the 24-byte buffer at ES:DI with (base, length,
;    type, extended attributes), EAX must hold E820h, EDX the signature
;    'SMAP', ECX the buffer size, and EBX the "continuation value" that the
;    previous call returned (0 for the first call).  The BIOS returns the
;    signature in EAX, the number of bytes written in ECX, the next
;    continuation value in EBX; EBX = 0 or CF = 1 means the last entry
;    (ACPI specification, section 15.1 "INT 15H, E820H - Query System
;    Address Map"; OSDev wiki: "Detecting Memory (x86)").  This has to
;    happen in real mode: there is no BIOS in protected mode.
;    The entries are stored one after the other from E820_ENTRIES and the
;    count at E820_COUNT; ES is 0 so ES:DI is a physical address.
;------------------------------------------------------------------------------
    mov     dword [E820_COUNT], 0
    xor     ebx, ebx
    mov     di, E820_ENTRIES
.e820_next:
    mov     eax, 0xe820
    mov     ecx, E820_ENTRY_SIZE
    mov     edx, SMAP
    ; ACPI 3.0 extended attributes: bit 0 clear means "ignore this entry".
    ; Older BIOSes only write 20 bytes, so preset bit 0 ourselves.
    mov     dword [di + 20], 1
    int     0x15
    jc      .e820_done          ; CF = 1: end of the list (or unsupported)
    cmp     eax, SMAP
    jne     .e820_done          ; no signature: the call is not supported
    inc     dword [E820_COUNT]
    add     di, E820_ENTRY_SIZE
    test    ebx, ebx
    jz      .e820_done          ; EBX = 0: that was the last entry
    cmp     di, E820_ENTRIES + E820_MAX * E820_ENTRY_SIZE
    jb      .e820_next          ; stop before overflowing the block
.e820_done:

Line by line. The count is zeroed and EBX, the continuation value, with it; DI points at the first entry slot, and since step 1 set ES to 0, ES:DI is the physical address 0x508. Each iteration reloads EAX, ECX and EDX, because the BIOS overwrites all three: EAX with the signature, ECX with the byte count, and EDX with, on some BIOSes, anything at all. Then the line that the comment flags: before the call, the loop writes a 1 into the extended-attributes field of the entry it is about to receive. A BIOS that knows ACPI 3.0 overwrites it with the real attributes; an older one writes only 20 bytes and leaves our 1 in place, and since bit 0 set means “this entry is valid”, the kernel can treat every entry the same way whatever the BIOS did. Without the preset, a 20-byte BIOS would leave whatever was at 0x51C before, and a zero there would make the kernel ignore a perfectly good entry.

After int 0x15, three ways out. CF set is the end of the list on BIOSes that signal it that way, and also what a BIOS without the service returns, so the count stays 0 and the kernel will see an empty map rather than garbage. A wrong signature in EAX means the same. Otherwise the entry is valid: the count goes up, DI moves to the next slot, and EBX = 0 says the BIOS has no more. The last comparison stops the loop at 32 entries even if the BIOS has more; real machines return between 10 and 30, so the limit is comfortable, and the alternative is overwriting the bootloader’s stack.

The loop assembles to 72 bytes, from offset 0x4C to 0x94 in the sector, as nasm -l shows (the listing columns are line number, offset, bytes, source):

$ nasm -f elf -F dwarf -g -DKERNEL_SECTORS=129 -l bootloader.lst bootloader.asm -o /dev/null
$ sed -n '106,126p' bootloader.lst
   106 0000004C 66C706000500000000          mov     dword [E820_COUNT], 0
   107 00000055 6631DB                      xor     ebx, ebx
   108 00000058 BF0805                      mov     di, E820_ENTRIES
   109                                  .e820_next:
   110 0000005B 66B820E80000                mov     eax, 0xe820
   111 00000061 66B918000000                mov     ecx, E820_ENTRY_SIZE
   112 00000067 66BA50414D53                mov     edx, SMAP
   113                                      ; ACPI 3.0 extended attributes: bit 0 clear means "ignore this entry".
   114                                      ; Older BIOSes only write 20 bytes, so preset bit 0 ourselves.
   115 0000006D 66C7451401000000            mov     dword [di + 20], 1
   116 00000075 CD15                        int     0x15
   117 00000077 721B                        jc      .e820_done          ; CF = 1: end of the list (or unsupported)
   118 00000079 663D50414D53                cmp     eax, SMAP
   119 0000007F 7513                        jne     .e820_done          ; no signature: the call is not supported
   120 00000081 66FF060005                  inc     dword [E820_COUNT]
   121 00000086 83C718                      add     di, E820_ENTRY_SIZE
   122 00000089 6685DB                      test    ebx, ebx
   123 0000008C 7406                        jz      .e820_done          ; EBX = 0: that was the last entry
   124 0000008E 81FF0808                    cmp     di, E820_ENTRIES + E820_MAX * E820_ENTRY_SIZE
   125 00000092 72C7                        jb      .e820_next          ; stop before overflowing the block
   126                                  .e820_done:

Every instruction that touches a 32-bit register starts with the byte 66, the operand-size prefix of chapter 4, x86 Assembly and C: in 16-bit code, mov eax, 0xe820 is mov ax, ... with a prefix that widens it. SMAP appears as 50 41 4D 53 in the bytes, 'PAMS' read forwards, because the little-endian value 0x534D4150 is 'SMAP' when read as the register’s bytes from most to least significant; that is why the ACPI specification spells the signature as the letters and the code as a number. The padding line of the sector tells how much room is left:

$ sed -n '225p' bootloader.lst
   225 00000106 00<rep F8h>             times 510 - ($ - $$) db 0

The code and data end at offset 0x106, 262 bytes, and 248 zero bytes fill the sector up to the signature. Half the sector is still free: the bootloader is finished as far as this book is concerned, and the room is yours for the exercises.

12.3.3 The kernel’s view of the map

On the C side, the block is a structure at a fixed address:

e820.h

#ifndef E820_H
#define E820_H

#include <stdint.h>

/* The boot information block the bootloader fills at physical 0x500
   (code/README.md, "Memory map"; bootloader.asm, step 3).  The entry
   layout is the one INT 15h E820h returns (ACPI specification, section
   15.1, the table "Address Range Descriptor Structure"). */
#define BOOTINFO_ADDR 0x500
#define E820_MAX      32

struct e820_entry {
    uint64_t base;      /* first byte of the range */
    uint64_t length;    /* size in bytes */
    uint32_t type;      /* E820_USABLE ... */
    uint32_t attrs;     /* ACPI 3.0 extended attributes (bit 0: valid) */
} __attribute__((packed));

struct bootinfo {
    uint32_t e820_count;
    uint32_t reserved;              /* keeps the entries 8-byte aligned */
    struct e820_entry e820[E820_MAX];
} __attribute__((packed));

/* Address range types, ACPI specification, section 15.1, the table
   "Address Range Types". */
#define E820_USABLE     1   /* RAM the OS may use */
#define E820_RESERVED   2   /* in use by the firmware or hardware, hands off */
#define E820_ACPI       3   /* ACPI tables; reusable once they are parsed */
#define E820_NVS        4   /* ACPI non-volatile storage; must be preserved */
#define E820_BAD        5   /* RAM that failed the firmware's tests */

const struct bootinfo *e820_bootinfo(void);
const char *e820_type_name(uint32_t type);
void e820_print(void);

/* Sum of the lengths of all usable entries, in KiB (fits 32 bits up to
   4 TiB; our kprintf has no 64-bit conversion). */
uint32_t e820_usable_kib(void);

/* Highest address + 1 covered by a usable entry, clipped to 4 GiB. */
uint32_t e820_usable_top(void);

#endif

struct e820_entry is the 24-byte descriptor of the table above, and struct bootinfo is the block, with the reserved word that accounts for the gap between 0x504 and 0x508. Both are packed, as every structure that mirrors a layout defined outside the compiler. The two numbers that the rest of the kernel needs are computed by walking the entries of type 1:

e820.c

uint32_t e820_usable_kib(void)
{
    const struct bootinfo *bi = e820_bootinfo();
    uint64_t total = 0;
    uint32_t i;

    for (i = 0; i < bi->e820_count && i < E820_MAX; i++)
        if (bi->e820[i].type == E820_USABLE)
            total += bi->e820[i].length;
    return (uint32_t)(total / 1024);
}

uint32_t e820_usable_top(void)
{
    const struct bootinfo *bi = e820_bootinfo();
    uint64_t top = 0;
    uint32_t i;

    for (i = 0; i < bi->e820_count && i < E820_MAX; i++) {
        const struct e820_entry *e = &bi->e820[i];
        if (e->type == E820_USABLE && e->base + e->length > top)
            top = e->base + e->length;
    }
    if (top > 0xFFFFFFFFULL)
        top = 0xFFFFFFFFULL;
    return (uint32_t)top;
}

e820_print, not shown, prints the table we saw; the 64-bit fields go through a small print_u64 because kprintf only knows 32-bit conversions, which is also why the totals are returned in KiB. The arithmetic is done in uint64_t on purpose: on a machine with 8 GiB, the sum of the lengths does not fit in 32 bits, and e820_usable_top clips the result to what a 32-bit kernel can address at all.

Before the kernel has printed anything, the block can be read with gdb at the kmain breakpoint of .gdbinit, as raw memory and as the structure:

(gdb) x/2xw 0x500
0x500:  0x00000008  0x00000000
(gdb) x/8xg 0x508
0x508:  0x0000000000000000  0x000000000009fc00
0x518:  0x0000000100000001  0x000000000009fc00
0x528:  0x0000000000000400  0x0000000100000002
0x538:  0x00000000000f0000  0x0000000000010000
(gdb) p/x ((struct bootinfo *)0x500)->e820[3]
$2 = {base = 0x100000, length = 0x7edf000, type = 0x1, attrs = 0x1}
(gdb) p sizeof(struct e820_entry)
$3 = 24

Eight entries, and the first three in giant words: base 0, length 0x9fc00, then the 64-bit word 0x0000000100000001, which is type = 1 in its low half and attrs = 1 in its high half, that is, usable RAM and the valid bit. The next entry starts at 0x520 with base 0x9fc00, length 0x400, type 2. The entries are 24 bytes, so they do not line up with the 16-byte rows of x/8xg; p on the structure is easier to read.

12.3.4 QEMU’s map, entry by entry

The eight lines that the kernel printed are the physical address space of QEMU’s q35 machine with the default 128 MiB of RAM. Each one has a reason:

1. 0x0 to 0x9fc00, usable: the first 639 KiB, the conventional memory of the PC. Our bootloader, the boot information block, the kernel at 0x10000 and its stack at 0x90000 all live here.
2. 0x9fc00 to 0xa0000, reserved, 1 KiB: the Extended BIOS Data Area, where the BIOS keeps its own variables; the 639 KiB figure instead of 640 is this entry.
3. 0xf0000 to 0x100000, reserved: the BIOS ROM itself, the 64 KiB of SeaBIOS code that INT 13h and INT 15h jumped into. Note what is not listed: from 0xa0000 to 0xf0000 there is no entry at all. The VGA memory at 0xb8000 and the option ROMs are a hole in the map, neither usable nor reserved; a kernel must treat absence as “not RAM”.
4. 0x100000 to 0x7fdf000, usable: extended memory, everything from 1 MiB up, 129916 KiB.
5. 0x7fdf000 to 0x8000000, reserved, 132 KiB: the top of the 128 MiB. The firmware keeps the last pages of RAM for the ACPI tables, the SMBIOS tables and its own data, and marks them reserved so that we do not overwrite them before reading them. This is why the usable memory tops out at 0x7fdf000 and not at 0x8000000, and why the numbers below are 32735 frames and not 32768.
6. 0xb0000000 to 0xc0000000, reserved, 256 MiB: the PCI Express memory-mapped configuration space, MMCONFIG, where every PCIe device’s configuration registers appear in memory, 4 KiB per function; q35 places it there, and the ACPI MCFG table tells the OS. There is no RAM behind this address; a write goes to a device.
7. 0xfed1c000 to 0xfed20000, reserved, 16 KiB: the chipset’s own register block, the Root Complex Base Address of the ICH9 that q35 emulates.
8. 0xfffc0000 to 0x100000000, reserved, 256 KiB: the firmware flash, mapped just below 4 GiB, which is where the CPU fetched its very first instruction after reset (0xfffffff0, the 0x0000fff0 in ?? () that gdb reports when QEMU starts).

The usable total, 639 + 129916 = 130555 KiB, is the first number the kernel prints. A real machine prints a longer list: more reserved pockets below 1 MiB, an ACPI reclaimable range and an ACPI NVS range near the top of RAM, a hole below 4 GiB for the PCI devices, and, with more than about 3 GiB of RAM, a usable range above 0x100000000 that our 32-bit kernel cannot reach without the extensions that the epilogue describes.

12.4 Physical frames

Paging, which comes next, works in units of 4 KiB called pages on the virtual side and page frames on the physical side, and every memory structure the kernel builds from now on (page tables, task stacks, heap pages) is a whole number of frames. So the first allocator is a frame allocator: give me a free 4 KiB frame, take this frame back. There are 32735 frames in our 128 MiB, and the simplest data structure that remembers which ones are free is a bitmap, one bit per frame: 32735 bits are 4 KiB, a single page.

pmm.h

#ifndef PMM_H
#define PMM_H

#include <stdint.h>

/* Physical memory manager: hands out 4 KiB frames of RAM.
 *
 * Memory is divided into page frames of PAGE_SIZE bytes, the unit that
 * paging works with (Intel SDM Vol. 3A, section 5.3 "32-bit Paging").  A
 * bitmap holds one bit per frame: 1 = in use, 0 = free.  The frames are
 * numbered from physical address 0, so frame n starts at n * PAGE_SIZE. */
#define PAGE_SIZE   4096
#define PAGE_SHIFT  12

/* The allocator only manages the first PMM_MAX_MEMORY bytes, however
   much RAM the machine has; keeping the bitmap small and static. */
#define PMM_MAX_MEMORY (128u * 1024 * 1024)

void pmm_init(void);

/* Returns the physical address of a free frame and marks it used, or 0 if
   no frame is left.  Frame 0 is never free (it holds the real-mode
   interrupt vectors and the boot information block), so 0 is a safe
   "nothing" value.  The frame's contents are whatever was there before. */
uint32_t pmm_alloc_frame(void);
void     pmm_free_frame(uint32_t phys);
uint32_t pmm_free_frames_count(void);

/* First address after the last frame the allocator manages. */
uint32_t pmm_memory_top(void);

#endif

The interface is three functions and a convention: a frame is named by its physical address, and 0 means failure, which is safe because frame 0 holds the IVT and the boot information block and is never handed out. PMM_MAX_MEMORY caps what the allocator manages at 128 MiB, whatever the machine has, so that the bitmap can be a static array; a kernel for real machines would size it from the map instead, and that is exercise 12.3.

pmm.c

#define FRAMES_MAX (PMM_MAX_MEMORY / PAGE_SIZE)     /* 32768 frames */
#define BITS_PER_WORD 32

static uint32_t bitmap[FRAMES_MAX / BITS_PER_WORD];  /* 4 KiB */
static uint32_t frames_total;                       /* frames we manage */
static uint32_t frames_free;

extern char __kernel_start[], __kernel_end[];       /* os.lds */

The two extern char arrays are not arrays: they are linker symbols, and the kernel uses their addresses, never their contents. They come from two new lines in the linker script:

os.lds

  /* __kernel_start/__kernel_end tell the frame allocator (pmm.c) which
     frames the kernel image occupies, headers included. */
  __kernel_start = 0x10000;
  .text 0x10100 : ALIGN(0x100) { *(.text .text.*) } :code
  .rodata : { *(.rodata .rodata.*) } :code
  .data   : { *(.data .data.*) } :code
  /* __bss_start/__bss_end let entry.asm zero .bss: the bootloader copies
     the FILE, and .bss has no bytes in the file (NOBITS), so the memory it
     occupies holds whatever followed .data in the file (debug sections)
     until the kernel clears it.  A real ELF loader zeroes MemSiz - FileSiz
     for us; ours does not. */
  .bss    : { __bss_start = .; *(.bss .bss.*) *(COMMON) __bss_end = .; } :code
  __kernel_end = .;

__kernel_start is the address where the bootloader put the ELF file, headers included, and __kernel_end is the location counter after .bss, the first byte the kernel does not own. The extern char name[] declaration is the idiom for using a linker symbol from C, the same one entry.asm relied on for __bss_start in chapter 9, Protected mode and x86 descriptors: the symbol has an address and no size, and an array of unknown bound is the C type that says exactly that.

Initialization is a subtraction: everything is used, then the usable ranges of the map become free, then what is already occupied becomes used again:

void pmm_init(void)
{
    const struct bootinfo *bi = e820_bootinfo();
    uint32_t top = e820_usable_top();
    uint32_t i;

    if (top > PMM_MAX_MEMORY)
        top = PMM_MAX_MEMORY;
    frames_total = top / PAGE_SIZE;
    frames_free  = 0;
    memset(bitmap, 0xFF, sizeof(bitmap));           /* all used */

    /* 1. RAM reported by the BIOS becomes free... */
    for (i = 0; i < bi->e820_count && i < E820_MAX; i++)
        if (bi->e820[i].type == E820_USABLE)
            mark_range(bi->e820[i].base,
                       bi->e820[i].base + bi->e820[i].length, 0);

    /* 2. ...except what is already in use. */
    mark_range(0, 0x100000, 1);                     /* first megabyte */
    mark_range((uint32_t)__kernel_start, (uint32_t)__kernel_end, 1);
}

Starting from “all used” is what makes the holes of the map harmless: the range from 0xa0000 to 0xf0000 is never mentioned by the BIOS, so it is never freed, and the frame allocator will never hand out the VGA buffer. The whole first megabyte is then taken back wholesale, which covers the bootloader, the boot information block, the kernel stack and the EBDA in one line; the kernel image, which in our layout is inside the first megabyte anyway, gets its own line so that the code stays correct if it is ever linked higher. mark_range does the rounding and keeps frames_free honest:

static void mark_range(uint64_t start, uint64_t end, int used)
{
    uint32_t first, last, frame;

    if (end > (uint64_t)frames_total * PAGE_SIZE)
        end = (uint64_t)frames_total * PAGE_SIZE;
    if (start >= end)
        return;
    if (used) {
        first = (uint32_t)(start / PAGE_SIZE);
        last  = (uint32_t)((end + PAGE_SIZE - 1) / PAGE_SIZE);
    } else {
        first = (uint32_t)((start + PAGE_SIZE - 1) / PAGE_SIZE);
        last  = (uint32_t)(end / PAGE_SIZE);
    }
    for (frame = first; frame < last; frame++) {
        if (used && !frame_is_used(frame)) {
            frame_set_used(frame);
            frames_free--;
        } else if (!used && frame_is_used(frame)) {
            frame_set_free(frame);
            frames_free++;
        }
    }
}

The two roundings go in opposite directions, and the comment in the source says why: a frame that is only partly covered by a reserved range is reserved (round outwards), a frame that is only partly covered by a usable range is not usable (round inwards). The first usable entry ends at 0x9fc00, in the middle of frame 0x9f, so that frame is not freed; the EBDA is safe even before the first-megabyte line runs. Allocation is a linear scan for a zero bit, skipping full words:

uint32_t pmm_alloc_frame(void)
{
    uint32_t word, bit;

    for (word = 0; word < frames_total / BITS_PER_WORD; word++) {
        if (bitmap[word] == 0xFFFFFFFF)
            continue;                               /* all 32 used */
        for (bit = 0; bit < BITS_PER_WORD; bit++) {
            if (!(bitmap[word] & (1u << bit))) {
                uint32_t frame = word * BITS_PER_WORD + bit;
                frame_set_used(frame);
                frames_free--;
                return frame * PAGE_SIZE;
            }
        }
    }
    return 0;
}

void pmm_free_frame(uint32_t phys)
{
    uint32_t frame = phys / PAGE_SIZE;

    if (frame < frames_total && frame_is_used(frame)) {
        frame_set_free(frame);
        frames_free++;
    }
}

It is slow in the worst case, a thousand words to scan when memory is nearly full, and it always returns the lowest free frame, which is what makes the addresses in this chapter’s output predictable: the first frame ever allocated is 0x100000, the first one above the first megabyte. A faster allocator keeps a free list or a search hint; the bitmap is enough for us, and the interface would not change.

The numbers the kernel printed now make sense. frames_total is 0x7fdf000 / 4096 = 32735, the top of the usable map, and 32479 are free: 32735 minus the 256 frames of the first megabyte, in which the kernel image already lies. Under gdb, after finish from pmm_init:

(gdb) p frames_total
$5 = 32735
(gdb) p frames_free
$6 = 32479
(gdb) x/4xw bitmap
0x16020 <bitmap>:   0xffffffff  0xffffffff  0xffffffff  0xffffffff
(gdb) x/2xw &bitmap[7]
0x1603c <bitmap+28>:    0xffffffff  0x00000000
(gdb) p/x bitmap[1022]
$9 = 0x80000000
(gdb) p/x bitmap[1023]
$10 = 0xffffffff
(gdb) p &__kernel_end
$12 = (char (*)[]) 0x17030

Words 0 to 7 are all ones, 256 frames, the first megabyte; word 8 starts the free memory at frame 256, 0x100000. Word 1022 has only its top bit set: frame 32735 is the first one above frames_total, never freed, and word 1023 is entirely above the map. The kernel ends at 0x17030, so frame 0x17 is the last one it occupies, and all of it is inside the first megabyte as promised.

12.5 Paging on x86

The reading guide for this section is Intel SDM Volume 3A, chapter 5 “Paging”. It is long because it describes four paging modes; we use the oldest and simplest, and the sections you need are these:

• Section 5.1 “Paging Modes and Control Bits”: paging is enabled by CR0.PG, bit 31, and CR4.PAE and CR4.PSE select the mode. With both clear we get 32-bit paging, the mode of the 80386, which is the only one that fits a 32-bit page table entry and the one this chapter uses. Table 5-1 “Properties of Different Paging Modes” compares them: 32-bit paging translates 32-bit linear addresses into 32-bit physical addresses, 4 GiB of each, with 4 KiB or 4 MiB pages.

• Section 5.2 “Hierarchical Paging Structures: An Overview” explains the idea of a multi-level table, and why: a flat table with one entry per 4 KiB page of a 4 GiB address space would be 4 MiB per address space, mostly empty. Two levels let the empty parts cost nothing.

• Section 5.3 “32-Bit Paging” is the one to read with the code open. Figure 5-2 “Linear-Address Translation to a 4-KByte Page using 32-Bit Paging” is the picture to memorize: the 32-bit address is cut into 10, 10 and 12 bits. Table 5-3 gives the format of CR3, table 5-5 “Format of a 32-Bit Page-Directory Entry that References a Page Table” and table 5-6 “Format of a 32-Bit Page-Table Entry that Maps a 4-KByte Page” the two entry formats, and figure 5-4 draws them side by side. Table 5-4 is the 4 MiB page variant, which we do not use.

• Section 5.6 “Access Rights”: which accesses are allowed, as a function of the R/W and U/S bits at every level of the walk, and of the privilege level of the access. The rule to retain: the most restrictive entry wins.

• Section 5.7 “Page-Fault Exceptions”: when the CPU raises #PF and what it reports. Figure 5-12 is the error code.

• Section 5.8 “Accessed and Dirty Flags”: two bits that the CPU sets on its own and that an OS that swaps reads.

• Section 5.10 “Caching Translation Information”: the TLB, and section 5.10.4 “Invalidation of TLBs and Paging-Structure Caches”, the part about invlpg and about writing CR3, which answers the question “I changed a page table entry, why does the CPU not see it?”.

Section 2.5 “Control Registers” of the same volume describes CR0, CR2 and CR3 themselves.

12.5.1 The translation

With paging on, every address that an instruction produces, the linear address (which, with our flat segments, is the virtual address of the program), goes through this walk before it reaches the bus:

1. Bits 31:22 of the address, ten bits, index the page directory, a 4 KiB array of 1024 32-bit entries whose physical address is in CR3. The entry selected, a PDE, holds the physical address of a page table, or a present bit of 0.
2. Bits 21:12, ten bits, index that page table, another 4 KiB array of 1024 entries. The entry selected, a PTE, holds the physical address of a 4 KiB frame, or a present bit of 0.
3. Bits 11:0, twelve bits, are the offset inside that frame and go through unchanged.

The figure below is figure 5-2 of the manual with our names on it; the three dashed arrows are the three indexes, the two solid ones the two addresses read from the tables.

So one page directory covers the whole 4 GiB, one page table covers 4 MiB, and one entry covers 4 KiB. A directory whose entries are all absent costs one page and maps nothing; each 4 MiB region that is used costs one more page for its table. The entry formats of tables 5-5 and 5-6 are nearly identical, which is why one C header serves both:

paging.h

/* 32-bit two-level paging, Intel SDM Vol. 3A, section 5.3 "32-Bit Paging".
 *
 * A linear address is split in three:
 *     bits 31:22  index into the page directory (1024 entries)
 *     bits 21:12  index into the page table that entry points to (1024)
 *     bits 11:0   offset inside the 4 KiB page
 * Directory and tables are 4 KiB arrays of 32-bit entries; the entry holds
 * the physical address of the next level (bits 31:12, so it must be 4 KiB
 * aligned) and flags in the low 12 bits (SDM Vol. 3A, Table 5-5 and 5-6):
 */
#define PAGE_PRESENT   0x001    /* bit 0, P:   the entry is valid */
#define PAGE_WRITE     0x002    /* bit 1, R/W: writes allowed */
#define PAGE_USER      0x004    /* bit 2, U/S: ring 3 may access it */
#define PAGE_ACCESSED  0x020    /* bit 5, A:   set by the CPU on access */
#define PAGE_DIRTY     0x040    /* bit 6, D:   set by the CPU on write (PTE) */
#define PAGE_FRAME     0xFFFFF000   /* bits 31:12: physical address */

#define PAGE_DIR_INDEX(virt)   (((virt) >> 22) & 0x3FF)
#define PAGE_TABLE_INDEX(virt) (((virt) >> 12) & 0x3FF)
#define PAGE_ALIGN_DOWN(a)     ((a) & PAGE_FRAME)
#define PAGE_ALIGN_UP(a)       (((a) + 0xFFF) & PAGE_FRAME)

Because a page table and a frame are both 4 KiB aligned, their physical address has twelve zero low bits, and the entry formats reuse those twelve bits for flags. The ones we use:

Three bits, P, R/W and U/S, are the entire protection model of this book. P is what makes the page fault of the end of this chapter and the demand paging of real kernels possible. U/S is what will keep chapter 13’s user programs out of the kernel: the kernel’s pages have U/S = 0, so a ring-3 access to them faults. R/W is what makes a read-only .text possible (exercise 12.2). CR3 holds the physical address of the directory in its bits 31:12, with the same alignment requirement; its low bits are two more cache-policy flags that stay 0.

Section 5.6 states the combination rule: an access is allowed only if both the PDE and the PTE allow it. A user access needs U/S = 1 in both; a write needs R/W = 1 in both for a user access, and in both for a supervisor access as well when CR0.WP is set. For supervisor accesses with CR0.WP clear, which is our case, R/W is ignored: the kernel can write to a read-only page. This is a historical default and every modern kernel sets WP so that the kernel cannot scribble on its own code by mistake; we leave it clear in this chapter and exercise 12.2 turns it on.

12.5.2 The kernel’s page directory

paging.c

/* paging.c -- the kernel page directory and the page-fault handler.
 *
 * The kernel keeps "virtual == physical" for all the RAM it manages: the
 * page directory identity-maps every frame of the allocator.  That is the
 * simplest possible scheme and it means C pointers to frames work
 * unchanged after paging is on.  Everything above pmm_memory_top() is free
 * virtual space, used for the kernel heap (heap.c) and, later, for user
 * programs.
 */
#include "paging.h"
#include "pmm.h"
#include "isr.h"
#include "printf.h"
#include "panic.h"
#include "string.h"

/* Both must be 4 KiB aligned: CR3 and the directory entries only store
   bits 31:12 of their address (SDM Vol. 3A, Table 5-3 and 5-5). */
static uint32_t kernel_directory[1024] __attribute__((aligned(PAGE_SIZE)));
static uint32_t kernel_table0[1024]    __attribute__((aligned(PAGE_SIZE)));

The comment at the top states the design decision of the chapter, so let us state it again in one sentence: every frame that the allocator manages is mapped at the virtual address equal to its physical address. This is called an identity map, and its consequence is the invariant that the rest of the kernel relies on: a physical address returned by pmm_alloc_frame is a valid pointer, before paging is on and after. When get_table below allocates a frame for a page table and writes to it through (void *)frame, that works because of the identity map; when chapter 13 allocates a frame for a user stack and copies a program into it, same thing. The price is that the kernel’s virtual space from 0 to 128 MiB is spoken for, which is why the heap starts at 0xC0000000 and user programs at 0x08048000: 0x00400000 would have been RAM, and mapping the heap there would hide 4 MiB of frames behind it.

The two static arrays are the directory and the first page table. They are in .bss with aligned(PAGE_SIZE), because CR3 and a PDE only store bits 31:12 of the address: a directory at 0x14010 would be read as a directory at 0x14000. The alignment is visible in the kernel’s layout, and we come back to it in the build section.

static uint32_t *get_table(uint32_t *dir, uint32_t virt, int create,
                           uint32_t flags)
{
    uint32_t *pde = &dir[PAGE_DIR_INDEX(virt)];

    if (!(*pde & PAGE_PRESENT)) {
        uint32_t frame;

        if (!create)
            return 0;
        frame = pmm_alloc_frame();
        if (frame == 0)
            panic("paging: out of frames for a page table");
        memset((void *)frame, 0, PAGE_SIZE);        /* every entry not present */
        /* The directory entry is as permissive as any page below it may
           need to be; the page table entries do the real restricting
           (SDM Vol. 3A, section 5.6 "Access Rights": both levels must
           allow an access). */
        *pde = frame | PAGE_PRESENT | PAGE_WRITE | (flags & PAGE_USER);
    } else if ((flags & PAGE_USER) && !(*pde & PAGE_USER)) {
        *pde |= PAGE_USER;
    }
    return (uint32_t *)(*pde & PAGE_FRAME);
}

get_table is the first level of the walk, done in software: take the directory entry for virt, and if it is not present and the caller wants one, allocate a frame, clear it (a page table full of garbage would be a page table full of random mappings), and install it with P and R/W set. The directory entry is made writable and, when asked, user-accessible, because of the combination rule: the PDE must allow everything that any PTE under it will allow, and the PTE does the real restricting. The last line converts the entry back into a pointer by masking off the flags, and it is, again, the identity map that makes that pointer usable.

static void invlpg(uint32_t virt)
{
    asm volatile("invlpg (%0)" : : "r"(virt) : "memory");
}

static void map_in(uint32_t *dir, uint32_t virt, uint32_t phys, uint32_t flags)
{
    uint32_t *table = get_table(dir, virt, 1, flags);

    table[PAGE_TABLE_INDEX(virt)] = (phys & PAGE_FRAME) | PAGE_PRESENT
                                  | (flags & (PAGE_WRITE | PAGE_USER));
    invlpg(virt);
}

void paging_map(uint32_t virt, uint32_t phys, uint32_t flags)
{
    map_in(kernel_directory, virt, phys, flags);
}

void paging_unmap(uint32_t virt)
{
    uint32_t *table = get_table(kernel_directory, virt, 0, 0);

    if (table != 0) {
        table[PAGE_TABLE_INDEX(virt)] = 0;
        invlpg(virt);
    }
    /* The page table itself stays, even if empty: cheaper than counting
       its users, and it will probably be needed again. */
}

map_in is the second level: one store into the page table, frame address plus flags. paging_map is the public version for the kernel directory; map_in takes the directory as a parameter because chapter 13 will have one directory per process. paging_unmap zeroes the entry, and both call invlpg.

Why invlpg? Because the CPU does not walk the tables on every access. That would triple the cost of every memory reference, so it caches the result of recent walks in the Translation Lookaside Buffer, section 5.10.2, a small associative memory of (virtual page, physical frame, flags) entries. The tables in memory are the source of truth, but the CPU only consults them on a TLB miss. When the kernel changes an entry, a stale translation may stay in the TLB, and the next access to that page goes to the old frame, or succeeds on a page that was just unmapped. Section 5.10.4.1 lists the instructions that invalidate: invlpg m drops the TLB entry for the page containing the address m, and a mov cr3 drops them all (except the global ones, a feature we do not use). invlpg after each change is the precise and cheap option; reloading CR3 is the sledgehammer that chapter 13 uses when it switches address spaces. The "memory" clobber on the asm statement tells gcc that memory may have changed, so that it does not keep a value loaded through the old mapping in a register across the call. The instruction itself:

$ objdump -d -M intel build/os/os | grep 'invlpg BYTE'
   11214:   0f 01 38                invlpg BYTE PTR [eax]

12.5.3 Turning paging on

void paging_init(void)
{
    uint32_t addr, top = pmm_memory_top();
    uint32_t cr0;

    /* 1. The first 4 MiB (kernel, stack, VGA, boot information block) use
       a static page table so that nothing depends on the allocator. */
    memset(kernel_directory, 0, sizeof(kernel_directory));
    for (addr = 0; addr < 0x400000; addr += PAGE_SIZE)
        kernel_table0[PAGE_TABLE_INDEX(addr)] = addr | PAGE_PRESENT | PAGE_WRITE;
    kernel_directory[0] = (uint32_t)kernel_table0 | PAGE_PRESENT | PAGE_WRITE;

    /* 2. The rest of the managed RAM gets page tables from the frame
       allocator.  Paging is still off, so the fresh tables can be written
       at their physical address; once it is on, they still can because
       they are identity-mapped like everything else. */
    for (addr = 0x400000; addr < top; addr += PAGE_SIZE)
        paging_map(addr, addr, PAGE_WRITE);

    isr_register_handler(14, page_fault_handler);

    /* 3. CR3 holds the physical address of the page directory (SDM Vol.
       3A, section 2.5 "Control Registers" and Table 5-3); CR0.PG (bit 31)
       turns paging on.  The next instruction fetch is already translated,
       which is fine because the kernel is identity-mapped. */
    asm volatile("mov %0, %%cr3" : : "r"(kernel_directory) : "memory");
    asm volatile("mov %%cr0, %0" : "=r"(cr0));
    cr0 |= 0x80000000;
    asm volatile("mov %0, %%cr0" : : "r"(cr0) : "memory");
}

Step 1 fills the static table with the identity map of the first 4 MiB, 1024 entries of addr | 3, and hooks it into entry 0 of the directory. Everything the kernel is made of lives in those 4 MiB, so this is the part that must be right before paging is turned on, and it uses no allocator so that it cannot fail. Step 2 maps the remaining 124 MiB with paging_map, one page at a time, which creates 31 page tables on the way, from the frame allocator; the comment points out the subtlety: paging_map writes into those tables through their physical address, which is correct now because paging is off, and stays correct afterwards because the tables are identity-mapped too. Step 3 is the switch, and it is two instructions:

$ objdump -d -M intel build/os/os | sed -n '/<paging_init>:/,/ret/p' | tail -10
   1142d:   b8 00 40 01 00          mov    eax,0x14000
   11432:   0f 22 d8                mov    cr3,eax
   11435:   0f 20 c0                mov    eax,cr0
   11438:   89 45 ec                mov    DWORD PTR [ebp-0x14],eax
   1143b:   81 4d ec 00 00 00 80    or     DWORD PTR [ebp-0x14],0x80000000
   11442:   8b 45 ec                mov    eax,DWORD PTR [ebp-0x14]
   11445:   0f 22 c0                mov    cr0,eax
   11448:   90                      nop
   11449:   c9                      leave
   1144a:   c3                      ret

mov cr3, eax loads the directory’s address, 0x14000, and mov cr0, eax with bit 31 set turns paging on. The instruction after it, the nop at 0x11448, is already fetched through the page tables: the CPU translates 0x11448 through PDE 0, kernel_table0[0x11], and finds frame 0x11000, the same address. Had that entry been wrong, the fetch would have faulted, the fault handler’s address in the IDT would have been translated through the same broken tables, and the result would have been the triple fault of chapter 11. This is the moment every kernel author remembers: the first instruction after CR0.PG is set either works or reboots the machine. The reason it works for us is that the identity map makes the switch invisible: nothing in the kernel changes its address, the stack is where it was, ESP still points at it, and kmain continues at the next line as if nothing had happened. A kernel that lives at a different virtual address than its physical one (the usual choice, with the kernel at 0xC0000000 and above, is called a higher-half kernel) has to map itself twice around this instruction, at its old and its new address, and jump from one to the other; we avoid all of that by design, and pay for it with the 128 MiB of virtual space the identity map occupies.

What else changes for the kernel once paging is on? Nothing, and that is the point. Every pointer still works, every kprintf still writes to 0xB8000, because kernel_table0[0xB8] maps it to itself. The difference is that from now on there are addresses that do not work, and the kernel can make new ones work by calling paging_map.

12.5.4 Looking at the tables

Stop under gdb after paging_init returns (b paging_init, c, finish) and ask the CPU:

(gdb) p/x $cr3
$14 = 0x14000
(gdb) p &kernel_directory
$15 = (uint32_t (*)[1024]) 0x14000 <kernel_directory>
(gdb) p &kernel_table0
$16 = (uint32_t (*)[1024]) 0x15000 <kernel_table0>
(gdb) monitor info registers
...output omitted...
GDT=     00013000 00000017
IDT=     00013040 000007ff
CR0=80000011 CR2=00000000 CR3=00014000 CR4=00000000
...output omitted...

Before paging_init, the same command showed CR0=00000011: PE (bit 0) and ET (bit 4, a leftover that reads as 1). Now bit 31 is set, CR3 is the directory, CR4 is 0 (no PAE, no PSE: 32-bit paging). The directory itself:

(gdb) x/4xw kernel_directory
0x14000 <kernel_directory>: 0x00015023  0x00100003  0x00101003  0x00102003
(gdb) p/x kernel_directory[31]
$19 = 0x11e003
(gdb) p/x kernel_directory[32]
$20 = 0x0
(gdb) p/x kernel_table0[0x10]
$23 = 0x10003
(gdb) p/x kernel_table0[0xb8]
$24 = 0xb8003
(gdb) p/x ((uint32_t *)(kernel_directory[1] & 0xfffff000))[0]
$25 = 0x400003
(gdb) p/x ((uint32_t *)(kernel_directory[31] & 0xfffff000))[0x3de]
$27 = 0x7fde003
(gdb) p/x ((uint32_t *)(kernel_directory[31] & 0xfffff000))[0x3df]
$28 = 0x0

QEMU’s monitor can walk the tables for us. info mem lists the mapped virtual ranges, merging contiguous pages with the same flags, and info tlb lists every page:

(gdb) monitor info mem
0000000000000000-0000000007fdf000 0000000007fdf000 -rw
(gdb) monitor info tlb
0000000000000000: 0000000000000000 --------W
0000000000001000: 0000000000001000 --------W
...output omitted...
0000000000010000: 0000000000010000 --------W
0000000000011000: 0000000000011000 ----A---W
...output omitted...
0000000007fde000: 0000000007fde000 --------W

One range, from 0 to 0x7fdf000, 32735 pages, read-write, supervisor only (a u would appear in the flags for user pages). Each line of info tlb is virtual page, physical frame, flags; despite its name it prints the page tables, not the CPU’s TLB. The one A in the excerpt is on the page 0x11000, the one that holds the end of paging_init: the first code fetched through the tables. (The stack page, 0x8f000, has one too, further down the list.)

12.5.5 A mapping that is not the identity

Everything above 0x7fdf000 is unmapped virtual space, and kmain uses it to show the translation at work:

kernel.c

    /* 4. A virtual address far away from any RAM, backed by a real frame.
       Writing through the window and reading the frame directly (it is
       identity-mapped) shows both addresses name the same bytes. */
    frame = pmm_alloc_frame();
    paging_map(0x30000000, frame, PAGE_WRITE);
    window = (volatile uint32_t *)0x30000000;
    *window = 0xCAFEBABE;
    kprintf("virtual %p -> physical %p: wrote 0x%x, read back 0x%x, "
            "the frame holds 0x%x\n", (void *)window, (void *)frame,
            0xCAFEBABE, *window, *(volatile uint32_t *)frame);
    paging_unmap(0x30000000);
    pmm_free_frame(frame);

A frame is allocated, 0x11f000, the next free one after the 31 page tables. It is mapped at 0x30000000, 768 MiB, an address at which the machine has no memory at all. The kernel writes through the window and reads the same value back through the frame’s own address, which is also mapped, by the identity map. Two virtual addresses, 0x30000000 and 0x0011f000, name the same four bytes of RAM:

virtual 0x30000000 -> physical 0x0011f000: wrote 0xcafebabe, read back 0xcafebabe, the frame holds 0xcafebabe

Under gdb, with a conditional breakpoint (b paging_map if virt == 0x30000000) and finish:

(gdb) p/x kernel_directory[0x30000000 >> 22]
$31 = 0x120003
(gdb) p/x ((uint32_t *)(kernel_directory[0xc0] & 0xfffff000))[0]
$32 = 0x11f003
(gdb) monitor info mem
0000000000000000-0000000007fdf000 0000000007fdf000 -rw
0000000030000000-0000000030001000 0000000000001000 -rw

0x30000000 >> 22 is 0xc0, 192: directory entry 192 was empty, so get_table allocated a frame for a new page table, 0x120000, and entry 0 of that table (bits 21:12 of 0x30000000 are 0) now holds frame 0x11f000 with P and R/W. info mem shows the second range. After paging_unmap and pmm_free_frame, the frame is free again but the page table at 0x120000 stays allocated, as the comment in paging_unmap explains; that is the frame that is “missing” when the kernel reports 32445 free at the end instead of 32446.

12.6 Page faults

Vector 14, #PF, is raised when the walk fails: a P bit is clear at either level, or the access violates the R/W or U/S bits, or a reserved bit is set in an entry. Section 5.7 of Volume 3A describes what the CPU reports, and it is more than any other exception: the error code, in the format of figure 5-12, and the faulting linear address in CR2. The error code bits that matter:

CR2 is a register for exactly this purpose: nothing else writes it, and the handler reads it with mov eax, cr2. The chapter-11 dispatcher already routes vector 14 like every other exception, with the CPU’s error code in regs->err_code; all this chapter adds is a handler that decodes it:

paging.c

static void page_fault_handler(struct registers *regs)
{
    uint32_t cr2;

    asm volatile("mov %%cr2, %0" : "=r"(cr2));
    kprintf("\nPage fault at %p: %s, %s, %s mode%s, eip=%p (error code 0x%x)\n",
            (void *)cr2,
            (regs->err_code & 1) ? "protection violation" : "page not present",
            (regs->err_code & 2) ? "write" : "read",
            (regs->err_code & 4) ? "user" : "kernel",
            (regs->err_code & 16) ? ", instruction fetch" : "",
            (void *)regs->eip, regs->err_code);
    panic("unhandled page fault");
}

The handler is installed by paging_init just before paging is turned on. It prints and panics, because, as the comment in the source says, we have nothing to fix. The last lines of kmain provoke it on purpose:

kernel.c

    /* 6. And this is what happens when a program touches memory that is
       not mapped.  Exception 14 is now our page_fault_handler. */
    kprintf("reading unmapped address 0xdeadbeef...\n");
    kprintf("read 0x%x\n", *(volatile uint32_t *)0xdeadbeef);
    kprintf("not reached\n");
    for (;;)
        asm volatile("hlt");
}

and the serial output ends with:

reading unmapped address 0xdeadbeef...

Page fault at 0xdeadbeef: page not present, read, kernel mode, eip=0x00011069 (error code 0x0)

KERNEL PANIC: unhandled page fault

Error code 0: not present, read, supervisor, not a fetch; CR2 is the address the program asked for, and EIP the instruction that asked:

$ objdump -d -M intel build/os/os | grep -B1 -A1 '11069:'
   11064:   b8 ef be ad de          mov    eax,0xdeadbeef
   11069:   8b 00                   mov    eax,DWORD PTR [eax]
   1106b:   83 ec 08                sub    esp,0x8

EIP points at the mov that faulted, not after it: #PF is a fault in the sense of section 7.5 of Volume 3A, as chapter 11 explained. Under gdb with a breakpoint on the handler:

(gdb) b page_fault_handler
Breakpoint 6 at 0x112ee: file paging.c, line 102.
(gdb) c

Breakpoint 6, page_fault_handler (regs=0x8ff7c) at paging.c:102
102     asm volatile("mov %%cr2, %0" : "=r"(cr2));
(gdb) p/x $cr2
$38 = 0xdeadbeef
(gdb) p/x *regs
$39 = {gs = 0x10, fs = 0x10, es = 0x10, ds = 0x10, edi = 0x7fdf000, esi = 0x1fb7c, ebp = 0x8fff8, esp_dummy = 0x8ffac, ebx = 0x7edf, edx = 0x3d5, ecx = 0x2e, eax = 0xdeadbeef, int_no = 0xe, err_code = 0x0, eip = 0x11069, cs = 0x8, eflags = 0x10206, user_esp = 0x0, ss = 0xc0000088}
(gdb) x/i regs->eip
   0x11069 <kmain+531>: mov    eax,DWORD PTR [eax]
(gdb) bt
#0  page_fault_handler (regs=0x8ff7c) at paging.c:102
#1  0x00010dca in isr_dispatch (regs=0x8ff7c) at isr.c:64
#2  0x00010297 in isr_common () at isr_stubs.asm:110
#3  0x0008ff7c in ?? ()
#4  0x0001011b in _start () at entry.asm:30

int_no = 14, err_code = 0, the real one pushed by the CPU this time, eax = 0xdeadbeef, the operand of the mov, and eflags has RF set as in chapter 11. user_esp and ss are the garbage that chapter 11 warned about, and this time the garbage is recognizable: 0xc0000088 is the pointer d that kmain had left on its stack.

(gdb) p 0xdeadbeef >> 22
$42 = 890
(gdb) p (0xdeadbeef >> 12) & 0x3ff
$43 = 731
(gdb) p/x kernel_directory[0xdeadbeef >> 22]
$41 = 0x0

A page fault in kernel mode, U/S = 0, is a bug in the kernel: the kernel is the one that built the tables, so if it touches an address that it did not map, the pointer is wrong, and the only sensible reaction is to stop with as much information as possible, which is what we do. A page fault in user mode, U/S = 1, is different: it may be a bug in the program, in which case the kernel kills that program and carries on, and it may be the normal course of events, a stack that grew into the next page, a page swapped out to disk, a page of a file that is read in only when first touched. In all those cases the handler maps a frame, returns, and the faulting instruction runs again as if nothing had happened; that is demand paging, and the fault classification of chapter 11 is what makes it possible. Chapter 13 adds the user-mode case to this handler.

12.7 A kernel heap

Frames are the right unit for page tables and stacks; they are the wrong unit for a 40-byte task structure or a 12-byte list node, and chapter 13 needs plenty of both. A kernel therefore has an allocator for objects of arbitrary size, traditionally called kmalloc, built on top of the frame allocator exactly as a C library’s malloc is built on top of the pages that the OS gives it. Ours is the smallest useful one: a first-fit free list, with headers, splitting and merging.

heap.h

#ifndef HEAP_H
#define HEAP_H

#include <stddef.h>

/* The kernel heap: kmalloc()/kfree() for objects of any size, built on top
   of the page-sized frames of pmm.c.  It lives in the virtual range
   starting at HEAP_START, which is mapped page by page as it grows. */
#define HEAP_START 0xC0000000
#define HEAP_MAX   (4u * 1024 * 1024)   /* one page table covers it */

void  heap_init(void);
void *kmalloc(size_t size);
void  kfree(void *ptr);

/* For the demonstration in kmain: how many bytes are mapped. */
size_t heap_size(void);

#endif

The heap is a virtual range, from 0xC0000000 up, that is mapped a page at a time as the heap grows. The frames behind it are whatever pmm_alloc_frame returns, not contiguous and not in any order, and the heap does not care: it sees a contiguous range of virtual addresses, which is the first practical use of paging in the kernel. HEAP_MAX caps it at 4 MiB, so that the whole heap fits one page table, directory entry 0x300; chapter 13, which creates a page directory per process and must share the kernel’s mappings between them, relies on the heap not sprawling across more directory entries.

heap.c

struct block {
    size_t size;            /* usable bytes after this header */
    int free;
    struct block *next;     /* next block in address order, or 0 */
    uint32_t magic;         /* BLOCK_MAGIC: catches kfree() of a bad pointer */
};                          /* 16 bytes: keeps the payload 8-byte aligned */

#define BLOCK_MAGIC 0xB10C0000
#define ALIGN 8             /* every block and every size is a multiple of 8 */
#define MIN_SPLIT (sizeof(struct block) + ALIGN)

static struct block *head;      /* first block, at HEAP_START */
static uint32_t heap_end;       /* first unmapped address */

Every allocation is preceded in memory by a 16-byte header: the size of the payload, a free flag, a pointer to the next block, and a magic number. The caller gets the address just after the header, and kfree subtracts 16 to find it again; the magic number is there to catch a kfree of something that was never allocated, or whose header was overwritten by the caller running past the end of the previous block. Sixteen bytes, rather than the twelve that the three useful fields need, keeps every payload on an 8-byte boundary, which double and 64-bit integers want.

static uint32_t grow(size_t bytes)
{
    uint32_t start = heap_end, stop = PAGE_ALIGN_UP(heap_end + bytes);

    if (stop - HEAP_START > HEAP_MAX)
        panic("kernel heap exhausted");
    for (; heap_end < stop; heap_end += PAGE_SIZE) {
        uint32_t frame = pmm_alloc_frame();
        if (frame == 0)
            panic("out of physical memory");
        paging_map(heap_end, frame, PAGE_WRITE);
    }
    return start;
}

void heap_init(void)
{
    heap_end = HEAP_START;
    grow(PAGE_SIZE);
    head = (struct block *)HEAP_START;
    head->size = PAGE_SIZE - sizeof(struct block);
    head->free = 1;
    head->next = 0;
    head->magic = BLOCK_MAGIC;
}

grow is where the three layers of this chapter meet in four lines: for each new page, a frame from the bitmap allocator, mapped at the next heap address by paging_map, which may itself allocate a frame for the page table. heap_init maps the first page and writes one big free block over it, 4080 bytes of payload after the 16-byte header:

(gdb) x/4xw 0xc0000000
0xc0000000: 0x00000ff0  0x00000001  0x00000000  0xb10c0000
(gdb) p/x kernel_directory[0xc0000000 >> 22]
$33 = 0x121023
(gdb) p/x ((uint32_t *)(kernel_directory[0x300] & 0xfffff000))[0]
$34 = 0x11f063

The heap’s page table is at 0x121000, and its first page is backed by frame 0x11f000, the very frame that the mapping test used and freed: the allocator returns the lowest free frame. The PTE is 0x11f063, and its low bits 0x63 = 0110 0011 are P, R/W, A and D: heap_init has just written the header through this mapping, and the CPU recorded both the access and the write.

void *kmalloc(size_t size)
{
    struct block *b, *last = 0;

    size = round_up(size);
    for (b = head; b != 0; last = b, b = b->next) {
        if (!b->free || b->size < size)
            continue;
        if (b->size - size >= MIN_SPLIT) {
            /* Carve the remainder into a new free block after this one. */
            struct block *rest = (struct block *)((char *)(b + 1) + size);
            rest->size = b->size - size - sizeof(struct block);
            rest->free = 1;
            rest->next = b->next;
            rest->magic = BLOCK_MAGIC;
            b->size = size;
            b->next = rest;
        }
        b->free = 0;
        return b + 1;
    }

    /* Nothing fits: extend the heap with a block of exactly the right
       size... or a bit more, since pages come whole. */
    b = (struct block *)grow(sizeof(struct block) + size);
    b->size = heap_end - (uint32_t)(b + 1);
    b->free = 1;
    b->next = 0;
    b->magic = BLOCK_MAGIC;
    last->next = b;
    return kmalloc(size);           /* now the search finds it */
}

First fit: walk the list from the start, take the first free block that is large enough. If the block is larger than needed by at least a header plus the minimum payload, split it: the remainder becomes a new free block right after the allocated one, linked into the list. b + 1, in pointer arithmetic on struct block *, is the address 16 bytes after the header, the payload. If no block fits, the heap grows by enough pages to hold the request, the new space becomes one free block at the end of the list, and the function calls itself, so that the splitting code is not written twice.

void kfree(void *ptr)
{
    struct block *b;

    if (ptr == 0)
        return;
    b = (struct block *)ptr - 1;
    if (b->magic != BLOCK_MAGIC)
        panic("kfree: not a heap block");
    b->free = 1;

    /* Merge every run of adjacent free blocks.  One pass from the start
       is enough because the list is in address order. */
    for (b = head; b != 0; b = b->next) {
        while (b->free && b->next != 0 && b->next->free) {
            b->size += sizeof(struct block) + b->next->size;
            b->next = b->next->next;
        }
    }
}

kfree checks the magic, marks the block free, and then coalesces: because the blocks are contiguous in memory and the list is in address order, two consecutive free blocks can be merged into one by adding the second one’s header and payload to the first one’s size and unlinking it. Without this, a heap that allocates and frees many small objects ends up as a long list of small free blocks none of which can satisfy a medium request, a condition called fragmentation; with it, the heap returns to one big block when everything is freed. The pass is over the whole list, which is simple and slow; exercise 12.4 improves it.

Now the demonstration:

kernel.c

    /* 5. The heap: byte-granular allocations on top of page frames. */
    heap_init();
    a = kmalloc(100);
    b = kmalloc(2000);
    c = kmalloc(50);
    kprintf("kmalloc: a=%p b=%p c=%p (heap %u bytes)\n", a, b, c, heap_size());
    kfree(b);
    d = kmalloc(1000);
    kprintf("after kfree(b), kmalloc(1000) = %p (reuses b's block)\n", d);
    kfree(a);
    kfree(c);
    kfree(d);
    kprintf("%u frames free\n", pmm_free_frames_count());

kmalloc: a=0xc0000010 b=0xc0000088 c=0xc0000868 (heap 4096 bytes)
after kfree(b), kmalloc(1000) = 0xc0000088 (reuses b's block)
32445 frames free

a is at 0xc0000010: the first payload, 16 bytes after the start of the heap. 100 rounds up to 104, so the next header is at 0x10 + 104 = 0x78 and the next payload at 0x88, which is b. 2000 is already a multiple of 8, so c’s header is at 0x88 + 2000 = 0x858 and its payload at 0x868. All three fit in the first page, and the heap is still 4096 bytes. Freeing b leaves a 2000-byte free block between a and c, with nothing free on either side to merge with; the next request, for 1000 bytes, is served from it, at the same address 0xc0000088, with the remaining 984 bytes split off as a new free block. After the three kfree, the whole page is one free block again. The frame count, 32445, is the 32448 after paging_init minus the three frames the heap cost: its page table, its first page, and the page table for 0x30000000 that paging_unmap kept.

The heap’s limitations are the subject of the exercises: the scan is linear, the cap is 4 MiB, pages are never returned to the frame allocator, and there is no protection against writing past the end of a block except the magic number of the next header, which only tells you that something went wrong, not where. A production allocator (Linux’s slab allocator, for instance) keeps separate lists per object size and knows the type of what it allocates; the interface, a size in and a pointer out, is the same.

12.8 Building, testing and debugging

The Makefile changes are two lines: the test target now waits for the page fault message instead of the third timer tick, and the comment at the top. The kernel’s own Makefile is untouched, because it compiles every .c in the directory. The kernel ELF has grown to 65972 bytes, hence KERNEL_SECTORS=129 in the bootloader build:

$ make
...output omitted...
nasm -f elf -F dwarf -g -DKERNEL_SECTORS=129 bootloader.asm -o ../build/bootloader/bootloader.o
...output omitted...

and readelf -l shows a change worth noticing:

$ readelf -l build/os/os

Elf file type is EXEC (Executable file)
Entry point 0x10100
There are 2 program headers, starting at offset 52

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x00010034 0x00010034 0x00040 0x00040 R   0x4
  LOAD           0x000000 0x00010000 0x00010000 0x02a60 0x07030 RWE 0x1000

 Section to Segment mapping:
  Segment Sections...
   00     
   01     .text .rodata .data .bss 

The file part of the segment is 0x2a60 bytes, 11 KiB, but the memory part is 0x7030, 28 KiB, and the segment’s alignment is now 0x1000 where chapter 11 had 0x100. Both come from the aligned(PAGE_SIZE) on the two paging arrays: .bss now contains three 4 KiB-aligned pages, and the linker raised the segment alignment to match. readelf -S and nm show where everything landed:

$ readelf -S build/os/os | grep -E 'text|rodata|data|bss'
  [ 1] .text             PROGBITS        00010100 000100 00207c 00  AX  0   0 256
  [ 2] .rodata           PROGBITS        00012180 002180 00084d 00   A  0   0 32
  [ 3] .data             PROGBITS        000129e0 0029e0 000080 00  WA  0   0 32
  [ 4] .bss              NOBITS          00013000 002a60 004030 00  WA  0   0 4096
$ nm -n build/os/os | grep -E ' (__bss_start|__bss_end|__kernel_end|__kernel_start|kernel_directory|kernel_table0|bitmap|idt|gdt|head|heap_end)$'
00010000 A __kernel_start
00013000 B __bss_start
00013000 b gdt
00013020 b head
00013024 b heap_end
00013040 b idt
00014000 b kernel_directory
00015000 b kernel_table0
00016020 b bitmap
00017030 B __bss_end
00017030 B __kernel_end

.bss starts at 0x13000, itself page-aligned, with the GDT, the heap variables and the IDT; the page directory is at 0x14000, the table at 0x15000, the frame bitmap after it at 0x16020, and the kernel ends at 0x17030. These are the numbers that CR3 and monitor info registers showed, and that __kernel_end reported to the frame allocator. The .bss pages have no bytes in the file, so, as chapter 9 explained, entry.asm zeroes them before kmain; paging_init clears the directory again with memset anyway, because a page directory is the one structure where a stale bit is a security hole.

The .gdbinit only changed its comment. The sessions above were all produced with make qemu in one terminal and make gdb in another, and the recipe is worth keeping: b paging_init, c, finish to stop just after the switch; monitor info registers for the control registers; monitor info mem for the mapped ranges; p/x kernel_directory[n] and the cast ((uint32_t *)(kernel_directory[n] & 0xfffff000))[m] to walk a level by hand; b page_fault_handler and p/x $cr2 when something faults. When a bug sends the kernel into a triple fault right after mov cr0, the -d int log of chapter 11 shows a v=0e with CR2 equal to the address of the next instruction, and the fix is always in the entry for that page.

12.9 Exercises

12.10 Check your understanding

1. Why can the kernel not ask the processor how much RAM the machine has, and why must the memory map be collected before the switch to protected mode?
2. pmm_init starts by marking every frame used and then frees the usable ranges. What would go wrong with the opposite strategy, start free and mark the reserved ranges used, on QEMU’s map?
3. Why do the two roundings in mark_range go in opposite directions? Which frame of our map does that protect?
4. The instruction after mov cr0, eax with PG set is already fetched through the page tables. What must be true for it to execute, and what does a mistake look like in the -d int log?
5. Why does the heap start at 0xC0000000 rather than right after the kernel, and what would mapping it at 0x00400000 do?
6. Why does paging_map execute invlpg after each store into a page table, and what could a stale TLB entry do after paging_unmap?
7. A page fault reports “page not present” for 0xdeadbeef. From the error code alone, can the handler tell whether the directory entry or the page-table entry was missing? Where else would it have to look?
8. Why must kernel_directory be 4 KiB aligned, and how did that one attribute change the ELF segment alignment from 0x100 to 0x1000?