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 and free
  • in C++ - operations new and delete (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:

  1. provided toolchain may not provide such possibility (supporting for malloc is not available)
  2. allocation is not deterministic (time for memory chunk allocation)
  3. 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.

API of the Pool pattern.
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.

How to operate with the Pool class.
#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.

How to calculate number of uint8_t elements to hold SIZE bits.
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.

Set/clear/test bits in an array.
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.

Complete Pool pattern implementation.
#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