首页 文章

模拟作用域垃圾收集的生命周期约束

提问于
浏览 次
3

我正和一位朋友一起为“范围”垃圾收集器的生命周期定义一个安全的公共API . 生命周期要么过度约束，正确的代码不能编译，或者生命周期太松，它们可能允许无效行为 . 尝试多种方法后，我们仍然无法获得正确的API . 这特别令人沮丧，因为Rust的生命周期可以帮助避免在这种情况下的错误，但现在它看起来很顽固 .

Scoped垃圾收集

我正在实现一个ActionScript解释器，需要一个垃圾收集器 . 我研究了rust-gc但它不适合我的需要 . 主要原因是它需要垃圾收集值具有a static lifetime，因为GC状态是线程局部静态变量 . 我需要将垃圾收集绑定到动态创建的宿主对象 . 避免全局变量的另一个原因是我更容易处理多个独立的垃圾收集范围，控制其内存限制或序列化它们 .

范围内的垃圾收集器类似于typed-arena . 您可以使用它来分配值，并在删除垃圾收集器后释放它们 . 不同之处在于，您还可以在其生命周期内触发垃圾收集，并清除无法访问的数据（并且不限于单一类型） .

我有a working implementation implemented (mark & sweep GC with scopes)，但界面还不安全 .

这是我想要的用法示例：

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

以下代码必须 fail 因为 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短的数据

以下代码必须 fail ，因为 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的句柄 . 这允许任何有效的代码编译（并允许我测试我的实现）但是太松散并且允许无效的代码 . It allows Gc to outlive the gc_scope that created it . （违反第一个 property ）

这里的想法是我为我的所有结构添加一个生命周期 'gc . 这个想法是这个生命周期代表"how long gc_scope lives" .

// 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：

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

内/外生命

在inner-outer branch上实施

此实现尝试通过将 Gc 与 GcScope 的生命周期相关联来修复上一个问题 . It is overly constrained and prevents the creation of cycles. 这违反了最后一个属性 .

为了约束 Gc 相对于它的 GcScope ，我引入了两个生命周期： 'inner 是 GcScope 的生命周期，结果是 Gc<'inner, T> . 'outer 表示比 'inner 更长的生命周期，用于分配的值 .

这是alloc签名：

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

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

    // ...
}

关闭（上下文管理）

在with branch实施

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

这是alloc签名：

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);

我想要什么

根据我的理解，我喜欢的签名是：1270436_签名：

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

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

概述

以下是我的库的主要组件的快速概述 . GcScope包含 RefCell 到其可变状态 . 这被引入不需要 &mut self for alloc ，因为它是_cc_scope和违反属性3：分配多个值 . 这种可变状态是GcState . 它跟踪所有分配的值 . 这些值存储为GcBox的仅向前链接列表 . 这个 GcBox 是堆分配的，包含一些元数据的实际值（有多少活动 Gc 指针将它作为根，一个布尔标志用于检查是否可以从根访问该值（参见rust-gc） . 这里的值必须比这更长它 gc_scope 所以 GcBox 使用了一个生命周期，然后 GcState 必须使用一生和 GcScope ：这总是相同的生命周期意味着“比 gc_scope 更长”. GcScope 具有 RefCell （内部可变性）和生命周期的事实可能是为什么我不能让我的一生工作（它导致不变性？） .

Gc是指向某些 gc_scope 分配数据的智能指针 . 你只能通过 gc_scope.alloc 或克隆它 . GcRefCell很可能很好，它只是一个 RefCell 包装器添加元数据和行为以正确支持借用 .

灵活性

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

  • 不安全的代码

  • 夜间功能

  • API更改（请参阅我的 with 方法） . 重要的是我可以创建一个临时区域，在那里我可以操作垃圾收集的值，并且在此之后它们都被丢弃了 . 这些垃圾收集值需要能够访问范围之外的更长寿命（但不是静态）变量 .

The repository在 scoped-gc/src/lib.rs （编译失败）中有一些测试为 scoped-gc/src/test.rs .

I found a solution, I'll post it once redacted.

garbage-collection rust lifetime

1 回答

  • 2

    这是我到目前为止与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"的状态对象： custom implementations of drop use &mut self - >当值已经不可避免地借用时，不可能为丢弃获得可变的借位 .

    了解drop需要 &mut self 并且它与不可变借用不兼容解锁了这种情况 .

    事实证明，上述问题中描述的内外方法与 alloc 具有正确的生命周期：

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

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

    // ...
}

    返回的 Gc 与 GcScope 一样长，分配的值必须比当前 GcScope 长 . 正如问题所述，此解决方案的问题在于它不支持循环值 .

    循环值无法工作，因为 alloc 的生命周期，但由于自定义 drop . 删除 drop 允许所有测试通过（但泄漏的内存） .

    解释非常有趣：

    alloc 的生命周期表示已分配值的属性 . 分配的值不能超过 GcScope ，但其内容必须长于或长于 GcScope . 在创建循环时，该值受这两个约束的约束：它被分配，因此必须长于或短于 GcScope ，但也由另一个分配的值引用，因此它必须长于或长于 GcScope . 因此，只有一个解决方案：分配的值必须以 exactly as long 作为其范围 .

    这意味着 GcScope 的生命周期及其分配的值完全相同 . When two lifetimes are the same, Rust does not guarantee the order of the drops . 发生这种情况的原因是 drop 实现可能尝试相互访问，因为没有排序它会不安全（值可能已经是释放） .

    这在Drop Check chapter of the Rustonomicon中有解释 .

    在我们的例子中，收集的垃圾状态的 drop 实现没有取消引用分配的值（恰恰相反，它释放了它们的内存）所以Rust编译器过于谨慎，因为阻止我们实现 drop .

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

    具体来说，我的 drop 实现成为：

    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
    }
}

    我在 lib.rs 添加了以下行：

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

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

    如果您想仔细查看它，我更新了我的库scoped-gc以及此问题的修复程序 .

    回复于

相关问题