08. External Device Support - josehu07/hux-kernel GitHub Wiki

In the last chapter, we set up IDT and registered ISRs for CPU-reserved gates 0-31, enabling a basic skeleton of interrupt handling mechanism.

In this chapter, we will build support for external hardware devices upon this interrupt handling skeleton. This enables a bunch of very useful functionalities, such as keyboard input and a system timer.

Main References of This Chapter

Scan through them before going forth:

8259 PIC page: PIC architecture and programming examples ✭
Programmable Interval Timer: for PIT built-in timer chip specifications
PS/2 Keyboard page: for PS/2 keyboard input controller specifications
Philipp's blog section: on keyboard input handling

Communicating with External Devices

There are generally two ways of communicating with external devices:

Polling: loop and check the state of an external device on a regular basis
Hardware interrupts: as we have defined in the last chapter

Polling is in fact very useful in cases when the system does not have an elegent interrupt mechanism, or you have too many external devices such that polling might actually be more efficient than serving too many incoming interrupts. Despite, interrupt is often considered a more "advanced" way and is usually used for timers and input devices such as a keyboard. Things like a key-stroke on a keyboard naturally fits in the concept of an "interrupt".

Programmable Interrupt Controller (PIC)

We learned in the last chapter that pin-based hardware interrupts rely on a dedicated chip device called the programmable interrupt controller (PIC). An external device, e.g. a keyboard, send interrupt requests (IRQs) to the PIC. The PIC is the only device that directly talks to the CPU and sends interrupt index numbers.

It is the PIC's responsibility to serialize incoming IRQs, translate them to interrupt index numbers, and communicate the numbers with CPU through the CPU interrupt pin serially to perform hardware interrupts. You can somehow think of a PIC as a "external interrupt signal multiplexer".

On x86 IA32 architecture, the 8259 PIC plays this important role. (Notice that on some modern multiprocessor chip-sets, it is replaced by its successor - the advanced programmable interrupt controller (APIC).) The IBM PC/AT 8259 PIC has the following dual-chip architecture (thanks James for this figure) ✭:

Input pin #2 on master PIC is designed to be connected with slave PIC's output pin. With a total of 16 input pins, we have a total of 16 possible IRQ #s (0-15). Master PIC takes IRQ # 0-7 and slave PIC takes 8-15. Note that IRQ # 2 will never happen in action because it is wired to redirect slave PIC's output.

An external hardware is wired to a fixed PIC input pin. It will then generate that corresponding IRQ # when it signals a hardware interrupt to PIC.

After BIOS booting, a default IRQ # to interrupt # mapping will be established ✭:

IRQ # 0-7 (master PIC inputs) mapped to interrupt # 0x08-0x0F: recall that in protected mode, the first 32 interrupt numbers are reserved for CPU software exceptions - Hence, at IDT initialization, we must remap these to higher interrupt numbers to prevent conflicts. Conventionally, we remap them to interrupt # 0x20-0x27. This is a historical issue
IRQ # 8-15 (slave PIC inputs) mapped to interrupt # 0x70-0x77: we conventionally remap them to 0x28-0x2F

PIC Initialization, Remapping & Masking

To program the PIC chips, send control signals to I/O ports:

Master PIC: command port 0x20, data port 0x21
Slave PIC: command port 0xA0, data port 0xA1

Add these @ src/interrupt/idt.c:

/** Extern our PIC IRQ handlers written in ASM `irq-stub.s`. */
extern void irq0 (void);
...
extern void irq15(void);


/**
 * Initialize the interrupt descriptor table (IDT) by setting up gate
 * entries of IDT, setting the IDTR register to point to our IDT address,
 * and then (through assembly `lidt` instruction) load our IDT.
 */
void
idt_init()
{
    /**
     * Remap PIC cascade mode external interrupt numbers.
     *
     * I/O ports:
     *   - Master PIC: command port `0x20`, data port `0x21`
     *   - Slave  PIC: command port `0xA0`, data port `0xA1`
     *   
     * These PIC initialization commands are called initialization words
     * (ICWs) and the order of 4 ICWs must be correct. 
     */
    outb(0x20, 0x11);   /** Initialize master PIC in cascade mode. */
    outb(0xA0, 0x11);   /** Initialize slave  PIC in cascade mode. */
    outb(0x21, 0x20);   /** Master PIC mapping offset = 0x20. */
    outb(0xA1, 0x28);   /** Slave  PIC mapping offset = 0x28. */
    outb(0x21, 0x04);   /** Tell master PIC that slave PIC at IRQ # 2. */
    outb(0xA1, 0x02);   /** Tell slave PIC its cascade identity at 2. */
    outb(0x21, 0x01);   /** Set master PIC in 8086/88 mode. */
    outb(0xA1, 0x01);   /** Set slave  PIC in 8086/88 mode. */

    /** Pin masking. */
    outb(0x21, 0x0);    /** Set masking of master PIC. */
    outb(0xA1, 0x0);    /** Set masking of slave  PIC. */

    ...

    /** These are for PIC IRQs (remapped). */
    idt_set_gate(32, (uint32_t) irq0 , 8 * SEGMENT_KCODE, 0x8E);
    
    ...

    idt_set_gate(47, (uint32_t) irq15, 8 * SEGMENT_KCODE, 0x8E);

    ...
}

IRQs Handler Implementation

Similar to what we did for ISRs, we will create wrappers for the 16 IRQs in assembly and call a C function to handle IRQs, passing the IRQ # as an argument.

Code added @ src/interrupt/isr-stub.s:

/**
 * We make 16 wrapper for all 16 mapped IRQs from PIC. They all call the
 * handler stub function as well.
 */
.global irq0
.type irq0, @function
irq0:
    pushl $0                /** Dummy error code. */
    pushl $32               /** Interrupt index code. */
    jmp isr_handler_stub    /** Jump to handler stub. */

...     // Repeat for 1-15...

The saved interrupt state here is almost the same as exception ISRs # 0-31, except that we do not have an error code here, since no external interrupts push an error code on stack. Code added @ src/interrupt/isr.c:

/** Send back PIC end-of-interrupt (EOI) signal. */
static void
_pic_send_eoi(uint8_t irq_no)
{
    if (irq_no >= 8)
        outb(0xA0, 0x20);   /** If is slave IRQ, should send to both. */
    outb(0x20, 0x20);
}


/**
 * ISR handler written in C.
 *
 * Receives a pointer to a structure of interrupt state. Handles the
 * interrupt and simply returns. Can modify interrupt state through
 * this pointer if necesary.
 */
void
isr_handler(interrupt_state_t *state)
{
    uint8_t int_no = state->int_no;

    /** An exception interrupt. */
    if (int_no <= 31) {

        /** Panic if no actual ISR is registered. */
        if (isr_table[int_no] == NULL)
            error("missing handler for ISR interrupt # %#x", int_no);
        else
            isr_table[int_no](state);

    /** An IRQ-translated interrupt from external device. */
    } else if (int_no <= 47) {
        uint8_t irq_no = state->int_no - 32;

        /** Call actual ISR if registered. */
        if (isr_table[int_no] == NULL)
            error("missing handler for IRQ interrupt # %#x", int_no);
        else
            isr_table[int_no](state);

        _pic_send_eoi(irq_no);      /** Send back EOI signal to PIC. */
    }
}

Pay attention to the routine pic_send_eoi here. At the end of our IRQ handler, we MUST send back to PIC command port a 0x20 signal to indicate "this is the end of this interrupt and you can send me the next one now if there is one waiting". This is called an end-of-interrupt (EOI) signal. On slave IRQs, we should send to both master's and slave's port an EOI signal.

Programmable Interval Timer (PIT)

An OS kernel cannot live without a stable periodic signal generator. Such a generator is often called a timer. It generates interrupts at a stable & regular frequency f, defining a time interval length 1/f. This is the minimum time slot unit of the system. The presence of a timer gives the system a sense of time - it knows how long has passed by counting timer interrupts. Timer is also the basis of time-sharing multitasking ✭.

The programmable interval timer (PIT, 8253 chip) is a standard timer device consisting of an oscillator running at base frequency 1.193182 MHz. Provided different frequency dividers ranging from 0-65535, it can produce a timer frequency of the base frequency divided by the frequency divider. The PIT is wired to IRQ pin # 0.

Channel 0 of the PIT is connected directly to IRQ pin # 0 and is very useful as a system timer. We want the PIT to operate in "Square Wave Generator" mode (mode 3). To do this, write a control signal byte to I/O port 0x43 with the definition:

|7  Channel  6|5  Access mode  4|3  Operating mode  1|0  BCD/Binary  0|

In our case, the signal should be 0x36. Check out this section for detailed specifications.

Code @ src/device/timer.c:

/**
 * Timer interrupt handler registered for IRQ # 0.
 * Currently just prints a tick message.
 */
static void
timer_interrupt_handler(interrupt_state_t *state)
{
    (void) state;   /** Unused. */
    printf(".");
}


/**
 * Initialize the PIT timer. Registers timer interrupt ISR handler, sets
 * PIT to run in mode 3 with given frequency in Hz.
 */
void
timer_init(void)
{
    /** Register timer interrupt ISR handler. */
    isr_register(INT_NO_TIMER, &timer_interrupt_handler);
                 // 32, add macro definition in `src/interrupt/isr.h`

    /**
     * Calculate the frequency divisor needed to run with the given
     * frequency. Divisor = base frequencty / desired frequency.
     */
    uint16_t divisor = 1193182 / TIMER_FREQ_HZ;

    outb(0x43, 0x36);   /** Run in mode 3. */

    /** Sends frequency divisor, in lo | hi order. */
    outb(0x40, (uint8_t) (divisor & 0xFF));
    outb(0x40, (uint8_t) ((divisor >> 8) & 0xFF));
}

Add the declaration @ src/device/timer.h:

/** Timer interrupt frequency in Hz. */
#define TIMER_FREQ_HZ 100


void timer_init();

Now let's try it out and see if our timer is ready to roll! When our system boots up, interrupts are disabled by default. Thus, after IDT is initialized and all devices are set up, we execute the sti instruction to enable interrupts. At this time point, the CPU starts taking in interrupts. We then put our CPU into idle with a hlt loop - it is much cheaper and more elegant than a busy spin.

Our kernel main function @ src/kernel.c:

/** The main function that `boot.s` jumps to. */
void
kernel_main(unsigned long magic, unsigned long addr)
{
    /** Initialize VGA text-mode terminal support. */
    terminal_init();

    /** Double check the multiboot magic number. */
    if (magic != MULTIBOOT_BOOTLOADER_MAGIC) {
        error("invalid bootloader magic: %#x", magic);
        return;
    }

    /** Get pointer to multiboot info. */
    multiboot_info_t *mbi = (multiboot_info_t *) addr;

    /** Initialize debugging utilities. */
    debug_init(mbi);

    /** Initialize global descriptor table (GDT). */
    gdt_init();

    /** Initialize interrupt descriptor table (IDT). */
    idt_init();

    /** Initialize PIT timer at 100 Hz frequency. */
    timer_init();

    /** Executes `sti`, CPU starts taking in interrupts. */
    asm volatile ( "sti" );

    while (1)   // CPU idles with a `hlt` loop.
        asm volatile ( "hlt" );
}

Compile and boot in QEMU. We will see the timer printing dots periodically at around 100Hz frequency:

Keyboard Input Support

Keyboard input is no doubt a significant part of an OS kernel. This is the major way we interact with our system in real-time. In this section, we will enable PS/2 keyboard support.

The keyboard input is statically wired to the master PIC's input pin # 1, meaning that keyboard signals arrive as interrupt number 0x21 (33). What we need is to write an ISR handler for this interrupt number.

Mimicking what we did for the PIT timer, we add keyboard handler implementation @ src/device/keyboard.c:

/**
 * Keyboard interrupt handler registered for IRQ # 0.
 * Currently just prints a tick message.
 */
static void
keyboard_interrupt_handler(interrupt_state_t *state)
{
    (void) state;   /** Unused. */
    printf("k");
}


/** Initialize the PS/2 keyboard device. */
void
keyboard_init()
{
    /** Register keyboard interrupt ISR handler. */
    isr_register(INT_NO_KEYBOARD, &keyboard_interrupt_handler);
                 // 33, add macro definition in `src/interrupt/isr.h`
}


// src/device/keyboard.h

void keyboard_init();

If you now add keyboard_init() to our main function and run, you will find out that a letter k appears when we press a key - but only for the first time. This is because the keyboard controller follows a protocol that it won't send another interrupt until we have read the scancode of the pressed key. Check out this page for the detailed protocol model.

Pressing a key generates a different scancode from releasing the key. To read out the interrupt event's scancode, simply read from I/O port 0x60. We will get a byte value.

These are what we need to do in the keyboard interrupt handler:

Read out the event's scancode from I/O port 0x60
If scancode < 0xE0, interpret into "[key]-[pressed/released]" event
Else if scancode == 0xE0, it indicates key in the extended set
1. Read out an extra extendcode byte from I/O port 0x60
2. Interpret into "[key]-[pressed/released]" event
Perform actions with the event, like printing the character onto terminal window

Scancode Set 1 Mapping

By default, PS/2 keyboards emulate the scancode set 1 (IBM XT). Follow the linked page for a list of all scancode set 1 mappings. Very unfortunately, we have to hardcode these mappings by hand.

Code added @ src/device/keyboard.h:

/** A partial set of special keys on US QWERTY keyboard. */
enum keyboard_meta_key {
    KEY_NULL,   // Dummy placeholder for empty key

    KEY_ESC,    // Escape
    KEY_BACK,   // Backspace
    KEY_TAB,    // Tab
    KEY_ENTER,  // Enter
    KEY_CTRL,   // Both ctrls
    KEY_SHIFT,  // Both shifts
    KEY_ALT,    // Both alts
    KEY_CAPS,   // Capslock

    KEY_HOME,   // Home
    KEY_END,    // End
    KEY_UP,     // Cursor up
    KEY_DOWN,   // Cursor down
    KEY_LEFT,   // Cursor left
    KEY_RIGHT,  // Cursor right
    KEY_PGUP,   // Page up
    KEY_PGDN,   // Page down
    KEY_INS,    // Insert
    KEY_DEL,    // Delete
};
typedef enum keyboard_meta_key keyboard_meta_key_t;

/** Holds info for a keyboard key. */
struct keyboard_key_info {
    keyboard_meta_key_t meta;   /** Special meta key. */
    char codel;                 /** ASCII byte code - lower case. */
    char codeu;                 /** ASCII byte code - upper case. */
};
typedef struct keyboard_key_info keyboard_key_info_t;

/** Struct for a keyboard event. */
struct keyboard_key_event {
    bool press;     /** False if is a release event. */
    bool ascii;     /** True if is ASCII character, otherwise special. */
    keyboard_key_info_t info;
};
typedef struct keyboard_key_event keyboard_key_event_t;

We then code the mappings @ src/device/keyboard.c:

/**
 * Hardcode scancode -> key event mapping.
 *
 * Check out https://wiki.osdev.org/Keyboard#Scan_Code_Set_1
 * for a complete list of mappings.
 *
 * We will only code a partial set of mappings - only those most
 * useful events.
 */
#define NO_KEY { .press = false, .ascii = false, .info = { .meta = KEY_NULL } }

static keyboard_key_event_t scancode_event_map[0xE0] = {
    NO_KEY,                                                                      // 0x00
    { .press = true , .ascii = false, .info = { .meta = KEY_ESC   } },           // 0x01
    { .press = true , .ascii = true , .info = { .codel = '1' , .codeu = '!' } }, // 0x02

    ...

    { .press = false, .ascii = false, .info = { .meta = KEY_ESC   } },           // 0x81
    { .press = false, .ascii = true , .info = { .codel = '1' , .codeu = '!' } }, // 0x82

    ...

    NO_KEY,                                                                      // 0xDF
};

static keyboard_key_event_t extendcode_event_map[0xE0] = {
    NO_KEY,                                                            // 0x00
    NO_KEY,                                                            // 0x01
    NO_KEY,                                                            // 0x02

    ...

    { .press = true , .ascii = false, .info = { .meta = KEY_CTRL  } }, // 0x1D

    ...

    { .press = false, .ascii = false, .info = { .meta = KEY_CTRL  } }, // 0x9D

    ...

    NO_KEY,                                                            // 0xDF
};

In the interrupt handler, echo a character if a key of ASCII character is pressed:

/**
 * Timer interrupt handler registered for IRQ # 1.
 * Echoing keystrokes on keyboard.
 */
static void
keyboard_interrupt_handler(interrupt_state_t *state)
{
    (void) state;   /** Unused. */
    
    keyboard_key_event_t event = NO_KEY;

    /**
     * Read our the event's scancode. Translate the scancode into a key
     * event, following the scancode set 1 mappings.
     */
    uint8_t scancode = inb(0x60);
    if (scancode < 0xE0)
        event = scancode_event_map[scancode];
    else if (scancode == 0xE0) {    /** Is a key in extended set. */
        uint8_t extendcode = inb(0x60);
        if (extendcode < 0xE0)
            event = extendcode_event_map[extendcode];
    }

    if (event.press && event.ascii)
        cprintf(VGA_COLOR_LIGHT_BROWN, "%c", event.info.codel);
}

Now, add keyboard initialization to main function:

/** The main function that `boot.s` jumps to. */
void
kernel_main(unsigned long magic, unsigned long addr)
{
    ...

    /** Initialize PIT timer at 100 Hz frequency. */
    timer_init(100);

    /** Initialize PS/2 keyboard support. */
    keyboard_init();

    /** Executes `sti`, CPU starts taking in interrupts. */
    asm volatile ( "sti" );

    while (1)   // CPU idles with a `hlt` loop.
        asm volatile ( "hlt" );
}

Compile and boot in QEMU. We will still see the timer printing dots periodically. Try smashing your keyboard with random keystrokes and your should see the echoed characters appearing:

Progress So Far

In summary, we set up external device IRQs and remapped them to interrupt indices 32-47. We then enabled two typical external devices - a PIT timer and a keyboard. Our kernel is now starting to become "interactive"!

Current repo structure:

hux-kernel
├── Makefile
├── scripts
│   ├── gdb_init
│   ├── grub.cfg
│   └── kernel.ld
├── src
│   ├── boot
│   │   ├── boot.s
│   │   ├── elf.h
│   │   └── multiboot.h
│   ├── common
│   │   ├── debug.c
│   │   ├── debug.h
│   │   ├── port.c
│   │   ├── port.h
│   │   ├── printf.c
│   │   ├── printf.h
│   │   ├── string.c
│   │   ├── string.h
│   │   ├── types.c
│   │   └── types.h
│   ├── device
│   │   ├── keyboard.c
│   │   ├── keyboard.h
│   │   ├── timer.c
│   │   └── timer.h
│   ├── display
│   │   ├── terminal.c
│   │   ├── terminal.h
│   │   └── vga.h
│   ├── memory
│   │   ├── gdt-load.s
│   │   ├── gdt.c
│   │   └── gdt.h
│   ├── interrupt
│   │   ├── idt-load.s
│   │   ├── idt.c
│   │   ├── idt.h
│   │   ├── isr-stub.s
│   │   ├── isr.c
│   │   └── isr.h
│   └── kernel.c