shape_gc/
barrier.rs

1//! SATB (Snapshot At The Beginning) write barrier for incremental marking.
2//!
3//! During an incremental marking cycle the mutator may overwrite reference fields
4//! before the marker has scanned them.  The SATB invariant says: "any object that
5//! was reachable at the start of marking must be considered live."  To enforce
6//! this, every time a reference field is overwritten we enqueue the **old**
7//! reference into a per-thread SATB buffer.  At mark termination the GC drains
8//! these buffers and marks any enqueued (white) objects, preventing them from
9//! being falsely collected.
10
11/// Thread-local SATB buffer that accumulates old reference values overwritten
12/// during an active marking phase.
13pub struct SatbBuffer {
14    /// Accumulated old references that were overwritten while marking was active.
15    buffer: Vec<*mut u8>,
16    /// Maximum entries before the buffer should be flushed to the marker.
17    capacity: usize,
18}
19
20// Safety: SatbBuffer is owned by a single mutator thread and only handed to
21// the marker during STW termination.
22unsafe impl Send for SatbBuffer {}
23
24impl SatbBuffer {
25    /// Create a new SATB buffer with the given flush capacity.
26    pub fn new(capacity: usize) -> Self {
27        Self {
28            buffer: Vec::with_capacity(capacity),
29            capacity,
30        }
31    }
32
33    /// Enqueue an old reference that was just overwritten.
34    ///
35    /// This is the core write-barrier operation.  It must be called **before**
36    /// the store overwrites the old pointer value.
37    #[inline(always)]
38    pub fn enqueue(&mut self, old_ref: *mut u8) {
39        if !old_ref.is_null() {
40            self.buffer.push(old_ref);
41        }
42    }
43
44    /// Drain all enqueued references, returning them as a `Vec`.
45    ///
46    /// After draining, the buffer is empty and ready for new entries.
47    pub fn drain(&mut self) -> Vec<*mut u8> {
48        std::mem::take(&mut self.buffer)
49    }
50
51    /// Check whether the buffer is empty.
52    #[inline(always)]
53    pub fn is_empty(&self) -> bool {
54        self.buffer.is_empty()
55    }
56
57    /// Number of enqueued entries.
58    pub fn len(&self) -> usize {
59        self.buffer.len()
60    }
61
62    /// Whether the buffer has reached its flush capacity.
63    #[inline(always)]
64    pub fn should_flush(&self) -> bool {
65        self.buffer.len() >= self.capacity
66    }
67}
68
69impl Default for SatbBuffer {
70    fn default() -> Self {
71        Self::new(256)
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_new_buffer_is_empty() {
81        let buf = SatbBuffer::new(64);
82        assert!(buf.is_empty());
83        assert_eq!(buf.len(), 0);
84    }
85
86    #[test]
87    fn test_enqueue_and_drain() {
88        let mut buf = SatbBuffer::new(64);
89        let a = 0x1000 as *mut u8;
90        let b = 0x2000 as *mut u8;
91        buf.enqueue(a);
92        buf.enqueue(b);
93        assert_eq!(buf.len(), 2);
94        assert!(!buf.is_empty());
95
96        let drained = buf.drain();
97        assert_eq!(drained.len(), 2);
98        assert_eq!(drained[0], a);
99        assert_eq!(drained[1], b);
100        assert!(buf.is_empty());
101    }
102
103    #[test]
104    fn test_null_enqueue_ignored() {
105        let mut buf = SatbBuffer::new(64);
106        buf.enqueue(std::ptr::null_mut());
107        assert!(buf.is_empty());
108    }
109
110    #[test]
111    fn test_should_flush() {
112        let mut buf = SatbBuffer::new(2);
113        assert!(!buf.should_flush());
114        buf.enqueue(0x1000 as *mut u8);
115        assert!(!buf.should_flush());
116        buf.enqueue(0x2000 as *mut u8);
117        assert!(buf.should_flush());
118    }
119
120    #[test]
121    fn test_drain_resets_buffer() {
122        let mut buf = SatbBuffer::new(64);
123        buf.enqueue(0x1000 as *mut u8);
124        buf.enqueue(0x2000 as *mut u8);
125        let _ = buf.drain();
126        assert!(buf.is_empty());
127        assert_eq!(buf.len(), 0);
128        // Can enqueue again after drain
129        buf.enqueue(0x3000 as *mut u8);
130        assert_eq!(buf.len(), 1);
131    }
132}
shape_gc/barrier.rs

shape_gc/
barrier.rs
