Paging & Heap

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

Badestrand

FlashBurn schrieb:

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

Genau, die virtuelle Adresse muss man angeben. Also beim "paging_alloc" jedenfalls. Wir haben auch ein "malloc" drin, das 'nen Heap im Hintergrund hat (das bei 3-4GB), da braucht man natürlich keine Adresse angeben.
Wir haben das ganze unterteilt in Paging- und Heap- Zuständigkeiten. Der Heap für malloc und free, er nutzt das Paging. Paging kann nur an bestimmte Adressen mappen. Der Heap weiß immer seine obere Grenze und ruft dann beim Wachsen sowas wie " paging_alloc( kernel_pd, heap_top, 128*1024 ) " auf, um 128 KB zu wachsen. Intern im Heap haben wir auch eine Art Liste, allerdings unperformat, hier war Einfachheit das Gebot.

FlashBurn schrieb:

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).

Das stimmt, aber wie will man es sonst lösen? Oh, virtuellen Speicher im User-Prozess freihalten?

FlashBurn schrieb:

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).

Genau so machen wir's Bis jetzt ist der Speicher nicht ausgegangen und bis es soweit ist, haben wir's vielleicht eh schon umkonzeptioniert.

FlashBurn

Genau, die virtuelle Adresse muss man angeben. Also beim "paging_alloc" jedenfalls.

Das wäre also eure "map"-Funktion.

Wir haben auch ein "malloc" drin, das 'nen Heap im Hintergrund hat (das bei 3-4GB), da braucht man natürlich keine Adresse angeben.
Wir haben das ganze unterteilt in Paging- und Heap- Zuständigkeiten. Der Heap für malloc und free, er nutzt das Paging. Paging kann nur an bestimmte Adressen mappen. Der Heap weiß immer seine obere Grenze und ruft dann beim Wachsen sowas wie "paging_alloc( kernel_pd, heap_top, 128*1024 )" auf, um 128 KB zu wachsen. Intern im Heap haben wir auch eine Art Liste, allerdings unperformat, hier war Einfachheit das Gebot.

Ich würde da nen weiteren "Layer" dazwischen schieben. Sprich euer "malloc" ruft nur noch ne Funktion vom Kernel auf, die die Anzahl an Pages übergeben bekommt und dann den Rest macht (also Adresse finden und mappen). Auch würde es mehr Sinn machen wenn ihr eurem "paging_alloc" die Anzahl Pages übergeben würdet, da ihr eh darauf überprüft ob die übergebene Size durch 4096 teilbar ist.

Das stimmt, aber wie will man es sonst lösen? Oh, virtuellen Speicher im User-Prozess freihalten?

Da hast du mich wahrscheinlich falsch verstanden (oder ich dich )

Normalerweise "sieht" jeder Prozess nur sein PageDir und seine PageTables, weil ansonsten geht dir schnell der virtuelle Speicher aus (Bsp. bei 8 Userprozessen, wären das schon 8*4MiB= 32MiB + 8*4KiB= 32KiB).

Eine Methode das Problem zu lösen, wäre das man die Pagetables als Pages an eine fixe Stelle mappt und genauso das PageDir. Hört sich erstmal komisch an, vereinfacht aber den Code.

Ich mappe meine PageTables immer bei 4GiB-4MiB (also die letzten 4MiB im virtuellen Adressraum) und das PageDir bei 4GiB-4MiB-4KiB. Wenn ich dann ne Page mappen will, nehme ich einfach die virtuelle Adresse teile sie durch 4096 (das gibt mir die PageNum) und habe nen Pointer der auf 4GiB-4MiB zeigt und brauch dann nur noch "ptr[pagenum]= physikalische Adresse | Flags" machen und schon habe ich die Page gemappt.

Da ihr eure Pagetables für >3GiB eh voralloziert, habt ihr auch nicht das Problem wie man anderen Prozessen mitteilt, das sich eine Pagetable >3GiB geändert hat (das musste ich gestern in den Griff bekommen, da ich es doch glatt vergessen hatte).

Badestrand

FlashBurn schrieb:

Ich würde da nen weiteren "Layer" dazwischen schieben. Sprich euer "malloc" ruft nur noch ne Funktion vom Kernel auf, die die Anzahl an Pages übergeben bekommt und dann den Rest macht (also Adresse finden und mappen).

Da denke ich drüber nach, erstmal zum Rest!

FlashBurn schrieb:

Auch würde es mehr Sinn machen wenn ihr eurem "paging_alloc" die Anzahl Pages übergeben würdet, da ihr eh darauf überprüft ob die übergebene Size durch 4096 teilbar ist.
[...]
Ich mappe meine PageTables immer bei 4GiB-4MiB (also die letzten 4MiB im virtuellen Adressraum) und das PageDir bei 4GiB-4MiB-4KiB.

Das klingt beides gut, ist so gut wie drin (statt obere Grenze 4GB halt 3GB)!

Also verstehe ich das richtig, dass du deine Pagetables für die Userprozesse schon vor-allokierst? Oder erst bei Bedarf, sind ja immerhin 4 MB?

FlashBurn

Also gut mal ein Auszug aus meiner mapping Funtion:

for(x= 0; x < count; x++, pte++, phys+= 0x1000) {
	pde= pte >> 10;
	//look if the pde is present
	if(unlikely((pd[pde] & PG_FLAG_PRESENT) == 0)) {
		if(unlikely((pd[pde]= (uint32t)pmmAlloc4kb()) == 0))
			break;

		pd[pde]|= PG_FLAG_PRESENT;
		pt[(1023 << 10) + pde]= pd[pde];

		_invlpg((void *)((uint32t)pt + (pde << 12)));
	}
	//look if the entry is used
	if(unlikely(pt[pte] != 0))
		break;

	pt[pte]= (uint32t)phys | PG_FLAG_PRESENT | flags;

	_invlpg((void *)(pte << 12));
}

"pt" und "pd" sind Konstanten, das sind meine fixen Adressen wo in jedem Adressspace, die PageTables und das PageDir steht. "pte" errechnet sich aus "virt >> 12".

Also verstehe ich das richtig, dass du deine Pagetables für die Userprozesse schon vor-allokierst? Oder erst bei Bedarf, sind ja immerhin 4 MB?

Wie du oben im Code sehen kannst, allokiere ich die PageTables immer erst dann wenn ich sie auch brauche, aber der Virtuelle Speicher auf den "pt" zeigt (bis 4MiB danach) wird halt nicht anders genutzt, sondern nur von meinen PageTables.

Paging &amp; Heap

Paging & Heap