[Kos-dev] Reentrance de reschedule : un solution ?

[d2]

Hello,

J'ai lu tes idees sur le site Web. Ca fait un moment que l'idee
d'angliciser le site web me trote aussi dans la tete : au moins la
presentation, les news et les docs. Mais bon, manque d'envie pour
ca. Mais sur le principe, d'accord.

>>>>> "Thomas" == Thomas Petazzoni <thomas.petazzoni@ifrance.com> writes:
    Thomas> Avec d2 on avait eu l'idee que lorsque la taille de la
    Thomas> pile restante devenait trop critique pour un thread (genre
    Thomas> trois ou quatre pages avant qu'il arrive a la limite), on
    Thomas> le place a l'etat DELETED, pour qu'il ne soit plus elu, et
    Thomas> que notre cher kgc se charge de le virer.

C'est vrai.

    Thomas> mais le hic avec ca, c'est que si l'adresse de la pile est
    Thomas> completement fausse subitement (a cause d'un thread pas
    Thomas> gentil, comme les threads stack_fault), bin alors la on
    Thomas> sait pas quoi faire.

On est en cpl0 : les mecs qui ecrivent du code ne sont pas autorises a
ecrire n'importe quoi, ou a faire n'importe quoi sans verification. Si
il arrive que le mec touche a la main a la pile, ou si il met des
structures char[1024*1024] sur la pile, c'est tant pis pour le
systeme. Il y a un minimum de rigueur a avoir quand on ecrit du code
cpl0. C'est pas le role de l'OS de contourner les (grossieres) erreurs
du programmeur de l'OS.

    Thomas> si un thread atteint une limite de pile non acceptable, on
    Thomas> le passe a l'etat DELETED. mais attention ceci risque de
    Thomas> poser probleme si le nombre de threads est faible. je
    Thomas> m'explique.  on est dans le thread A, puis la
    Thomas> IRQ0. celle-ci fait un reschedule qui decide d'elire de
    Thomas> nouveau le thread A (car la politique de scheduling l'a
    Thomas> decide), puis apres avoir choisi ce prochain thread,
    Thomas> double fault.  si ce double fault conduit a une stack
    Thomas> overflow, le thread A va etre passe a l'etat DELETED, mais
    Thomas> vu que le reschedule a deja ete fait, mais il sera tout de
    Thomas> meme execute. bref on a une probabilite faible, mais non
    Thomas> nulle, que le thread A soit execute. donc notre solution
    Thomas> est bof. elle marchera dans 99.99% des cas, mais pas dans
    Thomas> les 0.01% restants.  - si un thread est completement out
    Thomas> de sa zone de pile, bin on arrete le systeme.

Bon, alors ce que tu crains, c'est le scenario suivant :

  thread A:
    ...
    ----------------
    | PAF: isr_clock :
    |   ...
    |   next_thread = current = reschedule(); // current <- thread A
    |   ...
    |   --------------------
    |   |  PAF: #DF
    |   |  ...
    |   |  thread A->state = DELETED;
    |   |  current = reschedule(); // current <- thread B
    |   |  IRET
    |   --------------------
    |   ... // retour dans isr
    |   switch_stack_vers_next_thread(); // stack <- stack thread A
    |   IRET;
    ----------------
    RETOUR dans thread A, or thread A->state == DELETED !!!!

C'est ca que tu crains ?

Je vois bien une solution : c'est de garantir que :

  « NI reschedule(), NI ce qui vient apres (cad avant le IRET de
    l'isr) n'utilisent PLUS ("plusssssse") de pile que ce qui
    precedait dans l'ISR »

Comme ca, on est assure qu'entre l'appel de reschedule() et la fin de
l'ISR (iret) on n'aura pas de #DF dus a un stack fault de l'ISR
(puisque tout aura ete mappe par avance). Ca necessite de savoir
combien de pile necessitent le reschedule() et ce qui suit dans
l'ISR. Une fois qu'on connait ca, il suffit de faire un
stack_top[-MAX_RESCHED_DEPTH] = 0 par exemple AVANT d'appeler
reschedule : comme ca on forcera le stack fault a avoir lieu avant le
reschedule().

Mais c'est pas beau comme solution (et chiatique si on se plante dans
l'estimation de la profondeur de pile necessaire), et c'est pas
franchement satisfaisant cote perfs (c'est toujours idiot de charger
une ligne de cache si ca sert a rien, et de faire 2 reschedules en
rafale : le premier dans le #DF, le 2eme dans l'ISR).

Autre methode proposee (plus srieuse)
-------------------------------------

Tout d'abord, il vaudrait mieux avoir au niveau des ISR, un truc du
genre :
  reschedule()
  switch_pile();
  iret
Et RIEN d'autre entre reschedule et iret. Avec un postulat important
sur switch_pile : il n'affecte pas la pile plus que reschedule le
fait. Donc, si #DF genant il doit y a avoir, il se situe dans le
reschedule et pas apres. Ca, ca parait pas trop complique a realiser.

Ensuite, il est a noter que le reschedule() n'est pas appele que par
l'ISR clock : mais plutot par toutes les ISR, voire certaines
exceptions (#PF quand il y a blocage pour aller chercher une page
swappee par exemple). Bref, on va retrouver ce probleme a d'autre
endroits. Reste a identifier le probleme. Ce "probleme" est la
reentrance de reschedule.

En gros, puisque de toutes facons on manipule/modifie des donnees
globales, ca pose un probleme lorsque le #DF arrive a l'interieur du
reschedule : il va lui-meme faire un reschedule. Par consequent,
lorsqu'on reviendra dans l'ISR, on peut renvoyer un thread qui a ete
mis en DELETED par le #DF. Bref, c'est pas bon : il faut s'interesser
a la reentrance de reschedule().

Alors voila une solution :

static int in_reschedule = 0;            // globale
static int dont_need_another_reschedule; // globale (pas d'init necessaire)

  /*
   * Le vrai reschedule.
   * Ca peut etre une fonction a part comme ici, ou etre
   * integre directement dans reschedule() plus bas
   */
  inline static cpu_context * algo_reschedule(cpu_context *orig) {
    // On fait l'ordonnancement sans s'occuper des pb de reentrance
  }

  /*
   * Le reschedule appele par les ISR, par le #DF et par tout le
   * reste...
   */
  cpu_context *reschedule(cpu_context *orig) {
    cpu_context *res;

    if (test_and_set(in_reschedule)) // Ce qui compte est l'atomicite
                                     // du test & set vis a vis de la
                                     // pile, pas forcement des
                                     // instructions processeur (ie #DF doit
                                     // etre impossible entre le test et
                                     // le set, c'est tout)
    {

      // If we're here, it means that we are interrupting another
      // reschedule() => This one does nothing, but signals the
      // interrupted reschedule() that it must recompute its result
      // (namely because calling reschedule() means "I've changed
      // something, please take it into account)

      dont_need_another_reschedule = 0;
      return orig;
    }

    // Un #DF ici n'est pas genant

    do {
      dont_need_another_reschedule = 1;
      // Un #DF entre ici et le while sera pris en compte
      res = algo_reschedule(orig);
    } while (! test_and_set(dont_need_another_reschedule));
    // Entre la fin du while et l'instruction suivante : pas de #DF
    // possible (pile non utilisee)
    in_reschedule = 0;
    return res;
  }

Si je compte : ca fait 8 lignes de code de plus que "return
algo_reschedule()".

Le principe, c'est de relancer le reschedule() de plus bas niveau
(typiquement : dans ISR) quand on se rend compte qu'il a ete
interrompu par un autre reschedule() de plus haut niveau (typiquement :
dans #DF). En plus, le reschedule() de plus haut niveau fait le
minimum (ie ne fait pas un vrai reschedule avec parcours de la liste
des taches, ...) : il signale juste qu'un reschedule() doit etre
redemarre au plus bas niveau.

Voila, comme ca, on a resolu le pb de la reentrance de reschedule. En
rapprochant le reschedule du switch_stack et de l'iret, on resoud le
probleme de #DF *apres* le reschedule (impossible puisque la stack a
deja ete utilisee avant par le reschedule, donc est dispo).

Le test_and_set() peut etre l'instruction "bts" (ia32). Vu que "bts"
travaille au niveau du bit, on peut meme reunir les 2 variables
in_reschedule et dont_need_another_reschedule dans le meme mot
memoire. Cependant, un test and set machine n'est pas vraiment
necessaire : il suffit juste de ne pas consommer de pile entre le test
et le set. On peut donc aussi s'en sortir avec de l'assembleur non 386
("inc" tout bete + test eflags).

Sinon, il y a moyen de s'en sortir avec d'autres operations atomiques
vis a vis de la pile (des xchg entre autre). Mais bon, c'est une
affaire de gout.

Voila les 2 solutions que je vois. Je trouve la 2eme bien meilleure
(plus belle). Mais comme j'ai pas teste, et que les problemes poses
sont vraiment tres fins, faudrait s'assurer que c'est Ok. En SMP,
c'est encore un autre bordel : il faut s'occuper de la reentrance au
niveau de chaque processeur : pas globalement sur tous les
processeurs. Donc il faut un moyen d'identifier le processeur qui est
dans le scheduler, et egalement sur quel processeur il faudra "another
reschedule". C'est plus complique.

Bonne journee,

-- 
d2