Projet système : mémoire virtuelle

De Ensiwiki
Aller à : navigation, rechercher

L'objectif de ce document est de présenter d'un point de vue pratique les spécifications, les attentes et les moyens fournis par l'environnement pour implémenter la mémoire virtuelle.

Spécifications

Objectifs à atteindre

L'implémentation de la mémoire virtuelle a pour objectif de réaliser une isolation forte des processus. Les processus ainsi isolés ont ainsi le statut de processus lourds, par opposition au processus légers, ou threads, qui partagent le même espace mémoire.

Un tel processus possède donc un espace mémoire propre dans lequel sont présents (mappés):

  • son code
  • ses données
  • son tas (si il y a lieu)
  • le noyau

Le processus ne partage donc rien avec ses voisins, le seul moyen pour lui d'y arriver, c'est de faire appel au noyau pour mettre en place des mécanismes de partage de mémoire.

De plus, dans le cas d'un noyau avec niveaux de protections, comme le notre, l'application est isolée du noyau. En effet, dans l'espace mémoire d'un processus donné, le noyau est mappé, certes, mais ce mapping n'autorise l'accès à la mémoire que lorsque le processeur se trouve un mode superviseur. Ainsi, une application qui s'éxecute en mode non privilégié ne peut ni accéder aux données ni éxecuter du code dans l'espace mémoire du noyau sans passer par un appel système. Sinon une exception est levée.

D'une manière générale, un accés à une adresse non-mappée, une écriture sur une page read-only ou encore un accés à une page privilégiée depuis le userspace provoque une exception. Ces exceptions doivent être rattrapées et traitées par le noyau pour prendre une action sur le processus; le tuer par exemple.

Conventions

L'une des difficultés de la mise en place d'une isolation par mémoire virtuelle réside dans les choix d'implémentation qu'il faut faire. Nous avons fait une partie de ces choix pour vous en se basant sur ce qui existe déjà dans d'autres systèmes d'exploitation.

Espace d'adressage : solution 1G/3G similaire au noyau Linux

  • L'espace mémoire du noyau est mappé entre les adresses 0 et 1G.
  • L'espace utilisateur est mappé entre 1G et 4G, un processus dispose donc de 3 Go de mémoire virtuelle.

Conventions d'édition de lien :

  • Le noyau est prévu pour être logé entre 0 et 1G, son adressage virtuel est directe (@virtuelle = @physique), le code commence à l'adresse 1M (0x100000).
  • Une application utilisateur commence à l'adresse virtuelle 1G, son code débute exactement à cette adresse (section .text), les données et le tas sont disposées après (sections .rodata, .data, .bss et autres).
  • La pile est logée où vous le souhaitez dans l'espace user en gardant deux choses à l'esprit:
    • Sur x86 une pile progresse à l'envers, l'adresse fournie initialement comme pointeur de pile va décroitre au fur et à mesure de l'éxecution,
    • La pile ne dois pas être trop proche de 1G sans quoi son évolution risque d'écraser les données puis le code de l'application.

Environnement de travail

Les sources du projet qui vous sont fournies permettent de compiler le noyau, des applications et d'embarquer le tout dans un seul et unique binaire qui sera chargé au moment du boot. Cette implémentation nous permet de nous passer d'un système de fichiers dont la mise en place serait complexe.

Voici le principe de fonctionnement de l'environnement proposé. En premier lieu, les applications situées dans le répertoire user/ sont compilées et linkées suivant les conventions que nous avons défini plus haut. Ensuite les sources du noyau sont compilées, puis au moment de l'édition de lien, le noyau est assemblé, et les applications sont ajoutées dans le binaire. Une table, générée à la compilation et intégrée au noyau, fourni la liste des applications et leur position en mémoire au moment de l'éxecution, cela vous permettra de retrouver et charger leur code/données.

Une application user

Une application pour la chaine de compilation est un dossier situé dans le répertoire user/, dont le nom est le nom de l'application et ajouté dans user/Makefile à la variable APPS_NAMES.

Exemple : user/Makefile

[...]
### Import userspace program build toolchain ###
APPS_NAMES := mon_appli1 mon_appli2 mon_appli3
[...]

Notez l'abscence de / en fin de nom, et pensez à ne pas utiliser caractères interprétés par GNUmake. A titre de convention, on peut se restreindre aux caractères alpha-numériques et '_'.

Le répertoire de l'application doit à minima comprendre un fichier C (*.c) ou assembleur (*.S) contenant un symbole main. L'implémentation minimale attendue est la suivante:

int main(void *arg)
{
        return 0;
}

quasiment à l'instar d'un main standard C. Cette application, disons toto, sera compilée en un fichier toto.bin que l'on retrouvera dans le dossier user/out/.

Ce code sera linké suivant les directives contenues dans le fichier user/out/apps.lds, à savoir:

  • Adresse de départ à 1G soit 0x40000000
  • En tête du binaire sont placées les sections .text (et .text.init dont nous parlerons plus tard) des fichiers de l'application de manière à pouvoir brancher sur l'adresse 1G de manière déterministe
  • Puis linker les sections .rodata, .data, .bss et autres à la suite.

Le binaire résultant est brut, prêt à être copié en mémoire et executé en place. Il ne contient plus d'information de débug ou de format ELF. Sinon il faudrait implémenter un chargeur ELF.

Au moment de la compilation du noyau, ces binaires bruts sont copiés dans une section particulière du binaire kernel.bin, ils seront ainsi embarqués dans la mémoire au moment du chargement du noyau par le boot loader.

Bibliothèque standard

L'environnement du noyau est livré avec un petit morceau de libc qui vous permet de bénéficier d'une partie de l'API C dont nous avons l'habitude (fonctions de manipulation de chaines de caractères, assertions, types standards, etc.). Les applications de l'espace utilisateur vont évidement vouloir accéder à ce code. De plus, il existera du code commun à toutes les applications pour permettre de faire des appels systèmes et autres. C'est ce qui va constituer la bibliothèque standard de notre couple kernel/userspace.

Pour répondre à ce besoin, l'environnement user du noyau fourni une mécanique pour compiler une bibliothèque standard et la linker à chacun des programmes. Cette bibliothèque est le résultat de la compilation des fichiers des répertoires shared et user/lib/ et se présente sous la forme d'une archive que l'on retrouvera dans user/out/libstd.a. Cette archive sera linkée statiquement avec chacune des applications. Encore une fois, ce n'est pas la solution la plus économe, mais elle permet à nouveau d'éviter l'implémentation d'un chargeur dynamique.

Le code et les définitions de vos appels systèmes doivent prendre place dans le répertoire user/lib/ et feront partie de la bibliothèque standard. Il faudra prendre soin de retirer les symboles de fonction du fichier user/lib/weak-syscall-stubs.S, ils sont là pour permettre la compilation, et seront à remplacer par votre implémentation.

Il est important de comprendre que ce partage de code n'implique pas un partage de données. Si vous définissez une variable globale quelle qu'elle soit dans ce code partagé, les applications ne la partageront pas mais en obtiendront une copie !

Notes :

  • Le code et les définitions placées dans shared/ doivent rester compatible avec l'environnement noyau et utilisateur. Il est conseillé de ne pas ou peu le modifier sous peine de vous attirer des problèmes. De même, les fichiers de shared/ ne doivent pas dépendre d'en tête de kernel/ ou user/, l'inverse est possible.
  • Il est fortement déconseillé de modifier la chaine de compilation sans de très bonnes raisons, elle est complexe et les conséquences peuvent-être importantes.
  • La bibliothèque standard est compilée et linkée suivant les directives contenues dans user/Makefile et user/build/stdlib.mk.

Chargement d'une application

Afin de lancer un processus vous devez avoir créé son environnement (structure de processus, pile, structures de pagination) de manière à ce que l'application puisse s'éxecuter dans l'environnement virtuel qu'elle attend (cf les spécifications plus haut). Néanmoins, à un moment donné pendant cette création, vous devez avoir copié le code de l'application dans la mémoire du processus et pour cela vous devez savoir où se trouve le code d'origine dans la mémoire du noyau.

Sur un système d'exploitation classique, les applications sont obtenues à partir du système de fichiers, ou plus généralement d'un support à mémoire non volatile (disque dur, ssd, clef usb, cdrom, etc). Notre implémentation ne fourni pas cela, les binaires des applications sont donc chargés dans la mémoire en même temps que le binaire du noyau.

Localiser une application

Une table fournie par la chaine de compilation permet de retrouver la position d'un binaire dans la mémoire à partir de son nom. Vous trouverez les déclarations de la table dans kernel/userspace_apps.h, fichier d'en-tête à inclure dans votre code.

Une table d'applications est composée de descripteurs qui suivent la déclaration suivante (déclaration disponible dans kernel/userspace_apps.h):

struct uapps {
        const char *name;
        void *start;
        void *end;
};
  • name le nom de l'application concernée par ce descripteur.
  • start pointeur sur le début de la mémoire contenant l'application.
  • end pointeur sur la fin de la zone contenant l'application.

Le nom name est le nom de l'application telle qu'il a été défini dans la variable APPS_NAMES de user/Makefile. Il n'existe aucune contrainte d'alignement sur les adresses start et end.

Le dernier descripteur de la table est rempli de valeurs nulles pour permettre la détection de fin de liste.

En supposant que j'ai trois applications toto1, toto2 et toto3 déclarées coté user, je vais obtenir la table suivante:

const struct uapps symbols_table[] = {
        {"toto1", _toto1_start, _toto1_end},
        {"toto2", _toto2_start, _toto2_end},
        {"toto3", _toto3_start, _toto3_end},
        {NULL, NULL, 0}
};

où les symboles _totoX_start et _totoX_end seront résolus à l'édition de lien pour fournir les adresses de début et de fin de l'application totoX.

A chaque lancement de processus vous devrez chercher dans cette liste le code de l'application et le charger dans la mémoire du processus créé. Par design cette recherche peut-être coûteuse si il y a un grand nombre d'applications. Une implémentation de table de hachage (kernel/hash.[hc]) vous est fourni, vous devez remplir une instance de cette table avec la liste des applications et leur descripteur afin d'avoir un accés rapide à ces informations.

Construction de la table des symboles

L'objectif de ce paragraphe est de documenter la partie de la chaine de compilation qui embarque les applications et génère la table des symboles. Ces informations ne vous seront pas utiles directement mais vous permettront peut être de faciliter le débugguage.

Dans la suite on considèrera que l'espace utilisateur contient trois applications déclarées dans user/Makefile de la manière suivante: user/Makefile :

[...]
APPS_NAMES := app1 app2 app3
[...]

La séquence de création est la suivante :

  • L'espace utilisateur est compilé : la bibliothèque standard puis les binaires des applications vont être générés, nous allons obtenir user/out/app1.bin, user/out/app2.bin et user/out/app3.bin.
  • La chaine de compilation coté kernel/ liste les *.bin contenus dans user/out/ et construit une liste d'applications à partir de noms de fichiers (retrait de l'extension .bin)
  • A partir de chaque fichier, par exemple app1.bin, un fichier objet est généré, kernel/out/app1.bin.o, dans lequel le contenu du binaire brut app1.bin est placé dans une section .app1.bin.
  • Génération de la table des symboles kernel/out/symbols-table.c à partir de la liste d'applications en utilisant kernel/build/generate-symbols-table.sh. Ce qui donne:

Exemple : kernel/out/symbols-table.c

#include "stddef.h"
#include "userspace_apps.h"

/*
 * Declare linker's symbols. For each user application we declare its
 * position in memory, the length of the binary, and the name of the
 * application.
 */

/* "app1" symbols */
extern char _app1_start[];
extern char _app1_end[];

/* "app2" symbols */
extern char _app2_start[];
extern char _app2_end[]; 

/* "app3" symbols */
extern char _app3_start[];
extern char _app3_end[];

const struct uapps symbols_table[] = {
        {"app1", _app1_start, _app1_end},
        {"app2", _app2_start, _app2_end},
        {"app3", _app3_start, _app3_end},
        {NULL, NULL, 0}
};
  • Compilation de kernel/out/symbols-table.c.
  • Génération d'un fichier d'édition de lien pour inclure les sections des binaires dans le noyau final, à l'aide de kernel/build/generate-link-sections.sh.

Exemple : kernel/out/apps.lds

/* "app1" link definition */
        _app1_start = .;
        *(.app1.bin)
        _app1_end = .;

/* "app2" link definition */
        _app2_start = .;
        *(.app2.bin)
        _app2_end = .;

/* "app3" link definition */
        _app3_start = .;
        *(.app3.bin)
        _app3_end = .;

Ce fichier sera inclu par les directives d'édition de lien du noyau (kernel/build/kernel.lds) de manière à placer les binaires dans la section .rodata du binaire final.

  • Compilation des sources du noyau et link : les fichiers objet du noyau et ceux des applications sont linkés, les symboles de la table des symboles sont résolus. Les applications seront localisables dans le binaire final à l'aide de la table.

Situation initiale

Avant de se lancer dans l'implémentation de votre solution, il faut comprendre l'état dans lequel est placé le noyau après le passage par le boot loader. Le binaire du noyau suit un standard appelé Multiboot qui permet de se faire charger par un loader respectant ce standard (GRUB legacy, GRUB, syslinux, qemu -kernel, etc.). Ainsi quand la main est passée à notre code, on connait l'état dans lequel est le processeur, nous sommes déjà en mode protégé, enfin, nous avons quelques facilités en plus.

Une fois le travail du loader fait, le processeur est branché sur notre code de bootstrap contenu dans kernel/boot/crt0.S. Cette portion de code va installer un environnement propice:

  • installer une pile

kernel/boot/crt0.S :

/* We have to set up a stack. */
leal    first_stack,%esp
addl    $FIRST_STACK_SIZE,%esp
xorl    %ebp,%ebp
  • passer la main a la fonction boot qui va finir les initialisations
call    boot

/* This function should never exit. If it happens, reboot. */
call	reboot


  • initialiser la mémoire non utilisée à 0

kernel/boot/boot.c :

/* Blank all free memory */
memset(_data_end, 0, (size_t)mem_heap_end - (size_t)_data_end);
  • initialiser certaines tables du processeur

kernel/boot/boot.c :

/* Initialize CPU structures */
cpu_init();


  • mettre en place une pagination identité avec protection des zones critiques

kernel/boot/boot.c :

/* Setup paging */
early_mm_check();       // Check binary linkage
early_mm_map_kernel();  // Map kernel memory
enable_paging();        // Enable CPU paging


  • Les 256 premiers Mo de la mémoire sont mappés de manière identitaire: @virtuelle = @physique
  • adresses 0 - 4Ko non mappées pour attraper les déréférencements de pointeurs NULL

kernel/boot/early_mm.c

/* Zone 1: protect first page, no mapping. */
pgtab[0] = 0;
  • la zone .rodata du noyau est mappée en read-only et la protection d'écriture est activée

kernel/boot/early_mm.c

/* Zone 4: .text, .rodata and .multiboot sections are obviously read only */
early_mm_map_region(pgdir, (unsigned)_text_start, (unsigned)_text_end, PAGE_TABLE_RO);
early_mm_map_region(pgdir, (unsigned)_multiboot_start, (unsigned)_multiboot_end, PAGE_TABLE_RO);
early_mm_map_region(pgdir, (unsigned)_rodata_start, (unsigned)_rodata_end, PAGE_TABLE_RO);
/* Except first stack which is RW */
early_mm_map_region(pgdir, (unsigned)_bootstrap_stack_start, (unsigned)_bootstrap_stack_end, PAGE_TABLE_RW);
  • Enfin les données et la mémoire libre sont mappées en lecture / écriture

kernel/boot/early_mm.c

/* Zone 5: .data and .bss are read/write */
early_mm_map_region(pgdir, (unsigned)_data_start, (unsigned)_data_end, PAGE_TABLE_RW);
early_mm_map_region(pgdir, (unsigned)_bss_start, (unsigned)_bss_end, PAGE_TABLE_RW);
/* Zone 6: free memory is read/write */
early_mm_map_region(pgdir, (unsigned)_end, (unsigned)mem_end, PAGE_TABLE_RW);


  • Finalement la pagination est activée

kernel/boot/crt0.S :

/* PG (paging) flag, bit 31 of CR0 : must to be set to active paging */
/* WP (write protect) flag, bit 16 of CR0: must be set to prevent write on ro pages */
/* Cf. 6.2.1 Intel Architecture Software Developer's Manual Volume 3 */
movl    %cr0,%eax  
orl     $0x80010000,%eax
movl    %eax,%cr0

Le directory et la table des pages utilisés pour ce premier mapping sont tous les deux stockés dans ce même fichier. Le directory est pré-initialisé (symbole pgdir), la table des pages (symbole pgtab) est juste pré-allouée par la directive .org et sera remplie à l'éxecution. Les protections à l'écriture seront rajoutées ensuite en modifiant certain flags dans la table des pages. Cette pagination pré-installée permet, entre autre, de déclencher le débuggeur sur les fautes d'accès mémoire et vous aider à débugguer. Il faudra la retirer, mais dans la mesure du possible en conserver les propriétés.