Paging & Heap

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