x86-Entsprechung für LWARX und STWCX

Question

Ich bin auf der Suche nach einem Äquivalent von LWARX und STWCX (wie auf den PowerPC-Prozessoren gefunden) oder eine Möglichkeit, ähnliche Funktionalität auf der x86-Plattform zu implementieren. Wo kann man sich am besten über solche Dinge informieren (d.h. gute Artikel/Webseiten/Foren für sperr- und wartungsfreie Programmierung)?

---

Editer
Ich glaube, ich muss mehr Details angeben, da angenommen wird, dass ich nur nach einer CAS-Operation (Compare and Swap) suche. Ich versuche, ein sperrfreies Referenzzählsystem mit intelligenten Zeigern zu implementieren, auf die mehrere Threads zugreifen und sie ändern können. Ich brauche im Grunde eine Möglichkeit, die folgende Funktion auf einem x86-Prozessor zu implementieren.

int\* IncrementAndRetrieve(int \*\*ptr)
{
  int val;
  int \*pval;
  do
  {
    // fetch the pointer to the value
    pval = \*ptr;

    // if its NULL, then just return NULL, the smart pointer
    // will then become NULL as well
    if(pval == NULL)
      return NULL;

    // Grab the reference count
    val = lwarx(pval);

    // make sure the pointer we grabbed the value from
    // is still the same one referred to by  'ptr'
    if(pval != \*ptr)
      continue;

    // Increment the reference count via 'stwcx' if any other threads
    // have done anything that could potentially break then it should
    // fail and try again
  } while(!stwcx(pval, val + 1));
  return pval;
}

Ich brauche wirklich etwas, das LWARX und STWCX ziemlich genau nachahmt, um dies zu erreichen (ich kann keinen Weg finden, dies mit den Funktionen CompareExchange, swap oder add zu tun, die ich bisher für x86 gefunden habe).

Danke

Answer 1

Wie Michael bereits erwähnt hat, suchen Sie wahrscheinlich nach der cmpxchg Anweisung.

Es ist jedoch wichtig darauf hinzuweisen, dass die PPC-Methode zur Erreichung dieses Ziels bekannt ist als Link laden / Bedingte speichern (LL/SC), während die x86-Architektur Vergleichen und Tauschen (CAS). LL/SC hat eine stärkere Semantik als CAS, da jede Änderung des Wertes an der konditionierten Adresse dazu führt, dass die Speicherung fehlschlägt, selbst wenn die andere Änderung den Wert durch denselben Wert ersetzt, auf den die Ladung konditioniert wurde. CAS hingegen würde in diesem Fall erfolgreich sein. Dies ist als ABA-Problem bekannt (siehe CAS-Link für weitere Informationen).

Wenn Sie die stärkere Semantik auf der x86-Architektur benötigen, können Sie sich ihr annähern, indem Sie den x86-Befehl DWCAS (double-width compare-and-swap) verwenden cmpxchg8b 或いは cmpxchg16b unter x86_64. Damit können Sie zwei aufeinanderfolgende Wörter in "natürlicher Größe" auf einmal atomar austauschen, anstatt nur das übliche eine. Der Grundgedanke ist, dass eines der beiden Wörter den gewünschten Wert enthält und das andere eine sich ständig erhöhende "Mutationszahl". Obwohl dies technisch gesehen das Problem nicht beseitigt, ist die Wahrscheinlichkeit, dass der Mutationszähler zwischen den Versuchen durchläuft, so gering, dass es für die meisten Zwecke ein vernünftiger Ersatz ist.

Answer 2

X86 unterstützt nicht direkt "optimistische Gleichzeitigkeit" wie PPC -- vielmehr basiert die x86-Unterstützung für Gleichzeitigkeit auf einem "Lock-Präfix", siehe aquí . (Einige so genannte "atomare" Befehle wie XCHG erhalten ihre Atomarität dadurch, dass sie das LOCK-Präfix für sich beanspruchen, unabhängig davon, ob der Programmierer des Assembler-Codes es tatsächlich kodiert hat oder nicht). Das ist nicht gerade "bombensicher", um es diplomatisch auszudrücken (in der Tat ist es ziemlich unfallträchtig, würde ich sagen;-).

Answer 3

Sie suchen wahrscheinlich nach der cmpxchg-Familie von Anweisungen.

Um ein gleichwertiges Verhalten zu erreichen, müssen Sie eine Sperranweisung voranstellen.

Schauen Sie mal aquí um einen schnellen Überblick über das Angebot zu erhalten.

Wahrscheinlich werden Sie am Ende etwas Ähnliches wie das hier vorfinden:

mov ecx,dword ptr [esp+4]
mov edx,dword ptr [esp+8]
mov eax,dword ptr [esp+12]
lock cmpxchg dword ptr [ecx],edx
ret 12

Sie sollten lesen dieses Papier ...

Editer

Als Antwort auf die aktualisierte Frage: Wollen Sie etwas wie die Boost shared_ptr ? Wenn ja, schauen Sie sich den Code und die Dateien in diesem Verzeichnis an - damit können Sie auf jeden Fall etwas anfangen.

Answer 4

Wenn Sie auf 64 Bits sind und sich auf sagen wir 1 TB Heap beschränken, können Sie den Zähler in die 24 unbenutzten oberen Bits packen. Wenn Sie wortausgerichtete Zeiger haben, sind die unteren 5 Bits auch verfügbar.

int* IncrementAndRetrieve(int **ptr)
{
  int val;
  int *unpacked;
  do
  {   
    val = *ptr;
    unpacked = unpack(val);

    if(unpacked == NULL)
      return NULL;
    // pointer is on the bottom
  } while(!cas(unpacked, val, val + 1));
  return unpacked;
}

Answer 5

Ich weiß nicht, ob LWARX und STWCX die gesamte Cache-Zeile ungültig machen, CAS und DCAS schon. Das heißt, wenn Sie nicht bereit sind, eine Menge Speicher wegzuwerfen (64 Byte für jeden unabhängigen "sperrbaren" Zeiger), werden Sie keine große Verbesserung sehen, wenn Sie Ihre Software wirklich unter Stress setzen. Die besten Ergebnisse, die ich bisher gesehen habe, waren, wenn die Leute bewusst 64b geopfert haben, ihre Strukturen darum herum geplant haben (indem sie Sachen gepackt haben, die nicht Gegenstand von Konflikten sein werden), alles auf 64b-Grenzen ausgerichtet haben und explizite Lese- und Schreibdatenbarrieren verwendet haben. Die Invalidierung von Cache-Zeilen kann ca. 20 bis 100 Zyklen kosten und ist damit ein größeres Problem als nur die Vermeidung von Sperren.

Außerdem müssten Sie eine andere Strategie für die Speicherzuweisung planen, um entweder kontrollierte Lecks zu verwalten (wenn Sie den Code in logische "Anforderungsverarbeitung" unterteilen können - eine Anforderung "leckt" und gibt dann am Ende die gesamte Speichermasse frei) oder die Zuweisung von Daten so zu verwalten, dass eine konkurrierende Struktur niemals Speicher erhält, der durch Elemente derselben Struktur/Sammlung belegt ist (um ABA zu verhindern). Einiges davon kann sehr kontra-intuitiv sein, aber es ist entweder das oder der Preis für GC zu zahlen.