[gclist] Guardians

[Carl Bruggeman]

--------
> > The only case where it might be more work is when the
> > programmer does want to do finalization in a particular.  This case is
> > trivial in the topological finalization model because you always get
> > topological ordering, which either works or doesn't work.
> I think this is the heart of the disagreement.  Topological ordering
> relies on the assumption that if something is accessible from the finalizer, 
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> it may be referenced, and thus should be preserved, i.e. not finalized.  A
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This may indeed be a significant part of the problem.  In our system,
a pointer chain of guardian protected objects (even a circular chain)
that becomes inaccessible will have all of its protected objects
placed on their respective guardian queues during the same collection.

> > I generally favor
> > erring on the side of putting power in the hands of programmers rather
> > than tying their hands to save them from themselves.
> So do I, up to a point.  I haven't been convinced that being able to see
> post-finalized objects (without finalizer cooperation to make them accessible
> again) is any more of a useful feature than being able to look at deallocated
> storage, which I could generally do without.  If the finalizer deallocates
> malloc'ed objects, they are THE SAME.

Ah, another part of the problem.  Guardians do not provide
"finalization".  They provide some useful information from the
collector, which can among other things be used to implement
finalization.  When an object is placed on a guardian queue (or
queues) during a collection, the collector is informing the program
that that the object registered with the guardian became inaccessible,
except via a guardian pointer(s), during the collection.  After all
guardian protected objects are placed on their respective queues, all
of the objects reachable from these objects are traced and copied. 
Thus guarded objects and all objects reachable from them are "normal"
after being placed on a guardian queue and guardians can implement any
type of service, not just finalization; there are no restrictions on
what can be done with objects retrieved from a guardian; the object
becomes inaccessible (and its storage is reclaimed) only when there is
no strong pointer or guardian pointer to the object.

> The default behavior should be to err on the side of safety.  In the presence
> of topologically ordered finalization, you (on rare occasions) do need a
> mechanism that corresponds to explicitly clearing pointers.  That allows you 
to
> use other orderings when you have to.  (In the version implemented in our

I believe that this confirms that topological ordering is not always
the correct order.  You explicitly clear pointers to change the order
of finalization (requiring global knowledge of the dependencies on the
part of the programmer to do so), while we advocate using multiple
guardian queues to handle finalization dependencies. 

> > Using guardians I would simply register type A objects with one guardian
> > and type B objects with another guardian, and always finalize all objects
> > on the type A guardian before finalizing objects on a type B guardian.
> > The information is not global; it can be limited to the implementation of
> > the A and B types.
> Yes, but A and B may have been written by different people.  The implementor 
of
> A (some random user) shouldn't need to know about the implementation of B
> (strings).  In fact B may refer to C, which refers to D, which requires
> finalization.  The necessary information is global.  Equivalently, you have
> to widen interface definitions to mention finalization constraints.  (This may

Its not global. A and B interact, B and C interact, and C and D interact.
A does not need to know about C and D.

> I also don't quire understand how your solution would work.  The type B
> finalization can trigger another collection, enqueuing more type A and B
> objects.  The newly enqueued type B objects will then be finalized before
> theire corresponding type A objects.

I don't understand your misunderstanding...  Perhaps you didn't
realize that there are separate queues for A types and B types, and
that any A-B chains or cycles will be placed on their queues during
the same collection.  Also, you can't blindly go through the entire B
queue; after each B you recheck the A queue.  This is a good example
of the flexibility you get with guardians -- its all under programmer
control.

BTW, how do you handle finalization cycles?  Is that where you need
pointer clearing?  If so, what happen if the programmer doesn't break
the cycle by clearing pointers correctly?  Infinite loop?

> You also seem to be relying on the fact that a type B object will not be foun
d
> inaccessible before its corresponding type A object.  Since A points to B,
> that's often true.  I'm not convinced it's true for our garbage collector.  I
> can certainly contrive collectors for which it's false.

I think I missed something here again.  This seems to be an assumption
for both of our collector.

> > You appear most concerned with C++ applications where the collector's
> > topological ordering is _one_ correct finalization order and you wish
> > to preserve and utilize this ordering information that the collector
> > derives.  I (and perhaps a few others) believe that topological
> > ordering is too restrictive for general purpose finalization and that
> > other correct finalization orders are simple enough to derive and
> > implement without being an undue burden on the programmer.
> 
> This is the claim I don't understand.  And I still haven't found an example.

There are examples in our paper.

> There are millions of lines of code written with topologically ordered
> finalization.  The only known deficiency is that you would on rare occasion
> like to ignore some pointers for finalization ordering.

Exactly!  Any of your applications where you had to explicitly clear
pointers because the topological order was not correct is a supporting
datum for our claim that topological ordering is not always desirable
and that some sort of user control is necessary (for you pointer
clearing; for us guardians).  Which is more "dangerous" or relies on
more "global" information is, to a large extent, a matter of taste.


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