By @pageman
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width,initial-scale=1,viewport-fit=cover">
<title>Linux Kernel Component Taxonomy β 80 Core Components</title>
<style>
:root {
--bg: #0d1117;
--surface: #161b22;
--surface2: #1c2128;
--border: #30363d;
--text: #e6edf3;
--text-muted: #8b949e;
--code-bg: #1f2937;
--def-color: #58a6ff;
--flow-color: #3fb950;
--edge-color: #f78166;
color-scheme: dark;
box-sizing: border-box;
padding-top: env(safe-area-inset-top, 0px);
padding-bottom: env(safe-area-inset-bottom, 0px);
}
*,*::before,*::after { box-sizing: inherit; }
html,body { margin:0; padding:0; background:var(--bg); color:var(--text); font-family:'Segoe UI',system-ui,-apple-system,sans-serif; font-size:15px; line-height:1.6; }
a { color:inherit; text-decoration:none; }
/* STICKY HEADER */
.site-header {
position:sticky; top:0; z-index:100;
background:rgba(13,17,23,0.95); backdrop-filter:blur(10px);
border-bottom:1px solid var(--border);
padding:12px 20px;
display:flex; align-items:center; gap:16px; flex-wrap:wrap;
}
.site-title { font-size:1rem; font-weight:700; color:var(--text); flex:1; min-width:200px; }
.site-title span { color:#58a6ff; }
.counter { font-size:0.75rem; color:var(--text-muted); background:var(--surface2); padding:3px 8px; border-radius:12px; border:1px solid var(--border); }
.search-wrap { position:relative; }
#search { background:var(--surface2); border:1px solid var(--border); border-radius:6px; color:var(--text); padding:6px 12px 6px 32px; font-size:0.85rem; width:220px; outline:none; }
#search:focus { border-color:#58a6ff; }
.search-icon { position:absolute; left:9px; top:50%; transform:translateY(-50%); color:var(--text-muted); font-size:0.9rem; pointer-events:none; }
#clear-search { background:none; border:none; color:var(--text-muted); cursor:pointer; padding:4px 8px; font-size:0.85rem; border-radius:4px; }
#clear-search:hover { color:var(--text); }
/* CATEGORY NAV */
.cat-nav {
background:var(--surface); border-bottom:1px solid var(--border);
padding:8px 20px; display:flex; gap:6px; flex-wrap:wrap; align-items:center;
position:sticky; top:49px; z-index:99;
}
.cat-nav-label { font-size:0.75rem; color:var(--text-muted); font-weight:600; letter-spacing:.05em; margin-right:4px; }
.nav-cat {
font-size:0.75rem; padding:4px 10px; border-radius:20px;
border:1px solid var(--border); color:var(--text-muted);
cursor:pointer; transition:all .15s; background:transparent;
white-space:nowrap;
}
.nav-cat:hover, .nav-cat.active {
background:color-mix(in srgb, var(--acc) 20%, transparent);
color:var(--acc);
border-color:var(--acc);
}
.nav-cat.all-btn { color:var(--def-color); border-color:var(--def-color)40; }
.nav-cat.all-btn.active, .nav-cat.all-btn:hover { background:var(--def-color)20; }
/* MAIN */
.main { max-width:960px; margin:0 auto; padding:24px 20px 60px; }
.section-heading {
position:sticky; top:85px; z-index:50;
font-size:0.75rem; font-weight:700; letter-spacing:.08em; text-transform:uppercase;
color:var(--text-muted); background:var(--bg); padding:12px 0 8px;
border-bottom:1px solid var(--border); margin:32px 0 16px;
display:flex; align-items:center; gap:10px;
}
.section-heading::before {
content:''; display:inline-block; width:12px; height:12px;
border-radius:50%; background:var(--acc); flex-shrink:0;
}
.no-results { text-align:center; color:var(--text-muted); padding:60px 20px; font-size:1rem; }
/* CARDS */
.card {
background:var(--surface); border:1px solid var(--border);
border-radius:10px; margin-bottom:14px; overflow:hidden;
border-left:3px solid var(--acc);
transition:box-shadow .15s;
}
.card:hover { box-shadow:0 0 0 1px var(--acc)40; }
.card-header {
display:flex; align-items:center; gap:10px;
padding:14px 18px 12px; cursor:pointer;
user-select:none;
}
.item-num { font-size:0.75rem; font-weight:700; color:var(--acc); font-family:monospace; min-width:28px; }
.item-title { font-size:0.95rem; font-weight:600; color:var(--text); flex:1; margin:0; }
.cat-badge { font-size:0.65rem; padding:2px 7px; border-radius:12px; border:1px solid; white-space:nowrap; }
.toggle-icon { color:var(--text-muted); font-size:0.8rem; transition:transform .2s; flex-shrink:0; }
.card.open .toggle-icon { transform:rotate(180deg); }
.card-body { display:none; padding:0 18px 18px; }
.card.open .card-body { display:block; }
.field { margin-bottom:16px; }
.field:last-child { margin-bottom:0; }
.field-label {
font-size:0.7rem; font-weight:700; letter-spacing:.06em; text-transform:uppercase;
margin:0 0 6px; padding:4px 0;
border-bottom:1px solid var(--border);
}
.def-label { color:var(--def-color); border-bottom-color:var(--def-color)30; }
.flow-label { color:var(--flow-color); border-bottom-color:var(--flow-color)30; }
.edge-label { color:var(--edge-color); border-bottom-color:var(--edge-color)30; }
.field-content p { margin:0 0 8px; color:var(--text); font-size:0.9rem; }
.field-content p:last-child { margin-bottom:0; }
.field-content ol, .field-content ul { margin:4px 0 8px 0; padding-left:22px; color:var(--text); font-size:0.88rem; }
.field-content li { margin-bottom:5px; }
.field-content strong { color:var(--text); }
code { background:var(--code-bg); color:#79c0ff; padding:1px 5px; border-radius:4px; font-family:'Cascadia Code',Consolas,monospace; font-size:0.82em; }
/* EXPAND ALL */
.controls { display:flex; gap:8px; margin-bottom:16px; }
.ctrl-btn { background:var(--surface2); border:1px solid var(--border); color:var(--text-muted); padding:5px 12px; border-radius:6px; cursor:pointer; font-size:0.8rem; }
.ctrl-btn:hover { color:var(--text); border-color:var(--text-muted); }
/* FOOTER */
.footer { text-align:center; color:var(--text-muted); font-size:0.78rem; padding:20px; border-top:1px solid var(--border); margin-top:40px; }
@media(max-width:600px) {
.site-header { padding:10px 14px; }
.cat-nav { top:45px; padding:6px 14px; }
.main { padding:16px 14px 40px; }
#search { width:160px; }
.section-heading { top:80px; }
.item-title { font-size:0.85rem; }
}
</style>
</head>
<body>
<header class="site-header">
<div class="site-title">π§ <span>Linux Kernel</span> Component Taxonomy</div>
<span class="counter" id="visible-counter">80 / 80 items</span>
<div class="search-wrap">
<span class="search-icon">π</span>
<input type="text" id="search" placeholder="Search componentsβ¦" oninput="doSearch(this.value)" autocomplete="off">
</div>
<button id="clear-search" onclick="clearSearch()" style="display:none">β Clear</button>
</header>
<nav class="cat-nav">
<span class="cat-nav-label">Filter:</span>
<a href="#" class="nav-cat all-btn active" onclick="filterCat('all'); return false">All 8 categories</a>
<a href="#cat1" class="nav-cat" style="--acc:#4a9ede" onclick="filterCat('1')">1. Core Kernel Subsystems</a>
<a href="#cat2" class="nav-cat" style="--acc:#9a6ede" onclick="filterCat('2')">2. Synchronization Primitives</a>
<a href="#cat3" class="nav-cat" style="--acc:#4ede9a" onclick="filterCat('3')">3. Memory Allocators</a>
<a href="#cat4" class="nav-cat" style="--acc:#de9a4a" onclick="filterCat('4')">4. Process & CPU Schedulers</a>
<a href="#cat5" class="nav-cat" style="--acc:#de4a6e" onclick="filterCat('5')">5. Block & I/O Schedulers</a>
<a href="#cat6" class="nav-cat" style="--acc:#4aaede" onclick="filterCat('6')">6. Virtual Filesystems (VFS)</a>
<a href="#cat7" class="nav-cat" style="--acc:#9ade4a" onclick="filterCat('7')">7. Network Stack Hooks</a>
<a href="#cat8" class="nav-cat" style="--acc:#ae4ade" onclick="filterCat('8')">8. Linux Security Modules (LSMs)</a>
</nav>
<main class="main">
<div class="controls">
<button class="ctrl-btn" onclick="expandAll()">Expand all</button>
<button class="ctrl-btn" onclick="collapseAll()">Collapse all</button>
</div>
<div id="items-container">
<div class="card" id="item_1_1" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.1</span>
<h3 class="item-title">Process Creation Subsystem (`do_fork` / `copy_process`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>fork(2)</code>, <code>vfork(2)</code>, <code>clone(2)</code>, and <code>clone3(2)</code> syscalls and is centered in <code>kernel/fork.c</code> around <code>copy_process()</code>.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Userspace calls <code>fork()</code>, <code>vfork()</code>, <code>clone()</code>, or <code>clone3()</code>.</li>
<li>The syscall entry (<code>sys_clone</code>, <code>sys_fork</code>, etc.) collects flags and enters <code>kernel_clone()</code>.</li>
<li><code>copy_process()</code> is called: it allocates a new <code>task_struct</code> via <code>dup_task_struct()</code>, which copies the kernel stack and sets up <code>thread_info</code>.</li>
<li>Task struct fields are initialized: counters reset, PID assigned from the PID namespace via <code>alloc_pid()</code>.</li>
<li>Depending on <code>CLONE_*</code> flags: <code>copy_mm()</code> duplicates or shares the address space; <code>copy_files()</code> duplicates or shares file descriptors; <code>copy_sighand()</code> duplicates signal handlers.</li>
<li>The new task is inserted into the task list under <code>tasklist_lock</code>.</li>
<li><code>wake_up_new_task()</code> places the child on a run queue with TASK_RUNNING state.</li>
<li>The scheduler may preempt the parent and begin running the child immediately (copy-on-write pages remain shared until first write-fault).</li>
<li>Both parent and child return from the syscall: parent receives the child's PID, child receives 0.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>ENOMEM</strong>: If <code>dup_task_struct()</code> or <code>copy_mm()</code> fails (OOM condition), <code>copy_process()</code> unwinds via <code>bad_fork_*</code> error labels; partial allocations are freed.</li>
<li><strong>PID namespace exhaustion</strong>: <code>alloc_pid()</code> returns <code>NULL</code> if the namespace's PID range is saturated; the fork fails with <code>EAGAIN</code>.</li>
<li><strong><code>RLIMIT_NPROC</code> exceeded</strong>: If the user's process count exceeds the rlimit, <code>copy_process()</code> returns <code>EAGAIN</code>; this is bypassed for <code>CAP_SYS_ADMIN</code>.</li>
<li><strong><code>vfork()</code> deadlock</strong>: The parent blocks on a completion until the child calls <code>exec()</code> or exits; if the child sleeps indefinitely, the parent is permanently blocked.</li>
<li><strong>Signal pending during fork</strong>: A pending fatal signal to the parent before <code>wake_up_new_task()</code> causes the entire fork to be unwound.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_2" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.2</span>
<h3 class="item-title">Interrupt Request (IRQ) Subsystem (`kernel/irq/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>irq_chip</code> abstraction layer.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>At boot, <code>irq_init_percpu_irqstack()</code> and architecture-specific <code>init_IRQ()</code> set up interrupt stacks and the IDT/GIC.</li>
<li>A driver calls <code>request_irq()</code> β <code>__setup_irq()</code>, which allocates an <code>irqaction</code> and links it to an <code>irq_desc</code> for the given IRQ number.</li>
<li>Hardware asserts an interrupt line; the CPU saves registers and jumps to the architecture's interrupt entry stub (<code>entry_64.S</code>).</li>
<li><code>handle_irq()</code> β <code>generic_handle_irq()</code> β <code>handle_level_irq()</code> / <code>handle_edge_irq()</code> depending on the <code>irq_desc->handle_irq</code> function pointer.</li>
<li>The irqchip's <code>irq_mask</code> or <code>irq_ack</code> is called to prevent re-entry.</li>
<li>The registered <code>irqaction->handler</code> runs in interrupt context (hardirq).</li>
<li>The handler returns <code>IRQ_HANDLED</code> or <code>IRQ_NONE</code>; if none of the handlers claim the IRQ, the kernel logs an unhandled interrupt.</li>
<li>The irqchip's <code>irq_unmask</code> / <code>irq_eoi</code> is called.</li>
<li>The CPU restores registers and resumes the interrupted task via <code>iret</code>/<code>eret</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>IRQ storm</strong>: A misbehaving device asserts its line continuously; the kernel detects this via <code>irq_safe_remove()</code> logic and may disable the IRQ after a threshold (bad IRQ detection in <code>handle_level_irq()</code>).</li>
<li><strong>Shared IRQ conflict</strong>: Multiple devices on the same line (legacy PCI); if one device's handler fails to claim <code>IRQ_HANDLED</code>, spurious IRQ warnings accumulate.</li>
<li><strong>NMI nesting</strong>: Non-Maskable Interrupts cannot be disabled; nested NMIs on x86 require the <code>nmi_nesting_preprocess</code> guard in <code>arch/x86/kernel/nmi.c</code> to prevent stack corruption.</li>
<li><strong>Interrupt affinity migration race</strong>: Changing <code>/proc/irq/N/smp_affinity</code> while an interrupt is in-flight can send EOI to the wrong CPU's APIC, causing the IRQ to be silently lost.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_3" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.3</span>
<h3 class="item-title">System Call Interface (`arch/x86/entry/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>SYSCALL</code>/<code>SYSRET</code> instructions; on ARM64, <code>SVC #0</code>. The interface dispatches through a syscall table (<code>sys_call_table</code>) indexed by syscall number.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Userspace loads the syscall number into <code>rax</code> (x86-64) and arguments into <code>rdi</code>, <code>rsi</code>, <code>rdx</code>, <code>r10</code>, <code>r8</code>, <code>r9</code>, then executes <code>syscall</code>.</li>
<li>The CPU switches to ring 0, saves <code>rip</code>/<code>rflags</code> to per-CPU state, loads the kernel <code>rsp</code>, and jumps to <code>entry_SYSCALL_64</code> in <code>arch/x86/entry/entry_64.S</code>.</li>
<li>The entry stub saves all registers to the kernel stack (<code>struct pt_regs</code>).</li>
<li><code>do_syscall_64()</code> is called; it fetches the syscall number from <code>regs->orig_ax</code>.</li>
<li>Bounds-checks the number against <code>NR_syscalls</code>; looks up <code>sys_call_table[nr]</code>.</li>
<li>Runs any active <code>seccomp</code> filters (BPF programs) before dispatch.</li>
<li>Calls the syscall handler (e.g., <code>sys_read</code>, <code>sys_mmap</code>); handler returns a <code>long</code> result.</li>
<li>The return value is placed in <code>regs->ax</code>.</li>
<li>The entry stub restores saved registers and executes <code>sysretq</code> to return to userspace at the saved <code>rip</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Invalid syscall number</strong>: Numbers β₯ <code>NR_syscalls</code> return <code>βENOSYS</code>.</li>
<li><strong><code>seccomp</code> SIGSYS kill</strong>: A BPF filter returning <code>SECCOMP_RET_KILL_PROCESS</code> delivers <code>SIGSYS</code> and kills the process before the syscall handler is reached.</li>
<li><strong>Signal pending at syscall exit</strong>: <code>exit_to_user_mode_prepare()</code> checks for pending signals; if found, the syscall returns with <code>βEINTR</code> or <code>βERESTARTSYS</code> before userspace sees the result.</li>
<li><strong><code>SMAP</code>/<code>SMEP</code> violations</strong>: If the kernel accidentally dereferences a userspace pointer without <code>copy_from_user()</code>, <code>SMAP</code> raises a fault; the kernel oopses rather than allowing privilege escalation.</li>
<li><strong>Speculation side-channels (Spectre v2 / Retpoline)</strong>: The indirect <code>call</code> through <code>sys_call_table</code> is protected by <code>retpoline</code> or <code>IBRS</code>; disabling mitigations can re-open the attack surface.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_4" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.4</span>
<h3 class="item-title">Workqueue Subsystem (`kernel/workqueue.c`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 (<code>struct work_struct</code>), and thread pools organized as <code>worker_pool</code> objects per CPU and per NUMA node.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A kernel subsystem defines a <code>work_struct</code> and initializes it with <code>INIT_WORK(&work, handler_fn)</code>.</li>
<li><code>queue_work()</code> β <code>__queue_work()</code> selects the appropriate <code>worker_pool</code> (bound to the current CPU for normal workqueues, or unbound for UNBOUND workqueues).</li>
<li>The work item is added to the pool's <code>worklist</code>.</li>
<li>If no idle worker is available and the pool is below the concurrency target, <code>create_worker()</code> spawns a new kworker kernel thread.</li>
<li>The kworker thread calls <code>worker_thread()</code> β <code>process_one_work()</code>.</li>
<li><code>process_one_work()</code> calls the handler function: <code>work->func(work)</code>.</li>
<li>After the handler returns, the worker checks for more pending work; if none, it goes idle.</li>
<li>Idle workers are reaped after <code>IDLE_WORKER_TIMEOUT</code> (5 minutes) to prevent thread proliferation.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Work item requeue during flush</strong>: Calling <code>queue_work()</code> from within a handler re-enqueues for the next iteration; calling <code>flush_work()</code> from within the same workqueue deadlocks.</li>
<li><strong>Worker pool stall (watchdog)</strong>: If all workers are blocked (e.g., waiting on a mutex held by work in the same pool), <code>wq_watchdog_timer_fn()</code> fires after <code>wq_watchdog_thresh</code> seconds and dumps a stack trace.</li>
<li><strong>Memory allocation failure in <code>create_worker()</code></strong>: If <code>kthread_create()</code> fails during worker creation, the pool falls back to existing workers; if zero workers exist, work is never processed.</li>
<li><strong><code>WQ_MEM_RECLAIM</code> ordering</strong>: Non-<code>WQ_MEM_RECLAIM</code> workqueues 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_5" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.5</span>
<h3 class="item-title">Kernel Timer Subsystem (`kernel/time/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The timer subsystem provides two classes of kernel timers: <code>hrtimer</code> (high-resolution timers backed by CLOCK_MONOTONIC/CLOCK_REALTIME, using hardware timer interrupts down to nanosecond resolution) and legacy <code>timer_list</code> (low-resolution jiffies-based timers). It also exposes POSIX timers to userspace via <code>timer_create(2)</code>.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A caller initializes a timer: <code>hrtimer_init(&ht, CLOCK_MONOTONIC, HRTIMER_MODE_REL)</code> and sets <code>ht.function = callback</code>.</li>
<li><code>hrtimer_start()</code> calls <code>hrtimer_start_range_ns()</code>, which inserts the timer into the per-CPU <code>hrtimer_clock_base</code> red-black tree ordered by expiry time.</li>
<li>The hardware timer (TSC-deadline, HPET, or ARM architected timer) is programmed to fire at the earliest expiry in the tree.</li>
<li>When the hardware fires, the interrupt handler calls <code>hrtimer_interrupt()</code>.</li>
<li><code>hrtimer_interrupt()</code> iterates expired timers from the rbtree front: calls <code>timer->function(timer)</code>.</li>
<li>The callback returns <code>HRTIMER_RESTART</code> (re-arms) or <code>HRTIMER_NORESTART</code> (removes from tree).</li>
<li>The hardware timer is reprogrammed for the next expiry.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Cascading timer overload</strong>: If hundreds of timers expire simultaneously, <code>hrtimer_interrupt()</code> processes them all in one IRQ context, extending interrupt latency significantly.</li>
<li><strong>Clock discontinuity</strong>: Calling <code>settimeofday()</code> or <code>adjtimex()</code> while <code>CLOCK_REALTIME</code>-based hrtimers are pending can cause incorrect future expiry; <code>CLOCK_MONOTONIC</code> timers are immune.</li>
<li><strong><code>timer_list</code> overflows</strong>: Jiffies-based timers use <code>timer_wheels</code>; a timer set for more than <code>MAX_JIFFY_OFFSET</code> jiffies into the future wraps silently and fires immediately.</li>
<li><strong><code>nohz_full</code> interactions</strong>: On CPUs in <code>nohz_full</code> mode, the tick is suppressed; timers are only re-evaluated when a wake-up event occurs, adding up to one-tick jitter to expected expiry.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_6" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.6</span>
<h3 class="item-title">Power Management Framework (`drivers/base/power/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>cpuidle</code> and <code>cpufreq</code> subsystems).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A userspace tool writes <code>mem</code> or <code>disk</code> to <code>/sys/power/state</code>.</li>
<li><code>enter_state()</code> β <code>pm_prepare()</code> calls each device driver's <code>.prepare()</code> callback in topological order (children before parents).</li>
<li><code>dpm_suspend()</code> calls <code>.suspend()</code> callbacks on all devices (device PM list traversal).</li>
<li><code>dpm_suspend_late()</code> / <code>dpm_suspend_noirq()</code> follow, allowing drivers to cut clocks/power after IRQs are disabled.</li>
<li>CPU-specific suspend: each CPU is taken offline except the last; the last CPU calls <code>arch_suspend_cpu()</code> which issues the platform-specific sleep instruction (e.g., ACPI <code>_GTS</code>, ARM PSCI).</li>
<li>On wake: the platform restores CPU state; <code>arch_resume_cpu()</code> runs; IRQs re-enabled.</li>
<li><code>dpm_resume_noirq()</code> β <code>dpm_resume_early()</code> β <code>dpm_resume()</code> calls <code>.resume()</code> in reverse topological order.</li>
<li><code>pm_finish()</code> calls <code>.complete()</code> on all devices; the system returns to <code>S0</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Driver suspend failure</strong>: A driver returning non-zero from <code>.suspend()</code> aborts the suspend; <code>dpm_resume()</code> is called on already-suspended devices to restore state.</li>
<li><strong>Firmware / ACPI AML bugs</strong>: BIOS <code>_PTS</code> or <code>_WAK</code> methods can crash or wedge the system; <code>acpi_suspend_error</code> paths attempt to recover but sometimes leave hardware in a broken state.</li>
<li><strong>Hibernation image corruption</strong>: 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.</li>
<li><strong>Runtime PM reference count leak</strong>: A driver calling <code>pm_runtime_get()</code> without a matching <code>pm_runtime_put()</code> prevents the device from ever entering a low-power state.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_7" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.7</span>
<h3 class="item-title">Device Model and sysfs (`drivers/base/`, `fs/sysfs/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>sysfs</code> (a virtual filesystem mounted at <code>/sys</code>), enabling enumeration, configuration, and udev event delivery for hotplug.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A bus driver (e.g., PCI) scans for devices and calls <code>device_register()</code> for each discovered device.</li>
<li><code>device_register()</code> β <code>kobject_add()</code> creates a <code>kobject</code> node in the sysfs hierarchy under <code>/sys/devices/</code>.</li>
<li><code>bus_probe_device()</code> iterates registered drivers; for each, calls <code>driver_match_device()</code> (uses device IDs or DT compatible strings).</li>
<li>On match, <code>driver_probe_device()</code> calls <code>driver->probe()</code>.</li>
<li>The driver claims the device; attributes are created via <code>device_create_file()</code>, populating <code>sysfs</code> attribute files.</li>
<li>A <code>uevent</code> is sent via <code>kobject_uevent()</code> β <code>netlink_broadcast()</code> to inform <code>udevd</code> of the new device.</li>
<li><code>udevd</code> processes the event, creates <code>/dev</code> nodes, loads firmware, runs <code>udev</code> rules.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Driver probe failure</strong>: If <code>probe()</code> returns an error, <code>driver_probe_device()</code> decrements the driver's reference count; if no other driver matches, the device sits unbound.</li>
<li><strong>Probe deferral (<code>-EPROBE_DEFER</code>)</strong>: A driver may return <code>-EPROBE_DEFER</code> if a dependency (e.g., a GPIO chip) is not yet available; the kernel re-queues the probe after any new device is registered.</li>
<li><strong>sysfs attribute race</strong>: Reading a sysfs attribute while <code>device_unregister()</code> is running can reference freed memory if the driver did not hold the device reference count correctly.</li>
<li><strong><code>kobject</code> reference count underflow</strong>: Calling <code>kobject_put()</code> more times than <code>kobject_get()</code> triggers a <code>BUG()</code> in <code>kobject_release()</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_8" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.8</span>
<h3 class="item-title">Kernel Module Loader (`kernel/module/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The module loader implements <code>insmod</code>/<code>modprobe</code> support: it verifies ELF64 <code>.ko</code> files for valid <code>vermagic</code> (kernel version + config hash), applies relocations, resolves symbol dependencies against the kernel's exported symbol table (<code>ksymtab</code>), runs module initialization, and later handles safe removal.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Userspace calls <code>finit_module(fd, params, flags)</code> or <code>init_module(buf, len, params)</code>.</li>
<li><code>load_module()</code> reads the ELF sections into kernel memory via <code>vmalloc_exec()</code>.</li>
<li><code>check_modinfo()</code> validates the <code>vermagic</code> string; mismatches abort immediately.</li>
<li><code>simplify_symbols()</code> resolves undefined symbols against <code>ksymtab</code> and <code>ksymtab_gpl</code>; unresolved symbols abort.</li>
<li><code>apply_relocations()</code> patches the module's code/data for the final load address (KASLR randomizes this).</li>
<li><code>module_init_layout_section()</code> sets up <code>__init</code> and <code>core</code> sections; <code>__init</code> is marked executable only during <code>do_one_initcall()</code>.</li>
<li><code>do_one_initcall(mod->init)</code> runs the module's <code>init_module()</code> function.</li>
<li>On success, the module is added to <code>modules</code> list; <code>__init</code> sections are freed.</li>
<li>On <code>rmmod</code>: <code>module_exit()</code> is called; <code>free_module()</code> unmaps the ELF image; symbols are removed from the lookup table.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Symbol version mismatch</strong>: Even if the symbol name matches, a CRC checksum mismatch (<code>CONFIG_MODVERSIONS</code>) causes <code>ENOEXEC</code>.</li>
<li><strong><code>init()</code> failure</strong>: If <code>init_module()</code> 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.</li>
<li><strong>Tainted kernel</strong>: Loading an unsigned or out-of-tree module sets the <code>TAINT_OOT_MODULE</code> flag; this affects crash dump analysis.</li>
<li><strong>Unload race</strong>: If a module is in use (reference count > 0), <code>rmmod</code> returns <code>EWOULDBLOCK</code>; force-removal (<code>rmmod -f</code>) bypasses this but can crash the kernel.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_9" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.9</span>
<h3 class="item-title">Memory Management Subsystem (`mm/`)</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The <code>mm/</code> subsystem is the kernel's unified memory management layer: it manages physical page frames (via the buddy allocator), virtual address spaces (<code>vm_area_struct</code> / <code>mmap</code>), page tables, demand paging, swap, and memory compaction/reclaim. It is the largest single subsystem in the kernel.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>mmap(2)</code> calls <code>do_mmap()</code> β <code>mmap_region()</code>, which allocates a <code>vm_area_struct</code> and inserts it into the process's <code>mm_struct</code> maple tree / red-black tree.</li>
<li>No physical pages are allocated yet (lazy allocation).</li>
<li>When the process accesses the mapped region, the CPU raises a page fault (<code>#PF</code> / <code>ESR_ELx_EC_DABT_LOW</code>).</li>
<li><code>do_page_fault()</code> β <code>handle_mm_fault()</code> β <code>handle_pte_fault()</code> determines the fault type: anonymous page, file-backed page, copy-on-write, or swap-in.</li>
<li>For anonymous faults: <code>do_anonymous_page()</code> calls <code>alloc_zeroed_user_highpage_movable()</code> (buddy allocator), sets up the PTE.</li>
<li>For file-backed: <code>do_fault()</code> calls the VMA's <code>vm_ops->fault()</code> to load the page from the page cache.</li>
<li><code>update_mmu_cache()</code> flushes the TLB entry.</li>
<li><code>kswapd</code> and <code>vmscan</code> run asynchronously to reclaim pages under memory pressure, writing dirty pages to swap or disk.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>OOM (Out-of-Memory)</strong>: When both physical memory and swap are exhausted, <code>out_of_memory()</code> invokes the OOM killer, which selects and kills a process based on <code>oom_score</code>.</li>
<li><strong>Huge page splinting</strong>: 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 <code>split_huge_page()</code>).</li>
<li><strong>Stack overflow</strong>: The stack VMA grows down; if a process exhausts its <code>RLIMIT_STACK</code>, the page fault is not on a valid VMA and delivers <code>SIGSEGV</code>.</li>
<li><strong><code>mmap_lock</code> contention</strong>: The <code>mmap_lock</code> (formerly <code>mmap_sem</code>) is a per-process read-write semaphore; under high contention (many threads faulting simultaneously), it becomes a scalability bottleneck.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_1_10" data-cat="1" style="--acc:#4a9ede">
<div class="card-header">
<span class="item-num">1.10</span>
<h3 class="item-title">VFS (Virtual Filesystem Switch) Core Layer</h3>
<span class="cat-badge" style="background:#4a9ede20;color:#4a9ede;border-color:#4a9ede40">Cat 1</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The VFS is the kernel's filesystem-independent abstraction layer. It defines generic <code>inode</code>, <code>dentry</code>, <code>file</code>, and <code>superblock</code> objects with operation tables (<code>inode_operations</code>, <code>file_operations</code>, <code>super_operations</code>) that concrete filesystems implement. This allows uniform syscall handling (open, read, write, stat) regardless of the underlying filesystem type.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A syscall like <code>open(path, flags)</code> β <code>do_sys_open()</code> β <code>do_filp_open()</code> enters the VFS.</li>
<li><code>path_openat()</code> performs pathname resolution via <code>walk_component()</code> and <code>lookup_fast()</code> / <code>lookup_slow()</code> against the dentry cache.</li>
<li>On cache miss, the filesystem's <code>inode_operations->lookup()</code> is called to load the dentry from storage.</li>
<li><code>vfs_open()</code> checks permissions via <code>inode_permission()</code> (which invokes LSM hooks).</li>
<li>A <code>struct file</code> is allocated and <code>f->f_op</code> is set from <code>inode->i_fop</code>.</li>
<li><code>f->f_op->open(inode, file)</code> is called (filesystem-specific open handler).</li>
<li>A file descriptor is allocated and placed in the process's <code>fdtable</code>.</li>
<li>Subsequent <code>read(fd)</code> / <code>write(fd)</code> calls are dispatched through <code>f->f_op->read_iter</code> / <code>write_iter</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Dentry cache poisoning</strong>: 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 <code>d_invalidate()</code> call).</li>
<li><strong><code>O_NOFOLLOW</code> + symlink race (TOCTOU)</strong>: Between the permission check and the open, a symlink can be replaced; <code>O_PATH</code> and <code>openat2(RESOLVE_NO_SYMLINKS)</code> mitigate this.</li>
<li><strong>File descriptor table exhaustion</strong>: Opening files without closing them exhausts the per-process <code>RLIMIT_NOFILE</code> limit; the <code>open()</code> call returns <code>EMFILE</code>.</li>
<li><strong>Stale NFS handles</strong>: For NFS-backed filesystems, a dentry can reference a file that has been deleted on the server; operations on it return <code>ESTALE</code>, which must be handled by the application.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_1" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.1</span>
<h3 class="item-title">Spinlock (`arch/x86/include/asm/spinlock.h`, `kernel/locking/spinlock.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 (<code>qspinlock</code>) uses a ticket-based protocol to ensure fairness.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>spin_lock(&lk)</code> calls <code>raw_spin_lock()</code>.</li>
<li>On x86 with <code>CONFIG_QUEUED_SPINLOCKS</code>: the lock byte is tested; if zero, an atomic CAS sets it to the current CPU's ticket.</li>
<li>If locked: the CPU enters a <code>PAUSE</code>-instruction loop, reading the lock byte until it matches the CPU's ticket (MCS/qspinlock queue position).</li>
<li>Once acquired, preemption is implicitly disabled (or explicitly via <code>spin_lock_irq()</code> which also disables local IRQs).</li>
<li>The critical section executes.</li>
<li><code>spin_unlock(&lk)</code> atomically increments the lock's serving counter, releasing the next waiter in the queue.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Deadlock on same CPU</strong>: Attempting to acquire a spinlock already held on the same CPU (without <code>spin_trylock</code>) causes an infinite loop; <code>CONFIG_DEBUG_SPINLOCK</code> detects this.</li>
<li><strong>Lock held across sleep</strong>: If code holding a spinlock calls any function that may sleep (e.g., <code>kmalloc(GFP_KERNEL)</code>), it triggers a <code>might_sleep()</code> BUG if <code>CONFIG_DEBUG_ATOMIC_SLEEP</code> is set.</li>
<li><strong>Interrupt nesting</strong>: Failing to use <code>spin_lock_irqsave()</code> in interrupt-context code can allow IRQ re-entry that tries to re-acquire the same spinlock, causing a deadlock.</li>
<li><strong>Cache line bouncing</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_2" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.2</span>
<h3 class="item-title">Mutex (`kernel/locking/mutex.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>atomic_long_t</code> state combined with an MCS-node-based wait queue for fairness.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>mutex_lock(&m)</code> calls <code>__mutex_lock()</code>.</li>
<li>An optimistic fast-path: atomic CAS on <code>m->owner</code>; if the mutex is unlocked (owner = 0), it is set to the current task pointer, and the lock is acquired immediately.</li>
<li>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 (<code>mutex_optimistic_spin()</code>), avoiding a full sleep if the lock is released quickly.</li>
<li>Slow-path: the task is added to <code>m->wait_list</code>, sets its state to <code>TASK_UNINTERRUPTIBLE</code> (or <code>TASK_INTERRUPTIBLE</code> for <code>mutex_lock_interruptible()</code>), and calls <code>schedule()</code>.</li>
<li>When the current owner calls <code>mutex_unlock()</code>, it clears <code>m->owner</code> and wakes the first waiter via <code>wake_up_process()</code>.</li>
<li>The woken task re-attempts the fast-path; on success, it clears TASK_UNINTERRUPTIBLE and continues.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Priority inversion</strong>: A low-priority task holding a mutex blocks a high-priority task; the kernel's PI-mutex (<code>mutex_lock_pi()</code> via <code>rt_mutex</code>) implements priority inheritance to mitigate this.</li>
<li><strong>Self-deadlock detection</strong>: <code>CONFIG_DEBUG_MUTEXES</code> enables lock validation; a task acquiring a mutex it already holds triggers a BUG.</li>
<li><strong><code>mutex_lock_interruptible()</code> early return</strong>: If a signal arrives while waiting, the call returns <code>-EINTR</code>; the caller must handle the unacquired-lock case.</li>
<li><strong>Livelock (OSQ)</strong>: 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 <code>need_resched()</code> checks.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_3" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.3</span>
<h3 class="item-title">Read-Write Semaphore (`kernel/locking/rwsem.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>An <code>rwsem</code> allows multiple concurrent readers or a single exclusive writer. It is a sleeping lock (readers and writers may block). Used heavily for the <code>mmap_lock</code>, <code>i_rwsem</code> (inode), and <code>s_umount</code> (superblock) locks. Modern kernels use <code>rwsem</code> with an OSQ (Optimistic Spin Queue) for writers.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><strong>Read lock</strong>: <code>down_read(&sem)</code> β fast-path: atomically increments the reader count field if no writer is active or waiting.</li>
<li>If a writer is pending, the reader enqueues to <code>wait_list</code> with <code>RWSEM_WAITING_FOR_READ</code> state and calls <code>schedule()</code>.</li>
<li><strong>Write lock</strong>: <code>down_write(&sem)</code> β sets the <code>RWSEM_WRITER_LOCKED</code> bit via atomic CAS.</li>
<li>If readers are active, the writer OSQ-spins briefly, then enqueues with <code>RWSEM_WAITING_FOR_WRITE</code>.</li>
<li>The writer sleeps until all active readers call <code>up_read()</code>.</li>
<li>Last active reader calling <code>up_read()</code> checks for waiting writers; if any, wakes the first writer.</li>
<li>When the writer calls <code>up_write()</code>, it clears the writer-locked bit; if readers are queued, it wakes them all simultaneously (batch wake-up).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Writer starvation</strong>: A continuous stream of readers can prevent a writer from ever acquiring the lock; the kernel's <code>RWSEM_FLAG_WAITERS</code> bit causes new readers to queue once a writer is waiting.</li>
<li><strong>Downgrade race</strong>: <code>downgrade_write()</code> 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.</li>
<li><strong><code>mmap_lock</code> scale issue</strong>: The <code>mmap_lock</code> is an <code>rwsem</code>; 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_4" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.4</span>
<h3 class="item-title">RCU (Read-Copy-Update) (`kernel/rcu/`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>rcu_read_lock()</code> / <code>rcu_read_unlock()</code>, 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Reader: <code>rcu_read_lock()</code> disables preemption (or marks an RCU read-side critical section in <code>PREEMPT_RCU</code>).</li>
<li>Reader dereferences an RCU-protected pointer via <code>rcu_dereference(ptr)</code> (which includes a data dependency barrier / <code>smp_read_barrier_depends()</code>).</li>
<li>Reader reads the data; <code>rcu_read_unlock()</code> re-enables preemption.</li>
<li>Writer: allocates a new version of the data, copies and modifies it, then calls <code>rcu_assign_pointer(ptr, new_data)</code> (which includes a write memory barrier).</li>
<li>Writer calls <code>synchronize_rcu()</code> (or <code>call_rcu(&old_data->rcu_head, free_fn)</code> for async).</li>
<li><code>synchronize_rcu()</code> waits for a grace period: it blocks until all currently-executing RCU read-side critical sections on all CPUs complete.</li>
<li>After the grace period, the old data is safe to free.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Grace period stall</strong>: A CPU stuck in a long RCU read-side critical section (e.g., with preemption disabled for too long) delays <code>synchronize_rcu()</code> indefinitely; the RCU watchdog timer fires and prints a stall warning.</li>
<li><strong><code>rcu_dereference()</code> outside read-side</strong>: Dereferencing an RCU pointer outside <code>rcu_read_lock()</code> can read a pointer to freed memory; <code>CONFIG_PROVE_RCU</code> detects this.</li>
<li><strong>Expedited RCU side effects</strong>: <code>synchronize_rcu_expedited()</code> forcibly preempts CPUs to accelerate the grace period; this increases interrupt latency and should not be used in hot paths.</li>
<li><strong>SRCU (Sleepable RCU) deadlock</strong>: Unlike regular RCU, <code>srcu_read_lock()</code> can sleep; calling blocking operations inside an SRCU critical section is legal, but holding an SRCU lock and then calling <code>synchronize_srcu()</code> on the same <code>srcu_struct</code> deadlocks.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_5" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.5</span>
<h3 class="item-title">Seqlock (`include/linux/seqlock.h`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Reader: calls <code>read_seqbegin(&sl)</code> β reads and returns the current sequence counter value <code>seq</code>.</li>
<li>Reader reads the shared data (non-atomically, without locking).</li>
<li>Reader calls <code>read_seqretry(&sl, seq)</code> β reads the counter again; if it differs from <code>seq</code> or is odd (write in progress), returns <code>true</code> β reader retries from step 1.</li>
<li>Writer: calls <code>write_seqlock(&sl)</code> β acquires the embedded spinlock, then atomically increments the sequence counter (making it odd).</li>
<li>Writer modifies the shared data.</li>
<li>Writer calls <code>write_sequnlock(&sl)</code> β atomically increments the counter again (making it even), then releases the spinlock.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Livelock</strong>: 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.</li>
<li><strong>Non-retryable operations in reader</strong>: 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.</li>
<li><strong>Large critical sections</strong>: The kernel's <code>jiffies</code> and <code>timekeeper</code> use seqlocks; if the writer (clock interrupt handler) holds the lock for too long, readers on other CPUs spin repeatedly.</li>
<li><strong>Pointer dereference hazard</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_6" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.6</span>
<h3 class="item-title">Completion (`kernel/sched/completion.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>complete()</code>) and a consumer task (which calls <code>wait_for_completion()</code>). Used extensively in driver probe/unprobe sequences and kernel thread lifecycle management.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A completion is initialized: <code>init_completion(&done)</code> β sets <code>done.done = 0</code>, <code>done.wait</code> initialized.</li>
<li>The waiting task calls <code>wait_for_completion(&done)</code>:</li>
<li style="list-style-type:lower-alpha">Atomically checks <code>done.done</code>; if non-zero, decrements and returns immediately.</li>
<li style="list-style-type:lower-alpha">Otherwise, creates a <code>wait_queue_entry</code>, sets the task state to <code>TASK_UNINTERRUPTIBLE</code>, and adds itself to <code>done.wait</code>.</li>
<li style="list-style-type:lower-alpha">Calls <code>schedule()</code>; the task sleeps.</li>
<li>The signaling task calls <code>complete(&done)</code>:</li>
<li style="list-style-type:lower-alpha">Increments <code>done.done</code>.</li>
<li style="list-style-type:lower-alpha">Calls <code>wake_up_process()</code> on the first waiter in <code>done.wait</code>.</li>
<li>The sleeping task resumes from <code>schedule()</code>, re-checks <code>done.done</code>, and returns.</li>
<li>For broadcast wakeup: <code>complete_all(&done)</code> sets <code>done.done = UINT_MAX / 2</code> and wakes all waiters.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong><code>complete()</code> before <code>wait_for_completion()</code></strong>: This is safe; the <code>done</code> counter records the signal and the later <code>wait_for_completion()</code> returns immediately.</li>
<li><strong><code>complete()</code> without a waiter</strong>: The <code>done</code> counter accumulates; if <code>wait_for_completion()</code> is never called, the completion leaks but causes no crash (unless the memory is freed).</li>
<li><strong><code>wait_for_completion_killable()</code> early return</strong>: A fatal signal causes the function to return <code>-ERESTARTSYS</code>; the caller must handle the case where the waited-for event has not occurred.</li>
<li><strong>Re-initialization race</strong>: Calling <code>init_completion()</code> while another task is blocked in <code>wait_for_completion()</code> corrupts the wait queue; completions must not be re-initialized while in use.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_7" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.7</span>
<h3 class="item-title">Atomic Operations (`arch/x86/include/asm/atomic.h`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>Atomic operations provide CPU-guaranteed read-modify-write operations on integer values (<code>atomic_t</code>, <code>atomic64_t</code>, <code>atomic_long_t</code>) without requiring locks. They map to CPU-native instructions: on x86, <code>LOCK ADD</code>, <code>LOCK CMPXCHG</code>, <code>XCHG</code>; on ARM64, <code>LDADD</code>, <code>CAS</code> (ARMv8.1+). They serve as the foundation for reference counting, lock implementation, and wait-free counters.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A variable is declared: <code>atomic_t refcount = ATOMIC_INIT(1)</code>.</li>
<li><code>atomic_inc(&refcount)</code> compiles to a <code>LOCK ADDL $1, (mem)</code> on x86 β the <code>LOCK</code> prefix causes the CPU to assert the bus lock (or use cache coherency) guaranteeing the increment is indivisible.</li>
<li><code>atomic_dec_and_test(&refcount)</code> compiles to <code>LOCK DECL (mem)</code> followed by reading the zero flag β returns true if the result is zero.</li>
<li><code>atomic_cmpxchg(&v, old, new)</code> β <code>LOCK CMPXCHG</code> β atomically compares <code>v</code> to <code>old</code>; if equal, stores <code>new</code> and returns <code>old</code>; otherwise returns the current value.</li>
<li>Memory ordering variants: <code>atomic_read()</code> is a plain load with a compiler barrier; <code>smp_load_acquire()</code> / <code>smp_store_release()</code> add CPU-level acquire/release semantics.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>ABA problem</strong>: <code>atomic_cmpxchg()</code> succeeds even if the value was changed to <code>A</code>, then back to <code>A</code> between the load and the CAS; use tagged pointers or DCAS where this matters.</li>
<li><strong>Overflow/underflow</strong>: <code>atomic_t</code> is a 32-bit counter; overflow wraps silently. Use <code>refcount_t</code> (which uses <code>CONFIG_REFCOUNT_FULL</code> protection) for reference counts to catch accidental underflow to zero.</li>
<li><strong><code>refcount_t</code> saturation</strong>: The kernel's <code>refcount_t</code> saturates at INT_MAX to prevent integer overflow bugs from causing use-after-free; operations on a saturated counter warn but do not crash.</li>
<li><strong>Non-atomic accesses on 64-bit counters (32-bit CPUs)</strong>: On 32-bit kernels, <code>atomic64_t</code> operations require a lock (emulated) because 64-bit memory accesses are not natively atomic; this is a performance cliff.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_8" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.8</span>
<h3 class="item-title">Per-CPU Variables (`include/linux/percpu.h`, `mm/percpu.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>cpu_slab</code>).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A per-CPU variable is declared: <code>DEFINE_PER_CPU(unsigned long, mycounter)</code>.</li>
<li>At boot, <code>setup_per_cpu_areas()</code> allocates a contiguous memory region for each CPU, copies the initial values, and sets per-CPU base pointers.</li>
<li>Access: <code>get_cpu_var(mycounter)</code> disables preemption and returns a reference to the current CPU's copy via <code>this_cpu_ptr(&mycounter)</code> (which uses the <code>%gs</code> or <code>TPIDR_EL1</code> base register offset on x86/ARM64).</li>
<li>The variable is modified.</li>
<li><code>put_cpu_var(mycounter)</code> re-enables preemption.</li>
<li>For lockless access (safe only for statistics): <code>this_cpu_add(mycounter, 1)</code> uses a <code>LOCK</code>-free <code>ADD</code> via the <code>this_cpu_*</code> family of operations, which rely on the fact that only the local CPU writes this copy.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Preemption not disabled</strong>: If preemption is enabled when <code>this_cpu_ptr()</code> is used (not inside <code>get_cpu_var()</code>), the task can be migrated to another CPU between reading the pointer and dereferencing it, accessing the wrong CPU's copy.</li>
<li><strong>Interrupt context access</strong>: An interrupt handler can preempt code using <code>this_cpu_ptr()</code> on the same CPU; both access the same per-CPU variable without coordination, causing a data race if the interrupt handler also modifies it.</li>
<li><strong>Dynamic per-CPU allocation (<code>alloc_percpu()</code>)</strong>: The returned pointer must be freed with <code>free_percpu()</code>; a leak causes the per-CPU allocator's chunk pool to grow without bound.</li>
<li><strong>Hotplug CPU offline</strong>: When a CPU goes offline, its per-CPU data is not automatically migrated; subsystems must flush/drain per-CPU data in their <code>CPU_DEAD</code> notifier.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_9" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.9</span>
<h3 class="item-title">Futex (`kernel/futex/`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>futex(2)</code> syscall to block in the kernel. The kernel maintains a hash table of <code>futex_q</code> (futex queue) entries keyed by the physical address of the futex word.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Lock attempt: userspace atomically tries CAS on the futex word (<code>uaddr</code>); if it succeeds (word was 0, now 1), the lock is acquired without entering the kernel.</li>
<li>On contention (word was already 1): the thread sets a "has waiters" bit (word = 2) and calls <code>futex(FUTEX_WAIT, uaddr, expected_val, timeout)</code>.</li>
<li>Kernel: <code>do_futex()</code> β <code>futex_wait()</code> β computes the hash key (<code>futex_key</code>) from the futex word's physical page + offset.</li>
<li><code>futex_wait_setup()</code> verifies the futex value still equals <code>expected_val</code>; if it changed (racing unlock), returns immediately with <code>EAGAIN</code>.</li>
<li>The task is added to <code>hb->chain</code> (hash bucket wait queue) and calls <code>schedule_hrtimeout()</code>.</li>
<li>Unlock: the unlocking thread atomically clears the word; if "has waiters" bit was set, calls <code>futex(FUTEX_WAKE, uaddr, count)</code>.</li>
<li>Kernel: <code>futex_wake()</code> removes up to <code>count</code> waiters from the hash bucket and wakes them via <code>wake_up_q()</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Priority inversion</strong>: A low-priority holder blocks a high-priority waiter; <code>FUTEX_LOCK_PI</code> / <code>FUTEX_UNLOCK_PI</code> implement priority inheritance via RT-mutexes to prevent this.</li>
<li><strong>Spurious wakeup</strong>: A signal delivery wakes the futex waiter before the futex word changes; userspace must re-check the futex word in a loop.</li>
<li><strong><code>FUTEX_WAIT</code> / value race</strong>: Between the userspace CAS failure and the kernel <code>futex_wait_setup()</code> check, another thread may have already unlocked; the check catches this and returns <code>EAGAIN</code>, preventing a missed wakeup.</li>
<li><strong>Robust futex list corruption</strong>: If a process is killed while holding a robust futex, the kernel walks the robust list (<code>set_robust_list(2)</code>) to wake waiters with <code>FUTEX_OWNER_DIED</code>; a corrupt list pointer causes a kernel read of a bad address, triggering a fault in <code>handle_futex_death()</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_2_10" data-cat="2" style="--acc:#9a6ede">
<div class="card-header">
<span class="item-num">2.10</span>
<h3 class="item-title">Semaphore (`kernel/locking/semaphore.c`)</h3>
<span class="cat-badge" style="background:#9a6ede20;color:#9a6ede;border-color:#9a6ede40">Cat 2</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>A counting semaphore (<code>struct semaphore</code>) allows a specified number of concurrent holders, unlike a mutex (which allows exactly one). It is a sleeping primitive: <code>down()</code> decrements the count and sleeps if the result is negative; <code>up()</code> increments and wakes a waiter. Used for resource pools (e.g., limiting concurrent hardware accesses).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Initialization: <code>sema_init(&sem, N)</code> sets <code>sem.count = N</code> and initializes <code>sem.wait_list</code>.</li>
<li><code>down(&sem)</code> β <code>__down()</code>:</li>
<li style="list-style-type:lower-alpha">Atomically decrements <code>sem.count</code>.</li>
<li style="list-style-type:lower-alpha">If result β₯ 0, returns immediately (resource acquired).</li>
<li style="list-style-type:lower-alpha">If result < 0, adds the current task to <code>sem.wait_list</code> with state <code>TASK_UNINTERRUPTIBLE</code>, calls <code>schedule()</code>.</li>
<li><code>up(&sem)</code> β <code>__up()</code>:</li>
<li style="list-style-type:lower-alpha">Atomically increments <code>sem.count</code>.</li>
<li style="list-style-type:lower-alpha">If <code>wait_list</code> is non-empty, calls <code>wake_up_process()</code> on the first waiter.</li>
<li>The woken waiter re-runs from <code>schedule()</code> return, verifies it was woken by an <code>up()</code> (not spuriously), and returns.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Semaphore released without being acquired</strong>: Calling <code>up()</code> more times than <code>down()</code> raises the counter above its initial value, allowing more concurrent holders than intended; the kernel does not check for this.</li>
<li><strong><code>down_interruptible()</code> early return</strong>: Returns <code>-EINTR</code> on signal; the caller must handle the case where the resource was not acquired, to avoid resource leaks.</li>
<li><strong><code>down_trylock()</code> busy-wait abuse</strong>: Using <code>down_trylock()</code> in a tight loop is equivalent to spinning and wastes CPU; the caller should use the blocking <code>down()</code> or a semaphore-appropriate data structure.</li>
<li><strong>Priority inversion (no inheritance)</strong>: Unlike <code>rt_mutex</code>-based locks, the kernel <code>semaphore</code> has no priority inheritance; real-time tasks blocked on a semaphore held by a low-priority task may miss their deadlines.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_1" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.1</span>
<h3 class="item-title">Buddy Allocator (`mm/page_alloc.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>alloc_pages(gfp_flags, order)</code> β <code>__alloc_pages()</code>.</li>
<li><code>get_page_from_freelist()</code> iterates memory zones (ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM) in preference order.</li>
<li>For the target zone, <code>rmqueue()</code> checks the free list at the requested order.</li>
<li>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.</li>
<li>If no block at the requested order is available, <code>rmqueue()</code> tries the next higher order and splits.</li>
<li>If all higher orders are also empty: watermark check fails, <code>wake_up_kswapd()</code> is called to reclaim memory, and <code>__alloc_pages_slowpath()</code> tries OOM killer / migration.</li>
<li>Physical page address returned as <code>struct page *</code>; virtual mapping via <code>page_to_virt()</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>External fragmentation</strong>: Over time, free memory becomes fragmented into non-contiguous blocks; large-order allocations fail even when total free memory is sufficient. <code>CONFIG_COMPACTION</code> and <code>kcompactd</code> migrate movable pages to coalesce free space.</li>
<li><strong>Zone imbalance</strong>: If <code>ZONE_DMA32</code> is exhausted but <code>ZONE_NORMAL</code> has free pages, allocations requiring <code>GFP_DMA32</code> fail; devices that require DMA below 4 GiB report errors.</li>
<li><strong>Atomic allocation failures (<code>GFP_ATOMIC</code>)</strong>: Atomic allocations cannot sleep or reclaim; they draw from a reserved "emergency" pool (<code>min_free_kbytes</code>). If that pool is exhausted, the allocation fails and the caller must handle <code>NULL</code>.</li>
<li><strong>High-order allocation under pressure</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_2" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.2</span>
<h3 class="item-title">SLAB Allocator (`mm/slab.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The SLAB allocator (Bonwick 1994, Linux port ~2.0) manages pools of fixed-size kernel objects. Each pool (<code>kmem_cache</code>) 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>kmem_cache_create("name", object_size, align, flags, ctor)</code> creates a new cache; calculates optimal objects-per-slab and slab order.</li>
<li><code>kmem_cache_alloc(cache, gfp)</code> β checks the per-CPU cache (<code>array_cache</code>); if non-empty, returns the top-of-stack object (fast path, no locking).</li>
<li>If per-CPU cache is empty: <code>cache_alloc_refill()</code> fills it from the shared array (requires <code>cache_lock</code>); if shared array is empty, <code>cache_grow_begin()</code> allocates new pages from the buddy allocator and divides them into objects.</li>
<li>Object initialization: if a constructor (<code>ctor</code>) was provided, it is called on first use.</li>
<li><code>kmem_cache_free(cache, obj)</code> returns the object to the per-CPU cache top-of-stack.</li>
<li>When the per-CPU cache overflows its <code>batchcount</code>, objects are moved to the shared array; when that overflows, full slabs are returned to the buddy allocator.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Slab poisoning detection</strong>: With <code>CONFIG_DEBUG_SLAB</code>, freed objects are filled with <code>0x6b</code> ("k"); a later allocation that reads a non-poisoned value indicates a use-after-free.</li>
<li><strong>Cache aliasing</strong>: Multiple <code>kmem_cache_create()</code> calls with the same size may or may not share an underlying slab pool depending on <code>CONFIG_SLAB_MERGE_DEFAULT</code>; unintended sharing can lead to type confusion bugs.</li>
<li><strong>Per-CPU cache under/overflow in hot-unplug</strong>: When a CPU goes offline while its per-CPU cache holds objects, <code>free_block()</code> must flush those objects to the shared list; failure to do so leaks memory.</li>
<li><strong>Constructor called on reuse (SLAB only)</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_3" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.3</span>
<h3 class="item-title">SLUB Allocator (`mm/slub.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>kmem_cache_alloc(s, gfp)</code> β reads <code>s->cpu_slab->freelist</code> (locklessly, using <code>this_cpu_ptr</code>).</li>
<li>Fast path: if <code>freelist</code> is non-NULL, pops the first free object from the freelist (a pointer stored inside the object itself), returns it.</li>
<li>Slow path (<code>__slab_alloc()</code>): if the CPU slab is empty, tries the next partial slab on <code>s->node[nid]->partial</code>.</li>
<li>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.</li>
<li><code>kmem_cache_free(s, obj)</code> β <code>do_slab_free()</code>: pushes <code>obj</code> onto the CPU slab's freelist (lockless CAS using <code>this_cpu_cmpxchg_double</code>).</li>
<li>When the CPU slab becomes fully free, it is returned to the partial list or freed to the buddy allocator (based on <code>min_partial</code> threshold).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Double-free detection</strong>: SLUB stores a "freelist pointer" XOR'd with a secret in the object itself (<code>CONFIG_SLAB_FREELIST_HARDENED</code>); a double-free corrupts the XOR value and is detected on the next allocation with a <code>BUG_ON</code>.</li>
<li><strong>Redzone overwrite</strong>: <code>CONFIG_SLUB_DEBUG</code> adds redzones around objects; buffer overflows into the redzone are detected on free.</li>
<li><strong>Quarantine (KASAN)</strong>: Kernel Address Sanitizer delays reuse of freed SLUB objects; a use-after-free that accesses a quarantined object triggers an immediate KASAN report.</li>
<li><strong>NUMAism</strong>: SLUB maintains per-node partial lists; on NUMA systems, allocating from a remote node's slab incurs a NUMA penalty; the <code>kmem_cache_alloc_node()</code> API enforces local allocation.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_4" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.4</span>
<h3 class="item-title">SLOB Allocator (`mm/slob.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>kmalloc(size, gfp)</code> with SLOB selects one of three free lists by size bracket.</li>
<li><code>slob_alloc(size, gfp, align, node)</code> acquires <code>slob_lock</code> (global spinlock) and walks the selected free list.</li>
<li>First-fit: finds the first free block β₯ requested size.</li>
<li>If the block is significantly larger, it is split: the remainder becomes a new free block inserted after the allocated portion.</li>
<li>If no fit found: <code>slob_new_pages()</code> allocates a new page from the buddy allocator, initializes it as a SLOB page, and retries.</li>
<li><code>kfree(obj)</code> β <code>slob_free()</code> acquires <code>slob_lock</code>, inserts the block back into the appropriate free list in address order, and coalesces with adjacent free blocks.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Global lock bottleneck</strong>: The single <code>slob_lock</code> serializes all allocations and frees; SLOB is entirely unsuitable for SMP workloads above trivial scale.</li>
<li><strong>Fragmentation (no compaction)</strong>: SLOB has no per-slab concept; fragmentation accumulates and is never compacted, leading to wasted memory over time.</li>
<li><strong>No NUMA awareness</strong>: SLOB is unaware of NUMA topology; all allocations come from the same free list regardless of NUMA node.</li>
<li><strong>Deprecation path</strong>: SLOB was removed from mainline Linux in kernel 6.4 (<code>CONFIG_SLOB</code> removed); code relying on it must migrate to SLUB.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_5" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.5</span>
<h3 class="item-title">`vmalloc` / `vmap` (`mm/vmalloc.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>vmalloc()</code> allocates virtually contiguous but physically discontiguous memory by mapping individual (potentially non-contiguous) physical pages into a contiguous range in the kernel's <code>vmalloc</code> area (above <code>VMALLOC_START</code>). It is used when large allocations are needed but physically contiguous pages cannot be guaranteed.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>vmalloc(size)</code> β <code>__vmalloc_node()</code>.</li>
<li>A <code>vm_struct</code> is allocated (describes the virtual range) and inserted into the vmalloc Red-Black tree.</li>
<li><code>get_vm_area_caller()</code> finds a gap in the vmalloc address space for the requested size (aligned to page boundaries).</li>
<li>For each page in the allocation: <code>alloc_page(GFP_KERNEL)</code> obtains a physical page (order 0) from the buddy allocator.</li>
<li><code>map_kernel_range()</code> / <code>vmap_pages_range()</code> establishes page table entries mapping the virtual range to the allocated physical pages.</li>
<li><code>flush_cache_vmap()</code> flushes TLB entries for the new mapping.</li>
<li>Returns the virtual address of the start of the mapping.</li>
<li><code>vfree(addr)</code> unmaps page tables, frees each physical page to the buddy allocator, and removes the <code>vm_struct</code> from the tree.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>vmalloc space exhaustion</strong>: The vmalloc area is finite (128 TiB on x86-64 by default); a leak of <code>vm_struct</code> entries or large vmalloc allocations without <code>vfree()</code> can exhaust it.</li>
<li><strong>TLB shootdown cost</strong>: Each <code>vfree()</code> 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.</li>
<li><strong>Non-contiguous physical pages</strong>: Drivers that use <code>vmalloc()</code>-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.</li>
<li><strong><code>vmap()</code> on highmem pages (32-bit kernels)</strong>: Mapping <code>ZONE_HIGHMEM</code> pages via <code>vmap()</code> is the standard way to access them on 32-bit kernels; <code>kunmap_atomic()</code> must be called promptly to avoid kmap slot exhaustion.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_6" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.6</span>
<h3 class="item-title">`kmalloc` / `kfree` (`include/linux/slab.h`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>kmalloc(size, gfp_flags)</code> 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 <code>kmem_cache</code> whose object size is the smallest power-of-two β₯ <code>size</code>. The returned memory is physically and virtually contiguous (unlike <code>vmalloc</code>).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>kmalloc(size, gfp)</code> β <code>__kmalloc()</code>.</li>
<li><code>kmalloc_slab(size, gfp)</code> looks up the appropriate <code>kmem_cache</code> from <code>kmalloc_caches[type][index]</code> where <code>index = ilog2(roundup_pow_of_two(size))</code>.</li>
<li>If size is 0, returns <code>ZERO_SIZE_PTR</code> (a non-NULL magic constant that is safe to pass to <code>kfree()</code>).</li>
<li>If size > <code>KMALLOC_MAX_CACHE_SIZE</code> (typically 8 KiB on 4 KiB page systems): falls through to <code>kmalloc_large()</code> β <code>alloc_pages()</code> for order-based allocation.</li>
<li>Otherwise: <code>kmem_cache_alloc(cache, gfp)</code> is called on the selected cache (SLUB fast path: per-CPU freelist pop).</li>
<li><code>kfree(ptr)</code> β <code>__kfree()</code>: uses <code>virt_to_head_page()</code> to find the <code>struct page</code> β identifies the <code>kmem_cache</code> β calls <code>kmem_cache_free()</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Size rounding waste</strong>: An allocation of 33 bytes uses the 64-byte cache, wasting 31 bytes; for performance-critical code with many such objects, <code>kmem_cache_create()</code> with an exact size is preferable.</li>
<li><strong>GFP flag misuse</strong>: Using <code>GFP_KERNEL</code> (may sleep/reclaim) in atomic context (IRQ handler, spinlock held) triggers a <code>might_sleep()</code> warning or, worse, deadlock if the allocator tries to reclaim memory.</li>
<li><strong><code>kfree()</code> on a stack pointer or non-kmalloc memory</strong>: SLUB's <code>kfree()</code> uses <code>virt_to_head_page()</code> to verify the pointer is slab-managed; a pointer to a stack variable or static data causes a BUG.</li>
<li><strong>Speculative failure under pressure</strong>: Even <code>GFP_KERNEL</code> allocations can fail under extreme memory pressure if the OOM killer has already killed all candidates; callers must check for <code>NULL</code> and handle it gracefully.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_7" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.7</span>
<h3 class="item-title">Memory Pool (`mm/mempool.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>mempool_create(min_nr, alloc_fn, free_fn, pool_data)</code> calls <code>alloc_fn()</code> <code>min_nr</code> times and stores the objects in <code>pool->elements[]</code>.</li>
<li><code>mempool_alloc(pool, gfp)</code> first tries the underlying allocator directly: calls <code>pool->alloc(gfp | __GFP_NOMEMALLOC, pool->pool_data)</code>.</li>
<li>If the allocator succeeds, the reserved pool is untouched.</li>
<li>If the allocator fails and <code>gfp & __GFP_DIRECT_RECLAIM</code>: the caller may wait on <code>pool->wait</code> (a wait_queue) if the pool is empty.</li>
<li>If the pool's <code>elements[]</code> array is non-empty, an element is popped (under <code>pool->lock</code>) and returned.</li>
<li>If both the allocator and pool are empty and <code>GFP_NOIO</code>: returns NULL (fatal for some paths; must be sized conservatively).</li>
<li><code>mempool_free(element, pool)</code>:</li>
<li style="list-style-type:lower-alpha">If pool is below <code>min_nr</code>, the element is returned to <code>pool->elements[]</code> and a waiter in <code>pool->wait</code> is woken.</li>
<li style="list-style-type:lower-alpha">Otherwise, <code>pool->free()</code> is called to return the element to the underlying allocator.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Pool size insufficient for deadlock avoidance</strong>: 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.</li>
<li><strong><code>mempool_alloc</code> with <code>GFP_NOIO</code> returning NULL</strong>: 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.</li>
<li><strong>Pool element leak</strong>: If code acquires an element from a mempool and returns an error without calling <code>mempool_free()</code>, the pool shrinks below <code>min_nr</code>; the pool replenishes lazily when elements are freed but may be temporarily undersized.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_8" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.8</span>
<h3 class="item-title">CMA (Contiguous Memory Allocator) (`mm/cma.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>CMA reserves contiguous physical memory regions at boot time (via <code>cma=</code> kernel parameter or device tree <code>reserved-memory</code> 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>At boot: <code>cma_declare_contiguous()</code> marks a physical range as a CMA region; the range is managed by the buddy allocator as <code>MIGRATE_CMA</code> pages.</li>
<li><code>dma_alloc_contiguous()</code> β <code>cma_alloc(cma, count, align, no_warn)</code>.</li>
<li><code>alloc_contig_range()</code> tries to isolate the requested page range from the buddy allocator.</li>
<li><code>start_isolate_page_range()</code> changes the migration type of the target pages to <code>MIGRATE_ISOLATE</code>, preventing new allocations into them.</li>
<li><code>migrate_pages()</code> moves all currently-allocated movable pages out of the range to other memory zones.</li>
<li>If migration succeeds, the range is allocated contiguously and returned as a <code>struct page *</code>.</li>
<li><code>cma_release()</code> β <code>free_contig_range()</code> returns the pages to the buddy allocator as <code>MIGRATE_CMA</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Migration failure</strong>: If a page in the requested range cannot be migrated (pinned, locked, or of a non-movable type), <code>alloc_contig_range()</code> fails with <code>-EBUSY</code>; the caller receives NULL.</li>
<li><strong>CMA fragmentation over time</strong>: Long-running systems may pin non-movable pages inside the CMA region (via <code>get_user_pages()</code>), making contiguous allocation progressively harder.</li>
<li><strong>CMA size reservation vs. DMA size</strong>: If the CMA region is smaller than the device's DMA buffer requirement, the allocation always fails regardless of total free memory.</li>
<li><strong>Early CMA allocation before migration is ready</strong>: During early boot (before <code>mem_init()</code>), page migration is not available; CMA requests during this phase use a simple early allocator that permanently removes pages from the buddy pool.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_9" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.9</span>
<h3 class="item-title">Transparent Huge Pages (THP) (`mm/huge_memory.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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. <code>khugepaged</code> is a background kernel thread that scans for small-page regions eligible for promotion.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A process <code>mmap()</code>s a large anonymous region.</li>
<li>Initial page faults allocate 4 KiB pages normally.</li>
<li><code>khugepaged</code> wakes periodically, scans <code>mm_struct</code> page 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).</li>
<li><code>collapse_huge_page()</code> allocates a 2 MiB physically contiguous block (order-9 huge page from the buddy allocator).</li>
<li><code>copy_page()</code> copies all 512 small pages into the new huge page.</li>
<li>The PMD entry is replaced with a huge-page PMD pointing to the new 2 MiB block.</li>
<li>The 512 original small pages are released to the buddy allocator.</li>
<li>Future page faults in the region use the PMD-level huge page, skipping 512 PTE lookups.</li>
<li>On split (e.g., due to <code>mprotect()</code>, <code>mremap()</code>, or memory pressure): <code>split_huge_page()</code> rebuilds the 512 PTE entries and returns the huge page to the buddy allocator.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>THP allocation failure</strong>: The order-9 allocation may fail under memory pressure; <code>khugepaged</code> retries later, so the page table remains small until a contiguous block becomes available.</li>
<li><strong>THP split under swap pressure</strong>: 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).</li>
<li><strong>THP in <code>mlock()</code>'d regions</strong>: Locking a region prevents <code>khugepaged</code> from collapsing it; the interaction between <code>VM_LOCKED</code> and THP requires care in memory-pinning code.</li>
<li><strong>False sharing amplification</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_3_10" data-cat="3" style="--acc:#4ede9a">
<div class="card-header">
<span class="item-num">3.10</span>
<h3 class="item-title">Per-CPU Allocator (`mm/percpu.c`)</h3>
<span class="cat-badge" style="background:#4ede9a20;color:#4ede9a;border-color:#4ede9a40">Cat 3</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The per-CPU allocator manages the per-CPU memory areas created at boot time (and dynamically via <code>alloc_percpu()</code>). 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 <code>__percpu</code>-annotated pointers are offsets relative to each CPU's base address.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>At boot: <code>pcpu_setup_first_chunk()</code> carves out per-CPU memory from the kernel image and sets <code>__per_cpu_offset[cpu]</code> for each CPU.</li>
<li><code>alloc_percpu(type)</code> β <code>__alloc_percpu(size, align)</code>.</li>
<li><code>pcpu_alloc()</code> acquires <code>pcpu_lock</code> and searches for a free slot in existing chunks of appropriate group (small/large).</li>
<li>If no space in existing chunks: <code>pcpu_create_chunk()</code> allocates new pages from the buddy allocator and maps them into each CPU's per-CPU address space.</li>
<li>The allocated offset is stored; the returned <code>__percpu *</code> pointer is an offset, not a real address.</li>
<li><code>per_cpu_ptr(ptr, cpu)</code> β <code>(void *)((unsigned long)(ptr) + __per_cpu_offset[cpu])</code> β produces the real per-CPU address for a specific CPU.</li>
<li><code>free_percpu(ptr)</code> returns the offset to the chunk's free list; fully free chunks are returned to the buddy allocator.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Early boot allocation before <code>__per_cpu_offset</code> is set</strong>: Accessing per-CPU data before <code>setup_per_cpu_areas()</code> completes reads garbage; architecture-specific boot code must be careful about ordering.</li>
<li><strong>Module per-CPU allocation failure</strong>: If <code>alloc_percpu()</code> fails during module load, the module's <code>init()</code> must free all previously allocated per-CPU areas before returning the error; partial cleanup causes permanent per-CPU space leakage.</li>
<li><strong>CPU offline drain</strong>: When a CPU goes offline, any data accumulated in its per-CPU allocator slab caches (SLUB <code>cpu_slab</code>) must be drained to the per-node list; the <code>CPU_DEAD</code> notifier handles this but only if properly registered.</li>
<li><strong>Cache line alignment</strong>: The per-CPU allocator aligns allocations to <code>SMP_CACHE_BYTES</code> (typically 64 B); structures smaller than a cache line waste space but prevent false sharing.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_1" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.1</span>
<h3 class="item-title">CFS (Completely Fair Scheduler) (`kernel/sched/fair.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 <code>vruntime</code> (virtual runtime: actual CPU time scaled by task weight) to select the next task.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Task enqueueing: <code>enqueue_task_fair()</code> adds the <code>sched_entity</code> to the per-CPU RB tree and updates <code>cfs_rq->nr_running</code>.</li>
<li>Task selection: <code>pick_next_task_fair()</code> returns the <code>sched_entity</code> with the minimum <code>vruntime</code> (leftmost node of the RB tree).</li>
<li>The selected task's <code>vruntime</code> is advanced by <code>calc_delta_fair(delta, se)</code> during each scheduler tick, proportional to actual runtime divided by its weight.</li>
<li><code>update_curr()</code> is called on each tick (via <code>task_tick_fair()</code>) to update <code>vruntime</code> and check if the current task should be preempted.</li>
<li>Preemption check: if the minimum <code>vruntime</code> on the RB tree is more than <code>sysctl_sched_latency / nr_running</code> less than the current task's <code>vruntime</code>, <code>resched_curr()</code> sets <code>TIF_NEED_RESCHED</code>.</li>
<li>On the next kernel exit or <code>schedule()</code> call, <code>pick_next_task_fair()</code> dequeues the minimum-vruntime task and context-switches to it.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>vruntime overflow</strong>: After long uptime, 64-bit <code>vruntime</code> could 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.</li>
<li><strong>Newly woken task vruntime placement</strong>: A sleeping task's <code>vruntime</code> is not advanced; on wake, it is set to <code>max(task->vruntime, cfs_rq->min_vruntime - sysctl_sched_wakeup_granularity)</code> to prevent "vruntime regression" (a just-woken task unfairly dominating the CPU).</li>
<li><strong>Group scheduling (cgroups) complexity</strong>: With CPU cgroups, CFS uses a hierarchical scheduler entity (<code>sched_entity</code> trees); incorrect group weight configuration can starve entire cgroups.</li>
<li><strong>Latency target vs. throughput</strong>: With many tasks, <code>sysctl_sched_latency</code> is spread over <code>nr_running</code> tasks; each task's timeslice shrinks below <code>sysctl_sched_min_granularity</code>, causing excessive context-switch overhead.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_2" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.2</span>
<h3 class="item-title">RT Scheduler (`kernel/sched/rt.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The real-time scheduler implements <code>SCHED_FIFO</code> and <code>SCHED_RR</code> policies. All real-time tasks have a static priority (1β99 for <code>SCHED_FIFO</code>/<code>SCHED_RR</code>) and preempt any CFS or idle task. <code>SCHED_FIFO</code> runs until blocked or preempted by a higher-priority RT task. <code>SCHED_RR</code> adds a timeslice (100 ms default): when exhausted, the task is moved to the back of the run queue at the same priority.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>enqueue_task_rt()</code> adds the task to the per-priority FIFO queue in <code>rt_rq->active.queue[priority]</code>.</li>
<li><code>pick_next_task_rt()</code> calls <code>pick_next_rt_entity()</code> β finds the highest non-empty priority queue using the <code>rt_rq->active.bitmap</code> (a bitmask of populated priority levels).</li>
<li>The highest-priority task is returned; if multiple tasks share the same priority, the head of the FIFO queue is selected.</li>
<li><code>task_tick_rt()</code> runs on each tick; for <code>SCHED_RR</code>, decrements the timeslice counter; on expiry, calls <code>requeue_task_rt()</code> to move the task to the tail of its priority queue.</li>
<li>For <code>SCHED_FIFO</code>, the task runs until it blocks, yields, or is preempted by a higher-priority task.</li>
<li><code>dequeue_task_rt()</code> removes the task from the bitmap/queue on block or completion.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>RT bandwidth throttling</strong>: Without <code>CONFIG_RT_GROUP_SCHED</code>, a single SCHED_FIFO task at priority 99 can starve all other tasks (including the kernel's watchdog thread). <code>sysctl_sched_rt_runtime</code> / <code>sysctl_sched_rt_period</code> enforce a bandwidth cap (default: 95% CPU for RT tasks).</li>
<li><strong>Priority inversion in RT</strong>: An RT task blocked waiting for a resource held by a CFS task may be delayed indefinitely without priority inheritance; <code>SCHED_FIFO</code> with <code>pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT)</code> mitigates this.</li>
<li><strong>Missed SCHED_RR timeslice reset</strong>: On <code>fork()</code>, 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.</li>
<li><strong>Migration to wrong CPU</strong>: Under <code>RT_GROUP_SCHED</code>, pull/push migrations of RT tasks must respect CPU affinity masks; a migration that violates <code>cpus_allowed</code> causes a kernel BUG in <code>set_task_cpu()</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_3" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.3</span>
<h3 class="item-title">Deadline Scheduler (`kernel/sched/deadline.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The deadline scheduler implements <code>SCHED_DEADLINE</code> policy based on the Earliest Deadline First (EDF) algorithm with Constant Bandwidth Server (CBS) for admission control. Each task specifies three parameters: <code>runtime</code> (worst-case execution time per period), <code>deadline</code> (relative deadline), and <code>period</code>. The scheduler guarantees that a task meeting its parameters will never miss its deadline, as long as the total utilization (Ξ£ runtime/period) β€ 1.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Task admission: <code>dl_overflow()</code> checks that adding the new task's utilization (runtime/period) would not exceed the CPU's capacity; rejects with <code>EBUSY</code> if it would.</li>
<li><code>enqueue_task_dl()</code> inserts the task's <code>sched_dl_entity</code> into the per-CPU RB tree keyed by absolute deadline.</li>
<li><code>pick_next_task_dl()</code> returns the leftmost node (earliest absolute deadline).</li>
<li>During execution: <code>update_dl_task_contention()</code> depletes the CBS bandwidth; <code>task_tick_dl()</code> decrements remaining runtime.</li>
<li>When runtime is exhausted before the deadline, the task is throttled: <code>start_dl_timer()</code> sets a replenishment timer for the next period start.</li>
<li>At period start, the runtime is replenished and the task re-enters the RB tree with a new deadline.</li>
<li>When the absolute deadline passes (task completes): <code>dequeue_task_dl()</code> removes the entity; the next period's parameters are set.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Admission control race</strong>: Two simultaneous <code>sched_setattr()</code> calls for two tasks may each pass the capacity check individually but together exceed 100%; the kernel serializes via <code>dl_b->lock</code> per root domain but a race across NUMA nodes can still occur.</li>
<li><strong>Missed deadline (overrun)</strong>: CBS guarantees no deadline miss for tasks meeting their parameters; if a task's actual execution time exceeds <code>runtime</code>, it is throttled (not preempted), which causes a soft deadline miss for that period.</li>
<li><strong><code>SCHED_DEADLINE</code> task on a cgroup-constrained CPU</strong>: 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.</li>
<li><strong>Priority boosting interaction</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_4" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.4</span>
<h3 class="item-title">Idle Scheduler (`kernel/sched/idle.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The idle scheduler runs the special <code>idle</code> task (PID 0, one per CPU) when no other runnable task exists. The idle task calls the architecture's idle loop (<code>cpu_idle_loop()</code>), which calls <code>cpuidle_idle_call()</code> 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>pick_next_task_idle()</code> is reached only when all other scheduler classes (<code>stop</code>, <code>dl</code>, <code>rt</code>, <code>fair</code>) have no runnable tasks.</li>
<li>The idle task is returned; it cannot be dequeued.</li>
<li><code>cpu_idle_loop()</code> starts: sets <code>current->state = TASK_IDLE</code>.</li>
<li><code>tick_nohz_idle_enter()</code> stops the scheduling tick if <code>NO_HZ_IDLE</code> is configured (tickless idle).</li>
<li><code>cpuidle_idle_call()</code> queries the cpuidle governor (menu or ladder) for the best C-state.</li>
<li>The cpuidle driver executes <code>state->enter()</code> (e.g., <code>mwait_idle_with_hints()</code> on x86 β <code>MWAIT</code> instruction).</li>
<li>When a hardware interrupt or IPI arrives, the CPU exits the C-state and re-runs the scheduler.</li>
<li><code>tick_nohz_idle_exit()</code> restores the tick; <code>schedule_idle()</code> checks for new runnable tasks.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>C-state entry latency vs. wakeup latency</strong>: Deep C-states (C6, C7) have high exit latency (100s of Β΅s); a real-time task requiring sub-100 Β΅s response must set a <code>PM_QOS_CPU_DMA_LATENCY</code> constraint to prevent deep idle entry.</li>
<li><strong>Idle task stack overflow</strong>: 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 <code>CONFIG_VMAP_STACK</code> is set).</li>
<li><strong>Tick granularity in nohz_full</strong>: On CPUs in <code>nohz_full</code> mode, re-entering the tick after long idle periods requires an IPI from another CPU, adding latency.</li>
<li><strong>Intel C-state hardware bugs</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_5" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.5</span>
<h3 class="item-title">Stop Scheduler (`kernel/sched/stop_task.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The stop scheduler is the highest-priority scheduler class, running <code>stop_machine</code> tasks (threads named <code>migration/N</code>). 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 <code>stop_machine()</code> callbacks. Only one stop task exists per CPU.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>stop_one_cpu(cpu, fn, arg)</code> or <code>stop_machine(fn, arg, cpumask)</code> is called.</li>
<li><code>cpu_stop_work</code> entries are prepared with the callback <code>fn</code> and queued on the target CPU's <code>stopper->works</code> list.</li>
<li>The stop thread (<code>migration/N</code> for CPU N) is woken via <code>wake_up_process()</code>.</li>
<li><code>pick_next_task_stop()</code> runs before all other scheduler classes; it preempts any running task immediately.</li>
<li>The stop task runs <code>fn(arg)</code> in kernel thread context.</li>
<li>For <code>stop_machine()</code>: all CPUs are synchronously stopped (via <code>multi_cpu_stop()</code> using an atomic state machine); only the calling CPU executes <code>fn()</code>.</li>
<li>After <code>fn()</code> returns, CPUs are released in reverse order; the stop task sleeps by setting its state to <code>TASK_DEAD</code> (stop task goes back to waiting).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Nested <code>stop_machine()</code> calls</strong>: Calling <code>stop_machine()</code> from within a <code>stop_machine()</code> callback deadlocks (all CPUs are already stopped; the inner call cannot stop them again).</li>
<li><strong>Stop task migration race</strong>: 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.</li>
<li><strong>Long <code>stop_machine()</code> callbacks</strong>: Any code run inside <code>stop_machine()</code> runs with IRQs disabled on all CPUs; long-running callbacks cause visible system freezes and watchdog timeouts.</li>
<li><strong><code>stop_one_cpu_nowait()</code> completion ordering</strong>: The async variant (<code>_nowait</code>) returns before <code>fn()</code> completes; callers that assume immediate completion introduce subtle ordering bugs.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_6" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.6</span>
<h3 class="item-title">Core Scheduler Loop (`schedule()` / `kernel/sched/core.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>schedule()</code> is the central context-switch function that runs the scheduler, selects the next task via <code>pick_next_task()</code>, and performs the actual CPU context switch. It is the heart of the scheduler; every voluntary or involuntary context switch passes through it.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>schedule()</code> β <code>__schedule(sm)</code> where <code>sm</code> is the preempt mode (voluntary, preemption, idle).</li>
<li><code>rq_lock(rq)</code> acquires the run queue lock for the current CPU.</li>
<li><code>deactivate_task()</code> is called if the current task is not runnable (<code>TASK_INTERRUPTIBLE</code>, <code>TASK_UNINTERRUPTIBLE</code>).</li>
<li><code>pick_next_task(rq, prev)</code> calls the scheduler class chain: stop β deadline β rt β fair β idle; returns the highest-priority runnable task.</li>
<li><code>clear_tsk_need_resched(prev)</code> clears the <code>TIF_NEED_RESCHED</code> flag.</li>
<li><code>prepare_task_switch(rq, prev, next)</code> runs pre-switch callbacks (e.g., <code>perf_event_task_sched_out()</code>).</li>
<li><code>context_switch(rq, prev, next)</code> performs the actual switch:</li>
<li style="list-style-type:lower-alpha"><code>switch_mm_irqs_off()</code>: switches page tables (CR3 on x86).</li>
<li style="list-style-type:lower-alpha"><code>switch_to(prev, next, prev)</code>: saves/restores CPU registers (rsp, rbp) and FPU state lazily; jumps to <code>next</code>.</li>
<li>After <code>switch_to()</code> returns, execution is on the <code>next</code> task's stack.</li>
<li><code>finish_task_switch()</code> releases the previous task's run queue lock and handles post-switch work.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong><code>schedule()</code> in IRQ context</strong>: Calling <code>schedule()</code> with <code>in_interrupt()</code> returning true causes a BUG; IRQ handlers must not sleep.</li>
<li><strong><code>TIF_NEED_RESCHED</code> missed</strong>: If <code>clear_tsk_need_resched()</code> is called but the new task immediately re-sets the flag (e.g., a high-frequency timer fires during <code>finish_task_switch()</code>), the CPU loops back into <code>__schedule()</code> on the next kernel exit.</li>
<li><strong>FPU state corruption</strong>: 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, <code>migrate_disable()</code> / <code>fpregs_lock()</code> must be used.</li>
<li><strong>Runqueue lock ordering violations</strong>: Locking two run queues simultaneously (required for cross-CPU task migration) must always be done in lowest-address-first order to prevent deadlock.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_7" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.7</span>
<h3 class="item-title">Load Balancer (`kernel/sched/fair.c` β `load_balance()`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Triggered by: <code>scheduler_tick()</code> detecting CPU imbalance, or <code>newidle_balance()</code> when a CPU becomes idle.</li>
<li><code>load_balance(this_cpu, this_rq, sd, idle, continue_balancing)</code> is called for the current scheduling domain.</li>
<li><code>find_busiest_group()</code> 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.</li>
<li><code>find_busiest_queue()</code> within the busiest group finds the CPU with the highest <code>cfs_rq->avg.load_avg</code>.</li>
<li><code>detach_tasks()</code> selects and removes up to <code>imbalance</code> worth of load from the busiest queue, applying migration constraints (CPU affinity, cache hot threshold, <code>numa_preferred_nid</code>).</li>
<li><code>attach_tasks()</code> migrates the detached tasks to <code>this_rq</code>.</li>
<li>If migration is blocked (all tasks on busiest CPU are CPU-affinity-pinned), <code>load_balance()</code> returns a "failed" indicator and the domain is marked for re-check.</li>
<li>The process repeats for each outer scheduling domain level (Core β Package β NUMA).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Affinity pinning creates permanent imbalance</strong>: If all tasks on a CPU are pinned to that CPU, the load balancer cannot fix the imbalance and repeatedly fails; <code>nr_balance_failed</code> increments until a <code>active_load_balance_cpu_stop()</code> migration is attempted (which also fails, causing a stall).</li>
<li><strong>Scheduler domain misconfiguration (topology)</strong>: An incorrect <code>sched_domain_topology_level</code> array (e.g., after CPU hotplug that doesn't rebuild topology) causes domains to cover wrong CPU sets, leading to migrations that degrade cache performance.</li>
<li><strong>NUMA Imbalance vs. load imbalance</strong>: 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.</li>
<li><strong>Nohz imbalance</strong>: CPUs in <code>nohz_full</code> mode don't run the scheduler tick; their load is not updated until they exit idle; <code>nohz_kick_needed()</code> / <code>nohz_balancer_kick()</code> asynchronously trigger a rebalance via IPI.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_8" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.8</span>
<h3 class="item-title">NUMA Balancer (`kernel/sched/numa_balancing.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The NUMA balancer (<code>CONFIG_NUMA_BALANCING</code>) 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>task_tick_fair()</code> calls <code>task_tick_numa(rq, curr, queued)</code> on each scheduler tick.</li>
<li><code>numa_work_next_cpu()</code> queues a <code>numa_work</code> on the task via <code>task_work_add()</code>.</li>
<li>When the task returns to userspace, <code>task_numa_work()</code> scans a portion of the task's page tables via <code>change_prot_numa()</code>, converting PTEs to <code>_PAGE_NUMA</code> (access-cleared).</li>
<li>The next access to such a page triggers a NUMA fault (page fault with <code>pte_numa()</code> set).</li>
<li><code>do_numa_page()</code> β <code>mpol_misplaced()</code> determines if the page should be migrated.</li>
<li><code>migrate_misplaced_page()</code> moves the page to the task's preferred NUMA node.</li>
<li>NUMA hint statistics (<code>task->numa_faults[]</code>) are updated; <code>numa_migrate_preferred()</code> checks if the task should be migrated to the node holding most of its pages.</li>
<li><code>task_numa_migrate()</code> calls <code>migrate_task_to()</code> to move the task itself.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>NUMA thrashing</strong>: Two tasks repeatedly swap NUMA nodes to follow each other's shared pages, causing continuous migration overhead; <code>sched_numa_balancing</code> can be disabled per-cgroup.</li>
<li><strong>False-negative scan</strong>: 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.</li>
<li><strong>Migration stall under memcg limits</strong>: 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.</li>
<li><strong>Interaction with huge pages</strong>: NUMA fault handling on a THP requires splitting the huge page first; this defeats THP's purpose and can cause performance regression.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_9" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.9</span>
<h3 class="item-title">cgroup CPU Controller (`kernel/cgroup/cpu.c`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The cgroup CPU controller (v1: <code>cpu</code> controller; v2: unified hierarchy) limits and prioritizes CPU access for groups of tasks. In v2, it provides <code>cpu.weight</code> (CFS nice-equivalent weight), <code>cpu.max</code> (bandwidth limiting: maximum runtime per period), and <code>cpu.uclamp.min</code>/<code>max</code> (frequency scaling hints). It operates by embedding cgroup-level <code>sched_entity</code> objects into the CFS hierarchy.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A cgroup is created: <code>mkdir /sys/fs/cgroup/mygroup</code>.</li>
<li>Tasks are added: <code>echo PID > /sys/fs/cgroup/mygroup/cgroup.procs</code>.</li>
<li>CFS creates a per-CPU <code>task_group</code> with a <code>cfs_rq</code> (group-level run queue) and a <code>sched_entity</code> (group entity on the parent run queue).</li>
<li>When a task in the group is scheduled: CFS selects the group entity from the parent <code>cfs_rq</code> (based on group vruntime), then selects a task entity from the group's <code>cfs_rq</code>.</li>
<li>Bandwidth enforcement (<code>cpu.max</code>): <code>cfs_bandwidth_work</code> runs periodically; when the group has used its <code>quota</code> within the <code>period</code>, <code>throttle_cfs_rq()</code> is called β all tasks in the group are dequeued.</li>
<li>At the next period start, <code>unthrottle_cfs_rq()</code> re-enqueues all throttled tasks.</li>
<li><code>cpu.weight</code> adjusts the group entity's <code>se.load.weight</code>, proportionally scaling vruntime advance rate.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Bandwidth throttling cliff</strong>: A cgroup that hits its <code>cpu.max</code> quota 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.</li>
<li><strong>Hierarchical weight interaction</strong>: Nested cgroups accumulate weights multiplicatively; a deeply nested cgroup may have a de facto weight of near zero regardless of its own <code>cpu.weight</code> setting.</li>
<li><strong>RT tasks bypass cgroup limits</strong>: <code>SCHED_FIFO</code>/<code>SCHED_RR</code> tasks are not subject to <code>cpu.max</code>; they can exceed the cgroup's intended CPU budget.</li>
<li><strong>v1 / v2 incompatibility</strong>: The <code>cpu</code> controller cannot be simultaneously mounted in v1 and v2 hierarchies; a system using systemd's cgroup v2 must not also mount the legacy v1 <code>cpu</code> hierarchy.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_4_10" data-cat="4" style="--acc:#de9a4a">
<div class="card-header">
<span class="item-num">4.10</span>
<h3 class="item-title">Context Switch / `switch_to()` Mechanism (`arch/x86/include/asm/switch_to.h`)</h3>
<span class="cat-badge" style="background:#de9a4a20;color:#de9a4a;border-color:#de9a4a40">Cat 4</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>context_switch()</code> and its architecture-specific <code>switch_to(prev, next, last)</code> macro implement the CPU register save/restore that transfers execution from one task to another. It saves the current task's stack pointer (<code>rsp</code>), instruction pointer (implicitly via the return address), and optionally FPU state, then restores the next task's saved state.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>context_switch(rq, prev, next)</code> in <code>kernel/sched/core.c</code> is called with <code>rq->lock</code> held.</li>
<li><code>prepare_task_switch(rq, prev, next)</code> runs perf/cgroup/trace hooks.</li>
<li>If <code>next</code> has a different address space: <code>switch_mm_irqs_off(prev->active_mm, next->mm, next)</code> β updates <code>CR3</code> (x86) with <code>next->mm->pgd</code> physical address, flushing TLB entries (or using PCID/ASID to avoid a full flush).</li>
<li><code>switch_to(prev, next, prev)</code> (assembly macro):</li>
<li style="list-style-type:lower-alpha">Pushes callee-saved registers (<code>rbp</code>, <code>rbx</code>, <code>r12</code>β<code>r15</code>) onto <code>prev</code>'s kernel stack.</li>
<li style="list-style-type:lower-alpha">Saves <code>rsp</code> to <code>prev->thread.sp</code>.</li>
<li style="list-style-type:lower-alpha">Loads <code>rsp</code> from <code>next->thread.sp</code> (now on <code>next</code>'s kernel stack).</li>
<li style="list-style-type:lower-alpha">Calls <code>__switch_to_asm()</code> β <code>__switch_to()</code> which updates the <code>TSS.sp0</code> field (kernel stack pointer for syscall entry), loads <code>next</code>'s <code>fsbase</code>/<code>gsbase</code>.</li>
<li style="list-style-type:lower-alpha"><code>ret</code> on <code>next</code>'s stack returns to wherever <code>next</code> last called <code>schedule()</code> (or to <code>ret_from_fork</code> for a new task).</li>
<li>After <code>switch_to()</code> returns (now running as <code>next</code>): <code>finish_task_switch(prev)</code> releases <code>prev</code>'s lock state and handles task cleanup.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>FPU state corruption without lazy save</strong>: 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), <code>fpregs_assert_state_consistent()</code> will BUG.</li>
<li><strong>Stack corruption during switch</strong>: A stack overflow in <code>prev</code> that overwrites the saved <code>rsp</code> causes the CPU to jump to a garbage address when <code>switch_to()</code> loads the corrupted stack pointer. <code>CONFIG_VMAP_STACK</code> places a guard page under each stack to catch this.</li>
<li><strong>CR3 update and speculative execution (Spectre/Meltdown)</strong>: On CPUs without hardware PCID support, every <code>switch_mm</code> flushes the entire TLB; this is expensive for applications with large working sets; <code>CONFIG_PAGE_TABLE_ISOLATION</code> (PTI/KPTI) adds further overhead for user/kernel page table separation.</li>
<li><strong><code>last</code> pointer aliasing</strong>: <code>switch_to(prev, next, prev)</code> returns with <code>prev</code> pointing to the task that was running before <code>next</code> woke, which may differ from the task that called <code>switch_to()</code> if another task ran between them; callers must use the returned <code>prev</code> (via the <code>last</code> output parameter) for cleanup, not the caller's local variable.</li>
</ul>
<p># Linux Kernel Component Taxonomy β Part 2 (Categories 5β8)</p></div>
</section>
</div>
</div>
<div class="card" id="item_5_1" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.1</span>
<h3 class="item-title">blk-mq (Multi-Queue Block Layer) (`block/blk-mq.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A filesystem or direct I/O caller submits a <code>bio</code> to <code>submit_bio()</code>.</li>
<li><code>blk_mq_submit_bio()</code> splits the bio if it exceeds queue limits, then calls <code>blk_mq_get_request()</code> to allocate a <code>struct request</code> from the per-CPU request pool.</li>
<li>The request is inserted into the per-CPU software staging queue (<code>ctx->rq_list</code>).</li>
<li><code>blk_mq_run_hw_queue()</code> is called: it drains the software queue into the hardware dispatch queue (<code>hctx->dispatch</code>).</li>
<li>If an I/O scheduler is attached, <code>e->type->ops.insert_requests()</code> is called (e.g., BFQ sorts by deadline/priority).</li>
<li><code>blk_mq_dispatch_rq_list()</code> calls the driver's <code>queue_rq()</code> callback with a batch of requests.</li>
<li>The driver submits requests to hardware (NVMe SQ doorbell, SCSI command queue, etc.).</li>
<li>Hardware completes I/O, raises an interrupt; <code>blk_mq_complete_request()</code> is called, which calls the bio's <code>bi_end_io</code> callback, waking the submitting task.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Request tag exhaustion</strong>: Each hardware queue has a fixed tag depth; if all tags are in-flight, new requests block in <code>blk_mq_get_tag()</code> on the <code>hctx->tags->bitmap_tags</code> wait queue.</li>
<li><strong>Queue quiesce deadlock</strong>: <code>blk_mq_quiesce_queue()</code> 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.</li>
<li><strong>CPU hotplug and per-CPU queue migration</strong>: When a CPU goes offline, its software queue must be drained to another CPU's queue; <code>blk_mq_hctx_notify_dead()</code> handles this but races with concurrent submissions.</li>
<li><strong>Plug/unplug coalescing failure</strong>: <code>blk_start_plug()</code> / <code>blk_finish_plug()</code> batch requests before dispatch; a process that starts a plug and exits without calling <code>blk_finish_plug()</code> leaves requests stranded until the plug is flushed at <code>schedule()</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_2" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.2</span>
<h3 class="item-title">BFQ (Budget Fair Queueing) I/O Scheduler (`block/bfq-iosched.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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 (<code>bfq_queue</code>) organized in a hierarchical weight-fair tree with time-slice based service.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A request arrives: <code>bfq_insert_request()</code> places it in the submitting process's <code>bfq_queue</code>, sorted by LBA (for seek optimization).</li>
<li>The <code>bfq_queue</code> is inserted into the BFQ service tree (a Red-Black tree ordered by virtual finish time, computed from budget and weight).</li>
<li><code>bfq_select_queue()</code> selects the queue with the minimum virtual finish time that has pending requests and whose budget has not expired.</li>
<li>The selected queue is "in service"; its requests are dispatched to the blk-mq hardware queue via <code>bfq_dispatch_request()</code>.</li>
<li>After <code>budget</code> sectors 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.</li>
<li>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.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Latency cliff for interactive tasks</strong>: 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.</li>
<li><strong>Weight starvation in hierarchical scheduling</strong>: A cgroup with low <code>blkio.bfq.weight</code> may 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.</li>
<li><strong>bfq_queue split on shared access</strong>: When multiple processes share the same <code>bfq_queue</code> (cooperative scheduling), a synchronization point split is needed; missing a split leaves one process's I/O blocking another's.</li>
<li><strong>Think-time estimation error</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_3" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.3</span>
<h3 class="item-title">mq-deadline I/O Scheduler (`block/mq-deadline.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A request arrives: <code>dd_insert_request()</code> inserts it into both the LBA RB-tree and the FIFO queue for its direction (read or write).</li>
<li><code>dd_dispatch_request()</code> is called by blk-mq when the hardware queue needs requests.</li>
<li>Deadline check: the front of the read FIFO is examined; if its deadline (<code>jiffies + read_expire</code>, default 500 ms) has passed, it is dispatched immediately (deadline enforcement).</li>
<li>Write starvation check: if writes have been starved for <code>writes_starved</code> (default 2) read batches, force a write dispatch.</li>
<li>Otherwise, <code>dd_dispatch_prio_aged_requests()</code> dispatches from the LBA RB-tree to maximize sequential access patterns (elevator-style seek optimization).</li>
<li>After <code>fifo_batch</code> (default 16) consecutive requests from one direction, the scheduler switches to the other direction.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Read/write inversion on SSDs</strong>: 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 <code>none</code> scheduler is often better for NVMe.</li>
<li><strong>Write starvation under heavy read load</strong>: If <code>writes_starved</code> is set too high, write requests can be delayed far beyond their deadline; dirty-page writeback stalls and VFS write syscalls block.</li>
<li><strong>FIFO queue ordering on multi-queue devices</strong>: 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.</li>
<li><strong>Deadline expiry on power-loss-safe SSDs</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_4" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.4</span>
<h3 class="item-title">Kyber I/O Scheduler (`block/kyber-iosched.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Requests are classified into domains: <code>KYBER_READ</code> (sync reads) or <code>KYBER_WRITE</code> (writes/async).</li>
<li><code>kyber_bio_merge()</code> attempts to merge incoming bios with pending requests.</li>
<li><code>kyber_dispatch_request()</code> acquires a token from the per-domain <code>sbitmap_queue</code> (a semaphore-like token bucket per hardware queue context).</li>
<li>If tokens are available for the high-priority domain, its requests are dispatched first.</li>
<li>The latency sampler (<code>kyber_latency_timer_fn()</code>) runs periodically: measures recent per-domain completion latencies against <code>read_lat_nsec</code> and <code>write_lat_nsec</code> targets.</li>
<li>If a domain's latency exceeds its target, <code>kyber_adjust_rq_dispatches()</code> increases that domain's token budget; if latency is well below target, tokens are reduced.</li>
<li>This feedback loop maintains target latencies dynamically without explicit request sorting.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Token starvation feedback loop</strong>: 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.</li>
<li><strong>Domain mis-classification</strong>: Writes issued as <code>REQ_SYNC</code> (e.g., <code>fsync</code> metadata writes) are classified as synchronous but share a token bucket with background writes, defeating prioritization.</li>
<li><strong>Low queue depth devices</strong>: On rotational or emulated NVMe devices with small queue depths (QD=1), Kyber's token system does not improve over <code>none</code>; the hardware serializes everything regardless.</li>
<li><strong>Multi-actuator drive unsupported</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_5" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.5</span>
<h3 class="item-title">None / NOOP I/O Scheduler (`block/noop-iosched.c` / `block/mq-deadline.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The <code>none</code> 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 <code>noop</code> in the single-queue era. Optimal for devices with their own sophisticated internal schedulers (NVMe controllers, SSDs with FTL).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>bio</code> β <code>blk_mq_submit_bio()</code> β request allocation.</li>
<li><code>noop_insert_request()</code> appends the request to the per-hardware-queue dispatch list (<code>hctx->dispatch</code>).</li>
<li><code>noop_dispatch_request()</code> dequeues from the front of the list (pure FIFO).</li>
<li>The request is passed to the driver's <code>queue_rq()</code>.</li>
<li>No latency tracking, no reordering, no merging decisions beyond bio merging at the blk-mq layer.</li>
<li>Completion: <code>blk_mq_complete_request()</code> β <code>bio->bi_end_io()</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Request ordering on rotational media</strong>: Using <code>none</code> on 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.</li>
<li><strong>Write ordering for fsync correctness</strong>: The <code>none</code> scheduler does not enforce write ordering beyond what the driver provides; on devices without FUA (Force Unit Access) support, <code>fsync</code> may complete before data is persistent.</li>
<li><strong>Starvation of low-priority requests</strong>: Without any fairness mechanism, a high-throughput process issuing many requests can delay latency-sensitive requests indefinitely; the <code>none</code> scheduler has no mitigation.</li>
<li><strong>Hot-swap scheduler (online change)</strong>: The scheduler can be changed at runtime via <code>/sys/block/sdX/queue/scheduler</code>; changing from BFQ to <code>none</code> on a busy disk flushes in-flight BFQ queues immediately, which can cause a brief I/O pause.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_6" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.6</span>
<h3 class="item-title">`bio` Layer (`block/bio.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>A <code>bio</code> (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 <code>bio_vec</code> 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>bio_alloc(gfp, nr_vecs)</code> allocates a bio with space for <code>nr_vecs</code> page vectors from the bio slab or mempool.</li>
<li><code>bio_add_page(bio, page, len, offset)</code> adds a page vector entry; if the new entry is physically contiguous with the last, they are merged into one <code>bio_vec</code>.</li>
<li><code>submit_bio(bio)</code> enters the block layer: <code>blk_mq_submit_bio()</code> checks queue limits (max sectors, max segments).</li>
<li>If the bio exceeds limits: <code>bio_split()</code> creates two bios; the second is resubmitted recursively.</li>
<li>Bio merging: <code>blk_attempt_plug_merge()</code> tries to merge the new bio with an existing request on the plug list (front/back merge by sector adjacency).</li>
<li>After merging decisions, the bio is converted to a <code>request</code> and enters the I/O scheduler.</li>
<li>On completion: the driver calls <code>bio_endio(bio, error)</code> β <code>bio->bi_end_io(bio)</code>.</li>
<li>For split bios: <code>bio_chain()</code> links parent/child; the parent's <code>bi_end_io</code> fires only after all children complete.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>bio_vec segment limit overflow</strong>: A bio is bounded by <code>queue_max_segments()</code>; exceeding it requires splitting. Drivers that don't check the bio segment count before DMA mapping will produce DMA errors or memory corruption.</li>
<li><strong>High-memory page mapping</strong>: On 32-bit kernels, <code>bio_vec</code> pages in <code>ZONE_HIGHMEM</code> require <code>kmap_atomic()</code> to access; failing to unmap causes permanent kmap slot exhaustion.</li>
<li><strong>bio cloning for mirroring (DM/MD)</strong>: <code>bio_clone_fast()</code> 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.</li>
<li><strong>Partial completion handling</strong>: A device that completes only part of a bio (e.g., a device with a sector boundary error) calls <code>bio_advance()</code> to update the remaining range; callers that don't handle partial completions may submit the already-completed range again.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_7" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.7</span>
<h3 class="item-title">Request Queue (`block/blk-core.c`, `include/linux/blkdev.h`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The <code>request_queue</code> (<code>struct request_queue</code>) is the central data structure of the block layer for a given block device. It holds the blk-mq tag sets, hardware queue contexts (<code>blk_mq_hw_ctx</code>), 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 <code>request_queue</code>.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>At device registration: <code>blk_mq_init_queue()</code> allocates a <code>request_queue</code> and sets its limits from <code>blk_mq_tag_set</code> (driver-provided: queue depth, number of hardware queues, etc.).</li>
<li><code>blk_queue_max_hw_sectors()</code>, <code>blk_queue_physical_block_size()</code>, etc., configure the queue's operational limits.</li>
<li>An I/O scheduler is attached: <code>elevator_init_mq()</code> sets <code>q->elevator</code>.</li>
<li>I/O submission: <code>submit_bio()</code> β <code>blk_mq_submit_bio()</code> β routes through <code>q->mq_ops->queue_rq()</code>.</li>
<li>Queue freeze (<code>blk_freeze_queue()</code>): stops new I/O submission and waits for in-flight I/O to drain (used during driver suspend, error recovery, scheduler change).</li>
<li>Queue drain (<code>blk_drain_queue()</code>): waits for all requests to complete.</li>
<li>Queue teardown (<code>blk_cleanup_queue()</code>): on device removal, drains the queue, destroys tag sets, frees the <code>request_queue</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Queue limits violation</strong>: A filesystem that caches <code>queue_max_sectors()</code> 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.</li>
<li><strong>Request queue stall on tag exhaustion</strong>: When all blk-mq tags are in-flight, new requests block; if the device never completes a request (firmware hang), the queue stalls permanently. <code>blk_abort_request()</code> and device reset paths exist but are complex.</li>
<li><strong>Queue freeze deadlock</strong>: Calling <code>blk_freeze_queue()</code> 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.</li>
<li><strong>Rotational flag and elevator selection</strong>: Setting <code>q->rotational = 0</code> signals that the device is non-rotational; the kernel uses this to select a default scheduler (<code>none</code> for NVMe, <code>mq-deadline</code> for rotational). An incorrect flag causes the wrong default scheduler.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_8" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.8</span>
<h3 class="item-title">I/O Barriers / Write Ordering (`block/blk-flush.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A filesystem calls <code>blkdev_issue_flush()</code> or submits a bio with <code>REQ_PREFLUSH | REQ_FUA</code>.</li>
<li><code>blk_insert_flush()</code> checks the device's flush/FUA capabilities in <code>q->queue_flags</code> (<code>QUEUE_FLAG_WC</code> = write cache, <code>QUEUE_FLAG_FUA</code> = FUA support).</li>
<li>If neither is supported: the flush is a no-op (all writes are already cache-less).</li>
<li>If FUA is supported but <code>REQ_PREFLUSH</code> is set: a FLUSH command is dispatched first; the data write follows with the FUA bit set in the command.</li>
<li>The flush sequence state machine (<code>blk_flush_complete_seq()</code>) processes three phases: <code>REQ_FSEQ_PREFLUSH</code> (send flush), <code>REQ_FSEQ_DATA</code> (send data writes), <code>REQ_FSEQ_POSTFLUSH</code> (optional trailing flush).</li>
<li>Flush coalescing: multiple concurrent flush requests are coalesced into one hardware flush command to reduce overhead.</li>
<li>On flush completion: <code>blk_flush_complete_seq()</code> advances all coalesced requests to the data phase.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Flush coalescing window race</strong>: Two <code>fsync()</code> calls that arrive nanoseconds apart may land in different flush batches; the second process may wait for a full extra flush cycle, adding latency.</li>
<li><strong>Device reports FUA support but doesn't implement it</strong>: 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.</li>
<li><strong><code>REQ_PREFLUSH</code> overhead on tmpfs</strong>: Filesystems mounted on <code>tmpfs</code> or <code>ramfs</code> bypass the block layer entirely; <code>blkdev_issue_flush()</code> returns immediately without a syscall. Callers must check the mount type.</li>
<li><strong>Flush timeout on faulty device</strong>: 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 <code>fsync()</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_9" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.9</span>
<h3 class="item-title">Device Mapper (`drivers/md/dm.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>A DM device is created: <code>dm_create()</code> allocates a <code>mapped_device</code> and a <code>gendisk</code>; a mapping table is loaded via <code>ioctl(DM_TABLE_LOAD_CMD)</code>.</li>
<li>The table is a list of <code>dm_target</code> entries, each covering a sector range and naming a target type (e.g., <code>linear</code>, <code>crypt</code>, <code>thin</code>).</li>
<li>I/O submission: <code>dm_make_request()</code> intercepts bios destined for the DM device.</li>
<li><code>dm_map_bio()</code> looks up the target for the bio's start sector in the table's sector-range tree.</li>
<li>The target's <code>.map()</code> callback transforms the bio: remaps the sector number and device pointer (for <code>linear</code>), applies encryption (for <code>crypt</code>), or handles copy-on-write (for <code>snapshot</code>).</li>
<li>The transformed bio is re-submitted to the underlying device via <code>submit_bio()</code>.</li>
<li>On completion: the target's optional <code>.end_io()</code> callback runs; then <code>dm_io_dec_pending()</code> decrements the reference count and completes the original bio.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Table reload race</strong>: <code>dm_swap_table()</code> 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. A <code>dm_suspend()</code> / <code>dm_resume()</code> cycle is needed for a clean swap.</li>
<li><strong>dm-crypt bio splitting overhead</strong>: 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.</li>
<li><strong>dm-thin provisioning ENOSPC</strong>: When the thin pool runs out of space, new writes to thin volumes return <code>EIO</code> immediately; the filesystem must handle this gracefully (most ext4/XFS implementations do, but applications that assume ENOSPC is impossible may crash).</li>
<li><strong>dm-multipath path failure during I/O</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_5_10" data-cat="5" style="--acc:#de4a6e">
<div class="card-header">
<span class="item-num">5.10</span>
<h3 class="item-title">MD RAID Layer (`drivers/md/raid*.c`, `drivers/md/md.c`)</h3>
<span class="cat-badge" style="background:#de4a6e20;color:#de4a6e;border-color:#de4a6e40">Cat 5</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Array assembly: <code>md_run()</code> reads superblocks from each member device, validates the configuration, and starts the RAID personality (<code>raid5_run()</code>, <code>raid1_run()</code>, etc.).</li>
<li>I/O submission: <code>md_make_request()</code> intercepts bios; the RAID personality's <code>make_request()</code> (e.g., <code>raid5_make_request()</code>) determines the stripe number and position.</li>
<li>For RAID-5: a <code>stripe_head</code> is 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).</li>
<li>The stripe cache (hash table of <code>stripe_head</code> objects) coalesces multiple bios targeting the same stripe.</li>
<li>Completed stripe I/O: <code>raid5_end_read_request()</code> / <code>raid5_end_write_request()</code> update stripe state; when all required I/O is done, <code>handle_stripe()</code> advances the stripe state machine.</li>
<li>Device failure: <code>md_error()</code> marks the failing device; RAID-1/5/6 continues degraded; <code>md_check_recovery()</code> starts a resync to rebuild the missing data on a hot spare.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>RAID-5 write hole</strong>: 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 (<code>raid5_journal</code>) or by writing a "partial parity log" (PPL).</li>
<li><strong>Stripe cache deadlock</strong>: 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 <code>stripe_hash_locks</code> / <code>conf->max_nr_stripes</code> semaphore.</li>
<li><strong>Bitmap-assisted resync</strong>: 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.</li>
<li><strong>RAID-6 double-disk failure during resync</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_1" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.1</span>
<h3 class="item-title">Dentry Cache (dcache) (`fs/dcache.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The dentry cache is an in-memory cache of directory entry objects (<code>struct dentry</code>), each mapping a filename component to its inode. It implements the VFS name lookup fast path: <code>lookup_fast()</code> checks the dcache hash table before hitting the filesystem. The cache is bounded by memory and uses LRU eviction under pressure.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li>Pathname lookup begins: <code>path_lookupat()</code> calls <code>walk_component()</code> for each path component.</li>
<li><code>lookup_fast()</code> hashes the (parent dentry, name) pair and checks <code>dentry_hashtable</code> with RCU read lock.</li>
<li><strong>Cache hit</strong>: a dentry is found and reference-counted via <code>lockref_get_not_dead()</code>; the lookup returns immediately without filesystem I/O.</li>
<li><strong>Cache miss</strong>: <code>lookup_slow()</code> acquires <code>parent->d_inode->i_rwsem</code>, calls <code>d_lookup()</code> again under lock (to close a race), then calls the filesystem's <code>inode_operations->lookup()</code>.</li>
<li>The filesystem reads the directory entry and calls <code>d_add()</code> or <code>d_splice_alias()</code> to insert a new dentry into the cache.</li>
<li>Dentry eviction: under memory pressure, <code>shrink_dcache_sb()</code> / <code>dcache_shrinker</code> calls <code>dentry_kill()</code> on unused (zero-refcount) dentries in LRU order.</li>
<li>Negative dentries (for nonexistent files) are also cached to avoid repeated "file not found" disk lookups; they expire via timer or explicit <code>d_invalidate()</code>.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Dentry leaks</strong>: A module that calls <code>d_lookup()</code> without a matching <code>dput()</code> increments the dentry's reference count permanently; the dentry is never evicted, slowly growing the dcache without bound.</li>
<li><strong>Stale negative dentry after create</strong>: 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 <code>actimeo</code> timeout.</li>
<li><strong>Alias dentries on hardlinks</strong>: Multiple dentries can point to the same inode (hardlinks); <code>d_find_alias()</code> finds all aliases; operations that must be coherent across aliases (e.g., <code>rename()</code>) must lock all aliases.</li>
<li><strong>Dentry hash table scalability</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_2" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.2</span>
<h3 class="item-title">Inode Cache (`fs/inode.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The inode cache stores <code>struct inode</code> 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 <code>sb + ino</code>) and an LRU list for eviction.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>iget_locked(sb, ino)</code> checks <code>inode_hashtable</code> for an existing inode; if found, returns a locked reference.</li>
<li>On cache miss: <code>alloc_inode()</code> β <code>sb->s_op->alloc_inode()</code> allocates a filesystem-specific inode struct (embedded or separate from <code>struct inode</code>).</li>
<li>The inode is added to the hash table and marked <code>I_NEW</code>; the caller must call <code>sb->s_op->read_inode()</code> (or its equivalent) to populate the inode from disk.</li>
<li><code>unlock_new_inode()</code> clears <code>I_NEW</code>, waking any waiters that were blocked on <code>wait_on_inode()</code>.</li>
<li>Normal usage: <code>iget_locked()</code> returns the locked inode; the caller increments its reference count via <code>ihold()</code> and stores it in a dentry.</li>
<li>When all references drop: <code>iput_final()</code> calls <code>sb->s_op->evict_inode()</code> to write back dirty data and release filesystem-specific state.</li>
<li>The inode struct is then returned to the inode cache's slab (<code>inode_cachep</code>) or freed if the cache is under pressure.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Inode number reuse race</strong>: After <code>iput()</code> removes an inode from the cache, a new file created on the filesystem may reuse the same inode number; a concurrent <code>iget_locked()</code> call racing with the eviction may return the old, partially-cleared inode.</li>
<li><strong><code>I_DIRTY</code> writeback ordering</strong>: An inode is marked <code>I_DIRTY_DATASYNC</code> on a metadata write; if <code>evict_inode()</code> is called before writeback completes, <code>write_inode_now()</code> must be called to flush dirty metadata.</li>
<li><strong>Filesystem-specific inode allocation failure</strong>: If <code>s_op->alloc_inode()</code> fails (OOM), <code>iget_locked()</code> returns <code>ERR_PTR(-ENOMEM)</code>; callers that don't check the error create a NULL pointer dereference.</li>
<li><strong>Inode cache over-retention</strong>: Large filesystems with millions of inodes can fill the inode cache; the <code>inode_shrinker</code> evicts inodes but can be slow; a "dentry/inode storm" (rapidly creating and deleting files) can exhaust the slab allocator.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_3" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.3</span>
<h3 class="item-title">Page Cache (`mm/filemap.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The page cache (address space cache) stores filesystem pages in memory indexed by <code>(inode, page_index)</code> pairs in a per-inode <code>address_space</code> 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 <code>pdflush</code>/<code>writeback</code> threads. It is also used for memory-mapped files.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>filemap_get_pages()</code> (called from <code>generic_file_read_iter()</code>) looks up the page in <code>inode->i_mapping</code> XArray.</li>
<li><strong>Cache hit</strong>: the page is returned; its reference count is incremented.</li>
<li><strong>Cache miss</strong>: <code>page_cache_alloc()</code> allocates a new page; <code>add_to_page_cache_lru()</code> inserts it into the XArray and the LRU list.</li>
<li><code>a_ops->readpage()</code> / <code>readahead()</code> submits I/O to populate the page from disk.</li>
<li>The calling task waits on the page's <code>PG_locked</code> bit via <code>wait_on_page_locked()</code>; when I/O completes, the driver calls <code>unlock_page()</code>.</li>
<li>The page is returned; <code>copy_page_to_iter()</code> copies data to the userspace buffer.</li>
<li>Write path: <code>generic_perform_write()</code> β <code>a_ops->write_begin()</code> locks the page; data is copied from userspace; <code>a_ops->write_end()</code> marks the page <code>PG_dirty</code>.</li>
<li><code>balance_dirty_pages_ratelimited()</code> throttles the writer if dirty ratio thresholds are exceeded.</li>
<li>Writeback: <code>wb_writeback()</code> calls <code>a_ops->writepages()</code> to submit dirty pages to the block layer.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Page cache coherence with direct I/O</strong>: <code>O_DIRECT</code> bypasses the page cache; a file opened with <code>O_DIRECT</code> while 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.</li>
<li><strong>Dirty ratio threshold exhaustion</strong>: If the dirty ratio (<code>vm.dirty_ratio</code>) is exceeded, the writing process is throttled in <code>balance_dirty_pages()</code>; under extreme write pressure, all processes writing to disk may be throttled simultaneously, causing application-visible stalls.</li>
<li><strong>Page writeback error handling</strong>: If writeback fails (e.g., network filesystem timeout), <code>mapping_set_error()</code> records the error; subsequent <code>fsync()</code>/<code>close()</code> calls return the error. But if the error is not consumed between two <code>close()</code> calls, the second call may succeed without seeing the error (Linux 5.1+ <code>errseq_t</code> fixes this).</li>
<li><strong>Page eviction under mmap</strong>: 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; <code>try_to_unmap()</code> must succeed before <code>shrink_page_list()</code> can reclaim it.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_4" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.4</span>
<h3 class="item-title">VFS `open()` Path (`fs/open.c`, `fs/namei.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The VFS <code>open()</code> path is the kernel's implementation of <code>open(2)</code> / <code>openat(2)</code>: it resolves a pathname to an inode, checks permissions, allocates a <code>struct file</code>, 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.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>sys_openat2()</code> β <code>do_sys_open()</code> β <code>do_filp_open()</code> β <code>path_openat()</code>.</li>
<li><code>path_init()</code> establishes the starting dentry (root <code>/</code> or current working directory).</li>
<li><code>link_path_walk()</code> resolves each component: for each slash-delimited name, calls <code>walk_component()</code> β <code>lookup_fast()</code> β (on miss) <code>lookup_slow()</code>.</li>
<li>Symlink resolution: each symlink encountered calls <code>pick_link()</code> β recursively resolves the symlink target (up to <code>MAXSYMLINKS = 40</code> depth).</li>
<li>At the final component: if <code>O_CREAT</code> is set, <code>atomic_open()</code> or <code>lookup_open()</code> is called; if the file doesn't exist, <code>vfs_create()</code> β <code>inode_ops->create()</code> creates it.</li>
<li><code>vfs_open()</code> β <code>do_dentry_open()</code>: checks <code>inode_permission()</code> (DAC + LSM hooks); calls <code>f->f_op->open(inode, file)</code>.</li>
<li>A file descriptor is allocated from the process's <code>fdtable</code> via <code>get_unused_fd_flags()</code>.</li>
<li><code>fd_install(fd, file)</code> atomically places the <code>struct file *</code> into the fdtable.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>TOCTOU (time-of-check/time-of-use) races</strong>: Between <code>path_lookupat()</code> and <code>vfs_open()</code>, the filesystem state can change; <code>O_NOFOLLOW</code> and <code>openat2()</code> with <code>RESOLVE_NO_SYMLINKS</code> reduce the attack surface but cannot eliminate all races.</li>
<li><strong>Too many open files</strong>: <code>get_unused_fd_flags()</code> returns <code>EMFILE</code> when the process's <code>fdtable</code> is full (up to <code>RLIMIT_NOFILE</code>); the filesystem's <code>inode_ops->create()</code> may have already run, leaving a created-but-unreachable file.</li>
<li><strong><code>O_CREAT | O_EXCL</code> race</strong>: Two processes simultaneously calling <code>open(path, O_CREAT|O_EXCL)</code> on the same path; only one succeeds; the filesystem's <code>atomic_open()</code> or <code>inode_ops->create()</code> must use an atomic create mechanism to avoid creating duplicate files.</li>
<li><strong>Pathname too long</strong>: Pathname components are bounded by <code>NAME_MAX</code> (255 bytes); the full path by <code>PATH_MAX</code> (4096 bytes); exceeding these returns <code>ENAMETOOLONG</code> before any filesystem I/O.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_5" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.5</span>
<h3 class="item-title">VFS `read()` / `write()` (`fs/read_write.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The VFS <code>read(2)</code> and <code>write(2)</code> paths dispatch file I/O through the <code>file->f_op->read_iter</code> / <code>write_iter</code> 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 <code>iov_iter</code>.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>sys_read(fd, buf, count)</code> β <code>ksys_read()</code> β <code>vfs_read()</code>.</li>
<li><code>file_pos_read(f)</code> reads and locks the current file position (<code>f->f_pos</code>).</li>
<li><code>rw_verify_area()</code>: verifies the file is open for the requested direction; checks mandatory locks; calls <code>security_file_permission()</code> (LSM hook).</li>
<li><code>call_read_iter(f, &kiocb, &iter)</code> β <code>f->f_op->read_iter(&kiocb, &iter)</code>.</li>
<li>For regular files: <code>generic_file_read_iter()</code> β page cache lookup β readahead if needed β <code>copy_page_to_iter()</code> to userspace buffer.</li>
<li>For O_DIRECT: <code>generic_file_direct_write()</code> submits bios directly, bypassing the page cache.</li>
<li><code>file_pos_write(f, pos)</code> updates <code>f->f_pos</code> under <code>f->f_lock</code>.</li>
<li>Returns bytes transferred (may be less than <code>count</code> for signals, EOF, pipe full, etc.).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Short read</strong>: 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.</li>
<li><strong><code>f_pos</code> race on shared file descriptor</strong>: Two threads sharing the same <code>struct file</code> (via <code>fork()</code> without <code>O_CLOEXEC</code>) racing on <code>f->f_pos</code>; the kernel serializes <code>f_pos</code> updates with <code>f->f_lock</code> but the read/update window is not atomic.</li>
<li><strong><code>O_APPEND</code> semantics</strong>: Writes with <code>O_APPEND</code> seek to end-of-file and write atomically under the inode's <code>i_mutex</code>; on NFS, this atomicity guarantee may be lost if the server reboots between the seek and the write.</li>
<li><strong>Blocking <code>read()</code> on a pipe</strong>: A <code>read()</code> from an empty pipe blocks until data is available or all write ends are closed; if the writer is killed, <code>read()</code> returns 0 (EOF); a signal to the reader returns <code>-EINTR</code>.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_6" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.6</span>
<h3 class="item-title">Mount Subsystem (`fs/namespace.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>The mount subsystem manages filesystem mount points, maintaining a tree of <code>struct mount</code> objects (each containing a <code>vfsmount</code> and a dentry binding point). It supports bind mounts, shared/private/slave/unbindable propagation types, mount namespaces (per-process mount views), and <code>pivot_root()</code> / <code>chroot()</code> operations.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>sys_mount(source, target, fstype, flags, data)</code> β <code>do_mount()</code>.</li>
<li><code>lookup_mnt_in_ns()</code> looks up the target path in the current mount namespace.</li>
<li>For a new filesystem mount: <code>vfs_kern_mount()</code> β <code>mount_fs()</code> calls <code>fstype->mount(fstype, flags, dev, data)</code> β returns a new <code>dentry</code> and <code>super_block</code>.</li>
<li><code>graft_tree()</code> attaches the new <code>struct mount</code> to the target dentry in the mount tree.</li>
<li>For bind mounts (<code>MS_BIND</code>): <code>copy_tree()</code> duplicates a subtree of the mount tree and attaches it at the target.</li>
<li>Mount propagation: <code>propagate_mnt()</code> propagates the new mount to all peer/slave mounts in the same propagation group.</li>
<li>The new mount is visible in <code>/proc/self/mounts</code> and in the VFS path walk (intercepted by <code>follow_mount()</code> in <code>walk_component()</code>).</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Mount namespace leak</strong>: A process that enters a mount namespace and creates mounts without calling <code>umount()</code> before exiting leaves orphan mounts; they persist until the last process holding a reference to the namespace exits.</li>
<li><strong>Propagation storm</strong>: In a heavily shared mount namespace (e.g., systemd's <code>MS_SHARED</code> root), every <code>mount()</code> call propagates to all peers; with thousands of containers sharing a namespace, one <code>mount()</code> call triggers thousands of propagation operations.</li>
<li><strong><code>pivot_root()</code> ordering requirements</strong>: <code>pivot_root()</code> requires the new root and old root to be on different filesystems and that the new root be a mount point; violating these constraints returns <code>EINVAL</code> and can leave the filesystem in a partially-pivoted state.</li>
<li><strong>Unmount with busy mountpoint</strong>: <code>umount()</code> fails with <code>EBUSY</code> if any file or directory on the mount is in use (open files, working directories, nested mounts); <code>MNT_FORCE</code> can unmount NFS even with open files but may cause data loss.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_7" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.7</span>
<h3 class="item-title">`fsync` / Writeback (`fs/sync.c`, `fs/fs-writeback.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p>Writeback is the kernel's mechanism for asynchronously flushing dirty pages (modified file data and metadata) from the page cache to storage. <code>fsync(2)</code> / <code>fdatasync(2)</code> are synchronous variants that guarantee all dirty data for a specific file has been written and acknowledged by the storage device before returning.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>fsync(fd)</code> β <code>vfs_fsync_range()</code> β <code>file->f_op->fsync(file, 0, LLONG_MAX, 0)</code>.</li>
<li>The filesystem's <code>fsync</code> implementation (e.g., <code>ext4_sync_file()</code>):</li>
<li style="list-style-type:lower-alpha">Calls <code>file_write_and_wait_range()</code> to submit and wait for all dirty data pages in the page cache.</li>
<li style="list-style-type:lower-alpha">Logs a journal commit (for journaled filesystems: ext4, XFS, btrfs) to ensure metadata consistency.</li>
<li style="list-style-type:lower-alpha">Calls <code>blkdev_issue_flush()</code> to flush the device's write cache.</li>
<li>Asynchronous writeback (background): <code>wb_do_writeback()</code> runs periodically from <code>bdi_writeback</code> kernel threads; it calls <code>writeback_inodes_wb()</code> β <code>writeback_single_inode()</code> β <code>do_writepages()</code> β <code>a_ops->writepages()</code>.</li>
<li>Dirty ratio enforcement: <code>balance_dirty_pages()</code> throttles the process if dirty pages exceed <code>vm.dirty_ratio</code>.</li>
<li><code>writeback_inodes_sb_nr()</code> can be triggered by <code>sync(2)</code> or <code>syncfs(2)</code> to flush all dirty inodes on a superblock.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>fsync on rename (rename without fsync of parent)</strong>: Renaming a file over another is atomic at the VFS level but requires fsyncing the parent directory to guarantee durability; many applications call <code>fsync(new_file_fd)</code> but not <code>fsync(dir_fd)</code>, so a crash can leave the directory pointing to the old file.</li>
<li><strong>Writeback loop stall</strong>: Under extreme write load, <code>pdflush</code> threads cannot drain dirty pages faster than new dirty pages are created; the system enters "writeback throttling" and all writing processes may block indefinitely.</li>
<li><strong>ext4 delayed allocation + crash</strong>: With <code>data=ordered</code> mode, 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.</li>
<li><strong>btrfs CoW writeback ordering</strong>: 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.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_8" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.8</span>
<h3 class="item-title">`splice` / `sendfile` (`fs/splice.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>splice(2)</code> and <code>sendfile(2)</code> implement zero-copy data transfer between file descriptors, eliminating the need to copy data through userspace. <code>sendfile()</code> transfers from a file fd to a socket fd using the page cache; <code>splice()</code> moves data between arbitrary fds via an internal pipe buffer without touching userspace memory.</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>sendfile(out_fd, in_fd, offset, count)</code> β <code>do_sendfile()</code>.</li>
<li><code>vfs_sendfile()</code> calls <code>in_file->f_op->splice_read()</code> to populate pipe buffers from the source file (page cache pages are added to the pipe without copying).</li>
<li><code>splice_from_pipe()</code> calls <code>out_file->f_op->splice_write()</code> on the destination socket.</li>
<li>For socket send: <code>skb_splice_bits()</code> maps the pipe's pages into <code>sk_buff</code> fragments directly, avoiding a <code>memcpy()</code>.</li>
<li>For <code>splice(in_fd, in_off, out_fd, out_off, len, flags)</code>:</li>
<li style="list-style-type:lower-alpha">If <code>in_fd</code> is a pipe: pages are moved from the in-pipe's buffer to the out-fd.</li>
<li style="list-style-type:lower-alpha">If <code>in_fd</code> is a file: <code>generic_file_splice_read()</code> fills a temporary pipe from the page cache, then drains it into the out-fd.</li>
<li>Pipe buffer reference counts track when pages can be released back to the page cache.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><strong>Non-splice-capable fd</strong>: Not all fd types support splice; a device file or procfs file without <code>f_op->splice_read</code> falls back to <code>default_file_splice_read()</code>, which copies data through a temporary page buffer β no actual zero-copy.</li>
<li><strong>sendfile to non-socket</strong>: <code>sendfile()</code> is defined only for socket destinations on most Linux versions; using it with a regular file destination returns <code>EINVAL</code>.</li>
<li><strong>Pipe buffer exhaustion</strong>: <code>splice()</code> requires at least one pipe fd; the pipe's buffer (default 64 KiB, configurable via <code>F_SETPIPE_SZ</code>) limits the in-flight data; a full pipe blocks the writer.</li>
<li><strong>Page pinning under memory pressure</strong>: Pages used in a <code>splice()</code> transfer are reference-counted to prevent eviction; a long-lived <code>splice()</code> operation on a large file pins many pages, potentially causing memory pressure for other workloads.</li>
</ul></div>
</section>
</div>
</div>
<div class="card" id="item_6_9" data-cat="6" style="--acc:#4aaede">
<div class="card-header">
<span class="item-num">6.9</span>
<h3 class="item-title">`epoll` (`fs/eventpoll.c`)</h3>
<span class="cat-badge" style="background:#4aaede20;color:#4aaede;border-color:#4aaede40">Cat 6</span>
</div>
<div class="card-body">
<section class="field">
<h4 class="field-label def-label">Definition</h4>
<div class="field-content"><p><code>epoll</code> is a scalable I/O event notification mechanism for monitoring large numbers of file descriptors simultaneously. Unlike <code>poll(2)</code> / <code>select(2)</code> (which scan all fds in O(N)), <code>epoll</code> 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.).</p></div>
</section>
<section class="field">
<h4 class="field-label flow-label">Execution Flow</h4>
<div class="field-content"><ol>
<li><code>epoll_create1(flags)</code> β creates an <code>eventpoll</code> struct and an anonymous inode/fd for it.</li>
<li><code>epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &event)</code>: adds <code>fd</code> to the RB tree; calls <code>ep_insert()</code> β <code>add_wait_queue()</code> to register a callback on <code>fd</code>'s wait queue.</li>
<li>When <code>fd</code> becomes readable/writable: the kernel calls <code>ep_poll_callback()</code> β adds the epoll item to the <code>eventpoll->rdllist</code> (ready list) and wakes up any task blocked in <code>epoll_wait()</code>.</li>
<li><code>epoll_wait(epfd, events, maxevents, timeout)</code>:</li>
<li style="list-style-type:lower-alpha">Checks <code>ep->rdllist</code>; if events are ready, calls <code>ep_send_events()</code> β copies events to userspace.</li>
<li style="list-style-type:lower-alpha">If none ready: adds the calling task to <code>ep->wq</code>, calls <code>schedule_hrtimeout_range()</code>.</li>
<li style="list-style-type:lower-alpha">On wake (by <code>ep_poll_callback()</code>): re-checks <code>rdllist</code>, copies events.</li>
<li><code>EPOLLET</code> (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.</li>
</ol></div>
</section>
<section class="field">
<h4 class="field-label edge-label">Edge Cases & Failure Modes</h4>
<div class="field-content"><ul>
<li><s
β¦ (truncated β use Raw)