Here are just some side notes about linux kernel internals I put here to avoid to have to learn same things again and again. Every notes target linux kernel 5.18.12.
There will be a lot of code for which I do not comment the whole part.
Kernel heap management (SLUB, SLAB, SLOB)
Same way as for userland, the kernel has many algorithms to manage memory allocation according to what the kernel is looking for (huge resources or not, safety needs etc).
SLUB
The SLUB algorithm is the algorithm I know the more, so that’s the one I will cover first. To allocate dynamically memory, the kernel provides the kmalloc
function to which you can provide flags:
1 | /** |
What are the main structures of SLUB management ? This can be described by this picture for which we will review each of the data structures (pic from here):
To cover the whole allocation process, we will review the main structures to then take a look at the actual allocation algorithm.
Given the complexity of such structures, each of these structures are treated in separate articles:
Let’s take a look at the source code of the __kmalloc
SLUB implemementation:
1 | // https://elixir.bootlin.com/linux/v5.18.12/source/mm/slub.c#L4399 |
Large allocations
Thus, if the requested size is larger than KMALLOC_MAX_CACHE_SIZE
, kmalloc_large
is called, and kmalloc_order
is called according to a particular order
that represents the number of pages from the requested size:
1 | // https://elixir.bootlin.com/linux/v5.18.12/source/mm/slab_common.c#L944 |
The __GFP_COMP
stands for the allocation of “compound pages”, to quote Jonathan Corbet from this article:
A compound page is simply a grouping of two or more physically contiguous pages into a unit that can, in many ways, be treated as a single, larger page. They are most commonly used to create huge pages, used within hugetlbfs or the transparent huge pages subsystem, but they show up in other contexts as well. Compound pages can serve as anonymous memory or be used as buffers within the kernel; they cannot, however, appear in the page cache, which is only prepared to deal with singleton pages.
The actual allocation is made in alloc_pages
, more specifically in __alloc_pages
that requests pages to the buddy allocator. But that’s out of scope for now. Thus what we know is that large allocations are handled directly by the buddy system.
Small allocations
By following the other code path kmalloc_slab
is called:
1 | // https://elixir.bootlin.com/linux/v5.18.12/source/mm/slab_common.c#L730 |
kmem_cache_init
kmalloc_slab
returns the kmalloc_cache
entry that matchs the provided flags and size. Let’s see how is initialized this array, the main initialization occurs in kmem_cache_init
:
1 | void __init kmem_cache_init(void) |
slab_nodes
is a bitmap representing the nodes used by the kernel. Given we’re on x86-64 the cpu is NUMA but behaves for compatibility purposes like a UMA system. Which means there is only one node used, and in it one “zone”: N_NORMAL_MEMORY
. This way for_each_node_state
loops only one time:
1 | // https://elixir.bootlin.com/linux/latest/source/include/linux/nodemask.h#L482 |
This way slab_nodes
is initialized to 1
.
Then the first two kmem_cache are created: kmem_cache_node
and kmem_cache
:
1 | // https://elixir.bootlin.com/linux/latest/source/mm/slub.c#L4819 |
Let’s take a look at the main functions. But before that, let’s review the internal layout of the kmem_cache
structure.
References
- cdnblogs, Allocation of mm-slab objects
- cdnblogs, Linux Memory Description of Memory Node Node - Linux Memory Management (II)
- programmerSought, Linux Memory Management SLUB Distributor 2 [Kmalloc_Cache Structure]
- dingmos, Linux kernel | Memory management - Slab allocator
- wenqupro, Article about kmem_cache
- cdnblogs, Slub Allocator Learning Series Linux 5.10
- zhuanlan, Non-professional understanding slub
- Birost, Analysis of linux slub allocator
- LWN, The zen of kobjects