Need help porting a wait free trie from C to Rust

Question

For some HPC computing I need to port a wait free trie (but you can think of it as a tree) from C to Rust. The trie is 99% read 1% write, and is used both in parallel-concurrent scenarios , and concurrent only scenarios (single thread with multiple coroutines). The size of the tree is usually between 100kb and 8 mb.

Basically the tree is like:

pub struct WFTrie {
    nodes: Vec<Node>,
    leaves: Vec<Leaf>,
    updates: Vec<Update>,
    update_pos: AtomicUsize,
    update_cap: usize,
}

//.... 
let mut wftrie = WFTrie::new(); 
let wftrie_ptr = AtomicPtr::new(&mut wftrie);

//....

As you can see the trie already uses something very similar to the arena approach that many suggests, by using a vec and storing

• When I want to update, I do a fetch_and_add on update_pos. If it's greater than update_cap I return an error (size exhausted), otherwise I'm sure sure my coroutine/thread has exclusive access to updates[update_pos % update_cap], where I can put my update

• Every X updates (if update_pos % 8 == 0 { //update tree} ) a coroutine will clone the tree, apply all pending updates, and then compare_and_swap the wftrie_ptr

• When I want to read I do an atomic load on wtftrie_ptr and I can access the tree, taking care of considering also the pending updates.

My questions are:

• If I have multiple coroutines having an immutable reference, how can I have one coroutine doing updates? What's the most idiomatic way to translate this to rust?

• If a coroutine is still holding a ref to the old tree during an update what happens? Should I replace the AtomicPtr with Arc?

• Does this design fit well with the rust borrow checker or am I going to have to use unsafe?

• In the case of concurrent only scenario, can I drop atomics without using unsafe?

Answer 1

I'm not particularly informed about HPC, but I hope I can give you some useful pointers about programming with concurrency in Rust.

… I'm sure sure my coroutine/thread has exclusive access to updates[update_pos], where I can put my update

This is necessary, but not sufficient: if you are going to write to data behind an & reference (whether from multiple threads or not), then you are implementing interior mutability, and you must always signal that to the compiler by using some cell type. The minimal at-your-own-risk way to do that is with an UnsafeCell, which provides no synchronization and is unsafe to operate on:

    updates: Vec<UnsafeCell<Update>>,

but you can also use a safer type such as a lock (that you know will never experience any contention since you arranged that no other thread is using it). In Rust, all locks and other interior mutability primitives — including atomics — are built on top of UnsafeCell; it is how you tell the compiler “this memory is exempt from the usual rule of N readers xor 1 writer”.

Every X updates … a coroutine will clone the tree …

You will have to arrange so that the clone isn't trying to read the data that is being modified. That is, don't clone the WFTrie, but only the nodes and leaves vectors since that's the data you actually need.

If you were to use UnsafeCell or a lock as I mentioned above, then you'll find that you can't just clone the updates vector, precisely because it wouldn't be sound to do so without explicit locking. If necessary, you can read it step-by-step in some way that agrees with your concurrency requirements.

If I have multiple coroutines having an immutable reference, how can I have one coroutine doing updates? What's the most idiomatic way to translate this to rust?

I'm not aware of a specifically Rust-y way to do this. It sounds like you could manage it with just an AtomicBool, but you probably know more than I do here.

If a coroutine is still holding a ref to the old tree during an update what happens? Should I replace the AtomicPtr with Arc?

Yes, this is a problem. Note that AtomicPtr is unsafe to read, because it does not guarantee the pointed-to thing is alive. You need a way to use something like Arc and atomically swap which specific Arc is in the wftrie_ptr location; the arc-swap library provides that.

Does this design fit well with the rust borrow checker or am I going to have to use unsafe?

From a perspective of using the data structure, it seems fine — it will not be any more inconvenient to read or write than any other data structure held behind Arc.

For implementation, you will not be having very much “fight with the borrow checker” because you are not going to be writing functions with very many borrows — since your data structure owns its contents. But, insofar as you are writing your own concurrency primitives with unsafe, you will need to be careful to obey all the memory rules anyway. Remember that unsafe is not a license to disregard the rules; it's telling the compiler “I'm going to obey the rules but in a way you can't check”.

In the case of concurrent only scenario, can I drop atomics without using unsafe?

Yes; in a no-threads scenario, you can use Cell for all purposes that atomics would serve.