Is it a dynamic memory bug?

Projects Programming
1

Hey guys,
I'm going crazy for a week.
My project uses dynamic data, especially two-dimensional dynamic arrays I need.
The problem is that for a few elements works well, but sometimes when I try to add more items, it fails.
I cleaned up and simplified the code to be well understood.
I think the problem is "addSubItem", but I fail to see why.

Is it a bug? I'm a bug? XD

I'm using Arduino 0022 and MEGA2560

THX!! Greetings from Spain

struct typeSubItem {
  int subitem;
};

struct typeItem {
  int item;
  typeSubItem** arraySubItem;
  int arraySubItemSize;
};

typeItem** arrayItem = NULL;
int arrayItemSize = 0;

//=======================================================================
void addItem(int item) {
   arrayItem = (typeItem**) realloc(arrayItem, (arrayItemSize + 1) * sizeof(typeItem*)); 
   arrayItem[arrayItemSize] = (typeItem*) malloc(sizeof(typeItem)); 
   
   arrayItem[arrayItemSize]->item = item;
   arrayItem[arrayItemSize]->arraySubItem = NULL;
   arrayItem[arrayItemSize]->arraySubItemSize = 0;
   arrayItemSize++;
}
//=======================================================================
void addSubItem(int pos, int subitem) {
  arrayItem[pos]->arraySubItem = (typeSubItem**) realloc(arrayItem[pos]->arraySubItem, (arrayItem[pos]->arraySubItemSize + 1) * sizeof(typeSubItem*)); 
  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize] = (typeSubItem*) malloc(sizeof(typeSubItem)); 
 
  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize]->subitem = subitem;
  arrayItem[pos]->arraySubItemSize++; 
}
//=======================================================================
void setup() {  
  
  int items = 10;      // !!!!!!!!!! For (30, 10) it fails, for (10, 10) is OK
  int subitems = 10;
  
  Serial.begin(9600); 
      
  Serial.println("Processing..."); 
  for (int i = 0; i < items; i++) {
    Serial.println(i);
    addItem(i);
    delay(20);
    for (int j = 0; j < subitems; j++) {
      Serial.print("\t"); Serial.println(j);
      addSubItem(i, j);
    }
  }
  Serial.println("Done.");
}
//=======================================================================
void loop() {}
2

Probably. Using dynamic memory is a bad idea on embedded platforms with limited RAM, such as the Arduino. The only exception is that malloc() or new can be used from within setup() to allocate objects that can't easily be declared statically.

I suggest re-coding your sketch to use fixed-size arrays. Then check that the total amount of RAM needed still leaves enough for the stack (total available RAM is only 2k on the atmega328p). Unfortuately, the Arduino IDE is extremely unhelpful in this respect.

Remember that string literals also occupy RAM unless you put them in PROGMEM.

3

Thanks DC42, but this is not a problem of overflow, malloc fails with only a few bytes. I have mega2560 with 7KB free! It's more than I need. Unfortunately I need to use dynamic memory because the data comes externally and are of variable size.

The question is: is reliable malloc () or my code is wrong.

4

With all those malloc and realloc calls, I think you are fragmenting the memory, causing it to be exhausted much earluier than you expect. Like I said, dynamic memory is a bad idea in embedded systems. If you really must do it, allocate the maximum amount you need in one go, don't keep changing your mind about how much you want and making realloc calls.

5

pieldetoro:
Is it a bug?

I seem to recall some thread in the last couple of months that had a patch to the dynamic memory routines to fix a bug where the memory was not necessarily released properly. I don't remember where, but I would search for that.

Also you possibly are fragmenting your memory, something that will be hard to fix.

Further research shows that whilst those lines are worth pursuing, you actually do have a bug. :slight_smile:

Modifying your program to add debugging displays:

struct typeSubItem {
  int subitem;
};

struct typeItem {
  int item;
  typeSubItem** arraySubItem;
  int arraySubItemSize;
};

typeItem** arrayItem = NULL;
int arrayItemSize = 0;

//=======================================================================
void addItem(int item) {
  arrayItem = (typeItem**) realloc(arrayItem, (arrayItemSize + 1) * sizeof(typeItem*)); 
  if (!arrayItem)
    Serial.println (__PRETTY_FUNCTION__);
  else
    Serial.println ((int) arrayItem, HEX);
  arrayItem[arrayItemSize] = (typeItem*) malloc(sizeof(typeItem)); 
  if (!arrayItem[arrayItemSize])
    Serial.println (__PRETTY_FUNCTION__);
  else
    Serial.println ((int) arrayItem[arrayItemSize], HEX);

  arrayItem[arrayItemSize]->item = item;
  arrayItem[arrayItemSize]->arraySubItem = NULL;
  arrayItem[arrayItemSize]->arraySubItemSize = 0;
  arrayItemSize++;
}
//=======================================================================
void addSubItem(int pos, int subitem) {
  arrayItem[pos]->arraySubItem = (typeSubItem**) realloc(arrayItem[pos]->arraySubItem, (arrayItem[pos]->arraySubItemSize + 1) * sizeof(typeSubItem*)); 
  if (!arrayItem[pos]->arraySubItem)
    Serial.println (__PRETTY_FUNCTION__);
  else
    Serial.println ((int) arrayItem[pos]->arraySubItem, HEX);
  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize] = (typeSubItem*) malloc(sizeof(typeSubItem));  
  if (!arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize])
    Serial.println (__PRETTY_FUNCTION__);
  else
    Serial.println ((int) arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize], HEX);

  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize]->subitem = subitem;
  arrayItem[pos]->arraySubItemSize++; 
}
//=======================================================================
void setup() {  

  int items = 30;      // !!!!!!!!!! For (30, 10) it fails, for (10, 10) is OK
  int subitems = 10;

  Serial.begin(115200); 

  Serial.println("Processing..."); 
  for (int i = 0; i < items; i++) {
    Serial.print("Free Memory:  ");
    Serial.print(memoryFree()); 
    Serial.println();  

    Serial.print ("---> i = ");
    Serial.println(i);
    addItem(i);
    delay(20);
    for (int j = 0; j < subitems; j++) {
      Serial.print ("-----> j = ");
      Serial.println(j);
      addSubItem(i, j);
    }
  }
  Serial.println("Done.");
}
//=======================================================================
void loop() {
}



extern unsigned long __bss_end;
extern void *__brkval;

int memoryFree()
{
  //  long myValue;
  int freeValue;
  freeValue = 0;

  if ((unsigned long)__brkval == 0)
  { 
    freeValue = ((unsigned long)&freeValue) - ((unsigned long)&__bss_end);
    //       Serial.println("here and there");
  }
  else
  { 
    freeValue = ((unsigned long)&freeValue) - ((unsigned long)__brkval);
    //      Serial.println("here  2");
  }

  return freeValue;

}//end memoryFree()

I found (near the end of the debugging) this:

Free Memory:  6221
---> i = 16
957
9A3
-----> j = 0
9AB
9AF
-----> j = 1
9B3
9AB
-----> j = 2
9B3
9BB
-----> j = 3
9BF
9B7
-----> j = 4
9BF
9B3
-----> j = 5
9BF
9CD
-----> j = 6
9D1
9C9
-----> j = 7
9D1
9C5
-----> j = 8
9D1
9BF
-----> j = 9
9D1
9E7
Free Memory:  6149
---> i = 17
957
975
-----> j = 0

Now clearly there is plenty of memory left (6149 bytes). But the problem is your design.

You have pointers to pointers, right? And those (arrays of) pointers are being reallocated? That invalidates the pointer-to-pointer concept. It works for a while, because realloc doesn't have any room to reallocate, so it just does a malloc. Therefore everything is fresh and new. But once it reallocates due to a big enough gap, then the pointers which used to point to X, now find X has moved.

If I may suggest, if the design warrants all these arrays of arrays, use the STL (Standard Template Library). That will manage all that for you. The overhead should be acceptable on the Mega2560.

6

Thank you very much for yousr comments, you have helped me a lot.
I solved the problem allocating memory for the entire array instead of using "realloc()".

However there is a bug when memory is freed. I found this post which explains it:
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294392281

Memory free bug:

BEGIN free:7480
AFTER ADD free:878
AFTER CLEAR free:878
Done.

After apply patch code "fix28135_malloc_bug()"

BEGIN free:7480
AFTER ADD free:878
AFTER CLEAR free:7480
Done.

The new modified code works fine:

#include "MemoryFree.h"

struct typeSubItem {
  int subitem;
};

struct typeItem {
  int item;
  typeSubItem** arraySubItem;
  int arraySubItemSize;
};

typeItem** arrayItem = NULL;
int arrayItemSize = 0;

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

extern struct __freelist *__flp;
extern uint8_t* __brkval;
//=======================================================================
void fix28135_malloc_bug()
 {
   for (__freelist *fp = __flp, *lfp = 0; fp; fp = fp->nx)
   {
     if (((uint8_t*)fp + fp->sz + 2) == __brkval)
     {
       __brkval = (uint8_t*)fp;
       if (lfp)
         lfp->nx = 0;
       else
         __flp = 0;
       break;
     }
     lfp = fp;
   }
 }
//=======================================================================
void declareItems(int numitems) {
  arrayItem = (typeItem**) malloc(numitems * sizeof(typeItem*)); 
}  
//=======================================================================
void declareSubItems(int pos, int numsubitems) {
  arrayItem[pos]->arraySubItem = (typeSubItem**) malloc(numsubitems * sizeof(typeSubItem*)); 
}
//=======================================================================
void addItem(int item) {
   arrayItem[arrayItemSize] = (typeItem*) malloc(sizeof(typeItem)); 
   
   arrayItem[arrayItemSize]->item = item;
   arrayItem[arrayItemSize]->arraySubItem = NULL;
   arrayItem[arrayItemSize]->arraySubItemSize = 0;
   arrayItemSize++;
}
//=======================================================================
void addSubItem(int pos, int subitem) {
  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize] = (typeSubItem*) malloc(sizeof(typeSubItem)); 
 
  arrayItem[pos]->arraySubItem[arrayItem[pos]->arraySubItemSize]->subitem = subitem;
  arrayItem[pos]->arraySubItemSize++; 
}
//=======================================================================
void addData(int items, int subitems) {
  
  declareItems(items);
  for (int i = 0; i < items; i++) {
    addItem(i);
    declareSubItems(i, subitems);
    for (int j = 0; j < subitems; j++) {
      addSubItem(i, j);
    }
  }  
}
//=======================================================================
void clearData() {
  
 for (int i = 0; i < arrayItemSize; i++) {
   
   for (int j = 0; j < arrayItem[i]->arraySubItemSize; j++) {
     free(arrayItem[i]->arraySubItem[j]);
     fix28135_malloc_bug();
   }
   free(arrayItem[i]->arraySubItem);
   fix28135_malloc_bug();
   free(arrayItem[i]);
   fix28135_malloc_bug();
 } 
 free(arrayItem);
 arrayItemSize = 0;
 fix28135_malloc_bug();
}
//=======================================================================
void setup() {  
  
  int items = 50;      
  int subitems = 20;
  
  Serial.begin(9600); 
 
  Serial.print("BEGIN free:"); Serial.println(freeMemory());
  addData(items, subitems);
  Serial.print("AFTER ADD free:"); Serial.println(freeMemory());
  clearData();
  Serial.print("AFTER CLEAR free:"); Serial.println(freeMemory());
  
  Serial.println("Done.");
}
//=======================================================================
void loop() {}
7

Oh yes, that is the one I meant, the "fix28135_malloc_bug()" post. Somehow I didn't remember the post name. :wink:

Glad I could help.