Thema: Allgemeiner Ressourcen-Allocator

[Svenska]

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.

Der PMM kann Speicher bereitstellen und funktioniert auch ohne VMM und ohne Paging. Also bezieht der VMM seinen Speicher vom PMM und setzt das Mapping selbst auf.

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.

Die Umrechnung macht die MMU, aber das Mapping wird vom VMM aufgebaut. Ebenso die Verwaltung, welcher Speicher wo wie gemappt ist (sofern benötigt) und was wo frei ist.

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

Jo, so kann man das machen.

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.

Richtig. Damit implementierst du malloc() nicht im VMM, sondern eine Ebene darüber, auf der gleichen Ebene wie z.B. den Slab Allocator.

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.

Es sei denn, du implementierst deinen VMM so, dass er ein malloc() bereitstellt und eben nicht mit Pagegrößen arbeitet, sondern mit Speicherblöcken variabler Größe umgehen kann.

Kein Grund, mir Inkompetenz vorzuwerfen.

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

Ich mache mir die Welt, widewidewie sie mir gefällt... ich hätte das halt anders gelöst.

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

Ist "nur" ein Praktikum. Und wenn der Chef überarbeitet ist und ich nichts zu tun habe, dann ergibt sich das halt...

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.

Wenn man den Code hat und relativ wenig Kontext dazu (Dokumentation!) und aus dem Code rauspopeln muss, wie die Datenstrukturen aussehen, ohne ihn ausführen und nachschauen zu können, dann ist das recht schwer, wenn man den Code nicht geschrieben hat oder nicht so sehr in der Thematik drin ist.

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

Ich programmiere hauptsächlich sowas, sowas oder sowas. Das ist ein bisschen simpler.

Ich kenne einfache binäre Suchbäume und eine Möglichkeit, diese auszugleichen. Sich selbst ausgleichende Bäume (wie z.B. der von dir verwendete AVL-Baum) sind mir vom Prinzip her bekannt, jedoch nicht von der Implementierung. (Ich könnte mir das schon selbst implementieren, aber eben nicht aus dem Effeff.)

Auch ist es keine Ausrede in welcher Sprache du das mal geschrieben hast, wer programmieren kann, dem ist die Sprache (nicht das Paradigma!) egal.

Das ist korrekt. Und Delphi/C sind nicht die einzigen Programmiersprachen, in denen ich programmieren kann. Es ist aber ein Unterschied, wenn du gewisse Paradigmen vor Jahren in einer Programmiersprache letztmalig angefasst hast, das ewig nicht benutzt hast und dann von dir erwartet wird, das spontan hochzuhusten. Das kann ich nicht.

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

Ich habe "man likely" und "man unlikely" eingegeben und anschließend dein Angebot für Nachfragen angenommen...

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

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!

Das meinte ich nicht.

Wenn du InOrder-Traversierst, dann bekommst du die Einträge des Baumes in sortierter Reihenfolge, bei entsprechender Strukturierung also den Adressraum von Null bis Ende. Da du nur aufeinanderfolgende Bereiche mergen kannst, brauchst du also deinen Suchschlüssel, das vorhergehende und das nachfolgende Element - also speicherst du immer das aktuelle und die beiden letzten Elemente extra ab und traversierst exakt einmal mehr, als du für das Finden brauchst und brichst dann ab.

Damit hast du das "Suchschlüssel+1" (das aktuelle), "Suchschlüssel" (das letzte) und "Suchschlüssel-1" (das vorletzte) Element gleichzeitig aus dem Baum gepopelt und brauchst nur nachschauen, ob diese auch aufeinander folgen (dann sind sie mergebar) oder nicht.

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.

Ist mir spontan zu hoch, klingt aber für mich falsch. Der "hintere" Bereich liegt immer hinter dem "vorderen" Bereich. Da du die Bäume balanciert hältst, kann der hintere Bereich auch im anderen Zweig liegen und nicht in einem Kindknoten, nämlich dann, wenn dein Suchwort in irgendeinem Zweig bereits das rechteste Element ist.

Gruß,
Svenska

[FlashBurn]

Der PMM kann Speicher bereitstellen und funktioniert auch ohne VMM und ohne Paging. Also bezieht der VMM seinen Speicher vom PMM und setzt das Mapping selbst auf.

Das klappt aber nur, wenn du vorher weißt wieviel RAM du verwalten musst und du dann deine Datenstrukturen schon im vorraus reservierst (so mache ich das auch, ich wüsste auch nicht wie man es anders lösen sollte).

Es sei denn, du implementierst deinen VMM so, dass er ein malloc() bereitstellt und eben nicht mit Pagegrößen arbeitet, sondern mit Speicherblöcken variabler Größe umgehen kann.

Könntest du denn nicht mal pseudo-Code schreiben, so wie du dir das vorstellst. Denn egal wie ich das drehe oder wende es läuft immer darauf hinaus, das du nen vmmAllocMem(uint32t size) zur Verfügung stellst und diese Funktion wird halt irgendeine Funktion aus deinem VMM aufrufen wo sie mehr Speicher bekommt (Page-Größe), weil der VMM kann auch nur Page-Größe verwalten, weil die MMU nichts anderes zulässt.
In dem Sinne ist das auch losgelöst vom VMM, ich weiß gerade nicht so richtig was du damit meinst das der VMM auch ein malloc() implementieren soll.

Der Punkt ist einfach, das du die Zirkularität nicht raus bekommst.

Wenn man den Code hat und relativ wenig Kontext dazu (Dokumentation!) und aus dem Code rauspopeln muss, wie die Datenstrukturen aussehen, ohne ihn ausführen und nachschauen zu können, dann ist das recht schwer, wenn man den Code nicht geschrieben hat oder nicht so sehr in der Thematik drin ist.

Stimmt schon. Mir ging es auch nur darum wie ich die Suche in einem Baum nach einem Bereich bzw. 2 Elementen gleichzeitig und effizient machen kann.

Ich programmiere hauptsächlich sowas, sowas oder sowas. Das ist ein bisschen simpler.

Darf ich also annehmen das du in Magdeburg studierst? Da habe ich auch angefangen zu studieren (jetzt bin ich woanders)

Wenn du InOrder-Traversierst, dann bekommst du die Einträge des Baumes in sortierter Reihenfolge, bei entsprechender Strukturierung also den Adressraum von Null bis Ende. Da du nur aufeinanderfolgende Bereiche mergen kannst, brauchst du also deinen Suchschlüssel, das vorhergehende und das nachfolgende Element - also speicherst du immer das aktuelle und die beiden letzten Elemente extra ab und traversierst exakt einmal mehr, als du für das Finden brauchst und brichst dann ab.

Damit hast du das "Suchschlüssel+1" (das aktuelle), "Suchschlüssel" (das letzte) und "Suchschlüssel-1" (das vorletzte) Element gleichzeitig aus dem Baum gepopelt und brauchst nur nachschauen, ob diese auch aufeinander folgen (dann sind sie mergebar) oder nicht.

Da mir gerade klar wird was du mit InOrder-Traversierung meinst, kann ich nur sagen, das ist nicht im Zwecke des Erfinders

Der Vorteil eines Baums ist ja das du gerade nicht alle Elemente anfassen musst, wenn du was bestimmtes suchst und du willst ja ne Art Liste machen (das wäre das Ergebnis der InOrder-Traversierung).

Mir ist gestern Abend dann noch die entscheidene Idee gekommen.

In meinem aktuellen Code ist auch noch ein Fehler. Denn ich muss den Baum immer bis zu einem Ende durchlaufen, ansonsten kann ich nicht sicher sein das ich nicht gerade einen "illegalen" Bereich freigeben möchte.

Ich habe mir das so vorgestellt das ich 2 Pointer habe *before und *behind, die auf Baum-Knoten zeigen können.
Ich gehe halt den Baum von der Wurzel an durch und überprüfe jeden Knoten darauf, ob der Bereich sich irgendwie mit dem freizugebenden überschneidet (wenn ja, dann wird ein Fehler zurückgegeben). Desweiteren wird jeder Knoten darauf überpüft ob der Bereich da drinnen sich mit dem freizugebenden irgendwie angrenz (deswegen before und behind) und wenn das der Fall ist, wird der entsprechende Pointer auf diese Node zeigen.
Ich gehe dann den Baum noch bis zu einem Ende durch um sicher zu sein, das der Bereich auch freigegeben werden darf.

Wenn ich dann mit der Schleife durch bin, brauche ich einfach nur 3 Fälle unterscheiden:

• beide Pointer sind NULL
• nur *before ist NULL
• nur *behind ist NULL

Und schon gehe ich den Baum nur noch einmal anstatt zweimal durch und ich kann dann auch ganz leicht sagen welche "struct avlNode_t" und "struct boundaryTag_t" ich freigeben kann und kann mir so unnötig Allocator-Aufrufe sparen.

Ich denke das sollte das Optimum sein was man rausholen kann und eine Halbierung im worst-case sollte nicht schlecht sein.

[Svenska]

Hallo,

Der PMM kann Speicher bereitstellen und funktioniert auch ohne VMM und ohne Paging. Also bezieht der VMM seinen Speicher vom PMM und setzt das Mapping selbst auf.

Das klappt aber nur, wenn du vorher weißt wieviel RAM du verwalten musst und du dann deine Datenstrukturen schon im vorraus reservierst (so mache ich das auch, ich wüsste auch nicht wie man es anders lösen sollte).

Solange die RAM-Größe sich nicht im Betrieb ändert, erhältst du die zu verwaltende RAM-Größe (physisch) vom BIOS bzw. einer Probe-Funktion deiner Wahl. Ich weiß nicht, worauf du hinaus möchtest. Der PMM bekommt die RAM-Größe mitgeteilt und gibt diese Information an den VMM weiter, der daraufhin seine Datenstrukturen anlegt.

Es sei denn, du implementierst deinen VMM so, dass er ein malloc() bereitstellt und eben nicht mit Pagegrößen arbeitet, sondern mit Speicherblöcken variabler Größe umgehen kann.

Könntest du denn nicht mal pseudo-Code schreiben, so wie du dir das vorstellst.

Nein, denn dazu müsste ich solchen Code zumindest real mal angefasst haben...

Denn egal wie ich das drehe oder wende es läuft immer darauf hinaus, das du nen vmmAllocMem(uint32t size) zur Verfügung stellst und diese Funktion wird halt irgendeine Funktion aus deinem VMM aufrufen wo sie mehr Speicher bekommt (Page-Größe), weil der VMM kann auch nur Page-Größe verwalten, weil die MMU nichts anderes zulässt.
In dem Sinne ist das auch losgelöst vom VMM, ich weiß gerade nicht so richtig was du damit meinst das der VMM auch ein malloc() implementieren soll.

Ich verstehe dein Problem. In meiner Welt besteht der VMM aus zwei Teilen, einmal einem auf Page-Größen basierendem System zur Verwaltung der MMU, zum anderen aus einem System zur Verwaltung der Blockgrößen (aller Speicherblöcke) in einem zentralen Register.

In deinem Pseudocode speicherst du die Informationen zu jedem Speicherblock (die Größe) direkt vor den Speicherblock, das heißt es gibt kein zentrales Register, damit fällt auch die gesamte Funktionalität aus dem VMM heraus. Bei dir gibt es damit einen VMM, der nur Pagegrößen kennt und damit arbeitet, und darüber den Slab-Allocator, welcher malloc() implementiert.

Da ich vor diesem Thread mit einem Slab-Allocator nichts anfangen konnte, gab es bei mir keine Slabs, und damit musste die Verwaltung von beliebig großen Speicherblöcken (die malloc()-Implementierung) woanders erledigt werden. Für meine Welt im VMM.

Der Punkt ist einfach, das du die Zirkularität nicht raus bekommst.

Doch, wenn du nämlich dem VMM verbietest, den VMM zu nutzen. Das heißt, dass der VMM kein allgemeines malloc() benutzen darf, da er es entweder selbst implementiert (ich) oder die malloc()-Implementation einen VMM voraussetzt.

Wenn der VMM nur mit Pages arbeitet, so darf er halt nur Pages für seine interne Verwaltung nutzen. Das ist eine Einschränkung, aber das vermeidet zirkuläre Abhängigkeiten. Der VMM implementiert also nur ein getVirtMem(int size) mit size = n*PAGESIZE.

Stimmt schon. Mir ging es auch nur darum wie ich die Suche in einem Baum nach einem Bereich bzw. 2 Elementen gleichzeitig und effizient machen kann.

Und genau das ist ein Optimierungsproblem. Dazu müsstest du einen Informatiker fragen. Ich bin keiner.

Darf ich also annehmen das du in Magdeburg studierst? Da habe ich auch angefangen zu studieren (jetzt bin ich woanders)

Darfst du. Bin allerdings so gut wie fertig. Was hast du studiert? (Ich bin an der FEIT.)

Da mir gerade klar wird was du mit InOrder-Traversierung meinst, kann ich nur sagen, das ist nicht im Zwecke des Erfinders

Das ist mir schon klar.

Der Vorteil eines Baums ist ja das du gerade nicht alle Elemente anfassen musst, wenn du was bestimmtes suchst und du willst ja ne Art Liste machen (das wäre das Ergebnis der InOrder-Traversierung).

Exakt, dabei fallen dann das vorherige/nachfolgende Element mit bei raus. Ein Baum ist relativ ungeeignet, um das vorherige/nachfolgende Element zu einem bestimmten Element zu finden, zumindest wüsste ich nicht, wie man das tut. (Im Gegensatz zu einer doppelt verketteten Liste, wo das trivial ist.)

Mir ist gestern Abend dann noch die entscheidene Idee gekommen.

In meinem aktuellen Code ist auch noch ein Fehler. Denn ich muss den Baum immer bis zu einem Ende durchlaufen, ansonsten kann ich nicht sicher sein das ich nicht gerade einen "illegalen" Bereich freigeben möchte.

Ich verstehe nicht, was du meinst. Inwiefern illegal?

Ich stelle mir einen Baum vor, der Blöcke anhand ihrer Anfangsadresse(!) im Adressraum enthält und zu jedem Block abspeichert, ob er gerade frei oder belegt ist (und wenn ja, von wem). Jede Ressource (Adressraum) gehört zu exakt einem Block, das heißt es gibt prinzipbedingt keine Überschneidungen. Ist derjenige, der die Freigabe fordert nicht der Eigentümer, darf nicht freigegeben werden. (Möchte der Kernel ein "Loch" freigeben, so darf er das. Jemand könnte ja RAM nachgesteckt haben oder was auch immer.)

Ich habe mir das so vorgestellt das ich 2 Pointer habe *before und *behind, die auf Baum-Knoten zeigen können.
Ich gehe halt den Baum von der Wurzel an durch und überprüfe jeden Knoten darauf, ob der Bereich sich irgendwie mit dem freizugebenden überschneidet (wenn ja, dann wird ein Fehler zurückgegeben).

In einer Baumstruktur können zwei Nachbarn aber prinzipiell weit voneinander entfernt sein, du brauchst aber den Vorgänger zu einem gegebenen Knoten. Der kann im worst case einen vollständigen Weg über die Wurzel nötig machen, gleiches gilt für den Nachfolger.

Desweiteren wird jeder Knoten darauf überpüft ob der Bereich da drinnen sich mit dem freizugebenden irgendwie angrenz (deswegen before und behind) und wenn das der Fall ist, wird der entsprechende Pointer auf diese Node zeigen.

Das funktioniert so nicht, weil Vorgänger und Nachfolger weit voneinander entfernt sein können und nicht auf einem Wege erreichbar sein müssen. Ist dein Suchschlüssel in irgendeinem Unterbaum das rechteste Element, so wird dessen Nachfolger in einem Nachbarbaum das linkste Element sein und du müsstest bis zur Wurzel nach oben schauen.

Dein Ansatz funktioniert, wird aber nicht in jedem Fall den angrenzenden Bereich finden. Oder ich übersehe etwas.

Ich gehe dann den Baum noch bis zu einem Ende durch um sicher zu sein, das der Bereich auch freigegeben werden darf.

Damit fasst du also auch jedes Element im Baum an. Die Information, ob du einen Bereich freigeben darfst, muss vollständig im Baumknoten enthalten sein, sonst musst du zwangsweise jedes Element überprüfen.

Wenn ich dann mit der Schleife durch bin, brauche ich einfach nur 3 Fälle unterscheiden:

• beide Pointer sind NULL
• nur *before ist NULL
• nur *behind ist NULL

In meinem Fall stehen im Baum alle Blöcke mit der Information, ob sie belegt oder frei sind; das heißt, jeder Block existiert. Du müsstest also auf Freiheit der Blöcke prüfen.

Und schon gehe ich den Baum nur noch einmal anstatt zweimal durch und ich kann dann auch ganz leicht sagen welche "struct avlNode_t" und "struct boundaryTag_t" ich freigeben kann und kann mir so unnötig Allocator-Aufrufe sparen.

Was die letzte Struktur darstellen soll, weiß ich nicht.

Ich denke das sollte das Optimum sein was man rausholen kann und eine Halbierung im worst-case sollte nicht schlecht sein.

Wenn du zuviel optimierst, kommen am Ende falsche Werte raus.

Code: [Auswählen]

int rand()
{
    return 4; /* Wurde statistisch korrekt mit einem Würfel ermittelt. */
}

Gruß,
Svenska

[FlashBurn]

Das heißt, dass der VMM kein allgemeines malloc() benutzen darf

Richtig

Genau das macht meiner ja auch nicht (mehr ). Ich habe mir noch einen Allocator geschrieben, der aus einem vorher festgelegten Bereich allokiert. Damit weiß ich immer welche Adresse noch frei ist und muss nicht den VMM fragen.

Wenn ich es mir recht überlege, dann könnte das genau sowas sein was du die ganze Zeit meinst

Aber dieser Allocator ist nicht wirklich praktikabel wenn es um den ganzen Adressraum geht, nen kleines, zur Compile-Zeit feststehendes Stückchen vom virtuellen Adressraum geht gerade noch so.

Was hast du studiert?

Ich habe und mache es noch immer Informatik studiert (ich habe an eine Fachhochschule gewechselt, weil ich mit theoretischer Informatik rein gar nichts am Hut habe, sondern eher mit der Praxis).

Ein Baum ist relativ ungeeignet, um das vorherige/nachfolgende Element zu einem bestimmten Element zu finden, zumindest wüsste ich nicht, wie man das tut.

Ist gar nicht schwierig. Du guckst dir den Knoten an (fängst natürlich mit der Wurzel an) und vergleichst den Wert im Knoten mit deinem Wert (in unserem Bsp. also den Start-Wert), ist der Wert im Knoten größer als deiner gehst du nach links und ansonsten nach rechts.
Auf diesem Weg findest du (sofern vorhanden) einen Knoten der deinen Vorgänger und einen Knoten der deinen Nachfolger enthält.

Ich verstehe nicht, was du meinst. Inwiefern illegal?

Gehen wir mal davon aus das eine Map IDs speichert. Jemand ruft den Code auf um einen Bereich von IDs wieder freizugeben, er möchte die IDs 16 bis 18 freigeben.

Ich fange bei der Wurzel an und die hat die ID 20, also gehe ich nach links.
Der nächste Knoten hat die ID 15, ich habe also die ID vor meinen IDs gefunden (wird also in *before gespeichert). Da meine Start-ID größer ist gehe ich nach rechts.
Der nächste Knoten hat die ID 19, ich habe also die ID nach meinen IDs gefunden (wird also in *behind gespeichert).

Jetzt kommt das Problem meines alten Algos. Denn ich habe jetzt einfach aufgehört den Baum zu durchsuchen.

Ich gehe jetzt nach links (weil 19 ist größer als 16)
Der nächste Knoten hat die ID 17! Damit weiß ich jetzt, der Aufrufer wollte IDs freigeben die gar nicht in Benutzung waren und gebe einen Fehler zurück (das meine ich mit "illegal").

Wenn du jetzt wieder meinst das ja eigentlich nur IDs freigegeben werden die in Benutzung sind, sag ich einfach mal, dann könnte man sich auch solche Sachen wie auf nen NULL-Pointer überpüfen oder gucken ob eine PageAddr auch wirklich 4KB aligned ist sparen! Macht man aber nicht.

Entweder um sich vor Bugs zu schützen oder in meinem Fall wird dieser Map-Code auch aus dem UserSpace aufgerufen (wenn das App Speicher wieder freigeben will) und da kann dann schonmal ein böses Programm versuchen Speicher freizugeben was es eigentlich gar nicht darf!

In meinem Fall stehen im Baum alle Blöcke mit der Information, ob sie belegt oder frei sind; das heißt, jeder Block existiert. Du müsstest also auf Freiheit der Blöcke prüfen.

Glaub mir wenn ich die sage, dass das ne ganz schlechte Idee ist!

Ich will nur die freien Bereiche speichern, weil ich erstens daraus ableiten kann welche Bereich benutzt sind und weil ich damit den wenigst nötigen Speicher brauche.

Mal nen kleines Bsp. Du speicherst in einem Baum alle Bereiche die frei oder benutzt sind. Das ganze wird vom VMM genutzt, bildet also den UserSpace ab.

Wir haben also einen 3GB Adressraum. Ich nehme mir jetzt mal bewusst den worst-case (wenn er auch unwahrscheinlich ist, aber er dürfte relativ einfach herbei zu führen sein).
Du hast also ein Schema frei-belegt-frei-belegt-... und jeder Bereich ist genau eine Page (4KB) groß.

Dann hast du 393216 frei und 393216 benutzte Bereiche, dein Baum würde also aus 786432 Einträgen bestehen. Ich gehe mal optimistischer Weise von einer Knoten-Größe von 16bytes aus, macht insgesamt 12.582.912bytes = 12MB.

Meine Variante würde mit "nur" 6MB auskommen und ich könnte das gleiche machen wie du auch.

Wenn du zuviel optimierst, kommen am Ende falsche Werte raus. tongue

Code: [Auswählen]

int rand()
{
    return 4; /* Wurde statistisch korrekt mit einem Würfel ermittelt. */
}


Darf ich diese auf Geschwindigkeit optimierte rand() Funktion übernehmen "Schlimmere" Werte als die normale liefert die auch nicht

[erik.vikinger]

Hallo,

Sowas in der Art habe ich probiert und das hat auch funktioniert, bis ich zuviele CPUs (unter QEMU) hatte....

Ja, das ist ein kniffliges Problem. Das könnte man aber im SlabAllocator damit lösen indem man erstmal prüft ob überhaupt Knappheit herrscht (wenn nicht kann der SlabAllocator einfach ein Objekt rausgeben) und wenn doch dann muss geschaut werden ob der VMM gerade benutzt wird (sollte sich am VMM-Lock bestimmen lassen, wenn das VMM-Lock belegt ist dann läuft der VMM auch gerade und wird am Ende auch neuen Speicher für den SlabAllocator bringen da das Knapp-Flag in jedem Fall gesetzt werden sollte). Wenn der VMM schon in Benutzung ist dann darf der SlabAllocator nur dann ein Objekt zurückgeben wenn er auch vom VMM aufgerufen wurde (hierzu muss eben ein passendes bool-Parameter zu kmalloc hinzugefügt werden) ansonsten muss gewartet werden (ja das ist unangenehm aber sicher auch nicht gerade häufig), wenn der VMM noch nicht läuft dann muss der SlabAllocator ihn direkt aufrufen. Ich weiß das klingt ein bisschen kompliziert und umständlich aber ich denke es steckt nur wenig Fehlerpotential drin und ermöglicht einem so auch das man selbst im VMM ganz normales kmalloc/kfree benutzen kann (für diesen Komfort bin ich schon bereit etwa 50 Code-Zeilen zu investieren). Wenn man das nicht macht benötigt man auf jeden Fall im VMM eine zusätzliche primitive malloc/free-Implementierung nur für die Verwaltungsstrukturen die der VMM selber benutzt (was wohl deutlich mehr als 50 Code-Zeilen werden dürften und zu primitiv sollte man das auch nicht machen wenn man ordentlich Performance will). Damit hätte ich also einen SlabAllocator der das kmalloc/kfree zur Verfügung stellt (für die etwa 5 oder 6 möglichen Objekt-Größen, mehr wird der Micro-Kernel intern nicht brauchen) der auf einem VMM aufsetzt welcher seinerseits auch kmalloc/kfree benutzen kann. Einen PMM benötige ich nicht in der normalen Form da bei mir ja normalerweise linearer Speicher identisch zum physischen Speicher ist und das Paging nur für Speichermagie und Swapping benutzt werden soll. Der eine lineare Speicher (welcher vom VMM in Page-Granularität verwaltet wird) bleibt also der Master von dem alles abhängt und eine zusätzliche Verwaltung physischen Speichers findet nur statt wenn diese auch nötig ist.

Das heißt, dass der VMM kein allgemeines malloc() benutzen darf

Genau das find ich doof. Ich verstehe das damit ein (eventuell schwerwiegendes) Henne-Ei-Problem entsteht aber ich vermute das es mit meinem Vorschlag (elegant und performant) lösbar ist. Was ich auf jeden Fall vermeiden möchte ist doppelter Code.


@FlashBurn:
Ich würde den VMM auch die benutzten Speicher-Blöcke verwalten lassen damit bei einem free (was ja nur den Anfangspointer eines Bereiches mitbekommt) auch ermittelt werden kann wie groß der freizugebende Bereich eigentlich ist. Dein Beispiel mit den abwechselden Pages ist IMHO schon ziemlich extrem daneben, wer so nen Scheiß macht muss sich auch nicht wundern wenn das OS lahmt, alternativ könnte das OS ja die Menge der zugewiesenen Speicherblöcke pro Prozess begrenzen (ein einfacher Zähler im Prozess-Descriptor-Struct) so das ein Prozess maximal X beliebig große Blöcke an Speicher holen kann (wenn ein Programm seinen Speicherbedarf nicht in anständig großen Blöcken holt bekommt es eben irgendwann keine mehr und fertig, 3GB in 4kB-Häppchen zu holen ist schon ziemlich dumm, für X würde ich einfach mal 4096 nehmen so das Dein Baum maximal 8193-Elemente enthält).


Grüße
Erik

[FlashBurn]

Ich würde den VMM auch die benutzten Speicher-Blöcke verwalten lassen damit bei einem free (was ja nur den Anfangspointer eines Bereiches mitbekommt) auch ermittelt werden kann wie groß der freizugebende Bereich eigentlich ist.

Und was ist wenn er nicht den ganzen Speicher des vorher geholten Blocks freigeben möchte (mache ich im Kernel oft)?

Dein Beispiel mit den abwechselden Pages ist IMHO schon ziemlich extrem daneben, wer so nen Scheiß macht muss sich auch nicht wundern wenn das OS lahmt

Nicht der User wird sich wundern warum das System so lahmt, sondern der Programmierer wird sich freuen das er gerade das System verlangsamt hat.

Ein anderes Bsp, selbes Prinzip. Eine DoS-Attacke verlangsamt ja nen Server auch. Wimre habe ich mal in einer Arbeit (wo es um Bäume ging) gelesen das die IP-Adressen (glaub ich jedenfalls) nicht immer in einem Baum verwaltet wurden und dadurch eine DoS-Attacke erst richtig effektiv möglich war, seit dem man sowas in einem Baum abspeichert kann der Server mehr Anfragen schneller beantworten und es ist nicht mehr so einfach eine DoS-Attacke durchzuführen.

Zumal ich immer auch den worst-case mit einplane und selbst du sagst sogar, das man das machen soll (ich erinnere mich da an einen 64bit Counter der ja überlufen kann, was aber unwahrscheinlich bis unmöglich war und du hast ja auch da gesagt, dass man sowas behandeln soll ).

3GB in 4kB-Häppchen zu holen ist schon ziemlich dumm

Kommt ganz drauf an wie das passiert. Wenn du 3GB auf einmal haben willst dann ist es dumm, wenn du aber immer nur wenig Speicher brauchst und dann immer von Zeit zu Zeit 4KB holst, ist das schon nicht mehr dumm.

alternativ könnte das OS ja die Menge der zugewiesenen Speicherblöcke pro Prozess begrenzen (ein einfacher Zähler im Prozess-Descriptor-Struct) so das ein Prozess maximal X beliebig große Blöcke an Speicher holen kann (wenn ein Programm seinen Speicherbedarf nicht in anständig großen Blöcken holt bekommt es eben irgendwann keine mehr

Damit zwingst du ein Programm ja zur Verschwendung. Lösung wäre jetzt nur den Bereich zu reservieren und keine physischen Pages zu mappen, sondern das erst machen wenn das erste Mal auf die Page zugegriffen wird.

Ich weiß das ich das bei mir machen kann, aber du (möchte ich doch meinen) nicht bei dir.

Zumal ich möchte das ein Programm selbst entscheiden darf, ob erstmal nur der Bereich reserviert wird und dann bei einem PageFault erst Speicher gemappt wird oder ob das gleich gemacht wird.

@erik

Was deinen Vorschlag betrifft, würde bei mir zu Performance Problemen führen und ob es funktioniert bin ich mir auch nicht sicher.
Denn bei mir kommt (bzw. kam) noch ein Problem dazu. Ich verwende zum Verwalten ja nen AVL-Baum und der wird noch ganz oft in meinem Kernel verwendet und jedes Mal wenn er verwendet wird und nicht für den VMM benötigt wird könntest du den VMM ja ganz normal aufrufen (denkt man) ohne etwas überprüfen zu müssen.
Braucht der VMM (der vom SlabAllocator aufgerufen wurde, weil er ne Page für AVL-Nodes braucht) jetzt aber doch noch ne Node, hast du ne Dead-Lock (weil der Lock für den Slab ja schon von jemand anderes gehalten wird).

Deswegen habe ich mir halt nen kleinen eigenen Allocator geschrieben.

edit::

Welchen Vorteil versprecht ihr euch eigentlich davon, wenn man die benutzten Bereich mit speichert?

[Svenska]

Hallo,

Das heißt, dass der VMM kein allgemeines malloc() benutzen darf

Genau das macht meiner ja auch nicht (mehr ). Ich habe mir noch einen Allocator geschrieben, der aus einem vorher festgelegten Bereich allokiert. Damit weiß ich immer welche Adresse noch frei ist und muss nicht den VMM fragen.

Richtig.

Wenn ich es mir recht überlege, dann könnte das genau sowas sein was du die ganze Zeit meinst

Richtig.

Aber dieser Allocator ist nicht wirklich praktikabel wenn es um den ganzen Adressraum geht, nen kleines, zur Compile-Zeit feststehendes Stückchen vom virtuellen Adressraum geht gerade noch so.

Es ist aber ein neuer Allokator und damit genau das, was erik nicht möchte. Kannst du den PMM nicht dafür benutzen? Dir geht es an sich ja nicht um virtuellen Adressraum, sondern um Speicher für die internen Datenstrukturen des VMMs. Den Speicher schenkt dir der PMM und das Mapping dazu denkst du dir halt selbst aus, genau so, wie du es für andere Datenblöcke auch machst.

Ein Baum ist relativ ungeeignet, um das vorherige/nachfolgende Element zu einem bestimmten Element zu finden, zumindest wüsste ich nicht, wie man das tut.

Ist gar nicht schwierig. Du guckst dir den Knoten an (fängst natürlich mit der Wurzel an) und vergleichst den Wert im Knoten mit deinem Wert (in unserem Bsp. also den Start-Wert), ist der Wert im Knoten größer als deiner gehst du nach links und ansonsten nach rechts.
Auf diesem Weg findest du (sofern vorhanden) einen Knoten der deinen Vorgänger und einen Knoten der deinen Nachfolger enthält.

Das heißt, ich durchsuche den Baum insgesamt dreimal... einmal suche ich im Baum nach meinem Block. Beim zweiten Mal untersuche ich alle Blöcke, die kleiner sind als mein Block (und damit potentiell links angrenzen), beim dritten Mal untersuche ich alle Blöcke, die größer sind. Da lohnt es sich, jeden Block exakt einmal anzuschauen (Liste/Traversierung); im Durchschnitt untersuche ich ohnehin nur die Hälfte aller Blöcke. Somit leider O(n/2).

Ich verstehe nicht, was du meinst. Inwiefern illegal?

Gehen wir mal davon aus das eine Map IDs speichert. Jemand ruft den Code auf um einen Bereich von IDs wieder freizugeben, er möchte die IDs 16 bis 18 freigeben.

Stop, das darf er nicht. Entweder er hat sich einen Block aus 3 IDs (16-17-18) geholt, dann darf er diesen Block als Ganzes freigeben. Wenn nicht, dann muss(!) er diese IDs auch einzeln zurückgeben. Die Permissions werden dann einzeln geprüft.

Wenn du jetzt wieder meinst das ja eigentlich nur IDs freigegeben werden die in Benutzung sind, sag ich einfach mal, dann könnte man sich auch solche Sachen wie auf nen NULL-Pointer überpüfen oder gucken ob eine PageAddr auch wirklich 4KB aligned ist sparen! Macht man aber nicht.

Darum solltest du auch überprüfen, ob der Block in exakt dieser Form auch existiert (NULL-Pointer, PageAlignment, ... werden beim Erstellen geprüft; "unrunde" Adressen existieren somit nicht, brauchen also nicht extra geprüft werden) UND belegt ist UND der Eigentümer auch derjenige ist, der freigeben möchte.

Entweder um sich vor Bugs zu schützen oder in meinem Fall wird dieser Map-Code auch aus dem UserSpace aufgerufen (wenn das App Speicher wieder freigeben will) und da kann dann schonmal ein böses Programm versuchen Speicher freizugeben was es eigentlich gar nicht darf!

Also guckst du nach, ob das böse Programm den Speicher auch besitzt, wenn nicht wird es gekillt.

In meinem Fall stehen im Baum alle Blöcke mit der Information, ob sie belegt oder frei sind; das heißt, jeder Block existiert. Du müsstest also auf Freiheit der Blöcke prüfen.

Glaub mir wenn ich die sage, dass das ne ganz schlechte Idee ist!

Warum?

Ich will nur die freien Bereiche speichern, weil ich erstens daraus ableiten kann welche Bereich benutzt sind und weil ich damit den wenigst nötigen Speicher brauche.

Speicher ist heutzutage wirklich genug da... mal abgesehen ist bei einem "freien" Block nur bekannt, dass niemand ihn besitzt; bei einem "belegten" Block gibt es aber noch weitere, interessante Informationen: Eigentümer, Permissions (r/w/x) usw. Dann speichere lieber die belegten Blöcke.

Mal nen kleines Bsp. Du speicherst in einem Baum alle Bereiche die frei oder benutzt sind. Das ganze wird vom VMM genutzt, bildet also den UserSpace ab.

Wir haben also einen 3GB Adressraum. Ich nehme mir jetzt mal bewusst den worst-case (wenn er auch unwahrscheinlich ist, aber er dürfte relativ einfach herbei zu führen sein).
Du hast also ein Schema frei-belegt-frei-belegt-... und jeder Bereich ist genau eine Page (4KB) groß.

Dann hast du 393216 frei und 393216 benutzte Bereiche, dein Baum würde also aus 786432 Einträgen bestehen. Ich gehe mal optimistischer Weise von einer Knoten-Größe von 16bytes aus, macht insgesamt 12.582.912bytes = 12MB.

Das heißt, im Worst Case kostet mich das 12 MB. Wenn ich 3 GB Speicher in Blöcken zu je 4k belege. Das ist erstmal weit hergeholt, zum anderen habe ich - wenn ich 3 GB RAM habe - auch 12 MB übrig. Das ist kein Grund.

Meine Variante würde mit "nur" 6MB auskommen und ich könnte das gleiche machen wie du auch.

Nein, du kannst keine Permissions prüfen.

Wenn du zuviel optimierst, kommen am Ende falsche Werte raus.

Code: [Auswählen]

int rand()
{
    return 4; /* Wurde statistisch korrekt mit einem Würfel ermittelt. */
}


Darf ich diese auf Geschwindigkeit optimierte rand() Funktion übernehmen "Schlimmere" Werte als die normale liefert die auch nicht

Darfst du.

Das heißt, dass der VMM kein allgemeines malloc() benutzen darf

Genau das find ich doof. Ich verstehe das damit ein (eventuell schwerwiegendes) Henne-Ei-Problem entsteht aber ich vermute das es mit meinem Vorschlag (elegant und performant) lösbar ist. Was ich auf jeden Fall vermeiden möchte ist doppelter Code.

Naja, Durchgriffe durch verschiedene Layer halte ich nicht für elegant. Relativ schnell implementierbar mag es sein, performant auch, aber nicht elegant...

Und was ist wenn er nicht den ganzen Speicher des vorher geholten Blocks freigeben möchte (mache ich im Kernel oft)?

Dann benutzt du eine Funktion, die nicht free() heißt. Diese kann einen Block einfach in zwei Teile aufspalten: einen freigegebenen und einen weiterhin belegten Block.

Nicht der User wird sich wundern warum das System so lahmt, sondern der Programmierer wird sich freuen das er gerade das System verlangsamt hat.

Da gibt es elegantere Methoden. Außerdem hast du als Userspace-Prozess kein Wissen darüber, wieviel Speicher nun exakt zur Verfügung steht [ein malloc() braucht mehr Speicher als den angeforderten] und kannst somit den Prozess nicht rechtzeitig anhalten; damit wird am Ende des Tages der OOM-Sensenmann kommen und dich umbringen.

Ein anderes Bsp, selbes Prinzip. Eine DoS-Attacke verlangsamt ja nen Server auch. Wimre habe ich mal in einer Arbeit (wo es um Bäume ging) gelesen das die IP-Adressen (glaub ich jedenfalls) nicht immer in einem Baum verwaltet wurden und dadurch eine DoS-Attacke erst richtig effektiv möglich war, seit dem man sowas in einem Baum abspeichert kann der Server mehr Anfragen schneller beantworten und es ist nicht mehr so einfach eine DoS-Attacke durchzuführen.

Betonung auf "nicht mehr so einfach". Die Leute benutzen aber trotzdem Apache.

Zumal ich immer auch den worst-case mit einplane und selbst du sagst sogar, das man das machen soll (ich erinnere mich da an einen 64bit Counter der ja überlufen kann, was aber unwahrscheinlich bis unmöglich war und du hast ja auch da gesagt, dass man sowas behandeln soll ).

Richtig. Aber 12 MB Speicherverlust in einem Fall, den man quasi nur absichtlich herbeiführen kann, ist für mich jetzt kein Weltuntergang.

Die Zeit zum Traversieren der Bäume halte ich da für tödlicher.

Kommt ganz drauf an wie das passiert. Wenn du 3GB auf einmal haben willst dann ist es dumm, wenn du aber immer nur wenig Speicher brauchst und dann immer von Zeit zu Zeit 4KB holst, ist das schon nicht mehr dumm.

Doch, ist es. Ich kann mir keinen Anwendungsfall (mal abgesehen von richtig miesen memory leaks) vorstellen, bei dem du den Endspeicherverbrauch nicht mal näherungsweise abschätzen kannst und er trotzdem so groß werden kann. Das bedeutet schließlich, dass der Speicherverbrauch unbegrenzt ist (memleak). Im Normalfall sollte dann wieder ein OOM-Killer bereitstehen. Man kann Programme ja auch präventiv killen, wenn sie zuviel RAM verbrauchen...

alternativ könnte das OS ja die Menge der zugewiesenen Speicherblöcke pro Prozess begrenzen (ein einfacher Zähler im Prozess-Descriptor-Struct) so das ein Prozess maximal X beliebig große Blöcke an Speicher holen kann (wenn ein Programm seinen Speicherbedarf nicht in anständig großen Blöcken holt bekommt es eben irgendwann keine mehr

Damit zwingst du ein Programm ja zur Verschwendung. Lösung wäre jetzt nur den Bereich zu reservieren und keine physischen Pages zu mappen, sondern das erst machen wenn das erste Mal auf die Page zugegriffen wird.

Nein. Ein Programm sollte eine dem Anwendungsfall angepasste Menge an Speicher reservieren und nicht das zwingend minimalste Minimum. Schließlich muss jeder mit malloc() geholte Block auch irgendwo verwaltet werden. Außerdem sind bei einer Programmgröße von z.B. 200 MB (typischer Firefox) ein paar hundert KB Verschwendung irrelevant.

Ich weiß das ich das bei mir machen kann, aber du (möchte ich doch meinen) nicht bei dir.

Optimieren ja, aber nicht zu viel. Außerdem kannst du immer Rechenzeit gegen Speicherverbrauch eintauschen, der Optimalfall liegt nie auf der einen oder anderen Seite. (Es sei denn, die Ressourcen sind wirklich zu knapp, wie z.B. ein TCP/IP-Stack auf einem 8-bit-µC.)

Zumal ich möchte das ein Programm selbst entscheiden darf, ob erstmal nur der Bereich reserviert wird und dann bei einem PageFault erst Speicher gemappt wird oder ob das gleich gemacht wird.

Wozu? Damit kann ein Programm dein System lahmlegen, indem es Speicher reserviert und ihn nicht nutzt. Dazu kommt dann noch der Gedanke des "Working Set" einer Anwendung, d.h. nachdem die wesentlichen Teile per PageFault gemappt wurden, spielt der Zeitverlust kaum noch eine Rolle.

Alternativ kannst du auch sagen, dass Blöcke größer 16 MB nicht automatisch gemappt werden, Blöcke kleiner schon. Das geschieht unter der Annahme, dass kleine Blöcke auch genutzt werden, sehr große Blöcke erstmal für später reserviert werden.

Gruß,
Svenska

[FlashBurn]

Dir geht es an sich ja nicht um virtuellen Adressraum

Doch genau darum geht es ja. Ich brauche eine freie virtuelle Adresse um physischen Speicher mappen zu können und wenn ich vorher nen kleinen Bereich genau dafür abzwacke und auch meine Datenstrukturen zur Verwaltung dieses Bereichs schon vorher allokiere dann habe ich das erreicht.

Das heißt, ich durchsuche den Baum insgesamt dreimal... einmal suche ich im Baum nach meinem Block. Beim zweiten Mal untersuche ich alle Blöcke, die kleiner sind als mein Block (und damit potentiell links angrenzen), beim dritten Mal untersuche ich alle Blöcke, die größer sind. Da lohnt es sich, jeden Block exakt einmal anzuschauen (Liste/Traversierung); im Durchschnitt untersuche ich ohnehin nur die Hälfte aller Blöcke.

Wieso so umständlich, dass machst du alles in einem Durchlauf! Du überprüfst jeden Knoten darauf, ob er eine der 3 Eigenschaften erfüllt und fertig.

Stop, das darf er nicht.

Wenn er das bei dir nicht darf, ok, aber bei mir darf er das. Ist halt ne Design-Entscheidung.

Speicher ist heutzutage wirklich genug da

Sorry, aber mit dieser Einstellung kommst du bei mir nicht weiter, das ist wie CPU Leistung ist doch genug da, wozu nen komplizierten Baum nehmen, ne Liste ist viel einfacher!

Wegen solcher Einstellungen werden die CPUs immer schneller, haben wir immer mehr RAM, aber die Programme werden immer langsamer!

Nein, du kannst keine Permissions prüfen.

Richtig, brauch ich nicht und will ich nicht. Wozu eigentlich?

Dann kommt noch hinzu das es hier um allgemeinen Code geht, den man zur Verwaltung von all den Sachen nutzen kann, die sich halt auf Integer-Werte abbilden lassen.

Ich kann mir keinen Anwendungsfall (mal abgesehen von richtig miesen memory leaks) vorstellen, bei dem du den Endspeicherverbrauch nicht mal näherungsweise abschätzen kannst und er trotzdem so groß werden kann.

Nen Server, ne DB usw.

Du weißt vorher nie mit wievielen Clients du es zu tun bekommst usw. und bei einer DB kannst du vorher auch nicht wissen wie groß die im Endeffekt wird.

Optimieren ja, aber nicht zu viel. Außerdem kannst du immer Rechenzeit gegen Speicherverbrauch eintauschen, der Optimalfall liegt nie auf der einen oder anderen Seite. (Es sei denn, die Ressourcen sind wirklich zu knapp, wie z.B. ein TCP/IP-Stack auf einem 8-bit-µC.)

Der Satz war für erik und seine Architektur gedacht

Wozu? Damit kann ein Programm dein System lahmlegen, indem es Speicher reserviert und ihn nicht nutzt. Dazu kommt dann noch der Gedanke des "Working Set" einer Anwendung, d.h. nachdem die wesentlichen Teile per PageFault gemappt wurden, spielt der Zeitverlust kaum noch eine Rolle.

Ok, falsch ausgedrückt, ich meinte das ein Programm sagen, das es einen Bereich im virtuellen Speicher reservieren kann, der erst mit physischen Speicher hinterlegt wird, wenn das erste Mal darauf zugegriffen wird. Damit kannst du kein System lahmlegen.

[erik.vikinger]

Hallo,

Und was ist wenn er nicht den ganzen Speicher des vorher geholten Blocks freigeben möchte (mache ich im Kernel oft)?

Meinst Du das ernst? Sowas hab ich noch nie (bewusst) gesehen.

Edit:  natürlich kenne ich das, das heißt realloc() aber für physischen Speicher finde ich das trotzdem unangemessen.

sondern der Programmierer wird sich freuen das er gerade das System verlangsamt hat.

Deswegen ja das Limit bei der gewährten Block-Anzahl und schon sind solche Probleme gegessen. Bei mir ist dieses Limit automatisch dadurch gegeben das eine LDT nur ein begrenzte Anzahl an Einträgen hat, ich sehe damit auch kein Problem.

Zumal ich immer auch den worst-case mit einplane und selbst du sagst sogar, das man das machen soll (ich erinnere mich da an einen 64bit Counter der ja überlufen kann, was aber unwahrscheinlich bis unmöglich war und du hast ja auch da gesagt, dass man sowas behandeln soll ).

Natürlich musst Du als OS-Dever auch immer an den Worst-Case denken, sonst wärt Du ein schlechter Programmierer, deswegen hab ich ja das Limit vorgeschlagen.

Kommt ganz drauf an wie das passiert. Wenn du 3GB auf einmal haben willst dann ist es dumm, wenn du aber immer nur wenig Speicher brauchst und dann immer von Zeit zu Zeit 4KB holst, ist das schon nicht mehr dumm.

Alle normalen malloc-Implementierungen holen den virtuellen Speicher in größeren Blöcken herein und nicht jede Page einzeln. Wenn das OS in den virtuellen Speicher nicht sofort physische Pages mappt dann entsteht noch nicht mal eine Verschwendung des physischen Speichers.

Ich weiß das ich das bei mir machen kann, aber du (möchte ich doch meinen) nicht bei dir.

Ich habe dieses Problem (mit den zu umfangreichen Bäumen) nicht, bei mir haben die Prozesse Segmente, deren Anzahl per HW limitiert ist, und diese können dafür vergrößert (oder auch verkleinert) werden. Mit den LDTs verwalte ich also nur den belegten Speicher (mitsamt den Zugriffsrechten usw.) und der VMM verwaltet alle Blöcke im linearen Speicher (das können Segmente für die User-Space-Programme oder Slab-Blöcke für den Kernel-SlabAllocator sein und natürlich die freien Bereiche aber sonst nichts).

Zumal ich möchte das ein Programm selbst entscheiden darf, ob erstmal nur der Bereich reserviert wird und dann bei einem PageFault erst Speicher gemappt wird oder ob das gleich gemacht wird.

Das ist natürlich ein nettes Feature, aber dabei muss man aufpassen das trotzdem nur Speicher herausgegeben wird der sich auch wirklich mit Pages hinterlegen lässt (da gab es mal bestimmte 2.6er Linux-Kernel die das anders gehandhabt haben).

... und jedes Mal wenn er verwendet wird und nicht für den VMM benötigt wird könntest du den VMM ja ganz normal aufrufen (denkt man) ohne etwas überprüfen zu müssen.
Braucht der VMM (der vom SlabAllocator aufgerufen wurde, weil er ne Page für AVL-Nodes braucht) jetzt aber doch noch ne Node, hast du ne Dead-Lock (weil der Lock für den Slab ja schon von jemand anderes gehalten wird).

Wenn der SlabAllocator aufgerufen wird dann muss er als erstes seinen Lock holen (bei mir will ich pro Objekt-Größe einen eigenen Lock benutzen weil die unterschiedlichen Größen ja aus unterschiedlichen Blöcken kommen und damit auch keine Überschneidungen entstehen) und dann ein neues Objekt allozieren (für das allozieren selber wird kein VMM benötigt, die Slab-Verwaltungsstrukturen sind ja schon alle vorhanden). Wenn das allozieren nicht klappt dann muss als erstes das Lock wieder frei gegeben werden und dann der VMM aufgefordert werden einen neuen Block in den entsprechenden Slab-Pool hinzuzufügen (wofür natürlich der entsprechende Slab-Lock benötigt wird weil an den Slab-Verwaltungsstruckturen geändert wird) und erst danach kann der SlabAllocator den ganzen Vorgang erneut versuchen (also auch wieder den Lock neu holen).

Welchen Vorteil versprecht ihr euch eigentlich davon, wenn man die benutzten Bereich mit speichert?

Damit Du eben die Größe und auch andere Attribute der benutzten Blöcke kennst.

Das heißt, dass der VMM kein allgemeines malloc() benutzen darf

Genau das find ich doof. Ich verstehe das damit ein (eventuell schwerwiegendes) Henne-Ei-Problem entsteht aber ich vermute das es mit meinem Vorschlag (elegant und performant) lösbar ist. Was ich auf jeden Fall vermeiden möchte ist doppelter Code.

Naja, Durchgriffe durch verschiedene Layer halte ich nicht für elegant. Relativ schnell implementierbar mag es sein, performant auch, aber nicht elegant...

Wo siehst Du da einen Durchgriff? VMM und SlabAllocator sind auf einer Ebene und (leider) wechselseitig voneinander abhängig. Der SlabAllocator wird (neben dem VMM) von den verschiedenen Teilen im Kernel benutzt (er stellt ja den Kernel-Heap zur Verfügung) und der User-Space benötigt Segmente und holt sich diese vom VMM (natürlich über Kernel-Funktionen die zur Verwaltung der Segmente wieder den SlabAllocator benötigen). Ich sehe darin keine Probleme, wichtig ist nur das wenn SlabAllocator und VMM sich gegenseitig aufrufen der jeweils eigene Lock frei ist damit eben kein Dead-Lock entsteht.
Warum das nicht elegant ist musst Du mir mal genauer erklären! Gerade den Umstand das ich keinen doppelten Code habe betrachte ich als ziemlich elegant an meinem Konzept.


Grüße
Erik

[FlashBurn]

natürlich kenne ich das, das heißt realloc() aber für physischen Speicher finde ich das trotzdem unangemessen.

Also in meinem Kernel gibt es kein malloc/free/realloc und ich habe den VMM nur als ein Bsp genutzt wie man solch einen allgemeinen Ressourcen Allocator verwenden kann.

Wie kommst du von realloc() auf physischen Speicher?

Natürlich musst Du als OS-Dever auch immer an den Worst-Case denken, sonst wärt Du ein schlechter Programmierer, deswegen hab ich ja das Limit vorgeschlagen.

Ich mag künstlich geschaffene Limits nicht. Da hätte ich ja gleich bei meinem alten Kernel-Design bleiben können
Da war alles künstlich begrenzt, Prozesse, Threads, Ports usw. Macht die Verwaltung natürlich wesentlich einfacher und schneller, aber inzwischen finde ich soll das System halt so genutzt werden was der Speicher hergibt ohne das ich es irgendwo künstlich begrenze.

Alle normalen malloc-Implementierungen holen den virtuellen Speicher in größeren Blöcken herein und nicht jede Page einzeln. Wenn das OS in den virtuellen Speicher nicht sofort physische Pages mappt dann entsteht noch nicht mal eine Verschwendung des physischen Speichers.

Um mal wieder Haare zu spalten, wenn meine malloc-Implementation das nicht so macht ist deine Aussage schon automatisch falsch
Ansonsten fordert malloc halt immer 16KB an, aber ich finde halt trotzdem das ein Programm die Möglichkeit haben sollte auch nur 4KB anzufordern und einen angeforderten Block muss es auch anders wieder freigeben dürfen.

Ich habe dieses Problem (mit den zu umfangreichen Bäumen) nicht, bei mir haben die Prozesse Segmente, deren Anzahl per HW limitiert ist, und diese können dafür vergrößert (oder auch verkleinert) werden. Mit den LDTs verwalte ich also nur den belegten Speicher (mitsamt den Zugriffsrechten usw.) und der VMM verwaltet alle Blöcke im linearen Speicher (das können Segmente für die User-Space-Programme oder Slab-Blöcke für den Kernel-SlabAllocator sein und natürlich die freien Bereiche aber sonst nichts).

Ich meinte eigentlich das du nicht einfach nen Bereich im virtuellen Adressraum reservieren kannst und erst später (am besten Page-weise) mit physischen RAM hinterlegst.

Das ist natürlich ein nettes Feature, aber dabei muss man aufpassen das trotzdem nur Speicher herausgegeben wird der sich auch wirklich mit Pages hinterlegen lässt

Meinst du damit jetzt, das ich nicht 16MB an virtuellem Speicher rausgebe, obwohl ich nur noch 8MB an physischen RAM frei habe?
Dafür gibt es dann swapping. Wobei ich das für den Anfang nicht implementieren werde, da ich gar nicht wüsste wie.

Wenn der SlabAllocator aufgerufen wird dann muss er als erstes seinen Lock holen

Guck dir mal das Dokument von Bonwick aus dem Jahre 2001 zum SlabAllocator an. Denn deine Variante skaliert nämlich gar nicht mit mehreren CPUs.

Damit Du eben die Größe und auch andere Attribute der benutzten Blöcke kennst.

Zwei Sachen dazu, dass soll hier ein allgemeiner Ressourcen Allocator werden und wozu braucht man das?

Ich bin bisher ganz gut damit ausgekommen, nur die freien Bereiche zu speichern und habe noch keinen Nachteil davon getragen (der etwas anderes rechtfertigen würde).

Zum Thema Speicherverschwendung. Nochmal zum worst-case, wenn man jetzt immer nur 4KB Blöcke allokiert und halt die vollen 3GB ausgenutzt hat, dann ist mein Baum leer und eurer mit 786432 Elementen voll. Finde ich ein wenig übertrieben

Insbesondere rechne das mal auf 64bit hoch, da wird mein Baum seine größe behalten oder kleiner werden und eurer wird immer größer und das pro Prozess.

[Svenska]

Hallo,

Dir geht es an sich ja nicht um virtuellen Adressraum

Doch genau darum geht es ja. Ich brauche eine freie virtuelle Adresse um physischen Speicher mappen zu können und wenn ich vorher nen kleinen Bereich genau dafür abzwacke und auch meine Datenstrukturen zur Verwaltung dieses Bereichs schon vorher allokiere dann habe ich das erreicht.

Achso. Ich würde das dann wahrscheinlich mit in die Verwaltung der virtuellen Adressen mit reinziehen, d.h. du nutzt den gleichen Code zum Verwalten deiner eigenen Strukturen wie auch zum Verwalten der fremden Strukturen. Wichtig ist halt, dass du nicht den gesamten VMM dafür nutzt, denn das geht nicht.

Das heißt, ich durchsuche den Baum insgesamt dreimal... einmal suche ich im Baum nach meinem Block. Beim zweiten Mal untersuche ich alle Blöcke, die kleiner sind als mein Block (und damit potentiell links angrenzen), beim dritten Mal untersuche ich alle Blöcke, die größer sind. Da lohnt es sich, jeden Block exakt einmal anzuschauen (Liste/Traversierung); im Durchschnitt untersuche ich ohnehin nur die Hälfte aller Blöcke.

Wieso so umständlich, dass machst du alles in einem Durchlauf! Du überprüfst jeden Knoten darauf, ob er eine der 3 Eigenschaften erfüllt und fertig.

Dann muss ich mir ohnehin jedes Element anschauen. Was sowieso eine Pflicht ist, wenn im Gesamtbereich Löcher existieren.

Stop, das darf er nicht.

Wenn er das bei dir nicht darf, ok, aber bei mir darf er das. Ist halt ne Design-Entscheidung.

Das heißt, ich darf mir ein Megabyte Speicher geben lassen und dann in einem Befehl die mittleren 333 KB freigeben? Seltsames Design.

Speicher ist heutzutage wirklich genug da

Sorry, aber mit dieser Einstellung kommst du bei mir nicht weiter, das ist wie CPU Leistung ist doch genug da, wozu nen komplizierten Baum nehmen, ne Liste ist viel einfacher!

Stop. Es geht um zwölf Megabyte im Worst Case bei einer vorhandenen Ressourcenmenge von drei Gigabytes. Das sind 0,39%. Im Worst Case.

Ein System mit 64 MB RAM wird in den seltensten Fällen etwas davon haben, wenn ein Prozess 3 GB RAM alloziiert. Mit RAM hinterlegen geht nur begrenzt (die arme Festplatte) und ohne RAM ist das eh fürn Popo.
Wenn man 1% der verfügbaren Ressourcen für die Verwaltung derselben gebraucht, dann ist das für mich ein sehr akzeptabler Kompromiss. Vergleiche mal die formatierte/unformatierte Größe deiner Diskette/Festplatte - nicht in Bezug auf Dateisysteme, sondern den realen Unterschied.

Wegen solcher Einstellungen werden die CPUs immer schneller, haben wir immer mehr RAM, aber die Programme werden immer langsamer!

Das ist eine Frage von Verhältnismäßigkeit.

Nein, du kannst keine Permissions prüfen.

Richtig, brauch ich nicht und will ich nicht. Wozu eigentlich?

Damit niemand (außer dem Kernel) ein Loch im Adressraum freigeben kann? Damit ein Userspace-Programm nicht durch wildgewordene Zeiger Speicher eines anderen Programms (oder des Kernels) freigeben kann? Von mir aus auch "basic sanity checks".

Dann kommt noch hinzu das es hier um allgemeinen Code geht, den man zur Verwaltung von all den Sachen nutzen kann, die sich halt auf Integer-Werte abbilden lassen.

Och, so wirklich auf Integerwerte beschränkt ist der Ansatz auch nicht... allerdings hat jede Ressource die Eigenschaft, (mindestens) einen Eigentümer zu besitzen, sofern sie benutzt ist, und keinen, wenn sie frei ist.

Ich kann mir keinen Anwendungsfall (mal abgesehen von richtig miesen memory leaks) vorstellen, bei dem du den Endspeicherverbrauch nicht mal näherungsweise abschätzen kannst und er trotzdem so groß werden kann.

Nen Server, ne DB usw.

Hä? Konkretisier mal.

Du weißt vorher nie mit wievielen Clients du es zu tun bekommst usw. und bei einer DB kannst du vorher auch nicht wissen wie groß die im Endeffekt wird.

Ich werde die Datenbank aber nicht in Bröckchen verarbeiten, d.h. der RAM-Maximalverbrauch ist in jedem Fall durch die Größe der DB beschränkt. Außerdem werden DBs grundsätzlich so optimiert, dass die mindestmögliche Menge an I/O stattfinden muss (Transaktionen), das heißt, die DB-Dateien werden in möglichst großen Blöcken von der Festplatte und damit in große Blöcke im RAM gelesen.

Bei reinen Datenservern wächst nur der Plattencache an, der ist aber für das System irrelevant und darf jederzeit wieder in Anspruch genommen werden - ist also auch kein Grund.

Ok, falsch ausgedrückt, ich meinte das ein Programm sagen, das es einen Bereich im virtuellen Speicher reservieren kann, der erst mit physischen Speicher hinterlegt wird, wenn das erste Mal darauf zugegriffen wird. Damit kannst du kein System lahmlegen.

Richtig, das meinte ich auch. Das würde ich wahrscheinlich mit einer automatischen Grenze lösen (die genannten 16 MB).

Wo siehst Du da einen Durchgriff? VMM und SlabAllocator sind auf einer Ebene und (leider) wechselseitig voneinander abhängig. Der SlabAllocator wird (neben dem VMM) von den verschiedenen Teilen im Kernel benutzt (er stellt ja den Kernel-Heap zur Verfügung) und der User-Space benötigt Segmente und holt sich diese vom VMM (natürlich über Kernel-Funktionen die zur Verwaltung der Segmente wieder den SlabAllocator benötigen). Ich sehe darin keine Probleme, wichtig ist nur das wenn SlabAllocator und VMM sich gegenseitig aufrufen der jeweils eigene Lock frei ist damit eben kein Dead-Lock entsteht.

Wenn man das so betrachtet, dann sind Slab-Allocator und VMM ein monolithischer Blob. Solange man dann nicht behauptet, dass es verschiedene Ebenen seien (wie ich es tue), dann ist das auch eine Lösung und das hatte das auch so gekennzeichnet.

Ich mag künstlich geschaffene Limits nicht. Da hätte ich ja gleich bei meinem alten Kernel-Design bleiben können
Da war alles künstlich begrenzt, Prozesse, Threads, Ports usw. Macht die Verwaltung natürlich wesentlich einfacher und schneller, aber inzwischen finde ich soll das System halt so genutzt werden was der Speicher hergibt ohne das ich es irgendwo künstlich begrenze.

Dynamische Verwaltung von Zeugs erfordert immer mehr Ressourcen als statische Verwaltung von Zeugs. Mal abgesehen davon haben Limits durchaus eine Berechtigung, sei es für Zugriffe (wieder die Permissions), sei es, um einen amok laufenden Prozess loszuwerden.

Wann tritt denn dein OOM-Killer in Kraft? Wenn der RAM [ohne Plattencache] voll ist, wenn ein Prozess mehr RAM möchte als physisch vorhanden oder wenn die Festplatte wegen Swap voll ist? Ist das System überhaupt noch benutzbar, wenn es swappt? (Mein Linux bricht komplett zusammen, wenn der RAM nahezu voll ist und der Auslagerungsmarathon losgeht. Je schneller der OOM-Killer dann zuschlägt, umso eher läuft das System überhaupt wieder.)

Alle normalen malloc-Implementierungen holen den virtuellen Speicher in größeren Blöcken herein und nicht jede Page einzeln. Wenn das OS in den virtuellen Speicher nicht sofort physische Pages mappt dann entsteht noch nicht mal eine Verschwendung des physischen Speichers.

Um mal wieder Haare zu spalten, wenn meine malloc-Implementation das nicht so macht ist deine Aussage schon automatisch falsch

Dann ist deine malloc()-Implementierung nicht 'normal'.

Ansonsten fordert malloc halt immer 16KB an, aber ich finde halt trotzdem das ein Programm die Möglichkeit haben sollte auch nur 4KB anzufordern und einen angeforderten Block muss es auch anders wieder freigeben dürfen.

Darum geht es nicht. Wenn 16 MB angefordert werden, dann wird dein VMM hoffentlich nicht anfangen, 4096 einzelne Pages zu verarbeiten, oder?

Ich meinte eigentlich das du nicht einfach nen Bereich im virtuellen Adressraum reservieren kannst und erst später (am besten Page-weise) mit physischen RAM hinterlegst.

Klar. Das ist recht teuer, wenn du sofort den RAM benötigst (durch die Masse an PageFaults) - dem kannst du vorbeugen, wenn du den RAM sofort bereitstellst. Letzteres ist aber RAM-Verschwendung, wenn die Anwendung den RAM eben nicht nutzt und nur vorbeugend reserviert.

Das ist natürlich ein nettes Feature, aber dabei muss man aufpassen das trotzdem nur Speicher herausgegeben wird der sich auch wirklich mit Pages hinterlegen lässt

Meinst du damit jetzt, das ich nicht 16MB an virtuellem Speicher rausgebe, obwohl ich nur noch 8MB an physischen RAM frei habe?
Dafür gibt es dann swapping. Wobei ich das für den Anfang nicht implementieren werde, da ich gar nicht wüsste wie.

Swapping ist so sehr langsam und für das System so sehr tot, wenn die Daten nicht im RAM liegen, dass du das nicht unbegrenzt erlauben darfst. Sonst legt ein malloc(2TB, MAP_NOW) für hinreichend große Festplatte dein System für mehrere Stunden vollständig lahm.

Eine sinnvolle Grenze (für kleine Systeme) liegt bei etwa 2*RAMSIZE für alle Prozesse und 0.75*RAMSIZE für einen einzelnen Prozess. Und ja, das ist ein künstliches Limit und kann für bestimmte Anwendungsfälle auch zur Laufzeit korrigierbar sein (vgl. Linux /sys/*).

Damit Du eben die Größe und auch andere Attribute der benutzten Blöcke kennst.

Zwei Sachen dazu, dass soll hier ein allgemeiner Ressourcen Allocator werden und wozu braucht man das?

Und? Was für Ressourcen hast du denn? Hier geht es konkret um virtuellen Adressraum, in meinem Geiste zusätzlich zur Verwaltung von z.B. I/O-Ports und IRQ-Leitungen, in deinem Geiste zusätzlich zur Verwaltung von IDs.

Für Adressraum/Ports/IRQs gibt es jeweils Eigentümer (oder freigegeben), außerdem ist das Ding in Bereiche sortiert, die Elemente werden selten einzeln alloziiert. Für IDs gibt es einen Eigentümer, nur in seltenen Fällen wird Blockweise gearbeitet (jedes Dateihandle eines Prozesses steht für sich allein, eine Page eines Prozesses eher nicht).

Ich bin bisher ganz gut damit ausgekommen, nur die freien Bereiche zu speichern und habe noch keinen Nachteil davon getragen (der etwas anderes rechtfertigen würde).

Dann werden wir dich wohl nicht davon überzeugen können. Eh ich jetzt wieder einen Streit lostrete, lasse ich es damit sein.

Zum Thema Speicherverschwendung. Nochmal zum worst-case, wenn man jetzt immer nur 4KB Blöcke allokiert und halt die vollen 3GB ausgenutzt hat, dann ist mein Baum leer und eurer mit 786432 Elementen voll. Finde ich ein wenig übertrieben

Korrekt. Mach das mal unter einem normalen Betriebssystem und schaue, wieviel RAM du rauskriegst, wenn du (a) immer 4k-Blöcke alloziierst und (b) alles an einem Stück haben möchtest. Beobachte bitte die Performance des Systems in beiden Fällen... mich würde interessieren, ob die bekannten Betriebssysteme mit so einer Workload klarkommen oder nicht.

Insbesondere rechne das mal auf 64bit hoch, da wird mein Baum seine größe behalten oder kleiner werden und eurer wird immer größer und das pro Prozess.

Da der Ansatz Blödsinn ist, ist die Schlussfolgerung ebenfalls Blödsinn. Außerdem betrifft das, wenn man sinnvolle Limits einstellt (ja, das ist sinnvoll), nur Rechner, die auch genug RAM haben.

Andere Sache, die aber mehr Dateisysteme betrifft: Schiebe in einen Ordner mal 10k Dateien mit unterschiedlichen Größen (z.B. den WINXP-Installationsordner, für langsamere Systeme reicht auch der WIN31-Installationsordner). Gehe dann mit einem Dateimanager deiner Wahl dort rein. Merkt man die Wartezeit?

Du wirst mit jedem System eine gezielte Workload aufbauen können, die sämtliche Algorithmen in den worst case treibt. Die Frage ist, ob das System als Ganzes dann noch benutzbar und vor allem stabil bleibt (dann ist es auch DoS-sicher) oder ob dann Grenzfälle und race conditions auftreten, die dann Bugs triggern. Das ist für die Qualität eines OS mMn wichtiger... auch, wenn es hier nur um ein Hobby geht.

Gruß,
Svenska

[FlashBurn]

Dann muss ich mir ohnehin jedes Element anschauen. Was sowieso eine Pflicht ist, wenn im Gesamtbereich Löcher existieren.

Entweder wir reden mal wieder aneinander vorbei oder du hast es immernoch nicht verstanden

Nimm einfach an, du suchst in einem binären Baum ein bestimmtes Element, du fässt da ja nicht alle Elemente an (dann hätte der binäre Suchbaum ja keinen Vorteil gegenüber einer Liste), sondern nur die Elemente die auf deinem Suchweg liegen und auch nur die überprüfe ich auf die 3 Eigenschaften.

Das heißt, ich darf mir ein Megabyte Speicher geben lassen und dann in einem Befehl die mittleren 333 KB freigeben? Seltsames Design.

Jein. Wenn du geschrieben hättest das du 332KB (zwecks 4KB aligned) freigeben möchtest (und der Start ebenfalls 4KB aligned ist) dann ja

Ich denke halt an eine Situation wo du halt erstmal nen größere Brocken allokierst und dann später einen Teil wieder freigibst, weil du ihn nicht mehr brauchst.

Ein System mit 64 MB RAM wird in den seltensten Fällen etwas davon haben, wenn ein Prozess 3 GB RAM alloziiert. Mit RAM hinterlegen geht nur begrenzt (die arme Festplatte) und ohne RAM ist das eh fürn Popo.

Du vergisst den SharedMemory in deiner Rechnung, also kannst du durchaus mehr Speicher mappen als physisch vorhanden ist ohne dass das über Swapping laufen muss.

Wenn ich jetzt viele 4KB SharedMemory Bereiche habe (was bei mir der Fall sein wird) wird dein Baum immer größer weil du diese Bereiche ja auch mit speicherst.

Damit ein Userspace-Programm nicht durch wildgewordene Zeiger Speicher eines anderen Programms (oder des Kernels) freigeben kann?

Da wären wir dann wieder dabei, dass du einen Denkfehler drin hast oder das Konzept des virtuellen Speichers/Paging noch nicht ganz verstanden hast. Denn ich kann nicht den Speicher eines anderen Programms freigeben, auch nicht vom Kernel!

Jeder Prozess hat seine eigene Map wo die virtuellen Adressen verwaltet werden, das gleiche gilt für den Kernel.

Und ich kann ja nachprüfen ob das Programm mist macht oder nicht (von Löchern mal abgesehen) ohne das ich die benutzten Bereiche mitspeichern muss.

Och, so wirklich auf Integerwerte beschränkt ist der Ansatz auch nicht

Was schwebt dir denn da noch so vor, denn mir fällt nichts anders ein?

Hä? Konkretisier mal.

Am Bsp. vom Server. Jeder Client der Kontakt zum Server aufnimmt, erfordert nen neuen Thread und neue Datenstrukturen und da du nie wissen kannst wieviele Clients connecten, kannst du auch vorher nicht den Speicherverbrauch wissen.

Am Bsp der Datenbank, ich gehe jetzt mal davon aus das die komplett im Speicher liegt (wenn auch Teile ausgelager sein können).
Desto mehr Daten du in die DB einträgst desto größer wird die und auch dort kannst du ja vorher nicht wissen wie groß die mal wird oder ob sie klein bleibt.

Wann tritt denn dein OOM-Killer in Kraft? Wenn der RAM [ohne Plattencache] voll ist, wenn ein Prozess mehr RAM möchte als physisch vorhanden oder wenn die Festplatte wegen Swap voll ist? Ist das System überhaupt noch benutzbar, wenn es swappt? (Mein Linux bricht komplett zusammen, wenn der RAM nahezu voll ist und der Auslagerungsmarathon losgeht. Je schneller der OOM-Killer dann zuschlägt, umso eher läuft das System überhaupt wieder.)

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Aber wie schaffst du es das dein Linux einbricht (bzw. was verstehst du darunter). Ich habe das noch nicht (wieder) erlebt.

Dann ist deine malloc()-Implementierung nicht 'normal'.

Ich sags erstmal so, ich sehe den Zweck eines OS programmieren nicht darin, ein schon vorhandenes nachzuprogrammieren, also musst du auch mal was machen was nicht normal ist.

Mein SlabAllocator fordert auch nur 4KB an wenn da genügend Objekte reinpassen. Zumal müssen wir auch mal von malloc weg. Ich denke auch an die Fälle die direkt meine OS-API und nicht die libc nutzen.

Sonst legt ein malloc(2TB, MAP_NOW) für hinreichend große Festplatte dein System für mehrere Stunden vollständig lahm.

An so ein Bsp hatte ich noch gar nicht gedacht (auch wenn es eh nicht möglich ist, da ich mich erstmal auf 32bit beschränke, aber auch da wäre was in der Region von 2GB nicht so toll bei 128MB RAM).

Spontan würde ich halt sagen, bekommt er einfach nicht Da ich eh kein Swapping habe, geht das sowieso nicht.

außerdem ist das Ding in Bereiche sortiert, die Elemente werden selten einzeln alloziiert.

Das ist halt das Ding an einem allgemeinen Ressourcen Allocator, er muss damit klarkommen, das ganze Bereiche (virtuelle Adressen/IO-Ports) oder nur einzelne Elemente (IDs) allokiert werden.

Ich meine wie sinnvoll ist es denn für jede mögliche ID einen Eintrag zu haben das sie benutzt ist.

Im Endeffekt ist es doch sowieso so, dass es nur Probleme geben kann bei virtuellen Adressen die ausm UserSpace kommen, alles andere sollte/darf keine Probleme machen da es ansonsten nur aus dem Kernel kommt und da gehe ich mal davon aus, das ich nicht versuche meinen eigenen Kernel zu ärgern

Soll ich denn meinen neuen Code zum freigeben von Bereichen posten oder kann ich mir das auch sparen? Ich kann auch gleich sagen, dass der alte Code noch richtig viele Fehler hatte und um diese Fehler zu beseitigen und um einen schnelleren Code zu bekommen ist der Code nicht wirklich "schön".

[Svenska]

Nimm einfach an, du suchst in einem binären Baum ein bestimmtes Element, du fässt da ja nicht alle Elemente an (dann hätte der binäre Suchbaum ja keinen Vorteil gegenüber einer Liste), sondern nur die Elemente die auf deinem Suchweg liegen und auch nur die überprüfe ich auf die 3 Eigenschaften.

Naja, ich suche ja kein bestimmtes Element (dessen Suchschlüssel ich kenne), sondern ich suche ein Element mit bestimmten Eigenschaften... damit muss ich alle Elemente, die kleiner/größer sind als mein freizugebendes Element untersuchen, ob sie eine gemeinsame Grenze haben. Haben sie diese nicht, so existiert kein Nachbarelement.

Du kennst doch die Anfangsadressen dieser Nachbarelemente nicht, also kannst du danach nicht suchen, oder irre ich da?

Das heißt, ich darf mir ein Megabyte Speicher geben lassen und dann in einem Befehl die mittleren 333 KB freigeben? Seltsames Design.

Jein. Wenn du geschrieben hättest das du 332KB (zwecks 4KB aligned) freigeben möchtest (und der Start ebenfalls 4KB aligned ist) dann ja

Ich denke halt an eine Situation wo du halt erstmal nen größere Brocken allokierst und dann später einen Teil wieder freigibst, weil du ihn nicht mehr brauchst.

Das ist Unfug. Entweder du alloziierst genau das, was du brauchst, oder du alloziierst mehr. Und zwar so, dass du den Brocken dann von Vorne mit Daten füllst, und wenn du alle Daten hast, dann schneidest du hinten den ungenutzten Teil ab und gibst ihn wieder frei. (Das macht realloc() so.)

Einen belegten Block in drei Teile zu spalten, von denen nur der zweite Teil freizugeben ist, ist unsinnig. Außerdem bringt das nur bei auf 4k ausgerichteten Speicherblöcken was, da für den dritten Teil eine Anfangsadresse mit Alignment da sein muss.

Mir fällt kein sinnvoller Anwendungsfall dafür ein. Eher, dass du den vorderen und den hinteren Teil abschneidest (z.B. von einem HTTP-Request den Header und den hinteren Teil vom Body), aber das ist aufgrund der Alignment-Vorgabe unpraktisch.

Ein System mit 64 MB RAM wird in den seltensten Fällen etwas davon haben, wenn ein Prozess 3 GB RAM alloziiert. Mit RAM hinterlegen geht nur begrenzt (die arme Festplatte) und ohne RAM ist das eh fürn Popo.

Du vergisst den SharedMemory in deiner Rechnung, also kannst du durchaus mehr Speicher mappen als physisch vorhanden ist ohne dass das über Swapping laufen muss.

Wenn ich jetzt viele 4KB SharedMemory Bereiche habe (was bei mir der Fall sein wird) wird dein Baum immer größer weil du diese Bereiche ja auch mit speicherst.

Wieder eine Designentscheidung deinerseits, wobei du sicherlich keine 100k ShMem-Blöcke je 4 KB haben wirst. Ansonsten glaube ich nicht, dass das so ins Gewicht fallen wird. Verwalten musst du die Blöcke ohnehin irgendwo. In der globalen Verwaltung ist es schon aus CPU-Cachegründen besser aufgehoben.

Damit ein Userspace-Programm nicht durch wildgewordene Zeiger Speicher eines anderen Programms (oder des Kernels) freigeben kann?

Da wären wir dann wieder dabei, dass du einen Denkfehler drin hast oder das Konzept des virtuellen Speichers/Paging noch nicht ganz verstanden hast. Denn ich kann nicht den Speicher eines anderen Programms freigeben, auch nicht vom Kernel!

Ein Userspace-Programm kann aber Teile des Kernel-Speichers freigeben, wenn dieser Bereich im Userspace-Programm gemappt ist.

Jeder Prozess hat seine eigene Map wo die virtuellen Adressen verwaltet werden, das gleiche gilt für den Kernel.

Du willst also einen Baum pro Prozess haben?

Und ich kann ja nachprüfen ob das Programm mist macht oder nicht (von Löchern mal abgesehen) ohne das ich die benutzten Bereiche mitspeichern muss.

Wenn der Baum pro Prozess ist, ist der Eigentümer-Eintrag natürlich unsinnig, da es nur einen Eigentümer geben kann.

Och, so wirklich auf Integerwerte beschränkt ist der Ansatz auch nicht

Was schwebt dir denn da noch so vor, denn mir fällt nichts anders ein?

Spontan GUIDs. Die sind keine Integerwerte, lassen sich aber als Bereiche darstellen. Prinzipiell ist jeder Elementtyp möglich, welchen du irgendwie sortieren kannst (auf dem du also "<" und "=" definieren kannst).

Am Bsp. vom Server. Jeder Client der Kontakt zum Server aufnimmt, erfordert nen neuen Thread und neue Datenstrukturen und da du nie wissen kannst wieviele Clients connecten, kannst du auch vorher nicht den Speicherverbrauch wissen.

Falsch. Wenn jeder Client einen Thread erzeugt, dann braucht jeder Thread exakt einen Satz an Datenstrukturen. Da es recht teuer ist, hunderte/tausende Threads gleichzeitig zu erzeugen, werden die meist im Voraus erzeugt (z.B. im Apache gibst du an, wieviele Prozesse du gerne hättest und wieviele Threads jeder Prozess maximal erzeugen soll). Das gibt eine praktische Grenze an. Ansonsten hast du ein riesiges Einfallstor für DoS-Angriffe (Erzeugen/Freigeben von Threads kostet CPU-Zeit im Kernel; was ist, wenn die Daten mit 2 Byte/sek in die Threads geschoben werden?).

Theoretisch unlimitierte Anzahl gleichzeitiger Clients mit lange aktiven Verbindungen - also eben kein HTTP - erfordert asynchrones I/O. Schließlich kostet ein Thread durchaus eine Menge Speicher, da jeder Thread nicht nur einen Datensatz hat, sondern auch eigenen Heap & Stack etc. und das ganze zudem noch auf Page-Granularität liegt. Wenn du AIO verwendest, kannst du den Speicherverbrauch vorher recht gut abschätzen.

Am Bsp der Datenbank, ich gehe jetzt mal davon aus das die komplett im Speicher liegt (wenn auch Teile ausgelager sein können).
Desto mehr Daten du in die DB einträgst desto größer wird die und auch dort kannst du ja vorher nicht wissen wie groß die mal wird oder ob sie klein bleibt.

Solche Datenbanken sind nur für kleine Datenbestände geeignet. Außerdem wird die Datenbank, wenn sie komplett im Speicher gehalten wird, auch am Stück im Speicher gehalten - es ist sehr unhandlich, wenn du zigtausende einzelne Zeiger auf jeden Speicherblock vorhalten musst. Da wirst du dich in der Anwendung auf wenige, übersichtliche Blöcke beschränken, allein schon um sinnvoll Zeigerarithmetik machen zu können und im Zweifelsfall mit realloc() deinen Block vergrößern. (Realloc wird dann, wenn möglich, einfach Adressraum hinten dranhängen oder wenn das nicht geht, den Block umkopieren. Zumindest laut POSIX.)

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Also geht das System komplett kaputt.

Aber wie schaffst du es das dein Linux einbricht (bzw. was verstehst du darunter). Ich habe das noch nicht (wieder) erlebt.

Einfach ein "dd if=/dev/zero of=/dev/null bs=BLOCKSIZE count=5" machen und die BLOCKSIZE so groß wie möglich setzen. Optimalerweise auf den maximal möglichen Wert, so dass für jeden Block geswappt werden muss, der Block selbst aber noch in den RAM passt. Bei genügend hohem 'count' (oder ohne Angabe) dürfte das System fast unbenutzbar werden, da du keinen Speicher mehr hast und das I/O-Subsystem komplett ausgelastet ist.

Eine zweite Variante, die allerdings bekannt ist, ist ein langsames USB-1.1-Gerät, wo du mal schnell einige hundert MB draufkopierst [was dauert] und dann wird der RAM knapp oder du forderst eine große Menge RAM an. Dann geht auch nichts mehr, bis der Kopiervorgang beendet ist.

Dann ist deine malloc()-Implementierung nicht 'normal'.

Ich sags erstmal so, ich sehe den Zweck eines OS programmieren nicht darin, ein schon vorhandenes nachzuprogrammieren, also musst du auch mal was machen was nicht normal ist.

Naja, ich würde schon ein POSIX-artiges System bauen. Allein der Software wegen. Aber du hast recht, neue Wege zu beschreiten ist durchaus schön.

Mein SlabAllocator fordert auch nur 4KB an wenn da genügend Objekte reinpassen. Zumal müssen wir auch mal von malloc weg. Ich denke auch an die Fälle die direkt meine OS-API und nicht die libc nutzen.

Diese Interfaces sollte eigentlich nur die libc nutzen (und Treiber).

Sonst legt ein malloc(2TB, MAP_NOW) für hinreichend große Festplatte dein System für mehrere Stunden vollständig lahm.

An so ein Bsp hatte ich noch gar nicht gedacht (auch wenn es eh nicht möglich ist, da ich mich erstmal auf 32bit beschränke, aber auch da wäre was in der Region von 2GB nicht so toll bei 128MB RAM).

Spontan würde ich halt sagen, bekommt er einfach nicht Da ich eh kein Swapping habe, geht das sowieso nicht.

Warum sollte er es nicht kriegen? Du hast doch gesagt, dass jeder Prozess so viel Speicher anfordern kann wie geht, schließlich gibt es ja Swapspace.

Das ist halt das Ding an einem allgemeinen Ressourcen Allocator, er muss damit klarkommen, das ganze Bereiche (virtuelle Adressen/IO-Ports) oder nur einzelne Elemente (IDs) allokiert werden.

Ich meine wie sinnvoll ist es denn für jede mögliche ID einen Eintrag zu haben das sie benutzt ist.

Wie gesagt, eine Übersicht über die Eigentümer finde ich schon recht nett. Zumindest, wenn man die Ressourcen (IO-Ports) systemweit verwaltet. Mal abgesehen davon ist es unnötig, dass ich mehrere einzeln alloziierte Ressourcen als Block freigeben können muss. (Dazu müsste ich als Anwendung ja im Voraus schon das mergen vornehmen. Das kann der Kernel - der dafür optimiert sein sollte - ohnehin besser.) Der einzige Vorteil dabei ist die Syscall-Ersparnis, allerdings sind die von mir genannten Ressourcen relativ statisch und auch Filedescriptoren werden nicht zu hunderttausenden jede Sekunde freigegeben.

Im Endeffekt ist es doch sowieso so, dass es nur Probleme geben kann bei virtuellen Adressen die ausm UserSpace kommen, alles andere sollte/darf keine Probleme machen da es ansonsten nur aus dem Kernel kommt und da gehe ich mal davon aus, das ich nicht versuche meinen eigenen Kernel zu ärgern

Deinem eigenen Kernel solltest du schon trauen können, ebenso wie du allen Hardwaretreibern vertrauen musst.

Soll ich denn meinen neuen Code zum freigeben von Bereichen posten oder kann ich mir das auch sparen? Ich kann auch gleich sagen, dass der alte Code noch richtig viele Fehler hatte und um diese Fehler zu beseitigen und um einen schnelleren Code zu bekommen ist der Code nicht wirklich "schön".

Kannst du dir sparen, es sei denn, erik oder taljeth wollen drübergucken.

[erik.vikinger]

Hallo,

Ich mag künstlich geschaffene Limits nicht
[......]
aber inzwischen finde ich soll das System halt so genutzt werden was der Speicher hergibt ohne das ich es irgendwo künstlich begrenze.

Dann lass das Limit weg, was kann schon so schlimmes passieren? Im Worst-Case verbraucht ein Prozess der ganze 3 GB benötigt noch mal zusätzliche 6 oder 12 MB zur Verwaltung, da stimme ich mit svenska überein: "was solls". Wenn ein Prozess seinen Speicher in 4kB-Häppchen holt dann muss er eben damit leben das seine Speicherwünsche nur mit gemächlicher Geschwindigkeit (wegen dem riesigen Baum) bearbeitet werden können (selber schuld) und wenn Du ausgerechnet wegen den 6 oder 12 MB das Swappen anfangen musst dann war eh zu wenig RAM im Rechner (so dicht an der Grenze sollte man nicht arbeiten).

Alle normalen malloc-Implementierungen holen den virtuellen Speicher in größeren Blöcken herein und nicht jede Page einzeln. Wenn das OS in den virtuellen Speicher nicht sofort physische Pages mappt dann entsteht noch nicht mal eine Verschwendung des physischen Speichers.

Um mal wieder Haare zu spalten, wenn meine malloc-Implementation das nicht so macht ist deine Aussage schon automatisch falsch
Ansonsten fordert malloc halt immer 16KB an,

Also wenn Deine malloc-Implementierung (für die User-Space-libc) wirklich in 16kB-Häppchen den virtuellen Speicher holt dann würde ich da tatsächlich das Prädikat "kaputt" benutzen. Sorry, aber sowas macht man nicht.
Was Okay wäre ist wenn Du zur Compilezeit der libc sagst wie viel Speicher ein bestimmtes Programm maximal zur Laufzeit benötigen wird so das die libc ihre Allozierungen an virtuellem Speicher in optimal passenden Häppchen machen kann (falls man überhaupt zur Compilezeit sagen kann wie viel Speicher ein Programm maximal braucht) aber gute malloc-Implementierungen passen sich dem zur Laufzeit dynamisch an und versuchen den virtuellen Speicher in möglichst (angemessen) großen Stücken zu holen (z.B. in 4MB-Häppchen um die Benutzung von 4MB-Pages zu unterstützen).

aber ich finde halt trotzdem das ein Programm die Möglichkeit haben sollte auch nur 4KB anzufordern und einen angeforderten Block muss es auch anders wieder freigeben dürfen.

Natürlich muss ein Programm auch die Möglichkeit haben kleinste Pages einzeln anzufordern aber damit sollte es nicht seinen generischen Heap versorgen sondern nur spezielle Sachen wo so kleine Pages auch wirklich erforderlich und sinnvoll sind.

Ich meinte eigentlich das du nicht einfach nen Bereich im virtuellen Adressraum reservieren kannst und erst später (am besten Page-weise) mit physischen RAM hinterlegst.

Warum sollte ich das nicht können? Ich hab doch trotzdem ein Paging in der Hinterhand das ich bei Bedarf dazu schalten kann. Wenn ich noch 2GB freien Speicher hab und ein Prozess 16MB anfordert dann bringt es einfach nichts da erst mal nur ein paar Pages rein zulegen und den Rest mit teuren Page-Not-Present-Exceptions zu managen aber wenn das System kurz vor dem Swappen ist (oder aus anderen Gründen der physische Adressraum knapp wird) dann kann ich prinzipiell auch zu diesem Trick greifen. Ich möchte auf jeden Fall das es in einem 32Bit-System von mir auch bei nur 512MB RAM möglich ist ein 1GB Segment zu erstellen und damit arbeiten zu können, egal wie extrem langsam das wird es soll zumindest grundsätzlich funktionieren (ich sehe auch keinen Grund warum das nicht funktionieren sollte).

aber dabei muss man aufpassen das trotzdem nur Speicher herausgegeben wird der sich auch wirklich mit Pages hinterlegen lässt

Meinst du damit jetzt, das ich nicht 16MB an virtuellem Speicher rausgebe, obwohl ich nur noch 8MB an physischen RAM frei habe?

Fast, als maximale Obergrenze an virtuellem Speicher der für alle Prozesse zusammen (inklusive Kernel) zugewiesen werden darf zählt für mich tatsächlich vorhandener physischer RAM + tatsächlich vorhandener Swapp-Space (und wenn Du kein Swapping hast dann eben nur der physische RAM). Shared-Memory ist was anderes, der darf immer nur ein mal zählen egal in wie vielen Prozessen er gemappt wird (es wird ja auch nur ein mal physischer RAM dafür benötigt).
Manche 2.6er Linux-Kernel haben das mal anders gemacht so das man auf Embedded-Systemen (die eben kein Swapping haben) zwar deutlich mehr virtuellem RAM anfordern konnte als physisch da ist aber wenn man dann diesen virtuellen RAM benutzt (und er langsam mit echten Pages hinterlegt werden muss) kommt irgendwann eine OOM-Excpetion und der Prozess wird gekillt (was soll man auch sonst machen, der Prozess denkt ja das er Speicher hat und will den auch benutzen). Meiner persönlichen Meinung nach ist dieses Verhalten des Linux-Kernel ein Bug aber es wurde als Feature angepriesen, ob das in der Zwischenzeit behoben ist weiß ich jetzt gar nicht aber es ist einer der Gründe warum für viele kleine Embedded-Sachen immer noch gerne ein 2.4er Linux-Kernel benutzt wird.

Guck dir mal das Dokument von Bonwick aus dem Jahre 2001 zum SlabAllocator an. Denn deine Variante skaliert nämlich gar nicht mit mehreren CPUs.

Der schaltet vor den eigentlichen SlabAllocator noch diese "Magazin-Ebene", das geht bei mir prinzipiell auch, ich habe nur versucht meine Erklärung so einfach wie möglich zu halten und mich auf das Wesentliche (Wechselwirkung zwischen SlabAllocator und VMM) zu beschränken. Dieser Magazin-Mechanismus würde bei meinem nichtunterbrechbaren Kernel sogar besser funktionieren weil ich dafür keinerlei Lock o.ä. benötige.

Ich bin bisher ganz gut damit ausgekommen, nur die freien Bereiche zu speichern und habe noch keinen Nachteil davon getragen (der etwas anderes rechtfertigen würde).

Ich muss ehrlich sagen das mir die Idee das der VMM nur die freien Bereiche verwaltet mit längerem Nachdenken immer besser gefällt. Die benutzten Bereiche meines linearen Adressraumes sind ja schon wo anders (z.B. in den LDTs der Prozesse) ausreichend gut gemanagt.

Das heißt, ich darf mir ein Megabyte Speicher geben lassen und dann in einem Befehl die mittleren 333 KB freigeben? Seltsames Design.

Wenn der VMM nur die freien Bereiche verwaltet sollte sowas tatsächlich möglich sein (ohne negative Folgen), ob das auch sinnvoll ist sei mal dahin gestellt.

Wo siehst Du da einen Durchgriff? VMM und SlabAllocator sind auf einer Ebene und (leider) wechselseitig voneinander abhängig. Der SlabAllocator wird (neben dem VMM) von den verschiedenen Teilen im Kernel benutzt (er stellt ja den Kernel-Heap zur Verfügung) und der User-Space benötigt Segmente und holt sich diese vom VMM (natürlich über Kernel-Funktionen die zur Verwaltung der Segmente wieder den SlabAllocator benötigen). Ich sehe darin keine Probleme, wichtig ist nur das wenn SlabAllocator und VMM sich gegenseitig aufrufen der jeweils eigene Lock frei ist damit eben kein Dead-Lock entsteht.

Wenn man das so betrachtet, dann sind Slab-Allocator und VMM ein monolithischer Blob. Solange man dann nicht behauptet, dass es verschiedene Ebenen seien (wie ich es tue), dann ist das auch eine Lösung und das hatte das auch so gekennzeichnet.

Ich bin da nicht der Meinung das SlabAllocator und VMM ein monolithischer Block sind, schon weil ich jeden von beiden unabhängig vom anderen durch eine völlig andere Implementierung austauschen kann so lange die offizielle API nach oben gleich bleibt und auch die Randbedingen, wie das jeder seinen eigenen Lock freigeben muss wenn er den anderen aufrufen möchte, eingehalten werden (also void* kmalloc(uint objectsize,bool isVMM)/free(void* obj) beim Heap und void* vmalloc(size_t size,size_t allignment,uint attribute)/vfree(void* obj,size_t size) für den VMM, ja wenn man im VMM nur die freien Bereiche verwaltet dann muss man beim vfree auch die Größe des zu befreienden Blocks korrekt mitgeben was innerhalb meines Kernels aber auch absolut kein Problem sein dürfte).

Sonst legt ein malloc(2TB, MAP_NOW) für hinreichend große Festplatte dein System für mehrere Stunden vollständig lahm.

Wenn nur 4GB physicher RAM noch frei sind dann darf ein malloc(2TB, MAP_NOW) trotzdem nicht versuchen die gesamten 2TB mit physischen Pages zu hinterlegen, das wäre auch offensichtlicher Schwachsinn. Vielmehr muss einfach 2TB des Swapp-Space für diesen Bereich reserviert werden und fertig. Wenn auch mit dem Swapp-Space keine 2TB mehr verfügbar sind dann muss NULL zurück kommen. Offensichtlich unsinnige Anforderungen darf ein OS auch nicht ausführen!

Mach das mal unter einem normalen Betriebssystem und schaue, wieviel RAM du rauskriegst, wenn du (a) immer 4k-Blöcke alloziierst und (b) alles an einem Stück haben möchtest. Beobachte bitte die Performance des Systems in beiden Fällen... mich würde interessieren, ob die bekannten Betriebssysteme mit so einer Workload klarkommen oder nicht.

Ich vermute das die meisten aktuellen/bedeutenden OSe da zumindest Schwächen zeigen auch wenn zu hoffen ist das keines dieser OSe damit in ernste Schwierigkeiten gerät. Entweder wird der Prozess gekillt oder das OS lahmt ein klein wenig (theoretisch noch nicht mal das, weil ja alle anderen Prozesse und der Kernel selber davon eigentlich nicht negativ beeinflusst werden dürften).

Die Frage ist, ob das System als Ganzes dann noch benutzbar und vor allem stabil bleibt (dann ist es auch DoS-sicher) oder ob dann Grenzfälle und race conditions auftreten, die dann Bugs triggern. Das ist für die Qualität eines OS mMn wichtiger

Full ACK!

auch, wenn es hier nur um ein Hobby geht.

"Hobby" ist keine Ausrede für schlechte Software.

Wann tritt denn dein OOM-Killer in Kraft? Wenn der RAM [ohne Plattencache] voll ist, wenn ein Prozess mehr RAM möchte als physisch vorhanden oder wenn die Festplatte wegen Swap voll ist? Ist das System überhaupt noch benutzbar, wenn es swappt? (Mein Linux bricht komplett zusammen, wenn der RAM nahezu voll ist und der Auslagerungsmarathon losgeht. Je schneller der OOM-Killer dann zuschlägt, umso eher läuft das System überhaupt wieder.)

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Dem muss ich erst mal zustimmen. Ich frage mich da auch was ein "OOM-Killer" eigentlich machen soll, das einzigste was ich mir vorstellen kann ist das es bestimmte Prozesse gibt die ihren Speicher, auf Anforderung vom Kernel, wieder freigeben können. Der Cache im VFS wäre da ein Beispiel, aber mehr fällt mir dazu auch nicht ein.

Aber wie schaffst du es das dein Linux einbricht (bzw. was verstehst du darunter). Ich habe das noch nicht (wieder) erlebt.

Das würde mich auch mal interessieren.
Kleines Gegenbeispiel: nehmen wir mal an wir hätten auf einem PC mit 512MB RAM ein Officeprogramm das eine 1GB große Wörterdatenbank für die Rechtschreibkontrolle besitzt, da im aktuellen Text ja wohl kaum alle möglichen Worte vorkommen dürfte diese Datenbank nur sehr spärlich benutzt werden so das es hier reicht wenn nur wenige Prozent der Pages tatsächlich im physischen RAM liegen. Mir ist klar das dieses Beispiel nicht ganz real ist aber es wäre eine Situation in der mehr virtueller RAM tatsächlich benötigt wird als physischer RAM vorhanden ist und trotzdem beim normalen Arbeiten keine Page eingelagert oder ausgelagert werden müsste.
(@svenska: Unter anderem wegen solcher Szenarien bin ich der Meinung das segmentweises Swappen keinen Sinn macht.)

Ich sags erstmal so, ich sehe den Zweck eines OS programmieren nicht darin, ein schon vorhandenes nachzuprogrammieren, also musst du auch mal was machen was nicht normal ist.

Sehr gutes Argument. (auch wenn eine ordentliche User-Space-malloc-Implementierung eher große Brocken an virtuellem Speicher holen sollte, ist einfach praktischer)

Ich denke auch an die Fälle die direkt meine OS-API und nicht die libc nutzen.

Ein Programm das direkt Deine OS-API benutzt weiß auch wie es das am besten tun sollte um ein Optimum an Performance zu holen (wenn es das nicht wollte könnte es auch gleich bei malloc bleiben).

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Also geht das System komplett kaputt.

Quatsch, nur ein Programm wird sich (hoffentlich mit einer ordentlichen Fehlermeldung) beenden oder irgendeine Aktion nicht korrekt ausführen, weil es bei irgendeinem malloc NULL zurück bekommen hat. Wenn der Speicher (inklusive Swapp) endgültig zu Ende ist dann passiert sowas schon mal. Aber das OS bleibt stabil und das zählt.


Grüße
Erik

[Svenska]

Ich bin bisher ganz gut damit ausgekommen, nur die freien Bereiche zu speichern und habe noch keinen Nachteil davon getragen (der etwas anderes rechtfertigen würde).

Ich muss ehrlich sagen das mir die Idee das der VMM nur die freien Bereiche verwaltet mit längerem Nachdenken immer besser gefällt. Die benutzten Bereiche meines linearen Adressraumes sind ja schon wo anders (z.B. in den LDTs der Prozesse) ausreichend gut gemanagt.

Klar, in meinem Kopf wird das halt zentral im VMM gemanagt und dafür ist es wichtig, dass es da eine Übersicht gibt.

Ich bin da nicht der Meinung das SlabAllocator und VMM ein monolithischer Block sind, schon weil ich jeden von beiden unabhängig vom anderen durch eine völlig andere Implementierung austauschen kann so lange die offizielle API nach oben gleich bleibt und auch die Randbedingen, wie das jeder seinen eigenen Lock freigeben muss wenn er den anderen aufrufen möchte, eingehalten werden (also void* kmalloc(uint objectsize,bool isVMM)/free(void* obj) beim Heap und void* vmalloc(size_t size,size_t allignment,uint attribute)/vfree(void* obj,size_t size) für den VMM, ja wenn man im VMM nur die freien Bereiche verwaltet dann muss man beim vfree auch die Größe des zu befreienden Blocks korrekt mitgeben was innerhalb meines Kernels aber auch absolut kein Problem sein dürfte).

Du kannst in einem monolithischem Kernel auch Teile austauschen, wenn du sinnvolle Abstraktionen da drin hast. Deswegen bleibt der trotzdem monolithisch und als Ganzes trotzdem ein Blob (vgl. BSD-Kernel, auch wenn es dort inzwischen Module gibt).

Sonst legt ein malloc(2TB, MAP_NOW) für hinreichend große Festplatte dein System für mehrere Stunden vollständig lahm.

Wenn nur 4GB physicher RAM noch frei sind dann darf ein malloc(2TB, MAP_NOW) trotzdem nicht versuchen die gesamten 2TB mit physischen Pages zu hinterlegen, das wäre auch offensichtlicher Schwachsinn. Vielmehr muss einfach 2TB des Swapp-Space für diesen Bereich reserviert werden und fertig. Wenn auch mit dem Swapp-Space keine 2TB mehr verfügbar sind dann muss NULL zurück kommen. Offensichtlich unsinnige Anforderungen darf ein OS auch nicht ausführen!

Ich stelle mir die Dokumentation dazu gerade vor... "Wenn MAP_LAZY angegeben wird, so wird RAM erst zugewiesen, wenn er benötigt wird. Wenn MAP_NOW angegeben wird, wird der Speicher sofort zugewiesen, allerdings nur, wenn das System der Meinung ist, dass das so einfach möglich ist." Wenn du ein Flag bereitstellst, solltest du dieses Flag niemals ignorieren. Daher würde ich dort kein Flag angeben.

Jedes System erlaubt es dir, unsinnige Anforderungen auszuführen, solange sie möglich sind. Schließlich kannst du als Programmierer in der Regel garnicht abschätzen, ob sie unsinnig sind oder nicht. (Das NX-Bit verhindert das Ausführen von Daten und das ist gut. Aber ein JIT-Compiler benutzt das, obwohl der Gedanke an sich unsinnig ist. Präventiv verbieten bringt nichts.)

auch, wenn es hier nur um ein Hobby geht.

"Hobby" ist keine Ausrede für schlechte Software.

Aber durchaus ein Argument für beschränkte Software. Wichtig hierbei: Man muss die Grenzen kennen (und evtl. dokumentieren). Das gilt für mich aber grundsätzlich - das Wissen um das Nichtwissen ist wichtiger, als das Wissen selbst.

Zumal du ein OpenSolaris mit ZFS eher nicht auf deinem Router laufen lassen magst, oder Windows 3.1 nativ im Rechenzentrum. Das sind solche Grenzen.

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Dem muss ich erst mal zustimmen. Ich frage mich da auch was ein "OOM-Killer" eigentlich machen soll, das einzigste was ich mir vorstellen kann ist das es bestimmte Prozesse gibt die ihren Speicher, auf Anforderung vom Kernel, wieder freigeben können. Der Cache im VFS wäre da ein Beispiel, aber mehr fällt mir dazu auch nicht ein.

Wenn ein Prozess eben nicht auf malloc()=NULL reagiert, sondern munter weitermacht (mit eventuell kleineren Größen), dann ist das eine Endlosschleife oder systematisches Ausbluten des RAMs. Der OOM-Killer tritt dann in Kraft, wenn der Kernel für sich selbst Speicher benötigt, z.B. Puffer um Hardware anzusteuern oder Baumknoten für den VMM. Dieser Speicher ist u.U. wichtig, um Swapping überhaupt zu ermöglichen (man stelle sich ein network block device via TCP/IP vor) und daher grundsätzlich wichtiger als jedes Userspace-Programm. Dann werden nach Speicherverbrauch in absteigender Reihenfolge sortiert die Prozesse abgeschossen, um das System am Laufen zu halten.

Ich habe noch keinen OOM-Killer und auch noch kein Swapping, bei mir können dann einfach irgendwelche Speicheranforderungen nicht mehr gemacht werden

Also geht das System komplett kaputt.

Quatsch, nur ein Programm wird sich (hoffentlich mit einer ordentlichen Fehlermeldung) beenden oder irgendeine Aktion nicht korrekt ausführen, weil es bei irgendeinem malloc NULL zurück bekommen hat. Wenn der Speicher (inklusive Swapp) endgültig zu Ende ist dann passiert sowas schon mal. Aber das OS bleibt stabil und das zählt.

Und was ist, wenn der Kernel zum Funktionieren Speicher braucht? Das kann man nicht ablehnen, denn es würde zum DoS und/oder zum Absturz führen (wenn Hardware dann halt woanders hinschreibt, weil der Treiber damit nicht rechnet).

Kleines Gegenbeispiel: nehmen wir mal an wir hätten auf einem PC mit 512MB RAM ein Officeprogramm das eine 1GB große Wörterdatenbank für die Rechtschreibkontrolle besitzt, da im aktuellen Text ja wohl kaum alle möglichen Worte vorkommen dürfte diese Datenbank nur sehr spärlich benutzt werden so das es hier reicht wenn nur wenige Prozent der Pages tatsächlich im physischen RAM liegen. Mir ist klar das dieses Beispiel nicht ganz real ist aber es wäre eine Situation in der mehr virtueller RAM tatsächlich benötigt wird als physischer RAM vorhanden ist und trotzdem beim normalen Arbeiten keine Page eingelagert oder ausgelagert werden müsste.
(@svenska: Unter anderem wegen solcher Szenarien bin ich der Meinung das segmentweises Swappen keinen Sinn macht.)

Beim Einlesen der Datenbank geht ein Swapmarathon los, da du als Anwendung ja eher keine Lust hast, die Daten von Platte direkt in Swapspace zu laden. Also wirst du dich hüten, die gesamte DB im RAM halten zu wollen und richtest deine DB-Struktur so ein, dass du schon im Voraus weißt, welche Teile der DB du benötigen wirst und lädst diese bei Bedarf von Platte.

Um das ganze performant zu machen, gibt es präventives Readahead, welches im Blocklayer ausgeführt wird. Die DB hängt dann nicht vollständig im RAM der Anwendung, sondern (eventuell komprimiert) im Plattencache. Damit spart man sich die I/O-Zugriffszeit für das Teile-Laden, die I/O-Zeit für das Swapping und gleichzeitig Unmengen an RAM, weil die ungenutzten Daten nicht im RAM liegen müssen. (Plattencache ist semi-freier Speicher).

Außerdem kann man als Anwendung das auch so bauen, dass man einen großen virtuellen Block für die ganze DB anfordert und den mit den benötigten Daten füllt. Das wird man natürlich nicht mit MAP_NOW machen, sondern mit MAP_LAZY... und das ganze Konstrukt fällt performanceseitig vollständig zusammen, wenn die DB-Größe auch nur in die Nähe der RAM-Größe kommt. Darum ist das unüblich für große DBs.

Gruß,
Svenska

[FlashBurn]

Du kennst doch die Anfangsadressen dieser Nachbarelemente nicht, also kannst du danach nicht suchen, oder irre ich da?

Jein

Deswegen hatte ich ja ein konkrettes Bsp gebracht. Ich mache einfach nochmal eins.

Du willst die ID 15 freigeben und fängst mir der Wurzel des Baums an.

Die Wurzel hat den Wert 20, d.h. deine Nachbarn, so fern vorhanden, können sich nur noch im linken Teil-Baum befinden.
Da 20 > 15 gehst du nach links.
Der nächste Knoten hat den Wert 10 (und size 1), d.h. deine Nachbarn, so fern vorhanden können sich nur noch im rechen Teil-Baum befinden.
Da 10 < 15 gehst du nach rechts.
Der nächste Knoten hat den Wert 16, d.h. du hast einen Nachbarn gefunden und der andere Nachbar kann sich, so fern vorhanden, nur noch im linken Teilbaum befinden.
Da 16 > 15 gehst du nach links.
Der nächste Knoten hat den Wert 14 (und size 1), d.h. du hast deinen anderen Nachbarn gefunden und musst jetzt aber trotzdem noch bis zum Ende des Baums durchgehen (weil der Code ja allgemein bleiben soll).
Da 14 < 15 gehst du nach rechts.
Der nächste Knoten ist NULL (also keiner vorhanden), du bist also fertig und die ID darf freigegeben werden und du hast sogar deine beiden Nachbarn gefunden.

Ich hoffe du kannst es jetzt nachvollziehen. Du musst die Start-Werte deiner Nachbarn nicht kennen um sie zu finden. Denn sie können nur auf deinem Suchweg sein!

Außerdem bringt das nur bei auf 4k ausgerichteten Speicherblöcken was, da für den dritten Teil eine Anfangsadresse mit Alignment da sein muss.

Und genau darum geht es auch nur bei einem VMM, der verwaltet immer Bereiche die an PAGE_SIZE aligned sind und die ein vielfaches von PAGE_SIZE haben.

Ein Userspace-Programm kann aber Teile des Kernel-Speichers freigeben, wenn dieser Bereich im Userspace-Programm gemappt ist.

Richtig, da ich aber im Moment eh nur eine derartig Page im UserSpace habe und das die letzte ist, kann ich auch ganz einfach meine Map eine Page kleiner machen und falls ich wirklich mal sowas derartiges brauchen sollte, dann will ich das so implementieren, das du einer Map eine andere Map hinzufügen kannst. Dann kannst du die Löcher zw. den Maps auch nicht freigeben.

Was anderes, überprüft ihr ob das Programm versucht seinen eigenen Code freizugeben?

Du willst also einen Baum pro Prozess haben?

Sorry, aber das ist wieder so eine Frage, wo ich mich dann frage, ob du das mit dem VMM wirklich verstanden hast

Ich will nicht ich muss einen Baum pro Prozess haben. Denn in dem Sinne haben ja alle Prozesse den gleichen Adressraum (ich meine damit der geht immer von 0 - 3GB) und da musst du nunmal einen Baum pro Prozess nehmen.

Diese Interfaces sollte eigentlich nur die libc nutzen (und Treiber).

Falsch! Z.b. GUI-Programme werden entweder ne Library nutzen (welche dann die jeweilige OS-API nutzen wird) oder wird direkt die OS-API nutzen.
Ich behaupte mal das gerade sowas wie Spiele und wahrscheinlich auch bzw. gerade DBs kein malloc, jedenfalls nicht für größere Daten nutzen wird. Die werden immer nen eigenen Allocator nutzen oder halt im Falle der DB einfach den VMM des OS, weil die Daten werden nachher eh in 4KB Blöcken gespeichert, da kann man den Speicher auch gleich so anfordern.

Also wenn Deine malloc-Implementierung (für die User-Space-libc) wirklich in 16kB-Häppchen den virtuellen Speicher holt dann würde ich da tatsächlich das Prädikat "kaputt" benutzen. Sorry, aber sowas macht man nicht.

D.h. wenn ich ein kleines Sinnlos-Programm schreibe (wie man es oft an der Uni macht), dann wird ein "new int" gleich 16MB vom System holen (oder setzt was anderes ein, was nicht auf dem Stack passiert)?
Das finde ich kaputt

Dieser Magazin-Mechanismus würde bei meinem nichtunterbrechbaren Kernel sogar besser funktionieren weil ich dafür keinerlei Lock o.ä. benötige.

Der Sinn und Zweck des ganzen war, das man auch in jedem anderen Kernel keinen Lock benötigt, sondern einfach nur die Ints ausmacht.

Wenn ein Prozess eben nicht auf malloc()=NULL reagiert, sondern munter weitermacht (mit eventuell kleineren Größen), dann ist das eine Endlosschleife oder systematisches Ausbluten des RAMs.

Wenn er auf ein malloc()=NULL nicht reagiert greift er endweder auf Speicher zu wo er es nicht darf (wird also gekillt) oder er wird zu einer endlos Schleife. Beides sehe ich nicht als Problem an und auch der RAM wird so nicht ausgeblutet.
Wenn er mit kleineren Größen weitermacht, ist es das selbe als wenn ich noch andere Prozesse starte die auch RAM brauchen, sehe ich also auch nicht das Problem.

Und was ist, wenn der Kernel zum Funktionieren Speicher braucht? Das kann man nicht ablehnen, denn es würde zum DoS und/oder zum Absturz führen (wenn Hardware dann halt woanders hinschreibt, weil der Treiber damit nicht rechnet).

Das nenne ich mal kaputtes Design

Also mein Kernel kommt damit klar, wenn er Speicher braucht und dem nicht nachgekommen werden kann. Genau aus dem Grund ist mein neuer Code ja etwas schwieriger zu lesen und der Code der noch benutzt wird ist deswegen auch eigentlich fehlerhaft (der kommt damit zwar auch klar, aber dadurch gibt es dann Memory-Leaks).

Du musst doch Speicher eh immer vorher allokieren, also kannst du auch nicht einfach welchen benutzen ohne das du ihn allokiert hast und wenn das Allokieren schon nicht ging, gibst du einfach nen Fehler zurück und fertig!

[erik.vikinger]

Hallo,

Ich muss ehrlich sagen das mir die Idee das der VMM nur die freien Bereiche verwaltet mit längerem Nachdenken immer besser gefällt. Die benutzten Bereiche meines linearen Adressraumes sind ja schon wo anders (z.B. in den LDTs der Prozesse) ausreichend gut gemanagt.

Klar, in meinem Kopf wird das halt zentral im VMM gemanagt und dafür ist es wichtig, dass es da eine Übersicht gibt.

Ja, da bei mir die User-Space-Prozesse auch nie direkt mit dem VMM in Kontakt kommen sondern ihren Speicher immer über (Kernel kontrollierte) Segmente managen müssen kann es auch nicht passieren das der VMM mit unsinnigen/fehlerhaften Parametern benutzt wird. Bei FlashBurn ist es wohl so das er für jeden Prozess (also jeden virtuellen Adressraum) eine eigene Verwaltung will und wenn dort ein Prozess 30 Pages anfordert und die mittleren 10 frei gibt dann ist das auch in Ordnung denn wenn der Prozess später auf diese mittleren Pages zugreift gibt es eine Exception und der Exception-Handler kann beim VMM klar ermitteln das dieser Bereich frei ist und killt den Prozess. Es ist zwar eine bizarre Möglichkeit einfach Löcher in den virtuellen Adressraum zu schießen (oder auch mehrere hintereinander liegende Bereiche die einzeln angefordert wurden mit einem einzigen free wieder los zu werden) aber grundsätzlich entsteht daraus erst mal keine negative Konsequenz.

Du kannst in einem monolithischem Kernel auch Teile austauschen, wenn du sinnvolle Abstraktionen da drin hast. Deswegen bleibt der trotzdem monolithisch und als Ganzes trotzdem ein Blob (vgl. BSD-Kernel, auch wenn es dort inzwischen Module gibt).

Okay, aber dann sage auch nicht mehr das ich da durch verschiedene Layer hindurch greife. Modularisieren will ich meinen Kernel nur auf Quell-Code-Ebene, wenn er kompiliert ist ist er nur noch ein Stück.

Ich stelle mir die Dokumentation dazu gerade vor... "Wenn MAP_LAZY angegeben wird, so wird RAM erst zugewiesen, wenn er benötigt wird. Wenn MAP_NOW angegeben wird, wird der Speicher sofort zugewiesen, allerdings nur, wenn das System der Meinung ist, dass das so einfach möglich ist." Wenn du ein Flag bereitstellst, solltest du dieses Flag niemals ignorieren. Daher würde ich dort kein Flag angeben.

Also für ein Flat-Memory-System empfinde ich dieses Flag schon als sinnvoll. Der SlabAllocator (der im User-Space das malloc anbietet) wird für neue Slabs wohl eher MAP_LAZY benutzen weil er weiß das es unwahrscheinlich ist das der neue Slab sofort komplett benutzt wird aber wenn er mit einem malloc(100MByte) konfrontiert wird, was er mit Sicherheit nicht mehr über Slabs macht sondern direkt virtuellen Speicher für diese Anforderung hollt, wir er wohl eher MAP_NOW benutzen da damit zu rechnen ist dass das Programm diesen neuen Block auch wirklich sofort benutzen will. Ich sehe dieses Flag auch eher als freundliche Bitte an das OS um ihm die Möglichkeit zu geben sich so zu verhalten das die Applikation möglichst performant arbeiten kann. Dieses Flag ist mMn kein absoluter Befehl dem das OS unbedingt gehorchen muss.

"Hobby" ist keine Ausrede für schlechte Software.

Aber durchaus ein Argument für beschränkte Software.

Okay, das ist richtig.

das Wissen um das Nichtwissen ist wichtiger, als das Wissen selbst.

Vielleicht nicht unbedingt wichtiger aber zumindest genau so wichtig.

Wenn ein Prozess eben nicht auf malloc()=NULL reagiert

Dann ist er fehlerhaft, die Rückgabe von malloc muss immer geprüft werden!

sondern munter weitermacht (mit eventuell kleineren Größen)

Wenn der Prozess statt dessen versuch mit weniger Speicher aus zu kommen dann ist das IMHO ein guter Kompromiss. Schließlich hat der User diesen Prozess ja gestartet weil er will das der Prozess eine bestimmte Aufgabe erledigt und das sollte auch erst mal nach besten Möglichkeiten versucht werden.

dann ist das eine Endlosschleife oder systematisches Ausbluten des RAMs.

Dann ist das ein Bug im OS, die letzten Speicher-Reserven darf das OS nur noch für sich selber und für Prozesse benutzen die mit root-Rechten laufen. Wenn root dann 50 Shells startet und das System endgültig an die Wand fährt ist das einfach nur Dummheit von root aber wenn root gar keine Shell mehr starten kann (um z.B. andere Prozesse zu killen) dann ist das IMHO ein Bug im OS.

... und daher grundsätzlich wichtiger als jedes Userspace-Programm.

Okay, verstehe.

Dann werden nach Speicherverbrauch in absteigender Reihenfolge sortiert die Prozesse abgeschossen, um das System am Laufen zu halten.

Also bevor das System anfängt nach eigenem Gutdünken einfach beliebige Prozesse zu killen wäre es IMHO schon schön wenn root die Möglichkeit hat selber (mit Verstand) zu entscheiden welcher Prozess gekillt wird.

Und was ist, wenn der Kernel zum Funktionieren Speicher braucht?

Der Kernel braucht Speicher weil er eine Aufgabe erfüllen soll und diese Aufgabe kann eben nicht ausgeführt werden wenn es nicht genug Speicher dafür gibt. Bei mir bekommt jeder Syscall einen Rückgabewert der auch Fehlercodes darstellen kann und die User-Space-Programme dürfen das grundsätzlich nicht einfach ignorieren sondern müssen immer entsprechend reagieren.
Außerdem kann man da eine weitere Regel einführen:
Kernel-Speicher ist normalerweise nicht auslagerbar also immer davon abhängig das noch physischer RAM verfügbar ist. Der VMM muss einfach immer mitzählen wie viel nicht auslagerbarer Speicher zugewiesen wurde und wenn das mehr als 75% des real vorhandenen physischen RAM sind dann arbeitet der VMM nur noch im Dienste von root-Prozessen. Bei mir möchte ich sogar so weit gehen das Speicher von root-Prozessen (wozu auch alle Treiber und die Personality zählen) auch zu dem nicht auslagerbaren Speicher zählt, damit sowas wie ne Shell auch während eines extremen Swapp-Marathons noch funktionsfähig bleiben, das bedeutet natürlich das root-Prozesse immer möglichst sorgsam mit dem Speicher umgehen müssen (und root natürlich aufpassen muss was er alles startet, ne fette Datenbank wird man sicher nicht als root ausführen).

(wenn Hardware dann halt woanders hinschreibt, weil der Treiber damit nicht rechnet).

Wenn ein Treiber eine ungültige/falsche physische Adresse an eine HW-Komponente gibt dann ist das ein Bug im Treiber! Gerade ein Treiber darf ein NULL von malloc nicht ignorieren. Außerdem gehören Treiber IMHO nicht gerade zu den Programmen die einen ständig wechselnden Speicherbedarf haben, außer das da permanent Job-Descriptoren o.ä. alloziert und freigegeben werden (was in kBytes gemessen sicher nicht viel ist und somit von der malloc-Implementierung abgefangen werden sollte) dürfte sich am virtuellen Adressraum eines Treibers nicht viel tun (mal abgesehen davon das er die Nutzdaten eventuell per Shared-Memory o.ä. in seinen virtuellen Adressraum eingeblendet bekommt).

(@svenska: Unter anderem wegen solcher Szenarien bin ich der Meinung das segmentweises Swappen keinen Sinn macht.)

Beim Einlesen der Datenbank geht ein Swapmarathon los .....

Ich glaube Du hast nicht ganz verstanden was ich eigentlich ausdrücken wollte. Es geht mir nicht um Datenbanken o.ä. sondern um ein Szenario in dem ein Programm einen großen Bereich an virtuellem Speicher benötigt und diesen auch mit echten Daten befüllt aber dann zur weiteren Laufzeit nur einen kleinen Anteil davon tatsächlich benutzt, das bedeutet das von diesem Bereich durchaus ein hoher Anteil an Pages ausgelagert sein können ohne dass das negative Konsequenzen (für die Performance) hat. Das selbe trifft auch auf übliche Code-Bereiche zu, kaum ein Programm wird ständig all seinen Programm-Code ausführen.

Was anderes, überprüft ihr ob das Programm versucht seinen eigenen Code freizugeben?

Ja, jedes Segment das bereits in der Executable drin war (also .code , .const , .data und .tls_master) kann nicht freigeben werden, nur Segmente die zur Laufzeit angefordert werden können auch wieder freigegeben werden. Stack-Segmente (und thread-spezifische TLS-Segmente) können nur von KillThread freigegeben werden.

Also wenn Deine malloc-Implementierung (für die User-Space-libc) wirklich in 16kB-Häppchen den virtuellen Speicher holt dann würde ich da tatsächlich das Prädikat "kaputt" benutzen. Sorry, aber sowas macht man nicht.

D.h. wenn ich ein kleines Sinnlos-Programm schreibe (wie man es oft an der Uni macht), dann wird ein "new int" gleich 16MB vom System holen (oder setzt was anderes ein, was nicht auf dem Stack passiert)?
Das finde ich kaputt

Klar ist das doof wenn ein Miniprogramm gleich große Mengen an Speicher verbraucht aber wen stört das? Willst Du 100'000 solcher Programme parallel starten? Außerdem wird die libc schon oft genug malloc für eigene Sachen benutzen so das Dein "new int" auch nicht mehr viel macht. Nebst dessen das eine gute malloc-Implementierung sich dem dynamisch anpasst, die greift also nicht gleich beim ersten malloc(4) in die vollen sondern erst wenn das Programm auch wirklich viel Speicher will.

Der Sinn und Zweck des ganzen war, das man auch in jedem anderen Kernel keinen Lock benötigt, sondern einfach nur die Ints ausmacht.

In Kaptel 3.5 (auf Seite 7 oben rechts) von http://www.usenix.org/event/usenix01/full_papers/bonwick/bonwick.pdf (ich hoffe mal wir redeten immer vom selben Dokument) ist klar erklärt warum man sich für ein Lock entschieden hat.


Grüße
Erik

[FlashBurn]

aber wen stört das?

Mich

Ich sollte mal erwähnen das ich mein OS dahin trimmen möchte, das es mit 4-8MB RAM lauffähig ist. Mein Fern-Ziel ist dann mit diesem RAM auch eine GUI zu haben (Win3.11 und Win95 haben das ja auch hinbekommen und laut der Meinung vieler ist Win Schrott und MS unfähig ).

In Kaptel 3.5 (auf Seite 7 oben rechts) von http://www.usenix.org/event/usenix01/full_papers/bonwick/bonwick.pdf (ich hoffe mal wir redeten immer vom selben Dokument) ist klar erklärt warum man sich für ein Lock entschieden hat.

Ja wir reden vom selben Dokument.

Blöd nur, das bei mir Locks im Kernel grundsätzlich die Ints ausmachen, Real-Time ist auch kein Hindernis für mich und den letzten Punkt wüsste ich jetzt nicht wie ich ihn umgehen sollte, außer (wie du) grundsätzlich den Kernel nicht unterbrechbar zu machen.

Der Punkt ist aber das die Zeit ein cli und ein sti auszuführen wohl wesentlich kürzer ist, als wenn auf nem Single CPU System ständig die Threads gewechselt werden, weil der Thread der den Lock hält erstmal wieder an die Reihe kommen muss (bzw. müsste ich dann ja auch zw. Single und SMP System unterscheiden, was ich nicht mache und nicht will).

Interessant wird es erst auf nem SMP System. Denn da kann es durchaus passieren das ich ziemlich oft die Ints an und aus machen (in ganz kurzen Abständen). Das könnte dann doch ganz schön Zeit kosten, aber wie gesagt, sollte nicht so viel sein wie die Thread-Wechsel.

Zumal das bei mir die Regel ist, ein Lock (also Ints aus) wird nur da benutzt wo ich Pi mal Daumen sagen, kann das es weniger Zeit benötigt als die Zeit für 3 Thread-Wechsel.

[Svenska]

Du kennst doch die Anfangsadressen dieser Nachbarelemente nicht, also kannst du danach nicht suchen, oder irre ich da?

Jein [...] Ich hoffe du kannst es jetzt nachvollziehen. Du musst die Start-Werte deiner Nachbarn nicht kennen um sie zu finden. Denn sie können nur auf deinem Suchweg sein!

Aaahh!! Dann ist das natürlich sehr vorteilhaft.

Außerdem bringt das nur bei auf 4k ausgerichteten Speicherblöcken was, da für den dritten Teil eine Anfangsadresse mit Alignment da sein muss.

Und genau darum geht es auch nur bei einem VMM, der verwaltet immer Bereiche die an PAGE_SIZE aligned sind und die ein vielfaches von PAGE_SIZE haben.

Damit ist es aber für allgemeine Anwendungsfälle nutzlos, sich da einen Kopf drüber zu machen. Außerdem sollte sich ein Userspace-Programm nicht um Alignments kümmern müssen (es sei denn, es geht um Performance oder Ansteuerung einer Hardware), das heißt die API - solltest du sie im Userspace bereitstellen - exponiert hardwareabhängige Dinge und das ist schlecht.

Wenn du das nur innerhalb des Kernels nutzt, kannst du das natürlich tun. Sinnvoll finde ich das trotzdem nicht, da reicht für meine Verhältnisse ein naher realloc()-Verwandter hin.

Ein Userspace-Programm kann aber Teile des Kernel-Speichers freigeben, wenn dieser Bereich im Userspace-Programm gemappt ist.

Richtig, da ich aber im Moment eh nur eine derartig Page im UserSpace habe und das die letzte ist, kann ich auch ganz einfach meine Map eine Page kleiner machen und falls ich wirklich mal sowas derartiges brauchen sollte, dann will ich das so implementieren, das du einer Map eine andere Map hinzufügen kannst. Dann kannst du die Löcher zw. den Maps auch nicht freigeben.

Achso.

Was anderes, überprüft ihr ob das Programm versucht seinen eigenen Code freizugeben?

Das solltest du tun. Denn tust du es nicht, so stürzt das Programm in der nachfolgenden Anweisung ab (weil der Speicher nicht mehr vorhanden ist) und wenn du dann den Task killst, wird dein Kernel die vorhandenen Ressourcen freigeben wollen, was u.U. zu einem double-free() und damit zu einer Exception/Panic im Kernel führen kann.

Du willst also einen Baum pro Prozess haben?

Sorry, aber das ist wieder so eine Frage, wo ich mich dann frage, ob du das mit dem VMM wirklich verstanden hast

Hmm... Warum kann die Welt nicht einfach sein? Ich habe halt immernoch "globale" Ressourcen im Hinterkopf (eben I/O-Ports, GUIDs, ...) und da trifft das natürlich nicht zu. Stimmt, der virtuelle Adressraum ist per-process, kann sich aber mit anderen überschneiden. *seufz*

Diese Interfaces sollte eigentlich nur die libc nutzen (und Treiber).

Falsch! Z.b. GUI-Programme werden entweder ne Library nutzen (welche dann die jeweilige OS-API nutzen wird) oder wird direkt die OS-API nutzen.
Ich behaupte mal das gerade sowas wie Spiele und wahrscheinlich auch bzw. gerade DBs kein malloc, jedenfalls nicht für größere Daten nutzen wird. Die werden immer nen eigenen Allocator nutzen oder halt im Falle der DB einfach den VMM des OS, weil die Daten werden nachher eh in 4KB Blöcken gespeichert, da kann man den Speicher auch gleich so anfordern.

Anwendungen sollten niemals die OS-API direkt benutzen, weil sie das inhärent unportabel macht und außerdem dich dazu zwingt, deine Kernel-ABI (nicht nur die API!) stabil zu halten. Sonst funktionieren die Applikationen nicht mehr. Das ist ein Maintenance-Burden und ein Grund für schlechten Linux-Hersteller-Treibersupport - der Kernel garantiert eine einigermaßen stabile API, keine stabile ABI. Darum müssen die Treiber auch immer an die aktuellen Kernel-Interna angepasst werden und das will kein Hersteller selbst tun (vgl. NVidia). Für den Userspace wäre das eine Katastrophe, nach jedem Kernelupdate müsstest du alle Anwendungen neu kompilieren.

Üblicherweise abstrahiert man das also in Libraries raus, diese sind die einzigen Nutzer der OS-API. Was Datenbanken angeht, so organisieren diese ihren Speicher selbst, das hat mit dem VMM erstmal nichts zu tun (schließlich soll ein MySQL auf mehreren Plattformen laufen können, und für Apache gibt es die Apache Portable Runtime, APR) und 3D-Spiele greifen auch nicht auf den Kernel direkt zu, sondern über Libraries wie OpenGL oder DirectX und damit über Bindings. Selbst 2D-Programme nutzen das X11-Protokoll nicht direkt, sondern die Xlib (oder darauf aufbauende Systeme wie Motif) oder Toolkits wie Qt oder GTK.

Wenn du Kernel-Interfaces änderst, brauchst du dann nur die Libraries anpassen, solange deren ABI stabil bleibt, funktionieren auch Binärprogramme weiter.

Also wenn Deine malloc-Implementierung (für die User-Space-libc) wirklich in 16kB-Häppchen den virtuellen Speicher holt dann würde ich da tatsächlich das Prädikat "kaputt" benutzen. Sorry, aber sowas macht man nicht.

D.h. wenn ich ein kleines Sinnlos-Programm schreibe (wie man es oft an der Uni macht), dann wird ein "new int" gleich 16MB vom System holen (oder setzt was anderes ein, was nicht auf dem Stack passiert)?
Das finde ich kaputt

Hä? Du solltest die Blockgröße schon von der angeforderten Größe abhängig machen. Ein "new int" sollte also maximal eine 4KB-Page zurückgeben, ein "new buf[16M]" sollte 4 Pages je 4MB zurückgeben...

Dieser Magazin-Mechanismus würde bei meinem nichtunterbrechbaren Kernel sogar besser funktionieren weil ich dafür keinerlei Lock o.ä. benötige.

Der Sinn und Zweck des ganzen war, das man auch in jedem anderen Kernel keinen Lock benötigt, sondern einfach nur die Ints ausmacht.

Geht das bei SMP? Ints ausmachen wirkt doch nur für jede CPU...

Wenn ein Prozess eben nicht auf malloc()=NULL reagiert, sondern munter weitermacht (mit eventuell kleineren Größen), dann ist das eine Endlosschleife oder systematisches Ausbluten des RAMs.

Wenn er auf ein malloc()=NULL nicht reagiert greift er endweder auf Speicher zu wo er es nicht darf (wird also gekillt) oder er wird zu einer endlos Schleife. Beides sehe ich nicht als Problem an und auch der RAM wird so nicht ausgeblutet.
Wenn er mit kleineren Größen weitermacht, ist es das selbe als wenn ich noch andere Prozesse starte die auch RAM brauchen, sehe ich also auch nicht das Problem.

Code: [Auswählen]

void* p = NULL;
int size=1024*1024*1024;
while(true) {
    p = malloc(size, MAP_NOW); /* alternativ den erfolgreich reservierten Speicher mit 0xFF füllen, um Mapping zu erzwingen */
    if( p == NULL ) {
        size = size/2;
    }
}
Würde also so lange weitermachen, bis der reale Speicher bis aufs letzte Byte gefüllt ist. Was passiert, wenn dir im Kernel ein malloc()==NULL passiert? Du hast keinen OOM-Killer.

Also mein Kernel kommt damit klar, wenn er Speicher braucht und dem nicht nachgekommen werden kann. Genau aus dem Grund ist mein neuer Code ja etwas schwieriger zu lesen und der Code der noch benutzt wird ist deswegen auch eigentlich fehlerhaft (der kommt damit zwar auch klar, aber dadurch gibt es dann Memory-Leaks).

Also braucht dein Kernel keinen dynamisch reservierten Speicher, und auch alle Hardwaretreiber (jetzt und in Zukunft) alloziieren sämtlichen benötigten Speicher bereits beim Laden?

Du musst doch Speicher eh immer vorher allokieren, also kannst du auch nicht einfach welchen benutzen ohne das du ihn allokiert hast und wenn das Allokieren schon nicht ging, gibst du einfach nen Fehler zurück und fertig!

Was aber, wenn du übers Netzwerk swapst, dein TCP/IP-Stack aus Speichermangel größtenteils auf Platte liegt, der RAM randvoll ist und ein seltsames Paket im TCP/IP-Stack landet und verarbeitet werden muss? Du müsstest erstmal Teile deines TCP/IP-Stacks wieder in den RAM laden, wozu du Zeugs auslagern müsstest, was du nicht kannst, weil es den TCP/IP-Stack erfordert.

Da kann man genug Beispiele konstruieren, die unter Last zu seltsamen Effekten führen, weil du u.U. gewisse Randfälle nicht bedacht hast. (Darum ist Swapping in ein Swapfile via NFS oder direkt in ein NBD noch nicht besonders lange stabil und auch Swapfiles im Dateisystem erst seit Kernel 2.6 so performant wie Swap-Partitionen. Das liegt an ebendiesen Zusammenhängen zwischen Speicherverwaltung und Rest des Systems.)

Und das Verhalten eines Systems unter diesen Randbedingungen muss immer absolut stabil sein, auch auf Kosten von Applikationen.

Also für ein Flat-Memory-System empfinde ich dieses Flag [MAP_NOW, MAP_LAZY] schon als sinnvoll. Der SlabAllocator (der im User-Space das malloc anbietet) wird für neue Slabs wohl eher MAP_LAZY benutzen weil er weiß das es unwahrscheinlich ist das der neue Slab sofort komplett benutzt wird aber wenn er mit einem malloc(100MByte) konfrontiert wird, was er mit Sicherheit nicht mehr über Slabs macht sondern direkt virtuellen Speicher für diese Anforderung hollt, wir er wohl eher MAP_NOW benutzen da damit zu rechnen ist dass das Programm diesen neuen Block auch wirklich sofort benutzen will. Ich sehe dieses Flag auch eher als freundliche Bitte an das OS um ihm die Möglichkeit zu geben sich so zu verhalten das die Applikation möglichst performant arbeiten kann. Dieses Flag ist mMn kein absoluter Befehl dem das OS unbedingt gehorchen muss.

Naja, ich als Anwendungsprogrammierer erwarte schon von einem Flag, dass es exakt das tut, was ich möchte und nichts anderes. Daher würde ich eine Automatik machen (MAP_NOW wenn <16M, MAP_LAZY wenn größer). Ich bin der Meinung, dass kleine Blöcke sofort benutzt werden und große Blöcke nicht/teilweise. Der Slab-Allocator holt sich ja nur darum eine begrenzte Anzahl an Pages im Voraus, damit es schnell wird, Pagefaults sind aber langsam.

Alternativ kann man das Flag anbieten, aber den gesamten Request fehlschlagen lassen, wenn es nicht geht. Niemals so, dass ich ein Flag explizit angebe und es dann ignoriert wird.

dann ist das eine Endlosschleife oder systematisches Ausbluten des RAMs.

Dann ist das ein Bug im OS, die letzten Speicher-Reserven darf das OS nur noch für sich selber und für Prozesse benutzen die mit root-Rechten laufen. Wenn root dann 50 Shells startet und das System endgültig an die Wand fährt ist das einfach nur Dummheit von root aber wenn root gar keine Shell mehr starten kann (um z.B. andere Prozesse zu killen) dann ist das IMHO ein Bug im OS.

Sehe ich etwas anders, denn die Größe der "letzten Reserven" hängt von root ab. Wenn er nur "bash", "ps" und "kill" nutzen möchte, mag das sein - aber eventuell möchte er erstmal seine X11-Umgebung mit KDE starten, um darin nachzuschauen, was überhaupt kaputt ist... Daher bin ich der Meinung, dass - sofern im Kernel kein Speicher mehr da ist - der Prozess mit dem größten Speicherverbrauch gekillt werden sollte.

Dann werden nach Speicherverbrauch in absteigender Reihenfolge sortiert die Prozesse abgeschossen, um das System am Laufen zu halten.

Also bevor das System anfängt nach eigenem Gutdünken einfach beliebige Prozesse zu killen wäre es IMHO schon schön wenn root die Möglichkeit hat selber (mit Verstand) zu entscheiden welcher Prozess gekillt wird.

Das unterscheidet ihn von einem OOM-Killer, richtig. Man kann ja beides kombinieren. Allerdings ist ein Programm, welches so viel RAM für sich in Anspruch nimmt, dass es das System nahezu lahmlegt für den Rechner dann ohnehin ungeeignet und man sollte das Programm anpassen oder RAM nachstecken.

Ein System, was konstant am Anschlag lebt, sollte man überdenken.

Kernel-Speicher ist normalerweise nicht auslagerbar also immer davon abhängig das noch physischer RAM verfügbar ist. Der VMM muss einfach immer mitzählen wie viel nicht auslagerbarer Speicher zugewiesen wurde und wenn das mehr als 75% des real vorhandenen physischen RAM sind dann arbeitet der VMM nur noch im Dienste von root-Prozessen. Bei mir möchte ich sogar so weit gehen das Speicher von root-Prozessen (wozu auch alle Treiber und die Personality zählen) auch zu dem nicht auslagerbaren Speicher zählt, damit sowas wie ne Shell auch während eines extremen Swapp-Marathons noch funktionsfähig bleiben, das bedeutet natürlich das root-Prozesse immer möglichst sorgsam mit dem Speicher umgehen müssen (und root natürlich aufpassen muss was er alles startet, ne fette Datenbank wird man sicher nicht als root ausführen).

Wenn du allgemeine Treiber nutzt, ist das nicht möglich; deren Speicheranforderung kann sich stark unterscheiden, je nach Auslastung. Außerdem willst du wirklich 25% des RAMs für root reservieren? Das stelle ich mir grad in einem Rechenzentrum mit 64 GB RAM/Node vor...

(@svenska: Unter anderem wegen solcher Szenarien bin ich der Meinung das segmentweises Swappen keinen Sinn macht.)

Beim Einlesen der Datenbank geht ein Swapmarathon los .....

Ich glaube Du hast nicht ganz verstanden was ich eigentlich ausdrücken wollte. Es geht mir nicht um Datenbanken o.ä. sondern um ein Szenario in dem ein Programm einen großen Bereich an virtuellem Speicher benötigt und diesen auch mit echten Daten befüllt aber dann zur weiteren Laufzeit nur einen kleinen Anteil davon tatsächlich benutzt, das bedeutet das von diesem Bereich durchaus ein hoher Anteil an Pages ausgelagert sein können ohne dass das negative Konsequenzen (für die Performance) hat. Das selbe trifft auch auf übliche Code-Bereiche zu, kaum ein Programm wird ständig all seinen Programm-Code ausführen.

Ich hab das schon so verstanden. Ursprünglich ging es aber um die Verwaltung des virtuellen Speichers - jeder dort vorhandene Block wird (in meiner Welt) durch mehrere Pages ausgedrückt, d.h. die Verwaltung, welche Pages nun wirklich im RAM sind, liegt anderswo. Und wenn deine Rechtschreibprüfung jedes Wort in eine eigene Page (mit eigenem malloc) stopfen will, dann wird die Anwendung halt langsam. Der aktuelle Auslagerungszustand ist davon unabhängig und ich muss Blöcke auch nicht unbedingt vollständig ausgelagert haben.

Ich sollte mal erwähnen das ich mein OS dahin trimmen möchte, das es mit 4-8MB RAM lauffähig ist. Mein Fern-Ziel ist dann mit diesem RAM auch eine GUI zu haben (Win3.11 und Win95 haben das ja auch hinbekommen und laut der Meinung vieler ist Win Schrott und MS unfähig ).

Auf solch einem System wird aber kaum ein Prozess anfangen, 3GB virtuellen Speicher in 4KB-Häppchen zu alloziieren. Und selbst wenn, dann geht das eben nicht.

Zumal das bei mir die Regel ist, ein Lock (also Ints aus) wird nur da benutzt wo ich Pi mal Daumen sagen, kann das es weniger Zeit benötigt als die Zeit für 3 Thread-Wechsel.

Was passiert, wenn du (weils schnell geht) kein Lock benutzt und während der Arbeit an den Strukturen dein Thread unterbrochen wird - und bei SMP auf einer anderen CPU gleichzeitig an den Strukturen gearbeitet wird? Du solltest Locks lieber möglichst billig machen und an jeder erdenklichen Stelle ein Lock setzen, wo es potentiell krachen kann. Wenn immer nur ein Thread auf ein Lock zugreift [es also unnötig ist, z.B. Singlecore-Systeme], sollte es sogar (fast) schmerzlos sein.

Gruß,
Svenska

[FlashBurn]

Damit ist es aber für allgemeine Anwendungsfälle nutzlos, sich da einen Kopf drüber zu machen. Außerdem sollte sich ein Userspace-Programm nicht um Alignments kümmern müssen (es sei denn, es geht um Performance oder Ansteuerung einer Hardware), das heißt die API - solltest du sie im Userspace bereitstellen - exponiert hardwareabhängige Dinge und das ist schlecht.

Du und deine libc

Ich behaupte mal das jedes OS einen Syscall hast mit dem du Speicher allokieren kannst und das geht immer nur in vielfachen von PAGE_SIZE. Warum sollte sich auch der Kernel um alles was kleiner ist kümmern? Das macht dein malloc(), das wiederrum nutzt genau solch einen Syscall.

Wenn man nur ein kleines schnelles Programm oder einen eigenen Allocator schreiben will, wird man genau solch einen Syscall nutzen.

Das solltest du tun. Denn tust du es nicht, so stürzt das Programm in der nachfolgenden Anweisung ab (weil der Speicher nicht mehr vorhanden ist) und wenn du dann den Task killst, wird dein Kernel die vorhandenen Ressourcen freigeben wollen, was u.U. zu einem double-free() und damit zu einer Exception/Panic im Kernel führen kann.

Ich sags mal so, wenn das App scheiße baut und seinen eigenen Code freigibt, dann ne Exception bekommt und gekillt wird, wo ist das Problem?
Zu einem double-free() kann es bei mir nicht kommen. Ich hatte auch keine Lust mir ständig nen Kopf darüber zu machen wie oft ne Page gemappt ist und ob ich noch Copy-On-Write machen muss und sowas. Deswegen habe ich für jede Page (physische Adresse) nen Counter, wie oft die gemappt ist und wenn das mehr als 1 ist wird sie nicht freigegeben und wenn der Counter 1 ist dann wird sie erst freigegeben (und ist damit auch aus der PageTable raus).

Anwendungen sollten niemals die OS-API direkt benutzen, weil sie das inhärent unportabel macht und außerdem dich dazu zwingt, deine Kernel-ABI (nicht nur die API!) stabil zu halten. Sonst funktionieren die Applikationen nicht mehr.

Du solltest anfangen deinen Kopf von den ganzen Linux Sachen zu befreien

Ich hab nen Mikrokernel und da sollte sich die API nun wirklich nicht ändern und wenn sie es doch tut, dann so schlimm das du das auch über Libraries nicht abfangen kannst.

Das sich die API von nem monolithen öfter ändert kann ich nachvollziehen. Denn der bietet ja wesentlich mehr Services an.

3D-Spiele greifen auch nicht auf den Kernel direkt zu, sondern über Libraries wie OpenGL oder DirectX

Wir sind immernoch bei der Speicherverwaltung und da behaupte ich mal das die besseren Engines kein libc malloc() sondern ihren eigenen Allocator benutzen und dieser ruft direkt die Speicher-Funktionen vom OS auf (würde ich jedenfalls so machen, zwecks Performance).

Du solltest die Blockgröße schon von der angeforderten Größe abhängig machen.

Ich befürchte so langsam das entweder du oder ihr beide mich missverstanden haben Denn das ist doch genau das was ich die ganze Zeit sage.
Wenn ich malloc(4) aufrufe und malloc() keinen freien Speicher mehr hat, dann holt sich malloc() nicht 16MB, sondern nur 4KB an Speicher.
Wenn ich aber malloc(128000) aufrufe, dann werden nicht mehrere 4KB Aufrufe gemacht sondern ein Aufruf (an den Kernel) das ich 128KB haben will.

Geht das bei SMP? Ints ausmachen wirkt doch nur für jede CPU...

Dazu musst du wissen das jede CPU sozusagen ihren eigenen kleinen Cache hat und deswegen reicht es wenn du die Ints ausmachst, denn in dem Moment ist die CPU ja belegt und die anderen CPUs greifen auf ihre kleinen Caches zu. Dadurch kannst du dir das Locking sparen (so fern in diesem kleinen Cache was drin ist).

Also braucht dein Kernel keinen dynamisch reservierten Speicher

Doch, aber wenn du einen Syscall machst und der Kernel kann keinen Speicher mehr bekommen, dann wird halt ein Fehler zurück gegeben (vergleichbar mit malloc()= NULL).

Und selbst wenn, dann geht das eben nicht.

Mein reden

Was passiert, wenn du (weils schnell geht) kein Lock benutzt und während der Arbeit an den Strukturen dein Thread unterbrochen wird - und bei SMP auf einer anderen CPU gleichzeitig an den Strukturen gearbeitet wird? Du solltest Locks lieber möglichst billig machen und an jeder erdenklichen Stelle ein Lock setzen, wo es potentiell krachen kann. Wenn immer nur ein Thread auf ein Lock zugreift [es also unnötig ist, z.B. Singlecore-Systeme], sollte es sogar (fast) schmerzlos sein.

Ich hätte wahrscheinlich noch hinzufügen sollen, das wenn kein Lock benutzt wird, eine Semaphore benutzt wird, aber die lohnt sich halt erst, wenn der kritische Bereich wirklich lange dauert (meine Meinung und ich weiß das erik das anders sieht).