Hart 0 builds the kernel page table, writes started = 1, and enables paging. Hart 1 observes started == 1 and immediately loads a stale page-table root because the compiler or CPU made the flag visible before the page-table writes. The source order looks correct; volatile would still not create inter-hart publication. Early boot is a concurrent protocol with fewer diagnostics than ordinary code, not a magical phase exempt from memory ordering.
Boot has one governing invariant:
Activation invariant. No execution context may use a facility until the facility’s state is constructed, its dependencies are live, and publication makes those writes visible to that context.
Failure localization before terminology
For the stale-page-table scenario, separate the failure into three questions: Was the table constructed? Was its address published? Was the consuming hart activated only after an acquire operation? State one observation that distinguishes each failure.
HintExpandCollapse
A ready flag can have the correct value while the object it announces is not safely visible.
Worked solutionExpandCollapse
Construction is tested by inspecting the producing hart’s table memory and root value before publication. Publication is tested by verifying a release operation occurs after all table writes and that the announced root is the one later loaded. Activation is tested by verifying each secondary hart performs a matching acquire before reading the table or enabling translation. A zero or malformed PTE suggests construction; a wrong root suggests publication of identity; correct producer memory but stale consumer data suggests missing synchronization. A debugger that halts all harts may accidentally add ordering and hide the defect.
Reset, handoff, entry, and activation
These stages must be named by contract rather than by a universal product sequence.
| Stage | Producer’s obligation | Kernel may assume | Kernel must not assume |
|---|---|---|---|
| Reset/firmware | Establish architecture-defined reset state and platform firmware behavior | Only the documented platform contract | A C stack, a page table, or discovered RAM unless promised |
| Loader/firmware handoff | Place the image and provide entry parameters | Entry PC, image layout, register/CSR state explicitly specified | UEFI, BIOS, or device tree on every platform |
| Assembly entry | Establish stack and minimal execution environment | Linker-defined symbols and handoff registers | Allocator, interrupts, or global constructors are ready |
| Privilege setup | Configure delegation, protection, timer access, and return target | CSRs written by the boot code | Supervisor mode is active before mret |
| Global construction | Initialize shared allocators, tables, drivers, and the first process | Single bootstrap owner where the protocol guarantees it | Secondary harts see writes before publication |
| Per-hart activation | Install hart-local translation, trap vector, and interrupt routing | Published global state | Another hart configured this hart’s local CSRs |
“Bootloader” is therefore a role, not one mandatory binary. In the xv6 rev5 QEMU configuration, QEMU loads the kernel at physical 0x80000000 with -bios none and starts each hart at _entry. A production RISC-V Linux kernel expects a different documented handoff, including hart ID and device-tree address registers and satp=0.
Retrieval — identify the contract, not the brand
A platform jumps to the kernel with translation disabled, a0=hartid, a1=device_tree_pa, and interrupts masked. Which facts belong in a portable kernel-entry contract, and which would be unjustified additions?
Worked solutionExpandCollapse
The four stated facts belong in the contract: entry PC by implication, translation disabled, register arguments, and interrupt state. It is unjustified to infer UEFI remains callable, RAM begins at a particular address, all harts enter simultaneously, .bss is zeroed, or a stack exists. Those may be supplied by a specific image format or loader, but each needs separate evidence. The reasoning gap is replacing an explicit handoff with a familiar PC boot story.
Worked trace: one xv6 hart reaches C
Xv6 rev5 fixes enough details for an exact trace.
| Cut | Mode | PC / operation | Stack and translation | Established fact |
|---|---|---|---|---|
| 0 | M | QEMU jumps to _entry at 0x80000000 | no xv6 stack; paging off | image placement matches kernel.ld |
| 1 | M | _entry reads mhartid | selects one 4096-byte slice of stack0 | C calls cannot collide across harts |
| 2 | M | call start | valid aligned stack; paging off | C machine-mode setup can run |
| 3 | M | start writes mstatus.MPP=S, mepc=main, satp=0 | same stack | mret target and next privilege fixed |
| 4 | M | delegates traps, configures PMP, timer access, and tp=hartid | same stack | supervisor kernel receives intended events/resources |
| 5 | S | mret transfers to main | paging still off | C supervisor initialization begins |
The stack formula is
The +1 makes sp point just above the hart’s downward-growing stack slice. If hart 0 used stack0 + 0, its first push would write before the allocation.
The diagram encodes a partial order, not a duration chart. Global construction occurs once; CSR activation occurs per hart. Rev5 implements publication with __sync_synchronize() before the bootstrap hart’s volatile flag store and another __sync_synchronize() after a secondary observes the flag. Those full compiler/hardware fences play the ordering role; the volatile access alone would not publish the preceding object initialization. This is the concrete rev5 protocol, not a claim that the source uses C11 release/acquire atomics.
Application — corrupt the entry stack
Assume NCPU=8 but stack0 reserves only four 4096-byte slices. Explain two distinct failure signatures: hart 5 enters C, and hart 5 never enters C because only four harts are started.
Worked solutionExpandCollapse
If hart 5 enters, its computed SP points beyond stack0; a call or spill corrupts adjacent static storage, often producing delayed, symbol-dependent failures. If the platform starts only harts 0–3, the undersized array is latent: no current access is out of bounds, but the binary violates its declared NCPU configuration. A correct audit checks both allocated capacity and the actual set of entering hart IDs; “it boots on my four-core QEMU command” does not prove the formula safe.
Multicore Boot Publication Matrix
Hart 0 builds the kernel page table and sets started = 1. Evaluate each statement regarding multicore memory publication without memory fences:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
From machine mode to a supervisor kernel
mret uses mstatus.MPP to choose the next privilege and mepc as the next PC. xv6 also arranges that supervisor mode can access RAM through PMP, receives delegated exceptions and interrupts, can read the time counter, and receives timer events. These are independent permissions. Setting the return privilege does not automatically delegate traps or grant physical-memory access.
The trap delegation values in a teaching kernel are a platform choice, not a portable recipe. A firmware environment may retain machine-mode responsibilities. A secure monitor may deliberately withhold regions. A robust explanation lists the authority each CSR grants rather than presenting a block of writes as ceremony.
Transfer — one missing machine-mode permission
Supervisor code reaches main but faults on its first RAM access. satp=0, the physical address is correct, and mstatus.MPP was set to S. Which machine-mode setup should be investigated first, and why does successful mret not exonerate it?
Worked solutionExpandCollapse
Investigate PMP configuration. The privilege return and physical-memory authorization are separate controls: mret can enter S-mode while PMP denies S-mode access to the RAM region. Check pmpaddr0/pmpcfg0 and firmware-reserved ranges before blaming the page table, which is disabled. The failure reveals a missing authority grant, not an incorrect control-transfer target.
Global construction is a dependency graph
On the bootstrap hart, xv6 rev5 performs this high-level order:
console → physical allocator → kernel page table → enable paging
→ process table → trap state → interrupt controller
→ buffer cache → inode/file tables → disk → first process
→ publish started
The real graph branches. Console output can precede the allocator. Kernel stacks require physical pages and mappings. Per-hart trap-vector installation requires a valid vector address on that hart. The first user process needs process-table and filesystem-facing state. The scheduler needs a process table and a valid per-hart context, but it need not wait for every optional driver in a different design.
The graph is more useful than memorizing calls because it supports counterfactual design. A RAM-only first process could remove the disk/filesystem dependency. A demand-loaded driver could move activation later. Every moved node needs a revised error and concurrency contract.
Dependency exercise — parallelize without guessing
A team wants to initialize the buffer cache, inode table, and interrupt controller on secondary harts before started is published. Give a safe plan or reject the proposal. State the ownership and publication needed for each parallel task.
Worked solutionExpandCollapse
A safe plan needs more than graph independence. The allocator and kernel mappings must already be published to workers. Each initialization task must have exclusive ownership of its state or internal synchronization; the bootstrap hart needs a join/acquire before any consumer runs. Buffer-cache construction and inode-table construction may contend for allocator state and may have an ordering edge if inode initialization assumes cache locks exist. Interrupt-controller setup often has both one-time global and per-hart parts, so assigning it wholesale to one worker is incorrect. Reject the proposal unless these contracts are exposed. Parallelizing a short teaching-kernel boot is unlikely to justify the proof burden, but the decision should follow dependencies and measurements, not instinct.
Worked failure trace: publishing before the first process
Suppose rev5’s __sync_synchronize(); started = 1 publication sequence is moved immediately after the page table is initialized, before procinit() and userinit().
- Hart 1 observes nonzero
started, crosses rev5’s consumer-side full fence, safely observes the page table, installs translation and its trap vector, then callsscheduler(). - The scheduler scans
proc[]while hart 0 is still initializing process locks and states. - Hart 1 may acquire an uninitialized lock, observe zero-filled state that happens to resemble an enum member, or race with
userinit()publishing the first runnable process. - The fence/flag/fence ordering has worked; the published predicate did not imply that process state was initialized.
The repair is not “use stronger memory ordering.” Publish a condition whose truth implies every stated dependency of the consumer, or use separate phase barriers. Synchronization orders writes; it does not invent the right invariant.
Counterexample — a successful boot that is still wrong
Hart 1’s scheduler sees no runnable process, executes wfi, and later wakes on a timer after hart 0 has created the first process. The system appears to work. Why must the early publication still be rejected?
Worked solutionExpandCollapse
The path relies on accidental zero-state interpretations, interrupt timing, and unsynchronized concurrent initialization. A different compiler, hart count, timer phase, or lock representation can expose corruption. Eventual wakeup does not prove process-lock construction or state publication was race-free. The correct criterion is the activation invariant across all allowed executions, not one observed boot transcript.
Kernel organization: call boundary, protection boundary, fault boundary
xv6 is monolithic: process management, virtual memory, filesystems, and drivers execute in one supervisor address space. Source files and C interfaces improve reasoning, but a wild write in one subsystem can mutate another subsystem’s state.
Compare three kinds of boundary:
| Boundary | Enforcement mechanism | Failure contained? | Typical cost |
|---|---|---|---|
| C module/API | language and build conventions | not against memory corruption in privileged C | ordinary call |
| in-kernel compartment | memory protection, language isolation, or control-flow enforcement | depends on mechanism and shared authority | checked call / mapping change |
| user-space service | separate address space plus IPC authority | direct memory faults usually contained; protocol faults may propagate | trap, scheduling, copying or mapping |
Moving a driver to user space can reduce direct kernel-memory authority, but it adds IPC, lifecycle, and recovery paths. A monolithic call can be fast and simple, but every privileged parser joins the TCB. “Microkernel is secure” and “monolithic is fast” are incomplete claims until the workload, hardware, and authority graph are specified.
Synthesis — isolate a fallible parser
A new kernel feature parses an untrusted, variable-length device manifest during boot. Design two placements: privileged in-process and isolated service. For each, state the earliest boot phase, required authority, failure recovery, and evidence needed to choose.
Worked solutionExpandCollapse
The privileged design can run after a bounded input buffer, allocator, and diagnostics exist. Give it read-only access to the manifest and a narrow builder API rather than raw global pointers; parse into temporary state, validate references and lengths, then commit. Failure can reject the device or stop boot, but memory corruption remains in the TCB. The isolated design requires address spaces, IPC, scheduling, and a way to hand over a bounded buffer, so it must run later or use a pre-kernel compartment mechanism. It can be restarted on a fault, but the kernel must validate the returned object graph and handle service absence. Measure boot latency and memory cost, fuzz both protocol boundaries, and audit authority. Isolation is valuable only if the trusted consumer does not blindly accept malicious parsed output.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.3.1: Per-Hart Entry Stack Allocation and Bounds Corruption
In RISC-V xv6 entry.S, initial stack pointers are computed as sp = stack0 + (hartid + 1) * 4096. Explain the failure modes that occur if NCPU is configured to 8 but stack0 in static data allocates only four 4096-byte slices.
HintExpandCollapse
Trace the memory layout when hart 5 writes to its computed stack pointer.
Worked solutionExpandCollapse
Each hart computes an offset based on its hardware ID. If only 4 slices (16 KiB) are allocated in the BSS/data segment, harts 0 through 3 occupy valid bounds. When hart 4 or 5 boots, its computed sp points beyond the stack0 buffer into adjacent static kernel variables (such as kernel locks or page tables). Any subsequent function call or register spill corrupts those symbols, causing delayed, non-deterministic system panics. If the hardware platform only powers on harts 0 through 3, the bug remains latent until tested on an 8-core CPU.
Exercise 1.3.2: Memory Ordering Fences in Secondary Hart Bootstrapping
Hart 0 constructs the kernel page table and initializes subsystems before setting a volatile flag started = 1. Secondary harts spin on while (started == 0). Explain why removing memory fences (__sync_synchronize()) causes secondary harts to crash even though started is declared volatile.
HintExpandCollapse
Contrast compiler volatile semantics with hardware store-buffer visibility across CPU cores.
Worked solutionExpandCollapse
In C, volatile prevents compiler register caching and dead-code elimination on the variable itself, but it does NOT emit CPU memory barrier instructions. Modern out-of-order or weakly-ordered architectures (like RISC-V) buffer stores in local write buffers. Without a release fence (__sync_synchronize()) on hart 0, the write started = 1 can become globally visible to hart 1 before the stores populating the page tables and kernel data structures drain to cache. Hart 1 then exits its spin loop and loads uninitialized, corrupt page tables into satp.
Exercise 1.3.3: Machine-Mode Handoff, PMP, and Exception Delegation
Detail why setting mstatus.MPP to supervisor mode and jumping to mret is insufficient to establish a functioning supervisor kernel without configuring Physical Memory Protection (PMP) and trap delegation CSRs (medeleg and mideleg).
HintExpandCollapse
Recall that machine mode owns all physical memory by default and traps trap to machine mode unless delegated.
Worked solutionExpandCollapse
By default on RISC-V, all traps (exceptions and interrupts) trap to machine mode (M-mode), and supervisor mode (S-mode) has zero physical memory access rights. If M-mode executes mret into S-mode without programming pmpcfg0 and pmpaddr0 to grant supervisor read/write/execute permissions to physical RAM, the first instruction fetch in S-mode immediately triggers an access fault. Furthermore, without setting bits in medeleg (system calls, page faults) and mideleg (timer and external interrupts), any subsequent user trap or timer interrupt traps back into M-mode rather than reaching the kernel’s supervisor trap handler.
Exercise 1.3.4: Subsystem Construction Graph and Premature Interrupt Hazards
Construct the strict partial order of initialization in main() for the following kernel subsystems: console, physical page allocator, kernel page table, process table, trap vector, and PLIC interrupt controller. Identify the failure that occurs if interrupts are enabled before the process table is initialized.
HintExpandCollapse
Map the prerequisite resources required by each subsystem constructor.
Worked solutionExpandCollapse
Strict initialization order:
- Console and print locks (enables diagnostic output).
- Physical page allocator
kinit()(provides free physical frames). - Kernel page table
kvminit()and activationkvminithart()(enables MMU translation). - Process table
procinit()(allocates proc locks and kernel stacks). - Trap vector
trapinithart()(installskernelvecintostvec). - PLIC / timer interrupt controller
plicinit()andplicinithart(). If device interrupts are enabled beforeprocinit(), an incoming device interrupt invokestrap(), which attempts to acquire proc locks, inspect the current CPU’s process pointer, or wake waiting processes. Dereferencing uninitialized process table locks or pointers causes an immediate kernel panic or deadlock.
Exercise 1.3.5: Monolithic vs Compartmentalized Boot-Time Device Manifest Parsers
Compare placing a complex device-tree or ACPI hardware manifest parser directly inside the early monolithic boot sequence versus executing it inside an isolated user-space or pre-kernel compartment.
HintExpandCollapse
Analyze the trade-offs between trusted computing base (TCB) size, crash recovery, and early boot resource availability.
Worked solutionExpandCollapse
Monolithic placement: The parser runs in early supervisor mode with direct access to physical memory. Benefit: minimal resource requirements (runs before scheduler or address spaces exist) and zero IPC overhead. Cost: complex C string and tree parsing runs with full kernel privilege; a memory corruption vulnerability compromises the entire kernel. Isolated compartment placement: The parser runs in a restricted address space with only read access to the raw manifest buffer and communicates parsed records via IPC. Benefit: parser crashes or exploits cannot corrupt kernel memory; faults can be logged and contained. Cost: requires deferring device parsing until memory management, scheduling, and IPC are functional, complicating bootstrap of boot-critical storage or interrupt controllers.
References & Further Reading
- MIT PDOS, xv6 rev5
kernel/entry.S,kernel/start.c,kernel/main.c,kernel/kernel.ld, andMakefile. - MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapters 1–2.
- RISC-V International, The RISC-V Instruction Set Manual, Volume II: Privileged Architecture, machine/supervisor privilege, delegation, PMP, and return-from-trap sections.
- Linux kernel documentation, RISC-V Kernel Boot Requirements and Constraints, for a production handoff comparison rather than an xv6 requirement.