Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

const-eval: load of partially initialized scalar produces entirely uninitialized result #69488

Closed
HeroicKatora opened this issue Feb 26, 2020 · 16 comments · Fixed by #94527
Closed
Labels
A-const-eval Area: Constant evaluation (MIR interpretation) C-bug Category: This is a bug. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@HeroicKatora
Copy link
Contributor

The constant evaluation of a move of a union differs from the semantics of non-constant evaluation. The union instance is not regarded as a bag-of-bits as aluded to in the reference and also this unsafe-code-guidelines issue. This occurs only if the unions has a single scalar scalar field and otherwise ZSTs, which is pretty specific but occurs for MaybeUninit if the type parameter is a scalar. If the field is of other types such as arrays ([scalar; N]) or if the other field is not a ZST then the semantics seem fine.

I tried this code:

#![feature(const_if_match)] // Only related to make_1u8_bag, all of them set by Miri
#![feature(const_fn)]
#![feature(const_mut_refs)]
#![feature(const_panic)]
#![feature(const_raw_ptr_deref)]

// Or, equivalently: `MaybeUninit`.
pub union BagOfBits<T: Copy> {
    uninit: (),
    _storage: T,
}

pub const fn make_1u8_bag<T: Copy>() -> BagOfBits<T> {
    assert!(core::mem::size_of::<T>() >= 1);
    let mut bag = BagOfBits { uninit: () };
    unsafe { (&mut bag as *mut _ as *mut u8).write(1); };
    bag
}

pub fn check_bag<T: Copy>(bag: &BagOfBits<T>) {
    let val = unsafe { (bag as *const _ as *const u8).read() };
    assert_eq!(val, 1);
}

fn main() {
    check_bag(&make_1u8_bag::<[usize; 1]>()); // Fine
    check_bag(&make_1u8_bag::<usize>()); // Fine

    const CONST_ARRAY_BAG: BagOfBits<[usize; 1]> = make_1u8_bag();
    check_bag(&CONST_ARRAY_BAG); // Fine.
    const CONST_USIZE_BAG: BagOfBits<usize> = make_1u8_bag();
    check_bag(&CONST_USIZE_BAG); // Panics
}

Playground

I expected to see this happen: All assertions succeed.

Instead, this happened: The check where a union of type BagOfBits<usize> is moved during constant evaluation, panics. When putting everything through Miri it panics with the message of trying to read an uninitialized byte. The check where the union of type BagOfBits<[usize; 1]> is used instead runs fine in both cases.

error: Miri evaluation error: attempted to read undefined bytes
  --> src/main.rs:21:5
   |
21 |     assert_eq!(val, 1);
   |     ^^^^^^^^^^^^^^^^^^^ attempted to read undefined bytes

As far as I am aware, when constant evaluation reads scalars then it propagates uninitialized bytes. If that were to happen then it would explain the observed behaviour but it seems weird why the union copy would use a scalar read.

cc @RalfJung

@HeroicKatora HeroicKatora added the C-bug Category: This is a bug. label Feb 26, 2020
@RalfJung RalfJung changed the title Move of union with scalar field deinitializes initialized bytes in constant evalution Partially initialized scalar result of const evaluation becomes entirely uninitialized Feb 26, 2020
@RalfJung
Copy link
Member

RalfJung commented Feb 26, 2020

I adjusted the title: this is not about a "move" happening during const-eval, this is specifically about taking the result of const-eval and using it elsewhere in the program. If you continue to use make_1u8_bag::<usize>() inside the same constant, you should see the behavior you expect. Could you confirm that?

@RalfJung
Copy link
Member

Cc @rust-lang/wg-const-eval and specifically @oli-obk: I think what is happening here is (again) "const-eval result normalization" going wrong. Specifically, here we decide to treat Scalar results of const-eval as immediates, and this includes BagOfBits<usize>. But that is wrong, as BagOfBits<usize> may legitimately be only partially initialized, and treating it as an immediate loses that information.

@HeroicKatora
Copy link
Contributor Author

HeroicKatora commented Feb 26, 2020

When making check_bag a const_fn and using it to define a unit constant, the constant evaluation fails/const errors as well. This is happening during evaluation and not as part of embedding the const result.

pub const fn check_bag<T: Copy>(bag: &BagOfBits<T>) {
    let val = unsafe { *(bag as *const _ as *const u8) };
    assert!(val == 1);
}

const _: () = check_bag(&make_1u8_bag::<usize>());
   Compiling playground v0.0.1 (/playground)
error: any use of this value will cause an error
  --> src/main.rs:21:13
   |
21 |     assert!(val == 1);
   |             ^^^^^^^^
   |             |
   |             attempted to read undefined bytes
   |             inside call to `check_bag::` at src/main.rs:35:19
...
35 |     const _: () = check_bag(&make_1u8_bag::());
   |     --------------------------------------------------
   |
   = note: `#[deny(const_err)]` on by default

@RalfJung
Copy link
Member

Hm... that is interesting. The same assumption ("Scalar means we can treat it as an immediate") is also being made here. Our immediates are unable to represent partially initialized values, and in this case that leads to an incorrect execution.

And indeed what I wrote above is not correct, that code contains another layer of a hack to work around mistreatment of uninitialized scalars from earlier. Layers upon layers.^^

So, the concrete bug is likely caused by try_read_immediate_from_mplace, and ideally a proper fix will also help simplify op_to_const.

@oli-obk
Copy link
Contributor

oli-obk commented Feb 26, 2020

Yea we have the same optimization for scalar immediates during const eval. Basically this means we can't trust just the Abi as a decision maker for whether to run the scalar immediate optimization or not. I'm not sure how we can make this decision sanely though. The unionness won't be visible in the layout if the type is e.g. ((), BagOfBits) I think?

Alternatively we can make the size field a defined mask field instead of a "defined bytes as per the type" value. This would increase the size of that field to u16 (since u128 has 16 bytes, and we need one bit per byte for the mask). That size increase would be fine, I'm not sure about the complexity though. Right now the field is just a sanity check that we use to assert that we didn't mess up the value somewhere along the way.

@RalfJung RalfJung changed the title Partially initialized scalar result of const evaluation becomes entirely uninitialized const-eval: load of partially initialized scalar produces entirely uninitialized result Feb 26, 2020
@oli-obk
Copy link
Contributor

oli-obk commented Feb 26, 2020

So, the concrete bug is likely caused by try_read_immediate_from_mplace, and ideally a proper fix will also help simplify op_to_const.

Oh interesting, not having to touch the logic deciding what can be an immediate, but just adding a check for full initialization should suffice. I don't see how this would allow a simplification though.

@RalfJung
Copy link
Member

Alternatively we can make the size field a defined mask field instead of a "defined bytes as per the type" value.

Wow... so then we could properly represent initializedness in intermediates. That is pretty awesome! I'd live this. But it's also non-trivial and might impact performance.
(It would still not be entirely faithful to the abstract machine as it cannot represent parts of pointers, but -- baby steps.)

Oh interesting, not having to touch the logic deciding what can be an immediate, but just adding a check for full initialization should suffice.

Yeah, something like that would be the simpler fix. However, try_read_immediate_from_mplace has some callers (I think) that rely on it always succeeding for certain types, so this might still have rippling effects.

I don't see how this would allow a simplification though.

Potentially, op_to_const could just call try_read (instead of looking at the layout itself) and only if that succeeds, do anything non-ByRef.

@RalfJung
Copy link
Member

However, try_read_immediate_from_mplace has some callers (I think) that rely on it always succeeding for certain types, so this might still have rippling effects.

More precisely, pretty much every single call of read_immediate has the risk of ICE'ing if try_read suddenly returns None for things like integers.

@RalfJung RalfJung added the A-const-eval Area: Constant evaluation (MIR interpretation) label Feb 28, 2020
@jonas-schievink jonas-schievink added the T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. label Mar 22, 2020
@RalfJung
Copy link
Member

I just thought of an alternative to adding a full initialization check that makes try_read fail for partially initialized integers. First of all, I am not even sure if that would be correct -- when loading at integer type, making the full integer uninitialized if any one byte is uninitialized might well be the desired semantics. That is the only way to preserve the idea that integers have anything to do with their mathematical counterpart, that they are a way to represent numbers in Rust. I can imagine adding a single "non-number" to the abstract domain that usize represents, but having "0x00 0xUU 0x00 0xUU" in there is making a mockery of the entire idea of Rust types describing "abstract values".

So the alternative would be to adjust this check (and possibly others) to test if the type we are working at is a "bag of bytes" or not. If it is an integer or a newtyped integer, it should be treated as a bag of bytes. If it involves a union, it should not. That would solve the issue here while still permitting an Immediate representation of all types that MIR has native operations for.

@RalfJung
Copy link
Member

RalfJung commented May 6, 2020

I am now starting to wonder if we should really fix this bug in Miri...

A function like this

pub union BagOfBits<T: Copy> {
    uninit: (),
    _storage: T,
}

pub fn foo(x: BagOfBits<usize>) {}

gets translated to LLVM IR like

; playground::foo
; Function Attrs: nonlazybind uwtable
define void @_ZN10playground3foo17h31b32b7845372f25E(i64 %x) unnamed_addr #0 !dbg !6 {
start:
  %x.dbg.spill = alloca i64, align 8
  store i64 %x, i64* %x.dbg.spill, align 8
  call void @llvm.dbg.declare(metadata i64* %x.dbg.spill, metadata !20, metadata !DIExpression()), !dbg !21
  ret void, !dbg !22
}

Note the argument type: i64. In LLVM, to my knowledge, an integers is either fully poison or not poison at all, so if we use poison as our model of uninitialized memory (which is probably the best long-term bet), then it is impossible to pass a partially initialized "bag of bits" to this function. In that sense current Miri behavior actually accurately reflects the LLVM IR we are generating.

This might change on the LLVM side -- from what I know, poison being all-or-nothing is one of the main contentious points for why the "killing undef and spreading poison" proposal has not been adopted yet -- but we certainly must tread carefully here.

@HeroicKatora
Copy link
Contributor Author

Are the LLVM semantics those which we want, considering that mem::MaybeUninit is an instance of such a union? Also const-eval is not fully consistent with the LLVM semantics. The type [T; 1] has the same llvm representation as T itself and thus MaybeUninit<[i64; 1]> is as well a i64. But in const-eval, as noted above, the union behaves like a bag-of-bits for array types and does not propagate undefined bytes to the whole value. Possibly this should be a classified as a codegen bug.

@RalfJung
Copy link
Member

RalfJung commented May 7, 2020

The type [T; 1] has the same llvm representation as T itself and thus MaybeUninit<[i64; 1]> is as well a i64.

Fair.

Are the LLVM semantics those which we want,

I think that is an open question.

The LLVM way to say "bag of 64 bits that can individually be poison" would be [i1 x 64], but LLVM optimization passes can handle that much less well than i64, so switching to this "bit vector" could lead to severe performance regressions. (I actually think we want a "bag of bytes", which would be [i8 x 8], but that may or may not be any better.)

@RalfJung
Copy link
Member

A great way to represent the desired semantics of MaybeUninit<i64> in LLVM would be with the proposed "byte" type. However, it is not clear yet if LLVM will accept this proposal.

bors bot added a commit to taiki-e/atomic-memcpy that referenced this issue Feb 13, 2022
1: Remove miri hack r=taiki-e a=taiki-e

Use currently use a hack to avoid rust-lang/rust#69488 and to make sure that Miri errors for  atomic load/store of integers containing uninitialized bytes (which is probably not a problem and uncharted territory at best [1] [2] [3], and can be detected by `-Zmiri-check-number-validity` [4]), do not mask Miri errors for the use of uninitialized bytes (which is definitely a problem).

https://github.com/taiki-e/atomic-memcpy/blob/3507fef17534e4825b2b303d04702b4678e29dd0/src/lib.rs#L426-L450

[1]: crossbeam-rs/crossbeam#315 
[2]: rust-lang/unsafe-code-guidelines#158 
[3]: rust-lang/unsafe-code-guidelines#71 
[4]: rust-lang/miri#1904 

However, this actually causes another "unsupported operation" Miri error.

```
error: unsupported operation: unable to turn pointer into raw bytes
   --> /Users/taiki/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:701:9
    |
701 |         copy_nonoverlapping(src, tmp.as_mut_ptr(), 1);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ unable to turn pointer into raw bytes
    |
    = help: this is likely not a bug in the program; it indicates that the program performed an operation that the interpreter does not support
```


Co-authored-by: Taiki Endo <te316e89@gmail.com>
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Feb 27, 2022
…oli-obk

For MIRI, cfg out the swap vectorization logic from 94212

Because of rust-lang#69488 the swap logic from rust-lang#94212 doesn't currently work in MIRI.

Copying in smaller pieces is probably much worse for its performance anyway, so it'd probably rather just use the simple path regardless.

Part of rust-lang#94371, though another PR will be needed for the CTFE aspect.

r? `@oli-obk`
cc `@RalfJung`
@RalfJung
Copy link
Member

As mentioned before, a strategy to fix this problem would be to adjust Miri such that it no longer attempts to put union values into its interpret::Scalar type. Scalar can only be wholly initialized or wholly uninitialized, and is thus not suited for types that can be partially initialized (as is the intent for MaybeUninit<_>).

In #94411 I started working on this, but recursively traversing the type is actually quite annoying, and also usually something that Miri avoids doing. It would be much better if this information was encoded in the Layout, as part of the abi::Scalar type: basically, valid_range can be "all values are valid, including uninit" or "all values are valid, excluding uninit". And it seems like that would also help with things like #93670, since we could add noundef to types that exclude uninit. Unfortunately the abi and layout is quite a bit outside my expertise, and I am not sure I will have the time to dig into this to figure this all out myself.
@erikdesjardins not sure what your plans are for noundef; do you think handling that via abi::Scalar would make sense?

@RalfJung
Copy link
Member

I am now starting to wonder if we should really fix this bug in Miri...

After thinking about this some more, and seeing bugs like #94371, we definitely need to fix something in Miri here. I opened #94428 to track the LLVM side of the problem.

bors added a commit to rust-lang-ci/rust that referenced this issue Feb 27, 2022
…i-obk

For MIRI, cfg out the swap vectorization logic from 94212

Because of rust-lang#69488 the swap logic from rust-lang#94212 doesn't currently work in MIRI.

Copying in smaller pieces is probably much worse for its performance anyway, so it'd probably rather just use the simple path regardless.

Part of rust-lang#94371, though another PR will be needed for the CTFE aspect.

r? `@oli-obk`
cc `@RalfJung`
@bors bors closed this as completed in f262ca1 Apr 5, 2022
@RalfJung
Copy link
Member

RalfJung commented Apr 5, 2022

Thank you so much for fixing this, @oli-obk. This resolves 1 of the 2 long-standing hard-to-fix ways in which Miri differs from my mental model of the actual Rust Abstract Machine.

I guess I have to fix #87184 some day now to also resolve the other one. ;)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-const-eval Area: Constant evaluation (MIR interpretation) C-bug Category: This is a bug. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
4 participants