alloca, malloc and friends

[Doug Gwyn]

In article <6793 at suns302.cel.co.uk> ir at cel.co.uk (ian reid) writes:
>There seems to me to be a fundamental flaw in the implementation of malloc,
>as I can determine the implementation from TFM.

No, malloc() is okay.

>As I understand it malloc(3) manages an area of memory in the data segment,
>if there is insufficient space in the data segment a call to sbrk(2) is made
>to increase the size of the data segment, and hence the memory available for
>malloc to manage.  The size of the application therefore grows by the amount
>of memory added to the data segment.

Essentially correct.

>The problem is that there is no way that this memory can be returned to the 
>operating system, at least no way documented on the sbrk(2) manual page ...

Theoretically, brk()/sbrk() can be used to reduce the program break as well
as increase it.  However, most malloc() implementations don't bother to try
to detect the opportuntity to do this, because it isn't really very useful.

>Well imagine this, an application mallocs (insert a number here which is a
>large amount of memory for system), this is a one-off occurrence and this
>much memory is never needed again.  But the application size can never
>shrink, therefore a lot of memory which is not being used is unavailable to
>the system.

In practice this seldom matters, particularly in a demand-paged virtual
memory environment, which is used by most UNIX implementations on "real"
computers these days.

>I'm specualting that alloca(3) which allocates memory on the stack frame was
>invented for two reasons.  Firstly to overcome the above flaw in malloc, and
>secondly for speed.  alloca has it's own flaws though, it's operating system,
>compiler and architecture dependant (I think this means it's not portable:-))
>, and as if this weren't enough there is no documented way to grow the stack
>segment so there's less chance of being able to get the memory you want.

alloca()'s main raison d'etre is to automatically garbage collect the
allocated storage when the containing function's dynamic scope terminates.
Of course auto variables have this property too, but they require that the
needed space be known precisely in advance, whereas alloca() steals space
as requested and is thus more flexible.

There are architectures for which implementing alloca() is impractical,
and you should simply not count on its being universally available.  I
published a "mostly portable" public-domain implementation that has seen
wide distribution, but I'll be among the first to admit that it has its
flaws.  I intended it only as an aid for people trying to port already-
written code that relied unduly heavily on alloca(), not for new code.

Note also that machine machines have much more stringent limits on the
total amount of stack space allocated than on malloc()ed heap space.