Atomics in

Über Atomics

Ein einzelner Befehl kann wie eine unteilbare Aktion aussehen, obwohl er nichts dergleichen ist. Nimm etwa das Addieren von fünf zu einem Wert im Speicher:

add qword [rel counter], 5

Unter der Haube kann der Prozessor nicht direkt zu einer Speicherstelle addieren. Er zerlegt diesen einen Befehl in drei kleinere Schritte, genannt Mikrooperationen:

1. Lies den aktuellen Wert aus dem Speicher;
2. Ändere diesen Wert in einem Register, indem du fünf addierst;
3. Schreibe das Ergebnis zurück.

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

Das ist ein verbreitetes Muster namens Read-Modify-Write (RMW).

Beachte, dass das Lesen (oder Laden) und das Schreiben (oder Speichern) getrennte Ereignisse sind, sodass zwischen ihnen ein Zeitfenster liegt. Normalerweise fällt uns das nicht auf, weil auf einem einzelnen Kern garantiert wird, dass jeder Befehl seine volle Wirkung zeigt, bevor der nächste an die Reihe kommt. Dieses Fenster ist daher unsichtbar, und add verhält sich wie eine einzelne Einheit.

Moderne CPUs haben jedoch selten nur einen Kern, und Anwendungen laufen oft gleichzeitig auf vielen Kernen, ohne dass zwischen ihnen eine Reihenfolge besteht. Wenn mehrere Kerne im selben Augenblick laufen, kann ein anderer Kern counter innerhalb des Fensters lesen oder schreiben, nach dem Laden dieses Kerns und vor seinem Speichern. Zwei Threads laden jeweils denselben alten Wert, addieren jeweils fünf und speichern jeweils ihr Ergebnis. Es fanden zwei Additionen statt, aber der Wert hat sich nur um fünf erhöht. Eine Aktualisierung ging stillschweigend verloren.

Das ist ein Datenrennen, und es ist ein häufiges Problem in Multithread-Code.

Nicht jeder Wert ist dem ausgesetzt. Jeder Thread hat seine eigenen Register und seinen eigenen Stack, daher ist ein Wert in einem Register oder eine lokale Variable auf dem Stack eines Threads exklusiv für diesen Thread und kann nicht in ein Rennen geraten. Nur der Speicher, den die Threads gemeinsam nutzen, wie counter oben, muss geschützt werden.

x86-64 bietet eine Reihe von Befehlen, um dieses Problem zu lösen, indem ein Befehl unteilbar gemacht wird. Er verhält sich nicht nur für den Kern, der ihn ausführt, wie eine einzelne Einheit, sondern auch für jeden anderen Kern. Eine Operation, die zusammenhält, die kein anderer Kern aufteilen kann, heißt atomar.

Atomarer Austausch

Der xchg-Befehl vertauscht zwei Operanden. Der Zieloperand wird gleich dem vorherigen Wert im Quelloperanden, während der Quelloperand gleich dem vorherigen Wert im Zieloperanden wird. Konzeptionell kann man sich das als zwei mov-Befehle vorstellen, die gleichzeitig stattfinden.

Wie üblich kann er mit zwei Registeroperanden oder mit einem Speicheroperanden und einem Registeroperanden verwendet werden:

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

Wenn er mit einem Speicheroperanden verwendet wird, ist xchg immer atomar. Der Prozessor setzt für die Dauer ein Lock auf die Speicherstelle, denselben Mechanismus, den auch das lock-Präfix für andere Befehle nutzt; es wird als Nächstes beschrieben.

Das Lock-Präfix

Die gebräuchlichste Art, einen Befehl in x86-64 atomar zu machen, ist das Hinzufügen des lock-Präfixes. Es verschmilzt das Lesen, das Ändern und das Schreiben zu einem unteilbaren Schritt. Das heißt, der Kern hält den Speicher während des gesamten Vorgangs exklusiv, sodass kein anderer Kern diese Stelle dazwischen lesen oder schreiben kann.

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

lock funktioniert nur, wenn das Ziel eine Speicherstelle ist, und nur bei Befehlen, die diesen Speicher lesen, ändern und schreiben:

1. arithmetische Operationen wie add, sub, inc, dec, neg;
2. bitweise Operationen wie and, or, xor, not;
3. die Bitoperationen bts, btr, btc;
4. einige andere spezialisierte Befehle wie xadd und cmpxchg, die weiter unten beschrieben werden.

Bei jedem anderen Befehl, etwa einem einfachen mov, ist das Präfix ungültig, und der Prozessor löst eine Ausnahme für einen ungültigen Opcode aus. Ein einzelnes Laden oder ein einzelnes Speichern braucht kein Präfix: Ein natürlich ausgerichteter Zugriff ist bereits von sich aus atomar.

Atomare Bitoperationen

Unter den sperrbaren Befehlen passen die Bittests natürlich zum Spinlock am Ende dieses Dokuments. Jeder von bts, btr und btc kopiert ein ausgewähltes Bit in das Carry-Flag und setzt, löscht oder invertiert es dann. Mit dem lock-Präfix wird daraus ein Read-Modify-Write über ein einzelnes Bit: Das Bit wird atomar geändert, und CF meldet, wie sein Wert vorher war.

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

Ein Setzen, das das Bit bereits gesetzt vorfindet, bedeutet, dass ein anderer Thread es zuerst beansprucht hat. Das ist eine Ein-Bit-Version des Beanspruchens eines Flags, das xchg für ein ganzes Wort erledigt.

Austausch und Addition

Ein einfaches lock add aktualisiert den Speicher, verwirft aber den alten Wert. Oft ist der alte Wert genau das, was gewünscht ist, zum Beispiel um jedem Thread eine eigene Ticketnummer zuzuweisen.

Der Befehl xadd (x steht für exchange) gibt den vorherigen Wert zurück, während er addiert. Er schreibt die Summe in das Ziel und lässt den ursprünglichen Zielwert im Quellregister.

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

Mit dem lock-Präfix ist das ein atomares Fetch-and-Add. Von vielen Threads auf demselben Zähler ausgeführt, liefert jeder Aufruf einen anderen alten Wert.

Wie bei lock add endet der Zähler bei der exakten Anzahl der Aufrufe. Anders als bei lock add wird jedoch auch jeder Zwischenwert zurückgegeben, einer an jeden Aufrufer.

Die Quelle kann ein beliebiges Allzweckregister sein, und die Operandenbreite reicht von einem Byte bis zu einem Quadword. Das Addieren eines negativen Werts macht denselben Befehl zu einem Fetch-and-Subtract.

Vergleichen und Austauschen

xadd addiert, und xchg überschreibt, aber keiner von beiden kann den neuen Wert vom aktuellen Wert abhängig machen und ihn nur dann anwenden, wenn sich darunter nichts geändert hat. Diese bedingte Aktualisierung bietet cmpxchg, Compare-and-Exchange, und es ist die allgemeinste dieser Grundoperationen.

cmpxchg dest, src verwendet rax als impliziten Akkumulator und vergleicht ihn mit dest:

• Wenn dest == rax, dann dest = src und ZF = 1.
• Wenn dest != rax, dann rax = dest und ZF = 0.

Der Akkumulator folgt der Operandengröße: al für ein Byte, dann ax, eax und rax für die breiteren Formen.

Beachte, dass dest nur aktualisiert wird, wenn es gleich dem erwarteten Wert ist, der zuvor in rax geladen wurde. Diese Gleichheit stellt sicher, dass dest noch den Wert enthält, aus dem der neue berechnet wurde, sodass eine Aktualisierung auf Basis eines veralteten Lesevorgangs nie angewendet wird. Das macht cmpxchg zum Baustein für eine atomare Aktualisierung, auch bekannt als 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

Diese Wiederholungsschleife ist das Herzstück lockfreier Aktualisierungen. Das Fenster zwischen dem Lesen und dem Compare-and-Exchange ist genau der Moment, in dem ein anderer Thread eingreifen könnte, und cmpxchg erkennt das, indem es sich weigert, einen aus einem veralteten Lesevorgang berechneten Wert zu speichern.

Eine Feinheit sollte man kennen. cmpxchg prüft, dass der Wert gleich dem gelesenen ist, nicht, dass die Speicherstelle nie berührt wurde. Wenn ein anderer Thread den Wert innerhalb des Fensters von A nach B und zurück nach A bewegt, gelingt der Austausch trotzdem, obwohl sich die Welt darunter geändert hat.

Bei einem einfachen Zähler ist das harmlos, denn ein gleicher Zählerstand ist ein ebenso guter Zählerstand. Bei einer Speicheradresse am Kopf einer lockfreien Liste ist es das nicht, weil dieselbe Adresse jetzt woanders hinführen kann. Das ist das ABA-Problem.

Die übliche Lösung für dieses Problem kombiniert den Wert mit einem „Stempel“, zum Beispiel einem Zähler, der nur wächst. Da der Stempel immer weiter voranschreitet, beweist ein übereinstimmender Stempel, dass die Speicherstelle zwischenzeitlich nicht berührt wurde, und nicht bloß, dass sie unverändert aussieht.

Damit das in einer Multithread-Umgebung funktioniert, müssen jedoch sowohl die Speicheradresse als auch ihr Stempel zusammen aktualisiert werden. Da eine Speicheradresse in x86-64 ein volles Quadword ist, reicht ein cmpxchg nicht aus, um sie und gleichzeitig einen anderen Wert zu aktualisieren.

Es gibt einen doppelt breiten Befehl namens cmpxchg16b, der semantisch dasselbe ist wie cmpxchg, aber auf 16 Bytes gleichzeitig arbeitet und in dieser Situation verwendet werden kann. Er hat keinen Quelloperanden, sondern verwendet rcx:rbx als Ersatzwert. Sein einziger Operand ist eine 16-Byte-ausgerichtete Speicherstelle. Dieser Befehl verwendet außerdem rdx:rax als Akkumulator statt nur rax.

Speicherordnung

Jede bisherige Operation hat eine einzelne Speicherstelle berührt. Wenn Threads über mehr als eine Speicherstelle koordinieren, taucht eine neue Frage auf: In welcher Reihenfolge werden die Schreibvorgänge eines Threads für einen anderen sichtbar? Die Regeln, die diese Frage beantworten, sind die Speicherordnung des Prozessors.

Das Konzept Branchless-Code hat die Idee eingeführt, dass ein moderner Kern nicht Befehl für Befehl dahinstapft. Er hält viele gleichzeitig in der Ausführung und läuft voraus, wo er kann. Das bedeutet, dass ein Schreibvorgang für die anderen Kerne später sichtbar werden kann, als das Programm vermuten lässt, während Befehle danach bereits vorausgegangen sind.

x86-64 hält eine starke Speicherordnung zwischen gewöhnlichen Lade- und Schreibvorgängen aufrecht, sodass auf jedem Kern gilt:

1. Ein Ladevorgang wird nie hinter einen späteren Ladevorgang verschoben;
2. Ein Schreibvorgang wird nie hinter einen späteren Schreibvorgang verschoben;
3. Ein Ladevorgang wird nie hinter einen späteren Schreibvorgang verschoben.

Die einzig mögliche Umordnung ist, dass ein Schreibvorgang nach einem späteren Ladevorgang einer anderen Adresse abgeschlossen zu sein scheint.

Ein mit lock präfixierter Befehl oder ein xchg mit Speicheroperand ist eine vollständige Barriere: Nichts scheint sich in irgendeine Richtung über sie hinweg zu bewegen. Deshalb reichen sie aus, um in den meisten Situationen die vollständige Reihenfolge sicherzustellen.

Der Mechanismus hinter der einen verbleibenden Umordnung ist der Store-Puffer. Um weiter vorauslaufen zu können, stellt ein Kern jeden Schreibvorgang in diesem Puffer ab und lässt spätere Befehle weiterlaufen, bevor der Schreibvorgang den Speicher erreicht, den die anderen Kerne sehen können. Ein Schreibvorgang, gefolgt von einem Lesevorgang einer anderen Speicherstelle, kann daher außer der Reihe erscheinen: Der Schreibvorgang kann noch im Puffer liegen, während der spätere Lesevorgang weiterläuft. Dieses Modell, in dem alles geordnet ist außer dieser Lücke zwischen Schreiben und Lesen, heißt Total Store Order.

Diese einzelne Lücke reicht aus, um einen Schreiben-dann-Prüfen-Handshake zu brechen. Wenn zwei Threads jeweils ihr eigenes Flag schreiben und dann das des anderen lesen, können beide Lesevorgänge ungesetzt zurückkommen, weil noch kein Schreibvorgang seinen Store-Puffer verlassen hat. Der Befehl mfence schließt die Lücke, indem er den Store-Puffer leert: Jeder Schreibvorgang vor ihm wird sichtbar, bevor ein Lesevorgang nach ihm ausgeführt wird.

    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

Es gibt auch zwei schmalere Barrieren:

• sfence ordnet Schreibvorgänge zueinander und ist vor allem bei den Streaming- oder Non-Temporal-Schreibvorgängen wichtig;
• lfence ordnet Lesevorgänge.

Für die gewöhnlichen atomaren Muster oben tragen die mit lock präfixierten Befehle bereits die vollständige Ordnung, sodass eine explizite Barriere nur für einen Handshake nötig ist, der aus einfachen Speicher- und Ladevorgängen wie dem obigen aufgebaut ist.

Diese Garantien haben Namen, die über x86 hinausreichen. Eine Operation hat Acquire-Ordnung, wenn kein späterer Zugriff vor sie zu wandern scheint, und Release-Ordnung, wenn kein früherer Zugriff nach ihr zu wandern scheint. Auf x86 ist jeder Ladevorgang ein Acquire, jeder Schreibvorgang ein Release, und ein mit lock präfixierter Befehl oder ein xchg mit Speicher ist beides zugleich.

Spin-Warten und pause

Befehle, die ein Flag setzen und gleichzeitig seinen vorherigen Zustand zurückgeben, sind als Test-and-Set bekannt. Sie können als Grundlage für einen Spinlock dienen, der sicherstellt, dass ein Kern exklusiven Zugriff auf einen Teil des Codes hat.

Das ist der Gesamtablauf, der den Befehl xchg mit einem binären Flag verwendet:

1. Das Flag beginnt bei 0.
2. Um die Sperre zu erhalten, vertauscht ein Kern den Wert im Flag mit 1.
3. Wenn der zurückgegebene Wert 1 ist, bedeutet das, dass die Sperre von einem anderen Kern gehalten wird. Der aktuelle Kern wartet dann und versucht erneut, die Sperre zu erhalten.
4. Wenn der zurückgegebene Wert 0 ist, bedeutet das, dass die Sperre frei war. xchg hat sie nun auf 1 gesetzt, und andere Kerne warten, bis dieser Kern sie freigibt.
5. Sobald der aktuelle Kern seine Arbeit beendet hat, gibt die Aktualisierung des Flags mit 0 die Sperre frei.

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

Der pause-Befehl in der Warteschleife ändert nicht, was der Code berechnet. Er gibt dem Prozessor einen Hinweis, dass dies ein Spin-Wait ist. Die CPU kann dann den Stromverbrauch des wartenden Threads reduzieren und einem weiteren Thread, der denselben Kern nutzt, den Vortritt lassen. Eine Spin-Schleife ohne pause ist immer noch korrekt, nur verschwenderisch.

Beachte, dass ein Befehl wie xchg in einem Test-and-Set das Flag immer setzt, selbst wenn es bereits gesetzt war. Das bedeutet, dass er bei jedem Spin exklusiven Zugriff auf den Speicher erhält, selbst wenn die Sperre wahrscheinlich noch gehalten wird.

Es gibt eine Variante dieses Algorithmus, bekannt als Test-and-Test-and-Set, die zuerst das Flag testet (liest), um zu prüfen, ob es bereits gesetzt ist. Sie versucht das Test-and-Set (in diesem Fall xchg) erst dann, wenn die Sperre frei aussieht:

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

Sobald der Thread seine Arbeit beendet hat, kann er die Sperre mit einem einfachen Schreibvorgang von 0 mithilfe von mov freigeben. Mehr als ein mov ist nicht nötig, weil auf x86-64 Lade- und Schreibvorgänge nie hinter einen späteren Schreibvorgang verschoben werden. Ein Schreibvorgang, der die Zugriffe vor ihm nie überholt, hat Release-Ordnung, und auf x86 trägt jeder einfache Schreibvorgang sie.