Hans-J. Boehm

Deterministic Destruction can be a Bug

Standard tracing garbage collectors cannot invoke user-written ``destructors'' at the precise point at which an object becomes inaccessible. Instead they typically provide for asynchronous ``finalizers'', which are invoked when the garbage collector happens to notice that the object is no longer accessible. In correct implementations, these finalizers are run completely asynchronously from the user's code, in their own thread. It will become clear below why this is essential.

It has often been claimed that this is an essential disadvantage of tracing collectors, relative to something like a simple reference-count collector, which can be used to run a destructor at a theoretically well-defined program point. Here we argue that the opposite is in fact the case: For a number of more complex applications, asynchronously run finalizers are essential. If we wanted to use a simple reference counter, we would in fact have to add a queue and a separate thread to force them to run asynchronously.

Disclaimers

There are many cases in which timing of C++ destructors is essential, and it must be deterministic. But in my experience, in these cases destruction also, almost by definition, occurs at well-defined program points. It is thus fairly easy to invoke the right actions either as destructors associated with non-heap-allocated objects, or with explicit calls. We are not concerned with these here.

This note is concerned with destructors associated with heap objects whose lifetime does not end at a well-understood program point. This typically happens because the heap object is shared by multiple data structures, and it is not apparent which one will have the longest lifetime, or because the object is shared between threads, and it is unclear, and possibly timing dependent, which thread will keep the last reference. In short, it is concerned with the kind of objects that would normally have to be managed through a tracing collector or reference counting.

It seems to be very rare that an object's lifetime does not end at a single well-defined program point, but it is important for a destructor to be run exactly when the object becomes inaccessible. If such an example exists, that would argue that we may need both synchronous and asynchronous finalizers. (Note that even if file descriptors are in short supply, destructors which close files usually don't constitute an example. Usually the vast majority of files can easily be closed explicitly. Even for the remainder, it only matters that the file descriptor is reclaimed soon enough to prevent subsequent file opens from failing, e.g. by invoking the tracing collector when a file is opened, but no descriptors are available.)

In many cases, the arguments presented here are not directly applicable, since most finalizers are trivial, and their timing is completely irrelevant. Either synchronous or asynchronous finalization is fine. However future additions to the code may break a synchronous finalization scheme.

An Example

We present a fairly specific example of a case in which asynchronous finalization is essential. Note that this is inherently a bit involved. Simple programs can generally deallocate objects at easily determinable program points, and hence are not relevant. Even somewhat more involved programs often don't need to deallocate anything other than the programs own memory via reference counting or garbage collection, and hence are still not interesting.

To make it more easier to follow, the example is more specific than it needs to be. In general, this problem occurs whenever:

The programmer doesn't want to consider the particular point at which a finalizer/destructor is executed.
The finalizer/destructor updates a global data structure, and hence needs to acquire a lock that may be held by user code.

We assume that our application is multithreaded, but needs to invoke a thread-unsafe legacy library L. We use suitably defined lock() and unlock() operations to ensure that there is only one user of L at a time.

We assume that L's interface includes the following:

new_X() allocates and returns a pointer to an X. Xs are allocated in explicitly managed memory, but consume no other significant system resources. To avoid a memory leak, they must be explicitly deallocated.
delete_X(...) deallocates an X.
setup_for_f(...) sets up some global state for a subsequent f operation. It may return some interesting information which user may have to process before making the following f(...) call.
f(...) does something important that depends on the preceding setup_for_f(...) call. No other calls on L may be made between setup_for_f(...) and f(...). In particular, Xs may not be deallocated between the two.

(This is admittedly a horrible interface design. But I did say this was a legacy library.)

In this application, some Xs are refenced only by Ys, which are a part of a complicated shared data structures managed by the garbage collector. Xs are deallocated by Ys finalizer. The code in the finalizer must look like

lock();
delete_X(...);
unlock();

to avoid conflicts with the client code which we asssume looks like:

lock();
setup_for_f(...);
// Processing of setup_for_Y(...) results, preparing for call
    ...
    w = v;	// Pointer assignment.  w points to a data structure
		// that somewhere deep inside it includes a Y.
    ...
f(...);
unlock();

The programmer has decided to abstract away the point at which a particular X is deallocated. It doesn't matter for program correctness, and it only matters slightly for resource consumption.

Now assume that the

w = v;

assignment makes a particular Y inaccessible, since the data structure that w originally pointed to included it, but the new one doesn't.

With asynchronous finalization, we're fine. The inaccessibility of the object will be noted. If that happens after the lock is released, we have no problem. If it happens before the lock is released, and the finalizer is run in another thread, it will simply wait until the thread that executed the assignment releases the lock.

With synchronous finalization, e.g. with a C++ destructor invoked from a simple reference counting scheme, this breaks. The thread executing the assignment will, in a way that the programmer almost certainly failed to predict, invoke the finalizer immediately between the setup_for_f and f calls. If locks can be reacquired by the same thread, this will proceed to do the wrong thing. If they can't, it will deadlock, as the thread tries to reacquire the lock it already holds.

Conclusion

If finalizers are invoked synchronously, the programmer must either

Design finalizers so that they do not need to acquire locks, and never need to wait for anything. This usually means they can't update global user-visible data structures, and they are effectively limited to releasing system resources (whose locks can't be held when a pointer assignment is executed). Or
Prove that the lock needed by a finalizer is never held during a pointer assignment or scope exit which might cause the finalizer to become invoked.

The former is often true, even by accident, in simpler software systems. But there often seem to be reasons to violate the rule in more complex systems.

The latter appears to be impractical for complex systems. Whether or not a particular assignment can cause a particular kind of object to be dropped is a global property of the system, which cannot be determined by looking at a single component. Pointer assignments are ubiquitous and often hidden inside opaque abstractions.

Some early Java implementations ran finalizers in the client thread triggering the garbage collection, instead of in a separate thread. This can cause exactly the same problems as synchronous finalization. It was never allowed by the Java language specification.

Properly implemented asynchronous finalization avoids these issues.