Mis à jour le 7 mars 2006
TD 3 : Système de fichiers

TD 3 : Système de fichiers

Mardi 24 janvier 2006


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  Description du système de fichiers

Le système de fichier est paramétré par trois valeurs: Le fichier contenant ce système de fichier est composé de: La taille totale du fichier est donc nb_block * block_size + 4.

Le superbloc (premier bloc de la partition) contient dans cet ordre: Le numéro d'un inode correspond au numéro du bloc le contenant. Chaque inode contient: La liste des blocs libres est formée (comme dans le cours) de blocs index: chaque bloc index contient les numéros des blocs libres, ainsi que le numéro du bloc index suivant en position 0. Lorsqu'un souhaite utiliser un bloc, et qu'il ne reste plus de blocs libres dans le bloc index courant, on utilise cette valeur comme nouveau bloc index, et on retourne l'ancien bloc index comme bloc à utiliser. Une valeur de bloc index de 0 indique qu'il n'y a plus de tout de blocs libres dans le système de fichiers.

Finalement, les répertoires sont composés d'une suite d'entrées (dirent) contenant un nom de fichier sur filename_max_size octects, terminé par un caractère zéro s'il est plus court que filename_max_size, et d'un numéro d'inode. filename_max_size est fixée à 28. Une entrée d'un répertoire peut être inutilisée (si un fichier a été ajouté puis supprimé), auquel cas le nom du fichier est simplement vide (i.e. le premier octect de l'entrée est 0). Pour rajouter un fichier à un répertoire, il faut donc soit trouver une entrée vide, soit ajouter une entrée au répertoire.

Un exemple de fichier partition est fourni ici: simplefs.bin.gz. On sauvera ce fichier dans le répertoire /tmp/, puis on le décompressera en utilisant la commande gzip -d /tmp/simplefs.bin.gz

2  Vérification

La première étape du TD va consister à s'assurer que le fichier partition précédent n'est pas corrompu avant de l'utiliser. Pour cela, on désire effectuer les vérifications suivantes: On commencera par copier les définitions suivantes dans un fichier disk.ml.

      
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
exception Implementation of string

let get_int8 s pos = int_of_char s.[pos]

let read_int s pos =
  let c4 = get_int8 s pos in
  let c3 = get_int8 s (pos+1) in
  let c2 = get_int8 s (pos+2) in
  let c1 = get_int8 s (pos+3) in
  c1 + (c2 lsl 8) + (c3 lsl 16) + (c4 lsl 24)


let write_int i s pos =
  s.[pos+3] <- char_of_int (i land 255);
  s.[pos+2] <- char_of_int ((i lsr 8) land 255);
  s.[pos+1] <- char_of_int ((i lsr 16) land 255);
  s.[pos] <- char_of_int ((i lsr 24) land 255)

let system_error err call mes = raise (System (errcallmes))

let handle_unix f x =
  try f x with Unix.Unix_error (error,s,mes) -> system_error EIO s
        (Printf.sprintf "%s/%s" mes (Unix.error_message error))

let implementation_error s = raise (Implementation s)

let try_finalize f x finally y =
  let res = try f x with exn -> finally yraise exn in
  finally y;
  res;;

let rec really_read fd buffer start length =
  if length <= 0 then () else
  match Unix.read fd buffer start length with
    0 -> raise End_of_file
  | r -> really_read fd buffer (start + r) (length - r);;

let debug = ref 0 (* 2 mean no debug *)

let to_path name =
  let rec iter name pos len =
    try
  let end_pos = String.index_from name pos '/' in
  let before = String.sub name pos (end_pos - posin
  let after = iter name (end_pos+1) len in
  if before = "" then after else before :: after
    with Not_found ->
    let before = String.sub name pos (len - posin
    if before = "" then [] else [before]
  in
  iter name 0 (String.length name)

Cela définit les fonctions read_int et write_int permettant de lire et d'écrire des entiers dans une chaîne de caractère (sur 4 caractères), ainsi que les fonctions try_finalize, really_read des TDs précédents. Une fonction to_path transformant un nom de fichier en une liste de noms de répertoires est aussi fournie. Enfin, des exceptions System et Implementation correspondant respectivement à des erreurs systèmes et à des erreurs d'implantation sont aussi définies, et pourront être utilisées dans le TD.

Définir un type partition contenant les principales valeurs caractérisant une partition:

(corrigé)
Écrire une fonction open_partition qui prend en argument un nom de fichier et retourne une valeur de type partition initialisée à partir du contenu du fichier.

(corrigé)
Écrire une fonction lseek_block qui positionne le descripteur de fichier de la partition au début du bloc dont le numéro est donné en argument.

(corrigé)
Écrire une fonction read_block qui retourne une chaîne de caractère contenant le contenu du bloc dont le numéro a été passé en argument.

(corrigé)
On définit le type inode avec le code suivant:

      
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 ;
  };;

type inode = {
    stats : stats;
    blocktbl : int array;
    partition : partition;
  }

Écrire une fonction read_inode qui retourne la valeur de type inode associée au numéro d'inode fourni en argument de la fonction.

(corrigé)
Écrire une fonction print_partition qui affiche les informations sur la partition courante.

(corrigé)
On devrait trouver:

      
         block_size: 1024
         block_nb: 20048
         blocktbl_size: 253
         max_file_size: 259072
         inode_nb: 2048
         last_free_inode: 1650
         free_block_list: 9473
         free_block_nb: 7530
         fstypesfs0

Écrire une fonction df qui parcourt la liste des blocs index pour calculer le nombre de blocs libres, et vérifier qu'il est égal à free_block_nb. On testera cette fonction sur le fichier exemple de partition.

(corrigé)
Notre but est d'écrire une fonction fsck qui va vérifier l'état du système de fichiers. Pour cela, nous avons besoin de parcourir l'arborescence des fichiers sur la partition, à partir de l'inode d'un répertoire. Nous allons essayer de le faire de façon générique, afin que notre code puisse être réutilisé par la suite.

Nous définisson un type file_descr pour les descripteurs de fichiers, que nous allons utiliser pour manipuler les fichiers en général, et dans le cas immédiat, les répertoires:

      
type file_descr = { inode : inodemutable pos : intmutable closed : bool }

let open_inode inode =
  {
    inode = inode;
    pos = 0;
    closed = false;
  }

La fonction open_inode ci-dessus associe un descripteur de fichier à un inode. Écrire la fonction correspondant à l'appel système read, dont le type est file_descr -> string -> int -> int -> int. Cette fonction provoque les erreurs EINVAL si les arguments sont invalides (descripteur fermé, chaîne trop courte), ainsi que EIO si le fichier est plus grand que la taille maximale.

(corrigé)
On définit les constantes suivantes:

      
let dirent_size = 32
let filename_max_size = 28

Écrire la fonction read_dirent, de type file_descr -> int * string, qui lit l'entrée suivante du répertoire dont le descripteur a été passé en argument, et qui retourne la paire composée du numéro d'inode et du nom de fichier, ou lève l'exception End_of_file si la fin du répertoire est atteinte.

(corrigé)
En déduire une fonction print_directory, qui prend un inode et son nom de répertoire en argument, et affiche les noms des fichiers qu'il contient, et liste récursivement les sous-répertoires. Tester votre fonction en utilisant l'appel: print_directory (read_inode p p.root_inode) "/"

(corrigé)
Notre fonction fsck doit calculer le type de chaque bloc et son utilisation, afin de vérifier la cohérence du système de fichier. Nous définissons donc ici les valeurs que peuvent prendre les différents blocs du système.

      
type block_type =
  Inode of int    (* Inode, nombre de liens durs observés *)
Block of bool   (* Block, utilisé ou pas *)
IndexBlock      (* Block d'index de la liste des blocs libres *)
Supernode       (* Supernode du système *)
FreeBlock       (* Block libre confirmé *)

let string_of_block t =
  match t with
    Inode n -> Printf.sprintf "inode[%d]" n
  | Block b -> Printf.sprintf "block[%b]" b
  | IndexBlock -> "indexblock"
  | Supernode -> "supernode"
  | FreeBlock -> "freeblock"

Écrire la fonction fsck:

(corrigé)

This document was translated from LATEX by HEVEA and HACHA.