Double

OS in Rust

Announcements

  • Action Items:
    • Testing done.
    • First handler assigned, more to come.

Citations

  • CPU exceptions are algorithmically interesting but technically tedious.
  • Double Faults

Negation

  • Not to be confused with the double type.
  • That is floating point type and has no place in an OS class.

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.

Types

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

  • Double Fault: When an exception occurs, the CPU tries to call the corresponding handler function. If another exception occurs while calling the exception handler, the CPU raises a double fault exception.
    • This exception also occurs when there is no handler function registered for an exception.

Handle It

What is it?

  • A special exception that occurs when the CPU fails to invoke an exception handler.
  • For example, a page fault is triggered without a page fault handler registered in the IDT.

Python

  • Perhaps a generalized exception.
try:
    1/0
except:
    "Control flow diverts *regardless* of what goes wrong in the `try`"

Behavior

  • A double fault behaves like a normal exception.
  • It has the vector number 8 and we can define a normal handler function for it in the IDT.
  • It is really important to provide a double fault handler, because if a double fault is unhandled, a fatal triple fault occurs.
  • Triple faults can’t be caught, and most hardware reacts with a system reset.

Triggering a Double Fault

  • We don’t have a page fault handler, so it will double (and triple) fault.
src/main.rs
#[unsafe(no_mangle)]
pub extern "C" fn _start() -> ! {
    osirs::init();
    
    unsafe { *(0xdeadbeef as *mut u8) = 42; };

    #[cfg(test)]
    osirs::qemu_quit(osirs::QEMU_PASS);

    loop {}
}

Description

  • We use unsafe to write to a literal.
  • This address lacks meaning.
    • A virtual (software-visible) address.
    • Regard as a key in key-value storage that maps software-visible addresses to hardware addresses (the MMU).
    • The key is not present in the data structure.

Result

  • So, when we attempt to assign a value based on that key, it explodes.
    • The emulated device goes into a reboot loop.
  • Why?

Steps

  1. The CPU tries to write to 0xdeadbeef, which causes a page fault.
  2. The CPU indexes into the IDT for a page fault and no handler function is specified so a double fault occurs.
  3. The CPU indexes into the IDT for double fault handler and no handler function is specified so a triple fault occurs.
  4. A triple fault is fatal. QEMU (or hardware) issues a system reset.

Handle it

  • To prevent this triple fault, we need to either:
    • Provide a handler function for page faults, or
    • Provide a double fault handler.
  • We want to avoid triple faults in all cases
    • Let’s start with a double fault handler.

Throwback

src/interrupts.rs
#![allow(static_mut_refs)]
static mut IDT: x86_64::structures::idt::InterruptDescriptorTable =
    x86_64::structures::idt::InterruptDescriptorTable::new();

pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        IDT.load();
    }
}

// Love these `cargo fmt` newlines
extern "x86-interrupt" fn breakpoint_handler(
    stack_frame: x86_64::structures::idt::InterruptStackFrame,
) {
    crate::println!("EXCEPTION: BREAKPOINT\n{:#?}", stack_frame);
}

Write a Handler

  • For now, just rip a panic.
    • “Ah!” - that’s what I sound like when I panic.
  • The handler has to diverge because the hardware doesn’t allow returns from a double fault.
    • After all, it’s bad. Twice as bad, even.

One Example

  • Short and sweet.
src/interrupts.rs
extern "x86-interrupt" fn double_fault_handler(
    stack_frame: x86_64::structures::idt::InterruptStackFrame, _error_code: u64) -> !
{
    panic!("EXCEPTION: DOUBLE FAULT\n{:#?}", stack_frame);
}

Wait a minute

  • Blog, in its infinite wisdom, claims we can safely ignore the error code because “it’s always zero”.
  • I’ll be the judge of that.
src/interrupts.rs
extern "x86-interrupt" fn double_fault_handler(
    stack_frame: x86_64::structures::idt::InterruptStackFrame, error_code: u64) -> !
{
    assert!(error_code == 0);
    panic!("EXCEPTION: DOUBLE FAULT\n{:#?}", stack_frame);
}

By the way

  • This is how it looks with cargo fmt
src/interrupts.rs
extern "x86-interrupt" fn double_fault_handler(
    stack_frame: x86_64::structures::idt::InterruptStackFrame,
    error_code: u64,
) -> ! {
    assert!(error_code == 0);
    panic!("EXCEPTION: DOUBLE FAULT\n{:#?}", stack_frame);
}

I bet that works

  • It doesn’t, run it.
  • Yet another reboot loop.
  • But we wrote a function!
    • Friends - did we add it to our IDT?

Update Init

  • This should do it!
src/interrupts.rs
pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        IDT.double_fault.set_handler_fn(double_fault_handler);
        IDT.load();
    }
}

Test it

Behind the Curtain

  • Typically at this point I would show you what QEMU looks like at this time.
  • I can trivially do that with the screendump->ppm2png->base64->html pipeline.
  • It is much cooler to just dump the error message to console.
  • But how?

For Serial

  • Naturally, we can write to console via the serial port from out test environment.
  • So, let’s quickly write a test case for the double-fault handler.
  • It is basically a glorified should_panic.rs.
cp tests/should_panic.rs tests/double.rs

What I start with

test/double.rs
#![no_std]
#![no_main]
#![feature(custom_test_frameworks)]
#![test_runner(osirs::_test_runner)]

#[panic_handler]
fn test_panic(_info: &core::panic::PanicInfo) -> ! {
    osirs::serial_println!("[Pass]");
    osirs::qemu_quit(osirs::QEMU_PASS);
    loop {}
}

fn bad() {
    assert!(false);
}

#[unsafe(no_mangle)]
pub extern "C" fn _start() -> ! {
    osirs::_test_runner(&[&bad]);
    osirs::qemu_quit(osirs::QEMU_FAIL);
    loop {}
}

Changes

  • We want to:
    • Print the error message via serial_println!
    • Hit a panic from within a double-fault handler.
  • Easy enough, we’ll just also init and then modify the panic handler.
    • (We’ll change it back once we get the text out.)

Change bad

  • Was:
test/should_panic.rs
fn bad() {
    assert!(false);
}
  • Is now:
test/double.rs
fn bad() {
    unsafe { *(0xdeadbeef as *mut u8) = 42; };
}

Change panic

  • Was:
test/should_panic.rs
fn test_panic(info: &core::panic::PanicInfo) -> ! {
    osirs::serial_println!("[Pass]");
    osirs::qemu_quit(osirs::QEMU_PASS);
    loop {}
}
  • Is now:
test/double.rs
fn test_panic(info: &core::panic::PanicInfo) -> ! {
    osirs::serial_println!("{}", info);
    osirs::serial_println!("[Pass]");
    osirs::qemu_quit(osirs::QEMU_PASS);
    loop {}
}

Change _start

  • Was:
test/should_panic.rs
pub extern "C" fn _start() -> ! {
    osirs::_test_runner(&[&bad]);
    osirs::qemu_quit(osirs::QEMU_FAIL);
    loop {}
}
  • Is now:
test/double.rs
pub extern "C" fn _start() -> ! {
    osirs::init();
    osirs::_test_runner(&[&bad]);
    osirs::qemu_quit(osirs::QEMU_FAIL);
    loop {}
}

The Stack Frame:

  • I didn’t have to manually type this:
InterruptStackFrame {
    instruction_pointer: VirtAddr(
        0x203a4c,
    ),
    code_segment: 8,
    cpu_flags: 0x2,
    stack_pointer: VirtAddr(
        0x10000201f40,
    ),
    stack_segment: 0,
}

Clean up

  • I kept the test and just reverted the panic handler.
    • Actually, maybe that variant should be factored to src/lib.rs
    • Software engineering… it’s everywhere…
  • (Do this on your own time).
  • (Also stop using the test runner on singleton tests).

Back to Work

What happened?

  1. The CPU tries to write to 0xdeadbeef, which causes a page fault.
  2. Like before, the CPU looks at the corresponding entry in the IDT and sees that no handler function is defined. Thus, a double fault occurs.
  3. The CPU jumps to the – now present – double fault handler.

Vegan

  • Like me, the CPU now abstains from dead beef.
  • The triple fault (and the boot-loop) no longer occurs, since the CPU can now call the double fault handler.
  • Now we’re all done!
    • (We aren’t)

Complications

  • We have now caught a (singular, one) double fault.
    • And a contrived one at that!
  • It so happens there are other things that can also go wrong with computers.
    • Do any of you remember the infinite recursion implementation that could’ve been SO COOL if Rust was just normal about it.

Causes of Double Faults

  • Before we look at the special cases, we need to know the exact causes of double faults.
  • Above, we used a pretty vague definition:

A double fault is a special exception that occurs when the CPU fails to invoke an exception handler.

Failure

  • What does “fails to invoke” mean exactly?
  • The handler is not present?
  • The handler is swapped out?
  • And what happens if a handler causes exceptions itself?

Aside: Swaps

Swap 1

In the 1960s, swapping was an early memory management technique. An entire program or entire segment would be “swapped out” (or “rolled out”) from Random-access memory (RAM) to disk or drum, and another one would be swapped in (or rolled in).

Swap 2

A swapped-out program would be current but its execution would be suspended while the RAM was in use by another program; a program with a swapped-out segment could continue running until it needed that segment, at which point it would be suspended until the segment was swapped in.

Swap 3

Swap space in Linux is used when the amount of physical memory (RAM) is full. If the system needs more memory resources and the RAM is full, inactive pages in memory are moved to the swap space. While swap space can help machines with a small amount of RAM, it should not be considered a replacement for more RAM.

Swap 4

Swap space is located on hard drives, which have a slower access time than physical memory. Swap space can be a dedicated swap partition (recommended), a swap file, or a combination of swap partitions and swap files.

Swap 5

  • I had to increase my swap space that time I was dumping QEMU traces to text files and filled my harddrive.
  • I don’t remember what I did exactly.
  • Here’s a Stack Overflow question
$ free -m
               total        used        free      shared  buff/cache   available
Mem:            15Gi       597Mi        14Gi       6.0Mi       913Mi        14Gi
Swap:          4.0Gi          0B       4.0Gi
$ cat /proc/swaps
Filename                                Type            Size            Used            Priority
/dev/sdc                                partition       4194304         0               -2

Swap 6

Back to Work

Handling Problems

  1. What if a breakpoint exception occurs, but the handler function is swapped out?
  2. What if a page fault occurs, but the handler is swapped out?
  3. What if a divide-by-zero handler causes a breakpoint exception, but the breakpoint handler is swapped out?
  4. What if our kernel overflows its stack and the guard page is hit?

Read the Docs!

  • The AMD64 manual, a real thing that actually exists, is also actually helpful here.
  • Wait that link is broken.
  • We’ll trust the blog.

a double fault exception can occur when a second exception occurs during the handling of a prior (first) exception handler

Combo

First Exception Second Exception
Divide-by-zero,
Invalid TSS,
Segment Not Present,
Stack-Segment Fault,
General Protection Fault
Invalid TSS,
Segment Not Present,
Stack-Segment Fault,
General Protection Fault
Page Fault Page Fault,
Invalid TSS,
Segment Not Present,
Stack-Segment Fault,
General Protection Fault

Examples

  • A divide-by-zero fault followed by a page fault is fine.
    • The page fault handler is invoked.
  • A divide-by-zero fault followed by a general-protection fault is not.
    • Leads to a double fault.
    • Security hat on: a user-mode program may be attempting privilege escalation.

We Now Know 1

  • If a breakpoint exception occurs and the corresponding handler function is swapped out, a page fault occurs and the page fault handler is invoked.
  • If a page fault occurs and the page fault handler is swapped out, a double fault occurs and the double fault handler is invoked.

We Now Know 2

  • If a divide-by-zero handler causes a breakpoint exception, the CPU tries to invoke the breakpoint handler.
  • If the breakpoint handler is swapped out, a page fault occurs and the page fault handler is invoked.

Another case

  • An exception without a handler function in the IDT:
    • CPU derefs the corresponding IDT entry.
    • The entry is invalid so a general protection fault occurs.
    • We lack a general protection fault handler, so another general protection fault occurs.
    • This leads to a double fault.

Four!

Let’s look at the fourth question:

What happens if our kernel overflows its stack and the guard page is hit?

En Garde!

  • A guard page denotes the bottom of a stack to detect stack overflows.
  • The page is not mapped to any physical frame, so accessing page faults.
    • It is the idea of memory that doesn’t exist.
    • The Rust option would’ve been great here!
  • The bootloader sets up a guard page so overflow causes a page fault.

Kernel Stack Overflow

  • When a page fault occurs, the CPU looks up the page fault handler in the IDT and tries to push the [interrupt stack frame] onto the stack.
  • However, the current stack pointer still points to the non-present guard page.
  • Thus, a second page fault occurs, which causes a double fault (according to the above table).

Visually

  • The “interrupt stack frame”:

2s to 3s

  • On the second page fault, the CPU tries to call the double fault handler now.
  • This would push yet another stack frame, which…
  • … still points to the guard page.
  • Third page fault, triple fault, reboot loop.

Count to Three

  • Easy enough, I just make a new test.
cp tests/except.rs tests/overflow.rs
  • Add a function and call from _start
tests/overflow.rs
#[allow(unconditional_recursion)]
fn recurse() {
    recurse();
}

#[unsafe(no_mangle)]
pub extern "C" fn _start() -> ! {
    osirs::init();
    recurse();
    ...

Run Just This Test

  • I have a lot of tests now, so…
cargo t --test overflow
  • Good to run all of them though!
  • Anyways it will fail somehow (boot loop into time out).

Fix

  • How can we avoid this problem?
    • We can’t omit the pushing of the exception stack frame.
      • Done by hardware.
    • We need to ensure somehow that the stack is always valid when a double fault exception occurs.
      • Fortunately, the x86_64 architecture has a solution to this problem.

Switcheroo

  • The x86_64 architecture operates multiple stacks.
  • Maintained in (effectively) a linear data structure.
  • Interrupt Stack Table (IST)
    • There’s 7.

Handle it

  • Each exception handler, can choose a stack from the IST through the stack_pointers field in the corresponding IDT entry.
  • For example, our double fault handler could use the first stack in the IST.
    • I don’t know if it’s zero or one indexed.
  • This preempts the push to prevent the triple.

TSS

  • We recall other segments: Code (CS), Data (DS), Stack (SS).
  • Now, the “Task State Segment”
    • Developed for 32-bit “hardware context switching” that was not brought to 64-bit due to complexities/inefficiencies.
    • Still around and now used here.
  • The 64-bit TSS and 32-bit TSS are wildly different and this doesn’t matter.

The 64-bit

Field Type
(reserved) u32
Privilege Stack Table [u64; 3]
(reserved) u64
Interrupt Stack Table [u64; 7]
(reserved) u64
(reserved) u16
I/O Map Base Address u16
  • I/O Map Base Address supports both 32 and 64 bit port-mapped I/O.

PST

  • Not a timezone.
  • Privilege Stack Table
  • Privilege is bits 12-13 of the code segment, or the code segment “descriptor privilege level.
CS[12:14]
  • We recall all actually existing OSes:
assert(CS[12] == CS[13])

Usage

  • An unprivileged executable divides-by-zero.
  • The handler is called.
  • The handler most be privileged, it’s part of the OS.
  • So it grabs the privileged stack.
  • (This is stack 0 since privilege 0 is the most privileged, mostly)
  • We ignore for now (we have no software).

Creating a TSS

  • Let us create a new TSS that contains a separate double fault stack in its interrupt stack table. For that, we need a TSS struct.
  • By “us” we mean the x86_64 crate which contains a TaskStateSegment struct.
  • We’ll work within src/gdt.rs
    • Global Descriptor Table - we’ll add more latter.

First

  • We need to pub mod this in src/lib.rs
src/lib.rs
pub mod interrupts;
pub mod serial;
pub mod vga;
pub mod gdt;
  • Add the initializer for the GDT to the init function too.
src/lib.rs
pub fn init() {
    interrupts::init_idt();
    gdt::init_gdt();
}

Start on the GDT

  • First, let’s make a TSS.
  • It will come as a shock to no one that I will use static mut to solve a problem wherein a language-level alias is used for actually existing, persistent, mutable hardware.
src/gdt.rs
// TSS
const STACK_SIZE: usize = 4096 * 5;
static mut TSS: x86_64::structures::tss::TaskStateSegment =
    x86_64::structures::tss::TaskStateSegment::new();
static mut STACK: [u8; STACK_SIZE] = [0; STACK_SIZE];

Initialize

  • Not too bad - we set the double fault index to be the stack index plus the stack size.
  • We just made an arbitrarily sized (ish) stack in a static mut (which requires unsafe)
src/gdt.rs
pub const DOUBLE_FAULT_IST_INDEX: usize = 0;

pub fn init_gdt() {
    unsafe {
        TSS.interrupt_stack_table[DOUBLE_FAULT_IST_INDEX] =
            x86_64::VirtAddr::from_ptr(&raw const STACK) + STACK_SIZE;
    }
}

I bet this will work

  • It won’t.
  • We made a TSS but to tell the CPU that it should use it.
  • We need to add a new segment descriptor to the GDT.
  • Then we can load our TSS with the respective GDT index.

Make a GDT

  • Yes, yes, the same trick.
src/gdt.rs
// GDT
static mut GDT: x86_64::structures::gdt::GlobalDescriptorTable =
    x86_64::structures::gdt::GlobalDescriptorTable::new();
  • The GDT, like the TSS, is a 32-bit holdover but still used to:
    • Hold the TSS, obviously, and
    • Swap between kernel (privileged) and user (software/unprivileged) modes.

I bet this will…

  • We further have to add entries to the GDT, naturally.
  • I add the kernel code segment
  • I add the TSS we made.
  • I use the crate to do this.
src/gdt.rs
// Within "init"
let kcs = GDT.add_entry(x86_64::structures::gdt::Descriptor::kernel_code_segment());
let tss = GDT.add_entry(x86_64::structures::gdt::Descriptor::tss_segment(&TSS));

Now it will…

  • Test it, but…
  • The GDT segments are “not yet active” because the segment and TSS registers still contain the values from the old GDT.
  • We also need to modify the double fault IDT entry so that it uses the new stack.

So we…

  1. Reload code segment register: We changed our GDT, so we should reload CS, the code segment register. The old segment selector could now point to an old e.g. TSS.
  2. Load the TSS: We loaded a GDT that contains a TSS selector, but we still need to tell the CPU that it should use that TSS.
  3. ** Update the handler**: Our double fault handler must know to use the novel stack we have created.

Not too bad…

  • Load the GDT.
src/gdt.rs
// Within "init"
let kcs = GDT.add_entry(x86_64::structures::gdt::Descriptor::kernel_code_segment());
let tss = GDT.add_entry(x86_64::structures::gdt::Descriptor::tss_segment(&TSS));
// This is new.
GDT.load();

Update Segments

  • Basically, we got the kernel CS, and TSS.
  • We turned them into descriptors.
  • Either “set” or “load” these descriptors into the GDT.
src/gdt.rs
// Within "init"
GDT.load();
// I love Rust namespaces!
use x86_64::instructions::segmentation::Segment;
x86_64::instructions::segmentation::CS::set_reg(kcs);
x86_64::instructions::tables::load_tss(tss);

Full File

src/gdt.rs
#![allow(static_mut_refs)]

// GDT
static mut GDT: x86_64::structures::gdt::GlobalDescriptorTable =
    x86_64::structures::gdt::GlobalDescriptorTable::new();

// TSS
const STACK_SIZE: usize = 4096 * 5;
static mut TSS: x86_64::structures::tss::TaskStateSegment =
    x86_64::structures::tss::TaskStateSegment::new();
static mut STACK: [u8; STACK_SIZE] = [0; STACK_SIZE];

pub const DOUBLE_FAULT_IST_INDEX: usize = 0;

pub fn init_gdt() {
    unsafe {
        TSS.interrupt_stack_table[DOUBLE_FAULT_IST_INDEX] =
            x86_64::VirtAddr::from_ptr(&raw const STACK) + STACK_SIZE;
        let kcs = GDT.add_entry(x86_64::structures::gdt::Descriptor::kernel_code_segment());
        let tss = GDT.add_entry(x86_64::structures::gdt::Descriptor::tss_segment(&TSS));
        GDT.load();
        use x86_64::instructions::segmentation::Segment;
        x86_64::instructions::segmentation::CS::set_reg(kcs);
        x86_64::instructions::tables::load_tss(tss);
    }
}

Insufficient

  • I still triple fault on this.
  • Why?
    • We added a stack.
    • We added it’s location to the GDT.
    • We added a double fault handler, but
    • We did not direct the double fault handler to change stacks.
  • We return to the handler (NOT the GDT) to update it…

Handle it

  • You probably have:
src/interrupt.rs
pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        IDT.double_fault.set_handler_fn(double_fault_handler);
        IDT.load();
    }
}

Update

  • Update to change a stack index
src/interrupt.rs
pub fn init_idt() {
    unsafe {
        IDT.breakpoint.set_handler_fn(breakpoint_handler);
        // This is from `cargo fmt`...
        IDT.double_fault
            .set_handler_fn(double_fault_handler)
            .set_stack_index(crate::gdt::DOUBLE_FAULT_IST_INDEX as u16);
        IDT.load();
    }
}

This “worked” for me

  • Prefer panic to boot loop.
panicked at src/interrupts.rs:25:5:
EXCEPTION: DOUBLE FAULT
InterruptStackFrame {
    instruction_pointer: VirtAddr(
        0x205cbb,
    ),
    code_segment: 8,
    cpu_flags: 0x6,
    stack_pointer: VirtAddr(
        0x10000201f56,
    ),
    stack_segment: 0,
}

Tying this off

  • This is… incomplete.
    • As a test.
    • For the OS, it is fine.
  • You need to still:
    • Create a test case
    • Modify various handlers
    • Exit successfully when double, rather than triple, faulting.
    • Would’ve been this weeks HW.

Fin