pcg@cs.aber.ac.uk (Piercarlo Grandi) (09/25/90)
I am reposting here, with updates and extensions, a collection of news articles on the subject of storage management (mostly conservative g.c.) in C++, for which i have had some requests. From chase@Ozona.UUCP 16 Nov 88 19:30:05 GMT Path: aber-cs!dcl-cs!ukc!mcvax!uunet!husc6!mailrus!ncar!ames!oliveb!Ozona!chase From: chase@Ozona.orc.olivetti.com (David Chase) Newsgroups: comp.lang.c Subject: C garbage collection Message-ID: <32696@oliveb.olivetti.com> Date: 16 Nov 88 19:30:05 GMT References: <8841@smoke.BRL.MIL> <1988Nov11.232629.15414@utstat.uucp> <20588@apple.Apple.COM> <32596@oliveb.olivetti.com> <276@esosun.UUCP> Sender: news@oliveb.olivetti.com Reply-To: chase@Ozona.UUCP (David Chase) Organization: Olivetti Research Center, Menlo Park, CA Lines: 88 Status: RO In article <276@esosun.UUCP> jackson@freyja (Jerry Jackson) writes: >(I wrote) > >>(Yes, a garbage collector for C -- >> ~ftp/sun-source/gc.shar@titan.rice.edu >>It works on Sun3s, Sun4s, Vaxes. Send mail with subject "help" to >>"archive-server@rice.edu" if you lack FTP access.) >> > >I've written garbage collectors for lisp and have a pretty good idea >what is involved... I can't imagine what this does, but I'm pretty sure >it's something very different. Could someone please explain what this >program does? Sure (I thought you'd never ask :-). The collector was written by Hans-J. Boehm, Alan J. Demers, with contributions from Mark Weiser at Xerox and suggestions from me here. The algorithms are described in Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative Environment", Software Practice & Experience, September 1988. The collector/allocator segregates objects by size (Big Bags of Pages) and keeps a free list for each size. Objects too large to fit in a page, of course, are allocated using a different strategy. The mark bits for each piece of allocated memory are stored in a "bit array" at the beginning of each page; there are no "header words" prepended to allocated memory. Pages of objects can also be tagged as "non-pointer-containing" to improve the performance of the collector. After collection, pages are scanned to rebuild free lists and empty pages. Collection itself is just trace-and-sweep, using process stack to store temporary marking information. The collector makes certain assumptions about pointer use that don't hold for all C programs; however, they hold for most C programs. These are: 1) BSS, stack, registers, and data are always "live". 2) If something "live" contains a pointer to the *beginning* of a block of allocated memory, then that object is "live". 3) Linked lists store their "next" pointer in the first word of an object (this is just an important optimization). Obviously this collector will sometimes fail to reclaim an object, because some integers will look like pointers. In practice, this is not a problem. Obviously, this collector can be tricked into reclaiming something to which a pointer is retained if the pointer is encoded. Knuth's pointer XORing trick in lists is not compatible with this collector, and adding 4 to every pointer will also confuse it. Note, however, that there is nothing wrong with encoded pointers to an object AS LONG AS AT LEAST ONE pointer to the beginning remains. Thus, this collector can be used with a "front-end allocator" if the front-end allocator keeps its pools linked together. Most C programs do retain pointers to the beginning of objects, so this usually works. How is this used with C? Typically, I replace "malloc" with "garbage-collected malloc" and "free" with "do-nothing". The garbage collector supports freeing of allocated structures, but I don't bother. If free is do-nothing, then a trivial realloc maintains compatibility with the old-style realloc that people seem to worry about so much (this is so because if you can "realloc" a pointer, then you must have a copy of it somewhere, and if you have a copy of it somewhere, then in the garbage collector's eyes it hasn't really been freed, and thus hasn't been overwritten or reused. Note that with BIBOP allocation a realloc must almost always perform a new allocation.) What have we used this with? Code, lots of it. (Read the SP&E article; they ran it with lots of stuff, also.) Thousands of lines of C and Modula-2+, generated by tools, compiled by three different compilers (M2+, cc, gcc), taken from the X library, and recycled from years ago. We are perhaps not a typical group, since M2+ requires garbage collection, and all code written recently (by us) was written with the knowledge that a collector would be used. We've only had two problems with it: 1) if you don't put your linked-list links in the first word and have BIG lists, you'll gobble up lots and lots of stack. Note that signals are turned off during collection to avoid unpleasant surprises. 2) because there are no header words attached to objects, this allocator exposes overwriting bugs that otherwise go unnoticed until memory is freed (and if memory isn't freed, then they just go unnoticed). For more information, obtain the collector and read the README file. The shar file is about 67K large. David From dld@F.GP.CS.CMU.EDU 13 Feb 89 23:30:30 GMT Path: aber-cs!dcl-cs!ukc!mcvax!uunet!lll-winken!ames!mailrus!cornell!rochester!pt.cs.cmu.edu!pt!dld From: dld@F.GP.CS.CMU.EDU (David Detlefs) Newsgroups: comp.lang.c++ Subject: RE: Garbage Collection Message-ID: <DLD.89Feb13183030@F.GP.CS.CMU.EDU> Date: 13 Feb 89 23:30:30 GMT Organization: CMU CS Department Lines: 42 Status: RO << Kevin Sullivan asks about garbage collection for C++. >> I've been doing a literature search in this area recently, and have found the following relevant references: Boehm & Weiser: "Garbage Collection in an Uncooperative Environment" Software Practice & Experience, September 88 Caplinger: "A Memory Allocator with Garbage Collection for C" Winter 88 Usenix Both of these present mark & sweep algorithms fairly compatible with the existing malloc/free/etc interface. Bartlett: "Compacting Garbage Collection with Ambiguous Roots" DEC WRL Research Report 88/2 Outlines an approach applicable to a copying collector for C. (To get, send a message to wrl-techreports@decwrl.dec.com, with body "help.") All of these methods are applicable, mutas mutandis, to C++. There is also a rumor that Chris Torek of Maryland is working on something along these lines (Chris, if you read this, could you confirm or deny to me, along with a pointer to a reference, or a description of what you're doing? Thanks...) Hopefully I've done a service. Perhaps the collective consciousness out there can help me in return. I would like to find some emprical evidence on just how much more reliable garbage collection makes programs. The ideal reference would be one that states "in project X, we found Y bugs, Z% of which were caused by improper explicit storage management. These took W% of the time to debug..." Any pointers to such a paper would be greatly appreciated. Thanks! -- Dave Detlefs Any correlation between my employer's opinion Carnegie-Mellon CS and my own is statistical rather than causal, dld@cs.cmu.edu except in those cases where I have helped to form my employer's opinion. (Null disclaimer.) -- From roy@phri.UUCP 8 Jun 89 01:35:09 GMT Path: aber-cs!dcl-cs!ukc!mcvax!uunet!cs.utexas.edu!rutgers!cmcl2!phri!roy From: roy@phri.UUCP (Roy Smith) Newsgroups: comp.unix.wizards Subject: Re: Need debugging version of malloc()/free() Message-ID: <3795@phri.UUCP> Date: 8 Jun 89 01:35:09 GMT References: <850@pcsbst.UUCP> Reply-To: roy@phri.UUCP (Roy Smith) Organization: Public Health Research Inst. (NY, NY) Lines: 226 Status: RO jkh@meepmeep.pcs.com ( Jordan K. Hubbard ) writes: > Has anyone written a version of malloc/free that keeps extra information > around about each chunk allocated and free'd so that garbage things free'd > (or legitimate data free'd multiple times) can be detected and reported? I have two such packages, both of which were posted to the net some time ago. Michael Schwartz's maltrace package (slightly reformatted README file included below) is for tracing memory leaks; not exactly what Jordan asked for, but useful in its own right. I don't have much experience with it personally. Another package, from Brandon Allbery (see excerpt below), is useful for the kind of stuff Jordan wants to do; ckecking for corrupted malloced()'d memory, bad or redundant free()'s, etc. I've used it a lot and think it's wonderful. If you have BSD source, you should be able to recompile your standard malloc package to do similar checking, but I've never done so, I just use Brandon's. See the headers below to find out where and when the articles were posted originally. If you can't find them in some standard archive site (they are probably both on uunet, I would guess) let me know and I could mail them to you. > An additional plus would be for malloc() to somehow detect when you'd gone > off the end (either end) of a malloc'd block, but I can see how this would > be a lot harder to do, if not impossible in some cases. I've never tried this, but it seems possible to automatically generate a call to a checking function after each statement using a procedure like what dbx's "next" function does to single-step through a program to gain control. Each time you malloc a block, you could generate a few extra words before and after the block and fill them with magic numbers. The checking function could make sure all the magic numbers are as they should be. Of course, you still want to have free() be extra careful about checking to make sure it's freeing something it's supposed to. You might also have free zero out every byte that it frees and check to make sure that they stay zero (or some magic number, preferably an odd number which is not likely to be a valid pointer) each time the check function is called. This will catch programs which still use free()'d memory. This would all be slow as shit, but at least it would catch most malloc errors. Perhaps you could have switches all over the place to trade off speed for exhaustiveness -- maybe only check on every Nth statement execution, maybe not to the free'd zero checking, etc. Another thing which might be nice to have is a flag to malloc to automatically make each allocated block N bytes longer than is asked for. If your program has mysterious crashes which go away when you allocate an extra 4 bytes on each block, you might want to start looking for off-by-one errors at the ends of malloc'ed blocks. ---------------------- Newsgroups: comp.sources.misc Subject: maltrace -- trace un-free()'d space with dbx (maybe others?) Message-ID: <2835@ncoast.UUCP> Date: 10 Jul 87 02:00:34 GMT X-Archive: comp.sources.misc/8707/39 Malloc Leak Trace Package by Michael Schwartz University of Washington Computer Science Department Seattle, Washington, USA schwartz@cs.washington.edu (ARPANET) schwartz%cs.washington.edu@relay.cs.net (CSNET) ...{allegra,caip,ihnp4,nike}!uw-beaver!schwartz (UUCP) April 1987 1. Description This package is designed to help trace dynamic memory allocation leaks. It works by providing the standard malloc/free/realloc interface, but at the same time keeping track of all malloc'd buffers, including their size, order of call, and address. That way, at any point during the execution of your program, you can see what malloc'd buffers haven't yet been freed. It is particularly useful when your program performs many allocations before reaching some steady state, and hence you want to ignore the initial allocations and concentrate on where steady-state leaks occur. The idea is that you have some code (usually a server) that looks as follows: initialization code; do { ... } while (1); /* main loop */ There might be some dynamic allocation during the initialization, but this isn't where the memory leak is, since it's a one-shot allocation (i.e., at worst the initialization wastes some memory, but doesn't continually leak it). There might also be some dynamic allocation in the first few iterations of the main loop, until a "steady state" is reached (e.g., until some cache gets filled). In both cases (initialization and pre-steady state iterations), there may be many allocation calls, but you don't really want to look at them; rather, you want to look at what memory isn't being free'd once steady state has been reached. This package helps you to see the state of memory allocation after steady state has been reached. Bug reports and suggestions for improvements are welcome. 2. Instructions To use this package, take your favorite malloc/free/realloc code, and change the routine names as follows: malloc -> mmalloc free -> ffree realloc -> rrealloc You'll probably also need to add the following line to the beginning of your malloc.c: char *malloc(); (because realloc still calls malloc, but malloc is no longer defined in that file). Then link the program to be leak-traced with maltrace.o, btree.o, and (your modified) malloc.o. I would have included my malloc.c, but it's the copyrighted BSD 4.3 code, and besides, there are plenty of public domain malloc's available (e.g., in volume 6 of mod.sources). To trace a leak, take the example program skeleton, and augment it as follows: extern int MalTraceEnbld; extern int MalBrkNum; initialization code; do { ... if ( steady state reached) MalTraceEnbld = 1; ... at end of first steady-state cycle: PMal(-10); /* print last 10 (say) malloc's that haven't yet been free'd */ } while (1); /* main loop */ Then compile the program with -g, and run it. At the end of the first cycle, PMal will print a list of the last 10 malloc's that haven't yet been freed. (PMal(n) will print the first n entries if n > 0, the last -n entries if n < 0, and all entries if n == 0). Note the sequence number of one of these mallocs, and then go into dbx on the program, and put a breakpoint somewhere in the initialization code, and run the program. When you hit the breakpoint, use dbx to set MalBrkNum to the number of the malloc you just noticed, and set a break in MalBreak. Then, continue the program. When the malloc call in question is reached, MalBreak will get called, breaking, and giving you a chance to examine the state of the program at the time of this (potentially leaking) malloc call. In case this call is still within the steady-state setup (it is sometimes difficult to find where the setup ends), you can use dbx to call NextMal, to set MakBrkNum to be the next traced malloc call. 2.1 Usage Details This technique is not applicable to situations where the steady state allocation behavior (i.e., order and size of malloc requests) exhibits variation, e.g., due to pseudo-randomization or interaction with other processes via non-deterministically ordered message exchanges. In such situations you can sometimes inhibit the variation during debugging (e.g., by forcing interactions to occur in the same order each time). Alternatively, you can use dbx to set MalBreakSize to be the size of the malloc request at which to have MalBreak called, to reach a breakpoint (similar to the MalBrkNum scheme described above). This can be useful when the order of mallocs isn't fixed, but a particular size keeps showing up in the list of malloc's that haven't yet been free'd. There is also a routine called UntracedFree that gets called when a free call is made on an address that was not malloc'd with tracing enabled (again, this routine is present to allow one to set dbx breakpoints for this event). This could either indicate a free call on an address that isn't malloc'd (a bug) or a free call on an address that was malloc'd with tracing disabled. You can determine if it was of the former nature by going through the standard malloc code. For example, in the BSD code, you can set the switches -DDEBUG and -DRCHECK to check for this and other types of bugs. Alternatively, you can enable tracing from the very beginning of your program, and then any time UntracedFree gets called, it indicates a free call on an addresss that isn't malloc'd. 3. Interactive Demo You can try out this package interactively by making the program 'test'. Note that if you tell it to free some memory that was not malloc'd (with MalTraceEnbld = 1), it will give you a warning and then try to free the address anyway (for the reasons explained earlier). This may or may not cause malloc/free to get into a bad state; in BSD malloc this can cause a core dump, for instance. 4. Acknoledgements, History Thanks to Richard Hellier from the University of Kent at Canterbury (rlh@ukc.UUCP) for the btree package (which I modified slightly for the current package). I probably could have implemented my trace package more efficiently than it works currently (e.g., by incorporating the linked-list and btree nodes into the malloc header nodes), but I was more into hacking something together quickly that would solve my problems than making efficient code. Besides, this code doesn't need to be efficient, since it's only plugged in during debugging. ---------------- From: allbery@ncoast.UUCP (Brandon S. Allbery) Newsgroups: comp.sources.misc Subject: malloc package with debugging Message-ID: <3268@ncoast.UUCP> Date: 21 Jul 87 01:32:07 GMT X-Archive: comp.sources.misc/8707/59 This is my malloc() debugging package. Response to my small note was rather startling, so I'm posting it. The basic idea is that malloc'ed and free'd blocks are kept in doubly-linked lists. Every time an allocation function (malloc, free, calloc, realloc, or _mallchk) is called, the lists are checked to make sure the pointers have not been overwritten and the sizes are valid. They catch the majority of malloc'ed array overflows, and print dumps on segmentation and bus errors in order to determine if a memory overwrite was involved. They aren't perfect (an interpreter or other form of full runtime checking of every assignment would be needed for that), but they're pretty good. One warning: you can't depend on a free()'d block still being available, it will sbrk() backwards if possible. It also doesn't coalesce adjacent free blocks or do other kinds of "optimum" memory management; I consider this unimportant, since this is a debugging package rather than a full replacement for malloc. It's also slower than the "real" malloc. The code is included below; it's probably heavily 68000 dependent, but I've done my best to reduce such dependencies to a miminum. -- Roy Smith, Public Health Research Institute 455 First Avenue, New York, NY 10016 {allegra,philabs,cmcl2,rutgers,hombre}!phri!roy -or- roy@alanine.phri.nyu.edu "The connector is the network" From bet@bent 10 Jun 89 23:11:06 GMT Path: aber-cs!dcl-cs!ukc!mcvax!uunet!cs.utexas.edu!rutgers!mcnc!duke!bet From: bet@bent (Bennett Todd) Newsgroups: comp.unix.wizards Subject: Re: Need debugging version of malloc()/free() Message-ID: <14721@duke.cs.duke.edu> Date: 10 Jun 89 23:11:06 GMT References: <850@pcsbst.UUCP> Sender: news@duke.cs.duke.edu Reply-To: bet@bent (Bennett Todd) Organization: Diagnostic Physics, Raddiology, DUMC Lines: 22 Posted: Sat Jun 10 19:11:06 1989 In-reply-to: jkh@pcsbst.UUCP (jkh) Status: RO My error-checking wrappers library (libbent) does this in its wrappers around malloc/free/realloc (emalloc, efree, and erealloc, respectively). I sometimes regret having done this, since as a result of this decision, the pointers handled by emalloc/efree/erealloc aren't interchangeable with malloc/free/realloc, whereas the other cookies that are passed about (file descriptors, FILE pointers, and so forth) are interchangeable between my e* wrappers and the lower level functions. On the other hand, I haven't gotten into trouble as a result of mixing yet, and the additional checking has helped me catch some evil bugs quickly. My code has emalloc over-allocate by twice the length of a header structure, which includes a magic number and the allocation length. One copy is prepended, and one appended, and the pointer to the middle space is returned. On efree and erealloc the headers and trailers are checked; on efree they are mangled in a predictable fasion, so that double freeing can be detected. This catches double freeing, freeing bogus pointers, and running off either end of the array. I use these in all my production code. Although they don't catch problems as quickly as some other more ambitious packages out there, they also don't inflict enough overhead to make me want to leave them out of production code. -Bennett bet@orion.mc.duke.edu From bartlett@decwrl.dec.com Sun Dec 10 18:14:34 1989 From: bartlett@decwrl.dec.com (Joel Bartlett) Newsgroups: comp.lang.c++ Subject: Generational, Compacting Garbage Collection for C++ Date: 8 Dec 89 16:53:38 GMT Distribution: comp.lang.c++ Organization: DEC Western Research Lab Status: RO A technical report describing a generational, compacting garbage collector for C++ is available from Digital's Western Research Lab: WRL Technical Note TN-12 Mostly-Copying Garbage Collection Picks Up Generations and C++ Joel Bartlett October 1989 The "mostly-copying" garbage collection algorithm provides a way to perform compacting garbage collection in spite of the presence of ambiguous pointers in the root set. As originally defined, each collection required almost all accessible objects to be moved. While adequate for many applications, programs that retained a large amount of storage spent a significant amount of time garbage collecting. To improve performance of these applications, a generational version of the algorithm has been designed. This note reports on this extension of the algorithm, and its application in collectors for Scheme and C++. For instructions on how to order a hard copy report or have the Postscript e-mailed to you, send a message to our technical report server at Wrl-Techreports@decwrl.dec.com with the word "help" in the subject line. jfb From bartlett@bartlett.pa.dec.com 19 Apr 90 23:13:43 GMT Path: aber-cs!gdt!dcl-cs!ukc!mcsun!sunic!uupsi!rpi!uwm.edu!ogicse!decwrl!decwrl!bartlett.pa.dec.com!bartlett From: bartlett@bartlett.pa.dec.com (Joel Bartlett) Newsgroups: comp.lang.c++,comp.lang.ada Subject: Re: garbage collection references? Message-ID: <3407@bacchus.dec.com> Date: 19 Apr 90 23:13:43 GMT References: <1990Apr18.235304.115@calgary.uucp> Sender: news@decwrl.dec.com Reply-To: bartlett@bartlett.pa.dec.com (Joel Bartlett) Organization: DEC Western Research Laboratory Lines: 13 Xref: aber-cs comp.lang.c++:5312 comp.lang.ada:2131 Status: RO Here at DEC WRL we've added a compacting, generational garbage collector to C++ and are quite happy with the resulting system. You can get technical reports explaining the work by sending a message with "help" in the subject line to wrl-techreports@decwrl.dec.com. This will give you instructions on how to get Postscript or paper copies of the reports. The ones you're interested in are: WRL Technical Note TN-12, Mostly-Copying Garbage Collection Picks Up Generations and C++ WRL Research Report 88/2, Compacting Garbage Collection with Ambiguous Roots jfb From daniel@terra.ucsc.edu Thu Jul 19 15:38:28 1990 From: daniel@terra.ucsc.edu (Daniel Edelson) Newsgroups: comp.lang.c++ Subject: Copying collection in C++ Date: 18 Jul 90 01:27:52 GMT Reply-To: daniel@terra.ucsc.edu () Organization: University of California, Santa Cruz X-Local-Date: 17 Jul 90 18:27:52 PDT Status: RO I indicated in a recent posting to this newsgroup that a technical report (ucsc-crl-90-19) describing a copying collector for C++ is available via anonymous ftp from midgard.ucsc.edu (128.114.134.15). The version of the report that does not include source code had some simple bugs that have now been corrected. If you obtained ucsc-crl-90-19-nocode.ps.Z prior to Tue Jul 17 18:22:34 PDT 1990 you should probably get it again. Thanks to Hans Boehm@xerox.com for pointing this out. daniel daniel@cis.ucsc.edu From daniel@terra Fri Jul 20 22:22:37 1990 From: daniel@terra (Daniel Edelson) Newsgroups: comp.os.research Subject: TR available: "Dynamic Storage Reclamation in C++" Date: 18 Jul 90 20:34:33 GMT Status: RO The following technical report is now available: Dynamic Storage Reclamation in C++ Daniel Edelson daniel@cis.ucsc.edu June 1990 UCSC-CRL-90-19 The report describes a copying garbage collector organization and implementation that is both efficient and philosophically consistent with the design goals of the C++ programming language. In particular, code fragments that do not use collected objects are not impacted, and, the efficiency of collecting a data structure depends solely on the complexity of the data structure, not the total size of the program. The organization does not use an ``object table'' which would add a level of indirection to all object accesses. The technical report does not propose a syntax for adding garbage collection to C++, rather it describes an organization and an algorithm. The collector is currently implemented outside of the compiler; a future version in the compiler will require changes to the language and is an area of current research. The postscript report is available via anonymous ftp from midgard.ucsc.edu (128.114.134.15). There is one version with source code and one without that is about 25 pages shorter. The files are: total 404 -rw-r--r-- 1 ftp 220779 Jul 16 18:48 ucsc-crl-90-19.ps.Z -rw-r--r-- 1 ftp 193619 Jul 16 18:48 ucsc-crl-90-19-nocode.ps.Z It is also available via US Mail from the Baskin Center for Computer Engineering and Information Science at the University of California, Santa Cruz. If you have difficult obtaining the report or comments once you have it please contact me. Daniel Edelson daniel@cis.ucsc.edu -- Piercarlo "Peter" Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk