Understand the stack, heap, and bare-metal memory management malloc of the microcontroller in one article

When it comes to memory management, you may think of the malloc and free functions.

Before talking about these two functions, let's first talk about the concepts of stack and heap.

1.stack

Our microcontrollers generally have a startup file, take STM32F103 as an example.

This Stack_Size is the stack size, and 0x00000400 represents the size of 1K (0x400/1024).

So what is this stack used for?

For example, the formal parameters of our function and the local variables defined in the function are stored on the stack, so the local variables and arrays of our function cannot exceed 1K (including nested functions), otherwise the program will crash and enter hardfaul.

In addition to these local variables, there are also some real-time operating system on-site protection and return addresses that are stored in the stack.

One more digression is that the growth direction of the stack is from high addresses to low addresses. This is not used much and there is no need to delve into it for the time being.

2. Heap

The memory dynamically allocated by the malloc() function belongs to the heap space.

Similarly, the heap size is also defined in the microcontroller startup file.

0x00000200 means 512 bytes.

This means that if you use the malloc() function, the maximum allocated memory cannot be larger than 512 bytes, otherwise the program will crash.

Many articles on the Internet say that global variables and static variables are placed in the heap area.

But I did an experiment and set the heap space size to 0, and it had no impact on the normal operation of the program.

This shows that the global variables and static variables we usually define are not stored in the heap, but in another static space area outside the stack. I understand it personally. Please correct me if I am wrong.

Ok, so we have a brief understanding of the concepts of heap and stack, and we also know that the malloc() function allocates heap space.

So below, we discuss a question: There is a ready-made dynamically allocated memory function malloc(), but why is it rarely used in microcontrollers? Why do we need to do memory management ourselves (write our own code to implement functions such as malloc() and free())?

The malloc() function has been verified by thousands of netizens and is prone to problems, so no one dares to use it in general microcontroller development unless it is...

Many host computers will use it, because there are memory management algorithms written in the lib library, which are not suitable for microcontrollers.

The main problem with malloc() used in microcontrollers is that it is prone to memory fragmentation.

What is memory fragmentation?

Memory fragmentation is the part of allocated memory space that is not used.

For example, if you use malloc(1) to allocate 1 byte, but you are actually allocated 8 bytes of space, the remaining 7 are memory fragments.

How do memory fragmentations occur?

Let's demonstrate it through a program:

When we allocate p1 and p2, we obviously allocate only 1 byte, but actually allocate 8 bytes of space. These 7 bytes cannot be allocated again before they are released, which is equivalent to 7 bytes of space. Just wasted.

This is one of the ways fragmentation occurs, but there are other ways.

For example, if you apply for two spaces in a row for the first time, the first block is 1 byte, and the second block is also 1 byte.

Theoretically, the allocated space addresses are continuous, but 7 bytes of memory fragments are generated in the middle. If two blocks are allocated, it will be 14 bytes.

After the first block of 1 byte is released, the second block of 1 byte of space has not yet been released.

In this way, the space equivalent to the first block can only be used to allocate about 1 byte of space (it may be possible to allocate 2-6 bytes). The details depend on the Malloc() function allocation algorithm.

But what is certain is that if you cannot allocate a space as large as 10 bytes, the application scope of this space will be reduced a lot.

If a program allocates a lot of small space of 1 byte, then there will be a lot of such fragments superimposed on the entire memory block.

In the end, there is obviously a lot of free memory, but the allocation always fails, and even the program crashes.

Therefore, this is the reason why we have to write our own memory management, which is to solve the pain point of memory fragmentation.

Memory management consists of many different sub-functions, such as dynamic memory allocation algorithms, memory release, etc.

But memory management is relatively complicated, involving data structures and some small algorithms.

In order to help engineers solve tedious memory management codes, some high-end microcontrollers have built-in MMU (memory management unit) modules.

However, most microcontrollers don't have it, and I haven't used it myself. If they don't have it, I have to write my own code to implement memory management.

Memory management can be said to be a necessity for real-time operating systems and self-written program architectures. The operating system generally comes with it and does not need to be written by yourself.

1. What are the practical applications of dynamically allocated memory?

Take our wifi alarm host project as an example.

1. Used for flexible task creation

Our host has written a small system by itself, which involves task creation and scheduling.

We are very inflexible when creating tasks and need to manually adjust the number of tasks in the kernel header file.

The most ideal situation is that the system kernel file does not need to modify anything. In fact, it is impossible to do this without dynamic memory allocation.

Our architecture can be used by many products. Each product has different functions, so the number of tasks is also different.

If there is dynamic memory allocation, you can flexibly create the tasks required for your own products without having to change them manually. I can even encapsulate the architecture code into a lib and directly provide functional interfaces for different engineers to use.

2. Used for undetermined amounts of temporary data

For example, our host has a pairing function, which means that it can learn the detector through wireless communication.

Then there is a detector list in our settings menu, which will display all paired detectors.

If you want to display all paired detectors, for example, my host supports a total of 20 detectors.

Then I have to implement and define a structure array that can hold 20 detectors.

The worst thing is that it needs to be defined as static, otherwise the data will be lost again the next time you enter this function.

And if I am not in this menu, this memory is actually wasted. If there is dynamic memory allocation, it will definitely be too late.

If you don’t know it yet, learn it quickly and you’ll need it sooner or later!

2. How to implement memory management?

I used to search for a lot of information and routines on the Internet, and I scolded them while searching, but I still ended in failure.

This is a pain that I have always wanted to break through, but have never been able to break through. I have done it before, but I have never been able to solve the fragmentation problem well.

I've been lucky recently. After being recommended by an expert, I found a memory management code written by an expert on Github.

The code is of no use to you, the knowledge is yours to learn, haha.

Download it, study it in depth first, and then correct a small bug and some detailed code to make it a version that can be compiled by Keil.

The test platform is our wifi alarm project hardware, based on STM32F103.

The picture below shows the painful process of debugging and testing.

Do you feel like your scalp is numb? That's right! The coder's mind has never been comfortable.

The following is the test data (a bit long, only 3/4 was intercepted):

The upper line of the dense data is the address. In order to facilitate debugging and display, I limited the maximum allocation to 120 bytes. Then one byte of the address is enough, so I removed the upper 3 bytes of the address.

The next line is data, a group of 2 lines, as shown in the figure below.

Ok, let’s get to the climax of this article. How to implement the algorithm?

1. Algorithm principle

The essence is to play with structure pointers in an array, and the array serves as a memory pool.

First define a large array. Define the array as large as the maximum memory allocation you support. For example, I currently support a maximum of 120 bytes, and MEM_SIZE is 120.

2. Array storage method

Every time we allocate memory to this memory, we make a "table", and the "table" records the information of this memory.

Tables are represented by programs as structures, because only structures can represent collections of different types of data.

This "table" will record a total of three pieces of information about the memory block: the storage address of the memory block data, the memory block size, and the memory block ID.

These three pieces of information pave the way for later writing dynamic memory allocation and memory release functions, with the purpose of better finding the specified memory block.

It is equivalent to every time a piece of memory is dynamically allocated, two pieces of memory space will be allocated in the memory pool (array).

A piece of memory is used to store the only table (structure) of this memory. Calculated based on the structure members, it is a fixed 8 bytes.

The other piece of memory is the actual size of the memory space you need to allocate, and ultimately your data is stored in this memory.

For example, when I call the dynamic memory allocation function mem_malloc(10), 10 bytes of memory space are allocated, and all values ​​​​1 are written.

After completion, the storage structure of the memory pool is as follows:

Then, I called the dynamic memory allocation function mem_malloc(8), allocated another 8 bytes of memory space, and wrote all values ​​​​2.

After completion, the storage structure of the memory pool changes as follows: