Mardi 24 janvier 2006 |
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
inode_nb
blocs inode,
nb_block - inode_nb - 1
blocs de données, et
block_size
sur 4 octects.
nb_block * block_size + 4
.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).
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é.
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./tmp/
, puis on le
décompressera en utilisant la commande gzip -d /tmp/simplefs.bin.gz
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 (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) |
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.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.
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; } |
open_partition
qui prend en argument un nom de
fichier et retourne une valeur de type partition initialisée à partir du
contenu du fichier. 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; } |
lseek_block
qui positionne le descripteur de
fichier de la partition au début du bloc dont le numéro est donné en
argument. 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) |
read_block
qui retourne une chaîne de caractère
contenant le contenu du bloc dont le numéro a été passé en argument. 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 n; really_read p.part_fd buffer 0 p.block_size; buffer with Unix.Unix_error (_,_,_) | End_of_file -> system_error EIO "readblock: Unix_error" p.part_name |
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; } |
read_inode
qui retourne la valeur de type inode
associée
au numéro d'inode fourni en argument de la fonction. 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_size) init_block in { stats = { st_dev = 0; st_ino = n ; st_kind = kind ; st_nlink = nlink; st_size = size; }; blocktbl = blocktbl; partition = p; } |
print_partition
qui affiche les informations
sur la partition courante. 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 |
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 |
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.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 |
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.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; } |
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.(* 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.pos) in 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.(block) in if bid > 0 then let b = read_block p bid in String.blit b pos' buffer 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 |
let dirent_size = 32 let filename_max_size = 28 |
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.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'; inode, String.sub dirent 0 (String.index dirent '\000') |
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) "/"
let rec print_directory inode dirname = let p = inode.partition in let fd = open_inode inode in try while true do let (i, name) = 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 -> () |
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" |
fsck
:
let fsck p = (* init the table of blocks *) let t = Array.create p.block_nb (Block false) in 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.(inode) with 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.(n) in match t.(b) with 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 (inode, name) = 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.(block) with 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.(b) with | 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.(n) with 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.(n) with Block false -> Printf.printf "Forgotten block %d\n" n | _ -> () done; Printf.printf "Scan done\n"; () |
Ce document a été traduit de LATEX par HEVEA