Follow and star our public account to access exciting content
Source: Online materials
Key content:
☆ Linux memory organization structure and page layout, causes of memory fragmentation and optimization algorithms.
☆ Various memory management methods in the Linux kernel, memory usage scenarios, and pitfalls in memory usage.
☆ From the principles and structure of memory to algorithm optimization and usage scenarios, exploring the mechanisms and mysteries of memory management.
Understanding Linux Memory
1. What is Memory?
1) Memory, also known as main memory, is the storage space that the CPU can directly address, made from semiconductor devices.
2) The characteristic of memory is its fast access speed.
2. The Role of Memory
1) Temporarily stores the computation data of the CPU.
2) Data exchanged with external storage devices like hard drives.
3) Ensures the stability and high performance of CPU calculations.
Linux Memory Address Space
1. Linux Memory Address Space Overview
2. Memory Address – User Mode & Kernel Mode
· User Mode: Ring 3 code running in user mode is subject to many restrictions by the processor.
· Kernel Mode: Ring 0 is the core mode in the processor’s memory protection.
· Three ways to switch from user mode to kernel mode: system calls, exceptions, and device interrupts.
· Difference: Each process has its own independent, non-interfering memory space; user mode programs cannot arbitrarily access kernel address space, providing a certain level of security; kernel mode threads share the kernel address space.
3. Memory Address – MMU Address Translation
· MMU is a hardware circuit that includes two components: a segmentation unit and a paging unit.
· The segmentation mechanism converts a logical address to a linear address.
· The paging mechanism converts a linear address to a physical address.
4. Memory Address – Segmentation Mechanism
1) Segment Selector
· To facilitate quick retrieval of segment selectors, the processor provides six segment registers to cache segment selectors: cs, ss, ds, es, fs, and gs.
· Segment Base Address: The starting address of the segment in the linear address space.
· Segment Limit: The maximum offset that can be used within the segment in the virtual address space.
2) Segmentation Implementation
· The value in the segment register of the logical address provides the segment descriptor, from which the segment base and limit are obtained, and then the logical address offset is added to obtain the linear address.
5. Memory Address – Paging Mechanism (32-bit)
· The paging mechanism occurs after segmentation, further converting the linear address to a physical address.
· 10 bits for page directory, 10 bits for page table entries, and 12 bits for page offset.
· The size of a single page is 4KB.
6. User Mode Address Space
· TEXT: Executable code, string literals, read-only variables in the code segment.
· DATA: Data segment, mapping initialized global variables in the program.
· BSS Segment: Stores uninitialized global variables in the program.
· HEAP: Runtime heap, memory area allocated using malloc during program execution.
· MMAP: Mapped area for shared libraries and anonymous files.
· STACK: User process stack.
7. Kernel Mode Address Space
· Direct Mapping Area: The linear space starting from 3G, with a maximum range of 896M, is the direct memory mapping area.
· Dynamic Memory Mapping Area: This area is allocated by the kernel function vmalloc.
· Permanent Memory Mapping Area: This area can access high memory.
· Fixed Mapping Area: This area has only a 4k isolation band from the top of 4G, with each address item serving a specific purpose, such as ACPI_BASE, etc.
8. Process Memory Space
· User processes typically can only access the virtual addresses in user space and cannot access the virtual addresses in kernel space.
· The kernel space is mapped by the kernel and does not change with the process; the kernel space addresses have their own corresponding page tables, while user processes each have different page tables.
Linux Memory Allocation Algorithms
Memory management algorithms are a godsend for those who dislike managing memory themselves.
1. Memory Fragmentation
1) Basic Principles
· Causes: Memory allocation is small, and the allocated small memory has a long lifespan, leading to memory fragmentation after repeated requests.
· Advantages: Increases allocation speed, facilitates memory management, and prevents memory leaks.
· Disadvantages: A large amount of memory fragmentation can slow down the system, reduce memory utilization, and cause significant waste.
2) How to Avoid Memory Fragmentation
· Minimize the use of dynamic memory allocation functions (try to use stack space).
· Allocate and free memory in the same function whenever possible.
· Try to request larger memory blocks at once instead of repeatedly requesting small memory.
· Whenever possible, request large blocks of memory in powers of two.
· Avoid external fragmentation – Buddy System Algorithm.
· Avoid internal fragmentation – Slab Algorithm.
· Manage memory yourself by designing a memory pool.
2. Buddy System Algorithm – Organizational Structure
1) Concept
· Provides an efficient allocation strategy for the kernel to allocate a group of contiguous pages and effectively solves the external fragmentation problem.
· The allocated memory area is based on page frames.
2) External Fragmentation
· External fragmentation refers to memory free areas that have not been allocated (not belonging to any process) but are too small to be allocated to new processes requesting memory space.
3) Organizational Structure.
· All free pages are grouped into 11 block linked lists, each containing blocks of contiguous pages of sizes 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024 page frames. The maximum allocable size is 1024 contiguous pages, corresponding to 4MB of contiguous memory.
3. Buddy System Algorithm – Allocation and Reclamation
1) Allocation Algorithm
· Request storage space for 2^i page blocks; if the block linked list corresponding to 2^i has free page blocks, allocate them to the application.
· If there are no free page blocks, check if the block linked list corresponding to 2^(i-1) has free page blocks; if so, allocate 2^i block linked list nodes to the application, and insert the other 2^i block linked list nodes into the corresponding block linked list.
· If there are no free page blocks in the 2^(i-1) block linked list, repeat step 2 until a block linked list with free page blocks is found.
· If still none are found, return memory allocation failure.
2) Reclamation Algorithm
· Release 2^i page block storage space, check if there are contiguous page blocks with the same physical address in the 2^i block linked list; if not, no need to merge.
· If there are, merge them into 2^(i-1) page blocks, and continue checking the next level block link until no further merging is possible.
3) Conditions
· Two blocks must be of the same size.
· Their physical addresses must be contiguous.
· Page block sizes must be the same.
4. How to Allocate Memory Over 4MB?
1) Why is there a limit on large memory allocation?
· The larger the allocated memory, the greater the chance of failure.
· Large memory blocks have fewer usage scenarios.
2) Methods to obtain large memory over 4MB in the kernel
· Modify MAX_ORDER and recompile the kernel.
· Pass the “mem=” parameter during kernel startup, such as “mem=80M” to reserve part of the memory; then use
· request_mem_region and ioremap_nocache to map the reserved memory into the module. This method requires modifying kernel startup parameters and does not require recompiling the kernel, but it does not support x86 architecture, only ARM, PowerPC, and other non-x86 architectures.
· Call alloc_boot_mem before the mem_init function in start_kernel to pre-allocate large memory blocks, which requires recompiling the kernel.
· The vmalloc function is used by kernel code to allocate memory that is contiguous in virtual memory but not necessarily contiguous in physical memory.
5. Buddy System – Anti-fragmentation Mechanism
1) Non-movable Pages
· These pages have fixed positions in memory and cannot be moved or reclaimed.
· Kernel code segments, data segments, memory allocated by kernel kmalloc(), memory occupied by kernel threads, etc.
2) Reclaimable Pages
· These pages cannot be moved but can be deleted. The kernel reclaims pages when they occupy too much memory or when memory is scarce.
3) Movable Pages
· These pages can be moved freely, and pages used by user-space applications belong to this category. They are mapped through page tables.
· When they are moved to a new location, the page table entries are updated accordingly.
6. Slab Algorithm – Basic Principles
1) Basic Concept
· The slab allocator used in Linux is based on an algorithm first introduced by Jeff Bonwick for the SunOS operating system.
· Its basic idea is to place frequently used objects in the kernel into a cache, maintained by the system in an initially available state. For example, process descriptors are frequently requested and released in the kernel.
2) Internal Fragmentation
· The allocated memory space is larger than the requested memory space.
3) Basic Goals
· Reduce internal fragmentation caused by the buddy algorithm when allocating small blocks of contiguous memory.
· Cache frequently used objects to reduce the time overhead of allocating, initializing, and releasing objects.
· Use coloring techniques to adjust objects for better utilization of hardware caches.
7. Structure of the Slab Allocator
· Since objects are allocated and released from slabs, a single slab can move between slab lists.
· Slabs in the slabs_empty list are the main candidates for reclamation (reaping).
· The slab also supports the initialization of generic objects, avoiding the need to reinitialize an object for the same purpose.
8. Slab Cache
1) General Cache
· The allocation of small blocks of contiguous memory provided by the slab allocator is achieved through a general cache.
· The general cache provides objects of geometrically distributed sizes, ranging from 32 to 131072 bytes.
· The kernel provides two interfaces, kmalloc() and kfree(), for memory allocation and release, respectively.
2) Specialized Cache
· The kernel provides a complete set of interfaces for allocation and release of specialized caches, allocating slab caches for specific objects based on the parameters passed in.
· kmem_cache_create() is used to create a cache for a specified object. It allocates a cache descriptor from the cache_cache general cache for the new specialized cache and inserts this descriptor into the cache_chain list formed by cache descriptors.
· kmem_cache_alloc() allocates a slab from the cache specified in its parameters. Conversely, kmem_cache_free() releases a slab from the cache specified in its parameters.
9. Kernel Mode Memory Pool
1) Basic Principles
· First, allocate a certain number of memory blocks of equal size (generally) as a reserve.
· When there is a new memory demand, a portion of memory blocks is allocated from the memory pool; if the memory blocks are insufficient, new memory is requested.
· One significant advantage of this approach is that it minimizes memory fragmentation, improving memory allocation efficiency.
2) Kernel API
· mempool_create creates a memory pool object.
· mempool_alloc allocates a function to obtain that object.
· mempool_free releases an object.
· mempool_destroy destroys the memory pool.
10. User Mode Memory Pool
1) C++ Example
11. DMA Memory
1) What is DMA?
· Direct Memory Access is a hardware mechanism that allows peripheral devices to directly transfer their I/O data to and from main memory without the involvement of the system processor.
2) Functions of the DMA Controller.
· Can issue a system hold (HOLD) signal to the CPU, requesting bus takeover.
· When the CPU issues a signal allowing takeover, it takes control of the bus and enters DMA mode.
· Can address memory and modify address pointers to perform read and write operations on memory.
· Can determine the number of bytes for this DMA transfer and judge whether the DMA transfer has ended.
· Issues a DMA end signal to allow the CPU to resume normal operation.
2) DMA Signals
· DREQ: DMA request signal. It is the signal from the peripheral to the DMA controller requesting DMA operation.
· DACK: DMA acknowledgment signal. It is the signal from the DMA controller to the requesting peripheral indicating that the request has been received and is being processed.
· HRQ: The signal from the DMA controller to the CPU requesting bus takeover.
· HLDA: The signal from the CPU to the DMA controller allowing bus takeover.
Memory Usage Scenarios
Is the era of out of memory over? No, even with sufficient memory, it should not be used recklessly.
1. Memory Usage Scenarios
· Page management.
· Slab (kmalloc, memory pool).
· User mode memory usage (malloc, realloc, file mapping, shared memory).
· Program memory map (stack, heap, code, data).
· Data transfer between kernel and user mode (copy_from_user, copy_to_user).
· Memory mapping (hardware registers, reserved memory).
· DMA memory.
2. User Mode Memory Allocation Functions
· alloca requests memory from the stack, so it does not need to be released.
· Memory allocated by malloc is uninitialized; programs using malloc() may run normally at first (when the memory space has not been reallocated) but may encounter issues after some time (when the memory space has been reallocated).
· calloc initializes every bit of the allocated memory space to zero.
· realloc expands the size of existing memory space.
a) If the current contiguous memory block is sufficient for realloc, it simply enlarges the space pointed to by p and returns the pointer address of p. At this point, q and p point to the same address.
b) If the current contiguous memory block is insufficient, it finds a new sufficiently long space, allocates a new memory block, q, copies the content pointed to by p to q, returns q, and deletes the memory space pointed to by p.
3. Kernel Mode Memory Allocation Functions
Function allocation principles for maximum memory other_get_free_pages directly operate on page frames suitable for allocating large amounts of contiguous physical memory. kmem_cache_alloc is based on the slab mechanism and is suitable for frequently allocating and releasing memory blocks of the same size. kmalloc is based on kmem_cache_alloc and is the most common allocation method, suitable for memory less than page frame size. vmalloc establishes a mapping of non-contiguous physical memory to virtual addresses, suitable for large memory needs where address continuity is not required. dma_alloc_coherent is based on _alloc_pages and is suitable for DMA operations. ioremap implements the mapping from known physical addresses to virtual addresses, suitable for cases where the physical address is known, such as device drivers. alloc_bootmem reserves a segment of memory during kernel startup, which is invisible to the kernel and requires high memory management.
4. Memory Allocation with malloc
· When calling the malloc function, it searches the free_chunk_list linked list for a memory block large enough to satisfy the user’s request.
· The main job of the free_chunk_list linked list is to maintain a linked list of free heap space buffers.
· If the space buffer linked list does not find the corresponding node, it needs to extend the process’s stack space through the system call sys_brk.
5. Page Faults
· Request one or more physical pages through get_free_pages.
· Calculate the pte address in the process’s pdg mapping where addr is located.
· Set the pte corresponding to addr to the physical page’s starting address.
· System calls: Brk – request memory less than or equal to 128kb, do_map – request memory greater than 128kb.
6. User Process Memory Access Analysis
· User mode processes exclusively occupy virtual address space; two processes can have the same virtual address.
· When accessing user mode virtual address space, if there is no mapped physical address, a page fault is triggered through a system call.
· The page fault traps into the kernel, allocates physical address space, and establishes a mapping with the user mode virtual address.
7. Shared Memory
1) Principle
· It allows multiple unrelated processes to access the same portion of logical memory.
· Sharing memory between two running processes is an extremely efficient solution for data transfer.
· Sharing data between two running processes is an efficient method of inter-process communication, effectively reducing the number of data copies.
2) shm Interface
· shmget creates shared memory.
· shmat starts access to the shared memory and connects it to the current process’s address space.
· shmdt detaches the shared memory from the current process.
Memory Usage Pitfalls
1. C Memory Leaks
· Not matching calls to new and delete in class constructors and destructors.
· Not properly clearing nested object pointers.
· Not defining the base class destructor as a virtual function.
· When a base class pointer points to a subclass object, if the base class destructor is not virtual, the subclass destructor will not be called, and the subclass’s resources will not be properly released, leading to memory leaks.
· Missing copy constructors; passing by value will call (copy) constructors, while passing by reference will not.
· An array of pointers to objects is not the same as an array of objects; the array stores pointers to objects, and both the space for each object and each pointer must be released.
· Missing overloaded assignment operators also lead to memory leaks when copying objects in a member-wise manner if the class size is variable.
2. C Dangling Pointers
· Pointer variables not initialized.
· Pointers set to NULL after being freed or deleted.
· Pointer operations exceeding the variable’s scope, such as returning a pointer to stack memory, result in dangling pointers.
· Accessing null pointers (need to check for null).
· sizeof cannot obtain the size of an array.
· Attempting to modify constants, e.g., char p=”1234″; p=’1′;
3. C Resource Access Conflicts
· Multi-threaded shared variables not marked with volatile.
· Multi-threaded access to global variables without locks.
· Global variables are only valid for a single process.
· Multi-process writing to shared memory data without synchronization.
· mmap memory mapping is not safe for multiple processes.
4. STL Iterator Invalidations
· Deleted iterators become invalid.
· Adding elements (insert/push_back, etc.) or deleting elements can cause iterator invalidation in sequential containers.
· Incorrect example: Deleting the current iterator will invalidate it.
Correct example: When erasing an iterator, save the next iterator.
5. C++11 Smart Pointers
· Replace auto_ptr with unique_ptr.
· Use make_shared to initialize a shared_ptr.
· weak_ptr is a smart pointer helper.
1) Principle Analysis:
2) Data Structure:
3) Usage: a. lock() to get a strong reference pointer to the managed object b. expired() to check if the managed object has been released c. get() to access the smart pointer object.
6. C++11 Smaller, Faster, Safer
· std::atomic provides thread-safe atomic data types.
· std::array has smaller overhead than long arrays and differs from std::vector in that the length of array is fixed and cannot be dynamically expanded.
· std::vector can shrink its capacity to match its size using shrink_to_fit().
· std::forward_list is a singly linked list (std::list is a doubly linked list); in cases where only sequential traversal is needed, forward_list can save more memory and has better performance for insertions and deletions than list.
· std::unordered_map and std::unordered_set are unordered containers implemented with hash, with insertion, deletion, and lookup time complexity of O(1). Using unordered containers can achieve higher performance when the order of elements in the container is not a concern.
How to Check Memory:
· System memory usage: /proc/meminfo
· Process memory usage: /proc/28040/status
· Query total memory usage: free
· Query process CPU and memory usage ratio: top
· Virtual memory statistics: vmstat
· Process memory consumption ratio and sorting: ps aux –sort -rss
· Release system memory cache: /proc/sys/vm/drop_cache
Copyright Statement: This article is sourced from the internet, freely conveying knowledge, and the copyright belongs to the original author. If there are any copyright issues, please contact me for deletion.
‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧
Follow my public WeChat account, reply "Join Group" to join the technical exchange group according to the rules.
Click "Read the original text" for more shares, feel free to share, bookmark, like, and view.