Thema: Speicherverwaltung

[bluecode]

Ist das normal?

Ja, da "fehlt" auch nichts.

Oder sollte ich statt jna(jump if not above) jb(jump if below) verwenden?

Das wird in dem Fall auch nicht ändern, denn sowohl 2MB <= 3MB (not above) als auch 2MB < 3MB (below).

[ChristianF]

nun mir ist nur gerade aufgefallen, dass deswegen auch bei exakt 4 MB abgebrochen wird, weshalb ich das so abgeändert habe.

Code: [Auswählen]

jna => jb


Ist das normal?

Ja, da "fehlt" auch nichts.

Das verstehe ich nicht, muss ich aber auch nicht...
 
 
Gruß Christian

[bluecode]

Ist das normal?

Ja, da "fehlt" auch nichts.

Das verstehe ich nicht, muss ich aber auch nicht...

Es steht nirgends geschrieben, was genau das high_mem sein soll (ist halt mehr oder weniger ein Maß für die Speichergröße über 1MB, aber wie genau das zustandekommt ist eben nicht definiert), es steht aber geschrieben, dass man es eben nicht für die Speicherverwaltung hernehmen soll. Solange also die memory map in Ordnung ist, "fehlt" auch nirgends etwas.

[ChristianF]

ich habe jetzt verstanden warum da 1 MB "Fehlt".

Code: [Auswählen]

The maximum possible value for lower memory is 640 kilobytes. The value returned for upper memory is maximally the address of the first upper memory hole minus 1 megabyte.
Da steht ja, dass 1 MB abgezogen wird. Aber warum ist der Wert dann bei Bochs 3MB, wenn es bei VMWare 2MB ist und laut spezifikation ja der Speicher ab 1 MB - 1 MB sein soll?

[bluecode]

Wir haben 4MB RAM, d.h. nach 4MB kommt das erste Speicherloch. Dann steht in deiner Erklärung, dass (4MB - 1MB) = 3MB der maximale Wert von mem_high ist. Alle Werte in den Emulatoren verletzen die zitierte Ausage nicht.

edit: Nur um das nochmal hervorzuheben, da steht "address of the first upper memory hole"

[ChristianF]

Ok
Ich hab das jetzt verstanden. 
 
*EDIT 1*
Nun habe ich allerdings noch eine Frage:
Ab dem Pentium Pro ist es ja möglich mit 36-Bit zu Addressieren PAE-36. Nun stellt sich mir die Frage, wie bewerkstellige ich das, dass die 36 Bit in die 20 Bit für den Page-Frame passen?
Ich könnte das ganze shiften, aber woher weiß die MMU dann, welche Adresse jetzt gemeint ist, weil durch das shiften fallen ja 16-Bit weg? 

Sorry hat sich erledigt. Es gibt ja die Intel Manuals 

[ChristianF]

SoSo...
Ich arbeite immer noch an der Speicherverwaltung 
Diesmal aber zum größten Teil Konzeption, denn ich habe mir gedacht, wenn ich 512 MB mit einer Bitmap verwalten muss, kann das ja ziemlich lange dauern und eine ziemlich große Bitmap ergeben (ist ja logisch) 

Nun habe ich einige Beispiele gehört, von wegen den DMA-Space mit einer Bitmap zu verwalten, was heißt max. 16 MB und den Rest mit einem Stack, aus Geschwindigkeitsgründen.

Da ich noch am Durchdenken des Ganzen bin, wollte ich einfach mal fragen, wie ihr das in euren Projekten macht.
 
Gruß Christian

[RedEagle]

Eine Liste, in der die Reservierten pages stehen,
eine Liste in der die Freien Pages stehen,
eine Liste, in der der Byteweise reservierte Speicher steht,
und eine Liste, in der der freie Byteweise reservierbare Speicher steht.
=> 4 voneinander abhängige Listen, und ne menge fast unüberschaubarer code 

Ist bestimmt nicht die Optimallösung, aber es Funktioniert  ;
und es ist eine Eigenkreation, Ich habe also keine großartigen Theorien zu dem Thema gelesen, sondern einfach selber drauflos entwickelt 

---
zum Thema 4MB-Pages:
Ganz zu beginn (also vor dem aktivieren des pagings) bekommt mein kernel 3 4MB-Pages (die 1. 12 Byte im Speicher, physikalische adresse == virtuelle adresse).
Ansonsten arbeite ich nur mit 4KB-Pages.

[bluecode]

Interface
Implementation für x86/x64: hier und hier.

3 Stacks mit freien Pages (4 bzw. 8byte mit der Adresse der Page, Struktur eines Stacks):
1. freie Pages über 16MB und unter 4GB
2. freie Pages über 4GB und unter 64GB
3. freie Pages über 64GB

2 Listen mit Speicherbereichen (also nur Beginn + Größe gespeichert):
* freie Bereiche unter 1MB
* freie Bereiche unter 16MB und über 1MB

[ChristianF]

Ich habe mir die Beispiele mal kurz angesehen

Das ganze verwirrt mich grad ein wenig...
Sollte man das so machen:
Bsp:
* Bitmap 0 bis <1MB
* Bitmap 1MB bis <16MB
* Stack für den Rest (Bis 64 GB  )
Ist jetzt von dir abgeschaut bluecode. Wenn man das so machen sollte, warum?
Ich hatte bisher immer nur die beiden letzten Punkte, also "DMA" und "Nicht-DMA".
 
Gruß Christian
 
PS: Momentan ist bei mir alles auf 32-Bit Basis 
Das ganze 64-Bit Geraffel habe ich mal nach hinten verschoben, bis ich mit Version 0.0.1 fertig bin 
 
 
*EDIT*

Eine Liste, in der die Reservierten pages stehen,
eine Liste in der die Freien Pages stehen,
eine Liste, in der der Byteweise reservierte Speicher steht,
und eine Liste, in der der freie Byteweise reservierbare Speicher steht.
=> 4 voneinander abhängige Listen, und ne menge fast unüberschaubarer code 

Ist bestimmt nicht die Optimallösung, aber es Funktioniert  ;
und es ist eine Eigenkreation, Ich habe also keine großartigen Theorien zu dem Thema gelesen, sondern einfach selber drauflos entwickelt 

Also die Idee mit den 4 voneinander abhängigen Listen ist sicherlich nicht schlecht, allerdings leider immer sehr unüberschaubar, da ich Listen ja schon vorher immer wieder Programmiert habe

zum Thema 4MB-Pages:
Ganz zu beginn (also vor dem aktivieren des pagings) bekommt mein kernel 3 4MB-Pages (die 1. 12 Byte im Speicher, physikalische adresse == virtuelle adresse).
Ansonsten arbeite ich nur mit 4KB-Pages.

Ich hatte vorher auch 4 MB-Pages. Da der Kernel allerdings theoretisch kompatibel zu einem 386er sein soll, habe ich das ganze umgeändert und verwende 4KB-Pages.
Da ich einen HigherHalf Kernel habe, werden kurz vor dem Aufruf der main-Funktion 4 MB speicher gemappt. Das Page Directory muss ich dann später noch ersetzen.
Ich verwende auch 1 zu 1 Mapping, mappe allerdings die ersten 4 MB auch noch nach 0xC0000000, was ich ja muss  .

[bluecode]

Ist jetzt von dir abgeschaut bluecode. Wenn man das so machen sollte, warum?

Sollen/Müssen tut man garnichts. Es gibt natürlich noch andere (mögliche und vllt sogar andere sinnvolle ) Möglichkeiten. Meine Kriterien waren folgende:
* möglichst wenig Speicherverbrauch für die Datenstrukturen zur Verwaltung
* möglichst effizienter Algorithmus zur Allokation/Deallokation von Speicherbereichen
Deshalb die verschiedenen Stacks für alles >16MB, da ein Stack eine konstante Zeit zur Allokation/Deallokation [einer Page] (aka O(1) in Landau-Notation) und geringen Speicherverbraucht (bzw. kein Speicherverbrauch, da man den Stack selbst langsam deallozieren kann, er besteht ja selbst aus Pages), außerdem ist m.E. ein Stack am einfachsten zu Erstellen, da man einfach die freien Pages die man draufpusht dazu verwendet den Speicherplatz für den Stack herzubekommen.
Eine Bitmap ist meiner Erfahrung nach ein ziemliches Gefrickel, da man da meistens statischen einen relativ großen Teil des physischen RAM für selbige verwendet (Mag sein, dass es da bessere Implementationen gibt, das will ich an dieser Stelle nicht ausschließen, aber ich habe glaub ich noch keine gesehen). Mit einer Bitmap bekommt man auch nur lineare Zeit zur Allokation [einer Page] hin (also O(n) in Landau-Notation) [trotzdem aber konstante Zeit zur Deallokation, nur um das auch zu erwähnen]. Außerdem ist dann der Speicherverbrauch größer als bei einem Stack, da man die Bitmap nicht mit der Zeit deallozieren kann.
So, warum nun 3 verschiedene Stacks. Das hat folgenden Grund: Teilweise braucht man Speicherseiten, die eben bestimmten Bedingungen an die Größe der Adresse genügen müssen. Beispielsweise braucht man einem 32bit PCI Gerät keine 36 oder gar 64bit Adressen andrehen. Auch kann man bei PAE für Page Directories keine 36bit Adressen verwenden, da Cr3 trotz allem nur 32bit hat. Deshalb sind m.E. drei Stacks dafür sinnvoll. Bei jeder Allokation wird dann angegeben welchen Bedingungen die Speicherseite genügen muss.
Die drei Stacks decken nun Allokationen ab, welche nicht physisch kontinuierliche Pages brauchen, da dies mit einem Stack nicht effizient implementierbar ist.

Deshalb nun die zwei (ich nenn es mal) "Range-Lists" (also Liste mit Startadresse und Größe eines Speicherbereichs), welche die Speicherbereiche <1MB bzw zwischen 1MB und 16MB verwalten und physisch zusammenhängende Speicherallokationen ermöglichen. Warum solche Rangelists? Weil die solche Allokationen selten sind und damit die Fragmentierung (und damit die Größe der Rangelist) gering ist und außerdem ist die Allokation linear (also O(n), aber mit kleinem n, da es wenig Einträge in der Liste hat). Bei der Komplexität der Deallokation bin ich mir grad nicht ganz sicher, aber ich glaube die ist bei mir auch linear (da Speicherbereiche welche zusammenhängen in einen EIntrage in der Liste gemergt werden). Bei einer Bitmap hingegen hat man eine langsamere Allokation (zwar auch O(n) afaik, aber eben größeres n, da n die Anzahl der verwalteten Pages ist) und die benötigt für meinen bzw. den Verwendungszweck auch mehr Speicher als die Rangelist (gefühlt/geschätzt!).
Warum 2 Rangelist? Teilweise braucht man Speicher <1MB, zB. wenn man über VBE (VESA BIOS Extensions) eine Modiliste bekommen möchte. Außerdem möchte man dann natürlich nicht, dass andere Geräte denen <16MB ausreichen würde <1MB bekommen, sonst geht einem evtl. im entscheidenden Moment der Speicher aus.

Ob sich das alles am Ende bewährt ist eine andere Frage, die ich noch nicht beantworten kann, da das für sich genommen natürlich alles toll klingt, aber fraglich ist zB. was passiert wenn einem zB die >16MB Speicherseiten ausgehen, obwohl noch einige in den Rangelists wären. Da muss man sich dann natürlich zu gegebener Zeit nochmal Gedanken machen.

Also die Idee mit den 4 voneinander abhängigen Listen ist sicherlich nicht schlecht, allerdings leider immer sehr unüberschaubar, da ich Listen ja schon vorher immer wieder Programmiert habe

Wenn du deine Funktionen zur Listenmanipulation sehr allgemein fasst (wie zB die Listenimplementation von LOST für CDI [= Common Driver Interface] bzw. meine C++ Template Implementation für pedigree), dann brauchst du nicht mehrmals das gleiche wieder programmieren.
Und generell gesehen ist die Liste mit dem dynamischen Array aka Vector eine der einfachsten Datenstrukturen überhaupt. Ich denke, dass man das schon hinkriegen sollte

Ich hoffe das war ein bisschen holfreich
btw. das sind die Gründe warum ich das so mache wie ich es eben mache. Ich erhebe da natürlich keinen Anspruch auf Vollständigkeit & Fehler-/Problemfreiheit.

[RedEagle]

[...]

Also die Idee mit den 4 voneinander abhängigen Listen ist sicherlich nicht schlecht, allerdings leider immer sehr unüberschaubar, da ich Listen ja schon vorher immer wieder Programmiert habe

Wenn du deine Funktionen zur Listenmanipulation sehr allgemein fasst (wie zB die Listenimplementation von LOST für CDI [= Common Driver Interface] bzw. meine C++ Template Implementation für pedigree), dann brauchst du nicht mehrmals das gleiche wieder programmieren.
Und generell gesehen ist die Liste mit dem dynamischen Array aka Vector eine der einfachsten Datenstrukturen überhaupt. Ich denke, dass man das schon hinkriegen sollte [...]

Klar kriegt man das hin, und auch unter 1000 Zeilen code
Die "Schwierigkeit" liegt darin, dass man andauernd prüfen muss, ob
a) Eine Liste über eine Page-grenze geht, (also um pages für eine der listen zu reservieren/frei zugeben)
b) Sich 2 elemente einer Liste zusammenfassen lassen.

Es muss also einiges an rechnleistung investiert werden, nur um die Listen zu pflegen.

---
ps.: Man sollte evtl erwähnen, das ich Elektrotechnik studiere und nicht Informatik 
Ich habe also nie sowas wie softwaredesign gelernt. Ich male im prinzip ein paar bildchen, verfasse sie in Code. Und bis ich den Code soweit lauffähig hatte, vergingen einige Monate 

[bluecode]

RedEagle: Ich hab nicht dich gequotet und das hatte schon seinen Grund, ich wollte eigentlich eher sagen, dass Listen einfach sind

Klar kriegt man das hin, und auch unter 1000 Zeilen code

200 Zeilen mit Kommentaren und in C++ Awesomeness verpackt, siehe hier (nur der Wrapper um die eigentliche Liste). Die eigentliche Liste hat mehr Code (siehe auch hier) aber bietet halt auch einges was ein C++ STL gewöhnter Mensch so erwarten würde. Die Liste enthält auch einiges an Template-Tricksereien, um Codebloat zu vermeiden (und ist deswegen teilweise mehr Code als wirklich notwendig) und verwendet eine nette Iterator Klasse, die ziemlich viel Code spart (da sie auch von anderen Datenstrukturen verwendet werden kann).
Aber jo, in C kann man das definitiv unter 1000 Zeilen Code machen und jo, ich bin ein C++ Fanatiker.

Die "Schwierigkeit" liegt darin, dass man andauernd prüfen muss, ob
a) Eine Liste über eine Page-grenze geht, (also um pages für eine der listen zu reservieren/frei zugeben)

Versteh ich nicht wirklich, ich erlaube da nur Allokationen eines Vielfachen einer Page.

b) Sich 2 elemente einer Liste zusammenfassen lassen.

Genau ein mal, beim Freigeben eines Speicherbereiches, siehe auch meine Implementation.

Es muss also einiges an rechnleistung investiert werden, nur um die Listen zu pflegen.

Wie gesagt, beim Allozieren brauchst du lineare Zeit (bezogen auf die Anzahl der Einträge in der Liste), d.h. du gehst ein mal die Einträge durch und suchst dir einen passenden raus. Da es sehr wenige Einträge sind in der Liste wird es auch nicht viel Rechenaufwand sein.
Das Freigeben ist auch linear (bezogen auf die Anzahl der Einträge in der Liste), wobei ich diesmal zweimal durch die Einträge durchgehe, um einmal zu schauen ob darunter und das andere Mal, ob darüber ein Speicherbereich liegt. Auch hier gilt, da es wenige Einträge sind fällt das linear so gut wie nicht ins Gewicht.

Vorsicht: Die Ausführung bezieht sich natürlich auf mein konkretes Szenario. Es ist in keinem Fall immer so, dass linear kaum ins Gewicht fällt.

ps.: Man sollte evtl erwähnen, das ich Elektrotechnik studiere und nicht Informatik 
Ich habe also nie sowas wie softwaredesign gelernt.

Ich denke nicht, dass das viel ausmacht.
Ich studiere zwar Informatik, aber mein momentanen Wissen hat sich eher außerhalb des Studiums angesammelt. Ich bin auch erst im zweiten Semester, da sind noch nicht soviele weltbewegende theoretische Dinge in Informatik gesagt worden. Vielleicht abgesehen von der Vorlesung "Einführung in die theoretische Informatik", aber die hat bis jetzt nichts mit dem hier angeschnittenen Thema zu tun.

[Korona]

Um einen freien Speicherbereich beliebiger Größe zu finden kannst du ja einen B-Tree mit Knotengröße = Pagesize implementieren, wobei du für jedes Element jeweils die Größe des Blocks (als Schlüssel) und die Addresse speicherst. Damit hast du O(log n) statt O(n) Laufzeit. Falls man zu jedem Knoten noch die Addresse des nächsten Blocks und des vorherigen Blocks speichert + ein Flag das anzeigt ob diese frei oder belegt sind, kann man Speicherblöcke auch in O(1) spalten (oder in O(log n), wenn man den abgespaltenen Speicherblock wieder in den Tree einfügt) oder wieder zusammenführen. So werde ich warscheinlich meinen virtuellen Speichermanager implementieren, wenn ich irgentwann mal Zeit habe den zu überarbeiten (im Moment ist mir das noch zuviel Overkill und mir sind andere Features wichtiger ). Bis jetzt habe ich ihn nur als binären Suchbaum implementiert, was eine worst-cast Laufzeit von O(n) hat.

[ChristianF]

Ahoi,
also ich habe mich nun für folgendes Modell entschieden:

• Bitmap für DMA-Bereich (max. 16MB)
• Stack für alles darüber (bei Intel mit PAE max. 64GB, bei anderen bis ohne PAE max. 4GB)

Wie ich das dann mache, wenn aufeinanderfolgender Speicher überhalb des DMA-Bereichs reserviert werden soll, werde ich zu gegebener Zeit nachschauen, was so wie ich das gelesen habe recht schwer ist mit einem Stack .
 
 
Gruß Christian

[bluecode]

Wie ich das dann mache, wenn aufeinanderfolgender Speicher überhalb des DMA-Bereichs reserviert werden soll, werde ich zu gegebener Zeit nachschauen, was so wie ich das gelesen habe recht schwer ist mit einem Stack .

Ich würde es als nicht praktikabel bezeichnen. Wie gesagt, wenn jemand zusammenhängenden RAM braucht, dann kriegt er den bei mir (pedigree) aus dem <16MB Allokator. Das kommt m.E. nicht häufig vor und es werden auch nicht große Stücke sein, insofern halte ich es für vertratbar.

[jgraef]

Wie ich das dann mache, wenn aufeinanderfolgender Speicher überhalb des DMA-Bereichs reserviert werden soll, werde ich zu gegebener Zeit nachschauen, was so wie ich das gelesen habe recht schwer ist mit einem Stack

Wenn ein Programm "normalen" zusammenhängenden Speicher haben will, ist es doch egal ob dieser physisch zusammenhängt. Er muss nur virtuell zusammenhängen.

[bluecode]

Wie ich das dann mache, wenn aufeinanderfolgender Speicher überhalb des DMA-Bereichs reserviert werden soll, werde ich zu gegebener Zeit nachschauen, was so wie ich das gelesen habe recht schwer ist mit einem Stack

Wenn ein Programm "normalen" zusammenhängenden Speicher haben will, ist es doch egal ob dieser physisch zusammenhängt. Er muss nur virtuell zusammenhängen.

Wo steht da irgendwas von Programm? Es geht hier eher um speziellere Allokationen innerhalb des Kernels.

[ChristianF]

Es funktioniert...
*freu*
 
Nach einer Pause und dem Neuschreiben der Speicherverwaltung funktioniert diese nun, zumindest der Part mit der Bitmap.
Auch einen Stack habe ich drinne, da muss ich bei der Initialisierung allerdings noch die Adressen speichern. (Dafür habe ich schon so eine Idee)
 
Momentan muss ich aber erst einmal schauen, wie ich mit der Memory Map von GRUB den RAM zählen kann, denn mem_end_page (Variable mit der Adresse der letzten Speicherseite) wird bei der Bitmap, sowohl auch bei dem Stack verwendet.
Mit der GNU GRUB Dokumentation und den Beispielen habe ich folgendes Stück Quellcode erstellt:

Code: [Auswählen]

/* Eine globale Variable, vielleicht auch später lokal :D */
unsigned int mem_end_page = 0;
...
if(CHECK_FLAG(mbt->flags, 6))
{
memory_map_t *mmap;

for(mmap = (memory_map_t *)mbt->mmap_address;
(unsigned long)mmap < mbt->mmap_address + mbt->mmap_length;
mmap = (memory_map_t *)((unsigned long)mmap + mmap->size + sizeof(mmap->size)))
{
mem_end_page += (unsigned int)(mmap->length_low + mmap->length_high);
}
}
Was haltet ihr davon, bzw. wie erfasst ihr die Größe des Arbeitsspeichers?
 
Gruß Christian
 
*EDIT*
So eben habe ich das Stück Quellcode eingebaut und es hat auf anhieb funktioniert 

[kevin]

Was haltet ihr davon, bzw. wie erfasst ihr die Größe des Arbeitsspeichers?

Die Größe interessiert mich meistens gar nicht so sehr.

Als brauchbare Näherung kann man mem_upper + 1 MB aus der Multiboot-Info nehmen.