Re: link references (Re: _foreach vs _forall ...)

[Marius Vollmer <mvo zagadka ping de>]

Tim Janik <timj@gtk.org> writes:

> On 5 Sep 1998, Marius Vollmer wrote:
> 
> > errm, can I take this opportunity to introduce the `reference tracing'
> > feature I want to have?
> 
> hm, i wasn't really aware of you wanting to have that implemented,
> did you mention that earlier and i missed it?

No, I said this before but not as a feature request.  I planned to do
this myself but now I saw your forall effort and I thought about
introducing my stuff alongside with it, because people will have to
rethink their forall handlers anyway.

> > Basically, I want to have a way to enumerate absolutely all GtkObjects
> > that are referenced by a certain other GtkObject, that is all
> > GtkObjects that the other GtkObject has called gtk_object_ref for.
> > 
> > This is very useful for language bindings that have a tracing garbage
> > collector (like Guile).  With this reference tracing function, the
> > garbage collector can detect cycles of unused objects.
> 
> hm, do you really encounter such behaviour in gtk?
> i know such references are possible, but does gtk really introduce them?

Gtk is not to blame for these cycles.  The refcounting scheme in Gtk
can not handle cycles of references and thus there shouldn't be any.
However, it is easy to introduce cycles from Scheme, for example.  The
Scheme GC *can* handle cycles and thus there are any number of them in
the typical Scheme implementation.  When such a cycle is formed partly
from Scheme objects and partly from GtkObjects, this becomes a
problem.

Such a cycle can for example be formed like this:

    (let ((f (gtk-frame-new #f))
          (b (gtk-button-new-with-label "Close")))
      (gtk-container-add f b)
      (gtk-signal-connect b "clicked" (lambda () (gtk-widget-destroy f))))

Here we have a frame F with a child B.  B has a handler which
includes F in its environment.  Thus, F holds on to B via a Gtk
refcount, and B holds on to F via a Scheme reference in the handler
for "clicked".

[ There are some subtle points with GtkObjects and proxies and that
  kind of stuff, but we don't really need to look closer here.  A
  GtkObject and its proxy object for Scheme are very tightly connected
  so that we can treat them as one.  One way to break the cycle above
  would be to *not* couple the GtkObject and the proxy so firmly, but
  we came to the conclusion that has other more serious drawbacks. ]

That cycle makes the two GtkObjects (and the connected Scheme objects)
leak.  Nobody will ever destroy one of them because they have not been
shown, and no other code knows about them.  This looks like a coding
error, but can actually arise in perfectly normal code because of
non-local control flow (exceptions).

> i think we should keep _forall() as an iterator for gtkcontainer that
> will walk a container's children list, as it is actually part of the
> parent<->child relationship concept which is only available for widgets.

Yes, I tend to agree.

> also, you wouldn't get the desired effect by using GtkContainer::forall,
> because we keep the reference count for parent<->child relations on
> the children, not on the parents.

Whoops, really?  Look at this code

    void
    gtk_widget_set_parent (GtkWidget *widget,
			   GtkWidget *parent)
    {
      ...
      gtk_widget_ref (widget);
      gtk_object_sink (GTK_OBJECT (widget));
      widget->parent = parent;
      ...
    }

> so rather than having the children presented through the parents
> _forall method, you'd have the parents presented in the children's
> _forall methods.

I think you got this wrong.  The parent holds references to its
children.
 
> we need a different approach for GtkObject based reference tracing, and
> i don't even think we need a class method at all.
> for the implementation side, i'd suggest something like (function names
> are arguable as always, maybe you find better ones):

I don't think we need this at all.  All I need is a way to iterate
over the GtkObjects that a certain GtkObject has outstanding
references to.  That can be done by a function like
gtk_container_foreach (and in fact, I'm using that as a first
approximation), and it wouldn't impose any overhead when it is not
used.

> so far for the suggestion. marius, can you extend on the use of
> these link references? afaik, the only advantage it gives you is
> that you can detect circular references on objects [...]

Here is how the cycle detection works for a mark/sweep tracing
collector like that of Guile:

At GC time, the world is conceptionally frozen, that is, while the GC
is running, the references maintained by gtk_object_ref/unref do not
change.

The set of GtkObjects is (conceptually) divided into two subsets:
internal and external.  An internal GtkObject is one that has an
associated Scheme proxy (that is, there are possibly references to it
from other Scheme objects, and thus might be part of a cycle).
External GtkObjects are the rest.

Likewise, the set of references between GtkObjects is divided into two
subsets: internal and external.  An internal reference is a reference
from one internal GtkObject to another internal GtkObject.  External
references are the rest.

All internal GtkObjects are known (because the guile-gtk bindings keep
book about them) and the job is now to find the number of internal
references to each internal GtkObject.  When there are only internal
references to a GtkObject and no Scheme references to the proxy of
that GtkObject or to any other proxy of a GtkObject that is
responsible for one of the internal references to the before-mentioned
GtkObject, then that GtkObject is garbage and its proxy can be
released.  Because this proxy is released--and because all other
proxys that are responsible for the internal references are released
also--the GtkObject looses all its refcounts is freed.

For the example from above, we have this situation:

       ............................
       :                          :
       v                          :
    proxy of F ---> F (1)         :
              <.... |             :
                    |             :
                    v             :
    proxy of B ---> B (2)         :
              <.....#             :
                    #######> handler for "clicked" 

The number is parens are the refcounts of the widgets.  "---" is a
reference maintained by gtk_object_ref/unref, "..." is a Scheme
reference maintained by the Guile's mark/sweep collector, and "###" is
the the connection of signals handlers to widgets.

Now, suppose there no other references to the proxies or the widgets.
F ans B are both internal GtkObjects and all "---" references are
internal references.

The algorithm proceeds like this: during the mark phase, no proxy is
marked and the internal references are counted by using the trace_refs
method I want to have.  F has zero internal references, and B has one
(from F).  Then, for all internal GtkObjects, we mark the proxies of
those GtkObjects that have a refcount that is greater than the
internal refcount+1 (the +1 comes from the proxy itself).  Neither F
nor B fulfill this condition, so no proxy is marked in this phase.

Then, during sweep, both proxies get collected, they release their
refcounts, F gets finalized, F releases its refcount on B and B gets
finalized, too.

When we find an GtkObject that a refcount greater than the internal
refcount+1, we mark its proxy.  Marking a proxy involves marking all
proxies of the GtkObjects that are referenced by the internal
references.

Right now, I'm using gtk_container_foreach to enumerate all references
from one GtkObject to another and this would already be enough for the
case above.  But to be generally correct, I need a method that is
guaranteed to find absolutely all references.