Garbage Collection

[g-rh@cca.CCA.COM (Richard Harter)]

In article <628@ra.rice.edu> boehm@titan.rice.edu (Hans Boehm) writes:

>  My experience is that any attempt at manipulation of interesting linked
>structures in a language that doesn't support real automatic storage
>management will either fail, or waste large amounts of debugging time.
>(My experience includes a (working) 40,000 line compiler, written in C, that
>manipulates a reference counted syntax "tree", or more accurately, a
>reference counted syntax graph.)  Normally, it is extremely difficult
>to track down bugs created by premature deallocation.  When such bugs are
>finally removed, the resulting programs normally include a substantial
>number of storage leaks.
>  Some recent experiments by Mark Weiser and myself with retrofitting a
>garbage collector to existing C programs, verify the latter point.
>(The garbage collector should never free anything since that was the
>programmers responsibility.  It does.  In other people's code.
>Our paper on this should appear in Software P&E shortly.)
>Mike Caplinger reported similar results for another application at the last
>USENIX conference, I believe.  We have resurrected C code with storage
>management bugs by linking it against a garbage collector (which in the case
>of C doesn't always work either, but it has a better track record than manual
>storage management).

	There is problably something I am missing, but I don't quite see
how you can implement garbage collection in C without collateral assumptions
-- how is the garbage collector supposed to know that that a block is free?

	Your main point is certainly true - manual allocation and deallocation
with the programmer being responsible for ensuring that all comes out right
really doesn't work very well.  This was a critical issue for us -- our
software has to run on systems which do not have pseudo-infinite memory
and it sometimes has to run for very long runs.  We can't afford memory
leaks (or premature deallocation).  What we did was to write our own
storage allocation package.  Salient features:

The allocation routine takes two arguments, a size and an ID.  The latter
is a unique integer specifying that particular call.  (We manage the ID list
manually.)  The allocator creates a node for each request block.  In this
node are sundry links, the ID, and (in effect) a date stamp.  There is also
a hash table that contains the address of every allocated block.  All allocator
control information is stored in a separate space from allocated memory itself.
(This eliminates a large class of mystery bugs associated with overwriting
allocator control data.)

The deallocation routine takes one argument, the address of the block being
returned.  The deallocation routine validates the address as being an
allocated address.  This eliminates another class of bugs caused by passing
an improper or stale address to the deallocation routine.

There is a facility for printing out a complete map of allocated memory
including call ID's and date stamps.  We use this, from time to time, to
check the code for storage leaks.

This scheme is not as good as automatic garbage collection, but we have
found it to be satisfactory.  
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.