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 :)

[HeroicKatora]

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)
        }
    }
}

[HeroicKatora]

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.

[HeroicKatora]

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.

[HeroicKatora]

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

[oberien]

I've read a bit more into rid an UB operation from all of its UB-powers. At this point I don't think that it's actually possible.

• {read,write}_volatile
  • "operations which […] have undefined behavior can be hoisted past a volatile operation."
• std::hint::black_box
  • defined in RFC: hint::bench_black_box rust-lang/rfcs#2360
  • "This property makes black_box […] too unreliable when disabling these optimizations is required for correctness."
• inline-assembly as "manual" black_box
  • currently inline-assembly can be used as black_box (and is used that way)
  • however, "The only reason black_box happens to work is that LLVM does not analyze the assembly code inside the asm!. But there is nothing in the hypothetical asm! spec that prevents it from doing so."
• "strong" black_box baked into llvm as intrinsic
  • black_box with strong guarantees instead of being a hint
  • its semantics are very unclear
  • could be similar to an unknown function to llvm

Any use of a black_box that is compiler-dependent isn't guaranteed to always work. While it may work at the moment, that doesn't mean that a new version of the same compiler will also generate the same code. In fact, it's not even guaranteed that we'll always be passed to llvm. There can be a different rust compiler in the future, which uses a different backend, which acts completely different.
Moreover, unless the semantics of the black_box are defined to prohibit all optimization related to the input, it doesn't help here. That's due to some optimizations, which may result in a different case of UB than we anticipated. Even if such a black_box existed, the performance overhead would be too high for the concat functionality provided by this crate. At that point it might even be faster to perform a new allocation and append the values on the heap.

For all of the above reasons, I'll drop the idea of having a safe unsound function.

[RalfJung]

@oberien also see https://youtu.be/nXaxk27zwlk?t=2445 for Chandler (of LLVM fame) saying that (the equivalent of) black_box must not be used to avoid UB:

Don't defeat the optimizer because you have undefined behavior in your source code and you're like 'No no no optimizer, you're not going to miscompile my code today, nah ah!'. That's not gonna actually work for you. It goes very badly.

[oberien]

Everything is marked as unsafe as of #7 and we'll add proper reasoning to the readme in #9. I'll make a new release after #9 and yank all previously released versions.

Ifneedbe, we can try implementations of the approaches suggested in #8 (comment) and #8 (comment).

[maplant]

One solution for this problem would be to allow this method only for strings, and then to add a null-terminator (or any arbitrary byte) to the end of every string, which is then not included in slices to the string content.
This would ensure that slices cannot be contiguous across allocation boundaries, at the cost of one extra byte per string (and probably a lot of work to the standard library).
This in theory could also be done for arrays, but I would argue that is likely to be a much larger cost than a single byte per string, which is already a cost that C accepts.

[hanna-kruppe]

Even if we were willing to add this to Strings, one can construct a &str from an &[u8] to arbitrary memory, which need not have the same terminator. For example, take the example snippet I gave at the start and throw in some str::from_utf8: same problem for &strs and no terminator byte after either string.

[maplant]

Right, so you would have to add end padding of at least one byte to every block of memory that is allocated and then adjust the safety requirements for all from_utf8 methods for strings, all so that strs can be rejoined.

FTR I'm not advocating for this but if a pointer crossing allocation boundaries is UB then there is no other way to do this safely.

[hanna-kruppe]

I don't see how padding all allocations is possible (what about memory allocated outside Rust? what about Rust code calling into other allocators via FFI? etc.). Even if it was, the overhead would likely be way too big to accept. So I guess that leaves just the status quo of "not safely possible"?

[maplant]

It would be possible to make every allocation that occurs within the standard library and every allocation that the rust compiler makes to have an extra padding. As for outside allocations, those require unsafe code anyway so the solution for that would be to simply adjust the safety requirements of methods that convert from bytes to str to include some sentence like "every block of memory passed into here must have at least one extra byte allocated passed the end".
However, I'm not sure what the rust team's stance on adding extra safety requirements to methods is, so it might not be possible to do in practice. On the other hand, in practice, this safety requirement would be only required to ensure that this one method operates properly, and therefore could possibly added only to the method (i.e. something like "in order to use concat, both strings must be correctly allocated with at least one extra byte passed the end of their internal storage").
I'm not quite sure how large the overhead truly would be, in practice heap allocators usually use headers that are aligned to blocks, so adding a byte will only cause for extra memory to be allocated 1/4 of the time on the heap, and allocations on the stack are fairly rare. Maybe we could make this only apply to arrays of size u8 as well, maybe not.
With all that said, considering the time it would take to implement, the amount of safety requirements and gymnastics that need to be documented, and the potential to cause a significant amount of overhead, I would say that it is practically impossible to implement safely.

[HeroicKatora]

Padding allocations with a spare byte might still make an interesting custom type, outside the standard library. If joining is really necessary for some algorithm or performance reasons then this would be neat to have. I don't see a point in an (essentially) user requirement affecting the standard library and, fundamentally, the memory model underlying it. That sounds horribly contagious given that there are a ton of programs that apparently wouldn't even benefit from it as they work fine without join.

[HeroicKatora]

It would be possible to make every allocation that occurs within the standard library and every allocation that the rust compiler makes to have an extra padding.

If you want a safe generic join then that is insufficient. The memory model is not equivalent to the standard library and alloc can be implemented in user programs, the fact that it require unsafe is not sufficient to allow changing it arbitrarily. The unsafe requirements of the allocator interface only pertains to some invariants that the caller has to manually uphold, such as dealloc only being called on pointers previously obtained via alloc. It is not a blanket permission to make arbitrary changes. If you think so, that is a fundamental misunderstanding of what unsafe is in the Rust language.

So a generic join would need to work with all possible object locations, including those allocated by the standard library. However, not limited to those. Therefore you really need to change the memory model if you want to have it, you are free to make an RFC for that of course but I'm quite confident that it is unlikely to be accepted.

[HeroicKatora]

@oberien If you want to keep this issue open for tracking whether there is a possible safe wrapper (and what difficulties there are) then I think the above discussion is off-topic. The actual issue was fixed with the release of 0.2, so closing the issue and opening a dedicated tracking issue could also be useful.

[HeroicKatora]

[..] if a pointer crossing allocation boundaries is UB then there is no other way to do this safely.

This statement makes an assertion that I hadn't heard before and doesn't provide any evidence. Did you mean this in a colloquial sense, that there were many attempts but all failed, or in a true mathematical one?

[Lokathor]

There's an LLVM IR operation, "get element pointer inbounds", which must stay in bounds or point to the byte one past the end after the offset (similar to a C array offset/indexing), otherwise it's UB. However, this gives better optimization than using the less restricted offset operation.

So since indexing in rust has to be in bounds anyway, rust uses GEPI for indexing (once you go through all the compile laters).

So, pretty fundamentally, this entire goal of being able to join two slices or strings that happen to be next to each other in memory just won't work.

[RalfJung]

It's more than just the "inbounds" operation. Even the non-"inbounds" variant will always stay within the same allocation. Likewise, it is impossible in C by pure pointer arithmetic to switch between allocations.

This is also why the wrapping_offset docs say

Compared to offset, this method basically delays the requirement of staying within the same allocated object: offset is immediate Undefined Behavior when crossing object boundaries; wrapping_offset produces a pointer but still leads to Undefined Behavior if that pointer is dereferenced. offset can be optimized better and is thus preferrable in performance-sensitive code.

Casting to an integer, doing arithmetic and casting back should work, but unfortunately the details of integer-pointer casts are fuzzy enough and compilers are buggy enough around those details that it's hard to say.

[oberien]

If I understand correctly, what @maplant is suggesting, is to add allocation delimiters to rust's memory rules, such that we can check those during a safe join. The solution presented is, however, not sufficient, not even for strings, because those can contain zero-bytes. UTF-8 allows strings to contain the ASCII-Null character, which is represented by 0x00. We would need a more sophisticated rule to separate even string allocations.
Not to say, any pattern we come up can be contained within a byte-slice.
In general, I'd say that joining two adjacent slices within the same allocation without having access to the original slice is rare enough not to warrant a large backwards-incompatible change to the whole of rusts memory allocation rules (though take that with a grain of salt as I'm in no position to argue about that and have no relations to any of the involved rust teams).

Instead of changing all of the rust memory rules, as @HeroicKatora suggested, this could make an interesting library type, and is also somewhat related to what the bytes crate does. However, I don't see any advantage in a library-provided new type over just using the solutions lined out in #8 (comment) and #8 (comment).

As this issue is fixed with 0.2.0 and the yanking of all other versions, I'll close it and open separate issues for the two possible solutions proposed in the above comments. @maplant If you'd like to, you can also open a new separate issue to propose your solution laid out as a library type which could be implemented and integrated into this library as a solution with different tradeoffs compared to the other two.

[maplant]

If you want a safe generic join then that is insufficient. The memory model is not equivalent to the standard library and alloc can be implemented in user programs, the fact that it require unsafe is not sufficient to allow changing it arbitrarily. The unsafe requirements of the allocator interface only pertains to some invariants that the caller has to manually uphold, such as dealloc only being called on pointers previously obtained via alloc. It is not a blanket permission to make arbitrary changes. If you think so, that is a fundamental misunderstanding of what unsafe is in the Rust language.

My statement implicitly requires a change to the memory model so I'm not sure exactly what you're getting at, apologies if I'm not making my comments as clear as they should be. My point is that it is possible to have this implemented opaquely in Rust internally. It is not, however, possible to have this work with all rust code currently, because now there is a new requirement that all allocated blocks have to have an extra byte. That being said, it would be possible to implement this without breaking any rust code.

I am also quite confident that this would never be accepted :-)

This statement makes an assertion that I hadn't heard before and doesn't provide any evidence. Did you mean this in a colloquial sense, that there were many attempts but all failed, or in a true mathematical one?

Are you asking me if I have a mathematical proof that it is impossible to ensure that two blocks of memory with the same lifetime are non-continuguous, I do not at the top of my head.

@oberien erp!!! sorry I commented right after you closed the issue. My apologies

[oberien]

Race conditions :) Feel free to open another issue to further explore and discuss your idea, I'm interested if this might be a possible solution.

[HeroicKatora]

Are you asking me if I have a mathematical proof that it is impossible to ensure that two blocks of memory with the same lifetime are non-continuguous, I do not at the top of my head.

You initially asserted in this comment that changes to the memory model are necessary. I'm asking for a something backing up the assertion that in the current memory model a safe join function can not be implemented. This obviously depends on what join is even supposed to do, and on which references it should work, for which we might not have a common defintion even.

[HeroicKatora]

That being said, it would be possible to implement this without breaking any rust code.

@maplant That is demonstrably false. The alloc::GlobalAlloc trait is stable. Adding new unsafe requirements to the trait would break those existing implementations in very subtle ways. Contrary to C (and C++), the standard library has much less special treatment and is in many ways only a stable interface to the unstable language internals, not the source of language memory rules¹. That is, it may access features that are not stable (and those features can change). But the feature accessed by alloc is not a special new kind of objects that are allocated but instead it is the existence of a global allocator object with special linkage. Almost all other functionality is implemented in pure user code. Even alloc::alloc::Layout does not define what parts of the object model are stable but instead gives safe access to those parts that definitely are.

---

¹ For example, did you know that std::vector (C++) could not be implemented as a user-type because it inherently creates arrays of objects from memory that was not allocated as an array of those objects? Don't trust me, trust an MSVC STL Dev. All standard library implements would be UB if implemented by a user.

[maplant]

Adding new unsafe requirements to the trait would break those existing implementations in very subtle ways.

That is not what I'm suggesting, I'm suggesting changing the way the alloc trait is used, not adding unsafe requirements to alloc. The invariants would not change. The unsafe requirements would be added to other library constructors. In older code this invariant would be broken however since "join" would be the only method that uses this and older code by definition cannot use this new method and violating these invariants would never invoke UB in practice. Should that code be changed to use join, it would immediately be broken.

You are right that there are a number of issues with this. Again I'm not advocating for it, it's just a random idea I had.

Regardless, this issue is closed and your tone seems more intent on trying to teach me something than trying to have a meaningful discussion this will be the last comment I make. If you would like to further this discussion feel free to send me an email.