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

[d2]

Hello,

>>>>> "Thomas" == Thomas Petazzoni <thomas.petazzoni@ifrance.com> writes:
    Thomas> bin disons que moi je pensais pas que DF ferait un
    Thomas> reschedule, mais admettons (encore que ce soit discutable
    Thomas> de faire un reschedule apres un DF, car le thread peut
    Thomas> etre relance directement. enfin bon si tu penses que c'est
    Thomas> mieux... je connais pas grand chose a tous ces problemes,
    Thomas> mais si tu pouvais expliquer les motivations poussant a
    Thomas> faire reschedule dans ton DF...).

Imaginons que le timer appelle reschedule, que ca entraine un
*mauvais* #DF (suppr du thread) : dans ce cas #DF fout le thread en
DELETED : il faut bien qu'a un moment ou un autre un reschedule soit
fait pour prendre en compte ce DELETED, et ceci *avant* le
"iret". Comme on sait pas ou le reschedule a ete interrompu, il faut
le relancer depuis le debut.

D'un autre cote tu as raison : c'est sur qu'on n'a pas besoin d'un
vrai reschedule dans le handler #DF. On a juste besoin de
"dont_need_another_reschedule = 0;". Mais bon, comme ca coute pas
beaucoup plus cher de rendre reschedule reentrant, autant le faire (ca
peut peut-etre servir dans d'autres cas bizarres).

    Thomas> tu oublies le set_current_thread, que reschedule ne fait
    Thomas> pas lui meme, justement pour eviter des problemes de
    Thomas> consistence. par exemple dans l'IRQ timer, le reschedule
    Thomas> est loin devant le iret, mais le set_current_thread est
    Thomas> juste avant.  quant au switch_pile y'a pas a s'en faire,
    Thomas> c'est fait par le pre handler du ISR (idtasm.S), et ca
    Thomas> fait un movl sur esp, pi plein de pop, donc la y'a plus
    Thomas> consommation de pile.

Voui. Faudrait regarder le coup du set_current de plus pres. Etudier
la question comme reschedule : doit-il etre appele dans le #DF ?...

    Thomas> a priori, je trouve que nous n'avions pas vraiment pris de
    Thomas> direction contraire a celle de l'implementation de la
    Thomas> memoire virtuelle proposee dans SunOS. qu'en pensez-vous ?

Je pense comme tu l'as dit plus loin que ca n'a rien de
revolutionnaire. Mais que ca permet de nous donner un peu de recul sur
ce dont on a besoin pour la liaison avec tout ce qui est disque, swap,
etc.. Personnellement, ca m'a permis d'y voir plus clair. C'est
surtout ca l'interet que j'ai vu dans ces docs.

    Thomas> Page 2, section 1.1.3 : "Cependant malgre l'aspect
    Thomas> preemptif du systeme du point de vue utilisateur, avec les
    Thomas> Unix classique, et en UP toujours : une fois en mode
    Thomas> noyau, le thread courant s'execute jusqu'a ce que le noyau
    Thomas> passe la main (blocage sur ressource). Cet aspect
    Thomas> multitache cooperatif..."

    -> Dans KOS, un thread noyau peut tout a fait etre interrompu par
    -> le
    Thomas> timer, et un autre thread (noyau ou utilisateur) peut etre
    Thomas> execute. En somme les threads noyau ou utilisateur sont
    Thomas> considérés comme des entites tres similaires, et dans les
    Thomas> 2 cas, le multitache est preemptif me semble-t-il...

Oui, avec kos, le noyau est preemptif en UP.

    -> Je ne comprends pas bien ton explication concernant ce type de
    Thomas> fonction et l'allocation implicite faite par le
    Thomas> compilateur. Pourrais-tu expliquer un peu de plus de
    Thomas> manière a ce que je comprenne pourquoi cela est genant
    Thomas> pour la reentrance ?

static passwd result_password;

struct passwd *getpwuid(uid_t uid) {
  /* Blah blah : remplissage de result_passwd */
  return &result_passwd;
}

Imagine ce que donne le remplissage de result_passwd qd 2 threads
l'executent "simultanement" (meme en UP) => caca. Donc getpwuid n'est
pas reentrante. D'ou la presence de getpwuid_r a laquelle on fournit
en parametre le struct passwd a remplir => version reentrante.

    -> Je suppose que le deadlock d'un processeur correspond a un etat
    -> dans
    Thomas> lequel le processeur se retrouve completement bloque (par
    Thomas> un mauvais jeu de spinlock). Mais je comprends pas bien ta
    Thomas> condition necessaire (et apparemment suffisante) pour que
    Thomas> ces deadlocks n'apparaissent pas....

Imagine qu'on est en SMP, sans cli/sti autour des spinlocks. Puisque
on est en SMP, on a de /vraies/ variables de spinlocks (/vraies/
attentes actives). Imaginons qu'un thread met le spinlock a USED pour
proteger une section critique. Imagine que sur le meme processeur une
interuption soit levee pdt cette section critique (car pas de sti) et
que, pour proteger une section critique vis a vis des autres
processeurs, elle veuille posseder le *meme* spinlock => elle va
bloquer a l'infini car le spinlock est deja pris par le processeur !
Donc quand on prend un spinlock en SMP, il faut que les interruptions
soient interdites en local. Sinon deadlock.

Cependant, on peut faire plus fin : rien ne sert d'interdire les
interruptions quand on est CERTAIN que le spinlock ne sera jamais pris
dans une interruption (en SMP comme en UP). D'ou la methode linux, qui
distingue les spin_lock_irq_save, et les spin_lock tout court.

    Thomas> Page 3, Section 1.2.2 : "Cependant, ce mécanisme de files
    Thomas> d'attente est difficilement compatible avec la notion
    Thomas> d'interruption : il est hors de question de mettre le
    Thomas> traitement d'une ISR dans une file d'attente pour réveil a
    Thomas> plus tard".

    -> Tu devrais preciser que pourtant c'est ce qu'on fait avec les
    -> bottom
    Thomas> halves, mis a part que tout le traitement n'est pas remis
    Thomas> a plus tard.  Ce qui essentiel (mise de cote de donnees
    Thomas> critiques...) est effectue de suite, le reste est deporte
    Thomas> a plus tard. Ce passage est donc un peu ambigu, non ?

Ca doit effectivement paraitre ambigu, puisque c'est mal percu. Une
file d'attente, c'est pas une "wait queue" (extension des bottom
halves) de Linux ! Une file d'attente est une structure de threads en
attente reservee a l'ordonnancement. Une file d'attente, c'est
exactement ce que Julien et toi vous gerez avec les IPC ou les Sleep
respectivement : une liste de threads en attente sur ressource/sur le
temps.

    Thomas> Partie 1.3.1 : effectivement la solution des bottom halves
    Thomas> me parait plus appropriee, et c'est d'ailleurs celle
    Thomas> utilisee dans Linux et dans d'autres OS... c'est qu'elle
    Thomas> est surement valable. N'utiliser que les spinlocks risque
    Thomas> de provoquer une chute de performances assez terrible.  On
    Thomas> pourrait donc imaginer un pool de threads reserves a
    Thomas> l'avance, qui pourrait etre associes rapidement a un
    Thomas> traitement d'interruption donne.  Peu importe le mecanisme
    Thomas> exact, mais j'aimerais que dans la mesure du possible, les
    Thomas> bottom halves ne constituent pas une nouvelle entite,
    Thomas> differente du thread noyau.

Attention, dans un bottom half, pas de blocage possible. Ce qui
differencie une ISR d'un BH, c'est que l'ISR est protegee des
interruptions ("un BH est interruptible"). Cependant, comme le BH
n'est pas associe a un thread propre (on ne peut pas dire que le
thread qui a ete interrompu ait ete choisi deterministiquement), il
est hors de question que ce BH puisse bloquer en attente sur
ressource, pas plus que l'ISR ne peut le faire.

Dans le sens Linux, le BH est en effet une extension de l'ISR. Ce dont
parle le draft-0, c'est que, en plus des BH (et des wait queues
Linux), on ait recours a un "thread mandataire" (proxy) destine a
executer les traitements (associes aux ISR) susceptibles de bloquer en
attente sur ressource. On pourrait presque les appeler "BH de 2eme
niveau".

ISR   => pas interruptibles
BH    => interruptibles par niveau (IPL), non bloquables
proxy => interruptibles, bloquables.

    Thomas> Partie 1.3.2 : tu pourrais aussi preciser que le task
    Thomas> switch qu'implique l'utilisation de task gate entraine un
    Thomas> certain surcout. d'apres les mesures que j'avais effectue,
    Thomas> il etait moins grand que prevu, mais je pense qu'il etait
    Thomas> au moins de 15 ou 20%.

Oui.

    Thomas> Partie 1.4 : content de voir que nous sommes d'accord
    Thomas> concernant l'utilisation de bottom halves, ou equivalent.

A nuancer : ta vision des BH correspond a ma vision des "threads
mandataires", mais faudrait qu'on se mette d'accord sur le
vocabulaire.

    Thomas> Ce bottom half quant a lui, sera interruptible. Donc en
    Thomas> fait ca revient a reporter le maximum des traitements dans
    Thomas> une partie interruptible, le bottom half.

On se rejoint : le BH est l'extension interruptible des ISR. Mais je
rajoute que un BH ne peut pas se bloquer en attente sur ressource, pas
plus que l'ISR. Que donc il faut deleguer un thread special pour que
le traitement associe a une ISR puisse bloquer en attente sur
ressource : le thread mandataire, qui peut etre 1 ou plusieurs (a
definir).

    Thomas> Toutefois, je ne saisis pas bien le mecanisme d'IPL que tu
    Thomas> decris pendant une page. Je pense que tu devrais etre plus
    Thomas> precis concernant les interruptions dont tu
    Thomas> parles. Parles-tu uniquement des IRQs (ce doit etre le
    Thomas> cas, tu parles de EOI, etc...), ou de toutes les
    Thomas> interruptions y compris les fautes (page fault, double
    Thomas> fault & co). Je ne comprends vraiment pas a quoi ca peut
    Thomas> servir, si tu pouvais m'eclairer sur ce sujet, ce serait
    Thomas> plutot pas mal.

Je parle les IRQ (interruptions asynchrones). Les exceptions sont
synchrones et resultent d'une faute processeur : on n'a *surtout* pas
interet a les masquer. D'ailleurs, elles ne sont pas masquables
(tiens, j'en suis meme pas si sur ;).

    Thomas> Partie 3 : personnellement, je ne trouve pas que les
    Thomas> papiers de Sun soient si revolutionnaires que ca. j'en

Non, et je n'ai jamais pretendu ca. Mais moi ca m'a permis d'y voir
plus clair.

Bonne journee,

-- 
d2