Page Faults as a Feature

18 · Page Faults as a Feature¶

The question¶

What can a kernel do with a fault it expected?

ch17 ended with a walk that stopped and a level to report it at. That was presented as a diagnosis, which is how a fault is usually introduced: something went wrong, and here is where. But a walk stops whenever an entry is absent, and the kernel decides which entries are absent. So a kernel can arrange to be told, by hardware, at the exact moment a particular address is touched — and the question stops being what went wrong and becomes what to do about it.

The material¶

The hardware will call you¶

A page fault is a callback, with three unusual properties.

It is precise: the kernel is given the address, in stval, not merely told that something happened. It is synchronous: it happens at the instruction that touched the address and not at some convenient later point. And it is unavoidable: the program cannot opt out, because it does not know it is happening.

No other mechanism in the machine has all three. A timer interrupt is not precise. A system call is not unavoidable — the program has to make it. This is the only way to have code run exactly when a particular byte is used, and everything in this chapter is built on that one property.

The instruction runs again¶

The difference from ch16 is one line of the kernel.

After a system call, usertrap advances the saved program counter past the ecall before returning, because the call has been made and the program should carry on with the next instruction. After a page fault it does not. The saved program counter still points at the load or store that faulted, so returning from the handler runs that instruction again.

That is exactly what you want. The handler does not emulate the access, does not need to know what the instruction was, and does not have to put a value anywhere. It makes the address work and returns, and the hardware does the rest. A fault handler is therefore allowed to be ignorant of almost everything about the program it is rescuing.

One test, and the one next to it¶

xv6’s handler asks whether the faulting address is below the process’s size. Below it, the process asked for this memory and has not touched it yet, so the right answer is to allocate a page, map it, and return. At or above it, the process is using an address it never requested, and the right answer is to kill it.

A second test sits beside it, and it is the one that gets left out. If the page is already mapped, the fault cannot be a first touch — the entry is there and valid, so the walk did not stop for lack of one. It stopped because a permission was refused. Allocating a fresh page for that case would map a blank page over one the program was in the middle of using, and the program would not crash; it would get the wrong answer. Problem 18.2 is about exactly these edges.

Both policies are already here¶

Unusually, this kernel already implements both allocation policies, and lets a program pick one per call. sbrk, the call that grows a process’s memory, allocates the pages when you ask. sbrklazy increases the process’s size and allocates nothing, leaving the faults to do it.

So this chapter adds no policy and changes no decision. The patch counts:

+census_page(int lazy)
+{
+  struct proc *p = myproc();
+
+  if (p == 0) // during boot there is nobody to charge it to
+    return;
+  if (lazy)
+    p->fc.lazy_pages++;
+  else
+    p->fc.eager_pages++;
+}
+

Per process, because the shell is allocating too and a global total would mostly be a fact about the shell. Recorded as the process exits, because by the time anybody can press a key the interesting process has gone.

The trade, counted¶

The workload asks for memory both ways and touches a known amount of it:

int main(void) {
  char *sparse_lazy = sbrklazy(SYSFS_SPARSE_PAGES * PGSIZE);
  touch(sparse_lazy, SYSFS_SPARSE_TOUCHED);

  char *dense_lazy = sbrklazy(SYSFS_DENSE_PAGES * PGSIZE);
  touch(dense_lazy, SYSFS_DENSE_PAGES);

  char *eager = sbrk(SYSFS_SPARSE_PAGES * PGSIZE);
  touch(eager, SYSFS_SPARSE_TOUCHED);

Build it into the kernel, boot, and run it:

./run faultload

Three phases, chosen to bracket the trade rather than to demonstrate a win. A large lazy request barely touched; a smaller lazy request touched in full; an eager request of the same size as the first. The two lazy requests appear in the table summed rather than separately, because the census counts per process and not per call.

Conditions: target xv6 · qemu virt (-machine virt -bios none) · QEMU emulator version 8.2.2 (Debian 1:8.2.2+ds-0ubuntu1.18) · xv6-riscv @ 9e3161a · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · xv6's own CFLAGS · 2026-09-17 · Source: bench/results/faults-xv6.json, code hash 89e452857447d851.

Read the first four rows as one sentence. Most of what was asked for lazily was never allocated, and the pages that were allocated each cost one entry into the kernel — the whole of ch16’s trap path, plus a walk, plus an allocation, for every one of them.

That is the exchange rate, and the half usually left out is the price. Laziness is nearly always described by its saving, and the saving here is real and large. The price is real too: a number of kernel entries equal to the number of pages the program actually uses. Which of those matters depends entirely on the ratio between them, and that ratio is a property of the program rather than of the policy.

The last row is a different kind of fact: before main ran at all, exec had already allocated pages for the program’s text, its data and its stack. Every process pays that, and it is the baseline everything else in the table sits on top of.

Which fault, and what this kernel does about it¶

The hardware does not report “a page fault”. It reports a load fault, a store fault or an instruction-fetch fault, as three different causes.

Conditions: target xv6 · qemu virt (-machine virt -bios none) · QEMU emulator version 8.2.2 (Debian 1:8.2.2+ds-0ubuntu1.18) · xv6-riscv @ 9e3161a · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · xv6's own CFLAGS · 2026-09-17 · Source: bench/results/faults-xv6.json, code hash 89e452857447d851.

Every page in this run arrived on a store, because the workload writes to each page it touches. A program that read a lazily-allocated page before writing it would produce load faults instead, for the same pages.

And this kernel does nothing with the difference: both causes are handled identically and get a readable, writable page. That is a real observation about xv6 rather than a gap in the measurement — the distinction exists in the hardware, and using it is what copy-on-write is. A kernel that shares a page between two processes marks it read-only in both, at which point a load fault cannot happen and a store fault means somebody is about to modify a page they are sharing. Same hook, same handler, one more test.

What laziness costs that is not faults¶

There is a second price, and it is not pages or faults: laziness changes when a program finds out it has run out of memory.

An eager request that cannot be satisfied fails at the call. The program gets a return value it can test, and can do something sensible — free a cache, use a smaller buffer, report a clear error. A lazy request always succeeds, because nothing has been allocated and there is nothing to fail. The shortage is discovered later, by a store instruction, in the middle of code that has no idea it is allocating anything. There is no return value to check at that point, and nothing the kernel can do but kill the process.

So laziness moves a failure from a place where the program can handle it to a place where it cannot. That is the whole reason an operating system which overcommits — promises more memory than it has — needs a policy for choosing something to kill, and problem 18.3 is about being able to say precisely when each version finds out.

What we measured¶

Pages allocated and faults taken for one workload, under each of the kernel’s two policies, with every quantity fixed by the program rather than observed to be steady. faultload prints what it asked for and what it touched; the kernel counts independently; the runner refuses to stamp a result in which the two disagree, refuses one latched from a different process, and refuses one in which the handler declined a fault — which would mean the workload went somewhere it never asked for, and that the numbers describe a bug rather than a policy.

What this cannot tell you¶

What a fault costs. Not a single duration appears above, and it could not honestly. A fault’s cost is the trap path, the walk, the allocation and whatever the TLB and the caches make of the interruption — and this target models none of the last part. ch29 prices the whole shape on hardware. Until then, the fault count above is a count of kernel entries and not a claim about time.

Whether laziness is worth it. The table gives the exchange rate for one workload, chosen to show both ends. Whether trading those pages for those faults is a good deal depends on how much memory costs relative to kernel entries on the machine in question, which is a question about hardware and not about kernels.

Copy-on-write, demand paging — a page fetched from disk when first touched — and the rest. The chapter names them and measures none of them, which is deliberate and is not the same as their being free. Each is this hook with a different test, and each has its own exchange rate that this chapter has not measured. Naming a mechanism and pricing it are different things, and the book tries hard not to let the first pass for the second.

Anything about fragmentation. Every page here is the same size and comes from a free list that does not care which one it hands out. A system where physical contiguity matters — for large pages, or for a device doing its own addressing — has an allocation problem this one does not, and no measurement here would notice.

Problems¶

Three, in tests/page_faults_as_a_feature/policy.c. They are the three decisions the handler is really making, taken out of the kernel so that being right about them is separable from getting a kernel to boot. Neither this chapter’s patch nor anything in sysfs/ answers any of them: the patch counts and decides nothing.

18.1 — How many faults will these accesses cause? You are given runs of bytes a program touches and asked for the number of first-touch faults.

A program thinks in bytes and the machine charges pages, which is the trap the whole chapter rests on. Two accesses in one page cost one fault; an access of two bytes can cost two. The runs overlap, repeat and arrive in no order.

python3 -m pytest tests/page_faults_as_a_feature/test_problem_1_faults.py

18.2 — What should the handler do about this fault? Allocate, kill, or refuse to have an opinion. Nine cases, and three of them are the ones a handler written from the happy path gets wrong: the exact boundary, a page that is already mapped, and a cause that is not a page fault at all.

python3 -m pytest tests/page_faults_as_a_feature/test_problem_2_action.py

18.3 — When does a program that asks for too much find out? For each policy, say where the shortage becomes visible: at the request, at the touch, or never.

This is the section above, turned into a function. Getting it right means you can predict which of two programs — identical apart from one argument — dies in a way its author can do something about.

python3 -m pytest tests/page_faults_as_a_feature/test_problem_3_observed.py

Where to go next¶

The RISC-V privileged specification RISC-V International (n.d.) lists the fault causes and says exactly what the hardware guarantees about stval and about the state at the point of a fault. The guarantee that the faulting instruction has had no effect is the one worth reading carefully; it is what makes re-running it safe, and it is not free for the hardware to provide.

xv6’s vmfault in kernel/vm.c Cox et al. (n.d.) is the handler this chapter measured, and it is shorter than this section. Read it beside sys_sbrk in kernel/sysproc.c, which is where the two policies are chosen between — the whole difference is one branch.

ch19 stays with the same mechanism and changes what raises it. A page fault is the CPU interrupting itself about something it was doing; a device interrupt is somebody else entirely, with no relationship to the instruction that happens to be running, and that difference turns out to matter more than it sounds.