Project 4: Minimal Microkernel (Bare Metal)

Build a bootable x86-64 microkernel with IPC, scheduling, and address spaces.

Quick Reference

Attribute Value
Difficulty Master
Time Estimate 2-3 months
Language C + x86-64 Assembly (Alternatives: Rust)
Prerequisites IPC, paging, context switching, x86 boot flow
Key Topics Kernel entry, syscalls, IPC fast path, page tables

1. Learning Objectives

By completing this project, you will:

  1. Boot into long mode and set up a minimal kernel environment.
  2. Implement process creation, scheduling, and context switching.
  3. Provide IPC syscalls as the core kernel API.
  4. Enforce address-space isolation with page tables.

2. Theoretical Foundation

2.1 Core Concepts

  • Bootstrapping: From bootloader to long mode, GDT/IDT setup.
  • Context Switching: Saving/restoring registers and stacks.
  • Address Spaces: Page tables and permissions for isolation.
  • IPC Fast Path: Direct handoff if receiver is waiting.

2.2 Why This Matters

This is the point where theory becomes an OS. Implementing a minimal microkernel forces you to choose what belongs in the kernel and what belongs in user space.

2.3 Historical Context / Background

L4 demonstrated that a small kernel can be fast. seL4 proved it can be correct. Your kernel will mirror those decisions at a small scale.

2.4 Common Misconceptions

  • “A kernel must include drivers.” In microkernels, drivers are user-space processes.
  • “IPC is just a syscall.” In a microkernel, IPC is the syscall.

3. Project Specification

3.1 What You Will Build

A bootable microkernel that runs simple user-space tasks, provides synchronous IPC, schedules multiple threads, and isolates memory via paging.

3.2 Functional Requirements

  1. Boot: Load into long mode and print to serial.
  2. Tasks: Create at least two user tasks.
  3. Scheduling: Preemptive or cooperative scheduling.
  4. IPC: send/receive/call syscalls.
  5. Memory: Per-process address spaces with page tables.

3.3 Non-Functional Requirements

  • Stability: Kernel should not crash on invalid user input.
  • Minimality: Keep kernel code under ~10k lines.
  • Debuggability: Provide serial logs and a panic handler.

3.4 Example Usage / Output

Booting MicroK v0.1...
[mm] 128 MB detected
[ipc] endpoints ready
[sched] round-robin enabled
[init] user task started

3.5 Real World Outcome

$ qemu-system-x86_64 -kernel kernel.bin -serial stdio
Booting MicroK v0.1...
Memory: 128 MB detected
IPC: ready
Scheduler: round-robin

MicroK> ps
PID  STATE   NAME
1    RUNNING idle
2    WAITING vfs
3    RUNNING shell

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐   sys_call   ┌──────────────┐
│ User Task A  │ ───────────▶ │ Microkernel  │
│ User Task B  │ ◀─────────── │ IPC+Sched+MM │
└──────────────┘              └──────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Boot code Enter long mode Multiboot vs custom loader
Scheduler Select next task Round-robin vs priority
IPC send/receive/call Fast-path handoff
Memory manager Page allocation Bitmap vs buddy allocator
Syscall handler Dispatch syscalls Interrupt vs syscall instruction

4.3 Data Structures

typedef struct {
    uint64_t *pml4;
    uint64_t rsp;
    uint64_t rip;
    uint32_t state;
} task_t;

typedef struct {
    task_t *waiting_sender;
    task_t *waiting_receiver;
} endpoint_t;

4.4 Algorithm Overview

Key Algorithm: IPC Fast Path

  1. Sender traps into kernel and locates endpoint.
  2. If receiver is waiting, copy registers and directly switch.
  3. Otherwise block sender and schedule another task.

Complexity Analysis:

  • Time: O(1) per IPC in the fast path
  • Space: O(N) tasks and endpoints

5. Implementation Guide

5.1 Development Environment Setup

# Example toolchain setup
brew install x86_64-elf-gcc qemu

5.2 Project Structure

microk/
├── boot/
│   └── boot.asm
├── kernel/
│   ├── main.c
│   ├── syscall.c
│   ├── ipc.c
│   ├── sched.c
│   └── mm.c
├── user/
│   └── init.c
└── Makefile

5.3 The Core Question You’re Answering

“What is the smallest set of privileged mechanisms that can support an OS?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. x86-64 Boot Process
  2. Interrupt Descriptor Table (IDT)
  3. Page Tables and Privilege Levels
  4. Context Switching

5.5 Questions to Guide Your Design

  1. How will you transition to user mode?
  2. How will you represent tasks and endpoints?
  3. What is your IPC message format (registers vs buffers)?
  4. How will you handle invalid syscalls?

5.6 Thinking Exercise

Draw a Syscall Timeline

Draw the instruction flow from syscall in user space to kernel handler and back to user space.

5.7 The Interview Questions They’ll Ask

  1. “How does a syscall transition to kernel mode on x86-64?”
  2. “Why do microkernels keep the kernel small?”
  3. “How does the IPC fast path avoid the scheduler?”

5.8 Hints in Layers

Hint 1: Start with serial output Print a boot message before adding paging.

Hint 2: Implement a single task Run a single user task before adding scheduling.

Hint 3: Add IPC last Add IPC after syscalls and context switching work.

5.9 Books That Will Help

Topic Book Chapter
Boot + paging OSTEP Virtual memory chapters
x86-64 setup OSDev Wiki Boot sequence
IPC design L4 papers IPC sections

5.10 Implementation Phases

Phase 1: Foundation (3-4 weeks)

Goals:

  • Boot into long mode
  • Serial output

Tasks:

  1. Set up GDT/IDT.
  2. Print boot banner.

Checkpoint: QEMU shows kernel banner.

Phase 2: Core Functionality (4-6 weeks)

Goals:

  • Tasks and scheduling
  • Syscalls and IPC

Tasks:

  1. Implement task creation.
  2. Add round-robin scheduler.
  3. Implement IPC syscalls.

Checkpoint: Two tasks exchange messages.

Phase 3: Polish & Edge Cases (3-4 weeks)

Goals:

  • Memory isolation
  • Error handling

Tasks:

  1. Add per-task page tables.
  2. Validate user pointers.

Checkpoint: Invalid pointers are rejected without crash.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Syscall entry syscall, int 0x80 syscall Faster on x86-64
Scheduler RR, priority RR Simpler first
IPC transfer copy, map copy Simpler until stable

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Boot Tests Validate startup banner and serial output
IPC Tests Send/receive ping-pong tasks
Memory Tests Isolation invalid pointer access

6.2 Critical Test Cases

  1. IPC ping-pong: Two tasks exchange 1000 messages.
  2. Page fault handling: Invalid user pointer doesn’t panic kernel.
  3. Scheduler fairness: Both tasks make progress.

6.3 Test Data

Task count: 2, 4
Message sizes: 8, 64 bytes

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Bad stack switching Triple fault Validate TSS and stacks
Wrong page table flags Page faults Audit PTE permissions
IPC races Deadlocks Keep IPC data structures minimal

7.2 Debugging Strategies

  • Use QEMU + GDB to single-step boot.
  • Log scheduler decisions over serial.

7.3 Performance Traps

Excessive syscall overhead makes IPC slow. Implement the fast path once correctness is proven.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a simple shell with two commands.
  • Add a timer interrupt.

8.2 Intermediate Extensions

  • Add priority scheduling.
  • Add shared memory pages.

8.3 Advanced Extensions

  • Implement capability system (Project 2).
  • Add user-space drivers (Project 3).

9. Real-World Connections

9.1 Industry Applications

  • seL4: Verified microkernel with similar primitives.
  • QNX: Commercial microkernel in safety-critical systems.
  • seL4: https://sel4.systems/
  • L4Re: https://os.inf.tu-dresden.de/L4/

9.3 Interview Relevance

Kernel boot, paging, and IPC are classic OS interview topics.

10. Resources

10.1 Essential Reading

  • OSDev Wiki - Boot and paging guides.
  • OSTEP - Virtual memory and CPU virtualization.

10.2 Video Resources

  • MIT 6.S081 lectures on xv6 kernel basics.

10.3 Tools & Documentation

  • QEMU: system emulation
  • GDB: kernel debugging
  • Project 1: IPC semantics.
  • Project 5: User-space filesystem server.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the x86-64 boot flow.
  • I can describe how IPC works in my kernel.

11.2 Implementation

  • Kernel boots and runs user tasks.
  • IPC syscalls work and are stable.

11.3 Growth

  • I can articulate what I would move out of the kernel next.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Kernel boots and prints to serial.
  • One user task runs successfully.

Full Completion:

  • Multiple tasks run and can IPC.
  • Memory isolation is enforced.

Excellence (Going Above & Beyond):

  • IPC fast path optimized.
  • Capability system integrated.

This guide was generated from LEARN_MICROKERNELS.md. For the complete learning path, see the parent directory.