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 Taxonomy — 80 Core Components</title>
<style>
:root {
--bg:#0d1117; --surface:#161b22; --surface2:#1c2128; --border:#30363d;
--text:#e6edf3; --muted:#8b949e; --code:#79c0ff; --codebg:#1f2937;
--def:#58a6ff; --flow:#3fb950; --edge:#f78166;
--sidebar-w:260px;
color-scheme:dark;
}
*,*::before,*::after{box-sizing:border-box;margin:0;padding:0}
html,body{height:100%;background:var(--bg);color:var(--text);font-family:'Segoe UI',system-ui,-apple-system,sans-serif;font-size:14px;line-height:1.6}
/* ── LAYOUT ── */
.layout{display:flex;height:100vh;overflow:hidden}
.sidebar{width:var(--sidebar-w);flex-shrink:0;background:var(--surface);border-right:1px solid var(--border);overflow-y:auto;display:flex;flex-direction:column}
.main{flex:1;overflow-y:auto;display:flex;flex-direction:column}
/* ── SIDEBAR ── */
.sidebar-header{padding:16px 16px 10px;border-bottom:1px solid var(--border);position:sticky;top:0;background:var(--surface);z-index:10}
.logo{font-size:.95rem;font-weight:700;color:var(--text);display:flex;align-items:center;gap:8px}
.logo-icon{font-size:1.3rem}
.sidebar-meta{font-size:.7rem;color:var(--muted);margin-top:2px}
.sidebar-search{margin:10px 12px;position:relative}
.sidebar-search input{width:100%;background:var(--surface2);border:1px solid var(--border);border-radius:6px;color:var(--text);padding:6px 10px 6px 28px;font-size:.8rem;outline:none}
.sidebar-search input:focus{border-color:var(--def)}
.search-ico{position:absolute;left:9px;top:50%;transform:translateY(-50%);color:var(--muted);font-size:.8rem;pointer-events:none}
.sidebar-nav{padding:4px 8px 16px}
.sidebar-all{display:flex;align-items:center;gap:8px;padding:7px 10px;border-radius:7px;cursor:pointer;color:var(--muted);font-size:.8rem;font-weight:600;text-decoration:none;transition:background .12s,color .12s;margin-bottom:4px}
.sidebar-all:hover,.sidebar-all.active{background:rgba(88,166,255,.1);color:var(--def)}
.sidebar-item{display:flex;align-items:center;gap:8px;padding:6px 10px;border-radius:7px;cursor:pointer;color:var(--muted);font-size:.78rem;text-decoration:none;transition:background .12s,color .12s;margin-bottom:2px}
.sidebar-item:hover{background:rgba(255,255,255,.04);color:var(--text)}
.sidebar-item.active{background:hsl(var(--hue,210),40%,15%);color:hsl(var(--hue,210),70%,70%)}
.si-icon{width:24px;height:24px;border-radius:5px;display:flex;align-items:center;justify-content:center;font-size:.85rem;flex-shrink:0}
.si-text{flex:1;min-width:0}
.si-num{font-weight:700;margin-right:4px;font-size:.7rem;opacity:.7}
.si-count{font-size:.65rem;background:var(--surface2);border:1px solid var(--border);border-radius:10px;padding:1px 6px;flex-shrink:0}
/* ── TOP BAR ── */
.topbar{background:rgba(13,17,23,.95);backdrop-filter:blur(10px);border-bottom:1px solid var(--border);padding:10px 20px;display:flex;align-items:center;gap:12px;position:sticky;top:0;z-index:50;flex-shrink:0}
.tb-title{font-size:.85rem;font-weight:600;color:var(--muted);flex:1}
.tb-counter{font-size:.72rem;background:var(--surface2);border:1px solid var(--border);border-radius:12px;padding:3px 10px;color:var(--muted)}
.tb-actions{display:flex;gap:6px}
.tb-btn{background:var(--surface2);border:1px solid var(--border);color:var(--muted);padding:4px 10px;border-radius:5px;cursor:pointer;font-size:.75rem}
.tb-btn:hover{color:var(--text);border-color:var(--muted)}
/* ── CONTENT ── */
.content{padding:16px 24px 60px;max-width:860px;width:100%}
/* ── CATEGORY DIVIDER ── */
.cat-divider{display:flex;align-items:center;gap:10px;padding:24px 0 10px;margin-top:8px;border-bottom:1px solid var(--border);margin-bottom:14px}
.cat-divider:first-child{padding-top:8px}
.cdiv-icon{width:32px;height:32px;border-radius:7px;display:flex;align-items:center;justify-content:center;font-size:1.1rem;flex-shrink:0}
.cdiv-title{font-size:.9rem;font-weight:700;color:var(--text);flex:1}
.cdiv-badge{font-size:.65rem;color:var(--muted);background:var(--surface2);border:1px solid var(--border);border-radius:10px;padding:2px 8px}
/* ── CARDS ── */
.card{background:var(--surface);border:1px solid var(--border);border-left:3px solid hsl(var(--hue),65%,45%);border-radius:8px;margin-bottom:10px;overflow:hidden;transition:border-color .15s}
.card:hover{border-color:hsl(var(--hue),55%,35%)}
.card.open .ch-toggle{transform:rotate(180deg)}
.card-head{display:flex;align-items:center;gap:10px;padding:12px 14px;cursor:pointer;user-select:none}
.ch-left{display:flex;align-items:center;gap:10px;flex:1;min-width:0}
.item-num{font-size:.7rem;font-weight:700;color:hsl(var(--hue),70%,60%);font-family:monospace;min-width:28px;flex-shrink:0}
.ch-titles{min-width:0}
.item-title{font-size:.9rem;font-weight:600;color:var(--text);white-space:nowrap;overflow:hidden;text-overflow:ellipsis}
.item-def-short{font-size:.75rem;color:var(--muted);white-space:nowrap;overflow:hidden;text-overflow:ellipsis;margin-top:1px}
.ch-toggle{color:var(--muted);font-size:.75rem;transition:transform .2s;flex-shrink:0}
.card-body{display:none;padding:0 14px 14px;border-top:1px solid var(--border)}
.card.open .card-body{display:block}
/* ── VIEW TABS ── */
.view-tabs{display:flex;gap:4px;padding:10px 0 10px;border-bottom:1px solid var(--border);margin-bottom:12px}
.vtab{background:none;border:1px solid var(--border);color:var(--muted);padding:3px 12px;border-radius:14px;cursor:pointer;font-size:.72rem;transition:all .12s}
.vtab.active{background:var(--surface2);color:var(--text);border-color:var(--muted)}
/* ── FIELDS ── */
.field{margin-bottom:14px}
.field:last-child{margin-bottom:0}
.field-lbl{font-size:.65rem;font-weight:700;letter-spacing:.07em;text-transform:uppercase;padding:3px 0;border-bottom:1px solid;margin-bottom:6px}
.lbl-def{color:var(--def);border-bottom-color:rgba(88,166,255,.2)}
.lbl-flow{color:var(--flow);border-bottom-color:rgba(63,185,80,.2)}
.lbl-edge{color:var(--edge);border-bottom-color:rgba(247,129,102,.2)}
.field-body p{font-size:.85rem;color:var(--text);margin-bottom:6px}
.field-body p:last-child{margin-bottom:0}
.field-body ol,.field-body ul{padding-left:20px;font-size:.83rem;color:var(--text)}
.field-body li{margin-bottom:4px}
.field-body li.sub{list-style-type:lower-alpha;margin-left:12px}
code{background:var(--codebg);color:var(--code);padding:1px 5px;border-radius:3px;font-family:'Cascadia Code',Consolas,monospace;font-size:.78em}
/* ── MDL VIEW ── */
.view-mdl{font-size:.82rem}
.mdl-row{display:flex;gap:12px;padding:8px 0;border-bottom:1px solid var(--border)}
.mdl-row:last-child{border-bottom:none}
.mdl-label{font-size:.62rem;font-weight:700;letter-spacing:.08em;color:var(--muted);min-width:38px;padding-top:3px;text-transform:uppercase;flex-shrink:0}
.mdl-def{color:var(--text);font-size:.83rem;line-height:1.5}
.steps-wrap{display:flex;flex-wrap:wrap;gap:4px}
.step-chip{background:rgba(63,185,80,.08);border:1px solid rgba(63,185,80,.2);color:var(--flow);padding:2px 8px;border-radius:12px;font-size:.72rem;white-space:nowrap}
.edges-wrap{display:flex;flex-direction:column;gap:5px;width:100%}
.edge-row{display:flex;gap:8px;align-items:flex-start}
.edge-label{font-size:.7rem;font-weight:600;color:var(--edge);flex-shrink:0;min-width:120px;padding-top:1px}
.edge-desc{font-size:.75rem;color:var(--muted)}
/* ── NO RESULTS ── */
.no-results{text-align:center;color:var(--muted);padding:60px 20px;font-size:.9rem}
/* ── FOOTER ── */
.footer{border-top:1px solid var(--border);padding:16px 24px;font-size:.72rem;color:var(--muted)}
/* ── MOBILE ── */
@media(max-width:700px){
.sidebar{display:none}
.content{padding:12px 14px 40px}
.topbar{padding:8px 14px}
.item-def-short{display:none}
}
</style>
</head>
<body>
<div class="layout">
<!-- SIDEBAR -->
<nav class="sidebar">
<div class="sidebar-header">
<div class="logo"><span class="logo-icon">🐧</span>Linux Kernel Taxonomy</div>
<div class="sidebar-meta">80 components · 8 categories · Linux 5.x/6.x</div>
</div>
<div class="sidebar-search">
<span class="search-ico">⌕</span>
<input type="text" id="sidebar-search" placeholder="Search…" oninput="doSearch(this.value)" autocomplete="off">
</div>
<div class="sidebar-nav">
<a class="sidebar-all active" id="nav-all" href="#" onclick="filterCat('all');return false">
<span style="font-size:1rem">≡</span> All categories
</a>
<a class="sidebar-item" data-cat="1" href="#cat1" onclick="filterCat('1');return false">
<span class="si-icon" style="background:hsl(210,70%,20%);color:hsl(210,80%,65%)">⚙️</span>
<span class="si-text"><span class="si-num">S1</span>Core Kernel Subsystems</span>
<span class="si-count" id="count-1">10</span>
</a>
<a class="sidebar-item" data-cat="2" href="#cat2" onclick="filterCat('2');return false">
<span class="si-icon" style="background:hsl(265,70%,20%);color:hsl(265,80%,65%)">🔒</span>
<span class="si-text"><span class="si-num">S2</span>Synchronization Primitives</span>
<span class="si-count" id="count-2">10</span>
</a>
<a class="sidebar-item" data-cat="3" href="#cat3" onclick="filterCat('3');return false">
<span class="si-icon" style="background:hsl(145,70%,20%);color:hsl(145,80%,65%)">🧠</span>
<span class="si-text"><span class="si-num">S3</span>Memory Allocators</span>
<span class="si-count" id="count-3">10</span>
</a>
<a class="sidebar-item" data-cat="4" href="#cat4" onclick="filterCat('4');return false">
<span class="si-icon" style="background:hsl(30,70%,20%);color:hsl(30,80%,65%)">📅</span>
<span class="si-text"><span class="si-num">S4</span>Process & CPU Schedulers</span>
<span class="si-count" id="count-4">10</span>
</a>
<a class="sidebar-item" data-cat="5" href="#cat5" onclick="filterCat('5');return false">
<span class="si-icon" style="background:hsl(340,70%,20%);color:hsl(340,80%,65%)">💾</span>
<span class="si-text"><span class="si-num">S5</span>Block & I/O Schedulers</span>
<span class="si-count" id="count-5">10</span>
</a>
<a class="sidebar-item" data-cat="6" href="#cat6" onclick="filterCat('6');return false">
<span class="si-icon" style="background:hsl(195,70%,20%);color:hsl(195,80%,65%)">📂</span>
<span class="si-text"><span class="si-num">S6</span>Virtual Filesystems (VFS)</span>
<span class="si-count" id="count-6">10</span>
</a>
<a class="sidebar-item" data-cat="7" href="#cat7" onclick="filterCat('7');return false">
<span class="si-icon" style="background:hsl(100,70%,20%);color:hsl(100,80%,65%)">🌐</span>
<span class="si-text"><span class="si-num">S7</span>Network Stack Hooks</span>
<span class="si-count" id="count-7">10</span>
</a>
<a class="sidebar-item" data-cat="8" href="#cat8" onclick="filterCat('8');return false">
<span class="si-icon" style="background:hsl(280,70%,20%);color:hsl(280,80%,65%)">🛡️</span>
<span class="si-text"><span class="si-num">S8</span>Linux Security Modules (LSMs)</span>
<span class="si-count" id="count-8">10</span>
</a>
</div>
</nav>
<!-- MAIN -->
<div class="main">
<div class="topbar">
<span class="tb-title" id="tb-label">All 8 categories</span>
<span class="tb-counter" id="tb-counter">80 / 80 shown</span>
<div class="tb-actions">
<button class="tb-btn" onclick="expandAll()">Expand all</button>
<button class="tb-btn" onclick="collapseAll()">Collapse all</button>
<button class="tb-btn" onclick="switchAllView('mdl')">MDL view</button>
<button class="tb-btn" onclick="switchAllView('full')">Full view</button>
</div>
</div>
<div class="content" id="content">
<div class="cat-divider" id="cat1" data-cat="1">
<span class="cdiv-icon" style="background:hsl(210,70%,18%);color:hsl(210,80%,65%)">⚙️</span>
<h2 class="cdiv-title">S1 — Core Kernel Subsystems</h2>
<span class="cdiv-badge">10 components</span>
</div>
<div class="card" id="c1_1" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_1')">
<div class="ch-left">
<span class="item-num">1.1</span>
<div class="ch-titles">
<h3 class="item-title">Process Creation Subsystem (`do_fork` / `copy_process`)</h3>
<p class="item-def-short">The process creation subsystem is the kernel mechanism that creates new processes and threads by duplicating an exist…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_1','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_1','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The process creation subsystem is the kernel mechanism that creates new processes and threads by duplicating an exist…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Userspace calls `fork()`, `vfork()`, `clone()`, or `clo…</span><span class="step-chip">The syscall entry (`sys_clone`, `sys_fork`, etc.) colle…</span><span class="step-chip">`copy_process()` is called: it allocates a new `task_st…</span><span class="step-chip">Task struct fields are initialized: counters reset, PID…</span><span class="step-chip">Depending on `CLONE_*` flags: `copy_mm()` duplicates or…</span><span class="step-chip">The new task is inserted into the task list under `task…</span><span class="step-chip">`wake_up_new_task()` places the child on a run queue wi…</span><span class="step-chip">The scheduler may preempt the parent and begin running …</span><span class="step-chip">Both parent and child return from the syscall: parent r…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">ENOMEM</span><span class="edge-desc">If `dup_task_struct()` or `copy_mm()` fails (OOM condition), `copy_process()` un</span></div><div class="edge-row"><span class="edge-label">PID namespace exhaustion</span><span class="edge-desc">`alloc_pid()` returns `NULL` if the namespace's PID range is saturated; the fork</span></div><div class="edge-row"><span class="edge-label">`RLIMIT_NPROC` exceeded</span><span class="edge-desc">If the user's process count exceeds the rlimit, `copy_process()` returns `EAGAIN</span></div><div class="edge-row"><span class="edge-label">`vfork()` deadlock</span><span class="edge-desc">The parent blocks on a completion until the child calls `exec()` or exits; if th</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_2" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_2')">
<div class="ch-left">
<span class="item-num">1.2</span>
<div class="ch-titles">
<h3 class="item-title">Interrupt Request (IRQ) Subsystem (`kernel/irq/`)</h3>
<p class="item-def-short">The IRQ subsystem manages hardware interrupt lines from device discovery through handler dispatch.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_2','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_2','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The IRQ subsystem manages hardware interrupt lines from device discovery through handler dispatch.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">At boot, `irq_init_percpu_irqstack()` and architecture-…</span><span class="step-chip">A driver calls `request_irq()` → `__setup_irq()`, which…</span><span class="step-chip">Hardware asserts an interrupt line; the CPU saves regis…</span><span class="step-chip">S`).</span><span class="step-chip">`handle_irq()` → `generic_handle_irq()` → `handle_level…</span><span class="step-chip">The irqchip's `irq_mask` or `irq_ack` is called to prev…</span><span class="step-chip">The registered `irqaction->handler` runs in interrupt c…</span><span class="step-chip">The handler returns `IRQ_HANDLED` or `IRQ_NONE`; if non…</span><span class="step-chip">The irqchip's `irq_unmask` / `irq_eoi` is called.</span><span class="step-chip">The CPU restores registers and resumes the interrupted …</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">IRQ storm</span><span class="edge-desc">A misbehaving device asserts its line continuously; the kernel detects this via </span></div><div class="edge-row"><span class="edge-label">Shared IRQ conflict</span><span class="edge-desc">Multiple devices on the same line (legacy PCI); if one device's handler fails to</span></div><div class="edge-row"><span class="edge-label">NMI nesting</span><span class="edge-desc">Non-Maskable Interrupts cannot be disabled; nested NMIs on x86 require the `nmi_</span></div><div class="edge-row"><span class="edge-label">Interrupt affinity migration race</span><span class="edge-desc">Changing `/proc/irq/N/smp_affinity` while an interrupt is in-flight can send EOI</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_3" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_3')">
<div class="ch-left">
<span class="item-num">1.3</span>
<div class="ch-titles">
<h3 class="item-title">System Call Interface (`arch/x86/entry/`)</h3>
<p class="item-def-short">The system call interface is the controlled gate through which userspace transitions to kernel privilege to request k…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_3','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_3','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The system call interface is the controlled gate through which userspace transitions to kernel privilege to request k…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Userspace loads the syscall number into `rax` (x86-</span><span class="step-chip">and arguments into `rdi`, `rsi`, `rdx`, `r10`, `r8`, `r…</span><span class="step-chip">The CPU switches to ring 0, saves `rip`/`rflags` to per…</span><span class="step-chip">S`.</span><span class="step-chip">The entry stub saves all registers to the kernel stack …</span><span class="step-chip">`do_syscall_64()` is called; it fetches the syscall num…</span><span class="step-chip">Bounds-checks the number against `NR_syscalls`; looks u…</span><span class="step-chip">Runs any active `seccomp` filters (BPF programs) before…</span><span class="step-chip">Calls the syscall handler (e.g., `sys_read`, `sys_mmap`…</span><span class="step-chip">The return value is placed in `regs->ax`.</span><span class="step-chip">The entry stub restores saved registers and executes `s…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Invalid syscall number</span><span class="edge-desc">Numbers ≥ `NR_syscalls` return `−ENOSYS`.</span></div><div class="edge-row"><span class="edge-label">`seccomp` SIGSYS kill</span><span class="edge-desc">A BPF filter returning `SECCOMP_RET_KILL_PROCESS` delivers `SIGSYS` and kills th</span></div><div class="edge-row"><span class="edge-label">Signal pending at syscall exit</span><span class="edge-desc">`exit_to_user_mode_prepare()` checks for pending signals; if found, the syscall </span></div><div class="edge-row"><span class="edge-label">`SMAP`/`SMEP` violations</span><span class="edge-desc">If the kernel accidentally dereferences a userspace pointer without `copy_from_u</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_4" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_4')">
<div class="ch-left">
<span class="item-num">1.4</span>
<div class="ch-titles">
<h3 class="item-title">Workqueue Subsystem (`kernel/workqueue.c`)</h3>
<p class="item-def-short">The workqueue subsystem provides a kernel-thread pool for deferred, process-context work.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_4','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_4','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The workqueue subsystem provides a kernel-thread pool for deferred, process-context work.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A kernel subsystem defines a `work_struct` and initiali…</span><span class="step-chip">`queue_work()` → `__queue_work()` selects the appropria…</span><span class="step-chip">The work item is added to the pool's `worklist`.</span><span class="step-chip">If no idle worker is available and the pool is below th…</span><span class="step-chip">The kworker thread calls `worker_thread()` → `process_o…</span><span class="step-chip">`process_one_work()` calls the handler function: `work-…</span><span class="step-chip">After the handler returns, the worker checks for more p…</span><span class="step-chip">Idle workers are reaped after `IDLE_WORKER_TIMEOUT` (5 …</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Work item requeue during flush</span><span class="edge-desc">Calling `queue_work()` from within a handler re-enqueues for the next iteration;</span></div><div class="edge-row"><span class="edge-label">Worker pool stall (watchdog)</span><span class="edge-desc">If all workers are blocked (e.g., waiting on a mutex held by work in the same po</span></div><div class="edge-row"><span class="edge-label">Memory allocation failure in `create_worker()`</span><span class="edge-desc">If `kthread_create()` fails during worker creation, the pool falls back to exist</span></div><div class="edge-row"><span class="edge-label">`WQ_MEM_RECLAIM` ordering</span><span class="edge-desc">Non-`WQ_MEM_RECLAIM` workqueues must not be called from memory-reclaim paths; do</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_5" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_5')">
<div class="ch-left">
<span class="item-num">1.5</span>
<div class="ch-titles">
<h3 class="item-title">Kernel Timer Subsystem (`kernel/time/`)</h3>
<p class="item-def-short">The timer subsystem provides two classes of kernel timers: `hrtimer` (high-resolution timers backed by CLOCK_MONOTONI…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_5','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_5','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The timer subsystem provides two classes of kernel timers: `hrtimer` (high-resolution timers backed by CLOCK_MONOTONI…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A caller initializes a timer: `hrtimer_init(&ht, CLOCK_…</span><span class="step-chip">`hrtimer_start()` calls `hrtimer_start_range_ns()`, whi…</span><span class="step-chip">The hardware timer (TSC-deadline, HPET, or ARM architec…</span><span class="step-chip">When the hardware fires, the interrupt handler calls `h…</span><span class="step-chip">`hrtimer_interrupt()` iterates expired timers from the …</span><span class="step-chip">The callback returns `HRTIMER_RESTART` (re-arms) or `HR…</span><span class="step-chip">The hardware timer is reprogrammed for the next expiry.</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Cascading timer overload</span><span class="edge-desc">If hundreds of timers expire simultaneously, `hrtimer_interrupt()` processes the</span></div><div class="edge-row"><span class="edge-label">Clock discontinuity</span><span class="edge-desc">Calling `settimeofday()` or `adjtimex()` while `CLOCK_REALTIME`-based hrtimers a</span></div><div class="edge-row"><span class="edge-label">`timer_list` overflows</span><span class="edge-desc">Jiffies-based timers use `timer_wheels`; a timer set for more than `MAX_JIFFY_OF</span></div><div class="edge-row"><span class="edge-label">`nohz_full` interactions</span><span class="edge-desc">On CPUs in `nohz_full` mode, the tick is suppressed; timers are only re-evaluate</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_6" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_6')">
<div class="ch-left">
<span class="item-num">1.6</span>
<div class="ch-titles">
<h3 class="item-title">Power Management Framework (`drivers/base/power/`)</h3>
<p class="item-def-short">The kernel power management framework orchestrates system-wide and per-device power state transitions.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_6','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_6','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The kernel power management framework orchestrates system-wide and per-device power state transitions.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A userspace tool writes `mem` or `disk` to `/sys/power/…</span><span class="step-chip">`enter_state()` → `pm_prepare()` calls each device driv…</span><span class="step-chip">`dpm_suspend()` calls `.suspend()` callbacks on all dev…</span><span class="step-chip">`dpm_suspend_late()` / `dpm_suspend_noirq()` follow, al…</span><span class="step-chip">CPU-specific suspend: each CPU is taken offline except …</span><span class="step-chip">On wake: the platform restores CPU state; `arch_resume_…</span><span class="step-chip">`dpm_resume_noirq()` → `dpm_resume_early()` → `dpm_resu…</span><span class="step-chip">`pm_finish()` calls `.complete()` on all devices; the s…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Driver suspend failure</span><span class="edge-desc">A driver returning non-zero from `.suspend()` aborts the suspend; `dpm_resume()`</span></div><div class="edge-row"><span class="edge-label">Firmware / ACPI AML bugs</span><span class="edge-desc">BIOS `_PTS` or `_WAK` methods can crash or wedge the system; `acpi_suspend_error</span></div><div class="edge-row"><span class="edge-label">Hibernation image corruption</span><span class="edge-desc">If the swap partition is modified between snapshot and restore, the kernel detec</span></div><div class="edge-row"><span class="edge-label">Runtime PM reference count leak</span><span class="edge-desc">A driver calling `pm_runtime_get()` without a matching `pm_runtime_put()` preven</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_7" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_7')">
<div class="ch-left">
<span class="item-num">1.7</span>
<div class="ch-titles">
<h3 class="item-title">Device Model and sysfs (`drivers/base/`, `fs/sysfs/`)</h3>
<p class="item-def-short">The kernel device model provides a unified hierarchical representation of all hardware devices and their relationship…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_7','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_7','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The kernel device model provides a unified hierarchical representation of all hardware devices and their relationship…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A bus driver (e.g., PCI) scans for devices and calls `d…</span><span class="step-chip">`device_register()` → `kobject_add()` creates a `kobjec…</span><span class="step-chip">`bus_probe_device()` iterates registered drivers; for e…</span><span class="step-chip">On match, `driver_probe_device()` calls `driver->probe(…</span><span class="step-chip">The driver claims the device; attributes are created vi…</span><span class="step-chip">A `uevent` is sent via `kobject_uevent()` → `netlink_br…</span><span class="step-chip">`udevd` processes the event, creates `/dev` nodes, load…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Driver probe failure</span><span class="edge-desc">If `probe()` returns an error, `driver_probe_device()` decrements the driver's r</span></div><div class="edge-row"><span class="edge-label">Probe deferral (`-EPROBE_DEFER`)</span><span class="edge-desc">A driver may return `-EPROBE_DEFER` if a dependency (e.g., a GPIO chip) is not y</span></div><div class="edge-row"><span class="edge-label">sysfs attribute race</span><span class="edge-desc">Reading a sysfs attribute while `device_unregister()` is running can reference f</span></div><div class="edge-row"><span class="edge-label">`kobject` reference count underflow</span><span class="edge-desc">Calling `kobject_put()` more times than `kobject_get()` triggers a `BUG()` in `k</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_8" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_8')">
<div class="ch-left">
<span class="item-num">1.8</span>
<div class="ch-titles">
<h3 class="item-title">Kernel Module Loader (`kernel/module/`)</h3>
<p class="item-def-short">The module loader implements `insmod`/`modprobe` support: it verifies ELF64 `.ko` files for valid `vermagic` (kernel …</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_8','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_8','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The module loader implements `insmod`/`modprobe` support: it verifies ELF64 `.ko` files for valid `vermagic` (kernel …</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Userspace calls `finit_module(fd, params, flags)` or `i…</span><span class="step-chip">`load_module()` reads the ELF sections into kernel memo…</span><span class="step-chip">`check_modinfo()` validates the `vermagic` string; mism…</span><span class="step-chip">`simplify_symbols()` resolves undefined symbols against…</span><span class="step-chip">`apply_relocations()` patches the module's code/data fo…</span><span class="step-chip">`module_init_layout_section()` sets up `__init` and `co…</span><span class="step-chip">`do_one_initcall(mod->init)` runs the module's `init_mo…</span><span class="step-chip">On success, the module is added to `modules` list; `__i…</span><span class="step-chip">On `rmmod`: `module_exit()` is called; `free_module()` …</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Symbol version mismatch</span><span class="edge-desc">Even if the symbol name matches, a CRC checksum mismatch (`CONFIG_MODVERSIONS`) </span></div><div class="edge-row"><span class="edge-label">`init()` failure</span><span class="edge-desc">If `init_module()` returns non-zero, the module is immediately unloaded; partial</span></div><div class="edge-row"><span class="edge-label">Tainted kernel</span><span class="edge-desc">Loading an unsigned or out-of-tree module sets the `TAINT_OOT_MODULE` flag; this</span></div><div class="edge-row"><span class="edge-label">Unload race</span><span class="edge-desc">If a module is in use (reference count > 0), `rmmod` returns `EWOULDBLOCK`; forc</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_9" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_9')">
<div class="ch-left">
<span class="item-num">1.9</span>
<div class="ch-titles">
<h3 class="item-title">Memory Management Subsystem (`mm/`)</h3>
<p class="item-def-short">The `mm/` subsystem is the kernel's unified memory management layer: it manages physical page frames (via the buddy a…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_9','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_9','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The `mm/` subsystem is the kernel's unified memory management layer: it manages physical page frames (via the buddy a…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`mmap(</span><span class="step-chip">` calls `do_mmap()` → `mmap_region()`, which allocates …</span><span class="step-chip">No physical pages are allocated yet (lazy allocation).</span><span class="step-chip">When the process accesses the mapped region, the CPU ra…</span><span class="step-chip">`do_page_fault()` → `handle_mm_fault()` → `handle_pte_f…</span><span class="step-chip">For anonymous faults: `do_anonymous_page()` calls `allo…</span><span class="step-chip">For file-backed: `do_fault()` calls the VMA's `vm_ops->…</span><span class="step-chip">`update_mmu_cache()` flushes the TLB entry.</span><span class="step-chip">`kswapd` and `vmscan` run asynchronously to reclaim pag…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">OOM (Out-of-Memory)</span><span class="edge-desc">When both physical memory and swap are exhausted, `out_of_memory()` invokes the </span></div><div class="edge-row"><span class="edge-label">Huge page splinting</span><span class="edge-desc">A 2 MiB THP can be split back to 4 KiB pages under memory pressure; the split op</span></div><div class="edge-row"><span class="edge-label">Stack overflow</span><span class="edge-desc">The stack VMA grows down; if a process exhausts its `RLIMIT_STACK`, the page fau</span></div><div class="edge-row"><span class="edge-label">`mmap_lock` contention</span><span class="edge-desc">The `mmap_lock` (formerly `mmap_sem`) is a per-process read-write semaphore; und</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c1_10" data-cat="1" style="--hue:210">
<div class="card-head" onclick="toggleCard('c1_10')">
<div class="ch-left">
<span class="item-num">1.10</span>
<div class="ch-titles">
<h3 class="item-title">VFS (Virtual Filesystem Switch) Core Layer</h3>
<p class="item-def-short">The VFS is the kernel's filesystem-independent abstraction layer.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c1_10','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c1_10','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The VFS is the kernel's filesystem-independent abstraction layer.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A syscall like `open(path, flags)` → `do_sys_open()` → …</span><span class="step-chip">`path_openat()` performs pathname resolution via `walk_…</span><span class="step-chip">On cache miss, the filesystem's `inode_operations->look…</span><span class="step-chip">`vfs_open()` checks permissions via `inode_permission()…</span><span class="step-chip">A `struct file` is allocated and `f->f_op` is set from …</span><span class="step-chip">`f->f_op->open(inode, file)` is called (filesystem-spec…</span><span class="step-chip">A file descriptor is allocated and placed in the proces…</span><span class="step-chip">Subsequent `read(fd)` / `write(fd)` calls are dispatche…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Dentry cache poisoning</span><span class="edge-desc">If a filesystem returns a negative dentry for a path, cached "file not found" an</span></div><div class="edge-row"><span class="edge-label">`O_NOFOLLOW` + symlink race (TOCTOU)</span><span class="edge-desc">Between the permission check and the open, a symlink can be replaced; `O_PATH` a</span></div><div class="edge-row"><span class="edge-label">File descriptor table exhaustion</span><span class="edge-desc">Opening files without closing them exhausts the per-process `RLIMIT_NOFILE` limi</span></div><div class="edge-row"><span class="edge-label">Stale NFS handles</span><span class="edge-desc">For NFS-backed filesystems, a dentry can reference a file that has been deleted </span></div></div>
</div>
</div>
</div>
</div>
<div class="cat-divider" id="cat2" data-cat="2">
<span class="cdiv-icon" style="background:hsl(265,70%,18%);color:hsl(265,80%,65%)">🔒</span>
<h2 class="cdiv-title">S2 — Synchronization Primitives</h2>
<span class="cdiv-badge">10 components</span>
</div>
<div class="card" id="c2_1" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_1')">
<div class="ch-left">
<span class="item-num">2.1</span>
<div class="ch-titles">
<h3 class="item-title">Spinlock (`arch/x86/include/asm/spinlock.h`, `kernel/locking/spinlock.c`)</h3>
<p class="item-def-short">A spinlock is a busy-wait mutual exclusion primitive for use in contexts where sleeping is prohibited (interrupt hand…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_1','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_1','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A spinlock is a busy-wait mutual exclusion primitive for use in contexts where sleeping is prohibited (interrupt hand…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`spin_lock(&lk)` calls `raw_spin_lock()`.</span><span class="step-chip">On x86 with `CONFIG_QUEUED_SPINLOCKS`: the lock byte is…</span><span class="step-chip">If locked: the CPU enters a `PAUSE`-instruction loop, r…</span><span class="step-chip">Once acquired, preemption is implicitly disabled (or ex…</span><span class="step-chip">The critical section executes.</span><span class="step-chip">`spin_unlock(&lk)` atomically increments the lock's ser…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Deadlock on same CPU</span><span class="edge-desc">Attempting to acquire a spinlock already held on the same CPU (without `spin_try</span></div><div class="edge-row"><span class="edge-label">Lock held across sleep</span><span class="edge-desc">If code holding a spinlock calls any function that may sleep (e.g., `kmalloc(GFP</span></div><div class="edge-row"><span class="edge-label">Interrupt nesting</span><span class="edge-desc">Failing to use `spin_lock_irqsave()` in interrupt-context code can allow IRQ re-</span></div><div class="edge-row"><span class="edge-label">Cache line bouncing</span><span class="edge-desc">Under high contention on NUMA systems, the lock byte bounces between CPU caches,</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_2" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_2')">
<div class="ch-left">
<span class="item-num">2.2</span>
<div class="ch-titles">
<h3 class="item-title">Mutex (`kernel/locking/mutex.c`)</h3>
<p class="item-def-short">A mutex (MUTual EXclusion) is a sleeping lock for process context.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_2','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_2','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A mutex (MUTual EXclusion) is a sleeping lock for process context.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`mutex_lock(&m)` calls `__mutex_lock()`.</span><span class="step-chip">An optimistic fast-path: atomic CAS on `m->owner`; if t…</span><span class="step-chip">, it is set to the current task pointer, and the lock i…</span><span class="step-chip">Mid-path (OSQ — Optimistic Spinning Queue): if the owne…</span><span class="step-chip">Slow-path: the task is added to `m->wait_list`, sets it…</span><span class="step-chip">When the current owner calls `mutex_unlock()`, it clear…</span><span class="step-chip">The woken task re-attempts the fast-path; on success, i…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Priority inversion</span><span class="edge-desc">A low-priority task holding a mutex blocks a high-priority task; the kernel's PI</span></div><div class="edge-row"><span class="edge-label">Self-deadlock detection</span><span class="edge-desc">`CONFIG_DEBUG_MUTEXES` enables lock validation; a task acquiring a mutex it alre</span></div><div class="edge-row"><span class="edge-label">`mutex_lock_interruptible()` early return</span><span class="edge-desc">If a signal arrives while waiting, the call returns `-EINTR`; the caller must ha</span></div><div class="edge-row"><span class="edge-label">Livelock (OSQ)</span><span class="edge-desc">In degenerate cases, the optimistic spinning phase can consume excessive CPU on </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_3" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_3')">
<div class="ch-left">
<span class="item-num">2.3</span>
<div class="ch-titles">
<h3 class="item-title">Read-Write Semaphore (`kernel/locking/rwsem.c`)</h3>
<p class="item-def-short">An `rwsem` allows multiple concurrent readers or a single exclusive writer.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_3','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_3','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">An `rwsem` allows multiple concurrent readers or a single exclusive writer.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">**Read lock**: `down_read(&sem)` → fast-path: atomicall…</span><span class="step-chip">If a writer is pending, the reader enqueues to `wait_li…</span><span class="step-chip">**Write lock**: `down_write(&sem)` → sets the `RWSEM_WR…</span><span class="step-chip">If readers are active, the writer OSQ-spins briefly, th…</span><span class="step-chip">The writer sleeps until all active readers call `up_rea…</span><span class="step-chip">Last active reader calling `up_read()` checks for waiti…</span><span class="step-chip">When the writer calls `up_write()`, it clears the write…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Writer starvation</span><span class="edge-desc">A continuous stream of readers can prevent a writer from ever acquiring the lock</span></div><div class="edge-row"><span class="edge-label">Downgrade race</span><span class="edge-desc">`downgrade_write()` converts a held write lock to a read lock; if done incorrect</span></div><div class="edge-row"><span class="edge-label">`mmap_lock` scale issue</span><span class="edge-desc">The `mmap_lock` is an `rwsem`; on heavily multithreaded workloads (e.g., many co</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_4" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_4')">
<div class="ch-left">
<span class="item-num">2.4</span>
<div class="ch-titles">
<h3 class="item-title">RCU (Read-Copy-Update) (`kernel/rcu/`)</h3>
<p class="item-def-short">RCU is a synchronization mechanism that allows multiple readers to access shared data concurrently with writers, with…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_4','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_4','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">RCU is a synchronization mechanism that allows multiple readers to access shared data concurrently with writers, with…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Reader: `rcu_read_lock()` disables preemption (or marks…</span><span class="step-chip">Reader dereferences an RCU-protected pointer via `rcu_d…</span><span class="step-chip">Reader reads the data; `rcu_read_unlock()` re-enables p…</span><span class="step-chip">Writer: allocates a new version of the data, copies and…</span><span class="step-chip">Writer calls `synchronize_rcu()` (or `call_rcu(&old_dat…</span><span class="step-chip">`synchronize_rcu()` waits for a grace period: it blocks…</span><span class="step-chip">After the grace period, the old data is safe to free.</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Grace period stall</span><span class="edge-desc">A CPU stuck in a long RCU read-side critical section (e.g., with preemption disa</span></div><div class="edge-row"><span class="edge-label">`rcu_dereference()` outside read-side</span><span class="edge-desc">Dereferencing an RCU pointer outside `rcu_read_lock()` can read a pointer to fre</span></div><div class="edge-row"><span class="edge-label">Expedited RCU side effects</span><span class="edge-desc">`synchronize_rcu_expedited()` forcibly preempts CPUs to accelerate the grace per</span></div><div class="edge-row"><span class="edge-label">SRCU (Sleepable RCU) deadlock</span><span class="edge-desc">Unlike regular RCU, `srcu_read_lock()` can sleep; calling blocking operations in</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_5" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_5')">
<div class="ch-left">
<span class="item-num">2.5</span>
<div class="ch-titles">
<h3 class="item-title">Seqlock (`include/linux/seqlock.h`)</h3>
<p class="item-def-short">A seqlock (sequence lock) is an optimistic concurrency primitive designed for data that is written rarely but read ve…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_5','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_5','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A seqlock (sequence lock) is an optimistic concurrency primitive designed for data that is written rarely but read ve…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Reader: calls `read_seqbegin(&sl)` → reads and returns …</span><span class="step-chip">Reader reads the shared data (non-atomically, without l…</span><span class="step-chip">Reader calls `read_seqretry(&sl, seq)` → reads the coun…</span><span class="step-chip">4. Writer: calls `write_seqlock(&sl)` → acquires the em…</span><span class="step-chip">Writer modifies the shared data.</span><span class="step-chip">Writer calls `write_sequnlock(&sl)` → atomically increm…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Livelock</span><span class="edge-desc">Under a very high writer rate, readers may never see a stable (even) sequence va</span></div><div class="edge-row"><span class="edge-label">Non-retryable operations in reader</span><span class="edge-desc">If a reader performs side-effecting operations (e.g., memory allocation) inside </span></div><div class="edge-row"><span class="edge-label">Large critical sections</span><span class="edge-desc">The kernel's `jiffies` and `timekeeper` use seqlocks; if the writer (clock inter</span></div><div class="edge-row"><span class="edge-label">Pointer dereference hazard</span><span class="edge-desc">Reading a pointer under a seqlock and then dereferencing it after the read windo</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_6" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_6')">
<div class="ch-left">
<span class="item-num">2.6</span>
<div class="ch-titles">
<h3 class="item-title">Completion (`kernel/sched/completion.c`)</h3>
<p class="item-def-short">A completion is a one-shot or multi-shot synchronization object that allows one task to wait for another to signal "d…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_6','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_6','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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 class="sub">Atomically checks <code>done.done</code>; if non-zero, decrements and returns immediately.</li>
<li class="sub">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 class="sub">Calls <code>schedule()</code>; the task sleeps.</li>
<li>The signaling task calls <code>complete(&done)</code>:</li>
<li class="sub">Increments <code>done.done</code>.</li>
<li class="sub">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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A completion is a one-shot or multi-shot synchronization object that allows one task to wait for another to signal "d…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A completion is initialized: `init_completion(&done)` →…</span><span class="step-chip">The waiting task calls `wait_for_completion(&done)`:</span><span class="step-chip">The signaling task calls `complete(&done)`:</span><span class="step-chip">The sleeping task resumes from `schedule()`, re-checks …</span><span class="step-chip">For broadcast wakeup: `complete_all(&done)` sets `done.…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">`complete()` before `wait_for_completion()`</span><span class="edge-desc">This is safe; the `done` counter records the signal and the later `wait_for_comp</span></div><div class="edge-row"><span class="edge-label">`complete()` without a waiter</span><span class="edge-desc">The `done` counter accumulates; if `wait_for_completion()` is never called, the </span></div><div class="edge-row"><span class="edge-label">`wait_for_completion_killable()` early return</span><span class="edge-desc">A fatal signal causes the function to return `-ERESTARTSYS`; the caller must han</span></div><div class="edge-row"><span class="edge-label">Re-initialization race</span><span class="edge-desc">Calling `init_completion()` while another task is blocked in `wait_for_completio</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_7" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_7')">
<div class="ch-left">
<span class="item-num">2.7</span>
<div class="ch-titles">
<h3 class="item-title">Atomic Operations (`arch/x86/include/asm/atomic.h`)</h3>
<p class="item-def-short">Atomic operations provide CPU-guaranteed read-modify-write operations on integer values (`atomic_t`, `atomic64_t`, `a…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_7','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_7','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">Atomic operations provide CPU-guaranteed read-modify-write operations on integer values (`atomic_t`, `atomic64_t`, `a…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A variable is declared: `atomic_t refcount = ATOMIC_INI…</span><span class="step-chip">`.</span><span class="step-chip">`atomic_inc(&refcount)` compiles to a `LOCK ADDL $1, (m…</span><span class="step-chip">`atomic_dec_and_test(&refcount)` compiles to `LOCK DECL…</span><span class="step-chip">`atomic_cmpxchg(&v, old, new)` → `LOCK CMPXCHG` — atomi…</span><span class="step-chip">Memory ordering variants: `atomic_read()` is a plain lo…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">ABA problem</span><span class="edge-desc">`atomic_cmpxchg()` succeeds even if the value was changed to `A`, then back to `</span></div><div class="edge-row"><span class="edge-label">Overflow/underflow</span><span class="edge-desc">`atomic_t` is a 32-bit counter; overflow wraps silently. Use `refcount_t` (which</span></div><div class="edge-row"><span class="edge-label">`refcount_t` saturation</span><span class="edge-desc">The kernel's `refcount_t` saturates at INT_MAX to prevent integer overflow bugs </span></div><div class="edge-row"><span class="edge-label">Non-atomic accesses on 64-bit counters (32-bit CPUs)</span><span class="edge-desc">On 32-bit kernels, `atomic64_t` operations require a lock (emulated) because 64-</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_8" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_8')">
<div class="ch-left">
<span class="item-num">2.8</span>
<div class="ch-titles">
<h3 class="item-title">Per-CPU Variables (`include/linux/percpu.h`, `mm/percpu.c`)</h3>
<p class="item-def-short">Per-CPU variables are instances of data duplicated once per logical CPU, stored in CPU-local memory regions, and acce…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_8','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_8','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">Per-CPU variables are instances of data duplicated once per logical CPU, stored in CPU-local memory regions, and acce…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A per-CPU variable is declared: `DEFINE_PER_CPU(unsigne…</span><span class="step-chip">At boot, `setup_per_cpu_areas()` allocates a contiguous…</span><span class="step-chip">Access: `get_cpu_var(mycounter)` disables preemption an…</span><span class="step-chip">.</span><span class="step-chip">The variable is modified.</span><span class="step-chip">`put_cpu_var(mycounter)` re-enables preemption.</span><span class="step-chip">For lockless access (safe only for statistics): `this_c…</span><span class="step-chip">` uses a `LOCK`-free `ADD` via the `this_cpu_*` family …</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Preemption not disabled</span><span class="edge-desc">If preemption is enabled when `this_cpu_ptr()` is used (not inside `get_cpu_var(</span></div><div class="edge-row"><span class="edge-label">Interrupt context access</span><span class="edge-desc">An interrupt handler can preempt code using `this_cpu_ptr()` on the same CPU; bo</span></div><div class="edge-row"><span class="edge-label">Dynamic per-CPU allocation (`alloc_percpu()`)</span><span class="edge-desc">The returned pointer must be freed with `free_percpu()`; a leak causes the per-C</span></div><div class="edge-row"><span class="edge-label">Hotplug CPU offline</span><span class="edge-desc">When a CPU goes offline, its per-CPU data is not automatically migrated; subsyst</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_9" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_9')">
<div class="ch-left">
<span class="item-num">2.9</span>
<div class="ch-titles">
<h3 class="item-title">Futex (`kernel/futex/`)</h3>
<p class="item-def-short">A futex (Fast Userspace muTEX) is a hybrid synchronization primitive: the fast path is a userspace atomic operation o…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_9','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_9','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A futex (Fast Userspace muTEX) is a hybrid synchronization primitive: the fast path is a userspace atomic operation o…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Lock attempt: userspace atomically tries CAS on the fut…</span><span class="step-chip">, the lock is acquired without entering the kernel.</span><span class="step-chip">On contention (word was already</span><span class="step-chip">: the thread sets a "has waiters" bit (word =</span><span class="step-chip">and calls `futex(FUTEX_WAIT, uaddr, expected_val, timeo…</span><span class="step-chip">Kernel: `do_futex()` → `futex_wait()` → computes the ha…</span><span class="step-chip">`futex_wait_setup()` verifies the futex value still equ…</span><span class="step-chip">The task is added to `hb->chain` (hash bucket wait queu…</span><span class="step-chip">Unlock: the unlocking thread atomically clears the word…</span><span class="step-chip">Kernel: `futex_wake()` removes up to `count` waiters fr…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Priority inversion</span><span class="edge-desc">A low-priority holder blocks a high-priority waiter; `FUTEX_LOCK_PI` / `FUTEX_UN</span></div><div class="edge-row"><span class="edge-label">Spurious wakeup</span><span class="edge-desc">A signal delivery wakes the futex waiter before the futex word changes; userspac</span></div><div class="edge-row"><span class="edge-label">`FUTEX_WAIT` / value race</span><span class="edge-desc">Between the userspace CAS failure and the kernel `futex_wait_setup()` check, ano</span></div><div class="edge-row"><span class="edge-label">Robust futex list corruption</span><span class="edge-desc">If a process is killed while holding a robust futex, the kernel walks the robust</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c2_10" data-cat="2" style="--hue:265">
<div class="card-head" onclick="toggleCard('c2_10')">
<div class="ch-left">
<span class="item-num">2.10</span>
<div class="ch-titles">
<h3 class="item-title">Semaphore (`kernel/locking/semaphore.c`)</h3>
<p class="item-def-short">A counting semaphore (`struct semaphore`) allows a specified number of concurrent holders, unlike a mutex (which allo…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c2_10','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c2_10','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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 class="sub">Atomically decrements <code>sem.count</code>.</li>
<li class="sub">If result ≥ 0, returns immediately (resource acquired).</li>
<li class="sub">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 class="sub">Atomically increments <code>sem.count</code>.</li>
<li class="sub">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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A counting semaphore (`struct semaphore`) allows a specified number of concurrent holders, unlike a mutex (which allo…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Initialization: `sema_init(&sem, N)` sets `sem.count = …</span><span class="step-chip">`down(&sem)` → `__down()`:</span><span class="step-chip">`up(&sem)` → `__up()`:</span><span class="step-chip">The woken waiter re-runs from `schedule()` return, veri…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Semaphore released without being acquired</span><span class="edge-desc">Calling `up()` more times than `down()` raises the counter above its initial val</span></div><div class="edge-row"><span class="edge-label">`down_interruptible()` early return</span><span class="edge-desc">Returns `-EINTR` on signal; the caller must handle the case where the resource w</span></div><div class="edge-row"><span class="edge-label">`down_trylock()` busy-wait abuse</span><span class="edge-desc">Using `down_trylock()` in a tight loop is equivalent to spinning and wastes CPU;</span></div><div class="edge-row"><span class="edge-label">Priority inversion (no inheritance)</span><span class="edge-desc">Unlike `rt_mutex`-based locks, the kernel `semaphore` has no priority inheritanc</span></div></div>
</div>
</div>
</div>
</div>
<div class="cat-divider" id="cat3" data-cat="3">
<span class="cdiv-icon" style="background:hsl(145,70%,18%);color:hsl(145,80%,65%)">🧠</span>
<h2 class="cdiv-title">S3 — Memory Allocators</h2>
<span class="cdiv-badge">10 components</span>
</div>
<div class="card" id="c3_1" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_1')">
<div class="ch-left">
<span class="item-num">3.1</span>
<div class="ch-titles">
<h3 class="item-title">Buddy Allocator (`mm/page_alloc.c`)</h3>
<p class="item-def-short">The buddy allocator is the kernel's physical page frame manager.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_1','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_1','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The buddy allocator is the kernel's physical page frame manager.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`alloc_pages(gfp_flags, order)` → `__alloc_pages()`.</span><span class="step-chip">`get_page_from_freelist()` iterates memory zones (ZONE_…</span><span class="step-chip">For the target zone, `rmqueue()` checks the free list a…</span><span class="step-chip">If a block of that order is available, it is removed fr…</span><span class="step-chip">If no block at the requested order is available, `rmque…</span><span class="step-chip">If all higher orders are also empty: watermark check fa…</span><span class="step-chip">Physical page address returned as `struct page *`; virt…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">External fragmentation</span><span class="edge-desc">Over time, free memory becomes fragmented into non-contiguous blocks; large-orde</span></div><div class="edge-row"><span class="edge-label">Zone imbalance</span><span class="edge-desc">If `ZONE_DMA32` is exhausted but `ZONE_NORMAL` has free pages, allocations requi</span></div><div class="edge-row"><span class="edge-label">Atomic allocation failures (`GFP_ATOMIC`)</span><span class="edge-desc">Atomic allocations cannot sleep or reclaim; they draw from a reserved "emergency</span></div><div class="edge-row"><span class="edge-label">High-order allocation under pressure</span><span class="edge-desc">A request for order-10 (4 MiB) pages may fail even with gigabytes of free memory</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_2" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_2')">
<div class="ch-left">
<span class="item-num">3.2</span>
<div class="ch-titles">
<h3 class="item-title">SLAB Allocator (`mm/slab.c`)</h3>
<p class="item-def-short">The SLAB allocator (Bonwick 1994, Linux port ~2.0) manages pools of fixed-size kernel objects.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_2','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_2','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The SLAB allocator (Bonwick 1994, Linux port ~2.0) manages pools of fixed-size kernel objects.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`kmem_cache_create("name", object_size, align, flags, c…</span><span class="step-chip">`kmem_cache_alloc(cache, gfp)` → checks the per-CPU cac…</span><span class="step-chip">If per-CPU cache is empty: `cache_alloc_refill()` fills…</span><span class="step-chip">Object initialization: if a constructor (`ctor`) was pr…</span><span class="step-chip">`kmem_cache_free(cache, obj)` returns the object to the…</span><span class="step-chip">When the per-CPU cache overflows its `batchcount`, obje…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Slab poisoning detection</span><span class="edge-desc">With `CONFIG_DEBUG_SLAB`, freed objects are filled with `0x6b` ("k"); a later al</span></div><div class="edge-row"><span class="edge-label">Cache aliasing</span><span class="edge-desc">Multiple `kmem_cache_create()` calls with the same size may or may not share an </span></div><div class="edge-row"><span class="edge-label">Per-CPU cache under/overflow in hot-unplug</span><span class="edge-desc">When a CPU goes offline while its per-CPU cache holds objects, `free_block()` mu</span></div><div class="edge-row"><span class="edge-label">Constructor called on reuse (SLAB only)</span><span class="edge-desc">SLAB's constructor is called only at slab creation, not on each allocation; a co</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_3" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_3')">
<div class="ch-left">
<span class="item-num">3.3</span>
<div class="ch-titles">
<h3 class="item-title">SLUB Allocator (`mm/slub.c`)</h3>
<p class="item-def-short">SLUB (SLab Unqueued Bookkeeping) is the default slab allocator since Linux 2.6.23.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_3','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_3','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">SLUB (SLab Unqueued Bookkeeping) is the default slab allocator since Linux 2.6.23.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`kmem_cache_alloc(s, gfp)` → reads `s->cpu_slab->freeli…</span><span class="step-chip">Fast path: if `freelist` is non-NULL, pops the first fr…</span><span class="step-chip">Slow path (`__slab_alloc()`): if the CPU slab is empty,…</span><span class="step-chip">If no partial slabs: allocates a new slab of pages from…</span><span class="step-chip">`kmem_cache_free(s, obj)` → `do_slab_free()`: pushes `o…</span><span class="step-chip">When the CPU slab becomes fully free, it is returned to…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Double-free detection</span><span class="edge-desc">SLUB stores a "freelist pointer" XOR'd with a secret in the object itself (`CONF</span></div><div class="edge-row"><span class="edge-label">Redzone overwrite</span><span class="edge-desc">`CONFIG_SLUB_DEBUG` adds redzones around objects; buffer overflows into the redz</span></div><div class="edge-row"><span class="edge-label">Quarantine (KASAN)</span><span class="edge-desc">Kernel Address Sanitizer delays reuse of freed SLUB objects; a use-after-free th</span></div><div class="edge-row"><span class="edge-label">NUMAism</span><span class="edge-desc">SLUB maintains per-node partial lists; on NUMA systems, allocating from a remote</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_4" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_4')">
<div class="ch-left">
<span class="item-num">3.4</span>
<div class="ch-titles">
<h3 class="item-title">SLOB Allocator (`mm/slob.c`)</h3>
<p class="item-def-short">SLOB (Simple List Of Blocks) is a compact allocator designed for systems with very limited memory (embedded, tiny IoT…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_4','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_4','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">SLOB (Simple List Of Blocks) is a compact allocator designed for systems with very limited memory (embedded, tiny IoT…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`kmalloc(size, gfp)` with SLOB selects one of three fre…</span><span class="step-chip">`slob_alloc(size, gfp, align, node)` acquires `slob_loc…</span><span class="step-chip">First-fit: finds the first free block ≥ requested size.</span><span class="step-chip">If the block is significantly larger, it is split: the …</span><span class="step-chip">If no fit found: `slob_new_pages()` allocates a new pag…</span><span class="step-chip">`kfree(obj)` → `slob_free()` acquires `slob_lock`, inse…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Global lock bottleneck</span><span class="edge-desc">The single `slob_lock` serializes all allocations and frees; SLOB is entirely un</span></div><div class="edge-row"><span class="edge-label">Fragmentation (no compaction)</span><span class="edge-desc">SLOB has no per-slab concept; fragmentation accumulates and is never compacted, </span></div><div class="edge-row"><span class="edge-label">No NUMA awareness</span><span class="edge-desc">SLOB is unaware of NUMA topology; all allocations come from the same free list r</span></div><div class="edge-row"><span class="edge-label">Deprecation path</span><span class="edge-desc">SLOB was removed from mainline Linux in kernel 6.4 (`CONFIG_SLOB` removed); code</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_5" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_5')">
<div class="ch-left">
<span class="item-num">3.5</span>
<div class="ch-titles">
<h3 class="item-title">`vmalloc` / `vmap` (`mm/vmalloc.c`)</h3>
<p class="item-def-short">`vmalloc()` allocates virtually contiguous but physically discontiguous memory by mapping individual (potentially non…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_5','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_5','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">`vmalloc()` allocates virtually contiguous but physically discontiguous memory by mapping individual (potentially non…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`vmalloc(size)` → `__vmalloc_node()`.</span><span class="step-chip">A `vm_struct` is allocated (describes the virtual range…</span><span class="step-chip">`get_vm_area_caller()` finds a gap in the vmalloc addre…</span><span class="step-chip">For each page in the allocation: `alloc_page(GFP_KERNEL…</span><span class="step-chip">from the buddy allocator.</span><span class="step-chip">`map_kernel_range()` / `vmap_pages_range()` establishes…</span><span class="step-chip">`flush_cache_vmap()` flushes TLB entries for the new ma…</span><span class="step-chip">Returns the virtual address of the start of the mapping…</span><span class="step-chip">`vfree(addr)` unmaps page tables, frees each physical p…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">vmalloc space exhaustion</span><span class="edge-desc">The vmalloc area is finite (128 TiB on x86-64 by default); a leak of `vm_struct`</span></div><div class="edge-row"><span class="edge-label">TLB shootdown cost</span><span class="edge-desc">Each `vfree()` requires an IPI to all CPUs to flush TLB entries for the freed ra</span></div><div class="edge-row"><span class="edge-label">Non-contiguous physical pages</span><span class="edge-desc">Drivers that use `vmalloc()`-allocated buffers for DMA must use scatter-gather l</span></div><div class="edge-row"><span class="edge-label">`vmap()` on highmem pages (32-bit kernels)</span><span class="edge-desc">Mapping `ZONE_HIGHMEM` pages via `vmap()` is the standard way to access them on </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_6" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_6')">
<div class="ch-left">
<span class="item-num">3.6</span>
<div class="ch-titles">
<h3 class="item-title">`kmalloc` / `kfree` (`include/linux/slab.h`)</h3>
<p class="item-def-short">`kmalloc(size, gfp_flags)` is the primary general-purpose kernel small-object allocator.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_6','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_6','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">`kmalloc(size, gfp_flags)` is the primary general-purpose kernel small-object allocator.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`kmalloc(size, gfp)` → `__kmalloc()`.</span><span class="step-chip">`kmalloc_slab(size, gfp)` looks up the appropriate `kme…</span><span class="step-chip">If size is 0, returns `ZERO_SIZE_PTR` (a non-NULL magic…</span><span class="step-chip">If size > `KMALLOC_MAX_CACHE_SIZE` (typically 8 KiB on …</span><span class="step-chip">Otherwise: `kmem_cache_alloc(cache, gfp)` is called on …</span><span class="step-chip">`kfree(ptr)` → `__kfree()`: uses `virt_to_head_page()` …</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Size rounding waste</span><span class="edge-desc">An allocation of 33 bytes uses the 64-byte cache, wasting 31 bytes; for performa</span></div><div class="edge-row"><span class="edge-label">GFP flag misuse</span><span class="edge-desc">Using `GFP_KERNEL` (may sleep/reclaim) in atomic context (IRQ handler, spinlock </span></div><div class="edge-row"><span class="edge-label">`kfree()` on a stack pointer or non-kmalloc memory</span><span class="edge-desc">SLUB's `kfree()` uses `virt_to_head_page()` to verify the pointer is slab-manage</span></div><div class="edge-row"><span class="edge-label">Speculative failure under pressure</span><span class="edge-desc">Even `GFP_KERNEL` allocations can fail under extreme memory pressure if the OOM </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_7" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_7')">
<div class="ch-left">
<span class="item-num">3.7</span>
<div class="ch-titles">
<h3 class="item-title">Memory Pool (`mm/mempool.c`)</h3>
<p class="item-def-short">A mempool is a reserved pool of pre-allocated objects that guarantees allocation success even under extreme memory pr…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_7','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_7','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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 class="sub">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 class="sub">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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">A mempool is a reserved pool of pre-allocated objects that guarantees allocation success even under extreme memory pr…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`mempool_create(min_nr, alloc_fn, free_fn, pool_data)` …</span><span class="step-chip">`mempool_alloc(pool, gfp)` first tries the underlying a…</span><span class="step-chip">If the allocator succeeds, the reserved pool is untouch…</span><span class="step-chip">If the allocator fails and `gfp & __GFP_DIRECT_RECLAIM`…</span><span class="step-chip">If the pool's `elements[]` array is non-empty, an eleme…</span><span class="step-chip">If both the allocator and pool are empty and `GFP_NOIO`…</span><span class="step-chip">`mempool_free(element, pool)`:</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Pool size insufficient for deadlock avoidance</span><span class="edge-desc">If the pool size is too small and all elements are in-flight simultaneously, a n</span></div><div class="edge-row"><span class="edge-label">`mempool_alloc` with `GFP_NOIO` returning NULL</span><span class="edge-desc">Callers in the I/O stack must handle NULL explicitly; most DM/bio code treats th</span></div><div class="edge-row"><span class="edge-label">Pool element leak</span><span class="edge-desc">If code acquires an element from a mempool and returns an error without calling </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_8" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_8')">
<div class="ch-left">
<span class="item-num">3.8</span>
<div class="ch-titles">
<h3 class="item-title">CMA (Contiguous Memory Allocator) (`mm/cma.c`)</h3>
<p class="item-def-short">CMA reserves contiguous physical memory regions at boot time (via `cma=` kernel parameter or device tree `reserved-me…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_8','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_8','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">CMA reserves contiguous physical memory regions at boot time (via `cma=` kernel parameter or device tree `reserved-me…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">At boot: `cma_declare_contiguous()` marks a physical ra…</span><span class="step-chip">`dma_alloc_contiguous()` → `cma_alloc(cma, count, align…</span><span class="step-chip">`alloc_contig_range()` tries to isolate the requested p…</span><span class="step-chip">`start_isolate_page_range()` changes the migration type…</span><span class="step-chip">`migrate_pages()` moves all currently-allocated movable…</span><span class="step-chip">If migration succeeds, the range is allocated contiguou…</span><span class="step-chip">`cma_release()` → `free_contig_range()` returns the pag…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Migration failure</span><span class="edge-desc">If a page in the requested range cannot be migrated (pinned, locked, or of a non</span></div><div class="edge-row"><span class="edge-label">CMA fragmentation over time</span><span class="edge-desc">Long-running systems may pin non-movable pages inside the CMA region (via `get_u</span></div><div class="edge-row"><span class="edge-label">CMA size reservation vs. DMA size</span><span class="edge-desc">If the CMA region is smaller than the device's DMA buffer requirement, the alloc</span></div><div class="edge-row"><span class="edge-label">Early CMA allocation before migration is ready</span><span class="edge-desc">During early boot (before `mem_init()`), page migration is not available; CMA re</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_9" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_9')">
<div class="ch-left">
<span class="item-num">3.9</span>
<div class="ch-titles">
<h3 class="item-title">Transparent Huge Pages (THP) (`mm/huge_memory.c`)</h3>
<p class="item-def-short">THP automatically promotes 4 KiB pages to 2 MiB huge pages (on x86-64) when a process's anonymous mappings are large …</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_9','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_9','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">THP automatically promotes 4 KiB pages to 2 MiB huge pages (on x86-64) when a process's anonymous mappings are large …</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">A process `mmap()`s a large anonymous region.</span><span class="step-chip">Initial page faults allocate 4 KiB pages normally.</span><span class="step-chip">`khugepaged` wakes periodically, scans `mm_struct` page…</span><span class="step-chip">`collapse_huge_page()` allocates a 2 MiB physically con…</span><span class="step-chip">`copy_page()` copies all 512 small pages into the new h…</span><span class="step-chip">The PMD entry is replaced with a huge-page PMD pointing…</span><span class="step-chip">The 512 original small pages are released to the buddy …</span><span class="step-chip">Future page faults in the region use the PMD-level huge…</span><span class="step-chip">On split (e.g., due to `mprotect()`, `mremap()`, or mem…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">THP allocation failure</span><span class="edge-desc">The order-9 allocation may fail under memory pressure; `khugepaged` retries late</span></div><div class="edge-row"><span class="edge-label">THP split under swap pressure</span><span class="edge-desc">If the system needs to swap out part of a THP region, the huge page must be spli</span></div><div class="edge-row"><span class="edge-label">THP in `mlock()`'d regions</span><span class="edge-desc">Locking a region prevents `khugepaged` from collapsing it; the interaction betwe</span></div><div class="edge-row"><span class="edge-label">False sharing amplification</span><span class="edge-desc">A 2 MiB THP means a write to any page in the region dirtifies the entire 2 MiB; </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c3_10" data-cat="3" style="--hue:145">
<div class="card-head" onclick="toggleCard('c3_10')">
<div class="ch-left">
<span class="item-num">3.10</span>
<div class="ch-titles">
<h3 class="item-title">Per-CPU Allocator (`mm/percpu.c`)</h3>
<p class="item-def-short">The per-CPU allocator manages the per-CPU memory areas created at boot time (and dynamically via `alloc_percpu()`).</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c3_10','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c3_10','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The per-CPU allocator manages the per-CPU memory areas created at boot time (and dynamically via `alloc_percpu()`).</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">At boot: `pcpu_setup_first_chunk()` carves out per-CPU …</span><span class="step-chip">`alloc_percpu(type)` → `__alloc_percpu(size, align)`.</span><span class="step-chip">`pcpu_alloc()` acquires `pcpu_lock` and searches for a …</span><span class="step-chip">If no space in existing chunks: `pcpu_create_chunk()` a…</span><span class="step-chip">The allocated offset is stored; the returned `__percpu …</span><span class="step-chip">`per_cpu_ptr(ptr, cpu)` → `(void *)((unsigned long)(ptr…</span><span class="step-chip">`free_percpu(ptr)` returns the offset to the chunk's fr…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Early boot allocation before `__per_cpu_offset` is set</span><span class="edge-desc">Accessing per-CPU data before `setup_per_cpu_areas()` completes reads garbage; a</span></div><div class="edge-row"><span class="edge-label">Module per-CPU allocation failure</span><span class="edge-desc">If `alloc_percpu()` fails during module load, the module's `init()` must free al</span></div><div class="edge-row"><span class="edge-label">CPU offline drain</span><span class="edge-desc">When a CPU goes offline, any data accumulated in its per-CPU allocator slab cach</span></div><div class="edge-row"><span class="edge-label">Cache line alignment</span><span class="edge-desc">The per-CPU allocator aligns allocations to `SMP_CACHE_BYTES` (typically 64 B); </span></div></div>
</div>
</div>
</div>
</div>
<div class="cat-divider" id="cat4" data-cat="4">
<span class="cdiv-icon" style="background:hsl(30,70%,18%);color:hsl(30,80%,65%)">📅</span>
<h2 class="cdiv-title">S4 — Process & CPU Schedulers</h2>
<span class="cdiv-badge">10 components</span>
</div>
<div class="card" id="c4_1" data-cat="4" style="--hue:30">
<div class="card-head" onclick="toggleCard('c4_1')">
<div class="ch-left">
<span class="item-num">4.1</span>
<div class="ch-titles">
<h3 class="item-title">CFS (Completely Fair Scheduler) (`kernel/sched/fair.c`)</h3>
<p class="item-def-short">CFS is the default scheduler for normal (non-real-time) tasks in Linux, implementing SCHED_NORMAL and SCHED_BATCH pol…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c4_1','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c4_1','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">CFS is the default scheduler for normal (non-real-time) tasks in Linux, implementing SCHED_NORMAL and SCHED_BATCH pol…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Task enqueueing: `enqueue_task_fair()` adds the `sched_…</span><span class="step-chip">Task selection: `pick_next_task_fair()` returns the `sc…</span><span class="step-chip">The selected task's `vruntime` is advanced by `calc_del…</span><span class="step-chip">`update_curr()` is called on each tick (via `task_tick_…</span><span class="step-chip">Preemption check: if the minimum `vruntime` on the RB t…</span><span class="step-chip">On the next kernel exit or `schedule()` call, `pick_nex…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">vruntime overflow</span><span class="edge-desc">After long uptime, 64-bit `vruntime` could theoretically overflow; it doesn't in</span></div><div class="edge-row"><span class="edge-label">Newly woken task vruntime placement</span><span class="edge-desc">A sleeping task's `vruntime` is not advanced; on wake, it is set to `max(task->v</span></div><div class="edge-row"><span class="edge-label">Group scheduling (cgroups) complexity</span><span class="edge-desc">With CPU cgroups, CFS uses a hierarchical scheduler entity (`sched_entity` trees</span></div><div class="edge-row"><span class="edge-label">Latency target vs. throughput</span><span class="edge-desc">With many tasks, `sysctl_sched_latency` is spread over `nr_running` tasks; each </span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c4_2" data-cat="4" style="--hue:30">
<div class="card-head" onclick="toggleCard('c4_2')">
<div class="ch-left">
<span class="item-num">4.2</span>
<div class="ch-titles">
<h3 class="item-title">RT Scheduler (`kernel/sched/rt.c`)</h3>
<p class="item-def-short">The real-time scheduler implements `SCHED_FIFO` and `SCHED_RR` policies.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c4_2','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c4_2','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The real-time scheduler implements `SCHED_FIFO` and `SCHED_RR` policies.</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">`enqueue_task_rt()` adds the task to the per-priority F…</span><span class="step-chip">`pick_next_task_rt()` calls `pick_next_rt_entity()` → f…</span><span class="step-chip">The highest-priority task is returned; if multiple task…</span><span class="step-chip">`task_tick_rt()` runs on each tick; for `SCHED_RR`, dec…</span><span class="step-chip">For `SCHED_FIFO`, the task runs until it blocks, yields…</span><span class="step-chip">`dequeue_task_rt()` removes the task from the bitmap/qu…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">RT bandwidth throttling</span><span class="edge-desc">Without `CONFIG_RT_GROUP_SCHED`, a single SCHED_FIFO task at priority 99 can sta</span></div><div class="edge-row"><span class="edge-label">Priority inversion in RT</span><span class="edge-desc">An RT task blocked waiting for a resource held by a CFS task may be delayed inde</span></div><div class="edge-row"><span class="edge-label">Missed SCHED_RR timeslice reset</span><span class="edge-desc">On `fork()`, the child inherits the parent's remaining timeslice, not a fresh 10</span></div><div class="edge-row"><span class="edge-label">Migration to wrong CPU</span><span class="edge-desc">Under `RT_GROUP_SCHED`, pull/push migrations of RT tasks must respect CPU affini</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c4_3" data-cat="4" style="--hue:30">
<div class="card-head" onclick="toggleCard('c4_3')">
<div class="ch-left">
<span class="item-num">4.3</span>
<div class="ch-titles">
<h3 class="item-title">Deadline Scheduler (`kernel/sched/deadline.c`)</h3>
<p class="item-def-short">The deadline scheduler implements `SCHED_DEADLINE` policy based on the Earliest Deadline First (EDF) algorithm with C…</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c4_3','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c4_3','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class="view-mdl" style="display:none">
<div class="mdl-row">
<span class="mdl-label">DEF</span>
<span class="mdl-def">The deadline scheduler implements `SCHED_DEADLINE` policy based on the Earliest Deadline First (EDF) algorithm with C…</span>
</div>
<div class="mdl-row">
<span class="mdl-label">FLOW</span>
<div class="steps-wrap"><span class="step-chip">Task admission: `dl_overflow()` checks that adding the …</span><span class="step-chip">`enqueue_task_dl()` inserts the task's `sched_dl_entity…</span><span class="step-chip">`pick_next_task_dl()` returns the leftmost node (earlie…</span><span class="step-chip">During execution: `update_dl_task_contention()` deplete…</span><span class="step-chip">When runtime is exhausted before the deadline, the task…</span><span class="step-chip">At period start, the runtime is replenished and the tas…</span><span class="step-chip">When the absolute deadline passes (task completes): `de…</span></div>
</div>
<div class="mdl-row">
<span class="mdl-label">EDGE</span>
<div class="edges-wrap"><div class="edge-row"><span class="edge-label">Admission control race</span><span class="edge-desc">Two simultaneous `sched_setattr()` calls for two tasks may each pass the capacit</span></div><div class="edge-row"><span class="edge-label">Missed deadline (overrun)</span><span class="edge-desc">CBS guarantees no deadline miss for tasks meeting their parameters; if a task's </span></div><div class="edge-row"><span class="edge-label">`SCHED_DEADLINE` task on a cgroup-constrained CPU</span><span class="edge-desc">If the CPU's available capacity is reduced by cpuset/cgroup constraints, the uti</span></div><div class="edge-row"><span class="edge-label">Priority boosting interaction</span><span class="edge-desc">A deadline task boosting a mutex-holding CFS task (via PI) adds unbounded latenc</span></div></div>
</div>
</div>
</div>
</div>
<div class="card" id="c4_4" data-cat="4" style="--hue:30">
<div class="card-head" onclick="toggleCard('c4_4')">
<div class="ch-left">
<span class="item-num">4.4</span>
<div class="ch-titles">
<h3 class="item-title">Idle Scheduler (`kernel/sched/idle.c`)</h3>
<p class="item-def-short">The idle scheduler runs the special `idle` task (PID 0, one per CPU) when no other runnable task exists.</p>
</div>
</div>
<span class="ch-toggle">▾</span>
</div>
<div class="card-body">
<div class="view-tabs">
<button class="vtab active" onclick="switchView(this,'c4_4','full')">Full</button>
<button class="vtab" onclick="switchView(this,'c4_4','mdl')">MDL Compact</button>
</div>
<div class="view-full view-active">
<section class="field">
<h4 class="field-lbl lbl-def">Definition</h4>
<div class="field-body"><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-lbl lbl-flow">Execution Flow</h4>
<div class="field-body"><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-lbl lbl-edge">Edge Cases & Failure Modes</h4>
<div class="field-body"><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 class
… (truncated — use Raw)