April 15, 2015
This was combined with our custom thread management explained here.
Once, I worked on a project in which we needed to implement our own and custom dynamic memory manager.
We did. This was an embedded product in which we were really limited by RAM size, but the product requirements forced us to have dynamic memory in the software. So we decided to implement our own memory manager, optimizing memory usage. At that time we had just worked with a SIM800H chip which firmware also contains a custom memory manager and it allowed me to analyze it and gave me ideas on how to improve it in the way we needed. I came to the following conclusions:
That system was using 16 bytes in order to allocate from 1 to 8 bytes, which was a lot for our software.
The extra information stored in the header, footer and in every allocation control block may not be completely necessary. Also, the control information for every allocation used too much memory. So I tried to reduce those things:
This way, only 8 bytes are used to allocate from 1 to 4 bytes, and 12 bytes are used to allocate from 5 to 8 bytes. The 4 bytes alignment would slightly slow down the system depending on the hardware but the requirement was to optimize the use of memory, not speed.
In order to handle the memory allocation, the software needs to have a huge array declared somewhere in the program (usually in the memory manager module). This huge array is basically all the memory available as dynamic memory. That means every succesful memory allocation should return a pointer into this array. So the size of this array needs to be adjusted depending on the hardware, requirements and the amount of available dynamic memory you want in the project. Setting its size as the total memory size you have in your chip could work, but it isn’t the best option. There are some things that should be taken into account that should be substracted from the total amount of dynamic memory:
My recommendation during development would be to start with a relatively small dynamic memory array and increase it as the development requires it. Let’s look at how the memory is organised in this array:
The main idea is that the memory is organised by memory blocks. Each block can be a free memory block or an allocated memory block. Two adjacent blocks can’t be of the same type: if they are, they join and make a single and bigger block. In order to keep track of all the blocks, each of them needs a pointer to the next one of the same type. This is what will be used to makes searches of the different memory blocks.
In the header we need two pointers: one to the first free memory block and the other to the first allocated memory block. That is 8 bytes, 4 for each pointer. Both pointers can point to NULL which means there are no blocks of that type, i.e. if the first free memory block in the header is NULL, it means all the memory has already been allocated. I also added two counters which can be very useful to know some statistics about the memory usage. Here it is an example of the header and the 16 bytes used in it (note it’s little endian):
|Start address||Memory content||Use|
|0x2000099C||E0||09||00||20||Addres of the first free memory block (saved as unsigned int, this example shows the address 0x200009E0)|
|0x200009A0||00||00||00||00||Address of the first allocated block|
|0x200009A4||EC||3B||00||00||Number of free bytes. It does NOT count the 4 control bytes of the next allocation. Saved as unsigned int.|
|0x200009A8||00||00||00||00||Number of used bytes including ALL the control bytes of each allocation. Saved as unsigned int.|
Each of both free and allocated blocks use 4 control bytes to save the address of the next block of the same type. In the last blocks of each type, the pointer is NULL (0x00000000). Let’s see an example when making a single allocation of 5 bytes:
|Start address||Memory content||Use|
|0x2000099C||B8||09||00||20||Memory Header. Address saved in 0x200009A0 points to the first allocated block (0x200009AC in this example)|
|0x200009AC||00||00||00||00||Allocated Block. Pointer to the next allocated block. In this example it points to NULL because it's the last allocated block in memory|
|0x200009B0||00||00||00||00||Usable bytes for the user.|
|0x200009B4||00||00||00||00||Allocation of 5 bytes implies reserving 8 bytes due to 4 bytes alignment.|
|0x200009B8||00||00||00||00||Free Block. Control bytes of the next free block. In this example it points to NULL because it's the last free block in memory|
In this example, the memory manager would return the address 0x200009B0 which is the address of the first usable bytes by the user. But internally, the allocated block in the memory manager starts at 0x200009AC. Also, the user could use not only the 5 bytes they want, but 3 more, so 8 bytes in total. If we wanted to still optimize more, we could start the next block after the 5 bytes for the user.
In the multi-threaded environment we had, we needed to make it thread safe. In order to accomplish that, some functions have to be provided to the memory manager. There are two different approaches:
Since we also wanted to use this module in a CPU interruption occasionally (UART, GPIO, etc) the first approach was not good enough for us because the execution would be blocked if an interruption was called during the execution of the memory manager. So we provided a function in which CPU interruptions were disabled. The provided function is called at the beginning and at the end of the allocation and free processes.