Thema: Allgemeiner Ressourcen-Allocator

[FlashBurn]

Ich arbeite gerade an einem allgemeinen Ressourcen-Allocator (inspiriert durch Bonwick und seinen SlabAllocator) und stecke ein wenig fest.

Es geht darum das man viele ja auf Integerwerte und Bereich zurück führen kann (z.B. IDs und virtuelle Speicherbereiche).

Man initialisert eine sogenannte Map mit einem Startwert und einer Größe (z.B. beim UserSpace mit 0 als Startwert und 0xC0000000 als Größe). Desweiteren gibt man noch die Größe einer Einheit an (bei virtuellen Adressen 0x1000 und bei IDs 1).

Eine Map-Datenstruktur könnte also so aussehen:

Code: [Auswählen]

struct map_t {
 uint32t start;
 uint32t size;
 uint32t sizeItem;
};

Probleme habe ich jetzt bei der Organisation der einzelnen bzw. des gesamten Bereichs einer Map. Ich würde pro Bereich folgende Datenstruktur haben:

Code: [Auswählen]

struct mapSegment_t {
 uint32t start;
 uint32t size;
};

Wenn man ein Segment/Bereich aus einer Map haben möchte ist es hilfreich wenn die freien Segmente/Bereiche de größe nach geordnet sind. Damit es im extrem Fall auch schnell geht würde ich nen Baum (AVL/Rot-Schwarz) verwenden.

Wenn man ein Segment/Bereich wieder freigibt und 2 oder 3 Segmente/Bereiche zu einem zusammengefügt werden sollen, wäre es nicht schlecht wenn sie auch nach dem Start-Wert sortiert sind, also noch nen Baum.
Auch macht es eine Sortierung nach dem Start-Wert einfacher beim zurückgeben, eines Segments/Bereichs, zu überprüfen ob das Segement/der Bereich überhaupt benutzt war.

Das ist ja alles gut und schön, aber wenn ich z.b. an IDs denke dann finde ich den Speicherverbrauch ziemlich hoch. Wenn es um virtuelle Adressbereiche geht ist der Speicherverbrauch in Ordnung (meine momentane Variante verbraucht genauso viel).

Hat jemand eine Idee wie man das mit dem Sortieren noch anders lösen könnte, so dass der Speicherverbrauch geringer wird, aber die Geschwindigkeit erhalten bleibt?

[Svenska]

Du solltest grundsätzlich 64-Bit-Werte oder größer in deinen Strukturen verwenden, um z.B. einen ID-Adressraum oder den virtuellen Adressraum im 64-Bit-Modus abbilden zu können.

So wie ich das verstehe, steigt der Speicherverbrauch nur mit dem Fragmentierungsgrad der Nutzung aller Ressourcen. Das heißt, am Anfang enthalten beide Bäume genau einen Eintrag (mapSegment:start=map:start, mapSegment:size=mapSegment:size), wird dann ein Teil in Anspruch genommen, so existieren je zwei Einträge ("genutzter Bereich", dahinter "freier Bereich"). Gibst du den Bereich wieder frei, dann hast du nur noch einen Eintrag, wenn du direkt zusammenfügst. Der Speicherverbrauch hält sich somit in Grenzen.

Den Maximalspeicherverbrauch erreichst du also, wenn der Ressourcen-Adressraum den Aufbau "genutzt"-"ungenutzt"-"genutzt"-"ungenutzt"-... hat. Das ist allerdings äußerst unwahrscheinlich, da du z.B. IDs immer von vorne zuweist (Descriptoren nach POSIX müssen immer der kleinstmögliche sein) und Adressraum meist im Block alloziiert wird (und auch als Block freigegeben wird).

Es hängt also von der konkreten Ressource und insbesondere von deren Granularität (map:sizeItem) ab, wieviel Speicher für die Verwaltung der Strukturen draufgeht. Grundsätzlich sehe ich da aber keine Problem. Es sei denn, ich übersehe was.

Gruß,
Svenska

[FlashBurn]

Du solltest grundsätzlich 64-Bit-Werte oder größer in deinen Strukturen verwenden, um z.B. einen ID-Adressraum oder den virtuellen Adressraum im 64-Bit-Modus abbilden zu können.

Da es im Moment eh nur unter 32bit laufen soll, ist das erstmal nicht nötig und würde unnötig Spiecherplatzverschwenden.

Wenn es mal nach 64bit portiert werden sollte, kann man das ja ganz einfach ändern.

So wie ich das verstehe, steigt der Speicherverbrauch nur mit dem Fragmentierungsgrad der Nutzung aller Ressourcen. Das heißt, am Anfang enthalten beide Bäume genau einen Eintrag (mapSegment:start=map:start, mapSegment:size=mapSegment:size), wird dann ein Teil in Anspruch genommen, so existieren je zwei Einträge ("genutzter Bereich", dahinter "freier Bereich"). Gibst du den Bereich wieder frei, dann hast du nur noch einen Eintrag, wenn du direkt zusammenfügst. Der Speicherverbrauch hält sich somit in Grenzen.

Wenn ich dich jetzt richtig verstanden habe, dann hast du mich nicht richtig verstanden

Ich will nur die Bereiche speichern, die auch frei sind, die genutzten tauchen nirgends auf! Spart Speicher und zum Nachgucken ob ein Bereich der freigegeben werden soll auch wirklich genutzt ist, brauch ich einfach nur die "Liste" der freien Bereiche durchgehen, wo sie dem Start-Wert nach sortiert sind.

Den Maximalspeicherverbrauch erreichst du also, wenn der Ressourcen-Adressraum den Aufbau "genutzt"-"ungenutzt"-"genutzt"-"ungenutzt"-... hat. Das ist allerdings äußerst unwahrscheinlich, da du z.B. IDs immer von vorne zuweist (Descriptoren nach POSIX müssen immer der kleinstmögliche sein) und Adressraum meist im Block alloziiert wird (und auch als Block freigegeben wird).

Ja (Fragmentierung) und Nein (IDs). Ich gehe jetzt mal von Task, Thread und Port IDs aus. Da wäre es schön wenn man erstmal die Liste bis zum größt möglichen Wert durchgeht und dann wieder von vorne (natürlich nur die freien) anfängt.
Das wäre deswegen schön, weil dann die wahrscheinlich sinkt, das du als Programm ne Thread-ID von nem anderen Thread gespeichert hast und mit dem irgendetwas machen willst, aber inzwischen schon ein anderer Thread die ID hat (noch schlimmer ist das bei Ports).

Im Moment ist es bei mir sogar ziemlich einfach diesen worst-Case (genutzt-frei-genutzt-...) herzustellen. Man muss einfach nur zwei Programme haben, die jeweils das andere Programm starten und sich dann selbst beenden, da ich benutzte IDs nicht wiederverwende (weil es zu aufwendig wäre nen ganzen Baum nach einer freien ID zu durchsuchen).
Das gleiche kannst du im Adressraum machen, einfach den ganzen Adressraum allokieren und dann jede zweite "Page" wieder freigeben.

Also werde ich wohl den Baum benutzen, es sei denn ich finde noch ne schönere Datenstruktur.

Ich würde diese Map dann noch dahingehend erweitern, dass man seinen eigenen Allocator (für die mapSegment_t und die node_t Strukturen) mitgeben kann. Damit erreiche ich dann, dass ich diesen Ressourcen-Allocator auch für meinen VMM nutzen kann und kein Henne-Ei-Problem erschaffe. Theoretisch könnte man den Allocator sogar für nen PMM verwenden.

Ich überlege auch, ob es Sinn macht wenn man einer solchen Map noch Bereiche hinzufügen/adden könnte (wenn z.B. bei einem PMM "Löcher" im physikalischen Speicher sind).

[Svenska]

Hallo,

Ich will nur die Bereiche speichern, die auch frei sind, die genutzten tauchen nirgends auf! Spart Speicher und zum Nachgucken ob ein Bereich der freigegeben werden soll auch wirklich genutzt ist, brauch ich einfach nur die "Liste" der freien Bereiche durchgehen, wo sie dem Start-Wert nach sortiert sind.

Stimmt auch wieder. Ich suche nur noch nach einem Grund, warum das schlecht ist. Mir fällt keiner ein.

Ich gehe jetzt mal von Task, Thread und Port IDs aus. Da wäre es schön wenn man erstmal die Liste bis zum größt möglichen Wert durchgeht und dann wieder von vorne (natürlich nur die freien) anfängt.

In einer Baumstruktur den ersten Eintrag zu finden ist aber einfacher als einen Zwischenzeiger auf das "nächste" Element immer abzuspeichern - besonders, wenn du den Baum zwischenzeitlich änderst.

Das wäre deswegen schön, weil dann die wahrscheinlich sinkt, das du als Programm ne Thread-ID von nem anderen Thread gespeichert hast und mit dem irgendetwas machen willst, aber inzwischen schon ein anderer Thread die ID hat (noch schlimmer ist das bei Ports).

Das ist dann aber ein Bug im Programm (z.B. Leaking File Descriptor). Sachen wie Thread-IDs sollten übrigens für jede Anwendung in einem eigenen Adressraum stattfinden, denn Threads kommunizieren nie direkt mit anwendungsfremden Threads, sondern immer nur über IPC. Der Kernel sollte solche Interna besser nicht öffentlich machen.

Im Moment ist es bei mir sogar ziemlich einfach diesen worst-Case (genutzt-frei-genutzt-...) herzustellen. Man muss einfach nur zwei Programme haben, die jeweils das andere Programm starten und sich dann selbst beenden, da ich benutzte IDs nicht wiederverwende (weil es zu aufwendig wäre nen ganzen Baum nach einer freien ID zu durchsuchen).

Den Worst-Case herstellen ist immer einfach, wenn man den Algorithmus kennt. Auf diese Weise kriegst du jedes Betriebssystem in den Keller gefahren (es gibt Wettbewerbe, um einen Algorithmus so zu implementieren, dass er auf einem OS richtig krass langsam ist).

Wenn du in deinem Baum nur freie IDs speicherst, dann ist jedes Blatt des Baumes doch eine freie ID? Und die erste freie ID ist die, wenn du immer nur links abbiegst. Irre ich da? Wie gesagt, die Wiederverwertung von manchen Ressourcen wird von POSIX vorausgesetzt (wobei ich nicht weiß, inwieweit sich Anwendungen auch darauf verlassen).

Also werde ich wohl den Baum benutzen, es sei denn ich finde noch ne schönere Datenstruktur.

Ich kenne nur die einfachen Grundstrukturen, und simple binäre Bäume sind da Goldstandard...

Ich würde diese Map dann noch dahingehend erweitern, dass man seinen eigenen Allocator (für die mapSegment_t und die node_t Strukturen) mitgeben kann. Damit erreiche ich dann, dass ich diesen Ressourcen-Allocator auch für meinen VMM nutzen kann und kein Henne-Ei-Problem erschaffe. Theoretisch könnte man den Allocator sogar für nen PMM verwenden.

Naja, das bietet sich doch an, den für VMM zu verwenden. Adressraum ist schließlich auch "bloß" eine Ressource unter vielen. Ich merk mir den Grundgedanken auch selbst vor, denn darauf wär ich wahrscheinlich spontan nicht gekommen und gut ist es, soweit ichs einschätzen kann, auch.

Aber warum brauchst du einen eigenen Allokator, um das für dein VMM nutzen zu können? Baue doch ein 1:1-Mapping für ein paar KB auf und stelle eine statische Grundstruktur. Da du Bäume verwendest, ist jeder weitere Eintrag von den vorhandenen Einträgen unabhängig, zumindest was die Erzeugung betrifft.

Du erwähnst mir das Henne-Ei-Problem zu häufig - mach doch einfach eine komplett statische, im Code vorgegebene Struktur, die als Henne dient. Die Einschränkung, die sich ergibt, wäre beispielsweise, dass im Adressraum an der Stelle 216KB (oder halt woanders) kein Loch sein darf, da du dort den Anfang deines Baumes hinlegst. Wenn du das statisch vorcodierst, muss dein VMM-Allokator niemals Speicher alloziieren, um betriebsbereit zu werden.

Dann würde der Allokator auch für den PMM funktionieren.

Ich überlege auch, ob es Sinn macht wenn man einer solchen Map noch Bereiche hinzufügen/adden könnte (wenn z.B. bei einem PMM "Löcher" im physikalischen Speicher sind).

Du unterteilst deine Map in Bereiche, indem du die Löcher vom Kernel in Beschlag nimmst. Also der Kernel sucht die Löcher im Ressourcenadressraum und markiert diese als "belegt/unswapbar" für sich selbst. Schon ist das Loch gefüllt.

Gruß,
Svenska

[FlashBurn]

Sachen wie Thread-IDs sollten übrigens für jede Anwendung in einem eigenen Adressraum stattfinden, denn Threads kommunizieren nie direkt mit anwendungsfremden Threads, sondern immer nur über IPC. Der Kernel sollte solche Interna besser nicht öffentlich machen.

Es gibt aber so Sachen wie die Priorität eines Threads ändern und dafür brauchst du dann die ID und es gibt bestimmt noch andere Sachen. Es wird die Situation das ein Thread seine ID oder die eines anderen Wissen möchte (so fern er es darf) also schon geben.

Und die ProzessID wirst du irgendwann auf jeden Fall mal brauchen.

Wenn du in deinem Baum nur freie IDs speicherst, dann ist jedes Blatt des Baumes doch eine freie ID? Und die erste freie ID ist die, wenn du immer nur links abbiegst. Irre ich da? Wie gesagt, die Wiederverwertung von manchen Ressourcen wird von POSIX vorausgesetzt (wobei ich nicht weiß, inwieweit sich Anwendungen auch darauf verlassen).

Nope. Bei meiner momentanen Implementierung stehen in dem Baum z.B. Thread-Diskriptoren und jeder Thread hat ne ID. Also stehen in dem Baum nur benutzte IDs, wenn ich jetzt ne freie finden möchte (und nicht den einfachsten Fall nehme -> größte ID + 1) muss ich den ganzen Baum durchsuchen (im worst-case, obwohl der average-case auch nicht besser sein wird).

Aber warum brauchst du einen eigenen Allokator, um das für dein VMM nutzen zu können?

Um mir ne endlos-Schleife zu vermeiden. Denn der Map-Code ruft den Slab-Allocator auf, der ruft den VMM auf und der wiederrum den Map-Code und das Spiel geht wieder von vorne los.

Das lässt sich leider nicht so leicht lösen und deswegen nutze ich da nen eigenen Allocator, der nur aus nem bestimmten statischen Bereich die Objekte holt.

Auch habe ich in meinem KernelSpace für jeden Prozess ne Art privaten Bereich reserviert, für genau diese Datenstrukturen und nutze da dann auch nen eigenen Allocator.

Du unterteilst deine Map in Bereiche, indem du die Löcher vom Kernel in Beschlag nimmst. Also der Kernel sucht die Löcher im Ressourcenadressraum und markiert diese als "belegt/unswapbar" für sich selbst. Schon ist das Loch gefüllt.

Dann hast du das Prinzip nicht verstanden. Ich speichere nicht welche Bereiche in Benutzung sind und von wem, sondern nur was noch frei ist und wie groß der "Ur-Bereich" ist.

Deswegen könnte es durch einen Fehler/Bug passieren das man einfach ein solches Loch freigeben könnte. Wenn ich aber in einer Map mehrere Unter-Maps speichern könnte, dann wäre das kein Problem.

Was den PMM betrifft, wird das bei mir nichts werden (es sei denn ich nutze viele Maps, aber das lohnt sich einfach nicht), weil ich auch 4MB Pages unterstütze und mein PMM daher immer darauf achtet das er nur Pages rausgibt, so dass die größtmöglichste Anzahl an 4MB Pages frei ist.

Ansonsten kann man solch einen Allocator für viele Sachen benutzen, was natürlich den Code kleiner und robuster macht.

[Svenska]

Hallo,

Sachen wie Thread-IDs sollten übrigens für jede Anwendung in einem eigenen Adressraum stattfinden, denn Threads kommunizieren nie direkt mit anwendungsfremden Threads, sondern immer nur über IPC. Der Kernel sollte solche Interna besser nicht öffentlich machen.

Es gibt aber so Sachen wie die Priorität eines Threads ändern und dafür brauchst du dann die ID und es gibt bestimmt noch andere Sachen. Es wird die Situation das ein Thread seine ID oder die eines anderen Wissen möchte (so fern er es darf) also schon geben.

Mein Ansatz war, dass jeder Prozess mehrere Threads haben kann, die immer durchnummeriert werden, es für jeden Prozess also einen eigenen ID-Raum gibt. Nur der Kernel kennt die systemweite ID des Threads, der Thread selbst nicht. Damit kann es solche leckenden ThreadIDs vom Userspace aus nicht geben.

Und die ProzessID wirst du irgendwann auf jeden Fall mal brauchen.

Prozesse sind an sich unabhängig, daher kriegen die eine systemweit eindeutige ID (sonst gäbe es ja sonst nur ProzessID=0 für jeden Prozess); Threads sind nicht unabhängig, da jeweils mehrere zu einem Prozess als Oberklasse gehören (und bekommen darum einen eigenen Raum für ihre IDs).

Wenn du in deinem Baum nur freie IDs speicherst, dann ist jedes Blatt des Baumes doch eine freie ID? Und die erste freie ID ist die, wenn du immer nur links abbiegst. Irre ich da? Wie gesagt, die Wiederverwertung von manchen Ressourcen wird von POSIX vorausgesetzt (wobei ich nicht weiß, inwieweit sich Anwendungen auch darauf verlassen).

Nope. Bei meiner momentanen Implementierung stehen in dem Baum z.B. Thread-Diskriptoren und jeder Thread hat ne ID. Also stehen in dem Baum nur benutzte IDs, wenn ich jetzt ne freie finden möchte (und nicht den einfachsten Fall nehme -> größte ID + 1) muss ich den ganzen Baum durchsuchen (im worst-case, obwohl der average-case auch nicht besser sein wird).

Achso. Vor 2 Posts schriebst du nämlich, du speicherst nur die freien Bereiche. Wenn du nur die belegten Bereiche speicherst, wird das natürlich aufwendiger.

Du unterteilst deine Map in Bereiche, indem du die Löcher vom Kernel in Beschlag nimmst. Also der Kernel sucht die Löcher im Ressourcenadressraum und markiert diese als "belegt/unswapbar" für sich selbst. Schon ist das Loch gefüllt.

Dann hast du das Prinzip nicht verstanden. Ich speichere nicht welche Bereiche in Benutzung sind und von wem, sondern nur was noch frei ist und wie groß der "Ur-Bereich" ist.

Hier schreibst du, du speicherst nur freie Ressourcen. Einige dich mal auf eine Version. Die Vorteile von beiden Varianten bekommst du übrigens, wenn du zwei Bäume hast - einen mit den freien Bereichen, den anderen mit den belegten Bereichen. Die kleinste unbenutzte ID findet sich dann im "Frei-Baum" und wenn du eine bestimmte Ressource suchst, dann findest du die im "Belegt-Baum".

Deswegen könnte es durch einen Fehler/Bug passieren das man einfach ein solches Loch freigeben könnte. Wenn ich aber in einer Map mehrere Unter-Maps speichern könnte, dann wäre das kein Problem.

Mein Gedanke ist, dass der Kernel die Löcher als belegt markiert und sie nie freigegeben werden dürfen. Wenn du ein solches Loch freigibst, ist das ein Bug und sollte gefixt werden, statt das Problem zu verschleiern. Je weniger Code, desto weniger Bugs.

Aber warum brauchst du einen eigenen Allokator, um das für dein VMM nutzen zu können?

Um mir ne endlos-Schleife zu vermeiden. Denn der Map-Code ruft den Slab-Allocator auf, der ruft den VMM auf und der wiederrum den Map-Code und das Spiel geht wieder von vorne los.

Das ist schon klar. Aber die Endlosschleife entsteht doch nur Erzeugen der allerersten Datenstrukturen, weil diese Ressourcen sind und sich somit selbst verwalten. In dem Moment, wo du diese erzeugt hast, ist dein Allokator doch funktionsfähig. Also erzeugst du die statisch (bereits im Code), dann umgehst du die ganzen Schwierigkeiten. Das ähnelt dann der Lebendgeburt von Eriks System.

Das lässt sich leider nicht so leicht lösen und deswegen nutze ich da nen eigenen Allocator, der nur aus nem bestimmten statischen Bereich die Objekte holt.

Dynamisch zur Laufzeit. Mach das Ergebnis doch statisch zur Compilezeit, dann sparst du dir den eigenen Allokator und das Henne-Ei-Problem.

Auch habe ich in meinem KernelSpace für jeden Prozess ne Art privaten Bereich reserviert, für genau diese Datenstrukturen und nutze da dann auch nen eigenen Allocator.

Das verstehe ich nicht.

Was den PMM betrifft, wird das bei mir nichts werden (es sei denn ich nutze viele Maps, aber das lohnt sich einfach nicht), weil ich auch 4MB Pages unterstütze und mein PMM daher immer darauf achtet das er nur Pages rausgibt, so dass die größtmöglichste Anzahl an 4MB Pages frei ist.

Mach doch eine Map je Pagegröße, die du miteinander synchronisierst. Belegst du eine 4MB-Page, so werden 4MB in der 4KB-Map als belegt markiert und belegst du eine 4KB-Page, so wird in der 4MB-Map eine einzelne Page markiert. Für andere Pagegrößen gilt entsprechendes. Kostet ein bisschen RAM, sollte aber dennoch schneller sein, als alles aus einer Map mit der kleinsten Pagegröße rauszupopeln.

Allerdings weiß ich nicht, wie effizient dein jetziger PMM arbeitet. Gehe ich richtig in der Annahme, dass dein VMM sowieso ständig auf den PMM zugreift? Dann lohnt sich es wahrscheinlich trotzdem, den PMM ebenfalls in dieses Schema zu stopfen. Spart man sich zwei verschiedene Allokatoren mit verschiedenen Bugs und von Bugfixes profitieren dann alle Beteiligten.

Gruß,
Svenska

[FlashBurn]

Mein Ansatz war, dass jeder Prozess mehrere Threads haben kann, die immer durchnummeriert werden, es für jeden Prozess also einen eigenen ID-Raum gibt. Nur der Kernel kennt die systemweite ID des Threads, der Thread selbst nicht. Damit kann es solche leckenden ThreadIDs vom Userspace aus nicht geben.

Willst du wirklich 2 IDs für Threads vergeben, weil sich deine Erklärung so anhört und das wäre doch quatsch.
Ob du nun nen eigenen ID-Raum für Threads hast oder nicht, du brauchst nur eine ID. Denn wenn du sagst das die Prozess und die Thread IDs nur 16bit groß sind (was für 32bit Systeme vollkomen ausreichend sein sollte) dann bildest du eine globale ID aus den beiden zusammen.
Ich plane halt so das ich bestimmt mal irgendwo die Thread ID brauche.

Achso. Vor 2 Posts schriebst du nämlich, du speicherst nur die freien Bereiche. Wenn du nur die belegten Bereiche speicherst, wird das natürlich aufwendiger.

Nee, ich habe geschrieben dass das so bei meiner momentanen Implementierung ist und da wird dieser allgemeine Allocator noch nicht genutzt.

Bei dem vorgeschlagenen allgemeinen Ressourcen Allocator sollen nur die freien Bereiche gespeichert werden.

Mein Gedanke ist, dass der Kernel die Löcher als belegt markiert und sie nie freigegeben werden dürfen. Wenn du ein solches Loch freigibst, ist das ein Bug und sollte gefixt werden, statt das Problem zu verschleiern. Je weniger Code, desto weniger Bugs.

Ich dachte da dann auch an irgendwelche "Löcher" im UserSpace, die das Programm zwar versuchen könnte freizugeben, was aber nicht passieren darf. Dagegen habe ich im moment noch keinen Schutz, aber den bräuchte man und da kannst du dann nicht so eine einfache Lösung nehmen.

Das ist schon klar. Aber die Endlosschleife entsteht doch nur Erzeugen der allerersten Datenstrukturen, weil diese Ressourcen sind und sich somit selbst verwalten. In dem Moment, wo du diese erzeugt hast, ist dein Allokator doch funktionsfähig. Also erzeugst du die statisch (bereits im Code), dann umgehst du die ganzen Schwierigkeiten.

Nope! Das Starten ist nicht das Problem, sondern die Sachen die während der Laufzeit passieren.

Ich allokieren alle Datenstrukturen dynamisch, bei mir ist in dem Sinne nichts statisch und dadurch kann es passieren das der VMM dynamisch ne Datenstruktur allokiert. Das ganze würde dann über den allgemeinen SlabAllocator-Code gemacht werden und dieser stellt fest das er keine Objekte mehr in seinem Cache hat und muss vom VMM neuen Speicher anfordern und dadurch entsteht die endlos Schleife.

Ich weiß net ob du da mit dem VMM vom Linuxkernel durcheinander kommst, denn den finde ich mal richtig scheiße Meiner funktioniert etwas anders.
Ich mappe im KernelSpace nicht 1:1 sondern bei mir passiert alles dynamisch, ich nutze also Paging auch im KernelSpace aus.

Auch habe ich in meinem KernelSpace für jeden Prozess ne Art privaten Bereich reserviert, für genau diese Datenstrukturen und nutze da dann auch nen eigenen Allocator.

Das verstehe ich nicht.

Normalerweise ist doch der KernelSpace für alle Prozesse gleich. Dem ist bei mir nicht so, ich habe nen Bereich der für jeden Prozess anders ist und aus diesem Bereich kommen die Objekte/Datenstrukturen die der VMM für den UserSpace braucht.
Dadurch verbrauche ich weniger virtuellen Speicher und könnte meinen Kernel wahrscheinlich sogar auf 512MB anstatt 1GB virtuellen Speicher beschränken.

Mach doch eine Map je Pagegröße, die du miteinander synchronisierst. Belegst du eine 4MB-Page, so werden 4MB in der 4KB-Map als belegt markiert und belegst du eine 4KB-Page, so wird in der 4MB-Map eine einzelne Page markiert. Für andere Pagegrößen gilt entsprechendes. Kostet ein bisschen RAM, sollte aber dennoch schneller sein, als alles aus einer Map mit der kleinsten Pagegröße rauszupopeln.

Allerdings weiß ich nicht, wie effizient dein jetziger PMM arbeitet. Gehe ich richtig in der Annahme, dass dein VMM sowieso ständig auf den PMM zugreift? Dann lohnt sich es wahrscheinlich trotzdem, den PMM ebenfalls in dieses Schema zu stopfen.

Ich behaupte das mein jetziger PMM schneller (wesentlich schneller) ist als es eine zusammengefrieckelte Map Variante je sein könnte.

Spart man sich zwei verschiedene Allokatoren mit verschiedenen Bugs und von Bugfixes profitieren dann alle Beteiligten.

Das ist auch eine Idee hinter diesem allgemeinen Allocator und trotzdem werde ich meinen PMM extra behandeln (das hat mehrere Gründe).

[Svenska]

Hallo,

Mein Ansatz war, dass jeder Prozess mehrere Threads haben kann, die immer durchnummeriert werden, es für jeden Prozess also einen eigenen ID-Raum gibt. Nur der Kernel kennt die systemweite ID des Threads, der Thread selbst nicht. Damit kann es solche leckenden ThreadIDs vom Userspace aus nicht geben.

Willst du wirklich 2 IDs für Threads vergeben, weil sich deine Erklärung so anhört und das wäre doch quatsch.

Ja, daran dachte ich wirklich. Außer bissl RAM-Verbrauch (bei 1k Threads etwa 8k RAM) und bissl CPU-Verbrauch sehe ich da auch keine Probleme.

Ob du nun nen eigenen ID-Raum für Threads hast oder nicht, du brauchst nur eine ID. Denn wenn du sagst das die Prozess und die Thread IDs nur 16bit groß sind (was für 32bit Systeme vollkomen ausreichend sein sollte) dann bildest du eine globale ID aus den beiden zusammen.

Das ist natürlich eine elegantere Lösung. Zwar kennt der Thread dann seine kernelinterne ID, aber es ist halt unwahrscheinlicher, dass er durch Rechenfehler plötzlich auf einen prozessfremden Thread zugreifen will. Darum ging es mir.

Bei dem vorgeschlagenen allgemeinen Ressourcen Allocator sollen nur die freien Bereiche gespeichert werden.

Damit bist du doch einmal das Problem der Löcher los (die sind nie frei) und kannst gleichzeitig immer den ersten freien Descriptor (das erste Baumblatt) zurückgeben.

Mein Gedanke ist, dass der Kernel die Löcher als belegt markiert und sie nie freigegeben werden dürfen. Wenn du ein solches Loch freigibst, ist das ein Bug und sollte gefixt werden, statt das Problem zu verschleiern. Je weniger Code, desto weniger Bugs.

Ich dachte da dann auch an irgendwelche "Löcher" im UserSpace, die das Programm zwar versuchen könnte freizugeben, was aber nicht passieren darf. Dagegen habe ich im moment noch keinen Schutz, aber den bräuchte man und da kannst du dann nicht so eine einfache Lösung nehmen.

Da sehe ich das Problem nicht. Was meinst du für Löcher im Userspace? Ein Programm darf nur Ressourcen in Anspruch nehmen, die es vom System angefordert und zugewiesen bekommen hat - und auch nur diese Ressourcen darf es wieder freigeben. Löcher werden aber niemals zugewiesen, können also auch nicht freigegeben werden. Und die Verwaltung der zugewiesenen Ressourcen obliegt dem Programm selbst, also hat sich der Kernel nicht drum zu kümmern.

Ich allokieren alle Datenstrukturen dynamisch, bei mir ist in dem Sinne nichts statisch und dadurch kann es passieren das der VMM dynamisch ne Datenstruktur allokiert. Das ganze würde dann über den allgemeinen SlabAllocator-Code gemacht werden und dieser stellt fest das er keine Objekte mehr in seinem Cache hat und muss vom VMM neuen Speicher anfordern und dadurch entsteht die endlos Schleife.

Achso. Dann ist das Problem im Design enthalten und nicht lösbar... zirkuläre Abhängigkeiten sind für mich schlechtes Design. Erklärt aber dein Problem.

Ich weiß net ob du da mit dem VMM vom Linuxkernel durcheinander kommst, denn den finde ich mal richtig scheiße Meiner funktioniert etwas anders.

Nö, hab ich mir nie angeschaut, kann ich nicht beurteilen.

Normalerweise ist doch der KernelSpace für alle Prozesse gleich. Dem ist bei mir nicht so, ich habe nen Bereich der für jeden Prozess anders ist und aus diesem Bereich kommen die Objekte/Datenstrukturen die der VMM für den UserSpace braucht.
Dadurch verbrauche ich weniger virtuellen Speicher und könnte meinen Kernel wahrscheinlich sogar auf 512MB anstatt 1GB virtuellen Speicher beschränken.

Klingt kompliziert.

Theoretische Zwischenfrage: Ist es möglich, in den Adressraum jeden Prozesses nur eine einzelne Page einzublenden, die nur eine IPC-Funktion enthält und auf diese Weise Kernelfunktionen bereitzustellen?

Gruß

[FlashBurn]

Damit bist du doch einmal das Problem der Löcher los (die sind nie frei) und kannst gleichzeitig immer den ersten freien Descriptor (das erste Baumblatt) zurückgeben.

Es geht mir nicht darum das man diese "Löcher" allokieren könnte, sondern das man sie freigeben kann und dann könnten sie allokiert werden!

Ein Programm darf nur Ressourcen in Anspruch nehmen, die es vom System angefordert und zugewiesen bekommen hat - und auch nur diese Ressourcen darf es wieder freigeben. Löcher werden aber niemals zugewiesen, können also auch nicht freigegeben werden. Und die Verwaltung der zugewiesenen Ressourcen obliegt dem Programm selbst, also hat sich der Kernel nicht drum zu kümmern.

Du vertraust einem Programm aber ganz schön. Denn dann würde es auch keine Buffer-Overflows geben, wenn die Programme nur soviele Daten "schicken" wie sie dürfen!
Es geht um das freigeben von Speicher/virtuellem Speicher und da gibt es Sachen im UserSpace die ich gerne davor schützen würde.
Zumal sich mein Kernel wahrscheinlich mehr um den UserSpace kümmert als das normalerweise der Fall ist.

Achso. Dann ist das Problem im Design enthalten und nicht lösbar... zirkuläre Abhängigkeiten sind für mich schlechtes Design. wink Erklärt aber dein Problem.

Dann wäre meine Frage wie du das Problem lösen willst, das der VMM Datenstrukturen dynamisch allokiert und damit er das machen kann muss er ja wieder (irgendwann) auf den VMM zugreifen.
Du brauchst also ne Möglichkeit im VMM Speicher zu allokieren ohne das du den VMM dazu brauchst.

Dafür wäre übrigens der Thread wo ich mein VMM Design vorgestellt habe nicht schlecht.

Klingt kompliziert.

Nicht wirklich, ich hab halt nen bestimmten Bereich (am Ende des KernelSpace) von 8MB (glaub ich, habe jetzt nicht nachgesehen) wo in jedem Prozess andere physikalische Pages gemappt sind und aus diesem Bereich hole ich mir die Datenstrukturen für den VMM (der für den UserSpace zuständig ist).

Theoretische Zwischenfrage: Ist es möglich, in den Adressraum jeden Prozesses nur eine einzelne Page einzublenden, die nur eine IPC-Funktion enthält und auf diese Weise Kernelfunktionen bereitzustellen?

Das musst du genauer erklären!

Meinst du das du den Funktions-Code von einer Kernel-Funktion in den UserSpace mappst und dort dann vom "User" der Code ausgeführt werden kann?
Wenn ja, wird nichts werden, weil du dann ja auch die Datenstrukturen mit in den UserSpace mappen musst und dafür muss genug freier virtueller Speicher vorhanden sein, dann kommt noch hinzu das du den Speicher mit den Datenstrukturen erstmal finden musst und du erlaubst dem User damit nicht nur deine Daten lesen zu können, sondern auch noch zu schreiben und dann kannst du das Konzept des getrennten Kernel- und UserSpace gleich abschaffen.

[Svenska]

Hallo,

Damit bist du doch einmal das Problem der Löcher los (die sind nie frei) und kannst gleichzeitig immer den ersten freien Descriptor (das erste Baumblatt) zurückgeben.

Es geht mir nicht darum das man diese "Löcher" allokieren könnte, sondern das man sie freigeben kann und dann könnten sie allokiert werden!

Freigeben kann man Ressourcen aber nur dann, wenn man sie besitzt oder liege ich da falsch? Wenn dein Kernel sich die Löcher selbst greift, kann nur er sie wieder freigeben und genau das tut er ja nie...

Ein Programm darf nur Ressourcen in Anspruch nehmen, die es vom System angefordert und zugewiesen bekommen hat - und auch nur diese Ressourcen darf es wieder freigeben. Löcher werden aber niemals zugewiesen, können also auch nicht freigegeben werden. Und die Verwaltung der zugewiesenen Ressourcen obliegt dem Programm selbst, also hat sich der Kernel nicht drum zu kümmern.

Du vertraust einem Programm aber ganz schön. Denn dann würde es auch keine Buffer-Overflows geben, wenn die Programme nur soviele Daten "schicken" wie sie dürfen!

Darum gibt es Zugriffsrechte. Prozesse werden gekillt, wenn sie auf ihnen nicht gehörende Ressourcen zugreifen wollen. Wenn ein Programm Ressourcen freigeben möchte, die ihm nicht gehören, wird es gekillt. Wenn ein Programm Ressourcen anfordern möchte, die bereits ein anderes Programm hat, wird die Anforderung abgelehnt. Will ein Programm Daten ausführen, wird es gekillt. Will ein Programm auf nur lesbare Pages schreiben, wird es gekillt. Und so weiter.

In seinen eigenen Ressourcen darf sich ein jeder Prozess frei austoben, der Kernel hat nur die Aufgabe, die Prozesse voreinander zu schützen, gegenseitig voneinander abzusichern und Dienste anzubieten, die Interprozesskommunikation ermöglichen. Buffer-Overflows sind Programmfehler, keine Betriebssystemfehler. Du solltest deinen Kernel also gegen Buffer-Overflows absichern, wie es jedes Programm auch tun muss.

Es geht um das freigeben von Speicher/virtuellem Speicher und da gibt es Sachen im UserSpace die ich gerne davor schützen würde.

Wenn dein Programm Speicher freigeben möchte, dann wird es damit schon Recht haben. Greift es danach nochmal auf diesen Speicher zu, wird es gekillt - das darf man nämlich nicht.

Zumal sich mein Kernel wahrscheinlich mehr um den UserSpace kümmert als das normalerweise der Fall ist.

Ich denke da wohl anders drüber.

Dann wäre meine Frage wie du das Problem lösen willst, das der VMM Datenstrukturen dynamisch allokiert und damit er das machen kann muss er ja wieder (irgendwann) auf den VMM zugreifen.
Du brauchst also ne Möglichkeit im VMM Speicher zu allokieren ohne das du den VMM dazu brauchst.

Es geht also darum, dass der VMM Speicher für sich selbst unter Verwendung des VMM reservieren muss. Genau das darf er aber nicht tun. Da fallen mir spontan nur zwei Möglichkeiten ein, die ich (mangels eigenem OS) nicht ausführlich erklären kann. Also keine Garantie auf Funktion [oder das ich überhaupt etwas verstehe].

(a) Der VMM reserviert sich selbst keinen Speicher dynamisch.
Das setzt voraus, dass die benötigten Datenstrukturen für den VMM in ihrer Größe zur Laufzeit statisch sind. Keine Ahnung, ob das funktioniert. Immerhin kann man die Größe der Datenstrukturen ermitteln und festlegen, bevor der VMM funktionsbereit sein muss.

Führt zwangsweise zu einem sehr sparsamen VMM mit vielen Einstellmöglichkeiten, für Mikrocontroller oder sowas sicherlich gut machbar. Ansonsten unelegant.

(b) Der VMM reserviert sich Speicher nicht über den VMM.
Da der VMM selbst die Hoheit über den virtuellen Adressraum hat, muss er seine eigenen Datenstrukturen ja nicht in den gleichen Büchern führen, wie die restlichen Datenstrukturen. Er darf - im Gegensatz zu allen anderen - die Ressourcen auch erst verwenden und danach die Buchführung betreiben, schließlich verwaltet er ja die Ressourcen und was nicht durch seine Finger gegangen ist, darf auch niemand anders nutzen.

Konkret darf der VMM einfach einen Block virtuellen, bisher ungenutzten Adressraum für sich selbst nehmen, ihn benutzen und erst im Anschluss daran die Bäume pflegen.

Soweit ich dich und das Slab Allocator-Prinzip verstehe, fragt die Anwendung beim Slab Allocator nach Objekten, die der Slab Allocator aus einem Cache zurückgibt. Ist im Cache nichts mehr frei, muss ein neues Stück Speicher zu einem neuen Cache für Objekte umfunktioniert werden und dazu fragt der Slab Allocator beim VMM an. In diesem Augenblick darf der VMM niemals beim Slab Allocator nach Objekten für sich selbst fragen, denn das wäre unzulässiges Layering und eine zirkuläre Abhängigkeit. Dafür gibt es wieder zwei Auswege, die mir einfallen:

(a) Der VMM benutzt keinen Slab Allocator.
Der VMM kümmert sich vollautonom um den virtuellen Speicher und benutzt selbst den PMM für den Zugriff auf den physischen Speicher. Mehr nicht. Der Slab Allocator nutzt dann den VMM, um seine Caches zu bauen, für alles, was so von den oberen Schichten (Kernel, Treiber, Anwendungen) anfällt. Da er den VMM benötigt, darf er diesen nicht verwalten. Du hast also mehrere getrennte Schichten.

(b) Der VMM ist gleichzeitig der Slab Allocator.
Damit verwischst du die Schichten, indem du grundsätzlich VMM und Slab Allocator gemeinsam implementierst. Du verwaltest somit keinen virtuellen Speicher mehr, sondern direkt Slab-Caches im physischen Speicher. Dein Slab Allocator redet also nach unten nicht mit einem VMM, sondern direkt mit dem PMM und verwaltet den virtuellen Speicher für sich selbst (und niemand anders hat darauf Zugriff).

Das geht natürlich nicht, wenn du Objekte irgendwo außerhalb des physischen Speichers alloziieren möchtest. Moderne nVidia-/ATI-Grafikkarten haben eine eigene MMU und die Speicherverwaltung im Grafikspeicher unterliegt gewissen Grenzen, wenn man so Sachen wie CUDA haben will; das lässt sich nicht ausschließlich über Slabs lösen. (Allerdings kann man das natürlich im Grafiktreiber implementieren, statt im System. Und für dich sollte das ohnehin irrelevant sein.)

Hoffe, das hilft. Im VMM-Thread kann ich nicht wirklich etwas beitragen, da ich das Problem an anderer Stelle sehe. Du verwischst die Grenzen nicht vollständig, sondern implementierst schnittstellenfremde Durchgriffe durch die Ebenen, sodaß dein VMM den Slab Allocator kennt und dein Slab Allocator den VMM mit dem Ziel, dass dein VMM selbst Slabs zu seiner eigenen Verwaltung verwenden kann. Das ist nicht einfach, nicht sauber und führt zu Problemen, wenn du Teile davon austauschen möchtest.

Theoretische Zwischenfrage: Ist es möglich, in den Adressraum jeden Prozesses nur eine einzelne Page einzublenden, die nur eine IPC-Funktion enthält und auf diese Weise Kernelfunktionen bereitzustellen?

Das musst du genauer erklären!

Ich mache mal einen eigenen Thread auf, denn das ist hier OT. (Gehört nicht dieser Thread nach OS-Design? Hier geht es doch um Ideen, nicht um die konkrete Implementierung - oder hab ich deinen Thread versehentlich theoretisiert?)

Gruß,
Svenska

[FlashBurn]

Freigeben kann man Ressourcen aber nur dann, wenn man sie besitzt oder liege ich da falsch? Wenn dein Kernel sich die Löcher selbst greift, kann nur er sie wieder freigeben und genau das tut er ja nie...

Ich sags mal so, mein Kernel stellt eine Funktion zur Verfügung womit du als User wieder virtuellen (und damit verbunden physischen) Speicher wieder freigeben kannst.
Da ich nicht Buch führe wer welche Ressource (was die Map allgemein und die virtuellen Bereiche speziell betrifft) hat, kann ich auch nicht nachprüfen ob jemand eine Ressource freigibt, die ihm gar nicht gehört. Im Kernel sollte das nicht passieren, da wäre es ein Bug, aber wenn der User sowas probiert sollte man das schon abfangen können.

Um auf das Bsp. mit dem Freigeben von virtuellem Speicher zurück zu kommen, so könnte der User einfach diesen Syscall aufrufen mit einer Adresse die er gar nicht "besitzt" sondern die ich als OS "besitze" (die aber im UserSpace sind) und genau das will ich verhindern.

Da der VMM selbst die Hoheit über den virtuellen Adressraum hat, muss er seine eigenen Datenstrukturen ja nicht in den gleichen Büchern führen, wie die restlichen Datenstrukturen.

Äh, das ist im Prinzip genau das was ich mache.

Der VMM kümmert sich vollautonom um den virtuellen Speicher und benutzt selbst den PMM für den Zugriff auf den physischen Speicher.

Ist ja fast wieder das selbe wie oben. Auch ich nutze den SlabAllocator nicht (mehr) für den VMM, aber den Allocator den ich mir geschrieben habe, funktioniert genauso wie der SlabAllocator (weil der einfach besser ist).

Das ist nicht einfach, nicht sauber und führt zu Problemen, wenn du Teile davon austauschen möchtest.

Ich behaupte mal dieser Satz ist quatsch. Denn er impleziert ja (so wie ich ihn verstehe) das du alles so allgemein wie möglich halten musst und damit dürftest du den SlabAllocator ja sowieso nie effizient (denn man kann den SlabAllocator auch für malloc/free einsetzen, aber das ist sehr unschön) einsetzen und das wäre ja quatsch.
Irgendwelche Komponenten auszutauschen wird immer irgendwo zu Problemen führen.

[erik.vikinger]

Hallo,

Es geht also darum, dass der VMM Speicher für sich selbst unter Verwendung des VMM reservieren muss. Genau das darf er aber nicht tun.

Warum? Genau das möchte ich auch tun. Nur mit einer kleinen Abwandlung im SlabAllocator für die Heap-Objekte des Kernels, der SlabAllocator holt die doch immer aus einem (oder mehreren) großen Block und wenn dort der Platz fast aufgebraucht ist dann wird ein Flag gesetzt aber die Heap-Anforderung des VMM (z.B. nach einem neuen Baum-Element für die VMM-Verwaltungsstrukturen) trotzdem noch bedient (es ist ja noch ein kleiner Rest übrig). Wenn der VMM dann fertig ist mit seiner Arbeit sollte er als letztes den VMM-Lock abgeben (der VMM ist eine zentrale Ressource die IMHO nur einmal gleichzeitig benutzt werden kann) aber unmittelbar bevor der Lock freigegeben wird wird noch geprüft ob das Heap-SlabAllocator-NearEmpty-Flag gesetzt ist und dann für den SlabAllocator noch mal ein dicker Brocken alloziert, das kann gemacht werden weil der VMM von seiner eigentlichen Arbeit ja nicht mehr in einem kritischen Zustand ist. Mit diesem Trick kann ich den Kernel-Heap voll dynamisch verwalten und auch der VMM kann den Kernel-Heap benutzen um dort seine Verwaltungsstrukturen zu holen und trotzdem kann der Heap aus großen Blöcken vom VMM geholt werden. Der Heap würde also die Verwaltungsstrukturen die ihn beschreiben selber enthalten.

(a) Der VMM reserviert sich selbst keinen Speicher dynamisch.

Das bedeutet das der VMM nur eine begrenzte Anzahl an Speicherblöcken verwalten kann und ist IMHO damit nicht mal für Mikrocontroller einsetzbar.

(b) Der VMM reserviert sich Speicher nicht über den VMM.

Das bedeutet das es mehrere unabhängige Allozierungsechanismen geben muss und das halte ich für ungeschickt.
Du weißt ja:

Je weniger Code, desto weniger Bugs.

Deswegen sollte es jede Funktionalität nur genau ein mal geben.

Konkret darf der VMM einfach einen Block virtuellen, bisher ungenutzten Adressraum für sich selbst nehmen, ihn benutzen und erst im Anschluss daran die Bäume pflegen.

Das stimmt schon, der VMM muss die Verwaltungsstrukturen nicht sofort aktualisieren aber eben doch bevor er sein return macht.

In diesem Augenblick darf der VMM niemals beim Slab Allocator nach Objekten für sich selbst fragen, denn das wäre unzulässiges Layering und eine zirkuläre Abhängigkeit.

Du meinst also das der VMM niemals ein kmalloc benutzen darf? Das würde bedeuten Du musst extra/exklusiv für den VMM was spezielles bauen das diese Funktionalität anbietet. Wie gesagt, das halte ich für ungeschickt wegen dem doppeltem Code und wenn man ganz ungeniert, auch in den Unterfunktionen des VMM, ein kmalloc benutzen darf dürfte das sicher einige Sachen erleichtern. Dazu kommt das die Verwaltungsstrukturen für den VMM eben nur so viel Speicher belegen wie auch tatsächlich benötigt wird. Den Pointer zur Baumwurzel würde ich aber trotzdem in einem statischen Bereich packen (ist ja auch winzig) damit man immer schnell drauf zugreifen kann.

Du verwischst die Grenzen nicht vollständig, sondern implementierst schnittstellenfremde Durchgriffe durch die Ebenen, sodaß dein VMM den Slab Allocator kennt und dein Slab Allocator den VMM mit dem Ziel, dass dein VMM selbst Slabs zu seiner eigenen Verwaltung verwenden kann. Das ist nicht einfach, nicht sauber und führt zu Problemen, wenn du Teile davon austauschen möchtest.

Ja, es gibt eine zirkuläre Abhängigkeit wenn der Kernel-Heap den VMM benötigt und der VMM den Kernel-Heap benötigt aber das ist IMHO lösbar weil man die maximalen Bedürfnisse des VMM vom Heap pro VMM-Aufruf recht gut abschätzen kann.

Ob du nun nen eigenen ID-Raum für Threads hast oder nicht, du brauchst nur eine ID. Denn wenn du sagst das die Prozess und die Thread IDs nur 16bit groß sind (was für 32bit Systeme vollkomen ausreichend sein sollte) dann bildest du eine globale ID aus den beiden zusammen.

Das ist natürlich eine elegantere Lösung. Zwar kennt der Thread dann seine kernelinterne ID, aber es ist halt unwahrscheinlicher, dass er durch Rechenfehler plötzlich auf einen prozessfremden Thread zugreifen will. Darum ging es mir.

Also ich würde auch eher für einen einzelnen globalen ID-Raum plädieren. Wenn man mehrere davon hat kommt man eventuell irgendwann mal durcheinander und man hat auch noch doppelten (zumindest erhöhten) Speicherverbrauch. Was ein Programm mit der Thread-ID eines fremden Threads alles machen darf hängt von den Zugriffsrechten ab und ob ein bestimmter Thread zum aktuellem Prozess gehört sollte sich doch recht einfach feststellen lassen (im Thread-Descriptor-Struct steht bei mir die Prozess-ID des Besitzers).


Grüße
Erik

[FlashBurn]

Genau das möchte ich auch tun. Nur mit einer kleinen Abwandlung im SlabAllocator für die Heap-Objekte des Kernels, der SlabAllocator holt die doch immer aus einem (oder mehreren) großen Block und wenn dort der Platz fast aufgebraucht ist dann wird ein Flag gesetzt aber die Heap-Anforderung des VMM (z.B. nach einem neuen Baum-Element für die VMM-Verwaltungsstrukturen) trotzdem noch bedient (es ist ja noch ein kleiner Rest übrig). Wenn der VMM dann fertig ist mit seiner Arbeit sollte er als letztes den VMM-Lock abgeben (der VMM ist eine zentrale Ressource die IMHO nur einmal gleichzeitig benutzt werden kann) aber unmittelbar bevor der Lock freigegeben wird wird noch geprüft ob das Heap-SlabAllocator-NearEmpty-Flag gesetzt ist und dann für den SlabAllocator noch mal ein dicker Brocken alloziert, das kann gemacht werden weil der VMM von seiner eigentlichen Arbeit ja nicht mehr in einem kritischen Zustand ist. Mit diesem Trick kann ich den Kernel-Heap voll dynamisch verwalten und auch der VMM kann den Kernel-Heap benutzen um dort seine Verwaltungsstrukturen zu holen und trotzdem kann der Heap aus großen Blöcken vom VMM geholt werden. Der Heap würde also die Verwaltungsstrukturen die ihn beschreiben selber enthalten.

Sowas in der Art habe ich probiert und das hat auch funktioniert, bis ich zuviele CPUs (unter QEMU) hatte. Problem ist ja, das wenn du als VMM den SlabAllocator aufrufst und dein Objekt bekommst, wieder eine andere CPU den SlabAllocator aufrufen kann und da reicht dann so ein Flag nicht mehr aus (ich habe halt auch mit 255 CPUs getestet), weil bei zu vielen CPUs reichen die Objekte in einem Slab nicht mehr aus um alle CPUs bedienen zu können (vorallem nicht wenn du den SlabAllocator in seiner aktuellsten Abwandlung einsetzt).

[FlashBurn]

So ich habe mal etwas gecodet und ich bin noch nicht ganz mit meiner mapFree-Funktion zufrieden. Ich finde sie ist in dem Zustand zwar elegant geschrieben, aber der Algo ist nicht die schnellste Möglichkeit ein Segment/Bereich wieder freizugeben.

Optimierungen die mir schon bekannt sind (sparen Allocator- und Baumänderungs-Aufrufe):

• Anstatt jedes Mal die nodeStart aus dem Baum zu entfernen, wird sie drin gelassen und erst entfernt falls man 2mal mergen kann
• nodeSize kann auch einmal "behalten" werden und nur falls es schon eine Node mit der Größe gibt wird sie freigegeben

Erstmal der Code:

Code: [Auswählen]

uint32t mapFree(struct map_t *map, uint32t start, uint32t size) {
struct boundaryTag_t *tag= 0, *merge;
struct avlNode_t *nodeStart, *nodeSize;

if(unlikely(start < map->start || (start + size) > (map->start + map->size)))
goto error0;
//look if we can merge a segment before/after and look if the segment is used
spinAcquire(&map->lock);

nodeStart= map->freeStart;
//we first search for a segment after ours
while(likely(nodeStart)) {
merge= nodeStart->obj;
//is the start or the end in this segment
if(unlikely((start >= merge->start && start < (merge->start + merge->size)) || ((start + size) > merge->start && (start + size) < (merge->start + merge->size))))
goto error1;
//is our end == the start of the node segment
if(unlikely((start + size) == merge->start)) {
//we need to remove the original tag out of the size-tree
nodeSize= avlFind(map->freeSize,merge->size,&mapSizeComparatorVal);
//shouldn´t happen, just to be sure
if(unlikely(!nodeSize))
goto error1;

nodeSize->obj= listRemove((struct list_t *)nodeSize->obj,(struct list_t *)merge)
//look if we need to take the size-node out of the tree and free it
if(!nodeSize->obj) {
map->freeSize= avlDelete(nodeSize);
map->freeNode(nodeSize);
}
//get the start-node out of the tree and free it
map->freeStart= avlDelete(nodeStart);
map->freeNode(nodeStart);
//actualize the new segment, given size and set tag to the just merged tag
merge->start= start;
merge->size+= size;
size= merge->size;
tag= merge;

break;
}
//if our segment comes after the node segment then go right
if(start > merge->start)
nodeStart= nodeStart->right;
else
nodeStart= nodeStart->left;
}
//we found no segment after us for merging, now we search for a segment before us
nodeStart= map->freeStart;

while(likely(nodeStart)) {
merge= nodeStart->obj;
//is start == merge->start + merge->size
if(unlikely(start == (merge->start + merge->size))) {
//we need to remove the node segment out of the size-tree
nodeSize= avlFind(map->freeSize,merge->size,&mapSizeComparatorVal);
//shouldn´t happen, just to be sure
if(unlikely(!nodeSize))
goto error1;

nodeSize->obj= listRemove((struct list_t *)nodeSize->obj,(struct list_t *)merge)
//look if we need to take the size-node out of the tree and free it
if(!nodeSize->obj) {
map->freeSize= avlDelete(nodeSize);
map->freeNode(nodeSize);
}
//get the start-node out of the tree
map->freeStart= avlDelete(nodeStart);
//actualize the tag start, tag size, set nodeStart to our tag and free the merge tag
tag->start= merge->start;
tag->size+= merge->size;
nodeStart->obj= tag;
map->freeTag(merge);

break;
}
//if our segment comes after the node segment then go left
if(start > (merge->start + merge->size))
nodeStart= nodeStart->left;
else
nodeStart= nodeStart->right;
}
//if tag isn´t set, alloc a new one
if(!tag) {
if(unlikely(!(tag= map->allocTag())))
goto error1;

tag->start= start;
tag->size= size;
}
//if nodeStart isn´t set, alloc a new one
if(!nodeStart) {
if(unlikely(!(nodeStart= map->allocNode())))
goto error2

nodeStart->obj= tag;
}
//look for a node with the same size
nodeSize= avlFind(map->freeSize,size,&mapSizeComparatorVal);
//insert the tag into the size-tree
if(!nodeSize) {
if(unlikely(!(nodeSize= map->allocNode())))
goto error3;

nodeSize->obj= listAddFirst((struct list_t *)tag);

map->size= avlInsert(map->size,nodeSize,&mapSizeComparatorNode);
} else {
nodeSize->obj= listAddTail((struct list_t *)nodeSize->obj,(struct list_t *)tag);
}
//now insert the tag into the start-tree
map->freeStart= avlInsert(map->freeStart,nodeStart,&mapStartComparatorNode);
end0:
spinRelease(&map->lock);

return 1;
error3:
map->freeNode(nodeStart);
error2:
map->freeTag(tag);
error1:
spinRelease(&map->lock);
error0:
return 0;
}

Ich hoffe die Funktionsaufrufe sind selbsterklärend, wenn nicht fragen.

Ich hätte jetzt gerne gewusst ob noch jemand ne Optimierung des Algos einfällt. Blöd ist halt das der Baum zweimal durchgegangen werden muss (einmal um nach einem Bereich vor uns und einmal um nach einem Bereich nach uns zu suchen mit dem wir mergen können) und wie schon gesagt, die zuvielen Allocator-Aufrufe.

Es kann auch sein das noch Fehler drin sind, ich habe den Code noch nicht getestet!

[Svenska]

Hallo,

(a) Der VMM reserviert sich selbst keinen Speicher dynamisch.

Das bedeutet das der VMM nur eine begrenzte Anzahl an Speicherblöcken verwalten kann und ist IMHO damit nicht mal für Mikrocontroller einsetzbar.

Richtig. Man kann das allerdings etwas aufweichen, indem man "so gut wie nie" eine Veränderung zulässt, beispielsweise durch Erzeugen eines neuen Arrays und anschließendem Umkopieren. Tritt das "hinreichend selten" (sehr konkret, ich weiß) auf, stört das auch nicht zu stark. Währenddessen steht natürlich die komplette Speicherverwaltung.

(b) Der VMM reserviert sich Speicher nicht über den VMM.

Das bedeutet das es mehrere unabhängige Allozierungsechanismen geben muss und das halte ich für ungeschickt.

Warum? Wenn du sauberes Layering machst, dann hast du einen PMM, der vom VMM als Allocator genutzt wird - und zwar sowohl für die oberen Schichten als auch für sich selbst. Du brauchst in jedem Fall zwei Mechanismen, um Kreisabhängigkeiten zu vermeiden.

In diesem Augenblick darf der VMM niemals beim Slab Allocator nach Objekten für sich selbst fragen, denn das wäre unzulässiges Layering und eine zirkuläre Abhängigkeit.

Du meinst also das der VMM niemals ein kmalloc benutzen darf? Das würde bedeuten Du musst extra/exklusiv für den VMM was spezielles bauen das diese Funktionalität anbietet. Wie gesagt, das halte ich für ungeschickt wegen dem doppeltem Code und wenn man ganz ungeniert, auch in den Unterfunktionen des VMM, ein kmalloc benutzen darf dürfte das sicher einige Sachen erleichtern. Dazu kommt das die Verwaltungsstrukturen für den VMM eben nur so viel Speicher belegen wie auch tatsächlich benötigt wird. Den Pointer zur Baumwurzel würde ich aber trotzdem in einem statischen Bereich packen (ist ja auch winzig) damit man immer schnell drauf zugreifen kann.

Jein. Der VMM darf kein kmalloc() benutzen, weil er ein kmalloc() implementieren soll. Du musst aber trotzdem nichts spezielles bauen, denn dein virtueller Speichermanager baut auf dem physischen Speicherverwalter auf und kann diesen auch selbst benutzen. Ich sehe keine besondere Einschränkung, wenn im VMM nur ein getPhysMem() existiert, was nur ganze Pages bereitstellen kann. Mit virtuellen Adressen kannst du im VMM ohnehin nichts anfangen, weil du diese ja erst bereitstellst.

Warum sollte der VMM selbst einen VMM nutzen müssen?

Du verwischst die Grenzen nicht vollständig, sondern implementierst schnittstellenfremde Durchgriffe durch die Ebenen, sodaß dein VMM den Slab Allocator kennt und dein Slab Allocator den VMM mit dem Ziel, dass dein VMM selbst Slabs zu seiner eigenen Verwaltung verwenden kann. Das ist nicht einfach, nicht sauber und führt zu Problemen, wenn du Teile davon austauschen möchtest.

Ja, es gibt eine zirkuläre Abhängigkeit wenn der Kernel-Heap den VMM benötigt und der VMM den Kernel-Heap benötigt aber das ist IMHO lösbar weil man die maximalen Bedürfnisse des VMM vom Heap pro VMM-Aufruf recht gut abschätzen kann.

Und sich dann, wenn man nicht genau aufpasst, unglaublich viele Race Conditions und Abhängigkeiten ins Haus holt.

Ich hoffe die Funktionsaufrufe sind selbsterklärend, wenn nicht fragen.

Was ist unlikely() ? Das habe ich schon öfter gesehen und kann mir darunter garnichts vorstellen...

Es kann auch sein das noch Fehler drin sind, ich habe den Code noch nicht getestet!

Schaue ich mir eventuell nachher an, ist aber Praxis und die kann ich nicht.

Gruß,
Svenska

[FlashBurn]

Jein. Der VMM darf kein kmalloc() benutzen, weil er ein kmalloc() implementieren soll. Du musst aber trotzdem nichts spezielles bauen, denn dein virtueller Speichermanager baut auf dem physischen Speicherverwalter auf und kann diesen auch selbst benutzen. Ich sehe keine besondere Einschränkung, wenn im VMM nur ein getPhysMem() existiert, was nur ganze Pages bereitstellen kann. Mit virtuellen Adressen kannst du im VMM ohnehin nichts anfangen, weil du diese ja erst bereitstellst.

Was macht denn ein kmalloc()? Der weiß wieviel Speicher er noch hat und wenn dieser nicht mehr reicht dann wird der VMM aufgerufen. Also müsste auch ein kmalloc() was vom VMM implementiert (hört sich doof an und weiß auch nicht so richtig was du damit meinst) ist den VMM aufrufen.
Desweiteren kannst du ja so nicht mal eben deinen kmalloc() austauschen und das ist ja auch doof.

Warum sollte der VMM selbst einen VMM nutzen müssen?

Woher soll denn der VMM wissen welche virtuellen Bereiche frei sind und welche nicht, wenn er es nicht irgendwo speichert? Um diese Infos irgendwo zu speichern, brauchst du Speicher (virtuellen und physischen). Um das ganze möglichst flexibel zu machen, sollte man nicht immer schon den ganzen Speicher für den worst-case allokieren (dann würde dein OS sehr sehr viel Speicher brauchen um nur starten zu können und zur Laufzeit wird das pro Prozess immer und immer mehr).
Also muss der VMM die Möglichkeit haben nur Objekte zu allokieren und dafür kann es (und wird es) notwendig sein das du nen freien virtuellen Bereich brauchst und dafür brauchst du wieder den VMM.

Was ist unlikely() ? Das habe ich schon öfter gesehen und kann mir darunter garnichts vorstellen...

Sorry, wenn ich mal so treist frage, aber kannst du englisch?

Likely = Wahrscheinlich
Unlikely = Unwahrscheinlich

Das sind Makros um dem Compiler mehr Infos zum Optimieren zu geben, da ich ja besser als er weiß welche Pfade wahrscheinlicher sind als andere.

Schaue ich mir eventuell nachher an, ist aber Praxis und die kann ich nicht.

Das ist immer schlecht. Ich (persönlich) finde ja das man nur mit Praxis weiter kommt als nur mit Theorie!

[Svenska]

...

Die Übersetzung von likeley/unlikely ist mir schon klar, vielen Dank für dein Verständnis. Es gibt aber keine manpage dazu, und wenn es ein Compiler-Makro ist, dann sieht man dem Ding eben nicht an. Und meine C-Kenntnisse sind C-Kenntnisse, keine gcc-Kenntnisse. Vielen Dank.

Zum Rest: Du verstehst nicht, was ich meine, wenn ich sage, dass der VMM den VMM nicht aufrufen darf.

Jein. Der VMM darf kein kmalloc() benutzen, weil er ein kmalloc() implementieren soll. Du musst aber trotzdem nichts spezielles bauen, denn dein virtueller Speichermanager baut auf dem physischen Speicherverwalter auf und kann diesen auch selbst benutzen. Ich sehe keine besondere Einschränkung, wenn im VMM nur ein getPhysMem() existiert, was nur ganze Pages bereitstellen kann. Mit virtuellen Adressen kannst du im VMM ohnehin nichts anfangen, weil du diese ja erst bereitstellst.

Was macht denn ein kmalloc()? Der weiß wieviel Speicher er noch hat und wenn dieser nicht mehr reicht dann wird der VMM aufgerufen. Also müsste auch ein kmalloc() was vom VMM implementiert (hört sich doof an und weiß auch nicht so richtig was du damit meinst) ist den VMM aufrufen.

Nein.
void *kmalloc(size_t size, int flags) alloziiert Speicher der Größe size, wobei flags angibt, ob es User-/Kernel-/Interrupthandler-Speicher ist. So steht es hier zumindest.

Wo implementierst du denn dein kmalloc()? In der Userspace-C-Library? Wahrscheinlich nicht.

Zumindest in meinem Kopf ist das ein Dreischichtenmodell: physischer Speicher, virtueller Speicher, Objekte. Die bauen aufeinander auf, aber nicht umgekehrt.

(a) Der physische Speicherverwalter (ab hier PMM) nimmt physischen Speicher, arbeitet mit physischen Adressen und kann nur PAGESIZE-große (=4k, 2M, 4M, ...) Blöcke verwalten. Diese Blöcke sind also physische Speicherblöcke mit RAM dahinter.

(b) Der virtuelle Speicherverwalter (ab hier VMM) nimmt diese physischen Speicherblöcke, die ihm vom PMM zur Verfügung gestellt wurden und verwaltet die. Er implementiert ein kmalloc(). Er darf kmalloc() niemals aufrufen. Wenn er für sich selbst Speicher braucht, muss er den PMM danach fragen und kann auch nur physische Speicherblöcke für sich selbst verwenden. Diesen Blöcken darf er gerne virtuelle Adressen geben und damit weiterarbeiten.

(c) Der Slab-Allocator sitzt oben auf dem VMM drauf und verwaltet Objekte. Er darf kmalloc() benutzen und mit dem Speicher tun, was immer er möchte.

Tut mir ja Leid, wenn dein VMM in dem Schema den Slab-Allocator nicht benutzen darf. Der PMM darf den VMM auch nicht benutzen.

Desweiteren kannst du ja so nicht mal eben deinen kmalloc() austauschen und das ist ja auch doof.

Warum? Ein kmalloc() ist eng mit der Speicherverwaltung verbunden, wird also vom VMM bereitgestellt. Du kannst kmalloc() nicht vom VMM trennen, ohne zirkuläre Abhängigkeiten und damit Extra-Codepfade zu bekommen.

Warum sollte der VMM selbst einen VMM nutzen müssen?

Woher soll denn der VMM wissen welche virtuellen Bereiche frei sind und welche nicht, wenn er es nicht irgendwo speichert?

Warum sollte der VMM selbst einen VMM nutzen müssen? Ich wiederhole die Frage gerne nochmals. Er ist der VMM. Er ruft ihn nicht auf. Er ist es.

Um diese Infos irgendwo zu speichern, brauchst du Speicher (virtuellen und physischen). Um das ganze möglichst flexibel zu machen, sollte man nicht immer schon den ganzen Speicher für den worst-case allokieren (dann würde dein OS sehr sehr viel Speicher brauchen um nur starten zu können und zur Laufzeit wird das pro Prozess immer und immer mehr).

Du brauchst, um Daten speichern zu können, in erster Linie physischen Speicher. Den kriegst du vom PMM. Um daraus virtuellen Speicher zu machen, wirst du den VMM nicht aufrufen, denn das kannst du selbst (du bist der VMM).

Also muss der VMM die Möglichkeit haben nur Objekte zu allokieren und dafür kann es (und wird es) notwendig sein das du nen freien virtuellen Bereich brauchst und dafür brauchst du wieder den VMM.

Warum sollte der VMM den VMM aufrufen, wenn er es doch selber kann?

Schaue ich mir eventuell nachher an, ist aber Praxis und die kann ich nicht.

Das ist immer schlecht. Ich (persönlich) finde ja das man nur mit Praxis weiter kommt als nur mit Theorie!

Tut mir Leid, dass ich derzeit  kein OS auf die Beine stelle. Ich habe dazu weder Zeit noch Lust, dennoch Interesse daran.

Gruß,
Svenska

[FlashBurn]

void *kmalloc(size_t size, int flags) alloziiert Speicher der Größe size, wobei flags angibt, ob es User-/Kernel-/Interrupthandler-Speicher ist.

Ein kmalloc ist nichts anderes als ein malloc! Der einzige Unterschied ist, das er im Kernel benutzt wird.

Der physische Speicherverwalter (ab hier PMM) nimmt physischen Speicher, arbeitet mit physischen Adressen und kann nur PAGESIZE-große (=4k, 2M, 4M, ...) Blöcke verwalten. Diese Blöcke sind also physische Speicherblöcke mit RAM dahinter.

Wo läuft der Code des PMM und wo speichert der PMM seine Daten?

Der virtuelle Speicherverwalter (ab hier VMM) nimmt diese physischen Speicherblöcke, die ihm vom PMM zur Verfügung gestellt wurden und verwaltet die. Er implementiert ein kmalloc(). Er darf kmalloc() niemals aufrufen. Wenn er für sich selbst Speicher braucht, muss er den PMM danach fragen und kann auch nur physische Speicherblöcke für sich selbst verwenden. Diesen Blöcken darf er gerne virtuelle Adressen geben und damit weiterarbeiten.

Woher weiß der VMM welche virtuelle Adresse frei ist? Nach deinem Verständnis ist virtuelle Adresse == physischer Adresse. Dem ist aber fast nie so, dafür gibt es ja Paging und genau deswegen braucht man ja einen PMM und einen VMM.

Der Slab-Allocator sitzt oben auf dem VMM drauf und verwaltet Objekte. Er darf kmalloc() benutzen und mit dem Speicher tun, was immer er möchte.

Warum sollte der SlabAllocator kmalloc() benutzen? Der SlabAllocator holt sich seinen Speicher vom VMM und nur mal so, in Linux steckt hinter dem kmalloc() der SlabAllocator.

Warum? Ein kmalloc() ist eng mit der Speicherverwaltung verbunden, wird also vom VMM bereitgestellt. Du kannst kmalloc() nicht vom VMM trennen, ohne zirkuläre Abhängigkeiten und damit Extra-Codepfade zu bekommen.

Sorry, aber du hast nicht verstanden was ein kmalloc() ist und was es macht. Genauso weißt du eigentlich nicht was ein VMM macht und wie Paging funktioniert.

Tut mir Leid, dass ich derzeit  kein OS auf die Beine stelle. Ich habe dazu weder Zeit noch Lust, dennoch Interesse daran.

Naja, der Code hat erstmal gar nichts mit einem OS zu tun und ich bin daher davon ausgegangen das du theoretisch was vom Programmieren weißt, es aber praktisch noch nicht wirklich gemacht hast.

Der Code verwendet im Endeffekt einfach nur 2 Bäume um seine Daten zu organisieren und dafür muss man sich nicht mal im entferntesten mit einem OS beschäftigt habe.

[Svenska]

Ein kmalloc ist nichts anderes als ein malloc! Der einzige Unterschied ist, das er im Kernel benutzt wird.

Richtig.

Wo läuft der Code des PMM und wo speichert der PMM seine Daten?

Der PMM wird seine Daten höchstwahrscheinlich im physischen RAM speichern... und der VMM hat sicherzustellen, dass der PMM auch weiß, wo das im virtuellen Adressraum ist (dieser Bereich kann 1:1 gemappt werden).

Woher weiß der VMM welche virtuelle Adresse frei ist?

Er ist der VMM, er kümmert sich um die Verwaltung des virtuellen Speichers. Also weiß er, wo da im Adressraum etwas frei ist...

Nach deinem Verständnis ist virtuelle Adresse == physischer Adresse. Dem ist aber fast nie so, dafür gibt es ja Paging und genau deswegen braucht man ja einen PMM und einen VMM.

Ist mir klar. Der PMM kümmert sich um die physischen Adressen, der VMM kümmert sich um die Umrechnung von physischen Adressen in virtuelle Adressen und die Steuerung der MMU. Und für die Speicherbereiche des PMM kann man das 1:1-Mapping garantieren, da es sich um elementare (und recht kleine) Strukturen handelt.

Der Slab-Allocator sitzt oben auf dem VMM drauf und verwaltet Objekte. Er darf kmalloc() benutzen und mit dem Speicher tun, was immer er möchte.

Warum sollte der SlabAllocator kmalloc() benutzen? Der SlabAllocator holt sich seinen Speicher vom VMM und nur mal so, in Linux steckt hinter dem kmalloc() der SlabAllocator.

Man kann beides auch trennen.

Ich hatte überlegt, die Dinger anders zu bezeichnen, mit getPhysMem(), was vom PMM bereitgestellt wird, getVirtMem(), was vom VMM bereitgestellt wird und kmalloc(), was vom Slab-Allocator bereitgestellt wird. Das ist aber nur eine Lösung. Du kannst das kmalloc() auch vom VMM bereitstellen, und einen Slab-Allocator oben draufsetzen - das war mein Ausgangspunkt. Oder du kannst Slab-Allocator und VMM gemeinsam, monolithisch, implementieren - dann ist kmalloc() der Slab-Allocator, der als darunterliegende Schicht den PMM direkt benutzt. Der Slab-Allocator wäre somit identisch dem VMM.

Warum? Ein kmalloc() ist eng mit der Speicherverwaltung verbunden, wird also vom VMM bereitgestellt. Du kannst kmalloc() nicht vom VMM trennen, ohne zirkuläre Abhängigkeiten und damit Extra-Codepfade zu bekommen.

Sorry, aber du hast nicht verstanden was ein kmalloc() ist und was es macht. Genauso weißt du eigentlich nicht was ein VMM macht und wie Paging funktioniert.

Wie Paging funktioniert, ist mir durchaus klar. Was kmalloc() tut, ist mir auch klar. Dazwischen liegt eine Speicherverwaltung, und wie man die implementiert, ist relativ frei... ich habe halt eine Vorstellung davon, wie man das tun kann. Du tust das offensichtlich anders. Kein Grund, mir Inkompetenz vorzuwerfen.

Tut mir Leid, dass ich derzeit kein OS auf die Beine stelle. Ich habe dazu weder Zeit noch Lust, dennoch Interesse daran.

Naja, der Code hat erstmal gar nichts mit einem OS zu tun und ich bin daher davon ausgegangen das du theoretisch was vom Programmieren weißt, es aber praktisch noch nicht wirklich gemacht hast.
Der Code verwendet im Endeffekt einfach nur 2 Bäume um seine Daten zu organisieren und dafür muss man sich nicht mal im entferntesten mit einem OS beschäftigt habe.

Ich habe seit dem Abitur keine binären Baumstrukturen mehr gebraucht oder verwendet. Das ist inzwischen über 3 Jahre her. Außerdem habe ich sie damals nur in Delphi umgesetzt, nicht in C und die Compilerinterna vom gcc kenne ich auch nicht. Ich nutze einen "Compiler" und für Sachen, die sich auf stdio beschränken, brauche ich keinerlei Erweiterungen. Außerdem bin ich auf Arbeit und habe nebenher noch andere Dinge zu tun. Code analysieren kostet halt Zeit.

Zumal ich mich nie groß mit Optimierungen auseinandergesetzt habe (maximal QuickSort fürs Abi) und durch deinen Code steige ich spontan ebenfalls nicht durch.

Lässt sich das Mergen nicht durchführen, indem du den Baum mit den Adressen als Suchschlüssel stupide in-order traversierst und, wenn du deine freizugebende Adresse findest, das vorhergehende und das nachfolgende Element vergleichst? (Die drei Elemente fallen beim Traversieren eh raus.) Wenn du bei jeder Freigabe jeweils deinen Block mit dem vorhergehenden und nachfolgendem Block zusammenfügst (sofern möglich), brauchst du nicht den gesamten Baum durchsuchen, sondern nur diese drei Blöcke und die Wege dazwischen und du hast trotzdem die größtmöglichen Blöcke.

Gruß,
Svenska

[FlashBurn]

Er ist der VMM, er kümmert sich um die Verwaltung des virtuellen Speichers. Also weiß er, wo da im Adressraum etwas frei ist...

Und wo speichert er diese Infos? Die nächste Frage wäre dann woher er den Speicher bekommt das er diese Infos Speichern kann.
Wie gesagt, alles im Vorraus zu allokieren ist nicht praktikabel.

der VMM kümmert sich um die Umrechnung von physischen Adressen in virtuelle Adressen

Nicht wirklich, das macht die MMU, wie du dann weiterschreibst steuert der VMM die MMU. Die eigentliche Aufgabe des VMM ist es, zu wissen welche Bereiche, in einem Adressraum, noch frei sind.

Also gut nur mal so als Bsp. wie ein Pseudo-Code von einem malloc() aussehen könnte:

Code: [Auswählen]

void *malloc(uint32t size) {
 void *addr= guckeObFreierBlockVorhanden(size + 4); //man kann das in einer Liste machen

 if(!addr) {
  void *newMem= vmmGetVirtMem((size + 3 & ~0xFFF) + 0x1000); //das in der Klammer aligned size+4 auf Page-Größe
  packeNeuenSpeicherBlockInList(newMem);
  addr= guckeObFreierBlockVorhanden(size);
 }

 *((uint32t *)addr)= size; //ich merke mir wie groß der rausgegebene Block ist

 return addr + 4; //und gebe die Addr auf den eigentlichen Speicher an den User weiter
}

Der malloc()-Code hat in dem Sinne erstmal gar nichts mit dem VMM zu tun, sondern er benutzt ihn. Wenn du als User mit 4KB-Pages an Speicher klarkommst, könntest du auch malloc() gar nicht benutzen. malloc() ermöglicht dir einfach das du dich nicht darum kümmern brauchst.

Der SlabAllocator funktioniert ähnlich, auch er holt sich immer ein vielfaches der Page-Größe vom VMM (was anderes bekommst du auch nicht und das ist der Unterschied zu malloc()) und gibt dann einen Pointer auf ein freies Objekt raus, hat auch nichts mit dem VMM zu tun.

Kein Grund, mir Inkompetenz vorzuwerfen.

Sorry, aber nachdem was du geschrieben hast, hast du halt nicht verstanden wie das normalerweise so miteinander funktioniert.

Außerdem bin ich auf Arbeit und habe nebenher noch andere Dinge zu tun. Code analysieren kostet halt Zeit.

Du darfst auf Arbeit nebenbei surfen

Ich meinte damit auch gar nicht das du den Code schnell mal analysieren sollst. Es ging mir darum, das nur weil ich den Code in meinem OS verwende, muss man sich nicht mit OS Programmierung auskennen, um den Code zu verstehen.

Ich kann mir mit der folgenden Aussage jetzt ziemlichen Ärger einhandeln, aber was solls

Ich denke als Programmierer sollte man schon so grundlegende Datenstrukturen wie Bäume (auch ausgeglichene) kennen. Ich weiß nun nicht ob du beruflich programmierst oder nicht (wenn nicht dann schiebe ich das jetzt mal auf noch keine Erfahrung), aber Bäume gibt es schon ziemlich lange
Auch ist es keine Ausrede in welcher Sprache du das mal geschrieben hast, wer programmieren kann, dem ist die Sprache (nicht das Paradigma!) egal.

und die Compilerinterna vom gcc kenne ich auch nicht.

Ich denke mal du spielst auf likely/unlikely an? Ich hab mal "gcc likely" bei google eingegeben und gleich die ersten beiden Ergebnisse waren dahingehend sehr hilfreich

Lässt sich das Mergen nicht durchführen, indem du den Baum mit den Adressen als Suchschlüssel stupide in-order traversierst und, wenn du deine freizugebende Adresse findest, das vorhergehende und das nachfolgende Element vergleichst? (Die drei Elemente fallen beim Traversieren eh raus.) Wenn du bei jeder Freigabe jeweils deinen Block mit dem vorhergehenden und nachfolgendem Block zusammenfügst (sofern möglich), brauchst du nicht den gesamten Baum durchsuchen, sondern nur diese drei Blöcke und die Wege dazwischen und du hast trotzdem die größtmöglichen Blöcke.

Ich bin mir jetzt nicht sicher ob ich dich verstanden habe, aber in einem Baum muss das vorhergehende (der Vater) Element (Node) nicht auch der Vorgänger sein!

Du bringst mich allerdings auf die Idee, das ich gleichzeitig gucken kann, ob ich einen Bereich am Ende oder am Anfang gefunden habe, mit dem ich mergen kann (das mach ich momentan in 2 Baum-Traversierungen). Denn wenn ich eins gefunden haben kann der eventuell andere Bereich nur noch in den Kind-Knoten davon liegen. Damit würde ich mir eine weitere Traversierung sparen.