Nœud d'index

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un nœud d'index ou inode (contraction de l'anglais index et node) est une structure de données contenant des informations à propos d'un fichier stocké dans certains systèmes de fichiers (notamment de type Linux/Unix). À chaque fichier correspond un numéro d'inode (i-number) dans le système de fichiers dans lequel il réside, unique au périphérique sur lequel il est situé. Les inodes 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 inodes[modifier | modifier le code]

Les inodes contiennent notamment les métadonnées des systèmes de fichiers, et en particulier celles concernant les droits d'accès.

Les inodes sont créés lors de la création du système de fichiers. La quantité d'inodes (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]

Inode et périphérique[modifier | modifier le code]

Le numéro d'inode est un entier unique pour le périphérique dans lequel il est stocké. Le numéro d'inode d'un fichier jean-jacques peut être affiché avec la commande

ls -i jean-jacques

Le terme inode se réfère usuellement aux inodes dans les périphériques bloc (voir (en) device node) qui gèrent des fichiers réguliers, des répertoires 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. Cette norme impose donc 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 d'inode 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 de l'inode 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 inode (Nlinks).

Remarque : les inodes ne contiennent pas le nom des fichiers.

Voir (en) Stat (commande Unix).

Les différentes versions d'inode[modifier | modifier le code]

vnode de Berkeley[modifier | modifier le code]

La représentation en mémoire des inodes 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 inodes dans ReiserFS[modifier | modifier le code]

Les systèmes de fichiers Unix non traditionnels tels que ReiserFS évitent d'avoir une table des inode de taille fixe, ils utilisent une structure plus souple pour gérer les inodes.

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 (en fait, ext3 est un ext2 avec un journal en plus).

Chaque inode contient environ 64 champs, dont 13 d'entre eux 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 :

1024 * (10 + 256^1 + 256^2 + 256^3) = 17 247 250 432

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).