Cours 3: Les fichiers: vue dynamique.

Table des descripteurs, table des fichiers ouverts, table des inodes en mémoire.
Ouvrir un fichier, lire (cache de blocs de disque), écrire, fermer, rediriger, se déplacer.
Manipuler l'inode.
Manipuler des répertoires, des liens symboliques.

La figure suivante montre les différentes structures du système mises en place par le noyau pour accéder aux constituants d'un fichier.
La Table des Descripteurs de Fichiers (tdf) est propre à chaque processus. Chaque entrée de la tdf contient un pointeur vers la Table des Fichiers Ouverts (tfo) (le pointeur vaut NULL si le descripteur de la tdf est libre).
La tfo est globale et partagée par tous les processus. Ses entrées pointent sur la Table des Inodes en Mémoire (tim).
La tim contient les versions les plus à jour des inodes en accès par au moins un processus.

La figure ci-dessous décrit la tdf et ses liens avec la tfo.
La tdf se situe dans la structure-U du processus auquel elle appartient. Toutes les tdf contiennent le même nombre d'entrées.
Trois entrées de chaque tdf jouent un rôle particulier pour leur processus. L'entrée STDIN_FILENO est l'entrée standard (point de lecture des processus en avant-plan). L'entrée STDOUT_FILENO est la sortie standard (point d'écriture des processus en avant-plan). L'entrée STDERR_FILENO est la sortie erreur standard (point d'écriture des erreurs des processus en avant-plan).
Chaque entrée se compose d'un champ d'attributs du descripteur et d'un champ pointeur sur tfo.

La figure ci-dessous présente la tfo.
Chaque entrée de la tfo se compose d'un champ compteur de références (nombre de pointeurs tdf), d'un champ mode d'ouverture du fichier (lecture, écriture, etc ...), d'un champ de position dans le fichier (déplacement en octet par rapport au début) et d'un champ pointeur sur tim. Une entrée dont le compteur de référence est nul est libre.

La figure ci-dessous montre la tim.
Chaque entrée de la tim se compose d'un champ compteur de références (nombre de pointeurs tfo), d'un champ device (disque, partition où se trouve l'inode), d'un champ contenant le numéro de l'inode, d'un champ d'état (inode modifié) et enfin d'un champ contenant une copie de l'inode, dont la Table des Blocs du Fichier (tbf).

Les entrées de la table tim sont organisées en cache. Il faut garantir l'unicité des inodes dans le cache. La recherche d'un inode dans le cache est accélérée en le partitionnant. Chaque partition est une liste doublement chaînée (voir figure ci-dessous).
Parmi les inodes du cache, certains ne sont plus accédés par aucun processus. Les entrées de tim correspondantes sont libres. Les entrées libres de tim sont en liste doublement chaînée.
Voici l'algorithme de recherche d'un inode I dans le cache:

Soit P la partition du cache où I doit figurer. 
Parcourir P à la recherche de I.
Si I n'est pas trouvé dans P
   allouer la première entrée libre de tim (soit E),
   (cette entrée contenait l'inode I', de la partition P')
   si I' est modifié, le copier sur disque,
   charger l'inode I dans E,
   initialiser le compteur de références de E à 1,
   retirer E de la partition P' (le pointeur arrière est utile),
   ajouter E en tête de la partition P,
   retirer E de la liste libre.
Sinon (I est trouvé en E)
   Si E est libre (pointeurs de liste libre non nuls)
      retirer E de la liste libre (le pointeur arrière est utile),
      initialiser le compteur de références de E à 1.
   Sinon (I est accédé par un processus)
      incrémenter le compteur de références de E.

La figure ci-dessous montre une variété de situations.
On peut constater (processus p4) qu'un processus dont les accès standards n'ont pas été redirigés a les trois premières entrées de sa tdf qui désignent le même fichier (même entrée de tim) à partir de trois entrées de tfo. Ces descripteurs se partagent le même fichier mais ont des modes d'accès (lecture, écriture) et des offsets (position dans le fichier) différents.
On constate aussi que deux descripteurs de deux tdf différentes peuvent pointer sur la même entrée de tfo (après un fork qui duplique une tdf) (cas des entrées standards de p1 et p2). Dans ce cas, les descripteurs se partagent le mode d'accès et l'offset.
Par ailleurs, deux entrées d'une même tdf peuvent pointer vers une même entrée de tfo (cas de p2 qui redirige sa sortie avec une duplication de descripteur (dup)).
Deux entrées d'une même tdf peuvent pointer vers un même fichier via deux entrée de tfo (cas de p3 dont la sortie et la sortie erreur sont dirigées sur le même fichier).
Enfin, la table tim peut contenir des inodes non libres, mais pas accessibles par une tdf ou par la tfo. C'est le cas pour les appels systèmes accédant aux fichiers sans ouverture (e.g. stat, chmod, chown, chgrp, link, unlink, etc ...).

Les appels systèmes manipulant les différentes parties de ces structures (y compris les fichiers sur disque eux-mêmes) peuvent être classés selon la table qu'ils manipulent.
Pour l'existence de tdf, ce sont les appels fork et exit. L'appel fork crée la tdf (clônage de celle du processus père; les compteurs de références des entrées de tfo pointées par la tdf d'origine sont incrémentés). L'appel exit la supprime (après avoir fermé tous les descripteurs).
Pour le lien entre tdf, tfo et tim, ce sont les appels open et close. L'appel open alloue un descripteur libre en tdf, une entrée libre en tfo et relie le tout à une entrée de tim contenant l'inode du fichier à ouvrir (allouée ou occupée par cet inode). L'appel close libère un descripteur en défaisant le lien de tdf à tfo (une libération en cascade des ressources pointées peut intervenir si les compteurs de références deviennent nuls).
Pour la manipulation de tfo (champ offset principalement), on dispose de l'appel lseek.
Pour consulter l'inode (tim), on emploie l'appel fstat (fichier ouvert) ou stat (fichier non ouvert; l'inode est chargé dans le cache par stat). Divers appels permettent de changer certains champs de l'inode (link et unlink: compteur de liens; chmod: droits; chown et chgrp: propriétaires; les champs taille, dates et table des blocs sont mis à jour par les accès aux blocs de données du fichier).
Pour accéder aux blocs de données du fichier (i.e. son contenu), on dispose des appels read et write.
Des appels de la librairie standard permettent d'effectuer des accès formatés (le format des données contenues dans le fichier est connu: caractère: fgetc, fputc; ligne: fgets, fputs; entier, flottant, etc ...: fscanf, fprintf).
Des appels POSIX sont disponibles pour consulter les répertoires.
Voici un récapitulatif (non exhaustif) des appels systèmes de gestion des fichiers (le terme bloc désigne un bloc de données d'un fichier; les crochets encadrent un accès potentiel; la colonne ouverture indique que l'appel concerne (oui) ou pas (non) un descripteur de tdf; la colonne POSIX/C distingue les appels POSIX de ceux de la librairie standard de C):

  nom             ouverture    POSIX/C      structure accédée
  open            oui          p            tdf+tfo+tim
  fopen           oui          C            tdf+tfo+tim
  creat           oui          p            tdf+tfo+tim
  close           oui          p            tdf[+tfo[+tim[+blocs]]]
  fclose          oui          C            tdf[+tfo[+tim[+blocs]]]
  read            oui          p            tdf+tfo+tim+blocs
  fread           oui          C            tdf+tfo+tim+blocs
  write           oui          p            tdf+tfo+tim+blocs
  fwrite          oui          C            tdf+tfo+tim+blocs
  lseek           oui          p            tdf+tfo
  fseek           oui          C            tdf+tfo
  dup             oui          p            tdf+tfo
  dup2            oui          p            tdf+tfo
  fstat (*)       oui          p            tdf+tfo+tim
  stat (**)       non          p            tim
  link            non          p            tim
  unlink          non          p            tim
  rename          non          p            tim
  fchmod          oui          p            tdf+tfo+tim
  chmod           non          p            tim
  fchown          oui          p            tdf+tfo+tim
  chown           non          p            tim
  opendir         oui          p            tdf+tfo+tim
  closedir        oui          p            tdf+tfo+tim
  readdir         oui          p            tdf+tfo+tim+bloc
  lstat           non          p            tim
  symlink         non          p            tim+blocs
  readlink        non          p            tim+blocs
  fgetc           oui          C            tdf+tfo+tim+bloc
  fputc           oui          C            tdf+tfo+tim+bloc
  fgets           oui          C            tdf+tfo+tim+blocs
  fputs           oui          C            tdf+tfo+tim+blocs
  fscanf          oui          C            tdf+tfo+tim+blocs
  fprintf         oui          C            tdf+tfo+tim+blocs

  (*): fstat sur un lien symbolique accède à tdf+tfo+tim+blocs
  (**): stat sur un lien symbolique accède à tim+blocs
  

L'ouverture d'un fichier s'effectue avec l'appel POSIX open.

int open(const char *ref, int mode[, mode_t droits]);

La fonction retourne le descripteur alloué par le noyau (numéro de l'entrée allouée dans tdf). Le premier argument est le nom de fichier à ouvrir (référence relative ou absolue). Le second argument est le mode d'ouverture, présenté sous la forme de constantes dont on fait l'union (activation d'une opération à l'ouverture, e.g.

O_WRONLY|O_APPEND

). Le troisième argument n'est fourni qu'en création. Il fixe les droits d'accès du fichier pour toutes les catégories d'utilisateurs (S_IRUSR, S_IWUSR, S_IXUSR, S_IRWXU pour le propriétaire, mêmes noms suffixés par GRP et G pour le groupe et par OTH et O pour les autres).

  mode                           ouverture            inexistant        existant
  O_RDONLY                       lecture seule        erreur            
  O_WRONLY                       écriture seule       erreur
  O_WRONLY|O_APPEND              écriture en queue    erreur
  O_RDWR                         lecture+écriture     erreur 
  O_WRONLY|O_CREAT|O_TRUNC       écriture seule       création          réinitialisé
  O_WRONLY|O_CREAT|O_EXCL        écriture seule       création          erreur

Voici le travail effectué par le noyau à l'ouverture d'un fichier:

  Allocation d'un descripteur dans tdf,
  Allocation d'une entrée dans tfo, compteur à 0, mode,
    offset en début de fichier (sauf O_APPEND),
  Convertir la référence en son numéro d'inode
    (algorithme namei qui parcourt l'arborescence),
  Chercher l'inode dans tim,
  S'il y est et est libre,
    l'allouer et initialiser le compteur de référence à 1,
  S'il y est et n'est pas libre,
    incrémenter le compteur de référence,
  S'il n'y est pas,
    allouer une entrée libre de tim, y charger l'inode
    et initialiser le compteur de référence à 1,
  Retourner le numéro du descripteur alloué.

La fermeture d'un fichier s'effectue avec l'appel POSIX close.

int close(int desc);

Voici le travail effectué par le noyau à la fermeture d'un fichier:

  Libération du descripteur desc de tdf,
  Décrémenter le compteur de l'entrée de tfo pointée,
  S'il devient nul,
    décrémenter le compteur de l'entrée de tim pointée,
    S'il devient nul et si le compteur de liens de l'inode est nul,
       Supprimer le fichier
       (libérer les blocs de données et l'inode).

Les accès aux contenus des fichiers passent par un cache des blocs de disque dont la gestion est similaire à celle de la table tim (la figure représentant le chaînage des entrées du cache décrit aussi bien la table tim que le cache des blocs de disque). Chaque entrée du cache comprend, en plus des pointeurs de chaînage, une en-tête avec le numéro du bloc caché et une copie du bloc lui-même.
La figure ci-dessous montre le lien entre la tim et le cache de blocs de disque. Voici l'algorithme de recherche d'un bloc B d'un fichier (le numéro B du bloc est obtenu dans la tbf de l'inode I du fichier):

Soit P la partition du cache où B doit figurer. 
Parcourir P à la recherche de B.
Si B n'est pas trouvé dans P
   allouer la première entrée libre du cache (soit E),
   (cette entrée contenait le bloc B', de la partition P')
   si B' est modifié, le copier sur disque,
   charger le bloc B dans E,
   retirer E de la partition P' (le pointeur arrière est utile),
   ajouter E en tête de la partition P,
   retirer E de la liste libre.
Sinon (B est trouvé en E)
   Si E est libre (pointeurs de liste libre non nuls)
      retirer E de la liste libre (le pointeur arrière est utile),
   Sinon (B est accédé par un processus)
      attendre que B soit libéré par le processus qui y accède.

La lecture dans un fichier se fait avec l'appel POSIX read.

ssize_t read(int desc, void *tampon, size_t nb);

L'appel lit au plus nb octets à partir de la position courante dans le fichier (champ offset de la table tfo). Les octets sont transférés du cache des blocs de disque dans le tampon pointé (qui doit exister et avoir une taille suffisante). La fonction retourne le nombre d'octets effectivement lus (éventuellement 0).
Voici l'algorithme de lecture:

Accès à tdf[desc]
Accès à tfo
Vérification du mode d'ouverture
Accès à tim
Vérification des droits
Boucle de lecture (tant que moins de nb octets ont été lus)
  Convertir l'offset en un numéro d'entrée dans tbf (0 à 12)
  Accès à tbf dans tim
  Soit B le numéro du bloc à lire
  (déterminer B peut nécessiter de lire des blocs d'indirection)
  Chercher B dans le cache (chargement du disque si B n'est pas dans le cache)
  Jusqu'à concurrence de nb octets ou de la fin de bloc, copier du cache dans *tampon
  Avancer l'offset
  (si nb octets ont été lus ou si l'offset est égal à la taille, sortir)
Retourner le nombre d'octets lus

L'écriture dans un fichier se fait avec l'appel POSIX write.

ssize_t write(int desc, void *tampon, size_t nb);

L'appel écrit nb octets du tampon dans le cache (l'écriture sur disque est différée. Elle n'intervient que quand l'entrée du cache est réallouée pour un autre bloc). L'écriture se fait à la suite de l'offset dans le fichier. L'algorithme d'écriture est similaire à celui de lecture.

On peut dupliquer un descripteur dans la tdf avec l'appel POSIX dup. La copie prend place dans une entrée libre de la tdf (a priori la première. Ainsi, en fermant le descripteur 0 (STDIN_FILENO) et en dupliquant le descrpiteur d, on redirige l'entrée standard sur le fichier désigné par d). L'appel POSIX dup2 ne suppose pas d'ordre sur les descripteurs (par exemple que STDIN_FILENO=0).

int dup(int desc);
/*copie le descripteur desc dans la première entrée libre de tdf*/

int dup2(int d_source, int d_copie);
/*duplique d_source dans d_copie*/
/*il y a fermeture de d_copie au préalable si nécessaire*/

On peut déplacer l'offset dans un fichier avec l'appel POSIX fseek. Le déplacement est virtuel (aucun accès disque n'est effectué. C'est l'offset qui est modifié dans tfo).

off_t lseek(int desc, off_t distance, int origine);

L'offset est modifié avec le déplacement distance. L'origine du déplacement est défini par l'argument origine. S'il vaut SEEK_SET, l'origine est le début du fichier (positionnement absolu en distance). S'il vaut SEEK_CUR, l'origine est l'offset (on peut se déplacer vers l'arrière avec une distance négative). S'il vaut SEEK_END, l'origine est la fin de fichier (on peut se déplacer vers l'avant, ce qui étend artificiellement le fichier: les éventuels nouveaux blocs ne sont créés que s'ils sont accédés).

On peut consulter un inode avec l'appel POSIX fstat.

int fstat(int desc, struct stat *pstat);

L'inode est copié dans la structure stat pointée par pstat. La structure stat est ainsi définie:

struct stat {
 dev_t st_dev;           /*partition où se trouve le fichier*/
 ino_t st_ino;           /*numéro d'inode*/
 mode_t st_mode;         /*type et droits*/
 nlink_t st_nlink;       /*nombre de liens*/
 uid_t st_uid;           /*propriétaire*/
 gid_t st_gid;           /*groupe propriétaire*/
 off_t st_size           /*taille (ou (majeur, mineur))*/
 time_t st_atime;        /*dernier accès*/
 time_t st_mtime;        /*dernière modification du fichier*/
 time_t st_ctime;        /*dernière modification de l'inode*/
}

On peut exploiter le champ st_mode pour déterminer le type d'un fichier avec les macro fonctions suivantes:

S_ISREG(pstat->st_mode)  /*fichier régulier*/
S_ISDIR(pstat->st_mode)  /*fichier répertoire*/

Pour tester les droits d'accès, on emploie un masquage approprié de st_mode:

/*pour tester si accessible en lecture et écriture propriétaire:*/
if (((pstat->st_mode) & S_IRUSR) && ((pstat->st_mode) & S_IWUSR)) {...}

L'appel POSIX stat permet d'effectuer la même consultation sans ouvrir le fichier:

int stat(const char *ref, struct stat *pstat);

Voici quelques appels POSIX supplémentaires pour manipuler un inode:

int link(const char *ancien, const char *nouveau);
/*incrémente le compteur de liens de ancien*/
/*et ajoute la référence nouveau dans le répertoire courant*/
/*nouveau et ancien ont le même numéro d'inode*/

int unlink(const char *ref);
/*décrémente le compteur de référence du fichier *ref*/
/*supprime la référence *ref du répertoire courant*/
/*si le fichier n'est plus référencé, il est supprimé*/
/*(ses blocs sont libérés)*/

int chmod(const char *ref, mode_t mode);
int fchmod(int desc, mode_t mode);
/*nouveaux droits pour le fichier*/

int chown(const char *ref, uid_t id_prop, gid_t id_grp);
int fchown(int desc, uid_t id_prop, gid_t id_grp);
/*nouveaux propriétaires*/

Les répertoires sont des fichiers dont le contenu suit un format particulier décrit par la structure dirent qui contient au moins:

struct dirent {
  ...
  char d_name[NAME_MAX]; /*nom de fichier*/
  ...
  ino_t d_ino; /*numéro d'inode*/
  ...
}

On peut chercher un numéro d'inode ou un nom de fichier dans un répertoire avec les appels POSIX suivants (la structure DIR est une structure opaque du système. Elle joue le rôle de descripteur, c'est-à-dire de pointeur sur tdf):

DIR *opendir(const char *ref); /*ouvrir le répertoire*/

struct dirent *readdir(DIR *pdir); /*lire l'entrée suivante et avancer*/
/*la structure retournée en résultat contient l'entrée lue*/
/*NULL en fin de fichier*/

int closedir(DIR *pdir); /*fermer le répertoire*/

Les appels suivants sont définis dans la librairie standard (la structure FILE est une structure opaque du système. Elle joue le rôle de descripteur, c'est-à-dire de pointeur sur tdf):

FILE *fopen(const char *ref, const char *mode);
/*mode: "r" (O_RDONLY), "w" (O_WRONLY|O_CREAT|O_TRUNC), "a" (O_WRONLY|O_CREAT|O_APPEND)*/
/*"r+" (O_RDWR), "w+" (O_RDWR|O_CREAT|O_TRUNC), "a+" (O_RDWR|O_CREAT|O_APPEND)*/

int fclose(FILE *f);

int fread(void *tampon, size_t taille_e, size_t nb_e, FILE *f);
/*lecture de nb_e éléments de taille taille_e octets*/

int fwrite(void *tampon, size_t taille_e, size_t nb_e, FILE *f);
/*écriture de nb_e éléments de taille taille_e octets*/

int fseek(FILE *f, long int offset, int origine);
/*origine=SEEK_SET, SEEK_CUR, SEEK_END*/

Les appels suivants sont définis dans la librairie standard pour effectuer des accès formatés:

/*fichiers de caractères*/
int fgetc(FILE *f);
/*retourne un entier, négatif en cas d'erreur*/

int fputc(int c, FILE *f);

/*fichiers de lignes de caractères*/
char *fgets(char *tampon, int nb, FILE *f);
/*lecture d'une ligne d'au plus nb-1 octets*/
/*la ligne lue est terminée par un \0*/
/*le résultat pointe sur la ligne lue*/
/*retourne NULL en cas d'erreur*/

int fputs(char *tampon, FILE *f);
/*écrit une chaîne terminée par \0*/
/*le \0 n'est pas écrit*/

/*fichiers de données formatées*/
int fscanf(FILE *f, const char *format, ...);
int fprintf(FILE *f, const char *format, ...);

Les liens sont internes à une partition. Pour établir un lien entre deux fichiers de deux partitions différentes, on emploie un lien symbolique. Le lien symbolique est un fichier dont le contenu est la référence liée (chemin absolu ou relatif -relatif au répertoire contenant le lien-).
Des appels systèmes permettent de manipuler le fichier lien (les appels standards traversent le lien symbolique et accèdent directement au fichier lié. C'est le cas par exemple de stat qui retourne l'inode du lié en non pas l'inode du lien).

int lstat(const char *ref, struct stat *pstat);
/*lit l'inode du lien*/

ssize_t readlink(const char *ref, char *tampon, size_t taille);
/*l'argument taille donne le nombre d'octets libres du tampon*/
/*le tampon contient le chemin vers le lié, non terminé par \0*/

int symlink(const char *lié, const char *lien);
/*crée un lien symbolique liant lien à lié*/

La figure ci-dessous récapitule les structures accédées par les divers appels systèmes de gestion des fichiers.