Approche détaillée des futex (partie 2/4)

Dans cet article, nous aborderons la gestion des futex dans le noyau, les réglages pour le réveil des threads, l'optimisation intra processus et enfin, la terminaison anticipée des threads.

1. Gestion des futex dans le noyau

La gestion des futex par le noyau Linux est configurable par le drapeau CONFIG_FUTEX (fichier init/Kconfig). Les traitements sont essentiellement effectués dans le fichier source kernel/futex.c. La structure de donnée principale, décrite en figure 1, est une table de hachage [1] nommée futex_queues. Chaque entrée est une structure futex_hash_bucket.

Le futex dont l'adresse virtuelle est fournie par l'espace utilisateur via l'appel système futex() est converti, par la fonction get_futex_key(), en une clé unique représentée par l'union futex_key définie dans le fichier include/linux/futex.h :

Passée à la fonction de hachage hash_futex(), la clé est transformée en index dans la table futex_queues. À chaque entrée de la table de hachage est associée une liste de priorité (plist définie dans le fichier d'en-tête include/linux/plist.h). C'est en fait une liste de listes qui classe ses éléments futex_q par valeur croissante du champ prio (flèches rouges sur la figure 1) et classe les éléments dont le champ prio est identique en « First In, First Out » (FIFO, représenté par les flèches vertes sur la figure 1).

Chaque futex_q est associé via le champ task à un thread en attente sur un futex identifié par sa clé dans le champ key et est alloué dans la pile du thread (i.e. variable locale de l'appel système futex()). Il convient de préciser que du point de vue de l'utilisateur, plus la valeur numérique de la priorité d'un thread est grande, plus il est prioritaire. Il suffit de se reporter au manuel en ligne de l'appel système sched_setscheduler(). Cela est perturbant, car en interne, le noyau Linux et notamment l'ordonnanceur, utilisent la logique inverse. Linux supporte les threads temps réel (politiques d'ordonnancement SCHED_RR et SCHED_FIFO) et les threads temps partagé (politique d'ordonnancement SCHED_OTHER entre autres). Les appels système sched_get_priority_min() et sched_get_priority_max() retournent respectivement les valeurs minimales et maximales pour les priorités en fonction du type d'ordonnancement, comme indiqué dans le tableau de la figure 2.

Les threads temps réel sont toujours plus prioritaires que les threads temps partagé, vu que ces derniers ont la priorité 0 alors que les premiers ont une priorité minimale de 1. Pour garantir un temps de réponse optimal, Linux tient compte de la priorité des threads lors de la mise en file d'attente sur les futex. Par contre, la politique d'ordonnancement n'est pas prise en compte. Comme les files d'attente sont des plist ordonnées par ordre croissant des champs prio, nous sommes dans la logique inverse des significations des priorités pour les threads (du point de vue de l'utilisateur tout au moins !). C'est la raison pour laquelle le champ prio qui sert à ordonner les éléments futex_q, est dérivé de la priorité des threads qui leur sont associés par la formule suivante :

prio = MIN(normal_prio, MAX_RT_PRIO)

avec :

- normal_prio égal :

 - "MAX_RT_PRIO - 1 - priorité" pour les threads temps réel,

 - "100 à 139" pour les threads temps partagé.

- MAX_RT_PRIO égal à 100.

Pour les threads temps réel, la formule utilise les priorités passées par l'utilisateur qui vont de 1 à 99 avec l'appel système sched_setscheduler(). Comme ces valeurs sont inférieures à MAX_RT_PRIO, il en résulte que le champ prio aura respectivement les valeurs de 98 à 0.

Pour les threads temps partagé, la formule utilise la priorité interne au noyau qui va de 100 à 139 en fonction du niceness du thread modifiable par l'appel système nice(). Comme ces valeurs sont supérieures à MAX_RT_PRIO, il en résulte que le champ prio est toujours égal à 100.

Par conséquent, les threads temps réel, sortent toujours de la file en premier par rapport aux threads temps partagé et dans l'ordre du plus prioritaire au moins prioritaire. De plus, quand il y a égalité de priorité, l'algorithme des plistrange les futex_q de manière FIFO. Ce qui implique que les threads temps partagé, tous rangés avec le champ prio égal à MAX_RT_PRIO (100) et les threads temps réel de priorités identiques sont sortis de la liste dans l'ordre du plus anciennement au plus récemment mis en attente.

Pour étayer le propos, le programme futex_prio du listing suivant crée tout d'abord, pour un futex, un emplacement de la taille d'un entier à l'adresse futex_vardans un segment de mémoire partagée via l'appel système mmap(). Ensuite, il crée des processus dont les priorités sont passées en argument. Quand l'argument vaut 0, c'est un processus temps partagé de priorité par défaut qui est créé. Lorsque le paramètre est supérieur à 0 et précédé de la lettre « f » ou « r », c'est un processus de priorité temps réel avec les politiques d'ordonnancement respectives SCHED_FIFO ou SCHED_RR qui est créé. Les processus sont mis en attente, dans l'ordre de leur création, tant que le futex vaut 0. Après avoir passé le futex à la valeur 1, le thread principal réveille un à un les processus endormis en passant 1 en troisième paramètre de l'opération FUTEX_WAKE de l'appel système futex().

L'exécution du programme requiert les droits du super-utilisateur (e.g. commande sudo) car, par défaut, Linux n'autorise pas la création de threads temps réel par les utilisateurs non privilégiés.

Dans ce premier exemple d'exécution, quatre threads temps réel sont créés. On constate bien que peu importe la politique d'ordonnancement, les threads sont réveillés dans l'ordre croissant des priorités :

Dans ce second exemple, seuls des threads temps partagé sont créés. On constate bien le réveil dans l'ordre FIFO :

Dans ce dernier exemple qui est le cas illustré en figure 1, des threads temps réel et temps partagé sont créés. On constate bien le réveil des premiers avant les seconds et l'ordre FIFO pour les threads de mêmes priorités :

On notera que l'ordre de réveil des threads établi au moment de la mise en attente sur le futex ne varie pas en cas de changement de priorité, comme le met en exergue le programme suivant qui est une variante du listing précédent. Une fois les processus fils créés et mis en attente sur un premier futex, le processus père inverse leur priorité avec l'opération "100 - prio", puis les réveille. Ensuite, les processus fils se remettent en attente sur un deuxième futex avant d'être de nouveau réveillés par le processus père.

L'exécution montre qu'après attente sur le premier futex, l'ordre de réveil ne change pas malgré l'inversement des priorités des processus fils. Les nouvelles priorités ne prennent effet qu'au moment de la mise en attente sur le deuxième futex :

2. Nombre de threads à réveiller

Le troisième paramètre de l'opération FUTEX_WAKE est le nombre de threads à réveiller. Quand on doit gérer plus de deux threads en concurrence, on peut s'interroger sur la valeur à utiliser.

Dans certains cas particuliers, comme les barrières vues en section 3.3 du premier article de cette série, on connaît le nombre de threads en attente et la sémantique du service implique qu'il faut réveiller tous les threads en attente. Dans ce cas, le troisième paramètre sera au moins égal à ce nombre.

Cependant, d'autres services comme les mutex peuvent avoir un nombre indéterminé de threads en attente. On peut vouloir réveiller plusieurs threads, voire tous les threads suspendus pour laisser l'ordonnanceur de Linux choisir le thread qui prendra effectivement le CPU. Dans [2], Ulrich Drepper déconseille de faire toute supposition sur tel ou tel comportement du noyau, car c'est sujet à modifications. Il propose d'utiliser soit la valeur 1, soit la valeur INT_MAXdéfinie dans le fichier d'en-tête <limits.h>, mais pas de valeurs intermédiaires. Toutefois, [2] n'indique pas quelle valeur choisir de préférence entre 1 ou INT_MAX. Avec la connaissance de la gestion des files d'attente sur les futex côté noyau telle que présentée en section 1, il peut être suggéré les choix suivants :

1. Si le futex ne concerne que des threads temps réel avec la politique d'ordonnancement SCHED_FIFO, il est conseillé de spécifier la valeur 1 en troisième paramètre, car c'est le thread de priorité maximum et qui est en attente depuis le plus longtemps (en cas d'égalité de priorité) qui sera réveillé. Il en est de même pour les threads temps réel avec la politique d'ordonnancement SCHED_RR, car s'ils sont en attente sur le futex, cela veut dire qu'ils n'ont pas consommé leur quantum de temps CPU et qu'ils peuvent donc reprendre leur exécution.

2. Si le futex ne concerne que des threads temps partagé, tous les threads sont ordonnés en FIFO sous la même priorité MAX_RT_PRIO. Si on précise la valeur 1, alors on favorise le thread qui est en attente depuis le plus longtemps sans se soucier des priorités réelles des threads. La valeur INT_MAXlaisse, une fois les threads réveillés, l'opportunité à l'ordonnanceur de Linux de choisir le thread non seulement en fonction du temps d'attente sur le futex, mais aussi en fonction de sa priorité réelle qui est recalculée régulièrement en fonction de la consommation CPU antérieure.

3. Si le futex concerne à la fois des threads temps réel et temps partagé, alors il semble que la valeur INT_MAX soit la plus appropriée car à tout moment on sait que si au moins un thread temps réel est en attente sur le futex, alors il sera réveillé en premier et s'il n'y a pas de threads temps réel, alors le cas 2 s'applique.

Bien-entendu, ces règles doivent être pondérées par le temps CPU consommé par un thread pour reprendre le contrôle sur la ressource gérée par le futex et par le nombre potentiel de threads en attente. Sous peine d'être confronté au fameux problème de « thundering herd » évoqué dans [3], il est souvent préférable de ne réveiller qu'un thread à la fois.

3. Optimisation intra processus

Lorsque les threads en compétition sont dans un seul et même processus Linux, il est possible de rendre l'appel système futex() plus efficace en utilisant les versions PRIVATE de certains opérateurs définis dans le fichier d'en-tête <linux/futex.h> :

Dans le cas où le futex ne concerne que les threads d'un même processus, les traitements internes au noyau pour identifier la variable (association d'une clé d'identification effectuée par la fonction get_futex_key() dans le fichier kernel/futex.c dont un extrait est donné dans le code suivant) sont moins lourds, car il n'est pas besoin d'identifier la page mémoire ou l'inode associé à l'objet dans lequel se trouve le futex et il n'est même pas besoin d'incrémenter le compteur de référence associé. L'adresse virtuelle suffit à identifier une variable au sein d'un même processus, vu que tous ses threads partagent son espace d'adressage. On parle alors de futex privés par opposition aux futex partagés.

Dans le listing qui suit, les traitements associés aux clés des futex privés est en rouge. Le reste du code, beaucoup plus long et complexe, concerne les clés des futex partagés.

À titre d'exemple, dans la GLIBC/NPTL, ce sont les versions PRIVATE des opérations qui sont utilisées par défaut pour les futex se cachant derrière les mutex ou les barrières. Pour une utilisation par des threads appartenant à différents processus, les services pthread_mutexattr_setpshared() et pthread_barrierattr_setpshared() permettent de positionner l'attribut PTHREAD_PROCESS_SHARED afin de passer par les versions non PRIVATE des opérations sur les futex.

4. Terminaison anticipée des threads

Lorsque des threads sont en attente sur un futex parce qu'un ou plusieurs autres threads ont pris la main dessus, il peut arriver la situation où les threads détenant le mutex se terminent sans réveiller les threads en attente. Par exemple, une erreur de programmation qui aboutirait à la terminaison d'un thread qui détient un mutex. C'est un cas d'étreinte fatale [4] pour les threads en attente sur le futex concerné, car ils ne seront plus réveillés !

À titre d'exemple, le programme futex_robust du listing suivant crée deux processus fils : le premier se met en attente sur un futex tant que ce dernier est à 0, le second le met à 1, mais ne réveille pas les threads en attente dessus avant de se terminer. Le thread principal attend la fin du second processus, puis du premier, via l'appel système waitpid().

À l'exécution, le programme ne se termine pas, car le processus principal reste en attente infinie sur la fin du premier fils, qui lui-même est en attente infinie sur le futex non libéré par le second fils :

Pour pallier le problème, Linux propose la notion de listes robustes (i.e. « robust lists ») décrite succinctement dans la documentation fournie avec ses sources : Documentation/robust-futexes.txt. Le principe consiste à passer au noyau une liste de futex occupés par les threads en espace utilisateur. Au moment de la terminaison des threads, le noyau parcourt cette liste pour identifier les futex occupés sur lesquels au moins un thread est en attente, afin de déclencher l'opération FUTEX_WAKE pour un seul des threads en attente (i.e. comme lorsque l'on passe la valeur 1 en troisième paramètre de l'appel système).

Conformément à la description donnée en section 1, c'est le thread le plus prioritaire ou le plus anciennement mis en attente en cas d'égalité de priorités, qui est réveillé. La mise en œuvre n'est pas triviale au premier abord. Une ABI (i.e. « Application Binary Interface ») est définie dans la documentation des sources : Documentation/robust-futex-ABI.txt.

Pour aider à la compréhension, le code suivant est une nouvelle version du programme précédent : les lignes de code différentes sont en rouge.

La figure 3, qui schématise l'organisation des données en mémoire durant l'exécution du programme, sert de support pour la description des modifications.

4.1. La structure de données de l'utilisateur

L'application doit prévoir une structure de données qui embarque le futex et les pointeurs pour la liste chaînée. D'où la structure udata_t qui contient respectivement les champs futex_var et link. Le type struct robust_list est défini dans le fichier d'en-tête <linux/futex.h> :

Afin d'ajouter ou supprimer efficacement en O(1) n'importe quel élément de la liste, il est conseillé d'utiliser un double chaînage, sinon on devra parcourir tout ou partie de la liste pour retrouver les éléments. Ici, pour simplifier le propos, nous nous contentons d'une liste simplement chaînée, car c'est le minimum requis par le noyau.

4.2. La tête de liste

L'application doit définir et initialiser une tête de liste dont le type est défini dans le fichier d'en-tête <linux/futex.h> :

D'où la définition de la variable globale head avec le type robust_list_head et son initialisation en début de fonction main().

Le champ list est une liste circulaire qui pointe sur la structure robust_list des enregistrements qui contiennent le futex. Le champ futex_offset est la valeur à ajouter à l'adresse de la structure robust_list dans l'enregistrement pour retrouver l'adresse du futex. La fonction de service offsetof() est préconisée pour calculer un offset de champ dans une structure donnée. Le champ list_op_pending est l'adresse de la structure robust_list de l'enregistrement qu'on s'apprête à ajouter à la liste juste avant de prendre la main sur le futex ; on verra par la suite son utilité. On notera que la liste circulaire est vide lorsque le champ list pointe sur lui-même.

Il faut ensuite enregistrer la tête de liste au sein du noyau via l'appel système set_robust_list(). Cela a pour conséquence de mémoriser l'adresse de la tête de liste dans le descripteur du thread au sein du noyau. Chacun des threads doit effectuer cette opération et au plus une tête de liste peut être enregistrée par thread. D'où l'invocation de set_robust_list() au début de chaque processus (le principal et les deux secondaires).

4.3. Prise de contrôle sur le futex

Dans le dernier listing de la section 4, c'est le second fils qui prend le contrôle sur le futex (e.g. opération de verrouillage si c'est un mutex). Cela consiste tout d'abord à assigner le champ list_op_pending de la tête de liste avec l'adresse de l'enregistrement associé au futex. Ensuite, il faut renseigner les 29 bits de poids faible du futex avec l'identifiant du thread qui prend le contrôle.

Ici, comme nous avons affaire à trois processus mono-thread, l'identifiant de process est aussi l'identifiant du thread (à ne pas confondre avec l'identifiant retourné par le service POSIX pthread_self() en espace utilisateur !). D'où l'appel à getpid() (cela devrait se faire par opération atomique, mais ce n'est pas justifié dans cet exemple simple, car on sait que le thread concurrent n'accède pas à la variable à ce moment). Enfin, l'enregistrement du futex est inséré dans la liste circulaire, puis le champ list_op_pending est remis à 0.

La prise de contrôle sur le futex (affectation de l'identifiant de thread) et la mise en liste circulaire de l'enregistrement associé n'est pas une opération atomique. S'il arrivait que le thread se termine entre les deux actions (suite à la réception d'un signal de terminaison par exemple), le noyau n'aurait pas le moyen de savoir que le futex est verrouillé et donc, ne réveillerait pas les autres threads en attente. Sur terminaison de thread, une valeur non nulle pour le champ list_op_pending permet au noyau de savoir qu'une opération de verrouillage était en cours et qu'il faut donc procéder au réveil d'éventuels threads en attente.

4.4. Mise en attente sur le futex

Toujours dans le dernier listing de la section 4, c'est le premier fils qui se met en attente. Cela consiste simplement à positionner le bit FUTEX_WAITERS dans la variable du futex. Il faudrait prévoir une opération atomique pour cela, mais ce n'est pas utile dans cet exemple car à ce moment, le thread concurrent n'accède plus au futex. Ensuite, le thread se met en attente sur le futex via l'appel système futex().

4.5. Le réveil du thread en attente

Dans le cas normal, pour libérer le futex, le thread qui a la main dessus doit assigner le champ list_op_pending de la tête de liste avec l'adresse de l'enregistrement associé au futex, enlever l'enregistrement de la liste circulaire, remettre les 29 bits de poids faible à 0 (i.e. remise à 0 de l'identifiant de thread) et, à l'aide de l'opération FUTEX_WAKE de l'appel système futex(), réveiller les threads en attente sur le futex si le bit FUTEX_WAITERS est positionné. Cela doit se faire de manière atomique en général. Enfin, il faut remettre le champ list_op_pending à zéro.

Dans notre exemple simple, nous simulons un arrêt prématuré du thread qui a la main sur la ressource : le second processus se termine sans l'appel système futex() pour réveiller le premier qui est en attente. Le noyau se charge de remédier au problème en parcourant la liste robuste. L'enregistrement correspondant au futex s'y trouvant, il positionne le bit FUTEX_OWNER_DIED en plus du bit FUTEX_WAITERS, remet à 0 les 29 premiers bits (i.e. l'identifiant de thread) et réveille le thread en attente.

Avec ce nouveau comportement, le programme se termine bien à l'exécution :

4.6. Limitations

Le protocole imposé par l'ABI restreint l'utilisation de la variable du futex, vu que les 29 bits de poids faible sont destinés à stocker l'identifiant de thread, le bit 29 est réservé pour de futures améliorations, le bit 30 est réservé pour FUTEX_OWNER_DIED et le bit 31 pour FUTEX_WAITERS (cf. figure 4).

Des mécanismes d'optimisation du nombre d'appels système futex() tels que vu en section 3.1.2 du premier article de cette série, sont rendus plus difficiles à mettre en place car ils nécessitent de pouvoir stocker différentes valeurs dans la variable. Ce qui est offert ici est un fonctionnement basique du futex : libre (ou déverrouillé) quand les 29 bits de poids faible sont à 0, occupé (ou verrouillé) quand les 29 bits de poids faible sont différents de 0 (i.e. un identifiant de thread y est stocké) avec toutefois la possibilité de voir si des threads sont en attente ou non via le bit FUTEX_WAITERS.

Il a été vu qu'au plus une liste robuste pouvait être enregistrée par thread. Comme ce mécanisme est utilisé par l'extension non POSIX pthread_mutexattr_setrobust_np() avec le drapeau PTHREAD_MUTEX_ROBUST_NP pour rendre un mutex robuste, il en résulte que ces services sont prohibés dans les applications liées à la librairie GLIBC/NPTL. Avec cette dernière, le service pthread_mutex_lock() retourne le compte-rendu d'erreur EOWNERDEAD tout en ayant verrouillé le mutex quand il est avéré qu'un thread s'est terminé sans libérer le mutex (i.e. en interne, le bit FUTEX_OWNER_DIED est positionné dans la variable du futex associé). Un exemple est donné dans le listing suivant :

Le programme crée un mutex robuste et deux threads. Celui qui prend la main en premier verrouille le mutex et se termine sans le déverrouiller. Par conséquent, le second reçoit le code d'erreur EOWNERDEAD (de valeur 130) sur le verrouillage :

Utilisée avec ou sans la GLIBC/NPTL, cette fonctionnalité semble surtout destinée à repérer la terminaison anormale d'un thread pendant l'exécution de sa section critique. Le thread réveillé par le noyau aura la plupart du temps la plus grande difficulté à savoir si les données modifiées durant la section critique inachevée sont valides ou non.

Conclusion

Ainsi s'achève la deuxième partie de la série consacrée à l'implémentation dans le noyau de la face cachée des futex. Le prochain opus évoquera la notion d'héritage de priorité, ainsi que le multiplexage.

Références

[1] Principe de la table de hachage : http://fr.wikipedia.org/wiki/Table_de_hachage

[2] « Futex are tricky » par Ulrich Drepper : http://people.redhat.com/drepper/futex.pdf

[3] Thundering herd problem : http://en.wikipedia.org/wiki/Thundering_herd_problem

[4] Notion d'étreinte fatale : http://fr.wikipedia.org/wiki/Interblocage