Decide on zero-sized offsets and memory accesses #472

We have previously discussed that we want to make offset(0) always-defined, but never FCP's this decision. We also discussed zero-sized memory accesses, without reaching a clear conclusion. We never discussed the case of zero-offset offset_from.

I propose we resolve all these questions around zero-sized offsets/accesses as follows:

• ptr.offset(0) is always defined.
• ptr1.offset_from(ptr2) is always allowed when ptr1.addr() == ptr2.addr().
• Zero-sized accesses (reads and writes) are always allowed with every pointer.

We also adjust the definition of "dereferenceable for n bytes" to say that every pointer is dereferenceable for 0 bytes. This implies that any aligned non-null pointer is valid as a reference to a zero-sized type.

Together these ensure "provenance monotonicity": if something is allowed on a pointer without provenance, then adding arbitrary provenance to the pointer can never introduce UB. We also achieve that for ptr: *const (), ptr.offset(_) is allowed if and only if ptr.read() is allowed (because they are both always allowed).

For offset_from specifically, we need to deal with ptr::invalid::<u8>(A).offset_from(ptr::invalid::<u8>(A)) being allowed for A != 0 (and maybe even for A == 0, see the next section). This means it must still be allowed when we add arbitrary provenance to both pointers, including arbitrary different provenance.

If ptr::invalid returns a provenance-less pointer, then we already allow zero-sized offset/read/write on such provenance-less pointers, and offset_from as well if both pointers have no provenance and the same address, so the proposal is almost the obvious result of applying "provenance monotonicity closure" to the current semantics: keep everything allowed that we currently allow, keep ptr::invalid unchanged, and allow enough additional cases such that provenance monotonicity holds.

Null pointer

This proposal is almost, but not exactly, the provenance monotonicity closure of the current semantics. There is one further change that does not fall out of provenance monotonicity closure:

ptr::null::<()>().read() is allowed, or more generally zero-sized reads/writes with the null pointer are allowed. Those could remain forbidden without violating provenance monotonicity. We allow them for consistency with ptr::null::<T>().offset(0), which we decided to allow, and which in particular C++ (but not C) allows -- having more UB than C++ without a good reason seems like a bad call, and if offset considers 0 bytes to be "in-bounds at the null pointer", then it seems only fair that reads/writes do the same. References still must be non-null, and we assume that null is never in-bounds of a non-zero-sized allocation, so non-zero-sized accesses at null remain UB regardless of whether that memory is mapped or not. This issue is concerned with zero-sized offsets/accesses only, so changing the rules for any other kind of access is out of scope.

There is one downside to this: we can no longer infer "nonnull" from a read/write having happened on a pointer, unless we know that the size of the access was non-zero. However, we can infer "nonnull" for references in general, and we have NonNull to express non-null-ness of raw pointers, so code can still steer the compiler in the right direction if it has to. Furthermore, the size is generally known post-monomorphization, so all the non-null reasoning LLVM does based on a pointer being used for memory accesses is still valid.

Alternative proposal

All that said, there is an alternative proposal that achieves provenance monotonicity. It considers there to exist some dedicated provenance that covers "zero-sized accesses at every location". Let's call this the "zero-sized provenance". ptr::invalid (and thus ptr::null) would be changed to return a pointer with that special provenance. Int-to-ptr transmute would still yield a pointer without provenance. Zero-sized accesses are then allowed if

• the pointer has the zero-sized provenance
• or the pointer has a regular provenance of a live allocation and the address is in-bounds of that allocation

We haven't discussed offset or offset_from under this proposal, but presumably we'd use similar rules: offset(0) is UB on pointers without provenance but allowed on pointers with the zero-sized provenance. On pointers with regular provenance it requires the pointer to be in-bounds. offset_from would be UB if either pointer has no provenance; if they both have the zero-sized provenance then it's allowed if they have the same address; otherwise they must both have regular (non-zero-sized) provenance of some live allocation and be in-bounds of that allocation.

This proposal:

• allows the optimization discussed in the meeting, assuming allocations cannot shrink
• achieves provenance monotonicity
• allows ptr::null::<T>().offset(0)
• for ptr: *const (), allows ptr.offset(_) if and only if ptr.read() is allowed

However,

• it achieves provenance monotonicity by making more things UB (for instance, transmute::<_, *const ()>(4usize).read()), which all else being equal seems worse than achieving it by making more things defined
• it needs a new intrinsic to create pointers with the zero-sized provenance

There's a variant of this proposal which has not one zero-sized provenance but one such provenance for each address; in that case the pointer is in-bounds for 0 bytes only if it points to that address. This is equivalent to having a zero-sized allocation at every address exist at program startup. This model disallows even more code (for instance, ptr::invalid::<()>(4).byte_add(4).read() becomes UB).

Summary

Overall this means we have a design space of (at least) 6 models:

• zero-sized-accesses-are-nops
• zero-sized-provenance-global
• zero-sized-provenance-per-address

and each of them with or without allowing zero-sized null pointer reads/writes. (I'm assuming it as a given here that we do want to allow zero-sized null pointer offsets and offset_from of the null pointer with itself.)

The two zero-sized-provenance models avoid having a "lattice" of provenance with a non-trivial bottom element: the bottom, "no provenance", just doesn't allow anything at all. OTOH it needs the new concept of a zero-sized provenance (or memory pre-initialized with many zero-sized allocations), making the theory more complicated as well. The main proposal being suggested here make the "bottom" provenance support zero-sized accesses anywhere, thus making the provenance lattice less canonical but avoiding a dedicated "zero-sized provenance".

In the meeting people generally weren't convinced by the one optimization example we have that is enabled by the extra UB in the zero-sized-provenance models (in particular since it is incompatible with shrinking allocations). Using zero-sized accesses/dereferenceability as an optimization signal is not clearly a good idea, and when it comes to UB, implicit/unintended signals are dangerous. Provenance as a concept is already deeply mysterious to many programmers; making it more complicated by introducing imaginary provenance for the zero-sized case (with the penalty of misunderstandings being UB) does not seem advisable. The example could be rewritten to use n.max(4) as the length, which would make the assumption that the length is at least 4 explicit (but of course, the programmer might not know that they have to write this to get all the optimizations).

So, because of all of that, I think we should go with the model that has the least UB. I'll wait a bit before starting FCP to see whether people have any new points they'd like to see added to this summary.