Soirée d'ouverture

Atomicité

Une instruction unique peut ressembler à une action indivisible alors qu'elle n'en est rien. Prenons l'exemple de l'ajout de cinq à une valeur en mémoire :

add qword [rel counter], 5

En réalité, le processeur ne sait pas ajouter directement à la mémoire. Il découpe cette unique instruction en trois étapes plus petites, appelées micro-opérations :

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

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é read-modify-write (RMW).

Note que la lecture (ou load) et l'écriture (ou store) sont des événements distincts, ce qui laisse une fenêtre de temps entre les deux. On ne le remarque généralement pas, car sur un cœur unique, 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é.

Cependant, les processeurs modernes ont rarement un seul cœur, et les applications s'exécutent souvent sur plusieurs cœurs à la fois, sans ordre défini entre eux. Lorsque plusieurs cœurs tournent au même instant, un autre cœur peut lire ou écrire counter à l'intérieur de la fenêtre, après le load de ce cœur et avant son store. Deux threads chargent chacun la même ancienne valeur, y ajoutent chacun cinq, et enregistrent 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 multi-thread.

Toutes les valeurs ne sont pas exposées de cette façon. Chaque thread possède ses propres registres et sa propre pile, si bien qu'une valeur conservée dans un registre, ou une variable locale sur la pile d'un thread, est propre à ce thread et ne peut pas entrer en course. Seule la mémoire que les threads partagent, comme counter ci-dessus, doit ê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 la traite, 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.

Échange atomique

L'instruction xchg échange deux opérandes. L'opérande de destination prend la valeur précédente de l'opérande source, tandis que l'opérande source prend 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 toujours, 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 préfixe lock

La façon la plus courante 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. Le cœur détient ainsi la mémoire de façon exclusive pendant tout le processus, si bien qu'aucun autre cœur ne peut lire ni é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 uniquement sur les instructions qui effectuent un read-modify-write sur 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.

Échange et addition

Un simple lock add met à jour la mémoire, mais jette l'ancienne valeur. Souvent, cette ancienne valeur est précisément ce que l'on veut, par exemple pour attribuer à chaque thread 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, il s'agit d'un fetch-and-add atomique. Exécuté par de nombreux threads 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 également renvoyée, une à chaque appelant.

Comparaison et échange

xadd additionne et xchg écrase, mais ni l'une ni l'autre 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, compare-and-exchange, 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.

Note que dest n'est modifiée que si elle est égale à 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, également 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 nouvelle tentative est le cœur des mises à jour sans verrou. La fenêtre entre la lecture et le compare-and-exchange est précisément le moment où un autre thread pourrait intervenir, et cmpxchg y remédie en refusant de stocker une valeur calculée à partir d'une lecture obsolète.

Ordonnancement mémoire

Jusqu'ici, chaque opération n'a touché qu'un seul emplacement. Lorsque des threads se coordonnent via plusieurs emplacements, une nouvelle question se pose : dans quel ordre les écritures d'un thread deviennent-elles visibles pour un autre ? Les règles qui répondent à cette question constituent l'ordonnancement mémoire du processeur.

Le concept sur le code sans branchement a introduit l'idée qu'un cœur moderne ne déroule pas les instructions une par une, laborieusement. Il en garde beaucoup en vol en même temps et prend de l'avance quand il le peut. Une écriture peut donc devenir visible aux autres cœurs plus tard que ne le suggère le programme, pendant que les instructions qui la suivent ont déjà été exécutées en avance.

x86-64 conserve un ordonnancement mémoire fort entre les loads et les stores ordinaires, si bien que sur chaque cœur :

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

Le seul réordonnancement possible est qu'un store semble se terminer après un load ultérieur portant sur 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 pouvoir la franchir, dans un sens comme dans l'autre. C'est pourquoi elles suffisent à garantir un ordre complet dans la plupart des situations.

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 à nouveau d'acquérir le verrou.
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, remettre 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 calcule le code. Elle indique au processeur qu'il s'agit d'une attente active. Le processeur peut alors réduire la consommation d'énergie du thread en attente et céder la place à un thread frère qui partage le même cœur. Une boucle d'attente active sans pause reste correcte, mais elle gaspille des ressources.

Une fois que le thread a terminé son travail, il peut libérer le verrou par un simple store de 0 avec mov. Un simple mov suffit, car sur x86-64 les loads et les stores ne sont jamais réordonnés après un store ultérieur. On dit qu'un store qui ne double jamais les accès qui le précèdent a un ordonnancement de libération, et sur x86 tout store ordinaire en bénéficie.