While at Linaro connect, I was discussing with someone the state of the Energy Aware Scheduler (EAS) patches. This is an ongoing project to update the Linux kernel scheduler to be aware of processor hardware to make better scheduling decisions and reduce power usage. Parts of the patch set have been accepted upstream but a large part still exists out of tree. The patch set is fairly intrusive and the scheduler in the kernel is a finicky piece of code. The EAS patches take a good bit work to maintain which brought up a general discussion of what subsystems would be easier or harder to replace than the scheduler. Someone proposed that kmalloc would be difficult but thinking about it, kmalloc is one of the easier places to write a new implementation.
kmalloc in the kernel serves the same purpose as malloc in userspace; it allocates heap memory. The fundamental behavior works the same as in userspace too:
malloc(something) try to allocate some memory if (I found some memory) return what I found else increase my heap if (I can't increase my heap) uh oh out of memory :( try to allocate some memory if (I found some memory) return what I found else uh oh out of memory :(
Yes, this is very hand wavy. The point here is that the heap is dynamic, it
grows with the size of the program. In userspace, the size of the heap is
controlled by sbrk or a similar system
call. In the kernel, kmalloc makes calls to the underlying page allocator
alloc_page). This is a part of the kernel that many people get confused
about, what’s the difference between a call to
kmalloc and a call to
alloc_pages is the lowest level memory allocator using
to allocate pages in
PAGE_SIZE order. A typical page size is 4096 bytes.
Most allocations do not require 4096 bytes. kmalloc sits on top of the
buddy allocator to manage smaller allocation sizes. In general, the buddy
allocator is only used directly when a physically contiguous
allocation is needed.
kmalloc should be used unless there is a specific
use case in mind.
The slab allocator works on top of
alloc_pages. The kernel currently offers
three different algorithms, SLOB, SLAB, and SLUB. There was a very good
a few years ago about the differences between these allocators. In general,
SLOB is old and isn’t used except in select circumstances, SLAB was the
replacement followed by SLUB. Most of the work these days is done on SLUB.
The different allocators are kept around because some people care about the
use cases where one performs better than another. Because of this, the code
is written to make it easy to add a drop in replacement.
I decided to see just how self-contained a new allocator would be.
I started by defining a new Kconfig item in
init/Kconfigto select a new algorithm type.
KMALLOC_SHIFT_HIGHwere needed. I borrowed the definitions from SLAB for the purposes of compiling.
struct kmem_cachehad to be defined in
mm/slab.h1 I ended up just using the same definition as
CONFIG_SLOBplus a node field for some
At this point, the kernel would compile but fail to link. I added stub functions for
kmem_cache_flags, a total of 21 functions.
And that was enough to get the kernel to compile. Obviously this kernel won’t
boot since the stub malloc always returns
Compared to replacing other fundamental parts of the kernel, this was very easy. The code changes needed outside a file that contained a new implementation (or in my case stubs) were fairly small. Does this mean everyone should go out and write a brand new allocator for submission to the community? Almost certainly not. Most work upstream should be on expanding existing allocators. A new allocator would need piles of benchmarking and research to be considered for acceptance, and it would have to be better than what’s there. It’s much better to have one allocator that works for as many cases as possible versus a new allocator for every use case. That doesn’t mean research shouldn’t happen on your own. Writing your own memory allocator is an excellent project for learning that doesn’t need to be submitted to the community. If you’ve never written an allocator before (in user or kernel space) I highly recommend it. Forking off one of the existing allocators and making changes on top can be a great way to compare against a known baseline. Once your changes are validated, they can be submitted to the existing allocator.
In conclusion, kmalloc in the kernel is self contained, so break your kernel by experimenting with it. You might get some ideas that can be turned into a project for existing allocators.
many places such as
slab_common.c and not just the
slabis used to refer to all the types of allocators in ↩