Thema: kmalloc und malloc

[rizor]

Hallo zusammen,

ich mache mir gerade Gedanken über meine Speicherverwaltung mit malloc und kmalloc.
Beim Kernel habe ich mir überlegt, da es ja recht leicht zu berechnen ist, welche Größen angefordert werden und somit sollte an sich ja eine einfach verkettete Liste reichen.
Beim malloc habe ich mir erst überlegt, einen AVL-Baum aufzubauen, dann habe ich bei der Implementierung gemerkt, dass der Rechenaufwand recht groß ist.
Da bin ich mir nicht sicher, ob dieser Aufwand einen Algorithmus der O(log n) hat rechtfertigt.
Dann kam mir ein Fibonacci-Heap als Idee, da der ja zum teil konstanten Aufwand hat.
Was ist denn am effektivsten zur Verwaltung von Speicher.

Zur Aufteilung in meinem Kernel habe ich mir überlegt, dass die Speicherverwaltung am Ende des Kernels liegt, darüber die TSS und Directories und darüber dann der Rest und andere Sachen.

Dann habe ich noch eine Frage.
Wie kann ich die Listenelemente denn anlegen?
Im prinzip bräuchte ich ja 2 4k-Seiten.
Einmal für den freien Speicher und einmal für die Verwaltung.
Für den freien Speicher habe ich ja meine Liste.
Aber wie lege ich die Liste an?
Ich müsste doch immer wieder berechnen, ob meine Liste noch auf die Page passt oder nicht.
Stimmt das soweit?
Ich finde es unnötig lauter Listenelement am Anfang einzufügen. Das ist mir ein wenig zu unflexibel.
Wie macht ihr das, bzw. wie kann man das am besten lösen?

Gruß
rizor

[kevin]

Der entscheidende Trick ist, daß du bei einem malloc(42) nicht nur 42 Bytes reservierst, sondern ein paar mehr, in denen du deine Metadaten unterbringen kannst, z.B. next-Pointer bei einer Freispeicherliste. Dann mußt du nicht nochmal getrennt deine Metadaten verwalten.

[rizor]

Dann habe ich doch aber trotzdem das Problem, dass ich bei einer Page nicht weiß, wie voll sie ist.
Es sei denn, ich speichere in diesen Blöcken einen Header, der mir diese Werte angibt.
Aber in diesem Fall habe ich ja das Problem, dass wenn ich nun eine Anfrage bekomme, die größer ist als eine Page, dann klappt das ja nicht mehr richtig mit dem Header.

Wie kann man das Problem am besten regeln?

Wenn ich dass so mache, dass ich mir direkt nach dem Block noch einen Pointer anlege, dann ist ein Baum doch unnötig, bis unmöglich, oder?

[bluecode]

Dann kam mir ein Fibonacci-Heap als Idee, da der ja zum teil konstanten Aufwand hat.
Was ist denn am effektivsten zur Verwaltung von Speicher.

Vier Anmerkungen dazu:
1) Ein Fibonacci-Heap implementiert eine Prioritätswarteschlange (in dem Fall die Operationen insert, delete, find_min und decrease_key). Da würde mich schonmal interessieren, was denn hier überhaupt die Priorität aka. der Schlüssel sein soll. (Ich finde das nämlich nicht wirklich offensichtlich).
2) Ein Fibonacci-Heap hat amortisiert konstante Zeit (in insert, find_min und decrease_key), dass ist aber von der Interpretation was anderes wie "normale" konstante Zeit, denn es gibt eben Operationen die "ab und zu" einiges mehr als konstante Zeit benötigen. Das ist im Umfeld eines Kernels (je nach dem was genau du dir vorstellst) evtl. schlecht. Offensichtlich vorallem bei einem Realtime Kernel.
3) Bei einem Fibonacci-Heap haben die Knoten unterschiedlich viele Kinder, was extrem ungeschickt ist zu implementieren auf dieser Ebene.
4) Bei einem Fibonacci-Heap müsste der "konstante" Faktor um einiges höher sein als bei anderen Möglichkeiten. Ich denke der wird deine konstante bzw. logarithmische Zeit negativ beeinflussen und andere asymptotisch-betrachtet schlechtere Datenstrukturen als geschickter erscheinen lassen. Das ist aber nur eine subjektive Einschätzung von mir (und iirc meinte das auch mein Prof).

[rizor]

Ja, da hast du recht.
Habe den Gedanken nicht wirklich zu ende gedacht.
Aber was ist dann am besten?
Mir ist eingefallen, dass man einen Baum doch recht einfach implementieren kann.
Nur jetzt stellt sich die Frage, welcher und wie.
Mein Hauptproblem sind momentan meine 4k-alignten Blöcke, die ich irgendwie verwalten muss.
Aber leider nicht weiß wie.(s.o.)

[kevin]

Wenn du 4k-Blöcke willst, ist das aber nicht malloc, sondern die physische Speicherverwaltung. Standardlösung ist eine Bitmap oder ein Stack. Buddy-Zeug kann man auch machen, wenn man unbedingt einen Baum verbasteln will.

[rizor]

Nein, dass meine ich nicht.
Ich bekomme durch das Paging ja 4k-alignte Seiten.
Diese verwalte ich mit malloc.
Das ist mir klar.

Aber ich splitte diese 4k-Seiten ja in die Anforderungen des Prozesses/Kernels auf.
Das ist mein Problem wie ich das realisieren kann.
Das kann ich ja auch durch eine Liste machen.
Nur wie weiß ich, wieviel Speicher in meiner Seite noch frei ist.

[tarrox]

Statt Block für Block zu bearbeiten, würde ich die ganzen Blöcke zusammenfassen und als einen Großen Block sehen (ist ja kein Problem dank Paging). So könntest du auch einen Header an den Anfang setzen, der den Größten Block beschreibt. Es ist halt besser einen Heap zu haben als 100 kleine.

[kevin]

Jeder Block (ob voll oder leer) bekommt einen Header. Die freien Blöcke sind miteinander über einen next-Pointer verbunden, so daß du eine Freispeicherliste (ich habe das Wort mehrmals genannt, oder?) bekommst. Beim malloc gehst du die Liste durch und suchst einen Block, der groß genug ist, um den Speicher bereitzustellen, ggf. wird der Block dabei aufgesplittet und der nicht verwendete Teil bleibt in der Freispeicherliste.  Beim free hängst du den Block einfach wieder vorne an die Liste. Aufpassen solltest du, daß es kein doppeltes free gibt. Ansonsten baust du statt einer endlichen Freispeicherliste eine Endlosschleife.

Gibt natürlich einen Haufen Varianten für dieses grundsätzliche Vorgehen, aber so funktioniert es grundsätzlich.

Edit: Und bei sehr großen Anfragen kannst du dir auch überlegen, einfach nur komplette Pages rauszugeben und den Verschnitt in Kauf zu nehmen.

[rizor]

Wenn ich das mit dem Header mache, wo lege ich denn dann immer hin?
Wenn ich nun über eine Page hinaus Speicher allozieren lasse, dann kann ich den Header nicht mehr an den Anfang legen.
Woher weiß ich dann, wo der liegt?

[kevin]

Jeweils an den Anfang des Speicherblocks. Bei der Freispeicherliste speicherst du noch in einer globalen Variablen den Anker der Liste, der Rest ist dann durch die next-Pointer aufgehängt. Bei den benutzten Blöcken kommt der Header direkt vor der Adresse, die du in malloc zurückgibst. Daß dieser Pointer nicht verloren geht, ist dann Aufgabe des Programms, du bekommst ihn beim free wieder und findest damit auch den Header.

[rizor]

Mal sehen ob ich es richtig verstanden habe.
Der Speicher würde dann folgendermaßen aussehen:
frei->header(size)->frei.

Oder wie sieht der Speicher dann aus?
Ich stehe grad ein wenig auf dem Schlauch

[kevin]

Keine Ahung, ob es was bringt, aber ASCII-Bilder sind immer lustig.

Also angenommen wir haben eine 4k-Page vom Kernel geholt. Dann packen wir erstmal einen Header an den Anfang, der sagt, daß dieser Block 4k groß ist und lassen den Anker auf ihn zeigen, damit er eine Freispeicherliste wird.

Anschließend führen wir den folgenden Pseudocode aus, damit auch irgendwas ansatzweise interessantes zu sehen ist:

Code: [Auswählen]

p = malloc(20);
q = malloc(50);
free(p);
Bei den mallocs paßt jeweils der erste Block in der Freispeicherliste. Der Block wird aufgesplittet in einen belegten und einen nicht belegten Block. Anschließend wird p freigegeben, wandert also wieder zurück in die Liste. Damit haben wir folgenden Aufbau erhalten:

Code: [Auswählen]

Anker ---+
         |
         |   +------------------------+
0x0000   +-> | next = 0x80            |--+
             | size = 0x20            |  |
             +------------------------+  |
0x0008       | <freier Speicher>      |  |
             | ...                    |  |
             +------------------------+  |
0x0028       | next = NULL            |  |
             | size = 0x50            |  |
             +------------------------+  |
0x0030       | <belegter Speicher>    |  |
             | ...                    |  |
             +------------------------+  |
0x0080       | next = NULL            |<-+
             | size = 0xf80           |
             +------------------------+
0x0088       | <freier Speicher>      |
             | ...                    |
             +------------------------+
Wird wenigstens so ungefähr klar, was ich ausdrücken will?

[rizor]

Ja das ist schon echt gut.
Nun stellt sich mir nur die Frage des Ankers.
Dann habe ich doch im Prinzip eine Liste aus Ankern, oder?
Denn ich habe ja nicht immer nur eine Page zu verwaltet.

[rizor]

Ach die Frage hat sich geklärt.
Ich kann ja auch einfach den letzten freien Block nehmen und die neue Page in die Freispeicherliste eintragen.

[kevin]

Ja, einfach alles in dieselbe Liste packen. Wobei in eine Liste einfügen vorne leichter geht als hinten, weil man dann nicht erst komplett durchwandern muß - aber das ist ein Detail.

[rizor]

Ich habe mir überlegt, dass ich das nach dem Nextfit-Schema mache, da ich ja so einen ausgeglichenen Speicher erhalte.
Zu dem Thema:
Ich könnte mir doch einfach noch einen Pointer anlegen, der auf das letzte Element zeigt.
Die 4 Byte machen den Kohl ja auch nicht fett und so habe ich dann einen Konstanten Einschub.
Und so habe ich zeitgleich eine sortierte Liste.

[kevin]

Wie gesagt, das sind dann die Details. Wenn du dir einen Vorteil von einer sortierten Liste versprichst, mach das einfach so. Wenn man das Grundprinzip verstanden hat, kann man beliebig variieren.

[Termite]

wobei eine sortierte Liste auch noch andere Vorteile hat.
mit free wird ja ein speicherbereich in die Freispeicher liste eingetragen. Liegen jetzt 2 Seicherbereiche direckt hintereinander, können diese zusammengefasst werden, damit mus ggf beim nächsten malloc nicht eine neue 4K kachel angefordert werden.

[rizor]

Genau das war auch mein gedanke.
Leider funktioniert momentan meine merge-Funktion noch nicht.

Seht ihr vllt einen Fehler?

Code: [Auswählen]

void merge_blocks(list_element_p new_free_p){
list_element_p prev_free = NULL;

//new last element
if(new_free_p > free_end_p){
//merge the blocks
if((address_t)((size_t)free_end_p + free_end_p->size + HEADER_SIZE) == new_free_p){
free_end_p->size += new_free_p->size + HEADER_SIZE;
return;
}

free_end_p->next = new_free_p;
free_end_p = new_free_p;
return;
}

//the first element
if(new_free_p < free_start_p){
//merge the blocks
if((address_t)((size_t)new_free_p + new_free_p->size + HEADER_SIZE) == free_start_p){
new_free_p->size += free_start_p->size + HEADER_SIZE;
new_free_p->next = free_start_p->next;
free_start_p = new_free_p;
return;
}

new_free_p->next = free_start_p;
free_start_p = new_free_p;
return;
}

while(((size_t)free_p + free_p->size + HEADER_SIZE) < (size_t)new_free_p){
prev_free = free_p;
free_p = free_p->next;
}

//merge the right block
if((address_t)((size_t)new_free_p + new_free_p->size + HEADER_SIZE) == free_p){
new_free_p->size += free_p->size + HEADER_SIZE;
new_free_p->next = free_p->next;
}

//merge the left block
if((address_t)((size_t)prev_free + prev_free->size + HEADER_SIZE) == new_free_p){
prev_free->size += new_free_p->size + HEADER_SIZE;
if(new_free_p->next)
prev_free->next = new_free_p->next;
}
}

Die Header-Size ist einfach sizeof(struct list_element)