Interaction of isize / usize with value layout

[gnzlbg]

EDIT: I'm recycling this issue to track how isize and usize's layout interact with value layout in general. The old comment can be read below.

The reference of isize/usize currently documents the limits of the current implementation in a non-normative way:

• the maximum value size is isize::max_value(),
• the maximum number of elements in an array is usize::max_value(),
• the largest pointer offset is usize::max_value().

These limits are unspecified (not implementation-defined), that is, we don't guarantee anything about these and the Rust implementation does not have to document them at all.

Changing these to either implementation defined, or to some guarantee that all implementations must satisfy probably would require an RFC on its own that answers the questions:

• What's the size of the largest Rust value?
• What's the length of the largest Rust array / slice ? Do we differentiatiate between array / slices to ZSTs and non-ZSTs ?
• What's the largest pointer offset ?

These limits could be implementation-defined, unspecified, or set to some value that all implementations must uphold (isize::MAX, usize::MAX, etc.). And the trade-offs involved here are, among others, the kinds of code-generation backends Rust can easily support (e.g. LLVM and GCC limit some of these to isize::MAX, although these might be worked around), the kinds of optimizations these backends can do, and language complexity (e.g. how easy it is for users to write portable code, etc.).

---

old comment:

Layout isize/usize

The current reference says that the layout of usize determines the maximum size of Rust objects (size_of and size_of_val return usize), the maximum number of elements in an array ([T; N: usize]), and how much a pointer of a certain type can be offseted. It also says that the maximum size of any single value must fit within usize to ensure that pointer diff is representable.

There are two issues with this:

• unclear what's meant by "offseted". Pointer add operates on usize, but pointer offset operates on isize. If by "offseted" we mean ptr.add we should probably be more explicit about this.

• contradiction: we state that the layout of usize determines the maximum size of an object, and then argue that this is to ensure that pointer diff is representable, but AFAICT if the maximum size of an object is larger than isize then pointer diff will overflow and is not representable. IIRC @nikomatsakis argued that currently all Rust objects can be at most isize::max_value() large because of this, but this is not what the text says.

[RalfJung]

Yeah, that statement in the reference is incorrect. The maximal size of an object, even of an allocation, in LLVM is isize::MAX. Cc @rkruppe

[gnzlbg]

Is isize::MAX is also the maximum number of elements that an array can have? AFAICT not necessarily (e.g. an array of ZSTs is able to have usize::MAX elements without issues).

I wonder whether these are things that we should just "document" vs "guarantee".

[gnzlbg]

So I chatted with @eddyb and they recommended also pinging @sunfishcode to ask whether Cranelift has these limitations as well.

@eddyb recommended not guaranteeing this, the maximum object size should be implementation-defined, and we identified the need for an intrinsic to compute the offset of a field within a struct, similar to C's offsetof intrinsic, which returns the offset as an usize (this would allow the maximum object size to be usize::MAX). ptr.offset_from is intended to be bidirectional (which is why returns isize) and is not intended to be used to compute field offsets.

EDIT: it seems that the need for offset_of is not new: rust-lang/rfcs#2421 , https://internals.rust-lang.org/t/discussion-on-offset-of/7440, https://internals.rust-lang.org/t/pre-rfc-add-a-new-offset-of-macro-to-core-mem/9273, https://internals.rust-lang.org/t/pre-pre-rfc-field-offsets/7845, etc. A lack of offset_of should not motivate guaranteeing all objects to be limited by isize::MAX.

[hanna-kruppe]

In my book offset_from and related concerns are not why allocations can't be larger than isize::MAX. Instead, the first-order reason is that we can't use inbounds GEP instructions in the translation to LLVM: the inbounds requires that the address calculation does not wrap in signed arithmetic. There are multiple reasons for why LLVM wants that and I'm not sure if I can do them justice, but in any case it's useful for enabling optimizations at IR level and at codegen level, so it seems like something that's generally a reasonable restriction for optimizing compilers, not a LLVM-ism. Indeed GCC doesn't support object sizes larger than isize::MAX either.

[gnzlbg]

I'm not very familiar with GEP, but can't we just pass it wider signed integer types as offsets? E.g. if the base pointer is an unsigned i64, instead of using signed i64 offsets can't we use signed i128 offsets?

[RalfJung]

Is isize::MAX is also the maximum number of elements that an array can have? AFAICT not necessarily (e.g. an array of ZSTs is able to have usize::MAX elements without issues).

Agreed, arrays of ZSTs can have usize::MAX elements.

I'm not very familiar with GEP, but can't we just pass it wider signed integer types as offsets? E.g. if the base pointer is an unsigned i64, instead of using signed i64 offsets can't we use signed i128 offsets?

No, LLVM fixes the offset to be isize, basically. In hindsight this looks like a design mistake to me, but well, here we are.

[gnzlbg]

So #98 should now fix this issue. It document these things as implementation-defined, mentioning that the upper limit on object size, array length, and pointer offset is usize::max_value(). It then documents these implementation-defined limits for the current implementation (isize::max_value() for object size, and usize::max_value() for the others).

Instead of making array length and pointer offset implementation defined, we could guarantee that usize::max_value is always ok - but we can always add that guarantee later AFAICT. cc @eddyb

[hanna-kruppe]

I believe there's two distinct open questions here:

1. Do we want to lift this restriction at all in some implementations? It's far from obvious to me that we do, it enables some optimizations and AFAIK has never actually been an issue for any programs except deliberately pathological toy ones. Even if e.g. Cranelift doesn't actually do anything that benefits from limiting allocation sizes, it may not be worth the conceptual complexity of carrying around another implementation-defined parameter.
2. If we wanted to, how could do that even for the LLVM backend? Larger integer types don't work off the bat as @RalfJung said, but even if they did I think it would be a bad idea: using larger-than-native integers invites tons of potential for code quality problems. What would work today is simply not emitting inbounds. We'd lose the other aspect of inbounds, that the resulting pointer is poison if it would be out-of-bounds, but it's unclear how useful that is (even ordinary GEP without inbounds has provenance rules that give a fair amount of aliasing information). But in any case we could also try to salvage it by changing LLVM to separate the two aspects, e.g. splitting off the signed overflow part into an nsw flag.

[gnzlbg]

So I've just documented in #98 what the implementation currently does, but the behavior remains unspecified.

Guaranteeing anything about the maximum size of Rust objects is something that's probably worth doing on its own RFC (see the top comment for a brief summary). It would be nice to make progress towards that, and we can keep discussing the trade-offs here, but I feel that it is not worth blocking an MVP of the UCGs RFC on this issue so I'm tagging this as such.

[gnzlbg]

@rkruppe

Do we want to lift this restriction at all in some implementations? It's far from obvious to me that we do, it enables some optimizations and AFAIK has never actually been an issue for any programs except deliberately pathological toy ones. Even if e.g. Cranelift doesn't actually do anything that benefits from limiting allocation sizes, it may not be worth the conceptual complexity of carrying around another implementation-defined parameter.

I agree that the pathological toy programs, e.g., that create arrays with usize::MAX elements just to see the compiler fail, are worth fixing. There is unsafe generic code in the standard collections trying to prevent UB even when users do so, which I think is more interesting.

There, whether the limit can actually achieved in practice on a particular platform (e.g. due to LLVM, lack of memory / stack space / etc.), or whether the limit is usize::MAX or isize::MAX, might not be as relevant for unsafe code writers as the fact that there is a limit that they want their unsafe code to be robust against (e.g. Vec and the other collections contain code to handle these limits).

---

@joshtriplett @briansmith Another constraint when choosing Rust largest object size is being able to map to all C types in C FFI.

With usize = uintptr_t, and if we fix the largest allowed layout to usize::MAX, then because uintptr_t can be larger than C's size_t, then repr(Rust) types can be larger than repr(C) types. AFAICT this is ok, we'll just have to enforce an extra layout constraint for repr(C) types (e.g. that their size is at most size_t::MAX). CHERI would be such a platform (size_t = u64::MAX and uintptr_t = u128::MAX).

OTOH if we fix the maximum allowed value size to isize::MAX, then there is a subset of C types (those with a larger size) that we can't interface with via C FFI. This might be a trade-off worth making, e.g., if choosing isize::MAX simplifies Rust unsafe code, or if the usize::MAX strategy is not implementable.