Ordering finalizers in the MiniMark GC

RPython interface

In RPython programs like PyPy, we need a fine-grained method of controlling the RPython- as well as the app-level __del__(). To make it possible, the RPython interface is now the following one (from May 2016):

• RPython objects can have __del__(). These are called immediately by the GC when the last reference to the object goes away, like in CPython. However, the long-term goal is that all __del__() methods should only contain simple enough code. If they do, we call them “destructors”. They can’t use operations that would resurrect the object, for example. Use the decorator @rgc.must_be_light_finalizer to ensure they are destructors.

• RPython-level __del__() that are not passing the destructor test are supported for backward compatibility, but deprecated. The rest of this document assumes that __del__() are all destructors.

• For any more advanced usage — in particular for any app-level object with a __del__ — we don’t use the RPython-level __del__() method. Instead we use rgc.FinalizerController.register_finalizer(). This allows us to attach a finalizer method to the object, giving more control over the ordering than just an RPython __del__().

We try to consistently call __del__() a destructor, to distinguish it from a finalizer. A finalizer runs earlier, and in topological order; care must be taken that the object might still be reachable at this point if we’re clever enough. A destructor on the other hand runs last; nothing can be done with the object any more, and the GC frees it immediately.

Destructors

A destructor is an RPython __del__() method that is called directly by the GC when it is about to free the memory. Intended for objects that just need to free an extra block of raw memory.

There are restrictions on the kind of code you can put in __del__(), including all other functions called by it. These restrictions are checked. In particular you cannot access fields containing GC objects. Right now you can’t call any external C function either.

Destructors are called precisely when the GC frees the memory of the object. As long as the object exists (even in some finalizer queue or anywhere), its destructor is not called.

Register_finalizer

The interface for full finalizers is made with PyPy in mind, but should be generally useful.

The idea is that you subclass the rgc.FinalizerQueue class:

• You must give a class-level attribute base_class, which is the base class of all instances with a finalizer. (If you need finalizers on several unrelated classes, you need several unrelated FinalizerQueue subclasses.)

• You override the finalizer_trigger() method; see below.

Then you create one global (or space-specific) instance of this subclass; call it fin. At runtime, you call fin.register_finalizer(obj) for every instance obj that needs a finalizer. Each obj must be an instance of fin.base_class, but not every such instance needs to have a finalizer registered; typically we try to register a finalizer on as few objects as possible (e.g. only if it is an object which has an app-level __del__() method).

After a major collection, the GC finds all objects obj on which a finalizer was registered and which are unreachable, and mark them as reachable again, as well as all objects they depend on. It then picks a topological ordering (breaking cycles randomly, if any) and enqueues the objects and their registered finalizer functions in that order, in a queue specific to the prebuilt fin instance. Finally, when the major collection is done, it calls fin.finalizer_trigger().

This method finalizer_trigger() can either do some work directly, or delay it to be done later (e.g. between two bytecodes). If it does work directly, note that it cannot (directly or indirectly) cause the GIL to be released.

To find the queued items, call fin.next_dead() repeatedly. It returns the next queued item, or None when the queue is empty.

In theory, it would kind of work if you cumulate several different FinalizerQueue instances for objects of the same class, and (always in theory) the same obj could be registered several times in the same queue, or in several queues. This is not tested though. For now the untranslated emulation does not support registering the same object several times.

Note that the Boehm garbage collector, used in rpython -O0, completely ignores register_finalizer().

Ordering of finalizers

After a collection, the MiniMark 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.

(Note that this creates rare but annoying issues as soon as the program creates chains of objects with finalizers more quickly than the rate at which major collections go (which is very slow). In August 2013 we tried instead to call all finalizers of all objects found unreachable at a major collection. That branch, gc-del, was never merged. It is still unclear what the real consequences would be on programs in the wild.)

The basic idea fails in the presence of 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 MiniMark GCs, we can encode the 4 states with a combination of two bits in the header:

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

So the loop above that does the transition from state 1 to state 2 is really just a recursive visit. We must also clear the FINALIZATION_ORDERING bit at the end (state 2 to state 3) to clean up before the next collection.