kernel memory: buddy system and slab allocator

[milouz]

Hi all,

Here is the problem :

• Kmalloc() frequently relies on some slab allocator
• Slab allocator relies on page frames allocations
• Page frames are frequently managed with a buddy system
• Buddy system uses some linked lists whose item are allocated with kmalloc()

When developing my own kernel, solving that circular problem was rather hair raising and I'm still not sure about my solution.

What are your thoughts about that ?

[Nessphoro]

Static allocation.
Better yet, use a stack allocator

[sortie]

Use unallocated memory to keep track of unallocated memory.

A simple solution to keeping track of unused physical frames is to have a stack full of pointers. When the stack grows too big, then you pop an unused physical frame off it, map it somewhere, and then you have another pageful of pointers available. You can then push/pop to the stack and have constant time physical frame allocation, and when the stack is empty, you just start eating the pages you used to map the memory with, and there is no overhead in memory usage when you need the memory.

In addition, you need some system for keeping allocating virtual memory ranges. The kernel heap can simply be a region that has a lot of places to go (perhaps 256 MiB or much more) so allocating more virtual memory areas will always succeed for the kernel given that the heap doesn't get too large. Other virtual memory allocations will need some data structure that is allocated from the kernel heap, but it can rely on that.

Lastly, you would need a component that simply maps the allocated physical frames at the allocated memory range. For example, if you have a driver that needs 16 physical frames and mapping them somewhere, then it can do:

Code: Select all

unsigned long physical_frames[16];
allocate_physical_frame(physical_frames, 16);
unsigned long map_at;
allocate_virtual_kernel_address_space(&map_at, PAGE_SIZE * 16);
for ( size_t i = 0; i < 16; i++ )
    map_physical_frame_at(physical_frame[i], map_at + PAGE_SIZE * i);
memory_flush();

It's a good idea to detach the concept of allocating virtual address space from allocating actual physical frames. This allows a driver that does memory mapped IO to bring its own physical frames, allocate somewhere to map them, and then just map them. Of course, this procedure is a bit bothersome in this case where you just want 16 pages somewhere, but you can build nice utility functions based on this.

To implement malloc, you must first code a system for allocating a memory region for the kernel heap. You can simply statically decide somewhere nice where you know there will be plenty of room and then simply map a page there or two. Once that isn't enough, you simply increase the pointer, pop a few physical frames and map them there. It may also be useful with a shrinking primitive, but probably not really.

Your malloc will now simply ask the size of this regionand its location from the memory region backend. It will initialize be 0 bytes, but gradually grow. The task is now simply to manage this large memory buffer and implement the traditional malloc semantics.

[Yoda]

Buddy system uses some linked lists whose item are allocated with kmalloc()

Here is the root of problem.
You have the following options:
- Pre-allocate memory for buddy allocator;
- Re-design buddy not to use linked lists;
- Or use another algorithm that doesn't require kmalloc(). For example, stack allocator.
I use page allocator based on table structures which are pre-allocated at system startup (using primitive allocator which is substituted after all allocation mechanism is set up) and never free.

[milouz]

- Pre-allocate memory for buddy allocator;

You mean creating sufficient dedicated slabs ?
That's what I did, but dealing with dead locks when adding new slabs was not simple at all.

- Re-design buddy not to use linked lists;

???
Looked for on the web but found nothing about such a method. How could we do that ?

- Or use another algorithm that doesn't require kmalloc(). For example, stack allocator.
I use page allocator based on table structures which are pre-allocated at system startup (using primitive allocator which is substituted after all allocation mechanism is set up) and never free.c

You mean replacing buddy system with stack allocator ? Well, definitely out of topic for me as I'd like to allocate several contiguous frames.

[Combuster]

The typial "stack allocator" is actually a linked list with the elements being stored in "free" memory - i.e. all the details about free pages is stored in the free pages themselves, resulting in no free pages = no memory overhead.

If you understand how that trick works, you might be able to extend that to buddy allocators. Or you can do what all the bitmap-users do: have a dedicated setup function that subtracts the space needed for the data structures from the system ram during setup itself.

[milouz]

The typial "stack allocator" is actually a linked list with the elements being stored in "free" memory - i.e. all the details about free pages is stored in the free pages themselves, resulting in no free pages = no memory overhead.

If you understand how that trick works, you might be able to extend that to buddy allocators.

I did it too. But I also found that dealing properly with locks was very difficult due to the intrinsic circularity between slabs and buddy system. In fact, I omit something else : creating some new slab could lead to page table creation (we need to map pf to vm). Thus we have:

kmalloc -> slab creation -> pf allocation (buddy system) -> kmalloc

and:

slab creation -> mapping (pf, vm) -> create page table -> pf allocation

Because all those functions are reentrant, I protected some structures with locks. My kernel is for now perfectly running but I'm still afraid of dead locks and that's why I wondered how to deal properly with all that complexity.

[Yoda]

You mean creating sufficient dedicated slabs?
That's what I did, but dealing with dead locks when adding new slabs was not simple at all.

First, you may allocate basic data structures needed to start your main allocator just by primitive algorithm, for example increasing pointer on heap.
Second, you may keep pool of pages needed for your linked list and watch that it doesn't drop below some level, defined by the momentary demand of allocator. As soon as it drops below, fill the pool.
Third, you may try to use free memory to setup data structures for allocator, as in stack allocator.

- Re-design buddy not to use linked lists;

???
Looked for on the web but found nothing about such a method. How could we do that?

Redesign means new design. I don't like buddy concept and don't use it. Instead I use a brand new table-driven algorithm which doesn't have circular dependencies.

BTW, did you check how the Linux kernel buddy allocator is implemented?

[milouz]

BTW, did you check how the Linux kernel buddy allocator is implemented?

Yes, I gave it a quick look but as usual with Linux sources, load of abstractions layers make them difficult to understand them at first glance.

Btw, I just thought about a method to use buddy allocator without the need to dynamic allocation (creating an array of node, on for each frame, and each node has a pointer to his next buddy). Just implementing it and have to test it.