(Maybe) Undefined behavior in safe code from `getelementptr inbounds` with offset 0

[jturner314]

As far as I can tell, slicing a Vec<T> (in safe code) results in undefined behavior when T is zero-sized or the Vec has zero capacity. I'm probably missing something, but I'm creating this issue in case my investigation is correct.

In particular, these two examples appear to cause undefined behavior due the .offset() call violating the first safety constraint ("Both the starting and resulting pointer must be either in bounds or one byte past the end of the same allocated object.") when performing the slice:

// Example 1: zero-sized T
let v = Vec::from(&[(); 5][..]);
let _ = &v[2..3];

// Example 2: zero-capacity Vec
let v = Vec::<i32>::with_capacity(0);
let _ = &v[0..0];

Example 1

In the first example, the v has field values

Vec {
    buf: RawVec {
        ptr: Unique {
            pointer: NonZero(0x1 as *const ()),
            ..
        },
        ..
    },
    len: 5,
}

(Verify this with v.as_ptr() and v.len().) Performing the slice &v[2..3] expands to approximately the following:

let slice = unsafe {
    let p = v.buf.ptr();
    assume(!p.is_null());
    slice::from_raw_parts(p, v.len)
};
// Note that the pointer of `slice` has value `0x1`.
// (Bounds checks elided here.)
unsafe {
    from_raw_parts((slice as *const [()] as *const ()).offset(2), 3 - 2)
}

So, it's calling ptr.offset(2) where ptr has value 0x1. This pointer is not "in bounds or one byte past the end of [an] allocated object", so the .offset() is undefined behavior. (This pointer was created from casting an integer (the alignment of ()) to a pointer in libcore/ptr.rs, Unique::empty.)

Example 2

The second example has a similar issue. In the second example, the v has field values

Vec {
    buf: RawVec {
        ptr: Unique {
            pointer: NonZero(0x4 as *const i32),
            ..
        },
        ..
    },
    len: 0,
}

(Verify this with v.as_ptr() and v.len().) Performing the slice &v[0..0] expands to approximately the following:

let slice = unsafe {
    let p = v.buf.ptr();
    assume(!p.is_null());
    slice::from_raw_parts(p, v.len)
};
// Note that the pointer of `slice` has value `0x4`.
// (Bounds checks elided here.)
unsafe {
    from_raw_parts((slice as *const [i32] as *const i32).offset(0), 0 - 0)
}

So, it's calling ptr.offset(0) where ptr has value 0x4. This pointer is not "in bounds or one byte past the end of [an] allocated object", so the .offset() is undefined behavior. (This pointer was created from casting an integer (the alignment of i32) to a pointer in libcore/ptr.rs, Unique::empty.)

Further investigation

There are a few ways that these examples might actually not be undefined behavior:

1. If the documentation is incorrect, and .offset() is in fact safe if the offset in bytes is zero (even if the pointer is not part of an allocated object).

2. If LLVM considers Unique::empty to be an allocator so that the returned pointer is considered part of an allocated object. I don't see anything to indicate this is the case, though.

3. If, somewhere, the runtime allocates the range of bytes with addresses 0x1..=(max possible alignment). This would mean that pointers returned by Unique::empty would be within an allocated object. I don't see anything to indicate this is the case, though, and I'm not entirely convinced that casting an integer to a pointer would work in this case anyway (since the pointer would be derived from an integer instead of offsetting a pointer of an existing allocation).

I did some further investigation into possibility 1.

The .offset() method is converted into an LLVM getelementptr inbounds instruction. (src/libcore/ptr.rs provides the .offset() method, which calls intrinsics::offset. src/libcore/intrinsics.rs defines the extern "rust-intrinsic" offset but not the implementation. The codegen_intrinsic_call function in src/librustc_codegen_llvm/intrinsic.rs handles the "offset" case by calling .inbounds_gep() in the Builder. The implementation of .inbounds_gep() is provided in src/librustc_codegen_llvm/builder.rs, which in turn calls the extern function LLVMBuildInBoundsGEP imported in src/librustc_llvm/ffi.rs. The function is defined in src/llvm/include/llvm-c/Core.h)

The docs for the LLVM getelementptr inbounds instruction say the following:

If the inbounds keyword is present, the result value of the getelementptr is a poison value if the base pointer is not an in bounds address of an allocated object, or if any of the addresses that would be formed by successive addition of the offsets implied by the indices to the base address with infinitely precise signed arithmetic are not an in bounds address of that allocated object. The in bounds addresses for an allocated object are all the addresses that point into the object, plus the address one byte past the end. The only in bounds address for a null pointer in the default address-space is the null pointer itself. In cases where the base is a vector of pointers the inbounds keyword applies to each of the computations element-wise.

The LLVM docs say this about poison values:

Poison values are similar to undef values, however they also represent the fact that an instruction or constant expression that cannot evoke side effects has nevertheless detected a condition that results in undefined behavior.

…

Poison values have the same behavior as undef values, with the additional effect that any instruction that has a dependence on a poison value has undefined behavior.

As far as I can tell, the reason why the Rust docs for .offset() consider getting a "poison value" to be undefined behavior is that performing any operation with a dependence on the poison value (e.g. printing it with println!) is undefined behavior. In particular, it's possible to perform operations with a dependence on a pointer value in safe code, so a pointer must never be a poison value.

Anyway, back to the safety constraints on .offset(). The constraints listed in the docs for getelementptr inbounds match the constraints listed in the docs for .offset() with one exception: "The only in bounds address for a null pointer in the default address-space is the null pointer itself." This means that even though a null pointer is not part of an allocation, it's still safe to perform an offset of 0 bytes on it. The docs for getelementptr inbounds don't indicate that this is true for non-null pointers, though, which is the case described in this issue (slicing a Vec with zero-size elements or zero capacity).

Meta

This appears to be an issue in both stable (1.29.1) and nightly.

[ishitatsuyuki]

Pardon me, but does this actually results in miscompilation? I'm aware the 1 approach is a dangerous manual layout optimization but cares have been taken to not actually let LLVM misbehave.

[hanna-kruppe]

cc @rust-lang/wg-unsafe-code-guidelines

[RalfJung]

Thanks for bringing this up! This is indeed an interesting question. And it's the same question in both cases: What, if any, are the "inbounds" addresses for non-NULL integer pointers (i.e., pointer created from integers instead of an actual allocation)?

I recall chatting with @arielb1 about this, and the answer I got (IIRC) was that all the integer pointers form one huge allocation excluding NULL which is in some logical way disjoint from the actual addresses covered by real allocations. So, my understanding is that getelementptr inbounds on an integer pointer is okay if the pointer does not "change" from being non-NULL to NULL or vice versa -- and moreover, the resulting pointer cannot be used to actually access any memory even if it is bitwise equal to a "proper" pointer. IOW, (1 as *mut u8).offset(ptr as usize) is very different from (ptr as *mut u8).offset(1). The former is an "integer pointer" and not allowed to be used, the latter is perfectly fine to use (if ptr points to a large enough allocation).

This also matches the formal model that we recently proposed. That paper proves correctness of at least some of the alias analysis done by LLVM, showing that the model is compatible with what LLVM does. Basically, the reason this works is that the resulting pointer (in the "integer allocation") can never be dereferenced, so it doesn't really matter what alias analysis thinks it might alias with.

It would be interesting to get an official answer from LLVM on this, and I wouldn't know that we can do much until we get clarification from their side. We could rule out offset on integer pointers, but given that this is likely okay and compatible with LLVM, that seems premature.

[arielb1]

So @RalfJung's model successfully performs "optimization chicken" for pointers that come from integers.

What I said was the situation with LLVM was entirely different - it's more of an "LLVM-ABI interface" issue: why do you think there isn't a valid 0-sized object at address 0x1? There's no conflicting thing that LLVM "owns", so we can say that there is such an object and LLVM won't object.

This is similar to being able to mmap addresses and use them in LLVM, without it being UB - in a world where you work with an ABI, it is impossible to make "whole-program" assumptions (for example, that you all objects) even if you know the entire program, because unsafe code can assume that it can work by following the ABI.

This is not an "optimization chicken" thing - if you start from an 0x1 pointer, you can't gepi your way into a stack allocation and scribble into it. But if you somehow remapped the null page into something accessible, you can scribble into that. And even if you haven't done any remapping,

OTOH, we have to be more careful with 0-sized objects at addresses that can conflict with memory that LLVM does "own". For example, in the following case, I think that LLVM should be allowed to fold the comparison here to true, even if y ends up at address 0x80000001:

let x: &() = &*(0x80000000 as *const u8);
let y: [u8; 2] = 0;
let _t = *x; // force `x` to be valid.

let x_addr = x as *const () as usize;
let y_addr = (&y) as *const () as usize;
// `y` is a stack object, and `x` is a valid object, therefore `x` and `y` must be disjoint.
if x_addr.wrapping_sub(y_addr) >= mem::size_of::<[u8; 2]>() {
    something_involving(x_addr, y_addr);
}

This means that we might have UB if we use Vec::new on objects with an alignment large enough to overlap with the stack.

[RalfJung]

I am not sure what exactly you mean by "optimization chicken". However:

• Your argument, if I understood it correctly, only applies to doing offset(0) on an integer pointer. According to @jturner314's analysis, we are also doing this with a non-zero offset.

• Your argument assumes that LLVM accepts 0-sized allocations as existing. I see no reason to assume that is the case.

---

For example, in the following case, I think that LLVM should be allowed to fold the comparison here to true, even if y ends up at address 0x80000001:

Pointer comparison is a whole different can of worms, and lucky enough not involved in the original question. ;) But since you did your comparison at integer type, I disagree with your analysis. Integer comparison should compare the "actual" address.

[jturner314]

does this actually results in miscompilation?

I don't know. I haven't experienced any miscompilation myself; I came across this issue while reading the libcore/liballoc source code. I submitted this issue in the hope that people more knowledgeable than me about the compiler/LLVM could determine whether or not it's actually undefined behavior. If it is not undefined behavior, then we should update the docs. If it is undefined behavior, then we should fix the implementation.

According to @jturner314's analysis, we are also doing this with a non-zero offset.

A clarification: the current implementation does perform a nonzero offset but only when T is zero-size. In other words, the offset in units of T (the count argument to .offset() is in units of T) may be nonzero, but the offset in units of bytes is always zero.

Fwiw, the current implementation calls .offset() on a Unique::empty() pointer in additional places too. I created this issue describing slicing because it was the most obvious and occurs for zero-capacity Vecs in addition to Vecs with zero-size elements. However, the same behavior also occurs in the following:

• .insert() with zero-size elements. This also involves ptr::copy and ptr::write at the offset pointer.
• .remove() with zero-size elements. This also involves ptr::read and ptr::copy at the offset pointer.
• .push() with zero-size elements. This also involves a ptr::write at the offset pointer.
• .get() and .get_mut() with zero-size elements (with usize index). These also involve converting the pointer to a reference.
• .pop() with zero-size elements. This also involves a ptr::read at the offset pointer.
• .split_off() with zero-size elements.
• .split_at_mut() with zero-size elements or zero capacity.
• etc.

@RalfJung Thanks for the article! It's really helpful for understanding what kinds of optimizations LLVM might want to perform, and, as a result, why constraints on offsets are important. It seems like the primary goal of placing constraints on offsets is to be able to guarantee in certain cases that pointers don't alias.

If I understand the article correctly, under the proposed model, casting an integer to a pointer (as in Unique::empty) produces a "physical pointer", and it's always safe to perform inbounds offsets on a physical pointer (including things like moving the pointer across or between allocated objects) if the pointer is never dereferenced, since bounds checking is deferred until dereference (section 3.1). If a physical pointer is dereferenced at some point, its initial value and all subsequent values produced by inbounds offsets leading up to the dereference must be within a single allocated object, and (if the pointer and allocated object have lifetime information) the allocated object's lifetime must have started before the initial physical pointer was created and must end after the dereference.

The article is slightly ambiguous on the current behavior of LLVM, but I interpret it to mean that LLVM follows the "wildcard provenance" strategy for integer-derived pointers (section 2.4) with additional support for inbounds offsets to enable some optimizations (section 2.5). This seems to indicate that integer-derived pointers are okay in LLVM, and can even be dereferenced; LLVM must assume that they can point to any offset (except for offsets that would violate the inbounds constraint) in any allocation (wildcard provenance). This suggests to me that a zero-byte offset of an integer-derived pointer should always be safe in current LLVM.

@arielb1 You seem to be saying something like the following: "LLVM cannot assume that it knows about all allocations. For example, we can write a shared library in Rust, compiled with LLVM, with a function following the C ABI, and C/Haskell/Python/etc. can allocate an object and pass a pointer to that object to our library's function; LLVM would never be aware of that allocation. Therefore, LLVM must assume that any inbounds offset may be within an existing allocation unless it has evidence to the contrary. In other words, LLVM can't conclude that an offset of a pointer is a poison value just because it doesn't know about any allocations containing that pointer." Am I understanding correctly?

Following this line of reasoning, the only evidence that would allow LLVM to conclude that an inbounds offset violates the constraint would be:

1. If the pointer moves across an existing allocation that LLVM knows about.

2. If the pointer moves into or out of an existing allocation that LLVM knows about.

3. If LLVM does not accept zero-sized allocations as existing and any of addresses from (ptr created by Unique::empty()) to (ptr created by Unique::empty()) + mem::size_of::<T>() overlaps an existing allocation that LLVM knows about. (If LLVM does not accept zero-sized allocations as existing, then an allocation created on the other side of the ABI must be at least as large as mem::size_of::<T>() bytes. If such an allocation would overlap an allocation that LLVM knows about, then it must not exist (because that would violate the aliasing rules), and so the pointer is not in bounds of an allocated object.)

Case 3 is concerning because T can be arbitrarily large.

However, assuming LLVM does accept zero-sized allocations as existing, the only remaining case this explanation doesn't fully justify is if the pointer overlaps an allocation created on the LLVM side of the ABI. In this case, the base and offset would in fact be "in bounds" addresses of an allocated object, but LLVM might not allow pointers to its allocations to be created from integers this way. Since LLVM provides an inttoptr instruction, though, and @RalfJung's article seems to indicate that LLVM considers integer-derived pointers to have "wildcard provenance", I think this case is fine.

My conclusion from @RalfJung's article is that offsetting a pointer by zero bytes is probably always okay, regardless of the value of that pointer or how it was constructed. @arielb1's explanation provides additional support to this conclusion if LLVM accepts zero-sized allocations as existing.

It would be nice to get confirmation from LLVM on this. How's the best way to get an answer? Ask on the llvm-dev mailing list?

Thoughts?

[RalfJung]

A clarification: the current implementation does perform a nonzero offset but only when T is zero-size. In other words, the offset in units of T (the count argument to .offset() is in units of T) may be nonzero, but the offset in units of bytes is always zero.

Ah thanks, I had missed that indeed! I sent a PR to miri to enforce this restriction, and it seems in all the code it tests (which is not terribly much), this holds true.

If I understand the article correctly, under the proposed model, casting an integer to a pointer (as in Unique::empty) produces a "physical pointer", and it's always safe to perform inbounds offsets on a physical pointer (including things like moving the pointer across or between allocated objects) if the pointer is never dereferenced, since bounds checking is deferred until dereference (section 3.1). If a physical pointer is dereferenced at some point, its initial value and all subsequent values produced by inbounds offsets leading up to the dereference must be within a single allocated object, and (if the pointer and allocated object have lifetime information) the allocated object's lifetime must have started before the initial physical pointer was created and must end after the dereference.

Exactly.

The article is slightly ambiguous on the current behavior of LLVM, but I interpret it to mean that LLVM follows the "wildcard provenance" strategy for integer-derived pointers (section 2.4) with additional support for inbounds offsets to enable some optimizations (section 2.5).

Well, LLVM is mostly ambiguous about its semantics, so it's hard to say anything. ;)

But we think that our proposed semantics is consistent with what LLVM does currently, modulo the changes described in the paper.

My conclusion from @RalfJung's article is that offsetting a pointer by zero bytes is probably always okay, regardless of the value of that pointer or how it was constructed.

No, that's not correct. What we call a "logical" pointer in the paper does immediate bounds-checking, even if you offset by 0. So this is still illegal:

let x = Box::into_raw(Box::new(0u32));
let x = x.wrapping_offset(8); // okay, this has no inbounds tag
let x = unsafe { x.offset(0) }; // UB, the pointer is not inbounds of the only object it can point to

The reason this check is deferred to "physical" pointers is that we cannot know which object it is intended to point to. We could look up memory at this point and see which object lives at the given address, but then inttoptr and/or getelementptr could not be reordered wrt. to malloc/free, so that's not a good solution.

How's the best way to get an answer? Ask on the llvm-dev mailing list?

That's worth a try :)

[arielb1]

Your argument assumes that LLVM accepts 0-sized allocations as existing. I see no reason to
assume that is the case.

I don't think LLVM semantics are defined enough to decide whether it is the case or not. From what I know about LLVM optimizations, LLVM does handle 0-sized allocations.

Pointer comparison is a whole different can of worms, and lucky enough not involved in the original question. ;) But since you did your comparison at integer type, I disagree with your analysis. Integer comparison should compare the "actual" address.

The code dereferences the &() to force the allocation to be valid. This doesn't emit any LLVM IR today, but it could.

If zero-sized allocations can't overlap with stack addresses, there's no valid execution in which y_addr is 0x7fffffff - you would have already gotten UB when you dereference the zero-sized pointer. Therefore, the optimizer is justified in optimizing the if to be true. This is not based on y_addr being unknowable, only on it being a distinct allocation.

0x1 is obviously not even a valid 1-byte allocation - I would expect a 1-byte allocation to at least be dereferencable. So it if is a valid allocation, it is a valid 0-byte allocation.

We can have the semantics in which physical pointers have deferred bounds checking and there is no way to check whether zero-sized pointers point to a valid zero-sized allocation (in which case, zero-sized allocations have no effect), or we can have a world when there is such a way and there are zero-sized allocations. In both cases, align_of would work, as long as you don't alias the stack.

[RalfJung]

0x1 is obviously not even a valid 1-byte allocation

Because why? Could have been allocated by something else. AFAIK the only address that will never be in-bounds is 0x0.

Or are we now talking about the code in libstd again, and some some unknown code that might make extra assumptions about the platform it is running on? (You seem to jump between talking about different pieces of code, and I have a hard time following.)

If zero-sized allocations can't overlap with stack addresses, there's no valid execution in which y_addr is 0x7fffffff - you would have already gotten UB when you dereference the zero-sized pointer.

This is based on "cannot guess stack addresses", which is an extremely fuzzy part of the semantics and hard to say anything precise about. Also you assume that dereferencing a pointer to a ZST is not a NOP. It currently is a NOP, and IMO that makes lots of sense. If it's not a NOP, it would still have to be a special case in load and store because unlike non-ZST accesses, it does not require the address to be dereferencable. Given that we need a special case, the most sensible definition I can think of is to make it a NOP. And if we accept that, then your example doesn't work any more.

We can have the semantics in which physical pointers have deferred bounds checking and there is no way to check whether zero-sized pointers point to a valid zero-sized allocation (in which case, zero-sized allocations have no effect), or we can have a world when there is such a way and there are zero-sized allocations. In both cases, align_of would work, as long as you don't alias the stack.

Now you lost me entirely. Why does align_of come up? Also note that making bounds checks on getelementptr deferred is not optional -- if we choose to perform immediate bounds checks instead, getelementptr can no longer be reordered with alloc/free, so it can no longer be reordered with unknown function calls, and that's something LLVM does.

[jturner314]

So this is still illegal

Ah, yes, I forgot about .wrapping_offset().

I haven't had a chance yet to ask about this question on the LLVM mailing list.

I just realized that even if Vec is okay, we need to update the docs for std::slice::from_raw_parts and std::slice::from_raw_parts_mut to indicate that the caller must ensure that it's safe to .offset() the provided pointer by zero bytes. (Otherwise, the caller could provide an out-of-bounds pointer constructed by .wrapping_offset().)

[RalfJung]

we need to update the docs for std::slice::from_raw_parts and std::slice::from_raw_parts_mut to indicate that the caller must ensure that it's safe to .offset() the provided pointer by zero bytes

Good catch. Yes. Phrasing this in a way that's not confusing will not be completely easy.

Do you want to give it a try?

[comex]

Eugh… that sounds like a really arcane rule to have to put in the documentation. I guess it's not unreasonable, since even if you're intentionally creating an invalid pointer for a zero-sized type, it's hard to think of a reason you'd pick such a convoluted path to create it – that is, starting with a valid object and wrapping_offset'ing it out of bounds. (Passing a valid object that later gets freed would also count, right?) But it's still something people are going to have to wrap their heads around, before realizing it doesn't affect what they're doing. And it hardly seems necessary. Why can't the semantics just make an exception for offset(0) and make it a nop?