Opérations atomiques en

À propos de Opérations atomiques

Une seule instruction peut sembler être une action indivisible alors qu'elle n'en est rien. Prenons l'ajout de cinq à une valeur en mémoire :

add qword [rel counter], 5

Sous le capot, le processeur n'a pas de moyen d'ajouter directement à la mémoire. Il décompose cette instruction unique en trois étapes plus petites, appelées micro-opérations :

1. lire la valeur actuelle en mémoire ;
2. modifier cette valeur dans un registre, en y ajoutant cinq ;
3. écrire le résultat.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

C'est un schéma courant appelé lecture-modification-écriture (RMW).

Note que la lecture (ou le chargement) et l'écriture (ou le stockage) sont des événements distincts, ce qui laisse une fenêtre de temps entre eux. On ne s'en aperçoit généralement pas, car sur un seul cœur, chaque instruction a la garantie de produire son effet en entier avant la suivante. Cette fenêtre est donc invisible, et add se comporte comme une seule unité.

Toutefois, les processeurs modernes ont rarement un seul cœur, et les applications s'exécutent souvent sur plusieurs cœurs à la fois, sans aucun ordonnancement entre eux. Quand plusieurs cœurs s'exécutent au même instant, un autre cœur peut lire ou écrire counter à l'intérieur de cette fenêtre, après le chargement de ce cœur et avant son stockage. Deux fils d'exécution chargent chacun la même ancienne valeur, y ajoutent chacun cinq, et stockent chacun leur résultat. Deux additions ont eu lieu, mais la valeur n'a augmenté que de cinq. Une mise à jour a été silencieusement perdue.

C'est une course de données, un problème courant dans le code multithread.

Ce n'est pas le cas de toutes les valeurs. Chaque fil d'exécution possède ses propres registres et sa propre pile, donc une valeur conservée dans un registre, ou une variable locale sur la pile d'un fil, est exclusive à ce fil et ne peut pas entrer en course. Seule la mémoire partagée entre les fils, comme counter ci-dessus, a besoin d'être protégée.

x86-64 propose un ensemble d'instructions pour résoudre ce problème, en rendant une instruction indivisible. Elle se comporte comme une seule unité, non seulement pour le cœur qui l'exécute, mais aussi pour tous les autres cœurs. Une opération qui tient d'un seul bloc, qu'aucun autre cœur ne peut scinder, est dite atomique.

L'échange atomique

L'instruction xchg échange deux opérandes. L'opérande de destination devient égal à la valeur précédente de l'opérande source, tandis que l'opérande source devient égal à la valeur précédente de l'opérande de destination. Conceptuellement, on peut la voir comme deux instructions mov qui se produisent en même temps.

Comme d'habitude, on peut l'utiliser avec deux opérandes de registre ou avec un opérande mémoire et un opérande de registre :

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Lorsqu'elle est utilisée avec un opérande mémoire, xchg est toujours atomique. Le processeur pose un verrou sur l'emplacement pendant toute la durée de l'opération, le même mécanisme que le préfixe lock utilise pour d'autres instructions, décrit plus bas.

Le préfixe lock

Le moyen le plus courant de rendre une instruction atomique en x86-64 est d'ajouter le préfixe lock. Il fusionne la lecture, la modification et l'écriture en une seule étape indivisible. Cela signifie que le cœur détient la mémoire de façon exclusive pendant toute l'opération, si bien qu'aucun autre cœur ne peut lire ou écrire cet emplacement entre-temps.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock ne fonctionne que lorsque la destination est en mémoire, et seulement sur les instructions qui effectuent une lecture-modification-écriture de cette mémoire :

1. les opérations arithmétiques, comme add, sub, inc, dec, neg ;
2. les opérations bit à bit, comme and, or, xor, not ;
3. les opérations sur les bits bts, btr, btc ;
4. quelques autres instructions dédiées, comme xadd et cmpxchg, décrites plus bas.

Sur toute autre instruction, comme un simple mov, le préfixe est invalide et le processeur déclenche une faute d'opcode invalide. Un chargement ou un stockage isolé n'a pas besoin de préfixe : un accès naturellement aligné est déjà atomique en soi.

Opérations atomiques sur les bits

Parmi les instructions verrouillables, les tests de bits se marient naturellement avec le verrou tournant présenté à la fin de ce document. Chacune des instructions bts, btr et btc copie un bit choisi dans l'indicateur de retenue, puis le positionne, l'efface ou l'inverse. Avec le préfixe lock, cela devient une lecture-modification-écriture d'un seul bit : le bit est modifié de façon atomique, et CF indique sa valeur précédente.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

Un positionnement qui trouve le bit déjà positionné signifie qu'un autre fil l'a revendiqué en premier. C'est la version à un seul bit de la revendication de drapeau que xchg effectue sur un mot entier.

Échange et addition

Un simple lock add met à jour la mémoire mais jette l'ancienne valeur. Souvent, l'ancienne valeur est exactement ce que l'on veut, par exemple pour attribuer à chaque fil un numéro de ticket distinct.

L'instruction xadd (le x pour échange) renvoie la valeur précédente tout en effectuant l'addition. Elle écrit la somme dans la destination et laisse la valeur d'origine de la destination dans le registre source.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Avec le préfixe lock, c'est un fetch-and-add atomique. Exécuté par de nombreux fils sur le même compteur, chaque appel renvoie une ancienne valeur différente.

Comme avec lock add, le compteur finit à exactement le nombre d'appels. Cependant, contrairement à lock add, chaque valeur intermédiaire est renvoyée elle aussi, une à chaque appelant.

La source peut être n'importe quel registre à usage général, et la largeur des opérandes va d'un octet à un quadword. Ajouter une valeur négative transforme la même instruction en un fetch-and-subtract.

Comparaison et échange

xadd additionne et xchg écrase, mais aucune des deux ne peut faire dépendre la nouvelle valeur de la valeur actuelle et ne l'appliquer que si rien n'a changé entre-temps. C'est cette mise à jour conditionnelle que fournit cmpxchg, la comparaison-échange, et c'est la plus générale de ces primitives.

cmpxchg dest, src utilise rax comme accumulateur implicite et le compare à dest :

• Si dest == rax, alors dest = src et ZF = 1.
• Si dest != rax, alors rax = dest et ZF = 0.

L'accumulateur suit la taille de l'opérande : al pour un octet, puis ax, eax et rax pour les tailles plus grandes.

Note que dest n'est mis à jour que lorsqu'il est égal à la valeur attendue, préalablement chargée dans rax. Cette égalité garantit que dest contient toujours la valeur à partir de laquelle la nouvelle a été calculée, de sorte qu'une mise à jour fondée sur une lecture obsolète n'est jamais appliquée. Cela fait de cmpxchg la brique de base d'une mise à jour atomique, aussi appelée compare-and-swap (CAS) :

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Cette boucle de réessai est le cœur des mises à jour sans verrou. La fenêtre entre la lecture et la comparaison-échange est exactement le moment où un autre fil pourrait intervenir, et cmpxchg l'intercepte en refusant de stocker une valeur calculée à partir d'une lecture obsolète.

Une subtilité mérite d'être connue. cmpxchg vérifie que la valeur est égale à celle qui a été lue, et non que l'emplacement n'a jamais été touché. Si un autre fil fait passer la valeur de A à B puis de nouveau à A à l'intérieur de la fenêtre, l'échange réussit quand même, même si le monde a changé entre-temps.

Pour un simple compteur, c'est sans conséquence, puisqu'un compte égal est un compte tout aussi valable. Pour une adresse mémoire en tête d'une liste sans verrou, ce n'est pas le cas, car la même adresse peut désormais mener ailleurs. C'est le problème ABA.

La solution habituelle à ce problème associe la valeur à une « estampille », par exemple un compteur qui ne fait que croître. Comme l'estampille ne fait qu'avancer, une estampille identique prouve que l'emplacement n'a pas été touché entre-temps, et pas seulement qu'il semble inchangé.

Pour que cela fonctionne dans un environnement multithread, il faut toutefois que l'adresse mémoire et son estampille soient mises à jour ensemble. Comme une adresse mémoire occupe un qword entier en x86-64, un cmpxchg ne suffit pas à la mettre à jour en même temps qu'une autre valeur.

Il existe une instruction de largeur double appelée cmpxchg16b, sémantiquement identique à cmpxchg mais qui opère sur 16 octets à la fois et peut être utilisée dans cette situation. Elle n'a pas d'opérande source et utilise plutôt rcx:rbx comme valeur de remplacement. Son seul opérande est un emplacement mémoire aligné sur 16 octets. Cette instruction utilise aussi rdx:rax comme accumulateur, au lieu du seul rax.

Ordonnancement mémoire

Toutes les opérations vues jusqu'ici ne touchaient qu'un seul emplacement. Quand des fils se coordonnent via plusieurs emplacements, une nouvelle question se pose : dans quel ordre les écritures d'un fil deviennent-elles visibles pour un autre. Les règles qui répondent à cette question constituent l'ordonnancement mémoire du processeur.

Le concept branchless-code a introduit l'idée qu'un cœur moderne ne progresse pas laborieusement instruction par instruction. Il en garde beaucoup en cours d'exécution à la fois et prend de l'avance là où il le peut. Ainsi, une écriture peut devenir visible pour les autres cœurs plus tard que ne le suggère le programme, alors que les instructions qui la suivent ont déjà pris de l'avance.

x86-64 maintient un ordonnancement mémoire fort entre les chargements et les stockages ordinaires, de sorte que, sur chaque cœur :

1. un chargement n'est jamais réordonné après un chargement ultérieur ;
2. un stockage n'est jamais réordonné après un stockage ultérieur ;
3. un chargement n'est jamais réordonné après un stockage ultérieur.

Le seul réordonnancement possible est celui d'un stockage qui semble s'achever après un chargement ultérieur d'une adresse différente.

Une instruction préfixée par lock, ou un xchg avec un opérande mémoire, constitue une barrière complète : rien ne semble la traverser dans un sens ou dans l'autre. C'est pourquoi elles suffisent à garantir un ordonnancement complet dans la plupart des situations.

Le mécanisme à l'origine du seul réordonnancement qui subsiste est le tampon d'écriture. Pour continuer à prendre de l'avance, un cœur gare chaque stockage dans ce tampon et laisse les instructions suivantes progresser avant que le stockage n'atteigne la mémoire visible par les autres cœurs. Une écriture suivie de la lecture d'un emplacement différent peut donc sembler se produire dans le désordre : l'écriture peut encore se trouver dans le tampon pendant que la lecture ultérieure passe devant. Ce modèle, où tout est ordonné sauf ce trou entre l'écriture et la lecture, s'appelle le total store order.

Ce seul trou suffit à briser une poignée de main de type « écrire puis vérifier ». Si deux fils écrivent chacun leur propre drapeau puis lisent celui de l'autre, les deux lectures peuvent renvoyer une valeur non positionnée, car aucun des deux stockages n'a encore quitté son tampon d'écriture. L'instruction mfence comble ce trou en vidant le tampon d'écriture : toute écriture qui la précède devient visible avant toute lecture qui la suit.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

Il existe aussi deux barrières plus étroites :

• sfence ordonne les écritures les unes par rapport aux autres et intervient surtout avec les stockages non temporels ;
• lfence ordonne les lectures.

Pour les schémas atomiques ordinaires présentés plus haut, les instructions préfixées par lock portent déjà un ordonnancement complet, si bien qu'une barrière explicite n'est nécessaire que pour une poignée de main construite à partir de simples stockages et chargements comme celle ci-dessus.

Ces garanties portent des noms qui dépassent le cadre de x86. Une opération a un ordonnancement acquire lorsque aucun accès ultérieur ne peut sembler passer avant elle, et un ordonnancement release lorsque aucun accès antérieur ne peut sembler passer après elle. Sur x86, tout chargement est un acquire, tout stockage est un release, et une instruction préfixée par lock, ou un xchg avec la mémoire, est les deux à la fois.

Attente active et pause

Les instructions qui positionnent un drapeau tout en renvoyant son état précédent sont appelées test-and-set. Elles peuvent servir de base à un verrou tournant, garantissant qu'un cœur dispose d'un accès exclusif à une partie du code.

Voici l'algorithme général, qui utilise l'instruction xchg avec un drapeau binaire :

1. Le drapeau commence à 0.
2. Pour acquérir le verrou, un cœur échange la valeur du drapeau avec 1.
3. Si la valeur renvoyée est 1, cela signifie que le verrou est détenu par un autre cœur. Le cœur courant attend alors et essaie d'acquérir le verrou à nouveau.
4. Si la valeur renvoyée est 0, cela signifie que le verrou était libre. xchg l'a maintenant mis à 1, et les autres cœurs attendront que ce cœur le libère.
5. Une fois que le cœur courant a terminé son travail, mettre le drapeau à 0 libère le verrou.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

L'instruction pause dans la boucle d'attente ne change rien à ce que le code calcule. Elle indique au processeur qu'il s'agit d'une attente active. Le processeur peut alors réduire la consommation d'énergie du fil en attente et céder la place à un fil frère qui partage le même cœur. Une boucle d'attente active sans pause reste correcte, mais elle gaspille des ressources.

Note que dans un test-and-set, une instruction comme xchg positionne toujours le drapeau, même s'il était déjà positionné. Cela signifie qu'elle obtient un accès exclusif à la mémoire à chaque tour de boucle, même lorsqu'il est probable que le verrou soit encore détenu.

Il existe une variante de cet algorithme, appelée test-and-test-and-set, qui teste (lit) d'abord le drapeau pour vérifier s'il est déjà positionné. Elle ne tente ensuite le test-and-set (le xchg dans ce cas) qu'une fois que le verrou semble libre :

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

Une fois que le fil a terminé son travail, il peut libérer le verrou par un simple stockage de 0 avec mov. Un simple mov suffit, car en x86-64 les chargements et les stockages ne sont jamais réordonnés après un stockage ultérieur. Un stockage qui ne dépasse jamais les accès qui le précèdent est dit avoir un ordonnancement release, et sur x86 tout stockage simple en bénéficie.