Re: Strange malloc() problem, what am I missing

[Jeff Johnston <jjohnstn at redhat dot com>]

Per-Henrik Lundblom wrote:
> * Per-Henrik Lundblom <ph@whatever.nu> [060810 09:50]:
>
>
> > Hi,
> >
> > I'm using newlib in a project involving FreeRTOS running on an ARM7
> > target (Philips LPC2138, 32kb RAM). I have use pre-compiled GnuARM
> > toolchain available from www.gnuarm.net running on both Windows and 
> > Linux. The newlib version is 1.14.0.
> >
> > I have spent the last week trying to sort out a strange problem that
> > occurs when using malloc() (eg. malloc_r()). In my application I alloc a
> > few "large" blocks (~1kb) and then continously alloc and free a lot of
> > small chunks (8-100bytes). I haven't fully understood exactly how the
> > malloc implementation in newlib works but I will try to describe the
> > problem:

Can you create a test case that duplicates the problem consistently?
It's tough to analyze something like this without such a simple test case.


> > Eventually a 24 bytes allocated chunk will be free:d and placed in the
> > 24 bytes bin. This is the only chunk in the 24 bytes bin so the two
> > next/prev chunk pointers in the chunk points to the same location and
> > that location is the chunk itself.
> >
> > This chunk eventually is allocated with a malloc(18) which turns out to
> > a request to a 24 bytes chunk. The code executed is mallocr.c:2357.
> > victim and q is set and are not equal so the code block starting at line 
> > 2374 is executed. The unlink() macro is executed. Here I experience the
> > strange problem. Unlink doesn't release the chunk from the 24 byte bin
> > in the __malloc_av_ (av_ in mallocr.c). Because the chunk is the only
> > chunk in the 24 byte bin I get the impression it should!
> >
> > Anyway, the chunk is allocated and returned to the application that
> > writes data to it. The next/prev pointers that where in the "head" of
> > the chunk when it was free is of course overwritten because this memory
> > is allocated and returned to the application.
> >
> > After a while a malloc(8) is requested. This is again seen as a small 
> > request by malloc. The code in the block mallocr.c:2357 is executed. q and
> > victim is set, but because these are equal, the q and victim is advanced
> > one bin. But now this bin is still pointing at the chunk that where
> > allocated to the application previously! The application has overwritten
> > the next/prev pointers in the chunk and because of this, these pointers
> > are invalid and results in a data abort on the ARM7 when executing the
> > unlink() macro.
> >
> > I have fixed this with a simple if statement checking if all the
> > conditions mentioned above is true. If yes, the __malloc_av_ bin array
> > is updated. See patch below.
> >
> > THE REAL QUESTION IS: What am I missing, have I mis-configured
> > something? I can't really see such a simple thing beeing a flaw in the
> > implementation.

The malloc code has been in use for a while and fairly stable, but that 
doesn't mean it's proven free from all defects.  The code in newlib is 
based on an older version of Doug Lea's malloc (2.6.4).  The current 
version is at least: 2.8.3.  It isn't just a simple grab of the new code 
as there is newlib-fication required.  I tend to be leary of changing 
such a sensitive fundamental piece of code without evidence a particular 
problem is being solved and new ones aren't introduced.

I went to Doug's web-site:  ftp://gee.cs.oswego.edu/pub/misc/ to see if 
I could find any key fixes that might help you.  Looking through the 
brief discussion at the end of the current malloc, I didn't see a lot of 
"fixes" mentioned per se.  A fix was made in 2.7.1 to sysmalloc, but it 
is tough to compare that with 2.6.4 as many additional changes were 
introduced as of 2.7.0.

In 2.6.5, Doug made a simple patch to the malloc_extend_top function 
which I have included.  It may not have anything to do with your 
problem, but I include it none-the-less.  Try it out.

I also included the current malloc.c I found there.  If you want to try 
the latest version (with some fiddling to get it working), that would go 
a long way to determine if the problem has already been solved.

I will forward your note to Doug to see if your problem sounds at all 
familiar to him.

-- Jeff J.

> > --- newlib-1.14.0/newlib/libc/stdlib/mallocr.c  2005-10-07 20:07:26.000000000 +0200
> > +++ newlib-1.14.0_patched/newlib/libc/stdlib/mallocr.c  2006-08-09 17:07:14.4230 64700 +0200
> > @@ -2367,6 +2367,7 @@ Void_t* mALLOc(RARG bytes) RDECL size_t
> >     if (victim == q)
> >     {
> >       q = next_bin(q);
> > +      victim = (mchunkptr) q;
> >       victim = last(q);
> >     }
> > #endif
> > @@ -2374,6 +2375,11 @@ Void_t* mALLOc(RARG bytes) RDECL size_t
> >     {
> >       victim_size = chunksize(victim);
> >       unlink(victim, bck, fwd);
> > +if (victim->fd == victim->bk && last(q) == first(q) && victim->fd ==
> > last(q))
> > +{
> > +    q->fd = q;
> > +    q->bk = q;
> > +}
> >       set_inuse_bit_at_offset(victim, victim_size);
> >       check_malloced_chunk(victim, nb);
> >       MALLOC_UNLOCK;
>
>
> Doesn't anyone have a clue about this? 
>
> /PH
>
> --
> Per-Henrik Lundblom           epost: ph@whatever.nu
> telefon: 0733-20 71 26        hemsida: www.whatever.nu

Index: libc/stdlib/mallocr.c
===================================================================
RCS file: /cvs/src/src/newlib/libc/stdlib/mallocr.c,v
retrieving revision 1.15
diff -u -p -r1.15 mallocr.c
--- libc/stdlib/mallocr.c	7 Oct 2005 18:07:26 -0000	1.15
+++ libc/stdlib/mallocr.c	21 Aug 2006 18:54:09 -0000
@@ -2223,11 +2223,11 @@ static void malloc_extend_top(RARG nb) R
 
       /* Also keep size a multiple of MALLOC_ALIGNMENT */
       old_top_size = (old_top_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
-      set_head_size(old_top, old_top_size);
       chunk_at_offset(old_top, old_top_size          )->size =
         SIZE_SZ|PREV_INUSE;
       chunk_at_offset(old_top, old_top_size + SIZE_SZ)->size =
         SIZE_SZ|PREV_INUSE;
+      set_head_size(old_top, old_top_size);
       /* If possible, release the rest. */
       if (old_top_size >= MINSIZE) 
         fREe(RCALL chunk2mem(old_top));

Attachment: malloc.c.tgz
Description: application/compressed-tar