Thema: Paging

[rizor]

Ich habe mitlerweile herausgefunden, warum er auf die Adresse zugreifen will.
Habe meine Directory mit den Flags falsch in die Directory eingetragen.
Vorher:
paging_directory[PAGING_VIRTADDR >> PAGING_DIR_SHIFT] = (dword)paging_directory | PAGING_PRESENT | PAGING_WRITEABLE;
Nachher:
paging_directory[PAGING_VIRTADDR << PAGING_DIR_SHIFT] = (dword)paging_directory | PAGING_PRESENT | PAGING_WRITEABLE;

So herum müsste es jetzt richtig sein, oder?

[kevin]

Eher nicht, die alte Variante sieht mir vernünftiger aus.

[rizor]

Ach ja, ich kenne ja die virtuelle Adresse.
Die Frage ist, woran liegt es dann?
Die Adresse die ich  aus dem Rechtsshift erhalte ist dann genau die Adresse die im cr2 register liegt.
Die Frage ist jetzt nur, wieso versucht er daruf zuzugreifen?

[rizor]

Nabend,

ich habe mir mal Gedanken gemacht, ob mein Algorithmus überhaupt richtig ist.
So wie ich euer Wiki dazu verstanden habe, muss ich mir zu jeder virtuellen Adresse die Directory, etc suchen.
Dann habe ich aber woanders gelesen, dass ich mir die Stelle in der Directory suche (für die virtuelle Startadresse) und ab da für eine bestimmte Länge jedes Nachfolgeelement mit der physikalischen Adresse belege.

Das klingt für mich auch logischer, da das ja die externe Fragmentierung verhindert.
Also habe ich das mal so programmiert.
Leider funktioniert das immer noch nicht.
Schaut euch mal bitte den Code an.
Vllt findet ihr den Fehler.

Code: [Auswählen]

void map_pages(physaddr_t paddr , virtaddr_t vaddr , paging_flags flags , size_t size){
    size_t i , offset = (dword)vaddr >> PAGING_TAB_SHIFT;;
    dword phys_addr;
    paging_directory_t requested_directory = (paging_directory_t)paging_directory[(dword)vaddr >> PAGING_DIR_SHIFT];
    paging_table_t requested_table;

    if((dword)requested_directory & PAGING_PAGE_FREE){
        //request memory for the table and prepare it to run
        requested_table = phys_alloc(PAGING_TABLE_SIZE * sizeof(paging_table_t) / BLOCK_SIZE);
        for(i = 0; i < PAGING_TABLE_SIZE; i++)
            requested_table[i] = 0 | PAGING_PAGE_FREE;
        //include the new table to the directory
        requested_directory = requested_table;
        //map the physical addresses
        for(i = 0; i < size; i++){
            phys_addr = (dword)paddr + i * BLOCK_SIZE;
            requested_table[offset + i] = phys_addr | flags | PAGING_PAGE_INUSE;
        }
    }
    else if((dword)(requested_table = (paging_table_t)requested_directory[offset]) & PAGING_PAGE_FREE){
        //go through the tavle at the requested addresses
        for(i = 0; i < size; i++){
            phys_addr = (dword)paddr + i * BLOCK_SIZE;
            //check if the entry is empty
            if((dword)requested_table[i] & PAGING_PAGE_FREE)
                requested_table[i] = phys_addr | flags | PAGING_PAGE_INUSE;
            else
                panic("Tried to write into a set table-entry");
        }
    }
    else
        panic("Tried to write into a set table-entry");
}

Danke für eure Hilfe.

[kevin]

Code: [Auswählen]

void map_pages(physaddr_t paddr , virtaddr_t vaddr , paging_flags flags , size_t size){
    size_t i , offset = (dword)vaddr >> PAGING_TAB_SHIFT;;
    dword phys_addr;
    paging_directory_t requested_directory = (paging_directory_t)paging_directory[(dword)vaddr >> PAGING_DIR_SHIFT];
    paging_table_t requested_table;

    if((dword)requested_directory & PAGING_PAGE_FREE){
        //request memory for the table and prepare it to run
        requested_table = phys_alloc(PAGING_TABLE_SIZE * sizeof(paging_table_t) / BLOCK_SIZE);
        for(i = 0; i < PAGING_TABLE_SIZE; i++)
            requested_table[i] = 0 | PAGING_PAGE_FREE;Ist an dieser Stelle Paging noch aus? Sonst ist das falsch, du greifst hier auf physische Adressen zu.

Code: [Auswählen]

        //include the new table to the directory
        requested_directory = requested_table;Ähm, sicher?

Code: [Auswählen]

        //map the physical addresses
        for(i = 0; i < size; i++){
            phys_addr = (dword)paddr + i * BLOCK_SIZE;
            requested_table[offset + i] = phys_addr | flags | PAGING_PAGE_INUSE;Wofür hast du ein FREE und ein INUSE?

Code: [Auswählen]

        }
    }
    else if((dword)(requested_table = (paging_table_t)requested_directory[offset]) & PAGING_PAGE_FREE){Ob eine Page Table frei ist, wird nirgends gesetzt, wenn ich das richtig sehe. Und wenn du das requested_table als Pointer benutzen willst, dann solltest du vielleicht vorher die Flags rausmachen...

Code: [Auswählen]

        //go through the tavle at the requested addresses
        for(i = 0; i < size; i++){
            phys_addr = (dword)paddr + i * BLOCK_SIZE;
            //check if the entry is empty
            if((dword)requested_table[i] & PAGING_PAGE_FREE)
                requested_table[i] = phys_addr | flags | PAGING_PAGE_INUSE;
            else
                panic("Tried to write into a set table-entry");
        }
    }
    else
        panic("Tried to write into a set table-entry");
}
Was passiert, wenn sich ein Aufruf über mehrere Page Tables erstreckt? Dein Code würde dann halt irgendwo in die Landschaft schreiben - gelegentlich auch Buffer Overflow genannt.

Die Gültigkeit der Parameter zu überprüfen wäre auch keine schlechte Idee, aber daran liegt es vermutlich erstmal nicht.

[rizor]

Ist an dieser Stelle Paging noch aus? Sonst ist das falsch, du greifst hier auf physische Adressen zu.

Ja, an dieser Stelle ist Paging noch aus.

Ähm, sicher?

Wie sollte ich die neue Table denn dann in die Directory eintragen?
Im Prinzip muss ich die Tabelle doch genau an der Stelle eintragen.

Wofür hast du ein FREE und ein INUSE?

Die benutze ich in den Bits, die für das OS da sind.
Da wird dann später geschaut, ob die Table geswapped wurde.

Ob eine Page Table frei ist, wird nirgends gesetzt, wenn ich das richtig sehe. Und wenn du das requested_table als Pointer benutzen willst, dann solltest du vielleicht vorher die Flags rausmachen...

Das setze ich ja, wenn ich sehe, dass die Table noch nicht existiert.

[rizor]

Ich bin den Code jetzt immer wieder durchgegangen.
Finde den Fehler aber nicht.
Die Methode zur Initialisierung des Pagings hat sich nicht geändert.
Könnt ihr einen Fehler erkennen, außer dass ich nicht alle Parameter auf Korrektheit überprüfe?

Danke für eure Hilfe.

Gruß
rizor

[rizor]

Nabend zusammen,

habe mir noch einmal den Code angeschaut und ihn elementarer gemacht.
Leider geht es immer noch nicht.
Mein File zum Paging sieht jetzt so aus:

Code: [Auswählen]

#include <kernel32.h>
 #include <memory/mmu.h>
 #include <memory/pmmu.h>

//internal methods
void map_pages(physaddr_t , virtaddr_t , cond_flags , size_t);
void directory_init();
void printReserved(int , int);

//methods from the asm-file
extern void _write_cr3(dword);
extern void _write_cr0(dword);
extern dword _read_cr0();
extern dword _read_cr3();

page_table_t directory;
extern dword bitmap_length;
extern dword *bitmap_virt;

void paging_init(){
    size_t param;
    //initialize the directory
    directory_init();

    //map the kernel
    param = ((dword)kernel_end - (dword)kernel_start) / BLOCK_SIZE;
    map_pages(kernel_start , kernel_mem_start , PAGE_READWRITE | PAGE_PRESENT , param);

    //map the video
    param = 80 * 25 * 2 / BLOCK_SIZE + 1;
    map_pages((physaddr_t)0xB8000 , (virtaddr_t)0xB8000 , PAGE_READWRITE | PAGE_PRESENT , param);

    //map the directory
    map_pages(directory , directory , PAGE_READWRITE | PAGE_PRESENT , 1);

    //map the bitmap
    param = bitmap_length / BLOCK_SIZE;
    map_pages(bitmap_virt , bitmap_virt , PAGE_READWRITE | PAGE_PRESENT , param);

    _write_cr3((dword)directory);
    _write_cr0((_read_cr0() | 0x80000000));
}

void directory_init(){
    size_t i;
    directory = phys_alloc(TABLE_SIZE * sizeof(page_table_t) / BLOCK_SIZE);

    memset(directory , 0 , TABLE_SIZE);
}

void map_pages(physaddr_t paddr , virtaddr_t vaddr , cond_flags flags , size_t size){
    size_t i , offset = ((dword)vaddr >> SHIFT_PAGE) % TABLE_SIZE;
    page_table_t table;
    dword phys_addr;

    if(size >= TABLE_SIZE - offset){
        //TODO: change parameters
    }

    if(directory[(dword)vaddr >> SHIFT_DIRECTORY] == NULL){
        puts("Generating new table\n");
        //prepare the table
        table = phys_alloc(TABLE_SIZE * sizeof(page_table_t) / BLOCK_SIZE);
        memset(table , 0 , TABLE_SIZE);

        //register in the directory
        directory[(dword)vaddr >> SHIFT_DIRECTORY] = (dword)table | PAGE_PRESENT | PAGE_READWRITE;
    }

    table = (page_table_t)directory[(dword)vaddr >> SHIFT_DIRECTORY];
    for(i = 0; i <= size; i++){
        phys_addr = (dword)paddr + i * BLOCK_SIZE;

        table[offset + i] = phys_addr | flags;
    }
}

Habe immer noch keine Ahnung woran das liegt.
Die Berechnung müsste ja an sich stimmen.
Seht ihr nun vllt den Fehler?

Gruß
rizor

[EDIT]
Stimmt meine Theorie überhaupt, dass ich einfach nur die Offset-Adresse berechne und Dann in meinem Array einfach solange hoch zählen muss, bis alles gemappt ist, was im physischen Speicher liegt?

[tarrox]

Hab mal durgeschaut und ein paar Fehler gefunden.

Code: [Auswählen]

#include <kernel32.h>
 #include <memory/mmu.h>
 #include <memory/pmmu.h>

//internal methods
void map_pages(physaddr_t , virtaddr_t , cond_flags , size_t);
void directory_init();
void printReserved(int , int);

//methods from the asm-file
extern void _write_cr3(dword);
extern void _write_cr0(dword);
extern dword _read_cr0();
extern dword _read_cr3();

page_table_t directory;
extern dword bitmap_length;
extern dword *bitmap_virt;

void paging_init(){
    size_t param;
    //initialize the directory
    directory_init();

    //map the kernel
    param = ((dword)kernel_end - (dword)kernel_start) / BLOCK_SIZE;
    map_pages(kernel_start , kernel_mem_start , PAGE_READWRITE | PAGE_PRESENT , param);

    //map the video
    param = 80 * 25 * 2 / BLOCK_SIZE + 1;
    map_pages((physaddr_t)0xB8000 , (virtaddr_t)0xB8000 , PAGE_READWRITE | PAGE_PRESENT , param);

    //map the directory
    map_pages(directory , directory , PAGE_READWRITE | PAGE_PRESENT , 1);

    //map the bitmap
    param = bitmap_length / BLOCK_SIZE;
    map_pages(bitmap_virt , bitmap_virt , PAGE_READWRITE | PAGE_PRESENT , param);

    _write_cr3((dword)directory);
    _write_cr0((_read_cr0() | 0x80000000));
}

void directory_init(){
    size_t i;
    directory = phys_alloc(TABLE_SIZE * sizeof(page_table_t) / BLOCK_SIZE);

    memset(directory , 0 , TABLE_SIZE);
}

void map_pages(physaddr_t paddr , virtaddr_t vaddr , cond_flags flags , size_t size){
    size_t i , offset = ((dword)vaddr >> SHIFT_PAGE) % TABLE_SIZE;
    page_table_t table;
    dword phys_addr;
Ich frag mich was du hier machst? Dir ist schon klar, dass du mindestens 3073 Pages anfragen musst, damit diese Bedingung erfüllt ist. Ich denke nicht, dass du das gemeint hast.

Code: [Auswählen]

    if(size >= TABLE_SIZE - offset){
        //TODO: change parameters
    }

    if(directory[(dword)vaddr >> SHIFT_DIRECTORY] == NULL){
        puts("Generating new table\n");
        //prepare the table
        table = phys_alloc(TABLE_SIZE * sizeof(page_table_t) / BLOCK_SIZE);
Sollte jetzt noch nicht stören, wird es aber wenn das Paging aktiviert ist, den dann greifst du auf ungemappten Speicher zu sehr sehr böse. Daher erst zuweisen dann Nullen.

Code: [Auswählen]

        memset(table , 0 , TABLE_SIZE);

        //register in the directory
        directory[(dword)vaddr >> SHIFT_DIRECTORY] = (dword)table | PAGE_PRESENT | PAGE_READWRITE;
    }

Hier hast du wohl vergessen, das im directory Eintrag noch die Flags sind, die musst du rausnehmen bevor du die Richtige Table Adresse erhältst.

Code: [Auswählen]

    table = (page_table_t)directory[(dword)vaddr >> SHIFT_DIRECTORY];
    for(i = 0; i <= size; i++){
        phys_addr = (dword)paddr + i * BLOCK_SIZE;

        table[offset + i] = phys_addr | flags;
    }
}


Stimmt meine Theorie überhaupt, dass ich einfach nur die Offset-Adresse berechne und Dann in meinem Array einfach solange hoch zählen muss, bis alles gemappt ist, was im physischen Speicher liegt?

Stimmt soweit nur solltest du mitbedenken, das das Maximum für das offset 1023 ist und du dannach denn nächsten directory Eintrag nehmen solltest.

Ansonsten würde mich interessieren wie page_table_t aussieht. Und ob du auch wirklich Adressen vom Physischem Memory Manager kreigst die Page Alligned sind. Ansonsten musst du alle Werte dir ausgeben lassen und schaun ob nicht einer falsch ist.

[rizor]

Ich frag mich was du hier machst? Dir ist schon klar, dass du mindestens 3073 Pages anfragen musst, damit diese Bedingung erfüllt ist. Ich denke nicht, dass du das gemeint hast.

Welche Bedingung meinst du?

Code: [Auswählen]

    if(size >= TABLE_SIZE - offset){
        //TODO: change parameters
    }

    if(directory[(dword)vaddr >> SHIFT_DIRECTORY] == NULL){
        puts("Generating new table\n");
        //prepare the table
        table = phys_alloc(TABLE_SIZE * sizeof(page_table_t) / BLOCK_SIZE);
Sollte jetzt noch nicht stören, wird es aber wenn das Paging aktiviert ist, den dann greifst du auf ungemappten Speicher zu sehr sehr böse. Daher erst zuweisen dann Nullen.

Code: [Auswählen]

        memset(table , 0 , TABLE_SIZE);

        //register in the directory
        directory[(dword)vaddr >> SHIFT_DIRECTORY] = (dword)table | PAGE_PRESENT | PAGE_READWRITE;
    }


Gut, das stimmt.

Hier hast du wohl vergessen, das im directory Eintrag noch die Flags sind, die musst du rausnehmen bevor du die Richtige Table Adresse erhältst.

Code: [Auswählen]

    table = (page_table_t)directory[(dword)vaddr >> SHIFT_DIRECTORY];
    for(i = 0; i <= size; i++){
        phys_addr = (dword)paddr + i * BLOCK_SIZE;

        table[offset + i] = phys_addr | flags;
    }
}


Ja, habe ich korrigiert, ändert aber nichts an der Fehlermeldung.

Ansonsten würde mich interessieren wie page_table_t aussieht. Und ob du auch wirklich Adressen vom Physischem Memory Manager kreigst die Page Alligned sind. Ansonsten musst du alle Werte dir ausgeben lassen und schaun ob nicht einer falsch ist.

Mein page_table_t ist ein

Code: [Auswählen]

unsigned long*.
Ja, der Physische Manager liefert 4k-aligned Adressen und auch wirklich die Anfangsadresse, denn wenn ich es ganz primitiv mache und einfach die ersten 4 MB mappe, funktioniert der Code.

[rizor]

Verdammt.... habe den Fehler entdeckt.
Habe mir die Adresse, die in der Tabelle steht falsch formatiert.

Nun habe ich allerdings eine Frage zur Funktionsweise:
Wie sollte das denn nun aussehen, wenn ein neuer Prozess aufgerufen wird?
Ich könnte die neuen Prozesse ja einfach in die Directory eintragen.
Dann habe ich doch nur das Problem, dass ich Zugriffsfehler nicht feststellen kann, außer der Prozess greift in den Kernel oder die Page ist noch nicht gemappt.
Dann ist mir eingefallen, dass ich jedem Prozess ja eine eigene Directory geben könnte.
Da habe ich nur das Problem, dass ich bei jdem Prozesswechsel den Speicher swappen müsste, oder?
Ansonsten könnte es doch zu doppelten Zugriffen kommen.
Das wäre mir dann ein wenig zu viel Arbeit des Kernels.
Wie kann man das denn am besten realisieren?

[kevin]

Jeder Prozeß bekommt sein eigenes Page Directory. Beim Taskwechsel wird dann eben cr3 neu geladen.

[rizor]

Nabend,

habe jetzt nochmal eine Frage:

Wie kann ich am besten Speicher allozieren, wenn Paging aktiviert wurde?
Wollte mir der Einfachheit halber eine Liste erstellen, die alle Directories speichert.
Die Frage ist, wie mache ich das am besten?
Mein phys_alloc liefert mir ja eine physische Seite, wie mache ich daraus eine virtuelle?
Oder ist es am besten, wenn ich mir erst die virtuellen Seiten suche und danach einfach physischen Speicher alloziere und diesen dann in die neue Page eintrage?

[kevin]

Die Liste aller PDs entspricht ja ziemlich genau der Liste aller Prozesse, und die brauchst du so oder so.

Aber von einer physischen Adresse auf die virtuelle schließen mußt du eigentlich nie. Beim Allozieren suchst du eben einen freien Platz im virtuellen Adreßraum, mappst die physische Seite, die du von phys_alloc bekommst, und gibst dann die virtuelle Adresse zurück. Alles weitere arbeitet dann nur noch mit virtuellen Adressen. Was du gelegentlich brauchen kannst, ist der umgekehrte Weg, also von virtuellen Adressen  auf die zugehörigen physischen zu schließen. Das kannst du einfach in der passenden Page Table nachschlagen.

[rizor]

Nabend,

nun habe ich noch eine Frage zu malloc.
Wie sollte man das am besten implemeniteren.
Wenn ich bei jedem malloc eine bestimmte Anzahl an Pages abgebe kann ich doch abartig großen verschnitt haben.
Wenn ich mir überlege, dass wenn ein Prozess eine Struktur anfordert, die 12 Byte groß ist, wäre es das dümmste, wenn ich einen 4k-Block markiere.
Sollte ich den noch unterteilen?
Das würde aber wiederrum einen extremen Overhead bedeuten.

Wie macht man das am besten?

[Jidder]

Wenn du mit Unterteilen meinst, dass die restlichen 4084 Bytes der Seite dem Prozess für weitere malloc()-Aufrufe zur Verfügung stehen, dann ist das sinnvoll. Den Rest für andere Prozesse/Zwecke zu verfügbar machen, ist hingegen nicht praktikabel.

[kevin]

Und das passende Stichwort für malloc heißt Freispeicherliste.

[tarrox]

Du solltest am besten für jeden Prozess einen Heap erstellen, der die dynamische Speicherverwaltung übernimmt. Der kümmert sich darum aus den für sie vorgegebenen Pages, Speicher an den Prozess zu geben, wenn er angefordert wird (und auch wieder freizugeben).

[rizor]

Gut ok.
Ist das nicht ein enormer Speicheraufwand?
Da fällt mir auch noch eine Frage ein:

Wenn ich nun malloc/kmalloc etc implementiere, wie kommuniziert mein Programm dann mit diesen Methoden?
Über Syscalls?
Bei Linux sehe ich ja, dass das irgendwie über libc geregelt wird.
Wie mache ich das bei meinem eigenen OS und wie kann ich überhaupt shared-libraries implementieren?

[kevin]

Für malloc solltest du eher keinen Syscall nehmen, sondern eine Lib. Den Syscall sollte malloc erst aufrufen, wenn es neue Pages braucht. Du brauchst dazu nicht unbedingt Shared Libs, du kannst die libc einfach statisch dazulinken.