Return-position noalias

[RalfJung]

LLVM supports the noalias attribute in return position, and Rust uses that for functions that return Box. However the semantics of that are mostly unclear I think -- this has very little to do with argument-position noalias.

I think in Stacked Borrows terms it corresponds to something like: give the return value a fresh tag, and remove all other tags from the stack.

Questions:

• Is that the right semantics?
• Should there be some way to get return-position noalias without using Box? @gnzlbg recently mentioned a usecase for that.

[RalfJung]

Specifically I think this code has UB since the returned box aliases m:

fn id<T>(x: Box<T>) -> Box<T> { x }

fn main() {
    let mut m = 0;
    let b = unsafe { Box::from_raw(&mut m) };
    let mut b2 = id(b);
    *b2 = 5;
    std::mem::forget(b2);
    println!("{}", m);
}

Miri however says this code is fine.

Cc @nikic @comex do you know the exact assumptions introduced by return-position noalias?

[nikic]

LangRef:

Furthermore, the semantics of the noalias attribute on return values are stronger than the semantics of the attribute when used on function arguments. On function return values, the noalias attribute indicates that the function acts like a system memory allocation function, returning a pointer to allocated storage disjoint from the storage for any other object accessible to the caller.

So yes, that example would be UB.

[RalfJung]

So how is that supposed to work for boxes with custom allocators?

@rust-lang/wg-allocators the type Box<T, A> is decorated with noalias as a return type by Rust, which means that affected functions must return "a pointer to allocated storage disjoint from the storage for any other object accessible to the caller". Arguably this is violated by a custom allocator that hands out memory that is also accessible to the caller by other means.

In particular this makes an allocator like the following unsound:

struct OnceAlloc<'a> {
    space: Cell<&'a mut [MaybeUninit<u8>]>,
}

unsafe impl<'shared, 'a: 'shared> Allocator for &'shared OnceAlloc<'a> {
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        let space = self.space.replace(&mut []);

        let (ptr, len) = (space.as_mut_ptr(), space.len());

        if ptr.align_offset(layout.align()) != 0 || len < layout.size() {
            return Err(AllocError);
        }

        let slice_ptr = ptr::slice_from_raw_parts_mut(ptr as *mut u8, len);
        unsafe { Ok(NonNull::new_unchecked(slice_ptr)) }
    }

    unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
}

The issue is code like this

    let mut space = vec![MaybeUninit::new(0); 1];
    let once_alloc = OnceAlloc { space: Cell::new(&mut space[..]) };

    let boxed = Box::new_in([42u8; 1], &once_alloc);
    drop(boxed); // basically a NOP

LLVM assumes that boxed does not alias anything else, causing UB when space gets dropped and deallocates the memory that boxed used to point to.

(In this concrete case the Box is 2 ptrs in size, and we don't add a noalias to its first field, possibly because LLVM does not support such attributes -- but one can imagine similar situations where the custom allocator is a ZST. Also should the aliasing rules for the Box pointer really depend on whether the allocator is a ZST? That does not sound reasonable to me.)

[Diggsey]

So, previously we discussed the idea of an allocator wrapper that would apply the "allocation magic" used by LLVM to optimize allocations.

Could that approach solve the same problem here? We could say that allocators such as the one you gave in your example are sound, but would be unsound if wrapped in this magic type since they don't uphold the necessary guarantees. noalias would only be applied by the compiler to the subset of Boxed types which use the magic allocator wrapper.

[RalfJung]

That would help with the immediate example, but if the semantics of return-position noalias are as my PR defines them, only very few allocators will be able to use that magic wrapper. The LLVM requirement of being "disjoint from the storage for any other object accessible to the caller" has no time limit, and due to things like inlining "caller" recursively means basically the rest of the program. I think this is not even compatible with the concept of "nesting" allocators that we discussed previously. To make something like that possible, LLVM would have to take into account that calling free can move ownership of such memory back to the outside world, which poses restrictions on moving loads and stores up across free.

Basically return-position noalias can only be used for malloc and thin wrappers around malloc, where deallocation removes the memory entirely from the abstract machine state. Any time that there is a "life after deallocation" inside the abstract machine, we cannot use this attribute. (LLVM better makes sure that free never gets inlined even with LTO, otherwise this could go wrong real badly.)

[Amanieu]

I believe these LLVM attributes were only ever designed to work in a situation where malloc is in a separate compilation unit (libc) and it acts as a black box to the optimizer (on both ends). This is definitely a flaw in the LLVM attribute and a better mechanism should be designed in LLVM to properly handle this situation. I know GCC and MSVC have similar attributes for return value noalias on malloc, so perhaps they could be involved as well?

[comex]

Indeed, putting return-position noalias onto all functions returning Box is unsound, because when LLVM assumes the return value cannot alias anything else, that includes values that existed before calling the function. In other words, if you have

fn id(x: Box<i32>) -> Box<i32> { x }

// given a: Box<i32>
*a = 1;
let b: Box<i32> = id(a);
print(b);

then LLVM thinks that a and b cannot alias. If it also knows that id has no side-effects, then it can reorder *a = 1; and print(b);.

The bad aliasing assumption can be demonstrated using -aa-eval or -print-alias-sets. But I had quite a hard time actually exploiting it, because the situations where LLVM will actually reorder accesses are somewhat narrow and many of them don't apply here. For the same reason, I'm not surprised we haven't seen reports of breakage in practice. I did manage to exploit it though, using only safe code...

Exploitation details

My usual approach to exploiting bad noalias assumptions between a and b involves accessing a first, then b, then a again – for instance, write 100 to a, write 200 to b, then read from a, and let LLVM's GVN pass optimize the read to return 100, even though it should return 200 because a and b secretly alias. But that isn't an option here where, before you can access b, you have to pass a through the id function and (because it's a Box) lose access to it. Another approach is to rely on loop-invariant code motion (LICM), i.e. hoisting instructions out of loops if they compute same value on every loop iteration. But that's also difficult here (at least if the goal is to use only safe code), because just putting the code in a loop would result in the compiler complaining about use-after-move of a. You could replace a with a new value at the end of the loop, but that would make it not loop invariant. However, I managed to get this to work by having a be effectively undefined on the second and further iterations… at the cost of the code that uses it being not actually reachable on those iterations, because we break out of the loop first. This has the downside of allowing the optimizer to remove the loop entirely. Even though we only care about the first iteration, removing the loop entirely would prevent LICM from running. But luckily the LICM pass is executed before the pass that removes the loop.

Demo: https://rust.godbolt.org/z/6nvcqnesf

It prints 100 with optimizations enabled, but the correct value is 10, as is printed with optimizations disabled. Note that this only works with -C panic=abort.

[RalfJung]

Wait that noalias also works backwards in time on pointers before the fn was called? Wow that is not what I expected. Seems pretty broken, at leat for our usecase.

[RalfJung]

In that case I see no option than to just stop using this attribute: rust-lang/rust#106371

[RalfJung]

Closed by rust-lang/rust#106371