1. Overview

When the kernel boots it uses the e820 memory map (x86) or Device Tree /memory nodes (ARM) to learn which physical address ranges are usable RAM. It then builds a three-level hierarchy: NUMA nodes → zones → page frames. Each 4 KB page frame gets one struct page descriptor stored in a contiguous array called mem_map. The buddy allocator manages free blocks within each zone using power-of-2 free lists — splitting large blocks when allocating and coalescing adjacent buddies when freeing.

2. Key Data Structures

struct page — one per physical frame

The kernel allocates one struct page for every physical page frame at boot. On a 64 GB machine that is 16 million descriptors — about 1 GB of memory just for metadata. The struct is carefully padded to exactly 64 bytes so that a page index directly maps to an array offset.

Memory Zones & Watermarks

Each zone maintains three watermarks — min, low, and high — expressed as page counts. The watermarks control when background reclaim (kswapd) wakes up and when allocators must block for direct reclaim.

Buddy Free Lists

Each zone holds MAX_ORDER (typically 11) free lists, indexed by order. Order k holds blocks of 2^k contiguous pages. A freshly booted machine might have one order-10 block (1024 pages = 4 MB) in ZONE_NORMAL.

3. Core Mechanism — Buddy Allocator Split & Coalesce

Allocation path — alloc_pages()

Background: The kernel frequently needs 1–16 contiguous page frames for kernel stacks, DMA buffers, and slab slabs. A simple bitmap scan would be O(n). The buddy system maintains power-of-2 free lists so that both allocation and freeing are O(log n) — with n = max order.

Plan:

1. Look in free_list[requested_order]. If non-empty, dequeue and return.
2. Walk up to free_list[requested_order + 1], +2, … until a non-empty list is found.
3. Dequeue the large block. Split it in half: lower half goes to the caller; upper half (“buddy”) is added to free_list[k-1].
4. Repeat splitting until the block is exactly the requested order.

Example — allocating order-1 (2 pages) from a pool with only an order-2 block at 0x1000:

Free path — free_pages() — coalescing

Background:Returning a single page back to order-0 causes fragmentation over time. The buddy system coalesces adjacent same-size blocks (“buddies”) on every free, pushing the block up to the highest possible order.

Key insight — buddy address: For a block of size 2^k pages at address addr, the buddy is at addr XOR (1 << (k + PAGE_SHIFT)). Because blocks are power-of-2 aligned, toggling that single bit flips between the block and its buddy.

Anti-fragmentation — migrate types: The buddy system groups pages by mobility within each free list to prevent unmovable pages from fragmenting the pool of movable pages.

4. Minimal C Demo

The demo below implements the core buddy split and coalesce algorithm with a 16-page pool (order-4). The same logic — walk up to find a large-enough block, split down, coalesce on free — is used by the kernel's __rmqueue() and __free_one_page().

The next demo simulates the zone watermark check — the logic inside zone_watermark_ok() that decides whether an allocation can proceed or must wait for reclaim.

5. Kernel Source Pointers

6. Interview Prep

7. Overview — Slab/Slub + Paging

The buddy allocator gives out whole pages (4 KB minimum). But most kernel allocations are tiny: a struct inode is ~600 B, a struct sk_buff is ~232 B. Rounding each up to 4 KB wastes 80–99 % of every allocation. The slab allocator (modern Linux uses SLUB by default) carves each slab page into equal-size objects and keeps a per-CPU freelist — allocation is a single pointer pop, lock-free on the hot path.

Virtual memory adds translation: every load/store goes through a 4-level page table (PGD → PUD → PMD → PTE). A TLB caches recent VA→PA mappings; a miss triggers a hardware walk costing 100–300 cycles. Huge pages (2 MB / 1 GB) cover more address space per TLB entry — the core reason DPDK pins 1 GB pages at startup.

8. Key Data Structures — Slab

kmem_cache — one descriptor per object type

Every slab cache has one kmem_cache descriptor. Linux creates hundreds at boot — inode_cache, skbuff_head_cache, mm_struct, etc. List them with cat /proc/slabinfo.

SLAB vs SLUB vs SLOB

9. Core Mechanism — Slab Allocation Fast & Slow Path

Background: The kernel allocates network buffers, dentries, and inodes millions of times per second. Taking a spinlock on every allocation serializes CPUs. SLUB avoids this with a per-CPU embedded freelist: the first sizeof(void *) bytes of every free object store a pointer to the next free object — so the freelist has zero memory overhead and fast- path alloc/free are both a single pointer update.

Plan:

1. Fast path — check cpu_slab->freelist. If non-NULL: read the embedded next pointer, advance freelist head, return object. No lock, no atomic.
2. Slow path — partial slab — lock node->list_lock, grab a partial slab from the NUMA-node list, set it as the CPU's active slab, unlock, retry fast path.
3. Slow path — new slab — if no partial slab exists, call alloc_pages() to get a fresh page from the buddy allocator, initialize the freelist through all objects in that page, add to node partial list.

Example — allocating 10 sk_buff objects from a fresh cache:

10. Virtual Memory & Paging

4-Level Page Table Walk (x86-64)

x86-64 uses a 4-level page table to map 48-bit virtual addresses to physical frames. The CPU register CR3 holds the physical address of the top-level Page Global Directory (PGD). Each level is a 4 KB page containing 512 8-byte entries — indexed by 9 bits of the VA. On every TLB miss the hardware walker reads all four levels, fills the TLB, and retries the instruction.

TLB — Translation Lookaside Buffer

Walking 4 page-table levels requires 4 memory accesses — up to 4 × 100 ns = 400 ns on a cold cache. The TLB is a small fully-associative hardware cache (64–1024 entries per core) storing recent VA→PA translations. A hit costs 1–4 cycles; a miss triggers the full hardware walk. flush_tlb_mm() invalidates all TLB entries for a process on context switch; on SMP systems a TLB shootdown IPI is sent to remote CPUs.

Huge Pages & TLB Pressure

Transparent Huge Pages (THP) — the khugepaged kernel thread promotes runs of 512 contiguous 4 KB anonymous pages to a single 2 MB page automatically; no application change required. HugeTLBfs — explicit huge pages reserved at boot via hugepages=N or /proc/sys/vm/nr_hugepages. DPDK calls rte_eal_init() which uses mmap(MAP_HUGETLB) to pin 1 GB pages, guaranteeing TLB entries are never evicted for the lifetime of the application.

11. Minimal C Demo

The first demo implements the SLUB embedded-freelist pattern. Every free object stores its "next free" pointer in its own first bytes — freelist overhead is zero, and alloc/free are each a single pointer update.

The second demo extracts each page-table index from a 48-bit virtual address — the same decomposition the hardware page walker performs on every TLB miss.

12. Kernel Source Pointers

13. Interview Prep

14. Overview

Every Linux process has its own virtual address space described by a struct mm_struct. Within that space, each contiguous region with the same permissions is one struct vm_area_struct (VMA). The kernel builds the VMA set lazily — pages are physically allocated only on first access (demand paging). Copy-on-Write makes fork() nearly free: child and parent share physical pages until one writes.

File I/O is served from the page cache — a per-inode struct address_space backed by an XArray of cached pages. A two-list LRU (active / inactive) decides which pages to keep hot and which to reclaim. Dirty pages are written back by per-device worker threads on a configurable schedule.

DMA lets hardware write directly to physical RAM without CPU involvement. The IOMMUinterposes on device bus addresses — protecting arbitrary memory from buggy or malicious devices and enabling DPDK's kernel-bypass via VFIO.

15. Key Data Structures

struct mm_struct — per-process address space

All threads of a process share one mm_struct. It holds the page-table root (loaded into CR3 on context switch), the ordered set of VMAs, and accounting counters. mmap_lock (an rwsem) serialises structural changes — taking it as a writer during mmap() / munmap() and as a reader during page fault handling.

struct vm_area_struct — one VMA per region

A call to mmap() creates one VMA. The kernel keeps VMAs in both a sorted linked list (for iteration) and a red-black tree (for O(log n) lookup by address — used in page fault handling to find the VMA owning the faulting address in microseconds).

struct address_space — page-cache anchor

Every file inode has one address_space embedded. The XArray i_pages maps page offsets (0, 1, 2…) to struct page *. A page fault on a file-backed VMA first looks here — cache hit costs a single XArray lookup; cache miss triggers a_ops->readpage() to load from disk.

16. Core Mechanism — Copy-on-Write (COW)

Background: fork()must give the child a full copy of the parent's address space. Physically copying all mapped pages upfront would take hundreds of milliseconds for a process with gigabytes of mappings. COW defers the copy to the moment of first write — and many child processes never write most pages (e.g., exec() immediately replaces the image).

Plan:

1. fork() calls copy_page_range() — walks the parent PTEs and copies entries into the child page table, but marks all writable PTEs read-only in both parent and child. Increments physical page _refcount for each shared page.
2. Either process writes → CPU sees PTE.W=0 → raises #PF (protection fault).
3. do_cow_fault(): allocate a fresh page, copy 4 KB, update the faulting PTE to point to the new page with PTE.W=1, decrement the shared page's refcount.
4. If refcount drops to 1 after the COW (only one PTE remains), the other process's PTE is re-armed writable — no future fault needed.

Example — fork then child writes one page:

17. Core Mechanism — Page Cache & LRU Reclaim

Background:Modern servers have tens of gigabytes of RAM and workloads that touch far more data than fits. The kernel must decide which cached file pages to keep (hot) and which to discard (cold) under memory pressure. A simple FIFO evicts pages that were loaded recently but haven't been reused — killing streaming workloads. A pure LRU has the thrashing problem: a single sequential scan of a large file evicts all hot pages.

Plan — two-list strategy:

1. New pages start on the inactive list (cold). They are protected from immediate eviction but not from reclaim under pressure.
2. If a page is accessed a second time while still on the inactive list, it is promoted to the active list (hot). Only truly reused pages earn active status.
3. Over time, active pages that are not accessed are demoted back to the inactive list tail by kswapd's shrink_active_list().
4. Reclaim always takes from the inactive list tail — oldest cold pages first. If dirty, they are written back; if clean, dropped immediately.

Dirty Page Writeback Lifecycle

write() modifies the page cache, marks pages PG_dirty, and returns — it does not wait for disk. A per-device kernel thread (wb_workqueue) flushes dirty pages after dirty_expire_interval (default 30 s) or when the dirty ratio exceeds dirty_background_ratio(default 10 %). If dirty pages reach dirty_ratio (default 20 %), the writing task itself is throttled inside balance_dirty_pages().

18. Memory-Mapped I/O & DMA

Three Address Spaces

Hardware operates in three distinct address spaces. Confusing them is the single most common bug in driver code.

DMA API

IOMMU — DMA Remapping

Without an IOMMU, a buggy or malicious PCIe device can DMA to any physical address — including kernel code. The IOMMU (Intel VT-d, AMD-Vi) interposes on every device DMA access: it maintains a per-device page table mapping bus addressesto physical pages, and faults on unmapped access. DPDK's VFIO mode uses the IOMMU to give user-space drivers safe, direct DMA without a kernel driver in the forwarding path.

19. Minimal C Demo

The first demo simulates Copy-on-Write: parent and child share a physical page after fork; the child's write triggers a copy. The same logic lives in do_cow_fault() in mm/memory.c.

The second demo simulates the two-list LRU: pages start in the inactive list and are promoted to active on a second access. Memory pressure evicts from the inactive tail — the same policy used by shrink_inactive_list().

The third demo shows how dma_map_single() converts a kernel virtual address to a bus address. On x86 without an IOMMU the bus address equals the physical address; with an IOMMU the device sees a remapped address.

20. Kernel Source Pointers

21. Interview Prep