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}