Malloc implementation in avr

[Boyapati, Anitha]

Hi,

I have a question w.r.t malloc implementation in AVR. Malloc pages from avr-libc user manual (http://www.nongnu.org/avr-libc/user-manual/malloc.html):

Excerpt -

"When allocating memory, first the freelist is walked to see if it could satisfy the request. If there's a chunk available on the freelist that will fit the request exactly, it will be taken, disconnected from the freelist, and returned to the caller. If no exact match could be found, the closest match that would just satisfy the request will be used. The chunk will normally be split up into one to be returned to the caller, and another (smaller) one that will remain on the freelist. In case this chunk was only up to two bytes larger than the request, the request will simply be altered internally to also account for these additional bytes since no separate freelist entry could be split off in that case. "

I am trying to understand the rationale behind the last case. The corresponding source file malloc.c has the following code (line 112) in for malloc(size_t len) -



/*
 * Step 2: If we found a chunk on the freelist that would fit
 * (but was too large), look it up again and use it, since it
 * is our closest match now.  Since the freelist entry needs
 * to be split into two entries then, watch out that the
 * difference between the requested size and the size of the
 * chunk found is large enough for another freelist entry; if
 * not, just enlarge the request size to what we have found,
 * and use the entire chunk.
 */
if (s) {
        if (s - len < sizeof(struct __freelist))
                len = s;

This means when a user requests say for x bytes from heap, he will get x+2 bytes. Suppose a user's application does a hack on the memory returned to verify the exact size, would not this be a problem? Or he may want write his own free().  Although the probability of such a case is low, it still appears as a limitation to me(I think a testcase might be difficult for such a case)

Regards
Anitha


_______________________________________________
AVR-libc-dev mailing list
AVR-libc-dev@...
http://lists.nongnu.org/mailman/listinfo/avr-libc-dev

[Joerg Wunsch]

As Boyapati, Anitha wrote:

> This means when a user requests say for x bytes from heap, he will
> get x+2 bytes.

Yes, but keep in mind that this will *only* happen if the request is
satisfied from a freelist entry that was exactly x+2 bytes long (as
such an entry could not be split into an actual part to return, and a
remainder to keep in the freelist).

> Suppose a user's application does a hack on the memory returned to
> verify the exact size, would not this be a problem?

What "hack" do you have in mind?

The user is requesting a piece of memory x bytes long.  The only grant
that is implied by returning a non-NULL pointer is that this points to
a memory area that has /at least/ x bytes space.  For example, in
environments where RAM consumption is not such a big problem as for
microcontrollers, it is quite common to round up each request to the
next power of two for efficiency reasons (at least for small
requests).  For the pointer returned, the user must /never/ write
below ptr[0] or above ptr[x-1], so it could not possibly detect how
large the memory chunk returned actually is.

> Or he may want
> write his own free().

He is not allowed to do this (the C standards explicitly forbids that
an application overrides a library implementation), and this would not
work in almost /any/ C environment, because the way free() must be
implemented is completely tied to the implementation of malloc()
itself.

--
cheers, J"org               .-.-.   --... ...--   -.. .  DL8DTL

http://www.sax.de/~joerg/                        NIC: JW11-RIPE
Never trust an operating system you don't have sources for. ;-)


_______________________________________________
AVR-libc-dev mailing list
AVR-libc-dev@...
http://lists.nongnu.org/mailman/listinfo/avr-libc-dev

[Boyapati, Anitha]

> -----Original Message-----
> From: avr-libc-dev-bounces+anitha.boyapati=atmel.com@...
> [mailto:avr-libc-dev-bounces+anitha.boyapati=atmel.com@...] On
> Behalf Of Joerg Wunsch
> Sent: Monday, September 14, 2009 6:14 PM
> To: avr-libc-dev@...
> Subject: Re: [avr-libc-dev] Malloc implementation in avr
>
> As Boyapati, Anitha wrote:

>
> > Or he may want to
> > write his own free().
>
> He is not allowed to do this (the C standards explicitly forbids that
> an application overrides a library implementation), and this would not
> work in almost /any/ C environment, because the way free() must be
> implemented is completely tied to the implementation of malloc()
> itself.


This sure explains the rationale. Thanks for the details.


Regards
Anitha



_______________________________________________
AVR-libc-dev mailing list
AVR-libc-dev@...
http://lists.nongnu.org/mailman/listinfo/avr-libc-dev

[Stu Bell]

> > > Or he may want to write his own free().
> >
> > He is not allowed to do this (the C standards explicitly
> > forbids that an application overrides a library implementation),
> > and this would not work in almost /any/ C environment, because
> > the way free() must be implemented is completely tied to the
> > implementation of malloc() itself.
>
>
> This sure explains the rationale. Thanks for the details.

On the other hand, this should not stop you from implementing your own
memory manager if you believe you understand your application's needs
and usage patterns, and you believe that a better mechanism for the
application would improve it's memory usage.  

For example, FreeRTOS comes with 3 different "heap managers" (or
malloc/free pairs) with different ideas about how dynamic memory should
be managed.  In each case, the heap manager is pre-allocated a chunk of
RAM that it manages.  In our application, we've taken one of the heap
managers and tweaked it further as we've seen how memory is actually
used.

Rather than calling the routines "malloc" and "free", the routines are
called "pvPortMalloc()" and "vPortFree()".  From a strict maintenance
point of view, I prefer to have a specially named function for my heap
manager instead of renaming malloc() and free().  This will tell a later
programmer that he is not looking at the "box standard" malloc but at a
custom heap manager.

In the embedded world, the programmer can and must control many things
that are handed to him in the "big compute" world of PCs.  Memory
management is one of those things.  Realize that, while the C compiler
and library are the enablers, *you* must decide how to manage the
resources available to you.  That is the blessing and curse of
programming microcontrollers.

Best regards,

Stu Bell
DataPlay (DPHI, Inc.)



_______________________________________________
AVR-libc-dev mailing list
AVR-libc-dev@...
http://lists.nongnu.org/mailman/listinfo/avr-libc-dev