cactusref/
drop.rs

1use alloc::alloc::{Allocator, Global, Layout};
2use alloc::vec;
3use core::mem::{self, MaybeUninit};
4use core::ptr;
5
6#[cfg(doc)]
7use crate::adopt::Adopt;
8use crate::hash::HashMap;
9use crate::link::{Kind, Link};
10use crate::rc::RcInnerPtr;
11use crate::Rc;
12
13unsafe impl<#[may_dangle] T> Drop for Rc<T> {
14    /// Drops the [`Rc`].
15    ///
16    /// This will decrement the strong reference count. If the strong reference
17    /// count reaches zero then the only other references (if any) are [`Weak`],
18    /// so we `drop` the inner value.
19    ///
20    /// [`Weak`]: crate::Weak
21    ///
22    /// If this `Rc` has adopted any other `Rc`s, drop will trace the reachable
23    /// object graph and detect if this `Rc` is part of an orphaned cycle. An
24    /// orphaned cycle is a cycle in which all members have no owned references
25    /// held by `Rc`s outside of the cycle.
26    ///
27    /// `Rc`s do not pay the cost of the reachability check unless they use
28    /// [`Adopt::adopt_unchecked`].
29    ///
30    /// [`Adopt::adopt_unchecked`]: crate::Adopt::adopt_unchecked
31    ///
32    /// # Examples
33    ///
34    /// ```
35    /// use cactusref::Rc;
36    ///
37    /// struct Foo;
38    ///
39    /// impl Drop for Foo {
40    ///     fn drop(&mut self) {
41    ///         println!("dropped!");
42    ///     }
43    /// }
44    ///
45    /// let foo  = Rc::new(Foo);
46    /// let foo2 = Rc::clone(&foo);
47    ///
48    /// drop(foo);    // Doesn't print anything
49    /// drop(foo2);   // Prints "dropped!"
50    /// ```
51    ///
52    /// ```
53    /// use cactusref::{Adopt, Rc};
54    ///
55    /// struct Foo(u8);
56    ///
57    /// impl Drop for Foo {
58    ///     fn drop(&mut self) {
59    ///         println!("dropped {}!", self.0);
60    ///     }
61    /// }
62    ///
63    /// let foo  = Rc::new(Foo(10));
64    /// let foo2 = Rc::new(Foo(20));
65    ///
66    /// unsafe {
67    ///     Rc::adopt_unchecked(&foo, &foo2);
68    ///     Rc::adopt_unchecked(&foo2, &foo);
69    /// }
70    ///
71    /// drop(foo);    // Doesn't print anything
72    /// drop(foo2);   // Prints "dropped 10!" and "dropped 20!"
73    /// ```
74    ///
75    /// # Cycle Detection and Deallocation Algorithm
76    ///
77    /// [`Rc::adopt_unchecked`] does explicit bookkeeping to store links to
78    /// adoptee `Rc`s.  These links form a graph of reachable objects which are
79    /// used to detect cycles.
80    ///
81    /// [`Rc::adopt_unchecked`]: crate::Rc::adopt_unchecked
82    ///
83    /// On drop, if an `Rc` has no links, it is dropped like a normal `Rc`. If
84    /// the `Rc` has links, `Drop` performs a breadth first search by traversing
85    /// the forward and backward links stored in each `Rc`. Deallocating cycles
86    /// requires correct use of [`Adopt::adopt_unchecked`] and [`Adopt::unadopt`]
87    /// to perform the reachability bookkeeping.
88    ///
89    /// [`Adopt::adopt_unchecked`]: crate::Adopt::adopt_unchecked
90    /// [`Adopt::unadopt`]: crate::Adopt::unadopt
91    ///
92    /// After determining all reachable objects, `Rc` reduces the graph to
93    /// objects that form a cycle by performing pairwise reachability checks.
94    /// During this step, for each object in the cycle, `Rc` counts the number
95    /// of refs held by other objects in the cycle.
96    ///
97    /// Using the cycle-held references, `Rc` computes whether the object graph
98    /// is reachable by any non-cycle nodes by comparing strong counts.
99    ///
100    /// If the cycle is orphaned, `Rc` busts all the link structures and
101    /// deallocates each object.
102    ///
103    /// ## Performance
104    ///
105    /// Cycle detection uses breadth first search to trace the object graph.
106    /// The runtime complexity of detecting a cycle is `O(links + nodes)` where
107    /// links is the number of adoptions that are alive and nodes is the number
108    /// of objects in the cycle.
109    ///
110    /// Determining whether the cycle is orphaned builds on cycle detection and
111    /// iterates over all nodes in the graph to see if their strong count is
112    /// greater than the number of references in the cycle. The runtime
113    /// complexity of finding an orphaned cycle is `O(links + nodes)` where
114    /// links is the number of adoptions that are alive and nodes is the number
115    /// objects in the cycle.
116    fn drop(&mut self) {
117        // If `self` is held in a cycle, as we deallocate members of the cycle,
118        // they will drop their refs to `self`. To prevent a double free, mark
119        // nodes as dead if they have already been deallocated and short
120        // circuit.
121        if self.inner().is_dead() {
122            return;
123        }
124
125        // If a drop is occuring it is because there was an existing `Rc` which
126        // is maintaining a strong count. Decrement the strong count on drop,
127        // even if this `Rc` is dead. This ensures `Weak::upgrade` behaves
128        // correctly for deallocated cycles and does not cause a use-after-free.
129        self.inner().dec_strong();
130
131        unsafe {
132            // If links is empty, the object is either not in a cycle or
133            // part of a cycle that has been link busted for deallocation.
134            if self.inner().links().borrow().is_empty() {
135                // If the object was never in a cycle, `dec_strong` above will
136                // kill the `Rc`.
137                //
138                // If the object was in a cycle, the `Rc` will only be dead if
139                // all strong references to it have been dropped.
140                if self.inner().is_dead() {
141                    drop_unreachable(self);
142                }
143                // otherwise, ignore the pointed to object; it will be dropped
144                // when there are no more remaining strong references to it.
145                return;
146            }
147            if self.inner().is_dead() {
148                drop_unreachable_with_adoptions(self);
149                return;
150            }
151            if let Some(cycle) = Self::orphaned_cycle(self) {
152                drop_cycle(cycle);
153                return;
154            }
155            debug!("cactusref drop skipped, Rc is reachable");
156        }
157    }
158}
159
160unsafe fn drop_unreachable<T>(this: &mut Rc<T>) {
161    debug!("cactusref detected unreachable Rc");
162    let forward = Link::forward(this.ptr);
163    let backward = Link::backward(this.ptr);
164    // Remove reverse links so `this` is not included in cycle detection for
165    // objects that had adopted `this`. This prevents a use-after-free in
166    // `Rc::orphaned_cycle`.
167    let links = this.inner().links();
168    for (item, &strong) in links.borrow().iter() {
169        match item.kind() {
170            Kind::Forward => {
171                let mut links = links.borrow_mut();
172                links.remove(forward, strong);
173                links.remove(backward, strong);
174            }
175            Kind::Loopback => {
176                let mut links = links.borrow_mut();
177                links.remove(*item, strong);
178            }
179            Kind::Backward => {}
180        }
181    }
182
183    let rcbox = this.ptr.as_ptr();
184    // Mark `this` as pending deallocation. This is not strictly necessary since
185    // `this` is unreachable, but `kill`ing `this ensures we don't double-free.
186    if !(*rcbox).is_uninit() {
187        trace!("cactusref deallocating unreachable RcBox {:p}", rcbox);
188        // Mark the `RcBox` as uninitialized so we can make its `MaybeUninit`
189        // fields uninhabited.
190        (*rcbox).make_uninit();
191
192        // Move `T` out of the `RcBox`. Dropping an uninitialized `MaybeUninit`
193        // has no effect.
194        let inner = mem::replace(&mut (*rcbox).value, MaybeUninit::uninit());
195        // destroy the contained `T`.
196        drop(inner.assume_init());
197        // Move the links `HashMap` out of the `RcBox`. Dropping an uninitialized
198        // `MaybeUninit` has no effect.
199        let links = mem::replace(&mut (*rcbox).links, MaybeUninit::uninit());
200        // Destroy the heap-allocated links.
201        drop(links.assume_init());
202    }
203
204    // remove the implicit "strong weak" pointer now that we've destroyed the
205    // contents.
206    (*rcbox).dec_weak();
207
208    if (*rcbox).weak() == 0 {
209        // SAFETY: `T` is `Sized`, which means `Layout::for_value_raw` is always
210        // safe to call.
211        let layout = Layout::for_value_raw(this.ptr.as_ptr());
212        Global.deallocate(this.ptr.cast(), layout);
213    }
214}
215
216unsafe fn drop_cycle<T>(cycle: HashMap<Link<T>, usize>) {
217    debug!(
218        "cactusref detected orphaned cycle with {} objects",
219        cycle.len()
220    );
221    // Iterate over all the nodes in the cycle, bust all of the links. All nodes
222    // in the cycle are reachable by other nodes in the cycle, so removing
223    // all cycle-internal links won't result in a leak.
224    for (ptr, &refcount) in &cycle {
225        trace!(
226            "cactusref dropping {:?} member of orphaned cycle with refcount {}",
227            ptr,
228            refcount
229        );
230
231        // Remove reverse links so `this` is not included in cycle detection for
232        // objects that had adopted `this`. This prevents a use-after-free in
233        // `Rc::orphaned_cycle`.
234        //
235        // Because the entire cycle is unreachable, the only forward and
236        // backward links are to objects in the cycle that we are about to
237        // deallocate. This allows us to bust the cycle detection by clearing
238        // all links.
239        let rcbox = ptr.as_ptr();
240        let cycle_strong_refs = {
241            let mut links = (*rcbox).links().borrow_mut();
242            links
243                .extract_if(|link, _| {
244                    if let Kind::Forward | Kind::Loopback = link.kind() {
245                        cycle.contains_key(link)
246                    } else {
247                        false
248                    }
249                })
250                .map(|(link, count)| {
251                    if let Kind::Forward = link.kind() {
252                        count
253                    } else {
254                        0
255                    }
256                })
257                .sum::<usize>()
258        };
259
260        // To be in a cycle, at least one `value` field in an `RcBox` in the
261        // cycle holds a strong reference to `this`. Mark all nodes in the cycle
262        // as dead so when we deallocate them via the `value` pointer we don't
263        // get a double-free.
264        for _ in 0..cycle_strong_refs.min((*rcbox).strong()) {
265            (*rcbox).dec_strong();
266        }
267    }
268
269    let mut inners = vec![];
270    for (ptr, _) in &cycle {
271        if !ptr.is_dead() {
272            // This object continues to be referenced outside the cycle in
273            // another part of the graph.
274            continue;
275        }
276
277        let ptr = ptr.into_raw_non_null();
278        let rcbox = ptr.as_ptr();
279
280        if !(*rcbox).is_uninit() {
281            // Mark the `RcBox` as uninitialized so we can make its
282            // `MaybeUninit` fields uninhabited.
283            (*rcbox).make_uninit();
284
285            // Move `T` out of the `RcBox`. Dropping an uninitialized
286            // `MaybeUninit` has no effect.
287            let inner = mem::replace(&mut (*rcbox).value, MaybeUninit::uninit());
288            // Move the links `HashMap` out of the `RcBox`. Dropping an
289            // uninitialized `MaybeUninit` has no effect.
290            let links = mem::replace(&mut (*rcbox).links, MaybeUninit::uninit());
291            trace!("cactusref deconstructed member {:p} of orphan cycle", rcbox);
292            // Move `T` and the `HashMap` out of the `RcBox` to be dropped after
293            // busting the cycle.
294            inners.push((inner.assume_init(), links.assume_init()));
295        }
296    }
297    // Drop and deallocate all `T` and `HashMap` objects.
298    drop(inners);
299
300    let unreachable_cycle_participants = cycle.into_iter().map(|(ptr, _)| ptr).filter(|ptr| {
301        // Filter the set of cycle participants so we only drop `Rc`s that are
302        // dead.
303        //
304        // If an `Rc` is not dead, it continues to be referenced outside of the
305        // cycle, for example:
306        //
307        //  | Rc | -> | Rc | -> | Rc | <-> | Rc |
308        //    ^                   |
309        //    |-------------------|
310        //
311        // This object continues to be referenced outside the cycle in another
312        // part of the graph.
313        ptr.is_dead()
314    });
315
316    for ptr in unreachable_cycle_participants {
317        let ptr = ptr.into_raw_non_null();
318        trace!(
319            "cactusref deallocating RcBox after dropping item {:?} in orphaned cycle",
320            ptr
321        );
322
323        let rcbox = ptr.as_ptr();
324        // remove the implicit "strong weak" pointer now that we've destroyed
325        // the contents.
326        (*rcbox).dec_weak();
327
328        if (*rcbox).weak() == 0 {
329            trace!(
330                "no more weak references, deallocating layout for item {:?} in orphaned cycle",
331                ptr
332            );
333            // SAFETY: `T` is `Sized`, which means `Layout::for_value_raw` is
334            // always safe to call.
335            let layout = Layout::for_value_raw(ptr.as_ptr());
336            Global.deallocate(ptr.cast(), layout);
337        }
338    }
339}
340
341// Drop an `Rc` that is unreachable, but has adopted other `Rc`s.
342//
343// Unreachable `Rc`s have a strong count of zero, but because they have adopted
344// other `Rc`s, other `Rc`s have back links to `this`.
345//
346// Before dropping `this`, we must traverse `this`'s forward links to collect
347// all of `this`'s adoptions. Then, remove `this` from it's adoptions back
348// links. By pruning back links in the rest of the graph, we can ensure that
349// `this` and its `RcBox` are not referenced and can be safely deallocated.
350//
351// # Diagram
352//
353//          this
354// |--------------------|
355// | ptr:    RcBox      |
356// |      |----------| <--------|
357// |      | value: T |  |       |
358// |      | links: ------> | other RcBox |
359// |      |   |----------> | other RcBox |
360// |      |          |  |       |
361// |      |----------| <--------|
362// |--------------------|
363unsafe fn drop_unreachable_with_adoptions<T>(this: &mut Rc<T>) {
364    // Construct a forward and back link from `this` so we can
365    // purge it from the adopted `links`.
366    let forward = Link::forward(this.ptr);
367    let backward = Link::backward(this.ptr);
368    // `this` is unreachable but may have been adopted and dropped.
369    //
370    // Iterate over all of the other nodes in the graph that have links to
371    // `this` and remove all of the adoptions. By doing so, when other graph
372    // participants are dropped, they do not try to deallocate `this`.
373    //
374    // `this` is fully removed from the graph.
375    let links = this.inner().links();
376    for (item, &strong) in links.borrow().iter() {
377        // if `this` has adopted itself, we don't need to clear these links in
378        // the loop to avoid an already borrowed error.
379        if ptr::eq(this.inner(), item.as_ptr()) {
380            continue;
381        }
382        let mut links = item.as_ref().links().borrow_mut();
383        // The cycle counts don't distinguish which nodes the cycle strong
384        // counts are from, so purge as many strong counts as possible.
385        //
386        // Additionally, `item` may have forward adoptions for `this`, so
387        // purge those as well.
388        //
389        // `Links::remove` ensures the count for forward and back links will not
390        // underflow.
391        links.remove(forward, strong);
392        links.remove(backward, strong);
393    }
394    // Bust the links for this since it is now unreachable and set to be
395    // deallocated.
396    links.borrow_mut().clear();
397
398    let rcbox = this.ptr.as_ptr();
399    // Mark `this` as pending deallocation. This is not strictly necessary since
400    // `this` is unreachable, but `kill`ing `this ensures we don't double-free.
401    if !(*rcbox).is_uninit() {
402        trace!(
403            "cactusref deallocating RcBox after dropping adopted and unreachable item {:p} in the object graph",
404            rcbox
405        );
406        // Mark the `RcBox` as uninitialized so we can make its `MaybeUninit`
407        // fields uninhabited.
408        (*rcbox).make_uninit();
409
410        // Move `T` out of the `RcBox`. Dropping an uninitialized `MaybeUninit`
411        // has no effect.
412        let inner = mem::replace(&mut (*rcbox).value, MaybeUninit::uninit());
413        // destroy the contained `T`.
414        drop(inner.assume_init());
415        // Move the links `HashMap` out of the `RcBox`. Dropping an uninitialized
416        // `MaybeUninit` has no effect.
417        let links = mem::replace(&mut (*rcbox).links, MaybeUninit::uninit());
418        // Destroy the heap-allocated links.
419        drop(links.assume_init());
420    }
421
422    // remove the implicit "strong weak" pointer now that we've destroyed the
423    // contents.
424    (*rcbox).dec_weak();
425
426    if (*rcbox).weak() == 0 {
427        trace!(
428            "no more weak references, deallocating layout for adopted and unreachable item {:?} in the object graph",
429            this.ptr
430        );
431        // SAFETY: `T` is `Sized`, which means `Layout::for_value_raw` is always
432        // safe to call.
433        let layout = Layout::for_value_raw(this.ptr.as_ptr());
434        Global.deallocate(this.ptr.cast(), layout);
435    }
436}