Wo ist die Sperre für ein std :: atomic?

71

Wenn eine Datenstruktur mehrere Elemente enthält, kann die atomare Version nicht (immer) sperrfrei sein. Mir wurde gesagt, dass dies für größere Typen gilt, da die CPU die Daten nicht atomar ändern kann, ohne eine Art Sperre zu verwenden.

zum Beispiel:

#include <iostream>
#include <atomic>

struct foo {
    double a;
    double b;
};

std::atomic<foo> var;

int main()
{
    std::cout << var.is_lock_free() << std::endl;
    std::cout << sizeof(foo) << std::endl;
    std::cout << sizeof(var) << std::endl;
}

Die Ausgabe (Linux / gcc) ist:

0
16
16

Da das Atom und foodie gleiche Größe haben, glaube ich nicht, dass ein Schloss im Atom gespeichert ist.

Meine Frage ist:
Wenn eine atomare Variable eine Sperre verwendet, wo wird sie gespeichert und was bedeutet das für mehrere Instanzen dieser Variablen?

neugieriger Kerl12
quelle
3
Haben Sie es mit einem größeren Typ als nur 16 Bytes versucht? Ich bin mit der x86-Architektur nicht besonders vertraut, aber wenn sie einen einzigen CAS-Befehl für 16 Bytes hätte, der die Notwendigkeit einer expliziten Sperre ausschließen würde, wäre ich nicht überrascht.
Xirema
6
@Xirema In diesem Fall würde ich erwarten is_lock_free()zu seintrue.
François Andrieux
5
@Xirema: gcc / clang unter x86-64 Linux wird verwendet, lock cmpxchg16bfalls verfügbar, aber gcc7 und höher geben immer noch false zurück is_lock_free, obwohl dies technisch gesehen der Fall ist. Aber reine Ladungen und reine Speicher sind langsam und reine Ladungen konkurrieren miteinander. Unter is_lock_free (), das nach dem Upgrade auf MacPorts gcc 7.3 false zurückgegeben hat, finden Sie Links zu weiteren Details zu dieser Entwurfsentscheidung.
Peter Cordes
12
@ James Nein, dies besiegt den Zweck von std :: atomic.
Benjarobin
8
Wie pro github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/... , Klappern (und wahrscheinlich gcc) verwenden , um die Adresse des Atom als ein Index in einer Hash-Karte von Schlössern.
Frank

Antworten:

54

Der einfachste Weg, solche Fragen zu beantworten, besteht im Allgemeinen darin, sich die resultierende Baugruppe anzusehen und sie von dort zu übernehmen.

Kompilieren Sie Folgendes (Ich habe Ihre Struktur vergrößert, um schlauen Compiler-Spielereien auszuweichen):

#include <atomic>

struct foo {
    double a;
    double b;
    double c;
    double d;
    double e;
};

std::atomic<foo> var;

void bar()
{
    var.store(foo{1.0,2.0,1.0,2.0,1.0});
}

In Clang 5.0.0 ergibt sich unter -O3 folgendes: siehe auf Godbolt

bar(): # @bar()
  sub rsp, 40
  movaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [1.000000e+00,2.000000e+00]
  movaps xmmword ptr [rsp], xmm0
  movaps xmmword ptr [rsp + 16], xmm0
  movabs rax, 4607182418800017408
  mov qword ptr [rsp + 32], rax
  mov rdx, rsp
  mov edi, 40
  mov esi, var
  mov ecx, 5
  call __atomic_store

Großartig, der Compiler delegiert an ein intrinsic ( __atomic_store), das sagt uns nicht, was hier wirklich los ist. Da der Compiler jedoch Open Source ist, können wir die Implementierung des Intrinsic leicht finden (ich habe sie unter https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c gefunden ):

void __atomic_store_c(int size, void *dest, void *src, int model) {
#define LOCK_FREE_ACTION(type) \
    __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\
    return;
  LOCK_FREE_CASES();
#undef LOCK_FREE_ACTION
  Lock *l = lock_for_pointer(dest);
  lock(l);
  memcpy(dest, src, size);
  unlock(l);
}

Es scheint, als ob die Magie in passiert lock_for_pointer(), also schauen wir uns das an:

static __inline Lock *lock_for_pointer(void *ptr) {
  intptr_t hash = (intptr_t)ptr;
  // Disregard the lowest 4 bits.  We want all values that may be part of the
  // same memory operation to hash to the same value and therefore use the same
  // lock.  
  hash >>= 4;
  // Use the next bits as the basis for the hash
  intptr_t low = hash & SPINLOCK_MASK;
  // Now use the high(er) set of bits to perturb the hash, so that we don't
  // get collisions from atomic fields in a single object
  hash >>= 16;
  hash ^= low;
  // Return a pointer to the word to use
  return locks + (hash & SPINLOCK_MASK);
}

Und hier ist unsere Erklärung: Die Adresse des Atoms wird verwendet, um einen Hash-Schlüssel zur Auswahl eines vorab zugewiesenen Schlosses zu generieren.

Frank
quelle
1
Mit godbolt.org können Sie auf einfache Weise Assemblys für verschiedene Compiler generieren und freigeben .
François Andrieux
19
@ FrançoisAndrieux ja, ich weiß. Meine persönliche Präferenz ist es, Godbolt-Links in Kommentaren zu verwenden, aber die Ergebnisse beim Schreiben von Antworten tatsächlich kopieren und einfügen, damit sie vollständig in sich geschlossen bleiben (wenn die Versammlung kurz genug ist)
Frank
65

Die übliche Implementierung ist eine Hash-Tabelle mit Mutexen (oder auch nur einfachen Spinlocks ohne Rückgriff auf OS-unterstütztes Sleep / Wakeup), wobei die Adresse des atomaren Objekts als Schlüssel verwendet wird . Die Hash-Funktion ist möglicherweise so einfach wie die Verwendung der niedrigen Bits der Adresse als Index für ein Array mit einer Potenz von 2, aber die Antwort von @ Frank zeigt, dass die std :: atomic-Implementierung von LLVM XOR in einigen höheren Bits ausführt, sodass Sie dies nicht tun. t erhält automatisch ein Aliasing, wenn Objekte durch eine große Zweierpotenz getrennt sind (was häufiger vorkommt als bei jeder anderen zufälligen Anordnung).

Ich denke (aber ich bin nicht sicher), dass g ++ und clang ++ ABI-kompatibel sind; Das heißt, sie verwenden dieselbe Hash-Funktion und Tabelle, sodass sie sich darauf einigen, welche Sperre den Zugriff auf welches Objekt serialisiert. Das Sperren erfolgt jedoch vollständig in libatomic. Wenn Sie also dynamisch verknüpfen, verwendet der libatomicgesamte Code innerhalb desselben Programms, das aufgerufen __atomic_store_16wird, dieselbe Implementierung. clang ++ und g ++ sind sich definitiv einig, welche Funktionsnamen aufgerufen werden sollen, und das ist genug. (Beachten Sie jedoch, dass nur sperrfreie atomare Objekte im gemeinsam genutzten Speicher zwischen verschiedenen Prozessen funktionieren: Jeder Prozess verfügt über eine eigene Hash-Tabelle mit Sperren . Sperrenfreie Objekte sollen (und tatsächlich) nur im gemeinsam genutzten Speicher auf einer normalen CPU arbeiten Architekturen, auch wenn die Region unterschiedlichen Adressen zugeordnet ist.)

Hash-Kollisionen bedeuten, dass zwei atomare Objekte möglicherweise dieselbe Sperre verwenden. Dies ist kein Korrektheitsproblem, aber es könnte ein Leistungsproblem sein : Anstatt zwei Threadpaare, die separat um zwei verschiedene Objekte miteinander konkurrieren, könnten alle vier Threads um den Zugriff auf eines der beiden Objekte kämpfen. Vermutlich ist das ungewöhnlich, und normalerweise möchten Sie, dass Ihre atomaren Objekte auf den Plattformen, die Sie interessieren, frei von Sperren sind. Aber die meiste Zeit hat man nicht wirklich Pech und es ist im Grunde in Ordnung.

Deadlocks sind nicht möglich, da es keine std::atomicFunktionen gibt, die versuchen, zwei Objekte gleichzeitig zu sperren. Der Bibliothekscode, der die Sperre übernimmt, versucht also niemals, eine andere Sperre zu aktivieren, während er eine dieser Sperren hält. Zusätzliche Konflikte / Serialisierungen sind kein Korrektheitsproblem, sondern nur die Leistung.


x86-64 16-Byte-Objekte mit GCC vs. MSVC :

Als Hack können Compiler das lock cmpxchg16bLaden / Speichern von 16-Byte-Atomen sowie tatsächliche Lese-, Änderungs- und Schreibvorgänge implementieren.

Dies ist besser als das Sperren, weist jedoch im Vergleich zu 8-Byte-Atomobjekten eine schlechte Leistung auf (z. B. konkurrieren reine Lasten mit anderen Lasten). Dies ist der einzige dokumentierte sichere Weg, um mit 16 Bytes 1 atomar etwas zu tun .

AFAIK, MSVC verwendet niemals lock cmpxchg16bfür 16-Byte-Objekte und sie sind im Grunde die gleichen wie ein 24- oder 32-Byte-Objekt.

gcc6 und früher lock cmpxchg16bbeim Kompilieren -mcx16inline (cmpxchg16b ist leider keine Basis für x86-64; AMD K8-CPUs der ersten Generation fehlen es.)

gcc7 hat beschlossen, libatomic16-Byte-Objekte immer aufzurufen und niemals als sperrenfrei zu melden, obwohl libatomische Funktionen lock cmpxchg16bauf Computern, auf denen die Anweisung verfügbar ist, weiterhin verwendet werden. Siehe is_lock_free () hat nach dem Upgrade auf MacPorts gcc 7.3 false zurückgegeben . Die gcc-Mailinglistennachricht, die diese Änderung erklärt, ist hier .

Sie können einen Union-Hack verwenden, um einen relativ billigen ABA-Zeiger + Zähler auf x86-64 mit gcc / clang zu erhalten: Wie kann ich einen ABA-Zähler mit c ++ 11 CAS implementieren? . lock cmpxchg16bfür Aktualisierungen von Zeiger und Zähler, aber einfaches movLaden nur des Zeigers. Dies funktioniert jedoch nur, wenn das 16-Byte-Objekt tatsächlich sperrenfrei lock cmpxchg16bist.


Fußnote 1 : Das movdqaLaden / Speichern von 16 Byte ist in der Praxis auf einigen (aber nicht allen) x86-Mikroarchitekturen atomar , und es gibt keine zuverlässige oder dokumentierte Methode, um zu erkennen, wann es verwendbar ist. Siehe Warum ist die Ganzzahlzuweisung für eine natürlich ausgerichtete Variable auf x86 atomar? und SSE-Anweisungen: Welche CPUs können atomare 16B-Speicheroperationen ausführen? Ein Beispiel, bei dem K10 Opteron mit HyperTransport nur zwischen Sockets an 8B-Grenzen reißt.

Compiler-Writer müssen also auf Nummer sicher gehen und können movdqadie Art und Weise, wie sie SSE2 movqfür das Laden / Speichern von 8-Byte-Atomen in 32-Bit-Code verwenden, nicht verwenden. Es wäre großartig, wenn CPU-Anbieter einige Garantien für einige Mikroarchitekturen dokumentieren oder CPUID-Feature-Bits für das Laden / Speichern von atomaren Vektoren mit 16, 32 und 64 Byte (mit SSE, AVX und AVX512) hinzufügen könnten. Vielleicht könnten die Mobo-Anbieter die Firmware auf funky Maschinen mit vielen Sockeln deaktivieren, die spezielle Kohärenz-Klebechips verwenden, die nicht ganze Cache-Zeilen atomar übertragen.

Peter Cordes
quelle
2
Nitpick: Die Implementierung von LLVM ist ein bisschen komplizierter / aufwändiger als die Verwendung der niedrigen Bits als Index.
Frank
1
@Frank: Danke, behoben. Ich habe eine Verschiebung und Maske gesehen, aber das wird natürlich auch mit einer komplexeren Hash-Funktion passieren, also hätte ich weiter nach dem XORing einiger hoher Bits suchen sollen. Das macht mehr Sinn; Große 2-Potenz-Schritte sind in Computerprogrammen nicht selten, und naive Low-Bits würden für diese kollidieren.
Peter Cordes
12

Ab 29.5.9 des C ++ - Standards:

Hinweis: Die Darstellung einer atomaren Spezialisierung muss nicht dieselbe Größe wie der entsprechende Argumenttyp haben. Spezialisierungen sollten nach Möglichkeit dieselbe Größe haben, da dies den Aufwand für das Portieren von vorhandenem Code verringert. - Endnote

Es ist vorzuziehen, die Größe eines Atoms an die Größe seines Argumenttyps anzupassen, obwohl dies nicht erforderlich ist. Der Weg, dies zu erreichen, besteht darin, entweder Schlösser zu vermeiden oder die Schlösser in einer separaten Struktur zu speichern. Wie die anderen Antworten bereits klar erklärt haben, werden alle Sperren in einer Hash-Tabelle gespeichert. Dies ist die speichereffizienteste Methode zum Speichern einer beliebigen Anzahl von Sperren für alle verwendeten atomaren Objekte.

Hadi Brais
quelle
5
Ein weiterer Grund dafür, dass nicht jedes Objekt gesperrt wird, ist die Interoperabilität mit C11-Atomics, bei der die statische Initialisierung ein Problem darstellt. Der C11-Standard definiert ein ATOMIC_VAR_INITMakro (was für zusammengesetzte Typen nicht gut funktioniert) und erfordert auch, dass die statische Nullinitialisierung eines atomaren Objekts funktioniert. Und C11 bietet keine Destruktoren, um Betriebssystemressourcen in Objektsperren freizugeben. Siehe auch developer.redhat.com/blog/2016/01/14/… für eine Diskussion der im C11-Standard entdeckten Probleme.
Peter Cordes