11

I previously asked this question:

Is it required to delete variables before going to sleep?

On that question, @Delta_G posted this comment:

... Really on a microcontroller I would create the object in a smaller scope and try to do everything in my power to avoid having to use new or any other form of dynamic allocation. .... etc.

That comment got three likes and when I google about dynamic allocation using Arduino, everyone also tries to stay away from that. In summary from all the research I did, my conclusion is now Do not allocate memory unless you really really have to.

I am using the Visual Studio IDE to create my C++ libraries that I intend to use with Arduino. On the Arduino IDE I just reference those libraries and the code compiles great. Visual Studio is very powerful and it enables me to create really nice code, because I can test it on my computer before running it on Arduino. For example, I created this library:

// MyQueue.h

typedef struct QueueItem
{
    void* item;

    QueueItem* next;

    QueueItem()
    {
        item = nullptr;
        next = nullptr;
    }

} QueueItem;


class Queue
{
public:
    unsigned char count;        /* Number of items on queue */
    QueueItem* first;           /* Points to first item on the queue */

    Queue()                     /* Constructor */
    {
        count = 0;
        first = nullptr;
    }

    void enqueue(void* item)    /* Enqueue an object into the queue */
    {
        count++;

        if (first == nullptr)
        {
            first = new QueueItem();
            first->item = item;

            // Log message because we are using the "new" keword. We need to make sure we dispose QueueItem later

            #ifdef windows

            std::cout << "Creating " << first << endl;

            #endif // windows
        }
        else {

            // Find last item
            QueueItem* current = first;
            while (current->next != NULL)
            {
                current = current->next;
            }
            QueueItem* newItem = new QueueItem();
            newItem->item = item;

            // Log message because we are using the "new" keyword. We need to make sure we dispose QueueItem later
            #ifdef windows
            std::cout << "Creating " << newItem << endl;
            #endif // windows

            current->next = newItem;
        }
    }

    void* dequeue()
    {
        if (count == 0)
            return nullptr;

        QueueItem* newFirst = first->next;

        void* pointerToItem = first->item;

        // Log message we are deleting an object because we created it with the 'new' keyword
        #ifdef windows
        std::cout << "Deleting " << first << endl;
        #endif // windows

        delete first;
        first = newFirst;
        count--;

        return pointerToItem;
    }

    void clear()                /* Empty queue */
    {
        while (count > 0)
        {
            dequeue();
        }
    }

    ~Queue()                    /* Destructor. Dispose everything */
    {
        clear();
    }
};

Now on my Arduino sketch, I can have the following code if I reference that header file.

typedef struct Foo
{
    int id;
} Foo;

void someMethod()
{

    Queue q;

    // Create items
    Foo a;
    a.id = 1;

    Foo b;
    b.id = 2;

    // Enqueue a,b and c
    q.enqueue(&a);
    q.enqueue(&b);

    // Deque
    Foo * pointerTo_a = (Foo*)q.dequeue();
    int x = pointerTo_a->id; // =1

    Foo * pointerTo_b = (Foo*)q.dequeue();
    int y = pointerTo_b->id; // =2

    // Error
    Foo * test = (Foo*)q.dequeue();
    // test == null pointer
}

Most people say do not use void pointers. Why!? Because I am using void pointers I can now use this queue class with whatever object I want!

So I guess my question is: Why is everyone trying to stay away and avoid code like this?

I am using the NRF24L01 radio module to send messages to several Arduinos. It is convenient to have a queue of messages to be sent. I would be able to code the same program without allocating memory and avoiding the new keyword. But that code will look ugly in my opinion.

In this quarantine I decided to learn C++ and that has changed the way I code Arduino. The moment I learned C++ I stopped using the Arduino IDE. I been a backed developer for 12 years, and that is the reason why I learned C++ in a couple of months. Arduino is just a hobby for me. I am still very new to microcontrollers and I will like to understand why people stay away from the full power of C++ when it comes to microcontrollers. I know I have only 2 kilobytes of RAM. I will not be allocating that much memory. I still want to take advantage of the C++ programming language by using the new , delete , poineters and destructors`. I want to keep using Visual Studio to write powerful C++ libraries.

In C++ I write interfaces like this

// Note I use uint32_t instead of 'unsigned long' because an unsigned long is different size on Windows than on Arduino. Also I use an unsigned short instead of an int because an unsigned short is the same size on Windows and Arduino.

class IArduinoMethods
{
public:

    // Unsigned long in Arduino
    virtual void delay(uint32_t delayInMilliseconds) = 0;

    virtual void print(const char* text) = 0;


    virtual uint32_t millis() = 0; // Get elapsed time in milliseconds
};

And I then implement the classes like this. For example, this is the class that I will use when testing my code on a windows computer:

// Class to be run on Windows.
class ArduinoMockWindows : public IArduinoMethods
{
public:

    // Inherited via IArduinoMethods
    virtual void delay(uint32_t delayInMilliseconds) override
    {
        // This code will be different on Arduino, and that is why I need this dependency
        Sleep(delayInMilliseconds); // Windows
    }


    virtual uint32_t millis()
    {
        //clock_begin = std::chrono::steady_clock::now();

        std::chrono::steady_clock::time_point now = std::chrono::steady_clock::now();
        auto duration = now.time_since_epoch();
        // etc..
        return someDuration;

    }


};

Because a Windows computer cannot send NRF24 radio messages, I can implement an interface (dependency) that will write to a file, for example instead of sending a real radio packet just for testing.

The caveat is that my libraries will require these dependencies. For my library to work, I will have to pass it an object of type IArduinoMethods and INrfRadio. If I am running my code on Windows I will pass it a class that will implement those methods that can run on windows. Anyways the point is not to show how C++ works. I am just showing how I use pointers and allocate memory for a lot of things.

Because I allocated memory I was able to test my library on Windows and on Arduino for example. I may also create unit tests. I see so many benefits by allocating memory. If I am organized and remember to free the objects I no longer use, I can gain all this benefits. Why people do not code like this when it comes to Arduino?


Edit 1


Now that I understand how heap fragmentation works, I know I have to be careful when using the new keyword.

I hate when people do what they are told to do without understanding how things work. For example, the answer https://arduino.stackexchange.com/a/77078/51226 from Why is the queue library in this question for starters?. There are going to be times when a ring buffer works better and other times when the new keyword works better. Probably the ring buffer will work best for most cases.

Take the following scenario where you only have 1 KB of memory left.

  1. There is a hierarchy of nodes where a node have a child and a sibling. For example, node A can have child B and sibling C. Then child B can have another child, etc.

(I will be storing this in memory)

  1. I have a queue of work that needs to be done.

(I will have to store this work somewhere)

  1. I will have a queue of events

(I will have to store this somewhere)

If I use what most people say I should do then I will be have to:

  1. Reserve 500 kB to be able to store nodes (I will be limited to n number of nodes)

  2. Reserve 250 kB for the queue of work that needs to be done.

  3. Reserve 250 kB for the queue of events.

This is what most people will do and it will work great with no problems of heap fragmentation.

Now this is what I will do

  1. Ensure that everything that I allocate is of size 12 bytes. A node only has its id (unsigned int), child (pointer), type (unsigned char), etc.. with a total of 12 bytes.

  2. Ensure that all the work that will be enqueued is of size 12 bytes as well.

  3. Ensure that all the events that will be enqueued is of size 12 bytes as well.

Now if I have more work than events, this will work. I just have to program in my code that I never allocate more than 70 items. I will have a global variable that has that count of allocations. My code will be more flexible. I will not have to be stuck with strictly 20 events, 20 work and 30 nodes. If I have fewer nodes then I will be able to have more events. **Anyways my point is that one solution is not better than the other. There are going to be scenarios when one solution is better.

In conclusion, just understand how heap fragmentation works and you will gain a lot of power by using the new keyword. Do not be a sheep and do what people tell you to do without understanding how things work.**.


Edit 2


Thanks to @EdgarBonet, I ended up storing Nodes on the stack. Here is why:

I have a hierarchy of nodes that can be represented as:

typedef struct Node
{
   unsigned short id;
   Node * sibling;
   Node * child;
} Node;

As you can see every node is only 6 bytes. That is another reason why I did not care to much about allocating Nodes at the beginning. If I allocate this node on the heap I will be losing 2 more bytes (33%) for every allocation because on every allocation the size of the node has to be stored. As a result I created these two methods and a buffer:

// For this to work a node can never have an id of 0 !!!

Node nodeBuffer[50];                     /* Buffer to store nodes on stack */

Node* allocateNode(Node nodeToAllocate)  /* Method to store a node */
{
    // Find first available spot where a node can be saved
    for (char i = 0; i < 50; i++)
    {
        if (nodeBuffer[i].id == 0)
        {
            nodeBuffer[i] = nodeToAllocate;
            return & nodeBuffer[i];
        }
    }
    return nullptr;
}

void freeNode(Node* nodeToFree)          /* Method to delete a node */
{
    nodeToFree->id = 0; // If the id of a node is 0 this is my convention of knowing it is deleted.
}

And on my code I used to have things like:

Node * a = new Node();
a->id = 234423;
// ....
// .. etc
// ..
delete a;

Now I just have to replace that code with:

Node * a = allocateNode({});
a->id = 234423;
// ....
// .. etc
// ..
freeNode(a);

And my code works exactly the same without having to use the new keyword. I thought it was going to be complicated to refactor the code and create a buffer.

I made this modification because I wanted to be able to store more nodes on my code. By loosing that 33% I was not going to be able to create that many. If I only allocate objects of the same size and I do not allocate that many it is perfectly fine to use the new keyword. > Also in the case of the queue I will allocate and delete objects very fast. Because the objects will not persist on memory for too long, and the chances of having heap fragmentation are very low.

  • 1
    short answer: there is no heap management to defragament it. so you can allocate at setup or create a pool of objects, but don't delete/free the memory. – Juraj Jul 23 at 19:43
  • 2
    Because you have very limited memory space and no operating system to clean up behind you. That means you have to do a lot of things manually that you wouldn’t ordinarily have to do like watch for heap fragmentation. Add to that the fact that an Arduino is a one program at a time device and that sort of eliminates most of the advantage to using heap memory. You got nobody else to share with so it’s ok to be stingy. But it’s mostly about not having the OS to keep things clean for you. – Delta_G Jul 23 at 20:06
  • 1
    Of course you are right, but as shown by your edit, using dynamic allocation safely brigs some uncomfortable constraints. I would not recommend it to a beginner (i.e. most of those who ask questions here). It also has its own memory cost: two bytes per allocated chunk, plus some padding, because it is more than unlikely that all your objects happen to naturally have the same size. – Edgar Bonet Jul 24 at 19:22
  • 1
    @CortAmmon: Do you have an example? The avr-libc's malloc() does heap management, and it runs on devices as small as the ATtiny13A (1 KiB flash, 64 bytes of RAM). Not that it would be very sensible to use it on such device though... – Edgar Bonet Jul 24 at 19:33
  • 1
    @TonoNam You could compress that by using simple segregated storage like boost.pool does. That lets you use arbitrarially sized chunks (at the cost of fragmenting if you don't free them uniformly, of course). The extreme version of this, with 1 large chunck, of course, is the typical storage reservation approach you document above. – Cort Ammon Jul 24 at 20:07
16

Most Arduinos (like the Uno or Nano) have very few RAM, thus you first need to make sure, that you never allocate too much memory. Also dynamically allocating memory can lead to heap fragmentation (heap being the part of memory, where dynamic allocation happens).

In most cases you would want to allocate memory of different sizes (for example arrays of different sizes) or just different objects (with each having it's own size) (!!! This is the key point here). Then you are going to delete some of these objects. That will create holes inside the memory. They can be filled again with objects with the same or less size. As time passes and more allocation and deleting happens, these holes tend to get smaller, up to the point, where none of your new to allocate objects can fit in there. That memory then is unusable. This phenomenon is called heap fragmentation.

These holes appear naturally, also on a PC. But there are 2 key differences:

  1. The Arduino has such little RAM, that the holes can fill up your memory very very fast.

  2. While the PC has an operating system, which manages the RAM (defragmenting it or putting unused stuff away into a paging/swap file), the Arduino does not have an OS. So noone keeps an eye on the real available RAM and noone tidies up the memory once in a while.

That does not mean, that you cannot use dynamic allocation on an Arduino, but that is very risky depending on what exactly you are doing and how long the program should work without failing.

Considering this big caveat, you are very limited on how to use dynamic allocation. Doing it too much will result in very unstable code. The remaining possibilities, where it might be safe to use it, can also easily done with static allocation. For example take your queue, which is basically a linked list. Where is the problem with allocating an array of QueueItems at the start. Each item gets a way to determine, if it is valid. When creating a new item, you just pick the first element in the array, which has a non-valid item, and set it to the desired value. You still can use the data via the pointers, just as before. But now you have it with static allocation.

You might find, that the code looks uglier that way, but you need to adapt to the platform, that you use.

Note, that this does not apply, when you are going to create only objects with the same size. Then any deleted object will leave a hole, where any new object can fit into. The compiler uses that fact. So in that case you are safe. Just every object, that you dynamically create in your program, needs to be the exact same size. That of course also includes objects, that are created inside different libraries or classes. (For this reason it can still be a bad design choice, as you or others (if you want to publish your code), may want to pair your library with other code)

Another way to be safe is to only create and delete objects in closed cycles, meaning, that a created object needs to be deleted, before the next object is created. Though that is not fitting for your application.


On bigger microcontrollers, for example the non-Arduino boards with the ESP32, have much more memory. Thus the use of dynamic allocation is not that bad on them. Though you still don't have an OS to manage the RAM.

| improve this answer | |
  • Thanks a lot for the explanation. I already coded a lot of libraries using pointers. So I guess that now I have to be careful on the number of objects I alocate correct? The code works now because I am allocating very few objects and there is always room in the heap for new objects. As long as my allocations are small size and I do not allocate to many objects I should be good correct? – Tono Nam Jul 23 at 20:18
  • 1
    @TonoNam Yes, that is correct. You need to consider the size, the rate of allocation and how long the code should run. Assuming a constant rate of allocation, the code might run good for a day. But if you want it to run like a month, that could be way different. If you want to use dynamic allocation you will need to just test this out. – chrisl Jul 23 at 20:35
  • 1
    @dandavis I don't know of a way, other than just deleting all dynamic objects and recreating them. If you do this, I would guess, that then you again have a linear bunch of memory without holes in it (effectively defragmented). Though I'm not enough of an expert in the compiler, that I could guarantee that. Also I don't think, that this is really an option most of the time. – chrisl Jul 23 at 20:38
  • 2
    @dandavis: The only way to defrag new/delete allocated memory is to don't. ;-) What I do instead, is to declare an array of buffers of a fixed size, and hand out one of those, no matter how much the caller asked for (up to the buffer size, of course). That mechanism won't cause fragmentation because you never split blocks, so every hole is re-usable. You do have to know - or guess well! - the maximum number of buffers your application will ever need and declare a few more than that for safety. – JRobert Jul 23 at 21:41
  • 2
    I would add to this that dynamic allocation is often slow and somwhat unpredictable in terms of timings (due to fragmentation and other effects), so if you're writing performance or timing sensitive code, it's often best to avoid it even if memory usage is not an issue. – Austin Hemmelgarn Jul 24 at 12:38
7

Dynamic allocation is generally discouraged in embedded applications because you cannot guarantee that you do not exceed (attempt to allocate more than) the available memory. Static allocation will generally have this guarantee although out-of-memory bugs may still be possible.

Additionally, far fewer services or tools are available to automatically manage and mind the memory for you. Any service that does so will consume computational resources.

This means that you inherently create a mechanism in your device that would cause a memory (heap) overflow and possible undefined behavior (UB). This is true even if your code is bug-free and has no memory leaks.

In non-critical, exploration, learning, and prototype applications this may not be important.

Consider that without careful consideration undefined behavior can result in hardware failures and unsafe performance, for example if the device reconfigures GPIO through an errant write to the correct registers during a crash.

| improve this answer | |
  • Yes Dynamic allocation is generally discouraged. +1 for using the word generally. In some cases it might work. I will just have to keep track of how many objects I allocate and ensure that all of them are of the same size. – Tono Nam Jul 24 at 19:48
5

For starters, fix your library

As noted by @crasic, dynamic memory allocation is generally not recommended for embedded systems. It may be acceptable for embedded devices which have a larger amount of free memory - embedded Linux is commonly used, for example, and all Linux apps/services will tend to use dynamic memory allocation - but on small devices such as an Arduino there simply is no guarantee that this will work.

Your library illustrates one common reason why this is a problem. Your enqueue() function creates a new QueueItem() but does not check that the allocation succeeded. The result of failed allocation may either be a C++ bad_alloc exception, or it may be returning a null pointer, which when you reference it will give a system memory access exception (SIGSEGV signal in Linux, for example). It is nearly universal in Linux and Windows programming to ignore memory allocation failure (as encouraged by most textbooks), because the massive amount of free RAM and the existence of virtual memory makes this very unlikely, but this is unacceptable in embedded programming.

More generally though, as @crasic says, memory fragmentation can leave even non-buggy code unable to allocate memory. The result will be a failure to allocate memory, but the code will at least know this has happened and will probably be able to continue.

But better, use a fixed-size FIFO queue instead

Your code relies on dynamic allocation to add and remove elements in a queue. It is perfectly possible (and equally easy coding-wise) to create a fixed-size array for the queue, so the various failure modes of dynamic allocation simply do not apply. An item to be queued is simply copied into the next free queue slot, and a queue slot is marked free when it has been used. (Don't forget to use a mutex when adding and removing items from the queue, because adding and removing will often be called from different places.)

The queue can be made whatever size you feel is appropriate (allowing for how much RAM you have). With a fixed size, you are forced to make a design decision on what should happen if the queue overflows - do you delete the oldest data to make room for the new value, or do you ignore the new value? This may seem an unwelcome new feature, but it is a good thing, because the third option which you've currently got is that your code goes "Aaaarrggghhh I don't know what to do!" and crashes fatally, and we don't really want that.

| improve this answer | |
  • 3
    A fixed-size FIFO queue is typically implemented as a ring buffer. – Edgar Bonet Jul 24 at 10:24
  • @EdgarBonet Yes it is. The OP should be able to find plenty of existing code for FIFOs online though, so I guess I'm more interested in helping them getting the concept than exactly how they do the implementation. – Graham Jul 24 at 11:54
  • The FIFO fix sized as ring buffer is a great sollution. There are going to be times when the ring buffer is better (probably most of the time) and there are others when it is not. Take a look at the edit of the question. If you keep track of allocations and you never exceed the count of allocations all of the same size you should have no problem allocating a new queue item. – Tono Nam Jul 24 at 15:14
  • Exactly graham your answer is probably the best solution for most of the cases and also the safest. But for cases when I am building a hierarchy of nodes it will be harder to create with a buffer. If I am already allocating Nodes I guess I can keep allocating them using the queue. My point is that if you know how things work it is ok to not go with the convention. Also the probability of an alloc not working is very small since I am not using interupts or running my code in different places. For the rest of my projects I will probably use your solution. – Tono Nam Jul 24 at 17:55
  • @TonoNam You are assuming there that your allocation granularity goes down to at least 4 bytes. If the granularity is 8 bytes at best, then each 12-byte allocation will actually occupy 16 bytes of RAM. So your heap-based code would only be able to store 3/4 of what could be stored with a statically-allocated queue. Plus whatever overheads are involved in running the heap, which can be significant when you're allocating small amounts of data (and 12 bytes is usually "small"). You can't just divide RAM length by structure length and assume that's how many you get. – Graham Jul 24 at 21:19
3

I'm adding this not so much to add to the answer as to add some real world implications for those that may be down this particular rabbit hole. It's nice to talk about what could happen theoretically, but a new programmer may still be tempted to think that he can out-think these limitation and still do something useful. Here is some real world talk about why that is foolish even if you are capable.

Let's say we're developing code on an Arduino UNO. We've got 2K of RAM to work with. We have a class that loads a list of names, maybe it's a building access device or something. Anyways, this hypothetical class has a name field to store someone's name. And we decide to use the String class to hold the name as a String.

Let's say after our program is all there and doing what it's doing that there is 500 bytes left for this list of objects, each with a name field that could be of varying length. So we run along nicely for years with a crew of 14 or 15 people with an average name length of 30 characters or so.

But one day a new guy signs up. And his name is really long. Let's say it takes 100 characters. Even if we're smart coders and only have one copy of this String in memory, we've got it there and suddenly it doesn't fit. Now a program that has worked for years suddenly fails. And nobody knows why.

So the solution is easy right? Enforce a maximum limit on the length of the name. Some simple code that checks the name length and we can write a great piece that still allows the variable name length and won't let you create a new user if there's less than that much left. Seems simple enough, but then Becky in accounting gets married and her last name changes from Smith to Wolfeschlegelsteinhausenbergerdorff and suddenly our program breaks again for no reason.

So the solution is simple right? We'll enforce a maximum length and we'll be sure to reserve enough memory for each object that it can afford to have the maximum length name. And that's something that we do most efficiently without dynamic allocation since we already know the size of the object.

I hear what you're saying, "but Delta-G, if we have all those short names in there, why are we going to waste all that memory on them when we don't have to. Let's only save space for a long one if we have a long one." And I like your thinking, this is good thinking. But it doesn't help anything to save that memory. If you do save some, what are you going to do with it? If your program uses it, then there is no longer room for the longer case and suddenly you have to enforce an even shorter maximum length to accommodate that usage.

Say for instance we have 500 bytes of room and we enforce a maximum length of 50 bytes for 10 users. And let's say that when the names are short we want to let the program use some of that saved space. If the program can encroach 100 bytes into that space when the names are short, then why wouldn't the same situation happen with long names? So really since the program can use all but 400 bytes then there's really only 400 bytes of room and we have to enforce a 40 byte maximum for 10 users or 50 bytes for 8.

Since you're going to have to make that sacrifice anyway, then it only makes sense to remove the work of dynamic allocation and just make things fixed sizes or use fixed size buffers.

If we had a PC with gigabytes of memory, we wouldn't even be thinking about this. But on an Arduino UNO with 2K bytes of memory it can become a big problem really fast.

The other problem is that these bugs are so insidious. If out of memory bugs just caused a simple crash and the thing no longer worked then it wouldn't be nearly so scary. But that's not how out of memory bugs work on a microcontroller. It all depends on how things are arranged in memory by the compiler.

These bugs often manifest as something that seems to work most of the time but has some funny bugs nobody can explain. Maybe there's only a problem if someone has a name that is exactly 26 characters long and tries to open the door on a Wednesday. Or maybe the issue will only arise if Becky logs in immediately after Bob. Maybe it just garbles three letters on the screen but other than that everything works. Maybe with a different name changed that suddenly turns into our lock opens for anyone. There's no guessing or explaining out of memory bugs. So we have to be super careful to avoid even the remote possibility of running into one.

And that's why we avoid using dynamic allocation on small microcontrollers. At the end of the day, there's nothing you can save with it, and even if you could the consequences of getting something a little wrong are terribly frustrating. With these types of programs you almost always have to end up enforcing some sort of limit on everything and once you're enforcing limits there's no use for dynamic allocation anymore.

| improve this answer | |
  • Again in your real life example you are allocating objects of different sizes (names). That will lead to heap fragmentation. If you where to allocate names of the same size and very few of them it is perfectly fine to use heap allocation. – Tono Nam Jul 25 at 14:40
  • But like I said in the example, if you’re allocating a fixed number of things of a fixed size then why do you want to use dynamic allocation to do that? What would be the advantage at that point? – Delta_G Jul 25 at 16:34
  • That if I have multiple queues I do not have to create one buffer for each. There might be cases when allocation is helpful. My point is that if you understand how it works it is ok to use it. Probably most of the time it makes no sense to use it but not never. – Tono Nam Jul 27 at 3:28
  • Yeah not never, but not for what you're thinking either. You run into the same issue. If you have multiple queues and you want them to be able to share a buffer space then it would certainly be easier to have one buffer allocated and a single class that is controlling adding and removing. I'm thinking probably anything that can add to the queue needs to inherit some base class that allows you to have code in one place doing it. That is exactly the use case I'm on about where you think you know what you're doing and one day some corner case you never suspected bites you. – Delta_G Jul 27 at 3:50
  • I guess it's one of those things that you just can't truly learn any way but the hard way. But at the end of the day, if you want shared buffer space you must put a limit on its size and if you're going to do that then you might as well allocate it all and let your code control putting things in and out. – Delta_G Jul 27 at 3:53
-1

As someone interested in how hardware enables computing, there are actually a number of fascinating facts as to why the heap is dangerous on embedded systems beyond just not having much RAM. Most issues you'd encounter with an Arduino or similar system are not from exceeding the RAM's size with variables, but from memory fragmentation. This is a side effect of how the heap allocates memory in embedded systems, which commonly don't have a memory manager.

The heap on simple devices like the Arduino is what is closest to what is commonly known as a "base and bounds" system (technically, it's stack allocated, which can also be looked up if you are curious). Memory is allocated somewhere, and is then marked with information about where it is in memory and how much it has. When it is deallocated, this region becomes free again. Problems arise because this space must be contiguous. Think of allocated memory as an array (which it basically is); there's no logic to say "oops, there's another object here, skip 37 bytes and continue.

If you do repeated allocations, chunks of memory are parceled out and move further up the heap, since two chunks of memory obviously can't occupy the same space. Memory may become available again if some of it is freed, but that leaves the rest of it "floating" higher up the heap, in the middle of the memory space (if you've ever played a certain 3D voxel building game, think of mining out part of a tree trunk). Further allocations will then fill in parts of the cleared areas in the deallocated portions (or at the top of the used heap, if they won't fit in the cleared areas), but unless the newly-allocated memory is the exact same size as what was removed, holes form where the free memory is too small to fit anything else. In the end, there may be a lot of free memory, but none of it can be used since there are no contiguous sections even if there are a bunch of bytes here and there.

As mentioned, one workaround is to ensure that all allocated memory is the same size, but may does not help when so much of the Arduino system uses dynamic memory on its own. This is mainly anything to do with Strings (especially returning them, concatenation, or setting one to another), but there may well be other utilities that use it, making debugging itself hazardous. Anything that lets you "register" a callback, listener, or user function will also most likely use dynamic memory, and I imagine a WiFi library with "scan" functionality or a filesystem library (SD card, for example) likely will too.

Many of the inbuilt String libraries actually make full copies of heap memory on return or definition, so even if the original string is then deallocated automatically by the String library when that variable goes out of scope, there were briefly two copies of that item on the heap, causing fragmentation (since the second one was bumped forward by the first, leaving a hole when the first is deleted but the second stays).

It would probably be safe if you use dynamic memory allocation in very small amounts and infrequently, as long as there are no ways that you can graph out the maximum allocated memory in a way that would prevent the allocation of a new piece, but this is admittedly annoying to test.

A not-so-perfect solution exists where you use the heap as something like a stack, and you allocate all the extra-large scratch space while you run a task, and then deallocate it before you do the next item or otherwise allocate memory again. This lets you handle problems that would take up more memory than you'd have if you used a global for each, but, then again, this can also be done if you just enclose that section of code with curly brackets and use a local array (which puts it on the actual stack). Note that some systems (like the ESP8266, which can be programmed with the Arduino framework, but most definitely isn't an Arduino) may have limitations on the stack size, so dynamic memory may actually be required in some cases.

Interestingly, despite the heap being stack allocated, the actual stack is immune to this issue. This is because of how return-oriented programming works. Any function call or memory allocation on the stack (which, as you know, is done by defining a variable the normal way) is always placed on top, and when it returns or goes out of scope, is deleted. Since there is no way to delete things from the middle of the stack, there is never any fragmentation and thus your free memory is always available as long as you don't exceed physical resources. Stack allocation thus only fails when the allocated memory stops behaving like a stack (which is unfortunately often).

As a final note, modern computer OSes use a much more advanced technique called paging, which your solution approaches (the kernel may have and use exceptions to this rule, since it's time critical and paging is slightly slower, but there's a reason that coding the kernel is so painstaking). In paging, all the memory is specially allocated in equal-sized blocks, and blocks can be portioned out to best meet memory requests. However, the blocks can be arranged in any order and do not even need to be physically adjacent in memory. This means that there is no way that a piece of memory cannot be allocated, as the chunks are always the same size (and thus always fit into the holes). It's the memory management unit that performs the rest of the magic by making all those tiny blocks into what seems like a larger expanse of memory (and also by handling memory ownership, but that's not relevant here).

Unfortunately, paging requires hardware support, a lot more memory to hold the page table, and OS support (or at least some kind of manager to periodically kick in and reorganize things for you). None of these are present in an Arduino, and in fact would cause problems for the sort of real-time code that was originally intended to run on an Arduino's CPU. Remember, the Arduino was built around a small, cheap chip that happened to have an open-source programming interface and compiler (and a few other projects who had their code and IDE "borrowed"), and was never really designed for the sorts of uses that we commonly put it to (which is why computer programming isn't quite the same as embedded development; the coder must think in a much more low-level way than normal, and is why C/C++ is commonly used--it's somewhat closer to Assembly than most other languages, although C++ is getting away from that). Even the architecture of the AVR CPU is rather telling of its actual use case: High-speed, real-time processing. The memory and data buses are independent, allowing for code to be executed even while it streams data from RAM, EEPROM, or an I/O pin.

There's a useful free guide to operating system design called "Operating Systems: Three Easy Pieces," which is the source of some of what I learned and then wrote here. Since the authors don't want its chapters linked directly, and the landing page has a number of spurious links to random books, I can't link it directly, but you can always look it up if you are curious. You'd want the topics on memory management, of course, and the chapters themselves are linked in the colored table section.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.