[gclist] Guardians

[Carl Bruggeman]

I have been following the finalization debate here periodically, but
haven't had the time in recent weeks to contribute.

Our group at Indiana identified many of the problems discussed here
when designing a finalization mechanism for Chez Scheme a few years
ago, especially the problem finalization order (our problem analysis,
design and implementation is described in a 1993 PLDI paper available
at:  http://www-cse.uta.edu/~bruggema/papers/guardians.ps).  We
concluded, as many people on list list probably have by now, that
there is no way to automatically determine the order in which
finalization should occur because there are cases when the order is
program dependent rather than topologically dependent (assuming
finalization actions are not severely restricted, e.g., freeing
storage for an object in its destroy method in C++).  Another
important problem for collectors that execute finalizers as part of a
collection, which I haven't seen mentioned here, is that of
maintaining data structure integrity between the mutator and
finalizers.  Finalizers executed at collection time are analogous to
interrupt handlers in operating systems (since a GC can generally
occur at any point in the mutator) and any data structures shared
between the mutator and finalizer must be updated using some mechanism
that assures that both the mutator and finalizers update and examine
any shared structures atomically.  As with OS interrupts, the
easiest way to assure correct behavior is to disable interrupts (i.e. 
collections) while updating shared structures in the mutator.  Another
way that avoids critical sections in the mutator is to ensure that the
finalizer is simple enough that locking is not needed (i.e.  if there
is only one mutable field that the finalizer needs to examine it can
be updated atomically in the mutator without a critical section). 
This later mechanism is probably used more frequently than not (but
more by accident, I suspect, than by design).  I also suspect that
potential bugs are rarely, if ever, exercised in most problems because
collections are usually triggered by allocation and few program do
allocation in the middle of updating shared structures that are
examined by a finalizer. 

In order to solve these and other problems that are described in our
paper, we designed the guardian mechanism.  Guardians, among other
things, allow the programmer to specify the order in which objects
are finalized.

A thumbnail sketch of the guardian mechanism is:

1.  the program creates a guardian

2.  the program registers an object with the guardian

3.  when the collector determines that there are no strong pointers to
    an object and the object is protected by a guardian, the object is
    placed on a queue associated with the guardian

4.  periodically the program queries the guardian for objects that
    have become inaccessible and performs whatever finalization
    actions it wants for objects collected on that guardian

Since finalizer code is never executed as part of a collection, no
critical sections are necessary.  Using the OS analogy, an interrupt
simply queues up an event that is handled by a daemon process outside
of the context of an interrupt.  When finalization order is important,
the program retrieves objects from guardians, and finalizes them in
whatever order it deems necessary (it can even defer processing
objects until other related objects become inaccessible if
necessary).  Multiple guardians can be used to classify objects or
classes of objects. 

The guardian mechanism not only puts the finalization order problem in
the hands of the programmer, but also puts the "resurrection"
semantics problem in their hands as well.  Objects are never in limbo;
when no strong pointers exist, the object is simply put on the
guardian queue (or queues if it has more than one guardian).  The
program can "finalize" the object by turning it loose in the system
again if it wants.  If the object is not registered with the guardian
again, it will never be "finalized" again.  If the "finalizer" drops
its pointer to the object (without re-registering it with a guardian),
and there are no other weak pointers or other guardians with pointers
to the object, then the object is really dead and will be collected on
the next cycle. 

The important aspect of the guardian mechanism is that it put a
capability in the hands of the programmer, namely the lack of
reachability of an object from the normal GC roots, in the hands of
the programmer without restriction.  Objects can simply be dropped so
that they truely die; they can be "finalized" in some way before being
dropped; they can be "recycled" by turning them loose in the system
again.

Our paper describes a number of other related problems (i.e. 
interaction with weak pointers, interaction with generational
collectors, etc.) as well as their solutions within the guardian
framework.  The collection algorithm is straightforward and is
described in our paper.

Carl


--------------------------------------------------------------------------------
Carl Bruggeman -- bruggema@cse.uta.edu -- Phone: (817) 272-3600 Fax: 272-3784
Computer Science and Engineering Department -- University of Texas at Arlington