Operating Systems #6 — Traps and System Calls in xv6

Lecture taught that invoking a system call causes a trap and flips the mode bit to kernel mode. Lab is where you go find that in the xv6 source.

Three ways into kernel mode

Control transfers from user mode to kernel mode in three cases.

• System call — the user asks the OS for a service.
• Exception — the user program does something invalid: touching a bad memory address, dividing by zero. The transfer happens because the OS has to clean up after the program.
• Interrupt — an event telling the OS something happened, usually a device signalling that it wants attention.

All three are handled through interrupt handling.

An interrupt is a signal sent to the processor when hardware or software needs attention right now. An instruction is processed in three stages — fetch, decode, execute — and if an interrupt has occurred by the check-interrupt stage, the current state (registers and so on) is saved onto the running process's stack. Then the interrupt is identified and control jumps to the ISR (interrupt service routine). Saving the registers first is what makes returning to the original flow possible.

To do interrupt handling, the OS has to support four things:

1. Save the processor's current register values.
2. Prepare to run in kernel mode, since interrupts must execute there.
3. Be able to receive information about which interrupt this is.
4. Maintain proper isolation between user and kernel. Interrupts run in kernel mode, so user programs must not be able to interfere with the kernel.

int n and the registers

The first instruction executed when an interrupt is taken is int n, which raises interrupt number n.

• eip — holds the address of the next instruction to execute.
• esp — holds the address at the end of a stack frame, i.e. where the next datum will be stored. As data is pushed, esp decreases. Draw the address space top to bottom and it's natural.

Push order in a stack frame

If main called sum(num1, num2, num3), the pushes go num3, num2, num1, return address. So num3 sits at the highest address and the return address at the lowest.

To read num2 out of the frame (assuming ints), read at esp + 4 + 2*4. Data is written from lower to higher addresses, so num2 occupies esp + 4 + 2*4 through that plus three.

The IDT and tvinit

Each interrupt has its own entry point — the address where it actually starts. The table holding those addresses is the IDT (Interrupt Descriptor Table).

On boot, main.c calls tvinit(), short for trap vector init; a trap vector is an interrupt's entry point. tvinit() fills the IDT with trap vectors. The vectors themselves are defined in vectors.S, an array holding, for each trap number, the address of a short piece of assembly. It's generated by make.

When the int n instruction completes, eip is set to that address.

On terminology: an interrupt is a change in flow from hardware (interrupt in the general sense), and a trap is a change in flow from software. A system call counts as a software interrupt. And you can create a new interrupt in an empty IDT slot — something Project 1 actually makes use of.

CPL and DPL

x86 has privilege levels indicating how much access the currently running process has. xv6 only uses 0 (kernel mode) and 3 (user mode). Smaller numbers mean more privilege.

• CPL (Current Privilege Level) — two bits in the cs register, giving the current privilege level.
• DPL (Descriptor Privilege Level) — the minimum privilege required to take the interrupt for int n. It lives in the IDT.

So the service is only performed if CPL is numerically less than or equal to DPL. When a process running in user mode switches to kernel mode, CPL is set to 0. If DPL is 0, only processes with CPL 0 can get in.

Look at tvinit() and the last argument to SETGATE is the DPL: every interrupt is set to DPL = 0 except the last line, where T_SYSCALL gets DPL_USER (3). Because the system call is the one that must be callable from user mode.

What int n does

1. Fetch the nth descriptor from the IDT.
2. Check that the CPL in cs is less than or equal to the DPL in the IDT.
3. If the DPL is more privileged than the CPL, the level has to move user → kernel. That's the case where the interrupt was raised in user mode; raised in kernel mode, no level change is needed.

alltraps

When int n completes, every handler jumps to alltraps. In xv6 every ISR calls alltraps. alltraps pushes the CPU registers onto the stack frame and calls trap. The registers it saves are what builds the stack frame trap needs.

From a user program to a system call

From the lab — one question had us confirm that copying the code of a system call function and running it in user mode doesn't get the system call to run properly.

usys.S is a macro. Calling the function in user mode invokes SYSCALL(name). And from what came later: invoking a system call executes int 64, and through SETGATE entry 64 has DPL 3 so that interrupt handling is reachable from user mode too.

So copying system call code into user space doesn't get you anything. You have to pass through the gate into kernel mode, and that gate is entry 64, opened at DPL 3. "System calls are OS code, with different privileges" from the lecture shows up here as actual code.

The xv6 boot sequence

From the lab — one question asked for the full xv6 boot process in detail.

1. When xv6 boots, a program called the BIOS starts first.
2. The BIOS checks the hardware and loads the boot block from disk into memory. The boot block is the first 512 bytes of the boot disk. It contains the boot loader, the instructions that load the kernel into memory. The boot loader consists of bootasm.S and bootmain.c.
3. Once the boot block is in memory, the BIOS jumps to the boot loader's address, setting eip to 0x7c00 — the address of the boot loader's start function.
4. bootmain jumps to the kernel's entry point.
5. main() initializes some devices and subsystems and creates the first process.
6. kinit1() adds the pages from the end virtual address of the kernel image (end) up to 4MB to the free list. These pages get allocated by kalloc between kvmalloc() and startothers().
7. kvmalloc() builds the kernel page table and switches to it.
8. tvinit() initializes the IDT — the function from earlier in this post.
9. kinit2() adds the pages from 4MB up to PHYSTOP to the free list.
10. userinit() creates the first process.

This is where you see where tvinit() falls in the boot flow: set up half the page allocator, build the kernel page table, and then get ready to receive interrupts.