Miri/CTFE discriminant computation happens at the wrong type

[RalfJung]

When loading discriminants of an enum that uses niche optimizations, Miri/CTFE has to do some arithmetic:

rust/src/librustc_mir/interpret/operand.rs

Lines 645 to 646 in bdd4bda

	let adjusted_discr = raw_discr.wrapping_sub(niche_start)
	.wrapping_add(variants_start);

Currently, this happens on type u128. That's probably wrong, it should happen on the type of the discriminant. That will result in different overflow behavior.

It's just addition and subtraction, so signed vs unsigned does not matter and we could just mask off the "too high" bits after each operation, as in:

rust/src/librustc_target/abi/mod.rs

Lines 664 to 669 in bdd4bda

	let mask = !0u128 >> (128 - bits);
	let start = *self.valid_range.start();
	let end = *self.valid_range.end();
	assert_eq!(start, start & mask);
	assert_eq!(end, end & mask);
	start..(end.wrapping_add(1) & mask)

However, it might be more elegant to use our binary_*op methods in operator.rs.

Cc @oli-obk @eddyb

[RalfJung]

@eddyb it would be nice to have some code that actually hits this incorrect overflow behavior, but I don't know enough about niches to massage the involved values into the right place. Could you help with that?

[Centril]

cc #61696

[eddyb]

@RalfJung You would start by using a small type, such as u8 or i8, to make it easier to work with.
variants_start tends to be 0 or 1 anyway, so the value you want to control is niche_start.

Let's say you'll use Option<Enum>: you need Enum to have some invalid values, which when subtracted from a small u128, result in a very large u128.

Come to think of it, wouldn't even None::<bool> result in a very large u128?

---

Well, no, I'm wrong, there's this condition for "is this a niche (i.e. non-dataful) variant":

rust/src/librustc_mir/interpret/operand.rs

Line 647 in bdd4bda

if variants_start <= adjusted_discr && adjusted_discr <= variants_end {

Because all we're missing is a mask, we can only have more bits set, not less, which implies that the value can be larger than the correct one, not smaller.

Given that the condition checks whether our value (adjusted_discr) is in a range, the most likely way we can break this is if we get the condition to be false when it should've been true.
In other words, hit the else case ("dataful", like Some) instead of the "then" one (like None).

You can't literally use Option as the optimized outer enum, as then raw_discr == niche_start, and so the subtraction ends in simply 0 for None, and if it's Some it's going to the else case anyway.

---

Really, you need to cause one of the non-dataful variants to have raw_discr < niche_start, i.e. the invalid values need to "wrap around", which we can do by leaving some "on both sides of 0":

#[repr(u8)]
enum WithWraparoundInvalidValues {
    X = 1,
    Y = 254,
}

The valid_range of that will be 1..=254, leaving only 255 and 0 (in that order) as invalid values.
We can then add an enum with 2 variants that will use each of the invalid values:

enum Foo {
    A,
    B,
    C(WithWraparoundInvalidValues),
}

fn main() {
    let x = Foo::B;
    if let Foo::C(_) = x {
        panic!();
    }
}

That trips an assert_eq! within miri! It's presumably related, but it does't even get to my panic!().

assertion failed: `(left == right)`
  left: `0`,
 right: `256`: Unsigned value 0x100 does not fit in 8 bits', src/librustc/mir/interpret/value.rs:290:9

[RalfJung]

Nice, thanks @eddyb <3

Now we got a test case for this issue. :)

[RalfJung]

I tried to fix this by using machine arithmetic instead of host arithmetic, and found something odd: For types like Option<unsafe extern "C" fn(*mut u8)>, the discriminant has pointer type! Specifically, it has type *mut (). @eddyb why is that? I was certain the discriminant would be an integer type, because clearly it is used as an integer.

(I am referring to the type and layout returned by layout.field using the discr_index from Variants::Multiple.)

[RalfJung]

Looks like Niche::reserve returns the Scalar part of the layout directly from the niche type. Would it make sense to normalize that to always be an integer type, to permit arithmetic?

[eddyb]

@RalfJung Oh, right, we even have to special-case that for LLVM, if it's non-integer you can't have a range, but only one niche value (which will be 0 for pointers).

Keep in mind that Option<fn()> must have a Scalar(Pointer) ABI, so the discriminant being an integer would mean that it needs to behave as a "castful" newtype, likely adding complexity elsewhere.

[RalfJung]

@eddyb what is a "castful" newtype? All I ask is that layout.field for the discriminant always returns a Scalar that is some integer. What would go wrong with that?

For Option<String>, the discriminant also obviously does not have the same layout as the entire enum. So I don't see any problem with Option<fn()> being a Scalar(Pointer) and its discriminant being a pointer-sized integer. But I also don't know any of the context.

[eddyb]

The problem is that scalar newtypes of scalars usually have the same type of scalar, so no cast is required, AFAIK this would be the first one.

Probably the closest thing right now is Option<bool> which is represented in LLVM as i8 (both the whole type and also its discriminant field) while bool is represented as i1, so we have to zero-extend/truncate to go between the two.

I guess right now we still do discriminant operations through memory (ugh), so it wouldn't hurt too much. But I suspect LLVM optimizations might suffer, as the same memory location would now be accessed as both a pointer and an integer, and I don't think LLVM will change it back to a pointer.

Then again, maybe the final result is indistinguishable between integers and pointers?

And we would need to treat the discriminant as an integer anyway if we wanted to support e.g. floats.

---

I'll go try it and submit a PR if it's overall a cleanup and doesn't need special cases.

[RalfJung]

I'll go try it and submit a PR if it's overall a cleanup and doesn't need special cases.

Thanks! <3
Please Cc me.

[RalfJung]

Actually, the backtrace in @eddyb's testcase is from write_discriminant_index, not from the reading side:

  10: rustc::mir::interpret::value::Scalar<Tag>::from_uint
             at ./<::std::macros::panic macros>:8
  11: rustc_mir::interpret::place::<impl rustc_mir::interpret::eval_context::InterpCx<M>>::write_discriminant_index
             at /rustc/ad7c55e1fc55d9af4787b285cec1c64e3480ae84/src/librustc_mir/interpret/place.rs:1038
  12: rustc_mir::interpret::step::<impl rustc_mir::interpret::eval_context::InterpCx<M>>::statement
             at /rustc/ad7c55e1fc55d9af4787b285cec1c64e3480ae84/src/librustc_mir/interpret/step.rs:92

There's also some arithmetic there, obviously.

[eddyb]

Yeah, I said "It's presumably related, but it does't even get to my panic!()."
I expect if you fix that one, it will trigger the panic!() (which should never happen).

[RalfJung]

Well I fixed the read-side first, so I won't be able to tell. ;)