Validity of references: Bit-related properties
Closed this issue · 17 comments
Discussing the "bit-pattern validity" of references: the part that can be defined without referring to memory.
Certainly, references are non-NULL. Following the current lowering to LLVM, they also must be aligned. This is in conflict with creating references to fields of packed structs, see RFC 2582 for a proposed solution.
Do we want to allow uninitialized bits? Theoretically we could allow something like 0xUU000001 (on 32bit, where U represents 4 uninitialized bits) for &(), but there seems to be little point in doing so.
What does "aligned" mean for unsized types, where we might have to use the metadata to actually determine the alignment? For unsized types, the "actual" alignment isn't just a bit-level property. But we still have a "least required alignment" (whatever layout.align says for such types), and we could just use that?
For, &(u32, dyn Trait) would have to be 4-aligned if we just look at bit-related properties, even though the actual type implementing Trait could make higher requirements.
Certainly, references are non-NULL. Following the current lowering to LLVM, they also must be aligned.
Yes.
Do we want to allow uninitialized bits?
Absent a compelling reason to do so, I think we should forbid them for now.
Also see prior discussion at rust-lang/rust-memory-model#10 and rust-lang/rust-memory-model#12.
Summary from #77 (comment) and previous comments:
On some platforms (e.g. x86_64-unknown-linux-gnu) virtual address space available to userspace is limited such that several of the high bits will always be zero. Where exactly that limit is is a bit fuzzy due to advancements in processor technology and kernel features (sysv ABI and kernel documentation say 47bits for backwards compatibility, anything higher is opt-in), but saying that the upper half belongs to the kernel should be fairly conservative and forwards-compatible. So applying a platform-specific restriction to the bit patterns of references could make an additional 2^63 niche values available.
These niches would be much easier to use compared to alignment-based ones since they do not depend on the pointee type.
The only open question here is if this could also be applied to &ZST since they're not subject to virtual address space limitations, i.e. if there's anything safe today that would generate references to ZSTs that are > isize::MAX. #102 seems relevant.
The only open question here is if this could also be applied to &ZST since they're not subject to virtual address space limitations, i.e. if there's anything safe today that would generate references to ZSTs that are > isize::MAX.
I am not sure about "anything safe", but as of right now, the following code is certainly sound, so your proposal would be a breaking change:
fn mk_unit() -> &'static () { unsafe {
&*(usize::MAX as *const ())
} }Yeah, the question is whether that would be acceptable. If not then the optimization can only be applied to non-ZST references, which loses some of the simplicity, but it's still more powerful than the alignment niches since it would also apply to align(1) types.
Reguarding uninitialized references. I've mentioned lccc on issues here before, so I'll skip the large details.The two things that apply here, if you create a value with an uninitialized byte, the entire thing is uninitialized and types with validity requirements or pointers with non-trivial validity attributes cause uninit to become invalid (which is UB to even create) on reads and writes. Because references have validity requirements (both trivial and non-trivial), they aren't allowed to be uninitialized ever on read or write at the very least. For these reasons, unless there is a compelling reason to allow uninitialized values or bits, I would strongly oppose allowing uninitialized values (including partially uninitialized values) of reference types. This is, of course, particularily the case because of the non-trivial validity requirements (dereferenceable/dereference_write, readonly, and noalias, in the case of references), so a trivially valid representation may not be a valid one (and there is no way to prevent it, because the representation of any completely valid reference also represents a non-trivially valid reference of the same type).
Yeah, I don't think anyone would suggest that uninit memory should be valid for references -- as you noted, that is in conflict with the requirement of being non-null and well-aligned. (I don't know what "non-trivially valid" etc mean, but I think I am getting the gist of what you are saying.)
Note that even for types where all initialized bit patterns are valid, there are good reason not to make uninitialized memory valid. I view uninitialized memory as a separate possible value memory can have, so the decision whether it is valid ought to be made separately (with the one restriction that if uninit is valid, then everything should be valid).
Non-trivially valid refers to attributes like dereferenceable. Things that cannot be proven by a bit-level inspection of the type, and therefore are not trivial to prove. Likewise trivially valid means bitwise valid. This also extends to uninit bytes, as I said, lccc takes an all or nothing approach to uninit (but see C for an exception for non-scalar types).
In the case of the high bytes, I think it may reasonable to have an implementation defined region of high bytes or bits that must be 0. On 65816, I have imposed a requirement that all pointers have a 0 in the most significant byte (previously the byte was padding and thus indeterminate) for compatibility with extensions that extend the effective address space to 32-bit from 24-bit (using, for example, bank switching). Allowing the invention of large pointers like that would be future incompatible with such extensions as it would cause a breaking change (suddenly accessing these pointers causes a bank switch). By technicality this would extend to ZST references because they are pointers, according to the ABI. (Though this wouldn't necessarily cause an issue if usize is allowed to be 24-bit 0 extended to 32-bit)
In the case of the high bytes, I think it may reasonable to have an implementation defined region of high bytes or bits that must be 0. On 65816, I have imposed a requirement that all pointers have a 0 in the most significant byte (previously the byte was padding and thus indeterminate) for compatibility with extensions that extend the effective address space to 32-bit from 24-bit (using, for example, bank switching).
Interesting, thanks for bringing this up.
I think I am missing something though: how does disallowing these pointers help with enabling such extensions? It seems to me like it makes the extensions impossible because the pointers they need are not valid? Putting it differently, doesn't such an extension require pointers with non-0 high bits?
That's actually an interesting point. The restriction is primarily for users, who could not rely on the byte being non-zero not causing breaking changes on new platforms (however, a similar argument could be made that the users could rely on the upper byte being zero).
The primary this is that any code that was compiled prior to such an extension would necessarily have to be recompiled, so an ABI breaking change is less of an issue than user-facing breaking change. That's the primary rationale for the restriction (it was also made because previously the byte was indeterminate, but for specially tagged pointers and function pointers, it must be zero, so the two were unified to always require the high byte be 0. The latter because pointer to member functions from C++ are fun.).
The specific wording is:
All passed and static normal pointers are treated as 4-byte values. The pointer value is 0-extended to the full four bytes.
who could not rely on the byte being non-zero not causing breaking changes on new platforms
That's a few too many negations for me to understand.^^
it was also made because previously the byte was indeterminate
Are you talking about C/C++ here? While it is good to know what other languages do, we should not just blindly copy that, so this is not really a satisfying answer when it comes to figuring out why this is needed / helps.
My naive understanding is that on those platforms, the allocator will only ever return pointers with their high byte 0, so every non-ZST dereferencable pointer already has this property anyway. And for ZST it should not matter, they never lead to any actual memory accesses anyway. So I do not understand how it would be useful to specifically rule out non-zero high bytes for ZST references (that seems to be the only effect).
I am assuming here that raw pointers, which are permitted to dangle, do not have any such restriction.
Are you talking about C/C++ here
This is an ABI which supports, among others, C and C++. Rust also falls under it. It would, at the very least, be incompatible with extern"C" on the platform.
And for ZST it should not matter, they never lead to any actual memory accesses anyway.
Because ZST pointers are still pointers, they are still 3-byte values 0 extended to 4 bytes according to the ABI (this is the source of the requirement).
Oh, so the ABI actually loses the high byte when a pointer is passed from one function to another? Presumably this would also affect raw pointers? In that case this would not be about references only, so it should be its own thread of discussion. This also puts into question things like usize (looks like it would need a u24 type or so^^).
so it should be its own thread of discussion
It was supporting a discussion on this thread so that's why I brought it up here (it probably could be brought to its own thread)
Oh, so the ABI actually loses the high byte when a pointer is passed from one function to another
In the model, pointers are only 3 bytes: a low byte, a high byte, and a bank (the same as hardware pointers on the 65816, though represented in 4 bytes). If a language did make use of all four, yes it would have to drop this high byte, particularily if it passed it to a different translation unit.