Paging & Heap

taljeth

Badestrand schrieb:

Es fehlt aber noch die Umwandlung physischen Speichers in virtuellen Speicher (also das Umrechnen der Adressen).

Brauchst du das wirklich? Ich habe dafür noch keinen Einsatzzweck gesehen. An manchen Stellen brauchst du die physische Adresse, aber die kannst du ja direkt beim Allozieren in der passenden Datenstruktur speichern statt hinterher die virtuelle Adresse konvertieren zu wollen.

Erhard Henkes

An manchen Stellen brauchst du die physische Adresse, aber die kannst du ja direkt beim Allozieren in der passenden Datenstruktur speichern statt hinterher die virtuelle Adresse konvertieren zu wollen.

@taljeth: Beim vorherigen Modul habe ich die von dir angesprochene Umwandlung wie folgt erledigt:

uint32_t show_physical_address(uint32_t virtual_address)
{
    page_t* page = get_page(virtual_address, 0, kernel_directory);
    return( (page->frame_addr)*PAGESIZE + (virtual_address&0xFFF) );
}

Aber nun zu PCI und BAR:
Bei der Ermittlung der sechs BAR erhalte ich vom PCI-Scan physikalische Adressen, die ich mappen muss. Um das Ergebnis im virtuellen Speicherraum (also pciScan hinter paging_install) zu finden, benötige ich die erzeugte virtuelle Adresse. Dafür hatte ich beim alten Modul von JM keine Bestimmungsmethode, soweit ich das verstanden habe.

Daher die von mir noch nicht abgelegte Idee der Umrechnung: phys. --> virtuell

@Badestrand: Wie sind diese beiden Fälle bei deinem Modul bisher gelagert?

Das hier in pciScan() kann ich nur vor dem Einschalten des Paging ohne Mapping erledigen:

/// TEST Memory Size Begin
                                cli();
                                pci_config_write_dword  ( bus, device, func, PCI_BAR0 + 4*i, 0xFFFFFFFF );
                                pciBar = pci_config_read( bus, device, func, PCI_BAR0 + 4*i             );
                                pci_config_write_dword  ( bus, device, func, PCI_BAR0 + 4*i,
                                                          pciDev_Array[number].bar[i].baseAddress       );
                                sti();
                                pciDev_Array[number].bar[i].memorySize = (~pciBar | 0x0F) + 1;
                                printformat("sz:%d ", pciDev_Array[number].bar[i].memorySize );
                                /// TEST Memory Size End

taljeth

Erhard Henkes schrieb:

@taljeth: Beim vorherigen Modul habe ich die von dir angesprochene Umwandlung wie folgt erledigt:
uint32_t show_physical_address(uint32_t virtual_address)
{
    page_t* page = get_page(virtual_address, 0, kernel_directory);
    return( (page->frame_addr)*PAGESIZE + (virtual_address&0xFFF) );
}

Ja, es war zu früh. Ich hab's genau falschrum gesagt. Ändert aber nichts an der Tatsache, dass man eigentlich nie anhand der physischen die virtuelle Adresse rausfinden muss.

Bei der Ermittlung der sechs BAR erhalte ich vom PCI-Scan physikalische Adressen, die ich mappen muss. Um das Ergebnis im virtuellen Speicherraum (also pciScan hinter paging_install) zu finden, benötige ich die erzeugte virtuelle Adresse.

Die Mappingfunktion sollte dir einfach die virtuelle Adresse zurückgeben, an die sie gemappt hat.

Erhard Henkes

So sieht unsere Funktion zur Ermittlung der physikalischen Adresse zur Zeit aus:

static uint32_t paging_get_phys_addr( page_directory_t* pd, void* virt_addr )
{
    // Find the page table
    uint32_t pagenr = (uint32_t)virt_addr / PAGESIZE;
    page_table_t* pt = pd->tables[pagenr/1024];
    ASSERT( pt != 0 );

    // Read the address, cut off the flags, append the address' odd part
    return (pt->pages[pagenr%1024]&0xFFFF000) + (((uint32_t)virt_addr)&0x00000FFF);
}

Die Mappingfunktion sollte dir einfach die virtuelle Adresse zurückgeben, an die sie gemappt hat.

@Badestrand: Da solltest Du etwas dazu schreiben.

Erhard Henkes

Hier die Funktionen, die Paging und Heap bisher bieten:

paging.h:

bool paging_alloc( page_directory_t* pd, void* addr, uint32_t size, uint32_t flags );
void paging_free ( page_directory_t* pd, void* addr, uint32_t size );
void paging_switch( page_directory_t* pd  );
page_directory_t* paging_create_user_pd();
void paging_destroy_user_pd( page_directory_t* pd );
uint32_t paging_install();

kheap.h:

void heap_install();
void* k_malloc( uint32_t size, uint32_t alignment );
void k_free( void* mem );

Badestrand

Die Mappingfunktion sollte dir einfach die virtuelle Adresse zurückgeben, an die sie gemappt hat.

Naja, beim Mapping gibt man ja eigentlich schon die virtuelle Adresse an (so wie ich das kenne, sonst skizziere bitte mal).

Wie ist das eigentlich mit dem physischen Speicher, der bei PCI verwendet wird: Ist der in der Memory-Map als "nicht frei" angegeben?
Ansonsten bringt ein Mapping phys->virt auch nur mäßig was, weil man muss ja u.U. allokieren. Wie wär's mit

// Gibt den Anfang der virtuellen Adresse zurück, die
//  auf den angegebenen physischen Bereich gemappt ist.
void* paging_get_phys( uint32_t phys_start, uint32_t phys_end );

?

Und was machen wir, wenn der entsprechende physische Speicher schon belegt ist? In welchem Adressbereich befinden sich typischerweise die PCI-Adressen? 0MB-20MB haben wir ja identity-gemappt.

Erhard Henkes

In welchem Adressbereich befinden sich typischerweise die PCI-Adressen?

Ich habe mir mal einige Screenshots angesehen:

USB UHCI:
6000h - 7000h

USB OHCI und EHCI:
CDBFF800h
CFFFD000h - CFFFF000h
F0804000h - F0805000h

Das sind physikalische Adressen vor dem Paging.
Wenn ich diese auf virtuelle Adressen "mappen" muss, brauche ich eigentlich so etwas:
virtual_address = paging_alloc(...,phys_address)
... oder sehe ich das falsch?

Mit dem alten Modul hatte ich das gleiche Problem. Nach dem Mappen wusste ich nicht, auf welcher virtuellen Adresse die physikalische BAR-Adresse gelandet ist. Also hätte ich GetVirtualAddress(phys-Address) benötigt, gab es aber nur umgekehrt.

Erhard Henkes

Und was machen wir, wenn der entsprechende physische Speicher schon belegt ist?

Ist das überhaupt nutzbares RAM?

Badestrand

Erhard Henkes schrieb:

Das sind physikalische Adressen vor dem Paging.
Wenn ich diese auf virtuelle Adressen "mappen" muss, brauche ich eigentlich so etwas:
virtual_address = paging_alloc(...,phys_address)
... oder sehe ich das falsch?

Richtig, ich sehe mal zu, könnte diese Woche noch klappen (aber nicht vor morgen Abend).

Erhard Henkes schrieb:

Ist das überhaupt nutzbares RAM?

Gute Frage, ich checke dann auch gleich mal die Memory Map..

Erhard Henkes

checke dann auch gleich mal die Memory Map

Thx. So ein paar Analysefunktionen wären didaktisch nicht schlecht. Ins alte Modul habe ich ein paar rein geschrieben. Vielleicht kann man da was übertragen.

Erhard Henkes

taljeth im IRC: <taljeth> In eurem Pagingcode wollt ihr vermutlich den TLB gelegentlich invalidieren, übrigens.

Badestrand

Erhard Henkes schrieb:

taljeth im IRC: <taljeth> In eurem Pagingcode wollt ihr vermutlich den TLB gelegentlich invalidieren, übrigens.

An welchen Stellen denn genau? Oh, wahrscheinlich z.B. wenn der Heap erweitert wird. Bzw generell bei paging_alloc. Guter Punkt, muss ich mich drum kümmern, ich hatte aber merkwürdigerweise noch keine Probleme damit.

Badestrand

Badestrand schrieb:

Erhard Henkes schrieb:

Ist das überhaupt nutzbares RAM?

Gute Frage, ich checke dann auch gleich mal die Memory Map..

Ich hab mal ein wenig geforstet, hier Ausgabe auf meinem Läppi:

Memory Map:
Begin       Ende     Typ (ungleich 1 heißt "belegt")
00000000 -> 0009F800 frei
0009F800 -> 000A0000    2
000E0000 -> 00100000    2
00100000 -> 1F680000 frei
1F680000 -> 1F68E000    4
1F68E000 -> 1F700000    4
1F700000 -> 1F800000    2
1F800000 -> 20000000    2
[Hier noch viele Einträge für Bereich 0xE0000000 - 0xFFFFFFFF; und das bei 512 MB RAM!]

USB-PciScan-Ausgabe:
I/O Adresse 0x000050A0, Size -65504
I/O Adresse 0x000050C0, Size -65504
I/O Adresse 0x000050E0, Size -65504
Mem Adresse 0xD0444000, Size 1024

Darauf komme ich nicht ganz klar. Einmal wegen der Memory Map Einträge bei über 512 MB RAM, zum Zweiten der USB-Mem in so einem hohen Bereich, zum Dritten sind die USB-I/O-Adressen nicht von der Memory-Map als "belegt" markiert.

taljeth

Badestrand schrieb:

An welchen Stellen denn genau? Oh, wahrscheinlich z.B. wenn der Heap erweitert wird. Bzw generell bei paging_alloc. Guter Punkt, muss ich mich drum kümmern, ich hatte aber merkwürdigerweise noch keine Probleme damit.

Probleme gibt es erst dann, wenn du eine schonmal benutzte virtuelle Adresse erneut vergibst und woanders hinmappst. Im allgemeinen also nachdem du Paging fertig getestet hast und überall mit Fehlern rechnest, nur nicht dort. Und TLB-Bugs sind hässlich zu debuggen. Mach's also besser gleich richtig.

Generell in paging_alloc klingt nach einer guten Idee. Beim Freigeben kann es auch nicht schaden. Wenn es dort fehlt, sollten korrekte Programme zwar keine Probleme machen, aber für das Debuggen nicht ganz korrekter Programme ist es besser, wenn sie sofort auf die Schnauze fliegen und nicht erst irgendwann später.

FlashBurn

Falls, ich mich mal einmischen darf

@Badestrand

Also die USB I/O Ports werden auch nicht in der Memory Map auftauchen, da es I/O-Ports sind und keine Speicheradressen! Es ist ganz normal das in der Memory Map sehr viele Bereiche am oberen Ende des Adressraumes kommen, da dort die ganzen PCI Sachen (welche Memory Mapped I/O verwenden) hingemappt werden.

@all

Ich habe noch keinen Blick auf euren Source geworfen, aber wie funktioniert denn eure Funktion, wenn ihr eine Page alloziert? Ich meine woher wisst ihr welche virtuelle Adresse im aktuellen PageDir noch frei ist? Ich würde ich empfehlen eine Funktion zu schreiben, die einfach nur einen Bereich des virtuellen Adressraumes alloziert und in die ihr dann nach belieben physikalischen Speicher mappen könnt.

Badestrand

taljeth schrieb:

Probleme gibt es erst dann, wenn du eine schonmal benutzte virtuelle Adresse erneut vergibst und woanders hinmappst. Im allgemeinen also nachdem du Paging fertig getestet hast und überall mit Fehlern rechnest, nur nicht dort. Und TLB-Bugs sind hässlich zu debuggen. Mach's also besser gleich richtig.

Generell in paging_alloc klingt nach einer guten Idee. Beim Freigeben kann es auch nicht schaden. Wenn es dort fehlt, sollten korrekte Programme zwar keine Probleme machen, aber für das Debuggen nicht ganz korrekter Programme ist es besser, wenn sie sofort auf die Schnauze fliegen und nicht erst irgendwann später.

Cool, danke! Ich will mir auch gar nicht vorstellen, wie das zu Debuggen wäre Ich bau's dann also in paging_alloc und paging_free ein. Ist es besser, die einzelnen Adressen zu updaten oder gleich cr3 neu zu laden (was wohl einfacher ist)?

FlashBurn schrieb:

Also die USB I/O Ports werden auch nicht in der Memory Map auftauchen, da es I/O-Ports sind und keine Speicheradressen! Es ist ganz normal das in der Memory Map sehr viele Bereiche am oberen Ende des Adressraumes kommen, da dort die ganzen PCI Sachen (welche Memory Mapped I/O verwenden) hingemappt werden.

Ok, also müssen wir uns da wohl keine Sorgen machen..? Aber müsste der USB-Adressbereich ab 0xD0444000 nicht in der Memory Map auftauchen? Oder wird der nur nicht eingetragen, weil mein Speicher sowieso nur bis 0x20000000 geht?

FlashBurn schrieb:

Ich habe noch keinen Blick auf euren Source geworfen, aber wie funktioniert denn eure Funktion, wenn ihr eine Page alloziert? Ich meine woher wisst ihr welche virtuelle Adresse im aktuellen PageDir noch frei ist? Ich würde ich empfehlen eine Funktion zu schreiben, die einfach nur einen Bereich des virtuellen Adressraumes alloziert und in die ihr dann nach belieben physikalischen Speicher mappen könnt.

Bis jetzt haben wir afaik gar keine Gefahr der Überschneidung. Der Bereich 0-20MB ist Identity gemappt. Ab 3 GB (0xC0000000) beginnt der Heap, der alloziert beim Wachsen die fortfolgenden Adressen und sonst sollte/darf in den beiden Bereichen niemand anders allozieren.
Sonst an Allokationen gibt's nur das Laden der ELF, wobei wir im Moment eine Basis-Adresse von 0x01400000 (20 MB) voraussetzen, dort den Speicher im User-Page-Directory allokieren und den ELF-Code hinkopieren. Da ist vorher auch nichts und sonst haben wir nichts an Allokationen.
Wie wird das denn "normalerweise" gemacht?

FlashBurn

Ok, also müssen wir uns da wohl keine Sorgen machen..? Aber müsste der USB-Adressbereich ab 0xD0444000 nicht in der Memory Map auftauchen? Oder wird der nur nicht eingetragen, weil mein Speicher sowieso nur bis 0x20000000 geht?

Da muss ich ehrlich passen, soweit bin ich auch noch nicht (ich müsste mir jetzt auch nochmal die Memorymap auf meinem PC angucken). Auf der einen Seite würde ich sagen, er sollte eigentlich in der Memorymap drin stehen, aber soweit ich weiß kann der Bereich ja auch geändert werden (wird über die BARs im PCI CFG Space gemacht). Probleme gibt es erst, wenn du 4GiB Ram hast, und der Speicher eines Gerätes auf eine Adresse gemappt (physikalisch nicht virtuell) wird, der in eurem PMM als frei markiert ist.

Wie wird das denn "normalerweise" gemacht?

Also ich kann dir sagen, wie ich es mache Wie es im Allgemeinen Funktioniert kann ich dir so genau auch nicht sagen.

Wenn ich dich richtig verstanden habe, sieht euer Adressraum so aus:

0-20MiB Kernel Space
20MiB - 3GiB User Space
3GiB - 4GiB Kernel Heap

Um auf deine Frage wegen dem TLB zurück zu kommen, es ist aus Performancesicht besser ein "invlpg" zu machen, denn da wird nur der Eintrag für diese Page im TLB "gelöscht". Sobald CR3 neu geschrieben wird, wird der gesamte TLB gelöscht, mit einer Ausnahme, die Pages die das Globalflag gesetzt haben, werden nicht gelöscht. Im Endeffekt heißt das, dass du die Pages die das Flag gesetzt haben nur mit dem "invlpg" Befehl aus dem TLB löschen kannst.

Was macht ihr denn wenn mein Programm mehr als eine Page bräuchte und der Speicher zusammenhängend sein muss?

Ich würde euch empfehlen folgendes zu machen (ich mache es so und bisher funktioniert es ):

Eine Datenstruktur in der steht welche Adressbereiche noch frei sind (wenn man das ganze dann noch nach Größe und Basisadresse sortieren kann, wird es performanter).
Eine Funktion die euch physikalischen Speicher an eine virtuelle Adresse mappt.
Der VMM (virtuelle Memory Manager) sucht dann nach einem Adressbereich der für die Anforderung groß genug ist und löscht ihn aus der Datenstruktur. Dann ruft er den PMM (physikalischen Memory Manager) auf und mapped die Physikalische Page an die Basis des Bereichs den ihr vorher "alloziert" habt, das macht er so oft bis der ganze Bereich gemappt ist.

Diese Variante hat den Vorteil, das man auch einfach nur Adressbereiche "allozieren" kann und dann in diesen Adressbereich den Speicher von den Geräten mappen kann. Denn wie wollt ihr dieses Problem lösen?

Auch solltet ihr euch fragen, was passiert wenn im Kernelspace (>=3GiB) eine neue PageTable/Page gemappt wird, wie erfahren das die anderen PageDirs?

Mir fällt gerade auf, das ich noch nicht alles erfasst habe, wie ihr es macht. Ich meine wo werden eure PageDirs von den anderen User Prozessen gespeichert?

Ich hoffe ich war einigermaßen verständlich Wenn nicht einfach nachfragen was unklar ist!

Badestrand

Danke erstmal für die ausführliche Antwort! So eine Debatte tut gut, gerade weil es ja selten einen "right way" gibt und die Tutorials an dieser Stelle meist schon geendet haben.

Den Adressraum hast du richtig erfasst. Dabei werden die Page Directories und Page Tables für den Kernel Heap vor-allokiert und liegen irgendwo im Kernel Space zwischen 16 MB und 20 MB. Das Vorallokieren soll den "Deadlock" vermeiden, wenn der Heap wachsen will, aber nicht genug Speicher für neue Page Tables da ist und infolge der Heap rekursiv immer wieder weiter wachsen will, was aber nicht geht.
Die User-Prozesse haben Kernel-Space und Kernel-Heap auch gemappt, die haben in ihrem Page Directory einfach die selben Einträge für 0-20 MB und 3-4GB wie das Kernel-Page-Directory. Das ist ganz praktisch, weil man beim Erweitern vom Heap die User-Page-Directories (und -Tables) nicht updaten muss
Die Page-Directories und -Tables für die User-Prozesse werden einfach im Kernel-Heap via "malloc" angefordert.

Das mit dem "Global"-Flag im Page Table ist ja eine coole Sache, kannte ich gar nicht. Benutzen wir auch nicht, soweit ich weiß. Könnte man aber darüber nachdenken, schließlich ist das Kernel-Space und -Heap Mapping z.Zt. "unabänderlich". Bzw muss der TLB jedenfalls nicht für diese Bereiche geflusht werden beim Prozess-Wechsel.

> Was macht ihr denn wenn mein Programm mehr als eine Page bräuchte und der Speicher zusammenhängend sein muss?
Naja, zusammenhängenden virtuellen Speicher können wir ja ohne Probleme liefern, nur mit dem physischen haperts Für den virtuellen ist die "paging_alloc"-Funktion verantwortlich, die übernimmt die virtuelle Ziel-Adresse und die Größe des angeforderten Speichers; wird dann an die fortlaufenden Adressen gemappt.
Wie ist das mit den fortlaufenden physischen Bereichen? Braucht man die noch für Anderes als für Geräte-Speicher?
Aber mir schwebt da schon was im Kopf herum: Man könnte doch physischen Speicher an bestimmter Adresse anfordern. Wenn da schon Speicher liegt, muss er verschoben werden, das entsprechende Page-Directory plus -Table gefunden und geupdated werden. Na gut, das Finden des PDs ist sehr aufwendig, das Finden einer virtuellen Adresse muss auch gut überlegt werden (vielleicht könnte man von 4 GB dem Heap nach unten entgegen kommen).

Wie behandelst du den Fall, dass der angeforderte physische Speicher schon belegt ist?
Deine Memory Management Variante sieht gut aus, obwohl mir der Gedanke der fixen virtuellen Speicheraufteilung im Moment noch besser gefällt. Was meinst du zu der Idee, den virtuellen Geräte-Speicher dem Heap entgegenwachsen zu lassen?

FlashBurn

Also ich muss zugeben, das ich euren VMM noch immer nicht verstanden habe, im Endeffekt wollte ich wissen was für eine Datenstruktur nutzt ihr um zu wissen was freier virtueller Speicher ist und was nicht? (Ich sage mal, solange man nicht dealloziert nimmt man einfach nen Pointer, gibt den zurück und addiert einfach die Größe der Anforderung drauf.)

Also zusammenhängenden physischen Speicher könnte ich ab 32MiB Ram (theoretisch) auch allozieren (ist praktisch nicht umgesetzt), aber das muss man auch nicht.

Folgender Satz:

Für den virtuellen ist die "paging_alloc"-Funktion verantwortlich, die übernimmt die virtuelle Ziel-Adresse und die Größe des angeforderten Speichers; wird dann an die fortlaufenden Adressen gemappt.

Soll das heißen, das ich selbst wissen muss wo der physische Speicher in den virtuellen gemappt werden muss?

Nochmal zu euren Pagetables und Pagedirs. Also an sich brauchst du um die vollen 4GiB pro Prozess nutzen zu können, 4MiB (Pagetables) + 4KiB(Pagedir) und von daher wird euer virtueller Speicher schnell ausgehen (auch wenn man jetzt pro Prozess 1MiB weniger rechnen könnte, da ab 3GiB eh immer die selben Pagetables verwendet werden).

Um es an einem Beispiel zu verdeutlichen. Du hast 2 Prozesse, A und B, Prozess A ruft den Kernel auf macht da irgendwas und der Kernel muss deswegen ne neue Page anfordern (im Heap) und das wiederrum brauch ne neue Pagetable, weil die vorher nicht im Pagedir stand. Soweit so gut, aber wie updatest du jetzt das Pagedir von Prozess B? Es sei denn ihr habt die Pagetables für die vollen 3GiB schon voralloziert (was aber ne Verschwendung von 1MiB Ram wäre, aber würde die Sache extremst vereinfachen).

Was meinst du zu der Idee, den virtuellen Geräte-Speicher dem Heap entgegenwachsen zu lassen?

Könnte funktionieren, mir fällt auch gerade kein Nachteil ein (außer das ich es anders machen würde/mache )

Ich vermute mal ihr habt nen Monolithen Kernel?

Erhard Henkes

Ich vermute mal ihr habt nen Monolithen Kernel?

Ja

Paging &amp; Heap

Paging & Heap