Miscompilation when using wrapping_sub/wrapping_add on pointer.

[steffahn]

Relevant comment on IRLO. The following code leads to illegal instruction in release mode. (It works fine, printing 42 in debug mode.)

pub unsafe fn foo(x: *const i8) -> i8 {
    *x.wrapping_sub(x as _).wrapping_add(x as _)
}

fn main() {
    let x = 42;
    println!("{}", unsafe {foo(&x)});
}

Apparently, leaving the object x with a wrapping_sup, then going back into the object with wrapping_add and dereferencing the resulting pointer is supposed to be safe (although there is still an open issue (#80306) about properly documenting that this is safe).

As discussed in the linked IRLO thread, what’s probably happening here is that LLVM realizes that the first x.wrapping_sub(x as _) evaluates to the null pointer, and then considers the code equivalent to something like *std::ptr::null().wrapping_add(x as _) which is then detected as UB (dereferencing some integer offset of the null pointer), hence the illegal instruction.

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished release [optimized] target(s) in 1.03s
     Running `target/release/playground`
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     7 Illegal instruction     timeout --signal=KILL ${timeout} "$@"

[steffahn]

Here’s a similar miscompilation, using only safe Rust code
(admitted, I was playing around with this until I got some safe code to miscompile, I’m not entirely sure anymore as to why exactly this particular example gets turned into UB by the optimizer)

pub fn ptr(x: *const i8) -> *const i8 {
    x.wrapping_offset(-(x as isize)).wrapping_offset(x as isize)
}
pub fn zero(x: *const i8) -> isize {
    (ptr(x) as isize).wrapping_add(-(x as isize))
}
pub fn qux(x: &[i8]) -> i8 {
    x[zero(x.as_ptr()) as usize]
}

fn main() {
    let z = vec![42, 43];
    println!("{}", qux(&z));
}

(playground)

   Compiling playground v0.0.1 (/playground)
    Finished release [optimized] target(s) in 0.60s
     Running `target/release/playground`
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     7 Illegal instruction     timeout --signal=KILL ${timeout} "$@"

@rustbot modify labels: C-bug, T-compiler
@rustbot prioritize

[LeSeulArtichaut]

After a bit of godbolt testing, this seems to happen since 1.16.0, when ptr_wrapping_offset was stabilized

[nikic]

Reduced: https://llvm.godbolt.org/z/qec9oz

[nikic]

LLVM bug report: https://bugs.llvm.org/show_bug.cgi?id=48577

[steffahn]

Simplified the vec example:

pub fn zero(x: usize) -> usize {
    std::ptr::null::<i8>().wrapping_add(x) as usize - x
}
pub fn qux(x: &[i8]) -> i8 {
    x[zero(x.as_ptr() as usize)]
}

fn main() {
    let z = vec![42, 43];
    println!("{}", qux(&z));
}

[apiraino]

Assigning P-critical as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

[nagisa]

As per documentation of wrapping_sub and wrapping_add the expectation is that provenance of the pointers is retained, so the wrapping_sub setting the provenance of the resulting pointer to something else (to that of the null pointer in this case) than the provenance of the original pointer seems like the bug here.

Given that reasoning the fix that has landed (llvm/llvm-project@899faa5) to LLVM smells like it could be partial and we might still be prone to the same issue if it happens through some other contrived sample code?

We could potentially work-around this in Rust as well by implementing these wrapping operations in a way that discards provenance entirely for now (probably via ptrtoint -> op -> inttoptr)?

[RalfJung]

As per documentation of wrapping_sub and wrapping_add the expectation is that provenance of the pointers is retained, so the wrapping_sub setting the provenance of the resulting pointer to something else (to that of the null pointer in this case) than the provenance of the original pointer seems like the bug here.

Agreed.

We could potentially work-around this in Rust as well by implementing these wrapping operations in a way that discards provenance entirely for now (probably via ptrtoint -> op -> inttoptr)?

AFAIK, the entire reason that wrapping_* exist is to not have to do that.

[nagisa]

AFAIK, the entire reason that wrapping_* exist is to not have to do that.

Well, temporarily work around. I suspect fixing the issue at the root in LLVM might take some time.

[Aaron1011]

Note that llvm/llvm-project@899faa5 was reverted in llvm/llvm-project@ef2f843: the underlying issue is tracked at https://bugs.llvm.org/show_bug.cgi?id=44403

[nikic]

This was later fixed by https://reviews.llvm.org/D93820.

[RalfJung]

So can we cherry-pick that into the rustc LLVM fork, or what is the usual process?

[nagisa]

I believe this is resolved by the bump to LLVM 12.

[nagisa]

Reopening this as it does not appear to be fixed yet :(

[nagisa]

https://reviews.llvm.org/rG2ad1f5eb1a47275593bd9baf75dcf3e9c3977473 is the last changeset that is necessary to resolve this fully. Given that promotion to LLVM12 happened fairly recently, we may want to backport the commit.

[RalfJung]

Hm, but that optimization doesn't sound wrong, it just sounds bad. Some other actually wrong optimization would be needed to turn this into a miscompilation.

[nagisa]

Well, it effectively manifests a constant null pointer, much like the instsimplify fixed by nikic. null always has its own provenance, so this optimisation is only "correct" in absence of intermediate null pointers. In this specific example such a null pointer does manifest itself:

; code corresponds to `x.wrapping_sub(x as usize)`
define i8* @initial(i8* %b) {
  %b_ptr = ptrtoint i8* %b to i64
  %sub = sub i64 0, %b_ptr
  %gep = getelementptr i8, i8* %b, i64 %sub
  ret i8* %gep
}

define i8* @step1(i8* %b) {        ; no provenances remain in this function, ptrtoint discards that information
  %b_ptr = ptrtoint i8* %b to i64
  %1 = ptrtoint i8* %b to i64
  %2 = sub i64 %1, %b_ptr          ; constant 0
  %gep = inttoptr i64 %2 to i8*    ; becomes a constant `null` pointer, with a provenance of null object
  ret i8* %gep
}

To complete the original reproducer we then have these two instructions:

  %wrapping_add = getelementptr i8, i8* null, i64 %b_ptr
  %deref = load i8, i8* %wrapping_add, align 1

; becomes=>

  %deref = i8 undef ; because we're dereferencing a pointer with a provenance of a null object.

So I guess if we call anything else wrong, its probably going to be inttoptr 0 => null.

[RalfJung]

Ah... that is interesting. It sounds potentially problematic. Usually, when I start with a pointer x, if I cast it to an integer and back, that pointer should have a provenance that allows "at least as much" as the original. It should always be correct to add an integer roundtrip. That is the one thing one can rely on with ptr-int-casts, or so I thought.

What you are saying is that if the pointer has physical address 0, then this is not true.

[nikic]

This is fixed on nightly by the LLVM 13 upgrade. Probably worth adding a test for this.

[nikic]

Dropping priority as the issue is fixed.