garbage-collection - 对范围内的垃圾收集进行建模的生命周期约束

我正在与一个 friend 一起为“作用域”垃圾收集器的生命周期定义一个安全的公共(public)API。生存期受到过度限制，并且无法编译正确的代码，或者生存期过于宽松，可能会导致无效行为。在尝试了多种方法之后，我们仍然无法获得正确的API。尤其令人沮丧的是，Rust的生命周期可以帮助避免这种情况下的错误，但是现在它看起来很顽固。

范围垃圾回收

我正在实现一个ActionScript解释器，并且需要一个垃圾回收器。我研究了rust-gc，但它不符合我的需求。主要原因是因为GC状态是线程局部静态变量，所以它要求垃圾回收值具有a static lifetime。我需要获取到动态创建的宿主对象的垃圾收集绑定(bind)。避免使用全局变量的另一个原因是，对于我来说，更容易处理多个独立的垃圾收集范围，控制它们的内存限制或序列化它们。

有作用域的垃圾收集器类似于typed-arena。您可以使用它来分配值，并在丢弃垃圾收集器后将它们全部释放。不同之处在于，您还可以在其生命周期内触发垃圾收集，它将清除无法访问的数据(并且不仅限于单个类型)。

我有a working implementation implemented (mark & sweep GC with scopes)，但是该接口(interface)尚不安全。

这是我想要的用法示例:

pub struct RefNamedObject<'a> {
    pub name: &'a str,
    pub other: Option<Gc<'a, GcRefCell<NamedObject<'a>>>>,
}

fn main() {
    // Initialize host settings: in our case the host object will be replaced by a string
    // In this case it lives for the duration of `main`
    let host = String::from("HostConfig");

    {
        // Create the garbage-collected scope (similar usage to `TypedArena`)
        let gc_scope = GcScope::new();

        // Allocate a garbage-collected string: returns a smart pointer `Gc` for this data
        let a: Gc<String> = gc_scope.alloc(String::from("a")).unwrap();

        {
            let b = gc_scope.alloc(String::from("b")).unwrap();
        }

        // Manually trigger garbage collection: will free b's memory
        gc_scope.collect_garbage();

        // Allocate data and get a Gc pointer, data references `host`
        let host_binding: Gc<RefNamed> = gc_scope
            .alloc(RefNamedObject {
                name: &host,
                other: None,
            })
            .unwrap();

        // At the end of this block, gc_scope is dropped with all its
        // remaining values (`a` and `host_bindings`)
    }
}

终生属性

基本直觉是Gc只能包含生命周期比相应GcScope更长(或更长)的数据。 Gc与Rc类似，但支持循环。您需要使用Gc<GcRefCell<T>>来突变值(类似于Rc<RefCell<T>>)。

以下是我的API生命周期必须满足的属性:
Gc的生命周期不能超过其GcScope
以下代码必须失败，因为a比gc_scope生命周期长:

let a: Gc<String>;
{
    let gc_scope = GcScope::new();
    a = gc_scope.alloc(String::from("a")).unwrap();
}
// This must fail: the gc_scope was dropped with all its values
println("{}", *a); // Invalid

Gc不能包含生命周期短于GcScope的数据

以下代码必须失败，因为msg的生存时间(或更长)不及gc_scope

let gc_scope = GcScope::new();
let a: Gc<&string>;
{
    let msg = String::from("msg");
    a = gc.alloc(&msg).unwrap();
}

必须可以分配多个Gc(gc_scope不排除)

以下代码必须编译

let gc_scope = GcScope::new();

let a = gc_scope.alloc(String::from("a"));
let b = gc_scope.alloc(String::from("b"));

必须有可能分配包含生命周期超过gc_scope的引用的值

以下代码必须编译

let msg = String::from("msg");
let gc_scope = GcScope::new();
let a: Gc<&str> = gc_scope.alloc(&msg).unwrap();

必须有可能创建Gc指针的循环(这就是重点)

与Rc<Refcell<T>>模式类似，您可以使用Gc<GcRefCell<T>>突变值并创建周期:

// The lifetimes correspond to my best solution so far, they can change
struct CircularObj<'a> {
    pub other: Option<Gc<'a, GcRefCell<CircularObj<'a>>>>,
}

let gc_scope = GcScope::new();

let n1 = gc_scope.alloc(GcRefCell::new(CircularObj { other: None }));
let n2 = gc_scope.alloc(GcRefCell::new(CircularObj {
    other: Some(Gc::clone(&n1)),
}));
n1.borrow_mut().other = Some(Gc::clone(&n2));

到目前为止的解决方案

自动生命周期/生命周期标签

在 auto-lifetime branch上实现

该解决方案的灵感来自 neon 的句柄。
这样可以编译任何有效的代码(并允许我测试我的实现)，但是它过于宽松并且允许无效的代码。 它允许Gc超过创建它的gc_scope 。 (违反第一个属性)

这里的想法是，我向所有结构添加一个生命周期的'gc。想法是，此生命期表示“gc_scope生命期”。

// A smart pointer for `T` valid during `'gc`
pub struct Gc<'gc, T: Trace + 'gc> {
    pub ptr: NonNull<GcBox<T>>,
    pub phantom: PhantomData<&'gc T>,
    pub rooted: Cell<bool>,
}

我将其称为自动生命周期，因为这些方法永远不会将这些结构生命周期与它们收到的引用的生命周期混合在一起。

这是gc_scope.alloc的含义:

impl<'gc> GcScope<'gc> {
    // ...
    pub fn alloc<T: Trace + 'gc>(&self, value: T) -> Result<Gc<'gc, T>, GcAllocErr> {
        // ...
    }
}

内/外生命周期

在 inner-outer branch上实现

此实现尝试通过将Gc与GcScope的生存期相关联来解决以前的问题。 约束过多，无法创建循环。 这违反了最后一个属性。

为了相对于Gc限制GcScope，我引入了两个生存期:'inner是GcScope的生存期，结果是Gc<'inner, T>。 'outer表示比'inner更长的生存期，并用于分配的值。

这是分配签名:

impl<'outer> GcScope<'outer> {
    // ...

    pub fn alloc<'inner, T: Trace + 'outer>(
        &'inner self,
        value: T,
    ) -> Result<Gc<'inner, T>, GcAllocErr> {
        // ...
    }

    // ...
}

闭包(上下文管理)

在 with branch上实现

另一个想法是不让用户使用GcScope手动创建GcScope::new，而是公开提供GcScope::with(executor)引用的函数gc_scope。闭合executor对应于gc_scope。到目前为止，它要么阻止使用外部引用，要么允许将数据泄漏到外部Gc变量(第一和第四属性)。

这是分配签名:

impl<'gc> GcScope<'gc> {
    // ...
    pub fn alloc<T: Trace + 'gc>(&self, value: T) -> Result<Gc<'gc, T>, GcAllocErr> {
        // ...
    }
}

这是一个使用示例，显示违反第一个属性的情况:

let message = GcScope::with(|scope| {
    scope
        .alloc(NamedObject {
            name: String::from("Hello, World!"),
        })
        .unwrap()
});
println!("{}", message.name);

我想要什么

据我了解，我想要的alloc签名是:

impl<'gc> GcScope<'gc> {
    pub fn alloc<T: Trace + 'gc>(&'gc self, value: T) -> Result<Gc<'gc, T>, GcAllocErr> {
        // ...
    }
}

凡事都比self(gc_scope)长寿或长寿的地方。但这会通过最简单的测试爆炸:

fn test_gc() {
    let scope: GcScope = GcScope::new();
    scope.alloc(String::from("Hello, World!")).unwrap();
}

原因

error[E0597]: `scope` does not live long enough
  --> src/test.rs:50:3
   |
50 |   scope.alloc(String::from("Hello, World!")).unwrap();
   |   ^^^^^ borrowed value does not live long enough
51 | }
   | - `scope` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

我不知道这里会发生什么。 Playground link

编辑:正如在IRC上向我解释的那样，这是因为我实现了Drop，它需要&mut self，但是scope已经以只读模式借用了。

概述

这里是我图书馆主要组成部分的快速概述。
GcScope 包含一个处于可变状态的RefCell。引入它的目的是不需要&mut self作为alloc，因为它“锁定”了gc_scope并违反了属性3:分配多个值。
此可变状态为 GcState 。它跟踪所有分配的值。这些值存储为 GcBox 的仅向前链接列表。这个GcBox是堆分配的，并且包含带有一些元数据的实际值(多少活跃的Gc指针将其作为根，并带有一个 bool 标志，用于检查从根是否可访问该值(请参阅rust-gc)。此处的值必须有效它的gc_scope，因此GcBox使用了生存期，然后GcState必须同时使用lifet和GcScope:这始终是相同的生存期，意思是“比gc_scope更长”。我无法终生工作的原因(这会导致不变性吗？)。

GcScope 是指向某些RefCell分配的数据的智能指针。您只能通过Gc或克隆它来获取它。
gc_scope 很可能很好，它只是一个gc_scope.alloc包装器，添加了元数据和行为以适当地支持借用。

灵活性

我很满意以下要求以获得解决方案:

不安全代码

夜间功能

API更改(例如，参见我的GcRefCell方法)。重要的是，我可以创建一个临时区域，在其中可以处理垃圾收集的值，然后将它们全部删除。这些垃圾收集的值需要能够访问范围之外的生命周期较长(但不是静态)的变量。

The repository在RefCell(编译失败)中以with进行了一些测试。

我找到了一个解决方案，将其删除后将其发布。

最佳答案

到目前为止，这是我在Rust的一生中遇到的最困难的问题之一，但是我设法找到了解决方案。谢谢panicbit和mbrubeck在IRC上对我的帮助。

插入我前进的是我对问题结尾处发布的错误的解释:

error[E0597]: `scope` does not live long enough
  --> src/test.rs:50:3
   |
50 |   scope.alloc(String::from("Hello, World!")).unwrap();
   |   ^^^^^ borrowed value does not live long enough
51 | }
   | - `scope` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

我不明白此错误，因为我不清楚为什么借用了scope，持续了多长时间，或者为什么在范围末尾不再需要借用了scope。

原因是在分配值期间，在分配的值期间，drop是不变地借用的。现在的问题是，作用域包含一个实现“Drop”的状态对象:&mut self的自定义实现使用&mut self ->当值已经被不可改变地借用时，就不可能获得可变的借用。

了解该下降需要alloc，并且它与不可变的借位不兼容，从而解开了局面。

事实证明，上面问题中描述的内外方法具有正确的Gc生存期:

impl<'outer> GcScope<'outer> {
    // ...

    pub fn alloc<'inner, T: Trace + 'outer>(
        &'inner self,
        value: T,
    ) -> Result<Gc<'inner, T>, GcAllocErr> {
        // ...
    }

    // ...
}

返回的GcScope的生命周期与GcScope的生命周期相同，并且分配的值必须比当前alloc的生命周期更长。正如问题中提到的那样，此解决方案的问题在于它不支持循环值。

循环值无法工作不是因为drop的生存期，而是由于自定义drop。删除alloc可使所有测试通过(但内存泄漏)。

解释很有趣:
GcScope的生存期表示分配值的属性。分配的值不能超过其GcScope，但是其内容的生命周期必须比GcScope更长或更长。创建循环时，该值受这两个约束:分配该值的生命周期必须比GcScope更长或更短，但还要由另一个分配的值引用，因此它的生命周期必须比GcScope更长或更长。因此，只有一种解决方案:分配的值必须与其范围的一样长。

这意味着drop的生存期及其分配的值完全相同。 当两个生存期相同时，Rust不保证丢弃的顺序。发生这种情况的原因是，drop实现可能会尝试相互访问，并且由于没有排序，这将是不安全的(值可能已经被释放)。

这在Drop Check chapter of the Rustonomicon中进行了解释。

在我们的案例中，收集到的垃圾状态的drop实现不会取消引用已分配的值(相反，它释放了它们的内存)，因此Rust编译器过分谨慎，因为它阻止了我们实现may_dangle。

幸运的是，Nomicon还解释了如何解决这些具有相同生存期的值检查。解决方案是在Drop实现的生命周期参数上使用generic_param_attrs属性。
这是不稳定属性，需要启用dropck_eyepatch和drop功能。

具体来说，我的lib.rs实现变为:

unsafe impl<'gc> Drop for GcState<'gc> {
    fn drop(&mut self) {
        // Free all the values allocated in this scope
        // Might require changes to make sure there's no use after free
    }
}

我在generic_param_attrs中添加了以下几行:

#![feature(generic_param_attrs)]
#![feature(dropck_eyepatch)]

您可以阅读有关这些功能的更多信息:

may_dangle

ojit_code

如果您想仔细看一下，我用此问题的修复程序更新了我的库scoped-gc。

关于garbage-collection - 对范围内的垃圾收集进行建模的生命周期约束，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49183195/