[Kos-announce] Nouveautes de la semaine

[d2]

Bonjour,

Durant la semaine passee, Julien, Thomas et moi nous sommes reunis
chez Thomas pour faire avancer KOS. Au programme : codage,
uniformisation, blindage du coeur de l'OS et brainstorming (Babel et
VMM).

Grand Merci a lui et a ses parents pour l'agreable sejour que nous
avons pu passer ensemble a (entre autre) coder KOS et a ecouter du
Mozart. Ca a ete une semaine productive, tant sur le plan des
realisations, que sur le plan du design du coeur de l'OS. Des docs
(Babel + gestion des interruptions) devraient suivre.

Quand on essaye KOS tel quel (recup source + compilation ou image
disquette), on ne remarque pas de nouveaute neuve nouvelle a
l'ecran. Mais il faut savoir que le test effectué en arriere plan
(invisible a l'ecran sauf quand une erreur se produit) est assez
violent :
  - 20 threads cpl0 qui font 2000 campagnes d'allocation/deallocation
    aleatoires de 1234 elements de taille aleatoire comprise entre 4
    et 2048 octets chacune, avec usleep() aleatoire entre chaque
    campagne. Permet de tester intensivement la gestion de la memoire
    noyau, et la synchronisation.
  - 1 paire de threads cpl0 producteur/consommateur utilisant les
    primitives de kmsg. Le producteur est lance toutes les secondes.
  - 1 DSR "marqué" a chaque interruption clavier
  - 1 paire de DST bloquants associes au timer, synchronises par kmsg
  - 2 threads cpl0 de twidlle (les 2 caracteres rouges a l'ecran)
  - 2 threads qui ne font rien (terminent immediatement)
  - 1000 interruptions timer par seconde (HZ=1000) + twiddle (caractere
    bleu en haut a droite)

Pour les termes obscurs (DST, DSR, kmsg, ...), voir ce qui suit.

Si vous voulez tester, 40M de RAM minimum sont recommandes. Sinon vous
aurez droit a un :
  [get_physical_page_unsafe@_pmm.c:71] **** System Halted **** :
  No more physical memory
Vers le debut.

Bochs n'est pas le meilleur choix pour tester : tres lent, et vous
aurez l'impression que les ticks d'horloge deviennent de plus en plus
lents. Utilisez un ordinateur reel avec debug sur ligne serie, c'est
plus rapide et moins "surprenant".

Thomas a redige le compte-rendu plus detaille ci-dessous.


Compte rendu semaine KOS 
------------------------

Une semaine de développement KOS s'est déroulée du vendredi 27 juillet
au 5 aout, avec Julien, David et moi-même. Jérome et Estelle sont
venus voir l'avancée du développement et nous apporter leurs
suggestions le dernier jour.


Travaux réalisés
----------------

1 - Scheduler : reorganisation (toujours du round-robin)
  Découpage du module scheduler en plusieurs fichiers, en respectant
  les usages dans le nommage des fichiers. Trois parties composent ce
  scheduler : _timer.c qui contient le handler de l'IRQ timer,
  _scheduler.c qui s'occupe d'élire un nouveau thread (fonction
  reschedule_unsafe), et de relancer un nouveau thread (fonction
  rechedule_next). Une fonction reschedule_after_interrupt est aussi
  présente, et elle est appelée après chaque IRQ (voir plus loin). Le
  fichier _sleep.c contient les primitives nécessaires à la gestion de
  la fonction usleep().

2 - task-x86 : problemes de synchro
  Découpage du module task-x86 en plusieurs fichiers. La partie
  gestion des TSS qui faisait auparavant partie de mm-x86 est
  maintenant dans task-x86 (fichier _tss.c). Modification des
  cpl0_switch_context pour qu'ils ne fassent pas le 'sti' brute force
  (trop bourrin avec les spinlocks).

3 - IDT : DSR et DST
  Réécriture quasi complète de la gestion de l'IDT. Les "prehandlers"
  se trouvent dans _idt.S, la gestion du (ou des syscalls) est dans
  _syscall.c (le syscall existe mais ne fait presque rien). La gestion
  des irq dans _irq.c, la gestion des exceptions dans
  _exception.c. D'autre part la partie spécifique au i8259 a été
  placée dans un fichier a part (_i8259.c). Grande nouveauté : les DSR
  et DST.

  DSR : Deferred Service Routine, plus ou moins équivalents aux
        tasklets de Linux (noyau 2.4) ou aux bottom half (noyau
        2.2). Les DSR sont des fonctions qui sont éxécutées après le
        traitement de la dernière IRQ la plus externe (lors de
        l'éventuelle imbrication d'IRQ), et ce avec les interruptions
        activées. Nous avons actuellement 42 niveaux de DSR, avec pour
        le moment une fonction par niveau. La fonction de niveau 0
        étant éxécutée avant la fonction de niveau 1. Ces fonctions
        sont éxécutées avec les interruptions activées sur le
        processeur courant. Deux DSRs différents peuvent s'éxécuter
        simultanément sur plusieurs processeurs, de même que le même
        DSR peut s'éxécuter simultanément sur plusieurs processeurs.

  DST : Deferred Service Thread, plus ou moins équivalents aux
        softirqs de Linux 2.4.7+. Lorsque le traitement à faire après
        une interruption peut etre bloquant (attente sur ressource),
        il convient d'utiliser un DST plutôt qu'un DSR, car
        l'utilisation d'un DSR pénaliserait le thread qui aurait reçu
        l'IRQ pour un temps assez long (attente sur ressource). Les
        DST sont donc des threads, actuellement au nombre de 16 (16
        niveaux). Chaque thread peut éxécuter un nombre illimité de
        'jobs'. Deux jobs d'un niveau différent peuvent s'éxécuter en
        même temps sur des processeurs différent, mais deux jobs d'un
        même niveau ne peuvent s'éxécuter en même temps sur des
        processeurs différent.

  Nous allons prochainement écrire une documentation expliquant
  précisement l'implémentation de la gestion des interruptions.

4 - KITC : ksignal et kmsg
  Un nouveau module kitc a fait son apparition : Kernel Inter Thread
  Communication. Il contient des primitives de communication inter
  thread RESERVEES au noyau. Ces primitives sont donc simples, mais
  aussi rapides. On a _ksignal.c qui implémente des fonctions
  permettant à un thread de bloquer tant qu'un autre thread n'envoie
  pas un signal. _kmsg.c implémente une gestion de boites aux lettres
  (ports) de base, reposant sur ksignal.

5 - Module kos : headers globaux dans <kos/*.h>
  Création d'un module kos, contenant wolfgang.c (partie principale du
  noyau), et tous les .h qui étaient en bazar dans modules/. Le module
  wolfgang a donc été supprimé.

6 - Module bootstrap : init levels + suppression de l'identity mapping
  Un nouveau module bootstrap qui se charge de supprimer l'identity
  mapping qui n'est plus nécessaire, puis d'initialiser les
  modules. Ce n'est donc plus kos_main dans kos/wolfgang.c qui est le
  point d'entrée du noyau pour le loader, mais la fonction
  kernel_bootstrap dans le module bootstrap. D'autre part,
  l'initialisation des modules a été repensée : on peut avoir
  plusieurs init_module par module : il y a des 'init levels'. Tous
  les init_modules de level 0 sont éxécutés, puis tous les
  init_modules de level1, puis tous les init_modules de level3 ... Ceci
  permet de supprimer certaines contraintes que nous avions concernant
  l'ordre d'initialisation des modules. Les levels sont définis dans
  loader/mod.h

7 - kmem : Tout repose sur kslab
  Réécriture du module kmem (non terminé, il manque
  kslab_cache_destroy). L'utilisation de slab est toujours à l'ordre
  du jour, mais la nouvelle implémentation se rapproche de celle
  proposée par Bonwick, et utilisée dans SunOS. On utilise des listes
  chainées de blocs libres (sans avoir a les parcourir) plutot que des
  bitmaps, ce qui est finalement plus simple et nettement plus
  rapide. De plus, on peut maintenant avoir de cache avec des blocs de
  grande taille, car les slabs peuvent faire plusieurs pages. Ce
  module a été testé via _kmem_test.c.

8 - liblist
  Finition de liblist. Cette librairie (un .h) est un ensemble de
  macros pour gérer simplement des listes chainées. Très pratique,
  nous l'utilisons au maximum dans le système. Toutefois, nous
  envisageons sous peu de passer à des listes circulaires.

9 - loader : bootmem + exportation de variables + modules 'ar'
  Relecture et correction de bugs mineurs dans bootmem (allocateur de
  mémoire du loader). Possibilité d'exporter des variables entre les
  modules. Toutefois ceci ne doit être utilisé que dans les cas
  extremes (ex : spinlock). Correction de bugs sur l'ordre
  d'initialisation des modules qui étaient inversés lors du
  désarchivage d'une archive ar. Tous les modules sont maintenant
  regroupées dans une archive ar, gzippée ou non. C'est plus rapide à
  charger avec Grub.

10 - Synchronisation : blindage + anticipation SMP
  Grosses reprises de code concernant la synchro : nous avons revu
  tous les spinlocks dans tous les modules, pour corriger de nombreux
  problemes de synchro. Nous avons tenu compte du multi processing
  (même si celui ci n'est pas encore implémenté dans KOS). Ces
  reprises concernent notamment le module idt, scheduler, kitc mais
  aussi les modules de gestion de la mémoire (pmm, kmem). Les
  deadlocks canoniques (appeles 2 fois de suite un lock sans unlock
  intermediaire) sont detectables (macro __DEADLOCK_CHECK__ du config.h).

11 - Babel
  Ce collecteur d'interfaces et d'instances avance bien. Le module
  babel contient un fichier babel.h donnant les structures de base de
  tout objet Babel. La sous partie tower est le collecteur
  d'interfaces en lui meme. La sous partie syscall s'occupera plus
  spécifiquement de recevoir et de gérer les syscalls. La sous partie
  resource est destinée à définir ce qu'est la resource de base.

  Pour résumer brièvement, Babel permet d'enregistrer des interfaces,
  et d'instancier ces interfaces. Ainsi, on peut enregistrer
  l'interface disk_ide, et créeer deux instances ide_disk_0 et
  ide_disk_1 correspondants à l'interface. On appelle aussi ces
  interfaces des services, et elle peuvent être organisée en classes
  de services. Par exemple la classe de service disk définira des
  méthodes telles que read,write,format,etc... mais ne sera pas
  instatiable. Seul un service tel que disk_ide héritant de la classe
  de service disk et proposant au minimum les méthodes de la classe de
  service disk et éventuellement d'autres pourra être instancié. Les
  classes de services correspondent en quelque sorte à des classes
  abstraites, les services à des classes, et les instances à des
  objets.

  D'autre part, nous avons introduit la notion de ressource. Une
  ressource est propre a chaque team. Elle peut représenter n'importe
  quoi : un fichier, une socket, une carte son, un disque dur, un port
  d'IPC, etc... Chaque ressource est liée à un instance de service,
  via un lien appelé translator. Ces ressources sont créés lors d'un
  open, et peuvent donc être comparées aux file descriptors sous
  Unix. Toutefois la ressource n'est pas vue comme un fichier, mais
  plutôt comme un objet sur lequel on peut appliquer les méthodes du
  service lié par le translator.

  Cette nouvelle notion de ressource, dont nous avions déjà discuté
  sur la mailing list kos-dev nous a permis de bien comprendre comment
  allait fonctionner globalement le système, de l'appel open() du
  programme utilisateur à l'éxécution du bon open du bon service dans
  le noyau.

12 - Brainstorming VMM
  Gestion de la mémoire virtuelle. Sur ce point ci, nous avons
  progressé durant cette semaine. Nous allons implémenter un système
  assez classique, ala SVR4.

  Dans KOS, les régions virtuelles contiendront :
	- un pointeur vers une shadow ressource représentant la
          ressource mappée en mémoire (fichier, disque dur, frame
          buffer)
	- une adresse virtuelle de base, et une taille
	- les protections maximales de la region
	- le type de partage { PRIVATE, SHARED }
	- des pointeurs vers un ensemble de méthodes :
          page_fault_handler, is_swappable, swapout_notification,
          swapin_notification. Ces méthodes sont différentes pour
          chaque type de région virtuelle (cf précédent mail dans
          kos-dev).

  Comme précisé dans la partie 11, une ressource correspond
  globalement à un descripteur de fichier ouvert : si plusieurs team
  ouvrent le même fichier, il y a alors une ressource par team pour ce
  même fichier. Derrière cette ressource se trouve une shadow
  ressource, unique pour chaque fichier, frame buffer, disque dur,
  etc...

  Lorsqu'un appel open() est réalisé, si la 'shadow resource' existe
  déjà, alors on créé simplement une ressource pointant vers cette
  shadow resource, sinon on créé la shadow resource et une
  ressource. La ressource permet de maintenir les informations propres
  à l'état de cette ressource pour la team qui l'appartient (position
  dans le fichier...), tandis que la shadow resource permet de
  maintenir des informations globales à toutes les teams, utiles pour
  la gestion de la mémoire virtuelle. Chaque segment de mémoire
  virtuelle est lié à une shadow resource, et non directement à une
  resource.

  Une shadow resource permet de maintenir les informations liées aux
  différents mappings de la ressource concernée. Il y aurait donc une
  liste des régions virtuelles associées à cette shadow resource. Un
  page fault qui intervient sur une région virtuelle fait appel au
  driver de cette région virtuelle, qui pourra alors utiliser la
  shadow resource pour charger des données en mémoire.

  Les entités shadow resource/virtual region/address space et les
  différents drivers de segments semblent suffisantes pour implémenter
  la gestion de la mémoire virtuelle.

  En ce qui concerne le swapping, nous n'allons pas comme sous Linux
  actuellement swapper des régions virtuelles. Nous allons raisonner à
  partir des pages physiques, ce qui implique pour chaque page
  physique de maintenir tous les mappings virtuels associés. Or
  maintenir ces informations peut devenir très couteux en terme de
  mémoire, et nous allons donc partager au maximum des PT entre
  différentes teams, afin de factoriser les reverses mappings.

  struct reverse_mapping 
  {
    pte_t *pte;
    struct reverse_mapping *next;
  };

  A noter que le pointeur vers le pte présent dans cette structure est
  un pointeur vers l'adresse du PTE en zone noyau, et non dans le
  mirroring. Pour utiliser au maximum le partage de PTs, les
  ressources mappées en mémoire seront le plus possible seules sur des
  espaces de 4Mo. Une fois que celà n'est plus possible, alors on
  mettra plusieurs ressources par zone de 4Mo, mais on perdra le
  partage des PT.

13 - utils/mod_check
  Le programme mod_check dans le répertoire utils/ checke en offline
  les dépendances entre les modules (détection des unresolved symbols)
  afin de ne pas attendre de booter Bochs ou une machine réelle pour
  le voir. Par ailleurs, ce programme permet de générer des graphes de
  dépendances avec 'dot' (package graphviz de ATT).

14 - config.h
  Les fichiers loader/config.h et modules/config.h permettent
  respectivement de changer la configuration du loader et des modules,
  notamment au niveau du debugging (DEBUG ON BOCHS, DEBUG ON CONSOLE,
  DEBUG ON SERIAL, etc..). Ils remplacent les variables du fichier
  MkVars.

15 - Dependances Makefile
  Generation des dependances .c->.h automatique

-- 
d2