Return to Revisions

The short answer is that fragmentation crashes are infrequent because they require very specific conditions to arise—and that's the problem.

Imagine you have a crash that occurs once every few days and can't figure out why. It never happens while testing and doesn't seem to be caused by anything specific.

Then it turns out that your code is printing numbers to a string, usually 4 digits but sometimes 2 or 3. And it turns out that very specific sequences of the lengths of strings being allocated and deallocated trigger a crash. But there's no good way to analyse or predict the problem because it hinges on absolutely everything that's happened since boot. If there was a 3- instead of 4-digit number 8 hours ago, that completely changes what would need to happen now to trigger a crash.

While answering this question I tried to come up with some code that would leave memory very fragmented. It was very difficult. Memory fragmentation is very sensitive to what happens, in what order. Basically it's a highly chaotic system.

This is reminiscent of problems related to multithreading, where running a simple program multiple times can easily give different results. Problems like this are really, really frustrating to identify and diagnose. A lot of people have felt the pain and that is why there is such stigma about String.

To answer your questions:

1. why should I not use String if it makes my work so much easier?

As long as you understand the pitfalls and how to avoid them, sometimes Strings are the best tool for the job.

The main goal of avoiding String is to prevent severe heap fragmentation. There are other ways to do that, though:

• Don't store lots of heap-allocated objects on a long-term basis. If you only have 3 global String variables then it's probably fine to allocate 100 small strings if you delete them before doing anything else
• If you have to store many heap-allocated objects long-term, try not to allocate them during a period of a lot of heap allocations, deallocations, and resizings (such as during a loop when a string is being built). You want to avoid these long-term objects being given "random" positions through memory.

If you want to use String in an application where reliable long-term operation is important, you really have to be thorough in understanding your memory usage patterns and why they are unlikely to trigger a problem.

I should add that each String adds several bytes of memory overhead, both for the string descriptor and for the invisible bookkeeping that the malloc() implementation does. They are also slower to access than char []s.

2. Is it possible to quantify the fragmentation and get a feel of what's safe and when it becomes risky?

This is difficult because of how sensitive things are to tiny differences in allocation history. There are a few simple analyses you can do, though.

If you have n heap-allocated objects, you have n+1 fragments (although some fragments may be zero size.) The average fragment size will be ≤ the amount of free space divided by n+1. For example if you have 19 allocated objects and 2000 bytes of remaining space, your average fragment size will be 100 bytes. Mathematically this implies that at least one fragment is ≥ this size, and therefore you are guaranteed to be able to allocate anything smaller than 100 bytes. Keep in mind though that every allocated object consumes a few bytes of invisible bookkeeping data used by the runtime's implementation of malloc(), and there may be other hidden things floating around in the system, like some objects allocated by libraries. Also remember that on Arduino, SRAM is shared by stack and heap.

Now let's say you have 8KB of heap space and you allocate a lot of stuff, then deallocate a lot of stuff, leaving exactly 3 small objects allocated. This will divide your heap into 4 regions. The average size will be just under 2KB and so no matter how unlucky you are, one or more of the regions will be at least that size. So you should be able to allocate one large object of around 2KB, or, allocate hundreds of small objects, or allocate one object and keep resizing it anywhere up to 2KB. If you then free everything except for 3 small objects, you will be back in the same situation: you are guaranteed a region of at least 2KB.

There are two noteworthy conclusions:

• If the maximum number of items you will ever allocate is n, and their maximum size is s, and your heap size is at least (n+1) × (s+4), you will never have a fragmentation problem. (4 is an architecture-dependent fudge factor to cover malloc bookkeeping and padding issues.)
• If there are "checkpoints" in your code where only a few objects are allocated, this makes it easier to reason about what can happen between these checkpoints.

Are there any tools to measure / alert / help us know how close we are to fall off that cliff?

Not for Arduino that I know of. The problem is, a program susceptible to severe fragmentation may only display signs for short periods once every few days or something.

The easiest technique you can use is to allocate say 30% of your memory with malloc() at the start of your program to put more heap pressure on it, and see if it still works. This isn't guaranteed to bring the problems out of the woodwork, but it greatly boosts the chances that you will see something.

You can also write a function to try to allocate the largest objects possible over and over, slowly reducing the size, and see to what extent you are prevented from allocating large objects but can allocate small ones. I was going to post one but I decided it would be of limited benefit. Beware that this may reduce the available stack space.

If you really want to see what is going on with your heap you can look at the source of your malloc() implementation and inspect its data structures from within your program. In this case it seems to be as simple as putting this at the start of your code

struct __freelist {
  size_t sz;
  struct __freelist *nx;
};
extern struct __freelist *__flp;

and then you can traverse the contents of the freelist using __flp.