LLVM assumes that unused allocations always succeed, leading to violated invariants

View all comments

See rust-lang/unsafe-code-guidelines#328

LLVM assumes that calls to the global allocator (and local variable cration) do not fail when trying to optimize away unused allocations. This results in calls that are always going to fail (because they together exceed the address space) being able to observably violate invariants of rust types, for example by making &muts provably overlap.

Note that this is extremely contrived. Maybe someone can come up with an example that shows this better by more "directly" demonstrating hypothetically overlapping allocations? Also note that using any of the allocations in a way that is not optimized away causes the call to alloc to reappear alongside its null checks.

The example demonstrates this on 32 bit because LLVM's max allocation size is 1 << 61 bytes. It can be made to work on 64-bit, but I got lazy ^^
https://godbolt.org/z/6PWfYnno7

use std::mem::*;

fn mk_arr<const N: usize>() -> &'static mut [MaybeUninit<u8>; N] {
    Box::leak(Box::new([const { MaybeUninit::uninit() }; N]))
}

fn pidgeon_hole(arrs: [&mut [MaybeUninit<u8>]; 3]) {
    let [a, b, c] = arrs;
    // SAFETY: By pigeonhole principle, the total size of pointees behind
    // different `&mut T`s can never overflow, due to the type invariant
    // of their allocations not overlapping.
    unsafe { 
        size_of_val(a)
            .checked_add(size_of_val(b)).unwrap_unchecked()
            .checked_add(size_of_val(c)).unwrap_unchecked();
    }
}

pub fn main() {
    const N: usize = usize::MAX / 2;

    // LLVM just assumes this doesn't fail because
    // we're not using the allocations
    let a = mk_arr::<N>();
    let b = mk_arr::<N>();
    let c = mk_arr::<N>();

    // If LLVM can prove that we make it here, we have UB.
    // LLVM assumes the allocations succeed, so this will miscompile.
    pidgeon_hole([a, b, c]);    
}

@rustbot label I-unsound I-miscompile A-LLVM T-opsem

Start by reproducing the 32-bit example from the issue and reviewing rust-lang/unsafe-code-guidelines#328, including the linked Godbolt case. Work out the applicable LLVM allocation and optimization assumptions; done means the demonstrated allocation-failure case no longer permits the described invariant violation or miscompilation, with the behavior covered by an appropriate regression test.