Organization: Ecole Nationale Superieure des Telecommunications, Paris
Date: Tue, 12 Oct 93 15:56:25 +0100
From: David Powers <powers AT inf DOT enst DOT fr>
To: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: Re: Malloc and free

> >     I compile the program using: gcc prog.c -Wall
> 
> >     Why is'nt the memory free'd ?
> 
> How do you know it isn't freed?  There are no calls in there to check
> memory status.  Note that since you allocate ever-increasing block
> sizes, the smaller chunks are never available for future mallocs.  You
> end up with a very large free list (djgpp's malloc doesn't merge free
> blocks, sadly).
> 
> Try running your test the other way - start with big packets, then
> allocate ever smaller ones.

Most people writing portable programs write their own mallocs, because
some mallocs are incredibly bad, and although some are tuneable, not all
are.  The Berkeley/GNU/DJGPP distribution malloc can waste up to 87.5%
of your memory - if you keep (re)allocating bigger and bigger blocks,
because it always uses blocks of size a power or two, and it doesn't
return or merge such blocks, so that all the smaller blocks are still around
on free lists (so that wastes half already, in addition, half of the
current block may be wasted - e.g. if you are allocating EXACT powers of
two, the few bytes of overhead force you into the next size, so you are
using only 25% of the memory malloc has grabbed).  The justification for
this approach is that with virtual memory, these holes don't matter, they
just won't be paged in.  But if they are dirty, and as malloc doesn't say
it doesn't need them, they will use up you swap space.  In addition,
if your current usage uses one block more than half of swap space,
you won't be able to grow again, so you have bombed out when using only
12.5% of your swap space.

I have also written a malloc replacement that uses sbrk() stackwise,
and is incompatible with malloc (which is a problem for the many library
routines which use malloc).  I have also written a hmalloc library which
also allows allocating and growing arbitrarily large logical datastructures
using malloc to provide fixed size chunks and linking them together, providing
a set of access routines to access, push, pop and move frames of this stack.

Malloc and sbrk are intrinsically dated as hardware and operating systems
can now support multiple independent stacks, and malloc/sbrk assume just one.

The moral is, that for any application that is going to push the system to
the limit, you need to evaluate your requirements for malloc very carefully,
and either provide your own malloc, an independent allocation technique,
or some higher-level discipline to ensure the default malloc is used in an
efficient way.

dP