Pages: 1 2 [3] 4   Go Down
Author Topic: malloc(), realloc().. the dark side powerful it is  (Read 9462 times)
0 Members and 1 Guest are viewing this topic.
Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Personally I would prefer if the Arduino administrators/owners (whatever they are called) would roll out 1.1 of the IDE with this fix in it. Since the String library, supplied, uses malloc, and we keep hearing from people that their programs crash when using String, it might solve a few problems. And while they are at it, they could include placement new in new.cpp.
Logged

Lisbon, Portugal
Offline Offline
Full Member
***
Karma: 0
Posts: 152
Bow before me for I am root.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Just for fun, wiring uses avr-libc-1.7.1, libc.a dated from 2011/05/27.

I'll open a bug report for this topic at Arduino's Google Code page.
Logged


Lisbon, Portugal
Offline Offline
Full Member
***
Karma: 0
Posts: 152
Bow before me for I am root.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Bug report #857 open.
Logged


Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Active you have been. smiley

The source is strong in you.

The source in you is strong.
« Last Edit: March 11, 2012, 10:16:52 pm by Nick Gammon » Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Well this is interesting. Adding this test function to the test:

Code:
void stest ()
  {
   String foo = "Hi there";
  }
  

And calling it like this:

Code:
Serial.println ("String test ...");
 showmem();
 stest ();
 showmem ();

I get the results:

Code:
String test ...
0000 1619 1623 : used/free/large
0000 1619 1612 : used/free/large

So a simple usage of a single string has reduced the largest block.

Now with the new library:

Code:
String test ...
0000 1607 1611 : used/free/large
0000 1607 1611 : used/free/large

(Different base figures because one was tested under v0022 and one under 1.0 of the IDE).

I've worked out a reasonably simple way of retrofitting it. The bug seems to be in free, so we'll concentrate on that. I copied this:

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

extern char     __heap_start;
extern char     __heap_end;
#define STACK_POINTER() ((char *)AVR_STACK_POINTER_REG)

extern char    *__brkval; /* first location not yet allocated */
extern struct __freelist *__flp;/* freelist pointer (head of freelist) */
extern size_t   __malloc_margin;/* user-changeable before the first malloc() */
extern char    *__malloc_heap_start;
extern char    *__malloc_heap_end;

char           *__brkval;
struct __freelist *__flp;

void
myfree(void *p)
{
struct __freelist *fp1, *fp2, *fpnew;
char           *cp1, *cp2, *cpnew;
  
/* ISO C says free(NULL) must be a no-op */
if (p == 0)
return;
  
cpnew = p;
cpnew -= sizeof(size_t);
fpnew = (struct __freelist *) cpnew;
fpnew->nx = 0;
  
/*
* Trivial case first: if there's no freelist yet, our entry
* will be the only one on it.  If this is the last entry, we
* can reduce __brkval instead.
*/
if (__flp == 0) {
if ((char *) p + fpnew->sz == __brkval)
__brkval = cpnew;
else
__flp = fpnew;
return;
}
/*
* Now, find the position where our new entry belongs onto the
* freelist.  Try to aggregate the chunk with adjacent chunks
* if possible.
*/
for (fp1 = __flp, fp2 = 0;
    fp1;
    fp2 = fp1, fp1 = fp1->nx) {
if (fp1 < fpnew)
continue;
cp1 = (char *) fp1;
fpnew->nx = fp1;
if ((char *) &(fpnew->nx) + fpnew->sz == cp1) {
/* upper chunk adjacent, assimilate it */
fpnew->sz += fp1->sz + sizeof(size_t);
fpnew->nx = fp1->nx;
}
if (fp2 == 0) {
/* new head of freelist */
__flp = fpnew;
return;
}
break;
}
/*
* Note that we get here either if we hit the "break" above,
* or if we fell off the end of the loop.  The latter means
* we've got a new topmost chunk.  Either way, try aggregating
* with the lower chunk if possible.
*/
fp2->nx = fpnew;
cp2 = (char *) &(fp2->nx);
if (cp2 + fp2->sz == cpnew) {
/* lower junk adjacent, merge */
fp2->sz += fpnew->sz + sizeof(size_t);
fp2->nx = fpnew->nx;
}
/*
* If there's a new topmost chunk, lower __brkval instead.
*/
for (fp1 = __flp, fp2 = 0;
    fp1->nx != 0;
    fp2 = fp1, fp1 = fp1->nx)
    /* advance to entry just before end of list */ ;
cp2 = (char *) &(fp1->nx);
if (cp2 + fp1->sz == __brkval) {
if (fp2 == NULL)
/* Freelist is empty now. */
__flp = NULL;
else
fp2->nx = NULL;
__brkval = cp2 - sizeof(size_t);
}
}

into the tail-end of wiring.c (where else?).

Then since String (and presumably most things, such as Arduino.h) include stdlib.h I edited stdlib.h and added:

Code:
#define free myfree

This redirects String (and other places where you call free) to use myfree, which is now implemented inside wiring.c.

It's a bit of a hack, but this lets you get on with having a fixed memory allocator, until such time as a more proper way of fixing it is released.
« Last Edit: March 11, 2012, 10:17:35 pm by Nick Gammon » Logged

Lisbon, Portugal
Offline Offline
Full Member
***
Karma: 0
Posts: 152
Bow before me for I am root.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Great work Nick, I'll use that workaround in the meanwhile.
Personally I would prefer to see the avr-libc updated rather than hacking on top of it to fix issues that were already corrected at mainstream.
Logged


Smithfield, Rhode Island
Offline Offline
God Member
*****
Karma: 2
Posts: 843
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Interesting, this could explain some memory boundary errors and/or allocation failures I can't find, but only when I send data to a terminal (which i don't need to do in my app). Still, it seems hard to believe that such a serious bug made it this far. Thanks for your work Nick...
 

 
Logged

Smithfield, Rhode Island
Offline Offline
God Member
*****
Karma: 2
Posts: 843
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

It turns out that the existing Arduino tool chain (the compiler, linker and so on, but not including AVRDude) also has a bug that prevents it from properly generating code bigger than 128K bytes, which is a problem for the Mega Arduinos.

It looks like both this memory allocation issue and the flash size issue can be resolved by upgrading the Arduino tool chain to the latest. Instructions on how to do that are here:

http://www.open-electronics.org/arduino-full-memory-upgrade-to-the-last-atmel-toolchain-version/

I have not tried it yet, but its high on my priority list. I'll report back after I try it and run this test.
Logged

Essex, UK
Offline Offline
Full Member
***
Karma: 4
Posts: 150
Arduino rocks
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Nice work everyone, particularly Nick. I upgraded my libc version from 1.6.x to 1.7.x a long time ago when I recompiled avr-gcc up to 4.5.1 to get some other bug fixes and enhancements so yes, on my website you are seeing the results of 1.7.x free().
Logged

Home of the Nokia QVGA TFT LCD hacks: http://andybrown.me.uk

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks, Andy. For my part, thanks very much for porting the STL. I was starting to do it when I heard about your version. You saved me a lot of work and almost certainly did a better job. smiley

I love the STL, admittedly it doesn't get used every day on the Arduino, but that's a bit of a pity. I found recently that the string class uses somewhat less program memory than the String class, so it's a shame it isn't shipped with the system.
Logged

Smithfield, Rhode Island
Offline Offline
God Member
*****
Karma: 2
Posts: 843
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I have not tried it yet, but its high on my priority list. I'll report back after I try it and run this test.

Okay I tried it... Who needs to sleep anyhow? I applied this to Arduino 1.0.

After following the instructions, everything seemed to work. The compiler and linker did their thing and AVRDude uploaded the resulting HEX file with no errors! So far so good. Then I tried to run a simple sketch, and discovered that the sketches can not talk back to my terminal. Hm... I tried again with the original 1.0 and ran the ASCII Table example, which worked fine. Back to the modified version, no joy. Maybe after some sleep things will be better...
Logged

Smithfield, Rhode Island
Offline Offline
God Member
*****
Karma: 2
Posts: 843
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Nice work everyone, particularly Nick. I upgraded my libc version from 1.6.x to 1.7.x a long time ago when I recompiled avr-gcc up to 4.5.1 to get some other bug fixes and enhancements so yes, on my website you are seeing the results of 1.7.x free().

Andy, thanks for confirming that! Your blog rocks, by the way!

Logged

Smithfield, Rhode Island
Offline Offline
God Member
*****
Karma: 2
Posts: 843
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Okay, the new tool chain works with my Uno board, just not with my 1284P board. The differences are primarily, the boot loader and of course the CPU.

More to come...
 
Logged

Offline Offline
Full Member
***
Karma: 0
Posts: 179
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Code:
#define free myfree

I'm impressed, Nick. Less so with Arduino.  This product is far too mature (old) to have that sort of thing still in it. Refusing to incorporate what appears to be a thoroughly worked out fix does not inspire much confidence for anything more than tinkering.  smiley-roll

I'll have a closer look a getting a Tweeny.  

Code:
Serial.println ("String test ...");
 showmem();
 stest ();
 showmem ();

Is that your own util fn?  I dont find that in /usr/share/arduino*

« Last Edit: August 08, 2012, 10:41:31 am by ardnut » Logged

Global Moderator
Offline Offline
Brattain Member
*****
Karma: 452
Posts: 18694
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

See reply #18 which I'll reproduce here:



http://andybrown.me.uk/ws/2011/01/01/debugging-avr-dynamic-memory-allocation/


Andy Brown wrote a library that debugs memory allocation in detail, by walking the free list.
Logged

Pages: 1 2 [3] 4   Go Up
Jump to: