Miscompilation: Equal pointers comparing as unequal

[JakobDegen]

I tried this code:

pub fn foo() -> (usize, usize, bool) {
    let a: *const u8;
    let b: *const u8;
    {
        let v: [u8; 16] = [std::hint::black_box(4); 16];
        a = &(v[0]);
    }
    {
        let v: [u8; 16] = [std::hint::black_box(4); 16];
        b = &(v[0]);
    }
    (a as usize, b as usize, a == b)
}

fn main() {
    println!("{:?}", foo());
}

I expected to see this happen: Either the pointers (when cast to integers) are the same and the comparison is true, or they are not the same and the comparison is false.

Instead, this happened: It printed: (140728325198984, 140728325198984, false)

Upstream LLVM issue

Meta

Reproduced via rustc +nightly -Copt-level=3 test.rs && ./test.

rustc --version --verbose:

rustc 1.69.0-nightly (5b8f28453 2023-02-12)
binary: rustc
commit-hash: 5b8f284536d00ba649ca968584bedab4820d8527
commit-date: 2023-02-12
host: x86_64-unknown-linux-gnu
release: 1.69.0-nightly
LLVM version: 15.0.7

Also reproduces on master.

@rustbot label +I-unsound +T-compiler +A-llvm

[JakobDegen]

Godbolt indicates that this is EarlyCSE in LLVM optimizing the pointer comparison to false despite the two stack allocations have non-overlapping lifetime ranges.

[zirconium-n]

This seems related to pointer provenance.

[JakobDegen]

The bug itself or the cause of the bug? I don't know what the incorrect reasoning that LLVM is using here is, so I can't comment on the cause of the issue. But both Rust and LLVM clearly define pointer comparison to be address based, which means that I don't think we need to think about provenance in order to conclude that this is a miscompilation

[DoubleHyphen]

This seems related to pointer provenance.

tl;dr even if the docs were changed to take provenance into account when comparing for equality, there would still be a miscompilation, because evaluating the same expression twice leads to different results!

fn main() {
    let a: *const u8;
    let b: *const u8;
    {
        let v: [u8; 16] = [core::hint::black_box(0); 16];
        a = &(v[0]);
    }
    {
        let v: [u8; 16] = [core::hint::black_box(0); 16];
        b = &(v[0]);
    }
    println!("{a:?} == {b:?} evaluates to {}", a==b);
    println!("{a:?} == {b:?} evaluates to {}", a==b);
}

0x7ffd8828d818 == 0x7ffd8828d818 evaluates to false
0x7ffd8828d818 == 0x7ffd8828d818 evaluates to true

Playground link

This was exactly the train of thought that led me to experiment, thereby uncovering the bug: “Can two pointers compare as equal, even when they belong to different allocations?” I experimented, figured out that they cannot, and tried to refactor my println!s, whereupon the program started behaving differently. (In the second linked program, uncommenting line 18 changes the output of line 19.)

PS: In case it matters, my experiments were on the stable channel.

[RalfJung]

tl;dr even if the docs were changed to take provenance into account when comparing for equality, there would still be a miscompilation, because evaluating the same expression twice leads to different results!

In theory they could define pointer comparison to be non-deterministic, and then this would be okay. For a comparison that involves provenance, that is probably the case.

But to my knowledge that's not how LLVM intends their ptr comparison to work.

That last example is really strange though, why would it optimize only one of them? Also I was unable to reproduce this without printing, which is equally strange...

[DoubleHyphen]

Also I was unable to reproduce this without printing, which is equally strange...

I thought that was queer, so I experimented further.

What I found is as follows:

• As long as a pointer is never printed using println!, the behaviour remains stable. a==b always evaluates to false, and even if a and b are cast to integers and compared, the comparison still returns false. In other words, the code (continued from above)

    let (a_, b_) = (a as u128, b as u128);
    dbg!(a_ == b_, a_ ^ b_);

outputs

a_ == b_ = false
a_ ^ b_ = 0

to stderr, which –to the best of my knowledge– is not exactly how integers are supposed to work.

• As soon as either pointer gets printed using println!, a==b starts evaluating to true. Casting them both to u128 before printing them does not cause that; only eg println!("{a:?}") does.

[Imberflur]

I tried some alternatives to println!, it looks like black_box(format_args!("{:?}", a)) is sufficient for it to start evaluating to true:

// Produces true on following println

black_box(format_args!("{:?}", a));
//black_box(format_args!("{:?}", b));
//format!("{:?}", a);

// Doesn't

//format_args!("{:?}", black_box(a));
//black_box(format_args!("{:?}", black_box(a)));
//format!("{:?}", black_box(a));

[RalfJung]

The wild thing is that black_box(a) doesn't cause this... so format_args is an even blacker box than black_box, or so? black_box is supposed to be a wildcard, and for all LLVM knows it might be calling format_args...

In fact looks like adding black_box actually enables the optimization?!?

[Imberflur]

Reduced to black_box(&a) (edit: here is a playground link)

[JakobDegen]

The wild thing is that black_box(a) doesn't cause this... so format_args is an even blacker box than black_box, or so? black_box is supposed to be a wildcard, and for all LLVM knows it might be calling format_args...

Yeah, this isn't all too surprising, the difference between black_box(a) and black_box(&a) is quite significant

[apiraino]

Result from my bisection points to a rollup. Out of that rollup likely #102232, I guess?

searched nightlies: from nightly-2022-01-01 to nightly-2023-02-14
regressed nightly: nightly-2022-09-29
searched commit range: 470e518...ce7f0f1
regressed commit: 837bf37

bisected with cargo-bisect-rustc v0.6.5

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --start=2022-01-01 --script script.sh 

Also - If I'm correct - this should tag more t-libs than t-compiler

@rustbot label -t-compiler +t-libs +t-libs-api

[DoubleHyphen]

Is it note-worthy that the issue can trigger without using black_box at all?

[RalfJung]

Yeah, this isn't all too surprising, the difference between black_box(a) and black_box(&a) is quite significant

How's that not surprising?^^ In terms of tings like "exposing the pointer", both should be equivalent...

Is it note-worthy that the issue can trigger without using black_box at all?

In fact even the original examples work without black-box, e.g.

fn main() {
    let a: *const u8;
    let b: *const u8;
    {
        let v: [u8; 16] = [0; 16];
        a = &(v[0]);
    }
    {
        let v: [u8; 16] = [0; 16];
        b = &(v[0]);
    }
    println!("{a:?} == {b:?} evaluates to {}", a==b);
    println!("{a:?} == {b:?} evaluates to {}", a==b);
}

[RalfJung]

Result from my bisection points to a rollup. Out of that rollup likely #102232, I guess?

That just stabilizes black_box without changing its behavior. Presumably you need to add a feature flag to continue bisecting this code further into the past?

Definitely looks like a t-compiler issue to me.

[eggyal]

Somewhat simpler, still demonstrating misbehaviour, again no black_box. Likewise with usize rather than *const types.

Edit: updated even simpler.

[DoubleHyphen]

I whipped up a quick example for the Compiler Explorer, and tried it with the 10 newest and the 10 oldest stable versions of the compiler. All of them appear to fold the comparison to xor eax eax, ie all of them arbitrarily decide it's false.

What's even more staggering is that this behaviour persists even if we use strict provenance and expose_addr. I'd been hoping that this would fix the issue, but no.

[pitaj]

Here's an example without the prints in between, using a bunch of black boxes:

https://godbolt.org/z/cKMra38a8

It appears that copying the value from either integer causes llvm to "realize" that they're actually equal. Before that it assumes they're not equal.

Edit: actually only the one black box is needed (let c = black_box(a)) the others aren't necessary to reproduce

[apiraino]

Hmm you are all right here, the black_box just confused me. And as @DoubleHyphen points out it's not even a regression, I can reproduce with any version of rustc.

@rustbot label T-compiler -T-libs -T-libs-api P-high

[RalfJung]

Yeah we know what it's triggered by: llvm/llvm-project#45725. It's a very hard to fix bug in LLVM boiling down to different parts of LLVM making contradicting assumptions about the semantics of lifetime intrinsics, fundamentally caused by never properly deciding and documenting the semantics of said intrinsics.

[DoubleHyphen]

/r/rust already managed to turn this into a segfault in safe code: https://www.reddit.com/r/rust/comments/112crfj/comment/j8ml9zh/?utm_source=reddit&utm_medium=web2x&context=3

Inlining the code to avoid indirection/loss, credits to u/duckerude:

use std::cell::RefCell;

fn main() {
    let a = {
        let v = 0u8;
        &v as *const _ as usize
    };
    let b = {
        let v = 0u8;
        &v as *const _ as usize
    };
    let i = a - b;
    let arr = [
        RefCell::new(Some(Box::new(1))),
        RefCell::new(None),
        RefCell::new(None),
    ];
    assert_ne!(i, 0);
    let r = arr[i].borrow();
    let r = r.as_ref().unwrap();
    *arr[0].borrow_mut() = None;
    println!("{}", *r);
}

Out of curiosity, I tried those two examples in the playground again, to see if the behaviour had changed from version to version.

EDIT: Both examples currently fail with Exited with signal 11 (SIGSEGV): segmentation violation, ie pretty much as previously.

Original post preserved for history:

Guess what… no segfault! But it was obviously miscompiling, since the final println! never appeared.

Just to make sure that segfaults were caught, I replaced main with

fn main() {
    unsafe { core::hint::unreachable_unchecked() }
}

and… guess what! No segfault!

…Do those functions actually not segfault, or has the playground just stopped reporting segfaults when they happen?