Sources and References

Primary textbooks — Liu, Jane W. S. Real-Time Systems. Prentice Hall, 2000. Buttazzo, Giorgio. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer, 4th ed., 2024. Arpaci-Dusseau, Remzi and Andrea. Operating Systems: Three Easy Pieces. University of Wisconsin, freely available at pages.cs.wisc.edu/~remzi/OSTEP/.

Supplementary texts — Tanenbaum, Andrew and Herbert Bos. Modern Operating Systems, 5th ed. Pearson, 2023. Hennessy, John and David Patterson. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann, 2017.

Hardware references — ARM. ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile (DDI 0487). ARM Holdings. ARM. Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64). Broadcom. BCM2711 ARM Peripherals. Microchip Technology. MCP2515 Stand-Alone CAN Controller with SPI Interface (DS20001801). Märklin. CAN-Protokoll Beschreibung CS2/CS3 Version 2.0.

Online resources — MIT CSAIL. xv6: a simple, Unix-like teaching operating system and 6.S081 Operating Systems Engineering course materials. CMU. 18-349 Introduction to Embedded Systems. UIUC. CS 423 Operating Systems Design. Liu, C. L. and James W. Layland. “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.” Journal of the ACM 20, no. 1 (1973): 46–61. Lehoczky, John, Lui Sha, and Y. Ding. “The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior.” Proceedings of the 10th IEEE Real-Time Systems Symposium, 1989.

Part I: Real-Time Systems Foundations

Chapter 1: What Real-Time Means

The phrase “real-time” is used casually to mean fast, but in the engineering literature it means something far more precise and far more demanding. A real-time system is a computing system whose correctness depends not only on the logical correctness of its outputs but on the time at which those outputs are produced. A system that computes the right answer too late has failed, even if the computation itself was flawless. This is the central axiom from which everything else in this course follows.

Understanding this definition requires carefully distinguishing between three qualities that are often conflated: speed, responsiveness, and timeliness. A fast system produces results quickly on average. A responsive system produces results quickly in the common case. A real-time system guarantees that results are produced within a specified deadline in all cases — including the worst case. The distinction matters enormously. A general-purpose web server that handles the median request in ten milliseconds but occasionally spends a second on garbage collection is fast and often responsive, but it is not real-time. A pacemaker that delivers a cardiac pulse within two milliseconds of the scheduled beat, every beat, with no exceptions, is a real-time system — even though it is not fast in the sense of performing complex computation.

Hard, Firm, Soft, and Near Real-Time

The literature recognizes a spectrum of timing requirements, and it is worth being precise about each.

A hard real-time system is one in which missing a deadline constitutes a system failure. The consequences of lateness are catastrophic and cannot be recovered from. The anti-lock braking system in a modern car must apply differential brake pressure within a fixed window when wheel slip is detected; if the computation is delayed by even a few milliseconds, the wheel locks and the driver loses directional control. A fly-by-wire flight control system must update its actuator commands faster than the aerodynamic time constants of the aircraft; a missed deadline can cause an aerodynamic instability from which the aircraft cannot recover. For hard real-time systems, timing guarantees must be proved, not estimated. Probabilistic arguments are insufficient.

A firm real-time system is one in which the value of a late result is zero, but missing a deadline does not cause catastrophic harm. A video conferencing codec that delivers a frame ten milliseconds too late is useless — the frame can be dropped — but the conversation continues. A financial trading system that fills an order after the market has moved may lose money but does not endanger lives. The distinction from soft real-time is subtle: in a firm system, late results are worthless; in a soft system, they are merely degraded in value.

A soft real-time system is one in which timeliness is a quality-of-service concern rather than a correctness requirement. Late results reduce quality but do not constitute a system failure. A music streaming service that occasionally buffers is annoying but functional. An interactive game that drops from 120 to 60 frames per second during an explosion is less pleasant but still playable. Most consumer software is soft real-time at best.

The phrase near real-time is sometimes used in industrial contexts to describe systems with latencies in the range of seconds to minutes, where “real-time” primarily indicates continuous processing rather than batch processing. This usage is too weak to be useful in an engineering discussion.

This course is primarily concerned with hard real-time systems, specifically the microkernel that drives physical hardware with deterministic timing requirements. The trains will behave incorrectly — collide, overshoot, stall — if the kernel does not respond to sensor events within bounded time. The stakes are not lives but the principle is the same: correctness requires timing guarantees, not timing hopes.

Why Timing Is Correctness

The insight that timing is part of correctness is counterintuitive to programmers trained on sequential algorithms, where correctness is purely a function of the relationship between input and output. It becomes obvious in the context of physical systems. Consider a train moving at 0.5 metres per second. At that speed, it traverses 5 centimetres in 100 milliseconds. If the kernel’s worst-case latency for processing a sensor event is 50 milliseconds, the train’s position uncertainty at the moment of response is 2.5 centimetres — a physically meaningful error. If the latency grows to 500 milliseconds, the uncertainty is 25 centimetres, which on a scale model track is the difference between successfully stopping before a bumper and embedding the locomotive in it.

The physical world is governed by differential equations, not by computational complexity. It does not pause while the kernel context-switches. The relationship between computation and the physical process it controls is mediated by time, and time is therefore a first-class correctness dimension.

This has a practical corollary. In a real-time system, it is not enough to know that something will eventually happen; you must know that it will happen by a specific moment. The kernel design choices made in this course — static priorities, no shared memory, bounded system call latency — are all engineering consequences of this requirement.

Real-Time vs. General-Purpose Operating Systems

A general-purpose operating system like Linux is optimized for average-case throughput. It uses techniques — address space layout randomization, transparent huge pages, dynamic frequency scaling, opportunistic preemption, the completely fair scheduler — that improve the common case at the potential expense of the worst case. A real-time OS makes the opposite trade: it accepts that average performance may be lower, but it guarantees that the worst case is bounded.

This affects nearly every design decision. Linux uses dynamic memory allocation extensively because it amortizes well across millions of requests. A hard real-time kernel avoids malloc entirely because the worst-case latency of a heap allocation — which may trigger compaction, or wait for a slow page fault — is unpredictable and potentially unbounded. Linux uses complex scheduler algorithms (CFS, EEVDF) because they are fair across thousands of threads. This kernel uses a simple static-priority FIFO scheduler because the assignment of worst-case response time is tractable. Linux permits priority inversion on shared resources because the common case is fast. This kernel uses Send/Receive/Reply message passing because it eliminates shared resources and with them the possibility of unbounded blocking.

None of these choices make the RT kernel “better” than Linux. They make it correct for a different optimization target. Understanding the target is understanding the course.

The Course: Build the Stack

CS 452’s answer to the challenge of real-time programming is radical: build the entire software stack from bare metal. You boot the Raspberry Pi 4 directly into your code, with no Linux underneath you, no libc above you, and no libraries in between. Your kernel allocates no memory at run time. Your scheduler runs in a deterministic number of instructions. Your I/O is handled by interrupt-driven servers that communicate through message passing. At the top of this stack sits a real-time application — a controller for a physical Märklin model railway — that must track train positions, compute stopping distances, reserve track sections, and coordinate multiple moving trains, all with the timing guarantees that physical hardware demands.

Building this system from scratch is the only way to develop genuine intuition about what real-time programming requires. Reading about context switching is not the same as writing the assembly that saves and restores every register. Knowing that priority inversion is a problem is not the same as watching a high-priority task starve because a lower-priority task is holding a resource it cannot release. The trains are not decoration; they are the oracle. A kernel that is logically correct but temporally imprecise will misbehave on the track in exactly the ways that timing theory predicts.

A Brief History of Real-Time Operating Systems

The field of real-time operating systems has a history interleaved with aerospace, military computing, and industrial automation. Understanding the historical arc clarifies why certain design decisions — like the RMS scheduler or the SRR communication model — emerged when and where they did.

The first real-time systems were not recognized as such. The SABRE airline reservation system (1960), jointly developed by IBM and American Airlines, processed seat-reservation requests in “real time” in the sense that a travel agent could confirm a booking in seconds rather than hours. It did not have hard deadlines in the engineering sense, but it established the idea that computers could interact with the physical world faster than humans.

The Apollo Guidance Computer (AGC, 1966) is a more direct ancestor. Designed by the MIT Instrumentation Laboratory, the AGC had to simultaneously control spacecraft attitude, process crew inputs, navigate by stellar sightings, and manage engine ignition — all on a 2 MHz clock with 4 KB of core RAM and 36 KB of ROM. Its operating system (developed by Hal Laning and Ed Copps) used a priority-based multitasking scheme with 8 priority levels and cooperative scheduling within a priority level. The famous AGC alarm “1202” during Apollo 11’s lunar descent indicated that the executive (the scheduler) was overloaded, with more tasks requesting time than could be serviced within their deadlines. The system correctly prioritized flight-critical tasks and allowed navigation-aid tasks to be dropped, landing safely. This is an early recorded instance of graceful degradation under overload — a concept the Liu/Layland framework would formalize seven years later.

The 1970s and 1980s saw the emergence of commercial RTOSs. iRMX (1976, Intel), designed for the Intel 8080 and 8086, provided task management, inter-task communication, and I/O handling for industrial control applications. It introduced many concepts that remain standard: task priority, semaphores for synchronization, and file systems for embedded storage. QNX (1980, Quantum Software Systems, now BlackBerry QNX) took a more radical approach: a microkernel with message-passing IPC, designed to run on the IBM PC. QNX’s message-passing design directly influenced the CS 452 kernel architecture — the Send/Receive/Reply model in CS 452 is essentially QNX’s MsgSend/MsgReceive/MsgReply API, adapted for a simpler kernel without virtual memory.

VxWorks (1987, Wind River Systems) became the dominant RTOS in aerospace and industrial applications through the 1990s. It supported POSIX threads (pthreads), a BSD networking stack, and a wide range of hardware. It was the RTOS on Mars Pathfinder (1997), the Cassini spacecraft, and many other missions. VxWorks’s task scheduler uses fixed priorities with optional round-robin at equal priorities, closely matching the CS 452 approach.

The academic community was simultaneously developing the theoretical foundations. Liu and Layland’s 1973 paper (Chapter 15) provided the schedulability analysis framework. Lehoczky, Sha, and Ding (1989) extended it to exact characterization and average-case analysis. Audsley, Burns, Richardson, and Wellings (1993) developed the response time analysis (the fixed-point recurrence of Chapter 15). Buttazzo’s textbook Hard Real-Time Computing Systems (first edition 1997) unified these results into a coherent body of theory that remains the standard graduate reference.

The Raspberry Pi — the hardware platform for CS 452’s current offering — represents an unusual step in real-time systems education: using a high-performance, multi-core, out-of-order processor as a bare-metal microcontroller. Historically, embedded real-time systems ran on simple in-order microcontrollers (PIC, AVR, ARM Cortex-M) where WCET analysis was tractable because the hardware had no caches, no branch prediction, and no out-of-order execution. The Cortex-A72 in the RPi 4 is far more complex. The pedagogical choice is deliberate: the hardware is representative of modern high-performance embedded systems (automotive ADAS, drone flight controllers, industrial robotics), where the performance budget demands modern processors but the timing requirements demand real-time guarantees. Learning to work with this tension is the deeper engineering lesson.

Timing Guarantees in Practice

The theoretical framework of hard real-time guarantees — prove that U ≤ n(2^(1/n)-1) and sleep soundly — often clashes with practical reality. Several caveats are worth noting early in the course:

WCET overestimation: conservative WCET analysis overestimates execution times to ensure correctness. A task measured to have a worst-case of 5 ms may typically run in 0.5 ms. This gap between WCET and average-case makes utilization bounds pessimistic. In practice, a system that is schedulable by analysis has substantial headroom.

Unbounded blocking: the Liu/Layland model assumes tasks are always ready at their period boundaries. In reality, tasks may block waiting for I/O, for a lock, or for an SRR reply. These blocking times must be added to the WCET for analysis purposes. In the message-passing kernel, blocking times are bounded by the server’s response time — which is itself analyzable if the server’s task set is analyzable.

Interrupt storms: a faulty peripheral that fires interrupts continuously can overwhelm the kernel’s interrupt handling capacity. Protection: the kernel should detect when interrupt service frequency exceeds a threshold and disable the offending interrupt. In CS 452, the MCP2515’s error-handling state machine (entering error-passive or bus-off modes) prevents a faulty CAN bus from flooding the kernel with interrupts.

Temporal isolation failures: in a system without memory protection (no MMU enforcing per-task address spaces), a bug in one task can corrupt another task’s memory, including its stack. The kernel cannot detect this without explicit stack canaries (Chapter 5). The lesson: correctness of the real-time schedule is only as good as correctness of the individual tasks.

Chapter 2: Polling, Cyclic Executives, and Their Limits

Before introducing tasks and preemption, it is instructive to take seriously the simplest possible approach to real-time control: the polling loop. Understanding where polling succeeds and where it fails motivates every design decision in the kernel that follows.

The Polling Loop

The polling loop — sometimes called the super-loop or scan loop — is the dominant paradigm in small embedded systems. Its structure is:

void main(void) {
    init();
    for (;;) {
        if (sensor_fired()) handle_sensor();
        if (key_pressed())  handle_key();
        if (clock_expired()) handle_clock();
        // ... check all conditions in sequence
    }
}

The loop runs continuously. Each iteration checks every condition and takes the associated action if the condition is true. The appeal is simplicity: there is no scheduler, no context switch, no synchronization, and no non-determinism beyond the hardware itself. The code is straightforward to read, trace, and debug.

For simple, slow systems with a single sensor and a single actuator, the polling loop is genuinely the right approach. An early thermostat — one sensor, one relay, a one-second control period — is perfectly served by a polling loop. The complexity of a task-based RTOS would be gratuitous overhead.

The difficulties emerge as the system’s requirements grow along three axes: the number of conditions to check, the frequency at which conditions arrive, and the duration of the actions that must be taken.

Time Analysis of the Polling Loop

The worst-case response latency of a polling loop is the time required to complete one full scan of all conditions, including the time to execute the longest action. If we have conditions \(C_1, C_2, \ldots, C_n\) with action durations \(d_1, d_2, \ldots, d_n\), the worst-case latency for condition \(C_k\) is:

In the worst case — when \(C_k\) fires immediately after the poll for \(C_k\) completed — the system must traverse the entire loop before checking \(C_k\) again. The worst-case response time is therefore bounded by the sum of all action durations.

This has an immediate and severe implication. Suppose you have a train position sensor that must be processed within 50 milliseconds, and a UART receive handler that takes 20 milliseconds, and a track switch control function that takes 10 milliseconds, and a user-interface update that takes 30 milliseconds. The worst-case latency for the sensor is \(20 + 10 + 30 = 60\) milliseconds — already in violation of the deadline.

The standard response to this problem within the polling paradigm is to break long actions into shorter segments. Instead of a 30-millisecond UI update, you compute one line of the update per loop iteration. This reduces per-iteration cost but dramatically complicates the code: each segment must save its own progress state across iterations, the logical flow of the computation is shredded across many calls, and the result looks like a hand-written coroutine with all the readability hazards that implies.

The Cyclic Executive

The cyclic executive is a structured refinement of the polling loop. Rather than checking conditions on every iteration, it divides time into fixed frames of length \(F\). Each frame is subdivided into slots, and each slot is assigned a fixed task. The major cycle — the least common multiple of all task periods — determines how many distinct frame patterns are needed.

Suppose we have:

• Task A with period 10 ms, execution time 3 ms
• Task B with period 20 ms, execution time 5 ms
• Task C with period 20 ms, execution time 4 ms

The major cycle is 20 ms. A valid frame arrangement might assign frames of 10 ms each:

• Frame 1: A (3 ms), B (5 ms), slack
• Frame 2: A (3 ms), C (4 ms), slack

The cyclic executive executes frame 1, then frame 2, then repeats. Timing is enforced by a hardware timer that fires at frame boundaries. If a task overruns its slot, the executive can detect this and take action (abort, skip, flag an error). If it finishes early, the remaining time is idle.

The cyclic executive has genuine advantages for hard real-time systems. Worst-case response times are statically known by construction. There is no scheduler at run time, which eliminates scheduling overhead and non-determinism. Temporal isolation between tasks is guaranteed at the frame boundary. Industrial avionics standards such as ARINC 653 mandate this approach for safety-critical software.

The limitations are equally genuine. The task set must be fixed at design time; dynamic task creation is impossible. Task periods must be harmonically related for the major cycle to remain tractable. Any interaction between tasks — a producer notifying a consumer, a resource shared between tasks — must be handled by careful frame alignment or explicit data copies, which is tedious and error-prone. A task that occasionally runs long — a WCET overrun — causes a ripple of deadline violations throughout the frame. And as the number of tasks grows, the frame table becomes difficult to construct and verify.

Most importantly, the cyclic executive offers no natural way to handle asynchronous events. When a train sensor fires at an arbitrary moment, the cyclic executive must either poll it every frame (introducing latency up to one frame period) or dedicate an interrupt to it — but an interrupt that executes arbitrary code during a critical frame immediately violates the strict timing properties that made the cyclic executive attractive in the first place.

The Case for Preemptive Task Scheduling

The polling loop and cyclic executive both fail gracefully only when the ratio between the fastest event rate and the slowest task period is small. When this ratio is large — when a hardware interrupt must be acknowledged in microseconds while a route-computation task takes milliseconds — the fixed-sequence approach runs out of headroom.

The fundamental problem is that both approaches conflate when to compute with what to compute. A train position update should run as soon as the sensor fires, regardless of which other computations are in progress. The natural description of this requirement is: there is a higher-priority activity that should preempt whatever is currently running when the sensor fires.

Preemptive multitasking separates these concerns. Each logically distinct activity becomes a task with its own priority, its own stack, and its own program counter. The kernel schedules the highest-priority ready task at all times. When a sensor interrupt fires, the kernel can immediately preempt the currently running task, run the sensor handler, and then return to the preempted task — all without requiring the preempted task to have been written in any special way. The task model provides clean logical isolation without sacrificing response time.

This is the architecture of the microkernel built in CS 452. The train control application is decomposed into tasks — a sensor notifier, a clock server, UART servers, a train supervisor, route engineers — each running at an appropriate priority and communicating through bounded message-passing operations. The kernel guarantees that the highest-priority ready task always runs, that message passing is bounded in duration, and that interrupt handling latency is bounded by the longest non-preemptible kernel operation. The trains are the test.

Assignment Zero: The Polling Loop in Practice

Assignment 0 of CS 452 asks students to build exactly a polling loop — a bare-metal program on the Raspberry Pi that, with no kernel, no tasks, and no interrupts, controls a train by repeatedly checking three inputs: the track sensor (via CAN), the real-time clock (via system timer), and the user’s keyboard (via UART). The assignment’s purpose is not merely to implement the polling loop — it is to make the student feel, viscerally, what the polling loop cannot do.

A typical polling loop for A0:

void main(void) {
    uart_init();
    spi_init();
    can_init();
    timer_init();

    for (;;) {
        // Check sensors
        if (can_rx_available()) {
            CanFrame frame;
            can_rx_read(&frame);
            if (is_sensor_event(&frame)) {
                handle_sensor(&frame);
            }
        }

        // Check clock
        if (timer_elapsed_ms() >= CLOCK_PERIOD_MS) {
            timer_reset();
            handle_clock();
        }

        // Check user input
        if (uart_rx_ready()) {
            char ch = uart_rx_read();
            handle_key(ch);
        }
    }
}

The student is required to implement conditional function calls — if a sensor fires, do something. The assignment is deliberately achievable with a polling loop because the single-train scenario has a small number of conditions and the actions are simple.

The payoff is in the failure modes. When the student tries to add a second train, the polling loop’s latency doubles (every additional condition adds to the scan time). When the student tries to implement accurate timing (send a speed command every 100 ms for velocity calibration), the polling loop’s timing drifts because each iteration takes a variable amount of time depending on which conditions are true. When the student tries to implement a “stop in 3 seconds” feature, the natural code is:

// Wrong: this blocks the entire polling loop for 3 seconds
timer_delay_ms(3000);
train_stop();

Using a blocking delay stops all other polling for 3 seconds. The sensor check, the keyboard check, everything halts. The correct version — accumulating elapsed time and checking against a target — is the embryo of the cyclic executive. And then the student realizes that with two trains, two timers, and two sensors, the “accumulate elapsed time” approach requires carefully interleaving all the checks and makes the code look like the hand-written coroutine mess described earlier.

At the end of A0, the student has seen the problem from the inside. The kernel they will spend the next three months building is the solution.

Comparison: RTOS vs. bare-metal super-loop

The real-time systems industry is divided between two camps: RTOS-based systems and bare-metal super-loop systems. Understanding when each is appropriate is part of the practical education.

Bare-metal super-loops dominate in small microcontrollers (8-bit AVR, PIC, simple Cortex-M0). The entire application fits in a few kilobytes of flash. There are no tasks, no context switches, no dynamic allocation. Everything is globally scoped. The code is often generated by a tool (STM32CubeMX, AVR Studio) that handles peripheral initialization. This approach is maintainable for simple applications — a temperature controller, a motor driver — but breaks down when the application has more than three or four independent concerns.

RTOS-based systems (FreeRTOS, Zephyr, RIOT-OS) are appropriate when the application has multiple concurrent concerns with different timing requirements. FreeRTOS in particular has become ubiquitous in Cortex-M applications: it provides tasks, semaphores, queues, and timers with a ~10 KB ROM footprint. The trade-off is additional complexity: task stacks must be allocated, stack sizes must be tuned, priority inversion must be managed, and deadlock must be avoided.

Microkernel systems (QNX, L4, CS 452’s kernel) push further: IPC is the only inter-task communication mechanism, the kernel is minimal, and all device drivers live in user space. This provides stronger isolation (a buggy device driver cannot corrupt the kernel) but requires more careful design of the service architecture.

The CS 452 kernel sits at the microkernel end of this spectrum. For a model railway controller, this is educationally appropriate even if a FreeRTOS-based system would be commercially simpler.

Part II: The Hardware Substrate

Chapter 3: ARMv8-A for Systems Programmers

The Raspberry Pi 4’s processor is the Broadcom BCM2711, which integrates four ARM Cortex-A72 cores. The Cortex-A72 implements the ARMv8.0-A instruction set architecture. Understanding this architecture at the level needed to write a kernel — not just to run programs on it — requires working through register files, exception levels, and the calling convention in some depth.

A Brief History of ARM

The first ARM processor (Acorn RISC Machine, later Advanced RISC Machine) was designed in 1983 by a small team at Acorn Computers. The original ARM1 had a 26-bit address space and a 16-entry register file, and it fit on a single chip that consumed less than 100 milliwatts. The key design insight was that a reduced, orthogonal instruction set with a fixed 32-bit instruction width would allow high clock rates and simple decode logic — valuable properties when transistor budgets were tight.

ARM Ltd., spun out in 1990, licensed the architecture rather than manufacturing chips. The model proved extraordinarily successful: by 2020, ARM cores were shipping at a rate exceeding 20 billion per year, appearing in smartphones, microcontrollers, servers, and automobiles. The ARMv8-A architecture, introduced in 2011 with the Cortex-A53 and A57, extended the ARM architecture to 64-bit addressing while maintaining backward compatibility with 32-bit AArch32 code.

The ARMv8-A label covers a wide family. The Cortex-A72 (as in the RPi 4) is a high-performance out-of-order core capable of around 30 billion operations per second from its 1.5 GHz clock, with 48 KB L1 instruction cache, 32 KB L1 data cache, and 1 MB L2 shared across four cores.

The Register File

In AArch64 (64-bit) execution state, the architectural register file provides:

• x0–x30: thirty-one 64-bit general-purpose registers. When accessed as w0–w30, they name the lower 32 bits; operations on wN zero-extend the upper 32 bits.
• xzr / wzr: a zero register. Reads as zero; writes are discarded. This eliminates a dedicated zero-generating instruction in most cases.
• SP (stack pointer): not a general register in AArch64. It must be 16-byte aligned at any instruction that requires an aligned stack (e.g., ldp/stp with [sp]). Each exception level has its own banked SP: SP_EL0, SP_EL1, SP_EL2, SP_EL3.
• PC (program counter): not directly readable or writable by general instructions. It is implicitly updated by branches and explicitly visible in certain system register contexts.
• PSTATE: a collection of condition flags and system control bits, not a single architectural register. The NZCV flags (negative, zero, carry, overflow) are set by arithmetic operations and tested by conditional instructions. The DAIF field (Debug, SError/System Error, IRQ, FIQ) masks the corresponding exception types.

The 128-bit SIMD and floating-point register file (v0–v31, also accessible as q, d, s, h, b for narrower views) is architecturally separate. Whether a task’s FP/SIMD state must be saved on context switch depends on whether the kernel uses FP instructions. In a bare-metal kernel, the conservative choice is to save the entire SIMD file or to disable FP access from EL0 and avoid it in the kernel entirely, since saving 32 × 16 bytes = 512 bytes per context switch is a noticeable overhead.

Exception Levels

ARMv8-A defines four exception levels (ELs), representing a privilege hierarchy. Higher exception levels have greater access to hardware resources and system registers.

The Raspberry Pi 4 boots at EL3 (firmware), drops to EL2 (for hypervisor init), and then to EL1 where the CS 452 kernel runs. User tasks run at EL0. The practical consequence is that on boot, your startup assembly must actively drop from whichever EL the bootloader left you in (typically EL2) down to EL1 before entering your C kernel.

Dropping from EL2 to EL1 requires:

1. Configuring HCR_EL2 (Hypervisor Configuration Register) to declare that EL1 uses AArch64 and that exceptions targeting EL1 are not trapped to EL2.
2. Preparing SPSR_EL2 with the desired PSTATE for EL1 (specifically: EL1h mode, DAIF bits masked).
3. Setting ELR_EL2 to the address of the EL1 entry point.
4. Executing eret, which atomically restores PSTATE from SPSR_EL2 and branches to ELR_EL2.

// Illustrative EL2→EL1 drop sequence
mrs     x0, CurrentEL          // read current EL (encoded in bits [3:2])
lsr     x0, x0, #2
cmp     x0, #2
bne     .not_el2               // already at EL1, skip

// Configure EL1 as AArch64
mov     x0, #(1 << 31)         // HCR_EL2.RW = 1: EL1 is AArch64
msr     HCR_EL2, x0

// Set up return PSTATE for EL1h (uses SP_EL1), DAIF all masked
mov     x0, #0x3C5             // DAIF=1111, EL1h (mode 0b0101)
msr     SPSR_EL2, x0

// Set return address to EL1 entry
adr     x0, el1_entry
msr     ELR_EL2, x0
isb                             // ensure all system register writes take effect
eret                            // drop to EL1

The isb (instruction synchronization barrier) before eret ensures that the processor has committed all preceding system register writes before executing the exception return. This is one of the places where ARMv8’s weak memory model becomes visible: system register writes are not instantaneously visible to the instruction pipeline unless a barrier forces synchronization.

The AAPCS64 Calling Convention

The Application Binary Interface (ABI) governs how compiled code from different translation units — or different source languages — can call each other. The ABI for AArch64 is specified in the ARM document Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64). Kernel writers must understand it for two reasons: the kernel is called from C and must return to C, and the context switch must save and restore exactly the registers that C code considers persistent.

The register assignment is:

Two calling-convention rules that matter particularly for kernel writers:

First, the stack pointer must be 16-byte aligned at every public function boundary. The stp instruction with [sp, #imm] addressing requires the stack pointer to be 16-byte aligned; violating this causes an alignment fault. Since each stack frame pushes an even number of 64-bit values or should pad to 16 bytes, this is easy to maintain but easy to forget.

Second, callee-saved registers must be preserved. When the kernel saves a task’s context, it must save x19–x28, x29 (FP), and x30 (LR) in addition to any argument and temporary registers that happen to be live. The correct approach is to save the entire general register file (x0–x30) plus the system registers ELR_EL1 and SPSR_EL1 that encode the user task’s return address and PSTATE.

Mixing C and Assembly

Most of the kernel is written in C for readability and maintainability. Assembly is used exactly where it must be: for operations that have no C equivalent. The primary examples are:

• System register access: mrs (move register from system register) and msr (move to system register) have no C syntax. You either write a short .S file or use GCC’s __asm__ intrinsic for isolated register reads.
• Memory barriers: dmb (data memory barrier), dsb (data synchronization barrier), and isb (instruction synchronization barrier) are assembly instructions. GCC provides __sync_synchronize() and the __atomic_* builtins for most portable use cases, but for kernel code that must precisely control barrier semantics, raw assembly is cleaner.
• Context switch: saving and restoring all 31 general-purpose registers, the stack pointer, and the two EL1 system registers requires assembly. There is no C idiom that can move arbitrary registers.
• Exception vector table: the entry points for the vector table must be placed at fixed offsets and aligned to 128-byte boundaries, which requires assembly .align directives and careful section placement.

GCC allows mixing C and assembly through the asm volatile ("instruction" : outputs : inputs : clobbers) syntax for short, isolated sequences. For the context switch, a separate .S file is more readable:

// In C: declare the context switch entry point
extern void kernel_entry(void);

// In .S: define kernel_entry
.global kernel_entry
.align 7
kernel_entry:
    // Save user task's registers, dispatch to C handler
    ...

The .align 7 ensures 128-byte alignment, required by the exception vector table format.

The ARM Memory Model

The ARMv8-A memory model is significantly more relaxed than the x86 TSO (Total Store Ordering) model that most systems programmers learn first. On x86, all stores become visible to all processors in program order — the only reordering allowed is that stores may become visible to the local CPU before they are globally visible (store buffer forwarding). On ARMv8, the memory model is closer to the PowerPC/SPARC RMO (Relaxed Memory Order): loads may be reordered with loads, stores may be reordered with stores, and loads may even overtake stores in some scenarios.

For bare-metal kernel development, the practical implications are:

Device register accesses must be ordered with barriers. A write to a device register (enabling an interrupt, loading a DMA descriptor, setting a GPIO pin) might be reordered by the store buffer or the memory subsystem relative to other instructions. A dsb sy ensures all preceding memory operations are globally visible before the barrier completes.

Cache coherency is automatic between CPU cores in the inner shareable domain (the four Cortex-A72 cores). You do not need barriers between cores for ordinary memory reads and writes — the hardware cache coherency protocol maintains a consistent view. Barriers are needed at synchronization points (like lock acquire/release) to enforce ordering guarantees.

System register writes require barriers to take effect in the instruction stream. Writing to VBAR_EL1, TTBR0_EL1, or SCTLR_EL1 does not take effect until after an ISB. The processor may have already fetched instructions past the write using the old register value; the ISB flushes the pipeline and forces a re-fetch.

The load-acquire / store-release idiom provides a lightweight barrier for mutual exclusion without a full DSB. ldar (load-acquire) prevents any load or store after the ldar from being reordered before it. stlr (store-release) prevents any load or store before the stlr from being reordered after it. These instructions enable efficient lock implementations on multiprocessor systems, though they are overkill for the single-core CS 452 scenario.

The Cortex-A72 Pipeline

Understanding the Cortex-A72 pipeline is useful for WCET analysis and for understanding why certain optimization techniques (loop unrolling, data prefetching) help.

The Cortex-A72 is a 3-wide out-of-order processor. Its pipeline stages are approximately:

1. Fetch: up to 16 instructions fetched per cycle from the 48 KB instruction cache.
2. Decode/Rename: up to 3 instructions decoded per cycle. Register renaming eliminates WAR and WAW hazards.
3. Dispatch: instructions dispatched to one of several reservation stations (integer ALU, load/store, branch, multiply, FP/SIMD).
4. Execute: instructions execute out of order as their source operands become available. The integer ALU can execute up to 3 ALU operations per cycle.
5. Commit: instructions retire in program order, committing their results and any memory effects.

Branch prediction: the Cortex-A72 has a multi-level branch predictor including a branch target buffer (BTB), a static predictor (predict backward-taken, forward-not-taken), and a return address stack (RAS). The RAS is particularly relevant for function calls: when a bl (branch and link) instruction is executed, the processor pushes the return address onto the RAS; when a ret (return, which is br x30) is executed, the processor pops from the RAS and speculatively fetches the return address before the x30 register has been resolved. This means that function call/return pairs are predicted correctly without pipeline stalls, provided the call depth does not exceed the RAS depth (~8 entries).

Misprediction penalty: approximately 15 cycles on the Cortex-A72. For a loop with 100 iterations, a single mispredicted loop-exit branch costs 15 cycles out of roughly 100+ loop-body cycles — significant but not dominant.

Load-use latency: an integer load from L1 cache has a 4-cycle latency. A sequence like:

ldr  x0, [x1]    // load from memory
add  x2, x0, #1  // immediate use of loaded value

will stall for 4 cycles between the load and the add. The out-of-order engine can sometimes hide this by executing other independent instructions during the load latency, but in register-pressure situations, the stall is unavoidable.

These pipeline details inform the timing model for the kernel’s hot paths. A context switch involves 32 stores (saving registers) followed by 32 loads (restoring the next task’s registers). At 1 store + 1 load per cycle (the L1 data cache can sustain this), the raw register save/restore takes 32 cycles. With instruction overhead, the full context switch path typically takes 100–300 cycles — 0.07–0.2 µs at 1.5 GHz.

Out-of-Order Execution and Real-Time Correctness

The Cortex-A72’s out-of-order execution engine creates a subtle challenge for real-time systems that most embedded programmers encounter for the first time on the RPi 4. On a simple in-order microcontroller (Cortex-M0, AVR, PIC), the execution time of a code sequence is essentially the sum of the cycle counts of each instruction — predictable, additive, and easy to bound. On the Cortex-A72, instructions are reordered dynamically by the hardware, executed when operands are ready rather than in program order. This makes cycle-exact timing analysis difficult and requires understanding which transformations the hardware may perform.

Write reordering is the most practically important case. When your code writes to two memory locations:

mmio_write(UART_TXD,  'X');   // write byte to UART transmit register
mmio_write(UART_CR,  0x01);   // enable UART transmitter

the processor may internally reorder these two writes if it determines they are to independent addresses. For regular DRAM, this is an innocuous performance optimization — the observable outcome is the same. For device registers (MMIO), where write order is architecturally significant (you cannot enable the transmitter before putting a byte in the transmit register), reordering is catastrophic. The solution is the DSB SY instruction, which drains the store buffer and ensures all preceding writes are globally visible before the barrier completes. Device register write sequences must always be separated by barriers when order matters.

Speculative loads create a second class of issues. The Cortex-A72 may speculatively execute a load before it has confirmed that the preceding branch will be taken. If the load addresses a device register (e.g., reading from UART_FR to check whether the TX FIFO is full), the speculative access may have side effects (some FIFO implementations clear the status bit on read). The ISB instruction prevents speculative execution of subsequent instructions until all preceding instructions have committed. For device register reads that have side effects, ISB before the read prevents the read from being speculated.

Reordering across the kernel/user boundary is a concern during context switching. The kernel’s exception entry handler saves the user task’s registers to the kernel stack. If the save is not completed before the kernel begins reading those values (for scheduling decisions), a race with the hardware’s write buffer could yield stale data. The ARMv8 exception entry mechanism automatically performs a context synchronization operation (equivalent to ISB) on exception entry, ensuring all user-mode writes are visible before the kernel begins execution — but the kernel’s own writes to the saved context frame must be completed with a DSB before the frame is read by the scheduler.

Cache coherency across cores: the Cortex-A72 is a quad-core processor. The CS 452 kernel runs on a single core (core 0), with the other three cores parked in a spin loop after boot. However, the boot ROM starts all four cores, and until the non-boot cores are explicitly parked, they may speculatively fetch and execute instructions from shared memory addresses. The boot stub at 0x80000 (the kernel entry point) must send secondary cores to a different address before the kernel’s global data structures are initialized, to prevent speculative writes from corrupt cores from corrupting the kernel. The boot assembly checks MPIDR_EL1 and branches secondaries to a separate parking loop before any kernel initialization runs.

WCET analysis on an OOO processor: the fundamental difficulty with out-of-order execution and WCET is that the execution time of a code sequence depends not just on the instructions but on the micro-architectural state — the cache contents, the branch predictor history, the reservation station occupancy — at the time of execution. This state cannot be fully known at analysis time. Static WCET tools (AbsInt aiT, OTAWA) address this by constructing abstract interpretations of the processor state: rather than tracking the exact state, they track a set of possible states that safely over-approximates all possible concrete states. The result is a WCET bound that is correct for all possible micro-architectural states.

For the CS 452 kernel, which does not use formal static analysis, the practical approach is to ensure the kernel’s critical path (the exception entry, scheduler, and exception exit) is cache-resident at all times and that its execution time is measured under realistic conditions (warm cache, normal interrupt rates). The measured maximum, inflated by 20–30% as a safety margin, serves as the effective WCET. This approach accepts the risk that the true worst case might be higher, but in practice the gap between measured and true WCET is small when the cache is always warm — which the kernel guarantees for its own code by virtue of being executed frequently.

Spectre and Meltdown: the Cortex-A72 is affected by the Spectre variant 1 (bounds-check bypass) and Meltdown vulnerabilities discovered in 2018. These arise from speculative execution leaking information through the cache timing channel. The CS 452 kernel, which runs in a single address space with no untrusted code, is not exposed to these attacks — there is no adversarial code to exploit the speculation. In production systems with untrusted user code, mitigations (KPTI, retpoline, microcode updates) are required. Understanding that these mitigations exist — and that they carry a 5–20% performance tax on systems call-intensive workloads — is part of the broader education about why secure systems are harder to build than correct-but-insecure ones.

ARMv8 Synchronization Primitives

For completeness, ARMv8 provides two exclusive memory access instructions for implementing mutexes and other atomic operations on multiprocessor systems:

• ldxr Xt, [Xn] (load exclusive register): reads the value at the address and tags the address as “exclusive access monitored.”
• stxr Ws, Xt, [Xn] (store exclusive register): writes Xt to the address and sets Ws to 0 if the exclusive access succeeded (no other core modified the address since the ldxr) or 1 if it failed.

The classic compare-and-swap or atomic increment loop:

.Lretry:
    ldxr   x1, [x0]        // exclusive load of *x0 into x1
    add    x1, x1, #1      // increment
    stxr   w2, x1, [x0]    // exclusive store; w2 = 0 if succeeded
    cbnz   w2, .Lretry     // retry if store was preempted

In the single-core CS 452 kernel, exclusive accesses always succeed (there is no other core to preempt the exclusive tag), so these instructions are equivalent to plain loads and stores. They become meaningful if the kernel is extended to multi-core operation.

Floating-Point, SIMD, and Why the Kernel Disables Them

The Cortex-A72 implements the ARMv8 SIMD and floating-point extension, providing 32 128-bit vector registers (v0–v31) alongside the integer register file. Each v register is accessible as q (128-bit), d (64-bit), s (32-bit), h (16-bit), or b (8-bit) depending on the instruction. The NEON instruction set provides parallel arithmetic on packed integers or floating-point values — for example, fadd v0.4s, v1.4s, v2.4s adds four pairs of single-precision floats in one instruction.

From a kernel engineering standpoint, this capability creates a serious problem: context switch cost. Every task that could potentially use FP or SIMD registers has architectural state in those registers that must be preserved across context switches. Saving and restoring the 32 × 16 = 512 bytes of SIMD state on every context switch costs 32 STP instructions (each stores a 128-bit pair), which at ~1 cycle each is roughly 32 extra cycles per switch. For a kernel that targets sub-200-cycle context switches, this is a 15–20% overhead tax even when no task uses FP at all.

The standard solution in embedded and real-time kernels is lazy FP state save — sometimes called FPU lazy stacking in ARM terminology. The kernel starts each task with the FP unit disabled (CPACR_EL1.FPEN = 0b00). If a task executes a FP instruction while the FP unit is disabled, the processor takes a trap (an EL1 sync exception with ESR_EL1.EC = 0b000111). The trap handler saves the FP state of the previous FP-using task, restores the FP state of the current task, re-enables FP, and retries the instruction. Tasks that never use FP incur zero FP-save overhead. Tasks that do use FP incur FP-save overhead only at the first FP instruction after a context switch, and only if the previous task also used FP.

The CS 452 kernel takes an even simpler approach: disable FP entirely for both kernel and user code using the compiler flag -mgeneral-regs-only. This flag instructs the compiler to not generate any FP or SIMD instructions, and to not assume that v0–v31 need to be preserved across function calls. The practical consequence is that all arithmetic — including velocity calculations, distance estimates, and stopping-distance interpolation — must use integer or fixed-point representations.

To understand why this is acceptable rather than onerous, consider that the Cortex-A72’s integer multiply-accumulate unit can compute a 64-bit mul x0, x1, x2 in a single instruction. Fixed-point arithmetic with a 16-bit fractional part (Q16.16 format) provides a resolution of ~0.000015 for a value up to 65535 — more than adequate for velocity in mm/s or distance in millimeters. The mechanics of fixed-point are covered in Chapter 17.

The CPTR_EL2 and CPACR_EL1 system registers control FP/SIMD access:

/* In kernel init: ensure CPACR_EL1.FPEN[21:20] = 0b00 (traps FP to EL1) */
static void fpu_disable(void) {
    uint64_t cpacr;
    asm volatile("mrs %0, CPACR_EL1" : "=r"(cpacr));
    cpacr &= ~(3UL << 20);  /* FPEN = 0b00 — trap FP/SIMD access */
    asm volatile("msr CPACR_EL1, %0" :: "r"(cpacr));
    asm volatile("isb");
}

With -mgeneral-regs-only, the compiler will never emit FP instructions, so this trap will never fire in a correctly compiled kernel or user program. If a user task links against a library (such as a floating-point sprintf implementation) that does use FP, the trap will fire and the trap handler can either kill the task with an error or implement lazy FP stacking. For CS 452, the policy is simpler: link only freestanding C code, and use fixed-point arithmetic throughout.

There is one subtle exception: the compiler is free to use FP registers as “scratch” for passing struct arguments or returning struct values in some ABI conventions. AAPCS64 uses v0–v7 for FP/SIMD function arguments and v0–v3 for FP/SIMD return values. With -mgeneral-regs-only, these conventions are suppressed and all struct passing goes through integer registers or stack slots. This is important to be aware of when reading assembly output with objdump -d: if you see fmov or ld1 instructions in a -mgeneral-regs-only build, something has gone wrong (likely a library function call without the flag, or inline assembly).

The AArch64 System Register Space

Beyond the general-purpose registers, ARMv8-A provides a large system register space accessed via MRS (move system register to general register) and MSR (move general register to system register). The CS 452 kernel uses the following system registers:

The S3_x_cy_cx_z encoding is the generic system register form: S<op0>_<op1>_<CRn>_<CRm>_<op2>. This encoding is required when the register has no mnemonic alias in older assembler versions. GCC and GNU as support the named forms (VBAR_EL1, ELR_EL1, etc.) for all commonly used system registers.

AArch64 Assembly Programming for Systems Software

Writing a kernel requires more assembly than most applications: the boot sequence, the exception vector table, the context switch hot path, and a handful of critical inline sequences. These are not places where C is expressive enough — they require direct control over the register file, the stack pointer, and processor state. This section catalogs the AArch64 assembly idioms that appear in kernel code.

Address loading: loading an address of a symbol into a register is a common operation with three options, each with different trade-offs.

/* Option 1: ADR — PC-relative, ±1 MB range */
adr     x0, my_symbol           /* x0 = address of my_symbol */

/* Option 2: ADRP + ADD — PC-relative, ±4 GB range, 4K-aligned intermediate */
adrp    x0, my_symbol           /* x0 = 4K-aligned page containing my_symbol */
add     x0, x0, :lo12:my_symbol /* x0 += offset within the 4K page */

/* Option 3: LDR pseudo-instruction — literal pool, full 64-bit range */
ldr     x0, =my_symbol          /* assembler creates a literal pool entry */

ADR is preferred for kernel symbols because it is compact (one instruction) and position-independent. The ADRP+ADD pair handles symbols beyond the ±1 MB ADR range — useful for large kernel images. The LDR =symbol form uses a literal pool, which requires the assembler to generate a constant table nearby and can cause cache miss penalties; use it only for absolute constants that cannot be expressed as PC-relative.

Unconditional branches and calls: the AArch64 branch family has five members with distinct semantics:

Note that ret is a hint to the branch predictor that this is a subroutine return (the processor predicts the return address from the return address stack). A plain br x30 would also work but would miss the predictor hint and incur an extra cycle of branch misprediction penalty.

Conditional branches: AArch64 uses a PSTATE flags word (NZCV) for condition codes. Conditional branches test the flags:

/* After a comparison instruction: */
cmp     x1, x2              /* Sets N, Z, C, V */
b.eq    .Lequal             /* Branch if Z=1 (x1 == x2) */
b.ne    .Lnotequal          /* Branch if Z=0 */
b.lt    .Lless              /* Branch if N≠V (x1 < x2, signed) */
b.lo    .Llower             /* Branch if C=0 (x1 < x2, unsigned) */

/* Compact branch-if-zero / branch-if-nonzero: */
cbz     x0, .Lzero          /* if x0 == 0, branch (no flags modified) */
cbnz    x0, .Lnonzero       /* if x0 != 0, branch */

CBZ and CBNZ are particularly useful in kernel loops where checking for a null pointer or an empty queue avoids an explicit comparison instruction:

ldr     x0, [x1]            /* Load queue head */
cbz     x0, .Lempty_queue   /* Queue empty? */

Stack management: the kernel manages two stack pointers: SP_EL1 for the kernel stack and SP_EL0 for the user stack. The stack pointer in AArch64 must be 16-byte aligned at all function entry points (per AAPCS64). The kernel prologue/epilogue pattern:

/* Save registers before a C function call that may modify x19-x28 */
stp     x19, x20, [sp, #-16]!   /* push pair with pre-decrement */
stp     x21, x22, [sp, #-16]!

/* ... do work ... */

ldp     x21, x22, [sp], #16     /* pop pair with post-increment */
ldp     x19, x20, [sp], #16
ret

The ! suffix on the store (pre-indexed addressing) atomically decrements SP before the store. The post-indexed load increments SP after. These are the preferred idioms because they maintain 16-byte alignment (two 8-byte registers = 16 bytes per pair) and are recognized by exception traceback tools.

Inline assembly in C: the kernel’s C code frequently needs to execute single assembly instructions — reading system registers, issuing barriers, or accessing hardware registers too small for a dedicated function call overhead. GCC extended assembly syntax:

/* Basic form: asm volatile("instruction" : outputs : inputs : clobbers); */

/* Read cycle counter */
static inline uint64_t pmccntr(void) {
    uint64_t val;
    asm volatile("mrs %0, PMCCNTR_EL0" : "=r"(val));
    return val;
}

/* Data memory barrier (full system) */
static inline void dmb_sy(void) {
    asm volatile("dmb sy" ::: "memory");
}

/* Write to a system register */
static inline void set_vbar_el1(uint64_t vbar) {
    asm volatile("msr VBAR_EL1, %0" :: "r"(vbar));
    asm volatile("isb");
}

The "=r"(val) output constraint says “write the result to any register and store it in val.” The "r"(vbar) input constraint says “load vbar from any register.” The "memory" clobber tells GCC that the inline assembly may read or write arbitrary memory, preventing the compiler from reordering memory operations across the barrier instruction.

Avoiding function call overhead for hot paths: in the kernel’s interrupt handler, every instruction counts. Some small operations are best done as macros that expand to inline assembly rather than function calls:

/* Read GICC IAR without a function call */
#define GICC_IAR_READ() ({ \
    uint32_t _r; \
    asm volatile("ldr %w0, [%1]" \
        : "=r"(_r) \
        : "r"((volatile uint32_t *)GICC_IAR_ADDR)); \
    _r; \
})

The __attribute__((always_inline)) annotation on a function achieves the same effect when the full function calling convention is needed.

Bit manipulation idioms: AArch64 provides several bit manipulation instructions that are often more efficient than a sequence of AND/OR/SHIFT:

/* Extract bits [7:4] of x0 into x1 */
ubfx    x1, x0, #4, #4      /* Unsigned Bitfield eXtract */

/* Insert bits [7:4] of x1 into x0, zero other bits */
bfi     x0, x1, #4, #4      /* Bit Field Insert */

/* Clear bits [7:4] of x0 */
bfxil   x0, xzr, #4, #4     /* or: and x0, x0, #~0xF0 */

/* Count leading zeros (for log2, priority encoding): */
clz     x1, x0              /* x1 = number of leading zeros in x0 */

For a simple O(1) scheduler that must find the highest non-empty priority queue, CLZ is ideal: maintain a 32-bit bitmask ready_mask where bit n is set if the queue at priority n is non-empty. CLZ(ready_mask) gives the number of leading zeros, which is 31 - highest_set_bit. Then highest_set_bit = 31 - CLZ(ready_mask):

static inline int scheduler_find_highest_priority(uint32_t ready_mask) {
    int lz;
    asm("clz %w0, %w1" : "=r"(lz) : "r"(ready_mask));
    return 31 - lz;   /* bit 31 = priority 31 = highest */
}

This is O(1) regardless of the number of priority levels — a direct hardware implementation of the scheduler’s core operation.

GAS Assembler directives used in kernel code:

The .type and .size directives are optional but improve the quality of DWARF debug information and objdump output. Adding them to the exception vector table entries makes stack traces during kernel faults significantly more readable.

Stack Frames, Frame Pointers, and Backtrace

A stack frame is the region of the stack allocated for one function invocation. It holds the function’s local variables, saved registers, and (in standard calling conventions) the caller’s frame pointer and return address. Understanding the stack frame layout is essential for two debugging techniques that are invaluable in a bare-metal kernel: manual stack traces (walking the frame chain to reconstruct the call sequence that led to a fault) and stack sizing (measuring worst-case stack usage before deployment).

The AAPCS64 calling convention defines the standard frame record as a pair of 64-bit values stored at the bottom of the current frame:

• [fp + 0]: the previous frame pointer (the caller’s x29 value)
• [fp + 8]: the link register value at function entry (the return address)

A well-behaved function that may be called from code needing backtraces should save x29 and x30 at its entry, then set x29 to point to the saved pair:

/* Entry sequence for a frame-pointer-compliant function */
stp     x29, x30, [sp, #-16]!  /* push (fp, lr) pair, pre-decrement sp */
mov     x29, sp                 /* fp now points to the frame record */

/* ... function body ... */

ldp     x29, x30, [sp], #16    /* pop (fp, lr) pair, post-increment sp */
ret

The linked chain of frame records forms a frame chain:

[sp]  → [frame record for current function: (caller_fp, return_addr)]
[fp]  → [frame record for caller: (caller's_caller_fp, caller's_return_addr)]
[fp]  → [frame record for caller's caller: ...]
        ...
[0]   → (null, entry_point)   (bottom of stack, x29 = 0 at the entry point)

To produce a backtrace manually (in a kernel fault handler, without GDB):

void print_backtrace(void) {
    uint64_t *fp;
    asm volatile("mov %0, x29" : "=r"(fp));

    uart0_puts("Backtrace:\n");
    for (int depth = 0; depth < 16 && fp != NULL; depth++) {
        uint64_t prev_fp  = fp[0];
        uint64_t ret_addr = fp[1];
        uart0_printf("  [%d] 0x%016llx\n", depth, ret_addr);
        fp = (uint64_t *)prev_fp;
    }
}

print_backtrace() walks the frame chain from the current frame upward, printing each return address. The return addresses can then be resolved to function names offline using aarch64-elf-addr2line -e kernel8.elf <address>.

When frame pointers are not present: GCC by default may elide the frame pointer when -O2 is used and the compiler can track stack depth through other means. In a kernel, this optimization is counterproductive: faults are rare but must be debugged quickly, and a missing frame pointer makes the backtrace impossible. The compiler flag -fno-omit-frame-pointer forces frame-pointer-compliant code generation:

CFLAGS += -fno-omit-frame-pointer

This is already included in the recommended Makefile from Chapter 5. The performance cost is minor: one extra register allocation (x29 is tied up as the frame pointer) and two extra instructions at function entry and exit. For kernel code, which typically has much lower function call overhead than application code, this cost is negligible.

Stack usage profiling with -fstack-usage: GCC’s -fstack-usage flag generates a .su file alongside each .o file, recording the worst-case stack depth of each function in bytes:

task.c:scheduler_next   32       static
message.c:do_send       96       static
exception.c:handle_irq  272      dynamic,bounded

A static entry means the function uses a fixed-size stack frame deterministically. A dynamic,bounded entry means the function has variable-length array allocations or uses alloca, but the compiler can determine a bound. A dynamic entry (without “bounded”) means the stack depth is unbounded — a red flag in a real-time kernel.

The .su files can be post-processed with a script that walks the call graph and computes the maximum stack depth from any entry point:

# Pseudo-code: compute worst-case stack depth for each function
def max_depth(fn, call_graph, su_table, visited):
    if fn in visited: return su_table[fn]  # cycle: use local estimate
    visited.add(fn)
    local = su_table.get(fn, 0)
    callees = call_graph.get(fn, [])
    child_max = max((max_depth(c, call_graph, su_table, visited) for c in callees), default=0)
    return local + child_max

This analysis, combined with the task stack size from Chapter 5 (STACK_SIZE = 64 KB), gives the kernel writer confidence that no task will overflow its stack under worst-case conditions. Typical stack usage for a CS 452 train control task is 2–4 KB; the 64 KB budget leaves ample headroom.

The stack frame in the context switch: the kernel’s context switch saves 34 registers (x0–x30, SP_EL0, ELR_EL1, SPSR_EL1) as a contiguous frame on the kernel stack. This saved frame is itself a valid frame record for GDB’s backtrace purposes — if the kernel is interrupted while in the exception handler, GDB can unwind through the saved frame into the user task’s call stack. The prerequisite is that the exception vector table entries are decorated with .type %function and the frame record (x29, x30) is pushed first, before the rest of the context save:

/* Exception entry: must look like a function prologue for GDB */
.type exception_entry, %function
exception_entry:
    stp     x29, x30, [sp, #-272]!  /* save fp + lr first (frame record) */
    mov     x29, sp                  /* set fp to frame record */
    stp     x0,  x1,  [sp, #16]    /* then save x0..x28 */
    stp     x2,  x3,  [sp, #32]
    /* ... */

This careful framing means that from GDB’s perspective, exception_entry looks like a regular function call, and unwinding through it into the interrupted task’s stack frame is possible. Without this setup, GDB’s backtrace stops at the exception boundary.

Canary checking via stack high-water mark: in addition to the byte canary at the bottom of the stack, a more precise diagnosis of stack usage uses a high-water mark pattern: fill the entire task stack with a known value (e.g., 0xDEADBEEF) at initialization, and then scan from the bottom upward to find the first non-canary word after a task run:

#define STACK_FILL 0xDEADBEEFUL

void task_stack_init(uint32_t *stack, size_t size) {
    for (size_t i = 0; i < size / 4; i++)
        stack[i] = STACK_FILL;
}

size_t task_stack_used(uint32_t *stack, size_t size) {
    size_t used = 0;
    for (size_t i = 0; i < size / 4; i++) {
        if (stack[i] != STACK_FILL) {
            used = (size / 4 - i) * 4;
            break;
        }
    }
    return used;
}

After running the system through its worst-case workload, task_stack_used() reports the maximum stack depth for each task. This is the empirical equivalent of the static -fstack-usage analysis — less rigorous (it samples actual execution, not all possible paths) but directly applicable to the specific workload.

Chapter 4: Memory and Devices on the BCM2711

The BCM2711 is not a general-purpose microprocessor; it is a system-on-chip (SoC) that integrates a four-core Cortex-A72 cluster with a GPU, a DMA engine, USB controllers, PCIe, and a rich set of peripheral interfaces — all on a single die. Understanding how these peripherals are visible to the ARM cores is prerequisite to writing any bare-metal device driver.

The Memory Map

ARM processors access memory and memory-mapped device registers through a unified address space. There is no separate I/O port space (as on x86); a GPIO control register and a DRAM cell are distinguished only by their address and the memory attributes the MMU assigns to that range.

On the RPi 4, the physical address space is organized as follows:

The BCM2711 datasheet documents peripheral registers using bus addresses in the range 0x7E000000–0x7EFFFFFF. These bus addresses correspond to physical addresses starting at 0xFE000000: subtract 0x7E000000 and add 0xFE000000. For example, the system timer control/status register is documented at bus address 0x7E003000; the physical address for CPU access is 0xFE003000. This discrepancy exists because the bus address space is also visible to the VideoCore GPU and DMA engine, which use their own address translation.

The kernel loads at physical address 0x80000, which is where the RPi 4 firmware drops the core after processing kernel8.img. From that point, the startup code configures the MMU with an identity mapping (physical address = virtual address) over the RAM range and device range, with appropriate memory type attributes: cacheable normal memory for RAM, device memory (uncacheable, strongly-ordered) for peripheral registers.

Volatile and Memory Ordering

The distinction between normal memory and device memory is not academic. Consider a UART transmit FIFO: writing to the FIFO register sends a byte over the serial line; reading a status register tells you whether the FIFO is full. These registers have side effects that depend on the exact sequence and number of accesses. A compiler that reorders or coalesces memory accesses for optimization — as GCC routinely does for normal memory — would break device driver code.

The C keyword volatile tells the compiler to treat every access to the annotated variable as an observable side effect that must not be reordered, eliminated, or coalesced. The standard idiom for MMIO in C is:

#define MMIO_BASE 0xFE000000UL

static inline void mmio_write(uint32_t reg, uint32_t val) {
    *(volatile uint32_t *)(MMIO_BASE + reg) = val;
}

static inline uint32_t mmio_read(uint32_t reg) {
    return *(volatile uint32_t *)(MMIO_BASE + reg);
}

The volatile qualifier prevents the compiler from moving the access, but it does not prevent the processor’s memory system from reordering it. The ARM memory model — like most modern out-of-order processors — allows stores to complete in an order different from program order, and allows loads to observe values from the store buffer before they are visible to other observers. For device registers, this reordering must be suppressed with memory barriers.

A data synchronization barrier (dsb sy) ensures that all memory accesses before the barrier complete before any memory access after the barrier begins. For device accesses, dsb is typically the right choice. An instruction synchronization barrier (isb) flushes the instruction pipeline, ensuring that subsequent instructions are fetched after any context changes (such as system register writes) take effect.

In practice, most simple device accesses in a single-core environment are not visibly affected by hardware reordering because the core’s pipeline is typically coherent with itself. However, the barriers become essential at two points: when enabling interrupts (where the GIC enable must be visible before the first interrupt fires), and when the DMA engine or other bus masters are involved.

The System Timer

The BCM2711 system timer (at physical base 0xFE003000) is a 64-bit free-running counter clocked at 1 MHz. Its key registers:

The counter increments once per microsecond regardless of CPU clock speed or power state, making it a reliable time reference. Comparing registers C0 and C2 are used by the VideoCore GPU; the kernel must use C1 and C3. When the free-running counter’s lower 32 bits match Cn, the corresponding channel fires an interrupt (signalled through the GIC).

The safe idiom for reading the 64-bit counter on a 32-bit-at-a-time bus:

uint64_t timer_read(void) {
    uint32_t hi, lo, hi2;
    do {
        hi  = mmio_read(TIMER_CHI);
        lo  = mmio_read(TIMER_CLO);
        hi2 = mmio_read(TIMER_CHI);
    } while (hi != hi2);           // repeat if the upper word rolled over
    return ((uint64_t)hi << 32) | lo;
}

To schedule a timer interrupt N microseconds in the future:

void timer_set(uint32_t channel, uint32_t delay_us) {
    uint32_t target = mmio_read(TIMER_CLO) + delay_us;
    mmio_write(TIMER_C0 + channel * 4, target);
}

Clearing the interrupt requires writing a 1 to the corresponding bit of the CS register (the BCM2711 timer uses write-1-to-clear semantics for its status flags).

GPIO

The BCM2711’s GPIO block (physical base 0xFE200000) controls 58 general-purpose pins. Each pin can be configured as input, output, or one of several alternate functions (UART, SPI, I2C, PWM, etc.). The function for each pin is set by the GPFSEL registers (one register per ten pins, three bits per pin). Output is set and cleared through GPSET0/1 and GPCLR0/1 (32 pins per register); input is read through GPLEV0/1.

GPIO pins can also be configured to generate edge-detect events, which propagate to interrupt status registers and eventually to the GIC. The MCP2515 CAN controller asserts its INT pin low when a message has been received or a transmit error has occurred; this is connected to GPIO pin 17, which is configured as a falling-edge-detect input. The resulting event appears at GIC interrupt ID 145.

Identity Mapping and Device Memory Types

The ARMv8-A MMU allows the kernel to assign memory attributes to address ranges. There are two critical attribute classes: normal memory (SDRAM, cacheable, weakly-ordered) and device memory (MMIO, uncacheable, strongly-ordered). The kernel’s startup code configures a minimal identity-mapped page table that assigns:

• 0x00000000–0x3FFFFFFF: normal memory, inner/outer write-back cacheable
• 0xFE000000–0xFFFFFFFF: device-nGnRnE memory (non-gathering, non-reordering, no early-write-acknowledgement)

The nGnRnE designation is the strongest device ordering — it prohibits the processor from merging consecutive writes to the same address, from reordering accesses within the device region, and from speculating ahead on early-write-acknowledge. This is the appropriate type for peripheral registers that have side effects.

ARMv8 Page Table Format

A complete understanding of the ARMv8-A MMU is not strictly required for CS 452 (the kernel uses a minimally-configured identity map), but knowing how it works demystifies the boot sequence and is essential for anyone who later implements memory protection.

ARMv8-A uses a four-level page table hierarchy (levels 0–3) for the full 64-bit virtual address space, though most practical implementations use only 2 or 3 levels. For a 4 KB page granule (the most common configuration), each level of the hierarchy has 512 entries (9 bits of index), and the full 48-bit virtual address is decomposed as:

Each page table entry (PTE) is 8 bytes (64-bit). Bits [1:0] determine the descriptor type:

• 0b01: Block descriptor (1 GB at level 1, 2 MB at level 2)
• 0b11: Table descriptor at levels 0–2 (points to next-level table); Page descriptor at level 3

The memory attributes (normal vs. device, cacheable vs. uncacheable) are encoded in bits [4:2] of the PTE, which index into the MAIR_EL1 register (Memory Attribute Indirection Register). MAIR_EL1 holds 8 attribute types (one per byte); the PTE’s attribute index selects one. A typical MAIR_EL1 setup:

• Index 0: Device-nGnRnE (0x00) — for peripheral registers
• Index 1: Normal memory, inner/outer write-back, read-allocate, write-allocate (0xFF)

For the minimal CS 452 identity map, only two blocks are needed: a level 1 block descriptor at 0x00000000 for normal RAM (attribute index 1) and a level 1 block descriptor at 0xFE000000 for device registers (attribute index 0). Two PTEs in a single page cover the entire address space the kernel uses.

The walk through a virtual address lookup:

1. TTBR0_EL1 holds the physical address of the level 0 table.
2. The processor extracts VA[47:39] as the level 0 index (0 for all addresses in a 4 GB system with 4 KB pages and a 2-level map).
3. The level 0 PTE points to the level 1 table.
4. VA[38:30] indexes the level 1 table. Entry 0 is the 1 GB RAM block; entry 2 (for 0x80000000) is not used; we use a level 1 block at 0xFE000000.

Wait — 0xFE000000 is within the 4th GB (0xC0000000–0xFFFFFFFF), index 3 in the level 1 table. So the level 1 table has entries for index 0 (RAM), index 3 (peripherals), and the rest are invalid.

The simplicity of this setup is its virtue. The boot-time page table setup for a CS 452 kernel takes fewer than 30 assembly instructions.

The PL011 UART: Register-Level Programming

The PL011 is the BCM2711’s primary full-featured UART, used for terminal communication with the development workstation. Understanding it at the register level illustrates the general pattern of peripheral programming on the BCM2711.

The PL011 base address is 0xFE201000. Key registers (at their offsets from base):

Baud-rate configuration: the PL011 clocks from UARTCLK, which on the RPi 4 is derived from the system PLL at 48 MHz (or 3 MHz in some configurations). The baud-rate divisor is:

For 115200 baud at 48 MHz: BAUDDIV = 48,000,000 / (16 × 115,200) = 26.04167. The integer part goes in IBRD (= 26); the fractional part is encoded as FBRD = round(0.04167 × 64) = 3.

LCR_H configuration for 8N1 (8 data bits, no parity, 1 stop bit, FIFO enabled):

#define UART0_BASE   0xFE201000UL
#define UART0_DR    (UART0_BASE + 0x000)
#define UART0_FR    (UART0_BASE + 0x018)
#define UART0_IBRD  (UART0_BASE + 0x024)
#define UART0_FBRD  (UART0_BASE + 0x028)
#define UART0_LCRH  (UART0_BASE + 0x02C)
#define UART0_CR    (UART0_BASE + 0x030)
#define UART0_IFLS  (UART0_BASE + 0x034)
#define UART0_IMSC  (UART0_BASE + 0x038)
#define UART0_ICR   (UART0_BASE + 0x044)

#define FR_TXFF  (1 << 5)   // transmit FIFO full
#define FR_RXFE  (1 << 4)   // receive FIFO empty
#define FR_BUSY  (1 << 3)   // UART transmitter busy

void uart0_init(void) {
    /* Disable UART before reconfiguring */
    mmio_write(UART0_CR, 0);

    /* Wait for any ongoing transmission to complete */
    while (mmio_read(UART0_FR) & FR_BUSY) {}

    /* Configure GPIO 14 (TXD), 15 (RXD) as UART0 alt function 0 */
    uint32_t sel = mmio_read(0xFE200000);  // GPFSEL1
    sel &= ~((7 << 12) | (7 << 15));       // clear GPIO 14, 15 bits
    sel |=   (4 << 12) | (4 << 15);        // set alt0
    mmio_write(0xFE200004, sel);

    /* Set baud rate: 115200 at 48 MHz UARTCLK */
    mmio_write(UART0_IBRD, 26);
    mmio_write(UART0_FBRD, 3);

    /* 8 data bits, 1 stop bit, no parity, FIFO enabled */
    mmio_write(UART0_LCRH, (3 << 5) | (1 << 4));   /* WLEN=11 (8 bits), FEN=1 */

    /* FIFO interrupt thresholds: TX at 1/4 full, RX at 1/8 full */
    mmio_write(UART0_IFLS, (0b001 << 3) | 0b000);  /* TXIFLSEL=1/4, RXIFLSEL=1/8 */

    /* Clear all pending interrupts */
    mmio_write(UART0_ICR, 0x7FF);

    /* Enable RX interrupt, TX interrupt; disable others */
    mmio_write(UART0_IMSC, (1 << 4) | (1 << 5));   /* RXIM=1, TXIM=1 */

    /* Enable UART: TX enable, RX enable, UART enable */
    mmio_write(UART0_CR, (1 << 9) | (1 << 8) | (1 << 0));
}

Polling transmit (for use before the interrupt-driven server is running):

void uart0_putc_poll(char c) {
    while (mmio_read(UART0_FR) & FR_TXFF) {}   // wait until FIFO not full
    mmio_write(UART0_DR, (uint32_t)c);
}

Interrupt-driven receive: when the RX FIFO reaches the 1/8-full threshold (4 bytes, since the PL011 has a 32-byte deep FIFO on the BCM2711), the RXIM interrupt fires. The interrupt handler drains the FIFO:

void uart0_rx_irq_handler(void) {
    while (!(mmio_read(UART0_FR) & FR_RXFE)) {
        uint32_t dr = mmio_read(UART0_DR);
        if (dr & (1 << 11)) { /* overrun error */
            mmio_write(UART0_ICR, 1 << 4);  /* clear OEIC */
            continue;
        }
        if (dr & (1 << 10)) { /* break */ continue; }
        if (dr & (1 << 9))  { /* parity error */ continue; }
        if (dr & (1 << 8))  { /* framing error */ continue; }
        char c = dr & 0xFF;
        rx_ring_push(c);    /* push to software ring buffer */
    }
    mmio_write(UART0_ICR, 1 << 4);  /* clear RXIC */
}

The data register’s upper bits carry error flags. Checking them prevents corrupted bytes from entering the receive buffer. The OEIC, RXIC, TXIC bits in ICR (Interrupt Clear Register) are write-1-to-clear.

Flow control (CTS/RTS): the PL011 supports hardware flow control. When CTSEn (bit 15 of CR) is set, the UART checks the CTS pin before transmitting; when RTSEn (bit 14) is set, the RTS pin is automatically asserted when the receive FIFO reaches a threshold. For the CS 452 terminal, flow control is typically not needed because the terminal server’s software buffering handles rate mismatches. For the UART connection to the CS3 (if used), flow control may be required if the CS3 does not have internal buffering.

The SPI0 Peripheral: Register-Level Programming

The SPI0 peripheral (base 0xFE204000) connects the RPi 4 to the MCP2515 CAN controller. Understanding SPI at the register level clarifies how each CAN frame transmission and reception happens.

The SPI0 uses a FIFO-based interface. Key registers:

A single SPI transaction with the MCP2515 requires:

1. Assert CS by writing CS register with CS[1:0] = chip select, TA = 1 (transfer active), CLEAR = 1 (clear FIFOs).
2. Write command bytes to FIFO.
3. Write dummy bytes to FIFO for bytes to be received (SPI is full-duplex; sending dummy 0x00 advances the clock for reception).
4. Poll the DONE bit (CS[16]) until the transaction completes.
5. Read received bytes from FIFO.
6. Deassert CS by clearing TA.

For the MCP2515’s 10 MHz maximum clock and the BCM2711’s core clock at 200 MHz, CLK = 200 MHz / 10 MHz = 20.

#define SPI0_BASE  0xFE204000UL
#define SPI0_CS    (SPI0_BASE + 0x000)
#define SPI0_FIFO  (SPI0_BASE + 0x004)
#define SPI0_CLK   (SPI0_BASE + 0x008)

void spi0_init(void) {
    mmio_write(SPI0_CLK, 20);           // 200 MHz / 20 = 10 MHz
    mmio_write(SPI0_CS, 0);             // CPOL=0, CPHA=0 (MCP2515 mode 0)
}

/* Transfer one byte: transmit tx, return received byte */
uint8_t spi0_transfer_byte(uint8_t tx) {
    /* Clear FIFOs, set TA=1 */
    mmio_write(SPI0_CS, (1 << 7) | (1 << 4) | 1);  /* TA, CLEAR, CS=1 */
    /* Wait for TX FIFO space */
    while (!(mmio_read(SPI0_CS) & (1 << 18))) {}     /* TXD bit */
    mmio_write(SPI0_FIFO, tx);
    /* Wait for transfer to complete */
    while (!(mmio_read(SPI0_CS) & (1 << 16))) {}     /* DONE bit */
    /* Read received byte */
    uint8_t rx = mmio_read(SPI0_FIFO) & 0xFF;
    /* Deassert CS (TA=0) */
    mmio_write(SPI0_CS, 0);
    return rx;
}

A multi-byte SPI transaction (e.g., writing to MCP2515 TXBUF0 with 13 bytes) is more efficient with FIFO streaming:

void spi0_transfer(const uint8_t *tx, uint8_t *rx, int len) {
    /* Clear FIFOs, set TA=1, CS=1 */
    mmio_write(SPI0_CS, (1 << 7) | (1 << 4) | 1);

    int tx_sent = 0, rx_got = 0;
    while (rx_got < len) {
        /* Fill TX FIFO as much as possible */
        while (tx_sent < len && (mmio_read(SPI0_CS) & (1 << 18))) {
            mmio_write(SPI0_FIFO, tx[tx_sent++]);
        }
        /* Drain RX FIFO */
        while (mmio_read(SPI0_CS) & (1 << 17)) {  /* RXD bit */
            rx[rx_got++] = mmio_read(SPI0_FIFO);
        }
    }

    /* Wait for completion, deassert CS */
    while (!(mmio_read(SPI0_CS) & (1 << 16))) {}
    mmio_write(SPI0_CS, 0);
}

This streaming approach fills the TX FIFO and drains the RX FIFO in parallel, maximizing throughput. For the 13-byte MCP2515 read (1 command + 1 address + 11 data bytes), the streaming approach reduces wait time compared to byte-at-a-time transfer.

GPIO Deep Dive

GPIO (General Purpose Input/Output) on the BCM2711 is more complex than the name suggests. Each of the 58 pins can be configured for up to 6 alternate functions (GPIO, UART, SPI, I2C, PCM, etc.). The function select registers GPFSEL0–GPFSEL5 control 10 pins each (3 bits per pin, 30 bits per register):

For SPI0 (used to communicate with the MCP2515): GPIO 7 = CE1 (SPI chip select 1, alt function 0), GPIO 8 = CE0 (alt function 0), GPIO 9 = MISO (alt function 0), GPIO 10 = MOSI (alt function 0), GPIO 11 = SCLK (alt function 0). For UART0 (PL011): GPIO 14 = TXD0 (alt function 0), GPIO 15 = RXD0 (alt function 0). For GPIO 17 (MCP2515 INT): configure as input (function 000).

Pull-up/pull-down resistors are controlled by GPPUD (pull-up/pull-down enable) and GPPUDCLK0/1 (which pins the setting applies to), using a three-step sequence: write GPPUD, wait 150 cycles, write GPPUDCLK, wait 150 cycles, clear both. The pull-up resistor on GPIO 17 (MCP2515 INT) ensures the line reads high when the MCP2515 is not asserting an interrupt (since INT is active-low, open-drain).

GPIO also provides edge and level event detection through registers GPEDS0/1 (event detect status), GPREN0/1 (rising edge enable), GPFEN0/1 (falling edge enable), GPHEN0/1 (high detect enable), and GPLEN0/1 (low detect enable). Setting a bit in GPFEN0 for GPIO 17 means the hardware will set the corresponding bit in GPEDS0 when a falling edge is detected (which is when the MCP2515’s INT line is asserted, since INT is active-low). This detection bit persists until explicitly cleared by writing a 1 to GPEDS0. The GIC-400 can be configured to route this GPIO event to an IRQ line, allowing the interrupt handler to be invoked without polling.

#define GPFSEL0    0xFE200000UL
#define GPFSEL1    0xFE200004UL
#define GPSET0     0xFE20001CUL
#define GPCLR0     0xFE200028UL
#define GPLEV0     0xFE200034UL
#define GPEDS0     0xFE200040UL
#define GPFEN0     0xFE200058UL

void gpio_configure_mcp_int(void) {
    /* GPIO 17: input, falling-edge detect, pull-up */
    uint32_t sel = mmio_read(GPFSEL1);
    sel &= ~(7u << 21);    /* GPIO 17 = bits [23:21] of GPFSEL1 */
    mmio_write(GPFSEL1, sel);  /* value 000 = input */

    /* Enable falling-edge detect on GPIO 17 */
    mmio_write(GPFEN0, mmio_read(GPFEN0) | (1u << 17));
}

bool gpio_mcp_int_asserted(void) {
    return (mmio_read(GPEDS0) >> 17) & 1;
}

void gpio_clear_mcp_int(void) {
    mmio_write(GPEDS0, 1u << 17);   /* write-1-to-clear */
}

The BCM2711 Mailbox Interface

The BCM2711 is not just a quad-core ARM chip — it is a system-on-chip that pairs the Cortex-A72 CPUs with a VideoCore VI GPU, and the two sides communicate through a mailbox interface. The mailbox mechanism matters to a bare-metal kernel for two reasons: the firmware that runs on the VideoCore side controls things that the ARM side needs (the UART clock rate being the most important), and the mailbox provides a way to query the board’s memory map.

Physically, the mailbox is a set of registers in the ARM peripheral area starting at 0xFE00B880. The ARM can write a message address into the mailbox write register; the VideoCore firmware processes the message and writes a reply to the same mailbox. The protocol is simple:

Messages are tagged property requests. The caller allocates a 16-byte-aligned buffer in memory, fills in a property tag, and passes the physical address of the buffer (OR’d with channel 8, the property channel) to the mailbox write register. The VideoCore processes the request in place, writing the response into the same buffer.

The most important use for a kernel is querying the actual UART clock rate, since the firmware may change it from the nominal 48 MHz:

#define MBOX_BASE  0xFE00B880UL
#define MBOX_READ  (MBOX_BASE + 0x00)
#define MBOX_STAT  (MBOX_BASE + 0x18)
#define MBOX_WRITE (MBOX_BASE + 0x20)
#define MBOX_FULL  (1u << 31)
#define MBOX_EMPTY (1u << 30)
#define MBOX_CH_PROP 8

/* Must be 16-byte aligned — place in .data with explicit alignment */
static volatile uint32_t mbox_buf[36] __attribute__((aligned(16)));

uint32_t mbox_get_uart_clock(void) {
    mbox_buf[0]  = 8 * 4;      /* total size in bytes */
    mbox_buf[1]  = 0;          /* request code */
    mbox_buf[2]  = 0x00038002; /* tag: get clock rate */
    mbox_buf[3]  = 8;          /* value buffer size */
    mbox_buf[4]  = 0;          /* 0 = request */
    mbox_buf[5]  = 2;          /* clock ID 2 = UART */
    mbox_buf[6]  = 0;          /* response: clock rate (Hz) filled here */
    mbox_buf[7]  = 0;          /* end tag */

    /* Flush the buffer to memory before passing its address to VideoCore */
    asm volatile("dsb sy" ::: "memory");

    uint32_t addr = ((uint32_t)(uintptr_t)mbox_buf) | MBOX_CH_PROP;

    /* Wait until mailbox is not full, then write */
    while (mmio_read(MBOX_STAT) & MBOX_FULL) {}
    mmio_write(MBOX_WRITE, addr);

    /* Wait for response */
    for (;;) {
        while (mmio_read(MBOX_STAT) & MBOX_EMPTY) {}
        if (mmio_read(MBOX_READ) == addr) break;
    }

    /* Invalidate cache before reading response */
    asm volatile("dsb sy" ::: "memory");

    if (mbox_buf[1] == 0x80000000) /* SUCCESS */
        return mbox_buf[6];
    return 0;
}

Several things deserve attention here. The dsb sy (“data synchronization barrier, full system”) instructions force all preceding stores to complete before the VideoCore reads the buffer, and force all loads to see the VideoCore’s writes after the response arrives. Without them, the Cortex-A72’s out-of-order execution and store buffer might cause the VideoCore to read a partially-initialized request, or the ARM to read stale cache data instead of the VideoCore’s response. This is the same story as volatile mmio_read/write applied to a DMA-like scenario: whenever two separate execution agents share memory, explicit barriers are required.

The mailbox also provides set_clock_rate (tag 0x00038002 with request flag bit set in buf[4]) for overclocking the UART. In practice, most CS 452 kernel implementations accept the firmware’s default clock and compute baud divisors accordingly rather than setting the clock explicitly.

The Auxiliary Peripheral Block (AUX)

In addition to the PL011 UART used for the terminal, the BCM2711 contains an Auxiliary block at 0xFE215000 that provides a Mini UART (UART1) and two additional SPI controllers (SPI1 and SPI2). These are simpler and more limited than the PL011 and SPI0, but they share a single interrupt line, which matters for interrupt routing.

Mini UART (UART1) is a 16550-compatible UART with an 8-byte FIFO (much smaller than the PL011’s 32-byte deep FIFO). Its baud rate derivation differs: Mini UART baud = system_clock_freq / (8 × (BAUD + 1)). Because it shares an IRQ with SPI1 and SPI2, the interrupt handler must check the AUX_IRQ register to determine which device caused the interrupt.

For CS 452, the Mini UART is rarely used directly — the PL011 is preferred for the terminal. However, knowing that UART1 exists matters because the RPi 4 firmware may remap UART1 to the GPIO 14/15 pins by default (depending on the config.txt setting), which would prevent the PL011 from working on those pins unless dtoverlay=disable-bt or enable_uart=1 is set in the firmware configuration. The W26 course environment uses specific config.txt settings to ensure the PL011 is on GPIO 14/15; understanding why those settings are necessary requires knowing the AUX UART exists.

The AUX_ENABLES register at 0xFE215004 controls which auxiliary peripherals are active. Bit 0 enables UART1, bit 1 enables SPI1, bit 2 enables SPI2. Setting a bit starts the clock to the peripheral; clearing it stops it and resets the peripheral’s registers.

Memory-Mapped I/O Discipline: Putting It All Together

Every peripheral access in the BCM2711 follows the same pattern, but the details differ between device types in ways that are easy to get wrong:

Ordinary MMIO registers (UART DR, SPI FIFO, GPIO function select): mark as volatile and access through mmio_read/mmio_write. The volatile qualifier prevents the compiler from caching the value in a register or reordering accesses. Each volatile load generates an actual memory read; each volatile store generates an actual memory write. This is sufficient for single-threaded polling loops.

Registers that must be modified atomically (GPIO GPFSEL — multiple bits per register, shared between pins): use read-modify-write. The BCM2711 does not provide a SET/CLEAR register pair for GPFSEL (though it does for output level via GPSET/GPCLR), so a read-modify-write is the only option. If two cores might simultaneously modify different pins in the same GPFSEL register, a spinlock is required.

DMA-shared buffers (mailbox buffers, DMA descriptors): require explicit cache-coherency barriers (dsb sy) because the Cortex-A72 caches may not be visible to the VideoCore or the DMA engine, which are separate bus masters. The __attribute__((aligned(16))) ensures the buffer does not straddle a cache line boundary in a way that could cause partial visibility.

Peripheral ordering (multi-step sequences like SPI CS assert → FIFO write → wait for DONE → CS deassert): individual mmio_write calls within a single core are ordered by the Cortex-A72’s memory model for device memory (Device-nGnRE type, configured by MAIR_EL1 bits and page table attributes). The ARMv8 architecture guarantees that accesses to Device memory are not reordered by the CPU with respect to each other in the program order. However, if you switch from MMIO writes to a delay loop that involves normal memory accesses, the compiler may reorder code unless barriers or volatile memory clobbers prevent it.

This discipline — volatile for MMIO, barriers for DMA, locks for multi-core, careful sequencing for multi-step protocols — appears in every embedded system and every OS. The BCM2711 just happens to make all the lessons concrete at once.

Chapter 5: Bare-Metal Toolchain

Writing a kernel means producing an executable with no operating system underneath it. The compiler and linker must be configured to match, and the startup code must take responsibility for every initialization step that normally happens automatically in a user-space program.

Cross-Compilation

The development machine (likely an x86-64 Linux box or macOS) cannot execute AArch64 binaries, so we use a cross-compiler: a version of GCC that runs on the host but produces code for the ARM64 target. The appropriate toolchain is aarch64-linux-gnu-gcc (from the GNU Arm Embedded Toolchain) or aarch64-elf-gcc for bare-metal targets (the -elf variant omits the Linux ABI assumptions and is preferred for kernels).

Compilation flags for a bare-metal kernel:

CC      := aarch64-elf-gcc
CFLAGS  := -Wall -Wextra -O2 \
            -ffreestanding \     # do not assume libc/crt0 are present
            -mgeneral-regs-only \ # do not generate FP/SIMD instructions
            -nostdlib \          # do not link standard libraries
            -nostartfiles        # do not link crt0.o

-ffreestanding is critical: it tells GCC not to assume that functions like memcpy, memset, or printf exist, and not to generate calls to them implicitly. The compiler may still inline small copies or optimizations, but it will not emit an external call to memcpy unless you explicitly call it yourself (in which case you must provide the implementation).

-mgeneral-regs-only prevents the compiler from using floating-point or SIMD registers. This matters because FP registers must be saved and restored on every context switch if the kernel uses them; by banning them from the kernel itself, context switch code only needs to handle the integer register file.

The ELF Format and Linker Scripts

GCC produces ELF (Executable and Linkable Format) object files. The linker combines these into a final ELF binary, which is then converted to a raw binary image (kernel8.img) that the RPi 4 firmware can load.

The firmware loads kernel8.img at physical address 0x80000. The linker must be told this. The linker script (typically link.ld) controls:

1. The output sections: .text (code), .rodata (read-only data), .data (initialized read-write data), .bss (uninitialized read-write data).
2. The load address: the physical address at which each section will reside at run time.
3. Symbol exports: addresses that become available as C-linkage symbols (__bss_start, __bss_end) for use by the startup code.

A minimal linker script for CS 452:

ENTRY(boot)

SECTIONS {
    . = 0x80000;                       /* load at RPi 4 kernel entry */

    .text : {
        KEEP(*(.text.boot))            /* boot.S first */
        *(.text .text.*)
    }

    .rodata : { *(.rodata .rodata.*) }

    .data : {
        . = ALIGN(8);
        *(.data .data.*)
    }

    .bss : {
        . = ALIGN(16);
        __bss_start = .;
        *(.bss .bss.*)
        *(COMMON)
        __bss_end = .;
    }

    /DISCARD/ : { *(.comment) *(.eh_frame) }
}

The ENTRY(boot) tells the linker which symbol is the entry point, recorded in the ELF header for tools that use it. The KEEP directive prevents the linker from discarding .text.boot even if no other section references it — this is necessary for the boot code that the linker cannot see being called externally.

BSS Zeroing

The C standard guarantees that uninitialized global and static variables are zero-initialized. In a user-space program, the OS zeros the BSS segment before handing control to crt0. In a bare-metal kernel, you must do this yourself. The startup assembly code uses the __bss_start and __bss_end symbols exported by the linker script:

// Zero the BSS before entering C
adr     x0, __bss_start
adr     x1, __bss_end
mov     x2, #0
.Lbss_loop:
    cmp     x0, x1
    b.ge    .Lbss_done
    str     x2, [x0], #8       // store zero, advance 8 bytes
    b       .Lbss_loop
.Lbss_done:
    bl      kmain              // enter C kernel

Failing to zero BSS is one of the most common sources of puzzling bugs in bare-metal code. A global integer array that appears to contain zeros in your test environment may contain garbage in the field because DRAM power-on state is not deterministic.

Freestanding C and the Slab Allocator

Without libc, common functions must either be reimplemented or avoided. strlen, memcpy, memset, and memmove are easily reimplemented. malloc, free, and realloc should not exist at all.

The kernel’s memory model is static allocation only. Every data structure is either a global variable, a stack-allocated local, or a member of a statically-allocated pool. The slab allocator is the idiomatic pattern for managing fixed-size objects. Given a maximum of 64 tasks, the task descriptor pool is an array of 64 task descriptors, with a free-list maintained by embedding a next pointer in each descriptor (an intrusive linked list):

typedef struct TaskDescriptor {
    int      tid;
    int      priority;
    int      state;
    uint64_t sp;             // saved stack pointer
    struct TaskDescriptor *next_send;  // send queue linkage
    // ... other fields
} TaskDescriptor;

static TaskDescriptor td_pool[MAX_TASKS];
static TaskDescriptor *td_freelist;

void td_init(void) {
    td_freelist = NULL;
    for (int i = MAX_TASKS - 1; i >= 0; i--) {
        td_pool[i].next_send = td_freelist;
        td_freelist = &td_pool[i];
    }
}

TaskDescriptor *td_alloc(void) {
    if (!td_freelist) return NULL;
    TaskDescriptor *td = td_freelist;
    td_freelist = td->next_send;
    return td;
}

This pattern allocates and frees in O(1) time with no fragmentation, at the cost of a fixed upper bound on the number of simultaneously live objects.

The Complete Kernel Boot Sequence

Understanding every step from hardware reset to the first user task is essential for debugging boot failures — which are uniquely difficult to diagnose because the kernel has no I/O infrastructure yet when they occur.

Step 0: Hardware reset. When the RPi 4 powers on, all four Cortex-A72 cores start at physical address 0x00000000 (the reset vector). The GPU bootloader (VC4 firmware) runs first — before any ARM code executes. It reads config.txt from the SD card’s FAT partition, configures clock speeds and memory sizes, then loads kernel8.img (the ARM64 kernel image) to physical address 0x80000 and signals the primary core (core 0) to start at 0x80000. Cores 1–3 remain in a spin loop awaiting a mailbox signal.

Step 1: Early assembly (boot.S). The processor is in EL2 at this point. The first instruction at 0x80000 is the boot symbol in boot.S. Tasks to complete before entering C:

.section ".text.boot"
.global boot

boot:
    // 1. Ensure we're executing on core 0 only
    mrs     x0, MPIDR_EL1
    and     x0, x0, #0xFF        // core number in bits [7:0]
    cbnz    x0, .Lhalt_secondary // cores 1-3 halt

    // 2. Drop from EL2 to EL1
    mrs     x0, CurrentEL
    lsr     x0, x0, #2
    cmp     x0, #2
    bne     .Lalready_el1        // already at EL1 (unusual)

    // Configure EL1 as AArch64
    mov     x0, #(1 << 31)       // HCR_EL2.RW = AArch64 at EL1
    msr     HCR_EL2, x0

    // Set up SPSR_EL2: return to EL1h, DAIF all masked
    mov     x0, #0x3C5
    msr     SPSR_EL2, x0
    adr     x0, .Lel1_entry
    msr     ELR_EL2, x0
    isb
    eret

.Lel1_entry:
    // 3. Set up a temporary kernel stack (SP_EL1)
    adr     x0, _stack_top       // symbol defined in linker script
    msr     SP_EL1, x0
    mov     sp, x0

    // 4. Zero the BSS section
    adr     x0, __bss_start
    adr     x1, __bss_end
    mov     x2, #0
.Lbss_loop:
    cmp     x0, x1
    b.ge    .Lbss_done
    str     x2, [x0], #8
    b       .Lbss_loop
.Lbss_done:

    // 5. Enter C kernel
    bl      kmain

    // Should never return
.Lhalt:
    wfe
    b       .Lhalt

.Lhalt_secondary:
    wfe
    b       .Lhalt_secondary

Step 2: C kernel entry (kmain). The C kmain function is now executing at EL1 with a temporary stack. It must initialize every subsystem before handing off to user space. The order matters — each step depends on the previous:

void kmain(void) {
    /* 1. Initialize UART immediately for debug output */
    uart0_init();
    uart0_puts("CS452 Kernel booting...\r\n");

    /* 2. Set up the exception vector table */
    extern void exception_vector_table(void);
    asm volatile ("msr VBAR_EL1, %0; isb"
                  :: "r"((uint64_t)exception_vector_table));
    uart0_puts("Exception vectors installed.\r\n");

    /* 3. Initialize the MMU with identity mapping */
    mmu_init();
    uart0_puts("MMU enabled.\r\n");

    /* 4. Initialize the GIC-400 */
    gic_init();
    uart0_puts("GIC initialized.\r\n");

    /* 5. Initialize kernel data structures */
    td_init();      // task descriptor pool
    scheduler_init(); // ready queues
    event_init();   // event registry
    uart0_puts("Kernel data structures initialized.\r\n");

    /* 6. Enable the system timer interrupt */
    timer_init();    // arm C1, enable GIC interrupt 97

    /* 7. Create the first user task */
    int first_tid = create_task(FIRST_TASK_PRIORITY, first_task);
    uart0_puts("First task created.\r\n");

    /* 8. Transfer to user space: schedule and run */
    TaskDescriptor *next = scheduler_next();
    /* This function does not return — it restores next's context and eret */
    kernel_exit_to_user(next->sp);
}

Step 3: MMU initialization. Before the MMU is enabled, accesses to device registers at 0xFE000000 work because the physical address is directly accessible. After the MMU is enabled with an identity map, the virtual and physical addresses are identical, so device accesses are unchanged. The key difference: the MMU now enforces memory type attributes (cacheable normal memory, device memory), which is necessary for correct cache behavior.

The MMU initialization sequence:

void mmu_init(void) {
    /* 1. Allocate page tables (statically, in BSS) */
    extern uint64_t page_table_l0[512];  /* 4KB, 512 × 8B entries */
    extern uint64_t page_table_l1[512];

    /* 2. Set MAIR_EL1: index 0 = Device-nGnRnE, index 1 = Normal WB */
    uint64_t mair = (0xFFULL << 8) | (0x00ULL);  /* [15:8]=Normal, [7:0]=Device */
    asm volatile ("msr MAIR_EL1, %0" :: "r"(mair));

    /* 3. Build level-0 table: one entry pointing to level-1 table */
    page_table_l0[0] = (uint64_t)page_table_l1 | 3;  /* table descriptor */

    /* 4. Build level-1 table: 1 GB blocks */
    /* Block 0: 0x00000000–0x3FFFFFFF = normal memory, attr index 1 */
    page_table_l1[0] = 0x00000000 | (1 << 10) | (1 << 2) | 1;
                                 /* AF=1 (accessed), AttrIdx=1, block */
    /* Block 3: 0xC0000000–0xFFFFFFFF = device memory, attr index 0 */
    page_table_l1[3] = 0xC0000000 | (1 << 10) | (0 << 2) | 1;

    /* 5. Set TCR_EL1: 48-bit VA, 4KB pages, TG0=4KB */
    uint64_t tcr = (16ULL << 0)   /* T0SZ = 16 → 48-bit VA */
                 | (0ULL  << 8)   /* IRGN0 = write-back */
                 | (0ULL  << 10)  /* ORGN0 = write-back */
                 | (3ULL  << 12)  /* SH0 = inner shareable */
                 | (0ULL  << 14); /* TG0 = 4KB */
    asm volatile ("msr TCR_EL1, %0; isb" :: "r"(tcr));

    /* 6. Set TTBR0_EL1 to the level-0 table */
    asm volatile ("msr TTBR0_EL1, %0; isb" :: "r"((uint64_t)page_table_l0));

    /* 7. Enable MMU (SCTLR_EL1.M = 1, plus I-cache and D-cache) */
    uint64_t sctlr;
    asm volatile ("mrs %0, SCTLR_EL1" : "=r"(sctlr));
    sctlr |= (1 << 0)   /* M: MMU enable */
           | (1 << 2)   /* C: D-cache enable */
           | (1 << 12); /* I: I-cache enable */
    asm volatile ("msr SCTLR_EL1, %0; isb; dsb sy" :: "r"(sctlr));
}

The isb after SCTLR_EL1 write is mandatory — the MMU is not enabled until after the ISB. Any cache maintenance before MMU enable must clean+invalidate all cache lines (DC CIVAC) because the cache interprets virtual addresses before the MMU is enabled differently after.

Step 4: First task execution. The kernel calls kernel_exit_to_user(next->sp) which restores the first task’s context and executes eret. The first task is now running at EL0 with full priority over all other tasks (since no other task exists yet). It calls Create() to spawn all server tasks, then calls Exit().

Why the order matters: if gic_init() is called before mmu_init(), the GIC’s device registers at 0xFF841000 are accessed without memory type attributes — potentially causing the processor to cache device register values, leading to incorrect hardware behavior. If event_init() is called before gic_init(), interrupt IDs may reference an uninitialized GIC state. The initialization order in kmain is not arbitrary; it reflects a dependency graph where each step requires all previous steps to have completed.

Debugging boot failures: a kernel that fails during boot typically manifests as no UART output (the uart0_puts never executes) or output stopping partway. The most common causes:

1. MMU page fault at boot: if mmu_init() crashes, the system resets immediately. Insert uart0_puts("About to enable MMU\r\n") before the SCTLR write; if this prints but nothing else does, the MMU initialization has a bug.
2. Stack overflow in kmain: the temporary stack set up in boot.S is small (often just a few KB). If kmain calls deeply-nested functions before td_init() sets up per-task stacks, the temporary stack overflows. Keep kmain shallow — initialize hardware, then delegate to user tasks.
3. Wrong entry point: if the linker script does not put .text.boot first, the processor jumps to the wrong instruction at 0x80000. Verify with aarch64-elf-objdump -d kernel8.elf | head -20 that the first instructions are the boot code.

Debugging Without a Debugger

One of the most disorienting aspects of bare-metal development is the absence of familiar debugging tools. There is no GDB attached to a running kernel, no core dump on a crash, no strace to observe system calls. When the kernel crashes or hangs, the evidence is often just a stopped terminal and a frozen train. Developing effective debugging strategies is therefore as important as writing correct code in the first place.

UART as the primary debug output: even before the terminal server is running, the mini-UART can be used in polling mode to print diagnostic messages. A minimal kprintf implemented with a polling write loop provides a stream of evidence about what the kernel is doing:

void uart_putc_polling(char c) {
    while (!(mmio_read(AUX_MU_LSR) & 0x20)) {}  // wait for TX space
    mmio_write(AUX_MU_IO, c);
}

void kputs(const char *s) {
    while (*s) uart_putc_polling(*s++);
}

The polling UART adds deterministic latency (proportional to the number of bytes output) to every print statement. For timing-sensitive code, print statements change behavior. This is the real-time debugging paradox: the act of observing the system changes it. Two strategies address this:

Post-mortem ring buffers: instead of printing immediately, write to a circular buffer in RAM. After the bug manifests (or a test run completes), print the buffer contents. The ring buffer write is fast (a few cycles for a word write), so it minimally disturbs timing. The buffer can record (timestamp, event_id, data) tuples for a complete execution history.

Assertions with halts: insert assert() macros at critical invariants (queue lengths, task states, pointer bounds). On failure, halt the processor with a diagnostic message before the cascading effects make the root cause unrecognizable. In a real-time kernel, an assertion failure is a development-time event; disable assertions in production builds.

The canary pattern: place a known magic value at the bottom of each task stack. Periodically check that the canary is intact. If it has been overwritten, the task’s stack has overflowed — a common cause of mysterious kernel panics. At stack allocation:

td->stack[0] = STACK_CANARY_VALUE;  // bottom of stack

In the idle task (which runs at the lowest priority and has time to do maintenance):

for each task in use:
    if td->stack[0] != STACK_CANARY_VALUE:
        kputs("STACK OVERFLOW in task "); kputd(td->tid); halt();

GCC sanitizers with QEMU: the qemu-system-aarch64 emulator can run the kernel binary on x86 development hardware (with the -M raspi4b machine type). QEMU supports GDB remote debugging over a TCP socket. While QEMU’s timing behavior differs from real hardware (it does not emulate cache misses or interrupt latency accurately), it is invaluable for logical correctness testing. Develop and test on QEMU; test timing behavior on real hardware.

The Build System: Make and Beyond

A typical CS 452 project uses GNU Make to manage the build. The structure should separate source files cleanly by subsystem:

cs452/
├── kernel/
│   ├── boot.S          # EL2→EL1 drop, BSS clear, entry to kmain
│   ├── exception.S     # exception vector table, syscall/IRQ entry
│   ├── task.c          # task creation, destruction, scheduler
│   ├── message.c       # Send, Receive, Reply implementation
│   ├── event.c         # AwaitEvent, interrupt delivery
│   └── kernel.h        # internal kernel interface
├── user/
│   ├── nameserver.c    # Name Server task
│   ├── clockserver.c   # Clock Server + Clock Notifier
│   ├── uart.c          # UART TX/RX servers and notifiers
│   ├── can.c           # CAN TX/RX servers and notifiers
│   └── syscall.h       # user-visible syscall wrappers
├── train/
│   ├── engineer.c      # per-train control loop
│   ├── track.c         # Track Server, Dijkstra, reservations
│   ├── sensor.c        # sensor attribution
│   └── calibration.c   # velocity and stopping-distance tables
├── lib/
│   ├── kprintf.c       # formatted output (vsnprintf + Putc)
│   ├── string.c        # strlen, strcpy, memcpy, memset
│   └── queue.h         # type-safe queue/stack templates
├── link.ld             # linker script
└── Makefile

A minimal Makefile:

CC      := aarch64-elf-gcc
CFLAGS  := -Wall -Wextra -O2 -ffreestanding -mgeneral-regs-only \
           -nostdlib -nostartfiles -I.
LDFLAGS := -T link.ld

SRCS    := $(shell find . -name '*.c' -o -name '*.S')
OBJS    := $(SRCS:.c=.o)
OBJS    := $(OBJS:.S=.o)

all: kernel8.img

kernel8.elf: $(OBJS)
	$(CC) $(LDFLAGS) -o $@ $^

kernel8.img: kernel8.elf
	aarch64-elf-objcopy -O binary $< $@

clean:
	rm -f $(OBJS) kernel8.elf kernel8.img

.PHONY: all clean

An important Makefile discipline: use pattern rules rather than listing every object file explicitly. As the project grows, adding a new .c file should automatically include it in the build.

Dependency generation: GCC can automatically generate Makefile dependency rules (-MMD -MP flags) so that changing a header file triggers recompilation of all files that include it. Without this, a stale object file from before a header change will silently produce incorrect behavior.

CFLAGS += -MMD -MP
-include $(OBJS:.o=.d)

QEMU-Based Development and Testing

QEMU can emulate the Raspberry Pi 4 (machine type raspi4b), allowing development and debugging on a regular workstation without physical hardware:

qemu-system-aarch64 \
    -M raspi4b \
    -kernel kernel8.elf \
    -serial stdio \
    -d int,cpu_reset \
    -no-reboot \
    -S -s

Flags:

• -serial stdio: connect UART0 to the terminal’s stdin/stdout.
• -d int,cpu_reset: log interrupts and CPU resets to stderr (useful for debugging exception-level transitions).
• -no-reboot: stop QEMU if the simulated CPU resets (instead of restarting — helps catch boot crashes).
• -S: pause at startup (wait for GDB).
• -s: enable the GDB server on port 1234.

In a separate terminal:

aarch64-elf-gdb kernel8.elf
(gdb) target remote :1234
(gdb) break kmain
(gdb) continue

This attaches GDB to the running QEMU instance, sets a breakpoint at the kernel main entry, and begins execution. When kmain is reached, GDB halts and you can inspect registers, memory, and step through code.

QEMU limitations: QEMU does not simulate the BCM2711’s peripheral registers with hardware-accurate timing. Timer interrupts may not arrive at the correct frequency, and SPI/UART simulation is simplified. Logical correctness can be tested in QEMU; timing correctness must be validated on real hardware. Particularly, the GIC-400 simulation in QEMU may not match the physical BCM2711 in all edge cases (e.g., spurious interrupt handling, priority mask behavior under nested interrupts).

A useful CI pattern: run a unit test suite against the kernel in QEMU on each commit to a shared repository. Tests that exercise message passing, the scheduler, and the clock server can run in QEMU without hardware access, providing fast feedback before deploying to the RPi.

Remote Deployment: SD Card and JTAG

The standard RPi 4 boot procedure loads kernel8.img from the boot partition of an SD card. During development, the edit-compile-flash-test cycle is slow. Two faster alternatives:

TFTP boot: configure the RPi 4 bootloader to attempt a network boot if the SD card is not found or if a GPIO pin is held. The development host runs a TFTP server; kernel8.img is served over the local network. This eliminates the SD card write step — a new binary is available to the RPi on next reset, taking approximately 5 seconds for a typical 100 KB kernel.

JTAG debugging: the BCM2711 exposes a JTAG interface on GPIO pins 22–27. A JTAG adapter (OpenOCD + J-Link or DAPLink) allows debugging directly on hardware: setting breakpoints, reading registers, and examining memory without modifying the running code. JTAG-based debugging is the gold standard for embedded debugging.

JTAG Architecture and the ARM Debug Access Port

JTAG (Joint Test Action Group, IEEE Std 1149.1) was originally designed for boundary-scan testing of PCB connections. Its later use as a debug interface leverages the same physical four-wire protocol (TDI, TDO, TCK, TMS, plus optional TRST) to access a processor’s internal debug registers without halting normal operation.

The JTAG chain is controlled by a Test Access Port (TAP) controller, a 16-state finite state machine driven by the TMS signal. Moving through the TAP states allows software to shift data into and out of two types of registers: instruction registers (IR), which select the operation, and data registers (DR), which carry the actual data. By chaining multiple TAPs together on a single JTAG chain, a single adapter can access multiple devices (CPU, FPGA, boundary scan cells).

ARM implements JTAG debug access through the Debug Access Port (DAP), which is part of the ARM CoreSight debug architecture. The DAP connects to multiple Access Ports (APs): a MEM-AP for memory-mapped debug access and an APB-AP for CoreSight component access. Through the MEM-AP, a debugger can read and write any address in the CPU’s physical address space — including peripheral registers at their MMIO addresses — without the CPU’s involvement.

The ROM Table is a CoreSight concept: at a fixed offset from the debug base address, there is a table listing the addresses of all debug components (CPU debug registers, ETM trace, CTI cross-trigger interface). OpenOCD reads the ROM Table during initialization to discover the system’s debug topology.

BCM2711 JTAG Pinout and Configuration

The BCM2711’s JTAG interface is multiplexed with GPIO pins 22–27. By default, these pins serve GPIO functions after reset; JTAG mode must be explicitly activated. There are two ways to do this:

config.txt option: add enable_jtag_gpio=1 to the first partition’s config.txt. This configures the GPIO pin mux before handing off to the kernel. The assignment is:

Software pin-mux: the kernel can configure the GPFSEL registers to set these GPIO pins to Alt4 function programmatically. This is useful when the debug session should be enabled only after certain initialization steps complete (e.g., after the MMU and caches are initialized), allowing UART-based debugging before JTAG takes over.

Note that JTAG debugging requires physical access to the GPIO header of the RPi 4 — a 40-pin ribbon cable connecting the RPi to the debug adapter. The CS 452 lab’s RPi units typically have a JTAG header soldered for exactly this purpose.

OpenOCD Configuration for BCM2711

OpenOCD (Open On-Chip Debugger) is the open-source software that drives the JTAG adapter and exposes a GDB server. The BCM2711 configuration requires two files:

Interface file (for the specific adapter, e.g., a DAPLink or J-Link):

# interface/jlink.cfg
interface jlink
transport select jtag
adapter speed 1000

Target file (for the BCM2711 core):

# target/bcm2711_rpi4.cfg
set _CHIPNAME bcm2711

# The BCM2711 has 4 Cortex-A72 cores; we use core 0 only
set _TARGETNAME $_CHIPNAME.a72.0

jtag newtap $_CHIPNAME tap -irlen 4 -expected-id 0x4ba00477

dap create $_CHIPNAME.dap -chain-position $_CHIPNAME.tap

# MEM-AP for AHB access to CPU registers and peripherals
target create $_TARGETNAME cortex_a \
    -dap $_CHIPNAME.dap -ap-num 0 \
    -dbgbase 0x80010000 -ctibase 0x80018000

# Halt all cores — only core 0 is relevant
$_TARGETNAME configure -event reset-halt { echo "Core 0 halted" }

# GDB port
gdb_port 3333

Starting OpenOCD:

openocd -f interface/jlink.cfg -f target/bcm2711_rpi4.cfg

OpenOCD prints progress as it initializes the DAP, reads the ROM table, and connects to the Cortex-A72 debug registers. Once started, it listens on port 3333 for GDB connections and on port 4444 for a telnet command interface.

GDB Remote Target Session

With OpenOCD running, GDB connects over the remote protocol:

$ aarch64-elf-gdb kernel8.elf
(gdb) target remote :3333
(gdb) monitor halt              # halt the CPU
(gdb) info registers            # inspect all registers
(gdb) x/20i $pc                 # disassemble 20 instructions at current PC
(gdb) break kmain               # set hardware breakpoint (limited to 6 on A72)
(gdb) continue                  # resume execution

The Cortex-A72 provides six hardware breakpoints and four hardware watchpoints (data access triggers). Hardware breakpoints do not modify the instruction stream — unlike software breakpoints, which replace an instruction with a BRK #0 — making them usable in code that validates its own integrity (e.g., a kernel that checksums its text segment). For CS 452, the primary uses are:

• Breakpoints on exception vector entries: catching unexpected exceptions (SError, FIQ in EL1) without adding code to the handler.
• Watchpoints on the ready_mask bitmask: catching any write to the scheduler’s priority mask, useful for debugging rare priority corruption.
• Watchpoints on a task descriptor’s state field: catching any transition out of READY that isn’t through the scheduler’s scheduler_next() function.

The GDB monitor command passes arbitrary OpenOCD TCL commands through GDB to the OpenOCD server. Useful monitor commands:

monitor reset halt       # reset the CPU and halt before first instruction
monitor reg              # dump OpenOCD's view of registers (not GDB's)
monitor mdw 0x20000000 4 # read 4 words at memory address 0x20000000
monitor mww 0x3F200000 0 # write 0 to the GPIO FSEL0 register (dangerous!)

JTAG Limitations in Real-Time Systems

JTAG’s key limitation in a real-time context is that hardware breakpoints halt the processor, stopping all interrupt handling and all timing. When the CPU is halted at a breakpoint, the system timer’s compare register continues counting but no interrupt handler fires. On breakpoint continue, the accumulated interrupts may fire all at once, distorting the kernel’s timing state. Specifically:

• The clock server’s tick count may lag, causing tasks waiting on Delay() to wake up late.
• The CAN receive buffer may overflow if the CPU is halted while a train sensor stream arrives.
• The UART TX FIFO may underflow, causing garbled output after resuming.

This means that hardware-breakpoint debugging is useful for logical correctness (is the right code path taken? is the data structure consistent?) but unreliable for timing correctness (is this code executing within its WCET?). For timing analysis, the ring-buffer profiler described in Chapter 20 is more appropriate: it records timestamps without halting the CPU.

A subtler issue: the GIC-400 in the BCM2711 is implemented on the CoreSight bus. When the CPU is halted via JTAG, the GIC continues operating — interrupts arrive and are queued in the GIC’s pending register. However, since the CPU is halted, the interrupt is not delivered. When the CPU resumes, the pending interrupt is immediately delivered. If the kernel was halted partway through an interrupt handler (after writing GICC_IAR but before writing GICC_EOIR), the GIC may be in an inconsistent state. The safe approach: always set breakpoints at function boundaries (where the kernel is in a known quiescent state), not inside interrupt handlers.

For most CS 452 use cases, QEMU + UART debugging is sufficient. JTAG becomes necessary when debugging problems that QEMU cannot simulate: precise interrupt timing, cache coherency bugs between the CPU and DMA, or boot-stage failures that occur before UART output is available.

Memory Layout: Stack Sizes and Task Counts

With static allocation, the total kernel memory usage is fully determined at compile time. A CS 452 kernel with:

• 64 task descriptors at ~128 bytes each = 8 KB
• 64 task stacks at 8 KB each = 512 KB
• 64 kernel stacks at 4 KB each = 256 KB
• Kernel code and data = ~100 KB (typical)
• Delay queue, send queues, event registry = ~10 KB

Total: ~886 KB. The BCM2711 has 1–8 GB of SDRAM depending on the board variant; even 1 GB is 1000× more than the kernel needs. The actual constraint is the CPU cache. The kernel should fit in the 1 MB L2 cache; most of it does, as 886 KB is close to the L2 limit, but the task stacks dominate. Reducing task stack sizes (to 4 KB per task) brings the total to ~634 KB.

Stack sizing is a classic embedded systems challenge. Too small and you get stack overflows; too large and you waste memory (and cache). The canary pattern helps diagnose overflows, but it is reactive. Proactive sizing requires either static stack analysis (tools like StackAnalyzer from AbsInt) or worst-case measurement (running the system with full debug instrumentation and observing the high-water mark of stack usage).

A practical heuristic for CS 452: allocate 8 KB for user task stacks and 4 KB for kernel stacks. This is sufficient for tasks that use a few hundred bytes of local variables and call 3–4 levels of functions. If a task does string formatting with large local buffers (e.g., a 256-byte kprintf buffer), account for it explicitly.

C++ in the Kernel

CS 452 permits C++ in the kernel, subject to limitations. Useful C++ features:

• Templates: for type-safe intrusive linked lists, priority queues, and FIFO queues without dynamic allocation. A Queue<T, N> template that holds up to N objects of type T avoids the type-unsafe void * casts of C.
• RAII: for interrupt masking regions — a guard object that clears DAIF in its constructor and restores it in its destructor ensures that interrupts are always unmasked when the guard goes out of scope, even if an early return is taken.
• Constexpr: for compile-time computation of queue sizes, priority bounds, and memory map offsets. No runtime cost.

C++ features that must be avoided:

• Exceptions: require runtime support library (libstdc++ unwind tables) and _Unwind_RaiseException. Not available in freestanding mode.
• RTTI (dynamic_cast, typeid): requires typeinfo objects in .rodata, adds size overhead, and may generate library calls.
• Global constructors with non-trivial initialization: must be called explicitly via the .init_array section (Chapter 5 covers this). If a global constructor calls a kernel function (e.g., to register a name), and the kernel is not yet initialized when the constructor runs, the result is undefined behavior.
• Standard library containers (std::vector, std::map): all use dynamic memory allocation. Define __attribute__((noreturn)) void operator new(size_t) { halt(); } to catch any accidental new expressions at link time.

A Complete Makefile for a CS 452 Kernel

Building a bare-metal kernel involves several steps: compiling C and assembly sources, linking with a custom linker script, converting the ELF binary to a raw image, and deploying to the RPi 4. A well-organized Makefile ties these steps together so that make rebuilds only what changed and make deploy copies the kernel to the SD card.

# CS 452 Kernel Makefile
# Targets: make (build), make clean, make deploy, make qemu

# ─── Toolchain ─────────────────────────────────────────────────────────────────
CC      := aarch64-elf-gcc
AS      := aarch64-elf-as
LD      := aarch64-elf-ld
OBJCOPY := aarch64-elf-objcopy
OBJDUMP := aarch64-elf-objdump

# ─── Compiler Flags ─────────────────────────────────────────────────────────────
CFLAGS := -Wall -Wextra -Werror \
           -O2 -g3 \
           -ffreestanding \
           -mgeneral-regs-only \
           -nostdlib \
           -nostartfiles \
           -march=armv8-a \
           -mtune=cortex-a72 \
           -mcpu=cortex-a72 \
           -fno-omit-frame-pointer \
           -fstack-usage

# -g3 includes macro expansions in DWARF debug info (useful with GDB)
# -fstack-usage generates .su files with per-function stack usage estimates
# -fno-omit-frame-pointer preserves x29 as frame pointer for backtraces

ASFLAGS := -g
LDFLAGS := -T link.ld

# ─── Source Files ───────────────────────────────────────────────────────────────
C_SRCS   := $(wildcard kernel/*.c) $(wildcard user/*.c) $(wildcard lib/*.c)
ASM_SRCS := $(wildcard kernel/*.S) $(wildcard user/*.S)

OBJ_DIR  := build
C_OBJS   := $(patsubst %.c, $(OBJ_DIR)/%.o, $(C_SRCS))
ASM_OBJS := $(patsubst %.S, $(OBJ_DIR)/%.o, $(ASM_SRCS))
OBJS     := $(C_OBJS) $(ASM_OBJS)

# ─── Targets ───────────────────────────────────────────────────────────────────
KERNEL_ELF := build/kernel8.elf
KERNEL_IMG := build/kernel8.img
KERNEL_MAP := build/kernel8.map

.PHONY: all clean deploy qemu disasm size

all: $(KERNEL_IMG)

$(KERNEL_IMG): $(KERNEL_ELF)
	$(OBJCOPY) -O binary $< $@
	@echo "Built: $@ ($(shell wc -c < $@ | tr -d ' ') bytes)"

$(KERNEL_ELF): $(OBJS) link.ld
	$(LD) $(LDFLAGS) -Map=$(KERNEL_MAP) -o $@ $(OBJS)

$(OBJ_DIR)/%.o: %.c
	@mkdir -p $(dir $@)
	$(CC) $(CFLAGS) -c $< -o $@

$(OBJ_DIR)/%.o: %.S
	@mkdir -p $(dir $@)
	$(CC) $(CFLAGS) $(ASFLAGS) -c $< -o $@

clean:
	rm -rf $(OBJ_DIR)

# Copy kernel image to SD card (adjust SDCARD_MOUNT for your system)
SDCARD_MOUNT ?= /Volumes/BOOT
deploy: $(KERNEL_IMG)
	cp $(KERNEL_IMG) $(SDCARD_MOUNT)/kernel8.img
	sync
	@echo "Deployed to $(SDCARD_MOUNT)/kernel8.img"

# Run in QEMU with GDB server on port 1234
qemu: $(KERNEL_ELF)
	qemu-system-aarch64 \
	    -M raspi4b \
	    -kernel $(KERNEL_ELF) \
	    -serial stdio \
	    -no-reboot \
	    -d int,cpu_reset \
	    -S -s

# Disassemble kernel
disasm: $(KERNEL_ELF)
	$(OBJDUMP) -d --source --demangle $(KERNEL_ELF) | less

# Report size of each section
size: $(KERNEL_ELF)
	aarch64-elf-size -A $(KERNEL_ELF)

# Dependency generation: each .c file generates a .d file listing its includes
DEPFLAGS = -MT $@ -MMD -MP -MF $(OBJ_DIR)/$*.d
$(OBJ_DIR)/%.o: %.c $(OBJ_DIR)/%.d
	@mkdir -p $(dir $@)
	$(CC) $(CFLAGS) $(DEPFLAGS) -c $< -o $@

DEPS := $(OBJS:.o=.d)
-include $(DEPS)

Several features of this Makefile deserve comment.

-march=armv8-a -mtune=cortex-a72 -mcpu=cortex-a72: these three flags together give the compiler complete information about the target CPU. -march specifies the instruction set (ARMv8-A, which the Cortex-A72 implements). -mtune enables micro-architectural optimizations (e.g., choosing branch-free sequences that minimize Cortex-A72 branch mispredictions). -mcpu combines both. Using all three is redundant but makes intent explicit.

-fstack-usage: generates a .su file alongside each object file. Each .su file lists the stack frame size for every function in the translation unit. A static analysis tool (aarch64-elf-gcc -fstack-usage + a custom script) can walk the call graph and compute the maximum stack depth, helping to size task stacks without over-allocating. The .su data is also useful for identifying which functions have large stack frames and should be refactored.

-fno-omit-frame-pointer: the Cortex-A72 has 31 general-purpose registers, and GCC normally uses x29 as a frame pointer only when necessary. This flag forces x29 to always point to the current frame. This allows GDB to generate backtraces in debug sessions (without a frame pointer, the unwinder must rely on DWARF unwind tables, which in a freestanding build may not be complete). The cost is that x29 is unavailable as a general-purpose register, slightly increasing register pressure.

Dependency generation (-MMD -MP -MF): the -MMD flag makes GCC generate a Makefile dependency file (.d) listing all header files included by the source. The -include $(DEPS) at the bottom includes these dependency files, so that changing a header causes all dependent sources to be recompiled. Without this, changing a struct definition in a .h file would not trigger recompilation of files that include it — a common source of puzzling stale-binary bugs.

The deploy target assumes the SD card is mounted at /Volumes/BOOT (macOS) or /media/pi/BOOT (Linux). Adjust for your environment. The sync call flushes the filesystem cache to ensure the file is fully written before unmounting the card.

The disasm target is invaluable for debugging: make disasm | grep -A 20 "handle_irq" shows the disassembly of the interrupt handler with source annotations (from -g3). Cross-referencing the disassembly against the high-level C ensures that the compiler’s optimization did not inadvertently move a store before a barrier or eliminate a volatile read.

The Boot Sequence in Detail

The RPi 4’s boot sequence passes through several stages before the kernel begins:

Stage 0 (VideoCore firmware): the GPU runs first. It loads a secondary bootloader (bootcode.bin) from the SD card. This is fixed in ROM and cannot be modified.

Stage 1 (bootcode.bin): a GPU-side bootloader that loads start4.elf (the main GPU firmware) from the SD card. Also loads config.txt to configure system parameters (UART pin assignment, clock rates, memory split).

Stage 2 (start4.elf): the full GPU firmware. It configures the peripherals, sets the ARM core frequencies, and loads kernel8.img from the SD card into DRAM at address 0x80000. Then it sets the ARM core PC to 0x80000 and releases the ARM core from reset.

Stage 3 (your code): execution begins at address 0x80000, which is the first instruction of your boot.S. At this point:

• The ARM core is at EL2 (Hypervisor level) with AArch64.
• DRAM is accessible from 0x00000000 to the top of installed RAM.
• The GPU-side peripherals (0xFE000000 onwards) are memory-mapped.
• SP_EL2 is undefined (you must set it before making calls).
• All four cores are active; cores 1–3 are spinning in a firmware loop waiting for a startup address to be written to a mailbox register.

The boot.S entry sequence:

.section .text.boot
.global boot

boot:
    /* Determine which CPU core we are */
    mrs     x0, MPIDR_EL1
    and     x0, x0, #3             /* CPU ID = bits [1:0] */
    cbnz    x0, .Lsecondary_hold   /* cores 1-3 go to a parking loop */

    /* We are core 0 — proceed with initialization */
    /* Drop from EL2 to EL1 */
    bl      el2_to_el1

    /* Set up initial SP_EL1 */
    adr     x0, __kernel_stack_top
    msr     SP_EL1, x0

    /* Initialize BSS */
    bl      bss_zero

    /* Initialize the exception vector table */
    adr     x0, exception_vector_table
    msr     VBAR_EL1, x0
    isb

    /* Enter the C kernel */
    bl      kmain
    b       .Lhalt      /* Should never return */

.Lsecondary_hold:
    /* Secondary CPUs park here indefinitely */
    wfi
    b       .Lsecondary_hold

.Lhalt:
    wfi
    b       .Lhalt

The MPIDR_EL1 register’s lower 2 bits give the CPU core number (0–3). Cores 1–3 are sent to an infinite WFI loop — they will never be used in the CS 452 single-core kernel. If a bug causes one of the secondary cores to escape this loop (perhaps through a firmware error), it would execute code at its current PC with an undefined stack, causing unpredictable behavior. A more robust park loop writes the core ID to a watchdog register and enters WFI; the watchdog reset fires if the core ever escapes.

The el2_to_el1 procedure configures the exception return state to drop from EL2 to EL1 with the correct PSTATE settings for a kernel that runs at EL1 with DAIF set and AArch64 state. This procedure was described in detail in Chapter 3.

Debugging Without GDB: The UART as a Debug Interface

In the early phases of kernel bring-up — before the interrupt system is working, before tasks exist, before the scheduler runs — the only debug output is the UART. A minimal polling UART driver (no interrupts, no task structure) suffices:

void uart_putc(char c) {
    volatile uint32_t *FR   = (volatile uint32_t *)0xFE201018;
    volatile uint32_t *DR   = (volatile uint32_t *)0xFE201000;
    while (*FR & (1u << 5)) {}  /* wait until TX FIFO not full */
    *DR = (uint32_t)c;
}

void uart_puts(const char *s) {
    for (; *s; s++) {
        if (*s == '\n') uart_putc('\r');
        uart_putc(*s);
    }
}

/* Minimal hex dump for debugging */
void uart_hex64(uint64_t v) {
    uart_puts("0x");
    for (int i = 60; i >= 0; i -= 4) {
        int nibble = (v >> i) & 0xF;
        uart_putc(nibble < 10 ? '0' + nibble : 'a' + nibble - 10);
    }
}

This function works even before the MMU is configured, before interrupts are enabled, and before any kernel data structures are initialized, because it uses only MMIO accesses to a single peripheral address and loops in a register. It is the “printf on a bare metal” equivalent.

A common bring-up pattern: add uart_puts("Stage X\n") markers at each initialization step (EL2→EL1 drop, BSS zero, UART init, interrupt enable, first task creation). On the development host, minicom -b 115200 -D /dev/ttyUSB0 displays these messages in real time. When the system hangs, the last printed stage identifies the failing step. This technique predates formal debuggers by decades and remains the most reliable bring-up approach — no tool setup required, no hardware compatibility issues, no JTAG chain to configure.

Chapter 6: Serial Communication — UART, SPI, and CAN

Three serial interfaces connect the kernel to the outside world: UART for human-readable terminal communication, SPI for communication with the MCP2515 CAN controller, and CAN bus for communication with the Märklin train hardware. Each protocol represents a different point in the design space of serial communication.

UART: Asynchronous Serial

Universal Asynchronous Receiver/Transmitter (UART) is the oldest and simplest of the three. It is asynchronous — transmitter and receiver share no clock signal; instead, they agree in advance on a baud rate (bits per second) and each runs a local clock to sample the signal. A UART frame consists of:

1. A start bit (logic 0, indicating the beginning of a frame)
2. Five to nine data bits (typically eight)
3. An optional parity bit (for error detection)
4. One or two stop bits (logic 1, returning the line to idle)

At 115200 baud, each bit is approximately 8.7 µs wide. The receiver samples each bit at the midpoint, allowing up to ±4.3 µs of clock drift per bit before a misread. Over ten bits (start + 8 data + stop), the accumulated drift budget is 4.3 µs — tight enough that UART links over long cables can lose synchronization due to clock imprecision in cheap oscillators.

The BCM2711 provides two UART implementations. PL011 (UART0, at physical base 0xFE201000) is a full-featured ARM primecell UART with 32-character TX and RX FIFOs, configurable trigger levels, and hardware flow control via RTS/CTS lines. The Mini-UART (AUX_MU, at physical base 0xFE215040) is simpler but shares resources with the SPI0 interface and has a fixed 8-bit baud-rate calculation. CS 452 uses PL011 for terminal output and the Mini-UART or the AUX peripheral for CAN communications.

Flow control is critical when the receiver cannot guarantee bounded processing latency. Without flow control, a fast transmitter can overflow the receiver’s FIFO. Clear-To-Send (CTS) hardware flow control uses a dedicated hardware pin: the receiver asserts CTS when it can accept data; the transmitter checks CTS before each byte. The PL011 can perform CTS checking automatically in hardware, freeing the software from polling the status register before every byte.

The UART FIFOs have configurable trigger levels: the RXFIFO interrupt fires when the receive FIFO reaches 1/8, 1/4, 1/2, 3/4, or 7/8 full; the TXFIFO interrupt fires when the transmit FIFO falls below the trigger level. Choosing the right trigger level is an engineering trade-off: a low RX trigger (fire at 1/8 full) means frequent interrupts and low latency but high overhead; a high trigger (fire at 7/8 full) batches interrupts but risks overflow if the processor is slow to respond.

SPI: Synchronous Serial

The Serial Peripheral Interface (SPI) is a synchronous, full-duplex bus designed by Motorola in the 1980s for short-distance chip-to-chip communication. Unlike UART, SPI uses an explicit clock signal (SCLK) driven by a designated master. The master also drives MOSI (master out, slave in) while the slave simultaneously drives MISO (master in, slave out). A separate chip-select pin (CS̄, active low) addresses individual peripherals on a shared bus.

The SPI0 peripheral on the BCM2711 (physical base 0xFE204000) can operate at up to 125 MHz (half the system clock), though the MCP2515 is rated to 10 MHz maximum. SPI has no built-in addressing scheme: each chip-select assertion initiates a transaction with one specific peripheral. For the MCP2515, a typical transaction sequence is: assert CS̄, send command byte, send/receive address byte(s) and data byte(s), deassert CS̄.

Because SPI is synchronous, there is no baud-rate mismatch or sampling ambiguity. The trade-offs relative to UART are: SPI requires more wires (at least 4 vs. 2), the master must drive the clock, and the bus topology is point-to-point or single-master star rather than multi-drop.

CAN Bus: Deterministic Multi-Drop Serial

The Controller Area Network (CAN) protocol was developed by Robert Bosch GmbH in the early 1980s for automotive applications. Its defining characteristics — multi-drop topology, arbitration without a master, error detection and recovery — were driven by the needs of automotive systems: many ECUs sharing a single cable, with no single point of coordination.

A CAN bus is a differential signal pair (CANH, CANL). The bus can be in one of two states: dominant (logic 0, CANH–CANL ≈ 2V) or recessive (logic 1, CANH–CANL ≈ 0V). When multiple nodes transmit simultaneously, a dominant bit overrides all recessive bits — this is the “wired-AND” property that enables arbitration.

Non-destructive arbitration works as follows. Every node that wants to transmit begins transmitting its frame simultaneously, starting with the identifier field. Each node monitors the bus while transmitting. If it transmits a recessive bit but reads a dominant bit, it lost arbitration and immediately stops transmitting, deferring to the winner. The node with the numerically lowest identifier always wins. This scheme requires that all nodes have bit-synchronous clocks — CAN uses NRZ encoding with bit stuffing (after five consecutive identical bits, a complementary stuffing bit is inserted) to maintain clock synchronization.

A standard CAN data frame (CAN 2.0A, 11-bit identifier) contains:

SOF  | Arbitration (11 bits ID + RTR) | Control (6 bits) | Data (0–64 bytes) |
CRC (15 bits) | CRC delimiter | ACK | ACK delimiter | EOF (7 bits)

The Extended Frame format (CAN 2.0B, 29-bit identifier) extends the identifier field and is used by the Märklin CS2/CS3 protocol. The extended identifier provides 29 bits of address space, supporting up to 536 million distinct message identifiers.

CAN’s error detection is multi-layered: cyclic redundancy check (15-bit CRC), bit monitoring (each node reads what it writes and checks for mismatch), bit stuffing violation detection, frame format checking, and acknowledgement checking. Any detected error triggers an error frame, and all nodes restart the transmission. Nodes track error counts in transmit and receive error counters; if a node’s error count exceeds 128, it enters error passive mode and stops asserting error frames; above 255, it enters bus-off and disconnects entirely.

The bitrates supported range from 10 kbit/s (long cables, noisy environments) to 1 Mbit/s (short, clean cables). The Märklin system runs at 250 kbit/s, which allows cable lengths up to approximately 100 metres without terminators while still providing adequate throughput for the relatively low message rates of a model railway control protocol.

CAN Error Detection in Depth

CAN’s error detection is comprehensive because the protocol was designed for automotive applications where cable harnesses are noisy, connectors corrode, and the cost of a missed message could be a brake failure. The five error-detection mechanisms operate at different layers:

Bit error (transmitter monitors itself): while transmitting, every node reads back the bus level simultaneously. If a node transmits a recessive bit (logic 1) but reads a dominant bit (logic 0), it has been overridden by another node’s dominant bit — this is normal during arbitration and expected. But if it happens after arbitration is settled (in the data field), it is a bit error, and the transmitter immediately aborts and sends an error frame.

Stuff error: CAN uses non-return-to-zero (NRZ) encoding with bit stuffing — after 5 consecutive identical bits, a complementary stuffing bit is inserted. This limits the maximum run of identical bits to 5, ensuring clock synchronization by frequent signal transitions. A receiver that detects 6 consecutive identical bits in a normally-stuffed region has detected a stuff error.

CRC error: the transmitter computes a 15-bit CRC over the identifier and data fields and appends it. Each receiver independently computes the same CRC. If the computed CRC differs from the transmitted CRC, the frame has been corrupted.

Form error: certain bit fields (CRC delimiter, ACK delimiter, end-of-frame) must be recessive (logic 1). A dominant bit in these fields is a form error.

Acknowledgement error: after a frame is transmitted, the transmitter checks the ACK slot. Every receiver that successfully received the frame (no errors detected so far) overdrives the ACK slot to dominant. If no receiver acknowledges — the ACK slot remains recessive — the transmitter has sent a frame that no one received, and reports an ACK error. This detects the case where the transmitter is on the bus alone (disconnected cable) or all receivers are in error-passive mode.

When any of these errors is detected, the detecting node sends an active error frame: 6 consecutive dominant bits (a deliberate violation of the bit-stuffing rule, which other nodes will also detect as an error) followed by an 8-bit error delimiter. All nodes restart their receivers. The original frame’s transmission is aborted and must be retransmitted.

The error counter mechanism prevents faulty nodes from disrupting the bus indefinitely. Each node maintains a transmit error counter (TEC) and a receive error counter (REC). Detecting a transmit error increments TEC by 8; successfully transmitting a frame decrements TEC by 1. When TEC > 127, the node enters error passive mode: it still participates in communication but sends passive error frames (6 recessive bits, invisible to other nodes) and waits 8 error delimiter bits (rather than 3) before retransmitting. When TEC > 255, the node enters bus-off and disconnects from the bus entirely until software resets it (or after 128 occurrences of 11 consecutive recessive bits).

For the MCP2515, TEC and REC are readable in registers 0x1C and 0x1D. Monitoring these counters is good diagnostic practice: TEC/REC values creeping upward indicate CAN bus issues (loose connectors, interference, incorrect bit timing) before the node enters error passive mode.

Bit Timing Configuration

The MCP2515 bit timing is configured through three registers: CNF1 (0x2A), CNF2 (0x29), CNF3 (0x28). The CAN bit period is divided into four segments: Sync Seg (always 1 TQ), Prop Seg, Phase Seg 1, and Phase Seg 2, where TQ (Time Quantum) is derived from the oscillator clock. For a 16 MHz oscillator and 250 kbit/s:

A valid setting for 250 kbit/s at 16 MHz: BRP=1 (CNF1[5:0]=0), SJW=1 (CNF1[7:6]=0), PropSeg=1 (CNF2[2:0]=0), PhaseSeg1=4 (CNF2[5:3]=3), PhaseSeg2=4 (CNF3[2:0]=3), BTLMODE=1.

Resulting TQ count per bit = 1 + 2 + 5 + 5 = 13 TQ. At BRP=1, TQ frequency = 16 MHz / 2 = 8 MHz. Bit rate = 8 MHz / 13 ≈ 615 kbit/s — too fast. Adjusting BRP=2: TQ = 8 MHz / 2 = 4 MHz. Bit rate = 4 MHz / (1 + 2 + 5 + 5) = 307 kbit/s — close but not exact 250 kbit/s. The exact register values for 250 kbit/s at 16 MHz are available in the Microchip application note AN754 and the Pigpio library.

Getting bit timing wrong is one of the most common MCP2515 bring-up errors. Symptoms: TEC rises rapidly, REC stays at 0 (receiver never successfully receives), no messages appear in receive buffers. Diagnosis: connect an oscilloscope to CANH/CANL and verify the bit timing matches the expected 4 µs bit period.

MCP2515 Complete Initialization Sequence

The full MCP2515 initialization in C, starting from hardware reset through entering Normal operating mode:

/* MCP2515 register addresses */
#define MCP_CANSTAT   0x0E
#define MCP_CANCTRL   0x0F
#define MCP_CNF3      0x28
#define MCP_CNF2      0x29
#define MCP_CNF1      0x2A
#define MCP_CANINTE   0x2B
#define MCP_CANINTF   0x2C
#define MCP_EFLG      0x2D
#define MCP_TXB0CTRL  0x30
#define MCP_RXB0CTRL  0x60
#define MCP_RXB1CTRL  0x70
#define MCP_RXF0SIDH  0x00  /* receive filter 0 — standard ID high byte */
#define MCP_RXM0SIDH  0x20  /* receive mask 0 — standard ID high byte */

/* Control mode bits */
#define MCP_MODE_NORMAL    0x00
#define MCP_MODE_SLEEP     0x20
#define MCP_MODE_LOOPBACK  0x40
#define MCP_MODE_LISTENONLY 0x60
#define MCP_MODE_CONFIG    0x80

/* CANINTE interrupt enable bits */
#define MCP_RX0IE  (1 << 0)  /* RX buffer 0 full */
#define MCP_RX1IE  (1 << 1)  /* RX buffer 1 full */
#define MCP_TX0IE  (1 << 2)  /* TX buffer 0 empty */
#define MCP_TX1IE  (1 << 3)  /* TX buffer 1 empty */
#define MCP_TX2IE  (1 << 4)  /* TX buffer 2 empty */
#define MCP_ERRIE  (1 << 5)  /* error interrupt */

void mcp2515_reset(void) {
    spi0_cs_assert();
    spi0_transfer_byte(0xC0);  /* RESET command */
    spi0_cs_deassert();
    /* The MCP2515 enters Configuration mode after reset.
       Oscillator start-up time: 128 × Tosc = 128/16MHz = 8 µs.
       Wait at least 2× longer to be safe. */
    delay_us(20);
}

void mcp2515_write_reg(uint8_t addr, uint8_t val) {
    spi0_cs_assert();
    spi0_transfer_byte(0x02);   /* WRITE command */
    spi0_transfer_byte(addr);
    spi0_transfer_byte(val);
    spi0_cs_deassert();
}

uint8_t mcp2515_read_reg(uint8_t addr) {
    spi0_cs_assert();
    spi0_transfer_byte(0x03);   /* READ command */
    spi0_transfer_byte(addr);
    uint8_t val = spi0_transfer_byte(0x00);
    spi0_cs_deassert();
    return val;
}

void mcp2515_bit_modify(uint8_t addr, uint8_t mask, uint8_t data) {
    spi0_cs_assert();
    spi0_transfer_byte(0x05);   /* BIT MODIFY command */
    spi0_transfer_byte(addr);
    spi0_transfer_byte(mask);
    spi0_transfer_byte(data);
    spi0_cs_deassert();
}

void mcp2515_init(void) {
    mcp2515_reset();

    /* Verify we are in Configuration mode (CANSTAT[7:5] = 100) */
    uint8_t canstat = mcp2515_read_reg(MCP_CANSTAT);
    if ((canstat & 0xE0) != MCP_MODE_CONFIG) {
        /* MCP2515 not responding — check SPI wiring */
        panic("MCP2515 init failed: not in config mode");
    }

    /* Configure bit timing for 250 kbit/s at 16 MHz oscillator.
       From Microchip AN754:
         BRP = 0 (TQ = 2/16MHz = 125ns)
         SJW = 0 (1 TQ)
         PropSeg = 5 (6 TQ, CNF2[2:0] = 5)
         PhaseSeg1 = 7 (8 TQ, CNF2[5:3] = 7)
         PhaseSeg2 = 5 (6 TQ, CNF3[2:0] = 5)
         Total: 1+6+8+6 = 21 TQ × 125ns = 2.625 µs → ~380 kbit/s

       For 250 kbit/s, BRP must be adjusted. Use BRP=1:
         TQ = 2*(1+1)/16MHz = 250ns
         Total: 1+6+8+6 = 21 TQ × 250ns = 5.25 µs → ~190 kbit/s (too slow)

       Standard recipe for 250 kbit/s at 16 MHz (from CAN forums):
         CNF1 = 0x41  (BRP=1, SJW=1)
         CNF2 = 0xF1  (BTLMODE=1, SAM=1, PS1=7, PRSEG=1)
         CNF3 = 0x05  (SOF=0, WAKFIL=0, PS2=5)
       Resulting: 1+2+8+6=17 TQ at 500ns = 8.5 µs → ~117 kbit/s still wrong.

       Correct values verified against TJA1050 datasheet reference:
         CNF1 = 0x01 (BRP=1: TQ=250ns, SJW=1TQ)
         CNF2 = 0xAC (BTLMODE=1, SAM=0, PHSEG1=5 → 6TQ, PRSEG=4 → 5TQ)
         CNF3 = 0x05 (PHSEG2=5 → 6TQ)
       Total TQ: 1+5+6+6=18 TQ; bit time=18×250ns=4.5µs; bitrate=222kbit/s
       Closest to 250: BRP=0 (TQ=125ns), 1+2+7+6=16TQ, 16×125ns=2µs = 500kbit/s
       BRP=0: CNF1=0x00, CNF2=0xC5, CNF3=0x04 → 500kbit/s

       Final answer for 250kbit/s with 16MHz:
         BRP = 0 (Fosc/2 = 8MHz, TQ=125ns), TQ×16 doesn't work.
         Use 8MHz oscillator: TQ=125ns, 1+3+4+2=10TQ,10×125ns×2=2.5µs = 400kbit/s
       The exact configuration depends on the oscillator actually installed on
       your MCP2515 board. Check the crystal marking. Assume 16 MHz:
         CNF1 = 0x01 (BRP=1: Fosc/4=4MHz, TQ=250ns)
         CNF2 = 0xB5 (BTLMODE=1,SAM=0,PHSEG1=6→7TQ,PRSEG=5→6TQ)
         CNF3 = 0x01 (PHSEG2=1→2TQ)
       Total: 1+6+7+2=16TQ, 16×250ns=4µs = 250kbit/s ✓
    */
    mcp2515_write_reg(MCP_CNF1, 0x01);
    mcp2515_write_reg(MCP_CNF2, 0xB5);
    mcp2515_write_reg(MCP_CNF3, 0x01);

    /* Configure RXB0 to receive all frames (mask=0, filter don't-care) */
    mcp2515_write_reg(MCP_RXB0CTRL, 0x60);  /* RXM=11: receive all */
    mcp2515_write_reg(MCP_RXB1CTRL, 0x60);  /* RXB1 also receive all */

    /* Set acceptance mask to zero (accept all IDs) */
    for (int i = 0; i < 4; i++) {
        mcp2515_write_reg(MCP_RXM0SIDH + i, 0x00);
    }

    /* Enable RX buffer 0 and 1 interrupts + error interrupt */
    mcp2515_write_reg(MCP_CANINTE, MCP_RX0IE | MCP_RX1IE | MCP_ERRIE | MCP_TX0IE);

    /* Enter Normal mode */
    mcp2515_write_reg(MCP_CANCTRL, MCP_MODE_NORMAL);

    /* Verify Normal mode (CANSTAT[7:5] = 000) */
    uint32_t timeout = 1000;
    while (timeout-- && (mcp2515_read_reg(MCP_CANSTAT) & 0xE0) != MCP_MODE_NORMAL)
        delay_us(1);
    if (timeout == 0)
        panic("MCP2515: failed to enter Normal mode");
}

The commented bit-timing calculation shows the complexity of getting the exact 250 kbit/s rate from a 16 MHz oscillator. The approach is: choose BRP and the segment lengths such that the total number of TQ per bit period equals F_osc / (2 × BRP_val × bitrate) where BRP_val = BRP + 1. Segment lengths must satisfy: PhaseSeg2 > SJW; 1 < PhaseSeg1 + PropSeg ≤ 16; SJW ≤ min(4, PhaseSeg1). These constraints come from the CAN standard and the MCP2515 register field widths.

CAN Acceptance Filters

The MCP2515 provides six acceptance filters (RXF0–RXF5) and two acceptance masks (RXM0, RXM1). Each received CAN frame’s identifier is compared against the filters using the mask:

If the comparison succeeds, the frame is accepted into the corresponding receive buffer. If no filter matches, the frame is discarded silently.

For the Märklin system, the CS3 sends back acknowledgement frames with the same command code as the original command but with the response bit (bit 16 of the extended identifier) set. If your kernel wants to receive only sensor events (command 0x10/0x11) and system status messages, you configure filters to match only those IDs:

void mcp2515_set_filter_for_sensor_events(void) {
    /* Sensor event (S88) command code = 0x10, shifted to extended ID bits [28:17] */
    /* Extended ID for sensor event: (0x10 << 17) = 0x00200000 */
    /* Encode in SIDH, SIDL, EID8, EID0 format */
    uint32_t filter_id = (0x10 << 17);  /* S88 event command */

    uint8_t sidh = (filter_id >> 21) & 0xFF;
    uint8_t sidl = ((filter_id >> 13) & 0xE0) | 0x08 | ((filter_id >> 16) & 0x03);
    uint8_t eid8 = (filter_id >> 8) & 0xFF;
    uint8_t eid0 = (filter_id) & 0xFF;

    /* Write filter 0 (for RXB0) */
    mcp2515_write_reg(MCP_RXF0SIDH, sidh);
    mcp2515_write_reg(MCP_RXF0SIDH + 1, sidl);
    mcp2515_write_reg(MCP_RXF0SIDH + 2, eid8);
    mcp2515_write_reg(MCP_RXF0SIDH + 3, eid0);

    /* Set mask to match only the command bits (bits [28:17]) */
    uint32_t mask_id = (0xFFF << 17);   /* 12-bit command field mask */
    mcp2515_write_reg(MCP_RXM0SIDH,     (mask_id >> 21) & 0xFF);
    mcp2515_write_reg(MCP_RXM0SIDH + 1, ((mask_id >> 13) & 0xE0) | 0x08);
    mcp2515_write_reg(MCP_RXM0SIDH + 2, (mask_id >> 8) & 0xFF);
    mcp2515_write_reg(MCP_RXM0SIDH + 3, mask_id & 0xFF);
}

In practice, for CS 452, it is simpler to configure the MCP2515 to receive all frames (mask = 0x000, filter = 0x000) and filter in software — the message rate is low enough that the software filtering overhead is negligible. Hardware filtering would be important at high CAN bus utilization (hundreds of nodes, high message rates) to prevent the kernel from being interrupted for every bus message.

GPIO Pin Multiplexing for SPI and CAN

The RPi 4’s GPIO pins are multiplexed — each pin can serve one of several functions, selected by writing to the GPIO Function Select registers (GPFSELn at 0xFE200000–0xFE20000C). For SPI0, the relevant pins are:

For the MCP2515 INT pin (interrupt output), any GPIO in input mode with falling-edge detect enabled can be used. GPIO 17 (physical pin 11) is a common choice:

void gpio_init_spi_and_can(void) {
    volatile uint32_t *GPFSEL0 = (uint32_t *)0xFE200000;
    volatile uint32_t *GPFSEL1 = (uint32_t *)0xFE200004;
    volatile uint32_t *GPREN0  = (uint32_t *)0xFE20004C;  /* rising edge detect */
    volatile uint32_t *GPFEN0  = (uint32_t *)0xFE200058;  /* falling edge detect */

    /* GPIO 8–11: Alt0 for SPI0 */
    uint32_t fsel1 = *GPFSEL0;
    fsel1 = (fsel1 & ~(7 << 24)) | (4 << 24);  /* GPIO8: Alt0 */
    fsel1 = (fsel1 & ~(7 << 27)) | (4 << 27);  /* GPIO9: Alt0 */
    *GPFSEL0 = fsel1;

    uint32_t fsel2 = *GPFSEL1;
    fsel2 = (fsel2 & ~(7 << 0))  | (4 << 0);   /* GPIO10: Alt0 */
    fsel2 = (fsel2 & ~(7 << 3))  | (4 << 3);   /* GPIO11: Alt0 */
    fsel2 = (fsel2 & ~(7 << 21)) | (0 << 21);  /* GPIO17: Input */
    *GPFSEL1 = fsel2;

    /* Enable falling-edge detect on GPIO17 (MCP2515 INT, active low) */
    *GPFEN0 |= (1 << 17);
}

The GPIO event detect registers (GPFEN0 for falling edge, GPREN0 for rising edge, GPLEV0 for current level) work by latching the detected event in GPEDS0 (event detect status). The kernel’s interrupt handler reads GPEDS0 to identify which GPIO triggered, then writes 1 to the corresponding GPEDS0 bit to clear the event.

Chapter 7: The Märklin Protocol over CAN

The Märklin Digital system uses a proprietary extension of CAN for communication between the Central Station (CS2 or CS3) and accessories, sensors, and other control nodes. Understanding this protocol is necessary for writing the train control layer — it defines every command that can move a locomotive, change a switch, or query a sensor.

The CS3 Architecture

The Märklin CS3 (Central Station 3) is the master controller on the CAN bus. It:

• Maintains a list of active locomotives — any loco that has received a speed or direction command recently. The CS3 periodically cycles through this list to refresh commands, since Märklin locomotives use a DCC or Motorola protocol with watchdog-like semantics: a loco that stops receiving commands will eventually reset to stop.
• Controls track power and turnout switches directly.
• Relays commands from the CAN bus to the track using its internal DCC/Motorola encoder.
• Reports sensor events from S88 sensor modules.

The CS3 sits between the CAN bus and the track. Your kernel sends commands to the CS3 over CAN; the CS3 executes them on the track. This two-hop architecture means that CAN message latency is not the only source of control delay — the CS3’s internal scheduling adds additional latency that must be accounted for in timing models.

MCP2515 Registers and SPI Interface

The MCP2515 (Microchip Technology) is a standalone CAN 2.0B controller that interfaces to any microprocessor via SPI. It handles all CAN framing, arbitration, error detection, and recovery in hardware, presenting a simple mailbox interface to the host.

The MCP2515 provides three transmit buffers (TXB0, TXB1, TXB2) and two receive buffers (RXB0, RXB1). Each buffer contains registers for the extended identifier, DLC (data length code), and up to 8 data bytes. Transmission is initiated by writing to the buffer and setting the TXREQ bit in TXBnCTRL. Reception is signalled by an interrupt flag in CANINTF.

SPI commands for the MCP2515:

Initialization sequence: RESET, wait 128 µs (oscillator start-up), write CNF1/CNF2/CNF3 for 250 kbit/s bit timing, write CANCTRL to enter Normal mode, write CANINTE to enable RX interrupts, configure acceptance filters.

A complete SPI transaction to send a CAN frame:

// assert CS (GPIO output low)
// SPI WRITE: load TXB0 starting at TXBnSIDH
spi_byte(0x02);             // WRITE command
spi_byte(0x31);             // TXB0SIDH address
spi_byte((id >> 21) & 0xFF); // SIDH: standard ID bits [10:3]
spi_byte(((id >> 13) & 0xE0) | 0x08 | ((id >> 16) & 0x03)); // SIDL + EXIDE=1
spi_byte((id >> 8) & 0xFF); // EID8
spi_byte(id & 0xFF);        // EID0
spi_byte(len & 0x0F);       // DLC
for (int i = 0; i < len; i++) spi_byte(data[i]);
// deassert CS
// assert CS
spi_byte(0x81);             // REQUEST TO SEND TXB0
// deassert CS

Märklin Command Codes

The Märklin CAN protocol uses the 29-bit extended identifier to encode command type, response flag, and hash. The high 9 bits of the identifier encode the command (Befehl); the remaining 20 bits encode a hash derived from the UID of the command originator.

Key command codes:

For speed control, the speed argument ranges from 0 (stop) to 1000 (maximum). The mapping from speed level to actual locomotive velocity is highly non-linear and varies by locomotive model, decoder type, and motor characteristics. This non-linearity is precisely what the velocity calibration procedure in Chapter 17 measures and models.

Switch control (0x0B) requires specifying the turnout’s UID and the desired position (0 = straight/through, 1 = diverging). The CS3 briefly activates the solenoid coil to move the switch, then cuts power to prevent coil burnout. A critical operational note: double slips (double-crossover switches with four positions) should never be commanded to invalid states (both curved positions simultaneously) as this can mechanically damage the mechanism.

The CS3 active locomotive list is a practical constraint that affects software design. The CS3 accepts speed commands only for locomotives that it considers “active” — meaning they have been acknowledged by the CS3. Before sending speed commands to a locomotive, you must issue a Go command (system command 0x00) to activate the loco on the CS3. More subtly, the CS3 cycles through its active list and periodically re-sends speed commands; a loco you commanded to speed 500 will gradually slow if the CS3 removes it from its active list. Your kernel must either keep locos active through periodic commands or explicitly manage CS3 loco registration.

The S88 sensor modules report reed-switch contacts to the CS3, which forwards events over CAN. A sensor event message contains the module number and the contact number within the module. The CS3 polls S88 modules at a configurable rate; the maximum poll rate determines the sensor latency. At 250 kbit/s CAN with 16 contacts per S88 module, polling 8 modules takes approximately 1–2 ms.

Märklin CAN Message Format

A complete Märklin CAN message consists of the 29-bit extended identifier plus up to 8 data bytes. The extended identifier encodes:

The command field encodes what type of message this is. Values above 0x00 are defined by the Märklin protocol; the response flag is set by the CS3 when it is responding to a command (as opposed to initiating one). The hash is a 16-bit value derived from the originator’s UID, ensuring that messages from different devices have different identifiers and CAN arbitration works correctly.

For a speed command (command 0x04), the data bytes are:

The locomotive UID is a 32-bit identifier assigned to each Märklin locomotive decoder. It is printed on the underside of the locomotive or can be read from the CS3’s locomotive database. The CS3 uses the UID to identify which decoder should act on the command.

A complete speed command to locomotive UID 0x00000042 at speed 500 forward:

typedef struct {
    uint8_t data[8];
    uint8_t len;
} MarklnData;

void build_speed_cmd(MarklnData *d, uint32_t uid, uint16_t speed, uint8_t dir) {
    d->data[0] = (uid >> 24) & 0xFF;
    d->data[1] = (uid >> 16) & 0xFF;
    d->data[2] = (uid >>  8) & 0xFF;
    d->data[3] = (uid >>  0) & 0xFF;
    d->data[4] = (speed >> 8) & 0xFF;
    d->data[5] = (speed >> 0) & 0xFF;
    d->data[6] = dir;
    d->data[7] = 0;
    d->len = 8;
}

void send_markln_cmd(uint8_t command, MarklnData *d, uint32_t my_hash) {
    uint32_t can_id = ((uint32_t)command << 17) | (my_hash & 0xFFFF);
    // Build CAN frame with extended identifier can_id and data d->data[0..d->len-1]
    can_tx_frame(can_id, d->data, d->len);
}

Locomotive Decoder Types

Märklin locomotives use several DCC/Motorola decoder variants, which affects the speed step resolution and the locomotive behavior:

14-step decoders (older Märklin Motorola format): 14 discrete speed steps plus stop. Speed 0 = stop; steps 1–14 map to increasing speeds. The CS3 maps these to the 0–1000 range: step n → speed = n × 71 (approximately). The coarse speed granularity makes smooth speed ramping impossible — only 14 distinct velocities are achievable.

28-step decoders (DCC): 28 discrete speed steps plus stop. More resolution than 14-step. Many modern Märklin locomotives use 28-step DCC decoders.

128-step decoders (DCC with extended speed steps): 128 speed steps, giving fine-grained control. Modern high-quality decoders support 128 steps. The CS3 maps the 0–1000 software range to the decoder’s step count transparently.

The type of decoder in each locomotive must be determined experimentally: set the speed to a low value and observe whether the locomotive moves, or use the CS3’s built-in decoder identification function. The calibration procedure (Chapter 17) produces a velocity table that is correct regardless of decoder type, because it measures actual physical velocity rather than relying on the decoder specification.

Emergency Stop and Safety

The Märklin system command 0x00 with subcommand 0x00 is a broadcast emergency stop: all locomotives stop immediately, all switch commands are cancelled, and the CS3 cuts track power. This is the safety command that the train control application should issue when any safety invariant is violated — two trains predicted to occupy the same segment, a sensor firing with no plausible attribution, or a kernel assertion failure.

Implementing an emergency stop involves:

1. Sending the broadcast stop CAN frame.
2. Waiting for the CS3 to acknowledge (or timing out).
3. Marking all trains as stopped in the track server state.
4. Blocking all subsequent speed commands until the operator manually resumes.

The emergency stop should be callable from any task, including interrupt handlers, through a dedicated “kill switch” mechanism that bypasses the normal SRR queue. One approach: a dedicated emergency-stop task at the highest priority, started at boot, that parks itself in a Receive loop. Any task that detects a safety violation calls Send to the emergency-stop task; the emergency-stop task wakes, issues the stop command, and blocks until an operator presses the resume key.

The Track Layout Data Format

The CS 452 course distributes a track graph data structure representing the specific Märklin track set available in the lab. The format is a C array of TrackNode structs, where each node represents a track section endpoint. The connectivity is specified as directed edges — each node has up to two “next” nodes (one for each direction of travel, or two for a switch).

Two track layouts are available (track A and track B), with different topologies. Track A is a figure-8 with four sidings; track B has a more complex structure with a central loop and multiple branch lines. Students choose which layout to demonstrate on. The track data array is handed out rather than having students measure it themselves, to ensure consistency and save time.

The key invariant of the track data: every edge has a corresponding reverse edge. If node 27 has a “next” to node 28 with distance 150 mm, then node 28 has a “next” to node 27 (traveling in the opposite direction) with the same distance. This reversibility property ensures that Dijkstra’s algorithm can find paths in either direction along any segment.

The DCC Protocol: What the CS3 Does on the Track

The CS3 sits between your CAN commands and the trains. When you send a Märklin CAN speed command, the CS3 translates it into a DCC (Digital Command Control) packet and transmits it to the track. Understanding DCC demystifies why commands sometimes have unexpected effects and why the CS3 introduces additional latency beyond CAN communication time.

DCC is an NMRA-standardized digital protocol (NMRA Standard S-9.1) for controlling model trains. The track carries both power (approximately 15–18 V AC-like) and data simultaneously. The data is encoded as a bit stream modulated onto the power waveform: a long half-cycle (58 µs per half) encodes a 0 bit; a short half-cycle (29 µs per half) encodes a 1 bit. The track voltage oscillates continuously; the duration of each half-cycle determines the bit value. Locomotives with DCC decoders extract both power and data from the track signal.

A DCC packet consists of:

1. A preamble of at least 14 consecutive 1 bits.
2. A 0 start bit introducing the address byte.
3. An address byte (1 byte for short addresses 1–127, 2 bytes for long addresses 128–9999).
4. A 0 start bit introducing the data byte.
5. One or more data bytes (instruction type and value).
6. A 0 start bit introducing the error correction byte.
7. An error check byte (XOR of all preceding bytes).
8. A 1 end bit completing the packet.

A complete DCC speed-and-direction packet to locomotive address 42, speed step 14 (of 28), forward direction:

Preamble: 1 1 1 1 1 1 1 1 1 1 1 1 1 1   (14 ones)
Start:    0
Address:  0 0 1 0 1 0 1 0               (0x2A = decimal 42)
Start:    0
Data:     0 1 1 0 1 1 1 0               (direction+speed: 0b01101110)
Start:    0
CRC:      0 1 0 0 0 1 0 0               (0x2A XOR 0x6E = 0x44)
End:      1

The data byte for speed is encoded as 01DSSSS for 28-step mode (where D = direction, SSSS = speed steps 0–28). The full DCC speed byte encoding includes a half-bit for the highest speed bit, making the encoding non-obvious at first glance.

The CS3 generates these packets continuously for all “active” locomotives in its roster. A locomotive that has not received a DCC packet within a manufacturer-specific timeout will reset to speed 0 (the DCC “emergency stop” behavior). This is the watchdog mechanism mentioned in Chapter 7: the CS3 must continuously re-send commands to keep locomotives at their commanded speed. If the CAN bus to the CS3 is disrupted (the RPi 4 crashes or reboots), the CS3 will stop receiving speed commands from your kernel, but it will continue sending the last-commanded speed to the track until the locomotive’s decoder resets. This provides a brief “fail-safe” period, but ultimately the locomotive will stop.

DCC packet timing: at 1-bit duration of 58 µs (half-cycle) and a 14-bit preamble, one DCC packet takes approximately 14×116 µs (preamble) + 8×(2×116 µs) (address byte) + 8×(2×116 µs) (data byte) + 8×(2×116 µs) (CRC byte) + overhead ≈ 10 ms. The CS3 cycles through all active locomotives at this rate; with 5 active locomotives, the refresh rate per locomotive is approximately 50 ms. This means a speed command update takes up to 50 ms to take effect on the track, independent of CAN latency. This is the dominant delay in the train control critical path and explains why stopping distances are not sub-centimeter.

Motorola protocol: older Märklin locomotives use the proprietary Märklin/Motorola digital protocol rather than DCC. The Motorola protocol predates NMRA DCC standardization and is not interoperable. The CS3 supports both; it determines which protocol to use based on the locomotive decoder type registered in its database. The key difference from a software perspective: Motorola locomotives have 14 speed steps compared to DCC’s 28 or 128, and the protocol lacks some DCC features (no multi-function decoders with function outputs, no long addresses). The CS3 handles this transparently — your kernel always speaks the Märklin CAN protocol, and the CS3 chooses Motorola or DCC as appropriate.

CAN Bus Physical Layer and Error Handling

The MCP2515 speaks CAN 2.0B, which specifies a physical layer based on differential signaling over a twisted-pair bus. Understanding the physical layer matters because the train lab is a noisy electrical environment — locomotive motor brushes generate RF interference, and track power creates magnetic fields that can couple into the CAN cable.

Differential signaling: the CAN bus has two wires, CAN_H (high) and CAN_L (low). A recessive bit is signalled when both wires are at the same voltage (approximately 2.5 V each, differential = 0 V). A dominant bit is signalled when CAN_H is driven to approximately 3.5 V and CAN_L to approximately 1.5 V (differential = 2 V). Any node on the bus can force the bus dominant by driving CAN_H and CAN_L; a dominant state overrides a recessive state. This property is the basis of CAN arbitration.

Bit stuffing: to maintain synchronization between nodes, CAN uses bit stuffing: after 5 consecutive bits of the same polarity in the data stream, the transmitter inserts a bit of the opposite polarity. The receiver removes these stuffed bits. Bit stuffing limits run-length to 5 and ensures the receiver can re-synchronize its clock. A stuff error occurs when more than 5 consecutive identical bits are seen (indicating either a corrupted frame or a line fault).

CAN frame structure (standard frame, extended ID used by Märklin):

Start-of-Frame (SOF): 1 dominant bit
Extended identifier: 29 bits (11-bit base ID + substitute remote request + IDE + 18-bit extension)
Remote Transmission Request (RTR): 1 bit
Reserved bits: 2 bits (EDL=0, res=0 for CAN 2.0)
Data Length Code (DLC): 4 bits (0-8 data bytes)
Data Field: 0-64 bits (0-8 bytes)
CRC Field: 15 bits + 1 CRC delimiter bit
ACK Field: 1 bit + 1 delimiter (receiver drives ACK dominant to acknowledge receipt)
End-of-Frame (EOF): 7 recessive bits
Intermission Frame Space (IFS): 3 recessive bits

Arbitration: when two nodes transmit simultaneously, each node monitors the bus state while transmitting. A node that has transmitted a recessive bit but detects a dominant bit on the bus knows it has been overridden by another node with a lower-ID (higher-priority) frame. It immediately stops transmitting and waits for the bus to be idle before retrying. This mechanism (bit-wise arbitration) ensures that the lowest-numbered CAN ID always wins, without any explicit collision detection or retry protocol. Märklin uses the command field in the extended ID for priority: system commands (0x00) have higher CAN priority than speed commands (0x04), which have higher priority than sensor poll commands (0x11).

Error detection: CAN has five error detection mechanisms:

1. Bit monitoring: a transmitting node monitors its own bits; if the received bit differs from the transmitted bit (outside of the arbitration phase for dominant bits), it is a bit error.
2. Bit stuffing: a violation of the 5-bit limit is a stuff error.
3. CRC check: the receiver independently computes the CRC and compares it to the transmitted CRC.
4. Form check: the fixed-format fields (EOF, IFS, ACK delimiter, CRC delimiter) must have specific values.
5. Acknowledgement check: if no node acknowledges (no dominant ACK bit), the transmitter detects an acknowledgement error.

When an error is detected, the detecting node transmits an error flag: 6 dominant bits (violating the bit-stuffing rule, which forces all other nodes to also generate error flags). After the error flag, the bus returns to idle and the transmitter retries.

Error counters: the MCP2515 maintains two error counters, TEC (Transmit Error Counter) and REC (Receive Error Counter). Each transmitted error flag increments TEC by 8; each received error flag increments REC by 1; each successful transmission or reception decrements the counter by 1. The counters drive a state machine:

Bus-off recovery: when TEC exceeds 255, the MCP2515 enters Bus-Off mode and stops participating on the bus. To recover, the software must write the appropriate control bits to CANCTRL to initiate recovery. Recovery requires 128 occurrences of 11 consecutive recessive bits (the “error delimiter + IFS” sequence), which at 250 kbit/s takes approximately 128 × 11 × 4 µs = 5.6 ms.

void can_recover_bus_off(void) {
    uint8_t canctrl = mcp2515_read_reg(MCP_CANCTRL);
    if ((canctrl & 0xE0) == MCP_MODE_CONFIG) {
        /* Already in config mode (bus-off) — request recovery */
        mcp2515_write_reg(MCP_CANCTRL, MCP_MODE_NORMAL);
    }
    /* Poll until normal mode is confirmed */
    uint32_t timeout = 10000;   /* ~10 ms at 1 µs per iteration */
    while (--timeout) {
        uint8_t stat = mcp2515_read_reg(MCP_CANSTAT);
        if ((stat & 0xE0) == MCP_MODE_NORMAL) return;
        delay_us(1);
    }
    /* Timeout: serious hardware fault */
    kernel_panic("MCP2515: bus-off recovery timeout");
}

The CAN RX server should include a periodic check of the MCP2515’s error counters:

void can_rx_server_error_check(void) {
    uint8_t tec = mcp2515_read_reg(MCP_TEC);
    uint8_t rec = mcp2515_read_reg(MCP_REC);
    uint8_t eflg = mcp2515_read_reg(MCP_EFLG);

    if (eflg & MCP_EFLG_TXBO) {
        /* Bus-off — attempt recovery */
        can_recover_bus_off();
    } else if (eflg & MCP_EFLG_TXEP || eflg & MCP_EFLG_RXEP) {
        /* Error passive — log warning, monitor */
        log_event(LOG_CAN_ERROR_PASSIVE, (tec << 8) | rec);
    }
}

A robust production CAN driver calls this check after every received message and periodically from the clock server. In the lab, noise-induced errors are rare but not impossible; having the diagnostic path in place means the first sign of trouble produces a useful log entry rather than silent misbehavior.

CS3 Initialization and the Active Locomotive Protocol

The CS3 must be explicitly started before it will relay commands to the track. This is done through the Go command (Märklin system command 0x00, subcommand 0x01). The initialization sequence from your kernel is:

1. Send the Stop command (system 0x00, subcommand 0x00) to ensure the track is off at startup.
2. Wait approximately 500 ms for the CS3 to power up if it was just connected.
3. Send the Go command (system 0x00, subcommand 0x01) to enable track power.
4. For each locomotive you intend to control: send a speed 0 command to register it on the CS3’s active list.
5. Verify the CS3 responded with an acknowledgement (command 0x00, response flag set).

void cs3_initialize(void) {
    MarklnData d;
    /* Stop command: data = [subcommand=0, UID=0 (broadcast)] */
    memset(&d, 0, sizeof(d));
    d.data[4] = 0x00;   /* subcommand: stop */
    d.len = 5;
    send_markln_cmd(0x00, &d, MY_HASH);

    /* Wait for CS3 to stabilize */
    Delay(clock_tid, 50);  /* 500 ms at 10 ms/tick */

    /* Go command: subcommand = 0x01 */
    d.data[4] = 0x01;
    send_markln_cmd(0x00, &d, MY_HASH);
}

void cs3_register_loco(uint32_t uid) {
    MarklnData d;
    /* Speed 0, forward — this registers the loco on the CS3 active list */
    build_speed_cmd(&d, uid, 0, 1);
    send_markln_cmd(0x04, &d, MY_HASH);
}

After cs3_initialize() and cs3_register_loco() for each locomotive, the CS3 will forward subsequent speed and switch commands to the track. The “active list” registration must be repeated if the CS3 is power-cycled, if the CAN bus drops and reconnects, or if the CS3 does not receive a speed command for an extended period (typically 60–120 seconds, depending on CS3 firmware version).

Part III: A Microkernel from Scratch

Chapter 8: Tasks and the Static-Priority FIFO Scheduler

The central abstraction of this kernel is the task: an independent sequential computation with its own stack, its own program counter, and its own priority. Tasks are the unit of scheduling, the unit of communication, and the unit of resource isolation. Understanding what a task is, how it is represented in memory, and how the scheduler selects among ready tasks is the prerequisite for understanding every other kernel mechanism.

Why Tasks?

Chapter 2 argued that a polling loop cannot achieve bounded response latency when event rates are heterogeneous. The task abstraction resolves this by separating what to compute from when to compute it. Each logically distinct activity — processing a sensor event, updating the clock, servicing a UART receive request — becomes a task. The kernel continuously runs the highest-priority ready task, preempting it when a higher-priority task becomes ready. This ensures that the most urgent work always executes first, regardless of what other work is pending.

The analogy to hardware interrupt priority is deliberate. When the GIC delivers an IRQ, the processor drops whatever it was executing and handles the interrupt, then resumes the preempted computation. Tasks extend this priority-driven preemption into software, allowing arbitrarily many priority levels and complex interactions among them.

Task Descriptors

Each task is represented by a task descriptor (TD), a data structure that the kernel uses to track everything it needs to know about the task. The minimum fields are:

typedef struct TaskDescriptor {
    int       tid;             // unique task identifier
    int       parent_tid;     // tid of the creating task
    int       priority;       // static priority (higher value = higher priority)
    RunState  state;          // current run state (Active, Ready, SendWait, etc.)
    uint64_t  sp;             // saved stack pointer (when not running)
    struct TaskDescriptor *send_queue; // head of senders waiting for Receive
    struct TaskDescriptor *send_next;  // next task in a send queue
    struct TaskDescriptor *reply_target; // task waiting for our Reply
} TaskDescriptor;

The sp field is crucial: when a task is not running, its stack pointer is stored here. The task’s registers — the full register file plus ELR_EL1 and SPSR_EL1 — are saved on the task’s own user stack. To resume a task, the kernel loads sp, pops the saved context, and executes eret.

Task descriptors are allocated from a static pool. The maximum number of simultaneous tasks is a compile-time constant (typically 64 for CS 452). There is no dynamic allocation.

Run States

A task is always in exactly one of seven states:

These states form a directed graph. A task transitions between them only through explicit kernel operations — system calls and interrupt delivery — never spontaneously. This determinism is what allows the kernel to make scheduling decisions with bounded cost.

The Ready Queue

The scheduler selects the highest-priority Ready task. The data structure must support two operations efficiently: inserting a newly-Ready task, and extracting the highest-priority task. Priority queues implemented as heaps would give O(log n) for both; however, the kernel uses a simpler structure that gives O(1) for both operations: an array of FIFO queues, one per priority level.

#define MAX_PRIORITY 16
#define MAX_TASKS    64

typedef struct {
    TaskDescriptor *head, *tail;
} ReadyQueue;

static ReadyQueue ready[MAX_PRIORITY];
static int        highest_ready = -1;  // cached highest non-empty priority

void scheduler_insert(TaskDescriptor *td) {
    int p = td->priority;
    if (ready[p].tail) {
        ready[p].tail->send_next = td;
    } else {
        ready[p].head = td;
    }
    ready[p].tail = td;
    td->send_next = NULL;
    if (p > highest_ready) highest_ready = p;
}

TaskDescriptor *scheduler_next(void) {
    while (highest_ready >= 0 && !ready[highest_ready].head)
        highest_ready--;
    if (highest_ready < 0) return NULL;  // no ready tasks (idle)
    TaskDescriptor *td = ready[highest_ready].head;
    ready[highest_ready].head = td->send_next;
    if (!ready[highest_ready].head) ready[highest_ready].tail = NULL;
    return td;
}

Within a priority level, tasks are scheduled FIFO — the task that became Ready earliest runs first. There is no time-slicing: once a task starts running, it continues until it makes a system call (which may yield the CPU, block, or explicitly defer). This is a key design choice. Time-slicing adds unpredictability: a task that is preempted mid-computation has a longer worst-case response time. By using cooperative scheduling within a priority level, combined with the discipline that server tasks never block indefinitely, the kernel keeps worst-case latency tractable.

Comparison: Linux’s Completely Fair Scheduler (CFS) and its successor EEVDF use virtual runtime accounting to achieve fair CPU sharing among equal-priority threads, at the cost of O(log n) scheduling operations and cache-unfriendly data structures. The RT scheduler in Linux (SCHED_FIFO, SCHED_RR) more closely resembles the CS 452 kernel, but it supports preemption within the kernel itself, adds preemption points throughout the kernel, and must handle many more corner cases for a general-purpose system.

Creating and Destroying Tasks

Create(int priority, void (*function)(void)) allocates a task descriptor from the pool, initializes the task’s stack with a startup frame, and inserts it into the Ready queue at the given priority. The return value is the new task’s TID (a positive integer), -1 if the priority is invalid, or -2 if the descriptor pool is exhausted.

Stack initialization is subtle. When the task is first scheduled, the kernel’s context switch code will pop the saved context frame and execute eret. The “saved” context for a new task must be carefully crafted so that eret jumps to task_start, which calls the task’s function. A helper wrapper handles the case where the task function returns:

void task_start(void (*function)(void)) {
    function();
    Exit();        // if task returns, clean up automatically
}

Without the Exit() call at the end, a returning task function would execute whatever is on the stack below its frame — undefined behaviour with potentially catastrophic consequences on bare metal.

Exit() marks the task as Exited, removes it from all queues, and returns its descriptor to the free pool. The kernel immediately reschedules after Exit().

Yield() moves the calling task to the end of its priority queue. This is a cooperative-scheduling primitive: a task that wants to give other same-priority tasks a chance can yield. It has no effect in a system with only one task at each priority level. The kernel handles Yield() by treating it as a degenerate scheduler entry: the current task is re-inserted at the tail of its queue, and the scheduler selects the next task.

Priority Assignment Strategy

Choosing task priorities is an engineering decision that directly determines the system’s real-time behavior. The general principle is: assign higher priority to tasks with tighter deadlines and smaller execution times. This is precisely the Rate Monotonic principle from Chapter 15, applied to the software task set.

For the CS 452 train control application, a typical priority assignment (from highest to lowest):

The notifiers are at the top because they execute AwaitEvent immediately after an interrupt fires and must begin executing before another interrupt can arrive. The clock notifier at priority 31 means that even while a train engineer task is computing a route, the clock tick is processed within one scheduling decision.

The idle task at priority 0 is special: it must exist and must run when no other task is ready, but it should never prevent useful work from executing. Assigning it priority 0 (or the minimum defined priority) ensures this.

A critical discipline: do not assign two tasks the same priority unless they truly have the same timing requirements and both are acceptable as candidates for indefinite deferral in favour of the other. Within a priority level, the scheduler is FIFO, not preemptive — one task at a given priority level cannot preempt another at the same level. If a high-priority task has a long execution time, it prevents a same-priority task from running until it yields or blocks, which may cause deadline violations.

Task Creation and the First Task

The kernel’s initial user task — the first task — is created by the kernel itself before transferring control to EL0. The first task is responsible for creating all other initial tasks (servers, notifiers) and then exiting or becoming the user shell. A typical first task:

void first_task(void) {
    // Create infrastructure servers
    Create(25, clock_server_main);
    Create(31, clock_notifier_main);
    Create(24, can_rx_server_main);
    Create(30, can_rx_notifier_main);
    Create(23, uart_rx_server_main);
    Create(29, uart_rx_notifier_main);
    Create(23, uart_tx_server_main);
    Create(28, uart_tx_notifier_main);
    Create(10, name_server_main);

    // Wait for servers to register before creating application tasks
    Delay(WhoIs("ClockServer"), 10);  // 100ms stabilization

    // Create application tasks
    Create(20, train_engineer_main);
    Create(15, route_planner_main);
    Create(1, user_shell_main);

    Exit();
}

The first task runs at a temporary priority. Since it creates servers at various priorities, some of those servers will immediately preempt the first task if their priority is higher. This is correct behaviour — the high-priority notifiers should start calling AwaitEvent immediately so they are ready to handle the first interrupt.

The Full Task Descriptor Layout

The minimal task descriptor shown earlier suffices for describing the concept, but a production-quality implementation requires additional fields. Here is a more complete descriptor that handles all the states and metadata needed by the full SRR system:

#define MAX_PRIORITY   32
#define MAX_TASKS      64
#define TASK_STACK_SZ  (8 * 1024)   /* 8 KB per task */

typedef enum {
    STATE_FREE        = 0,  /* descriptor is not in use (available for Create) */
    STATE_ACTIVE      = 1,  /* currently executing on the CPU */
    STATE_READY       = 2,  /* eligible to run, waiting in ready queue */
    STATE_SEND_WAIT   = 3,  /* blocked in Send(), waiting for receiver */
    STATE_RECV_WAIT   = 4,  /* blocked in Receive(), waiting for sender */
    STATE_REPLY_WAIT  = 5,  /* blocked after Send(), waiting for Reply() */
    STATE_EVENT_WAIT  = 6,  /* blocked in AwaitEvent(), waiting for interrupt */
    STATE_EXITED      = 7,  /* exited; descriptor may be reclaimed */
} TaskState;

typedef struct TaskDescriptor {
    /* Identity */
    int              tid;           /* unique task ID; never 0 */
    int              parent_tid;    /* TID of the task that called Create() */
    int              priority;      /* 0 (lowest) to MAX_PRIORITY-1 (highest) */

    /* Scheduling */
    TaskState        state;
    uint64_t         sp;            /* saved EL0 stack pointer when not running */

    /* SRR: Send queue (when this TD is a Receive target) */
    struct TaskDescriptor *send_queue_head;
    struct TaskDescriptor *send_queue_tail;

    /* SRR: intrusive list link (when this TD is in a send queue) */
    struct TaskDescriptor *send_next;

    /* SRR: message buffers (set during Send/Receive pairing) */
    const void      *send_buf;      /* sender's message buffer */
    int              send_len;      /* sender's message length */
    void            *recv_buf;      /* receiver's buffer for message */
    int              recv_cap;      /* receiver's buffer capacity */
    void            *reply_buf;     /* sender's reply buffer */
    int              reply_cap;     /* sender's reply buffer capacity */

    /* SRR: return values */
    int              retval;        /* return value of syscall (Receive, Send, AwaitEvent) */

    /* AwaitEvent: which event this task is waiting for */
    int              event_id;      /* filled on entry to AwaitEvent */

    /* Scheduler: intrusive link in ready queue */
    struct TaskDescriptor *ready_next;

    /* Stack canary for overflow detection */
    uint32_t         stack_canary;  /* must always equal CANARY_VALUE */
} TaskDescriptor;

#define CANARY_VALUE 0xDEADBEEF

The canary field is placed at the bottom of the task descriptor (which is contiguous with the task’s stack in memory). If the task’s stack overflows downward into the descriptor, the canary is overwritten. A periodic kernel health check compares td->stack_canary against CANARY_VALUE for all active tasks; a mismatch triggers an emergency stop.

Memory layout: the kernel allocates task stacks statically:

/* Static allocation: descriptors and stacks together */
static TaskDescriptor task_pool[MAX_TASKS];
static uint8_t        task_stacks[MAX_TASKS][TASK_STACK_SZ];

The stack for task_pool[i] is task_stacks[i]. The user task’s stack pointer starts at the top of its stack: (uint64_t)task_stacks[i] + TASK_STACK_SZ. The stack grows downward as the task pushes data (function arguments, local variables, saved registers).

Placing the stack canary at the bottom of the descriptor (i.e., adjacent to where the stack would overflow into the descriptor) requires that the descriptor and stack are adjacent in memory. One approach: allocate them as a single struct { TaskDescriptor td; uint8_t stack[STACK_SZ]; }, then the stack overflows downward into the descriptor. Another approach: allocate stacks below their corresponding descriptors in memory. The canary approach detects overflows on the current check; it does not prevent the overflow from causing damage before the check runs. For guaranteed safety, a memory protection unit (MPU) or the MMU’s page-level protection would be needed.

Task Descriptor Pool Management

The free list of task descriptors:

static TaskDescriptor *free_list_head = NULL;

void td_pool_init(void) {
    for (int i = MAX_TASKS - 1; i >= 0; i--) {
        task_pool[i].state    = STATE_FREE;
        task_pool[i].tid      = -1;
        task_pool[i].send_next = free_list_head;
        free_list_head         = &task_pool[i];
    }
}

TaskDescriptor *td_alloc(void) {
    if (!free_list_head) return NULL;
    TaskDescriptor *td = free_list_head;
    free_list_head     = td->send_next;
    td->send_next      = NULL;
    return td;
}

void td_free(TaskDescriptor *td) {
    td->state    = STATE_FREE;
    td->tid      = -1;
    td->send_next = free_list_head;
    free_list_head = td;
}

The free list reuses the send_next field (which is not needed by a free descriptor) for list linkage — a common C trick to avoid adding a field that is only used in one state.

TID assignment: TIDs should be globally unique across the lifetime of the system, not just unique among currently-active tasks. If TIDs were reused immediately, a task that holds a stale TID (from a previous occupant of a descriptor) could accidentally send to the wrong task. The solution: use a monotonically increasing TID counter.

static int next_tid = 1;  /* 0 is reserved for the idle task */

TaskDescriptor *create_task(int priority, void (*fn)(void)) {
    TaskDescriptor *td = td_alloc();
    if (!td) return NULL;
    td->tid       = next_tid++;
    td->priority  = priority;
    td->state     = STATE_READY;
    td->stack_canary = CANARY_VALUE;
    init_task_stack(td, fn);
    scheduler_insert(td);
    return td;
}

With 64 task descriptors and a 32-bit TID counter, TIDs will never wrap in a CS 452 session (even creating a new task every millisecond for a full 4-hour session uses only 14,400 TIDs, far below \(2^{31}\)).

The Receive Queue and Priority Within the Server

Within the send queue of a server (the queue of SendWait tasks waiting for the server to Receive), tasks are ordered FIFO by default. This means a high-priority client that arrives after a low-priority client will wait behind the low-priority client. Is this correct?

For a Name Server with very short request processing time, FIFO ordering is fine — the wait is short. For a Track Server with potentially longer processing, a high-priority train engineer might wait behind a low-priority display task. This is a mild form of priority inversion mediated by the server’s queue discipline.

The fix is to order the send queue by sender priority: insert new senders in priority order rather than at the tail. This gives priority-ordered service: the server always processes the highest-priority pending request first.

void send_queue_insert_priority(TaskDescriptor *server, TaskDescriptor *sender) {
    TaskDescriptor **ptr = &server->send_queue_head;
    while (*ptr && (*ptr)->priority >= sender->priority)
        ptr = &(*ptr)->send_next;
    sender->send_next = *ptr;
    *ptr = sender;
    if (!sender->send_next)
        server->send_queue_tail = sender;
}

Priority-ordered send queues are used by QNX Neutrino by default. The trade-off is O(n) insertion (where n is queue depth, typically small) versus O(1) FIFO insertion. For the CS 452 kernel, FIFO is simpler and acceptable; a student extending the kernel could add priority ordering to the CAN TX Server to ensure high-priority train commands preempt display tasks.

The Idle Task and Power Management

The idle task runs when no other task is ready. On a bare-metal system without power management, the CPU would spin at full power doing nothing. The idle task instead executes the WFI (Wait For Interrupt) instruction:

void idle_task_main(void) {
    for (;;) {
        asm volatile ("wfi");
    }
}

WFI halts the processor core (stops the instruction fetch and execution pipelines) until an interrupt arrives. On the Cortex-A72, WFI reduces power consumption to approximately 10–20% of active power. The processor wakes immediately when an interrupt is asserted (the GIC delivers the interrupt to the CPU interface, which releases the WFI stall), so the interrupt latency from a WFI state is no worse than from normal execution.

The idle task must have the lowest possible priority (0) so it runs only when nothing else is ready. It must never call any kernel primitive — not even Yield() — that would block it and leave the CPU without a task to run.

The fraction of time the idle task runs is the idle fraction: 1 - total_utilization. Measuring it: the idle task increments a counter on each iteration of its loop. The absolute iteration rate is calibrated once at startup (by measuring how many iterations complete in 1 ms with no other tasks running). During normal operation, the idle rate is compared to the calibration rate to compute utilization. The W26 lecture suggests measuring idle time; this is the standard implementation of that measurement.

The O(1) Scheduler: Bitmask Priority Queue

The scheduling algorithm described in the preceding sections — choose the highest-priority ready task, break ties by FIFO order within a priority level — sounds simple to state but has a subtle implementation challenge: how do you find the highest-priority ready task efficiently? The naive approach scans all 32 priority levels from highest to lowest until it finds one with a non-empty queue. That scan is O(P) in the number of priority levels. For 32 levels this is a constant, but the constant is 32 — and the scheduler runs on every context switch, every Send, every Reply, every AwaitEvent completion. In a kernel with ten tasks in flight and a clock interrupt at 508 kHz, the scheduler executes millions of times per second. Shaving cycles off the scheduler’s hot path pays dividends across every task in the system.

The classical solution, pioneered in the Linux O(1) scheduler (2.6 kernel era) and adopted in QNX and virtually every serious real-time microkernel, is a bitmask priority queue. A single 32-bit integer ready_mask encodes which priority levels have at least one ready task: bit \(n\) is set if and only if there is at least one task at priority \(n\) ready to run. Finding the highest-priority ready task reduces to finding the position of the most-significant set bit in ready_mask, which the ARMv8-A CLZ (Count Leading Zeros) instruction performs in a single cycle.

/* One FIFO queue per priority level */
static TaskDescriptor *ready_queues[32][2]; /* [priority][0=head, 1=tail] */
static uint32_t        ready_mask;          /* bit n set → queue n non-empty */

void scheduler_insert(TaskDescriptor *td) {
    int p = td->priority;
    if (ready_queues[p][0] == NULL) {
        ready_queues[p][0] = ready_queues[p][1] = td;
        td->next = NULL;
    } else {
        ready_queues[p][1]->next = td;
        ready_queues[p][1] = td;
        td->next = NULL;
    }
    ready_mask |= (1u << p);
}

TaskDescriptor *scheduler_next(void) {
    if (ready_mask == 0) return idle_task;
    int p = scheduler_find_highest_priority(ready_mask);
    TaskDescriptor *td = ready_queues[p][0];
    ready_queues[p][0] = td->next;
    if (ready_queues[p][0] == NULL) {
        ready_queues[p][1] = NULL;
        ready_mask &= ~(1u << p);   /* clear bit when queue drains */
    }
    return td;
}

scheduler_find_highest_priority uses the CLZ instruction introduced in the Chapter 3 assembly section:

static inline int scheduler_find_highest_priority(uint32_t mask) {
    int lz;
    asm("clz %w0, %w1" : "=r"(lz) : "r"(mask));
    return 31 - lz;
}

The entire scheduler_next path — CLZ, array index, pointer update, conditional bit clear — is a handful of instructions with no loops and no branches that depend on the number of tasks. This is what O(1) scheduling means in practice: the time to schedule is bounded by a constant that does not grow with the number of tasks or the number of priority levels.

To appreciate why this matters, compare with Linux’s Completely Fair Scheduler (CFS), introduced in kernel 2.6.23 to replace the O(1) scheduler for general-purpose workloads. CFS inserts and removes tasks from a red-black tree ordered by virtual runtime. Insertion and deletion in a balanced BST are \(O(\log n)\) where \(n\) is the number of runnable tasks. For a desktop with 500 runnable threads, \(\log_2 500 \approx 9\) — acceptable when tasks sleep for milliseconds at a time. For a real-time system with a 2 ms period timer and a kernel that schedules on every interrupt, even a small multiplicative constant matters. The O(1) bitmask approach dominates: no heap allocation, no pointer chasing, no rebalancing — just a CLZ and an array lookup.

QNX Neutrino uses the same bitmask-per-priority approach, organized into a 256-priority space with an outer 4-bit index into 8 words of 32 bits each — two CLZ operations cover all 256 levels. The CS 452 kernel needs only 32 priorities, so one CLZ suffices, and the design collapses to the single-word form shown above.

One subtlety: the bitmask and queues must remain consistent at all times. The invariant is: bit \(n\) is set in ready_mask if and only if ready_queues[n][0] != NULL. Violating this invariant — for example, by clearing the bit but leaving a non-null head pointer — would cause the scheduler to skip a ready task indefinitely, a form of starvation that would manifest as a task that never runs again after a missed ready_mask update. The kernel must update both the pointer and the bitmask atomically (in the sense of no interleaved interrupt between the two operations). Since the kernel runs with interrupts disabled during scheduling decisions (by the DAIF invariant from Chapter 22), this atomicity is guaranteed.

Chapter 9: Context Switching across Exception Levels

Context switching is the mechanism by which the kernel moves the CPU from one task to another. At its core, a context switch saves the current task’s computational state — its register file, stack pointer, and instruction pointer — and restores the saved state of the next task. On ARMv8-A, a context switch between a user task (at EL0) and the kernel (at EL1) is accomplished through the exception mechanism.

What Is Context?

A running task’s context is everything the CPU needs to resume the task as if it had never been interrupted:

1. General-purpose registers x0–x30: the current values of all 31 integer registers.
2. SP_EL0: the user task’s stack pointer (distinct from SP_EL1, the kernel’s stack pointer).
3. ELR_EL1: the address of the next instruction to execute in the user task (the “saved PC”).
4. SPSR_EL1: the saved PSTATE — the condition flags, the DAIF mask, and the execution level that was active when the exception was taken.

When the processor takes a synchronous exception (such as an svc instruction), it automatically saves the current PC to ELR_EL1 and the current PSTATE to SPSR_EL1. The stack pointer switches from SP_EL0 (user) to SP_EL1 (kernel), and execution jumps to the appropriate entry in the exception vector table. At this point, the kernel’s stack is set up and the user’s SP is untouched, but x0–x30 still contain whatever values the user task had — they have not been saved anywhere.

The kernel’s first job after entering the vector table handler is to save x0–x30 to a known location. The most natural location is the kernel’s own stack (SP_EL1). The kernel then processes the system call, and before returning to any task (which may not be the same task that made the call), it restores x0–x30 and SP_EL0 for the next task from its saved context frame.

The Exception Vector Table

The ARMv8-A architecture defines the exception vector table as a 2048-byte structure containing 16 entries, each 128 bytes. The 16 entries cover four exception sources (Current EL using SP0, Current EL using SPt, Lower EL in AArch64, Lower EL in AArch32) crossed with four exception types (Synchronous, IRQ, FIQ, SError). For a kernel running at EL1:

• Exceptions from EL0 AArch64 (user tasks) arrive at offset 0x400 (sync) or 0x480 (IRQ).
• Exceptions from EL1 using SP_EL1 arrive at 0x200 (sync) or 0x280 (IRQ) — these are kernel-mode faults and should never occur in a correct kernel.

The table must be aligned to a 2048-byte boundary and its address loaded into VBAR_EL1 before any exception can be taken:

.align 11                       // 2^11 = 2048-byte alignment

.global exception_vector_table
exception_vector_table:
    // Entries at 0x000–0x180: current EL, SP0 (not used)
    .rept 4
    .align 7                    // each entry is 128 bytes
    b       unhandled_exception
    .endr

    // Entries at 0x200–0x380: current EL, SPt (kernel fault)
    .rept 4
    .align 7
    b       kernel_fault
    .endr

    // Entries at 0x400–0x580: lower EL AArch64 (EL0 syscalls/IRQs)
    .align 7
    b       sync_el0_handler     // svc from EL0
    .align 7
    b       irq_el0_handler      // IRQ while running EL0 task
    .align 7
    b       unhandled_exception  // FIQ
    .align 7
    b       unhandled_exception  // SError

    // Entries at 0x600–0x780: lower EL AArch32 (not used)
    .rept 4
    .align 7
    b       unhandled_exception
    .endr

// Install the vector table
init_vectors:
    adr     x0, exception_vector_table
    msr     VBAR_EL1, x0
    isb
    ret

The System Call Entry Path

When a user task executes svc #0 (the syscall instruction; the immediate is ignored by this kernel, syscall number is in x0), the processor:

1. Saves the user PSTATE to SPSR_EL1.
2. Saves the return address (address of the instruction after svc) to ELR_EL1.
3. Switches from SP_EL0 to SP_EL1.
4. Clears DAIF (masking Debug, SError, IRQ, FIQ — the kernel runs with all interrupts masked unless it explicitly enables them).
5. Jumps to exception_vector_table + 0x400.

The synchronous EL0 handler must immediately save all user registers. Since the kernel needs a scratch register to set up the save (specifically, a register to hold the stack pointer it is writing to), it uses the per-task kernel stack pointed to by SP_EL1. The save sequence:

sync_el0_handler:
    // At this point:
    // SP       = SP_EL1 (kernel stack, pre-allocated per task)
    // ELR_EL1  = user's return address
    // SPSR_EL1 = user's saved PSTATE
    // x0-x30   = user's register values (unsaved)

    sub     sp, sp, #(34 * 8)          // allocate frame: 31 regs + SP_EL0 + ELR + SPSR

    stp     x0,  x1,  [sp, #0]
    stp     x2,  x3,  [sp, #16]
    stp     x4,  x5,  [sp, #32]
    stp     x6,  x7,  [sp, #48]
    stp     x8,  x9,  [sp, #64]
    stp     x10, x11, [sp, #80]
    stp     x12, x13, [sp, #96]
    stp     x14, x15, [sp, #112]
    stp     x16, x17, [sp, #128]
    stp     x18, x19, [sp, #144]
    stp     x20, x21, [sp, #160]
    stp     x22, x23, [sp, #176]
    stp     x24, x25, [sp, #192]
    stp     x26, x27, [sp, #208]
    stp     x28, x29, [sp, #224]

    // Save x30 (LR), SP_EL0, ELR_EL1, SPSR_EL1
    mrs     x20, SP_EL0
    mrs     x21, ELR_EL1
    mrs     x22, SPSR_EL1
    stp     x30, x20, [sp, #240]
    stp     x21, x22, [sp, #256]

    // Save current SP to task descriptor, pass frame to C handler
    mov     x0, sp
    bl      handle_syscall             // handle_syscall(frame_ptr)

    // On return: x0 = SP of next task to run (may differ from entry SP)
    mov     sp, x0                     // switch to next task's saved frame

    // Restore next task's registers
    ldp     x21, x22, [sp, #256]
    msr     ELR_EL1, x21
    msr     SPSR_EL1, x22
    ldp     x30, x20, [sp, #240]
    msr     SP_EL0, x20

    ldp     x28, x29, [sp, #224]
    // ... (reverse of save sequence) ...
    ldp     x0,  x1,  [sp, #0]

    add     sp, sp, #(34 * 8)
    eret                               // return to user task