rstubs::assignments

Module a2_interrupts

source
Expand description

§BSB - A2: Interrupts

StuBS needs interrupt handling, e.g., for the keyboard, and other stuff down the line. To configure the interrupts, StuBS will support the Advanced Programmable Interrupt Controller (APIC).

The path of a keyboard interrupt on x86 looks like this:

+---------+
| CPU 0   |
|         |
|   +-RIDT----> IDT[Vector] => handler
+---|-----+
| LAPIC 0 | <- EOI, Timer, IPI, ...
+----o----+
     |
---o-o------- ... Interrupt Bus
   |
 +-o------+
 | IOAPIC | <- Redirection Table
 +--o---o-+    (Device -> Vector)
   /     \
Keyboard  HDD ...

First the keyboard (at the bottom) talks to the IO “Advanced Programmable Interrupt Controllers” (IO APIC). If properly configured by the OS, it sends the interrupt to a CPU’s Local APIC (every CPU has its own LAPIC). This LAPIC again forwards the interrupt to its CPU. The CPU then uses its Interrupt Descriptor Table (IDT) to determine which function or “Interrupt Hander” should be called for the specific interrupt. This IDT is just a table with a lot of function pointers to the corresponding interrupt handler functions.

In this assignment, you have to program the IoApic and IDT. The low-level part of setting up LApic, as well as helper functions to enable/disable interrupts on the current core, are already implemented.

§Configuring the IDT

The IDT is a table of 256 entries, each entry containing a function pointer and some flags. The function pointer is called when the corresponding interrupt occurs. An abstraction for the IDT is already part of the template. In interrupts/idt.rs, you will find the IDT variable, which contains the actual IDT and a load() function to set up and load the IDT into the CPU.

  • All interrupts that are not handled or trigger faults during handling produce a double fault that can be handled. However, a triple fault will cause an immediate reboot.
  • Use the Vector enum to index the IDT (idt[Vector::Keyboard as usize]).

§Configuring the IO APIC

Modern PCs usually support xAPIC, having up to 24 external devices connected to the I/O APIC (you can even have multiple I/O APICs – although StuBS only supports the first one). During the boot process, interrupts are masked for each core and the I/O APIC.

Memory mapped IO
---------------------------------------------------
    .. | IOREGSEL | .. | IOWIN | ..
---------------------------------------------------
0xfec00000 |      +0x10 ___|___
           +-----------/_______\
                           |
--------------------------------------------------------
| IOAPICID | .. | RT[0] : RT[0]' | RT[1] : RT[1]' | ...
--------------------------------------------------------
0x0             0x10    0x11     0x12    0x13

Implement the functionality in IOAPIC to configure interrupts from external sources (IoApic::config_raw()). As device manufacturers are free to reconfigure which slot corresponds to which device, the boot process retrieves this information and stores it in the IoApic::overrides table. You can use the IoApic::slot() function to translate a Device to its corresponding slot index. Using this index, you can access the Redirection Table entries, shown above (IoApic::write()).

To test your implementation, you can configure and enable (level triggered) interrupts from the keyboard – since you have already configured the interrupt handler, which should be executed automatically if a key is pressed or released! However, because the characters are not fetched by the PS2Controller, you will continuously receive the interrupt until you empty the keyboard buffer by reading its content using PS2Controller::event().

Lastly, you have to initialize the IOAPIC once in interrupts::setup_gloabl().

  • As many HW registers have reserved bits that should not be changed, it is recommended to read->modify-write them.
  • While handling an interrupt, you don’t need to worry about unwanted interrupts. They are disabled on the corresponding core when the handler starts and are not enabled until it returns.
  • According to the specification (see ISDMv3, 10.8.5 Signaling Interrupt Servicing Completion), it is necessary to confirm the processing of each interrupt (EOI). To do this, call LApic::eoi() in the interrupt handler.
  • Depending on the environment, it may also be necessary to empty the keyboard buffer completely before activating interrupts.

§Changes to the Keyboard Driver

After each keystroke, the corresponding characters should be displayed on the screen. Allocate one line of your screen to display these characters. The key combination Ctrl-Alt-Delete should trigger a system reboot.

You can reuse the Keyboard implementation of assignment 1 but might have to change the PS2Controller::event() function if you wait in there. Also, you have to update your test application accordingly.

§Synchronization

Implement a test program in user.rs that prints an increasing number to the screen. It should be called by main() on every core, and each instance should print into another location (using Window::set_cursor()). On the first execution, you’ll see that the multi-core system does not even need interrupts to mess up the output (Think about why that is the case). To avoid these race conditions, the methods provided by cpu alone are not enough, as they only allow synchronization with interrupts.

Whenever we have concurrent access to shared data structures, we must think about synchronizing this access. Reading in parallel is usually safe, but if we have at least one writer, we must synchronize accesses. If not, we might read partially written data. Thus, we must ensure that only one CPU accesses a shared data structure at a time. This is done with mutual exclusion, e.g., by using locks.

Where exactly do we have race conditions here? To avoid them, you must implement a Spinlock (or Ticketlock) to synchronize parallel CPUs with one another. Are there dangers when we have multiple locks?

In Rust, we can use the RAII pattern to ensure that locks are released when they go out of scope. For this, we have an extra LockGuard type that is returned by the lock() function. This type implements the Drop trait, which is called when the lock guard goes out of scope, unlocking the lock.

use crate::util::Spin;

let lock = Spin::new(0);
{
    let guard = lock.lock();
    // lock is locked
    *guard += 1;
} // <- lock is unlocked

§Spinlock

Each architecture has a few safe atomic operations synchronized by the CPU. Based on these instructions, we can implement higher-level synchronization primitives.

The spin lock is the most basic lock, which uses a single atomic boolean to achieve mutual exclusion. Each CPU that wants to acquire the lock spins in a loop until it can set the boolean to true. Then, it can continue with the critical section. Afterwards, the CPU sets the boolean to false again, allowing other CPUs to acquire the lock.

§Ticketlock

The ticket lock is fairer than the spin lock, as it ensures that CPUs acquire the lock in the order they requested it. It uses two atomic integers to achieve mutual exclusion. Each CPU that wants to acquire the lock first increments the ticket number and then spins in a loop until the ticket number equals the serving number. Then, it can continue with the critical section. Afterwards, the CPU increments the serving number, allowing other CPUs to acquire the lock.