Linux Memory Management Deep Dive: Address Spaces, Allocation Algorithms, and Common Pitfalls

1. Understanding Linux Memory

Memory (RAM) is directly addressable by the CPU, made of semiconductor devices, with fast access speed. It temporarily stores CPU computation data, exchanges data with external storage, and ensures CPU stability and performance.

2. Linux Memory Address Space

2.1 User Mode vs Kernel Mode

User mode (Ring3): restricted, each process has independent memory space.

Kernel mode (Ring0): privileged, kernel threads share kernel address space.

Three ways to switch: system calls, exceptions, hardware interrupts.

2.2 MMU Address Translation

MMU hardware with segmentation and paging units.

Segmentation converts logical address to linear address.

Paging converts linear address to physical address.

2.3 Segmentation Mechanism

Segment selector cached in 6 segment registers (cs, ss, ds, es, fs, gs).

Segment descriptor provides base address and limit.

Linear address = segment base + offset.

2.4 Paging Mechanism (32-bit)

Two-level page table: 10-bit page directory, 10-bit page table, 12-bit page offset.

Page size 4KB.

2.5 User Space Layout

TEXT: code, string literals, read-only variables.

DATA: initialized global variables.

BSS: uninitialized global variables.

HEAP: runtime heap via malloc.

MMAP: shared libraries and anonymous file mappings.

STACK: user process stack.

2.6 Kernel Space Layout

Direct mapping zone: 3GB to 3GB+896MB, direct physical mapping.

Dynamic mapping zone: vmalloc allocations.

Permanent mapping zone: accesses high memory.

Fixed mapping zone: near 4GB top, specific purposes like ACPI_BASE.

2.7 Process Memory Space

User processes access only user virtual addresses; kernel space mapped by kernel, static across processes.

Kernel has its own page tables; each user process has separate page tables.

3. Linux Memory Allocation Algorithms

3.1 Memory Fragmentation

Cause: small allocations with long lifetimes, repeated requests.

Pros: faster allocation, easier management, prevents leaks.

Cons: system slowdown, low memory utilization, waste.

Avoidance: minimize dynamic allocation (use stack), allocate/free in same function, request large blocks once, prefer power-of-two sizes, buddy system for external fragmentation, slab for internal fragmentation, custom memory pools.

3.2 Buddy System Algorithm

Organization

Provides efficient allocation of contiguous page frames, solves external fragmentation.

Allocates in page-frame units.

Free pages grouped into 11 block lists: sizes 1,2,4,8,16,32,64,128,256,512,1024 contiguous page frames (max 4MB).

Allocation Algorithm

Request 2^i pages: if free block in list i, allocate.

Else search higher-order list (i+1), split block, allocate one half, return other to list i.

Repeat until found or fail.

Free Algorithm

Release 2^i block, check buddy (same size, physically contiguous).

If buddy free, merge into 2^(i+1) block, repeat up the lists.

Merge conditions: same size, contiguous physical addresses.

3.3 Allocating >4MB Memory

Limit reasons: larger allocations more likely to fail; large contiguous memory rarely needed.

Methods: increase MAX_ORDER and recompile kernel; boot parameter "mem=" to reserve memory (non-x86 only); alloc_bootmem before mem_init (recompile); vmalloc for virtually contiguous but physically non-contiguous memory.

3.4 Anti-Fragmentation: Page Mobility Groups

Unmovable pages: fixed location, non-reclaimable (kernel code, data, kmalloc allocations, kernel thread stacks).

Reclaimable pages: cannot move but can be dropped (page cache, etc.).

Movable pages: can be relocated via page table updates (user-space pages).

3.5 Slab Allocator Basics

Origin: Jeff Bonwick for SunOS.

Idea: cache frequently used kernel objects (e.g., task_struct) in initialized state to avoid repeated initialization.

Internal fragmentation: allocated memory larger than requested.

Goals: reduce internal fragmentation from buddy system for small allocations; cache objects to reduce allocation/init/free overhead; use coloring for hardware cache efficiency.

3.6 Slab Structure

Slabs move between empty, partial, full lists.

Empty slabs are primary candidates for reclaiming.

Supports generic object initialization to avoid repeated initialization.

3.7 Slab Caches

General Caches

Provide small contiguous allocations via kmalloc/kfree.

Object sizes geometrically distributed from 32 to 131072 bytes.

Specific Caches

kmem_cache_create() creates cache for specific object, allocates descriptor from cache_cache, adds to cache_chain.

kmem_cache_alloc()/kmem_cache_free() allocate/free objects from specific cache.

3.8 Kernel Memory Pools (mempool)

Pre-allocate fixed-size blocks; draw from pool, expand if needed.

Reduces fragmentation, improves allocation efficiency.

APIs: mempool_create, mempool_alloc, mempool_free, mempool_destroy.

3.9 User-Space Memory Pools

Example C++ implementation shown (image).

3.10 DMA Memory

DMA: hardware mechanism for direct peripheral-to-memory transfers without CPU.

DMA controller functions: request bus (HOLD), take control, address memory, count bytes, signal completion.

Signals: DREQ (request), DACK (acknowledge), HRQ (bus request), HLDA (bus grant).

4. Memory Usage Scenarios

Page management

Slab (kmalloc, memory pools)

User-space allocation (malloc, realloc, file mapping, shared memory)

Program memory map (stack, heap, code, data)

Kernel-user data transfer (copy_from_user, copy_to_user)

Memory mapping (hardware registers, reserved memory)

DMA memory

4.1 User-Space Allocation Functions

alloca: stack allocation, auto-freed.

malloc: uninitialized memory; may cause issues after memory reuse.

calloc: zero-initialized.

realloc: extend existing block; if contiguous space available, extend in place; else allocate new block, copy, free old.

4.2 Kernel-Space Allocation Functions

__get_free_pages: direct page frame ops, max 4MB, for large contiguous physical memory.

kmem_cache_alloc: slab-based, max 128KB, for frequent same-size allocations.

kmalloc: based on kmem_cache_alloc, max 128KB, most common for sub-page allocations.

vmalloc: maps non-contiguous physical to contiguous virtual, for large memory without physical contiguity requirement.

dma_alloc_coherent: based on alloc_pages, max 4MB, for DMA operations.

ioremap: maps known physical to virtual, for device drivers.

alloc_bootmem: early boot reservation, hidden from kernel, high management requirements.

4.3 malloc Internals

malloc searches free_chunk_list for suitable block.

free_chunk_list maintains free heap buffer linked list.

If no fit, uses sys_brk to extend heap.

4.4 Page Fault Handling

Allocate physical pages via get_free_pages.

Calculate PTE address in process page directory.

Set PTE to physical page address.

System calls: brk for ≤128KB, do_mmap for >128KB.

4.5 User Process Memory Access

Each process has private virtual address space; same virtual addresses in different processes map to different physical pages.

On access to unmapped virtual address, page fault triggers kernel to allocate physical page and establish mapping.

4.6 Shared Memory

Allows unrelated processes to access same logical memory.

High-efficiency IPC, reduces data copies.

Interfaces: shmget (create), shmat (attach), shmdt (detach).

5. Common Memory Pitfalls

5.1 C/C++ Memory Leaks

Mismatched new/delete in constructors/destructors.

Failure to clean nested object pointers.

Non-virtual base class destructor: deleting derived via base pointer leaks derived resources.

Missing copy constructor: pass-by-value invokes copy constructor, pass-by-reference does not.

Pointer array vs object array: must free each object and each pointer.

Missing assignment operator overload: shallow copy causes leaks for variable-sized classes.

5.2 C Wild Pointers

Uninitialized pointer variables.

Pointer not set to NULL after free/delete.

Pointer exceeds variable scope (e.g., returning stack address).

Dereferencing NULL pointer (need null checks).

sizeof cannot determine array size when passed as pointer.

Attempting to modify string literals (e.g., char *p="123"; p[0]='1').

5.3 C Resource Access Conflicts

Shared variables across threads without volatile.

Global variable access without locks.

Global variables only valid per-process.

Multi-process shared memory writes without synchronization.

mmap memory mapping not process-safe.

5.4 STL Iterator Invalidation

Erased iterator becomes invalid.

Insertion/deletion invalidates iterators in sequence containers.

Incorrect: erasing current iterator in loop invalidates it.

Correct: save next iterator before erase (e.g., it = vec.erase(it)).

5.5 C++11 Smart Pointers

auto_ptr replaced by unique_ptr (exclusive ownership).

Use make_shared to initialize shared_ptr (single allocation for control block and object).

weak_ptr: helper to break cycles; lock() obtains shared_ptr, expired() checks if object released, get() accesses raw pointer.

weak_ptr control block contains weak count and strong count.

5.6 C++11: Smaller, Faster, Safer

std::atomic: thread-safe atomic types.

std::array: fixed-size array, lower overhead than vector, size fixed.

std::vector::shrink_to_fit(): reduces capacity to size.

std::forward_list: singly-linked list (vs doubly-linked list), saves memory when only forward traversal needed, faster insert/delete.

std::unordered_map/unordered_set: hash-based, O(1) insert/delete/find, better performance when order irrelevant.

6. Monitoring Memory Usage

System memory: /proc/meminfo Process memory: /proc/<pid>/status Overall usage: free Per-process CPU/memory: top Virtual memory stats: vmstat Process memory sorted by RSS: ps aux --sort -rss Drop caches: echo 1 > /proc/sys/vm/drop_caches (pagecache), echo 2 (dentries/inodes), echo 3 (all).