Every running program, from a tiny shell script to the kernel itself, needs memory that doesn’t exist until something decides to hand it out. That “something” is a memory allocator, and understanding how allocators work is one of those topics that quietly underlies almost everything else in operating systems. I want to walk through what memory allocators actually are, why the kernel specifically can’t just wing it, and how different allocation strategies fit together into the layered system every modern OS uses.
What a Memory Allocator Actually Does
At the simplest level, a memory allocator is the piece of software responsible for answering two questions:
- “Here’s a chunk of raw memory — who gets to use which part of it, and when?”
- “This memory isn’t needed anymore — how do I make it available again without losing track of what’s free and what isn’t?”
That sounds trivial until you consider the constraints an allocator operates under. It has to be fast, because allocation happens constantly — sometimes millions of times per second across a busy system. It has to avoid wasting memory, because both internal fragmentation (rounding requests up) and external fragmentation (scattering free memory into unusable gaps) directly reduce how much useful work a system can do. And in a multi-core, multi-threaded environment, it has to avoid becoming a bottleneck where every CPU is stuck waiting on the same lock just to get a few bytes.
Why the Kernel Specifically Needs Sophisticated Allocators
User-space programs get memory from allocators too — malloc() in C, garbage-collected heaps in Java or Python, and so on — but the kernel’s situation is different in a few important ways.
The kernel can’t fail gracefully as often as user space. If your browser fails to allocate memory, it might crash or show an error. If the kernel fails to allocate memory for a critical data structure while handling an interrupt, you can be looking at a system-wide freeze or crash. Kernel allocators are built with this asymmetry in mind — certain allocation paths (like those used in interrupt context) are restricted to non-blocking behavior specifically because sleeping to wait for memory simply isn’t an option there.
The kernel manages memory for everyone else. Every process’s page tables, every open file’s struct file, every network packet’s socket buffer, every mounted filesystem’s inode and dentry cache — all of that lives in kernel memory, allocated and freed constantly as the system does ordinary work. The volume and diversity of allocation sizes the kernel handles is enormous compared to a typical user application.
The kernel operates directly on physical memory. User-space allocators work within a process’s virtual address space and ultimately ask the kernel for more via brk()/mmap(). The kernel’s allocators are one layer deeper — they’re the ones deciding how actual physical page frames get sliced up and handed out, including to those very user-space allocators.
The Layered Allocator Stack in Linux
Linux doesn’t use one allocator for everything; it uses a stack of allocators, each suited to a different granularity of request.
+-------------------------------------------------------+
| kmalloc() / kmem_cache_alloc() <- small objects |
| (SLUB, historically SLAB/SLOB) |
+-------------------------------------------------------+
| Buddy allocator (page-granularity) |
+-------------------------------------------------------+
| Physical page frames (RAM) |
+-------------------------------------------------------+
The buddy allocator sits at the bottom, managing memory in power-of-two page groups (order 0 = 1 page, order 1 = 2 pages, order 2 = 4 pages, and so on up to MAX_ORDER). Its “buddy” name comes from how it splits and merges blocks: when a block is freed, the allocator checks whether its “buddy” block (the matching block that would combine with it into the next larger power-of-two size) is also free, and if so, merges them back together. This keeps large contiguous regions available and directly fights external fragmentation at the page level.
The slab-family allocators (SLUB today, historically SLAB and SLOB) sit above the buddy allocator, requesting whole pages from it and then subdividing those pages into much smaller, fixed-size objects — the kind of memory most kernel data structures actually need (tens to a few hundred bytes, not whole 4KB pages).
vmalloc() is a separate mechanism for when you need a large, contiguous virtual range that doesn’t have to be physically contiguous — useful for large buffers where physical contiguity isn’t required but a large virtually-contiguous mapping is convenient.
Why Fragmentation Is the Central Design Problem
Almost every allocator design decision traces back to managing fragmentation, so it’s worth being precise about what’s at stake:
- Internal fragmentation wastes memory that’s technically allocated but never used by anyone, because the allocator rounded a request up to a convenient size.
- External fragmentation wastes memory that’s technically free but can’t be used because it’s scattered into pieces too small or misaligned for the next request.
A naive allocator can solve one at the direct expense of the other. Round every request up to a huge fixed block size, and internal fragmentation gets terrible but external fragmentation nearly vanishes. Pack every request as tightly as possible with no rounding, and internal fragmentation nearly vanishes while external fragmentation, over time, gets worse. Good allocator design — SLUB’s size-class tiers, the buddy system’s splitting/merging — is fundamentally about finding a workable middle ground for a given workload’s typical allocation pattern.
Speed and Concurrency Matter Just As Much
On modern multi-core hardware, an allocator that’s memory-efficient but requires a global lock on every allocation will bottleneck the whole system the moment more than a handful of cores are allocating simultaneously. This is precisely why SLUB’s design emphasizes per-CPU “current slab” fast paths with largely lock-free operations — allocation speed and multi-core scalability are just as central to allocator design as raw fragmentation numbers.
Allocators Across Operating Systems
This isn’t unique to Linux. Every general-purpose kernel deals with the same fundamental tension, with its own flavor of solution:
- Windows uses the Executive Pool Allocator for kernel-mode allocations, split into paged and non-paged pools, with its own lookaside-list fast-path caching conceptually similar in spirit to SLUB’s per-CPU slabs.
- macOS and iOS, built on the XNU kernel, use a zone allocator (
zalloc) for fixed-size kernel objects, again a close cousin conceptually to the slab family. - Android, running a modified Linux kernel, inherits SLUB directly, though user-space allocators like Scudo (a hardened allocator) handle app-level memory with additional security mitigations layered on top.
- Classic UNIX systems (Solaris in particular) are actually where the original slab allocator concept was born, in Jeff Bonwick’s 1994 paper, before Linux adopted and adapted the idea.
Real-World Consequences of Allocator Behavior
This isn’t abstract. A poorly performing allocator, or one poorly suited to a workload, shows up as very concrete problems:
- A database server doing millions of small object allocations per second can be meaningfully bottlenecked by lock contention in a naive allocator — this is a big part of why per-CPU caching designs exist.
- An embedded router with 8MB of RAM can genuinely run out of usable memory well before
freereports zero available bytes, purely due to external fragmentation, if it’s using an allocator (or is being asked to allocate patterns) poorly suited to its memory budget. - A long-running server process with a slow memory leak can be mistaken for “just fragmentation” if nobody checks
/proc/slabinfoand/proc/buddyinfoto distinguish reclaimable slab growth from genuinely pinned, leaked objects.
Troubleshooting Allocator-Related Issues
- Distinguish user-space from kernel-space memory pressure first —
free -m,/proc/meminfo‘sSlab:line, andslabtopwill tell you whether kernel allocators are the culprit. - Check
/proc/buddyinfofor page-level fragmentation (few high-order blocks available signals real trouble for anything needing large contiguous allocations, like huge network buffers or hugepages). - Use
slabtopto identify which specific kernel cache is growing unexpectedly. - For user-space leaks, tools like
valgrind,AddressSanitizer, orheaptrackare the equivalent of what KASAN gives you in kernel space.
Best Practices
- Don’t hand-roll a custom allocator unless profiling has proven the general-purpose one is actually the bottleneck — modern allocators like SLUB are the product of decades of tuning.
- Match allocation patterns to allocator strengths: batch small fixed-size allocations through dedicated caches (
kmem_cache_create()in kernel code) rather than generickmalloc()calls in hot loops. - Monitor fragmentation over realistic uptimes, not just fresh boots — fragmentation is a function of accumulated allocation history, not a static property.
Summary
Memory allocators are the unglamorous but absolutely load-bearing infrastructure underneath every piece of software that touches memory, and the kernel’s allocators carry an especially heavy burden because they serve every other subsystem, often under strict constraints on blocking and failure. Linux’s layered approach — buddy allocator for pages, slab-family allocators for smaller objects — reflects a genuinely elegant division of labor, where each layer is tuned to solve the fragmentation and concurrency problems at its own scale. Every OS you’ve used, from Windows to macOS to the UNIX systems that started it all, is solving essentially the same problem with its own architecture-specific answer.
FAQs
What is the difference between the buddy allocator and slab allocators? The buddy allocator manages memory at page granularity (4KB and multiples thereof via power-of-two blocks), while slab allocators like SLUB subdivide pages obtained from the buddy allocator into much smaller, fixed-size objects for typical kernel data structures.
Why can’t the kernel just use malloc() like user-space programs? The kernel operates directly on physical memory, has strict non-blocking requirements in certain contexts (like interrupt handlers), and needs to serve an enormous diversity of allocation sizes and patterns across every subsystem — requirements a general user-space allocator isn’t designed around.
What’s the biggest cause of fragmentation in kernel memory? A mix of internal fragmentation (allocations rounded up to fixed size classes) and external fragmentation (free memory scattered into unusable gaps from mixed allocation/free patterns over time).
Do other operating systems face the same allocator challenges as Linux? Yes — Windows, macOS/iOS, and other UNIX-derived systems all use conceptually similar layered allocator designs (pool allocators, zone allocators) to solve the same fragmentation and concurrency problems.
References
- Bonwick, J., “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” USENIX 1994
- Linux kernel documentation,
Documentation/mm/directory (kernel.org) - Love, R., Linux Kernel Development, chapters on memory management
- Microsoft Docs, “Memory Pools” (Windows Driver Kit documentation)