Paging - where to store the page tables

[mangaluve]

Im about to implement paging for my memory manager. Now I've read and understand the basics of paging, but there's one thing Im confused about. What if I need a new page table (for instance, I've allocated 4 mb and want more free pages). Now I assume I've already initialized my heap so I can allocate memory dynamically, and ask for more pages when I need. Where should I store this place table? I get a little confused, if the heap is full and I need more pages, where should I store the table? I could of course "pre-allocate" them before enabling paging, but that would waste some space. What are the alternatives?

[JohnnyTheDon]

Use your page frame allocator to allocate space for page tables. Page tables are the size of pages and they have to be page aligned, so you should just allocate them directly from physical memory. Using the heap would waste a lot of space and make the whole operation more complicated because you need to align the page tables on page boundaries.

[Ready4Dis]

As mentioned, these should be allocated from your physical page allocator. There isn't much to it really, grab the new page, and set it up however is required. There are a few methods, you set aside a specific location to access your PDE (and a default memory address to access your PTE's), this uses the least amount of virtual space. Another method is to map your PDE to virtual memory at some location (as well as your PTE's)

Example of the first method:

Code: Select all

#define Default_PDE_Location 0x1000   //Default location for accessing a PDE
#define Default_PTE_Location 0x2000  //Default location for accessing a PTE
unsigned long *Default_PDE = (unsigned long*)Default_PDE_Location;  //This is a pointer we can use to access our PDE
volatile unsigned long *Default_PTE = (unsigned long*)Default_PTE_Location;  //A pointer to access our PTE

unsigned long *New_PTE = AllocatePhysicalPage();
Default_PDE[PDE_Index] = New_PTE | 0x03; //Set it up as a supervisor page, read/write
Physical2Virtual(New_PTE, (void*)Default_PTE_Location); //Cast int to a void*
//We can now access our current PTE using Default_PTE[PTE_Index] as long as we invalidate the page, or reload CR3...

Explanation of self mapping our PDE...

Physical2Virtual(Physical_PDE, 0xFFC00000); //Map our physical address of CR3 to virtual address 0xFFC00000

Here is the part most people have a hard time wrapping their head around... since you mapped this to 0xFFC00000, it also acts as
a PTE, mapping 4mb worth of data, and itself . If you think about it, when we map a memory address, we are setting a PTE entry, so this 4mb
PTE entry, maps our PDE... which maps our PTE's . So, you can now access ALL PTE's and the PDE using this, however it does consume 4mb of virtual memory, and other tricks need to be implemented if you want to support things like PAE, etc. This trick also sucks in long mode, since there is a much larger area
of memory that could possibly be mapped.

I don't have any of my sources handy, but if you want more information, there is a good amount available, and when I can get some time, I could post a few of my functions that deal with this self mapping (it is quick, and you don't have to reload CR3 or invalidate a page each time you want to access a PTE, like the first example, especially useful when you just reading contents, possibly to convert a virtual address back into a physical one, or searching for pages to swap out, etc).

[mangaluve]

Thanks a lot, seems good to just take them from the page frame allocator. I didn't however really understand the last message, the difference between the two approaches. My main concern is, where should I put the new page table in my virtual memory? Should I reserve 4 MB of virtual memory where I place all my Page Tables? Which way is the most efficients (in terms of wasted virtual memory)

[JohnnyTheDon]

The easiest and most effective way is to, as ready said, insert the PDE into itself. That lets you access all the page tables and the pde in a 4MB region of memory. You will probably want to insert it at the end so it is in the higher half (kernel area). With this method, you can access page tables linearly (ie the 5000th page table entry is 5000 page table entries from the start of where you mapped the PDE into itself) and it doesn't require any extra page tables.

[mangaluve]

I didn't really understand that approach with inserting the PDE into itself. Didnt he write that it sucked too? I got a little confused

[Brendan]

Hi,

I didn't really understand that approach with inserting the PDE into itself.

It's an important concept to understand. My advice would be imagine "plain 32-bit paging" where the last page directory entry refers to itself, and then manually (on paper) work out what the CPU would do when it needs to access anything in the area from 0xFFC00000 to 0xFFFFFFFF (e.g. CPU uses CR3 to find the physical address of the page directory, then uses the highest 10 bits of the virtual address to find which page directory entry to use, etc).

Didnt he write that it sucked too? I got a little confused

So, you can now access ALL PTE's and the PDE using this, however it does consume 4mb of virtual memory, and other tricks need to be implemented if you want to support things like PAE, etc. This trick also sucks in long mode, since there is a much larger area
of memory that could possibly be mapped.

What (I assume) Ready4Dis means is that in long mode you can use the same trick (e.g. make the last PML4 entry refer to the PML4 itself), and in this case it will consume a relatively large amount of space because the virtual address space is huge.

If you do the maths, in this case (long mode) the mapping itself will consume 512 GiB of space. At first glance this does sound huge, until you realize that the address space itself is 262144 GiB and that 512 GiB is only 0.1953125% of the total virtual address space. More importantly, in long mode a virtual address space is split into two separate 131072 GiB halves, where normally the upper 131072 GiB half is used for "kernel space" and the lower 131072 GiB half is used for "user space", and where the mapping would consume 0.390625% of this (typically unused) "kernel space", and the amount of space left for processes remains the same.

Also note that in all cases we're talking about space, not RAM. For example, for plain paging the self reference trick costs 4 MiB of space (and zero bytes of RAM), and for long mode the self reference trick costs 512 GiB of space (and zero bytes of RAM).

For PAE things get a little trickier, but once you understand the basic concept it's easy enough to figure out. If you make a PDPT (Page Directory Pointer Table) entry point to the PDPT itself then it'll cost you 1 GiB of space (or 25% of the total virtual address space size) where most of this space is entirely wasted (can't be used for anything at all), which is a massive problem. However, for PAE there's only 4 page directories, and you can make the last 4 page directory entries in the highest page directory refer to each page directory, and end up with a 8 MiB mapping. This is only slightly more complex, but still only costs a tiny fraction of the total virtual address space.

The only other part you'd need to understand is how to manage the protection bits, the accessed/dirty bits and the bits that control caching. My advice here is to always set all of them (so that everything is "accessed, dirty, read/write executable, write-back") except for the bits in the lowest level entries (e.g. in the page table entries); and only ever use the protection bits, the accessed/dirty bits and the bits that control caching in the lowest level entries (e.g. in the page table entries) to control the attributes for individual pages.


Cheers,

Brendan

[mangaluve]

THanks! Can you tell me more about the situation your described, with "plain 32 bit paging"? Like give me more details on how I should think. Should only the very last PDE point to itself? That only maps 4 megabytes of the virtual memory (the last PDE), namely FFBFFFFF - FFFFFF. If a look what happens when the CPU tries to access memory covered by the last PDE, it will end up with the last PDE as the start of a Page Table, and use the next 4096 bytes to determine the physical address (and for all I know, what comes after the last PDE could be anything). I think I mssed something.

Edit: I think I understand a little more now. If I set the last PDE to point to the beginning of my PD, then the last 4 MB of memory will map to all my page table entries, right?

Just a short one, whats wrong with just reserving 4 MB of virtual memory to use for the page tables and not use the trick above?

[Brendan]

Hi,

Edit: I think I understand a little more now. If I set the last PDE to point to the beginning of my PD, then the last 4 MB of memory will map to all my page table entries, right?

The area from 0xFFFFF000 to 0xFFFFFFFF becomes a mapping of all page directory entries, and the area from 0xFFC00000 to 0xFFFFFFFF becomes a mapping of all page table entries (if the corresponding page table is present). These areas overlap because the page directory is being used as a page table - the area from 0xFFFFF000 to 0xFFFFFFFF contains the page directory entries and the page table entries for the last page table (which is the same thing).

To access the page directory entry for any virtual address you'd be able to do "mov eax,[0xFFFFF000 + (virtualAddress >> 20) * 4]", and (if the page table is present) to access the page table entry for any virtual address you'd be able to do "mov eax,[0xFFC00000 + (virtualAddress >> 12) * 4]". Most C programmers would use these areas as arrays and let the compiler do some of the work, so they can access any page directory entry as "PDE = pageDirectoryMapping[virtualAddress >> 20]" and any page table entry as "PTE = pageTableMapping[virtualAddress >> 12]".

Now imagine that someone wants to allocate a new page at 0x12345000. You need to check if a page table exists for this area (and if the page table doesn't exist, allocate a new page of RAM to use as a page table, create a page directory entry for it, and INVLPG the mapping for the new page table), then check if the page already exists (and if the page doesn't exist, allocate a new page of RAM, create a page table entry for the new page, and INVLPG the new page).

The same sort of lookups are needed for lots of things - freeing a page, checking accessed/dirty bits, changing page attributes (read, write, execute, etc), page fault handling, etc. Basically, having fast access to page directory entries and page table entries is important, because it speeds up everything your virtual memory management code does.

Without making a page directory entry refer to the page directory, you need to find some other way to access page directory entries and page table entries, and there is no better way (all the other ways are slower, more complicated and waste more RAM).

Just a short one, whats wrong with just reserving 4 MB of virtual memory to use for the page tables and not use the trick above?

In this case it'll cost you an extra 4 KiB of RAM for the page table you use for the mapping, you won't have any way to access the page directory, when you change a page directory entry you'll also need to change the data in the page table you use for the mapping, and the page table you use for the mapping will contain (almost) exactly the same data as the page directory. Basically it'd work, but it'd be slower, more complicated and waste more RAM.


Cheers,

Brendan

[mangaluve]

Thanks for the explanations, I finally got it The reason I misunderstood in the beginning was that I thought that the last Page Dir Entry should refer to itself and not to the beginning of the Page Directory, in which case things would get pretty weird Anyways, it's a very nice trick

[Ready4Dis]

Sorry, was a bit short on time, and no code or anything in front of me. Glad everyone else could explain a little better. I use this 'trick' in my OS, however I don't currently support PSE/PAE or long mode, although I am going to probably drop 32-bit support and stick with 64-bit only since most computers are migrating, although net-books are the only thing sticking to 32-bit, which I would like to get into a bit also. Anyways, let us know if you run into any problems while implementing, or have any other questions.

[mangaluve]

Well I have a couple of questions I guess that the memory that is filled with my kernel (the code and static variables and such) should be mapped linearly? So what is the best way of initializing this? I have to get a couple of page tables (perhaps just one) and map the kernel code Before I enable paging.

[JohnnyTheDon]

I recommend something like a stage 3 loader that sets up paging, SMP, etc. and loads your kernel. You can do this quite easily with grub multiboot modules or you can use some sort of similar scheme with your own bootloader.

[narke]

Well I have a couple of questions I guess that the memory that is filled with my kernel (the code and static variables and such) should be mapped linearly? So what is the best way of initializing this? I have to get a couple of page tables (perhaps just one) and map the kernel code Before I enable paging.

Look for identity-mapping.