15 Address spaces: fork and exec
The kernel of chapter 14, File system, loads a program from an ext2
disk and runs it in ring 3, but look at who decides what runs:
kmain calls elf_exec("/bin/hello") and
elf_exec("/bin/count"), and that is the complete list of
programs the machine will ever run. A program cannot start another
program, cannot find out when it ends, and cannot learn whether it
succeeded. The kernel is a loader with a scheduler attached, and the
programs are its passengers. Unix’s answer, present in its first edition
of 1971 (Thompson and
Ritchie 1971) and unchanged since, is four system calls:
fork makes a copy of the calling process; exec
replaces the program of a process by one loaded from a file;
exit ends a process with a status; wait lets a
parent block until a child has exited and collects that status. With
these four, a program can start any other program and get its result
back, and the kernel starts exactly one program, init,
which starts the rest. By the end of this chapter that is what our
kernel does:
exec /bin/init: segment 0 at 0x08048000, 1792 bytes in file, 1792 in memory
init: pid 1
init: forking for /bin/hello
[task 1: fork() -> task 2]
[task 1: copy-on-write 0x7ffff000: copied (2 users)]
[task 2: copy-on-write 0x7ffff000: made writable (last user)]
[task 2: exec("/bin/hello")]
exec /bin/hello: segment 0 at 0x08048000, 343 bytes in file, 343 in memory
Hello from user space, pid 2
[task 2 (/bin/hello) exited with status 0]
[task 1: wait() collected task 2, status 0]
init: child 2 exited with status 0
..... output omitted .....
all processes finished, 32430 frames free, 11 copy-on-write faults, 6 pages copied, 3 pages mapped on demandThe chapter is about what fork really copies, which is
the interesting part. A naive fork copies every page of the
parent, and then exec throws the copy away a microsecond
later; every Unix since the 1980s avoids the waste with
copy-on-write: the child shares the parent’s pages, read-only,
and a page is copied only when one of the two writes to it. That is a
mechanism built entirely out of things we already have, the page tables
of chapter 12, the page-fault handler and its error code, and the frame
allocator, plus one idea, counting how many address spaces use a frame.
The two lines copied (2 users) and
made writable (last user) above are that mechanism at work,
and we will watch it in the debugger with CR2, the error
code and the reference count in front of us. exec and
wait are simpler, and each has one subtlety worth a
section: exec must copy its argument before destroying the
address space the argument lives in, and wait needs a
process to survive its own death for a while, which is what a
zombie is. And once the fault handler has learned from
fork that a page fault can be a request rather than an
error, exec can stop allocating pages nobody has asked for
yet: the section “Pages on demand” makes the .bss and the
stack appear one page at a time, as they are touched.
Running this chapter’s code
The code is in code/chapter15/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/chapter15/os os01make builds the bootloader, the kernel, the four user
programs (hello and count from chapter 14, and
the new init and bigbss) and
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 30 seconds, for the exit status of the three children
init execed
(init: child 2 exited with status 0,
init: child 3 ... and init: child 4 ...), the
line bigbss prints after a wait whose status
went to a page nobody had touched
(bigbss: child exited with status 3), the copy-on-write
demonstration (init: shared = 42), the line the kernel read
back from /log.txt (chapter 14) and the kernel’s final
message; then it runs e2fsck and debugfs on
the file system as chapter 14 did. The debugger sessions of this chapter
break on C functions by name, so they work unchanged after you edit the
code; the frame numbers and addresses are those of the build in the
repository.
15.1 The Unix process model
15.1.1 Four system calls
Every Unix shell, and every program that runs another, does the same
four-step dance, and it is worth having it in C before looking at how
the kernel provides it. This is run() in the
init program of this chapter, minus the printing:
pid = fork();
if (pid == 0) {
exec(path); /* only returns when it failed */
exit(127);
}
pid = wait(&status);fork() is the strange one: it is called once and returns
twice. After it, two processes exist that are byte-for-byte copies of
each other, both at the instruction after the call, each with its own
copy of every variable; the only difference between them is the value
fork() returned, 0 in the child and the child’s process id
in the parent, and the if on that value is where the two
lives diverge. The child calls exec(path), which loads the
program in path into the child itself: the child’s
code, data and stack are thrown away and replaced by the new program’s,
its registers are reset, and it starts at the new program’s entry point.
exec never returns on success, since there is nothing to
return to; it returns -1 when the file does not exist or is not a
program, in which case the child is still the old program and can report
the error. Meanwhile the parent calls wait(&status),
which blocks until some child has exited and returns its id and
the value that child passed to exit.
Why two calls, fork and exec, rather than
one spawn(path) that creates a process running a program,
which is what Windows’s CreateProcess and the
posix_spawn of modern Unix do? Because between the
fork and the exec the child is a complete
process, running the parent’s code, and it can change anything about
itself before it becomes the new program: redirect its output into a
file, change its directory, close what it should not inherit, lower its
privileges. The shell’s ls > out.txt is
fork, then in the child open out.txt as
the standard output, then exec("ls"); the kernel does
not need to know anything about redirection. A spawn must
take an argument for every such thing anyone will ever want, and
CreateProcess has ten parameters and a structure of
attributes. The price of the Unix design is that fork must
copy a process that is about to discard the copy, which is the problem
this chapter spends most of its pages on.
15.1.2 What a process id is
The process id that fork returns and
wait reports is our task id, the id field of
struct task that task_alloc has assigned since
chapter 13. init gets 1, because it is the first task
created, as on Unix, where init has pid 1 and is the
ancestor of every other process. The kernel’s task 0, the idle task, is
kmain itself; Linux also has a task 0, the
swapper, which is the code that booted the machine and becomes
the idle loop.
15.1.3 The process tree
wait needs a notion that chapter 13 did not have: a
parent. Every task now records which task created it, and the
tasks form a tree with the idle task at the root: idle creates
init, init forks children, and so on. Two new
fields in struct task carry the whole model:
os/task.h (additions)
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_WAITING, /* chapter 15: in wait(), until a child exits */
TASK_DEAD /* exited; a zombie until its parent (or idle) frees it */
};
#define TASK_NAME_MAX 32 char name[TASK_NAME_MAX]; /* chapter 15: owned, since exec() renames */ /* Chapter 15: the process tree. A task's parent collects its exit
status with wait(); orphans are adopted by the idle task. */
struct task *parent;
int exit_status;The name becomes an array rather than a pointer, because until now
every name was a string literal ("/bin/hello" in
kmain) and from now on it comes from a user program’s
exec argument, which will not exist any more by the time
anyone prints the name. TASK_WAITING is the state of a
parent blocked in wait, and it has a section of its own
below.
15.2 What an address space is, really
15.2.1 The page directory is the process
Chapter 13 gave every user task a page directory of its own and
chapter 14 loaded a program into it; the gdb sessions showed
CR3 changing from 0x125000 to
0x12a000 as the scheduler moved from one task to the next.
It is worth stating what that means, because fork is
nothing but an operation on it: the address space of a process is
its page directory. Everything the program can see, its code at
0x08048000, its stack at 0x7FFFF000, is
reachable from the 4 KiB of that directory and nowhere else; two
processes with different directories cannot see each other’s memory
because there is no path from one directory to the other’s frames. “Copy
the process” therefore means “build a second directory that leads to the
same contents”, and the whole question is how much of what the directory
leads to must be duplicated and how much can be shared.
15.2.2 What is shared: the kernel’s page tables
Open the Intel SDM Volume 3A, section 5.3 “32-Bit Paging”, once more:
a linear address is split into a directory index (bits 31:22), a table
index (21:12) and an offset, and the directory entry (Table 5-5) holds
the physical address of a page table, not of a page. This
two-level shape is what makes sharing cheap.
paging_clone_kernel_directory, in chapter 13, copies the
kernel directory’s 1024 entries into a fresh frame, so that the new
directory’s entries point to the same page tables as the
kernel’s: the identity map of the first 128 MiB (entries 0 to 31) and
the heap (entry 0x300) are described once, in page tables
that every directory refers to, and a change to one of those tables, a
new heap page for instance, is visible in every address space at once.
That is the reason a system call can run with the task’s directory in
CR3: the kernel’s code, data and stacks are mapped in every
task, supervisor-only, at the same addresses. A forked child must share
these too, and it gets them for free from the same clone.
15.2.3 What is private: the user’s page tables
The rest of a directory is the process’s own: the page table for its
program (entry 0x20, for addresses 0x08000000
to 0x083FFFFF) and the one for its stack (entry
0x1ff). The kernel directory has no table there, so
paging_free_directory of chapter 13 recognizes these tables
as private by comparing each entry with the kernel directory’s, and
frees them with their pages when the task dies. fork uses
the same test the other way round: a table that differs from the
kernel’s must be copied, entry by entry, into a table of the
child’s own, because the two processes will diverge, one page at a time,
and a shared table could not describe two different sets of pages.
The pages themselves are a different matter. After fork
the child’s stack must hold the same bytes as the parent’s, and the
obvious way is a new frame and a memcpy. The clever way,
the one in the figure, is to let both tables point at the same
frame, and to arrange that neither process can write to it: both entries
lose their R/W bit. Reading is unaffected, and reading is most of what a
program does with most of its pages. The first write by either process
raises a page fault, and the fault handler, which can tell this fault
from every other kind, gives the writer a private copy of that one page
and makes it writable. A page that is never written is never copied, and
a child that calls exec right after fork,
which is the normal case, has copied a page or two instead of its whole
memory.
Three pieces of bookkeeping make this work, and the next three sections build them: a count of how many address spaces use each frame, so that the fault handler knows whether a copy is needed; a mark in the page-table entry, so that the handler knows that a read-only page is read-only because of fork and not because the program is misbehaving; and the fault handler’s new case.
15.3 fork
15.3.1 Counting the users of a frame
The frame allocator of chapter 12 keeps one bit per frame, used or
free. A bit cannot count, and copy-on-write has to answer the question
“is anyone else still using this frame?” when a write faults. Linux
keeps a struct page for every frame of RAM, with a
reference count and much else (mem_map, 64 bytes per
frame); we keep the smallest thing that counts, one byte per frame:
os/pmm.c (additions)
/* Chapter 15: how many page-table entries, in how many address spaces,
point at each frame. A bit can say "used" but cannot count, and
copy-on-write needs to know whether a frame has one user or several.
One byte per frame is 32 KiB of .bss for 128 MiB of RAM, and 255 users
are more than fork will ever give a page. Frames that were never
allocated by pmm_alloc_frame() (the kernel image, the first megabyte)
keep a count of 0 and are never freed. */
static uint8_t refcount[FRAMES_MAX];/* Drop one user of the frame; the frame is only free when nobody maps
it any more. */
void pmm_free_frame(uint32_t phys)
{
uint32_t frame = phys / PAGE_SIZE;
if (frame >= frames_total || !frame_is_used(frame))
return;
if (refcount[frame] > 1) {
refcount[frame]--;
return;
}
refcount[frame] = 0;
frame_set_free(frame);
frames_free++;
}
void pmm_frame_ref(uint32_t phys)
{
uint32_t frame = phys / PAGE_SIZE;
if (frame < frames_total && refcount[frame] < 255)
refcount[frame]++;
}
uint32_t pmm_frame_refcount(uint32_t phys)
{
uint32_t frame = phys / PAGE_SIZE;
return frame < frames_total ? refcount[frame] : 0;
}pmm_alloc_frame sets the count to 1 (one line added to
it), pmm_frame_ref adds a user, and
pmm_free_frame changes meaning: it now drops a
user, and only the last drop returns the frame to the bitmap. Every
existing caller is unaffected, since every frame they free has exactly
one user, and paging_free_directory can stay as it is: when
a process dies, each of its pages is dropped, and a page it still shared
with a sibling simply loses one user. The array lives in
.bss, 32 KiB that grow the kernel image in memory but not
on disk (__kernel_end, 0x1e110 in chapter 14,
is 0x28130 with this chapter’s code, still well below the
stack at 0x90000). The choice of a byte is a choice of
simplicity over range: 255 sharers of one frame is more than
fork will produce in this book, and question 7 at the end
asks what happens at 256.
15.3.2 The copy-on-write mark
The page-table entry format is Table 5-6 of the Intel SDM Volume 3A, “Format of a 32-Bit Page-Table Entry that Maps a 4-KByte Page”. Read it line by line: bits 0 to 8 all mean something to the processor, bits 31:12 are the frame, and bits 11:9 are listed as Ignored. “Ignored” means that the processor never reads them, whatever their value, which makes them the operating system’s: Linux calls them software bits, the AMD manual calls them AVL, “Available to Software” (APM Volume 2, section 5.4.1 “Field Definitions”), and every kernel uses them to remember something about a page that the hardware does not need to know. We use bit 9:
os/paging.h (addition)
/* Chapter 15: bits 11:9 of an entry are "Ignored" by the CPU (SDM Vol. 3A,
Table 5-6; AMD APM Vol. 2, section 5.4.1 "Available to Software (AVL)"),
so a kernel may keep its own flags there. COW marks a page that fork()
shares read-only between two address spaces: the first write to it
faults, and the handler gives the writer a private copy. */
#define PAGE_COW 0x200 /* bit 9: copy-on-write (ours, not the CPU's) */Why a mark at all, when the R/W bit already makes the page read-only? Because the fault handler must distinguish two reasons for a write to a read-only page: the page is shared and the write is legitimate, or the page is genuinely read-only and the program is misbehaving. Both arrive as the same exception with the same error code; the mark is what tells them apart. Our kernel maps every user page writable today, so the second case does not arise yet, but exercise 15.4 maps program text read-only and then it does.
15.3.3 Copying the page tables
os/paging.c (paging_fork_directory)
uint32_t *paging_fork_directory(uint32_t *parent)
{
uint32_t *child = paging_clone_kernel_directory();
uint32_t i, j;
for (i = 0; i < 1024; i++) {
uint32_t *table, *copy;
if (!(parent[i] & PAGE_PRESENT))
continue;
if ((parent[i] & PAGE_FRAME) == (kernel_directory[i] & PAGE_FRAME))
continue; /* a kernel table: the clone shares it */
/* A private page table: the child gets one of its own, with the
same entries, because the two address spaces will diverge entry
by entry as pages are written. */
table = (uint32_t *)(parent[i] & PAGE_FRAME);
copy = (uint32_t *)pmm_alloc_frame();
if (copy == 0)
panic("fork: out of frames for a page table");
for (j = 0; j < 1024; j++) {
uint32_t virt = (i << 22) | (j << 12);
if (!(table[j] & PAGE_PRESENT)) {
copy[j] = 0;
continue;
}
/* The page itself is shared, so a write by either side must
fault: clear R/W in the parent's entry (the TLB may still
hold the writable translation, hence INVLPG) and mark the
page COW so that the fault handler knows what the read-only
bit means here. A page that was read-only already (none
today) is just shared. */
if (table[j] & PAGE_WRITE) {
table[j] = (table[j] & ~PAGE_WRITE) | PAGE_COW;
invlpg(virt);
}
copy[j] = table[j];
pmm_frame_ref(table[j] & PAGE_FRAME);
}
child[i] = (uint32_t)copy | (parent[i] & 0xFFF);
}
/* The child's directory is not in CR3 yet; the MOV to CR3 that loads
it will flush the TLB (SDM Vol. 3A, section 5.10.4.1), so nothing
is stale on its side. */
return child;
}The function is the figure in C. It starts from a clone of the kernel
directory, so the kernel’s tables are shared; then, for each directory
entry that is present and differs from the kernel’s, it allocates a
table for the child and walks the parent’s table. Each present entry is
modified in the parent’s table (R/W cleared, COW set) and
copied as modified into the child’s; the frame’s count goes up by one.
The directory entry of the child gets the new table with the parent’s
flags (0x27: present, writable, user, the permissive
directory-level bits of chapter 12).
The invlpg is the subtle line. Section 5.10 of the SDM,
“Caching Translation Information”, explains that the processor keeps
recently used translations in the translation lookaside buffer
(5.10.2), including their access rights, and that changing a page-table
entry in memory does not change what the TLB remembers; section 5.10.4
lists what does, and the first recommendation of 5.10.4.2 “Recommended
Invalidation” is the rule we follow: “if software modifies a
paging-structure entry that maps a page, it should execute INVLPG for
any linear address with a page number whose translation uses that
paging-structure entry”. fork runs in the parent, with the
parent’s directory in CR3, and the parent has just been
writing to its stack: the TLB holds a writable translation of
0x7FFFF000, and without the invlpg the
parent’s next store would go through, into the frame the child now
shares, and the child would see it. The child needs no invalidation,
because its directory is not in CR3 and the
mov cr3 that will load it flushes the TLB (the MOV to CR3
item of 5.10.4.1). AMD documents the same rules in APM Volume 2, section
5.5.3 “TLB Management” and 6.6.2 “TLB Invalidation”.
Example 15.1. Before fork, the entry
for the parent’s stack page reads 0x126067 (we will see it
in gdb): frame 0x126000 and flags 0x67, which
is 0110 0111: Dirty, Accessed, User, R/W, Present. After
fork the same entry reads 0x126265: the same
frame, flags 0x265 = 0010 0110 0101, which is COW (bit 9),
Dirty, Accessed, User, Present, and R/W clear. The child’s entry is the
same word, 0x126265, in a different table. The dirty bit
survives: the processor set it when the parent wrote the page, and
nothing has cleared it; it tells nobody anything useful here, and a
kernel that swapped pages to disk would care.
15.3.4 The child’s kernel stack
A new task of chapter 13 starts life with a prepared kernel stack:
six words that context_switch pops, ending with a return
into a start function (user_task_start) which then does an
iret into ring 3 at the program’s entry point. A forked
child cannot start at an entry point: it must start where the parent
is, at the instruction after int 0x80, with the
parent’s registers, and with EAX = 0. Everything needed for
that is already on the parent’s kernel stack, in the
struct registers that isr_common saved on the
way in (chapter 13, “The next interrupt”), and it sits at a known place:
the very top of the stack, 76 bytes below
kernel_stack + KERNEL_STACK_SIZE, because the kernel stack
of a task is empty whenever the task runs in ring 3, and the system
call’s frame is the first thing pushed on it. So the child’s stack is
the parent’s frame, copied to the same place, plus the six words of a
context switch arranged so that the first switch to the child “returns”
into the tail of isr_common:
os/isr_stubs.asm (the label)
push esp ; struct registers *regs = current ESP
call isr_dispatch
add esp, 4 ; drop the argument
; Chapter 15: the way out, also the way IN for a forked child. task_fork
; builds the child's kernel stack so that its first context_switch() pops
; this address: ESP then points at a copy of the parent's struct registers
; and the child leaves the kernel exactly as the parent will, through IRET,
; into the instruction after INT 0x80, with EAX = 0.
global isr_return
isr_return:
pop gs
pop fs
pop es
pop ds
popa
add esp, 8 ; drop vector number and error code
iret ; pops EIP, CS, EFLAGS (and ESP, SS if needed)Nothing changed in the code, only a label was added where
isr_dispatch returns. And task_fork:
os/task.c (task_fork)
struct task *task_fork(struct registers *regs)
{
struct task *t;
struct registers *child_regs;
uint32_t *sp;
/* The frame isr_common saved for this system call sits at the very
top of the parent's kernel stack: the stack was empty when the
CPU switched to it on the way from ring 3 (chapter 13). A kernel
thread has no such frame and cannot fork. */
if ((char *)regs + sizeof(*regs)
!= (char *)current_task->kernel_stack + KERNEL_STACK_SIZE)
panic("fork: not called from ring 3");
t = task_new(current_task->name, paging_fork_directory(current_task->page_directory));
t->entry = current_task->entry;
t->user_stack_top = current_task->user_stack_top;
t->bss_start = current_task->bss_start; /* the lazy regions are the same */
t->bss_end = current_task->bss_end;
/* The child's kernel stack gets a copy of that frame at the same
place, with one word changed: the EAX that IRET will hand to the
program. Below it, the six words context_switch() pops, so that
the first switch to the child "returns" into isr_return, the tail
of isr_common, which pops the frame and IRETs into ring 3 at the
instruction after the parent's INT 0x80. The child never runs
syscall_handler at all: it starts life on its way out of it. */
child_regs = (struct registers *)((char *)t->kernel_stack + KERNEL_STACK_SIZE
- sizeof(*regs));
memcpy(child_regs, regs, sizeof(*regs));
child_regs->eax = 0; /* fork() returns 0 in the child */
sp = (uint32_t *)child_regs;
*--sp = (uint32_t)isr_return; /* popped by RET at the end of context_switch */
*--sp = 0; /* EBP */
*--sp = 0; /* EBX */
*--sp = 0; /* ESI */
*--sp = 0; /* EDI */
*--sp = 0x2; /* EFLAGS: IF clear, as inside any handler;
IRET restores the program's own */
t->esp = (uint32_t)sp;
task_link(t);
return t;
}Follow the child’s first moments. Some schedule() picks
it; context_switch loads its esp, pops
EFLAGS = 0x2 and four zeros, and ret pops
isr_return. ESP now points at the copied
frame, and the tail of isr_common does what it does at the
end of every interrupt: restores the segment registers and the general
registers, EAX among them, now 0, discards the vector and
error code, and iret pops EIP = 0x80480a5 (the
instruction after int 0x80 in syscall3),
CS = 0x1b, the program’s EFLAGS, its
ESP and SS. The child is in ring 3, inside
fork()’s wrapper, returning 0, on a stack whose page it
shares with its parent. The parent, meanwhile, returns from
task_fork into syscall_handler, which stores
the child’s id in its saved EAX, and leaves
through the same isr_return. Two returns from one call.
The 0x2 instead of chapter 13’s 0x202 is
deliberate. task_alloc had to enable interrupts in the
popfd, because nothing after it would: the start function
went straight into the program. Here the iret at the end of
isr_return loads the program’s own EFLAGS from
the frame, with IF set, exactly as it does for the parent;
the few instructions between the popfd and the
iret run with interrupts off, which is the state inside any
handler.
task_alloc of chapter 13 has been split for this:
task_new allocates the structure and the kernel stack, sets
the parent to current_task and does not link the
task into the run queue; task_link does that last, because
a task whose stack is not yet prepared must not be visible to the
scheduler. task_alloc is now task_new, the six
words, task_link, and task_fork is
task_new, the copied frame plus the six words,
task_link. The two bss_ lines belong to the
section “Pages on demand”; ignore them until then.
There is one more change forced by fork, which is
invisible in the listings and was found the hard way:
os/task.h (KERNEL_STACK_SIZE)
/* Chapter 15: 16 KiB rather than one page. exec() runs the ext2 reader on
the calling task's kernel stack, and that code keeps a block buffer of
up to 4 KiB in each of several nested functions; on a one-page stack
it silently overwrote the heap block below (the struct task itself).
Linux uses 16 KiB kernel stacks for the same reason, and forbids large
arrays on them. */
#define KERNEL_STACK_SIZE 16384Until this chapter, every disk read happened on kmain’s
stack, the big one at 0x90000. exec reads the
ELF file from inside a system call, on the task’s kernel stack, and
ext2_read_inode and dir_find each keep a
MAX_BLOCK_SIZE buffer on the stack, 4 KiB apiece: the first
exec overflowed its one-page stack into the heap block
below it, which held the struct task, and the kernel’s
first symptom was
Page fault at 0xf000f000: page not present, read, kernel mode
in paging_free_directory, two functions later, reading a
directory entry that had been overwritten. Chapter 16 is about finding
such things; the fix is four times the stack. A kernel stack overflow
does not fault, since the page below is mapped, which is why Linux puts
a guard page under each of its stacks.
15.3.5 The copy-on-write fault
os/paging.c (cow_fault)
uint32_t cow_faults, cow_copies, demand_faults;
/* Chapter 15: a write to a page that fork() shares read-only between two
address spaces. Returns 1 if `cr2` was such a page and the write may
now be retried, 0 if this is an ordinary fault. Two cases: if other
address spaces still use the frame, the writer gets a private copy and
lets go of the shared one; if it is the last user (the others have
exited, or exec'ed, or taken their own copies), the page simply becomes
writable again. Either way the stale read-only translation must leave
the TLB before the instruction is retried (SDM Vol. 3A, section 5.10.4.2
"Recommended Invalidation"). */
static int cow_fault(uint32_t cr2)
{
uint32_t *dir = current_task->page_directory;
uint32_t pde, *pte, frame, copy;
if (cr2 >= USER_STACK_TOP)
return 0; /* not a user page */
pde = dir[PAGE_DIR_INDEX(cr2)];
if (!(pde & PAGE_PRESENT))
return 0;
pte = &((uint32_t *)(pde & PAGE_FRAME))[PAGE_TABLE_INDEX(cr2)];
if ((*pte & (PAGE_PRESENT | PAGE_COW)) != (PAGE_PRESENT | PAGE_COW))
return 0;
frame = *pte & PAGE_FRAME;
cow_faults++;
if (pmm_frame_refcount(frame) > 1) {
copy = pmm_alloc_frame();
if (copy == 0)
panic("copy-on-write: out of frames");
memcpy((void *)copy, (void *)frame, PAGE_SIZE);
kprintf("[task %d: copy-on-write %p: copied (%u users)]\n",
current_task->id, (void *)PAGE_ALIGN_DOWN(cr2),
pmm_frame_refcount(frame));
pmm_free_frame(frame); /* one user fewer */
*pte = copy | ((*pte & 0xFFF & ~PAGE_COW) | PAGE_WRITE);
cow_copies++;
} else {
kprintf("[task %d: copy-on-write %p: made writable (last user)]\n",
current_task->id, (void *)PAGE_ALIGN_DOWN(cr2));
*pte = (*pte & ~PAGE_COW) | PAGE_WRITE;
}
invlpg(cr2);
return 1;
}and the handler of chapter 12 gains one line before it prints anything:
os/paging.c (the start of
page_fault_handler)
asm volatile("mov %%cr2, %0" : "=r"(cr2));
if ((regs->err_code & 3) == 3 && cow_fault(cr2))
return; /* IRET retries the write */Go back to figure 5-12 of the Intel SDM Volume 3A, section 5.7, the
page-fault error code, which chapter 12 introduced and chapter 13 used
to tell a user fault from a kernel one. Bit 0, P, is 1 when the page was
present and the fault is a protection violation; bit 1, W/R, is
1 for a write; bit 2, U/S, is 1 for an access from ring 3. A
copy-on-write fault is P = 1 and W/R = 1, error code 0x3 or
0x7 depending on who wrote. The handler tests those two
bits, and then cow_fault does the page walk of chapter 14’s
paging_lookup by hand, down to the address of the
page-table entry, because it is going to change it: the entry must be
present and carry the COW mark, otherwise this is somebody else’s fault
and the function declines. Then the two cases of the figure. If the
frame has more than one user, allocate a frame, copy the page into it,
drop one user of the old frame, and point the entry at the copy,
writable and no longer COW. If the frame has exactly one user, the
sharing is over: whoever shared it has exited, or called
exec, or already taken its own copy, and the page just
becomes writable again, with no copy at all. In both cases
invlpg throws the read-only translation out of the TLB, the
handler returns, iret resumes the program at the
faulting instruction, and the store that faulted executes a second
time and succeeds. That last property, a fault being transparent to the
program, is why the saved EIP of a fault points at the
instruction and not after it (chapter 11, “Faults, traps and
aborts”).
Example 15.2. The first fault of the run:
CR2 = 0x7fffff04, error code 0x7,
CS = 0x1b, EIP = 0x80480a5, which disassembles
to mov DWORD PTR [ebp-0x8], eax. Error code
111: present, write, user. The instruction is the store of
fork()’s return value into a local variable of
syscall3, the first thing the parent does after the system
call, and it is on the stack page. The frame has two users (the parent
and the child, which has not run yet), so the parent gets the copy and
the child, when it runs and stores its own 0, finds a frame with one
user and gets made writable.
15.3.6 Who writes: CR0.WP
One line in paging_init changed for this mechanism, and
it answers a question the previous paragraph glossed over: what if the
kernel writes to a shared page? The kernel does that in
wait, storing the child’s exit status through the pointer
the parent passed, and the pointer leads to the parent’s stack page,
which may still be shared with a child. Section 5.1.3 “Paging-Mode
Modifiers” of the SDM says it in two sentences: “If CR0.WP = 0,
supervisor-mode write accesses are allowed to linear addresses with
read-only access rights; if CR0.WP = 1, they are not. (User-mode write
accesses are never allowed to linear addresses with read-only access
rights, regardless of the value of CR0.WP.)” Section 5.6 “Access Rights”
defines the supervisor-mode and user-mode accesses the sentence refers
to. The bit is bit 16 of CR0 (section 2.5 “Control
Registers”; AMD APM Volume 2, sections 3.1.1 and 5.6.4 “Write Protect
(CR0.WP) Bit”), and chapter 12 left it clear, as it is after reset. With
it clear, the kernel’s store in wait would go straight into
the shared frame, no fault, and the child would find a number it never
wrote in one of its variables. So the kernel now sets it:
os/paging.c (the end of
paging_init)
asm volatile("mov %0, %%cr3" : : "r"(kernel_directory) : "memory");
asm volatile("mov %%cr0, %0" : "=r"(cr0));
cr0 |= 0x80000000 | 0x00010000; /* PG, WP */
asm volatile("mov %0, %%cr0" : : "r"(cr0) : "memory");With WP set, a kernel write to a COW page faults with
error code 0x3 (present, write, supervisor), the saved
CS is 0x08, the fault handler runs on the same
kernel stack, below the frames of syscall_handler and
task_wait (no stack switch, since the fault came from ring
0), cow_fault takes the same two branches, and
iret retries the kernel’s own mov. This is the
reason the test in page_fault_handler looks only at bits 0
and 1 of the error code and not at bit 2: the U/S bit says who wrote,
and for copy-on-write the answer does not matter. Linux sets
WP for the same reason, and it is also what makes a
kernel’s own code pages, mapped read-only there, safe from the kernel’s
own bugs.
15.3.7 The system call
os/syscall.h (additions)
/* Chapter 15: the Unix process model. */
#define SYS_FORK 7 /* fork(): a copy of the caller; returns the child's id to
the caller and 0 to the child */
#define SYS_EXEC 8 /* exec(const char *path): replace the caller's program by
the executable at path; returns -1 only on failure */
#define SYS_WAIT 9 /* wait(int *status): block until a child exits; returns
its id and stores its exit status, or -1 without children */os/syscall.c (the SYS_FORK case)
case SYS_FORK: {
/* The child is a copy of `regs` too; only its EAX differs. */
struct task *child = task_fork(regs);
kprintf("[task %d: fork() -> task %d]\n", current_task->id, child->id);
regs->eax = child->id;
break;
}The handler hands task_fork the saved registers, which
are both the thing to copy and the place where the parent’s return value
goes, and prints a line for the test log. On the user side, in
user/syscall.h, fork() is
syscall3(SYS_FORK, 0, 0, 0), and the wrapper is worth one
look in the disassembly because its first instruction after the system
call is the one that faults:
$ objdump -d -M intel build/user/init
..... output omitted .....
08048090 <syscall3>:
..... output omitted .....
80480a3: cd 80 int 0x80
80480a5: 89 45 f8 mov DWORD PTR [ebp-0x8],eax
..... output omitted .....
08048113 <fork>:
8048113: 55 push ebp
8048114: 89 e5 mov ebp,esp
8048116: 6a 00 push 0x0
8048118: 6a 00 push 0x0
804811a: 6a 00 push 0x0
804811c: 6a 07 push 0x7
804811e: e8 6d ff ff ff call 8048090 <syscall3>EAX = 7 and int 0x80; the mov
at 0x80480a5 stores whatever came back, 0 or an id, into
the stack, and both processes execute it on a page they share. That
store is why every fork in this chapter costs at least one
page copy: the stack. A program that forked and immediately called
exec without touching its stack would copy nothing, and no
C program does that.
15.4 exec
15.4.1 Copying the path first
exec(path) takes a pointer into the calling program’s
memory, and the first thing exec does with that memory is
destroy it. The order of operations is therefore forced: validate the
pointer, copy the string into kernel memory, then load the new
program and free the old address space. A string is a new kind of
argument for user_range_ok, which wants a length that the
kernel does not know until it has read the string, which is the thing
being checked; the two have to be one loop:
os/syscall.c (user_string_copy)
/* A string has no length until the kernel has read it, and reading it is
what must be checked. So the copy and the check are one loop: before
each byte, make sure its page is the task's (once per page, not once per
byte: a page that was fine for its first byte is fine for the rest). */
int user_string_copy(char *dst, uint32_t src, uint32_t max)
{
uint32_t i;
for (i = 0; i < max; i++) {
if ((i == 0 || ((src + i) & (PAGE_SIZE - 1)) == 0)
&& !user_range_ok(src + i, 1))
return -1;
dst[i] = ((const char *)src)[i];
if (dst[i] == '\0')
return (int)i;
}
return -1; /* no NUL within max bytes */
}max is EXEC_PATH_MAX, 64 bytes, and a
string that is not terminated within it is refused like a bad pointer;
Linux’s strncpy_from_user is this function, with a limit of
4096 for a path. The handler:
os/syscall.c (the SYS_EXEC case)
case SYS_EXEC:
/* EBX = path. The string is copied out of user memory before
anything else happens, because task_exec() destroys the address
space the string lives in. */
if (user_string_copy(path, regs->ebx, sizeof(path)) < 0) {
kprintf("[task %d: exec(%p) rejected]\n", current_task->id, (void *)regs->ebx);
regs->eax = (uint32_t)-1;
break;
}
kprintf("[task %d: exec(\"%s\")]\n", current_task->id, path);
if (task_exec(regs, path) < 0)
regs->eax = (uint32_t)-1; /* the old program goes on, with -1 */
/* On success regs->eip is the new program's entry point: IRET
starts it. There is no return value to set. */
break;path is a local array of syscall_handler,
on the kernel stack, which is mapped in every address space and survives
the switch.
15.4.2 Replacing the address space
Chapter 14’s elf_exec did two things, load a file into a
fresh directory and create a task around it; exec needs the
first without the second, so the function is split into
elf_load(path, &dir, &entry, &bss_start, &bss_end),
which is the old function up to its last line and returns -1 instead of
0 on failure (the last two arguments are for the section “Pages on
demand”; ignore them until then), and a two-line elf_exec
that kmain still uses. Then:
os/task.c (task_exec)
int task_exec(struct registers *regs, const char *path)
{
uint32_t *dir, *old, entry, bss_start, bss_end;
/* Load the new program into a directory of its own first: if the
file is missing or not an executable, the caller keeps its address
space and gets -1, as Unix's execve does. */
if (elf_load(path, &dir, &entry, &bss_start, &bss_end) < 0)
return -1;
map_user_stack(dir);
/* Switch to the new address space, then free the old one. The order
matters: we are running on the kernel stack, which is mapped in
both, but the old directory must not be in CR3 when its frames go
back to the allocator. */
old = current_task->page_directory;
current_task->page_directory = dir;
paging_switch_directory(dir);
paging_free_directory(old);
task_set_name(current_task, path);
current_task->entry = (void (*)(void))entry;
current_task->user_stack_top = USER_STACK_TOP;
current_task->bss_start = bss_start;
current_task->bss_end = bss_end;
/* The system call does not return to the caller: the saved frame is
rewritten so that the IRET at the end of this handler lands in the
new program, at its entry point, on an empty stack, with the
general registers cleared. CS, SS and EFLAGS keep their ring 3
values. */
regs->eip = entry;
regs->user_esp = USER_STACK_TOP;
regs->eax = regs->ebx = regs->ecx = regs->edx = 0;
regs->esi = regs->edi = regs->ebp = 0;
return 0;
}Read it as three steps with a reason for each boundary. First, build
the new address space completely, program and stack, while the
old one is still intact: if the file is missing, elf_load
has allocated nothing and the caller gets -1 with everything as it was,
which is what lets init print
exec("/bin/nothing") returned -1 and carry on. Second,
switch CR3 to the new directory and only then free the old
one; the kernel keeps running through the switch because its own stack
is in the heap, which both directories map identically, and the frames
of the old directory must not be in use when they go back to the
allocator. paging_free_directory drops the old pages’
users, so a page the program still shared with its parent survives with
one user fewer, and the parent’s next write to it will find
made writable. Third, and this is the part that
fork prepared us for: there is no “return” from
exec. The frame that isr_common saved is
edited in place, EIP to the entry point of the new program,
ESP to the top of a fresh stack page, the general registers
to zero, and when syscall_handler returns and
isr_return executes its iret, the processor
lands in _start of the new program. CS,
SS and EFLAGS are left alone: they are the
ring 3 values of chapter 13 and the new program needs the same ones.
The name of the task changes too, which is why name
became an array: /bin/init becomes /bin/hello,
and the [task 2 (/bin/hello) exited with status 0] line of
the transcript is the forked child, under its new name.
15.4.3 What Linux adds
Our exec passes nothing to the new program:
main(void). Linux’s execve(path, argv, envp)
passes an array of argument strings and an array of environment strings,
and it does so by writing them onto the new stack before the
first instruction runs: the strings themselves, then an array of
pointers to them, then argc, laid out as the System V ABI
specifies (“Process Initialization” in the i386 supplement), so that
_start finds argc at [esp] and
argv just above it and can call
main(argc, argv). The kernel copies the strings from the
old address space to kernel memory, exactly as we copy the path, before
switching; exercise 15.1 adds this. Linux also handles #!
scripts (it runs the interpreter named on the first line with the script
as an argument), closes the file descriptors marked close-on-exec,
resets signal handlers, and drops privileges unless the file is set-uid.
None of that changes the three steps above.
15.5 Pages on demand
exec, as the previous section left it, allocates every
page the program could ever touch before the program’s first instruction
runs: map_range walks the whole p_memsz of
each segment, and map_user_stack gives every program its
stack page. For hello that is two pages and the right
answer. For a program that declares a 64 KiB buffer and fills one line
of it, or a stack sized for the deepest recursion it might ever reach,
it is a frame of memory and a memset per page that nobody
will read, zeroed at exec and returned at
exit. Unix stopped doing this in 1979, when 3BSD brought
paging to the VAX, and the way it stopped is the way fork
stopped copying: allocate nothing, and let the page fault say which
pages are actually wanted. That is demand paging, and it rests
on the same property of the processor as copy-on-write: the saved
EIP of a fault points at the faulting instruction (chapter
11, “Faults, traps and aborts”), so the handler can supply the page and
let the instruction run again.
15.5.1 What exec no longer allocates
Two regions of a program are known to contain zeros before its first
instruction, and so can be made out of nothing: the .bss,
which the loader zeroes anyway, and the stack, which is empty. Both are
also described by a range of addresses that the kernel knows without
reading a byte of the program: the tail of a PT_LOAD
segment beyond its p_filesz, and the window below
USER_STACK_TOP. So elf_load keeps allocating
and filling the pages that hold bytes of the file, including the page in
which the file ends and .bss begins, which
map_range zeroes as before, and leaves the pages that would
hold nothing but zeros unallocated, reporting their range instead:
os/elf.c (the loop of elf_load)
/* Allocate the pages that hold bytes of the file, including the
one where the file ends and .bss begins (zeroed by map_range);
leave the pages that would hold only zeros to the page-fault
handler. ld puts .bss at the end of the last segment, so the
last segment with a zero-only tail is the one recorded. */
if (map_range(dir, ph->p_vaddr, ph->p_filesz) < 0) {
kprintf("exec %s: out of memory\n", path);
paging_free_directory(dir);
kfree(file);
return -1;
}
copy_to_dir(dir, ph->p_vaddr, file + ph->p_offset, ph->p_filesz);
if (PAGE_ALIGN_UP(ph->p_vaddr + ph->p_memsz)
> PAGE_ALIGN_UP(ph->p_vaddr + ph->p_filesz)) {
*bss_start = PAGE_ALIGN_UP(ph->p_vaddr + ph->p_filesz);
*bss_end = PAGE_ALIGN_UP(ph->p_vaddr + ph->p_memsz);
kprintf("exec %s: %u pages of .bss at %p left for the fault handler\n",
path, (*bss_end - *bss_start) / PAGE_SIZE, (void *)*bss_start);
}The range travels through the two out-parameters of
elf_load into two new fields of struct task,
next to the stack top that was already there, and the stack grows from
one page to a 256 KiB window of which map_user_stack maps
only the top page:
os/task.h (additions)
/* Chapter 15, "Pages on demand": the pages of the program's .bss,
[bss_start, bss_end), are not allocated by exec() but by the
page-fault handler, each one the first time the program (or the
kernel, on its behalf) touches it. The stack window below
user_stack_top is treated the same way, all but its top page. */
uint32_t bss_start, bss_end;/* The user stack of every user task lives in the USER_STACK_SIZE bytes
below this address in the task's own page directory. Only the top page
is mapped by exec(); the rest is mapped on demand, a page at a time, as
the program's frames reach it (chapter 15, "Pages on demand"). */
#define USER_STACK_TOP 0x80000000
#define USER_STACK_SIZE (256 * 1024)The top page stays eager so that crt0’s first
call has somewhere to push. fork needs no
change: task_fork copies the two fields along with
user_stack_top (the two lines added to its listing above),
and paging_fork_directory already copies a not-present
entry as a zero, so a page that neither process has touched stays
untouched in both, and whichever touches it first gets a zeroed frame of
its own. One function completes the bookkeeping, telling the handler
whether an address lies in one of these lazy regions:
os/task.c (task_lazy_region)
const char *task_lazy_region(const struct task *t, uint32_t virt)
{
if (virt >= t->bss_start && virt < t->bss_end)
return "bss";
if (t->user_stack_top != 0 && virt < t->user_stack_top
&& virt >= t->user_stack_top - USER_STACK_SIZE)
return "stack";
return 0;
}The name it returns is for the kernel’s log line; the test is two
range comparisons, and the user_stack_top != 0 keeps a
kernel thread, which has no user stack, from claiming the 256 KiB below
address 0. The loader’s report for the program of this section, 16 pages
of .bss behind a file that ends 538 bytes into its first
page:
exec /bin/bigbss: segment 0 at 0x08048000, 538 bytes in file, 66084 in memory
exec /bin/bigbss: 16 pages of .bss at 0x08049000 left for the fault handler15.5.2 Three kinds of page fault
As long as every page of a program was present, “page not present” in
the fault handler meant “bug”, and the handler could print and kill. Now
a not-present page may simply not have been asked for yet, and the
handler must tell three situations apart with what the processor hands
it: CR2, the linear address that faulted, and the error
code of figure 5-12 in section 5.7 “Page-Fault Exceptions” of the Intel
SDM Volume 3A (AMD APM Volume 2, section 8.4.2 “Page-Fault Error Code”,
figure 8-3, has the same bits under the same names). Bit 0, P, “is 0 if
there is no translation for the linear address because the P flag was 0
in one of the paging-structure entries used to translate that address”,
and 1 when there is a translation whose access rights forbade the
access; bit 1, W/R, is 1 for a write and, the manual insists, “describes
the access causing the page-fault exception, not the access rights
specified by paging”; bit 2, U/S, is 1 for a user-mode access, with the
same caution, which AMD puts more bluntly: the bit “does not necessarily
indicate the cause of the page fault was a privilege violation”. Bits 3
and 4, a reserved bit set in an entry and an instruction fetch, do not
occur in this kernel. The decision therefore starts with bit 0. If P is
1 the page is there and the access was refused: a write to a page marked
PAGE_COW is the first case, cow_fault, and any
other refusal is an error. If P is 0 the page is not there: an address
inside one of the task’s lazy regions is the second case, and any other
address is an error. The second case is fifteen lines:
os/paging.c (demand_fault)
/* Chapter 15, "Pages on demand": an access to a page that is not present
but lies in one of the current task's lazy regions, the .bss that
exec() did not allocate or the stack below the page it did. Returns 1
with a zeroed frame mapped at the page, so that the access may be
retried, or 0 when the address is not the task's to touch. Who
touched it does not matter: a program's own load or store faults from
ring 3, and the kernel's store of a wait() status into an untouched
page faults from ring 0; both are served here, in the task's directory,
because current_task is the same in both cases. No TLB work is
needed: the CPU never caches a not-present translation (SDM Vol. 3A,
section 5.10.2.3 "Details of TLB Use"). */
static int demand_fault(uint32_t cr2)
{
const char *region = task_lazy_region(current_task, cr2);
uint32_t frame;
if (region == 0)
return 0;
frame = pmm_alloc_frame();
if (frame == 0)
panic("demand paging: out of frames");
memset((void *)frame, 0, PAGE_SIZE); /* .bss must read as zeros */
paging_map_in(current_task->page_directory, PAGE_ALIGN_DOWN(cr2), frame,
PAGE_WRITE | PAGE_USER);
demand_faults++;
kprintf("[task %d: page %p mapped on demand (%s)]\n",
current_task->id, (void *)PAGE_ALIGN_DOWN(cr2), region);
return 1;
}and the handler’s opening becomes two questions instead of one:
os/paging.c (the start of
page_fault_handler)
asm volatile("mov %%cr2, %0" : "=r"(cr2));
if ((regs->err_code & 3) == 3 && cow_fault(cr2))
return; /* IRET retries the write */
if ((regs->err_code & 1) == 0 && demand_fault(cr2))
return; /* IRET retries the access */Note two things demand_fault does not do. It does not
ask who faulted: the first fault of bigbss below is the
program’s own store from ring 3, error code 0x6 (not
present, write, user), and the third is the kernel’s store of a
wait status from ring 0, error code 0x2, and
both map a page in current_task->page_directory, the
directory in CR3 in both cases, since a system call runs
with its caller’s directory. And it does not invlpg: the
TLBs “cache entries only for linear addresses with translations”, says
section 5.10.2.3 “Details of TLB Use” of the SDM, so a page that was not
present has no stale translation to remove, and the retried instruction
walks the tables and finds the new entry. The one luxury it skips is the
zero page: Linux serves a read of an untouched page by
mapping one shared frame of zeros read-only and copy-on-write, so that a
page only ever read costs nothing; ours allocates a frame for a read
too, though the pieces to do better, a reference count and
PAGE_COW, are in place.
15.5.3 A pointer to a page that does not exist yet
One piece of the kernel assumed that a program’s pages are present:
user_range_ok, which refuses a buffer unless every page of
it is present with the User bit, so that the kernel never follows a user
pointer into memory the program could not touch itself.
wait(&status) with status in an untouched
page of .bss, which is what bigbss does, would
now be refused, for memory the program is entitled to. Two fixes are
possible. The kernel could touch the pages before using them, which
duplicates the handler’s work in a second place and has to know about
both regions; or the check can accept an address in a lazy region and
let the kernel’s own access fault the page in, which is what the handler
was written for and costs one condition:
os/syscall.c (the third check of
user_range_ok)
/* 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,
or (chapter 15, "Pages on demand") not present yet but in one of
the task's lazy regions: the program could touch it, so the
kernel may, and its access takes the same fault, and the same
fix, as the program's would have. */
for (page = PAGE_ALIGN_DOWN(ptr); page < end; page += PAGE_SIZE)
if (!paging_user_accessible(current_task->page_directory, page)
&& task_lazy_region(current_task, page) == 0)
return 0;The invariant the check protects is unchanged: the kernel touches
only memory the program could touch, and a page in a lazy region is such
memory, present or not. What the kernel’s access then costs is the fault
the program’s would have cost, served by the same code; the one novelty
is that it is taken in ring 0, in the middle of task_wait,
on the same kernel stack, and CR0.WP plays no part in it,
since a not-present page faults whoever the writer is.
15.5.4 /bin/bigbss
user/bigbss.c
/* bigbss.c -- a program with more memory than it uses.
*
* The array below is 16 pages of .bss; the program writes one byte of it.
* Since chapter 15, "Pages on demand", exec() allocates none of those
* pages: the write faults, the kernel maps one zeroed page, and the rest
* stay unmapped until something touches them. A function with a 12 KiB local buffer does
* the same to the stack, which exec() also no longer maps in full. Then
* the program forks, the child exits with 3, and the parent calls wait()
* with a pointer to another .bss variable that nobody has touched yet:
* this time it is the kernel's own store that takes the fault, from ring
* 0, and the result still arrives.
*/
#include "syscall.h"
static char big[65536]; /* 16 pages, all zeros, all in .bss */
static int child_status; /* .bss too; the kernel's wait() store faults it in */
/* Three pages of stack, one byte written at the far end. */
static char deep(void)
{
char buf[12288];
buf[0] = 'y';
return buf[0];
}
int main(void)
{
char line[40];
int pid, n = 0;
big[40000] = 'x'; /* one byte: one page of the sixteen */
deep();
pid = fork();
if (pid == 0)
exit(3);
wait(&child_status); /* the kernel writes to an untouched page */
while ("bigbss: child exited with status "[n] != '\0') {
line[n] = "bigbss: child exited with status "[n];
n++;
}
line[n++] = '0' + child_status;
line[n++] = '\n';
line[n] = '\0';
write(line);
return big[40000] == 'x' ? 0 : 1;
}init runs it after count, and these are its
lines in the run:
exec /bin/bigbss: segment 0 at 0x08048000, 538 bytes in file, 66084 in memory
exec /bin/bigbss: 16 pages of .bss at 0x08049000 left for the fault handler
[task 4: page 0x08051000 mapped on demand (bss)]
[task 4: page 0x7fffc000 mapped on demand (stack)]
[task 4: fork() -> task 5]
[task 4: copy-on-write 0x7ffff000: copied (2 users)]
[task 5: copy-on-write 0x7ffff000: made writable (last user)]
[task 5 (/bin/bigbss) exited with status 3]
[task 4: page 0x08058000 mapped on demand (bss)]
[task 4: wait() collected task 5, status 3]
bigbss: child exited with status 3Three faults and three frames, for a program whose .bss
and stack window add up to 79 lazy pages; the exec of the
previous section would have allocated and zeroed the sixteen pages of
.bss up front, and could not have run deep at
all on its one-page stack. big starts at
0x08048220, so big[40000] is the byte at
0x08051e60, in the ninth of the sixteen lazy pages, and the
only byte of big the program writes. deep
writes the first byte of its buffer, 12 KiB below the top of the stack,
in the page at 0x7fffc000; the two pages between it and the
top page are skipped over and never allocated either. The
fork shares the touched pages copy-on-write, as the two
lines after it show for the stack, and copies nothing for the untouched
ones. The third fault is the kernel’s: child_status is at
0x08058220, on the last lazy page, and the store in
task_wait is what mapped it, just before the
wait report. The gdb session “Three demand faults in gdb”
takes the three apart. One consequence to keep in mind for exercise
15.5: bss_end is the program break of Unix, the
address a brk system call moves, and raising it is now a
matter of changing a field.
15.6 wait and exit
15.6.1 Zombies
task_exit of chapter 13 marked the task dead and the
idle task’s task_reap freed everything it owned at the next
opportunity. With wait, something must outlive the
task: its exit status, and its id, until the parent asks for them. The
smallest container for both is the struct task itself, so a
dead task now keeps its structure (and, for simplicity, its kernel
stack) until its parent has collected it. Such a task, which has exited
but still has an entry in the process table, is what Unix calls a
zombie, and the Z in a ps listing on
a Linux machine is exactly this state: TASK_DEAD with a
parent that has not called wait yet.
os/task.c (task_exit)
void task_exit(int status)
{
struct task *t;
asm volatile("cli");
current_task->exit_status = status;
current_task->state = TASK_DEAD;
/* Orphans: the children of a task that exits are adopted by idle,
whose reaper frees them when they die (Unix gives them to init). */
for (t = idle_task.next; t != &idle_task; t = t->next)
if (t->parent == current_task)
t->parent = &idle_task;
/* A parent blocked in wait() has something to collect now. */
if (current_task->parent != 0 && current_task->parent->state == TASK_WAITING)
current_task->parent->state = TASK_READY;
schedule();
panic("task_exit: a dead task was scheduled");
}Three things happen before the final schedule(), which
never returns. The status is stored. The task’s own children, if any,
are reparented: a process that exits while its children run
would otherwise leave them with a parent pointer to a structure about to
be freed, so they are handed to the idle task, as Unix hands orphans to
init (or, since Linux 3.4, to a subreaper that a
process may volunteer to be). And if the parent is blocked in
wait, it is made ready, so that schedule() can
pick it. task_exit now takes the status as an argument, and
its three callers pass one: SYS_EXIT passes the program’s,
the page-fault handler passes -1 for a task it kills, and
kernel_thread_start passes 0.
15.6.2 Waiting: a new state
os/task.c (task_wait)
int task_wait(int *status)
{
struct task *t, *child;
int id;
for (;;) {
int children = 0;
child = 0;
for (t = idle_task.next; t != &idle_task; t = t->next) {
if (t->parent != current_task)
continue;
children++;
if (t->state == TASK_DEAD) {
child = t;
break;
}
}
if (children == 0)
return -1; /* nothing to wait for */
if (child != 0)
break;
/* Children, but none has exited: block until task_exit() of one
of them makes us ready again. Not TASK_SLEEPING: nobody should
wake us at a given tick, only a child's exit may. */
current_task->state = TASK_WAITING;
schedule();
}
/* The zombie has nothing left but its struct task: collect the status
and free it. The store through `status` goes to the parent's own
user memory, which may still be a copy-on-write page shared with
another child; CR0.WP makes that write fault and copy, like the
program's own writes. */
if (status != 0)
*status = child->exit_status;
kprintf("[task %d: wait() collected task %d, status %d]\n",
current_task->id, child->id, child->exit_status);
id = child->id;
task_free(child);
return id;
}The loop walks the run queue looking for children of the current
task; the run queue is the process table, there is no other list. With
no children at all, wait returns -1 immediately, as Unix
returns -1 with errno = ECHILD. With a dead child, it
collects. With live children only, it blocks, and the blocking is the
new state. Why TASK_WAITING rather than reusing
TASK_SLEEPING? Because TASK_SLEEPING has a
precise meaning in task_wake_sleepers: “make me ready when
ticks reaches wake_at”, and a waiting parent
has no such tick; a wake_at in the far future would work
and would be a lie that the timer handler checks a hundred times a
second for nothing. A state with a name says what the task waits for,
which is what ps shows and what you want to see in gdb. A
real kernel generalizes both into one blocked state plus a
wait queue per thing that can be waited for (a child, a disk
block, a key press), with the wake-up coming from whoever produces the
thing; our two states are two such queues, both scanned rather than
kept. The scheduler’s loop grows by one case, through a helper:
os/task.c (schedule, the selection)
static int task_runnable(const struct task *t)
{
return t->state == TASK_READY || t->state == TASK_RUNNING;
} next = prev->next;
while (!task_runnable(next))
next = next->next; /* idle never sleeps, waits or dies, so this ends */task_wait runs inside the system call handler, with
interrupts disabled by the interrupt gate, which is what makes the walk
over the run queue safe, as chapter 13’s section on critical sections
required; schedule() switches away with them disabled and
they are disabled again when the task is switched back, so the second
walk is safe too. The collection at the end is the one place where the
kernel writes to user memory in this book, and the comment says why that
write is allowed to fault now.
task_free is the unlinking and freeing that
task_reap used to do inline, made a function because
wait does it too: the task leaves the run queue, its page
directory is freed (which drops a user of every page it still shared),
then its kernel stack and its structure.
15.6.3 What the idle task’s reaper does now
os/task.c (task_reap)
int task_reap(void)
{
uint32_t flags = irq_save();
struct task *t = idle_task.next;
int alive = 0;
while (t != &idle_task) {
struct task *next = t->next;
/* Only idle's own children: anybody else's zombie belongs to a
parent that will wait() for it. */
if (t->state == TASK_DEAD && t->parent == &idle_task)
task_free(t);
else
alive++;
t = next;
}
irq_restore(flags);
return alive;
}Chapter 13’s reaper freed every dead task; now it frees only the dead
tasks whose parent is the idle task, which is init when it
exits, and any orphan. A zombie whose parent is alive is left for that
parent’s wait, and counted as alive, so that
kmain’s loop does not finish while a status is still
waiting to be collected. This is the division of labor of Unix: a parent
reaps its children, init reaps the orphans.
15.6.4 The system call
os/syscall.c (the SYS_WAIT case)
case SYS_WAIT:
/* EBX = int *status, or 0. Validated before we block: a bad
pointer is refused at once, not after the child has exited. */
if (regs->ebx != 0 && !user_range_ok(regs->ebx, sizeof(int))) {
kprintf("[task %d: wait(%p) rejected]\n", current_task->id, (void *)regs->ebx);
regs->eax = (uint32_t)-1;
break;
}
regs->eax = (uint32_t)task_wait((int *)regs->ebx);
break;The pointer is checked before blocking, with
user_range_ok of chapter 13, four bytes; a null pointer
means the caller does not want the status. Note what the check does
not guarantee: that the page is writable, or even that it is
present. It is not writable if it is a COW page, and it is not present
if it is a page of .bss or of the stack that the program
has never touched (the previous section), and both are fine, because
CR0.WP, cow_fault and
demand_fault make the kernel’s store behave exactly like
the program’s. The user side, in user/syscall.h:
user/syscall.h (additions)
#define SYS_FORK 7 /* chapter 15 */
#define SYS_EXEC 8
#define SYS_WAIT 9/* Chapter 15: the Unix process model, without arguments or environment.
fork() returns twice: the child's id in the parent, 0 in the child.
exec() returns only when it failed (-1); otherwise the calling program
is gone and `path` runs in its place. wait() blocks until a child has
exited and returns its id, storing its exit status through `status`
when that is not 0; it returns -1 when there is no child to wait for. */
static inline int fork(void)
{
return syscall3(SYS_FORK, 0, 0, 0);
}
static inline int exec(const char *path)
{
return syscall3(SYS_EXEC, (int)path, 0, 0);
}
static inline int wait(int *status)
{
return syscall3(SYS_WAIT, (int)status, 0, 0);
}15.7 The first program:
/bin/init
user/init.c
/* init.c -- the first program, and the only one the kernel starts.
*
* Like init on Unix, it starts every other program with the pair
* fork() + exec(), waits for each child and reports its exit status.
* Its last child does not exec anything: it writes a variable that it
* shares with its parent, to show that the sharing is copy-on-write.
*/
#include "syscall.h"
/* A global, so that it lives in the program's page (code and data share
one page in our small executables) rather than on the stack: the
child's write to it is the only write to that page, and the only
reason it gets copied. */
int shared = 42;The file continues with append and
append_number, the two line-building helpers of chapter
13’s userprog.c copied verbatim, since a program on the
disk has no library to get them from; then run, quoted at
the start of the chapter, which forks, execs in the child,
waits in the parent and prints
init: child N exited with status S; and
main:
int main(void)
{
char line[80];
int pid, status = -1, n;
n = append(line, 0, "init: pid ");
n = append_number(line, n, getpid());
line[n++] = '\n';
line[n] = '\0';
write(line);
run("/bin/hello");
run("/bin/count");
run("/bin/bigbss");
/* Copy-on-write: the child changes `shared`; the parent reads it
after the child has exited and still sees 42. */
write("init: forking a child that writes the shared variable\n");
pid = fork();
if (pid == 0) {
shared = 99;
n = append(line, 0, "child: shared = ");
n = append_number(line, n, shared);
line[n++] = '\n';
line[n] = '\0';
write(line);
exit(7);
}
pid = wait(&status);
n = append(line, 0, "init: child ");
n = append_number(line, n, pid);
n = append(line, n, " exited with status ");
n = append_number(line, n, status);
n = append(line, n, "; init: shared = ");
n = append_number(line, n, shared);
line[n++] = '\n';
line[n] = '\0';
write(line);
/* An exec that fails leaves the program as it was. */
n = append(line, 0, "init: exec(\"/bin/nothing\") returned ");
n = append_number(line, n, exec("/bin/nothing"));
line[n++] = '\n';
line[n] = '\0';
write(line);
/* And a wait with nothing to wait for. */
n = append(line, 0, "init: wait() with no children returned ");
n = append_number(line, n, wait(&status));
line[n++] = '\n';
line[n] = '\0';
write(line);
return 0;
}The last child is the demonstration. It does not exec;
it writes 99 into shared, prints it, and exits with status
7, a value chosen to be visibly not 0. The parent, after
wait, prints shared and gets 42: the child’s
write went into the child’s private copy of the page, which died with
the child. If fork had shared the page without the
copy-on-write arrangement, both would have seen 99; if it had copied
every page eagerly, the result would be the same 42 at a higher price,
and the pages copied count at the end would be 12 instead
of 6: two pages for each of init’s four forks and four for
the fork inside bigbss. The variable is a global on
purpose, as its comment says: the stack page is copied anyway, by the
store of fork’s return value, so a stack variable would
prove nothing.
kmain loses the two elf_exec calls of
chapter 14 and the directory listings, and gains one line:
os/kernel.c (the end of kmain)
/* 3. The kernel starts exactly one program. Everything else that
runs is forked and exec'ed by a program, as on Unix, where the
kernel starts init and init starts the rest. */
kprintf("%u frames free before starting init\n", pmm_free_frames_count());
if (elf_exec("/bin/init") == 0)
panic("no /bin/init");
/* 4. kmain is the idle task again: it reaps its own children (init,
and any orphan) until nothing is left. */
for (;;) {
if (task_reap() == 0)
break;
asm volatile("hlt");
}
kprintf("all processes finished, %u frames free, %u copy-on-write faults, %u pages copied, %u pages mapped on demand\n",
pmm_free_frames_count(), cow_faults, cow_copies, demand_faults);The user/Makefile builds init like the
other programs, and the bootdisk rule copies it to
/bin; debugfs shows it as inode 16, 5464
bytes, of which 1792 are the single LOAD segment:
$ readelf -l build/user/init
..... output omitted .....
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
LOAD 0x000000 0x08048000 0x08048000 0x00700 0x00700 RWE 0x1000
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x10The segment is RWE where hello’s was
R E: init has a .data section,
four bytes, shared, and with our linker script it lands in
the same page as the code, 0x080486fc. One page of program,
one page of stack: that is the whole address space fork has
to copy, and the counts at the end of the run are small enough to check
by hand.
15.8 Building, testing and debugging
15.8.1 make test
$ make test
..... build output omitted .....
serial-test: ok, found "init: child 2 exited with status 0" and "init: child 3 exited with status 0" and "init: child 4 exited with status 0" and "bigbss: child exited with status 3" and "init: shared = 42" and "boot 1 of this disk image" and "all processes finished"
--- serial output ---
Hello World from the kernel!
CPU: GenuineIntel, QEMU Virtual CPU version 2.5+ (family 6, model 6, stepping 3)
ata: primary master "QEMU HARDDISK", 16384 sectors (8192 KiB)
ext2: volume "os01", block size 1024, 1792 inodes, 7168 blocks, revision 1
ext2: wrote 45 bytes to /log.txt
/log.txt (45 bytes):
boot 1 of this disk image, written at tick 2
32447 frames free before starting init
exec /bin/init: segment 0 at 0x08048000, 1792 bytes in file, 1792 in memory
init: pid 1
init: forking for /bin/hello
[task 1: fork() -> task 2]
[task 1: copy-on-write 0x7ffff000: copied (2 users)]
[task 2: copy-on-write 0x7ffff000: made writable (last user)]
[task 2: exec("/bin/hello")]
exec /bin/hello: segment 0 at 0x08048000, 343 bytes in file, 343 in memory
Hello from user space, pid 2
[task 2 (/bin/hello) exited with status 0]
[task 1: wait() collected task 2, status 0]
init: child 2 exited with status 0
init: forking for /bin/count
[task 1: fork() -> task 3]
[task 1: copy-on-write 0x7ffff000: copied (2 users)]
[task 3: copy-on-write 0x7ffff000: made writable (last user)]
[task 3: exec("/bin/count")]
exec /bin/count: segment 0 at 0x08048000, 331 bytes in file, 331 in memory
count: 1
count: 2
count: 3
count: 4
count: 5
[task 3 (/bin/count) exited with status 0]
[task 1: wait() collected task 3, status 0]
init: child 3 exited with status 0
init: forking for /bin/bigbss
[task 1: fork() -> task 4]
[task 1: copy-on-write 0x7ffff000: copied (2 users)]
[task 4: copy-on-write 0x7ffff000: made writable (last user)]
[task 4: exec("/bin/bigbss")]
exec /bin/bigbss: segment 0 at 0x08048000, 538 bytes in file, 66084 in memory
exec /bin/bigbss: 16 pages of .bss at 0x08049000 left for the fault handler
[task 4: page 0x08051000 mapped on demand (bss)]
[task 4: page 0x7fffc000 mapped on demand (stack)]
[task 4: fork() -> task 5]
[task 4: copy-on-write 0x7ffff000: copied (2 users)]
[task 5: copy-on-write 0x7ffff000: made writable (last user)]
[task 5 (/bin/bigbss) exited with status 3]
[task 4: page 0x08058000 mapped on demand (bss)]
[task 4: wait() collected task 5, status 3]
bigbss: child exited with status 3
[task 4 (/bin/bigbss) exited with status 0]
[task 1: wait() collected task 4, status 0]
init: child 4 exited with status 0
init: forking a child that writes the shared variable
[task 1: fork() -> task 6]
[task 1: copy-on-write 0x7ffff000: copied (2 users)]
[task 6: copy-on-write 0x7ffff000: made writable (last user)]
[task 6: copy-on-write 0x08048000: copied (2 users)]
child: shared = 99
[task 6 (/bin/init) exited with status 7]
[task 1: wait() collected task 6, status 7]
init: child 6 exited with status 7; init: shared = 42
[task 1: exec("/bin/nothing")]
exec /bin/nothing: no such file
init: exec("/bin/nothing") returned -1
init: wait() with no children returned -1
[task 1 (/bin/init) exited with status 0]
all processes finished, 32430 frames free, 11 copy-on-write faults, 6 pages copied, 3 pages mapped on demand
qemu-system-i386: terminating on signal 15 from pid 170 (/bin/sh)
dd if=build/disk.img of=build/fs.img bs=512 skip=2048 status=none
e2fsck -fn build/fs.img
e2fsck 1.47.2 (1-Jan-2025)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
os01: 19/1792 files (0.0% non-contiguous), 514/7168 blocks
debugfs -R "cat /log.txt" build/fs.img
debugfs 1.47.2 (1-Jan-2025)
boot 1 of this disk image, written at tick 2Read the bracketed kernel lines against the sections above. Each
fork is followed by exactly two copy-on-write faults on the
stack page, in the same order every time: the parent faults first,
because it returns from the system call first and stores the child’s id,
and finds two users, so it takes the copy; the child runs later, stores
its 0, finds itself the last user of the original frame, and gets it
back writable. Then the child execs, under its old name,
and exits under its new one; the parent’s wait collects the
status and init prints it. The last of init’s
forks adds one more fault, task 6’s write to shared at
0x08048000, which copies the program page; the parent never
writes that page, so the parent’s entry stays read-only to the end and
nobody notices. In between, bigbss forks once itself and
adds the three mapped on demand lines of the section “Pages
on demand”. Eleven faults, six copies, five forks: every fork copied the
stack once, and one copied a second page. Compare with an eager
fork, which would have copied two pages at each of
init’s four forks and four at bigbss’s.
Example 15.3. The frame count.
32447 frames free before starting init, 32430
at the end: seventeen frames did not come back, and as in chapters 13
and 14 they are heap pages, which the heap keeps once it has grown into
them; the kernel stacks are 16 KiB now, so a task costs the heap four or
five pages, the heap reuses the block of a freed child for the next one,
and it grew once more than in a run without bigbss, whose
fork is the only moment three tasks besides idle exist at once.
Everything the six processes owned outright, directories, page tables,
program pages, stack pages, the copies made on write and the pages
mapped on demand, came back through task_free. The debugger
session below counts five of them being returned by a single
wait.
15.8.2 A fork, two faults and an exec in gdb
Start make qemu in one terminal and
make gdb in another; the .gdbinit stops at
kmain. The first system call of interest is the fork:
(gdb) b task_fork
Breakpoint 2 at 0x15600: file task.c, line 206.
(gdb) c
Breakpoint 2, task_fork (regs=0xc0006fc4) at task.c:206
206 if ((char *)regs + sizeof(*regs)
(gdb) p current_task->name
$1 = "/bin/init", '\000' <repeats 22 times>
(gdb) p current_task->id
$2 = 1
(gdb) p/x regs->eax
$3 = 0x7
(gdb) p/x regs->eip
$4 = 0x80480a5
(gdb) p/x regs->user_esp
$5 = 0x7ffffef8
(gdb) set $pt = (uint32_t *)(current_task->page_directory[0x1ff] & 0xfffff000)
(gdb) p/x $pt[0x3ff]
$6 = 0x126067
(gdb) set $frame = $pt[0x3ff] & 0xfffff000
(gdb) p (int)'pmm.c'::refcount[$frame >> 12]
$7 = 1
(gdb) p 'pmm.c'::frames_free
$8 = 32435init, task 1, in a system call with
EAX = 7, SYS_FORK; regs is at
0xc0006fc4, 76 bytes below the top of its kernel stack at
0xc0007010, as task_fork’s first test
requires. $pt is the page table of directory entry
0x1ff, the stack’s, and its last entry maps
0x7FFFF000 to frame 0x126000 with flags
0x67, as example 15.1 decoded; the frame has one user. Let
the function run:
(gdb) finish
0x00015019 in syscall_handler (regs=0xc0006fc4) at syscall.c:117
117 struct task *child = task_fork(regs);
Value returned is $9 = (struct task *) 0xc0000078
(gdb) set $child = $
(gdb) p $child->id
$10 = 2
(gdb) p $child->name
$11 = "/bin/init", '\000' <repeats 22 times>
(gdb) p $child->parent->id
$12 = 1
(gdb) p/x $child->esp
$13 = 0xc000bfac
(gdb) x/6xw $child->esp
0xc000bfac: 0x00000002 0x00000000 0x00000000 0x00000000
0xc000bfbc: 0x00000000 0x000102a9
(gdb) info symbol *(uint32_t *)($child->esp + 20)
isr_return in section .text
(gdb) p/x *(struct registers *)($child->esp + 24)
$14 = {gs = 0x23, fs = 0x23, es = 0x23, ds = 0x23, edi = 0x0, esi = 0x0, ebp = 0x7fffff0c, esp_dummy = 0xc0006ff4, ebx = 0x0, edx = 0x0, ecx = 0x0, eax = 0x0, int_no = 0x80, err_code = 0x0, eip = 0x80480a5, cs = 0x1b, eflags = 0x202, user_esp = 0x7ffffef8, ss = 0x23}
(gdb) p/x regs->eax
$15 = 0x7Task 2 exists, named like its parent, with parent 1. Its
esp points at the six prepared words:
EFLAGS = 0x2, four zeros, and 0x102a9, which
is isr_return; right above them, at
$child->esp + 24, the copied frame, identical to the
parent’s except for eax = 0: the same EIP
after the int 0x80, the same user ESP, the
same EBP into the shared stack page. The parent’s own saved
EAX is still 7, since syscall_handler has not
stored the child’s id yet. Now the page tables:
(gdb) p/x $pt[0x3ff]
$16 = 0x126265
(gdb) set $cpt = (uint32_t *)($child->page_directory[0x1ff] & 0xfffff000)
(gdb) p/x $cpt[0x3ff]
$17 = 0x126265
(gdb) p (int)'pmm.c'::refcount[$frame >> 12]
$18 = 2
(gdb) p/x current_task->page_directory[0x20]
$19 = 0x125027
(gdb) p/x $child->page_directory[0x20]
$20 = 0x12e027
(gdb) p/x ((uint32_t *)(current_task->page_directory[0x20] & 0xfffff000))[0x48]
$21 = 0x124225
(gdb) p/x ((uint32_t *)($child->page_directory[0x20] & 0xfffff000))[0x48]
$22 = 0x124225
(gdb) p/x current_task->page_directory[0x300]
$23 = 0x120023
(gdb) p/x $child->page_directory[0x300]
$24 = 0x120023
(gdb) p 'pmm.c'::frames_free
$25 = 32427
(gdb) monitor info mem
0000000000000000-0000000007fe0000 0000000007fe0000 -rw
0000000008048000-0000000008049000 0000000000001000 ur-
000000007ffff000-0000000080000000 0000000000001000 ur-
00000000c0000000-00000000c000d000 000000000000d000 -rwThe parent’s stack entry has become 0x126265 (R/W clear,
COW set), the child’s table, a different frame, holds the same word, and
frame 0x126000 has two users. The program’s directory
entries differ (0x125000 and 0x12e000 are two
page tables) but the page they describe is one frame,
0x124000, flagged 0x225: COW, Accessed, User,
Present, and not Dirty, since nobody has written to the program’s page.
Entry 0x300, the heap, is the same table in both
directories, shared with the kernel. The fork cost eight frames: the
directory, two page tables, and the heap pages of the child’s kernel
stack. QEMU’s info mem summarizes the parent’s address
space as the processor sees it, and both user ranges are
ur-: user, readable, not writable. Now the first write:
(gdb) b paging.c:114
Breakpoint 3 at 0x13655: file paging.c, line 114.
(gdb) c
Breakpoint 3, cow_fault (cr2=2147483396) at paging.c:114
114 if (pmm_frame_refcount(frame) > 1) {
(gdb) p current_task->id
$26 = 1
(gdb) p/x cr2
$27 = 0x7fffff04
(gdb) p/x frame
$28 = 0x126000
(gdb) frame 1
#1 0x0001382e in page_fault_handler (regs=0xc0006fc4) at paging.c:188
188 if ((regs->err_code & 3) == 3 && cow_fault(cr2))
(gdb) p/x regs->err_code
$29 = 0x7
(gdb) p/x regs->cs
$30 = 0x1b
(gdb) x/i regs->eip
0x80480a5: mov DWORD PTR [ebp-0x8],eax
(gdb) frame 0
#0 cow_fault (cr2=2147483396) at paging.c:114
114 if (pmm_frame_refcount(frame) > 1) {
(gdb) p (int)'pmm.c'::refcount[frame >> 12]
$31 = 2Example 15.2 in the debugger: task 1, the parent, at the store after
int 0x80, error code 7, two users. The fault handler’s
regs is at 0xc0006fc4, the same place the
system call’s frame was: the kernel stack was empty again when the fault
came. finish lets the copy happen:
(gdb) finish
0x0001382e in page_fault_handler (regs=0xc0006fc4) at paging.c:188
188 if ((regs->err_code & 3) == 3 && cow_fault(cr2))
Value returned is $32 = 1
(gdb) p (int)'pmm.c'::refcount[$frame >> 12]
$33 = 1
(gdb) p/x $pt[0x3ff]
$34 = 0x135067
(gdb) p 'paging.c'::cow_faults
$35 = 1
(gdb) p 'paging.c'::cow_copies
$36 = 1
(gdb) monitor info mem
0000000000000000-0000000007fe0000 0000000007fe0000 -rw
0000000008048000-0000000008049000 0000000000001000 ur-
000000007ffff000-0000000080000000 0000000000001000 urw
00000000c0000000-00000000c000d000 000000000000d000 -rwFrame 0x126000 is down to one user, the child; the
parent’s entry now reads 0x135067: a new frame,
0x135000, with the original flags 0x67 back,
writable and no longer COW. info mem shows the stack range
as urw again, and the program range still ur-.
The second fault is the child’s:
(gdb) c
Breakpoint 3, cow_fault (cr2=2147483396) at paging.c:114
114 if (pmm_frame_refcount(frame) > 1) {
(gdb) p current_task->id
$37 = 2
(gdb) p/x cr2
$38 = 0x7fffff04
(gdb) frame 1
#1 0x0001382e in page_fault_handler (regs=0xc000bfc4) at paging.c:188
188 if ((regs->err_code & 3) == 3 && cow_fault(cr2))
(gdb) p/x regs->err_code
$39 = 0x7
(gdb) frame 0
#0 cow_fault (cr2=2147483396) at paging.c:114
114 if (pmm_frame_refcount(frame) > 1) {
(gdb) p (int)'pmm.c'::refcount[frame >> 12]
$40 = 1
(gdb) finish
0x0001382e in page_fault_handler (regs=0xc000bfc4) at paging.c:188
188 if ((regs->err_code & 3) == 3 && cow_fault(cr2))
Value returned is $41 = 1
(gdb) p/x $cpt[0x3ff]
$42 = 0x126067
(gdb) p (int)'pmm.c'::refcount[$frame >> 12]
$43 = 1
(gdb) p 'paging.c'::cow_copies
$44 = 1Same address, same instruction, same error code, but task 2 and
regs on its kernel stack, at
0xc000bfc4; the frame has one user, so no copy: the child’s
entry goes back to 0x126067, the word the parent had before
the fork, and cow_copies stays at 1. Then the
exec:
(gdb) delete
(gdb) b task_exec
Breakpoint 4 at 0x1572b: file task.c, line 249.
(gdb) c
Breakpoint 4, task_exec (regs=0xc000bfc4, path=0xc000bf38 "/bin/hello") at task.c:249
249 if (elf_load(path, &dir, &entry, &bss_start, &bss_end) < 0)
(gdb) p current_task->id
$45 = 2
(gdb) p/x regs->eip
$46 = 0x80480a5
(gdb) p/x regs->user_esp
$47 = 0x7ffffef4
(gdb) p/x $cr3
$48 = 0x12d000
(gdb) p current_task->name
$49 = "/bin/init", '\000' <repeats 22 times>
(gdb) p 'pmm.c'::frames_free
$50 = 32426
(gdb) finish
0x000150c6 in syscall_handler (regs=0xc000bfc4) at syscall.c:133
133 if (task_exec(regs, path) < 0)
Value returned is $51 = 0
(gdb) p/x regs->eip
$52 = 0x8048080
(gdb) p/x regs->user_esp
$53 = 0x80000000
(gdb) p/x regs->eax
$54 = 0x0
(gdb) p/x $cr3
$55 = 0x136000
(gdb) p current_task->name
$56 = "/bin/hello", '\000' <repeats 21 times>
(gdb) p 'pmm.c'::frames_free
$57 = 32425
(gdb) monitor info mem
0000000000000000-0000000007fe0000 0000000007fe0000 -rw
0000000008048000-0000000008049000 0000000000001000 urw
000000007ffff000-0000000080000000 0000000000001000 urw
00000000c0000000-00000000c000d000 000000000000d000 -rwpath lives on the kernel stack (0xc000bf38,
in syscall_handler’s frame), as it must. Before: the saved
EIP is still the instruction after int 0x80 in
init, CR3 is the forked directory
0x12d000, the task is /bin/init. After:
EIP = 0x8048080, which is _start of
hello (the entry point in chapter 14’s
readelf -l), ESP at the top of a fresh stack
page, EAX zero, CR3 a new directory, the task
renamed, and the address space is two fresh pages, both
urw: hello has no .bss, so
nothing was left for the fault handler, and the stack window shows only
its top page. The frame count moved by one: the new address space cost
five frames and freeing the old one returned four, because the program
page was still shared with the parent and only lost a user.
15.8.3 A wait and an exit in gdb
A second session, from a fresh make qemu, for the other
half. The parent calls wait right after the fork, long
before the child has execed:
(gdb) b task_wait
Breakpoint 2 at 0x1584a: file task.c, line 286.
(gdb) c
Breakpoint 2, task_wait (status=0x7fffff30) at task.c:286
286 int children = 0;
(gdb) p current_task->id
$1 = 1
(gdb) b task.c:306
Breakpoint 3 at 0x158ba: file task.c, line 306.
(gdb) c
Breakpoint 3, task_wait (status=0x7fffff30) at task.c:306
306 schedule();
(gdb) p current_task->state
$2 = TASK_WAITING
(gdb) p children
$3 = 1One child, none dead: init is about to switch away as
TASK_WAITING. The next event in its life is the child’s
exit, which takes place on the child’s kernel stack, under its new
name:
(gdb) delete
(gdb) b task_exit
Breakpoint 4 at 0x15ad2: file task.c, line 398.
(gdb) c
Breakpoint 4, task_exit (status=0) at task.c:398
398 asm volatile("cli");
(gdb) p current_task->id
$4 = 2
(gdb) p current_task->name
$5 = "/bin/hello", '\000' <repeats 21 times>
(gdb) p current_task->parent->name
$6 = "/bin/init", '\000' <repeats 22 times>
(gdb) p current_task->parent->state
$7 = TASK_WAITING
(gdb) b task.c:412
Breakpoint 5 at 0x15b4a: file task.c, line 412.
(gdb) c
Breakpoint 5, task_exit (status=0) at task.c:412
412 schedule();
(gdb) p current_task->state
$8 = TASK_DEAD
(gdb) p current_task->exit_status
$9 = 0
(gdb) p current_task->parent->state
$10 = TASK_READYBetween line 398 and line 412, the child became a zombie with status
0 and its parent became ready. The schedule() at line 412
goes to the idle task, which finds a dead task that is not its own child
and leaves it alone; at the next time slice init runs
again, back in task_wait’s loop:
(gdb) delete
(gdb) b task.c:315
Breakpoint 6 at 0x158c8: file task.c, line 315.
(gdb) c
Breakpoint 6, task_wait (status=0x7fffff30) at task.c:315
315 *status = child->exit_status;
(gdb) p current_task->id
$11 = 1
(gdb) p child->id
$12 = 2
(gdb) p child->state
$13 = TASK_DEAD
(gdb) p child->exit_status
$14 = 0
(gdb) p 'pmm.c'::frames_free
$15 = 32425
(gdb) finish
0x0001513e in syscall_handler (regs=0xc0006fc4) at syscall.c:146
146 regs->eax = (uint32_t)task_wait((int *)regs->ebx);
Value returned is $16 = 2
(gdb) p 'pmm.c'::frames_free
$17 = 32430The store at line 315 writes 0 into 0x7fffff30, the
status variable in run()’s frame on
init’s stack, a page init has already copied,
so no fault this time; then task_free returns five frames,
the directory, two page tables, a program page and a stack page of
/bin/hello, and wait returns 2. Finally the
end of the run:
(gdb) delete
(gdb) b kernel.c:138
Breakpoint 7 at 0x13330: file kernel.c, line 138.
(gdb) c
Breakpoint 7, kmain () at kernel.c:138
138 kprintf("all processes finished, %u frames free, %u copy-on-write faults, %u pages copied, %u pages mapped on demand\n",
(gdb) p 'paging.c'::cow_faults
$18 = 11
(gdb) p 'paging.c'::cow_copies
$19 = 6
(gdb) p 'paging.c'::demand_faults
$20 = 3
(gdb) p 'pmm.c'::frames_free
$21 = 3243015.8.4 Three demand faults in gdb
A third session, from a fresh make qemu, for the section
“Pages on demand”. Line 152 of paging.c is the
pmm_alloc_frame() in demand_fault, after the
region test, so a breakpoint there stops only for faults the handler is
about to serve:
(gdb) b paging.c:152
Breakpoint 2 at 0x1377d: file paging.c, line 152.
(gdb) c
Breakpoint 2, demand_fault (cr2=134553184) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) p current_task->id
$1 = 4
(gdb) p current_task->name
$2 = "/bin/bigbss", '\000' <repeats 20 times>
(gdb) p/x cr2
$3 = 0x8051e60
(gdb) p/x current_task->bss_start
$4 = 0x8049000
(gdb) p/x current_task->bss_end
$5 = 0x8059000
(gdb) p region
$6 = 0x16dc5 "bss"
(gdb) frame 1
#1 0x00013851 in page_fault_handler (regs=0xc000afd4) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
(gdb) p/x regs->err_code
$7 = 0x6
(gdb) p/x regs->cs
$8 = 0x1b
(gdb) x/i regs->eip
0x8048150: mov BYTE PTR ds:0x8051e60,0x78
(gdb) frame 0
#0 demand_fault (cr2=134553184) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) set $pt = (uint32_t *)(current_task->page_directory[0x20] & 0xfffff000)
(gdb) p/x $pt[0x51]
$9 = 0x0
(gdb) p 'pmm.c'::frames_free
$10 = 32425
(gdb) monitor info mem
0000000000000000-0000000007fe0000 0000000007fe0000 -rw
0000000008048000-0000000008049000 0000000000001000 urw
000000007ffff000-0000000080000000 0000000000001000 urw
00000000c0000000-00000000c000d000 000000000000d000 -rwTask 4, /bin/bigbss, faulted at 0x8051e60,
which is big[40000], inside its .bss range
0x8049000 to 0x8059000; the error code is
0x6: not present, write, user, and CS = 0x1b
confirms ring 3. The instruction is the store of 'x'
(0x78) in main. Entry 0x51 of the
program’s page table is a zero, not a cleared entry: it was never
written. info mem shows the program as one page and the
stack as one page, 32425 frames free. Let the handler work:
(gdb) finish
0x00013851 in page_fault_handler (regs=0xc000afd4) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
Value returned is $11 = 1
(gdb) p/x $pt[0x51]
$12 = 0x126007
(gdb) p 'pmm.c'::frames_free
$13 = 32424
(gdb) monitor info mem
0000000000000000-0000000007fe0000 0000000007fe0000 -rw
0000000008048000-0000000008049000 0000000000001000 urw
0000000008051000-0000000008052000 0000000000001000 urw
000000007ffff000-0000000080000000 0000000000001000 urw
00000000c0000000-00000000c000d000 000000000000d000 -rwOne frame fewer, and entry 0x51 reads
0x126007: frame 0x126000, which was
init’s stack page at the start of the first session, long
since freed and reused, with flags 0x7, User, R/W, Present,
and neither Accessed nor Dirty yet, since the instruction has not been
retried. info mem now has a second program range of one
page, with 32 KiB of nothing between the two; the pages in between do
not exist. The second fault is the stack’s:
(gdb) c
Breakpoint 2, demand_fault (cr2=2147471296) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) p/x cr2
$14 = 0x7fffcfc0
(gdb) p region
$15 = 0x16dc9 "stack"
(gdb) frame 1
#1 0x00013851 in page_fault_handler (regs=0xc000afd4) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
(gdb) p/x regs->err_code
$16 = 0x6
(gdb) p/x regs->user_esp
$17 = 0x7fffcfc0
(gdb) x/i regs->eip
0x8048133: mov BYTE PTR [ebp-0x3000],0x79
(gdb) frame 0
#0 demand_fault (cr2=2147471296) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) finish
0x00013851 in page_fault_handler (regs=0xc000afd4) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
Value returned is $18 = 1
(gdb) p/x ((uint32_t *)(current_task->page_directory[0x1ff] & 0xfffff000))[0x3fc]
$19 = 0x12d007
(gdb) p/x ((uint32_t *)(current_task->page_directory[0x1ff] & 0xfffff000))[0x3fd]
$20 = 0x0CR2 equals the saved user ESP: the faulting
store is deep’s buf[0] = 'y', and
buf is the bottom of its frame, 12 KiB below
main’s. The region is now stack, the error
code is the same 0x6, and afterwards entry
0x3fc of the stack’s page table is a fresh frame while
entry 0x3fd, the page just above it, is still zero: the
stack has a hole in it, which nothing will ever notice. Then
bigbss forks, and the fork is worth one look because it is
the first one of a process with lazy pages:
(gdb) b task_fork if current_task->id == 4
Breakpoint 3 at 0x15600: file task.c, line 206.
(gdb) c
Breakpoint 3, task_fork (regs=0xc000afd4) at task.c:206
206 if ((char *)regs + sizeof(*regs)
(gdb) finish
0x00015019 in syscall_handler (regs=0xc000afd4) at syscall.c:117
117 struct task *child = task_fork(regs);
Value returned is $21 = (struct task *) 0xc00000e0
(gdb) set $child = $
(gdb) p/x $child->bss_start
$22 = 0x8049000
(gdb) p/x $child->bss_end
$23 = 0x8059000
(gdb) p/x $pt[0x51]
$24 = 0x126265
(gdb) p/x ((uint32_t *)($child->page_directory[0x20] & 0xfffff000))[0x51]
$25 = 0x126265
(gdb) p/x ((uint32_t *)($child->page_directory[0x20] & 0xfffff000))[0x52]
$26 = 0x0
(gdb) p/x $pt[0x52]
$27 = 0x0The child inherits the .bss range, entry
0x51 is shared copy-on-write by both directories
(0x126265, the same word and the same flags as the stack
page in the first session), and entry 0x52, a page nobody
has touched, is zero in both: paging_fork_directory copied
a not-present entry as a not-present entry and incremented no reference
count. The third fault is the kernel’s:
(gdb) c
Breakpoint 2, demand_fault (cr2=134578720) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) p current_task->id
$28 = 4
(gdb) p/x cr2
$29 = 0x8058220
(gdb) p region
$30 = 0x16dc5 "bss"
(gdb) frame 1
#1 0x00013851 in page_fault_handler (regs=0xc000aecc) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
(gdb) p/x regs->err_code
$31 = 0x2
(gdb) p/x regs->cs
$32 = 0x8
(gdb) x/i regs->eip
0x158d1 <task_wait+141>: mov DWORD PTR [eax],edx
(gdb) bt
#0 demand_fault (cr2=134578720) at paging.c:152
#1 0x00013851 in page_fault_handler (regs=0xc000aecc) at paging.c:190
#2 0x00012ee8 in isr_dispatch (regs=0xc000aecc) at isr.c:73
#3 0x000102a6 in isr_common () at isr_stubs.asm:115
#4 0xc000aecc in ?? ()
#5 0x0001513e in syscall_handler (regs=0xc000afd4) at syscall.c:146
#6 0x00012ee8 in isr_dispatch (regs=0xc000afd4) at isr.c:73
#7 0x000102a6 in isr_common () at isr_stubs.asm:115
#8 0xc000afd4 in ?? ()
Backtrace stopped: previous frame inner to this frame (corrupt stack?)
(gdb) frame 0
#0 demand_fault (cr2=134578720) at paging.c:152
152 frame = pmm_alloc_frame();
(gdb) finish
0x00013851 in page_fault_handler (regs=0xc000aecc) at paging.c:190
190 if ((regs->err_code & 1) == 0 && demand_fault(cr2))
Value returned is $33 = 1
(gdb) p/x $pt[0x58]
$34 = 0x142007
(gdb) p 'paging.c'::demand_faults
$35 = 3Same task, CR2 = 0x8058220, which is
child_status, in the .bss again; but the error
code is 0x2, not present, write, supervisor,
CS is 0x08, and the instruction is in
task_wait: the mov DWORD PTR [eax],edx is line
315, *status = child->exit_status. The backtrace shows
where the fault was taken: page_fault_handler with its
regs at 0xc000aecc, below
syscall_handler’s at 0xc000afd4, on the same
kernel stack, because a fault in ring 0 switches no stack (chapter 13);
the two ?? () entries are gdb tripping over the
push esp in isr_common, whose frame it cannot
unwind. demand_fault neither knows nor cares:
current_task is task 4, the address is in its range, and
after finish entry 0x58 holds a fresh frame,
the mov is retried and the status lands. Three pages mapped
on demand, out of 79 the program could have asked for.
15.8.5 Limitations
The process model of this chapter is Unix’s in shape and a fraction
of it in substance. The gaps, in the order a shell would meet them.
There are no arguments and no environment: exec takes a
path and nothing else, so a program cannot be told what to do (exercise
15.1). There are no file descriptors: write goes to the
console and nowhere else, wait is the only way to pass a
value from a child to its parent, and there is no pipe; file descriptors
are what makes fork and exec a
composition mechanism, since a child inherits its parent’s open
files, and chapter 14’s exercises are where they start. There are no
signals and no kill: a parent cannot stop a child, a
program cannot be interrupted from the keyboard, and wait
cannot tell “exited with status -1” from “killed by a page fault”.
fork copies a whole page table for each private region, 4
KiB per 4 MiB of address space, even for a program that uses two pages
of it; Linux copies page tables lazily too. The reference count is a
byte, and nothing is done when it saturates. There is no swap: a frame
given to a program stays in memory until the program exits or
execs, and the kernel panics rather than reclaim anything
when the allocator runs dry. Demand paging stops at the zero-filled
pages: the program’s code and data are still read from the file and
copied in full by exec, where Unix maps the file and reads
each page at its first fault, and a read of an untouched page costs a
frame that a shared zero page would have saved. And wait
waits for any child; Unix’s waitpid selects one,
and can poll instead of blocking. Each of these is a few dozen lines on
top of what exists, and most of them are the exercises below or the
milestone project.
15.9 Exercises
Exercise 15.1. Give exec arguments:
exec(path, argv) where argv is a
NUL-terminated array of strings, which the kernel must validate and copy
to kernel memory before loading the program (every pointer in
the array, then every string), then write onto the new user stack in the
System V i386 layout: the strings, then the array of pointers, then
argc, so that crt0.asm can call
main(argc, argv). Write /bin/echo, which
prints its arguments, and make init run it with three
words. How many bytes of kernel stack does your copy use, and what
bounds the number of arguments?
Exercise 15.2. Add kill(pid), a system
call that ends another task. Decide what to do when the target is
TASK_SLEEPING or TASK_WAITING (it must not
stay in the queue in a state nobody will clear), when it is the caller’s
own parent, and when it is the idle task; make its parent’s
wait report a distinguishable status, as Unix encodes
“killed by signal N” separately from an exit code. Then make the
page-fault handler use the same path to kill a task, and check with
make test that nothing else changed.
Exercise 15.3. Implement vfork: a fork
that does not copy or share-COW anything, but lets the child run in the
parent’s address space, with the parent suspended (a new state)
until the child calls exec or exit. Measure
the frames and faults saved on the init sequence. Then
explain, with the stack page in mind, why the child must not return from
the function that called vfork, and what happens if it
does; this is why BSD invented it in 1979 and why POSIX removed it in
2008.
Exercise 15.4. Program text never changes, so it
need not be copied on write, and it need not be loaded twice either.
Make elf_load map segments without PF_W in
p_flags read-only (no PAGE_WRITE), and make
paging_fork_directory share such pages without the COW
mark; then keep a small cache in elf.c of the frames loaded
for each path, so that a second exec of
/bin/count reuses the frames of the first, with the
reference count keeping them alive. The user linker script will have to
put .data in a separate, page-aligned segment first;
readelf -l shows whether it did. Count the frames and the
disk reads before and after.
Exercise 15.5. Add brk(addr), which
sets the end of the program’s data segment: pages between the old end
and addr are mapped (zeroed, user, writable) and pages
above a lowered addr are freed. Keep the current break in
struct task, initialize it in elf_load from
the end of the highest PT_LOAD segment, and make
fork copy it. Write a malloc for user programs
on top of it, modeled on kmalloc, and a program that
allocates a megabyte, forks, and has the child write one byte: how many
frames did the parent’s allocation cost, and how many did the fork and
the write add?
Exercise 15.6. Measure copy-on-write. Write a
program with a global array of 256 KiB (64 pages of .bss),
fork it, and have the child write one byte every 16 KiB; print
cow_faults and cow_copies before and after
from the kernel (a SYS_GETSTATS is enough). Then implement
the eager alternative in paging_fork_directory, a
memcpy of every present page into a fresh frame, under a
compile-time switch, and compare the frames used and the time between
fork and the child’s first line, with gettime,
for both strategies. At what fraction of pages written does eager
copying stop losing?
Exercise 15.7. The stack window is 256 KiB with
nothing below it, so a program that recurses too deep is killed with the
same page not present message as one that dereferences a
wild pointer. First make the message tell them apart: when a user fault
lands just below the window, say so. Then put a guard page at
the bottom of the window, an address task_lazy_region
refuses even though it is inside the range, and explain what it buys
that the window’s edge did not. Finally let the window grow: record the
lowest stack page a task has touched and allow a fault one page below
it, up to a limit such as 8 MiB, which is what ulimit -s
prints on Linux; test with a recursive function and a counter of its
depth printed every thousand calls.
Exercise 15.8. Finish the job: make the file-backed
pages lazy too. Keep the executable’s inode and the PT_LOAD
segments (file offset, address, sizes) in struct task, have
elf_load map nothing at all, and have the fault handler
read the right 4 KiB of the file into a fresh frame when a page of a
segment is first touched, zeroing the part beyond p_filesz.
This is what Unix means by demand paging, and the reason an
exec of a large program is fast. Count the disk reads and
the frames for /bin/init before and after, and find the one
thing in the lazy loader that is harder than in the eager one (hint:
what does fork have to copy now, and what happens to a page
whose file bytes and .bss bytes share a page after a
fork?).
15.10 Check your understanding
paging_fork_directoryclears the R/W bit in the parent’s page-table entries, not only in the child’s copy. What would go wrong if only the child’s entries were read-only, and which process would observe it?The parent’s entries are changed while the parent’s directory is in
CR3, and each change is followed byinvlpg. Suppose theinvlpgwere omitted. Describe exactly which process would see which bytes, and why the bug would come and go depending on how much else the machine was doing.task_forkpushesEFLAGS = 0x2on the child’s prepared stack wheretask_allocpushed0x202. What would change iftask_forkused0x202, and why was0x202necessary in chapter 13 but not here?SYS_EXECcopies the path into a kernel buffer before callingtask_exec. Suppose it passedregs->ebxstraight through andtask_execread the path afterpaging_switch_directory. What would the kernel read, and what wouldcurrent_task->namepoint to after the old directory was freed?If
CR0.WPhad stayed clear, what precisely would the store*status = child->exit_statusintask_waitdo when the page holdingstatusis still shared copy-on-write with a running child, and which of the two processes would notice?A dead task keeps its
struct taskuntilwait. Why cantask_exitnot free the structure itself, and why does the kernel not simply copy the status into the parent’s structure at exit time and free the child at once?The reference count is a byte and
pmm_frame_refsaturates at 255. Trace what happens to a frame that 256 processes share when they exit one by one, and say whether the result is a leak or something worse. What is the cheapest correct fix?page_fault_handlertests bit 0 of the error code before deciding betweencow_faultanddemand_fault, and each of the two functions then checks for itself,cow_faultthe page-table entry anddemand_faultthe task’s lazy regions. Give an access whose error code has P = 0 and which is nevertheless not a demand fault, and one whose error code has P = 1 at an address inside a lazy region; say what the handler does with each, and whydemand_faultcould not simply be tried first on every fault.After
bigbssforks, neither process has touched the page of.bssat0x08052000, and both page tables hold a zero for it. The child then writes to it. Which directory gets a frame, what does the parent see at that address afterwards, and why is that the right answer? Then supposetask_forkhad forgotten to copybss_startandbss_end: which of the child’s accesses would still work, and which would kill it?
15.11 Milestone project: a shell
Part III ends here, and the kernel you have can run any program on
its disk, but only init decides which. The milestone that
closes the part is to replace that decision by a prompt: a shell,
/bin/sh, that reads a command line from the keyboard and
runs it. The pieces are all in place except one, the way from the
keyboard to a program.
What you already know. The keyboard driver of
chapter 11 turns IRQ 1 into characters and prints them; the scheduler of
chapter 13 can block a task and wake it from an interrupt handler
(TASK_SLEEPING and task_wake_sleepers are the
pattern); chapter 13’s user_range_ok validates a buffer;
chapter 14 reads directories and files; this chapter runs programs with
fork, exec and wait.
Goal. A read(buf, len) system call that
returns characters typed on the keyboard, and a shell built on it. The
driver’s IRQ 1 handler stores characters in a ring buffer and
wakes the task blocked in read, if any; read
copies what is available into the validated user buffer and returns the
count, or blocks, in a new TASK_BLOCKED state, when the
buffer is empty, so that the idle task’s hlt is where the
processor waits for a key. No busy waiting:
monitor info registers in QEMU should show the processor
halted while the shell waits. On top of read, a line editor
in the shell (characters up to Enter, backspace, echo by the shell,
since the chapter 11 driver should stop printing what it receives), and
the loop: read a line, if it is empty prompt again, otherwise
fork, exec("/bin/" + word) in the child,
wait in the parent, and print the exit status when it is
not 0. Two built-ins: ls, through a
readdir(path, index, entry) system call that returns the
index-th entry of a directory, name and inode number, from
the ext2 code; and cat name, through
open(path) and read(fd, buf, len) on a regular
file, which means a small table of open files per task (an inode and an
offset) and a file descriptor number, with the keyboard as descriptor 0.
The kernel starts /bin/sh instead of
/bin/init.
Success criterion. From a fresh
make qemu, typing ls lists /bin
with hello, count, init,
bigbss and sh; cat /etc/motd
prints the file; hello prints
Hello from user space with the pid of the child;
count prints its five lines and the prompt comes back after
them, not before; nothing prints a message from the shell,
not from the kernel, and the prompt comes back; a program that faults
(write one that reads 0x10000) is killed by the kernel and
the shell prints its status and goes on. make test must
keep passing: feed the shell a script through the serial port (QEMU’s
-serial is bidirectional; make read accept the
serial port’s receive interrupt as a second source) with the lines above
and the strings they produce, and keep the e2fsck
check.
Stretch goals. Arguments through exercise 15.1, so
that cat and echo work the Unix way instead of
as built-ins. & after a command, which skips the
wait and reaps the child later; wait then
needs to say which child it collected. A history of the last ten lines
on the arrow keys. Project 2 of chapter 17, Epilogue, continues from
here with pipes, redirection and Ctrl-C.
Debugging note. The kernel now writes into user
memory in read, and the buffer may be a page that
fork shares copy-on-write: the write faults in ring 0 with
error code 0x3, and cow_fault must handle it,
which it does only because CR0.WP is set; break on
cow_fault and look at regs->cs the first
time a read from a freshly forked shell completes. The
second thing to watch is TASK_BLOCKED without a wake-up: a
task that blocks before the character arrives and a handler that wakes
nobody because the task was not yet blocked is a race, and
irq_save around the test-and-block in read is
the fix, for the reason given in chapter 13’s section on critical
sections. When the shell hangs, make gdb,
p *current_task and a walk of the run queue with the
while loop of chapter 13 tell you who is waiting for
what.