Fixed: Paging: 32 Bits inside 20 Bits + Faults

[Octacone]

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!

Code: Select all

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

Again, nothing changes. Also I changed page_table_t page_tables[1024]; to page_table_t* page_tables[1024];
Present flag is in place. Every single bit of the kernel is identity mapped so there should not be any stack related issues.

Edit:
Fixed couple of things:
Now allocating 1024 * 1024 blocks (4096 KB each) of physical memory for the paging structures (entire everything)
Now memory set clears 1024 * 1024 * 4096 bytes of memory. (the entire structure)

Edit 2:
This is not correct either:

[BrightLight]

Show us how you create the page directory, page table and all the entries.

[Octacone]

Show us how you create the page directory, page table and all the entries.

Well I guess I'll have to reveal the code if I want to get any deeper help.
Here it is:

Code: Select all

uint32_t kernel_end_address = Memory_Core.Page_Align_Address(kernel_end);
page_directory_address = PMM.Allocate_Blocks(1024 * 1024);
page_directory = (page_directory_t*) page_directory_address;
String.Memory_Set(page_directory, 0, 4096 * 1024 * 1024);
uint32_t current_address = 0;
while(current_address < kernel_end_address)
{
	//& 0x3FF = % 1024
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].present = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].write_enabled = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].user_page = 0;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].frame_address = current_address;
	current_address += 0x1000;
};
Write_CR3(page_directory_address);
Set_Paging_Bit();

[BrightLight]

Code: Select all

uint32_t kernel_end_address = Memory_Core.Page_Align_Address(kernel_end);
page_directory_address = PMM.Allocate_Blocks(1024 * 1024);
page_directory = (page_directory_t*) page_directory_address;
String.Memory_Set(page_directory, 0, 4096 * 1024 * 1024);
uint32_t current_address = 0;
while(current_address < kernel_end_address)
{
	//& 0x3FF = % 1024
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].present = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].write_enabled = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].user_page = 0;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].frame_address = current_address;
	current_address += 0x1000;
};
Write_CR3(page_directory_address);
Set_Paging_Bit();

I don't see you allocating memory for the page tables. Do your PMM functions work like expected?

Code: Select all

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

This line should be:

Code: Select all

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

This would keep only the highest 20 bits as you're working with a 20-bit field. Try running it like this and tell us what happens.

[Octacone]

Code: Select all

uint32_t kernel_end_address = Memory_Core.Page_Align_Address(kernel_end);
page_directory_address = PMM.Allocate_Blocks(1024 * 1024);
page_directory = (page_directory_t*) page_directory_address;
String.Memory_Set(page_directory, 0, 4096 * 1024 * 1024);
uint32_t current_address = 0;
while(current_address < kernel_end_address)
{
	//& 0x3FF = % 1024
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].present = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].write_enabled = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].user_page = 0;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].frame_address = current_address;
	current_address += 0x1000;
};
Write_CR3(page_directory_address);
Set_Paging_Bit();

I don't see you allocating memory for the page tables. Do your PMM functions work like expected?

Code: Select all

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

This line should be:

Code: Select all

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

This would keep only the highest 20 bits as you're working with a 20-bit field. Try running it like this and tell us what happens.

It triple faults again. Same exceptions as before.
Yes I am allocating memory for everything:
page_directory_address = PMM.Allocate_Blocks(1024 * 1024);
1024 * 1024 => every existing page/table -> further explanation: it is actually 1024 * 1024 * 4096 since PMM allocates 4096 bytes of ram per block

[goku420]

In my opinion, you should scrap your design. It's clear that you have a misunderstanding of the paging structures as well as the layout of structures in C++.

If you have something like this:

Code: Select all

struct test {
    int a;
    int b;
} t;

Then &t == &t.a and &t.b == ((uintptr_t)(&t.a) + 4)

What this means is that your paging directory structure will soak up 4 megabytes of consecutive memory (likely overwriting all kinds of data). Do sizeof(page_directory_t) if you do not believe me.

Further, changing page_table to page_table* will not fix the problem. When the other poster was talking about pointers, what he meant was that the page directory contains entries that have the physical address of a page table. So what your code should do:

- Get the physical address of the page directory
- Get the index of the page table
- Check if the page table is already present; if it's not, allocate a physical page to hold the page table
- Assign that page table (with the present flag) to the page directory
- Get the index of the page table entry
- Assign the physical (not virtual address) that you're trying to map to the page table with the present flag

All of this implies that the page directory, paging table and paging entries could be in unrelated places in memory.

[Octacone]

In my opinion, you should scrap your design. It's clear that you have a misunderstanding of the paging structures as well as the layout of structures in C++.

If you have something like this:

Code: Select all

struct test {
    int a;
    int b;
} t;

Then &t == &t.a and &t.b == ((uintptr_t)(&t.a) + 4)

What this means is that your paging directory structure will soak up 4 megabytes of consecutive memory. Do sizeof(page_directory_t) if you do not believe me.

Further, changing page_table to page_table* will not fix the problem. When the other poster was talking about pointers, what he meant was that the page directory contains entries that have the physical address of a page table.

I already did sizeof(page_directory_t) and it returns 4096.
I know it will soak up 4 MB of RAM because I am actually allocating 4 MB for the entire thing. Do you genuinely think this is the problem, because I've seen similar implementations. So is my entire structure okay or not?

[goku420]

I already did sizeof(page_directory_t) and it returns 4096.
I know it will soak up 4 MB of RAM because I am actually allocating 4 MB for the entire thing. Do you genuinely think this is the problem, because I've seen similar implementations. So is my entire structure okay or not?

As stated above, a page table (not just a page table entry) needs to have the present/write bit set. Think about it for a second. How can a page directory hold both a page table as well as its offset (with the flags set)? If your page table is located at 0x1000, then page_directory[page_table_index] = 0x1003. This implies that the page table cannot overlap with the paging directory in memory (as all 1024 page frames that the page table holds will overwrite the rest of the page table entries).

[eryjus]

Here is my paging structure:

You are statically allocating your entire table structure at compile time, but since it is not initialized it will be in your .bss section. Are you certain your loader is zero-ing out this structure? I saw you are zeroing the Page Directory but I did not see the individual Page Table and likely could have missed it.

Also, your structures are not tagged as packed (in C this would be "__attribute__((packed))" and since I am not quite as good in C++, I leave it to you to find the correct decoration). This will not make a technical difference, but it does not hurt to get in this habit when you do not want the compiler to align your structure members when at a higher optimization.

Finally, and probably the most important point, your structure has about a 1 in 1000 chance of being page aligned by accident. I see nothing to ensure this alignment in your snapshot and it is required. To be particularly redundant, the last 3 nibbles of the address of the Page Directory must be 0x000.

Now, gong back to your original question and subject line.... You are not packing a 32-bit address into a 20-bit page selector -- I trust you understand that after a these few days. Breaking it down, you can look at the 32-bit address in the following manner: 10-10-12, where the first 10 bits is an index into the Page Directory table (be sure not to confuse this with a byte offset) which results in a Page Table and the second 10 bits is an index into the Page Table. The remaining 12 bits is a byte-offset into the resulting Page of Virtual Memory Offset which will map byte-to-byte to your Physical Memory Frame.

I tend to keep my frames as integer numbers (meaning 20 bits long) and my addresses full 32 bits. This will make life easier when you know that to convert any frame to and addressed you can use:

Code: Select all

addr = frame << 12;

and frames are never addresses and addresses are never frames.

So, it is no accident that the last 12 bits of a Page starting address must be 0x000, just like the last 3 nibbles of a frame must be 0x000. Similarly, it is no accident that a Page Table and a Page Directory must be page-aligned. Ultimately you are using 20 of the 32 bits to select a page and the remaining 12 bits to select a byte-offset therein.

Code: Select all

uint32_t kernel_end_address = Memory_Core.Page_Align_Address(kernel_end);
page_directory_address = PMM.Allocate_Blocks(1024 * 1024);
page_directory = (page_directory_t*) page_directory_address;
String.Memory_Set(page_directory, 0, 4096 * 1024 * 1024);
uint32_t current_address = 0;
while(current_address < kernel_end_address)
{
	//& 0x3FF = % 1024
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].present = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].write_enabled = 1;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].user_page = 0;
	page_directory->page_tables[(current_address >> 22)]->pages[(current_address >> 12) % 1024].frame_address = current_address;
	current_address += 0x1000;
};
Write_CR3(page_directory_address);
Set_Paging_Bit();

No. I want to map an address, let's say addr = 0x1023af65 to make the example more interesting. First of all, we map pages and not addresses, so immediately I would mask the address to a page address:

Code: Select all

addr &= (~0x00000fff)           //  my address is now 0x1023a000

Notice that this drops the last 12 bits of the address... I call this out as this is part of the 10-10-12 pattern I mentioned above. Also notice that we are left with 5 nibbles, or 20 bits... or the 10-10 part.
* the first 10 is 0b00 0100 0000 (or 64)
* the second 10 is 0b10 0011 1010 (or 314)

Now, it's just a matter of a pedantic walk through the paging tables:

Code: Select all

// -- Find the page table
pdEntry = &pd[addr >> 22];       // -- this is the first 10
// -- I did mention that pd must be page-aligned, right?

// -- TODO: check if we have a frame allocated for the Page Table (present?) and if not add a new one
ptFrame = pdEntry->frame;
ptAddr = (PageTable *)(ptFrame << 12);

// -- Find the Page Table Entry
ptEntry = &ptAddr[(addr >> 12) & 0x3ff];     // this is the second 10

// -- TODO: Is the frame present?  what should you do if it is?

// -- identity map the address;   TODO: set all the other relevant fields in the entry
ptEntry->frame = addr >> 12;

Notice the conversions between frames and addresses. Don't allow yourself to be confused between the address-to-frame conversion and the address-to-page-table-index conversion.

Now, I know you mentioned that you are doing this without any tutorials. My algorithm above is taken straight from this picture:
http://forum.osdev.org/viewtopic.php?f= ... 36#p276069

If you are still having trouble, maybe you can restate your problem.

[davidv1992]

From what i glanced from the code you showed here, the most major problem is actually deeper than stated by most here. You should really do a thorough read on how paging works in x86, a good source for this is the intel manuals (specifically chapter 4 of the 3rd volume if i remember correctly). Essentially, you seem to be completely misunderstanding just how the processor tries to read your page tables, and how it uses it.

[Octacone]

As stated above, a page table (not just a page table entry) needs to have the present/write bit set. Think about it for a second. How can a page directory hold both a page table as well as its offset (with the flags set)? If your page table is located at 0x1000, then page_directory[page_table_index] = 0x1003. This implies that the page table cannot overlap with the paging directory in memory (as all 1024 page frames that the page table holds will overwrite the rest of the page table entries).

You are statically allocating your entire table structure at compile time, but since it is not initialized it will be in your .bss section. Are you certain your loader is zero-ing out this structure? I saw you are zeroing the Page Directory but I did not see the individual Page Table and likely could have missed it.
Also, your structures are not tagged as packed (in C this would be "__attribute__((packed))" and since I am not quite as good in C++, I leave it to you to find the correct decoration). This will not make a technical difference, but it does not hurt to get in this habit when you do not want the compiler to align your structure members when at a higher optimization.
Finally, and probably the most important point, your structure has about a 1 in 1000 chance of being page aligned by accident. I see nothing to ensure this alignment in your snapshot and it is required. To be particularly redundant, the last 3 nibbles of the address of the Page Directory must be 0x000.
Now, gong back to your original question and subject line.... You are not packing a 32-bit address into a 20-bit page selector -- I trust you understand that after a these few days. Breaking it down, you can look at the 32-bit address in the following manner: 10-10-12, where the first 10 bits is an index into the Page Directory table (be sure not to confuse this with a byte offset) which results in a Page Table and the second 10 bits is an index into the Page Table. The remaining 12 bits is a byte-offset into the resulting Page of Virtual Memory Offset which will map byte-to-byte to your Physical Memory Frame.
I tend to keep my frames as integer numbers (meaning 20 bits long) and my addresses full 32 bits. This will make life easier when you know that to convert any frame to and addressed you can use:

Code: Select all

addr = frame << 12;

and frames are never addresses and addresses are never frames.
So, it is no accident that the last 12 bits of a Page starting address must be 0x000, just like the last 3 nibbles of a frame must be 0x000. Similarly, it is no accident that a Page Table and a Page Directory must be page-aligned. Ultimately you are using 20 of the 32 bits to select a page and the remaining 12 bits to select a byte-offset therein.
No. I want to map an address, let's say addr = 0x1023af65 to make the example more interesting. First of all, we map pages and not addresses, so immediately I would mask the address to a page address:

Code: Select all

addr &= (~0x00000fff)           //  my address is now 0x1023a000

Notice that this drops the last 12 bits of the address... I call this out as this is part of the 10-10-12 pattern I mentioned above. Also notice that we are left with 5 nibbles, or 20 bits... or the 10-10 part.
* the first 10 is 0b00 0100 0000 (or 64)
* the second 10 is 0b10 0011 1010 (or 314)
Now, it's just a matter of a pedantic walk through the paging tables:

Code: Select all

...pseudo code...

Notice the conversions between frames and addresses. Don't allow yourself to be confused between the address-to-frame conversion and the address-to-page-table-index conversion.
Now, I know you mentioned that you are doing this without any tutorials. My algorithm above is taken straight from this picture:
http://forum.osdev.org/viewtopic.php?f= ... 36#p276069
If you are still having trouble, maybe you can restate your problem.

From what i glanced from the code you showed here, the most major problem is actually deeper than stated by most here. You should really do a thorough read on how paging works in x86, a good source for this is the intel manuals (specifically chapter 4 of the 3rd volume if i remember correctly). Essentially, you seem to be completely misunderstanding just how the processor tries to read your page tables, and how it uses it.

Hey guys I have some updates. Past couple of days I've been carefully reading the Intel manuals. They really helped me a lot with some theoretical troubles I was having. Now I get everything about setting page table as present and so on. That image really helps, once you look at it for 20-200 times while thinking about it. I updated some code, does it now look as remotely as good?

Code: Select all

typedef struct page_t
{
	uint32_t present : 1;
	uint32_t write_enabled : 1;
	uint32_t user_page : 1;
	uint32_t write_through : 1;
	uint32_t cache_disabled : 1;
	uint32_t accessed : 1;
	uint32_t dirty : 1;
	uint32_t pat_supported : 1;
	uint32_t global : 1;
	uint32_t available : 3;
	uint32_t frame_address : 20;
}page_t;

typedef struct page_directory_entry_t
{
	uint32_t present : 1;
	uint32_t write_enabled : 1;
	uint32_t user_page_table : 1;
	uint32_t write_through : 1;
	uint32_t cache_disabled : 1;
	uint32_t accessed : 1;
	uint32_t ignored : 1;
	uint32_t page_size : 1;
	uint32_t global : 1;
	uint32_t available : 3;
	uint32_t page_table_address : 20;
}page_table_entry_t;

typedef struct page_table_t
{
	page_t pages[1024];
}page_table_t;

typedef struct page_directory_t
{
	page_directory_entry_t physical_page_tables[1024]; //Physical locations of those page tables, need to use PMM for this in order to allocate them and also I need to init some flags in here
	page_table_t* virtual_page_tables[1024]; //I need to use this in order to get the actual PMM frames and also for translation process
}page_directory_t;

They only thing that I don't understand is what does a page directory point to? I know it holds two different sets of page table info? But how does a CPU know what to do with a page directory? What is the CPU looking at inside that struct? Actually page_directory_entry_t is used to store page table addresses (physical ones, and their flags) now "virtual" page tables store virtual addresses and also page_t stores a page frame that the linear address is mapped to. Why is this so hard? Why did Intel have to make it so complicated?

[LtG]

It's not really hard or complicated, you just have to concentrate and read slowly until you get it. Read it many times, look at the diagrams and read it again, until you get it.

You have to understand that you are dealing with four distinct concepts, for both physical and virtual there is memory and address space, so:
- Physical address space
- Physical memory
- Virtual address space
- Virtual memory

All four are distinct, think about those four concepts and what they mean. If you don't understand them or understand why they are different things then it might be difficult to understand paging theory.

As for the x86 paging implementation it's really quite simple, but as said, takes some thinking and time to get used to. Let's make the normal/basic assumptions that we are looking things from a normal userland apps perspective. The app accesses some memory (virtual memory) that has been allocated to it (by malloc/new):
For every memory access the CPU must translate the address of said virtual memory to something it can do something about (physical memory) so it will do the following lookup (obviously in reality it caches these steps so it doesn't have to do everything every time):
- The CPU knows the virtual memory address that the app just attempted to access, in addition it knows the _physical_ address for page directory (PD) since it's in CR3.
- The CPU takes the top 10-bits of the virtual address for the virtual memory the app tried to use, that is used as an index to the PD (and the address of the PD, in CR3, is physical so the CPU can access it without translation)
- In that index of the PD is some entry, called PDE (Page Directory Entry)
- That PDE has some info, including Present bit, if it's not present then raise page fault, app did something it shouldn't have, let's assume it was present
- The PDE also has a _physical_ address for the PT (Page Table) that describes things further, let's go check that
- The next 10-bits of the virtual address we are currently translating describes and index in to the PT, that would be a PTE (Page Table Entry)
- That PTE has a Present bit (similar to PDE) and a physical address of which the top 20-bits are relevant, since the bottom 12-bits are used as flags (including the Present bit), that will become our final physical address's top 20-bits, the bottom 12-bits come from the initial virtual address that was attempted to be accessed.

So in all cases the bottom 12-bits of the virtual address go straight thru to the final physical address after translation, the top 20-bits come from the page table (from one specific PTE). Which PT to use comes from the PD (from one specific PTE in the PD).


The top 10-bits of the virtual address are used as an index to the PD (to pick a single PDE), that PDE specifies which PT to use, the next 10-bits of the virtual address are used as an index to the PT to pick a single PTE, and that PTE tells the CPU what the top 20-bits for physical address are. Of course at both levels (PD and PT) of translation the Present bit is checked and the accessed/dirty, etc, so all the flags are checked as specified.

The virtual address (top 20-bits) is used as indices to the PD and PT's, and the entries in the PD and PT's then specify some physical address, in the case of PD it specifies physical address for the relevant PT and in the case of PT it specifies the physical address for a specific page, and remember, the last 12-bits of the initial virtual address specifies the "index" in to that 4KiB physical page frame.

Sorry for the long post, tried to explain it from a couple of different angles in case it helps. It's useful to remember that abstract stuff is hard, indirection (which there's couple of levels here) is hard, which means you need to read the paging stuff with thought, slowly and probably multiple times.

Hopefully I didn't mix some of the terminology, problem with trying to write fast is that sometimes they get mixed up..

PS. there's the old joke on how to measure programmer "skill" and that's how many levels of indirection they're capable of understanding, IIRC the claimed average is somewhere in the 1-2 levels..

[goku420]

The above information seems correct but I think a practical example is in order. Let's say you are using the recursive paging directory trick. This means that one of your entries (typically the last) in the PD points to the PD itself.

What this means is that you can access the page directory at the virtual address: 0xfffff000 (1024ull * 1023ull * 4096ull + 4096 * 1023ull)

And the last page table at: 0xffc00000 (1024ull * 1023ull * 4096ull)

So in qemu if you run the commands info TLB and info mem you get information that looks like this:

Code: Select all

00000000ffc00000: 0000000000413000 ---DA---W
00000000fffff000: 00000000001a7000 ----A---W

Notice how you see a virtual address followed by a physical address. 0x001a7000 happens to be the physical address where I created my page directory (in my boot assembly). And 0x00413000 happened to be a free page allocated by my PMM.

If I do "x address" I should be able to further see the page table mappings:

Code: Select all

# The physical address of the page table; notice the present bits at the end
(qemu) x 0xfffff000
fffff000: 0x00413063

# The first entry of the page table; in this case I mapped the first 4 MiB to the linear frame buffer starting at address 0 for simplicity
(qemu) x 0xffc00000
ffc00000: 0xfd000063

Now you're probably wondering how a page table index relates to a virtual address. It's pretty simple. The code is:

Code: Select all

          uint32_t virtual_address = 0xFFC00000;

          virtual_address |= (page_table_index << PAGE_OFFSET);
  
          return virtual_address;

If for example page_table_index is 1023 and PAGE_OFFSET is 12, this should give you 0xfffff000. This shouldn't be surprising if you remember that we made the PDE point to itself.

I hope this helps you understand that what it means to map a virtual address to a physical address. All of the paging structures hold physical addresses and the indices/offsets themselves can be computed to get the virtual address.

[Octacone]

Thank you both guys for further explanation. I think I know what it going on!
So:
Page directory is fake, it doesn't even exist. It is just a creation of our imagination, an abstraction. What I really want to put inside CR3 is an address of all the physical page directory entries! Then each one of those page directory entries contain an address of its virtual representative we use for translating. I think that was the key part missing in this entire story. Now I just need a strategy for actually managing the virtual memory. What are the functions I need, standard ones perhaps? Something like allocate block/s free blocks/s but with ability to set the flags and a virtual address itself (the one we want). Okay let's put that aside. Now the real question is, are all the structures already pre-allocated since there is a finite number of entries (cause compiler knows what to reserve), that is the data section right? So that means I only need to allocate virtual page tables, right? This is so exciting I think I am slowly putting everything in perspective.

[FusT]

Page directory is fake, it doesn't even exist. It is just a creation of our imagination, an abstraction.

Basically, yes.
The PD is just an array containing all the PDEs and since the address of an array points to the first element in it you could say that the PD doesn't really exist.
The same goes for the PT: It's simply an array containing PTEs.