Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Crossing the kernel boundary
Page 3 of 29

Boot and Kernel Organization

Trace a RISC-V machine from its firmware handoff to concurrent scheduler loops, deriving initialization order, publication, and kernel subsystem boundaries from explicit invariants.

Lesson briefCrossing the kernel boundary · 5 h 30 min · 4 outcomes

Required knowledge

  • RISC-V privilege modes, control and status registers, and calling convention
  • Linking, ELF sections, static storage, and C initialization
  • Page tables, interrupts, and acquire-release synchronization at a conceptual level

Learning outcomes

  • Reconstruct the xv6 rev5 boot path from QEMU's entry address through machine-mode setup, supervisor initialization, and per-hart scheduling.
  • Derive an initialization dependency graph and distinguish construction, publication, and per-hart activation.
  • Explain why a source-code module boundary is not necessarily a protection or fault-containment boundary.
  • Diagnose an early-boot failure from register, symbol, and initialization-order evidence rather than from boot folklore.

Assessment target

Given an unfamiliar multiprocessor boot trace and subsystem dependency graph, identify the violated precondition, prove a safe publication order, and redesign one module boundary with an explicit protection argument.

Scope boundary

  • UEFI services, ACPI, device-tree parsing, secure/measured boot, dynamic kernel modules, and platform-specific firmware are represented only by their handoff contracts.
  • Linker relocation, physical-memory discovery, NUMA bring-up, and production Linux initialization are not implemented.
  • Microkernel, hybrid-kernel, and exokernel designs are compared only where an address-space or authority boundary changes the failure analysis.

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.

HintExpand

A ready flag can have the correct value while the object it announces is not safely visible.

Worked solutionExpand

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.

StageProducer’s obligationKernel may assumeKernel must not assume
Reset/firmwareEstablish architecture-defined reset state and platform firmware behaviorOnly the documented platform contractA C stack, a page table, or discovered RAM unless promised
Loader/firmware handoffPlace the image and provide entry parametersEntry PC, image layout, register/CSR state explicitly specifiedUEFI, BIOS, or device tree on every platform
Assembly entryEstablish stack and minimal execution environmentLinker-defined symbols and handoff registersAllocator, interrupts, or global constructors are ready
Privilege setupConfigure delegation, protection, timer access, and return targetCSRs written by the boot codeSupervisor mode is active before mret
Global constructionInitialize shared allocators, tables, drivers, and the first processSingle bootstrap owner where the protocol guarantees itSecondary harts see writes before publication
Per-hart activationInstall hart-local translation, trap vector, and interrupt routingPublished global stateAnother 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 solutionExpand

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.

CutModePC / operationStack and translationEstablished fact
0MQEMU jumps to _entry at 0x80000000no xv6 stack; paging offimage placement matches kernel.ld
1M_entry reads mhartidselects one 4096-byte slice of stack0C calls cannot collide across harts
2Mcall startvalid aligned stack; paging offC machine-mode setup can run
3Mstart writes mstatus.MPP=S, mepc=main, satp=0same stackmret target and next privilege fixed
4Mdelegates traps, configures PMP, timer access, and tp=hartidsame stacksupervisor kernel receives intended events/resources
5Smret transfers to mainpaging still offC supervisor initialization begins

The stack formula is

sp=addr⁡(stack0)+(hartid+1)⋅4096.sp = \operatorname{addr}(stack0) + (hartid+1)\cdot4096.

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.

Code
start
:QEMU loads kernel at 0x80000000;
:each hart enters _entry in M-mode;
:select stack0 slice from mhartid;
:start() configures delegation, PMP, timer, tp;
:mret to main() in S-mode;
if (hart id is zero?) then (bootstrap)
:construct allocator and kernel page table;
:activate paging and trap vector on hart 0;
:initialize process, interrupt, file, and device state;
:create first user process;
:full fence, then volatile started = 1;
else (secondary)
:spin on volatile started, then full fence;
:activate paging and trap vector on this hart;
endif
:enter per-hart scheduler loop;
stop
QEMU loads kernel at0x80000000each hart enters _entry inM-modeselect stack0 slice from mhartidstart() configures delegation,PMP, timer, tpmret to main() in S-modehart id is zero?bootstrapsecondaryconstruct allocator and kernelpage tableactivate paging and trap vectoron hart 0initialize process, interrupt, file,and device statecreate first user processfull fence, then volatile started =1spin on volatile started, then fullfenceactivate paging and trap vectoron this hartenter per-hart scheduler loop

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 solutionExpand

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

0 / 4 answered

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.

1
Without a release fence on hart 0, preceding page-table stores may not be visible when hart 1 reads started.
2
Declaring started as volatile in C automatically injects hardware bus memory fences across all processor cores.
3
Hart 1 requires an acquire fence or data dependency to order its read of started before reading page tables.
4
Atomic read-modify-write instructions universally flush L1 CPU instruction and data caches to physical RAM.

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 solutionExpand

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.

Code
component "physical allocator" as PA
component "kernel page table" as PT
component "per-process kernel stacks" as KS
component "process table" as PR
component "trap vectors" as TV
component "interrupt controller" as IC
component "buffer cache" as BC
component "inode + file tables" as FS
component "disk driver" as DD
component "first process" as INIT
component "scheduler" as SCH

PA --> PT : supplies table pages
PA --> KS : supplies stack pages
PT --> KS : maps guarded stacks
KS --> PR : process slots name stacks
PR --> INIT : allocates process state
TV --> INIT : user return needs trap path
IC --> DD : routes completion interrupts
BC --> FS : caches filesystem blocks
DD --> FS : supplies persistent blocks
FS --> INIT : resolves / and /init
PR --> SCH : exposes RUNNABLE state
INIT --> SCH : creates runnable work

note right of SCH
An arrow means "must be usable before",
not "must live in another source file."
end note
physical allocatorkernel page tableper-process kernel stacksprocess tabletrap vectorsinterrupt controllerbuffer cacheinode + file tablesdisk driverfirst processschedulerAn arrow means "must be usablebefore",not "must live in another sourcefile."supplies table pagessupplies stack pagesmaps guarded stacksprocess slots namestacksallocates process stateuser return needs trappathroutes completioninterruptscaches filesystem blockssupplies persistentblocksresolves / and /initexposes RUNNABLEstatecreates runnable work

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 solutionExpand

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

  1. Hart 1 observes nonzero started, crosses rev5’s consumer-side full fence, safely observes the page table, installs translation and its trap vector, then calls scheduler().
  2. The scheduler scans proc[] while hart 0 is still initializing process locks and states.
  3. 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.
  4. 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 solutionExpand

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:

BoundaryEnforcement mechanismFailure contained?Typical cost
C module/APIlanguage and build conventionsnot against memory corruption in privileged Cordinary call
in-kernel compartmentmemory protection, language isolation, or control-flow enforcementdepends on mechanism and shared authoritychecked call / mapping change
user-space serviceseparate address space plus IPC authoritydirect memory faults usually contained; protocol faults may propagatetrap, 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 solutionExpand

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.

Section Exercises

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

Descriptionapplication

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.

HintExpand

Trace the memory layout when hart 5 writes to its computed stack pointer.

Worked solutionExpand

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

Verificationapplication

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.

HintExpand

Contrast compiler volatile semantics with hardware store-buffer visibility across CPU cores.

Worked solutionExpand

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

Descriptiontransfer

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).

HintExpand

Recall that machine mode owns all physical memory by default and traps trap to machine mode unless delegated.

Worked solutionExpand

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

Formalisationtransfer

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.

HintExpand

Map the prerequisite resources required by each subsystem constructor.

Worked solutionExpand

Strict initialization order:

  1. Console and print locks (enables diagnostic output).
  2. Physical page allocator kinit() (provides free physical frames).
  3. Kernel page table kvminit() and activation kvminithart() (enables MMU translation).
  4. Process table procinit() (allocates proc locks and kernel stacks).
  5. Trap vector trapinithart() (installs kernelvec into stvec).
  6. PLIC / timer interrupt controller plicinit() and plicinithart(). If device interrupts are enabled before procinit(), an incoming device interrupt invokes trap(), 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

Constructionsynthesis

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.

HintExpand

Analyze the trade-offs between trusted computing base (TCB) size, crash recovery, and early boot resource availability.

Worked solutionExpand

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

  1. MIT PDOS, xv6 rev5 kernel/entry.S, kernel/start.c, kernel/main.c, kernel/kernel.ld, and Makefile.
  2. MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapters 1–2.
  3. RISC-V International, The RISC-V Instruction Set Manual, Volume II: Privileged Architecture, machine/supervisor privilege, delegation, PMP, and return-from-trap sections.
  4. Linux kernel documentation, RISC-V Kernel Boot Requirements and Constraints, for a production handoff comparison rather than an xv6 requirement.