Enabling Paging

[AR]

Did you actually load the page directory? If that dump is from the Bochs status terminal, it says CR3 is 0 which would be wrong. You must load CR3 first.

[calpis]

oh yeah, u ar right. CR3 has nothing...I also fixed a few mistake that i made earlier. i used the setcr3() and print out the values. which is correct.

I got the CR3 values in but as soon as I or CR0 with 0x8000 0000, it reboots itself.

I also tried to change the page directory value to 0x9FC00 with 0xA0100 for page dir and page tab.

I don't know what is wrong with it...

flags = 0x3E7
mem_lower = 639KB, mem_upper = 523264KB
boot_device = 0x8000FFFF
mdline = /kerneler.elf
elf_section:
num_of_entry = 10, size = 0x28, addr = 0x104000, shndx = 0x7
mmap_addr = 0x2CAE8, mmap_length = 0x30
size = 0x14, base_addr = 0x00, length = 0x09FC00, type = 0x1
size = 0x14, base_addr = 0x0100000, length = 0x01FF00000, type = 0x1
cr0:0x60000011 cr3:0x0 cs:0x8 ds:0x10 ss:0x10
es:0x10 fs:0x10 gs:0x10
ebp:0x1032F0 esp:0x10328C esi:0x2CB46 edi:0x103CE0
eax:0x2CA20 ebx:0x2CA20 ecx:0x0 edx:0x3D5
Interrupt is off 0
Paging Initialization.
PDir:0x9FC00 PTable:0xA0C00
.cr0:0x60000011 cr3:0x9FC00 cs:0x8 ds:0x10 ss:0x10
s:0x10 fs:0x10 gs:0x10
bp:0x1032F0 esp:0x10326C esi:0x9FC00 edi:0x103CE0
ax:0xA0C00 ebx:0xA0C00 ecx:0x0 edx:0x3D5

This is output from my grub. Please help~

ALso this is from my bochs

00000000000i[ ] PAE support: no
00000000000i[ ] PGE support: no
00000000000i[ ] PSE support: no
00000000000i[ ] x86-64 support: no
00000000000i[ ] SEP support: no
.
.
.
00006777141i[BIOS ] int15: Func 24h, subfunc 01h, A20 gate control not supported

Does it have anything to do with it?

[AR]

A20 gate control is a BIOS function for enabling A20, the Bochs BIOS doesn't support it but GRUB has code to do it manually anyway.

Page Directories are 4096 bytes long, and must be 4096 byte aligned, 0x9FC00 is not valid, the last 3 numbers should be 0.

The Page Table should be identity mapped (0=0 1=0x1000 2=0x2000 etc) and then loaded into the page directory as entry 0, if you only put it at 0xC00 in the page directory then it'll crash because it's executing at 0x100000 or wherever and the only valid memory has been put at 0xC0000000.

[calpis]

I didn't quite understand what you mean by this. But I ran a printf on page_table and directory. They give me:

Paging Initialization.Page Directory Adress: 0x2 Page Table: 0x3
Page Directory Adress: 0x2 Page Table: 0x1003
Page Directory Adress: 0x2 Page Table: 0x2003
Page Directory Adress: 0x2 Page Table: 0x3003
Page Directory Adress: 0x2 Page Table: 0x4003
....

"The Page Table should be identity mapped (0=0 1=0x1000 2=0x2000 etc) and then loaded into the page directory as entry 0, if you only put it at 0xC00 in the page directory then it'll crash because it's executing at 0x100000 or wherever and the only valid memory has been put at 0xC0000000."

This is my code to implement a basic paging. Hope you can tell me whats wrong. Thanks alot for you reply, and your patience.

Code: Select all

#include <kprintf.h>
#include <pageinit.h>
#include <regs.h>
#include <sirqswitch.h>
#include <mminit.h>
void pageinit()
{
   interrupt_off();
   kprintf("Paging Initialization");
   unsigned long *page_directory = (unsigned long *) 0x9C000;
   unsigned long *page_table = (unsigned long *) 0x9D000;
   unsigned long address = 0;
   unsigned int i;

   //map first 4MB of memory
   for (i = 0; i < 1024; i++)
   {
      page_table[i] = (address | 3);
      address = address + 4096;
      //kprintf("Page Table Adress: %h\n",address);
   }
   kprintf(".");
   page_directory[0] = page_table;
   page_directory[0] = (page_directory[0] | 3);
   
   for (i = 0; i < 1024; i++)
   {
      page_directory[i] = (0 | 2); 
      //kprintf("Page Directory Adress: %h\n",page_directory[i]);

   }

   for (i = 0; i < 1024; i++)
   {
      kprintf("Page Directory Adress: %h Page Table: %h\n",page_directory[i], page_table[i]);
      
   }
   
   kprintf(".");
   setcr3(page_directory);
   mminit();
   kprintf(".");

   setcr0(getcr0() | 0x80000000);

   kprintf(".Completed\n");
   interrupt_on();
   
   kprintf("\n CR0:%h CR3:%h\n",getcr0(),getcr3());

}

[AR]

for (i = 0; i < 1024; i++)
{
page_directory = (0 | 2);
//kprintf("Page Directory Adress: %h\n",page_directory);

}

You've just deleted the entry you put in the page directory (you fill the entry then fill all the entries with zeros), also what is the point of having a writable non-present page? The CPU only checks Present, if present is off then the other bits aren't used and can be used for whatever you like.

[calpis]

To be honest, I don't know why. I think I made a mistake there.
I am following a tutorial from on implementing Basic Paging from here:http://www.osdever.net/tutorials/paging.php?the_id=43

I read alot about this and it still confuses me.

Thanks in advance.

[calpis]

Yeah, you are right. I made a mistake.

Thanks so much!

[calpis]

Can I also ask, why do we only map the first page table entries (the first 4MB)? But not for the other page tables? Is it because we only write new page table when we need it?

Also I want to clear this.
My first entry of page directory entry[0] is pointing to 9D023 where the location of my page table first entry is (0x9D000). So where should the page directory entry [1] pointing to? At the moment, it is point to 0x2? Should it be pointing to 0x9D001 upto 0x9E000(4Byte x1024 entries)?

I also notice that when I printf the page entries, I saw some entries like these

0x0063
0x1003
0x2023
0x3003
...so on

Why did I have a 0x2023? I only (or) it with 3.

Also does this function maps the first 4MB of phyiscal or virtual memory?

My kernel lives in 0x1000000 to 0x104000. Would the page table maps my kernel memory into the page table entries?

I am trying to write some sort of memory allocator so I can allocate pages to tasks.

Sorry about these long winded silly questions...its just that the more i read, the more I get confuse...

Please help~ Many thanks in advance.

[AR]

The first 4MB is identity mapped (mapped at the virtual address which matches where it is in the physical address space) because you only map what you actually use, it would be stupid to map the entire address space at startup because it won't be used anyway.

Entry 1 in the Page Directory points to another page table, the page table points to more pages, the second (PageDirectory[1]) entry is for 4MB-8MB, the one after is for 8MB-12MB and so on. Entries that are not present will trigger a page fault when accessed.

The memory starts at 0 and goes to 0xFFF which is 0x1000 bytes so 0x9D000 goes from 0x9D000 to 0x9DFFF the page after that one is 0x9E000-0x9EFFF and so on.

I don't recall what it is exactly but the 0x60/0x20 things are in the flags section, they're probably the accessed/dirty bits which the CPU sets when the page has been read or changed respectively.

Paging is only for virtual memory, whenever paging is on you are operating in the virtual address space declared by the page directory and tables.

I can't understand what you're asking about the kernel address.

[calpis]

Thanks to clear this up.

So that means my memory manager should map new page table when more memory is required right.

Ok, basically, I placed my paginginit first at main, then printing the identity map. At the end of the main, I printf the identity map again. Then I looked at all the pagetable entry and the is what I found.

This is my main kernel
main()
{
paginginit; print map;
GDT
LDT
video
.
.
.
timer
multiboot info
printf the map again.
end
}

These are the page table entries
-------------------------------------
entry[156] 0x9C023
entry[157] 0x9D023
entry[184] 0xB8063
entry[256] 0x100023
entry[257] 0x101023
entry[258] 0x102023
entry[259] 0x103063

entry[0] 0x63
entry[2] 0x2023
entry[156] 0x9C023
entry[157] 0x9D023
entry[184] 0xB8063
entry[256] 0x100023
entry[257] 0x101023
entry[258] 0x102023
entry[259] 0x103063

So the processor updates the map by itself at CR0 as you said, how fequent does it update it? If some page hasn't been accessed or dirty, does that mean it is a free page?

I now realised I asked a silly question about the kernel...sorry.

Free pages and freeing a used page using bitmaps and stack.

With the stack method I want to know if this is correct. I don't quite understand how it free a used page.

we setup a 2 new stacks right?
then check each pages table entries on the flags
if its a flag or some sort, we put it on the stack
else we move to the next page right
We continue it tell the end. So we have a free page pile

How do I free and collect those pages? Do I just indentify the pages which say a task was using and finished. And just set the flag bit to free or somthing?

Thanks in advances and thanks for you patience AR.

[AR]

It modifies the Page Directory and Page Tables, if neither accessed or dirty is set then it simply means the program/kernel has not used that page yet (which is useful later in user space for deciding which pages to remove from memory when you need more).

The page stack approach is quite straightforward, it's simply a list of free pages, if a page isn't on the stack then the page is "used". A used page is one that contains data and is being used by the kernel or a program, a free page is just a page that doesn't belong to anyone yet (isn't mapped in any of the page tables). Basically you'll just have two functions; void PushPage(physpageptr_t Page) and physpageptr_t PopPage() for managing the stack. Push writes the parameter at the end of the list and increments the pointer, Pop just takes the last item off the stack and decrements the pointer. To use it, when a program or the kernel frees a page just unmap and Push it, when a program or the kernel needs a page just Pop and map it.

The Page Stack is fast[O(1)] and simple and also doesn't waste any memory (when all pages are used the list is empty so the pages that the list was stored in can be reused for programs) but the disadvantage is that there is no way to check whether a page is used or not in an efficient manner (you'd need to search the whole list giving you an O(n) search time), the other is that there is no way to "see" contiguous pages so for DMA you can only guarantee 1 page. The second problem could be overcome by reserving a chunk of contiguous space for DMA at startup (say 128-256KBs and provide a sort of scheduler to allow drivers to take turns).

Page Bitmaps are slower to search since it is O(n) to find a free page but you can relatively easily see relationships between pages (free contiguous pages would be marked free and be next to each other in the bitmap), in the bitmap approach you would have GetPage, FreePage and QueryPage functions as well as the variation for finding a contiguous range.

Another approach is the page description struct which is basically a big array of structs describing each page in the memory, each struct generally will include a pointer to the page it represents, a set of custom flags for whatever you want to keep track of and a pointer to the process/thread that owns it.

The last "in the box" approach is a hybrid of the stack and bitmap approaches, you have a page stack that stores say about 10-50 entries and a bitmap behind that. When the stack becomes empty the code will search the bitmap for more free pages and refill the stack so most of the time you'll get a nice O(1) allocation speed but you can still find contiguous ranges, this overcomes both approaches weaknesses but the bitmap will still eat upto 131072 bytes if the user has 4GB of RAM.

An "outside the box" approach I've seen was using "memory maps" where basically you just have the BIOS memory map and use that for looking at the RAM, you then simply create a custom identifier for "Used" and just alter the memory maps as you use memory. This approach seems to be a rather good idea as it's both fast and simple (The algorithm would be O(n) but n would always be small, if the allocator is smart enough to allocate contiguously that is), it's also easy to see contiguous blocks for DMA.

[Kim]

Iam using that "outside the box" approach you said for my init code that enables paging and stuff like that.

mmap^.base_addr_low += PAGE_SIZE;
mmap^.length_low -= PAGE_SIZE;
igetpage := Pointer(mmap^.base_addr_low);

Simple, works but you can't free pages, isn't a prob for init code because everything you allocated will be used anyway.

[AR]

You can free via insertion after a quick check to find if an existing free entry is top or bottom bordered with the page (In which case you would just modify the Base and/or Length accordingly). To speed up freeing you could throw in a page stack so that the map is only referred to when the stack overflows with free pages or the free pages run out.

Fragmentation of memory is the worst enemy with this though, if every second page is free then you'll end up with a massive map that will be slow to search, of course the allocator should attempt to fill in the gaps to create larger combined regions in the map which would still be fast (you wouldn't go far to find a free entry) until you add other constraints like page colors and whatever else.

This also brings the physical fragmentation of the array itself to light, this can be dealt with by zeroing unneeded entries and recycling them instead of creating a new one, then physically reorganising the array when the CPU is otherwise idle.

[Freanan]

My Kernel crashes as well when i try to start paging.
I am using effectually the same code as the tutorial mentioned above, the only differences are that i packed the code for setting up page-dir-entries and page-table-entries in seperate functions, and that my pagedir and pagetabe are already set up as arrays of unsigned long with 1024 entries each so instead of using the adresses from the tutorial i am using the adresses of my arrays.

I also wrote a seperate function in assembler to actually start paging after setting up the tables:

Code: Select all

global start_paging
start_paging:
    pop eax
    mov cr3,eax
    mov eax,cr0
    or eax,0x80000000
    mov cr0,eax
    return

My asm code might be wrong, or maybe the idea with the arrays was not that good?
But as someobody has had the same problem without changing the code, maybe something else is the problem...
How did you fix your bogus pointer problem, Mr. L - mabye it is my problem too?
If you think the problem is in my code i can of course also post my c-code here..
Thanks in advance!

[JoeKayzA]

Hi!

Do you call this procedure (start_paging) from C-Code, as a function? This would mean, you actually pop the return address off the stack, write it to cr3 and enable paging. So the processor tries to interpret some of your code as its page directory (which doesn't work) and when it continues execution, the code won't be present any more (from now on, a crash is guaranteed).

My suggestion: Replace 'pop eax' with 'mov [esp + 4], eax'
This will place the address you have passed as the first argument in eax. I hope I didn't get confused with intel syntax, normally I write all my assembly (which is quite little) for gas! ;D

BTW, using arrays of unsigned long should work well, if you want to make sure, check sizeof(unsigned long), it should be 4.

Hope I could help!
cheers Joe