Adding more atomic intrinsics


#1

Rust currently offers access to many atomic intrinsics: http://doc.rust-lang.org/std/intrinsics/ . They are all based on the atomics implemented in LLVM for C11/C++11.

However, when trying to port some lock-free algorithms, I found that several operations which are supported by LLVM are not exposed by Rust. I am willing to do the work to add them in, but I would like to know first if there is a reason they have been omitted, and what the process is for contributing such a change (one issue on the bug tracker, a RFC, one per modification ?)

Here are the several categories of missing intrinsics I’ve noticed:

1) Compare and exchange with two memory orders

In C11/C++11, compare and exchange is unique in that it takes two different memory orders (the extra argument for atomics that decides which barriers should be added by the compiler): one in case it succeeds, and one in case it fails (always weaker than or equal to the other one). However, rust only allows the programmer to specify the memory order in case of success, picking the strongest possible for the failure case.

2) Weak compare and exchange

On some architectures including ARM and Power it is significantly cheaper to implement compare and exchange when it is allowed to fail spuriously. The programmer can opt in this behaviour in C/C++, it would also be useful in Rust. It could either be an extra boolean argument to compare and exchange, or more likely by duplicating the intrinsics with the “weak” prefix.

3) Different sizes

There has already been some discussion on this on the issue tracker, but it did not result in any clear decision:

It seems that 128 bits atomics are controversial for portability reasons, but I would expect u8/u16/u32 at least to be easily portable.

Please note that I am talking here about the unstable atomic intrinsics, not (at least for the moment) the stable interface that mirrors them. Obviously, it would probably be easy to also modifiy AtomicPtr, AtomicBool, etc… later on.


Pre-RFC: Extended atomic types
#2

cc @aturon @alexcrichton


#3

I prefer for added intrinsics to have a path forward for stabilization rather than just adding them to std::intrinsics (which is unlikely to ever be stabilized), but even along those lines these seem like fine operations to add at least as #[unstable] to the atomic types we have today already.

Unfortunately we can’t change the current definition of compare_and_swap because of backwards compatibility, but I think it’d be ok to just add another method for a CAS with two memory orderings. Similarly it’d also probably be fine to add weak_compare_and_swap.

My only concern about atomic types of fixed-size integers would be platform support. I don’t think a comprehensive survey has been done of what atomic types all of our various supported platforms have and which ones we could expose (e.g. does AArch64 have 8-32 bit atomics?). For me the results of this kind of survey will probably help guide us on where to add these types the standard library (e.g. std::sync::atomic or something like std::arch::x86::atomic)


#4

Atomic operations for sizes less than the size of a pointer can always be built on top of pointer-sized atomics. The only interesting thing you’d get out of a survey is which platforms have double-pointer-size atomics.


#5

Yeah it’s possible to provide an API which uses AtomicUsize as the underlying implementation, but that doesn’t seem like something that necessarily belongs in the standard library (it’s easy to build elsewhere), I’d be more interested in something like struct AtomicU8(u8) where the literal memory representation is precisely what’s needed. I don’t know what the platform support for that looks like.


#6

Only when the access is word aligned, for multibyte values.


#7

No, I meant that you can implement “struct AtomicU8(u8)” on top of pointer-size atomics: if you have pointer-sized compare_and_exchange, you can use it to atomically update any arbitrary byte. LLVM will do this automatically on platforms where it is relevant. See, for example, https://github.com/llvm-mirror/llvm/blob/de0129ac0821e693b08df7269f956f5418b2b5f7/lib/Target/Mips/MipsISelLowering.cpp#L1168 .


#8

Ah right! We’d have to do some trickery to handle things like alignment and make sure we don’t generate a spurious page fault or anything, but this seems like a fairly legit strategy for moving forward.


#9

I just want to voice that I am not in favor of adding features that LLVM supports simply because they are missing. This compulsion has bitten us numerous times. I hate discovering that we’ve exposed some weird LLVM feature needlessly. Unless somebody is going to use these for a real purpose in the near future I do not think we should add them.


#10

Agreed. However, I believe the operations outlined here are both useful and expected for those coming from C++. For example, when one is doing a compare and exchange, it is usually in a loop, in which case spurious failures make no difference, and the weak variant is more performant.


#11

For the record, AArch64 supports load-link/store-conditional on 8, 16, 32, 64, and 128 bit values; ARM (32) goes up to 64; PowerPC traditionally does only 32 and 64 bit (the latter only in 64 bit mode), but newer architectures added native 8, 16, and 128 bit support.