TP2: Procesos de usuario¹

Este TP guía la implementación de procesos de usuario. En particular, cubre la ejecución de un solo proceso, esto es: una vez inicializado el sistema, el kernel lanzará el programa indicado por línea de comandos y, una vez finalizado este, volverá al monitor de JOS. En futuros TPs se abordará la ejecución de múltiples programas simultáneamente.

Los programas de usuario se encuentran en el directorio user, y la biblioteca estándar en lib. Por ejemplo, el programa user/hello.c:

1
2
3
4
5
6
#include <inc/lib.h>

void umain(int argc, char **argv) {
    cprintf("hello, world\n");
    cprintf("i am environment %08x\n", thisenv->env_id);
}

una vez finalizada la parte 4 se va a poder ejecutar mediante make run-hello-nox:

1
2
3
4
5
6
7
8
9
10
$ make run-hello-nox
[00000000] new env 00001000
hello, world
i am environment 00001000
[00001000] exiting gracefully
[00001000] free env 00001000
Destroyed the only environment - nothing more to do!
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K>

Nota: JOS usa el término environment para referirse a proceso, porque la semántica de los procesos en JOS diverge de la semántica típica en Unix. En esta consigna, se usa “proceso” directamente para environment.

Índice

• Código
• Parte 1: Inicializaciones
  • Tarea: mem_init_envs
  • Tarea: env_init
  • Tarea: env_alloc
  • Tarea: env_setup_vm
  • Tarea: env_init_percpu
• Parte 2: Carga de ELF
  • Tarea: region_alloc
  • Tarea: load_icode
• Parte 3: Lanzar procesos
  • Tarea: env_create
  • Tarea: env_pop_tf
  • Tarea: env_run
  • Tarea: gdb_hello
• Parte 4: Interrupts y syscalls
  • Tarea: kern_idt
  • Tarea: kern_interrupts
  • Tarea: kern_syscalls
• Parte 5: protección de memoria
  • Tarea: user_evilhello
  • Tarea: user_mem_check

Código

El código base para el TP se encuentra en la rama tp2 del repositorio. Esta nueva base añade un número de archivos:

Parte 1: Inicializaciones

1
2
3
4
5
6
7
$ git show --stat tp2_parte1
 kern/env.c  | 10 ++++++++++
 kern/pmap.c |  5 +++++
 2 files changed, 15 insertions(+)

$ wc --words < TP2.md
253

En JOS, toda la información de un proceso de usuario se guarda en un struct Env, el cual se define en el archivo inc/env.h. Env contiene, notablemente, los siguientes campos:

• env_id: identificador numérico del proceso²
• env_parent_id: identificador numérico del proceso padre
• env_status: estado del proceso (en ejecución, listo para ejecución, bloqueado…)

Así como:

• env_pgdir: el page directory del proceso
• env_tf: un struct Trapframe (definido en inc/trap.h) donde guardar el estado de la CPU (registros, etc.) cuando se interrumpe la ejecución del proceso. De esta manera, al reanudar el proceso es posible restaurar con exactitud su estado anterior.

La constante NENV, por su parte, limita la cantidad máxima de procesos concurrentes en el sistema; el límite actual es 1024. Este límite facilita la creación de procesos de la siguiente manera:

• al arrancar el sistema, se pre-reserva un arreglo de NENV elementos struct Env (de manera similar al arreglo pages del TP1)

• al crear procesos, no será necesario reservar memoria de manera dinámica, sino que se usan los struct Env del arreglo

• el arreglo se configura en una lista enlazada env_free_list de la que se puede obtener el siguiente Env libre en O(1). Cuando se destruye un proceso, se reinserta su struct en la lista.

Tanto el arreglo como la lista de procesos libres se definen en kern/env.c:

1
2
3
4
5
6
7
8
// Arreglo de procesos (variable global, de longitud NENV).
struct Env *envs = NULL;

// Lista enlazada de `struct Env` libres.
static struct Env *env_free_list;

// Proceso actualmente en ejecución (inicialmente NULL).
struct Env *curenv = NULL;

Tarea: mem_init_envs

1. Añadir a mem_init() código para crear el arreglo de procesos envs. Se debe determinar cuánto espacio se necesita, e inicializar a 0 usando memset().

2. Mapear envs, con permiso de sólo lectura para usuarios, en UENVS del page directory del kernel.³

Tras esta tarea, la función check_kern_pgdir() debe reportar éxito:

1
2
3
4
5
6
7
$ make qemu-nox
Physical memory: 131072K available, base = 640K ...
check_page_alloc() succeeded!
check_page() succeeded!
check_kern_pgdir() succeeded!
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
check_page_installed_pgdir() succeeded!

Tarea: env_init

Inicializar, en la función env_init() de env.c, la lista de struct Env libres. Para facilitar la corrección automática, se pide que la lista enlazada siga el orden del arreglo (esto es, que env_free_list apunte a &envs[0]).

Tarea: env_alloc

La función env_alloc(), ya implementada, encuentra un struct Env libre y lo inicializa para su uso. Entre otras cosas:

• le asigna un identificador numérico único
• lo marca como listo para ejecutar (ENV_RUNNABLE)
• inicializa sus segmentos de datos y código con permisos adecuados

Se pide leer la función env_alloc() en su totalidad y responder las siguientes preguntas:

1. ¿Qué identificadores se asignan a los primeros 5 procesos creados? (Usar base hexadecimal.)

2. Supongamos que al arrancar el kernel se lanzan NENV procesos a ejecución. A continuación se destruye el proceso asociado a envs[630] y se lanza un proceso que cada segundo muere y se vuelve a lanzar. ¿Qué identificadores tendrá este proceso en sus sus primeras cinco ejecuciones?

Tarea: env_setup_vm

Desde env_alloc() se llama a env_setup_vm() (no implementada) para configurar el page directory correspondiente al nuevo proceso. Implementar esta función siguiendo las instrucciones en el código fuente.

Ayuda: es una función muy corta, y apenas le faltan 3 líneas de código por añadir. Se permite usar memcpy().

Tarea: env_init_percpu

La función env_init() hace una llamada a env_init_percpu() para configurar sus segmentos. Antes de ello, se invoca a la instrucción lgdt. Responder:

• ¿Cuántos bytes escribe la función lgdt, y dónde?
• ¿Qué representan esos bytes?

Bibliografía relevante:

• [IA32-3A]: §2.1.1 — §2.4 — §3.2.2 — §3.5.1 — §3.4
• documentación sobre inline assembly de GCC

Parte 2: Carga de ELF

1
2
3
$ git show --stat tp2_parte2
 kern/env.c | 32 ++++++++++++++++++++++
 1 file changed, 32 insertions(+)

El segundo paso para lanzar un proceso, tras inicializar su struct Env, es copiar el código del programa a memoria para que pueda ser ejecutado. Normalmente, el código se carga del sistema de archivos, pero en JOS no tenemos soporte para discos todavía.

Por el momento, para ejecutar un programa en JOS, el linker empotra el código máquina del programa al final de la imagen del kernel. La posición y tamaño de cada programa disponible se marca con símbolos en el binario. Por ejemplo, el código para ejecutar user/hello.c se puede encontrar así:

1
2
3
4
$ grep user_hello obj/kern/kernel.sym
00008948 A _binary_obj_user_hello_size
f01217f4 D _binary_obj_user_hello_start
f012a13c D _binary_obj_user_hello_end

Es decir, 549 KiB a partir de la dirección de enlazado 0xf01217f4. Ahí en realidad se encuentra un archivo ELF (ver readelf -a obj/user/hello).

En la parte 3, se lanzará el programa mediante:

1
2
3
4
5
6
// Este símbolo marca el comienzo del ELF user/hello.c.
extern uint8_t _binary_obj_user_hello_start[];

// No es necesario indicar el tamaño; env_create()  lo
// encuentra vía las cabeceras ELF.
env_create(_binary_obj_user_hello_start, ENV_TYPE_USER);

O, de manera más sencilla usando la macro ENV_CREATE:

1
ENV_CREATE(user_hello, ENV_TYPE_USER);

Tarea: region_alloc

Se puede usar page_insert() para reservar 4 KiB de memoria en el espacio de memoria de un proceso. Para facilitar la carga del código en memoria, la función auxiliar region_alloc() reserva una cantidad arbitraria de memoria.

Se pide la función region_alloc() siguiendo las instrucciones en su documentación. Atención a los alineamientos.

Ayuda: usar las funciones page_alloc() y page_insert().

Tarea: load_icode

La función load_icode() recibe un puntero a un binario ELF, y lo carga en el espacio de memoria de un proceso en las direcciones que corresponda. En particular, para cada uno de los e_phnum segmentos o program headers de tipo PT_LOAD:

• reserva memsz bytes de memoria con region_alloc() en la dirección va del segmento
• copia filesz bytes desde binary + offset a va
• escribe a 0 el resto de bytes desde va + filesz hasta va + memsz

Se debe, además, configurar el entry point del proceso.

Ayuda: usar las funciones memcpy() y memset() en el espacio de direcciones del proceso, y la documentación de la función.

Bibliografía:

• la sección Program headers de la entrada en Wikipedia sobre ELF
• readelf -l obj/user/hello

Parte 3: Lanzar procesos

1
2
3
4
5
6
$ git show --stat tp2_parte3
 kern/env.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

$ wc --words < TP2.md
687

Una vez llamado a env_init(), el kernel llama a env_create() y env_run():

• env_create() combina todas las funciones de partes anteriores para dejar el proceso listo para ejecución

• env_run() se invoca cada vez que se desea pasar a ejecución un proceso que está listo

Tarea: env_create

Implementar la función env_create() siguiendo la documentación en el código.

Si, por ejemplo, env_alloc() devuelve un código de error, se puede usar el modificador "%e" de la función panic() para formatear el error:

1
2
if (err < 0)
    panic("env_create: %e", err);

Tarea: env_pop_tf

La función env_pop_tf() ya implementada es en JOS el último paso de un context switch a modo usuario. Antes de implementar env_run(), responder a las siguientes preguntas:

1. Dada la secuencia de instrucciones assembly en la función, describir qué contiene durante su ejecución:
   • el tope de la pila justo antes popal
   • el tope de la pila justo antes iret
   • el tercer elemento de la pila justo antes de iret

2. En la documentación de iret en [IA32-2A] se dice:

   If the return is to another privilege level, the IRET instruction also pops the stack pointer and SS from the stack, before resuming program execution.

   ¿Cómo determina la CPU (en x86) si hay un cambio de ring (nivel de privilegio)? Ayuda: Responder antes en qué lugar exacto guarda x86 el nivel de privilegio actual. ¿Cuántos bits almacenan ese privilegio?

Tarea: env_run

Implementar la función env_run() siguiendo las instrucciones en el código fuente. Tras arrancar el kernel, esta función lanza en ejecución el proceso configurado en i386_init().

Nota: El programa por omisión, user/hello.c, imprime una cadena en pantalla mediante la llamada al sistema sys_cputs(). Al no haber implementado aún soporte para llamadas al sistema, se observará una triple falla en QEMU (o un loop de reboots, según la versión de QEMU). En la tarea a continuación se guía el uso de GDB para averiguar cuándo aborta exactamente el programa.

Tarea: gdb_hello

Arrancar el programa hello.c bajo GDB. Se puede usar, en lugar de make qemu-gdb-nox:

1
2
$ make run-hello-nox-gdb
$ make gdb

Se pide mostrar una sesión de GDB con los siguientes pasos:

1. Poner un breakpoint en env_pop_tf() y continuar la ejecución hasta allí.

2. En QEMU, entrar en modo monitor (Ctrl-a c), y mostrar las cinco primeras líneas del comando info registers.

3. De vuelta a GDB, imprimir el valor del argumento tf:

   1
   2
   (gdb) p tf
   $1 = ...
   

4. Imprimir, con x/Nx tf tantos enteros como haya en el struct Trapframe donde N = sizeof(Trapframe) / sizeof(int).

   (Se puede calcular a mano afuera de GDB, o mediante el comando: print sizeof(struct Trapframe) / sizeof(int), utilizando ese resultado en x/Nx tf)

5. Avanzar hasta justo después del movl ...,%esp, usando si M para ejecutar tantas instrucciones como sea necesario en un solo paso:

   1
   2
   (gdb) disas
   (gdb) si M
   

6. Comprobar, con x/Nx $sp que los contenidos son los mismos que tf (donde N es el tamaño de tf).

7. Describir cada uno de los valores. Para los valores no nulos, se debe indicar dónde se configuró inicialmente el valor, y qué representa.

8. Continuar hasta la instrucción iret, sin llegar a ejecutarla. Mostrar en este punto, de nuevo, las cinco primeras líneas de info registers en el monitor de QEMU. Explicar los cambios producidos.

9. Ejecutar la instrucción iret. En ese momento se ha realizado el cambio de contexto y los símbolos del kernel ya no son válidos.

   • imprimir el valor del contador de programa con p $pc o p $eip
   • cargar los símbolos de hello con symbol-file obj/user/hello
   • volver a imprimir el valor del contador de programa

   Mostrar una última vez la salida de info registers en QEMU, y explicar los cambios producidos.

10. Poner un breakpoint temporal (tbreak, se aplica una sola vez) en la función syscall() y explicar qué ocurre justo tras ejecutar la instrucción int $0x30. Usar, de ser necesario, el monitor de QEMU.

Ayuda: muy posiblemente GDB no encuentre la variable tf definida. En ese caso, se recomienda aumentar el nivel de debug en el Makefile, usando -ggdb3 en lugar de -gstabs.

Parte 4: Interrupts y syscalls

Una vez lanzado un proceso, este debe poder interaccionar con el sistema operativo para realizar tareas como imprimir por pantalla o leer archivos. Asimismo, el sistema operativo debe estar preparado para manejar excepciones que deriven de la ejecución de un proceso (por ejemplo, si realiza una división por cero o dereferencia un puntero nulo).

1
2
3
4
5
6
7
8
$ git show --stat tp2_parte4
 kern/syscall.c   | 18 ++++-
 kern/trap.c      | 50 ++++++++++---
 kern/trapentry.S | 59 ++++++++++++++++
 3 files changed, 117 insertions(+), 10 deletions(-)

$ wc --words < TP2.md
960

Bibliografía para esta parte:

• Sección Handling Interrupts and Exceptions y siguientes de la versión MIT de este TP.

• Capítulo 6 de [IA32-3A]: Interrupts and Exception Handling (secciones 6.1 a 6.6 y 6.10 a 6.12).

• Recordatorio de excepciones: capítulo 8 de [BRY2] (introducción y sección 8.1).

• Recordatorio de cambio de privilegio, capítulo 5 de [IA32-3A]: Protection (en especial secciones 5.2, 5.5 y 5.8).

Tarea: kern_idt

En JOS, todas las excepciones, interrupciones y traps se derivan a la función trap(), definida en trap.c. Esta función recibe un puntero a un struct Trapframe como parámetro, por lo que cada interrupt handler debe, en cooperación con la CPU, dejar uno en el stack antes de llamar a trap().

Se debe definir ahora en JOS interrupt handlers para todas las interrupciones de la arquitectura x86 (ver Tabla 6-1 en [IA32-3A]: Protected-Mode Exceptions and Interrupts). Esto se realiza en dos partes:

1. en trap_init(), se usará la macro SETGATE para configurar la tabla de descriptores de interrupciones (IDT), alojada en el arreglo global idt[].

2. previamente, se debe definir cada interrupt handler en trapentry.S. Para no repetir demasiado código, se proporcionan las macros TRAPHANDLER y TRAPHANDLER_NOEC (leer cuidadosamente su documentación). Los nombres de los interrupt handlers tienen que ser distintos a cualquier función definida ya en JOS, por ejemplo el handler para designar a la interrupción breakpoint no se debería llamar breakpoint pues ya existe una función breakpoint() definida en el kernel. Un patrón posible puede ser trap_N, siendo N el número de la interrupción según la tabla de Intel.

   Ambas macros comparten código común en una función _alltraps, que se debe implementar también en assembler.

   Ayuda: cargar GD_KD en %ds y %es mediante un registro intermedio de 16 bits (por ejemplo, %ax). Considerar, además, que GD_KD es una constante numérica, no una dirección de memoria (‘mov $GD_KD’ vs ‘mov GD_KD’).

Tras esta tarea, deben pasar las siguientes pruebas:

1
2
3
4
5
$ make grade
divzero: OK (0.7s)
softint: OK (0.9s)
badsegment: OK (0.9s)
Part A score: 3/3

Responder:

• ¿Cómo decidir si usar TRAPHANDLER o TRAPHANDLER_NOEC? ¿Qué pasaría si se usara solamente la primera?

• ¿Qué cambia, en la invocación de handlers, el segundo parámetro (istrap) de la macro SETGATE? ¿Por qué se elegiría un comportamiento u otro durante un syscall?

• Leer user/softint.c y ejecutarlo con make run-softint-nox. ¿Qué excepción se genera? Si es diferente a la que invoca el programa… ¿cuál es el mecanismo por el que ocurrió esto, y por qué motivos?

Tarea: kern_interrupts

Para este TP, se manejan las siguientes dos excepciones: breakpoint (n.º 3) y page fault (n.º 14). El manejo de excepciones se centraliza en la función trap_dispatch(), que decide a qué otra función de C invocar según el valor de tf->tf_trapno:

• para T_BRKPT se invoca a monitor() con el Trapframe adecuado.
• para T_PGFLT se invoca a page_fault_handler() (ya implementado).

Además, la excepción de breakpoint se debe poder lanzar desde programas de usuario. En general, esta excepción se usa para implementar el depurado de código.⁴

Tras esta tarea, los siguientes tests pasan también:

1
2
3
4
5
6
7
$ make grade
...
faultread: OK (1.0s)
faultreadkernel: OK (1.0s)
faultwrite: OK (1.9s)
faultwritekernel: OK (1.1s)
breakpoint: OK (1.9s)

Tarea: kern_syscalls

Hoy en día, la mayoría de sistemas operativos implementan sus syscalls en x86 mediante las instrucciones SYSCALL/SYSRET (64-bits) o SYSENTER/SYSEXIT (32-bits). Tradicionalmente, no obstante, siempre se implementaron mediante una interrupción por software de tipo trap.

En JOS, se elige la interrupción n.º 48 (0x30) como slot para T_SYSCALL. Tras la implementación de syscalls, el programa user/hello podrá imprimir su mensaje en pantalla.

Pasos a seguir:

1. Definir un interrupt handler adicional en trapentry.S y configurarlo adecuadamente en trap_init().

2. Invocar desde trap_dispatch() a la función syscall() definida en kern/syscall.c. A la hora de especificar los parámetros de la función, se debe respetar la convención de llamada de JOS para syscalls (leer y estudiar el archivo lib/syscall.c).

3. Implementar en syscall() soporte para cada tipo de syscall definido en inc/syscall.h. Se debe devolver -E_INVAL para números de syscall desconocidos.

   Nota: solo hace falta despachar, desde syscall(), cada tipo a las funciones estáticas ya implementadas: SYS_cputs a sys_cputs(), SYS_getenvid a sys_getenvid(), etc.

1
2
3
4
$ make grade
...
testbss: OK (1.0s)
hello: OK (1.0s)

IMPORTANTE: Aplicar el siguiente cambio a user/hello.c:

1
2
3
4
5
6
7
8
9
--- user/hello.c
+++ user/hello.c
@@ -5,5 +5,5 @@ void
 umain(int argc, char **argv)
 {
        cprintf("hello, world\n");
-       cprintf("i am environment %08x\n", thisenv->env_id);
+       cprintf("i am environment %08x\n", sys_getenvid());
 }

Parte 5: protección de memoria

1
2
3
4
5
$ git show --stat tp2_parte5
 kern/pmap.c    | 22 ++++++++++++++++++++++
 kern/syscall.c |  1 +
 kern/trap.c    |  5 +++++
 3 files changed, 28 insertions(+)

En la implementación actual de algunas syscalls ¡no se realiza suficiente validación! Por ejemplo, con el código actual es posible que cualquier proceso de usuario acceda (imprima) cualquier dato de la memoria del kernel mediante sys_cputs(). Ver, por ejemplo, el programa user/evilhello.c:

1
2
// Imprime el primer byte del entry point como caracter.
sys_cputs(0xf010000c, 1);

Tarea: user_evilhello

Ejecutar el siguiente programa y describir qué ocurre:

1
2
3
4
5
6
7
8
9
#include <inc/lib.h>

void
umain(int argc, char **argv)
{
    char *entry = (char *) 0xf010000c;
    char first = *entry;
    sys_cputs(&first, 1);
}

Responder las siguientes preguntas:

• ¿En qué se diferencia el código de la versión en evilhello.c mostrada arriba?
• ¿En qué cambia el comportamiento durante la ejecución?
  • ¿Por qué?
  • ¿Cuál es el mecanismo?

Tarea: user_mem_check

Leer la sección Page faults and memory protection de la consigna original de 6.828 y completar el ejercicio 9:

1. Llamar a panic() en trap.c si un page fault ocurre en el ring 0.

2. Implementar user_mem_check(), previa lectura de user_mem_assert() en kern/pmap.c.

3. Para cada syscall que lo necesite, invocar a user_mem_assert() para verificar las ubicaciones de memoria.

1
2
3
4
5
6
$ make grade
...
buggyhello: OK (1.1s)
buggyhello2: OK (2.1s)
evilhello: OK (0.9s)
Part B score: 10/10