From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.7 required=5.0 tests=BAYES_00,INVALID_DATE, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 Xref: utzoo comp.lang.misc:1377 comp.lang.modula2:737 comp.lang.ada:1092 Path: utzoo!mnetor!uunet!husc6!cca!g-rh From: g-rh@cca.CCA.COM (Richard Harter) Newsgroups: comp.lang.misc,comp.lang.modula2,comp.lang.ada Subject: Garbage Collection Message-ID: <26358@cca.CCA.COM> Date: 31 Mar 88 06:27:08 GMT References: <145@krafla.rhi.hi.is> <272@fang.ATT.COM> <429@zap.UUCP> <8196@sol.ARPA> <628@ra.rice.edu> Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter) Organization: Computer Corp. of America, Cambridge, MA List-Id: 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.