Part IV · Chapter 12

Interrupts

Polling means asking a device "are you ready yet?" over and over. Interrupts turn that around: the processor gets on with its work, and the device taps it on the shoulder when it needs attention. This one idea is behind responsive keyboards, smooth music, and the ability to run many programs at once.

Think about the doorbell. Without one, you'd have to walk to the front door every minute to check whether anyone was there. You'd get nothing else done, and you'd still keep visitors waiting. With a doorbell, you just get on with your day, and when it rings you stop what you're doing, answer the door, and then go back to exactly where you left off.

An interrupt is a doorbell for the processor.

How an interrupt works

Each device gets a wire to the processor, called an interrupt request line, or IRQ. When the keyboard has a new key, it raises its IRQ line. That's all the device does.

The processor checks that line between every two instructions. Remember the fetch, decode, execute cycle from Chapter 6? Interrupts add one small step to it: "before fetching the next instruction, is anyone ringing?" If so, the processor:

Finishes the instruction it's working on.
Saves its place: the address of the next instruction and its flags, pushed onto the stack.
Turns further interrupts off for the moment.
Jumps to a special piece of code for that device, the interrupt handler (also called an interrupt service routine).

The handler talks to the device (reading the key from port 0x60, say), and ends with a special return instruction, iretq on x86-64. It takes the saved place and flags back off the stack, and the interrupted program carries on exactly where it stopped. It never even knows it was interrupted.

Press Run, then Press a key a few times. Watch the CPU save its place, run the handler, and come back. Then untick Handler saves RAX and keep pressing keys: sooner or later the counter will jump. (It happens when the key arrives between the load and the store.)

Leave everything as you found it

The second experiment shows the golden rule of interrupt handlers. An interrupt can strike between any two instructions of the main program, and that program has no idea it's coming. So the handler must leave every register exactly as it found it. The processor saves the bare minimum, its place and its flags. Everything else the handler touches, it must save first and restore at the end, usually by pushing it on the stack.

Break that rule and you get the worst kind of bug: one that shows up only now and then, when an interrupt happens to land in exactly the wrong spot, and can't be reproduced on demand.

Sometimes the main program also needs a moment of peace, for example while it updates something the handler also uses. It can briefly switch interrupts off: cli ("clear interrupt flag") and sti ("set interrupt flag") on x86. Requests that arrive meanwhile simply wait. There's one exception: the non-maskable interrupt (NMI), a separate line kept for emergencies like hardware failures, which can't be switched off.

Which device? The vector table

A computer has many devices, and each needs its own handler. So every interrupt gets a number, its vector, and memory holds a table with the address of the handler for each number: the interrupt vector table.

On the IBM PC, the table sits at the very bottom of memory, from address 0 to 0x3FF: 256 entries of 4 bytes each. The timer is vector 8 and the keyboard vector 9, so the address of the keyboard handler lives at bytes 0x24 to 0x27. Anyone can change it, which is how DOS programs of the 1980s added their own features: they replaced the keyboard vector with their own handler, which looked for a special "hot key" and passed everything else on to the original.

On x86-64 the table is called the interrupt descriptor table (IDT): still 256 entries, now 16 bytes each, and it can live anywhere in memory. The operating system tells the processor where with the lidt instruction. RISC-V keeps things simpler: a register called mtvec (or stvec for the operating system) holds the address of a single handler, and another register, mcause, tells it why it was called.

The interrupt controller

The 8088 had just one ordinary interrupt input (plus the NMI). To connect eight devices, the IBM PC used a helper chip, the Intel 8259A programmable interrupt controller (PIC), sitting at I/O ports 0x20 and 0x21. It has eight IRQ inputs and does three jobs:

Priority: if several devices ring at once, the lowest IRQ number goes first. The timer, IRQ 0, beats everyone.
Masking: the operating system can silence any line by setting its bit in the mask register.
Telling the CPU who it was: when the processor accepts the interrupt, the PIC hands it the vector number, here 8 plus the IRQ number.

The PIC also remembers which interrupt is being handled ("in service"). Until the handler says it's done by writing the end of interrupt command, 0x20, to port 0x20, the PIC holds back that line and any less important ones. That's the out 0x20, al in our keyboard handler.

Raise the keyboard (IRQ 1) and COM1 (IRQ 4) together, and let the CPU accept. Then, with the keyboard still in service, raise the timer (IRQ 0): it can interrupt the keyboard handler, but COM1 has to wait. Also try masking a line.

Eight lines soon weren't enough. The IBM PC/AT of 1984 added a second 8259A, chained into IRQ 2 of the first, for 15 usable lines. Today's PCs use the APIC ("advanced PIC"): one small controller inside each processor core, plus one for the motherboard's devices, so interrupts can be sent to whichever core is best placed to handle them. Modern PCI Express devices don't even use wires: they signal an interrupt by writing a small message to a special memory address, called a message-signaled interrupt (MSI). Memory-mapped I/O in reverse! RISC-V systems use a controller called the PLIC, which you saw at address 0x0C000000 in the last chapter's memory map.

The timer: a heartbeat

IRQ 0, the most important line of all, doesn't come from a keyboard or a disk. It comes from a timer chip, the Intel 8253 at ports 0x40 to 0x43. It counts down from a number you choose, at 1,193,182 ticks per second, and raises IRQ 0 each time it reaches zero. The PC's BIOS set it to count down from 65,536, so it interrupted about 18.2 times a second. That was the PC's clock: DOS kept the time of day by counting those ticks.

But the timer interrupt does something far more important. Every time it fires, the operating system gets control back, whatever the running program is doing, even if it's stuck in an endless loop. That gives the operating system the chance to switch to another program. Do this fast enough, and many programs seem to run at the same time.

Three programs share one processor, and one of them has a bug: it loops forever. Run it without a timer interrupt, then with one.

Without the timer, each program has to give the CPU back voluntarily. That's called cooperative multitasking, and Windows 3.1 and the classic Mac OS worked this way: one misbehaving program could freeze the whole computer. With the timer, the operating system takes the CPU back by force, called preemptive multitasking, which every modern operating system uses. We'll see how it chooses who runs next in Chapter 20.

The timer also lets an idle computer save power. When there's nothing to do, the operating system runs the hlt instruction (wfi, "wait for interrupt", on RISC-V), and the processor sleeps until the next interrupt wakes it up.

Interrupts from inside: exceptions

Devices aren't the only things that can interrupt a program. Sometimes the processor itself runs into a problem with an instruction, and uses the very same mechanism to call for help. These are called exceptions:

Divide error (x86 vector 0): dividing by zero.
Invalid opcode (vector 6): the bytes don't form a valid instruction.
Page fault (vector 14): the MMU couldn't translate an address. This is how the page faults of Chapter 10 reach the operating system.
Breakpoint (vector 3): the one-byte int3 instruction, which debuggers write over an instruction to stop a program right there.

Programs can even interrupt themselves on purpose, to ask the operating system for a service: syscall on x86-64, ecall on RISC-V. That's how every program opens files or prints text, and it's the subject of Chapter 20. x86 reserves vectors 0 to 31 for exceptions. RISC-V calls interrupts and exceptions together traps, and the top bit of mcause says which kind it was.

Meanwhile, inside a real CPU

Here is a keyboard handler in x86-64 assembly, like the one in our demo:

; x86-64: keyboard interrupt handler
keyboard:
        push    rax             ; save every register we use
        in      al, 0x60        ; read the scan code
        mov     [key], al       ; keep it for later
        mov     al, 0x20
        out     0x20, al        ; tell the PIC: end of interrupt
        pop     rax             ; put RAX back exactly as it was
        iretq                   ; return to the interrupted program

On x86-64, the processor saves a little more than our demo shows: on entering a handler it pushes five values (the stack position and segment, the flags, and the code segment and address), and iretq pops all five. RISC-V doesn't use the stack at all. It copies the interrupted address into the register mepc, writes the reason into mcause, and jumps to the address in mtvec:

# RISC-V: the start and end of a trap handler
trap:   csrr    t0, mcause      # why are we here?
        bltz    t0, interrupt   # top bit set: an interrupt, not an exception
        # ... handle the exception ...
        mret                    # return to the address saved in mepc

(A real handler first saves any register it uses, including t0.) The control instructions are tiny:

fa              cli             ; interrupts off
fb              sti             ; interrupts on
f4              hlt             ; sleep until the next interrupt
cc              int3            ; breakpoint
48 cf           iretq           ; return from interrupt
30200073        mret            # RISC-V: return from trap
10500073        wfi             # RISC-V: wait for interrupt

On Linux, /proc/interrupts counts every interrupt since the computer started. Here are a few lines from the computer this book was written on, after 11½ days running, with the counts of its 20 processor cores added together:

$ cat /proc/interrupts         (trimmed, cores added up)
146:      40,327,475   PCI-MSI   xhci_hcd       ← USB: keyboard, mouse…
154:      10,792,639   PCI-MSI   ahci           ← SATA disks
155:      25,119,408   PCI-MSIX  enp4s0         ← wired network
156:      90,228,125   PCI-MSI   i915           ← Intel graphics
174:          21,751   PCI-MSI   snd_hda_intel  ← sound
LOC:   1,650,171,829             Local timer interrupts

Every device here uses message-signaled interrupts. And that's 1.65 billion timer interrupts: about 83 per second for each core. Linux can tick up to 1,000 times a second, but it lets idle cores skip ticks to save power.

Try it yourself

On the IBM PC, the keyboard uses vector 9. At which memory addresses is the address of its handler stored?
Show answer
Each entry is 4 bytes, so entry 9 starts at 9 × 4 = 36 = 0x24 and covers bytes 0x24 to 0x27.
The timer counts at 1,193,182 ticks per second. What number should it count down from to interrupt about 1,000 times a second?
Show answer
1,193,182 / 1,000 ≈ 1,193. Counting down from 1,193 gives 1,193,182 / 1,193 ≈ 1,000.15 interrupts per second.
In the interrupt controller demo, IRQ 3 and IRQ 6 are both waiting. Which is passed to the CPU first? What if IRQ 3 is masked?
Show answer
IRQ 3: the lower number has the higher priority. If it's masked, the controller ignores it and passes on IRQ 6 instead. IRQ 3's request is remembered and will be delivered once it's unmasked.
Why did the counter jump when the handler didn't save RAX, but only sometimes?
Show answer
The main program keeps the counter in RAX between loading it and storing it back. If the interrupt arrives in that window, the handler overwrites RAX with the scan code and 0x20, and the main program then stores the wrong value. If the interrupt arrives at any other moment, RAX isn't holding anything important, so nothing goes wrong.
Why can't one buggy program freeze a computer that uses preemptive multitasking?
Show answer
Because the timer interrupt doesn't depend on the program's cooperation. However the program loops, the timer still fires, the processor jumps to the operating system's handler, and the operating system can give the CPU to someone else (or end the buggy program).

What we learned

An interrupt lets a device signal the processor instead of being polled.
Between instructions, the processor checks for interrupts, saves its place, runs a handler, and returns with iretq or mret.
Handlers must restore every register they use; cli/sti switch interrupts off and on.
A vector table maps interrupt numbers to handlers; an interrupt controller sorts out priorities and masks.
The timer interrupt keeps time and lets the operating system take the CPU back: preemptive multitasking.
Exceptions (divide errors, page faults, breakpoints) and system calls use the same mechanism.

Interrupts free the processor from waiting. But it still has to move every byte itself: a disk delivering a whole file would interrupt it for each tiny piece. In the next chapter we'll meet DMA, which lets devices copy data into memory on their own, and the modern buses, PCI Express and USB, that connect them.