Portail informatique Année 2018 – 2019

PAAM – Programmation avancée des architectures multicoeurs

Ce TP a comme premier but de vous faire prendre en main xv6, un noyau développé au MIT pour apprendre les systèmes d'exploitation. Le second but de ce TP est que vous comprenniez comment se déroule un appel système. Pour cela, vous mettez en place un nouveau mécanisme de synchronisation dans le noyau et explorez les structures de base de xv6. Commencez par cloner xv6 : git clone https://stark2.int-evry.fr/csc4508_xv6/ Ensuite, créez une branche locale nommée tp-syscall pour votre TP : $ git checkout -b tp-syscall master Ensuite, compilez le noyau : make Dans ce cours, il n'est possible de compiler et exécuter xv6 que dans un Linux. Si vous n'avez pas de Linux, installez-en un. Démarrez xv6 avec la commande suivante : make qemu

Cette commande démarre xv6 dans l'émulateur qemu. Lorsque xv6 démarre, il lance un petit shell permettant d'exécuter quelques commandes de base. Le code du shell se trouve dans le fichier sh.c. Si vous regardez les sources, vous pouvez retrouver l'architecture classique d'un système : la bibliothèque noyau s'appelle xv6 et est constituée des fichiers indiqués dans la variable OBJS que vous trouverez dans le Makefile. À chacune des commandes de base correspond un fichier source (cat.c, sh.c etc.). Vous pouvez trouver la liste de ces commandes, chacune préfixée par un _ dans la variable UPROGS (user commands) du Makefile.

Il est aussi possible de lancer xv6 en mode debug pour directement voir le fonctionnement bas niveau du noyau. Pour cela, il suffit de lancer make qemu-gdb Cette commande lance une fenêtre pour exécuter xv6 dans qemu. Le démarrage s'interrompt juste avant que la machine virtuelle démarre et permet à gdb de s'y connecter.

Dans un autre terminal, déplacez-vous dans les sources de xv6, puis lancez gdb. Si vous voyez un message d'erreur similaire à celui-ci :

warning: File "/home/gael/xv6/.gdbinit" auto-loading has been declined by your `auto-load safe-path' set to "$debugdir:$datadir/auto-load"

Alors, copiez-coller la ligne affichée juste après la ligne « To enable execution of this file add » dans votre fichier de configuration de gdb (~/.gdbinit) afin d'autoriser l'utilisation du script .gdbinit par gdb.

Une fois que gdb démarre correctement, saisissez b main (break main) pour interrompre l'exécution de xv6 dans sa fonction main puis lancez l'exécution de xv6 avec la commande c (continue). Si tout se passe bien, xv6 s'arrête au début de la fonction main.

Affichez le code de la fonction main avec list. Vous pouvez contempler le code qui initialise le système (le code source de cette fonction se trouve dans main.c. Techniquement, ce code est appelé à partir d'un trampoline en assembleur qui se trouve dans entry.S et qui s'occupe d'installer le minimum vital permettant de passer en C. Techniquement, lorsque grub charge le noyau, il saute directement sur le label entry, la partie assembleur initialise correctement le processeur (on vous expliquera comment plus tard) puis saute sur dans la fonction main.

Bienvenue dans un noyau de système d'exploitation !
Le but de cet exercice est d'ajouter de nouveaux appels systèmes à xv6. L'appel système que nous créons est relativement artificiel, mais reproduit de façon assez réaliste le fonctionnement des futex Linux que vous avez étudiés lors des précédents TPs. Pour commencer, nous créons une nouvelle commande nommée ftest permettant de tester nos nouveaux appels systèmes. Cette commande, comme toute commande, s'exécute en userland et donc, à terme, interagit avec le noyau. Pour le moment, notre commande effectue simplement un petit affichage. Pour cela, commencez par créer un fichier ftest.c dans lequel vous définissez une fonction main qui :
  • utilise printf pour afficher "starting". Attention, la fonction printf de xv6 prend un premier paramètre correspondant au flux (stdin, stderr, stdout) sur lequel on souhaite écrire. Comme nous souhaitons écrire sur la sortie standard, ce paramètre vaut 1 (rappelez-vous de vos cours CSC3102).
  • appelle exit() pour quitter la commande. En l'absence de exit(), le programme ne s'arrête pas naturellement comme sous Linux à la fin du main et exécute donc du code aléatoire qui mène, en général, à une erreur.
Les fonctions printf et exit sont définies dans le fichier d'entête user.h, et ce fichier nécessite avant l'inclusion de types.h.
Maintenant que nous avons notre première commande, nous pouvons la compiler et la tester. Pour cela, modifiez la variable UPROGS du Makefile pour que la commande ftest soit ajoutée à la liste des commandes. Ensuite, lancez xv6 (make qemu) et vérifiez que votre commande fonctionne en saisissant ftest dans le shell. Félicitations, vous savez créer de nouvelles commandes dans xv6 ! Maintenant que notre commande est fonctionnelle, nous pouvons ajouter nos deux appels systèmes. Il s'agit des appels :
  • int fwake(int slot, int val) : cette fonction considère que le noyau dispose de variables internes, appelées slots, et numérotées de 0 à 5. La fonction fwake affecte la valeur val au slotième slot, puis réveille les processus qui attendent que la variable slot change de valeur (voir fonction suivante) ;
  • int fwait(int slot, int val) : cette fonction endort le processus tant que le slot numéro slot ne vaut pas val.

Une utilisation typique de fwake/fwait est donnée ici :

#include "types.h" #include "user.h" int main() { if(fork() == 0) { printf(1, "%d - wait...\n", getpid()); fwait(1, 42); printf(1, "go go go!\n"); } else { sleep(500); printf(1, "%d - notify...\n", getpid()); fwake(1, 42); } exit(); }

Ce programme commence par créer un fils qui attend que le slot 1 passe à la valeur 42 (initialement, un slot vaut 0). Le père s'endort pendant 500 ticks (autour de 5s, le temps est géré de façon très approximative dans xv6) puis positionne le slot 1 à 42, ce qui a pour effet de réveiller le fils.

Commencer par copier-coller ce code dans votre fichier ftest.c.

Nous ajoutons maintenant les fonctions fwait et fwake dans user.h. Ces fonctions appellent simplement les fonctions idoines dans le noyau en effectuant un appel système. Pour cela :
  • donnez un numéro d'appel à nos appel système en ajoutant SYS_fwait (numéro 22) et SYS_fwake (numéro 23) dans syscall.h ;
  • ensuite, plutôt que d'écrire nous-même le code permettant d'appeler les fonctions 22 et 23 du noyau en utilisant du code assembleur, on vous demande d'ajouter SYSCALL(fwait) et SYSCALL(fwake) à la fin de usys.S. Cette macro crée alors des fonctions fwait et fwake qui appellent les fonctions systèmes 22 et 23 pour nous. Techniquement, pour fwait, cette macro crée une fonction fwait qui place le numéro de syscall (22) dans le registre %eax (rappelez-vous que les registres sont les variables internes d'un processeur) puis exécute l'instruction int 0x40 qui correspond à l'instruction trap dans xv6 ;
  • après, ajoutez la définition de ces fonctions au fichier user.h. Ce fichier contient les définitions C des fonctions assembleur se trouvant dans usys.S. Les signatures de ces fonctions sont données à la question précédente : int fwait(int slot, int val) et int fwake(int slot, int val).

La partie de test en userland permettant de tester les nouveaux appels systèmes est maintenant prête. Comme vous n'avez pas encore associé de code à ces appels systèmes dans le noyau, les appels doivent lamentablement échouer avec des messages "unknown sys call 22" et "unknown sys call 23". Vérifiez que c'est bien le cas en compilant, en lançant xv6 (make qemu) et en lançant votre commande ftest.

Cette question a pour but de comprendre pas à pas la suite d'événements engendrés par l'appel à fwait(1, 42) dans votre commande ftest. N'hésitez pas à demander à vos professeurs lorsqu'il y a des étapes que vous n'arrivez pas à comprendre.

Pour commencer, nous regardons ce qui se passe en userland. Pour ce faire, ouvrez le fichier ftest.asm. Ce fichier contient le code assembleur de votre commande ftest :

  • dans ce fichier, cherchez le code correspondant à fwait(1, 42). Vous devriez voir la mise en place des arguments (push $0x2a sachant que 0x2a est égal à 42, et push $1) suivi d'un appel à fwait (call 371). 371 est l'adresse à laquelle a été générée la fonction fwait. (Remarque : il est tout à fait possible que vous ayez une autre adresse que 371 dans votre code généré).
  • on peut ensuite suivre le flot d'exécution en cherchant ce 371 dans le fichier. Vous devriez voir le code assembleur de la fonction fwait généré à partir de usys.S. Ce code assembleur consiste en deux instructions :
    • mov $0x16, %eax : met le nombre 22 dans %eax, c'est le numéro d'appel système fwait,
    • int $0x40 : instruction trap qui fait basculer en mode système.

À partir de ce point, le processeur bascule en mode système et poursuit son exécution dans la fonction vector64 (notez que $0x40 = 64) qui a été associée à la trappe au démarrage de xv6. On peut donc suivre le flot d'exécution de la façon suivante :

  • la fonction vector64 se trouve le fichier vector.S. Techniquement, lors d'un int 0x40, le processeur bascule en mode système et exécute cette fonction ;
  • la fonction assembleur vector64 positionne des arguments qui, in fine, vont être reçus par la fonction C trap se trouvant dans le fichier trap.c. Il s'agit des valeurs 64 et 0 ;
  • le code se poursuit dans alltraps se trouvant dans le fichier trapasm.S. Cette fonction remplie un struct trapframe (défini dans x86.h) en sauvegardant les registres (la suite de pushl suivie du pushal), puis installe un trampoline avant de sauter dans la fonction C trap se trouvant dans trap.c ;
  • Pour comprendre comment le struct trapframe est construit, dessinez le contenu de la pile suite à tous ces push et comparez avec la structure.
  • la fonction trap reçoit un argument tf. tf->trapno est égal à 64 car vector64 a exécuté push $64. Cette valeur étant égale à T_SYSCALL, la fonction trap appelle syscall se trouvant dans syscall.c ;
  • la fonction syscall retrouve l'argument 22 correspondant à l'appel système en consultant tf->eax (rappelez vous du mov $0x16, %eax en userland). Comme cette entrée n'existe pas encore dans le noyau, syscall affiche que l'appel système est inconnu ;
  • comme l'appel système n'a pas réussi, syscall enregistre la valeur -1 dans tf->eax. Cette valeur est la valeur de retour de l'appel système. L'exécution se poursuit en sens inverse jusqu'à ce qu'on reviennent jusqu'au site d'appel à fwait(1, 42) dans le main de ftest.c.

Pour naviguer plus facilement dans les sources de xv6, nous vous invitons à utiliser l'outils ctags (sudo apt-get install exuberant-ctags) qui permet d'indexer du code source et y effectuer des recherches.

  • Pour générer un index, lancez la commande make tags qui invoque etags *.S *.c (vous pouvez d'ailleurs modifier le Makefile pour indexer égalements les fichiers *.h).
Ensuite, l'utilisation de l'index dépend de votre éditeur:
  • Sous emacs:
    • Pour rechercher la définition d'une fonction (ou d'un type), positionnez le curseur sur le type, puis faites M-. ("META point", donc la touche Echap puis la touche .)
    • Pour revenir en arrière, faites M-,
  • Sous VIM:
    • Pour rechercher la définition d'une fonction ou d'un type, positionnez le curseur sur la fonction, puis faites C-] (Ctrl et ])
    • Pour revenir en arrière, faites C-t
Maintenant que notre infrastructure de test en userland est en place, nous pouvons écrire les appels systèmes fwait et fwake dans le noyau. Vous écrivez donc vos premières lignes de code noyau à cette question !

Dans le fichier syscall.c, modifiez la table des syscalls pour faire correspondre respectivement l'appel système SYS_fwait à sys_fwait et l'appel système SYS_fwake à sys_fwake. Ajoutez la signatures de ces fonctions juste avant la définition de la structure syscalls, comme c'est déjà le cas pour sys_uptime.

Dans le fichier proc.c qui s'occupe de gérer les processus et qui possède donc la liste des processus, ajoutez les fonctions sys_fwait et sys_fwake. Chacune de ces fonctions doit afficher un message à l'aide de la fonction noyau cprintf puis retourner 0. La fonction cprintf se comporte à peu près comme la fonction printf que vous connaissez (mais ne requiert pas d'argument supplémentaire comme printf en userland puisque cprintf ne peut que faire un affichage sur la console).

Vérifiez que les messages sont bien affichés quand vous lancez la commande ftest.

Félicitations, vous savez maintenant créer des appels systèmes dans xv6 et vous êtes capables de les tester !
Nous nous occupons d'abord de la fonction sys_fwait. Pour commencer, récupérons les arguments de l'appel système. Pour cela, utilisez la fonction argint. Vous trouverez un exemple d'utilisation de argint dans sysproc.c. Affichez les valeurs des deux premiers paramètres de sys_fwait et vérifiez qu'ils valent bien 1 et 42. Nous créons maintenant les slots. Dans le fichier proc.c, ajoutez une variable int slots[] que vous initialisez avec un tableau de 5 éléments à 0. Comme le noyau xv6 peut s'exécuter en parallèle sur plusieurs cœurs, il faut acquérir un verrou avant d'accéder à slots. En effet, il est tout à fait possible qu'un autre cœur exécute fwake pendant qu'on exécute fwait. Dans sys_wait, acquérez le verrou ptable.lock après avoir extrait les arguments puis relachez le. Ce verrou est celui utilisé par l'ordonnanceur de xv6. On l'utilise ici car on modifie l'état de notre processus pour l'endormir, et l'acquisition du verrou ptable.lock nous protége donc aussi pendant qu'on modifie l'état du processus. Pour pouvoir réveiller les processus qui attendent sur un slot, nous ajoutons un champ entier wait_slot à la structure d'un processus. Lorsque ce champ vaut 1, c'est que le processus attend qu'un slot change de valeur. Ajoutez ce champs à la structure proc se trouvant dans le fichier proc.h. Dans sys_wait, il faut être capable de retrouver la structure proc correspondant au processus courant. Pour cela, vous pouvez appeler myproc(). Ensuite, tant que slots[slot] n'est pas égal à val (où slot et val sont les arguments de sys_wait), il faut :
  • positionner le champ wait_slot du processus courant à 1,
  • mettre l'état (state) du processus courant à SLEEPING, ce qui rend le processus non éligible.
  • appeler sched() pour que xv6 fasse tourner un autre processus (xv6 choisit un processus à l'état RUNNABLE et donc ignore notre processus),
  • remettre wait_slot à 0.
Si vous regardez le code de sched(), vous verrez que cette fonction considère que le processus courant doit posséder le verrou table.lock. De façon assez magique, la fonction sched() ne lâche jamais le verrou ! Techniquement, cette fonction élit un nouveau processus, et c'est ce nouveau processus qui possède le verrou puisque c'est ce processus qui tourne et qui l'avait acquis avant de s'endormir.
Testez votre programme et vérifiez que le fils ne s'exécute plus jamais. C'est normal puisque le père ne le réveille jamais. Mettez en œuvre la fonction sys_fwake. Pour cela, vous devez :
  • acquérir le verrou table.lock,
  • extraire les arguments slot et arg,
  • affecter la valeur val à slots[slot],
  • parcourir la table des processus (de ptable.proc[0] à ptable.proc[NPROC]) et pour chacun d'entre eux, le remettre à l'état RUNNABLE s'il est à l'état SLEEPING et si sa variable wait_slot est vraie.
  • lâcher le verrou table.lock.
Vérifiez que votre programme a maintenant bien le comportement attendu. La solution se trouve dans la branche futex (git checkout futex). Pour afficher l'ensemble des modifications apportées au code source, il suffit d'afficher les différences entre la version courante et les commits précédents avec : git diff HEAD^^.
Comparez le code de vos fonctions sys_fwait/sys_fwake avec le code des fonctions sleep et wakeup se trouvant dans le même fichier.

Vous devriez remarquer que ces fonctions généralisent le principe d'attente. sleep endort un processus en attendant un événement sur chan alors que wakeup réveille les processus qui attendent un événement sur chan. On aurait donc pu coder nos fonctions de la façon suivante  :

struct spinlock my_lock; int sys_wait() { ... acquire(&my_lock); while(slots[slot] != var) sleep(&slots[slot], &my_lock); // attend un wakeup sur &slots[slot] release(&my_lock); } int sys_fwake() { ... wakeup(&slots[slot]); // réveille les processus qui attendent sur &slots[slot] }