The C/C++ language differs from other languages in that it requires developers to manage memory resources themselves. Improper use of dynamic memory can easily lead to segmentation faults or memory leaks. In particular, memory leaks are often discovered only after the program has been running for a while, making it difficult for developers to locate the error immediately.
Compared to personal computers, embedded systems have even scarcer memory resources. As an embedded C developer, understanding the principles of memory management can help use memory resources more correctly and locate bugs in the program. This article will introduce the principles of dynamic memory management using C language as an example.
Principles of Dynamic Memory
1. Stack Space and Heap Space
Before introducing memory management, let’s first explain stack space and heap space: Stack space is automatically allocated and released by the compiler. For operating systems like AWorks, when a user creates a task, they can decide the size of the task’s stack space.
Stack space generally stores the following data: local variables within functions (excluding variables defined as static), and information about general registers saved when calling another function, etc.
Refer to the following example (for ease of understanding, general register information is omitted):
Before the task executes s = calculate_sum(a,b);, the stack of the task holds the following data:
The program then executes the calculate_sum function, and its stack grows downwards. Before returning to the task, its stack structure is as follows:
After executing calculate_sum, upon returning to the task based on the return address, the stack restores to its previous structure:
Thus, stack space stores local variables within code blocks, dynamically increasing and decreasing internal data. This is why variables cease to “exist” after the interface call ends.
Heap space is a region managed by the OS, where developers can dynamically request a region for data operations.
Heap space remains valid during program execution, equivalent to defining a large global array. Memory is requested from the heap as needed and returned when no longer in use. This allows developers to dynamically control the size of the space without needing to consider the worst-case scenario when writing code (defining an array requires its size to be determined before compilation, and it cannot be increased or decreased during use, so the maximum required data size must be considered).
Heap space is determined by the compiler. If developers want to implement a piece of dynamic memory, they can request a block of aligned memory from the heap.
2. Memory Resource Allocation and Release
We will use the commonly used memory operation interfaces—malloc and free—as examples to introduce the details of dynamic memory operations.
void* malloc(size)——Requests a block of memory of size bytes.
Refer to the diagram below, the gray area represents memory that has already been used, while the blank area represents memory that can be requested for use. When requesting memory, the system first checks if there is a sufficiently large unused area. If so, it allocates it to the requester and marks this area as “used”; otherwise, the allocation fails.
(For ease of reading, we will assume that memory addresses grow from top to bottom from here on)
void free(void *)——Releases allocated memory. In contrast to malloc, the purpose of free is to mark the “used” area as “unused”, allowing the released memory to be reallocated for reuse next time. Memory released by free must be memory allocated by malloc.
Due to the need to mark the state of memory and record positions (for release), additional space is required for information recording when allocating/releasing memory. Some systems manage recorded information centrally, while others allocate a small additional area for recording when requesting memory.
3. Memory Leak
For dynamically allocated memory, it should be returned to the heap after use to allow for subsequent allocations. If the allocated memory is not returned, it results in a memory leak. Refer to the following code:
Now we set flag=1, what will happen when this function is executed?
First, ptr will point to the allocated 128-byte memory (Figure b), then after checking flag==1, it will request 256 bytes of memory (Figure c). Assuming we now release ptr:
Now we have released the 256-byte memory block, but we initially allocated a 128-byte memory block. What will happen to this 128-byte memory block? Since the only pointer pointing to this memory, ptr, now points to the 256-byte memory block, there are no pointers pointing to this memory anymore, thus this memory can no longer be released, and we say there is a memory leak.
For a period of time at the beginning of the program’s execution, the system will not have any exceptions. Even if a small piece of memory is not released, it will not cause an error because the memory heap still has enough space to use. However, if the program runs long enough and this function is called multiple times (with flag==1), the heap space will gradually be filled with leaked memory blocks until the program can no longer request memory from the heap, at which point it will report an error.
Memory leaks are particularly troublesome for developers for this reason; the issue of memory leaks is often not discovered immediately! For developers unfamiliar with memory management, it is even more difficult to locate the error.
For dynamic memory operations, it is essential to remember: When a block of allocated memory is no longer in use, it must be released promptly. Each malloc operation must correspond to a free operation.
4. Memory Alignment
In many cases, allocated memory must not only meet the requested size but also be aligned to allow the allocated space to be converted into other structure types besides char. The system generally aligns memory allocation based on the byte size of int type variables. The aw_mem_align interface provided by AWorks allows users to obtain custom-aligned memory space.
Readers are encouraged to look up relevant materials on type alignment knowledge, which will not be elaborated on here.
Memory Management Algorithms
Next, we will learn how to manage memory in heap space. Here we will mainly introduce two commonly used memory management algorithms in embedded systems.
1. Linked List Method
The linked list method maintains two linked lists, one recording allocated used memory segments and the other recording unallocated free memory segments. When requesting a block of memory, the system finds a suitable block from the free memory segment to allocate to the user, while linking it into the used memory segment. When releasing, it finds the corresponding entry from the used memory segment and releases it back to the free memory segment for next allocation.
Now we will introduce the details of the first-fit algorithm as an example. The first-fit algorithm starts from the head of the free linked list, sequentially searching for free memory. Once it finds a sufficiently large contiguous area, it returns it to the user.
As mentioned earlier, managing memory areas requires additional recording information. The linked list method generally allocates extra space for recording relevant information when operating on memory space. We assume the red area in the diagram below records used memory, while the cyan area records free memory. Here, the free link linked list maintains free memory segments, and the used link maintains used memory segments:
After the program runs for a while, assume the heap space distribution is as follows:
Information about free and used areas is maintained by the two lists.
Now, if a user needs to request a memory block of size 3k, the system will start from the free link, first finding a 2k free area. Since 2k is insufficient, it continues searching and finds a 4k area, which is large enough, so it will take 3k from the 4k space and link it into the used link.
Although the remaining 3k space is more suitable for allocation, the first-fit algorithm will not continue searching once it finds a sufficiently large space.
When the user has finished using the resource, they return the allocated 3k, and the system will find the allocated memory from the used link, link it back to the free link for next allocation, and then merge adjacent free memory blocks into a complete block:
Now consider this situation: Suppose the user wants to request a 5k memory block, can the system provide it? No, it cannot.
Although the total free memory blocks add up to 9k (2k+4k+3k), the 9k memory is not contiguous, so it cannot be allocated to the user. This is known as external memory fragmentation—although the total free memory space is sufficient, it cannot be allocated due to fragmented memory blocks breaking the continuity.
Other linked list methods include best-fit algorithms, next-fit algorithms, etc. Interested readers can look up relevant materials.
2. Bitmap Method
Using the bitmap method, the system’s memory is divided into fixed memory blocks. A variable’s one bit indicates whether a memory block is free:
In the diagram, each square represents a fixed-size memory block, assumed to be 1k. A 16-bit variable represents a 16k memory segment. If a block is free, it is represented by 0; if it is used, it is represented by 1.
In the diagram, the 1st, 2nd memory blocks and the 7th, 8th, 9th memory blocks are used, and the corresponding bits are set to 1 to indicate they are occupied.
Compared to the linked list method, the bitmap method uses less additional space to record information about the memory heap, and since allocation and release are done in whole blocks, it generates less external fragmentation.
However, if a user only requests a few bytes of memory but allocates a 1k memory block, a large amount of space will remain unused, leading to what we call internal memory fragmentation.
One way to reduce internal memory fragmentation is to choose the size of memory blocks reasonably; smaller fixed sizes lead to less memory fragmentation—when a user requests a few bytes of memory, using fixed 16-byte memory blocks generates less fragmentation than using fixed 1k memory blocks. However, smaller fixed sizes also require more bits to record memory information.
There are many excellent bitmap algorithms available—dividing memory into different fixed sizes for faster allocation speed and less memory fragmentation. Interested readers can look up relevant materials.
If you have any questions, you can:
Add WeChat ID: zlgmcu-888
Call the official technical hotline of ZLG Zhiyuan Electronics: 400-888-4005.