Overview of Linux Physical Memory Fragmentation and Management

This article uses kernel code from Linux 4.19 as a reference for readers who wish to study the source while reading.

1. Overview of Linux Physical Memory Fragmentation

Linux physical memory fragmentation can be divided into two types:

1) Internal fragmentation : Unused portions within an allocated memory block. For example, a process requests 3 KB of physical memory; the buddy allocator rounds up to the minimum granule of 4 KB, leaving 1 KB unused – this is internal fragmentation.

2) External fragmentation : Small free memory blocks that cannot satisfy larger allocation requests. For instance, 16 KB of free memory is split into four non‑contiguous 4 KB pages; a request for a contiguous block larger than 4 KB cannot be satisfied, illustrating external fragmentation.

2. Linux Physical Memory Management Framework

Linux manages physical memory using the buddy system allocator. The allocator maintains 11 free‑area lists, each managing blocks of size 2^n pages (from 4 KB up to 4 MB). Memory is organized into nodes (for NUMA support) and zones (to handle hardware constraints). The free_area array contains 11 indices, each representing a different block size.

Allocation steps (simplified):

Identify the appropriate node and zone based on the page type.

Select the free_area entry matching the requested size.

Choose the corresponding free_list and allocate a page.

Release steps (simplified):

Locate the node and zone for the page type.

Check if adjacent free blocks can be merged (must be contiguous, same type/size, and the resulting block’s first page address must be a multiple of 2 × block size × 4 KB).

Find the appropriate free_area and free_list to return the page.

3. Measures to Mitigate Physical Memory External Fragmentation

The buddy system already reduces external fragmentation by:

Allocating small blocks from small‑block lists, preventing large‑block list pollution.

Merging free blocks during deallocation, helping to form larger contiguous regions.

Additional kernel mechanisms include:

1) Memory Compaction

The compaction process migrates movable pages to create larger contiguous free areas, similar to disk defragmentation. It involves two scans: one from the bottom collecting allocated movable pages, and another from the top collecting free target pages. When the scans meet, pages are moved to form a contiguous region.

Compaction can be triggered automatically when a high‑order allocation fails after a direct reclaim, or manually by writing to /proc/sys/vm/compact_memory .

2) kcompactd

kcompactd is a background kernel thread that proactively triggers compaction when kswapd is about to sleep and certain conditions are met (e.g., allocation cannot use direct reclaim, node memory is balanced, and kswapd has failed more than MAX_RECLAIM_RETRIES times).

3) Other Optimizations

To further reduce external fragmentation:

Limit the pollution caused by UNMOVABLE pages by restricting their stealing behavior to large allocations only.

Implement a reclamation mechanism where UNMOVABLE pages that have stolen pages later return them when free space becomes available.

Reduce randomness in page‑frame allocation; reserving memory regions for small or large allocations can lower the probability of fragmentation.

These strategies aim to mitigate, though not completely eliminate, external fragmentation in long‑running Linux systems.

References

1. Linux kernel source code 2. http://tinylab.org/lwn-368869/ 3. https://patchwork.kernel.org/patch/