One Page Table, Two Harts

08 · One Page Table, Two Harts¶

The question¶

What does address translation do, and what does a second core break?

Two questions, and two programs, because they are two mechanisms and a chapter that ran them together would teach neither. Both are the hardware changing what memory does behind the program’s back: translation does it deliberately and usefully; a second core does it simply because there is more than one processor.

The material¶

An address is a number until something translates it¶

Everything so far has used addresses that were what they said. &x was where x actually was; the UART (the console’s serial device) was at the number the machine’s documentation gives. Translation — the hardware turning every address a program uses into the one memory actually sees — makes that stop being true, and the whole of the mechanism is a table the program writes and a register that points at it.

Sv39, RISC-V’s translation scheme for 64-bit machines RISC-V International (n.d.), splits a thirty-nine-bit address into three nine-bit indexes and a twelve-bit offset, which means three levels of table. This program needs none of that, because an entry at the top level can be a leaf — one that maps memory directly instead of pointing at the next table down — covering a whole gigabyte at once:

/* A leaf entry for a whole gigabyte. The physical page number is the address shifted right by
 * twelve; the entry holds it shifted left by ten, which is the ten bits of flags underneath. */
static uint64 gigapage(uint64 physical) {
    return ((physical >> 12) << 10) | PTE_LEAF;
}

The entire table is three entries:

static void build_the_table(void) {
    root[DEVICES_BASE / GIGABYTE] = gigapage(DEVICES_BASE);
    root[RAM_BASE / GIGABYTE] = gigapage(RAM_BASE);
    root[ALIAS_BASE / GIGABYTE] = gigapage(RAM_BASE); /* the alias: a second name for RAM */
    entries_used = 3;
}

Two of them map memory to itself — an identity mapping. They have to: the moment translation is switched on, the instruction after the switch is fetched through the table, and a table without the code in it would make the program vanish. The third points a different virtual address — the kind a program uses — at the same physical memory — the kind the chips have — so that afterwards two addresses a gigabyte apart name one byte.

Switching it on is one register — satp, which points at the table — and one instruction:

    bare_csr_write(satp, SATP_SV39 | ((uint64)root >> 12));
    asm volatile("sfence.vma zero, zero"); /* the processor may have cached the old answer */

sfence.vma is there because the processor is allowed to remember translations it has already worked out, and is not obliged to notice that the table changed underneath it. Forgetting it gives a program that works until it does not, which is among the least pleasant kinds of bug.

And then the part that catches everyone: machine mode ignores satp entirely. Translation applies to supervisor and user mode; machine mode addresses are physical, always. So the program has to leave machine mode before any of this means anything, which is why ch07 came first.

The demonstration itself is then one variable read twice, by its own address and through the alias, before an ecall asks machine mode to take the program back:

/* Runs with translation on. Everything it touches is either identity-mapped or the alias. */
__attribute__((noinline)) static void in_supervisor_mode(void) {
    uint64 offset = (uint64)&marker - RAM_BASE;
    volatile uint64 *through_alias = (volatile uint64 *)(ALIAS_BASE + offset);

    reached_supervisor = 1;
    marker_direct = marker;
    marker_through_alias = *through_alias;

    asm volatile("ecall"); /* ask machine mode to take us back */
}

What a second core breaks¶

The second program has two processors in it, and one counter.

The usual way to show what goes wrong is to start both harts incrementing as fast as they can and observe that the total comes out short. That works, sometimes, and teaches the wrong thing when it does: it makes lost updates look like weather. The useful claim is narrower: counter = counter + 1 is a load, an add and a store, and anything at all happening between the load and the store is enough.

So this loses an update on purpose, identically every run, by holding those three instructions apart and letting the other hart finish entirely in the gap. The two flags are the handshake that holds it open:

    /* The three instructions of `counter = counter + 1`, with the other hart invited into the
     * gap between the load and the store. */
    stale = counter;      /* 1. load:  reads 0 */
    hart1_may_go = 1;     /*    ... and here the other hart does its entire increment ... */
    while (!hart1_finished) {
    }
    counter = stale + 1;  /* 2. add, 3. store: writes 1 over the other hart's 1 */

The other hart’s whole increment happens inside one statement of this one. Both processors incremented; the counter went up once.

Then the same shape with an atomic instruction — one that cannot be interrupted part-way through, because it is one instruction. __sync_fetch_and_add asks the compiler for it, and on this machine it is amoadd, a load, an add and a store in a single step:

    /* The same shape, with an instruction that has no gap in it. */
    __sync_fetch_and_add(&atomic_counter, 1);
    hart1_may_go_atomic = 1;
    while (!hart1_finished_atomic) {
    }

Nothing is lost, and nothing about the schedule changed. What changed is that there is no longer a moment at which the counter has been read but not yet written.

What we measured¶

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

./run paging
./run harts

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/paging-bare.json, code hash ef29e43c6d7be324.

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/harts-bare.json, code hash 0c2a2353f264220a.

The runner refuses a run in which updates_lost is anything but exactly one, because if the handshake ever stopped holding the read-modify-write open, the program would still boot, still print, and still look convincing, while showing nothing at all.

What this cannot tell you¶

How expensive any of this is. A page-table walk costs something, a translation cache exists to avoid paying it, and two cores touching one cache line — the unit in which memory moves between them — cost each other a great deal. None of that is visible here. ch25 and ch28 are those questions on hardware, and the second one is where the atomic instruction above stops looking free.

What actually happens when two real cores race. The lost update here was arranged. On real hardware the ordering is decided by machinery this target has none of — ch28 names it — and the answer is neither deterministic nor as simple as one update going missing. What transfers from this chapter is the shape of the hazard, not its likelihood.

Whether one atomic is enough. It was here, for one counter. It is not a general answer: an operation that cannot be split is not the same as a sequence of them that cannot be reordered, and the second is what a lock needs.

Problems¶

Three, in tests/one_page_table_two_harts/.

8.1 — Map a page rather than a gigabyte. Change the alias to cover four kilobytes instead of a gigabyte. You will need the two levels this chapter skipped. The test checks that the alias still reads the same byte and that the entry at the top level is no longer a leaf.

python3 -m pytest tests/one_page_table_two_harts/test_problem_1_four_kilobytes.py

8.2 — Break it on purpose. Remove one of the two identity mappings and predict, before running it, exactly which instruction the machine fails on and with what cause. Then run it. The test compares your prediction with the run.

python3 -m pytest tests/one_page_table_two_harts/test_problem_2_no_identity.py

8.3 — Lose an update the other way round. The program loses the second hart’s increment. Rearrange the handshake so it loses the first hart’s instead, without changing the counter’s final value. Say which of the three instructions moved. The test checks the value, the loss, and that you did not simply swap the two harts’ code.

python3 -m pytest tests/one_page_table_two_harts/test_problem_3_other_way.py

Where to go next¶

The privileged specification RISC-V International (n.d.) defines Sv39, the page-table entry format and satp; the unprivileged specification RISC-V International (n.d.) defines the atomic instruction the second program leans on. Both are worth having open — the entry format in particular is one diagram and this chapter built it by hand.

ch09 turns the boundary this chapter crossed into an interface.