From: utzoo!decvax!duke!harpo!seismo!hao!hplabs!sri-unix!dan@BBN-UNIX
Newsgroups: net.unix-wizards
Title: Re: compaction using realloc
Article-I.D.: sri-unix.4783
Posted: Fri Dec 10 04:25:31 1982
Received: Sun Dec 12 11:24:56 1982

From: Dan Franklin <dan at BBN-UNIX>
Date:  6 Dec 1982 16:56:22 EST (Monday)
I agree; that code is highly implementation-dependent.  It knows that the last
storage freed is always the first storage allocated (if it fits).  This wouldn't
be so bad if that particular strategy weren't so awful in the general case.  I
once wrote a program which used stdio to read a lot of files (never more than
three were open simultaneously) and also permanently allocated a series of small
chunks of space (for a linked list).  It turns out that if you have a series of
such small allocations, interspersed with the malloc(512), free() statements
from stdio, that every 512-byte freed area gets at least one tiny chunk removed
from it, so EVERY TIME stdio reaches out for another buffer it causes an sbrk!
Essentially the program acted as though the free() simply weren't there!

It would be nice if we could fix malloc, and at the same time provide the
malloc_compact routine you suggest.  It would mean breaking those programs--like
the one that fragment of code came from--that relied on its LIFO behavior, but
the statement in the manual is so opaque that there probably aren't very many
such programs--and I for one would never rely on being able to get back freed
data (which I think the manual is recommending) in any case!

    Dan