[Python-Dev] Cyclic GC issues

["Martin v. Löwis"]

> 1) I originally had lone rings refer to themselves (ob_refcnt started out
>    at 3; 2 self-references and one reference held by the associated edge).

I would have thought the refcount should have been 4: two self
references, plus one from E, plus one from N (maybe I don't understand
what make a ring "lone", though).

>    This didn't work.  It appears that the cyclic GC does not actually
>    calculate the number of live references to objects (references that are
>    reachable by traversing all objects accessible from the root set);

That's correct. It doesn't need to.

>    instead it assumes that if tp_clear() doesn't drop the reference count
>    to a number that equals the number of references from live objects,
>    there must still be references from live objects.  

That's also correct. tp_clear is called for objects that are not
reachable from the root set, anymore, so it *should* break all
non-reachable cycles.

>    Unfortunately,
>    visit()ing self does not work, so there is no way to convince Python
>    that all references are from unreachable objects.

Wrong. If tp_clear is called, you already know for certain that "self"
is garbage. So you need to clear all references - regardless of whether
you think you should: trust us, we know what we do.

>    Working around this in Crux requires a lot of extra reference counting
>    complexity, because there are three different cases for reference
>    counts, depending on how many members there are in a ring (1, 2, or 3+
>    members).

Why is that? Just DECREF every PyObject* in "self", then set the
PyObject* to NULL. No need for any additional reference counts.

> 2) This issue is really just a different manifestation of issue (1).
> 
>    At the C (not Python object) level, each node only actually stores a
>    pointer to a single member of the associated ring.  Given a single ring
>    member, it is possible to traverse the ring and reach all other ring
>    members.  As mentioned in issue (1), the cyclic GC expects tp_traverse()
>    to call visit() once for each reference held.  It is not enough for a
>    node to visit() one ring member; it must visit() all ring members, in
>    order for the GC to count how many references are from unreachable
>    objects, versus reachable from the root set.

Hmmm. Even if a ring member holds only a single reference to another
ring member, would not calling visit() on this member in turn invoke
visit() on the other one, which would, in turn, invoke visit() on
the next one, and so on?

>    In summary, issues (1) and (2) are due to how the cyclic GC does the
>    "marking" phase of mark/sweep GC.  My expectation of mark/sweep GC is
>    that it should be sufficient to assure that all objects reachable from
>    the root set are visit()ed at least once; it should not be important how
>    many times each unreachable object is visit()ed.

Correct. Indeed, cyclic GC makes sure visit is not called more often
than needed.

>    I don't have a deep enough understanding of the Python interpreter to
>    give a detailed suggestion for improvement.  I suspect that determining
>    the root set is not an easy operation; if this is the case, then I think
>    we're stuck with the current design.  If determining the root set *is*
>    easy (or even possible), then I would suggest using a standard
>    mark/sweep collector, where unreachable objects are scheduled for
>    destruction.

That is already the case. tp_clear is the procedure that performs the
destruction.

>    tp_traverse(), tp_clear(), and tp_dealloc() would retain
>    the same structure; the only difference would be the logic that
>    determines which objects can be destroyed.

I don't see a need for change. The logic that determines the objects
to be destroyed is already "precise", determining only unreachable
objects.

> 3) A strange thing can happen when tp_clear() is called.  Suppose that an
>    edge object is being cleared, and it drops its references to the
>    associated rings.  If ob_refcnt of one of the rings drops to 0 as a
>    result, Python will tp_dealloc() the ring *right* *now*, without ever
>    calling tp_clear() on the ring.  That means that I have to keep track of
>    whether tp_clear() has been called on objects, if it is at all important
>    that tp_clear() be called, so that I can manually do so in tp_dealloc(),
>    if necessary.  It is in my opinion reasonable to have cleanup code in
>    tp_clear(), with the assumption that it will be called precisely once,
>    but Python makes me do extra work to make sure that this happens.

Your expectation is wrong. tp_clear is not the place to perform cleanup.
It is the place to break cycles. tp_dealloc is the place to perform
cleanup.

> 4) There is no way to control the order in which objects are
>    tp_dealloc()ed.

Correct. Unfortunately, there is no way to change that. For cyclic
structures, there is no natural "starting point". Python picks an
arbitrary starting point, assuming that the order does not matter.
If class objects have an __del__, it assumes that the order does
matter, and gives up - putting the objects into gc.garbage.

>    This could be addressed in the Python interpreter by paying heed to the
>    return value of tp_dealloc().  If the return value is non-zero, move the
>    object to the end of the list of objects to be destroyed, so that
>    destruction is tried later.  This allows the module to impose its own
>    destruction ordering.

I don't understand. tp_dealloc does not have a return value, so what
does "pay heed" mean?

Regards,
Martin