13 Processes: context switching, scheduling, user mode and system calls
The kernel of chapter 12, Memory management, can allocate frames, map
pages and hand out memory with kmalloc, but it still does
exactly one thing at a time, and that thing is kmain. In
this chapter it starts running programs. By the end, seven
tasks share the processor: two kernel threads that take turns printing,
two user programs that run in ring 3 and talk to the kernel through
int 0x80, one rogue program that reads a kernel variable,
gets a page fault, and is killed while everything else carries on, one
that sleeps and wakes up on time, and a second rogue that lies to the
kernel about a buffer and is simply refused. Everything is printed on
the serial port, so make test can check it:
thread A: 1
thread B: 1
user task 3: hello from ring 3
user task 4: count 1
user task 5: about to read kernel memory
Page fault at 0x00018000: protection violation, read, user mode, eip=0x0001432f (error code 0x5)
killing task 5 (user rogue)
user task 6: tick 10, sleeping 25 ticks
[task 7: write(0x00010000, 16) rejected]
user task 7: write(0x10000, 16) returned -1
..... output omitted .....
user task 6: awake at tick 85, done
[task 6 (user sleeper) exited]
all tasks finished, 32432 frames freeThe first part of the chapter is conceptual: what a process is and what the words scheduler, context switch, preemption and thread mean. The second part is the x86 view: what the Intel manual calls a task, the Task-State Segment, and why we use only a small corner of what the manual offers. The rest is the code, in the order the kernel needs it: kernel threads and the switch between them, the scheduler on the timer interrupt, the descent to ring 3, system calls, a clock and a way to sleep, a careful look at what “disabling interrupts” does and does not protect, and the two kinds of protection that make a misbehaving program a dead or a refused program instead of a dead machine.
Running this chapter’s code
The code is in code/chapter13/os. From the root of the
repository:
$ docker run --rm -it --user "$(id -u):$(id -g)" --security-opt seccomp=unconfined \
-v "$PWD":/work -w /work/code/chapter13/os os01make builds build/disk.img;
make qemu boots it stopped at the first instruction with a
gdb stub on port 26000 and the serial port on the terminal;
make gdb in a second shell connects and stops at
kmain. make test boots headless and waits, for
up to 15 seconds, for the string all tasks finished on the
serial port, which only appears after every task, including the two that
misbehave, has run to its end and been reaped; the whole serial log is
printed either way. The sessions of this chapter use
-serial file: and b *address breakpoints on
the assembly in switch.asm; the addresses are those of the
build in the repository and will differ if you change a file before
switch.asm in the link order, so take them from
objdump -d as the text explains.
13.1 Concepts
13.1.1 Task
A task is a unit of work that an OS needs to do, similar to how humans have tasks to do daily. From a user’s point of view, a task for a computer can be web browsing, document editing, gaming, sending and receiving emails, etc. Since a CPU can only execute sequentially, one instruction after another (fetched from main memory), there must be some way to do many meaningful tasks at once. For that reason, the computer must share its resources, e.g. registers, stack, memory, etc., between tasks, since we have many tasks but a single set of limited resources.
13.1.2 Process
A process is a data structure that keeps track of the
execution state of a task. Task is a general concept, and process is the
implementation of a task. In a general-purpose OS, a task is usually a
program. For example, when you run Firefox, a process structure is
created to keep track of where the stack and the heap allocated for
Firefox are, where Firefox’s code area is, which instruction
EIP is holding to execute next, etc. A typical process
structure records, in words: an identifier; the state (running, ready,
sleeping…); the saved registers, or at least the stack pointer from
which they can be found; the page directory that describes its memory;
the open files; and a link to the other processes the scheduler can
choose from. The struct task of this chapter has every one
of these fields except the open files, which this book’s kernel never
gets (exercise 14.2 adds them).
A process is a virtual computer, but much more primitive than the virtual machine of virtualization software like VirtualBox, and that is a good thing. Imagine having to run a full-fledged virtual machine for every task; how wasteful of machine resources that would be. In the view of a running process, its code executes as if it ran directly on hardware. Each process has its own set of register values, which are kept track of by the OS, and its own contiguous virtual memory space (which is discontiguous in actual physical memory). The code in a process is given virtual memory addresses to read and write from. Picture each process as a small Von Neumann machine of its own: a CPU with a full set of registers, and a memory that, from inside, looks like one contiguous range of addresses, while every cell of it is actually a cell of the one physical memory, scattered wherever the frame allocator of chapter 12 happened to find a free frame. The page directory is the table that records the scattering, and that is why each process gets its own.
A process can run only so much until the OS tells it to temporarily stop for other tasks to use the hardware resources. The suspended process can then wait until further notice from the OS. This whole switching process is so fast that a computer user thinks his computer actually runs tasks in parallel. The program that does the switching between tasks is called a scheduler.
13.1.3 Scheduler
An OS needs to perform a wide range of different functionalities, e.g. web browsing, document editing, gaming, etc. A scheduler decides which tasks get to run before the others, and for how long, in an efficient manner. The scheduler turns your computer into a time sharing system, because tasks share CPU execution time and no one process can monopolize the CPU (in practice, it still happens regularly). Without a scheduler, only a single task can be performed at a time.
13.1.4 Context switch
When a process is prepared to be switched out for another process to take its place, certain hardware resources, i.e. current open files, current register values, etc., must be backed up to later resume that process’s execution. The backed-up state is the context, and the operation is a context switch. How much must be saved is a design decision of the OS, and the whole second half of this chapter is about making that decision on x86: the answer turns out to be “surprisingly little”.
13.1.5 Priority
Priority is an important metric for an OS to decide which task is scheduled to run before the others, and to allocate appropriate CPU execution time to each task. The scheduler of this chapter has no priorities: every task is equal and they run in turn. Exercise 13.1 adds them.
13.1.6 Preemptive vs non-preemptive
A preemptive OS can interrupt an executing process and switch to another process. In a non-preemptive OS, a task runs until it completes or until it volunteers to give the CPU up.
Our kernel is both, in a sense: a task may volunteer with
yield(), and if it does not, the timer interrupt takes the
CPU away from it every tenth tick. The second mechanism is what makes
the system preemptive, and it is what a program cannot opt out of.
13.1.7 Process states
A state is a particular condition of a process, triggered by an action from the scheduler. A process goes through various states during its life cycle. A process typically has these states:
- Run
-
the CPU is executing code in this process.
- Sleep
-
(or Suspended, or Ready) the CPU is executing some other process; this one waits for its turn.
- Destroyed
-
the process is done and waits to be destroyed completely.
The states of enum task_state in task.h are
these three, TASK_RUNNING, TASK_READY and
TASK_DEAD, plus a fourth, TASK_SLEEPING, which
is the “sleeping, waiting for something” of a real kernel in its
simplest form: a task that has asked not to run before a given time. A
real kernel also distinguishes “waiting for a disk block” from “waiting
for a key press”; we do not need that yet because no task of this
chapter waits for a device. Mind the vocabulary: the “Sleep” of the list
above, a task that merely waits for its turn, is
TASK_READY; TASK_SLEEPING is kept for a task
that has asked not to run. The fourth state arrives in the section
“Timekeeping and sleeping”; the first three carry the chapter until
then.
13.1.8 procfs
On Linux, the process structure is not hidden: the kernel exposes the
state of every process as a directory of files under /proc,
the proc filesystem, and /proc/self always denotes
the process that is reading it. Every field a kernel keeps about a
process has a file there, which is a good way to find out what a process
structure contains:
$ ls -C -w 80 /proc/self
arch_status fdinfo ns smaps_rollup
attr gid_map numa_maps stack
autogroup io oom_adj stat
auxv ksm_merging_pages oom_score statm
cgroup ksm_stat oom_score_adj status
clear_refs limits pagemap syscall
cmdline loginuid personality task
comm map_files projid_map timens_offsets
coredump_filter maps root timers
cpu_resctrl_groups mem sched timerslack_ns
cwd mountinfo schedstat uid_map
environ mounts sessionid wchan
exe mountstats setgroups
fd net smapsstatus is the state and the identifiers,
maps the virtual memory layout (the page directory, as a
list of ranges), fd the open files, stack the
kernel stack, task the threads, syscall the
system call the process is in. Read man 5 proc with this
chapter in one hand.
13.1.9 Threads
Threads are units of work inside a process that share the execution environment. A process creates a whole new execution environment with code of its own; think of a process as a large box that holds an address space, and of its threads as smaller boxes nested inside it, each pointing to a different place in the same code.
Instead of creating a completely new process structure in memory, the OS simply lets the thread use some of the resources of the parent process that created it. A thread has its own registers, program counter, stack pointer, and its own call stack. Everything else is shared between the threads, such as the address space, heap, static data, code segments, and file descriptors. Because a thread simply reuses existing resources and switching between threads involves no change of address space, it is much faster to create and switch between threads than between processes.
| Private to each thread | Shared by the threads of a process |
|---|---|
registers, including EIP and ESP |
address space (page directory) |
| the stack | code, static data, heap |
| state (running, ready…) | open files |
However, note that the above scheme is just one implementation of the thread concept. You can completely treat threads the same as processes (hence you can call all processes threads and vice versa). Or you can back up some resources while leaving others shared. It is up to the OS designer to distinguish between threads and processes. Threads are usually implemented as a component of a process.
On Linux, a thread is simply a process that shares resources with its parent process; for that reason, a Linux thread is also called a light-weight process. Put another way, a thread in Linux is merely an implementation of a single-threaded process that executes its main program code. A multi-threaded program in Linux is just a process whose resources are shared with its single-threaded children processes, each pointing to a different code region of its parent process.
On Windows, threads and processes are two separate entities, so the above description for Linux does not apply. However, the general idea holds: a thread shares the execution environment.
Our kernel follows the Linux view. There is one structure,
struct task, for everything that can be scheduled. A
kernel thread is a task that runs kernel code in ring 0 with
the kernel page directory; a user task is a task that runs ring
3 code with a page directory of its own. The scheduler does not care
which is which.
13.2 What a context is on x86
13.2.1 The Intel manual’s task
Open the Intel SDM Volume 3A, chapter 10 “Task Management”. Section
10.1 “Task Management Overview” defines a task exactly as we did above,
“a unit of work that a processor can dispatch, execute, and suspend”,
and then describes a complete hardware mechanism for switching between
them: a task is described by a Task-State Segment (TSS), a
system segment whose layout is figure 10-2 in section 10.2.1 “Task-State
Segment (TSS)”, and a task switch (section 10.3 “Task
Switching”) is an operation in which the processor saves every
register into the current TSS, loads every register from the new TSS,
and goes on. A task switch is triggered by a far jmp or
call to a TSS descriptor or to a task gate
(section 10.2.5), or by an interrupt whose IDT entry is a task gate.
Read 10.1 to 10.3 now: it is about fifteen pages, and the TSS layout is
needed below whatever we decide to do with it.
Figure 10-2 shows the 104-byte TSS. Reading it from offset 0 upward:
a link to the previous task; three ESP/SS
pairs for privilege levels 0, 1 and 2; CR3;
EIP and EFLAGS; the eight general registers;
the six segment registers; the LDT selector; a trap bit; and the offset
of an I/O permission bitmap. It is, quite literally, a process structure
designed in silicon, for a design of operating systems in which each
process is a task, each task has a TSS, and the kernel switches with one
instruction.
13.2.2 Why we do not use hardware task switching
No modern kernel uses this mechanism, and neither do we, for three reasons.
It is slow. A hardware task switch saves and restores all the
registers, all the segment registers (which means reloading their hidden
descriptor caches, see chapter 9), and CR3 (which flushes
the TLB), whether or not the new task needs any of that. A kernel that
switches in software saves only what the calling convention does not
already protect, and, as we will see, that is four registers and the
flags.
It is inflexible. The processor saves what figure 10-2 says it saves, nothing more and nothing less. A kernel keeps far more per task than the registers (the page directory it already has, the open files, the accounting), so it needs a structure of its own anyway, and then the TSS is a second copy of part of it.
It does not exist in 64-bit mode. Section 10.7 “Task Management in 64-bit Mode” says it in one sentence: “task switches are not supported”. The 64-bit TSS (figure 10-11) keeps only the stack pointers for privilege transitions and an interrupt stack table. A kernel that relies on hardware task switching cannot be ported to long mode; chapter 17, Epilogue, comes back to this.
13.2.3 The one TSS we need
What remains of chapter 10 for us is section 10.2.1, the fields
ESP0 and SS0, and the reason is in chapter 7
“Interrupt and Exception Handling”, section 7.12.1 “Exception- or
Interrupt-Handler Procedures”, under “Stack Switching”: when an
interrupt or exception occurs while the processor runs at privilege
level 3, the handler runs at level 0, and the processor must not
keep using the user program’s stack (the program could have set
ESP to anything, and the kernel would push its state
wherever that pointed). So the processor switches stacks: it
loads SS and ESP from the SS0 and
ESP0 fields of the current TSS, pushes the old
SS and ESP on the new stack, and only then
pushes EFLAGS, CS and EIP. Figure
7-4 “Stack Usage on Transfers to Interrupt and Exception-Handling
Routines” draws both cases side by side; chapter 11 showed the left one
(no privilege change), and this chapter is the right one. The processor
finds the current TSS through the task register (section
10.2.4), loaded with ltr, which is the one task-management
instruction we execute. Section 6.8 “Privilege Level Checking When
Transferring Program Control Between Code Segments” describes the same
stack switch for call gates; we never use call gates, but the rule that
“a transfer to a more privileged level always switches to a stack owned
by that level” is the thing to remember.
So the kernel has one TSS, for the whole system, and uses two of its fields. Here it is:
os/tss.h
#ifndef TSS_H
#define TSS_H
#include <stdint.h>
/* The 32-bit Task-State Segment, Intel SDM Vol. 3A, section 10.2.1
"Task-State Segment (TSS)", Figure 10-2. It was designed for hardware
task switching, which nobody uses; what every OS still needs from it is
ss0:esp0, the stack the CPU switches to when an interrupt or a system
call arrives while ring 3 code is running (SDM Vol. 3A, section 7.12.1
"Exception- or Interrupt-Handler Procedures", "Stack Switching"). */
struct tss {
uint32_t prev_task_link;
uint32_t esp0; /* kernel stack pointer for ring 0 entry */
uint32_t ss0; /* kernel stack segment */
uint32_t esp1, ss1; /* rings 1 and 2: unused */
uint32_t esp2, ss2;
uint32_t cr3;
uint32_t eip, eflags;
uint32_t eax, ecx, edx, ebx, esp, ebp, esi, edi;
uint32_t es, cs, ss, ds, fs, gs;
uint32_t ldt_selector;
uint16_t trap; /* bit 0: raise #DB on a task switch */
uint16_t iomap_base; /* offset of the I/O permission bitmap */
} __attribute__((packed));
void tss_init(void);
/* Called by the scheduler before switching to a task: the next interrupt
from ring 3 must land on that task's own kernel stack. */
void tss_set_kernel_stack(uint32_t esp0);
#endifCompare the structure with figure 10-2 field by field, as we did for
the segment descriptor in chapter 9: 26 doublewords and two words, 104
bytes, 0x68. The segment registers are 32-bit fields of
which only the low 16 bits are meaningful, as the figure’s shaded upper
halves show.
os/tss.c
/* tss.c -- one TSS for the whole kernel.
*
* We never use hardware task switching: the scheduler saves and restores
* registers itself (switch.asm). The TSS exists because the CPU insists
* on reading the ring 0 stack pointer from it on every transition from
* ring 3 to ring 0.
*/
#include "tss.h"
#include "gdt.h"
#include "string.h"
static struct tss tss;
void tss_init(void)
{
memset(&tss, 0, sizeof(tss));
tss.ss0 = GDT_KERNEL_DATA;
tss.esp0 = 0; /* set per task by the scheduler */
/* No I/O permission bitmap: an offset past the segment limit means
"none", and then IN/OUT from ring 3 always fault (SDM Vol. 1,
section 20.5.2 "I/O Permission Bit Map"). */
tss.iomap_base = sizeof(tss);
gdt_set_tss((uint32_t)&tss, sizeof(tss) - 1);
/* LTR loads the task register with the selector of the TSS descriptor
(SDM Vol. 3A, section 10.2.4 "Task Register"); the descriptor is
marked "busy" from then on. */
asm volatile("ltr %%ax" : : "a"(GDT_TSS));
}
void tss_set_kernel_stack(uint32_t esp0)
{
tss.esp0 = esp0;
}SS0 is the kernel data selector and never changes.
ESP0 is the interesting field: it must point to the kernel
stack of whatever task is currently running in ring 3, so the
scheduler rewrites it at every switch, which is what
tss_set_kernel_stack is for. The iomap_base
detail is worth a minute: the TSS may be followed by a bitmap with one
bit per I/O port, and the processor consults it when ring 3 code
executes in or out (Volume 1, section 20.5.2).
An offset at or beyond the segment limit means “no bitmap”, and then
every port access from ring 3 raises #GP. That is exactly
what we want: a user program must not talk to the serial port behind the
kernel’s back.
13.2.4 The TSS descriptor and the user segments
A TSS is a segment, so it needs a descriptor in the GDT, and
ltr takes the selector of that descriptor. Section 10.2.2
“TSS Descriptor” and figure 10-3 show that it is the ordinary 8-byte
descriptor of chapter 9 with S = 0 (a system segment) and
Type = 1001, “32-bit TSS, available”; after
ltr the processor changes it to 1011, “busy”,
which QEMU will show us. While we are in the GDT, this chapter also
needs code and data segments that ring 3 may use. gdt.h
gains three selectors and gdt.c three entries:
os/gdt.h (additions)
#define GDT_USER_CODE 0x18
#define GDT_USER_DATA 0x20
#define GDT_TSS 0x28
/* The selectors ring 3 code runs with: the same descriptors with the
requested privilege level (bits 0-1) set to 3. Loading a DPL 3 segment
with RPL 0 is refused by the CPU (SDM Vol. 3A, section 6.5 "Privilege
Levels"). */
#define GDT_USER_CODE_RPL3 (GDT_USER_CODE | 3)
#define GDT_USER_DATA_RPL3 (GDT_USER_DATA | 3)os/gdt.c (additions)
#define ACC_RING3 0x60 /* DPL = 3 */
#define ACC_TSS32 0x09 /* system segment, type 9 = 32-bit TSS, available
(SDM Vol. 3A, section 3.5 "System Descriptor
Types", Table 3-2) */static struct gdt_entry gdt[6]; /* Ring 3 segments: identical except for the DPL. */
gdt_set_entry(3, 0, 0xFFFFF,
ACC_PRESENT | ACC_RING3 | ACC_CODE_DATA | ACC_EXEC | ACC_RW,
GRAN_4K | GRAN_32BIT);
gdt_set_entry(4, 0, 0xFFFFF,
ACC_PRESENT | ACC_RING3 | ACC_CODE_DATA | ACC_RW,
GRAN_4K | GRAN_32BIT);
/* Entry 5, the TSS, is filled by tss_init(). */void gdt_set_tss(uint32_t base, uint32_t limit)
{
/* A system segment: S = 0, so the access byte is P | DPL | 0 | type.
The limit is in bytes (G = 0) and the segment is not a code or data
segment, so D/B does not apply. */
gdt_set_entry(GDT_TSS / 8, base, limit, ACC_PRESENT | ACC_RING0 | ACC_TSS32, 0);
}The user segments are the same flat segments as the
kernel’s, base 0 and limit 4 GiB, with DPL = 3 instead
of 0: the access byte is 0xFA for code and
0xF2 for data, where chapter 9 had 0x9A and
0x92. This looks pointless, and from the point of view of
memory protection it is: a ring 3 program with a 4 GiB data segment can
address every byte of memory, and segmentation will not stop it. Paging
will (the USER bit, chapter 12), and it does a far better job. The
reason the DPL 3 descriptors must exist is different: the processor
defines the current privilege level as the RPL of the selector
in CS (section 6.5), and the only way to get
CPL = 3 is to load CS with a selector whose
descriptor has DPL = 3. Example 9.2 computed the selector:
entry 3 at RPL 3 is 0x1b; entry 4 at RPL 3 is
0x23. With RPL 0, 0x18 and 0x20,
the processor refuses the load (section 6.6: a data segment may be
loaded only if DPL >= max(CPL, RPL), and the symmetric
rule for CS), which is why both forms are defined in
gdt.h.
The GDT now has six entries, 48 bytes, so the GDTR limit becomes
0x2f, and ltr with 0x28 names the
sixth. We will read all of it back from QEMU at the end of the
chapter.
13.3 Kernel threads
13.3.1 struct task
os/task.h
#ifndef TASK_H
#define TASK_H
#include <stdint.h>
/* A task is a thread of execution with its own kernel stack. Kernel
threads run ring 0 code on that stack; user tasks run ring 3 code on a
user stack in their own page directory and only use the kernel stack
while they are inside a system call or an interrupt handler. */
enum task_state {
TASK_READY, /* waiting for the CPU */
TASK_RUNNING, /* the task current_task points to */
TASK_SLEEPING, /* waiting for the tick in wake_at; the timer wakes it */
TASK_DEAD /* exited; waiting for the idle task to free it */
};
struct task {
int id;
enum task_state state;
uint32_t esp; /* saved kernel ESP while not running */
void *kernel_stack; /* KERNEL_STACK_SIZE bytes from kmalloc() */
uint32_t *page_directory; /* loaded into CR3 when the task runs */
const char *name;
struct task *next; /* circular run queue */
void (*entry)(void); /* where the task starts */
uint32_t user_stack_top; /* user tasks: initial ESP for ring 3 */
uint32_t wake_at; /* TASK_SLEEPING: the tick to wake up at */
};
#define KERNEL_STACK_SIZE 4096
/* The user stack of every user task is mapped just below this address
in the task's own page directory. */
#define USER_STACK_TOP 0x80000000
#define USER_STACK_SIZE 4096
extern struct task *current_task;
/* Turn the code running kmain into task 0, the idle task. */
void task_init(void);
struct task *task_create(const char *name, void (*entry)(void));
struct task *task_create_user(const char *name, void (*entry)(void));
/* Pick the next ready task and switch to it. Must be called with
interrupts disabled; returns when this task is scheduled again. */
void schedule(void);
void yield(void);
/* Put the current task to sleep for `nticks` timer ticks (chapter 13,
"Timekeeping and sleeping"). Returns once the timer handler has woken
it and the scheduler has picked it again. */
void task_sleep(uint32_t nticks);
/* Called by the timer handler on every tick: make every sleeping task
whose time has come ready. Returns how many were woken. */
int task_wake_sleepers(void);
/* Mark the current task dead and never return to it. */
void task_exit(void) __attribute__((noreturn));
/* Free dead tasks; returns how many tasks other than idle still exist. */
int task_reap(void);
/* switch.asm */
void context_switch(uint32_t *old_esp, uint32_t new_esp);
void enter_user_mode(uint32_t eip, uint32_t esp) __attribute__((noreturn));
#endifThe structure is small (ignore wake_at,
task_sleep and task_wake_sleepers until the
section on sleeping), and the most important field is the least
impressive: esp. A task that is not running has all its
registers on its own kernel stack, pushed there by the code
that switched it out, and the task structure only needs to remember
where that stack ended. Everything else follows from that idea. Each
task has a kernel stack of one page, allocated with
kmalloc, which means that it lives in the heap at
0xC0000000 and up (chapter 12). The idle task is special:
it is kmain itself, whose stack is the original one at
0x90000 set up by entry.asm, and
task_init only fills in a structure for it.
13.3.2 The first switch: a prepared stack
How does a task that has never run get started, if “resuming” a task
means popping its registers off its stack? By building the stack it
would have had if it had been switched out at the right moment.
That is what task_alloc does:
os/task.c (first part)
struct task *current_task;
static struct task idle_task;
static int next_id = 1;
extern char __user_start[], __user_end[]; /* os.lds: the .user section */
/* A new task's stack is prepared so that the first context_switch() to
it pops zeros into the callee-saved registers, an EFLAGS with IF set,
and "returns" into one of these two functions. */
static void kernel_thread_start(void)
{
current_task->entry();
task_exit();
}
static void user_task_start(void)
{
enter_user_mode((uint32_t)current_task->entry, current_task->user_stack_top);
}
void task_init(void)
{
idle_task.id = 0;
idle_task.state = TASK_RUNNING;
idle_task.kernel_stack = (void *)(0x90000 - KERNEL_STACK_SIZE); /* entry.asm */
idle_task.page_directory = paging_kernel_directory();
idle_task.name = "idle";
idle_task.next = &idle_task;
current_task = &idle_task;
}
/* Allocate the task and its kernel stack, build the initial stack frame
(see context_switch in switch.asm for the layout, read bottom-up) and
insert the task in the run queue. */
static struct task *task_alloc(const char *name, void (*entry)(void),
void (*start)(void), uint32_t *dir)
{
struct task *t = kmalloc(sizeof(*t)), *last;
uint32_t *sp;
uint32_t flags;
memset(t, 0, sizeof(*t));
t->id = next_id++;
t->state = TASK_READY;
t->name = name;
t->entry = entry;
t->page_directory = dir;
t->kernel_stack = kmalloc(KERNEL_STACK_SIZE);
sp = (uint32_t *)((char *)t->kernel_stack + KERNEL_STACK_SIZE);
*--sp = (uint32_t)start; /* popped by RET at the end of context_switch */
*--sp = 0; /* EBP */
*--sp = 0; /* EBX */
*--sp = 0; /* ESI */
*--sp = 0; /* EDI */
*--sp = 0x202; /* EFLAGS: IF = 1, bit 1 always 1
(SDM Vol. 1, section 3.4.3 "EFLAGS Register") */
t->esp = (uint32_t)sp;
/* Append at the tail of the circular queue, i.e. just before idle,
so that tasks first run in the order they were created. */
flags = irq_save();
for (last = &idle_task; last->next != &idle_task; last = last->next)
;
t->next = &idle_task;
last->next = t;
irq_restore(flags);
return t;
}
struct task *task_create(const char *name, void (*entry)(void))
{
return task_alloc(name, entry, kernel_thread_start, paging_kernel_directory());
}Six words are pushed on the fresh stack, from the top down: the
address of a start function, four zeros, and
0x202. To see why these six and in this order, read
context_switch next; the short version is that
context_switch ends with five pops and a ret,
and these are the six values they will pop. The start function is
kernel_thread_start for a kernel thread: it calls the
task’s entry function and, when that returns, task_exit, so
that a thread whose function simply returns is cleaned up instead of
returning into nothing. (For a user task the start function is
user_task_start, which goes to ring 3; we come to it
later.) current_task->entry rather than an argument,
because a function reached by ret has no arguments: nobody
pushed any.
The value 0x202 deserves attention. Bit 1 of
EFLAGS is always 1 (Volume 1, section 3.4.3), and bit 9 is
IF, the interrupt-enable flag. schedule() is
always entered with interrupts disabled, as we will see, so the
popfd that loads this value into EFLAGS is
the instruction that first enables interrupts for the new task.
Push 0x2 here instead and the new thread runs with
interrupts off until something turns them on, which for
thread_a is never: the timer cannot preempt it.
The last lines append the task at the tail of the circular
run queue, just before idle_task. The first version of this
code inserted the new task right after current_task, which
is simpler, and ran the tasks in reverse order of creation: each new
task was inserted in front of the previous one. The loop with
irq_save and irq_restore around it costs a few
lines and gives the natural order.
13.3.3 context_switch,
line by line
os/switch.asm (first part)
;******************************************************************************
; switch.asm -- the two places where a task's registers are replaced wholesale.
;******************************************************************************
bits 32
section .text
;------------------------------------------------------------------------------
; void context_switch(uint32_t *old_esp, uint32_t new_esp)
;
; Save the current task's registers on its stack, store its ESP through
; old_esp, load new_esp and restore the other task's registers from there.
; The RET at the end then pops the other task's return address: either
; the place where IT called context_switch(), or, for a task that never ran,
; the start function task.c put on its fresh stack.
;
; Only EBX, ESI, EDI and EBP are saved. The System V i386 ABI makes them
; "callee-saved": a called function must preserve them. EAX, ECX and EDX
; are "caller-saved": the compiler assumes any function call may destroy
; them, so the C code in schedule() has already saved what it needs
; (System V ABI i386 supplement, section 3.2.1 "Registers"). EIP is the
; return address and ESP is what we swap. EFLAGS is saved so that the
; interrupt-enable flag returns with the task that owns it.
;
; Stack of a task that is not running, lowest address first, as the
; "pops" below read it:
; EFLAGS, EDI, ESI, EBX, EBP, return address
;------------------------------------------------------------------------------
global context_switch
context_switch:
mov eax, [esp + 4] ; old_esp
mov edx, [esp + 8] ; new_esp
push ebp
push ebx
push esi
push edi
pushfd
mov [eax], esp ; the old task is now frozen here
mov esp, edx ; from here on we are the new task
popfd
pop edi
pop esi
pop ebx
pop ebp
retThis is the whole context switch: fifteen instructions, and the
comment is longer than the code. It is a C function with the usual
calling convention of chapter 4, so on entry the stack holds the return
address at [esp] and the two arguments above it. It pushes
four registers and the flags, stores the resulting ESP into
*old_esp, loads ESP from new_esp,
and pops the same five things from the other stack. The
ret then pops a return address from the other
stack, and that is the moment the switch happens: execution
continues wherever the other task was when it called
context_switch (or, for a brand new task, at its start
function, since task_alloc put that address where a return
address would be).
Why only EBX, ESI, EDI and
EBP? Because context_switch is a function, and
the System V i386 ABI (chapter 3 “Low-Level System Information”,
“Function Calling Sequence”, table of register usage) says which
registers a function must leave as it found them: these four, plus
ESP. The other three, EAX, ECX
and EDX, may be destroyed by any call, and the compiler
knows it: when schedule() calls
context_switch, gcc has already made sure that
nothing it needs afterwards is in those three. So from the caller’s
point of view, context_switch is an ordinary function that
happens to take a very long time to return (until the task is scheduled
again), and the only state that has to survive is the state any function
must preserve. EIP is saved by the call
instruction itself, as the return address. ESP is the one
thing stored in struct task. EFLAGS is not
part of the ABI contract, but it carries IF, and we want
each task to resume with interrupts in the state it had; it costs one
pushfd.
Compare with the 104 bytes a hardware task switch moves: this is 24
bytes, and no segment register is touched because every kernel thread
runs with the same flat selectors. The CS, DS
and the other segment registers of a user task are saved too,
but not here: they are saved by the interrupt that brought it into the
kernel, on the kernel stack, in the struct registers of
chapter 11, and iret restores them. By the time
context_switch runs, every task is in ring 0 with the
kernel’s selectors.
13.3.4 Ending a task
os/task.c (task_exit and
task_reap)
void task_exit(void)
{
asm volatile("cli");
current_task->state = TASK_DEAD;
schedule();
panic("task_exit: a dead task was scheduled");
}
int task_reap(void)
{
uint32_t flags = irq_save();
struct task *prev = &idle_task, *t = idle_task.next;
int alive = 0;
while (t != &idle_task) {
struct task *next = t->next;
if (t->state == TASK_DEAD) {
prev->next = next; /* unlink */
if (t->page_directory != paging_kernel_directory())
paging_free_directory(t->page_directory);
kfree(t->kernel_stack);
kfree(t);
} else {
alive++;
prev = t;
}
t = next;
}
irq_restore(flags);
return alive;
}A task cannot free its own kernel stack: it is standing on it. So
task_exit only marks the task dead and schedules;
schedule() skips dead tasks and never returns to this one,
and the panic after it documents that. The actual freeing
is done later, by someone else, on another stack: the idle task calls
task_reap from its loop in kmain, unlinks the
dead tasks from the queue, and returns their memory. This split between
“exit” and “reap” exists in every kernel; on Unix it is the reason for
zombie processes, which have exited but whose parent has not
yet collected them.
13.4 The scheduler
13.4.1 Round robin
The scheduling policy of this chapter is the simplest one that works:
round robin. The tasks form a circle, the circular list through
next, and schedule() hands the processor to
the next task in the circle that is neither dead nor asleep. No
priorities, no measurement of how long a task has run. Every task gets
the processor in turn, for at most a time slice, and a task that gives
it up early simply lets the circle advance sooner.
os/task.c (schedule and
yield)
void schedule(void)
{
struct task *prev = current_task, *next;
if (prev == 0)
return; /* a timer tick before task_init() */
next = prev->next;
while (next->state == TASK_DEAD || next->state == TASK_SLEEPING)
next = next->next; /* idle never sleeps or dies, so this ends */
if (next == prev)
return;
if (prev->state == TASK_RUNNING)
prev->state = TASK_READY;
next->state = TASK_RUNNING;
current_task = next;
/* If `next` is interrupted in ring 3, the CPU must find its kernel
stack in the TSS. The stack is empty at that moment: the task is
either in ring 3 or about to go there, so start from the top. */
tss_set_kernel_stack((uint32_t)next->kernel_stack + KERNEL_STACK_SIZE);
if (next->page_directory != prev->page_directory)
paging_switch_directory(next->page_directory);
context_switch(&prev->esp, next->esp);
/* We are back: some later schedule() switched to us again. */
}
void yield(void)
{
uint32_t flags = irq_save();
schedule();
irq_restore(flags);
}Read schedule() as four steps. Choose next.
Update the bookkeeping: the states, and current_task, which
from here on names the task that is about to run. Prepare the
processor for next: its kernel stack top goes into the TSS,
and its page directory into CR3 if it differs from the
current one (switching CR3 flushes the TLB, so we avoid it
between two kernel threads, which share the kernel directory). And
switch. The line after context_switch is the first line
that runs when this task is scheduled again, possibly much later, from a
schedule() call made by some other task; everything on this
task’s stack is exactly as it was.
The TSS.esp0 update is the subtle one. The kernel stack
of a user task is empty whenever the task runs in ring 3: it
was entered through an interrupt or int 0x80, the handler
ran, and iret emptied it again on the way out. So “the top
of the kernel stack” is always the right value for ESP0,
and it must be the top of this task’s stack, because the next
interrupt from ring 3 will push there. Forget this line and the next
system call of task 4 pushes its frame on the kernel stack of task 3. A
kernel thread never needs ESP0, since an interrupt in ring
0 stays on the current stack, but setting it costs nothing.
yield() is schedule() for callers that run
with interrupts enabled: it disables them, switches, and restores them
when the task comes back. The comment in task.h is the
contract: schedule() must be called with interrupts
disabled. There are four callers, and each satisfies it in its own
way: the timer handler (interrupt gate, so IF is already
clear), yield() (cli through
irq_save), task_exit (explicit
cli), and task_sleep of the next sections
(irq_save again). The system call handler is a fifth, and
it is in the first category too.
13.4.2 Preemption: the timer handler and the EOI
os/pit.c (changes)
/* Chapter 13: a task runs for at most this many ticks (100 ms at 100 Hz)
before the next one gets the CPU. schedule() does not return until
this task is picked again; the IRET at the end of isr_common then
resumes whatever it was doing. */
#define SCHEDULE_TICKS 10
static void irq0_handler(struct registers *regs)
{
(void)regs;
ticks++;
/* A task whose sleep just ended should not wait for the end of the
current time slice, so a wake-up also triggers a switch. Both
calls happen with IF clear (interrupt gate), as schedule() requires. */
if (task_wake_sleepers() > 0 || ticks % SCHEDULE_TICKS == 0)
schedule();
}This is preemption. (Read past task_wake_sleepers() for
now: it belongs to the section “Timekeeping and sleeping” and returns 0
until a task sleeps.) Every tenth tick the timer handler calls
schedule(), which calls context_switch, which
does not return until the interrupted task is picked again. The task
being interrupted does not know: from its point of view, an instruction
took a tenth of a second. Look at where it happens, though: inside
an interrupt handler, with the interrupt frame on the stack and the
iret of isr_common still to come. The whole
interrupt frame, struct registers included, stays on that
task’s kernel stack, under the five words context_switch
pushed, and is popped only when the task resumes and
isr_common finishes. This works precisely because every
task has its own kernel stack.
It also forces one change in isr.c, which chapter 11
placed at the end of the dispatcher:
os/isr.c (isr_dispatch)
void isr_dispatch(struct registers *regs)
{
isr_handler_t handler = handlers[regs->int_no];
/* Tell the PIC the interrupt has been handled so it can send the next
one; without this the IRQ line stays blocked forever. The EOI is
sent BEFORE the handler (chapter 13): the timer handler may switch
to another task and only come back here much later, and in the
meantime the PIC would deliver no more timer interrupts. Nothing
can nest: IF stays clear until IRET (interrupt gate). */
if (regs->int_no >= IRQ_BASE && regs->int_no < IRQ_BASE + 16)
pic_send_eoi(regs->int_no - IRQ_BASE);
if (handler != 0) {
handler(regs);
} else if (regs->int_no < 32) {
kprintf("\nException %d: %s (error code 0x%x)\n",
regs->int_no, exception_names[regs->int_no], regs->err_code);
dump_registers(regs);
kprintf("System halted.\n");
for (;;)
asm volatile("cli; hlt");
}
}The end-of-interrupt command moved from after the handler to before
it. Chapter 11 explained what the EOI does: until the PIC receives it,
IRQ 0 is “in service” and the PIC raises no further IRQ 0. Now follow
the first timer-driven switch with the EOI still at the end. Tick 10
arrives while kmain runs; irq0_handler calls
schedule(), which switches to thread A. Thread A runs with
interrupts enabled (its EFLAGS says so), but no timer
interrupt ever arrives: the PIC is still waiting for the EOI of
tick 10, and the code that would send it is on the idle task’s stack,
waiting to be resumed. If thread A never yields, that is the end of
multitasking. Sending the EOI first makes the PIC ready to deliver tick
11 to whichever task is running then. Is it safe? The danger of an early
EOI is a nested interrupt, the same handler running on top of itself; it
cannot happen here, because the gate is an interrupt gate,
IF is clear from the moment the processor entered
isr0 until its iret, and a tick that arrives
in between is simply held by the PIC. (A hlt with
interrupts disabled would hang, which is why panic and the
halt loop above use cli; hlt deliberately, and nothing else
does.)
13.4.3 Critical
sections: irq_save and irq_restore
os/irq.h
#ifndef IRQ_H
#define IRQ_H
#include <stdint.h>
/* Disable interrupts while touching data that an interrupt handler also
touches (the run queue, chapter 13). irq_save() returns the old EFLAGS
so that irq_restore() can put IF back the way it was, which matters
when the caller itself runs with interrupts already disabled. */
static inline uint32_t irq_save(void)
{
uint32_t flags;
asm volatile("pushf; pop %0; cli" : "=r"(flags) : : "memory");
return flags;
}
static inline void irq_restore(uint32_t flags)
{
asm volatile("push %0; popf" : : "r"(flags) : "memory", "cc");
}
#endifPreemption creates a new kind of bug. task_alloc walks
the run queue to find its tail and links a new task in; if the timer
fires between the walk and the link, schedule() walks the
same list while it is half modified. The list is shared between ordinary
code and an interrupt handler, and the only way to make a sequence of
operations on it atomic on a single processor is to keep the
handler from running: disable interrupts around the sequence, a
critical section. irq_save saves
EFLAGS and clears IF; irq_restore
puts the saved EFLAGS back, which re-enables interrupts
only if they were enabled before. The pair is better than a bare
cli/sti because it nests: a function that is
sometimes called with interrupts already disabled (as
schedule() is) would otherwise enable them by mistake on
its way out.
kprintf has no such protection, and it is the one known
weakness of this chapter: a tick that lands in the middle of a
kprintf in thread A can run thread B, whose
kprintf then mixes its characters with A’s. It does not
happen in the test, because each thread prints a short line and yields
long before its time slice ends, but nothing prevents it. Exercise 13.3
fixes it with the two functions above.
13.4.4 The idle task
os/kernel.c (the end of kmain)
task_create("thread A", thread_a);
task_create("thread B", thread_b);
task_create_user("user hello", user_hello);
task_create_user("user counter", user_counter);
task_create_user("user rogue", user_rogue);
task_create_user("user sleeper", user_sleeper);
task_create_user("user rogue write", user_rogue_write);
/* kmain is now the idle task: it gives up the CPU and frees what the
other tasks leave behind. HLT with interrupts enabled sleeps until
the next interrupt; the timer then calls schedule(). */
for (;;) {
if (task_reap() == 0)
break;
asm volatile("hlt");
}
/* Fewer frames than before: the heap grew to hold the kernel stacks
and keeps its pages; the frames of the tasks themselves (page
directories, user stacks) came back. */
kprintf("all tasks finished, %u frames free\n", pmm_free_frames_count());
for (;;)
asm volatile("hlt");A round-robin scheduler needs at least one task that is always ready,
otherwise schedule() has nowhere to go when every other
task is dead or waiting. That task is the idle task, and here
it is kmain itself after it has created the others: it
reaps dead tasks and executes hlt, which stops the
processor until the next interrupt (chapter 11). The next timer tick
wakes it, the handler may call schedule(), and if no other
task is ready, schedule() returns to the idle loop
immediately (next == prev). On a laptop, this
hlt is where the processor spends most of its life, and it
is why an idle machine is cool and quiet.
13.4.5 Thread A and thread B
os/kernel.c (the threads)
/* Two kernel threads. yield() hands the CPU to the next task, so their
lines come out interleaved. */
static void thread_a(void)
{
int i;
for (i = 1; i <= 3; i++) {
kprintf("thread A: %d\n", i);
yield();
}
}
static void thread_b(void)
{
int i;
for (i = 1; i <= 3; i++) {
kprintf("thread B: %d\n", i);
yield();
}
}The two kernel threads are the “Hello World” of multitasking: each
prints a line and yields, three times, and returns, so
kernel_thread_start calls task_exit for it.
Their lines interleave in the output, A then B, which is the run queue
order. Note that thread_a is a plain C function that knows
nothing about tasks; the yield() call is the only hint.
This is what a cooperative thread looks like; remove the
yield() and the timer still interleaves them, just in
slices of a tenth of a second.
13.5 User mode
13.5.1 Privilege levels, again
Chapter 9 introduced the three numbers CPL,
DPL and RPL and promised to come back to them
when the first user program runs. Here is the whole protection model of
this chapter in three rules, all from the Intel SDM Volume 3A, chapter 6
“Protection”:
The current privilege level is the RPL of
CS(section 6.5). Code runs in ring 3 if and only ifCSholds a selector such as0x1b.Ring 3 code can load into a data segment register only a descriptor with
DPL = 3(section 6.6), can executeint nonly through a gate withDPL = 3(section 7.12.1.2), and can access a page only if the USER bit is set in both its page-directory entry and its page-table entry (section 5.6 “Access Rights”, chapter 12). Privileged instructions (lgdt,ltr,mov cr3,hlt,cli,in,out…) raise#GPin ring 3 (section 6.9 and, for I/O, Volume 1 section 20.5).The only ways from ring 3 to ring 0 are the gates of the IDT, interrupts and exceptions, and the only way back is
iret(sections 6.8 and 7.12.1). On every transition from 3 to 0 the processor switches to the stack inTSS.ESP0.
Nothing in this list involves the segment limits; with flat segments, the memory protection is done by rule 2’s USER bit, which is to say by paging.
13.5.2 A page directory per task
os/task.c (task_create_user)
struct task *task_create_user(const char *name, void (*entry)(void))
{
uint32_t *dir = paging_clone_kernel_directory();
uint32_t addr, frame;
struct task *t;
/* The user program's code and data are part of the kernel image
(os.lds collects userprog.c into the page-aligned .user section);
giving those pages the USER bit is what lets ring 3 execute them.
Every other kernel page stays supervisor-only. */
for (addr = (uint32_t)__user_start; addr < (uint32_t)__user_end; addr += PAGE_SIZE)
paging_map_in(dir, addr, addr, PAGE_WRITE | PAGE_USER);
/* One page of user stack, in a fresh frame. */
frame = pmm_alloc_frame();
if (frame == 0)
panic("task_create_user: out of frames");
paging_map_in(dir, USER_STACK_TOP - USER_STACK_SIZE, frame, PAGE_WRITE | PAGE_USER);
t = task_alloc(name, entry, user_task_start, dir);
t->user_stack_top = USER_STACK_TOP;
return t;
}A user task is a kernel thread plus three things: a page directory of
its own, user-accessible pages for its code, and a user stack. The
directory comes from three new functions in paging.c:
os/paging.c (additions)
uint32_t *paging_kernel_directory(void)
{
return kernel_directory;
}
uint32_t *paging_clone_kernel_directory(void)
{
uint32_t frame = pmm_alloc_frame();
if (frame == 0)
panic("paging: out of frames for a page directory");
memcpy((void *)frame, kernel_directory, PAGE_SIZE);
return (uint32_t *)frame;
}
void paging_free_directory(uint32_t *dir)
{
uint32_t i, j;
for (i = 0; i < 1024; i++) {
uint32_t *table;
if (!(dir[i] & PAGE_PRESENT))
continue;
if ((dir[i] & PAGE_FRAME) == (kernel_directory[i] & PAGE_FRAME))
continue; /* shared with the kernel */
table = (uint32_t *)(dir[i] & PAGE_FRAME);
for (j = 0; j < 1024; j++)
if (table[j] & PAGE_PRESENT)
pmm_free_frame(table[j] & PAGE_FRAME);
pmm_free_frame((uint32_t)table);
}
pmm_free_frame((uint32_t)dir);
}
void paging_switch_directory(uint32_t *dir)
{
asm volatile("mov %0, %%cr3" : : "r"(dir) : "memory");
}
int paging_user_accessible(uint32_t *dir, uint32_t virt)
{
uint32_t pde = dir[PAGE_DIR_INDEX(virt)], pte;
if ((pde & (PAGE_PRESENT | PAGE_USER)) != (PAGE_PRESENT | PAGE_USER))
return 0;
pte = ((uint32_t *)(pde & PAGE_FRAME))[PAGE_TABLE_INDEX(virt)];
return (pte & (PAGE_PRESENT | PAGE_USER)) == (PAGE_PRESENT | PAGE_USER);
}Cloning the kernel directory is a 4 KiB memcpy: the new
directory has the same 1024 entries, so it points to the same page
tables as the kernel’s. The kernel is therefore mapped, at the same
addresses, in every task, which is what makes system calls possible (the
handler runs with the task’s directory loaded) and what keeps the
kernel’s data out of reach (those entries have no USER bit). The copy is
shallow by design, but it has one consequence to keep in mind: the two
directories share only the page tables that exist at the time of the
clone. If the kernel later creates a page table, by mapping a page
in a 4 MiB region that had no table yet, the new table appears in the
kernel directory only. The heap is the one region that grows at run
time, and heap_init maps its first page, which creates the
heap’s page table, before any task exists; HEAP_MAX is 4
MiB, exactly one page table, so the heap can never need a second one.
Every task sees every later heap page. A kernel that grows in more
places would need to copy the new entries into every directory, or to
keep the kernel’s part of the directories in sync in some other way.
paging_map_in is map_in of chapter 12 made
public, with one subtlety visible in get_table: when a page
is mapped with PAGE_USER into a table that already exists,
the USER bit is also set on the directory entry, because both
levels must allow an access. For the .user pages this
changes the entry of the first page table in the task’s directory, not
in the kernel’s, but it does change the page table entries, which are
shared: the .user pages become user-accessible in every
directory. That is harmless, since the kernel directory’s own entry 0
still lacks the USER bit, and no task runs ring 3 code with the kernel
directory anyway; we will see both entries in the debugger.
The user stack is one page, in a fresh frame, mapped at
0x7FFFF000, just below
USER_STACK_TOP = 0x80000000. This address is in a region
the kernel directory has no page table for, so get_table
creates one, and that table belongs to this task alone;
paging_free_directory recognizes it as private because its
entry differs from the kernel’s, and frees its frames and the table
itself. The code pages, on the other hand, are shared with the kernel
and are left alone.
13.5.3 Entering ring 3 with
iret
There is no instruction that calls a less privileged ring.
call and jmp through a gate go up in
privilege; the only instruction that goes down is a return,
retf or iret, because a return to an outer
level is the normal end of a system call. So to run the first ring 3
instruction, the kernel pretends it is returning from an interrupt that
happened in ring 3:
os/switch.asm (second part)
;------------------------------------------------------------------------------
; void enter_user_mode(uint32_t eip, uint32_t esp)
;
; There is no instruction that "calls" ring 3; the way in is to pretend we
; are returning from an interrupt that happened in ring 3. IRET pops EIP,
; CS, EFLAGS and, because the new CS has a lower privilege, also ESP and SS
; (Intel SDM Vol. 2A, "IRET/IRETD", "RETURN-TO-OUTER-PRIVILEGE-LEVEL").
; We push those five words by hand and execute IRET. The data segments
; are set first: a ring 3 task must not keep a ring 0 data selector (the
; CPU would fault on the first use anyway; SDM Vol. 3A, section 6.6
; "Privilege Level Checking When Accessing Data Segments").
;------------------------------------------------------------------------------
GDT_USER_CODE_RPL3 equ 0x1B ; gdt.h
GDT_USER_DATA_RPL3 equ 0x23
global enter_user_mode
enter_user_mode:
mov ecx, [esp + 4] ; eip
mov edx, [esp + 8] ; esp
mov ax, GDT_USER_DATA_RPL3
mov ds, ax
mov es, ax
mov fs, ax
mov gs, ax
push GDT_USER_DATA_RPL3 ; SS
push edx ; ESP
push 0x202 ; EFLAGS: IF set so the timer keeps ticking,
; IOPL 0 so IN/OUT/CLI/HLT fault in ring 3
push GDT_USER_CODE_RPL3 ; CS: the CPL becomes 3
push ecx ; EIP
iretTake figure 7-4 of the Intel SDM Volume 3A, the right-hand side,
“with privilege-level change”, and read it backwards. On an interrupt
from ring 3 the processor pushes SS, ESP,
EFLAGS, CS, EIP, in that order,
on the ring 0 stack; iret pops them in the reverse order,
and pops the last two only if the CS it just
popped has a higher RPL than the current CPL, which is what
“return to outer privilege level” means in the pseudo-code of the
IRET entry of Volume 2A. The five pushes above build that
frame by hand, and iret does the rest:
EIP = eip, CS = 0x1b (so
CPL = 3), EFLAGS = 0x202,
ESP = esp, SS = 0x23. The data segment
registers are not part of the frame; they are loaded before, while we
are still in ring 0, with the RPL 3 selector, because a program in ring
3 cannot load them itself and would fault on its first memory access
through a selector it is not allowed to use.
The EFLAGS value matters as much as in
task_alloc. IF = 1: the timer must be able to
preempt a user program, otherwise a for (;;); in ring 3
would own the machine. IOPL = 0 (bits 12-13):
cli, sti, in, out
and hlt are allowed only when CPL <= IOPL,
so with IOPL = 0 a user program that tries any of them gets
#GP. A user program also cannot change IOPL or
IF itself: popf in ring 3 silently ignores
those bits (Volume 2B, “POPF/POPFD”).
user_task_start, the start function of a user task, is
the glue: a brand-new user task is first “resumed” by
context_switch like a kernel thread, lands in
user_task_start in ring 0, and that function calls
enter_user_mode with the entry point and the user stack top
from the task structure. It never returns; a user task ends with the
exit system call.
13.5.4 The next interrupt
What happens when the timer ticks while user_hello runs?
The gate for vector 0x20 has a ring 0 code selector; the
processor sees CPL = 3, consults the TSS, loads
SS:ESP from SS0:ESP0, the top of the kernel
stack of the current task, which schedule() set, and pushes
the user’s SS and ESP, then
EFLAGS, CS, EIP. From there
everything is chapter 11: isr32 pushes the vector,
isr_common pushes the general registers and the data
segments, loads the kernel data selector into
DS..GS (this is where the “in later chapters,
a user-mode one” of chapter 11 comes true), and calls
isr_dispatch. The handler may call schedule(),
in which case the kernel stack of this task holds the complete user
state, in struct registers, under the five words of
context_switch, until the task is picked again. When the
handler returns, isr_common pops everything and
iret, which now finds a ring 3 CS in the
frame, pops the user ESP and SS too and
returns to ring 3. The user_esp and ss fields
of struct registers, which chapter 11 declared and left
unused, are valid for the first time; we will print them.
13.5.5 The .user section
The user programs of this chapter are compiled into the kernel image,
because the kernel cannot read a file from disk until chapter 14. They
live in one source file, userprog.c, and the linker script
makes sure that everything in that file ends up in a section of
its own:
os/os.lds (the section rules)
.text 0x10100 : ALIGN(0x100) { EXCLUDE_FILE(*userprog.o) *(.text .text.*) } :code
.rodata : { EXCLUDE_FILE(*userprog.o) *(.rodata .rodata.*) } :code
.data : { EXCLUDE_FILE(*userprog.o) *(.data .data.*) } :code
/* Chapter 13: everything from userprog.c (code, strings, data) goes in
its own page-aligned section, so that task.c can give exactly these
pages the USER bit. EXCLUDE_FILE above keeps the generic rules from
grabbing userprog.o first: ld assigns an input section to the first
rule that matches it. */
.user ALIGN(4096) : {
__user_start = .;
*userprog.o(.text .text.* .rodata .rodata.* .data .data.* .bss .bss.*)
. = ALIGN(4096);
__user_end = .;
} :codeWhy a whole file and not an attribute on each function? Because
gcc at -O0 puts the string literals of a
function in .rodata, not next to the code, and
__attribute__((section(".user"))) on a function moves only
the function. A user program whose "ticks is zero\n" sits
in the kernel’s .rodata faults the moment it passes that
pointer to write: ring 3 cannot read that page. Routing the
whole object file is the robust rule: whatever the compiler emits for
userprog.c, code, literals, initialized or zeroed data,
lands between __user_start and __user_end, and
task_create_user gives exactly those pages the USER
bit.
The EXCLUDE_FILE clauses are needed because of how
ld assigns input sections to output sections: the first
matching rule wins (GNU ld manual, “Input Section Basics”). Without
them, *(.text .text.*) in the .text rule would
already have taken userprog.o(.text) by the time the
.user rule is read, and the .user section
would be empty. EXCLUDE_FILE(*userprog.o) in each of the
three earlier rules makes them skip that file.
The section is aligned to a page at both ends, since the USER bit is
a per-page property, and it is placed before .bss.
This order is not an accident. Chapter 8 established that the bootloader
copies the ELF file verbatim and that the file layout must therefore
equal the memory layout; .bss has no bytes in the file, so
it must be last. A page-aligned section before it costs some padding in
the file (the .user section is padded to
0x1000 bytes with 66 90, the two-byte
nop that ld uses as filler in code sections),
which is a price worth paying to keep the loader of chapter 9
unchanged.
os/userprog.c (first part)
/* userprog.c -- programs that run in ring 3.
*
* Everything in this file (code, strings, data) is placed by os.lds in
* the .user section, the only part of the kernel image whose pages get
* the USER bit. The programs therefore cannot call any kernel function
* or touch any kernel variable: the CPU faults. Their only way to get
* something done is INT 0x80 (usercall.h). In chapter 14 they move out
* of the kernel into their own executable files.
*/
#include <stdint.h>
#include "usercall.h"
extern volatile uint32_t ticks; /* a kernel variable, for user_rogue */
void user_hello(void)
{
char msg[] = "user task ?: hello from ring 3\n";
int i;
msg[10] = '0' + user_getpid();
for (i = 0; i < 3; i++) {
user_write(msg, sizeof(msg) - 1);
user_yield();
}
user_exit();
}
void user_counter(void)
{
char msg[] = "user task ?: count ?\n";
int i;
msg[10] = '0' + user_getpid();
for (i = 1; i <= 3; i++) {
msg[19] = '0' + i;
user_write(msg, sizeof(msg) - 1);
user_yield();
}
user_exit();
}
/* Reads a kernel variable. The page is mapped, but without the USER bit,
so the read raises a page fault with the U/S bit set in the error code;
the kernel kills the task and goes on. */
void user_rogue(void)
{
char msg[] = "user task ?: about to read kernel memory\n";
msg[10] = '0' + user_getpid();
user_write(msg, sizeof(msg) - 1);
if (ticks == 0)
user_write("ticks is zero\n", 14);
else
user_write("ticks is not zero\n", 18);
user_write("not reached\n", 12);
user_exit();
}These programs are written without kprintf, without
%d, and without any kernel function, because none of those
is reachable from ring 3; msg[10] = '0' + user_getpid() is
how a program with no library prints a one-digit number, and
sizeof(msg) - 1 is how it counts the bytes of a string for
write, which takes a pointer and a length, like
the write of Unix and for a reason given at the end of the
chapter. (The file has two more programs, quoted in the sections that
need them.) Note that user_hello is linked into the kernel
and compiled with the kernel’s flags, and that the compiler has no idea
it will run in ring 3; the only things that make it a user program are
the section it is placed in and the selector in CS when it
runs.
13.6 System calls
13.6.1 Vector 0x80 with DPL
3
A user program that wants something done, printing a line, giving up
the processor, exiting, needs a way into the kernel, and rule 3 above
says there is exactly one: a gate. The traditional choice on x86,
Linux’s choice since 1991, is a software interrupt on vector
0x80:
os/syscall.h
#ifndef SYSCALL_H
#define SYSCALL_H
#include <stdint.h>
/* System call numbers, shared by the kernel (syscall.c) and user programs
(usercall.h). Convention, modelled on Linux i386: INT 0x80 with the
number in EAX and up to three arguments in EBX, ECX, EDX; the result
comes back in EAX. */
#define SYS_WRITE 1 /* write(const char *buf, uint32_t len): print len bytes;
returns len, or -1 if the buffer is not the task's */
#define SYS_YIELD 2 /* yield(): let another task run */
#define SYS_EXIT 3 /* exit(): terminate the task */
#define SYS_GETPID 4 /* getpid(): task id */
#define SYS_GETTIME 5 /* gettime(): timer ticks since boot (100 per second) */
#define SYS_SLEEP 6 /* sleep(uint32_t ticks): return after that many ticks */
#define SYSCALL_VECTOR 0x80
/* The longest buffer a single write() accepts. */
#define WRITE_MAX 1024
void syscall_init(void);
/* 1 if the task may hand the kernel the bytes [ptr, ptr + len): no
wrap-around, entirely below the kernel/user split, and every page mapped
with the USER bit in the task's own page directory (chapter 13,
"Validating what user mode hands us"). */
int user_range_ok(uint32_t ptr, uint32_t len);
#endifos/syscall.c (syscall_init)
void syscall_init(void)
{
idt_set_gate(SYSCALL_VECTOR, (uint32_t)isr128, GDT_KERNEL_CODE,
IDT_INTERRUPT_GATE_RING3);
isr_register_handler(SYSCALL_VECTOR, syscall_handler);
}The gate is an interrupt gate like all the others, with one
difference: IDT_INTERRUPT_GATE_RING3 is 0xEE
instead of 0x8E, DPL 3 instead of 0. Chapter 11 explained
why this field exists; now it is used. The DPL of a gate is the
privilege level a program needs to execute int n for that
vector; with DPL 0, int 0x80 from ring 3 raises
#GP (section 7.12.1.2 of the Intel SDM Volume 3A: “the CPL
must be equal to or less than the DPL of the gate”). Every other gate
keeps DPL 0, so int 0x20 from a user program, an attempt to
fake a timer tick, is a general-protection fault, not a tick. Hardware
interrupts and exceptions ignore the gate DPL, which is why the timer
still works in ring 3.
The stub is one more line in isr_stubs.asm,
ISR_NOERRCODE 128, which expands to isr128
exactly like the 48 others:
00010284 <isr128>:
10284: 6a 00 push 0x0
10286: 68 80 00 00 00 push 0x80
1028b: eb 00 jmp 1028d <isr_common>It is not in isr_stub_table, since idt_init
fills vectors 0 to 47 with DPL 0 gates; syscall_init
installs it separately with the right DPL. The handler then runs with a
complete struct registers, like any interrupt handler, and
that is the whole point of reusing isr_common: the system
call arguments are simply the saved registers.
13.6.2 The register convention and the wrappers
The convention is Linux’s for 32-bit x86: the system call number in
EAX, up to three arguments in EBX,
ECX, EDX, the result back in EAX.
There are six calls; the first four are used by the programs above, and
gettime and sleep are the subject of a later
section. On the user side it is a dozen lines of inline assembly:
os/usercall.h
#ifndef USERCALL_H
#define USERCALL_H
#include "syscall.h"
/* The user program's view of the system calls: tiny wrappers around
INT 0x80. always_inline matters: with -O0 a plain static inline
function would be emitted as a real function in the kernel's .text, and
a ring 3 caller would fault on it. Inlined, the INT instruction ends up
inside the user function, in the .user section. */
static inline __attribute__((always_inline))
int user_syscall(int number, int arg1, int arg2, int arg3)
{
int result;
asm volatile("int $0x80"
: "=a"(result)
: "a"(number), "b"(arg1), "c"(arg2), "d"(arg3)
: "memory");
return result;
}
/* Print `len` bytes from `buf`; returns len, or -1 if the kernel refused
the buffer (see user_range_ok in syscall.c). */
static inline __attribute__((always_inline))
int user_write(const char *buf, int len)
{
return user_syscall(SYS_WRITE, (int)buf, len, 0);
}
static inline __attribute__((always_inline))
void user_yield(void)
{
user_syscall(SYS_YIELD, 0, 0, 0);
}
static inline __attribute__((always_inline))
void user_exit(void)
{
user_syscall(SYS_EXIT, 0, 0, 0);
}
static inline __attribute__((always_inline))
int user_getpid(void)
{
return user_syscall(SYS_GETPID, 0, 0, 0);
}
/* Timer ticks since boot, 100 per second. */
static inline __attribute__((always_inline))
unsigned user_gettime(void)
{
return (unsigned)user_syscall(SYS_GETTIME, 0, 0, 0);
}
/* Do not come back before `nticks` ticks have passed. */
static inline __attribute__((always_inline))
void user_sleep(int nticks)
{
user_syscall(SYS_SLEEP, nticks, 0, 0);
}
#endifThe constraints of the asm statement (chapter 10
introduced the syntax) put number in EAX, the
arguments in EBX, ECX, EDX, and
take the result from EAX; the "memory" clobber
tells the compiler that the kernel may read or write memory, so that the
string a pointer refers to is really in memory before the
int. The always_inline attribute is not
decoration. At -O0, gcc does not inline
anything it is not forced to, and a plain static inline
function becomes a real function in the object file that includes the
header; user_syscall would then exist as a function in
userprog.o, which is fine, but also nowhere else,
which is fine too, until one realizes that the header could be included
from a kernel file, or that a future compiler decides differently.
Forcing the inlining guarantees that the int 0x80
instruction is part of the user function itself, in .user,
as the disassembly of user_hello shows:
$ objdump -d -M intel build/os/os
..... output omitted .....
00014000 <user_hello>:
..... output omitted .....
1403f: c7 45 f4 04 00 00 00 mov DWORD PTR [ebp-0xc],0x4
14046: c7 45 f0 00 00 00 00 mov DWORD PTR [ebp-0x10],0x0
1404d: c7 45 ec 00 00 00 00 mov DWORD PTR [ebp-0x14],0x0
14054: c7 45 e8 00 00 00 00 mov DWORD PTR [ebp-0x18],0x0
1405b: 8b 45 f4 mov eax,DWORD PTR [ebp-0xc]
1405e: 8b 5d f0 mov ebx,DWORD PTR [ebp-0x10]
14061: 8b 4d ec mov ecx,DWORD PTR [ebp-0x14]
14064: 8b 55 e8 mov edx,DWORD PTR [ebp-0x18]
14067: cd 80 int 0x80
14069: 89 45 e4 mov DWORD PTR [ebp-0x1c],eax
..... output omitted .....This is user_getpid() at -O0: the four
arguments are stored in local variables, loaded into the four registers,
and int 0x80 (opcode cd 80) is the call. The
function starts at 0x14000, the first byte of
.user. There is no call anywhere in it: a user
program of this chapter never calls a function, because every function
it could call is in the kernel.
13.6.3 The kernel side
os/syscall.c (the handler)
static void syscall_handler(struct registers *regs)
{
uint32_t i;
switch (regs->eax) {
case SYS_WRITE:
/* EBX = buffer, ECX = length. Refuse, never panic: the program
is wrong, not the kernel. */
if (regs->ecx > WRITE_MAX || !user_range_ok(regs->ebx, regs->ecx)) {
kprintf("[task %d: write(%p, %u) rejected]\n",
current_task->id, (void *)regs->ebx, regs->ecx);
regs->eax = (uint32_t)-1;
break;
}
for (i = 0; i < regs->ecx; i++)
putc(((const char *)regs->ebx)[i]);
regs->eax = regs->ecx;
break;
case SYS_YIELD:
schedule(); /* IF is clear: interrupt gate */
regs->eax = 0;
break;
case SYS_EXIT:
kprintf("[task %d (%s) exited]\n", current_task->id, current_task->name);
task_exit();
case SYS_GETPID:
regs->eax = current_task->id;
break;
case SYS_GETTIME:
regs->eax = ticks;
break;
case SYS_SLEEP:
task_sleep(regs->ebx); /* comes back after EBX ticks */
regs->eax = 0;
break;
default:
kprintf("[task %d: unknown system call %u]\n", current_task->id, regs->eax);
regs->eax = (uint32_t)-1;
}
}The handler is a switch on the saved EAX.
The arguments are read from the saved EBX and
ECX, and the result is written into the saved
EAX, which isr_common pops with
popa and iret hands back to the program: the
user sees it as the return value of user_syscall.
SYS_YIELD calls schedule() directly, with no
irq_save, because an interrupt gate cleared IF
on entry; this is the same situation as the timer handler.
SYS_EXIT never returns; the missing break
after it is deliberate and the noreturn attribute on
task_exit keeps the compiler from warning.
SYS_GETTIME and SYS_SLEEP are explained with
the clock, two sections from here. An unknown number is reported and
answered with -1, as Linux answers
-ENOSYS.
SYS_WRITE is the only call that takes a pointer, and it
does not use it before user_range_ok has said that it may.
The pointer in EBX and the length in ECX are
numbers the user program chose; the kernel runs with the task’s page
directory, in ring 0, where every mapped address is readable, including
the kernel’s own data. The check, what it tests, and a program that
tries to get past it have a section of their own at the end of the
chapter, “Validating what user mode hands us”; until then, read the
SYS_WRITE case as “print ECX bytes from
EBX, if the program is allowed to read them”.
13.6.4 Linux
What we built is, in miniature, the 32-bit Linux system call
interface before 2002: the same vector, the same register convention,
the same numbers passed in EAX (Linux’s write
is number 4 and exit is 1; ours are made up). You can see
it in any statically linked 32-bit program under gdb, or in
the kernel’s arch/x86/entry/entry_32.S, where the entry
point for int 0x80 is a stub that saves the registers in a
struct pt_regs that plays the part of our
struct registers. Modern processors offer a faster way in,
sysenter on 32-bit and the syscall instruction
on 64-bit, that skips the IDT and the privilege checks of a gate because
the entry point is fixed in a register; chapter 17, Epilogue, says what
changes. The idea is the same: one well-known door, a number, and
arguments in registers.
13.7 Timekeeping and sleeping
Every program of this chapter so far gives up the processor with
yield() and gets it back a few microseconds later. A real
program more often wants the opposite: to give up the processor for
a while, until a key is pressed, a disk block arrives, or simply
until half a second has passed. The last case is the simplest and it
introduces everything the others need: a notion of time, a task state
that means “do not run me”, and a place where the kernel decides that
the waiting is over. This section adds all three, and two system calls
for user programs, gettime and sleep.
13.7.1 Ticks
The kernel already has a clock: ticks in
pit.c, incremented by the timer handler of chapter 11 a
hundred times a second since pit_init. It is the only clock
the kernel needs for scheduling, and the only one user programs get,
through a new system call that simply returns it.
SYS_GETTIME is number 5 in syscall.h and one
line in the handler:
case SYS_GETTIME:
regs->eax = ticks;
break;A tick count is not a time of day. It starts at zero whenever the
machine boots and it means nothing to anyone outside the machine; but it
is monotonic, cheap, and it is the unit in which the scheduler already
thinks. Unix kept exactly this distinction: jiffies inside
the Linux kernel, clock() and times() for
programs, and a separate idea of calendar time that we come to at the
end of the section.
13.7.2 A sleeping task
sleep(n) must not return before n ticks
have passed, and it must not burn those ticks either. The naive
implementation loops on yield() in the handler until
ticks is large enough, and it works; it also makes the
sleeping task run a few hundred times a second for nothing, each time
pushing the whole round robin forward by one slot, and with ten sleeping
tasks the idle loop would never see its hlt again. The
right implementation has three parts: a new state, a wake-up time, and a
check on every tick.
os/task.h (the new state and field)
enum task_state {
TASK_READY, /* waiting for the CPU */
TASK_RUNNING, /* the task current_task points to */
TASK_SLEEPING, /* waiting for the tick in wake_at; the timer wakes it */
TASK_DEAD /* exited; waiting for the idle task to free it */
}; uint32_t wake_at; /* TASK_SLEEPING: the tick to wake up at */os/task.c (task_sleep and
task_wake_sleepers)
void task_sleep(uint32_t nticks)
{
uint32_t flags = irq_save();
current_task->wake_at = ticks + nticks;
current_task->state = TASK_SLEEPING;
schedule(); /* returns when we are TASK_RUNNING again */
irq_restore(flags);
}
int task_wake_sleepers(void)
{
struct task *t;
int woken = 0;
if (current_task == 0)
return 0; /* a timer tick before task_init() */
/* The subtraction, cast to signed, is true when `ticks` has reached
wake_at, and stays true across the wrap-around of the 32-bit tick
counter (497 days at 100 Hz): a plain `ticks >= wake_at` would not. */
for (t = idle_task.next; t != &idle_task; t = t->next) {
if (t->state == TASK_SLEEPING && (int32_t)(ticks - t->wake_at) >= 0) {
t->state = TASK_READY;
woken++;
}
}
return woken;
}task_sleep is yield() with two lines in
front: it records when the task wants to be woken, marks it
TASK_SLEEPING, and calls schedule(). From here
on the task is treated like a dead one by the scheduler, whose loop now
skips both:
while (next->state == TASK_DEAD || next->state == TASK_SLEEPING)
next = next->next; /* idle never sleeps or dies, so this ends */The difference from a dead task is that somebody will bring it back.
That somebody is the timer handler, which on every tick calls
task_wake_sleepers, walks the run queue and turns every
sleeping task whose time has come into a ready one. The function has the
same guard as schedule(), and for the same reason: the
first timer interrupt arrives right after the sti in
kmain, long before task_init has filled in the
run queue, and a walk through a list whose head still points nowhere
does not end well. (The first version of this function lacked the guard,
and the kernel printed nothing at all, not even the greeting: the first
tick hung the machine before kmain reached its second line.
Chapter 16 tells how such a thing is found.)
The comparison deserves its comment. ticks is a 32-bit
counter that wraps after 497 days, which is nothing for a server.
ticks >= wake_at fails at the wrap: a task that went to
sleep at tick 0xFFFFFFF0 for 32 ticks has
wake_at = 0x10, and ticks, now small, is never
“greater” than it was. The subtraction ticks - wake_at,
computed in unsigned arithmetic and then read as a signed number, is
small and non-negative once ticks has passed
wake_at, whether or not a wrap happened in between, because
the wrap cancels out in the subtraction. Linux has the same idiom as the
macro time_after, and every kernel has the bug that
precedes it somewhere in its history.
Go back to the timer handler quoted under “Preemption”, which now reads
if (task_wake_sleepers() > 0 || ticks % SCHEDULE_TICKS == 0)
schedule();One decision is hidden in the ||. Waking a task only
changes a field; it does not run it. Without the first operand, a task
woken at tick 35 would wait until tick 40, the next multiple of
SCHEDULE_TICKS, for the scheduler to look at it, and
sleep(25) would last anywhere between 25 and 34 ticks. By
calling schedule() on the tick of the wake-up, the sleep is
accurate to one tick, at the price of cutting short whatever task was
running. For a kernel whose only other activity is hlt in
the idle loop, that is the right trade.
13.7.3 The system call and a program that sleeps
SYS_SLEEP is number 6, and its handler is
task_sleep:
case SYS_SLEEP:
task_sleep(regs->ebx); /* comes back after EBX ticks */
regs->eax = 0;
break;Follow what happens to the user task. It executes
int 0x80, the processor switches to its kernel stack,
isr_common saves its registers,
syscall_handler calls task_sleep, which calls
schedule(), which calls context_switch, which
freezes the task with the whole system call in progress on its kernel
stack: the struct registers of the user program, the frames
of isr_dispatch, syscall_handler and
task_sleep, and the five words of
context_switch. Twenty-five ticks later the timer handler,
running on some other task’s kernel stack, marks it ready and
calls schedule(), which switches back;
context_switch returns into task_sleep, which
returns into syscall_handler, which stores the result and
returns, and iret resumes the program at the instruction
after int 0x80. Nothing about the sleeping task was kept
anywhere but on its own stack, which is the whole design of this chapter
applied once more.
The wrappers in usercall.h:
/* Timer ticks since boot, 100 per second. */
static inline __attribute__((always_inline))
unsigned user_gettime(void)
{
return (unsigned)user_syscall(SYS_GETTIME, 0, 0, 0);
}
/* Do not come back before `nticks` ticks have passed. */
static inline __attribute__((always_inline))
void user_sleep(int nticks)
{
user_syscall(SYS_SLEEP, nticks, 0, 0);
}and a program that uses both. The programs of this chapter have no
printf, and until now printed digits by patching a
character in a string; printing a tick count needs a little more, so
userprog.c gains two helpers that build a line in a buffer,
which user_write then prints in one call:
os/userprog.c (second part: the helpers and the sleeper)
/* There is no printf in ring 3, so the next two programs build their
lines by hand: append a string, or a number in decimal, at position
`n` of `line`, and return the new position. */
static int append(char *line, int n, const char *s)
{
while (*s != '\0')
line[n++] = *s++;
return n;
}
static int append_number(char *line, int n, int value)
{
char digits[12];
int i = 0;
unsigned u = (unsigned)value;
if (value < 0) {
line[n++] = '-';
u = 0u - u;
}
do {
digits[i++] = '0' + u % 10;
u /= 10;
} while (u != 0);
while (i > 0)
line[n++] = digits[--i];
return n;
}
/* Prints the time, sleeps a quarter of a second, three times. While it
sleeps it is TASK_SLEEPING: the scheduler skips it and the timer handler
makes it ready again when the tick in wake_at arrives. */
void user_sleeper(void)
{
char line[64];
int i, n;
for (i = 0; i < 3; i++) {
n = append(line, 0, "user task ");
n = append_number(line, n, user_getpid());
n = append(line, n, ": tick ");
n = append_number(line, n, (int)user_gettime());
n = append(line, n, ", sleeping 25 ticks\n");
user_write(line, n);
user_sleep(25);
}
n = append(line, 0, "user task ");
n = append_number(line, n, user_getpid());
n = append(line, n, ": awake at tick ");
n = append_number(line, n, (int)user_gettime());
n = append(line, n, ", done\n");
user_write(line, n);
user_exit();
}append_number is print_unsigned from
chapter 10 written into a buffer instead of to the console, with the
sign handled the same careful way; the two functions are
static, and since the whole of userprog.o goes
into the .user section, they end up in ring 3 pages next to
their callers, which is the only place a ring 3 program can call.
kmain creates the sleeper as the sixth task, after the
rogue. Here is what it prints, with the lines of the other tasks left in
because the interleaving is the point:
user task 5: about to read kernel memory
Page fault at 0x00018000: protection violation, read, user mode, eip=0x0001432f (error code 0x5)
killing task 5 (user rogue)
user task 6: tick 10, sleeping 25 ticks
[task 7: write(0x00010000, 16) rejected]
..... output omitted .....
[task 7 (user rogue write) exited]
thread A: 2
thread B: 2
user task 3: hello from ring 3
user task 4: count 2
thread A: 3
thread B: 3
user task 3: hello from ring 3
user task 4: count 3
[task 3 (user hello) exited]
[task 4 (user counter) exited]
user task 6: tick 35, sleeping 25 ticks
user task 6: tick 60, sleeping 25 ticks
user task 6: awake at tick 85, done
[task 6 (user sleeper) exited]
all tasks finished, 32432 frames freeThe sleeper first runs at tick 10, the tick at which the timer first
took the processor from the idle task, and prints that number; then it
is gone from the output while the other tasks finish their rounds at
ticks 20 and 30, and it comes back at tick 35, exactly 25 ticks later,
then 60, then 85. (The task 7 whose lines are omitted is the subject of
the last section of the chapter.) Look at where the second sleeper line
sits: after tasks 3 and 4 have exited. At tick 35 the timer
handler wakes the sleeper and calls schedule() from the
idle task; the round robin then goes through the queue in order, and
threads A and B and tasks 3 and 4, which were all ready and waiting for
their fourth turn, run first, return from their loops and exit, before
the queue reaches task 6. A woken task is ready, not privileged.
The same thing under gdb, from the inside. Break in
task_sleep and step over the two assignments:
(gdb) b task_sleep
Breakpoint 2 at 0x12a87: file task.c, line 156.
(gdb) c
Breakpoint 2, task_sleep (nticks=25) at task.c:156
156 uint32_t flags = irq_save();
(gdb) p current_task->name
$1 = 0x13393 "user sleeper"
(gdb) p ticks
$2 = 10
(gdb) p nticks
$3 = 25
(gdb) next
158 current_task->wake_at = ticks + nticks;
(gdb) next
159 current_task->state = TASK_SLEEPING;
(gdb) next
160 schedule(); /* returns when we are TASK_RUNNING again */
(gdb) p current_task->state
$4 = TASK_SLEEPING
(gdb) p current_task->wake_at
$5 = 35Now a breakpoint in the timer handler’s helper, conditioned on the
tick we expect, and finish to see what it returns:
(gdb) b task_wake_sleepers if ticks == 35
Breakpoint 4 at 0x12aca: file task.c, line 167.
(gdb) c
Breakpoint 4, task_wake_sleepers () at task.c:167
167 int woken = 0;
(gdb) p current_task->name
$22 = 0x1373c "idle"
(gdb) finish
0x000118a8 in irq0_handler (regs=0x8ffac) at pit.c:38
38 if (task_wake_sleepers() > 0 || ticks % SCHEDULE_TICKS == 0)
Value returned is $23 = 1
(gdb) delete
(gdb) b task_sleep
Breakpoint 5 at 0x12a87: file task.c, line 156.
(gdb) c
Breakpoint 5, task_sleep (nticks=25) at task.c:156
156 uint32_t flags = irq_save();
(gdb) p current_task->name
$24 = 0x13393 "user sleeper"
(gdb) p ticks
$25 = 35At tick 35 the idle task was running, as it should: everything else
was ready and waiting or asleep, and hlt is where the
processor spends its time between events. The helper found one task to
wake and returned 1, the handler called schedule(), and the
next time task_sleep is entered it is the sleeper again, at
tick 35, going back to sleep.
13.7.4 What time is it? The CMOS clock
Ticks say how long the machine has been running, not what day it is.
The PC has a second clock for that, a battery-backed chip that keeps
counting while the machine is off: the real-time clock. The
original part was a Motorola MC146818, whose datasheet, “MC146818A
Real-Time Clock Plus RAM”, is still the reference for the register
layout that every chipset since the PC/AT has kept, and the OSDev wiki
page “CMOS” is the short version. The chip holds 64 bytes, of which the
first ten are the time and date, two more are the status registers A and
B, and the rest is the CMOS RAM where the BIOS keeps its
settings. It is reached through two ports, the way the VGA CRT
controller was in chapter 10: write the register number to port
0x70, read or write the register through port
0x71.
os/rtc.h
#ifndef RTC_H
#define RTC_H
#include <stdint.h>
/* The battery-backed real-time clock of the PC (the MC146818 and its
descendants in every chipset since the PC/AT), read through the CMOS
ports 0x70 and 0x71. It knows the wall-clock date and time; the PIT
(chapter 11) only counts ticks since boot. */
struct rtc_time {
uint32_t year; /* four digits, assuming the 21st century */
uint8_t month, day; /* 1-12, 1-31 */
uint8_t hour, minute, second;
};
void rtc_read(struct rtc_time *t);
/* One line on the console: "RTC: 2026-10-09 14:03:21 UTC". */
void rtc_print(void);
#endifos/rtc.c
/* rtc.c -- the CMOS real-time clock.
*
* The clock chip of the PC/AT was a Motorola MC146818, "Real-Time Clock
* Plus RAM"; every chipset since has kept its register map, so the
* MC146818A datasheet is still the reference (OSDev wiki: "CMOS"). It is
* reached like the VGA CRT controller of chapter 10: write a register
* number to port 0x70, then read the register through port 0x71. Bit 7
* of the byte written to 0x70 doubles as the NMI disable bit; we leave it
* clear. Registers 0 to 9 hold the time and date, 0x0A and 0x0B are the
* status registers A and B; the rest is the CMOS RAM where the BIOS keeps
* its settings.
*/
#include "rtc.h"
#include "io.h"
#include "printf.h"
#define CMOS_INDEX 0x70
#define CMOS_DATA 0x71
#define RTC_SECONDS 0x00
#define RTC_MINUTES 0x02
#define RTC_HOURS 0x04
#define RTC_DAY 0x07
#define RTC_MONTH 0x08
#define RTC_YEAR 0x09 /* two digits */
#define RTC_STATUS_A 0x0A
#define RTC_STATUS_B 0x0B
#define STATUS_A_UIP 0x80 /* update in progress */
#define STATUS_B_24H 0x02 /* 0: 12-hour mode, hour bit 7 = PM */
#define STATUS_B_BINARY 0x04 /* 0: the registers hold BCD */
static uint8_t cmos_read(uint8_t reg)
{
outb(CMOS_INDEX, reg);
return inb(CMOS_DATA);
}
/* Binary-coded decimal: each nibble is one decimal digit, so 0x59 means
59. This is how the chip counts unless status register B says
otherwise, and it is how QEMU's clock counts. */
static uint8_t bcd_to_binary(uint8_t v)
{
return (v >> 4) * 10 + (v & 0x0F);
}
static void read_registers(struct rtc_time *t)
{
t->second = cmos_read(RTC_SECONDS);
t->minute = cmos_read(RTC_MINUTES);
t->hour = cmos_read(RTC_HOURS);
t->day = cmos_read(RTC_DAY);
t->month = cmos_read(RTC_MONTH);
t->year = cmos_read(RTC_YEAR);
}
void rtc_read(struct rtc_time *t)
{
struct rtc_time again;
uint8_t status_b, pm;
/* The chip updates its registers once a second, and a read during
the update (status A, bit 7, "UIP") may see a half-written time.
So wait for the update to end, read everything, read it again, and
only trust two identical readings. */
do {
while (cmos_read(RTC_STATUS_A) & STATUS_A_UIP)
;
read_registers(t);
read_registers(&again);
} while (t->second != again.second || t->minute != again.minute ||
t->hour != again.hour || t->day != again.day ||
t->month != again.month || t->year != again.year);
status_b = cmos_read(RTC_STATUS_B);
pm = t->hour & 0x80; /* only meaningful in 12-hour mode */
t->hour &= 0x7F;
if (!(status_b & STATUS_B_BINARY)) {
t->second = bcd_to_binary(t->second);
t->minute = bcd_to_binary(t->minute);
t->hour = bcd_to_binary(t->hour);
t->day = bcd_to_binary(t->day);
t->month = bcd_to_binary(t->month);
t->year = bcd_to_binary(t->year);
}
if (!(status_b & STATUS_B_24H)) {
t->hour %= 12;
if (pm)
t->hour += 12;
}
/* The chip stores two digits of year. The century lives in a
chipset-specific CMOS byte that ACPI tells an OS about; we assume
the obvious. */
t->year += 2000;
}
void rtc_print(void)
{
struct rtc_time t;
rtc_read(&t);
/* QEMU's clock runs on UTC unless told otherwise (-rtc base=...). */
kprintf("RTC: %u-%s%u-%s%u %s%u:%s%u:%s%u UTC\n",
t.year,
t.month < 10 ? "0" : "", t.month,
t.day < 10 ? "0" : "", t.day,
t.hour < 10 ? "0" : "", t.hour,
t.minute < 10 ? "0" : "", t.minute,
t.second < 10 ? "0" : "", t.second);
}Three things in this driver are typical of old chips and worth
knowing. The registers hold binary-coded decimal unless bit 2
of status register B says otherwise: 0x59 means fifty-nine,
each nibble one digit, which was convenient for a 1984 BIOS that
displayed the digits and is a conversion for everyone since;
bcd_to_binary is that conversion. The chip updates all its
registers once a second, and the update takes about two milliseconds
during which the update-in-progress bit, bit 7 of status
register A, is set; a read in that window may see the old seconds and
the new minutes, so the driver waits for the bit to clear and then reads
everything twice until two readings agree, which is the method the
datasheet describes under “Update Cycle” and the one every operating
system uses. And the hour register carries the AM/PM flag in its top bit
when the clock is in 12-hour mode, which QEMU never is but a BIOS
setting can select. The year is two digits, as in 1984; the century is
in a chipset-dependent CMOS byte whose location ACPI reports, and we
assume this one.
The kernel reads the clock once, at boot:
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
RTC: 2026-10-09 18:15:49 UTC
usable memory: 130555 KiBYour output will show your date, because QEMU initializes the
emulated clock from the host’s, in UTC unless
-rtc base=localtime says otherwise. A real kernel reads it
exactly once too, then keeps time by adding ticks to that value, because
a port access to the CMOS costs microseconds and the chip has a
resolution of one second.
13.7.5 Why rdtsc is not a
clock
There is a third counter on every x86 since the Pentium, and
newcomers reach for it first: the time-stamp counter, a 64-bit
register that counts processor clock cycles and that the
rdtsc instruction reads into EDX:EAX. The
Intel SDM Volume 3A, section 2.8.9 “Reading Time-Stamp Counter and
IA32_TSC_AUX”, describes it in one paragraph: a model-specific counter,
reset to zero when the processor is reset, that at 3 GHz takes over 190
years to wrap. It is the finest-grained counter in the machine and the
right tool for measuring how many cycles a piece of code takes. It is
the wrong tool for telling time, for three reasons. Its rate is the
processor’s clock, which modern processors change dozens of times a
second to save power, so a count of cycles is not a count of nanoseconds
unless the processor documents an invariant TSC (section
20.17.1 “Invariant TSC” of Volume 3, which is in the Volume 3B half of
the set). It is per core: each processor of a multiprocessor
machine has its own, started at its own reset, and a program migrated
from one core to another can see time go backwards. And it has no epoch:
zero is “when this core was reset”, which relates to neither the boot of
the machine nor to any calendar. Linux uses it, after calibrating it
against the PIT or the HPET and only when the processor promises
invariance, as the fast source behind clock_gettime; the
ticks and the CMOS clock of this section are the slow sources it falls
back on, and the ones a kernel can trust without asking questions.
13.8 Locks and concurrency on one processor
This chapter has used irq_save and
irq_restore around the run queue, task_exit
has an explicit cli, and the heap of chapter 12 is called
from task_alloc and task_reap, which both run
with interrupts disabled. Nothing has been said about why this is
enough, and it is worth saying precisely, because the reasoning stops
being true the day a second processor appears.
13.8.1 What a critical section protects against
A critical section is a sequence of operations on shared
data that must appear atomic to everyone else who uses the data: nobody
may observe, or act on, the half-modified state in the middle. On a
single processor, “everyone else” is a short list. Our kernel is not
reentrant in any other way: a task cannot run while another task runs,
since there is one processor and current_task names its
only occupant, and a task gives up the processor only by calling
schedule() itself. The only code that can run in the
middle of a sequence of instructions, without being called, is an
interrupt handler. So on one processor there is exactly one other
“thread” to fear, the handler, and keeping it from running, with
cli, is a complete lock: while IF is clear,
the sequence of instructions between cli and
sti is executed from beginning to end by the one processor,
with nothing in between. This is why the chapter has been able to say
“atomic” about the run-queue updates in task_alloc and
task_reap without any lock instruction:
irq_save is the lock, and the data it protects is
everything that the timer handler, through schedule() and
task_wake_sleepers, reads or writes.
The heap is the same case one level down. kmalloc and
kfree walk and split a list of blocks; if a timer tick
could run schedule() in the middle of a split and the next
task called kmalloc, the list would be corrupted. It does
not happen in this chapter, but look at why: task_reap
frees inside a critical section, while the kmalloc calls of
task_alloc run with interrupts enabled, and a tick
in the middle of one switches to a task that, as it happens, never
allocates. That is an argument about the current set of tasks, not about
the allocator, and it will be false the day a kernel thread calls
kmalloc. Exercise 13.3 asks you to make it unnecessary by
putting the lock inside the allocator, where it belongs.
13.8.2 What it does not protect against
The lock has a precise meaning, “no interrupt handler runs here”, and three things fall outside it.
A handler that sleeps. task_sleep and
schedule() disable interrupts and then switch to another
task, which re-enables them with the popfd of
context_switch or the iret at the end of its
own handler. The critical section of the caller is therefore
not closed by the switch: the other task runs with interrupts
on, inside what the first task believed was an atomic sequence. For
schedule() this is intended, since the run queue is
consistent at the moment of the switch. For anything else it is a bug: a
kmalloc that called schedule() halfway through
a split would be a corruption waiting to happen, and a system call
handler that sleeps while holding a half-updated structure is the same
thing in a longer disguise. The rule in every kernel is the same: never
give up the processor inside a critical section, which is why Linux will
complain loudly, “scheduling while atomic”, when a driver sleeps with
interrupts disabled or a spinlock held.
Nested disabling. If cli and sti were used
directly, a function called from a context that already has interrupts
disabled would enable them on its way out, in the middle of its caller’s
critical section. This is the reason irq_save returns the
old EFLAGS and irq_restore puts it back rather
than executing sti: the pair restores the state it found,
so critical sections nest. schedule() relies on it, since
it is called both from yield() with interrupts on and from
the timer handler with interrupts off.
Exceptions and non-maskable interrupts. cli masks the
hardware interrupts that come through the PIC; it does not mask a page
fault, a division by zero, or an NMI. A critical section that touches an
unmapped page takes the fault anyway, and the handler runs on top of it.
Our handlers do not touch the run queue or the heap, so this is harmless
today; it is the reason real kernels are careful about what a fault
handler is allowed to do.
13.8.3 Two processors
Now give the machine a second processor, as -smp 2 would
and as chapter 17 discusses. cli is a per-processor
instruction: it clears IF in the EFLAGS of the
processor that executes it, and the other processor keeps running with
its own EFLAGS, its own current_task, and its
own timer interrupts. Two tasks can now be inside
task_alloc at the same time, both with interrupts disabled,
both walking the run queue to find its tail, both linking a new task
there; the list ends up with one of the two tasks lost and the other
pointing at freed memory. Disabling interrupts still protects against
the handler on this processor, which is still necessary, but it
no longer protects against the other processor, which is the new thing
to fear.
The protection against another processor has to be a word in memory
that both processors agree on: a lock variable, which a
processor sets on entering the critical section and clears on leaving,
and which it must test and set atomically, otherwise both could
see it clear and both set it. The processor provides exactly that. The
Intel SDM Volume 3A, chapter 11 “Multiple-Processor Management”, section
11.1 “Locked Atomic Operations”, describes the mechanism: the
lock prefix, which makes a read-modify-write instruction
such as add, or or cmpxchg atomic
with respect to every other processor and bus agent, by locking the bus
or, on anything since the P6, the cache line; and the xchg
instruction, which exchanges a register and a memory operand and is
locked implicitly, prefix or not (section 11.1.2.1 “Automatic
Locking”). A loop that does xchg of the value 1 into the
lock variable until the value it gets back is 0 is a spinlock,
the building block of every multiprocessor kernel;
lock cmpxchg is its more general form, and
lock add and friends are how counters are kept without a
lock at all. Section 11.1.1 is also worth reading for what the processor
guarantees without any prefix: an aligned 32-bit load or store
is atomic by itself, which is why ticks can be read by one
task while the handler increments it, and why that would stop being true
for a 64-bit counter on a 32-bit kernel.
Chapter 17, Epilogue, picks the thread up: a multiprocessor kernel
keeps cli for the handler and adds a spinlock for the other
processors, in that order, and the irq_save of this chapter
becomes the first half of spin_lock_irqsave, which is the
name Linux gives to the pair.
13.9 Protection in action: the rogue task
Task 5, user_rogue, is a program that does what a buggy
or malicious program does: it reads a kernel variable,
ticks. The compiler turns ticks == 0 into a
load from the absolute address of the variable:
00014242 <user_rogue>:
..... output omitted .....
1432f: a1 00 80 01 00 mov eax,ds:0x18000
14334: 85 c0 test eax,eaxticks is at 0x18000, in the kernel’s
.bss. The page is present in the task’s directory, since
the kernel is mapped everywhere, but neither its page-table entry nor
the directory entry has the USER bit. The processor, in ring 3, raises
exception 14 with an error code that says precisely why:
Page fault at 0x00018000: protection violation, read, user mode, eip=0x0001432f (error code 0x5)
killing task 5 (user rogue)Error code 0x5 is binary 101: bit 0 set, so
the page was present and the fault is a protection
violation, not a missing page; bit 1 clear, a read; bit 2 set, the
access came from user mode (figure 5-12 of the Intel SDM Volume 3A,
section 5.7 “Page-Fault Exceptions”). Compare with chapter 12’s
deliberate fault on 0xdeadbeef, whose error code was
0x0: not present, read, kernel mode. The page-fault handler
of chapter 12 printed the message and panicked; this chapter’s version
looks at one more thing before deciding:
os/paging.c (the end of
page_fault_handler)
if ((regs->cs & 3) == 3) {
kprintf("killing task %d (%s)\n", current_task->id, current_task->name);
task_exit();
}
panic("unhandled page fault");The saved CS tells which ring the faulting code ran in.
A page fault in ring 0 is a kernel bug, and the right thing to do is to
stop. A page fault in ring 3 is the program’s bug, and the right thing
to do is to end the program: task_exit marks it dead and
schedules the next one, and the idle task later frees its directory, its
user stack and its kernel stack. The kernel continues because nothing of
the kernel’s was touched; the task did not get to read
ticks, let alone to write it, and the other tasks print
their remaining lines as if nothing had happened. That is the difference
between a kernel with user mode and a kernel without: in chapter 12, the
same bug, in the same program, would have halted the machine.
The last line of the output is the accounting:
32446 frames free before starting tasks
..... output omitted .....
all tasks finished, 32432 frames freeFourteen frames did not come back, and they should not: they are the
pages the heap grew into to hold the seven kernel stacks (each
kmalloc(4096) needs a little more than a page, so the heap
grows by two pages per task, 0xC0001010, 0xC0003010, … in the listing
below), and the heap keeps its pages after kfree, as
chapter 12’s allocator was designed to do. Everything a task owned
outright, the page directory, the user stack frame, the page table for
the user stack, fifteen frames in all for the five user tasks, was
returned by paging_free_directory.
13.10 Validating what user mode hands us
The rogue of the previous section attacked the kernel directly, and
the processor stopped it. There is a second way for a program to reach
kernel memory, and the processor does nothing about it: ask the kernel
to do the reading. write(buf, len) takes a pointer and a
length from ring 3, and the handler that serves it runs in ring 0, with
the task’s page directory loaded, where the kernel’s own pages are
perfectly readable. If the handler simply did putc(buf[i])
for i up to len, a program could print the
kernel’s data by passing a kernel address, could make the kernel walk
into an unmapped page by passing a length that runs past its buffer, and
with a read-like call that writes through the pointer,
could overwrite the kernel outright. Every one of these is a real bug
class with a name, and the defense is a single rule: the kernel
never trusts a pointer or a length that came from ring 3. Both are
numbers the program chose, and a number is not a right.
13.10.1 user_range_ok
The check lives next to the handler, and it is the only piece of memory protection in the kernel that is done by software rather than by the processor:
os/syscall.c (user_range_ok)
/* Everything a user task owns (its program, its stack) lies below this
address; the kernel's heap and the kernel itself are either above it or
mapped without the USER bit. */
#define USER_SPACE_END USER_STACK_TOP
/* A user pointer and a user length are just numbers the program chose.
Before the kernel touches a single byte through them it checks that the
whole range is memory the task could touch itself: otherwise a program
could make the kernel print (or, with another call, overwrite) kernel
memory on its behalf, or make it fault in ring 0 by walking off the end
of a mapping. Three checks, from cheapest to most expensive. */
int user_range_ok(uint32_t ptr, uint32_t len)
{
uint32_t end = ptr + len, page;
/* 1. ptr + len must not wrap around 4 GiB: a huge len would otherwise
make `end` small and pass the next test. */
if (end < ptr)
return 0;
/* 2. The whole range lies in the user half of the address space. */
if (ptr >= USER_SPACE_END || end > USER_SPACE_END)
return 0;
/* 3. Every page of it is present and user-accessible in this task's
page directory: the same two bits the CPU would check in ring 3. */
for (page = PAGE_ALIGN_DOWN(ptr); page < end; page += PAGE_SIZE)
if (!paging_user_accessible(current_task->page_directory, page))
return 0;
return 1;
}Read the three tests in order, because the order is the point. The
first is arithmetic: ptr + len is computed in 32 bits, and
a length close to 4 GiB makes it wrap to a small number, so a
range check that looked only at end would accept it.
Testing end < ptr catches the wrap before anything else
is believed. The second is the kernel/user split: this kernel
puts everything a task owns, its program at 0x08048000 from
chapter 14 and the .user section before that, and its stack
below 0x80000000, in the lower half of the address space,
and the heap with the kernel stacks at 0xC0000000 in the
upper half. A range that reaches past the split is wrong whatever the
page tables say, and rejecting it costs two comparisons. Linux has the
same constant, TASK_SIZE, and the same check,
access_ok. The third test is the one the processor would
have made: for every page of the range,
paging_user_accessible walks this task’s page directory and
requires the PRESENT and USER bits at both
levels. It is needed because the lower half is not all the task’s: the
kernel itself is identity-mapped at 0x10000, below the
split, in every directory, without the USER bit. The page
walk is the expensive test, one directory and one table lookup per page,
and it comes last so that the cheap ones reject the obvious cases
first.
SYS_WRITE now takes a length in ECX as well
as the pointer in EBX, like the write of Unix,
and uses the check:
os/syscall.c (the SYS_WRITE case)
case SYS_WRITE:
/* EBX = buffer, ECX = length. Refuse, never panic: the program
is wrong, not the kernel. */
if (regs->ecx > WRITE_MAX || !user_range_ok(regs->ebx, regs->ecx)) {
kprintf("[task %d: write(%p, %u) rejected]\n",
current_task->id, (void *)regs->ebx, regs->ecx);
regs->eax = (uint32_t)-1;
break;
}
for (i = 0; i < regs->ecx; i++)
putc(((const char *)regs->ebx)[i]);
regs->eax = regs->ecx;
break;WRITE_MAX, 1024 bytes, bounds the work a single call can
ask of the kernel, and it is tested first: a length above it never
reaches the page walk, which would otherwise be asked to check half a
million pages for a program that passed 0x7fffffff. A
rejected call returns -1 to the program, the way Unix returns -1 and
sets errno to EFAULT; it prints a line, which
a real kernel would not, so that the test log shows what happened. What
it never does is panic(): the program is wrong, not the
kernel, and a wrong program is the normal state of affairs on a machine
that runs programs.
13.10.2 A program that lies
os/userprog.c (third part: the rogue writer)
/* Lies to the kernel: asks it to print from an address the program may
not read, then from its own buffer but with an absurd length. A kernel
that trusted either argument would leak its memory or fault in ring 0;
ours returns -1 and the program carries on. */
static void report(const char *what, int result)
{
char line[64];
int n;
n = append(line, 0, "user task ");
n = append_number(line, n, user_getpid());
n = append(line, n, ": ");
n = append(line, n, what);
n = append(line, n, " returned ");
n = append_number(line, n, result);
n = append(line, n, "\n");
user_write(line, n);
}
void user_rogue_write(void)
{
char buf[] = "this buffer is fine\n";
/* 1. The kernel's ELF header: mapped in every directory, not USER. */
report("write(0x10000, 16)", user_write((const char *)0x10000, 16));
/* 2. The kernel heap, above the user/kernel split. */
report("write(0xc0000000, 16)", user_write((const char *)0xc0000000, 16));
/* 3. A good pointer with a length that runs past the stack page. */
report("write(buf, 0x7fffffff)", user_write(buf, 0x7fffffff));
/* 4. The same buffer, honestly described. */
report("write(buf, 20)", user_write(buf, sizeof(buf) - 1));
user_exit();
}Task 7 makes four calls, one for each way of lying and one honest. The kernel’s answer:
user task 6: tick 10, sleeping 25 ticks
[task 7: write(0x00010000, 16) rejected]
user task 7: write(0x10000, 16) returned -1
[task 7: write(0xc0000000, 16) rejected]
user task 7: write(0xc0000000, 16) returned -1
[task 7: write(0x7fffff5f, 2147483647) rejected]
user task 7: write(buf, 0x7fffffff) returned -1
this buffer is fine
user task 7: write(buf, 20) returned 20
[task 7 (user rogue write) exited]
thread A: 2Each lie is caught by a different test. The first pointer,
0x10000, is below the split and the page is present in the
task’s directory, since the kernel is mapped everywhere; it fails the
page walk, because the entry has no USER bit, exactly as
the rogue of the previous section failed in hardware. The second,
0xC0000000, is the heap, where the kernel stacks of all
seven tasks live, and it fails the split test before any table is read.
The third is the program’s own stack buffer, a perfectly good pointer,
with a length that would take the kernel through the rest of the stack
page, the unmapped gap above it, and on across the split; it fails
WRITE_MAX before user_range_ok is even called.
The fourth call is the same buffer with its real length, and it
succeeds, prints the line, and returns 20. The program ends with
exit like any other, and the kernel is as it was: three
lines of complaint and nothing else.
Here are the three calls that reach user_range_ok, under
gdb, with a breakpoint conditioned on the task and finish
to show the return value:
(gdb) b user_range_ok if current_task->id == 7
Breakpoint 3 at 0x12502: file syscall.c, line 37.
(gdb) c
Breakpoint 3, user_range_ok (ptr=65536, len=16) at syscall.c:37
37 uint32_t end = ptr + len, page;
(gdb) p/x ptr
$6 = 0x10000
(gdb) p len
$7 = 16
(gdb) finish
0x000125b9 in syscall_handler (regs=0xc000dfc4) at syscall.c:62
62 if (regs->ecx > WRITE_MAX || !user_range_ok(regs->ebx, regs->ecx)) {
Value returned is $8 = 0
(gdb) c
..... the write() of the report line, accepted .....
(gdb) c
Breakpoint 3, user_range_ok (ptr=3221225472, len=16) at syscall.c:37
37 uint32_t end = ptr + len, page;
(gdb) p/x ptr
$12 = 0xc0000000
(gdb) p len
$13 = 16
(gdb) finish
0x000125b9 in syscall_handler (regs=0xc000dfc4) at syscall.c:62
62 if (regs->ecx > WRITE_MAX || !user_range_ok(regs->ebx, regs->ecx)) {
Value returned is $14 = 0
(gdb) c
..... the write() of the report line, accepted .....
(gdb) c
Breakpoint 3, user_range_ok (ptr=2147483344, len=48) at syscall.c:37
37 uint32_t end = ptr + len, page;
(gdb) p/x ptr
$18 = 0x7ffffed0
(gdb) p len
$19 = 48
(gdb) p/x ptr + len
$20 = 0x7fffff00
(gdb) finish
0x000125b9 in syscall_handler (regs=0xc000dfc4) at syscall.c:62
62 if (regs->ecx > WRITE_MAX || !user_range_ok(regs->ebx, regs->ecx)) {
Value returned is $21 = 1The last one is a report line: a buffer at
0x7ffffed0 on the user stack, 48 bytes long, ending at
0x7fffff00, inside the one user page, and accepted. The
third call of the program, with len = 0x7fffffff, never
appears, since WRITE_MAX stopped it in the handler.
13.10.3 Where the fault would have landed
It is worth being precise about what the check prevents, because the
alternative is not “the program gets killed”. Take the third lie, and
imagine the handler without any check, looping putc over
two gigabytes from the user stack page. The first 4 KiB print the stack.
The next access is to 0x80000000, the page above the stack,
which is not mapped: the processor raises #PF, and the
saved CS in the fault handler’s
struct registers is 0x08, because the
instruction that faulted was the kernel’s putc loop, in
ring 0. The page-fault handler of this chapter looks at that
CS, sees a kernel-mode fault, and panics: “unhandled page
fault”. The whole machine halts, every other task with it, because one
program passed one bad number to one system call. A fault inside the
kernel is, correctly, treated as a kernel bug; the kernel must therefore
make sure that a user program cannot cause one, and that is what
validation means. (Linux goes one step further:
copy_from_user lets the fault happen and recovers from it,
with a table of “if a fault occurs at this instruction, continue at that
one” that the fault handler consults before deciding that the kernel is
broken. The effect is the same as our check, at a lower cost on the
common path.)
This is also the answer to a question that puzzles newcomers to
operating systems: why a buffer overflow in a user program is the
program’s problem and not the kernel’s. A program that overruns an array
on its stack scribbles over its own variables and its own return
addresses, and the processor’s protection keeps every byte of the damage
inside pages marked USER in that task’s directory; the
worst it can do by itself is crash, with the page fault of the previous
section, or jump somewhere strange in ring 3. The only way for
the damage to spread into the kernel is through the system call
boundary, as a corrupted pointer or length that the program then passes
to write, and a kernel that validates sends it back with
-1. A kernel that does not validate turns every overflow in every
program into a kernel vulnerability: the attacker’s garbage becomes a
pointer the kernel dereferences in ring 0, and the “missing access
check” is, year after year, one of the most common categories of
operating system security bugs, in kernels far more careful than this
one. The rule is one sentence and user_range_ok is one
function; what makes it hard in a real kernel is remembering to call it
in every one of a few hundred system calls, for every pointer and every
length, including the ones buried in structures the pointer points
to.
13.11 Building, testing and debugging
13.11.1 The build
make in code/chapter13/os builds as before;
the only new compilation units are switch.asm,
rtc.c, syscall.c, task.c,
tss.c and userprog.c, with the same flags as
chapter 12. The kernel ELF is now 95872 bytes, 188 sectors, which is
what the bootloader is told to read. Its sections show the one
novelty:
$ readelf -S build/os/os
There are 16 section headers, starting at offset 0x17400:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 00010100 000100 002da5 00 AX 0 0 256
[ 2] .rodata PROGBITS 00012ec0 002ec0 0008c9 00 A 0 0 32
[ 3] .data PROGBITS 000137a0 0037a0 000084 00 WA 0 0 32
[ 4] .user PROGBITS 00014000 004000 001000 00 WAX 0 0 1
[ 5] .bss NOBITS 00015000 005000 004110 00 WA 0 0 4096
..... output omitted ......user starts at 0x14000, the first page
boundary after .data, and is exactly one page long, with
the five programs and their helpers; .bss follows at
0x15000. The file offset of each section equals its address
minus 0x10000, as the bootloader requires. Its flags are
WAX, writable, allocated and executable, because it holds
code and data together; the kernel maps it with
PAGE_WRITE | PAGE_USER, and a user program could overwrite
its own code. A kernel with a real ELF loader (chapter 14) maps code
read-only. The program header confirms that the file layout is the
memory layout: one LOAD segment, file offset 0,
FileSiz 0x5000, MemSiz 0x9110, the difference
being .bss.
$ readelf -l build/os/os
..... output omitted .....
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x00010034 0x00010034 0x00040 0x00040 R 0x4
LOAD 0x000000 0x00010000 0x00010000 0x05000 0x09110 RWE 0x1000
Section to Segment mapping:
Segment Sections...
00
01 .text .rodata .data .user .bss13.11.2 make test
$ make test
..... build output omitted .....
../../../tools/serial-test.sh build/disk.img "all tasks finished"
serial-test: ok, found "all tasks finished"
--- serial output ---
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
RTC: 2026-10-09 18:15:49 UTC
usable memory: 130555 KiB
32446 frames free before starting tasks
thread A: 1
thread B: 1
user task 3: hello from ring 3
user task 4: count 1
user task 5: about to read kernel memory
Page fault at 0x00018000: protection violation, read, user mode, eip=0x0001432f (error code 0x5)
killing task 5 (user rogue)
user task 6: tick 10, sleeping 25 ticks
[task 7: write(0x00010000, 16) rejected]
user task 7: write(0x10000, 16) returned -1
[task 7: write(0xc0000000, 16) rejected]
user task 7: write(0xc0000000, 16) returned -1
[task 7: write(0x7fffff5f, 2147483647) rejected]
user task 7: write(buf, 0x7fffffff) returned -1
this buffer is fine
user task 7: write(buf, 20) returned 20
[task 7 (user rogue write) exited]
thread A: 2
thread B: 2
user task 3: hello from ring 3
user task 4: count 2
thread A: 3
thread B: 3
user task 3: hello from ring 3
user task 4: count 3
[task 3 (user hello) exited]
[task 4 (user counter) exited]
user task 6: tick 35, sleeping 25 ticks
user task 6: tick 60, sleeping 25 ticks
user task 6: awake at tick 85, done
[task 6 (user sleeper) exited]
all tasks finished, 32432 frames free
qemu-system-i386: terminating on signal 15 from pid 139 (/bin/sh)Read the order of the lines against the run queue. The idle task
creates seven tasks and halts; at the tenth tick the timer switches to
thread A, the head of the queue. Each task prints one line and yields,
so the first round is A, B, 3, 4, 5, 6, 7, in creation order; task 5
dies in its first turn, task 6 goes to sleep, and task 7 makes its four
calls and exits. The second and third rounds, at ticks 20 and 30, are A,
B, 3, 4. At tick 35 the sleeper’s wake-up calls the scheduler early: A
and B return from their functions and are exited by
kernel_thread_start silently, 3 and 4 call
exit and are reported, then the sleeper prints and sleeps
twice more, and at tick 85 the idle task finds nothing left to reap.
13.11.3 A context switch in gdb
Start make qemu in one terminal and
make gdb in another; the .gdbinit connects and
stops at kmain. The first thing to look at is the run queue
just after the tasks are created, which is the first call of
task_reap:
(gdb) b task_reap
Breakpoint 2 at 0x12b5b: file task.c, line 193.
(gdb) c
Continuing.
Breakpoint 2, task_reap () at task.c:193
193 uint32_t flags = irq_save();
(gdb) p *current_task
$1 = {id = 0, state = TASK_RUNNING, esp = 0, kernel_stack = 0x8f000, page_directory = 0x16000 <kernel_directory>, name = 0x1373c "idle", next = 0xc0000010, entry = 0x0, user_stack_top = 0, wake_at = 0}
(gdb) set $t = current_task->next
(gdb) while $t != current_task
> printf "task %d \"%s\" state %d esp 0x%x kernel_stack %p dir %p\n", $t->id, $t->name, $t->state, $t->esp, $t->kernel_stack, $t->page_directory
> set $t = $t->next
>end
task 1 "thread A" state 0 esp 0xc0001ff8 kernel_stack 0xc0001010 dir 0x16000
task 2 "thread B" state 0 esp 0xc0003ff8 kernel_stack 0xc0003010 dir 0x16000
task 3 "user hello" state 0 esp 0xc0005ff8 kernel_stack 0xc0005010 dir 0x125000
task 4 "user counter" state 0 esp 0xc0007ff8 kernel_stack 0xc0007010 dir 0x12a000
task 5 "user rogue" state 0 esp 0xc0009ff8 kernel_stack 0xc0009010 dir 0x12f000
task 6 "user sleeper" state 0 esp 0xc000bff8 kernel_stack 0xc000b010 dir 0x134000
task 7 "user rogue write" state 0 esp 0xc000dff8 kernel_stack 0xc000d010 dir 0x139000The while loop walks the circle from idle back to idle.
Every task is TASK_READY (0), the kernel stacks are in the
heap, two pages apart, the two kernel threads share the kernel directory
at 0x16000 and the five user tasks each have a directory in
a frame of their own. Each saved esp is 24 bytes below the
top of its stack: the six prepared words. Here they are, for thread A
and for the first user task:
(gdb) x/6xw current_task->next->esp
0xc0001ff8: 0x00000202 0x00000000 0x00000000 0x00000000
0xc0002008: 0x00000000 0x00012732
(gdb) info symbol *(uint32_t *)(current_task->next->esp + 20)
kernel_thread_start in section .text
(gdb) x/6xw current_task->next->next->next->esp
0xc0005ff8: 0x00000202 0x00000000 0x00000000 0x00000000
0xc0006008: 0x00000000 0x00012747
(gdb) info symbol *(uint32_t *)(current_task->next->next->next->esp + 20)
user_task_start in section .textEFLAGS = 0x202, four zeros, and the start function:
task_alloc as promised. Now the switch itself. Break on the
mov [eax], esp of context_switch, the
instruction that freezes the old task, and continue:
(gdb) delete
(gdb) b *0x102cd
Breakpoint 3 at 0x102cd: file switch.asm, line 37.
(gdb) c
Continuing.
Breakpoint 3, context_switch () at switch.asm:37
37 mov [eax], esp ; the old task is now frozen here
(gdb) bt
#0 context_switch () at switch.asm:37
#1 0x00000002 in ?? ()
#2 0x000118d4 in irq0_handler (regs=0x8ffac) at pit.c:39
#3 0x00010e9d in isr_dispatch (regs=0x8ffac) at isr.c:73
#4 0x000102a6 in isr_common () at isr_stubs.asm:115
#5 0x0008ffac in ?? ()
#6 0x0001011b in _start () at entry.asm:30
(gdb) p/x $eax
$2 = 0x19068
(gdb) p/x $edx
$3 = 0xc0001ff8
(gdb) x/6xw $esp
0x8ff20: 0x00000002 0x00019110 0x00007cd8 0x00000000
0x8ff30: 0x0008ff60 0x00012a52
(gdb) x/6xw $edx
0xc0001ff8: 0x00000202 0x00000000 0x00000000 0x00000000
0xc0002008: 0x00000000 0x00012732
(gdb) p current_task->name
$4 = 0x1335e "thread A"The backtrace tells the story: the timer interrupt
(isr_common, isr_dispatch,
irq0_handler) interrupted _start’s call of
kmain, that is, the idle task’s hlt, and the
handler called schedule(). (Frame #1 is
garbage, because gdb does not know that the assembly
function pushed five words; the real caller is schedule,
whose address, 0x12a52, is the sixth word at
$esp.) current_task already names thread A:
the bookkeeping is done before the switch. EAX points into
idle_task (its esp field,
0x19068), EDX holds thread A’s prepared
esp, and the two stacks are side by side: the idle task’s,
at 0x8ff20, with EFLAGS = 0x2 on top
(interrupts disabled, as they are in every handler), its callee-saved
registers and the return address into schedule; and thread
A’s, which we have seen. Step through the rest:
(gdb) si
38 mov esp, edx ; from here on we are the new task
(gdb) si
39 popfd
(gdb) p/x $esp
$5 = 0xc0001ff8
(gdb) si
40 pop edi
..... output omitted .....
(gdb) si
44 ret
(gdb) info registers eip esp ebp ebx esi edi
eip 0x102d6 0x102d6 <context_switch+22>
esp 0xc000200c 0xc000200c
ebp 0x0 0x0
ebx 0x0 0x0
esi 0x0 0x0
edi 0x0 0x0After mov esp, edx, ESP is in the heap, on
thread A’s stack; after the five pops the callee-saved registers are the
zeros of the prepared frame, and ret is about to pop
0x12732, kernel_thread_start. Thread A has
never run and is about to start, in the middle of what was a timer
interrupt of another task. Continue a few more times and watch who
switches to whom, and from where:
(gdb) c
Continuing.
Breakpoint 3, context_switch () at switch.asm:37
37 mov [eax], esp ; the old task is now frozen here
(gdb) bt
#0 context_switch () at switch.asm:37
#1 0x00000096 in ?? ()
#2 0x00012a70 in yield () at task.c:150
#3 0x00010f22 in thread_a () at kernel.c:38
#4 0x00012742 in kernel_thread_start () at task.c:31
#5 0x00000fe0 in ?? ()
(gdb) p current_task->name
$6 = 0x13367 "thread B"
(gdb) x/6xw $esp
0xc0001f7c: 0x00000096 0x00000000 0x00000000 0x00000000
0xc0001f8c: 0xc0001fbc 0x00012a52
(gdb) c
..... output omitted .....
#2 0x00012a70 in yield () at task.c:150
#3 0x00010f57 in thread_b () at kernel.c:48
(gdb) p current_task->name
$7 = 0x13370 "user hello"
(gdb) c
..... output omitted .....
#2 0x0001263f in syscall_handler (regs=0xc0005fc4) at syscall.c:73
#3 0x00010e9d in isr_dispatch (regs=0xc0005fc4) at isr.c:73
#4 0x000102a6 in isr_common () at isr_stubs.asm:115
(gdb) p current_task->name
$8 = 0x1337b "user counter"
(gdb) c
..... output omitted .....
(gdb) p current_task->name
$9 = 0x13388 "user rogue"
(gdb) c
..... output omitted .....
#2 0x00012b47 in task_exit () at task.c:187
#3 0x000113d4 in page_fault_handler (regs=0xc0009fc4) at paging.c:114
#4 0x00010e9d in isr_dispatch (regs=0xc0009fc4) at isr.c:73
(gdb) p current_task->name
$10 = 0x13393 "user sleeper"
(gdb) c
..... output omitted .....
#2 0x00012ab3 in task_sleep (nticks=25) at task.c:160
#3 0x000126a2 in syscall_handler (regs=0xc000bfc4) at syscall.c:86
#4 0x00010e9d in isr_dispatch (regs=0xc000bfc4) at isr.c:73
(gdb) p current_task->name
$11 = 0x133a0 "user rogue write"
(gdb) c
..... output omitted .....
#2 0x00012b47 in task_exit () at task.c:187
#3 0x00012674 in syscall_handler (regs=0xc000dfc4) at syscall.c:78
#4 0x00010e9d in isr_dispatch (regs=0xc000dfc4) at isr.c:73
(gdb) p current_task->name
$12 = 0x1373c "idle"The second switch is thread A yielding to thread B: this time the
frozen stack is a real one, with EFLAGS = 0x96 (the
arithmetic flags of whatever yield was computing,
IF clear thanks to irq_save), a real
EBP and the return address into schedule. Then
B yields to task 3; task 3 reaches the kernel through
int 0x80 (isr_common,
syscall_handler, the SYS_YIELD case) and
switches to task 4, which does the same towards task 5; task 5 is killed
from inside the page-fault handler and the processor goes to task 6,
which sleeps (task_sleep under
syscall_handler) and hands over to task 7; and task 7 exits
through SYS_EXIT and the processor goes back to idle. Five
different ways into schedule(), one
context_switch.
13.11.4 Into ring 3 and back
Restart QEMU and break on the iret of
enter_user_mode:
(gdb) b *0x102f6
Breakpoint 2 at 0x102f6: file switch.asm, line 76.
(gdb) c
Continuing.
Breakpoint 2, enter_user_mode () at switch.asm:76
76 iret
(gdb) x/5xw $esp
0xc0005fdc: 0x00014000 0x0000001b 0x00000202 0x80000000
0xc0005fec: 0x00000023
(gdb) info registers cs ss ds es
cs 0x8 8
ss 0x10 16
ds 0x23 35
es 0x23 35
(gdb) p/x $cr3
$1 = 0x125000
(gdb) p current_task->name
$2 = 0x13370 "user hello"
(gdb) p/x tss
$3 = {prev_task_link = 0x0, esp0 = 0xc0006010, ss0 = 0x10, esp1 = 0x0, ss1 = 0x0, esp2 = 0x0, ss2 = 0x0, cr3 = 0x0, eip = 0x0, eflags = 0x0, eax = 0x0, ecx = 0x0, edx = 0x0, ebx = 0x0, esp = 0x0, ebp = 0x0, esi = 0x0, edi = 0x0, es = 0x0, cs = 0x0, ss = 0x0, ds = 0x0, fs = 0x0, gs = 0x0, ldt_selector = 0x0, trap = 0x0, iomap_base = 0x68}The five words of figure 7-4 are on the stack:
EIP = 0x14000 (user_hello),
CS = 0x1b, EFLAGS = 0x202,
ESP = 0x80000000, SS = 0x23. We are still in
ring 0 (CS = 0x8), but DS and ES
already hold the user selector. CR3 is task 3’s directory,
loaded by schedule(), and the TSS has
ESP0 = 0xc0006010, the top of task 3’s kernel stack, with
everything else zero: the hardware task-switching fields are unused. Now
one instruction:
(gdb) si
user_hello () at userprog.c:16
16 {
(gdb) info registers cs ss ds eip esp eflags
cs 0x1b 27
ss 0x23 35
ds 0x23 35
eip 0x14000 0x14000 <user_hello>
esp 0x80000000 0x80000000
eflags 0x202 [ IOPL=0 IF ]
(gdb) monitor info registers
CPU#0
EAX=80000023 EBX=00000000 ECX=00014000 EDX=80000000
ESI=00000000 EDI=00000000 EBP=c000600c ESP=80000000
EIP=00014000 EFL=00000202 [-------] CPL=3 II=0 A20=1 SMM=0 HLT=0
ES =0023 00000000 ffffffff 00cff300 DPL=3 DS [-WA]
CS =001b 00000000 ffffffff 00cffa00 DPL=3 CS32 [-R-]
SS =0023 00000000 ffffffff 00cff300 DPL=3 DS [-WA]
DS =0023 00000000 ffffffff 00cff300 DPL=3 DS [-WA]
FS =0023 00000000 ffffffff 00cff300 DPL=3 DS [-WA]
GS =0023 00000000 ffffffff 00cff300 DPL=3 DS [-WA]
LDT=0000 00000000 0000ffff 00008200 DPL=0 LDT
TR =0028 000190a0 00000067 00008900 DPL=0 TSS32-avl
GDT= 00015000 0000002f
IDT= 00015040 000007ff
CR0=80000011 CR2=00000000 CR3=00125000 CR4=00000000
..... output omitted .....This is the first ring 3 instruction ever executed by our kernel.
QEMU’s register dump says CPL=3, and shows the hidden parts
of the segment registers: all six hold descriptors with
DPL=3, base 0 and limit ffffffff, the access
bytes fa (code) and f3 (data, with the
accessed bit set by the load). TR holds 0x28
and the hidden part shows the TSS base 0x190a0 (the
tss variable in .bss), limit
0x67, and type TSS32-avl; the GDT at
0x15000 has limit 0x2f, six entries. (QEMU
prints the descriptor as still “available” after ltr; a
real processor marks it busy, as it does with the accessed bit on far
jumps, see chapter 9.) The first system call of user_hello
is getpid; break in the handler:
(gdb) b syscall_handler
Breakpoint 3 at 0x1257e: file syscall.c, line 58.
(gdb) c
Continuing.
Breakpoint 3, syscall_handler (regs=0xc0005fc4) at syscall.c:58
58 switch (regs->eax) {
(gdb) p regs->eax
$4 = 4
(gdb) p/x regs->cs
$5 = 0x1b
(gdb) p/x regs->user_esp
$6 = 0x7fffff78
(gdb) x/i regs->eip - 2
0x14067 <user_hello+103>: int 0x80
(gdb) p current_task->kernel_stack
$7 = (void *) 0xc0005010
(gdb) p/x tss.esp0
$8 = 0xc0006010
(gdb) p *regs
$9 = {gs = 35, fs = 35, es = 35, ds = 35, edi = 0, esi = 0, ebp = 2147483644, esp_dummy = 3221250036, ebx = 0, edx = 0, ecx = 0, eax = 4, int_no = 128, err_code = 0, eip = 82025, cs = 27, eflags = 519, user_esp = 2147483512, ss = 35}regs is at 0xc0005fc4, on task 3’s kernel
stack, 76 bytes below the ESP0 the processor took from the
TSS: 20 bytes pushed by the processor (SS,
ESP, EFLAGS, CS,
EIP), 8 by the stub, 48 by isr_common. The
saved CS is 0x1b, the saved EIP
is the instruction after int 0x80, and the
user_esp and ss fields that chapter 11 told us
not to read are now meaningful: the user stack pointer
0x7fffff78 inside the user stack page, and
SS = 0x23. EAX is 4, SYS_GETPID.
Continue to the next call, a write, and let the handler
finish:
(gdb) c
Continuing.
Breakpoint 3, syscall_handler (regs=0xc0005fc4) at syscall.c:58
58 switch (regs->eax) {
(gdb) p regs->eax
$10 = 1
(gdb) x/s regs->ebx
0x7fffff7c: "user task 3: hello from ring 3\n"
(gdb) p regs->ecx
$11 = 31
(gdb) finish
Run till exit from #0 syscall_handler (regs=0xc0005fc4) at syscall.c:58
0x00010e9d in isr_dispatch (regs=0xc0005fc4) at isr.c:73
73 handler(regs);
(gdb) p regs->eax
$12 = 31The string lives on the user stack (msg is a local
array), the digit 3 has been patched in by the previous
call, ECX carries its length, 31 bytes, and after the
handler regs->eax holds the return value, the 31 bytes
written, that iret will deliver. Finally, the point of
separate directories: break in task 4 and compare CR3:
(gdb) delete
(gdb) b user_counter
Breakpoint 4 at 0x1412b: file userprog.c, line 30.
(gdb) c
Continuing.
Breakpoint 4, user_counter () at userprog.c:30
30 char msg[] = "user task ?: count ?\n";
(gdb) info registers cs eip esp
cs 0x1b 27
eip 0x1412b 0x1412b <user_counter+7>
esp 0x7fffff78 0x7fffff78
(gdb) p/x $cr3
$13 = 0x12a000Task 3 ran with CR3 = 0x125000, task 4 runs with
CR3 = 0x12a000; both have a user stack at
0x7FFFF000, in two different frames, and neither can see
the other’s.
13.11.5 The page fault
One last session, for the rogue:
(gdb) b page_fault_handler
Breakpoint 2 at 0x1130e: file paging.c, line 104.
(gdb) c
Continuing.
Breakpoint 2, page_fault_handler (regs=0xc0009fc4) at paging.c:104
104 asm volatile("mov %%cr2, %0" : "=r"(cr2));
(gdb) p current_task->name
$1 = 0x13388 "user rogue"
(gdb) p/x regs->err_code
$2 = 0x5
(gdb) p/x regs->cs
$3 = 0x1b
(gdb) x/i regs->eip
0x1432f <user_rogue+237>: mov eax,ds:0x18000
(gdb) p/x current_task->page_directory[0]
$4 = 0x17027
(gdb) p/x kernel_directory[0]
$5 = 0x17023
(gdb) p/x ((uint32_t *)(current_task->page_directory[0] & 0xfffff000))[0x18]
$6 = 0x18063
(gdb) p/x ((uint32_t *)(current_task->page_directory[0] & 0xfffff000))[0x14]
$7 = 0x14027
(gdb) p/x current_task->page_directory[0x1ff]
$8 = 0x131027
(gdb) p/x kernel_directory[0x1ff]
$9 = 0x0
(gdb) p/x current_task->page_directory[0x300]
$10 = 0x120023
(gdb) p/x kernel_directory[0x300]
$11 = 0x120023
(gdb) p &ticks
$12 = (volatile uint32_t *) 0x18000 <ticks>Everything the chapter claimed about the page tables is in these
numbers. Entry 0 of both directories points to the same page table,
0x17000 (kernel_table0); the task’s entry has
flags 0x27, with the USER bit (4) that
get_table added, the kernel’s has 0x23,
without it. In that shared table, the entry for 0x18000,
the page of ticks, is 0x18063: present,
writable, accessed, dirty, not user, hence error code 5; the
entry for 0x14000, the .user page, is
0x14027: present, writable, user. Entry 0x1ff
(addresses 0x7FC00000 and up) is the user stack’s page
table, which exists only in the task’s directory; entry
0x300 (0xC0000000, the heap) is the same table
in both, the sharing that lets every task see the kernel stacks of the
others. And regs->cs & 3 is 3, so this fault kills a
task rather than the kernel.
13.11.6 Limitations
This is a working multitasking kernel with memory protection, and it
is also the smallest one that deserves the name. What it lacks, in rough
order of importance: a way for a task to wait for a device
rather than for a time, so that a task blocked on the keyboard does not
spin (the TASK_SLEEPING state is half of it; the other half
is a queue per device and a wake-up from its interrupt handler); locking
in kprintf, in the heap and in every other shared
structure; a time slice that is counted per task rather than from the
global tick; priorities; user programs that come from somewhere other
than the kernel image, which is chapter 14; and the
fork/exec/wait family that makes
processes useful to each other, which is chapter 15. None of these
changes the mechanism of this chapter, which every kernel from Linux to
the one you will write next shares: one kernel stack per task, a switch
that swaps stacks, a TSS for the ring 3 to ring 0 stack change,
iret to go down, a gate to come up.
13.12 Exercises
Exercise 13.1. Add a priority field to
struct task and change schedule() so that
among the ready tasks it picks the one with the highest priority, round
robin among equals. Give thread B a higher priority than thread A and
explain the new order of the output. Then give the idle task the lowest
priority and check that it only runs when nothing else can; what happens
to task_reap?
Exercise 13.2. task_wake_sleepers walks
the whole run queue on every tick, a hundred times a second, even when
nothing sleeps. Replace it with a sleep queue: a second list,
sorted by wake_at, into which task_sleep
inserts the task at the right place, so that the timer handler only
looks at the head. Keep the wrap-around comparison correct in the
insertion. Then build an alarm(n) system call on top of it:
the task keeps running, and when the time comes the kernel writes a line
on its behalf. Where does the kernel run that code, on whose stack, and
what may it not do there (reread the section on locks)? Finally verify
with monitor info registers that the idle task’s
hlt is where the processor spends its time while every task
sleeps.
Exercise 13.3. Make kprintf,
kmalloc and kfree atomic with
irq_save and irq_restore. Then provoke the bug
it fixes: remove the yield() calls from
thread_a and thread_b, make each print a long
line in a loop that runs for several seconds, and compare the output
with and without your fix. Now add a kernel thread that calls
kmalloc and kfree in a loop, run it alongside
the others, and find out how long the unprotected heap survives. Why is
disabling interrupts an acceptable lock on a single processor and not on
a multiprocessor?
Exercise 13.4. Implement a fork-like
call for kernel threads: task_clone() creates a new task
whose kernel stack is a copy of the current one, so that both
return from task_clone, the parent with the child’s id and
the child with 0. You must copy the stack, adjust the saved
ESP, and fix any pointer into the stack (start
with EBP). Where exactly in the copied stack does the
child’s return value go?
Exercise 13.5. Write a user task that executes
int 0x80 with EAX = 42, then one that executes
int 0x20, then one that executes cli, then one
that executes in al, 0x60. For each, predict what the
kernel prints before running it, using sections 6.9, 7.12.1.2 and Volume
1 section 20.5 of the Intel SDM; then make the general-protection fault
handler kill the task instead of halting, as the page-fault handler
does.
Exercise 13.6. Move the user stack from
0x80000000 to 0x00400000, the first address
after the kernel’s static page table, and then to
0x00300000. For each case, say which page table
task_create_user writes the stack’s entry into, whether
that table is shared with the kernel directory, what happens to the
identity mapping of that address in every task, and what
paging_free_directory does with the stack’s frame when the
task dies. Check your answers in gdb the way the page-fault session
above does. Then make task_create_user refuse a user
address that falls in a region the kernel directory already maps.
Exercise 13.7. Read section 10.3 “Task Switching” of
the Intel SDM Volume 3A and list every piece of processor state that a
hardware task switch saves into the TSS and that
context_switch does not save. For each, explain why our
kernel does not need to save it (the same value in every task, saved
elsewhere, or not used). Then read section 10.7 and say which items of
your list a 64-bit kernel would have to handle differently.
13.13 Check your understanding
context_switchsaves four general registers andEFLAGS, while a hardware task switch saves everything. Suppose a kernel thread kept a value inEAXacross a call toyield(). Would it survive, and whose fault is it if it does not: the scheduler’s or the compiler’s?schedule()setsTSS.esp0to the top of the next task’s kernel stack, even when that task is in the middle of a system call with a deep stack. Why is the top always correct, and what would happen if the task were a kernel thread that was preempted while running on its kernel stack and the next ring 3 interrupt used that sameESP0?The EOI moved before the handler in
isr_dispatch. In a kernel with a trap gate for the timer instead of an interrupt gate, would the early EOI still be safe? Describe the sequence of events on a tick that arrives while the handler is still running.The user segments of the GDT have base 0 and limit 4 GiB, exactly like the kernel’s, so segmentation does not isolate user programs at all. Why do they have to exist anyway, and what single bit, in which table, actually keeps the rogue task out of
ticks?task_sleepsets the task’s state toTASK_SLEEPINGand then callsschedule(). If a timer tick arrived between those two statements, with the assignment done and the switch not yet made, what wouldtask_wake_sleepersandschedule()do, and which line oftask_sleepmakes the question moot?The tick comparison is written
(int32_t)(ticks - t->wake_at) >= 0. A task callssleep(0x90000000), about 280 days. What does the comparison conclude on the very next tick, and what does that tell you about the longest sleep this kernel can represent?irq_saveis a correct lock on one processor. Name the one piece of code that can still run inside a critical section even withIFclear, and explain whytask_sleepis allowed to callschedule()from inside one whilekmallocwould not be.user_range_oktestsend < ptrbefore anything else. Suppose that test were removed and thatWRITE_MAXdid not exist. Find a pointer and a length for which the split test and the page walk both pass although the range covers almost the whole address space, and say what theputcloop would do with them.