TP4: Sistema de archivos e intérprete de comandos¹

Índice

• Código
• Parte 0: Privilegio I/0
  • Tarea: fs_iopl
• Parte 1: caché de bloques
  • Tarea: bc_pgfault
  • Tarea: flush_block
• Parte 2: Bloques de datos
  • Tarea: alloc_block
  • Tarea: file_block_walk
  • Tarea: file_get_block
• Parte 3: interfaz IPC
  • Tarea: serve_read
  • Tarea: serve_write
• Parte 4: spawn() y shell
  • Tarea: sys_env_set_trapframe
  • Tarea: pte_share
  • Tarea: kbd_interrupt
  • Tarea: sh_redir

Código

El código base para el TP se encuentra en la rama tp4 del repositorio, y se añaden —entre otros— los archivos que se indican a continuación.²

Importante: Tras realizar la integración de la base del TP4 con las soluciones anteriores, se debe comprobar que las pruebas del TP3 siguen ejecutándose con éxito. En caso de no hacerlo, quizá hubo algún problema con la integración.

1
2
3
4
5
$ git merge origin/tp4
$ make clean
$ ./grade-lab4
...
Score: 20/20

Importante: Las pruebas del TP3 solamente pasarán si se comentan las siguientes dos líneas (que deberán ser descomentadas una vez pasadas las pruebas del TP3):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
--- kern/init.c
+++ kern/init.c
@@ -56,7 +56,6 @@ i386_init(void)
 	boot_aps();

 	// Start fs.
-	ENV_CREATE(fs_fs, ENV_TYPE_FS);

 #if defined(TEST)
 	// Don't touch -- used by grading script!
--- lib/exit.c
+++ lib/exit.c
@@ -4,7 +4,6 @@
 void
 exit(void)
 {
-	close_all();
 	sys_env_destroy(0);
 }

Parte 0: Privilegio I/0

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

En JOS, el sistema de archivos se implementa en modo usuario mediante un entorno dedicado que actúa de file server para el resto de entornos. El kernel no participa en la lectura y escritura en disco.

Acceder a disco, no obstante, es una operación privilegiada que un proceso común no puede realizar. Pero sí es posible dotar a un proceso de privilegios adicionales para realizar operaciones de entrada y salida.

Este nivel de “privilegio I/O” es distinto al “ring” de ejecución, pues solo afecta a operaciones de entrada y salida. Así, un proceso común puede acceder a disco pero seguir ejecutándose en el ring 3.

Tarea: fs_iopl

Desde la función i386_init() se lanza al arrancar el sistema el proceso file server para que esté disponible una vez se empiecen a lanzar el resto de procesos:

1
2
3
4
5
6
7
8
void i386_init(void) {
    // ...

    // Start fs.
    ENV_CREATE(fs_fs, ENV_TYPE_FS);

    // ...
}

Como se ve, el proceso no es de tipo ENV_TYPE_USER sino de un nuevo tipo ENV_TYPE_FS. Asignar un tipo distinto a este proceso permite dos cosas:

1. Que el resto de procesos con necesidad de acceder a disco puedan ubicarle fácilmente. (Ver la nueva función ipc_find_env() en lib/ipc.c.)

2. Que, en el momento de su creación, el kernel pueda asignar privilegios de entrada y salida a procesos de este tipo.

Esto último es lo que se pide en esta tarea, mediante el valor IOPL de la arquitectura x86. (Ver macros FL_IOPL_N en inc/mmu.h.)

Auto-corrección: Tras implementar esta tarea debería pasar el ítem fs i/o de las pruebas:

1
2
3
4
5
$ make grade
internal FS tests [fs/test.c]: OK
  fs i/o: OK
  ... FAIL
  ...

Parte 1: caché de bloques

1
2
3
$ git show --stat tp4_parte1
 fs/bc.c | 20 ++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

Una vez el proceso ENV_TYPE_FS cuenta con acceso directo al disco y ya se escribieron funciones para leer y escribir de vía el protocolo IDE (ver archivo fs/ide.c), se necesitan implementar al menos tres componentes:

1. manejo consistente de acceso a bloques lógicos (interno a ENV_TYPE_FS)

2. conversión de bloques de filesystem a directorios y archivos (interno a ENV_TYPE_FS)

3. recepción de peticiones de lectura/escritura por parte de otros procesos (interno-externo; comunicación con otros procesos).

El punto 1 se implementará en esta parte, y los dos siguientes puntos en las partes 2 y 3.

DISKMAP

Para facilitarse la tarea, el proceso ENV_TYPE_FS dedica la mayor parte de su espacio de direcciones a mantener una “imagen virtual” del disco; la imagen virtual se mantiene entre 0x10000000 (constante DISKMAP) hasta 0xD0000000 (valor de DISKMAP + DISKSIZE).

Esto quiere decir que, para el proceso ENV_TYPE_FS, el byte de memoria DISKMAP + i siempre contiene (o representa) el byte i-ésimo del disco.³

De esta manera, la implementación del sistema de archivos puede referirse a posiciones de memoria y usar punteros libremente, sabiendo que numéricamente corresponden a posiciones particulares en el disco.

Lecturas y escrituras

Para mantener esta “imagen virtual” de manera perezosa se usa el mecanismo de page faults implementado en el trabajo práctico anterior. Esto es, en ningún momento se lee de disco por adelantado; solamente en el momento que es necesario. Esto último se detecta porque se genera una falla en una dirección comprendida en el rango [DISKMAP, DISKMAP + DISKSIZE). Cuando esto ocurre, el manejador de fallas bc_pgfault() (a implementar en una de las tareas siguientes) lee de disco el bloque afectado y lo inserta en la posición de memoria correspondiente.

• Se recomienda leer la función diskaddr() en el archivo fs/bc.c. ¿Qué es super->s_nblocks?

Las escrituras, por su parte, se manejan con una función específica flush_block() (también a implementar en una de la tareas siguientes). Otras partes de la implementación deberán llamar a esta función para asegurarse que los cambios llegan a disco (por ejemplo, al cerrar un archivo o cambiar sus metadatos).

Como se verá, la función flush_block() solamente escribe a disco si los contenidos del bloque realmente cambiaron.

Tarea: bc_pgfault

Se pide implementar la función bc_pgfault() en fs/bc.c. Esta función es un page fault handler como los implementados en el trabajo práctico anterior. Ante una falla, debe leer el bloque correspondiente de disco e insertarlo en una página nueva en la dirección correspondiente.

Se debe usar la función ide_read() para leer de disco. Esta función toma un número de sector inicial y el número de sectores a leer. Normalmente, un bloque lógico de filesystem lo componen más de un sector de disco (pues estos son de tamaño menor); la proporción entre bloque y sector lo da la constante BLKSECTS (“sectores por bloque”).

Tarea: flush_block

La función flush_block() recibe una dirección en el rango [DISKMAP, DISKMAP + DISKSIZE) y escribe a disco el bloque que contiene a esa dirección.

Para evitar escrituras innecesarias, la función se fija en el bit “dirty” del PTE (representado por la constante PTE_D); la MMU pone este bit a 1 cada vez que hay una escritura en la página correspondiente.

Una vez escrito el bloque, se debe poner el bit dirty a 0 usando sys_page_map(), tal y como se hace al final de la función bc_pgfault().

Auto-corrección: Tras implementar estas tareas deberían pasar los siguentes ítems de las pruebas:

1
2
3
4
5
6
$ make grade
internal FS tests [fs/test.c]: OK
  fs i/o: OK
  check_bc: OK
  check_super: OK
  check_bitmap: OK

Parte 2: Bloques de datos

1
2
3
$ git show --stat tp4_parte2
 fs/fs.c | 50 ++++++++-
 1 file changed, 47 insertions(+), 3 deletions(-)

En el archivo fs/fs.c se implementa el grueso del sistema de archivos, en particular:

• manejo interno de los bloques de cada archivo

• conversión de rutas (/a/b/c/...) a una secuencia de directorios y un archivo final en disco

• todas las operaciones de bajo nivel sobre archivos (open, create, read, write, close).

Los dos últimos ítems ya están implementados, y esta parte se centra en el primero. Dado un struct File:

1
2
3
4
5
6
7
8
9
10
struct File {
    char f_name[MAXNAMELEN]; // filename
    off_t f_size;            // file size in bytes
    uint32_t f_type;         // file type

    // Block pointers.
    // A block is allocated iff its value is != 0.
    uint32_t f_direct[NDIRECT]; // direct blocks
    uint32_t f_indirect;        // indirect block
};

lo que se desea es tener la operación: “dirección en memoria del bloque i-ésimo de f”. Esta primitiva facilita la escritura a bloques “logicamente contiguos” de un archivo, pero que en disco no lo están. Por ejemplo, el siguiente pseudocódigo:

1
2
3
4
5
6
escribir DATA en F:
  nblocks := ⌈len(DATA) / BLKSIZE⌉

  for i := 0 .. nblocks
    addr := file_get_block(F, i)
    memmove(addr, DATA + i*BLKSIZE, BLKSIZE)

Esta primitiva file_get_block() se basará a su vez en otra file_block_walk() a implementar en una de las tareas siguientes.

Tarea: alloc_block

Las primitivas anteriormente descritas a veces reservarán un bloque nuevo para la posición i cuando aún no existe uno. Para ello, es necesario consultar el bitmap de bloques libres y asignar uno.

En esta tarea se pide implementar la función alloc_block() en fs/fs.c que hace precisamente eso.

Se recomienda leer las funciones block_is_free() y free_block() y entender su implementación, pues son el complemento de alloc_block().

Tarea: file_block_walk

Si la función file_get_block() realiza la tarea descrita en la introducción (dirección del bloque i-ésimo de un archivo), la función a implementar aquí file_block_walk() realiza la tarea inmediatamente anterior: determinar el número de bloque global que corresponde al bloque i-ésimo del archivo.

Sin embargo, y de manera similar al pgdir_walk() del TP1, en lugar de devolver el valor del bloque global, devuelve la posición en memoria donde se almacena; esto es, un puntero.

Así, si con la llamada file_block_walk(f, 0) piden el bloque global del primer bloque de f, la respuesta es simplemente &f->f_direct[0].

La única complicación ocurre cuando i >= NDIRECT, pues la dirección a devolver estará en medio del bloque de punteros indirectos. Se recomienda usar la función diskaddr() mencionada anteriormente.

Tarea: file_get_block

Haciendo uso de la primitiva anterior file_block_walk(), implementar la función file_get_block(), ya descrita en párrafos anteriores.

Auto-corrección: Tras implementar estas tareas deberían pasar los siguentes ítems adicionales:

1
2
3
4
5
6
7
$ make grade
internal FS tests [fs/test.c]: OK
  ...
  alloc_block: OK
  file_open: OK
  file_get_block: OK
  file_flush/file_truncate/file rewrite: OK

Parte 3: interfaz IPC

1
2
3
4
$ git show --stat tp4_parte3
 fs/serv.c  | 27 +++++-
 lib/file.c | 10 +-
 2 files changed, 33 insertions(+), 4 deletions(-)

Una vez implementada el sistema de archivos propiamente dicho, queda exponerlo al resto de procesos de usuario del sistema. En JOS, esto se hace en dos layers o capas:

• en primer lugar, el proceso ENV_TYPE_FS ofrece una interfaz con una serie de primitivas para leer, escribir y modificar archivos. Esta capa:

  • está implementada en fs/serv.c
  • pasa como mensaje un union Fsipc, definido en inc/fs.h, que refleja todas las operaciones posibles, y sus argumentos
  • se identifica a los archivos mediante un argumento fileid devuelto por la operación FSREQ_OPEN; este identificador no es un file descriptor y solo es válido para la comunicación directa, vía IPC, con ENV_TYPE_FS.

• en segundo lugar, la biblioteca estándar de JOS implementa una interfaz de filesystem compatible con Unix y basada en file descriptors. Esta capa:

  • está implementada en lib/fd.c
  • asigna números de file descriptor únicos (por proceso) y mantiene la correspondencia entre estos y los archivos abiertos en ENV_TYPE_FS
  • no realiza directamente llamadas IPC a ENV_TYPE_FS sino que usa la abstracción Device (ver struct Dev en inc/fd.h)
  • gracias a esta abstracción, permite usar la misma interfaz para distintos tipos de “open file” (por ejemplo, ya implementados en JOS: pipes y consola); tal y como se hace en Unix. Véase estas tres implementaciones de device:
    • lib/file.c
    • lib/console.c
    • lib/pipe.c

En esta parte nos centraremos solamente en el primer ítem, interfaz IPC; y no en la capa de file descriptors.

Lo anteriormente descrito se puede esquematizar en el siguiente diagrama:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
     Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

Tarea: serve_read

En esta tarea se pide implementar, desde fs/serv.c, la respuesta a una petición de lectura de un archivo ya abierto. La petición contiene el identificador del archivo y la cantidad de bytes a leer; se debe escribir la respuesta en el mismo union Fsipc de entrada, en el campo readRet.

Importante: no escribir más allá del tamaño de ret_buf.

Ayuda: Usar la función file_read() y examinar la función serve_set_size() para observar el uso de openfile_lookup() (la función que transforma un “file id” en un struct Openfile).

Tarea: serve_write

En esta tarea se pide:

• la implementación de serve_write() en fs/serv.c, similar a serve_read() del punto anterior

• completar la implementación del Device archivo en lib/file.c, añadiendo el código faltante en la función devfile_write(). Esta es la función que se invoca desde lib/fd.c cuando se invoca a write() sobre un file descriptor que resulta ser un archivo.

Auto-corrección: Tras implementar estas tareas debe obtenerse:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ make grade
internal FS tests [fs/test.c]: OK (1.5s)
  fs i/o: OK
  check_bc: OK
  check_super: OK
  check_bitmap: OK
  alloc_block: OK
  file_open: OK
  file_get_block: OK
  file_flush/file_truncate/file rewrite: OK
testfile: OK (1.1s)
  serve_open/file_stat/file_close: OK
  file_read: OK
  file_write: OK
  file_read after file_write: OK
  open: OK
  large file: OK

Parte 4: spawn() y shell

1
2
3
4
5
6
7
8
$ git show --stat tp4_parte4
 kern/syscall.c   | 25 ++++++++++++++--
 kern/trap.c      |  8 +++++
 kern/trapentry.S |  2 ++
 lib/fork.c       |  4 ++-
 lib/spawn.c      | 18 ++++++++++-
 user/sh.c        | 12 +++++++-
 6 files changed, 64 insertions(+), 5 deletions(-)

El objetivo de esta parte es tener un sistema operativo que, tras arrancar, permita algún tipo de interacción con el usuario. Para ello hace falta:

• definir qué programa se ejecutará en userspace al finalizar con el arranque

• permitir, mediante un driver de consola, que dicho programa tenga acceso al teclado (hasta ahora, el manejo de teclado de JOS se realizaba exclusivamente en el kernel)

• si se va a permitir la ejecución de programas adicionales, tener una manera de leer ejecutables y lanzarlos a ejecución desde el sistema de archivos

El programa que JOS va a ejecutar tras finalizar el arranque es un shell o intérprete de comandos, ya implementado en user/sh.c (a falta de una pequeña parte en la última tarea del TP).

Lanzar programas a ejecución desde el sistema de archivos está implementado en lib/spawn.c, excepto por los dos ítems que se describen a continuación.

Tarea: sys_env_set_trapframe

El código de la función spawn() es similar al código de load_icode() en el TP2. Simplemente, en lugar de leer el ejecutable de memoria, se lee mediante la función read().

Y si bien spawn() se basa en sys_exofork(), surgen las siguientes dos dificultades con respecto a la implementación de fork():

• se debe dar un stack al nuevo proceso que no sea copia del stack actual. Es más, el proceso esperará recibir en su stack los argumentos correspondientes a la función umain: int argc y char *argv[].

  spawn() realiza esta tarea en la función init_stack(). Esta funcion ya está implementada y no es el objetivo de esta tarea; sin embargo, su lectura y comprensión es altamente instructiva.

• por otra parte, se desea que el nuevo proceso arranque su ejecución en el entry point del binario ELF; pero esto es algo que, hasta ahora, un proceso no podía modificar. (En fork() se resuelve fácil porque el comportamiento de sys_exofork() de copiar los registros es precisamente lo que precisa fork() para su implementación.)

Para este segundo punto se introduce una nueva system call sys_env_set_trapframe() que permite a un proceso modificar, directamente, el struct Trapframe de otro proceso, para que tenga efecto la próxima vez que ese proceso se ejecute.

Para asegurarse un uso seguro de la llamada, el kernel tiene que realizar tres comprobaciones o modificaciones:

• que el Trapframe recibido como parámetro apunta a memoria de usuario válida

• que el proceso no va a salir del ring 3 (esto es, que el CPL de todos sus segmentos es 3)

• que sale con interrupciones habilitadas e IOPL a 0

Tarea: pte_share

Una característica que tienen los file descriptors en JOS es que su estado se mantiene en memoria de usuario y no en el kernel (en tablas y páginas mantenidas por lib/fd.c). Es típico, no obstante, que tras una llamada a fork() o spawn() los file descriptors se preserven.

Actualmente, fork() marcaría esas regiones como copy-on-write, mientras que spawn() no las copiaría en absoluto. Esto quiere decir que un proceso lanzado con spawn() arrancaría sin archivos abiertos; y, en el caso de fork(), la copia realizada al modificar un file descriptor haría que estos cambios ya no se comuniquen a otros procesos con el mismo archivo abierto, ni por ejemplo a ENV_TYPE_FS.

La solución propuesta es la siguiente: marcar este tipo de memoria que debería compartirse entre padres e hijos con un bit especial PTE_SHARE (similar a PTE_COW en el TP3, uno de los bits en PTE_AVAIL) de manera que las funciones que crean procesos sepan cuándo marcar copy-on-write y cuándo simplemente compartir.

En esta tarea se pide:

• modificar la implementación de fork() del TP anterior (en particular duppage() para que, si una página tiene el bit PTE_SHARE, se comparta con el hijo con los mismos permisos.

• implementar, en lib/spawn.c la función copy_shared_pages() que simplemente recorre el espacio de direcciones del padre en busca de páginas marcadas PTE_SHARE para compartirlas.

Tarea: kbd_interrupt

El driver de consola ya se encuentra implementado en JOS (tanto la parte del kernel como en la biblioteca estándar), y solo resta empezar a responder a las interrupciones del teclado, y también las del puerto serie (para que QEMU atienda al teclado en la terminal).

Simplemente:

• añadir un manejador para IRQ_OFFSET+IRQ_KBD que, una vez en trap.c, desemboque en kbd_intr()
• añadir otro manejador para IRQ_OFFSET+IRQ_SERIAL que desemboque en serial_intr()

Con esta tarea implementada ya se puede ejecutar make qemu e interaccionar con el intérprete de comandos, por ejemplo ejecutando ls.

Tarea: sh_redir

La implementación de user/sh.c funciona y solo se pide agregarle la siguiente funcionalidad: poder invocarla mediante sh <script.txt. Para ello, se debe revisar el switch de la función runcmd() y manejar el caso del caracter '<'.

Se debe abrir el archivo t asegurándose que termina en el descriptor 0 (de tal manera que sh lo tome como su entrada estándar). Para ello, será necesario usar la función dup() de JOS, similar a la función dup2() ya existente en Unix.

Auto-corrección: Con el TP completado, deben pasar el resto de pruebas y alcanzarse el puntaje de 150:

1
2
3
4
5
6
7
8
9
10
$ make grade
...
spawn via spawnhello: OK (0.8s)
Protection I/O space: OK (1.0s)
PTE_SHARE [testpteshare]: OK (1.0s)
PTE_SHARE [testfdsharing]: OK (1.0s)
start the shell [icode]: Timeout! OK (5.5s)
testshell: OK (1.8s)
primespipe: OK (7.4s)
Score: 150/150