Should I use third party memory managers for the kernel?

[mrjbom]

Hello.
I want to be able to allocate memory for the needs of my kernel and release it after use.
Implement dynamic memory on their own seems to me too difficult, I do not really want to spend a lot of time on what would be from scratch to write page addressing and stuff. Using code from other people's projects is also difficult because it is difficult to understand someone else's code when dealing with such complex things.
Is there something universal that I can easily add to my kernel and not have to suffer with writing everything from scratch? I've seen libraries for this, tell me how difficult it is to use liballoc for this task and what I should implement in the kernel before using such libraries.

[bzt]

Hi,

Let's be more specific a bit here. You'll need at least 3 different memory allocators.

1. a physical page allocator, which is called by the virtual memory subsystem when it needs to map a new page (allocation unit 1 page)
2. a kernel heap, which is allocated when your kernel runs out of allocated memory (allocation unit minimum anything you want)
3. a user-space allocator, used by applications (allocation unit minimum is usually native word size or more, 16 bytes is typical for allocating 1 byte)

Now for the 1., I think it is the best that you write your own, because only you and your kernel knows how YOU manage RAM. There's no best option here, only different compromises. You have to decide how you want to deal with this. As for the 2., in theory you could use the same library as for 3., but most people tend not to do that, because kernel allocation is often special (either uses a special virtual memory address space, like higher-half, or needs special requirements on physical addresses like for DMA, and as running under supervisor-mode it can't call sbrk system call if your interrupt handler is not ring-independently re-entrant etc.). The last, the 3. allocator (malloc / free) is pretty much straightforward, therefore you can use any existing libraries you want for them, provided you have already implemented sbrk or mmap system calls (depends which allocator library you choose.) All the OSS libraries you can find (dlmalloc, ptmalloc, jemalloc, hoard etc.) are most likely written for this level, with the notable exception of SLAB allocator which was specifically designed for level 2. The others can be used for level 2. too, but only after minor tweaks and modifications.

Cheers,
bzt

[Craze Frog]

If you do not know how to write your own, it is best to write your own (make it simple).

Then, when you have that working, you can optimize by reading about other approaches.

[mrjbom]

Hi,

Let's be more specific a bit here. You'll need at least 3 different memory allocators.

1. a physical page allocator, which is called by the virtual memory subsystem when it needs to map a new page (allocation unit 1 page)

I wrote a Frame Page Allocator, it is able to select pages and delete them, the size of 4096 bytes.

How will this help me in allocating the necessary amount of memory?

[bzt]

How will this help me in allocating the necessary amount of memory?

I'm not sure I understand what you're asking. It does not help you with high level allocation, it is a requirement to implement that.

For example, let's say there's no allocated memory at start (doesn't matter if we talk about kernel heap or user-space memory, the algorithm is the same).

At first, you'd like to allocate let say 128 bytes (either kalloc(128) or malloc(128), it's the same in this regard). Now you simply have no free memory to do that, so you have to make a call to your virtual memory manager and ask for a page. This page is allocated by the page allocator, and mapped (either to kernel memory or to user-space memory). Now you have 4096 bytes of free and mapped memory, so your high-level allocator can continue to fulfill the 128 bytes request. Next you allocate for example 8 bytes (again, either kalloc(8) or malloc(8)). This time there's enough free memory mapped in the virtual address space (either kernel heap or user-space), so there's no need to call the virtual memory manager, your high-level allocator can continue and serve the request.

As you can see there's nothing high-level allocator specific in this, meaning mapping pages into the address space is independent of the actual memory allocator implementation.

High level allocators usually have three options to do this low-level mapping call (note this is not a must nor something put in stone; it's more like a guide to help you out).
1. memory allocators in kernel usually do a direct call (specially in a monolithic design) or send a special message to the MM (microkernels)
2. old school memory allocators in user-space usually use sbrk system call to tell the kernel to map more free memory into user-space
3. newer memory allocators tend to use the memman interface, mmap() and munmap() to achieve the same

Now consider this: all allocators are different, but they all have to ask for more free memory at some point. This means if you take an allocator (like dlmalloc for example) and want to use it in your kernel, then you have to replace 2. with 1., but that's all you need to do. Likewise, to use jemalloc with your kernel, you'll have to replace 3. with 1., but that's all the modification you have to make to get it work in a kernel.

To make it clearer: calling malloc in user-space is fast and cheap, on the other hand asking the kernel to map more free memory is expensive. Therefore allocators like to ask to map more free memory (4k, 2M etc.) at once and then they are managing that mapped memory for the application. As a downside, these allocators like to hold on to that memory, so even though the RAM is not used by the application (at high-level it is all free and available), it is not returned to the OS either (the kernel keeps the mapping and sees that memory as used). Some allocators use a data structure (like dlmalloc) that stores the high-level free allocation records in the freed memory, therefore it is not possible for them to ever return memory to the OS (otherwise their data structure would became inconsistent). Hope this makes sense to you.

On the other hand, if you implement the kernel memory allocator yourself, then you can build on the intimate knowledge of when and how your kernel uses the memory, meaning you can return the RAM to the OS as soon as possible. Or you could keep it mapped in the hope that it will be needed again. With a custom allocator you decide this, with a third party allocator it is decided for you (and most allocator implementations don't return memory ever, as they rely on the process termination to actually unmap and free the RAM. Obviously not a good choice for kernel-heap as kernel terminates only when you power down the entire computer, so choose third party allocator wisely for a kernel, or even better, write your own.).

Cheers,
bzt