Pages: 1 [2] 3 4   Go Down
Author Topic: malloc(), realloc().. the dark side powerful it is  (Read 9368 times)
0 Members and 1 Guest are viewing this topic.
United kingdom
Offline Offline
Full Member
***
Karma: 0
Posts: 101
just think how much free time you would have if everything worked first time!!
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I'm not sure why, I always thought it was something odd about Microsofts C compiler on the PC...but I've since encountered the same problem with gcc on Linux and also with C compilers on QNX.
Logged

Kind Regards,
Sy

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

But what's the reason behind the 8K block not the be freed as a continuous block, is it due to the malloc's internals ? So if it's possible to write a wrapper around malloc() to better handle memory, couldn't this be incorporated into avr-libc malloc() itself ?

Well I don't know that he is right. Certainly fragmentation can occur depending on the order of allocating/freeing. But in the given example? Looking at the source for avr-libc 1.7.1 which I seem to have downloaded at some stage, I see these comments in free():

Code:
        /*
* 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.
*/

So if you allocate 8K and then free it, you should be back to no freelist.

Then:

Code:
/*
* Now, find the position where our new entry belongs onto the
* freelist.  Try to aggregate the chunk with adjacent chunks
* if possible.
*/

Then it tries to merge the current freed block with earlier ones.
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

Nick, how could this be tested under the current arduino's avr-libc ?
Logged


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

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

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 link ! I've adapted the sketch to compile under arduino my results are:
Code:
allocating
0000 1584 1588 : used/free/large
0022 1562 1566 : used/free/large
0044 1540 1544 : used/free/large
0066 1518 1522 : used/free/large
0088 1496 1500 : used/free/large
0110 1474 1478 : used/free/large
0132 1452 1456 : used/free/large
0154 1430 1434 : used/free/large
0176 1408 1412 : used/free/large
0198 1386 1390 : used/free/large
0220 1364 1368 : used/free/large
0242 1342 1346 : used/free/large
0264 1320 1324 : used/free/large
0286 1298 1302 : used/free/large
0308 1276 1280 : used/free/large
0330 1254 1258 : used/free/large
0352 1232 1236 : used/free/large
0374 1210 1214 : used/free/large
0396 1188 1192 : used/free/large
0418 1166 1170 : used/free/large
0440 1144 1148 : used/free/large
freeing
0418 1166 1148 : used/free/large
0396 1188 1148 : used/free/large
0374 1210 1148 : used/free/large
0352 1232 1148 : used/free/large
0330 1254 1148 : used/free/large
0308 1276 1148 : used/free/large
0286 1298 1148 : used/free/large
0264 1320 1148 : used/free/large
0242 1342 1148 : used/free/large
0220 1364 1148 : used/free/large
0198 1386 1148 : used/free/large
0176 1408 1148 : used/free/large
0154 1430 1148 : used/free/large
0132 1452 1148 : used/free/large
0110 1474 1148 : used/free/large
0088 1496 1148 : used/free/large
0066 1518 1148 : used/free/large
0044 1540 1148 : used/free/large
0022 1562 1148 : used/free/large
0000 1584 1148 : used/free/large
allocating
0000 1584 1148 : used/free/large
0022 1562 1148 : used/free/large
0044 1540 1148 : used/free/large
0066 1518 1148 : used/free/large
0088 1496 1148 : used/free/large
0110 1474 1148 : used/free/large
0132 1452 1148 : used/free/large
0154 1430 1148 : used/free/large
0176 1408 1148 : used/free/large
0198 1386 1148 : used/free/large
0220 1364 1148 : used/free/large
0242 1342 1148 : used/free/large
0264 1320 1148 : used/free/large
0286 1298 1148 : used/free/large
0308 1276 1148 : used/free/large
0330 1254 1148 : used/free/large
0352 1232 1148 : used/free/large
0374 1210 1148 : used/free/large
0396 1188 1148 : used/free/large
0418 1166 1148 : used/free/large
0440 1144 1148 : used/free/large
freeing
0418 1166 1148 : used/free/large
0396 1188 1148 : used/free/large
0374 1210 1148 : used/free/large
0352 1232 1148 : used/free/large
0330 1254 1148 : used/free/large
0308 1276 1148 : used/free/large
0286 1298 1148 : used/free/large
0264 1320 1148 : used/free/large
0242 1342 1148 : used/free/large
0220 1364 1148 : used/free/large
0198 1386 1148 : used/free/large
0176 1408 1148 : used/free/large
0154 1430 1148 : used/free/large
0132 1452 1148 : used/free/large
0110 1474 1148 : used/free/large
0088 1496 1148 : used/free/large
0066 1518 1148 : used/free/large
0044 1540 1148 : used/free/large
0022 1562 1148 : used/free/large
0000 1584 1148 : used/free/large

Shouldn't I see the large block at the end be the same size as at the beginning ?
Logged


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

Confirmed here. On Andy's page it looks OK.

Looks like he has a fixed library, huh?

<prod> Message to more senior guys  .... bug in memory allocation! Alert! How about releasing a fixed library? This happens on both 0022 and 1.0 of the IDE.
Logged

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

Actually, looking more closely, the test crashes the processor (that is, it doesn't complete it) on IDE 1.0.

On version 0022 it completes, like this:

Code:
0000 1594 1598 : used/free/large
0022 1572 1576 : used/free/large
...
0418 1176 1180 : used/free/large
0440 1154 1158 : used/free/large
freeing
0418 1176 1158 : used/free/large
0396 1198 1158 : used/free/large
...
0022 1572 1158 : used/free/large
0000 1594 1158 : used/free/large
allocating
0000 1594 1158 : used/free/large
0022 1572 1158 : used/free/large
...
0418 1176 1158 : used/free/large
0440 1154 1158 : used/free/large
freeing
0418 1176 1158 : used/free/large
0396 1198 1158 : used/free/large
...
0022 1572 1158 : used/free/large
0000 1594 1158 : used/free/large

The last figure(s) should be the same as the first, but isn't.

Oh, and it shouldn't crash.
Logged

Left Coast, CA (USA)
Offline Offline
Brattain Member
*****
Karma: 331
Posts: 16513
Measurement changes behavior
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Actually, looking more closely, the test crashes the processor (that is, it doesn't complete it) on IDE 1.0.

On version 0022 it completes, like this:

Code:
0000 1594 1598 : used/free/large
0022 1572 1576 : used/free/large
...
0418 1176 1180 : used/free/large
0440 1154 1158 : used/free/large
freeing
0418 1176 1158 : used/free/large
0396 1198 1158 : used/free/large
...
0022 1572 1158 : used/free/large
0000 1594 1158 : used/free/large
allocating
0000 1594 1158 : used/free/large
0022 1572 1158 : used/free/large
...
0418 1176 1158 : used/free/large
0440 1154 1158 : used/free/large
freeing
0418 1176 1158 : used/free/large
0396 1198 1158 : used/free/large
...
0022 1572 1158 : used/free/large
0000 1594 1158 : used/free/large

The last figure(s) should be the same as the first, but isn't.

Oh, and it shouldn't crash.

Nick, come back to the light. Fix it with hardware I say.

Lefty
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

On my UNO with IDE 1.0 it finishes OK without crashing.
« Last Edit: March 11, 2012, 06:14:30 pm by fuh » 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

Tested under AVR Studio using WinAVR-20100110 (avr-libc 1.6.7) and the same output happens, the largest block is not grown at the end. Tested with native libc from Atmel (using AVR studio) and the output is correct. Maybe this is the bug fixed on avr-libc 1.7 ?

Code:
allocating
0000 1476 1476 : used/free/large
0022 1454 1454 : used/free/large
0044 1432 1432 : used/free/large
0066 1410 1410 : used/free/large
0088 1388 1388 : used/free/large
0110 1366 1366 : used/free/large
0132 1344 1344 : used/free/large
0154 1322 1322 : used/free/large
0176 1300 1300 : used/free/large
0198 1278 1278 : used/free/large
0220 1256 1256 : used/free/large
0242 1234 1234 : used/free/large
0264 1212 1212 : used/free/large
0286 1190 1190 : used/free/large
0308 1168 1168 : used/free/large
0330 1146 1146 : used/free/large
0352 1124 1124 : used/free/large
0374 1102 1102 : used/free/large
0396 1080 1080 : used/free/large
0418 1058 1058 : used/free/large
0440 1036 1036 : used/free/large
freeing
0418 1058 1036 : used/free/large
0396 1080 1036 : used/free/large
0374 1102 1036 : used/free/large
0352 1124 1036 : used/free/large
0330 1146 1036 : used/free/large
0308 1168 1036 : used/free/large
0286 1190 1036 : used/free/large
0264 1212 1036 : used/free/large
0242 1234 1036 : used/free/large
0220 1256 1036 : used/free/large
0198 1278 1036 : used/free/large
0176 1300 1036 : used/free/large
0154 1322 1036 : used/free/large
0132 1344 1036 : used/free/large
0110 1366 1036 : used/free/large
0088 1388 1036 : used/free/large
0066 1410 1036 : used/free/large
0044 1432 1036 : used/free/large
0022 1454 1036 : used/free/large
0000 1476 1476 : used/free/large
allocating
0000 1476 1476 : used/free/large
0022 1454 1454 : used/free/large
0044 1432 1432 : used/free/large
0066 1410 1410 : used/free/large
0088 1388 1388 : used/free/large
0110 1366 1366 : used/free/large
0132 1344 1344 : used/free/large
0154 1322 1322 : used/free/large
0176 1300 1300 : used/free/large
0198 1278 1278 : used/free/large
0220 1256 1256 : used/free/large
0242 1234 1234 : used/free/large
0264 1212 1212 : used/free/large
0286 1190 1190 : used/free/large
0308 1168 1168 : used/free/large
0330 1146 1146 : used/free/large
0352 1124 1124 : used/free/large
0374 1102 1102 : used/free/large
0396 1080 1080 : used/free/large
0418 1058 1058 : used/free/large
0440 1036 1036 : used/free/large
freeing
0418 1058 1036 : used/free/large
0396 1080 1036 : used/free/large
0374 1102 1058 : used/free/large
0352 1124 1058 : used/free/large
0330 1146 1058 : used/free/large
0308 1168 1058 : used/free/large
0286 1190 1058 : used/free/large
0264 1212 1058 : used/free/large
0242 1234 1058 : used/free/large
0220 1256 1058 : used/free/large
0198 1278 1058 : used/free/large
0176 1300 1058 : used/free/large
0154 1322 1058 : used/free/large
0132 1344 1058 : used/free/large
0110 1366 1058 : used/free/large
0088 1388 1058 : used/free/large
0066 1410 1124 : used/free/large
0044 1432 1300 : used/free/large
0022 1454 1300 : used/free/large
0000 1476 1476 : used/free/large
Logged


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

Well I got rid of the "crash". I added a *gasp* delay!

Code:
delay (1000);
 
// freeze the mcu until reset
 
  exit(0);

It appears that "freeze the MCU" was taken a bit literally, and the final few bytes were not output to the serial port.
Logged

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

Nick, come back to the light. Fix it with hardware I say.

Lefty

In a moment, Lefty. smiley-wink
Logged

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

Right then.

Since I don't know how to fix the precompiled libraries, I've simply made my own versions of malloc/free/realloc from the avr-libc-1.7.1 source.

This can be downloaded from:

http://gammon.com.au/Arduino/mymalloc.c

Just incorporate that into your project (make a new tab in the IDE called mymalloc.c - NOT .cpp) and paste the file into it.

Then, add this to the start of your project:

Code:
extern "C" {
  void * mymalloc(size_t len);
  void myfree(void *p);
  void * myrealloc(void *ptr, size_t len);
}

Now change (or #define) malloc to mymalloc and so on. Then the test runs with everything going back to normal at the end.

Possibly all that needs changing is free, since I think that is the thing with the bug.

A caveat is that things like the String library will probably still pull in the old malloc/free. There is probably a smarter way of achieving this.
Logged

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

Another caveat. Taking a closer look, this version (taken from 1.7.1) does not seem to contain the patch alluded to in the previous page. Interesting.
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

Quote from: Joerg Wunsch
I backed out your patch, and instead rewrote free() so it returns memory from the heap whenever the topmost chunk of the freelist becomes free. While it increases the codesize a little, it appears to be the cleanest solution to me. If you still find any issue with this, please open a new bug report, preferrably with a test case. Have a look at the existing testcases to get an idea how they look like.

So it seems that free() was rewritten somewhere in time.

I'm wondering which avr-libc wiring uses.. Andy had his uC to correctly free the memory blocks.
Logged


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