Projet système PC : 2018 - EL HAIK Léa, MAILLARD Jose, MILHADE Laurent, SICARD Valentin, TRAMPAL Lucas, WALLON Benoît

De Ensiwiki
Aller à : navigation, rechercher
Affichage au démarrage - Cliquer sur l'image pour afficher l'animation

Présentation

Ce projet correspond à la suite du cours de Projet de Conception de Système d'Exploitation - Fondements. Il consiste à poursuivre et compléter ce qui avait été fait pendant ce cours afin d'obtenir un noyau de système d'exploitation utilisable sur une architecture Intel x86. Cela, à partir de seulement quelques librairies C données. L'objectif était de pouvoir mettre en œuvre des concepts de base liés aux systèmes d'exploitation: la gestion de processus, l'utilisation de files de messages, la mémoire partagée, la gestion des entrées / sorties et l'implémentation d'un interprète de commande.

Notre équipe

Notre équipe est constituée de 6 étudiants :

Implémentation et Réalisation

Phase 1 : Gestion de l'affichage à l'écran

100 %

Cette partie fut reprise directement depuis la partie correspondante du cours de PCSE-F. Les caractères à afficher sont inscrits directement dans la zone mémoire à laquelle l'écran est associé. Les manipulations d'affichage correspondent à des manipulations de cette zone mémoire.

Phase 2 : Gestion de processus et changement de contexte au niveau du noyau

100 %

Les procesus sont crées statiquement et stockés dans un tableau. Cela permet un accès en o(1) à partir du pid.

Une file permet de recenser les processus terminés et de les réatribuer lorsque toute les cases du tableau ont été attribuées une première fois.

Le pid est tel que modulo la longueur du tableau, on obtient l'indice du processus dans ce tableau.


Un processus peut avoir plusieurs états :

- INIT quand l'emplacement mémoire n'est pas encore attribué

- ELECTED quand il est en cours d'execution

- ACTIVABLE quand il est prêt à s'executer

- SEM_BLOCKED quand il est bloqué sur la réception ou l'envoi de message

- IO_BLOCKED quand il est bloqué sur les entrées clavier

- CHiLD_BLOCKED quand il est bloqué sur l'attente d'un fils

- ASLEEP quand il attend une date pour se réveiller

- ZOMBIE quand il est terminé


L'ordonnanceur gère le changement de contexte et l'attribution des états ELECTED, ACTIVABLE et ASLEEP.

Il est appelé pour le changement de contexte par l'horloge à la fréquence SCHEDFREQ.


Un gestionnaire de processus controle l'ordonnanceur, ainsi que la échanges de messages et les entrées clavier.

Il gère la création de processus et les rend disponibles pour l'ordonnanceur, la terminaison et l'état ZOMBIE, et l'attente des processus fils.

Phase 3 : Ordonnancement, création, filiation et terminaison des processus

100 %

De la même façon que pour l'affichage, la gestion de l'horloge fut récupérée du cours de PCSE-F. On utilise un traitant d'interruptions correspondant aux tics de l'horloge. Ce traitant permet d'avoir le nombre de secondes écoulées depuis le lancement du système, de potentiellement réveiller un processus et de lancer le gestionnaire de changement de contexte à des intervalles de tics réguliers. Parler aussi de waitclock qui est dans phase 4 mais qu'on a fait ici

Filiation des processus

Notre OS gère la filiation entre les processus. Un processus dit "père" peut ainsi attendre et récupérer la valeur de retour de n'importe lequel des processus qu'il a créé.

Il faut donc que chaque processus connaisse sa filiation directe.

Nous avons dû adapter les fonctions de terminaison d'un processus (kill, exit) pour conserver la valeur de retour et potentiellement réveiller son père, s'il est en attente.


Les processus dans l'état ASLEEP sont stockés dans une file de priorité ordonnée par la date de réveil. A chaque tick de l'horloge, les processus ayant une date de réveil inférieure à la date courante sont réveillés.


Le réveil des processus n'est pas sychronisé avec l'appel à l'ordannanceur


Un processus non terminé dont le parent passe dans l'état ZOMBIE est rataché a processus idle et terminé définitivement lorsqu'il se termine.

Pour être plus précis, la suppression définitive d'un processus rataché à idle dans l'état ZOMBIE s'effectue à la création d'un nouveau processus.

Phase 4 : Les files de messages

100 %

Les files de messages sont des structures de données qui permettent à des processus de se transmettre des informations : des processus envoient des données et si la file est pleine, ils bloquent jusqu'à ce qu'un autre processus viennent récupérer un message, le processus envoyant va alors immédiatemment combler le vide laisser et se débloquer. De cette manière, même si la file est pleine, les processus peuvent tout de même se mettre en attente pour envoyer leur message. Le système est le même dans le cas où un receveur demande un message à une file vide.

L'implémentation de ce système a posé quelque difficulté : notamment réussir à envoyer immédiatement un message après libération d'un espace sur la file de message.

Phase 5 : Mémoire virtuelle et séparation utilisateur / superviseur

100 %

Mémoire virtuelle

Implémentation

L'idée derrière le concept de mémoire virtuelle est de séparer la mémoire des processus de manière à ce que l'un ne puisse pas accéder aux données de l'autre directement mais également de simuler un espace de taille fixe (ici 4Gio) dans lequel chaque processus s’exécute toujours à la même adresse. Une base de mémoire virtuelle était déjà fournie dans les sources de bases du projet pour le processus originel ("idle"). Il nous restait à implémenter la mémoire virtuelle pour chaque nouveau processus.

L'implémentation que nous avons réalisée est très classique : à sa création, chaque processus alloue une structure qui stocke l'adresse de ses pages : le répertoire de page. Le matériel se charge de la conversion d'adresse virtuelle en adresse physique grâce à la MMU (memory management unit). Pour que celle-ci se fasse correctement, il faut lui indiquer l'adresse mémoire de la structure de pagination utilisé par le processus courant dans le registre cr3. Pour cela, à chaque changement de contexte, il faut modifier ce registre avec la valeur du répertoire de page du nouveau processus.

Au lancement du processus, ses pages sont allouées dans la mémoire kernel (dans le tas kernel situé entre 16Mio et 64Mio) et à chaque changement de contexte elles sont chargées dans la mémoire utilisateur située entre 64Mio et 256Mio.

Mémoire physique
                           +--------------+ [256Mio]
                           |              |
                           |              |
                           |              |
    Espace utilisateur     |              |             Contient les pages des processus qui ont été chargées en mémoire
                           |              |
                           |              |
                           |              |
                           +--------------+ [64Mio]
                           |              |             Tas du noyau (contient la mémoire allouée dont les tables des pages, les répertoires de pages
     Espace kernel         |              |             et les pages des processus)
                           |              | [16Mio]
                           +--------------+ [0Mio]      Espace contenant le code du noyau et des programmes utilisateurs

Spécificité de notre implémentation Le cadre de ce projet ne demandait que l'implémentation simplifiée de la pagination. Il n'y a notamment pas d'allocation dynamique de pages en mémoire physique dans notre système d'exploitation : au lancement du processus, toutes les pages du processus sont chargées en mémoire physique (dans l'espace utilisateur). S'il ne reste plus de place pour celle-ci, une page n'appartenant pas au processus que l'on est en train de charger est retirée de la mémoire physique pour faire de la place. Chaque page de l'espace utilisateur est en fait une copie d'une page située dans l'espace kernel. Lorsqu'une page est sortie de l'espace utilisateur, elle est immédiatement copiée dans l'espace kernel pour remplacer son ancienne version.

Cartographie de la mémoire virtuelle d'un processus

NB: la mémoire d'un processus utilisateur est mappée par un répertoire de page (page directory) contenant 1024 tables des pages qui elles mêmes contiennent chacune les références vers 1024 pages de 4Kio.

Mémoire virutelle d'un processus
                    +--------------+ [4Gio] = 0xFFFFFFFF
                    |              |
2 tables des pages  +- STACK USER--+     2 Page tables -> la taille maximale de la stack d'un processus est 8Mio
                    |              |   
                    +--------------+ [4Gio - 8Mio] 
                    |##############| 4KiB             1 Page "canarie" (voir remarque 1)
                    |   EXIT CODE  | 4KiB             1 Page contenant le code à executer à la fin du programme utilisateur
1 tables des pages  | STACK KERNEL | 4KiB             1 Page contenant la stack du noyau du processus
                    |              |
                    |       .      |
                    +--------------+ 
                    |       .      |
                    |       .      |
                    +--------------+ [2Gio + 4Mio]
                    |       .      |
1 tables des pages  | SHARED PAGES |                  1024 pages pouvant correspondre à des pages partagées entre processus
                    |       .      |
                    +--------------+ [2Gio] = 0x80000000
                    |       .      |
                    |       .      |
                    |       .      |
                    | PROCESS CODE |
                    +--------------+ [1Gio] = 0x40000000
                    |              |
64 tables des pages | KERNEL MEMORY|
                    |              |
                    +--------------+ [0Gio] = 0x0

Remarque 1 : Cette page est n'est jamais mappé en mémoire : de cette manière si la stack utilisateur vient dépasse sa capacité maximale, la MMU renverra une faute de page en accédant à ces adresses.

Remarque 2 : Il n'y a pas besoin de page de canarie ici car la stack kernel est de taille limitée et ne remplie jamais une page complète.

Invalidation de la TLB (Translation Lookaside Buffer)

La TLB est une unité matérielle qui participe avec la MMU à la conversion d'adresse virtuelle en adresse physique. Il s'agit en fait d'un cache qui retient les dernières traductions qui ont été effectuées par la MMU. Lorsqu'une page est retirée de la mémoire physique, l'entrée correspondante de sa table des pages est mise à 0 de manière à ce que la conversion d'adresse effectuée par la MMU échoue. Toutefois, si cette page a été récemment accédée, une traduction valide de celle-ci peut toujours exister dans la TLB ce qui mènera à un accès mémoire non autorisé ou à une erreur. Pour cela il est important d'invalider dans la TLB, à chaque retrait de page, l'entrée correspondant à cette page. Cela est réalisé simplement avec l'instruction assembleur "invlpg". On pourra noter qu'au changement de contexte entre deux processus, il faut invalider toute la TLB mais qu'il n'est pas nécessaire d'utiliser "invlpg" pour cela car un changement du registre cr3 invalide automatiquement toutes les entrées de la TLB.

Protection de la mémoire kernel, mise en place du mode utilisateur

Principe de la protection mémoire

L'objectif de la mise en place de la protection de la mémoire du noyau est l'isolation complète des processus entre eux et l'impossiblité pour eux d'accéder à la mémoire des autres. Cela restreint également le champ d'action possible des processus en leur interdisant l'accès à certaines instructions, périphériques et zones mémoires.

L'exemple le plus basique est celui de l'accès au registre cr3 : c'est le registre qui détermine quel répertoire de pages va servir pour la traduction d'adresse, si un processus peut le modifier, il va pouvoir accéder directement à la mémoire d'un autre. Pire, il peut directement aller modifier dans la mémoire kernel (sans passer par le registre cr3) les structures de pagination des autres processus qui y sont stockées.

Parmis les opérations privilégiées on trouve notamment :

  • accès aux registres privilégiés (segments, cr3...)
  • appel à certaines interruptions
  • accès à des instructions privilégiées : lgdt, lidt... pour les accès à l'adresse des tables de descripteurs de segments ou encore invlpg que nous avons vu plus haut

L'objectif est donc de diminuer le niveau de privilège des processus utilisateurs : pour cela il faut modifier les registres de segments (cs, ss, ds, es, fs et gs) qui determine les permissions utilisateurs. Ceci suffit à restreindre l'accès aux instructions privilégiées. La limitation de l'accès à l'espace mémoire se fait directement dans les structures de paginations grâce à des flags associés à chaque page, et notamment le flag US qui définit si un processus en mode utilisateur peut accéder à cette page. Toutes les pages de l'espace kernel n'ont donc pas ce flag et un processus avec des segments utilisateur ne pourra pas y accéder.

Le seul moyen pour un processus d'effecuter des opérations privilégiés ou du code situé dans l'espace kernel sera de passer par des appels systèmes ou des interruptions qui élèverons les privilèges du processus le temps de réaliser une opération précise.

Implémentation Pour implémenter une séparation kernel fonctionnelle, nous avons dans un premier temps rajouté un stack kernel pour chaque processus : quand le processus s'execute en mode kernel, il a besoin de stocker des données sur la stack et pour assurer une séparation complète il convient que les données kernel du processus soit séparée de ses données utilisateur.

Un difficulté rencontrée a été de lancer le processus en mode utilisateur : en effet, le processus est toujours crée par le CPU alors que celui-ci est en mode superviseur. Cela ce produit de 2 façons : soit le processus père est idle, soit c'est un autre processus utilisateur qui l'a crée par le biais d'un appel système (en passant par l'instruction "int" qui fait passer le processus en mode superviseur, celui-ci reviendra en mode utilisateur avec l'instruction "iret"). Pour que le processus passe bien en mode utilisateur à son lancement, nous l'avons donc placé (sa stack kernel notamment) dans un état similaire à celui dans lequel il aurait été suite à une interruption tout en nous arrangeant pour qu'il execute l'instruction iret en se lançant.

La seconde difficulté a été de gérer la terminaison du processus : en effet, quand un processus se termine, nous avons besoin de stocker sa valeur de retour dans une structure pour la mettre à disposition d'autres processus en ayant besoin. Le code permettant de réaliser ce comportement est celui de la fonction exit. Le problème est que au moment du lancement, le processeur en en mode kernel et ne connaît pas l'adresse de la fonction exit utilisateur : il est donc impossible de l'indiquer comme adresse de retour au processus. Nous avons donc créer une page spéciale contenant le code assembleur permettant d'executer l'appel système à correspondant à l'appel de la fonction exit.

Appels système

Nous avons une bibliothèque de primitives systèmes partie user. Ces primitives appellent une fonction en assembleur, définie dans syscallx86.S, qui va elle même déclencher l'interruption 49. On passe alors dans le traitant d'interruption coté kernel, qui va pouvoir effectuer l'action voulue, et ensuite rendre la main coté user. Pour la gestion des paramètres, nous avons choisi de les ajouter à la pile. Puisque nous avons une fonction générale, nous passons toujours 5 paramètres, ceux ci étant à NULL si inutiles. Le premier paramètre est celui de l'appel système à effectuer, se référant à une macro dans shared/table_syscall.h. Ce paramètre est donc ensuite récupéré sur la pile au niveau du kernel, on teste sa valeur et on effectue la fonction correspondante.

API de partage de pages

Les fonctions shm_create shm_require et shm_release ont été réalisées en respectant la spécification.

Comme indiqué sur le schéma de la mémoire utilisateur, les pages partagés sont mapées à partir de 2Gio sur une seule page table (ie d'index 512 dans le page directory).

On peut donc avoir au plus 1024 pages partagées dans notre OS ce qui nous a semblé suffisant dans la plupart des cas.

Sécurisation de l'espace kernel

Un des tests qui nous était fourni pour tester notre OS réalisait une élévation de privilège en utilisant les appels systèmes pour écrire une nouvelle interruption dans la page des descripteurs d'interruption en choisissant pour adresse de traitant d'interruption une fonction qui s'executera en mode kernel. Cette attaque est réalisée grâce à certains appels systèmes qui demande qu'on leur donne un pointeur dans lequel ils écriront une valeur : si le processus utilisateur donne un pointeur vers une zone en mémoire kernel, l'appel système s'executera en mode superviseur et aura les droits pour écrire cette zone. Via d'autres moyens, le processus utilisateur peut parvenir à controler la valeur écrite à l'adresse pointée et ainsi élever ses privilèges.

Pour s'assurer que notre noyau ne soit pas vulnérable à ce genre de faille, tous les pointeurs servant à une écriture qui sont utilisés dans les appels systèmes sont testés et mis à NULL s'ils présentent des risques.

Phase 6 : Pilote console

100 %

Gestion des événements de frappe

L'analyse des scan codes étant fournie, il ne restait plus qu'à rattacher un traitant d'interruption à chaque frappe. La fonction appelée récupère le scan code et le transmet au code fourni. Ce dernier appelle ensuite la fonction keyboard_data avec les caractères lus qui : - les stocke dans le tampon si celui-ci n'est pas plein - affiche le caractère à l'écran si l'écho est activé, efface le caractère précédant si backspace a été pressé

Lecture des caractères tapés

La lecture des caractères se fait via un appelle à cons_read comme requis dans la spécification. Lorsqu'un processus demande une lecture, il se bloque une première fois si d'autres processus sont déjà en attente. Il est ensuite libéré lorsque c'est son tour et qu'un retour à la ligne a été tapé et reçoit les caractères dans la limite de la taille demandée.

Phase 7 : Interprète de commande (shell)

100 %

Nous avons essayé de nous avancer sur le mode utilisateur dès le début du projet, avec l'élaboration d'un parseur pour les commandes entrées dans le shell. Malheureusement, il n'y a pas eu de test avant la fin de la phase 5 puisque la séparation mémoire n'était pas implémentée. Du coup, une fois la mémoire implémentée, nous nous sommes rendu compte que la méthode n'était pas la bonne puisque nous ne pouvions allouer de la mémoire dynamiquement. De plus, il y avait une bibliothèque de commande liée à l’interpréteur de commande dans la lib user, mais cela causait trop de soucis en mémoire, donc nous avons préféré créer une application dédiée à la console.

Le debug de cette partie était difficile, puisque nous n'avions pas accès à la mémoire utilisateur avec make run-debug. Il fallait donc faire des breakpoints sur les différents appels systèmes et regarder le code assembleur qui était présent ensuite.

Finalement, nous avons pu implémenter un shell respectant les spécifications du projet, soit les commandes :

  • ps
  • echo [on/off]
  • exit

Nous avons rajouté quelques commandes qui peuvent être utiles comme :

  • history, qui affiche l'historique des commandes écrites dans le shell
  • help, qui affiche l'aide
  • kill [pid], qui tue un processus pour le zombifier
  • clear, qui nettoie l'écran
  • boot qui lance l'écran de démarrage
  • [proc] qui lance un processus, si ceci est possible.

Nous gérons aussi le lancement d'un processus en tâche de fond, avec un espace entre le nom du processus et l’esperluette, celle ci devant être à la fin de la commande ( exemple : autotest &), ainsi que le Ctrl-C pour kill un processus en tache de fond.

Répartition des tâches

Léa El Haik
  • Interprète de commande
  • Aide au mode utilisateur
José Maillard
  • Gestion des processus
  • Debogage des files de messages.
Laurent Milhade
  • Tests kernels et analyse des résultats.
Valentin Sicard
  • Aide au processus.
  • Aide au mode utilisateur.
  • Partage mémoire entre processus.
Lucas Trampal
  • Pilote clavier et fonctions associées.
Benoît Wallon
  • Files de messages
  • Mémoire virutelle
  • Mode utilisateur

Résultats

Nous avons réussi à implémenter un OS de base fonctionnel, avec un shell léger mais satisfaisant. Tous les tests fournis passent en mode user, et nous avons aussi testé manuellement les différentes commandes.


Autotest running.png


Nous avons préféré concevoir un OS sans extension importante mais avec une gestion de la mémoire solide, comme expliqué plus haut.

Conclusion

Ce projet imposant fut fort intéressant et formateur. Il nous a permis d'obtenir des bases plutôt solides sur des concepts importants du bas niveau et des connaissances approfondies de l'architecture Intel x86. Il nous permet de tester nos connaissances, et d'aller chercher dans de la documentation des informations très précises, donc nous avons acquis des connaissances solides sur la conception des systèmes d'exploitation.

Pour la gestion de projet, étant donné que nous étions une équipe de 6, il a fallu s'organiser. Nous avons respecté la roadmap afin de suivre les différentes phases, qui constituaient des "parties" du projet.

La disposition des horaires de cours (trois heures coupées en deux, par semaine) ne nous permettait pas d'être efficaces lors des séances de développement prévues. La bonne répartition des charges de travail à 6 en fut d'autant plus compliquée.

Cependant, nous avons réussi à rendre un projet qui nous satisfait pleinement, en travaillant avec une équipe hétéroclite mais soudée.

Documentation

Outils utilisés