Unsoundness if two separate allocations happen to be next to each other

[hanna-kruppe]

First off, kudos for carefully considering each of the stated safety requirements for each unsafe operation used and documenting these so clearly. However, I believe I found a subtle issue that can lead to UB. It relates to a requirement that is unfortunately not explicitly noted (unless I missed something), but follows from how slices and str work. For simplicity I'll demonstrate with u8 slices and the currently-internal concat_slice function, but of course str is just as affected.

To set the stage, note that it is possible for two separate allocations (for example, two Strings, or two u8 arrays on the stack) to be adjacent in memory. When that happens, this crate will happily detect that they're adjacent and concatenate them. I don't think there's any way to avoid that, and while one can't rely on two allocations being adjacent, maybe someone wants to make use of it when the stars align (or they simply made a mistake when passing the pointers).

The problem arises after the concatenated slice is constructed: indexing into it or slicing it (and likely other operations) calculates addresses in ways that assume the pointer doesn't cross allocation boundaries, otherwise it's UB. For example, given bytes: &[u8], the expression bytes[i] boils down to something involving the pointer bytes.as_ptr().add(i). That can cross from the first allocation into the second in the scenario we're considering, but <*const T>::add states among other safety preconditions:

Both the starting and resulting pointer must be either in bounds or one byte past the end of the same allocated object.

So the following code will have UB in the cases where concat_slice returns Ok(..):

let buf1 = [0; 16];
let buf2 = [0; 16];
if let Ok(combined) = concat_slice(&buf1, &buf2) {
    let x = combined[20];
}

In effect, slices and strs and other safe references can't span allocation boundaries. Unfortunately, since I also don't know a way to ensure that two references come from the same allocation, I believe this makes it impossible to soundly provide the operations this crate exists to provide 😭

NOTE: Theoretically it's an implementation detail that add -- or any of its cousins with the same precondition -- is used here. However, this requirement is pretty important for performance and thus unlikely to change, which is why I'm raising it here first. Certainly should be documented, though. I filed rust-lang/rust#62765 for that.

[oberien]

Thanks for the report and find! I really didn't think about that. You're right that you can currently achieve your behaviour, which is UB both from the side of implementation details of slice, and from llvm's pointer aliasing rules. Thus we should mark all of those functions as unsafe.

We could provide a safe interface by taking the full original allocation in addition to the two sub-slices. That way we don't even need unsafe, because we can create the returned slice from the original full allocation (only works for non-mut references). This doesn't really have any advantage over just using ranges into the original slice except for maybe some sort of ergonomics for some specific use-cases.

fn concat_slice<'a, T>(all: &'a [T], sub_a: &'a [T], sub_b: &'a [T]) -> &'a [T] {
    let all_end = unsafe { all.as_ptr().add(all.len()) };
    let sub_a_end = unsafe { sub_a.as_ptr().add(sub_a.len()) };
    let sub_b_end = unsafe { sub_b.as_ptr().add(sub_b.len()) };
    // check that sub-slices are in-bounds in full allocation
    assert!(all.as_ptr() <= sub_a.as_ptr() && all.as_ptr() <= sub_b.as_ptr()
        && all_end >= sub_a_end && all_end >= sub_b_end);
    // check that sub-slices are next to each other
    assert!(sub_a_end == sub_b.as_ptr());

    // concatenate
    let num_elems = sub_a.len() + sub_b.len();
    let start_elem = match mem::size_of::<T> {
        0 => panic!("We can't find out the starting element of sub_a"),
        s => unsafe { sub_a.as_ptr().sub(all.as_ptr()) } / s,
    }
    &all[start_elem..][..num_elems]
}

Is it somehow possible to find out where a subslice of a slice of ZSTs points to, i.e. which is the first element the subslice points to? Is it safe to just ignore the starting element and make the new concatenated slice start from the beginning of the full original slice?

[hanna-kruppe]

Is it somehow possible to find out where a subslice of a slice of ZSTs points to, i.e. which is the first element the subslice points to? Is it safe to just ignore the starting element and make the new concatenated slice start from the beginning of the full original slice?

All the elements are at the same address anyway, so I think you should be able to get away with just slicing with 0..(sub_a.len() + sub_b.len()).

[oberien]

Syntactically, I also think that should be fine. But considering the latest discussion I'm unsure if that's also semantically correct and not actually able to trigger some sort of undefined behaviour in the guarantees inside the compiler. Especially since the behaviour around slices of ZSTs seem highly underdocumented :)

[197g]

I had an idea going in a different direction. Keep the current interface but mark it unsafe and state that its only required safety invariant be that both slices are part of the same allocation. Then introduce a new type that dynamically constructs the proof that for some lifetime, some addresses are within the same allocation. We could then use that proof instance to check that both joined slices are part of that allocation and hence part of the same allocation. This comes as useful because we can not keep an unborrowed reference to the whole slice when we want to create and join mutable parts.

pub struct SameAllocation<'a, T> {
    phantom: PhantomData<&'a [T]>,
    base: usize,
    bytes: usize,
}

impl<'a, T> SameAllocation<'a, T> {
    pub fn new(ptr: &'a [T]) -> Self {
        SameAllocation {
            phantom: PhantomData,
            base: ptr.as_ptr() as usize,
            bytes: ptr.len() * mem::size_of::<T>(),
        }
    }

    // Pretend to borrow but return the complete array.
    pub fn new_mut(ptr: &'a mut [T]) -> (Self, &'a mut [T]) {
        let result = SameAllocation {
            phantom: PhantomData,
            base: ptr.as_ptr() as usize,
            bytes: ptr.len() * mem::size_of::<T>(),
        };
        (result, ptr)
    }

    // Possible `unsafe fn new_unchecked` variant omitted

    // Join two slices that must be part of the allocation used in the construction.
    pub fn join<'b: 'a>(&self, a: &'b mut [T], b: &'b mut [T]) -> Result<&'b mut [T], Error> {
        // Assert the beginning is within the allocation. Instead of asserting we could error.
        // This guarantees each complete slice is within the same allocation.
        assert!(self.base <= a.as_ptr() as usize && a.as_ptr() as usize <= self.base + self.bytes);
        assert!(self.base <= b.as_ptr() as usize && b.as_ptr() as usize <= self.base + self.bytes);
        unsafe {
            // SAFETY: Guaranteed the exact check we need for the current method.
            concat_slice_unchecked(a, b)
        }
    }
}

[197g]

Usage of the above proposal:

// usage:
fn main() {
    let mut data = [0xa; 16];
    let (allocation, data) = SameAllocation::new_mut(&mut data[..]);
    
    let (a, b) = data.split_at_mut(10);
    let rejoined = allocation.join(a, b).unwrap();
    
    assert_eq!(rejoined, &[0xa; 16]);
}

play. If this is sound it would give me incredible satisfaction since it can only be done in Rust due to its reliance on lifetimes and thus C/C++ would face the same problem with UB safety we currently face but can not resolve it.

[oberien]

self_mut might not be safe, because you have PhantomData<&'a [T]> and not &'a mut [T]. You can't merge non-mut and mut variants I think.

[197g]

self_mut might not be safe, because you have PhantomData<&'a [T]> and not &'a mut [T]. You can't merge non-mut and mut variants I think.

Why would I need that? The code never accesses the mutable slice underlying the allocation through any non-mutable reference. I'm not even sure if the type parameter T is necessary and it could do with just a PhantomData<&'a ()>. The fact 'within the same allocation' is independent of the slice type that has been constructed in the allocation (at least gep has no problems) and we are only required to operate in the bounds of the underlying allocation object.

[oberien]

Edit: Doesn't work as discussed in #8 (comment)

Here is a super-crazy idea: The main problem here is that the compiler can use the UB to perform optimizations based on usage of the original slices and its knowledge where the resulting slice is coming from. For example in the original code below, the compiler optimizes buf2 away, because its pointer isn't used anywhere, giving us access to uninitialized memory.

let buf1 = [0; 16];
let buf2 = [0; 16];
concat_slice(&buf1, &buf2).unwrap()[20];

However, if we rid the compiler of any information it knew about the input and output slices, we might get away with technically having UB. The compiler can't perform any optimizations on the assumptions we break, because it doesn't know about any of those guarantees anymore. We can do that by simply black_boxing those three slices.

You can find a godbolt example here. Without any black_box, the compiler detects and abuses the UB to do whatever it pleases (which in this case is an unconditional panic during the adjacency check. However, if we uncomment the line with concat2, which has the black boxes, the resulting code should function just fine.

Obviously, this is playing with fire:

1. We still have UB. We don't have anything to prevent it. We just try to mitigate its effects. We fight its symptoms.
2. Using a black_box not only adds direct overhead of the ptr::read_volatile on stable, but also prevents lots of compiler optimizations, as seen below.

lea rax, [rsp + 32]
lea r14, [rsp + 32]
cmp rax, r14
jne .LBB10_1

3. We probably can't ensure that UB will never occur, even though I'm somewhat certain that this "solution" should work.

What do you think? Could this be the very first safe unsound function? ;)

[Lokathor]

No, it couldn't

[RalfJung]

@oberien see rust-lang/rfcs#2360 for a detailed discussion about black_box, what it can be used for, how to specify it, and so on. This comment links to some of the key posts.

[197g]

Implementation of my above idea: https://github.com/HeroicKatora/str-concat/tree/proof-instance