gomicollector

gomicollector 是 Rust 中一个简单的标记-清除垃圾收集器。

当堆满时，gomicollector 会收集垃圾。

由于 Rust 中的指针操作很困难，我通过将堆视为对象的向量以及将指针视为向量的索引来实现了 gomicollector。

如何使用

1. 初始化一个堆。

let mut heap = Heap::<String>::new(4);

2. 将对象分配到堆中。当调用 heap.allocate() 时，如果堆已满，gc 会收集垃圾并返回分配的内存地址。

let obj1_id = heap.allocate("Obj1".to_string());

3. 将根对象设置为指向 obj1

heap.root_set.insert(obj1_id.unwrap());

4. 将 obj1 的头设置为指向 obj3

let obj3_id = heap.allocate("Obj3".to_string());
heap.heap[obj1_id.unwrap()].set_head(obj3_id);

5. 更改对象数据

heap.heap[obj1_id.unwrap()].set_data("changed data".to_string());

示例

• 情况
  • root->obj1->obj3 (可达)
  • obj2 (不可达或垃圾，因此将被收集)

$ git clone https://github.com/speed1313/gomicollector.git
$ cd gomicollector
$ cargo run
mark and sweep
obj1 allocated Object { head: None, tail: None, marked: false, id: 3, data: Some("Obj1") }
tmp0 will be allocated
tmp1 will be allocated
tmp2 will be allocated
tmp3 will be allocated
mark and sweep
droped "tmp2"
droped "tmp1"
droped "tmp0"
obj2 allocated: Object { head: None, tail: None, marked: false, id: 1, data: Some("Obj2") }
tmp0 will be allocated
tmp1 will be allocated
mark and sweep
droped "tmp0"
droped "Obj2"
droped "tmp3"
tmp2 will be allocated
tmp3 will be allocated
mark and sweep
droped "tmp3"
droped "tmp2"
droped "tmp1"
obj3 allocated: Object { head: None, tail: None, marked: false, id: 2, data: Some("Obj3") }
tmp0 will be allocated
tmp1 will be allocated
tmp2 will be allocated
mark and sweep
droped "tmp1"
droped "tmp0"
tmp3 will be allocated
heap: Heap {
    heap: [
        Object {
            head: None,
            tail: None,
            marked: false,
            id: 0,
            data: Some(
                "tmp3",
            ),
        },
        Object {
            head: None,
            tail: None,
            marked: false,
            id: 1,
            data: Some(
                "tmp2",
            ),
        },
        Object {
            head: None,
            tail: None,
            marked: true,
            id: 2,
            data: Some(
                "Obj3",
            ),
        },
        Object {
            head: Some(
                2,
            ),
            tail: None,
            marked: true,
            id: 3,
            data: Some(
                "changed data",
            ),
        },
    ],
    root: Some(
        3,
    ),
    size: 4,
    free_list: [],
}

待办事项

• 允许已分配对象更改其数据，而不是通过堆对象。
• 使用 gomicollector 模拟堆栈机器

参考

• https://speed1313.notion.site/Garbage-Collection-mark-sweep-b04f5cb763824b8b9cc3735c29fde545
• https://github.com/munificent/mark-sweep
• https://github.com/jorendorff/gc-in-50-lines
• 垃圾收集：构建自动内存管理的理论与实现，Richard Jones 等（著），前田敦司等（译）
• Crafting Interpreters，Robert Nystrom，https://craftinginterpreters.fullstack.org.cn/garbage-collection.html