Memory

Almost everything a program believes about memory is a lie the MMU tells, maintained lazily by the page-fault handler. Kernel memory is the other half: real, finite, un-swappable, and allocated through a family of allocators whose differences matter enormously and are invisible at the call site.

Six concepts in the six-part treatment: virtual memory and the page fault, the page allocator, GFP flags, slab, vmalloc, and choosing, folios and the page cache, and DMA.

Concept 1: Virtual Memory and the Page Fault

1. What problem it solves

Every process needs its own address space, more address space than there is RAM, protection from every other process, and the ability to map files and share pages. One mechanism provides all of it: the CPU translates every address through page tables the kernel controls, and traps to the kernel whenever the translation is absent or the permission is wrong.

That trap is not an error path — it is the main path. Demand paging, copy-on-write, mmap of files, swap, and lazy allocation are all "we deliberately left the page table empty and will fill it in when someone touches it".

2. Where it exists in the kernel

mm/, plus per-architecture page-table code in arch/*/mm/.

rg -n "handle_mm_fault|do_user_addr_fault" mm/memory.c arch/x86/mm/fault.c
rg -n "struct vm_area_struct \{" include/linux/mm_types.h
ls Documentation/mm/
find Documentation -path '*x86*' -name 'mm.rst'      # the x86-64 address-space layout

3. Who owns or interacts with it

4. The structures and paths

   task_struct
       └── mm_struct                    the address space
             ├── pgd                    the top of the page tables
             └── a set of VMAs          each: [start, end), prot, flags, and a
                                        backing (a file, or anonymous)

   FAULT:  CPU traps  →  handler asks: which VMA covers this address?
             │
             ├── none                        → SIGSEGV  (or an oops, if the
             │                                  address came from kernel code)
             ├── VMA exists, page not present
             │      ├── file-backed, in page cache  → MINOR fault: just map it
             │      ├── file-backed, not cached     → MAJOR fault: read from disk,
             │      │                                  and this SLEEPS
             │      ├── anonymous, first touch      → allocate a zeroed page
             │      └── swapped out                 → MAJOR fault: read from swap
             └── VMA exists, present, but write to a read-only page
                    ├── it is a CoW page            → copy it, map writable
                    └── it really is read-only      → SIGSEGV

Two things follow that people find surprising:

A malloc() that succeeds has not allocated memory. It extended a VMA. The pages appear on first touch, which is why a program can succeed at allocation and be OOM-killed while writing to it.

A page fault can sleep, because a major fault does I/O. That is why copy_to_user() belongs on the list of functions that can sleep, and why the whole of context and atomicity applies to it.

5. Experiment

CLAIM. Allocation and residency are different events, and you can watch the gap.

METHOD.

cat > /tmp/vm.c <<'EOF'
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
static void show(const char *tag) {
    char line[256]; FILE *f = fopen("/proc/self/status", "r");
    printf("== %s\n", tag);
    while (fgets(line, sizeof line, f))
        if (!strncmp(line, "VmSize", 6) || !strncmp(line, "VmRSS", 5)) printf("   %s", line);
    fclose(f);
}
int main(void) {
    show("start");
    char *p = malloc(256 * 1024 * 1024);          /* 256 MB */
    show("after malloc (untouched)");
    for (size_t i = 0; i < 256UL*1024*1024; i += 4096) p[i] = 1;   /* touch every page */
    show("after touching every page");
    return 0;
}
EOF
gcc -O0 -o /tmp/vm /tmp/vm.c && /tmp/vm

PREDICT FIRST: after malloc, does VmSize grow? Does VmRSS? By how much? And after the touch loop?

Then count the faults themselves:

/usr/bin/time -v /tmp/vm 2>&1 | grep -E 'Maximum resident|page faults'
sudo perf stat -e page-faults,minor-faults,major-faults /tmp/vm
sudo bpftrace -e 'software:page-faults:1 /comm=="vm"/ { @ = count(); }' -c /tmp/vm

PREDICT FIRST (again): how many minor faults for 256 MB at 4 KB pages? Are you off by a factor of 512? If so, you just discovered transparent huge pages:

cat /sys/kernel/mm/transparent_hugepage/enabled
grep -E 'AnonHugePages|Hugepagesize' /proc/meminfo

6. Failure mode

Concept 2: The Page Allocator

1. What problem it solves

Everything else is built on this. Physical memory has to be handed out in page-sized and larger-power-of-two-sized chunks, with low fragmentation, quickly, from any CPU, under pressure.

2. Where it exists in the kernel

mm/page_alloc.c, the buddy allocator.

rg -n "__alloc_pages\b|struct zone \{" mm/page_alloc.c include/linux/mmzone.h | head
rg -n "MAX_PAGE_ORDER|MAX_ORDER" include/linux/mmzone.h | head
cat /proc/buddyinfo
cat /proc/zoneinfo | head -30

Note: The maximum allocation order and its spelling both changed during the 6.x series (MAX_ORDER became inclusive, then was renamed MAX_PAGE_ORDER). This is exactly the kind of thing not to memorize — grep it in your tree.

3. How it works

  FREE LISTS, one per order, per zone, per migrate type:

    order 0  [4 KB]   ████████████████  many
    order 1  [8 KB]   ██████            
    order 2  [16 KB]  ███
    order 3  [32 KB]  █
    ...
    order N  [max]    

  ALLOCATE order 2, none free:
     split an order-3 block → two order-2 "buddies"; give one away, free the other.
  FREE an order-2 block:
     if its buddy is also free, merge into an order 3. Recursively.

  This is why /proc/buddyinfo is a fragmentation report: lots of order-0 and
  nothing at order 5+ means you cannot get a 128 KB contiguous allocation even
  though there is plenty of free memory.

Zones exist because not all physical memory is equivalent to all devices:

4. The API

5. Experiment

CLAIM. High-order allocations fail long before memory runs out, because of fragmentation — and /proc/buddyinfo predicts it.

METHOD. In a module, try increasing orders and report where it stops:

for (order = 0; order <= 10; order++) {
        struct page *p = alloc_pages(GFP_KERNEL | __GFP_NOWARN, order);
        pr_info("order %2d (%4lu KB): %s\n", order,
                (PAGE_SIZE << order) >> 10, p ? "ok" : "FAILED");
        if (p)
                __free_pages(p, order);
}

PREDICT FIRST: on a freshly booted guest with plenty of free memory, at which order does it start failing? Now run something that fragments memory first (a large find, a kernel build), re-run, and predict again.

cat /proc/buddyinfo        # before and after; the right-hand columns are the story

6. Failure mode

Concept 3: GFP Flags

1. What problem it solves

The allocator needs to know what it is allowed to do to satisfy you: may it sleep? may it start I/O? may it recurse into the filesystem? may it use the emergency reserve? That is not a property of the size — it is a property of your calling context, and only you know it.

2. Where it exists in the kernel

rg -n "define GFP_KERNEL|define GFP_ATOMIC|define GFP_NOWAIT" include/linux/gfp_types.h
$EDITOR Documentation/core-api/memory-allocation.rst    # READ THIS. It is short and canonical.

3. The flags that matter

Warning: GFP_NOIO and GFP_NOFS are largely superseded by scopes. Rather than threading a flag through twenty call layers, mark the region:

unsigned int flags = memalloc_nofs_save();
...   /* everything in here allocates as if GFP_NOFS, including callees */
memalloc_nofs_restore(flags);

Modern filesystem code does it this way, and a patch adding GFP_NOFS to a deep helper will be asked why it did not use the scope. See Documentation/core-api/gfp_mask-from-fs-io.rst.

GFP_ATOMIC is not "the atomic-context version of GFP_KERNEL". It is a request to dip into a reserve that exists so that network receive and interrupt paths can allocate at all when memory is exhausted. Overusing it exhausts that reserve and hurts unrelated subsystems. The order of preference in atomic context is: restructure so you allocate outside the lock → GFP_NOWAIT with a real failure path → GFP_ATOMIC.

4. What happens on the slow path

   kmalloc(n, GFP_KERNEL)
        │
        ├── fast path: a free object in this CPU's slab cache      → done, ~20 ns
        │
        ├── ask the page allocator for a new slab
        │      └── free page available in the right zone           → done
        │
        └── no free pages → RECLAIM (this is where GFP_KERNEL sleeps)
               ├── wake kswapd (background reclaim) and try again
               ├── DIRECT RECLAIM in the calling task:
               │      drop clean page cache · write back dirty pages
               │      · swap anonymous pages · shrink slab caches
               │      (LRU, or MGLRU if CONFIG_LRU_GEN is on)
               ├── compaction, if the request is high-order
               └── still nothing → the OOM killer picks a victim

Watch it:

grep -E 'pgscan|pgsteal|pgalloc|allocstall|compact_' /proc/vmstat
cat /proc/pressure/memory 2>/dev/null       # PSI: how much time is lost to memory stalls
dmesg | grep -i "out of memory\|oom-kill"

5. Experiment

CLAIM. GFP_ATOMIC and GFP_KERNEL behave identically on an idle machine and differently under pressure — so the distinction is untestable without creating pressure deliberately.

METHOD. With CONFIG_FAILSLAB (in lab-paranoid), make allocations fail on demand:

F=/sys/kernel/debug/failslab
echo 50 > $F/probability
echo -1 > $F/times
echo N  > $F/ignore-gfp-wait     # ALSO fail allocations that could have slept
insmod ./alloc-lab.ko

PREDICT FIRST: with a 50% injected failure rate, how many of your module's allocation sites handle NULL correctly? Count them in the source first, then count the ones the module survives.

RESULT. Note every path that oopsed. Each one is a real bug that would have appeared, in production, on a machine under pressure, in a way that looked like something else.

6. Failure mode

Concept 4: Slab, vmalloc, and Choosing

1. What problem it solves

The page allocator's granularity is a page. Most kernel objects are 32–512 bytes and there are millions of them. The slab allocator sits on top of the page allocator and hands out small objects from per-CPU caches, with no lock in the fast path.

vmalloc solves the opposite problem: a large allocation where physical contiguity is not needed and would be hard to get.

2. Where it exists in the kernel

ls mm/slub.c mm/vmalloc.c mm/util.c
grep -E 'CONFIG_SLUB|CONFIG_SLAB\b|CONFIG_SLOB' ~/kernel/build/.config   # SLUB is the only one now
head -3 /proc/slabinfo; sudo slabtop -o | head -15
grep -E 'VmallocTotal|VmallocUsed' /proc/meminfo

3. The choice — this table is the chapter

/* Arrays: use the checked helpers. kmalloc(n * sizeof(x)) can overflow
 * with an attacker-controlled n, and that is a classic heap overflow.   */
p = kmalloc_array(n, sizeof(*p), GFP_KERNEL);      /* not kmalloc(n * sizeof(*p)) */
p = kcalloc(n, sizeof(*p), GFP_KERNEL);            /* ...and zeroed              */

/* A struct with a trailing flexible array: */
s = kzalloc(struct_size(s, items, n), GFP_KERNEL); /* overflow-checked           */

/* A large, runtime-sized buffer with no DMA and no contiguity requirement: */
buf = kvmalloc(len, GFP_KERNEL);
...
kvfree(buf);

/* Many objects of one type — and now `slabtop` shows YOUR cache by name: */
cache = kmem_cache_create("mylab_node", sizeof(struct node), 0,
                          SLAB_HWCACHE_ALIGN, NULL);
node  = kmem_cache_alloc(cache, GFP_KERNEL);

Why vmalloc is not simply "kmalloc for big things":

4. Experiment

CLAIM. vmalloc memory is not physically contiguous, and you can prove it.

METHOD.

size_t sz = 64 * 1024;
void *k = kmalloc(sz, GFP_KERNEL);
void *v = vmalloc(sz);
int i;

pr_info("kmalloc: virt=%p\n", k);
for (i = 0; i < 4; i++)
        pr_info("  page %d: phys=%pa\n", i,
                &(phys_addr_t){ virt_to_phys(k + i * PAGE_SIZE) });

pr_info("vmalloc: virt=%p\n", v);
for (i = 0; i < 4; i++) {
        phys_addr_t pa = page_to_phys(vmalloc_to_page(v + i * PAGE_SIZE));
        pr_info("  page %d: phys=%pa\n", i, &pa);
}

PREDICT FIRST: for kmalloc, are the four physical addresses 4096 apart? For vmalloc? Write both predictions down.

Then check the timing:

t0 = ktime_get_ns(); for (i = 0; i < 1000; i++) kfree(kmalloc(4096, GFP_KERNEL));
pr_info("kmalloc/kfree x1000: %llu ns\n", ktime_get_ns() - t0);
t0 = ktime_get_ns(); for (i = 0; i < 1000; i++) vfree(vmalloc(4096));
pr_info("vmalloc/vfree x1000: %llu ns\n", ktime_get_ns() - t0);

PREDICT FIRST: the ratio. Most people guess 3×.

5. Failure mode

Concept 5: Folios and the Page Cache

1. What problem it solves

The kernel caches file contents in memory. That cache is most of your RAM (Cached in /proc/meminfo), and it is why the second cat of a file in the warm-up was so much faster than the first.

Folios solve a second, internal problem: struct page was used to mean both "one 4 KB page" and "the head of a compound multi-page allocation", and a great deal of code could not tell which it had. A struct folio is by construction the head — a set of physically contiguous pages treated as one unit — which makes whole classes of head/tail bugs unrepresentable.

2. Where it exists in the kernel

rg -n "struct folio \{" include/linux/mm_types.h
rg -n "struct address_space \{" include/linux/fs.h
ls Documentation/mm/
git log --oneline --grep="folio" -- mm/ | head -20      # the conversion, still in progress

3. The structures

   struct file  ──▶ struct inode ──▶ struct address_space
                                          │  (an XArray, indexed by file offset)
                                          ▼
                                     folios: the cached contents
                                       flags: uptodate? dirty? writeback? locked?

   read():   look up the folio at this offset
               present and uptodate → copy_to_user. MINOR. Microseconds.
               absent               → allocate, submit I/O, SLEEP, wake, copy. MAJOR.

   write():  find or create the folio, copy into it, mark it DIRTY, return.
             The data is NOT on disk. Writeback happens later, or on fsync().

Note: This is why write() returning does not mean the data is durable, and why fsync() exists and is slow. It is also why a filesystem's crash-consistency story is complicated: the page cache decides when things reach the disk, and journaling exists to make "some of it did" a recoverable state.

4. Experiment

CLAIM. The page cache is visible, controllable, and dominant.

METHOD.

dd if=/dev/urandom of=/tmp/f bs=1M count=200 status=none
sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

grep -E '^Cached' /proc/meminfo
sudo perf stat -e major-faults,minor-faults -- cat /tmp/f > /dev/null   # cold
grep -E '^Cached' /proc/meminfo
sudo perf stat -e major-faults,minor-faults -- cat /tmp/f > /dev/null   # warm

# Which pages of a file are resident right now:
python3 - <<'EOF'
import mmap, os, ctypes
f = open('/tmp/f','rb'); sz = os.fstat(f.fileno()).st_size
m = mmap.mmap(f.fileno(), 0, prot=mmap.PROT_READ)
vec = (ctypes.c_ubyte * ((sz + 4095)//4096))()
libc = ctypes.CDLL(None)
libc.mincore(ctypes.c_void_p(ctypes.addressof(ctypes.c_char.from_buffer(m))),
             ctypes.c_size_t(sz), vec)
print("resident pages:", sum(v & 1 for v in vec), "of", len(vec))
EOF

PREDICT FIRST: the ratio of cold to warm time, and the major-fault count in each case.

5. Failure mode

Concept 6: DMA

1. What problem it solves

A device writes into RAM without the CPU. For that to work, three things must be true that are not guaranteed by "I allocated some memory":

  1. THE DEVICE MUST BE ABLE TO ADDRESS IT.
     A 32-bit device cannot reach a buffer above 4 GB. An IOMMU may
     remap; a bounce buffer (SWIOTLB) may copy. Either way, the address
     the DEVICE uses is not the address the CPU uses.

  2. THE MEMORY MUST BE PHYSICALLY CONTIGUOUS (for a single mapping).
     The device follows physical addresses. It knows nothing of page tables.

  3. THE CACHES MUST AGREE.
     On a non-cache-coherent architecture, the CPU's cached copy and what
     the device wrote to RAM are different. Somebody must invalidate or
     flush, at the right moment, in the right direction.

The DMA API exists so drivers express intent and the platform handles all three.

2. Where it exists in the kernel

ls kernel/dma/ include/linux/dma-mapping.h
$EDITOR Documentation/core-api/dma-api-howto.rst      # READ THIS before writing a driver
$EDITOR Documentation/core-api/dma-api.rst
grep -E 'CONFIG_DMA_API_DEBUG' ~/kernel/build/.config

3. The two kinds of mapping

/* Declare what the device can address. Do this in probe, BEFORE any mapping. */
ret = dma_set_mask_and_coherent(dev, DMA_BIT_MASK(64));
if (ret)
        return ret;

/* Coherent: a descriptor ring both the CPU and the device read continuously. */
ring = dma_alloc_coherent(dev, RING_BYTES, &ring_dma, GFP_KERNEL);
/*     ^ CPU virtual address        ^ the DEVICE's address — NOT a physical
 *                                    address, and not interchangeable        */

/* Streaming: one buffer, one transfer, one direction. */
dma_addr_t handle = dma_map_single(dev, buf, len, DMA_TO_DEVICE);
if (dma_mapping_error(dev, handle))        /* ALWAYS check */
        return -ENOMEM;
start_transfer(dev, handle, len);
/* ...on completion: */
dma_unmap_single(dev, handle, len, DMA_TO_DEVICE);

4. The rules, and why kmalloc memory is not automatically safe

So: kmalloc memory is usable for streaming DMA — it is physically contiguous and suitably aligned — but that is not sufficient. The device's addressing mask may exclude where it landed, in which case the DMA API silently bounces it through a low buffer (SWIOTLB), which costs a copy. And on a non-coherent platform, a kmalloc of 8 bytes next to other live data is a cache-line hazard. The correctness comes from using the API, not from the allocator.

5. Experiment

CLAIM. CONFIG_DMA_API_DEBUG catches DMA misuse that is otherwise invisible on x86 and catastrophic elsewhere.

METHOD. Build a lab-paranoid kernel with CONFIG_DMA_API_DEBUG=y and write a module that deliberately maps a stack buffer:

static int __init dma_lab_init(void)
{
        char stackbuf[64];              /* WRONG ON PURPOSE */
        dma_addr_t h = dma_map_single(&pdev->dev, stackbuf, sizeof(stackbuf),
                                      DMA_TO_DEVICE);
        ...
}

PREDICT FIRST: does this (a) fail to compile, (b) warn at runtime, (c) work on x86 and corrupt data on arm64, or (d) all of the above depending on config? Then run it and read:

WARNING: ... at kernel/dma/debug.c:...
DMA-API: device driver maps memory from stack [addr=...]

Also try forgetting the dma_unmap_single and see what the checker says at driver removal.

6. Failure mode

The Decision Table

Validation / Self-check

1. Why is a page fault the main path rather than an error path? Name four normal features built on it.
2. malloc() returned successfully. How much memory has been allocated? Explain.
3. Which kinds of page fault can sleep, and what does that imply about copy_to_user?
4. Explain the buddy allocator's split and merge, and say what /proc/buddyinfo tells you.
5. Why do memory zones exist? Give one device-driven reason.
6. Compare GFP_KERNEL, GFP_NOWAIT, and GFP_ATOMIC along three axes.
7. What is the correct order of preference for allocating in atomic context, and why is GFP_ATOMIC last?
8. What are memalloc_nofs_save()/memalloc_noio_save() for, and what problem with GFP_NOFS do they solve?
9. Trace what kmalloc(64, GFP_KERNEL) does when no memory is free. Where does it sleep?
10. Give four differences between kmalloc and vmalloc that would change your choice.
11. What is kvmalloc for, and what may you never do with its result?
12. Why is kmalloc(n * sizeof(*p)) a security bug and kmalloc_array(n, sizeof(*p)) not?
13. What is a folio and which class of bug did it eliminate?
14. Why does write() returning not mean the data is on disk?
15. Name the three things that must be true for a device to DMA into a buffer, and the API call that handles each.
16. Why may you not DMA to or from the stack? Give two independent reasons.
17. kmalloc memory is physically contiguous, so why is it still not automatically safe for DMA?
18. What is dma_addr_t, and why is it not a physical address?

Next: Deferred Work — the interrupt takes 2 µs and the work takes 2 ms. Now what?