Unlocking Linux Memory: From Address Spaces to Allocation Algorithms

1. Getting into Linux Memory

Linux memory is a crucial resource for backend developers; proper usage improves system performance and stability. This article introduces Linux memory organization, page layout, causes of memory fragmentation, optimization algorithms, kernel memory management methods, usage scenarios, and common pitfalls.

2. Linux Memory Address Space

Linux divides memory into user space and kernel space. User space runs in Ring 3 and cannot directly access kernel addresses, providing protection. Kernel space runs in Ring 0 and is shared among all kernel threads.

Three ways to switch from user to kernel mode: system calls, exceptions, and hardware interrupts.

Memory address translation is performed by the MMU, which first converts a logical address to a linear address (segmentation) and then to a physical address (paging).

Segmentation uses segment selectors stored in six segment registers (cs, ss, ds, es, fs, gs). Each segment has a base address and a limit defining the maximum offset.

Paging (32‑bit) splits the linear address into a 10‑bit page directory, a 10‑bit page table entry, and a 12‑bit offset, yielding 4 KB pages.

3. Linux Memory Allocation Algorithms

Linux provides several allocation mechanisms to reduce fragmentation and improve efficiency.

3.1 Memory Fragmentation

Fragmentation occurs when many small allocations with long lifetimes leave unusable gaps, reducing performance and memory utilization.

To avoid fragmentation: minimize dynamic allocations, allocate and free memory within the same function, request larger blocks, use power‑of‑two sizes, employ the buddy system, use the slab allocator, or design custom memory pools.

3.2 Buddy System

The buddy system manages memory in blocks of sizes 2^i pages, maintaining 11 free‑list chains for block sizes from 1 to 1024 pages (up to 4 MB). Allocation searches the appropriate list; if empty, larger blocks are split. Deallocation merges adjacent free buddies.

3.3 Slab Allocator

The slab allocator, derived from the SunOS Bonwick algorithm, caches frequently used kernel objects (e.g., process descriptors) to reduce allocation overhead. It maintains caches (slabs) that can be reclaimed, and provides kmalloc/kfree interfaces for up to 128 KB allocations.

3.4 Kernel Memory Pools

Kernel memory pools pre‑allocate a set of equal‑sized blocks for fast allocation, reducing fragmentation. APIs include mempool_create, mempool_alloc, mempool_free, and mempool_destroy.

3.5 DMA Memory

Direct Memory Access (DMA) allows peripherals to transfer data to/from main memory without CPU involvement. The DMA controller handles bus arbitration, address translation, transfer size, and completion signaling (DREQ, DACK, HRQ, HLDA).

4. Memory Usage Scenarios

Page management (allocating/freeing pages).

Slab (kmalloc, memory pools).

User‑space allocation (malloc, calloc, realloc, mmap, shared memory).

Process memory map (stack, heap, code, data).

Kernel‑user data transfer (copy_from_user, copy_to_user).

Memory‑mapped hardware registers and reserved memory.

DMA buffers.

4.1 User‑Space Allocation Functions

alloca allocates on the stack; malloc returns uninitialized memory; calloc returns zero‑filled memory; realloc expands or moves an existing allocation.

4.2 Kernel‑Space Allocation Functions

get_free_pages allocates contiguous physical pages; kmalloc/kmem_cache_alloc use the slab allocator; vmalloc creates virtually contiguous but physically non‑contiguous memory; dma_alloc_coherent provides DMA‑safe buffers; ioremap maps known physical addresses; alloc_bootmem reserves memory early in boot.

4.3 Page Fault Handling

When a user process accesses an unmapped virtual address, the CPU raises a page‑fault exception. The kernel allocates a physical page, updates the page table entry, and resumes execution. System calls such as brk (for small allocations) and do_map (for larger allocations) are used.

4.4 Shared Memory

Shared memory allows unrelated processes to map the same physical memory region, enabling fast inter‑process communication. The shmget, shmat, and shmdt APIs manage creation, attachment, and detachment.

5. Common Memory Pitfalls

5.1 C Memory Leaks

Missing matching new/delete in constructors/destructors.

Failing to delete nested object pointers.

Non‑virtual base class destructors.

Missing copy constructors or assignment operators.

Confusing pointer arrays with object arrays.

5.2 Wild Pointers

Uninitialized pointers.

Using pointers after free/delete without setting to NULL.

Returning pointers to stack‑allocated memory.

Dereferencing null pointers.

5.3 Resource Access Conflicts

Shared variables without volatile or proper locking.

Global variables accessed by multiple threads without synchronization.

Multiple processes writing to shared memory without coordination.

5.4 STL Iterator Invalidations

Erasing elements invalidates iterators; store the next iterator before erasing.

5.5 Modern C++ Smart Pointers

Replace auto_ptr with unique_ptr.

Use make_shared to create shared_ptr.

Use weak_ptr to break reference cycles; lock() obtains a strong reference, expired() checks validity.

5.6 C++11 Improvements

std::atomic for lock‑free thread‑safe variables.

std::array for fixed‑size arrays with lower overhead.

std::vector::shrink_to_fit() to reduce capacity.

std::forward_list for memory‑efficient singly linked lists.

std::unordered_map/set for O(1) average lookup.

6. Monitoring Memory Usage

/proc/meminfo – system memory statistics.

/proc/<pid>/status – per‑process memory usage.

free – overall memory usage.

top – process CPU and memory consumption.

vmstat – virtual memory statistics.

ps aux --sort -rss – list processes by memory usage.

echo 1 > /proc/sys/vm/drop_caches – free page cache.

echo 2 > /proc/sys/vm/drop_caches – free dentries and inodes.

echo 3 > /proc/sys/vm/drop_caches – free all caches.

Source: Translated from a Chinese article originally published by “一口Linux”.