Guarantee that `heap::EMPTY.offset(0)` has defined behaviour

[Gankra]

Currently we have an awkward situation where heap::EMPTY (1 as *mut _) is frequently used to represent zero-sized types or other "non-allocations". It is often desirable to offset-by-0 from this in general code to avoid complicating things with special-cases for ZSTs or empty array iterators.

Unfortunately it is possible to interpret the LLVM GEP docs to determine that heap::EMPTY.offset(0) (which is marked as inbounds unconditionally) has undefined behaviour, because heap::EMPTY is not actually allocated. I see two ways forward for this: mark heap::EMPTY as allocated in some way for LLVM, or ensure offset(0) is always safe. I favour the latter, simply because it's plausible to want to offset by 0 off some other ptrs. However the former is acceptable if this is not possible.

[Gankra]

CC @Aatch @dotdash

[huonw]

The LLVM docs can't be talking about literal malloc allocations, since e.g. one can perfectly well index into static data.

[Gankra]

"allocated" is just the actual terminology they use in the documentation. I have no idea what it properly entails (LLVM vagueness prevails).

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. In cases where the base is a vector of pointers the inbounds keyword applies to each of the computations element-wise.

(emphasis mine)

via http://llvm.org/docs/LangRef.html#getelementptr-instruction

[Gankra]

I can't imagine heap::EMPTY is allocated by any reasonable definition, though.

[huonw]

Yes, I know the terminology used by the docs, in just pointing out that one has to be careful to avoid conflating it with malloc (doing so is something I've seen happen a lot in this sort of discussion).

In any case, due to the zero size, I think there are definitions of allocated which work fine with EMPTY.

[huonw]

(One way to guarantee this would be to lower offsets on zero sized types to a noop.)

[Gankra]

Special-casing ZSTs covers half the usecase, but it doesn't cover creating the iterator for a empty slice of non-ZSTs.

e.g.

let vec: Vec<u8> = Vec::new();
for i in vec { .. }

where Vec::new sets ptr to heap::EMPTY and Vec's iterator code (for non ZSTs) amounts to:

let mut start = vec.ptr;
let end = start.offset(vec.len); // does this work if vec.ptr == heap::EMPTY and vec.len == 0?
while start != end {
  let elem = ptr::read(start);
  // ... use elem
  start = start.offset(1);
} 

[Gankra]

CC @pczarn and #24604

[dotdash]

Adding a zero check to every offset operation seems bad. Vec should probably add a special case for zero length as done in #24604, and if you want to just mess around with possibly "invalid" pointers, there's the arith_offset intrinsic that uses GEP without the inbounds modifier.

[Gankra]

I was more hoping at codegen time we could just convince LLVM that everything's alright (or possibly someone with a better understanding could simply determine that this isn't actually a concern -- certainly LLVM doesn't seem to actually produce UB when we do this today). A check on every offset is definitely a non-starter.

[bluss]

sdf Edit: that's right.

[Gankra]

@bluss That discussion doesn't seem relevant to ptr::offset?

[Gankra]

I talked this out with @sunfish on IRC. Evidently allocation is a very abstract concept for LLVM where it's basically "as long as you're consistent it's cool". This means that we can pretend heap::EMPTY is an allocated ZST without telling LLVM anything, and so offset-by-0 is legal since that's 1-past-the-end.

However offset-by-0 off heap::EMPTY as *mut T is not sound in general as if e.g. T is a HugeStruct it could actually alias with some real allocated memory somewhere.

Therefore we don't need to worry about ZSTs (yay!) but do need to care about empty arrays. As such I'm closing this as basically resolved.