fork, Built Rather Than Read

11 · fork, Built Rather Than Read¶

The question¶

What is the least a machine needs before two programs can run on it?

fork is usually introduced as a riddle: a function that returns twice, with different answers. It is not a riddle. It looks like one because it is normally met from the outside. From the inside it is a short function, and the two returns stop being mysterious once you can see that a return value is a word in a saved register set.

Everything this chapter needs already exists. ch08 built an address space — a page table, and so a private view of memory; ch09 saved a caller’s registers into a frame. A process is those two things kept together, and fork is a copy.

The material¶

What a process is, here¶

struct proc {
    uint64 frame[32]; /* the registers it had when it last left the processor */
    uint64 epc;       /* and where it was */
    uint64 *root;     /* its address space */
    uint64 *page;     /* the physical page behind USER_VA, so machine mode can look */
    int used;
};

A saved register set, a place it was, and an address space. That is the whole of it — and the first field is ch09’s trap frame, unchanged. The frame was built to survive a system call; keep it a little longer and it is a saved process.

Mapping one page rather than one gigabyte¶

ch08 got away with three top-level leaf entries. A per-process page needs a real walk — an entry at each of the three levels — because four kilobytes is a leaf at the bottom level, and the levels above it have to exist first:

/* Walk to the leaf entry for one virtual address, making the levels that are missing. Three
 * levels, nine bits each, because Sv39 is thirty-nine bits of address and the bottom twelve are
 * the offset within a page. The bare-metal paging chapter used gigabyte leaves and needed none of this. */
static uint64 *leaf_entry(uint64 *root, uint64 va) {
    uint64 *table = root;
    for (int level = 2; level > 0; level--) {
        uint64 *entry = &table[(va >> (12 + 9 * level)) & 0x1FF];
        if (*entry & PTE_V) {
            table = (uint64 *)(((*entry) >> 10) << 12);
        } else {
            uint64 *next = take_page();
            *entry = (((uint64)next >> 12) << 10) | PTE_V; /* no R/W/X: a pointer, not a leaf */
            table = next;
        }
    }
    return &table[(va >> 12) & 0x1FF];
}

Each process gets the kernel’s identity mappings — without them the code would vanish the moment its own table was installed — plus one page of its own at the same virtual address:

static uint64 *build_address_space(uint64 *user_page) {
    uint64 *root = take_page();
    /* The kernel's own mappings, identity, so that the code keeps running with paging on. */
    root[DEVICES_BASE / GIGABYTE] = ((DEVICES_BASE >> 12) << 10) | PTE_LEAF;
    root[RAM_BASE / GIGABYTE] = ((RAM_BASE >> 12) << 10) | PTE_LEAF;
    *leaf_entry(root, USER_VA) = (((uint64)user_page >> 12) << 10) | PTE_DATA | PTE_U;
    return root;
}

Same address in both processes, different physical page behind it. That is what “its own memory” means, mechanically, and it is why an address space is worth having.

fork¶

static int fork_current(uint64 *frame) {
    struct proc *parent = &procs[current];
    struct proc *child = &procs[current + 1];

    for (int i = 0; i < 32; i++) {
        child->frame[i] = frame[i];
    }
    /* The one edit that makes the answer differ. Everything else about the two is identical. */
    child->frame[10] = 0;
    child->epc = bare_csr_read(mepc) + 4;

    child->page = take_page();
    for (uint64 i = 0; i < BARE_PAGE_BYTES / sizeof(uint64); i++) {
        child->page[i] = parent->page[i];
    }
    pages_copied++;

    child->root = build_address_space(child->page);
    child->used = 1;
    children_made++;
    return current + 1;
}

The frame is copied wholesale and then one slot is changed, and that one line is why fork returns twice. Slot ten is a0, where a system call’s return value lives, and the child resumes by having its frame loaded back into the registers. Two frames, identical but for one word, produce two returns with different answers.

The page is copied too — a fresh page and a byte-for-byte duplicate, so the child begins with everything the parent had and can then diverge. This is the eager version, and it is what xv6’s uvmcopy does too: a fresh page and a copy, per page, at the moment of the call. ch18 is where that stops being necessary.

Putting a process back on the processor¶

/* Put a saved process back on the processor: its registers, and where it was.
 *
 * `sp` is loaded last because every other load is relative to it, and a frame is not somewhere
 * you can still address once you have replaced the pointer to it. */
__attribute__((naked)) void bare_enter_process(uint64 *frame, uint64 epc) {
    asm volatile("csrw mepc, a1\n"
                 "mv   sp, a0\n"
                 "ld x1,1*8(sp)\n  ld x3,3*8(sp)\n  ld x4,4*8(sp)\n  ld x5,5*8(sp)\n"
                 "ld x6,6*8(sp)\n  ld x7,7*8(sp)\n  ld x8,8*8(sp)\n  ld x9,9*8(sp)\n"
                 "ld x10,10*8(sp)\n ld x11,11*8(sp)\n ld x12,12*8(sp)\n ld x13,13*8(sp)\n"
                 "ld x14,14*8(sp)\n ld x15,15*8(sp)\n ld x16,16*8(sp)\n ld x17,17*8(sp)\n"
                 "ld x18,18*8(sp)\n ld x19,19*8(sp)\n ld x20,20*8(sp)\n ld x21,21*8(sp)\n"
                 "ld x22,22*8(sp)\n ld x23,23*8(sp)\n ld x24,24*8(sp)\n ld x25,25*8(sp)\n"
                 "ld x26,26*8(sp)\n ld x27,27*8(sp)\n ld x28,28*8(sp)\n ld x29,29*8(sp)\n"
                 "ld x30,30*8(sp)\n ld x31,31*8(sp)\n"
                 "ld x2,2*8(sp)\n"
                 "mret\n");

sp is loaded last because every other load is relative to it, and a frame stops being addressable the instant you replace the pointer to it.

The scheduler is four lines, and calling it a scheduler is generous:

void bare_process_left(void) {
    if (current + 1 < PROCESSES && procs[current + 1].used) {
        current++;
        bare_csr_write(satp, SATP_SV39 | ((uint64)procs[current].root >> 12));
        asm volatile("sfence.vma zero, zero");
        bare_enter_process(procs[current].frame, procs[current].epc);
    }
}

Install the next process’s address space, load its registers, mret. There is no policy, no priority and no preemption — nothing takes the processor away from a process that has not given it up. ch21 is where the interesting parts go back in.

The kernel cannot simply dereference what it is given¶

One detail here is a genuine trap, and it cost a confusing hour:

    /* The handler runs in machine mode, and machine mode ignores `satp`. So it cannot simply
     * dereference the address its caller gave it: `USER_VA` here would be a *physical* address,
     * and on this board there is a PCI window at that number which answers every read with ones.
     *
     * What the kernel has to do instead is translate for itself — here trivially, because it
     * remembers which physical page it gave each process. A real kernel walks the caller's page
     * table to do the same thing, and `copyin` is what that function is called. */
    case SYS_PEEK:
        return procs[current].page[0];
    case SYS_POKE:
        procs[current].page[0] = frame[10];
        return 0;

The handler runs in machine mode, and ch08 established that machine mode ignores satp. So an address the caller supplies is not an address the handler can use — and on this machine the particular number involved lands in a region QEMU reserves for PCI devices, which answers every read with ones, so the failure is not even a fault. It is a plausible-looking wrong answer.

A real kernel walks the caller’s page table to translate by hand. That function is called copyin, and this is why it exists.

What we measured¶

Run it yourself before reading the table — the rows below are what you should see, and a figure you have reproduced is worth more than one you have been shown:

./run fork

Conditions: target bare · qemu virt (-machine virt -bios none) · QEMU emulator version 8.2.2 (Debian 1:8.2.2+ds-0ubuntu1.18) · no firmware, no kernel · riscv64-linux-gnu-gcc · -march=rv64g -mabi=lp64 -mcmodel=medany -ffreestanding -nostdlib -fno-pic -fno-stack-protector -fno-builtin -O1 -g -Wall -Werror · 2026-09-17 · Source: bench/results/fork-bare.json, code hash 5b436c26f6ab9ccd.

One page copied, for one page mapped. xv6 copies every mapped page of the parent the same way — kalloc and memmove per page, no sharing — so the count here is small for the same reason the program is small, not because the strategy differs.

What this cannot tell you¶

What fork costs. Copying a page has a price, copying a thousand has a much larger one, and the entire reason real kernels stopped doing this eagerly is a number this target cannot produce. ch29 measures a real fork, and the gap between an eager copy and what Linux actually does is most of the answer.

What the child should inherit. The child here gets the address space and nothing else, because there is nothing else. A real fork has to decide about descriptors, the working directory, signal handlers, resource limits and more. ch10’s two tables answer the descriptor half: the descriptor table is copied, the open files it refers to are shared.

Whether two processes really run concurrently. They do not. One runs, gives up, and the other starts. Nothing here preempts anything, and both are on one hart.

What happens when the table is full. There is room for two, fork is called once, and the question of what a process table does when it runs out is left entirely alone. xv6’s allocproc returns zero; what the caller should do about it is a design question this program never has to face.

Problems¶

Three, in tests/fork_built_rather_than_read/.

11.1 — Make the child run first. The parent continues and the child waits. Swap it, so the child runs to completion before the parent resumes, without changing what either prints. The test checks the order and that both still report correctly.

python3 -m pytest tests/fork_built_rather_than_read/test_problem_1_child_first.py

11.2 — Run out of processes. Call fork until the table is full. Decide what it returns then, implement it, and show the caller handling it. The test checks the failure is distinguishable from a successful fork and that the machine survives it.

python3 -m pytest tests/fork_built_rather_than_read/test_problem_2_full_table.py

11.3 — Count what a lazy fork would save. Do not implement copy-on-write — sharing the parent’s pages and copying one only when somebody writes to it. Instead, say exactly which of this program’s steps it would remove, what it would add, and what new trap the handler would have to deal with. The test asks for the cause code of that trap and for which page-table bit changes, both of which you have met.

python3 -m pytest tests/fork_built_rather_than_read/test_problem_3_lazy.py

Where to go next¶

The privileged specification RISC-V International (n.d.) has the page-table entry bits this program sets by hand, including the one problem 11.3 asks about.

This is the end of Part II. Part III steps back to ask what a program is before Part IV reads a kernel — and that kernel’s fork will look like a longer version of this one rather than a new idea, which was the point of building it.