Primitive leaks memory

[Vtec234]

I'm sorry to say this, but this scheme is one huge leak. This simple bit of code

    let lk = RcuLock::new(Vec::<u8>::with_capacity(1024));
    for _ in 0..1024 {
        let mut grd = lk.write();
    }

happily leaks ~50kB of memory on my system. Valgrind report:

==21124== Memcheck, a memory error detector
==21124== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==21124== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==21124== Command: ./target/debug/repl
==21124== 
==21124== 
==21124== HEAP SUMMARY:
==21124==     in use at exit: 51,608 bytes in 2,056 blocks
==21124==   total heap usage: 2,070 allocs, 14 frees, 52,852 bytes allocated
==21124== 
==21124== 1,072 (8 direct, 1,064 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 10
==21124==    at 0x4C28EBF: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==21124==    by 0x11007C: alloc::heap::allocate::he9994f5c840a3439 (heap.rs:59)
==21124==    by 0x10FFF0: alloc::heap::exchange_malloc::h42a7945bff40af31 (heap.rs:138)
==21124==    by 0x10E1A5: new<alloc::arc::Arc<collections::vec::Vec<u8>>> (boxed.rs:236)
==21124==    by 0x10E1A5: _$LT$crossbeam..mem..epoch..Owned$LT$T$GT$$GT$::new::h92afcedf701443f0 (mod.rs:153)
==21124==    by 0x10D2AB: _$LT$rculock..RcuLock$LT$T$GT$$GT$::new::hb1c537f80898c60e (isaac.rs:109)
==21124==    by 0x110900: repl::main::he889ee5ac08341a1 (main.rs:9)
==21124==    by 0x13C2FA: __rust_maybe_catch_panic (lib.rs:98)
==21124==    by 0x135D76: try<(),fn()> (panicking.rs:429)
==21124==    by 0x135D76: catch_unwind<fn(),()> (panic.rs:361)
==21124==    by 0x135D76: std::rt::lang_start::haad2d3aa43066bbc (rt.rs:57)
==21124==    by 0x110A12: main (in /home/wojtek/Programming/Rust/repl/target/debug/repl)
==21124== 
==21124== 49,152 (8,192 direct, 40,960 indirect) bytes in 1,024 blocks are definitely lost in loss record 10 of 10
==21124==    at 0x4C28EBF: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==21124==    by 0x11007C: alloc::heap::allocate::he9994f5c840a3439 (heap.rs:59)
==21124==    by 0x10FFF0: alloc::heap::exchange_malloc::h42a7945bff40af31 (heap.rs:138)
==21124==    by 0x10E1A5: new<alloc::arc::Arc<collections::vec::Vec<u8>>> (boxed.rs:236)
==21124==    by 0x10E1A5: _$LT$crossbeam..mem..epoch..Owned$LT$T$GT$$GT$::new::h92afcedf701443f0 (mod.rs:153)
==21124==    by 0x1105AE: _$LT$rculock..RcuGuard$LT$$u27$a$C$$u20$T$GT$$u20$as$u20$core..ops..Drop$GT$::drop::haf9686b400feda32 (lib.rs:104)
==21124==    by 0x10F8B0: drop::h40f4fb563ab45008 (isaac.rs:356)
==21124==    by 0x1109C2: repl::main::he889ee5ac08341a1 (main.rs:12)
==21124==    by 0x13C2FA: __rust_maybe_catch_panic (lib.rs:98)
==21124==    by 0x135D76: try<(),fn()> (panicking.rs:429)
==21124==    by 0x135D76: catch_unwind<fn(),()> (panic.rs:361)
==21124==    by 0x135D76: std::rt::lang_start::haad2d3aa43066bbc (rt.rs:57)
==21124==    by 0x110A12: main (in /home/wojtek/Programming/Rust/repl/target/debug/repl)
==21124== 
==21124== LEAK SUMMARY:
==21124==    definitely lost: 8,200 bytes in 1,025 blocks
==21124==    indirectly lost: 42,024 bytes in 1,026 blocks
==21124==      possibly lost: 0 bytes in 0 blocks
==21124==    still reachable: 1,384 bytes in 5 blocks
==21124==         suppressed: 0 bytes in 0 blocks
==21124== Reachable blocks (those to which a pointer was found) are not shown.
==21124== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==21124== 
==21124== For counts of detected and suppressed errors, rerun with: -v
==21124== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

The reason for this is that the epoch-based memory reclamation is actually not used at all. A crucial element in crossbeam's implementation is the unsafe Guard.unlinked function. It's unsafe, since the programmer has to assert two invariants with respect to the data - that no more references (pointers) to it can be created, and that all existing references are local in the threads that use them (i.e. pointers on function stacks). Only values that have been unlinked in this way can be reclaimed. It's totally the fault of crossbeam docs for not explaining this anywhere, I'll try to write up a fix for them.

Unfortunately, as it currently stands, crossbeam's implementation of the epoch GC cannot be used in this crate. That is because Arcs rely on their destructors to decrement the reference count, and deferred destructors (drop ran during the recollection) are currently not supported in crossbeam. Hopefully I or someone else can get them merged sometime soon, as they block nearly everything else. For now, you could use the ArcCell type instead of Atomic<Arc>. It provides the required functions and won't leak. However, it is not lock-free, so you cannot claim that in your description. I've got an implementation with wait-free reads PR'd here, but we have to wait for maintainers to act.

[nivekuil]

Oh boy. I just noticed that it was leaking memory myself, but I wasn't aware of the cause until reading this writeup - thanks. ArcCell seems like the right way to go for now.

I'm curious about your wait-free ArcCell PR: does the sem spinlock offer any fairness guarantees? Or is the protected section in get() fast enough that starvation won't happen?

[Vtec234]

I haven't spent too much time thinking about that. You raise a good point. The way it works now is that all gets have to finish before set can run, so with many readers any writer thread will definitely be starved. Anyway, ideally there should be an altogether different, better solution, maybe integrating the epoch GC to forgo the need for a lock.

[Vtec234]

It seems that the issue has been fixed.