Clarify offset safety rules

[joshlf]

According to the nightly offset docs, in order to avoid UB, "both the starting and resulting pointer must be either in bounds or one byte past the end of an allocated object."

However, it's not clear to me what constitutes an "allocated object." This confusion caused this issue about whether it's safe to use offset in the implementation of an allocator.

cc @kennytm @gankro @japaric @ezrosent

[joshlf]

One way of looking at this might be: does "allocated object" mean "allocated by any Alloc implementation" or "from the heap", or something else entirely?

[Gankra]

I think the precise definition depends on memory model work, but my intuitive model is "thing you got from malloc".

[jonas-schievink]

Note that stack allocations are fine as well

[joshlf]

I think the precise definition depends on memory model work, but my intuitive model is "thing you got from malloc".

I'm curious about this definition because I can't imagine how Rust or LLVM would formalize the notion of an allocation. Does anybody know what LLVM offset is implemented in terms of? I tried to look for the intrinsic implementation in the compiler but I'm not familiar with where those are in the compiler source, and I couldn't find it by grepping.

[jonas-schievink]

@joshlf You're looking for this part of trans:

rust/src/librustc_trans/intrinsic.rs

Lines 198 to 202 in 0701b37

	"offset" => {
	let ptr = llargs[0];
	let offset = llargs[1];
	bcx.inbounds_gep(ptr, &[offset])
	}

So basically, the invariants of getelementptr inbounds must hold.

[joshlf]

Awesome, thanks so much @jonas-schievink !

I'm still a little unsure of what the semantics are, though. Quoting from that link:

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.

I'm not sure on how LLVM defines "allocated object." Do you have any insight on this?

[jonas-schievink]

I don't, sorry. Not really an LLVM expert.

[steveklabnik]

@rust-lang/lang and/or @rust-lang/compiler , some guidance here on the wording would be great. We could always just do what we do with aliasing and link to that LLVM page, but that's not as great.

[cramertj]

Someone who knows more about LLVM could probably answer this better, but I'd expect that LLVM is using "allocated object" to mean that the starting and resulting pointer must both point to memory that can be legally dereferenced (without e.g. segfaulting). I'd imagine LLVM is using this additional knowledge to know that it can safely prefetch the memory behind the pointer.

Edit: I was wrong! See below.

[Gankra]

No, I don't think the important part is that the result can be accessed right away, but rather that the pointer doesn't point at something seemingly unrelated. I believe this condition is designed to avoid having to treat every pointer offset as "welp, now it can point to anything, give up on all alias analysis".

For instance, if I modify an element of a Vec, it sure as heck shouldn't invalidate the values of my local stack variables! But without [inbounds], it technically could.

[hanna-kruppe]

Yeah @gankro is right. Code like this is UB:

let x: u8 = ...;
let y: u8 = ...;
// assume &x as usize < &y as usize, to avoid worrying about wrapping in the offset calculation
let ptr_to_y = (&x as *const _).offset(&y as usize - &x as usize);

(even if the x and y are actually allocated right next to each other at runtime)

[cramertj]

That makes sense-- thanks for the clarification!

[Dylan-DPC]

Revisiting this as part of a triage run. There is a link added to the docs which links you to this part. So it should be fine to resolve this issue and if anything is lacking, a new issue might be a better idea than this being buried deep into the issue tracker.