Thema: SMP und die damit verbundenen Probleme

[FlashBurn]

Ich mache diesmal ein seht weitreichendes Thema auf, da ich genau deswegen gerade Probleme habe, meinen Kernel wieder (vorher ist das Problem einfach nur noch nicht aufgetreten) zum Laufen zu bekommen.

Im speziellen geht es darum, wie man einen sogenannten TLB-Shutdown macht. Also der TLB auf allen CPUs synchronisiert werden muss.

Ich habe das bei mir so gelöst, das man Nachrichten an andere CPUs verschicken kann (per IPI) und man selbst dann wartet bis alle anderen CPUs die Nachricht abgearbeitet haben.

Mein Problem ist nun, das eine CPU die Ints aus hat, weil sie sich in einem kritischen Bereich befindet und versucht einen Lock zu bekommen. Diesen Lock hat nun aber die CPU die gerade eine Nachricht an alle anderen CPUs schickt. Der Deadlock entsteht dadurch das die eine CPU darauf wartet einen Lock zu bekommen und die Ints aus sind und die andere wartet darauf das die gesendete Nachricht bearbeitet wird und auch bei ihr sind die Ints aus.

Wenn ihr jetzt meint "dann mach doch einfach die Ints an", das ist leider nicht so einfach. Dieses spezielle Lock schützt die PagingTables eines Prozesses vor dem gleichzeitigen Zugriff (und außerdem ist es einfacher wenn ich davon ausgehen kann dass das Ändern alles auf ein und der selben CPU passiert) und ich muss auch von genau dieser CPU aus die IPI versenden.

Eine andere (vermeintliche) Lösung wäre einfach das Lock freizugeben, die Ints auszulassen und die andere CPU bekommt den Lock.
Dann habe ich trotzdem nen Deadlock, weil dann beide (immernoch) die Ints aus haben und beide jetzt versuchen ne Msg zu senden.

Einzige Lösung, die mir eingefallen ist, wäre das diese spezielle Funktion nur mit angeschalteten Ints aufgerufen werden darf, aber das ist leider nicht wirklich möglich.

Hat wer schon seinen Kernel so weit und SMP Unterstützung und hat das Problem gelöst?

@erik

Wie willst du solch ein Problem lösen? Denn dein Kernel ist ja grundsätzlich nicht unterbrechbar.

[erik.vikinger]

Hallo FlashBurn,


ich kann nicht wirklich Dein Problem erkennen.

Ich versuche das mal mit eigenen Worten zu wiederholen:
Du hast 2 CPUs (klar es sind noch mehr CPUs im System), CPU A hat einen Lock (zum modifizieren eines Pgaing-Directorys) und möchte nun an alle anderen CPUs einen IPI schicken damit diese ihren TLB löschen (um die Änderungen zu übernehmen), CPU B möchte gerade den selben Lock bekommen (hat ihn aber noch nicht) und hat deswegen ihre INTs abgeschaltet.
Hab ich Dich richtig verstanden?

Wenn ja dann ist die Lösung so einfach wie offensichtlich, wenn man einen Lock in einem unterbrechbaren Kernel haben will dann müssen für den Versuch diesen zu bekommen zwar die INTs aus sein aber falls dieser Versuch nicht klappt müssen die INTs kurz angeschaltet werden.

Code: [Auswählen]

lock_holen:
    cli                   //IRQs abschalten
    mov    al,1           //den Wert für belegt in AL laden
    xchg   [ebx],al       //Versuchen den Lock zu holen (das LOCK-Präfix ist für xchg nicht nötig), ebx ist passend vorbelegt
    cmp    al,0           //war Lock vorher frei?
    je     lock_bekommen  //wenn ja dann habe ich den jetzt
    sti                   //IRQs wieder anschalten
    pause                 //oder irgendwas anderes damit die CPU mal kurz inne hält
    jmp    lock_holen     //auf ein neues
lock_bekommen:ich hoffe Du verstehst was ich meine. Bei dem sti müsste noch eine Abfrage hin ob die INTs auch vorher an waren damit nichts böses passiert.

Wenn ich Dein Problem falsch verstanden habe dann erkläre es bitte noch mal etwas deutlicher (und benutze A und B für die CPUs damit man nicht durcheinander kommt).


Auf meiner Plattform trifft dieses TLB-Problem grundsätzlich nicht auf, bei mir soll es möglich sein das eine CPU über ein spezielles Controll-Register (sowas wie die MSR bei x86) einen globalen TLB-Flush für eine bestimmte Page auslösen kann. Die CPUs führen das in HW aus ohne die gerade laufende SW zu unterbrechen, einzig die Suche im TLB nach der zu löschenden Page hindert die laufende SW kurz daran einen gepageten Speicherzugriff durchzuführen (die CPU-Pipeline würde blockieren), wenn die Segmente der laufenden SW ohne Paging auskommen (was wohl die Regel ist) dann merkt die SW gar nichts davon. Die CPU welche das initiiert hat blockiert natürlich bis alle anderen ein Okay zurückmelden, was durchaus einige 100 bis 1000 Takte dauern kann, aber etliche IPIs loszutreten dauert sicher länger (vor allem trotz dessen das die meisten CPUs die betreffende Page gar nicht im TLB haben). Im Gegenzug gibt es auf meiner Plattform keine IPIs und damit auch keine Möglichkeit eine bestimmte CPU zu einer Reaktion zu bewegen. Trotzdem denke ich das mein System gerade wegen solcher Kleinigkeiten deutlich besser skalieren wird.


Grüße
Erik

[FlashBurn]

Wenn ich Dein Problem falsch verstanden habe dann erkläre es bitte noch mal etwas deutlicher (und benutze A und B für die CPUs damit man nicht durcheinander kommt).

Ich würde nicht sagen das du es falsch verstanden hast, sondern nicht komplett.

Dein Vorschlag hatte ich schon vor Ewigkeiten (wegen solcher Probleme) umgesetzt.

Man hat ne vmmMap()-Funktion und um sich die Arbeit zu erleichtern darf immer nur einer gleichzeitig in den PageTables eines Prozesses (und der KernelSpace ist für ich in dem Fall ein extra Prozess) rumwerkeln. Also sichere ich den Code durch einen Lock und wenn man das Lock hat dann sind die Ints aus. Soweit kein Problem. Mein Problem ist nun das ich eigentlich sagen muss, dass diese vmmMap() nur mit eingeschalteten Ints aufgerufen werden darf, aber genau das bekomme ich ohne viele neue Probleme an anderen Stellen nicht hin.

Dadurch kann es jetzt halt passieren, das jemand auf CPU A im KernelSpace was gemappt hat und nen TLB-Shutdown macht, aber auf CPU B ist jemand in einem kritischen Bereich und hat seine Ints aus und ruft jetzt dummerweise vmmMap() auf und will eine Page im KernelSpace mappen. Den Lock kann er natürlich nicht bekommen, weil CPU A den hat und ihn erst freigibt, wenn der TLB-Shutdown abgeschlossen. Dies wiederrum kann nicht geschehen, weil CPU B die Ints nicht an hat und so nie die IPI-Nachricht bearbeitet.

Um es einfacher zu machen, was wird wohl einfacher sein, mir alle Funktionen angucken die die Ints aus haben und vmmMap() angucken oder versuchen vmmMap() und den TLB-Shutdown anders zu gestalten?

Meine Vermutung ist, das ich mir alle Funktionen angucken muss die die vmmMap mit ausgeschalteten Ints aufrufen und zusehen muss das ich das nicht mehr mache.

Ich werde nachher mal eins der Probleme posten, die anderen sehen ähnlich aus.

[erik.vikinger]

Hallo,


wenn Dein Problem so ist dann empfehle ich Dir das man bei verschachtelten Locks immer in der selben Reihenfolge locken muss. Klingt vielleicht doof und lässt sich wohl nicht so ganz mit Deiner Zielvorstellung in Einklang bringen aber schlussendlich wirst du da kaum drumherum kommen.

Wenn die CPU A mit ihren Modifikationen am Page-Directory fertig ist und anschließend alle anderen CPUs nur noch darüber informieren möchte, ist da der Lock wirklich noch erforderlich? Wäre es nicht möglich den Lock freizugeben nachdem alle Änderungen erledigt sind aber bevor die anderen CPUs informiert werden? Ich weiß ja nicht genau wie Deine Speicherverwaltung arbeitet aber ich sehe da eigentlich kein Erfordernis den Lock zu behalten.


Grüße
Erik

[FlashBurn]

wenn Dein Problem so ist dann empfehle ich Dir das man bei verschachtelten Locks immer  in der selben Reihenfolge locken muss. Klingt vielleicht doof und lässt sich wohl nicht so ganz mit Deiner Zielvorstellung in Einklang bringen aber schlussendlich wirst du da kaum drumherum kommen.

Das ist klar und wird auch so gemacht, aber (um bei meinem Bsp. zu bleiben) die vmmMap() wird ja nicht nur von einer anderen Funktion aus aufgerufen und d.h. dann auch das da noch andere Locks mit im Spiel sind.

Wenn die CPU A mit ihren Modifikationen am Page-Directory fertig ist und anschließend alle anderen CPUs nur noch darüber informieren möchte, ist da der Lock wirklich noch erforderlich? Wäre es nicht möglich den Lock freizugeben nachdem alle Änderungen erledigt sind aber bevor die anderen CPUs informiert werden? Ich weiß ja nicht genau wie Deine Speicherverwaltung arbeitet aber ich sehe da eigentlich kein Erfordernis den Lock zu behalten.

Praktisch ist der Lock erforderlich.

Stell dir einfach vor du möchtest mehr als eine Page mit einem Aufruf von vmmMap() mappen und jetzt stell dir mal vor die Funktion wird nach jeder Page unterbrochen und läuft dann jedesmal auf ner anderen CPU. Unschön, aber noch zu handeln. Denn jetzt könntest du sagen, ok machen wir einfach so, beim TLB-Shutdown wird einfach jede CPU (auch die die die IPI versendet) angeschrieben und invalidet den TLB. Die Variante ist aus Performance sicht natürlich absolute scheiße (zumal ich bei meiner Variante noch ein wenig optimieren kann).

Das Problem ist, halt, dass das Versenden der IPI Nachricht auf der selben CPU (A) stattfinden muss, weil es sonst passiert das dieser Teil auf ner anderen CPU B stattfindet und die ihren TLB also nicht aktualisiert, aber die andere CPU A invalidet ihren TLB nochmal.

Lange Rede kurzer Sinn, ich behalte den Lock, damit ich davon ausgehen kann dass das Senden der IPI Nachricht auf der selben CPU stattfindet wie das mappen. Den Lock zu behalten hat den Sinn, die Ints auszulassen.

[erik.vikinger]

Hallo,


ich würde sagen Du sollst nicht jede Page einzeln mappen und immer sofort alle TLBs invalidieren sondern erst alle Pages mappen und erst am Schluss alle TLBs invalidieren. Zu häufiges TLB invalidieren kosten nur unnötig Performance (das solltest Du nicht unterschätzen). Das einzigste was Du sicherstellen musst ist das bevor die Pages das erste mal benutzt werden es keine Altlasten in den TLBs gibt. Von welcher CPU das Invalidieren der TLBs dann ausgeht ist doch völlig egal solange Du keine CPU vergisst.


Grüße
Erik

[FlashBurn]

ich würde sagen Du sollst nicht jede Page einzeln mappen und immer sofort alle TLBs invalidieren sondern erst alle Pages mappen und erst am Schluss alle TLBs invalidieren. Zu häufiges TLB invalidieren kosten nur unnötig Performance (das solltest Du nicht unterschätzen). Das einzigste was Du sicherstellen musst ist das bevor die Pages das erste mal benutzt werden es keine Altlasten in den TLBs gibt. Von welcher CPU das Invalidieren der TLBs dann ausgeht ist doch völlig egal solange Du keine CPU vergisst.

So schlimm ist es bei mir auch nicht.

Also:

Code: [Auswählen]

vmmMap(void *virt, void *phys, uint32t count, struct addrSpace_t *addrSpace) {
spinAcquire(&addrSpace->lock);

for(uint32t x= 0; x < count; x++, virt+= PG_SIZE, phys+= PG_SIZE) {
 //hier packt er jetzt die phys in die PageTables
 invalidTLB(virt);
}

smpSendBroadcastMsg(SMP_CODE_INVALIDPG,virt,count,getPD());

spinRelease(&addrSpace->lock);
}
Das wäre mal ne sehr stark vereinfachte Variante der vmmMap().

Dein Vorschlag heißt also das ich das invalidieren nicht in der Schleife mache, sondern das ich ne Nachricht sende und die geht an alle einschließlich der CPU die die Nachricht gesendet hat.
Wäre ne Möglichkeit. Schwierigkeit sehe ich halt dann darin, das ich auch das Senden der Nachricht in einen Lock packe und da ja wieder keine Ints an sind und somit die sendende CPU wieder die Nachricht nicht bekommen würde.
Ich muss das Senden mit nem Lock schützen, da ich immer nur eine Nachricht zur selben Zeit senden und bearbeiten lassen kann.

Edit::

Was mir noch einfällt. Deine Lösung das ich den Lock freigeben und erst später an alle CPUs die Nachricht sende, kann auch deswegen nicht funktionieren, weil es wieder einen Deadlock (obwohl ich inzwischen glaube, dass das das falsche Wort dafür ist) gibt.
Denn Problem an deinem Vorschlag und meinem momentanen Code ist, dass beide davon ausgehen (müssen) das die Ints vorher an waren und genau das ist das Problem.

Edit::

Auf meiner Plattform trifft dieses TLB-Problem grundsätzlich nicht auf, bei mir soll es möglich sein das eine CPU über ein spezielles Controll-Register (sowas wie die MSR bei x86) einen globalen TLB-Flush für eine bestimmte Page auslösen kann.

Wenn ich dich hier richtig verstehe dann willst du nen TLB-Flush mit der physikalischen und nicht der virtuellen Adresse machen?
Das würde so bei mir gar nicht funktionieren, weil es durchaus sein kann, das ein und die selbe physikalische Page an mehreren virtuellen Adressen gemappt ist.

[erik.vikinger]

Hallo,

aber (...) die vmmMap() wird ja nicht nur von einer anderen Funktion aus aufgerufen und d.h. dann auch das da noch andere Locks mit im Spiel sind.

Das korrekte Locken muss man immer über die gesamte SW und alle Ausführungspfade betrachten.

Dein Vorschlag heißt also das ich das invalidieren nicht in der Schleife mache, sondern das ich ne Nachricht sende und die geht an alle einschließlich der CPU die die Nachricht gesendet hat.

Ja, Du sollst erst das PD fertig bearbeiten und danach alle TLBs löschen. Somit kannst Du zum TLB-Löschen den Lock, fürs PD, freigeben.

Schwierigkeit sehe ich halt dann darin, das ich auch das Senden der Nachricht in einen Lock packe und da ja wieder keine Ints an sind und somit die sendende CPU wieder die Nachricht nicht bekommen würde.

In der eigentlichen IPI-Sende-Funktion, welche für jede Ziel-CPU einzeln aufgerufen wird und internen einen Lock benutzt, muss natürlich die aktuelle CPU als Ziel ausgefiltert werden (die gewünschte Aktion muss dann direkt ausgeführt werden).

Denn Problem an deinem Vorschlag und meinem momentanen Code ist, dass beide davon ausgehen (müssen) das die Ints vorher an waren und genau das ist das Problem.

Also ich sehe nicht wo mein Vorschlag bedingt das die INTs vorher an sind.

Wenn ich dich hier richtig verstehe dann willst du nen TLB-Flush mit der physikalischen und nicht der virtuellen Adresse machen?

Da hast Du mich missverstanden, ich will das TLB-Löschen auch mit linearen Adressen machen. Ich hab zwar nur ein einziges Page-Directory im gesamten System aber auch dort können physische Pages an mehreren Stellen im linearen Adressraum gemappt sein.


Grüße
Erik

[FlashBurn]

In der eigentlichen IPI-Sende-Funktion, welche für jede Ziel-CPU einzeln aufgerufen wird und internen einen Lock benutzt, muss natürlich die aktuelle CPU als Ziel ausgefiltert werden (die gewünschte Aktion muss dann direkt ausgeführt werden).

Sorry, wenn ich das mal so sage, aber das ist sehr unvorteilhaft

Wie lange soll das dauern, wenn du die Sende-Funktion für jede CPU einzeln aufrufst (max. 255 mal)? Dann kommt noch hinzu das der Vorteil, der gleichzeitigen Bearbeitung auch flöten geht.
Viel einfacher ist es, wenn ich eine Nachricht schicke und die geht entweder an alle oder an alle außer der sendenden.

Das die aktuelle CPU den Code direkt ausführen soll, ist auch eher unvorteilhaft (zwecks extra Behandlung).

Also ich sehe nicht wo mein Vorschlag bedingt das die INTs vorher an sind.

Das Senden ist durch einen Lock geschützt und als sendende CPU (A) wartest du (und behälst damit den Lock) bis alle CPUs die Nachricht bearbeitet haben und genau das ist der springende Punkt. Jemand kommt mit Ints aus bei der IPI-Sende-Funktion an und möchte den Lock (CPU B).
Den wird er nur nie bekommen, denn es hat gerade eine CPU (A) den Lock und die wartet auf genau die CPU (B) die gerade versucht den Lock zu bekommen und mit Ints aus da rein ist. Da sie (CPU B) schon die Ints aus hatte als sie rein kam, wird sie die Nachricht nicht (bzw. sogar nie) bekommen.

Eine andere Idee die ich noch hatte, ist es das man mehrere Msgs senden kann. Das sollte dann so aussehen, das die Msgs in einer Queue sind und jede CPU die Msgs der Queue durchgeht und guckt ob sie sie bearbeiten muss. Hat die CPU die Msg bearbeitet setzt es das Bit in einer Bitmap und erhöht nen Counter, ist der Counter gleich der Anzahl der CPUs wird die Nachricht "gelöscht".
So kann ich einfach mehrere Msgs senden und muss auch nicht mehr darauf warten das eine Nachricht bearbeitet wurde.

Alles gut und schön, aber da habe ich dann immernoch eine "Bedingung", nämlich das wenn man vmmMap() aufgerufen hat, man die Page(s) die man gemappt hat erst benutzen darf, wenn man die Ints an hatte. Denn ansonsten nutzt du die Page und hast den TLB noch gar nicht aktualisiert (was ich natürlich mache in meinen Problemfunktionen ).

Allerdings sollte das Problem des nicht aktualisierten TLBs eigentlich gar keins sein. Denn was kann schon passieren? Wurde die Page neu gemappt, ist (eigentlich) eh kein Eintrag vorhanden und es muss in die PageTables geschaut werden.
Blöd wird es erst wenn da vorher ne andere Page stand und ein vmmUnmap() mit einem vmmMap() (auf einer anderen CPU) mit der selben virtuellen Adresse kollidiert (was eigentlich nicht passieren darf).

Jetzt weißt du hoffentlich warum man einen unterbrechbaren Kernel haben sollte!?

[erik.vikinger]

Hallo,

Sorry, wenn ich das mal so sage, aber das ist sehr unvorteilhaft

Tja, ich hab eben keine Ahnung davon wie die IPIs auf x86 realisiert sind, ich weiß nur das ich auf meiner Plattform keine IPIs brauche (wozu auch?) und demzufolge auch keine habe.

Viel einfacher ist es, wenn ich eine Nachricht schicke und die geht entweder an alle oder an alle außer der sendenden.

Dann eben "an alle außer der sendenden". Wo ist das Problem?

Das die aktuelle CPU den Code direkt ausführen soll, ist auch eher unvorteilhaft (zwecks extra Behandlung).

Warum, einen TLB-Flush wirst Du doch überall mal kurz ausführen können.

Das Senden ist durch einen Lock geschützt .....

Das klingt irgendwie kompliziert. Kann man an diese Sache nicht anders ran gehen?

.... und muss auch nicht mehr darauf warten das eine Nachricht bearbeitet wurde.

Nach einem vmmUnmap() solltest Du aber schon warten bis wirklich alle CPUs ihren TLB gelöscht haben.

Allerdings sollte das Problem des nicht aktualisierten TLBs eigentlich gar keins sein. Denn was kann schon passieren? Wurde die Page neu gemappt, ist (eigentlich) eh kein Eintrag vorhanden und es muss in die PageTables geschaut werden.

Ich weiß zwar nicht wie Intel und AMD das implementieren aber es wäre schon ziemlicher Unsinn wenn ungültige PD-Einträge in den TLB kommen könnten. Ich denke Deine Annahme ist richtig.

Blöd wird es erst wenn da vorher ne andere Page stand und ein vmmUnmap() mit einem vmmMap() (auf einer anderen CPU) mit der selben virtuellen Adresse kollidiert (was eigentlich nicht passieren darf).

Nach einem vmmUnmapp() muss man tatsächlich warten bis alle CPUs ihren TLB aktualisiert haben aber dort gibt es ja auch keine neuen Pages die man gleich benutzen will und es sollte auch kein Problem sein nach einem vmmUnmap() mal die INTs an zuschalten.

Jetzt weißt du hoffentlich warum man einen unterbrechbaren Kernel haben sollte!?

Ich weiß jetzt nur noch deutlicher warum ich keinen unterbrechbaren Kernel will! Das ist ja ein unheimlicher Zusatzaufwand der da getrieben werden muss! Vor allem kann ich für einen Micro-Kernel keinen Vorteil dadurch erkennen.


Grüße
Erik

[FlashBurn]

Ich weiß jetzt nur noch deutlicher warum ich keinen unterbrechbaren Kernel will! Das ist ja ein unheimlicher Zusatzaufwand der da getrieben werden muss! Vor allem kann ich für einen Micro-Kernel keinen Vorteil dadurch erkennen.

Du kommst einfach auf x86 um einen unterbrechbaren Kernel nicht herum!

Warum, einen TLB-Flush wirst Du doch überall mal kurz ausführen können.

Mir geht es in dem Fall eigentlich darum, das ich keinen doppelten Code habe, weil ich müsste die Nachrichten Behandlung ja einmal im Handler haben und einmal im Sende-Code was natürlich quatsch ist.

Das klingt irgendwie kompliziert. Kann man an diese Sache nicht anders ran gehen?

Bin ich gerade dabei Wenn ich fertig bin und es funktioniert so wie ich es mir vorstelle, dann muss man nur noch einen Lock haben, damit man eine neue Nachricht in die Liste packen kann. Man muss dann auch nicht mehr warten bis alle anderen CPUs die Nachricht bearbeitet haben.
Allerdings muss der Sendevorgang an sich (das Schreiben, genauer 2 32bit Werte, in ein 64bit APIC Register) durch deaktivierte Ints geschützt werden.

Nach einem vmmUnmap() solltest Du aber schon warten bis wirklich alle CPUs ihren TLB gelöscht haben.

Nö

Ich gehe immernoch davon aus, das auf der aktuellen CPU die TLBs in Ordnung sind und wenn ich die Nachricht gesendet habe, kann mir alles andere egal sein.

Was ich machen könnte, ist am Ende von vmmMap() und vmmUnmap() nachzusehen ob nicht irgendwelche IPI Nachrichten da sind und diese dann bearbeiten oder noch besser bevor ich eine neue Nachricht sende, wird nachgeguckt ob ich nicht erstmal alte bearbeiten sollte.
Ich denke ich werde letzteres umsetzen.

Nach einem vmmUnmapp() muss man tatsächlich warten bis alle CPUs ihren TLB aktualisiert haben aber dort gibt es ja auch keine neuen Pages die man gleich benutzen will und es sollte auch kein Problem sein nach einem vmmUnmap() mal die INTs an zuschalten.

Nein und nein

Also das Problem was ich meine ist, das CPU A nen Unmap macht (und die Ints aus sind) und auf CPU B macht jemand danach nen Map (mit Ints aus und der gleichen virtuellen Adresse).
Jetzt steht in den PageTables schon ein korrekter neuer Wert drin, aber da nicht alle CPUs aktuelle TLBs hat, kann es passieren das einer auf ne alte Page zugreift.

Die Ints kann ich deswegen nicht mal eben wieder anmachen, weil es bei mir Code gibt, der auf der selben CPU beendet werden muss, auf der er auch begonnen wurde und dann kann man nicht mal eben die Ints anmachen.

[FlashBurn]

Ich gehe immernoch davon aus, das auf der aktuellen CPU die TLBs in Ordnung sind und wenn ich die Nachricht gesendet habe, kann mir alles andere egal sein.

Ich kann sagen, dass das so nicht stimmt

Mein Kernel läuft wieder auf mehreren CPUs, mehr oder weniger

Also wer sein OS möglichst erstmal "nur" zum Laufen bringen will, sollte von SMP (d.h. nicht das man kein Multithreading machen soll) erstmal Abstand halten!

Es ist einfach eine Qual Code zu debuggen der auf mehreren CPUs gleichzeitig läuft. Ich bin mir nicht sicher ob ich noch irgendwo ein Locking Problem habe (obwohl da wo es zu sein scheint, kann es eigentlich nicht sein) oder ob ich ein Problem mit fehlerhaften bzw. nicht aktuellen TLBs habe.

Die Symptome sind, dass mein Kernel die meiste Zeit, wenn ich ihn in Bochs oder Qemu teste, läuft, aber ab und zu kommt entweder ein Locking Problem oder ein Fehler der nach fehlerhaften bzw. nicht aktuellen TLB aussieht.

Edit::

Ich denke ich kann inzwischen die Probleme mit dem TLB-Shutdown und nicht aktuellen TLBs einschränken.

Mit meiner neuen Variante IPI-Nachrichten zu versenden und zu bearbeiten offenbart sich leider immer mehr ein Problem mit dem Locking.

Um es mal an einem Bsp. zu zeigen. Ich habe ja ne relativ aktuelle Variante des SlabAllocators implementiert und bei dieser ist es so das man sogenannte Magazine (kleine Stacks, die bei mir 4 Objekte beinhalten) pro CPU benutzt. Hat den Vorteil das, solange mind. 1 Objekt in dem Magazin ist, dass allokieren verdammt schnell geht.
Leider hat es den Nachteil, das man während man guckt ob noch Objekte im Magazine sind die Ints ausmachen muss, da das ja alles auf der selben CPU laufen muss. So weit ist da auch noch kein Problem.
Problematisch wird es wenn das Magazin aufgefüllt werden muss. Dazu wird der "alte", "einfache" SlabAllocator aufgerufen. Auch das muss wieder auf der gleichen CPU passieren, weil ansonsten könnte es passieren das man versucht das Magazin einer anderen CPU aufzufüllen, das gar nicht leer ist bzw. sogar voll ist.
Das ist auch immernoch kein Problem. Erst wenn der VMM aufgerufen wird, weil der SlabAllocator ne neue Page braucht tritt ein Problem auf. Solange das alles auf der CPU passiert die ihr Magazin neu befüllen muss funktioniert das auch. Wenn jetzt aber eine andere CPU auch ihr Magazin auffüllen will und dann auf die neue Page zugreift kann das schief gehen.
Denn die Ints sind ja aus, da alles auf der gleichen CPU laufen muss, und damit wird auch nicht der TLB aktualisiert und es wird ein alter Eintrag genutzt.

Ich hoffe ihr konntet das Problem nachvollziehen.

Ich suche jetzt nach einer vernünftigen Lösung dafür, aber bisher ist mir nichts eingefallen. Die einzige Idee die mir kam, war den IPI-Service-Int weg von einem normalen Int hin zu einem NMI zu machen. Damit wird jede CPU immer unterbrochen auch wenn sie eigentlich die Ints aus hat und da ich nur Code ausführe der TLBs aktualisiert sollte das auch kein Problem darstellen.
Was meint ihr?

[erik.vikinger]

Hallo,

Du kommst einfach auf x86 um einen unterbrechbaren Kernel nicht herum!

Das glaube ich nicht! Das einzigste was ein Problem bei SMP ist ist das löschen der anderen TLBs aber dafür möchtest Du ja NMI benutzen (was IMHO wohl der richtige Weg ist). Für alles andere benötigt man keinen unterbrechbaren Kernel, zumindest solange man bei einem Micro-Kernel bleibt der nur die elementaren Basics wie Speicher, CPU-Zeit und IPC anbietet.

Warum, einen TLB-Flush wirst Du doch überall mal kurz ausführen können.

Mir geht es in dem Fall eigentlich darum, das ich keinen doppelten Code habe

Das TLB löschen ist ein kleines Assembler-Macro:

Code: [Auswählen]

#define TLB_FLUSH  asm("mov eax,cr3; \n mov cr3,eax;" : : "eax","memory");und ein TLB_FLUSH an 2 Stellen zu tippen ist jetzt nicht so der Aufwand außerdem macht es Deinen Kernel portabel wenn dieses define in einer plattformspezifischen H-Datei drin ist.

Ich gehe immernoch davon aus, das auf der aktuellen CPU die TLBs in Ordnung sind

Das diese Annahme falsch ist weißt Du ja nun selber. Zumindest bei einem vmmUnmap() musst Du die vorher gültigen PT-Einträge aus dem TLB entfernen. Andersrum ist das nicht so kritisch.

Du darfst aber die Pages, die vmmUnmap() frei gibt, erst dann wieder in den Pool mit den freien Pages legen wenn das TLB-löschen auf allen CPUs fertig ist! Damit diese Pages nicht während dessen schon wieder für etwas neues benutzt werden, dann ist es auch egal auf welcher CPU das alles passiert.

Also wer sein OS möglichst erstmal "nur" zum Laufen bringen will, sollte von SMP (d.h. nicht das man kein Multithreading machen soll) erstmal Abstand halten!

Diesen Rat werde ich bei meiner Plattform nicht befolgen, bei mir ist SMP ein essentieller Bestandteil.
Aber ich hab ja auch nicht so erquickende Dinge wie IPIs.

Es ist einfach eine Qual Code zu debuggen der auf mehreren CPUs gleichzeitig läuft. Ich bin mir nicht sicher ob ich noch irgendwo ein Locking Problem habe (obwohl da wo es zu sein scheint, kann es eigentlich nicht sein) oder ob ich ein Problem mit fehlerhaften bzw. nicht aktuellen TLBs habe.

Du bist es offensichtlich nicht gewöhnt in parallelen Bahnen zu denken, ich kann Dir da nur empfehlen erst mal mit Multithreading-User-Space-Programmen zu üben. Als ich das erste mal für ein Multi-CPU-PC programmiert habe (damals ein 4 x Pentium-Pro) war das für mich auch eine Art Kulturschock, man wird mit so vielen neuartigen Problemen konfrontiert.

.....
Ich hoffe ihr konntet das Problem nachvollziehen.

Nicht so ganz, Du musst Dir mehr Mühe geben keine Henne-Ei-Probleme in Deinem Design zu haben.

Ich suche jetzt nach einer vernünftigen Lösung dafür, aber bisher ist mir nichts eingefallen. Die einzige Idee die mir kam, war den IPI-Service-Int weg von einem normalen Int hin zu einem NMI zu machen. Damit wird jede CPU immer unterbrochen auch wenn sie eigentlich die Ints aus hat und da ich nur Code ausführe der TLBs aktualisiert sollte das auch kein Problem darstellen.
Was meint ihr?

Ich denke solange der TLB-Flush das einzigste ist was Du per IPI machst kannst Du die ruhig als NMI realisieren. Ist bei meiner Plattform ja in gewisser Weise auch so nur das ich das komplett in HW machen möchte um eben in der SW trotzdem ohne eine Unterbrechung aus zukommen.

Hast Du denn vor die IPIs noch für etwas anderes zu benutzen?  Mir fällt da ehrlich gesagt nichts ein.


Grüße
Erik

[Svenska]

Du kommst einfach auf x86 um einen unterbrechbaren Kernel nicht herum!

Also die BSDs haben in ihrer ersten SMP-Implementierung einfach ein GIANT_LOCK genutzt. Manche alten Treiber nutzen diesen Ansatz immernoch, steht dann im Bootlog. Alternativ pinnst du den Kernel auf eine CPU fest und lässt auf den anderen CPUs nur Userspace laufen. Möglichkeiten gibt es, ob sie gut (oder hinreichend gut) sind, ...

[FlashBurn]

Das TLB löschen ist ein kleines Assembler-Macro:

Das ist seit dem 486 nicht mehr so bzw. geht viel performanter nämlich mit "invlpg". Mir deiner Variante würde ich ja jedes Mal den ganzen TLB löschen und das ist nicht Sinn der Sache.
Zumal du damit ab PPro richtig Probleme bekommen kannst, denn deine Variante löscht nicht die Einträge die global markiert sind, die musst du alle explizit mit "invlpg" löschen (wimre).

Das diese Annahme falsch ist weißt Du ja nun selber. Zumindest bei einem vmmUnmap() musst Du die vorher gültigen PT-Einträge aus dem TLB entfernen. Andersrum ist das nicht so kritisch.

Wie gesagt, das Löschen im TLB mache ich immer gleich in der vmmMap() und der vmmUnmap() und dann wird einfach nur noch eine IPI-Nachricht verschickt dass das die anderen CPUs (eventuell) auch machen müssen.
Damit ist der TLB auf der aktuellen CPU immer gültig.

Du bist es offensichtlich nicht gewöhnt in parallelen Bahnen zu denken, ich kann Dir da nur empfehlen erst mal mit Multithreading-User-Space-Programmen zu üben. Als ich das erste mal für ein Multi-CPU-PC programmiert habe (damals ein 4 x Pentium-Pro) war das für mich auch eine Art Kulturschock, man wird mit so vielen neuartigen Problemen konfrontiert.

Ich habe von Anfang an so programmiert und meinen Kernel immer für SMP/Multithreading ausgelegt und so programmiert.
Es ist halt ne Tatsache das ein Bug, der nur sporadisch und nach keinem Muster auftritt eher verdammt schwer bis gar nicht zu finden ist.
Gerade bei SMP kann das heißen das dein Kernel mal läuft und mal gibt es nen Deadlock ohne das du weißt warum.

Die ganze Bug Suchgeschichte hatte aber auch seine Vorteile, bei der Suche habe ich mir teile des Codes in Assembler angesehen und da ist mir erstmal aufgefallen wie fehleranfällig mein Lockcode war  Ein Wunder das da bisher nichts passiert ist.

Nicht so ganz, Du musst Dir mehr Mühe geben keine Henne-Ei-Probleme in Deinem Design zu haben.

Das lässt sich aber eigentlich gerade bei einem OS nie vermeiden, irgendjemand muss halt mal irgendwann initialisieren und da gibt es immer so ein Problem. Bei mir treten die halt auch nach der Initialisierung auf

Nächste Sache ist halt, ich könnte wieder den alten SlabAllocator verwenden, der hat nicht die Probleme, aber der ist nicht mal annähernd so schnell und skaliert auch nicht so schön.

Zumal du damit ja indirekt implizierst das man lieber keine komplizierten Sachen/Konzepte nutzen sollte, damit fällt dann auch Multithreading auf mehreren Cores weg. Denn damit holt man sich nen Haufen Probleme und die Komplexität steigt auch nicht ganz unwesentlich.

Hast Du denn vor die IPIs noch für etwas anderes zu benutzen?  Mir fällt da ehrlich gesagt nichts ein.

Ja. Wird für Rendevouz-Funktionen genutzt (z.B. TSCs synchronisieren) und dafür alle außer der sendenden CPUs anzuhalten.

Beide Fälle sollten aber kein Problem darstellen. Jetzt muss ich nur noch rausbekommen wie das mit dem NMI funktioniert und dann habe ich durch meinen ersten Versuch das Problem zu lösen meinen IPI-Code für die sendende CPU sogar wesentlich performanter gemacht.

Alternativ pinnst du den Kernel auf eine CPU fest und lässt auf den anderen CPUs nur Userspace laufen.

Ersteres habe ich bei mir nicht implementiert und finde ich auch nicht nötig und zweiteres ist, aus meiner Sicht unmöglich.
Denn was willst du machen, wenn schon 2 CPUs im KernelSpace laufen und den Kernel sozusagen sperren willst. Wenn du daran denkst das immer nur eine CPU in den Kernel darf, dann ist das wieder ne GIANT_LOCK und sowas sollte man heutzutage nicht mal mehr in Betracht ziehen. Das ist nur unnötige Ressourcen Verschwendung weil man zu faul war sich nen Kopf zu machen

[Svenska]

Alternativ pinnst du den Kernel auf eine CPU fest und lässt auf den anderen CPUs nur Userspace laufen.

Ersteres habe ich bei mir nicht implementiert und finde ich auch nicht nötig und zweiteres ist, aus meiner Sicht unmöglich.
Denn was willst du machen, wenn schon 2 CPUs im KernelSpace laufen und den Kernel sozusagen sperren willst. Wenn du daran denkst das immer nur eine CPU in den Kernel darf, dann ist das wieder ne GIANT_LOCK und sowas sollte man heutzutage nicht mal mehr in Betracht ziehen. Das ist nur unnötige Ressourcen Verschwendung weil man zu faul war sich nen Kopf zu machen

Das das ungeeignet ist, war mir schon klar. Aber du kannst durchaus hingehen und sagen "CPU0 darf Kernel und Userspace ausführen" und "alle anderen CPUs dürfen den Kernel nicht aufrufen". Bei deinem Mikrokernelsystem ist sicher nicht so schädlich wie bei einem Monolithen.

Der GIANT_LOCK-Ansatz wurde bei den BSDs sofort als SMP-Möglichkeit eingeführt, da kannten andere OSse keine Mehrprozessorsysteme, und seitdem wird der Kernel in immer feinere, einzeln gelockte Abschnitte unterteilt, die ihrerseits unterbrechbar sind. Für Neuschreiben (wie bei dir) ist diese Vorangehensweise sicherlich die denkbar schlechteste Lösung.

Darum ging es aber garnicht - dies sind nur Möglichkeiten, ohne unterbrechbaren Kernel auf x86 auszukommen.

Gruß

[FlashBurn]

Bei deinem Mikrokernelsystem ist sicher nicht so schädlich wie bei einem Monolithen.

Ich würde sagen, das nimmt sich nicht so viel. Bei nem Mikrokernel wirst du viele Kernelaufrufe zwecks IPC haben, aber dafür sollte die Zeit im Kernel wirklich nicht lange dauern.

Für Neuschreiben (wie bei dir) ist diese Vorangehensweise sicherlich die denkbar schlechteste Lösung.

Du weißt doch, es gibt immer jemanden der es trotzdem macht

[erik.vikinger]

Hallo,

Das ist seit dem 486 nicht mehr so bzw. geht viel performanter nämlich mit "invlpg".

Okay, dann machst Du aus TLB-Flush eben eine (etwas komplexere) Funktion die an mehreren Stellen aufgerufen wird.

Wie gesagt, das Löschen im TLB mache ich immer gleich in der vmmMap() und der vmmUnmap() und dann wird einfach nur noch eine IPI-Nachricht verschickt dass das die anderen CPUs (eventuell) auch machen müssen.
Damit ist der TLB auf der aktuellen CPU immer gültig.

Das Problem das Du Pages bereits im Frei-Pool hast die aber eventuell noch in TLBs einiger/anderer CPUs drin sind muss aber gelöst werden indem Du alle TLBs löscht bevor die Pages in den Frei-Pool kommen. Das senden der IPIs und warten auf alle Antworten muss also in der Mitte von vmmUnmap() passieren und nicht erst hinterher.

Ich habe von Anfang an so programmiert und meinen Kernel immer für SMP/Multithreading ausgelegt und so programmiert.

Sicher? Warum hast Du dann jetzt so viele Probleme damit?

  "Der Mensch denkt oft richtig aber nur selten vollständig."

Ich bestreite nicht das Du Dir Mühe gibst aber aus Deinen vergangenen Problembeschreibungen habe ich den subjektiven Eindruck gewonnen das Dir da etwas an Erfahrung fehlt und Du deswegen verschiedene Probleme nicht so deutlich/frühzeitig erkennst. Beim Programmieren von Algorithmen, in dehnen viele Dinge parallel und in unvorhersehbarer Reihenfolge ausgeführt werden, gibt es eben eine Reihe von Problem-Klassen für die man erst etwas Übung braucht um damit ganz selbstverständlich umgehen zu können.

Es ist halt ne Tatsache das ein Bug, der nur sporadisch und nach keinem Muster auftritt eher verdammt schwer bis gar nicht zu finden ist.

Das hat aber nichts mit SMP zu tun. Du solltest mal ganz klar definieren was ein Bug ist und dann Code schreiben der zur Laufzeit (in der Debug-Version) nach genau dieser Bedingung prüft. Mit diesem Weg kommst Du zu recht präzisen Debug-Meldungen, zumindest bin ich bis her damit recht gut gefahren.

Gerade bei SMP kann das heißen das dein Kernel mal läuft und mal gibt es nen Deadlock ohne das du weißt warum.

Jedes mal wenn Du einen Deadlock hast musst Du die Ursache heraus finden und dann wird Dein Code mit jedem beobachteten Deadlock besser.

Das lässt sich aber eigentlich gerade bei einem OS nie vermeiden

Was ist an einem OS so anders als an anderen Programmen das bei OSen eben Henne-Ei-Probleme nicht vermieden werden können? Klar gibt es ein paar zusätzliche Schwierigkeiten aber die sind IMHO nicht unlösbar.

Bei mir treten die halt auch nach der Initialisierung auf

Also doch Design-Probleme?!

Zumal du damit ja indirekt implizierst das man lieber keine komplizierten Sachen/Konzepte nutzen sollte

Das meine ich auch direkt explizit! Man sollte immer versuchen alles so simpel wie möglich zu halten, nicht nur bei der SW-Entwicklung. Versuche jede Lösung mit gerade dem Minimum an Komplexität zu realisieren den das Problem zulässt!

damit fällt dann auch Multithreading auf mehreren Cores weg. Denn damit holt man sich nen Haufen Probleme und die Komplexität steigt auch nicht ganz unwesentlich.

Das stimmt doch gar nicht, man muss in der Design-Phase nur das nötige Maß an Umsicht walten lassen dann bringt Multithreading fast keine zusätzliche Komplexität mit sich. Es gibt bestimmt auch Probleme die sich mit Multithreading leichter lösen lassen als ohne Multithreading.

Wird für Rendevouz-Funktionen genutzt (z.B. TSCs synchronisieren) und dafür alle außer der sendenden CPUs anzuhalten.

Wofür willst Du alle CPUs anhalten? Planst du noch andere Dinge für IPI?
Ich frage so hartnäckig weil ich auf meiner Plattform gar keine Möglichkeit habe eine bestimmte CPU zu unterbrechen aber viele OSe bei SMP eben so eine Möglichkeit erwarten und deswegen möchte ich vorher an alle Eventualitäten denken damit ich hinterher nichts vergessen hab.

Darum ging es aber garnicht - dies sind nur Möglichkeiten, ohne unterbrechbaren Kernel auf x86 auszukommen.

Ich denke ob man einen unterbrechbaren Micro-Kernel benötigt oder nicht hängt eher vom Kernel-Design ab und weniger von der darunter liegenden Hardware. Mal von den TLB-Flushs abgesehen benötigt man IMHO auch bei x86 keinen unterbrechbaren Micro-Kernel.


Grüße
Erik

[FlashBurn]

Das Problem das Du Pages bereits im Frei-Pool hast die aber eventuell noch in TLBs einiger/anderer CPUs drin sind muss aber gelöst werden indem Du alle TLBs löscht bevor die Pages in den Frei-Pool kommen. Das senden der IPIs und warten auf alle Antworten muss also in der Mitte von vmmUnmap() passieren und nicht erst hinterher.

So wie du dir das denkst funktioniert das bei mir nicht. Ich hatte doch mal ne vereinfachte Variante von meiner vmmUnmap/vmmMap geschrieben.
Die Pages landen ziemlich "spät" bis gar nicht im Frei-Pool. Die sind auch gar nicht das Problem, sondern das eine andere CPU auf Page A zugreift, da es so im TLB steht, aber inzwischen Page B an der virtuellen Adresse steht.
Diese Situation tritt natürlich sehr sehr selten auf.
Solange ich aus der vmmMap/vmmUnmap Funktion noch nicht rausbin, sind die Pages praktisch noch nicht in Verwendung. Also kann ich das TLB Löschen auch hinterher machen (aber ich gebe den Lock erst frei, wenn die Nachricht versendet ist).
Es ist halt wieder ne Performance-Frage, ich meine stell dir vor, es sollen 20 Pages geunmappt werden, da wäre es sehr schlecht wenn du auch 20 IPIs versendest und dann auch noch wartet müsstest bis die anderen CPUs ihr IPIs abgearbeitet haben!

Ich bestreite nicht das Du Dir Mühe gibst aber aus Deinen vergangenen Problembeschreibungen habe ich den subjektiven  Eindruck gewonnen das Dir da etwas an Erfahrung fehlt und Du deswegen verschiedene Probleme nicht so deutlich/frühzeitig erkennst.

Richtig, an Erfahrung mangelt es mir, besonders was das Programmieren von Anwendungen betrifft. Meine Programmiererfahrung beschränkt sich leider nur auf das OS Programmieren.

Du solltest mal ganz klar definieren was ein Bug ist und dann Code schreiben der zur Laufzeit (in der Debug-Version) nach genau dieser Bedingung prüft. Mit diesem Weg kommst Du zu recht präzisen Debug-Meldungen, zumindest bin ich bis her damit recht gut gefahren.

Am Bsp. einer Deadlock wüsste ich nicht wie ich zur Laufzeit prüfen könnte das einer vorliegt. Das gemeine am Deadlock ist doch, du kannst ja nicht wissen ob der Lock halt gerade in Benutzung ist und bald wieder freigegeben wird oder ob der Besitzer des Lock gerade versucht den Lock zu bekommen den man selber inne hat!

Jedes mal wenn Du einen Deadlock hast musst Du die Ursache heraus finden und dann wird Dein Code mit jedem beobachteten Deadlock besser.

Und genau hier ist doch das Problem. Ich kann nur Bugs fixen die ich "nachstellen" kann (das ist das größte Problem von Bugs eines OSs). Ein Deadlock der nur sporadisch auftritt und nach keinem Muster zu "fangen" ist, wie willst du da raus bekommen, in welcher Lock jemand war und welche Lock er bekommen wollte.

Was ich damit sagen will, stell dir vor du hast ein tolles OS geschrieben und das wird halt ausgeführt (ohne Debug-Msgs) und das bleibt halt von Zeit zur Zeit an immer einer anderen Stelle hängen und du als Entwickler kannst die Situation nicht nachstellen. Das kann alles sein, von Hardware-Problem bis irgendein Lockingfehler der schwer zu finden ist.

Klar gibt es ein paar zusätzliche Schwierigkeiten aber die sind IMHO nicht unlösbar.

Von unlösbar redet ja auch keiner, nur schwierig zu lösen

Das stimmt doch gar nicht, man muss in der Design-Phase nur das nötige Maß an Umsicht walten lassen dann bringt Multithreading fast keine zusätzliche Komplexität mit sich.

Fairerweise muss man schon mal sagen, wer macht denn ne wirkliche Design-Phase (mal von dir und deiner Hardware abgesehen)?
Ich behaupte mal das selbst bei größeren Softwareprojekten nicht so viel vorher designt wird, sondern das dann alle drauflos programmieren und deswegen kommt es oft zu Problemen.
Und ich als Hobbyprogrammieren/Anfänger werde mich bestimmt nicht vorher hinsetzen und ein Design anfertigen. Denn dann würde ich heute noch immer keinen Kernel haben, weil ich mich mit Dingen beschäftigen würde, von denen ich keine Ahnung habe und ohne Praxis auch nie haben werde.

Wofür willst Du alle CPUs anhalten? Planst du noch andere Dinge für IPI?

Anhalten will ich sie nur im Falle einer Kernel-Exception (damit die nicht alle ne for(;; Schleife abarbeiten) und wenn der PC runtergefahren wird. Ansonsten könnte man noch die Möglichkeit geben, CPUs zur Laufzeit "abzuschalten", aber wozu das gut sein soll weiß ich nicht.
Ich habe halt z.B. mit der Rendevouz-Funktion versucht mein IPI System möglichst nutzbar zu machen, keine Ahnung ob ich das später noch für was anderes als TSC synchronisieren nutzen werde.
Auch weiß ich nicht ob man je die Möglichkeit braucht das man eine IPI Nachricht an genau eine CPU (und eine bestimme) schicken können muss.

Mal von den TLB-Flushs abgesehen benötigt man IMHO auch bei x86 keinen unterbrechbaren Micro-Kernel.

Wenn du den Kernel mit einem GIANT_LOCK schützt brauchst du nichtmal dafür nen unterbrechbaren MikroKernel.

[FlashBurn]

Also die NMI Variante hat sogar noch den Vorteil, das dadurch mein CPU anhalten Code erst richtig funktioniert. Denn vorher ist immer mind. 1 CPU (B) in einer "endlos" Schleife hängen geblieben, da eine CPU (A) ne Exception ausgelöst hat und genau diese CPU (A) hat den Lock den die andere CPU (B) versucht zu bekommen und da die CPU (B) meistens die Ints aus hat, hat sie halt die IPI Nachricht nie bekommen, aber jetzt mit dem NMI klappt das wunderbar.

Jetzt kann ich auch endlich mal nen Bug fixen, der sonst so selten aufgetreten ist, das ich ihn nie reproduzieren konnte, jetzt klappt es öfter

Was noch gar nicht diskutiert wurde, hat denn die NMI Variante irgendwelche Nachteile?