gcmodule/
cc.rs

1use crate::collect;
2use crate::collect::AbstractObjectSpace;
3use crate::collect::ObjectSpace;
4use crate::debug;
5use crate::ref_count::RefCount;
6use crate::trace::Trace;
7use crate::trace::Tracer;
8use std::cell::UnsafeCell;
9use std::mem;
10use std::mem::ManuallyDrop;
11use std::ops::Deref;
12use std::ops::DerefMut;
13use std::panic::UnwindSafe;
14use std::ptr::NonNull;
15
16// Types not tracked by the cycle collector:
17//
18//     CcBox<T>
19//     +-----------+ <---+--- Cc<T> (pointer)
20//     | ref_count |     |
21//     +-----------+     +--- Cc<T> (pointer)
22//     | T (data)  |
23//     +-----------+
24//
25// Types not tracked by the cycle collector:
26//
27//     CcBoxWithHeader<T>
28//     +----------------------+
29//     | GcHeader | next      | (GcHeader is in a linked list)
30//     |          | prev      |
31//     |          | vptr<T>   |
32//     +----------------------+ <---+--- Cc<T> (pointer)
33//     | CcBox<T> | ref_count |     |
34//     |          | T (data)  |     +--- Cc<T> (pointer)
35//     +----------------------+
36
37/// The data shared by multiple `RawCc<T, O>` pointers.
38#[repr(C)]
39pub(crate) struct RawCcBox<T: ?Sized, O: AbstractObjectSpace> {
40    /// The lowest REF_COUNT_SHIFT bits are used for metadata.
41    /// The higher bits are used for ref count.
42    pub(crate) ref_count: O::RefCount,
43
44    #[cfg(test)]
45    pub(crate) name: String,
46
47    value: UnsafeCell<ManuallyDrop<T>>,
48}
49
50/// The real layout if `T` is tracked by the collector. The main APIs still use
51/// the `CcBox` type. This type is only used for allocation and deallocation.
52///
53/// This is a private type.
54#[repr(C)]
55pub struct RawCcBoxWithGcHeader<T: ?Sized, O: AbstractObjectSpace> {
56    header: O::Header,
57    cc_box: RawCcBox<T, O>,
58}
59
60/// A single-threaded reference-counting pointer that integrates
61/// with cyclic garbage collection.
62///
63/// See [module level documentation](index.html) for more details.
64///
65/// [`Cc`](type.Cc.html) is not thread-safe. It does not implement `Send`
66/// or `Sync`:
67///
68/// ```compile_fail
69/// use std::ops::Deref;
70/// use gcmodule::Cc;
71/// let cc = Cc::new(5);
72/// std::thread::spawn(move || {
73///     println!("{}", cc.deref());
74/// });
75/// ```
76pub type Cc<T> = RawCc<T, ObjectSpace>;
77
78/// Low-level type for [`Cc<T>`](type.Cc.html).
79pub struct RawCc<T: ?Sized, O: AbstractObjectSpace>(NonNull<RawCcBox<T, O>>);
80
81// `ManuallyDrop<T>` does not implement `UnwindSafe`. But `CcBox::drop` does
82// make sure `T` is dropped. If `T` is unwind-safe, so does `CcBox<T>`.
83impl<T: UnwindSafe + ?Sized> UnwindSafe for RawCcBox<T, ObjectSpace> {}
84
85// `NonNull` does not implement `UnwindSafe`. But `Cc` only uses it
86// as a "const" pointer. If `T` is unwind-safe, so does `Cc<T>`.
87impl<T: UnwindSafe + ?Sized> UnwindSafe for Cc<T> {}
88
89/// Type-erased `Cc<T>` with interfaces needed by GC.
90///
91/// This is a private type.
92pub trait CcDyn {
93    /// Returns the reference count for cycle detection.
94    fn gc_ref_count(&self) -> usize;
95
96    /// Visit referents for cycle detection.
97    fn gc_traverse(&self, tracer: &mut Tracer);
98
99    /// Get an cloned `Cc<dyn Trace>`. This has 2 purposes:
100    /// - Keep a reference so `CcBox<T>` is not released in the next step.
101    ///   So metadata like `ref_count` can still be read.
102    /// - Operate on the object.
103    fn gc_clone(&self) -> Box<dyn GcClone>;
104
105    #[cfg(feature = "debug")]
106    /// Name used in collect.rs.
107    fn gc_debug_name(&self) -> String {
108        "?".to_string()
109    }
110}
111
112/// Type-erased gc_clone result.
113///
114/// This is a private type.
115pub trait GcClone {
116    /// Force drop the value T.
117    fn gc_drop_t(&self);
118
119    /// Returns the reference count. This is useful for verification.
120    fn gc_ref_count(&self) -> usize;
121}
122
123/// A dummy implementation without drop side-effects.
124pub(crate) struct CcDummy;
125
126impl CcDummy {
127    pub(crate) fn ccdyn_vptr() -> *mut () {
128        let mut dummy = CcDummy;
129        // safety: To access vtable pointer. Stable API cannot do it.
130        let fat_ptr: [*mut (); 2] = unsafe { mem::transmute(&mut dummy as &mut dyn CcDyn) };
131        fat_ptr[1]
132    }
133}
134
135impl CcDyn for CcDummy {
136    fn gc_ref_count(&self) -> usize {
137        1
138    }
139    fn gc_traverse(&self, _tracer: &mut Tracer) {}
140    fn gc_clone(&self) -> Box<dyn GcClone> {
141        panic!("bug: CcDummy::gc_clone should never be called");
142    }
143}
144
145impl<T: Trace> Cc<T> {
146    /// Constructs a new [`Cc<T>`](type.Cc.html) in a thread-local storage.
147    ///
148    /// To collect cycles, use [`collect_thread_cycles`](fn.collect_thread_cycles.html).
149    pub fn new(value: T) -> Cc<T> {
150        collect::THREAD_OBJECT_SPACE.with(|space| Self::new_in_space(value, space))
151    }
152}
153
154impl<T: Trace, O: AbstractObjectSpace> RawCc<T, O> {
155    /// Constructs a new [`Cc<T>`](type.Cc.html) in the given
156    /// [`ObjectSpace`](struct.ObjectSpace.html).
157    ///
158    /// To collect cycles, call `ObjectSpace::collect_cycles()`.
159    pub(crate) fn new_in_space(value: T, space: &O) -> Self {
160        let is_tracked = T::is_type_tracked();
161        let cc_box = RawCcBox {
162            ref_count: space.new_ref_count(is_tracked),
163            value: UnsafeCell::new(ManuallyDrop::new(value)),
164            #[cfg(test)]
165            name: debug::NEXT_DEBUG_NAME.with(|n| n.get().to_string()),
166        };
167        let ccbox_ptr: *mut RawCcBox<T, O> = if is_tracked {
168            // Create a GcHeader before the CcBox. This is similar to cpython.
169            let header = space.empty_header();
170            let cc_box_with_header = RawCcBoxWithGcHeader { header, cc_box };
171            let mut boxed = Box::new(cc_box_with_header);
172            // Fix-up fields in GcHeader. This is done after the creation of the
173            // Box so the memory addresses are stable.
174            space.insert(&mut boxed.header, &boxed.cc_box);
175            debug_assert_eq!(
176                mem::size_of::<O::Header>() + mem::size_of::<RawCcBox<T, O>>(),
177                mem::size_of::<RawCcBoxWithGcHeader<T, O>>()
178            );
179            let ptr: *mut RawCcBox<T, O> = &mut boxed.cc_box;
180            Box::leak(boxed);
181            ptr
182        } else {
183            Box::into_raw(Box::new(cc_box))
184        };
185        // safety: ccbox_ptr cannot be null from the above code.
186        let non_null = unsafe { NonNull::new_unchecked(ccbox_ptr) };
187        let result = Self(non_null);
188        if is_tracked {
189            debug::log(|| (result.debug_name(), "new (CcBoxWithGcHeader)"));
190        } else {
191            debug::log(|| (result.debug_name(), "new (CcBox)"));
192        }
193        debug_assert_eq!(result.ref_count(), 1);
194        result
195    }
196
197    /// Convert to `RawCc<dyn Trace>`.
198    pub fn into_dyn(self) -> RawCc<dyn Trace, O> {
199        #[cfg(feature = "nightly")]
200        {
201            // Requires CoerceUnsized, which is currently unstable.
202            self
203        }
204
205        // safety: Trait object magic. Test by test_dyn_downcast.
206        #[cfg(not(feature = "nightly"))]
207        unsafe {
208            // XXX: This depends on rust internals. But it works on stable.
209            // Replace this with CoerceUnsized once that becomes stable.
210            // Cc<dyn Trace> has 2 usize values: The first one is the same
211            // as Cc<T>. The second one is the vtable. The vtable pointer
212            // is the same as the second pointer of `&dyn Trace`.
213            let mut fat_ptr: [usize; 2] = mem::transmute(self.inner().deref() as &dyn Trace);
214            let self_ptr: usize = mem::transmute(self);
215            fat_ptr[0] = self_ptr;
216            mem::transmute(fat_ptr)
217        }
218    }
219}
220
221impl<T: Trace + Clone> Cc<T> {
222    /// Update the value `T` in a copy-on-write way.
223    ///
224    /// If the ref count is 1, the value is updated in-place.
225    /// Otherwise a new `Cc<T>` will be created.
226    pub fn update_with(&mut self, mut update_func: impl FnMut(&mut T)) {
227        let need_clone = self.ref_count() > 1;
228        if need_clone {
229            let mut value = <Cc<T>>::deref(self).clone();
230            update_func(&mut value);
231            *self = Cc::new(value);
232        } else {
233            let value_ptr: *mut ManuallyDrop<T> = self.inner().value.get();
234            let value_mut: &mut T = unsafe { &mut *value_ptr }.deref_mut();
235            update_func(value_mut);
236        }
237    }
238}
239
240impl<T: ?Sized, O: AbstractObjectSpace> RawCcBox<T, O> {
241    #[inline]
242    fn header_ptr(&self) -> *const () {
243        self.header() as *const _ as _
244    }
245
246    #[inline]
247    fn header(&self) -> &O::Header {
248        debug_assert!(self.is_tracked());
249        // safety: See `Cc::new`. GcHeader is before CcBox for tracked objects.
250        unsafe { cast_ref(self, -(mem::size_of::<O::Header>() as isize)) }
251    }
252
253    #[inline]
254    fn is_tracked(&self) -> bool {
255        self.ref_count.is_tracked()
256    }
257
258    #[inline]
259    fn is_dropped(&self) -> bool {
260        self.ref_count.is_dropped()
261    }
262
263    #[inline]
264    fn inc_ref(&self) -> usize {
265        self.ref_count.inc_ref()
266    }
267
268    #[inline]
269    fn dec_ref(&self) -> usize {
270        self.ref_count.dec_ref()
271    }
272
273    #[inline]
274    fn ref_count(&self) -> usize {
275        self.ref_count.ref_count()
276    }
277
278    #[inline]
279    fn set_dropped(&self) -> bool {
280        self.ref_count.set_dropped()
281    }
282
283    #[inline]
284    pub(crate) fn drop_t(&self) {
285        let already_dropped = self.set_dropped();
286        if !already_dropped {
287            debug::log(|| (self.debug_name(), "drop (T)"));
288            // safety: is_dropped() check ensures T is only dropped once. Other
289            // places (ex. gc collector) ensure that T is no longer accessed.
290            unsafe { ManuallyDrop::drop(&mut *(self.value.get())) };
291        }
292    }
293
294    pub(crate) fn trace_t(&self, tracer: &mut Tracer) {
295        if !self.is_tracked() {
296            return;
297        }
298        debug::log(|| (self.debug_name(), "trace"));
299        // For other non-`Cc<T>` container types, `trace` visit referents,
300        // is recursive, and does not call `tracer` directly. For `Cc<T>`,
301        // `trace` stops here, is non-recursive, and does apply `tracer`
302        // to the actual `GcHeader`. It's expected that the upper layer
303        // calls `gc_traverse` on everything (not just roots).
304        tracer(self.header_ptr());
305    }
306
307    pub(crate) fn debug_name(&self) -> String {
308        #[cfg(test)]
309        {
310            self.name.clone()
311        }
312        #[cfg(not(test))]
313        {
314            #[allow(unused_mut)]
315            let mut result = format!("{} at {:p}", std::any::type_name::<T>(), &self.value);
316
317            #[cfg(all(feature = "debug", feature = "nightly"))]
318            {
319                if !self.is_dropped() && crate::debug::GC_DROPPING.with(|t| !t.get()) {
320                    let debug = self.deref().optional_debug();
321                    if !debug.is_empty() {
322                        result += &format!(" {}", debug);
323                    }
324                }
325            }
326
327            return result;
328        }
329    }
330}
331
332#[cfg(all(feature = "debug", feature = "nightly"))]
333pub(crate) trait OptionalDebug {
334    fn optional_debug(&self) -> String;
335}
336
337#[cfg(all(feature = "debug", feature = "nightly"))]
338impl<T: ?Sized> OptionalDebug for T {
339    default fn optional_debug(&self) -> String {
340        "".to_string()
341    }
342}
343
344#[cfg(all(feature = "debug", feature = "nightly"))]
345impl<T: std::fmt::Debug + ?Sized> OptionalDebug for T {
346    fn optional_debug(&self) -> String {
347        format!("{:?}", self)
348    }
349}
350
351impl<T: ?Sized, O: AbstractObjectSpace> RawCc<T, O> {
352    #[inline]
353    pub(crate) fn inner(&self) -> &RawCcBox<T, O> {
354        // safety: CcBox lifetime maintained by ref count. Pointer is valid.
355        unsafe { self.0.as_ref() }
356    }
357
358    /// `trace` without `T: Trace` bound.
359    ///
360    /// Useful for structures with `Cc<T>` fields where `T` does not implement
361    /// `Trace`. For example, `struct S(Cc<Box<dyn MyTrait>>)`. To implement
362    /// `Trace` for `S`, it can use `Cc::trace(&self.0, tracer)`.
363    #[inline]
364    pub fn trace(&self, tracer: &mut Tracer) {
365        self.inner().trace_t(tracer);
366    }
367
368    #[inline]
369    fn inc_ref(&self) -> usize {
370        self.inner().inc_ref()
371    }
372
373    #[inline]
374    fn dec_ref(&self) -> usize {
375        self.inner().dec_ref()
376    }
377
378    #[inline]
379    pub(crate) fn ref_count(&self) -> usize {
380        self.inner().ref_count()
381    }
382
383    pub(crate) fn debug_name(&self) -> String {
384        self.inner().debug_name()
385    }
386}
387
388impl<T, O: AbstractObjectSpace> Clone for RawCc<T, O> {
389    #[inline]
390    fn clone(&self) -> Self {
391        // In theory self.inner().ref_count.locked() is needed.
392        // Practically this is an atomic operation that cannot be split so locking
393        // becomes optional.
394        // let _locked = self.inner().ref_count.locked();
395        self.inc_ref();
396        debug::log(|| (self.debug_name(), format!("clone ({})", self.ref_count())));
397        Self(self.0)
398    }
399}
400
401impl<T: ?Sized> Deref for Cc<T> {
402    type Target = T;
403
404    #[inline]
405    fn deref(&self) -> &Self::Target {
406        self.inner().deref()
407    }
408}
409
410impl<T: ?Sized, O: AbstractObjectSpace> Deref for RawCcBox<T, O> {
411    type Target = T;
412
413    #[inline]
414    fn deref(&self) -> &Self::Target {
415        debug_assert!(
416            !self.is_dropped(),
417            concat!(
418                "bug: accessing a dropped CcBox detected\n",
419                "This usually happens after ignoring another panic triggered by the collector."
420            )
421        );
422        // safety: CcBox (and its value) lifetime maintained by ref count.
423        // If `Trace` is implemented correctly then the GC won't drop_t()
424        // incorrectly and this pointer is valid. Otherwise the above
425        // assertion can prevent UBs on debug build.
426        unsafe { &*self.value.get() }
427    }
428}
429
430fn drop_ccbox<T: ?Sized, O: AbstractObjectSpace>(cc_box: &mut RawCcBox<T, O>) {
431    // safety: See Cc::new. The pointer was created by Box::into_raw.
432    let cc_box: Box<RawCcBox<T, O>> = unsafe { Box::from_raw(cc_box) };
433    let is_tracked = cc_box.is_tracked();
434    if is_tracked {
435        // The real object is CcBoxWithGcHeader. Drop that instead.
436        // safety: See Cc::new for CcBoxWithGcHeader.
437        let gc_box: Box<RawCcBoxWithGcHeader<T, O>> = unsafe { cast_box(cc_box) };
438        O::remove(&gc_box.header);
439        // Drop T if it hasn't been dropped yet.
440        // This needs to be after O::remove so the collector won't have a
441        // chance to read dropped content.
442        gc_box.cc_box.drop_t();
443        debug::log(|| (gc_box.cc_box.debug_name(), "drop (CcBoxWithGcHeader)"));
444        drop(gc_box);
445    } else {
446        // Drop T if it hasn't been dropped yet.
447        cc_box.drop_t();
448        debug::log(|| (cc_box.debug_name(), "drop (CcBox)"));
449        drop(cc_box);
450    }
451}
452
453impl<T: ?Sized, O: AbstractObjectSpace> Drop for RawCc<T, O> {
454    fn drop(&mut self) {
455        let ptr: *mut RawCcBox<T, O> = self.0.as_ptr();
456        // Block threaded collector. This is needed because "drop()" is a
457        // complex operation. The whole operation needs to be "atomic".
458        let _locked = self.inner().ref_count.locked();
459        let old_ref_count = self.dec_ref();
460        debug::log(|| (self.debug_name(), format!("drop ({})", self.ref_count())));
461        debug_assert!(old_ref_count >= 1);
462        if old_ref_count == 1 {
463            // safety: CcBox lifetime maintained by ref count.
464            drop_ccbox(unsafe { &mut *ptr });
465        }
466    }
467}
468
469impl<T: Trace, O: AbstractObjectSpace> CcDyn for RawCcBox<T, O> {
470    fn gc_ref_count(&self) -> usize {
471        self.ref_count()
472    }
473
474    fn gc_traverse(&self, tracer: &mut Tracer) {
475        debug::log(|| (self.debug_name(), "gc_traverse"));
476        T::trace(self.deref(), tracer)
477    }
478
479    fn gc_clone(&self) -> Box<dyn GcClone> {
480        self.ref_count.inc_ref();
481        debug::log(|| {
482            let msg = format!("gc_clone ({})", self.ref_count());
483            (self.debug_name(), msg)
484        });
485        // safety: The pointer is compatible. The mutability is different only
486        // to satisfy NonNull (NonNull::new requires &mut). The returned value
487        // is still "immutable".
488        let ptr: NonNull<RawCcBox<T, O>> = unsafe { mem::transmute(self) };
489        let cc = RawCc::<T, O>(ptr);
490        Box::new(cc)
491    }
492
493    #[cfg(feature = "debug")]
494    fn gc_debug_name(&self) -> String {
495        self.debug_name()
496    }
497}
498
499impl<T: Trace, O: AbstractObjectSpace> GcClone for RawCc<T, O> {
500    fn gc_ref_count(&self) -> usize {
501        self.ref_count()
502    }
503
504    fn gc_drop_t(&self) {
505        self.inner().drop_t()
506    }
507}
508
509impl<T: Trace> Trace for Cc<T> {
510    fn trace(&self, tracer: &mut Tracer) {
511        Cc::<T>::trace(self, tracer)
512    }
513
514    #[inline]
515    fn is_type_tracked() -> bool {
516        T::is_type_tracked()
517    }
518}
519
520impl Trace for Cc<dyn Trace> {
521    fn trace(&self, tracer: &mut Tracer) {
522        Cc::<dyn Trace>::trace(self, tracer)
523    }
524
525    #[inline]
526    fn is_type_tracked() -> bool {
527        // Trait objects can be anything.
528        true
529    }
530}
531
532#[cfg(feature = "nightly")]
533impl<T: ?Sized + std::marker::Unsize<U>, U: ?Sized, O: AbstractObjectSpace>
534    std::ops::CoerceUnsized<RawCc<U, O>> for RawCc<T, O>
535{
536}
537
538#[inline]
539unsafe fn cast_ref<T: ?Sized, R>(value: &T, offset_bytes: isize) -> &R {
540    let ptr: *const T = value;
541    let ptr: *const u8 = ptr as _;
542    let ptr = ptr.offset(offset_bytes);
543    &*(ptr as *const R)
544}
545
546#[inline]
547unsafe fn cast_box<T: ?Sized, O: AbstractObjectSpace>(
548    value: Box<RawCcBox<T, O>>,
549) -> Box<RawCcBoxWithGcHeader<T, O>> {
550    let mut ptr: *const RawCcBox<T, O> = Box::into_raw(value);
551
552    // ptr can be "thin" (1 pointer) or "fat" (2 pointers).
553    // Change the first byte to point to the GcHeader.
554    let pptr: *mut *const RawCcBox<T, O> = &mut ptr;
555    let pptr: *mut *const O::Header = pptr as _;
556    *pptr = (*pptr).offset(-1);
557    let ptr: *mut RawCcBoxWithGcHeader<T, O> = mem::transmute(ptr);
558    Box::from_raw(ptr)
559}
560
561#[cfg(test)]
562mod tests {
563    use super::*;
564    use crate::collect::Linked;
565
566    /// Check that `GcHeader::value()` returns a working trait object.
567    #[test]
568    fn test_gc_header_value() {
569        let v1: Cc<Box<dyn Trace>> = Cc::new(Box::new(1));
570        assert_eq!(v1.ref_count(), 1);
571
572        let v2 = v1.clone();
573        assert_eq!(v1.ref_count(), 2);
574        assert_eq!(v2.ref_count(), 2);
575
576        let v3: &dyn CcDyn = v1.inner() as &dyn CcDyn;
577        assert_eq!(v3.gc_ref_count(), 2);
578
579        let v4: &dyn CcDyn = v2.inner().header().value();
580        assert_eq!(v4.gc_ref_count(), 2);
581    }
582
583    #[cfg(feature = "nightly")]
584    #[test]
585    fn test_unsize_coerce() {
586        let _v: Cc<dyn Trace> = Cc::new(vec![1u8, 2, 3]);
587    }
588}
gcmodule/cc.rs

gcmodule/
cc.rs
