Linux Kernel Programming
Who Are We?
Lehr- und Forschungsgebiet Betriebssysteme
Operating Systems Research and Teaching Unit
Faculty
- Prof. Redha Gouicem
Administration
- Claudia Graf
Researchers
- Jérôme Coquisart, M.Sc.
- Mostafa Hadizadeh, M.Sc.
Research assistants - Tutors (HiWi)
- 16 people, both bachelor and master students
Where Can You Find Us?
Our offices are in the UMIC building, 2nd floor
Website: https://os.rwth-aachen.de
Teaching Curriculum
Past/current theses examples
- Multi-Processing Support for Unikernels (M.Sc.)
- Understanding the Performance Impact of Security Mitigations in the Linux Kernel (B.Sc.)
- Automatic Caching for Cloud Object Storage Systems (B.Sc.)
- Automatic Detection and Mitigation of Page Reclamation Overhead (M.Sc.)
- Design and Implementation of an Evaluation Framework for a NUMA-Aware Page Cache (B.Sc.)
- Evaluating Memory Prefetching Policies in Linux Systems (B.Sc.)
- Implement Support for Instructions in the Front-End of a Hybrid Binary Translator (B.Sc.)
- Implement a Shared Page Cache in a Virtualised Environment (B.Sc./M.Sc.)
- Impact of State-of-the-Art Page Table Replication Schemes on the Efficiency of NUMA Systems (B.Sc./M.Sc.)
- Evaluation and Improvement for NUMA Kernel Text Replication (B.Sc./M.Sc.)
Lecture Live Q&A
During lectures, you can ask questions directly by raising your hand, or through an online Q&A tool:
Link: Claper room
Operating System and Kernel
In this course, we will use the following definitions:
Definition
The operating system is the set of software components that enables applications to use the underlying hardware and provides APIs to ease development.
Definition
The kernel is the set of components of the operating system that are executed in a privileged mode, usually in supervisor mode.
Monolithic Kernels
A monolithic kernel embeds all the system functionalities in a single binary. It contains all the core features of an operating system (scheduling, memory management, etc…) as well as drivers for devices or less essential components.
Characteristics
- Defines a high level interface through system calls
- Good performance when kernel components communicate (regular function calls in kernel space)
- Limited safety: if one kernel component crashes, the whole system crashes
Examples
- Unix family: BSD, Solaris
- Unix-like: Linux
- DOS: MS-DOS
- Critical embedded systems: Cisco IOS
Why ‘monolithic’?
Monolithic means it is built as a single binary and runs in the same address space. The source code can still be organised in a modular way (e.g., using libraries).
Modularity
Some monolithic kernels allow dynamic code loading as modules, e.g., for drivers. These are usually called modular monolithic kernels.
Microkernels
A microkernel contains only the minimal set of features needed in kernel space:
address-space management, basic scheduling and basic inter-process communication.
All other services are pushed in user space as servers:
file systems, device drivers, high level interfaces, etc.
Characteristics
- Small memory footprint, making it a good choice for embedded systems
- Enhanced safety: when a user space server crashes, it does not crash the whole system
- Adaptability: servers can be replaced/updated easily, without rebooting
- Limited performance: IPCs are costly and numerous in such an architecture
Examples
- Minix
- L4 family: seL4, OKL4, sepOS
- Mach
- Zircon
Hybrid Microkernels
The hybrid kernel architecture sits between monolithic kernels and microkernels.
It is a monolithic kernel where some components have been moved out of kernel space as servers running in user space.
While the structure is similar microkernels, i.e., using user servers, hybrid kernels do not provide the same safety guarantees as most components still run in the kernel.
Controversial architecture
This architecture’s existence is controversial, as some just define it as a stripped down monolithic kernel.
Examples
- Windows NT
- XNU (Mach + BSD)
Unikernels
A unikernel, or library operating system, embeds all the software in supervisor mode.
The kernel as well as all user applications run in the same privileged mode.
It is used to build single application operating systems, embedding only the necessary set of applications in a minimal image.
Characteristics
- High peformance: system calls become regular function calls and no copies between user and kernel spaces
- Security: attack surface is minimized, easier to harden
- Usability: hard to build unikernels due to lack of features supported
Examples
- Unikraft
- clickOS
- IncludeOS
Comparison Between Kernel Architectures
The choice of architecture has various impacts on performance, safety and interfaces:
- Switching modes is costly: minimizing mode switches improves performance
- Supervisor mode is not safe: minimizing code in supervisor mode improves safety and reliability
- High level interfaces for programmers are in different locations depending on the architecture
i.e., in the kernel for monolithic, but in libraries or servers for microkernels
In this course, we will focus on a monolithic modular kernel: Linux.
Timeline of Unix Systems
Source: https://en.wikipedia.org/wiki/History_of_Unix
Linux Kernel Map
Structures in Memory
A structure is a collection of one or more variables.
struct version {
unsigned short major; // usually 2 bytes
unsigned long minor; // usually 8 bytes
char flags; // 1 byte
};Memory alignment
A memory access is aligned if the accessed address is a multiple of the size of the access.
Example: an access to an unsigned long is aligned if the address is a multiple of 8 bytes.
Ordering and Padding
The only guarantee in the C language is the order of the members! The compiler can add padding between members for performance reasons.
Generic Data Structures in C
Instead of having objects in a list, we have the list in the objects!
The “naive” version:
Not generic! You need one list type of list per object type.
When you iterate over the list, how do you get the containing object?
Container of
From the address of any member in a structure, how can we get the address of the structure?
e.g., from the address of a list_head element in a structure
Linux implements the container_of macro!
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
* WARNING: any const qualifier of @ptr is lost.
*/
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
static_assert(__same_type(*(ptr), ((type *)0)->member) || \
__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })After expanding all macros, this looks like this:
#define offset_of(type, member) \
(&((type *)0)->member)
#define container_of(ptr, type, member) \
((type *)(((void *)ptr - offset_of(type, member))))offset_of: cast the address0totype *and access the membercontainer_of: substract this offset from the address of the member
Overview
In monolithic architectures, kernel and user programs are run in different permission levels:
supervisor mode and user mode.
There needs to be communication between the user and the kernel.
Multiple mechanisms are available in the Linux kernel, and choosing the right one is a common discussion on the mailing list.
Communication mechanisms:
- Module parameters
- Pseudo file systems
- Sockets
- System Calls
- ioctl
System Calls
System calls are the most classic user-kernel communication mechanism.
They allow user space applications to execute privileged kernel code:
- I/Os (disk, network)
- Resource management (threads, memory)
- Communication (signals, IPCs)
- Access to specific hardware
They are the core API of the kernel, with some limitations:
- Each system call is identified by a number defined at kernel compile time. You cannot add new ones dynamically.
- They are a “universal” API, so they need to be the same on all systems. 1
There are two ways of making system calls:
- The “old” interrupt way (x86)
- The “new”
syscallinstruction way (x86, amd64, ARM64)
System Calls: The Interrupt Way
System calls are a software interrupt like the others:
1. Place the system call number in a register
2. Place the arguments in the proper registers and/or on the stack
3. Trigger the “system call” interrupt (switching to supervisor mode)
4. Jump to the “system call” interrupt handler
5. Load the system call table and jump to the index given by the syscall number
6. Execute the system call handler
7. Return the result to user space (switching back to user mode)
System Calls: The Instruction Way
Some architectures provide a specific instruction (syscall, svc, sysenter, …):
1. Place the system call number in a register
2. Place the arguments in the proper registers and/or on the stack
3. Use the system call instruction (switching to supervisor mode)
4. Jump to the index given by the syscall number in the syscall table
5. Execute the system call handler
6. Return the result to user space (switching back to user mode)
One level of indirection is bypassed!
Tip
You can find a very detailed (with less omissions) explanation of how system calls work in Linux here!
Page Frame Allocation
You might have noticed that most of the memory API works at the page granularity.
There are multiple levels of allocators:
- User space allocators that allocate objects of arbitrary sizes, request memory from the kernel
e.g., glibc malloc, jemalloc, more implementations here - Kernel space object allocators that allocate objects of arbitrary sizes, request page frames
- Page frame allocator that allocates page frames from the physical memory
The page frame allocator is responsible for managing the physical memory, giving page frames to allocators upon request, and reclaiming them when freed.
Page order
You might have also noticed that the page granularity API uses orders (powers of two) for allocations:
struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
Orders come from the inner working of the page frame allocator of Linux: the buddy allocator.
Buddy Allocator
Linux uses the buddy allocator to manage physical page frame allocation.
Initially, physical memory is seen as a single large chunk containing all page frames, e.g., \(2^8 = 256\) pages.
Allocation:
- The allocation size is rounded to the next power of 2, i.e., the order
- A chunk of the closest size is repeatedly split in half until it reaches the order size
Two chunks split from the same parent are called buddies - The resulting chunk is allocated
If a chunk of the correct size is available, it is directly chosen
Free:
- The freed chunk is tagged as free
- If two buddies are free, they are merged back into a larger chunk
If two neighbors are free but not buddies, they cannot be merged!
Buddy Allocator: Linux Implementation
Linux implements the buddy allocator with an array of free lists, indexed by order.
Examples:
alloc_pages(GFP_KERNEL, 3);- Look up the list of order 3 for a free chunk
- A chunk is available, remove it from the free list and return it to the caller
alloc_pages(GFP_KERNEL, 4);- Look up the list of order 4 for a free chunk
- No chunk of order 4 available, look up for a higher order free chunk
- A chunk of order 5 is available: split it, choose one chunk for allocation and put the other in the order 4 free list
When freeing a chunk of size order, it is added back its free list.
The kernel also maintains bitmaps to identify buddies: if both buddies are free, they are merged and stored in the order + 1 list.
User interface via procfs
You can check the state of your buddy allocator by reading the /proc/buddyinfo file.
Object Allocators
The page frame allocator works at the page granularity.
This is not convenient for most allocations that request memory for smaller objects!
Object allocators act as a layer between the page allocator and subsystems to allocate smaller chunks of memory. They allocate pages, and “redistribute” smaller chunks to subsystems that allocate memory through them.
For example, when using kmalloc(), you are using an object allocator, not directly allocating pages.
Linux has multiple object allocation layers (you can even implement your own), but we will see the main one: the slab layer.
The Slab Layer
Allocating and freeing objects is extremely frequent, so it’s a good idea to have some sort of caching mechanism.
In Linux, this caching mechanism is called the slab layer.
The slab layer allows you to create caches, each of which contains a certain type of objects, e.g., struct task_struct or struct inode.
Each cache is then divided into slabs, blocks of contiguous memory that contain a certain number of instances of the object stored by this cache.
A slab contains the actual data and maintains their status (used or free).
When a slab is full, the slab layer will allocate a new one for this cache.
When the system wants to reclaim memory, empty slabs will be freed.
Note
Additionally, allocations are done at the page granularity, so for smaller objects, you would need manual management to not waste memory.
SLAB Allocator
Added in Linux in 1996, implements work from Sun Microsystems in SunOS 5.41
Cache friendly
- Queues to track per-cpu and per-node data
- Page coloring to enforce cache locations
NUMA aware
- Per-node slabs, allocation are done on the local node by default
- Other policies can be used depending on the objects stored
Design: Page frame layout
Metadata of each slab can be embedded in the slab itself:
- freelist contains the indexes of the free objects in this slab. It has as many entries as the number of objects that can be stored in the page frame
- padding aligns the objects properly
Note
Multiple allocations can be done by only touching one cache line (the one with the freelist). No need to touch the actual objects.
SLAB Allocator (2)
Design: Data structures
Partial description, see their real definitions for more details
struct kmem_cache {
struct array_cache __percpu *cpu_cache;
unsigned int size;
int object_size;
struct kmem_cache_node *node[MAX_NUMNODES];
};struct kmem_cache_node {
struct list_head slabs_partial; // slabs with free objects
struct list_head slabs_full; // full slabs
struct list_head slabs_free; // empty slabs
/* some counters, locks, and pointers to array_caches */
};struct array_cache {
unsigned int avail; // number of active entries
unsigned int limit; // max number of entries
void *entry[]; // LIFO array of free elements
};struct slab {
/* metadata */
struct kmem_cache *slab_cache;
struct list_head slab_list;
void *freelist;
void *s_mem;
/* ... */
/* actual data, containing the page frame layout shown here*/
};Frame layout:
Object layout:
SLUB Allocator
Introduced in 2007. The idea is to simplify the implementation, with less queues.
Locality by having per-cpu slabs, still NUMA aware
struct kmem_cache {
struct kmem_cache_cpu __percpu *cpu_slab;
unsigned int size;
unsigned int object size;
struct kmem_cache_node *node[MAX_NUMNODES];
};struct kmem_cache_node {
unsigned long nr_partial;
struct list_head partial;
};struct kmem_cache_cpu {
void **freelist;
struct slab *slab;
};struct slab {
struct kmem_cache *slab_cache;
struct list_head slab_list;
void *freelist;
unsigned long counters; // nr_objects, nr_inuse
};Frame layout:
Object layout:
Page Frame Reclamation
Linux tries to keep a pool of available free pages to ensure future allocations won’t fail (most likely).
Pages can be of one of four types:
- Unreclaimable: Cannot be swapped out and reclaimed, e.g., kernel stacks, locked pages
- Swappable: Can be swapped out and reclaimed, e.g., anonymous pages, shared memory
- Syncable: Cached disk data that might need to be synced before reclamation if dirty, i.e., page cache
- Discardable: Unused pages that can be immediately reclaimed, e.g., unused pages in kernel slab allocators
Page reclamation is performed on two occasions:
- During an allocation, when the amount of free pages drops below the low watermark, the
kswapddaemon is asynchrounously woken up to reclaim pages - During an allocation, when the amount of free pages drops below the min watermark, a direct reclamation is synchronously performed
PFRA: Two-List Strategy
The PFRA maintains two lists: the active and the inactive lists.
The active list contains recently accessed pages, while the inactive list contains the pages that were not accessed recently.
In other words, the active list contains the current working set of the system.
When a page is accessed for the first time, it is added in the inactive list, with a referenced bit set to 0.
Periodically, the PFRA scans the lists:
- When a page is accessed, its referenced bit is set to 1 by the MMU (used)
- If an inactive page’s referenced bit is 1 during the scan, the page is moved to the active list (used)
- Periodically (after multiple scans), referenced bits are cleared (timeout)
- If an active page’s referenced bit is 0, the page is moved to the inactive list (refill)
- If the active list is too long, pages can be moved to the inactive list (refill)
Lengths of lists
The PFRA tries to balance the length of the active and inactive list through a ratio. By default, Linux is usually tuned to have an active list at most two thirds of the page cache’s size.
The Virtual File System Abstraction
Dentry Cache
Dentries are cached into a hash table for fast lookup.
This cache is declared as static struct hlist_bl_head *dentry_hashtable in fs/dcache.c.
Spoiler alert!
No more details here, you will have to work with that cache in the next lab.
In particular, you will have to find out:
- the dentry cache size (number of buckets)
- how the hash table is implemented
- what are negative dentries used for
Back to the VFS
Now, let’s go back to our layers, and more specifically how the VFS glues all this together
Relations Between VFS Objects
Relations Between VFS Objects and the Page Cache
The xarray in the address_space may contain folios instead of pages depending on the file system. We won’t go into more details on this, but if you want to have a look, you can check the kernel documentation/online resources.
Relations Between VFS Objects (Super Block Edition)
File system in User SpacE
Another way of implementing a file system in Linux is through the File system in User SpacE (FUSE) API.
With FUSE, you can implement everything in user space and register your FUSE file system with the kernel.
The VFS will then redirect system calls targeting your file system to your code in user space, which in turn may use the underlying “real” file system.
Performance
The amount of round trips between user and kernel modes greatly impacts the performance of FUSE-based file systems.
FUSE Passthrough
Since 6.9, the FUSE subsystem supports a passthrough feature to avoid mode switches.
It allows the FUSE driver to directly communicate with other file systems for read/write operations, without going back to the user space FUSE daemon.
Ptrace – Process tracer
The system call ptrace allows a thread (the tracer) to observe and control the execution of another thread (the tracee).
long ptrace(enum __ptrace_request request, pid_t pid, void *addr, void *data);The tracer sends commands (requests) to observe or modify the behavior of the tracee, and the tracee is stopped on events specified by the tracer.
Some commands:
PTRACE_ATTACH/PTRACE_SEIZE: trace the specified thread.PTRACE_TRACEME: used by a tracee to ask its parent to trace it.PTRACE_GETREGS/PTRACE_SETREGS: get/set the registers of the tracee.PTRACE_GETSIGINFO/PTRACE_SETSIGINFO: get/set the information about the signal that caused the tracee to stop.PTRACE_CONT: make a stopped tracee resume its execution.PTRACE_SYSCALL: same asPTRACE_CONT, but also makes the tracee stop at the next syscall entry/exit.PTRACE_SINGLESTEP: same asPTRACE_CONT, but also makes the tracee stop after executing one instruction.
Ftrace – User front ends
In practice, you most likely will use a front-end tool instead of directly configuring ftrace.
- perf can use ftrace for some of its features
- trace-cmd is a CLI tool from the ftrace developers (https://www.trace-cmd.org/)
- Control the ftrace file system interface
- Display the trace, statistics, etc.
- KernelShark is a GUI tool from the ftrace developers to visualize traces
![]()
Ftrace – Kernel perspective
Most features of ftrace boil down to hooking callbacks before/after a function is called.
When ftrace is enabled in a kernel, the compiler adds noop instructions before and after every function of the kernel.
These instructions can then be patched at run time as calls to callbacks.
These callbacks can trigger the tracers previously presented (function, function graph, etc.) or call arbitrary functions in kernel space.
This is an overly simplified explanation of what is happening!
Check out this amazing (and very very technical) talk from the main ftrace developer, Steven Rostedt:
ftrace: Where modifying a running kernel all started – Kernel Recipes 2019
eBPF – A virtual machine in the kernel
eBPF (extended Berkeley Packet Filter) is a managed runtime environment embedded in the kernel.
It defines an instruction set (bytecode), data structures (maps), primitives, as well as a run time infrastructure to execute eBPF programs.
eBPF – Writing eBPF programs
There are multiple ways of writing eBPF programs:
- Directly write eBPF bytecode
Cumbersome, don’t do that - bcc (BPF Compiler Collection)
Toolkit to generate eBPF programs for the kernel in C, with Python and lua front-ends.
![]()
