Quelques exemples de SGF

g n ral, la partie ressource est assez petite, mais, si elle n'est pas vide, elle occupe au moins un bloc.

Le descripteur de fichier contient la description des trois premi res zones allou es chacune des parties du

fichier, chaque zone tant d crite par le num ro du premier bloc et le nombre de blocs. Si une partie a besoin de

plus de trois zones, les descriptions des zones manquantes sont regroup es, par groupe de 3, dans le fichier de

description des extensions vu plus haut.

Chaque entr e de ce fichier est constitu e des champs suivants, les trois premiers composant la cl

d'identification de l'entr e:

" Num-ID du fichier.

"

" Num ro logique l'int rieur du fichier correspondant la premi re zone. Ce num ro est en fait gal la

Indicateur pr cisant si on a affaire la partie ressource ou la partie donn es.

somme des longueurs des zones allou es qui pr c dent la premi re du groupe.

" Description des trois zones allou es.

Pour faciliter les acc s, les entr es sont organis es en arbre B*. Nous n'entrerons pas ici dans le d tail d'une

telle structure, mais nous sugg rons le lecteur de voir un cours de structures de donn es. Bri vement, la figure

11.1 donne un exemple simple d'arbre B*, o les cl s sont simplement des entiers. Dans notre cas, chaque nSud

occupe un secteur.

Fig. 11.1. Exemple d'arbre B* utilis dans HFS.

Notons que si un fichier est fragment , et occupe plus de 3 zones, le syst me devra rechercher dans l'arbre le ou

les groupes de 3 zones n cessaires. Cependant, les entr es correspondantes sont en fait ordonn es dans le

fichier de description des extensions, puisqu'il s'agit d'un arbre B*.

Le fichier de description des extensions est galement utilis pour conserver les blocs invalides, c'est- -dire

ceux pour lesquels on a d tect une erreur permanente. Ces blocs sont affect s, comme zone d'extension, un

objet externe de Num-ID particulier qui n'est rep r par aucun r pertoire. Ainsi, ces blocs sont consid r s

comme allou s, mais l'objet auquel ils sont allou s n'est pas accessible.

11.2.2. Les r pertoires

Ce syst me utilise une arborescence de r pertoires, mais avec une repr sentation originale de cette

arborescence, puisque l'ensemble est galement repr sent dans un arbre B* unique, que nous avons appel ci-

dessus le catalogue des fichiers et r pertoires. chaque objet externe, on associe une entr e de ce catalogue qui

est constitu e essentiellement des champs suivants, les deux premiers composant la cl d'identification de

l'entr e:

" Num-ID de son r pertoire parent.

" Nom de l'objet externe, limit 31 caract res quelconque l'exception du ':', la casse n'intervenant pas

dans les comparaisons.

" Le type de l'entr e, et donc de l'objet externe, fichier ou catalogue.

" Dates de cr ation, modification et sauvegarde.

" Num-ID de l'objet lui-m me.

" Descripteur de fichier dans le cas d'un fichier. En particulier, pour chacune des parties du fichier, la

taille physique (allou e), sa taille logique (utile) et les descripteurs des trois premi res zones allou es

cette partie.

Par ailleurs, le catalogue contient des entr es sp ciales qui permettent de remonter dans l'arborescence depuis

un r pertoire son parent, et que nous appellerons un lien. Une telle entr e est constitu e comme suit, les deux

premiers champs tant toujours la cl de l'entr e:

" Num-ID du r pertoire

"", ou cha ne vide.

"

" Le type de l'entr e en tant que lien.

" Num-ID de son parent.

" Nom du r pertoire lui-m me.

Par ailleurs, le catalogue, en tant que arbre B*, a toutes ses entr es ordonn es par cl s croissantes. Par

cons quent, le lien d'un r pertoire vers son parent est imm diatement suivi des entr es correspondant aux objets

externes qu'il contient.

11.2.3. Coh rence du SGF

Comme dans tout syst me de gestion de fichier, les informations sur la structure sont tr s importantes et doivent

tre coh rentes entre elles. Ainsi, la table bitmap ne doit pas indiquer comme libre un bloc qui serait allou un

fichier. Conform ment ce que nous avons dit en 10.2.1, lorsqu'il y a redondance d'informations, on peut

distinguer les informations primaires et les informations secondaires, celles-ci ayant pour but de donner des

acc s efficaces. Dans le cas des informations sur l' tat d'allocation des blocs, les informations primaires sont les

descriptions des zones allou es, et la table bitmap constitue les informations secondaires permettant d'acc l rer

les recherches de blocs libres.

De m me, pour pouvoir attribuer un Num-ID aux objets lors de la cr ation, il faut conna tre le dernier attribu .

Cette information secondaire est m moris e dans le descripteur du volume. L'information primaire est

repr sent e en fait par la plus grande valeur des Num-ID existant sur le volume.

Pour garantir cette coh rence, HFS maintient un indicateur dans le descripteur de volume, qui indique que le

volume n'a pas t d mont proprement. Cet indicateur est crit sur disque lors du montage en criture du

volume, et remis z ro lors du d montage du volume. Il permet donc de savoir lors d'un montage si une

v rification de coh rence est n cessaire.

11.2.4. Le syst me HFS Plus

Ce syst me a pour but de lever les contraintes rencontr es dans HFS. Nous ne mentionnerons ici que les

modifications les plus importantes pour l'usager:

" La plus importante que nous ayons vu est la limitation du nombre de quanta d'une partition, impliquant

d'avoir une taille de quantum importante pour les grosses partitions. Cette contrainte est lev e en

prenant 32 bits pour les num ros de blocs d'allocation. videmment cela a pour cons quence

d'augmenter notablement la table bitmap, qui devient un fichier, permettant d'homog n iser les acc s.

" La taille maximale de chacune des parties d'un fichier est elle aussi augment e, puisqu'elle est port e

263 octets.

" Comme les blocs deviennent plus petits et peuvent conduire une fragmentation plus importante, et

donc un nombre plus grand de zones, les groupes ont t port s 8, tant dans le descripteur de fichier

que dans les entr es du fichier de description des extensions.

" Les noms des objets ne sont plus limit s 31 caract res MacRoman (codage sur 8 bits), puisqu'un nom

peut avoir maintenant 255 caract res Unicode (16 bits). Ceci a conduit augmenter la taille des nSuds

de l'arbre B* du catalogue (4 Ko par d faut), car plus ces nSuds contiennent de valeurs, plus la hauteur

de l'arbre est faible.

" Un troisi me fichier de volume organis en arbre B* a t introduit pour permettre terme de g rer

plusieurs attributs d'un fichier, mais il s'agit plus d'ouverture vers l'avenir et d' viter ainsi d'avoir

red finir un nouveau SGF, car les sp cifications compl tes ne sont pas encore compl tement d finies en

mars 1999. Ce fichier devrait permettre, par exemple, d'avoir plus de deux parties pour un m me fichier,

et de pouvoir nommer ces parties.

11.3. Le syst me NTFS

Ce syst me a t cr par Microsoft pour tre le syst me de gestion de fichier de Windows NT. Plusieurs

syst mes existaient initialement, comme VFAT ou HPFS de OS/2, mais aucun ne satisfaisait aux crit res de

fiabilit et de taille d'un syst me moderne.

En dehors du premier secteur de la partition, qui contient un ensemble minimal d'informations comme la

localisation du fichier MFT dont il est question ci-dessous, ce SGF consid re que "tout est fichier". Le

formatage d'une partition en volume NTFS consiste donc cr er un certain nombre de fichiers qui donnent la

structure du volume. Nous ne d crirons que certains de ces fichiers.

" Le fichier des descripteurs de fichiers, appel la Master File Table (MFT), qui commence par son

propre descripteur. Il peut commencer n'importe o dans la partition, il est n cessaire de conna tre cet

endroit a priori, pour pouvoir acc der son descripteur, ce qui est indiqu dans le premier secteur de la

partition. Notons que ce fichier est doubl pour des raisons de s curit , la copie tant aussi rep r e par le

secteur 0 de la partition.

" Le fichier du volume, contenant en particulier le nom du volume.

" Le fichier bitmap d crivant l' tat d'allocation du volume.

" Le r pertoire racine du volume.

" Le fichier journal qui a pour but de garantir la fiabilit de la structure.

11.3.1. Les descripteurs de fichiers

Chaque objet externe re oit, sa cr ation, un num ro qui est l'indice dans la MFT o est situ son descripteur.

La taille de ces descripteurs est fix e la cr ation du volume et est comprise entre 1 Ko et 4 Ko, ce qui est donc

relativement important. Un objet externe, fichier ou r pertoire, est constitu d'un certain nombre d'attributs qui

peuvent tre r sidents, c'est- -dire, rang s dans le descripteur de l'objet externe lui-m me, ou non r sident et

donc l'ext rieur de la MFT dans un espace qui lui est allou en propre. Voici quelques exemples d'attributs :

" Le nom de l'objet externe sous forme d'une suite de au plus 255 caract res Unicode.

" Les informations de base habituelles, comme les dates de cr ation, modification ou d'acc s.

" Les informations de protections de l'objet.

" Le ou les contenus des fichiers ou r pertoires.

Un m me objet externe peut avoir plusieurs attributs "nom", correspondant au principe des liens physiques

nonc s au 9.4.3.

Si un fichier est suffisamment petit, tous ses attributs, et donc son contenu se trouvera dans le descripteur. Dans

les autres cas, certains attributs (en particulier les donn es) seront non r sidents.

NTFS utilise le principe de l'allocation par zone pour les attributs non r sidents d'un objet externe , et la valeur

de l'attribut est remplac e dans le descripteur par la suite des descriptions des zones allou es. Le nombre de

zones est quelconque, chacune tant de taille quelconque (cf. 8.2.3). La taille du quantum est un nombre entier

de secteurs, ce nombre tant une puissance de 2. Le terme de cluster d signe les unit s d'allocation. Les clusters

sont num rot s sur 64 bits, ce qui implique qu'il n'y a pratiquement pas de limite aux nombres de clusters d'un

volume. Comme un descripteur de zone doit localiser le premier cluster de la zone et son nombre de clusters,

soit 16 octets, une technique de compression est utilis e, d'une part en prenant son d placement par rapport au

premier cluster de la zone pr c dente, et en supprimant les octets nuls en t te de ces deux valeurs.

La longueur d'un attribut non r sident est m moris e sur 64 bits, ce qui permet donc des fichiers dont la taille

n'est pratiquement limit e que par l'espace disponible sur le volume.

Notons que le contenu d'un fichier est un attribut sans nom, mais l'utilisateur peut cr er des attributs nomm s

qui peuvent avoir des contenus s par s dans des espaces distincts. L'implantation de serveur de fichier

MacIntosh sur Windows NT utilise ce principe pour s parer la partie ressource et la partie donn e (voir HFS).

11.3.2. Les R pertoires

NTFS utilise une arborescence de r pertoire. Le contenu d'un r pertoire est organis en arbre B+, qui se

rapprochent des arbres B* vus plus haut, si ce n'est que les donn es associ es aux cl s sont r parties dans tous

les nSuds au lieu de n' tre que dans les feuilles comme sur la figure 11.1. Les entr es d'un r pertoire

contiennent les informations suivantes, la premi re tant la cl :

" Le nom de l'objet,

" Le num ro de l'objet dans la MFT, permettant de localiser son descripteur.

" Les dates de cr ation, modification ou d'acc s de l'objet,

" La taille de l'objet

" Le num ro du r pertoire parent qui le contient dans la MFT.

En fait seuls les deux premiers sont effectivement n cessaires, puisque les trois derniers se trouvent dans le

descripteur de l'objet. Cette duplication a un avantage et un inconv nient. L'avantage est que l'on a acc s aux

informations essentielles de l'objet sans devoir acc der au descripteur. L'inconv nient est inh rent la

duplication: toute modification de ces informations doit tre port e plusieurs endroits sur le disque, sous peine

d'avoir des donn es incoh rentes. Notons qu'il peut para tre surprenant de trouver dans cette entr e le num ro

du r pertoire qui contient l'entr e! En fait, Toutes ces informations, avec la cl , font partie l'attribut "nom de

fichier", pr sent dans le descripteur du fichier, et en sont une copie. Or, le num ro du r pertoire parent d'un

fichier permet de remonter l'arborescence des fichiers et r pertoires, en retrouvant ainsi le parent de chaque

r pertoire.

Le principe des arbres B implique que des nSuds soient cr s ou supprim s au fur et mesure des adjonctions

ou suppressions. La suppression d'un nSud peut ne pas tre le dernier nSud physique du r pertoire, et il faut

pr voir sa r utilisation ult rieure. Ceci se fait en d finissant un attribut "bitmap" pour chaque r pertoire qui

indique quels sont les nSuds libres. S'il n'y en a plus, une allocation d'une nouvelle zone est effectu e, et la

table bitmap est mise jour pour tenir compte des nSuds libres ajout s.

11.3.3. Compression de donn es

NTFS propose une technique de compression/d compression des fichiers au fur et mesure des acc s. L'id e

est de d couper le contenu du fichier par tranche dont la taille correspond 16 clusters, et de tenter de

compresser chaque tranche ind pendamment les unes des autres. La compression n'est effective que si elle fait

gagner au moins 1 cluster. Dans ce cas, les clusters gagn s ainsi sont m moris dans la suite des descripteurs de

zones par une zone marqu e non allou e dont la taille correspond au nombre de clusters gagn s. A la lecture,

l'op ration inverse est effectu e. Notons que la mise en Suvre de la compression/d compression sur un fichier

est m moris dans le descripteur du fichier, l'utilisateur n'ayant pas s'en pr occuper ensuite. videmment cette

technique est co teuse en temps processeur, et doit tre utilis e bon escient.

11.3.4. S curit par fichier journal

Les op rations mises en Suvre sur les structures de fichiers, en g n ral, concernent plusieurs secteurs distincts

r partis sur le volume. Les modifications ne peuvent toutes tre port es sur le disque en une seule fois, mais

doivent tre effectu es en s quence. videmment, les syst mes tiennent compte de l' ventualit d'une panne qui

emp che le d roulement complet de la s quence et entra ne une incoh rence. Ceci est obtenu en d finissant

pour chaque op ration l'ordre qui donnera le minimum de d g t en cas de panne. En particulier, il est pr f rable

de perdre de l'espace disque plut t que de risquer d'allouer deux fois le m me bloc deux objets diff rents. En

fait, il est presque toujours possible de r tablir la coh rence et retrouver les blocs non allou s, mais cela peut

tre co teux en temps.

Dans le cas des SGF modernes, le risque est aggrav par le fait que bien souvent les op rations sont effectu es

dans des tampons en m moire, et que l' criture de ces tampons sur disque est effectu e plus tard, pour gagner

en performance et en efficacit (principe de l' criture paresseuse). Par exemple, une cr ation de fichier donnera

souvent lieu dans un avenir proche une ou plusieurs allocations d'espace disque. Le report des critures de la

table bitmap peut avoir pour cons quence qu'elle ne sera crite qu'une seule fois lorsque tout sera termin .

La structuration d'un volume en NTFS contient un fichier particulier, dit fichier journal, qui va avoir un r le

analogue au fichier journal des syst mes de gestion de bases de donn es classiques, dans lequel sera m moris e

la s quence des actions effectu es sur le disque dans le but de pouvoir soit les refaire soit les d faire apr s une

panne. Cette utilisation fait appel la notion de transaction, qui signifie, entre autre, que l'on garantit que toutes

les op rations l mentaires de la transaction sont effectu es, m me en cas de panne, ou que aucune n'est faite.

Expliquons bri vement le d roulement des op rations lors de la cr ation d'un fichier avec allocation d'espace.

Les op rations sont les suivantes:

1. Initialisation d'une transaction.

2. Cr ation d'un descripteur du fichier dans la MFT.

3. Cr ation de l'entr e dans le r pertoire parent,

4. Mise l' tat non libre des bits correspondants aux clusters allou s, dans la bitmap,

5. Cl ture de la transaction.

Les op rations 2, 3 et 4 sont faites dans des tampons en m moire, et lors de la cl ture de la transaction, il est

probable que ces tampons n'ont pas encore t crits sur disque. Chacune de ces op rations donne lieu un

enregistrement dans le fichier journal qui d crit comment "refaire" et comment "d faire" l'op ration

correspondante. En fait ces enregistrements sont mis dans des tampons en m moire, en vue d'une criture

ult rieure, comme pour tout fichier. Cependant le gestionnaire de ces tampons fera en sorte que les tampons du

fichier journal soient crits sur disque avant l' criture des autres tampons. De plus, p riodiquement, l' tat des

transactions ainsi que la liste des tampons en m moire non encore crits sur disque sont enregistr s dans le

fichier journal. En cas de panne une analyse du fichier journal permet de savoir les transactions cl tur es dont

les actions n'ont pas t port es physiquement sur disque et qui doivent donc tre refaites, ou les transactions

non cl tur es dont les actions port es physiquement sur disque doivent tre d faites.

11.4. Le syst me ext2fs de Linux

Linux est un syst me d'exploitation qui s'apparente fort Unix, tout en tant un logiciel libre. Le syst me de

fichier initial tait d riv de celui du syst me Minix, lui aussi d riv d'Unix pour l'enseignement. Le SGF de

Minix tant cependant trop contraint, un nouveau syst me de gestion de fichier a t crit, ext2fs.

11.4.1. La repr sentation de l'espace

Comme d'habitude, l'ensemble du disque est d coup en blocs dont la taille est un multiple (puissance de 2) de

la taille d'un secteur. Ext2fs pratique l'allocation par bloc de taille fixe, plusieurs niveaux (cf. 8.3.2). Les

descripteurs d'objets externes sont repr sent s dans ce qui est appel un inSud, qui sont regroup s dans une

table, l'indice dans la table, appel le num ro du inSud (i est l pour integer), identifiant de fa on unique cet

objet. Une table bitmap d crit l' tat d'allocation des inSuds, et une autre d crit l' tat d'allocation des blocs. Pour

des raisons de performances, en particulier sur les gros disques, ces tables sont morcel es et r parties dans la

partition.

Une partition est d coup e en groupes de m me taille, chaque groupe comportant 6 parties:

" Le super bloc, qui contient les informations de structure du volume.

" La liste des descripteurs de groupe, qui localise sur le disque les informations essentielles de chaque

groupe (localisation des tables).

" La table bitmap d' tat d'allocation des blocs du groupe.

" La table bitmap d' tat d'allocation des inSuds du groupe.

" La table des inSuds du groupe.

" Les blocs de donn es.

Le super bloc et la liste des descripteurs de groupe sont donc r p t s au d but de chaque groupe, pour des

raisons de fiabilit . Lors du montage, on ne lit en fait que ceux du premier groupe. Cette s paration en groupes

doit plus tre vue comme une r partition des donn es sur le disque, dans le but d'am liorer les performances. La

taille d'un groupe est d'ailleurs limit e, puisque chaque table bitmap d'un groupe doit tenir dans un seul bloc. Si

la taille de la partition est importante, il y aura beaucoup de groupes.

Les groupes ont pour but de rapprocher dans un espace physique proche les informations qui sont reli es entre

elles. Ainsi, lors d'une allocation d'un inSud, on cherchera de pr f rence dans le groupe du r pertoire o il est

r f renc ; de m me, lors de l'allocation d'un bloc, on cherchera d'abord le bloc qui suit le dernier allou

l'objet, puis dans son voisinage imm diat ( 32), puis dans le m me groupe et enfin dans les autres groupes.

Un descripteur d'objet externe contient videmment le type de l'objet, des informations pour sa protection, sa

longueur, les dates habituelles de cr ation, modification, acc s et destruction, ainsi que les informations de

localisation du contenu, qui sont semblables celles de la figure 8.4 (la seule diff rence est qu'il y a en g n ral

12 blocs directs au lieu de 10). La taille d'un objet externe est limit 2 Go, mais la taille d'une partition peut

atteindre 4 To.

11.4.2. Les r pertoires

Ext2fs g re une arborescence de fichiers. Le contenu d'un r pertoire tant une liste d'entr es constitu es de

couples <inSud, nom>, le nom tant limit 255 caract res. Les deux premi res entr es d'un r pertoire sont les

entr es "." et ".." habituelles. Il est possible d'avoir plusieurs noms ou chemins d'acc s pour le m me inSud.

Ceci a pour cons quence que la suppression d'une entr e dans un r pertoire n'entra ne pas obligatoirement la

suppression du inSud correspondant. Celle-ci ne sera effective que s'il n'existe plus d'entr e associ e ce

inSud dans aucun r pertoire. En dehors de la suppression d'une entr e dans un r pertoire, qui n'affecte donc que

cette entr e, toutes les autres op rations effectu es par l'un des chemins aura les m mes r percussions par

l'autre.

Ce syst me permet aussi la cr ation de liens symboliques (cf. 9.4.3). Dans ce cas, il s'agit de cr er un objet

externe (avec inSud et contenu), du type lien symbolique, et dont le contenu sera le chemin d'acc s l'objet

reli . Rappelons que dans ce cas la recherche de l'objet externe reli implique la r valuation du chemin

d'acc s.

11.4.3. S curit

Comme beaucoup de syst mes, ext2fs est bas sur l'utilisation de caches m moire des blocs disques, l' criture

des blocs modifi s tant report e ( criture paresseuse). Cela peut avoir pour cons quence des incoh rences dans

la structure du volume. L' criture d'un bloc est effective lorsque le tampon qu'il occupait est r cup r pour un

autre bloc. De plus, cette criture est forc e automatiquement une p riode r guli re. Comme tous les

syst mes, il est cependant recommand de toujours l'arr ter par la commande associ e. Dans ext2fs, chaque

objet externe, est attach un indicateur qui, lorsqu'il est positionn , demande que le inSud et les blocs indirects

sur disque soient synchrones avec leur contenu en m moire, c'est- -dire, que toute modification en m moire

soit port e imm diatement sur le disque, avant de retourner au programme d'application. Pour l'utilisateur, la fin

d'ex cution de l'op ration signifie pour lui un tat coh rent de la structure disque, en regard de son fichier.

Notons deux attributs d finis par ext2fs et attach s chaque fichier :

" L'attribut de "secret" implique que, lors de la destruction du fichier, le contenu doive tre effac en le

remplissant de donn es al atoires. Cela vite que des donn es sensibles puissent tre vues lors de la

r allocation des blocs qui les contenaient.

" L'attribut de "r cup ration" permet la r cup ration d'un fichier d truit, jusqu' un certain point.

11.5. Structuration en couche du syst me

Certains syst mes permettent de manipuler, au m me moment, des volumes structur s diff remment. C'est

assez naturel lorsque l'un des SGF est une extension de l'autre par le m me concepteur, comme par exemple

HFS et HFS Plus. La caract ristique de standard de fait de FAT fait que pratiquement tous les syst mes

implantent ce SGF en plus de leur propre SGF propri taire. Windows NT reconna t et g re FAT, VFAT, HPFS

(de OS/2) et NTFS. Il ne reconna t pas HFS, mais est capable de simuler un serveur de fichier de ce type sur un

r seau, en s'appuyant sur NTFS. Linux permet la manipulation de tous les SGF voqu s dans ce chapitre, au

moins en lecture, si ce n'est en criture.

La reconnaissance simultan e de plusieurs SGF est en g n ral bas sur un d coupage du logiciel en couches, en

d finissant les sp cifications entre les couches:

" Le syst me de fichier virtuel (SFV) est la vue homog ne de tous les SGF r els. Il est d fini en interne en

terme de structures de repr sentations et d'op rations de manipulations de ces structures.

" Le syst me de tampons m moire qui contiennent les blocs disque (le cache).

" Le disque abstrait est une vue homog ne des tous les disques support s par l'installation. Il d finit un

ensemble d'op rations d'acc s disques l mentaires ind pendantes des p riph riques physiques eux-

m mes .

Les couches du logiciel sont les suivantes:

" La couche haute, proche de l'application, implante les op rations d'acc s n cessaires aux programmes

d'applications en voyant le syst me de fichier avec la structure de SFV.

" La couche interm diaire, li e un SGF, assure l'interface entre le SFV et les tampons m moire. Elle

assure la transformation entre les structures du SFV et du SGF particulier et implante les op rations du

SFV, selon les caract ristiques du SGF, en se servant de ces tampons.

" Le gestionnaire de cache g re les tampons m moire et lance les op rations n cessaires vers le disque

abstrait.

" Les pilotes des disques, li s aux p riph riques eux-m mes, implantent les op rations du disque abstrait

en terme d'op rations concr tes du disque.