Linux Memory Management Part II

In a previous discussion on Linux memory management, Part I, we examined physical memory and saw how Linux divides it into fixed-size pages. With that foundation in place, the next step is to examine how memory allocation works under the hood.

I Earlier in the series Linux Memory Management Part I →

This involves exploring how the Linux memory manager tracks and manages pages at runtime, how page deallocation is handled, and how the kernel maintains contiguous chunks of free memory efficiently. Understanding these mechanics gives kernel developers, systems programmers, and application engineers a clearer view of overall system behavior.

Free lists

In an earlier approach to kernel memory management, different kernel subsystems maintained their own free lists for frequently used data structures. For example, one subsystem could maintain a free list for process-related objects, while another maintained a separate free list for file-system objects.

• Each free list stored unused, previously allocated objects of a particular type.
• When a subsystem needed an object, it took one from its corresponding free list instead of allocating and initializing new memory.
• When the object was no longer needed, the subsystem returned it to the same free list.
• The free lists therefore acted as separate object caches maintained by different parts of the kernel.
• This approach improved allocation speed, but the kernel had no central mechanism for monitoring and shrinking all these independently managed caches when memory became scarce.

Problem with free list

• Independently implemented free lists have no common management mechanism.
• When memory becomes scarce, the kernel cannot centrally ask these unrelated free lists to release cached objects.
• The kernel also lacks information about what each free list stores and how much memory it holds.

Introduction of Slab Allocator in Linux

• Linux introduced the slab allocator to provide a common, kernel-managed object-caching layer.
• The slab allocator centralizes object-cache management and allows cached memory to be reclaimed when required.

The concepts behind slab allocator

The slab allocator is based on the following ideas:

• Cache frequently used kernel objects. Objects that are repeatedly allocated and freed can be retained and reused.
• Reduce repeated setup work. A freed object can be returned to the cache and supplied to a later request without obtaining and preparing fresh memory each time.
• Limit fragmentation. Objects of the same size are organized within slabs made from one or more contiguous pages. This reduces fragmentation.
• Use memory information when organizing caches. The allocator considers object size, page size, alignment and slab size when deciding how objects should be stored.
• Use per-CPU caches. Frequently used objects can be allocated and freed from CPU-local caches, reducing contention on shared locks.

How the slab allocator obtains memory

• The slab allocator manages small kernel objects, but it does not create the underlying physical memory. 
• When an object cache needs a new slab, it requests one or more contiguous pages from the kernel’s page allocator.
• The page allocator uses the buddy system to manage free physical pages. 
• Within the buddy allocator, the free_area[] array organizes free page blocks by order:
  • free_area[0] contains free blocks of 20 = 1 page.
  • free_area[1] contains free blocks of 21 = 2 contiguous pages.
  • free_area[2] contains free blocks of 22 = 4 contiguous pages.
• Higher entries contain progressively larger power-of-two page blocks.

Typical Memory Allocation Path

• A typical request for a kernel object follows this path:
  • The kernel requests a fixed-size object.
  • The slab allocator checks the appropriate object cache.
  • If a free object is available, the slab allocator returns it immediately.
  • If the cache needs another slab, the slab allocator requests one or more pages from the page allocator.
  • The buddy allocator finds a suitable contiguous block of pages.
  • The buddy allocator uses its free_area[] array to organize free page blocks by order.

Allocating pages using the buddy algorithm

• Assume the slab allocator requests four contiguous pages.
• Four pages correspond to order 2:

2²=4 pages

• The buddy allocator first checks the order-2 free list. 
• If a block is available, it removes and returns that block. 
• If the list is empty, it searches higher orders and repeatedly splits a larger block into two equal buddies until it obtains an order-2 block.

If the order-2 free list is empty

• Assume the allocator searches the higher-order free lists and finds an order-4 block containing 16 contiguous pages, numbered 0–15.

The allocator splits the block as follows:

1. The order-4 block is divided into two order-3 buddies:
   • Pages 0–7
   • Pages 8–15
2. One order-3 block is kept free and added to the order-3 free list.
3. The other order-3 block is divided into two order-2 buddies:
   • Pages 0–3
   • Pages 4–7
4. One order-2 block is returned to satisfy the request for four contiguous pages.
5. The unused order-2 buddy is added to the order-2 free list.

After the allocation

• One order-2 block containing four pages has been allocated.
• One order-2 block containing four pages remains free.
• One order-3 block containing eight pages remains free.

The larger 16-page block has therefore been split only as far as necessary to satisfy the four-page request.

Freeing pages and merging buddies

• When a page block is freed, the buddy allocator checks whether its matching buddy is also free and available for merging. 
• The two blocks must have the same order and form the two aligned halves of one larger block.

Suppose an order-2 block containing PFNs 0–3 is freed: 2²=4 pages

Its matching order-2 buddy contains PFNs 4–7.

The buddy is allocated

• If PFNs 4–7 are still allocated, the two blocks cannot be merged. 
• The freed block is added to the order-2 free list:

Order-2 free list: PFNs 0–3

The allocator now has one free block containing four contiguous pages.

The buddy is free

• If PFNs 4–7 are also free, the allocator removes that buddy from the order-2 free list and combines the two blocks: Order 2: PFNs 0–3   and Order 2: PFNs 4–7   into one larger Order 3: PFNs 0–7   block. 

The resulting block contains eight contiguous pages: 2³=8 pages

Checking the next buddy

• The allocator then checks the matching buddy of the new order-3 block. Its buddy contains PFNs 8–15.
• If that block is also free and eligible for merging, the allocator combines the two order-3 blocks: Order 3: PFNs 0–7 and Order 3: PFNs 8–15 into a larger Order 4: PFNs 0–15 block. 
• The resulting order-4 block contains 16 contiguous pages:

2⁴=16 pages

• This repeated merging is called coalescing. 
• The allocator continues checking higher-order buddies until the next buddy cannot be merged or the maximum supported order is reached.
• Coalescing reconstructs larger contiguous free blocks as matching buddy blocks become available.

Summary

Main role of the buddy allocator

• Manages free physical memory at page level.
• Groups free contiguous pages into power-of-two blocks called orders.
• Uses free_area[] to organize available blocks by order.
• Splits a larger block when the requested order is unavailable.
• Merges matching free buddies to rebuild larger contiguous blocks.
• Supplies pages to kernel subsystems, including the slab allocator.

Main role of the slab allocator

• Manages frequently used kernel objects smaller than or built from page allocations.
• Maintains separate object caches for different object types or allocation sizes.
• Divides slab memory into same-sized object slots.
• Returns an available object from an existing slab when possible.
• Reuses freed objects, reducing repeated page allocation and object initialization.
• Requests additional pages when an object cache needs a new slab.

How they work together

• The kernel requests a fixed-size object from the slab allocator.
• The slab allocator checks the appropriate object cache.
• If a free object is available, it returns the object immediately.
• If the cache needs a new slab, it requests pages through the page allocator.
• The buddy allocator obtains a suitable page block from its free lists.
• The slab allocator divides those pages into object slots and returns one object.
• Freed objects return to the slab cache for reuse.
• Unneeded slab pages can eventually return to the buddy allocator.
• The buddy allocator may merge the returned pages with their free buddies.

Key terminologies

• Physical page: A fixed-size unit of physical memory managed by the kernel.
• PFN: Page Frame Number, which identifies a physical page.
• Page allocator: The kernel interface used to request and release physical pages.
• Buddy allocator: Manages free physical pages as contiguous power-of-two blocks.
• Order: Identifies a block size using 2order2^{\text{order}} pages.
• free_area[]: Organizes the buddy allocator’s free page blocks by order.
• Buddy blocks: Equal-sized, correctly aligned blocks that can be merged.
• Splitting: Dividing a larger free block into two smaller buddy blocks.
• Coalescing: Repeatedly merging eligible free buddies into larger blocks.
• Slab allocator: Manages caches of frequently used kernel objects.
• Object cache: A cache dedicated to one object type or allocation size.
• Slab: One or more pages divided into same-sized object slots.
• Object: A reusable kernel data structure stored within a slab.
• Free object: An unused object retained in its cache for a later request.

I Earlier in the series Linux Memory Management Part I →

Reference

Love, R. (2010). Linux Kernel Development (3rd ed.). Addison-Wesley Professional. Chapter 12: Memory Management.