Memory management is one of the most fundamental areas of software engineering.
In many scripting languages you do not have to worry about memory management, but that does not make memory management any less important.
In languages like C and C++, memory management was left to the responsibility of the software engineer. Modern C++ designs make heavy use of dynamic memory. (e.g. Inversion of control, dependency injection, factories, collections of objects, design for testability, event passing with objects, etc.)
This is a standard practice in desktop applications, where memory is freely available and latency not an issue.
On embedded and real time systems, the situation is different:
Dynamic allocation of memory may be non-deterministic, depending on the underlying operating system. Fragmentation of the dynamic memory pool can lead to a slower system responsibility over time or even worse to “out of memory” exceptions, even if there is enough memory available.
A conservative approach in designing real-time systems is not to use dynamic memory at all. But there are also other possibilities to implement such systems.
C++ Memory Spaces
First let us have a look at the memory usage in C++:
In C++ memory can be regarded as being divided into three parts. There is static memory, automatic variables and dynamic memory.
- Static memory allocation refers to the process of allocating memory at compile-time before the associated program is executed. The actual allocation of addresses to variables is performed by the embedded software development toolkit.
- All variables declared within a block of code are automatic by default. This means they are allocated and de-allocated automatically when the program flow enters and leaves the variable’s scope. Automatic variables are stored on the stack.
- Dynamic memory is allocated from the heap. The two key dynamic memory functions are new and delete. The allocation and deletion of memory are non-deterministic operations on most operating systems. Depending on the dynamic memory allocation strategy we may observe a degradation of performance over time due to fragmentation issues.
Static memory should not cause any run-time problems. Automatic variables shouldn’t be a problem either, unless the stack size is too small and a stack overflow occurs.
Dynamic memory however is a big issue. One approach to manage dynamic memory on a real-time system is to use a fixed-size pre-allocated memory block, a memory pool.
Memory pooling
A Memory pool allows dynamic memory allocation comparable to malloc or C++’s operator new. But almost all implementations suffer from fragmentation because of variable block sizes. The use of memory pools has been considered a source of in-determinism in the real-time domain, due to the unconstrained response time of dynamic storage allocation algorithms and the fragmentation problem.
However there are some memory pool implementations that are capable to circumvent these issues.
One of those is TLSF. (http://www.gii.upv.es/tlsf/ )
Two-Level Segregated Fit memory allocator (TLSF)
TLSF is a general purpose dynamic memory allocator specifically designed to meet real-time requirements. TLSF implements a two level mechanism:
The first level uses an array which divides free blocks in classes, that are a power of two apart (8, 16, 32, 64, etc.). The second level subdivides each first-level class in a linear manner. The second level contains an associate bitmap used to mark which lists are empty and which ones contain a free block.
The advantages of this approach are:
- Bounded Response Time: TLSF has a constant cost for memory allocation and de-allocation of O(1).
- Fast: TLSF executes a maximum of 168 processor instructions in a x86 architecture. It can be slightly lower or higher, depending on the compiler and optimization.
- Efficient Memory Use: The maximum fragmentation measured is lower than 25%.
(For more documentation on TLSF see also: http://www.gii.upv.es/tlsf/main/pubs/)
Example in c++
TLSF uses a plain c interface style api. In order to use TLSF from c++ one has to overload the new and delete operators.
Here are the functions that have to be implemented:
#ifndef WRAPPER_H #define WRAPPER_H #include void* operator new(std::size_t p_RequestedSize) throw (std::bad_alloc); void operator delete(void* p_Address) throw(); void* operator new[](std::size_t p_RequestedSize) throw (std::bad_alloc); void operator delete[](void* p_Address) throw(); void* operator new(std::size_t p_RequestedSize, const std::nothrow_t& pc_Exception) throw(); void operator delete(void* p_Address, const std::nothrow_t& pc_Exception) throw(); void* operator new[](std::size_t p_RequestedSize, const std::nothrow_t& pc_Exception) throw(); void operator delete[](void* p_Address, const std::nothrow_t& pc_Exception) throw(); #endif // WRAPPER_H
And the implementation:
#include "wrapper.h"
extern "C"{
#include
}
void* operator new(std::size_t p_RequestedSize) throw (std::bad_alloc){
void* const result = ::tlsf_malloc(p_RequestedSize);
if (0 == result) {// throw exception }
return result;
}
void operator delete(void* p_Address) throw(){
return ::tlsf_free(p_Address);
}
// other operators follow the same scheme...
Now let’s have a look at a little demo program:
#include
#include
#include
extern "C"
{
#include
}
#include "wrapper.h" // This redefines new and delete
// Test class
class DummyClass
{
public:
DummyClass(){ s_counter++;};
virtual ~DummyClass(){s_counter--;};
static unsigned int s_counter;
protected:
unsigned short m_pBuffer [100];
};
unsigned int DummyClass::s_counter = 0;
//-------------------------------------
int main()
{
int mPoolSize = 65536;
void* mPoolbuffer = ::malloc(mPoolSize);
// create memory pool
::memset(mPoolbuffer, 0, mPoolSize);
::init_memory_pool(mPoolSize, mPoolbuffer); // TLSF function
// statistics
size_t used = get_used_size(mPoolbuffer); // TLSF function
std::cout << "Before new DummyClass....:" << used << std::endl;
// usage of operator new()
DummyClass* pClass = new DummyClass();
// statistics
used = get_used_size (mPoolbuffer); // TLSF function
std::cout << "After new DummyClass.....:" << used << std::endl;
// usage of operator delete()
delete pClass;
// statistics
used = get_used_size(mPoolbuffer); // TLSF function
std::cout << "After delete pClass......:" << used << std::endl;
// usage of operator new[]()
char* pCharArray = new char[245];
// statistics
used = get_used_size(mPoolbuffer); // TLSF function
std::cout << "After new char[245]......:" << used << std::endl;
// usage of operator delete[]()
delete [] pCharArray;
// statistics
used = get_used_size(mPoolbuffer); // TLSF function
std::cout << "After delete [] pChar....:" << used << std::endl;
// delete memory pool
::destroy_memory_pool(mPoolbuffer); // TLSF function
return 0;
}
(* To enable statistics enable TLSF_STATISTIC (1) in tlsf.cpp )
And the output is:
Before new DummyClass....:6384 After new DummyClass.....:6608 After delete pClass......:6384 After new char[245]......:6656 After delete [] pChar....:6384
Summary
TLSF enables you to predictably use dynamic memory in real-time applications. But the usage of dynamic memory will always increase the complexity of a real-time system. Therefore its use should be restricted to cases where it is really needed, for example in message communication related operations. Because don’t forget, with dynamic memory allocation, memory leaks can plague the system for a long time. (see also C++ Memory error detection on a Linux platform)
