Is a static data structure for paging possible?

[pearmypie]

Hello guys, I'm intrigued by A. S. Tanenbaum's claim that there is no malloc in the Minix kernel, everything is (over)provisioned instead using compile-time constants. At a first glance everything seems fine; the array of processes is fixed-length, among other things. I am almost halfway through the Minix book and I'm exploring the source code for Minix 2.0.0 and 3.1.4 (which should have paging).

But how can Minix avoid dynamic memory management when it comes to constructing page tables for user processes? The `struct proc` type contains no mention of page tables. Pre-allocating a structure to keep the entire page table radix tree for a single process, let alone 64 or however many you #define, would take 512^4*8=512GB, so how is it possible?

I think it might have something to do with the VM server, but I don't know how a user process could possibly modify its own page table, let alone other processes' or the kernel's. I thought scheduling, IPC and virtual memory management comfortably fit the responsibilities of a microkernel, so why would VMM be a user process?

Thanks

[Octocontrabass]

there is no malloc

I'm pretty sure the Minix kernel doesn't have any dynamic memory management, but it is possible to have dynamic memory management without malloc. You wouldn't want to use malloc for page tables anyway.

I thought scheduling, IPC and virtual memory management comfortably fit the responsibilities of a microkernel, so why would VMM be a user process?

Most aspects of virtual memory management don't actually need kernel privileges, so if you want your kernel to be especially micro, you put VMM in a user process. As far as I can tell, this is what Minix does.

Now, if you don't want a user process to mess with page tables, you don't have to allow that. There are microkernel designs where the user process only implements policy decisions and the actual page table manipulation is handled by the kernel.

You could also have all aspects of VMM in the kernel and still call it a microkernel. The definition of a microkernel is pretty nebulous.

[pearmypie]

Most aspects of virtual memory management don't actually need kernel privileges,

You're totally right, thanks for the reply. I've looked into it, and VMM is really done through message passing.

The `struct proc` type contains no mention of page tables.

This was just superficial on my part. `proc.p_seg.p_cr3` was right there, I just assumed that p_seg contained segment register values.

[thewrongchristian]

Hello guys, I'm intrigued by A. S. Tanenbaum's claim that there is no malloc in the Minix kernel, everything is (over)provisioned instead using compile-time constants. At a first glance everything seems fine; the array of processes is fixed-length, among other things. I am almost halfway through the Minix book and I'm exploring the source code for Minix 2.0.0 and 3.1.4 (which should have paging).

But how can Minix avoid dynamic memory management when it comes to constructing page tables for user processes? The `struct proc` type contains no mention of page tables. Pre-allocating a structure to keep the entire page table radix tree for a single process, let alone 64 or however many you #define, would take 512^4*8=512GB, so how is it possible?

I think it might have something to do with the VM server, but I don't know how a user process could possibly modify its own page table, let alone other processes' or the kernel's. I thought scheduling, IPC and virtual memory management comfortably fit the responsibilities of a microkernel, so why would VMM be a user process?

Why would you need the entire page table radix tree for any process?

It is possible that the hardware page table can be entirely transient, populated on demand, as memory pages are referenced. If a page mapping isn't defined at the point of use, we trap to the page fault handler, which generates a new PTE that is installed into the page table, and the faulting instruction retried. This can form the basis of an interface for the page table that makes no assumptions on the structure of the page table implementation itself. But it also means we make no assumptions on the lifetime of a mapping, so mappings can be discarded at will and recreated as necessary, so the entire paging radix tree can be dynamically created and destroyed depending on what pages the process is referencing.

It might be that a process would have a working set of only a handful of page tables. Basically, you'd have a code working set (.text segment, common library functions and shared libraries), a stack working set, and a global/heap data working set. With perhaps a working set of 1MB (probably on the large side for a working set in many cases,) that's only 256 page mappings, which can be handled in a single page table page! A single page table has a reach of 4MB (classic i386 page, 2MB if using PAE).

So, depending on your application, it would be entirely reasonable to have a pool of perhaps 64 page table/directory pages, statically allocated in the microkernel image and reused in some sort of NRU or LRU manner.

So, assuming 64 4K pages, that's only 256KB of statically allocated page table memory, and that can map nearly 1GB of memory at any one time, plus any CPU overhead to manage page reuse. 64 pages not enough? Add some more pages to the pool.

For a microkernel, what else would you need to allocate? All the VMM and filesystem data structures are handled in the user space server process, and your microkernel just becomes an abstraction behind which address spaces are switched and VA mapped to some physical page, all described using an API that completely hides the MMU implementation.

[pearmypie]

Why would you need the entire page table radix tree for any process?

What I was initially asking, was how is it possible to manage page tables for processes (of which the kernel supports a fix number) without dynamic memory management, akin to a statically sized array. I quickly realized my confusion and read more on the topic; I should finish my memory management code in the following weeks (if I don't relax too much during the holidays).