[Kos-dev] Re: [Kos-announce] Nouveautes du Week End

[d2]

Bonjour,

L'annonce faite hier concernant les nouveautés du WE ne rentrait pas
dans les détails des modifications et de nos réflexions sur la VM.

Thomas a donc rédigé le compte-rendu plus détaillé et plus précis que
voici.

------

Seuls David et Thomas étaient présents à ce WE, Julien n'ayant pas pu
nous rejoindre.

Au programme des réalisations de ce WE :

 1 - Compilation silencieuse tous warnings activés

   Auparavant, nous compilions simplement KOS avec l'option -Wall
   permettant d'obtenir un certain nombre de warnings, mais pas tous
   ceux détectés par gcc.

   La nouvelle séquence de CFLAGS présente dans le fichier MkVars est
   la suivante :

       CFLAGS += -ffreestanding -W -Wundef -Wshadow -Wpointer-arith
                 -Wcast-align -Wsign-compare -Waggregate-return
                 -Wmissing-prototypes -Wredundant-decls -Wnested-externs
                 -Winline -Wold-style-cast -Wall -O2

   Par rapport à la version initialement prévue, nous avons supprimé
   les warnings suivants :
	-Wbad-function-cast car il générait un warning chaque fois
           que l'on castait un void* en addr_t ou l'inverse. Ce
           warning nous embêtait vraiment : les fonctions d'allocation
           de mémoire retournent généralement des void*, mais nous
           voulons parfois stocker le résultat dans une variable de
           type addr_t (qui n'est pas un pointeur).
	-Wcast-qual car il générait un warning dès que l'on castait
           une variable ayant un qualifier (par exemple const ou
           register) en un type n'ayant pas ce qualifier.
	-Wconversion car il générait un warning dans le cas où nous
           passions un int à une fonction demandant un short par
           exemple (problème de taille). Cette vérification nous a
           semblé trop contraignante.

   Ces nouveaux warnings ont permis de mettre de l'ordre dans le
   code. Ils permettent notamment de vérifier que :
 	 - tous les membres d'une structure sont bien initialisés (pas
           d'initialisation partielle de la structure). Cette
           vérification a introduit une grosse correction de
           modules/debug/disasm.c qui pratiquait énormément
           l'initialisation partielle de structures.
	 - toutes les fonctions qui n'ont pas de prototypes dans un .h
           (ou précédemment dans le .c), sont bien locales, et donc
           sont bien déclarées comme étant statiques.
	 - toutes les valeurs négatives placées dans un unsigned sont
           correctement castées, et donc que le programmeur est bien
           conscient de ce qu'il fait. Ex unsigned int toto = -4;
         - aucune variable dans un scope donne ne cache une variable
           de meme nom d'un scope englobant. Par exemple : une
           variable locale toto est définie alors qu'une variable
           globale toto existe déjà.


 2 - Passage en liste circulaire

   Jusqu'à maintenant la liblist (modules/liblist) implémentait la
   gestion de listes doublement chaînées classiques. La gestion de ces
   listes nécessitait de maintenir à la fois une tête et une queue, ce
   qui est un peu ennuyeux si l'on a une solution avec laquelle ce
   n'est pas nécessaire. C'est la raison pour laquelle nous avons
   modifié liblist pour implémenter des listes doublement chaînées
   circulaires.

   Cette gestion est implémentée par des macros, ce qui évite d'avoir
   à caster comme c'est le cas pour les splaytrees.

   Les fonctions disponibles sont :
     - list_init(list,item) permet d'initialiser la liste 'list' avec
       le premier élément 'item'.
     - list_insert_before(before_this,item) insère l'élément 'item'
       juste avant l'élément 'before_this'
     - list_insert_after(after_this,item) insère l'élément 'item'
       juste après l'élément 'after_this'
     - list_add_head(list,item) insère l'élément 'item' en tête de la
       liste 'list'.
     - list_add_tail(list,item) insère l'élément 'item' en queue de la
       liste 'list'.
     - list_delete(list,item) supprime l'élément 'item' de la liste
       'list'
     - list_for_each(list,iterator,nb_elements) permet de créer une
       boucle dans laquelle le 'iterator' pointe successivement vers
       tous les éléments de la liste 'list'. Le paramètre
       'nb_elements' est une variable contenant à la fin de la boucle
       le nombre d'éléments parcourus. Cette dernière variable est
       obligatoire.

   Pour chacune de ces fonctions on dispose de l'alternative avec un
   suffixe _named permettant de gérer des listes dans lesquelles les
   pointeurs vers l'élément suivant et l'élément précédant ne
   s'appellent pas next et prev. Se reporter à
   modules/liblist/liblist.h pour plus de détails.

   Le plus gros travail concernant ce point à été de modifier
   l'ensemble des modules pour utiliser la nouvelle gestion de liste
   chaînée.


 3 - Compilation avec -fomit-frame-pointer, sans plantage à l'éxécution

   Par défaut, au début de chaque fonction, gcc introduit les
   instructions suivantes :
	push %ebp
	movl %esp, %ebp
   Et introduit l'instruction leave à la fin de chaque fonction.

   Ceci permet de maintenir dans %ebp un pointeur sur la pile dans
   l'état ou elle était au début de la fonction. Ceci lui est utile
   pour aller chercher les paramètres de la fonction empilée dans la
   pile. Toutefois, il peut se débrouiller en utilisant directement
   des calculs sur le esp courant, sans utiliser ebp. Ceci est
   possible grâce à l'option -fomit-frame-pointer, et permet :
	- d'économiser deux instructions à chaque début de fonction,
          et une instruction à chaque fin de fonction. Ceci peut
          paraître ridicule mais étant donné le nombre d'appels de
          fonction, ceci peut être intéressant.
	- d'utiliser ebp comme un registre de travail pour réaliser
          des optimisations (utilisation des registres pour certaines
          variables au lieu de la mémoire).

   L'utilisation de l'option -fomit-frame-pointer a nécessité la
   modification du fichier modules/task-x86/_cpl0_switch.c. Ce fichier
   contenait deux fonctions en assembleur inline pour switcher entre
   threads. Toutefois, gcc ne permettait pas de spécifier esp en tant
   que cloberred register, et nous étions donc dans l'impossibilité de
   réaliser ces fonctions en assembleur inline. Nous avons donc
   remplacé le fichier .c par un fichier .s, ce qui a permis de gérer
   manuellement l'utilisation des registres.

   La compilation avec -fomit-frame-pointer économise un registre et
   l'éxécution de quelques instructions, mais ne permet plus le
   backtracking. Cependant nous pouvons toujours compiler sans cette
   option, et ainsi utiliser éventuellement le backtracking (qui reste
   à implémenter). Le backtracking permettrait de savoir quelle est la
   suite d'appels de fonctions qui a conduit là on on se trouve (très
   utile pour le debugging).

   Ces trois premiers points ont constitué la phase de
   proprification-amélioration du code source existant.


 4 - Gestion de la mémoire virtuelle

   Le brainstorming sur la VMM du début du mois d'aout (réunion
   Méridon) n'avait pas donné lieu à du coding. Durant ce WE, nous
   avons poursuivi notre réfléxion, concernant :
	- le partage de virtual_region_t entre différentes team
	- le partage de PTs
	- l'implémentation orientée-objet
	- les liens unissant team/address space/virtual region/shadow
          resource/resource
   et entamé l'implantation.

   Address space : cette nouvelle entité est placée entre la team et
   l'arbre des régions virtuelles. Elle permet de bien séparer la team
   (du ressort du module task) de l'ensemble des régions virtuelles
   (du ressort du module vmm).

   Partage de virtual_region_t : Hlide nous avait proposé (via une
   discussion Icq) de partager les virtual_region_t entre différents
   address space, afin d'éviter les surcoûts induits par les recopies
   lors d'un fork. Nous avons beaucoup réfléchi sur le sujet, envisagé
   différentes solutions, mais finalement il s'est avéré que ce
   partage n'est pas possible car chaque virtual_region_t contient un
   pointeur vers l'address space qui la contient. Or ce pointeur est
   unique (ce n'est pas un tableau de pointeur) et donc une
   virtual_region_t ne peut se trouver à un instant donné que dans un
   seul address space.  Il est clair que nous avons besoin d'un
   pointeur vers l'address space dans chaque virtual_region_t, pour
   savoir dans quel memory context (PD/PT...) il faut mapper la page
   qui a provoqué un page fault...  La seule solution trouvée pour le
   moment est de recopier l'arbre des virtual_region_t durant le fork.

   Partage de PT : étant donné que nous maintenons pour chaque page
   physique l'ensemble de ses mappings en mémoire virtuelle
   (l'ensemble de PTE la désignant), nous avons besoin de limiter le
   nombre de PTE pointant sur une même page physique. Le partage de PT
   permet de répondre à ce souci.
   La shadow resource maintiendra deux listes de virtual_region_t. La
   première liste contiendra les virtual_region_t mappant la shadow
   resource sur un espace où elle est seule (région virtuelle seule
   sur une zone multiple de 4Mo). On peut alors utiliser directement
   les PT de cette virtual_region pour mapper de nouveau le meme
   objet.  La deuxième liste contiendra les virtual_region ne
   correspondant pas à cette contrainte.

   Le mapping de ressource va se dérouler comme suit :
	- trouver une zone libre dans notre address space
          (vérification overlapping)
	- négocier avec la shadow resource pour trouver éventuellement
          une virtual_region_t existante, correspondant à nos besoins,
          afin de partager les PTs
	- créer la nouvelle région virtuelle (vr_new)
	- ajouter la région dans l'address space (as_add_vr)

   Droits d'accès :
   Pour ne pas avoir à splitter une région en deux lorsque l'on change
   les droits d'accès sur une portion d'une région, nous avons
   introduit dans chaque virtual_region_t un arbre de
   access_range_t. Chacun des éléments de cet arbre définit les droits
   d'accès maximaux pour la portion de région [node.key (start), end].

   L'implémentation orientée objet :
   Le modèle objet de la mémoire virtuelle est présenté dans le
   fichier doc/vm_model.eps. (Le source doc/vm_model.dia est lisible
   via le logiciel dia).

   Au niveau de l'address space, on dispose d'une série de fonctions
   permettant :
     - d'initialiser un address space relativement à une team donnée
     - de supprimer le contenu d'un address space
     - de trouver la région correspondant à une adresse virtuelle donnée
     - de dupliquer un address space
     - d'ajouter, de supprimer et de redimensionner une région de
       l'address space
     - de gérer une page fault reçu dans l'address space courant

   Au niveau des régions, on dispose d'une série de fonctions
   permettant :
     - de créer/supprimer une région
     - d'afficher les informations concernant une ou l'ensemble des
       régions
     - de gérer le page fault

   Chaque region dispose d'un pointeur vers un driver, ce qui permet
   de spécialiser le comportement d'une virtual region en fonction de
   sa nature. Chaque driver doit implanter les méthodes
   d'initialisation/désinitialisation, de notification de remappage en
   mémoire, et de notification de swap.

   De la même manière chaque shadow resource possède un pointeur vers
   un driver permettant de spécialiser le comportement lorsque l'on
   reçoit un page fault, lorsque l'on a besoin de lire ou écrire sur
   la ressource mappée en mémoire. La gestion des shadow resource
   reste à mettre en place.

   Pages anonymous : afin de partager au maximum les pages dites
   anonymes, SunOS utilise pour chaque virtual_region_t un tableau de
   pointeurs vers les pages anonymous de la virtual_region. Or, avec
   notre système de reverse mapping, nous sommes directement capable
   lors du remapping (après swap par exemple) d'une page en mémoire de
   la remapper à TOUS les endroits où elle était mappée. Nous pouvons
   donc nous passer de gestion de page anonymous. Donc, contrairement
   au fonctionnement de la VM SVR4, ceci permet de découpler la partie
   shadow_resource/virtual_region de la gestion du swap.


   Il reste donc à implémenter (pour que le système fonctionne de
   nouveau) :
	- la gestion des shadow resource
	- la création d'un équivalent à /dev/kmem pour mapper la zone
          noyau. Nous avons identifie qu'il faut 2 versions du page
          fault de la shadow resource suivant que la page fault
          provient du cpl3 (=> recopie de la zone noyau) ou du cpl0
          (allocation de page physique).
	- la création d'une sorte de shadow resource /dev/kstack ou
          équivalent pour gérer la région de piles noyau de supportant
          aucun page fault

   Puis :
	- reverse mapping
	- partage de PT
        - shadow resource /dev/zero
	- fork : ce sont les fonctions de gestion des shadow resources
  	  qui font l'essentiel du travail sur le plan algorithmique en
          cas de création d'un mapping en MAP_PRIVATE (passage de tous
	  les mappings de la zone en read-only), puis en cas de page
	  fault sur une zone ou un mapping MAP_PRIVATE existe
	  (différenciation).
	- régions de type MAP_PRIVATE / MAP_SHARED avec le COW, etc...



Bonne journee,

-- 
d2