Fixing guardians

[Marius Vollmer]

Michael Livshin <address@hidden> writes:

> > In your example, the port would not be returned by the port-guardian
> > as long as the cell is in the cell-guardian.
> > 
> > Is this possible?
> 
> yes, I think it is.
> 
> the smart way would be to order the "zombification" topologically, so
> that you'll get the behaviour you ask for above.

Ok, let me talk out of my *bleep* here. I haven't read the guardian
code in Guile, nor did I read any paper.  I'd like to just write down
what I have in my mind right now, maybe it makes sense.  If it doesn't
make sense, don't bother to explain it to me in great detail.  Just
tell me to RTFC.

I imagine guardians for the Guile mark/sweep collector to be
implemented like this:


A guardian has two lists: one list of `guarded' objects and one list
of `caught' objects.  The `guarded' objects are those that have been
added to the guardian and not yet moved to the `caught' list.  The
`caught' list contains those objects that will be returned when asking
the guardian for objects to finalize.

These two lists are _not_ visible to the GC, that is, objects on them
are not automatically marked.  Maintaining these lists does not
trigger the GC either.

After the mark phase of the GC:

    For every guardian:
      For every object on the `guarded' list:
        If the object is unmarked:
          Call scm_gc_mark on it.
          Unset its mark bit afterwards.

    Then, for every guardian:
      Move all unmarked objects on the `guarded' list to
      the `caught' list and set their mark bit.

Then do the sweep phase.  This may delete some guardians and we might
have superfluously marked some objects that these guardians have on
their `caught' list.  These objects will not be deleted this time, but
on the next GC pass.  I don't think it is important to avoid this
behaviour and it might be tricky to do because guardians might be
guarded themselves and thus can go from unmarked to marked during the
process above.


This process should take care of guarded objects referencing other
guarded objects and of cycles among guarded objects.  The cycle will
be broken at an arbitrary link, but that's OK.


For example, take two cons cells

    a:  ( b . #f )
    b:  ( a . b )

with a guarded by guardian A and b guarded by guardian B.  Thus:

    A guarded: a
      caught:

    B guarded: b
      caught:

Suppose both a and b are garbage.  Let us denote a set marked bit by
`+' and a cleared mark bit by `-'.  Then we have after the mark phase:

    A guarded: a-
      caught:

    B guarded: b-
      caught:

In the first guardian phase, we process first A, then B.  Thus, we
first check a, and see that it is unmarked.  We call scm_gc_mark on it
and reset its mark bit, leading to:

    A guarded: a-
      caught:

    B guarded: b+
      caught:

Then we check b, and see that it is marked.  We do nothing.

In the second guardian phase, we move a to the caught list and set its
mark bit.  We don't touch b.

    A guarded:
      caught:  a+

    B guarded: b+
      caught:

Thus, we have `caught' a but not b, which is right.


Ok, what's wrong with this simple algorithm?