OSDev.org

I am following James Molly's tutorial to write a toy OS. I found the memory management module particularly involved because the interdependence of paging and the kernel heap.

For example, in his implementation, paging relies on the kernel heap to dynamically allocate space for the page table data structures. Note that it needs the virtual address to be returned because once paging is enabled, everything is accessed via the virtual address. This is done in paging.c via:



On the other hand, the heap relies on paging as well to allocate physical frames when it needs to grow. This is done in kheap.c via:



So paging and the heap are interdependent on each other and tightly coupled together. I am wondering if it is possible to separate and implement them in a stacking fashion like TCP/IP protocols so that, say heap uses paging but paging does not depend on heap at all.

Then how / where do you allocate e.g. page table data structures, without a kernel heap?

Hi,




Over the years I've written about 5 "different but related" micro-kernels; but I've never bothered to have any heap in any of these kernels, and I know that I'll never have a heap in any future kernel either. However; for all of them it would have been easy to slap a heap on top of the virtual memory management (such that heap depends on VMM, but VMM continues to not depend on the existence of a heap).



Assuming a "3 layer model" (e.g. like this) the virtual memory manager would use the physical memory manager to allocate and free physical pages for things like page tables, etc.


Cheers,

Brendan

Hi,


For future reference, please take a look at the wiki page concerning the tutorial you are following.

For specifically memory management, I recommend reading Brendan's Memory Management Guide. If you are overwhelmed (just like about everyone reading that is), pick the parts you deem as most important and implement them. Then after some count of months or years you may add some more parts, then after another count of months or years you may add even more parts, etc.


Regards,
glauxosdever

Not going to lie, I assumed you wouldn't need memory management yet by that point o.o Especially since paging is one of the earliest things you want to get running in the kernel.

I didn't work yet on kernels for modern hardware so take this with a grain of salt but: I'd have the core of the kernel be a fixed size (i.e. all statically allocated, both code and variables), then have it figure out the RAM layout and put the page table right after the portion it uses up (no need for full-blown dynamic allocation, just compute the address range), the leave the page manager use everything after the page table (at which point you can start using dynamic allocation with proper heaps as usual).

tl;dr you shouldn't need a heap before paging is ready.

As for me it's not acceptable to make interdepencies between paging and pool management, if it is possible at all.

On mips, I have 256MB trivially mapped region, accessing which doesn't involve even TLB, so I put all the kernel there. It's very different from anything else.

On arm, as with x86, you first build system page tables at the OS loader and init code time, build PFN database and then, create pools (non-paged and paged) and others (system cache). Assigning them VAs, and binding to them physical (system) pages through memory manager services that work on PFN only. For this you cannot and do not need pools by themselves. From this point other modules might use pool memory for their needs.

@Brendan

Thank you very much for your awesome and enlightening guide (also referenced by glauxosdever). It is really helpful. Yet I am still a bit confused. Would you mind advising on if my following understanding?



I agree it is possible for the virtual memory (VM) manager to directly ask for physical pages (a.k.a frames), but the physical memory (PM) manager knows only the physical address, not the virtual address.

In the case of x86, once paging is enabled by manipulating the cr0 register, all memory accesses would be hardwired to use the virtual address. This includes accesses to page tables to determine if a particular page entry is dirty/present/etc or not. As a result, the VM manager must maintain both the virtual and the physical addresses of page tables.

The PM manager can certainly return physical addresses to the VM manager during allocation, but it is up to the VM manager to

1) maintain virtual address space data structures for the kernel and all processes
2) within a certain VM space, find a free/mappable virtual page address
3) establish the mapping from the virtual address to the physical address returned by the PM manager.

To satisfy requirement 2, and suppose the discussion is restricted to the kernel, the VM manager must maintain the mappable-or-not state of all virtual pages for the kernel. This is not a very big issue, but implies that the kernel had better have a static addressing space that does not grow or shrink. Otherwise it would be much harder for the VM manager to handle the kernel's memory space because the total number of "mappable-or-not states" would change dynamically. I think this is acceptable, because even x86 Linux also implements a 1GiB upper limit (called the highmem if I recall). If my understanding is correct, these two are very similar.

A more serious issue happens to requirement 1, because processes are created and destroyed dynamically, bringing the dynamic memory management issue to the VM manager. If we introduce a heap, then the VM manager would be dependent on the heap. But certainly the heap (as part of the kernel) depends on the VM manager as well. If we don't, how can the VM manager handle process fork and termination? Is there any better design?

Yeah that is certainly possible during the bootstrap. But after that, the kernel may want to allocate further paging data structures for userspace processes. And the allocation, let's say is done by the virtual memory manager, must return/maintain both the physical and virtual addresses. Then the virtual memory and the kernel heap will rely on each other.

Your first post says your problem is that you were under the impression that you need the heap to allocate the memory for the page tables. The point I was making is that you don't need the heap for that (getting rid of the interdependency), and indeed those tables should stay away from it (also for what's worth it, their size should remain fixed once reserved since it's proportional to the RAM size).

Also I'd argue that virtual-to-physical address mapping is something to do with paging, not the heap.

Hi,



Requirement 2 isn't necessarily a requirement. For example, the virtual memory manager can provide a "set area to virtual type" function, where the caller tells the virtual memory manager the starting virtual address and the ending virtual address of the area (or the size of the area), and where the "virtual type" can be one of "inaccessible", "read-write no-execute", "read-only executable", "memory mapped file", etc; and where the virtual memory manager does what its told with the area it was told and never finds/decides which area to use. I would (and have in the past) argue that this is how things should be done, even for "Unix like" OSs with monolithic kernels.



For a very simple virtual memory manager; let's assume that the virtual memory manager provides the following functions:

• uint64_t create_virtual_address_space(void); - constructs a new virtual address space (by allocating a physical page for the page directory and copying kernel's page directory entries into it) and returns a "abstract virtual address space identifier" (probably the physical address of the page directory)
• destroy_virtual_address_space(uint64_t address_space_ID); - destroys a virtual address space by scanning the page tables and telling the physical memory manager to free all physical pages that it references (including the page directory itself, but excluding everything in kernel space).
• change_virtual_area_type(void *start, void *end, int new_virtual_type); - for the virtual address space currently being used; compares the virtual type for each page in the ("explicitly specified by caller") area to what it already is, and does whatever is needed to change its virtual type (which could include telling the physical memory manager to allocate physical page/s and mapping them if the area is being changed from "not accessible" to "read-write RAM"; and could include telling the physical memory manager to free physical pages and unmapping them if the area is being changed from "read-write RAM" to "not accessible"; and could include doing nothing if a page happens to already be using the requested virtual type).
• create_memory_mapped_file_area(void *start, void *end, int file_handle, uint64_t file_offset); - essentially the same as "change_virtual_area_type()" with a little extra setup/metadata.
• clone_virtual_address_space(uint64_t source_address_space_ID); - sets the virtual page type for everything in user-space to "copy on write" in the source address space, calls "create_virtual_address_space()", and copies page tables from the source address space into the newly allocated virtual address space.

Let's also assume that all virtual pages have an "actual type" that must be encoded in the page table entries (e.g. present or not present, read-only/read-write, executable/not-executable), and a "pretend type". For example, the pretend type of a page might be "pretend read-write RAM" and its actual type might be "present read-write", but due to various paging tricks its actual type might be "not present" (e.g. the page is on swap space) or "present read-only" (e.g. the page is copy-on-write) or something else. The pretend type can also be encoded in the page table entries by using "available for OS use" bits in page table entries to augment the actual type.

Now; a lot of the virtual memory manager's functions can be implemented without any additional data (using page table entries and nothing else). You only need additional data to support:

• swap space (where a page is on swap space, how recently each page was accessed, etc)
• memory mapped files (which part of which file each page uses)
• copy on write resulting from "fork()" and shared memory areas (a reference count for each page)

However, I've never seen a kernel that allows any of these things to be used in kernel-space, and if you don't allow the kernel to do these things (e.g. don't allow kernel's pages to be sent to swap space, don't allow kernel to "fork()", etc) then the virtual memory manager can manage kernel space without using any additional data (using page table entries and nothing else).

For the extra data that the virtual memory manager needs to manage user-space, there's multiple different approaches. For example; some people use an array of "physical page metadata structures" (that's indexed by "physical page number") for keeping track of how recently each page was accessed and for keeping track of a reference count for each page, but some people don't; some people have a simple list of "memory mapped file metadata structures" and some people have elaborate trees; etc. How memory is allocated for these things also varies; and in some cases this memory can come from kernel's heap, but in those cases the kernel itself (and the kernel's heap) doesn't depend on them anyway.


Cheers,

Brendan

Assume that the physical memory manager only returns the page and the virtual memory manager has to do the copy work. (Please correct me if this is not the case.) How can the virtual memory manager even access the page entries of the new virtual memory space in order to copy something into it? It has to do so via the virtual address (of the page directory/tables, not the data that this space manages) because paging has been enabled in cr0. However, it seems to have no information about that. This can be illustrated by the following pseudocode:

Hi,



There's 2 options:

• temporarily map the physical page into kernel space while you modify it (and unmap it after); possibly using a 4 KiB "temporary mapping area" for each CPU.
• permanently map the physical page

For an example of the latter; for some of my micro-kernels I set aside an area of kernel space for a "page directory mapping area" and told the virtual memory manager that this area is "allocate on write" (essentially, map the same page full of zeros everywhere in the area as "read-only" so that if the kernel modifies anything in the area it causes a page fault where the page fault handler allocates a new page and maps it as "read-write"). Then I had a function to find an unused process ID, and once a process ID was assigned I could do "new_page_directory_virtual_addr = new_process_ID << 12 + page_directory_mapping_area_start;" to figure out where the page directory for that process was mapped and copy the kernel's page directory entries into it (which would "auto-allocate" the physical page if it wasn't already allocated because the whole area is "allocate on write"). After that's done I'd obtain the physical address of the page (that will become the new page directory) from the page table entry corresponding to the mapping.

Note that there is a related problem - because the kernel is mapped into all virtual address spaces; when you modify a page directory entry (e.g. add or remove a page table) for kernel space you need to modify every virtual address space/every page directory. This is what my "page directory mapping area" was really intended for - so I could do a "for each virtual address space { update page directory entry using the page directory mapping }" loop.

For my latest code (actually boot code and not a kernel, but it's the same problem because my boot code runs each "boot module" in its own isolated virtual address space) I used a very different approach. I didn't initialise the page directory when it's allocated (and don't update all page directories when a page directory entry is modified in "kernel space"); but instead I update the page directory during task switches by temporarily mapping it and copying "kernel space" page directory entries into it before switching to that virtual address space. Of course because it was just boot code (not performance critical) I was lazy - I always updated the page directory entries during every virtual address space switch whether it's necessary or not. For a kernel (where it is performance critical) I would've use version numbers and something like "if(next_process->page_directory_version < current_page_directory_version) { update_process_page_directory_to_new_version(next_process); }" during task switches so that it's only updated if it's necessary (if something changed since last time).

Unfortunately this was designed last year, and everything changed at the start of this year when the "meltdown vulnerability" was announced. Now I'm shifting to a "temporarily map the page directory if/when it needs to be accessed" approach (e.g. when the virtual address space is created) where only a small piece of "kernel space" (that doesn't change) is mapped into all virtual address spaces (and the kernel has its own special virtual address space that contains everything). In this case, because that small piece of "kernel space" doesn't change I won't need to update it during any task switches (but I will need to change from "process/boot module virtual address space" to "kernel virtual address space" when switching from CPL=3 to CPL=0 and change back again when switching from CPL=3 to CPL=0).


Cheers,

Brendan

Hi Brendan, thank you very much for the detailed response. However, I am still not entirely clear about it.



Does this implies that all page directories are assigned with virtual addresses (with the kernel memory space) that end with page_directory_mapping_area_start as the 12 offset bits?

If the page directory mapping area is 4KiB (i.e. of the same size with a page), and for simplicity assume the lower 12 bits of page_directory_mapping_area_start are all zeros (i.e. page_directory_mapping_area_start && 0xFFFFF000 == 0), then the page directory of process x would take exactly the whole 4KiB virtual page located at x<<12. (If I may, although not very relevant, I would like to confirm that this address x<<12 itself will be converted to a physical one by looking up the kernel page directory.)

If my understanding above is correct, then to avoid the use of a heap (or whatever dynamic memory management utilities) in the virtual memory manager, a lot of virtual pages in the kernel space have to be reserved for potential paging usage. This is because the process ID can range from 0 to, say 65535. Consequently:

The page directory of process 0 will be held at virtual address 0x00000000, and it is going to take up to 0x00000FFF.
The page directory of process 1 will be held at virtual address 0x00001000, and it is going to take up to 0x00001FFF.
...
The page directory of process 65535 will be held at virtual address 0x0FFFF000, and it is going to take up to 0x0FFFFFFF.

To support up to 65536 processes without paging's dependency on a heap, all the kernel RAM between 0x00000000 to 0x0FFFFFFF must be reserved so that the page directory of process x can be mapped with guarantee!!

I am not Brendan, of course, bu I'll say too. For process page tables and directories, you could use the kernel pool. You can have 1 process or 1000, so this dynamic allocation entity is good for it. I haven't done any process things yet, but I am going to do it this way.
Reserving might be needed for system page tables, those that describe the kernel part of an address space. It begins at the OS loader time, ultimately it's OS loader, that creates the page directory for the kernel space. and then switches to that space and jumps into kernel.

Hi,



That's mostly correct; except that you're forgetting that there's a "page_directory_mapping_area_base", so:

The page directory of process 0 will be held at virtual address "page_directory_mapping_area_base"
The page directory of process 1 will be held at virtual address "page_directory_mapping_area_base + 0x00001000"
...
The page directory of process 65535 will be held at virtual address "page_directory_mapping_area_base + 0x0FFFF000"

In other words, you can do:



Note that I use the "recursive mapping trick" so that the page table entries for the current virtual address space are also accessible; and because kernel space is always the same in all virtual address spaces this means that the page table entries for the kernel's pages are always accessible. In that case, you can fetch the physical address of a page directory from the page tables, like:



And if you don't need the virtual address you can combine both of these to get:



Note that K is a constant that can be calculated at compile time; so this ends up being two instructions - e.g. "mov eax,[K + eax*4]" followed by "and eax,0xFFFFF000".

In other words; to determine the virtual address of a page directory from a process ID it takes two instructions and no memory accesses (and no potential cache misses); and to determine the physical address of a page directory from a process ID it takes two instructions and one memory access (and one potential cache miss). Of course you'd also cache the physical address of a process' page directory in each of its thread's "thread data" so that it's a little more convenient to set CR3 during task switches.

I also use a similar approach for other things. For example; each process has a "process data area" (to store the process' name, how much CPU time it consumed, which threads belong to it, if it has special access to range/s of IO ports or memory mapped IO areas, etc), and each thread has a "thread data area" (to contain the thread's state used during task switches, for its kernel stack, "link" fields used for scheduler's queues, etc).

For message queues; in my case, each message queue is implemented as "linked list of 4 KiB blocks, where each block contains one or more variable length entries (one variable length entry per message)", and where memory management is done with an O(1) "stack of 4 KiB message queue blocks". A large area of kernel space is set aside for these message queue blocks (e.g. from 0xC0000000 to 0xD0000000); and that area uses the same "allocate on write" approach that's used for the "page directory mapping area" (and the "process data mapping area" and the "thread data mapping area").

Of course a micro-kernel doesn't contain much more than this (other than a few smaller things in the ".bss", etc). In other words; the physical memory management mostly uses free page stacks and doesn't need a heap; the virtual memory management is mostly done with page tables (and the "page directory mapping area") and doesn't need a heap; all of the process and thread management and scheduling is done with "process/thread data mapping areas" that don't need a heap; messaging/message queues have their own "stack of 4 KiB blocks" allocator that is much simpler and faster than a heap; and because it's a micro-kernel there's almost nothing else in kernel space so the kernel has no need for a heap.

There is one thing that I haven't mentioned (and probably should). Because almost everything uses "allocate on write", over time the amount of physical RAM the kernel is using grows. For example, if you create 100 processes it will allocate about 1200 KiB of physical RAM (for page directories, process data structures and one thread data structure per process) and when you destroy those 100 processes the physical RAM that was allocated will remain allocated (to improve performance by avoiding the need to re-allocate it next time its used). If/when the kernel is running low on physical RAM it asks all of the pieces to free some; and all the pieces (virtual memory manager, scheduler, messaging code, etc) have code to find "previously allocated but currently unused" pages and convert them back to "allocate on write" (causing the physical RAM to be freed). This is typically relatively simple - e.g. if you have code to find a free process ID (or find a free thread ID, or...) then it's not that hard to find all of the free process IDs (or all of the free thread IDs, or...) and tell the virtual memory manager to make sure the corresponding pages are "allocate on write" (even if they already are). Once that's done the virtual memory manager may scan kernel space looking for page tables that can also be freed. Of course this is typically done in a more progressive way (e.g. if kernel is only slightly worried about free physical memory then only free some pages and stop, without freeing as much as possible) and is sensitive to CPU load (e.g. be more aggressive about freeing pages if kernel has nothing better to do with CPU time), in the hope of avoiding/reducing "garbage collection stalls" under load.


Cheers,

Brendan