fitzgen / bacon-rajan-cc Goto Github PK

License: Other

Rust 100.00%

bacon-rajan-cc's Introduction

bacon_rajan_cc

Cc<T>: A reference counted type with cycle collection for Rust. Concurrent or stop-the-world. Based on the paper "Concurrent Cycle Collection in Reference Counted Systems" by David F. Bacon and V.T. Rajan. JVM implementation

Currently only stop-the-world, not concurrent.

Usage

Add to Cargo.toml:

Note this requires at least Rust 1.28 for the std::alloc api's.

[dependencies]
bacon_rajan_cc = "0.3"

Then, in your crate:

extern crate bacon_rajan_cc;
use bacon_rajan_cc::{Cc, Trace, Tracer};

Documentation

Read the docs!

Future

Incremental cycle collection

Alternatives

https://github.com/jrmuizel/cc-mt (an experimental thread safe version of bacon-rajan-cc)
https://github.com/withoutboats/shifgrethor
https://github.com/Manishearth/rust-gc
https://github.com/redradist/ferris-gc (a thread safe reimplementatin of rust-gc)
https://github.com/Others/shredder
https://github.com/jazz-lang/wafflelink (conservative on stack,precise on heap Immix Mark-Region GC with evacuation in Rust)
https://github.com/artichoke/cactusref https://hyperbo.la/w/cactus-harvesting/

bacon-rajan-cc's People

Contributors

Stargazers

Watchers

Forkers

manishearth laanak08 appcoreopc jrmuizel coolreader18 quark-zju archive-tsao-chi-forks clinuxrulz rolftimmermans in-line icodein ves-lang optimalstrategy certainlach mbartlett21 peamaeq

bacon-rajan-cc's Issues

attempt to subtract with overflow

https://github.com/clinuxrulz/sodium_rust_concurrency_experiment/tree/wip-bacon_rajan_cc

(must be the wip-bacon_rajan_cc branch)

then run: cargo test, and you'll get the panic "attempt to subtract with overflow"

impl Trace found in "cell_loop.rs", "cell.rs", "dep.rs", "lambda.rs" "listener.rs", "node.rs", "stream_loop.rs", "stream.rs" all in the "src/impl_".

Not 100% sure if I've misused the library or not. I'm yet to have a small example failing.

Crash on keeping weak references after collecting a cycle (minor bug)

The following test fails (add to tests module in lib.rs):

    #[test]
    fn test_retain_weak() {
        let retained_weak_a;
        {
            struct A {
                x: Cc<RefCell<Option<A>>>,
            }
            struct WeakA {
                _x: Weak<RefCell<Option<A>>>
            }
            impl A {
                fn downgrade(this: &Self) -> WeakA {
                    WeakA { _x: Cc::downgrade(&this.x) }
                }
            }
            impl Clone for A {
                fn clone(&self) -> Self {
                    A { x: self.x.clone() }
                }
            }
            impl Trace for A {
                fn trace(&self, tracer: &mut Tracer) {
                    self.x.trace(tracer);
                }
            }
            let a = A { x: Cc::new(RefCell::new(None)) };
            *a.x.borrow_mut() = Some(a.clone());
            retained_weak_a = A::downgrade(&a);
        }
        collect_cycles();
        let _x = retained_weak_a;
    }

the following panic occurs:
thread 'tests::test_retain_weak' panicked at 'assertion failed: i.as_ref().weak() == 1', src\collect.rs:323:13

I have a feeling that assert should be replaced with an if-statement checking if the weak count is 1. As the end-user can have his own weak references he wants to hold onto beyond collect_cycles().

One place the user might want to do this is when designing a way to trace through a closure. (I.E. closure captures weak references, and is bundle with a separate vector of strong references to keep them alive)

Invalid Memory Access

Valgrind reports invalid memory access in collect_cycles. This can be reproduced using the doctest of the collect_cycles() function, or the example below:

extern crate bacon_rajan_cc;
use bacon_rajan_cc::{collect_cycles, Cc, Trace, Tracer};
use std::cell::RefCell;

struct List(Vec<Cc<RefCell<List>>>);
impl Trace for List {
    fn trace(&mut self, tracer: &mut Tracer) {
        self.0.trace(tracer);
    }
}

fn main() {
    {
        let a = Cc::new(RefCell::new(List(Vec::new())));
        let b = Cc::new(RefCell::new(List(Vec::new())));
        {
            let mut a = a.borrow_mut();
            a.0.push(b.clone());
        }
        {
            let mut b = b.borrow_mut();
            b.0.push(a.clone());
        }
    }
    collect_cycles();
}

The invalid access is:

==21659== Invalid read of size 8
==21659==    at 0x1139FE: core::cell::Cell<T>::get (cell.rs:249)
==21659==    by 0x112983: bacon_rajan_cc::cc_box_ptr::CcBoxPtr::strong (cc_box_ptr.rs:35)
==21659==    by 0x113212: <bacon_rajan_cc::Cc<T> as core::ops::drop::Drop>::drop (lib.rs:486)
==21659==    by 0x10E4BD: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x10E3B5: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x1116BF: drop_in_place<[bacon_rajan_cc::Cc<core::cell::RefCell<b::List>>]> (ptr.rs:185)
==21659==    by 0x1116BF: <alloc::vec::Vec<T> as core::ops::drop::Drop>::drop (vec.rs:2135)
==21659==    by 0x10E500: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x10E56D: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x10E48D: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x10E4D1: core::ptr::real_drop_in_place (ptr.rs:195)
==21659==    by 0x11342E: <bacon_rajan_cc::CcBox<T> as bacon_rajan_cc::cc_box_ptr::CcBoxPtr>::drop_value (lib.rs:892)
==21659==    by 0x112731: bacon_rajan_cc::cc_box_ptr::CcBoxPtr::free (cc_box_ptr.rs:88)
==21659==  Address 0x4aadbd0 is 32 bytes inside a block of size 56 free'd
==21659==    at 0x48389AB: free (vg_replace_malloc.c:530)
==21659==    by 0x111ED2: alloc::alloc::dealloc (alloc.rs:93)
==21659==    by 0x1133F1: <bacon_rajan_cc::CcBox<T> as bacon_rajan_cc::cc_box_ptr::CcBoxPtr>::deallocate (lib.rs:897)
==21659==    by 0x112755: bacon_rajan_cc::cc_box_ptr::CcBoxPtr::free (cc_box_ptr.rs:91)
==21659==    by 0x11B02D: bacon_rajan_cc::collect::collect_roots::collect_white (collect.rs:296)
==21659==    by 0x11C170: bacon_rajan_cc::collect::collect_roots::collect_white::{{closure}} (collect.rs:293)
==21659==    by 0x1132E3: <bacon_rajan_cc::Cc<T> as bacon_rajan_cc::trace::Trace>::trace (lib.rs:824)
==21659==    by 0x111487: bacon_rajan_cc::trace::impls::vec::<impl bacon_rajan_cc::trace::Trace for alloc::vec::Vec<T>>::trace (trace.rs:255)
==21659==    by 0x10FDD3: <b::List as bacon_rajan_cc::trace::Trace>::trace (b.rs:8)
==21659==    by 0x1105F1: bacon_rajan_cc::trace::impls::cell::<impl bacon_rajan_cc::trace::Trace for core::cell::RefCell<T>>::trace (trace.rs:206)
==21659==    by 0x113323: <bacon_rajan_cc::CcBox<T> as bacon_rajan_cc::trace::Trace>::trace (lib.rs:837)
==21659==    by 0x11B020: bacon_rajan_cc::collect::collect_roots::collect_white (collect.rs:292)
==21659==  Block was alloc'd at
==21659==    at 0x483777F: malloc (vg_replace_malloc.c:299)
==21659==    by 0x111E6B: alloc::alloc::alloc (alloc.rs:75)
==21659==    by 0x111DD9: alloc::alloc::exchange_malloc (alloc.rs:185)
==21659==    by 0x112E86: new<bacon_rajan_cc::CcBox<core::cell::RefCell<b::List>>> (boxed.rs:113)
==21659==    by 0x112E86: bacon_rajan_cc::Cc<T>::new (lib.rs:258)
==21659==    by 0x10FE56: b::main (b.rs:14)
==21659==    by 0x10FCEF: std::rt::lang_start::{{closure}} (rt.rs:64)
==21659==    by 0x126902: {{closure}} (rt.rs:49)
==21659==    by 0x126902: std::panicking::try::do_call (panicking.rs:293)
==21659==    by 0x1286A9: __rust_maybe_catch_panic (lib.rs:85)
==21659==    by 0x1273BC: try<i32,closure> (panicking.rs:272)
==21659==    by 0x1273BC: catch_unwind<closure,i32> (panic.rs:388)
==21659==    by 0x1273BC: std::rt::lang_start_internal (rt.rs:48)
==21659==    by 0x10FCC8: std::rt::lang_start (rt.rs:64)
==21659==    by 0x110199: main (in /data/quark/oss/bacon-rajan-cc/target/debug/examples/b)

I think the fix would be splitting drop to two phases:

drop_value, but do not de-allocate CcBoxData for white objects.
deallocate only CcBoxData for white objects.

Drop is unsound

Cc's will be dropped while references to them still exist which can be accessed in the Drop implementation causing use-after-free. bb2bf84 from 'dirty' branch tries to address this.

How to use Cc<T> with multithreading?

I want to implement a multi-threaded interpreter with Cc<T>.
Does Mutex<Cc<T>> work?

data is deallocated while holding a mutable reference

From running cargo miri test

error[E0080]: Miri evaluation error: deallocating while item is protected: [Unique for 159533 (call 64208)]
   --> /Users/jrmuizel/.rustup/toolchains/nightly-2019-05-27-x86_64-apple-darwin/lib/rustlib/src/rust/src/liballoc/alloc.rs:103:5
    |
103 |     __rust_dealloc(ptr, layout.size(), layout.align())
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Miri evaluation error: deallocating while item is protected: [Unique for 159533 (call 64208)]
    |
note: inside call to `std::alloc::dealloc` at src/lib.rs:882:9
   --> src/lib.rs:882:9
    |
882 |         dealloc(NonNull::new_unchecked(ptr).cast().as_ptr(), Layout::new::<CcBox<T>>());
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `<CcBox<i32> as cc_box_ptr::CcBoxPtr>::deallocate` at src/lib.rs:846:9
   --> src/lib.rs:846:9
    |
846 |         self._ptr.as_mut().deallocate();
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `<Cc<i32> as cc_box_ptr::CcBoxPtr>::deallocate` at src/cc_box_ptr.rs:77:13
   --> src/cc_box_ptr.rs:77:13
    |
77  |             self.deallocate();
    |             ^^^^^^^^^^^^^^^^^
note: inside call to `<Cc<i32> as cc_box_ptr::CcBoxPtr>::free` at src/lib.rs:299:9
   --> src/lib.rs:299:9
    |
299 |         self.free();
    |         ^^^^^^^^^^^
note: inside call to `Cc::<i32>::release` at src/lib.rs:487:21
   --> src/lib.rs:487:21
    |
487 |                     self.release();
    |                     ^^^^^^^^^^^^^^
    = note: inside call to `<Cc<i32> as std::ops::Drop>::drop` at /Users/jrmuizel/.rustup/toolchains/nightly-2019-05-27-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ptr.rs:195:1
note: inside call to `std::ptr::real_drop_in_place::<Cc<i32>> - shim(Some(Cc<i32>))` at src/lib.rs:1055:5
   --> src/lib.rs:1055:5
    |
1055|     }
    |     ^
note: inside call to `tests::test_cowrc_clone_make_unique` at src/lib.rs:1034:5
   --> src/lib.rs:1034:5
    |
1034| /     fn test_cowrc_clone_make_unique() {
1035| |         let mut cow0 = Cc::new(75);
1036| |         let mut cow1 = cow0.clone();
1037| |         let mut cow2 = cow1.clone();
...   |
1054| |         assert!(*cow1 != *cow2);
1055| |     }
    | |_____^

Update to be buildable with Nightly or Stable rust

It seems like this crate is providing useful functionality. It would be nice to make it usable again.

Incorrect Docs for Trace

Currently, the docs indicate that the Tracers should be used like by calling the function, like this

    tracer(&self.owner);

This correct usage seems to be:

   self.owner.trace(tracer)

Otherwise, it can result in a subtract with overflow when a Cc contains a struct containing a Cc, because the Cc is traced a second time through its CcBox.

use bacon_rajan_cc::{Cc, Trace, Tracer, collect_cycles};

struct A {
    a: Cc<i32>,
}

impl Trace for A {
    fn trace(&self, tracer: &mut Tracer) {
        tracer(&self.a); // wrong

        // Should be:
        // self.a.trace(tracer);
    }
}

fn main() {
    let a = Cc::new(A { a: Cc::new(1) });
    let b = Cc::clone(&a);
    drop(b);
    collect_cycles();
}

thread 'main' panicked at 'attempt to subtract with overflow', C:\...\src\cc_box_ptr.rs

Miri flag passing changed

Passing flags to Miri changed to make cargo miri test more compatible with cargo test. hence this will need adjusting:

bacon-rajan-cc/.travis.yml

Line 11 in 0041221

- cargo miri test -- -Zmiri-seed=23

However, in fact you should not have to pass a seed at all any more. Just a plain cargo miri test should do it. (cargo miri setup also is not needed as a separate step any more.)

The old way still works for now, but is deprecated and will be removed in the future.

CcBox (and likely Cc) need 'static (or !Drop) bound for soundness

In the presence of data with some stack-bound lifetime 'a and a Drop implementation, when a cycle is collected after the stack frame has expired then Drop::drop() may access invalidated references with the lifetime 'a.

This could be avoided by not running Drop::drop() at all (as mem::forget() is safe, but running a late destructor on non-'static data is not), but as that leaks memory it is likely not a viable solution.

Use-after-free?

For example in a cycle like: a->b, b->a.
garbage is collected into white like this: [a, b]
If in the first loop, a is drop&deallocated,
in the second loop(where i is b), wouldn't RAII makes b access a after a is deallocated?

bacon-rajan-cc/src/collect.rs

Line 341 in b890d5b

unsafe { crate::drop_value(*i) };

    for i in &white {
       // ...
        unsafe { crate::drop_value(*i) };
        unsafe { free(*i) };
    }

How to user #[derive(Trace)?]

How to user #[derive(Trace)?] It seems that this derive isn't on crates.io

Add atomic support.

It would be nice to have an analog to Arc.

Add function to insure all memory is freed at the at the end of each test.

Just a simple global counter to count the number of CcBoxPtrs still floating around, and insure it has hit zero after each test is complete.

Clarify Trace trait usage

The Trace implementation for CcBox doesn't call tracer, instead of the trait seems to rely on owner of the Cc to do this. Is this necessary? Shouldn't the derived implementation of Trace basically just be to call trace() on each of its members?

Free too soon in mark_roots() (suspected bug)

I do not have a failing test case for this. However I believe this is not a safe place to free a node:

bacon-rajan-cc/src/collect.rs

Line 223 in 9d59ed4

free(s);

I believe the free-ing should be defered to the end of collect_roots, just like collect_white does.

The reason is that the early drop() it could be potentially be changing the shape of the memory graph that has already been traversed by mark_grey(). Potentially causing scan_black() not to restore the reference counts properly.

miri shows undefined behaviour when run with -Zmiri-tag-raw-pointers

test tests::extra_free ... error: Undefined Behavior: trying to reborrow <248731> for SharedReadWrite permission at alloc96889[0x22], but that tag only grants SharedReadOnly permission for this location
    --> /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:487:1
     |
487  | pub unsafe fn drop_in_place<T: ?Sized>(to_drop: *mut T) {
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     | |
     | trying to reborrow <248731> for SharedReadWrite permission at alloc96889[0x22], but that tag only grants SharedReadOnly permission for this location
     | this error occurs as part of a reborrow at alloc96889[0x0..0x28]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <248731> was created by a retag at offsets [0x0..0x28]
    --> src/collect.rs:311:24
     |
311  |             white.push(s.into());
     |                        ^^^^^^^^
     = note: inside `std::ptr::drop_in_place::<dyn cc_box_ptr::CcBoxPtr> - shim(Some(dyn cc_box_ptr::CcBoxPtr))` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:487:1
note: inside `drop_value` at src/lib.rs:922:5
    --> src/lib.rs:922:5
     |
922  |     ptr::drop_in_place(ptr.as_ptr());
     |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `collect::collect_roots` at src/collect.rs:338:18
    --> src/collect.rs:338:18
     |
338  |         unsafe { crate::drop_value(*i) };
     |                  ^^^^^^^^^^^^^^^^^^^^^
note: inside `collect::collect_cycles` at src/collect.rs:192:5
    --> src/collect.rs:192:5
     |
192  |     collect_roots();
     |     ^^^^^^^^^^^^^^^
note: inside `tests::extra_free` at src/lib.rs:1367:13
    --> src/lib.rs:1367:13
     |
1367 |             collect_cycles(); // <- incorrectly? frees env_a.
     |             ^^^^^^^^^^^^^^^^
note: inside closure at src/lib.rs:1314:5
    --> src/lib.rs:1314:5
     |
1313 |       #[test]
     |       ------- in this procedural macro expansion
1314 | /     fn extra_free() {
1315 | |         struct Env {
1316 | |             pub closures: Vec<Cc<RefCell<Clos>>>,
1317 | |             pub next: Option<Cc<Env>>,
...    |
1381 | |         collect_cycles();
1382 | |     }
     | |_____^
     = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

Weak<> doesn't work properly

Miri catches undefined behaviour.

"Invalid access during cycle collection" - collect_cycles() leaves live nodes with zero refs

I have a case where a cycle is correctly freed but leaves live dependencies with a zero ref count.

Fairly small example below. circular_env is correctly reclaimed but live_env is left with a reference to env_a which has a zero reference count. This leads to a panic ("Invalid access during cycle collection").

It seems to happen because mark_gray decrements the ref count but scan does not reinstate that ref count for the first black node, only its descendants (presumably because the ref from the cycle is now assumed dead). When the white nodes are subsequently freed, the ref count of this first black node (env_a in the example below) is decremented again. The end result is we've decremented twice for the impact of removing one dependant (the cycle).

        struct Env {
            pub closures: Vec<Cc<RefCell<Clos>>>,
            pub next: Option<Cc<Env>>,
        }
        impl Trace for Env {
            fn trace(&self, tracer: &mut Tracer) {
                self.closures.trace(tracer);
                self.next.trace(tracer);
            }
        }
        struct Clos {
            pub env: Cc<Env>,
        }
        impl Trace for Clos {
            fn trace(&self, tracer: &mut Tracer) {
                self.env.trace(tracer);
            }
        }

        let live_env = {
            let base_env = Cc::new(Env {
                closures: vec![],
                next: None,
            });

            let env_a = Cc::new(Env {
                closures: vec![Cc::new(RefCell::new(Clos {
                    env: base_env.clone(),
                }))],
                next: Some(base_env.clone()),
            });

            let circular_env = Cc::new(Env {
                closures: vec![Cc::new(RefCell::new(Clos {
                    env: base_env.clone(),
                }))],
                next: Some(env_a.clone()),
            });
            circular_env.closures[0].replace(Clos {
                env: circular_env.clone(),
            });

            let live_env = Cc::new(Env {
                closures: vec![],
                next: Some(env_a.clone()),
            });

            drop(base_env); // don't need the stack ref
            drop(env_a); // don't need the stack ref
            collect_cycles();

            drop(circular_env); // cycle root
            collect_cycles(); // <- incorrectly? frees env_a.
                              // mark_gray decrements env_a and does
                              // not reinstate (it's the root of the
                              // black region). collect_white frees
                              // circular_env, which decrements env_a
                              // again - to zero and frees it...

            live_env
        };

        // the following panics
        if let Some(a) = &live_env.next {
            assert_eq!(a.closures.len(), 0);
        }