TD 3 : Système de fichiers

Mis à jour le 7 mars 2006

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:

nb_block, le nombre total de blocs sur le disque.
block_size, la taille d'un bloc du disque en octects.
inode_nb, le nombre total d'inodes sur le disque

Le fichier contenant ce système de fichier est composé de:

un superbloc (un bloc),
inode_nb blocs inode,
nb_block - inode_nb - 1 blocs de données, et
la valeur de block_size sur 4 octects.

La taille totale du fichier est donc nb_block * block_size + 4.

Le superbloc (premier bloc de la partition) contient dans cet ordre:

inode_nb, le nombre total d'inodes sur ce disque
last_free_inode, le numéro du bloc contenant le dernier inode libéré.
free_block_list, le numéro d'un bloc index de la liste des blocs libres.
free_block_nb, le nombre de blocs libres.
fstype, une chaîne de 4 caractères permettant d'identifier le type de fichier. Dans notre cas, il doit s'agir de sfs0.
root_inode, le numéro de l'inode correspondant au répertoire racine de la partition (toujours 1 dans notre cas).

Le numéro d'un inode correspond au numéro du bloc le contenant. Chaque inode contient:

kind, le type du fichier, un entier dont la valeur est 0 pour un fichier et 1 pour un répertoire,
nlink, le nombre de liens durs vers ce fichier. Si cette valeur est nulle, l'inode est considéré comme libre, et peut être utilisé pour la création d'un nouveau fichier.
size, la taille du fichier en octects,
blocks[], les numéros des blocs contenant les données du fichier. Le bloc 0 correspond à un bloc rempli de zéros, non encore alloué.

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:

Le compteur de liens durs de chaque inode correspond bien au nombre de fois où le fichier apparaît dans un répertoire.
Un bloc utilisé par un fichier n'apparaît jamais dans la liste des blocs libres.
Tout bloc non-utilisé apparaît bien dans la liste des blocs libres.
Un bloc utilisé par un fichier n'est jamais utilisé par un autre fichier.

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 * stringexception Implementation of stringlet 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 (err, call, mes))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 y; raise 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 - pos) in 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 - pos) in 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:

part_name, le nom du fichier sur le disque
part_fd, le descripteur de fichier correspondant
block_size, la taille des blocs (en octects)
block_nb, le nombre de blocs
part_alive, un booléen indiquant si la partition est activée, c'est a dire si le champ part_fd est toujours ouvert.
block_word_size, le nombre de mots par bloc (entiers de 4 octects dans un bloc)
blocktbl_size, le nombre maximal de blocs dans un fichier, i.e. la taille en mots de la table des blocs d'un inode.
max_file_size, la taille maximale d'un fichier, calculee a partir des proprietes de la partition
blocktbl_offset, la position de la table des blocs dans un inode, en octects.
inode_nb, le nombre d'inodes dans la partition
last_free_inode, le numéro du dernier inode libéré
free_block_list, le numéro du bloc index de la liste de blocs libres
free_block_nb, la position dans ce bloc d'index
fstype, le type de la partition
root_inode, le numéro de l'inode du répertoire racine.

(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_DIRtype 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 fstype: sfs0

É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 : inode; mutable pos : int; mutable 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 = 32let 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:

Créer un tableau contenant le type de chaque bloc au départ.
Parcourir l'arborescence des fichiers à partir de la racine.
- Ne parcourir qu'une fois chaque inode, mais ne pas oublier de changer son type dans le tableau pour correspondre aux nombres de liens durs observés.
- Marquer chaque bloc utilisé par un fichier.
- Se plaindre si un bloc est utilisé par plusieurs fichiers.
- Se plaindre si des blocs non-nuls apparaissent après la fin du fichier.
Parcourir la liste des blocs, et vérifier:
- Que chaque bloc noté libre est bien inutilisé
- Que tous les blocs inutilisés apparaissent dans cette liste.

(corrigé)

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