Part VII · Chapter 19

The Operating System Kernel

The bootloader has jumped to the kernel. From now on, one program owns the whole machine: every byte of memory, every device, every tick of the clock. Its job is to share all of it among the other programs, safely and fairly, so that none of them can harm the others. This chapter shows how the processor itself helps the kernel keep control.

An operating system is a lot of software: the kernel, plus libraries, settings, background services and all the familiar windows and menus. The heart of it is the kernel: the one program that runs with full control of the hardware. Everything else, from your web browser to the desktop itself, runs as an ordinary program that has to ask the kernel for anything it can't do alone.

The kernel has three big jobs:

Share the hardware: give each program its turn on the processor (Chapter 20), its own memory (Chapter 10), and its share of the disks, the network and the screen.
Protect: make sure no program can read another's memory, damage the kernel, or take over a device.
Simplify: hide the endless variety of hardware behind a few simple ideas, like files, processes and network connections, so that every program doesn't need to know how every disk works.

Two worlds: user mode and kernel mode

Protection is impossible in software alone. If a program could simply switch off interrupts, change the page tables or talk to the disk controller directly, no kernel could stop it. So the processor itself keeps track of who is running, with a privilege level.

In kernel mode, every instruction is allowed.
In user mode, the processor refuses the dangerous ones: switching interrupts off, halting, port I/O, loading page tables or interrupt tables, and more. It also refuses any access to memory pages marked "kernel only" in the page tables (Chapter 10).

x86 calls its levels rings, numbered 0 (most privileged) to 3. The current ring is kept in the lowest two bits of the CS register. Linux and Windows use just two: ring 0 for the kernel and ring 3 for everything else. RISC-V names its levels: machine mode (the firmware of Chapter 18), supervisor mode (the kernel) and user mode.

What happens if a user program tries something forbidden? The instruction doesn't run. Instead the processor raises an exception (Chapter 12), which jumps into the kernel. The kernel sees that the program broke the rules and, almost always, ends it.

Pick an instruction, then try it in both modes. In user mode, the processor checks every instruction and every memory access before allowing it.

This isn't theoretical. Here's a tiny program, run on the computer this book was written on, that prints a message (legally, by asking the kernel) and then tries cli:

$ ./user
Hello from user mode!
Segmentation fault (core dumped)
$ echo $?
139                                 ← 128 + 11: signal 11

The kernel even wrote it down in its log. The address 401018 is exactly where the cli instruction sits in the program:

traps: user[3323124] general protection fault ip:401018 sp:7ffec31be5c0 error:0 in user[401000+1000]

The door: system calls

If programs can't touch the hardware, how do they print, read files or send messages? They ask. A system call is a request to the kernel, made with a special instruction: syscall on x86-64, ecall on RISC-V. It's the one door between the two worlds that's always open, and it's carefully designed so that the program can't misuse it:

The processor switches to kernel mode and jumps to a single entry point chosen by the kernel at boot. The program can't choose where the kernel starts running.
The program says what it wants with a number in a register (on Linux, 1 means "write", 0 means "read") and puts the details in other registers.
The kernel checks everything before acting. Is that file really open? Does that memory really belong to the program? A kernel that trusted a program's pointers would let it read anyone's memory.
When the work is done, sysret (or sret on RISC-V) returns to the program, in user mode again.

Follow one real request, writing a line of text to the screen, all the way into the kernel and back out.

All this checking and switching has a price. On the computer this book was written on, we timed ten million calls of the simplest system call there is, one that just asks "who is my parent process?":

function call: 1.0 ns
system call:   65.3 ns              ← 60 times longer

That's still tiny, but it's why programs avoid making system calls one byte at a time. Libraries collect output in a buffer and write it in one go.

Device drivers

Part of the kernel's job is to hide the endless variety of hardware. Each kind of device is handled by a driver: a part of the kernel that knows that particular device's registers, interrupts and DMA rings (Chapters 11 to 13), and presents it to the rest of the kernel in a standard way. To the file system, every disk looks the same, whether it's a 1980s hard disk or an NVMe SSD; the driver does the translating.

Drivers are by far the biggest part of a modern kernel. Linux has around 40 million lines of code, and more than half of it is drivers, for tens of thousands of different devices. Most are loaded only when the matching hardware is found, as kernel modules. Here are a few of the 198 loaded on the computer this book was written on, each one handling a device we met in earlier chapters:

$ lsmod                              (a few lines)
Module                  Size  Used by
i915                 4288512  97     ← the Intel GPU (Chapter 17)
xhci_pci               24576  0      ← the USB controller (Chapter 13)
usbhid                 77824  0      ← USB keyboards and mice
r8169                 118784  0      ← the Realtek network chip
snd_hda_intel          61440  1      ← sound
iwlwifi               606208  1 iwlmvm ← Wi-Fi

Monolithic kernels and microkernels

Which parts of the operating system should run in kernel mode? There are two schools of thought.

A monolithic kernel puts everything in: the scheduler, memory management, file systems, network protocols and all the drivers, in one big program running in ring 0. Linux works this way. It's fast, because the parts call each other directly. But a single bug in any driver can corrupt the whole kernel.

A microkernel keeps only the bare essentials in kernel mode: scheduling, memory, and a way for programs to send each other messages. File systems and drivers run as ordinary user-mode processes. A crashing driver can simply be restarted. The price is speed: every request travels from process to process through the kernel, crossing the boundary many times.

Read a file in each design and count the trips across the boundary. Then crash the USB driver in each.

The debate is old and famous: in 1992 Andrew Tanenbaum, author of the MINIX microkernel, and Linus Torvalds, the young author of Linux, argued it out in public online. Both designs are thriving. Linux runs most of the world's servers, phones and every one of the 500 fastest supercomputers. Microkernels run where reliability matters most: QNX in cars and medical devices, and seL4, whose correctness has been proved mathematically. Windows and macOS sit in between, as "hybrid" kernels.

Meanwhile, inside a real CPU

Here's the complete program from the start of this chapter. It's the smallest possible Linux program: no libraries at all, just two system calls and one forbidden instruction:

# x86-64 Linux: print a line, then try a privileged instruction
_start:
    mov eax, 1              # system call 1: write
    mov edi, 1              # file descriptor 1: the screen
    lea rsi, [rip + msg]    # address of the message
    mov edx, 22             # its length
    syscall                 # 0f 05: ask the kernel to print it
    cli                     # fa: not allowed in user mode!
    mov eax, 60             # system call 60: exit (never reached)
    xor edi, edi
    syscall
msg: .ascii "Hello from user mode!\n"

The strace tool shows every system call a program makes, and what happened to it:

$ strace ./user
execve("./user", ["./user"], ...) = 0
write(1, "Hello from user mode!\n", 22) = 22
--- SIGSEGV {si_signo=SIGSEGV, si_code=SI_KERNEL, si_addr=NULL} ---
+++ killed by SIGSEGV (core dumped) +++

The doors in and out, on both instruction sets:

0f 05           syscall         ; x86-64: user → kernel
48 0f 07        sysretq         ; x86-64: kernel → user
73 00 00 00     ecall           # RISC-V: user → kernel (or kernel → firmware)
73 00 20 10     sret            # RISC-V: kernel → user

Try it yourself

The low two bits of the x86 CS register are 11. Which ring is the processor in, and what kind of code is running?
Show answer
11 in binary is 3: ring 3, user mode. An ordinary program is running. In the kernel, the bits are 00.
Why must cli be forbidden in user mode? What could a program do with it?
Show answer
With interrupts off, the timer interrupt of Chapter 12 can't reach the kernel. The program could then keep the processor forever, and no other program, not even the kernel, would ever run again.
Our program died with exit status 139. What does that number mean?
Show answer
On Linux, a status above 128 means "killed by a signal", and 139 − 128 = 11: signal 11, SIGSEGV, the signal the kernel sends for memory and protection faults.
A system call takes about 65 ns. A program prints a 1,000-character text one character at a time, each with its own system call. How much time goes on system calls? How about one call for the whole text?
Show answer
1,000 × 65 ns = 65 µs, against about 65 ns for one call: a thousand times less overhead. That's why output is buffered and written in large pieces.
In the kernel design demo, why does reading a file take 8 crossings in the microkernel but only 2 in the monolithic kernel?
Show answer
In the monolithic kernel, the file system and disk driver are inside the kernel, so the request goes in once and comes out once. In the microkernel they're separate user-mode processes, so the request passes through the kernel's message system between each pair: app, file system, disk driver, file system, app, with a trip in and out of the kernel each time.

What we learned

The kernel owns the hardware, shares it among programs, protects them from each other, and hides the hardware's details.
The processor enforces privilege levels: in user mode (ring 3) dangerous instructions and kernel memory cause an exception; kernel mode (ring 0) may do anything.
Programs ask the kernel for services with system calls (syscall, ecall), entering at a fixed entry point; the kernel checks every argument.
Device drivers make every device look standard to the rest of the kernel; they're most of its code.
Monolithic kernels are fast but fragile; microkernels isolate services in user mode, at the cost of more boundary crossings.

We've seen that the kernel gives each program its turn on the processor. But what exactly is a "program" while it runs, and how does the kernel decide whose turn it is? The next chapter is about processes, scheduling and system calls in detail.