Thema: Locking innerhalb des Kernels

[FlashBurn]

Du musst doch nen Zeiger auf die Wurzel irgendwo speichern, oder? Das ist doch meistens ne statische Variable, die nie freigegeben wird und wenn du diese durch einen Lock schützt kann auch nichts schiefgehen.

Es wäre für dich vorteilhafter wenn du dein Problem ganz genau beschreiben würdest.

Wenn ich bei mir nen Cache (mit mehreren Objekten) löschen möchte, dann nehme ich diesen aus der empty-Liste und diese herausnehmen, wird durch einen Lock geschützt und sobald der Lock wieder frei ist, kann auch kein anderer Thread/CPU mehr auf diesen Cache "zugreifen".

Wofür verwendest du bei deinem SlabAllocator nen Baum?

[rizor]

Das hat nichts mit den Bäumen zu tun. Das Thema wurde parallel aufgeworfen.
Bei einem Baum ist mir die Wurzel klar. Sowas habe ich bei SLABs natürlich nicht.
Da habe ich keine Verwaltung von Caches.
Ein Cache wird angefordert und einfach an den jeweiligen Thread oder das Subsystem weitergegeben. Beim Allozieren eines Objekts wird der Cache mit übergeben. Dadurch habe ich einen kontrollierten Einstieg und es gibt keine Serialisierung bei unterschiedlichen Anfragen. Das ist halt mein Hauptproblem. So habe ich recht viele Datenstrukturen implementiert, damit der Parallelisierungsgrad so hoch wie möglich ist.

[bluecode]

Wo kommt denn da überhaupt das Problem auf, dass ein Cache freigegeben wird, während andere noch darauf zugreifen? Normalerweise alloziert man doch halt in dem Subsystem einen/mehrere Caches und gibt die beim Herunterfahren wieder frei, oder?

Aber man könnte wohl wie folgt das Problem lösen: Einen reference-counter (der natürlich atomar in/dekrementiert wird) pro Cache halten (innerhalb des Subsystems). Das Subsystem setzt den beim Initialisieren auf 1 und falls es meint den Cache freigeben zu wollen dekrementiert es den reference-counter (falls der Wert vor dem dekrement 1 ist, wird freigegeben). Benutzt werden darf der Cache nur falls der counter >= 1 ist. Beim Benutzen des Caches wird vorher der counter inkrementiert (*) und nach der Benutzung wieder dekrementiert. Falls der counter dabei vorher (vor dem Dekrementieren) den Wert 1 hatte wird er freigegeben.

(*) sollte man dann wie folgt machen:
snapshot = atomic_read(counter);
if (counter < 1)return;
atomic_cmpxchg das counter mit snapshot vergleicht und falls gleich auf snapshot + 1 setzt, andernfalls von vorne beginnen

Das mit dem Dekrementieren geht wohl analog.

[rizor]

Die Idee mit dem Counter finde ich echt nicht schlecht.
Werde mal schauen, wie ich das implementieren kann.
Der SLAB-Allocator war jetzt nur ein Beispiel (unter Umständen nicht das beste).
Aber es gibt ja auch dynamische Strukturen, wie z.B. Prozess-/Thread-Strukturen,die koordiniert abgearbeitet werden müssen. Ich versuche ein halbwegs generisches Konzept zu finden, damit ich das dann nicht immer wieder neu machen muss.

[bluecode]

Für Prozess/Threadstrukturen funktioniert wohl ein Counter auch, wobei der Thread/Prozess selbst beim Erstellen um eins erhöht und beim zerstören um eins erniedrigt. Alle anderen müssen in irgendeiner Weise ein Handle auf den Thread öffnen, wobei beim erstellen/zerstören des Handles ebenfalls der Counter entsprechend angepasst wird.

[FlashBurn]

Mir ist immer noch nicht so ganz das eigentliche Problem klar. Was sind für dich Caches? Für mich ist ein Cache (im Zusammenhang mit nem Slab-Allocator) eine oder mehrere Pages wo Objekte von einem bestimmten Typ "drin" sind.

Was das andere Bsp mit Task-/Threadstrukturen betrifft, wo ist da das Problem?

Ich würde mir halt Gedanken machen, wer kann wann (und auch wer wird wann) auf diese Strukturen zugreifen? Ich meine wird z.B. ein Pointer auf die Thread-Struktur irgendwo zw. gespeichert und später schnelleren Zugriff zu haben oder wird immer nach einer ID gesucht und als nächstes der Thread gelockt?

Wenn es darum geht, das eine CPU nach Thread A gesucht hat und den Pointer für einen späteren Zugriff zw. speichert und eine andere CPU kurz danach den Thread A löscht. Dann wären wirklich Hazard-Pointers das performanteste (vllt nicht das beste in Bezug zum Aufwand). Denn mit dem Reference-Counter wartest du also mit dem Löschen solange bis keiner mehr darauf zugreift, aber das kann unter Umständen "ewig" dauern. Von dem Gesichtspunkt ist das nicht wirklich performant.

[bluecode]

Denn mit dem Reference-Counter wartest du also mit dem Löschen solange bis keiner mehr darauf zugreift, aber das kann unter Umständen "ewig" dauern. Von dem Gesichtspunkt ist das nicht wirklich performant.

öhm... Prinzip ist bei dem reference-counter, dass der letzte aufräumt, da wird nicht gewartet. Insofern hat das erstmal ganrichts mit Performanz zu tun.
Bei hazard pointer kann es btw. auch so sein, dass etwas nicht gelöscht wird. Nämlich dann, wenn es immer jemand anderen gibt, der es im hazard-pointer record hat. Ich bin mir übrigens nicht sicher, ob du überhaupt hazard pointer hier so anwenden kannst wie das reference-counting. Bei hazard pointern darf es nämlich nicht so sein, dass eine Referenz die ich löschen will in einem anderen hazard pointer record "plötzlich" wieder auftaucht (*), dass könnte aber bei dem beispiel mit den caches nicht gegeben sein.

(*) Beim Löschen einer Referenz geht man ja ganz normal sequentiell durch die hazard pointer records der anderen Threads und schaut ob die Referenz da drinsteht. Wenn man einmal durch ist muss man schließen können, dass auch zu diesem Zeitpunkt niemand die Referenz neu in seinen hazard pointer record geschrieben hat. Das wird bei normalen Datenstrukturen (zB Liste) dadurch sichergestellt, dass Dinge die ich löschen will von der Datenstruktur nicht mehr "erreichbar" sind, die Operationen auf der Datenstruktur aber nur hazard-pointer halten, die zum Zeitpunkt des Setzens (nicht ganz richtig, eigentlich zum Zeitpunkt des Validierens des hazard pointers) von der Datenstruktur aus "erreichbar" sind.

edit: Nochmal drüber nachgedacht. Man könnte folgendes machen. Man benutzt das unterste Bit eines Zeigers auf den Cache als ein Invalid-Bit. Wenn jemand den Cache löschen will, dann setzt er atomar das Bit (und zusätzlich den Rest des Zeigers auf 0) und kann den Cache löschen (wenn er aus allen hazard pointer records verschwunden ist). Wenn ich auf den Cache zugreifen will, hole ich mir atomar einen Snapshot des Zeigers, setze meinen hazard pointer und validiere ihn dadurch, dass ich atomar schaue ob das Invalid-Bit immernoch gelöscht ist (und der pointer noch der gleiche ist, falls man auch nen neuen cache allozieren darf) in dem globalen Zeiger. Falls dem so ist, dann kann ich weitermachen, falls nicht, setze ich meinen hazard pointer record zurück und gebe auf.

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

Die Idee finde ich aber auch nicht so gut, da ich dadurch eine Serialisierung drin habe, die an sich unnötig ist.

Wieso kriegst du da eine unnötige Serialisierung? Und wie oft kommt es überhaupt vor, dass du die Wurzel löschst?

[bluecode]

hm, noch ne bisschen andere Idee: Man könnte es wohl auch mit einem reader-writer-Lock machen. Wobei writer heißt, dass derjenige den Cache löschen und den Pointer auf 0 setzen darf, und alles andere ein reader ist, bin mir gerade nicht sicher, ob die Idee schon aufkam. Schwierig ist dabei wohl die _faire_ Implementierung eines reader-writer-Locks im Kernel.

[kevin]

An einen RwLock habe ich gedacht, ja. Eine Mutex wäre Blödsinn, wenn es wirklich nur das Löschen schützen soll.

Und das mit der Fairness spielt dann auch keine Rolle: Der, der löschen will, gewinnt und danach will nie wieder ein anderer Reader oder Writer den Lock haben.

[bluecode]

hm, stimmt, dass mit dem Gewinnen ist garnicht so schwierig wie ich dachte: Es gibt einen Counter, wobei das höchste Bit für einen Schreibzugriff reserviert ist, der Rest des Counters zählt die momentan aktiven Leser. Ein Schreiber setzt zuerst das Bit atomar, wartet dann bis der Rest 0 ist. Ein Leser liest zuerst atomar einen Snapshot, überprüft ob das Schreiberbit gesetzt ist (falls ja wird abgebrochen), andernfalls wird der globale wert versucht mit cmpxchg durch Snapshot+1 zu ersetzen.

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

Wieso kriegst du da eine unnötige Serialisierung? Und wie oft kommt es überhaupt vor, dass du die Wurzel löschst?

Wenn ich immer über eine Wurzel einsteigen müsste, damit ich meine Strukturen finde, hätte ich eine unnötige Serialisierung.
Das möchte ich vermeiden (außer beim VFS). Wobei ich mir da auch noch nicht wirklich sicher bin. Unter Umständen ist da viel mit Caching machbar um sogar das weitestgehend zu vermeiden.

Die Idee mit dem atomran Flag finde ich gut. Das ist wahrscheinlich das beste.
Mein Problem war/ist, das ich unter Umständen mehrere CPUs habe, die auf eine Struktur zugreifen wollen. Wenn nun einer die Struktur wegräumt (bei Threads/Prozessen wahrscheinlich sogar besser erklärt), möchte der Rest trotzdem noch ran.
Ein Szenario: Ich habe mehrere Threads eines Prozesses, die alle echt parallel auf mehreren CPUs laufen.
Nun macht ein Thread was illegales oder beendet den Prozess, Der Kernel räumt die Strukturen weg und beendet natürlich die Threads auf den anderen CPUs. Was passiert nun, wenn einer der Threads sich durch einen Syscall oder so im Kernel befindet, der gerade die IRQs deaktiviert hat und auch auf die Prozessstruktur zugreifen möchte? Momentan wartet der einfach auf den Lock, egal ob er jemals dran kommt oder nicht. Das war mein Problem. Das sollte durch die atomaren Flags vermeidbar sein oder durch den Reference-Counter.

[FlashBurn]

Wenn dein Probblem das Beenden von Tasks/Prozessen ist, dann mal folgender Vorschlag.

Bei mir kommt jeder beendeter Thread einfach in eine Liste, die wiederrum den Thread-Killer aktiviert (ist nen Kernel-Thread) und erst dieser räumt alles für den Thread auf, was der nicht machen konnte (z.B. den Stack), dann wird geguckt ob es der letzte Thread des Tasks ist, ist dass der Fall wird der komplette Task gelöscht.

Damit jetzt nicht ein neuer Thread erstellt werden kann, obwohl der Task eigentlich schon beendet sein soll, wird der Task (das gleiche gilt für jeden Thread der beendet werden soll) aus der Task-Liste genommen, um nicht mehr erreichbar zu sein und der Status wird auf _KILLED gesetzt.

Sowas ähnliches (ein Status-Bit) zusammen mit Hazard-Pointern (die sollten besser, einfacher und schneller sein, als Reference-Counting bzw. gab es beim Reference-Counting auch irgendein Problem, welches zwar selten auftritt, aber es tritt auf und deswegen will ich das auf keinen Fall nutzen) könnte eine Lösung sein, wenn du alles mögliche parallelisieren willst und auch Pointer in einem Cache behalten willst.

Ansonsten sollte man sich immer überlegen, ob die Parallelisierung, besonders mit den ganzen Problemen die da mit kommen, besser und schneller ist, als einfach nur ein oder ein paar vernünftige Locks.

Edit::

Ich glaube ich habe da nen Denkfehler bezüglich der Hazard-Pointers, oder? Es wird doch bei jedem "freigeben" eines Pointers überprüft ob schon eine gewisse Anzahl von Pointern in der Liste (per Thread) sind und dann werden die Pointer eventuell freigegeben (wenn kein anderer Thread mehr auf den Pointer zugreift). Sprich man muss kein Flag setzen, sondern das Problem löst sich irgendwann von selbst, oder?

[bluecode]

als Reference-Counting bzw. gab es beim Reference-Counting auch irgendein Problem, welches zwar selten auftritt, aber es tritt auf und deswegen will ich das auf keinen Fall nutzen

Abgesehen von einem Overflow (den man wohl getrost ignorieren kann), sehe ich in dem Fall kein Problem. Bei vielen anderen Algorithmen (zB einem Stack der als verkettete Liste implementiert ist) hast du allerdings das Problem, dass eine Lösung mit reference-counting ein Doppelwort-CAS braucht und hazard-pointer nur ein normales CAS.

Ich glaube ich habe da nen Denkfehler bezüglich der Hazard-Pointers, oder? Es wird doch bei jedem "freigeben" eines Pointers überprüft ob schon eine gewisse Anzahl von Pointern in der Liste (per Thread) sind und dann werden die Pointer eventuell freigegeben (wenn kein anderer Thread mehr auf den Pointer zugreift). Sprich man muss kein Flag setzen, sondern das Problem löst sich irgendwann von selbst, oder?

Ja. Wobei man das "wenn kein anderer Thread mehr auf den Pointer zugreift" dadurch implementiert, dass jeder Thread in einem sog. hazard-pointer Record allen anderen mitteilt welche hazard pointer er gerade hält (was natürlich Zeit kostet). Insbesondere kostet dabei Zeit (ich würde sagen, genau die gleiche wie im von mir beschjriebenen Algo mit reference-counting), dass man zuerst einen Snapshot holt, dann den in den hazard-pointer record packt und dann noch überprüfen muss, ob der globale Pointer immernoch gleich dem Snapshot ist, d.h. ich sehe nicht unbedingt warum hazard-pointer im obigen Algo. schneller sein sollten als reference-counting. Im speziellen halte ich es für eine doofe idee, wenn jeder (Userspace)Thread der noch ein Handle auf einen Prozess hat, weil er zB auf einen Statuscode wartet, einen hazard-pointer im Kernelspace dafür reservieren muss. Im speziellen brauchst du dann auf jeden Fall dynamisch vergrößerbare hazard-pointer Records. Laut dem Paper geht das aber das steht da wimre nicht explizit drin wie. Auf jeden Fall ist es dann nichtmehr ganz trivial.

[FlashBurn]

Das Hazard-Pointer nicht ganz trivial sind ist mir klar, aber das trifft auf alle (??) Lock-Free Algos zu.

Ich gucke bei Gelegenheit nochmal nach, aber irgendein Problem war da. Denn ich wollte auch erst solche Atomic-Pointers implementieren, aber hatte da irgendwas gefunden, was zwar selten bis gar nicht auftritt, aber ich wollte keinen Algo nehmen, der nicht 100%ig funktioniert.

Ich glaube das war so, das jeder Pointer, durch nen "Counter" (weil der immer nur um eins erhöht wird) "geschützt" wird und das Problem war, das wenn die Zeit zw. 2 Zugriffen eines Threads zu lange ist, dass dann das Objekt freigegeben werden kann und durch nen anderen Thread wieder alloziert wird und dann der Counter zufällig den selben Wert hat wie der Thread der nun nach längerer Zeit wieder darauf zugreift, aber das Objekt ist jetzt nicht mehr das gleiche.

Wie schaut es mit dem Problem beim Reference-Counting aus? Ich weiß das obiges Problem im Kernel eher unwahrscheinlich bis unmöglich ist, da man meistens auch die Ints aus haben wird, aber ich wollte halt nen Algo nutzen, den ich im Kernel und im UserSpace verwenden kann.

[rizor]

Ich glaube das war so, das jeder Pointer, durch nen "Counter" (weil der immer nur um eins erhöht wird) "geschützt" wird und das Problem war, das wenn die Zeit zw. 2 Zugriffen eines Threads zu lange ist, dass dann das Objekt freigegeben werden kann und durch nen anderen Thread wieder alloziert wird und dann der Counter zufällig den selben Wert hat wie der Thread der nun nach längerer Zeit wieder darauf zugreift, aber das Objekt ist jetzt nicht mehr das gleiche.

Ich bin mir nicht sicher, ob ich dein Szenario richtig verstehe, aber das Problem kannst du doch umgehen, dass du gewaehrleisten kannst, dass die Ueberpruefung der Werte und das Setzen atomar stattfindet. Da muesste man dann unter Umstaenden einen Lock aufbauen, der den Counter schuetzt.

[FlashBurn]

Ich meine folgendes, Thread A holt sich den Pointer und setzt atomar den Counter auf ALT+1 (das ist jetzt kein Reference-Counter) und wenn das erfolgreich war, weiß er das der Counter in Ordnung ist. Das Problem daran ist jetzt, dass das Auslesen und das spätere CMPXCHG nicht zusammenhängend atomar sein können.
Denn Thread B hat sich den Pointer auch geholt und er hat das Objekt freigegeben und irgendwie kommt ein neues Objekt an die gleiche Adresse wie das alte Objekt (was bei nem SlabAllocator mehr als wahrscheinlich ist) und der Counter hat jetzt leider den Wert den Thread A erwartet und was passiert nun? Thread A kommt an die Reihe und macht nen CMPXCHG und da der Counter dummerweise den erwarteten Wert hat, denkt Thread A es bekommt das alte Objekt, dabei ist es ein neues Objekt.

Das war das ABA-Problem, glaube ich.

[rizor]

Ich meine folgendes, Thread A holt sich den Pointer und setzt atomar den Counter auf ALT+1 (das ist jetzt kein Reference-Counter) und wenn das erfolgreich war, weiß er das der Counter in Ordnung ist. Das Problem daran ist jetzt, dass das Auslesen und das spätere CMPXCHG nicht zusammenhängend atomar sein können.
Denn Thread B hat sich den Pointer auch geholt und er hat das Objekt freigegeben und irgendwie kommt ein neues Objekt an die gleiche Adresse wie das alte Objekt (was bei nem SlabAllocator mehr als wahrscheinlich ist) und der Counter hat jetzt leider den Wert den Thread A erwartet und was passiert nun? Thread A kommt an die Reihe und macht nen CMPXCHG und da der Counter dummerweise den erwarteten Wert hat, denkt Thread A es bekommt das alte Objekt, dabei ist es ein neues Objekt.

Das war das ABA-Problem, glaube ich.

Dann habe ich dich richtig verstanden. Das funktioniert dann nur mit einem Lock. Den Algorithmus kannst du halt nicht lockless schreiben.
Man koennte es unter Umstaenden lockless machen, indem man eines der Cache-Protokolle emuliert. Dadurch wuerde aber der Overhead steigen. Da ist ein einfacher Lock vermutlich performanter.

[erik.vikinger]

Hallo,

Das war das ABA-Problem, glaube ich.

Ja, ich glaube auch.
Dem kann man zwar versuchen mit einem Double-Word-CAS (Word meint hier die native Datengröße also 32 oder 64 Bit) entgegen zu wirken indem man den eigentlichen Nutz-Pointer in die CAS-Operation mit einbezieht (was ein passendes Speicherlayout des Struct voraus setzt) aber auch das wirkt nicht zu 100% da ja theoretisch genau das selbe Element vom SLAB-Allocator gleich wieder ausgeliefert werden kann. Das Problem ist die Frage: wie lang kann der zeitliche Abstand zwischen dem Lesezugriff und dem CAS-Zugriff im Maximum werden? Selbst bei einem nichtunterbrechbaren aber SMP-fähigem Kernel kann das ziemlich lang werden. Wenn z.B. auf einer Multi-Core CPU mit Hyperthreading ein Core auf eine andere Taktfrequenz (z.B. per Turbo-Boost) umgeschaltet werden soll dann stehen für kurze Zeit natürlich beide Hyperthreading-Sub-CPUs still (solange die PLL eben braucht um einen neue Frequenz anzulegen) und wenn dann zufälliger Weise auf einer dieser beiden Hyperthreading-Sub-CPUs der A-Thread läuft kann es passieren das ein B-Thread der auf einem ganz anderen Code läuft in der Zeit ne Menge Zeugs (wie eben ein komplettes free und ein komplettes malloc) erledigen kann. Heutige CPUs bieten da eine schier unendliche Fülle an nicht vorhersagbaren Möglichkeiten an die Ausführungsgeschwindigkeit eines winzig kleinen Stückchen Codes extrem zu beeinflussen.

Meines Wissens nach gibt es dagegen nur 2 100%-tig sichere Abhilfen: zum einen ein richtiger atomarer Lock (z.B. per XCHG) oder eine Unterstützung durch die Hardware wie Load-link/store-conditional was aber x86 leider nicht bietet.

Ich habe noch nicht viel Erfahrung mit Lock-Free-Algorithmen aber soweit ich weiß sind viele von denen auf ein einigermaßen vorhersagbares zeitliches Verhalten des Code angewiesen und genau das ist auf modernen Plattformen (auch Abseits von x86) nicht mehr gegeben.


Grüße
Erik

[FlashBurn]

Und genau wegen solcher Probleme ist das mit Multithreading und Locking/Lock-free nicht wirklich trivial und man sollte sich da wirklich gut informieren.

Kennt sich denn noch irgendwer einigermaßen mit Hazard-Pointern aus um mal zu sagen, ob die performancemäßig (und auch ob sie theoretisch 100% sicher sind) besser oder schlechter sind als Reference-Counting.