Provide support for arbitrary width atomics from 16bit to 2x word size (u16, u32, u64, u128) #24564
Description
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.