futex(2) System Calls Manual futex(2) NOM futex - Verrouillage rapide en mode utilisateur BIBLIOTHEQUE Bibliotheque C standard (libc, -lc) SYNOPSIS #include /* Definition des constantes FUTEX_* */ #include /* Definition des constantes SYS_* */ #include long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val, const struct timespec *timeout, /* ou : uint32_t val2 */ uint32_t *uaddr2, uint32_t val3); Remarque : la glibc ne fournit pas de fonction autour de futex(), necessitant l'utilisation de syscall(2). DESCRIPTION L'appel systeme futex() offre une methode pour attendre qu'une condition soit vraie. On l'utilise en general comme construction de blocage dans le contexte de la synchronisation de la memoire partagee. Quand on utilise des futex, la majorite des operations de synchronisation s'effectue dans l'espace utilisateur. Un programme de l'espace utilisateur n'utilise l'appel systeme futex() que lorsqu'il est probable qu'il doive se bloquer plus longtemps avant que la condition ne soit vraie. D'autres operations futex() peuvent etre utilisees pour reveiller des processus ou des threads qui attendent une condition en particulier. Un futex est une valeur 32 bits -- designee ci-dessous comme << mot futex >> --dont l'adresse est fournie a l'appel systeme futex() (les futex ont une taille de 32 bits sur toutes les plateformes, y compris les systemes 64 bits). Toutes les operations futex sont pilotees par cette valeur. Afin de partager un futex entre des processus, le futex est place dans une zone de la memoire partagee creee en utilisant (par exemple) mmap(2) ou shmat(2) (ainsi, le mot futex peut avoir plusieurs adresses virtuelles dans differents processus, mais ces adresses se rapportent toutes au meme emplacement de la memoire physique). Dans un programme multithreade, il suffit de mettre le mot futex dans une variable globale partagee par tous les threads. Lors de l'execution d'une operation futex qui demande le blocage d'un thread, le noyau ne le bloquera que si le mot futex a une valeur fournie par le thread appelant (en tant qu'un des parametres de l'appel futex()) correspondant a celle prevue du mot futex. Le chargement de la valeur du mot futex, la comparaison de cette valeur avec celle attendue et le blocage s'effectueront de maniere atomique et seront entierement organises par rapport aux operations qui sont effectuees en parallele par d'autres threads sur le meme mot futex. Ainsi, le mot futex est utilise pour relier la synchronisation de l'espace utilisateur et l'implementation du blocage par le noyau. Tout comme une operation compare-and-exchange atomique qui modifie potentiellement la memoire partagee, le blocage par futex est une operation compare-and-block atomique. Une utilisation des futex consiste a implementer des verrous. L'etat du verrou (c'est-a-dire acquis ou non acquis) peut se representer comme un drapeau auquel on a un acces atomique en memoire partagee. En absence de conflit (uncontended case), un thread peut acceder et modifier l'etat du verrou avec des instructions atomiques, par exemple le passer de maniere atomique de l'etat non acquis a acquis, en utilisant une instruction compare-and-exchange atomique (de telles instructions s'effectuent entierement dans l'espace utilisateur et le noyau ne conserve aucune information sur l'etat du verrou). D'un autre cote, un thread peut etre incapable d'acquerir un verrou parce qu'il est deja acquis par un autre thread. Il peut alors passer l'attribut du verrou en tant que mot futex, et la valeur representant l'etat acquis en tant que valeur attendue pour l'operation d'attente de futex(). Cette operation futex() bloquera si et seulement si le verrou est encore acquis (c'est-a-dire si la valeur du mot futex correspond toujours a << l'etat acquis >>). Lorsque le verrou est relache, le thread doit d'abord reinitialiser l'etat du verrou sur non acquis puis executer une operation futex qui reveille les threads bloques par le drapeau de verrou utilise en tant que mot futex (cela peut etre mieux optimise pour eviter les reveils inutiles). Voir futex(7) pour plus de details sur la maniere d'utiliser les futex. Outre la fonctionnalite de base du futex consistant a attendre et a reveiller, d'autres operations futex visent a gerer des cas d'utilisation plus complexes. Remarquez qu'aucune initialisation ou destruction explicite n'est necessaire pour utiliser les futex ; le noyau ne garde un futex (c'est-a-dire un artefact d'implementation interne au noyau) que pendant que les operations telles que FUTEX_WAIT, decrite ci-dessous, s'effectuent sur un mot futex en particulier. Arguments Le parametre uaddr pointe vers un mot futex. Sur toutes les plateformes, les futex sont des entiers de quatre octets qui doivent etre alignes sur une limite de quatre octets. L'operation a effectuer sur le futex est indiquee dans le parametre de futex_op ; val est une valeur dont la signification et l'objectif dependent de futex_op. Les autres parametres (timeout, uaddr2 et val3) ne sont necessaires que pour certaines operations futex decrites ci-dessous. Si un de ces arguments n'est pas necessaire, il est ignore. Pour plusieurs operations de blocage, le parametre timeout est un pointeur vers une structure timespec qui indique la duree maximale de l'operation. Toutefois, contrairement au prototype decrit ci-dessus, pour certaines operations, les quatre octets les moins significatifs de ce parametre sont utilises comme un entier dont la signification est determinee par l'operation. Pour ces operations, le noyau diffuse la valeur timeout d'abord a unsigned long, puis a uint32_t, et dans le reste de cette page, ce parametre est designe par val2 quand il est interprete de cette maniere. Lorsqu'il est necessaire, le parametre uaddr2 est un pointeur vers un deuxieme mot futex utilise par l'operation. L'interpretation du parametre de l'entier final, val3, depend de l'operation. Operations futex Le parametre futex_op est en deux parties : une commande qui indique l'operation a effectuer et un bit ORed avec zero ou plusieurs options qui changent le comportement de l'operation. Les options qui peuvent etre incluses dans futex_op sont les suivantes : FUTEX_PRIVATE_FLAG (depuis Linux 2.6.22) Ce bit d'option peut etre utilise avec toutes les operations futex. Il dit au noyau que le futex est un processus prive non partage avec d'autres processus (c'est-a-dire qu'il n'est utilise que pour la synchronisation entre les threads du meme processus). Cela permet au noyau d'effectuer des optimisations de performance supplementaires. Par commodite, definit un ensemble de constantes dont le suffixe est _PRIVATE et qui sont equivalentes a toutes les operations listees ci-dessous mais avec l'attribut FUTEX_PRIVATE_FLAG ORed dans la valeur de la constante. On trouve ainsi FUTEX_WAIT_PRIVATE, FUTEX_WAKE_PRIVATE et ainsi de suite. FUTEX_CLOCK_REALTIME (depuis Linux 2.6.28) Ce bit d'option ne peut etre utilise qu'avec les operations FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI (depuis Linux 4.5), FUTEX_WAIT (depuis Linux 4.5) et FUTEX_LOCK_PI2 (depuis Linux 5.14). Si cette option est positionnee, le noyau mesure le timeout par rapport a l'horloge CLOCK_REALTIME. Si cette option n'est pas positionnee, le noyau mesure le timeout par rapport a l'horloge CLOCK_MONOTONIC. L'operation indiquee dans futex_op prend une de ces valeurs : FUTEX_WAIT (depuis Linux 2.6.0) Cette option teste que la valeur du mot futex vers laquelle pointe l'adresse uaddr contient toujours la valeur val attendue, et si tel est le cas, elle s'endort jusqu'a une operation FUTEX_WAKE sur le mot futex. Le chargement de la valeur du mot futex est un acces en memoire atomique (c'est-a-dire qu'il utilise des instructions machine atomiques de l'architecture concernee). Ce chargement, la comparaison avec la valeur attendue et la mise en sommeil s'effectuent de maniere atomique et sont totalement organises selon les autres operations futex sur le meme mot futex. Si le thread commence a dormir, il est considere comme en attente de ce mot futex. Si la valeur futex ne correspond pas a val, l'appel echoue immediatement avec l'erreur EAGAIN. Le but de la comparaison avec la valeur attendue est d'empecher des reveils perdus. Si un autre thread a change la valeur du mot futex apres que le thread a decide de se bloquer en se fondant sur la valeur d'avant, et si l'autre thread a effectue une operation FUTEX_WAKE (ou un reveil equivalent) apres le changement de cette valeur et avant cette operation FUTEX_WAIT, le thread appelant observera cette valeur et ne commencera pas a dormir. Si le timeout n'est pas NULL, la structure vers laquelle il pointe indique un delai d'attente (cet intervalle sera arrondi a la valeur superieure a partir de la granularite de l'horloge systeme et il est garanti de ne pas expirer en avance). Le delai est mesure par defaut par rapport a l'horloge CLOCK_MONOTONIC mais depuis Linux 4.5, l'horloge CLOCK_REALTIME peut etre choisie en indiquant FUTEX_CLOCK_REALTIME dans futex_op. Si le timeout est NULL, l'appel se bloque indefiniment. Remarque : pour FUTEX_WAIT, le timeout est interprete comme une valeur relative. Cela differe des autres operations futex ou le timeout est interprete comme une valeur absolue. Pour obtenir l'equivalent de FUTEX_WAIT, avec un delai absolu, utilisez FUTEX_WAIT_BITSET en indiquant val3 comme FUTEX_BITSET_MATCH_ANY. Les parametres uaddr2 et val3 sont ignores. FUTEX_WAKE (depuis Linux 2.6.0) Cette operation reveille jusqu'a val elements en attente (comme dans FUTEX_WAIT) sur le mot futex a l'adresse uaddr. Generalement, val est indique soit sous la forme de 1 (reveil d'un seul element en attente) soit avec INT_MAX (reveil de tous les elements en attente). Vous n'avez aucune garantie quant aux elements qui sont reveilles (par exemple un element en attente dont la priorite d'ordonnancement elevee n'est pas garanti de se reveiller avant un autre d'une priorite plus basse). Les parametres timeout, uaddr2 et val3 sont ignores. FUTEX_FD (de Linux 2.6.0 jusqu'a Linux 2.6.25 inclus) Cette operation cree un descripteur de fichier associe au futex sur uaddr. L'appelant doit fermer le descripteur de fichier renvoye apres l'avoir utilise. Quand un autre processus ou un autre thread effectue un FUTEX_WAKE sur le mot futex, le descripteur de fichier indique qu'il est accessible en lecture avec select(2), poll(2), et epoll(7) Le descripteur de fichier peut etre utilise pour avoir des notifications asynchrones, si val n'est pas nul, puis, quand un autre processus ou un autre thread execute FUTEX_WAKE, l'appelant recevra le numero du signal passe a val. Les parametres timeout, uaddr2 et val3 sont ignores. Parce qu'il etait de facon inherente sujet a des situations de concurrence, FUTEX_FD a ete supprime de Linux 2.6.26 et les suivants. FUTEX_REQUEUE (depuis Linux 2.6.0) Cette operation effectue la meme chose que FUTEX_CMP_REQUEUE (voir ci-dessous), sauf qu'elle ne verifie rien en utilisant la valeur dans val3 (le parametre val3 est ignore). FUTEX_CMP_REQUEUE (depuis Linux 2.6.7) Cette operation verifie d'abord si l'emplacement uaddr contient toujours la valeur val3. Si tel n'est pas le cas, l'operation echoue avec l'erreur EAGAIN. Si tel est le cas, l'operation reveille un maximum de val elements en attente du futex sur uaddr. S'il y a plus de val elements en attente, les autres sont supprimes de la file d'attente du futex source sur uaddr et ajoutes a la file d'attente du futex cible sur uaddr2. Le parametre val2 indique une limite superieure du nombre d'elements remis en attente dans le futex sur uaddr2. Le chargement a partir de uaddr est un acces atomique en memoire (c'est-a-dire qu'il utilise les instructions machine atomiques de l'architecture concernee). Ce chargement, la comparaison avec val3 et la remise en attente d'elements s'effectuent de maniere atomique et sont totalement organisees par rapport aux autres operations sur le meme mot futex. Les valeurs classiques qu'on indique a val sont 0 ou 1 (indiquer INT_MAX n'est pas utile car cela rendrait l'operation FUTEX_CMP_REQUEUE equivalente a FUTEX_WAKE). La valeur limite indiquee avec val2 est generalement 1 ou INT_MAX (indiquer 0 en parametre n'est pas utile car cela rendrait l'operation FUTEX_CMP_REQUEUE equivalente a FUTEX_WAIT). L'operation FUTEX_CMP_REQUEUE a ete ajoutee pour remplacer l'ancienne FUTEX_REQUEUE. La difference est que la verification de la valeur sur uaddr peut etre utilisee pour s'assurer que la remise en attente ne se produit que sous certaines conditions, ce qui evite les conflits de memoire (race conditions) dans certains cas d'utilisation. FUTEX_REQUEUE et FUTEX_CMP_REQUEUE peuvent etre utilisees pour eviter des reveils en troupeau (thundering herd) qui peuvent survenir quand on utilise FUTEX_WAKE dans des cas ou tous les elements en attente qu'on reveille doivent acquerir un autre futex. Imaginons le scenario suivant ou plusieurs threads attendent en B, une file d'attente implementee en utilisant un futex : lock(A) while (!check_value(V)) { unlock(A); block_on(B); lock(A); }; unlock(A); Si un thread qui se reveille utilisait FUTEX_WAKE, tous les elements attendant en B se reveilleraient et essaieraient d'acquerir le verrou A. Cependant, reveiller tous ces threads de cette maniere serait vain car tous les threads, sauf un, se bloqueraient immediatement a nouveau via le verrou A. Au contraire, une remise dans la file d'attente ne reveille qu'un element et deplace les autres sur le verrou A et quand celui reveille deverrouille A, le suivant peut continuer. FUTEX_WAKE_OP (depuis Linux 2.6.14) Cette operation a ete ajoutee pour prendre en charge certains cas d'utilisation de l'espace utilisateur ou plus d'un futex a la fois doit etre gere. L'exemple le plus frappant est l'implementation de pthread_cond_signal(3), qui necessite des operations sur deux futex, une pour implementer le mutex, l'autre pour utiliser dans l'implementation de la file d'attente associee a la variable conditionnelle. FUTEX_WAKE_OP permet d'implementer de tels cas sans augmenter le nombre de conflits et de changement de contexte. L'operation FUTEX_ WAKE_OP revient a executer le code suivant de maniere atomique et completement organise en fonction des operations futex sur un des deux mots futex fournis : uint32_t oldval = *(uint32_t *) uaddr2; *(uint32_t *) uaddr2 = oldval op oparg; futex(uaddr, FUTEX_WAKE, val, 0, 0, 0); if (oldval cmp cmparg) futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0); En d'autres termes, FUTEX_WAKE_OP fait ce qui suit : - sauvegarde la valeur d'origine du mot futex sur uaddr2 et effectue une operation pour modifier la valeur du futex sur uaddr2 ; il s'agit d'un acces en memoire read-modify-write atomique (c'est-a-dire d'une utilisation des instructions machine atomiques liees a l'architecture concernee) - reveille un maximum de val elements en attente sur le futex pour le mot futex sur uaddr ; - et selon les resultats d'un test de la valeur d'origine du mot futex sur uaddr2, reveille un maximum de val2 elements en attente du mot futex sur le futex sur uaddr2. L'operation et la comparaison qui doivent etre effectuees sont encodees dans les bits du parametre val3. Visuellement, l'encodage est : +---+---+-----------+-----------+ |op |cmp| oparg | cmparg | +---+---+-----------+-----------+ 4 4 12 12 <== # of bits Exprime en code, l'encodage est : #define FUTEX_OP(op, oparg, cmp, cmparg) \ (((op & 0xf) << 28) | \ ((cmp & 0xf) << 24) | \ ((oparg & 0xfff) << 12) | \ (cmparg & 0xfff)) Dans ce qui precede, op et cmp sont chacun des codes listes ci-dessous. Les composants oparg et cmparg sont des valeurs numeriques litterales, sauf les remarques ci-dessous. Le composant op prend une de ces valeurs : FUTEX_OP_SET 0 /* uaddr2 = oparg; */ FUTEX_OP_ADD 1 /* uaddr2 += oparg; */ FUTEX_OP_OR 2 /* uaddr2 |= oparg; */ FUTEX_OP_ANDN 3 /* uaddr2 &= ~oparg; */ FUTEX_OP_XOR 4 /* uaddr2 ^= oparg; */ En outre, comparer bit a bit (ORing) la valeur suivante dans op a pour consequence que (1 << oparg) sera utilise en tant qu'operande : FUTEX_OP_ARG_SHIFT 8 /* Utiliser (1 << oparg) comme operande */ Le champ cmp prend une de ces valeurs : FUTEX_OP_CMP_EQ 0 /* si (oldval == cmparg) reveiller */ FUTEX_OP_CMP_NE 1 /* si (oldval != cmparg) reveiller */ FUTEX_OP_CMP_LT 2 /* si (oldval < cmparg) reveiller */ FUTEX_OP_CMP_LE 3 /* si (oldval <= cmparg) reveiller */ FUTEX_OP_CMP_GT 4 /* si (oldval > cmparg) reveiller */ FUTEX_OP_CMP_GE 5 /* si (oldval >= cmparg) reveiller */ Le code de retour de FUTEX_WAKE_OP est la somme du nombre d'elements en attente reveilles par le futex uaddr et du nombre d'elements en attente reveilles sur le futex uaddr2. FUTEX_WAIT_BITSET (depuis Linux 2.6.25) Cette operation est equivalente a FUTEX_WAIT, sauf que val3 est utilise pour fournir un masque de bit de 32 bits au noyau. Ce masque, ou au moins un bit doit etre positionne, est stocke dans la partie interne du noyau de l'element en attente. Voir la description de FUTEX_WAKE_BITSET pour plus de details. Si timeout n'est pas NULL, la structure vers laquelle il pointe indique un delai absolu de l'operation d'attente. Si timeout est NULL, l'operation peut se bloquer indefiniment. L'argument uaddr2 est ignore. FUTEX_WAKE_BITSET (depuis Linux 2.6.25) Cette operation est identique a FUTEX_WAKE, sauf que le parametre val3 est utilise pour fournir un masque de bit de 32 bits au noyau. Ce masque, ou au moins un bit doit etre positionne, est utilise pour choisir les elements en attente qui doivent etre reveilles. Le choix se fait par une comparaison bit a bit AND du masque de bit << wait >> (a savoir la valeur de val3) et par un masque de bit stocke dans la partie interne de l'element en attente (le masque de bit << wait >> positionne en utilisant FUTEX_WAIT_BITSET). Tous les elements en attente pour lesquels le AND est positif sont reveilles ; les autres restent endormis. L'effet de FUTEX_WAIT_BITSET et de FUTEX_WAKE_BITSET est de permettre un reveil selectif parmi les elements en attente bloques sur le meme futex. Cependant, remarquez que selon le cas, l'utilisation de cette fonction de melange de masques de bit sur un futex peut etre moins efficace que le fait d'avoir plusieurs futex, car elle a besoin que le noyau verifie tous les elements en attente sur un futex, y compris ceux non concernes par le reveil (a savoir qu'ils n'ont pas de bit pertinent positionne dans leur masque de bit << wait >>). La constante FUTEX_BITSET_MATCH_ANY, qui correspond a tous les positionnements 32 bits du masque, peut etre utilise en tant que val3 de FUTEX_WAIT_BITSET et de FUTEX_WAKE_BITSET. En dehors des differences dans la gestion du parametre timeout, l'operation FUTEX_WAIT est equivalente a FUTEX_WAIT_BITSET ou val3 est indique en tant que FUTEX_BITSET_MATCH_ANY ; c'est-a-dire permettre le reveil par n'importe quel element en attente). L'operation FUTEX_WAKE est equivalente a FUTEX_WAKE_BITSET ou val3 est indique en tant que FUTEX_BITSET_MATCH_ANY ; c'est-a-dire, reveiller n'importe quel element en attente. Les arguments uaddr2 et timeout sont ignores. Futex et heritage de priorite Linux prend en charge l'heritage de priorite (priority inheritance, PI) des futex, afin de gerer des problemes d'inversion des priorites qu'on peut rencontrer avec des verrous futex normaux. L'inversion des priorites est un probleme qui survient quand une tache de haute priorite est bloquee en attente d'acquerir un verrou que possede une tache de basse priorite issue du processeur. Du coup, la tache de priorite basse ne va pas relacher le verrou et celle de haute priorite reste bloquee. L'heritage de priorite est un mecanisme pour gerer le probleme d'inversion des priorites. Avec ce mecanisme, quand une tache a haute priorite est bloquee par un verrou possede par une tache a basse priorite, la priorite de la seconde est temporairement amenee au meme niveau que celle a haute priorite, de sorte qu'elle ne soit pas doublee par une tache de niveau intermediaire et qu'elle puisse ainsi avancer pour relacher le verrou. Pour fonctionner, l'heritage de priorite doit etre transitif, ce qui signifie que si une tache a haute priorite bloque sur le verrou d'une tache a priorite intermediaire (et ainsi de suite sur des chaines de la taille de votre choix), les deux taches (ou plus generalement toutes les taches de la chaine de verrous) voient leur niveau de priorite amene a celui de la tache a haute priorite. Du point de vue de l'espace utilisateur, le futex a conscience d'un PI en acceptant une reglementation (decrite ci-dessous) entre l'espace utilisateur et le noyau sur la valeur du mot futex, couple a l'utilisation d'operations futex PI decrites ci-dessous (contrairement aux autres operations futex decrites ci-dessus, celles PI-futex sont concues pour l'implementation de mecanismes IPC tres specifiques). Les operations PI-futex decrites ci-dessous different des autres operations dans le sens ou elles imposent des regles dans l'utilisation de la valeur du mot futex : - Si le verrou n'est pas acquis, la valeur du mot futex doit etre 0. - Si le verrou est acquis, la valeur du mot futex doit etre l'ID du thread (TID ; voir gettid(2)) du thread proprietaire. - Si le verrou a un proprietaire et s'il y a des threads en concurrence pour le verrou, le bit FUTEX_WAITERS doit etre positionne dans la valeur du mot futex ; autrement dit, cette valeur est : FUTEX_WAITERS | TID (Remarquez que cela n'est pas possible pour un mot futex PI d'etre sans proprietaire ni FUTEX_WAITERS defini). Avec cette regle, une application de l'espace utilisateur peut acquerir un verrou non acquis ou en relacher un en utilisant des instructions atomiques dans l'espace utilisateur (comme une operation compare-and-swap telle que cmpxchg sur l'architecture x86). L'acquisition d'un verrou consiste simplement dans l'utilisation de compare-and-swap pour positionner la valeur du mot futex de maniere atomique sur le TID de l'appelant si sa valeur precedente etait 0. Relacher un verrou exige d'utiliser compare-and-swap pour positionner la valeur du mot futex sur 0 si la valeur precedente etait le TID prevu. Si un futex est deja acquis (c'est-a-dire qu'il a une valeur positive), les elements en attente doivent utiliser l'operation FUTEX_LOCK_PI pour acquerir le verrou. Si d'autres threads attendent le verrou, le bit FUTEX_WAITERS est defini dans la valeur du futex ; dans ce cas le detenteur du verrou doit utiliser l'operation FUTEX_UNLOCK_PI pour relacher le verrou. Dans le cas ou les appelants sont bloques dans le noyau (c'est-a-dire qu'ils doivent effectuer un appel futex()), ils traitent directement avec ce qu'on appelle un RT-mutex, un mecanisme de verrouillage du noyau qui implemente la semantique de l'heritage de priorite requis. Apres que le RT-mutex est acquis, la valeur futex est mise a jour en fonction, avant que le thread appelant ne renvoie vers l'espace utilisateur. Il est important de remarquer que le noyau mettra a jour la valeur du mot futex avant de renvoyer vers l'espace utilisateur (cela enleve la possibilite pour la valeur d'un mot futex de se terminer dans un etat non valable, par exemple en ayant un proprietaire mais en ayant la valeur 0, ou en ayant des elements en attente mais aucun bit FUTEX_WAITERS positionne). Si un futex a un RT-mutex associe dans le noyau (c'est-a-dire qu'il y a des elements en attente bloques) et si le proprietaire du futex/RT-mutex meurt de maniere inattendue, le noyau nettoie le RT-mutex et passe la main au prochain element en attente. Cela implique, en retour, que la valeur dans l'espace utilisateur soit mise a jour en fonction. Pour dire que c'est necessaire, le noyau positionne le bit FUTEX_OWNER_DIED dans le mot futex ainsi que dans l'ID du thread du nouveau proprietaire. L'espace utilisateur peut detecter cette situation par la presence du bit FUTEX_OWNER_DIED et il est alors responsable pour nettoyer l'espace laisse par le proprietaire mort. Les PI futex sont utilises en indiquant une des valeurs listees ci-dessous dans futex_op. Remarquez que les operations de PI futex doivent etre utilisees par paires et sont soumises a des exigences supplementaires : - FUTEX_LOCK_PI, FUTEX_LOCK_PI2 et FUTEX_TRYLOCK_PI vont de pair avec FUTEX_UNLOCK_PI. FUTEX_UNLOCK_PI ne doit etre appele que sur un futex appartenant au thread appelant, tel que defini par les regles de la valeur, sans quoi on obtient l'erreur EPERM. - FUTEX_WAIT_REQUEUE_PI va de pair avec FUTEX_CMP_REQUEUE_PI. Elles doivent s'effectuer depuis un futex non-PI vers un PI futex distinct (sans quoi on obtient l'erreur EINVAL). De plus, val (le nombre d'elements en attente a reveiller) doit etre de 1 (sans quoi on obtient l'erreur EINVAL). Les operations PI futex sont comme suit : FUTEX_LOCK_PI (depuis Linux 2.6.18) Cette operation est utilisee apres avoir essaye sans succes d'acquerir un verrou en utilisant une instruction atomique en mode utilisateur, car le mot futex a une valeur positive - en particulier parce qu'il contenait le TID (specifique a l'espace de noms PID) du verrou proprietaire. L'operation verifie la valeur du mot futex sur l'adresse uaddr. Si la valeur est de 0, le noyau essaie de positionner de maniere atomique la valeur du futex sur le TID de l'appelant. Si la valeur du mot futex est positive, le noyau positionne de maniere atomique le bit FUTEX_WAITERS, qui signale au proprietaire du futex qu'il ne peut pas deverrouiller le futex dans l'espace utilisateur de maniere atomique, en positionnant la valeur du futex a 0. Apres cela, le noyau : (1) Essaie de trouver le thread associe au TID du proprietaire. (2) Cree ou reutilise l'etat du noyau sur la base du proprietaire (s'il s'agit du premier element en attente, il n'existe pas d'etat du noyau pour ce futex, donc il est cree en verrouillant le RT-mutex et le proprietaire du futex devient proprietaire du RT-mutex). Si des elements en attente existent, l'etat existant est reutilise. (3) Rattache l'element en attente au futex (c'est-a-dire que l'element est mis dans la file d'attente du RT-futex). S'il existe plus d'un element en attente, la mise dans la file d'un element se fait par ordre de priorite descendant (pour des informations sur l'ordre des priorites, voir les points sur l'ordonnancement SCHED_DEADLINE, SCHED_FIFO et SCHED_RR dans sched(7)). Le proprietaire herite soit de la bande passante de processeur de l'element en attente (si l'element est programme sous la regle SCHED_DEADLINE ou SCHED_FIFO), soit de la priorite de l'element en attente (s'il est programme sous la regle SCHED_RR ou SCHED_FIFO). Cet heritage suit la chaine de verrous dans les cas de verrous imbriques et il effectue la detection des verrous morts (deadlocks). Le parametre timeout fournit un delai de tentative de verrouillage. Si timeout est positif, la structure vers laquelle il pointe indique un delai absolu mesure en fonction de l'horloge CLOCK_REALTIME. Si timeout est NULL, l'operation se bloquera indefiniment. Les parametres uaddr2, val et val3 sont ignores. FUTEX_LOCK_PI2 (depuis Linux 5.14) Cette operation est la meme que FUTEX_LOCK_PI, sauf que l'horloge par rapport a laquelle timeout est mesure peut etre selectionnee. Par defaut, le delai (absolu) indique dans timeout est mesure par rapport a l'horloge CLOCK_MONOTONIC mais si l'attribut FUTEX_CLOCK_REALTIME est indique dans futex_op, le delai est mesure par rapport a l'horloge CLOCK_REALTIME. FUTEX_TRYLOCK_PI (depuis Linux 2.6.18) L'operation essaie d'acquerir le verrou sur uaddr. Elle est appelee quand l'acquisition atomique dans l'espace utilisateur n'a pas reussi parce que le mot futex ne valait pas 0. Du fait que le noyau accede a plus d'informations d'etat que l'espace utilisateur, l'acquisition du verrou pourrait reussir si elle est effectuee par le noyau dans les cas ou le mot futex (c'est-a-dire les informations d'etat accessibles dans l'espace utilisateur) contient un etat stable (FUTEX_WAITERS et/ou FUTEX_OWNER_DIED). Cela peut arriver quand le proprietaire du futex est mort. L'espace utilisateur ne peut pas gerer cette condition de maniere "race-free", mais le noyau peut corriger cela et acquerir le futex. Les parametres uaddr2, val, timeout et val3 sont ignores. FUTEX_UNLOCK_PI (depuis Linux 2.6.18) Cette operation reveille l'element ayant la plus haute priorite et attendant un FUTEX_LOCK_PI ou un FUTEX_LOCK_PI2 a l'adresse indiquee par le parametre uaddr. Cela est appele quand la valeur dans l'espace utilisateur sur uaddr ne peut pas etre passee a 0 de maniere atomique depuis un TID (du proprietaire). Les parametres uaddr2, val, timeout et val3 sont ignores. FUTEX_CMP_REQUEUE_PI (depuis Linux 2.6.31) Cette operation est une variante PI-aware de FUTEX_CMP_REQUEUE. Elle remet en attente des elements bloques avec FUTEX_WAIT_REQUEUE_PI sur uaddr a partir d'un futex source non-PI (uaddr) vers un futex cible PI (uaddr2). Comme avec FUTEX_CMP_REQUEUE, cette operation reveille un maximum de val elements qui attendent le futex sur uaddr. Toutefois, pour FUTEX_CMP_REQUEUE_PI, val doit valoir 1 (puisque son but principal est d'eviter l'effet de troupeau (thundering herd). Les autres elements sont supprimes de la file d'attente du futex source sur uaddr et ajoutes sur celle du futex cible sur uaddr2. Les parametres val2 et val3 ont le meme objectif qu'avec FUTEX_CMP_REQUEUE. FUTEX_WAIT_REQUEUE_PI (depuis Linux 2.6.31) Attendre un futex non-PI sur uaddr et se mettre potentiellement en attente (avec une operation FUTEX_CMP_REQUEUE_PI dans une autre tache), d'un futex PI sur uaddr2. L'operation d'attente sur uaddr est la meme que pour FUTEX_WAIT. L'element peut etre retire de la file d'attente sur uaddr sans etre transfere sur uaddr2 a l'aide d'une operation FUTEX_WAKE dans une autre tache. Dans ce cas, l'operation FUTEX_WAIT_REQUEUE_PI echoue avec l'erreur EAGAIN. Si timeout n'est pas NULL, la structure vers laquelle il pointe indique un delai absolu de l'operation d'attente. Si timeout est NULL, l'operation peut se bloquer indefiniment. L'argument val3 est ignore. FUTEX_WAIT_REQUEUE_PI et FUTEX_CMP_REQUEUE_PI ont ete ajoutes pour gerer un cas d'utilisation bien particulier : la prise en charge des variables conditionnelles de threads POSIX ayant connaissance de l'heritage de priorite. L'idee est que ces operations devraient toujours aller par paires, afin de garantir que l'espace utilisateur et le noyau restent toujours synchronises. Ainsi, dans l'operation FUTEX_WAIT_REQUEUE_PI, l'application dans l'espace utilisateur pre-indique la cible de la remise en attente qui va se faire dans l'operation FUTEX_CMP_REQUEUE_PI. VALEUR RENVOYEE En cas d'erreur (en supposant que futex() a ete appele a l'aide de syscall(2)), toutes les operations renvoient -1 et positionnent errno pour indiquer l'erreur. En cas de succes, le code de retour depend de l'operation, comme decrit dans la liste suivante : FUTEX_WAIT Renvoie 0 si l'appelant a ete reveille. Remarquez qu'un reveil peut egalement resulter de l'utilisation de motifs d'utilisation classiques de futex dans du code non lie qui a pu utiliser l'emplacement memoire du mot futex (par exemple des implementations classiques basees sur futex de mutex Pthreads peuvent provoquer cela dans certaines conditions). Donc, les appelants devraient toujours, a titre conservatoire, supposer qu'un code de retour 0 peut signifier un faux reveil, et donc utiliser la valeur du mot futex (a savoir le schema de synchronisation de l'espace utilisateur) pour decider de rester bloques ou pas. FUTEX_WAKE Renvoie le nombre de processus en attente qui ont ete reveilles. FUTEX_FD Renvoie le nouveau descripteur de fichier associe au futex. FUTEX_REQUEUE Renvoie le nombre de processus en attente qui ont ete reveilles. FUTEX_CMP_REQUEUE Renvoie le nombre total d'elements en attente reveilles ou remis dans la file du futex pour le mot futex sur uaddr2. Si cette valeur est superieure a val, la difference devient le nombre d'elements en attente remis dans la file du futex pour le mot futex sur uaddr2. FUTEX_WAKE_OP Renvoie le nombre total d'elements en attente reveilles. Il s'agit de la somme des elements reveilles sur les deux futex pour les mots futex sur uaddr et uaddr2. FUTEX_WAIT_BITSET Renvoie 0 si l'appelant a ete reveille. Voir FUTEX_WAIT sur la maniere d'interpreter cela correctement en pratique. FUTEX_WAKE_BITSET Renvoie le nombre de processus en attente qui ont ete reveilles. FUTEX_LOCK_PI Renvoie 0 si le futex a applique le verrou avec succes. FUTEX_LOCK_PI2 Renvoie 0 si le futex a applique le verrou avec succes. FUTEX_TRYLOCK_PI Renvoie 0 si le futex a applique le verrou avec succes. FUTEX_UNLOCK_PI Renvoie 0 si le futex a correctement enleve le verrou. FUTEX_CMP_REQUEUE_PI Renvoie le nombre total d'elements en attente reveilles ou remis dans la file du futex pour le mot futex sur uaddr2. Si cette valeur est superieure a val, la difference devient le nombre d'elements en attente remis dans la file du futex pour le mot futex sur uaddr2. FUTEX_WAIT_REQUEUE_PI Renvoie 0 si l'appelant a ete mis dans la file d'attente avec succes au futex pour le mot futex sur uaddr2. ERREURS EACCES Pas d'acces en lecture a la memoire d'un mot futex. EAGAIN (FUTEX_WAIT, FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI) La valeur vers laquelle pointait uaddr n'etait pas egale a la valeur val attendue au moment de l'appel. Remarque : sur Linux, les noms symboliques EAGAIN et EWOULDBLOCK (les deux apparaissent dans differents endroits du code futex du noyau) ont la meme valeur. EAGAIN (FUTEX_CMP_REQUEUE, FUTEX_CMP_REQUEUE_PI) La valeur vers laquelle pointait uaddr n'etait pas egale a la valeur val3 attendue. EAGAIN (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) L'ID du thread proprietaire du futex sur uaddr (pour FUTEX_CMP_REQUEUE_PI : uaddr2) est sur le point de se terminer, mais il n'a pas encore gere le nettoyage de l'etat interne. Reessayez. EDEADLK (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Le mot futex sur uaddr est deja verrouille par l'appelant. EDEADLK (FUTEX_CMP_REQUEUE_PI) Pendant qu'il remettait en attente un element du PI futex pour le mot futex sur uaddr2, le noyau a detecte un verrou mort (deadlock). EFAULT Le parametre d'un pointeur necessaire (c'est-a-dire uaddr, uaddr2 ou timeout) ne pointait pas vers une adresse valable de l'espace utilisateur. EINTR Une operation FUTEX_WAIT ou FUTEX_WAIT_BITSET a ete interrompue par un signal (voir signal(7)). Dans Linux 2.6.22, cette erreur pouvait aussi etre renvoyee pour un faux reveil ; depuis Linux 2.6.22, cela n'arrive plus. EINVAL L'operation dans futex_op fait partie de celles qui utilisent un delai, mais le parametre timeout fourni n'etait pas valable (tv_sec valait moins de 0 ou tv_nsec ne valait pas moins de 1 000 000 000). EINVAL L'operation indiquee dans futex_op utilise uaddr et/ou uaddr2 mais l'un d'eux ne pointe pas vers un objet valable -- c'est-a-dire, l'adresse n'est pas alignee sur quatre octets. EINVAL (FUTEX_WAIT_BITSET, FUTEX_WAKE_BITSET) Le masque de bit fourni dans val3 vaut zero. EINVAL (FUTEX_CMP_REQUEUE_PI) uaddr est egal a uaddr2 (c'est-a-dire qu'une remise en attente a ete tentee sur le meme futex). EINVAL (FUTEX_FD) Le numero du signal fourni dans val n'est pas valable. EINVAL (FUTEX_WAKE, FUTEX_WAKE_OP, FUTEX_WAKE_BITSET, FUTEX_REQUEUE, FUTEX_CMP_REQUEUE) Le noyau a detecte une incoherence entre l'etat de l'espace utilisateur sur uaddr et l'etat du noyau -- c'est-a-dire qu'il a detecte un element qui attend dans FUTEX_LOCK_PI ou FUTEX_LOCK_PI2 sur uaddr. EINVAL (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI) Le noyau a detecte une incoherence entre l'etat de l'espace utilisateur sur uaddr et l'etat du noyau. Cela indique soit une corruption d'etat, soit que le noyau a trouve un element en attente sur uaddr qui attend aussi a l'aide de FUTEX_WAIT ou de FUTEX_WAIT_BITSET. EINVAL (FUTEX_CMP_REQUEUE_PI) Le noyau a detecte une incoherence entre l'etat de l'espace utilisateur sur uaddr et l'etat du noyau ; c'est-a-dire qu'il a detecte un element qui attend via FUTEX_WAIT ou FUTEX_WAIT_BITSET sur uaddr2. EINVAL (FUTEX_CMP_REQUEUE_PI) Le noyau a detecte une incoherence entre l'etat de l'espace utilisateur sur uaddr et l'etat du noyau ; c'est-a-dire qu'il a detecte un element qui attend a l'aide de FUTEX_WAIT ou de FUTEX_WAIT_BITESET sur uaddr. EINVAL (FUTEX_CMP_REQUEUE_PI) Le noyau a detecte une incoherence entre l'etat de l'espace utilisateur sur uaddr et l'etat du noyau ; c'est-a-dire qu'il a detecte un element qui attend a l'aide de FUTEX_LOCK_PI ou de FUTEX_LOCK_PI2 (au lieu de FUTEX_WAIT_REQUEUE_PI). EINVAL (FUTEX_CMP_REQUEUE_PI) Tentative de remise dans la file d'un element en attente vers un futex different de celui indique avec l'appel FUTEX_WAIT_REQUEUE_PI correspondant pour cet element. EINVAL (FUTEX_CMP_REQUEUE_PI) Le parametre val ne vaut pas 1. EINVAL Argument incorrect. ENFILE (FUTEX_FD) La limite du nombre total de fichiers ouverts sur le systeme a ete atteinte. ENOMEM (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) Le noyau n'a pas pu allouer de la memoire pour conserver les informations d'etat. ENOSYS Operation non valable indiquee dans futex_op. ENOSYS L'option FUTEX_CLOCK_REALTIME etait indiquee dans futex_op, mais l'operation qui l'accompagne n'est ni FUTEX_WAIT, ni FUTEX_WAIT_BITSET, ni FUTEX_WAIT_REQUEUE_PI, ni FUTEX_LOCK_PI2. ENOSYS (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_UNLOCK_PI, FUTEX_CMP_REQUEUE_PI, FUTEX_WAIT_REQUEUE_PI) Une verification pendant l'execution a determine que l'operation n'est pas disponible. Les operations PI-futex ne sont pas implementees sur toutes les architectures et ne sont pas prises en charge sur certaines variantes de processeur. EPERM (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) L'appelant n'est pas autorise a se rattacher au futex sur uaddr (pour FUTEX_CMP_REQUEUE_PI : le futex sur uaddr2) (cela peut venir d'une corruption de l'etat dans l'espace utilisateur). EPERM (FUTEX_UNLOCK_PI) Le verrou represente par le mot futex n'appartient pas a l'appelant. ESRCH (FUTEX_LOCK_PI, FUTEX_LOCK_PI2, FUTEX_TRYLOCK_PI, FUTEX_CMP_REQUEUE_PI) L'ID du thread dans le mot futex sur uaddr n'existe pas. ESRCH (FUTEX_CMP_REQUEUE_PI) L'ID du thread dans le mot futex sur uaddr2 n'existe pas. ETIMEDOUT L'operation de futex_op a utilise un delai indique dans timeout et le delai a expire avant la fin de l'operation. STANDARDS Linux. HISTORIQUE Linux 2.6.0. La prise en charge initiale des futex a ete ajoutee dans Linux 2.5.7 mais avec une semantique differente de celle decrite ci-dessus. Un appel systeme a 4 parametres avec la semantique decrite dans cette page a ete ajoute dans Linux 2.5.40. Dans Linux 2.5.70, un cinquieme parametre a ete ajoute. Un sixieme parametre a ete ajoute dans Linux 2.6.7. EXEMPLES Le programme ci-dessous montre l'utilisation des futex dans un programme ou un processus parent et un processus enfant utilisent une paire de futex situee dans un tableau anonyme partage pour synchroniser l'acces a une ressource partagee : le terminal. Les deux processus ecrivent chacun un message nloops (un parametre en ligne de commande qui vaut 5 par defaut s'il est absent) sur le terminal et ils utilisent un protocole de synchronisation pour garantir qu'ils alternent dans l'ecriture des messages. Pendant l'execution de ce programme, nous voyons un affichage comme suit : $ ./futex_demo Parent (18534) 0 Child (18535) 0 Parent (18534) 1 Child (18535) 1 Parent (18534) 2 Child (18535) 2 Parent (18534) 3 Child (18535) 3 Parent (18534) 4 Child (18535) 4 Source du programme /* futex_demo.c Usage: futex_demo [nloops] (Default: 5) Montrer l'utilisation des futex dans un programme ou le parent et l'enfant utilisent une paire de futex situee dans un tableau anonyme partage pour synchroniser l'acces a une ressource partagee : le terminal. Les processus ecrivent chacun des messages 'num-loops' sur le terminal et ils utilisent un protocole de synchronisation qui garantit qu'ils alternent l'ecriture des messages. */ #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #include #include static uint32_t *futex1, *futex2, *iaddr; static int futex(uint32_t *uaddr, int futex_op, uint32_t val, const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3) { return syscall(SYS_futex, uaddr, futex_op, val, timeout, uaddr2, val3); } /* Acquerir le futex vers lequel pointe 'futexp' : attendre que sa valeur passe a 1 puis positionner la valeur sur 0. */ static void fwait(uint32_t *futexp) { long s; const uint32_t one = 1; /* atomic_compare_exchange_strong(ptr, oldval, newval) fait atomiquement comme : if (*ptr == *oldval) *ptr = newval; Il renvoie true si le test a montre true et *ptr a ete mis a jour. */ while (1) { /* Le futex est-il disponible ? */ if (atomic_compare_exchange_strong(futexp, &one, 0)) break; /* Oui */ /* Le futex n'est pas disponible ; attendre. */ s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0); if (s == -1 && errno != EAGAIN) err(EXIT_FAILURE, "futex-FUTEX_WAIT"); } } /* Relacher le futex vers lequel pointe 'futexp' : si le futex a actuellement la valeur 0, positionner la valeur a 1 et reveiller tous les futex en attente pour que si le pair est bloque dans fwait(), ca puisse continuer. */ static void fpost(uint32_t *futexp) { long s; const uint32_t zero = 0; /* atomic_compare_exchange_strong() a ete decrit dans les commentaires ci-dessus. */ if (atomic_compare_exchange_strong(futexp, &zero, 1)) { s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0); if (s == -1) err(EXIT_FAILURE, "futex-FUTEX_WAKE"); } } int main(int argc, char *argv[]) { pid_t childPid; unsigned int nloops; setbuf(stdout, NULL); nloops = (argc > 1) ? atoi(argv[1]) : 5; /* Creer un tableau anonyme partage qui gardera les futex. Comme les futex vont etre partages entre les processus, nous utilisons donc les operations futex << shared >> (donc pas celles dont le suffixe est "_PRIVATE") */ iaddr = mmap(NULL, sizeof(*iaddr) * 2, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0); if (iaddr == MAP_FAILED) err(EXIT_FAILURE, "mmap"); futex1 = &iaddr[0]; futex2 = &iaddr[1]; *futex1 = 0; /* State: unavailable */ *futex2 = 1; /* State: available */ /* Creer un processus enfant qui herite du tableau anonyme partage. */ childPid = fork(); if (childPid == -1) err(EXIT_FAILURE, "fork"); if (childPid == 0) { /* Child */ for (unsigned int j = 0; j < nloops; j++) { fwait(futex1); printf("Child (%jd) %u\n", (intmax_t) getpid(), j); fpost(futex2); } exit(EXIT_SUCCESS); } /* Le parent se retrouve ici. */ for (unsigned int j = 0; j < nloops; j++) { fwait(futex2); printf("Parent (%jd) %u\n", (intmax_t) getpid(), j); fpost(futex1); } wait(NULL); exit(EXIT_SUCCESS); } VOIR AUSSI get_robust_list(2), restart_syscall(2), pthread_mutexattr_getprotocol(3), futex(7), sched(7) Les fichiers suivants des sources du noyau : - Documentation/pi-futex.txt - Documentation/futex-requeue-pi.txt - Documentation/locking/rt-mutex.txt - Documentation/locking/rt-mutex-design.txt - Documentation/robust-futex-ABI.txt Franke, H., Russell, R., and Kirwood, M., 2002. Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux (a partir des actions d'Ottawa Linux Symposium 2002), Hart, D., 2009. A futex overview and update, Hart, D. et Guniguntala, D., 2009. Requeue-PI: Making Glibc Condvars PI-Aware (a partir des comptes rendus de l'atelier Real-Time Linux 2009), Drepper, U., 2011. Futexes Are Tricky, La bibliotheque d'exemples de futex, futex-*.tar.bz2 a TRADUCTION La traduction francaise de cette page de manuel a ete creee par Christophe Blaess , Stephan Rafin , Thierry Vignaud , Francois Micaux, Alain Portal , Jean-Philippe Guerard , Jean-Luc Coulon (f5ibh) , Julien Cristau , Thomas Huriaux , Nicolas Francois , Florentin Duneau , Simon Paillard , Denis Barbier , David Prevot et Jean-Philippe MENGUAL Cette traduction est une documentation libre ; veuillez vous reporter a la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITE LEGALE. Si vous decouvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message a . Pages du manuel de Linux 6.06 31 octobre 2023 futex(2)