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<class T> 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<T>(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<T>
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 T> class gc_pointer {
class null{};
public:
gc_pointer(const T&);
| gc_pointer(const T&,void (*CleanUp)(T*));
| template<class C> gc_pointer(const T&,void (*CleanUp)(T*,gc_pointer<C>));
gc_pointer(const gc_pointer&);
| gc_pointer(const gc_array<T>&,size_t);
| template<class B> gc_pointer(const gc_pointer<B>&,const T B::*);
| template<class B> gc_pointer(const gc_array<B>&,size_t,const T B::*);
gc_pointer(null *p=0);
~gc_pointer();
| destroy();
gc_pointer& operator=(const gc_pointer&);
operator T*();
T* operator->()
template<class U> gc_pointer<U>();
| template<class D> gc_pointer<D> dyn_cast();
};
template<class T,size_t N> class gc_array {
public:
gc_array();
gc_array(void (*CleanUp)(T*));
| template<class C> gc_array(void (*CleanUp)(T*,gc_pointer<C>));
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<class B> 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.