Es gibt mehrere Möglichkeiten die unbenutzten Seiten im physikalischen Speicher zu verwalten – eine gute Übersicht findet sich z.B. im osdev-Wiki. Für die Aufgabe 3 soll ein Kompromiss aus kompakter aber einfacher Struktur genutzt werden: Linked-List

Freispeicherlisten

Es wird eine einfache verkettete Liste verwendet. Um das Allokieren einen Tick einfacher zu machen, verwenden wir hier statt einer Endadresse lieber eine Längenangabe, welche die Anzahl der vorhandenen freien Page Frames angibt

struct PageList:
    start (Zeiger auf anfang eines freien Bereiches, auf 4 KB ausgerichtet)
    len (Anzahl der 4 KB Pages)
    next (Zeiger auf nächsten PageList-Eintrag -- oder NULL)

Wur können hier mit new schnell dynamisch ein neues Element erstellen und mit delete dann wieder freigeben (dürfen halt nur nicht zu viele Einträge werden, aber mit das sollte mit dem hier beschriebenen Vorgehen kein Problem sein).

Grundlegenden Funktionen

Das Allokieren ist einfach (𝒪(1)): Erstes Element der Liste nehmen, und von dem Bereich einfach den letzten Page Frame zurückgeben – hat den Vorteil, dass ich nur len anfassen muss (solange in dem Bereich mehrere Page Frames vorhanden sind).

alloc():
    Nimm erstes Element aus der Liste
    Falls keine Einträge in der Liste: 
        gib Null zurück
    ansonst:
        Ziel ist start + len * 0x1000
        Reduziere len im Eintrag um 1
        Falls len nun 0:
            lösche den Eintrag
        gib Ziel zurück
}

Beim zurückgeben einer nun nichtmehr benötigten Seite machen wir es uns sehr einfach: Es wird als Bereich mit nur einem Page Frame an den Anfang der Liste gehängt – damit wird es gleich beim nächsten alloc wieder verwendet, und wir brauchen keine Angst haben, dass unsere verkettete Liste zu groß wird!

free(addr):
    Füge einen neuen Eintrag an den Anfang der Liste mit { addr, 1 }

Initialisierung

Einfaches Vorgehen: Wir beginnen mit einer leeren Liste, fügen von der Multiboot MemoryMap den Speicher hinzu, der als frei gekennzeichnet ist, jeder Bereich ist ein Element. Danach gehen wir nochmal über diese MemoryMap, und entfernen aus eben hinzugefügten Bereichen den belegten Speicher wieder hinaus – Überlappungen sind ja möglich! Der Aufwand ist zwar 𝒪(n²), aber das ist OK. Außerdem entfernen wir noch weitere Bereiche die wir nicht als Page Frames ausgeben wollen.

init():
    1. über Multiboot::getMemoryMap() iterieren
        Falls isAvailable():
            addRange(getStartAddress(), getEndAddress())
    2. nochmal über Multiboot::getMemoryMap() iterieren
        Falls nicht isAvailable():
            removeRange(getStartAddress(), getEndAddress())
    3. weitere Speicherbereiche entfernen
        removeRange(0, 0x00100000)  [< 1 MB für BIOS]
        removeRange(0x00F00000, 0x00FFFFFF)  [ISA Memory Hole]
        removeRange(&___KERNEL_START___, &___KERNEL_END___)
        ...

Hilfsfunktionen zum Löschen eines (beglegten Speicher-)Bereiches

Idee: Wir gehen die Freispeicherliste durch und prüfen für jeden Eintrag (welcher einen freien Speicher repräsentiert) eine Überlappung mit dem via Parameter übergebenen belegten/zu entfernenden Speicherbereich. Dazu gibt es prinzipiell 4 Fälle

• Vorbemerkung für die nachfolgenden Beispiele/Funktionen)
  • Start (from) ist inklusive
  • Ende (to) ist exklusive
  • es wird immer gleich mit ausgerichteten Adressen gearbeitet
• Fall 1: zu entfernender Bereich Überdeckt den Listeneintrag vollständig

  Eintrag in Liste: 0x5000 - 0xa000            [_______________]
  Belegter Bereich: 0x3000 - 0xc000       [XXXXXXXXXXXXXXXXXXXXXXXXX]
  Resultat: kein freier Bereich

• Fall 2: der zu entfernende Bereiche überschneidet sich mit dem Listeneintrag am Anfang

  Eintrag in Liste: 0x5000 - 0xa000            [_______________]
  Belegter Bereich: 0x3000 - 0x7000      [XXXXXXXXXXX]
  Resultat:         0x7000 - 0xa000                   [________]

• Fall 3: der zu entfernende Bereiche überschneidet sich mit dem Listeneintrag am Ende

  Eintrag in Liste: 0x5000 - 0xa000            [_______________]
  Belegter Bereich: 0x8000 - 0xc000                      [XXXXXXXXXXX]
  Resultat:         0x5000 - 0x8000            [________]

• Fall 4: zu entfernender Bereich ist echte Teilmenge des Listeneintrags

  Eintrag in Liste: 0x5000 - 0xa000            [_______________]
  Belegter Bereich: 0x6000 - 0x8000               [XXXXXXX]
  Resultat:         0x5000 - 0x6000            [_]         [___]
              sowie 0x8000 - 0xa000

Das nun als Pseudocode, dabei gibt der Eintrag in der Liste den freien Speicher von entry_start bis entry_end an, der zu entfernende Bereich von from bis to (auf Seitengrenzen gerundet, so dass der zu entfernende Bereich ggf. größer als durch die Parameter angegeben ist):

removeRange(from, to):
    from auf die Seitengrenze abrunden (from &= ~0xfff)
    to auf die letzte Seitengrenze aufrunden (to =  (to + 0xfff) & (~0xfff))
    Falls from < to:
        Gehe durch die Einträge der Liste (beginnend bei head):
            entry_start <- start des aktuellen Listenelements
            entry_end <- entry_start + len * 0x1000
            Falls from < entry_end und zugleich to > entry_start:
                wir haben eine Überlappung & müssen nun die Fälle durchgehen
                Falls from <= entry_start:
                    Falls to >= entry_end: [Fall 1]
                        die zu löschende Range überlappt vollständig den Eintrag
                        -> Eintrag muss aus der Liste gelöscht werden
                    andernfalls (to < entry_end): [Fall 2]
                        start des aktuellen Listenelements auf to setzen
                        Länge anpassen (entry_end - to) / 0x1000
                andernfalls (from > entry_start):
                    wir haben eine Überlappung beginnend in der Mitte [Fall 3 & 4]
                    Länge des Eintrags anpassen (from - entry_start) / 0x1000
                    Falls to < entry_end: [Fall 4]
                        Neuen Eintrag { to, (entry_end - to) / 0x1000 } an die Liste anfügen

Hilfsfunktionen zum Hinzufügen eines (freien Speicher-)Bereiches

Diese Funktion ist relativ trivial, rundet lediglich auf die Seitengrenze (-> tatsächlicher freier Bereich ist kleiner oder gleich dem via Parameter übergebenen Bereich) und berechnet die Länge (= Anzahl der vollen Seiten in dem freien Bereich)

addRange(from, to):
    from auf die nächste Seite aufrunden (umgekehrt zu removeRange!)
    to auf die letzte Seitengrenze abrunden (umgekehrt zu removeRange!)
    Falls from < to:
        removeRange(from, to) um ggf. doppelte/überlappende Einträge zu entfernen
        len = (to - from) / 0x1000
        füge { from, len } an das Ende der Liste an

Zurück zur Übersicht