Unlocking Linux Memory: From Basics to Advanced Allocation Algorithms

1. Introduction to Linux Memory

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

2. Linux Memory Organization and Layout

What is memory? Memory (main memory) is directly addressable by the CPU, made of semiconductor devices, and offers fast access rates.

Functions of memory

Temporarily store CPU computation data.

Exchange data with external storage such as disks.

Ensure CPU computation stability and high performance.

2.1 Linux Memory Address Space

The address space is divided into user mode and kernel mode. User mode runs at Ring3, kernel mode at Ring0. Transitions occur via system calls, exceptions, or hardware interrupts. Each process has an independent virtual address space; user programs cannot arbitrarily access kernel space, providing security.

2.2 Memory Address Translation

The MMU converts logical addresses to linear addresses (segmentation) and then to physical addresses (paging). Segmentation uses segment selectors stored in registers cs, ss, ds, es, fs, gs. Paging divides linear addresses into page directories, page tables, and offsets (e.g., 10‑bit directory, 10‑bit table, 12‑bit offset for 4 KB pages).

3. Linux Memory Allocation Algorithms

3.1 Memory Fragmentation

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

Mitigation strategies include:

Prefer stack allocation over dynamic allocation.

Allocate and free memory within the same function.

Allocate larger blocks instead of many small ones.

Use power‑of‑two sized blocks.

Apply the buddy system for external fragmentation.

Use the slab allocator for internal fragmentation.

Design custom memory pools.

3.2 Buddy System

The buddy allocator provides efficient allocation of contiguous pages and reduces external fragmentation. Free pages are grouped into 11 free‑list bins (sizes 1, 2, 4, …, 1024 pages, up to 4 MB). Allocation searches the appropriate bin; if empty, higher‑order bins are split. Deallocation merges buddies when possible.

3.3 Slab Allocator

Derived from the SunOS slab algorithm, the Linux slab allocator caches frequently used kernel objects (e.g., process descriptors). It reduces internal fragmentation, speeds up allocation/initialization, and improves cache locality. Interfaces include kmem_cache_create, kmem_cache_alloc, and kmem_cache_free. Specialized caches (e.g., kmalloc) are built on top of slabs.

3.4 Memory Pools

Kernel memory pools pre‑allocate a set of equal‑sized blocks for fast reuse, reducing fragmentation. APIs: mempool_create, mempool_alloc, mempool_free, mempool_destroy. User‑space pools use similar concepts via custom allocators.

4. Memory Usage Scenarios

Page management (kernel).

Slab/kmalloc and memory pools.

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

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

Kernel‑user data transfer ( copy_from_user, copy_to_user).

Memory‑mapped hardware registers and reserved regions.

DMA memory.

4.1 User‑Space Allocation Functions

alloca

allocates on the stack (no free needed). malloc returns uninitialized memory; calloc zero‑initializes. realloc expands or moves a block, copying data if necessary.

4.2 Kernel‑Space Allocation Functions

Functions include __get_free_pages (page‑frame allocation), kmalloc / kfree (up to 128 KB), vmalloc (non‑contiguous physical memory), dma_alloc_coherent (for DMA), and ioremap (map physical I/O registers).

4.3 Page Fault Handling

When a user process accesses an unmapped virtual address, the kernel allocates a physical page via get_free_pages, updates the page table entry, and resumes execution.

5. Common Pitfalls (Memory "Traps")

5.1 C Memory Leaks

Mismatched new / delete in constructors/destructors.

Missing deletion of nested pointers.

Non‑virtual base class destructors.

Improper copy constructors or assignment operators.

Confusing pointer arrays with object arrays.

5.2 Wild Pointers

Uninitialized pointers.

Using freed pointers without resetting to NULL.

Returning pointers to stack memory.

Dereferencing null pointers.

5.3 Resource Conflicts

Missing volatile on shared variables.

Unsynchronized access to global variables.

Improper shared‑memory synchronization.

5.4 STL Iterator Invalidations

Erasing an element invalidates its iterator; 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.

Employ weak_ptr to avoid cyclic references.

5.6 C++11 Improvements

std::atomic

for lock‑free thread safety. std::array for fixed‑size arrays. std::vector::shrink_to_fit to reduce capacity. std::forward_list for memory‑efficient singly linked lists. std::unordered_map/set for O(1) lookups.

6. Monitoring and Debugging Memory

System memory: /proc/meminfo Process memory: /proc/<pid>/status Overall usage: free Detailed stats: top, vmstat, ps aux --sort -rss Drop caches: echo 1 > /proc/sys/vm/drop_caches (pagecache), echo 2 > /proc/sys/vm/drop_caches (dentries/inodes), echo 3 > /proc/sys/vm/drop_caches (both).