Retrouvez cet article dans : Linux Magazine 98
SOS, pour Simple Operating System, est un noyau de système d’exploitation (OS) qui se veut simple à comprendre et qui couvre néanmoins les concepts et fonctions des OS modernes. Le code de l’OS accompagne une série d’une douzaine d’articles parus dans la revue GNU/Linux Magazine France entre 2004 et 2006. Pour chaque article, http://sos.enix.org propose le code de l’OS pour le dernier article et les précédents.
SOS et les articles dans GNU/Linux Magazine France s’adressent aux personnes curieuses de savoir comment fonctionne un OS, pas spécialement aux « pros » des OS. Ils visent à apprendre, par la pratique, la structure et le fonctionnement interne des OS. Une telle compréhension en profondeur n’est pas simplement anecdotique : elle permet d’avoir une vision synthétique du fonctionnement de tout le système. Chaque article apporte une pierre à l’édifice en expliquant une notion importante. Le résultat est un OS multitâche avec gestion de la mémoire virtuelle et système de fichiers virtuel fonctionnant sur PC (architecture x86 32 bits).
Résumé : Après une trop longue absence, SOS est de retour dans GNU/Linux Magazine. Dans le précédent article, nous avions étudié les périphériques de type bloc par l’implémentation du sous-système blockdev, ainsi que celles d’un pilote pour disque dur IDE et de l’infrastructure de gestion des partitions du disque. Ce mois-ci, nous allons détailler l’implémentation d’un système de fichiers FAT et son intégration dans le VFS.
Introduction
Jusqu’ici, les partitions que nous avons mises en place ne contenaient rien, puisqu’elles étaient dépourvues de système de fichiers. Le seul file system que nous avions à notre disposition, Virtfs, était stocké en mémoire vive, les données étaient donc volatiles. Dans cet article, nous allons étudier le système de fichiers « FAT ». Ainsi, nous aurons notre première source de données persistante dans SOS.
L’implémentation du FS FAT nous permettra d’étudier une organisation des données sur le disque très simple. Elle nous permettra également d’étudier l’intégration d’un système de fichiers réellement utilisé avec le VFS que nous avons étudié dans l’article 8 et avec le sous-système de périphérique bloc blockdev que nous avons étudié dans l’article 9.5.
En pratique, à la fin de cet article, les applications utilisateur pourront sauvegarder leurs données sur le disque grâce à notre implémentation du système FAT.
Toute l’implémentation du driver FAT se trouve dans les fichiers drivers/fs_fat.c et drivers/fs_fat.h.
1. Présentation du système de fichiers FAT
1.1 Généralités
Le système de fichiers FAT (File Allocation Table) a été inventé par Microsoft entre la fin des années 70 et le début des années 80. Il fut le premier système de fichiers supporté par le système d’exploitation MS-DOS. Il a été développé à l’origine comme un simple système de fichiers destiné aux disquettes dont la taille ne dépassait pas 360 ko. Au fur et à mesure, le système a été amélioré pour supporter des supports de stockage de plus en plus grands. Actuellement, il y a trois types de systèmes de fichiers FAT : FAT12, FAT16 et FAT32. La différence entre ces sous-types de FAT est la taille des entrées dans la structure FAT sur le disque. Elles sont de 12 bits en FAT12, 16 bits en FAT16 et 32 bits en FAT32.
La taille des entrées des différents types de FAT influe sur la taille des partitions gérées par le file system et la taille des fichiers supportés.
Le système de fichiers FAT est l’un des plus simples qui existent. Il est d’ailleurs limité et dépassé maintenant. Microsoft s’en est en effet séparé au profit du système de fichiers NTFS. N’ayant pas grande affinité avec le monde UNIX, le système FAT ne connaît pas certaines choses qui sont, pour les utilisateurs de *nix, des fondamentaux. Voici une liste non exhaustive des fonctionnalités manquantes pour un système de fichiers de ce type :
- Les liens ne sont pas supportés (symboliques et « hard »).
- Pas de gestion des droits d’accès/d’exécution.
- Pas de fichiers spéciaux (char/block).
D’autres limitations sont dues à notre implémentation. Reportez-vous à la section 1.3 pour plus d’informations.
Les contraintes citées ci-dessus montrent que le système de fichiers FAT n’est pas du tout adapté à un environnement UNIX. Néanmoins, la raison pour laquelle nous avons décidé d’implémenter le file system FAT dans SOS est double. D’abord, la norme FAT est simple, donc c’est un bon exemple pédagogique. Deuxièmement, le système de fichiers FAT est encore très utilisé, notamment pour les clés USB qui sont la plupart du temps pré-formatées en FAT lorsqu’on les achète.
1.2 Structure d’un système FAT
Reportez-vous à la figure 1 ci-dessous pour suivre la présentation de la structure générale du système FAT.
Un volume FAT est décomposé en 3 parties :
1. le secteur de démarrage ;
2. la structure FAT ;
3. les données elles-mêmes.
Avant de décrire en détail la structure d’un système FAT, il y a deux notions à aborder. La première est le « volume ». Un volume FAT est une partition contenant un système de fichiers de type FAT. La seconde notion est le « cluster ». Les clusters sont simplement les unités de stockage du système de fichiers FAT. Concrètement, un cluster est une agrégation contiguë de secteurs du disque qui contient les données utilisateur ou celles nécessaires à la gestion du système FAT. Le nombre de secteurs dans un cluster est variable d’un volume à un autre. Pour connaître la grandeur d’un cluster dans notre volume, reportez-vous à la section 2.
Sur la figure 2, on peut voir la hiérarchie entre les différentes unités de stockage dans un système FAT.
La première structure importante du système FAT est appelée le « secteur de démarrage » ou BPB (BIOS Parameter Block). On le trouve toujours dans le premier secteur du volume. Tous les types de FAT doivent avoir un secteur de boot. Le BPB contient beaucoup d’informations importantes, parmi lesquelles on trouve le nombre d’octets par secteur, le nombre de secteurs par cluster, le nombre d’entrées pré-allouées spécialement pour un répertoire particulier, le répertoire racine. Pour avoir une liste exhaustive des champs du secteur de boot, reportez-vous au document [Cor00].
La structure FAT est un tableau dont chaque élément correspond directement à un cluster du système FAT. C’est ici que la différence entre FAT12, FAT16 et FAT32 se fait : le type de FAT détermine la taille des entrées dans ce tableau. Ensuite, chaque nœud du système de fichiers (c’est-à-dire fichier ou répertoire) correspond à une suite de clusters, représentée par une liste chaînée d’éléments de ce tableau.
Un nœud n’est rien d’autre qu’une abstraction du VFS (voir article 8) pour représenter un fichier ou un répertoire du système de fichiers. Dans le cas du système FAT, c’est tout à fait adapté, car un répertoire n’est rien de plus qu’un fichier avec un attribut spécial qui indique que c’est un répertoire. La seule différence à propos des répertoires est que les données contenues dans ces « fichiers » sont une série d’entrées de répertoire de 32 octets chacune (voir 5 pour plus d’informations sur les entrées de répertoire). Sous tous les autres aspects, un répertoire est juste un fichier.
La figure 3 montre comment un fichier/répertoire est stocké sur disque : sous la forme d’un chaînage de clusters.
Figure 3 : Un fichier commence au cluster 2. Le cluster 2 n’est pas vide. Il contient le numéro du cluster suivant dans le fichier. On suit la chaîne jusqu’à tomber sur le marqueur de fin de liste « End ». Le cluster d’origine du fichier est stocké dans son entrée de répertoire.
Sur la figure, vous pouvez voir que les clusters 0 et 1 n’existent pas. C’est la règle dans tous les types de FAT. Le 0 dans une liste des clusters signifie que le cluster est libre et prêt à être utilisé. Par convention, le premier cluster de donnée porte le numéro 2.
La table des clusters FAT est dupliquée plusieurs fois sur disque pour une meilleure résistance aux secteurs défectueux. Les sauvegardes sont toutes dupliquées à la suite de la première table dans la zone réservée au début du volume.
Dernière partie, la zone de données du volume est découpée en clusters.
Maintenant que nous avons présenté les grands principes du système de fichiers FAT, nous allons passer aux détails de l’implémentation du système FAT dans SOS.
1.3 Limitations de l’implémentation du système de fichiers FAT dans SOS
Avant de commencer à détailler le fonctionnement du système de fichiers FAT dans SOS, je vais vous détailler les fonctionnalités que je n’ai pas implémentées pour cet article. Peut-être viendront-elles plus tard de moi ou de toute autre personne motivée. Ces limitations sont dans la page « exercices » sur le site de SOS (http://sos.enix.org/).
- pas de support du système FAT12 ;
- pas de support des dates de création/modification pour les fichiers/répertoires ;
- pas de support des noms de fichiers longs ;
- pas de renommage des fichiers.
En réalité, le type FAT12 n’est pratiquement plus utilisé (ni utilisable). La capacité d’un volume FAT12 se compte en ko et est donc totalement dépassée. De plus, l’implémentation de la FAT12 est la moins évidente des trois types de FAT.
Les estampilles temporelles (date et heure de création, dernière date d’accès au fichier et date et heure de dernière écriture) n’ont pas été implémentées par manque de primitives dans le noyau SOS.
Le support des noms de fichiers longs est tout à fait faisable dans le contexte actuel de SOS, mais demande un effort d’implémentation supplémentaire.
Pour des raisons de simplicité, le renommage des fichiers n’a pas été implémenté. L’opération rename de notre driver FAT est laissé à titre d’exercice.
2. Secteur de boot
Avant de plonger dans les arcanes du système FAT, une petite présentation du secteur de boot et de ses champs s’impose.
D’abord, il faut savoir que le secteur de boot diffère selon les types de FAT. Mais, on connaît le type de FAT en fonction des champs communs du secteur de boot.
Voici la partie commune du secteur de boot.
/** The FAT first sector structure */
struct sos_fat_boot_sector {
/* BS (Boot Sector) */
sos_ui8_t BS_jmpbBoot[3];
char BS_OEMName[8];
/* BPB (BIOS Parameter Block) */
sos_ui16_t BPB_BytsPerSec;
sos_ui8_t BPB_SecPerClus;
sos_ui16_t BPB_RsvdSecCnt;
sos_ui8_t BPB_NumFATs;
sos_ui16_t BPB_RootEntCnt;
sos_ui16_t BPB_TotSec16;
sos_ui8_t BPB_Media;
sos_ui16_t BPB_FATSz16;
sos_ui16_t BPB_SecPerTrk;
sos_ui16_t BPB_NumHeads;
sos_ui32_t BPB_HiddSec;
sos_ui32_t BPB_TotSec32;
/* BPB specific */
union {
struct sos_fat16_BPB fat16_BPB;
struct sos_fat32_BPB fat32_BPB;
} BPB_specific;
} __attribute__ ((packed));
Les champs qui nous intéressent pour déterminer le type de FAT sont les champs BPB_RootEntCnt, BPB_BytsPerSec, BPB_FATSz16, BPB_FATSz32, BPB_ResvdSecCnt, BPB_NumFATs, BPB_SecPerClus, BPB_TotSec16 et BPB_TotSec32.
BPB_BytsPerSec est le nombre d’octets par secteur. Les valeurs possibles sont 512, 1024, 2048 et 4096. Pour un maximum de compatibilité avec tous les codes implémentant le système de fichiers FAT, il est conseillé de prendre 512 octets par secteur.
BPB_SecPerClus est le nombre de secteurs par cluster. Les valeurs possibles sont 1, 2, 4, 8, 16, 32, 64 et 128. On obtient le nombre d’octets par cluster en multipliant cette valeur par la précédente (BPB_SecPerClus * BPB_BytsPerSec). Cette multiplication ne doit pas dépasser 32 ko pour être compatible avec le standard FAT.
BPB_ResvdSecCnt est le nombre de secteurs réservés entre le premier secteur du volume FAT et la liste chaînée de cluster du volume FAT. En FAT12 et FAT16, seul le secteur de boot est réservé.
BPB_NumFATs est le nombre de duplicata pour le tableau de clusters (voir 1). En général, il n’y a que 2 structures FAT, quel que soit le type de FAT.
BPB_RootEntCnt est le nombre d’entrées dans le répertoire racine. Ce champ est uniquement utile en FAT12 et FAT16. Ce nombre d’entrées, multiplié par 32 (la taille d’une entrée dans un répertoire), doit être un multiple de BPB_BytsPerSec.
BPB_TotSec16 est le nombre total de secteurs dans le volume FAT en comptant toutes les zones. Si ce champ est à 0, alors le champ BPB_TotSec32 contient le nombre total de secteurs du volume.
BPB_FATSz16 est la taille en octets d’un seul tableau de clusters FAT. Si le champ est à 0, alors le champ BPB_FATSz32 contient la taille d’un tableau FAT32.
Le champ BPB_FATSz32 est dans la partie du secteur de démarrage spécifique à la FAT32. Voici la structure qui lui correspond :
/** The FAT32 specific BPB */
struct sos_fat32_BPB {
sos_ui32_t BPB_FATSz32;
sos_ui16_t BPB_ExtFlags;
sos_ui16_t BPB_FSVer;
sos_ui32_t BPB_RootClus;
sos_ui16_t BPB_FSInfo;
sos_ui16_t BPB_BkBootSec;
char BPB_Reserved[12];
struct sos_fat16_BPB fat16_BPB;
} __attribute__ ((packed));
Comme on peut le voir, en FAT32, le secteur de boot contient également la partie spécifique à la FAT16 en tout dernier champ. Voici la structure pour la partie FAT16 :
/** The FAT16 specific BPB */
struct sos_fat16_BPB {
sos_ui8_t BS_DrvNum;
sos_ui8_t BS_Reserved1;
sos_ui8_t BS_BootSig;
sos_ui32_t BS_VolID;
char BS_VolLab[11];
char BS_FilSysType[8];
} __attribute__((packed));
Pour plus d’informations sur les autres champs du secteur de démarrage, reportez-vous au document [Cor00] et au code source du pilote FAT.
Nous allons maintenant pouvoir regarder en détail comment fonctionne un système de fichiers FAT.
3. Détermination du type de FAT
Dans le code de SOS, le calcul pour déterminer le type de FAT est fait lors du montage du volume, dans la fonction fat_mount. Toute cette section découpe le code du fat_mount en petites parties pour que l’explication soit plus claire, mais vous pouvez aussi suivre les explications directement dans le fichier drivers/fs_fat.c.
3.1 Calcul du nombre de secteurs du répertoire racine
En FAT12 et FAT16, le répertoire racine a un nombre de secteurs pré-alloués au début de la zone de données. Ces secteurs ne font partie d’aucun cluster et ne sont donc pas mappés dans la liste des clusters.
Le calcul qui suit consiste donc à savoir combien de secteurs sont alloués pour le répertoire racine.
data_struct->RootDirSectors =
SOS_ALIGN_SUP((sos_fat_bs->BPB_RootEntCnt * 32),
sos_fat_bs->BPB_BytsPerSec) /
sos_fat_bs->BPB_BytsPerSec;
La variable sos_fat_bs est la structure du secteur de boot étudiée à la section 2.
La variable data_struct est une structure qui contient toutes les valeurs calculées ici et qui seront souvent nécessaires dans la manipulation de la FAT. Voici sa déclaration :
/** Fat data structure */
struct sos_fat_data_structure {
sos_ui32_t RootDirSectors;
sos_ui32_t FATSz;
sos_ui32_t FirstDataSector;
sos_ui32_t TotSec;
sos_ui32_t DataSec;
sos_ui32_t CountOfClusters;
sos_ui32_t FirstRootDirSecNum;
sos_ui32_t FAT_Type;
sos_ui32_t EndOfCluster;
struct sos_fat_boot_sector BootSector;
};
Tous les champs de cette structure seront couverts dans les sections suivantes.
Revenons au calcul ci-dessus. Dans le secteur de démarrage, nous avons le nombre d’entrées réservées au répertoire racine (BPB_RootEntCnt) que l’on multiplie par 32, soit la taille en octets d’une entrée de répertoire. On ne veut pas la place du répertoire racine en octets, mais en secteurs. On arrondit donc cette valeur au secteur supérieur avec SOS_ALIGN_SUP et on divise le résultat par le nombre d’octets par secteur (BPB_BytsPerSec).
En FAT32, BPB_RootEntCnt est égal à 0, RootDirSectors est donc égal à 0 également. La raison est qu’en FAT32 le répertoire racine est un répertoire comme les autres et n’est pas pré-alloué en dehors des clusters du volume au début de la zone de données. La seule différence est que ce répertoire n’a pas de répertoire parent. On trouve la position du premier cluster du répertoire racine dans le champ BPB_RootClus dans la partie spécifique FAT32 du secteur de boot. Par défaut, BPB_RootClus est égal à 2, soit le premier cluster valide du volume.
3.2 Calcul du premier secteur de données du volume
Maintenant que nous avons la taille en secteurs du répertoire racine, nous pouvons calculer le premier secteur de données du volume FAT :
if (sos_fat_bs->BPB_FATSz16 != 0) {
data_struct->FATSz =
sos_fat_bs->BPB_FATSz16;
} else {
data_struct->FATSz =
sos_fat_bs->BPB_specific.fat32_BPB.BPB_FATSz32;
}
data_struct->FirstDataSector =
sos_fat_bs->BPB_RsvdSecCnt +
(sos_fat_bs->BPB_NumFATs *
data_struct->FATSz) +
data_struct->RootDirSectors;
La première partie du code ci-dessus détermine la taille en secteurs du tableau de clusters du volume. La taille est BPB_FATSz16 si ce dernier champ n’est pas à 0. Dans le cas contraire, FATSz est égal à BPB_FATSz32.
Dans la seconde partie, on calcule la position du premier secteur de données du volume FAT. Pour cela, on additionne BPB_RsvdSecCnt, soit le secteur de boot et éventuellement d’autres secteurs qui le suivent, avec la taille de la FAT calculée ci-dessus en tenant compte de la possible redondance de la FAT, BPB_NumFATs * FATSz, et le nombre de secteurs réservés au répertoire racine. On obtient ainsi la position du premier secteur de données.
Je rappelle que ce premier secteur fait partie du premier cluster de la zone de données et que ce cluster s’appelle « cluster numéro 2 » (voir la section 3).
3.3 Calcul du premier secteur d’un cluster
Puisque nous étudions des clusters, j’introduis ici le calcul du premier secteur d’un cluster en fonction d’un numéro de cluster. Voici la fonction de calcul :
/** Helper function to compute the first sector number
* of the given cluster. */
static sos_ui64_t
sos_fat_helper_first_sector_of_cluster(
struct sos_fat_data_structure *data_struct,
sos_ui32_t cluster_nr)
{
return ((cluster_nr - FAT_FIRST_VALID_CLUSTER) *
data_struct->BootSector.BPB_SecPerClus) +
data_struct->FirstDataSector;
}
Grâce au calcul du premier secteur de données du volume FAT à la section précédente, nous pouvons facilement effectuer ce calcul. FAT_FIRST_VALID_CLUSTER est égal à 2 par convention comme je l’ai déjà expliqué en section 3. On soustrait donc le numéro de cluster en paramètre à FAT_FIRST_VALID_CLUSTER. On multiplie le numéro de cluster relatif au nombre de secteurs par cluster (BPB_SecPerClus) pour obtenir le premier secteur du cluster par rapport au début de la zone de données. Il ne nous manque plus qu’à additionner ce nombre avec le numéro du premier secteur de données du volume pour obtenir le résultat.
3.4 Calcul du nombre de secteurs de données
Avant de connaître le nombre de clusters dans la zone de données nécessaire pour savoir de quel type de système FAT notre volume est rempli, il nous faut calculer le nombre de secteurs de données :
if (sos_fat_bs->BPB_TotSec16 != 0) {
data_struct->TotSec = sos_fat_bs->BPB_TotSec16;
} else {
data_struct->TotSec = sos_fat_bs->BPB_TotSec32;
}
data_struct->DataSec = data_struct->TotSec -
(sos_fat_bs->BPB_RsvdSecCnt +
(sos_fat_bs->BPB_NumFATs * data_struct->FATSz) +
data_struct->RootDirSectors);
La première partie du calcul détermine le nombre total de secteurs dans le volume. Pour cela, on regarde le champ BPB_TotSec16 du secteur de boot. Si celui-ci est nul, alors le nombre total de secteurs du volume est dans le champ BPB_TotSec32 de ce même secteur de boot.
La seconde partie du calcul soustrait le nombre total de secteurs du volume trouvé juste au-dessus avec les secteurs réservés au début du volume. Les secteurs réservés sont de 3 types :
1. les secteurs réservés en début de volume pour le secteur de boot par exemple (BPB_RsvdSecCnt) ;
2. les secteurs pour les tableaux FAT (BPB_NumFATs * FATSz) ;
3. et les secteurs réservés au répertoire racine (RootDirSectors).
On peut remarquer que la somme des secteurs réservés est égale à FirstDataSector, ce qui est logique.
3.5 Calcul du nombre de clusters dans la zone de données
À présent, nous sommes capables de connaître le nombre de clusters dans la zone de données, puisque nous venons de calculer le nombre de secteurs dans cette zone :
data_struct->CountOfClusters =
data_struct->DataSec / sos_fat_bs->BPB_SecPerClus;
On divise simplement le nombre de secteurs de données par le nombre de secteurs par cluster donné par les champs du secteur de démarrage.
Comme je l’ai fait remarquer dans la section 3.1, la division entière arrondit à l’inférieur. Ici, c’est tout à fait normal et le résultat doit rester tel quel. Cela signifie qu’éventuellement on peut avoir quelques secteurs non utilisés en fin de volume, le système FAT en a conscience et ne s’en préoccupe pas.
3.6 Calcul du type de FAT
Maintenant, nous sommes capables de déterminer le type de système FAT :
if (data_struct->CountOfClusters < FAT12_CLUSTER_LIMIT) {
data_struct->FAT_Type = FAT12;
} else if (data_struct->CountOfClusters < FAT16_CLUSTER_LIMIT) {
data_struct->FAT_Type = FAT16;
} else {
data_struct->FAT_Type = FAT32;
}
Notez bien que les signes sont bien des < et non des ≤. Notez également que les nombres sont corrects. Le premier nombre pour la FAT12 est bien 4085 et le second pour la FAT16 est bien 65525. Tout cela est défini dans les spécifications de Microsoft.
C’est la seule et unique méthode pour déterminer le type de FAT. Cette méthode est imposée par le standard. Si une implémentation de FAT ne respecte pas ces règles, alors les systèmes d’exploitations Microsoft risquent de ne pas considérer les volumes FAT correctement parce qu’ils prendront le volume FAT pour un autre type que celui défini à la base.
Voilà, nous savons à présent quel est le type de volume FAT que nous utilisons dans notre implémentation.
3.7 Marque de fin de chaîne de clusters
Avant de passer aux calculs sur les clusters, il reste un champ dans la structure sos_fat_data_structure à remplir qui dépend du type de volume FAT. Il s’agit de la marque qui permet de reconnaître le cluster de fin d’un fichier. Une simple affectation permet de le définir :
if (data_struct->FAT_Type == FAT16) {
data_struct->EndOfCluster = FAT16_EOC;
} else {
data_struct->EndOfCluster = FAT32_EOC;
}
Toutes les informations nécessaires à la manipulation du système de fichiers sont maintenant connues. On peut maintenant clore cette section sur le secteur de boot pour nous intéresser au système de fichiers lui-même.
4. Traduire un numéro de secteur en numéro de cluster + offset
Il y a un calcul plus important encore sur le système FAT que de déterminer son type. Connaissant N un numéro de cluster valide, où est l’entrée de ce cluster dans le tableau FAT ? Le seul type pour lequel le calcul est compliqué est le type FAT12, que nous ne supporterons pas, comme précisé en 1.3.
Avant de se lancer dans ce dernier calcul, il faut préciser qu’un fichier/répertoire est une liste chaînée de clusters dans le tableau de clusters FAT que nous allons étudier maintenant.
Maintenant, voici le calcul pour récupérer le numéro du cluster et l’offset pour un secteur donné :
/** Helper function to compute the FAT offset from
* the FAT type. */
static sos_ui32_t sos_fat_helper_fat_offset(
struct sos_fat_data_structure *data_struct,
sos_ui32_t cluster_nr)
{
if (data_struct->FAT_Type == FAT16) {
return cluster_nr * 2;
} else if (data_struct->FAT_Type == FAT32) {
return cluster_nr * 4;
}
/** FAT12 is unsupported */
return 0;
}
/** Helper function to compute the FAT sector
* number in the cluster table and its offset
* in this sector for a given cluster. */
static sos_ret_t
sos_fat_helper_get_sector_and_offset(
struct sos_fat_data_structure* data_struct,
sos_ui32_t cluster_nr,
sos_ui32_t *ThisFATSecNum,
sos_ui32_t *ThisFATEntOffset)
{
*ThisFATSecNum =
data_struct->BootSector.BPB_RsvdSecCnt +
(sos_fat_helper_fat_offset(cluster_nr) /
data_struct->BootSector.BPB_BytsPerSec);
*ThisFATEntOffset =
sos_fat_helper_fat_offset(cluster_nr) %
data_struct->BootSector.BPB_BytsPerSec;
return SOS_OK;
}
Le calcul de l’offset, en octets, dans la FAT (sos_fat_helper_fat_offset) consiste à doubler le numéro du cluster dans le cas d’un système FAT16 et quadrupler le numéro de cluster en FAT32. Ceci est dû à la largeur en octets de l’entrée FAT dans chacun des types (16 bits = 2 octets dans le premier cas, 32 bits = 4 octets dans l’autre).
L’opération % (remainder operator) est le reste de la division entière. C’est-à-dire le reste après division de FATOffset (voir calcul ci-dessus) par BPB_BytsPerSec. ThisFATSecNum est le numéro de secteur de début du cluster N dans la première FAT. Lorsque la FAT est redondante et que vous voulez accéder au numéro de secteur de la seconde FAT, il vous faut ajouter FATSz à ThisFATSecNum ; pour le numéro de secteur dans la troisième FAT, ajoutez 2 * FATSz, et ainsi de suite.
Avec ThisFATSecNum et ThisFATEntOffset, on peut lire l’entrée du cluster N. Il nous faut lire le secteur ThisFATSecNum. Voici un exemple de récupération de la valeur de l’entrée, le secteur est lu dans une variable SecBuf qui est un tableau d’octets :
sos_fat_helper_get_sector_and_offset(
data_struct, cluster_nr,
&ThisFATSecNum, &ThisFATEntOffset);
/* Lecture du secteur “ThisFATSecNum”
dans la variable SecBuf */
if (data_struct->FAT_Type == FAT16) {
FATClusEntryVal =
*((sos_ui16_t *) &SecBuf[ThisFATEntOffset]);
} else {
FATClusEntryVal =
(*((sos_ui32_t *) &SecBuf[ThisFATEntOffset]))
& 0x0FFFFFFF;
}
La variable FATClusEntryVal contient la valeur de l’entrée du cluster N. Maintenant, voici comment écrire une valeur dans l’entrée du cluster N :
/** Helper function to set a cluster in
* the cluster table with value. */
static sos_ret_t
sos_fat_helper_set_cluster_value(
struct sos_blockdev_instance *block_device,
struct sos_fat_data_structure *data_struct,
sos_ui32_t cluster_nr,
sos_ui32_t value)
{
sos_ret_t retval;
sos_ui32_t fat_nr;
sos_ui32_t ThisFATSecNum, ThisFATEntOffset;
SOS_ASSERT_FATAL(cluster_nr >= 2);
sos_fat_helper_get_sector_and_offset(
data_struct, cluster_nr,
&ThisFATSecNum, &ThisFATEntOffset);
sos_size_t sector_size =
data_struct->BootSector.BPB_BytsPerSec;
sos_ui8_t *SecBuf = (sos_ui8_t *)
sos_kmalloc(sector_size, 0);
if (SecBuf == NULL)
return -SOS_ENOMEM;
/* Lecture du secteur “ThisFATSecNum” dans
la variable SecBuf */
if (data_struct->FAT_Type == FAT16) {
*((sos_ui16_t *) &SecBuf[ThisFATEntOffset]) =
(sos_ui16_t) value;
} else {
*((sos_ui32_t *) &SecBuf[ThisFATEntOffset]) =
(*((sos_ui32_t *) &SecBuf[ThisFATEntOffset]))
& 0xF0000000;
*((sos_ui32_t *) &SecBuf[ThisFATEntOffset]) =
(*((sos_ui32_t *) &SecBuf[ThisFATEntOffset]))
| (0x0FFFFFFF & value);
}
/* Ecriture du secteur modifié sur le disque */
sos_kfree((sos_vaddr_t) SecBuf);
return SOS_OK;
}
Vous notez que le code FAT32 ci-dessus est un peu bizarre. Il y a une explication à cela. Les entrées de cluster FAT32 utilisent actuellement seulement les 28 bits de poids le plus faible. Les 4 bits de poids fort sont réservés pour les entrées FAT32. Ces 4 bits doivent être conservés en toutes circonstances (sauf formatage, dans ce cas remise à zéro).
Pour les curieux qui s’intéressent à ces calculs pour la FAT12 le document [Cor00] vous donnera toutes les informations nécessaires.
5. Structure des répertoires
Un champ reste initialisé dans la structure sos_fat_data_structure présentée dans la section 3.1. Il s’agit du champ FirstRootDirSecNum qui va être expliqué ici avec la structure des répertoires.
Rappelons que nous ne traiterons que le cas des entrées de répertoire courtes.
Un répertoire FAT n’est rien d’autre qu’un « fichier » composé d’une liste linéaire de structures de 32 octets. C’est pourquoi le terme « nœud » dans le système de fichiers FAT correspond très bien à un fichier comme à un répertoire.
Pour rappel, le seul répertoire spécial, qui doit toujours être présent, est le répertoire racine. Pour les FAT de type FAT12 et FAT16, la racine est placée à un endroit fixe sur le volume, immédiatement après la dernière FAT et à une taille fixe en nombre de secteurs calculée à partir du champ BPB_RootEntCnt (voir le calcul dans la section 3.1).
Pour la FAT32, le répertoire racine peut être de taille variable et est une liste chaînée de clusters, comme n’importe quel autre répertoire. Le premier cluster du répertoire racine en FAT32 est stocké dans le champ BPB_RootClus du secteur de boot FAT32.
Voici donc le calcul du numéro du premier secteur du répertoire racine :
if (data_struct->FAT_Type != FAT32) {
data_struct->FirstRootDirSecNum =
sos_fat_bs->BPB_RsvdSecCnt +
(sos_fat_bs->BPB_NumFATs *
sos_fat_bs->BPB_FATSz16);
} else {
data_struct->FirstRootDirSecNum =
sos_fat_bs->BPB_specific.fat32_BPB.BPB_RootClus;
}
On peut maintenant décortiquer les entrées qui sont dans ce répertoire.
5.1 Implémentation SOS de la structure de répertoire
Toutes les informations contenues dans cette section viennent principalement du standard [Cor00]. Notamment, la définition de la structure d’une entrée de répertoire FAT ci-dessous (sos_fat_directory_entry). Il faut noter que la structure sos_fat_directory_entry correspond exactement à la façon dont les données sont enregistrées sur le disque.
Voici la structure d’une entrée de répertoire FAT :
/** Fat Directory entry structure */
struct sos_fat_directory_entry {
#define IS_FAT_VALID_CHAR(c) \
((c) > 0x20 && (c) != 0x22 && \
((c) < 0x2A || (c) > 0x2C) && \
(c) != 0x2E && (c) != 0x2F && \
((c) < 0x3A || (c) > 0x3F) && \
((c) < 0x5B || (c) > 0x5D) && \
(c) != 0x7C)
char DIR_Name[11];
/* File attributes */
#define ATTR_READ_ONLY 0x01
#define ATTR_HIDDEN 0x02
#define ATTR_SYSTEM 0x04
#define ATTR_VOLUME_ID 0x08
#define ATTR_DIRECTORY 0x10
#define ATTR_ARCHIVE 0x20
#define ATTR_LONG_NAME \
(ATTR_READ_ONLY | ATTR_HIDDEN | \
ATTR_SYSTEM | ATTR_VOLUME_ID)
sos_ui8_t DIR_Attr;
sos_ui8_t DIR_NTRes;
sos_ui8_t DIR_CrtTimeTenth;
sos_ui16_t DIR_CrtTime;
sos_ui16_t DIR_CrtDate;
sos_ui16_t DIR_LstAccDate;
sos_ui16_t DIR_FstClusHI;
sos_ui16_t DIR_WrtTime;
sos_ui16_t DIR_WrtDate;
sos_ui16_t DIR_FstClusLO;
sos_ui32_t DIR_FileSize;
} __attribute__ ((packed));
Le premier champ fera l’objet de la prochaine section. On peut remarquer la macro de vérification des caractères de ce champ IS_FAT_VALID_CHAR sur laquelle nous reviendrons.
Le second champ contient les attributs du fichier. Nous y reviendrons également dans une section postérieure.
Le champ DIR_NTRes ne nous concerne pas, puisque réservé au système d’exploitation Windows NT.
Les champs DIR_CrtTimeTenth, DIR_CrtTime, DIR_CrtDate, DIR_LstAccDate, DIR_WrtTime et DIR_WrtDate sont les marques de temps du fichier. DIR_Cnt* sont les dates, heures et millisecondes de création du fichier. DIR_LstAccDate est la date de dernier accès au fichier. DIR_Wrt* sont les dates et heures de dernière écriture sur le fichier.
Le champ DIR_FstClusLO est le numéro du premier cluster du fichier en FAT12 et FAT16. En FAT32, le champ DIR_FstClusLO ne faisant que 16 bits, on a besoin du champ DIR_FstClusHI pour constituer un numéro de cluster entier. DIR_FstClusLO est la partie basse (LOW) du cluster, tandis que DIR_FstClusHI est la partie haute (HIGH). En FAT12/FAT16, le champ DIR_FstClusHI doit être à 0. La macro suivante reconstitue le numéro du premier cluster du fichier en fonction de la structure ci-dessus :
/** Helper macro to get the first * cluster of the node entry */ #define GET_FIRST_CLUSTER(dir_entry) \ (((dir_entry)->DIR_FstClusHI<<16) | \ (dir_entry)->DIR_FstClusLO)
Dernier champ de la structure d’entrée de répertoire, le champ DIR_FileSize contient la taille du fichier en octets.
5.2 Le champ DIR_Name
Il y a plusieurs remarques à faire concernant le premier caractère du champ DIR_Name.
1. Si DIR_Name[0] == 0xE5, alors l’entrée de répertoire est libre. Il n’y a pas de fichier ou de répertoire dans cette entrée.
2. Si DIR_Name[0] == 0, alors l’entrée de répertoire est libre (comme pour 0xE5) et il n’y a pas d’entrée de répertoire après celle-ci. Tous les caractères DIR_Name[0] dans toutes les entrées qui suivent doivent être à 0 aussi. La valeur spéciale 0, contrairement à la valeur 0xE5, indique au pilote de système de fichiers FAT que le reste des entrées dans ce répertoire n’a pas besoin d’être examiné puisqu’elles sont toutes libres.
3. Si DIR_Name[0] == 0x05, alors le véritable caractère doit être 0xE5. Le caractère 0xE5 est en effet un caractère kanji utilisé au Japon. Il fallait donc trouver un moyen de le représenter malgré tout.
Le champ DIR_Name est divisé en deux parties : les 8 premiers caractères sont la partie principale du nom et les 3 derniers sont l’extension du fichier. Ces deux parties sont complétées avec des espaces (caractère 0x20), si elles ne sont pas entièrement utilisées.
Le caractère DIR_Name[0] ne peut pas être une espace. Il y a implicitement un caractère . entre la partie principale et l’extension du nom de fichier qui n’est pas présent dans le champ DIR_Name. Les caractères en minuscule (lower case) ne sont pas admis dans le champ DIR_Name.
Pour résumer, voici les caractères interdits dans le champ DIR_Name :
Les valeurs inférieures ou égales à 0x20, excepté le caractère 0x05, sont interdites dans le premier caractère (DIR_Name[0]), comme décrit ci-dessus.
Les caractères 0x22, 0x2A, 0x2B, 0x2C, 0x2E, 0x2F, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, 0x5B, 0x5C, 0x5D et 0x7C sont interdits dans la totalité du champ DIR_Name.
Ces limitations sont exprimées dans la macro IS_FAT_VALID_CHAR définie avec la structure sos_fat_directory_entry décrite plus haut.
Voici quelques exemples de ce que rendent des noms de fichier de l’espace utilisateur dans DIR_Name :
«toto.txt» -> «TOTO TXT» «TOTO.TXT» -> «TOTO TXT» «Toto.Txt» -> «TOTO TXT» «toto» -> «TOTO « «toto.» -> «TOTO « “fichier.o” -> “FICHIER O “ «grosfich.big» -> «GROSFICHBIG» “.big” -> invalid, DIR_Name[0] ne peut être 0x20
Dans les répertoires FAT, les noms de fichiers sont uniques et ne tiennent pas compte de la casse. Voyez les trois premiers exemples ci-dessus. Ces noms différents se réfèrent tous au même fichier et il ne peut y avoir qu’un seul fichier avec le champ DIR_Name à «TOTO TXT» dans chaque répertoire.
5.3 Les attributs de fichier
Dans cette section, nous allons nous intéresser au champ DIR_Attr de la structure sos_fat_directory_entry.
L’attribut ATTR_READ_ONLY signifie que le fichier est en lecture seule.
L’attribut ATTR_HIDDEN précise que ce fichier ne doit pas être listé lors de l’affichage des entrées du répertoire. Ce fichier est caché à l’utilisateur.
L’attribut ATTR_SYSTEM indique que le fichier est un fichier appartenant au système d’exploitation.
L’attribut ATTR_VOLUME_ID ne doit être présent que dans le répertoire racine. Il indique que le nom de ce « fichier » est en fait le label du volume. Il n’y a donc pas de données associées, c’est pourquoi les champs DIR_FstClusLO et DIR_FstClusHI doivent toujours être à 0.
L’attribut ATTR_DIRECTORY indique que le nœud est un répertoire.
L’attribut ATTR_ARCHIVE est utilisé par les utilitaires de sauvegarde. Ce drapeau est positionné par le driver du système de fichiers FAT lorsqu’un fichier est créé, renommé (non implémenté dans notre driver, voir 1.3) ou écrit. Les utilitaires de backup utilisent cet attribut pour savoir quels fichiers dans le volume ont changé depuis la dernière sauvegarde effectuée.
L’attribut ATTR_LONG_NAME est une combinaison de tous les autres attributs. Il indique que l’entrée est une partie d’une autre entrée de fichier à nom long. Les fichiers FAT à nom long ne sont pas supportés actuellement dans SOS. Avis aux amateurs !
5.4 Création de répertoire
Un certain nombre d’initialisations sont nécessaires à la création d’un répertoire. Cette section décrit précisément le processus. Le code qui s’y réfère se trouve dans la fonction fat_link.
Lorsqu’un répertoire est créé, c’est-à-dire un fichier avec le bit ATTR_DIRECTORY positionné dans le champ DIR_Attr, il faut mettre DIR_FileSize à 0. Pour respecter la spécification [Cor00], DIR_FileSize n’est jamais utilisé et est toujours mis à 0 pour un répertoire (les répertoires ont simplement la taille de la liste chaînée de clusters jusqu’au marqueur de fin de chaîne). Un cluster est alloué au répertoire nouvellement créé (sauf pour le répertoire racine en FAT12/FAT16). On initialise les champs DIR_FstClusLO et DIR_FstClusHI avec le nouveau cluster et on place le marqueur EOC (EndOfCluster est un champ de la structure sos_fat_data_structure) dans l’entrée du cluster dans la FAT. Ensuite, il faut nettoyer le cluster en le remplissant de 0. Si le répertoire est le répertoire racine, alors c’est terminé (il n’y a pas d’entrées . et .. dans le répertoire racine). Si le répertoire n’est pas le répertoire racine, il nous faut deux entrées spéciales dans les deux premières entrées de répertoire du nouveau répertoire, qui ont pour nom (champ DIR_Name) :
«. « «.. «
Ces deux entrées sont appelées « point » (ou dot) et « point-point » (ou dotdot). Le champ DIR_FileSize est mis à 0 pour les deux entrées. On initialise les champs DIR_FstClusLO et DIR_FstClusHI de l’entrée point (la première) aux mêmes valeurs que dans l’entrée du nouveau répertoire que l’on crée.
Finalement, on remplit les champs DIR_FstClusLO et DIR_FstClusHI de l’entrée point-point (la deuxième) avec le premier cluster du répertoire dans lequel on crée le nouveau répertoire. Quand la valeur est 0, alors ce répertoire est le répertoire racine même en FAT32.
Pour résumer :
- L’ entrée
pointpointe sur lui-même. - Et l’entrée
point-pointpointe sur le premier cluster du répertoire parent de ce répertoire (qui est 0 si le répertoire parent est racine).
Vous savez maintenant tout sur la création d’un répertoire dans le système de fichiers FAT. À vous maintenant d’implémenter en exercice les estampilles temporelles pour les nœuds.
Contrairement aux autres répertoires, le répertoire racine de n’importe quel type de FAT n’a pas de date de modification, pas de nom (mis à part le nom implicite \) et ne contient pas de fichiers . et .. dans ses premières et secondes entrées de répertoire. Le seul autre aspect spécial du répertoire racine est qu’il est le seul répertoire dans le volume FAT dans lequel il est valide d’avoir un fichier qui a uniquement le bit d’attribut ATTR_VOLUME_ID positionné (voir la section 5.3 pour plus d’information).
6. Intégration au VFS
Le système de fichiers FAT s’interface avec le VFS. Cette section décrit succinctement cette intégration. Pour plus de détails, je vous laisse découvrir le code contenu dans le fichier drivers/fs_fat.c et notamment les fonctions sos_fat_helper_* qui permettent de manipuler le tableau des clusters du volume et les entrées de répertoire pour les opérations du VFS.
Les structures du VFS ont déjà été décrites dans l’article 8. La seule structure spécifique au système de fichiers FAT est dans le champ custom_data de cette structure.
6.1 sos_fs_node
Dans le cas d’un répertoire, cette structure contient la structure sos_fat_directory_entry que nous avons vue à la section 5, sauf pour le répertoire racine qui n’a pas d’entrée de répertoire. Pour un fichier, la structure est plus complexe pour tenir compte des mappings de fichier. Voici la structure sos_fat_file spécifique au fichier placé dans sos_fs_node::custom_data :
/** Fat mmap page list structure */
struct sos_fat_mmap_page_list {
/* Next page of the file */
struct sos_fat_mmap_page_list *next;
/* Offset in the file. Must be a
multiple of PAGE_SIZE */
sos_luoffset_t offset;
/* The page fill of datas of the file */
sos_vaddr_t mmap_page;
};
/** Fat file informations */
struct sos_fat_file {
struct sos_fat_directory_entry dir_entry;
/* Needed variables to map the file */
struct sos_umem_vmm_mapped_resource mapres;
sos_count_t num_mappings;
/* The list is ordered by offset */
struct sos_fat_mmap_page_list *list;
};
Vous remarquerez que la structure sos_fat_directory_entry est présente en premier dans la structure sos_fat_file. Ceci n’est pas innocent. C’est pour permettre, dans les opérations qui supportent les deux types de nœuds, d’accéder à la structure sos_fat_directory_entry sans avoir à connaître le type de ce nœud (fichier/répertoire).
Les autres champs de cette structure servent uniquement pour les opérations de mapping de fichier. sos_umem_vmm_mapped_resource définit le fichier comme une ressource pour l’opération mmap. num_mappings est un compteur de références qui compte le nombre de mappings dans le fichier. Enfin, la structure sos_fat_mmap_page_list est la liste des pages mappées triées par ordre de position croissante dans le fichier. Cette structure contient l’offset de la page dans le fichier, un pointeur sur la page mappée et un pointeur sur le mapping suivant dans le fichier.
6.2 sos_fs_opened_file
Dans la structure VFS de fichier ouvert, le champ custom_data n’est utilisé que pour les répertoires. Ici, pas de structure spécifique utilisée pour le système de fichiers FAT. On a uniquement besoin de la structure sos_fs_dirent définie dans le fichier sos/fs.h pour l’opération readdir du VFS.
7. Démonstration
Pour la démonstration de ce mois-ci, rien d’extraordinaire. Quelques fonctions ont été ajoutées au shell. Au nombre des nouvelles fonctionnalités, les commandes mount, umount, chdir, rmdir font leur apparition, ainsi qu’une commande mmap qui teste quelques appels au syscall mmap.
Un programme de test a été dérivé de fstest pour tenir compte des spécificités du système de fichiers FAT. Il se nomme fstestfat et on pourra le lancer, dans une arborescence FAT de préférence, avec la commande spawn fstestfat.
Ne lancez SOS sur une vraie machine que si vous êtes certain que toutes vos données de toutes les partitions de tous vos disques peuvent être perdues sans regret. Seulement dans ce cas-là, vous pourrez lancer SOS et/ou fstestfat sur la vraie machine. Dans tout cas contraire, faites vos essais sur une machine virtuelle telle que qemu avec une image disque comme expliqué ci-dessous. En aucun cas, ni l’auteur de cet article, ni les auteurs de SOS ne sauraient être tenus responsables de quelque perte de données que ce soit.
Pour avoir un volume FAT à notre disposition, nous utilisons comme dans l’article précédent une image disque. Voici la procédure de création pour une image disque contenant un volume FAT :
Création d’une image disque :
# dd if=/dev/zero of=hd20M.img bs=1M count=20 20+0 enregistrements lus 20+0 enregistrements écrits #
Création de 2 partitions de 10 mégaoctets. La première partition est un volume FAT16, la seconde pourra être utilisée lors du futur article sur le système de fichiers Ext2 :
# fdisk hd20M.img Commande (m pour l’aide): x Commande pour experts (m pour de l’aide): c Nombre de cylindres (1-1048576): 320 Commande pour experts (m pour de l’aide): h Nombre de têtes (1-256, par défaut 255): 4 Commande pour experts (m pour de l’aide): s Nombre de secteurs (1-63, par défaut 63): 32 Commande pour experts (m pour de l’aide): r Commande (m pour l’aide): n Action de commande e étendue p partition primaire (1-4) p Numéro de partition (1-4): 1 Premier cylindre (1-320, par défaut 1): 1 Dernier cylindre (1-320, par défaut 320): 160 Commande (m pour l’aide): n Action de commande e étendue p partition primaire (1-4) p Numéro de partition (1-4): 2 Premier cylindre (161-320, par défaut 161): 161 Dernier cylindre (161-320, par défaut 320): 320 Commande (m pour l’aide): t Numéro de partition (1-4): 1 Code Hex (taper L pour lister les codes): 6 Commande (m pour l’aide): p Disque hd20Mo.img: 0 Mo, 0 octets 4 têtes, 32 secteurs/piste, 320 cylindres Unités = cylindres de 128 * 512 = 65536 octets Périphérique Amorce Début Fin Blocs Id Système hd20Mo.img1 1 160 10224 6 FAT16 hd20Mo.img2 161 320 10240 83 Linux Commande (m pour l’aide): w La table de partitions a été altérée! Synchronisation des disques. #
Formatage de la première partition d’une image disque :
# losetup -o 16384 -s 10469376 /dev/loop0 hd20M.img # DISPLAY=»/dev/loop0» mformat -t 320 -h 4 -n 32 x: # losetup -d /dev/loop0
Pour ceux qui le souhaitent, une image disque pré-formaté en FAT16 est à disposition dans le répertoire extra de l’archive du code de cet article.
Si vous voulez pré-remplir le volume FAT :
# mkdir -p mount # mount -t vfat -o loop /dev/loop0 mount/ [ Manipulation de l’arborescence FAT ] # umount mount/
Lorsque vous passez les tests du programme fstestfat, faites-le sur un volume FAT vide de votre disque-image. Cela vous assurera par exemple qu’un test n’échoue simplement parce que le fichier a déjà été créé. Voici une manière de passer les tests dans le shell SOS :
$ mkdir mnt $ mount -t FAT /dev/hda1 mnt $ cd mnt $ spawn fstestfat
Vous pouvez ensuite regarder le résultat des tests sur la sortie du port 0xe9 de qemu.
Conclusion
Dans cet article, nous avons étudié le système de fichiers FAT, son histoire, ses types et sa structure. Parallèlement, son implémentation dans SOS a été présentée avec pour épilogue son intégration au VFS.
La démonstration du mois, très sommaire, nous permet de monter un système de fichiers FAT et de faire tourner une série de tests dessus. Mais, l’important à retenir est que nous pouvons maintenant sauvegarder nos données dans un système de fichiers.
Mais, celui-ci ne peut pas être un système de fichiers racine d’un système de type Unix comme SOS, car il ne supporte pas les fichiers spéciaux. La prochaine étape sera l’étude d’un système de fichiers qui puisse (entre autres) les supporter pour s’affranchir de Virtfs en système de fichiers racine. Ce système de fichiers sera Ext2.
En attendant, à vos claviers !
Référence :
- [Cor00] Microsoft Corporation, Microsoft Extensible Firmware Initiative FAT32 File System Specification, Microsoft, http://www.csn.ul.ie/_mel/projects/vm/, 2000.
Retrouvez cet article dans : Linux Magazine 98
