AtomicCell accessing uninitialized memory

[CeleritasCelery]

Run the follow code sample with cargo +nightly miri run

use crossbeam_utils::atomic::AtomicCell;

#[allow(dead_code)]
#[repr(align(8))]
#[derive(Copy, Clone, Debug)]
enum Test {
    Field(u32),
    FieldLess,
}

fn main() {
    assert!(AtomicCell::<Test>::is_lock_free());
    let x = AtomicCell::new(Test::FieldLess);
    println!("{:?}", x.load());
}

I see the following error from Miri

error: Undefined Behavior: type validation failed at .value.<enum-tag>: encountered uninitialized bytes, but expected a valid enum tag
note: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior

I think the root of this issue is that AtomicCell is trying to do a transmute_copy on the None value, but the upper bits are uninitialized, therefore AtomicCell is reading uninitialized data.

crossbeam-utils = "0.8.5"
cargo 1.56.0-nightly (cc17afbb0 2021-08-02)

[taiki-e]

This seems an instance of rust-lang/unsafe-code-guidelines#69?

I don't know if there is a way to fix this issue other than to restrict the types that can be used in AtomicCell using something like unsafe marker traits.

[taiki-e]

cc @RalfJung @jeehoonkang @Amanieu

[RalfJung]

This seems an instance of rust-lang/unsafe-code-guidelines#69?

Well, having uninitialized tags violates Rust's UB rules: enum values must have valid discriminants.

It seems like the AtomicCell implementation should be using MaybeUninit somewhere, to properly express that it is dealing with potentially uninit data.

transmute_copy of uninit bytes is totally fine as long as it is done with a type that can handle uninit bytes, i.e., MaybeUninit.

I don't know if there is a way to fix this issue other than to restrict the types that can be used in AtomicCell using something like unsafe marker traits.

No; working with uninit data requires MaybeUninit. This bug likely affects almost all types, Miri is just currently not very strict about enforcing that integers are properly initialized.

[adamreichold]

enum values must have valid discriminants.

But isn't the discriminant valid in the above example? My understanding is that the rest of the enum is uninitialized (because writing Test::FieldLess only writes the discriminant) and AtomicCell::<T> always reads the full size_of::<T>() bytes.

[RalfJung]

But isn't the discriminant valid in the above example?

Yes, and a transmute_copy of that data at type Test would be fine. But AtomicCell evidently does something more interesting.

AtomicCell:: always reads the full size_of::() bytes.

let x = Test::FieldLess; let y = x also copies all the bytes, and that is okay since the discriminant is valid. AtomicCell is copying some bytes at the wrong type somewhere, it seems.

[RalfJung]

I assume this is the relevant transmute_copy?

crossbeam/crossbeam-utils/src/atomic/atomic_cell.rs

Line 789 in 2653a6c

mem::transmute_copy(&a.load(Ordering::Acquire))

Unfortunately all the types are inferred here so I am not sure at which type this is invoked.

But it just occurred to me that this might be an instance of rust-lang/rust#69488. AtomicCell will load the entire 8-byte data at type u64, and it is not legal to load (partially) uninitialized data at type u64. Miri currently does not complain in this case (rust-lang/miri#1904 will implement a flag for Miri to detect this), but the way Miri works means that the uninitializedness is 'amplified' -- basically, if any of the 8 bytes in memory is uninit, then the entire integer is "poisoned". So this is related to rust-lang/unsafe-code-guidelines#71.

The proper fix is to do the (atomic) load at type MaybeUninit<u64> instead of u64, but there is no way to do that in Rust...

[CeleritasCelery]

The proper fix is to do the (atomic) load at type MaybeUninit instead of u64, but there is no way to do that in Rust...

so is it not possible to implement a sound AtomicCell like type in Rust?

[RalfJung]

AtomicCell goes beyond what is soundly possible in Rust in multiple ways -- besides this issue, also see #315. Furthermore, it uses an SeqLock, which cannot be soundly implemented in C/C++/Rust (see e.g. this article).

[taiki-e]

Minimized:

#[allow(dead_code)]
#[repr(align(8))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Test {
    Field(u32),
    FieldLess,
}

fn main() {
    unsafe {
        let v = Test::FieldLess;
        let v = std::mem::transmute::<_, u64>(v);
        let _v = std::mem::transmute::<_, Test>(v); // error: Undefined Behavior: type validation failed at .<enum-tag>: encountered uninitialized bytes, but expected a valid enum tag
    }
}

playground

And using [u64; 1] instead of u64 will fix the error.

          let v = Test::FieldLess;
-         let v = std::mem::transmute::<_, u64>(v);
+         let v = std::mem::transmute::<_, [u64; 1]>(v);
          let _v = std::mem::transmute::<_, Test>(v);

playground

I agree that this appears to be an instance of rust-lang/rust#69488.

[RalfJung]

And using [u64; 1] instead of u64 will fix the error.

Ah, that is an interesting work-around -- looks like single-element arrays get a different ABI than their element type, so they are not treated as scalars any more.

That said, this more of a Miri quirk than a proper fix. MaybeUninit<u64> is the more adequate type to use -- or, in combination with the Miri quirk, possibly [MaybeUninit<u64>; 1].

[taiki-e]

Furthermore, it uses an SeqLock, which cannot be soundly implemented in C/C++/Rust (see e.g. this article)

Btw, I implemented a C++ proposal p1478r1 to fix SeqLock's problem (repository: atomic-memcpy), but I had the same problem with padding that this issue encountered.

[RalfJung]

Btw, there is another way to trigger the same problem, which maybe shows a bit clearly what happens:

use crossbeam_utils::atomic::AtomicCell;

#[derive(Copy, Clone, Debug)]
#[repr(align(4))]
struct Test(u8, u16);

fn main() {
    assert!(AtomicCell::<Test>::is_lock_free());
    let x = AtomicCell::new(Test(1, 2));
    println!("{:?}", x.load());
}

Test has a padding byte, which is uninitialized, so AtomicCell internally using i32 to represent a Test does not work.