gc_arena/
dynamic_roots.rs

1use alloc::{
2    rc::{Rc, Weak},
3    vec::Vec,
4};
5use core::{fmt, mem};
6
7use crate::lock::RefLock;
8use crate::{
9    barrier::{unlock, Write},
10    metrics::Metrics,
11};
12use crate::{Collect, Gc, Mutation, Root, Rootable};
13
14/// A way of registering GC roots dynamically.
15///
16/// Use this type as (a part of) an [`Arena`](crate::Arena) root to enable dynamic rooting of
17/// GC'd objects through [`DynamicRoot`] handles.
18// SAFETY: Allows us to conert `Gc<'gc>` pointers to `Gc<'static>` and back, and this is VERY
19// sketchy. We know it is safe because:
20//   1) The `DynamicRootSet` must be created inside an arena and is branded with an invariant `'gc`
21//      lifetime.
22//   2) The inner `id` inside the `DynamicRootSet` is unique for as long as the `DynamicRootSet` or
23//      any `DynamicRoot` still references it.
24//   3) The `id` is stored inside each `DynamicRoot` and checked against the one in the set, and
25//      a match lets us know that this `Gc` must have originated from *this* set, so it is safe to
26//      cast it back to whatever our current `'gc` lifetime is.
27#[derive(Copy, Clone)]
28pub struct DynamicRootSet<'gc>(Gc<'gc, Inner<'gc>>);
29
30unsafe impl<'gc> Collect for DynamicRootSet<'gc> {
31    fn trace(&self, cc: &crate::Collection) {
32        self.0.trace(cc);
33    }
34}
35
36impl<'gc> DynamicRootSet<'gc> {
37    /// Creates a new, empty root set.
38    pub fn new(mc: &Mutation<'gc>) -> Self {
39        DynamicRootSet(Gc::new(
40            mc,
41            Inner {
42                handles: RefLock::new(Vec::new()),
43                metrics: mc.metrics().clone(),
44                set_id: Rc::new(SetId {}),
45            },
46        ))
47    }
48
49    /// Puts a root inside this root set.
50    ///
51    /// The returned handle can be freely stored outside the current arena,
52    /// and will keep the root alive across garbage collections.
53    pub fn stash<R: for<'a> Rootable<'a>>(
54        &self,
55        mc: &Mutation<'gc>,
56        root: Root<'gc, R>,
57    ) -> DynamicRoot<R> {
58        let handle = Rc::new(Handle {
59            set_id: self.0.set_id.clone(),
60            root,
61        });
62
63        Inner::adopt_handle(&Gc::write(mc, self.0), &handle);
64
65        DynamicRoot {
66            handle: unsafe {
67                mem::transmute::<Rc<Handle<Root<'gc, R>>>, Rc<Handle<Root<'static, R>>>>(handle)
68            },
69        }
70    }
71
72    /// Gets immutable access to the given root.
73    ///
74    /// # Panics
75    ///
76    /// Panics if the handle doesn't belong to this root set. For the non-panicking variant, use
77    /// [`try_fetch`](Self::try_fetch).
78    #[inline]
79    pub fn fetch<'a, R: for<'r> Rootable<'r>>(&self, root: &'a DynamicRoot<R>) -> &'a Root<'gc, R> {
80        if self.contains(root) {
81            unsafe { &*root.as_ptr() }
82        } else {
83            panic!("mismatched root set")
84        }
85    }
86
87    /// Gets immutable access to the given root, or returns an error if the handle doesn't belong
88    /// to this root set.
89    #[inline]
90    pub fn try_fetch<'a, R: for<'r> Rootable<'r>>(
91        &self,
92        root: &'a DynamicRoot<R>,
93    ) -> Result<&'a Root<'gc, R>, MismatchedRootSet> {
94        if self.contains(root) {
95            unsafe { Ok(&*root.as_ptr()) }
96        } else {
97            Err(MismatchedRootSet(()))
98        }
99    }
100
101    /// Tests if the given handle belongs to this root set.
102    #[inline]
103    pub fn contains<R: for<'r> Rootable<'r>>(&self, root: &DynamicRoot<R>) -> bool {
104        let ours = Rc::as_ptr(&self.0.set_id);
105        let theirs = Rc::as_ptr(&root.handle.set_id);
106        ours == theirs
107    }
108}
109
110/// An unbranded, reference-counted handle to a GC root held in some [`DynamicRootSet`].
111///
112/// A `DynamicRoot` can freely be stored outside GC arenas; in exchange, all accesses to the held
113/// object must go through the [`DynamicRootSet`] from which it was created.
114///
115/// This handle is cheaply clonable: all clones will refer to the *same* object, which will be
116/// dropped when the last surviving handle goes out of scope.
117pub struct DynamicRoot<R: for<'gc> Rootable<'gc>> {
118    handle: Rc<Handle<Root<'static, R>>>,
119}
120
121impl<R: for<'gc> Rootable<'gc>> Clone for DynamicRoot<R> {
122    fn clone(&self) -> Self {
123        Self {
124            handle: self.handle.clone(),
125        }
126    }
127}
128
129impl<R: for<'gc> Rootable<'gc>> DynamicRoot<R> {
130    /// Get a pointer to the held object.
131    ///
132    /// # Safety
133    ///
134    /// The pointer will never be dangling as long as at least one `DynamicRoot` is alive, but
135    /// using the object behind this pointer is extremely dangerous.
136    ///
137    /// Firstly, the `'gc` lifetime returned here is unbound, so it is meaningless and can allow
138    /// improper mixing of objects across arenas.
139    ///
140    /// Secondly, though the pointer to the object *itself* will not be dangling, any garbage
141    /// collected pointers the object holds *will* be dangling if the [`DynamicRootSet`] backing
142    /// this root has been collected.
143    #[inline]
144    pub fn as_ptr<'gc>(&self) -> *const Root<'gc, R> {
145        unsafe { mem::transmute::<&Root<'static, R>, &Root<'gc, R>>(&self.handle.root) as *const _ }
146    }
147}
148
149/// Error returned when trying to fetch a [`DynamicRoot`] from the wrong [`DynamicRootSet`].
150#[derive(Debug)]
151pub struct MismatchedRootSet(());
152
153impl fmt::Display for MismatchedRootSet {
154    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
155        f.write_str("mismatched root set")
156    }
157}
158
159#[cfg(feature = "std")]
160impl std::error::Error for MismatchedRootSet {}
161
162// The address of an allocated `SetId` type uniquely identifies a single `DynamicRootSet`.
163struct SetId {}
164
165struct HandleStore<'gc> {
166    handle: Weak<Handle<dyn Collect + 'gc>>,
167    root_size: usize,
168}
169
170struct Inner<'gc> {
171    handles: RefLock<Vec<HandleStore<'gc>>>,
172    metrics: Metrics,
173    set_id: Rc<SetId>,
174}
175
176fn size_of_handle_list<'gc>(list: &Vec<HandleStore<'gc>>) -> usize {
177    list.capacity() * mem::size_of::<Weak<Handle<dyn Collect + 'gc>>>()
178}
179
180impl<'gc> Inner<'gc> {
181    fn adopt_handle<T: Collect + 'gc>(this: &Write<Self>, handle: &Rc<Handle<T>>) {
182        // We count size_of::<T>() as part of the arena heap to encourage collection of the handle
183        // list. *Technically* this doesn't include the full size of the Rc allocation (strong and
184        // weak counts) but this does not matter very much.
185        let root_size = mem::size_of::<T>();
186        this.metrics.mark_external_allocation(root_size);
187
188        let handles = unlock!(this, Inner, handles);
189        let mut handles = handles.borrow_mut();
190        let old_size = size_of_handle_list(&handles);
191        handles.push(HandleStore {
192            handle: Rc::<Handle<T>>::downgrade(handle),
193            root_size,
194        });
195        let new_size = size_of_handle_list(&handles);
196
197        if new_size > old_size {
198            this.metrics.mark_external_allocation(new_size - old_size);
199        } else if old_size > new_size {
200            this.metrics.mark_external_deallocation(old_size - new_size);
201        }
202    }
203}
204
205impl<'gc> Drop for Inner<'gc> {
206    fn drop(&mut self) {
207        let handles = self.handles.borrow();
208        self.metrics
209            .mark_external_deallocation(handles.iter().map(|s| s.root_size).sum());
210        self.metrics
211            .mark_external_deallocation(size_of_handle_list(&self.handles.borrow()));
212    }
213}
214
215unsafe impl<'gc> Collect for Inner<'gc> {
216    fn trace(&self, cc: &crate::Collection) {
217        // SAFETY: We do not adopt any new pointers so we don't need a write barrier.
218        // We cheat horribly and filter out dead handles during tracing. Since we have to go
219        // through the entire list of roots anyway, this is cheaper than filtering on e.g.
220        // stashing new roots.
221        let handles = unsafe { self.handles.as_ref_cell() };
222        handles.borrow_mut().retain(|store| {
223            if let Some(handle) = store.handle.upgrade() {
224                handle.root.trace(cc);
225                true
226            } else {
227                cc.metrics().mark_external_deallocation(store.root_size);
228                false
229            }
230        });
231    }
232}
233
234struct Handle<T: ?Sized> {
235    // Store a clone of `Rc<SetId>` so that we ensure the `Rc<SetId>` lives as long as any extant
236    // handle.
237    set_id: Rc<SetId>,
238    root: T,
239}
gc_arena/dynamic_roots.rs

gc_arena/
dynamic_roots.rs
