Thema: Speicherverwaltung

[ChristianF]

Gut soviel ist mittlerweile klar.
Nun sitze ich vor der Funktion zum berechnen der Höhe eines Teilknotens. Der balance-Wert berechnet sich ja, in dem man die höhe des Linken Teilbaums von der Höhe des rechten Teilbaumes subtrahiert.
 
Wikipedia sagt, dies wird rekursiv gelöst, das habe ich auch gemacht. Die Funktionen sehen wie folgt aus:

Code: [Auswählen]

unsigned int internal_calculate_avl_tree_balance_factor(avl_node_t *node)
{
    unsigned int retval = 1;

    /* if left and right node are NULL the lowest part has been reached */
    if((node->left == NULL) && (node->right == NULL))
        return(0);
    else
    {
        if(node->right != NULL)
            retval += internal_calculate_avl_tree_balance_factor(node->right);
        if(node->left != NULL)
            retval += internal_calculate_avl_tree_balance_factor(node->left);
    }

    return(retval);
}


/* Function calculates the new balance factor */
unsigned int calculate_avl_tree_balance_factor( avl_tree_t *tree, avl_node_t *node)
{
    unsigned int retval1 = 0;
    unsigned int retval2 = 0;
    avl_node_t *left, *right, *local_node;
/* Check if node is NULL. This should never happen */
if(node == NULL)
panic("AVL Error: node contains NULL!\nNULL is not a valid address!");

if(tree->root_node == NULL)
{
    return(0);
}
else
{
    retval1 = internal_calculate_avl_tree_balance_factor(node->right);
    retval2 = internal_calculate_avl_tree_balance_factor(node->left);

    return( retval2 - retval1 );
}
}
Meine Logik sagt mir, das sollte so funktionieren...
Mein Gefühl sagt mir allerdings, dass da noch etwas fehlt, aber ich komme nicht drauf.
Könnt Ihr mir sagen, ob der Code so richtig ist? Ich habe momentan keine Möglichkeit das ganze zu testen, weswegen ich hier poste.
 
Gruß Christian

[bluecode]

hm, ich kenn mich mit Bäumen zwar nicht so sehr aus, aber m.E. berechnest du in internal_calculate_avl_tree_balance_factor die Anzahl der Knoten (ohne Blätter) des Baumes. Du müsstest m.E. nach nur den größeren Wert von internal_calculate_avl_tree_balance_factor(node->right) und internal_calculate_avl_tree_balance_factor(node->left) hinzufügen. Ich mein die Höhe unterhalb (inklusive) dieses Knotens ergibt sich ja aus 1 + max{rechts, links}.

edit: Wobei mir gerade auffällt, dass du doch eigentlich in der Funktion die Balance berechnen wolltest...

[kevin]

Code: [Auswählen]

unsigned int internal_calculate_avl_tree_balance_factor(avl_node_t *node)
{
    unsigned int retval = 1;

    /* if left and right node are NULL the lowest part has been reached */
    if((node->left == NULL) && (node->right == NULL))
        return(0);
    else
    {
        if(node->right != NULL)
            retval += internal_calculate_avl_tree_balance_factor(node->right);
        if(node->left != NULL)
            retval += internal_calculate_avl_tree_balance_factor(node->left);


Sollte das nicht ein -= sein?

Davon abgesehen ist diese Berechnung genau das, was du willst, weil du dazu den ganzen Baum anschauen mußt. Bei nur einem Knoten ist die Balance trivialerweise 0 und beim Einfügen oder Löschen ändert sich nur lokal was. Wenn du diese lokale Änderung richtig hinkriegst, mußt du nie die Balance auf diese Weise ausrechnen, sondern nur an den passenden Stellen was addieren oder subtrahieren.

[ChristianF]

Nun, ich füge einen Knoten ein.
Dessen balance-Wert ist 0, das ist mir schon klar. Allerdings muss ich dann den balance-Wert des Elternknotens neuberechnen. Dies bewerkstellige ich, in dem ich die Höhe des linken Teilbaums von der höhe des rechten Teilbaums abziehe.
So gesehen muss ich nach dem Einfügen, bzw. Löschen eines Knotens den Baum von der Stelle aus nach oben gehen und den balance-Wert neu berechnen. Ändert sich dieser jetzt nach 2 oder -2 muss ich rotieren.
 
Aber wie soll ich denn den balance-Wert deiner Meinung nach berechnen? Ich muss von dem Knoten aus die höhen des rechten und linken unterbaumes berechnen. Das heißt, ich muss irgendwie zum tiefsten Knoten kommen den es gibt.
 
Mmmmhhh...
Mir wird schon noch ein Einfall kommen wie ich das bewerkstellige, doch momentan ist das ein kleines Hindernis, an dem ich nicht vorbeikomme, weil ich irgendwo auf dem Schlauch stehe.
 
EDIT:
So wie ich das sehe ist das wie folgt.
Durch das Einfügen eines neuen Knotens wird der balance-Wert des Elternknoten des Elternknotens um eins verringert, bzw. erhöht oder liege ich da falsch?

[kevin]

So wie ich das sehe ist das wie folgt.
Durch das Einfügen eines neuen Knotens wird der balance-Wert des Elternknoten des Elternknotens um eins verringert, bzw. erhöht oder liege ich da falsch?

Genau.

[ChristianF]

Warum habe ich das nicht gleich so gemacht... 
 
Ich habe mir ein kleines Programm gebastelt, das einen AVL-Baum zusammen baut. Bis auf die Funktionen zum Löschen eines Knotens und zum Darstellen/Ausgeben des Baums, scheint alles soweit zu funktionieren.
Hier ist der geschriebene Quellcode: http://rafb.net/p/1zNXWH89.html
 
Gruß Christian
 
PS: Vielleicht habe ich auch einen Fehler drinne, denn ob das wirklich Fehlerfrei ist, kann ich nicht sagen. Gut ich habe den Baum getestet und er hat auch immer dann balanciert, wenn er musste, trotzdem bleibt eine kleine Unsicherheit. 
 
EDIT
Anscheinend ist die Berechnung der balance nach dem rotieren doch nicht richtig 
 
EDIT 2
Ich habe den Fehler anscheinend gefunden. Nachdem ich in der funktion zum rotieren nach rechts aus dem Aufruf MAX ein MIN gemacht habe, hat es funktioniert.
Hier der Link: http://rafb.net/p/lPLs5012.html
Nur einen etwas kuriose Eigenart habe ich noch. Und zwar wird in der funktion zum balancieren geschaut, ob der balance-Wert kleiner -1 oder größer 1 ist.
Gebe ich den balance-Wert aus, so ist dieser 0. Allerdings wird jedes mal die If-Bedingung ausgeführt, ob der balance-Wert jetzt 2, bzw. -2 ist oder nicht. Irgendwas habe ich da übersehen....
 
EDIT 3
Eine kleine Frage habe ich noch. Ich muss ja den Elternknoten des Elternknotens erhöhen, bzw. verringern. Wenn ich aber beim Elternknoten den balance-Wert um 1 erhöht habe, muss ich dann beim Elternknoten des Elternknotens den balance-Wert um 2 erhöhen oder?
Damit dieser wenn ein überhang entsteht entsprechend rotiert. Also anstatt dem ++ im Quellcode ein +=2!
 
EDIT 4
Nachdem ich nun den kompletten bisherigen Code verworfen und neugeschrieben habe funktioniert nun alles. Was jetzt noch fehlt ist die Funktion zum entfernen eines Knotens, aber das werde ich wahrscheinlich auch noch hinbekommen. Wenn interesse besteht, werde ich den Code hochladen und hierher verlinken.

[ChristianF]

Immer ist irgendetwas, mit dem ich mich ärgere weil es nicht funktioniert.
Ich wollte eben meine physikalische Speicherverwaltung testen. Der Stack funktioniert tadellos, die Bitmap allerdings mal wieder nicht...
Ich finde den Fehler nicht! In einer Funktion, die in einer Endlosschleife läuft wird in jedem durchlauf eine Seite gesucht und diese dann reserviert mittels setzen in der Bitmap. Nur funktioniert das setzen wie schon einmal nur bei 0. Sobald der Rückgabewert 1 ist, wird die Page nicht mehr gesetzt.
Hier mal der Quellcode:
bitmap.h

Code: [Auswählen]

#ifndef __BITMAP_H__
#define __BITMAP_H__

#include <multiboot.h>
#include <system.h>


#define INDEX_FROM_BIT(a) (a/(8*4))
#define OFFSET_FROM_BIT(a) (a%(8*4))
#define BIT(a) (0x1<<a)


extern unsigned int *physical_bitmap;
extern unsigned int nphysical_bitmap;
extern unsigned int num_dma_pages;
extern unsigned int placement_address;


extern unsigned int phys_mem_dma_find_free_page(void);
extern unsigned int phys_mem_dma_find_free_page_range(unsigned int num);
extern unsigned int phys_mem_dma_find_free_page_range_index(unsigned int lower_index, unsigned int num);

extern void phys_mem_dma_set_page(unsigned int physical_address);
extern void phys_mem_dma_reset_page(unsigned int physical_address);
extern unsigned int phys_mem_dma_test_page(unsigned int physical_address);

extern unsigned int phys_mem_dma_available(void);

extern void initialise_phys_dma_mem_manager(multiboot_info_t *mbt);

#endifbitmap.c

Code: [Auswählen]

#include <mm/physical/bitmap.h>
#include <mm/kheap.h>
#include <mm/paging.h>

unsigned int *physical_bitmap;
unsigned int nphysical_bitmap;
unsigned int num_dma_pages;

void phys_mem_dma_set_page(unsigned int physical_address)
{
    if(physical_address == -1)
        PANIC("INVALID ADDRESS");

unsigned int frame = physical_address / PAGE_SIZE;
unsigned int index = INDEX_FROM_BIT(frame);
unsigned int offset = OFFSET_FROM_BIT(frame);

physical_bitmap[index] |= BIT(offset);
}

void phys_mem_dma_reset_page(unsigned int physical_address)
{
    if(physical_address == -1)
        PANIC("INVALID ADDRESS");

unsigned int frame = physical_address / PAGE_SIZE;
unsigned int index = INDEX_FROM_BIT(frame);
unsigned int offset = OFFSET_FROM_BIT(frame);

physical_bitmap[index] &= ~(BIT(offset));
}

unsigned int phys_mem_dma_test_page(unsigned int physical_address)
{
    if(physical_address == -1)
        PANIC("INVALID ADDRESS");

unsigned int frame = physical_address / PAGE_SIZE;
unsigned int index = INDEX_FROM_BIT(frame);
unsigned int offset = OFFSET_FROM_BIT(frame);

return( (physical_bitmap[index] & BIT(offset)) );
}

unsigned int phys_mem_dma_find_free_page(void)
{
unsigned int i, j;

for(i = 0; i < INDEX_FROM_BIT(nphysical_bitmap); i++)
{
if(physical_bitmap[i] != 0xFFFFFFFF)
{
for(j = 0; j < 32; j++)
{
if( !(physical_bitmap[i] & BIT(j)) )
return( i*4*8+j );
}
}
}

return(-1);
}

unsigned int phys_mem_dma_available(void)
{
unsigned int i, j, retval = 0;
for(i = 0; i < INDEX_FROM_BIT(nphysical_bitmap); i++)
{
if(physical_bitmap[i] == 0xFFFFFFFF)
retval += 32;
else
{
for(j = 0; j < 32; j++)
{
if( !(physical_bitmap[i] & BIT(j)) )
retval++;
}
}
}
return(retval);
}

void test_manager(void)
{
    unsigned int page = 0;
    for(;;)
    {
        page = phys_mem_dma_find_free_page();
        printf("%i\t", page);
        printf("%i\t", phys_mem_dma_available());
        phys_mem_dma_set_page(page);
    }
}
 
 
An der Funktion zum Reservieren von Speicher (kmalloc) kann es nicht liegen, denn dann würde der Stack Manager auch nicht funktionieren. Des Weiteren habe ich herausgefunden, dass das setzen der Bitmap auf 0xFFFFFFFF funktioniert, denn wenn alles auf 0xFFFFFFFF gesetzt ist, springt die Funktion zum belegen einer physikalischen Seite in die IF-Abfrage rein:

Code: [Auswählen]

int i;

for(i = 0; i < INDEX_FROM_BIT(nphysical_bitmap); i++)
        physical_bitmap[i] = 0xFFFFFFFF;

    for(i = 0; i < INDEX_FROM_BIT(nphysical_bitmap); i++)
        printf("0x%x\t", physical_bitmap[i]);Folglich muss der Fehler beim suchen nach einer freien Seite oder beim Setzen eines Eintrags sein, doch kann ich keinen Fehler erkennen. Ich weiß auch nicht, warum der Code auf einmal nicht mehr funktioniert, da er ja zuvor gelaufen ist. 

[ChristianF]

 
Ich habe so einige dumme Anfänger-Fehler gemacht, wie mir gerade auffällt. Einer davon ist z.B. bei einem Rückgabetyp unsigned int -1 zurückzugeben, das kann ja nicht funktionieren! 
 
Ich sehe schon, da muss ich wohl nochmal ran. Ich werde das ganze so abändern, dass die Adressen alle als void pointer übergeben, bzw. zurückgegeben werden. Dieser wird dann je nach dem entsprechend konvertiert.

[ChristianF]

Soso...
ich habe da nochmal eine Frage:
Und zwar braucht man für das Paging ja physikalische Adressen. So weit ist das kein Problem, denn die physikalische Speicherverwaltung funktioniert.
 
Wenn ich also eine neue Page Table brauche, reserviere ich Speicher mit dem physikalischen Speichermanager. Das funktioniert, nur der Zugriff nicht, da die Adresse logischerweise nicht gemappt wurde.
Lange rede kurzer Sinn, es tritt ein Page Fault auf, da wie bereits geschrieben, die Adresse nicht gemappt ist.
 
Ein möglicher Weg wäre, den Speicher an virtuelle Stelle zu mappen und dann zu bearbeiten. Dies würde allerdings nur funktionieren, solange ich kein neues Page Table benötige. Wie kann man das obengenannte Problem noch lösen oder gibt es da keine anderen Möglichkeiten?
 
Gruß Christian

[MNemo]

ich löse das so, dass ich eine Page Table im Kernelspace dauerhaft gemapped habe. In dieser PageTable sind ein paar Einträge nur darfür resserviert Pages temporär zu mappen, so dass ich an einer fixen Addresse auf ihren Inhalt zugreifen kann.
Damit habe ich das problem nicht, dass ich evtl. eine neue PageTable benötige.

Eine andere Möglichkeit auf physikalische Addressen zu zugreifen, als sie zu mappen, gibt es AFAIK nicht.

[kevin]

Wenn du einen Eintrag im PD auf das PD selbst zeigen läßt, hast du an der Stelle 4 MB im virtuellen Adreßraum reserviert, in denen alle Pagetables hintereinander gemappt sind. Ist auf den ersten Blick verwirrend, aber auf den zweiten recht praktisch.

[ChristianF]

mmhhh...
Also würde das dann so aussehen:
Beim Initialisieren des Paging mappe ich das Page Directory in einen freie Page Table Eintrag.
Brauche ich nun eine neue Page Table, z.B. für die Adresse 0xD0000000, so muss ich den entsprechenden Eintrag setzen und dann über den Eintrag mit dem Page Directory diesen Eintrag z.B. mit erst mit "0|0x2" und dann mit der Adresse befüllen.
 
Allerdings müsste ich dies ja dann überall machen...
mal schauen, wie ich das dann löse.
 
Danke für die Antworten.
Gruß Christian

[ChristianF]

So...
ich habe das Page Directory einfach mal in dem Index 1 abgelegt.
Nun gehe ich beim anlegen eines neuen Page Table Eintrags wie folgt vor:

• Ich suche einen freien Speicherplatz (physikalisch)
• Dieser wird auf gültigkeit geprüft und als belegt gespeichert
• Nun mappe ich diesen neuen Eintrag an die entsprechende Stelle
• Als nächstes durchsuche ich den Eintrag im Page Directory mit dem Index 2 nach der Adresse
• Diese wird gefunden und liegt an Index 831.

Bis zum letzten Punkt ist mir alles klar.
Nun ist der eigentliche Index im Page Directory an den das Table gemappt wird, jedoch 832. Gibt es dafür einen bestimmten Grund?
Des Weiteren ist die "richtige" Nummer ja 2048+831, da ich mich ja im 3. Page Directory befinde.
 
Allerdings bekomme ich beim Zugriff auf diese Adresse einen Page Fault, wo der Handler mir mitteilt, dass die Adresse nur lesbar ist.
Der Page Table Eintrag wird so gemappt:

Code: [Auswählen]

unsigned int pdir_flags = (PTE_PRESENT|PTE_WRITEABLE|PTE_USERMODE);
printf("\n\npdir_flags = 0x%x\n", pdir_flags);
page_dir[table_idx] = (unsigned int)table;
page_dir[table_idx] |= pdir_flags;
Allerdings sollte der Fehler ja nicht hier liegen oder doch?
 
Hier ist der Zugriff auf die errechnete Adresse, die den Page Fault auslöst:

Code: [Auswählen]

unsigned int *test = GET_PAGE_ADDRESS((table_idx)+(2048));
printf("test = 0x%x\n", test);
memset(test, 0|0x2, PAGE_SIZE);

Habe ich da irgendetwas nicht berücksichtigt?