Thema: spinlocks

[bluecode]

Ich habe die Zahlen geändert, aber ich sehe nicht warum das MESI-Protokoll sowas verhindern würde (wenn man mal von Atomizität bei cmpxchg absieht).

[rizor]

Aber genau darauf basiert das.
Wenn du keine atomaren Befehle verwendest, kann es natürlich sein, dass zwischendurch ein anderer Owner wird und du nicht mitbekommst, dass jemand schon einen anderen Wert vreingeschrieben hast, da du ja danach nur noch auf Registern arbeitest (meistens)

[bluecode]

Ich sags nochmal: erik bezweifelt, dass die Atomizität von Lese+Schreibbefehl hardwaretechnisch möglich ist. Ich stimme dir insofern zu, als dass ich das für unwahrscheinlich halte, va. weil sonst der Befehl cmpxchg komplett überflüssig ist.

[rizor]

Wieso soll der nicht atomar sein?
Atomar heißt ja nicht, dass das ganze in einem Takt durch zuziehen ist.
Es kann doch auch sein, dass er in den ersten paar Takten liest und danach schreibt.
Er darf in der Zeit halt nur nicht auf der IRQ-Leitung und der CPU-Kommunikations-Leitung lauschen.
Die müssen währenddessen einfach ignoriert werden, dann ist das ganze Atomar.
Die x86er haben ja auch kaum Befehle, die in einem Takt durchführbar sind

[erik.vikinger]

Hallo,

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....

Genau das ist die Sorte Text die mir missfällt. Da steht einfach nur "vertrau uns". Wenn dort der Weg beschreiben wäre und dieser Weg wäre plausibel dann würde ich Intel auch tatsächlich vertrauen, aber so leider nicht.
Beim xchg-Befehl ist die Funktionsbeschreibung vollständig und nachvollziehbar aber vor allem auch Vertrauenerweckend (es lassen sich keine prinzipiellen Fehler o.ä. finden).

Deine Paranoia bei genau dem Befehl verstehe ich ehrlich gesagt nicht wirklich... Bei jedem anderem vertraust du Intel, aber genau hier nicht?

Das liegt einfach da ran das dieser Befehl so elementar wichtig ist aber man seine Zuverlässigkeit nicht wirklich prüfen kann. Eine ALU oder FPU kann man mit vielen Beispielrechnungen prüfen ob immer das richtige Ergebnis raus kommt, bei der Atomizität geht das nicht. Man kann zwar prüfen ob das Restrisiko nahe 0 ist, aber man kann eben nicht auf genau 0 prüfen.

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.

Da gebe ich Dir zwar Recht, aber ich habe schon von verschiedenen Leuten gehört das die Cache-Kohärenz-Protokolle eine ziemlich komplizierte (und damit fehlerträchtige) Angelegenheit sind, deshalb bevorzuge ich Wege die mit wenig Aufwand und wenig Komplexität ein zuverlässiges Ergebnis bringen.
Da die betreffende Cache-Line eh bei jedem betreten des Lock getrasht wird (dann wird ja auch ein Schreibzugriff für die Statusänderung auf belegt durchgeführt) bin ich der Meinung das diese Lock-Variablen erst gar nicht in den Cache rein dürfen. Wenn die Lock-Variablen eh nicht im Cache sind dann ist der xchg-Befehl aber auch deutlich schneller. Gerade bei sehr vielen CPUs verursacht das Cache-Kohärenz-Protokoll aber einen erheblichen Overhead so das der cmpxchg-Befehl mit Sicherheit deutlich langsamer ist.

Dieses einfache Owner-Prinzip garantiert, dass so etwas wie zeitgleiches Schreiben nicht funktioniert.

Intel hat keinen "Owner", dort gibt es nur MESI ohne O. Außerdem springt das Cache-Kohärenz-Protokoll erst an wenn geschrieben wird, es könnte natürlich sein dass das lock-Präfix beim cmpxchg hier noch mal was dreht aber das geht aus den Intel-Dokus nicht hervor. Dort wird doch beschrieben das der cmpxchg erst dann nach außen spürbare Auswirkungen hat wenn auch geschrieben wird.

Was ist wenn bei beiden CPUs die Daten nicht im Cache sind? Dann kommen 2 ganz normale Speicher-Lese-Zugriffe. Ich kann nicht erkennen wie damit die Atomizität gewährleistet werden soll.

erik hat nicht von zeitgleichem Schreiben gesprochen,

Es geht mir darum das zwischen dem Lesen und dem Schreiben der einen CPU eine andere überhaupt die Lock-Variable lesen kann (ohne das eine von beiden CPUs das bemerkt). Der Lese-Zugriff der anderen CPU bringt die selben Daten und damit geht die andere CPU eben auch davon aus (so wie die erste CPU) das der Lock noch frei ist und fühlt sich hinterher als rechtmäßiger Besitzer (so wie auch die erste CPU). Daran ändert auch nichts das dann beide CPUs später einen "irgendwie gesicherten" Schreibzugriff durchführen (beide mit den selben Daten), dann ist es schließlich schon zu spät. Die Entscheidung (Lock bekommen oder nicht) wird zwischen dem Lese-Zugriff und dem Schreib-Zugriff getroffen und alles externe was zwischen diesen Zugriffen passiert beeinflusst diese Entscheidung eben nicht.

....was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.

So sollte es sein, aber den Intel-Dokus kann man nicht entnehmen das es wirklich so ist.

Atomar heißt ja nicht, dass das ganze in einem Takt durch zuziehen ist.
Es kann doch auch sein, dass er in den ersten paar Takten liest und danach schreibt.

Beides Richtig.

Er darf in der Zeit halt nur nicht auf der IRQ-Leitung und der CPU-Kommunikations-Leitung lauschen.
Die müssen währenddessen einfach ignoriert werden, dann ist das ganze Atomar

Hä?  Ich will ja nicht unhöflich sein aber Du schreibst da wirres Zeugs.


Grüße
Erik

[bluecode]

Was ist wenn bei beiden CPUs die Daten nicht im Cache sind? Dann kommen 2 ganz normale Speicher-Lese-Zugriffe. Ich kann nicht erkennen wie damit die Atomizität gewährleistet werden soll.

Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?

erik hat nicht von zeitgleichem Schreiben gesprochen,

Es geht mir darum das zwischen dem Lesen und dem Schreiben der einen CPU eine andere überhaupt die Lock-Variable lesen kann (ohne das eine von beiden CPUs das bemerkt). Der Lese-Zugriff der anderen CPU bringt die selben Daten und damit geht die andere CPU eben auch davon aus (so wie die erste CPU) das der Lock noch frei ist und fühlt sich hinterher als rechtmäßiger Besitzer (so wie auch die erste CPU). Daran ändert auch nichts das dann beide CPUs später einen "irgendwie gesicherten" Schreibzugriff durchführen (beide mit den selben Daten), dann ist es schließlich schon zu spät. Die Entscheidung (Lock bekommen oder nicht) wird zwischen dem Lese-Zugriff und dem Schreib-Zugriff getroffen und alles externe was zwischen diesen Zugriffen passiert beeinflusst diese Entscheidung eben nicht.

siehe oben, abgesehen davon bin ich nicht dumm, du brauchst das Problem nicht 3mal wiederholen, ich habe es auch beim ersten Mal verstanden, aber ich sehe nicht warum man das nicht in Hardware implementieren können sollte mit #LOCK zB.

....was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.

So sollte es sein, aber den Intel-Dokus kann man nicht entnehmen das es wirklich so ist.

Das es atomar ist kann man den Dokus schon entnehmen, warum es funktioniert nicht, aber das ist auch nicht Ziel der Manuals.

[Jidder]

Ist xchg wirklich so anders als cmpxchg? Also ich nehme mal an, dass auf dem Datenbus nicht gleichzeitig Daten in beide Richtungen fließen können. Der Befehl xchg muss auch erst lesen und dann schreiben. Damit müsste xchg an den selben Problemen wie die hier für cmpxchg beschriebenen leiden, sofern diese existieren.

Gerade bei sehr vielen CPUs verursacht das Cache-Kohärenz-Protokoll aber einen erheblichen Overhead so das der cmpxchg-Befehl mit Sicherheit deutlich langsamer ist.

Genauso langsam wie xchg, da die selben Protokolle verwendet werden.

A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand.

[bluecode]

xchg liest nicht, sondern vertauscht nur.
Ich... sehe...

[erik.vikinger]

Hallo,

Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?

Das darf sie schon. Aber es soll ja gerade der Vorteil von cmpxchg sein das erst beim Schreibzugriff, falls dieser überhaupt notwendig ist, entsprechende Sicherungsprotokolle benutzt werden. Das ist doch der Vorteil von cmpxchg gegenüber von xchg, oder irre ich da?

abgesehen davon bin ich nicht dumm, du brauchst das Problem nicht 3mal wiederholen, ich habe es auch beim ersten Mal verstanden, aber ich sehe nicht warum man das nicht in Hardware implementieren können sollte mit #LOCK zB.

Entschuldige bitte, aber ich hatte nicht den Eindruck das Du verstehst warum ich xchg vertraue und cmpxchg nicht. Bei cmpxchg hast Du immer gesagt das der Lesezugriff noch keine (wirksamen) Sicherheitsmaßnahmen ergreift (und sogar nur im Cache arbeiten könnte) und das finde ich einfach nicht vertrauenerweckend.
Ich habe nie gesagt das man cmpxchg nicht sicher implementieren kann (alle anderen CPU-Hersteller können sowas oder ähnliches ja schließlich auch), ich sage nur das Intel sich dazu ausschweigt und ich aufgrund dessen kein Vertrauen zum cmpxchg habe. Die Infos die man über cmpxchg findet sind wage bzw. widersprüchlich und das schreckt mich eben ab.

Das es atomar ist kann man den Dokus schon entnehmen, warum es funktioniert nicht, aber das ist auch nicht Ziel der Manuals.

Da haben wir offensichtlich verschiedene Ansichten bezüglich einer CPU-Dokumentation. Bei anderen Herstellern werden solche Mechanismen sehr ausführlich erläutert, ARM ist da nur ein Beispiel von vielen, was auch eindeutig die elementare Wichtigkeit solcher Details zeigt (SMP ist schließlich sehr im kommen). Bei Intel geht das offensichtlich nicht (jedenfalls nicht bei cmpxchg aber bei xchg schon) und das stört mich.

Ist xchg wirklich so anders als cmpxchg? Also ich nehme mal an, dass auf dem Datenbus nicht gleichzeitig Daten in beide Richtungen fließen können. Der Befehl xchg muss auch erst lesen und dann schreiben. Damit müsste xchg an den selben Problemen wie die hier für cmpxchg beschriebenen leiden, sofern diese existieren.

Beim xchg-Befehl werden die Schreibdaten gleich mit in die Lese-Anforderung rein gepackt. Die Atomizität entsteht im Speichercontroller weil dieser den einen Job, mit 2 gegensätzlichen Speicherzugriffen, atomar ausführt. Einen Speichercontroller so zu entwickeln das er Jobs (auch wenn sie aus mehreren Teilen bestehen) seriell ausführt ist ungleich einfacher als die Entwicklung eines zuverlässigem Cache-Kohärenz-Protokolls. Wenn die Lock-Variable in keinem Cache ist wird für xchg auch kein Cache-Kohärenz-Protokoll benötigt und wenn doch dann müssen die betreffenden Cache-Lines nur zurückgeschrieben oder invalidiert werden, das ist deutlich simpler und wahrscheinlich auch schneller.

A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand.

Das ist auch kein Wunder weil der CPU-Kern ja vom absenden der speziellen Leseanforderung (mit den Schreibdaten) bis zur Antwort (mit den Lesedaten) untätig warten muss, 100 Takte sind da in größeren Systemen bestimmt noch optimistisch gerechnet. Wenn cmpxchg keine (IMHO unzulässigen) Optimierungen machen würde wäre es kein Stück schneller, da ich davon ausgehe (ohne es genau zu wissen) das sich cmpxchg mit lock-Präfix ähnlich verhält ist es sicher nicht schneller als xchg.
Ich sehe da eher noch ein anderes Performance-Problem: die Speicherstelle mit der Lock-Variable muss irgendwie vom Lesezugriff bis zum Schreibzugriff gesichert werden, in dieser Zeit können keine anderen CPUs auf diese Lock-Variable (oder die gesamte Cache-Line) zugreifen. Beim xchg wird der Speichercontroller nur so lange blockiert wie 2 DRAM-Zugriffe dauern (eigentlich nur 1 Zugriff plus ein paar Take fürs schreiben da die RAS/CAS-Zyklen ja nur einmal beim Lesezugriff benötigt werden).


Wirklich klären können wir das wohl nur mit einem kompetenten CPU-Entwickler von Intel.


Grüße
Erik

[erik.vikinger]

Hallo,

Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?

Weil es kein #LOCK-Signal mehr gibt. Das war früher, wo es noch einen einzigen zentralen Frondside-BUS gab an dem alle CPUs hingen, mal aktuell aber seit den Opterons mit dem HyperTransport-Netzwerk oder den Core i7 mit dem QPI-Netzwerk gibt es keine zentrale Stelle mehr über die alle Speicherzugriffe müssen und an der man ein #LOCK-Signal implementieren könnte. Diese Aufgabe muss jetzt das dezentralisierte Cache-Kohärenz-Protokoll übernehmen und das ist gerade bei vielen CPUs ein sehr komplexes System. Weder von Intel noch von AMD bekommt man da irgendwelche Infos wie das genau funktioniert. Da jedes Byte im Speicher aber einen Heimat-Speichercontroller hat würde es sich gerade hier anbieten den xchg-Mechanismus zu nutzen und die Lock-Variablen nie in einen Cache zu lassen.
Natürlich könnte der CPU-Kern beim cmpxchg-Befehl mit lock-Präfix vor dem Lesezugriff die betreffende Cache-Line zur exklusiven Nutzung reservieren. Aber was ist wenn mehrere CPUs sich zeitgleich dazu entschließen, dann müsste das Cache-Kohärenz-Protokoll einen Gewinner ermitteln und allen beteiligten diesen Gewinner mitteilen bevor auch nur der eigentliche Daten-Inhalt der betreffenden Cache-Line zur Gewinner-CPU geschickt wird. Das ist natürlich alles möglich (wenn auch etwas komplex) aber es ist sicher nicht schneller als xchg (selbst wenn hier Cache-Lines getrasht werden müssen). Genau da ist gerade der Widerspruch, da ja gesagt wird das cmpxchg nur im Schreibfall solch aufwendige Maßnahmen ergreift.
Entweder funktioniert der cmpxchg-Befehl nicht ordentlich oder Intel belügt uns was dessen Performance/Implementierung angeht, ich persönlich tippe auf letzteres. Vertrauen wird so definitiv nicht geschaffen.


Grüße
Erik

[Jidder]

Das klingt ja immer mehr nach Verschwörungstheorie. Deine Meinung ist also, dass Intel - Hersteller von Prozessoren mit Milliarden Transitoren - vorsätzlich ein fehlerhaftes Lockingprotokoll implementiert, weil der korrekte Weg zu kompliziert wäre?

Edit: Außerdem lockt cmpxchg bereits beim Lesen.

[erik.vikinger]

Hallo,

Das klingt ja immer mehr nach Verschwörungstheorie. Deine Meinung ist also, dass Intel - Hersteller von Prozessoren mit Milliarden Transitoren - vorsätzlich ein fehlerhaftes Lockingprotokoll implementiert, weil der korrekte Weg zu kompliziert wäre?

Nein, ich denke schon das Intel es ordentlich macht, aber wenn Intel den cmpxchg-Befehl ordentlich implementiert dann ist er definitiv langsamer (und aufwändiger) als xchg. Ich schrieb doch eindeutig das ich Intel als Lügner und Geheimniskrämer betrachte.

da ich davon ausgehe (ohne es genau zu wissen) das sich cmpxchg mit lock-Präfix ähnlich verhält ist es sicher nicht schneller als xchg.

Hier hab ich mich geirrt. cmpxchg kann sich nicht so wie xchg verhalten weil es die gelesenen Daten ja erst prüft bevor eventuell ein Schreibzugriff ausgelöst wird. Die Simplizität von xchg, wegen seinem bedingungslosen schreiben, kann der cmpxchg-Befehl mit lock-Präfix gar nicht erreichen.


Edit

Edit: Außerdem lockt cmpxchg bereits beim Lesen.

Logisch betrachtet muss es ja auch so sein (schreib ich doch schon die ganze Zeit), aber dann frage ich mich woher der beworbene Performancevorteil kommt.


Grüße
Erik

[Jidder]

Logisch betrachtet muss es ja auch so sein (schreib ich doch schon die ganze Zeit), aber dann frage ich mich woher der beworbene Performancevorteil kommt.

Hier im Thread wurde das geringere Cache Thrashing als Vorteil genannt. Außerdem ist die Semantik von cmpxchg eine andere als alles, was du mit xchg + weitere Befehle bauen kannst. Also es lassen sich zum Beispiel Algorithmen implementieren, die mit xchg nicht machbar sind, beziehungsweise bessere "Performance" (z.B. wait-freedom) haben.

[erik.vikinger]

Hallo,

Außerdem ist die Semantik von cmpxchg eine andere als alles, was du mit xchg + weitere Befehle bauen kannst. Also es lassen sich zum Beispiel Algorithmen implementieren, die mit xchg nicht machbar sind, beziehungsweise bessere "Performance" (z.B. wait-freedom) haben.

Das mit cmpxchg bestimmte Dinge "einfacher" (zumindest für den Assembler-Programmierer) gehen steht außer Frage. xchg ist nur für einfache Locks geeignet so wie eben ein klassischer Test-and-Set-Befehl, aber diese Aufgabe beherrscht xchg mit maximaler Effizienz.

Hier im Thread wurde das geringere Cache Thrashing als Vorteil genannt.

Okay, dann wollen wir uns das mal an einem Beispiel ansehen:

Ich bleibe bewusst bei einem einfachen Lock (0x00 für frei und 0x01 für belegt) und beziehe mich für die xchg-Variante auf meinen 4-Zeiler vom 17.03.
Folgende Umgebung: 8 CPUs (Anzahl der Kerne pro CPU lassen wir der Einfachheit halber mal bei 1), jede mit eigenem Speicher in einem modernem ccNUMA-CPU-Netzwerk (ob per HyperTransport oder QPI ist auch egal, ich denke die Unterschiede sind gering, auch wenn AMD und Intel das natürlich ganz anders darstellen).
A--B--C--D
|  |  |  |
E--F--G--H
Die CPUs A und H wollen (fast) zeitgleich einen Lock betreten dessen Lock-Variable (einfaches Byte) im Speicher der CPU G liegt. Der Lock ist momentan frei, also 0x00. Falls die Cache-Line mit der Lock-Variable in einem Cache liegt (was nicht in jedem meiner Szenarien so ist) dann modifiziert in CPU D.


- xchg-Szenario:
Das Lock-Byte liegt in keinem Cache weil die betreffende Page als non-cachable markiert ist. Die CPUs A und H schicken jeweils eine Locked-Exchange-Anfrage an CPU G, die enthaltenden Schreibdaten sind jeweils 0x01. Eine von beiden Anfrage erreicht die CPU G als erstes und der Memory-Controller antwortet mit einer 0x00 für den Gewinner und mit 0x01 für den Verlierer. Die Gewinner-CPU weiß das der Lock vorher frei war und fühlt sich zu recht als neuer Eigentümer (in der Lock-Variable steht nun sicher 0x01) und die Verlierer-CPU weiß das der Lock bereits belegt war und versucht es noch mal. Ich denke das Szenario ist recht klar und mann kann sich ziemlich genau ausrechnen wie lange der xchg-Befehl dauert: 2 * Transport-Zeit der Messages und ein mal DRAM-Zugriff (fürs Lesen, das Schreiben auf eine bereits aktive DRAM-Zeile können wir jetzt mal vernachlässigen), insgesamt ist das einem normalem Lesezugriff sehr ähnlich. Selbst wenn der Speicher-Controller die Jobs umsortieren sollte ist das kein Problem, dann gewinnt eben die andere CPU. Ein Cache-Kohärenz-Protokoll ist nicht erforderlich weil ja non-cachable. Der Zeitbedarf für vorher frei und vorher belegt ist logischerweise immer gleich.
Falls die Lock-Variable in einem der Caches liegt, was bei einer als cachable gekennzeichneten Page ja sein kann, dann muss vorher natürlich eine Write-Backe-Message an alle CPUs übermittelt werden. Wie lange das dauert kann ich nicht genau sagen aber es ist möglicherweise eventuell länger als der xchg-Befehl an sich braucht. Die CPU, welche den xchg-Befehl ausführt, müsste entweder pauschal eine bestimmte Zeit warten oder von der entferntesten CPU eine Rückmeldung bekommen. Alternativ, zur Beschleunigung, könnte man die Locked-Exchange-Anfrage einfach hinter der Write-Back-Message hinterher schicken und alle CPUs müssten dafür sorgen das sich die Messages nicht überholen, das heißt das bei einer CPU wo die betreffende Cache-Line modifiziert ist diese zuerst geschrieben werden muss und dann die 2 Messages erst weitergeleitet werden dürften. Falls die Locked-Exchange-Anfrage (welche natürlich nicht vervielfältigt werden darf, im Gegensatz zur Write-Back-Message welche ja an alle CPUs gebroadcastet werden muss) von CPU A über CPU E geleitet wird und die modifizierte Cache-Line in CPU D ist dann wird das zwar etwas kompliziert aber ist bestimmt noch möglich, CPU G müsste die Locked-Exchange-Anfrage so lange verzögern bis alle Write-Backes durchgeführt wurden. Den Zeitbedarf für dieses Cache-Kohärenz-Protokoll kann ich nur schwer abschätzen, mit allen Optimierungen sollte es etwas weniger sein als der xchg-Befehl alleine benötigt.

- das ARM-Szenario mit ldrex und strex:
Auch hier ist die betreffende Page als non-cachable markiert. Der ldrex-Befehl holt aus dem Speicher das betreffende Byte und richtet im Memory-Controller der CPU G einen Hardware-Lock ein. Die CPU entscheidet dann anhand des gelesenen Wertes ob der (SW-verwaltete) Lock noch frei war und schreibt immer 0x01 per strex-Befehl zurück in den Speicher. Der strex-Befehl hebt auch wieder den Hardware-Lock im Memory-Controller der CPU G auf und meldet an die CPU (A oder H) den Erfolg zurück. Falls eine zweite CPU (H oder A) kurz nach dem Lesezugriff der ersten CPU auch dran kommt dann wird für den ldrex-Befehl dieser CPU kein Hardware-Lock erstellt und nach dem Schreibzugriff merkt diese das sie verloren hat (hier wäre es natürlich geschickter wenn bereits der ldrex-Befehl einen Fehler melden könnte) und wiederholt den gesamten Vorgang. Der Zeitbedarf ist ziemlich genau das doppelte der xchg-Variante, sind ja 2 komplette Zugriffe. Natürlich lasen sich zwischen den beiden Befehlen auch komplexere Dinge erledigen, mindestens alles was man mit cmpxchg auch machen kann. Der Mehrbedarf dürfte in Anbetracht heutiger CPU-Performance vernachlässigbar sein. Der Zeitbedarf für vorher frei und vorher belegt ist gleich weil die CPU leider erst nach dem abschließenden Schreibzugriff merkt ob sie erfolgreich war oder nicht (da ließe sich aber noch optimieren).
Falls die betreffende Cache-Line doch gecached ist gelten die selben Dinge wie bei xchg, nur das der zusätzliche Zeitaufwand prozentual gesehen geringer ist. Das Cache-Kohärenz-Protokoll muss vor/mit dem ldrex-Befehl erfolgen.

- cmpxchg-Szenario :
....... wer mag sich daran versuchen und zeigen wo cmpxchg mit lock-Präfix (und ohne Cache-Trashing) schneller ist? Ich lerne gerne noch dazu.
Ich hab mal etwas gegrübelt und mir ist nichts eingefallen das cmpxchg wenigstens schneller als eine optimierte ARM-Variante machen würde, an die xchg-Variante dürfte cmpxchg erst recht nicht ran kommen, selbst dann nicht wenn man das Cache-Kohärenz-Protokoll in der ungünstigsten Variante annimmt.


Grüße
Erik

[Jidder]

Das Cache-Thrashing-Argument kam ursprünglich nicht von mir. Ich hätte das besser ausdrücken sollen. Ich hab dieses Argument ohne groß drüber nachzudenken für schlüssig gehalten, weil weniger Schreibzugriffe weniger Write Backs erzeugen und damit weniger Thrashing. Das ist zumindest in deinem Modell, das ich für schlüssig halte, nicht der Fall.

[erik.vikinger]

Hallo,

Das Cache-Thrashing-Argument kam ursprünglich nicht von mir.

Stimmt, sorry.

Ich hab dieses Argument ohne groß drüber nachzudenken für schlüssig gehalten, weil weniger Schreibzugriffe weniger Write Backs erzeugen und damit weniger Thrashing. Das ist zumindest in deinem Modell, das ich für schlüssig halte, nicht der Fall.

Man könnte für den Zeitraum eines cmpxchg die Cache-Lines in den Caches der anderen CPUs "sperren" (dazu müsste es dann aber einen zusätzlichen Zustand im MESI geben) so das die CPU, welche den cmpxchg-Befehl ausführt, auf ihrer lokalen Kopie im Cache arbeiten kann. Dazu müssten vorher natürlich noch eventuelle Modifikationen von anderen CPUs (also aus dehren Caches) eingesammelt werden und davor müsste man bei mehreren gleichzeitigen Anfragen von verschiedenen CPUs, die alle einen cmpxchg (oder auch was anderes wie z.B. einen xchg) auf diese Speicherstelle machen wollen, noch einen Gewinner ermitteln (schon allein das ist nicht trivial, vor allem nicht bei mehr als 2 interessierten Teilnehmern). Nach dem Ende von cmpxchg müssten dann die anderen Cache-Lines wieder freigegeben werden (kein Schreibzugriff) oder invalidiert werden (Schreibzugriff erfolgt). Ob der ganze Aufwand in kürzerer Zeit als ein xchg durchgeführt werden kann wage ich stark zu bezweifeln, selbst die ARM-Variante zu unterbieten dürfte nahezu unmöglich sein. Nebst dessen das dieses aufwendige Cache-Kohärenz-Protokoll eine Menge Traffic, über das gesamte CPU-Netzwerk, erzeugt der die anderen CPUs am arbeiten hindert.

Einen wirklich konsistenten Überblick über die Situation einer bestimmten Cache-Line zu bekommen und zu sichern, so das dieser Überblick nicht von anderen CPUs oder anderen Bus-Mastern unterlaufen wird, stelle ich mir ziemlich schwierig vor. Da müssen eine ganze Menge an Komponenten mitspielen und es bedarf einer ordentlichen Portion extra Verwaltungs-Logik. Dann auch noch sicher zu stellen das es wirklich 100%-tig keine Lücken in diesem System gibt dürfte nahezu unmöglich sein. Ich denke schon das Intel, oder auch AMD, das tatsächlich hin bekommen könnten, aber ohne eine schlüssige Erklärung kann ich dem nicht vertrauen. Nebst dessen das ich einfache Lösungen, die oft (so wie in diesem Fall auch) schon wegen ihrer Simplizität sicherer sind, bevorzuge.

Ich selber möchte ja auch eine CPU, mitsamt Plattform, entwickeln und da ich ebenfalls SMP und CPU-lokalen Speicher vorgesehen hab (also ccNUMA), werde ich vor dem selben Problem stehen. Für den ersten Anlauf werde ich den Daten-Cache wohl im Memory-Controller lassen. Dort gibt es keinen Weg dran vorbei und es werden immerhin die DRAM-Latenzen kompensiert. Wenn der Cache in die eigentliche CPU wandern soll (natürlich noch im selben FPGA) dann wird es schwierig. Als einfaches Konzept könnte es gehen wenn die Cache-Line der aktuellen CPU immer exklusiv gehört. Wenn eine CPU auf Daten zugreifen will muss sie sich die betreffende Cache-Line zur exklusiven Nutzung besorgen, entweder beim Heimat-Memory-Controller oder bei einer anderen CPU welche diese Cache-Line momentan noch hat. Dazu muss der Memory-Controller aber für jede mögliche Cache-Line aus seinem Speicher eine Liste führen welche Cache-Line er "verliehen" hat. Außerdem könnte es sein das 2 verschiedene CPUs immer wieder auf (unterschiedliche Bytes in) eine Cache-Line lesend zugreifen und dann ständig die gesamte Cache-Line hin und her geschickt wird ohne das dazu eine reale Notwendigkeit besteht (allerdings wäre das auch ziemlich doofer Code, dagegen hab ich extra 64 Register vorgesehen). Ein wirklich gutes Konzept zu entwickeln das möglichst wenig Traffic erzeugt und gleichzeitig allen möglichen (und unmöglichen) Situationen gerecht wird ist gar nicht einfach, ich denke das wird nach der eigentlichen CPU die größte Schwierigkeit in meinem Projekt.


Grüße
Erik

[FlashBurn]

Wenn ich mich mal einmischen dürfte.

Geht es nur um spinlocks im User-Code oder auch im Kernel-Code?

Also erstmal wäre es nicht wirklich toll, wenn ihr eine Spinlock nur über xchg programiert (der lock Präfix ist wie gesagt sehr teuer, vorallem wenn man das ständig macht). Nicht umsonst gibt es die Test-And-Set Variante.

Ich bin leider noch nicht so weit das ich mir schon ne Rübe darüber machen müsste wie ich im User-Code nen Lock ohne in den Kernel zu gehen hinbekomme, aber ich würde nie eine Spinlock im User-Code nutzen. Ich meine stellt euch mal die Situation vor, der Thread bekommt die Lock und gleich danach wird der Scheduler aufgerufen und der Thread ist nicht mehr an der Reihe. Das würde heißen das er den Lock hat und alle anderen die Versuchen ihn zu bekommen müssen warten (und zwar mit einem busy-wait, ganz schlecht) und das kann unter Umständen schon mal ne Weile dauern. Das Problem ist hier halt, das man im User-Code die Interrupts nicht ausschalten kann. Problematisch ist es natürlich wenn man den Lock nur für ein paar Instruktion (Assembler-Anweisungen) braucht. Da wäre eine Semaphore/Mutex natürlich totaler Overhead!

Ich nutze folgenden Code im Kernel für meine Spinlocks:

Code: [Auswählen]

struct spinlock_t {
uint32t volatile lock;
uint32t flags;
};

static inline void spinAcquire(struct spinlock_t *spinlock) {
asm volatile("pushfl\n\t"
"1:\tcli\n\t"
"testl $1,(%%eax)\n\t"
"je 2f\n\t"
"popfl\n\t"
"pushfl\n\t"
"pause\n\t"
"jmp 1b\n\t"
".align 4,0x90\n\t"
"2:\tlock bts $0,(%%eax)\n\t"
"jc 1b\n\t"
"popl %[output]\n\t"
"cli"
:[output] "=q"(spinlock->flags)
:"a"(spinlock)
:"memory", "flags");
}

static inline void spinRelease(struct spinlock_t *spinlock) {
//look if ints were enabled or disabled
asm volatile(""
:
:
:"memory");
spinlock->lock= 0;

if(likely(spinlock->flags & 0x200))
asm volatile("sti");
}

Ist halt die Test-And-Set Variante mit dem Deaktivieren der Interrupts.

[erik.vikinger]

Hallo,

Geht es nur um spinlocks im User-Code oder auch im Kernel-Code?

Ich denke um beides.

Also erstmal wäre es nicht wirklich toll, wenn ihr eine Spinlock nur über xchg programiert (der lock Präfix ist wie gesagt sehr teuer, vorallem wenn man das ständig macht). Nicht umsonst gibt es die Test-And-Set Variante.

Der BTS-Befehl ist ohne lock-Präfix aber nicht Multi-CPU-sicher! Warum das so ist habe ich in diesem Thread nun erschöpfend genug erklärt. In Deinem Quell-Code benutzt Du ja schließlich auch das lock-Präfix. Wenn man die Sicherheit will muss man auch den Preis für das lock-Präfix bezahlen!

Ich bin leider noch nicht so weit das ich mir schon ne Rübe darüber machen müsste wie ich im User-Code nen Lock ohne in den Kernel zu gehen hinbekomme, aber ich würde nie eine Spinlock im User-Code nutzen.

Warum nicht? Wenn man den Spinlock nur braucht um 3 Speicherzugriffe durchzuführen (z.B. kleine Struktur atomar modifizieren) dann lohnen zwei teure SYSCALLs wahrlich nicht.

Ich meine stellt euch mal die Situation vor, der Thread bekommt die Lock und gleich danach wird der Scheduler aufgerufen und der Thread ist nicht mehr an der Reihe. Das würde heißen das er den Lock hat und alle anderen die Versuchen ihn zu bekommen müssen warten (und zwar mit einem busy-wait, ganz schlecht) und das kann unter Umständen schon mal ne Weile dauern.

Das ist natürlich ein Problem, für das es aber ein paar hübsche Lösungen gibt. Zum einen kann der wartende Thread nach jedem fehlgeschlagenen Versuch die restliche Zeitscheibe freigeben damit der Thread der den Lock gerade hat möglichst schnell wieder an die CPU kommt und fertig wird. Bei Locks die immer nur kurz belegt werden ist das die effizienteste Lösung. Bei Locks die länger belegt werden ist es meist günstiger dafür den OS-Kernel zu bemühen der den wartenden Thread schlafen legt und sofort aufweckt sobald der Lock freigegeben wird (noch im Freigabe-SYSCALL). Dort könnte man dann auch so tolle Sachen wie Prioritätsvererbung einbauen, damit der Low-Prio-Thread der gerade den Lock besitzt auf die selbe Prio angehoben wird wie der High-Prio-Thread welcher den Lock haben will damit dieser möglichst bald dran kommt.
Im Kernel-Mode gibt es andere Kriterien für die Wahl der richtigen Lock-Methode. Auf einer Single-CPU-Maschine muss man z.B. zwingenst die IRQs sperren für den gesamten Zeitraum wo man den Lock hat sonst kommt der nächste Dead-Lock schneller als man denkt. Auf Multi-CPU-Systemen könnte man das theoretisch auch anders machen, riskiert damit aber erhebliche Wartezeiten (im Kernel ist ja nur aktives Warten möglich).

Man muss sich eben genau den Verwendungszweck anschauen und dann das geeignetste Werkzeug benutzen.

Ich nutze folgenden Code im Kernel für meine Spinlocks:

Code: [Auswählen]

....

Was mir auffällt ist das Du in der spinRelease-Funktion zwar eine Memory-Bariere (das erste Assembler-Macro) hast aber den eigentlichen Freigabe-Speicherzugriff erst danach ausführst, das bedeutet das dieser Freigabe-Speicherzugriff auch erst deutlich später kommen kann (auch nach dem zweiten Assembler-Macro). Ich finde dieser Freigabe-Speicherzugriff sollte in das erste Assembler-Macro rein. Durch die Befehle cli und sti ist Dein code auch nicht für User-Space-Programme geeignet, ein ordentliches OS wird die Nutzung dieser Befehle im User-Mode zuverlässig verhindern.


Grüße
Erik

[FlashBurn]

Der BTS-Befehl ist ohne lock-Präfix aber nicht Multi-CPU-sicher! Warum das so ist habe ich in diesem Thread nun erschöpfend genug erklärt. In Deinem Quell-Code benutzt Du ja schließlich auch das lock-Präfix. Wenn man die Sicherheit will muss man auch den Preis für das lock-Präfix bezahlen!

Hier hast du mich ein wenig missverstanden. Was ich an dem Code den ich hier gesehen habe, zu beanstanden habe ist dass er ständig eine Schleife macht und ständig den Lock durchführt!

Deswegen sollte man ja auch die Test-And-Set Variante verwenden! Das man erst den Memorybus Locked wenn der Lock wahrscheinlich frei ist!

(im Kernel ist ja nur aktives Warten möglich)

Wie kommst du darauf? Also mein Kernel beherrscht Semaphores (ihm ist es auch egal ob es ein User oder ein Kernel-Thread, da eh alles im Kernel läuft). Also das im Kernel nur aktives warten möglich ist, ist erstmal Quatsch, das ist ne reine Implementations Sache!

[erik.vikinger]

Hallo,

Hier hast du mich ein wenig missverstanden. Was ich an dem Code den ich hier gesehen habe, zu beanstanden habe ist dass er ständig eine Schleife macht und ständig den Lock durchführt!

Der Code versucht ständig den Lock zu bekommen und jeder Versuch wird mit einem atomaren Speicher-Befehl durchgeführt (das muss ja auch so sein).

Deswegen sollte man ja auch die Test-And-Set Variante verwenden! Das man erst den Memorybus Locked wenn der Lock wahrscheinlich frei ist!

Das macht Dein Code aber auch nicht besser.
Mann könnte natürlich in einer vorgelagerten Schleife mit nem einfachen Lese-Befehl (der nichts verändern darf) erst mal warten bis der Lock frei ist und dann mit dem richtigen bts-Befehl oder xchg-Befehl oder cmpxchg-Befehl versuchen den Lock tatsächlich zu bekommen. Die Wahrscheinlichkeit ist dann jedenfalls hoch, es sein den der Code ist im User-Mode und genau dazwischen schlägt der Scheduller (Timer-IRQ) zu.

Ich habe den Eindruck wir reden etwas an einander vorbei, poste doch mal Bitte konkreten Code um genau zu zeigen was Du meinst.

Also das im Kernel nur aktives warten möglich ist, ist erstmal Quatsch, das ist ne reine Implementations Sache!

Stimmt, man kann eine Thread auch im Kernel-Mode unterbrechen.


Grüße
Erik