[Kos-dev] DSR du commit de Thomas

[David Decotigny]

Hello,

Thomas vient de faire un commit pour rajouter les "DSR". Dans ce
commit, un "DSR" est un handler analogue au handler d'IRQ normal, sauf
qu'il est execute alors que les interruptions sont activees ("sti"
avant).

Le code me parait correct. Mais c'est pas tout a fait comme ca que
j'imaginais les choses. Comme c'est qqch qui peut cependant s'averer
utile, c'est a garder a mon avis. Je dirais meme que ce qui suit peut
pleinement tirer parti des "DSR" du commit en question.

Dans le commit en question, donc, le "DSR" est contigu a l'"ISR
normal", sachant que les interruptions sont reactivees ("sti") entre
les 2. Ce DSR va donc commencer 999999 fois sur 1000000
*immediatement* apres la partie non-interruptible. Le 1 cas sur
1000000 restant correspond au cas ou une irq plus forte est levee
entre le "sti" et le "call". Bref, 999999 fois sur 1000000, le terme
"deferred" dans "DSR" n'est pas verifie.

En fait, par "DSR", je pensais a qqch de plus proche de ce que
j'appelais "Bottom-Half" (voire "wait queue" Linux), et qui
correspondrait mieux au sens de "deferred" dans "DSR". Ca completerait
le commit de Thomas : ca rajoute un etage "vrai" DSR. On aurait :
  - ISR normal
  - le "DSR" du commit en question
  + L'etage supplementaire ("vrai" DSR) qui a les memes proprietes que
    le DSR de Thomas (ie interruptible non bloquant), mais qui est
    execute uniquement a la fin de l'ISR *la plus externe* =>
    "deferred".

Comme dit, le caractere "deferred" provient du fait que les "vrais"
DSR seraient executes a la chaine par la fin de l'interruption la plus
externe, ie leur commencement d'execution serait "retardee" en cas
d'imbrication d'interruptions.

Pour que ce soit plus clair, je pense que le mieux est de renommer
tout ca :
  - ISR normal -> "clISR" ("cli" + "ISR")
  - le "DSR" du commit en question  -> "stISR" ("sti" + "ISR")
  - "vrai" DSR (equivalent BH ou Wait Queue Linux) -> "DSR"

Techniquement, les dsr_handler sont geres sous forme de files a
priorite : on aurait DSR_LEVELS files (par exemple 32 ou 64 ou 4 ou 2
ou 1 ou...). Ca veut dire que j'ai DSR_LEVELS listes (ou tableaux ; a
voir) d'elements du type :

------------------------------------
  struct dsr_s {
     void (*routine)(int dsr_q, void *data);
     void *data;
     struct dsr_s *next, *prev; /* Liste circulaire */
  };
------------------------------------

(Ou alors un tableau de taille fixe si on veut eviter de kmallocer les
elements de la liste)

Et ces DSR_LEVELS files sont stockees dans qqch comme :

------------------------------------
  #define DSR_LEVELS 42 /* Par exemple */

  struct dsr_queue_s {

    unsigned char bitmap[ALIGN_SUP(DSR_LEVELS, CHAR_BITS) / CHAR_BITS];
    /* Un bit a 1 signifie que au moins 1 dsr est inscrit sur cette
       liste */

    struct dsr_s *level[DSR_LEVELS]; /* liste circulaire */

  } dsr_queue; /* Variable globale : 1 par processeur */
------------------------------------
(Pour la def de "CHAR_BITS", voir notes de fin de mail)

Cote algorithmique, on a besoin de :

  - int add_dsr(int dsr_level,
                void (*routine)(int level, void *data), void
                *data));
    => (0 si Ok, -1 si errreur)
       Se charge de mettre a jour le bitmap + insere le nouveau dsr en
       queue de la liste dsr_queue.level[dsr_level].

  - struct dsr_s * pop_dsr(int dsr_level);
    => Se charge de mettre a jour le bitmap + enleve le dsr en tete de
       la liste dsr_queue.level[dsr_level].

Puis cote interruption, le principe est le suivant (schematique) :

------------------------------------
  isr:
       hw_isr_nested_level ++
       save_context

       call clISR /* "ISR normal" */

       send_EOI
       push hw_isr_nested_level /* TRES important */

       sti
       call stISR /* "ton" DSR */

       if (pop eax == 1) /* C'etait l'irq la plus externe */ {
         /* ^
          * \--- Ce pop eax a pour but de recuperer le push
          * hw_isr_nested_level fait plus haut. Il ne faut pas
          * utiliser directement hw_isr_nested_level
          */
         call spawn_dsr /* Execution des DSR */
         /*
          * *TRES IMPORTANT* Retourne avec les interruptions
          * desactivees : "cli" implicite
          */
       } else
         cli /* TRES important */

       restore_context /* eventuellement nouveau contexte */
       hw_isr_nested_level --
       iret
------------------------------------

Avec :

------------------------------------
/* *TRES IMPORTANT* Retourne avec les interruptions desactivees :
   "cli" implicite */
spawn_dsr() {
  cli();
  while (1) {
    struct dsr_s *dsr;
    int toplevel = bsf_bitmap(& dsr_queue.bitmap, sizeof(dsr_queue.bitmap));
    if (toplevel >= DSR_LEVELS)
      break; /* Plus de DSR en attente */
    dsr = pop_dsr(toplevel);
    if (!dsr || !dsr->routine)
      continue;
    sti();
    dsr->routine(toplevel, dsr->data);
    cli();
  }
}
------------------------------------

L'interet de tout ca ? Ces DSR permettent de serialiser certains
traitements, ce qui evite d'avoir a prendre des precautions pour la
protection de certaines donnees globales accedees uniquement dans les
DSR. Ca complete la version DSR de Thomas, en la rendant plus fidele
au sens de "Deferred". Le but de la manip est donc de retomber sur ses
pied quant au vrai sens de "deferred".

Avant d'ecrire ca, je me suis demande si il serait possible de partir
des DSR de Thomas pour faire des "vrais" DSR (sous la forme de
fonctions speciales de gestion de listes de routines). Mais je me suis
heurte a plein de petits details de synchro, et c'est pour ca qu'on se
retrouve avec un etage supplementaire.

Remarque 0 : ce mecanisme est extensible en SMP (tablequ de dsr_queue)..

Remarque 1 : avec ce mecanisme, on peut par exemple mettre reschedule
sous forme d'un DSR de plus faible priorite. Ainsi, le prochain thread
a executer serait toujours determine en tout dernier lieu, a la suite
de la toute derniere interruption la plus externe. Le probleme, c'est
alors de savoir comment recuperer le contexte a executer depuis un
DSR. Le mieux est sans doute d'avoir une variable globale qui
s'appelle "next_cpu_context" (tableau en SMP), qui est positionnee par
le reschedule, et qui constitue le prochain contexte a mettre avant le
"iret".

Remarque 2 : Si on choisit de faire comme la remarque 1 le suggere, on
se heurte a un autre probleme de taille : dans ce cas, entre le
reschedule et le iret, il peut tres bien y avoir un autre DSR qui
provoque un #DF de pile !!!! Et donc notre hypothese forte sur "pas de
#DF entre la fin du reschedule et le iret" n'est plus verifiee =>
probleme.

Voila encore de quoi s'occuper.

Bonne journee,

Notes :
  CHAR_BITS : il faudrait definir cette macro dans types.h par exemple
              (c'est une macro standard en C). Elle indique le nombre
              de bits par type "char". Sur certaines architectures, ca
              vaut 16. Dans notre cas, ca vaut 8. On peut aussi
              utiliser cette macro dans tout ce qui est lib-x86.c,
              bien que ca ne soit pas la peine puisque c'est x86
              specific et que sur x86, CHAR_BITS vaut forcement 8. Mais
              ca serait plus propre.

-- 
David Decotigny