Linux RCU und doppelt verkettete Liste

Question

Ich lese über Read-copy-update (RCU). Ich bin mir nicht sicher, ob ich es im Falle von SMP richtig verstanden habe. Soweit ich weiß, stellt RCU sicher, dass Update atomar ausgeführt wird. Im Fall einer einzelnen verknüpften Liste ist es offensichtlich, dass das Ersetzen des alten Elements mit dem neuen Element in einer Operation durchgeführt werden kann, da dies durch Ändern des Zeigers geschieht. Aber wie kann man sicherstellen, dass RCU im Falle einer doppelt verketteten Liste immer noch atomar ausgeführt wird? Es gibt zwei Zeiger auf ein gegebenes Element (next und prev), so dass jede Änderung an diesem Element diese beiden Zeiger ändern muss. Wie kann sichergestellt werden, dass die Änderung dieser beiden Zeiger als atomare Operation ausgeführt wird? Wie es in Linux gemacht wird?

Answer 1

ich mir die gleiche Frage stellte, und eine schnelle Suche brachte a reply to a comment, von an introduction article to RCU von Paul McKenney extrahiert (wer, was ich sammeln, einer der mehrere gleichzeitige Erfinder der Ideen hinter RCU ist).

Die Frage:

Ich frage mich, ob das Weglassen der Backlinks in den Beispielen ist eine gute Sache. Die Auslassung macht die Technik trivial, da die Veröffentlichung nur einen ersetzt einen Zeiger enthält.

Was ist mit der Sekunde, zurück, eins? Ohne Unterstützung für atomare Two-Pointer Updates, wie kann sowohl die p-> prev-> next = q und p-> next-> prev = q Updates durchgeführt werden, ohne zu riskieren Kunden eine inkonsistente Sicht auf die doppelt verknüpft zu sehen Liste? Oder ist das in der Praxis kein Problem?

Danke für den Artikel, obwohl. Freue mich auf die nächste Ausgabe!

Die Antwort:

Gut, dass Sie den Artikel gefallen hat, und vielen Dank für die ausgezeichnete Frage! Ich könnte eine beliebige Anzahl von Antworten geben, einschließlich: In Produktionssystemen sind triviale Techniken eine sehr gute Sache. Zeigen Sie mir ein Beispiel, wo es sinnvoll ist, die -> prev-Zeiger unter RCU-Schutz zu durchlaufen. Anhand mehrerer solcher Beispiele könnten wir herausfinden, wie wir dies am besten unterstützen können. Konsistenz wird grob überbewertet. (Nicht alle stimmen mir dabei zu!) Betrachte selbst bei atomaren Zwei-Zeiger-Aktualisierungen die folgende Abfolge von Ereignissen: (1) Aufgabe 1 tut p = p-> next (2) Aufgabe 2 fügt ein neues Element dazwischen ein die zwei, die Aufgabe 1 gerade behandelt hat (3) Aufgabe 1 tut p = p-> prev und endet nicht dort, wo sie begonnen hat! Selbst bei einem atomaren Doppelzeiger-Update können Inkonsistenzen nicht beseitigt werden! ;-) Wenn Sie Konsistenz benötigen, verwenden Sie Sperren. In dem obigen Beispiel könnten wir eine Konsistenzstufe unterstützen, die der doppelpoligen atomaren Aktualisierung entspricht, indem wir einfach die Zeiger der Reihe nach zuweisen - entfernen Sie zum Beispiel die Pointer des vorherigen Pointers aus list_del_rcu(). Aber dies würde die Fähigkeit opfern, die Bugs zu fangen, die Pointer-Poisoning derzeit auffängt.

Es könnte also eine Zeit kommen, in der der Linux-Kernel RCU-geschütztes Traversieren von verketteten Listen in beide Richtungen erlaubt, aber wir müssen einen zwingenden Bedarf dafür sehen, bevor wir ihn implementieren.

Also im Grunde, Linux "nicht zulässt" rückwärts Traversal in beide Richtungen, wenn RCU tun. Wie im Kommentar erwähnt, könnten Sie einige neuere Hardware-Mechanismen wie Double Compare And Swap verwenden, aber sie sind nicht überall verfügbar, und wie erwähnt, können Sie immer noch Probleme mit der Speicherkonsistenz bekommen.