手写垃圾回收器：泛型容器、Cell 与第一次 unsafe

1
[package]
2
name = "pebble-gc"
3
description = "A mark-sweep garbage collector written with raw pointers and unsafe."
4
version.workspace = true
5
edition.workspace = true
6
rust-version.workspace = true
7
authors.workspace = true
8
license.workspace = true
9
repository.workspace = true
10

11
[dependencies]
12

13
[dev-dependencies]
14
rand.workspace = true
15

16
[lints]
17
workspace = true

1
//! A precise mark-sweep garbage collector plus a small bump arena for one-shot
2
//! allocations ([`bump`]).
3
//!
4
//! The collector is generic over the [`GcObject`] trait, so an embedder such as
5
//! the Pebble VM plugs in its own object enum and decides how each object
6
//! reports its child references. The heap owns a flat table of slots; an
7
//! embedder allocates with [`Heap::alloc`] and keeps the returned [`GcRef`]
8
//! handles in its own roots (value stack, globals, temporaries). Collection is
9
//! split into two embedder-driven phases:
10
//!
11
//! 1. Mark every root: `heap.mark(root)` for each handle the embedder still
12
//!    holds. Marking follows the children reported by [`GcObject::trace`]
13
//!    transitively.
14
//! 2. Sweep: `heap.collect()` returns every unmarked slot to the free list and
15
//!    clears the mark bits, ready for the next cycle.
16
//!
17
//! [`Heap::mark`] only needs `&self`, so roots can be marked through a shared
18
//! reference; the mark bits live in [`Cell`]s inside the heap. There is no
19
//! global collector state and no `Drop`-based collection: reclamation happens
20
//! only when the embedder calls [`Heap::collect`].
21
//!
22
//! # Example
23
//!
24
//! ```
25
//! use pebble_gc::{GcObject, GcRef, Heap};
26
//!
27
//! /// A list-like object: it traces the references it holds.
28
//! struct Node(Vec<GcRef>);
29
//!
30
//! impl GcObject for Node {
31
//!     fn trace(&self, mark: &mut dyn FnMut(GcRef)) {
32
//!         for &child in &self.0 {
33
//!             mark(child);
34
//!         }
35
//!     }
36
//! }
37
//!
38
//! let mut heap: Heap<Node> = Heap::new();
39
//! let kept = heap.alloc(Node(vec![]));
40
//! let garbage = heap.alloc(Node(vec![]));
41
//!
42
//! heap.mark(kept);
43
//! heap.collect();
44
//!
45
//! assert_eq!(heap.live_count(), 1);
46
//! assert!(heap.is_alive(kept));
47
//! assert!(!heap.is_alive(garbage));
48
//! ```
49

50
use core::cell::Cell;
51

52
pub mod bump;

1
/// A handle to a live object inside a [`Heap`].
2
///
3
/// `GcRef` is a plain `u32` slot index and is `Copy`, so embedders can store
4
/// handles on their own stacks and in registers without touching the heap. A
5
/// handle only means something to the [`Heap`] that produced it, and it becomes
6
/// *dangling* once its slot is returned by [`Heap::free`] or reclaimed by
7
/// [`Heap::collect`]; [`Heap::is_alive`] tests for that without panicking.
8
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
9
pub struct GcRef(u32);
10

11
impl GcRef {
12
    /// The underlying slot index of this handle.
13
    pub const fn index(self) -> u32 {
14
        self.0
15
    }
16

17
    /// Rebuilds a handle from a slot index.
18
    ///
19
    /// The index must have come from [`GcRef::index`]; forging one for a slot
20
    /// that is not live produces a dangling handle.
21
    pub const fn from_index(index: u32) -> Self {
22
        Self(index)
23
    }
24
}

1
/// A mark-sweep heap over a flat table of slots, generic over the object type.
2
///
3
/// Freed slots are recycled: the slot table grows to the peak number of
4
/// simultaneously live objects, not to the total number of allocations ever
5
/// performed.
6
#[derive(Debug)]
7
pub struct Heap<O: GcObject> {
8
    slots: Vec<Option<O>>,
9
    free: Vec<u32>,
10
    marked: Vec<Cell<bool>>,
11
    allocations_since_gc: usize,
12
}
13

14
impl<O: GcObject> Heap<O> {
15
    /// Creates an empty heap with no slots allocated.
16
    pub fn new() -> Self {
17
        Self {
18
            slots: Vec::new(),
19
            free: Vec::new(),
20
            marked: Vec::new(),
21
            allocations_since_gc: 0,
22
        }
23
    }

1
    /// Sweeps every slot that is not marked, then clears all mark bits.
2
    ///
3
    /// The embedder must have marked its roots (via [`Heap::mark`]) before
4
    /// calling this. After the sweep the heap is ready for the next mark phase.
5
    pub fn collect(&mut self) {
6
        for index in 0..self.slots.len() {
7
            if self.marked[index].get() {
8
                self.marked[index].set(false);
9
            } else if self.slots[index].is_some() {
10
                let slot = u32::try_from(index).expect("heap outgrew its u32 slot index");
11
                self.free(GcRef(slot));
12
            }
13
        }
14
        self.allocations_since_gc = 0;
15
    }

1
    /// Whether `r` names a slot that currently holds an object.
2
    ///
3
    /// Unlike [`Heap::get`], this never panics: an out-of-range or freed handle
4
    /// simply reports `false`.
5
    pub fn is_alive(&self, r: GcRef) -> bool {
6
        self.slots
7
            .get(r.0 as usize)
8
            .is_some_and(|slot| slot.is_some())
9
    }
10

11
    /// Number of occupied slots, i.e. objects not yet swept.
12
    pub fn live_count(&self) -> usize {
13
        self.slots.len() - self.free.len()
14
    }
15

16
    /// Number of object slots the heap can hold without reallocating its
17
    /// tables.
18
    pub fn capacity(&self) -> usize {
19
        self.slots.capacity()
20
    }
21

22
    /// Estimated total bytes occupied by the live slots.
23
    ///
24
    /// This is `live_count() * size_of::<O>()`: the inline size of each object
25
    /// as stored in its slot. Memory a `GcObject` owns indirectly, such as a
26
    /// `String` buffer or a `Vec`'s heap block, is not counted, so treat this
27
    /// as an estimate for deciding when to collect rather than an exact
28
    /// allocator figure.
29
    pub fn bytes_allocated(&self) -> usize {
30
        self.live_count() * core::mem::size_of::<O>()
31
    }
32

33
    /// Number of allocations performed since the last [`Heap::collect`].
34
    ///
35
    /// An embedder can use this to trigger collection after a fixed number of
36
    /// allocations.
37
    pub fn allocations_since_gc(&self) -> usize {
38
        self.allocations_since_gc
39
    }
40
}
41

42
impl<O: GcObject> Default for Heap<O> {
43
    fn default() -> Self {
44
        Self::new()
45
    }
46
}

1
#[cfg(test)]
2
mod tests {
3
    use super::{GcObject, GcRef, Heap};
4
    use rand::prelude::*;
5

6
    /// A concrete heap object for the tests, mirroring the shapes the Pebble
7
    /// runtime will plug in: strings, lists and closures.
8
    #[derive(Clone, PartialEq, Eq, Debug)]
9
    enum TestObject {
10
        Str(String),
11
        List(Vec<GcRef>),
12
        Closure { name: String, captured: Vec<GcRef> },
13
    }
14

15
    impl GcObject for TestObject {
16
        fn trace(&self, mark: &mut dyn FnMut(GcRef)) {
17
            match self {
18
                TestObject::Str(_) => {}
19
                TestObject::List(items) => {
20
                    for &child in items {
21
                        mark(child);
22
                    }
23
                }
24
                TestObject::Closure { captured, .. } => {
25
                    for &child in captured {
26
                        mark(child);
27
                    }
28
                }
29
            }
30
        }
31
    }
32

33
    fn list(heap: &mut Heap<TestObject>, children: &[GcRef]) -> GcRef {
34
        heap.alloc(TestObject::List(children.to_vec()))
35
    }

1
    #[test]
2
    fn deeply_nested_lists_survive() {
3
        let mut heap: Heap<TestObject> = Heap::new();
4
        let mut current = heap.alloc(TestObject::Str("bottom".into()));
5
        for _ in 0..10_000 {
6
            current = list(&mut heap, &[current]);
7
        }
8

9
        // The worklist marker must handle this depth without recursing.
10
        heap.mark(current);
11
        heap.collect();
12

13
        assert_eq!(heap.live_count(), 10_001);
14
    }
15

16
    #[test]
17
    fn unreachable_cycles_are_collected() {
18
        let mut heap: Heap<TestObject> = Heap::new();
19
        let a = list(&mut heap, &[]);
20
        let b = list(&mut heap, &[a]);
21
        // Close the cycle: a -> b -> a. Neither is rooted.
22
        match heap.get_mut(a) {
23
            TestObject::List(items) => items.push(b),
24
            other => panic!("expected a list, got {other:?}"),
25
        }
26

27
        heap.collect();
28

29
        assert_eq!(heap.live_count(), 0, "an unreachable cycle is swept");
30
        assert_eq!(heap.bytes_allocated(), 0);
31
        assert!(!heap.is_alive(a));
32
    }