How Linux Memory Compaction Resolves Fragmentation

Physical memory fragmentation occurs when free memory is broken into small, non-contiguous chunks over time, preventing the Linux kernel from fulfilling requests for large, contiguous memory blocks like Transparent Huge Pages (THP) or device driver DMA buffers. The Linux operating system resolves this issue through an engine called memory compaction. This article details how memory compaction identifies fragmented memory zones, shifts movable pages using a dual-scanner algorithm, and restores contiguous blocks of physical memory without needing to drop caches or swap heavily to disk.

The Fragmentation Problem

The Linux kernel manages physical memory allocations using the Buddy Allocator, which divides memory into page frames grouped by orders of power-of-two sizes (order-0 is 4 KB, order-1 is 8 KB, up to order-10 for 4 MB). As applications allocate and release memory unpredictably, physical memory becomes checkerboarded with scattered allocations. While the total volume of free memory might be high, the Buddy system may lack enough adjacent pages to satisfy a high-order allocation. This state is known as external memory fragmentation.

Page Mobility and Grouping

Before compaction can function, the kernel needs to know which pages can be relocated safely. Linux solves this by grouping page blocks according to their mobility:

• MIGRATE_MOVABLE: Pages allocated to userspace applications (anonymous memory, page cache) can be copied to a new physical address because their page table mappings can simply be updated.
• MIGRATE_RECLAIMABLE: Pages like directory entries (dentries) and inodes that cannot be shifted directly, but can be dropped or reclaimed under memory pressure.
• MIGRATE_UNMOVABLE: Pages allocated by core kernel structures, hardware drivers, or locked memory pages that cannot be changed without breaking system integrity.

Memory compaction exclusively targets MIGRATE_MOVABLE pages, leaving unmovable structures undisturbed.

The Dual-Scanner Compaction Algorithm

Memory compaction operates on individual memory zones (such as ZONE_NORMAL or ZONE_DMA32) using an efficient two-scanner mechanism. The algorithm moves pages from the bottom of the memory zone into free spaces located at the top of the zone.

1. The Migration Scanner: Begins at the start (lowest physical page frame number, or PFN) of the zone and scans upward, searching for allocated, movable pages.
2. The Free Scanner: Begins at the end (highest PFN) of the zone and scans downward, searching for isolated, unallocated page frames.
3. Page Migration: Once both scanners identify suitable candidates, the kernel copies the data from the migration scanner's pages into the free slots discovered by the free scanner. The page table entries referencing the old locations are atomically updated to point to the new physical addresses.
4. Completion: The scanners continue working toward each other until they meet somewhere in the middle of the zone, or until the desired high-order contiguous block is successfully assembled.

By sweeping allocated data toward the lower physical addresses and pooling free space toward the higher addresses, the Buddy Allocator naturally reconstructs high-order chunks of contiguous memory.

When Compaction Runs

Compaction is invoked through three distinct paths depending on system demand:

• Direct Compaction: Triggered synchronously when a process requests a high-order page allocation that cannot be fulfilled immediately. The process pauses briefly while the kernel compacts just enough memory to satisfy the request.
• Background Compaction (kcompactd): A kernel thread that monitors fragmentation indexes in each memory zone. When a zone exceeds a defined fragmentation threshold, kcompactd runs asynchronously to assemble contiguous blocks before processes actually experience allocation delays.
• Manual Compaction: System administrators can force system-wide compaction at runtime by writing 1 to /proc/sys/vm/compact_memory.

Performance and Trade-Offs

Memory compaction is significantly faster and less disruptive than traditional page reclaiming or swapping to disk, as it merely shifts memory contents within RAM. However, memory compaction does consume CPU cycles and memory bus bandwidth during page copy operations. To prevent performance degradation, the Linux kernel employs cost-benefit heuristics and fragmentation scoring to ensure compaction only runs when the likelihood of successfully recovering high-order contiguous blocks outweighs the operational cost of copying the pages.