Group Actions
Engagement
  • Author Author: e14 Contributor
  • Date Created: Date Created
  • Views 5074 views
  • Likes 1 like
  • Comments 13 comments
Related
Recommended

Arduino: Dynamically allocating and freeing memory

e14 Contributor

Everything that happens on a micro-controller has to be known. This includes dealing with memory. Many people (myself included) have developed a wonderful set of code that can dynamically use and free memory through the standard malloc and free functions. Only later do we discover that our available memory is getting reduced as time goes by -- followed by undetermined and random failures.

 

This is because no microcontroller (the ArduinoArduino included) has the ability to garbage collect.

 

For instance, let's say you malloc A and then malloc B. You then free A. There is now a memory hole (the size of A) that will never be closed again. Essentially a non-existing A is now taking up memory. If you now malloc A again, it will not be stored in that hole -- new memory will be taken up. You can see how this can become a problem.

 

To solve this problem, I developed the library ReMem (Reusable Memory), located in my usertools library, which among other things contains a full featured User Interface.

 

Documentation of ReMem can be found here. Basically ReMem creates an object (with a specified size) that has two functions: rmalloc and free. These work exactly the same way as the conventional malloc and free except when you free data, it will be used again if the same size data is requested. (The disadvantage is that it can be slow, and takes an extra byte of data per malloc).

 

 

Upcomming

The code is currently stable, but I'm going to be adding the ability to reclaim data that has been freed at the end, as well as cannibalize large allocations. Stay tuned.


Update

I have a new, more tested library for this purpose called tinymem. Check it out here: https://github.com/cloudformdesign/tinymem

  • I don't know for sure, but I thought malloc already reuses a block if it's the same size as a freed block.  Specifically, if all your allocated storage blocks are the same size then malloc and free will keep reusing the same blocks and you're fine.  The problem comes up if you're using different size blocks.  Then you'll end up with fragmentation, even with automatic garbage collection.

     

    I would guess that malloc uses "first fit" or a similar algorithm.  Feel free to correct me.

     

    Fragmentation must be avoided in embedded systems.  The best way is to make all blocks the same size, except for a few variable-length blocks that are allocated at initialization time and never deallocated.  Then you manage the list of available blocks yourself and fragmentation cannot occur.

     

    Another approach is to use "David Wheeler's Law" and access all dynamic storage through an extra level of indirection.  This has a big run-time penalty, but you can always defragment and move the blocks since each only has one pointer.

  • in reply to clem57

    What do you mean by that exactly? Do you mean something other than the stack?

     

    The issue is allocating memory for persistence outside of function calls (but not permanent persistence). On a microcontroller the heap becomes fragmented and memory allocation no longer works.

  • Like... how about a simple stack implementation for localized variables. Just suggesting.

    Clem