Thema: Speicherverwaltung

[ChristianF]

Nun ja...
mem_upper + 1024 verwende ich vor dem Aufruf der main-Funktion, da mind. 4MB RAM benötigt werden 
 
Die Memory Map so wie in dem Stück Quellcode oben wird bei der Initialisierung der Physikalischen Speicherverwaltung benutzt.
 
 
Jetzt habe ich aber noch eine Frage:
Und zwar habe ich für den nicht DMA-Bereich einen Page Stack, wo ich beliebig Adressen runter nehmen und wieder drauf legen kann.

Code: [Auswählen]

unsigned int *phys_mem_stack;
unsigned int phys_mem_stack_top;

/* Returns the address of a single page (allocated) */
unsigned int phys_mem_stack_pop(void)
{
/* No free physical Memory. panic should be replaced with a swap function later */
if(!phys_mem_stack_top)
panic("Out of Memory. Try Using DMA-Allocator");

return(phys_mem_stack[--phys_mem_stack_top])
}

/* push a address back to the stack (free it) */
void phys_mem_stack_push(unsigned int physical_address)
{
phys_mem_stack[phys_mem_stack_top++] = physical_address;
}
Wenn ich nun eine solche Adresse reserviere, wird die ja dann später in dem Page-Frame gespeichert.
Daraus schließe ich, dass ich nur den Stack mit den freien Pages brauche 
 
Wenn das so richtig ist, wie ich mir das denke, dann bin ich zumindest mit der hälfte fertig. Bei der anderen Hälfte sind noch ein paar ToDo's offen... 
 
Gruß Christian

[kevin]

Ja, es reicht immer, den freien Speicher zu verwalten. Den besetzten verwaltet schon der Benutzer.

[ChristianF]

Das ist sehr gut, dann bin ich schon mal mindestens zur Hälfte fertig.
 
Ich stehe momentan aber irgendwie auf dem Schlauch...
Ich versuche eine Funktion zu schreiben, die eine Anzahl von Speicherseiten sucht und die erste zurück gibt.
Ich habe mir auch die in LOST verwendete Lösung angesehen, aber diese gefällt mir nicht. Die Reservierung ist klar, allerdings ist die Suchfunktion etwas komisch. Da wird gesucht und wenn es heißt, ja found ist größer als num... ...geben wir mal die erste Adresse zurück.

Gibt es da noch eine andere Möglichkeit?
Diese Funktion brauche ich ja nur bei der bitmap, bei dem Stack würde sich das als recht Schwiereig erweisen, und da habe ich auch keine Lust, sowas zu machen... 

Code: [Auswählen]

unsigned int physical_dma_find_page_range(unsigned int num);

Gruß Christian
 
PS: Ich möchte hier keine Lösungen von euch, sondern lediglich Anregungen, wie man das machen könnte.

[kevin]

Ich versuche eine Funktion zu schreiben, die eine Anzahl von Speicherseiten sucht und die erste zurück gibt.
Ich habe mir auch die in LOST verwendete Lösung angesehen, aber diese gefällt mir nicht. Die Reservierung ist klar, allerdings ist die Suchfunktion etwas komisch. Da wird gesucht und wenn es heißt, ja found ist größer als num... ...geben wir mal die erste Adresse zurück.

Wie willst du es sonst machen? Du fängst an zu schauen, ob ausgehend von der ersten Seite genug freie Seiten am Stück vorhanden sind, und wenn ja, kannst du die nehmen. Wenn nein, muß man eben mit der nächsten freien Seite als erster Seite des Bereichs weiterprobieren.

[ChristianF]

Mmmhhh...
Mir kommt da gerade so eine Idee...
 
Ich denke man könnte das auch in folgenden Schritten lösen:

• Die Anzahl in eine Hexadezimale Zahl umwandeln
  ( bsp.: 0xA steht für 10 geforderte Speicherseiten )
• Den Inhalt der Bitmap-Einträge in eine temporäre Variable speichern
  ( bsp.: int tmp = bitmap; )
• Nun wird geprüft, ob die Hexadezimale Zahl in diesen Eintrag "rein passt",
  bzw. ob eine solche Abfolge an hintereinander folgenden Pages möglich ist.
• Passt sie rein, werden die Bits in bitmap auf 1 gesetzt
• Passt sie nicht rein, wird beim nächsten Eintrag weiter gesucht.

Dies oben ist eine Idee, die mir eben gekommen ist und ist noch nicht programmiert worden.
Bei einer leeren Bitmap dürfte es kein Problem sein, dies zu implementieren. Wie das allerdings bei einer stark benutzten bitmap ist, muss ich prüfen...
Was denkt ihr dazu?
 
Gruß Christian

[kevin]

Damit machst du eigentlich das gleiche, nur daß du Bereiche übersiehst, die sich über zwei Bitmapeinträge erstrecken. Außerdem hast du dir damit eine maximal allozierbare Größe von 32 Seiten (wenn deine Bitmap aus 32-Bit-Integern besteht) eingehandelt.

[ChristianF]

Damit machst du eigentlich das gleiche, nur daß du Bereiche übersiehst, die sich über zwei Bitmapeinträge erstrecken. Außerdem hast du dir damit eine maximal allozierbare Größe von 32 Seiten (wenn deine Bitmap aus 32-Bit-Integern besteht) eingehandelt.

Das habe ich noch nicht bedacht.
Aber das Konzept muss nicht unbedingt auf max 32 Speicherseiten beschränkt sein. Allerdings müsste ich mir dafür jetzt dazu noch etwas einfallen lassen.
 
Allerdings würde dies im Endeffekt dann auf das gleiche hinauslaufen, wie in dem Code von LOST, wenn ich das richtig überlege... 

[kevin]

Richtig. Deswegen auch mein "Wie willst du es sonst machen?".

[ChristianF]

Vielleicht eröffnet sich mir ja noch eine Möglichkeit 

[ChristianF]

So!
Die physikalische Speicherverwaltung das Paging sind eingebaut.
 
Allerdings stellt sich mir hier noch eine Frage!
Ich muss ja den Kernel mappen, was soweit auch geschieht. Nun wird aber, wenn der Speicher z.B. 4 MB beträgt aufgeteilt in 2MB DMA verwaltet von der Bitmap und 2 MB normal verwaltet von einem Stack.
 
Ich lasse meinen Kernel Physikalische Speicherseiten reservieren vom DMA Part, was wie mir gerade auffällt nicht korrekt funktioniert, da einige physikalische Bereiche ja bereits als benutzt in der bitmap abgelegt werden.
Das würde heißen, beim Mappen des physikalischen Speichers müsste ich das ja eigentlich wie folgt machen:

Code: [Auswählen]

unsigned int address, virt;
for(address = 0, virt = 0xC0000000; address < (load_end_address+(load_end_address%0x1000)); address += 0x1000, virt += 0x1000)
{
  set_bitmap_entry(address);
 
  map_address(address, address, 1, 1);
  map_address(address, virt, 1, 1);
}

Nun bin ich mir allerdings nicht mehr ganz sicher, was den Speicher betrifft.
Der Kernel wird an die Stelle 0x00100000 also ans erste MB geladen.
Die GRUB-Multiboot Struktur befindet sich irgendwo in den ersten 4 MB, was heißt, dass ich herausfinden muss, ob dies hinter load_end_address ist oder nicht und das dann je nach dem load_end_address ändern muss.
Was auch noch berücksichtigt werden muss, sind die Module, damit diese nicht überschrieben werden.
 
Ist sonst noch etwas wichtiges, worauf unbedingt geachtet werden muss?
 
Grüße Christian
 
*EDIT*
Und noch etwas. Ist es sinnvoller die physikalischen Speicherseiten für den Kernel Heap vom Stack zu nehmen? Oder sollte doch besser der DMA-Part dafür hinhalten.

[Termite]

Moin

korrigiert mich wenn ich da falsch leige. es geht doch gerade darum, phisikalische speicherseiten mittels paging in einen logischen speicher einzubinden?

Wenn dem so ist, ist es doch nicht zwingend notwendig, das n seiten genau am stück im physikalischen speicher liegen, es müssen nur n seiten in der logischen speicherverwaltung angehängt werden, und das natürlich vortlaufend. Wo die sich jetzt physikalisch befinden ist doch egal. Das ist doch gerade der vorteil des Pagings. Und wenn ich seiten im speicher nicht brauche, oder ich mehr speicher brauche als gerade frei ist, kann ich die sogar auslagern wenn ich lustig bin.

gruss

[ChristianF]

Das habe ich mir auch gerade gedacht...
 
Und jetzt habe ich da noch eine generelle Frage:
Welche Möglichkeiten gibt es denn, einen Heap Manager einzubauen? (Für den Kernel)
 
Folgende Möglichkeiten sind mir eingefallen oder habe ich irgendwo mal gesehen:

• Verkette Liste (einfach und doppelt)
• Array

Was verwendet ihr?
Was ist eurer Meinung nach am sinnvollsten?
 
Ich würde zur verketteten Liste greifen.

[bluecode]

Ein Array ist wohl eher nicht sinnvoll, aber wahrscheinlich meinst du eine Bitmap... die ist im Zusammenhang mit Buddy Allocation sinnvoll.
Ich würde sowenig wie möglich beim Allozieren auf ein allgemeines "malloc" ausweichen, sondern eher mit spezielleren Allokatoren arbeiten (also zB einen für fixed-size messages, etc...), da man da weiß wie groß die Objekte sind und das alles die gleichen Objekte sind. Die Allokatoren klauen sich dann Pages direkt vom physischen Speichermanagement. Damit kann man mit Sicherheit Fragmentation vermeiden und es ist bestimmt schneller bei so kritischen Sachen wie Messages. Sind aber wie immer nur meine 0,02€.

Paar Links mit Infos:
http://wiki.osdev.org/Memory_Allocation#Tips_to_go_further
http://wiki.osdev.org/Page_Frame_Allocation#Tree-based_approach.

Zwei Implementationen:
http://g.oswego.edu/dl/html/malloc.html
http://www.hoard.org/

edit: Es ist übrigens imho "kinderleicht" dlmalloc (bei hoard hab ich es noch nicht probiert) zu portieren (sowohl kernel- als auch userspace).

[ChristianF]

Nun ja ich hatte das ja so in der Art geplant, wie das bei dem ersten Link steht.
Mehrere Pools und zwar für Multitasking Strukturen (tss-, task- und vm86-Struktur), IPC, der ganze rest, wie z.B. Verkette Listen.
 
Mal schauen, wie ich das mache. Wahrscheinlich werde ich den Baum nehmen, da dies mich am ehsten anspricht.
 
*EDIT*
Was ich ja eigentlich auch machen könnte, wäre einen Heap Manager mit einem normalen malloc() allerdings festen Größen.
Bsp.:

Code: [Auswählen]

// Größe einer Nachricht in Bytes
#define IPC_MESSAGE 2048
void alloc_message(task_t *task)
{
     /*.....*/
     unsigned char *message = (unsigned char *)malloc(ipc_heap, sizeof(message)*IPC_MESSAGE);
     /*.....*/
}
Die größen und die Funktion sind fiktiv und (noch) nicht vorhanden.
 
Somit hätte ich verschiedene Speicherpools, aber nur eine Funktion zum reservieren des Speichers.
 
Was meint ihr dazu?
 
*EDIT 2*
Mein erstes Ziel ist erst einmal einen Heap Manager einzubauen, der für den ganzen sonstigen Kram zuständig ist, wie z.B. eine Verkettete Liste für irgendwas im Kernel. Das Beispiel ist nicht sehr schön.
Danach werde ich das ganze so ändern, dass man mit der malloc()-Funktion von verschiedenen Heaps speicher reservieren kann.

[ChristianF]

Nun denn...
ich bin ein wenig weiter. Ein wenig deswegen, weil ich nicht so viel Zeit hatte.
Ich habe mich für einen AVL-Baum entschieden und nun eine kleine Frage:
In jedem Knoten wird ein balance-Wert gespeichert. dieser ist je nachdem < -1, -1, 0, 1 oder > 1. Ist der Wert kleiner -1 oder größer 1, muss der Knoten neu ausbalanciert werden, was ich hinbekommen habe.
 
Nun muss ich allerdings nach jedem einfügen oder löschen eines Knotens jeden einzelnen balance-Wert neubestimmen. Laut wikipedia muss dies rekursiv gelöst werden, das könnte ich mir auch nicht anders vorstellen.
 
Allerdings bräuchte ich ein paar anreize, wie man das lösen könnte.

[kevin]

Ich habe gerade gestern einen entsprechenden Patch für LOST rausgeschickt: http://list.tyndur.org/pipermail/lost/2008-October/000923.html

Das Ergebnis sieht nicht offensichtlich falsch aus, allerdings würde es mich nicht wundern, wenn doch noch der eine oder andere Fehler drinsteckt. Der Code um diesen Balance-Wert aktuell zu halten, macht definitiv keinen Spaß. Das nachvollziehen zu wollen sorgt in erster Linie für Knoten im Hirn.

[ChristianF]

Also der balance-Wert eines neu eingefügten Knotens ist 0, das ist ja offensichtlich, da die beiden Kinder NULL beinhalten.
Nun muss ich allerdings nach dem Einfügen eines Elements alle balance Werte darüber prüfen und gegebenenfalls ändern. Danach muss ich dann eine Funktion drüberlaufen lassen, die die balance-Werte aller Knoten prüft und eventuelle Rotationen vornimmt. Im schlechtesten Fall wäre dies der komplette Baum. 
 
Das ist, was ich mir dabei gedacht habe. Habe ich vielleicht etwas vergessen, das ich bei der Implementation unbedingt berücksichtigen muss?
 
Gruß Christian

[kevin]

Ausgehend vom neu eingefügten Knoten von unten nach oben durchgehen reicht, im Rest vom Baum kann sich die Balance nicht ändern.

[ChristianF]

Allerdings muss ich dann, nachdem ich alles geprüft und falls nötig geändert habe, die Höhe der beiden Teilbäume vom Wurzelknoten aus prüfen und gegebenenfalls rotieren, da durch das einfügen ein rechter oder linker überhang entstehen kann.

[kevin]

Das kannst du alles in einem Zug machen. Nach dem Knoten einfügen von unten nach oben durchgehen und überall die Balance anpassen. Wenn die Balance irgendwo unterwegs 2 oder -2 wird, erstmal rotieren bevor man zum Vaterknoten weitergeht.

Und das ist das auch so ziemlich die einzige wirklich nicht offensichtliche Stelle: Wie ändert sich die Balance der Knoten nach einer Rotation? Du willst ja nicht immer den ganzen Baum durchgehen, sonst kannst du gleich eine verkettete Liste nehmen und bist noch performanter.