projet, systèmes Comments Disabled

TTTFS — The Tiny Toy File System

Projet de programmation C et programmation Systèmes

Bas niveau

Cette couche logicielle a pour but de simuler la couche d’accès de bas niveau à un dispositif de stockage permanent et de masse (type «disque dur»).

Un «disque dur» sera représenté par un fichier ordinaire sur le système hôte. Le nom de ce fichier sera par défaut disk.tfs, mais pourra être tout autre nom approprié que l’utilisateur pourrait souhaiter. Pour cette couche, le contenu du fichier sera vu comme une collection ordonnée de N blocs contenant chacun 1024 octets. La taille N sera déterminée à la construction du disque. Aucune information particulière ne doit être inscrite dans les blocs du disque dur (peut importe), sauf dans le premier bloc (bloc de numéro 0).

Il est demandé de produire une bibliothèque de fonctions permettant de manipuler ce disque. Certaines de ces fonctions seront considérées comme des fonctions internes (non visibles des couches supérieures) :

  • error read_physical_block(disk_id id,block b,uint32_t num);, qui lit depuis le disque d’identité donnée (voir plus bas), le bloc de numéro indiqué;
  • error write_physical_block(disk_id id,block b,uint32_t num);, qui écrit sur le disque le bloc de numéro donné.

Les autres fonctions seront considérées comme faisant partie de l’API de manipulation du disque (dont les prototypes devront nécessairement aparaître par inclusion du fichier ll.h) :

  • error start_disk(char *name,disk_id *id); qui permet de manipuler un disque en lui associant une identité dynamique;
  • error read_block(disk_id id,block b,uint32_t num); qui permet de lire un bloc sur le disque (lire annexe sur la raison de différencier cette fonction et la fonction read_physical_block);
  • error write_block(disk_id id,block b,uint32_t num); qui permet d’écrire un bloc sur le disque (même remarque que la fonction précédente);
  • error sync_disk(disk_id id); (voir annexe – en première approximation cette fonction peut ne rien faire du tout;
  • error stop_disk(disk_id id) qui permet de terminer une session de travail sur un disque.

À l’aide de cette API, il est demandé d’écrire la commande tfs_create -s size [name] permettant de créer un fichier qui contiendra les données du disque de nom name (par défault disk.tfs) et où size est le nombre de blocs qui constitueront le disque. Cette commande aura pour effet de créer un fichier sur le système hôte de la taille adéquate et contenant les informations suivantes sur le premier bloc :

  • avant toute chose les nombres sont toujours sur 32 bits et stockés sur le disque en little-endian et toujours alignés sur 4-octets;
  • le premier nombre du bloc 0 sera le nombre total de blocs du disque.

À l’aide de cette API, il est démandé d’écrire la commande tfs_partition -p size [-p size]... [name] permettant de partitionner l’espace physique du disque en paquets de blocs. Cette partition consiste à :

  • écrire le nombre de partition en seconde position du bloc 0 (seconde position signifie à partir de l’octet 4…)
  • écrire pour chaque partition sa taille, dans l’ordre et à la suite.

À l’aide de cette API, il est demandé d’écrire une commande tfs_analyze [name] qui permet d’obtenir les informations d’un disque : sa taille, son nombre de partitions, la taille de chaque partition, etc.

La bibliothèque devra être accompagnée et les commandes devraont être accompagnés des fichiers d’entêtes adéquats ainsi que d’un petit manuel.

Un makefile devra être produit permettant de nettoyer l’arborescence (make clean) et de créer la bibliothèque dynamique (libll.so) ainsi que les exécutables de différentes commandes.

Un exemple de disque physique : 

TTTFS Volume

Attention: tout ce qui est désigné comme nombre entier dans la suite et qui est destiné à être stocké sur le périphérique doit être codé sur 32 bits en little-endian et calés sur 4 octets.

Le système de fichier est construit par dessus le disque physique par construction d’algorithmes qui manipulent des données structurées accessibles depuis/vers ce disque. On notera que la seule communication de base possible avec le disque est la lecture ou l’écriture de bloc (voir API bas niveau).

Attention: un volume doit être auto-contenu, ce qui signifie que tous les références désignent des choses à l’intérieur du volume lui-même. Par exemple, lorsqu’on parle d’un numéro de bloc, il s’agit d’un numéro de bloc de la partition (pas d’un numéro de bloc physique).

Un système de Fichier TTTFS ou volume TTTFS occupe une partition entière d’un disque dur et impose sa propre structure sur l’usage des blocs :

  1. le bloc de description (premier bloc de la partition) — TTTFS Description Block
  2. la table des fichiers (quelques blocs suivants) — TTTFS File Table
  3. les blocs de données (le reste) – TTTFS Data Blocks

Un volume TTTFS contient des structures logiques :

  • la liste des fichiers libres (voir plus loin TTTFS File Table),
  • la liste des blocs libres (voir plus loin TTTFS Free Blocks Chain).

TTTFS Description Block

Le bloc de description d’un volume TTTFS est constitué de nombres (32 bits écrits en little-endian et toujours sur des frontières de 4-octets). Il contient les informations suivantes consécutivement et dans l’ordre :

  • L’identification de la version TTTFS, le TTTFS_MAGIC_NUMBER qui est égal à 0x31534654,
  • La taille d’un block TTTFS mesuré en octets, TTTFS_VOLUME_BLOCK_SIZE, pour la version 1 de TTTFS c’est égal à 1024,
  • Le nombre total de blocs du volume, TTTFS_VOLUME_BLOCK_COUNT, pour TTFS version c’est la taille de la partition,
  • Le nombre actuel de blocs libres du volume, TTTFS_VOLUME_FREE_BLOCK_COUNT,
  • Le numéro du premier block libre du volume, TTTFS_VOLUME_FIRST_FREE_BLOCK,
  • Le nombre total de fichiers supportables par ce volume, TTTFS_VOLUME_MAX_FILE_COUNT,
  • Le nombre de fichiers actuellement libres dans ce volume, TTTFS_VOLUME_FREE_FILE_COUNT,
  • Le numéro du premier fichier libre du volume, TTTFS_VOLUME_FIRST_FREE_FILE,

Certaines de ces valeurs sont à déterminer en fonction des paramètres utilisés par le formatage TTFS (voir plus loin).

Ce bloc est toujours considéré comme occupé, il ne peut être utilisé pour autre chose.

Attention, tous les nombres sont représentés en little-endian et sur 32 bits et calés sur des frontières de 4 octets…

TTTFS File Table

Le table des fichiers d’un volume TTFS est constitué d’une table d’entrée de fichiers contenus dans un ensemble de blocs consécutifs du volume et situés à la suite du bloc de description. Le nombre d’entrée de cette table est contenu dans le bloc de description (TTTFS_VOLUME_MAX_FILE_COUNT). Les blocs qui contiennent cette table doivent toujours être considérés comme occupés, il ne peuvent servir à autre chose.

Une entrée de la table des fichiers est structurée de la manière suivante :

  • La taille du fichier, tfs_size, exprimée en octets
  • Le type du fichier, tfs_type, qui peut prendre les valeurs suivantes : TFS_REGULAR=0, TFS_DIRECTORY=1, TFS_PSEUDO=2
  • Le sous-type du fichier, tfs_subtype qui n’est utilisé que pour le type TFS_PSEUDO et qui dans la version 1 peut prendre les valeurs TFS_DATE=0, TFS_DISK=1
  • 10 numéros de blocs, le tableau tfs_direct, qui peuvent être utilisés pour retrouver des données du fichier.
  • 1 numéro de bloc, tfs_indirect1, qui contiendra des numéros de blocs qui contiennent des données du fichier.
  • 1 numéro de bloc, tfs_indirect2, qui contiendra des numéros de lbocs qui contiennent des numéros de blocs qui contiennent des données du fichier.
  • 1 numéro de fichier, tfs_next_free, utilisé pour le chaînage libre.

Il existe deux logiquement deux types d’entrées :

  • les entrées occupées, pour lesquelles tfs_next_free ne correspond à rien et les autres informations doivent être telles qu’elles puissent permettre de manipuler le contenu d’un fichier. Les numéros de bloc, directs ou indirects désignent les blocs de données du fichier.
  • les entrées libres, dont le nombre est contenu dans le bloc de description (TTTFS_VOLUME_FREE_FILE_COUNT) et la première d’entre elles à pour numéro celui contenu dans le bloc de description (TTTFS_VOLUME_FIRST_FREE_FILE). Les entrées-libres sont chaînées les unes aux autres, en utilisant le champ tfs_next_free. La valeur du champ correspondant pour l’une au numéro de l’entrée libre qui la suit logiquement. La dernière entrée de la liste aura pour suivante son propre numéro. Ainsi si la liste des entrées libres est (dans l’ordre) 13, 38, 47, 8. Le chaînage sera next(13)=38, next(38)=47, next(47)=8 et next(8)=8. TTTFS_VOLUME_FIRST_FREE_FILE devra être égal à 0 s’il n’y a plus d’entrées libres.

TTTFS Data blocks & Free Blocks Chain

Les blocs de cette zone du volume contiennent :

  • des blocs occupés par des données de fichiers, les seuls fichiers qui possèdent des données sont les fichiers orinaires (type TFS_REGULAR) et les répertoires (type TFS_DIRECTORY) (voir plus loin).
  • des blocs occupés par des blocs d’indirection, ceux-ci contiennent des numéros de blocs de données ou des blocs d’indirection de niveau supérieur.
  • des blocs libres. Ceux-ci sont chaînés les uns aux autres à la manière des entrées libres de la table des fichiers. Le premier de cette liste a pour numéro celui indiqué par le champ TTTFS_VOLUME_FIRST_FREE_BLOCK du bloc de description du volume. Ensuite les blocs sont chaînés les uns aux autres. Le numéro du bloc libre suivant est enregistré comme le dernier entier du boc précédent. Le dernier a pour suivant lui-même.
TFS Directories

Un répertoire est un fichier contenant des entrées de répertoire. Chaque entrée est constituée de deux données :

  • un numéro de fichier
  • une suite de 28 caractères constituant une chaîne de caractère à la C c’est-à-dire nécessairement terminée par ASCII-0.

Un répertoire dit vide contient deux entrées : l’une de nom “.” et désignant lui-même et l’autre nommée “..” désignant son répertoire parent. La racine du système de fichier est le fichier de numéro 0, ne peut être supprimé et est son propre parent. Pour des raisons pratiques, il est autorisé d’avoir des entrées de répertoire vides, c’est à dire ne correspondant à rien, dont le nom est la chaîne vide (réduite au seul caractère nul).

Un exemple de partition : 

TFS Special Files

Les fichiers de type pseudo, sont particulier puisqu’il n’ont pas vraiment de contenu. Leur contenu est virtuel, c’est-à-dire dynamiquement déterminé.

Pour le type TFS_DATE, un accès à ce fichier permet d’obtenir la date courante exprimée sous la forme d’un entier exprimant le nombre de secondes écoulées depuis le démarrage du disque.

Pour le type TFS_DISK, les accès correspondent aux données brutes du volume courant.

TFS Pathnames

Les chemins manipulables par l’API TFS ont tous la forme :

FILE://disk/volume/rep1/rep2/name où :

  • disk désigne le disque contenant un ou plusieurs volumes TFS. Lorsque disk est égal à “HOST”, les accès sont réalisés directement sur le système de fichiers hôte (l’Unix sous-jacent).
  • volume désigne le volume TFS sur le disque (0, 1, etc.)
  • la suite constitue le chemin pour se déplacer depuis la racine vers le fichier concerné, les “/” sont des séparateurs.

TODO

Il est demandé d’implémenter une commande tfs_format -p partition -mf file_count [disk] permettant de créer un système de fichier minimal sur la partition donnée du disk donné; système de fichiers ayant pour nombre maximal de fichiers le file_count` donné et contenant un répertoire racine vide.

Il est demandé d’implémenter une bibliothèque de fonctions diverses et variées utiles permettant de (liste non-exhaustive) réaliser des opérations de bas-niveau sur un volume donné :

  • mettre un bloc dans la liste des blocs libres
  • supprimer un bloc de la liste des blocs libres
  • mettre une entrée de répertoire dans la liste des entrées libres
  • supprimer une entrée des entrées libres
  • ajouter un bloc dans la liste des blocs d’un fichier
  • supprimer un bloc dans la liste des blocs d’un fichier
  • découpage d’un chemin par itération
  • libérer les blocs de données d’un fichier ou répertoire
  • etc.

Ces fonctions devraient permettre de créer une API permettant de manipuler le système de fichier de façon standard :

  • int tfs_mkdir(const char *path, mode_t mode);
  • int tfs_rmdir(const char *path);
  • int tfs_rename(const char *old, const char *new);
  • int tfs_open(const char *name,int oflag, ...);
  • ssize_t tfs_read(int fildes,void *buf,size_t nbytes);
  • ssize_t tfs_write(int fildes,void *buf,size_t nbytes);
  • int tfs_close(fildes);
  • off_t tfs_lseek(int fildes,off_t offset,int whence);
  • DIR *opendir(const char *filename);
  • struct dirent *readdir(DIR *dirp);
  • void rewinddir(DIR *dirp);
  • int closedir(DIR *dirp);

Ces fonctions devront se comporter comme les appels systèmes Unix usuels (même valeurs possibles, même comportement, etc). La différence majeure notable étant l’interprétation du paramètre name de la fonction tfs_open qui devra supporter le schéma de nommage proposé plus haut.

Ces fonctions devront être les seules fonctions visibles de la bibliothèque dynamique libtfs.so qui servira à obtenir un exécutable supportant le système de fichiers TFS.

Il est aussi demandé d’écrire des commandes comme (liste non-exhaustive):

  • tfs_cp
  • tfs_mv
  • tfs_rm
  • tfs_cat
  • tfs_mkdir
  • …

Pour copier un fichier du monde Unix au monde TFS on pourra utiliser une commande comme tfs_cp FILE://HOST/home/yunes/truc.txt FILE://disk.tfs/0/dir/toto.txt qui permet donc de copier le contenu du fichier /home/yunes/truc.txt du système de fichier Unix vers le fichier de référence /dir/toto.txt situé sur le volume numéro 0 du disque tfs de nom disk.tfs.

Il est demandé de décrire soigneusement l’ensemble des fonctions réalisées, permettre la compilation via l’outil make, utiliser git comme système de gestion de version (on rappelle que la machine moule.informatique.univ-paris-diderot.fr:8080 héberge un gitlab utilisable…).

Les documentations doivent être fournies dans un format raisonnable, donc autre que du simple texte, par exemple HTML (un regard vers l’outil Doxygen ne sera pas inutile).

Annexe

Système de cache…