Thema: Bitmaps

[rizor]

Nabend,

ich bin gerade dabei mir einen Speichermenager für den physikalischen Speicher zu schreiben.
Habe mir überlegt, dass ich erst mal Bitmaps verwende (wirken für mich recht einfach).
Nun wollte ich mal fragen, ob ich alles richtig verstanden habe.

Bei einem x86-System habe ich zwei Möglichkeiten meinen Speicher zu mappen, 4kB und 2MB, oder?
Dann definiere ich mir einfach einen Speicherbereich in meinem Kernel, der meine Bitmap darstellt.
Da habe ich ja eine Endadresse meines Kernels, die ich als Offset interpretiere, oder?
Also wenn ich Bit2 in meiner Bitmap allozieren möchte, wähle ich einfach die Endadresse meines Kernels und addiere da dann dann die Größe drauf.
Dann habe ich doch meine Page-Adresse, oder?

Beim Speicher freigeben, habe ich die Adresse ziehe davon mein Kernelende ab und teile durch die Größe, oder?
Dann müsste ich doch das Bit haben.

Hoffe, dass das soweit stimmt.
Nun habe ich aber ein Problem.
Ein Teil des Speichers ist ja durch das BIOS und ein Teil durch meinen Bootloader (in meinem Fall GRUB) belegt.
Habe auch im LOST-Projekt gesehen, dass ich mit einer Multiboot-Struct das alles abfragen kann.
Nun habe ich aber das Problem, dass ich nicht weiß wie groß die Pages sind und wie groß mein RAM ist.
Wie bekomme ich raus, was genau belegt ist und wie groß mein RAM ist?

Die Größe des RAMs muss ich ja kennen um meine Bitmap-Größe zu bestimmen.
Außerdem schreibe ich gerade einen 32-Bit-Kernel.
Das bedeutet, dass ich ja durch die Adressierung eingeschränkt bin.
Sollte ich meinen Kernel-Bereich auch mappen?
Wenn ja, wie?

Wie muss ich denn darauf reagieren, wenn ich mehr als 3GB-RAM habe?
Muss ich dann von Hand darauf achten, dass ich nicht versuche mehr Speicher zu Adressieren?

Dann habe ich noch eine Frage zum Kernel-Aufbau.
Bevor ich meinen Speichermanager aufrufe, rufe ich erst den GDT udn IDT auf, die belegen doch auch schon Platz auf dem RAM, oder habe ich das falsch verstanden?
Die Adressen muss ich ja auch kennen.

Hoffe ich konnte die Fragen so formulieren, wie ich sie meine .

Danke für eure Hilfe.

Gruß
rizor

[ChristianF]

Guten Morgen,
 

Wie muss ich denn darauf reagieren, wenn ich mehr als 3GB-RAM habe?
Muss ich dann von Hand darauf achten, dass ich nicht versuche mehr Speicher zu Adressieren?

Du vertauschst hier gerade die physikalische Speicherverwaltung mit dem Paging. Über die GRUB Memory Map kannst du die größe des RAMs berechnen. Die Größe der Bitmap wird dann anhand der anzahl der Speicherseiten berechnet, also wie folgt:

Code: [Auswählen]

anzahl_der_pages = (max_ram_in_bytes) / groesse_einer_page
bitmap_groesse = (anzahl_der_pages / 32) * 4Bei der physikalischen Speicherverwaltung gibt es somit überhaupt kein Problem, wenn du mehr als 3 GB RAM eingebaut hast.
 
 

Nabend,

ich bin gerade dabei mir einen Speichermenager für den physikalischen Speicher zu schreiben.
Habe mir überlegt, dass ich erst mal Bitmaps verwende (wirken für mich recht einfach).
Nun wollte ich mal fragen, ob ich alles richtig verstanden habe.

Bei einem x86-System habe ich zwei Möglichkeiten meinen Speicher zu mappen, 4kB und 2MB, oder?
Dann definiere ich mir einfach einen Speicherbereich in meinem Kernel, der meine Bitmap darstellt.
Da habe ich ja eine Endadresse meines Kernels, die ich als Offset interpretiere, oder?
Also wenn ich Bit2 in meiner Bitmap allozieren möchte, wähle ich einfach die Endadresse meines Kernels und addiere da dann dann die Größe drauf.
Dann habe ich doch meine Page-Adresse, oder?

Beim Speicher freigeben, habe ich die Adresse ziehe davon mein Kernelende ab und teile durch die Größe, oder?
Dann müsste ich doch das Bit haben.

Im Paging hast du größen von 4KB, 2MB und sogar 4MB. Allerdings ist es nach meiner persönlichen Meinung nicht unbedingt sinnvoll 4MB Pages zu verwenden. Somit sollte 4 KB reichen, aber das ist dir überlassen.
 
Die Bitmap verwaltet die physikalischen Pages. Diese haben die Größe, die du festlegst. Wenn du in der Bitmap eine physikalische Page mit einer Größe von 8MB verwaltest, dann ist das so. Ob das dann sinnvoll ist, sei dahingestellt.. 
Wichtig ist, wenn du eine Größe für eine Page festgelegt hast, so sind alle gleich groß. Das heißt, wenn du deinen Speicher in 2 MB Blöcken verwalten möchtest, so sind alle Blöcke 2 MB groß.
Die physikalische Speicherverwaltung ist nur dazu da, den vorhandenen Speicher in gleichgroßen Blöcken zu verwalten. Wie oben schon gesagt, du vertauschst da die physikalische Speicherverwaltung mit dem Paging.
 
Die Adresse aus der Bitmap wird nicht nach der End-Adresse des Kernels bestimmt. Es gibt eine Formel, mit der man von dem aktuellen Index auf die Adresse kommt. Diese sieht wie folgt aus:

Code: [Auswählen]

physikalische_page_adresse = ((bitmap_index * 32) + aktuelles_bit) * page_groesseWürdest du in C also deine Bitmap durchsuchen wollen, so sähe das so aus:

Code: [Auswählen]

for(int i=0; i < groesse_bitmap; i++)
{
     // 0xFFFFFFFF zeigt, das alles belegt ist
     if(bitmap[i] != 0xFFFFFFFF)
     {
          for(int j=0; j < 32; j++)
          {
               // Bit bestimmen
               int check = 1 << j;
               // Ist die page frei?
               if(!(bitmap[i] & check))
               {
                    // Mach was mit der Adresse
               }
          }
     }
}

Die Bitmap verwaltet den kompletten Speicher in einzelnen immer gleich großen blöcken. Das heißt, dass z.B. wenn die Blockgröße 4096 Bytes ist, die kompletten 3 GB als 4KB Blöcke in einer riesigen Bitmap verwaltet wird.
 
Das Problem mit den 3 GB tritt erst auf, wenn du Paging einbaust. Paging kann nämlich in der ursprünglichen Variante, wie sie mit dem i386 kam nur 1 GB speicher verwalten.
Doch das braucht dich erst zu interessieren, wenn der physikalische Part abgeschlossen ist. 
 
 
Gruß Christian
 
PS: Ich hoffe der Post war hilfreich. Falls nicht, dann schau mal hier: http://lowlevel.brainsware.org/wiki/index.php/Speicherverwaltung Da ist das etwas besser erklärt. 
 
EDIT:
Standardmäßig ist eine Page 4KB groß. 

[kevin]

Bei einem x86-System habe ich zwei Möglichkeiten meinen Speicher zu mappen, 4kB und 2MB, oder?

Grundsätzlich 4k, mit PSE 4 MB und mit PAE 2 MB.

Nun habe ich aber ein Problem.
Ein Teil des Speichers ist ja durch das BIOS und ein Teil durch meinen Bootloader (in meinem Fall GRUB) belegt.

Nicht zu vergessen durch deinen Kernel. Wäre eher ungünstig, den zu überschreiben. Muß man dann halt gleich am Anfang als reserviert markieren.

Nun habe ich aber das Problem, dass ich nicht weiß wie groß die Pages sind und wie groß mein RAM ist.
Wie bekomme ich raus, was genau belegt ist und wie groß mein RAM ist?

Die Pages sind in der physischen (nicht "physikalischen"!) Speciehrverwaltung so groß wie du sie machst. Sinnvollerweise 4k. Die RAM-Größe kriegst du durch die Memory Map in der Multiboot-Struktur raus.

Sollte ich meinen Kernel-Bereich auch mappen?

Paging ist virtuelle Speicherverwaltung. Und wenn du den Kernel dort nicht mappst, hast du ein Problem...

Wie muss ich denn darauf reagieren, wenn ich mehr als 3GB-RAM habe?

4 GB sind die Grenze, wo die 32 Bit zu Ende sind. Vorher passiert gar nichts. Wenn du mehr willst, brauchst du PAE (oder x86_64).

[rizor]

Danke erst mal.
Mal sehen, ob ich es verstanden habe.
Wenn ich mein System starte, packt GRUB meinen Kernel ja an eine Stelle, die ich festgelegt habe.
Also weiß ich schon mal wo der steht.
Dann suche ich mir eine Größe pro Speicherblock aus.
Sagen wir 4kB.
Aus meinem Multiboot bekomme ich die Größe meines RAM.
Wenn ich nun die Größe des RAMs durch meine Speicherblockgröße teile, müsste ich an sich die Anzahl an Blöcken bekommen, oder?

Achso, wo bekomme ich den Multiboot her?
Ich weiß, den erstellt GRUB aber wo liegt der?

Gruß
rizor

[kevin]

Aus meinem Multiboot bekomme ich die Größe meines RAM.
Wenn ich nun die Größe des RAMs durch meine Speicherblockgröße teile, müsste ich an sich die Anzahl an Blöcken bekommen, oder?

Genau.

Achso, wo bekomme ich den Multiboot her?
Ich weiß, den erstellt GRUB aber wo liegt der?

Ein Pointer auf die Struktur liegt in ebx (oder war es eax?), wenn er in deinen Kernel springt. Am besten pushst du den auf den Stack, damit du ihn in deiner C-Hauptfunktion als Parameter nehmen kannst.

[rizor]

Danke für eure Antworten.
Habe jetzt noch eine Frage:

Mein Boot-Loader erstellt ja eine memorymap, anhand derer ich meine erstelle.
Wenn ich mir nun überlege, dass ich meine Blöcke frei wählen kann klingeln bei mir ein paar Alarmglocken.
Sagen wir ich mappe mit 2MB und der GRUB mappt mit 4kB, wenn ich nun versuche zu mappen gibt es doch einen Konflikt, denn unsere Relationen stimmen doch gar nicht überein, oder?

[kevin]

GRUB mappt überhaupt nichts. Der gibt dir Einträge zurück wie "von 0x0 bis 0x9fc00 ist frei". Was du dann damit anstellst, ist deine Sache.

[rizor]

Achso, wo bekomme ich den Multiboot her?
Ich weiß, den erstellt GRUB aber wo liegt der?

Ein Pointer auf die Struktur liegt in ebx (oder war es eax?), wenn er in deinen Kernel springt. Am besten pushst du den auf den Stack, damit du ihn in deiner C-Hauptfunktion als Parameter nehmen kannst.

Also muss ich in meiner ASM-Routine kurz vor dem call main ein push ebx machen, oder?
und wenn ich dann main(struct multiboot_info *bla) aufrufe, habe ich die Struktur?
Kenn leider die Konvention bei x86 Prozessoren bei der Parameterübergabe nicht.
Habe vorher nur auf dem ARM Hardwarenah programmiert.

Gruß
rizor

[kevin]

Ja, das sollte so passen. Steht aber auch nochmal in unserem Wiki.

[rizor]

Danke.
Hat funktioniert.
Ich habe mir mal den Code des LOST angeschaut.
Dabei kamen ein paar Fragen auf:
1. Wieso nimmt man in die Bitmap nur freien Speicher auf?
Wir suchen uns doch eine obere Grenze, die auf das letzte besetzte Element zeigt.
2. Wieso suchen wir den Speicher erst nach freien Blöcken ab und danach wieder nach besetzten?
Reicht es nicht alles als besetzt zu markieren und danach wieder die wirklich freien Bereiche wieder freigeben?

Gruß
rizor

[kevin]

Wenn du es so einfach hinkriegst, nur die wirklich freien Bereiche aufzuzählen, dann kannst du das ohne weiteres so machen. Die Weise wie es in kernel2 implementiert ist, ist aber wie ich es am einfachsten gefunden habe. Die BIOS-Memory-Map sagt erst einmal, wo grundsätzlich frei sein könnte, und aus diesem freien Speicher muß man wieder die Bereiche herausschneiden, wo der Kernel usw. liegen.

[rizor]

Ich habe noch einmal eine Frage zu den Bitmaps.
Damit ich den Speicher mappen kann, muss ich mir ja den reservierten Speicher suchen.
Nun habe ich mir das mal in LOST angeschaut und fand die Idee nicht schlecht, dass ihr gleich mal die Rückgabewerte "parametrisiert".
Mein Problem ist nur, dass ich nicht weiß, wo mein Kernel liegt.
Ich habe gesehen, dass ihr das im linker macht.
Ich habe leider nur keine Ahnung von linker-files.
Nun habe ich mir überlegt, dass ich das doch auch von Hand berechnen kann.
Das müsste doch ohne weiteres gehen, oder?

Dazu habe ich noch eine Frage zu meinem Code:

Code: [Auswählen]

physmemm_bitmap[bitmap_index] |= 1 << (((size_t) block / BLOCK_SIZE) & (BITS_PER_BLOCK - 1));
Hier sagt mein Compiler, dass ihm eine ) fehlt.
Das stimmt ja leider nicht.
Meine IDE meckert auch nicht.
Wieso könnte der gcc meckern?
Vllt ist auch einfach nur zu spät und ich bin betriebsblind.

Gruß
Sven

[kevin]

Mein Problem ist nur, dass ich nicht weiß, wo mein Kernel liegt.
Ich habe gesehen, dass ihr das im linker macht.
Ich habe leider nur keine Ahnung von linker-files.
Nun habe ich mir überlegt, dass ich das doch auch von Hand berechnen kann.
Das müsste doch ohne weiteres gehen, oder?

Den Anfang kennst du, weil du den ja sowieso dem Linker vorgibst. Aber wie willst du rauskriegen, wo der Kernel zu Ende ist?

Von den Linker-Skripten brauchst du eigentlich nicht groß Ahnung haben. Kopier was funktionierendes und gut.

Dazu habe ich noch eine Frage zu meinem Code:

Code: [Auswählen]

physmemm_bitmap[bitmap_index] |= 1 << (((size_t) block / BLOCK_SIZE) & (BITS_PER_BLOCK - 1));
Hier sagt mein Compiler, dass ihm eine ) fehlt.

Was ist denn die genaue Fehlermeldung? Vielleicht irgendwas in einer Zeile ein Stück vorher kaputt?

[rizor]

Mein Problem ist nur, dass ich nicht weiß, wo mein Kernel liegt.
Ich habe gesehen, dass ihr das im linker macht.
Ich habe leider nur keine Ahnung von linker-files.
Nun habe ich mir überlegt, dass ich das doch auch von Hand berechnen kann.
Das müsste doch ohne weiteres gehen, oder?

Den Anfang kennst du, weil du den ja sowieso dem Linker vorgibst. Aber wie willst du rauskriegen, wo der Kernel zu Ende ist?

Ich habe mir mal den Linker vom LOST angeschaut.
Da berechnest du doch nur ALGN(4096) von der Startadresse und das ist das Ende.

Zu dem Code-Stück:
Da ist sonst kein Fehler.

Code: [Auswählen]

void phys_mark_range_free(physaddr_t block , size_t size){
size_t i;

for(i = 0; i < size; i++){
size_t bitmap_index = (size_t) block / BLOCK_SIZE / BITS_PER_BLOCK;
physmemm_bitmap[bitmap_index] |=
1 << (((size_t) block / BLOCK_SIZE) & (BITS_PER_BLOCK - 1));
}
}

Außerdem hat er ein prblem wenn ich mit den werten arbeite, die im Linker definiert sind.
Dann gibt mir der Compiler den Fehler, dass die void* nicht ignoriert werden, wie es sein sollte.

[kevin]

Ich habe mir mal den Linker vom LOST angeschaut.
Da berechnest du doch nur ALGN(4096) von der Startadresse und das ist das Ende.

Mal abgesehen davon, daß dazwischen auch noch .text und die ganzen anderen Sections (auf deutsch: der komplette Kernel) eingefügt werden und damit die aktuelle Position verändern, ja.

[rizor]

Bei meinem Compiler-Fehler konnte ich den Schädling nun finden.
Das problem liegt bei BITS_PER_ELEMENT (8*sizeof(unsigned int))
Leider bekomme ich den Fehler nur behoben, wenn ich die Berechnung der Größe direkt angebe, dann kompiliert er.
Aber wieso kompiliert er es nicht mit BITS_PER_ELEMENT?
Wenn ich es auslagere und dann die neue Variable angebe, meldet er, dass BITS_PER_ELEMENT ohne Auswirkungen bleibt.

[rizor]

Eine Sache verstehe ich immer noch nicht.
Ich habe es jetzt mal einfach übernommen, weil ich dachte, dass mir das dann später klra wird.
Ist es aber leider nicht.
Beim Berechnen der Bitmap-Größe hat der LOST folgende Abfrage:

Code: [Auswählen]

((dword) (mmap[i].mm_base_addr + mmap[i].mm_length)
                > (dword) (uintptr_t) upper_end) && (mmap[i].mm_type == 1)
Warum?
Wenn ich die Abfrage richtig verstehe, schauen wir nach ob das untere Ende eine Map unter unserem eigenen upper_end liegt.
Wenn dann auch noch der Speicher frei ist, wird das auch noch erfüllt, haben wir eine neue obere Grenze wieso?
Damit verlieren wir doch speicher für unsere Bitmap, oder?

Wenn ich mir überlege, dass der Speicher von 0 - FF1 belegt ist und dann eine Map ab FF2-FF3 frei ist, wird unsere neue obere Grenze fpr die Bitmap FF3, oder?
Dann ist 0-FF1 nicht in unserer Bitmap.
Oder halt ein anderer Teil dieser Größe.
Das wirkt für mich ein wenig unlogisch.

Hoffe ihr könnt Licht ins dunkel bringen.

Gruß
rizor

[kevin]

Wieso sollte der Teil nicht von der Bitmap abgedeckt sein? Der Code, den du zitierst, sucht einfach nur die höchste freie Adresse raus. Wenn man die Bitmap dann so groß macht, daß sie von Null bis zur dieser Adresse alles abdeckt, ist der gesamte eingebaute RAM versorgt.

[rizor]

Aber was ist, wenn der letzte Teil des RAMs belegt ist?
Dann fehlt dieser Teil doch, denn die Länge, des Blocks, der in der Bitmap steht, gibt doch nur an, dass bis zu diesem Punkt die Bedingung gilt, dass der Speicher frei ist, oder?

[kevin]

Was soll ich denn Speicher verwalten, den ich eh nicht benutzen darf?