fitzgen / bacon-rajan-cc Goto Github PK
View Code? Open in Web Editor NEWLicense: Other
License: Other
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.
It would be nice to have an analog to Arc.
How to user #[derive(Trace)?] It seems that this derive isn't on crates.io
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?
Miri catches undefined behaviour.
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.
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);
}
I do not have a failing test case for this. However I believe this is not a safe place to free a node:
Line 223 in 9d59ed4
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.
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.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
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?
Line 341 in b890d5b
for i in &white {
// ...
unsafe { crate::drop_value(*i) };
unsafe { free(*i) };
}
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| | }
| |_____^
Currently, the docs indicate that the Tracer
s 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
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)
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.
Passing flags to Miri changed to make cargo miri test
more compatible with cargo test
. hence this will need adjusting:
Line 11 in 0041221
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.
It seems like this crate is providing useful functionality. It would be nice to make it usable again.
I want to implement a multi-threaded interpreter with Cc<T>
.
Does Mutex<Cc<T>>
work?
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.