Build-a-Unix

Because one machine runs programs written by people who have never met, and some of them are hostile. If any instruction could reprogram the timer, edit another program's memory or talk to the disk controller, then the first program to run would own the machine and everything after it.

The mode bit makes that impossible in hardware rather than by agreement. In user mode a whole class of instructions faults. The kernel sets up the mode bit and the trap address once, at boot, which is the word for the first moments after the machine is switched on, when the kernel is running and no program of yours exists yet. It still has permission to do so then, and from then on user code can only get in at the front door.

Register names. The trap instruction carries no arguments of its own, so everything the kernel needs has to be sitting in registers before it runs, and both sides have to agree in advance about which ones. This machine is a RISC-V, where the agreement is: a7 holds the number of the call you want, and a0, a1 and a2 hold its arguments in order. When the kernel is finished it puts the answer back in a0, so the register that carried the first argument in is the one that carries the result out.

The names are arbitrary and every family of processor picks its own. An x86-64 machine does exactly the same job with rax for the number and rdi for the first argument, and its trap instruction is called syscall rather than ecall. Nothing about the idea changes: some agreed registers, one instruction, and a number that chooses a handler.

It is stopped, completely. A trap does not start a second thing running alongside your program. It takes the one processor away from it, part way through, and gives it to the kernel. While the kernel works, your program executes no instructions at all.

What keeps its place is a small block of memory called the trap frame, holding every register your program had at the moment it trapped, including the address of the instruction it had reached. When the kernel is finished it copies all of that back and returns to that address, and your program carries on as though the call had simply taken a while. It has no way of telling how long it was stopped, or that anything else ran while it was, except by asking the kernel what time it is.

Nothing in the hardware makes descriptor 1 the screen. It is a convention, and the whole reason it works is that whoever starts your program sets the table up before you run. By agreement, 0 is where you read your input from, 1 is where your ordinary output goes, and 2 is where your complaints go.

Keeping 1 and 2 apart is what lets somebody send a program's output into a file while still seeing its error messages on the screen. Both are just numbers, and a program that writes to 2 has no idea whether anybody is looking.

Every system call in this course answers with one whole number and nothing else. There is no other channel. So that one number has to carry the news, and the convention is the same for all twenty one calls. A number of zero or more means it worked and the number is usually a count of something: how many bytes were written, or which descriptor you got. A negative number means it failed and nothing happened.

That is why -1 turns up so often below. It is not an error message and it does not say what went wrong; it only says the call did not do its job. A real machine puts a reason code in a second place beside the -1, which is why two completely different failures can look identical from the number alone.

Crossing into the kernel is expensive compared with adding two numbers, so the printing code in your program does not cross once per character. It collects characters in a buffer, which is an ordinary patch of memory used as a waiting area, and only when the buffer is full, or a new line arrives, does it make one system call carrying the lot.

It saves an enormous amount of work and it costs you one thing: if the program dies while characters are still sitting in the buffer, those characters are gone. They never reached the kernel. A crash can therefore omit the final partial line unless the program flushes it or writes to an unbuffered stream.

The panel shows, for each descriptor: the number, which open file entry it leads to, what that entry points at, and a count called refs. The number and the destination you have met. The middle one is the part worth knowing about, because it means your table does not hold the open file itself. Your table holds only positions, and each position names one entry in a second table that the kernel keeps once per open, whoever did the opening.

That is what refs counts: how many descriptors, in this process or in any other, currently point at that one entry. The entry, and the position in the file it is holding, is thrown away only when the count reaches zero. So closing a descriptor does not always close the file, and two descriptors can share one position in one file. Step 4 and step 7 are both built on exactly that.

Running means this one is on the processor right now, and on a machine with one core, core being the word for one processor inside a chip that may hold several, exactly one process is in that state. Runnable means ready and simply not chosen yet. Sleeping means waiting for something specific that has not happened. Zombie means finished but not yet collected. Unused means the slot is empty.

A sleeping process costs nothing at all. The part of the kernel that chooses who runs next, the scheduler, which step 11 takes apart, does not try it and skip it: it is not in the queue, and the note beside it says what would wake it. A machine with four hundred sleeping processes and one runnable one is doing exactly as much work as a machine with one process.

Every process is started by another process, which cannot be true of all of them or there would be no first one. So the kernel cheats exactly once. At boot it builds one process by hand: it fills in a row in the table, gives it pid 1, hands it a page of memory and a descriptor on the console, and starts it. That process is called init, and on the machine in these labs it is the row you will see above the shell in every process table on the page.

What init does is small and it never stops doing it. It starts a shell, and then it waits. Whenever a process dies and leaves children behind, those children are handed to init, and init collects their exit status. The lab protects pid 1 because removing the reaper would leave finished child entries in the simulated process table.

Because the kernel cannot allocate memory the comfortable way your programs do. It is the thing that hands memory out, so it cannot ask anybody for more, and a table that grew would have to be moved, halfway through, while other parts of the kernel were pointing into it. A fixed array of rows, decided when the kernel is built, can never fail halfway through and never needs moving.

The price is a hard ceiling, and the ceiling is real on real machines too. Linux has one, it is just a large number rather than eight. When you meet a machine that will not start anything at all while apparently doing nothing, this table, full of rows nobody has collected, is very often the reason.

It returns once in each process, which is not the same as returning twice in one. At the moment of the copy there are two processes, both stopped just after the trap instruction, both about to be given an answer. The kernel writes a different number into each one's register and lets them both go.

From inside either process nothing strange happened at all: a function was called and it came back with a number. The strangeness is only visible from outside, where you can see two of them.

It would be, and no real kernel does it. This machine copies every page at the moment of the fork because that is the easiest version to watch, and it is the pessimistic one: forking a process using a gigabyte would cost a gigabyte. What a real kernel does instead is point both page tables at the same frames and mark every one of them read only in both. Nothing is copied at all, and for that moment the two processes are sharing one set of frames.

Then the first time either of them writes, that write faults, exactly the way step 10 describes. The kernel sees a page that ought to be writable, copies that one page, points the writer at the copy, and restarts the instruction. Only the pages that are actually written cost anything, which is why forking is cheap and why forking and immediately calling exec, which throws the whole image away, costs almost nothing at all. It is called copy on write, and the frame counts in this course are the honest upper bound rather than what you would measure.

Same word, two completely unrelated meanings, and both of them turn up in this course. A stack frame is the patch of stack one function call uses while it runs. A frame here is a fixed-size slab of the actual memory chips, and this machine has twenty four of them, which the kernel hands out whole and takes back whole.

The kernel deals in frames because it never wants to search for a piece of memory the right size. Every request is one frame or several, every frame is interchangeable with every other, and the free ones are a list of numbers. Step 9 is about how a program's addresses get attached to particular frames, and until then the only thing to watch is the count: fork takes some, exec hands some back, and when there are none left the call that wanted one fails.

Plenty of systems have a single call that makes a new process running a named program, and it always grows a long list of options: run it with this input, that output, this directory, those permissions. Every one of those options exists because the new process cannot be adjusted before it starts.

Splitting the job leaves a gap in the middle where the child exists, is under your control, and is not yet the program. Anything you want to arrange, you arrange there using the ordinary calls you already have. Step 7 is entirely about what people do in that gap, and it is why redirection needs no support in the kernel and none in the program being redirected.

Three things, and the third is the surprising one. The instructions, as the numbers the processor reads. The starting values of any variables that exist for the whole run, because a program that begins with a total of zero has to get that zero from somewhere. And one number saying which instruction to start at, because the first instruction is not always the first byte.

The stack is not in the file. Nothing in a file could say what the stack should contain, because it depends entirely on what happens while the program runs. Exec sets aside room for it, empty, and the program fills it as it goes. A program is executable code and data stored in a file. A process is a running instance with registers, memory mappings, open descriptors, and other execution state.

The kernel has to know which frames of memory are in use and which are not, and it keeps that in the simplest structure there is: a free list, meaning nothing more than the set of frame numbers nobody currently has. Taking a frame means picking one out of it. Giving one back means putting the number back in. No searching for a piece the right size, no fitting things together, because every frame is the same size and any one of them will do.

Which is why the lab below shows something that looks wrong. Exec hands three frames back and then takes three more, and gets the same three numbers. This machine always hands out the lowest free number, and the moment the old ones were released they were the lowest free numbers there were. Nothing was kept and nothing was reused on purpose.

wait asks for the exit status of a finished child. If one has already finished it answers straight away and the row in the process table is thrown away. If none has, the caller sleeps until one does. If there are no children at all it answers -1 rather than waiting forever.

A shell without a wait keeps running and looks fine. The commands still work, because the child does its job whether or not anybody collects it. What builds up is finished rows nobody has claimed, one per command, until the table is full and the next fork fails.

Because it is not special. The shell has no permission your programs do not have and no help from the kernel: it is one more ordinary process, reading lines from descriptor 0 and making the same three calls anybody can make. If you deleted it and wrote your own, the machine would not notice.

The loop below is a minimal shell: read a command, create a child, replace the child image, and wait. Real shells add parsing, pipelines, redirection, job control, expansion, and built-in commands around those process operations.

When a process exits it hands back one small number, and the convention everywhere is that 0 means it worked and anything else means it did not. That number is the whole of what wait collects. It is what the zombie row in step 3 was holding on to. It exists because the process that started a program is usually the only one in a position to care whether it succeeded.

Almost everything a shell does with several commands is built on it. Joining two commands so that the second only runs if the first worked is a check on that number. A script that stops the moment anything fails is checking it after every line. And the reason a program should bother to exit with the right number, rather than always 0, is that nothing else it prints can be checked so cheaply by whatever started it.

Yes, and only three lab boxes in the whole course ask for it. The language in those boxes is a small one built for this page. It is close enough to the C you read in Bits and Memory that reading it takes nothing new. Three differences are worth knowing. You write const x = 5; or let x = 5; instead of naming a type. Text is compared with ==, the same way numbers are. And while (true) { ... } with a break; inside is how you write a loop that runs until something stops it.

Everything else is what you already read: a name followed by round brackets calls something, = puts a value somewhere, == asks a question, curly brackets group lines together, and if (...) { ... } else { ... } picks one group or the other. There is a Show me one that works button under every one of these boxes, and using it and then reading the answer is a perfectly good way to do the lab.

dup copies a descriptor to the lowest free number, so two numbers lead to one open file. Closing 1 and then opening a file gets you the same result in the simple case, and shells use dup when they need to keep the old descriptor to put back afterwards, or when what they want in slot 1 is already open, such as one end of a pipe.

Both copies share one position in the file. Writing through either moves both along, which is what you want when a program and the thing it launched are both appending to the same output.

A read from a pipe with nothing in it does one of two completely different things, and which one depends on something the reader cannot see. If some process somewhere still holds the write end open, more might yet arrive, so the read sleeps and waits. If every write end everywhere is closed, nothing can ever arrive, so the read answers 0 immediately. That 0 is what end of file means: not an error, just the news that there will be no more.

This is why the closing matters so much in the lab below. A write end left open by somebody who is not using it, the shell for instance, makes the second answer impossible, and a pipeline that should have finished sits waiting forever with no error anywhere.

The buffer is small, a few thousand bytes on a real machine and a handful of characters here, and a program on the writing end can easily produce faster than the program on the reading end consumes. Nothing is thrown away and nobody is killed. The write simply does not finish: the writer is put to sleep until the reader takes something out. Then it wakes and carries on.

So a pipeline runs at the speed of its slowest program, without any of the programs in it knowing that is what is happening. Each one performs ordinary reads and writes that may block. The kernel maps each descriptor to the appropriate pipe end, so neither program needs pipe-specific transfer code.

Because an inode has to be a fixed size. They live packed together in a table so the kernel can find number 4000 by arithmetic instead of by searching, and that only works if they are all the same size. A fixed size record cannot hold a list that grows.

Four direct numbers and one indirect block, which is what this disk has, is where the idea starts rather than where it stops. Real filesystems carry on the same trick with a pointer to a block of pointers to blocks of pointers, which is how a fixed size record describes a file of many gigabytes while staying exactly as big as every other record in the table.

An ordinary file. It has an inode and blocks like any other, and the only thing unusual about it is what is written inside: a list of pairs, each one a name and an inode number. That is all a directory is. It is why the kernel can look up a name in one without knowing anything about what the name leads to.

Two things follow that are otherwise strange. Two different names, in the same directory or in different ones, can carry the same inode number, and then one file has two names with neither one being the real one. And renaming a file inside one directory copies not one byte of its contents: the kernel writes a different name next to the same number. The contents never moved because the contents were never attached to the name in the first place.

Writing one file changes several blocks: the inode, the blocks holding the contents, the record of which blocks are free, and the directory holding the name. The disk does one block at a time. So there is always a moment when some of those have been written and the rest have not. A machine that stopped at that moment starts up again with a disk that contradicts itself. A block marked in use that no inode mentions is lost space. An inode listing a block the free record also offers to the next file is much worse.

Every real filesystem has an answer to this and none of them is simple. The usual one is to write down what you are about to do, in one place, before doing any of it, so a machine starting up can finish or undo whatever was in progress. That is a whole course of its own, and it is the one called Fault Tolerance at the bottom of this page.

A table with an entry per address would be bigger than the memory it describes. So translation works per page instead: the top bits of the address choose a page and the bottom bits say where you are inside it, and only the top part is translated. Where you are inside a page is the same before and after, which is why the offset is carried across untouched.

Splitting the top part again, into a directory index and a table index, saves more. A program using the very bottom of its address space and the very top needs two small tables and one directory instead of one enormous table with a vast empty middle. That is the only reason for the second level.

Every program in this course has its memory in three pieces and the labs name them the way Unix has named them since the seventies. The text is the program's instructions, which is an unhelpful name, since it holds no words at all, but it is the one everything uses. The data is the variables that exist for the whole run. The stack is the one from Bits and Memory: the part that grows and shrinks as functions call each other, and it sits at the very top of the address space, which is why its addresses all begin 0xFF.

The page table gives these regions different permissions. Text is readable and executable but not writable, which blocks ordinary stores from changing instructions. Data and stack pages are writable but should not be executable. Real systems may use finer divisions, but the protection still comes from permission bits in each page-table entry.

It would be unusable if it did. Two extra reads of memory to work out where one read of memory goes would make every program three times slower, and the walk in the lab below is the short version with only two levels. Real machines have four.

So the processor keeps a small store of translations it has done recently, right next to the part that does the arithmetic, and looks in there first. Almost every access hits it, because programs use the same few pages over and over. The full walk happens only when it misses. This is why the same program can be slow for reasons that have nothing to do with how much work it does: a program that jumps all over its memory misses that store constantly, and a program that keeps to a few pages almost never does.

The faulting instruction did not half happen. The processor works out that it cannot complete before it changes anything, so nothing was written and no register was updated. Once the kernel has mapped the page it returns to the same address, and the instruction runs again from the beginning, this time finding what it needs.

The program cannot tell any of this happened. There is no callback, no return value, no flag. The only trace is the time it took, which is why a program's first pass over a large array is slower than its second for reasons that have nothing to do with the cache.

Because it is how a program gets memory at all. Nothing is handed over when a program starts and nothing is handed over when it asks; a frame appears at the moment a page is first touched, and not before. So the ordinary life of an ordinary program includes a fault for its first instruction, a fault for the first thing it puts on the stack, and a fault for every new page after that. Starting a program and running one command costs tens of them before anything interesting has happened.

Lab 24 keeps the count on a badge that says page faults. Watch it while you touch a handful of addresses and you will see it climb steadily and nothing go wrong. The word makes it sound like a breakdown because it is the same mechanism as the two kinds that really are fatal, and the kernel cannot tell which of the three it has until it looks the address up.

It is handed it. The trap carries nothing by itself, so the processor puts the address that could not be translated into a register set aside for exactly this, along with a few bits saying whether the access was a read or a write and whether the program was in user mode at the time. The handler's first job is to read those, and it has no other way of knowing.

Which of the three cases it is comes entirely out of those two facts. An address in a region, with no frame behind it, is the ordinary case and gets one. An address in a region the program is entitled to read but not write, faulting on a write, is the second case. An address in no region at all is the third. The same handler, the same few lines, and the answer is different because what it looked up was different.

Early systems asked programs to give the processor up politely, and the arrangement works right up until one program has a loop with no exit in it. Then nothing else ever runs again, and there is no software anywhere that can help, because software only runs when it has the processor.

A timer that interrupts regardless is the only fix. It is why a modern machine survives a program spinning forever, and it is why turning interrupts off is a privileged instruction: a user program allowed to do that could take the machine and never give it back.

A tick is one firing of the timer, and it is the unit this whole machine measures time in. It is the number in the first column of the system call strip, it is the badge marked tick under the labs below. It is what a sleeping process is waiting for a certain number of. On a real machine a tick is a few thousandths of a second; here it is however often you press the button.

A time slice is how many ticks in a row one process is allowed to keep the processor before the scheduler takes it away and gives it to somebody else. The slider in the lab below sets it. A short slice means more switching, so more of the machine goes on the switching itself and less on the work; a long slice means less switching, but a job that wants the processor may sit and wait a long while for its turn. There is no right answer, and every operating system picks a compromise.

Because the program does not know it is being interrupted. When a function in your program calls another function, the two of them have agreed in advance about who saves what, and the caller can put anything it cares about somewhere safe before the call. A timer interrupt has no such moment. It lands between two instructions chosen by nobody and the program has no chance to prepare because it is not involved.

So the kernel has to save all of it, every register, exactly as it stands. In the lab below that is the three values you can see: pc, the address of the next instruction; the accumulator, which is where the counting is happening; and sp, the address of the top of the stack. Each process's row holds a copy of all three, and the row is out of date for exactly as long as that process is the one running. Lab 26 takes one of those three out of the saving code and lets you read what happens next.

Two processors run kernel code at the same time as easily as they run yours, and the kernel's data is shared by definition: one process table, one free frame list, one open file table. Two processes on two cores calling fork at the same moment are both walking the same table looking for a free slot.

The same problem turns up on a machine with one core, because the timer can interrupt between any two instructions, including between a read and the write that follows it. Multiple cores make it easier to see and much harder to get lucky with.

Take it too late or let it go too early and it protects nothing. If the gap between the read and the write is not entirely inside the lock, the other processor can still get in, and the count is still wrong, just less often, which is worse. Take it and never let it go and the counter is perfectly safe and the machine stops: the other processor waits for something that is never coming back. A wait with no end is called a hang. It is the most common way locking is got wrong.

And waiting is never free. A processor sitting on an acquire is doing no work at all, so every instruction inside a lock is an instruction some other processor may be spending doing nothing. That is why the piece of code a lock covers is kept as short as it possibly can be, and why the answer is never "put a lock round everything".

Something that neither piece of code is wrong on its own. Suppose one lock protects the process table and another protects the list of free frames. One processor takes the process table, then wants the frame list. The other takes the frame list, then wants the process table. Now each of them is holding the thing the other is waiting for, and neither will ever let go, because letting go is what they were going to do after getting the second one.

Nothing has crashed and no rule has been broken. Both processors are simply waiting, forever, and the machine is finished. The fix is a rule rather than a mechanism: everybody who takes both locks takes them in the same order. Kernels write that order down, in a comment. It is one of the things a change to kernel code is checked against most carefully.

A handler runs with every permission there is, on behalf of a program that may be actively hostile. Anything it is passed has to be checked before it is used: a pointer from a user program might point into the kernel, a length might be enormous, a descriptor number might be off the end of the table. The handler cannot trust any of it.

It also cannot take its time. While it runs, the process that called it is stopped, and if it holds a lock then everything else that wants that lock is stopped too. Handlers that need to wait put the process to sleep and return later rather than sitting there.

Because it is not in your address space. The process table is in kernel memory, and no page of kernel memory appears anywhere in your page table: there is no virtual address your program could put in a register that would reach it. It is not that reading it is forbidden and checked. There is nothing at those addresses as far as your program is concerned, and an attempt to touch them is the third kind of page fault from step 10, the fatal one.

Which is why the trap is not a formality on the way to something a program could have done anyway. It is a change of address space as well as a change of mode: the same instruction that raises the privilege puts the processor somewhere the table is visible. A system call crosses that protection boundary, allowing checked kernel code to inspect process-wide state that user code cannot access directly.

Linux has around three hundred and fifty, and the great majority of them are variations. There is a call to open a file, and another one that opens it relative to a directory you already have open, and another one that takes a bag of options instead of a fixed set of arguments. The twenty one here are close to the whole of what xv6 has. They are enough to run a shell, a compiler and a text editor, which suggests how much of the rest is convenience rather than capability.

What a real kernel does not do is renumber them. Every program ever compiled has the numbers built into it, so number 1 has to mean the same thing in thirty years as it does today, and a call that turns out to be a mistake is left in place forever with a better one added beside it. That is why the list only ever grows, and why the quiz below matters more than it looks.

A game wants low input latency. A render farm wants throughput. A flight controller must finish some work before a deadline. These goals can disagree. Operating systems therefore provide scheduling classes and weights, while safety-critical systems often reserve time explicitly. Write the workload and the failure that matters before choosing a policy.

Suppose a low-priority task holds a lock. A high-priority task needs that lock, so it blocks. A medium-priority task can now run ahead of the low-priority task, preventing it from releasing the lock. The high-priority task is indirectly delayed by medium-priority work. With priority inheritance, the lock holder temporarily receives the waiting task's priority. It runs, releases the lock, then returns to its old priority.

On several cores the scheduler must also decide where a task runs. Moving it may balance load, but it also makes the new core refill its caches. CPU affinity, cache topology and NUMA memory all affect that choice.

Reading a file usually places its blocks in the page cache. A later read can use those same physical pages without touching storage. mmap maps cached file pages into a process, so a load instruction can read them directly. Copy-on-write can let several processes share a page until one writes. These are different interfaces built on the same frame, page-table and fault machinery.

Each core has a TLB. If the kernel changes a mapping that other cores may have cached, it sends them a TLB shootdown so they discard the stale entry. On a NUMA machine, memory attached to the local CPU socket is faster than remote memory. Page placement and task placement then become one problem: moving a task can turn local accesses into remote ones, while moving its pages costs bandwidth and pauses.

Atomic means recovery sees the old state or the new state, not a mixture. Ordered means one write becomes durable before another. Durable means acknowledged data survives the failures named in the contract. A database transaction may be atomic but not durable if nobody asks the filesystem to flush it. Begin every crash test by naming the failure: process crash, kernel panic, device reset or sudden power loss.

A checksum can tell recovery that a block is torn or corrupted. It cannot reconstruct missing bytes on its own. Mirroring, erasure coding or another replica supplies a second copy. Checksums plus redundancy let a system both notice damage and repair it.

An IOMMU translates and checks device memory accesses in much the same way that a page table checks process accesses. The kernel maps only the buffers a device may use. Without that boundary, a broken or hostile device can overwrite kernel memory even though every process page table is correct.

Modern storage and network devices use rings of descriptors. Batching several completions into one interrupt reduces overhead and improves throughput. Waiting to fill a batch adds latency, so drivers tune queue depth and interrupt coalescing for the workload. Async I/O lets a process submit work, do something else and collect completions later instead of blocking one thread per request.

A container normally shares the host kernel. A mount namespace does not limit memory use. A memory cgroup does not hide host files. A syscall filter does not repair a dangerous file mount. Write down the attacker, the assets and the allowed operations, then map each risk to a specific boundary. Also decide what happens when a limit is reached: return an error, throttle work or terminate a process.

Fully emulating a device register by register works but can be slow. Paravirtual devices such as virtio give the guest and hypervisor a shared queue designed for virtualisation. Hardware virtualisation lets the guest run ordinary instructions directly and traps only operations the hypervisor must control. An IOMMU can safely assign a physical device or virtual function to a guest.

A proof connects a precisely stated model, assumptions and implementation property. The seL4 microkernel has machine-checked proofs that include functional-correctness results for its verified configurations. That does not prove every driver, application, compiler, circuit or deployment policy correct. Read the theorem and assumptions before repeating a claim. Testing samples executions; model checking explores a finite state model; deductive proof reasons from a specification. Strong systems use several kinds of evidence.

For a crash, preserve the build, configuration, input, logs and core dump. For a race, use stress tests, schedule perturbation and a race detector, then reason about the required ordering. For a protocol state machine, model checking can search every transition in a bounded model. Fuzzers generate many malformed inputs. A proof can cover all inputs under stated assumptions. None of these replaces a clear failure model.

A current coding model can suggest a trace query, summarise a large log or propose likely causes. Treat each result as a hypothesis. Keep raw evidence, check generated commands, minimise a reproducer and confirm the explanation with a counter or controlled change. Do not paste secrets, crash dumps or production memory into a service without permission. A plausible explanation is not a measurement.