Linux Memory Management Deep Dive: Organization, Allocation Algorithms, Pitfalls & Monitoring

Linux Memory Basics

Memory (main memory) is directly addressable by the CPU, built from semiconductor devices, and characterized by fast access speed. It temporarily stores CPU computation data, exchanges data with external storage like disks, and ensures CPU computing stability and high performance.

Linux Memory Address Space

User Mode vs Kernel Mode

User mode (Ring3): code runs with processor restrictions; each process has its own independent, non-interfering memory space.

Kernel mode (Ring0): core processor state; kernel threads share kernel address space.

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

MMU Address Translation

The Memory Management Unit (MMU) is a hardware circuit with segmentation and paging units. Segmentation converts a logical address to a linear address; paging converts a linear address to a physical address.

Segmentation Mechanism

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

Segment base address: starting address in linear address space.

Segment limit: maximum offset usable within the segment in virtual address space.

Logical address → segment descriptor (from segment register) → base + offset = linear address.

Paging Mechanism (32-bit)

Applied after segmentation; converts linear to physical address.

10-bit page directory, 10-bit page table entry, 12-bit page offset.

Single page size: 4KB.

User Space Layout

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

DATA: initialized global variables.

BSS: uninitialized global variables.

HEAP: runtime heap (malloc allocations).

MMAP: shared libraries and anonymous file mappings.

STACK: user process stack.

Kernel Space Layout

Direct mapping zone: linear space from 3GB, max 896MB, direct memory mapping.

Dynamic mapping zone: allocated via vmalloc.

Permanent mapping zone: accesses high memory.

Fixed mapping zone: near 4GB top, each entry serves specific purposes (e.g., ACPI_BASE).

Process Memory Space

User processes only access user-space virtual addresses; kernel space is mapped by the kernel and does not change per process.

Kernel space has its own page tables; each user process has distinct page tables.

Linux Memory Allocation Algorithms

Memory Fragmentation

Cause: small allocations with long lifetimes, repeated requests create fragmentation. Pros: faster allocation, easier management, prevents leaks. Cons: system slowdown, low memory utilization, waste.

Avoiding Fragmentation

Minimize dynamic allocation (prefer stack).

Allocate and free in same function.

Request large blocks once instead of many small ones.

Prefer power-of-two sizes.

External fragmentation: buddy system.

Internal fragmentation: slab algorithm.

Custom memory pools.

Buddy System — Organization

Provides efficient allocation of contiguous page frames for the kernel, solving external fragmentation.

Allocation unit: page frame.

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

Buddy System — Allocation & Deallocation

Allocation Algorithm

Request 2^i pages; if corresponding list has free block, allocate.

If not, search 2^(i+1) list; if found, split: allocate 2^i to caller, return other 2^i to 2^i list.

Repeat until a free block is found or allocation fails.

Deallocation Algorithm

Release 2^i pages; check buddy list for physically contiguous block of same size.

If none, no merge needed.

If found, merge into 2^(i+1) block; repeat until no merge possible.

Merge conditions: same size, physically contiguous, same page block size.

Allocating >4MB Memory

Large allocations fail more often and are rarely needed. Kernel methods:

Modify MAX_ORDER and recompile kernel.

Boot parameter "mem=" to reserve memory (e.g., mem=80M), then use request_mem_region and ioremap_nocache (non-x86 only).

Call alloc_boot_mem before mem_init in start_kernel (requires recompile).

vmalloc: allocates virtually contiguous but physically non-contiguous memory.

Buddy System — Anti-Fragmentation

Unmovable pages: fixed location, cannot move or reclaim (kernel code/data, kmalloc memory, kernel thread stacks).

Reclaimable pages: cannot move but can be deleted (page cache reclaimed under memory pressure).

Movable pages: can be relocated arbitrarily (user-space pages via page tables); page table entries updated on move.

Slab Allocator — Principles

Based on Jeff Bonwick's algorithm for SunOS.

Caches frequently used kernel objects (e.g., process descriptors) in initialized state for quick reuse.

Internal Fragmentation

Allocated memory larger than requested.

Goals

Reduce internal fragmentation from buddy system for small allocations.

Cache frequent objects to cut allocation/initialization/free overhead.

Use coloring to optimize hardware cache usage.

Slab Allocator Structure

Objects allocated/freed from slabs; slabs move between slab lists.

slabs_empty list: primary candidates for reaping.

Supports generic object initialization to avoid repeated initialization.

Slab Caches

General Caches

Provide small contiguous allocations via geometrically distributed sizes: 32 to 131072 bytes.

Interfaces: kmalloc() and kfree().

Specialized Caches

Full interface set for specific objects.

kmem_cache_create(): creates cache from cache_cache general cache, inserts descriptor into cache_chain list.

kmem_cache_alloc() / kmem_cache_free(): allocate/free slab in specified cache.

Kernel Memory Pools

Pre-allocate equal-sized blocks; draw from pool on demand, expand if empty. Avoids fragmentation, improves allocation efficiency.

mempool_create: create pool object.

mempool_alloc: allocate from pool.

mempool_free: return object to pool.

mempool_destroy: destroy pool.

User-Space Memory Pools

C++ example shown (diagram).

DMA Memory

What is DMA

Direct Memory Access: hardware mechanism allowing peripherals and main memory to transfer I/O data without CPU involvement.

DMA Controller Functions

Assert HOLD signal to request bus ownership.

Control bus after CPU grants HLDA.

Address memory, modify pointers, perform read/write.

Determine transfer byte count, detect completion.

Signal DMA end to return CPU to normal.

DMA Signals

DREQ: peripheral requests DMA.

DACK: controller acknowledges request.

HRQ: controller requests bus from CPU.

HLDA: CPU grants bus to controller.

Memory Usage Scenarios

Page management.

Slab (kmalloc, memory pools).

User-space memory (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.

User-Space Allocation Functions

alloca: stack allocation, no free needed.

malloc: uninitialized memory; may work initially but fail after memory reuse.

calloc: zero-initializes allocated memory.

realloc: extends existing allocation.

If current block sufficient, expands in place, returns same pointer.

If not, allocates new block, copies content, frees old block, returns new pointer.

Kernel-Space Allocation Functions

__get_free_pages : Direct page frame ops; max 4MB; for large contiguous physical memory.

kmem_cache_alloc : Based on slab mechanism; max 128KB; for frequent same-size allocations.

kmalloc : Based on kmem_cache_alloc; max 128KB; most common; small allocations < page size.

vmalloc : Non-contiguous physical → virtual mapping; physically non-contiguous; for large memory without physical contiguity requirement.

dma_alloc_coherent : Based on __alloc_pages; max 4MB; for DMA operations.

ioremap : Known physical → virtual mapping; N/A max; for device drivers with known physical addresses.

alloc_bootmem : Pre-allocate at boot; < physical memory; early boot, high memory management demands.

malloc Internals

malloc searches free_chunk_list (free heap buffer linked list) for a suitable block. If none, calls sys_brk to extend process heap.

Page Fault Handling

Allocate physical page(s) via get_free_pages.

Compute PTE address for faulting address in process page directory.

Set PTE to physical page base address.

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

User Process Memory Access

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

On access to unmapped virtual address, page fault triggers kernel allocation and mapping.

Shared Memory

Allows unrelated processes to access same logical memory. High-efficiency IPC, reduces data copies.

shm Interface

shmget: create shared memory segment.

shmat: attach segment to process address space.

shmdt: detach segment.

Memory Pitfalls

C Memory Leaks

Mismatched new/delete in constructors/destructors.

Failure to clean nested object pointers.

Base class destructor not virtual → derived destructor not called when deleting via base pointer.

Missing copy constructor (value passing invokes copy constructor).

Pointer array ≠ object array; must free each object and each pointer.

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

C Dangling Pointers

Uninitialized pointer variables.

Pointer not set to NULL after free/delete.

Pointer exceeds variable scope (e.g., returning pointer to stack memory).

Dereferencing NULL pointer (always check).

sizeof cannot determine array size when passed as pointer.

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

C Resource Access Conflicts

Shared variables in multithreading without volatile.

Global variable access without locks.

Globals only valid per-process.

Multi-process shared memory writes without synchronization.

mmap memory mapping not process-safe.

STL Iterator Invalidation

Erased iterator becomes invalid.

Insertion (insert/push_back) or deletion invalidates sequence container iterators.

Incorrect: Erasing current iterator invalidates it.

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

C++11 Smart Pointers

auto_ptr replaced by unique_ptr.

Use make_shared to initialize shared_ptr.

weak_ptr helper: lock() obtains strong reference, expired() checks if managed object released, get() accesses raw pointer.

C++11: Smaller, Faster, Safer

std::atomic: atomic types for thread safety.

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

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

std::forward_list: singly-linked list (vs doubly-linked list); saves memory when only forward traversal needed; insertion/deletion faster than list.

std::unordered_map / std::unordered_set: hash-based unordered containers; O(1) insert, delete, lookup; use when element order irrelevant.

Memory Monitoring Tools

System memory info: /proc/meminfo Process memory status: /proc/<pid>/status Overall memory usage: free Process CPU/memory percentages: top Virtual memory statistics: vmstat Process memory consumption sorted: ps aux --sort -rss Release system caches:

/proc/sys/vm/drop_caches

echo 1 > /proc/sys/vm/drop_caches

— free pagecache echo 2 > /proc/sys/vm/drop_caches — free dentries and inodes echo 3 > /proc/sys/vm/drop_caches — free pagecache, dentries, and inodes