Memory management in a microkernel

[GMorgan]

Hi Guys,

I've been thinking about how an L4 style microkernel would handle memory management and have a few questions about how certain scenarios would commonly play out.

Just for reference assume something like the Linux structures. In L4 the buddy algorithm lives in a userspace process. When another process wants a page it'll IPC the memory manager and the manager IPCs back with a map instruction the kernel honours built in. The kernel is the sole arbiter of the page tables and provided the sending process has the right to map that page it will honour the request.

When the kernel wants to evict a page it will IPC with the page in question for the memory manager to page it out.

Two scenarios bother me. How does the memory manager give itself more pages? How does the kernel get more pages?

For the first the manager knows nothing about page tables but I assume it can trivially self IPC to map. Is that how this is commonly done?

For the second the kernel obviously cannot just steal a page because it will invalidate the memory managers internal structures which it must know nothing about (if it starts poking the memory managers structures we may as well move it all in kernel). Does it IPC for memory as well? Make the kernel process 0 as far as IPC is concerned. Obviously there are special considerations, the memory manager must never OOM the kernel.

Any thoughts on these? Is IPC paging for the kernel efficient enough for real use? Should the kernel keep a pool and then pull pages asynchronously (I'm intending all my IPC to be async).

Thanks in advance.

[xenos]

I think it depends on the particular implementation. I have seen L4 kernels which reserve a fixed amount of memory (say a few MB) for themselves before handing the remaining free memory to the memory manager. This way the kernel has its own memory pool, separately from the memory manager. Probably this is not the most elegant solution, and there may be other implementations, but I don't know any particular one.

Personally I prefer to have the memory manager as part of the kernel, but this is different from the L4 philosophy. I imagine that in an L4 kernel there could be something like a thread ID for the kernel, without actually being a thread (like also interrupts have thread IDs) and is the kernel needs memory, it could use this thread ID to send a "fake IPC" to the memory manager (just like an interrupt would be forwarded to the handler thread via IPC), and then the memory manager would return the memory the same way via IPC as map or grant object, and the kernel would intercept this IPC when it sees its own thread ID and keep the memory for itself. But this is all just an idea, I haven't seen this used anywhere.

[Korona]

MM outside of the kernel either requires IPC that is guaranteed not to allocate, or some mechanism to ensure that there is always enough memory for IPC with the MM. This heavily conflicts with asynchronous IPC: asynchronous IPC constantly needs to allocate; usually on each request: as the IPC does not complete synchronously, some struct is necessary to memorize that there is an outstanding request.

[GMorgan]

As I understand it L4 style IPC doesn't need to allocate as it doesn't do copying. If you want to pass a big block of memory to L4 IPC there is a map request that literally just gives the receiving process the page with the data on. Any process can map its pages to any other process provided it doesn't increase access levels. Now the mapping would be done by the kernel before the IPC ever returns to the caller so is effectively synchronous.

The only remaining memory usage is capturing the register window which will be a maximum of 8 x 16 bytes a call. I've considered saying "if you have too many IPCs then you are basically a dead process" but that creates a vulnerability. An alternative is to actually just make the calling process wait or send a busy response (that every application will of course diligently check for) back if the queue is full.

There's also another aspect of this. If the MM allocates to itself by self IPC then that allocation is always synchronous, by the time the message returns it can receive and immediately discard an empty IPC and the kernel will have mapped the requested pages.

Of course I might well have missed something in all this. There are a lot of moving parts and undoubtedly people here know much more than me. This is definitely something I hadn't considered before.

[LtG]

Memory manager that doesn't manage memory (the kernel does)? That might be the problem.

If you absolutely have to do that, then I would suggest figuring out if it's possible for both the kernel and MM to only use static allocations (eg. no arbitrary few MiB and hoping it's enough).

But as said, I'd keep memory management within the memory manager, regardless whether you keep the MM within kernel or in a separate process.

Personally I'd start with the VMM/PMM separate from kernel and only include it in the kernel if there's a good reason, like performance, but of course that would happen at the very end of development.

[GMorgan]

The MM manages the memory but cannot set the page tables up. That has to be done in kernel space and is done that way in every L4 kernel. The MM determines what and tells the kernel to do it.

[thomtl]

@LtG Pretty noob question but how would you keep the PMM/VMM outside of the kernel, the kernel needs some way of spinning up those user processes right?

[GMorgan]

L4 pistachio at least uses a kickstart module that loads the kernel, sigma0 (the MM) and the root task into memory. The first thing sigma0 does is read the kernel information page and map the memory ranges recorded for initial modules there into itself.

Sigma0 then spends the rest of its life reading mm and ioport requests and forwarding the outcomes to the main kernel thread via IPC. Code below.

https://github.com/l4ka/pistachio/blob/ ... /sigma0.cc

[thomtl]

Huh, thanks i guess thats the way to do it then. Very odd coincidence though my OS is also called Sigma. I might have to look into something like that

[linguofreak]

Hi Guys,

I've been thinking about how an L4 style microkernel would handle memory management and have a few questions about how certain scenarios would commonly play out.

Just for reference assume something like the Linux structures. In L4 the buddy algorithm lives in a userspace process. When another process wants a page it'll IPC the memory manager and the manager IPCs back with a map instruction the kernel honours built in. The kernel is the sole arbiter of the page tables and provided the sending process has the right to map that page it will honour the request.

When the kernel wants to evict a page it will IPC with the page in question for the memory manager to page it out.

Two scenarios bother me. How does the memory manager give itself more pages? How does the kernel get more pages?

For the first the manager knows nothing about page tables but I assume it can trivially self IPC to map. Is that how this is commonly done?

For the second the kernel obviously cannot just steal a page because it will invalidate the memory managers internal structures which it must know nothing about (if it starts poking the memory managers structures we may as well move it all in kernel).

One option is that the kernel could reserve an area of memory for its own use before it starts the memory manager. In fact, unless the code and data that the kernel needs to start the memory manager is never again used for any other purpose (and can have the memory holding it deallocated), the kernel already has to do this to some degree, and the memory manager will never own *all* the memory on the system.

And in fact, designing the memory manager with the assumption that it does not own all the memory on the system has other advantages: For sandboxing, you could have multiple instances of the memory manager that operate on disjoint subsets of physical memory. For debugging, you could have an instance of the memory manager, instead of operating on physical memory, instead operating on a region in the address space of the debugger. The memory manager just needs to know that it is allocating pages from an address space, not the nature of that address space.

Obviously there are special considerations, the memory manager must never OOM the kernel.

Mustn't it? The memory manager just needs to tell the kernel that there is no memory left in the pool it manages to allocate from. The kernel may have pre-allocated, in which case the OOM just tells it that it needs to fall back on its pre-allocated pool and that the size of that pool is all that it has until further notice, so it needs to defer non-critical allocations. There may be separate memory managers running for general allocation without special requirements on location in physical memory and for providing physically contiguous buffers for device drivers, and if the manager for the general pool reports empty, the kernel could start allocating out of the contiguous pool. The allocation may be for some non-critical kernel functionality and the kernel may be able to proceed without the allocation succeeding. The kernel may implement an OOM killer and be able to kill a process to free up memory, in which case an OOM response to a kernel allocation request is the kernel's signal to ready the guillotine.

And if the kernel absolutely needs the memory and there is absolutely nowhere it can get new memory from, then the kernel needs to panic and it might as well know sooner rather than later.

It's the kernel's job to decide on what the policy should be in an OOM situation, the memory manager just needs to honestly inform the kernel when such a situation develops.

[GMorgan]

What I meant by 'never OOM' is it could conceivably restrict a user process while it should make every effort to service the kernel. If it is reserving pages for special needs, the kernel is special needs.

If a system is flat OOM and cannot even swap then the situation is different.

[LtG]

@LtG Pretty noob question but how would you keep the PMM/VMM outside of the kernel, the kernel needs some way of spinning up those user processes right?

You can have the bootstrap process setup a userland process called "init", and then init can do all the rest.

[LtG]

And if the kernel absolutely needs the memory and there is absolutely nowhere it can get new memory from, then the kernel needs to panic and it might as well know sooner rather than later.

I consider unnecessary kernel panics to be a design flaw. So the kernel should only panic if there's a hardware fault it can't deal with.