crossbeam-rs / crossbeam-epoch

Epoch-based garbage collection

NOTE: This crate has been moved into the crossbeam repository.

Do not use this repository.

Epoch-based garbage collection

This crate provides epoch-based garbage collection for use in concurrent data structures.

If a thread removes a node from a concurrent data structure, other threads may still have pointers to that node, so it cannot be immediately destructed. Epoch GC allows deferring destruction until it becomes safe to do so.

Usage

Add this to your Cargo.toml:

[dependencies]
crossbeam-epoch = "0.6"

Next, add this to your crate:

extern crate crossbeam_epoch as epoch;

The minimum required Rust version is 1.26.

License

Licensed under the terms of MIT license and the Apache License (Version 2.0).

See LICENSE-MIT and LICENSE-APACHE for details.

crossbeam-epoch's Issues

Explain the meaning of `#[cold]` attribute for `fn try_advance()`

reference:

crossbeam-epoch/src/epoch.rs

Line 36 in 7c4ba5a

#[cold]

It would be great to comment on this.

Travis failure due to "disk quota exceeded"

Failure for #43: https://travis-ci.org/crossbeam-rs/crossbeam-epoch/jobs/307321581

Worker information
hostname: [e-mail]
version: v3.4.0 https://github.com/travis-ci/worker/tree/ce0440bc30c289a49a9b0c21e4e1e6f7d7825101
instance: f176a01 travisci/ci-garnet:packer-1503972846 (via amqp)
startup: 6.573325344s
oci runtime error: exec failed: container_linux.go:265: starting container process caused "could not create session key: disk quota exceeded"

Can we think of a better name for `Garbage`?

@stjepang said:

"Garbage" is typically in plural and refers to a bunch of deleted/dead/unlinked objects. I'd prefer to use a better synonym in singular form. That said, I don't have any ideas for a better word to use. :)

@Vtec234 replied:

It seems that such a word literally doesn't exist: link. The closest name is PieceOfGarbage.

0.4.2 contains a breaking change

Updating crossbeam-utils to 0.4.0 is a breaking change since that version requires a newer version of Rust to compile (1.25 instead of 1.12). This has broken CI of one of my crates: https://travis-ci.org/jonas-schievink/xml-rpc-rs/jobs/391259820

As a side note, .travis.yml doesn't test for a minimum supported Rust version right now.

Archiving?

I just noticed that this repo is the only unarchived sub-crate repo. Shall we archive it?

Handle should implement Clone

Without implementing Clone, users who wish to use a crossbeam Handle as part of their own handle-based design will need to ensure that they retain access to the original Collector so they can call .handle() on it to get a new Handle. With Clone, a user's handle-based implementation could be as simple as:

#[derive(Clone)]
struct MyHandle {
    gc: crossbeam_epoch::Handle,
}

Segfault

I'm not sure exactly which repo this issue belongs in. I just updated to crossbeam 0.4.0 earlier and am now experiencing segfaults with the following stack trace. Apologies for the lack of pruning:

Thread 51 "tokio-runtime-w" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7fffe13fe700 (LWP 107445)]
arena_dalloc_bin_locked_impl (bitselm=<optimized out>, junked=true, ptr=<optimized out>, chunk=0x7fffdec00000, 
    arena=0x7ffff6d4eb00, tsdn=0x7fffe13fe480) at /checkout/src/liballoc_jemalloc/../jemalloc/src/arena.c:2964
2964	/checkout/src/liballoc_jemalloc/../jemalloc/src/arena.c: No such file or directory.
(gdb) bt
#0  arena_dalloc_bin_locked_impl (bitselm=<optimized out>, junked=true, ptr=<optimized out>, chunk=0x7fffdec00000, 
    arena=0x7ffff6d4eb00, tsdn=0x7fffe13fe480) at /checkout/src/liballoc_jemalloc/../jemalloc/src/arena.c:2964
#1  je_arena_dalloc_bin_junked_locked (tsdn=tsdn@entry=0x7fffe13fe480, arena=arena@entry=0x7ffff6d4eb00, 
    chunk=0x7fffdec00000, ptr=<optimized out>, bitselm=<optimized out>)
    at /checkout/src/liballoc_jemalloc/../jemalloc/src/arena.c:2981
#2  0x00005555558640a5 in je_tcache_bin_flush_small (tsd=0x7fffe13fe480, tcache=tcache@entry=0x7fffebca1000, 
    tbin=tbin@entry=0x7fffebca1328, binind=binind@entry=24, rem=rem@entry=10)
    at /checkout/src/liballoc_jemalloc/../jemalloc/src/tcache.c:137
#3  0x000055555583ca9f in je_tcache_dalloc_small (slow_path=<optimized out>, binind=<optimized out>, 
    ptr=<optimized out>, tcache=<optimized out>, tsd=<optimized out>)
    at /checkout/src/liballoc_jemalloc/../jemalloc/include/jemalloc/internal/tcache.h:419
#4  je_arena_sdalloc (slow_path=<optimized out>, tcache=<optimized out>, size=<optimized out>, ptr=<optimized out>, 
    tsdn=<optimized out>) at /checkout/src/liballoc_jemalloc/../jemalloc/include/jemalloc/internal/arena.h:1499
#5  je_isdalloct (slow_path=<optimized out>, tcache=<optimized out>, size=<optimized out>, ptr=<optimized out>, 
    tsdn=<optimized out>) at include/jemalloc/internal/jemalloc_internal.h:1195
#6  je_isqalloc (slow_path=<optimized out>, tcache=<optimized out>, size=<optimized out>, ptr=<optimized out>, 
    tsd=<optimized out>) at include/jemalloc/internal/jemalloc_internal.h:1205
#7  isfree (tsd=<optimized out>, slow_path=<optimized out>, tcache=<optimized out>, usize=<optimized out>, 
    ptr=<optimized out>) at /checkout/src/liballoc_jemalloc/../jemalloc/src/jemalloc.c:1921
#8  sdallocx (ptr=0x7fffdec59800, size=<optimized out>, flags=<optimized out>)
    at /checkout/src/liballoc_jemalloc/../jemalloc/src/jemalloc.c:2669
#9  0x00005555555ff077 in <alloc::alloc::Global as core::alloc::GlobalAlloc>::dealloc (self=<optimized out>, 
    ptr=<optimized out>, layout=...) at /checkout/src/liballoc/alloc.rs:86
#10 <alloc::alloc::Global as core::alloc::Alloc>::dealloc (self=<optimized out>, ptr=..., layout=...)
    at /checkout/src/liballoc/alloc.rs:117
#11 <alloc::raw_vec::RawVec<T, A>>::dealloc_buffer (self=<optimized out>) at /checkout/src/liballoc/raw_vec.rs:704
#12 <alloc::raw_vec::RawVec<T, A> as core::ops::drop::Drop>::drop (self=0x7fffdec72198)
    at /checkout/src/liballoc/raw_vec.rs:713
#13 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#14 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#15 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#16 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#17 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#18 0x0000555555634435 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#19 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#20 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#21 core::mem::drop (_x=0x7fffdec72000) at /checkout/src/libcore/mem.rs:787
#22 <crossbeam_epoch::atomic::Owned<T> as core::ops::drop::Drop>::drop (self=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/atomic.rs:723
#23 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#24 core::mem::drop (_x=...) at /checkout/src/libcore/mem.rs:787
#25 crossbeam_epoch::guard::Guard::defer::{{closure}} ()
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/guard.rs:176
#26 crossbeam_epoch::deferred::Deferred::new::call (raw=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/deferred.rs:44
#27 0x0000555555735be6 in crossbeam_epoch::deferred::Deferred::call (self=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/deferred.rs:75
#28 <crossbeam_epoch::internal::Bag as core::ops::drop::Drop>::drop (self=0x7fffe13fbcf8)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/internal.rs:106
#29 core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#30 0x0000555555736cf5 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#31 core::mem::drop (_x=...) at /checkout/src/libcore/mem.rs:787
#32 crossbeam_epoch::internal::Global::collect (self=0x7ffff6a8b040, guard=0x7fffe13fc530)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/internal.rs:190
#33 0x00005555555fec5d in crossbeam_epoch::internal::Local::pin (self=0x3)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/internal.rs:379
#34 crossbeam_epoch::collector::Handle::pin (self=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/collector.rs:72
---Type <return> to continue, or q <return> to quit---  
#35 crossbeam_epoch::default::pin::{{closure}} (handle=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/default.rs:25
#36 <std::thread::local::LocalKey<T>>::try_with (self=<optimized out>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#37 <std::thread::local::LocalKey<T>>::with (self=<optimized out>, f=...) at /checkout/src/libstd/thread/local.rs:248
#38 0x000055555567656d in crossbeam_epoch::default::pin ()
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-epoch-0.5.1/src/default.rs:25
#39 <crossbeam::seg_queue::SegQueue<T>>::try_pop (self=0x7ffff6b091a0)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/crossbeam-0.4.0/src/seg_queue.rs:116
#40 0x000055555569b367 in <hydrabadger::hydrabadger::handler::Handler as futures::future::Future>::poll (
    self=0x7ffff6b09178) at src/hydrabadger/handler.rs:684
#41 0x000055555560a3fe in futures::future::option::<impl futures::future::Future for core::option::Option<F>>::poll (
    self=0x7ffff6b09178)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/option.rs:12
#42 <futures::future::map_err::MapErr<A, F> as futures::future::Future>::poll (self=0x7ffff6b09178)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/map_err.rs:30
#43 0x00005555556274ac in <futures::future::join::MaybeDone<A>>::poll (self=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/join.rs:153
#44 <futures::future::join::Join4<A, B, C, D> as futures::future::Future>::poll (self=0x7ffff6b09000)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/join.rs:75
#45 0x00005555556098b9 in <futures::future::map::Map<A, F> as futures::future::Future>::poll (self=0x7ffff6b09000)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/map.rs:30
#46 0x0000555555718c60 in <alloc::boxed::Box<F> as futures::future::Future>::poll (self=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/future/mod.rs:113
#47 <futures::task_impl::Spawn<T>>::poll_future_notify::{{closure}} (f=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/task_impl/mod.rs:289
#48 <futures::task_impl::Spawn<T>>::enter::{{closure}} ()
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/task_impl/mod.rs:363
#49 futures::task_impl::std::set (task=0x7fffe13fd428, f=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/task_impl/std/mod.rs:78
#50 0x000055555571bc86 in <futures::task_impl::Spawn<T>>::enter (self=<optimized out>, 
    unpark=<error reading variable: access outside bounds of object referenced via synthetic pointer>, f=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/task_impl/mod.rs:363
#51 <futures::task_impl::Spawn<T>>::poll_future_notify (self=<optimized out>, notify=<optimized out>, id=76)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/futures-0.1.23/src/task_impl/mod.rs:289
#52 tokio_threadpool::task::TaskFuture::poll (self=<optimized out>, unpark=<optimized out>, id=76, 
    exec=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/task/mod.rs:292
#53 tokio_threadpool::task::Task::run::{{closure}} ()
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/task/mod.rs:165
#54 core::ops::function::FnOnce::call_once () at /checkout/src/libcore/ops/function.rs:223
#55 <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once (self=..., _args=<optimized out>)
    at /checkout/src/libstd/panic.rs:305
#56 std::panicking::try::do_call (data=0x7fffe13fd4d0 "H\325?\341\377\177") at /checkout/src/libstd/panicking.rs:310
#57 0x0000555555834d8a in __rust_maybe_catch_panic () at libpanic_unwind/lib.rs:105
#58 0x000055555571ade7 in std::panicking::try (f=...) at /checkout/src/libstd/panicking.rs:289
#59 std::panic::catch_unwind (f=...) at /checkout/src/libstd/panic.rs:374
#60 tokio_threadpool::task::Task::run (self=<optimized out>, unpark=<optimized out>, exec=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/task/mod.rs:151
#61 0x00005555557144a6 in tokio_threadpool::worker::Worker::run_task2 (self=<optimized out>, notify=<optimized out>, 
    sender=<optimized out>, task=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:545
#62 tokio_threadpool::worker::Worker::run_task (self=0x7fffe13fd938, task=..., notify=<optimized out>, sender=0x3)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:445
#63 0x00005555557137b5 in tokio_threadpool::worker::Worker::try_run_owned_task (notify=0x7fffe0a0d060, 
    sender=0x7ffff6a8b280, self=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:385
#64 tokio_threadpool::worker::Worker::try_run_task (self=<optimized out>, notify=<optimized out>, 
---Type <return> to continue, or q <return> to quit---
    sender=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:293
#65 tokio_threadpool::worker::Worker::run (self=0x7fffe13fd938)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:239
#66 0x0000555555700967 in tokio::runtime::builder::Builder::build::{{closure}}::{{closure}}::{{closure}}::{{closure}}
    () at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-0.1.7/src/runtime/builder.rs:125
#67 tokio_timer::timer::handle::with_default::{{closure}} (current=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-timer-0.2.4/src/timer/handle.rs:64
#68 <std::thread::local::LocalKey<T>>::try_with (self=<optimized out>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#69 <std::thread::local::LocalKey<T>>::with (self=<optimized out>, f=...) at /checkout/src/libstd/thread/local.rs:248
#70 0x0000555555700a93 in tokio_timer::timer::handle::with_default (handle=<optimized out>, enter=<optimized out>, 
    f=...) at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-timer-0.2.4/src/timer/handle.rs:56
#71 tokio::runtime::builder::Builder::build::{{closure}}::{{closure}}::{{closure}} (enter=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-0.1.7/src/runtime/builder.rs:124
#72 tokio_timer::clock::clock::with_default::{{closure}} (cell=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-timer-0.2.4/src/clock/clock.rs:136
#73 <std::thread::local::LocalKey<T>>::try_with (self=0x555555b886a0 <byte_str.0.llvm>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#74 <std::thread::local::LocalKey<T>>::with (self=0x555555b886a0 <byte_str.0.llvm>, f=...)
    at /checkout/src/libstd/thread/local.rs:248
#75 0x00005555557007cb in tokio_timer::clock::clock::with_default (clock=<optimized out>, enter=<optimized out>, f=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-timer-0.2.4/src/clock/clock.rs:119
#76 tokio::runtime::builder::Builder::build::{{closure}}::{{closure}} (enter=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-0.1.7/src/runtime/builder.rs:123
#77 tokio_reactor::with_default::{{closure}} (current=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-reactor-0.1.2/src/lib.rs:231
#78 <std::thread::local::LocalKey<T>>::try_with (self=<optimized out>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#79 <std::thread::local::LocalKey<T>>::with (self=<optimized out>, f=...) at /checkout/src/libstd/thread/local.rs:248
#80 0x00005555556fe0a9 in tokio_reactor::with_default (handle=<optimized out>, enter=<optimized out>, f=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-reactor-0.1.2/src/lib.rs:214
#81 tokio::runtime::builder::Builder::build::{{closure}} (w=<optimized out>, enter=0x7fffe13fd8a0)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-0.1.7/src/runtime/builder.rs:122
#82 0x000055555571a545 in tokio_threadpool::callback::Callback::call (self=<optimized out>, worker=0x0, enter=0x4c)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/callback.rs:21
#83 tokio_threadpool::worker::Worker::do_run::{{closure}}::{{closure}} (enter=0x4c)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:121
#84 tokio_executor::global::with_default::{{closure}} (cell=0x7fffe13fe5a8)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-executor-0.1.2/src/global.rs:176
#85 <std::thread::local::LocalKey<T>>::try_with (self=<optimized out>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#86 <std::thread::local::LocalKey<T>>::with (self=<optimized out>, f=...) at /checkout/src/libstd/thread/local.rs:248
#87 0x000055555571a68c in tokio_executor::global::with_default (executor=0x7ffff6a8b280, enter=0x8, f=...)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-executor-0.1.2/src/global.rs:150
#88 tokio_threadpool::worker::Worker::do_run::{{closure}} (c=<optimized out>)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:119
#89 <std::thread::local::LocalKey<T>>::try_with (self=0x555555b893c0 <byte_str.p.llvm>, f=...)
    at /checkout/src/libstd/thread/local.rs:294
#90 <std::thread::local::LocalKey<T>>::with (self=0x555555b893c0 <byte_str.p.llvm>, f=...)
    at /checkout/src/libstd/thread/local.rs:248
#91 0x0000555555719734 in tokio_threadpool::worker::Worker::do_run (self=0x7ffff6a8b280)
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/worker/mod.rs:110
#92 tokio_threadpool::pool::Pool::spawn_thread::{{closure}} ()
    at /home/nick/.cargo/registry/src/github.com-1ecc6299db9ec823/tokio-threadpool-0.1.5/src/pool/mod.rs:417
#93 std::sys_common::backtrace::__rust_begin_short_backtrace (f=...)
    at /checkout/src/libstd/sys_common/backtrace.rs:136
#94 0x000055555571bcec in std::thread::Builder::spawn::{{closure}}::{{closure}} ()
---Type <return> to continue, or q <return> to quit---
    at /checkout/src/libstd/thread/mod.rs:409
#95 <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once (self=..., _args=<optimized out>)
    at /checkout/src/libstd/panic.rs:305
#96 std::panicking::try::do_call (data=<optimized out>) at /checkout/src/libstd/panicking.rs:310
#97 0x0000555555834d8a in __rust_maybe_catch_panic () at libpanic_unwind/lib.rs:105
#98 0x000055555571740d in std::panicking::try (f=...) at /checkout/src/libstd/panicking.rs:289
#99 std::panic::catch_unwind (f=...) at /checkout/src/libstd/panic.rs:374
#100 std::thread::Builder::spawn::{{closure}} () at /checkout/src/libstd/thread/mod.rs:408
#101 <F as alloc::boxed::FnBox<A>>::call_box (self=0x7ffff3698380, args=<optimized out>)
    at /checkout/src/liballoc/boxed.rs:638
#102 0x000055555582982b in _$LT$alloc..boxed..Box$LT$alloc..boxed..FnBox$LT$A$C$$u20$Output$u3d$R$GT$$u20$$u2b$$u20$$u27$a$GT$$u20$as$u20$core..ops..function..FnOnce$LT$A$GT$$GT$::call_once::h9ad6846d840ae36b ()
    at /checkout/src/liballoc/boxed.rs:648
#103 std::sys_common::thread::start_thread () at libstd/sys_common/thread.rs:24
#104 0x00005555558188b6 in std::sys::unix::thread::Thread::new::thread_start () at libstd/sys/unix/thread.rs:90
#105 0x00007ffff77b16db in start_thread (arg=0x7fffe13fe700) at pthread_create.c:463
#106 0x00007ffff72c288f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

Should `internal::Local` be `Sync`?

Currently the internal::Local struct is marked as Sync. However it uses Cell for the guard and handle counts, which is not Sync, only Send. I don't think it safe to mark internal::Local as Sync, but only as Send (given that the other field are ok to be Send).

Possible memory leak in crossbeam

Unless I'm misunderstanding something in this crate, when I compile and run this simple gist in valgrind, I get the following "possibly lost" and "still reachable" leaks:

==14743== LEAK SUMMARY:
==14743==    definitely lost: 0 bytes in 0 blocks
==14743==    indirectly lost: 0 bytes in 0 blocks
==14743==      possibly lost: 25,440 bytes in 82 blocks
==14743==    still reachable: 848,610 bytes in 1,323 blocks
==14743==         suppressed: 0 bytes in 0 blocks
==14743== 
==14743== For counts of detected and suppressed errors, rerun with: -v
==14743== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)

These numbers only seem to increase as the number of loop iterations increases.
The full valgrind log is in the gist.

Running rustc 1.26.0-dev (nightly) with the system allocator on Linux.

Deferring from the execution of another defer can result in deadlock

version: 0.6.0
rustc: 1.29.1
os: macOS 10.13.6

After modifying some logic in sled to defer transitioning some state, which in turn triggered a nested defer and flush call I introduced a deadlock, which I traced to this recursive call to defer() and then flush(). Removing flush() gets it to work in this case, but I'm pretty sure that this will hit the same deadlock when the local Bag is filled, right?

In this case, I was able to reason that this would always only reach that nested defer from an outer one, so I was able to just remove the nested call.

Maybe it would be good to add some additional documentation to Guard::defer to warn people away from this usage?

To reproduce, run cargo test chunky from the root of the sled repo at commit c74a31f9.

Relaxing the condition on pointer tags

I am porting @stjepang 's channel (https://github.com/stjepang/channel) from coco to crossbeam-epoch, and found out that channel uses pointer tags >= 8 on x86-64: https://github.com/stjepang/channel/blob/master/src/flavors/list.rs#L102

It turns out that coco allows tags >= 8, while crossbeam-epoch doesn't: https://github.com/stjepang/coco/blob/master/src/epoch/atomic.rs#L429 https://github.com/crossbeam-rs/crossbeam-epoch/blob/master/src/atomic.rs#L518

I am convinced that this relaxation of coco is actually more ergonomic, as evidenced by the channel implementation. Though it may be a little bit more unsafe (in terms of surprising the users). In this tradeoff, I would like to prefer the usability to the safety. What do you think?

Also, if we will decide to be strict on pointer tags in this matter, I think it would be great to expose atomic.rs's low_bits() in the public interface, for supporting the use case in channel.

Should Atomic implement Clone?

I was implementing a simple Bw-Tree and had a vector of the following type:

Vec<(K, Atomic<Page<K, V>>)>

This vector had to be cloned, but it didn't implement Clone because Atomic<T> doesn't implement it. So I have to manually go through each element of the vector, load the Atomic<Page<K, V>> and then create a clone myself. I should also note that those Atomics never change - they are in fact immutable.

We have this pattern of immutable Atomics actually coming up pretty often. For example, in a lock-free stack nodes are defined as:

struct Node<T> {
    value: ManuallyDrop<T>,
    next: Atomic<Node<T>>,
}

The next field becomes immutable once we push the new node onto the stack. This is why loading next pointers using Relaxed is okay.

Is it a reasonable idea to implement Clone for Atomic<T>? If so, how would we implement it? Would we load the value using Relaxed or maybe SeqCst?

Provide functions to get the global Collector

If code accepts a Handle or a Collector that the user is expected to pass, it'd be nice for them to be able to opt out of having to manage their own GC by simply doing crossbeam::global_collector() or crossbeam::global_collector().handle() or something similar.

`fn defer_drop()` requires the object's type be `'static`

On the one hand, it is necessary: we don't know exactly when the object will be dropped. On the other hand, it may be a little bit restrictive: e.g. rsdb defer_drop()s non-'static types (https://github.com/spacejam/rsdb/blob/1f4e97fc8a3c8218af85b265761454c87f3591a0/src/stack.rs#L158).

This problem is well summarized in crossbeam-rs/crossbeam#57 (comment).

Announcing crossbeam-epoch 0.1.0?

It seems crossbeam-epoch is comparable to both the original crossbeam and coco in terms of features. For example, I could successfully port rsdb, which was based on coco, to crossbeam-epoch: https://github.com/jeehoonkang/rsdb/tree/crossbeam-epoch Also, its performance seems not bad compared to the two precursors.

So I wonder if (1) we want to announce the initial 0.1.0 release of the core of new crossbeam, and (2) when. Personally, I want to announce it after both crossbeam-rs/rfcs#9 and #13 are somehow resolved.

What do you think?

Using `Epoch::distance()` may give us a wrong result?

Suppose that usize is 32bits. Then the implementation of Epoch::decompose() implies the global epoch wraps around in 31bits: https://github.com/crossbeam-rs/crossbeam-epoch/blob/master/src/epoch.rs#L71

Then to my eyes, Epoch::distance() may give us a wrong result: https://github.com/crossbeam-rs/crossbeam-epoch/blob/master/src/epoch.rs#L39 . Suppose e1 is the maximum number that is represented in 31bits (i.e. (1 << 31) - 1), and e2 is the next epoch, which is represented in 0. Then distance() gives us (1 << 31) - 1, while a desired result is 1.

This will probably happen in a long-running process in 32bit machines.

I'd like to propose to change Epoch::distance() as follows:

    fn decompose(&self) -> (usize, bool) {
        (self.data & !1, (self.data & 1) == 1)
    }

Then the stride of the epoch advancement becomes 2, and we should adjust the implementation a little bit.

`lazy_static` is blocking

As discussed in crossbeam-rs/crossbeam#122 (comment), lazy_static is blocking. It is used for the global registries, the garbage queue, and the global epoch. It would be great if accessing them is non-blocking.

Tsan reports data races on sanitize example

Running

RUSTFLAGS="-Z sanitizer=thread" cargo +nightly run --example sanitize --target x86_64-unknown-linux-gnu

on current master (36f7a36) produces a lot of data race (in dealloc) warnings.
Same is true for running

RUSTFLAGS="-Z sanitizer=thread" cargo +nightly test --target x86_64-unknown-linux-gnu

on this example.

Undocumented/unused "strict_gc" feature

In garbage.rs,

crossbeam-epoch/src/garbage.rs

Lines 31 to 35 in 02c2c59

	/// Maximum number of objects a bag can contain.
	#[cfg(not(feature = "strict_gc"))]
	const MAX_OBJECTS: usize = 64;
	#[cfg(feature = "strict_gc")]
	const MAX_OBJECTS: usize = 4;

a feature named "strict_gc" is used but is not documented anywhere. Is this a feature used when testing, or is this something that can be removed?

Guard::defer is a footgun

@Amanieu just hit an annoying bug where he forgot to write move before the closure:

guard.defer(|| Self::finalize(self));

The documentation of defer suggests always using move, but it's too easy to forget about this rule and run into very difficult to find bugs. Clearly, we should do something here.

My suggestion is to have two variants of defer, a checked and an unchecked version (similar to get vs get_unchecked, or unreachable!() vs unreachable_unchecked()):

fn defer<F, R>(&self, f: F)
where
    F: FnOnce() -> R + Send + 'static;

unsafe fn defer_unchecked<F, R>(&self, f: F)
where
    F: FnOnce() -> R;

That means the original call to defer would be written as:

let ptr = self as *const _ as usize;
guard.defer(|| Self::finalize(ptr as *const Self));

Or, using the more dangerous option:

guard.defer_unchecked(move || Self::finalize(self));

This situation reminds me of spawn_unsafe (it should really be named spawn_unchecked), which is equivalent to std::thread::spawn, except it doesn't require F: 'static (and the F: Send bound should probably be lifted too, IMO; see this).

assertion failure: "participant was expected to be unpinned"

I'm running into an assertion failure on this line, "participant was expected to be unpinned." Is that error possible to induce via incorrect use of Crossbeam, or does it represent a bug in Crossbeam? If it's the latter, I can provide more details.

Supporting Rust 1.12 for Rayon

In order to use Crossbeam in Rayon, we need to support Rust 1.12. More discussions are in: rayon-rs/rayon#480 .

I hope it is the only remaining blocker for Rayon.

tests are failing on i686

failures:
---- src/atomic.rs - atomic::Owned<T>::with_tag (line 679) stdout ----
	thread 'rustc' panicked at 'test executable failed:
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `5`', src/atomic.rs:9:0
note: Run with `RUST_BACKTRACE=1` for a backtrace.
', src/librustdoc/test.rs:323:16
note: Run with `RUST_BACKTRACE=1` for a backtrace.
---- src/atomic.rs - atomic::Shared<'g, T>::tag (line 984) stdout ----
	thread 'rustc' panicked at 'test executable failed:
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `5`', src/atomic.rs:10:0
note: Run with `RUST_BACKTRACE=1` for a backtrace.
', src/librustdoc/test.rs:323:16
---- src/atomic.rs - atomic::Shared<'g, T>::with_tag (line 1003) stdout ----
	thread 'rustc' panicked at 'test executable failed:
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `5`', src/atomic.rs:13:0
note: Run with `RUST_BACKTRACE=1` for a backtrace.
', src/librustdoc/test.rs:323:16
failures:
    src/atomic.rs - atomic::Owned<T>::with_tag (line 679)
    src/atomic.rs - atomic::Shared<'g, T>::tag (line 984)
    src/atomic.rs - atomic::Shared<'g, T>::with_tag (line 1003)
test result: FAILED. 38 passed; 3 failed; 3 ignored; 0 measured; 0 filtered out

Interestingly, tests didn't fail on armv7hl (which is also 32bit).

`cargo build` fails in Rust Nightly 1.24.0 (2017-11-27)

$ rustc --version
rustc 1.24.0-nightly (560a5da9f 2017-11-27)

$ cargo build
   Compiling crossbeam-epoch v0.1.0 (file:///Users/jeehoon.kang/Works/crossbeam-epoch)
error[E0119]: conflicting implementations of trait `core::convert::Into<std::boxed::Box<_>>` for type `atomic::Owned<_>`:
   --> src/atomic.rs:732:1
    |
732 | / impl<T> Into<Box<T>> for Owned<T> {
733 | |     /// Converts the owned pointer into a `Box`.
734 | |     ///
735 | |     /// # Examples
...   |
748 | |     }
749 | | }
    | |_^
    |
    = note: conflicting implementation in crate `core`:
            - impl<T, U> core::convert::Into<U> for T
              where U: core::convert::From<T>;

error: aborting due to previous error

error: Could not compile `crossbeam-epoch`.

To learn more, run the command again with --verbose.

Specifying minimum patch level for dependencies

Currently, crossbeam-epoch specifies only major and minor version numbers for dependencies.
We agreed upon this in: #48 (comment) , and our Cargo.toml requires crossbeam-utils "0.2" rather than "0.2.1", where 0.2.1 is the the minimum required version. The main argument for requiring "0.2" (discussed in IRC) is basically no one specifies patch level.

However, recently I met: https://github.com/nikomatsakis/lalrpop/blob/master/lalrpop/Cargo.toml which specifies patch levels in its Cargo.toml. Note that lalrpop is is arguably one of the most popular crates for parsing.

For this precedence and the reason I wrote in #48 (comment) (mainly e.g. "0.2" can be resolved to either 0.2.0 or 0.2.1), I'd like to specify patch level for dependencies, namely crossbeam-utils "0.2.1" rather than "0.2".

Removing *_owned methods

Have a look at the following methods on Atomic<T> we currently implement:

Click to expand

impl<T> Atomic<T> {
    pub fn store(&self, new: Ptr<T>, ord: Ordering) {
        self.data.store(new.data, ord);
    }

    pub fn store_owned(&self, new: Owned<T>, ord: Ordering) {
        let data = new.data;
        mem::forget(new);
        self.data.store(data, ord);
    }

    pub fn swap<'scope>(&self, new: Ptr<T>, ord: Ordering, _: &'scope Scope) -> Ptr<'scope, T> {
        Ptr::from_data(self.data.swap(new.data, ord))
    }

    pub fn compare_and_set<'scope, O>(
        &self,
        current: Ptr<T>,
        new: Ptr<T>,
        ord: O,
        _: &'scope Scope,
    ) -> Result<(), Ptr<'scope, T>>
    where
        O: CompareAndSetOrdering,
    {
        match self.data.compare_exchange(
            current.data,
            new.data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => Ok(()),
            Err(previous) => Err(Ptr::from_data(previous)),
        }
    }

    pub fn compare_and_set_owned<'scope, O>(
        &self,
        current: Ptr<T>,
        new: Owned<T>,
        ord: O,
        _: &'scope Scope,
    ) -> Result<Ptr<'scope, T>, (Ptr<'scope, T>, Owned<T>)>
    where
        O: CompareAndSetOrdering,
    {
        match self.data.compare_exchange(
            current.data,
            new.data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => {
                let data = new.data;
                mem::forget(new);
                Ok(Ptr::from_data(data))
            }
            Err(previous) => Err((Ptr::from_data(previous), new)),
        }
    }
}

It's interesting that swap_owned is missing, although it is not stricly speaking necessary: a.swap_owned(o, ord, scope) would be equivalent to a.swap(o.into_ptr(scope), ord, scope). But, for the sake of consistency and convenience, we should probably have swap_owned as well.

There's a lot of duplication. We have one set of functions for Ptr and another for Owned. Let's try to unify them. First, we could introduce a trait that is implemented by Ptr and Owned:

/// A trait implemented by `Owned<T>` and `Ptr<T>`.
pub trait OwnedOrPtr<T> {
    fn into_data(self) -> usize;
    unsafe fn from_data(data: usize) -> Self;
}

impl<T> OwnedOrPtr<T> for Owned<T> {
    fn into_data(self) -> usize {
        let data = self.data;
        mem::forget(self);
        data
    }

    unsafe fn from_data(data: usize) -> Self {
        Owned::from_data(data)
    }
}

impl<'scope, T> OwnedOrPtr<T> for Ptr<'scope, T> {
    fn into_data(self) -> usize {
        self.data
    }

    unsafe fn from_data(data: usize) -> Self {
        Ptr::from_data(data)
    }
}

Second, let's clarify the return value of compare_and_set_owned. Instead of returning

Result<Ptr<'scope, T>, (Ptr<'scope, T>, Owned<T>)>

we could return something like

Result<Ptr<'scope, T>, CompareAndSetError<'scope, T>>

But let's make the error type a little bit more generic:

pub struct CompareAndSetError<'scope, T: 'scope, N> {
    /// The previous value in the `Atomic<T>`.
    pub previous: Ptr<'scope, T>,
    /// The new value that the compare-and-set operation failed to write.
    pub new: N,
}

Finally, now we're ready to eliminate all those *_owned functions. The new set of store/swap/compare-and-set functions is much smaller than the one at the beginning of this comment.

impl<T> Atomic<T> {
    pub fn store<N>(&self, new: N, ord: Ordering)
    where
        N: OwnedOrPtr<T>,
    {
        self.data.store(new.into_data(), ord);
    }

    pub fn swap<'scope, N>(&self, new: N, ord: Ordering, _: &'scope Scope) -> Ptr<'scope, T>
    where
        N: OwnedOrPtr<T>,
    {
        Ptr::from_data(self.data.swap(new.into_data(), ord))
    }

    pub fn compare_and_set<'scope, N, O>(
        &self,
        current: Ptr<T>,
        new: N,
        ord: O,
        _: &'scope Scope,
    ) -> Result<Ptr<'scope, T>, CompareAndSetError<'scope, T, N>>
    where
        N: OwnedOrPtr<T>,
        O: CompareAndSetOrdering,
    {
        let new_data = new.into_data();
        match self.data.compare_exchange(
            current.data,
            new_data,
            ord.success(),
            ord.failure(),
        ) {
            Ok(_) => Ok(Ptr::from_data(new_data)),
            Err(previous) => Err(CompareAndSetError {
                previous: Ptr::from_data(previous),
                new: unsafe { N::from_data(new_data) },
            })
        }
    }
}

The obvious downside is that the OwnedOrPtr<T> trait makes function signatures slightly more complicated. But maybe it's not too bad...? Maybe it's worth it in the end? What do you think?

More impls for Ptr

Since Ptr is just a pointer, it might make sense to implement Eq for it.

Currently, to compare whether two Ptrs are equal, one has to do: a.as_raw() == b.as_raw(). Why shouldn't we be able to do just a == b?

Maybe we could implement Ord, Hash, and std::fmt::Pointer as well.

Removing `from_*` methods

e.g. as far as we implement From<Owned<T>> for Atomic<T>, Atomic::from_owned() is redundant. I don't see much benefit of having these methods..