ANSI X3J16/94-0141, ISO WG21/N0528 Finalization Semantics for C++ Garbage Collection Gregory Colvin Information Management Research gregor@netcom.com This paper examines options for the finalization of objects allocated by the gc_pointer and gc_array templates, including a simple reference counting alternative, and recommends possible additions to the smart pointer interfaces given in ANSI X3J16/94-0097, ISO WG21/N0484. Finalization and Garbage Collection In the C++ expression delete p the object of type T pointed to by p is first destroyed by calling p->~T(), then the memory occupied by the object is released by calling operator delete(p). The destruction of the object is also known as clean-up or finalization, and is a distinct operation from the release of memory, even though they are ordinarily accomplished together. Garbage collected memory is released by the collector when objects are found to be unreachable. There are several issues of finalization semantics to resolve. 1. When an object is found to be unreachable by the collector should the object be finalized? 2. If so, then how should it be finalized? 3. If so, then when should it be finalized? In my original proposal I answered these questions as follows. 1. Yes, it should always be finalized. 2. By calling the destructor. 3. Almost anytime. Specifically, during any call to any library function, or at the end of any scope. I now think that these answers are not the best choices. Should garbage collected objects be finalized? Some languages with garbage collection have no support for finalization. When an object is found to be unreachable its memory is simply released. This is quite workable when an object amounts to nothing more than pointers to other garbage collected objects. However, objects which represent resources outside the program will typically require finalization. Either the user must be given a means of finalizing such objects, or they must be handled by the language itself. C++ programs must explicitly manage many resources, such as memory, file handles, record locks, semaphores, window handles and so on. Thus many C++ objects may require finalization. A garbage collection facility for C++ which did not provide finalization would severely restrict the range of C++ objects which could be garbage collected. Therefore garbage collected objects should be finalized before their memory is released. However, not all C++ objects need finalization, and for some collector implementations registering clean-up functions can be expensive. Thus finalization should optional. How should a garbage collected object be finalized? The normal means of finalizing a C++ object is to call its destructor. Thus the obvious answer to the above question is "by calling its destructor". The problem with this answer is that destructors for objects not originally designed for garbage collection may have preconditions that the garbage collector cannot meet. Thus it should be possible for the programmer to provide a separate clean-up function, which can call the destructor if that is appropriate. The STL function template template void destroy(T* p) { p->~T(); } might be useful in this regard. When should a garbage collected object be finalized? >From the collector's point of view the best answer might be "whenever I want", but this provides no control to the programmer, and in multithreaded programs can make writing clean-up functions difficult. Another answer might be "when the programmer says so", but this places a perhaps unnecessary burden on the programmer. John Ellis (personal communication) recommends the finalization queue technique specified in Ellis and Detlefs (1994), which has the collector put each otherwise unreachable object, together with its clean-up function, on one of several finalization queues managed by the programmer. This scheme provides a good balance of collector automation and programmer control, and would be well worth proposing in the future. My own preference is for the collector to finalize the object, but the constraints on the collector in my original proposal have proven too weak to be useful. I propose now to strengthen these constraints by allowing the collector to call clean-up functions only during calls to the default new-handler or when explicitly requested to do so by the function gc_collect(). This scheme can be implemented as a special case of Ellis' scheme. Both of these schemes allow the collector to run mostly asynchronously: it is only the calls to the clean-up functions which must be synchronous. An additional useful facility, which I remain hesitant to recommend, is to let the programmer explicitly finalize an object which has not yet been collected. This is obviously unsafe, and if allowed should be treated as only a hint to the collector. Finalization and Reachability. John Ellis (personal communication) gives two possible definitions of reachability. The weaker definition is as follows: An object is reachable if it can be accessed by zero or more applications of gc_pointer::operator->() starting from a root smart pointer. A smart pointer is a root if it is stored in a local or static variable or if it is contained in a non-garbage- collected heap object. A stronger definition is: An object is reachable if it can be accessed by zero or more applications of gc_pointer::operator->() starting at local or static objects, non-collected heap objects, or some collected object with a non-null finalization procedure (including the object itself). An object with a finalization procedure that is in a cycle of smart pointers will never be collected. The stronger definition requires only a reference counting implementation when all objects have a clean-up function, and guarantees that smart pointers contained within an object will not be dangling during a call to its clean-up function. For a safe global collection facility like Ellis and Detlefs (1994) propose this is an important guarantee, although the price of unreclaimed cycles seems to me rather steep. The Boehm and Demers (1994) collector provides for special "disappearing links" to allow for reclaimable cycles, and I suspect that some such facility will be needed for the Ellis and Detlefs proposal as well. For smart pointers I prefer the weaker definition. The rule that smart pointers contained in an object should not be dereferenced during a call to the object's clean-up function is then just a special case of the general rule for smart pointer safety: A garbage-collected object should not be accessed after it has become unreachable, except during its clean-up function. Odds and Ends It may be worthwhile to add dynamic casts and interior pointers to the gc_pointer interface. I would prefer to add dynamic casts by making dynamic_cast an overloadable operator. If that is not feasible a member template may be added to gc_pointer. An interior pointer is a pointer into a garbage collected object. I recommend a template constructor that takes a reference to a smart pointer and a pointer to a member as a type-safe interface. A concern with the current interface is the overhead of creating and copying a temporary T when constructing with gc_pointer(const T&). Although compilers should be able to optimize away the temporary, a possible work around is to provide a T* constructor for gc_pointer and a placement new operator for explicitly allocating and constructing garbage collected objects. I will not recommend this unsafe interface unless vendors indicate that they will not be able to optimize away the temporary. Revised Interfaces The interfaces to gc_pointer and gc_array require some additions (marked with |) to implement the above recommendations: template class gc_pointer { class null{}; public: gc_pointer(const T&); | gc_pointer(const T&,void (*CleanUp)(T*)); | template gc_pointer(const T&,void (*CleanUp)(T*,gc_pointer)); gc_pointer(const gc_pointer&); | gc_pointer(const gc_array&,size_t); | template gc_pointer(const gc_pointer&,const T B::*); | template gc_pointer(const gc_array&,size_t,const T B::*); gc_pointer(null *p=0); ~gc_pointer(); | destroy(); gc_pointer& operator=(const gc_pointer&); operator T*(); T* operator->() template gc_pointer(); | template gc_pointer dyn_cast(); }; template class gc_array { public: gc_array(); gc_array(void (*CleanUp)(T*)); | template gc_array(void (*CleanUp)(T*,gc_pointer)); gc_array(const gc_array&); ~gc_array(); | destroy(); gc_array& operator=(const gc_array&); operator T*(); T& operator[](size_t); }; | bool gc_collect(); Semantics for the Revised Interfaces If a non-null CleanUp function is provided for an object it will be called by the collector before it releases that object's memory: the default clean-up function is the object's destructor. The collector may call clean-up functions only during calls to destroy(), gc_collect() or to the default new-handler. The destroy() function may call the clean-up function (if any) and release the memory for the object released: the result of accessing the object again is undefined. The gc_collect() function calls the clean-up function (if any) and releases the memory for one or more of the currently unreachable objects; it returns false if no memory is released, and returns true otherwise. The default new-handler calls the clean-up function (if any) and releases the memory for one or more of the currently unreachable objects; it throws an alloc exception if no memory is released, and returns normally otherwise. The gc_array constructor and the two template constructors for gc_pointer are used to create interior smart pointers, initialized to point to an array element, member, or member of array element of a garbage collected object. An Alternative Semantics: Reference Counting At Waterloo we decided not to recommend adding a garbage-collected smart pointer to our Library, in part because of possible conflicts with the Ellis and Detlefs extension. There was understandable reluctance to mandate a library facility that might require nearly as much work for vendors as a language extension without providing nearly as much benefit to users. However, the problems of safe pointer usage that smart pointers can solve remain on the table. John Ellis (personal communication) has suggested that a reference counted smart pointer would be a simpler and more acceptable alternative. To allow for a reference counting implementation we need only allow cycles of smart pointers to go uncollected, and allow clean-up functions to be called immediately when a garbage collected object is found to be unreachable (i.e. during the destruction of the last smart pointer to that object). But merely allowing for reference counting does not eliminate the complexities of clean-up registration and reachability semantics. If we require reference counting semantics we can answer our three original questions quite simply: 1. A collected object should always be finalized. 2. By calling its destructor. 3. During the destruction of the last smart pointer to that object. Thus we will not need a modified new-handler, the gc_collect() function, the CleanUp function, or clean-up queues, and we will insure that collected objects are destroyed in reverse order of reachability. We would indeed achieve a considerable simplification of finalization semantics, at the cost of unreclaimable cycles and some unavoidable performance overhead. References 1. Boehm , H.J. and Demers, A.J. GC Version 4.1. Xerox Corporation, 1994. 2. Colvin, G.A. Smart pointer templates for garbage collection. ANSI X3J16/94-0097, ISO WG21/N0484 3. Ellis, J.R. and Detlefs, D.L. Safe, efficient garbage collection for C++. In Proceedings of the 1994 Usenix C++ Conference.