Memory allocation on Arduino Due never returns NULL

Question

I'm working on a project that uses quite a bit of RAM to store and analyze data that is sent from the PC. The program heavily relies on malloc/free, which normally works just fine. However, if the data set gets to big - which I can't tell beforehand - the Arduino just dies. Some analysis found that it has to do with memory management. Running a simple sketch which just does

void loop() {
  int SIZE_TO_TEST = (1024 * 10);
  int* mem = (int*)malloc(SIZE_TO_TEST);
  if (mem == nullptr)
  {
    // This never happens
    Serial.print("Allocation failed\r\n");
    return;
  }
  Serial.print("Allocation succeeded\r\n");
  Serial.print((int)mem, HEX); // this always prints 0x200712E0, regardless of the size
  Serial.println();
  for (int i = 0; i < SIZE_TO_TEST / 4; i++)
  {
    mem[i] = i;
  }

  for (int i = 0; i < SIZE_TO_TEST / 4; i++)
  {
    if (mem[i] != i)
    {
      // You better get a new board if this happens
      Serial.print("HARDWARE ERROR: Memory broken\r\n");
    }
  }
  free(mem);
}

works fine and repeatedly prints "Allocation succeeded". When I start increasing the SIZE_TO_TEST, the CPU crashes when the value is over the effective memory size of 96k. The weird thing is, that even when the value is 1000k (far beyond what the uP actually has), the pointer returned by malloc() is still the same memory address, not NULL, as one would expect. The crash also does not occur if the allocated memory is not used (if the two for loops are commented out), so I suspect the actual crash occurs because the program tries to write to memory that is not actually there.

How do I find out that the memory is exhausted? Why does malloc() never return NULL?

(Note: I know about the problems of memory fragmentation with small micro controllers, but I can work around that issue)

Answer 1

Why

This is a partial answer, for now, mostly with regard to:

Why does malloc() never return NULL?

So, the Due appears to use Newlib as its libc implementation; that is the systems C (standard and some non-standard) runtime that includes malloc(), or the greater part of malloc() anyway. The Newlib malloc() relies on an sbrk() function which is implemented by the specific system, the Due in this case. This name and basic idea comes out of Unix; you can read about the interplay between malloc and sbrk some without it having to be in connection with Newlib or the Due specifically. In short, sbrk extends the area that malloc has to work with and malloc divides that area into requested chunks. Here is Newlib's documentation for sbrk and a sample implementation.

The Due (SAM) core for Arduino implements sbrk as:

extern caddr_t _sbrk ( int incr )
{
    static unsigned char *heap = NULL ;
    unsigned char *prev_heap ;

    if ( heap == NULL )
    {
        heap = (unsigned char *)&_end ;
    }
    prev_heap = heap;

    heap += incr ;

    return (caddr_t) prev_heap ;
}

This is a kind of degenerate implementation of _sbrk that just blindly says, "You want more memory, sure here you go" without limit. If you look at the sample sbrk implementation for Newlib, you'll see it just calls abort() instead of a proper failure that would result in malloc returning NULL, which is admittedly not great, but at least it's not pretending that everything is fine.

There should be a condition somewhere in this code that check so see if there's any more space to be had and sets errno = ENOMEM and effectively does return -1 if there is not.

I modified this code to allow me to set a variable from the sketch that could force the next call to _sbrk to fail as described above. And sure enough, on the next call to malloc() it returned NULL because _sbrk had indicated failure.

So the _sbrk implementation provided by the Due/sam core should be changed so that malloc fails when appropriate. That said, I'm not precisely sure how that should be done. So I'm going to hold off on making specific recommendations about it. Maybe I look into it more I'll come back and update this with something more useful, addressing your other question of:

How do I find out that the memory is exhausted?

In rough terms though, the answer going to be that you modify that function so it returns -1 with ENOMEM under the right conditions.

---

How

This is the previously mentioned update with some details on the how:

How do I find out that the memory is exhausted?

So I've made something to give you an idea what the condition would look like. I'm not strictly recommending you use it; for one thing it's barely been tested.

From the ATSAM3X8E's family datasheet:

SRAM0 is accessible over the system Cortex-M3 bus at address 0x2000 0000 and SRAM1 at address 0x2008 0000. The user can see the SRAM as contiguous thanks to mirror effect, giving 0x2007 0000 - 0x2008 7FFF for SAM3X/A8

The stack pointer starts near the top of memory 0x2008 7FFF and grows downward. The _end symbol marks the end of the mutable static storage duration variables or the beginning of the heap. Somewhere closer to 0x2007 0000; the fewer of these variables the closer.

On this system, which has a fairly common layout, the heap grows up with positive increments to sbrk as the stack pointer grows down with stack frames (local variables, return addresses etc). So, "the end" of memory happens when the heap would otherwise allocate over the stack or the stack runs into the heap as your pushing things onto it.

So a typical thing to do is to check to see whether or not the sbrk's argument would cause the edge of the heap to get "too close" to the stack.

In the the /.arduino15/packages/arduino/hardware/sam/1.6.12/cores/arduino/syscalls_sam3.c, I've include some extra headers:

#include <errno.h>
#include <stdlib.h>

And put the following as a replacement _sbrk():

size_t __malloc_margin = 4 * (size_t)1024;
extern caddr_t _sbrk (int incr) {
    static const unsigned char *       heap      = (unsigned char *)&_end ;
    /****/ const unsigned char * const prev_heap = heap;

    if (incr > 0) {
        // Extra checks for stack growing


        if (incr >= 96 * (size_t)1024) {
            // The Due only has 96K of ram,
            // so any request for 96K or greater
            // is a failure out of the gate.
            errno = ENOMEM;
            return (caddr_t)-1;
        }

        unsigned char *stack_ptr;

        asm volatile(
            "mov %[sp_out], sp"
            : [sp_out] "=r" (stack_ptr)
            :
        );

        if (stack_ptr < heap) {
            // We're already in real trouble.
            abort();
        }

        if (stack_ptr - heap  <  incr + __malloc_margin) {
            // Not enough memory considering safety margin.
            errno = ENOMEM;
            return (caddr_t)-1;
        }
    }

    heap      += incr ;
    return (caddr_t) prev_heap ;
}

__malloc_margin was used as a variable name just because it's the name that avr-libc uses for the same purpose, namely to tune the minimum distance between the stack and heap during an allocation that the break to increase. By the way, you can see this same kind of check happen in avr-libc's implementation of malloc (which also takes sbrk's role.) Why is __malloc_margin 4K ? No really scientific reason. It's about 4% of memory, so it's not large, and it's not completely inconceivable to me that someone would try to put local variable(s) approaching 4k in a stack frame on a system that has 96kb total memory. 4K may not be an appropriate default though; more thought should go into that. Having it in a variable like this allows it to be tuned at runtime; usually there would be a header that provides an extern declaration for it.

I may add more later to explain, but it short if the break is being increased, this sbrk looks to see if the new break would get within __malloc_margin of the stack pointer on a request, an if it would it returns the -1 value and errno = ENOMEM to cause malloc to behave correctly from the user's perspective.

Before anyone bothers to mention: Yes, I know you can take the address of a local to get a stack pointer value. Yes, the check to see if the single allocation is larger than 96K is probably unnecessary. Yup, it has Due specific stuff in it even though it's not strictly a Due; there are probably identifiers that could be used instead. It should probably abort() if sbrk tries to go below 0 sized heap. It's just a somewhat working illustration of what should be in _sbrk(). More thought and at least one change should be put into it before general use.

Regarding abort()

It occurs to me in some cases abort() may be an appropriate way to handle this. If you believe that you can characterize the system (or the sketch if you like) at runtime so well that malloc() failing can be regarded as a major oversight, then calling abort() in sbrk() could make sense. Or at least providing the option to do that.

In the comments you asked:

What does abort() exactly [do] on the Due?

Well, Newlib documentation says:

Before terminating your program, abort raises the exception SIGABRT (using ‘raise(SIGABRT)’).

and then further down:

Supporting OS subroutines required: _exit and optionally, write.

The SIGABRT and _exit parts are more or less standard behaviour. So it will call your signal handler for SIGABRT if you have one.

So then what does _exit do? It loops forever.

I called abort() in a sketch and dumped the following via an arm version of the binutils objdump with -dS command-line options.

Here's the relevant abort() code:

00081b98 <abort>:
   81b98:   b508        push    {r3, lr}
   81b9a:   2006        movs    r0, #6
   81b9c:   f000 fb5c   bl  82258 <raise>
   81ba0:   2001        movs    r0, #1
   81ba2:   f7fe fec5   bl  80930 <_exit>
   81ba6:   bf00        nop

bl <raise> would in turn call your signal handler. and bl <_exit> calls exit which displays as:

00080930 <_exit>:

extern void _exit( int status )
{
   80930:   e7fe        b.n 80930 <_exit>

00080932 <_kill>:

    for ( ; ; ) ;
}

It appears the optimizer has combined some things here, but essentially _exit has an instruction that jumps (branches) to itself, equivelent to for(;;);.

I half-expected the abort(); code to disable interrupts before calling _exit(). If you do plan on abort() in your _sbrk() that might be something to think about. You may also want to provide a global flag that can be inspected from SIGABRT that allows the signal handler to do something diagnostically appropriate specifically for _sbrk() failures.
Perhaps sbrk should set a flag in a no-init data section and then set the watchdog timer and let it expire (or provide the SIGABRT handler with the information to do that). Lots of things to consider.

Answer 2

I think I found a workaround. It relies on the fact that on simple program architectures such as the one used on most microcontrollers, the heap grows upwards while the stack grows backwards.

const int MIN_FREE_STACK = 512;

void* mallocEx(int size)
{
  void* stackPtr = alloca(4); // This returns a pointer to the current bottom of the stack
  PrintAddress("StackPtr ", stackPtr);
  void* ptr = malloc(size);
  PrintAddress("NewInstance ", ptr);
  if ((byte*)ptr + size > ((byte*)stackPtr - MIN_FREE_STACK))
  {
    free(ptr); // This memory location is not really valid
    return nullptr;
  }
  return ptr;
}

The method checks, on each attempt to allocate memory, whether the newly allocated block would reach into the call stack (+ some safety margin). If so, the pointer is freed again and null is returned.

I tried with this a bit more demanding test, and it seems to work as expected (allocates a bunch of blocks until it fails at around 91k, then restarts)

void ValidateMemoryManager()
{
  const int oneK = 1024;
  const int maxMemToTest = 100; // the arduino due has 96k of memory
  void* ptrs[maxMemToTest];
  int idx = 0;
  int totalAllocsSucceeded = 0;
  while (idx < maxMemToTest)
  {
    void* mem = mallocEx(oneK);
    ptrs[idx] = mem;
    if (mem == nullptr)
    {
      break;
    }
    idx++;
  }

  // Happens in simulation
  if (idx == maxMemToTest)
  {
    idx--;
  }
  
  totalAllocsSucceeded = idx;
  while (idx >= 0)
  {
    free(ptrs[idx]);
    idx--;
  }

   Serial.print("Total usable memory: ");
   Serial.print(totalAllocsSucceeded * oneK, DEC);
   Serial.println();
}