Unlock Linux Memory: From Architecture to Allocation Algorithms

1. Introduction to Linux Memory

Linux memory is a critical resource for backend developers. Proper memory 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

2.1 What is memory? Memory (main storage) is the directly addressable storage for the CPU, made of semiconductor devices, characterized by fast access speed.

2.2 Functions of memory

Temporarily store CPU computation data.

Exchange data with external storage such as disks.

Ensure CPU computation stability and high performance.

2.3 Address space overview

Linux divides memory into user space and kernel space. Each process has an independent virtual address space; user programs cannot arbitrarily access kernel space, providing security isolation.

User mode (Ring3): code runs with limited privileges.

Kernel mode (Ring0): core code runs with full privileges.

Transition methods: system calls, exceptions, hardware interrupts.

2.4 MMU address translation

MMU consists of segmentation and paging units.

Segmentation converts a logical address to a linear address.

Paging converts a linear address to a physical address.

2.5 Segmentation mechanism

Segment selectors are cached in six segment registers: cs, ss, ds, es, fs, gs.

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

Limit defines the maximum offset within the segment.

2.6 Paging mechanism (32‑bit)

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

Page size is 4 KB.

2.7 User‑mode address space layout

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

DATA: initialized global variables.

BSS: uninitialized global variables.

HEAP: dynamically allocated memory (malloc, etc.).

MMAP: memory‑mapped files and shared libraries.

STACK: process stack.

2.8 Kernel‑mode address space

Direct‑mapping area: 3 GB–~3.9 GB (up to 896 MB) for physical memory mapping.

Dynamic memory‑mapping area: allocated by vmalloc.

Permanent mapping area: accesses high memory.

Fixed mapping area: small 4 KB region for special purposes (e.g., ACPI).

2.9 Process memory space User processes can only access their own virtual address space; kernel space is shared among all kernel threads and is not directly accessible from user mode.

3. Linux Memory Allocation Algorithms

Memory management algorithms help developers avoid manual memory handling.

3.1 Memory fragmentation

Caused by many small allocations with long lifetimes.

Pros: faster allocation, easier management, prevents leaks.

Cons: reduced utilization, system slowdown.

3.2 Avoiding fragmentation

Prefer stack allocation (e.g., alloca).

Allocate and free within the same function.

Request larger blocks instead of many small ones.

Use power‑of‑two sized blocks.

External fragmentation: buddy system.

Internal fragmentation: slab allocator.

Design custom memory pools when needed.

3.3 Buddy system

Provides efficient allocation of contiguous pages, solving external fragmentation.

Free pages are grouped into 11 lists for block sizes 1, 2, 4, …, 1024 pages (up to 4 MB).

Allocation: request 2^i pages; if unavailable, split larger blocks.

Freeing: merge adjacent free blocks of the same order.

3.4 Allocating >4 MB

Increase MAX_ORDER and recompile the kernel.

Pass mem= parameter at boot (works on ARM, PowerPC, not x86).

Use request_mem_region and ioremap_nocache for reserved memory.

Pre‑allocate in start_kernel via alloc_boot_mem.

Use vmalloc for virtually contiguous but physically non‑contiguous memory.

3.5 Slab allocator

Originated from Jeff Bonwick’s algorithm for SunOS.

Caches frequently used kernel objects to reduce allocation overhead.

Reduces internal fragmentation compared to buddy system for small objects.

Provides generic caches ( kmem_cache_create, kmem_cache_alloc, kmem_cache_free) and specialized caches.

3.6 Kernel memory pools

Create pool with mempool_create, allocate with mempool_alloc, free with mempool_free, destroy with mempool_destroy.

3.7 User‑mode memory allocation functions alloca: stack allocation, no explicit free. malloc: uninitialized heap memory. calloc: zero‑initialized heap memory. realloc: resize existing allocation, may move memory.

3.8 Kernel‑mode allocation functions __get_free_pages / alloc_pages: allocate contiguous pages. kmalloc / kfree: wrapper around slab for small objects. vmalloc / vfree: non‑contiguous physical memory mapped to contiguous virtual space. dma_alloc_coherent: allocate DMA‑capable memory. ioremap: map known physical addresses. alloc_bootmem: reserve memory early in boot.

3.9 Page fault handling

When a user address lacks a physical mapping, the CPU raises a page‑fault exception.

The kernel allocates a physical page, updates the page table, and resumes the process.

3.10 Shared memory

Allows unrelated processes to access the same logical memory region.

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

4. Memory Usage Scenarios

Page management.

Slab (kmalloc, memory pools).

User‑mode allocations (malloc, realloc, file mapping, shared memory).

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

Data transfer between kernel and user ( copy_from_user, copy_to_user).

Memory‑mapped hardware registers and reserved memory.

DMA memory.

5. Common Pitfalls

5.1 C memory leaks

Mismatched new / delete in constructors/destructors.

Failing to delete nested pointers.

Non‑virtual base destructors causing derived destructors not to run.

Missing copy constructors leading to shallow copies.

Confusing pointer arrays with object arrays.

Missing overloaded assignment operator.

5.2 C wild pointers

Uninitialized pointers.

Using freed pointers without resetting to NULL.

Returning pointers to stack memory.

Dereferencing null pointers.

Incorrect sizeof on arrays.

Modifying string literals.

5.3 Resource conflicts

Missing volatile on shared variables.

Unprotected global variables in multithreaded code.

Improper synchronization for shared memory.

Unsafe mmap usage across processes.

5.4 STL iterator invalidation

Erasing an element invalidates its iterator.

Insertions or deletions can invalidate iterators of sequential 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 (methods: lock(), expired(), get()).

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

6. Monitoring and Managing Memory

System memory info: /proc/meminfo.

Process memory status: /proc/<pid>/status.

Overall usage: free.

CPU and memory per process: top.

Virtual memory stats: vmstat.

Sort processes by RSS: ps aux --sort -rss.

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

Source: 人人都是极客