The process creation subsystem is the kernel mechanism that creates new processes and threads by duplicating an existing task's address space, file descriptors, signal handlers, and scheduling state. It is the implementation behind the fork(2), vfork(2), clone(2), and clone3(2) syscalls and is centered in kernel/fork.c around copy_process().
S1 — Core Kernel Subsystems
10 componentsProcess Creation Subsystem (`do_fork` / `copy_process`)
The process creation subsystem is the kernel mechanism that creates new processes and threads by duplicating an exist…
Definition
Execution Flow
- Userspace calls
fork(),vfork(),clone(), orclone3(). - The syscall entry (
sys_clone,sys_fork, etc.) collects flags and enterskernel_clone(). copy_process()is called: it allocates a newtask_structviadup_task_struct(), which copies the kernel stack and sets upthread_info.- Task struct fields are initialized: counters reset, PID assigned from the PID namespace via
alloc_pid(). - Depending on
CLONE_*flags:copy_mm()duplicates or shares the address space;copy_files()duplicates or shares file descriptors;copy_sighand()duplicates signal handlers. - The new task is inserted into the task list under
tasklist_lock. wake_up_new_task()places the child on a run queue with TASK_RUNNING state.- The scheduler may preempt the parent and begin running the child immediately (copy-on-write pages remain shared until first write-fault).
- Both parent and child return from the syscall: parent receives the child's PID, child receives 0.
Edge Cases & Failure Modes
- ENOMEM: If
dup_task_struct()orcopy_mm()fails (OOM condition),copy_process()unwinds viabad_fork_*error labels; partial allocations are freed. - PID namespace exhaustion:
alloc_pid()returnsNULLif the namespace's PID range is saturated; the fork fails withEAGAIN. RLIMIT_NPROCexceeded: If the user's process count exceeds the rlimit,copy_process()returnsEAGAIN; this is bypassed forCAP_SYS_ADMIN.vfork()deadlock: The parent blocks on a completion until the child callsexec()or exits; if the child sleeps indefinitely, the parent is permanently blocked.- Signal pending during fork: A pending fatal signal to the parent before
wake_up_new_task()causes the entire fork to be unwound.
Interrupt Request (IRQ) Subsystem (`kernel/irq/`)
The IRQ subsystem manages hardware interrupt lines from device discovery through handler dispatch.
Definition
The IRQ subsystem manages hardware interrupt lines from device discovery through handler dispatch. It provides a hardware-abstracted interrupt descriptor table, supports level-triggered and edge-triggered interrupts, and coordinates with APIC/GIC interrupt controllers via the irq_chip abstraction layer.
Execution Flow
- At boot,
irq_init_percpu_irqstack()and architecture-specificinit_IRQ()set up interrupt stacks and the IDT/GIC. - A driver calls
request_irq()→__setup_irq(), which allocates anirqactionand links it to anirq_descfor the given IRQ number. - Hardware asserts an interrupt line; the CPU saves registers and jumps to the architecture's interrupt entry stub (
entry_64.S). handle_irq()→generic_handle_irq()→handle_level_irq()/handle_edge_irq()depending on theirq_desc->handle_irqfunction pointer.- The irqchip's
irq_maskorirq_ackis called to prevent re-entry. - The registered
irqaction->handlerruns in interrupt context (hardirq). - The handler returns
IRQ_HANDLEDorIRQ_NONE; if none of the handlers claim the IRQ, the kernel logs an unhandled interrupt. - The irqchip's
irq_unmask/irq_eoiis called. - The CPU restores registers and resumes the interrupted task via
iret/eret.
Edge Cases & Failure Modes
- IRQ storm: A misbehaving device asserts its line continuously; the kernel detects this via
irq_safe_remove()logic and may disable the IRQ after a threshold (bad IRQ detection inhandle_level_irq()). - Shared IRQ conflict: Multiple devices on the same line (legacy PCI); if one device's handler fails to claim
IRQ_HANDLED, spurious IRQ warnings accumulate. - NMI nesting: Non-Maskable Interrupts cannot be disabled; nested NMIs on x86 require the
nmi_nesting_preprocessguard inarch/x86/kernel/nmi.cto prevent stack corruption. - Interrupt affinity migration race: Changing
/proc/irq/N/smp_affinitywhile an interrupt is in-flight can send EOI to the wrong CPU's APIC, causing the IRQ to be silently lost.
System Call Interface (`arch/x86/entry/`)
The system call interface is the controlled gate through which userspace transitions to kernel privilege to request k…
Definition
The system call interface is the controlled gate through which userspace transitions to kernel privilege to request kernel services. On x86-64 it uses the SYSCALL/SYSRET instructions; on ARM64, SVC #0. The interface dispatches through a syscall table (sys_call_table) indexed by syscall number.
Execution Flow
- Userspace loads the syscall number into
rax(x86-64) and arguments intordi,rsi,rdx,r10,r8,r9, then executessyscall. - The CPU switches to ring 0, saves
rip/rflagsto per-CPU state, loads the kernelrsp, and jumps toentry_SYSCALL_64inarch/x86/entry/entry_64.S. - The entry stub saves all registers to the kernel stack (
struct pt_regs). do_syscall_64()is called; it fetches the syscall number fromregs->orig_ax.- Bounds-checks the number against
NR_syscalls; looks upsys_call_table[nr]. - Runs any active
seccompfilters (BPF programs) before dispatch. - Calls the syscall handler (e.g.,
sys_read,sys_mmap); handler returns alongresult. - The return value is placed in
regs->ax. - The entry stub restores saved registers and executes
sysretqto return to userspace at the savedrip.
Edge Cases & Failure Modes
- Invalid syscall number: Numbers ≥
NR_syscallsreturn−ENOSYS. seccompSIGSYS kill: A BPF filter returningSECCOMP_RET_KILL_PROCESSdeliversSIGSYSand kills the process before the syscall handler is reached.- Signal pending at syscall exit:
exit_to_user_mode_prepare()checks for pending signals; if found, the syscall returns with−EINTRor−ERESTARTSYSbefore userspace sees the result. SMAP/SMEPviolations: If the kernel accidentally dereferences a userspace pointer withoutcopy_from_user(),SMAPraises a fault; the kernel oopses rather than allowing privilege escalation.- Speculation side-channels (Spectre v2 / Retpoline): The indirect
callthroughsys_call_tableis protected byretpolineorIBRS; disabling mitigations can re-open the attack surface.
Workqueue Subsystem (`kernel/workqueue.c`)
The workqueue subsystem provides a kernel-thread pool for deferred, process-context work.
Definition
The workqueue subsystem provides a kernel-thread pool for deferred, process-context work. Unlike tasklets (softirq-based), workqueue callbacks can sleep. It manages worker threads (kworkers), work items (struct work_struct), and thread pools organized as worker_pool objects per CPU and per NUMA node.
Execution Flow
- A kernel subsystem defines a
work_structand initializes it withINIT_WORK(&work, handler_fn). queue_work()→__queue_work()selects the appropriateworker_pool(bound to the current CPU for normal workqueues, or unbound for UNBOUND workqueues).- The work item is added to the pool's
worklist. - If no idle worker is available and the pool is below the concurrency target,
create_worker()spawns a new kworker kernel thread. - The kworker thread calls
worker_thread()→process_one_work(). process_one_work()calls the handler function:work->func(work).- After the handler returns, the worker checks for more pending work; if none, it goes idle.
- Idle workers are reaped after
IDLE_WORKER_TIMEOUT(5 minutes) to prevent thread proliferation.
Edge Cases & Failure Modes
- Work item requeue during flush: Calling
queue_work()from within a handler re-enqueues for the next iteration; callingflush_work()from within the same workqueue deadlocks. - Worker pool stall (watchdog): If all workers are blocked (e.g., waiting on a mutex held by work in the same pool),
wq_watchdog_timer_fn()fires afterwq_watchdog_threshseconds and dumps a stack trace. - Memory allocation failure in
create_worker(): Ifkthread_create()fails during worker creation, the pool falls back to existing workers; if zero workers exist, work is never processed. WQ_MEM_RECLAIMordering: Non-WQ_MEM_RECLAIMworkqueues must not be called from memory-reclaim paths; doing so can cause deadlock when kswapd tries to reclaim memory held by a worker waiting on that same workqueue.
Kernel Timer Subsystem (`kernel/time/`)
The timer subsystem provides two classes of kernel timers: `hrtimer` (high-resolution timers backed by CLOCK_MONOTONI…
Definition
The timer subsystem provides two classes of kernel timers: hrtimer (high-resolution timers backed by CLOCK_MONOTONIC/CLOCK_REALTIME, using hardware timer interrupts down to nanosecond resolution) and legacy timer_list (low-resolution jiffies-based timers). It also exposes POSIX timers to userspace via timer_create(2).
Execution Flow
- A caller initializes a timer:
hrtimer_init(&ht, CLOCK_MONOTONIC, HRTIMER_MODE_REL)and setsht.function = callback. hrtimer_start()callshrtimer_start_range_ns(), which inserts the timer into the per-CPUhrtimer_clock_basered-black tree ordered by expiry time.- The hardware timer (TSC-deadline, HPET, or ARM architected timer) is programmed to fire at the earliest expiry in the tree.
- When the hardware fires, the interrupt handler calls
hrtimer_interrupt(). hrtimer_interrupt()iterates expired timers from the rbtree front: callstimer->function(timer).- The callback returns
HRTIMER_RESTART(re-arms) orHRTIMER_NORESTART(removes from tree). - The hardware timer is reprogrammed for the next expiry.
Edge Cases & Failure Modes
- Cascading timer overload: If hundreds of timers expire simultaneously,
hrtimer_interrupt()processes them all in one IRQ context, extending interrupt latency significantly. - Clock discontinuity: Calling
settimeofday()oradjtimex()whileCLOCK_REALTIME-based hrtimers are pending can cause incorrect future expiry;CLOCK_MONOTONICtimers are immune. timer_listoverflows: Jiffies-based timers usetimer_wheels; a timer set for more thanMAX_JIFFY_OFFSETjiffies into the future wraps silently and fires immediately.nohz_fullinteractions: On CPUs innohz_fullmode, the tick is suppressed; timers are only re-evaluated when a wake-up event occurs, adding up to one-tick jitter to expected expiry.
Power Management Framework (`drivers/base/power/`)
The kernel power management framework orchestrates system-wide and per-device power state transitions.
Definition
The kernel power management framework orchestrates system-wide and per-device power state transitions. It supports runtime PM (device-level power gating), system sleep states (suspend-to-RAM, suspend-to-disk / hibernate), and CPU idle management (via the cpuidle and cpufreq subsystems).
Execution Flow
- A userspace tool writes
memordiskto/sys/power/state. enter_state()→pm_prepare()calls each device driver's.prepare()callback in topological order (children before parents).dpm_suspend()calls.suspend()callbacks on all devices (device PM list traversal).dpm_suspend_late()/dpm_suspend_noirq()follow, allowing drivers to cut clocks/power after IRQs are disabled.- CPU-specific suspend: each CPU is taken offline except the last; the last CPU calls
arch_suspend_cpu()which issues the platform-specific sleep instruction (e.g., ACPI_GTS, ARM PSCI). - On wake: the platform restores CPU state;
arch_resume_cpu()runs; IRQs re-enabled. dpm_resume_noirq()→dpm_resume_early()→dpm_resume()calls.resume()in reverse topological order.pm_finish()calls.complete()on all devices; the system returns toS0.
Edge Cases & Failure Modes
- Driver suspend failure: A driver returning non-zero from
.suspend()aborts the suspend;dpm_resume()is called on already-suspended devices to restore state. - Firmware / ACPI AML bugs: BIOS
_PTSor_WAKmethods can crash or wedge the system;acpi_suspend_errorpaths attempt to recover but sometimes leave hardware in a broken state. - Hibernation image corruption: If the swap partition is modified between snapshot and restore, the kernel detects a checksum mismatch and refuses to restore; the system cold-boots instead.
- Runtime PM reference count leak: A driver calling
pm_runtime_get()without a matchingpm_runtime_put()prevents the device from ever entering a low-power state.
Device Model and sysfs (`drivers/base/`, `fs/sysfs/`)
The kernel device model provides a unified hierarchical representation of all hardware devices and their relationship…
Definition
The kernel device model provides a unified hierarchical representation of all hardware devices and their relationships (buses, devices, drivers). It is exposed to userspace via sysfs (a virtual filesystem mounted at /sys), enabling enumeration, configuration, and udev event delivery for hotplug.
Execution Flow
- A bus driver (e.g., PCI) scans for devices and calls
device_register()for each discovered device. device_register()→kobject_add()creates akobjectnode in the sysfs hierarchy under/sys/devices/.bus_probe_device()iterates registered drivers; for each, callsdriver_match_device()(uses device IDs or DT compatible strings).- On match,
driver_probe_device()callsdriver->probe(). - The driver claims the device; attributes are created via
device_create_file(), populatingsysfsattribute files. - A
ueventis sent viakobject_uevent()→netlink_broadcast()to informudevdof the new device. udevdprocesses the event, creates/devnodes, loads firmware, runsudevrules.
Edge Cases & Failure Modes
- Driver probe failure: If
probe()returns an error,driver_probe_device()decrements the driver's reference count; if no other driver matches, the device sits unbound. - Probe deferral (
-EPROBE_DEFER): A driver may return-EPROBE_DEFERif a dependency (e.g., a GPIO chip) is not yet available; the kernel re-queues the probe after any new device is registered. - sysfs attribute race: Reading a sysfs attribute while
device_unregister()is running can reference freed memory if the driver did not hold the device reference count correctly. kobjectreference count underflow: Callingkobject_put()more times thankobject_get()triggers aBUG()inkobject_release().
Kernel Module Loader (`kernel/module/`)
The module loader implements `insmod`/`modprobe` support: it verifies ELF64 `.ko` files for valid `vermagic` (kernel …
Definition
The module loader implements insmod/modprobe support: it verifies ELF64 .ko files for valid vermagic (kernel version + config hash), applies relocations, resolves symbol dependencies against the kernel's exported symbol table (ksymtab), runs module initialization, and later handles safe removal.
Execution Flow
- Userspace calls
finit_module(fd, params, flags)orinit_module(buf, len, params). load_module()reads the ELF sections into kernel memory viavmalloc_exec().check_modinfo()validates thevermagicstring; mismatches abort immediately.simplify_symbols()resolves undefined symbols againstksymtabandksymtab_gpl; unresolved symbols abort.apply_relocations()patches the module's code/data for the final load address (KASLR randomizes this).module_init_layout_section()sets up__initandcoresections;__initis marked executable only duringdo_one_initcall().do_one_initcall(mod->init)runs the module'sinit_module()function.- On success, the module is added to
moduleslist;__initsections are freed. - On
rmmod:module_exit()is called;free_module()unmaps the ELF image; symbols are removed from the lookup table.
Edge Cases & Failure Modes
- Symbol version mismatch: Even if the symbol name matches, a CRC checksum mismatch (
CONFIG_MODVERSIONS) causesENOEXEC. init()failure: Ifinit_module()returns non-zero, the module is immediately unloaded; partial initialization (e.g., registered but un-initialized hardware) must be cleaned up by the module itself.- Tainted kernel: Loading an unsigned or out-of-tree module sets the
TAINT_OOT_MODULEflag; this affects crash dump analysis. - Unload race: If a module is in use (reference count > 0),
rmmodreturnsEWOULDBLOCK; force-removal (rmmod -f) bypasses this but can crash the kernel.
Memory Management Subsystem (`mm/`)
The `mm/` subsystem is the kernel's unified memory management layer: it manages physical page frames (via the buddy a…
Definition
The mm/ subsystem is the kernel's unified memory management layer: it manages physical page frames (via the buddy allocator), virtual address spaces (vm_area_struct / mmap), page tables, demand paging, swap, and memory compaction/reclaim. It is the largest single subsystem in the kernel.
Execution Flow
mmap(2)callsdo_mmap()→mmap_region(), which allocates avm_area_structand inserts it into the process'smm_structmaple tree / red-black tree.- No physical pages are allocated yet (lazy allocation).
- When the process accesses the mapped region, the CPU raises a page fault (
#PF/ESR_ELx_EC_DABT_LOW). do_page_fault()→handle_mm_fault()→handle_pte_fault()determines the fault type: anonymous page, file-backed page, copy-on-write, or swap-in.- For anonymous faults:
do_anonymous_page()callsalloc_zeroed_user_highpage_movable()(buddy allocator), sets up the PTE. - For file-backed:
do_fault()calls the VMA'svm_ops->fault()to load the page from the page cache. update_mmu_cache()flushes the TLB entry.kswapdandvmscanrun asynchronously to reclaim pages under memory pressure, writing dirty pages to swap or disk.
Edge Cases & Failure Modes
- OOM (Out-of-Memory): When both physical memory and swap are exhausted,
out_of_memory()invokes the OOM killer, which selects and kills a process based onoom_score. - Huge page splinting: A 2 MiB THP can be split back to 4 KiB pages under memory pressure; the split operation must pause all CPUs accessing the page (via
split_huge_page()). - Stack overflow: The stack VMA grows down; if a process exhausts its
RLIMIT_STACK, the page fault is not on a valid VMA and deliversSIGSEGV. mmap_lockcontention: Themmap_lock(formerlymmap_sem) is a per-process read-write semaphore; under high contention (many threads faulting simultaneously), it becomes a scalability bottleneck.
VFS (Virtual Filesystem Switch) Core Layer
The VFS is the kernel's filesystem-independent abstraction layer.
Definition
The VFS is the kernel's filesystem-independent abstraction layer. It defines generic inode, dentry, file, and superblock objects with operation tables (inode_operations, file_operations, super_operations) that concrete filesystems implement. This allows uniform syscall handling (open, read, write, stat) regardless of the underlying filesystem type.
Execution Flow
- A syscall like
open(path, flags)→do_sys_open()→do_filp_open()enters the VFS. path_openat()performs pathname resolution viawalk_component()andlookup_fast()/lookup_slow()against the dentry cache.- On cache miss, the filesystem's
inode_operations->lookup()is called to load the dentry from storage. vfs_open()checks permissions viainode_permission()(which invokes LSM hooks).- A
struct fileis allocated andf->f_opis set frominode->i_fop. f->f_op->open(inode, file)is called (filesystem-specific open handler).- A file descriptor is allocated and placed in the process's
fdtable. - Subsequent
read(fd)/write(fd)calls are dispatched throughf->f_op->read_iter/write_iter.
Edge Cases & Failure Modes
- Dentry cache poisoning: If a filesystem returns a negative dentry for a path, cached "file not found" answers can persist even after the file is created on-disk (requires a
d_invalidate()call). O_NOFOLLOW+ symlink race (TOCTOU): Between the permission check and the open, a symlink can be replaced;O_PATHandopenat2(RESOLVE_NO_SYMLINKS)mitigate this.- File descriptor table exhaustion: Opening files without closing them exhausts the per-process
RLIMIT_NOFILElimit; theopen()call returnsEMFILE. - Stale NFS handles: For NFS-backed filesystems, a dentry can reference a file that has been deleted on the server; operations on it return
ESTALE, which must be handled by the application.
S2 — Synchronization Primitives
10 componentsSpinlock (`arch/x86/include/asm/spinlock.h`, `kernel/locking/spinlock.c`)
A spinlock is a busy-wait mutual exclusion primitive for use in contexts where sleeping is prohibited (interrupt hand…
Definition
A spinlock is a busy-wait mutual exclusion primitive for use in contexts where sleeping is prohibited (interrupt handlers, softirqs, NMI handlers). The lock holder holds the CPU in a tight loop until the lock is released. On SMP systems, it uses an atomic exchange or compare-and-swap instruction; on x86, the queued spinlock (qspinlock) uses a ticket-based protocol to ensure fairness.
Execution Flow
spin_lock(&lk)callsraw_spin_lock().- On x86 with
CONFIG_QUEUED_SPINLOCKS: the lock byte is tested; if zero, an atomic CAS sets it to the current CPU's ticket. - If locked: the CPU enters a
PAUSE-instruction loop, reading the lock byte until it matches the CPU's ticket (MCS/qspinlock queue position). - Once acquired, preemption is implicitly disabled (or explicitly via
spin_lock_irq()which also disables local IRQs). - The critical section executes.
spin_unlock(&lk)atomically increments the lock's serving counter, releasing the next waiter in the queue.
Edge Cases & Failure Modes
- Deadlock on same CPU: Attempting to acquire a spinlock already held on the same CPU (without
spin_trylock) causes an infinite loop;CONFIG_DEBUG_SPINLOCKdetects this. - Lock held across sleep: If code holding a spinlock calls any function that may sleep (e.g.,
kmalloc(GFP_KERNEL)), it triggers amight_sleep()BUG ifCONFIG_DEBUG_ATOMIC_SLEEPis set. - Interrupt nesting: Failing to use
spin_lock_irqsave()in interrupt-context code can allow IRQ re-entry that tries to re-acquire the same spinlock, causing a deadlock. - Cache line bouncing: Under high contention on NUMA systems, the lock byte bounces between CPU caches, dramatically reducing throughput; use per-CPU structures or fine-grained locking to avoid.
Mutex (`kernel/locking/mutex.c`)
A mutex (MUTual EXclusion) is a sleeping lock for process context.
Definition
A mutex (MUTual EXclusion) is a sleeping lock for process context. Unlike spinlocks, a mutex allows the blocked thread to sleep, releasing the CPU. It enforces strict ownership: only the acquiring task may release it. It uses an atomic_long_t state combined with an MCS-node-based wait queue for fairness.
Execution Flow
mutex_lock(&m)calls__mutex_lock().- An optimistic fast-path: atomic CAS on
m->owner; if the mutex is unlocked (owner = 0), it is set to the current task pointer, and the lock is acquired immediately. - Mid-path (OSQ — Optimistic Spinning Queue): if the owner is running on another CPU, the task spins on an MCS node for a brief window (
mutex_optimistic_spin()), avoiding a full sleep if the lock is released quickly. - Slow-path: the task is added to
m->wait_list, sets its state toTASK_UNINTERRUPTIBLE(orTASK_INTERRUPTIBLEformutex_lock_interruptible()), and callsschedule(). - When the current owner calls
mutex_unlock(), it clearsm->ownerand wakes the first waiter viawake_up_process(). - The woken task re-attempts the fast-path; on success, it clears TASK_UNINTERRUPTIBLE and continues.
Edge Cases & Failure Modes
- Priority inversion: A low-priority task holding a mutex blocks a high-priority task; the kernel's PI-mutex (
mutex_lock_pi()viart_mutex) implements priority inheritance to mitigate this. - Self-deadlock detection:
CONFIG_DEBUG_MUTEXESenables lock validation; a task acquiring a mutex it already holds triggers a BUG. mutex_lock_interruptible()early return: If a signal arrives while waiting, the call returns-EINTR; the caller must handle the unacquired-lock case.- Livelock (OSQ): In degenerate cases, the optimistic spinning phase can consume excessive CPU on a system with many threads contending the same mutex; the kernel caps the spin duration with
need_resched()checks.
Read-Write Semaphore (`kernel/locking/rwsem.c`)
An `rwsem` allows multiple concurrent readers or a single exclusive writer.
Definition
An rwsem allows multiple concurrent readers or a single exclusive writer. It is a sleeping lock (readers and writers may block). Used heavily for the mmap_lock, i_rwsem (inode), and s_umount (superblock) locks. Modern kernels use rwsem with an OSQ (Optimistic Spin Queue) for writers.
Execution Flow
- Read lock:
down_read(&sem)→ fast-path: atomically increments the reader count field if no writer is active or waiting. - If a writer is pending, the reader enqueues to
wait_listwithRWSEM_WAITING_FOR_READstate and callsschedule(). - Write lock:
down_write(&sem)→ sets theRWSEM_WRITER_LOCKEDbit via atomic CAS. - If readers are active, the writer OSQ-spins briefly, then enqueues with
RWSEM_WAITING_FOR_WRITE. - The writer sleeps until all active readers call
up_read(). - Last active reader calling
up_read()checks for waiting writers; if any, wakes the first writer. - When the writer calls
up_write(), it clears the writer-locked bit; if readers are queued, it wakes them all simultaneously (batch wake-up).
Edge Cases & Failure Modes
- Writer starvation: A continuous stream of readers can prevent a writer from ever acquiring the lock; the kernel's
RWSEM_FLAG_WAITERSbit causes new readers to queue once a writer is waiting. - Downgrade race:
downgrade_write()converts a held write lock to a read lock; if done incorrectly (e.g., while in an interrupt-disabled section), it can release the lock to a waiting writer prematurely. mmap_lockscale issue: Themmap_lockis anrwsem; on heavily multithreaded workloads (e.g., many concurrent page faults), it becomes a scalability cliff. The kernel is actively replacing it with range-locked alternatives in long-term development.
RCU (Read-Copy-Update) (`kernel/rcu/`)
RCU is a synchronization mechanism that allows multiple readers to access shared data concurrently with writers, with…
Definition
RCU is a synchronization mechanism that allows multiple readers to access shared data concurrently with writers, without locking on the read side. Readers are protected by rcu_read_lock() / rcu_read_unlock(), which are essentially preemption-disable markers. Writers update data by creating a new copy, replacing the pointer atomically, and then waiting for a "grace period" (all pre-existing readers to complete) before freeing the old version.
Execution Flow
- Reader:
rcu_read_lock()disables preemption (or marks an RCU read-side critical section inPREEMPT_RCU). - Reader dereferences an RCU-protected pointer via
rcu_dereference(ptr)(which includes a data dependency barrier /smp_read_barrier_depends()). - Reader reads the data;
rcu_read_unlock()re-enables preemption. - Writer: allocates a new version of the data, copies and modifies it, then calls
rcu_assign_pointer(ptr, new_data)(which includes a write memory barrier). - Writer calls
synchronize_rcu()(orcall_rcu(&old_data->rcu_head, free_fn)for async). synchronize_rcu()waits for a grace period: it blocks until all currently-executing RCU read-side critical sections on all CPUs complete.- After the grace period, the old data is safe to free.
Edge Cases & Failure Modes
- Grace period stall: A CPU stuck in a long RCU read-side critical section (e.g., with preemption disabled for too long) delays
synchronize_rcu()indefinitely; the RCU watchdog timer fires and prints a stall warning. rcu_dereference()outside read-side: Dereferencing an RCU pointer outsidercu_read_lock()can read a pointer to freed memory;CONFIG_PROVE_RCUdetects this.- Expedited RCU side effects:
synchronize_rcu_expedited()forcibly preempts CPUs to accelerate the grace period; this increases interrupt latency and should not be used in hot paths. - SRCU (Sleepable RCU) deadlock: Unlike regular RCU,
srcu_read_lock()can sleep; calling blocking operations inside an SRCU critical section is legal, but holding an SRCU lock and then callingsynchronize_srcu()on the samesrcu_structdeadlocks.
Seqlock (`include/linux/seqlock.h`)
A seqlock (sequence lock) is an optimistic concurrency primitive designed for data that is written rarely but read ve…
Definition
A seqlock (sequence lock) is an optimistic concurrency primitive designed for data that is written rarely but read very frequently, and where the reader can tolerate retrying. Writers increment a sequence counter before and after the update; readers check the counter before and after reading — if the counter changed (or is odd, indicating a writer is active), the read is retried.
Execution Flow
- Reader: calls
read_seqbegin(&sl)→ reads and returns the current sequence counter valueseq. - Reader reads the shared data (non-atomically, without locking).
- Reader calls
read_seqretry(&sl, seq)→ reads the counter again; if it differs fromseqor is odd (write in progress), returnstrue→ reader retries from step 1. - Writer: calls
write_seqlock(&sl)→ acquires the embedded spinlock, then atomically increments the sequence counter (making it odd). - Writer modifies the shared data.
- Writer calls
write_sequnlock(&sl)→ atomically increments the counter again (making it even), then releases the spinlock.
Edge Cases & Failure Modes
- Livelock: Under a very high writer rate, readers may never see a stable (even) sequence value and loop indefinitely; this is by design but pathological in practice.
- Non-retryable operations in reader: If a reader performs side-effecting operations (e.g., memory allocation) inside the seqlock read window and must retry, those effects are not undone; seqlocks must only wrap pure reads.
- Large critical sections: The kernel's
jiffiesandtimekeeperuse seqlocks; if the writer (clock interrupt handler) holds the lock for too long, readers on other CPUs spin repeatedly. - Pointer dereference hazard: Reading a pointer under a seqlock and then dereferencing it after the read window is unsafe; if the writer freed the pointed-to object between the read and the dereference, a use-after-free results.
Completion (`kernel/sched/completion.c`)
A completion is a one-shot or multi-shot synchronization object that allows one task to wait for another to signal "d…
Definition
A completion is a one-shot or multi-shot synchronization object that allows one task to wait for another to signal "done." It is conceptually a simplified semaphore initialized to zero, used to synchronize between a producer task (which calls complete()) and a consumer task (which calls wait_for_completion()). Used extensively in driver probe/unprobe sequences and kernel thread lifecycle management.
Execution Flow
- A completion is initialized:
init_completion(&done)→ setsdone.done = 0,done.waitinitialized. - The waiting task calls
wait_for_completion(&done): - Atomically checks
done.done; if non-zero, decrements and returns immediately. - Otherwise, creates a
wait_queue_entry, sets the task state toTASK_UNINTERRUPTIBLE, and adds itself todone.wait. - Calls
schedule(); the task sleeps. - The signaling task calls
complete(&done): - Increments
done.done. - Calls
wake_up_process()on the first waiter indone.wait. - The sleeping task resumes from
schedule(), re-checksdone.done, and returns. - For broadcast wakeup:
complete_all(&done)setsdone.done = UINT_MAX / 2and wakes all waiters.
Edge Cases & Failure Modes
complete()beforewait_for_completion(): This is safe; thedonecounter records the signal and the laterwait_for_completion()returns immediately.complete()without a waiter: Thedonecounter accumulates; ifwait_for_completion()is never called, the completion leaks but causes no crash (unless the memory is freed).wait_for_completion_killable()early return: A fatal signal causes the function to return-ERESTARTSYS; the caller must handle the case where the waited-for event has not occurred.- Re-initialization race: Calling
init_completion()while another task is blocked inwait_for_completion()corrupts the wait queue; completions must not be re-initialized while in use.
Atomic Operations (`arch/x86/include/asm/atomic.h`)
Atomic operations provide CPU-guaranteed read-modify-write operations on integer values (`atomic_t`, `atomic64_t`, `a…
Definition
Atomic operations provide CPU-guaranteed read-modify-write operations on integer values (atomic_t, atomic64_t, atomic_long_t) without requiring locks. They map to CPU-native instructions: on x86, LOCK ADD, LOCK CMPXCHG, XCHG; on ARM64, LDADD, CAS (ARMv8.1+). They serve as the foundation for reference counting, lock implementation, and wait-free counters.
Execution Flow
- A variable is declared:
atomic_t refcount = ATOMIC_INIT(1). atomic_inc(&refcount)compiles to aLOCK ADDL $1, (mem)on x86 — theLOCKprefix causes the CPU to assert the bus lock (or use cache coherency) guaranteeing the increment is indivisible.atomic_dec_and_test(&refcount)compiles toLOCK DECL (mem)followed by reading the zero flag — returns true if the result is zero.atomic_cmpxchg(&v, old, new)→LOCK CMPXCHG— atomically comparesvtoold; if equal, storesnewand returnsold; otherwise returns the current value.- Memory ordering variants:
atomic_read()is a plain load with a compiler barrier;smp_load_acquire()/smp_store_release()add CPU-level acquire/release semantics.
Edge Cases & Failure Modes
- ABA problem:
atomic_cmpxchg()succeeds even if the value was changed toA, then back toAbetween the load and the CAS; use tagged pointers or DCAS where this matters. - Overflow/underflow:
atomic_tis a 32-bit counter; overflow wraps silently. Userefcount_t(which usesCONFIG_REFCOUNT_FULLprotection) for reference counts to catch accidental underflow to zero. refcount_tsaturation: The kernel'srefcount_tsaturates at INT_MAX to prevent integer overflow bugs from causing use-after-free; operations on a saturated counter warn but do not crash.- Non-atomic accesses on 64-bit counters (32-bit CPUs): On 32-bit kernels,
atomic64_toperations require a lock (emulated) because 64-bit memory accesses are not natively atomic; this is a performance cliff.
Per-CPU Variables (`include/linux/percpu.h`, `mm/percpu.c`)
Per-CPU variables are instances of data duplicated once per logical CPU, stored in CPU-local memory regions, and acce…
Definition
Per-CPU variables are instances of data duplicated once per logical CPU, stored in CPU-local memory regions, and accessed locklessly because each CPU always accesses only its own copy. They eliminate cache line bouncing on frequently updated statistics counters, scheduler run queues, and allocator caches (SLUB cpu_slab).
Execution Flow
- A per-CPU variable is declared:
DEFINE_PER_CPU(unsigned long, mycounter). - At boot,
setup_per_cpu_areas()allocates a contiguous memory region for each CPU, copies the initial values, and sets per-CPU base pointers. - Access:
get_cpu_var(mycounter)disables preemption and returns a reference to the current CPU's copy viathis_cpu_ptr(&mycounter)(which uses the%gsorTPIDR_EL1base register offset on x86/ARM64). - The variable is modified.
put_cpu_var(mycounter)re-enables preemption.- For lockless access (safe only for statistics):
this_cpu_add(mycounter, 1)uses aLOCK-freeADDvia thethis_cpu_*family of operations, which rely on the fact that only the local CPU writes this copy.
Edge Cases & Failure Modes
- Preemption not disabled: If preemption is enabled when
this_cpu_ptr()is used (not insideget_cpu_var()), the task can be migrated to another CPU between reading the pointer and dereferencing it, accessing the wrong CPU's copy. - Interrupt context access: An interrupt handler can preempt code using
this_cpu_ptr()on the same CPU; both access the same per-CPU variable without coordination, causing a data race if the interrupt handler also modifies it. - Dynamic per-CPU allocation (
alloc_percpu()): The returned pointer must be freed withfree_percpu(); a leak causes the per-CPU allocator's chunk pool to grow without bound. - Hotplug CPU offline: When a CPU goes offline, its per-CPU data is not automatically migrated; subsystems must flush/drain per-CPU data in their
CPU_DEADnotifier.
Futex (`kernel/futex/`)
A futex (Fast Userspace muTEX) is a hybrid synchronization primitive: the fast path is a userspace atomic operation o…
Definition
A futex (Fast Userspace muTEX) is a hybrid synchronization primitive: the fast path is a userspace atomic operation on a shared integer (no syscall required); only on contention does the thread make a futex(2) syscall to block in the kernel. The kernel maintains a hash table of futex_q (futex queue) entries keyed by the physical address of the futex word.
Execution Flow
- Lock attempt: userspace atomically tries CAS on the futex word (
uaddr); if it succeeds (word was 0, now 1), the lock is acquired without entering the kernel. - On contention (word was already 1): the thread sets a "has waiters" bit (word = 2) and calls
futex(FUTEX_WAIT, uaddr, expected_val, timeout). - Kernel:
do_futex()→futex_wait()→ computes the hash key (futex_key) from the futex word's physical page + offset. futex_wait_setup()verifies the futex value still equalsexpected_val; if it changed (racing unlock), returns immediately withEAGAIN.- The task is added to
hb->chain(hash bucket wait queue) and callsschedule_hrtimeout(). - Unlock: the unlocking thread atomically clears the word; if "has waiters" bit was set, calls
futex(FUTEX_WAKE, uaddr, count). - Kernel:
futex_wake()removes up tocountwaiters from the hash bucket and wakes them viawake_up_q().
Edge Cases & Failure Modes
- Priority inversion: A low-priority holder blocks a high-priority waiter;
FUTEX_LOCK_PI/FUTEX_UNLOCK_PIimplement priority inheritance via RT-mutexes to prevent this. - Spurious wakeup: A signal delivery wakes the futex waiter before the futex word changes; userspace must re-check the futex word in a loop.
FUTEX_WAIT/ value race: Between the userspace CAS failure and the kernelfutex_wait_setup()check, another thread may have already unlocked; the check catches this and returnsEAGAIN, preventing a missed wakeup.- Robust futex list corruption: If a process is killed while holding a robust futex, the kernel walks the robust list (
set_robust_list(2)) to wake waiters withFUTEX_OWNER_DIED; a corrupt list pointer causes a kernel read of a bad address, triggering a fault inhandle_futex_death().
Semaphore (`kernel/locking/semaphore.c`)
A counting semaphore (`struct semaphore`) allows a specified number of concurrent holders, unlike a mutex (which allo…
Definition
A counting semaphore (struct semaphore) allows a specified number of concurrent holders, unlike a mutex (which allows exactly one). It is a sleeping primitive: down() decrements the count and sleeps if the result is negative; up() increments and wakes a waiter. Used for resource pools (e.g., limiting concurrent hardware accesses).
Execution Flow
- Initialization:
sema_init(&sem, N)setssem.count = Nand initializessem.wait_list. down(&sem)→__down():- Atomically decrements
sem.count. - If result ≥ 0, returns immediately (resource acquired).
- If result < 0, adds the current task to
sem.wait_listwith stateTASK_UNINTERRUPTIBLE, callsschedule(). up(&sem)→__up():- Atomically increments
sem.count. - If
wait_listis non-empty, callswake_up_process()on the first waiter. - The woken waiter re-runs from
schedule()return, verifies it was woken by anup()(not spuriously), and returns.
Edge Cases & Failure Modes
- Semaphore released without being acquired: Calling
up()more times thandown()raises the counter above its initial value, allowing more concurrent holders than intended; the kernel does not check for this. down_interruptible()early return: Returns-EINTRon signal; the caller must handle the case where the resource was not acquired, to avoid resource leaks.down_trylock()busy-wait abuse: Usingdown_trylock()in a tight loop is equivalent to spinning and wastes CPU; the caller should use the blockingdown()or a semaphore-appropriate data structure.- Priority inversion (no inheritance): Unlike
rt_mutex-based locks, the kernelsemaphorehas no priority inheritance; real-time tasks blocked on a semaphore held by a low-priority task may miss their deadlines.
S3 — Memory Allocators
10 componentsBuddy Allocator (`mm/page_alloc.c`)
The buddy allocator is the kernel's physical page frame manager.
Definition
The buddy allocator is the kernel's physical page frame manager. It organizes free pages into 11 lists of power-of-two blocks (order 0 = 1 page to order 10 = 1024 pages = 4 MiB). When a block is freed, the allocator checks whether its "buddy" (the adjacent block of the same size) is also free; if so, the two are merged into a block of double the size (recursively up to order 10).
Execution Flow
alloc_pages(gfp_flags, order)→__alloc_pages().get_page_from_freelist()iterates memory zones (ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM) in preference order.- For the target zone,
rmqueue()checks the free list at the requested order. - If a block of that order is available, it is removed from the free list, split if the allocation is for a lower order (the remainder is added back to the appropriate free list as a buddy), and returned.
- If no block at the requested order is available,
rmqueue()tries the next higher order and splits. - If all higher orders are also empty: watermark check fails,
wake_up_kswapd()is called to reclaim memory, and__alloc_pages_slowpath()tries OOM killer / migration. - Physical page address returned as
struct page *; virtual mapping viapage_to_virt().
Edge Cases & Failure Modes
- External fragmentation: Over time, free memory becomes fragmented into non-contiguous blocks; large-order allocations fail even when total free memory is sufficient.
CONFIG_COMPACTIONandkcompactdmigrate movable pages to coalesce free space. - Zone imbalance: If
ZONE_DMA32is exhausted butZONE_NORMALhas free pages, allocations requiringGFP_DMA32fail; devices that require DMA below 4 GiB report errors. - Atomic allocation failures (
GFP_ATOMIC): Atomic allocations cannot sleep or reclaim; they draw from a reserved "emergency" pool (min_free_kbytes). If that pool is exhausted, the allocation fails and the caller must handleNULL. - High-order allocation under pressure: A request for order-10 (4 MiB) pages may fail even with gigabytes of free memory if no contiguous region is available; drivers should use scatter-gather DMA rather than requiring contiguous buffers.
SLAB Allocator (`mm/slab.c`)
The SLAB allocator (Bonwick 1994, Linux port ~2.0) manages pools of fixed-size kernel objects.
Definition
The SLAB allocator (Bonwick 1994, Linux port ~2.0) manages pools of fixed-size kernel objects. Each pool (kmem_cache) holds multiple slabs (pages containing a homogeneous array of objects). Freed objects are cached rather than immediately returned to the buddy allocator, amortizing initialization cost. SLAB is the original allocator; most modern kernels use SLUB by default.
Execution Flow
kmem_cache_create("name", object_size, align, flags, ctor)creates a new cache; calculates optimal objects-per-slab and slab order.kmem_cache_alloc(cache, gfp)→ checks the per-CPU cache (array_cache); if non-empty, returns the top-of-stack object (fast path, no locking).- If per-CPU cache is empty:
cache_alloc_refill()fills it from the shared array (requirescache_lock); if shared array is empty,cache_grow_begin()allocates new pages from the buddy allocator and divides them into objects. - Object initialization: if a constructor (
ctor) was provided, it is called on first use. kmem_cache_free(cache, obj)returns the object to the per-CPU cache top-of-stack.- When the per-CPU cache overflows its
batchcount, objects are moved to the shared array; when that overflows, full slabs are returned to the buddy allocator.
Edge Cases & Failure Modes
- Slab poisoning detection: With
CONFIG_DEBUG_SLAB, freed objects are filled with0x6b("k"); a later allocation that reads a non-poisoned value indicates a use-after-free. - Cache aliasing: Multiple
kmem_cache_create()calls with the same size may or may not share an underlying slab pool depending onCONFIG_SLAB_MERGE_DEFAULT; unintended sharing can lead to type confusion bugs. - Per-CPU cache under/overflow in hot-unplug: When a CPU goes offline while its per-CPU cache holds objects,
free_block()must flush those objects to the shared list; failure to do so leaks memory. - Constructor called on reuse (SLAB only): SLAB's constructor is called only at slab creation, not on each allocation; a constructor that initializes lock state may leave stale lock state if not re-initialized at alloc time.
SLUB Allocator (`mm/slub.c`)
SLUB (SLab Unqueued Bookkeeping) is the default slab allocator since Linux 2.6.23.
Definition
SLUB (SLab Unqueued Bookkeeping) is the default slab allocator since Linux 2.6.23. It reduces metadata overhead by storing bookkeeping in unused parts of objects themselves rather than in separate management arrays. It uses per-CPU "cpu_slab" pointers for lockless fast-path allocation and a per-node partial-slab list for the slow path.
Execution Flow
kmem_cache_alloc(s, gfp)→ readss->cpu_slab->freelist(locklessly, usingthis_cpu_ptr).- Fast path: if
freelistis non-NULL, pops the first free object from the freelist (a pointer stored inside the object itself), returns it. - Slow path (
__slab_alloc()): if the CPU slab is empty, tries the next partial slab ons->node[nid]->partial. - If no partial slabs: allocates a new slab of pages from the buddy allocator, initializes the freelist chain, and assigns it as the new CPU slab.
kmem_cache_free(s, obj)→do_slab_free(): pushesobjonto the CPU slab's freelist (lockless CAS usingthis_cpu_cmpxchg_double).- When the CPU slab becomes fully free, it is returned to the partial list or freed to the buddy allocator (based on
min_partialthreshold).
Edge Cases & Failure Modes
- Double-free detection: SLUB stores a "freelist pointer" XOR'd with a secret in the object itself (
CONFIG_SLAB_FREELIST_HARDENED); a double-free corrupts the XOR value and is detected on the next allocation with aBUG_ON. - Redzone overwrite:
CONFIG_SLUB_DEBUGadds redzones around objects; buffer overflows into the redzone are detected on free. - Quarantine (KASAN): Kernel Address Sanitizer delays reuse of freed SLUB objects; a use-after-free that accesses a quarantined object triggers an immediate KASAN report.
- NUMAism: SLUB maintains per-node partial lists; on NUMA systems, allocating from a remote node's slab incurs a NUMA penalty; the
kmem_cache_alloc_node()API enforces local allocation.
SLOB Allocator (`mm/slob.c`)
SLOB (Simple List Of Blocks) is a compact allocator designed for systems with very limited memory (embedded, tiny IoT…
Definition
SLOB (Simple List Of Blocks) is a compact allocator designed for systems with very limited memory (embedded, tiny IoT kernels). It uses three first-fit free lists for objects ≤ 256 B, ≤ 1024 B, and larger, and stores metadata inline as a small header per block. It has no per-CPU caches or object pools, trading performance for minimal code and metadata size.
Execution Flow
kmalloc(size, gfp)with SLOB selects one of three free lists by size bracket.slob_alloc(size, gfp, align, node)acquiresslob_lock(global spinlock) and walks the selected free list.- First-fit: finds the first free block ≥ requested size.
- If the block is significantly larger, it is split: the remainder becomes a new free block inserted after the allocated portion.
- If no fit found:
slob_new_pages()allocates a new page from the buddy allocator, initializes it as a SLOB page, and retries. kfree(obj)→slob_free()acquiresslob_lock, inserts the block back into the appropriate free list in address order, and coalesces with adjacent free blocks.
Edge Cases & Failure Modes
- Global lock bottleneck: The single
slob_lockserializes all allocations and frees; SLOB is entirely unsuitable for SMP workloads above trivial scale. - Fragmentation (no compaction): SLOB has no per-slab concept; fragmentation accumulates and is never compacted, leading to wasted memory over time.
- No NUMA awareness: SLOB is unaware of NUMA topology; all allocations come from the same free list regardless of NUMA node.
- Deprecation path: SLOB was removed from mainline Linux in kernel 6.4 (
CONFIG_SLOBremoved); code relying on it must migrate to SLUB.
`vmalloc` / `vmap` (`mm/vmalloc.c`)
`vmalloc()` allocates virtually contiguous but physically discontiguous memory by mapping individual (potentially non…
Definition
vmalloc() allocates virtually contiguous but physically discontiguous memory by mapping individual (potentially non-contiguous) physical pages into a contiguous range in the kernel's vmalloc area (above VMALLOC_START). It is used when large allocations are needed but physically contiguous pages cannot be guaranteed.
Execution Flow
vmalloc(size)→__vmalloc_node().- A
vm_structis allocated (describes the virtual range) and inserted into the vmalloc Red-Black tree. get_vm_area_caller()finds a gap in the vmalloc address space for the requested size (aligned to page boundaries).- For each page in the allocation:
alloc_page(GFP_KERNEL)obtains a physical page (order 0) from the buddy allocator. map_kernel_range()/vmap_pages_range()establishes page table entries mapping the virtual range to the allocated physical pages.flush_cache_vmap()flushes TLB entries for the new mapping.- Returns the virtual address of the start of the mapping.
vfree(addr)unmaps page tables, frees each physical page to the buddy allocator, and removes thevm_structfrom the tree.
Edge Cases & Failure Modes
- vmalloc space exhaustion: The vmalloc area is finite (128 TiB on x86-64 by default); a leak of
vm_structentries or large vmalloc allocations withoutvfree()can exhaust it. - TLB shootdown cost: Each
vfree()requires an IPI to all CPUs to flush TLB entries for the freed range; this is expensive under high allocation/free rates and can cause latency spikes. - Non-contiguous physical pages: Drivers that use
vmalloc()-allocated buffers for DMA must use scatter-gather lists; passing a vmalloc address directly to a DMA engine will cause silent corruption or a machine check. vmap()on highmem pages (32-bit kernels): MappingZONE_HIGHMEMpages viavmap()is the standard way to access them on 32-bit kernels;kunmap_atomic()must be called promptly to avoid kmap slot exhaustion.
`kmalloc` / `kfree` (`include/linux/slab.h`)
`kmalloc(size, gfp_flags)` is the primary general-purpose kernel small-object allocator.
Definition
kmalloc(size, gfp_flags) is the primary general-purpose kernel small-object allocator. It is a wrapper around the active slab allocator (SLUB by default) that selects a pre-existing kmem_cache whose object size is the smallest power-of-two ≥ size. The returned memory is physically and virtually contiguous (unlike vmalloc).
Execution Flow
kmalloc(size, gfp)→__kmalloc().kmalloc_slab(size, gfp)looks up the appropriatekmem_cachefromkmalloc_caches[type][index]whereindex = ilog2(roundup_pow_of_two(size)).- If size is 0, returns
ZERO_SIZE_PTR(a non-NULL magic constant that is safe to pass tokfree()). - If size >
KMALLOC_MAX_CACHE_SIZE(typically 8 KiB on 4 KiB page systems): falls through tokmalloc_large()→alloc_pages()for order-based allocation. - Otherwise:
kmem_cache_alloc(cache, gfp)is called on the selected cache (SLUB fast path: per-CPU freelist pop). kfree(ptr)→__kfree(): usesvirt_to_head_page()to find thestruct page→ identifies thekmem_cache→ callskmem_cache_free().
Edge Cases & Failure Modes
- Size rounding waste: An allocation of 33 bytes uses the 64-byte cache, wasting 31 bytes; for performance-critical code with many such objects,
kmem_cache_create()with an exact size is preferable. - GFP flag misuse: Using
GFP_KERNEL(may sleep/reclaim) in atomic context (IRQ handler, spinlock held) triggers amight_sleep()warning or, worse, deadlock if the allocator tries to reclaim memory. kfree()on a stack pointer or non-kmalloc memory: SLUB'skfree()usesvirt_to_head_page()to verify the pointer is slab-managed; a pointer to a stack variable or static data causes a BUG.- Speculative failure under pressure: Even
GFP_KERNELallocations can fail under extreme memory pressure if the OOM killer has already killed all candidates; callers must check forNULLand handle it gracefully.
Memory Pool (`mm/mempool.c`)
A mempool is a reserved pool of pre-allocated objects that guarantees allocation success even under extreme memory pr…
Definition
A mempool is a reserved pool of pre-allocated objects that guarantees allocation success even under extreme memory pressure, as long as the pool size is not exhausted. It is used in I/O paths (bio allocations, DM) where allocation failure would deadlock the system (the memory reclaim path itself triggers I/O). The pool maintains a minimum number of elements allocated at initialization time.
Execution Flow
mempool_create(min_nr, alloc_fn, free_fn, pool_data)callsalloc_fn()min_nrtimes and stores the objects inpool->elements[].mempool_alloc(pool, gfp)first tries the underlying allocator directly: callspool->alloc(gfp | __GFP_NOMEMALLOC, pool->pool_data).- If the allocator succeeds, the reserved pool is untouched.
- If the allocator fails and
gfp & __GFP_DIRECT_RECLAIM: the caller may wait onpool->wait(a wait_queue) if the pool is empty. - If the pool's
elements[]array is non-empty, an element is popped (underpool->lock) and returned. - If both the allocator and pool are empty and
GFP_NOIO: returns NULL (fatal for some paths; must be sized conservatively). mempool_free(element, pool):- If pool is below
min_nr, the element is returned topool->elements[]and a waiter inpool->waitis woken. - Otherwise,
pool->free()is called to return the element to the underlying allocator.
Edge Cases & Failure Modes
- Pool size insufficient for deadlock avoidance: If the pool size is too small and all elements are in-flight simultaneously, a new allocation blocks even from the reserved pool, causing deadlock in the reclaim path.
mempool_allocwithGFP_NOIOreturning NULL: Callers in the I/O stack must handle NULL explicitly; most DM/bio code treats this as a fatal condition and returns an I/O error.- Pool element leak: If code acquires an element from a mempool and returns an error without calling
mempool_free(), the pool shrinks belowmin_nr; the pool replenishes lazily when elements are freed but may be temporarily undersized.
CMA (Contiguous Memory Allocator) (`mm/cma.c`)
CMA reserves contiguous physical memory regions at boot time (via `cma=` kernel parameter or device tree `reserved-me…
Definition
CMA reserves contiguous physical memory regions at boot time (via cma= kernel parameter or device tree reserved-memory nodes). Unlike the buddy allocator, CMA regions are still used for movable page allocations during normal operation and are reclaimed (by migrating those pages) when a CMA allocation is requested, providing contiguous physical memory for DMA-capable devices without permanently wasting RAM.
Execution Flow
- At boot:
cma_declare_contiguous()marks a physical range as a CMA region; the range is managed by the buddy allocator asMIGRATE_CMApages. dma_alloc_contiguous()→cma_alloc(cma, count, align, no_warn).alloc_contig_range()tries to isolate the requested page range from the buddy allocator.start_isolate_page_range()changes the migration type of the target pages toMIGRATE_ISOLATE, preventing new allocations into them.migrate_pages()moves all currently-allocated movable pages out of the range to other memory zones.- If migration succeeds, the range is allocated contiguously and returned as a
struct page *. cma_release()→free_contig_range()returns the pages to the buddy allocator asMIGRATE_CMA.
Edge Cases & Failure Modes
- Migration failure: If a page in the requested range cannot be migrated (pinned, locked, or of a non-movable type),
alloc_contig_range()fails with-EBUSY; the caller receives NULL. - CMA fragmentation over time: Long-running systems may pin non-movable pages inside the CMA region (via
get_user_pages()), making contiguous allocation progressively harder. - CMA size reservation vs. DMA size: If the CMA region is smaller than the device's DMA buffer requirement, the allocation always fails regardless of total free memory.
- Early CMA allocation before migration is ready: During early boot (before
mem_init()), page migration is not available; CMA requests during this phase use a simple early allocator that permanently removes pages from the buddy pool.
Transparent Huge Pages (THP) (`mm/huge_memory.c`)
THP automatically promotes 4 KiB pages to 2 MiB huge pages (on x86-64) when a process's anonymous mappings are large …
Definition
THP automatically promotes 4 KiB pages to 2 MiB huge pages (on x86-64) when a process's anonymous mappings are large and contiguous, reducing TLB pressure and page table size. It operates transparently: userspace sees no change. khugepaged is a background kernel thread that scans for small-page regions eligible for promotion.
Execution Flow
- A process
mmap()s a large anonymous region. - Initial page faults allocate 4 KiB pages normally.
khugepagedwakes periodically, scansmm_structpage tables for 2 MiB-aligned regions where all 512 small pages are present and have no special flags (e.g., not locked, not shared beyond the PMD level).collapse_huge_page()allocates a 2 MiB physically contiguous block (order-9 huge page from the buddy allocator).copy_page()copies all 512 small pages into the new huge page.- The PMD entry is replaced with a huge-page PMD pointing to the new 2 MiB block.
- The 512 original small pages are released to the buddy allocator.
- Future page faults in the region use the PMD-level huge page, skipping 512 PTE lookups.
- On split (e.g., due to
mprotect(),mremap(), or memory pressure):split_huge_page()rebuilds the 512 PTE entries and returns the huge page to the buddy allocator.
Edge Cases & Failure Modes
- THP allocation failure: The order-9 allocation may fail under memory pressure;
khugepagedretries later, so the page table remains small until a contiguous block becomes available. - THP split under swap pressure: If the system needs to swap out part of a THP region, the huge page must be split first; splitting is expensive (requires locking all 512 PTEs and an IPI).
- THP in
mlock()'d regions: Locking a region preventskhugepagedfrom collapsing it; the interaction betweenVM_LOCKEDand THP requires care in memory-pinning code. - False sharing amplification: A 2 MiB THP means a write to any page in the region dirtifies the entire 2 MiB; under high write rates with sparse access patterns, this causes more writeback I/O than small pages would.
Per-CPU Allocator (`mm/percpu.c`)
The per-CPU allocator manages the per-CPU memory areas created at boot time (and dynamically via `alloc_percpu()`).
Definition
The per-CPU allocator manages the per-CPU memory areas created at boot time (and dynamically via alloc_percpu()). It segments memory into chunks aligned to CPU cache lines and allocates variable-sized per-CPU regions using a first-fit allocator within each chunk. The resulting __percpu-annotated pointers are offsets relative to each CPU's base address.
Execution Flow
- At boot:
pcpu_setup_first_chunk()carves out per-CPU memory from the kernel image and sets__per_cpu_offset[cpu]for each CPU. alloc_percpu(type)→__alloc_percpu(size, align).pcpu_alloc()acquirespcpu_lockand searches for a free slot in existing chunks of appropriate group (small/large).- If no space in existing chunks:
pcpu_create_chunk()allocates new pages from the buddy allocator and maps them into each CPU's per-CPU address space. - The allocated offset is stored; the returned
__percpu *pointer is an offset, not a real address. per_cpu_ptr(ptr, cpu)→(void *)((unsigned long)(ptr) + __per_cpu_offset[cpu])→ produces the real per-CPU address for a specific CPU.free_percpu(ptr)returns the offset to the chunk's free list; fully free chunks are returned to the buddy allocator.
Edge Cases & Failure Modes
- Early boot allocation before
__per_cpu_offsetis set: Accessing per-CPU data beforesetup_per_cpu_areas()completes reads garbage; architecture-specific boot code must be careful about ordering. - Module per-CPU allocation failure: If
alloc_percpu()fails during module load, the module'sinit()must free all previously allocated per-CPU areas before returning the error; partial cleanup causes permanent per-CPU space leakage. - CPU offline drain: When a CPU goes offline, any data accumulated in its per-CPU allocator slab caches (SLUB
cpu_slab) must be drained to the per-node list; theCPU_DEADnotifier handles this but only if properly registered. - Cache line alignment: The per-CPU allocator aligns allocations to
SMP_CACHE_BYTES(typically 64 B); structures smaller than a cache line waste space but prevent false sharing.
S4 — Process & CPU Schedulers
10 componentsCFS (Completely Fair Scheduler) (`kernel/sched/fair.c`)
CFS is the default scheduler for normal (non-real-time) tasks in Linux, implementing SCHED_NORMAL and SCHED_BATCH pol…
Definition
CFS is the default scheduler for normal (non-real-time) tasks in Linux, implementing SCHED_NORMAL and SCHED_BATCH policies. It models a "perfect multitasking processor" where each task receives equal CPU time proportional to its weight (nice value). It uses a Red-Black tree keyed by vruntime (virtual runtime: actual CPU time scaled by task weight) to select the next task.
Execution Flow
- Task enqueueing:
enqueue_task_fair()adds thesched_entityto the per-CPU RB tree and updatescfs_rq->nr_running. - Task selection:
pick_next_task_fair()returns thesched_entitywith the minimumvruntime(leftmost node of the RB tree). - The selected task's
vruntimeis advanced bycalc_delta_fair(delta, se)during each scheduler tick, proportional to actual runtime divided by its weight. update_curr()is called on each tick (viatask_tick_fair()) to updatevruntimeand check if the current task should be preempted.- Preemption check: if the minimum
vruntimeon the RB tree is more thansysctl_sched_latency / nr_runningless than the current task'svruntime,resched_curr()setsTIF_NEED_RESCHED. - On the next kernel exit or
schedule()call,pick_next_task_fair()dequeues the minimum-vruntime task and context-switches to it.
Edge Cases & Failure Modes
- vruntime overflow: After long uptime, 64-bit
vruntimecould theoretically overflow; it doesn't in practice on 64-bit kernels (overflow in ~584 years at 1 GHz), but on 32-bit kernels it can overflow in days if the system is under heavy load. - Newly woken task vruntime placement: A sleeping task's
vruntimeis not advanced; on wake, it is set tomax(task->vruntime, cfs_rq->min_vruntime - sysctl_sched_wakeup_granularity)to prevent "vruntime regression" (a just-woken task unfairly dominating the CPU). - Group scheduling (cgroups) complexity: With CPU cgroups, CFS uses a hierarchical scheduler entity (
sched_entitytrees); incorrect group weight configuration can starve entire cgroups. - Latency target vs. throughput: With many tasks,
sysctl_sched_latencyis spread overnr_runningtasks; each task's timeslice shrinks belowsysctl_sched_min_granularity, causing excessive context-switch overhead.
RT Scheduler (`kernel/sched/rt.c`)
The real-time scheduler implements `SCHED_FIFO` and `SCHED_RR` policies.
Definition
The real-time scheduler implements SCHED_FIFO and SCHED_RR policies. All real-time tasks have a static priority (1–99 for SCHED_FIFO/SCHED_RR) and preempt any CFS or idle task. SCHED_FIFO runs until blocked or preempted by a higher-priority RT task. SCHED_RR adds a timeslice (100 ms default): when exhausted, the task is moved to the back of the run queue at the same priority.
Execution Flow
enqueue_task_rt()adds the task to the per-priority FIFO queue inrt_rq->active.queue[priority].pick_next_task_rt()callspick_next_rt_entity()→ finds the highest non-empty priority queue using thert_rq->active.bitmap(a bitmask of populated priority levels).- The highest-priority task is returned; if multiple tasks share the same priority, the head of the FIFO queue is selected.
task_tick_rt()runs on each tick; forSCHED_RR, decrements the timeslice counter; on expiry, callsrequeue_task_rt()to move the task to the tail of its priority queue.- For
SCHED_FIFO, the task runs until it blocks, yields, or is preempted by a higher-priority task. dequeue_task_rt()removes the task from the bitmap/queue on block or completion.
Edge Cases & Failure Modes
- RT bandwidth throttling: Without
CONFIG_RT_GROUP_SCHED, a single SCHED_FIFO task at priority 99 can starve all other tasks (including the kernel's watchdog thread).sysctl_sched_rt_runtime/sysctl_sched_rt_periodenforce a bandwidth cap (default: 95% CPU for RT tasks). - Priority inversion in RT: An RT task blocked waiting for a resource held by a CFS task may be delayed indefinitely without priority inheritance;
SCHED_FIFOwithpthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT)mitigates this. - Missed SCHED_RR timeslice reset: On
fork(), the child inherits the parent's remaining timeslice, not a fresh 100 ms; this can cause the child to run for a very short time before being rotated. - Migration to wrong CPU: Under
RT_GROUP_SCHED, pull/push migrations of RT tasks must respect CPU affinity masks; a migration that violatescpus_allowedcauses a kernel BUG inset_task_cpu().
Deadline Scheduler (`kernel/sched/deadline.c`)
The deadline scheduler implements `SCHED_DEADLINE` policy based on the Earliest Deadline First (EDF) algorithm with C…
Definition
The deadline scheduler implements SCHED_DEADLINE policy based on the Earliest Deadline First (EDF) algorithm with Constant Bandwidth Server (CBS) for admission control. Each task specifies three parameters: runtime (worst-case execution time per period), deadline (relative deadline), and period. The scheduler guarantees that a task meeting its parameters will never miss its deadline, as long as the total utilization (Σ runtime/period) ≤ 1.
Execution Flow
- Task admission:
dl_overflow()checks that adding the new task's utilization (runtime/period) would not exceed the CPU's capacity; rejects withEBUSYif it would. enqueue_task_dl()inserts the task'ssched_dl_entityinto the per-CPU RB tree keyed by absolute deadline.pick_next_task_dl()returns the leftmost node (earliest absolute deadline).- During execution:
update_dl_task_contention()depletes the CBS bandwidth;task_tick_dl()decrements remaining runtime. - When runtime is exhausted before the deadline, the task is throttled:
start_dl_timer()sets a replenishment timer for the next period start. - At period start, the runtime is replenished and the task re-enters the RB tree with a new deadline.
- When the absolute deadline passes (task completes):
dequeue_task_dl()removes the entity; the next period's parameters are set.
Edge Cases & Failure Modes
- Admission control race: Two simultaneous
sched_setattr()calls for two tasks may each pass the capacity check individually but together exceed 100%; the kernel serializes viadl_b->lockper root domain but a race across NUMA nodes can still occur. - Missed deadline (overrun): CBS guarantees no deadline miss for tasks meeting their parameters; if a task's actual execution time exceeds
runtime, it is throttled (not preempted), which causes a soft deadline miss for that period. SCHED_DEADLINEtask on a cgroup-constrained CPU: If the CPU's available capacity is reduced by cpuset/cgroup constraints, the utilization bound is tighter; the kernel doesn't automatically re-admit tasks after capacity reduction.- Priority boosting interaction: A deadline task boosting a mutex-holding CFS task (via PI) adds unbounded latency to the DL task; this is an open research problem in the PREEMPT_RT community.
Idle Scheduler (`kernel/sched/idle.c`)
The idle scheduler runs the special `idle` task (PID 0, one per CPU) when no other runnable task exists.
Definition
The idle scheduler runs the special idle task (PID 0, one per CPU) when no other runnable task exists. The idle task calls the architecture's idle loop (cpu_idle_loop()), which calls cpuidle_idle_call() to enter the deepest available C-state (CPU power state) using the cpuidle framework. The idle scheduler is the last-resort scheduler class with priority below all others.
Execution Flow
pick_next_task_idle()is reached only when all other scheduler classes (stop,dl,rt,fair) have no runnable tasks.- The idle task is returned; it cannot be dequeued.
cpu_idle_loop()starts: setscurrent->state = TASK_IDLE.tick_nohz_idle_enter()stops the scheduling tick ifNO_HZ_IDLEis configured (tickless idle).cpuidle_idle_call()queries the cpuidle governor (menu or ladder) for the best C-state.- The cpuidle driver executes
state->enter()(e.g.,mwait_idle_with_hints()on x86 →MWAITinstruction). - When a hardware interrupt or IPI arrives, the CPU exits the C-state and re-runs the scheduler.
tick_nohz_idle_exit()restores the tick;schedule_idle()checks for new runnable tasks.
Edge Cases & Failure Modes
- C-state entry latency vs. wakeup latency: Deep C-states (C6, C7) have high exit latency (100s of µs); a real-time task requiring sub-100 µs response must set a
PM_QOS_CPU_DMA_LATENCYconstraint to prevent deep idle entry. - Idle task stack overflow: The idle task has a fixed kernel stack (8 KiB or 16 KiB); a buggy interrupt handler called in idle context that uses excessive stack causes a stack overflow without protection (unless
CONFIG_VMAP_STACKis set). - Tick granularity in nohz_full: On CPUs in
nohz_fullmode, re-entering the tick after long idle periods requires an IPI from another CPU, adding latency. - Intel C-state hardware bugs: Certain CPU stepping revisions have errata where entering C6 with specific hardware configurations causes system hangs; the kernel applies microcode workarounds or avoids the affected C-state.
Stop Scheduler (`kernel/sched/stop_task.c`)
The stop scheduler is the highest-priority scheduler class, running `stop_machine` tasks (threads named `migration/N`).
Definition
The stop scheduler is the highest-priority scheduler class, running stop_machine tasks (threads named migration/N). It is used for operations that must run exclusively on a CPU with all other activity stopped: CPU hotplug, scheduler migration operations, RCU quiescent state processing, and stop_machine() callbacks. Only one stop task exists per CPU.
Execution Flow
stop_one_cpu(cpu, fn, arg)orstop_machine(fn, arg, cpumask)is called.cpu_stop_workentries are prepared with the callbackfnand queued on the target CPU'sstopper->workslist.- The stop thread (
migration/Nfor CPU N) is woken viawake_up_process(). pick_next_task_stop()runs before all other scheduler classes; it preempts any running task immediately.- The stop task runs
fn(arg)in kernel thread context. - For
stop_machine(): all CPUs are synchronously stopped (viamulti_cpu_stop()using an atomic state machine); only the calling CPU executesfn(). - After
fn()returns, CPUs are released in reverse order; the stop task sleeps by setting its state toTASK_DEAD(stop task goes back to waiting).
Edge Cases & Failure Modes
- Nested
stop_machine()calls: Callingstop_machine()from within astop_machine()callback deadlocks (all CPUs are already stopped; the inner call cannot stop them again). - Stop task migration race: The stop task must run on its assigned CPU; if the CPU's affinity is changed while a stop work is pending, the work is never processed.
- Long
stop_machine()callbacks: Any code run insidestop_machine()runs with IRQs disabled on all CPUs; long-running callbacks cause visible system freezes and watchdog timeouts. stop_one_cpu_nowait()completion ordering: The async variant (_nowait) returns beforefn()completes; callers that assume immediate completion introduce subtle ordering bugs.
Core Scheduler Loop (`schedule()` / `kernel/sched/core.c`)
`schedule()` is the central context-switch function that runs the scheduler, selects the next task via `pick_next_tas…
Definition
schedule() is the central context-switch function that runs the scheduler, selects the next task via pick_next_task(), and performs the actual CPU context switch. It is the heart of the scheduler; every voluntary or involuntary context switch passes through it.
Execution Flow
schedule()→__schedule(sm)wheresmis the preempt mode (voluntary, preemption, idle).rq_lock(rq)acquires the run queue lock for the current CPU.deactivate_task()is called if the current task is not runnable (TASK_INTERRUPTIBLE,TASK_UNINTERRUPTIBLE).pick_next_task(rq, prev)calls the scheduler class chain: stop → deadline → rt → fair → idle; returns the highest-priority runnable task.clear_tsk_need_resched(prev)clears theTIF_NEED_RESCHEDflag.prepare_task_switch(rq, prev, next)runs pre-switch callbacks (e.g.,perf_event_task_sched_out()).context_switch(rq, prev, next)performs the actual switch:switch_mm_irqs_off(): switches page tables (CR3 on x86).switch_to(prev, next, prev): saves/restores CPU registers (rsp, rbp) and FPU state lazily; jumps tonext.- After
switch_to()returns, execution is on thenexttask's stack. finish_task_switch()releases the previous task's run queue lock and handles post-switch work.
Edge Cases & Failure Modes
schedule()in IRQ context: Callingschedule()within_interrupt()returning true causes a BUG; IRQ handlers must not sleep.TIF_NEED_RESCHEDmissed: Ifclear_tsk_need_resched()is called but the new task immediately re-sets the flag (e.g., a high-frequency timer fires duringfinish_task_switch()), the CPU loops back into__schedule()on the next kernel exit.- FPU state corruption: Lazy FPU save/restore means the FPU state is only saved when another task uses the FPU; if a task is migrated between CPUs while FPU state is not saved,
migrate_disable()/fpregs_lock()must be used. - Runqueue lock ordering violations: Locking two run queues simultaneously (required for cross-CPU task migration) must always be done in lowest-address-first order to prevent deadlock.
Load Balancer (`kernel/sched/fair.c` — `load_balance()`)
The CFS load balancer periodically redistributes tasks across CPUs and NUMA nodes to prevent imbalanced CPU utilization.
Definition
The CFS load balancer periodically redistributes tasks across CPUs and NUMA nodes to prevent imbalanced CPU utilization. It uses a hierarchical scheduling domain model (SMT ↔ Core ↔ Package ↔ NUMA node) and migrates tasks from the busiest CPU in the busiest domain to the idlest CPU, subject to cache affinity and task migration constraints.
Execution Flow
- Triggered by:
scheduler_tick()detecting CPU imbalance, ornewidle_balance()when a CPU becomes idle. load_balance(this_cpu, this_rq, sd, idle, continue_balancing)is called for the current scheduling domain.find_busiest_group()examines all CPUs in the scheduling domain, computes per-group load (using PELT: Per-Entity Load Tracking), and returns the group with the highest weighted load.find_busiest_queue()within the busiest group finds the CPU with the highestcfs_rq->avg.load_avg.detach_tasks()selects and removes up toimbalanceworth of load from the busiest queue, applying migration constraints (CPU affinity, cache hot threshold,numa_preferred_nid).attach_tasks()migrates the detached tasks tothis_rq.- If migration is blocked (all tasks on busiest CPU are CPU-affinity-pinned),
load_balance()returns a "failed" indicator and the domain is marked for re-check. - The process repeats for each outer scheduling domain level (Core → Package → NUMA).
Edge Cases & Failure Modes
- Affinity pinning creates permanent imbalance: If all tasks on a CPU are pinned to that CPU, the load balancer cannot fix the imbalance and repeatedly fails;
nr_balance_failedincrements until aactive_load_balance_cpu_stop()migration is attempted (which also fails, causing a stall). - Scheduler domain misconfiguration (topology): An incorrect
sched_domain_topology_levelarray (e.g., after CPU hotplug that doesn't rebuild topology) causes domains to cover wrong CPU sets, leading to migrations that degrade cache performance. - NUMA Imbalance vs. load imbalance: The NUMA balancer (task_numa_work) may conflict with the load balancer's decisions; a task may be migrated by both, negating each other's work.
- Nohz imbalance: CPUs in
nohz_fullmode don't run the scheduler tick; their load is not updated until they exit idle;nohz_kick_needed()/nohz_balancer_kick()asynchronously trigger a rebalance via IPI.
NUMA Balancer (`kernel/sched/numa_balancing.c`)
The NUMA balancer (`CONFIG_NUMA_BALANCING`) scans a process's page mappings periodically, marks pages as NUMA-fault-e…
Definition
The NUMA balancer (CONFIG_NUMA_BALANCING) scans a process's page mappings periodically, marks pages as NUMA-fault-eligible (by clearing PTE access bits), waits for access faults, and uses fault locations to infer which NUMA node the task accesses most. It then migrates both the task and its pages to the preferred NUMA node to reduce remote memory access latency.
Execution Flow
task_tick_fair()callstask_tick_numa(rq, curr, queued)on each scheduler tick.numa_work_next_cpu()queues anuma_workon the task viatask_work_add().- When the task returns to userspace,
task_numa_work()scans a portion of the task's page tables viachange_prot_numa(), converting PTEs to_PAGE_NUMA(access-cleared). - The next access to such a page triggers a NUMA fault (page fault with
pte_numa()set). do_numa_page()→mpol_misplaced()determines if the page should be migrated.migrate_misplaced_page()moves the page to the task's preferred NUMA node.- NUMA hint statistics (
task->numa_faults[]) are updated;numa_migrate_preferred()checks if the task should be migrated to the node holding most of its pages. task_numa_migrate()callsmigrate_task_to()to move the task itself.
Edge Cases & Failure Modes
- NUMA thrashing: Two tasks repeatedly swap NUMA nodes to follow each other's shared pages, causing continuous migration overhead;
sched_numa_balancingcan be disabled per-cgroup. - False-negative scan: If a task's working set exceeds the scan window, many hot pages are never promoted; the scan rate is adaptive but may lag for memory-intensive workloads.
- Migration stall under memcg limits: Page migration requires allocation of a new page; if the destination NUMA node's memcg limit is reached, migration fails and the fault penalty is wasted.
- Interaction with huge pages: NUMA fault handling on a THP requires splitting the huge page first; this defeats THP's purpose and can cause performance regression.
cgroup CPU Controller (`kernel/cgroup/cpu.c`)
The cgroup CPU controller (v1: `cpu` controller; v2: unified hierarchy) limits and prioritizes CPU access for groups …
Definition
The cgroup CPU controller (v1: cpu controller; v2: unified hierarchy) limits and prioritizes CPU access for groups of tasks. In v2, it provides cpu.weight (CFS nice-equivalent weight), cpu.max (bandwidth limiting: maximum runtime per period), and cpu.uclamp.min/max (frequency scaling hints). It operates by embedding cgroup-level sched_entity objects into the CFS hierarchy.
Execution Flow
- A cgroup is created:
mkdir /sys/fs/cgroup/mygroup. - Tasks are added:
echo PID > /sys/fs/cgroup/mygroup/cgroup.procs. - CFS creates a per-CPU
task_groupwith acfs_rq(group-level run queue) and asched_entity(group entity on the parent run queue). - When a task in the group is scheduled: CFS selects the group entity from the parent
cfs_rq(based on group vruntime), then selects a task entity from the group'scfs_rq. - Bandwidth enforcement (
cpu.max):cfs_bandwidth_workruns periodically; when the group has used itsquotawithin theperiod,throttle_cfs_rq()is called → all tasks in the group are dequeued. - At the next period start,
unthrottle_cfs_rq()re-enqueues all throttled tasks. cpu.weightadjusts the group entity'sse.load.weight, proportionally scaling vruntime advance rate.
Edge Cases & Failure Modes
- Bandwidth throttling cliff: A cgroup that hits its
cpu.maxquota in the first millisecond of a 100 ms period is throttled for the remaining 99 ms, causing application-visible latency spikes even when total CPU is available. - Hierarchical weight interaction: Nested cgroups accumulate weights multiplicatively; a deeply nested cgroup may have a de facto weight of near zero regardless of its own
cpu.weightsetting. - RT tasks bypass cgroup limits:
SCHED_FIFO/SCHED_RRtasks are not subject tocpu.max; they can exceed the cgroup's intended CPU budget. - v1 / v2 incompatibility: The
cpucontroller cannot be simultaneously mounted in v1 and v2 hierarchies; a system using systemd's cgroup v2 must not also mount the legacy v1cpuhierarchy.
Context Switch / `switch_to()` Mechanism (`arch/x86/include/asm/switch_to.h`)
`context_switch()` and its architecture-specific `switch_to(prev, next, last)` macro implement the CPU register save/…
Definition
context_switch() and its architecture-specific switch_to(prev, next, last) macro implement the CPU register save/restore that transfers execution from one task to another. It saves the current task's stack pointer (rsp), instruction pointer (implicitly via the return address), and optionally FPU state, then restores the next task's saved state.
Execution Flow
context_switch(rq, prev, next)inkernel/sched/core.cis called withrq->lockheld.prepare_task_switch(rq, prev, next)runs perf/cgroup/trace hooks.- If
nexthas a different address space:switch_mm_irqs_off(prev->active_mm, next->mm, next)→ updatesCR3(x86) withnext->mm->pgdphysical address, flushing TLB entries (or using PCID/ASID to avoid a full flush). switch_to(prev, next, prev)(assembly macro):- Pushes callee-saved registers (
rbp,rbx,r12–r15) ontoprev's kernel stack. - Saves
rsptoprev->thread.sp. - Loads
rspfromnext->thread.sp(now onnext's kernel stack). - Calls
__switch_to_asm()→__switch_to()which updates theTSS.sp0field (kernel stack pointer for syscall entry), loadsnext'sfsbase/gsbase. retonnext's stack returns to wherevernextlast calledschedule()(or toret_from_forkfor a new task).- After
switch_to()returns (now running asnext):finish_task_switch(prev)releasesprev's lock state and handles task cleanup.
Edge Cases & Failure Modes
- FPU state corruption without lazy save: The kernel uses lazy FPU save/restore; if a task is migrated between CPUs while FPU state is not saved (because no other task used the FPU),
fpregs_assert_state_consistent()will BUG. - Stack corruption during switch: A stack overflow in
prevthat overwrites the savedrspcauses the CPU to jump to a garbage address whenswitch_to()loads the corrupted stack pointer.CONFIG_VMAP_STACKplaces a guard page under each stack to catch this. - CR3 update and speculative execution (Spectre/Meltdown): On CPUs without hardware PCID support, every
switch_mmflushes the entire TLB; this is expensive for applications with large working sets;CONFIG_PAGE_TABLE_ISOLATION(PTI/KPTI) adds further overhead for user/kernel page table separation. lastpointer aliasing:switch_to(prev, next, prev)returns withprevpointing to the task that was running beforenextwoke, which may differ from the task that calledswitch_to()if another task ran between them; callers must use the returnedprev(via thelastoutput parameter) for cleanup, not the caller's local variable.
# Linux Kernel Component Taxonomy — Part 2 (Categories 5–8)
S5 — Block & I/O Schedulers
10 componentsblk-mq (Multi-Queue Block Layer) (`block/blk-mq.c`)
blk-mq is the modern block layer infrastructure introduced in Linux 3.13 that replaces the single-queue block layer.
Definition
blk-mq is the modern block layer infrastructure introduced in Linux 3.13 that replaces the single-queue block layer. It maps one software staging queue per CPU (or per NUMA node) to multiple hardware dispatch queues on the storage device, eliminating the single global queue lock bottleneck and enabling high-IOPS NVMe SSDs to use full parallelism.
Execution Flow
- A filesystem or direct I/O caller submits a
biotosubmit_bio(). blk_mq_submit_bio()splits the bio if it exceeds queue limits, then callsblk_mq_get_request()to allocate astruct requestfrom the per-CPU request pool.- The request is inserted into the per-CPU software staging queue (
ctx->rq_list). blk_mq_run_hw_queue()is called: it drains the software queue into the hardware dispatch queue (hctx->dispatch).- If an I/O scheduler is attached,
e->type->ops.insert_requests()is called (e.g., BFQ sorts by deadline/priority). blk_mq_dispatch_rq_list()calls the driver'squeue_rq()callback with a batch of requests.- The driver submits requests to hardware (NVMe SQ doorbell, SCSI command queue, etc.).
- Hardware completes I/O, raises an interrupt;
blk_mq_complete_request()is called, which calls the bio'sbi_end_iocallback, waking the submitting task.
Edge Cases & Failure Modes
- Request tag exhaustion: Each hardware queue has a fixed tag depth; if all tags are in-flight, new requests block in
blk_mq_get_tag()on thehctx->tags->bitmap_tagswait queue. - Queue quiesce deadlock:
blk_mq_quiesce_queue()waits for all in-flight requests to complete; if called from a context that holds a resource a completing request needs (e.g., a filesystem lock), it deadlocks. - CPU hotplug and per-CPU queue migration: When a CPU goes offline, its software queue must be drained to another CPU's queue;
blk_mq_hctx_notify_dead()handles this but races with concurrent submissions. - Plug/unplug coalescing failure:
blk_start_plug()/blk_finish_plug()batch requests before dispatch; a process that starts a plug and exits without callingblk_finish_plug()leaves requests stranded until the plug is flushed atschedule().
BFQ (Budget Fair Queueing) I/O Scheduler (`block/bfq-iosched.c`)
BFQ is a proportional-share I/O scheduler that assigns a "budget" (number of sectors) to each process's I/O queue and…
Definition
BFQ is a proportional-share I/O scheduler that assigns a "budget" (number of sectors) to each process's I/O queue and serves them in order of budget, while maintaining low latency for interactive and soft-real-time workloads. It tracks per-process I/O queues (bfq_queue) organized in a hierarchical weight-fair tree with time-slice based service.
Execution Flow
- A request arrives:
bfq_insert_request()places it in the submitting process'sbfq_queue, sorted by LBA (for seek optimization). - The
bfq_queueis inserted into the BFQ service tree (a Red-Black tree ordered by virtual finish time, computed from budget and weight). bfq_select_queue()selects the queue with the minimum virtual finish time that has pending requests and whose budget has not expired.- The selected queue is "in service"; its requests are dispatched to the blk-mq hardware queue via
bfq_dispatch_request(). - After
budgetsectors are served (or a think-time timeout fires), the queue's virtual finish time is advanced and it is re-inserted into the service tree. - Idle detection: BFQ waits a brief "slice_idle" period for the in-service process to submit a new request (to maintain request locality); if none arrives, the next queue is selected.
Edge Cases & Failure Modes
- Latency cliff for interactive tasks: If a large sequential background I/O workload gets a large budget, it monopolizes the disk for many milliseconds; BFQ's "low_latency" heuristic attempts to detect and throttle such workloads, but misclassification causes latency spikes.
- Weight starvation in hierarchical scheduling: A cgroup with low
blkio.bfq.weightmay starve if a high-weight sibling continuously issues I/O; the starvation is bounded by BFQ's fairness guarantee but can still cause multi-second delays. - bfq_queue split on shared access: When multiple processes share the same
bfq_queue(cooperative scheduling), a synchronization point split is needed; missing a split leaves one process's I/O blocking another's. - Think-time estimation error: BFQ uses per-queue think-time statistics to decide whether to wait for more I/O; on SSDs with microsecond latency, the think-time window is too coarse and BFQ may switch queues unnecessarily.
mq-deadline I/O Scheduler (`block/mq-deadline.c`)
mq-deadline is the multi-queue adaptation of the classic deadline scheduler.
Definition
mq-deadline is the multi-queue adaptation of the classic deadline scheduler. It maintains two per-direction (read/write) sorted queues: a Red-Black tree ordered by LBA (for sequential merging) and a FIFO queue ordered by submission time (for deadline enforcement). Requests are served from the LBA-sorted tree but are "expired" to the FIFO head if their deadline is reached.
Execution Flow
- A request arrives:
dd_insert_request()inserts it into both the LBA RB-tree and the FIFO queue for its direction (read or write). dd_dispatch_request()is called by blk-mq when the hardware queue needs requests.- Deadline check: the front of the read FIFO is examined; if its deadline (
jiffies + read_expire, default 500 ms) has passed, it is dispatched immediately (deadline enforcement). - Write starvation check: if writes have been starved for
writes_starved(default 2) read batches, force a write dispatch. - Otherwise,
dd_dispatch_prio_aged_requests()dispatches from the LBA RB-tree to maximize sequential access patterns (elevator-style seek optimization). - After
fifo_batch(default 16) consecutive requests from one direction, the scheduler switches to the other direction.
Edge Cases & Failure Modes
- Read/write inversion on SSDs: mq-deadline was designed for rotational media where sequential access is faster; on NVMe SSDs, seek optimization is irrelevant, and the LBA sorting adds overhead without benefit. The
nonescheduler is often better for NVMe. - Write starvation under heavy read load: If
writes_starvedis set too high, write requests can be delayed far beyond their deadline; dirty-page writeback stalls and VFS write syscalls block. - FIFO queue ordering on multi-queue devices: With multiple hardware queues, the FIFO ordering guarantee breaks across queues; a request submitted earlier may be on a different queue than a later request, violating the deadline ordering assumption.
- Deadline expiry on power-loss-safe SSDs: Power-loss-safe NVMe drives buffer writes in DRAM; a "written" request may not reach flash until a later flush; the deadline scheduler does not account for this, so apparent completion time differs from physical persistence time.
Kyber I/O Scheduler (`block/kyber-iosched.c`)
Kyber is a lightweight I/O scheduler designed for fast storage (NVMe, optane).
Definition
Kyber is a lightweight I/O scheduler designed for fast storage (NVMe, optane). Rather than sorting by LBA, it uses token-based rate limiting across two priority domains: "synchronous read" (latency-sensitive) and "other" (background). It targets specific per-domain latency goals and throttles the lower-priority domain when target latencies are exceeded.
Execution Flow
- Requests are classified into domains:
KYBER_READ(sync reads) orKYBER_WRITE(writes/async). kyber_bio_merge()attempts to merge incoming bios with pending requests.kyber_dispatch_request()acquires a token from the per-domainsbitmap_queue(a semaphore-like token bucket per hardware queue context).- If tokens are available for the high-priority domain, its requests are dispatched first.
- The latency sampler (
kyber_latency_timer_fn()) runs periodically: measures recent per-domain completion latencies againstread_lat_nsecandwrite_lat_nsectargets. - If a domain's latency exceeds its target,
kyber_adjust_rq_dispatches()increases that domain's token budget; if latency is well below target, tokens are reduced. - This feedback loop maintains target latencies dynamically without explicit request sorting.
Edge Cases & Failure Modes
- Token starvation feedback loop: If the latency target is set too aggressively (e.g., 100 µs for a device with 200 µs baseline), the latency controller continuously over-provisions tokens, overloading the device queue and worsening latency.
- Domain mis-classification: Writes issued as
REQ_SYNC(e.g.,fsyncmetadata writes) are classified as synchronous but share a token bucket with background writes, defeating prioritization. - Low queue depth devices: On rotational or emulated NVMe devices with small queue depths (QD=1), Kyber's token system does not improve over
none; the hardware serializes everything regardless. - Multi-actuator drive unsupported: New multi-actuator HDDs (e.g., Seagate MACH.2) present multiple independent actuators; Kyber has no actuator-aware dispatch path, treating both actuators as a single queue.
None / NOOP I/O Scheduler (`block/noop-iosched.c` / `block/mq-deadline.c`)
The `none` scheduler (blk-mq era) passes requests directly from the blk-mq software queues to the hardware dispatch q…
Definition
The none scheduler (blk-mq era) passes requests directly from the blk-mq software queues to the hardware dispatch queues in FIFO order with minimal overhead. It performs no sorting, no deadline enforcement, and no prioritization. Historically called noop in the single-queue era. Optimal for devices with their own sophisticated internal schedulers (NVMe controllers, SSDs with FTL).
Execution Flow
bio→blk_mq_submit_bio()→ request allocation.noop_insert_request()appends the request to the per-hardware-queue dispatch list (hctx->dispatch).noop_dispatch_request()dequeues from the front of the list (pure FIFO).- The request is passed to the driver's
queue_rq(). - No latency tracking, no reordering, no merging decisions beyond bio merging at the blk-mq layer.
- Completion:
blk_mq_complete_request()→bio->bi_end_io().
Edge Cases & Failure Modes
- Request ordering on rotational media: Using
noneon a spinning hard disk causes random-seek workloads with severe throughput degradation (e.g., 300 IOPS vs. 150 IOPS for sequential); mq-deadline or BFQ should be used instead. - Write ordering for fsync correctness: The
nonescheduler does not enforce write ordering beyond what the driver provides; on devices without FUA (Force Unit Access) support,fsyncmay complete before data is persistent. - Starvation of low-priority requests: Without any fairness mechanism, a high-throughput process issuing many requests can delay latency-sensitive requests indefinitely; the
nonescheduler has no mitigation. - Hot-swap scheduler (online change): The scheduler can be changed at runtime via
/sys/block/sdX/queue/scheduler; changing from BFQ tononeon a busy disk flushes in-flight BFQ queues immediately, which can cause a brief I/O pause.
`bio` Layer (`block/bio.c`)
A `bio` (Block I/O) is the fundamental unit of I/O in the Linux block layer.
Definition
A bio (Block I/O) is the fundamental unit of I/O in the Linux block layer. It describes a scatter-gather I/O operation: a list of bio_vec entries (each specifying a page, offset, and length), a target block device and start sector, and direction flags. The bio layer handles splitting, merging, and cloning of I/O operations before they reach the I/O scheduler.
Execution Flow
bio_alloc(gfp, nr_vecs)allocates a bio with space fornr_vecspage vectors from the bio slab or mempool.bio_add_page(bio, page, len, offset)adds a page vector entry; if the new entry is physically contiguous with the last, they are merged into onebio_vec.submit_bio(bio)enters the block layer:blk_mq_submit_bio()checks queue limits (max sectors, max segments).- If the bio exceeds limits:
bio_split()creates two bios; the second is resubmitted recursively. - Bio merging:
blk_attempt_plug_merge()tries to merge the new bio with an existing request on the plug list (front/back merge by sector adjacency). - After merging decisions, the bio is converted to a
requestand enters the I/O scheduler. - On completion: the driver calls
bio_endio(bio, error)→bio->bi_end_io(bio). - For split bios:
bio_chain()links parent/child; the parent'sbi_end_iofires only after all children complete.
Edge Cases & Failure Modes
- bio_vec segment limit overflow: A bio is bounded by
queue_max_segments(); exceeding it requires splitting. Drivers that don't check the bio segment count before DMA mapping will produce DMA errors or memory corruption. - High-memory page mapping: On 32-bit kernels,
bio_vecpages inZONE_HIGHMEMrequirekmap_atomic()to access; failing to unmap causes permanent kmap slot exhaustion. - bio cloning for mirroring (DM/MD):
bio_clone_fast()creates a bio that shares the original's page vector but has an independent completion; mishandling the clone's reference counting causes use-after-free in the original bio's page data. - Partial completion handling: A device that completes only part of a bio (e.g., a device with a sector boundary error) calls
bio_advance()to update the remaining range; callers that don't handle partial completions may submit the already-completed range again.
Request Queue (`block/blk-core.c`, `include/linux/blkdev.h`)
The `request_queue` (`struct request_queue`) is the central data structure of the block layer for a given block device.
Definition
The request_queue (struct request_queue) is the central data structure of the block layer for a given block device. It holds the blk-mq tag sets, hardware queue contexts (blk_mq_hw_ctx), queue limits (max sectors, max segments, logical/physical block size), and the I/O scheduler state. All block I/O operations for a device are funneled through its request_queue.
Execution Flow
- At device registration:
blk_mq_init_queue()allocates arequest_queueand sets its limits fromblk_mq_tag_set(driver-provided: queue depth, number of hardware queues, etc.). blk_queue_max_hw_sectors(),blk_queue_physical_block_size(), etc., configure the queue's operational limits.- An I/O scheduler is attached:
elevator_init_mq()setsq->elevator. - I/O submission:
submit_bio()→blk_mq_submit_bio()→ routes throughq->mq_ops->queue_rq(). - Queue freeze (
blk_freeze_queue()): stops new I/O submission and waits for in-flight I/O to drain (used during driver suspend, error recovery, scheduler change). - Queue drain (
blk_drain_queue()): waits for all requests to complete. - Queue teardown (
blk_cleanup_queue()): on device removal, drains the queue, destroys tag sets, frees therequest_queue.
Edge Cases & Failure Modes
- Queue limits violation: A filesystem that caches
queue_max_sectors()at mount time and doesn't re-query after a live queue limits change (e.g., after a hardware reconfiguration) may submit oversized bios that require splitting, reducing performance. - Request queue stall on tag exhaustion: When all blk-mq tags are in-flight, new requests block; if the device never completes a request (firmware hang), the queue stalls permanently.
blk_abort_request()and device reset paths exist but are complex. - Queue freeze deadlock: Calling
blk_freeze_queue()from within a bio completion callback deadlocks: completion callbacks run while the queue is active; a freeze waiting for active I/O to drain is blocked by the caller holding the callback context. - Rotational flag and elevator selection: Setting
q->rotational = 0signals that the device is non-rotational; the kernel uses this to select a default scheduler (nonefor NVMe,mq-deadlinefor rotational). An incorrect flag causes the wrong default scheduler.
I/O Barriers / Write Ordering (`block/blk-flush.c`)
I/O barriers (now implemented as flush sequences in blk-mq) ensure write ordering and durability.
Definition
I/O barriers (now implemented as flush sequences in blk-mq) ensure write ordering and durability. A "flush" operation forces the device's write cache to persistent storage. A "FUA" (Force Unit Access) write bypasses the write cache for a single request. These are used by filesystems (ext4, XFS, btrfs) and databases to implement journaling and fsync guarantees.
Execution Flow
- A filesystem calls
blkdev_issue_flush()or submits a bio withREQ_PREFLUSH | REQ_FUA. blk_insert_flush()checks the device's flush/FUA capabilities inq->queue_flags(QUEUE_FLAG_WC= write cache,QUEUE_FLAG_FUA= FUA support).- If neither is supported: the flush is a no-op (all writes are already cache-less).
- If FUA is supported but
REQ_PREFLUSHis set: a FLUSH command is dispatched first; the data write follows with the FUA bit set in the command. - The flush sequence state machine (
blk_flush_complete_seq()) processes three phases:REQ_FSEQ_PREFLUSH(send flush),REQ_FSEQ_DATA(send data writes),REQ_FSEQ_POSTFLUSH(optional trailing flush). - Flush coalescing: multiple concurrent flush requests are coalesced into one hardware flush command to reduce overhead.
- On flush completion:
blk_flush_complete_seq()advances all coalesced requests to the data phase.
Edge Cases & Failure Modes
- Flush coalescing window race: Two
fsync()calls that arrive nanoseconds apart may land in different flush batches; the second process may wait for a full extra flush cycle, adding latency. - Device reports FUA support but doesn't implement it: Some storage devices (especially in virtual environments) advertise FUA support but handle it as a no-op; writes "completed" with FUA may not be persistent on power loss. Databases have been bitten by this.
REQ_PREFLUSHoverhead on tmpfs: Filesystems mounted ontmpfsorramfsbypass the block layer entirely;blkdev_issue_flush()returns immediately without a syscall. Callers must check the mount type.- Flush timeout on faulty device: If a device takes too long to complete a cache flush (e.g., a failing SSD with a large write buffer), the block layer timeout fires, the request is aborted, and the filesystem sees an I/O error on
fsync().
Device Mapper (`drivers/md/dm.c`)
Device Mapper (DM) is a kernel framework that creates virtual block devices by mapping I/O operations to one or more …
Definition
Device Mapper (DM) is a kernel framework that creates virtual block devices by mapping I/O operations to one or more underlying real block devices according to configurable mapping tables. It underpins LVM2 (logical volume management), dm-crypt (full-disk encryption), dm-multipath (multipath I/O), and dm-thin (thin provisioning).
Execution Flow
- A DM device is created:
dm_create()allocates amapped_deviceand agendisk; a mapping table is loaded viaioctl(DM_TABLE_LOAD_CMD). - The table is a list of
dm_targetentries, each covering a sector range and naming a target type (e.g.,linear,crypt,thin). - I/O submission:
dm_make_request()intercepts bios destined for the DM device. dm_map_bio()looks up the target for the bio's start sector in the table's sector-range tree.- The target's
.map()callback transforms the bio: remaps the sector number and device pointer (forlinear), applies encryption (forcrypt), or handles copy-on-write (forsnapshot). - The transformed bio is re-submitted to the underlying device via
submit_bio(). - On completion: the target's optional
.end_io()callback runs; thendm_io_dec_pending()decrements the reference count and completes the original bio.
Edge Cases & Failure Modes
- Table reload race:
dm_swap_table()replaces the active mapping table atomically; in-flight I/O on the old table continues using the old target references until all I/O completes. Adm_suspend()/dm_resume()cycle is needed for a clean swap. - dm-crypt bio splitting overhead: dm-crypt splits bios to align with its crypto block size; on workloads with many small I/Os, this produces 2× the number of bios and can saturate the dm-crypt workqueue.
- dm-thin provisioning ENOSPC: When the thin pool runs out of space, new writes to thin volumes return
EIOimmediately; the filesystem must handle this gracefully (most ext4/XFS implementations do, but applications that assume ENOSPC is impossible may crash). - dm-multipath path failure during I/O: If a path fails while I/O is in-flight on it, dm-multipath must requeue the in-flight I/O on another path; some storage arrays have windows where both the original and retry I/O complete, causing duplicate writes.
MD RAID Layer (`drivers/md/raid*.c`, `drivers/md/md.c`)
The MD (Multiple Devices) RAID layer implements software RAID levels (0 through 10 and their variants) entirely in th…
Definition
The MD (Multiple Devices) RAID layer implements software RAID levels (0 through 10 and their variants) entirely in the kernel. Each MD array is a virtual block device with a stripe-based mapping across N physical member devices. MD handles data striping, mirroring, parity computation (for RAID-5/6), resync, reshape, and recovery from device failures.
Execution Flow
- Array assembly:
md_run()reads superblocks from each member device, validates the configuration, and starts the RAID personality (raid5_run(),raid1_run(), etc.). - I/O submission:
md_make_request()intercepts bios; the RAID personality'smake_request()(e.g.,raid5_make_request()) determines the stripe number and position. - For RAID-5: a
stripe_headis allocated for the target stripe; partial writes trigger a read-modify-write cycle (read old data and parity, XOR in new data, write new data + new parity). - The stripe cache (hash table of
stripe_headobjects) coalesces multiple bios targeting the same stripe. - Completed stripe I/O:
raid5_end_read_request()/raid5_end_write_request()update stripe state; when all required I/O is done,handle_stripe()advances the stripe state machine. - Device failure:
md_error()marks the failing device; RAID-1/5/6 continues degraded;md_check_recovery()starts a resync to rebuild the missing data on a hot spare.
Edge Cases & Failure Modes
- RAID-5 write hole: If power fails between writing the new data chunk and writing the new parity, the array is inconsistent; the kernel mitigates this with journal devices (
raid5_journal) or by writing a "partial parity log" (PPL). - Stripe cache deadlock: If the stripe cache is full and all stripes are waiting for I/O that itself requires new stripe cache entries, the array deadlocks; the kernel limits in-flight stripes via the
stripe_hash_locks/conf->max_nr_stripessemaphore. - Bitmap-assisted resync: The write-intent bitmap tracks which stripe regions need resync after a crash; a corrupted bitmap causes a full resync on every boot, adding hours of latency.
- RAID-6 double-disk failure during resync: If a second disk fails while the array is degraded (one disk already failed), RAID-6 can still recover; RAID-5 cannot and marks the array as "failed," making data inaccessible until the failed disks are restored.
S6 — Virtual Filesystems (VFS)
10 componentsDentry Cache (dcache) (`fs/dcache.c`)
The dentry cache is an in-memory cache of directory entry objects (`struct dentry`), each mapping a filename componen…
Definition
The dentry cache is an in-memory cache of directory entry objects (struct dentry), each mapping a filename component to its inode. It implements the VFS name lookup fast path: lookup_fast() checks the dcache hash table before hitting the filesystem. The cache is bounded by memory and uses LRU eviction under pressure.
Execution Flow
- Pathname lookup begins:
path_lookupat()callswalk_component()for each path component. lookup_fast()hashes the (parent dentry, name) pair and checksdentry_hashtablewith RCU read lock.- Cache hit: a dentry is found and reference-counted via
lockref_get_not_dead(); the lookup returns immediately without filesystem I/O. - Cache miss:
lookup_slow()acquiresparent->d_inode->i_rwsem, callsd_lookup()again under lock (to close a race), then calls the filesystem'sinode_operations->lookup(). - The filesystem reads the directory entry and calls
d_add()ord_splice_alias()to insert a new dentry into the cache. - Dentry eviction: under memory pressure,
shrink_dcache_sb()/dcache_shrinkercallsdentry_kill()on unused (zero-refcount) dentries in LRU order. - Negative dentries (for nonexistent files) are also cached to avoid repeated "file not found" disk lookups; they expire via timer or explicit
d_invalidate().
Edge Cases & Failure Modes
- Dentry leaks: A module that calls
d_lookup()without a matchingdput()increments the dentry's reference count permanently; the dentry is never evicted, slowly growing the dcache without bound. - Stale negative dentry after create: If a negative dentry (caching "file not found") exists and the file is then created on the same mount, the negative dentry must be invalidated; NFS-mounted directories with dcache_invalidate disabled may serve stale negatives for the full
actimeotimeout. - Alias dentries on hardlinks: Multiple dentries can point to the same inode (hardlinks);
d_find_alias()finds all aliases; operations that must be coherent across aliases (e.g.,rename()) must lock all aliases. - Dentry hash table scalability: Under extreme parallelism (millions of files, many threads doing concurrent lookups), the global dentry hash table lock becomes a scalability bottleneck; RCU-based lookup mitigates but does not eliminate this.
Inode Cache (`fs/inode.c`)
The inode cache stores `struct inode` objects in memory, representing files and directories independently of their na…
Definition
The inode cache stores struct inode objects in memory, representing files and directories independently of their names. Each inode holds file metadata (size, permissions, timestamps, block pointers) and operation function pointer tables. The cache uses a hash table (keyed by sb + ino) and an LRU list for eviction.
Execution Flow
iget_locked(sb, ino)checksinode_hashtablefor an existing inode; if found, returns a locked reference.- On cache miss:
alloc_inode()→sb->s_op->alloc_inode()allocates a filesystem-specific inode struct (embedded or separate fromstruct inode). - The inode is added to the hash table and marked
I_NEW; the caller must callsb->s_op->read_inode()(or its equivalent) to populate the inode from disk. unlock_new_inode()clearsI_NEW, waking any waiters that were blocked onwait_on_inode().- Normal usage:
iget_locked()returns the locked inode; the caller increments its reference count viaihold()and stores it in a dentry. - When all references drop:
iput_final()callssb->s_op->evict_inode()to write back dirty data and release filesystem-specific state. - The inode struct is then returned to the inode cache's slab (
inode_cachep) or freed if the cache is under pressure.
Edge Cases & Failure Modes
- Inode number reuse race: After
iput()removes an inode from the cache, a new file created on the filesystem may reuse the same inode number; a concurrentiget_locked()call racing with the eviction may return the old, partially-cleared inode. I_DIRTYwriteback ordering: An inode is markedI_DIRTY_DATASYNCon a metadata write; ifevict_inode()is called before writeback completes,write_inode_now()must be called to flush dirty metadata.- Filesystem-specific inode allocation failure: If
s_op->alloc_inode()fails (OOM),iget_locked()returnsERR_PTR(-ENOMEM); callers that don't check the error create a NULL pointer dereference. - Inode cache over-retention: Large filesystems with millions of inodes can fill the inode cache; the
inode_shrinkerevicts inodes but can be slow; a "dentry/inode storm" (rapidly creating and deleting files) can exhaust the slab allocator.
Page Cache (`mm/filemap.c`)
The page cache (address space cache) stores filesystem pages in memory indexed by `(inode, page_index)` pairs in a pe…
Definition
The page cache (address space cache) stores filesystem pages in memory indexed by (inode, page_index) pairs in a per-inode address_space XArray. It acts as the read/write cache for file I/O: reads check the cache first; writes go into cache (dirty) and are written back asynchronously by pdflush/writeback threads. It is also used for memory-mapped files.
Execution Flow
filemap_get_pages()(called fromgeneric_file_read_iter()) looks up the page ininode->i_mappingXArray.- Cache hit: the page is returned; its reference count is incremented.
- Cache miss:
page_cache_alloc()allocates a new page;add_to_page_cache_lru()inserts it into the XArray and the LRU list. a_ops->readpage()/readahead()submits I/O to populate the page from disk.- The calling task waits on the page's
PG_lockedbit viawait_on_page_locked(); when I/O completes, the driver callsunlock_page(). - The page is returned;
copy_page_to_iter()copies data to the userspace buffer. - Write path:
generic_perform_write()→a_ops->write_begin()locks the page; data is copied from userspace;a_ops->write_end()marks the pagePG_dirty. balance_dirty_pages_ratelimited()throttles the writer if dirty ratio thresholds are exceeded.- Writeback:
wb_writeback()callsa_ops->writepages()to submit dirty pages to the block layer.
Edge Cases & Failure Modes
- Page cache coherence with direct I/O:
O_DIRECTbypasses the page cache; a file opened withO_DIRECTwhile another fd has it open with buffered I/O can read stale cached data. The kernel partially invalidates the cache before direct I/O but cannot guarantee coherence during concurrent access. - Dirty ratio threshold exhaustion: If the dirty ratio (
vm.dirty_ratio) is exceeded, the writing process is throttled inbalance_dirty_pages(); under extreme write pressure, all processes writing to disk may be throttled simultaneously, causing application-visible stalls. - Page writeback error handling: If writeback fails (e.g., network filesystem timeout),
mapping_set_error()records the error; subsequentfsync()/close()calls return the error. But if the error is not consumed between twoclose()calls, the second call may succeed without seeing the error (Linux 5.1+errseq_tfixes this). - Page eviction under mmap: A page that is simultaneously in the page cache and mapped into a process's address space cannot be evicted until the mapping is removed;
try_to_unmap()must succeed beforeshrink_page_list()can reclaim it.
VFS `open()` Path (`fs/open.c`, `fs/namei.c`)
The VFS `open()` path is the kernel's implementation of `open(2)` / `openat(2)`: it resolves a pathname to an inode, …
Definition
The VFS open() path is the kernel's implementation of open(2) / openat(2): it resolves a pathname to an inode, checks permissions, allocates a struct file, invokes the filesystem's open handler, and returns a file descriptor. It is one of the most complex kernel paths, involving dentry/inode caches, LSM hooks, O_CREAT file creation, and symlink resolution.
Execution Flow
sys_openat2()→do_sys_open()→do_filp_open()→path_openat().path_init()establishes the starting dentry (root/or current working directory).link_path_walk()resolves each component: for each slash-delimited name, callswalk_component()→lookup_fast()→ (on miss)lookup_slow().- Symlink resolution: each symlink encountered calls
pick_link()→ recursively resolves the symlink target (up toMAXSYMLINKS = 40depth). - At the final component: if
O_CREATis set,atomic_open()orlookup_open()is called; if the file doesn't exist,vfs_create()→inode_ops->create()creates it. vfs_open()→do_dentry_open(): checksinode_permission()(DAC + LSM hooks); callsf->f_op->open(inode, file).- A file descriptor is allocated from the process's
fdtableviaget_unused_fd_flags(). fd_install(fd, file)atomically places thestruct file *into the fdtable.
Edge Cases & Failure Modes
- TOCTOU (time-of-check/time-of-use) races: Between
path_lookupat()andvfs_open(), the filesystem state can change;O_NOFOLLOWandopenat2()withRESOLVE_NO_SYMLINKSreduce the attack surface but cannot eliminate all races. - Too many open files:
get_unused_fd_flags()returnsEMFILEwhen the process'sfdtableis full (up toRLIMIT_NOFILE); the filesystem'sinode_ops->create()may have already run, leaving a created-but-unreachable file. O_CREAT | O_EXCLrace: Two processes simultaneously callingopen(path, O_CREAT|O_EXCL)on the same path; only one succeeds; the filesystem'satomic_open()orinode_ops->create()must use an atomic create mechanism to avoid creating duplicate files.- Pathname too long: Pathname components are bounded by
NAME_MAX(255 bytes); the full path byPATH_MAX(4096 bytes); exceeding these returnsENAMETOOLONGbefore any filesystem I/O.
VFS `read()` / `write()` (`fs/read_write.c`)
The VFS `read(2)` and `write(2)` paths dispatch file I/O through the `file->f_op->read_iter` / `write_iter` interface…
Definition
The VFS read(2) and write(2) paths dispatch file I/O through the file->f_op->read_iter / write_iter interface, which all modern kernel filesystems implement. This abstraction supports regular file I/O (page cache), direct I/O, pipe I/O, and character device I/O through the same syscall interface via iov_iter.
Execution Flow
sys_read(fd, buf, count)→ksys_read()→vfs_read().file_pos_read(f)reads and locks the current file position (f->f_pos).rw_verify_area(): verifies the file is open for the requested direction; checks mandatory locks; callssecurity_file_permission()(LSM hook).call_read_iter(f, &kiocb, &iter)→f->f_op->read_iter(&kiocb, &iter).- For regular files:
generic_file_read_iter()→ page cache lookup → readahead if needed →copy_page_to_iter()to userspace buffer. - For O_DIRECT:
generic_file_direct_write()submits bios directly, bypassing the page cache. file_pos_write(f, pos)updatesf->f_posunderf->f_lock.- Returns bytes transferred (may be less than
countfor signals, EOF, pipe full, etc.).
Edge Cases & Failure Modes
- Short read: A read can return fewer bytes than requested due to EOF, signal interruption, or pipe underflow; callers (especially library code) must loop until the full count is read or an error occurs.
f_posrace on shared file descriptor: Two threads sharing the samestruct file(viafork()withoutO_CLOEXEC) racing onf->f_pos; the kernel serializesf_posupdates withf->f_lockbut the read/update window is not atomic.O_APPENDsemantics: Writes withO_APPENDseek to end-of-file and write atomically under the inode'si_mutex; on NFS, this atomicity guarantee may be lost if the server reboots between the seek and the write.- Blocking
read()on a pipe: Aread()from an empty pipe blocks until data is available or all write ends are closed; if the writer is killed,read()returns 0 (EOF); a signal to the reader returns-EINTR.
Mount Subsystem (`fs/namespace.c`)
The mount subsystem manages filesystem mount points, maintaining a tree of `struct mount` objects (each containing a …
Definition
The mount subsystem manages filesystem mount points, maintaining a tree of struct mount objects (each containing a vfsmount and a dentry binding point). It supports bind mounts, shared/private/slave/unbindable propagation types, mount namespaces (per-process mount views), and pivot_root() / chroot() operations.
Execution Flow
sys_mount(source, target, fstype, flags, data)→do_mount().lookup_mnt_in_ns()looks up the target path in the current mount namespace.- For a new filesystem mount:
vfs_kern_mount()→mount_fs()callsfstype->mount(fstype, flags, dev, data)→ returns a newdentryandsuper_block. graft_tree()attaches the newstruct mountto the target dentry in the mount tree.- For bind mounts (
MS_BIND):copy_tree()duplicates a subtree of the mount tree and attaches it at the target. - Mount propagation:
propagate_mnt()propagates the new mount to all peer/slave mounts in the same propagation group. - The new mount is visible in
/proc/self/mountsand in the VFS path walk (intercepted byfollow_mount()inwalk_component()).
Edge Cases & Failure Modes
- Mount namespace leak: A process that enters a mount namespace and creates mounts without calling
umount()before exiting leaves orphan mounts; they persist until the last process holding a reference to the namespace exits. - Propagation storm: In a heavily shared mount namespace (e.g., systemd's
MS_SHAREDroot), everymount()call propagates to all peers; with thousands of containers sharing a namespace, onemount()call triggers thousands of propagation operations. pivot_root()ordering requirements:pivot_root()requires the new root and old root to be on different filesystems and that the new root be a mount point; violating these constraints returnsEINVALand can leave the filesystem in a partially-pivoted state.- Unmount with busy mountpoint:
umount()fails withEBUSYif any file or directory on the mount is in use (open files, working directories, nested mounts);MNT_FORCEcan unmount NFS even with open files but may cause data loss.
`fsync` / Writeback (`fs/sync.c`, `fs/fs-writeback.c`)
Writeback is the kernel's mechanism for asynchronously flushing dirty pages (modified file data and metadata) from th…
Definition
Writeback is the kernel's mechanism for asynchronously flushing dirty pages (modified file data and metadata) from the page cache to storage. fsync(2) / fdatasync(2) are synchronous variants that guarantee all dirty data for a specific file has been written and acknowledged by the storage device before returning.
Execution Flow
fsync(fd)→vfs_fsync_range()→file->f_op->fsync(file, 0, LLONG_MAX, 0).- The filesystem's
fsyncimplementation (e.g.,ext4_sync_file()): - Calls
file_write_and_wait_range()to submit and wait for all dirty data pages in the page cache. - Logs a journal commit (for journaled filesystems: ext4, XFS, btrfs) to ensure metadata consistency.
- Calls
blkdev_issue_flush()to flush the device's write cache. - Asynchronous writeback (background):
wb_do_writeback()runs periodically frombdi_writebackkernel threads; it callswriteback_inodes_wb()→writeback_single_inode()→do_writepages()→a_ops->writepages(). - Dirty ratio enforcement:
balance_dirty_pages()throttles the process if dirty pages exceedvm.dirty_ratio. writeback_inodes_sb_nr()can be triggered bysync(2)orsyncfs(2)to flush all dirty inodes on a superblock.
Edge Cases & Failure Modes
- fsync on rename (rename without fsync of parent): Renaming a file over another is atomic at the VFS level but requires fsyncing the parent directory to guarantee durability; many applications call
fsync(new_file_fd)but notfsync(dir_fd), so a crash can leave the directory pointing to the old file. - Writeback loop stall: Under extreme write load,
pdflushthreads cannot drain dirty pages faster than new dirty pages are created; the system enters "writeback throttling" and all writing processes may block indefinitely. - ext4 delayed allocation + crash: With
data=orderedmode, ext4 delays block allocation until writeback; a crash between data writeback and journal commit leaves allocated but uninitialized blocks exposed; ext4's zeroing-on-allocation prevents data leakage but requires extra I/O. - btrfs CoW writeback ordering: btrfs writes new data to new extents before updating metadata; a crash during writeback can leave unreferenced extents; the transaction commit log ensures that only fully committed trees are used on remount.
`splice` / `sendfile` (`fs/splice.c`)
`splice(2)` and `sendfile(2)` implement zero-copy data transfer between file descriptors, eliminating the need to cop…
Definition
splice(2) and sendfile(2) implement zero-copy data transfer between file descriptors, eliminating the need to copy data through userspace. sendfile() transfers from a file fd to a socket fd using the page cache; splice() moves data between arbitrary fds via an internal pipe buffer without touching userspace memory.
Execution Flow
sendfile(out_fd, in_fd, offset, count)→do_sendfile().vfs_sendfile()callsin_file->f_op->splice_read()to populate pipe buffers from the source file (page cache pages are added to the pipe without copying).splice_from_pipe()callsout_file->f_op->splice_write()on the destination socket.- For socket send:
skb_splice_bits()maps the pipe's pages intosk_bufffragments directly, avoiding amemcpy(). - For
splice(in_fd, in_off, out_fd, out_off, len, flags): - If
in_fdis a pipe: pages are moved from the in-pipe's buffer to the out-fd. - If
in_fdis a file:generic_file_splice_read()fills a temporary pipe from the page cache, then drains it into the out-fd. - Pipe buffer reference counts track when pages can be released back to the page cache.
Edge Cases & Failure Modes
- Non-splice-capable fd: Not all fd types support splice; a device file or procfs file without
f_op->splice_readfalls back todefault_file_splice_read(), which copies data through a temporary page buffer — no actual zero-copy. - sendfile to non-socket:
sendfile()is defined only for socket destinations on most Linux versions; using it with a regular file destination returnsEINVAL. - Pipe buffer exhaustion:
splice()requires at least one pipe fd; the pipe's buffer (default 64 KiB, configurable viaF_SETPIPE_SZ) limits the in-flight data; a full pipe blocks the writer. - Page pinning under memory pressure: Pages used in a
splice()transfer are reference-counted to prevent eviction; a long-livedsplice()operation on a large file pins many pages, potentially causing memory pressure for other workloads.
`epoll` (`fs/eventpoll.c`)
`epoll` is a scalable I/O event notification mechanism for monitoring large numbers of file descriptors simultaneously.
Definition
epoll is a scalable I/O event notification mechanism for monitoring large numbers of file descriptors simultaneously. Unlike poll(2) / select(2) (which scan all fds in O(N)), epoll maintains a Red-Black tree of monitored fds and delivers only ready events, achieving O(1) per-event overhead. It is used by high-performance servers (nginx, Redis, etc.).
Execution Flow
epoll_create1(flags)→ creates aneventpollstruct and an anonymous inode/fd for it.epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &event): addsfdto the RB tree; callsep_insert()→add_wait_queue()to register a callback onfd's wait queue.- When
fdbecomes readable/writable: the kernel callsep_poll_callback()→ adds the epoll item to theeventpoll->rdllist(ready list) and wakes up any task blocked inepoll_wait(). epoll_wait(epfd, events, maxevents, timeout):- Checks
ep->rdllist; if events are ready, callsep_send_events()→ copies events to userspace. - If none ready: adds the calling task to
ep->wq, callsschedule_hrtimeout_range(). - On wake (by
ep_poll_callback()): re-checksrdllist, copies events. EPOLLET(edge-triggered) mode: an event is delivered only once per state transition (not repeatedly while the fd remains ready); the application must drain the fd completely.
Edge Cases & Failure Modes
- Level-triggered (LT) busy loop: If the application calls
epoll_wait(), receives anEPOLLINevent, reads only part of the available data, and then callsepoll_wait()again, it immediately gets anotherEPOLLIN; without reading all data, this loops at 100% CPU. - Edge-triggered missed event: In
EPOLLETmode, if the application fails to drain all data after a wakeup, it will not receive another event until more new data arrives; subsequent data may never be read (missed wakeup). - Circular
epollmonitoring: Adding an epoll fd to itself viaEPOLL_CTL_ADDis detected and returnsELOOP; more complex cycles (epollA monitors epollB which monitors epollA) are also detected via cycle detection inep_loop_check(). EPOLLHUPand closed sockets: When a socket peer closes the connection,EPOLLHUPis delivered even if the application did not request it; failing to handleEPOLLHUPcauses the application to loop on a closed fd.
inotify (`fs/notify/inotify/`)
inotify is the kernel's filesystem event notification system.
Definition
inotify is the kernel's filesystem event notification system. It allows userspace applications to watch files and directories for events (create, delete, modify, rename, etc.) by registering watches on specific paths. The kernel delivers events via a file descriptor queue. Used by file managers, build systems, and configuration management tools.
Execution Flow
inotify_init1(flags)→ creates aninotify_deviceand returns a fd. The fd is backed by anfsnotify_group.inotify_add_watch(inotify_fd, path, mask): resolvespathto an inode; creates afsnotify_markon the inode'sfsnotify_markslist; registers the event mask.- When a monitored filesystem operation occurs (e.g.,
vfs_create(),vfs_unlink()), the VFS callsfsnotify(dir, inode, mask, name). fsnotify()iterates the inode's marks; for each matchingfsnotify_group, callsgroup->ops->handle_event()→inotify_handle_event().- An
inotify_eventstruct is queued to the group'snotification_list. - The inotify fd becomes readable;
read(inotify_fd, buf, len)dequeues events into the userspace buffer. inotify_rm_watch(inotify_fd, wd)removes the fsnotify_mark from the inode and closes the watch.
Edge Cases & Failure Modes
- IN_Q_OVERFLOW: If events are generated faster than the application reads them, the kernel queue exceeds
inotify_max_queued_events; a singleIN_Q_OVERFLOWevent is delivered, and subsequent events are dropped; the application must rescan the filesystem. - IN_IGNORED on watch removal: If a watched file is deleted, inotify delivers
IN_DELETE_SELFand thenIN_IGNORED(indicating the watch was automatically removed); applications that don't handleIN_IGNOREDaccumulate stale watch descriptors. - Rename across watched directories:
inotify_add_watch()watches an inode, not a path; if a file is renamed out of a watched directory into another, the watch on the old parent firesIN_MOVED_FROMand the new parent firesIN_MOVED_TOwith matching cookies; applications must correlate cookies to track renames. - Hardlink creation: Creating a hardlink to a watched file notifies the directory where the link is created (
IN_CREATE) but not the inode itself; applications tracking all names for a file must monitor both the inode and all parent directories.
S7 — Network Stack Hooks
10 componentsNetfilter Hook Framework (`net/netfilter/core.c`)
Netfilter is the kernel's packet filtering and manipulation framework.
Definition
Netfilter is the kernel's packet filtering and manipulation framework. It defines five hook points in the IPv4/IPv6 packet processing path (NF_INET_PRE_ROUTING, NF_INET_LOCAL_IN, NF_INET_FORWARD, NF_INET_LOCAL_OUT, NF_INET_POST_ROUTING) where registered hook functions (from iptables, nftables, conntrack, etc.) can inspect, modify, accept, or drop packets.
Execution Flow
- A packet arrives at a network interface:
netif_receive_skb()→ip_rcv()for IPv4. ip_rcv()callsNF_HOOK(NFPROTO_IPV4, NF_INET_PRE_ROUTING, skb, in, NULL, ip_rcv_finish).nf_hook_slow()iterates the registered hook list for this protocol+hooknum combination (sorted by priority).- Each hook function is called:
hook->hook(priv, skb, state). Returns one of:NF_ACCEPT,NF_DROP,NF_STOLEN,NF_QUEUE,NF_REPEAT. NF_ACCEPT: proceed to next hook or resume processing withip_rcv_finish().NF_DROP:kfree_skb()discards the packet; processing ends.NF_QUEUE: packet is enqueued tonfnetlink_queuefor userspace inspection; processing suspends until verdict is returned.- After all pre-routing hooks:
ip_rcv_finish()performs routing lookup and continues toNF_INET_LOCAL_INorNF_INET_FORWARD.
Edge Cases & Failure Modes
- Hook registration order: Hooks are sorted by numerical priority at registration time; a module that registers at the wrong priority level sees packets in the wrong order relative to conntrack or NAT, causing incorrect filter decisions.
NF_STOLENmemory leak: A hook returningNF_STOLENclaims ownership of theskb; if the hook function then loses the skb without freeing it, the packet is leaked permanently.- Hook list modification while in use: A module calling
nf_unregister_net_hook()while packets are traversing the hook list is safe (RCU-protected list), but the unregistered hook may still be executing on another CPU;synchronize_net()must be called before the hook function's module is unloaded. NF_QUEUEverdict timeout: If a userspacenfnetlink_queueprocess crashes or hangs, queued packets are never verdicted; they accumulate in memory until the queue limit is reached, after which new packets are dropped withNF_DROP.
iptables (`net/ipv4/netfilter/ip_tables.c`)
iptables is the classic packet filter that uses Netfilter hooks to implement stateless and stateful packet filtering,…
Definition
iptables is the classic packet filter that uses Netfilter hooks to implement stateless and stateful packet filtering, NAT, and packet mangling. It organizes rules into tables (filter, nat, mangle, raw, security), each containing chains (hook points) of rules. Each rule contains a match (conditions) and a target (action).
Execution Flow
- At the
NF_INET_LOCAL_INhook:iptable_filter_hook()→ipt_do_table(skb, state, priv->table). ipt_do_table()traverses the table's rule array: for each rule, calls all match functions (m->match(skb, par)).- If all matches return true for the packet, the target function is invoked:
t->target(skb, par). - Targets return a verdict:
IPT_CONTINUE(try next rule),NF_ACCEPT,NF_DROP,NF_QUEUE, or a chain jump (e.g.,LOGtarget). - Chain jumps (
-j CHAIN_NAME): push current position to a stack; begin traversing the named chain;RETURNtarget pops the stack. - If no rule matches and the chain's policy is reached: return the policy verdict (
ACCEPTorDROP). - The final verdict is returned to
nf_hook_slow().
Edge Cases & Failure Modes
- Stateful vs. stateless race with conntrack: The
nattable modifies packets based onconntrackstate; a packet processed before the conntrack entry is established may bypass NAT if therawtable'sNOTRACKtarget was used. - Rule table atomicity:
iptables-restorereplaces the entire ruleset atomically viasetsockopt(IPT_SO_SET_REPLACE); during the brief transition, packets may be processed by an inconsistent partial ruleset. - Jump stack overflow: The rule traversal maintains a stack for chain jumps; a deeply recursive ruleset (chains jumping to chains) can overflow the stack (bounded by
XT_JUMPSTACK_MULTIPLIER * xt_jumpstack_alloc()). - Connection tracking table exhaustion: The
conntrackmodule maintains a hash table of connections; ifnf_conntrack_maxis exceeded, new connections are dropped; on high-connection-rate servers, this requires tuningnf_conntrack_maxand GC parameters.
nftables (`net/netfilter/nf_tables_core.c`)
nftables is the modern replacement for iptables, providing a unified framework for packet classification using an in-…
Definition
nftables is the modern replacement for iptables, providing a unified framework for packet classification using an in-kernel virtual machine (nft_expr VM) that evaluates rules as bytecode expressions. It supports all protocols (IPv4, IPv6, ARP, Ethernet) through a single framework with set/map data structures for high-performance lookups.
Execution Flow
nft_do_chain()is called from a Netfilter hook; it receives thenft_chainandskb.- For each
nft_rulein the chain:nft_rule_for_each_expr()iterates the expression list. - Each expression (
nft_expr) is evaluated by itsops->eval(expr, regs, pktinfo)function:nft_cmp_eval(compare field),nft_lookup_eval(set/map lookup),nft_meta_eval(metadata extraction), etc. - Expressions write intermediate results to virtual registers (
nft_regs). - The final expression in a rule is typically a verdict (
nft_verdict):NFT_CONTINUE,NFT_ACCEPT,NFT_DROP,NFT_JUMP chain,NFT_GOTO chain,NFT_RETURN. - Set lookups:
nft_lookup_eval()callsnft_set_ops->lookup(set, key, &data)→ performs a hash lookup or rbtree/interval tree lookup in the set; on hit, may apply a map action (store data into a register). - The final verdict from
nft_do_chain()is returned tonf_hook_slow().
Edge Cases & Failure Modes
- Atomic ruleset commit: nftables transactions use
nft_transobjects;nft_commit()atomically installs the new generation; in-flight packets using the old generation continue untilsynchronize_rcu()completes. - Set update race with packet processing: Calling
nft_set_insert_elem()whilenft_lookup_eval()is running on another CPU is safe for hash sets (RCU-protected), but interval-tree sets require a write lock that blocks packet processing. - Expression VM register contamination: If an expression writes to a register and a subsequent expression reads a different register, uninitialized register data may cause incorrect decisions; nftables validates register usage at rule load time.
- JIT compilation overhead: nftables rules can be JIT-compiled to native code for performance; a JIT bug in an expression can cause arbitrary kernel code execution; the JIT is disabled by default and can be enabled with
nft jit on.
Socket Buffer (`sk_buff`) (`net/core/skbuff.c`)
The `sk_buff` (socket buffer, skb) is the fundamental data structure for network packets in the Linux kernel.
Definition
The sk_buff (socket buffer, skb) is the fundamental data structure for network packets in the Linux kernel. It is a metadata header describing a packet: pointers to the actual packet data (in a separate data buffer), linked list pointers for queues, protocol headers, timestamps, and device references. The design allows O(1) prepend/append of protocol headers without data copying.
Execution Flow
- Packet reception: the network driver allocates an skb via
netdev_alloc_skb()ornapi_alloc_skb(), places DMA'd packet data into the skb's data buffer. skb_put(skb, len)advances thetailpointer, defining the data length.- The skb is passed up the protocol stack: each layer calls
skb_pull(skb, header_len)to advance thedatapointer past the layer's header, exposing the payload to the next layer. - Protocol layers add metadata:
skb->protocol(ETH_P_IP),skb->ip_summed(checksum status),skb->mark(for firewall rules), etc. - For transmission:
skb_push(skb, header_len)prepends headers (TCP → IP → Ethernet) without data copying (theheadbuffer has headroom reserved for this purpose). dev_queue_xmit(skb)→ queues to the device's Qdisc → driver transmits.kfree_skb(skb)/consume_skb(skb): decrements reference count; on zero, callsskb_release_all()to free the data buffer and skb header.
Edge Cases & Failure Modes
- skb linear/non-linear confusion: An skb may have its data split between a linear buffer and
skb_shinfo->frags[](paged fragments); a function that callsskb->dataassuming all data is linear when the skb is non-linear causes incorrect reads past the linear portion. - skb reference count leak: Each call to
skb_get()increments the reference count; a code path that takes a reference and then exits on an error without callingkfree_skb()leaks the skb and its data buffer permanently. - GRO (Generic Receive Offload) aggregation corruption: GRO merges multiple incoming TCP/UDP segments into one large skb for efficiency; if the GRO logic misidentifies a packet as belonging to an existing flow, data from different flows is merged, causing TCP corruption.
- skb headroom exhaustion: If a driver allocates an skb with insufficient headroom and the protocol stack calls
skb_push()beyond the headroom,pskb_expand_head()must reallocate; under memory pressure this fails, dropping the packet.
Traffic Control Qdisc (`net/sched/`)
The Traffic Control (TC) framework implements Quality of Service (QoS) for outgoing packets via a hierarchy of Queuei…
Definition
The Traffic Control (TC) framework implements Quality of Service (QoS) for outgoing packets via a hierarchy of Queueing Disciplines (Qdiscs). A Qdisc is attached to each network device's transmit queue; it classifies, schedules, shapes, and polices outgoing traffic. Examples: pfifo_fast (default FIFO), htb (hierarchical token bucket), fq_codel (fair queuing + CoDel AQM), tbf (token bucket filter).
Execution Flow
dev_queue_xmit(skb)calls__dev_xmit_skb().q->enqueue(skb, q, &to_free)is called: the Qdisc's enqueue function classifies the packet (viatc_classify()for classful Qdiscs like HTB) and places it in the appropriate queue or band.qdisc_run(q)calls__qdisc_run(q):q->dequeue(q)removes the next packet according to the scheduling policy (FIFO, WFQ, token bucket drain rate, etc.).sch_direct_xmit(skb, q, dev, txq, root_lock, true)callsdev_hard_start_xmit()→ driver transmit.- Loop until the transmit queue is full or no more packets.
- For shaping (
tbf,htb): a softwarehrtimeris used to defer dequeue until the token bucket refills. - For AQM (
codel,fq_codel): packets are dropped or ECN-marked if sojourn time (time in queue) exceeds the target delay, signaling congestion to TCP.
Edge Cases & Failure Modes
- Qdisc lock contention: The Qdisc lock (
qdisc_lock(q)) serializes all enqueue/dequeue operations; under high packet rates, this becomes a bottleneck;noqueueormq(multi-queue) Qdiscs avoid this. - HTB quantum misconfiguration: If
quantum(burst size) is set too small relative to MTU, HTB cannot transfer a full packet in one dequeue cycle, causing starvation of low-priority classes even when their rate limit allows transmission. fq_codelunder UDP flood: CoDel's AQM relies on delay feedback from TCP congestion control; UDP flows don't respond to ECN or drops;fq_codel's flow hashing may assign UDP flood traffic to a separate flow bucket but cannot reduce the flood rate.- Shaping timer resolution: Software shaping uses
hrtimerswith nanosecond resolution, but the actual wake-up jitter depends on the system's timer resolution and load; at high rates (>1 Gbps), software shaping jitter significantly affects shaped throughput.
XDP (eXpress Data Path) (`net/core/xdp.c`, `include/linux/bpf.h`)
XDP is a high-performance, programmable packet processing framework that runs eBPF programs at the earliest possible …
Definition
XDP is a high-performance, programmable packet processing framework that runs eBPF programs at the earliest possible point in the receive path — in the network driver's NAPI receive function, before the skb is allocated. This eliminates the overhead of skb allocation, Netfilter hooks, and protocol stack traversal for packets that should be dropped or redirected.
Execution Flow
- At driver load time:
xdp_rxq_info_reg()registers a receive queue for XDP. - An eBPF program is loaded with
bpf(BPF_PROG_LOAD, ...)and typeBPF_PROG_TYPE_XDP; the verifier checks it. - The program is attached to the interface:
bpf(BPF_LINK_CREATE, ..., attach_type=BPF_XDP)or viaip link set dev eth0 xdp obj prog.o. - Packet reception: the driver's NAPI poll function calls
bpf_prog_run_xdp(prog, &xdp)before allocating an skb. - The XDP program executes, returning one of:
XDP_DROP(discard immediately),XDP_PASS(continue to normal stack),XDP_TX(retransmit on same interface),XDP_REDIRECT(send to another interface/CPU viabpf_redirect()),XDP_ABORTED(drop + trace). XDP_PASS: the driver proceeds to allocate an skb and pass the packet tonetif_receive_skb().XDP_REDIRECTwithAF_XDP: packets are delivered to a userspace memory-mapped ring buffer (UMEM) viaxsk_rcv().
Edge Cases & Failure Modes
- Driver XDP support required: XDP requires a driver-specific implementation (
ndo_bpfwithXDP_SETUP_PROG); drivers without XDP support fall back to "generic XDP" (skb-based), which is slower and loses most XDP performance benefits. XDP_TXon a congested interface: Retransmitting a packet on an interface whose transmit queue is full causes the packet to be dropped silently; the XDP program has no feedback mechanism to detect this.- Multi-buffer XDP packets: Jumbo frames or TSO-segmented packets that span multiple receive descriptors require "multi-buffer XDP" support (added in kernel 5.18); earlier kernels silently drop such packets when XDP is active.
- AF_XDP UMEM alignment requirements: The UMEM frame size must be a power of two aligned to the page size; misaligned frames cause the
xsk_bind()syscall to returnEINVAL, and the kernel does not report which alignment constraint was violated.
eBPF Network Hooks (`kernel/bpf/`, `net/core/filter.c`)
eBPF (extended Berkeley Packet Filter) allows safe, sandboxed programs to be loaded into the kernel at various attach…
Definition
eBPF (extended Berkeley Packet Filter) allows safe, sandboxed programs to be loaded into the kernel at various attachment points beyond XDP: socket filters (SO_ATTACH_BPF), traffic classifiers (TC BPF), cgroup socket hooks (BPF_CGROUP_INET_*), sk_msg / sk_skb for stream parsers, bpf_sockmap for socket redirection, and bpf_flow_dissector. Programs are verified by the eBPF verifier before being allowed to run.
Execution Flow
- A BPF program is written in restricted C, compiled with
clang -target bpf, producing eBPF bytecode. bpf(BPF_PROG_LOAD, attr)submits bytecode to the kernel; the eBPF verifier:- Checks the control-flow graph for loops (bounded only via the verifier's loop unrolling or bounded loops in 5.3+).
- Verifies type safety: each register's type is tracked; invalid dereferences are rejected.
- Checks that helper calls use valid argument types.
- The program is JIT-compiled by
do_jit()to native machine code. - Attached to a hook (e.g.,
setsockopt(SO_ATTACH_BPF)for a socket filter). - On packet arrival at the hook point:
BPF_PROG_RUN(prog, ctx)executes the JIT'd code. - The program reads packet data, calls BPF helpers (
bpf_skb_load_bytes(),bpf_map_lookup_elem()), and returns a verdict (drop/pass/redirect).
Edge Cases & Failure Modes
- Verifier false negative (complexity limit): Programs exceeding the instruction complexity limit (
BPF_COMPLEXITY_LIMIT_INSNS = 1,000,000instructions verified) are rejected withEACCESeven if semantically safe; refactoring into smaller programs is required. - JIT spraying via BPF constants: Loading a BPF program with crafted immediate values can place attacker-controlled data in JIT code pages;
BPF_JIT_KALLSYMSand constant blinding (bpf_jit_blind_constant()) mitigate this. - BPF map race conditions: Two BPF programs updating the same
BPF_MAP_TYPE_HASHmap concurrently are protected by per-bucket spinlocks, but a program that reads a value and then writes based on it (check-then-act) is not atomic; useBPF_MAP_TYPE_PERCPU_HASHor atomic helpers. - Helper function ABI stability: BPF helper functions are part of the stable kernel ABI; a helper removed or changed in a kernel update silently breaks BPF programs that relied on it.
NAPI (New API) (`net/core/dev.c`)
NAPI is the interrupt-mitigation mechanism for network drivers.
Definition
NAPI is the interrupt-mitigation mechanism for network drivers. Instead of delivering one interrupt per received packet (which at 10 Gbps would be millions per second), NAPI allows a driver to disable interrupts after the first packet arrival and poll for more packets in a single scheduling quantum, then re-enable interrupts. This dramatically reduces interrupt overhead under high load.
Execution Flow
- A packet arrives; the NIC asserts an IRQ; the driver's interrupt handler fires.
- The handler: disables further NIC receive interrupts; calls
napi_schedule(&napi)to add the NAPI structure to the per-CPUsoftnet_data->poll_list. - The
NET_RX_SOFTIRQsoftirq is raised;net_rx_action()runs in softirq context. net_rx_action()calls each NAPI'spoll()function (driver-specific, e.g.,igb_poll()) with a budget (default 64 packets).- The driver's
poll()function processes up tobudgetreceived descriptors; for each: allocates an skb, fills it, callsnapi_gro_receive()→netif_receive_skb(). - If fewer than
budgetpackets were processed:napi_complete_done()re-enables NIC interrupts and removes frompoll_list. - If exactly
budgetpackets were processed (more may be waiting): the NAPI remains scheduled;napi_schedule_prep()reschedules for the next softirq run.
Edge Cases & Failure Modes
- NAPI budget starvation: Under an extreme packet flood, a single high-traffic NAPI may consume the entire softirq time budget (10 ms) and starve other network devices;
netdev_budgetandnetdev_budget_usecscan be tuned. napi_schedule()from non-interrupt context: Callingnapi_schedule()from a context where the NIC interrupt is not disabled (e.g., from a timer callback) causes a double-schedule;napi_schedule_prep()uses an atomic bit to prevent this.- GRO session expiry: GRO (Generic Receive Offload) holds partially merged skbs in a session; if no more segments arrive within
GRO_MAX_BACKOFF, the session flushes vianapi_gro_flush(); on a lightly loaded interface, GRO adds per-packet latency equal to the flush timeout. - NAPI weight fairness: All NICs on the same CPU share the softirq budget; a NIC with 64 packets in one NAPI poll consumes the entire budget, starving other NICs;
ethtool -Ccan tune interrupt coalescing to redistribute.
Receive Packet Steering (RPS) (`net/core/dev.c`)
RPS is a software implementation of Receive-Side Scaling (RSS) for NICs that have only a single receive queue.
Definition
RPS is a software implementation of Receive-Side Scaling (RSS) for NICs that have only a single receive queue. It distributes received packets across multiple CPUs by computing a hash over the packet's flow tuple (src/dst IP, src/dst port) and steering the packet to the target CPU's input queue via an IPI, allowing parallel protocol processing.
Execution Flow
- A packet is received; the driver calls
netif_rx()ornetif_receive_skb(). - If RPS is enabled on the interface (
/sys/class/net/ethX/queues/rx-N/rps_cpusbitmap non-zero): get_rps_cpu(dev, skb, &rflow)computes a flow hash from the skb's L3/L4 headers usingskb_get_hash().- The hash is mapped to a CPU index via the
rps_map->cpus[]array. - If the target CPU differs from the current CPU:
enqueue_to_backlog()adds the skb to the target CPU'sinput_pkt_queue(a lockless ring buffer). - An IPI (
raise_softirq_irqoff(NET_RX_SOFTIRQ)) is sent to the target CPU. - The target CPU's
net_rx_action()softirq dequeues frominput_pkt_queueand calls__netif_receive_skb(). - Protocol stack processing continues on the target CPU.
Edge Cases & Failure Modes
- Flow hash collision: Two different flows that hash to the same CPU index are always processed on the same CPU, defeating RPS's distribution for those flows; increasing
rps_mapsize reduces collisions. - IPI overhead at low load: At low packet rates, the IPI to steer each packet to a remote CPU costs more than the protocol processing it saves; RPS should only be enabled on systems where the NIC interrupt CPU is a bottleneck.
input_pkt_queueoverflow: Each CPU's backlog queue has a maximum depth (netdev_max_backlog, default 1000); packets that arrive faster than the softirq can drain them are dropped withNET_RX_DROP.- RPS and hardware RSS interaction: If the NIC also has hardware RSS (distributing packets across multiple receive queues), enabling software RPS on top creates double-steering overhead; they should be used exclusively.
Netlink Socket (`net/netlink/`)
Netlink is a socket-based IPC mechanism for communication between the kernel and userspace (and between kernel subsys…
Definition
Netlink is a socket-based IPC mechanism for communication between the kernel and userspace (and between kernel subsystems). It uses a datagram-oriented socket family (AF_NETLINK) with protocol numbers for different subsystems: NETLINK_ROUTE (routing, ARP, links), NETLINK_NETFILTER (iptables/nftables configuration), NETLINK_GENERIC (extensible subsystem for new protocols). Used by ip, ss, iptables, iw, and many daemons.
Execution Flow
- Userspace opens:
socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE). bind(fd, &addr, sizeof(addr))registers the socket with its PID (or 0 for auto-assign) in the netlink subsystem.- Userspace sends a request:
sendmsg()with anlmsghdrheader (type, flags, sequence, PID) followed by a protocol-specific payload (e.g.,struct ifinfomsg). - The kernel's
netlink_rcv_skb()dequeues the message; calls the protocol'sinput()callback (e.g.,rtnetlink_rcv_msg()forNETLINK_ROUTE). - The handler processes the request: for
RTM_GETLINK, it iteratesdev_base_headand buildsnlmsghdrreplies usingnlmsg_put()/nla_put_*()helpers. nlmsg_unicast()ornlmsg_multicast()queues the reply to the requesting socket or all subscribers to a multicast group.- Userspace reads the reply via
recvmsg().
Edge Cases & Failure Modes
- Dump truncation: For large datasets (many routes, many interfaces), a Netlink dump uses
NLM_F_MULTI+NLMSG_DONEto paginate results; if the socket receive buffer (SO_RCVBUF) is too small,ENOBUFSis returned and the dump is incomplete; the client must retry with a larger buffer. - Netlink multicast group overflow: A slow userspace subscriber to a multicast group (e.g.,
RTMGRP_LINK) with a full receive buffer causes the kernel to drop events silently; the subscriber may miss link state changes. - Privileged operations without
CAP_NET_ADMIN: Write operations (adding routes, configuring interfaces) requireCAP_NET_ADMIN; a non-privileged process attempting these getsEPERM; read operations (listing routes) are generally unprivileged. - Netlink attribute parsing errors: Malformed
nlattrpayloads (incorrect length, missing required attributes) are caught bynla_validate()before dispatch; older kernels that don't validatenlattralignment can read unaligned memory.
S8 — Linux Security Modules (LSMs)
10 componentsLSM Framework (`security/security.c`)
The Linux Security Module (LSM) framework is the kernel's pluggable MAC (Mandatory Access Control) infrastructure.
Definition
The Linux Security Module (LSM) framework is the kernel's pluggable MAC (Mandatory Access Control) infrastructure. It defines over 200 security hook points throughout the kernel (in VFS, IPC, networking, process management, etc.) that call registered hook implementations. Multiple LSMs can be stacked (since Linux 4.2 for minor LSMs, full stacking since 5.1); each hook calls all registered implementations in sequence.
Execution Flow
- The kernel defines hooks as function calls in security-sensitive paths: e.g.,
security_inode_permission(inode, mask)ininode_permission(). security_inode_permission()insecurity/security.ccallscall_int_hook(inode_permission, 0, inode, mask).call_int_hookiterates thesecurity_hook_heads.inode_permissionlist; for each registered hook function, calls it with the same arguments.- Each LSM hook returns 0 (allow) or a negative error code (deny).
- The first non-zero return causes the loop to stop and the error is returned to the caller (deny-wins policy).
- The caller (e.g.,
vfs_open()) returns the error to userspace (typicallyEACCESorEPERM). - LSM registration: each LSM calls
security_add_hooks(hooks, count, name)during__init; hooks are added tosecurity_hook_headslists.
Edge Cases & Failure Modes
- Hook ordering non-determinism: Multiple LSMs registered for the same hook execute in registration order, which is determined by kernel config; a policy that relies on SELinux running before AppArmor may break if the order changes.
- Performance overhead of
call_int_hook: Each hook traversal iterates all registered LSMs; on systems with many stacked LSMs and performance-critical paths (e.g.,security_socket_sendmsg()), this adds measurable latency. - NULL hook dereference in minor LSMs: LSMs registered as "minor" (like Yama, Lockdown) may implement only a subset of hooks;
security_add_hooks()only registers non-NULL hooks, so stale hook function pointers are never called. - LSM data stored in kernel objects: Each LSM may attach private security blobs to kernel objects (inodes, tasks, sockets) via the
lsm_blob_sizesmechanism; a bug in blob allocation sizing causes memory corruption in security-sensitive structures.
SELinux (`security/selinux/`)
SELinux (Security-Enhanced Linux) implements mandatory access control via type enforcement: every process and kernel …
Definition
SELinux (Security-Enhanced Linux) implements mandatory access control via type enforcement: every process and kernel object has a security context (user:role:type:level), and access is governed by an in-kernel policy database (the Type Enforcement, Role-Based Access Control, and Multi-Level Security components). It is the dominant LSM on RHEL, Fedora, and Android.
Execution Flow
- At boot (policy load):
security_load_policy()→selinux_set_policy()loads the binary policy from/etc/selinux/*/policy.*viaavc_policy_seqno(). - The Access Vector Cache (AVC) is initialized: an in-memory hash table mapping (source SID, target SID, class) →
allowed/denied/auditallowdecision bitsets. - Access check at hook time:
selinux_inode_permission()→avc_has_perm(ssid, tsid, SECCLASS_FILE, perm). avc_has_perm_noaudit()checks the AVC cache: on hit, returns the cached decision in nanoseconds.- On AVC miss:
avc_compute_av()→security_compute_av()queries the policy database (DFA transitions). - The result is cached in the AVC and returned; if
denied:avc_audit()logs a denial message to the audit subsystem. - In "permissive" mode: denials are logged but access is granted; in "enforcing" mode: denials return
-EACCES.
Edge Cases & Failure Modes
- AVC thrashing: Rapidly creating processes with new type combinations (e.g., container runtimes) floods the AVC with new SID lookups; the AVC's LRU eviction can't keep up, causing repeated policy database queries and performance regression.
- Policy reload race: A
load_policycall during active use atomically swaps the policy via RCU; in-flight permission checks using the old policy SIDs complete with the old policy; a brief window of inconsistency is unavoidable. - Mislabeled filesystem objects: Files without SELinux extended attributes (
security.selinux) receive theunlabeled_ttype; most SELinux policies deny access tounlabeled_t, causing application failures on newly created files;restoreconfixes labels. - SID overflow: Security IDs are 32-bit integers assigned from an incrementing counter; long-lived systems with many unique contexts can exhaust the SID space;
selinux_sid_to_context()returnsENOMEMwhen this happens.
AppArmor (`security/apparmor/`)
AppArmor implements MAC via path-based profiles: each application is confined by a named profile that specifies allow…
Definition
AppArmor implements MAC via path-based profiles: each application is confined by a named profile that specifies allowed file paths (using globs), network access, capabilities, and mount operations. Unlike SELinux's type-enforcement model, AppArmor labels processes by their executable path and uses a DFA (Deterministic Finite Automaton) for path matching.
Execution Flow
- Profile loading:
aa_replace_profiles()reads profiles from userspace (viasecurityfsat/sys/kernel/security/apparmor/.replace); the profile text is compiled to a DFA byaa_policy_init()and stored inaa_profile. - Process confinement: at
exec(),apparmor_bprm_set_creds()looks up the new executable's path in the profile database; if a matching profile exists, it is attached to the task's credential. - File permission check:
apparmor_inode_permission()callsaa_path_perm()→aa_str_perms(profile->file.dfa, path, mode)runs the DFA against the file's path string. - The DFA transitions through states for each path character; the final state maps to a permission set (read, write, execute, lock, etc.).
- If the requested access is not in the allowed set: return
-EACCES(enforcing) or log + allow (complain mode). aa_audit_msg()logs denials to the audit ring buffer with the matched profile name and denied path.
Edge Cases & Failure Modes
- Path vs. inode confusion: AppArmor matches paths at permission-check time, not at exec time; a process can be confined to
/usr/bin/appbut ifappis bind-mounted to another location, the path check sees the new location, potentially matching a different or no profile. - Glob pattern explosion: Overly broad globs (e.g.,
/**) in a profile cause the DFA to become very large (exponential state explosion); AppArmor compiles profiles offline and may refuse to load excessively large DFAs. - Namespace profile inheritance: AppArmor namespaces (for containers) inherit parent profiles; a container that breaks out of its AppArmor namespace can access the parent's profiles, which are typically less restrictive.
- Transition label vs. exec path: If a process
exec()s a new binary while the filesystem path changes between theexec()call and the credential setup (TOCTOU via bind mount), the wrong profile may be attached.
Smack (`security/smack/`)
Smack (Simplified Mandatory Access Control Kernel) implements MAC using a simple label-based model: every process and…
Definition
Smack (Simplified Mandatory Access Control Kernel) implements MAC using a simple label-based model: every process and filesystem object has a Smack label (a short string). Access is governed by a small, explicitly defined access matrix: a process with label A can access an object with label B only if an A b rwxatl rule exists in the Smack access list. Designed for embedded and IoT use cases.
Execution Flow
- Labels are assigned: filesystem objects get Smack labels via extended attributes (
security.SMACK64); processes inherit their parent's label at fork, or receive a new one viasmack_task_setscheduler(). - Access check:
smack_inode_permission()→smk_access(subject_label, object_label, access_mode, audit). smk_access()callssmk_find_rule()which searches the Smack access list (a linked list ofsmack_rulestructs) for a matching (subject, object) pair.- If a rule is found: check whether the requested access mode is in
rule->smk_access; return 0 (allow) or-EACCES(deny). - If no rule is found: apply the star-rule fallback:
*label (floor label) allows all access;^label (hat label) has access only from*. - Write access to Smack configuration via
securityfs(/sys/fs/smackfs/) requiresCAP_MAC_ADMIN.
Edge Cases & Failure Modes
- Rule list scalability: Smack's access list is a simple linked list; with many labels,
smk_find_rule()is O(N) per access check; on systems with large policy files, this is a performance bottleneck. - Label length limit: Smack labels are limited to
SMK_MAXLEN(23 characters); labels exceeding this are silently truncated; two labels differing only after the 23rd character become the same label. - Unlabeled filesystem objects: Files without a
security.SMACK64xattr receive thedefault_label(initially the floor label_); unlabeled NFS mounts receive a fixed label configured at mount time, which may be more permissive than intended. - Transmute directories: A directory with the
SMACK64TRANSMUTExattr causes new files created within it to inherit the directory's label regardless of the creator's label; a misconfigured transmute directory allows label escalation.
TOMOYO (`security/tomoyo/`)
TOMOYO Linux is a name-based MAC system that learns and enforces process call graphs: every process's behavior is def…
Definition
TOMOYO Linux is a name-based MAC system that learns and enforces process call graphs: every process's behavior is defined in terms of which executables it can spawn (domain transitions) and which file paths it can access, based on its "domain" (defined by the sequence of programs in its execution history). It operates in learning, permissive, and enforcing modes.
Execution Flow
- Domain creation: each process starts in a domain defined by the full executable path chain (e.g.,
/sbin/init /usr/sbin/sshd /usr/bin/bash). - Learning mode:
tomoyo_check_file_perm()and other hooks log every access;tomoyo_managerreads logs and auto-generates allow rules. - Policy enforcement:
tomoyo_path_perm()→tomoyo_check_perm()looks up the current process's domain in the policy database. - The access request (file path, operation) is checked against the domain's allow list (a sorted list of path patterns stored as
tomoyo_path_aclentries). tomoyo_path_matches_pattern()performs glob-style matching on the path string against each pattern.- If no match: in enforcing mode, return
-EACCES; in learning mode, add the path to the domain's policy and allow. - Domain transitions at
exec():tomoyo_find_next_domain()looks up the new domain in the policy tree; if found, the process's domain pointer is updated.
Edge Cases & Failure Modes
- Policy database size in learning mode: TOMOYO's learning mode generates one entry per unique (domain, path) pair; on a heavily used system with many unique paths, the policy file can grow to hundreds of megabytes.
- Domain transition loop detection: A process that repeatedly
exec()s different programs generates an ever-deepening domain chain;TOMOYO_MAX_DOMAINNAME_LEN(4096 characters) caps the chain length; at the cap, the domain is truncated, potentially misidentifying the process. - Symlink indirection: TOMOYO uses the resolved path after all symlinks; a policy that allows access to
/usr/bin/pythonautomatically covers any symlink pointing to it, which may be undesirable for confining wrapper scripts. - Performance under high syscall rate: Each syscall to a file requires a path match against the domain's allow list; on a system making millions of syscalls per second, the linear list scan is a bottleneck;
CONFIG_TOMOYOis not recommended for high-throughput servers.
Yama (`security/yama/`)
Yama is a simple LSM that restricts `ptrace(2)` and `/proc/<pid>/mem` access between processes without a parental rel…
Definition
Yama is a simple LSM that restricts ptrace(2) and /proc/ access between processes without a parental relationship, preventing ptrace-based privilege escalation and credential theft. It implements a single policy knob (/proc/sys/kernel/yama/ptrace_scope) with four levels (0–3) controlling which processes can ptrace which others.
Execution Flow
- A process calls
ptrace(PTRACE_ATTACH, target_pid, ...). - The VFS path invokes
security_ptrace_access_check(task, mode)→yama_ptrace_access_check(task, mode). - Level 0 (classic): allows any process to ptrace any process it could normally
ptrace(DAC rules only). - Level 1 (restricted):
task_is_descendant(current, task)checks ifcurrentis an ancestor oftask; if not, checks for a capability exception (CAP_SYS_PTRACE). - Level 2 (admin-only): only processes with
CAP_SYS_PTRACEmay attach. - Level 3 (no attach):
ptrace(PTRACE_ATTACH)is denied for all processes (even root); no runtime override. - Exception grants: a process can explicitly allow another to ptrace it via
prctl(PR_SET_PTRACER, pid), which adds an entry toptracer_llist.
Edge Cases & Failure Modes
- Level 1 bypass via re-parenting: If a privileged daemon uses
prctl(PR_SET_CHILD_SUBREAPER), it becomes the ancestor of all orphaned processes; this allows it to bypass Level 1 restrictions by being an artificial ancestor. PR_SET_PTRACERlist growth: Eachprctl(PR_SET_PTRACER, pid)call allocates aptracer_node; a process that sets many ptrace permissions without revoking them accumulates nodes; the list is walked on every ptrace check.- Level 3 and debugger tooling: Enabling Level 3 breaks strace, gdb, and system-wide profiling tools (
perf); it cannot be relaxed at runtime; this makes Level 3 unsuitable for development systems. - Yama and user namespaces: Within a user namespace,
CAP_SYS_PTRACEis scoped to the namespace; a process with this capability in a user namespace can bypass Level 2 restrictions for processes in the same namespace, potentially unintended in container environments.
Landlock (`security/landlock/`)
Landlock (Linux 5.13+) is a sandboxing LSM that allows unprivileged processes to restrict their own access rights at …
Definition
Landlock (Linux 5.13+) is a sandboxing LSM that allows unprivileged processes to restrict their own access rights at runtime. Unlike SELinux or AppArmor (which require root-managed policies), Landlock lets a process create a ruleset specifying allowed filesystem access, network operations (5.19+), and IPC operations (6.10+), and then self-enforce it via a syscall.
Execution Flow
- A process creates a ruleset:
landlock_create_ruleset(attr, attr_size, flags)→ returns a ruleset fd. - Rules are added:
landlock_add_rule(ruleset_fd, type, attr, flags): - For
LANDLOCK_RULE_PATH_BENEATH: open the directory fd; specifyallowed_accessbitset (read, write, exec, etc.). - The rule is stored in the ruleset's Red-Black tree keyed by inode number.
- The process restricts itself:
landlock_restrict_self(ruleset_fd, flags)→ adds the ruleset to the current thread'slandlock_rulesetcredential field. - At each LSM hook (e.g.,
landlock_inode_permission()):landlock_get_applicable_ruleset(cred)retrieves the active ruleset. check_access_path()traverses the inode's ancestor dentries; for each layer, checks if the dentry's inode is in the ruleset's RB tree and whether the requested access is in itsallowed_access.- If no rule covers the access: return
-EACCES. - The ruleset is inherited by child processes (and survives
exec()) but cannot be extended; it can only be further restricted by adding a new ruleset.
Edge Cases & Failure Modes
- Ruleset inheritance + exec: A child process inherits the parent's Landlock restrictions; a setuid binary exec'd by a Landlock-restricted process inherits the restrictions, which may prevent the setuid program from accessing files it needs; this is intentional (defense in depth) but breaks some use cases.
- Hardlink bypass: Landlock rules are inode-based; a file accessible via a hardlink from a path not covered by the ruleset can be accessed if the hardlink target's inode is not explicitly restricted; this is a known limitation.
- Versioned ABI: Landlock's ABI is versioned via the
abi_versionfield inlandlock_create_ruleset; programs must check the version and downgrade theirhandled_access_fsto the highest supported version; failing to do so results inEINVAL. - Network restriction in Landlock < 5.19: The network restriction feature (
LANDLOCK_RULE_NET_PORT) was added in Linux 5.19; programs that check for Landlock support but don't check the ABI version may incorrectly assume network restrictions are available.
LoadPin (`security/loadpin/`)
LoadPin is a simple LSM that restricts kernel module loading and firmware loading to files from a single trusted file…
Definition
LoadPin is a simple LSM that restricts kernel module loading and firmware loading to files from a single trusted filesystem (typically the initramfs or the root filesystem). Once the "pinned" filesystem is set (on first module load after boot), no module or firmware may be loaded from any other filesystem. It prevents loading of untrusted kernel code at runtime.
Execution Flow
- At boot: LoadPin is enabled with
loadpin.enforce=1on the kernel command line. - The first time the kernel loads a module or firmware (
security_kernel_read_file()orsecurity_kernel_load_data()),loadpin_read_file()is called. - If
pinned_rootis NULL (not yet set): the superblock of the file being loaded is saved aspinned_root; this filesystem is now the trusted root. - On all subsequent module/firmware loads:
loadpin_read_file()checks whether the file's superblock matchespinned_root. - If it doesn't match: return
-EPERM; the module/firmware load is blocked. - The pinned root can optionally be set to a specific list of trusted filesystems via
loadpin.verity_root_digest(dm-verity integration).
Edge Cases & Failure Modes
- Initramfs pivot_root interaction: If the system pivots from an initramfs root to the real root filesystem,
pinned_rootwas set to the initramfs superblock; subsequent module loads from the real root fail with-EPERM; LoadPin-enabled systems must load all required modules beforepivot_root(). - Network-loaded firmware: Firmware blobs fetched from the network (e.g., via
request_firmware()with anFIRMWARE_URLoverride) have no filesystem superblock; LoadPin rejects them, preventing remote firmware updates;loadpin.exclude=firmwarecan exempt firmware from the check. - Hot-plugged device firmware: A USB device inserted after boot requires firmware; if the firmware is on the pinned filesystem, it loads normally; if it's on a removable media filesystem, it fails; this is intentional but may surprise administrators.
- LoadPin with module signing: LoadPin and
CONFIG_MODULE_SIGprovide complementary protections; LoadPin prevents loading from an untrusted FS, while module signing prevents loading unsigned code from any FS; both should be used together for maximum hardening.
SafeSetID (`security/safesetid/`)
SafeSetID is a targeted LSM that restricts which user IDs (UIDs) and group IDs (GIDs) a privileged process (one with …
Definition
SafeSetID is a targeted LSM that restricts which user IDs (UIDs) and group IDs (GIDs) a privileged process (one with CAP_SETUID / CAP_SETGID) may transition to. It enforces a whitelist of allowed UID/GID transitions, preventing a compromised privileged daemon from dropping privileges to an arbitrary UID and then re-acquiring them via other means.
Execution Flow
- Policy is loaded via
securityfsat/sys/kernel/security/safesetid/whitelist_policyas a text file ofsource_uid:target_uidpairs. safesetid_load_policy()parses the file and builds a hash table ofsetid_ruleentries keyed by(source_uid, target_uid).- When a process calls
setuid(new_uid)orsetresuid():safesetid_task_fix_setuid()is invoked. - It checks whether a whitelist entry exists for
(current_uid, new_uid)viasafesetid_find_rule(current_uid, new_uid). - If no entry exists: return
-EACCES; the UID transition is denied even if the process hasCAP_SETUID. - The check applies transitively: if process A transitions to UID B, and B tries to transition to UID C, the rule
(B, C)must also exist in the whitelist.
Edge Cases & Failure Modes
- Policy not loaded on boot: If SafeSetID is compiled in but no policy is loaded, all UID transitions are allowed (the default); the security benefit only activates once a policy is explicitly loaded.
- Wildcard transition blocker: The special rule
source_uid:CAP_SETUID_UNSAFEblocks a UID from ever usingCAP_SETUIDto transition to a UID not in the whitelist; a misconfigured wildcard rule can lock out legitimate UID transitions. - GID vs. UID policies: SafeSetID can enforce both GID and UID transitions; a policy that covers UIDs but not GIDs allows a process to change to an arbitrary GID, potentially gaining access to group-protected resources.
- Interaction with PAM: PAM modules that call
setuid()/setgid()as part of login (e.g.,pam_unix) may fail silently if the UID transition they attempt is not in the SafeSetID whitelist, causing login failures without obvious error messages.
Integrity Measurement Architecture (IMA) (`security/integrity/ima/`)
IMA (Integrity Measurement Architecture) is the kernel's runtime integrity subsystem.
Definition
IMA (Integrity Measurement Architecture) is the kernel's runtime integrity subsystem. It measures (hashes) files as they are opened for execution, reads, or mmap'd, and stores the measurements in an in-kernel log and in a TPM PCR (Platform Configuration Register). The companion EVM (Extended Verification Module) verifies file metadata integrity using HMAC or digital signatures stored in extended attributes. Together they detect unauthorized file modifications.
Execution Flow
- At boot:
ima_init()initializes the measurement list and extends TPM PCR 10 with an initial aggregate hash. - A file is opened:
security_file_open()→ima_file_check()→ evaluates the IMA policy (rules specifying which files to measure/appraise). - If the policy matches:
ima_collect_measurement()reads the file's hash (SHA-256 by default) usingcrypto_shash_digest(). - The measurement is added to the IMA measurement list (
ima_add_template_entry()). ima_pcr_extend()extends TPM PCR 10 with the hash of the measurement, cryptographically chaining it.- For EVM appraisal:
evm_inode_setxattr()readssecurity.imaxattr (expected hash or signature);ima_appraise_measurement()compares the measured hash to the expected value. - If appraisal fails: in
enforcemode,security_inode_permission()returns-EACCES; infixmode, the xattr is updated. - The IMA log is accessible from userspace at
/sys/kernel/security/integrity/ima/ascii_runtime_measurements.
Edge Cases & Failure Modes
- TPM unavailability: Without a TPM, IMA measurements are still logged in the kernel's measurement list but cannot be hardware-attested; remote attestation workflows that require TPM-backed PCR values fail.
- IMA policy miss after hot-plug: Files opened before IMA policy is loaded are not measured; a policy that is loaded after system start has no measurements for pre-loaded binaries;
ima_policymust be loaded via initramfs for complete coverage. - EVM HMAC key compromise: EVM's HMAC key is stored in a kernel keyring (
_evm); if the key is extracted (e.g., via a cold-boot attack or memory dump), an attacker can forge valid EVM signatures for any file, bypassing appraisal. - Extended attribute loss on filesystem copy: If files are copied without preserving extended attributes (
cp --no-preserve=all, some archive tools),security.imaandsecurity.evmxattrs are lost; IMA appraisal fails for all copied files until xattrs are regenerated.