Support index size != pointer width

Preliminaries

usize is the pointer-sized unsigned integer type [1]. It is also Rust's index type for slices and loops; this definition works well when pointer size corresponds to the space of indexable objects (most targets today). Informally, uintptr_t == size_t.

Note that the target pointer width is indisputably set by the LLVM data layout string. It would be correct to say that it is currently impossible to have usize different to target_pointer_width without breaking numerous assumptions in rustc [2, 3].

Unfortunately, uintptr_t == size_t doesn't hold for all architectures. For context, I've worked toward (not active) compiling Rust for MIPS/CHERI (CHERI128) [4]. This target has 128-bit capability pointers (as in layout string), and a 64-bit processor and address space.

I also assume that we don't want programmers messing with pointers in Safe Rust, and that they shouldn't have to care how a pointer (or reference) is represented/manipulated by an architecture.

Problem

I think that more than one type is necessary here, to distinguish between the "index" or "size" component of a pointer (a la size_t), and the space required to contain a pointer (uintptr_t).

To me, the ideal solution is to change usize to be in line with size_t and not uintptr_t. As @briansmith notes, this would be a breaking semantic change. I claim that this is only problematic on architectures where uintptr_t != size_t. As such, code breakage from changing this assumption is constrained to targets where the code was already broken.

Why not have a 128-bit usize? This is technically feasible, and it's the basis of my compilation of Rust for CHERI. But:

Bounds checks explode from 2 instructions to 7. Yes, this occurs with optimisation on, but no, I haven't profiled it on real-world applications.
rustc tries to index into LLVM intrinsics such as memcpy with 128-bit integers. This isn't defined in the backend, and arguably shouldn't be defined. I will not be the last person to wonder why memcpy doesn't generate any instructions.
The address space is 64 bits. ptr as int gives an LLVM i64, which can't be cast/isn't comparable to an i128; again there is no good reason to manipulate 128-bit integers here. Likewise when calling inttoptr, which is a valid instruction even if the result can't be dereferenced [5].

It may not be necessary to define and expose a uintptr_t type. It's optionally defined in C; I'm not sure programmers want to use such a type, and it could be relegated to the compiler. I haven't thought about this seriously, though.

The key issue is the conflict between index size and pointer width. How can we resolve this conflict, and support architectures with index size != pointer width? (or: why isn't this a problem at all?)

Notes

[1] From https://doc.rust-lang.org/std/primitive.usize.html [2] As remarked by @gnzlbg in https://github.com/rust-lang/libc/issues/1400#issuecomment-502308097; this related problem is a bit subtle and quite complex. [3] It isn't clear (to me!) whether this is primarily a compiler implementation problem or a semantic problem, but that is not the subject of this issue. [4] This issue does not motivate support of a particular architecture, though there has been community interest in CHERI. [5] This is relevant when finding out the size of an object, for example. While generating instructions to extend or truncate the integers is possible, this seems a silly use of cycles at compile time (and possibly runtime). [6] My experience is limited to rustc (c. 1.35 nightly), libcompiler_builtins, libcore, and liballoc. Some modification was needed to make this work, but no egregious violations. [7] See CHERI Concentrate for an overview of the considerations. [8] In particular I'm not asking for help in porting Rust to CHERI, or any other platform. However, I would like support for other architectures to be technically possible.

(edits because I accidentally posted early)

Why not have a 128-bit usize? This is technically feasible, and it's the basis of my compilation of Rust for CHERI. But:

Thank you for this information, it is useful to be sure that the "simplest" solution isn't good enough.

think that more than one type is necessary here,

Agreed, otherwise, according to the information provided, we cannot technically support such targets properly.

Integers (usize) are never cast back to pointers and dereferenced. We already know this at some level (rust-lang/unsafe-code-guidelines#52).

Integers are casted back to pointers and subsequently dereferenced all the time. I think that what that issue shows is that doing so is ok (and therefore answering your question, provenance isn't a problem).

To me, the ideal solution is to change usize to be in line with size_t and not uintptr_t. As @briansmith notes, this would be a breaking semantic change. I claim that this is only problematic on architectures where uintptr_t != size_t. As such, code breakage from changing this assumption is constrained to targets where the code was already broken.

The problem is that we do guarantee that this safe Rust code is portable to all platforms that Rust supports and is correct (playground):

    let ptr: *const i32;
    let x: usize = ptr as usize;
    let y = x as *const i32;
    assert_eq!(ptr, y);

A lot of correct tricky unsafe code relies on this to work on all targets, and we guarantee that such code is portable. It is unclear to me whether we guarantee this for all platforms that Rust will ever support or for all platforms that Rust currently supports. Either way, I don't think the distinction is very important if we can find a good solution.

Note that we already allow ptr as {int} only if {int} has the same size as ptr. This means that if we make usize equivalent to size_t, on all current platforms, ptr as usize will continue to work forever and that on CHERI ptr as usize would fail to compile, but ptr as u128 would work.

So we could add the following new language feature:

add a new integer type (e.g. iptr for "int ptr" - bikesheds aren't very useful at this stage) that's guaranteed to be pointer sized to libcore (whether its a type alias, or a native type, is to be determined later)

With that, code that fails to compile on CHERI can be upgraded from ptr as usize to ptr as iptr such that it now works on CHERI while also working on all existing platforms.

If we ever wanted to be consistent about using iptr, we could warn on ptr as usize easily, and maybe in some future edition, even forbid it, requiring users to use ptr as iptr instead.

This might not be a backward compatible change, depending on whether this breaks the usize guarantee or not, but if that's a guarantee that we have to respect, then so is usize being the index type, and we can't support CHERI properly at all.

Alternatively, we could just define an iptr type alias in standard that's cfg'd to u128 for cheri and usize for all other targets, and use it consistently in the toolchain libraries to make sure that they compile. User code can do the same if they want to.

Drive-by note (I currently have no budget to dive deeply into this topic):

Note that we already allow ptr as {int} only if {int} has the same size as ptr.

That's not true.

Damn, thanks. So the reference doesn’t say what that does AFAICT, only that it is a pointer to address cast, but the address doesn’t fit, so I suppose it gets truncated?

I have some bandwidth to address this topic in rustc (i.e. implementation work), but I guess there's lots of people who need to know about the semantics.

A lot of correct tricky unsafe code relies on this to work on all targets, and we guarantee that such code is portable. It is unclear to me whether we guarantee this for all platforms that Rust will ever support or for all platforms that Rust currently supports.

I think this is a separate issue. Given that it's Safe Rust, I'd be cautious about proposing we restrict the guarantee to currently-supported targets. In any case, no problem with CHERI; casting integers to pointers is OK unless you dereference the result (much like Rust, except it also traps if you try to forge a pointer to a valid object).

This might not be a backward compatible change, depending on whether this breaks the usize guarantee or not, but if that's a guarantee that we have to respect, then so is usize being the index type, and we can't support CHERI properly at all.

One of the big questions in this issue is what the usize guarantee actually is.

It's not clear to me: I (wishfully) want to interpret it as meaning usize is the width of a pointer, which just happens to be the same as size_t for all the targets we currently support. So existing code shouldn't break (certainly not on supported targets), and we can refactor to actually use the pointer width in the compiler...advice, anyone?

Alternatively, we could just define an iptr type alias in standard that's cfg'd to u128 for cheri and usize for all other targets, and use it consistently in the toolchain libraries to make sure that they compile. User code can do the same if they want to.

This feels like doing something you don't mean. From a compiler perspective, there seems to no more reason to use u128 on CHERI than on x86. It just happens that pointers take up extra space. You can't recover more data than the 64-bit address from the architecture*, and I suspect this approach would mean the same workaround for future architectures.

(*) when pretending a pointer is an int

This feels like RFC material.

@nw0

One of the big questions in this issue is what the usize guarantee actually is.

The documentation of usize is clear to me:

The pointer-sized unsigned integer type.

That's what we currently guarantee, and all existing safe and unsafe Rust code can and does rely on this being true.

This feels like doing something you don't mean. From a compiler perspective, there seems to no more reason to use u128 on CHERI than on x86. It just happens that pointers take up extra space. You can't recover more data than the 64-bit address from the architecture*, and I suspect this approach would mean the same workaround for future architectures.

Thanks, this is useful. Maybe we could "tune" the definition of usize to be an unsigned integer type that's wide enough to store the address of a pointer such that a pointer-to-int cast and back returns the exact same pointer. That would mean that ,on CHERI ,usize would be 64-bit, but that code that does this:

let x: *mut T;
let x: usize = transmute(x);

would fail to compile because usize and *mut T do not have the same size.

This would certainly be "weird", and this does not turn usize into a size_t, and this does not provide an integer type that is as wide as a pointer (but this type is already provided by libc), and there is probably a lot of code in the wild that assumes that this never happens. But maybe implementing this behavior for the CHERI target would be enough to see if the target can work at all with Rust ?

@steveklabnik

This feels like RFC material.

I think that any change to the guarantees of usize is clearly RFC material.

The pointer-sized unsigned integer type.

That's what we currently guarantee, and all existing safe and unsafe Rust code can and does rely on this being true.

Ah, I suppose the question should be how liberally this can be interpreted. I claim that yes, while sometimes code relies on usize taking the same space as a pointer (the guarantee), other code really relies on usize being the same size as the result of LLVM's ptrtoint instruction. (I won't be coy, Rust's ptr_diff intrinsic really wants the latter). The precise interpretation changes nothing for currently supported targets.

Maybe we could "tune" the definition of usize to be an unsigned integer type that's wide enough to store the address of a pointer such that a pointer-to-int cast and back returns the exact same pointer.

This model works nicely for CHERI. I don't know about future architectures, but I guess this definition hints at some sort of bijection between usize and the addressable space, which sounds reasonable to me. Windows does similar things for convenience.

let x: *mut T;
let x: usize = transmute(x);
would fail to compile because usize and *mut T do not have the same size.

Ah, but as the transmute documentation, nobody should be doing that...transforming pointers into pointers is fine (i.e. fiddling the types), and if you're converting to usize, you should probably cast (as noted in "Alternatives"). Would be happy to see counterexamples, though.

I guess I'm just highlighting that transmute doesn't change representations; as the doc says, it's semantically equivalent to a bitwise move.

But maybe implementing this behavior for the CHERI target would be enough to see if the target can work at all with Rust ?

Digression: I could compile nostd Rust (c. 1.35 nightly) programs with 128-bit CHERI capabilities earlier this year, after patching libcore. Not many changes required! Everything I have written above is really "lessons learnt" and design thoughts, but full support will be a different story.

This feels like RFC material.

I think that any change to the guarantees of usize is clearly RFC material.

Absolutely; this issue was to flesh out ideas before presenting an RFC. If/when the consensus is that clear options exist, I'm more than happy to bring this to RFC. Thanks for all the brainwork so far!

Ah, but as the transmute documentation, nobody should be doing that..

Notice that independently of what we recommend people to do or not, we still do guarantee that this works correctly (transmute is unnecessary for that case, but it is not wrong). Notice that we do also guarantee this for #[repr(C)] union U { x: *mut T, y: usize }, which can be used to "transmute" between those types without any loss of information because they have the same size. Crates that implement "tagged pointers" (using certain pointer bits to store other information) often rely on these types of "lossless" ptr-to-int conversions.

we still do guarantee that this works correctly

Point taken.

Crates that implement "tagged pointers" (using certain pointer bits to store other information) often rely on these types of "lossless" ptr-to-int conversions.

Yes, and I suppose code that relies on specific pointer representations will never work on architectures with different pointer representations, capabilities or not. If we accept such architectures as legitimate targets, the best we can do (from a compiler/language perspective) is probably to reject compilation with a helpful message.

Yes, and I suppose code that relies on specific pointer representations will never work on architectures with different pointer representations, capabilities or not. If we accept such architectures as legitimate targets, the best we can do (from a compiler/language perspective) is probably to reject compilation with a helpful message.

Sounds good to me. I think that for code using transmute, the error will be generated anyways because the sizes of the types differ.

FYI, for those unaware, Arm are investing heavily in a prototype adaptation of CHERI for Armv8 called Morello (https://developer.arm.com/architectures/cpu-architecture/a-profile/morello), with development boards for a real quad-core processor (based on the Neoverse N1 used in things like Amazon's Graviton2 instances) becoming available early next year (there is already a simulator you can download from Arm's developer portal). Arm are not committing to making an official CHERI extension to Armv8 (and Morello is definitely not how it will look; it includes multiple ways of accomplishing the same thing in order to determine which ways perform best, are most useful for software, etc, and a production architecture would trim it down), but if the program is successful it is likely that it will eventually happen, so CHERI is quickly becoming a very real architecture.

I am responsible for the design of the built-in __[u]intcap_t, which is used to represent [u]intptr_t in the C/C++ implementation for CHERI, so I can give a bit of background on what we did for compatibility there:

Our intptr_t is implemented as a capability (pointer) at the hardware level, but exposes arithmetic operations and not dereferencing operations to software. Any pointer can be cast to a [u]intptr_t and back again. You can perform any arithmetic on it that you could perform on the underlying type (CHERI is designed to allow pointers to be taken out of bounds a little way and brought back in before use, because a lot of C code does this). Arm's implementation does allow you to turn on top-byte ignore and then stash things in the top bits of a pointer, all CHERI implementations allow you to stash things in the low bits.

CHERI is a single-provenance model. Every pointer must be derived from exactly one existing pointer. Within the C abstract machine, addresses of globals or stack allocations and returns from malloc are the sources of pointers and so you can't create a pointer to any object from anything else (malloc itself is outside of the standard C abstract machine and receives pointers from mmap or equivalent and subdivides them). Allowing an integer that is not derived from an existing pointer to be cast back to a pointer is possible only in a zero-provenance model, where pointers can be materialised out of thin air. This model would be intrinsically impossible to implement in a memory-safe environment.

Note that the separation between a size_t and intptr_t-like thing can make some compiler optimisations better because a pointer cast to a size_t does not introduce untracked aliases, whereas a pointer cast to an intptr_t does.

https://www.reddit.com/r/rust/comments/x28fea/zen4_avx512_support_reminds_me_32bit_indices_in/

Thanks for this issue. I've always been after this . basically an alternate target with 64bit addressing, but 32bit datastructures - a world where no individual collection can exceed 4gb. This is the GPU use case, and also suits the more advanced auto-vectorizable CPU SIMD options (AVX512 making a resurgence with Zen4, and there are RISC-V designs). It would also be my default. still in 2022, I am targeting 8-16gb RAM, just as I was in 2014 when I first discovered rust , and 64bit indices are just overkill.

My idea is to make a type "std::index", probably "std::uindex" aswell. These would be defined to "usize", "isize" by default keep usize= strictly the pointer size, no change there. Change all the collections in the stdlib and index operator to use the "std::index" type alias. Then introduce either a #[cfg()] or new target tripple for a world where the the pointer size is 64bits, and the index size is 32bits (and also for retro users, 32bit pointer, 16bit index to handle x86 real mode ; perhaps there are microcontrollers out there that work like this. As this is all opt-in there would be no breaking changes in any codebase. Just refactor any code that may want to use the new modes to use std::index instead of usize where appropriate.

rust-lang / rust