[gclist] Guardians

[Carl Bruggeman]

> > For simple cases (probably
> > the vast majority), only the code for A needs to be inspected.  For
> > more complex cases (such as a cycle of dependencies or chains where
> > the finalizer code may be more complex) the programmer must bring
> > global semantic knowledge to the problem.
> >
> > All I am arguing is that _in some cases_ the programmer must have
> > global knowledge of the program's finalization dependencies to know
> > which pointers must be weak-for-finalization,
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Knowing what I now know about what weak-for-finalization means, this
should be amended to:
... know how to specify the finalization order for these cases.

> You're talking about a different problem to the one I was talking
> about above.  Here you are talking about what knowledge is required
> to decide which pointers _must_ be weak-for-finalization.  I am
> talking about what knowledge is required to decide which pointers
> _can_ be weak-for-finalization. 
>
> These two properties could be called completeness and soundness respectively.
> Local soundness: can I safely declare this pointer as weak-for-finalization?
> Completeness: have I declared enough pointers as weak-for-finalization
> to ensure that the topological dependencies amoung finalizers are acyclic?
> 
> Proving local soundness requires only local knowledge.
> Proving completeness requires global knowledge.

I follow you so far, but it is still not clear to me how you can get
by with only local knowledge, especially given what you say next:

> If you are careful to make pointers weak-for-finalization whenever
> possible, then the only time you will have any problems is if the
> finalization dependencies really are cyclic, at least when considered
> at the granularity of whole objects.  In that case, you're
> going to have to redesign your application to avoid the cycle,
> for example by splitting an object into two parts which can be finalized
> separately.

Here you are saying that for cycles the programmer must apply global
knowledge to break the application into parts that can be finalized
separately -- i.e., the programmer must specify the finalization order
using global knowledge.  This is precisely the point I was making: 
there are some cases (at least the cyclic cases) where the programmer
must have more than just local knowledge.  I have seen no explanations
or examples (just your assertion) that local soundness requires only
local knowledge.  Since cycles are a counterexample to this claim, it
seems to me that local soundness cannot require _only_ local
knowledge.  It may be sufficient in most cases but to get them right
sometimes requires global knowledge.  Consider the case with a
finalization chain A-B-C-D-E where the source code is modified and
introduces a cycle where E now depends on A.  Suppose further that
with this modification, the most natural point at which to break this
cycle is now at C.  How can a programmer come to this conclusion
without knowledge of all 5 objects?

> > When finalization
> > dependencies are simple enough, both approaches have simple interfaces
> > that requires little (guardians) or no (topological) work.  When the
> > programmer is in error bringing global knowledge to the problem, such
> > as breaking a cycle or chain in the wrong place with a weak pointer,
> > memory can be deallocated incorrectly (or other "dangerous" things can
> > occur) using either approach.
> 
> No, that's incorrect.  With the topological approach, if a programmer
> is incorrect in applying global knowledge, the only thing that can
> happen is failure to call finalizers and if desired a warning to the user
> that the GC detected a finalizer cycle.

I do not understand this assertion either.  Suppose that I have a
cycle of three objects A, B, and C that protect 3 external resources
a', b', and c' that must be finalized in the order a', b', c' because
the external resources will do explicit deallocation of shared
resources that will cause a memory smash if they are done in any other
order.  If the programmer breaks the cycle at B or C rather than A, a
memory error will occur because the finalization order will not be a',
b', c'.

> When is more control needed?  Can you give some convincing examples of why
> we would need this extra control?

In 100% of the production code that I have written, finalization order
has never mattered.  In the more realistic (but fabricated) examples
that I have come up with, dependency chains were easily handled by
using multiple guardians in a simple fashion.  Since we could
postulate vastly more complex examples (including cycles) and since
programmer control was not burdensome for the realistic examples we
could come up with, we chose to design and implement a feature that
gave the programmer complete control over finalization ordering and
actions.  It may well be that guardians would place too large a burden
on programmers in your application domain, but it is simply too early
to tell.  Neither you nor I have spent much time trying to find a
simpler way to use guardians to give the equivalent support that
topological finalization gives you.

I am beginning to believe that we have completely different targets
for finalization.  You apparently use finalization to deallocate C++
objects and find topological ordering very useful given the contraints
of C++ and its destroy methods, while I have viewed finalization only
as a means of managing externally allocated resources using the
collector, and thus have never had any need for topological
finalization.  You have made other tradeoffs as well, probably for
similar reasons.  You have traded off automatic timely finalization to
get the topological ordering information, requiring the programmer to
break long chains and cycles that might result in finalization that is
not timely.  Perhaps the best solution would be to find a way to
preserve topological ordering on a per-guardian basis and using
multiple guardians rather than weak-for-finalization pointer to break
cycles (there is one aspect of our collection algorithm that makes me
think this might be possible, though my first cut today was broken).


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