x86 Äquivalent für LWARX und STWCX

Question

Ich 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. Auch, wo wäre der beste Ort, um über solche Dinge zu erfahren (d. H. Gute Artikel/Websites/Foren für Lock/wartefreies Programmieren).

---

bearbeiten
ich glaube, ich könnte mehr Details geben müssen, wie es, dass ich für einen CAS bin nur (Vergleichs- und Auslagerungs) Betrieb suchen angenommen wird. Was ich versuche, ist ein Lock-Free-Referenzzählsystem mit intelligenten Zeigern zu implementieren, auf die mehrere Threads zugreifen und diese ä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 wirklich brauchen etwas, das imitiert LWARX und STWCX ziemlich genau diese abziehen (ich nicht einen Weg finden, können diese Funktionen mit dem CompareExchange, Swap zu tun oder füge ich für die bisher gefunden habe x86).

Dank

Answer 1

Wie Michael erwähnt, was Sie wahrscheinlich suchen, ist die cmpxchg Anweisung.

Es ist wichtig, darauf hinzuweisen, dass die PPC-Methode, um dies zu erreichen, als Load Link/Store Conditional (LL/SC) bekannt ist, während die x86-Architektur Compare And Swap (CAS) verwendet. LL/SC hat eine stärkere Semantik als CAS, da jede Änderung des Wertes an der konditionierten Adresse dazu führt, dass der Speicher fehlschlägt, selbst wenn die andere Änderung den Wert mit dem gleichen Wert ersetzt, auf den die Last konditioniert wurde. CAS hingegen würde in diesem Fall Erfolg haben. Dies wird als ABA-Problem bezeichnet (weitere Informationen finden Sie im CAS-Link).

Wenn Sie die stärkere Semantik auf der x86-Architektur benötigen, können Sie es annähernd durch die x86s doppelt breiten Vergleichs- und swap (DWCAS) Anweisung cmpxchg8b oder cmpxchg16b unter x86_64 verwenden. Auf diese Weise können Sie zwei aufeinander folgende Wörter mit "natürlicher Größe" auf einmal austauschen, anstatt nur die übliche. Der Grundgedanke ist, dass eines der beiden Wörter den Wert des Interesses enthält und das andere eine immer steigende "Mutationsanzahl" enthält. Obwohl dies das Problem technisch nicht beseitigt, ist die Wahrscheinlichkeit, dass die Mutation zwischen den Versuchen hin- und herwechselt, so gering, dass sie für die meisten Zwecke ein vernünftiger Ersatz ist.

Answer 2

x86 unterstützt nicht direkt „Parallelität“ wie PPC tut -, sondern Unterstützung der x86 für Parallelität basiert auf einem „Lock-Präfix“, here sehen. (Einige sogenannte "atomare" Befehle, wie XCHG, erhalten ihre Atomarität, indem sie das LOCK-Präfix intrinsisch aktivieren, unabhängig davon, ob der Assemblercode-Programmierer es tatsächlich codiert hat oder nicht). Es ist nicht gerade "bombensicher", um es diplomatisch zu sagen (es ist eher unfallträchtig, würde ich sagen ;-).

Answer 3

Sie suchen wahrscheinlich nach der Cmpxchg-Familie von Anweisungen.

Sie müssen diesen Anweisungen eine Lock-Anweisung voranstellen, um gleiches Verhalten zu erhalten.

Werfen Sie einen Blick auf here für einen schnellen Überblick über das, was verfügbar ist.

Sie werden wahrscheinlich mit etwas Ähnliches wie dies am Ende:

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 this paper lesen ...

bearbeiten

Als Antwort auf die Frage aktualisiert, Sie sind etwas zu tun, wie die Boost shared_ptr? Wenn ja, schauen Sie sich diesen Code und die Dateien in diesem Verzeichnis an - sie werden Sie auf jeden Fall weiterbringen.

Answer 4

Was Sie versuchen zu tun, wird nicht so funktionieren, wie Sie es erwarten. Was Sie oben implementiert haben, können Sie mit der InterlockedIncrement-Funktion (Win32-Funktion; Assembly: XADD) erledigen.

Der Grund, dass Ihr Code nicht tut, was Sie denken, ist, dass ein anderer Thread immer noch den Wert zwischen dem zweiten Lesen von * ptr und stwcx ändern kann, ohne die stwcx zu entwerten.

Answer 5

Wenn Sie 64 Bits haben und sich auf 1 TB Heap beschränken, können Sie den Zähler in die 24 unbenutzten oberen Bits packen. Wenn Sie wortorientierte Zeiger haben, sind auch die unteren 5 Bits 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 6

Ich weiß nicht, ob LWARX und STWCX die gesamte Cachezeile ungültig machen, CAS und DCAS tun dies. Das heißt, wenn Sie nicht viel Speicher (64 Bytes für jeden unabhängigen "abschließbaren" Zeiger) wegwerfen wollen, werden Sie nicht viel Verbesserung sehen, wenn Sie Ihre Software wirklich unter Stress setzen. Die besten Ergebnisse, die ich bis jetzt gesehen habe, waren, als Leute bewusst 64b kassierten, ihre Strukturen um sie herum planten (Sachen packten, die nicht strittig sind), alles auf 64b-Grenzen ausgerichtet hielten und explizite Lese- und Schreib-Datenbarrieren benutzten. Cache Line Invalidation kann ca. 20 bis 100 Zyklen kosten, was es zu einem größeren echten Perf-Problem macht.

Sie müssen auch verschiedene Speicherzuordnungsstrategien planen, um entweder kontrolliertes Leaking zu verwalten (wenn Sie Code in logische "Anfrageverarbeitung" partitionieren können - eine Anfrage "leckt" und dann am Ende alle Speichermasse freigibt) oder Dateiled Allocation Management, so dass eine Struktur, die sich in Konkurrenz befindet, niemals Speicher erhält, der durch Elemente der gleichen Struktur/Sammlung wieder freigegeben wird (um ABA zu verhindern). Einige davon können sehr kontraproduktiv sein, aber entweder ist es das oder der Preis für GC.