[gclist] Guardians

[Fergus Henderson]

Carl Bruggeman, you wrote:
> 
> > > 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.

For the topological model, I wouldn't quite agree with this amended
statement.  Instead I would amend it to "... to design the program so
that it doesn't have finalization cycles".  With the topological model,
the programmer doesn't specify the finalization order, that's up to the
collector to figure out.  Global knowledge is required to ensure that
there _is_ a valid finalization order; the collector guarantees that if
there is one, it will find it.

> > 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:

It depends what you want.  If you just want to prove local soundness,
then you only need local knowledge.  If you want to prove both local
soundness and completeness, you can't get away with local only
knowledge; proving completeness requires global knowledge.
(The same is true of other properties that you might want to prove
of your programs, e.g. termination.)

> I have seen no explanations
> or examples (just your assertion) that local soundness requires only
> local knowledge.

Well, I did offer what I thought was an explanation.

Anyway here is an example.

	class Foo {
		Bar *pointer;
		void finalizer() {
			do_something();
		}
		...
	}

My argument is that you should be able to determine from the interface
specification of do_something() whether it could access the pointer.

Hmmm... on further reflection I see that my argument is not as strong
as I thought it was.

Perhaps I am overestimating what should be specified in the interface
(and certainly in practice many of the things that ought to be specified
aren't, so even if this claim is true in theory it may not be in practice).

> 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.

Hmm.  I'm not quite sure exactly what you mean here.  I presume
that some of the pointers that cause the cycle are not actually
used by the finalizers?  If so, then I argue that they should have been
declared "weak-for-finalization" in the first place.

If all the pointers involved are actually used by the finalizers,
then the programmer has introduced a real cycle (at least when you
consider things at the granularity of objects), not just an apparent
cycle.  Was that what you meant?

> Suppose further that
> with this modification, the most natural point at which to break this
> cycle is now at C.

If the cycle can be broken at C, then the pointer from C to D should have
been declared weak-for-finalization in the first place.

> > 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'.

Yes, but if that happens, the programmer has incorrectly applied local
knowledge, not just global knowledge.  Presumably such mistakes will
be easier to avoid in the first place, easier to catch in code reviews,
etc.

> > When is more control needed?  Can you give some convincing examples of why
> > we would need this extra control?
> 
> I am beginning to believe that we have completely different targets
> for finalization.  You apparently use finalization to deallocate C++
> objects

Well in fact I haven't used finalization at all ;-)
I'm arguing from a theoretical perspective, not from practical experience.
It is of course quite possible that my analysis may be missing something.

Cheers,
	Fergus.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.