Milestone 0: The Kernel Mental Model

No code in this chapter. This is the model you will spend the rest of the curriculum making concrete. Read it, then explain it out loud to someone — or to a rubber duck, or to a text file. If any explanation stalls, that stall is exactly where your model is wrong.

The goal: after this chapter, for any behavior you observe on a Linux machine, you can say which side of the privilege boundary owns it, which context it runs in, and which directory of the tree it lives in.

1. The Kernel Is Not a Program That Runs

The first and most persistent misconception is that the kernel is a process — something with a main() that starts, loops, and services requests. It is not, and dropping that picture is the single biggest step in this chapter.

The kernel is a body of code and data, mapped into every address space, that runs only when something makes it run. It has no thread of its own by default. Between the moment your syscall returns and the moment the next interrupt fires, there may be no kernel code executing anywhere on the machine.

   THE WRONG PICTURE                       THE RIGHT PICTURE

   ┌──────────┐  requests   ┌────────┐     ┌────────────────────────────────┐
   │ your app │────────────▶│ KERNEL │     │  your app's address space      │
   │          │◀────────────│ (a big │     │  ┌──────────────────────────┐  │
   └──────────┘  responses  │  loop) │     │  │ user half: your code,    │  │
                            └────────┘     │  │ heap, stack, libraries   │  │
                                           │  ├──────────────────────────┤  │
                                           │  │ kernel half: THE SAME    │  │
                                           │  │ physical kernel, mapped  │  │
                                           │  │ into EVERY process,      │  │
                                           │  │ unreachable at CPL 3     │  │
                                           │  └──────────────────────────┘  │
                                           └────────────────────────────────┘
                                             the CPU raises its privilege and
                                             JUMPS INTO the upper half.
                                             Same thread. Same page tables.
                                             Different permissions.

Two consequences worth internalizing now:

A syscall is not a message. It is your own thread, changing privilege level and jumping to a fixed address. There is no queue, no receiver, no context switch to a "kernel process". This is why syscalls are measured in tens of nanoseconds and not microseconds — and why getpid() is fast and read() on a cold file is not (the work is slow; the transition is not).

"The kernel" running on CPU 0 and "the kernel" running on CPU 7 are the same code, at the same time, on different data — or worse, on the same data. Every kernel function you read must be assumed reentrant across CPUs unless something prevents it. This is where locking comes from, and it is why kernel C feels paranoid compared to application C.

2. The Privilege Boundary

The hardware provides exactly two things: a privilege level, and a controlled way to change it.

The privilege level is a bit in a CPU register. Everything the kernel protects — page tables, device registers, other processes' memory, the ability to halt the CPU — is protected by hardware checks against that bit. There is no software gatekeeper. When kernel code runs, the checks are simply not applied.

That is the entire security model, and it is why a bug in a sound driver can corrupt a filesystem.

3. The Four Ways In

Control enters the kernel in exactly four ways. Being able to name all four, and say which context each produces, is the point of this section.

 ══════════════════════════════ USER SPACE ══════════════════════════════

   ① SYSCALL                 ② EXCEPTION                (nothing here)
     deliberate                accidental
     `syscall` / `svc`         page fault, divide-by-zero,
     you asked                 illegal instruction, alignment
        │                         │            you did not ask
 ═══════│═════════════════════════│════════════════════════════════════════
        ▼                         ▼                          ▲
   ┌─────────────────────────────────────────┐         ③ INTERRUPT
   │  KERNEL                                 │◀────────  a device, a timer, an
   │                                         │           IPI from another CPU,
   │   ④ KERNEL THREADS were already here.   │           or an NMI
   │      kthreadd's children: kworker,      │           nobody asked; it just
   │      ksoftirqd, kcompactd, rcu_*.       │           happened, on whatever
   │      They have no user half at all.     │           was running
   └─────────────────────────────────────────┘

Two facts from that table are worth stopping on.

A page fault is a syscall you did not write. When you touch a page that is not present, the CPU traps to the kernel, the kernel figures out what should be there (a file mapping? swap? a fresh anonymous page?), possibly performs I/O, and returns to re-execute your instruction. Your program sees nothing. Most of what "memory management" means is this handler.

Kernel threads are real tasks with no user space. Run ps aux and look at the names in square brackets: [kworker/2:1], [ksoftirqd/0], [rcu_preempt]. They appear in ps, they are scheduled like anything else, they can sleep — and they have no address space of their own, no user stack, and no file descriptors in the usual sense.

ps -eo pid,ppid,stat,comm | awk '$4 ~ /^\[/ || $2 == 2' | head -20   # kthreadd's children

4. Context: The Single Most Important Idea in This Book

"Context" answers one question: may this code go to sleep?

To sleep means to call schedule() and give up the CPU until something wakes you. That requires there to be a task whose state can be saved and later restored. In interrupt context there is no such task — the interrupt borrowed whatever task happened to be on the CPU, and putting that innocent task to sleep on your behalf would be a correctness disaster.

So the rule is simple to state and endless to apply: you may not sleep in atomic context.

The taxonomy

Warning: Read the second row again. Taking a spinlock puts you in atomic context even inside a syscall. The most common beginner bug in the kernel is not "I wrote code in an interrupt handler"; it is "I called something that sleeps while holding a spinlock." The sleeping call is usually three functions deep and does not look like it sleeps.

The functions that sleep and do not look like it

How the kernel catches you

You are not expected to reason about this unaided. The kernel will tell you — if you turned the checks on.

The characteristic message is one you will see many times, and it names the file and line of the offending call:

BUG: sleeping function called from invalid context at mm/page_alloc.c:...
in_atomic(): 1, irqs_disabled(): 0, non_block: 0, pid: 1234, name: my-module

Tip: Turn on CONFIG_DEBUG_ATOMIC_SLEEP and CONFIG_PROVE_LOCKING in every lab kernel and never turn them off. They cost performance you do not care about and catch bugs that would otherwise reach a mailing list with your name on them. The lab rig enables both.

Preemption, the other half of the same idea

Even in process context, and even with no interrupt in sight, the scheduler can take the CPU away from you between any two instructions — unless preemption is disabled. spin_lock() disables it (that is half the reason spinlocks exist); so does preempt_disable() directly.

Which preemption model your kernel uses changes when this can happen:

Recent kernels can also select the model at boot or at runtime (PREEMPT_DYNAMIC). Check yours rather than assuming:

grep -E 'CONFIG_PREEMPT' /boot/config-"$(uname -r)" 2>/dev/null || zcat /proc/config.gz | grep -E 'CONFIG_PREEMPT'
grep -o 'preempt=[a-z]*' /proc/cmdline
cat /sys/kernel/debug/sched/preempt 2>/dev/null    # if PREEMPT_DYNAMIC is enabled

Why this matters for correctness, not just latency: code that is correct under PREEMPT_NONE because "nothing else can run here" is wrong, and it will be found to be wrong the day someone runs it on a PREEMPT_RT kernel. Never reason from "the scheduler probably will not".

5. The Boundary: Who Owns What

This table is the reason this chapter exists. Memorize the middle column.

Tip: When you hit a confusing kernel behavior for the rest of your career, ask three questions in this order: (1) Which side of the privilege boundary is this? (2) What context am I in? (3) Who else can be touching this data right now? Those three resolve the large majority of cases.

6. What a Task Actually Is

Everything the scheduler runs is a struct task_struct. Processes and threads are the same kind of object; what differs is what they share, decided by the flags passed to clone().

  struct task_struct  ── the schedulable entity ("a task")
    │
    ├── pid, tgid                 tgid == "the process id" that getpid() returns
    ├── state                     RUNNING / INTERRUPTIBLE / UNINTERRUPTIBLE / STOPPED / ZOMBIE
    ├── mm  ──────────────▶  struct mm_struct   the address space
    │                          (shared between threads; NULL for kernel threads)
    ├── files ────────────▶  the fd table       (shared or copied, per CLONE_FILES)
    ├── signal / sighand ─▶  signal state       (shared or copied, per CLONE_SIGHAND)
    ├── cred ─────────────▶  uid/gid/capabilities
    ├── sched_class, se, rt, dl   which scheduling policy owns this task
    └── stack ────────────▶  THE KERNEL STACK   8 or 16 KB. Per task. Always allocated.

Find the real thing rather than trusting the sketch:

rg -n "struct task_struct \{" include/linux/sched.h
rg -n "define THREAD_SIZE" arch/x86/include/asm/ arch/arm64/include/asm/
rg -n "TASK_RUNNING|TASK_INTERRUPTIBLE|TASK_UNINTERRUPTIBLE" include/linux/sched.h | head

Every task has two stacks: the user stack (which can grow to megabytes) and a kernel stack of 8 or 16 KB that is allocated when the task is created and never grows. All kernel execution on behalf of that task uses it — every nested function call, every local variable, every interrupt that lands while the task is in the kernel.

That is why kernel C has rules application C does not:

• No large local variables. A 4 KB buffer on the stack is a quarter of your budget. The build warns: warning: the frame size of N bytes is larger than M bytes.
• No deep recursion. Ever. There is no stack growth and no guard beyond a page.
• No alloca, no variable-length arrays.

A stack overflow does not raise an exception; it corrupts whatever is adjacent. CONFIG_VMAP_STACK puts a guard page there so it faults instead — one of many "make the failure loud" options you will turn on.

7. The Source Tree as a Map

Roughly 80,000 files. It is navigable, because the top level is a genuine taxonomy.

ls -d */ | tr -d /
git ls-files | wc -l
for d in */; do printf "%-16s %s\n" "${d%/}" "$(git ls-files "$d" | wc -l)"; done | sort -k2 -rn

Three navigation habits to build now:

# 1. "Where is this defined?" — never guess a line number; ask.
rg -n "struct file_operations \{" include/linux/fs.h
rg -n --type c "\bvfs_read\b" fs/ | head

# 2. "Who owns this, and is it alive?"
./scripts/get_maintainer.pl -f mm/
git log --oneline --since="6 months ago" -- mm/ | wc -l

# 3. "How did this get to be this way?" — the commit message is the design doc.
git log -S'copy_to_user' --oneline -- kernel/ | head
git log --format='%h %s%n%n%b' -1 <some commit>

Warning: Nothing in this book — not a struct name, not a function signature, not a config symbol, not a directory — should be believed without running the command next to it. The tree merged a thousand commits while you read this page. Naming things by role and then grepping is not a stylistic preference; it is the only way to write about the kernel that stays true.

8. The Life of a Syscall, as a State Machine

The introduction traced a specific read(). Here is the same path with the example removed, because the shape is what generalizes.

  USER              kernel entry            generic kernel          hardware
  ────              ────────────            ──────────────          ────────
  set up regs
  `syscall`  ──────▶ switch stack
                     save pt_regs
                     (KPTI: switch CR3)
                     bounds-check nr
                     table lookup
                            │
                            ▼
                     SYSCALL_DEFINEn body ── validate arguments
                                            copy_from_user() any structs
                                                    │
                                            ┌───────┴────────┐
                                            │                │
                                     can answer now?    must wait?
                                            │                │
                                            │         set task state
                                            │         add to a wait queue
                                            │         issue the request ────▶ device
                                            │         schedule()  ◀── CPU runs someone else
                                            │                │
                                            │           (time passes)
                                            │                │
                                            │         ◀───────────────────── IRQ fires
                                            │         top half: ack, defer
                                            │         bottom half: complete,
                                            │                      wake_up()
                                            │                │
                                            │         scheduler picks us again;
                                            │         we resume inside schedule()
                                            └───────┬────────┘
                                                    ▼
                                            copy_to_user() the result
                                            return a value: >= 0, or -Exxx
                            ┌───────────────────────┘
                            ▼
                     EXIT-TO-USER WORK — this part surprises people:
                        need_resched?      → schedule()   (a preemption point)
                        pending signals?   → deliver; maybe restart the syscall
                        task work queued?  → run it
                            │
                     restore pt_regs
  ◀────────────────  `sysretq` / `eret`
  next instruction

Three things in that diagram are load-bearing and commonly missed:

1. The return value is the error channel. The kernel has no exceptions. Functions return int: >= 0 for success, -EINVAL/-ENOMEM/-EFAULT for failure. Pointer-returning functions use ERR_PTR()/IS_ERR()/PTR_ERR() to encode an error in the pointer itself. errno in user space is libc negating that value and stashing it.
2. Signals are delivered on the way out, not when they are sent. kill() sets a flag and wakes the target; the target notices at the next boundary crossing. This is why a task in TASK_UNINTERRUPTIBLE (the D state in ps) cannot be killed — it is not going to check.
3. The preemption point is on exit. need_resched set by a wakeup or the timer tick is honored here, which is one reason a PREEMPT_NONE kernel still feels responsive to ordinary programs: they cross this boundary constantly.

9. Kernel C Is a Dialect

You know C. The kernel's C has different rules, and every one of them exists for a reason you can name.

rg -n "define container_of" include/linux/container_of.h include/linux/kernel.h
rg -n "define IS_ERR\b|define ERR_PTR\b" include/linux/err.h
rg -n "__user" include/linux/compiler_types.h | head

10. Common Misconceptions, Corrected

11. The Reader's Method: How to Approach Any Subsystem

You will use this in Subsystems eight times. Learn the shape now.

 1. WHO OWNS IT?        ./scripts/get_maintainer.pl -f <dir>
                        Is it Supported, Maintained, or Orphan?

 2. WHAT DOES IT SAY    find Documentation -ipath '*<name>*'
    ABOUT ITSELF?       Read the overview .rst before any .c file.

 3. WHAT ARE THE        rg -n "^struct [a-z_]+ \{" <dir>/*.h include/linux/<name>*.h
    NOUNS?              A subsystem is 3–6 core structs and the relationships between
                        them. Draw them before reading any function.

 4. WHAT ARE THE        rg -n "struct [a-z_]+_ops \{" -A 30 <dir> include/linux/
    VERBS?              Function-pointer tables ARE the architecture. Who fills them
                        in, and who calls through them?

 5. WHERE DOES CONTROL  Find the entry points: a syscall, a probe(), an IRQ handler,
    ENTER?              a softirq. Then follow ONE path all the way down.

 6. WHAT IS MOVING?     git log --oneline --since="6 months ago" -- <dir> | head -30
                        Recent churn tells you what is contentious and what is dead.

 7. HOW IS IT TESTED?   ls tools/testing/selftests/ | grep -i <name>
                        rg -l "kunit" <dir>
                        The tests are executable documentation of the contract.

Do not read a subsystem front to back. Find one path and follow it to the hardware, then find a second path and notice what it shares with the first.

Validation / Self-check

Milestone 0 is complete when you can answer all of these without notes. These are the same twelve questions from the introduction.

1. Name every way control can enter the kernel from outside it, and for each, say what context it produces and whether that context may sleep.
2. Why can kernel code not dereference a user pointer directly? Name three distinct failure modes and the function you must use instead.
3. Define "context". List the kinds and, for each, whether you may sleep.
4. What does might_sleep() do, which config option makes it useful, and what is the exact message it produces?
5. Name three functions that can sleep but do not look like they can.
6. GFP_KERNEL vs. GFP_ATOMIC: what does each permit the allocator to do, and what goes wrong in each direction if you choose the other?
7. Spinlock vs. mutex: which contexts may take each, why, and what does spin_lock() do to preemption?
8. What is preemption, and why is "the scheduler probably will not preempt here" an unsound argument even when it is empirically true?
9. Your interrupt handler needs 2 ms of work. Name three deferral mechanisms and the tradeoff between them.
10. Why does the kernel deliberately have no stable internal API, and what would be worse if it did?
11. What does "we do not break userspace" forbid? Give one allowed and one forbidden change that look superficially similar.
12. A patch is in linux-next. Is it "in Linux"? What must happen next, and roughly when?

And three more that only this chapter can ask:

13. Draw the kernel's position in a process's address space. Why is the kernel mapped into every process rather than living in one of its own?
14. Explain why a task in state D (TASK_UNINTERRUPTIBLE) cannot be killed, in terms of when signals are delivered.
15. Your module works perfectly on your 4-core laptop and corrupts a list on a 96-core server. Name the three most likely causes, in order.

Tip: Write these answers into answers-m0.md and commit it. At the capstone you re-answer the same fifteen and diff. That diff is the most direct measure of what this curriculum did for you.

Next: The Lab Rig — the tree, the config, the initramfs, QEMU, and GDB, assembled into a loop you can run in under five minutes.