Source

pypy-effect-analysis / pypy / doc / discussion / finalizer-order.txt

Full commit
Ordering finalizers in the SemiSpace GC
=======================================

Goal
----

After a collection, the SemiSpace GC should call the finalizers on
*some* of the objects that have one and that have become unreachable.
Basically, if there is a reference chain from an object a to an object b
then it should not call the finalizer for b immediately, but just keep b
alive and try again to call its finalizer after the next collection.

This basic idea fails when there are cycles.  It's not a good idea to
keep the objects alive forever or to never call any of the finalizers.
The model we came up with is that in this case, we could just call the
finalizer of one of the objects in the cycle -- but only, of course, if
there are no other objects outside the cycle that has a finalizer and a
reference to the cycle.

More precisely, given the graph of references between objects::

    for each strongly connected component C of the graph:
        if C has at least one object with a finalizer:
            if there is no object outside C which has a finalizer and
            indirectly references the objects in C:
                mark one of the objects of C that has a finalizer
                copy C and all objects it references to the new space

    for each marked object:
        detach the finalizer (so that it's not called more than once)
        call the finalizer

Algorithm
---------

During deal_with_objects_with_finalizers(), each object x can be in 4
possible states::

    state[x] == 0:  unreachable
    state[x] == 1:  (temporary state, see below)
    state[x] == 2:  reachable from any finalizer
    state[x] == 3:  alive

Initially, objects are in state 0 or 3 depending on whether they have
been copied or not by the regular sweep done just before.  The invariant
is that if there is a reference from x to y, then state[y] >= state[x].

The state 2 is used for objects that are reachable from a finalizer but
that may be in the same strongly connected component than the finalizer.
The state of these objects goes to 3 when we prove that they can be
reached from a finalizer which is definitely not in the same strongly
connected component.  Finalizers on objects with state 3 must not be
called.

Let closure(x) be the list of objects reachable from x, including x
itself.  Pseudo-code (high-level) to get the list of marked objects::

    marked = []
    for x in objects_with_finalizers:
        if state[x] != 0:
            continue
        marked.append(x)
        for y in closure(x):
            if state[y] == 0:
                state[y] = 2
            elif state[y] == 2:
                state[y] = 3
    for x in marked:
        assert state[x] >= 2
        if state[x] != 2:
            marked.remove(x)

This does the right thing independently on the order in which the
objects_with_finalizers are enumerated.  First assume that [x1, .., xn]
are all in the same unreachable strongly connected component; no object
with finalizer references this strongly connected component from
outside.  Then:

* when x1 is processed, state[x1] == .. == state[xn] == 0 independently
  of whatever else we did before.  So x1 gets marked and we set
  state[x1] = .. = state[xn] = 2.

* when x2, ... xn are processed, their state is != 0 so we do nothing.

* in the final loop, only x1 is marked and state[x1] == 2 so it stays
  marked.

Now, let's assume that x1 and x2 are not in the same strongly connected
component and there is a reference path from x1 to x2.  Then:

* if x1 is enumerated before x2, then x2 is in closure(x1) and so its
  state gets at least >= 2 when we process x1.  When we process x2 later
  we just skip it ("continue" line) and so it doesn't get marked.

* if x2 is enumerated before x1, then when we process x2 we mark it and
  set its state to >= 2 (before x2 is in closure(x2)), and then when we
  process x1 we set state[x2] == 3.  So in the final loop x2 gets
  removed from the "marked" list.

I think that it proves that the algorithm is doing what we want.

The next step is to remove the use of closure() in the algorithm in such
a way that the new algorithm has a reasonable performance -- linear in
the number of objects whose state it manipulates::

    marked = []
    for x in objects_with_finalizers:
        if state[x] != 0:
            continue
        marked.append(x)
        recursing on the objects y starting from x:
            if state[y] == 0:
                state[y] = 1
                follow y's children recursively
            elif state[y] == 2:
                state[y] = 3
                follow y's children recursively
            else:
                don't need to recurse inside y
        recursing on the objects y starting from x:
            if state[y] == 1:
                state[y] = 2
                follow y's children recursively
            else:
                don't need to recurse inside y
    for x in marked:
        assert state[x] >= 2
        if state[x] != 2:
            marked.remove(x)

In this algorithm we follow the children of each object at most 3 times,
when the state of the object changes from 0 to 1 to 2 to 3.  In a visit
that doesn't change the state of an object, we don't follow its children
recursively.

In practice, in the SemiSpace, Generation and Hybrid GCs, we can encode
the 4 states with a single extra bit in the header:

      =====  =============  ========  ====================
      state  is_forwarded?  bit set?  bit set in the copy?
      =====  =============  ========  ====================
        0      no             no        n/a
        1      no             yes       n/a
        2      yes            yes       yes
        3      yes          whatever    no
      =====  =============  ========  ====================

So the loop above that does the transition from state 1 to state 2 is
really just a copy(x) followed by scan_copied().  We must also clear the
bit in the copy at the end, to clean up before the next collection
(which means recursively bumping the state from 2 to 3 in the final
loop).

In the MiniMark GC, the objects don't move (apart from when they are
copied out of the nursery), but we use the flag GCFLAG_VISITED to mark
objects that survive, so we can also have a single extra bit for
finalizers:

      =====  ==============  ============================
      state  GCFLAG_VISITED  GCFLAG_FINALIZATION_ORDERING
      =====  ==============  ============================
        0        no              no
        1        no              yes
        2        yes             yes
        3        yes             no
      =====  ==============  ============================