Nœud d'index
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section «Notes et références».
En pratique: Quelles sources sont attendues? Comment ajouter mes sources?Un nœud d'index ou inode (contraction de l'anglais index et node), ou encore i-nœud en français, est une structure de données contenant des informations à propos d'un fichier ou répertoire stocké dans certains systèmes de fichiers (notamment de type Linux/Unix). À chaque fichier correspond un numéro de nœud (i-number) dans le système de fichiers dans lequel il réside, unique au périphérique sur lequel il est situé.
Chaque fichier a un seul nœud d'index, même s'il peut avoir plusieurs noms (chacun de ceux-ci fait référence au même nœud). Chaque nom est appelé lien.
Les nœuds d'index peuvent, selon le système de fichiers, contenir aussi des informations concernant le fichier, tel que son créateur (ou propriétaire), son type d'accès (par exemple sous Unix : lecture, écriture et exécution), etc.
Importance des nœuds d'index
[modifier | modifier le code ]Les nœuds d'index contiennent notamment les métadonnées des fichiers, et en particulier celles concernant les droits d'accès.
Les nœuds d'index sont créés lors de la création du système de fichiers. La quantité de nœuds d'index (généralement déterminée lors du formatage et dépendant de la taille de la partition) indique le nombre maximum de fichiers que le système de fichiers peut contenir.
Précisions techniques
[modifier | modifier le code ]Nœud d'index et périphérique
[modifier | modifier le code ]Le numéro de nœud d'index est un entier unique pour le système de fichier dans lequel il est stocké. Le numéro de nœud d'index d'un fichier mon-fichier.txt peut être affiché avec la commande
ls-imon-fichier.txt
Le terme nœud d'index se réfère usuellement aux nœuds d'index dans les périphériques bloc (voir (en) device node) qui gèrent des fichiers réguliers, des dossiers et éventuellement des liens symboliques. Ce concept est particulièrement important pour réussir à réparer un système de fichiers endommagé (voir fsck).
Spécifications POSIX sur les attributs de fichiers
[modifier | modifier le code ]Le standard POSIX s'est basé sur les systèmes de fichiers traditionnels d'Unix. Les nœuds d'index ne contiennent pas le nom des fichiers. Les noms sont dans les entrées des répertoire, avec le numéro de nœud auquel ils font référence. C'est ce mécanisme qui permet facilement de donner plusieurs noms à un fichier. La norme POSIX impose que les fichiers réguliers aient les attributs suivants :
- La taille du fichier en octets ;
- Identifiant du périphérique contenant le fichier ;
- L'identifiant du propriétaire du fichier (UID) ;
- L'identifiant du groupe auquel appartient le fichier (GID) ;
- Le numéro de nœud d'index qui identifie le fichier dans le système de fichiers ;
- Le mode du fichier qui détermine quel utilisateur peut lire, écrire et exécuter ce fichier ;
- horodatage (timestamp) pour :
- La date de dernière modification du nœud d'index, ctime (affichée par la commande stat ou par ls -lc, modification des droits du fichier),
- La date de dernière modification du fichier mtime (affichée par le classique ls -l),
- La date de dernier accès atime (affichée par la commande stat ou par ls -lu) ;
- Un compteur indiquant le nombre de liens physiques sur cet nœud d'index (Nlinks). Lorsqu'on supprime un nom du système de fichier, le compteur de liens du nœud d'index correspondant est décrémenté. Tant que ce compteur a une valeur supérieure à un, les données du fichier sont conservées. Lorsque ce compteur tombe à zéro, c'est qu'on vient de supprimer le dernier nom qui référence ce nœud, on peut alors supprimer les données du fichier, et marquer le nœud comme inutilisé.
On remarquera, que modifier le contenu d'un fichier va effectivement modifier le mtime, et également modifier le ctime, puisqu'écrire le mtime dans le nœud modifie ce dernier. les deux dates sont donc fréquemment identiques. Cependant, modifier le propriétaire d'un fichier, ou ses permissions d'accès, ou lui ajouter un lien, sont des opérations qui ne modifient pas le contenu ; dans ce cas seul le ctime est mis à jour.
Voir stat (Unix).
Les différentes versions de nœuds d'index
[modifier | modifier le code ]vnode de Berkeley
[modifier | modifier le code ]La représentation en mémoire des nœuds d'index dans le noyau est appelée struct inode dans Linux. Les systèmes dérivés de BSD (Berkeley) utilisent une structure appelée vnod (v signifiant ici virtual).
Les nœuds d'index dans ReiserFS
[modifier | modifier le code ]Les systèmes de fichiers Unix non traditionnels tels que ReiserFS évitent d'avoir une table des nœuds d'index de taille fixe, ils utilisent une structure plus souple pour gérer les nœuds d'index.
Exemple d'utilisation : le format ext2
[modifier | modifier le code ]Ext2 est un système de fichiers courant sous Linux, bien que maintenant souvent remplacé par Ext4 (ext3 est un ext2 avec un journal en plus).
Chaque nœud d'index contient environ 64 champs, dont 13 contiennent des blocs pouvant être de deux types :
- Des blocs d'adresses, qui contiennent des pointeurs vers d'autres blocs ;
- Des blocs de données, qui contiennent les données du fichier.
Les 10 premiers champs (sur les 13) contiennent les adresses des 10 premiers blocs de données du fichier (à raison d'une adresse par bloc). Si les blocs sur lesquels pointent les 10 premiers champs sont suffisants pour contenir le fichier, les champs 11, 12 et 13 ne sont pas utilisés.
Dans le cas contraire, en plus des 10 premiers blocs, les blocs 11, 12 et 13 sont utilisés. Ces blocs fonctionnent selon un système d'indirection. Il existe trois niveaux d'indirection :
- La simple indirection, utilisée par le champ 11 ;
- La double indirection, utilisée par le champ 12 ;
- La triple indirection, utilisée par le champ 13.
Plus le niveau d'indirection est élevé, plus le nombre final de blocs de données sur lequel pointe le champ (11, 12 ou 13) sera élevé. Ce système permet donc aux fichiers d'avoir une taille considérable.
De manière concrète, chacun de ces trois champs pointe vers un bloc d'adresses, qui pourra pointer vers un ou plusieurs blocs d'adresses ou de données. En supposant que les blocs ont comme taille 1024 octets (1 Kio), et que chaque adresse (dans le cas d'un bloc d'adresses) est stockée sur 32 bits (4 octets), chaque bloc d'adresses en contiendra 256. Avec ces informations en main, il est possible de calculer la taille maximale d'un fichier.
Pour être stocké sur disque, un gros fichier ne pouvant pas être contenu dans 10 blocs de données devra utiliser les champs 11, 12 et 13.
Le champ 11 pointe vers un bloc d'adresses. Ce bloc d'adresses contient des pointeurs vers des blocs de données (256 pointeurs). C'est la simple indirection Si cela est suffisant pour contenir le fichier, en comptant les blocs pointés par les 10 premiers champs, les champs 12 et 13 ne sont pas utilisés.
Sinon, le système fera appel à double indirection (bloc 12). Ce bloc pointe, comme le champ 11, vers un bloc d'adresses. Or, ce bloc d'adresses ne pointe pas vers 256 blocs de données ; il pointe vers 256 autres blocs d'adresses. Ce sont ces 256 blocs d'adresses qui pointeront vers 256 blocs de données. Si ces blocs de données ne sont pas suffisants pour contenir le fichier dans son intégralité, il faut utiliser le 13e champ.
Le 13e champ en est un à triple indirection. Cela signifie que le champ lui-même pointe vers un bloc de 256 adresses (comme pour les blocs 11 et 12). Ces 256 pointeurs pointent chacun sur un bloc de 256 adresses, comme le champ 12. Or, ces nouveaux blocs d'adresses pointent non pas sur des blocs de données, mais sur d'autres blocs d'adresses (encore 256), qui eux, pointent vers 256 blocs de données.
En utilisant les suppositions définies plus haut concernant la taille d'un bloc et d'une adresse, il est alors simple de calculer la taille maximale d'un fichier dans un système de fichiers EXT2.
Il faut d'abord déterminer sur combien de blocs de données au total le système d'indirections pointera :
- Les 10 premiers champs pointent chacun sur 1 bloc de données ;
- Le champ 11 (simple indirection) pointe vers 2561 blocs de données ;
- Le champ 12 (double indirection) pointe vers 2562 blocs de données ;
- Le champ 13 (triple indirection) pointe vers 2563 blocs de données.
La taille maximale d'un fichier peut alors être calculée en multipliant par 1024 octets le nombre de blocs de données total :
{\displaystyle 1024*(10+256^{1}+256^{2}+256^{3})=17247250432}
La taille maximale d'un fichier avec le système de fichiers EXT2 (en considérant les suppositions ci-dessus quant à la taille des blocs) est de 17 247 250 432 octets, soit environ 16 Gio (ou 17 Go).