Consignes

Le rendu de ce TP se fera uniquement par TPLab et consistera en une archive (zip, tar, etc.) contenant impérativement l'arborescence suivante : 

      TP3-votre_login/
         ├─ RAPPORT
         ├─ Makefile
         ├─ question1.c
         ├─ ...
         ├─ test_fichier.c
         ├─ ...
         └─ sfs/
             ├─ Makefile
             ├─ ...
             └─ ...

Attention :

Tout non respect d'une ou plusieurs de ces consignes entrainera automatiquement un retrait de points sur votre note de TP !

Liens utiles

1. Programmation et fichiers

N'oubliez pas que vous pouvez utiliser la commande man pour obtenir la documentation des fonctions C des bibliothèques standards : 

$ man 3 read
$ man 3 fwrite

Le 3 permet de préciser que vous voulez la documentation des fonctions C. (Par exemple, le shell possède une commande read, et par défaut, man read ouvre cette page de documentation. Vous pouvez trouver la liste des sections avec leur numéro dans la documentation de la commande man...)

Préliminaires

Le langage C offre deux interfaces pour les fichiers :

Dans le premier cas, les fichiers sont représentés par un entier appelé descripteur de fichiers, et dans le second cas, par un élément du type FILE.

  1. Écrivez deux programmes copy.c et fcopy.c qui recopient un fichier vers un autre. Une fois compilé, les exécutables s'utiliseront comme la command cp: 

    $ ./copy SOURCE DESTINATION
$ ./fcopy SOURCE DESTINATION

    • le programme copy.c utilisera les fonctions "bas niveau",

    • le programme fcopy.c utilisera les fonctions "haut niveau".

  2. Comparez les temps d'execution des deux programmes en fonction du nombre d'octets que vous lisez à chaque fois (un octet à la fois, ou 2 par 2, ou 1024 par 1024, etc.)

    Décrivez vos tests et les résultats.

Note : pour la version avec fread etc., utilisez un argument size (deuxième argument pour fread et fwrite) de 1, et un argument nmemb (troisième argument pour fread et fwrite) égal au nombre d'octets que vous voulez lire...

La fonction open prend un troisième argument optionnel qui précise les droits d'accès à donner au fichier s'il est créé. Lorsque vous donnez le drapeau O_CREAT, il est important de donner cet argument : 

  int fd = open(..., ... | O_CREAT, 0644);

0644 (644 en octal) donne les droit de lecture et d'écriture à l'utilisateur courant et les droits de lecture aux autres.

Vous pouvez trouver une description complète des droits d'accès avec 

$ man sys_stat.h

1.1. stdin, stdout et stderr

Au lancement d'un processus, 3 descripteurs de fichiers spéciaux sont initialisés :

stdin est ouvert en lecture et est associé au périphérique "clavier", et stdout et stderr sont ouvert en écriture et sont associés au périphérique "terminal".

  1. Il est possible de remplacer printf par un appel à write / fwrite. Testez les deux versions possibles du programme suivant et commentez le résultat : 

    #include <unistd.h>
#include <stdio.h>
#include <string.h>

#define NB 1024

int main() {
    char *msg = "Hello world!";
    int zero = 0;
    int oops;

    // utilisation de ``write``
    write(STDOUT_FILENO, msg, strlen(msg));

    /*
    // utilisation de ``fwrite``
    fwrite(msg, 1, strlen(msg), stdout);
    */

    oops = 1/zero;

    return oops;
}

  2. Décrivez le fonctionnement de la fonction fflush.

1.2. Blocs

  1. Si vous travaillez sur les machines de l'université, le répertoire /tmp/ est accessible en lecture et contient un système de fichiers avec inodes. Vous pouvez faire des tests dans ce répertoire.

  2. Si vous travaillez sur votre portable, vous pouvez facilement créer un système ext? dans un fichier en utilisant les commandes 

    $ dd if=/dev/zero of=fs.ext2 bs=4096 count=1024
$ sudo mkfs.ext2 fs.ext2
$ mkdir EXT2
$ sudo mount fs.ext2 EXT2

    Le répertoire EXT2 contiendra alors un système de fichier ext2 !

    Vous pouvez remplacer ext2 par d'autre systèmes de fichiers comme ext3, ext4, fat...

Chaque partition d'un support de stockage utilise un système de fichiers. Sous Linux, le système de fichier le plus courant est ext4 (successeur de ext2 et ext3).

Tous les systèmes de fichiers "interactifs" découpent les fichiers en blocs de taille fixe. La taille d'un fichier peut donc vouloir dire deux choses distinctes :

  1. Faites (et décrivez) quelques expériences simples pour deviner la taille des blocs de votre système de fichier. (Vous pouvez faire ces expériences sur plusieurs supports / partitions...)

  2. Essayer de créer un fichier qui nécessite des blocs à accès indirect. Comment vous y prenez vous ?

Sur un système Unix (ext? ou similaire), les répertoires occupent en général 4ko sur le disque (la taille d'un bloc).

  1. expliquez pourquoi on ne peut pas avoir de répertoire occupant moins d'un bloc sur le disque

  2. essayez d'obtenir un répertoire qui occupe plus d'un bloc sur le disque. Comment vous y prenez vous ?

1.3. Taille des répertoires

  1. Quelle est la taille des données d'un répertoire ext2/3/4 ? (commande ls -lhd DIR)

  2. Quelle est la taille occupée sur le disque par répertoire ext2/3/4 ? (commande ls -shd DIR)

  3. Est-ce que la taille des fichiers contenus dans le répertoire impacte la taille occupée sur le disque par le répertoire ?

  4. Ajoutez des fichiers dans un répertoire ext2/3/4 jusqu'à ce que sa taille augmente. Qu'elle est sa nouvelle taille ?

  5. Supprimez les fichiers contenus dans le répertoire. Qu'elle est maintenant sa taille ?

1.4. Taille des liens symboliques

La commande suivante permet de créer un lien symbolique LINK pointant vers le chemin TARGET 

$ ln -s TARGET LINK

  1. Qu'elle est la taille occupée sur le disque par un lien symbolique pointant vers un "petit" chemin ?

    Qu'elle est la taille occupée sur le disque par un lien symbolique pointant vers un "grand" chemin ?

  2. À quoi correspond la taille des données (affichée par ls -l) pour un lien symbolique ?

  3. À votre avis, comment est stocké la cible d'un lien symbolique ?

1.5. Fichiers creux

En général, la taille des données est plus petite que la taille occupée sur le support, qui est toujours un multiple de la taille des blocs.

Les fichiers creux (sparse files en anglais) sont une exception. Un tel fichier peut contenir des trous. Le plus simple pour créer un fichier creux est de suivre la procédure suivante :

  1. Écrivez un petit programme C qui permet de créer des fichiers creux.

    Une fois compilé, votre programme s'utilisera comme suit : 

    $ ./sparse FILENAME TOTAL_SIZE

  2. Testez votre programme sur plusieurs partitions pour voir celles qui autorisent de tels fichiers.

    Décrivez comment vous procédez.

  3. Expérimentez avec la commande cp et l'argument --sparse, et expliquez ce que vous observez...

La commande shell truncate (et l'appel système POSIX truncate) permet de modifier la taille d'un fichier :

  • si on augmente la taille, les blocs ajoutés au fichier sont des "trous",

  • si on diminue la taille, les blocs à la fin du fichier sont désalloués.

2. Un système de fichiers tout simple

La seconde partie du TP consiste à regarder les sources d'un système de fichiers très simple, créé pour l'occasion, appelé SFS (Simple FileSystem). L'objectif est de rajouter quelques fonctionnalités à ce système de fichiers.

Il s'agit d'un système de fichiers basé sur une notion très simple d'inode. Les "partitions" SFS sont en fait simplement stockées dans des fichiers standards. Un volume SFS peut donc être vu comme une archive contenant une arborescence de fichiers / répertoires.

Pour compiler SFS, vous devez avoir la bibliothèque de développement libfuse. Sous Debian / Ubuntu, 

$ sudo apt-get install libfuse-dev

devrait suffire.

2.1. Petite visite guidé du code fourni

L'archive contenant le code fourni se trouve ici.

2.1.1. Architecture du projet

Le répertoire sfs contient les fichiers suivants

Makefile

pour compiler les sources

sfs_parameters.h

contenant les paramètres fixes des systèmes de fichiers SFS. Vous pouvez si vous le souhaitez changer les valeurs des trois paramètres de base.

sfs_log.[ch]

contenant une petite fonction de "log" pour enregistrer des informations de debug dans un fichier (sfs.log par défaut)

sfs_volume.[ch]

contenant la gestion de la partition SFS (contenue en fait dans un fichier Unix)

sfs_low_level.[ch]

pour le code bas niveau : manipulation des blocs et des inodes, écriture et lecture, etc. C'est essentiellement dans ce fichier que vous devrez travailler.

sfs_posix.[ch]

contenant le code haut niveau : Autant que possible, les fonctions dans ces fichiers utilisent le même prototype que les appels système correspondant aux appels système POSIX usuels. Par exemple, la fonction sfs_write utilise le même prototype que la fonction write...

sfs_shell.[ch]

contenant un petit shell interactif pour manipuler les systèmes de fichiers SFS

sfs_fuse.[ch]

contenant les définitions nécessaires pour utiliser un système de fichiers SFS avec libfuse

2.1.2. Inodes

SFS est basé sur le type d'inodes suivant : 

  typedef struct inode {
      int type;                         // inode type: S_IFREG, S_IFDIR, S_IFLNK
      int size;                         // size, in bytes of the corresponding file
      int nlinks;                       // number of hard links to this inode (0 means the inode is free)
      int blocks[NB_DIRECT_BLOCKS+2];   // blocks for the data (last 2 blocks for single / double indirection blocks)
  } inode_t;

Les constantes S_IFREG, S_IFDIR, S_IFLNK et NB_DIRECT_BLOCKS sont définies dans le fichiers sfs_volume.h.

Chaque inode est représenté par un entier (type int), avec les constantes suivantes :

2.1.3. Blocs de données

Les blocs de données sont représentés par des tableaux : 

// size (in bytes) of blocks
#define BLOCK_SIZE 512

// type synonym for "raw" bytes
typedef unsigned char byte;

// type synonym for blocks
typedef byte block_t[BLOCK_SIZE];

2.1.4. Fonctions importantes

Les blocs et les inodes sont représentés par des entiers (positifs). Les fonctions sfs_get_inode / sfs_get_block prennent un argument entier et renvoie un pointeur vers l'inode / bloc correspondant.

Attention, ces fonctions ne font aucune vérification sur l'entier qui leur est fourni. Si vous les utilisez avec des entiers trop grands (ou négatifs), le résultat n'est pas spécifié, et votre programme risque de provoquer une erreur de segmentation.

2.1.5. Utilisation "bas niveau"

La compilation produit un exécutable sfs_shell qui lance un interpréteur pour diverses commandes sur les systèmes de fichiers SFS :

Il est possible de préciser un fichier Unix contenant un système de fichiers SFS sur la ligne de commandes avec 

$ ./sfs_shell FILE

Le fichier FILE sera alors automatiquement monté...

Les commandes disponibles dans sfs_shell sont brièvement décrites par la commande help (ou ?). Il s'agit essentiellement des commandes du fichiers sfs_low_level.c. Vous pouvez par exemple :

Le shell SFS ne gère pas l'historique des commandes. Pour cela, vous pouvez utiliser l'utilitaire rlwrap pour lancer le shell SFS: 

$ rlwrap ./sfs_shell [FILE]

2.1.6. Utilisation "haut niveau", libfuse

La compilation produit également un exécutable sfs_fuse.

libfuse est une bibliothèque pour créer des systèmes de fichiers sans modifier le noyau Linux. Il suffit de programmer les fonctions de bases comme open, read, mkdir, etc. et il est possible de manipuler un système de fichier "virtuel" (comme SFS) comme un système de fichiers réel.

Si FILE est un fichier Unix contenant un système de fichiers SFS et si DIR est un répertoire vide, on peut monter le système SFS dans le répertoire avec la commande : 

$ ./sfs_fuse -o use_ino FILE DIR

Toutes les opérations usuelles dans le répertoire DIR seront automatiquement répercutées sur le système de fichiers contenu dans FILE.

Vous pourrez notamment utiliser votre shell habituel pour manipuler des fichiers SFS...

Pour enregistrer les modifications dans le fichier contenant le système SFS, il faut démonter le système de fichiers avec la commande 

$ fusermount -u DIR

Le répertoire sfs contient un script test-fuse.sh qui permet de

La commande sfs_fuse envoie des informations dans le fichier sfs.log du répertoire courant. Il est conseillé de regarder le contenu de ce fichier en lançant la commande 

$ tail -f ./sfs.log

dans un autre terminal...

2.2. Un premier exercice

  1. Compilez le code fourni et lancez le shell SFS : 

    $ rlwrap ./sfs_shell

  2. Créez un système de fichiers dans le fichier TEST.sfs 

    (NULL)% mkfs TEST.sfs

  3. Regarder le contenu de l'inode 2 (la racine) 

    (TEST.sfs)% I 2

    et regarder le contenu du premier bloc de données associé : 

    (TEST.sfs)% H ???
(TEST.sfs)% E ???

    Dans les commandes précédentes, ??? doit être le numero du premier bloc de données de la racine. La première commande affiche le contenu du bloc en hexadécimal et la seconde affiche le contenu du bloc lorsque ses octets sont interprétés comme des entrées de répertoires (type dir_entry_t défini dans sfs_low_level.h).

  4. Initialisez un inode de fichier vide avec la commande 

    (TEST.sfs)% create_file

    et vérifier que l'inode utilisé a bien le type regular file, et une taille de 0 octet.

    Combien de blocs de données sont utilisés par cet inode ?

  5. Ajoutez cet inode dans le repertoire / avec la commande 

    (TEST.sfs)% add_entry 2 NAME ???

    N'oubliez pas d'utiliser le numéro d'inode approprié et de choisir un nom pour le fichier.

  6. Vérifiez que le fichier apparait bien dans les entrées du répertoire racine.

  7. Écrivez une petite chaine de caractères dans ce fichier avec la commande write du shell SFS.

    Vérifiez qu'un nouveau bloc de données à été alloué, et qu'il contient bien la chaine choisie...

  8. Quittez le shell SFS et lancez l'interface fuse : 

    $ ./test-fuse.sh

    Le répertoire TEST doit maintenant contenir le fichier que vous avez créé dans le shell SFS :

    • vous pouvez obtenir son numéro d'inode avec ls -i

    • vous pouvez obtenir sa taille avec ls -l et ls -s

    • vous pouvez visualisez sont contenu avec cat NAME

L'appel système statvfs permet d'obtenir des informations sur un système de fichiers :

La fonction sfs_statvfs du fichier sfs_posix.c contient des appels aux fonction sfs_count_free_blocks et sfs_count_free_inodes qui doivent être définies dans sfs_low_level.h.

Écrivez ces fonctions.

Remarques: vous aurez probablement besoin des fonctions

Le nombre total de blocs et d'inodes sont définis dans le fichier sfs_parameters.h.

Vous pouvez vérifiez que ces fonctions marchent avec la commande info dans le shell SFS, ou bien avec les commandes df et df -i si vous avez monté un volume SFS avec fuse.

2.3. Amélioration du système de fichiers

Pour la suite du TP, vous allez implanter des fonctionnalités manquantes au système de fichier.

Les fonctionnalités à ajouter sont données par ordre croissant de difficulté mais sont indépendantes les unes des autres.

Au total, les modifications demandées pour les quatre dernières questions sont de l'ordre de 120 lignes ajoutées et quelques lignes supprimées.

Une estimation de la taille des modifications est donnée dans chaque question. Il s'agit uniquement d'une indication pour vous donner un ordre de grandeur...

2.3.1. Liens physiques (facile)

Il s'agit d'ajouter la gestions des liens physiques sur les fichiers.

Ajoutez la gestion des liens physiques dans SFS.

Il faudra pour ceci modifier les fonctions sfs_unlink_inode et sfs_link_inode du fichier sfs_low_level.c.

Taille des modifications : quelques lignes pour chacune des fonctions.

Pour tester, vous pouvez utiliser test-fuse.sh et créer des liens physique avec ln : 

$ ln TARGET LINK

Le compteur de liens (visible dans le résultat de ls -l doit passer à 2), et les numéros d'inodes (visible dans le résultat de ls -i) doivent coïncider.

2.3.2. Liens symboliques

Il s'agit maintenant d'ajouter la gestions des liens physiques sur les fichiers. Les liens symboliques sont représentés par des inodes de type S_IFLNK.

Un lien symbolique n'a pas de données réelles, mais il doit contenir un chemin d'accès cible.

Ajoutez la gestion des liens symboliques dans SFS.

Pour ceci, il faut écrire les deux fonctions suivantes :

Ces deux fonctions se trouvent dans le fichier sfs_low_level.c.

Taille des modifications : environ une douzaine de lignes pour chacune des fonctions.

Pour tester, vous pouvez utiliser test-fuse.sh et créer des liens physique avec ln -s : 

$ ln -s TARGET LINK

La commande ls -l doit afficher la cible des liens symbolique...

2.3.3. Blocs à accès indirect

Actuellement, les blocs de données associes à un inode dans SFS sont tous à accès direct. Le tableau blocks contenu dans un inode contient NB_DIRECT_BLOCKS cases référençant des blocs de données. La taille maximale d'un fichier est donc égale a NB_DIRECT_BLOCKS * BLOCK_SIZE, soit quelques kibioctets...

Pour augmenter légèrement la taille possible des fichiers, nous allons ajouter la gestion de blocs indirects. Le tableau blocks d'un inode contient une case supplémentaire, actuellement non utilisée. Lorsque cela est nécessaire, cette case sera utilisée pour référencer un bloc contenant BLOCK_SIZE / sizeof(int) blocs de données.

Il n'est pas nécessaire d'ajouter la gestion des blocs indirects pour les répertoires ou les liens symboliques. La limite sur le nombre de fichiers dans un répertoire ou la taille de la cible d'un lien ne sont pas très contraignantes.

Ajoutez la gestion des blocs indirects pour les fichiers dans SFS.

Les fonctions POSIX qui accèdent au contenu du fichier sont read et write, ainsi que truncate.

  1. La fonction sfs_read (sfs_posix.c) est programmée à partir de la fonction sfs_read_from_inode (sfs_low_level.c), elle même programmée à partir de sfs_read_from_block (sfs_low_level.c), qui utilise

    • sfs_get_data_block_nb_from_inode pour chercher les numéros de blocs à lire.

    C'est cette dernière que vous devrez modifier...

  2. La fonction sfs_write (sfs_posix.c) est programmée à partir de la fonction sfs_write_to_inode (sfs_low_level.c), elle même programmée à partir de :

    • sfs_write_to_block (sfs_low_level.c).

    C'est cette dernière que vous devrez modifier...

  3. La fonction sfs_truncate (sfs_posix.c) est programmée à partir de la fonction sfs_truncate_inode (sfs_low_level.c), elle même programmée à partir de :

    • allocate_datablocks (sfs_low_level.c), utilisée pour augmenter la taille des données d'un inode,

    • deallocate_datablocks (sfs_low_level.c) utilisée pour diminuer la taille des données d'un inode,

    Ce sont ces deux dernières que vous devrez modifier...

N'oubliez pas de modifier la fonction do_info du fichier sfs_shell.c pour mettre à jours la taille maximale autorisée des fichiers et de documenter vos tests pour mettre en ouvre cette gestion des blocs indirects.

Taille des modifications :

2.3.4. Fichiers creux

Les systèmes avec inodes permettent de créer des fichiers creux : il suffit de mettre un numéro de bloc spécial qui n'est pas alloué sur le support. Les opérations de lecture sur un tel bloc renvoient des 0, et les opérations d'écriture vont provoquer l'allocation d'un vrai bloc...

Pour SFS, nous allons utiliser le numéro de bloc ZERO_BLOCK (constante définie à 0) pour représenter un bloc de 0 non alloué... (Plus précisément, ce bloc est alloué mais en "lecture seule".

Ajoutez la gestion des fichiers creux dans SFS.

Comme précédemment, les fonctions POSIX qui accèdent au contenu du fichier sont read et write, ainsi que truncate. Comme le bloc ZERO_BLOCK est un vrai bloc ne contenant que des 0, il n'est pas nécessaire de modifier les fonctions de lecture. Il reste donc

Il faut également modifier la fonction sfs_count_used_blocks_inode qui permet de calculer la taille occupée par les données d'un inode.

N'oubliez pas de documenter vos modifications dans le fichier RAPPORT...

Taille des modifications :

2.4. Pour aller plus loin

Les fonctionnalités suivantes sont en bonus...

  1. écrire une fonction badblocks qui recherche les blocs défectueux et les associe à l'inode BADBLOCKS_INODE (pour modéliser de blocs défectueux, vous pouvez par exemple considérer les blocs dont les premiers octets sont de ad be ef),

  2. gérer les blocs avec deux indirections dans les inodes, pour augmenter la taille maximale des fichiers,

  3. écrire une fonction checkfs qui vérifie la cohérence du volume SFS,

  4. gérer une date de modification.