Send/Sync bound needed on V in `impl Send/Sync for ARCache<K, V>`

[JOE1994]

Hello! 🦀
While scanning crates.io., we (Rust group @sslab-gatech) have noticed a soundness/memory safety issue in this crate which allows safe Rust code to trigger undefined behavior.

Issue

Currently Send & Sync for ARCache<K, V> is implemented as below.

unsafe impl<K: Hash + Eq + Ord + Clone + Debug, V: Clone + Debug> Send for ARCache<K, V> {}
unsafe impl<K: Hash + Eq + Ord + Clone + Debug, V: Clone + Debug> Sync for ARCache<K, V> {}

In the Send impl, there is no Send bound on V. In the Sync impl, there is no Sync bound on V.
It is possible to insert a non-Sync item to ARCache and share it across multiple threads.

Proof of Concept

I wrote a minimal proof-of-concept that exploits this issue to cause undefined behavior in safe Rust.
To observe undefined behavior, you need to run the below program in Debug mode.
In the program below, multiple threads clone & drop Rc(neither Send nor Sync) which is inside ARCache.
Since Rc's internal strong_count is updated by multiple threads without synchronization,
the program will terminate in either one of the following states.

• strong_count > 1
  • program panics at the assertion check at the end (memory leak)
• strong_count == 0
  • Rc is dropped while references to it are still alive.
    When run on Ubuntu 18.04, program crashes with error: Illegal Instruction (Core Dumped)
• strong_count == 1
  • Not impossible, but highly unlikely

#![forbid(unsafe_code)]
use concread::arcache::ARCache;

use std::sync::Arc;
use std::rc::Rc;

fn main() {
    let non_sync_item = Rc::new(0); // neither `Send` nor `Sync`
    assert_eq!(Rc::strong_count(&non_sync_item), 1);

    let cache = ARCache::<i32, Rc<u64>>::new_size(5, 5);
    let mut writer = cache.write();
    writer.insert(0, non_sync_item);
    writer.commit();

    let arc_parent = Arc::new(cache);

    let mut handles = vec![];
    for _ in 0..5 {
        let arc_child = arc_parent.clone();
        let child_handle = std::thread::spawn(move || {
            let reader = arc_child.read(); // new Reader of ARCache
            let smuggled_rc = reader.get(&0).unwrap();
            
            for _ in 0..1000 {
                let _dummy_clone = Rc::clone(&smuggled_rc); // Increment `strong_count` of `Rc`
                // When `_dummy_clone` is dropped, `strong_count` is decremented.
            }
        });
        handles.push(child_handle);
    }
    for handle in handles {
        handle.join().expect("failed to join child thread");
    }

    assert_eq!(Rc::strong_count(arc_parent.read().get(&0).unwrap()), 1);
}

How to fix the issue?

I think this issue can be solved by adding Send/Sync bounds to the current Send/Sync impls as below.

// Added `Send` bound to `V`
unsafe impl<K: Hash + Eq + Ord + Clone + Debug, V: Clone + Debug + Send> Send for ARCache<K, V> {}
// Added `Sync` bound to `V`
unsafe impl<K: Hash + Eq + Ord + Clone + Debug, V: Clone + Debug + Sync> Sync for ARCache<K, V> {}

Thank you for checking out this issue! 👍 🐱

[Firstyear]

Hi there, thanks for reporting this. Indeed I think you have found a real issue here, and I'm able to reproduce it with your example code. The unsafe Send + Sync had to be implemented due to the presence of *mut Node<K, V> in the underlying structures. Previously a similar issue was reported in Ebrcell, and a reproducer exists here https://github.com/kanidm/concread/blob/master/src/unsound.rs

The solution in that case was a Send + 'static bound on T, which works because Rc is not !Send and it prevents references that are not 'static.

I have put the fix of Send + 'static into #49 if you want to check and comment there. I'm still open to adding the Sync bound, but I am not sure it's required in this case, since it's not required in Ebrcell or Cowcell (or maybe it is and I'm wrong :) )

Thanks again for your excellent writeup and for opening this issue!

[Firstyear]

Fixed via #49