/gomicollector

gomicollector is a simple mark-sweep garbage collector in Rust.

Primary LanguageRust

logo

gomicollector

CI License: MIT Crates.io

gomicollector is a simple mark-sweep garbage collector in Rust.

gomicollector collects garbage when the heap is full.

Since pointer operation is difficult in Rust, I implemented a gomicollector by thinking of the heap as a vector of object and the pointer as the index of the vector.

How to use

  1. Initialize a heap.
let mut heap = Heap::<String>::new(4);
  1. Allocate an object to the heap. when you call heap.allocate(), gc collects garabage if the heap is full and return allocated memory address.
let obj1_id = heap.allocate("Obj1".to_string());
  1. Set the root object to point to the obj1
heap.root_set.insert(obj1_id.unwrap());
  1. Set the head of obj1 to point to obj3
let obj3_id = heap.allocate("Obj3".to_string());
heap.heap[obj1_id.unwrap()].set_head(obj3_id);
  1. change the object data
heap.heap[obj1_id.unwrap()].set_data("changed data".to_string());

Example

  • Situation:
    • root->obj1->obj3 (reachable)
    • obj2 (unreachable or garbage, so it will be collected)
$ 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: [],
}

TODO

  • allow allocated object to change its data, not via heap object.
  • simulate stack machine with gomicollector

Ref.