cc @ojeda

This could mention the atomic-maybe-uninit crate in the alternatives section (cc @taiki-e).

With some way for the language to be able to express "this type is valid for any bit pattern", which project safe transmute presumably will provide (and that exists in the ecosystem as bytemuck and zerocopy and probably others), I'm wondering if it would be better to return an AtomicPerByteRead<T>(MaybeUninit<T>) which we/the ecosystem could provide a safe into_inner (returning a T) if T is valid for any bit pattern.

This would also require removing the safe uninit method. But you could always presumably do an AtomicPerByte<MaybeUninit<T>> with no runtime cost to passing MaybeUninit::uninit() to new.

That's extra complexity, but means that with some help from the ecosystem/future stdlib work, this can be used in 100% safe code, if the data is fine with being torn.

The "uninit" part of MaybeUninit is essentially not a bit pattern though. That's the problem. Even if a value is valid "for all bit patterns", you can't unwrap uninit memory into that type.

not without the fabled and legendary Freeze Intrinsic anyway.

On the other hand, AnyBitPatternOrPointerFragment isn't a type we have, nor really a type we strictly need for this. Assuming tearing can't deinitialize initialized memory, then MaybeUninit would suffice I think?

note that LLVM already implements this operation:
llvm.memcpy.element.unordered.atomic Intrinsic
with an additional fence operation for acquire/release.

The trouble with that intrinsic is that unordered is weaker than monotonic aka Relaxed, and it can't easily be upgraded. There's no "relaxed fence" if the ordering you want is Relaxed; and even if the ordering you want is Acquire or Release, combining unordered atomic accesses with fences doesn't produce quite the same result. Fences provide additional guarantees regarding other memory accessed before/after the atomic access, but they don't do anything to restore the missing "single total order" per address of the atomic accesses themselves.

The trouble with that intrinsic is that unordered is weaker than monotonic aka Relaxed, and it can't easily be upgraded. There's no "relaxed fence" if the ordering you want is Relaxed; and even if the ordering you want is Acquire or Release, combining unordered atomic accesses with fences doesn't produce quite the same result. Fences provide additional guarantees regarding other memory accessed before/after the atomic access, but they don't do anything to restore the missing "single total order" per address of the atomic accesses themselves.

I'm very familiar with the standard Rust and C++ memory orderings, but I don't know much about llvm's unordered ordering. Could you give an example of unexpected results we might get if we were to implement AtomicPerByte<T>::{read, write} using llvm's unordered primitive and a fence? Thanks!

(It seems monotonic is behaves identically to unordered for loads and stores?)

cc @ojeda

Thanks! Cc'ing @wedsonaf since he will like it :)

Unordered is not monotonic (as in, it has no total order across all accesses), so LLVM is free to reorder loads/stores in ways it would not be allowed to with Relaxed (it behaves a lot more like a non-atomic variable in this sense)

In practical terms, in single-thread scenarios it behaves as expected, but when you load an atomic variable with unordered where the previous writer was another thread, you basically have to be prepared for it to hand you back any value previously written by that thread, due to the reordering allowed.

Concretely, I don't know how we'd implement relaxed ordering by fencing without having that fence have a cost on weakly ordered machines (e.g. without implementing it as an overly-strong acquire/release fence).

That said, I think we could add an intrinsic to LLVM that does what we want here. I just don't think it already exists.

(FWIW, another part of the issue is that this stuff is not that well specified, but it's likely described by the "plain" accesses explained in https://www.cs.tau.ac.il/~orilahav/papers/popl17.pdf)

CC @RalfJung who has stronger opinions on Unordered (and is the one who provided that link in the past).

I think we can easily implement this with relaxed in compiler-builtins though, but it should get a new intrinsic, since many platforms can implement it more efficiently.

We already have unordered atomic memcpy intrinsics in compiler-builtins. For 1, 2, 4 and 8 byte access sizes.

I'm not sure we'd want unordered, as mentioned above...

To clarify on the difference between relaxed and unordered (in terms of loads and stores), if you have

static ATOM: AtomicU8 = AtomicU8::new(0);
const O: Ordering = ???;

fn thread1() {
    ATOM.store(1, O);
    ATOM.store(2, O);
}

fn thread2() {
    let a = ATOM.load(O);
    let b = ATOM.load(O);
    assert!(a <= b);
}

thread2 will never assert if O is Relaxed, but it could if O is (the hypothetical) Unordered.

In other words, for unordered, it would be legal for 2 to be stored before 1, or for b to be loaded before a. In terms of fences, there's no fence that "upgrades" unordered to relaxed, although I believe (but am not certain) that stronger fences do apply to it.

something that could work but not be technically correct is:
compiler acquire fence
unordered atomic memcpy
compiler release fence

those fences are no-ops at runtime, but prevent the compiler from reordering the unordered atomics -- assuming your on any modern cpu (except Alpha iirc) it will behave like relaxed atomics because that's what standard load/store instructions do.

Those fences aren't always no-ops at runtime, they actually emit code on several platforms (rust-lang/rust#62256). It's also unclear what can and can't be reordered across compiler fences (rust-lang/unsafe-code-guidelines#347), certainly plain stores can in some cases (this is easy to show happening in godbolt).

Either way, my point has not been that we can't implement this. We absolutely can and it's probably even straightforward. My point is just that I don't really think those existing intrinsics help us do that.

I like MaybeAtomic, but following C++ with AtomicPerByte sounds reasonable.
The LLVM guys started something similar in 2016:
https://reviews.llvm.org/D27133

CC @RalfJung who has stronger opinions on Unordered (and is the one who provided that link in the past).

Yeah, I don't think we should expose Unordered to users in any way until we are ready and willing to have our own concurrency memory model separate from that of C++ (or until C++ has something like unordered, and it's been shown to also make sense formally). There are some formal memory models with "plain" memory accesses, which are similar to unordered (no total mo order but race conditions allowed), but I have no idea if those are an accurate model of LLVM's unordered accesses. Both serve the same goal though, so there's a high chance they are at least related: both aim to model Java's regular memory accesses.

We already have unordered atomic memcpy intrinsics in compiler-builtins. For 1, 2, 4 and 8 byte access sizes.

Well I sure hope we're not using them in any way that actually becomes observable in program behavior, as that would be unsound.

Most of the discussion so far is about the general concept and implementability of an "atomic per byte memcpy", but I'd also like some feedback on the API design itself. E.g. does the usage of MaybeUninit make sense, or should we have a separate MaybeTeared or something like that? Is it ergonomic enough, especially for slices? Etc.

It does seem kind of odd to me that unsafe code is needed to unpack the result of a byte-wise load even for types where that is actually always safe because any correctly sized stream of bytes is a valid representation.

For a caricatural example, I do not see why I should need unsafe code to load the contents of an AtomicPerByte<[u8; LENGTH]> into a &mut [u8; LENGTH], given that this operation is UB-free by definition.

In the actual use case that I have in mind (well, more exactly a client of that lib), it would be convenient to load an &[f32] byte-wise into an &mut [f32], which should be safe as well since any bag of 4 bytes is a valid f32 (though possibly a surprising one).

Basically, I second comment #3301 (comment) regarding the idea that any type that allows safe-transmute from a suitably sized stream of bytes, should be safe to load from AtomicPerByte storage. MaybeUninit does not model that guarantee well as it's designed to also handle uninitialized memory, which this abstraction cannot emit.

It does seem kind of odd to me that unsafe code is needed to unpack the result of a byte-wise load even for types where that is actually always safe because any correctly sized stream of bytes is a valid representation.

We have to be careful here, because not every stream of bytes is valid for [u8; N] -- if any of the bytes is uninitialized, that would be invalid. (So e.g. transmuting (u8, u16) to u32 or to [u8; 4] is not sound.)

However, [u8; N] has the property that mixing the bytes of any two or more valid instances, yields a valid instance. [bool; N] also has that property. But [NonZeroU32; N] does not. For the types that have that property we could offer an API that skips the MaybeUninit.

The way I read the API as proposed in the RFC text, it always goes between two instances of uses the same type. So, the transmutation questions shouldn't be an issue. If there's (u8, 16) giving you an uninit byte in there somewhere, then both the source and dest locations would have the same uninit byte position, and it remains sound.

EDIT: In other words, AtomicPerByte<(u8, 16)> can only store (u8, 16) values and load (u8, 16) values, you can't store as (u8, 16) and then load as [u8; 4], at least not as far as I can see in the API given here

You could have an enum with one variant being A((u8, 16)) and the other B([u8; 4]), a write can change the tag before setting the value, etc.

Yes, but that enum wouldn't count as "any correctly sized stream of bytes is a valid representation" to begin with.

The only types for which "any correctly sized stream of bytes is a valid representation" are MaybeUninit<T> and ZST's. Other types don't allow uninit bytes.

As I said, the property "any correctly sized stream of bytes is a valid representation" is not necessary for making this API return a T. (It is sufficient. But it is unnecessarily restrictive.) We should stop talking about it, and talk about the actually relevant property instead: mixing the bytes of multiple valid representations yields a valid representation.

Indeed (u8, u16) also has that property. But Either<(u8, u16), u32> does not.

However, [u8; N] has the property that mixing the bytes of any two or more valid instances, yields a valid instance. [bool; N] also has that property. But [NonZeroU32; N] does not. For the types that have that property we could offer an API that skips the MaybeUninit.

That could mean we should use a new MaybeTeared<T> here, instead of MaybeUninit<T>. I suppose that's slightly more accurate, but I'm not sure if it's worth adding such a type.

If any of the bytes of a value depend on other bytes, and the value gets torn at one or more random positions within the byte sequence, then you really can't do much with that torn thing. You mostly just have to reset the whole blob of bytes to some known good value.

ibraheemdev: For specific types the load granularity can be larger than a byte and we will likely want to take advantage of that, so the name AtomicPerByte might not fit well.

RalfJung: that is covered by the as-if rule. It is impossible for the program to tell if the load is truly per-byte, of if adjacent reads are merged into 2-byte reads (or larger).

thomcc: From the x86 architecture manual 3A/I 8.1.2.2:

Software should access semaphores (shared memory used for signalling between multiple processors) using identical addresses and operand lengths. For example, if one processor uses accesses a semaphore using a word access, other processors should not access the semaphore using a byte access.

RalfJung: I agree for now we should keep ruling them out, because I assume that's what C++ does -- and that should probably be explicitly documented for atomic memcpy, because that operation is much more likely to be used in unsafe type-punning code than the regular Atomic types.

P1478: Note that on standard hardware, it should be OK to actually perform the copy at larger than byte granularity. Copying multiple bytes as part of one operation is indistinguishable from running them so quickly that the intermediate state is not observed. In fact, we expect that existing assembly memcpy implementations will suffice when suffixed with the required fence.

I'm trying to wrap my head around the implications of these statements. Does this mean that:

1. it's never allowed for any atomic byte copy implementation to copy more than 1 byte in a single instruction, or
2. is (only) the internal (llvm?) implementation of atomic_{load|store}_per_byte_memcpy allowed to copy larger-than-1-byte values on targets where this is legal + it is never allowed to mix any of the Rust atomic types (not even AtomicU8) with atomic_{load|store}_per_byte_memcpy? (because from the programmer's perspective there is no way to tell which atomic granularity the internal implementation will choose).

If the second situation is the case, does this also imply that it could be UB if atomic_{load|store}_per_byte_memcpy is called from multiple threads simultaneously on overlapping memory regions with a different byte count or a different offset?

it's never allowed for any atomic byte copy implementation to copy more than 1 byte in a single instruction, or

That is definitely not the intent.

is (only) the internal (llvm?) implementation of atomic_{load|store}per_byte_memcpy allowed to copy larger-than-1-byte values on targets where this is legal + it is never allowed to mix any of the Rust atomic types (not even AtomicU8) with atomic{load|store}_per_byte_memcpy? (because from the programmer's perspective there is no way to tell which atomic granularity the internal implementation will choose).

Ah, good question. If we have two overlapping non-equal atomic-per-byte accesses we could run afoul of the x86 requirement to not mix differently-sized atomic accesses. Does C++ do anything here to prevent that?

A conforming implementation could use u32 for load and u64 for store.

That wouldn't be conforming if it causes UB on the x86 assembly level due to mixed-size concurrent accesses. (See above.)

I did't say x86, but in general this should be valid.

Well we are talking about x86 here currently, so if you mean something else you should clarify that you are not replying to the previous posts just above yours. By default people will naturally assume that you are continuing the active discussion, not throwing in an unrelated remark.

I know that the motivation for this feature is implementing seqlocks, but let me state another motivation: safe mmap.

Currently at least Linux allows modifying mapped files and reflects the modifications to program memory, even if the map is created with MAP_PRIVATE. This means that referring the mapped memory as &[u8] is clearly unsound. (Though fine, if modifications don't happen; but even if that's the intention, that's not something guaranteeable at the level of a programming language.) Accessing the memory with ptr::read_volatile or via UnsafeCell seems plausible, but while unlikely to cause problems in practice, the docs of both state that concurrent modification is UB.

I think that with the current memory model, only atomics can guarantee freedom from UB in the face of spurious modifications. (Another possibility seems to be allowing concurrent modifications with ptr::read_volatile and UnsafeCell, relaxing the memory model for accesses that are not attempting to communicate via the memory or trying to synchronize with any other accesses, but I'm not sure if that's possible or plausible.)

This API looks relevant for this use in the sense that the motivation for this mmap use case is just avoiding UB in the face of spurious modifications; and having performant accesses is also important, whereas caring about tearing is not relevant.

I recently expressed my dissatisfaction with the current situation of mmap in Reddit, and had a bunch of discussion: https://www.reddit.com/r/rust/comments/10u4anm/how_to_use_mmap_safely_in_rust/ I'm aware that many people who use mmap are either unaware of its soundness issues, or are aware of them but forced to ignore them. I don't think using AtomicPerByte to express the mmapped memory safely would necessarily fix all of those issues, but at least it would be one step in a better direction.

I would be in favor of adding atomic volatile primitives so that volatile stuff can be done concurrently. LLVM supports this we just don't support it in Rust (yet?)

afaict representing a mmap via [AtomicU8] is valid

@programmerjake Ah should have mentioned that. Yes, I think all of the current numeric atomics are valid for that use case. This would just let the user to pick a custom type, while letting AtomicPerByte wrapping to provide the (lack of) guarantees.

However, [u8; N] has the property that mixing the bytes of any two or more valid instances, yields a valid instance. [bool; N] also has that property. But [NonZeroU32; N] does not. For the types that have that property we could offer an API that skips the MaybeUninit.

That could mean we should use a new MaybeTeared<T> here, instead of MaybeUninit<T>. I suppose that's slightly more accurate, but I'm not sure if it's worth adding such a type.

After thinking about it a bit more, I'm going to try to see what this proposal looks like if we add a new MaybeTeared<T> and use that instead of using MaybeUninit<T>. I'm starting to think that might actually be better, making it clearer what the unsafety is about.

MaybeTeared<T> would be the return type of AtomicPerByte<T>::load(), representing a value of type T that might have been torn. It'd have something like an unsafe .assume_not_teared() to convert it to a T.

For certain types such as [u8; N], it's always safe to call that function (although it might not result in the expected value of course). There could be a trait for that category of types, but that's a tricky to define usefully. Would it include types like u32 or f32 for which any teared value still results in a valid value, even though it's very unlikely it'd be a meaningful value? This gets us into 'safe transmute' territories, which I think falls outside the scope of this RFC for now.

note that Teared is generally considered incorrect when referring to the past sense of tear as in to rip up.
https://en.m.wiktionary.org/wiki/teared#Verb_2
you probably want tore or torn or tearing

I just realized that atomic memcpy would probably require x86 to define what happens with mixed-size atomics: https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem/topic/mixed-size.20atomics.20and.20atomic.20memcpy/near/403111841

This question came up before but indeed has not been answered yet, I think.

I have vague memories of someone once mentioning in one of the numerous threads about this topic that they were approached by Intel engineers who claimed that this is fine on every current Intel hardware, but spec people are feeling nervous about committing to the public statement that it will stay fine on all future hardware, as they fear this could prevent future hardware optimizations.

So basically x86-TSO memory model history repeating itself: spec specifies a certain memory model, hardware actually follows a stronger memory model, software people would like to leverage useful properties of the stronger hardware memory model in their program, but hardware people first need to decide if they are ready to permanently close the door to the envisioned future hardware optimizations that led them to specify a weaker-than-necessary memory model in the first place.

Anyway, instead of trusting my faillible memory, maybe let me ping @joshtriplett in case they have more reliable memories or can in turn summon some former Intel colleague(s) to provide more authoritative material.

If the eventual conclusion is that mixed-size atomics are not fine, then it would indeed heavily constrain the implementation of the proposed atomic memcpy functionality.

On one hand, we would like implementations to use the most efficient hardware load and store operations, not juste byte loads and stores but at least native word loads and stores and ideally even SIMD loads and stores and more exotic load/stores like rep movs too, as long as the target range of memory addresses is large enough. So restricting ourselves to the moral equivalent of this...

struct AtomicMemcpyZone(Box<[AtomicU8]>);

...would be undesirable, and not an obvious improvement over the statu quo.

On the other hand, getting to the desired goal without hitting mixed-size atomics UB would mean something along the lines of the following...

• Specifying, for each target configuration, a largest memory access granularity that atomic memcpy will use (e.g. max-width SIMD load and store).
• Conceptually slicing memory into aligned blocks of this granularity.
• Stating that if two memory operations (not just memcpy, any atomic and non-atomic memory op counts) hit the same aligned block without hitting the same range of bytes within the block, and at least one of them is a memcpy, then it's instant UB for the program.

...and that would definitely be a very nasty memory model to commit to :(

Intel engineers who claimed that this is fine on every current Intel hardware

See: rust-lang/unsafe-code-guidelines#345 (comment)