Is there a way to handle heap memory fragmentation in AVR/Arduino microcontrollers?

Question

I've been searching for a few days now without any luck.

Heap memory fragmentation is a result of using malloc() and free() heavily in microcontrollers/Arduino.

If using them is unavoidable, how can I defragment the heap every now and then to make sure that the next malloc() call will find contiguous memory to allocate?

Liston

You could modify malloc so that it returns a handle for the chunk, and then have a function that translates handles to an actual pointer each time you need to access the chunk. This way you could roll your own defrag that periodically re-arranges the memory and updates the handle table. – Nappe

Interesting, do you have a sample code or can you point me into that direction? – Liston

Answer 1

Create a pool of fixed-size memory chunks. When you need any amount of memory, allocate one of the chunks from the pool and use the portion you need. When you're done with it, return the chunk to the pool. The pool will never fragment because the chunks are always the same size. And if any chunks are available then they're always the right size. Sometimes you'll need only a couple bytes and for a second you'll think that you're being wasteful for tying up an entire chunck. But then you'll remember that you're avoiding memory fragmentation and you'll feel better about it.

If the size of your allocations vary greatly then one fixed-size memory pool might really be too wasteful. Then you can make two or three fixed-size memory pools for small, medium, and large chunks. But make sure you return the chunks to the same pool that you obtained them from.

Use a queue or a linked list to organize the chunks in the pool. The chunks are removed from the queue/list when they're allocated. And they're returned to the queue/list when they're freed.

Tamratamsky

But if using malloc() is unavoidable, is there any way I can defragment the memory? – Liston

Resetting the device and reinitializing the heap will defragment the memory. Maybe reset when malloc() fails, or periodically, or when your application is in a convenient state. – Tamratamsky

But that is not the same as defragmenting the memory, that will throw away all of the allocated data. – Liston

Answer 2

As @kkrambo mentioned, use a queue or linked list to keep track of allocated memory chunks. I've included an example specifically for Arduino, which does not have all of my desired bells and whistles. I opted to only keep the pointer to the chunks of memory in the queue, as opposed to the chunks themselves (that seems to be what kkrambo says, although I do not know if s/he meant what I'm saying above.)

const int MAX_POOL_SIZE = 4;
const int MAX_DATA_SIZE = 128;

// Memory pool for data
QueueArray <uint8_t*> dataPool;

void initDataPool () {
  uint8_t * ptr;
  for (int i = 0; i < MAX_POOL_SIZE; i++) {
    ptr = (uint8_t*) malloc(MAX_DATA_SIZE);     // Allocate MAX_DATA_SIZE buffer
    dataPool.push(ptr);                         // Push buffer pointer to queue
  }
}

// Allocate message data buffer from data pool
// If data pool still has buffer space available, and requested
// buffer size is suitable, return pointer to avalable buffer
static void* allocateDataBuff (size_t buffSize) {
  if (!dataPool.isEmpty()) {
    if (buffSize < MAX_DATA_SIZE) return dataPool.pop();
    else {
      if (debugMsg) Serial.println("allocateDataBuff: Requested Buffer Size is too large");
      return NULL;
    }
  } // if message pool still has buffer space available
  else {
    if (debugMsg) Serial.println("allocateDataBuff: Memory pool is full, no buffers available at this time");  
  }
}
void setup() {
    initDataPool();
}
void loop() {
    // ........
    uint8_t* dataPtr = (uint8_t*) allocateDataBuff(100);
    // ....assign message to *dataPtr
    // ........
    deallocateDataBuff(dataPtr);
}

Boughpot

You didn't mention deallocateDataBuff() function... – Urea