Fixed: Paging: 32 Bits inside 20 Bits + Faults

[Octacone]

Hello everybody.

Currently I am trying to identity map my kernel and I ran into a problem. How do I fit 32 bits inside 20 bits? I don't understand how is that possible, since a page frame is only 20 bits wide. I am not using any tutorials or anything similar, trying to do this on my own. I have a page directory structure that points to 1024 page tables that have 1024 pages themselves. My "page" structure is the same as described in Intel Manuals.

Relevant code:

Code: Select all

//current_address -> range from 0 to 0x10E000
page_directory->page_tables[current_address / 1024]->pages[current_address % 1024].frame_address = current_address;

I was getting triple faults all over the place, and I decided to check the mappings... This is what I got:

Code: Select all

(frame_address, current_address) -> they should be equals since: .frame_address = current_address
0x0 0x0
0x1000 0x1000
0x2000 0x2000
0x3000 0x3000
0x4000 0x4000
0x5000 0x5000
...snip...
0xE000 0xE000
0xF000 0xF000
0x0 0x10000
0x11000 0x11000
0x12000 0x12000

I have no idea how to fix this. Any help would be appreciated. (dividing anything by 0x1000 or 1024 does not make any sense either)

[goku420]

You need to use bitshift to get the proper offset. To get a page table offset, you need to shift right by 22. To get a page offset, you need to shift right by 12. i.e,

Code: Select all

(vaddr >> PAGE_OFFSET) % 1024
(0x10000 >> 12) % 1024 == 16

This picture is taken straight from the manual:



Count the bits.

[no92]

Pages are 4 KiB aligned, i.e. the last 12 bits are zeroed. The page tables use (some of) the 12 bits to set various flags. Your pages are not present nor writable. Try setting the proper flags and searching the wiki. If the page is present, the virtual address is never equal to what you will find in the page table entry.

Also, you need to shift the virtual address by 22/12 bits to get the page directory/table index. (Hint: this numbers the pages in the table 0 through 1023)

EDIT: fix shift values

[Octacone]

You need to use bitshift to get the proper offset. To get a page table offset, you need to shift right by 22. To get a page offset, you need to shift right by 12. i.e,

Code: Select all

(vaddr >> PAGE_OFFSET) % 1024
(0x10000 >> 12) % 1024 == 16

This picture is taken straight from the manual:



Count the bits.

Thanks for the hint. I tried various bitshifts and none of them helped, but I was never actually dividing the output by 1024.

[sleephacker]

Each page table has 1024 entries describing one page of 4096 bytes each, so one page table accounts for 1024 * 4096 bytes, which is then also what you need to divide the address by to get the index in the page directory of the page table that describes that address. Each page is 4096 bytes, so to get the index of the entry within the page table you take the offset of the address within the address range corresponding to that page table and divide that by 4096. In other words:

Code: Select all

index_in_page_dir = address / (4096 * 1024);
offset_in_page_table_range = address % (4096 * 1024);
index_in_page_table = offset_in_page_table_range / 4096;
page_table = page_directory[index_in_page_dir]
page_entry = page_table[index_in_page_table]

[Octacone]

Pages are 4 KiB aligned, i.e. the last 12 bits are zeroed. The page tables use (some of) the 12 bits to set various flags. Your pages are not present nor writable. Try setting the proper flags and searching the wiki. If the page is present, the virtual address is never equal to what you will find in the page table entry.

Also, you need to shift the virtual address by 22/12 bits to get the page directory/table index. (Hint: this numbers the pages in the table 0 through 1023)

EDIT: fix shift values

Oh, don't worry I know about the flags. I am actually using them but did not show it in here. I will fix everything as suggested.

[Octacone]

Each page table has 1024 entries describing one page of 4096 bytes each, so one page table accounts for 1024 * 4096 bytes, which is then also what you need to divide the address by to get the index in the page directory of the page table that describes that address. Each page is 4096 bytes, so to get the index of the entry within the page table you take the offset of the address within the address range corresponding to that page table and divide that by 4096. In other words:

Code: Select all

index_in_page_dir = address / (4096 * 1024);
offset_in_page_table_range = address % (4096 * 1024);
index_in_page_table = offset_in_page_table_range / 4096;
page_table = page_directory[index_in_page_dir]
page_entry = page_table[index_in_page_table]

Ohhhh I get this. Thank you guys for helping. Now that I know how to access a specific virtual address, how do I map it? How to make 20 bit address equal a 32 bit one?

[goku420]

Each page table has 1024 entries describing one page of 4096 bytes each, so one page table accounts for 1024 * 4096 bytes, which is then also what you need to divide the address by to get the index in the page directory of the page table that describes that address. Each page is 4096 bytes, so to get the index of the entry within the page table you take the offset of the address within the address range corresponding to that page table and divide that by 4096. In other words:

Code: Select all

index_in_page_dir = address / (4096 * 1024);
offset_in_page_table_range = address % (4096 * 1024);
index_in_page_table = offset_in_page_table_range / 4096;
page_table = page_directory[index_in_page_dir]
page_entry = page_table[index_in_page_table]

This is a good explanation, but the code is hard to read. I prefer this:

Code: Select all

Get page table: page_directory[vaddr >> 22]
Get page: page_table[(vaddr >> 12) % 1024]

Some people prefer "& 0x3FF" instead of "% 1024".

The other thing to mention is that you should check if the page table already exists before overwriting it or you will have a bad time.

[Octacone]

Each page table has 1024 entries describing one page of 4096 bytes each, so one page table accounts for 1024 * 4096 bytes, which is then also what you need to divide the address by to get the index in the page directory of the page table that describes that address. Each page is 4096 bytes, so to get the index of the entry within the page table you take the offset of the address within the address range corresponding to that page table and divide that by 4096. In other words:

Code: Select all

index_in_page_dir = address / (4096 * 1024);
offset_in_page_table_range = address % (4096 * 1024);
index_in_page_table = offset_in_page_table_range / 4096;
page_table = page_directory[index_in_page_dir]
page_entry = page_table[index_in_page_table]

This is a good explanation, but the code is hard to read. I prefer this:

Code: Select all

Get page table: page_directory[vaddr >> 22]
Get page: page_table[(vaddr >> 12) % 1024]

Some people prefer "& 0x3FF" instead of "% 1024".

The other thing to mention is that you should check if the page table already exists before overwriting it or you will have a bad time.

This is getting more and more understandable, now I know what 0x3FF is for.

[BrightLight]

Ohhhh I get this. Thank you guys for helping. Now that I know how to access a specific virtual address, how do I map it? How to make 20 bit address equal a 32 bit one?

If you mean the 20 bits in the page table entry, they are simply same 32 bits of the 4 KB-aligned physical address, and thus the lowest 12 bits are zero, and thus only the high 20 bits are used. Since the lowest 12 bits are unused, the x86 processor uses them for the page flags. In fact, the reason the pages must be page-aligned is because only 20 bits are used.
For example, to map the physical memory at 0x1000, with read/write permissions, the page table entry for this page will contain 0x00001003. Notice how the lowest 12 bits are used for flags, while the unused bits are zero, and the actual page address is 20 bits in length. Bit 0 (value 1) here is the page present flag, while bit 1 (value 2) is the page writable flag.

To sum up and answer your question: to convert a 32-bit address to a 20-bit one you don't do anything, the 32-bit address just has to be 4 KB-aligned (i.e. bits 0 to 11 must be zero.) To convert a 20-bit address to a 32-bit one (i.e. getting the physical address from a page) you simply logical AND the value with 0xFFFFF000, which will clear everything except the 4 KB-aligned address; voila, you have the full 32-bit page-aligned address.

[Octacone]

Ohhhh I get this. Thank you guys for helping. Now that I know how to access a specific virtual address, how do I map it? How to make 20 bit address equal a 32 bit one?

If you mean the 20 bits in the page table entry, they are simply same 32 bits of the 4 KB-aligned physical address, and thus the lowest 12 bits are zero, and thus only the high 20 bits are used. Since the lowest 12 bits are unused, the x86 processor uses them for the page flags. In fact, the reason the pages must be page-aligned is because only 20 bits are used.
For example, to map the physical memory at 0x1000, with read/write permissions, the page table entry for this page will contain 0x00001003. Notice how the lowest 12 bits are used for flags, while the unused bits are zero, and the actual page address is 20 bits in length. Bit 0 (value 1) here is the page present flag, while bit 1 (value 2) is the page writable flag.

To sum up and answer your question: to convert a 32-bit address to a 20-bit one you don't do anything, the 32-bit address just has to be 4 KB-aligned (i.e. bits 0 to 11 must be zero.) To convert a 20-bit address to a 32-bit one (i.e. getting the physical address from a page) you simply logical AND the value with 0xFFFFF000, which will clear everything except the 4 KB-aligned address; voila, you have the full 32-bit page-aligned address.

Big big thanks to you. I have no more questions left to ask.
Seems like this was actually quite a simple solution. (that seems hard if you don't understand it deeply enough) I can't quite code right now, but tomorrow I will apply all these suggestions and hopefully have paging enabled.

[Octacone]

What a disappointment...

I did everything as you guys suggested, and it still doesn't work.

Here is my paging structure:

Updated code (setting flags code not shown, page present and write_enabled and not user page)

Code: Select all

page_directory->page_tables[(current_address >> 22)].pages[(current_address >> 12) % 1024].frame_address = current_address;

Bochs reports:

Code: Select all

(0).[971843393] ??? (physical address not available)
(0).[971843394] ??? (physical address not available)
bx_dbg_read_linear: physical address not available for linear 0x0000000000100a3f

Also "page 0x0" command shows:

Code: Select all

linear page 0x0000000000000000 maps to physical page 0x00000000f000f000

This is not supposed to be mapped to that address. Since I am ID mapping everything from 0x0 to 0x10F000.

[BrightLight]

Here is my paging structure:

paging_structure.png

What is this? The page directory doesn't contain 1024 page tables; it contains 1024 pointers to page tables. I don't have much time right now, but I'll review the other stuff later.

[Octacone]

Here is my paging structure:

paging_structure.png

What is this? The page directory doesn't contain 1024 page tables; it contains 1024 pointers to page tables. I don't have much time right now, but I'll review the other stuff later.

Okay so this changes nothing:

Code: Select all

page_table_t* page_tables[1024];

//I've had this in the first place but I removed it for some reason.

Edit: other possible/impossible causes:
page_directory_address = PMM.Allocate_Blocks(sizeof(page_directory_t) <-- this is 4096 which makes no sense since I want to allocate the entire page directory with all its table and pages);
all page tables + all pages should be equal to 4 MB overhead right? So do I need to allocate 4 MB blocks worth of memory?
then again this size is questionable String.Memory_Set(page_directory, 0, ->>> 4096 * 1024 * 1024 <--- since 1024 pg tables that contain 1024 entries 4096 KB each);

[BrightLight]

OK, try this then:

Code: Select all

page_directory->page_tables[(current_address >> 22)].pages[(current_address >> 12) & 0x3FF].frame_address = (current_address >> 12);

This takes only 20 bits to fit in your structure, which has a 20-bit field. Don't forget the present flag, and very important for your stack is the writable flag must be set!