Nachrichten

501

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 11. November 2010, 11:00 »

Aber Du bist doch so sehr für einen unterbrechbaren Kernel eingetreten und wenn Du HW-IRQs im Kernel willst dann sind Exceptions auch nicht mehr schlimm.

Das sind für mich 2 Paar Schuhe.

Das eine (HW-IRQs) sind einfach nur Unterbrechungen, wie sie in jedem UserApp auch vorkommen und das andere (Exceptions) sind Fehler! Letztere möchte ich nicht im Kernel behandeln, denn Exception könnte bedeuten das ich den Fehler nicht behandeln kann und das Programm muss gekillt werden, versuch das mal mit deinem Kernel

Eine Exception im Kernel heißt bei mir grundsätzlich PANIC().

502

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 11. November 2010, 10:57 »

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!

503

Lowlevel-Coding / Re:SMP und die damit verbundenen Probleme

« am: 10. November 2010, 21:32 »

Wieder mal nen OnTopic Beitrag.

Da wir ja in dem anderen Thread mal wieder schön streiten bin ich wieder mal auf ein Problem gestoßen was ich nicht so richtig einordnen kann.

Es geht darum das man erstmal nur einen Bereich im virtuellen Adressraum reserviert und diesen erst später mit physischen Speicher hinterlegt (erst wenn das erste mal auf die Page zugefgriffen wird, gilt also auch für Stacks die dynamisch wachsen können).
Jedes Mal wenn ein solcher PageFault aufgetreten ist und man eine Page gemappt hat, muss man ja auch den TLB-Eintrag invalidieren.
Ich behaupte mal dass das zu tierischen Performance Problemen auf SMP Systemen führen kann, weil da jedes Mal jede CPU unterbrochen wird.

Wie seht ihr das?

Eine andere Sache, ich habe mal irgendwo was gelesen das wenn ein PageFault zwecks aus dem Speicher lesen (und die Page halt noch nicht gemappt ist) erstmal nur eine Page die nur "0" enthält mappt und erst wenn dann auch darauf geschrieben wird, wird ne "normale" Page gemappt.

Was ist davon zu halten bzw. wird sowas die Performance nicht nochmehr kaputt machen und wann wird sowas überhaupt gemacht (das erst gelesen und dann geschrieben wird in einer neuen Page)?

504

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 10. November 2010, 21:26 »

Dem kann ich nur voll und ganz zustimmen (auch wenn FlashBurn das sicherlich anders sieht).

Habe ich sowas mal irgendwann gesagt 

Denn ich sehe es auch, Exceptions sollte man aus dem Kernel raushalten!

505

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 10. November 2010, 17:45 »

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

506

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 10. November 2010, 15:52 »

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.

507

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 10. November 2010, 13:35 »

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.

508

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 10. November 2010, 13:24 »

Sehr guter Einwand!

509

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 10. November 2010, 13:16 »

Als zusätzliche Sicherheit könnte man noch das Limit in den Ring-3-Descriptoren auf 3GB beschränken aber dann muss man wirklich wechseln.

Es ging ja damals darum, dass sich Segmente nicht durchgesetzt haben und auf anderen Architekturen gab es halt sowas nicht. Deswegen nimmt man heute nur noch das FlatMemoryModel und regelt die Sicherheit über die Flags in den Paging Tabellen.

Ich hab mal testweise im Interrupt-Stub von tyndur das Laden der Ring-0-Deskriptoren für ds und es rausgeworfen und es hat ohne irgendwelche Auffälligkeiten zur Shell gebootet.

Ich habe mal das selbe bei mir gemacht und funktioniert auch.

Jetzt bin ich aber auch baff. Denn wenn man sich das sparen kann, wäre das schon nicht schlecht.

510

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 10. November 2010, 08:30 »

Wenn man für die Daten nur Ring3 braucht dann sollte IMHO auch der Ring 0 Code damit zurecht kommen, kleinerer aktueller Ring geht immer dachte ich eigentlich.

Und welche Fälle fallen dir ein wo du ne Funktion vom UserMode aus aufrufst die dann nur mit den Daten aus dem UserMode läuft (ich hoffe dir fällt auf wie sinnlos das ist)?
Denn sobald du auf KernelMode Daten zugreifen willst geht das ja nicht, weil die ja genau gegen sowas geschützt sind und du dann nen KernelMode Datensegment brauchst.

Dieses Problem müsste doch dann auch bei Call-Gates existieren, da könnte man dann ja nie einen FAR-Pointer an Code mit kleinerem Ring übergeben.

Doch, entweder du benutzt kein Paging dann sollte es eh gehen (wozu sind da die Ringe überhaupt da?) und wenn du Paging benutzt dann geht es um das kleine aber feine Flag was zw User- und KernelMode entscheidet und da ein User dir immer ein Segment mitgibt was auf UserMode-Daten zeigt, funktioniert das eben.

511

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 10. November 2010, 08:25 »

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?

512

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 09. November 2010, 18:06 »

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

513

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 15:16 »

Mal was anderes, wird CR3 eigentlich jedes Mal neugeladen? Weil das wäre schon nen guter Grund kein Hardware-Multitasking zu nutzen (wenn man Threads unterstützt).

Außerdem macht das deinen Scheduler dann davon abhängig, weil du ja die TSS dann organisieren musst (du musst die dann ja im Scheduler "verlinken") und nicht mehr einfach deine Thread-Diskriptoren.

Also ich denke du musst dann schon noch an anderen Stellen anderen Code verwenden wo du dir das ohne Hardware-Multitasking sparen könntest.

514

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 14:56 »

Oder wir haben grundlegend unterschiedliche Vorstellungen davon, was das Wort "portabel" aussagt.

An dem Bsp. heißt für mich portabel das ich den Algo genauso wieder umsetzen kann ohne das ich erst irgendwelche Hardware sachen machen muss, sprich das Sichern der Register (welche und wieviele das sind ist ja erstmal egal) auf dem Stack sollte auf jeder Architektur machbar sein. Implementierst du aber Hardware-Multitasking, wirst du andere Strukturen und wahrscheinlich auch nen ganz anderen Algo brauchen.

An diesem Bsp. geht es ja dann weiter, wenn die Register nicht auf dem Stack gesichert sind, musst du an vielen weiteren Stellen auch Code ändern. Obwohl das eigentlich gar nicht nötig wäre.

515

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 14:04 »

Und was an für x86 implementiertem Software-Multitasking portabel sein soll, musst du mir erst noch erklären. Diese Teile eines OS sind allgemein architekturabhängig, egal welche Technik man jetzt nimmt.

Ich behaupte mal alle Architekturen haben nen Stack und wenn du also auf allen Architekturen die Register auf dem Stack sicherst, ist das portabel
Schon alleine das Wort "Software"-Multitasking impleziert doch das es portabel ist, weil es in Software und nicht in Hardware gemacht wird.

An einer anderen Stelle hatten wir mal das Bsp. das irgendein BSD die ganze Verschlüsselung im WLAN per Software macht und so jede WLAN-Hardware WPA2 beherrscht und genauso ist das mit Software-Multitasking. Du kannst das auf jeder Architektur umsetzen auch wenn sie das gar nicht in Hardware (das Multitasking) unterstützt.

516

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 12:04 »

Hm, weißt du zufällig, was Hardware-MT so langsam macht?

Wimre, war es "nur" das die Register ja in das TSS kopiert werden. Vorteil vom Software-Multitasking ist das es portabel ist und das du eh schon auf den Stack zugreifst, der also schon mal im TLB/Cache ist und du dann mit nem "pushad" alle Register einfach und schnell gespeichert hast.
Auch hat Intel das Hardware-Tasking dann nicht mehr weiter optimiert, weil es halt kaum bis gar nicht benutzt wurde.

517

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 11:27 »

Statt deinem Stub könntest du übrigens auch auf Hardwaremultitasking umsteigen und die CPU das alles machen lassen.

Du willst also etwas langsames noch langsamer machen

Zumal das nicht wirklich portabel ist.

Um Threadwechsel würde ich mir keine Sorgen machen, das passiert jedenfalls im Vergleich selten genug. Aber Syscalls werden ordentlich teuer.

Das "lustige" ist, es würde nur Sinn machen wenn man nen richtigen mikro MikroKernel so implementiert, weil dann wäre jeder Syscall eigentlich eh ne Nachricht zu versenden und dafür musst du eh das PageDir wechseln, also ist das auch nicht so schlimm. Nur braucht ein solcher MikroKernel auch nicht so viel Speicher das es sich lohnen würde ihn in einen extra Adressraum zu packen.

Was die 4GB für die Apps angeht. Ich denke 3GB sollten wirklich reichen und wenn man mehr braucht, 64bit!

518

Lowlevel-Coding / Re:Allgemeiner Ressourcen-Allocator

« am: 09. November 2010, 10:49 »

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.

519

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 09. November 2010, 10:30 »

Wenn der Kernel im Adressraum von 0 bis 1G liegt und die Anwendungen jeweils von 0 bis 4G-4M liegen, wobei in den letzten 4M die benötigten Strukturen eingeblendet sind, dann überschneiden sich die Adressräume.

Das geht aber nur, wenn der Kernel sein eigenes PageDir bekommt und dann kannst du ihm auch gleich die vollen 4GB geben.
Ansonsten geht es nicht das Kernel und Anwendungen im gleichen Adressraum sind und sich überschneiden.

Der Vorteil ist, dass du Anwendungen nahezu volle 4 GB virtuellen Speicher zur Verfügung stellen kannst.

Naja, da wäre halt die Lösung das man irgendwo hin die Strukturen packt die auf jeden Fall benötigt werden und nen Stub wie man in den Kernel wechselt.
Dann ist das möglich und sollte auch nicht alzu schwer sein, nur die Performance wird dann halt nicht so berauschend sein bzw. müsstest du dann dein komplettes Konzept auf SharedMem ausrichten und vorallem sind dann auch Thread-Wechsel sehr "teuer".

520

OS-Design / Re:Adressraum für Kernel und Prozesse

« am: 08. November 2010, 17:05 »

Also was verstehst du darunter das sich die Adressräume überschneiden?

Und was würdest du für Vorteile sehen, wenn der Kernel seinen eigenen 4GB Adressraum hat und nicht in jedem Prozess eingeblendet ist?