Pre-RFC: Extended atomic types


#1

There have been several requests to add additional atomic types to Rust (here and here). One of the main drivers for this change is that some lock-free algorithms requires a double-word compare-and-swap, which is currently not possible in Rust since the largest atomic type is only one word long.

Regarding platform support: after a quick survey of the LLVM and Clang code, architectures can be classified into 3 categories:

  • The architecture does not support any form of atomics (mainly microcontroller architectures).
  • The architecture supports all atomic operations for integers from i8 to iN (where N is the architecture word/pointer size).
  • The architecture supports all atomic operations for integers from i8 to i(N*2).

There are several ways in which this support can be implemented. This pre-RFC is intended to give an overview of each approach and elicit feedback from the community for which approach should be considered for an RFC. New ideas are o course welcome, and I will add them to this post.

Atomic pair types

#[cfg(target_atomic_pair)]
struct AtomicPtrPair<T, U> {}
#[cfg(target_atomic_pair)]
struct AtomicUsizePair {}
#[cfg(target_atomic_pair)]
struct AtomicIsizePair {}

These types would work like existing atomic types except that instead of working with single value they would work with tuple pairs. For example AtomicPtrPair<T, U> would allow atomically swapping a (*mut T, *mut U).

A #[cfg] attribute is used to only make these types available on architectures that support them. User code will be able to use this same attribute to select between code using atomic pairs and code using other synchronization (such as a mutex).

The downside of this approach is that sometimes you want to have a (*mut T, usize), and adding new types for each combination is impractical.

More atomic integer types

struct AtomicI8 {}
struct AtomicU8 {}
struct AtomicI16 {}
struct AtomicU16 {}
struct AtomicI32 {}
struct AtomicU32 {}
#[cfg(target_atomic_64)]
struct AtomicI64 {}
#[cfg(target_atomic_64)]
struct AtomicU64 {}
#[cfg(target_atomic_128)]
struct AtomicI128 {}
#[cfg(target_atomic_128)]
struct AtomicU128 {}

These types are fairly straightforward extensions of the existing AtomicIsize and AtomicUsize types, and support the same methods. Structs can be used with these atomics by transmuting them to an integer type before storing them in an atomic variable.

As with the previous approach, a #[cfg] attribute is used to conditionally expose the 64-bit and 128-bit atomic types. These are not required for 8, 16 and 32-bit atomic types because these are always available on all architectures that support atomics.

One downside is that AtomicI128 and AtomicU128 would probably require adding i128 and u128 to Rust, which brings another set of issues:

  • 128-bit integers are only available on 64-bit platforms, not 32-bit ones.
  • Adding i128 and u128 to the prelude would probably be a breaking change.

Generic atomic type

struct Atomic<T> {}

This would allow any type to be made atomic, similarly to the C++ std::atomic<T> type. The given type T is padded so that its size is a power of two and it is aligned to its size. If a native atomic type of the required size is not available, the atomic operations are transparently translated into a runtime library call which emulates the atomic operation using mutexes.

While this provides a great amount of flexibility, there are two major downsides. The first is that there is no way to implement such a type with the language features currently available (manipulating size and alignment in generic types). The second is that automatically translating atomic operations into runtime library calls can result in surprising behavior because the emulated operation uses a lock.

Generic atomic type with size restrictions

struct Atomic<T>
where sizeof(T) < 64/128
{}

This is the same as the previous approach without the option to fall back to a library call. Instead any type that does not fit in a native atomic type will cause a compile-time error. Unfortunately this still doesn’t resolve the first issue, which is that implementing such a type is not possible with the current set of language features. It also becomes harder for a user to know whether his code will compile on any given architecture.

Generic atomic type based on a trait

trait AtomicOps {
    fn compare_and_swap(self: *mut Self, current: Self, new: Self, order: Ordering) -> Self;
    fn swap(self: *mut Self, val: Self, order: Ordering) -> Self;
    fn load(self: *mut Self, order: Ordering) -> Self;
    fn store(self: *mut Self, val: Self, order: Ordering);
}
trait AtomicIntOps: AtomicOps { // Implemented for integers
    fn fetch_add(self: *mut Self, val: Self, order: Ordering) -> Self;
    fn fetch_sub(self: *mut Self, val: Self, order: Ordering) -> Self;
}
trait AtomicLogicalOps: AtomicOps { // Implemented for integers and bool
    fn fetch_and(self: *mut Self, val: Self, order: Ordering) -> Self;
    fn fetch_nand(self: *mut Self, val: Self, order: Ordering) -> Self;
    fn fetch_or(self: *mut Self, val: Self, order: Ordering) -> Self;
    fn fetch_xor(self: *mut Self, val: Self, order: Ordering) -> Self;
}

struct Atomic<T: AtomicOps> {}
impl Atomic<T> where T: AtomicOps {}
impl Atomic<T> where T: AtomicIntOps {}
impl Atomic<T> where T: AtomicLogicalOps {}

impl AtomicOps for bool {}
impl AtomicOps for isize {}
impl AtomicOps for *const T {}
impl AtomicOps for *mut T {}
impl AtomicOps for i8 {}
impl AtomicOps for i16 {}
impl AtomicOps for i32 {}
#[cfg(target_atomic_64)]
impl AtomicOps for i64 {}
#[cfg(target_atomic_128)]
impl AtomicOps for i128 {}

// And now the types in `std` can be recovered as:
type AtomicBool = Atomic<bool>;
type AtomicIsize = Atomic<isize>;
type AtomicUsize = Atomic<usize>;
type AtomicPtr<T> = Atomic<*mut T>;

This approach is a mix between adding more atomic integer types and a generic atomic type. This uses a generic Atomic<T> type which only supports a predefined set of T types for which atomic operations are defined.

A #[cfg] attribute is still needed to restrict support for 64-bit and 128-bit atomics on platforms that don’t support them, and a i128 type is needed for 128-bit atomics.


#2

I’ve wondered this before: Even for the type-specific atomic types (and this goes for the types already in std as well), wouldn’t it be more economical to define the type generically and only restrict the available methods to the types for which they are supported? I’m thinking of something like this:

pub struct Atomic<T> { data: T }

pub trait AtomicOps {
    fn compare_and_swap(self: &Atomic<Self>, current: T, new: T order: Ordering) -> bool;
    /* ...and others... */
}

impl AtomicOps for isize { ... }
impl AtomicOps for usize { ... }
impl AtomicOps for bool { ... }
impl<T: Sized> AtomicOps for *mut T { ... }

// And now the types in `std` can be recovered as:
pub type AtomicBool = Atomic<bool>;
pub type AtomicIsize = Atomic<isize>;
pub type AtomicUsize = Atomic<usize>;
pub type AtomicPtr<T> = Atomic<*mut T>;

// And we can go ahead and add further `impl`s without having to define a whole new type for each:
impl<T: Sized> AtomicOps for *const T { ... }
impl<'a, T: Sized> AtomicOps for &'a T { ... } // why not?
impl AtomicOps for (i32, u32) { ... }
/* and so on... */

I know the stdlib tends to shy away from providing trait-based abstractions (see also the wrapping_* methods), but I think that can be taken too far: it seems like a clear win in this case. Unless some low-level details get in the way of formulating it in this way.


#3

I really like your idea! I’ve added it to my post, I think it’s the best one so far.


#4

I proposed this initially but @aturon felt like it did not make sense, as the set of operations varies is not the same amongst all types. (For example, integers support fetch_add but bool does not.) It may be though that this could be accommodated with a deeper trait hierarchy.


#5

Oh, a few more notes:

  1. I hadn’t thought of applying this trait to thing like tuples etc.
  2. There are indeed many platform specific differences here which would probably show up just as different impls per platform. I am not sure how I feel about this – having types come and go on a platform specific basis feels easier to document and less surprising.
  3. Note also that your proposal is not strictly backwards compatible, just because of details around inherent fns and trait fns and so forth, but I think you could just keep the existing types.

#6

There’s also the question of how to expose 128-bit atomic types. The most obvious way would be to add i128 and u128 to the language but a temporary workaround would be to use (u64, u64) instead.


#7

Upon further reflection this seems more or less exactly analogous to the situation with checked arithmetic, except std actually made different choices for the two. In each case there are three designs:

  1. Neither the types nor the methods are generic. For each built-in type supporting the operations, a newtype struct is defined to wrap it and provide the operations.

  2. The type is generic but the methods are not, in other words there are separate inherent impls on the generic type for each supported type parameter.

  3. Both the type and the methods are generic, which means that the methods are abstracted by traits. This raises some further questions around the right way to organize them.

(Hopefully it’s apparent that for wrapping arithmetic the stdlib goes with 2., while for atomic operations it goes with 1.)

There is a tradeoff between 2. and 3.: 3. lets client code be generic over types supporting the given operations, but 2. requires fewer imports and fewer decisions to make in the design. However, I don’t see any advantage for 1. Does anyone else?


#8

@Amanieu I’ve opened an issue in the RFC repo about atomic pointers to functions: https://github.com/rust-lang/rfcs/issues/2481, I don’t know if it would be possible to support those (and pairs), with your API.