OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Jul 24, 2021 12:14 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: How to implement MM?
PostPosted: Thu Jun 10, 2021 11:11 pm 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
I have been stuck at memory management for many months now and I just can't do anything. After about 2-3 month I am at a point where I probably can map physical memory into virtual, but the mapping function is so extremely buggy that almost anything constantly causes page faults which cause double fault that I have to debug for days. I successfully mapped the kernel and reloaded page tables, but when it comes to doing things after I reloaded page tables, I just can't do anything. The algorithm for mapping page tables after there is no more identity mapping is that I have two lists in the kernel that are 4096bytes in size and I map the first area to a page table containing the entry for the second one and so by changing an entry in first area I map the second one. By now I I have a problem where mapping function started to fail after I made it clear page tables with zeroes if they were created by it and didn't exist before, cleaning causes the failure of physical memory allocation function in some strange way. I just don't know what to do next, I don't think it is normal to be stuck at memory manager(a hyper-simple one) for 2-3 or maybe even 4 month. Are there any other algorithms to map page tables that are simpler or better? Is there any way I could make my VMM even simpler, what could even the bug be about?

repo - https://github.com/NGX123/tos/
vmm(i haven't committed changes to the repo so it is a bit different from the one in the repo) - https://pastebin.com/RcQL7nbc

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Fri Jun 11, 2021 1:01 am 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,

Assuming I understood correctly, I believe the question is about how to update paging structures when Identity Space is removed. Don't worry about working on this for few months, am sure its pretty common -- memory management is arguably one of the most complex parts to get working.

If using 32 bit protected mode... We use recursive paging structures for this. The basic idea is that, during initialization, map a page directory entry to itself (we use the last entry.) What this does is effectively reserve the last 4MB of the virtual address space (assuming the last PDE is recursively mapped) for the current process page tables. This 4MB region will have all the paging structures (i.e. from our kernel):
Code:
MM_PAGE_DIRECTORY_BASE 0xfffff000
MM_PAGE_DIRECTORY_END 0xffffffff
MM_PAGE_TABLE_BASE 0xffc00000
MM_PAGE_TABLE_END 0xffffffff
MM_KERNEL_PAGE_TABLE_BASE 0xfff00000
MM_KERNEL_PAGE_TABLE_END 0xfff00fff
Creating a new page table then just involves getting a new page frame number from the physical memory allocator and setting the PDE from PAGE_DIRECTORY_BASE. This will map a page table within PAGE_TABLE_BASE that you can use to complete the mapping. A downside of this technique is that you lose 4MB of the address space. Another downside is that -- in my opinion -- this technique is very hard to explain and it is recommended to write it down carefully on paper and try to walk through it.

If using 64 bit long mode... the most common recommendation is to just keep Identity Space but mapped into Kernel Space. That way you have access to all of physical memory.

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Fri Jun 11, 2021 1:07 am 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,

Assuming I understood correctly, I believe the question is about how to update paging structures when Identity Space is removed. Don't worry about working on this for few months, am sure its pretty common -- memory management is arguably one of the most complex parts to get working.

If using 32 bit protected mode... We use recursive paging structures for this. The basic idea is that, during initialization, map a page directory entry to itself (we use the last entry.) What this does is effectively reserve the last 4MB of the virtual address space (assuming the last PDE is recursively mapped) for the current process page tables. This 4MB region will have all the paging structures (i.e. from our kernel):
Code:
MM_PAGE_DIRECTORY_BASE 0xfffff000
MM_PAGE_DIRECTORY_END 0xffffffff
MM_PAGE_TABLE_BASE 0xffc00000
MM_PAGE_TABLE_END 0xffffffff
MM_KERNEL_PAGE_TABLE_BASE 0xfff00000
MM_KERNEL_PAGE_TABLE_END 0xfff00fff
Creating a new page table then just involves getting a new page frame number from the physical memory allocator and setting the PDE from PAGE_DIRECTORY_BASE. This will map a page table within PAGE_TABLE_BASE that you can use to complete the mapping. A downside of this technique is that you lose 4MB of the address space. Another downside is that -- in my opinion -- this technique is very hard to explain and it is recommended to write it down carefully on paper and try to walk through it.

If using 64 bit long mode... the most common recommendation is to just keep Identity Space but mapped into Kernel Space. That way you have access to all of physical memory.


Thanks for answering

Is the recursive paging badly suited for 64 bit mode, becuase I would like to use one algorithm for both modes as I later could port the os to a 32-bit CPU? And also I don't really understand the recursive paging.

Identity mapping everything would waste RAM and isn't portable why would I use it for 64-bit mode?

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Fri Jun 11, 2021 1:16 am 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,

Technically recursive paging works in any mode. It is typically recommended to map Identity Space in Kernel Space for 64 bit long mode because...well...you can so might as well. Recursive paging is typically used in 32 bit protected mode due to the limited 4GB address space: you lose 4MB of the address space but it greatly simplifies paging code in the process.

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Fri Jun 11, 2021 5:51 am 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,

Technically recursive paging works in any mode. It is typically recommended to map Identity Space in Kernel Space for 64 bit long mode because...well...you can so might as well. Recursive paging is typically used in 32 bit protected mode due to the limited 4GB address space: you lose 4MB of the address space but it greatly simplifies paging code in the process.


Ok, I undersood

But I really can't understand how the recursive paging works, so here is my understanding of it - the level 4 page table has the last entry pointing to itself, but how does that work if it doesn't map and just points to itself and so just opens a path to level 3 page table which should in turn get to 2 and how is it possible?

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Fri Jun 11, 2021 8:49 am 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,

I am only going to address it in the context of 32 bit protected mode. The process is the same in 64 bit long mode, its just adds additional layers. We also noted earlier that it is very hard to explain and describe through text; we believe it is best to manually walk through it and visualize what is happening. First you must realize how the paging structures map to the virtual address space: a page (i.e. PTE) represents a 4K region of the address space, a page table (PDE) refers to a 4MB region of the address space. The first page table (PDE) is the first 4MB, next page table PDE[1] is the 2nd 4MB, PDE[2] is 3rd 4MB all the way to PDE[1023] for the last 4MB region. Lets walk through it: PDE[1023]=Page Directory (top most layer in 32 bit) is the recursive mapping. So if we try to write to address 0xfffff000 the CPU will lookup PDE[1023] and look at the Page Directory as a Page Table. Since the recursive mapping is setup still, PTE[1023] is still mapped to the page frame of the Page Directory itself. So when accessing 0xfffff000 you would be accessing the Page Directory. But you would also be accessing PTE[1023]. This has the side effect of PTE[0] being at 0xffc00000. Noting each page table is 1024*4 bytes in size, our kernel page table is PDE[768] which maps to 0xffc00000+(768*(1024*4)) = 0xfff00000.

During initialization, we set up recursive paging like this:
Code:
PageDirectoryEntry [0].u.device.valid = 1;
PageDirectoryEntry [0].u.device.pageFrameNumber = IdentitySpacePageTable;

PageDirectoryEntry [KernelPageTableIndex].u.device.valid = 1;
PageDirectoryEntry [KernelPageTableIndex].u.device.pageFrameNumber = KernelPageTable;

PageDirectoryEntry [1023].u.device.valid = 1;
PageDirectoryEntry [1023].u.device.pageFrameNumber = KernelPageDirectory;
When Identity Space is removed, it leaves the kernel page tables and the recursive mapping.

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 4:29 am 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,

I am only going to address it in the context of 32 bit protected mode. The process is the same in 64 bit long mode, its just adds additional layers. We also noted earlier that it is very hard to explain and describe through text; we believe it is best to manually walk through it and visualize what is happening. First you must realize how the paging structures map to the virtual address space: a page (i.e. PTE) represents a 4K region of the address space, a page table (PDE) refers to a 4MB region of the address space. The first page table (PDE) is the first 4MB, next page table PDE[1] is the 2nd 4MB, PDE[2] is 3rd 4MB all the way to PDE[1023] for the last 4MB region. Lets walk through it: PDE[1023]=Page Directory (top most layer in 32 bit) is the recursive mapping. So if we try to write to address 0xfffff000 the CPU will lookup PDE[1023] and look at the Page Directory as a Page Table. Since the recursive mapping is setup still, PTE[1023] is still mapped to the page frame of the Page Directory itself. So when accessing 0xfffff000 you would be accessing the Page Directory. But you would also be accessing PTE[1023]. This has the side effect of PTE[0] being at 0xffc00000. Noting each page table is 1024*4 bytes in size, our kernel page table is PDE[768] which maps to 0xffc00000+(768*(1024*4)) = 0xfff00000.

During initialization, we set up recursive paging like this:
Code:
PageDirectoryEntry [0].u.device.valid = 1;
PageDirectoryEntry [0].u.device.pageFrameNumber = IdentitySpacePageTable;

PageDirectoryEntry [KernelPageTableIndex].u.device.valid = 1;
PageDirectoryEntry [KernelPageTableIndex].u.device.pageFrameNumber = KernelPageTable;

PageDirectoryEntry [1023].u.device.valid = 1;
PageDirectoryEntry [1023].u.device.pageFrameNumber = KernelPageDirectory;
When Identity Space is removed, it leaves the kernel page tables and the recursive mapping.


So I pretty much understand the algorithm, the CPU cycles through the same table and in the end maps it, thinking it is a page, but I have a few questions:

- I didn't really understand the setup of recursive paging, is the only thing I need to do is make the last entry of PD point to PD(the start of it)?

- How do I access tables other then PD(e.g. PT or others in 4 level paging)?

- And also I haven't really understood the last 2 sentences - "So when accessing 0xfffff000 you would be accessing the Page Directory. But you would also be accessing PTE[1023]. This has the side effect of PTE[0] being at 0xffc00000. Noting each page table is 1024*4 bytes in size, our kernel page table is PDE[768] which maps to 0xffc00000+(768*(1024*4)) = 0xfff00000."

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 11:22 am 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,
Quote:
- I didn't really understand the setup of recursive paging, is the only thing I need to do is make the last entry of PD point to PD(the start of it)?
Technically it can be any entry. Most implementations (like Linux 32 bit) uses the last entry. Some implementations use a different index - like Windows (32 bit) uses the 768'th entry. But yes, that PDE[1023]=Page Directory is literally it.
Quote:
- How do I access tables other then PD(e.g. PT or others in 4 level paging)?
This is where it gets hard to explain due to the recursive definition. Basically, when you map the last page directory entry, any address in the last 4MB region of the address space become effected. What happens is that, during the address translation process, we will go through PDE[1023] to find the page table -- so it will next read the page directory again but this time treating it as a page table. So all page frame numbers in each page table entry refer to the page containing the contents of that respective page table -- keep in mind this is just the page directory being looked at as a page table hence the contents is the same. So to find the page table virtual addresses, we just need to know what page each page table / page directory entry maps to. You have already found one of them: the page directory itself is the last page table -- 1023.
Code:
0xfffff000 is PDE[1023] which is the last page table
0xffffe000 is PDE[1022] which is second to last page table.
0xffffd000 is PDE[1021]
...
0xfff00000 is PDE[768] this is typically the kernel page table for higher half kernels at 3GB
...
0xffc00000 is PDE[0]
So, lets say you need to update the kernel page table. Its respective page directory entry is the 768'th index from 0xfffff000 (MM_PAGE_DIRECTORY_BASE). If you need to update the page table itself, it will always and forever be at 0xfff00000 (MM_KERNEL_PAGE_TABLE_BASE).

Keep in mind all of this assumes you selected the PDE[1023] as the recursive index.

--
I will reiterate that there is no advantage to using recursive paging in 64 bit long mode. You don't lose anything by mapping all of physical memory into kernel space. If you did that, then you can easily determine the actual address and update paging structures. You wouldn't lose memory: in fact, doing this doesn't effect require additional memory at all. Recursive paging was used a lot in 32 bit protected mode as the size of the address space is the same as what was expected of physical memory at the time, so there was few good options available. Using multiple techniques to memory management is important to any good manager: you need to adjust the method depending on the environment to decide how best to manage memory. Even if the intent is trying to make things easier you will end up making it harder by not doing so.

--
As Recursive Paging comes up often, I started writing a small tutorial on it here. It is still a work in progress, but please feel free to point out any potential confusing parts and I will be happy to expand on them as needed.

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 11:54 am 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,
Quote:
- I didn't really understand the setup of recursive paging, is the only thing I need to do is make the last entry of PD point to PD(the start of it)?
Technically it can be any entry. Most implementations (like Linux 32 bit) uses the last entry. Some implementations use a different index - like Windows (32 bit) uses the 768'th entry. But yes, that PDE[1023]=Page Directory is literally it.
Quote:
- How do I access tables other then PD(e.g. PT or others in 4 level paging)?
This is where it gets hard to explain due to the recursive definition. Basically, when you map the last page directory entry, any address in the last 4MB region of the address space become effected. What happens is that, during the address translation process, we will go through PDE[1023] to find the page table -- so it will next read the page directory again but this time treating it as a page table. So all page frame numbers in each page table entry refer to the page containing the contents of that respective page table -- keep in mind this is just the page directory being looked at as a page table hence the contents is the same. So to find the page table virtual addresses, we just need to know what page each page table / page directory entry maps to. You have already found one of them: the page directory itself is the last page table -- 1023.
Code:
0xfffff000 is PDE[1023] which is the last page table
0xffffe000 is PDE[1022] which is second to last page table.
0xffffd000 is PDE[1021]
...
0xfff00000 is PDE[768] this is typically the kernel page table for higher half kernels at 3GB
...
0xffc00000 is PDE[0]
So, lets say you need to update the kernel page table. Its respective page directory entry is the 768'th index from 0xfffff000 (MM_PAGE_DIRECTORY_BASE). If you need to update the page table itself, it will always and forever be at 0xfff00000 (MM_KERNEL_PAGE_TABLE_BASE).

Keep in mind all of this assumes you selected the PDE[1023] as the recursive index.

--
I will reiterate that there is no advantage to using recursive paging in 64 bit long mode. You don't lose anything by mapping all of physical memory into kernel space. If you did that, then you can easily determine the actual address and update paging structures. You wouldn't lose memory: in fact, doing this doesn't effect require additional memory at all. Recursive paging was used a lot in 32 bit protected mode as the size of the address space is the same as what was expected of physical memory at the time, so there was few good options available. Using multiple techniques to memory management is important to any good manager: you need to adjust the method depending on the environment to decide how best to manage memory. Even if the intent is trying to make things easier you will end up making it harder by not doing so.

--
As Recursive Paging comes up often, I started writing a small tutorial on it here. It is still a work in progress, but please feel free to point out any potential confusing parts and I will be happy to expand on them as needed.


I can't really understand, the only thing I can think of is that we have an address like 0xffff<index of PT>000, so it interprets PD as PD, then PD as PT and finally it would map the PT at selected offset because it would interpret it as a page

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 12:04 pm 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,
Quote:
the only thing I can think of is that we have an address like 0xffff<index of PT>000, so it interprets PD as PD, then PD as PT and finally it would map the PT at selected offset because it would interpret it as a page
Basically, yes.

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 1:06 pm 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,
Quote:
the only thing I can think of is that we have an address like 0xffff<index of PT>000, so it interprets PD as PD, then PD as PT and finally it would map the PT at selected offset because it would interpret it as a page
Basically, yes.


Ok thanks, so here is my overview of understanding, please say if something is incorrect

Setup:
Have n-th(e.g. ff) offset of the highest level page table mapped to the start of highest level page table(e.g. PML4) - L4[ff] = L4; // setup

Usage:
Map L4 page table - So if you mapped the last page offset of highest page table to it's start then it is 0xff. And so to access L4 we just access 0xff'ff'ff'ff'ff'000, and that is because CPU interprets it as:
L3 = L4[FF];
L2 = L3[FF]; // because of previous step L3[FF] == L4[FF] and because L4[FF] == L4
L1 = L2[FF]; // because of previous step L2[FF] == L3[FF] and L3[FF] = L4[FF] because of the step before while L4[FF] == L4
Page = L1[FF] // and L1[FF] == L4[FF] and l4[FF] equals to the start of L4 and so L4 table is mapped like a page

And so we could just access page at 0xff'ff'ff'ff'ff'000 and that would be accessing L4 table where we could change address and flags in entry at any offset
To access chosen L3 page table in the L4 page table we should replace last "ff" with the offset of the needed L3 page table and then it would map it as a page

But that works for 32bit mode as mapping page table(level 1) gives us ability to change any mapping of page as it has the entries for pages, but in 64bit mode mapping level 3 table gives us ability to change level 2 page tables, so how should it work?

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Sat Jun 12, 2021 2:53 pm 
Offline
Member
Member
User avatar

Joined: Sun Feb 18, 2007 7:28 pm
Posts: 1517
Hi,

As I am working out a tutorial at the moment in order to give a more immediate answer I opted to go ahead and refer to this section of the Wiki here as it already documents all of the addresses assuming that you recursively map the last entry of the tables.

--
Perhaps a way to visualize what happens is to imagine overlaying the paging structures on top of each other such that they all share the page that is recursively mapped. For example, in 32 bit non-PAE mode:
Code:
              PD       PT
0xFFFFFFFF    +----+  +----+
              |    |  |    |
0xFFFFF000    +----+  |    |
                      |    |
0xFFC00000            +----+
The last entry of PT is recursively mapped. Likewise in 64 bit:
Code:
                     PML4    PDP        PD       PT
0xFFFFFFFFFFFFFFFF  +----+  +----+    +----+    +----+
                    |    |  |    |    |    |    |    |
0xFFFFFFFFFFFFF000  +----+  |    |    |    |    |    |
                            |    |    |    |    |    |
0xFFFFFFFFFFE00000          +----+    |    |    |    |
                                      |    |    |    |
0xFFFFFFFFC0000000                    +----+    |    |
                                                |    |
0xFFFFFF8000000000                              +----+

_________________
OS Development Series | Project Neptune | Repository | Wiki
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}


Top
 Profile  
 
 Post subject: Re: How to implement MM?
PostPosted: Mon Jun 14, 2021 10:07 am 
Offline
Member
Member

Joined: Sat Feb 20, 2021 3:11 pm
Posts: 94
neon wrote:
Hi,

As I am working out a tutorial at the moment in order to give a more immediate answer I opted to go ahead and refer to this section of the Wiki here as it already documents all of the addresses assuming that you recursively map the last entry of the tables.

--
Perhaps a way to visualize what happens is to imagine overlaying the paging structures on top of each other such that they all share the page that is recursively mapped. For example, in 32 bit non-PAE mode:
Code:
              PD       PT
0xFFFFFFFF    +----+  +----+
              |    |  |    |
0xFFFFF000    +----+  |    |
                      |    |
0xFFC00000            +----+
The last entry of PT is recursively mapped. Likewise in 64 bit:
Code:
                     PML4    PDP        PD       PT
0xFFFFFFFFFFFFFFFF  +----+  +----+    +----+    +----+
                    |    |  |    |    |    |    |    |
0xFFFFFFFFFFFFF000  +----+  |    |    |    |    |    |
                            |    |    |    |    |    |
0xFFFFFFFFFFE00000          +----+    |    |    |    |
                                      |    |    |    |
0xFFFFFFFFC0000000                    +----+    |    |
                                                |    |
0xFFFFFF8000000000                              +----+


Thanks

_________________
https://github.com/NGX123/tos


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 12 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group