在 MiniMark GC 中排序终结器¶

RPython 接口¶

在像 PyPy 这样的 RPython 程序中，我们需要一种细粒度的控制 RPython 以及应用程序级 __del__() 的方法。为了实现这一点，RPython 接口现在是以下内容（从 2016 年 5 月开始）

RPython 对象可以有 __del__()。当对对象的最后一个引用消失时，GC 会立即调用它们，就像在 CPython 中一样。但是，长期目标是所有 __del__() 方法都应该只包含足够简单的代码。如果它们这样做，我们称它们为“析构函数”。例如，它们不能使用会使对象复活的操作。使用装饰器 @rgc.must_be_light_finalizer 来确保它们是析构函数。
为了向后兼容，支持不通过析构函数测试的 RPython 级别的 __del__()，但已弃用。本文档的其余部分假设 __del__() 都是析构函数。
对于任何更高级的用法——特别是对于任何带有 __del__ 的应用程序级对象——我们不使用 RPython 级别的 __del__() 方法。相反，我们使用 rgc.FinalizerController.register_finalizer()。这使我们能够将终结器方法附加到对象，从而比 RPython __del__() 提供更多对排序的控制。

我们尝试一致地将 __del__() 称为析构函数，以将其与终结器区分开来。终结器运行得更早，并且按拓扑顺序运行；必须注意，如果我们足够聪明，对象可能仍然可以在此时被访问。另一方面，析构函数最后运行；不再可以对对象进行任何操作，GC 会立即释放它。

析构函数¶

析构函数是一个 RPython __del__() 方法，当 GC 即将释放内存时，它会直接调用该方法。旨在用于只需要释放额外块原始内存的对象。

对可以放在 __del__() 中的代码类型（包括它调用的所有其他函数）存在限制。这些限制将被检查。特别是，您不能访问包含 GC 对象的字段。现在您也不能调用任何外部 C 函数。

当 GC 释放对象的内存时，会精确地调用析构函数。只要对象存在（即使在某个终结器队列或任何地方），它的析构函数都不会被调用。

Register_finalizer¶

完整终结器的接口是针对 PyPy 设计的，但应该普遍有用。

这个想法是，您需要子类化 rgc.FinalizerQueue 类。

您必须提供一个类级属性 base_class，它是所有具有终结器的实例的基类。（如果您需要对多个不相关的类进行终结器，则需要多个不相关的 FinalizerQueue 子类。）
您需要重写 finalizer_trigger() 方法；请参见下文。

然后，您需要创建此子类的全局（或特定于空间）实例；将其称为 fin。在运行时，您需要为每个需要终结器的实例 obj 调用 fin.register_finalizer(obj)。每个 obj 必须是 fin.base_class 的实例，但并非所有此类实例都需要注册终结器；通常，我们尝试尽可能少地注册终结器（例如，仅当它是具有应用程序级 __del__() 方法的对象时）。

在进行主要收集后，GC 会找到所有注册了终结器且无法访问的对象 obj，并将它们标记为再次可访问，以及它们依赖的所有对象。然后，它会选择一个拓扑排序（如果存在循环，则随机打破循环），并将这些对象及其注册的终结器函数按顺序排队，排队到特定于预构建的 fin 实例的队列中。最后，在主要收集完成后，它会调用 fin.finalizer_trigger()。

此方法 finalizer_trigger() 可以直接执行一些工作，也可以延迟执行（例如，在两个字节码之间）。如果它直接执行工作，请注意它不能（直接或间接）导致 GIL 被释放。

要查找排队的项目，请重复调用 fin.next_dead()。它会返回下一个排队的项目，或者在队列为空时返回 None。

理论上，如果您为同一类的对象累积多个不同的 FinalizerQueue 实例，并且（始终在理论上）相同的 obj 可以多次注册到同一个队列中，或者注册到多个队列中，这将起作用。但这尚未经过测试。目前，未翻译的仿真不支持多次注册同一个对象。

请注意，Boehm 垃圾收集器（在 rpython -O0 中使用）完全忽略了 register_finalizer()。

终结器的排序¶

在收集之后，MiniMark GC 应该对某些具有终结器且已变得无法访问的对象调用终结器。基本上，如果从对象 a 到对象 b 存在引用链，则它不应该立即调用 b 的终结器，而应该保持 b 的活动状态，并在下一次收集后再次尝试调用其终结器。

（请注意，一旦程序比主要收集的速度（非常慢）更快地创建具有终结器的对象链，这就会产生罕见但令人讨厌的问题。在 2013 年 8 月，我们尝试改为对在主要收集时发现无法访问的所有对象调用所有终结器。该分支 gc-del 从未合并。目前尚不清楚这将对现实世界中的程序产生什么实际影响。）

基本思想在存在循环的情况下会失效。让对象永远存活或永远不调用任何终结器并不是一个好主意。我们想出的模型是在这种情况下，我们可以只调用循环中某个对象的终结器——当然，只有在循环外部没有其他具有终结器并引用该循环的对象时才这样做。

更准确地说，给定对象之间引用的图

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

算法¶

在 deal_with_objects_with_finalizers() 期间，每个对象 x 可以处于 4 种可能的状态

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

最初，对象处于状态 0 或 3，具体取决于它们是否被之前完成的常规扫描复制。不变式是，如果从 x 到 y 有引用，则 state[y] >= state[x]。

状态 2 用于可从终结器访问但可能与终结器位于同一强连通分量中的对象。当我们证明这些对象可以从肯定不在同一强连通分量中的终结器访问时，这些对象的状态变为 3。状态为 3 的对象的终结器不得调用。

令 closure(x) 为从 x 可访问的对象列表，包括 x 本身。获取标记对象列表的伪代码（高级）

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)

这在 objects_with_finalizers 枚举的顺序上做出了正确的事情。首先假设 [x1, .., xn] 都在同一个不可达强连通分量中；没有具有终结器的对象从外部引用此强连通分量。然后

当处理 x1 时，state[x1] == .. == state[xn] == 0，与我们之前做了什么无关。因此 x1 被标记，我们将 state[x1] = .. = state[xn] 设置为 2。
当处理 x2, … xn 时，它们的状态 != 0，因此我们不做任何操作。
在最终循环中，只有 x1 被标记，并且 state[x1] == 2，因此它保持标记状态。

现在，假设 x1 和 x2 不在同一个强连通分量中，并且从 x1 到 x2 有一个引用路径。然后

如果 x1 在 x2 之前枚举，则 x2 位于 closure(x1) 中，因此当我们处理 x1 时，它的状态至少变为 >= 2。当我们稍后处理 x2 时，我们只是跳过它（“continue” 行），因此它不会被标记。
如果 x2 在 x1 之前枚举，则当我们处理 x2 时，我们会标记它并将它的状态设置为 >= 2（在 x2 位于 closure(x2) 之前），然后当我们处理 x1 时，我们将 state[x2] 设置为 3。因此在最终循环中，x2 从“标记”列表中删除。

我认为这证明了算法正在做我们想要做的事情。

下一步是删除算法中 closure() 的使用，以便新算法具有合理的性能——与它操作的对象数量成线性关系。

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)

在这个算法中，我们最多跟踪每个对象的子节点 3 次，当对象的状态从 0 变为 1 再变为 2 再变为 3 时。在不改变对象状态的访问中，我们不会递归地跟踪它的子节点。

实际上，在 MiniMark GCs 中，我们可以使用标头中的两个位的组合来编码 4 种状态

状态 GCFLAG_VISITED GCFLAG_FINALIZATION_ORDERING

0 否否

1 否是

2 是是

3 是否

因此，上面的循环从状态 1 到状态 2 的转换实际上只是一个递归访问。我们还必须在最后（状态 2 到状态 3）清除 FINALIZATION_ORDERING 位，以便在下次收集之前进行清理。

状态	GCFLAG_VISITED	GCFLAG_FINALIZATION_ORDERING
0	否	否
1	否	是
2	是	是
3	是	否