malloc behaviour on an embedded system

Question

I'm currently working on an embedded project (STM32F103RB, CooCox CoIDE v.1.7.6 with arm-none-eabi-gcc 4.8 2013q4) and I'm trying to understand how malloc() behaves on plain C when the RAM is full.

My STM32 has 20kB = 0x5000Bytes of RAM, 0x200 are used for the stack.

#include <stdlib.h>
#include "stm32f10x.h"

struct list_el {
   char weight[1024];
};

typedef struct list_el item;

int main(void)
{
    item * curr;

    // allocate until RAM is full
    do {
        curr = (item *)malloc(sizeof(item));
    } while (curr != NULL);

    // I know, free() is missing. Program is supposed to crash

    return 0;
}

I would expect malloc() to return NULL as soon as the heap is too small for allocating:

0x5000 (RAM) - 0x83C (bss) - 0x200 (stack) = 0x45C4 (heap)

So when executing the malloc() for the 18th time. One item is 1024=0x400 Bytes large.

But instead the uC calls the HardFault_Handler(void) after the 18th time (not even the MemManager_Handler(void))

Does anybody have an advice how to forecast a malloc() failure - since waiting for a NULL return doesn't seem to work.

Thank you.

Answer 1

It does not look like malloc is doing any checks at all. The fault that you get comes from hardware detecting a write to an invalid address, which is probably coming from malloc itself.

When malloc allocates memory, it takes a chunk from its internal pool, and returns it to you. However, it needs to store some information for the free function to be able to complete deallocation. Usually, that's the actual length of the chunk. In order to save that information, malloc takes a few bytes from the beginning of the chunk itself, writes the info there, and returns you the address past the spot where it has written its own information.

For example, let's say you asked for a 10-byte chunk. malloc would grab an available 16-byte chunk, say, at addresses 0x3200..0x320F, write the length (i.e. 16) into bytes 1 and 2, and return 0x3202 back to you. Now your program can use ten bytes from 0x3202 to 0x320B. The other four bytes are available, too - if you call realloc and ask for 14 bytes, there would be no reallocation.

The crucial point comes when malloc writes the length into the chunk of memory that it is about to return to you: the address to which it writes needs to be valid. It appears that after the 18-th iteration the address of the next chunk is negative (which translates to a very large positive) so CPU traps the write, and triggers the hard fault.

In situations when the heap and the stack grow toward each other there is no reliable way to detect an out of memory while letting you use every last byte of memory, which is often a very desirable thing. malloc cannot predict how much stack you are going to use after the allocation, so it does not even try. That is why the byte counting in most cases is on you.

In general, on embedded hardware when the space is limited to a few dozen kilobytes, you avoid malloc calls in "arbitrary" places. Instead, you pre-allocate all your memory upfront using some pre-calculated limits, and parcel it out to structures that need it, and never call malloc again.

Answer 2

Your program most likely crashes because of an illegal memory access, which is almost always an indirect (subsequent) result of a legal memory access, but one that you did not intend to perform.

For example (which is also my guess as to what's happening on your system):

Your heap most likely begins right after the stack. Now, suppose you have a stack-overflow in main. Then one of the operations that you perform in main, which is naturally a legal operation as far as you're concerned, overrides the beginning of the heap with some "junk" data.

As a subsequent result, the next time that you attempt to allocate memory from the heap, the pointer to the next available chunk of memory is no longer valid, eventually leading to a memory access violation.

So to begin with, I strongly recommend that you increase the stack size from 0x200 bytes to 0x400 bytes. This is typically defined within the linker-command file, or through the IDE, in the project's linker settings.

If your project is on IAR, then you can change it in the icf file:

define symbol __ICFEDIT_size_cstack__ = 0x400

Other than that, I suggest that you add code in your HardFault_Handler, in order to reconstruct the call-stack and register values prior to the crash. This might allow you to trace the runtime error and find out exactly where it happened.

In file 'startup_stm32f03xx.s', make sure that you have the following piece of code:

EXTERN  HardFault_Handler_C        ; this declaration is probably missing

__tx_vectors                       ; this declaration is probably there
    DCD     HardFault_Handler

Then, in the same file, add the following interrupt handler (where all other handlers are located):

    PUBWEAK HardFault_Handler
    SECTION .text:CODE:REORDER(1)
HardFault_Handler
    TST LR, #4
    ITE EQ
    MRSEQ R0, MSP
    MRSNE R0, PSP
    B HardFault_Handler_C

Then, in file 'stm32f03xx.c', add the following ISR:

void HardFault_Handler_C(unsigned int* hardfault_args)
{
    printf("R0    = 0x%.8X\r\n",hardfault_args[0]);         
    printf("R1    = 0x%.8X\r\n",hardfault_args[1]);         
    printf("R2    = 0x%.8X\r\n",hardfault_args[2]);         
    printf("R3    = 0x%.8X\r\n",hardfault_args[3]);         
    printf("R12   = 0x%.8X\r\n",hardfault_args[4]);         
    printf("LR    = 0x%.8X\r\n",hardfault_args[5]);         
    printf("PC    = 0x%.8X\r\n",hardfault_args[6]);         
    printf("PSR   = 0x%.8X\r\n",hardfault_args[7]);         
    printf("BFAR  = 0x%.8X\r\n",*(unsigned int*)0xE000ED38);
    printf("CFSR  = 0x%.8X\r\n",*(unsigned int*)0xE000ED28);
    printf("HFSR  = 0x%.8X\r\n",*(unsigned int*)0xE000ED2C);
    printf("DFSR  = 0x%.8X\r\n",*(unsigned int*)0xE000ED30);
    printf("AFSR  = 0x%.8X\r\n",*(unsigned int*)0xE000ED3C);
    printf("SHCSR = 0x%.8X\r\n",SCB->SHCSR);                
    while (1);
}

If you can't use printf at the point in the execution when this specific Hard-Fault interrupt occurs, then save all the above data in a global buffer instead, so you can view it after reaching the while (1).

Then, refer to the 'Cortex-M Fault Exceptions and Registers' section at http://www.keil.com/appnotes/files/apnt209.pdf in order to understand the problem, or publish the output here if you want further assistance.

UPDATE:

In addition to all of the above, make sure that the base address of the heap is defined correctly. It is possibly hard-coded within the project settings (typically right after the data-section and the stack). But it can also be determined during runtime, at the initialization phase of your program. In general, you need to check the base addresses of the data-section and the stack of your program (in the map file created after building the project), and make sure that the heap does not overlap either one of them.

I once had a case where the base address of the heap was set to a constant address, which was fine to begin with. But then I gradually increased the size of the data-section, by adding global variables to the program. The stack was located right after the data-section, and it "moved forward" as the data-section grew larger, so there were no problems with either one of them. But eventually, the heap was allocated "on top of" part of the stack. So at some point, heap-operations began to override variables on the stack, and stack-operations began to override the contents of the heap.

Answer 3

The arm-none-eabi-* toolchain distribution includes the newlib C library. When newlib is configured for an embedded system, then the user program must provide an _sbrk() function for it to work properly.

malloc() relies solely on _sbrk() to figure out where the heap memory starts, and where it ends. The very first call to _sbrk() returns the start of the heap, and subsequent calls should return -1 if the required amount of memory is not available, then malloc() would in turn return NULL to the application. Your _sbrk() looks broken, because it apparently lets you allocate more memory than there is available. You should be able to fix it so that it returns -1 before the heap is expected to collide with the stack.

Answer 4

Using standard c malloc it's very hard to distinguish and malloc is seems buggy from my view. So you can manage memory by implementing some custom malloc using your RAM address.

I am not sure may this help you but i have done some custom malloc in my controller related project it's as follows

#define LENGTH_36_NUM   (44)
#define LENGTH_52_NUM   (26)
#define LENGTH_64_NUM   (4)
#define LENGTH_128_NUM  (5)
#define LENGTH_132_NUM  (8)
#define LENGTH_256_NUM  (8)
#define LENGTH_512_NUM  (18)    
#define LENGTH_640_NUM  (8) 
#define LENGTH_1536_NUM (6) 

#define CUS_MEM_USED        (1)
#define CUS_MEM_NO_USED     (0)

#define CALC_CNT    (0)
#define CALC_MAX    (1)

#define __Ram_Loc__         (0x20000000) ///This is my RAM address
#define __TOP_Ram_Loc__     (0x20000000 + 0x8000 -0x10) //Total 32K RAM and last 16 bytes reserved for some data storage

typedef struct _CUS_MEM_BLOCK_S {
    char used;
    int block_size;
    char *ptr;
    char *next;
} cus_mem_block_s;

static struct _MEM_INFO_TBL_S {
    int block_size;
    int num_max;
    cus_mem_block_s *wm_head;
    int calc[2];
} memInfoTbl[] = {

 {36,  LENGTH_36_NUM  , 0, {0,0} },
 {52,  LENGTH_52_NUM  , 0, {0,0} },
 {64,  LENGTH_64_NUM  , 0, {0,0} },
 {128, LENGTH_128_NUM , 0, {0,0} },
 {132, LENGTH_132_NUM , 0, {0,0} },
 {256, LENGTH_256_NUM , 0, {0,0} },
 {512, LENGTH_512_NUM , 0, {0,0} },
 {640, LENGTH_640_NUM , 0, {0,0} },
 {1536,LENGTH_1536_NUM, 0, {0,0} },
};
#define MEM_TBL_MAX     (sizeof(memInfoTbl)/sizeof(struct _MEM_INFO_TBL_S))

BOOL MemHeapHasBeenInitialised = FALSE;

This basically macro defines for RAM address and have manually chose more block number for block size which frequently require to allocate,Like 36 bytes required me more so i take more number for it.

This is init function for mem init

void cus_MemInit(void)
{
    int i,j;
    cus_mem_block_s *head=NULL;
    unsigned int addr;

    addr = __Ram_Loc__;

    for(i=0; i<MEM_TBL_MAX; i++) 
    {
        head = (char *)addr;
        memInfoTbl[i].wm_head = head;
        for(j=0;j<memInfoTbl[i].num_max; j++)
        {
            head->used =CUS_MEM_NO_USED;
            head->block_size = memInfoTbl[i].block_size;
            head->ptr = (char *)(addr + sizeof(cus_mem_block_s));
            addr += (memInfoTbl[i].block_size + sizeof(cus_mem_block_s));
            head->next =(char *)addr;
            head = head->next;
            if(head > __TOP_Ram_Loc__) 
            {
                printf("%s:error.\n",__FUNCTION__);
                return;
            }
        }
    }
    head->ptr = 0;
    head->block_size = 0;
    head->next = __Ram_Loc__;

    MemHeapHasBeenInitialised=TRUE;
}

This one for allocation

void* CUS_Malloc( int wantedSize )
{
    void *pwtReturn = NULL;
    int i;
    cus_mem_block_s *head;

    if(MemHeapHasBeenInitialised == FALSE) 
            goto done_exit;

    for(i=0; i<MEM_TBL_MAX; i++)
    {
        if(wantedSize <= memInfoTbl[i].block_size)
        {
            head = memInfoTbl[i].wm_head;
            while(head->ptr)
            {
                if(head->used == CUS_MEM_NO_USED)
                {
                    head->used = CUS_MEM_USED;
                    pwtReturn = head->ptr;
                    goto done;
                }
                head = head->next;
            }
            goto done;

        }
    }
 done:


    if(pwtReturn)
    {
        for(i=0; i<MEM_TBL_MAX; i++)
        {
            if(memInfoTbl[i].block_size == head->block_size)
            {

                memInfoTbl[i].calc[CALC_CNT]++;
                if(memInfoTbl[i].calc[CALC_CNT] > memInfoTbl[i].calc[CALC_MAX] )
                    memInfoTbl[i].calc[CALC_MAX]=memInfoTbl[i].calc[CALC_CNT];
                break;
            }
        }
    }
  done_exit:
    return pwtReturn;
}

This one for free

void CUS_Free(void *pm)
{
    cus_mem_block_s *head;
    char fault=0;


    if( (pm == NULL) || (MemHeapHasBeenInitialised == FALSE) )
        goto done;
    if( (pm < __RamAHB32__) && (pm > __TOP_Ram_Loc__) )
    {
        printf("%s:over memory range\n",__FUNCTION__);
        goto done;
    }

    head = pm-sizeof(cus_mem_block_s);


    if(head->used)
        head->used = CUS_MEM_NO_USED;
    else
    {
        printf("%s:free error\n",__FUNCTION__);
        fault=1;
    }


    if(fault)
        goto done;
    int i;
    for(i=0;i<MEM_TBL_MAX;i++)
    {
        if(memInfoTbl[i].block_size == head->block_size)
        {
            memInfoTbl[i].calc[CALC_CNT]--;
            goto done;
        }
    }
 done:;

}

After all you can use above function like

void *mem=NULL;
mem=CUS_Malloc(wantedsize);

Then can also watch your used memory as follows

void CUS_MemShow(void)
{
    int i;
    int block_size;
    int block_cnt[MEM_TBL_MAX];
    int usedSize=0, totalSize=0;
    cus_mem_block_s *head;

    if(MemHeapHasBeenInitialised == FALSE)
            return;

    memset(block_cnt, 0, sizeof(block_cnt));

    head = memInfoTbl[0].wm_head;
    i=0;
    block_size = head->block_size;
    vTaskSuspendAll();
    while( head->ptr !=0)
    {
        if(head->used == CUS_MEM_USED )
        {
            block_cnt[i]++;
            usedSize +=head->block_size;
        }
        usedSize += sizeof(cus_mem_block_s);

        totalSize += (head->block_size+ sizeof(cus_mem_block_s));

        /* change next memory block */  
        head = head->next;
        if( block_size != head->block_size)
        {
            block_size = head->block_size;
            i++;
        }
    }
    xTaskResumeAll();

    usedSize += sizeof(cus_mem_block_s);
    totalSize+= sizeof(cus_mem_block_s);

    dprintf("----Memory Information----\n");

    for(i=0; i<MEM_TBL_MAX; i++) {
        printf("block %d used=%d/%d (max %d)\n",
                    memInfoTbl[i].block_size, block_cnt[i], 
                    memInfoTbl[i].num_max,
                    memInfoTbl[i].calc[CALC_MAX]);
    }

    printf("used memory=%d\n",usedSize);
    printf("free memory=%d\n",totalSize-usedSize);
    printf("total memory=%d\n",totalSize);
    printf("--------------------------\n");
}

In general have pre-calculated the memory first then give as i have.

Answer 5

Here you can find how I could "force" malloc() to return NULL, if the heap is too small for allocating based on berendi's previous answer. I estimated the maximum amount of STACK and based on this I could calculate the address where the stack can start in worst case.

#define STACK_END_ADDRESS       0x20020000
#define STACK_MAX_SIZE              0x0400
#define STACK_START_ADDRESS   (STACK_END_ADDRESS - STACK_MAX_SIZE)

void * _sbrk_r(
   struct _reent *_s_r,
   ptrdiff_t nbytes)
{
   char  *base;     /*  errno should be set to  ENOMEM on error */

   if (!heap_ptr) { /*  Initialize if first time through.       */
      heap_ptr = end;
   }
   base = heap_ptr; /*  Point to end of heap.           */
   #ifndef STACK_START_ADDRESS
      heap_ptr += nbytes;   /*  Increase heap.              */
      return base;      /*  Return pointer to start of new heap area.   */
   #else
      /* End of heap mustn't exceed beginning of stack! */        
      if (heap_ptr <= (char *) (STACK_START_ADDRESS - nbytes) ) {  
         heap_ptr += nbytes;    /*  Increase heap.              */
         return base;       /*  Return pointer to start of new heap area.   */
      } else {
         return (void *) -1;         /*   Return -1 means that memory run out  */
      }
   #endif // STACK_START_ADDRESS
}