Need Help implementing Paging with a bitmap

[ChristianF]

Hi
I am implementing a Paging Management Routine. But there are some questions i have.
So first of all, this is my code:

Code: Select all

unsigned long page_usage_bitmap[32768];
unsigned long *frames;

unsigned long max_mem;
unsigned long num_pages;
unsigned long size_bitmap;

unsigned int find_free_frame(void)
{
	unsigned int i;
	// Find a 32-Bit entry where a free Frame is available
	for(i = 0; ((frames[i] == 0xFFFFFFFF) && i < (size_bitmap)); i++);
	
	for(j = 0; j < 32; j++)
	{
		check = 1 << j;
		/* Test wheather Page is free or not */
		if(!(frames[i] & check))
			return( ((i * 32) + j) );	/* We found a free frame, so return it */
	}
}
void init_frame_allocation(multiboot_info_t *mbt)
{
	int i=0, address;
	
	/* ToDo: Change */
	num_pages = ((mem_lower + mem_upper) * 1024) / 4096;
	/* Calculate the Size of the bitmap */
	size_bitmap = (num_pages / 32) * 4;
	
	frames = (unsigned long *)kmalloc(size_bitmap);
	
	memset((void*)frames, 0, size_bitmap);
}

My Question is now, how do i translate this value to an address, for writing it into a Page in the Page Table in my Page Directory?

Example:
i = 5
j = 24
so the function will return (5*32)+24 which is 184.
and this is not an address or is it?


Cheers Christian

[JamesM]

Hi,

184 is the page index. Your function is telling you that the 184'th page is free. So to get an address, you shift it right 12 bits (or multiply by 0x1000, it doesnt matter because the compiler will reduce it to a shift anyway).

Code: Select all

my_address = my_page_index << 12;

Cheers,

James

[ChristianF]

Ok
that makes the things clear.
So what I have to do next is:

• * Set the Bit in the selected entry (In this Example 5 and Bit 24)
  * And Write the Address into a Page Table managed by page_usage_bitmap.

Is this correct or have i forgotten something?

Cheers Christian

* EDIT *
There is now another question.
I have my Kernel ported to an Higher Half Kernel. All works nice, but when I try to use the multiboot_info_t structure vie pointer it restarts.
I tried setting the address back to the physical one by adding 0x40000000 like this:

Code: Select all

int main(unsigned long magic, multiboot_info_t *mbt)
{
    /* Translate Address of mbt from virtual into a physical one */
    mbt += 0x40000000;
	/* Function initialises the Kernel */
	init_kernel(mbt);

	for (;;);
	return(0);
}

But it doesn't work. Is there any way tosolve this problem?
When I'm doing something wrong so I actually don't see it.

* EDIT 2 *
Here is this what is logged by bochs:

Code: Select all

00000817755i[BIOS ] Booting from 0000:7C00
00002219132i[BIOS ] int13_harddisk: function 41, unmapped device for ELDL=80
00002223892i[BIOS ] int13_harddisk: function 08, unmapped device for ELDL=80
00002228536i[BIOS ] *** int 15h function AX=00C0, BX=0000 not yet supported!
00028210993i[CPU  ] protected mode
00028210993i[CPU  ] CS.d_b = 32 bit
00028210993i[CPU  ] SS.d_b = 32 bit
00028210993i[CPU  ] | EAX=80000011  EBX=0002bdc0  ECX=0002bdc0  EDX=00000400
00028210993i[CPU  ] | ESP=c012abf0  EBP=00067f00  ESI=0002bf37  EDI=0002bf38
00028210993i[CPU  ] | IOPL=0 id vip vif ac vm RF nt of df if tf SF zf af PF cf
00028210993i[CPU  ] | SEG selector     base    limit G D
00028210993i[CPU  ] | SEG sltr(index|ti|rpl)     base    limit G D
00028210993i[CPU  ] |  CS:0008( 0001| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] |  DS:0010( 0002| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] |  SS:0010( 0002| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] |  ES:0010( 0002| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] |  FS:0010( 0002| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] |  GS:0010( 0002| 0|  0) 40000000 000fffff 1 1
00028210993i[CPU  ] | EIP=c0100443 (c0100443)
00028210993i[CPU  ] | CR0=0x80000011 CR1=0 CR2=0x4002bdc4
00028210993i[CPU  ] | CR3=0x00103000 CR4=0x00000000
00028210993i[CPU  ] >> mov eax, dword ptr ds:[ecx+0x4] : 8B4104
00028210993e[CPU  ] exception(): 3rd (13) exception with no resolution, shutdown status is 00h, resetting
00028210993i[SYS  ] bx_pc_system_c::Reset(SOFTWARE) called
00028214435i[BIOS ] $Revision: 1.183 $ $Date: 2007/09/10 20:00:29 $
00028528068i[KBD  ] reset-disable command received

[ChristianF]

Mhhh.....
The Restart Occurs when i want to use the Multiboot Structure (from a called function).
I have tested it in the main Function and it Works.
But why not in a called Function?

Cheers
Christian

* EDIT *
So Stupid.
I found the failure. When I give a pointer to a function, the function must use a pointer of a pointer. Like this:

Code: Select all

int main(multiboot_info_t *mbt);
void init_kernel(multiboot_info_t **mbt);

[pcmattman]

Your "answer" to the problem isn't actually correct - init_kernel should work without requiring a pointer to a pointer.

Also,

Code: Select all

    /* Translate Address of mbt from virtual into a physical one */
    mbt += 0x40000000; 

The multiboot header pointer is already a physical address, though it may not be mapped into your address space.

[ChristianF]

mmhhhhh....
I mapped the first 4 MB to 0..4 MB and 3072...3076 MB.
I will look later, how i solve this problem.
Thanks

* EDIT *
It looks like he is accessing unmapped Memory, somewhere above 8 MB.
But why?
It was not there before it was an Higher Half Kernel.

[ChristianF]

It works now.
But there are some new questions now.

I have actually a frame, which manages the free and used pages.
Then there is an Array which is called page_usage_bitmap. It manages the the used pages. Here I have to search for a free entry for mapping the frame-address to a page.

Now my question is, how I should write the Function that it can be used for usermode page allocation too?
Or should I write an extra function for this?
Here is a prototype of what i have thought out:

Code: Select all

unsigned int allocate_page(int _iskernel);

So I have to check if _iskernel is true, so allocate it somewhere after 0xC0000000.
Or is there an better way?

Cheers Christian

[jgraef]

Hi,

I think it would be easier for us to help you if you could write whether it is a physical or virtual page each time you mention one. Without that I just don't understand what is what.

[AJ]

I think there is some major confusion here about what a memory allocator should actually do. If you want the 'traditional' memory allocation style, you basically have three items you can think of as discrete 'units':

1. The physical frame allocator. Contains a stack/bitmap(/other?) of physical page frames which can be quickly allocated as needed.

2. The virtual address space allocator which does not need to know about page frames (if you need page alignment for a particular allocation, this can be added to your virtual address space allocator later on). Think of this as a 'heap manager' - for an excellent tutorial on this one, see James Molloy's Tutorials.

3. The paging mechanism, which can simply be a PFE handler and is the glue between 1 and 2. Every time your heap manager allocates memory which is not paged in and that memory is used, a page fault exception occurs. Your PFE handler checks whether this address is inside a valid heap (see 2.). If it is, the PFE handler calls the page frame allocator and pages in with the approproate privileges.

Later on, you can start worrying about how to free unused pages and so on. You do not need a page frame allocator for virtual memory space unless you are a) doing something quite unusual or b) have a separate area reserved for memory mapping devices.

Cheers,
Adam

[ChristianF]

HiHo
Okay I understood it.
So I am coding for a while at my functions to allocate and free a page.
But there is an error in the code which is a little bit weird.
My Code looks like this:

Code: Select all

void free_page(unsigned int _address)
{
    unsigned int page_index, table_index, index, frame, address, *page_pointer = NULL;

    printf("Freeing Page!\n");

    /* Remove the entry from page_usage_bitmap */
    clear_page(_address);

    /* Change _address to an index */
    index = address / 0x1000;
    table_index = index / 1024;
    page_index = index % 1024;
    // When I remove the following printf, it jumps every time in the else-case
    printf("_address: 0x%x\nindex: 0x%x\ntable_index: %d\npage_index: %d\n", _address, index, table_index, page_index);
    if(kernelpagedir[table_index])
    {
        printf("1");
        page_pointer = &kernelpagedir[table_index];
        if(page_pointer[page_index])
        {
            printf("2");
            frame = page_pointer[page_index];
            clear_frame(frame);
            page_pointer[page_index] = 0;
        }
        else
            return;
    }
    else
        return;
}

So when I remove the printf(...) the function jumps every time in the else-case. With the printf(...) the function works.
What the hell is wrong in this piece of code?

Cheers Christian


* EDIT 1 *
When there is no pagetable allocated, the value of "kernelpagedir[table_index]" is 0.

Code: Select all

for(k = 0; k < 1024; k++)
{
        kernelpagedir[k]    = 0;        /* clear the page directory entries */
}

So I can check if the value of "kernelpagedir[table_index]" is true.

* EDIT 2 *
It is working now.
The Error was in the allocation method. The pointer to the pagetable there but in free_page too was set up wrong.

[ChristianF]

Ok
Now i have one last barrier.
I Save the Frame-Adresses in the Page-Table without the rights, e.g. supervisor, no user and so on like this:

Code: Select all

page_pointer[page_index] = frame;

I changed it into this one:

Code: Select all

page_pointer[page_index] = frame | 0x3;

This will later be changed by looking for things like: should it be for user-mode or is it writeable and so on.

But now I have to get the Frame Address for freeing a page and it is not always 0x3 (f.e. 0x7).
How could I extract this value.
When this is finished, so paging is finished and i will go further to the heap management.
Could you please help me?

Cheers Christian

[ChristianF]

Mmmmhhh...
According to this image:

(From James Molloys Tutorial)
I hget the first 20 Bits, when I allocate a Frame with my bitmap.
When this is right, so I have to Hang on 12 More Bits at the end of the frame address, like User and Present and so on.
Is this right or am I wrong?

Cheers Christian

[AJ]

That's right - bits 0-11 are used for control flags, which is why you must use at most 4kib page-aligned frames (any higher resolution and you start interfering with the flags).

Cheers,
Adam

[ChristianF]

Ok.
Now I get it.
My Functions to allocate and free a page now looks like this:

Code: Select all

unsigned int allocate_page(unsigned int _address, int _iskernel, int _iswriteable)
{
    unsigned int index, table_index, page_index, tmp, frame, access_bits = 0x0;
    /* Pointer for page_table */
    unsigned long *page_pointer = NULL;

    // Test weather Page is in User Mode or not
    access_bits |= (_iskernel)?0x0:0x4;
    // Test if Page should be writeable
    access_bits |= (_iswriteable)?0x2:0x0;
    // Set Present Bit
    access_bits |= 0x1;

    index = _address / 0x1000;
    table_index = index / 1024;
    page_index = index % 1024;
    if(kernelpagedir[table_index] != 0)
    {
        page_pointer = (unsigned long *)((kernelpagedir[table_index] & (~(0x7))) & (~(0xFFF)));
        if(page_pointer[page_index])
            return(_address); /* if page is already allocated return the address and exit earlier */
    }
    else
    {
        page_pointer = (unsigned long *)kmalloc_ap((sizeof(unsigned long) * 1024), &tmp);
        memset(page_pointer, 0, 0x1000);
        kernelpagedir[table_index] = tmp | 0x7; // Present, Read Write, User
    }
    frame = allocate_frame(_iskernel, _iswriteable);

    page_pointer[page_index] = frame | access_bits;

    return(_address);
}



void free_page(unsigned int _address)
{
    unsigned int page_index, table_index, index, frame;
    unsigned long *page_pointer = NULL;

    /* Change _address to an index */
    index = _address / 0x1000;
    table_index = index / 1024;
    page_index = index % 1024;

    if(kernelpagedir[table_index])
    {
        page_pointer = (unsigned long *)((kernelpagedir[table_index] & (~(0x7))) & (~(0xFFF)));
        if(page_pointer[page_index])
        {
            frame = page_pointer[page_index];

            frame ^= (frame & 0x1)?0x1:0x0;
            frame ^= (frame & 0x2)?0x2:0x0;
            frame ^= (frame & 0x4)?0x4:0x0;

            free_frame(frame);
            page_pointer[page_index] = 0 | 0;
        }
        else
            return;
    }
    else
        return;
}

What is your opinion to my code.
Is it okay so or should I change some parts?

Cheers Christian

* EDIT 1 *
The only Thing is, when I free a page, i set the page entry to 0.
Now there is a pointer set on this page in the Memory. So it should give an Page Fault, when I try to access this site, after freeing the page.
Here is an example:

Code: Select all

unsigned int *a = allocate_page(0xE0000000,1,1);
*a = 5;
free_page(a);
*a = 10; // At this Point the Exception Handler should be called, but nothing happens.

Do I have to set the Page Table Entry to a special Value other than 0?

[ChristianF]

Hummm...
it took a while until I found a simple failure in my paging code.
A Page Fault occurs, when I want to access Memory which isn't mapped, so I mapped my Page Directory as Page Table.

Now, the problem may be easy to solve, but I don't get it.
I have an Index 831 within the Page Directory Index 2. I want to Access the Memory via "unsigned int"-pointer. So calculate the address should be (2*1024+831)*0x1000, but when I try to access the calculated Address a Page Fault occurs that says that the Address is mapped read-only. Originally it is mapped with 0x7, because it is a page table.

What is wrong within this calculation?

EDIT:
I got it. It was the wrong index.
I allocate it with Page Index - 1, but for address calculation I have to use the normal page index.
So the right calculation is the following: (2*1024+832)*0x1000