Mastering Linux Memory Management: From Address Space to Allocation Algorithms

1. Introduction to Linux Memory

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

2. Linux Memory Address Space

2.1 Overall Layout

The Linux address space is divided into user‑mode and kernel‑mode regions, each with independent virtual memory. User processes cannot directly access kernel addresses, providing security isolation.

2.2 User‑Mode vs. Kernel‑Mode

User‑mode runs at Ring 3 and is subject to processor protection.

Kernel‑mode runs at Ring 0 with full hardware access.

Transition from user to kernel occurs via system calls, exceptions, or hardware interrupts.

2.3 MMU Address Translation

Segmentation converts a logical address to a linear address.

Paging converts a linear address to a physical address.

2.4 Segmentation Details

Segment selector registers (cs, ss, ds, es, fs, gs) cache selectors.

Base address defines the start of a segment in linear space.

Limit defines the maximum offset within the segment.

2.5 Paging (32‑bit)

Page directory (10 bits) + page table (10 bits) + offset (12 bits).

Page size is 4 KB.

2.6 User‑Mode Address Space Layout

TEXT: executable code, string literals, read‑only data.

DATA: initialized global variables.

BSS: uninitialized global variables.

HEAP: dynamic allocations via malloc etc.

MMAP: shared libraries and file mappings.

STACK: process stack.

2.7 Kernel‑Mode Address Space Layout

Direct‑mapped region (≈896 MiB starting at 3 GiB).

vmalloc‑mapped dynamic region.

Permanent mapping for high memory.

Fixed mappings for special purposes (e.g., ACPI).

2.8 Process Memory Space

User processes see only their own virtual address space.

Kernel space is shared among all processes and has its own page tables.

3. Linux Memory Allocation Algorithms

3.1 Fragmentation

Caused by many small, long‑lived allocations.

External fragmentation wastes memory and slows the system.

Internal fragmentation occurs when allocated blocks are larger than needed.

3.2 Avoiding Fragmentation

Prefer stack allocation or allocate large blocks.

Allocate and free memory within the same function when possible.

Use power‑of‑two sized blocks.

Apply the buddy system for external fragmentation.

Use the slab allocator for internal fragmentation.

Design custom memory pools for specific workloads.

3.3 Buddy System

Organises free pages into 11 linked lists, each representing block sizes of 2⁰ to 2¹⁰ pages (up to 4 MiB).

Allocation: find the smallest suitable block; if unavailable, split larger blocks.

Freeing: coalesce adjacent free blocks of the same order.

3.4 Slab Allocator

Originated from Jeff Bonwick’s SunOS slab algorithm.

Caches frequently used kernel objects (e.g., process descriptors) to reduce allocation overhead.

Provides per‑CPU caches, reduces internal fragmentation, and improves cache locality.

APIs: kmem_cache_create, kmem_cache_alloc, kmem_cache_free, kmem_cache_destroy.

4. Memory Usage Scenarios

Page management (kernel page allocator).

Slab / kmalloc / memory pools.

User‑space allocations: malloc, realloc, file mapping, shared memory.

Process memory map: stack, heap, code, data.

Kernel‑to‑user data transfer: copy_from_user, copy_to_user.

Memory‑mapped I/O and reserved regions.

DMA buffers.

5. Common Pitfalls

5.1 C Memory Leaks

Missing matching new / delete in constructors/destructors.

Non‑virtual base destructors causing derived objects not to be destroyed.

Absent copy constructors leading to shallow copies.

Improper handling of pointer arrays.

5.2 C Wild Pointers

Uninitialized pointers.

Use‑after‑free without resetting to NULL.

Returning pointers to stack memory.

Dereferencing null pointers.

5.3 Resource Conflicts

Missing volatile on shared variables.

Unprotected global variables in multithreaded code.

Unsynchronized shared‑memory writes.

5.4 STL Iterator Invalidation

Erasing an element invalidates its iterator.

Insertions or deletions may invalidate iterators of sequence containers.

5.5 C++11 Smart Pointers

Replace auto_ptr with unique_ptr.

Use make_shared to create shared_ptr. weak_ptr provides non‑owning references; use lock(), expired(), get().

5.6 Modern C++ Utilities std::atomic for lock‑free thread‑safe variables. std::array for fixed‑size arrays. std::vector::shrink_to_fit() to reduce capacity. std::forward_list as a memory‑efficient singly linked list. std::unordered_map/set for O(1) average lookup.

6. Inspecting Memory Usage

System‑wide info: /proc/meminfo.

Process‑specific info: /proc/<pid>/status.

Overall usage: free, top, ps aux --sort -rss.

Virtual memory stats: vmstat.

Drop caches: write 1, 2, or 3 to /proc/sys/vm/drop_caches.