Provide support for arbitrary width atomics from 16bit to 2x word size (u16, u32, u64, u128)

[rrichardson]

In order to perform many tasks without locks, CAS requires two values in order to avoid the ABA Problem

Typically, the first value is the item which needs to be swapped, and the 2nd is an independently adjust variable which reduces the likelyhood that a value can be swapped in, and swapped out without competing threads observing it.

For example, popping off of a list based stack might look like:

let mut head = [0u64, 0u64];
let mut next = [0u64, 0u64];

loop {  
    head = hdr.head_offset.load(Ordering::Relaxed);
    next[0] = get_list(head[0]).next_offset;
    next[1] = head[1] + 1;
    if hdr.head_offset.compare_and_swap(head, next, Ordering::SeqCst) {
        break;
    }
}

Note that even better, many atomic libs, such as concurrency kit provide additional functionality. When a CAS fails, it will put the updated value (which resides in hdr.head_offset) into another param of your choosing, making the cas loop more efficient and possibly doing so atomically.

So the updated value is placed into head, thus avoiding the need to put hdr.head_offset.load inside the loop.

I do recommend looking to concurrencykit for examples, we have used that library in a significant amount of production code with great success. However, the API provided by Atomic*.compare_and_swap is fine, as it always returns the value that was present in the variable at the time of the cas.

caveats
It seems like it would be straightforward to provide support for Usize atomic arrays, but doing such a thing with the pointer type (where my interests lie) would violate type safety mildly :)

Also, one major limitation right now is that when performing a cas, most architectures require an array to be aligned to the size of the array. e.g. on a 64 bit system, an AtomicUsize or AtomicPtr double width CAS would require the array to be aligned on a 16 byte boundary. I am not sure of a way to guarantee this happens if/when the data types are in structs.

[nagisa]

Related: rust-lang/rfcs#521. I believe adding quad-width types would also involve adding atomic operation support for them.

[huonw]

How many architectures support double-width atomics in the CPU? (x86-64 with cmpxchg16b is one.)

[huonw]

(Also alignment isn't a particular problem, e.g. the SIMD types have similarly higher alignment requirements.)

[rrichardson]

ARMv[78]-A support double register CAS. I haven't checked, but I am assuming LLVM's cmpxchg handles that correctly. Between that and x86 I think 99% of the relevant platforms are covered. (the rest are typically not multithreaded archs :)

[rrichardson]

After having used atomics a bit more for non-trivial things, I think I want to refine this issue into supporting atomics based on the standard integer sizes rather than just usize, isize and ptr. This might also require rust-lang/rfcs#521 to support 128bit values as a native type.

[cesarb]

The RISC-V architecture (http://riscv.org/) doesn't support double-wide compare-and-swap. It supports only Load-Reserved/Store-Conditional, which is an alternative way of avoiding the ABA problem. See page 30 of http://riscv.org/wp-content/uploads/2015/11/riscv-spec-v2.0.pdf.

I don't think it would be a good idea to have in the standard library an API which can only support DW-CAS but not LR/SC, or vice-versa. In the same way, having an AtomicU64 or AtomicI64 wouldn't be a good idea, since it rules out 32-bit processors without DW-CAS.

Even modern 64-bit x86 systems without DW-CAS do exist; see for instance http://www.pcworld.com/article/2058683/new-windows-8-1-requirements-strand-some-users-on-windows-8.html.

[japaric]

We now have Atomic* types for 8/16/32/64-bit atomic operations. An RFC for 128-bits have been accepted (#35118) but that doesn't include 128-bit atomics AFAIU (cc @Amanieu). If not, support for 128-bit atomics would have to be requested via an RFC. Should this be closed? cc @alexcrichton

[Amanieu]

The intent was to include 128-bit atomics as part of the int128 RFC.

[alexcrichton]

Yeah I believe we can close this now, thanks for the heads up @japaric!