OS Implementation Capstone: Build and Explain a Small Kernel

By the end of this lesson, you will be able to...

• Produce an inspectable small-kernel artifact that connects machine entry to a user-visible result.

• Defend ownership, invariants, blocking, failure behavior, and trade-offs across one end-to-end trace.

• Use tests and debug evidence to show that the artifact does more than boot once.

Idea in one sentence: A credible small kernel is not a list of subsystems; it is one coherent set of state transitions whose ownership, boundaries, failures, and evidence can be traced from boot to a user-visible outcome.

You now have the pieces: boot state, privilege transitions, page tables, process state, scheduling, syscall copying, locks, files, cached blocks, a driver, packet queues, isolation policy, and debugging evidence. The capstone asks a different question from every earlier lesson:

Can one small kernel explain what happens when a real user request crosses all of those boundaries?

Build or review a teaching-kernel artifact named TraceKernel. Its visible promise is modest: it boots, starts init, launches a restricted worker, and lets that worker write OK\n to /work/status. The kernel must make the result visible through a file-like interface and, when the worker requests a flush, report whether the block write completed. The worker must not see unrelated processes or exceed a stated resource budget.

The promise is intentionally small. The value is in the explanation: which object owns each byte and descriptor, which lock protects each queue, where the process can block, which operation crosses privilege, what happens if the user buffer is invalid, and how a test demonstrates the answer.

Core Insight

The capstone artifact is an evidence-backed walkthrough, not necessarily a new operating system. Choose one of these forms:

Plain meaning:

You are not being asked to build Linux in a weekend. You are being asked to make a small kernel explain itself when one request succeeds and when one request fails.

In this capstone:

worker writes three bytes. That small action should let a reviewer follow control from machine initialization to a scheduled user task, through a syscall trap and a copy boundary, into VFS/cache/driver state, across an interrupt completion, and back to a user-visible return. The restricted-worker extension makes the same trace state what the process can see and consume.

Technical name:

The deliverable is a cross-subsystem trace: an input, a sequence of controlled state transitions, an output, and failure evidence. Its proof obligations are the kernel's invariants (what must stay true), ownership (who may change or release state), interfaces (what each layer promises), and observability (how a test or trace supports the claim).

The Capstone Promise and Constraints

Use this concrete contract, or an equivalent one with the same coverage:

TraceKernel boots on a documented teaching-machine configuration.
It starts init and schedules worker in user mode.
worker is restricted to its own process/filesystem/network view and resource budget.
worker calls write(status_fd, "OK\n", 3), then flush(status_fd).
The kernel either reports a completed write or a defined error.
An invalid user buffer and a device-error test do not corrupt file or cache state.

Keep the implementation small. One process family, one regular-file path, one block-device request path, and one isolation policy are enough. Do not add advanced journaling, TCP, a production container runtime, a general allocator, multiple devices, or a sophisticated scheduler just to sound complete. The artifact is stronger when its boundaries are explicit.

Required artifact inventory

Your submission should include these seven items:

1. Machine and boot ledger — reset/loader handoff, early page-table choice, kernel entry point, initialized global objects, and the first runnable task.
2. Object and ownership map — process, address space, open-file object, inode, cache buffer, driver request, DMA buffer, and any isolation-policy records; state who creates, references, locks, and destroys each.
3. One happy-path trace — the worker request from user instruction to completed or accepted I/O result.
4. One blocking/wakeup trace — for example, flush waiting on device completion or a process waiting for a queue; include the lock/wait publication rule.
5. One failure trace — invalid user range, failed DMA completion, or full queue; show the defined error and preserved state.
6. One isolation map — process view, filesystem view, resource budget, and authority reduction; state the shared-kernel limit.
7. Evidence pack — focused tests plus at least one trace, structured log, assertion, panic record, or debugger observation.

The Initial Bad Capstone

An easy but weak submission says:

The kernel boots.
It has a scheduler, a filesystem, and a driver.
The worker writes a file.
Containers isolate it.

Every sentence can be true while leaving the important questions unanswered. Which scheduler state changes? Does write return when bytes are cached or when durable? Which buffer is device-owned? What happens when the worker pointer crosses an unmapped page? Does “containers isolate it” mean a private PID view, a cgroup memory maximum, a syscall filter, or a guest kernel?

The capstone fails when its parts cannot be connected. A boot diagram with no process state, a file diagram with no cache ownership, or an isolation claim with no trust boundary is a collection of labels rather than an implementation argument.

The better model is to choose one request and make each transition inspectable. If a component is not needed for the trace, name it as out of scope. If a mechanism appears, name the object it changes and the invariant that constrains it.

Worked Capstone Trace: worker writes and flushes OK\n

The following is a model trace for TraceKernel. Your implementation names may differ, but its control and ownership claims should be similarly explicit.

Input: after boot, worker executes:

write(status_fd, "OK\n", 3);
flush(status_fd);

worker is in a restricted process view, has a writable /work mount, and is attached to workers/a with a memory budget. status_fd refers to /work/status.

1. Boot establishes the objects the trace depends on

The loader hands the kernel a documented machine state. Kernel entry initializes the trap vector, physical-page allocator, kernel page table, process table, scheduler run queue, VFS tables, buffer cache, block-driver descriptor pool, and policy records for the worker boundary. It creates init with a user page table and a trap-return path, then makes it runnable.

init creates or launches worker. The scheduler selects worker, saves the previous task context, restores worker's registers/page-table context, and returns to user mode.

State ledger:

2. write crosses privilege and validates its data boundary

worker places syscall number and arguments in the ABI-defined registers, then executes the trap instruction. Trap entry saves user state in a trap frame and transfers to the kernel dispatcher. write checks that status_fd exists and is writable.

The string address is a user virtual address, not a kernel pointer. The kernel validates the complete three-byte range and copies OK\n through a helper that checks each necessary user page before side effects. If the range crosses an unmapped page, it returns the defined error and does not advance the file offset, dirty a cache buffer, or submit a device request.

Transition: worker: user running -> kernel syscall handling; user bytes become kernel-owned copied data only after validation.

3. VFS and cache turn bytes into a dirty block update

The VFS follows worker.files[status_fd] to an open-file object containing the offset and mode, then to the status inode. The inode maps the byte range to a logical file block and a device block. The buffer cache returns the single current buffer for that device block under its synchronization rule.

The kernel modifies the cache copy, marks it dirty, and advances the open-file offset according to the defined accepted-byte result. At this point later reads through the coherent cache can see OK\n; storage may still contain older bytes.

Transition: buffer: clean -> dirty; CPU owns the buffer; write returns an accepted byte count if buffered-write semantics are chosen.

4. flush makes the wait and device handoff visible

worker calls flush(status_fd) to ask for the capstone's defined completion guarantee. The cache pins the dirty buffer and gives the driver a request. The driver allocates a descriptor slot, records the buffer and waiting task in its request table, fills DMA-visible descriptors, publishes them in the required order, and writes the MMIO notification.

cache buffer B42: dirty + CPU-owned
  -> pinned + driver request 5
  -> DMA in flight + device-owned

The driver releases its short queue lock. worker publishes its wait condition before sleeping, so an early device interrupt cannot be lost. The process state becomes blocked(flush request 5) and the scheduler runs another runnable task.

5. Completion returns ownership and wakes the process

The device completes request 5 and raises an interrupt. The trap path enters the driver completion handler. The handler acknowledges the device, uses slot 5 to find B42, checks success or error status, records the result, returns the slot to the free pool, and wakes the waiter. It does not block or perform unrelated filesystem work in interrupt context.

On success, the cache may transition B42: in flight -> clean and unpin it. On failure, the buffer stays dirty or enters an explicit recoverable error state; it must not be falsely declared durable. When worker runs again, it rechecks the request result before returning from flush.

Output: user code sees a completed success or a defined error. A structured trace contains the request ID, block number, completion status, and wakeup state.

6. The isolation extension limits the worker without inventing a second kernel

Before worker starts, the launcher gives it a scoped process and mount view, a restricted network view if networking is included, a cgroup-like CPU/memory/process budget, closed inherited descriptors, and reduced authority. The exact teaching-kernel representation may be a simplified policy object rather than full Linux namespaces, but the contract must distinguish:

visibility  -> which PIDs, paths, and interfaces worker can observe
budget      -> CPU/memory/process resources worker may consume
authority   -> privileged operations or syscalls worker may request
trust       -> the host kernel remains shared

Naive contrast: saying “worker is a container” without a policy map leaves every part of the claim ambiguous. A memory limit alone does not hide host PIDs; a private root alone does not close inherited descriptors; neither stops a kernel vulnerability.

So far, one visible string has crossed boot assumptions, process scheduling, privilege, address translation, copying, VFS objects, cache state, DMA ownership, interrupt completion, wakeup, and an isolation policy. This is what integration means: each subsystem's local rule keeps the next subsystem's assumptions true.

Failure Review and Evidence Pack

Your artifact must show at least one failure as carefully as it shows success. Use either of these model cases.

Use the debugging loop from lesson 015. Start from a reproducible failing command. Capture the boundary state that distinguishes hypotheses. Add a focused test that fails before the repair and passes after it. A boot screenshot or a passing happy-path command alone is not sufficient evidence.

Trade-offs and Scope Boundaries

TraceKernel deliberately chooses simple mechanisms: one scheduler policy, coarse or clearly ordered locks, buffered writes with an explicit flush, one small driver queue, and a narrow isolation policy. This buys inspectability and a short proof of correctness. The trade-off is reduced concurrency and fewer features. A global lock may serialize unrelated work; synchronous flushes increase latency; copying to kernel buffers costs memory bandwidth; bounded queues drop work under pressure; a restrictive syscall policy can reject a legitimate workload.

The artifact must state which trade-off it chose and why. For example: “The driver permits one in-flight request, so its ownership proof is simple, but a slow device blocks flush throughput.” Or: “The VFS uses one coarse cache lock, which reduces race surface but limits parallel file access.”

The capstone does not prove production durability, multiprocessor scalability, hostile-tenant safety, or advanced network performance. Those are valid next tracks. It proves that you can identify the boundary where such work begins and explain why the teaching-kernel version stops there.

Common Capstone Failures

Confusion: “The artifact boots, so the architecture is validated.”

Why it is tempting:

Booting is a visible and satisfying milestone.

Better model:

Boot proves only that one initialization path reached a runnable state. The capstone needs a user request, an I/O or wait path, a failure case, and evidence about ownership and invariants.

Confusion: “A diagram can replace state transitions.”

Why it is tempting:

Subsystem boxes make the design look complete.

Better model:

Every arrow needs an object, a state change, an owner, and a failure behavior. A diagram is evidence only when its transitions can be traced.

Confusion: “The driver submission means flush succeeded.”

Why it is tempting:

The kernel has handed the request to hardware.

Better model:

Submission transfers ownership; completion status determines whether the cache may become clean and whether the blocked process may report success.

Confusion: “A container policy makes the capstone's kernel a VM.”

Why it is tempting:

The worker has a separate view of resources.

Better model:

The process still shares the same kernel. Visibility, budget, and authority are narrower policies, not a guest-kernel boundary.

Check: In the worked trace, the driver has notified the device but the completion interrupt has not occurred. Can flush return success and can B42 become clean?

Think first, then reveal.

Answer: No. The buffer is in flight and device-owned. Success requires a recorded completion status; otherwise a device error or power-loss boundary could be hidden behind a false clean state.

Check: A submission says “the worker has a private root and a 512 MiB limit.” What essential isolation claims are still unspecified?

Think first, then reveal.

Answer: At least process and network visibility, user/authority policy, inherited file descriptors, syscall restrictions, and the shared-kernel trust limit. A mount view plus memory budget is not a complete boundary description.

Capstone Submission and Rubric

Submit a concise design document, code repository note, or narrated walkthrough with the required inventory. A reviewer should be able to replay the happy path and failure path without asking you to fill in hidden assumptions.

Aim for each criterion to be independently inspectable. If a reviewer cannot answer “who owns this buffer?”, “what wakes this task?”, “what error does the user see?”, or “what proves this claim?” from the artifact, add a state table or focused trace rather than another broad paragraph.

Resources

• [BOOK] MIT 6.1810 xv6 book — Focus: use one small, coherent kernel as a reference for connecting traps, memory, processes, filesystems, drivers, and recovery.
• [COURSE] MIT 6.1810 course overview and labs — Focus: compare the capstone scope with a proven progression of implementation exercises.
• [DOC] QEMU GDB usage — Focus: collect repeatable debugger evidence for the failure path rather than relying only on a boot log.

Key Takeaways

1. The capstone proves integration through one request whose objects, control flow, owners, invariants, and outcomes remain visible across subsystem boundaries.
2. Success evidence must include a user-visible result and a completed state transition; failure evidence must preserve defined state and error behavior.
3. A small kernel becomes credible when it states its simplifications and trade-offs instead of hiding them behind broad subsystem names.
4. Completing this artifact prepares you to deepen one boundary—concurrency, storage, I/O, networking, containers, memory, or virtualization—without losing the whole-kernel model.