Système de fichiers et accès aux devices

Système de fichiers distribué

1. Objectifs

Le système de fichier est une partie importante du système d'exploitation, puisqu'il contient toutes les informations non volatiles, c'est à dire les informations qui doivent être conservées lorsqu'on éteint la machine entre deus sessions de travail, et sont donc enregistrées sur un périphériques de stockage externe (disque magnétique, clé USB, etc).

En règle générale, le système de fichiers est (beaucoup) plus gros que la capacité totale de la mémoire vive. Au cours d'une session de travail particulière, seule une (toute petite) partie des informations stockées dans le système de fichiers ont effectivement besoin d'être amenées en mémoire. Tous les systèmes d'exploitation définissent donc un cache des fichiers, qui est une représentation en mémoire, d'une partie du système de fichiers stocké sur disque.

Ce cache des fichiers est un bon exemple de structure de donnée du système d'exploitation susceptible de créer un goulot d'étranglement. Cette structure est partagée, puisqu'elle peut être accédée par n'importe quel thread de n'importe quel process souhaitant accéder à un fichier, et elle est potentiellement trop volumineuse pour être stockée dans un seul cluster. Elle doit donc être distribuée sur plusieurs clusters.

Dans ce TP, on présente les techniques de distribution utilisées dans Almos-mkh pour minimiser la contention lors des accès concurrents au système de fichier.

2. Principes Généraux

Le périphérique de stockage externe contenant le système de fichier est toujours organisé comme un tableau de secteurs physiques. Chaque secteur peut contenir un bloc de 512 octets, et est identifié par un numéro de secteur, appelé LBA (Logic Block Address). Bien que le plus petit élément de stockage adressable soit le secteur, presque tous les systèmes de fichiers définissent une unité d'allocation plus grosse, appelée cluster. Généralement, le cluster a une capacité égale à une page, c'est à dire 4 Koctets (8 secteurs consécutifs). Le système de fichier utilise donc le périphériques comme un tableau de clusters. Un fichier occupe toujours un nombre entier de clusters, et un même cluster ne peut pas être partagé par deux fichiers.

Dans les systèmes UNIX ou Microsoft, le système de fichier possède une structure hiérarchique arborescente, puisque certains fichiers sont des répertoires, qui contiennent eux-mêmes des liens vers d'autres fichiers ou répertoires. N'importe quel fichier (ou répertoire) dans le système de fichiers peut être désigné sans ambiguité par un cheminom, décrivant le chemin allant du répertoire racine du système de fichier à un fichier particulier.

Tout système de fichier doit donc stocker trois types d'information

1. certains clusters du disque sont utilisés pour stocker les fichiers terminaux, autres que les répertoires.
2. d'autres clusters sont utilisés pour stocker les fichiers répertoires, qui définissent la structure arborescente du système de fichier.
3. d'autres encore sont utilisés pour stocker la FAT (File Allocation Table) qui définit quels clusters ont été alloués à chaque fichier.

Il existe évidemment de nombreux types de système de fichier, qui sont différentes implémentations de la structure arborescente générique définie ci-dessus. C'est le format utilisé pour représenter les répertoires et la FAT qui différencient les différents types de systèmes de fichier. Pour pouvoir s'adapter facilement à plusieurs types de systèmes de fichiers, les systèmes UNIX définissent généralement une API indépendante du type de système de fichier appelée VFS (Virtual File Système).

A ce jour, l'API VFS de Almos-mkh a été portée sur trois systèmes de fichiers : FATFS, DEVFS, RAMFS. Dans ce TP, on utilisera un disque contenant un système de fichier FATFS, respectant le format Microsoft FAT32.

3. Implémentation du Cache des Fichiers

Le cache des fichiers est le nom générique de la représentation interne - en mémoire - du système de fichiers. Almos-mkh utilise deux techniques pour réduire l'encombrement du cache de fichiers en mémoire par rapport à encombrement du systèmes de fichiers sur le disque:

• pour les fichiers répertoires, seulement un sous-ensemble des liens vers les fichiers fils contenus dans le répertoire est présent dans le cache: seuls les liens permettant d'atteindre un fichier présent en mémoire sont représentés. Un répertoire peut donc contenir 10 liens vers 10 fichiers fils sur le disque, alors que sa représentation en mémoire contient un seul fils, si les 9 autres liens pointent vers des fichiers qui n'ont pas eu besoin d'être chargés dans le cache.
• pour les fichiers terminaux, seuls les pages contenant des données accédées en lecture ou en écriture sont effectivement chargées dans le cache des fichier en mémoire. Un fichier occupant 1 Moctets sur le disque (256 pages) peut n'occuper que 4 Koctets en memoire (1 page), si une seule page est accédée.

3.1 Arbre des Inodes

La structure générale du système de fichier n'est pas un arbre, mais un DAG (Graphe orienté sans cycles), puisqu'il peut exister plusieurs cheminoms permettant d'atteindre un même fichier par plusieurs chemins partant de la racine. Malgré cela, on utilise le nom arbre des inodes pour désigner la structure représentant le sous ensemble des fichiers et répertoires présents à un instant donné dans le cache des fichiers. Cette structure est implémentée par un graphe bi-parti contenant deux types de noeuds:

• un noeud de type inode représente un fichier terminal ou un répertoire. Il est implémentée par la structure vfs_inode_t.
• un noeud de type dentry représente un lien entre un fichier répertoire et un autre fichier fils contenu dans le répertoire. Il est implémentée par la structure vfs_dentry_t.

L'arbre des inodes est une structure distribuée: Les structures vfs_inode_t représentant les fichiers sont distribuées le plus uniformément possible sur les différents clusters de l'architecture. Dans le cas cas d'un inode père représentant un répertoire, toutes les structures vfs_dentry_t décrivant les liens vers les inodes fils sont toujours allouées dans le cluster contenant l'inode père. Mais l'inode père et l'inode fils sont généralement allouées dans deux clusters différents. Deux inodes fils d'un même inode père sont également rangés dans des clusters différents. Par conséquent, l'arbre des inodes utilise principalement des pointeurs étendus.

3.2 Mapper d'un fichier

A chaque noeud de type inode de l'arbre des inodes est attaché une structure annexe, appelée mapper contenant une copie partielle, en mémoire, du contenu du fichier représenté par cet inode. Cette structure mapper_t est implémentée comme un radix tree de profondeur 3. Ce radix tree est indexé par le numéro de la page dans le fichier, vu comme un tableau de pages de 4 octets, et chaque entrée du radix tree contient un pointeur sur une page de 4Koctets en mémoire.

• pour les fichiers terminaux, seules les pages qui ont été accédées (en lectures ou en écriture) sont effectivement copiées dans le mapper.
• pour les fichiers répertoires, tout le contenu du fichier est copié dans le mapper, mais la majorité des répertoires ne nécessitent pas plus d'une page.

La structure mapper_t est entièrement localisée dans le cluster contenant la structure vfs_inode_t à laquelle il est attaché.

3.3 File descriptor

Chaque fois qu'un processus ouvre un fichier avec un appel système open(), le noyau crée un descripteur de fichier ouvert, et renvoie au processus client un index identifiant ce descripteur de fichier. Ce descripteur de fichier doit être utilisé par le processus pour accéder au fichier, car de descripteur contient en particulier un offset (pointeur) définissant quelle zone du fichier doit être accédée.

Ce descripteur de fichier ouvert est implémenté par le structure vifs_file_t.

Il peut exister à un instant donné plusieurs descripteurs de fichiers ouverts pour un même fichier X, mais toutes les structures vfs_file_t concernant le fichier X sont allouées dans le cluster contenant l'inode représentant le fichier X.

3.4 Conclusion

Pour minimiser la contention, les structures vfs_inode_t sont distribuées le plus uniformément possible sur tous les clusters. Et les structures annexes attachées à un fichier X particulier: la structure mapper_t contenant les données du fichier, les structures vfs_dentry_t attachées à un fichier répertoire, et les structure vfs_file_t permettant l'accès au fichier, sont toutes allouées dans le cluster contenant la structure vfs_inode_t représentant le fichier X. Il s'agit donc d'une politique de distribution possédant la granularité fichier, qui minimise la contention dans le cas ou un grand nombre de threads accèdent parallèle à un grand nombre de fichiers différents, mais qui ne sera pas efficace dans le cas où un grand nombre de threads accèdent en parallèle à un même fichier.

4. Questions

Pour répondre aux questions ci-dessous, il faut plonger dans le code du VFS dans les fichiers ​almos-mkh/kernel/fs/vfs.c et ​almos-mkh/kernel/fs/vfs.h.

Vous pouvez également consulter le code du mapper dans les fichiers ​almos-mkh/kernel/mm/mapper.c et ​almos-mkh/kernel/mm/mapper.h.

Le code du radix_tree générique est défini dans les fichiers ​almos-mkh/kernel/libk/grdxt.c et ​almos-mkh/kernel/libk.grdxt.h.

1. L'arbre de inodes contient des pointeurs descendant permettant d'atteindre les inodes des fichiers fils à partir de l'inode du fichier répertoire père. Pourquoi l'appel système open() nécessite-t-il un parcours descendant, de la racine vers un fichier terminal? Quelle fonction du VFS implémente-t-elle ce parcours ? Quels sont ses arguments d'entrée? Que retourne-t-elle?
2. L'arbre de inodes contient également des pointeurs ascendant permettant d'atteindre l'inode d'un fichier père à partir de l'inode d'un fichier fils. Pourquoi l'appel système getcwd() nécessite-t-il un parcours ascendant, d'un fichier terminal vers la racine, sachant que le descripteur de processus contient un pointeur étendu sur l'inode représentant le répertoire courant? Quelle fonction du VFS implémente-t-elle ce parcours? Quels sont ses arguments d'entrée? Que retourne-t-elle?
3. Comment est représenté, dans la structure vfs_inode_t représentant un fichier répertoire père, l'ensemble des liens vers les structures de données vfs_dentry_t représentant les liens vers les fichiers fils contenus dans ce répertoire ?
4. Un fichier terminal pouvant être accédé par plusieurs chemins, un fichier terminal fils peut avoir plusieurs répertoires pères. Comment est représenté, dans la structure vfs_inode_t l'ensemble des liens pères ?
5. En cas de miss sur le cache des fichiers, Il faut parfois créer, dans l'arbre des inodes, un nouveau couple (dentry/inode) pour introduire un nouveau fichier fils dans un répertoire père existant. Le VFS utilise utilise pour cela la fonction vfs_add_child_in_parent(). Quelles actions sont réalisées par cette fonction ? Dans quel cluster est créée la nouvelle structure vfs_dentry_t représentant la nouvelle entrée dans le répertoire père ? En analysant le code de la fonction appelante, par exemple vfs_lookup(), dites comment est choisi le cluster dans lequel est allouée la mémoire pour la nouvelle structure vifs_inode_t représentant le fichier fils ?
6. L'arbre des inodes est une structure partagée, qui peut être accédée de façon concurrente par un grand nombre de threads. Toute modification de cette structure nécessité évidemment un accès exclusif interdisant tout parcours de l'arbre par un autre thread, pendant la modification de la structure. Quel mécanisme de protection est utilisé pour garantir un accès exclusif en cas de modification, tout en permettant des accès parallèles en lecture ? Quelle est la faiblesse principale de ce mécanisme ?
7. La structure mapper_t attachée à chaque inode (et donc à chaque fichier) peut être considérée comme un cache extensible dont la capacité augmente dynamiquement en fonction des besoins. Quelle fonction permet elle à un thread s'exécutant dans n'importe quel cluster C d'accéder n'importe quelle page de n'importe quel fichier située dans n'importe quel autre cluster C' ? Quelle fonction du mapper permet-elle de traiter un miss (c'est à dire un accès à une page du fichier qui n'est pas encore chargée dans le mapper) ? Décrivez précisément ce que font ces deux fonctions.
8. En cas de miss sur un mapper, dans quel cas la page manquante doit-t-elle être initialisée dans le mapper à partir des informations stockées dans le système de fichiers (sur le disque) ? Dans quel cas l'accès au disque est-il inutile ? Que peut-on en conclure que la politique d'écriture des caches mapper (write-through / write-back) ?
9. Un même fichier, et donc un même mapper, peut être accédé de façon concurrente par plusieurs threads. Quel mécanisme est utilisé pour permettre ces accès concurrents tout en maximisant le parallélisme ?

Entrées/sorties et accès aux périphériques

1. Objectifs

Les périphériques sont des ressources partagées par tous les threads en cours d'exécution : n'importe quel thread, de n'importe quel processus, s'exécutant dans n'importe quel cluster, peut effectuer un appel système nécessitant un accès au disque.

Dans une architecture manycore capable d'exécuter plusieurs centaines de threads en parallèle, le sous-système d'entrées/sorties, et plus précisément les structures de données du noyau permettant l'accès aux périphériques peuvent facilement devenir - après l'accès à la mémoire partagée - le principal goulot d'étranglement de la machine.

Le but de ce TP est de présenter les techniques de distribution utilisées par Almos-mkh pour minimiser les risques de contention lors de l'accès au sous-système d'entrées/sorties.

2. Principes Généraux

Pour chaque type de périphérique (contrôleur de disque, contrôleur réseau, contrôleur graphique, terminal alpha-numérique, etc.), il existe un - très - grand nombre de modèles de périphériques fournissant globalement le même service, mais ayant chacun leur propres commandes, leurs propre jeu de registres adressables, et leur propre mécanisme de signalisation.

Pour faciliter l'intégration des périphériques, et pour éviter de devoir modifier et/ou recompiler le code du noyau lors de l'ajout d'un nouveau périphérique, tous les systèmes d'exploitation définissent une représentation abstraite de chaque type de périphérique, permettant de masquer les différences entre différentes implémentations matérielles dans un pilote logiciel (appelé driver), généralement fourni par le fabricant.

Par ailleurs, pour améliorer la bande passante (c'est à dire le nombre d'opérations d'entrées sortie par seconde), les contrôleurs de périphériques sont souvent multi-canaux : un même contrôleur contient plusieurs jeux de registres indépendants, permettant à l'OS d'exécuter plusieurs opérations d'entrée/sortie en parallèle pour le compte de plusieurs clients. C'est presque toujours le cas des contrôleur de terminaux, c'est le cas des contrôleurs de disque respectant la norme AHCI, et c'est de plus en plus souvent le cas des contrôleurs réseau.

3. Implémentation du sous-système d'entrées-sorties

La principale abstraction définie par almos-mkh est la structure chdev, qui représente un canal d'un périphérique. Pour les terminaux texte, et pour les contrôleurs réseau, Almosmkh définit même un chdev par canal et par direction (direction RX pour la réception de donnée depuis l'extérieur / direction TX pour la transmission de données vers l'extérieur).

La structure chdev_t et les fonctions d'accès sont définis dans les fichiers ​chdev.h et ​chdev.c.

3.1) Typage des périphériques

Almost-mkh identifie un périphérique matériel par un double index (func,impl). L'index func défnit la fonctionnalité. Pour une fonctionnalité donnée, l'index impl définit une réalisation matérielle particulière.

• Chaque valeur de func définit en pratique un ensemble de fonctions (appelé API noyau) utilisables par le noyau et correspondant aux différents services fournis par ce type de périphérique, indépendamment de son implémentation. Il y a donc une API différente pour chaque type fonctionnel.
• Chaque valeur de impl définit une implémentation matérielle particulière, donc un pilote particulier, pour une même fonctionnalité définie par func.

3.2) Interface noyau / pilotes

Ll'interface entre les pilotes et le code noyau qui implémente - pour chaque type fonctionnel - l'API noyau, est standardisée et contient trois fonctions:

1. la fonction func_driver_init() est appelée par le noyau pour initialiser les registres du périphériques et les éventuelles structures de données en mémoire utilisées par le driver.
2. la fonction func_drived_cmd() permet au noyau de donner des ordres au périphérique sans connaître son implémentation.
3. la fonction func_driver_isr() est exécutée lorsque le périphérique signale une fin de traitement, en activant une interruption matérielle. ISR signifie Interrupt Service Routine.

3.3 File d'attente et thread serveur

Par définition un canal de périphérique ne peut traiter qu'une seule opération d'entrée/sortie à la fois. Il faut donc séquencialiser les requêtes concurrentes visant un même chdev. Almos-mkh attache donc à chaque chdev une file d'attente permettant à chaque thread client d'enregistrer sa requête puis de se bloquer, et de relâcher le processeur, en attendant que sa requête soit traitée. Ce n'est généralement pas le thread client qui exécute l'opération d'entrée/sortie. C'est un autre thread server, de type DEV, attaché au chdev, qui est chargé d'exécuter séquenciellement les requêtes d'entrée/sortie enregistrées dans la file d'attente, et de réveiller chaque thread client, quand le transfert de données demandé par le client est terminé.

En pratique, la file d'attente est implémentée comme une XLIST trans-clusters, enracinée dans la structure chdev_t, et permettant de chaîner entre elles les threads clients. Les paramètres de la requête (type de la requête, adresse du tampon mémoire source ou destination, nombre d'octets ou de blocs à transférer, etc) sont enregistrés dans le descripteur du thread client.

Lorsque la file d'attente est vide, le thread server se bloque et relâche le processeur. La politique d'ordonnancement des threads prévoit qu'un thread de type DEV a une priorité plus élevée qu'un thread de type USR, mais elle prévoit également qu'un thread DEV n'est pas exécutable lorsque la file d'attente est vide.

3.4) Placement des chdev

Les périphériques externes sont généralement connectés sur un bus externe (type PCI-express ou Hypertransport) qui est connecté au bus sytème (ou au micro-réseau dans le cas d'une architecture manycore), par un bridge. Il faut donc nécessairement passer par ce bridge, localisé dans un cluster particulier (appelé cluster_io) pour accéder aux registres adressables de tous les périphériques.

Pour minimiser les risques de contention, Almos-mkh ne place pas les descripteurs de chdev (et les threads server associés) dans le cluster_io, mais il les distribue, le plus uniformément possible, sur tous les clusters de l'architecture.

Par conséquent, dans le cas général, une opération d'entrée/sortie met en jeu trois clusters:

1. le cluster client, qui contient le descripteur du thread client (et donc les paramètres de la commande),
2. le cluster device, qui contient le périphérique (et donc le segment des registres adressages),
3. le cluster server, qui contient le descripteur de chdev et le thread server,

3.5) structure du descripteur de chdev

La structure chdev_t contient (entre autres) les informations suivantes:

• func : type fonctionnel
• impl : type d'implementation
• channel : index du canal
• is_rx : direction (RX/TX)
• base : adresse de base du segment contenant les registres
• cmd : pointeur sur la fonction func_driver_cmd()
• isr : pointeur sur la fonction func_driver_isr()
• server : pointeur local sur le thread server associé
• wait_root : racine de la liste the threads clients en attente de traitement

4. Questions

Pour répondre aux questions ci-dessous, vous devez commencer par lire la documentation décrivant le sous-système d'entrées/sorties, que vous trouverez ​ici.

L'API du contrôleur de disque générique (IOC pour Input/Outptut Controler) est définie ​ici

L'API du terminal texte générique (TXT pour Terminal teXTe) est définie ici ​ici

Trois contrôleurs de disque (et donc trois pilotes) ont été intégrés dans Almos-mkh : IOC_BDV, IOC_HBA, IOC_RDK. Le code du pilote IOC_BDV utilisé dans TSAR est défini dans les fichiers ​soclib_bdv.h et ​soclib_bdv.c.

Deux contrôleurs de terminaux texte (et donc deux pilotes) ont été intégrés dans Almos-mkh : TXT_TTY, TXT_MTY, Le code du pilote TXT_TTY utilisé dans TSAR est défini dans les fichiers ​soclib_tty.h et ​soclib_tty.c.

1. quels sont les 5 classes de périphériques (c'est à dire les 5 types fonctionnels) actuellement supportées par Almos-mkh ?
2. Les descripteurs de device (structure chdev_t) contenant toutes les informations permettant l'accès à un périphérique sont distribués de façon régulière dans les clusters, mais cette distribution dépend évidemment du nombre de clusters. Comment le noyau localise-t-il le cluster contenant un chdev particulier ? Pourquoi a-t-on préféré avoir un descripteur par canal plutôt qu'un descripteur par périphérique ?
3. Quels sont les trois fonctions qui doivent être définies par tout pilote de périphérique, quel que soit son type fonctionnel, pour être utilisés dans Almos-mkh ? Que fait chacune de ces trois fonctions ?
4. La plupart des opérations d'entrée/sortie sont des transferts de données qui utilisent des arguments (type de l'opération demandée, adresse du tampon mémoire source ou destination, nombre d'octets à transférer, etc.). Comment le noyau transmet-il ces arguments au pilote ? Comment le pilote signale-t-il au noyau une éventuelle erreur ((adresse mémoire illégale par exemple) ?
5. Dans le cas le plus général, une opération d'entrée/sortie fait intervenir deux threads (client et serveur) et trois clusters (client, serveur, device). Décrivez le scénario d'un accès au disque pour traiter un miss sur cache de fichier, détecté par un thread client. Dites ce que font les deux threads logiciels, et l'automate du contrôleur de disque, depuis l'appel de la fonction dev_ioc_read() par le thread client, en précisant quels accès mémoire - locaux ou distants - effectuent ces trois acteurs. La réponse à cette question se trouve dans les fichiers ​chdev.c, ​dev_ioc.c, et ​soclib_bdv.c.
6. Pour signaler la terminaison d'une opération d'entrée/sortie, la plupart des périphériques utilisent une IRQ (Interrupt Request), qui entraîne l'exécution d'une ISR (Interrupt Service Routine) sur le coeur qui reçoit cette IRQ. En principe cette ISR peut être exécutée sur n'importe coeur de l'architecture. Quel est la politique d'Almos-mkh concernant le choix du coeur qui recevra l'interruption ? Quelle technique est utilisée par Almos-MKH pour acheminer l'interruption vers le coeur choisi ? Ce routage des interruptions est-il statique (c'est à dire défini une fois pour toutes, pour chaque interruption de chaque périphérique, lors de l'initialization du système) ou dynamique (c'est à dire défini pour chaque opération d'entrée/sortie, en fonction du placement du thread client) ?
7. Dans le cas du type TXT (terminal texte), les pilotes de périphériques doivent définir une quatrième fonction txt_driver_aux(), utilisée exclusivement pour lancer les opérations de type TXT_SYNC_WRITE. Cette fonction n'utilise pas la structure txt_command_t enregistrée dans le descripteur du thread client. Pour quelle raison Almos-mkh n'utilise-t-il pas la fonction txt_driver_cmd() et la méthode standard de passage des arguments ?
8. Quelle est la politique générale de Almos-mkh concernant l'allocation d'un terminal texte à un processus utilisateur ? Puisqu'un même terminal peut être partagé par plusieurs processus, deux processus peuvent exécuter de façon concurrente l'appel système getc() pour acquérir un character saisi au clavier. Comment Almos-mkh détermine-t-il vers quel processus doit être aiguillé le caractère entrant ?
9. L'appel système printf() permet à une application d'afficher une chaîne de caractères sur l'écran alpha-numérique du terminal texte qui lui est attaché. Donnez la suite complète des appels de fonctions entre la fonction printf(), exécutée en mode utilisateur par le thread client, et l'appel de la fonction txt_driver_cmd(), exécutée en mode kernel par le thread server. Pour chaque fonction intermédiaire dans cette chaîne d'appels, vous préciserez ce que fait cette fonction, et vous donnerez la signification des arguments.