Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!rice!sun-spots-request
From: mc%miranda.uucp@moc.jpl.nasa.gov (Mike Caplinger)
Newsgroups: comp.sys.sun
Subject: "busted" malloc
Message-ID: <8901312116.AA01896@miranda.uucp>
Date: 9 Feb 89 01:37:17 GMT
Sender: usenet@rice.edu
Organization: Sun-Spots
Lines: 25
Approved: Sun-Spots@rice.edu
Original-Date: Tue, 31 Jan 89 14:16:52 MST
X-Sun-Spots-Digest: Volume 7, Issue 145, message 7 of 11

All versions of malloc from, I believe, 4.0 BSD on, have used a
powers-of-two multiple free list allocation scheme instead of the simpler,
less virtual-memory-efficient first-fit policy used in version 7 Unix.
Simply, this means that if you ask for two chunks of size N, free both,
and them ask for one chunk of size 2N, the system doesn't use the old
space, because it groups allocated blocks into multiple spaces based on
their size.

Your test program actually *does* reuse the large block on the second big
allocate (under 4.0 I verified that it returns the same address both
times), it just sbrks for more space in preparation for extending its free
list.  I suspect that this, coupled with the N vs. 2N problem mentioned
above, is the source of your difficulty.

All this probably doesn't help you much.  Two things: first, malloc is
surprisingly complicated, probably more than I think you expect; second, I
agree that this behavior is undesirable, but there are legitimate reasons
for why it works this way.  You could try using another version of malloc;
I wrote one described in the Winter 1988 Usenix Proceedings, but it
doesn't interact well with SunView, alas.  If you have the old, old
version 7 allocator handy, you could try that.  It should be noted though,
that SunView uses funny allocation (especially with space allocated with
the valloc call.)

	Mike Caplinger, mc@moc.jpl.nasa.gov