TD 3 : Représentation des fichiers sur le disque dur

Mardi 31 janvier 2004

Dans ce td nous allons commencer l'implantation d'un système de fichiers simple. Le disque dur sera modélisé en mémoire par un tableau de blocs. Pour commencer, nous allons supposer que le disque dur contient un unique fichier.

1 Le disque

Un disque est constitué de blocs qui contiennent des entiers comme illustré par la figure suivante :

Il est décrit par l'interface suivante :

module type DISKPARAMS = sig val block_size : int val block_nb : int endmodule type DISKDATA = sig include DISKPARAMS val blocks : int array array end

Après avoir sauvé l'interface précédente dans les fichiers disk.mli et disk.ml, ajouter au fichier disk.mli la signature du foncteur Empty :

module Empty (P : DISKPARAMS) : DISKDATA

Compléter le fichier disk.ml avec son implantation qui à partir des paramètres de géométrie du disque, taille des blocs (block_size) et nombre de blocs (block_nb), construit un tableau de blocs vides (blocks) correspondant à ces caractéristiques.

On souhaite maintenant pouvoir récupérer le contenu du disque à partir d'un fichier. Pour cela, ajouter le foncteur Fromfile suivant au fichier disk.mli et écrire son implantation dans le fichier disk.ml.

module type FILENAME = sig val name : string endmodule Fromfile (F : FILENAME) : DISKDATA

L'implantation du foncteur Fromfile initialise les paramètres du disque et son contenu avec les données d'un fichier dont le nom est passé en argument. Le fichier commence par les valeurs block_size et block_nb, stockées en binaire, suivies des blocs d'entiers écrits les uns derrière les autres. Pour lire les entiers stockés dans le fichier en binaire, utiliser input_binary_int.

On souhaite maintenant ajouter aux données du disque les fonctions de lecture et d'écriture, read et write et la fonction dump qui sauve dans un fichier la totalité du disque au format utilisé par Fromfile. Pour cela, ajouter au fichier d'interface disk.mli le foncteur Makedisk suivant :

module type DISK = sig include DISKDATA val read : int -> int array -> int -> unit val write : int -> int array -> int -> unit val dump : string -> unit endmodule Makedisk (P : DISKDATA) : DISK

Ajouter dans le fichier disk.ml son implantation. La fonction read i buffer offset permet de placer les données du bloc d'indice i dans le tampon buffer à partir de la position offset. La fonction write effectue l'opération inverse. On supposera à chaque fois qu'il y a suffisamment de place dans le tampon à partir de la position offset pour lire (resp. recevoir) la totalité d'un bloc. On utilisera une assertion pour vérifier cette propriété.

Dans un autre fichier, tester votre module en créant un disque vide contenant 100 blocs vides de taille 256.

Créer ensuite un disque à partir du contenu du fichiers "MyDisk.img". Vérifiez qu'il contient bien 100 blocs de taille 256.

2 Le système de fichiers

À l'instar du disque, nous allons implanter le système de fichiers sous forme de modules dans des fichiers simplefs.mli et simplefs.ml.

Le système de fichiers offre deux interfaces l'une interne Filesystem pour le programmeur du système de fichiers et l'autre externe UserFs, plus restreinte, pour l'utilisateur. Les interfaces de départ auxquelles nous ajouterons au fur et à mesure les fonctions et les types nécessaires pour la manipulation des fichiers sont les suivantes

module type UserFs = sig exception File_system_exception of string exception File_system_error of string endmodule type Filesystem = sig (* fonctions externes *) include UserFs end

On souhaite écrire le foncteur suivant qui construit un système de fichiers à partir d'un disque.

module Mount : functor (D : Disk.DISK) -> Filesystem

Dans le système de fichiers que nous allons implanter, un inode est stocké sur le disque dans un bloc (ie. un tableau d'entiers de la même taille) et le numéro d'inode correspond au numéro du bloc qui le contient.

Dans un inode, l'entier à l'indice 0 représente le type de l'inode (0 = S_REG, 1 = S_DIR et 2 = S_LNK); l'entier à l'indice 1 contient le nombre de liens vers cet inode; l'entier à l'indice 2 contient la taille du fichier et les autres entiers correspondent à la table des blocs. Il n'y a pas d'indirection dans la table des blocs. La taille maximale d'un fichier est donc : D.block_size * (D.block_size - 3)

Écrire l'implantation de la fonction read_inode qui lit sur le disque l'inode dont le numéro de bloc est passé en argument et retourne son contenu sous la forme d'un type inode.

Pour cela, placer les types file_kind et stats dans le module UserFs.

type file_kind = S_REG | S_DIR | S_LNK type stats = { st_dev : int; st_ino : int; st_kind : file_kind;st_nlink : int; mutable st_size : int}

et les types suivants dans le module Filesystem.

type inode = { mutable reference_number : int; stats : stats; blocktbl : int array } (* identificateur d'un bloc *) type bid = int (* lit un inode depuis un bloc disque *) val read_inode : bid -> inode

Le champs reference_number contient le nombre de descripteurs ouverts sur cet inode, il sera initialisé à 0. Le champs stats contient les différentes informations lues sur disque, dans lequel le numéro de partition (st_dev) est toujours égal à 0. Enfin, le tableau blocktbl contient la table des blocs.

L'inode de la racine de notre arborescence se trouve dans notre système de fichiers dans le bloc 1. Lire son contenu sur le disque est le stocker dans une référence de nom root_inode.

Ajouter au module Filesystem une fonction namei qui retourne l'inode du fichier dont le nom est passé en argument.

(* retourne l'inode associé à un chemin *) (* nous nous restreignons ici à la racine *) val namei : path -> inode

Écrire une premier implantation de cette fonction qui lèvera une exception File_system_exception lorsque le nom passé en argument est différent de / et retourne systématiquement root_inode.

Ajouter au module UserFs une fonction stat ui retourne les informations sur le fichier dont le nom est passé en argument (pour l'instant toujours /).

val stat : string -> stats

Écrire l'implantation de la fonction stat et la tester avec l'inode de la racine.

Définir le type des descripteurs de fichier file_descr qui contient un inode, une position dans le fichier et un mode d'ouverture (O_RDONLY, O_WRONLY, etc.). Pour se simplifier, on pourra décomposer la position courante en un numéro de bloc et une position relative au bloc, puis définir une fonction desc_offset qui retourne la position absolue.

Écrire une fonction openfile qui retourne un descripteur ouvert sur le fichier dont le nom est passé en argument (/ pour nous). On n'utilisera pas les drapeaux O_CREAT et O_EXCL qui ne s'appliquent pas dans notre cas. Dans un premier temps on ignorera les options et on ouvrira systématiauement le fichier en lecture.

Écrire la fonction close qui ferme un descripteur de fichier.

Écrire la fonction read qui a le même comportement que celle du module Unix. Dans un premier temps on ignorera les blocs vides qui peuvent être représentés par le bloc 0.

Écrire l'initialisation du super-bloc en mémoire à partir du contenu du premier bloc disque. Le champ contenant le nombre d'inodes du disque (toujours 1 pour nous) est lu dans le bloc à l'indice 0. Le numéro du premier bloc libre est lu dans le bloc à l'indice 1 et le nombre de numéros de blocs libres, stockés dans ce premier bloc, est lu à l'indice 2 (cf. Cours 2 page 39, on stocke en plus le nombre de blocs libres pour éviter la recherche du 0).

Écrire une fonction write_super_block qui écrit le super-bloc sur le disque.

Écrire la fonction alloc_block qui retourne le numéro du premier bloc libre et met à jour la liste des blocs libres comme vu en cours. S'il n'y a plus de blocs libres, la fonction lève une exception File_system_exception.

Écrire la fonction free_block qui libère le bloc dont le numéro est passé en argument.

Écrire la fonction write_inode qui écrit un inode sur le disque.

Écrire une fonction newfs qui initialise le disque comme un système de fichier vide.

Écrire une fonction qui tronque à la taille 0 le fichier dont l'inode est passé en argument et compléter la fonction openfile.

Écrire la fonction lseek qui permet de changer la position courante du descripteur de fichier. Lorsque lseek déplace le descripteur au delà de la fin du fichier, la taille du fichier n'est pas modifiée. En revanche, dès qu'une écriture aura lieu celle-ci augmentera la taille du fichier. Les blocs intermédiaires ne sont pas alloués, un 0 est laissé dans la table des blocs de l'inode.

Écrire la fonction write.

Écrire la focntion umount qui écrit le contenu du système de fichiers dans un fichier. On prendra soin de bien synchroniser les données représentées comme des structures en mémoire avec celles de notre « disque ».

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.