How to freeze an Rc data structure and send it across threads

user_890016 0
Viewed 302

My application works in two phases:

  1. A large data structure is created, involving lots of temporary objects and using reference counting for heap management
  2. The data structure is made read only, anything that is still alive is parked, and the resulting structure is sent to another thread to be read.

(For extra concreteness, the application is a language server, and the data structures are processed individual files, which are processed single threaded but the results of which have to be passed across threads.)

Currently, I am using Arc<T> to manage the data structure, but because phase 1 is large and expensive and single threaded, I would like to switch it to use Rc<T>. But Rc is neither Send nor Sync for good reason, and I can't send the data structure or a reference to it unless basically everything in the program uses thread-safe primitives.

I would like to reason that after phase 2 starts, we don't need reference counting anymore; thread 1 (the owner) is not allowed to touch the reference counts and thread 2 (the borrower) is not allowed to clone the data, only look at it, so it can't touch the reference counts either. I know that Rc will not provide this set of guarantees, because you could clone an Rc given the shared reference. Is there a safe API for this pattern? Ideally I would not have to copy any data when going from phase 1 to phase 2.

Here's a toy implementation, just to put some code to it. The function phase1() generates lots of garbage before returning a data structure of type T, which is then analyzed in a read only way in phase2() on another thread. If you change Arc in this code for Rc, you will get an error because it can't be sent across threads.

use std::sync::Arc;
use crossbeam::thread::scope; // uses the crossbeam crate for scoped threads

enum T { Nil, More(Arc<T>) }

fn phase1() -> T {
    let mut r = T::Nil;
    for i in 0..=5000 {
        r = T::Nil;
        for _ in 0..i { r = T::More(Arc::new(r)) }
    }
    r
}

fn phase2(mut t: &T) {
    let mut n = 0;
    while let T::More(a) = t {
        n += 1;
        t = a;
    }
    println!("length = {}", n); // should return length = 5000
}

fn main() {
    let r = phase1();
    scope(|s| { s.spawn(|_| phase2(&r)); }).unwrap();
}
rust reference-counting multithreading
1 Answers

It is not exactly clear to me what you are trying to accomplish in the larger picture. My takeaway is that you don't want to use an Arc just so that the data structure can be sent between threads, which only occurs once. One can do this by wrapping the type in another type for which you manually implement Send. This is really, really unsafe because the compiler will not be able to guard against race conditions.

use std::rc::Rc;
use std::thread::spawn;

// Foo is not Send because it contains a Rc
struct Foo {
    bar: Rc<bool>,
}

// Foowrapper is forced to be Send
struct FooWrapper {
    foo: Foo,
}
unsafe impl Send for FooWrapper {}

fn main() {
    println!("Hello, ");

    // We can't send a Foo...
    let foo = Foo {
        bar: Rc::new(false),
    };

    // This blows everything up, and there is no
    // protection by the compiler
    // let secret_bar = Rc::clone(&foo.bar);

    // ...but we can send a FooWrapper.
    // I hereby promise that I *know* Foo is in a
    // state which is safe to be sent! I really checked
    // and no future updates in the code will harm me, ever!
    let wrap = FooWrapper { foo };
    spawn(move || {
        // Unwrap the Foo.
        let foo: Foo = wrap.foo;
        println!("{:?}", foo.bar);
    })
    .join()
    .unwrap();
}

In the above example, we send a data structure that contains an Rc, which is not Send. By wrapping in a FooWrapper, it becomes Send. However, it is left to us to be 100% sure that at the moment where FooWrapper is sent to the other thread, the inner Foo is safe to be sent. For instance, this is not true if the main thread has a clone of one of bar (e.g. let secret_bar = Rc::clone(&foo.bar);) and holds it beyond the point of sending. This would allow both threads to drop their version of bar unsynchronized, wrecking the Rc.

user_27229680
Related