Mis à jour le 30 janvier 2006
TD 3 : Système de fichiers

TD 3 : Système de fichiers

Mardi 1er février 2005

Dans ce TD nous allons réaliser l'implantation d'un système de fichiers simple. Le disque dur sera modélisé par un fichier et le système par votre programme.

1  Préliminaire

Nous allons commencer par écrire quelques fonctions utilitaires dans un fichier misc.ml, pour nous permettre de lire ou d'écrire des entiers dans des chaînes de caractères. En pratique, on stockerait les entiers sous formes binaires. Cependant pour simplifier la mise au point, on les représentera en ascii sous forme décimale avec des 0 en tête. Ainsi, 7 sera représenté par la chaîne 0007. (Comme la taille des fichiers sera représentée par un entier sur le disque, on sera donc limité à des fichiers de taille inférieure à 10000 octets. Pour aller au delà, il suffira de revenir à une représentation binaire.)

Écrire une fonction read_int : string -> int -> int telle que read_int str offset retourne l'entier stocké en ascii dans la chaîne de caractères str à partir de la position offset. Ainsi, read_int "0123456789" 4 retournera l'entier 4567. On retournera l'entier −1 plutôt que d'échouer si la sous-chaîne ne représente pas un entier. (On pourra utiliser int_of_string et String.sub).
(corrigé)
Écrire la fonction inverse write_int : int -> string -> int -> unit telle que l'appel write_int n str offset écrive l'entier n dans la chaîne str en commençant à la position offset. (On pourra utiliser la fonction Printf.sprintf avec le format "%04d" et la fonction String.blit.)
(corrigé)
Ajouter dans le fichier misc.ml la déclaration de type suivant permettant de reporter différents types d'erreurs de façon uniforme.

      
type system_error =
    | EIO       (* Erreur de bas niveau lors d'un accès au disque *)
    | EACCESS   (* Erreur d'accès *)
    | EISDIR    (* Répertoire trouvé où un fichier régulier est attendu *)
    | ENOTDIR   (* Fichier régulier trouvé où un répertoire est attendu *)
    | EINVAL    (* Argument invalide *)
    | EEXIST    (* Un fichier existe déjà *)
    | ENOENT    (* Un fichier manque *)
    | EBUSY     (* Un fichier est occupé *)
    | ENOSPC    (* Plus d'espace sur le disque *)

exception System of system_error * string * string
let system_error err call mes = raise (System (err, call, mes))

exception Implementation of string
let implementation_error s = raise (Implementation s)
On réservera l'exception Implementation pour reporter des erreurs fatales liées à des erreurs d'implantation (des cas de figures qui ne devraient pas arriver dans un usage normal de la librairie en mode utilisateur).

On utilisera l'exception System pour reporter les erreurs à l'utilisateur de la librairie. On utilisera en particulier les cas suivants:
      
    ....
    | EIO       (* Erreur de bas niveau lors d'un accès au disque *)
    | EACCESS   (* Erreur d'accès *)
    | EISDIR    (* Répertoire trouvé où un fichier régulier est attendu *)
    | ENOTDIR   (* Fichier régulier trouvé où un répertoire est attendu *)
    | EINVAL    (* Argument invalide *)
    | EEXIST    (* Un fichier existe déjà *)
    | ENOENT    (* Un fichier manque *)
    | EBUSY     (* Un fichier est occupé *)
    | ENOSPC    (* Plus d'espace sur le disque *)
    ...
On indiquera en plus le nom de la fonction et une information sur l'argument à l'origine de l'erreur.

On pourra ajouter dans misc.ml d'autres fonctions d'usage général telles que try_finalize ou really_read, etc.

2  Le disque

Un disque est modélisé par un fichier de taille fixée, virtuellement découpé en une suite de blocs de même taille (block_size) et terminé par la taille des blocs écrite sur 4 octets. La taille du fichier représentant le disque, mesurée en octets, devra donc être un multiple de la taille des blocs augmenté de 4. Les blocs devront avoir au moins un taille minimale min_block_size de 32 octets.

Le code produit dans cette section sera placé dans les fichiers disk.mli et disk.ml.

Pour simplifier, tous les types de blocs sont de la même taille et donc pourront être lus et écrits de la même façon.

On va créer un foncteur Opendisk qui prend une structure avec une composante name contenant le chemin désignant le fichier représentant le disque et rend ce fichier visible comme un disque.
      
module type DISK = sig
  val block_size : int
  val block_nb : int
  val read_block : int -> string -> int -> unit
  val write_block : int -> string -> int -> unit
  val close : unit -> unit
  val print : unit -> unit
end
module Opendisk (F : sig val name : string end) : DISK

Dans l'implantation du foncteur Opendisk, commencer par écrire un champ disk (visible seulement dans le module) qui contient un descripteur ouvert sur le fichier représentant le disque.

(corrigé)
Définir et initialiser les champs block_size et block_nb qui contiennent la taille et le nombre total de blocs du disque.

(corrigé)
Définir une fonction lseek_block : int -> unit qui place la position du descripteur disk juste avant le bloc dont le numéro est passé en argument.

(corrigé)
Écrire la fonction close qui désactive le disque (en fermant le descripteur). Les appels suivants à read_block et write_block devront produire une erreur. Pour cela, on pourra ajouter une référence alive permettant de vérifier que le disque est toujours en état de marche avant chaque accès.

(corrigé)
Écrire une fonction read_block : int -> string -> int -> unit telle que read_block n buf offset transfert le bloc n du disque dans le tampon  buf à partir de l'octet offset. On vérifiera que la fonction est appelée avec des paramètres valides. En cas d'erreur de lecture ou d'écriture, on reportera une erreur EIO.

(corrigé)
Écrire une fonction write_block : int -> string -> int -> unit telle que write_block n buf offset effectue le transfert du contenu de  buf à partir de l'octet offset vers le bloc n du disque. En cas d'erreur de lecture ou d'écriture, on reportera un erreur EIO.

(corrigé)
Vous pourrez alors utiliser les fonctions print_block et print suivantes :

      
  let print_block s n =
    let buffer = String.create block_size in
      read_block n buffer 0;
      for i = 0 to block_size - 1 do
        if buffer.[i] = '\000' then buffer.[i] <- '@'
      done;
      Printf.printf "%04d%s" n s;
      for i = 0 to block_size / 4 - 1 do
        Printf.printf "%s " (String.sub buffer (i * 4) 4);
      done;
      print_newline()

  let print () =
    print_newline();
    Printf.printf "      I-NB I-FN B-FL N-FN (super block)\n";
    Printf.printf "      KIND LINK SIZE ... (inode)\n";
    for n = 0 to block_nb -1 do print_block ": " n done;;

Pour tester, vous pouvez utiliser le disque préformaté Simplefs.dbg Le bloc 007 devrait contenir une message...

Vous pouvez aussi créer à partir de rien, par exemple, un disque comportant 16 blocs de 48 octets (pour cela, il faut initialiser le support en créant d'abord un fichier de taille 16 × 58 + 4 avec la taille des blocs, soit 48, écrit sur les 4 derniers octets du fichier). On pourra ensuite tester les fonctions de lecture et d'écriture en écrivant des valeurs dans les blocs et en demandant l'affichage du contenu du disque avec print.
(corrigé)

3  Opérations sur les fichiers

On veut maintenant fournir une structure de fichier au dessus de cette interface de bas niveau. Les blocs qui sont tous équivalents sur le disque vont maintenant être séparés en trois types distincts : Avant de pouvoir utiliser un disque, il faut le formater, c'est-à dire créer un système de fichiers vide. Le formatage sera réalisé par le foncteur Format qui prend un disque et retourne uniquement une fonction mkfs permettant de le formatter.
      
module Format (D : Disk.DISK) : sig val mkfs : int -> unit end

Une fois formaté, un disque pourra être utilisé. Pour cela on utilisera un autre foncteur Mount où la signature USERFS représente l'ensemble des fonctions de manipulation d'un système de fichiers quelconque, disponibles pour l'utilisateur. Ce foncteur devra échouer si le disque n'est pas formaté :
      
module Mount (D : Disk.DISK) : USERFS;;

L'interface USERFS complète qui devra être implémentée à la fin de cette section est la suivante (on l'étendra dans la section 4 pour manipuler les répertoires) :
      
module type USERFS = sig
  open Common
      (* drapeaux d'ouverture de fichier *)
  type open_flag = O_RDWR | O_CREAT

  type file_descr

  type file_perm = int
  val openfile : string -> open_flag list -> file_perm -> file_descr
  val close : file_descr -> unit
      (* mode de positionnement. *)
  type seek_command = SEEK_SET | SEEK_CUR | SEEK_END
  val lseek : file_descr -> int -> seek_command -> int
  val read : file_descr -> string -> int -> int -> int
  val write : file_descr -> string -> int -> int -> int
  val ftruncate : file_descr -> int -> unit

  val stat : string -> stats
  val sync : unit -> unit
  val umount : unit -> unit
end;;
Le comportement des fonctions de ce module correspond autant que possible à celui des fonctions du module Unix de même nom.

À l'instar du formatage, l'implémentation des fonctions données à l'utilisateur nécessitent des fonctions auxilliares pour manipuler (allouer et désallouer) les inodes et les blocks. Ces opérations plus élémentaires sont fournies dans un foncteur Alloc, qui comme les modules Format et Mount, est abstrait par rapport à un module (D : Disk.DISK), i.e prend en argument un tel module. C'est le module Alloc que nous allons implanter en premier.

Définitions préliminaires et fonctions auxiliaires

Afin de pouvoir implanter la signature du module USERFS, nous allons créer un ensemble de fichiers common.ml, cache.ml, simplefs.mli et simplefs.ml.

Les types file_kind et stats qui sont les mêmes pour tous les systèmes de fichiers sont placés dans un fichier common.ml afin d'être partagés simplement entre les différents modules.
      
open Misc
  (* définitions communes à tous les systèmes de fichiers *)
type file_kind = S_REG | S_DIR

type stats = {
    st_dev : int ;
    st_ino : int ;
    mutable st_kind : file_kind ;
    mutable st_nlink : int ;
    mutable st_size : int ;
  };;

L'implantation des fonctions données à l'utilisateur, comme le formatage, nécessite des fonctions internes pour manipuler la structure des fichiers, c'est-à-dire les blocs, les inodes et le super-bloc. Ces opérations élémentaires sont abstraites par rapport à un DISK et fournies par le foncteur Make qui renvoie un type CACHE. Ce dernier contient un module Blk, un module Inode et un module Super. Cette interface et son implantation sont fournies dans le fichier cache.ml. Dans cette implantation, les blocs et les inodes sont cachés dans une table de hachage et écrits sur le disque lorsqu'ils ne sont plus utilisés.

L'interface des modules de CACHE est la suivante :
      
open Misc
open Common

module type CACHE = sig
  module Blk : sig
    val block_size : int
      (* taille des blocs *)
    type blk
      (* type opaque pour représenter les blocs en mémoire, il
         contient entre autres, le numéro du bloc et un tampon
         associé *)
    val bread : int -> blk
       (* prend en argument un numéro de bloc et retourne
          sa représentation mémoire. Indique au cache que la
          représentation mémoire est utilisée. *)
    val bzeros : int -> blk
       (* prend en argument un numéro de bloc et retourne
          sa représentation mémoire remplie de zéros *)
    val read_string : blk -> int -> string -> int -> int -> unit
       (* [ read_string b boff s soff len ] place dans
          la chaîne de caractères [s], à partir de la
          position [soff], [len] caractères lus, à partir
          de la position [boff] dans le bloc représenté
          en mémoire par [b] *)
    val write_string : string -> int -> blk -> int -> int -> unit
       (* [ write_string s soff b boff len ] place dans
          le bloc représenté par [b], à partir de la
          position [boff], [len] caractères lus dans la
          chaîne de caractères [s] à partir de la position
          [soff] *)
    val read_int : blk -> int -> int
       (* [ read_int b boff ] retourne l'entier dont
          les 4 octets de la représentation binaire
          ont été récupérés, à partir de la position
          [boff], dans le bloc représenté par [b] *)
    val write_int : int -> blk -> int -> unit
       (* [ write_int i b boff ] place les 4 octets de
          la représentation binaire de l'entier [i] dans
          le bloc représenté par [b] à partir de la
          position [boff] *)
    val brelse : blk -> unit
       (* Indique au cache que la représentation mémoire du
          bloc passé en argument n'est plus utilisée.
          Doit être exécuté après un bread sur le même bloc. *)
    val sync : unit -> unit
       (* copie sur le disque, tous les blocs dont la
          représentation en mémoire ne correspond pas à
          celle sur le disque *)
  end

  module Inode : sig
    type inode = {
        mutable reference_number : int;
          (* nombre de références actives : descripteurs
             ouverts *)
        stats : stats;
          (* informations de statut *)
        blocktbl : int array
          (* table des blocs *)
      }
      (* type utilisé pour la représentation des inodes en mémoire *)
    val blocktbl_offset : int
      (* offset de la table des blocs dans l'inode *)
    val blocktbl_size : int
      (* taille de la table des blocs *)
    val max_file_size : int
      (* taille maximale d'un fichier *)
    val iget : int -> inode
      (* retourne la représentation mémoire de l'inode dont le numéro est
         passé en argument et incrémente son compteur de références. *)
    val iput : inode -> unit
      (* décrémente le nombre de référence sur l'inode. L'inode peut être
         écrit sur le disque et son cache récupéré lorsqu'il n'est plus
         référencé. *)
    val sync : unit -> unit
      (* synchronise l'ensemble des représentations mémoire
         des inodes avec celles sur le disque *)
    val busy : unit -> int
      (* retourne false si tous les inodes sont libres, true sinon *)
  end

  module Super : sig
    val root_inode : int
      (* numéro du bloc contenant l'inode de la
         racine du système de fichier *)
    val inode_nb : int
      (* nombre total d'inodes dans le système de
         fichiers *)
    val sfstype : unit -> bool
      (* vérifie que le système de fichiers est au format "sfs0" *)
    val force_sfstype : unit -> unit
      (* déclare le système de fichiers au format "sfs0" *)
    val inode_nb_ref : int ref
      (* nombre d'inodes utilisés *)
    val last_free_inode : int ref
      (* le dernier inode libre trouvé *)
    val free_block_list : int ref
      (* liste des blocs libres *)
    val free_block_nb : int ref
      (* nombre de blocs libres *)
    val sync : unit -> unit
      (* synchronise le super-bloc en mémoire avec le disque *)
  end
  val block_nb : int
      (* nombre total de blocs (réguliers et inodes) *)
  val close : unit -> unit
      (* débranche le disque brutalement *)
end
      
module Make (D : Disk.DISK) : CACHE
L'utilisation du module CACHE doit permettre de changer la stratégie du cache sans avoir à changer le reste du programme. Pour cela, on doit respecter les conventions suivantes dans l'écriture du code. Pendant l'exécution du programme les appels aux fonctions bread et brelse, d'une part, et iget et iput, d'autre part, doivent être bien parenthésés pour chaque inode n et pour chaque bloc n. De plus, dans le cas des blocs, on n'autorise pas l'imbrication des parenthèses, ie. un bloc n ouvert ne peut pas être ouvert une deuxième fois avant d'avoir été refermé.

Dans la mesure du possible, on fera en sorte que la fonction qui « prend » un bloc soit aussi celle qui le rende (mais ce n'est pas toujours possible). On fera aussi attention à bien « rendre » les blocs lors de la levée d'exceptions.

Enfin, à la fin de chaque programme de test bien écrit (ie. où tous les descripteurs ont bien été refermés), on devrait pouvoir appeler la primitive umount qui exige que tous les blocs aient étés libérés. Une erreur au moment de umount peut être due au programme test, si un descripteur n'a pas été refermé, ou à la bibliothèque si le parenthèsage n'a pas été bien respecté.

Pour simplifier, on donne un fichier déjà formaté Simplefs.dbg.

On commencera cette partie avec un fichier d'interface simplefs.mli réduit à :
      
module type USERFS = sig end;;
module Mount (D : Disk.DISK) : USERFS;;
Placer dans son fichier implantation simplefs.ml, le début d'implantation du foncteur Alloc qui est abstrait par rapport à un cache (et donc un disque) et qui implantera les fonctions d'allocations de blocs et d'inodes pour notre système de fichiers :
      
module Alloc (C : Cache.CACHE) =
  struct
    open Common
    open C.Blk
    open C.Inode
    open C.Super
    (* Définitions propres à l'accocation des blocs et inodes [À COMLÉTER] *)
      
  end
Le corps du système de fichiers sera dans un module System lui aussi abstrait par rapport au cache, à placer également dans le fichier simplefs.ml.
      
module System (C : Cache.CACHE) =
  struct
    module A = Alloc (C)
    open Common
    open C.Blk
    open C.Inode
    open C.Super
    open A
    (* Définitions propres au système de fichiers [À COMLÉTER] *)
      
  end;;
Enfin, ajouter au fichier simplefs.ml une première implantation, vide, du module vide USERFS :
      
module type USERFS = sig end
      
module Mount (D : Disk.DISK) : USERFS =
  struct
    module C = Cache.Make (D)
    let () =
      if not (C.Super.sfstype()) then
        system_error EINVAL "Mount: fstype" ""
    module F = System(C)
    include Common
    include F
  end;;
(La construction include se comporte comme si on avait recopier le contenu du module: elle définit donc les composantes et les rend visibles dans la suite du module mais aussi dans le module vu de l'extérieur, alors que open n'est que du sucre syntaxique qui permet de référencer les noms d'un autre module sans avoir à les préfixer.)

Ainsi, le module Mount fournit à l'utilisateur une restriction des fonctionalités implémentées (principalement) par le module système. Par la suite, il suffira de compléter la signature USERFS au fur et à mesure que les définitions auront été implémentées dans le module System, sans avoir à changer la définition du module Mount lui-même. Remarquez que le module Mount vérifier que le disk est bien formatté et échoue dans le cas contraire.

Pour compiler la partie 3, on fera donc:
  1. Une fois au début, puis à répéter chaque fois que l'on modifie l'un de ces fichiers, dont dépendent simplefs.mli et simplefs.ml:
          
    ocamlc -c misc.ml disk.mli disk.ml common.ml cache.ml
  2. puis à chaque fois que l'on modifie simplefs.mli ou simplefs.ml:
          
    ocamlc -c simplefs.mli simplefs.ml
On pourra aussi utiliser le fichier Makefile et faire simplement:
      
make simplefs
Pour tester cette partie au fur et à mesure, on pourra d'une part récupérer le programme showdisk.ml qui permet de visualliser le disque: Pour l'utiliser:
      
make showdisk
./showdisk Simplefs.dbg
D'autre part éditer le fichier modèle mestests.ml. Pour exécuter mestests en mode script (pas besoin de le compiler):
      
make mestests
Vous pouvez également exécuter les tests de façon interactive et voir l'évolution du disque en parallèle: Ensuite il suffit d'envoyer les commandes du fichier mestests.ml une à une. L'exécution de D.sync() écrit les caches sur le disque, ie. dans le fichier, donc les modification devraient aussitôt apparaître dans le terminal qui imprime en permanence l'état du fichier vu comme un disque.

Il ne nous reste plus qu'à compléter les modules Alloc et System petit à petit.

Inodes

Dans le système de fichiers que vous allez implanter, un inode est stocké sur le disque dans un bloc (ie. une chaîne de caractères de la même taille) et le numéro d'inode correspond au numéro du bloc qui le contient.

Dans un inode (considéré ici comme un tableau d'entiers de 4 octects), l'entier à l'indice 0 représente le type de l'inode (0 = S_REG et 1 = S_DIR); l'entier à l'indice 1 contient le nombre de liens (« durs ») vers cet inode; l'entier à l'indice 2 contient la taille du fichier en octet et les autres entiers correspondent à la table des blocs (numéros des blocs constituant le fichier). Il n'y a pas d'indirection dans la table des blocs. La taille maximale d'un fichier est donc : (D.block_size / 4 - 3) * D.block_size.



Le module Inode qui est défini dans le fichier cache.ml que vous avez récupéré abstrait l'accès et le cache des inodes comme décrit ci-dessus.

Dans cette première partie, on supposera que le disque ne contient qu'un seul fichier /. On pourra donc court-circuiter les fonction d'allocation/déallocation des inodes que l'on considérera seulement dans la partie 4.

Définir une fonction System.namei : string -> inode (ie. une fonction namei dans le module System) qui pour l'instant « prend » et retourne l'inode de la racine si le nom passé en argument est / et sinon échoue (on pourra/devra utiliser iget).

(corrigé)
Écrire la fonction System.stat qui retourne les informations sur le fichier dont le nom est passé en argument (pour l'instant toujours /). Cette fonction doit prendre soin de « rendre » tout inode « pris » et doit recopier la structure stats avant de la retourner afin d'éviter que l'utilisateur ne puisse en la modifiant modifier celle du « système » (pour plus de sûreté, on aurait dû déclarer un autre type stats isomorphe à Common.stat mais avec des champs non mutables).

On devra trouver 159 pour la taille le fichier / du disque Simplefs.dbg.
(corrigé)

Ouverture et fermeture de fichier

Donner une implantation du type System.file_descr qui doit contenir une valeur de type inode, une position dans le fichier et un état (ouvert ou fermé) codé sur un booléen.

On considérera à terme les flags suivants pour l'ouverture des fichiers :
      
  type open_flag = O_RDWR | O_CREAT
(corrigé)
Définir une première version de la fonction System.openfile qui n'accepte que les flags O_RDONLY et O_CREAT (en même temps) et n'accepte que le chemin /. Les permissions sont ignorées (elles sont incluses dans la signature pour rester compatible avec la librairie Unix). La fonction openfile devra également incrémenter le nombre de référence à l'inode du fichier (au travers d'un appel à iget). correspondant au fichier: ainsi l'inode du fichier sera conservé dans le cache tant que le descripteur sera ouvert.
(corrigé)
Définir la fonction System.close qui ferme un descripteur de fichier. À l'inverse de la fonction openfile elle devra décrémenter le nombre de références à l'inode (au travers d'un appel à iput). Lorsque le nombre de référence est nul, la fonction iput relachera l'inode en le sauvant sur le disque de façon transparente.
(corrigé)

Lecture de fichier

Écrire une fonction System.read dont le comportement doit être similaire à celui de la fonction Unix.read. Dans un premier temps, on pourra ignorer les blocs vides qui sont associés au bloc 0 dans la table des blocs (i.e. on supposera qu'il n'y a pas de tels blocs). On fera particulièrement attention à lever des exceptions pour tous les cas d'erreur.

Vous pouvez dès à présent tester votre programme. En utilisant la librairie Simplefs, écrire un petit programme exécutable testread qui prend un nom de disque et un chemin sur la ligne de commande et affiche le contenu du fichier désigner par le chemin sur le dique. On devra donc pouvoir exécuter:
./testread Simplefs.dbg / | diff - testread.out
et ne trouver aucune différence. On considérera une erreur comme fatale (le programme retournant alors un code d'erreur non nul). On pourra s'inspirer de la fonction copyfile vue dans le cours.
(corrigé)


Super-bloc et liste des blocs libres

Le super-bloc contient dans l'ordre (et avec chaque valeur codée sur 4 octets), le nombre total de blocs affectés aux inodes inode_nb (fixé une fois pour toutes au formatage, ici 1), le dernier inode libre trouvé last_free_inode (utilisé comme point de départ pour chercher les inodes libres), la tête de la liste des blocs libres free_block_list et le nombre de bloc libres free_block_nb. Le reste du bloc est utilisé pour stocker une chaîne de caractères identifiant le système de fichiers (ici on utilise sfs0).


Il est possible de distinguer les inodes des blocs de données à partir de leur numéro. Les blocs de numéro supérieur au nombre d'inodes sont des blocs de donnée.



Le super-bloc est géré via le module Super, il reste à écrire les fonctions de gestion des blocs libres et des inodes libres.

Écrire une fonction Alloc.alloc_block : unit -> bid qui retourne le numéro du premier bloc libre et met à jour la liste des blocs libres comme vu en cours 2 page 36. S'il n'y a plus de bloc libre, la fonction lève une exception ENOSPC.

Écrire une fonction Alloc.free_block : bid -> unit qui libère le bloc dont le numéro est passé en argument et l'ajoute dans la liste des blocs libres.

Modification de fichiers

Écrire une fonction Alloc.itrunc telle que Alloc.itrunc inode size affecte la taille size au fichier associé à l'inode inode. Si la valeur de size est supérieure à la taille du fichier, la table des blocs sera remplie avec le bloc 0, si elle est inférieure, les blocs du fichiers au delà de size seront désalloués.

En déduire la fonction System.ftruncate qui prend un descripteur de fichier plutôt qu'un inode en premier argument. Contrairement à la précédente, celle-ci ne s'appliquer qu'aux fichiers réguliers. (La fonction ftruncate ne modifie pas la position courante de lecture/écriture.)

Écrire une fonction System.lseek comparable à la fonction lseek du module Unix. Attention ! Lorsque lseek déplace la position courante au delà de la fin du fichier, la taille du fichier n'augmente pas et son occupation disque n'est pas modifiée. En revanche, dès qu'une écriture aura lieu celle-ci augmentera la taille et l'occupation disque du fichier. Les blocs intermédiaires ne seront pas alloués, un 0 est placé dans la table des blocs de l'inode pour indiquer que le bloc n'a pas été alloué. Sémantiquement, un bloc 0 représente un bloc dont tous les caractères sont nuls ('\000'), donc lorsque le bloc sera effectivement alloué, pour écrire dedans, on veillera bien à initialiser le bloc avec des caractères nuls.

Écrire une fonction System.write dont le comportement doit être similaire à celui de la fonction Unix.read. Attention ! Il ne faut pas oublier d'allouer les blocs qui n'ont pas encore été alloués.

Synchronisation des données en mémoire

Écrire une fonction Alloc.sync qui écrit le contenu du système de fichiers dans le fichier. On prendra soin de bien synchroniser toutes les données représentées en mémoire avec celles de notre « disque ».

Écrire une fonction USEFS.umount qui effectue un appel à sync, vérifie que plus aucun fichier n'est ouvert (en utilisant Inode.busy) avant de fermer le disque.

(corrigé)




Écrire une fonction de System.mkfs: int -> unit qui prend en argument le nombre d'inodes, et initialise le disque avec un système de fichiers ne contenant que la racine. Pour cela, il faut définir le nombre d'inodes, les initialiser (on pourra utiliser la fonction iput en lui passant une structure de type inode créée manuellement et pas avec iget), chaîner les blocs libres (voir section 3) dans la liste des blocs libres, créer un fichier racine et écrire le super-bloc.

Pour l'instant, nous nous contenterons du seul fichier racine, ayant la sorte S_REG, et on pourra exiger que le node d'inode soit exactement 1 (on traitera le cas général dans la partie suivante).

On peut maintenant ajouter la déclaration suivante au fichier simplefs.mli :
      
module Format (D : Disk.DISK) : sig val mkfs : int -> unit end
et l'implémentation correspondante dans le fichier simplefs.ml :
      
module Format (D : Disk.DISK) = System (Cache.Make(D))


Pour tester

Comme l'interface USERFS du module Simplefs est (presque) un sous-ensemble de la librairie Unix, tout script de manipulation du (seul) fichier / de notre système de fichier peut également être écrit en utilisant le module Unix à la place du module Simplefs.

Cela fournit une façon facile de tester son programme en comparation l'effet d'un script sur (une copie) du fichier / système de fichier Simplefs.dbg avec son effet sur (une copie) d'un vrai fichier Unix Simplefs.out dont les contenus sont au départ identique.

Vous pourrez utiliser le programme de tests testSimplefs.ml fourni: le compiler et l'exécuter. Le programme de test a besoin du fichier Simplefs.tgz.

Il appliquera une série de scripts de difficultés croissantes (il est donc probable que, lorsqu'un test échoue, les suivants échouent également), et pour chaque test indiquera OK ou FAILED.

Les tests ne sont bien sûr pas exhaustifs: ils ne testent pas la cohérence de votre système de fichiers—il faudrait pour cela écrire un programme qui implémente la commande fsck, mais ils devrait éliminer la plupart des erreurs. Lorsqu'un test échoue, vous avez une idée de la fonction en cause, vous pouvez alors refaire des test plus petits et plus spécialisés, et insérer des ordres d'impression du disque pour comprendre ce qui s'est mal passé.

4  Ajout des répertoires

On veut maintenant ajouter des répertoires. Plus précisément, on souhaite compléter dans cette section l'interface USERFS avec les valeurs suivantes (que l'on ajoutera petit à petit) :
      
    type dir_handle
    val opendir : string -> dir_handle
    val readdir : dir_handle -> string
    val closedir : dir_handle -> unit
    val mkdir : string -> file_perm -> unit
    val unlink : string -> unit
Cette partie pourra être testée avec le disque Dirfs.dbg.

Commencez par écrire une fonction Alloc.ialloc: file_kind -> inode qui cherche un inode libre, le « prend », c'est-à-dire augmente son compteur de référence, et le destine à être un fichier (pour l'instant de taille vide) dont la sorte est passée en premier argument.

Écrire une fonction Alloc.iput destinée à remplacer la fonction C.Inode.iput qui, lorsqu'un inode est effectivement désalloué (ie. lorsqu'à la fois son compteur de référence et le nombre de liens sont nuls) désalloue également les blocs qu'il contient. On redonnera aux inodes libres le statut de fichier ordinaire (S_REG).

On peut maintenant implémenter les opérations sur les répertoires. En fait, en interne, les répertoires peuvent être manipulés (ie. lus et écrits comme des fichiers ordinaires), à condition de préserver leur contenu structuré, ie. une suite d'entrées qui sont des paires (name, ino) où ino est le numéro d'inode du fichier désigné par name.

On utilisera donc, autant que possible, les fonctions read, write et lseek déjà écrites pour manipuler le contenu des fichiers.

On limitera la taille des noms à 12 octets, donc la taille des entrées à 16 octets1.
      
  let dirent_size = 16
  let filename_max_size = 12

Chaque répertoire contient toujours les entrées '.' et '..'. Ainsi, chaque fois qu'un répertoire est créé, son nombre de liens initial est 2 et le nombre de liens du répertoire parent est incrémenté. Lorsqu'une entrée du répertoire est supprimée, on place le caractère '\000' (représenté pas \ dans le dessin) dans le premier caractère de l'entrée. Cette entrée libre peut être utilisée ultérieurement si une nouvelle entrée est créée dans le répertoire, mais le répertoire n'est jamais compacté a priori.

Comment retrouver son chemin...

Comme nous l'avons déjà remarqué, un répertoire sera manipulé comme un fichier ordirnaire. On déclarera donc :
      
type dir_handle = file_descr

L'utilisateur ne pourra pas les confondre car la signature USERFS ne révèle pas leur identité.

En déduire la fonction System.closedir.

Écrire une fonction internal_readdir qui prend un descripteur ouvert sur un répertoire et retourne l'entrée suivante du répertoire, sous la forme d'une paire (nom, n) où n est le numéro d'inode du fichier désigné par nom dans ce répertoire.

En déduire la fonction System.readdir.

Le but est maintenant d'écrire une version complète de la fonction namei qui permet de trouver et de « prendre » un inode déterminé par un chemin complet (ici toujours absolu). On pourra (si on le souhaite) écrire les fonctions auxiliares suivantes :

      
  val open_inode : inode -> bool -> inode
  val equal_dirent : string -> string -> bool
  val find_name_in_dir_inode : inode -> string -> inode
  val split_name : string -> string
  val relative_namei : inode -> name

Fabrication d'un répertoire

Écrire la fonction System.mkdir. Pour cela, on pourra utiliser des fonctions auxiliares suivantes :
      
  (* [fill_buffer_with_dirent buffer name n] rempli [buffer] avec le nom
     [name] et le numéro d'inode [n] *)
  val fill_buffer_with_dirent : string -> string -> int -> unit
  (* [add_dirent inode name n] ajoute au répertoire [inode] l'entrée de nom
     [name] et de numéro d'inode [n] *)
  val add_dirent inode -> string -> int

Création, destruction, ouverture de fichiers

Écrire la fonction System.unlink et une nouvelle version de System.openfile.

Écrire la fonction System.opendir.

Formatage

Modifier la fonction System.mkfs pour créer un répertoire à la racine plutôt qu'un fichier ordinaire lorsqu'il y a plusieurs inodes. Attention à la particularité de la racine. On exigera qu'il reste au moins autant de blocs que d'inodes.

Ce document a été traduit de LATEX par HEVEA