dreck/
root.rs

1use std::{
2    alloc,
3    cell::{Cell, RefCell},
4    marker::PhantomData,
5    mem,
6    ptr::NonNull,
7};
8
9use crate::{
10    marker::Invariant,
11    ptr::{Color, GcBox, GcBoxHead, DynGcBoxPtr},
12    Bound, Gc, Owner, Trace,
13};
14
15/// Object passed to [`Trace::trace`] method, used to mark pointers.
16#[derive(Clone, Copy)]
17pub struct Tracer<'gc, 'own>(&'gc Root<'own>);
18
19impl<'gc, 'own> Tracer<'gc, 'own> {
20    /// Mark a pointer as alive.
21    pub fn mark<T: Trace<'own>>(self, ptr: Gc<'_, 'own, T>) {
22        unsafe {
23            if ptr.ptr.as_ref().head.color.get() != Color::White {
24                return;
25            }
26            ptr.ptr.as_ref().head.color.set(Color::Gray);
27
28            if T::needs_trace() {
29                let ptr: DynGcBoxPtr<'own, '_> = ptr.ptr.cast::<GcBox<'own, T>>();
30                let ptr: DynGcBoxPtr<'own, 'static> = mem::transmute(ptr);
31                self.0.grays.borrow_mut().push(ptr);
32            }
33        }
34    }
35}
36
37#[derive(Clone, Copy, PartialEq, Eq, Debug)]
38enum Phase {
39    Sleep,
40    Wake,
41    Mark,
42    Sweep,
43}
44
45/// A guard which will keep a value on the stack rooted for as long as it is alive.
46///
47/// This struct should not be used in safe code.
48pub struct RootGuard<'own>(*const Root<'own>);
49
50impl<'own> RootGuard<'own> {
51    /// Rebind a value to the lifetime of the root guard.
52    /// # Safety
53    /// This method should only ever be called with the object this root guard was created in
54    /// [`Root::root_gc`].
55    pub unsafe fn bind<R: Bound<'own>>(&self, r: R) -> R::Rebound {
56        crate::rebind(r)
57    }
58}
59
60impl<'cell> Drop for RootGuard<'cell> {
61    fn drop(&mut self) {
62        unsafe {
63            (*self.0).roots.borrow_mut().pop();
64        }
65    }
66}
67
68/// Root of the dreck GC, used for allocating [`Gc`] pointers and run collection.
69pub struct Root<'own> {
70    roots: RefCell<Vec<DynGcBoxPtr<'own, 'static>>>,
71
72    grays: RefCell<Vec<DynGcBoxPtr<'own, 'static>>>,
73    grays_again: RefCell<Vec<DynGcBoxPtr<'own, 'static>>>,
74
75    sweep: Option<DynGcBoxPtr<'own, 'static>>,
76    sweep_prev: Cell<Option<DynGcBoxPtr<'own, 'static>>>,
77
78    all: Cell<Option<DynGcBoxPtr<'own, 'static>>>,
79
80    total_allocated: Cell<usize>,
81    remembered_size: usize,
82    wakeup_total: usize,
83    allocation_debt: Cell<f64>,
84
85    phase: Cell<Phase>,
86
87    _own: Invariant<'own>,
88}
89
90impl<'own> Root<'own> {
91    const PAUSE_FACTOR: f64 = 0.5;
92    const TIMING_FACTOR: f64 = 1.5;
93    const MIN_SLEEP: usize = 4096;
94
95    /// Create a new `Root`.
96    ///
97    /// This function is unsafe as creating two roots with the same `'own` lifetime is unsound. Prefer 
98    /// the use of the [`new_root!`](crate::new_root!) macro.
99    ///
100    /// # Safety
101    /// The `'own` lifetime must be different from all other [`Root`] objects created.
102    pub unsafe fn new(owner: &Owner<'own>) -> Self {
103        Root {
104            roots: RefCell::new(Vec::new()),
105
106            grays: RefCell::new(Vec::new()),
107            grays_again: RefCell::new(Vec::new()),
108
109            sweep: None,
110            sweep_prev: Cell::new(None),
111
112            all: Cell::new(None),
113
114            total_allocated: Cell::new(0),
115            remembered_size: 0,
116            wakeup_total: Self::MIN_SLEEP,
117            allocation_debt: Cell::new(0.0),
118
119            phase: Cell::new(Phase::Sleep),
120            _own: owner.0,
121        }
122    }
123
124    pub(crate) unsafe fn add_raw<T: Trace<'own>>(&self, v: T) -> NonNull<GcBox<'own, T>> {
125        let layout = alloc::Layout::new::<GcBox<T>>();
126        let ptr = NonNull::new(alloc::alloc(layout).cast::<GcBox<T>>()).unwrap();
127
128        ptr.as_ptr().write(GcBox {
129            head: GcBoxHead {
130                color: Cell::new(Color::White),
131                next: Cell::new(self.all.get()),
132            },
133            value: v,
134        });
135
136        self.total_allocated
137            .set(self.total_allocated.get() + layout.size());
138
139        if self.phase.get() == Phase::Sleep && self.total_allocated.get() > self.wakeup_total {
140            self.phase.set(Phase::Wake);
141        }
142
143        if self.phase.get() != Phase::Sleep {
144            self.allocation_debt.set(
145                self.allocation_debt.get()
146                    + layout.size() as f64
147                    + layout.size() as f64 / Self::TIMING_FACTOR,
148            );
149        }
150
151        let dyn_ptr: DynGcBoxPtr = ptr;
152        self.all.set(Some(mem::transmute(dyn_ptr)));
153
154        if self.phase.get() == Phase::Sweep && self.sweep_prev.get().is_none() {
155            self.sweep_prev.set(self.all.get());
156        }
157
158        ptr
159    }
160
161
162    /// Allocated a value as a garbage collected pointer.
163    #[must_use]
164    pub fn add<'gc, T, R>(&'gc self, v: T) -> Gc<'gc, 'own, R>
165    where
166        T: Bound<'gc, Rebound = R>,
167        R: Trace<'own>,
168    {
169        unsafe {
170            let ptr = self.add_raw(crate::rebind(v));
171            Gc {
172                ptr,
173                _gc: PhantomData,
174                _own: Invariant::new(),
175            }
176        }
177    }
178
179    /// Indicate a point at which garbage collection can run.
180    ///
181    /// The GC will only run if enough objects have been allocated.
182    /// As the GC is incremental it will also only run only a part of the collection cycle.
183    pub fn collect(&mut self, _owner: &Owner<'own>) {
184        unsafe { self.inner_collect() };
185    }
186
187
188    /// Run a full cycle of the garbage collection.
189    ///
190    /// Unlike [`Root::collect`] this method will allways collect all unreachable Gc'd objects.
191    pub fn collect_full(&mut self, _owner: &Owner<'own>) {
192        self.allocation_debt.set(f64::INFINITY);
193        self.phase.set(Phase::Wake);
194        unsafe { self.inner_collect() };
195    }
196
197    /// Mark a pointer value as possibly containing new [`Gc`] pointers.
198    ///
199    /// In safe code you should never have to call this method as the [`Gc`] struct will manage
200    /// write barriers for you.
201    ///
202    /// If a type has an unsafe trace implementation and could ever contain new GC'd values within
203    /// itself, One must call this function on objects of that type before running collection, everytime that object could
204    /// possibly contain new GC'd values.
205    #[inline]
206    pub fn write_barrier<T: Trace<'own>>(&self, gc: Gc<'_, 'own, T>) {
207        if !T::needs_trace() {
208            return;
209        }
210        unsafe {
211            if self.phase.get() == Phase::Mark && gc.ptr.as_ref().head.color.get() == Color::Black {
212                gc.ptr.as_ref().head.color.set(Color::Gray);
213                let ptr: DynGcBoxPtr<'own, '_> = gc.ptr.cast::<GcBox<T>>();
214                let ptr: DynGcBoxPtr<'own, 'static> = mem::transmute(ptr);
215                self.grays_again.borrow_mut().push(ptr);
216            }
217        }
218    }
219
220    /// Rebind a pointer to the lifetime of this root guard.
221    ///
222    /// On should prefer the [`rebind!`](crate::rebind!) macro instead of this function as it is more permissive
223    /// with which pointers it allows rebinding.
224    pub fn rebind_to<'r, T: Trace<'own> + Bound<'r> + 'r>(
225        &'r self,
226        t: Gc<'_, 'own, T>,
227    ) -> Gc<'r, 'own, T::Rebound>
228    where
229        T::Rebound: Trace<'own>,
230    {
231        unsafe { crate::rebind(t) }
232    }
233
234    /// Root a gc pointer for the duration of root guard's lifetime.
235    /// Prefer the use of the [`root!`](crate::root!) macro.
236    ///
237    /// # Safety
238    /// - The `Root` object must outlife the returned `RootGuard`
239    /// - All `RootGuard`'s must be dropped in the reverse order of which they where created.
240    pub unsafe fn root_gc<T: Trace<'own>>(&self, t: Gc<'_, 'own, T>) -> RootGuard<'own> {
241        let ptr: DynGcBoxPtr<'own, '_> = t.ptr.cast::<GcBox<T>>();
242        let ptr: DynGcBoxPtr<'own, 'static> = std::mem::transmute(ptr);
243        self.roots.borrow_mut().push(ptr);
244        RootGuard(self)
245    }
246
247    unsafe fn inner_collect(&mut self) {
248        if self.phase.get() == Phase::Sleep {
249            return;
250        }
251
252        let work = self.allocation_debt.get();
253        let mut work_done = 0usize;
254
255        while work > work_done as f64 {
256            match self.phase.get() {
257                Phase::Wake => {
258                    self.sweep_prev.set(None);
259
260                    for root in self.roots.borrow().iter() {
261                        root.as_ref().head.color.set(Color::Black);
262                    }
263
264                    for root in self.roots.borrow().iter() {
265                        root.as_ref().value.trace(Tracer(self));
266                        work_done += mem::size_of_val(root.as_ref());
267                    }
268
269                    self.phase.set(Phase::Mark);
270                }
271                Phase::Mark => {
272                    let ptr = self.grays.borrow_mut().pop();
273                    if let Some(ptr) = ptr {
274                        work_done += mem::size_of_val(ptr.as_ref());
275                        ptr.as_ref().value.trace(Tracer(self));
276                        ptr.as_ref().head.color.set(Color::Black);
277                    } else if let Some(ptr) = self.grays_again.borrow_mut().pop() {
278                        ptr.as_ref().value.trace(Tracer(self));
279                        ptr.as_ref().head.color.set(Color::Black);
280                    } else {
281                        self.phase.set(Phase::Sweep);
282                        self.sweep = self.all.get();
283                        self.remembered_size = 0;
284                    }
285                }
286                Phase::Sweep => {
287                    if let Some(ptr) = self.sweep {
288                        self.sweep = ptr.as_ref().head.next.get();
289                        let layout = alloc::Layout::for_value(ptr.as_ref());
290
291                        if ptr.as_ref().head.color.get() == Color::White {
292                            if let Some(prev) = self.sweep_prev.get() {
293                                prev.as_ref().head.next.set(ptr.as_ref().head.next.get());
294                            } else {
295                                self.all.set(ptr.as_ref().head.next.get());
296                            }
297
298                            self.total_allocated
299                                .set(self.total_allocated.get() - layout.size());
300                        } else {
301                            self.remembered_size += layout.size();
302                            ptr.as_ref().head.color.set(Color::White);
303                            self.sweep_prev.set(Some(ptr));
304                        }
305                    } else {
306                        self.phase.set(Phase::Sleep);
307                        self.allocation_debt.set(0.0);
308                        self.wakeup_total = self.total_allocated.get()
309                            + ((self.remembered_size as f64 * Self::PAUSE_FACTOR)
310                                .round()
311                                .min(usize::MAX as f64) as usize)
312                                .max(Self::MIN_SLEEP);
313                        return;
314                    }
315                }
316                Phase::Sleep => break,
317            }
318        }
319    }
320}
dreck/root.rs

dreck/
root.rs
