Kernel Architecture & OS Internals Questions

The problem. The kernel cannot call a C library malloc; it is the thing that hands out memory. It needs memory for its own data (process descriptors, file and network structures, buffers) in sizes from a few dozen bytes to megabytes, often from contexts that must not sleep. Two layers solve this: a page-level allocator underneath and an object-level allocator on top.

Layer 1: the buddy allocator (whole pages). Physical memory is divided into pages (4 KiB on x86-64). The buddy allocator tracks free memory as blocks of 2^order contiguous pages: order 0 is one page, order 3 is eight pages (32 KiB), and so on. To allocate an order-3 block, it takes a free order-3 block, or splits an order-4 block into two order-3 'buddies', using one and keeping the other free. When a block is freed, if its buddy (the adjacent same-size block) is also free, the two merge into the next order. Splitting and merging makes both operations fast and keeps contiguous space available as long as frees are not scattered.

A traced example: suppose the only free memory is one order-4 block (16 pages). Allocating one page (order 0) splits order 4 into two order-3 blocks (keep one free, split the other), that into two order-2 blocks, then two order-1, then two order-0. The free lists now hold one block each of order 3, 2, 1 and 0, which is 8 + 4 + 2 + 1 = 15 pages, plus the 1 page handed out, 16 in all. Freeing that page makes it merge with its free order-0 buddy, then order 1 with its buddy, order 2 with its, and order 3 with its, ending as the single order-4 block again. If instead a stray long-lived allocation sat in one of those pages, the merge would stop there and no order-4 block could be rebuilt: that is fragmentation.

Layer 2: the slab family (small objects). Asking the buddy allocator for a 4 KiB page to hold a 200-byte object wastes most of it. A slab allocator (SLUB is the Linux implementation) takes pages from the buddy allocator and carves each into many equal-size objects. A cache (a kmem_cache) serves one object type or size: for example one cache for a process descriptor, one for file metadata. Benefits: no per-object page waste, objects of one type packed together, freed objects are reused quickly (warm in cache) typically from per-CPU free lists (a private list of free objects for each CPU, so taking one needs no shared lock) with little locking, and a type's memory can be tracked and reclaimed separately. 'The slab family' means the allocator implementations that share this model (the kernel documentation for monitoring caches describes the SLUB implementation).

kmalloc vs vmalloc

How fragmentation shows up

• External fragmentation: plenty of free pages, but scattered, so no free block of the needed order exists. /proc/buddyinfo prints the count of free blocks at each order per zone; a healthy host has nonzero counts in the high columns, a fragmented one has large counts in the first columns and zeros at the end. Illustrative output in the format of /proc/buddyinfo (the counts are invented for this example and the small DMA zone's row is omitted; a real machine will differ):

Node 0, zone    DMA32      1      0      1      1      1      2      2      1      1      1    500 
Node 0, zone   Normal     86    619   7301  11504   5665   3437   2113   1324    739    516   1873 

Each row is a zone; the 11 numbers are counts of free blocks of order 0 through 10 (order 10 = 1,024 pages = 4 MiB). The Normal zone has 1,873 free 4 MiB blocks, so a large contiguous request succeeds: this is a healthy host. The free memory in a column is count x 2^order x 4 KiB, for example order 5 is 3,437 x 32 pages x 4 KiB = 429.6 MiB, and the Normal row's columns together come to about 11,716 MiB (the DMA32 row's 500 order-10 blocks add about 2,000 MiB more). A fragmented host with the same total would show most of that memory in the left columns and 0 in the right ones, so a request for order 8 or above would fail or force compaction even though free reports gigabytes. Symptoms: allocation failures or stalls for high-order requests, transparent huge page fallbacks, compact_stall counts rising in /proc/vmstat. The fix is to avoid high-order allocations (use kvmalloc or scatter-gather) and let compaction (moving pages to join free space) run.

• Internal fragmentation: waste inside the allocation. A kmalloc request is rounded up to its size class, and slab pages can be mostly empty (a few live objects pin a whole page). /proc/slabinfo (which needs root) shows active versus total objects per cache. Its columns are name active_objs num_objs objsize objperslab pagesperslab. An illustrative dentry row (dentries are the kernel's cached directory entries, mapping path names to files): dentry 50000 100000 192 21 1 ... means 100,000 object slots of 192 bytes held in memory (100,000 x 192 B = 18.3 MiB) of which only 50,000 are in use (9.2 MiB), so half the cache's memory is unused slack that only frees when whole slab pages empty out; /proc/meminfo splits Slab into SReclaimable (caches that can be dropped under pressure) and SUnreclaim (cannot).
  Why it hurts: a slab page cannot return to the buddy allocator until every object in it is freed, so long-lived stragglers keep memory unavailable for large requests even though 'free memory' looks fine.

Closing example: a high-performance network stack. Receive and transmit paths allocate and free a packet buffer descriptor millions of times per second, often from interrupt or softirq context where sleeping is forbidden. This is exactly what dedicated slab caches with per-CPU free lists and non-sleeping flags are for; designs on top of this typically recycle buffers instead of freeing them, so the hot path avoids the allocator altogether. The cost of getting it wrong is visible as GFP_ATOMIC failures under bursts, which the stack answers by dropping packets. Concretely: at 1 million packets per second, a 1 ms burst needs about 1,000 buffer descriptors from non-sleeping allocations; if the per-CPU lists and reserves hold fewer, the rest are dropped and the drop counters rise.

Direct answer

A loadable kernel module is a piece of kernel code compiled separately as a .ko file (an ELF object, ELF being the standard Linux executable and object file format) that can be inserted into and removed from a running kernel with insmod, modprobe and rmmod. Once loaded it is part of the kernel: same privilege, same address space, same crash domain. Code built into the kernel image (=y in the configuration) is always present from boot; a module (=m) is loaded on demand. A kernel is "tainted" when something has happened that makes its behaviour harder to trust or debug, such as loading a proprietary, out-of-tree or unsigned module; the state is a bitmask (one number whose individual binary digits are separate yes/no flags) readable from /proc/sys/kernel/tainted, and a nonzero value tells maintainers to be cautious with bug reports. Third-party modules carry stability risk (a bug panics the whole machine) and security risk (a malicious module is a rootkit (software that hides an intruder's presence) with full power), which signing and policy are meant to control.

Module versus built-in

The kernel has no stable internal interface, so a module must be built against the exact kernel (or compatible headers) it will run on: the module records a version string and, with CONFIG_MODVERSIONS, checksums of the kernel symbols it uses. That is why out-of-tree drivers are rebuilt by tools such as DKMS (Dynamic Kernel Module Support, which recompiles registered modules automatically when a new kernel is installed) on every kernel update. Modules can only use symbols the kernel exports; some are exported to GPL-compatible modules only, so a module without a GPL-compatible MODULE_LICENSE is treated as proprietary.

How loading happens: the loading process calls finit_module (or init_module), a system call that requires the CAP_SYS_MODULE capability (the Linux privilege bit that permits loading kernel modules, normally held only by root). The kernel loads the ELF image into kernel memory, resolves its symbols, checks the signature if enforcement is on, and runs its init function. At boot, modules come in three ways: from the initramfs (the early root image carrying the storage and filesystem drivers needed to mount the real root), from udev (the device manager daemon) loading by hardware alias (an identifier string a device advertises, matched to a module) when a device is discovered, and from lists in /etc/modules-load.d. Automatic loading can be suppressed with a modprobe blacklist or the modprobe.blacklist= boot parameter, but both are read by user-space modprobe, and a blacklist entry only makes modprobe ignore the module's internal hardware aliases (so alias-based loading by udev skips it): an explicit modprobe name or insmod can still load it. To refuse a module outright, use the kernel's own module_blacklist= boot parameter (read by the kernel itself: a comma-separated list of module names that the load path then rejects, whichever tool asked), or an install name /bin/false line in a modprobe.d file for loads that go through modprobe.

What taint means

Each cause sets a bit; the kernel documentation lists the flags. The ones that matter for modules are bit 0 (letter P, a proprietary module was loaded), bit 1 (F, a module was force-loaded), bit 12 (O, an externally built "out-of-tree" module was loaded) and bit 13 (E, an unsigned module was loaded); bit 7 (D) means the kernel has oopsed (hit a recoverable internal error and printed an "oops" report, as with a bad pointer dereference), and bit 9 (W) means it issued a warning. Decoding a value by hand:

$12289 = 8192 + 4096 + 1 = 2^{13} + 2^{12} + 2^{0}$

so bits 13, 12 and 0 are set: unsigned (E), out-of-tree (O) and proprietary (P). As a program:

FLAGS = {0: "P proprietary module loaded", 12: "O out-of-tree module loaded", 13: "E unsigned module loaded",
         1: "F module force-loaded", 7: "D kernel oopsed or BUG hit", 9: "W kernel warning issued"}

def decode(value):
    return [FLAGS.get(b, f"bit {b}") for b in range(19) if value >> b & 1]

for v in (0, 4097, 12289):
    print(v, decode(v))
print(2**13 + 2**12 + 2**0)

Output:

0 []
4097 ['P proprietary module loaded', 'O out-of-tree module loaded']
12289 ['P proprietary module loaded', 'O out-of-tree module loaded', 'E unsigned module loaded']
12289

Taint is sticky: it stays until reboot even after the module is unloaded, because the damage a bad module could have done to kernel memory does not go away. Upstream developers generally treat reports from kernels tainted by proprietary modules with suspicion because they cannot inspect that code. Taint is information, not a block: the kernel keeps running.

Stability and security consequences

The two risks call for different controls: stability comes from where the module came from and how it is tested; security comes from signing, the one-way sysctl and who holds CAP_SYS_MODULE. The bullets below follow that split.

• Stability. There is no isolation. A null pointer or a missed lock in a third-party module can corrupt any kernel structure or panic the machine, and the fault can show up far from the cause. A module also ties you to a kernel version: every kernel upgrade means a rebuild and a test, and a GPU or storage driver that lags a release blocks the upgrade.
• Security. A loaded module runs at the highest privilege and can hide processes, hook system calls or read any memory, which is how kernel rootkits work. Controls: module signing (CONFIG_MODULE_SIG; without CONFIG_MODULE_SIG_FORCE or the module.sig_enforce=1 boot parameter an unsigned module still loads but taints the kernel with E, with enforcement only validly signed modules load); the sysctl kernel.modules_disabled=1, which is one-way: after it is set, modules can be neither loaded nor unloaded until reboot; and restricting who holds CAP_SYS_MODULE.
• Secure Boot. Secure Boot verifies the bootloader and kernel signature, and distribution kernels commonly extend that by refusing unsigned modules while it is on. To run a third-party driver such as an out-of-tree GPU or virtualization module you then sign it with your own key and enrol that key with the firmware's machine-owner-key (MOK) mechanism, using the mokutil tool to queue the key for enrolment at the next boot, rather than disabling Secure Boot.

Recommendation

Prefer drivers that are in the mainline kernel, load only what the machine needs, enable signing with enforcement on production fleets, pin third-party modules to tested kernel versions, and record /proc/sys/kernel/tainted in your monitoring so a tainted host is visible before a crash report is filed. What would change this: if a vendor module is the only way to use the hardware, keep it on a fixed kernel and put the rebuild-and-test step into your upgrade pipeline.

The idea. On Linux a device is reachable as a file under /dev. A character device is one that user programs read and write as a stream of bytes (a serial port, a sensor, a custom FPGA card), as opposed to a block device (a disk, accessed in fixed-size blocks). When a program calls open, read or write on that file, the VFS (virtual filesystem layer, the kernel's common file interface) looks up which driver owns the file's device number and calls the driver's function for that operation. The driver's job is to supply those functions and register itself so the lookup finds them. (The functions named below are the real kernel interfaces, and a compact skeleton that uses them is shown after the list of operations. The skeleton builds as a module against Debian 12's linux-headers-6.1.0-53-arm64 package; it has been compiled only and not loaded into a running kernel.)

What the driver registers (in module init, in this order)

1. A device number. A device number is a major (which driver) and minor (which device of that driver) pair. alloc_chrdev_region() picks a free major dynamically and returns it with the first minor.
2. A struct file_operations (a table of function pointers describing what the VFS may do with the file) with at least: .owner = THIS_MODULE (set it in every driver; it identifies the owning module (a kernel module is a driver compiled to be loaded into the running kernel), which is what lets the kernel keep the module loaded while a file is open), .open, .release, .read and .write. Optionally .unlocked_ioctl for device-specific commands.
3. A struct cdev (the kernel's character device object): cdev_init() ties it to the operations table, and cdev_add() registers it with the device number. The kernel documentation says cdev_add makes the device live immediately, which dictates the rule: finish initialising all driver state (locks, buffers, hardware setup) before calling cdev_add, because a user program can open the device the instant it returns.
4. A device node. class_create() and device_create() register the device in sysfs (the kernel's /sys view of devices) so that user space tools (such as udev, the daemon that populates /dev) can create the /dev file automatically; otherwise an administrator creates it by hand with mknod (a command that creates a device file from a type and a major/minor pair).
   Module exit undoes this in reverse order: device_destroy/class_destroy, cdev_del, unregister_chrdev_region. Error paths in init must unwind exactly the steps that succeeded. Note the kernel docs on cdev_del: it guarantees no new opens, but files already open stay open, so the driver must tolerate in-flight calls and use the .owner pin plus its own reference count.

What each operation does

• open: the VFS creates a struct file (one per open file description) and calls open, which also receives the inode (the kernel's record of the file itself, as opposed to one particular opening of it). Allocate or look up per-open state and store it in the file's private_data (a pointer field in struct file reserved for the driver), so each open file has its own state. Check permissions or exclusive-use rules here and return a negative error code (such as -EBUSY) to refuse.
• read(file, user_buffer, count, offset): copy up to count bytes from the driver's data to the user's buffer, advance the offset, and return the number of bytes copied (0 means end of file). A blocking read waits on a wait queue (a list of sleeping tasks that the kernel wakes when a condition changes) until data exists, unless the file was opened non-blocking, in which case it returns -EAGAIN.
• write: the mirror image: copy from the user's buffer into the device, return the number accepted.
• release: called when the last reference to the open file goes away; free what open allocated.
  The kernel docs note these methods run without VFS locks held, so they may block, and so two programs can be inside the same method at once.

A skeleton that compiles. This is a deliberately small driver: one 256-byte buffer, a mutex, and no release, ioctl or blocking read, so that the registration order and the user-copy rule are the only things to see. Built in a Debian 12 container with make -C /usr/src/linux-headers-6.1.0-53-arm64 M=$PWD modules (from the linux-headers-arm64 package; the Makefile is the single line obj-m += chardemo.o), it compiles without warnings and produces chardemo.ko. On 6.1 class_create takes THIS_MODULE as its first argument; the current kernel documentation shows a one-argument class_create(name), so adjust that call for your kernel.

#include <linux/module.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
#include <linux/uaccess.h>
#include <linux/mutex.h>

#define DEV_NAME "chardemo"
#define BUF_SZ 256

static dev_t devno;                 /* major + first minor */
static struct cdev my_cdev;
static struct class *my_class;
static DEFINE_MUTEX(buf_lock);      /* protects buf and len */
static char buf[BUF_SZ];
static size_t len;

static int my_open(struct inode *inode, struct file *filp)
{
	return 0;                   /* nothing per-open to set up in this sketch */
}

static ssize_t my_read(struct file *filp, char __user *ubuf, size_t count, loff_t *off)
{
	char tmp[BUF_SZ];
	size_t n;

	mutex_lock(&buf_lock);
	if (*off >= len) {          /* offset at or past the data: end of file */
		mutex_unlock(&buf_lock);
		return 0;
	}
	n = min(count, len - (size_t)*off);
	memcpy(tmp, buf + *off, n); /* copy into a kernel buffer under the lock */
	mutex_unlock(&buf_lock);

	if (copy_to_user(ubuf, tmp, n))   /* non-zero means bytes were not copied */
		return -EFAULT;
	*off += n;
	return n;
}

static ssize_t my_write(struct file *filp, const char __user *ubuf, size_t count, loff_t *off)
{
	char tmp[BUF_SZ];
	size_t n = min(count, sizeof(tmp));   /* never trust count */

	if (copy_from_user(tmp, ubuf, n))
		return -EFAULT;
	mutex_lock(&buf_lock);
	memcpy(buf, tmp, n);
	len = n;
	mutex_unlock(&buf_lock);
	return n;                   /* number of bytes accepted */
}

static const struct file_operations my_fops = {
	.owner   = THIS_MODULE,
	.open    = my_open,
	.read    = my_read,
	.write   = my_write,
};

static int __init chardemo_init(void)
{
	int ret = alloc_chrdev_region(&devno, 0, 1, DEV_NAME);
	if (ret)
		return ret;
	cdev_init(&my_cdev, &my_fops);
	my_cdev.owner = THIS_MODULE;
	/* all state above is ready, so it is safe to go live */
	ret = cdev_add(&my_cdev, devno, 1);
	if (ret)
		goto err_region;
	my_class = class_create(THIS_MODULE, DEV_NAME);
	if (IS_ERR(my_class)) {
		ret = PTR_ERR(my_class);
		goto err_cdev;
	}
	if (IS_ERR(device_create(my_class, NULL, devno, NULL, DEV_NAME))) {
		ret = -ENOMEM;
		goto err_class;
	}
	return 0;
err_class:
	class_destroy(my_class);
err_cdev:
	cdev_del(&my_cdev);
err_region:
	unregister_chrdev_region(devno, 1);
	return ret;
}

static void __exit chardemo_exit(void)
{
	device_destroy(my_class, devno);
	class_destroy(my_class);
	cdev_del(&my_cdev);
	unregister_chrdev_region(devno, 1);
}

module_init(chardemo_init);
module_exit(chardemo_exit);
MODULE_LICENSE("GPL");

Reading it top to bottom: my_fops is the file_operations table, so read(2) on /dev/chardemo ends up in my_read and write(2) in my_write. In chardemo_init, alloc_chrdev_region fills devno (major and minor), cdev_init binds my_cdev to my_fops, cdev_add makes the device live, and class_create plus device_create produce the /dev/chardemo node. The goto err_* labels undo only the steps that already succeeded, in reverse order, and chardemo_exit repeats that reverse order. In my_read, *off is the file position the VFS keeps for this open file: the function returns 0 when the position is at or past the data (end of file), copies out of the shared buffer into a local array while holding the mutex, drops the mutex, and only then calls copy_to_user, whose non-zero result means some bytes were not copied (so the call returns -EFAULT). my_write clamps count to the size of its local buffer with min instead of trusting it.

Where it breaks without the lock: a worked race. Suppose my_write skipped the mutex, and writer A stores "AAAA" (4 bytes) while writer B stores "BB" (2 bytes). If the steps interleave as A copies its 4 bytes, B copies its 2 bytes over the first two, B sets len = 2, then A sets len = 4, the buffer holds "BBAA" with length 4, a value neither writer wrote. A reader then returns that mixed data. The mutex makes copy-plus-length one indivisible step. Two of the traps below are the first things to check in any driver review: using a user pointer directly instead of copy_to_user / copy_from_user (a security hole), and sleeping while holding a spinlock (a hang or a kernel warning).

Traps around memory

1. Never dereference a user pointer directly. The user buffer may be unmapped, not in memory, or malicious. Use copy_to_user and copy_from_user, which return the number of bytes not copied; non-zero means fail with -EFAULT. The kernel source notes that only copy_from_user zero-fills the destination on a short copy.
2. Validate count and the offset before sizing anything: an attacker-controlled length used for an allocation or a copy into a fixed buffer is a kernel memory corruption bug, not a crash in one process.
3. Do not leak kernel memory: a read that copies a buffer which was allocated but not fully written hands the user stale kernel bytes. Zero the buffer or copy only what you wrote.
4. Allocation context: kmalloc(GFP_KERNEL) may sleep and is fine in open/read/write (process context), but not in an interrupt handler (the function the kernel runs when hardware signals the CPU, which must not sleep), which needs GFP_ATOMIC (a non-sleeping allocation, per the kernel docs).
5. Free on every path, including error paths and release; a leaked allocation is a kernel-lifetime leak.

Traps around concurrency

1. Many callers at once. Two processes can read and write the same device, and a single process's threads can share a file descriptor. Protect shared driver state with a lock. In process context where sleeping is allowed, a mutex (a lock that puts a waiting task to sleep) is the normal choice; a spinlock (a lock where a waiting CPU busy-loops instead of sleeping) is for places that cannot sleep.
2. Interrupt handlers share data with these methods. If an interrupt handler touches the same data, a mutex cannot be used on the handler's side (it must not sleep), so the shared data is guarded by a spinlock taken with interrupts disabled on the process-context side, and the handler wakes the reader through the wait queue.
3. Do not call copy_to_user or copy_from_user while holding a spinlock. These functions may sleep (the kernel source marks them with might_fault(), a debugging annotation that warns when called where sleeping is not allowed, because touching a user page can page-fault and wait for disk). Copy into a kernel buffer under the lock, drop the lock, then copy to user space.
4. Lifetime races: release or module unload racing with a read in progress (see the cdev_del note), and a wait-queue sleeper that is not woken on unload. Use reference counts, and make blocking reads interruptible by signals (return -ERESTARTSYS) so a stuck reader can be killed.
5. Lost wakeups: check the condition and sleep atomically with the wait-queue helpers (wait_event_interruptible) rather than checking a flag and then sleeping by hand.

Smallest useful design. A driver with a mutex-protected ring buffer: write appends under the mutex and wakes readers; read waits for data with wait_event_interruptible, copies out under the mutex into a temporary kernel buffer, then calls copy_to_user after dropping the lock. Test the module in a virtual machine so an oops does not take a real host down.

Part 1: why interrupt context cannot sleep.
Terms: Sleeping means the running code asks the scheduler to take the CPU away until some event happens; the scheduler saves this context and runs something else, and later resumes it. Interrupt context is the code that runs when hardware signals the CPU (an interrupt handler): it starts in the middle of whatever task happened to be running, and it is not a thread of its own. A spinlock is a lock where a CPU that finds it taken busy-waits (spins in a tight loop) until the holder releases it, instead of sleeping. Preemption is the kernel taking the CPU away from the running task to run another; a critical section is the stretch of code between taking a lock and releasing it, which only one CPU at a time may execute. Atomic context is the wider class of places (interrupt handlers, code holding a spinlock) where the kernel's rules say sleeping is forbidden; the kernel documentation lists the conditions under which a routine that may sleep can be called (user context, no spinlock held, interrupts enabled) and notes that the user-space access functions and allocations without GFP_ATOMIC may sleep implicitly.
Reasons it cannot sleep:

• There is nothing to put to sleep and wake later. A sleeping task is parked as a saved record (its registers, its kernel stack, a place on a wait queue) that the scheduler can later pick and resume. The handler has no such record: it runs on top of whichever task was interrupted, so the scheduler would have to park the handler as if it were a task, and it has no task identity of its own to resume. Blocking would instead freeze the unlucky task that was interrupted, for a reason unrelated to it.
• Interrupts must finish quickly. A handler that waits on something (a lock held by a sleeping task, or I/O) can hold the system hostage; if the thing it waits for needs the interrupted task to run first, it is a deadlock.
• A spinlock is only safe if nobody holding it can be switched out. Spinlocks implicitly disable preemption (kernel docs), so a holder runs to its unlock without another task taking the CPU. If a holder could be switched out, another CPU could spin on that lock for as long as the holder stays descheduled, burning cycles for no progress.

How that decides spinlock versus mutex

Part 2: how a futex avoids the kernel in the uncontended case.
A futex ('fast user-space mutex') is a kernel facility for building user-space locks. The lock itself is an ordinary integer in user memory (the futex word), and the kernel only gets involved to put threads to sleep and wake them. Two atomic operations appear below: compare-and-swap (CAS: set the word to a new value only if it still holds an expected one, reporting what it found) and atomic exchange (store a new value and return the old one, as one indivisible step, so no other thread can slip in between). The man page says the noncontended case happens entirely in user space and the kernel only arbitrates contention: the lock operation is an atomic instruction (compare-and-swap, an indivisible 'change if still equal' on the word), which needs no system call. Only if that fails does the thread call futex(FUTEX_WAIT), and the kernel blocks it only if the word still holds the value the caller expected, with the check and the block done atomically, so a wake-up cannot slip in between and be lost. The unlocker calls FUTEX_WAKE only when it learns somebody may be waiting.
The states in the program below are 0 (unlocked), 1 (locked, nobody waiting), 2 (locked, someone may be waiting).

Reading lock() and unlock() line by line.

• atomic_compare_exchange_strong(&word, &c, 1) with c starting at 0: if the word is 0, make it 1 and return, which is the whole uncontended lock with no system call. If the word was not 0, the call fails and writes the value it found into c (1 or 2).
• if (c != 2) c = atomic_exchange(&word, 2); the thread is about to sleep, so it must first change the word to 2, the flag that tells the unlocker 'a sleeper exists, you must wake someone'. If the word is already 2 the write would change nothing, so it is skipped. The exchange also returns the old value, and if that is 0 the lock was released in the meantime and the thread now owns it.
• while (c != 0): c != 0 means the lock was still held when the thread last looked. futex(FUTEX_WAIT_PRIVATE, 2) sleeps only if the word still equals 2 (otherwise it returns at once), then after waking the thread exchanges in 2 again and re-checks. It writes 2 rather than 1 because it cannot know whether other sleepers remain, and a spurious wake-up later is harmless while a missed one would hang a thread forever.
• unlock(): atomic_exchange(&word, 0) releases the lock and returns what the word held. Only if that was 2 can a sleeper exist, so only then is FUTEX_WAKE called to wake one thread. Returning 1 means nobody ever advertised waiting, so no system call.

A traced run with two threads (word starts at 0).

The lost-wake-up case the kernel check prevents: if A unlocked between B's exchange and B's FUTEX_WAIT, the word would be 0 when the kernel compares it with the expected 2, so the call returns immediately instead of sleeping, and B retries. Built and run in a Linux container (gcc 14.4.0, aarch64, 14 cores, -O2 -Wall -Wextra -pthread), it reports no race under ThreadSanitizer or AddressSanitizer with four threads. It counts every futex system call:

#define _GNU_SOURCE
#include <linux/futex.h>
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/syscall.h>
#include <unistd.h>

/* 0 = unlocked, 1 = locked, 2 = locked and someone may be waiting */
static atomic_int word;
static atomic_long futex_calls;
static long counter;

static void futex(int op, int val) {
    atomic_fetch_add(&futex_calls, 1);
    syscall(SYS_futex, &word, op, val, NULL, NULL, 0);
}

static void lock(void) {
    int c = 0;
    if (atomic_compare_exchange_strong(&word, &c, 1)) return;   /* fast path: no syscall */
    if (c != 2) c = atomic_exchange(&word, 2);
    while (c != 0) {
        futex(FUTEX_WAIT_PRIVATE, 2);   /* kernel sleeps only if word is still 2 */
        c = atomic_exchange(&word, 2);
    }
}

static void unlock(void) {
    if (atomic_exchange(&word, 0) == 2) futex(FUTEX_WAKE_PRIVATE, 1);
}

static void *worker(void *arg) {
    (void)arg;
    for (int i = 0; i < 200000; i++) { lock(); counter++; unlock(); }
    return NULL;
}

int main(int argc, char **argv) {
    int nthreads = argc > 1 ? atoi(argv[1]) : 1;
    pthread_t t[8];
    for (int i = 0; i < nthreads; i++) pthread_create(&t[i], NULL, worker, NULL);
    for (int i = 0; i < nthreads; i++) pthread_join(t[i], NULL);
    printf("threads=%d lock_acquisitions=%d counter=%ld futex_syscalls=%ld\n",
           nthreads, nthreads * 200000, counter, atomic_load(&futex_calls));
    return 0;
}

Run as ./futex_mutex_demo 1 then ./futex_mutex_demo 4. Output from one run (the four-thread futex count differs on every run, see below):

threads=1 lock_acquisitions=200000 counter=200000 futex_syscalls=0
threads=4 lock_acquisitions=800000 counter=800000 futex_syscalls=42539

One thread: 200,000 lock operations and zero system calls, because every acquisition was the atomic fast path. Four threads: the counter is still exactly 800,000 (the lock works), and the futex calls were 42,539 for 800,000 acquisitions, about 5.3 percent (computed), so most acquisitions still avoided the kernel even under heavy contention. The count depends on thread timing and differs on every run: further runs of the same binary gave tens of thousands of futex calls, roughly 34,000 to 60,000 (about 4 to 7 percent of the acquisitions), and a ThreadSanitizer build slows the threads and gives a far higher count (several hundred thousand in one run), so quote the shape, not the number.

What contention costs. The slow path is a system call plus a context switch (the kernel saving one thread's state and loading another's), far more expensive than an uncontended atomic instruction (measure it on your hardware, for example with the program above and perf stat). That is why a lock held briefly and rarely contended is nearly free, and why the way to speed up a contended lock is usually to shorten what it protects, not to change the lock.

Link back to Part 1. A user-space futex lock can sleep (it is in task context), so it is a mutex in kernel terms. Kernel code in interrupt context cannot use anything built on a sleeping wait; it uses spinlocks. RCU (read-copy-update: readers take no lock, and a writer publishes a new copy of the data then waits until every reader that could still see the old copy has finished before freeing it) is the common way kernel code avoids even spinlocks on read-mostly data.

Direct answer

Firmware initializes the hardware and finds a bootloader; the bootloader loads the Linux kernel and an initial RAM filesystem (initramfs) into memory; the kernel decompresses itself, initializes the CPU, memory and devices, and runs /init from the initramfs; that code finds and mounts the real root filesystem and hands over to PID 1 (usually systemd), which starts services until a login prompt appears. The initramfs exists because the kernel often cannot reach the real root filesystem by itself: the drivers, disk encryption, RAID (several disks combined into one volume) or volume manager (software that carves a pool of disks into flexible logical volumes) needed to read it may be modules that live on that very disk.

Stage by stage

1. Firmware. On modern PCs this is UEFI (Unified Extensible Firmware Interface), the successor to legacy BIOS. It runs power-on self-test, initializes memory and basic devices, and picks a boot entry. With UEFI it reads a bootloader file (a .efi program) from the EFI System Partition, a small FAT filesystem (a simple, widely supported file system format that firmware can read). Legacy BIOS instead loads the first 512-byte sector of the boot disk and chains onward. Secure Boot, if enabled, makes the firmware verify the bootloader's signature before running it.
2. Bootloader (GRUB, systemd-boot, or the kernel itself acting as an EFI program). It shows a menu, loads the kernel image and the initramfs into RAM, builds the kernel command line (parameters such as root= and quiet), and jumps into the kernel.
3. Kernel start-up. The compressed image decompresses itself into memory. The kernel then sets up memory management, the interrupt table, the scheduler and timers, discovers hardware, and initializes built-in drivers. It mounts the initramfs as its first root and starts /init as the first user-space process.
4. initramfs stage. /init loads the missing driver modules (storage controller, filesystem, network for network root), assembles RAID or logical volumes (resizable virtual partitions built on top of one or more disks, managed by LVM), unlocks encrypted volumes (asking for a passphrase), finds the real root device, mounts it, and switches the root over to it (with switch_root, which also frees the initramfs memory). The kernel documentation describes the same idea for the older initrd mechanism: boot with a minimal set of built-in drivers, load the rest from a RAM disk, mount the real root, then run /sbin/init from it.
5. PID 1 and user space. On most distributions PID 1 is systemd. It mounts the remaining filesystems, brings up devices and the network, and starts units until it reaches the target named by default (a target is a named group of units that marks a system state: multi-user.target for text mode, graphical.target for a desktop).
6. Login prompt. A getty program (a small program that waits on a text console and starts a login; for example getty@tty1.service) opens a terminal and runs login, or a display manager shows a graphical login.

What is in memory at each handoff

Why an initramfs exists

Think of it as a tiny temporary operating system whose job is to reach the real one. The kernel binary should not carry every possible disk controller, filesystem and encryption driver, so distributions ship a generic kernel with most drivers as modules. A module for the root disk cannot be read from the root disk before the disk is readable. The initramfs breaks that circle: the bootloader can read it (it is a single file next to the kernel), and it carries exactly the modules and scripts needed for this machine.

Where things go wrong (and what each symptom tells you)

• No bootloader entry or "no boot device": firmware stage, boot order or ESP problem.
• Kernel panic "unable to mount root fs": initramfs lacks the driver or the root= parameter is wrong.
• Drops to an emergency shell asking for a passphrase or after a missing volume: initramfs stage.
• Boots then hangs in services: systemd stage; systemctl --failed and journalctl -b show why.

Pitfalls

• Confusing initramfs and initrd: initrd is an older block-device RAM disk; initramfs is a cpio archive (a simple file that bundles many files together, like a tar) that the kernel unpacks into a RAM-backed filesystem. Both serve the same purpose here.
• Assuming the kernel mounts the real root itself: on typical distributions it is the initramfs code that does it.
• A security note: this chain (firmware, bootloader, kernel, initramfs) is also where persistent malware hides (a tampered bootloader or a modified initramfs survives reinstalling programs), which is why signed boot chains matter.