Memory allocation using Pool¶
Introduction¶
Dynamic memory allocation is a method which reserves RAM memory space (heap) in run-time code execution. In contrast to static memory allocation, it brings new possibilities in case of writing embedded programs, such us:
- in C programming hiding types information (encapsulation) e.g. constructing Abstract Data Types (ADT)
- reserving space for objects while program is running e.g. in protocol stacks
- part of the code may allocate memory, while other part may use it
- making structures that can change its size in time e.g. lists, arrays, maps, queues
- smaller memory size is needed - application uses exactly the space it requires
There are of course many disadvantages of using dynamic memory allocation.
- programmer has to keep track of allocated memory and deallocate it when needed
- it takes time for allocation - this can be indeterministic time
- application can run out of memory
- memory footprint cannot be determined at link time
The following means are used for the purpose of dynamic memory allocation/deallocation:
- in C - functions
malloc
andfree
- in C++ - operations
new
anddelete
(both with some variations)
Nevertheless, using of the built-in means for small embedded systems is not a good choice. One should think about alternatives due to following reasons:
- provided toolchain may not provide such possibility (supporting for
malloc
is not available) - allocation is not deterministic (time for memory chunk allocation)
- using built-in
malloc
produces visible extend of the footprint
There are many technics how to overcome issues related with the dynamic memory allocation, but to be honest there is no cure-all solution. You can find some ideas and useful guidelines how to safely allocate memory in embedded world.
Pool pattern¶
I wrote this article not to elaborate on memory allocation, but to provide you a sample implementation of the quite useful pattern, which is a Pool pattern. Let’s start…
First of all, a Pool is a container that comprises declared SIZE
number of elements. Each element has the same byte size. The application can
take (allocate) elements from the Pool, use it and when it is not needed
anymore, give it back to the Pool (deallocate). Other variation of the
Pool pattern is when deallocation is not supported. It is useful for the
application which uses the Pool only at system initialization (startup).
This is the safest version of the dynamic memory allocation, because it
results in zero memory leakage, reasonable memory waste and no fragmentation.
Please take a look at the following code snippet.
namespace k2lib
{
// namespace k2lib body
template <typename T, int SIZE>
class Pool
{
public:
Pool();
T *palloc(); /*!< Take (allocate) one element from the Pool. */
void free(T *p); /*!< Give back (free) element of given argument pointer. */
int size(); /*!< Returns count of free Pool elements. */
private:
/* Rest of the elements... */
};
} // namespace k2lib
Above code shows API of the Pool pattern. It is quite straight-forward - one
constructor that initializes internal memory heap and three methods palloc
,
free
and size
that are used to operate with the Pool. There is nothing
hidden in mentioned methods, and their usage are commented in the code.
Pattern usage¶
Simple example that shows how to operate with the Pool is depicted below.
#include "Pool.h"
int main(void)
{
cout << "Start of test..." << endl;
const int SIZE = 4; // Number of Pool elements
k2lib::Pool<uint16_t, SIZE> pool; // Create Pool of 4 elements (uint16_t type)
uint16_t *objects[SIZE]; /* Create pointers to hold dynamically allocated
elements */
for (int i = 0; i < SIZE; i++)
{
// Allocate element from the Pool
objects[i] = pool.palloc();
// If allocation failed palloc() returns NULL
if (objects[i] == NULL)
cout << "Allocation error!" << endl;
}
// There is no more elements in the Pool, so p supposed to be NULL
uint16_t *p = pool.palloc();
if (p != NULL)
cout << "Allocation error!" << endl;
// Free (give back to the Pool) element pointed by objects[2]
pool.free(objects[2]);
// Allocate element from the Pool
objects[2] = pool.palloc();
// If allocation failed palloc() returns NULL
if (objects[2] == NULL)
cout << "Allocation error!" << endl;
// Test whether there are elements in the Pool (all supposed to be reserved)
if (pool.size() != 0)
cout << "Allocation error!" << endl;
// Free all elements
for (int i = 0; i < SIZE; i++)
{
pool.free(objects[i]);
}
// Test whether Pool has SIZE elements after freeing all elements
if (pool.size() != SIZE)
cout << "Allocation error!" << endl;
cout << "End of test..." << endl;
return 1;
}
Above example is simple and provides clear overview how to work with the Pool
pattern. However it is not clear yet what Pool pattern guts look like. First
of all it requires some elements storage elements[SIZE]
and some object that
keeps track of each elements status (free or allocated) - info
. In the small
microcontrollers world this info
object could be a huge overhead and for that
reason it has to be implemented in a optimized fashion.
Elements status tracking¶
My personal solution is to use bits to hold information about free/allocated
elements. This approach requires creation of an array of e.g. uint8_t
type
which can hold enough bits for Pool size SIZE
. This can be calculated in
the following way.
const int SIZE = 21; // Pool size (number of Pool elements) - random value only
// for this example.
// Number of bits in uint8_t type.
static const size_t BITS_IN_UINT8 = 8;
// Calculate number of uint8_t elements that can accomodate SIZE bits.
static const size_t NO_BYTES = (SIZE + BITS_IN_UINT8 - 1) / BITS_IN_UINT8;
// Create array of uint8_t elements of NO_BYTES size.
uint8_t info[NO_BYTES];
If you do calculation for yourself you should get NO_BYTES
equal to 3
(remember of integer casting - round down).
In order to operate with the info
array - set, clear and test bits, you can
define following methods setBit
, clrBit
and testBit
.
void setBit(int bit_index)
{
if (bit_index >= SIZE)
return;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
*((uint8_t *)(&info[0] + byte_offset)) |= (uint8_t)(1 << bit_index);
}
void clrBit(int bit_index)
{
if (bit_index >= SIZE)
return;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
*((uint8_t *)(&info[0] + byte_offset)) &= ~((uint8_t)(1 << bit_index));
}
bool testBit(int bit_index)
{
if (bit_index >= SIZE)
return false;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
return (0 !=
(*((uint8_t *)(&info[0] + byte_offset)) & (uint8_t)(1 << bit_index)));
}
In order to calculate position of the bit given by bit_index
argument, you have
to calculate byte position byte_offset
in the info
array and bit position
in the target byte bit_index
. Now, you can get &info[0]
address and move
it by byte_offset
. Obtained array
element can be set/cleared/tested with
the calculated bit_index
- 1 << bit_index
.
Conclusion¶
There are many patterns that can help developers in memory management. Different
applications require different approaches. The Pool pattern is one of the
possible solutions. It is designed for rather applications that requires safety,
then general purpose apps. It is well-suited for microcontrollers having small
memory capacity. In this article you also gained a knowledge how to use bit-arrays
which can be lightweight solution for e.g. std::bitset
. I hope you have enjoyed
this article and see you soon!
Complete implementation¶
In conclusion see below full code.
#ifndef POOL_H
#define POOL_H
#include <stddef.h>
#include <stdint.h>
namespace k2lib
{
// namespace k2lib body
template <typename T, int SIZE>
class Pool
{
public:
Pool();
T *palloc(); /*!< Take (allocate) one element from the Pool. */
void free(T *p); /*!< Give back (free) element of given argument pointer. */
int size(); /*!< Returns count of free Pool elements. */
private:
T elements[SIZE]; /*!< Holds the pool objects. */
static const size_t BITS_IN_UINT8 = 8; /*!< Number of bits in uint8_t type. */
static const size_t NO_BYTES =
(SIZE + BITS_IN_UINT8 - 1) /
BITS_IN_UINT8; /*!< Required number of bytes to hold information
about free/allocated pool objects. */
uint8_t info[NO_BYTES]; /*!< Keeps track of free/allocated memory objects. */
int free_elements_cnt; /*!< Counts number of free elements */
bool testBit(int bit_index);
void setBit(int bit_index);
void clrBit(int bit_index);
};
template <typename T, int SIZE>
Pool<T, SIZE>::Pool()
{
// Free all pool objects
for (unsigned int i = 0; i < NO_BYTES; i++)
info[i] = 0xFFU;
// Clera
free_elements_cnt = SIZE;
}
template <typename T, int SIZE>
T *Pool<T, SIZE>::palloc()
{
// Test whether there are any free elements
if (free_elements_cnt <= 0)
return NULL;
// Look up for first pool object
for (int i = 0; i < SIZE; i++)
{
if (testBit(i))
{
// Found free element, so mark it as allocated and return
clrBit(i);
free_elements_cnt--;
return &elements[i];
}
}
// No free elements available
return NULL;
}
template <typename T, int SIZE>
void Pool<T, SIZE>::free(T *p)
{
// Cannot free NULL pointer
if (NULL == p)
return;
// Loop through all elements and find the one to be freed
for (int i = 0; i < SIZE; i++)
{
if (p == &elements[i])
{
// Element found, so free this element
p = NULL;
setBit(i);
free_elements_cnt++;
}
}
// No elements found, memory cannot be freed
return;
}
template <typename T, int SIZE>
int Pool<T, SIZE>::size()
{
return free_elements_cnt;
}
template <typename T, int SIZE>
bool Pool<T, SIZE>::testBit(int bit_index)
{
if (bit_index >= SIZE)
return false;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
return (0 !=
(*((uint8_t *)(&info[0] + byte_offset)) & (uint8_t)(1 << bit_index)));
}
template <typename T, int SIZE>
void Pool<T, SIZE>::setBit(int bit_index)
{
if (bit_index >= SIZE)
return;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
*((uint8_t *)(&info[0] + byte_offset)) |= (uint8_t)(1 << bit_index);
}
template <typename T, int SIZE>
void Pool<T, SIZE>::clrBit(int bit_index)
{
if (bit_index >= SIZE)
return;
int byte_offset = (bit_index / BITS_IN_UINT8);
bit_index = (bit_index % BITS_IN_UINT8);
*((uint8_t *)(&info[0] + byte_offset)) &= ~((uint8_t)(1 << bit_index));
}
} // namespace k2lib
#endif /* end of include guard: POOL_H */
Footnote
kaeraz, 2018/11