circular dependency in paging

[tkausl]

Hello

I'm having a bit of a problem with paging. I use a higher-half kernel, beginning at 3GB + 1MB and the first thing i do is i map 4 megabytes from virtual 3GB to 0. This works (for now). Then i set up my 'kernel heap' to allocate space beginning with the virtual-kernel-end address (should be somewhere around 3GB + 2MB). This works too. The Problem now is, consider the following:

I request some bytes in kernel-heap. The heap is exhausted so it has to request the paging to map a new frame to the end of kernel-heap. BUT: The end of kernel-heap is an address dividable by (4096*1024) which would mean, it lies in the page-directory at an offset where no page-table is created yet, so the paging itself has to request a new page from kernel-heap first, to create the new page-table. Now everything breaks since kmalloc needs a new page and the paging needs allocated space from kmalloc. How would i handle this? I thought about pre-creating 256 page-tables for the 3GB-4GB (kernel) range so i'd never need a new page-table when i need space in kernel-heap. Also, this would mean i don't need to care about synchronizing processes kernel-space mappings since every processes page-directory already has the kernel-space tables set.

[alexfru]

I can't see a problem. If you need to allocate two page frames, allocate two. At once or one by one.
You should have a method like this:
tError MapVa(virtual_address, size, options);
If it sees that it needs to create one or more page tables, it does so.
You should also have a separate data structure to hold page frames available for allocation. When you allocate one from it, it shouldn't grow in size and require memory for itself. If, however, you wish to make its size change dynamically, based on how full it is, you should indeed be cautious about recursion, you should probably handle shrinking and growing of the structure holding available page frames at the same level.

[Brendan]

Hi,

I request some bytes in kernel-heap. The heap is exhausted so it has to request the paging to map a new frame to the end of kernel-heap. BUT: The end of kernel-heap is an address dividable by (4096*1024) which would mean, it lies in the page-directory at an offset where no page-table is created yet, so the paging itself has to request a new page from kernel-heap first, to create the new page-table. Now everything breaks since kmalloc needs a new page and the paging needs allocated space from kmalloc. How would i handle this? I thought about pre-creating 256 page-tables for the 3GB-4GB (kernel) range so i'd never need a new page-table when i need space in kernel-heap. Also, this would mean i don't need to care about synchronizing processes kernel-space mappings since every processes page-directory already has the kernel-space tables set.

Typically, you would:

• Map the kernel and its data/bss where you want it
• Process the physical address space map that you got from firmware and/or boot loader (using space in your kernel's bss where necessary)
• Initialise a physical memory manager (using space reserved in your bss if necessary)
• Initialise a virtual memory manager (using RAM allocated from the physical memory manager when needed)
• Initialise the kernel's heap (using virtual space allocated from the virtual memory manager)

Note: Depending on kernel design and other factors, you might not need/want a kernel heap and might use more efficient methods (object pools, etc) instead.


Cheers,

Brendan

[tkausl]

Typically, you would:

• Map the kernel and its data/bss where you want it
• Process the physical address space map that you got from firmware and/or boot loader (using space in your kernel's bss where necessary)
• Initialise a physical memory manager (using space reserved in your bss if necessary)

Thats alreay working fine, no problem here.

[*]Initialise a virtual memory manager (using RAM allocated from the physical memory manager when needed)
[*]Initialise the kernel's heap (using virtual space allocated from the virtual memory manager)[/list]

Thats my problem, the virtual memory manager allocates memory for the page-directory and page-tables from the kernel-heap which itself requests to map pages in.

Note: Depending on kernel design and other factors, you might not need/want a kernel heap and might use more efficient methods (object pools, etc) instead.

Don't know what you mean with object pool (i'll google that) but even if i don't use a kernel-heap, i still need to have some space mapped in every processes addresspace, at least the kernel and most likely the processes own page-directory and tables, or shouldn't the different directorys go into kernel space? (I think they somehow have to because i need to access them from the kernel?!)

[Combuster]

The existing page directory and table are available for editing - or at least, they should be. You can map any 4K page into that table, or any 4M page into the directory as a temporary measure to modify any physical memory.

[Kevin]

Now everything breaks since kmalloc needs a new page and the paging needs allocated space from kmalloc. How would i handle this?

Your paging code shouldn't use kmalloc, but directly allocate a physical page, with no VMM involvement at all.

In order to map that new page, you need to keep the page directory and at least one page table with free entries mapped all the time. On i386, it's easiest to actually keep all page tables of the active memory context mapped by using recursive mapping (i.e. using the page directory as a page table at the same time, so that you map all page tables there).

[Brendan]

Hi,

Typically, you would:

• Map the kernel and its data/bss where you want it
• Process the physical address space map that you got from firmware and/or boot loader (using space in your kernel's bss where necessary)
• Initialise a physical memory manager (using space reserved in your bss if necessary)

Thats alreay working fine, no problem here.

[*]Initialise a virtual memory manager (using RAM allocated from the physical memory manager when needed)
[*]Initialise the kernel's heap (using virtual space allocated from the virtual memory manager)[/list]

Thats my problem, the virtual memory manager allocates memory for the page-directory and page-tables from the kernel-heap which itself requests to map pages in.

Then your virtual memory manager is broken. It should be allocating memory (for the page-directory, page-tables and normal virtual pages) directly from the physical memory manager. The kernel's heap has nothing to do with any of these allocations at all. The kernel's heap is a consumer of the virtual pages allocated via. the virtual memory and not the other way around.

Note: Depending on kernel design and other factors, you might not need/want a kernel heap and might use more efficient methods (object pools, etc) instead.

Don't know what you mean with object pool (i'll google that) but even if i don't use a kernel-heap, i still need to have some space mapped in every processes addresspace, at least the kernel and most likely the processes own page-directory and tables, or shouldn't the different directorys go into kernel space? (I think they somehow have to because i need to access them from the kernel?!)

For an example; let's say that for each thread you want the kernel to have a "thread data structure" to keep track of it. You decide this structure will be 4 KiB because it's a nice number (and each thread has a kernel stack that you decided can go into the thread data structure). You do some maths and decide that (because its a 32-bit kernel and kernel space very limited) it's unreasonable to support more than 131072 threads, which means that for the worst case all thread data structures consume 512 MiB of kernel space.

Now; you have a look at your "kernel space layout" and decide that the area from 0xC0000000 to 0xD0000000 will be used for the kernel's code, etc; the 512 MiB area from 0xD0000000 to 0xEFFFFFFF will be used for an array of thread data structures, and the area from 0xF0000000 to 0xFFFFFFFF will be used for other things.

Basically; you've got a big fat 512 MiB array of thread data structures; but this is only space and not actual RAM. You have one physical page full of zeros, and one page table where every page is that physical page full of zeros. You map that everywhere as "read only". This makes the big fat 512 MiB array look like it's full of zeros but costs you almost no RAM at all.

When you create a thread you find an unused thread ID, then start creating the information in the thread data structure for that thread. It looks like a normal array (e.g. "thread_data_array[thread_ID].foo = bar") that's been pre-allocated, so you don't bother allocating any RAM for it. The first time a page is modified it causes a page fault (because the page full zeros is "read only") and the page fault handler allocates a physical page and maps it into that big fat array as "read write" (replacing the page full of zeros); but the rest of the kernel doesn't know or care about this because the virtual memory manager is taking care of it.

When a thread is terminated you do almost nothing - you don't free any memory. If the same thread ID is reused later, you just re-use the previously allocated RAM and avoid the initial page fault. However; if/when your physical memory manager starts to run out physical RAM you go on a scavenger hunt and finds any pages in that big fat 512 MiB array that aren't actually being used - if you find any you replace them with the "page full of zeros mapped as read only" and free the physical page.

Now imagine that your kernel also has "process data structures" and you do essentially the same thing for those; and there's other things (message queues, an array of page directories, "per CPU" data structures, etc) and you do the same for all of that. Let's also assume it's a micro-kernel and there's nothing else - it's all using these sparse arrays.

The end result is there's no explicit allocations or de-allocations in the kernel, physical pages are recycled where possible (which improves performance) and garbage collected only if necessary, finding anything (e.g. finding a thread data structure for a thread ID) is as fast as possible (it's all just array indexing rather than searching), and there's no kernel heap because it was all pre-allocated space.


Cheers,

Brendan