Why the kernel cannot just call malloc()
Back in the Learning-C rung, malloc() was a library call that asked the kernel for heap memory and handed you a clean pointer. But the kernel itself has no library underneath it — it is the bottom. When kernel code needs a buffer for a network packet, a new process control block, or a file's metadata, there is no malloc() to call, because malloc() works by making system calls into the kernel. The kernel has to grow its own memory, from raw physical pages up, and it must do so while running in contexts where it is not even allowed to wait. This section and the next are about that machinery.
Physical memory comes to the kernel in fixed-size pages — usually 4 KiB each. The lowest layer of kernel memory management is therefore a page allocator: give me one page, or four contiguous pages, and I hand back the physical addresses. The dominant design is the buddy allocator. It keeps pages in lists grouped by order: order 0 is one page, order 1 is two contiguous pages, order 2 is four, and so on in powers of two. To satisfy a request it finds the smallest order that fits, and if only a larger block is free it splits that block in half — the two halves are called buddies. When a block is freed, the allocator checks whether its buddy is also free and, if so, coalesces the two back into one larger block. Powers of two make finding a block's buddy a single address calculation, which is why the scheme is fast even under heavy churn.
The buddy allocator deals only in whole pages, but most kernel objects are tiny: a struct might be 96 bytes. Carving a fresh 4 KiB page for a 96-byte object would waste over 97 percent of it, so on top of the buddy allocator sits the slab allocator. A slab is a page (or a few pages) handed up from the buddy allocator and pre-sliced into many same-sized object slots, with a free list threaded through them. Allocating one object is then popping a slot off that list — a handful of instructions, no page-table work, and the object often comes back already in a warm CPU cache line from a recently freed sibling. The slab also caches partially-constructed objects so that reusing one skips re-initialization. This two-level split — buddy for pages, slab for objects — is the backbone of kernel allocation.
kmalloc, vmalloc, and the contexts that forbid sleeping
Kernel code does not poke the slab directly; it calls kmalloc(), which rounds your request up to one of a set of fixed size classes and pulls an object from the matching slab cache. The memory kmalloc() returns is physically contiguous, which matters because some hardware — a DMA engine handing data to a network card — reads physical addresses directly and cannot follow a scattered mapping. The cost is that a large contiguous request can fail outright if physical memory is fragmented, even when plenty of total memory is free. For big allocations that do not need physical contiguity, vmalloc() instead stitches together physically scattered pages and maps them to a contiguous virtual range in the kernel address space — convenient, but it burns page-table entries and pressures the TLB, so kmalloc() stays the default and vmalloc() is reserved for the genuinely large.
Here is the subtle part that the scheduler from guide 4 forces on us. kmalloc() takes a flags argument, and the most common values are GFP_KERNEL and GFP_ATOMIC. GFP_KERNEL says "I am in a context where it is fine to sleep" — if no memory is free, the allocator may block this thread, let the scheduler run something else, and even reclaim memory by writing dirty pages to disk before returning. GFP_ATOMIC says "I must not sleep — give me memory now from an emergency reserve or fail." Choosing wrong is a real bug, and to choose you must know which contexts are allowed to sleep.
The spinlock: a lock that refuses to sleep
That no-sleeping rule is exactly why the kernel needs a lock the user-space rung never required. A mutex, when it cannot acquire, sleeps — and we just saw that sleeping is forbidden in interrupt context. So how does an interrupt handler protect a shared list it shares with the rest of the kernel? With a spinlock. A spinlock that is already held does not put the waiter to sleep; the waiter simply spins — loops, re-reading the lock word with an atomic compare-and-swap — burning CPU until the lock is released. It never calls the scheduler, so it is legal in any context.
Spinning is only sane because the lock is held for a very short time — a few instructions to splice a list node, no I/O, no allocation that might sleep. This dictates an ironclad rule that catches every kernel newcomer: you must never sleep while holding a spinlock. If you grab a spinlock and then call kmalloc() with GFP_KERNEL (which may sleep), the scheduler can park your thread with the lock still held. Now every other CPU that wants that lock spins forever on a holder that is fast asleep — a deadlock that does not show up until the day memory happens to be tight enough for the allocation to actually block. Inside a spinlock you allocate with GFP_ATOMIC or, better, you do not allocate at all.
There is one more twist that ties back to the interrupt mechanism from guide 2. Suppose a normal kernel thread holds a spinlock, and then an interrupt fires on the same CPU whose handler tries to take the same lock. The handler spins, waiting for the thread to release — but that thread is frozen, because the interrupt preempted it and the handler will not return until it gets the lock. The CPU is wedged against itself. The fix is spin_lock_irqsave(): when a lock might also be taken from an interrupt handler, you disable interrupts on this CPU while you hold it, so no handler can fire to create that trap. The kernel makes you spell out, lock by lock, whether interrupts must be masked — a sharp edge the pthreads world simply never has.
Per-CPU data and RCU: avoiding the lock entirely
Every lock costs something even uncontended: the atomic operation that grabs it forces a cache line to bounce between CPUs, and two cores updating counters that merely share a cache line slow each other through false sharing without ever touching the same variable. The kernel's first answer is to remove the sharing: per-CPU data. A statistic like "packets received" becomes not one shared counter but an array with one private slot per CPU. Each CPU bumps only its own slot — no lock, no contention, no bounced cache line — and a reader who wants the total simply sums the slots. As long as the increment is done with preemption disabled so a thread cannot migrate to another CPU mid-update, no synchronization is needed at all.
Per-CPU data works when each CPU owns its own copy, but the kernel is full of structures that are genuinely shared yet read far more often than they are written — routing tables, the list of loaded modules, mount points. For these the kernel reaches for RCU, read-copy-update, and its whole point is that the read side takes no lock and no atomic at all. A reader brackets its access with rcu_read_lock() and rcu_read_unlock(), which on a classic kernel build expand to nothing more than disabling preemption on this CPU — a cheap per-CPU flag, not a lock. Inside, the reader follows pointers at full speed with zero contention.
How can a writer change shared data while lock-free readers walk it? It never edits in place. The writer reads the node, makes a private copy, edits the copy, then updates by atomically swinging one pointer from the old node to the new — so every reader sees either the whole old node or the whole new one, never a half-edited mix. The old node cannot be freed immediately, though: a reader that started before the swing may still be walking it. RCU waits for a grace period — the moment when every CPU has passed through a point where it is provably not inside any read-side section (a context switch, the idle loop, a return to user space). Once each CPU has scheduled once, every prior reader has drained, and only then is free() safe.
WRITER READER (no lock, no atomic) ------------------------------------ ------------------------------- new = copy_of(old); rcu_read_lock(); // disables preempt edit(new); p = rcu_dereference(shared); rcu_assign_pointer(shared, new); use(*p); // old OR new node /* ^ one atomic pointer swing */ rcu_read_unlock(); synchronize_rcu(); /* wait grace */ kfree(old); /* now safe: no reader can still hold old */
The barriers hiding in plain sight
There is one trap in that read side sharp enough to have bitten real kernel developers. The writer fills in the new node's fields before swinging the published pointer. The reader loads the pointer, then dereferences it to read those fields. But on a relaxed CPU like ARM, the reader can see the new pointer value before the new node's field writes have propagated — so it dereferences into a node that is still half garbage. A single plain pointer store does not, by itself, promise that the writer's earlier field writes are visible first; that promise must be requested explicitly.
That is exactly why the API is rcu_assign_pointer() on the write side and rcu_dereference() on the read side, not plain assignments. They embed a memory barrier: the assign is a release store that forces all the field writes out before the pointer; the dereference is the matching acquire load that guarantees a reader seeing the new pointer also sees everything published before it. Together they build the release-acquire ordering that makes publication safe. Omit them and your code passes every test on a strongly-ordered x86, then silently corrupts memory the first day it runs on an ARM phone or server. The hardware's memory model, which felt abstract two rungs ago, is now load-bearing under code that ships to billions of devices.