Dynamic memory allocation troubles
Life in the embedded world is not always as easy as on other platforms. If you do not have a full operating system running, you also lack a real memory manager. The standard solution: Do not use dynamic memory. In most cases you do not really need it. With something like an SSL libary, this becomes harder. Connections are created on-demand and those connections need SSL-global data during the handshake and the application will receive yet-unknown amounts of data for certificates and such. Pure stack-based allocation in such an environment is near-impossible without wasting a lot of stack space on probabilities. And in an embedded environment, that memory space is limited.
So in the development branch of PolarSSL, we wanted to allow you to change the default calls for malloc() and free() to polarssl_malloc() and polarssl_free() that can be overridden with other functionality than heap allocation. That allows you as a developer to provide some kind of memory allocation module that PolarSSL will use by calling memory_set_own().
But we want to go a step further. What if you do not have such a memory allocation module yet? We will provide one for you. Our next step was to develop a straightforward memory allocator that uses a buffer for storing the 'dynamic memory blocks'.
Designing the memory allocator
The main objective of the buffer-based allocator is not using malloc() and free(). In addition we want to detect common programmatic issues and allocated data left behind.
For this implementation we use a straightforward design where each of the allocated and unallocated memory blocks in the buffer has a header. Each header starts and ends with a magic number to allow memory corruption detection.
All blocks are present in the main linked list used by this allocator that is in-order. So blocks that are adjecent in the linked list are also adjecent in memory. All unallocated memory blocks are also present in the free block list. Blocks here are unordered and just inserted at the front.
Malloc and free
Allocating data with polarssl_malloc() is a O(n) operation. For allocating data in our buffer, we check our list of free blocks for the first block that could fit the requested size and the header into it. For the size we use the nearest multiple of POLARSSL_MEMORY_ALIGN_MULTIPLE, so as to make sure all blocks are aligned in memory. After finding a block that can fit the requested size, we have a decision to make. Use it whole or split? If the block has more than enough space for another memory header and more data, we split the block into two, use one and add the other to the list of free blocks.
freeing data with polarssl_free() is a O(1) operation. We already know where the block is located, as we get the pointer in our call. So the only thing to do is verifying that it is actually one of our blocks and that it is still allocated.
After marking it as free, we check to see if we are directly after and / or directly before another free block. If so, we should merge with that block in order to make a larger free block available. If not, we have to add the new block to the list of free memory blocks.
Especially when you dabble around with something as low-level as a memory allocator, strange things are bound to happen during development and testing. One thing we'd always like to know is: Is the memory block header we are now looking at still 'valid'. We have implemented a simple but effective magic number at the start and end of the memory block header that is verified when needed and can tell us if something overwrote our headers.
Note: This is meant for detecting programmatic errors, not modifications by malicious adversaries!
Memory left behind and backtraces
During and after your application code has run, you want to be able to see if all memory was de-allocated. If POLARSSL_MEMORY_DEBUG is enabled, you can call
memory_buffer_alloc_status() to get a display of all still allocated blocks (if any).
In addition it shows the maximum amount of memory that was ever allocated, so you can trim down the memory buffer if needed.
Current use: 0 blocks / 0 bytes, max: 18392 bytes, malloc / free: 1320907 / 1320907 All memory de-allocated in stack buffer
If you are on a Linux-like system and use glibc, you can also enable POLARSSL_MEMORY_BACKTRACE to get a debug-like backtrace of the calls active at the time of the memory allocation. This works best if you compile with gcc debug flags (-g) enabled. Granted, valgrind does a better job, but it does the job!
Enabling the buffer-based memory allocator
So how do you use this buffer-based memory allocator?
Call the following function with a buffer of your choice and PolarSSL will happily churn on.
int memory_buffer_alloc_init( unsigned char *buf, size_t len );
Eat your own dog food
In order to test the allocator, we have adapted some of the applications and all of the test suites to use the buffer-based allocated if POLARSSL_MEMORY_C and POLARSSL_MEMORY_BUFFER_ALLOC_C are defined.
If you also enable POLARSSL_MEMORY_DEBUG, you will get a valgrind-like status of still-allocated memory at the end of all test suites if you run the test suite by hand.
Use it yourself?
The buffer-based allocator is in no way dependent on other PolarSSL code itself. So if you want to borrow it, just do so. Check out the code for memory_buffer_alloc.c on github (development branch).