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é)
      
type partition = {
    mutable part_name : string;
    mutable part_fd : Unix.file_descr;
    mutable part_alive : bool;
    mutable block_size : int;
    mutable block_nb : int;
    mutable block_word_size : int;

(* for inodes *)
    mutable blocktbl_size : int;
    mutable max_file_size : int;
    mutable blocktbl_offset : int;

(* from the supernode *)
    mutable inode_nb : int;
    mutable last_free_inode : int;
    mutable free_block_list : int;
    mutable free_block_nb : int;
    mutable fstype : string;
    mutable root_inode : int;
  }
É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é)
      
    let open_partition name =
      let  fd = handle_unix (Unix.openfile name [ Unix.O_RDWR ]) 0 in

(* read the last 4 bytes *)
      ignore (Unix.lseek fd  (-4) Unix.SEEK_END);
      let buffer = String.create 4 in
      really_read fd buffer 0 4;
      let size = (Unix.fstat fd).Unix.st_size in
      let block_size = read_int buffer 0 in
      assert ((size - 4) mod block_size = 0);

(* compute some values *)
      let blocktbl_offset = 12  in
      let block_nb =  size / block_size in
      let blocktbl_size = (block_size - blocktbl_offset) / 4 in
      let max_file_size = block_size * blocktbl_size in
      let block_word_size = block_size / 4  in

(* read the superblock *)
      ignore (Unix.lseek fd  0 Unix.SEEK_SET);
      let buffer = String.create block_size  in
      really_read fd buffer 0 block_size;
      let inode_nb = read_int buffer 0 in
      let last_free_inode =  read_int buffer 4 in
      let free_block_list = read_int buffer 8 in
      let free_block_nb = read_int buffer 12 in
      let fstype = String.sub buffer (block_size - 4) 4 in
      let root_inode = 1 in

(* generate the partition value *)
       {
        part_name = name;
        part_fd = fd;
        block_size = block_size;
        block_nb = block_nb;
        part_alive = true;

        block_word_size = block_word_size;

        blocktbl_offset = blocktbl_offset;
        blocktbl_size = blocktbl_size;
        max_file_size = max_file_size;

        inode_nb = inode_nb;
        last_free_inode = last_free_inode;
        free_block_list = free_block_list;
        free_block_nb = free_block_nb;
        fstype = fstype;
        root_inode = root_inode;
      }
É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é)
      
    let lseek_block p n =
      assert (n < p.block_nb);
      ignore (handle_unix (
          Unix.lseek p.part_fd (n * p.block_size)) Unix.SEEK_SET)
É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é)
      
    let read_block p n =
      if not p.part_alive then
        system_error EIO "read_block: not alive" p.part_name;
      let buffer = String.create p.block_size in
      try lseek_block p nreally_read p.part_fd buffer 0 p.block_sizebuffer
      with Unix.Unix_error (_,_,_) | End_of_file ->
          system_error EIO "readblock: Unix_error" p.part_name
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é)
      
    let read_inode p n =
      let buffer = read_block p n in
      let kind =
        match (read_int buffer 0) with
          0 -> S_REG
        | 1 -> S_DIR
        | _ -> system_error EIO "read_inode" "kind" in
      let nlink = read_int buffer 4 in
      let size = read_int buffer 8 in
      if size > p.max_file_size then system_error EIO "read_inode" "size";
      let init_block i = (read_int buffer (i*4 + p.blocktbl_offset)) in
      let blocktbl = Array.init (p.blocktbl_sizeinit_block in
      {
        stats =  { st_dev = 0;
          st_ino = n ;
          st_kind = kind ;
          st_nlink = nlink;
          st_size = size;
        };
        blocktbl = blocktbl;
        partition = p;
      }
Écrire une fonction print_partition qui affiche les informations sur la partition courante.

(corrigé)
      
  let print_partition p =
      Printf.printf "\t block_size: %d\n" p.block_size;
      Printf.printf "\t block_nb: %d\n" p.block_nb;
      Printf.printf "\t blocktbl_size: %d\n" p.blocktbl_size;
      Printf.printf "\t max_file_size: %d\n" p.max_file_size;

      Printf.printf "From Supernode:\n";
      Printf.printf "\t inode_nb: %d\n" p.inode_nb;
      Printf.printf "\t last_free_inode: %d\n" p.last_free_inode;
      Printf.printf "\t free_block_list: %d\n" p.free_block_list;
      Printf.printf "\t free_block_nb: %d\n" p.free_block_nb;
      Printf.printf "\t fstype: %s\n" p.fstype
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é)
      

let df p =
  let rec iter n block pos =
    if block = 0 then n else
    let buffer = read_block p block in
    let next = read_int buffer 0 in
    let n = n + pos + 1 in
    iter n next (p.block_word_size - 1)

  in
  let offset = p.free_block_nb mod p.block_word_size in
  iter 0 p.free_block_list offset
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é)
      

(* lecture sur un descripteur *)
let read desc buffer from len =
  let p = desc.inode.partition in
  if desc.closed then system_error EINVAL "read" "closed descr";
  if desc.inode.stats.st_size > p.max_file_size then
    system_error EIO "read" "Inconsistent file system";
  if len <= 0 || from + len > String.length buffer then
    system_error EINVAL "read" "negative length";
  let len = min len (desc.inode.stats.st_size - desc.posin
  let rec read start len ret =
    if len > 0 then
      let block = desc.pos / p.block_size in
      let pos' = desc.pos mod p.block_size in
      let len' = min len (p.block_size - pos') in
      let bid = desc.inode.blocktbl.(blockin
      if bid > 0 then
        let b = read_block p bid in
        String.blit b posbuffer start len';
      else
        String.fill buffer start len' '\000';
      desc.pos <- desc.pos + len';
      read (start + len') (len - len') (ret + len')
    else ret in
  read from len 0
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é)
      

let rec read_dirent desc =
  let dirent = String.create dirent_size in
(* note that our read always read the desired quantity, except
when the end of file is reached. *)

  let nread = read desc dirent 0 dirent_size in
  if nread = 0 then raise End_of_file else
  if dirent.[0] = '\000' then read_dirent desc else
  let inode = read_int dirent filename_max_size in
  dirent.[filename_max_size] <- '\000';
  inodeString.sub dirent 0 (String.index dirent '\000')
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é)
      

let rec print_directory inode dirname =
  let p = inode.partition in
  let fd = open_inode inode in
  try
    while true do
      let (iname) = read_dirent fd in
      let filename = Filename.concat dirname name in
      Printf.printf "%s\n" filename;
      let inode = read_inode p i in
      match inode.stats.st_kind with
        S_REG -> ()
      | S_DIR ->
          if name <> "." && name <> ".." then
            print_directory inode filename
    done
  with End_of_file -> ()
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é)
      
let fsck p =

(* init the table of blocks *)
  let t = Array.create p.block_nb (Block falsein
  t.(0) <- Supernode;
  for i = 1 to p.inode_nb do
    t.(i) <- Inode 0
  done;

(* iter on the directories *)
  Printf.printf "Scanning directory tree\n";
  let rec fsck_inode inode =
    Printf.printf ".";
    match t.(inodewith
      Inode 0 -> begin
          t.(inode) <- Inode 1;
          let i = read_inode p inode in
          for n = 0 to p.blocktbl_size - 1 do
            let b = i.blocktbl.(nin
            match t.(bwith
              Block false ->
                if p.block_size * n > i.stats.st_size then
                  failwith (Printf.sprintf "Inode %d uses a block after its size" inode);
                t.(b) <- Block true
            | Supernode -> ()
            | _ ->
                failwith (Printf.sprintf "Inode %d uses block %d %s" inode b
                    (string_of_block t.(b)))
          done;
          match i.stats.st_kind with
            S_REG -> ()
          | S_DIR ->
              let fd = open_inode i in
              try
                while true do
                  let (inodename) = read_dirent fd in
                  fsck_inode inode
                done
              with End_of_file ->
                  ()
        end
    | Inode n -> t.(inode) <- Inode (n+1)
    | _ -> failwith (Printf.sprintf "Inode %d is not an inode !" inode)
  in
  fsck_inode p.root_inode;
  Printf.printf "\n";

(* iter on the free block list *)
  Printf.printf "Scanning free block list\n";
  let rec iter block nb =
    if block <> 0 then
    match t.(blockwith
        Block false ->
          Printf.printf "(%d)" nb;
          t.(block) <- IndexBlock;
          let buffer = read_block p block in
          let next = read_int buffer 0 in

          for i = 1 to nb - 1 do
            let b = read_int buffer (i * 4) in
            match t.(bwith
            | Block false -> t.(b) <- FreeBlock
            | _ ->
                failwith (Printf.sprintf "Free Block %d has type %s"
                  b (string_of_block t.(b)))
          done;

          iter next (p.block_word_size - 1)
      | _ ->
          failwith (Printf.sprintf "Block %d is not an index block !" block)

  in
  iter p.free_block_list ( (p.free_block_nb - 1) mod p.block_word_size);
  Printf.printf "\n";

(* scan inodes *)
  for n = 1 to p.inode_nb do
    let i = read_inode p n in
    match t.(nwith
      Inode x -> assert (x = i.stats.st_nlink)
    | _ -> failwith (Printf.sprintf "%d shoudl be an inode !" n)
  done;

  for n = p.inode_nb +1 to p.block_nb - 1 do
    match t.(nwith
      Block false -> Printf.printf "Forgotten block %d\n" n
    | _ -> ()
  done;

  Printf.printf "Scan done\n";
  ()

Ce document a été traduit de LATEX par HEVEA