Filesystem que utiliza el mecanismo FUSE (Filesystem in USErspace) provisto por el kernel, que permite definir en modo usuario la implementación de un filesystem.
Tabla de contenidos:
- Estructura del filesystem
- Serialización y guardado persistente
- Carga de archivo persistente en memoria
- Resolución del
path - Eliminación de archivos
- Cómo correr los tests
La estructura del filesystem guardada en memoria RAM, implementada en totalidad de manera estática (sin uso de memoria dinámica) que logra cumplir los requerimientos es la siguiente:
En el nivel más alto, se tiene: used_inodes para registrar la cantidad de inodos que están en uso, un "bitmap" que está representado por un array de bools (en rigor técnico no sería un bitmap porque no está implementado bit a bit, sino con bools, pero cumple el mismo propósito), y un array de inodos que son la estructura esencial del filesystem.
Analizando con más detalle la estructura inodo:
Inspirado en la estructura del VSFS (Very Simple FileSystem), el inodo es una estructura que contiene metadata del archivo que representa, el cual puede ser un directorio o un archivo regular. La metadata disponible incluye el tipo (dir o file), el id del inodo (que es igual a su índice en el array para facilitar un acceso directo), un campo is_empty, y toda la información disponible que contiene el struct stat, que se procede a detallar:
struct stat {
dev_t st_dev; // ID of device containing file
ino_t st_ino; // Inode number
mode_t st_mode; // File type and mode
nlink_t st_nlink; // Number of hard links
uid_t st_uid; // User ID of owner
gid_t st_gid; // Group ID of owner
dev_t st_rdev; // Device ID (if special file)
off_t st_size; // Total size, in bytes
blksize_t st_blksize; // Block size for filesystem I/O
blkcnt_t st_blocks; // Number of 512 B blocks allocated
// Since POSIX.1-2008, this structure supports nanosecond
// precision for the following timestamp fields.
// For the details before POSIX.1-2008, see VERSIONS.
struct timespec st_atim; // Time of last access
struct timespec st_mtim; // Time of last modification
struct timespec st_ctim; // Time of last status change
}Se incluyó el flag de compilación -D_POSIX_C_SOURCE=200809L para permitir guardar los campos de tipo struct timespec y la implementación de la operación de FUSE utimens (de similar uso que la syscall utimensat(2)).
Para emular el bloque de datos de VSFS se utilizó una union de nombre union data, que reserva, en este caso de manera estática, la memoria del elemento más grande para guardar sólo uno de los campos a la vez. Esto permite que el inodo guarde struct inode_dir ó struct inode_file, siendo un inodo de tipo directorio ó de archivo regular, pudiendo ser sólo uno a la vez.
Si el inodo es de tipo file, la union data guarda un array de bytes (uint8), el size actual de dicho array (el size en bytes) está guardado en el struct stat. Un file puede tener contenido de tamaño máximo de 156.25KB (160000 bytes), teniendo el filesystem una capacidad máxima de almacenamiento de 1023 (1024 - el nodo root que es el de índice 0) archivos de 156.25 KB, es decir ~156.09 MB. Esto sería para todos los archivos siendo sólo de tipo file y almacenados en el root o mountpoint.
Si el inodo es de tipo dir, la union data guarda un array de tipo dentry (directory-entry) y un contador del mismo. Un dentry es un key-value pair que almacena el nombre de un archivo o directorio el cual está bajo dicho directorio y el i-number (id de inodo) de dicho archivo o directorio.
Como se mencionó, al ser una union se reserva memoria para el elemento más grande:
- Para un
fileel tamaño es de 160.000 bytes, que sale de tener un array de 160.000 bytes. - Para un
direl tamaño es de 159.748 bytes, que sale de tener: 4 bytes para un uint32 + 1024 entradas de un tamaño de 156 bytes (152 chars de 1 byte + 4 bytes de un uint32).
Por lo tanto, el campo union data para un determinado inodo tendrá siempre 160.000 bytes de tamaño. Cuando se use el inodo como un dir, no se estarán usando 252 bytes del espacio total reservado para la union.
Sabiendo que un inodo posee el siguiente tamaño:
160.156 bytes ó 156.4 KB = 144 bytes del struct stat + 12 bytes de tres uint32 + 160.000 bytes del union data.
Pudiendo variar ligeramente el tamaño del struct stat dependiendo de la implementación específica del sistema operativo.
El filesystem cargado en memoria ocupa un total de:
160.000.772 bytes ó ~156.4 MB = 4 bytes (por 1 uint32) + 1024 bytes (1024 bools, asumiendo una implementación común de 1 bool con 1 char) + 1024 inodos de 160.156 bytes cada uno.
El guardado del filesystem de manera persistente en disco en el filesystem host (desde donde se monta a fisopfs) se realiza con datos binarios utilizando la syscall write(2).
El guardado no es 1:1 a cómo está representado en memoria, se guardan sólo las estructuras utilizadas, omitiendo las vacías. El proceso de describe a continuación de manera secuencial:
Primero se guarda el uint32 used_inodes y el bitmap en su totalidad. En el caso del array de inodos, se guardan sólo los que están siendo utilizados, referenciados por el bitmap y el campo is_empty del inodo mismo. Este guardado es secuencial, es decir, que si se están usando los inodos de i-number 0 y 2, se escriben los bytes del inodo 0 y a continuación se escriben los bytes del inodo 2.
Para cada inodo que se guarda, la información que se escribe en disco, también de manera secuencial y contigua es: el struct stat y los tres uint32 que guardan metadata. A continuación se guardan los bytes de union data dependiente del tipo de inodo.
Para los inodos de tipo file, que poseen el size de bytes usados en struct stat, se guardan sólo los primeros size bytes (que son los bytes en uso).
Para los inodos de tipo dir, se guarda el uint32 dentries_count, y del array de dentries se guardan los primeros dentries_count dentries (que son los dentries en uso).
Cada dentry se guarda en su totalidad, tanto el uint32 como los 152 caracteres.
Al momento de leer el archivo persistente para cargar el filesystem en memoria se realiza primero una inicialización vacía del mismo y luego se cargan los valores guardados leídos de disco, para tomar el lugar de los datos vacíos. El bitmap, que se guarda en totalidad, se utiliza para saber a qué posición del array de inodos pertenece el inodo leído, y cuál debería dejarse vacío.
Resolver un path implica encontrar el inodo que corresponde al archivo que se pretende buscar mediante un string con la estructura de un path.
Se propone un ejemplo de dicha estructura, conocida y estándar: /dirB/dirA/fileA. Por ejemplo alojada en una instancia del filesystem con los siguientes directorios y archivos:
/
├── dirA
├── dirB
│ └── dirA
├── fileA
└── fileB
├── fileA
└── fileB
La estrategia general para la resolución es:
- Si el path es mayor a
MAX_PATHcaracteres se devuelve el error correspondiente. - Acceder al directorio root. Si se buscaba el mismo, se retorna el inodo 0 (reservado para el root).
- Se establece el inodo 0 como directorio
containery se ejecuta el siguiente algoritmo:
Por cada dentry del container:
- Si el path hasta e incluyendo el
containerconcatenado con elnamedel dentry es el path buscado, se retorna el inodo encontrado. Este paso es agnóstico al tipo del inodo.- Si el inodo es un dir, se hace una llamada recursiva al paso 3, usando como
containera este dir.
- Si luego de las iteraciones sobre todo el árbol de directorios no se encontró una concatenación que haga match con el path buscado, se devuelve el error de entidad no existente. Si sí se encontró, se devuelve el inodo encontrado.
Una consecuencia de esta manera de tratar los paths es que sólo puede haber un dentry por directorio con un nombre determinado, un corolario es que un directorio no puede contener un archivo regular y un directorio con el mismo nombre, 1 inodo por nombre.
Otra consecuencia, es que en el peor caso se recorre todo el árbol de directorios, es decir, todos los inodos en uso, hasta encontrar el inodo buscado, ya que este es un approach de fuerza bruta.
Para la eliminación de archivos regulares primero se valida que efectivamente se trate de un archivo regular. Para ello se utiliza la función fs_resolve_path , la cual devuelve un puntero al inodo del archivo en cuestión. Si no se encuentra, se devuelve un error. Y si se encuentra pero no es un archivo regular, también.
Luego se procede a eliminar el dentry correspondiente. Con este motivo se obtiene el path y luego un puntero al inodo del directorio padre que contiene el archivo a eliminar. Entonces se desplazan las entradas restantes del array de dentries para eliminar la entrada correspondiente, y se reduce el contador de entradas del directorio.
Finalmente, se vacía el inodo del archivo y se lo quita del bitmap de inodos.
Con respecto a la eliminación de directorios, se procede de manera similar, pero haciendo las validaciones correspondientes a los directorios.
Los tests, verificados también para el container de docker, requieren de python las utilidades estándar de GNU para funcionar. Se disponibiliza un script para correrlos de manera automatizada, para ello basta correr desde la carpeta fisopfs:
./test.shLas pruebas se encuentran detalladas en el archivo tests/test_main.py, se utilizan sólo bibliotecas estándar de python3, por lo que no se requiere instalar paquetes extras.
Se recomienda correrlos dentro del container de Docker para tener el mismo entorno desde donde las pruebas fueron verificadas, para ello, correr los siguientes comandos:
Para construir la imagen y correr el container:
sudo make docker-buildsudo make docker-runRecompilar dentro del container, el make puede no reconocer el cambio de plataforma así que se recomienda borrar el ejecutable y compilarlo de nuevo:
make clean && makeCorrer el script con pruebas
./test.shSe observará output de stdout así como la cantidad de pruebas que pasaron exitosamente.