Thema: Locking innerhalb des Kernels

[rizor]

Nabend zusammen,

ich bin gerade dabei eine optimale Locking-Strategie fuer meinen Kernel zu entwickeln, da er ein preemptive Kernel werden soll. Das Locking der einzelnen Elemente und Subsysteme des Kernels ist kein Problem... solange die Strukturen existieren.
Nun habe ich aber Strukturen, die auch immer wieder zerstoert werden. Falls ich nun eine CPU habe, die auf einen Lock wartet, der in dem Moment zerstoert wird. Daraus resultieren zwei Probleme... Entweder die wartende CPU bekommt irgendwann den vermuteten Lock, weil der Speicher durch eine andere CPU fuer was anderes verwendet wird... dann kommt es ja zu einem unkontrollierten verhalten, oder die wartende CPU bleibt in einem Deadlock.

Ich bin momentan dabei, dass ich mir ein Konzept ueberlege, dass auch in solchen Situationen kontrolliert arbeitet. Ich hatte die Idee mit einem Flag, das angibt ob die Struktur noch passt oder eben auch nicht. EIne andere Moeglichkeit waere eine Semaphore, die bei der Zerstoerung einer Struktur aufgeloest wird und die blockierten CPUs frei gibt und ihnen den Grund fuer den Rueckruf mitteilt. Ist unter Umstaenden auch nicht die beste Idee.
Wie habt ihr das denn geloest?

Gruss,
rizor

[Svenska]

Hallo,

ich verstehe nicht so recht, was du meinst; mach mal konkreter. Daher rate ich mal rum: CPU1 möchte eine Struktur verändern und wartet auf ein Lock dafür, gleichzeitig hat CPU2 das Lock und entschließt sich, die Struktur zu vernichten. CPU1 sitzt nun in einem Deadlock. Ich rate mal weiter: Es geht um Bäume

Wenn ich mir einen Baum nehme, Wurzel - Knoten - Blatt, dann ist das so: Will ich auf das Blatt zugreifen, muss ich gegen das Blatt locken. Will ich aber das Blatt löschen, so verändere ich den übergeordneten Knoten, muss also gegen den locken.

Sollte ein CPU ein Stück des Baumes traversieren, dann geht diese in der Regel rekursiv durch den Baum, führt also (mit variierenden Abständen, je nach Tiefe) der Reihe nach eine Aktion für alle Blätter deines Knotens durch. Änderst du nun die Struktur, indem du mittendrin ein Blatt löschst, führt das zu Problemen. Ein Blatt zu locken reicht aus, wenn du nur dessen Inhalt änderst. Änderst du aber die Struktur, musst du auch Lesezugriffe auf den gesamten betroffenen Teilbaum (d.h. das Blatt und dessen Elternknoten) verhindern.

Konkret heißt das: Du brauchst ein Lock, welches Lesezugriffe auf die übergeordnete Ebene beschränkt. Wenn du dieses Lock hast, darfst du erst nachschauen, ob deine gesuchte Struktur existiert.

Wenn das, was ich jetzt geschrieben habe, total am Thema vorbeigeht, dann gib mir mal ein paar konkrete Beispiele.

Gruß,
Svenska

[FlashBurn]

Falls es wirklich um Bäume gehen sollte, warum einzelne Blätter locken (und sich damit viele Probleme holen) und nicht den ganzen Baum mit einer Read-Write-Lock schützen? So habe ich das gemacht, aber bisher habe ich auch nur Sachen gehabt, wo nur der Baum geändert wird und nicht einzelne Blätter.

Am besten guckst du dir mal Hazard-Pointers an, die könnten dein Problem lösen (die will ich auch irgendwann verwenden).

[kevin]

Ganzes Dateisystem locken, weil du grad ein Verzeichnis von der Platte lädst? Schlechte Idee...

[rizor]

Geht in die Richtung.
Ein Beispiel: Ich habe einen SLAB-Allocator und da soll nun entweder aufgeräumt werden, also freier Speicher freigegeben werden, oder der Cache selber soll zerstört werden.
Für den Cache selber brauche ich alle Locks, das ist klar. Somit gibt es dann nur auf der Struktur des Caches selber das Problem, dass es CPUs geben kann, die den Lock haben wollen. Nun zerstöre ich den Cache und die anderen CPUs stehen im Deadlock.

Ich möchte nicht immer die ganzen Strukturen locken, das ist mir nicht performant genug.

Das Locking an sich ist ja kein Thema, aber wie signalisiere ich den anderen CPUs, dass genau dieser Knoten gelöscht wird und die wartenden CPUs nicht unkontrolliert arbeiten?

Die Hazard-Pointer werde ich mir mal anschauen.
Ich hatte die Idee mit Semaphoren zu arbeiten und imer einen Status mitzugeben, der dem Thrread signalisiert ob er den Lock hat oder warum er geweckt wurde, obwohl er keine Exclusiv-Rechte hat.
Ist aber immer ein großer Speicheroverhead

[FlashBurn]

@taljeth

Naja, ich bin z.B. von einem Baum ausgegangen, in dem Thread-IDs gespeichert sind. Da ist es nicht wirklich schlimm wenn der ganze Baum gelockt wird.

Wenn man natürlich von einem Dateisystem ausgeht, ist das wieder was anderes. Zumal bei dem Bsp. sollte man doch alle "Nodes" auf dem Weg locken, damit es nicht passieren kann, das jemand anderes ein Verzeichnis über "mir" löscht und "ich" mich somit in einem Verzeichnis befinde das gar nicht mehr existiert.

Von daher würde ich immer von Fall zu Fall unterscheiden.

@rizor

Dein Problem mit dem Slab-Allocator sollte ich mir bei mir auch nochmal angucken, aber ich habe das irgendwie durch eine bestimmte Reihenfolge beim Löschen und mehreren Locks gemacht und bisher (was nicht heißen soll, das es richtig ist) ist noch nichts passiert.

[rizor]

Aber wie willst du garantieren, dass keine andere CPU auf einen der Locks wartet?
Das funktioniert in meinen Augen nicht mit Locks alleine, aber leider habe ich keine speicherschonende, performante Idee.

[kevin]

Naja, ich bin z.B. von einem Baum ausgegangen, in dem Thread-IDs gespeichert sind. Da ist es nicht wirklich schlimm wenn der ganze Baum gelockt wird.

Es kommt nicht auf den Inhalt an, sondern darauf, was gemacht wird, während der Lock gehalten wird. Ich kann mir vorstellen, dass es auch für die Taskstrukturen Sachen gibt, die etwas länger dauern.

Richtig weh tut es wahrscheinlich, wenn der Code, der den Lock hält, preemptet wird und es dann eine Weile dauert, bis er wieder drankommt. Aber gut, das sollte man an dieser Stelle wahrscheinlich sowieso vermeiden, auch mit feineren Locks.

Wenn man natürlich von einem Dateisystem ausgeht, ist das wieder was anderes. Zumal bei dem Bsp. sollte man doch alle "Nodes" auf dem Weg locken, damit es nicht passieren kann, das jemand anderes ein Verzeichnis über "mir" löscht und "ich" mich somit in einem Verzeichnis befinde das gar nicht mehr existiert.

Das ist harmlos. Alles, was du modifizierst, ist dann halt nicht mehr erreichbar, aber es stört nicht, erstmal weiter darauf zu arbeiten.

POSIX gibt es ja sogar so vor, dass man auf gelöschten Dateien weiterarbeiten kann und sie erst wirklich verschwinden, wenn alle Dateideskriptoren geschlossen sind.

[FlashBurn]

Es kommt ganz drauf an wie man das umsetzt.

Ich mache es so, das ich 2 Listen habe (empty und partial) und mit der partial Liste anfange und versuche das erste Element zu entfernen, dass mache ich solange bis das geklappt hat oder die Liste leer ist (es wird also immer die ganze Liste gelockt um das erste Element zu entfernen).
So kommt es zwar vor, dass ich soviele partial+empty Listen wie CPUs habe, aber das ist eher unwahrscheinlich und da die meisten Objekte eh nur nen Cache mit einer Page haben ist das auch nicht weiter schlimm.
Dann kommt noch hinzu, dass ich noch eine Ebene darüber habe, sprich das ich pro CPU noch nen Stack mit 4 Objekten habe und erstmal der benutzt wird.

Will ich einen Cache komplett löschen, locke ich die komplette Liste (in dem Fall die free) und entferne halt wieder das erste Element und kann dann den Cache freigeben ohne das es Probleme gibt. Das wiederhole ich solange bis die Liste leer ist.

Man kann das ganze natürlich auch noch mit Lock-free Algos implementieren, aber ob es das wirklich so bringt, wage ich doch zu bezweifeln, lasse mich aber gerne eines besseren belehren. Denn das Entfernen des ersten Elements aus einer Liste ist nun wirklich keine "lange" Angelegenheit.

Problematisch an meiner Variante ist "nur", dass durch das "ständige" Entfernen und Einfügen natürlich mehr Schreibzugriffe stattfinden als eventuell notwendig wären. Ob das wirklich ein Problem ist, kann ich aber nicht sagen.

@taljeth

Wenn ich an einer Taskstruktur arbeite, locke ich aber die Taskstruktur und nicht das Blatt! Das ist bei mir schon ein Unterschied. Es ging mir eigentlich nur darum, das sich die Position im Baum nicht verändern kann und nur wenn das geschiet, muss halt der Baum gelockt werden. Zumal man dann auch noch zw. Bäumen und Bäumen unterscheiden muss. Wenn bei nem einfachen binär Baum ein Blatt gelöscht wird, geht das ja noch, aber z.B. bei nem AVL-Baum kann das den ganzen Weg zurück zur Wurzel verändern, da finde ich es dann sinnvoller (und einfacher) den ganzen Baum zu locken.

[kevin]

Wie gesagt, je nachdem, wie lange du den Lock halten musst und wie viele Zugreifer du hast, kann es sinnvoll sein oder auch nicht, die komplette Struktur zu locken. Was für das ganze Dateisystem eine schlechte Idee ist, kann für einen kleinen AVL-Baum eine gute Idee sein.

Auf ein "kommt drauf an" kann man sich also einigen.

[rizor]

So ähnlich mache ich es auch mit dem Locking, außer, dass ich die Liste wieder freig eben, wenn ich gerade eine Page analysiere. Dadurch versuche ich halt den Paralleliserungsgrad des Slabs zu erhöhen.
Das ist ja alles kein Thema.
Was passiert, wenn du den Cache jetzt löschst, aber eine andere PU in dem moment auf den Cache zugreifen möchte?

[bluecode]

[...] wenn der Code, der den Lock hält, preemptet wird [...]

Normalerweise verhindert man preempten sobald man einen Lock hat (dadurch, dass zB das IF beim Locken gesetzt wird) und gibt es bei dem passenden unlock wieder frei. Sonst hast du einen Deadlock, wenn der preemptende Code auch gerne den gleichen Lock haben will (zumindest bei normalen Locks, soll ja auch rekursive geben oder wie auch immer das heißt).

Was passiert, wenn du den Cache jetzt löschst, aber eine andere PU in dem moment auf den Cache zugreifen möchte?

Kann man irgendwie verhindern, dass der Andere "zu dem Cache kommt bzw. den Cache erreicht"? Was ich damit meine ist folgendes (am Beispiel des Baums): Wenn ich ein Blatt löschen will und dabei einen Lock auf den Vater und das Blatt selbst habe (und auch bei allen anderen Operationen zuerst einen Lock auf den Vater, dann auf das Blatt hole), dann kann niemand auf die Idee kommen das Blatt zu locken, während ich das Kind lösche und am Vater den Zeiger auf null setze, da ich der Einzige bin, der den Vater gelockt hat. Nachdem ich beide ungelockt habe, kann auch niemand auf die Idee kommen, da der Zeiger ja jetzt null ist.

Zu Hazard Pointern: Die funktionieren fundamental anders als ein normales Freigeben des Speichers, denn es wird erstmal ein Pool (pro Thread/Core) angelegt in dem die von diesem Thread/Core entfernten Pointer zwischengelagert werden bis sie wirklich gefreet werden können (nämlich dann, wenn kein Anderer Thread mehr einen hazard pointer darauf hat). Das ist sowas in Richtung lokale garbage collection.

[rizor]

Stimmt, das funktioniert einwandfrei bei den unteren Elementen eines Baums.
Was ist nun, wenn du den gesamten Baum löschen möchtest?
Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Es ist klar, dass die CPU der Lock-Besitzer unterbrochen werden kann.
Aber das mache ich ja erst, sobald ich den Lock möchte.

[bluecode]

Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Einen Lock für den (imaginären) Vorgänger der Wurzel. Beim Abwärtslaufen des Baums fängst du mit dem Lock des imaginären Vorgänders der Wurzel an, dann locken der Wurzel, dann eines der beiden Kinder der Wurzel, dann freigeben des (imaginären) Vorgängers der Wuzel, etc...

Was ist nun, wenn du den gesamten Baum löschen möchtest?

Um den ges. Baum zu löschen musst du alles locken und dann löschen. Oder du löscht die Knoten einzeln Bottom-up. Problem bei letzterem ist natürlich, dass jemand so fies sein könnte und zwischendrin einfügt. Aber meistens will man sowieso keinen ges. Baum löschen (beim osdev logischerweise). Was ich oben zum Löschen geschrieben habe bezog sich auch nur auf Blätter (nicht auf innere Knoten) btw.
edit (mindestens der 9000ste): Es kommt ehrlich gesagt _sehr_ darauf an welche (anderen) Operationen (noch) und mit welcher Semantik unterstützt werden soll. Insofern sollte man sich darauf wohl vorher einigen.

[kevin]

Normalerweise verhindert man preempten sobald man einen Lock hat (dadurch, dass zB das IF beim Locken gesetzt wird) und gibt es bei dem passenden unlock wieder frei.

Bei Spinlocks, klar. Aber bei einer Mutex doch nicht unbedingt?

Sonst hast du einen Deadlock, wenn der preemptende Code auch gerne den gleichen Lock haben will

Einen Deadlock nicht, beim Warten auf den Lock wird ja auch irgendwann wieder weitergeschedult. Bei einem Spinlock ist das natürlich Ressourcenverschwendung, aber zum Stillstand kommt es nicht.

[kevin]

Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Irgendwo brauchst du halt eine oberste Ebene, die nicht weggeht. Im Zweifelsfall eine statische Variable als Lock.

[bluecode]

@taljeth: Innerhalb des Kernels (-> siehe Topic ) natürlich schon. Das Analogon im Userspace wären Signale bei denen der Handler einen bereits vom momentanen Thread gehaltenen Lock nochmals haben will. Da kann das unlock niemals kommen, da der Thread mit dem Lock läuft und auf genau diesen Lock nochmals wartet.

[kevin]

Zwischen Kernel und Userspace gibt es nicht viele Unterschiede, außer dass der Kernel mehr Rechte hat. Du meinst vermutlich innerhalb von IRQ-Handlern?

[bluecode]

Ich meine wohl prinzipiell den Fall, dass das was da preemptet wurde nicht auf eine andere CPU geschedult wird. Im speziellen trifft das IRQ-Handler und Signale. An Kernelthreads dachte ich im obigen Beitrag wohl nicht.

[rizor]

Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Irgendwo brauchst du halt eine oberste Ebene, die nicht weggeht. Im Zweifelsfall eine statische Variable als Lock.

Die Idee finde ich aber auch nicht so gut, da ich dadurch eine Serialisierung drin habe, die an sich unnötig ist.
Vermutlich ist die performanteste Idee wirklich eine Semaphore, die Informationen nach außen trägt.