bugAVR C Runtime Library - Bugs: bug #25723, Realloc corrupts free list when...

 
 

bug #25723: Realloc corrupts free list when growing into the next free item

Submitted by:  None
Submitted on:  Sat 28 Feb 2009 02:06:08 AM UTC  
 
Category: LibrarySeverity: 5 - Blocker
Priority: 9 - ImmediateItem Group: libc code
Status: FixedPercent Complete: 0%
Assigned to: Joerg Wunsch <joerg_wunsch>Originator Email: -unavailable-
Open/Closed: ClosedRelease: 1.6.3
Fixed Release: 1.6.6

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Mon 30 Nov 2009 06:40:34 PM UTC, comment #8:

Stefan Ernst came across the same regression and filed it as bug #27242. I've posted a patch there which should fix the problem.

Aleksandar Kanchev <kanchev>
Sun 29 Nov 2009 02:21:27 PM UTC, comment #7:

Hello, I think that there is a miscalculation in the patch which leads to a severe bug.

In realloc.c:
58: cp = (char )ptr + len; / new next pointer */
62: fp2 = (struct __freelist *)(cp - sizeof(size_t));
71: if (len <= fp1->sz) {
77: fp2->sz = fp1->sz - len - sizeof(size_t);
78: fp1->sz = len;

This leads to fp1 being actually 2 bytes less than the size stored into fp1->sz. Also it changes the last two bytes of the allocated memory and this is how I found it.

Code to reproduce the bug:
int main(void) {
uint8_t *p;
p = malloc(16);
p[8] = 8;
p[9] = 9;
p = realloc(p, 10);
if (p[8] != 8 && p[9] != 9)
/* memory looks like this:
* p - 2: 0A 00
* p : FF FF FF FF
* p + 4: FF FF FF FF
* p + 8: 04 00
*/
return 1;
return 0;
}

Since I'm not very sure how to fix this, could please someone confirm and fix this. Thanks!

Aleksandar Kanchev <kanchev>
Wed 04 Mar 2009 10:41:18 AM UTC, comment #6:

Fix applied, thanks! Also thanks for the nice and clear test
case, I added a testsuite script based on it.

One kind request though for future submissions: please always
attach the output of [cvs] diff -u as a separate file. The
web frontend damages all white space in it otherwise.

Joerg Wunsch <joerg_wunsch>
Project AdministratorIn charge of this item.
Sat 28 Feb 2009 05:47:10 PM UTC, comment #5:

Index: realloc.c
===================================================================
RCS file: /sources/avr-libc/avr-libc/libc/stdlib/realloc.c,v
retrieving revision 1.4
diff -u -w -r1.4 realloc.c
--- realloc.c 8 Feb 2005 20:34:17 -0000 1.4
+++ realloc.c 28 Feb 2009 17:46:05 -0000
@@ -59,7 +59,7 @@
if (cp < cp1)
/* Pointer wrapped across top of RAM, fail. */
return 0;
- fp2 = (struct __freelist *)cp;
+ fp2 = (struct __freelist *)(cp - sizeof(size_t));

/*
* See whether we are growing or shrinking. When shrinking,
@@ -84,16 +84,14 @@
* If we get here, we are growing. First, see whether there
* is space in the free list on top of our current chunk.
*/
- incr = len - fp1->sz - sizeof(size_t);
+ incr = len - fp1->sz;
cp = (char *)ptr + fp1->sz;
- fp2 = (struct __freelist *)cp;
for (s = 0, ofp3 = 0, fp3 = __flp;
fp3;
ofp3 = fp3, fp3 = fp3->nx) {
if (fp3 == fp2 && fp3->sz >= incr) {
/* found something that fits */
- if (incr <= fp3->sz &&
- incr > fp3->sz - sizeof(struct __freelist)) {
+ if (incr <= fp3->sz + sizeof(size_t)) {
/* it just fits, so use it entirely */
fp1->sz += fp3->sz + sizeof(size_t);
if (ofp3)
@@ -104,7 +102,7 @@
}
/* split off a new freelist entry */
cp = (char *)ptr + len;
- fp2 = (struct __freelist *)cp;
+ fp2 = (struct __freelist *)(cp - sizeof(size_t));
fp2->nx = fp3->nx;
fp2->sz = fp3->sz - incr - sizeof(size_t);
if (ofp3)

Lou Amadio <ooeygui>
Sat 28 Feb 2009 05:12:29 PM UTC, comment #4:

Updated diff

(sorry about the 'blessed' comment - it was originally a blog post, attempting to understand the avr-lib checkin and unit testing process in order to 'bless' the fix)

Index: realloc.c
===================================================================
RCS file: /sources/avr-libc/avr-libc/libc/stdlib/realloc.c,v
retrieving revision 1.4
diff -u -r1.4 realloc.c
--- realloc.c 8 Feb 2005 20:34:17 -0000 1.4
+++ realloc.c 28 Feb 2009 17:10:38 -0000
@@ -46,21 +46,21 @@
char cp, cp1;
void *memp;
size_t s, incr;
-
+
/* Trivial case, required by C standard. */
if (ptr == 0)
return malloc(len);
-
+
cp1 = (char *)ptr;
cp1 -= sizeof(size_t);
fp1 = (struct __freelist *)cp1;
-
+
cp = (char )ptr + len; / new next pointer */
if (cp < cp1)
- /* Pointer wrapped across top of RAM, fail. */
+ /* Pointer wrapped across top of RAM, fail. */
return 0;
- fp2 = (struct __freelist *)cp;
-
+ fp2 = (struct __freelist *)(cp - sizeof(size_t));
+
/*
* See whether we are growing or shrinking. When shrinking,
* we split off a chunk for the released portion, and call
@@ -79,21 +79,19 @@
free(&(fp2->nx));
return ptr;
}
-
+
/*
* If we get here, we are growing. First, see whether there
* is space in the free list on top of our current chunk.
*/
- incr = len - fp1->sz - sizeof(size_t);
+ incr = len - fp1->sz;
cp = (char *)ptr + fp1->sz;
- fp2 = (struct __freelist *)cp;
for (s = 0, ofp3 = 0, fp3 = __flp;
- fp3;
- ofp3 = fp3, fp3 = fp3->nx) {
+ fp3;
+ ofp3 = fp3, fp3 = fp3->nx) {
if (fp3 == fp2 && fp3->sz >= incr) {
/* found something that fits */
- if (incr <= fp3->sz &&
- incr > fp3->sz - sizeof(struct __freelist)) {
+ if (incr <= fp3->sz + sizeof(size_t)) {
/* it just fits, so use it entirely */
fp1->sz += fp3->sz + sizeof(size_t);
if (ofp3)
@@ -104,7 +102,7 @@
}
/* split off a new freelist entry */
cp = (char *)ptr + len;
- fp2 = (struct __freelist *)cp;
+ fp2 = (struct __freelist *)(cp - sizeof(size_t));
fp2->nx = fp3->nx;
fp2->sz = fp3->sz - incr - sizeof(size_t);
if (ofp3)
@@ -141,7 +139,7 @@
/* If that failed, we are out of luck. */
return 0;
}
-
+
/*
* Call malloc() for a new chunk, then copy over the data, and
* release the old region.

Lou Amadio <ooeygui>
Sat 28 Feb 2009 06:59:25 AM UTC, comment #3:

> I’m now playing with a couple of fixes, but need
> to figure out how to get a ‘blessed’ fix into lib-avr.


Please file it as the output of "cvs diff -u".

I guess I'll also somehow setup a test script for the test
suite.

Joerg Wunsch <joerg_wunsch>
Project AdministratorIn charge of this item.
Sat 28 Feb 2009 02:12:08 AM UTC, comment #2:

(Sorry about not being logged in when committing this bug, this was submitted by user ooeygui - Lou Amadio)

Lou Amadio <ooeygui>
Sat 28 Feb 2009 02:07:30 AM UTC, comment #1:

Note, this may be related to and or fix #22567.

Anonymous
Sat 28 Feb 2009 02:06:08 AM UTC, original submission:

void testMalloc()
{
size_t* array = (size_t)malloc(4 sizeof(size_t));
free(array);
array = NULL;

array = (size_t*)realloc(array, sizeof(size_t));
array = (size_t)realloc(array, 2 sizeof(size_t));
array = (size_t)realloc(array, 3 sizeof(size_t));
realloc(array, 4 * sizeof(size_t));
}
There is a bug in the free list manager in Realloc, specifically when growing a buffer into the next free entry. I was convinced I had a bug in a fairly large codebase, and whittled it down to this reproduction. I’m now playing with a couple of fixes, but need to figure out how to get a ‘blessed’ fix into lib-avr.

Stepping through the malloc into the free results in:

00000010 00000000 00000000 00000000

                1. 00000000 00000000 00000000
                2. 00000000 00000000 00000000

Over the first realloc:

00000008 00000000 00000000 00000004

                1. 00000000 00000000 00000000
                2. 00000000 00000000 00000000

Over the third:

0000000c 00000000 00000000 00000004

                1. 00000000 00000000 00000000
                2. 00000000 00000000 00000000

And finally:

00000010 00000000 00000000 00000004

                1. FFFFFFFC 00000000 00000000
                2. 00000000 00000000 00000000

At this point the free block pointer (__flp) points to the second line, with a size of 0xfffffffc. The next allocation fails.

I've tracked it down to some free list tracking code in realloc.c, here's a patch for the fix, which I have verified.

Index: realloc.c
===================================================================
RCS file: /sources/avr-libc/avr-libc/libc/stdlib/realloc.c,v
retrieving revision 1.4
diff -r1.4 realloc.c
49c49
<
---

>

53c53
<
---

>

57c57
<
---

>

60c60
< /* Pointer wrapped across top of RAM, fail. */
---

> /* Pointer wrapped across top of RAM, fail. */

62,63c62,63
< fp2 = (struct __freelist *)cp;
<
---

> fp2 = (struct __freelist *)(cp - sizeof(size_t));
>

82c82
<
---

>

87c87
< incr = len - fp1->sz - sizeof(size_t);
---

> incr = len - fp1->sz;

89d88
< fp2 = (struct __freelist *)cp;
91,92c90,91
< fp3;
< ofp3 = fp3, fp3 = fp3->nx) {
---

> fp3;
> ofp3 = fp3, fp3 = fp3->nx) {

95,96c94
< if (incr <= fp3->sz &&
< incr > fp3->sz - sizeof(struct __freelist)) {
---

> if (incr <= fp3->sz + sizeof(size_t)) {

107c105
< fp2 = (struct __freelist *)cp;
---

> fp2 = (struct __freelist *)(cp - sizeof(size_t));

144c142
<
---

>


Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by kanchev (Posted a comment)
  • -unavailable- added by arcanum (Updated the item)
  • -unavailable- added by joerg_wunsch (Posted a comment)
  • -unavailable- added by ooeygui (Posted a comment)
  •  

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 04 Mar 2009 10:41:18 AM UTCjoerg_wunschStatusNone=>Fixed
      Assigned toNone=>joerg_wunsch
      Open/ClosedOpen=>Closed
      Fixed ReleaseNone=>1.6.6
    Sat 28 Feb 2009 04:38:10 PM UTCarcanumPriority5 - Normal=>9 - Immediate
    Sat 28 Feb 2009 06:59:46 AM UTCjoerg_wunschSeverity3 - Normal=>5 - Blocker

    Back to the top


    Powered by Savane 3.1-cleanup1