Interrupts

OS in Rust

Announcements

  • Action Items:
    • Welcome back.
    • You should have a working:
      • Breakpoint handler.
      • Double fault handler.

Citations

  • Hardware interrupts are awesome.
    • They open up a wide range of interesting algorithmic ideas.
  • Hardware Interrupts
  • Still tedious though!

Negation

  • Not to be confused with software interrupts.
  • Basically this is I/O week - the hardware could be a keyboard.

Recall: Exceptions

  • CPU exceptions occur in various erroneous situations
    • Accessing an invalid memory address
    • Dividing by zero
  • We have to set up an interrupt descriptor table..
  • This week, our kernel will be able to catch double faults.

Recall: Types

On x86, there are about 20 different CPU exception types.

  • None of them are hardware interrupts.
  • The keyboard and the CPU are not the same thing.

Interrupts

Polling

  • Let’s go over what interrupts aren’t.
  • I don’t leave my cell phone on, pretty much ever.
    • It is usually silent, dead battery, and I don’t know where it is.
    • If someone texts me, then I will get the text when I voluntarily check my phone.
  • This is called polling.

Definition

Polling is the process where the computer or controlling device waits for an external device to check for its readiness or state, often with low-level hardware. For example, when a printer is connected via a parallel port, the computer waits until the printer has received the next character. These processes can be as minute as only reading one bit.

Interrupts

  • Imagine you have a cell phone that you keep with you, charged, and with some sort of way of notifying you that it has received a message.
  • Then, whenever it receives a message, it interrupts whatever you are doing.
  • In that way it is like other “hardware” interrupts, like stubbing your toe, the lights turning off, or a lamborghini crashing into the classroom.

Usage

  • Interrupts provide a way to notify the CPU from attached hardware devices.
  • So instead of letting the kernel periodically check the keyboard for new characters (polling)…
  • …the keyboard can notify the kernel of each keypress.
  • This is much more efficient because the kernel only needs to act when something happened.

Trade-offs

For interrupts (vs. polling).

Pros Cons
Fast Response Can be distruptive
Less overall compute More overall complexity

Overview

  • A interrupt controller aggregates the interrupts:

G Timer Timer IC Interrupt Controller Timer->IC Keyboard Keyboard Keyboard->IC Hardware Other Hardware Hardware->IC CPU CPU IC->CPU

PIC

  • Enter the Programmable Interrupt Controller (PIC)
  • Most interrupt controllers are programmable, which means they support different priority levels for interrupts.
  • For example, this allows to give timer interrupts a higher priority than keyboard interrupts to ensure accurate timekeeping.

Asynchronous

  • Unlike exceptions, hardware interrupts occur asynchronously.
  • This means they are completely independent from the executed code.
    • Can occur at any time, including, for example between lines of code.
  • Thus, we suddenly have a form of concurrency in our kernel with all the potential concurrency-related bugs.

Blog claims:

  • Rust’s strict ownership model helps us here…
    • “Here” being with respect to interrupts.
  • …because it forbids mutable global state.
    • Oh that’s a strong claim.
  • Deadlocks are still possible.
    • When two entities reserve part of what they need and get stuck.

The 8259 PIC

  • The Intel 8259 is a programmable interrupt controller (PIC) introduced in 1976.
  • It has long been replaced by the newer APIC, but its interface is still supported on current systems for backwards compatibility reasons.
  • The 8259 PIC is significantly easier to set up than the APIC, so we will use it to introduce ourselves to interrupts.

History

  • The 8259 has eight interrupt lines and several lines for communicating with the CPU.
  • The typical systems back then were equipped with two instances of the 8259 PIC:
    • one primary and,
    • one secondary PIC, connected to one of the interrupt lines of the primary.

Visually

  • We see that most of the 15 lines have a fixed mapping.
  • E.g., (zero indexed) line 4 of the secondary PIC is assigned to the mouse.

Configuration

  • Each controller can be configured through two I/O ports
    • So, port-mapped
    • By configured we mean “programmed”
    • One “command” port and one “data” port.
  • For the primary controller, these ports are 0x20 (command) and 0x21 (data).
  • For the secondary controller, they are 0xa0 (command) and 0xa1 (data).

Collisions

  • Remember this:
    • On x86, there are about 20 different CPU exception types.
      • None of them are hardware interrupts.
      • The keyboard and the CPU are not the same thing.
  • We have a collision in our key-value association.

Defaults

  • By default PICs send interrupt vector numbers in the range of 0–15 to the CPU.
  • These numbers collide with (the first 0x20) CPU exceptions.
  • E.g., 8 corresponds to a double fault in the CPU and Serial Port 1 in the PIC.
  • Remap the PIC interrupts to different numbers.

Conventions

  • The actual remap range doesn’t matter.
    • It’s programmable, after all.
    • But it must not overlap with the exceptions.
  • Typically the range of 32–47 is chosen, because these are the first free numbers after the 32 exception slots.

Cheating

pic8259/0.10.1/source/src/lib.rs
#![no_std]
use x86_64::instructions::port::Port;

const CMD_INIT: u8 = 0x11;
const CMD_END_OF_INTERRUPT: u8 = 0x20;
const MODE_8086: u8 = 0x01;

struct Pic {
    offset: u8,
    command: Port<u8>,
    data: Port<u8>,
}

impl Pic {
    fn handles_interrupt(&self, interupt_id: u8) -> bool {
        self.offset <= interupt_id && interupt_id < self.offset + 8
    }

    unsafe fn end_of_interrupt(&mut self) {
        self.command.write(CMD_END_OF_INTERRUPT);
    }

    unsafe fn read_mask(&mut self) -> u8 {
        self.data.read()
    }

    unsafe fn write_mask(&mut self, mask: u8) {
        self.data.write(mask)
    }
}

pub struct ChainedPics {
    pics: [Pic; 2],
}

impl ChainedPics {
    pub const unsafe fn new(offset1: u8, offset2: u8) -> ChainedPics {
        ChainedPics {
            pics: [
                Pic {
                    offset: offset1,
                    command: Port::new(0x20),
                    data: Port::new(0x21),
                },
                Pic {
                    offset: offset2,
                    command: Port::new(0xA0),
                    data: Port::new(0xA1),
                },
            ],
        }
    }

    pub unsafe fn initialize(&mut self) {
        let mut wait_port: Port<u8> = Port::new(0x80);
        let mut wait = || wait_port.write(0);

        let saved_masks = self.read_masks();

        self.pics[0].command.write(CMD_INIT);
        wait();
        self.pics[1].command.write(CMD_INIT);
        wait();

        self.pics[0].data.write(self.pics[0].offset);
        wait();
        self.pics[1].data.write(self.pics[1].offset);
        wait();

        self.pics[0].data.write(4);
        wait();
        self.pics[1].data.write(2);
        wait();

        self.pics[0].data.write(MODE_8086);
        wait();
        self.pics[1].data.write(MODE_8086);
        wait();

        self.write_masks(saved_masks[0], saved_masks[1])
    }

    pub unsafe fn read_masks(&mut self) -> [u8; 2] {
        [self.pics[0].read_mask(), self.pics[1].read_mask()]
    }

    pub unsafe fn write_masks(&mut self, mask1: u8, mask2: u8) {
        self.pics[0].write_mask(mask1);
        self.pics[1].write_mask(mask2);
    }

    pub unsafe fn disable(&mut self) {
        self.write_masks(u8::MAX, u8::MAX)
    }

    pub fn handles_interrupt(&self, interrupt_id: u8) -> bool {
        self.pics.iter().any(|p| p.handles_interrupt(interrupt_id))
    }

    pub unsafe fn notify_end_of_interrupt(&mut self, interrupt_id: u8) {
        if self.handles_interrupt(interrupt_id) {
            if self.pics[1].handles_interrupt(interrupt_id) {
                self.pics[1].end_of_interrupt();
            }
            self.pics[0].end_of_interrupt();
        }
    }
}

Let’s Cheat

  • We’ve added crates before.
Cargo.toml
[dependencies]
pic8259 = "0.10.1"
  • Read more: pic8259
  • My Cargo.toml is growing quite large.
$ wc Cargo.toml
 20  44 381 Cargo.toml

How I did it

  • I just appended to the end of src/interrupts.rs
  • I use “ChainedPics”, the main thing the crate provides.
src/interrupts.rs
// PIC

pub const PIC_1_OFFSET: u8 = 32;
pub const PIC_2_OFFSET: u8 = PIC_1_OFFSET + 8;

pub static mut PICS: pic8259::ChainedPics =
    unsafe { pic8259::ChainedPics::new(PIC_1_OFFSET, PIC_2_OFFSET) };

An Aside

  • Up until now, I have taken the liberty of not implementing an mutex in our OS.
    • Stands for “MUTual EXclusion”
    • Used to prevent different… things (threads)… from modifying the same shared state at the same time.
    • This can lead to program inconsistencies… but not in our case yet.

On the Mutex

  • Up until now, it hasn’t mattered - all our code executed serially (one thing at a time) and linearly (in a defined order).
  • We are now about to enter the “Cool Zone”
    • But I still won’t mutex yet until we see a better way to do it.

Back at it

  • We also initialize our PIC.
  • I did in interrupts::init_idt()
  • Some double fault handler stuff too…
src/interrupts.rs
pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        IDT.double_fault
            .set_handler_fn(double_fault_handler)
            .set_stack_index(crate::gdt::DOUBLE_FAULT_IST_INDEX as u16);
        IDT.load();
        PICS.initialize();
    }
}

Enabling Interrupts

  • Until now, interrupts were disabled in the CPU configuration.
  • So no interrupts can reach the CPU.
  • Let’s change that…
src/interrupts.rs
pub fn init_idt() {
    unsafe {
        // Snip
        PICS.initialize();
        x86_64::instructions::interrupts::enable();
    }
}

I bet that works!

  • It double faults.
    • This is good!
    • We’ve changed something.
    • The first step to changing something we want to change!

Why?

  • The hardware timer (the Intel 8253, to be exact) is enabled by default.
  • So we start receiving timer interrupts as soon as we enable interrupts.
  • Since we didn’t define a handler function for it yet, our double fault handler is invoked.
  • Absolute geniuses will notice that we can now do things using timers, though.

Remember this?

How about this part?

  • That’s a timer on line 0 of the primary PIC.
  • We offset by… it doesn’t matter, it was a pub const

An Aside

  • We can use an enum to specify the index of a given hardware interrupt in the PIC.
src/interrupts.rs
pub enum InterruptIndex {
    Timer = PIC_1_OFFSET,
}
  • This explodes, for a reason I complain about often.
error[E0308]: mismatched types
  --> src/interrupts.rs:51:13
   |
51 |     Timer = PIC_1_OFFSET,
   |             ^^^^^^^^^^^^ expected `isize`, found `u8`

Set repr

  • We can just tell Rust to use u8 because doing so would’ve been a sensible default.
src/interrupts.rs
#[repr(u8)]
pub enum InterruptIndex {
    Timer = PIC_1_OFFSET,
}
  • Rust: It’s good.
  • This does not at all encourage me to just not use enum and use magic numbers, at all.

Write a handler

  • I just used the breakpoint handler, but changed the print.
src/interrupts.rs
extern "x86-interrupt" fn timer_handler (
    stack_frame: x86_64::structures::idt::InterruptStackFrame,
) {
    crate::println!("INTERRUPT: TIMER\n{:#?}", stack_frame);
}

Set the handler

  • Nothing too fancy setting this within the IDT, just have to get the index right.
src/interrupts.rs
IDT[InterruptIndex::Timer as usize].set_handler_fn(timer_handler);
  • Make sure you include this line prior to loading the IDT.
    • Don’t ask why I made this note!

What do we expect

  • In theory, the timer should go off every so often.
  • We already know it seems to go off instantly, so probably quite often.
  • So we should see a few errors messages pop up right away… right?

Wrong!

  • The PIC expects an explicit “end of interrupt” (EOI) signal from our interrupt handler.
  • This signal tells the controller that the interrupt was processed and that the system is ready to receive the next interrupt.
  • So the PIC thinks we’re still busy processing the first timer interrupt and waits patiently for the EOI signal before sending the next one.

Easy fix

  • We simply update our PIC with the handy, built-in .notify_end_of_interrupt.
    • Rust crate creators: Thank you for writing our OS.
    • (We are still learning how OSes work, mind you!)

Code it up

  • I have no idea why cargo fmt but the arguments back on one line.
src/interrupts.rs
extern "x86-interrupt" fn timer_handler(stack_frame: x86_64::structures::idt::InterruptStackFrame) {
    crate::println!("INTERRUPT: TIMER\n{:#?}", stack_frame);
    unsafe { PICS.notify_end_of_interrupt(InterruptIndex::Timer as u8) };
}
  • I think of this as very close to being a “hardware level function return”

What’s Happening?

  • If you try it out, you will now get many timer interrupts.
  • The notify_end_of_interrupt:
    • Figures out whether the primary or secondary PIC sent the interrupt, then
    • Uses the command and data ports to
    • Send an EOI signal to the respective controllers.

A Race

2 Fast 2 Furious

  • We are now able to run multiple functions, or contexts, simultaneously.
    • We run whatever code is in _start, and…
    • We run whatever code is in the timer handler.
  • An obviously fun thing to do is print infinitely in both places.
    • We are already doing that with the timer, basically…

Infinite Worlds

  • It suffices to move our “Hello, world!” into the infinite loop for the purposes of this exercise.
src/main.rs
#[unsafe(no_mangle)]
pub extern "C" fn _start() -> ! {
    osirs::init();
    loop { println!("Hello, world{}", "!"); }
}
  • Run your OS quickly. What do you see?

Handwaving

  • Aw, they’re sharing!
  • I am going to handwave concurrency into what I hope to be a future networks class.
  • It’s a very interesting cloud topic, and in generally we won’t mind it too much here.
  • All we have to do at this time is establish a perhaps more reasonable timer handler.
src/interrupts.rs
extern "x86-interrupt" fn timer_handler(stack_frame: x86_64::structures::idt::InterruptStackFrame) {
    // crate::println!("INTERRUPT: TIMER\n{:#?}", stack_frame);
    unsafe { PICS.notify_end_of_interrupt(InterruptIndex::Timer as u8) };
}

Benefits

Timing Considerations

  • But there are some quick performance gains to be had here…
  • Until now, our loop {}’s gobbled up all available resources.
    • CPU time
    • CPU energy
    • Hydroelectric power
  • With multiple infinities around, we should be more considerate.

Halt!

  • With loop {} the CPU continues to run at full speed even though there’s no work to do.
  • What we really want to do is to halt the CPU until the next interrupt arrives.
  • This allows the CPU to enter a sleep state in which it consumes much less energy.
  • There is a hardware level “halt” command that does exactly that!
  • Read more on HLT

Try it

  • Let’s use this instruction to create an energy-efficient endless loop:
src/lib.rs
pub fn halt() -> ! {
    loop { x86_64::instructions::hlt(); }
}
  • This is helpfully diverging, so add to:
    • _start and panic in src/main.rs
    • Not needed when testing. (Why?)

Fin

Okay…

  • I think we are out of time here.
  • Coming up next in OS in Rust: Keyboard interrupts!

TODO

Keyboard Input

Now that we are able to handle interrupts from external devices, we are finally able to add support for keyboard input. This will allow us to interact with our kernel for the first time.

Like the hardware timer, the keyboard controller is already enabled by default. So when you press a key, the keyboard controller sends an interrupt to the PIC, which forwards it to the CPU. The CPU looks for a handler function in the IDT, but the corresponding entry is empty. Therefore, a double fault occurs.

So let’s add a handler function for the keyboard interrupt. It’s quite similar to how we defined the handler for the timer interrupt; it just uses a different interrupt number:

// in src/interrupts.rs

#[derive(Debug, Clone, Copy)]
#[repr(u8)]
pub enum InterruptIndex {
    Timer = PIC_1_OFFSET,
    Keyboard, // new
}

lazy_static! {
    static ref IDT: InterruptDescriptorTable = {
        let mut idt = InterruptDescriptorTable::new();
        idt.breakpoint.set_handler_fn(breakpoint_handler);
        […]
        // new
        idt[InterruptIndex::Keyboard.as_usize()]
            .set_handler_fn(keyboard_interrupt_handler);

        idt
    };
}

extern "x86-interrupt" fn keyboard_interrupt_handler(
    _stack_frame: InterruptStackFrame)
{
    print!("k");

    unsafe {
        PICS.lock()
            .notify_end_of_interrupt(InterruptIndex::Keyboard.as_u8());
    }
}

As we see from the graphic above, the keyboard uses line 1 of the primary PIC. This means that it arrives at the CPU as interrupt 33 (1 + offset 32). We add this index as a new Keyboard variant to the InterruptIndex enum. We don’t need to specify the value explicitly, since it defaults to the previous value plus one, which is also 33. In the interrupt handler, we print a k and send the end of interrupt signal to the interrupt controller.

We now see that a k appears on the screen when we press a key. However, this only works for the first key we press. Even if we continue to press keys, no more ks appear on the screen. This is because the keyboard controller won’t send another interrupt until we have read the so-called scancode of the pressed key.

Reading the Scancodes

To find out which key was pressed, we need to query the keyboard controller. We do this by reading from the data port of the PS/2 controller, which is the I/O port with the number 0x60:

// in src/interrupts.rs

extern "x86-interrupt" fn keyboard_interrupt_handler(
    _stack_frame: InterruptStackFrame)
{
    use x86_64::instructions::port::Port;

    let mut port = Port::new(0x60);
    let scancode: u8 = unsafe { port.read() };
    print!("{}", scancode);

    unsafe {
        PICS.lock()
            .notify_end_of_interrupt(InterruptIndex::Keyboard.as_u8());
    }
}

We use the Port type of the x86_64 crate to read a byte from the keyboard’s data port. This byte is called the scancode and it represents the key press/release. We don’t do anything with the scancode yet, other than print it to the screen:

QEMU printing scancodes to the screen when keys are pressed

The above image shows me slowly typing “123”. We see that adjacent keys have adjacent scancodes and that pressing a key causes a different scancode than releasing it. But how do we translate the scancodes to the actual key actions exactly?

Interpreting the Scancodes

There are three different standards for the mapping between scancodes and keys, the so-called scancode sets. All three go back to the keyboards of early IBM computers: the IBM XT, the IBM 3270 PC, and the IBM AT. Later computers fortunately did not continue the trend of defining new scancode sets, but rather emulated the existing sets and extended them. Today, most keyboards can be configured to emulate any of the three sets.

By default, PS/2 keyboards emulate scancode set 1 (“XT”). In this set, the lower 7 bits of a scancode byte define the key, and the most significant bit defines whether it’s a press (“0”) or a release (“1”). Keys that were not present on the original IBM XT keyboard, such as the enter key on the keypad, generate two scancodes in succession: a 0xe0 escape byte and then a byte representing the key. For a list of all set 1 scancodes and their corresponding keys, check out the OSDev Wiki.

To translate the scancodes to keys, we can use a match statement:

// in src/interrupts.rs

extern "x86-interrupt" fn keyboard_interrupt_handler(
    _stack_frame: InterruptStackFrame)
{
    use x86_64::instructions::port::Port;

    let mut port = Port::new(0x60);
    let scancode: u8 = unsafe { port.read() };

    // new
    let key = match scancode {
        0x02 => Some('1'),
        0x03 => Some('2'),
        0x04 => Some('3'),
        0x05 => Some('4'),
        0x06 => Some('5'),
        0x07 => Some('6'),
        0x08 => Some('7'),
        0x09 => Some('8'),
        0x0a => Some('9'),
        0x0b => Some('0'),
        _ => None,
    };
    if let Some(key) = key {
        print!("{}", key);
    }

    unsafe {
        PICS.lock()
            .notify_end_of_interrupt(InterruptIndex::Keyboard.as_u8());
    }
}

The above code translates keypresses of the number keys 0-9 and ignores all other keys. It uses a match statement to assign a character or None to each scancode. It then uses if let to destructure the optional key. By using the same variable name key in the pattern, we shadow the previous declaration, which is a common pattern for destructuring Option types in Rust.

Now we can write numbers:

QEMU printing numbers to the screen

Translating the other keys works in the same way. Fortunately, there is a crate named pc-keyboard for translating scancodes of scancode sets 1 and 2, so we don’t have to implement this ourselves. To use the crate, we add it to our Cargo.toml and import it in our lib.rs:

# in Cargo.toml

[dependencies]
pc-keyboard = "0.7.0"

Now we can use this crate to rewrite our keyboard_interrupt_handler:

// in/src/interrupts.rs

extern "x86-interrupt" fn keyboard_interrupt_handler(
    _stack_frame: InterruptStackFrame)
{
    use pc_keyboard::{layouts, DecodedKey, HandleControl, Keyboard, ScancodeSet1};
    use spin::Mutex;
    use x86_64::instructions::port::Port;

    lazy_static! {
        static ref KEYBOARD: Mutex<Keyboard<layouts::Us104Key, ScancodeSet1>> =
            Mutex::new(Keyboard::new(ScancodeSet1::new(),
                layouts::Us104Key, HandleControl::Ignore)
            );
    }

    let mut keyboard = KEYBOARD.lock();
    let mut port = Port::new(0x60);

    let scancode: u8 = unsafe { port.read() };
    if let Ok(Some(key_event)) = keyboard.add_byte(scancode) {
        if let Some(key) = keyboard.process_keyevent(key_event) {
            match key {
                DecodedKey::Unicode(character) => print!("{}", character),
                DecodedKey::RawKey(key) => print!("{:?}", key),
            }
        }
    }

    unsafe {
        PICS.lock()
            .notify_end_of_interrupt(InterruptIndex::Keyboard.as_u8());
    }
}

We use the lazy_static macro to create a static Keyboard object protected by a Mutex. We initialize the Keyboard with a US keyboard layout and the scancode set 1. The HandleControl parameter allows to map ctrl+[a-z] to the Unicode characters U+0001 through U+001A. We don’t want to do that, so we use the Ignore option to handle the ctrl like normal keys.

On each interrupt, we lock the Mutex, read the scancode from the keyboard controller, and pass it to the add_byte method, which translates the scancode into an Option<KeyEvent>. The KeyEvent contains the key which caused the event and whether it was a press or release event.

To interpret this key event, we pass it to the process_keyevent method, which translates the key event to a character, if possible. For example, it translates a press event of the A key to either a lowercase a character or an uppercase A character, depending on whether the shift key was pressed.

With this modified interrupt handler, we can now write text:

Typing “Hello World” in QEMU

Configuring the Keyboard

It’s possible to configure some aspects of a PS/2 keyboard, for example, which scancode set it should use. We won’t cover it here because this post is already long enough, but the OSDev Wiki has an overview of possible configuration commands.

Summary

This post explained how to enable and handle external interrupts. We learned about the 8259 PIC and its primary/secondary layout, the remapping of the interrupt numbers, and the “end of interrupt” signal. We implemented handlers for the hardware timer and the keyboard and learned about the hlt instruction, which halts the CPU until the next interrupt.

Now we are able to interact with our kernel and have some fundamental building blocks for creating a small shell or simple games.

What’s next?

Timer interrupts are essential for an operating system because they provide a way to periodically interrupt the running process and let the kernel regain control. The kernel can then switch to a different process and create the illusion of multiple processes running in parallel.

But before we can create processes or threads, we need a way to allocate memory for them. The next posts will explore memory management to provide this fundamental building block.