AtomicCell<T> - actually a Box with Cell semantics and lock-free atomicity

[Soni]

Something I’ve been missing in Rust from some other languages is AtomicReferences, basically lock-free thread-safe (mutable) data containers.

This could be done as a safe wrapper around AtomicPtr. Such a safe wrapper would work much like Cell<T>, but with heap-allocated T, powered by AtomicPtr.

For your average type there would be the basics “new”, “set”, “replace”, “swap”, similar to standard Cell<T>. The main difference is that AtomicCell<T> would be Send + Sync, which makes it usable in Arc<T>.

You might’ve noticed there would be no “get”. That’s because the following could happen:

1. Thread A retrieves pointer atomically.
2. Thread B swaps pointer atomically.
3. Thread B frees old pointer. (!)
4. Thread A reads (now freed) pointer. (!)

This would be most likely to happen as a result of “acell.replace(x)”, which allocates space for the replacement, swaps the pointers, copies the old value onto the stack, drops the old pointer, and returns. (I don’t know how to solve this.)

This provides a very basic safe wrapper around AtomicPtr. So basic that it can’t even compare and swap! What’s the point of going lock-free if you can’t benefit from it? Well… the idea is that it would have compare and swap, I just haven’t figured this out yet.

It would be really nice to have that compare and swap functionality, and it’s the main reason why I want something like this. But I’m having a hard time figuring it out.

[jdm]

This sounds like you’re looking for the atomic crate, which provides an Atomic<T> type for any T: Copy. For non-copy types, Servo relies on the atomic_refcell crate. There’s also an old atomic_cell crate which probably requires some updates to work on stable Rust.

[jmst]

Actually what he is looking for might be the AtomicOption<T> type from the crossbeam crate, which is the atomic equivalent of Cell<Option<Box<T>>>.

If you need Arc support in addition to Box, atomic-option has a version that supports it, but it seems unmaintained.

If you need Arc support and compare and swap, you’ll probably have to implement it yourself by modifying the atomic-option crate.

[obviously you can’t have compare and swap with Box, because without a mutex it can’t be applied to the content, and you can’t apply it to the pointer since you no longer own the box in the cell]

[Soni]

Ok so first, I’m a they.

Second, none of those seem to support Java semantics. (which does have a GC, but I don’t think a GC is necessary for this.)

Third, do we know if they are actually safe? “atomic” is probably safe, but it does make some significant tradeoffs (only works for Copy types with power of two size and alignment, for example, which means it’s neither a Box nor a Cell at all but instead probably relies on transmutation to/from AtomicUsize). “atomic_refcell” is apparently designed to panic all the time as much as possible. “atomic_cell” I haven’t looked into enough. “atomic-option” does provide that safety guarantee by swapping out an option, but it’s definitely not the nicest way to make lock-free algorithms.

[bossmc]

Self-advertising here, but I wrote https://crates.io/crates/pinboard to cover a similar problem in this area.

GC was needed to allow predictable decisions over who drops the stored T on a swap/set and making sure they don’t do it too early.

I’ve hammered this crate pretty hard in my projects at work and it’s held up well, the logic has been reviewed by the guys at crossbeam and there’s a (possibly currently shelved) plan to move it into crossbeam directly at some point.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.