Sans futex, cela n’a aucun sens

 (h4x0r.org)
4 points par GN⁺ 2025-08-21 | 1 commentaires | Partager sur WhatsApp
  • Il est regrettable que le manuel The Art of Multiprocessor Programming n’aborde pas la notion de futex
  • Le futex est un composant clé de la synchronisation efficace en programmation parallèle moderne, avec de meilleures performances que les verrous traditionnels basés sur System V
  • Les futex adoptent une structure qui sépare l’acquisition du verrou des opérations d’attente/réveil, ce qui réduit les appels système inutiles et l’overhead
  • L’article inclut des exemples et des techniques pour implémenter directement, à partir des futex, diverses primitives de concurrence comme les spinlocks, mutex et verrous récursifs
  • L’auteur critique le fait que l’ouvrage ne traite pas des méthodes de synchronisation modernes indispensables en pratique d’ingénierie, soulignant l’écart entre le monde académique et l’industrie

Introduction

  • Phil Eaton a lancé un club de lecture autour de The Art of Multiprocessor Programming, 2nd Edition
  • Ce livre est considéré comme un manuel de référence en programmation parallèle, mais l’auteur lui reproche son manque de portée pratique
  • Il critique en particulier le fait que, bien que destiné aux étudiants de fin de licence et de master, il n’aborde pas le futex, une technique de synchronisation essentielle

Qu’est-ce qu’un futex, et pourquoi est-ce important ?

  • Le futex, abréviation de “fast user space mutex”, n’est pas vraiment un mutex à proprement parler, mais plutôt une primitive de synchronisation fournie par l’OS pour implémenter les verrous modernes
  • Par le passé, la plupart des verrous reposaient sur les sémaphores de System V IPC, avec des limites en efficacité et en scalabilité
  • Avec l’introduction des futex dans Linux en 2002, les performances ont été 20 à 120 fois supérieures à celles des verrous System V dans des environnements avec 1000 tâches concurrentes
  • D’autres OS comme Windows (2012) et macOS (2016) ont aussi adopté des mécanismes similaires
  • Les verrous des bibliothèques système largement utilisées aujourd’hui, comme pthreads, s’appuient sur les futex

Principe de fonctionnement du futex et ce qui le distingue

  • Les sémaphores traditionnels combinaient verrouillage et attente, tandis que le futex sépare l’acquisition du verrou des opérations d’attente/réveil
  • Cela permet de réduire les délais inutiles et les appels système ; lors de la libération d’un verrou, s’il est certain qu’aucun thread n’attend, il n’est pas nécessaire d’entrer dans le noyau
  • L’appel d’attente (wait) du futex ne met en attente que si « la valeur à une adresse mémoire donnée correspond à l’état attendu », avec prise en charge des timeouts
  • L’appel de réveil (wake) du futex réveille le nombre souhaité de threads dans la liste d’attente interne associée à une adresse mémoire donnée
  • Le mécanisme vérifie explicitement la valeur réelle en mémoire, afin d’éviter une attente inutile si l’état a déjà changé

Utilisation concrète des futex : implémentation directe

  • Le futex étant une primitive de bas niveau, on utilise des types atomic en tenant compte des questions d’ordre des opérations mémoire côté compilateur et matériel
  • Sous Linux, il faut appeler directement le syscall futex via syscall ; sur macOS, on utilise l’interface __ulock (des API plus simples ont été ajoutées récemment)
  • En pratique, l’attente sur futex renvoie 0 en cas de succès, et un code d’erreur en cas d’échec (timeout, etc.)
  • Opérations centrales basées sur futex :
    • h4x0r_futex_wait_timespec() : attend si la valeur attendue correspond, avec possibilité de timeout
    • h4x0r_futex_wake() : réveille un seul ou tous les threads en attente

Exemples concrets d’implémentation de mutex/spinlock/verrou récursif

Spinlock

  • La forme de verrou la plus simple, fonctionnant avec un seul bit (atomic_fetch_or)
  • Il boucle indéfiniment (« spin ») jusqu’à obtenir le verrou, mais en cas de forte contention, il gaspille du CPU et présente des problèmes structurels comme une mauvaise libération du verrou ou des risques de deadlock en cas d’appel récursif

Mutex hybride (« unsafe » mutex)

  • En général, on essaie d’abord avec un spinlock, puis après un certain nombre d’échecs on bascule vers un futex pour un blocage plus efficace
  • S’il n’y a pas de thread en attente, on peut éviter des appels système inutiles ; pour les threads en attente, on peut aussi minimiser les syscalls de réveil
  • Comme la vérification stricte de propriété ou la gestion de la récursivité sont incomplètes, l’appellation « unsafe » est utilisée

Mutex avec compteur de waiters

  • Un bit représente l’état du verrou, les autres servent à compter le nombre de threads en attente, afin de réduire les syscalls de réveil inutiles
  • Il n’y a toujours ni gestion de propriété ni gestion de récursivité

Mutex avec gestion de propriété

  • La valeur pthread_t permet de suivre clairement le propriétaire du verrou et son état, afin de détecter des unlock incorrects ou des usages récursifs problématiques
  • L’acquisition, la libération et la gestion des waiters sont toutes contrôlées strictement par des opérations atomiques

Verrou récursif

  • Il ajoute un compteur de profondeur (depth) par thread, permettant au même thread d’acquérir plusieurs fois le verrou
  • Lors du unlock, la profondeur diminue ; quand elle atteint 0, le déverrouillage réel et le réveil ont lieu
  • Chaque opération est implémentée avec des opérations atomiques et une vérification stricte de propriété

Défis restants et réalité de l’ingénierie

  • Si le thread propriétaire du verrou se termine de manière anormale, la gestion du verrou exige des mécanismes supplémentaires comme une liste d’administration dédiée ou des callbacks de fin
  • L’usage de mutex partagés entre processus demande également des précautions supplémentaires pour gérer les changements d’état
  • Les verrous POSIX RW ne définissent pas le comportement en cas de récursivité imbriquée et les implémentations diffèrent, ce qui rend la sûreté difficile à garantir en pratique
  • L’auteur critique le fait que les enjeux de concurrence vraiment importants en pratique (futex, verrous récursifs, runtimes asynchrones, etc.) ne soient pas intégrés aux cursus

Conclusion

  • The Art of Multiprocessor Programming est trop centré sur l’histoire ou la théorie et ne transmet pas correctement des savoirs pratiques essentiels de la programmation parallèle moderne
  • Ne pas traiter correctement des composants clés de synchronisation comme les futex, tels qu’ils fonctionnent réellement dans les systèmes, peut nuire concrètement à la formation des générations suivantes
  • L’auteur insiste sur la nécessité d’intégrer les concepts récents et de renforcer le contenu pratique

Référence

  • L’ensemble des exemples de code est disponible sur codeberg

À lire aussi

1 commentaires

 
GN⁺ 2025-08-21
Commentaires sur Hacker News

  • Windows dispose d’une fonctionnalité appelée WaitForMultipleObjects, et Linux l’a également introduite avec Futex2 dans la version 5.16 (fin 2021)
    Lien connexe
    Diverses améliorations ont été apportées récemment à Futex2
    La prise en charge de NUMA a enfin été ajoutée
    Lien NUMA 1
    Lien NUMA 2
    NUMA est un facteur très important pour les performances
    L’application de futex à io_uring dans la 6.7 (2024) a contribué à améliorer les performances de l’AIO de PostgreSQL
    Article connexe
    La 6.7 a aussi ajouté les fonctionnalités small requeue et single wait
    Lien connexe

    • Windows n’a pas ajouté WaitForMultipleObjects récemment, il l’a eu dès le départ depuis plus de 30 ans
      WaitForMultipleObjects était bien un avantage de Windows NT par rapport à UNIX, mais IBM PL/I disposait déjà d’une fonctionnalité similaire en 1965
      La fonction wait d’UNIX était une version simplifiée du wait d’IBM PL/I et, comme plusieurs fonctions héritées de Multics, elle était moins puissante que le modèle d’origine
      Les fonctions WaitForSingleObject et WaitForMultipleObjects de Microsoft n’étaient pas non plus des implémentations efficaces, au point qu’il a finalement fallu introduire WaitOnAddress, l’équivalent de futex sous Linux
      Le futex de Linux est limité à une taille de 32 bits et ne peut attendre qu’un seul événement
      On peut implémenter l’attente de plusieurs événements à l’aide d’opérations atomiques sur les bits, mais ce n’est pas efficace, ce qui rend la contrainte des 32 bits encore plus problématique
      C’est une bonne chose d’essayer de combiner dans futex certains avantages de WaitForMultipleObjects
      Ce n’est pas une imitation de Windows, mais en réalité une réimplémentation d’une technique classique bien connue depuis plus de 50 ans, donc bien plus ancienne que Microsoft

    • Il est dommage qu’il n’existe toujours pas de fonctionnalité futex_swap
      Discussion connexe 1
      Document connexe 2

    • Futex n’a rien à voir avec WFMO (WaitForMultipleObjects) et correspond plutôt aux keyed events
      Sous Linux, l’équivalent de WFMO est select/poll/epoll

    • La prise en charge de futex dans io_uring est vraiment une excellente fonctionnalité
      Je l’ai utilisée pour implémenter des mutex et des files d’attente quand je travaillais avec les fibers Ruby
      Voir le code source

  • Le livre précise qu’il vaut mieux utiliser les primitives de synchronisation fournies par la bibliothèque, le langage ou le système, plutôt que d’implémenter soi-même ses structures
    L’objectif principal du livre porte sur les concepts généraux de concurrence, pas sur une plateforme particulière
    C’est dommage que l’auteur de l’article ait adopté une opposition un peu exagérée
    Cet article aurait été meilleur avec une perspective plus collaborative, du type « ce que TAoMP ne dit pas »
    On remarque aussi que ce blog vient d’être créé, que Phil a publié cet article et qu’il en a aussi promu d’autres

    • C’est moi qui ai écrit cet article, après avoir été déçu par le livre en le lisant
      J’ai eu l’impression qu’on n’apprend ni dans le monde académique ni dans l’industrie des choses vraiment utiles en pratique
      Donc l’intention n’était pas de dire « allons étudier futex ! »
      En réalité, j’ai été tellement déçu par le livre que j’ai repoussé d’autres billets pour écrire celui-ci d’abord
      J’ai déjà travaillé avec Phil auparavant, donc nous sommes en contact, mais jusqu’ici je n’ai eu aucun mal à trouver des lecteurs pour mes articles

    • Avec le recul, la partie où il disait qu’il ne comparait même pas le style sysv à un dinosaure allait trop loin
      C’est un point sur lequel il aurait fallu davantage d’humilité

  • Ce qu’il y a de plus intéressant avec futex, c’est sa structure sans handle
    C’est un observateur de mémoire côté noyau qui fournit un comportement de base très utile sans nécessiter d’allocation/libération via syscall
    S’il n’y a aucun thread en attente, tout est proprement nettoyé, et sans contention le noyau ne sait même pas qu’un mutex existe
    J’aimerais voir une analyse détaillée de la manière dont le noyau gère futex avec de hautes performances
    Je viens seulement d’apprendre aujourd’hui l’existence de futex2
    Documentation connexe

    • Oui, et on ne veut pas non plus d’un système qui appelle le malloc() du noyau pour allouer des données à chaque fois qu’un thread se bloque sur un verrou
      Pour éviter cela, beaucoup d’OS allouent un « queue object » à la création de chaque thread, puis associent cet objet au verrou quand le thread rencontre un verrou en contention
      Autrement dit, plusieurs threads laissent des queue objects dans une linked list associée au verrou, et chacun en récupère un en repartant au réveil
      Rien ne garantit qu’un thread récupère à sa fin l’objet qu’il avait créé au départ, car les objets se mélangent entre-temps
      Solaris a introduit en premier ce type de structure, appelé turnstile, et les BSD ont aussi adopté cette méthode
      Référence Solaris internals
      Document PDF BSD

    • Les premières wait queues dans le noyau Unix fonctionnaient aussi de cette manière

  • Dès l’article original sur futex en 2002, l’efficacité de futex était clairement démontrée, avec des performances 20 à 120 fois supérieures aux verrous sysv dans un test de 1 000 tâches parallèles
    Mais en pratique, le point de comparaison pertinent n’est pas le verrou sysv
    Concrètement, même sans futex, la plupart des implémentations de verrous n’entrent pas dans le noyau sur le fast path et ne passent au noyau pour attendre que sur le slow path ; le seul vrai gain de futex est donc la petite taille de la structure de données en espace utilisateur qui représente l’état d’attente du verrou
    Parmi les autres alternatives, on trouve les thin locks (utilisés dans la JVM) et ParkingLot (implémentation entièrement en userland), qui peuvent fonctionner sans futex fourni par l’OS

    • D’après mon expérience, la plupart des gens apprennent surtout les primitives de base réellement fournies dans la pratique, donc se concentrent sur ce que propose la bibliothèque standard de leur langage
      Autrement dit, la transition de sysv vers futex a été la tendance dominante, même s’il existe récemment des approches personnalisées ; la norme de fait reste futex
      Si quelqu’un écrivait son propre scheduler en userland, une implémentation séparée serait possible, mais la plupart choisiraient probablement d’écrire sur des file descriptors et de gérer eux-mêmes leur file
      Je me demande quel serait réellement le gain de cette approche

    • En pratique, presque tous les verrous modernes finissent par utiliser futex en interne quand c’est disponible
      Comme futex est le mécanisme d’attente le plus efficace sous Linux, il est toujours souhaitable de l’utiliser sur le chemin lent (down)
      Même des choses comme thread.park() dans un langage ont de fortes chances de reposer au final sur futex

    • Je me demande si la JVM utilise encore les thin locks
      J’avais autrefois trouvé une référence indiquant que la JVM appelait futex ; je serais curieux de savoir si elle a migré vers les thin locks
      Discussion Stack Overflow connexe

  • L’implémentation réelle des [recursive locks] n’est pas cohérente d’un standard à l’autre, et dans bien des cas ce n’est même pas défini du tout, justement parce que c’est difficile
    Cette attitude est assez frustrante
    C’est un peu le raisonnement : « les implémenteurs d’OS ou de langages ne sauront probablement pas bien implémenter la fonctionnalité X, donc laissons les développeurs d’applications se débrouiller eux-mêmes »
    Au final, les utilisateurs en aval n’ont pas vraiment d’autre recours que de changer de fournisseur

    • Imposer trop de contraintes à un standard peut fermer la porte à de meilleures implémentations
      Par exemple, la table de hachage et les expressions régulières de la norme C++ sont bien plus lentes que des alternatives tierces à cause de leurs nombreuses contraintes
      Dès qu’on impose une contrainte spécifique, comme l’obligation d’utiliser uniquement du chaînage, ou certaines garanties fonctionnelles, on bloque des implémentations alternatives plus performantes
      Comme on peut imaginer des recursive rwlocks qui sacrifient un peu de performance ou vérifient moins de choses, je ne pense pas qu’il faille bloquer ces différentes orientations

    • Personnellement, je pense qu’il vaut mieux ne pas utiliser de recursive lock du tout, donc je ne vois pas l’intérêt d’ajouter cette spécification au standard

    • Si vous voulez mieux comprendre le phénomène worse is better, voir le wiki
      Je n’aime pas vraiment ça, mais c’est la réalité

  • Je me suis demandé pourquoi futex sous Linux est limité aux int 32 bits, alors j’ai creusé la question
    Dans une discussion sur le support 64 bits, Linus disait qu’on pouvait utiliser un atomique 64 bits en espace utilisateur et n’employer que les 32 bits de poids faible avec futex
    Mais en C/C++, les atomiques de tailles mixtes sont considérés comme un undefined behavior, et c’est pourtant ainsi que fonctionne aussi l’implémentation des sémaphores de glibc
    Dans un entier 64 bits, les 32 bits de poids fort servent de compteur de waiters et les 32 bits de poids faible de valeur de sémaphore, et seul le bas 32 bits est utilisé avec futex
    Je me demande si c’est un comportement défini par gcc, ou si cela n’a pas d’importance grâce à la frontière de processus (noyau/processus), ou bien si même glibc utilise un undefined behavior

  • Je recommande aussi C++ Concurrency in Action d’Anthony Williams ; il ne traite pas de futex ni de l’implémentation directe des primitives de synchronisation, mais couvre des sujets très proches de la pratique, comme l’ordre mémoire et le SMR nécessaire aux structures lock-free
    Si vous voulez une perspective plus orientée matériel, je recommande aussi le livre gratuit de Paul McKenney, « Is Parallel Programming Hard, And, If So, What Can You Do About It? »
    Ce livre non plus ne couvre pas futex en profondeur, mais il renvoie vers « Futexes Are Tricky » d’Ulrich Drepper
    TAOMPP convient bien pour traiter des concepts de concurrence de haut niveau ; il n’a pas vocation à détailler les implémentations au niveau OS
    Quoi qu’il en soit, les verrous de Peterson ou de bakery sont inutiles en production, mais rien que comprendre leurs preuves aide beaucoup à saisir les algorithmes de concurrence réels

    • Le bakery lock est bon comme spin lock et il est cache-friendly
      On peut aussi implémenter un spin lock reader/writer, mais il devient strictement FIFO
      On peut connecter futex à l’attente active d’un bakery lock en espace utilisateur, mais c’est très inefficace
      Futex n’a pas du tout été conçu pour ce type d’usage (attente par spin)
      Les structures lock-free, les hazard pointers, RCU* et autres restent eux aussi délicats
      Il est même possible de construire des hazard pointers wait-free
      *Dans le cas de RCU, le copy-on-write est intuitif, mais devient coûteux si les mises à jour sont fréquentes

  • Tout comme un équivalent de futex a été introduit dans Windows 8, les critical sections de Win32 reposaient à l’origine sur des sémaphores du noyau
    Mais je me demande quelle est la structure utilisée par les SRW locks introduits avec Vista

    • CRITICAL_SECTION et SRWLock n’entrent tous deux pas dans le noyau en l’absence de contention
      SRWLock repose sur les keyed events, tandis que CRITICAL_SECTION, en cas d’échec, crée à la demande un objet noyau puis appelle celui-ci, avec un repli sur les keyed events

  • Parmi les vulnérabilités trouvées en 2014 par Pinkie Pie dans l’implémentation Linux de futex, la règle de requeue-once n’est autorisée que pour le futex passé à futex_wait_requeue_pi
    On ne peut pas faire un requeue de A vers B puis de nouveau de B vers C, mais une réaffectation de B vers B est possible
    Dans ce cas, si certaines conditions sont remplies, une fonction de cleanup n’est pas appelée, ce qui laisse un pointeur dans un état dangling
    On peut voir un cas concret ici
    Issue connexe

  • Certaines personnes ne s’inquiètent pas de la cohérence des données lorsqu’un thread plante, mais tant que tout le processus ne meurt pas, le problème du nettoyage des verrous reste entier
    La solution prévue pour cela est le robust lock
    On enregistre auprès du noyau la liste des futex détenus, puis sys_set_robust_list traite le bit concerné à la fin du thread et réveille la partie en attente

    • Le principal inconvénient des robust locks, c’est que la ressource protégée par le verrou a de fortes chances d’être déjà dans un état incohérent
      Tant qu’on ne sait pas avec certitude pourquoi le thread a crashé, il est possible que les données aient perdu leur intégrité et qu’aucune récupération ne soit possible
      Dans ce cas, tuer toute l’application peut être plus réaliste
      Les mécanismes de cleanup/récupération basés sur les robust locks sont élégants, mais probablement que 95 % des ingénieurs ne concevront pas correctement jusqu’au bout les structures de données robustes
      4 % n’auront pas le temps de le faire, et seul le 1 % restant en tirera vraiment de gros bénéfices en le faisant correctement

    • Lorsqu’on utilise des futex entre plusieurs processus (état inter-processus), on peut adopter une approche où un processus watchdog ouvre un Unix domain socket (SOCK_STREAM ou SOCK_SEQPACKET) par processus afin de détecter les crashes et nettoyer l’état propre à chaque processus

    • C’est aussi pour cela que j’ai limité ma discussion sur les mutex à la frontière du processus, de peur que le sujet ne devienne sans fin