3

I'm trying to understand if the following bit of code is subject to memory fragmentation.

Let's say I incrementally build a string within a function and I don't know how large the string should be.

String f() {
    String s = String("");
    s += "a"; // ...
    s += "bc"; // ...
    return s;
}

The String object does dynamic memory allocation internally, but s is on the stack, so once the function returns, the s object presumably deallocates and dynamically allocated memory is freed.

Before this happens, the String object to be returned must be copied from s. Since String objects hold internal data in dynamically allocated buffers, this means that the s internal buffer is allocated, then the return object internal buffer is allocated, then the s internal buffer is deallocated.

The return object internal buffer allocation is sandwiched between the s object alloc and dealloc.

To me, this implies that this will cause memory fragmentation. Am I reading this properly, or is this not the case? If so, does this also imply that functions like Serial.readString are also subject to memory fragmentation?

3

Pretty much every use of the String object can lead to memory fragmentation. Especially concatenating and copying objects.

I cover it here: https://hackingmajenkoblog.wordpress.com/2016/02/04/the-evils-of-arduino-strings/

You are much better off never using the String class and instead sticking to basic C strings (char arrays).

  • Thanks. And what about all the other classes in the Arduino library? A search at the Arduino source code finds a lot of ...allocs. Are Arduino projects subject to heap fragmentation in general? – Ana Mar 26 '16 at 19:19
  • There is very little allocation done in the core. It's only really String that does it. Libraries, though, are a law unto themselves. – Majenko Mar 26 '16 at 19:22
2

Memory fragmentation is hard to predict, as it depends on how your different allocation patters interact. This single pattern, per se, looks safe. By safe I mean that if

  1. your heap is not fragmented when you enter this function, and
  2. you do no dynamic allocation inside the function other than growing the string,

then the string will be allocated to the top of the heap and grow from there without moving or making holes. You can check this is the case by looking at the address of the string's internal buffer, which is given by the c_str() method. It should not change inside the function:

String f() {
    String s = String("");
    const char * p = s.c_str();
    s += "a"; // ...
    s += "bc"; // ...
    if (p != s.c_str())
        Serial.println(F("Warning: memory fragmentation."));
    return s;
}

Edit: I wrote this small test program to show the behaviour of the heap when you use string concatenation this way:

extern uintptr_t __brkval;

String f() {
    String s("");
    const char * p = s.c_str();
    Serial.print(F("  f(): string buffer @ 0x"));
    Serial.println((uintptr_t) p, 16);
    for (int i = 0; i < random(8) + 1; i++)
        s += random(2) ? "a": "bc";
    if (p != s.c_str())
        Serial.println(F("Warning: memory fragmentation."));
    Serial.print(F("        top of heap at 0x"));
    Serial.println(__brkval, 16);
    return s;
}

void setup() {
    Serial.begin(9600);
    Serial.print(F("***     heap starts at 0x"));
    Serial.println((uintptr_t) __malloc_heap_start, 16);
}

void loop() {
    Serial.print(F("loop(): top of heap at 0x"));
    Serial.println(__brkval, 16);
    String s = f();
    Serial.print(F("  f() returned "));
    Serial.println(s);
    Serial.print(F("        with buffer at 0x"));
    Serial.println((uintptr_t) s.c_str(), 16);
    delay(1000);
}

The output of the program is:

***     heap starts at 0x1D7
loop(): top of heap at 0x0
  f(): string buffer @ 0x1D9
        top of heap at 0x1DF
  f() returned abcbc
        with buffer at 0x1D9
loop(): top of heap at 0x1D7
  f(): string buffer @ 0x1D9
        top of heap at 0x1DF
  f() returned abcbc
        with buffer at 0x1D9
loop(): top of heap at 0x1D7
  f(): string buffer @ 0x1D9
        top of heap at 0x1DC
  f() returned aa
        with buffer at 0x1D9
loop(): top of heap at 0x1D7
  f(): string buffer @ 0x1D9
        top of heap at 0x1E2
  f() returned aabcabca
        with buffer at 0x1D9
[...]

The very first “top of heap at” is bogus because at this point the malloc library has not been initialized. Besides that, you can see here that:

  • the heap is always empty (top = bottom) at the beginning of loop()
  • the string is always allocated at the same place
  • the heap size inside f() varies depending on the string's length
  • the string is not copied when returned to the caller, as the internal buffer is still at the same address.

However, if the statement String s = f(); is replaced by String s; s = f();, then the string is copied when returned to the caller, which doubles the amount of RAM required to handle it. This is presumably because only the first form allows copy elision optimization. (This paragraph was added after reading Nick Gammon's answer, which made me realize the copy elision issue).

Keep in mind that this works so nicely only because there is nothing else doing dynamic allocation in this small program. This usage pattern is safe, but once you start doing dynamic allocation in different parts of the program, it becomes difficult to ensure that the allocation/deallocation pattern is still safe vs. memory fragmentation.

1

The worst line in your example is this:

s += "a"; // ...

Any sort of loop that adds one byte to a String is potentially going to fragment memory. First the String class allocates zero bytes for the string, then when you add a byte, it has to allocate one byte, then when you add another byte it has to deallocate (free) that byte and allocate two bytes, and so on.

The allocator tries to be efficient, so eventually when you get up to three bytes you will, with luck, actually get the memory previously allocated to the one-byte string followed by the two-byte string.

But if other allocations have occurred (eg. another use of String elsewhere in the program) this might not be possible. Eventually you have lots of small gaps of maybe one or two bytes, with other stuff inbetween. Unless they are adjacent they cannot be recombined into a bigger block. This is your "fragmentation".


When you += "a", it does not free the previously allocated space: it calls realloc() to grow the buffer, and realloc() tries to grow it in place. This works fine, without fragmentation, as long as your buffer is at the top of the heap.

Good point, however if you have multiple String instances, this may not work.

Edgar Bonet is right, however there is certainly the potential, with multiple String instances, for each of them to prevent the others from growing their buffer size neatly. In the example in the question, you will probably find that when f() returns, it returns a copy of the String allocated on the stack, thus we now have 2 x String instances.


While Edgar was writing some test code, so was I. :)

#include <memdebug.h>

String foo;

String f() {
  String s = String("");
  s += "a"; // ...
  s += "bc"; // ...
  return s;
}  // end of f

void showMemoryUsage ()
{
  Serial.println (F("---------------"));
  Serial.print (F("Largest block in freelist: "));
  Serial.println (getLargestBlockInFreeList ());
  Serial.print (F("Largest available memory: "));
  Serial.println (getLargestAvailableMemoryBlock ());
  Serial.print (F("Free memory: "));
  Serial.println (getFreeMemory ());
  Serial.print (F("address of foo data = "));
  Serial.println ((int) foo.c_str ());
} // end of showMemoryUsage

void setup() 
{
  Serial.begin (115200);
  Serial.println ();
  showMemoryUsage ();
  Serial.println (F("Calling f() ..."));
  foo = f ();
  showMemoryUsage ();
  Serial.println (F("Calling f() ..."));
  foo = f ();
  showMemoryUsage ();
  Serial.print (F("foo = "));
  Serial.println (foo);
}  // end of setup

void loop ()
{
}  // end of loop

Memory debug library from http://andybrown.me.uk/wk/2011/01/01/debugging-avr-dynamic-memory-allocation/

Output:

---------------
Largest block in freelist: 0
Largest available memory: 1675
Free memory: 1677
address of foo data = 478
Calling f() ...
---------------
Largest block in freelist: 2
Largest available memory: 1669
Free memory: 1675
address of foo data = 482
Calling f() ...
---------------
Largest block in freelist: 2
Largest available memory: 1669
Free memory: 1675
address of foo data = 482
foo = abc

The address of the data in foo has changed from 478 to 482, so my prediction above was right. The function f() made a String, but a second copy was returned, hence we have now "lost" 4 bytes in the heap. Well, not lost, but there is a gap.

Calling f() a second time did not make the fragmentation worse.


BTW, this is unnecessary:

  String s = String("");

Just write:

  String s;

You are invoking a second String just to provide something to copy into the first String. Strings start off empty so this is just wasted time.

  • Actually, it first allocates one byte (for the NULL at the end of ""), not zero. When you += "a", it does not free the previously allocated space: it calls realloc() to grow the buffer, and realloc() tries to grow it in place. This works fine, without fragmentation, as long as your buffer is at the top of the heap. – Edgar Bonet Mar 26 '16 at 21:24
  • See amended answer. – Nick Gammon Mar 26 '16 at 21:47
  • Added example code which tests the fragmentation theory. – Nick Gammon Mar 26 '16 at 22:19
  • Thanks for the test. It made me realize mine worked so well (zero copy) only because I used an idiom that allowed the compiler to do copy elision optimization. I added a note to my own answer. It's nice to learn stuff from comparing and elaborating answers this way. ;-) – Edgar Bonet Mar 27 '16 at 20:36
  • I also had to print foo or the compiler thought I had made a useless variable and optimized it away. :) – Nick Gammon Mar 27 '16 at 21:10

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.