kernel.md

Kernel design

The kernel is a microkernel. It implements only tasks, scheduling, IPC, interrupt dispatch, and virtual memory. Everything else lives in userspace tasks: the clock, serial, train control, a shell, even the C library. The kernel itself never blocks and holds no per-driver logic. Drivers are just tasks that AwaitEvent() on an interrupt.

The project descends from the CS452 real-time kernel assignments (k1–k4), but has since grown a real virtual-memory subsystem, an ELF loader, a name server, a POSIX-ish service layer, and a type-safe RPC framework.

Key constants (see kernel/include/core/constants.h):

• 64 task descriptors (MaxThreadsNum)
• 32 priority levels (MaxPriorityNum)
• 256-byte maximum IPC message (MaxMessageLength)
• 10 ms kernel tick (KernelTickInterval)

Table of contents

• Boot flow
• Tasks and threads
• Scheduling and real-time characteristics
• System calls
• Inter-process communication (IPC)
• Remote procedure calls (RPC)
• Interrupts and events
• Virtual memory

Boot flow

1. Loader (loader/) runs first from the front of kernel8.img. It parses the device tree and boot arguments, sets up initial page tables, unpacks the initrd, and hands a LoaderData structure to the kernel.
2. kernel_main (kernel/core/main.cc) takes over: it reclaims the loader's memory, rebuilds the physical-frame database, runs C++ static constructors (.init_array), and initializes the exception vectors, slab allocator, thread pool, and event subsystem.
3. It locates the init binary named by the init= boot argument inside the initrd, creates it as the first task at priority 1, then erets down to EL0 to begin executing userspace.

The kernel is linked to run in the high half of the address space (0xFFFF_8000_0000_0000); user tasks live in the low half. See the two linker.ld scripts.

Tasks and threads

Each task is a Thread (kernel/include/core/thread.h) drawn from a fixed pool of 64, allocated via an intrusive free-list. Stripped of its methods, the descriptor looks like this:

struct Thread {
   char         name[64];       // debug-only task name
   tid_t        user_tid;       // this task's ID
   tid_t        user_pid;       // parent task's ID
   uint64_t     priority;       // 0 = most urgent ... 31 = idle
   State        state;          // lifecycle state, see below

   Frame        saved_context;  // saved registers, restored on dispatch
   AddressSpace aspace;         // this task's private page tables
   elf::Parser  image;          // ELF image backing the task

   Ipc                   ipc;     // IPC control block (see IPC section)
   IntrusiveList<Thread> mailbox; // senders blocked waiting to Send() to us
};

Its lifecycle state is a small FSM:

enum class State {
   CREATING,     // being constructed; ELF copied in on first dispatch
   READY,        // sitting in a ready queue
   RUNNING,      // currently on the CPU
   IPC_WAIT,     // blocked inside Send/Receive/Reply
   IPC_DEFERRED, // rendezvous done; cross-space copy finishes on next dispatch
   EVENT_WAIT,   // blocked inside AwaitEvent
};

Tasks are created from ELF images stored in the initrd. thread::create() parses the ELF, builds a fresh address space, maps each PT_LOAD segment with the appropriate R/W/X permissions, and adds the standard regions (stack, heap, shared initrd, device MMIO) before enqueuing the task. The ELF's segments are copied into the new address space lazily, on first schedule, in finalize_thread_create().

Scheduling and real-time characteristics

The scheduler (thread::schedule) is fixed-priority preemptive with round-robin within a priority:

• Cooperation is required at the kernel level: the kernel does not preempt on its own. Tick-based preemption is driven from userspace, and every kernel entry - including any interrupt - triggers a rescheduling.
• There is one ready queue per priority level (32 total). Lower numeric priority = higher urgency (priority 0 is the most urgent).
• On every scheduling decision the kernel picks the highest-priority non-empty ready queue and takes its head. Within a level, tasks are served round-robin (FIFO re-enqueue).
• A task runs until it blocks (IPC or event), yields, exits, or is preempted by a higher-priority task becoming ready, for example when a clock or serial interrupt wakes a high-priority driver.

This gives the system its real-time property: the highest-priority runnable task always runs, and blocking is explicit, so worst-case latency is bounded by the (short, non-looping) kernel primitives rather than by unbounded kernel work. The scheduler and IPC paths are O(1)/O(small) with no dynamic allocation on the hot path. When every queue is empty and no task is event-blocked, the kernel declares deadlock and halts; if tasks are merely event-blocked it idles.

The kernel is instrumented with per-task performance counters (runtime, IPC-block time, event-block time, reschedule latency, schedule counts) exposed to userspace through virtual events (see below) and readable via the dmesg tool. An idle task (priority 31) reports CPU utilization.

System calls

System calls are AArch64 svc #imm traps; the immediate encodes the call number. Argument marshalling lives in lib/user/private/svc.h and the user-facing wrappers in lib/user/syscalls.h. The complete set (SYSCALL_LIST_MACRO in constants.h) is deliberately small:

Syscall	Purpose
Create(priority, entry)	Create a task from an ELF image, return its TID
MyTid()	Caller's task ID
MyParentTid()	Caller's parent task ID
Yield()	Give up the CPU to same-or-higher-priority tasks
Exit()	Terminate the calling task
Send(tid, msg, len, reply, rplen)	Send a message and block for a reply
Receive(&tid, msg, len)	Receive the next queued message
Reply(tid, reply, rplen)	Reply to a sender, unblocking it
AwaitEvent(event)	Block until a hardware/virtual event fires

Kernel-side implementations are in kernel/core/syscall.cc. Return values are delivered by writing the saved x0 of the blocked task.

Inter-process communication (IPC)

IPC is the classic Send–Receive–Reply (SRR) rendezvous. It is the only way tasks share data, since every task has an isolated address space. The three primitives:

// Sender: copy `msg` to `to`, block until it Reply()s. Returns reply length.
int Send(tid_t to, const void* msg, size_t msglen, void* reply, size_t replylen);

// Receiver: block until a message arrives; write the sender's TID into `from`
// and its message into `msg`. Returns the message length.
int Receive(tid_t* from, void* msg, size_t msglen);

// Replier: hand `reply` back to a sender blocked in Send(), unblocking it.
// Returns the number of bytes actually copied.
int Reply(tid_t to, const void* reply, size_t replylen);

• Send copies the message into the sender's kernel-side IPC buffer, marks the sender IPC_WAIT/AWAIT_RECEIVE, and enqueues it on the receiver's mailbox. If the receiver was already blocked in Receive, it is woken.
• Receive either pops a queued sender immediately (copying its message into the receiver's buffer and returning the sender's TID) or blocks AWAIT_SEND until one arrives.
• Reply copies the reply back into the sender's buffer and unblocks it.

Each task's IPC control block tracks where it is in this cycle:

struct Ipc {
   enum class State {
      INITIAL,       // not in an IPC cycle
      AWAIT_SEND,    // blocked in Receive(), no sender yet
      AWAIT_RECEIVE, // blocked in Send(), queued on receiver's mailbox
      AWAIT_REPLY,   // message delivered, waiting for Reply()
      REPLIED,       // receiver replied; sender's copy-back is pending
      SENT,          // sender arrived; receiver's copy-in is pending
   };

   State   state;
   uint8_t buf[MaxMessageLength]; // staging buffer (kernel copies through this)
   // ...plus per-direction metadata: message/reply lengths, the user's
   //    reply buffer, and the peer task pointer.
};

The kernel cannot touch another task's address space directly, so message and reply payloads are staged through a fixed 256-byte per-task buffer inside the kernel and copied across at the rendezvous points. Completion of the copy back into user memory is deferred to the moment the woken task is next scheduled (the IPC_DEFERRED state with sub-states SENT/REPLIED), so no task ever writes into another's page tables. Send-blocked senders queue on the receiver in FIFO order, giving predictable service.

Remote procedure calls (RPC)

Raw SRR is verbose, so userspace layers a type-safe RPC framework on top of it (lib/user/rpc.h). Server methods are ordinary C++ functions, arguments are serialized and dispatched by a compile-time hash of the handler's name, and results are returned transparently to the caller. This is how the name server, clock server, serial I/O, filesystem, and train commands are all expressed.

The RPC framework is documented in docs/writing-a-service.md, since it is the foundation for building userspace services. That covers deferred replies, the name server, and the notifier/server driver pattern.

Interrupts and events

Hardware interrupts are handled through the AwaitEvent mechanism, which keeps device policy in userspace. A driver task calls AwaitEvent(event) and blocks in EVENT_WAIT. When the corresponding IRQ fires, the kernel's interrupt handler (kernel/platform/irq.cc) calls event::handle(event, data), which unblocks every task waiting on that event and delivers the data word as the syscall return value.

Events (EVENT_LIST_MACRO in constants.h) include:

• UPDATE_TIME: the 10 ms system-timer tick (drives the clock server),
• UART0_RX/TX/CTS and UART3_RX/TX/CTS: serial I/O for the terminal and the Märklin controller,
• and several virtual events that are not real interrupts but requests serviced synchronously by the kernel: KCOUNTER_MAP / KCOUNTER_LENGTH / KCOUNTER_OFFSET map the performance-counter page into a task, and SET_IDLE_THREAD registers the idle task.

Events that arrive with no waiter can be deferred (queued or counted) so a driver that briefly missed one does not lose it. This is used, for example, for the UART3 CTS handshake line.

Virtual memory

Each task has a full private AArch64 4-level page table (kernel/core/vm.cc, kernel/include/core/vm.h). The design:

• Address spaces are collections of regions, where a region is a contiguous virtual range with uniform permissions:

  struct Region {
     uint64_t base, size;         // virtual address range [base, base+size)
     struct Flags {
        bool readable, writable, executable;
        bool shared;       // backed by a shared VMO (initrd, device MMIO)
        bool lazy_commit;  // pages committed on fault, not up front
        bool grows_down;   // expands toward lower addresses (stacks)
        bool is_device;    // Device memory attribute (uncached, ordered)
     } flags;
     IntrusiveList<Page> pages;   // physical frames backing this region
  };

• Physical memory is tracked by a page-frame database (one Page struct per 4 KiB frame) with an intrusive free-list allocator; page-table pages and kernel objects come from a slab allocator.

• A recursive mapping in slot 511 of the L0 table lets the kernel walk and edit any task's tables through virtual addresses.

• Lazy commit: stack and heap regions are created without backing pages and committed one page at a time on fault. Stacks are marked grows_down. Device MMIO and the initrd are mapped as shared regions (the initrd read-only, device memory with the Device memory attribute).

• Context switches reprogram TTBR0_EL1 (and TPIDR_EL0 for the thread-local base) and flush the TLB. The kernel half in TTBR1 is shared and never switched.

Memory map. Every task sees the same fixed layout in the low half (TTBR0); the kernel occupies the high half (TTBR1), shared across all tasks. Addresses are from kernel/include/core/constants.h and lib/user/linker.ld.

User address space (TTBR0, private per task):

Region	Range	Size	Perms	Backing
Program image	0x0000_0000_0004_0000 – varies	image	R-X/R--/RW-	ELF PT_LOAD, fixed base 0x40000
Heap	0x0000_0000_1000_0000 – 0x0000_0000_E000_0000	~3.25 GiB	RW-	lazy-commit, grows up
Device MMIO	0x0000_0000_FE00_0000 – 0x0000_0000_FF85_0000	~24 MiB	RW- Device	shared, identity-mapped (VA = PA)
Perf counters	0x0000_FFFD_0000_0000 – +VMO	≥1 page	R--	shared kernel VMO (kperf)
Initrd	0x0000_FFFE_0000_0000 – +initrd	initrd	R--	shared VMO (all ELF images live here)
Stack	0x0000_FFFE_8000_0000 – 0x0000_FFFF_0000_0000	2 GiB	RW-	lazy-commit, grows down

Kernel address space (TTBR1, shared):

Region	Base	Notes
Physical / linear map	0xFFFF_0000_0000_0000	KernelOffset: physical RAM linear-mapped for the kernel
Kernel image	0xFFFF_8000_0000_0000	KernelStart: .text/.rodata/.data/.kcounters/.bss
Recursive page tables	L0 slot 511	self-map; lets the kernel edit any task's tables by VA

Data/instruction aborts are decoded and reported by the exception layer (kernel/platform/exception.cc). A lazy-commit fault in a committable region is satisfied transparently, while a genuine fault is surfaced with a decoded ISS.

---

See the top-level README.md for build/run instructions, docs/runtime-abi.md for the userspace runtime and library ports, and docs/writing-a-service.md / docs/writing-a-program.md for building on the kernel.