Allocating space for page directories and page tables

[Andy1988]

Hi all,
I'm currently experiencing a slight chicken and egg problem with my implementation of all this memory stuff in my kernel.

Just after coming from GRUB, I enable Paging. I need to do this because I'm using the Higher-Half-Trick.
The page aligned space for this process is reserved by a placement allocator. So far so good.
Then my physical memory manager is set up. It's just a Bitmap which keeps track of any allocated and free frames. I didn't spend any more time for this because I just want it to work for now... Speed improvements are later tasks.
After that my kernel heap is initialized because it relies on Paging. It has an initial size which is configurable and will be expanded dynamically if needed. Means when no more space is available at least one frame is requested and mapped into the heap space.

The problem is that sometimes I need to get page aligned memory for all later page directories I set up for other threads/processes. Getting my heap to do this is a hard task I think.
I thought about taking full 4KB pages directly from the physical memory manager. But where do I map them into my virtual address space to modify them afterwards?
I could take another region for this. Let's say I use a 512MB section above my heap for this, but this would limit my flexibility. After creating/modifying them I could unmap them again. When there is need to modify the particular address space of a thread/process I would need to map it again into the kernel directory search for existing page tables inside it and map them too to some location. That's probably even more work than getting my heap to support page aligned memory allocation, would always destroy almost my complete TLB because I need to flush it after unmapping and takes much time.

How do you do this in your operating systems?

[NickJohnson]

There are a couple ways to do this, but all of them require the use of the heap. The most correct way (imho) is to write a function in the heap allocator that finds a block in the heap the size of the requested block plus one page size, and returns the part of that block that is page aligned; it is guaranteed that there will be a section that is page aligned because there is one page of extra space. As long as you leave holes on both side of that block after figuring out which piece is page aligned, you won't waste memory and won't have to have a special free() function.

The second, much lazier way is the one I use: just have the kernel heap allocate only single pages, all aligned. This seems like a strange restriction, but it makes the allocator extremely simple (~50 lines), fast, and have no memory waste/fragmentation. In my design, the heap is used almost exclusively for allocating page tables and directories, so it actually works quite well. You can only allocate things that are one page in size, so there can be no extra metadata in the page directories, which is sometimes done. For a more conventional design, you could have a separate allocator for paging structures that works like this along with the main heap.

If you already have a good heap algorithm, I would go with the first choice.

[Owen]

I'm doing this in Long Mode - but for Protected Mode it's similar.

I allocate two PML4 (Top level page directory) entries, one for mapping the current task's page tables, and one for mapping a foreign task's page tables. I just map the PML4 into itself; this works fine, though one has to be careful arround 4MB/1GB pages.

I allocate most of kernel space for the heap, then on top of that have regions for various purposes - mapping the page tables/another process' page tables, temporarily mapping pages and so on.

To allocate a paging structure I just request a (pre zeroed) page from my physical page allocator and use the directories mapped into themselves to map it in, then again use the recursive mapping to add entries to it. I also have special regions of address space for temporarily mapping pages and so on.

I find the idea of using the heap allocator for this to be wasteful and inefficient.

[NickJohnson]

To allocate a paging structure I just request a (pre zeroed) page from my physical page allocator and use the directories mapped into themselves to map it in, then again use the recursive mapping to add entries to it. I also have special regions of address space for temporarily mapping pages and so on.

I find the idea of using the heap allocator for this to be wasteful and inefficient.

Brilliant! I can't believe I didn't think of that! Using that technique, I could completely eliminate my kernel heap, saving tons of precious protected mode address space. A kernel that uses only 8 MB of address space would be impressive. Of course, each paging structure modification outside the current address space requires a cache invalidation, but that is pretty rare anyway.

In case I'm misinterpreting you, this is what I think you mean: Paging structures are allocated only from the physical page allocator, and not mapped in virtual address space. They are mapped on the fly only when they need to be accessed.

[AndreaOrru]

@Owen: I'm also very interested in your design, partly because I once thought something like that for my 64-bit kernel.
Can you please elaborate a bit more?

[Andy1988]

In case I'm misinterpreting you, this is what I think you mean: Paging structures are allocated only from the physical page allocator, and not mapped in virtual address space. They are mapped on the fly only when they need to be accessed.

That's the way it came to my mind this evening and I think it's the way how Owen implemented it.
Seems I have not been the first with this idea (Uaahhh... I just had to look up the tenses to get the grammar right. I hope it is. )

I'm currently trying to implement it. And again... I could slap myself for my decision about writing my kernel in C++

I can't just allocate memory and cast it. The constructor wouldn't be called.
All other ways were too hack-ish and just bad code

I'll redesign my whole memory stuff from scratch.
Physical memory allocator, paging, heap and the stacks. Much work, but hopefully I'll get a better design out of it.

I'm pretty self-critical about my code quality.

[Owen]

It's much simpler than creating a temporary mapping each time: Just point a page directory entry at the page directory (Or, in Long Mode, PML4 entry at the PML4).

This is mentioned in the [url=http://wiki.osdev.org/Paging]Paging[url] wiki article, and I remember reading about it years ago on OSDever.net...

Be careful to invalidate the TLBs correctly though when doing this

[AndreaOrru]

I'm already pointing a PML4 entry to the PML4 itself.
I'm interested in the mechanism you use to write into foreign tasks' space.

[AndreaOrru]

Up.
So, Owen, do you do something like this?

current_PML4[511] points at current_PML4
current_PML4[510] points at foreign_PML4

And then you use something like a watermark allocator for mapping temporary pages of foreign address spaces, maybe?

[Owen]

I use a stack for tracking pages in my temporary mapping table, and don't allow mapping consecutive pages. In general, this is faster than other methods would be

[KurtGollhardt]

It's much simpler than creating a temporary mapping each time: Just point a page directory entry at the page directory (Or, in Long Mode, PML4 entry at the PML4).

This is mentioned in the [url=http://wiki.osdev.org/Paging]Paging[url] wiki article, and I remember reading about it years ago on OSDever.net...

Be careful to invalidate the TLBs correctly though when doing this

This is a good trick you can use on IA-32 and similar MMUs, because the PDE & PTE formats are compatible. It lets you manipulate all of the PTEs & PDEs without allocating any extra physical memory for PTEs to map virtual to the PTEs & PDEs themselves.

As the wiki article suggests, you can also use this same mapping to obtain the physical address for any virtual address (in a currently-mapped address space).

With a second dedicated entry in the PDE (or PML4), as Owen suggests (current_PML4[510] in andreaorru's example), you can change this entry to point to the PDE (PML4) of another address space of interest (and flush the TLB if necessary) and use the same algorithm (with a constant offset) to obtain physical addresses or access PTEs/PDEs for the other address space.

I used this trick back in UnixWare 7, as one of several performance enhancements that got us benchmark-winning performance.

How you allocate physical page tables for new PTEs that fall into ranges that don't already have page tables allocated is another matter, which several others have touched on.