FAT

Le format FAT existe depuis l'aube de l'informatique. On utilise principalement le format :

• FAT32 pour les partitions de boot et les clé USB de moins de 32GiB
• exFat pour les clés USB de taille supérieure à 32GiB

Le format exFat étant essentiellement une mise à jour du format FAT32, c'est lui que nous allons présenter (et donnerons lorsque c'est nécessaire les différence d'avec le format FAT32).

Principe

Chaque ficher est stocké dans une suite de blocs du disque dur. Un bloc est un multiple d'un secteur physique et correspond à un découpage logique du disque. Le nombre maximum de bloc est fixé par le format, pour augmenter la taille de ce que l'on peut stocker on augmente la taille des blocs (de 4Kib, à 32MiB).

La FAT est un tableau de taille égale au nombre de bloc auto-référant se comportant comme une liste chaînée contenant les bloc sde tous les fichiers qui y sont stockés.

Par exemple, en considérant la FAT ce-dessous de taille 8 :

index valeur
0    :  2
1    :  8       
2    :  3
3    :  8
4    :  7
5    :
6    :
7    :  1

Et que l'on sait que notre file système contient deux fichiers, l'un commençant bloc 0, l'autre en 4, on en conclut que :

• le fichier commençant en 0 possède les blocs 0, 2, 3
• le fichier commençant en 4 possède les blocs 4, 7, 1

Les blocs peuvent être de deux types :

• donnée : ils contiennent une suite de byte formant le fichier
• dossier : contient la liste des fichiers/dossiers qu'il contient ainsi que leurs 1er blocs respectifs

On stocke donc à la fois les données et la structure en dossier dans les blocs eux même.

Tailles Limites

• FAT32
  • nombre maximum de blocs : $2^{28}$
  • taille maximum de bloc : 32KiB
  • taille de fichier codée sur 4B (donc la taille maximale est 4GiB)
  • nombre maximum de fichiers par dossiers : $2^{16}$
• exFAT
  • nombre maximum de blocs : $2^{32}$
  • taille maximum de bloc : 32MiB
  • taille de fichier codée sur 8B (donc la taille maximale est 16EiB)
  • nombre maximum de fichiers par dossiers : virtuellement illimitée

Structure du disque

Le découpage de la structure est en 4 parties :

1. Boot Area : contient les informations générales sur le volume
2. FAT : la fat elle même
3. bitmap des blocs
4. blocs de données

Boot Area

La première partie de la structure, nommé Boot Area contient diverse informations sur le volume. En particulier :

• la taille d'un secteur (de 512B à 4KiB)
• la taille d'un bloc, de 512B à 32MiB et habituellement 4KiB. C'est l'unité de stockage du format FAT
• le nombre de blocs du volume, au maximum $2^{32} -11$

La Boot Area est contenue sur les 12 premiers secteurs et est dupliquée dans les 12 suivant.

FAT

Est constituée d'un tableau de taille égale au nombre de blocs, chaque case du tableau faisant 32b = 4B.

C'est ce tableau qui va permettre de connaître les bloc où sont écrit des données.

Supposons que les données d'un fichier soient écrites sur les blocs numéros 4, 12, 8 et 45 dans cet ordre alors :

1. la case d'indice 4 aura 12 comme valeur,
2. la case d'indice 12 aura 8 comme valeur,
3. la case d'indice 8 aura 45 comme valeur,
4. la case d'indice 8 aura 0xFFFFFFFF comme valeur, signifiant que le fichier s'arrête.

Les trois premiers blocs étant intégralement remplis.

Cette structure en liste chaînées permet de reconstituer facilement le contenu d'un fichier si l'on possède son premier bloc.

La taille de cette partie est donc de 4B fois le nombre de blocs, qui est négligeable par rapport à la taille du disque.

En effet, la taille maximum de la FAT vaut au maximum $4/512 \simeq .7\%$ de la taille totale.

Bitmap

Une bitmap est associé aux blocs :

• 0 signifie que le bloc est libre
• 1 que le bloc est occupé

Ceci permet de rapidement savoir si un bloc est libre (par exemple, on prend 64b de cette partie et si ce nombre est inférieur au maximum (se fait en un cycle du processeur), il y a des blocs libres parmi les 64 considéré).

La taille de cette partie est le nombre de bloc bits, donc au maximum $1/(512 \cdot 8) \simeq .1\%$ de la taille totale.

Blocs de données

Chaque bloc est soit :

• une entrée pour un dossier
• une entrée pour une suite de byte constituant un fichier

Bloc dossier

Contient une entrée pour chaque dossier ou fichier le constituant, cette entrée détermine :

• le type d'entrée (fichier ou dossier)
• le bloc contenant l'entrée
• la taille de l'entrée en byte

Renseigner la taille permet de savoir où s'arrêter dans le dernier bloc.

La taille en bloc est déterminée par la FAT.

Bloc fichier

Pas de structure, uniquement une suite de byte qui constitue le ficher.

Opérations

l'ajout suppression de fichiers va rendre non linéaire le stockage ds fichiers.

Ajout

On suit la hiérarchie des dossiers jusqu'à arriver au bloc contenant le dossier pour lequel on veut ajouter une entrée. Si ce bloc est plein, on cherche un bloc libre pour étendre l'entrée de ce dossier puis on ajoute l'entrée.

On peut maintenant chercher autant de bloc libre que nécessaire pour stocker le contenu de l'entrée an ajoutant une chaîne à la FAT.

Suppression

On ne supprime que l'entrée dans le dossier contenant le fichier à supprimer. Le contenu reste présent :

• dans la FAT
• sur le disque

Il est donc possible de retrouver les données si on cherche directement sur le disque dur.