Closed RalfJung closed 11 months ago
It's been a week and there were no comments. Let's go then. @rfcbot merge
Team member @RalfJung has proposed to merge this. The next step is review by the rest of the tagged team members:
Concerns:
Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!
See this document for info about what commands tagged team members can give me.
I have a concern about the case
ptr1.offset_from(ptr2) is always defined when ptr1.addr() == ptr2.addr().
Shouldn't this say that ptr1
and ptr2
have the same provenance, or at least are from the same allocation? Because I would assume the compiler wants to deduce that from this comparison, and IIUC this is in the documentation.
not sure if I know how to do this:
@rfcbot concern offset_from-different-allocations
:bell: This is now entering its final comment period, as per the review above. :bell:
Nice race condition.
Shouldn't this say that ptr1 and ptr2 have the same provenance, or at least are from the same allocation? Because I would assume the compiler wants to deduce that from this comparison, and IIUC this is in the documentation.
That would be equivalent to not having any special case for when the two pointers are the same. I thought if we have a special case for offset 0 then we would want a matching special case for offset_from -- but maybe that's not a good idea?
The restriction arises because:
const
. But in const
, two pointers from different allocations can never have the same address, so this new case changes nothing.ptrdiff
operation with suitable restrictions does not "leak" the base address of a pointer, which could be helpful for analyses. I am honestly unsure if this is preserved under my proposed change, so maybe you are right and we should keep the offset_from
spec unchanged...Can we use "ptr1.offset(n) is well-defined with result ptr2" if and only if "ptr2.offset_from(ptr1) is well-defined with result n" as the defining property? I originally thought no, but I just realized this is a lot more subtle. It depends on our notion of equality on pointers. If it's "full equality including having the same provenance", then that property is already busted, since we allow ptr2.offset_from(ptr1)
when both are in the same allocation even if they have different aliasing tags. So we probably want to consider "pointers with their provenance reduced to just the allocation", or some such thing? I honestly don't remember what I was thinking... But if we go with that, then what would the spec be that achieves that property? I think it has to be "they must be to the same allocation, and either at the same offset or both in-bounds". That's a weird spec though? Or maybe not, for the "no provenance" case that's already what we do! What do you all think?
But I tend to agree, we want to keep the "same-allocation" restriction.
Is it legal to use offset_from
when the pointers have the null provenance? My initial reading was that your argument was that assuming this is the case, provenance monotonicity forces us to allow offset_from
for pointers with arbitrary different provenance. But maybe we can just say that offset_from
on null provenance is always UB, even when the pointers have the same value.
Is it legal to use offset_from when the pointers have the null provenance?
What is the null provenance? If you mean "no provenance", then the answer is "yes but only if both pointers have no provenance, and they point to the same address". I think we should keep that. Basically if we allow a pointer to be deref'd for n
times the pointee size (for a non-zero-sized pointee) then ptr.offset(n).offset_from(ptr)
must always return n
(and never be UB), IMO. For n = 0
, this implies we must allow ptr::null::<u8>().offset_from(ptr::null::<u8>())
and have it return 0.
I have updated the proposal to say that
ptr1.offset_from(ptr2)
has the following requirements when ptr1.addr() == ptr2.addr()
:
ptr::invalid
and ptr::null
)The offset_from
spec remains unchanged compared to today when ptr1.addr() != ptr2.addr()
.
I have also removed the references to that offset
/offset_from
property, I don't think it holds with more complicated provenance anyway so I don't really know what I was thinking there...
Doesn't this break provenance monotonicity? Is "the provenance used by ptr::null" not the bottom of the provenance preorder?
Oh, right... we have to allow the case where one side has no provenance and the other side has some alloc's provenance.
Ah no I've finally re-traced the steps that led me to the original spec. We need to allow arbitrary provenance mismatches. If we start out with both pointers having no provenance, then provenance monotonicity says that we can add provenance A to one pointer and provenance B to the other pointer and the call must still be allowed.
So I take it you agree with my previous message? I think I just gave that argument. But AFAIK we don't need to allow offset_from
when both values have no provenance, and without that the monotonicity rationale breaks down.
EDIT: Actually I see you addressed this in https://github.com/rust-lang/unsafe-code-guidelines/issues/472#issuecomment-1793758438 . In which case I'm satisfied with the rationale.
I think I just gave that argument
Yeah sorry, I didn't understand your message properly initially.
But AFAIK we don't need to allow offset_from when both values have no provenance, and without that the monotonicity rationale breaks down.
I think we at least "need to" do that in terms of backwards compatibility. Miri and const-eval currently allow it, and we generally allow zero-sized accesses of non-null pointers without provenance arguing that "it's as if there was a zero-sized allocation there". It follows that offset_from
should also work, since things are in-bounds of that zero-sized allocation.
But also beyond that it seems pretty necessary. If you want to represent an iterator as a begin and end pointer, and not allocate memory for when there are no elements, you'll use NonNull::dangling
as the begin and end pointer. But we'll still want to allow using offset_from
to compute how many elements are left in the iterator.
@rfcbot resolved offset_from-different-allocations
:bell: This is now entering its final comment period, as per the review above. :bell:
Zero-sized accesses (reads and writes) are always allowed with every pointer.
An interesting thing I’ve recently learned: WebAssembly does the opposite, it traps on zero-sized out of bound accesses:
Our zero-sized accesses do not even reach LLVM, let alone wasm, so I think that shouldn't be a problem.
Does this cover references to zero sized types (and zero-sized DST references) with the exception of null (which is a validity invariant of &T
in general)?
Only indirectly. This proposal affects the definition of "dereferenceable", where now any pointer is dereferenceable for 0 bytes. The validity invariant for references is defined in terms of "dereferenceable", so it changes accordingly.
Looks like LLVM only has dereferenceable(N)
for positive N
, so the question of dereferenceable(0)
does not come up there. So from a Rust perspective I guess we can conclude that any pointer is dereferenceable for 0 bytes, even null. (This feels strange, I admit -- but it is consistent with allowing the null pointer to be inbounds-offset by 0 bytes.)
I think that if references are included, that should be explicit, rather than simply implied from the rule for pointer reads.
Obviously we can't say that a null reference is valid for ZSTs, because &T has a stable niche at null, regardless of T.
I have added the following:
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.
The final comment period, with a disposition to merge, as per the review above, is now complete.
As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.
This will be merged soon.
Awesome, thanks all! I opened a tracking issue for the implementation of this: https://github.com/rust-lang/rust/issues/117945.
(Mostly for my own curiosity.)
Regarding the offset_from bits, wouldn't the new offset_from
preconditions mean the compiler can no longer transform end2 = begin.offset(end.offset_from(begin))
into end2 = end
? end2
will have begin
's provenance and, a priori, the compiler may not know that end
and begin
share provenance. With the tighter precondition, offset_from
is enough to infer this. With the new precondition, the compiler needs to know that end.offset_from(begin) != 0
, which may not be generally true, otherwise we might have hit the same address case.
Not sure how important that is transform is in practice, but it isn't completely random: this is converting back and forth between the pointer pair and pointer + length representations of a slice. Or, in other words, what happens if you call iter.as_slice().iter()
on a std::slice::Iter
. If iter
's creation was too far away, the compiler may not know end
and begin
were related.
That precondition and provenance monotonicity seem to just be in conflict though, if I'm understanding that property correctly. :-/ If you're always allowed to add provenance to a pointer, and the "add provenance" operation is allowed to add arbitrary provenances inconsistent with the pointer address, you might start with two dangling
s, add different provenance to each, and then attempt to offset_from
.
@davidben yes that sounds about right. And yes it is unfortunate but I also don't see an alternative. We could say that offset_from
on two pointers without provenance is just forbidden, i.e., they must have the same provenance and they both must have provenance. But that excludes legitimate uses involving empty slices.
This seems like a case where the "special zero-sized provenance" alternative actually has an advantage.
That said, you can still optimize this to end2 = begin.with_addr(end.addr())
, which removes the arithmetic (assuming with_addr
turns into some suitable primitive intrinsic).
I guess there is a point to be made for specifying the intrinsic behind offset_from
the way we document above (so we have provenance monotonicity in the op.sem), but then in the public library function that exposes the intrinsic, add some extra library UB for when the two pointers have different provenance. That would let us change the implementation later if we found a better way.
However, what should Miri do in that case? Usually we only implement language UB. Given that it's hard to reason about provenance, that would make this problem quite easy to miss. To represent this properly we'd need some sort of intrinsic that the library function can call to inform Miri that it'd like some extra checks on the provenance...
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-offsetoffset_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 whenptr1.addr() == ptr2.addr()
.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 ifptr.read()
is allowed (because they are both always allowed).For
offset_from
specifically, we need to deal withptr::invalid::<u8>(A).offset_from(ptr::invalid::<u8>(A))
being allowed forA != 0
(and maybe even forA == 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, andoffset_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, keepptr::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 withptr::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 ifoffset
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 thusptr::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 ifWe haven't discussed
offset
oroffset_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:
ptr::null::<T>().offset(0)
ptr: *const ()
, allowsptr.offset(_)
if and only ifptr.read()
is allowedHowever,
transmute::<_, *const ()>(4usize).read()
), which all else being equal seems worse than achieving it by making more things definedThere'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:
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.