How Linux Compacts Memory to Eliminate Fragmentation

Physical memory in Linux is managed in 4 KB pages (unless using huge pages). Allocation proceeds sequentially, while freeing is random, leading to scattered free pages. When a process requests several contiguous pages, allocation can fail despite sufficient total free pages—a situation known as memory fragmentation.

To resolve this, the kernel can compact memory by moving free pages together. The compaction process must also update the reverse mapping between virtual and physical pages.

Memory Compaction Principle

Compaction starts with two pointers at the start and end of a memory zone. The head pointer scans forward for movable pages, the tail pointer scans backward for free pages; when they meet, the process stops. Visual examples show initial fragmented state, scanning phase, and final compacted state where three contiguous pages can be allocated.

Implementation Overview

Compaction is triggered when alloc_pages_node() fails to allocate the requested order of pages. The call chain is:

alloc_pages_node()
└→ __alloc_pages()
   └→ __alloc_pages_nodemask()
      └→ __alloc_pages_slowpath()
         └→ __alloc_pages_direct_compact()

The function __alloc_pages_direct_compact() checks if the request is for a single page (no compaction needed) and then calls try_to_compact_pages(). This function iterates over all zones and invokes compact_zone_order(), which prepares a compact_control structure and calls compact_zone().

Inside compact_zone(), the algorithm repeatedly:

Collects movable pages via isolate_migratepages().

Migrates them to free pages using migrate_pages().

isolate_migratepages()

This function scans every page in a zone, skips non‑movable pages, removes selected pages from the LRU list, and adds them to a migrate list. It performs five steps: scan pages, obtain page objects, check movability, detach from LRU, and enqueue for migration.

migrate_pages()

It iterates over the migrate list, calling unmap_and_move() for each page. The loop retries up to ten passes, handling errors such as -ENOMEM and -EAGAIN, and counts failed migrations.

unmap_and_move()

The core steps are:

Find a free destination page.

Unmap all virtual mappings that reference the source page using try_to_unmap() (leveraging reverse page mapping).

Copy the source page’s data to the destination with move_to_new_page(), rebuilding the virtual mapping.

After migration, the original page is freed, and the previously fragmented region now contains a larger contiguous free block.

Summary

Linux memory compaction solves allocation failures caused by fragmented free pages by gathering movable pages and relocating them into contiguous free zones. While effective, compaction can be CPU‑intensive; callers can avoid it by using the __GFP_WAIT flag to skip waiting for compaction.

Note: The article omits detailed handling of reverse page mapping, which will be covered in a future piece.