Un kernel con reloj y tres tareas

Material de apoyo:

Índice

Creación de stacks en el kernel
Concurrencia cooperativa
Interrupciones: reloj y teclado
Desalojo ★

Creación de stacks en el kernel

Cuando un programa se ejecuta, normalmente es el sistema operativo quien le configura el stack de manera adecuada, esto es: reserva un espacio en memoria (a menudo 4 u 8 KiB) y apunta %esp a dicha región (bien al límite inferior, bien al superior, según la dirección en que crece la pila en la arquitectura).

Un kernel, en cambio, es responsable de asignarse su propio boot stack durante el proceso de arranque.

Por su parte, los programas de usuario también pueden crearse pilas adicionales, por ejemplo para ejecutar varias tareas de manera concurrente.

Ej: kern2-stack

Lecturas obligatorias
- BRY2
  - cap. 3: §6(6)

La manera estándar de configurar la pila de arranque del sistema operativo es reservar espacio en el propio binario, esto es: un arreglo en memoria del tamaño deseado. Puede declararse en un archivo C:

unsigned char kstack[8192];

o assembler:

.data
kstack:
    .space 8192

Normalmente, en x86 se alinea el stack de los procesos de usuario a 16 o 32 bits. Sin embargo, por razones relacionadas —como se verá— con memoria virtual, el stack del kernel se suele alinear 4 KiB:

Explicar: ¿qué significa “estar alineado”?
Mostrar la sintaxis de C/GCC para alinear a 32 bits el arreglo kstack anterior.
¿A qué valor se está inicializando kstack? ¿Varía entre la versión C y la versión ASM? (Leer la documentación de as sobre la directiva .space.)
Explicar la diferencia entre las directivas .align y .p2align de as, y mostrar cómo alinear el stack del kernel a 4 KiB usando cada una de ellas.

Otra posibilidad para definir el stack del kernel es hacerlo en alguna otra región de memoria, separada de la imagen del kernel. Así, si se sobrepasara el espacio reservado, se evitaría sobreescribir lo que hubiera al continuación (al menos hasta que se puedan introducir otras medidas de protección, como guard pages).

Para ello, convendrá saber la cantidad de memoria de que dispone la máquina. A partir de ahora definiremos que la función main del kernel, kmain, reciba un struct con la información Multiboot proporcionada por el gestor de arranque (ver ejercicio kern0-gdb; las definiciones están disponibles en el archivo multiboot.h):

#include "decls.h"
#include "multiboot.h"

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);
}

El archivo decls.h, por el momento, tendría:

#ifndef KERN2_DECL_H
#define KERN2_DECL_H

#include <stdint.h>

// write.c (función de kern0-vga copiada no-static).
void vga_write(const char *s, int8_t linea, uint8_t color);

#endif

Se pide ahora escribir una nueva versión del archivo boot.S en que se defina el stack de arranque, así como el “entry point” _start del kernel. Así, al saltar a código C, el stack ya estará debidamente configurado:

// boot.S

#include "multiboot.h"

#define KSTACK_SIZE 8192

.align 4
multiboot:
    .long MULTIBOOT_HEADER_MAGIC
    .long 0
    .long -(MULTIBOOT_HEADER_MAGIC)

.globl _start
_start:
    // Paso 1: Configurar el stack antes de llamar a kmain.
    movl $0, %ebp
    movl ..., %esp
    push %ebp

    // Paso 2: pasar la información multiboot a kmain. Si el
    // kernel no arrancó vía Multiboot, se debe pasar NULL.
    //
    // Usar una instrucción de comparación (TEST o CMP) para
    // comparar con MULTIBOOT_BOOTLOADER_MAGIC, pero no usar
    // un salto a continuación, sino una instrucción CMOVcc
    // (copia condicional).
    // ...

    call kmain
halt:
    hlt
    jmp halt

.data
.p2align ...
kstack:
    .space KSTACK_SIZE

Finalmente: mostrar en una sesión de GDB los valores de %esp y %eip al entrar en kmain, así como los valores almacenados en el stack en ese momento.

Ej: kern2-cmdline

Lecturas obligatorias
- REES
  - cap. 5
Lecturas recomendadas
- BRY2
  - cap. 3: §12

En el arranque, el sistema operativo puede recibir parámetros, al igual que cualquier programa, “por la línea de comandos”. En el caso de un kernel, la línea de comandos es el gestor de arranque, por ejemplo grub. Linux permite consultar los parámetros del arranque en el archivo /proc/cmdline:

$ cat /proc/cmdline
BOOT_IMAGE=/vmlinuz-4.9.0-3-amd64 root=/dev/sda2 ro

En QEMU, se pueden agregar parámetros al kernel mediante la opción -append. Si se añade una variable adicional a las reglas de QEMU propuestas en el lab anterior:

KERN ?= kern2
BOOT := -kernel $(KERN) $(QEMU_EXTRA)

se puede especificar la opción directamente al invocar make:

$ make qemu QEMU_EXTRA="-append 'param1=hola param2=adios'"

Ahora que kmain recibe un struct multiboot_info, se pide expandir kern2.c para imprimir al arrancar los parámetros recibidos:

#include <string.h>

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);

    if (/* mbi->flags indica que hay cmdline */) {
        char buf[256] = "cmdline: ";
        char *cmdline = (void *) mbi->cmdline;
        // Aquí usar strlcat() para concatenar cmdline a buf.
        // ...
        vga_write(buf, 9, 0x07);
    }
}

Para manejo de cadenas con string.h, se reusa la biblioteca estándar de Pintos, un kernel educativo de Stanford; en particular:

Estos archivos deben ir en un subdirectorio lib, ajustando la variable SRCS como corresponda.

Finalmente:

Mostrar cómo implementar la misma concatenación, de manera correcta, usando strncat(3).¹
Explicar cómo se comporta strlcat(3) si, erróneamente, se declarase buf con tamaño 12. ¿Introduce algún error el código?

Compilar el siguiente programa, y explicar por qué se imprimen dos líneas distintas, en lugar de la misma dos veces:

#include <stdio.h>

static void printf_sizeof_buf(char buf[256]) {
    printf("sizeof buf = %zu\n", sizeof buf);
}

int main(void) {
    char buf[256];
    printf("sizeof buf = %zu\n", sizeof buf);
    printf_sizeof_buf(buf);
}

Revisar, de ser necesario, K&R §5.3.²

Compiler includes

En código del kernel no hay acceso a la biblioteca estándar de C, por lo que se debe incluir una implementación de todas las funciones que se invocan.

Para código kernel, el compilador debería manejar las directivas include de la siguiente manera:

nunca usar los archivos de la biblioteca estándar de C (p. ej. string.h o stdlib.h)
si se necesita, por ejemplo, #include <string.h>, se debe buscar en la propia biblioteca del kernel, en este caso el subdirectorio lib
los includes estándar de C99 como stdint.h o stdbool.h sí deberían estar disponibles (en este caso, los proporciona el mismo compilador y no libc).

La opción -ffreestanding no es suficiente para conseguir este comportamiento, por lo que se necesitan ajustes adicionales en CPPFLAGS. A continuación se muestra cómo hacerlo en GCC y, más fácilmente, usando Clang:

Clang

CPPFLAGS := -nostdlibinc -idirafter lib

GCC³

CPPFLAGS := -nostdinc -idirafter lib

GCC_PATH := /usr/lib/gcc/x86_64-linux-gnu/6 ⁽¹⁾
CPPFLAGS += -I$(GCC_PATH)/include -I$(GCC_PATH)/include-fixed

⁽¹⁾ Consultar la salida de gcc --print-search-dirs.

Ej: kern2-meminfo ★

Se desea imprimir durante el arranque la cantidad de memoria física que el sistema reportó a través de Multiboot; por ejemplo:

$ make qemu QEMU_EXTRA="-append meminfo"
kern2 loading.............
cmdline: kern2 meminfo
Physical memory: 127MiB total (639KiB base, 129920KiB extended)

Se puede cambiar la cantidad de memoria con el parámetro -m de QEMU:

$ make qemu QEMU_EXTRA="-m 256"
Physical memory: 255MiB total (639KiB base, 260992KiB extended)

Para imprimir un valor número en el buffer VGA se podría definir en write.c una función con un prototipo similar a:

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

// Escribe en ‘s’ el valor de ‘val’ en base 10 si su anchura
// es menor que ‘bufsize’. En ese caso devuelve true, caso de
// no haber espacio suficiente no hace nada y devuelve false.
bool fmt_int(uint64_t val, char *s, size_t bufsize);

Así, en kmain se puede invocar a fmt_int sobre un buffer temporal, y usar strlcat para componer todas las partes:

char mem[256] = "Physical memory: ";
char tmp[64] = "";

if (fmt_int(NNN, tmp, sizeof tmp)) {
    strlcat(mem, tmp, sizeof mem);
    strlcat(mem, "MiB total", sizeof mem);
}

// ...

vga_write(mem, 10, 0x07);

La implementación de fmt_int puede comenzar por calcular la anchura del entero en decimal, y devolver false si no hay espacio suficiente en el buffer recibido:

static size_t int_width(uint64_t val) {
    // ...
}

bool fmt_int(uint64_t val, char *s, size_t bufsize) {
    size_t l = int_width(val);

    if (l >= bufsize)  // Pregunta: ¿por qué no "l > bufsize"?
        return false;

    s += l;
    // ...
    return true;
}

Ayuda adicional:

se puede pasar trivialmente de KiB a MiB con una operación de desplazamiento de bits, sin necesidad de división.

quizá la función fmt_int sí necesite realizar una división y/o operación de módulo, en cuyo caso el proceso de compilación quizá falle con un error similar a:

write.c:38: undefined reference to `__umoddi3'
write.c:40: undefined reference to `__udivdi3'

Este error está explicado en el documento Guide to Bare Metal Programming with GCC previamente señalado, y la solución se reduce a enlazar con libgcc. Existen dos maneras de hacerlo:

Seguir usando directamente ld como enlazador, en cuyo caso hay que solicitar a gcc la ruta completa al archivo libgcc.a:

LIBGCC := $(shell $(CC) $(CFLAGS) -print-libgcc-file-name)

$(KERN): $(OBJS)
        ld -m elf_i386 -Ttext 0x100000 $^ $(LIBGCC) -o $@

Usar el compilador de C como front-end al enlazador, que es lo que hace make por omisión. En ese caso, se debe ajustar la sintaxis de las opciones, y añadir -nostdlib:

LDLIBS := -lgcc
LDFLAGS := -m32 -nostdlib -static -Wl,-Ttext=0x100000

$(KERN): $(OBJS)
        $(CC) $(LDFLAGS) $^ $(LDLIBS) -o $@

(Esta es, de hecho, la regla implícita de make para el enlazado.)⁴

Concurrencia cooperativa

Dadas dos o más tareas que se desea ejecutar de manera concurrente en un procesador —por ejemplo, el cálculo de números primos o de los dígitos de π, o cualquier otra tarea CPU-bound— lo habitual es asignar a cada un flujo de ejecución separado (ya sean procesos o hilos); y delegar al sistema operativo la implementación de la concurrencia, esto es, la alternancia de ambos flujos.

Suponiendo, para el resto del lab, un sistema con un solo core, se presenta ahora la pregunta: ¿es posible implementar concurrencia de algún tipo sin ayuda del sistema operativo?⁵

La respuesta a esta pregunta es una planificación cooperativa en la que dos o más tareas se cedan mutuamente el uso del procesador por un internalo de tiempo. Como se verá, este tipo de cooperación puede implementarse sin ayuda del sistema operativo; y la implementación más sencilla se consigue proporcionando a cada tarea su propio stack.

Ej: kern2-task

En el ejercicio kern2-stack se vio cómo declarar espacio para stacks adicionales. En este ejercicio se realizarán, en dos stacks separados de 4 KiB, sendas llamadas a la función ya implementada vga_write().

Partiendo de un archivo kern2.c similar a:

#include "decls.h"
#include "multiboot.h"

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);

    // A remplazar por una llamada a two_stacks(),
    // definida en stacks.S.
    vga_write("vga_write() from stack1", 12, 0x17);
    vga_write("vga_write() from stack2", 13, 0x90);
}

se pide implementar una función two_stacks() en assembler que realice las llamadas mostradas en stacks distintos. Se recomienda usar el siguiente segmento de datos:

// stacks.S
#define USTACK_SIZE 4096

.data
        .align 4096
stack1:
        .space USTACK_SIZE
stack1_top:

        .p2align 12
stack2:
        .space USTACK_SIZE
stack2_top:

msg1:
        .asciz "vga_write() from stack1"
msg2:
        .asciz "vga_write() from stack2"

y el siguiente esqueleto de implementación:

// stacks.S continuado
.text
.globl two_stacks
two_stacks:
        // Preámbulo estándar
        push %ebp
        movl %esp, %ebp

        // Registros para apuntar a stack1 y stack2.
        mov $stack1_top, %eax
        mov $stack2_top, ...   // Decidir qué registro usar.

        // Cargar argumentos a ambos stacks en paralelo. Ayuda:
        // usar offsets respecto a %eax ($stack1_top), y lo mismo
        // para el registro usado para stack2_top.
        movl $0x17, ...(%eax)
        movl $0x90, ...(...)

        movl $12, ...
        movl $13, ...

        movl $msg1, ...
        movl $msg2, ...

        // Realizar primera llamada con stack1. Ayuda: usar LEA
        // con el mismo offset que los últimos MOV para calcular
        // la dirección deseada de ESP.
        leal ...(%eax), %esp
        call vga_write

        // Restaurar stack original. ¿Es %ebp suficiente?
        movl ..., %esp

        // Realizar segunda llamada con stack2.
        leal ...(...), %esp
        call vga_write

        // Restaurar registros callee-saved, si se usaron.
        ...

        leave
        ret

Ej: kern2-exec

Implementar ahora una función en C que realice la misma tarea que two_stacks(), realizando las llamadas de escritura de la siguiente manera:

para la primera llamada, definir una función auxiliar en un nuevo archivo tasks.S:

// Realiza una llamada a "entry" sobre el stack proporcionado.
void task_exec(uintptr_t entry, uintptr_t stack);

para la segunda llamada, realizar la llamada directamente mediante assembler inline.

El código en C puede estar en el mismo archivo kern2.c, y debe preparar sus stacks de modo análogo a stacks.S. Se sugiere el siguiente esqueleto de implementación:

#include "decls.h"
#include "multiboot.h"

#define USTACK_SIZE 4096

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);

    two_stacks();
    two_stacks_c();
}

static uint8_t stack1[USTACK_SIZE] __attribute__((aligned(4096)));
static uint8_t stack2[USTACK_SIZE] __attribute__((aligned(4096)));

void two_stacks_c() {
    // Inicializar al *tope* de cada pila.
    uintptr_t *a = ...
    uintptr_t *b = ...

    // Preparar, en stack1, la llamada:
    vga_write("vga_write() from stack1", 15, 0x57);

    // AYUDA 1: se puede usar alguna forma de pre- o post-
    // incremento/decremento, según corresponda:
    //
    //     *(a++) = ...
    //     *(++a) = ...
    //     *(a--) = ...
    //     *(--a) = ...

    // AYUDA 2: para apuntar a la cadena con el mensaje,
    // es suficiente con el siguiente cast:
    //
    //   ... a ... = (uintptr_t) "vga_write() from stack1";

    // Preparar, en s2, la llamada:
    vga_write("vga_write() from stack2", 16, 0xD0);

    // AYUDA 3: para esta segunda llamada, usar esta forma de
    // asignación alternativa:
    b -= 3;
    b[0] = ...
    b[1] = ...
    b[2] = ...

    // Primera llamada usando task_exec().
    task_exec((uintptr_t) vga_write, (uintptr_t) s1);

    // Segunda llamada con ASM directo. Importante: no
    // olvidar restaurar el valor de %esp al terminar, y
    // compilar con: -fasm -fno-omit-frame-pointer.
    asm("...; call *%1; ..."
        : /* no outputs */
        : "r"(s2), "r"(vga_write));
}

Ej: kern2-regcall

Para este ejercicio se añadirá una segunda versión de vga_write() que toma sus parámetros directamente por registros:

// decls.h
void __attribute__((regparm(3)))
vga_write2(const char *s, int8_t linea, uint8_t color);

Se pide, en primer lugar, leer la documentación de la convención de llamadas regparm para implementar la función vga_write2() en el archivo funcs.S:

// tasks.S
.globl vga_write2
vga_write2:
        push %ebp
        movl %esp, %ebp

        // ...
        call vga_write

        leave
        ret

A continuación, mostrar con objdump -d el código generado por GCC para la siguiente llamada a vga_write2() desde la función principal:

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);

    two_stacks();
    two_stacks_c();

    vga_write2("Funciona vga_write2?", 18, 0xE0);
}

Ej: kern2-swap

En el archivo contador.c se proporciona una función contador_yield() que muestra en el buffer VGA una cuenta desde 0 hasta un número pasado como parámetro. Para simular un retardo entre número y número, a cada incremento se le añade un ciclo while con un número alto de iteraciones (controlado por la macro DELAY).

Añadir el archivo a las fuentes de kern2 y comprobar que se ejecutan dos contadores (uno verde y otro rojo) al invocar a contador_run() desde la función principal:

void kmain(const multiboot_info_t *mbi) {
    vga_write("kern2 loading.............", 8, 0x70);

    two_stacks();
    two_stacks_c();
    contador_run();  // Nueva llamada ej. kern2-swap.

    vga_write2("Funciona vga_write2?", 18, 0xE0);
}

Al final de cada iteración, esto es, de cada incremento, el código del contador invoca a la función yield().⁶ Esta función simplemente invoca, pasando una variable estática como parámetro, a la función task_swap(), que es el verdadero objetivo de este ejercicio:

// Pone en ejecución la tarea cuyo stack está en ‘*esp’, cuyo
// valor se intercambia por el valor actual de %esp. Guarda y
// restaura todos los callee-saved registers.
void task_swap(uintptr_t *esp);

En este ejercicio se pide, siguiendo las instrucciones indicadas:

Reescribir la función contador_run() para que se ejecute cada contador en un stack separado:

void contador_run() {
    // Configurar stack1 y stack2 con los valores apropiados.
    uintptr_t *a = ...
    uintptr_t *b = ...

    ...

    // Actualizar la variable estática ‘esp’ para que apunte
    // al del segundo contador.
    ...

    // Lanzar el primer contador con task_exec.
    task_exec(...);
}

Consideraciones:

la configuración del stack del primer contador, que se ejecuta con task_exec(), será muy similar a las realizadas en la función two_stacks_c() del ejercicio kern2-exec.
la configuración del segundo contador es más compleja, y seguramente sea mejor realizarla tras implementar task_swap(); pues se debe crear artificialmente el stack tal y como lo hubiera preparado esta función.

Explicar, para el stack de cada contador, cuántas posiciones se asignan, y qué representa cada una.

Implementar en tasks.S la función task_swap(). Como se indicó arriba, esta función recibe como parámetro la ubicación en memoria de la variable esp que apunta al stack de la tarea en “stand-by”. La responsabilidad de esta función es:
- guardar, en el stack de la tarea actual, los registros que son callee-saved
- cargar en %esp el stack de la nueva tarea, y guardar en la variable esp el valor previo de %esp
- restaurar, desde el nuevo stack, los registros que fueron guardados por una llamada previa a task_swap(), y retornar (con la instrucción ret) a la nueva tarea.
Para esta función, se recomienda no usar el preámbulo, esto es, no modificar el registro %ebp al entrar en la función.

Ej: kern2-exit ★

En la función contador_run() del ejercicio anterior, se configuran ambos contadores con el mismo número de iteraciones. Reducir ahora el número de iteraciones del segundo contador, y describir qué tipo de error ocurre.

Si la segunda tarea finaliza antes, le corresponde realizar una última llamada a task_swap() que:

ceda por una vez más el procesador a la primera tarea
anule la variable esp, de manera que la primera tarea no ceda más el control, hasta su finalización

Se podría definir una función a tal efecto:

static void exit() {
    uintptr_t *tmp = ...
    esp = ...
    task_swap(...);
}

Completar la definición, y realizar una llamada a la misma al finalizar el ciclo principal de contador_yield(): ahora debería funcionar el caso en el que la segunda tarea termina primero.

A continuación, eliminar la llamada explícita a exit(), y programar su ejecución vía contador_run(), esto es: al preparar el stack del segundo contador.

Interrupciones: reloj y teclado

Para poder hacer planificación basada en intervalos de tiempo, es necesario tener configurada una interrupción de reloj que de manera periodica devuelva el control de la CPU al kernel. Así, en cada uno de esos instantes el kernel tendrá oportunidad de decidir si corresponde cambiar la tarea en ejecución.

El mismo mecanismo de interrupciones permite también el manejo de dispositivos físicos; por ejemplo, el teclado genera una interrupción para indicar al sistema operativo que se generó un evento (por ejemplo, la pulsación de una tecla).

Ej: kern2-idt

El mecanismo de interrupciones se describe en detalle en IA32-3A, capítulo 6: Interrupt and Exception Handling. El objetivo de este primer ejercicio será la configuración de la tabla de interrupciones (interrupt descriptor table). Para ello, se implementarán las siguientes funciones:

// interrupts.c
void idt_init(void);
void idt_install(uint8_t n, void (*handler)(void));

// idt_entry.S
void breakpoint(void);

A continuación se proporciona una guía detallada.

Definiciones

Tras leer las secciones 6.1–6.5 6.10–6.11 de IA32-3A y las definiciones del archivo interrupts.h, responder:

¿Cuántos bytes ocupa una entrada en la IDT?
¿Cuántas entradas como máximo puede albergar la IDT?
¿Cuál es el valor máximo aceptable para el campo limit del registro IDTR?
Indicar qué valor exacto tomará el campo limit para una IDT de 64 descriptores solamente.
Consultar la sección 6.1 y explicar la diferencia entre interrupciones (§6.3) y excepciones (§6.4).

Variables estáticas

Declarar, en un nuevo archivo interrupts.c dos variables globales estáticas para el registro IDTR y para la IDT en sí:

#include "decls.h"
#include "interrupts.h"

static ... idtr;
static ... idt[...];

A estas variables se accederá desde idt_init() e idt_install().

idt_init()

La función idt_init() debe realizar las siguientes tareas:

inicializar los campos base y limit de la variable global idtr:

idtr.base = (uintptr_t) ...
idtr.limit = ...

mediante la instrucción LIDT, activar el uso de la IDT configurada (inicialmente vacía). Se puede usar la instrucción:
```
1
asm("lidt %0" : : "m"(idtr));
```

kmain()

Para probar el funcionamiento de las rutinas de interrupción, se puede generar una excepción por software con la instrucción INT3. Así, antes de pasar a configurar el reloj, en la función kmain() se añadirá:

void kmain(const multiboot_info_t *mbi) {
    // ...

    two_stacks();
    two_stacks_c();

    // Código ejercicio kern2-idt.
    idt_init();   // (a)
    asm("int3");  // (b)

    vga_write2("Funciona vga_write2?", 18, 0xE0);
}

Si la implementación de idt_init() es correcta, el kernel debería ejecutar la llamada (a) con éxito y lanzar un “triple fault” al llegar en (b) a la instrucción INT3 (puesto que no se instaló aún una rutina para manejarla).⁷

idt_install()

La función idt_install() actualiza en la tabla global idt la entrada correspondiente al código de excepción pasado como primer argumento. El segundo argumento es la dirección de la función que manejará la excepción.

En otras palabras, se trata de completar los campos de idt[n]:

// Multiboot siempre define "8" como el segmento de código.
// (Ver campo CS en `info registers` de QEMU.)
static const uint8_t KSEG_CODE = 8;

// Identificador de "Interrupt gate de 32 bits" (ver IA32-3A,
// tabla 6-2: IDT Gate Descriptors).
static const uint8_t STS_IG32 = 0xE;

void idt_install(uint8_t n, void (*handler)(void)) {
    uintptr_t addr = (uintptr_t) handler;

    idt[n].rpl = 0;
    idt[n].type = STS_IG32;
    idt[n].segment = KSEG_CODE;

    idt[n].off_15_0 = addr & ...
    idt[n].off_31_16 = addr >> ...

    idt[n].present = 1;
}

Una vez implementada, desde idt_init() se deberá instalar el manejador para la excepción breakpoint (T_BRKPT definida en interrupts.h); el manejador será la función breakpoint(), cuya implementación inicial también se incluye:

void idt_init() {
    // (1) Instalar manejadores ("interrupt service routines").
    idt_install(T_BRKPT, breakpoint);

    // (2) Configurar ubicación de la IDT.
    idtr.base = (uintptr_t) ...
    idtr.limit = ...

    // (3) Activar IDT.
    asm("lidt %0" : : "m"(idtr));
}

Definir también, en un nuevo archivo idt_entry.S, una primera versión de la función breakpoint() con una única instrucción IRET:

.globl breakpoint
breakpoint:
        // Manejador mínimo.
        iret

Con esta primera definición, kern2 debería arrancar sin problemas, llegando hasta la ejecución de vga_write2().

Ej: kern2-isr

Cuando ocurre una excepción, la CPU inmediatamente invoca al manejador configurado, esto es, justo tras la instrucción original que produjo la excepción.

Un manejador de interrupciones (en inglés interrupt service routine) es, salvo por algunos detalles, una función común sin parámetros.

Las diferencias principales son:

desde el punto de vista del manejador, en (%esp) se encuentra la dirección de retorno; la CPU, no obstante, añade alguna información adicional a la pila, tal y como se verá en la sesión de GDB que se solicita a continuación.
a diferencia del ejercicio kern2-swap, donde la propia tarea solicitaba un relevo con llamando explícitamente a task_swap(), ahora la tarea es desalojada de la CPU sin previo aviso. Desde el punto de vista de esa tarea original, la ejecución del manejador debería ser “invisible”, esto es, que el manejador deberá restaurar el estado exacto de la CPU antes de devolver el control de la CPU a la tarea anterior.

En este ejercicio se pide:

Una sesión de GDB que muestre el estado de la pila antes, durante y después de la ejecución del manejador.
Una implementación ampliada de breakpoint() que imprima un mensaje en el buffer VGA.

Sesión de GDB

Se debe seguir el mismo guión dos veces:

versión A: usando esta implementación aumentada del manejador:

.globl breakpoint
breakpoint:
        nop
        test %eax, %eax
        iret

versión B: con el mismo manejador, pero cambiando la instrucción IRET por una instrucción RET.

Los pasos a seguir son:

Activar la impresión de la siguiente instrucción ejecutando:
```
1
display/i $pc
```
Poner un breakpoint en la función idt_init() y, una vez dentro, finalizar su ejecución con el comando de GDB finish. Mostrar, en ese momento, las siguientes instrucciones (con el comando disas o x/10i $pc): la ejecución debería haberse detenido en la misma instrucción int3.⁸ Mostrar:
- el valor de %esp (print $esp)
- el valor de (%esp) (x/xw $esp)
- el valor de $cs
- el resultado de print $eflags y print/x $eflags
Ejecutar la instrucción int3 mediante el comando de GDB stepi. La ejecución debería saltar directamente a la instrucción test %eax, %eax; en ese momento:
- imprimir el valor de %esp; ¿cuántas posiciones avanzó?
- si avanzó N posiciones, mostrar (con x/Nwx $sp) los N valores correspondientes
- mostrar el valor de $eflags
Responder: ¿qué representa cada valor? (Ver IA32-3A, §6.12: Exception and Interrupt Handling.)
Avanzar una instrucción más con stepi, ejecutando la instrucción TEST. Mostrar, como anteriormente, el valor del registro EFLAGS (en dos formatos distintos, usando print y print/x).
Avanzar, por última vez, una instrucción, de manera que se ejecute IRET para la sesión A, y RET para la sesión B. Mostrar, de nuevo lo pedido que en el punto 1; y explicar cualquier diferencia entre ambas versiones A y B.

Versión final de breakpoint()

La versión de breakpoint() a entregar simplemente realiza, desde idt_entry.S, la siguiente llamada:

vga_write2("Hello, breakpoint", 14, 0xB0);

siguiendo la estructura:

.globl breakpoint
breakpoint:
        // (1) Guardar registros.
        ...
        // (2) Preparar argumentos de la llamada.
        ...
        // (3) Invocar a vga_write2()
        call vga_write2
        // (4) Restaurar registros.
        ...
        // (5) Finalizar ejecución del manejador.
        iret

.data
breakpoint_msg:
        .asciz "Hello, breakpoint"

Como se explicó al comienzo del ejercicio, la ejecución del manejador debe resultar invisible para la tarea original (en este caso, la función kmain). Por tanto, se debe asegurar que todos los registros volvieron a su valor original antes de ejecutar iret.

Incluir las respuestas a las siguientes cuestiones:

Para cada una de las siguientes maneras de guardar/restaurar registros en breakpoint, indicar si es correcto (en el sentido de hacer su ejecución “invisible”), y justificar por qué:

// Opción A.
breakpoint:
    pusha
    ...
    call vga_write2
    popa
    iret

// Opción B.
breakpoint:
    push %eax
    push %edx
    push %ecx
    ...
    call vga_write2
    pop %ecx
    pop %edx
    pop %eax
    iret

// Opción C.
breakpoint:
    push %ebx
    push %esi
    push %edi
    ...
    call vga_write2
    pop %edi
    pop %esi
    pop %ebx
    iret

Responder de nuevo la pregunta anterior, sustituyendo en el código vga_write2 por vga_write. (Nota: el código representado con ... correspondería a la nueva convención de llamadas.)
Si la ejecución del manejador debe ser enteramente invisible ¿no sería necesario guardar y restaurar el registro EFLAGS a mano? ¿Por qué?
¿En qué stack se ejecuta la función vga_write()?

Ej: kern2-irq

Los códigos de excepción 0 a 31 forman parte de la definición de la arquitectura x86 (IA32-3A, §6.3.1); su significado es fijo. Los códigos 32 a 255 están disponibles para su uso bien por el sistema operativo, bien por dispositivos físicos del sistema.

En la arquitectura PC tradicional, la coordinación entre kernel y dispositivos físicos emplea un Programmable Interrupt Controller (PIC) que, entre otras cosas, permite al sistema operativo:

detectar los dispositivos presentes
configurar aspectos de algunos de los dispositivos
asignar a cada uno de ellos un código de interrupción propio

En particular, el procesador i386 dispone de dos PIC 8259 capaces de manejar 8 fuentes de interrupción cada uno; en este lab, usaremos solamente el primero de ellos.

Al arrancar la máquina, no se genera interrupción alguna hasta que se habilita su uso con la instrucción STI. En ese momento, por ejemplo, si se hace uso del teclado, se generaría una interrupción. En kern2, esto se hará desde una nueva función irq_init():

// interrupts.c
void irq_init() {
    // (1) Redefinir códigos para IRQs.
    ...

    // (2) Instalar manejadores.
    ...

    // (3) Habilitar interrupciones.
    asm("sti");
}

// kern2.c
void kmain(const multiboot_info_t *mbi) {
    // ...
    idt_init();
    irq_init();   // Nueva función.
    asm("int3");

    vga_write2("Funciona vga_write2?", 18, 0xE0);
}

Si no se completan los puntos (1) y (2) de la función irq_init(), al ejecutar kern2 se producirá de nuevo un “triple fault” porque —entre otras cosas— el reloj del sistema comienza a lanzar interrupciones para las que no hay un manejador. Se deberá instalar uno que al menos comunique al PIC que se procesó la interrupción:

void irq_init() {
    irq_remap();

    idt_install(T_TIMER, ack_irq);
    idt_install(T_KEYBOARD, ack_irq);

    asm("sti");
}

definiendo, en idt_entry.S:

#define PIC1 0x20
#define ACK_IRQ 0x20

.globl ack_irq:
ack_irq:
        // Indicar que se manejó la interrupción.
        movl $ACK_IRQ, %eax
        outb %al, $PIC1
        iret

Observaciones:

se instala el mismo manejador para el teclado, de manera que tampoco ocurran errores si se presiona una tecla en la ventana de QEMU.
por omisión, el modelo PIC 8259 usa el código 0 para el timer, y el código 1 para el teclado; pero estos códigos de excepción están en conflicto con los códigos propios de la arquitectura x86 (el código 0, por ejemplo, corresponde a un error en una operación DIV)
el propósito de la función irq_remap(), cuyo código se incluye a continuación, es desplazar los códigos de interrupción PIC de tal manera que comiencen en 32, y no en 0.

las constantes T_TIMER y T_KEYBOARD se definieron en el archivo interrupts.h con valores 32 y 33, respectivamente.

#define outb(port, data) \
        asm("outb %b0,%w1" : : "a"(data), "d"(port));

static void irq_remap() {
    outb(0x20, 0x11);
    outb(0xA0, 0x11);
    outb(0x21, 0x20);
    outb(0xA1, 0x28);
    outb(0x21, 0x04);
    outb(0xA1, 0x02);
    outb(0x21, 0x01);
    outb(0xA1, 0x01);
    outb(0x21, 0x0);
    outb(0xA1, 0x0);
}

La necesidad de escribir los manejadores en assembler surge de la obligación de usar iret y no ret para finalizar su ejecución; pero se puede, desde assembler, invocar a rutinas escritas en C, por ejemplo:

// handlers.c
#include "decls.h"

static unsigned ticks;

void timer() {
    if (++ticks == 15) {
        vga_write("Transcurrieron 15 ticks", 20, 0x07);
    }
}

Para poder invocar a esta función:

definir en idt_entry.S un “trampolín” en assembler:

.globl timer_asm
timer_asm:
        // Guardar registros.
        ...
        call timer
        // Restaurar registros.
        ...
        jmp ack_irq

en interrupts.c, instalar timer_asm en lugar de ack_irq para T_TIMER.

Ej: kern2-div

En este último ejercicio se estudia el subtipo particular de excepción llamado fault (ver IA32-3A §6.5 y §6.6).

Cuando ocurre una interrupción, o una excepción de tipo trap, se ejecuta inmediatamente el manejador y, una vez finalizado éste, se reanuda la ejecución de la tarea original en la siguiente instrucción. Por el contrario, para excepciones de tipo fault, se vuelve a intentar la misma instrucción.⁹

La instrucción DIV genera una excepción Divide Error (código numérico 0) cuando, entre otros casos, el divisor es 0. Como la división por 0 también es comportamiento no definido en C, usaremos directamente inline assembly para generar la excepción desde kmain().

Se pide:

Modificar la función kmain() como se indica, y verificar que kern2 arranca e imprime sus mensajes de manera correcta:

void kmain(const multiboot_info_t *mbi) {
    int8_t linea;
    uint8_t color;

    // ...

    idt_init();
    irq_init();

    asm("div %4"
        : "=a"(linea), "=c"(color)
        : "0"(18), "1"(0xE0), "b"(1), "d"(0));

    vga_write2("Funciona vga_write2?", linea, color);
}

Explicar el funcionamiento exacto de la línea asm(...) del punto anterior:
- ¿qué cómputo se está realizando?
- ¿de dónde sale el valor de la variable color?
- ¿por qué se da valor 0 a %edx?
Asignar a %ebx el valor 0 en lugar de 1, y comprobar que se genera una triple falla al ejecutar el kernel.

Definir en write.c una nueva variante de escritura:

void __attribute__((regparm(2)))
vga_write_cyan(const char *s, int8_t linea) {
    vga_write(s, linea, 0xB0);
}

Escribir, en idt_entry.S, un manejador divzero a instalar desde idt_init():
```
1
idt_install(T_DIVIDE, divzero);
```
El manejador debe, primero, incrementar el valor de %ebx, de manera que cuando se reintente la instrucción, ésta tenga éxito.

Asimismo, realizar desde assembly la llamada:
```
1
vga_write_cyan("Se divide por ++ebx", 17);
```
Requerimiento: no usar pusha/popa; guardar y restaurar el mínimo número de registros necesarios.

Ej: kern2-kbd ★

En el archivo handlers.c se incluyen un par de ejemplos de manejo del timer y del teclado. Sobre el código del teclado se pide:

manejar la tecla Shift, y emitir caracteres en mayúsculas cuando esté presionada.

Documentación de ejemplo.

Desalojo ★

En esta sección se implementará un planificador round-robin con desalojo, esto es: ahora las tareas no llamarán a la función yield() sino que la ejecución de todas ellas será intercalada de manera transparente.

El planificador consta de dos partes:

una función spawn() que, dada una función o entry point, deja preparado un struct Task para que la tarea entre en ejecución.
una función sched() que lanza a ejecución la siguiente tarea en estado ready.

Ej: kern2-task

En secciones anteriores, no se definió un struct Task como tal, sino que cada tarea era representada solamente por su stack pointer (ver ejercicio kern2-swap). El set de registros guardados quedaba implícito en la implementación de task_swap(). Además, sólo se almacenaban los registros callee-saved.

Para esta sección definiremos, en un nuevo archivo sched.h, la siguiente definición de tarea:

enum TaskStatus {
    FREE = 0,
    READY,
    RUNNING,
    DYING,
};

struct TaskFrame {
    // Ver ejercicio kern2-spawn más abajo.
};

struct Task {
    uint8_t stack[4096];
    enum TaskStatus status;
    struct TaskFrame *frame;
};

es decir, cada struct Task guarda el stack de la tarea, su estado, y un puntero al “frame” guardado entre ejecuciones.

En lugar de realizar reserva de memoria dinámica de estos structs, en el archivo sched.c se declarará un arreglo estático:

#include "decls.h"
#include "sched.h"

#define MAX_TASK 10

static struct Task Tasks[MAX_TASK];
static struct Task *current;

void sched_init() {
    // ...
}

void spawn(void (*entry)(void)) {
    // ...
}

void sched(struct TaskFrame *tf) {
    // ...
}

Por último, como “bootstrap” del planificador, se necesita una llamada a la función sched_init() desde kmain(), antes de las llamadas a idt_init()/irq_init(). Esto se necesita para que haya una tarea inicial en ejecución.

Esta función debe inicializar la variable global current al primer elemento del arreglo global de tareas, y poner su estado en RUNNING.

Ej: kern2-swap

Para ayudar con la inicialización del stack de una tarea, se define el siguiente struct TaskFrame que sigue el layout en memoria del stack de la tarea cuando ésta se encuentra suspendida:

struct TaskFrame {
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp;
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;
    /* below here defined by x86 hardware */
    uint32_t eip;
    uint16_t cs;
    uint16_t padding;
    uint32_t eflags;
} __attribute__((packed));

De esta manera, queda explícito en qué orden debe restaurarlos la función sched().

La función spawn() debe:

Encontrarn el el arreglo global Tasks, una entrada con estado FREE
Cambiar su status a READY
Inicializar todos sus registros a cero, excepto %cs, %eip y %eflags. En particular %eflags debe contener el flag IF, o las interrupciones de reloj no se habilitarán al entrar la tarea en ejecución.

Asimismo, ya se pueden crear las tareas sobre las que ejecutaremos el planificador, por ejemplo:

static void contador1() {
    contador_yield(50000000, 2, 0x2F);
}

static void contador2() {
    contador_yield(50000000, 3, 0x6F);
}

static void contador3() {
    contador_yield(50000000, 4, 0x4F);
}

void contador_spawn() {
    spawn(contador1);
    spawn(contador2);
    spawn(contador3);
}

Ej: kern2-sched

Para escribir el planificador en C, lo más conveniente es recibir como parámetro el stack pointer de la tarea que fue suspendida por la interrupción del reloj. Para ello, se puede ampliar la función timer_asm() de la siguiente manera:

.globl timer_asm
timer_asm:
    // Guardar registros e invocar handler
    pusha
    call timer

    // Ack *antes* de llamar a sched()
    movl $ACK_IRQ, %eax
    outb %al, $PIC1

    // Llamada a sched con argumento
    push %esp
    call sched

    // Retornar (si se volvió de sched)
    addl $4, %esp
    popa
    iret

La función sched() tiene dos partes bien diferenciadas:

encontrar, de manera round-robin, la siguiente tarea que se encuentra en estado READY. Una posible manera es encontrar en el arreglo la tarea en ejecución, y buscar a partir de ahí:
```
1
2
struct Task *new = 0;
struct Task *old = current;
```

si se la encuentra, se debe poner old->status a READY y guardar en old->frame el frame recibido como parámetro; actualizar la variable global current y en current->status poner RUNNING. Por último, para ejecutar el cambio, se puede usar el siguiente assembler:

asm("movl %0, %%esp\n"
    "popa\n"
    "iret\n"
    :
    : "g"(current->frame)
    : "memory")

El archivo string.c proporcionado no incluye una implementación de strncat(3). Esta implementación alternativa se puede realizar leyendo la documentación de la función, y probándolo en un programa aparte, en espacio de usuario. ↩︎
Es por esto que Linus Torvalds, en su estilo característico, recomienda siempre usar char *buf y nunca char buf[] en la declaración de una función. ↩︎
La opción -nostdlibinc de Clang es precisamente la que se necesita para el kernel; GCC no la tiene, y -nostdinc implementa el punto 1 sin combinarlo con el 3. ↩︎
Si esta versión no arranca, probar a añadir el flag -Wl,--build-id=none, o seguir usando ld directamente. ↩︎
En este contexto, «sin ayuda del sistema operativo» vendría a significar: bien en un solo proceso de usuario sin invocar ninguna llamada al sistema relacionada con la planificación; bien en un kernel básico sin reloj configurado. ↩︎
El verbo yield (en inglés, ceder el paso) es el término que se suele usar para indicar que una tarea cede voluntariamente el uso del procesador a otra. ↩︎
Se aconseja dejar la instrucción INT3 comentada hasta que se implemente idt_init() correctamente. Asimismo, para agilizar el desarrollo, se puede dejar comentada la llamada a contador_run(). ↩︎
Para este ejercicio, se debe evitar poner un breakpoint en la instrucción int3 directamente. ↩︎
Esta funcionalidad es principalmente útil cuando comienza a haber procesos no privilegiados de usuario, ya que se da oportunidad al kernel de decidir qué hacer si un programa muestra un comportamiento anómalo (por ejemplo, intentar escribir en una región de memoria de sólo lectura). ↩︎