Thema: spinlocks

[rizor]

Hallo zusammen,

ich habe ein Problem mit meinen Spinlocks.
Der Code stellt fest, dass ein Bereich gelockt ist, obwohl er es nicht ist.
Woran kann das liegen?

Code: [Auswählen]

#define LOCKED 1
#define UNLOCKED 0
typedef volatile uint32_t lock_t;

void lock(lock_t *lock){
    __asm__ __volatile__(
"mov %0 , %%ecx\n"
"loop: xor %%eax , %%eax\n"
"lock cmpxchg %%ecx , %1\n"
"jnz loop\n" : : "i"(LOCKED) , "m"(lock));
}
Habe mir auch lock angeschaut und der ist auf UNLOCKED gesetzt.

Kann mir nicht erklären, woran es scheitert.

gruß,
rizor

[erik.vikinger]

Hallo,

Kann mir nicht erklären, woran es scheitert.

Bist Du sicher das der cmpxchg wirklich mit dem gelesenen Wert vergleicht? Oder könnte "loop:" als Befehl interpretiert werden und nicht als Label?

Ich mach das immer so:

Code: [Auswählen]

        mov   eax,LOCKED   // den Wert für gelockt in EAX laden
lloop:  xchg  [ecx],eax    // ECX zeit auf die Lock-Speicherstelle, der XCHG-Befehl hat immer automatisch ein Lock-Prefix auch im Ring 3, ab jetzt ist auf jeden Fall gelockt
        cmp   eax,LOCKED   // prüfen ob bereits gelockt war (von wo anders)
        je    lloop        // wenn vorher bereits gelockt war dann wiederholen bis der andere freigegeben hat, ansonsten bin ich jetzt dran
(vorsicht Intel-Syntax)
zum entlocken wird einfach ein anderer Wert in die Lock-Speicherstelle geschrieben, das ist recht unkritisch.

Mit diesem 4-Zeiler hab ich schon oft auf SMP-System (unter Linux und Windows) gute Erfahrungen gemacht, OS-Funktionen nutze ich für so einen wichtigen Mechanismus prinzipiell nicht (höchstens wenn das OS den wartenden Thread pausieren lassen kann bis der aktuelle Lock-Besitzer diesen freigibt anstatt zu pollen, man könnte/sollte aber auch selber die aktuelle Zeitscheibe freigeben).


Grüße
Erik


edit: ich hab den ASM-Code besser formatiert

[bluecode]

Ich würde gcc atomic builtins einer eigenen Implementierung vorziehen.

edit:
@erik: xchg ist aber ungeschickt auf einem echten Multi/Manycore-System, weil es den Cache thrasht, da es ohne Bedingung schreibt, was die anderen Cores die Cacheline kostet.

[erik.vikinger]

Hallo,

Ich würde gcc atomic builtins einer eigenen Implementierung vorziehen.

Womit Du Dich eben vom Compiler abhängig machst.
An welches Builtin hast Du den gedacht?

xchg ist aber ungeschickt auf einem echten Multi/Manycore-System, weil es den Cache thrasht, da es ohne Bedingung schreibt, was die anderen Cores die Cacheline kostet.

In der Cacheline, in welcher die Lock-Variable liegt, sollte natürlich nichts anderes rein. Ansonsten ist das mit dem Cacheline-Trashing für die Verwendung als Lock natürlich erwünscht. In normalem Code hat der XCHG-Befehl eben nichts zu suchen, der gcc verwendet ihn wimre auch gar nicht.


Grüße
Erik

[bluecode]

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
    These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
    The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation.

Womit Du Dich eben vom Compiler abhängig machst.

Das macht man beim OSDev sowieso, die Frage ist wohl eher wie gut kapselt man, damit man beim Wechseln nicht alles neuschreiben muss. Außerdem macht man sich ohne builtins von der Architektur abhängig, was ich unschöner finde bzw. was mehr Probleme macht.

In der Cacheline, in welcher die Lock-Variable liegt, sollte natürlich nichts anderes rein.

Und die Cacheline ist wie groß? Das ist sicherlich nicht nur Architektur, sondern sogar prozessor-/Modelabhängig.

[rizor]

Danke für die Ratschläge.
Versuche das gerade mit den builtins.
Wie genau muss dass denn aussehen?
Irgendwie brauchen die auch nur ihr "__builtin_"-Präfix.
Sieht das dann so aus: __builtin___sync_bool_compare_and_swap(...)?
Da wird mir gesagt, dass die Funktionen nicht gefunden werden

[bluecode]

Ich hab gerade festgestellt, dass ich das in lightOS noch selber implementiert hatte, insofern kannst du dir da den cmpxchg-Code mal ansehen: hier.

Wie man das buildin verwendet siehst du zB bei pedigree.

[rizor]

Danke.
Jetzt funktioniert es mit den Builtin-Funktionen

[erik.vikinger]

Hallo,


ich persönlich vertraue dem cmpxchg-Befehl nicht. Ohne Lock taugt er nicht und mit Lock funktioniert er nur in Ring 0 (für wichtige Dinge ist er also nur im Kernel nutzbar). Ich weiß das in der Befehlsdokumentation steht das er mit dem lock-präfix sicher ist. Aber wenn man sich dann ansieht wie die Status-Änderungen der Cache-Lines funktionieren dann hab ich da gewisse Zweifel, kann aber auch sein dass das lock-Präfix dort was dreht (und cmpxchg sich xchg ähnlich verhält). Das der xchg-Befehl sicher dafür sorgt das die betreffende Cache-Line aus allen Caches rausfliegt hat für mich einen beruhigenden Faktor. Außerdem ist xchg bestimmt schneller da er beim Zugriff auf den Speicher gleich die zu schreibenden Daten mitgeben kann (es wird ein spezieller Speicherzugriff "gibt mir die Daten von Adresse X und schreibe Y unmittelbar danach (atomisch) an diese Stelle" benutzt, PCI-Express kennt auch so einen Zugriff, ich glaube HyperTransport kennt sowas auch) und die Atomizität im Speicherkontroller entsteht. Beim cmpxchg sind es zwei ganz normale und unabhängige Speicherzugriffe (falls das nicht gar im Cache gemacht wird), der CPU-Kern ist dafür zuständig das dieser Befehl atomar bleibt (was z.B. von einem PCI-Busmaster unterlaufen werden kann).

Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar. ARM unterstützt sowas z.B. mit speziellen Lade- und Schreib-Befehlen (ldrex und strex). Der Lade-Befehl flusht alle betreffenden Cache-Lines und erzeugt im Speicher-Controller einen Lock (der Speicher-Controller merkt sich die Adresse, Größe und welcher CPU-Kern diesen Lock initiiert hat) und die CPU kann die gelesenen Daten über mehrere Befehle atomar verarbeiten. Beim Schreib-Befehl prüft der Speicher-Controller ob der Lock noch besteht (ein zwischenzeitlicher normaler Schreib-Befehl einer anderen CPU an die betreffende Stelle hebt den Lock auf) und nur wenn der Lock noch intakt ist werden die Daten auch tatsächlich geschrieben, außerdem wird der Lock-Zustand an die CPU zurückgemeldet und der Schreib-Befehl setzt passend die Flags. Durch Abfrage der Flags kann der gesamte Vorgang, ab dem Lese-Befehl, komplett wiederholt werden falls etwas nicht gklappt hat (der Lock gestört wurde). Dieses Konzept finde ich wirklich gut, weil damit eine ganze Menge an Problemen von vornherein sicher ausgeschlossen sind, und möchte was vergleichbares auch in meiner Plattform umsetzen.

An buildins find ich __sync_lock_test_and_set und __sync_lock_release deutlich interessanter obwohl dort wieder der Nachteil ist das diese keine richtige "memory barrier" sind. Zumindest das "Test and Set" dürfte recht zuverlässig funktionieren, ob dort für x86 der xchg-Befehl oder der bts-Befehlt benutzt wird müsste man mal prüfen, ob der bts-Befehl ähnlich strickt mit Cache umgeht wie xchg weis ich nicht aber falls er ein lock-Präfix benötigt ist er auch wieder nicht für Ring 3 interessant.

Der Vorteil meines Codes von gestern ist das er auf x86 immer und unter allen Umständen (in allen Ringen) zuverlässig funktioniert. Ich hab das mal in einer C++-Klasse implementiert welche unter Windows (User-Mode-Programm) mit VisualC++ und unter ThreadX (auf ARM-CPU) mit gcc funktionieren musste.


Das mit der Cache-Line-Größe ist natürlich ein Problem, aber in der Mutex-Klasse muss man den Speicher-Platz für die Lock-Variable (einzelnes Byte reicht) ja nicht per malloc() holen sondern könnte da was eigenes bauen das immer ganze Pages vom OS holt. Ich denke das dürfte recht einfach machbar sein und nur eben das holen/zurückgeben der Pages ist Target-Abhängig. Die Pages verwaltet man einfach mit der Bit-Tabelle und gibt jedes Byte einzeln an eine Mutex-Instanz. Zusätzlich könnte man diese Pages gleich noch als Non-Cacheable markieren so das die Cache-Fluches bleiben können.


Grüße
Erik

[bluecode]

Warum sollte lock nur im Ring0 funktionieren?

ich persönlich vertraue dem cmpxchg-Befehl nicht. Ohne Lock taugt er nicht und mit Lock funktioniert er nur in Ring 0 (für wichtige Dinge ist er also nur im Kernel nutzbar). Ich weiß das in der Befehlsdokumentation steht das er mit dem lock-präfix sicher ist. Aber wenn man sich dann ansieht wie die Status-Änderungen der Cache-Lines funktionieren dann hab ich da gewisse Zweifel, kann aber auch sein dass das lock-Präfix dort was dreht (und cmpxchg sich xchg ähnlich verhält). Das der xchg-Befehl sicher dafür sorgt das die betreffende Cache-Line aus allen Caches rausfliegt hat für mich einen beruhigenden Faktor. Außerdem ist xchg bestimmt schneller da er beim Zugriff auf den Speicher gleich die zu schreibenden Daten mitgeben kann (es wird ein spezieller Speicherzugriff "gibt mir die Daten von Adresse X und schreibe Y unmittelbar danach (atomisch) an diese Stelle" benutzt, PCI-Express kennt auch so einen Zugriff, ich glaube HyperTransport kennt sowas auch) und die Atomizität im Speicherkontroller entsteht. Beim cmpxchg sind es zwei ganz normale und unabhängige Speicherzugriffe (falls das nicht gar im Cache gemacht wird), der CPU-Kern ist dafür zuständig das dieser Befehl atomar bleibt (was z.B. von einem PCI-Busmaster unterlaufen werden kann).

Mein Verständnis von Caches ist eher limitiert, aber ich sehe da kein Problem mit cmpxchg. Da die Cacheline ja nur in allen anderen CPUs geflusht werden muss, wenn wirklich geschriebene wird, aber das wird cmpxchg wohl auch machen. Der Vorteil ist halt, das cmpxchg nur schreibt wenn es wirklich durfte (d.h. wenn der Wert an der Stelle der erwartete ist). Das erscheint mir zum einen korrekt zum anderen wegen weniger Cache Thrashing effizienter.
Ich würde auch vermuten, dass das read in den Cache geht (was ja korrekt ist) und danach das write erst eine "richtige" Speicheroperation ist.

Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar.

Das ist falsch, für add/sub wird die xadd Instruktion (mit lock) verwendet, was mir auf den ersten Blick völlig korrekt erscheint. Für die anderen wird cmpxchg verwendet, was auch sicherlich korrekt ist.
Abgesehen davon würde gcc einen Funktioncall einfügen, wenn er es auf der Architektur nicht unterstützen kann und das würde man wohl merken.

edit: Noch eine kleine Randnotiz falls du es selbst versuchen willst. Wenn der Rückgabewert von den Operationen nicht verwendet wird, dann optimiert der gcc das zB zu einem add mit lock.

[erik.vikinger]

Hallo,

Warum sollte lock nur im Ring0 funktionieren?

Als ich das lock-Präfix das letzte mal im Ring 3 benutzt hatte gabs ne Illegal-OpCode-Exception, kann aber auch an was anderes gelegen haben, da will ich mich jetzt nicht genau festlegen. Ich hatte halt diesen Zusammenhang irgendwie im Gedächtnis.

... aber ich sehe da kein Problem mit cmpxchg. Da die Cacheline ja nur in allen anderen CPUs geflusht werden muss, wenn wirklich geschriebene wird

Richtige Atomizität (nennt man das eigentlich so?) muss mit dem Lese-Zugriff beginnen. Jetzt überlege mal was passiert wenn 2 CPUs gleichzeitig (das ist zwar nicht sehr wahrscheinlich aber doch möglich, ich denke als kritisches Zeit-Fenster können da etwa 4 CPU-Takte (vielleicht auch deutlich mehr) gelten) auf die Lock-Variable lesend zugreifen. Beide lesen das selbe ohne das einer vom anderen weiß. Wenn Du Dir die ARM-Implementierung ansiehst dann stellst Du fest das dort das Lock mit dem Lese-Befehl erstellt wird, die Lesebefehle werden spätestens im Speicher-Controller serialisiert (einer kommt eben als erster dran), wer dort verliert hat eben nicht den Lock. Beide Lese-Befehle liefern die selben Daten und beide CPUs werden gleichartig weitermachen aber nur bei einem wird der Schreib-Befehl zurückmelden das der Lock noch intakt war und beim anderen wird der ganze Code-Abschnitt, vom Lese-Befehl an, noch mal ausgeführt. Beim xchg-Befehl auf x86 wird die Atomizität im Speichercontroller damit erzeugt das dieser das Lesen der alten Daten und das Schreiben der neuen Daten als einen Zugriff atomar ausführt, ein gleichartiger Zugriff einer anderen CPU kommt eben danach und die bekommt beim Lesen auch sicher genau die Daten welche die erste CPU geschrieben hat. Beim Schreib-Part des cmpxchg-Befehls gibt es eben keine Rückmeldung das jemand anderes in der Zwischenzeit auch gelesen oder gar geschrieben hat. So könnten möglicherweise mehrere CPUs ermittelt haben das der Mutex/Spinlock/Semaphore vorher frei war und dann mehrere CPUs gleichzeitig drin sind. Idealer weise dürfte zwischen dem Lesen und dem zugehörigen Schreiben kein weiterer Zugriff, weder lesen noch schreiben, auf die Lock-Variable möglich sein, eben genau so wie es xchg immer macht. ARM hat das komplizierte mit einbeziehen des Speicher-Controllers, der ja gar nicht zur CPU gehört, nicht ohne Grund gemacht. Als kleine Optimierung könnte der Lesebefehl gleich zurückmelden ob der Lock überhaupt erstellt werden konnte, so das die CPU nicht vergeblich rechnen muss, so möchte ich es jedenfalls machen.

Der Vorteil ist halt, das cmpxchg nur schreibt wenn es wirklich durfte (d.h. wenn der Wert an der Stelle der erwartete ist).

Und genau da ist das Problem. Ich weiß nicht ob das lock-Präfix an diesem Verhalten nachbessert aber alles was ich bis jetzt über diesen Befehl gelesen hab lässt mich zweifeln. Möglicherweise sind meine Zweifel unbegründet, immerhin wird der cmpxchg-Befehl ja auch explizit für Semaphoren und Mutexes empfohlen und die Intel-Leute wissen hoffentlich was sie tun, aber ich persönlich bleibe (bei einer so elementaren/wichtigen Funktion) lieber auf der sicheren Seite.

Das erscheint mir zum einen korrekt zum anderen wegen weniger Cache Thrashing effizienter. Ich würde auch vermuten, dass das read in den Cache geht (was ja korrekt ist) und danach das write erst eine "richtige" Speicheroperation ist.

Wenn man davon ausgeht das Lock-Variablen prinzipiell nicht in den Cache dürfen, damit beim lesen auch immer der wirklich aktuelle Wert geliefert wird, dann ist xchg IMHO der effizientere Befehl.

Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar.

Das ist falsch, für add/sub wird die xadd Instruktion (mit lock) verwendet, was mir auf den ersten Blick völlig korrekt erscheint. Für die anderen wird cmpxchg verwendet, was auch sicherlich korrekt ist.

Okay, den Befehl kannte ich noch nicht. Das trifft aber nur auf __sync_fetch_and_add und __sync_fetch_and_sub zu. Die andere Variante __sync_add_and_fetch und __sync_sub_and_fetch gehen trotzdem nicht. Und alle anderen Rechenarten eben auch nicht. Oder gibt es da noch mehr Befehle die ich (noch) nicht kenne?

Wenn der Rückgabewert von den Operationen nicht verwendet wird, dann optimiert der gcc das zB zu einem add mit lock.

Das erwarte ich eigentlich auch.


Grüße
Erik

[XanClic]

Warum sollte lock nur im Ring0 funktionieren?

Als ich das lock-Präfix das letzte mal im Ring 3 benutzt hatte gabs ne Illegal-OpCode-Exception, kann aber auch an was anderes gelegen haben, da will ich mich jetzt nicht genau festlegen. Ich hatte halt diesen Zusammenhang irgendwie im Gedächtnis.

Wenn das nur aufgrund des Privileglevels nicht funktioniert, sollte es aber einen GPF geben (wie bei IN, OUT, CLI, ...).

[bluecode]

zu dem Zeug mit den Caches: Wie gesagt, ich habe wenig Ahnung davon, aber ich gehe davon aus, dass es funktioniert wenn es so in den Intel-Manuals steht und noch dazu von Compiler, etc. verwendet wird.

Außerdem bringt loch offensichtlich keine Exceptions. Ich habe wie oben erwähnt die Ops unter gcc compiliert, disassembliert und getestet. Das lief einwandfrei und verwendet lock. Einen Invalid Opcode liefert es nur dann, wenn man es mit beliebigen Instruktionen versucht zu verwenden. Eine Liste der erlaubten findet sich in den Intel Manuals unter der lock-Instruktion/Präfix.

Die andere Variante __sync_add_and_fetch und __sync_sub_and_fetch gehen trotzdem nicht. Und alle anderen Rechenarten eben auch nicht. Oder gibt es da noch mehr Befehle die ich (noch) nicht kenne?

Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.

edit: Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.

edit2: aus den Intel Manuals

To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)

Das kommt dann wohl auf das gleiche wie das xchg raus.

[erik.vikinger]

Hallo,

aber ich gehe davon aus, dass es funktioniert wenn es so in den Intel-Manuals steht und noch dazu von Compiler, etc. verwendet wird.

Ist ein Argument. Mich persönlich überzeugt allein die Aussage "es geht" nicht, ich möchte auch das die Beschreibung "wie es geht" mir den Eindruck vermittelt das es "wirklich geht" und genau das vermisse ich bei cmpxchg. Ich sehe einfach nicht wie die vorhin beschriebenen Probleme absolut zuverlässig vermieden werden sollen. Aber das ist nur mein persönlicher subjektiver Eindruck, die absolute Wahrheit zu diesem Thema kenn ich auch nicht.

Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.

Jetzt verstehe ich was Du meinst: man lädt den Wert der im Speicher steht, verrechnet ihn und der cmpxchg-Befehl prüft am Schluss ob er zwischenzeitlich im Speicher modifiziert wurde. Wenn nein dann wird der neue Wert geschrieben und wenn ja dann wird der ganze Vorgang wiederholt. Hab ich das jetzt richtig verstanden?

Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.

So wie ich gestern Nachmittag in meinem 4-Zeiler gezeigt hab. xchg schreibt immer den Wert für belegt. Falls der vorher schon drin war hat sich nichts geändert und falls nicht dann ist der Lock ab jetzt belegt. Falls der gelesene (alte) Wert belegt signalisiert dann war der Lock bereits (von wen anders) belegt und der Vorgang muss wiederholt werden, wenn vorher nicht belegt war dann ist der aktuelle Code jetzt der Eigentümer vom Lock.

Bevor ARM die tollen Lese- und Schreib-Befehle (mit dem Lock im Speicher-Controller) eingeführt hat war das die einzigste Möglichkeit auf ARM einen zuverlässigen Lock zu bauen, nur das der Befehl dort swp heißt (er ist aber genauso strickt atomar wir xchg von x86).
http://www.doulos.com/knowhow/arm/Hints_and_Tips/Implementing_Semaphores/


Grüße
Erik

[bluecode]

Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.

Jetzt verstehe ich was Du meinst: man lädt den Wert der im Speicher steht, verrechnet ihn und der cmpxchg-Befehl prüft am Schluss ob er zwischenzeitlich im Speicher modifiziert wurde. Wenn nein dann wird der neue Wert geschrieben und wenn ja dann wird der ganze Vorgang wiederholt. Hab ich das jetzt richtig verstanden?

Ja hast du.

Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.

So wie ich gestern Nachmittag in meinem 4-Zeiler gezeigt hab. xchg schreibt immer den Wert für belegt. Falls der vorher schon drin war hat sich nichts geändert und falls nicht dann ist der Lock ab jetzt belegt. Falls der gelesene (alte) Wert belegt signalisiert dann war der Lock bereits (von wen anders) belegt und der Vorgang muss wiederholt werden, wenn vorher nicht belegt war dann ist der aktuelle Code jetzt der Eigentümer vom Lock.

Ich meinte mit Semaphore (siehe auch Wikipedia) keine einfache Mutex, sondern einen Zähler. Der Zähler gibt die Zahl der Threads an die noch in den Bereich eintreten dürfen, d.h. es geht nicht nur darum ein Bit zu setzen oder zu löschen sondern auch darum korrekt zu zählen, das kann aber ein xchg nicht.

Man kann natürlich den Zähler über ne Mutex/Lock schützen, aber mit cmxchg geht es halt direkt.

[erik.vikinger]

Hallo,

edit2: aus den Intel Manuals

To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)

Das kommt dann wohl auf das gleiche wie das xchg raus.

Das erklärt aber nicht wie verhindert werden soll das wenn 2 CPUs per cmpxchg zur (fast) gleichen Zeit den Lesezugriff ausführen das diese dann unterschiedliche Daten bekommen damit eben nur eine von beiden denkt der Lock wäre noch frei. Wenn beide den Lock als frei betrachten (weil beide den selben Wert gelesen haben) werden auch beide sich als neuen Besitzer fühlen, daran ändern auch nichts die 2 Schreibzugriffe (egal in welcher Reihenfolge) die beide den selben Wert (für belegt) schreiben. (ich gehe hierbei von einem simplen Lock aus)

Ich bleibe dabei das ich noch keine schlüssige Begründung gelesen hab warum der cmpxchg-Befehl sicher immer zuverlässig funktioniert. Beim xchg kann man die Sicherheit recht einfach nachvollziehen (atomarer Daten-Austausch, so wie auch beim swp von ARM), beim cmpxchg fallen mir eben Möglichkeiten ein wo es schief geht. Solange diese Möglichkeiten nicht absolut nachvollziehbar ausgeschlossen werden verwende ich cmpxchg nicht. Das ist meine persönliche Entscheidung, was der Rest der Welt macht ist mir in diesem Punkt egal. Ich fürchte ohne einen kompetenten Mitarbeiter von Intel werden wir diese Frage nicht klären können.

Ich meinte mit Semaphore ....

Sorry, diese Begriffe bringe ich schon mal durcheinander.


Grüße
Erik

[bluecode]

Es könnte sein, dass das Kapitel 7.1 in den Intel® 64 and IA-32 Architectures Software Developer’s Manual 3A  dir die Lösung dazu verrät. Garantieren kann ichs natürlich nicht, da ich das gerade erst angefangen habe zu lesen und außerdem von Hardwaredingen nicht sonderlich viel verstehe. Ich zitiere trotzdem mal ein bisschen:

These mechanisms are interdependent in the following ways. Certain basic memory transactions (such as reading or writing a byte in system memory) are always guaranteed to be handled atomically. That is, once started, the processor guarantees that the operation will be completed before another processor or bus agent is allowed access to the memory location. The processor also supports bus locking for performing selected memory operations (such as a read-modify-write operation in a shared area of memory) that typically need to be handled atomically, but are not automatically handled this way. Because frequently used memory locations are often cached in a processor’s L1 or L2 caches, atomic operations can often be carried out inside a processor’s caches without asserting the bus lock. Here the processor’s cache coherency protocols insure that other processors that are caching the same memory locations are managed properly while atomic operations are performed on cached memory locations.

Das "[...] or bus agent" w+rde für mich bedeuten, dass deine PCI-Geräte kein Problem sind und der Rest bedeutet für mich, dass ich mich nicht darum kümmern muss wie genau es funktioniert, sondern das der Prozessor einfach dafür sorge trägt.

edit: Deine Paranoia bei genau dem Befehl verstehe ich ehrlich gesagt nicht wirklich... Bei jedem anderem vertraust du Intel, aber genau hier nicht? Außerdem wurde der Befehl exakt für Multiprozessorsysteme eingeführt. Da ist es unvorstellbar, dass es Randfälle geben soll die nicht abgedeckt sein sollen.

[rizor]

Das erklärt aber nicht wie verhindert werden soll das wenn 2 CPUs per cmpxchg zur (fast) gleichen Zeit den Lesezugriff ausführen das diese dann unterschiedliche Daten bekommen damit eben nur eine von beiden denkt der Lock wäre noch frei. Wenn beide den Lock als frei betrachten (weil beide den selben Wert gelesen haben) werden auch beide sich als neuen Besitzer fühlen, daran ändern auch nichts die 2 Schreibzugriffe (egal in welcher Reihenfolge) die beide den selben Wert (für belegt) schreiben. (ich gehe hierbei von einem simplen Lock aus)

Ich bleibe dabei das ich noch keine schlüssige Begründung gelesen hab warum der cmpxchg-Befehl sicher immer zuverlässig funktioniert. Beim xchg kann man die Sicherheit recht einfach nachvollziehen (atomarer Daten-Austausch, so wie auch beim swp von ARM), beim cmpxchg fallen mir eben Möglichkeiten ein wo es schief geht. Solange diese Möglichkeiten nicht absolut nachvollziehbar ausgeschlossen werden verwende ich cmpxchg nicht. Das ist meine persönliche Entscheidung, was der Rest der Welt macht ist mir in diesem Punkt egal. Ich fürchte ohne einen kompetenten Mitarbeiter von Intel werden wir diese Frage nicht klären können.

Das ganze funktioniert nach dem Cache-Prinzip.
Die CPUs haben Cache-Kohärenz-Protokolle, die genau das sichern.
Wenn eine CPU auf einen Speicher zugreifen möchte, meldet er sich als Owner an, falls es keinen Owner gibt.
Wenn es einen Owner gibt, schreibt er den Wert in den RAM und meldet sich als Owner ab.
Der neue wird dann Owner und schreibt dort etwas rein.
Wenn eine andere CPU diese Adresse im Cache hat, wird die auf dirty gesetzt und wenn nötig neu geladen, bzw. der Owner wird aufgefordert den aktuellen Wert in den RAM zu schreiben, damit alle wieder aktuelle Werte haben.

Dieses einfache Owner-Prinzip garantiert, dass so etwas wie zeitgleiches Schreiben nicht funktioniert.
Und das geht auch nicht, da die CPUs über einen eigenen Bus kommunizieren und jede CPU, die schreiben möchte und kein Owner ist, braucht von allen anderen CPUs eine Bestätigung.

Gruß,
rizor

EDIT:
Intel hatte in den Anfängen dieses Befehls eine Bug, der unter Umständen kurzzeitig falsche Werte im Cache haben könnte, darum sollte man nach dem Befehl kurz ein busywait haben und dann noch einmal abfragen.
Das gehört aber der Vergangenheit an.

[bluecode]

erik hat nicht von zeitgleichem Schreiben gesprochen, sondern von dem Lese-danach-Schreiben während eines compare and exchange, d.h. es geht um
CPU0 liest
CPU1 liest
CPU1 schreibt
CPU0 schreibt
Dann kommt eventuell Mist raus, was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.

edit: Zahlen korrigiert 

[rizor]

erik hat nicht von zeitgleichem Schreiben gesprochen, sondern von dem Lese-danach-Schreiben während eines compare and exchange, d.h. es geht um
CPU0 liest
CPU1 liest
CPU1 schreibt
CPU2 schreibt
Dann kommt eventuell Mist raus, was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.

Genau das kann nicht gehen, denn es gibt einen Owner und der verwaltet.
Wenn nun sagen wir CPU1 owner ist, darf CPU2 nicht schreiben und CPU0 bekommt nach "CPU1 schreibt" ein Dirty-Flag.
CPU2 darf erst schreiben, wenn sich 1 als Owner abmelden darf, somit werden die Befehle nacheinander ausgeführt.
Wenn nun CPU2 owner wär, dürfte CPU1 nicht einfach schreiben, sondern muss warten, bsi CPU2 fertig ist