Soundness hole in pattern matching on enums with an uninhabited variant

[strawberry-choco]

Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7a8a62d7a736d6bd54273422da29d7af

Click to see the example code from above link

#[derive(Debug)]
enum A {
    B(B),
    C(C),
    A1,
    A2,
}

#[derive(Debug)]
enum B {
    B1,
    B2,
    B3,
    B4,
    B5,
}

#[derive(Debug)]
enum C {}

fn main() {
    let a = A::B(B::B5);
    match a {
        A::B(_) => println!("success"),
        _ => println!("error: {:?}", a),
    }
}

Expected output: success

Actual output:

timeout: the monitored command dumped core
/root/entrypoint.sh: line 8:     7 Illegal instruction     timeout --signal=KILL ${timeout} "$@"

Running the above code on both Rust stable and nightly on my machine returns illegal hardware instruction (core dumped) with some number different on each run prefixing the output.

Some experimentations:

• Implementing variants for enum C solves this issue.
• Remove variants A1 and A2 solves this issue.
• Use any variant of B other than B5 works.

I assume this is a bug in the compiler?

[Mark-Simulacrum]

cc @eddyb since potentially has something to do with enum optimizations?

[Centril]

Minimized:

#![feature(never_type, core_intrinsics)]

pub enum E1 {
    V1 { f: bool },
    V2 { f: ! },
    V3,
    V4,
}

fn main() {
    match (E1::V1 { f: true }) {
        E1::V2 { .. } => unsafe { ::core::intrinsics::unreachable() },
        _ => {},
    }
}

MIR:

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
fn  main() -> () {
    let mut _0: ();                      // return place in scope 0 at src/main.rs:10:11: 10:11
    let mut _1: E1;                      // in scope 0 at src/main.rs:11:11: 11:31
    let mut _2: isize;                   // in scope 0 at src/main.rs:12:9: 12:22
    scope 1 {
    }

    bb0: {
        StorageLive(_1);                 // bb0[0]: scope 0 at src/main.rs:11:11: 11:31
        ((_1 as V1).0: bool) = const true; // bb0[1]: scope 0 at src/main.rs:11:11: 11:31
                                         // ty::Const
                                         // + ty: bool
                                         // + val: Scalar(0x01)
                                         // mir::Constant
                                         // + span: src/main.rs:11:24: 11:28
                                         // + ty: bool
                                         // + literal: Const { ty: bool, val: Scalar(0x01) }
        discriminant(_1) = 0;            // bb0[2]: scope 0 at src/main.rs:11:11: 11:31
        _2 = discriminant(_1);           // bb0[3]: scope 0 at src/main.rs:12:9: 12:22
        switchInt(move _2) -> [1isize: bb1, otherwise: bb2]; // bb0[4]: scope 0 at src/main.rs:12:9: 12:22
    }

    bb1: {
        const std::intrinsics::unreachable(); // bb1[0]: scope 1 at src/main.rs:12:35: 12:68
                                         // ty::Const
                                         // + ty: unsafe extern "rust-intrinsic" fn() -> ! {std::intrinsics::unreachable}
                                         // + val: Scalar(<ZST>)
                                         // mir::Constant
                                         // + span: src/main.rs:12:35: 12:66
                                         // + ty: unsafe extern "rust-intrinsic" fn() -> ! {std::intrinsics::unreachable}
                                         // + literal: Const { ty: unsafe extern "rust-intrinsic" fn() -> ! {std::intrinsics::unreachable}, val: Scalar(<ZST>) }
    }

    bb2: {
        StorageDead(_1);                 // bb2[0]: scope 0 at src/main.rs:15:1: 15:2
        return;                          // bb2[1]: scope 0 at src/main.rs:15:2: 15:2
    }
}

Debug ASM (does not reproduce with release profile):

```asm std::rt::lang_start: # @std::rt::lang_start # %bb.0: subq $56, %rsp leaq .L__unnamed_1(%rip), %rax movq %rdi, 24(%rsp) movq %rsi, 32(%rsp) movq %rdx, 40(%rsp) movq 24(%rsp), %rdx movq %rdx, 48(%rsp) leaq 48(%rsp), %rdx movq 32(%rsp), %rsi movq 40(%rsp), %rcx movq %rdx, %rdi movq %rsi, 16(%rsp) # 8-byte Spill movq %rax, %rsi movq 16(%rsp), %rdx # 8-byte Reload callq *std::rt::lang_start_internal@GOTPCREL(%rip) movq %rax, 8(%rsp) # 8-byte Spill # %bb.1: movq 8(%rsp), %rax # 8-byte Reload addq $56, %rsp retq # -- End function

std::rt::lang_start::{{closure}}: # @"std::rt::lang_start::{{closure}}"

%bb.0:

subq	$24, %rsp
movq	%rdi, 16(%rsp)
movq	16(%rsp), %rdi
callq	*(%rdi)

%bb.1:

callq	<() as std::process::Termination>::report
movl	%eax, 12(%rsp)          # 4-byte Spill

%bb.2:

movl	12(%rsp), %eax          # 4-byte Reload
addq	$24, %rsp
retq
                                    # -- End function

std::sys::unix::process::process_common::ExitCode::as_i32: # @std::sys::unix::process::process_common::ExitCode::as_i32

%bb.0:

pushq	%rax
movq	%rdi, (%rsp)
movq	(%rsp), %rdi
movzbl	(%rdi), %eax
popq	%rcx
retq
                                    # -- End function

core::ops::function::FnOnce::call_once{{vtable.shim}}: # @"core::ops::function::FnOnce::call_once{{vtable.shim}}"

%bb.0:

subq	$24, %rsp
movq	%rdi, 8(%rsp)
movq	8(%rsp), %rdi
movq	(%rdi), %rdi
callq	core::ops::function::FnOnce::call_once
movl	%eax, 4(%rsp)           # 4-byte Spill

%bb.1:

movl	4(%rsp), %eax           # 4-byte Reload
addq	$24, %rsp
retq
                                    # -- End function

core::ops::function::FnOnce::call_once: # @core::ops::function::FnOnce::call_once

%bb.0:

subq	$40, %rsp
movq	%rdi, 8(%rsp)
leaq	8(%rsp), %rdi
callq	std::rt::lang_start::{{closure}}
movl	%eax, 4(%rsp)           # 4-byte Spill
jmp	.LBB4_1

.LBB4_1:
jmp .LBB4_2

.LBB4_2:
movl 4(%rsp), %eax # 4-byte Reload
addq $40, %rsp
retq

.LBB4_3:
jmp .LBB4_4

.LBB4_4:
movq 24(%rsp), %rdi
callq _Unwind_Resume@PLT
ud2
movl %edx, %ecx
movq %rax, 24(%rsp)
movl %ecx, 32(%rsp)
jmp .LBB4_3
# -- End function

core::ptr::real_drop_in_place: # @core::ptr::real_drop_in_place

%bb.0:

pushq	%rax
movq	%rdi, (%rsp)
popq	%rax
retq
                                    # -- End function

<() as std::process::Termination>::report: # @"<() as std::process::Termination>::report"

%bb.0:

subq	$24, %rsp
xorl	%edi, %edi
callq	<std::process::ExitCode as std::process::Termination>::report
movl	%eax, 12(%rsp)          # 4-byte Spill

%bb.1:

movl	12(%rsp), %eax          # 4-byte Reload
addq	$24, %rsp
retq
                                    # -- End function

<std::process::ExitCode as std::process::Termination>::report: # @"<std::process::ExitCode as std::process::Termination>::report"

%bb.0:

pushq	%rax
movb	%dil, %al
movb	%al, 7(%rsp)
leaq	7(%rsp), %rdi
#DEBUG_VALUE: report:self <- [$rdi+0]
callq	std::sys::unix::process::process_common::ExitCode::as_i32
movl	%eax, (%rsp)            # 4-byte Spill

%bb.1:

movl	(%rsp), %eax            # 4-byte Reload
popq	%rcx
retq
                                    # -- End function

playground::main: # @playground::main

%bb.0:

subq	$1, %rsp
xorl	%eax, %eax
movl	%eax, %ecx
movb	$1, (%rsp)
movb	(%rsp), %dl
subb	$0, %dl
movzbl	%dl, %eax
movl	%eax, %esi
cmpb	$3, %dl
cmovbeq	%rsi, %rcx
cmpq	$1, %rcx
jne	.LBB8_2

%bb.1:

ud2

.LBB8_2:
addq $1, %rsp
retq
# -- End function

main: # @main

%bb.0:

subq	$24, %rsp
movb	__rustc_debug_gdb_scripts_section__(%rip), %al
movslq	%edi, %rcx
leaq	playground::main(%rip), %rdi
movq	%rsi, 16(%rsp)          # 8-byte Spill
movq	%rcx, %rsi
movq	16(%rsp), %rdx          # 8-byte Reload
movb	%al, 15(%rsp)           # 1-byte Spill
callq	std::rt::lang_start
movl	%eax, %r8d
movl	%r8d, %eax
addq	$24, %rsp
retq
                                    # -- End function

.L__unnamed_1:
.quad core::ptr::real_drop_in_place
.quad 8 # 0x8
.quad 8 # 0x8
.quad std::rt::lang_start::{{closure}}
.quad std::rt::lang_start::{{closure}}
.quad core::ops::function::FnOnce::call_once{{vtable.shim}}

rustc_debug_gdb_scripts_section:
.asciz "\001gdb_load_rust_pretty_printers.py"
# DW_AT_GNU_pubnames
# DW_AT_main_subprogram

</details>

[jonas-schievink]

Regression between 1.23.0 and 1.24.0

[Centril]

This seems like a rather serious soundness hole that I would suggest treating as P-high.

cc @rust-lang/compiler

[nagisa]

Given

#![feature(never_type, core_intrinsics)]
extern crate core;

pub enum E1 {
    V1 { f: bool },
    V2 { f: ! },
    V3,
    V4,
}

fn main() {
    match (E1::V1 { f: true }) {
        E1::V2 { .. } => unsafe { ::core::intrinsics::unreachable() },
        _ => {},
    }
}

LLVM for the interesting code is:

; test::main
; Function Attrs: nonlazybind uwtable
define internal void @_ZN4test4main17h4c216eb98fecdd36E() unnamed_addr #0 {
start:
  %_1 = alloca i8, align 1
  store i8 1, i8* %_1, align 1
  %0 = load i8, i8* %_1, align 1, !range !3    ; %0 = 1
  %1 = sub i8 %0, 0                            ; %1 = 1
  %2 = icmp ule i8 %1, 3                       ; %2 = 1 <= 3 = 1
  %3 = zext i8 %1 to i64                       ; %3 = 1
  %4 = select i1 %2, i64 %3, i64 0             ; %4 = 0
  %5 = icmp eq i64 %4, 1                       ; %5 = 0
  br i1 %5, label %bb1, label %bb2             ; -> bb1

bb1:                                              ; preds = %start
  unreachable

bb2:                                              ; preds = %start
  ret void
}

!3 = !{i8 0, i8 4}

[nagisa]

This is probably not A-LLVM because the generated LLVM IR is already wrong.

[RalfJung]

MIR still looks okay to me, so this seems like a MIR -> LLVM-IR translation bug.

[eddyb]

Much better, thanks!

So %2 = icmp ule i8 %1, 3 is, I believe, the check for the "dataful variant", since it's used to select discriminant 0 (E1::V1) when false. But it's true because the condition is all wrong.
I suspect the comparison was originally designed with "zero is a niche" in mind, but in this case, the available niche values are 2..=255_u8 (from the bool), so it should be checking >= 2 not <= 3.

Alternatively, sub i8 %0, 0 should be "rebasing" the the integers in memory to the enum discriminants, which would require subtracting 1, not 0, so maybe it's "just" an off-by-one?

EDIT: yeah the subtraction should be with 1, niche_variants should be 1..=3:

rust/src/librustc_codegen_ssa/mir/place.rs

Lines 265 to 266 in 1cbd8a4

	let delta = niche_start.wrapping_sub(niche_variants.start().as_u32() as u128);
	let lldiscr = bx.sub(lldiscr, bx.cx().const_uint_big(niche_llty, delta));

[hellow554]

"More minimized" without match and unstable features:

pub enum Infallable {}

pub enum E1 {
    V1 { f: bool },
    V2 { f: Infallable },
    V3,
    V4,
}

fn main() {
    if let E1::V2 { .. } = (E1::V1 { f: true }) {
        unsafe { std::hint::unreachable_unchecked(); }
    }
}

Interesting enough: When one removes the V4 in the enum, the MIR code is still the very same, but it does not print the line.
The LLVM-IR changes from

; playground::main
; Function Attrs: norecurse noreturn nounwind nonlazybind readnone uwtable
define internal void @_ZN10playground4main17h13d813b46f0ec3d7E() unnamed_addr #2 {
start:
  unreachable
}

to

; playground::main
; Function Attrs: norecurse nounwind nonlazybind readnone uwtable
define internal void @_ZN10playground4main17h13d813b46f0ec3d7E() unnamed_addr #1 {
start:
  ret void
}

(noreturn and ret void vs unreachable).

[pnkfelix]

triage: P-high. Leaving nominated and unassigned for now.

[oli-obk]

I compared what miri does (which doesn't fail) against what codegen does. The relevant difference is

rust/src/librustc_mir/interpret/operand.rs

Line 652 in 38cd948

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

vs

rust/src/librustc_codegen_ssa/mir/place.rs

Line 269 in 38cd948

let select_arg = bx.icmp(IntPredicate::IntULE, lldiscr, lldiscr_max);

where the latter (codegen) does not check whether niche_variants.start() <= adjusted_discr.

Other than that, both code paths are equivalent

Interesting enough: When one removes the V4 in the enum, the MIR code is still the very same, but it does not print the line.

I'd guess that's just a result from other niche optimizations kicking in for the enum without V4.

[eddyb]

I think I've figured out what's wrong here, why this wasn't triggered more often, and why V4 is needed.

What we have is an enum, with 4 variants:

• V1 contains the bool (which uses 0 and 1, so niche_start will be 2)
• V2 is excluded because it's uninhabited
• V3 and V4 are the niche_variants

I was confused because initially I thought V2 would be included and therefore niche_variants.start() would be 1 - but no, it's 2! So the codegen of the isub instruction is correct, delta should be 0.

The reason this hasn't caused many problems in the past is that niche_variants.start() has always been 1 (if the dataful variant is the first one) or 0 (otherwise), if no variant is uninhabited.

Currently, the check is:

discr - niche_start + niche_variants.start() <= niche_variants.end()

But the correct one-comparison trick, which I meant to use, would be:

discr - niche_start <= niche_variants.end() - niche_variants.start()

That is, you have to rely on rebasing the lowest value in the range to 0, for this to work.

What miri does is less efficient, but that's fine, as it's an interpreter. For codegen we want something simple.

[RalfJung]

What miri does is less efficient, but that's fine, as it's an interpreter. For codegen we want something simple.

What Miri does is correct though? Including considering both variants_start and variants_end as inclusive bounds?

[eddyb]

@RalfJung a <= x && x <= b is equivalent to x - a <= b - a (assuming unsigned integers).
This is because everything in a..=b will be shifted over to 0..=b-a and a <= x becomes 0 <= x - a.

And it would've worked, too, if I hadn't combined a different operation into it, ruining the trick.

Oh and miri should probably be using .contains(...) on a range, ideally the one from the layout.

[RalfJung]

@eddyb

Oh and miri should probably be using .contains(...) on a range, ideally the one from the layout.

I tried, it doesn't really make things nicer and I am not even sure if moving the assertions around is correct: RalfJung@279adf8. Probably it's not.

The adjusted_discr actually is raw_discr - niche_start + variants_start, so comparing that with variants_start again is anyway a bit funny.

EDIT: Also that arithmetic is done at type u128, is that even correct?

[eddyb]

@RalfJung Hmm, the arithmetic probably needs to be done on the size of the discriminant, like here:

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)

Double-casting assertions can, and probably should, be replaced nowadays by .try_into().unwrap().
Otherwise, your changes are in the right direction, IMO.

[RalfJung]

Otherwise, your changes are in the right direction, IMO.

I am not so convinced... seems like the VariantIdx is a u32, but the discriminant may be way bigger, so probably casting things down before we know that it is in the "niche range" is wrong?

This avoids casting too early, but it's not really any safer than what we do right now: RalfJung@f311c4e84d

[pnkfelix]

triage: assigning to @eddyb

[eddyb]

Regression between 1.23.0 and 1.24.0

I was going to argue that the bug is older, but 1.23 was early 2018, and the bug was introduced late 2017, as the code in question has been wrong in the same way since #45225.
So yeah, a 2-year-old regression-from-stable-to-stable codegen bug.

[pnkfelix]

noted that issue appears under control at T-compiler meeting, and deliberately skipped discussion of it. Removing nomination label.