Heap Fragmentation

[Doug Gwyn]

In article <6643 at thor.acc.stolaf.edu> mike at thor.stolaf.edu () writes:
>In article <11161 at smoke.BRL.MIL> gwyn at brl.arpa (Doug Gwyn) writes:
>>... it would be unsafe for
>>a UNIX malloc()/free() implementation to shrink the heap in general.
>Not true.  GNU malloc(), of which I am the author, can shrink the heap.
>...  The algorithm is:
>	if (sbrk(0) == mallocs_notion_of_top_of_heap)
>		sbrk(negative_amount);

Well, I did say it's not safe to shrink it in general, not "in general,
it's not safe to shrink it".  In specific cases it can be safe.  Note,
however, that it's tricky to get right.  Consider the scenario:
	malloc() => sbrk(+)
	sbrk(+)
	malloc() => sbrk(+)
	free() => sbrk(-) by above algorithm
At this point malloc()/free() need to be able to determine where the
last malloc() arena heap-top is, to know that it's not at the current
sbrk(0).  You may have taken care of this extra bookkeeping requirement,
but it's easy to get wrong.  I put quite a bit of time a couple of
years ago into fixing all the bugs in the SVR2 malloc() (both of them);
I think that it did manage to keep synchronized with sbrk() although it
never tried to shrink the program break.