Repository navigation
Return-position noalias #385
Description
Activity
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?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.
So how is that supposed to work for boxes with custom allocators?
@rust-lang/wg-allocators the type
Box<T, A>is decorated withnoaliasas 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
boxeddoes not alias anything else, causing UB whenspacegets dropped and deallocates the memory thatboxedused to point to.(In this concrete case the
Boxis 2 ptrs in size, and we don't add anoaliasto 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.)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.
noaliaswould only be applied by the compiler to the subset ofBoxed types which use the magic allocator wrapper.That would help with the immediate example, but if the semantics of return-position
noaliasare 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 callingfreecan move ownership of such memory back to the outside world, which poses restrictions on moving loads and stores up acrossfree.Basically return-position
noaliascan only be used formallocand thin wrappers aroundmalloc, 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 thatfreenever gets inlined even with LTO, otherwise this could go wrong real badly.)I believe these LLVM attributes were only ever designed to work in a situation where
mallocis 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 onmalloc, so perhaps they could be involved as well?Indeed, putting return-position
noaliasonto all functions returningBoxis 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 havefn 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
aandbcannot alias. If it also knows thatidhas no side-effects, then it can reorder*a = 1;andprint(b);.The bad aliasing assumption can be demonstrated using
-aa-evalor-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 betweenaandbinvolves accessingafirst, thenb, thenaagain – for instance, write 100 toa, write 200 tob, then read froma, and let LLVM's GVN pass optimize the read to return 100, even though it should return 200 becauseaandbsecretly alias. But that isn't an option here where, before you can accessb, you have to passathrough theidfunction and (because it's aBox) 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 ofa. You could replaceawith 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 havingabe 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
100with optimizations enabled, but the correct value is10, as is printed with optimizations disabled. Note that this only works with-C panic=abort.Reacted by bjorn3, Elichai Turkel, Andrew Wock, Jakob Degen, Ralf Jung and Alona Enraght-Moony- 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.Reacted by Diggory Blake
In that case I see no option than to just stop using this attribute: rust-lang/rust#106371
Closed by rust-lang/rust#106371
- added a commit that references this issue
on Jan 3, 2023
LLVM supports the
noaliasattribute in return position, and Rust uses that for functions that returnBox. However the semantics of that are mostly unclear I think -- this has very little to do with argument-positionnoalias.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:
noaliaswithout usingBox? @gnzlbg recently mentioned a usecase for that.