Allocators and Folios

Foundations taught you which allocator to call. This chapter is about how they work, because from here on you are reading and changing them rather than using them.

Three concepts in the six-part treatment: the buddy allocator, slab, and folios and the page cache.

Concept 1: The Buddy Allocator

1. What problem it solves

Physical memory must be handed out in page-sized and larger power-of-two chunks, quickly, from any CPU, with as little fragmentation as possible, and it must be possible to give a contiguous range to a device that needs one.

Those goals conflict. Handing out pages wherever they fit minimises waste and destroys contiguity; keeping large ranges intact wastes memory. The buddy allocator's answer is to make merging cheap enough to do eagerly.

2. Where it exists in the kernel

rg -n "__alloc_pages\b" -A 40 mm/page_alloc.c | head -50
rg -n "struct free_area \{" -A 6 include/linux/mmzone.h
rg -n "enum migratetype" -A 12 include/linux/mmzone.h
cat /proc/buddyinfo /proc/pagetypeinfo | head -20

3. The mechanism

   FREE LISTS: one per ORDER, per MIGRATETYPE, per ZONE, per NODE.

     order 0  [  4 KB]  ████████████████████  many
     order 1  [  8 KB]  ██████████
     order 2  [ 16 KB]  ████
     order 3  [ 32 KB]  █
     ...
     order N  [max]     (MAX_PAGE_ORDER -- grep it, the name changed in 6.x)

   ALLOCATE order 2, none free:
     take an order-3 block, split it into two order-2 "buddies",
     hand one out, put the other on the order-2 list.

   FREE an order-2 block:
     is its buddy also free? (its address differs in exactly one bit --
     that is why it is called a buddy, and why the check is O(1))
     if yes: merge into an order 3. Then check THAT block's buddy. Recurse.

The O(1) buddy check is the whole trick: two blocks of order n are buddies if their page-frame numbers differ only in bit n. Merging is therefore a bit test, not a search, which makes eager merging affordable.

Migratetypes are the anti-fragmentation mechanism, and they are the part people miss:

Grouping by migratetype means unmovable allocations cluster together, leaving other regions defragmentable. This is why a machine with 20 GB free can fail to allocate 2 MB contiguous: the free memory is order-0 blocks scattered among unmovable ones.

cat /proc/pagetypeinfo | head -30      # free blocks by order AND migratetype
grep -E 'compact_' /proc/vmstat        # compaction: attempts, successes, failures

4. Zones and nodes

   NUMA node 0                          NUMA node 1
     ZONE_DMA32   (< 4 GB, for old devices)
     ZONE_NORMAL  (everything else)       ZONE_NORMAL
     ZONE_MOVABLE (only movable pages)    ZONE_MOVABLE

   An allocation has a ZONELIST: the preferred zone, then fallbacks in
   order. The GFP flags and the NUMA policy decide the list.

cat /proc/zoneinfo | grep -E '^Node|^  pages free|^  min|^  low|^  high' | head -20
numactl --hardware 2>/dev/null || echo "single node"

The min/low/high watermarks are the control loop: crossing low wakes kswapd; crossing min means an allocating task must reclaim synchronously (direct reclaim).

5. Experiment

CLAIM. Fragmentation is real, visible, and predicts high-order allocation failure better than free memory does.

METHOD. In a module:

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

# Fresh boot:
cat /proc/buddyinfo; insmod ./orders.ko; dmesg | tail -12

# Now fragment memory deliberately, then repeat:
find / -type f -exec cat {} + > /dev/null 2>&1 &   # fill the page cache
sleep 60; kill %1
cat /proc/buddyinfo; rmmod orders; insmod ./orders.ko; dmesg | tail -12

# And watch compaction try to fix it:
grep compact /proc/vmstat
echo 1 | sudo tee /proc/sys/vm/compact_memory
grep compact /proc/vmstat
cat /proc/buddyinfo

PREDICT FIRST: on a fresh boot, at which order does allocation start failing? After fragmentation? And does explicit compaction restore the high orders?

6. Failure mode

Concept 2: Slab

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, allocated and freed constantly, often on the hot path of a syscall.

Slab sits on top of the page allocator and provides: sub-page granularity, per-CPU caches so the fast path takes no lock, and type-specific caches whose objects share a page and stay cache-warm.

2. Where it exists in the kernel

ls mm/slub.c mm/slab_common.c
grep -E 'CONFIG_SLUB|CONFIG_SLAB\b|CONFIG_SLOB' ~/kernel/build/.config
rg -n "kmem_cache_alloc\b" -A 25 mm/slub.c | head -35
head -3 /proc/slabinfo; sudo slabtop -o | head -20

SLUB is the only allocator now — SLOB was removed in 6.4 and SLAB in 6.8. Anything written about choosing between them is stale.

3. The structure

   kmem_cache "dentry"  (one per object type)
     ├── object size, alignment, constructor
     └── per-CPU:
           ├── the ACTIVE SLAB: a page of objects, with a freelist
           │     Allocation: pop the head of this CPU's freelist.
           │     NO LOCK. This is the fast path, and it is a few ns.
           └── a partial list, for when the active slab is exhausted
     └── per-NODE: partial slabs, and the path to the page allocator

   kmalloc(n) picks a size class:
     kmalloc-8, -16, -32, ..., -8k  (powers of two)
     A 33-byte allocation uses kmalloc-64. THIRTY-ONE BYTES ARE WASTED.
     Above the largest cache, kmalloc falls through to the page allocator.

grep -E '^kmalloc-' /proc/slabinfo | head -12
rg -n "KMALLOC_MAX_CACHE_SIZE|kmalloc_caches" include/linux/slab.h | head

The internal fragmentation of power-of-two classes is why a named cache matters for a hot object:

/* 1,000,000 of these via kmalloc: 96 bytes each in kmalloc-128 → 32 MB wasted */
struct thing { u64 a, b, c, d, e, f, g, h, i, j, k, l; };  /* 96 bytes */

/* With a named cache: exactly 96 bytes, packed, and visible in slabtop */
cache = kmem_cache_create("mylab_thing", sizeof(struct thing), 0,
                          SLAB_HWCACHE_ALIGN, NULL);

Flags worth knowing:

4. Experiment

CLAIM. The slab fast path is lock-free and per-CPU, and internal fragmentation is measurable.

METHOD.

/* In a module: time kmalloc/kfree round trips, and compare a named cache. */
u64 t0 = ktime_get_ns();
for (i = 0; i < 1000000; i++) kfree(kmalloc(96, GFP_KERNEL));
pr_info("kmalloc(96)      x1e6: %llu ns\n", ktime_get_ns() - t0);

cache = kmem_cache_create("labthing", 96, 0, 0, NULL);
t0 = ktime_get_ns();
for (i = 0; i < 1000000; i++) kmem_cache_free(cache, kmem_cache_alloc(cache, GFP_KERNEL));
pr_info("kmem_cache(96)   x1e6: %llu ns\n", ktime_get_ns() - t0);

PREDICT FIRST: nanoseconds per kmalloc/kfree pair. Then measure the memory difference:

grep -E '^kmalloc-128|^labthing' /proc/slabinfo
# columns: active_objs num_objs objsize objperslab pagesperslab ...

PREDICT FIRST: for 1,000,000 live 96-byte objects, how much memory does kmalloc-128 use versus a named 96-byte cache? Compute it, then allocate them and check.

5. Failure mode

Concept 3: Folios and the Page Cache

1. What problem it solves

The page cache is most of your RAM. It holds file contents so a second read costs microseconds instead of milliseconds, and it absorbs writes so a write() can return before the disk has seen anything.

Folios solve an internal problem: struct page was used to mean both "one 4 KB page" and "the head of a multi-page compound allocation", and enormous amounts of code could not tell which it had. Passing a tail page to a function expecting a head was a whole bug class. A struct folio is by construction a head, so the bug is unrepresentable.

2. Where it exists in the kernel

rg -n "struct folio \{" -A 30 include/linux/mm_types.h
rg -n "filemap_read\b|filemap_get_pages" -A 30 mm/filemap.c | head -40
rg -n "struct address_space \{" -A 25 include/linux/fs.h
git log --oneline --grep="folio" -- mm/ | head -20
ls Documentation/mm/

3. The structure

   struct file ──▶ struct inode ──▶ struct address_space
                                       ├── i_pages: an XArray
                                       │     file offset (in pages) -> folio
                                       ├── a_ops: address_space_operations
                                       │     read_folio, writepages,
                                       │     dirty_folio, invalidate_folio...
                                       └── host: back to the inode

   struct folio
     ├── flags: uptodate | dirty | writeback | locked | lru | referenced
     ├── mapping ──▶ the address_space (or NULL/anon for anonymous)
     ├── index      the offset within that mapping
     ├── _refcount  who holds a reference
     └── order      a folio is 2^order pages, treated as ONE unit

The flags are a state machine, and reading them is how you reason about I/O:

4. The two paths

   READ                                    WRITE
   ────                                    ─────
   filemap_read()                          generic_perform_write()
     └── look up the folio                   └── find or create the folio
          ├── present + uptodate                   └── copy from user
          │     copy_to_user. MINOR.               └── mark it DIRTY
          │     A few microseconds.                └── RETURN. The data is
          └── absent                                   NOT on disk.
                ├── allocate a folio
                ├── a_ops->read_folio()        ...later, asynchronously:
                │     submit I/O               writeback (per-bdi threads)
                ├── SLEEP on the folio lock      └── a_ops->writepages()
                └── woken when uptodate          └── clear dirty, set
                      copy_to_user. MAJOR.           writeback, submit I/O

That "RETURN" on the write side is why fsync() exists and is slow, and why a filesystem's crash-consistency design is complicated: the page cache decides when data reaches the disk, and journaling exists to make "some of it did" a recoverable state.

Readahead is the other half of read performance: the kernel detects sequential access and fetches ahead, so most "reads" of a sequentially-read file are minor faults on pages already in flight.

rg -n "page_cache_ra_unbounded|ondemand_readahead" mm/readahead.c | head
cat /sys/block/*/queue/read_ahead_kb 2>/dev/null | head -3
grep -E 'Dirty|Writeback' /proc/meminfo
cat /proc/sys/vm/dirty_ratio /proc/sys/vm/dirty_background_ratio

5. Experiment

CLAIM. The page cache is visible, controllable, and dominant; and folio order is observable.

METHOD.

dd if=/dev/urandom of=/tmp/f bs=1M count=512 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 the file are resident, right now:
sudo bpftrace -e 'tracepoint:filemap:mm_filemap_add_to_page_cache { @[comm] = count(); }' &
cat /tmp/f > /dev/null; kill %1

# Watch the write side NOT reach the disk:
grep -E 'Dirty|Writeback' /proc/meminfo
dd if=/dev/zero of=/tmp/w bs=1M count=256 status=none
grep -E 'Dirty|Writeback' /proc/meminfo          # look at Dirty immediately
sync
grep -E 'Dirty|Writeback' /proc/meminfo

PREDICT FIRST: the cold/warm ratio; and how large Dirty gets after writing 256 MB, and how long before it returns to near zero on its own.

Then folio order:

# Large folios mean fewer, bigger units. Where supported, this shows up as
# higher-order allocations in the cache.
grep -E 'AnonHugePages|FilePmdMapped' /proc/meminfo
sudo bpftrace -e 'kretprobe:filemap_alloc_folio { @order = hist(retval ? 1 : 0); }' 2>/dev/null | head

6. Failure mode

Validation / Self-check

1. Why are two blocks called "buddies", and what makes the merge check O(1)?
2. What are migratetypes for? Explain how a machine with 20 GB free fails a 2 MB contiguous allocation.
3. What do the min/low/high watermarks control, and what does crossing each one trigger?
4. Why is the slab fast path lock-free? What makes that possible?
5. kmalloc(96) for a million objects: how much memory is wasted, and what would you do instead?
6. What does SLAB_TYPESAFE_BY_RCU guarantee, and what must the reader still do?
7. What is a folio, and what class of bug did it make unrepresentable?
8. Name five folio flags and say what each tells you about the I/O state.
9. Trace a cold read() and a warm one through filemap_read, naming where each sleeps.
10. Why does write() return before the data is on disk, and what are the two consequences?
11. Which allocator is kvmalloc and when should you use it? What may you never do with the result?
12. Which is the better predictor of a high-order allocation succeeding: MemFree or /proc/buddyinfo? Why?

Next: Reclaim, cgroups, and OOM — what happens when there is not enough.