Tracking Issue for strict_provenance

[Gankra]

Feature gate: #![feature(strict_provenance)]

read the docs

get the stable polyfill

subtasks

This is a tracking issue for the strict_provenance feature. This is a standard library feature that governs the following APIs:

• pointer::addr
• pointer::with_addr
• pointer::map_addr
• core::ptr::invalid
• core::ptr::invalid_mut

IMPORTANT: This is purely a set of library APIs to make your code more clear/reliable, so that we can better understand what Rust code is actually trying to do and what it actually needs help with. It is overwhelmingly framed as a memory model because we are doing a bit of Roleplay here. We are roleplaying that this is a real memory model and seeing what code doesn't conform to it already. Then we are seeing how trivial it is to make that code "conform".

This cannot and will not "break your code" because the lang and compiler teams are wholy uninvolved with this. Your code cannot be "run under strict provenance" because there isn't a compiler flag for "enabling" it. Although it would be nice to have a lint to make it easier to quickly migrate code that wants to play along.

This is an unofficial experiment to see How Bad it would be if Rust had extremely strict pointer provenance rules that require you to always dynamically preserve provenance information. Which is to say if you ever want to treat something as a Real Pointer that can be Offset and Dereferenced, there must be an unbroken chain of custody from that pointer to the original allocation you are trying to access using only pointer->pointer operations. If at any point you turn a pointer into an integer, that integer cannot be turned back into a pointer. This includes usize as ptr, transmute, type punning with raw pointer reads/writes, whatever. Just assume the memory "knows" it contains a pointer and that writing to it as a non-pointer makes it forget (because this is quite literally true on CHERI and miri, which are immediate beneficiaries of doing this).

A secondary goal of this project is to try to disambiguate the many meanings of ptr as usize, in the hopes that it might make it plausible/tolerable to allow usize to be redefined to be an address-sized integer instead of a pointer-sized integer. This would allow for Rust to more natively support platforms where sizeof(size_t) < sizeof(intptr_t), and effectively redefine usize from intptr_t to size_t/ptrdiff_t/ptraddr_t (it would still generally conflate those concepts, absent a motivation to do otherwise). To the best of my knowledge this would not have a practical effect on any currently supported platforms, and just allow for more platforms to be supported (certainly true for our tier 1 platforms).

A tertiary goal of this project is to more clearly answer the question "hey what's the deal with Rust on architectures that are pretty harvard-y like AVR and WASM (platforms which treat function pointers and data pointers non-uniformly)". There is... weirdness in the language because it's difficult to talk about "some" function pointer generically/opaquely and that encourages you to turn them into data pointers and then maybe that does Wrong Things.

The mission statement of this experiment is: assume it will and must work, try to make code conform to it, smash face-first into really nasty problems that need special consideration, and try to actually figure out how to handle those situations. We want the evil shit you do with pointers to work but the current situation leads to incredibly broken results, so something has to give.

Public API

This design is roughly based on the article Rust's Unsafe Pointer Types Need An Overhaul, which is itself based on the APIs that CHERI exposes for dynamically maintaining provenance information even under Fun Bit Tricks.

The core piece that makes this at all plausible is pointer::with_addr(self, usize) -> Self which dynamically re-establishes the provenance chain of custody. Everything else introduced is sugar or alternatives to as casts that better express intent.

More APIs may be introduced as we explore the feature space.

// core::ptr
pub fn invalid<T>(addr: usize) -> *const T;
pub fn invalid_mut<T>(addr: usize) -> *mut T;

// core::pointer
pub fn addr(self) -> usize;
pub fn with_addr(self, addr: usize) -> Self;
pub fn map_addr(self, f: impl FnOnce(usize) -> usize) -> Self;

Steps / History

• Implementation: Strict Provenance MVP #95241
• Final comment period (FCP)
• Stabilization PR

Unresolved Questions

• How Bad Is This?

• How Good Is This?

• What's Problematic (And Should Work)?

  • Hardcoded MMIO address stuff
    • We should define a platform-specific way to do this, possibly requiring that you only use volatile access
  • Opaque Function Pointers - architectures like AVR and WASM treat function pointers special, they're normal pointers.
    • We should really define a #[repr(transparent)] OpaqueFnPtr(fn() -> ()) type in std, need a way to talk about e.g. dlopen.
  • libc interop for bad APIs that pun integers and pointers
    • Use a union to make the pun explicit?
  • passing shared pointers over IPC?
    • At worst you can rederive from your SHMEM?
  • downcasting to subclasses?
    • Would be nice if you could create a reference without shrinking its provenance to allow for ergonomic references to a baseclass that can be (unsafely) cast to a reference to a subclass.
  • memcpy operations conceptually say "all this memory is just u8's" which would trash provenance
    • it's pretty standard to carve out exceptions for memcpy, but it would be good to know if this can be done more rigorously
      with something like llvm's proposed byte type
  • AtomicPtr - AtomicPtr has a very limited API, so lots of people use AtomicUsize to do the equivalent of wrapping_add
    • Morally this is fine, unclear if the right compiler intrinsics exist to express this without "dropping" provenance.

• What's Problematic (And Might Be Impossible)?

  • High-bit Tagging - rustc::ty does this because it makes common addressing modes Free Untagging Realestate
    • Technically this is "fine" but CHERI might get upset about it, needs investigation.
  • Pointer Compression - V8 and JVM like compressing pointers, involving massive truncations.
    • Can a Sufficiently Smart Union handle this?
  • Unrestricted XOR-list - XORing pointers to make an even more jacked up linked list
    • You must allocate all your nodes in a Vec/Arena to be able to reconstitute ptrs. At that point, use indices.

• APIs We Want To Add/Change?

  • A lot of uses of .addr() are for alignment checks, .is_aligned(), .is_aligned_to(usize)?
  • An API to make ZST alloc forging explicit, exists_zst(usize)?
  • .addr() should arguably work on a DST, if you use .addr() you are ostensibly saying "I know this doesn't roundtrip"
  • Explicit conveniences for low-bit tagging? .with_tag(TAG)?
  • expose_addr/from_exposed_addr are slightly unfortunate names since it's not the address that gets exposed, it's the provenance. What would be better names? Please discuss on Zulip.
  • It is somewhat unfortunate that addr is the short and easy name for the operation that programmers likely expect less. (Many will expect expose_addr semantics.) Maybe it should have a different name. But which name?

[Gankra]

FAQ

Why Is Rust So Broken? This Clearly Isn't A Problem For C!

It is absolutely a problem for C. Rust, C, C++, Swift, etc. are all fundamentally built on the same tools and principles once you start dropping down to the level of memory models (i.e. Rust literally just punts on atomics by saying "it's the C11 model" because that's the model for atomics). Compiler backends currently do not consistently model pointers in the face of things like "but pointers are just integers right"?

Why Doesn't Rust Use C's Solution

Folks who work on C's semantics are still trying to solve this issue, with the leading solution being PNVI-ae-udi. It's an interesting and reasonable approach under the assumption of "we can't possibly get people to fix their code, and we can't completely change compiler backends". At a high-level, the proposal is to (in the abstract machine's semantics):

• Maintain a global list of all "exposed" ("maybe aliased") allocations.
• Allocations come into the world un-exposed (unaliased).
• Whenever a pointer is cast to an integer (or otherwise escapes opaquely), mark its allocation as "exposed".
• Whenever an integer is cast to a pointer do a global hittest with that address on all exposed allocations.
• If it hits an exposed allocation, great, it gets that allocation's provenance.
• If it hits two exposed allocations (due to "one-past-the-end" shenanigans) be sad and just tell the programmer to "be consistent" and only access one of the two.

The strength of this model is that from a compiler's perspective this can mostly just be understood as "business as usual" because you can still let programmers do ~whatever and reason locally along the lines of: "I have kept perfect track of these pointers, and therefore know exactly how they are/aren't aliased. These other pointers over here have escaped or come from something I don't know about, so I will assume they all alias eachother and compile their accesses very conservatively."

What they do need to change under this model is to admit that a ptr-to-int cast has a "side-effect" (exposing the allocation) and that optimizing it away is unsound, because then you will forget the pointer was exposed and do bad things.

The weakness of this model is that essentially implies that an int-to-ptr cast has permission to access whatever memory you want (all "exposed" memory). This makes it very hard for dynamic checkers to be useful, because anytime ptr-int-ptr things happen, even implicitly/transiently, the checker has to throw up its hands and say "I guess you know what you're doing" and won't actually be able to help you catch bugs. For instance if you use-after-free, the checker cannot notice if you get "lucky" and start accessing a new allocation in the same place if the pointer was cast from an integer after the reallocation. This is Sad.

It is perhaps an inevitable fate that Rust will adopt C's model, or at least have to interoperate with it, but it would be nice if we could do better given how much time and energy we put into having more rigorous and safe concepts for borrows and lifetimes! Rust is uniquely positioned to explore stricter semantics, and has established precedent for just saying "hey actually this idea we've had since time immemorial is busted, let's migrate everyone off of it so the language can make sense".

I am not saying we are going to break the world right now, but we should explore how bad breaking the world is, and at worst, making code conform to strict provenance in more places will make our existing tools work more reliably, which is just Good.

But CHERI Runs C Code Fine?

Yes! Sort of.

Pointer-integer shenanigans are not actually that common, and so most code actually already trivially has dynamic/strict provenance in both Rust and C. Most of the time people are just comparing addresses, checking alignment, or doing tagged-pointer shenanigans. These things are totally fine under strict provenance!

The remaining places where people are actually committing pointer-integer crimes are handled by a hack that mostly works: defining intptr_t to just actually be a pointer still and having the compiler handle/codegen it as such. This is one of the genuine successes of C's model of "define a million different integer types that sure sound like they should be the same thing but get to be different if an implementation says they are". In particular, making this tolerable requires CHERI to say intptr_t is 128-bit and size_t/ptrdiff_t and friends are 64-bit. That said this hack has its limitations and Sufficiently Evil code will still break and just needs to be reworked. Or the code needs to be compiled to a significantly less strict model that looks A Lot like PNVI-ae-udi and removes most of the value of the checker.

The intptr_t hack was explored for Rust but it doesn't work very well, because rust doesn't make a distinction between size_t and intptr_t. This meant every array size and index was 128-bit and handled by CHERI's more expensive pointer registers/instructions on the paranoid assumption that it could all be Secret Pointers We Need To Track. For Rust to properly support CHERI it needs to decouple the notions of size_t and intptr_t, which means we need everyone to be more clear on what they mean when they convert between pointers and integers.

It would also be nice if Rust, the systems language that Really Cares About Memory-Safety was a first-class citizen on CHERI, the architecture that Really Cares About Memory-Safety. We are pursuing the same goals, and Rust's design is seemingly very friendly to CHERI... except pointer<->integer shenanigans make everything into a muddy mess.

Isn't It A Big Deal That CHERI "Breaks" wrapping_offset

CHERI's pointer compression scheme falls over if you wrapping_offset too far out-of-bounds (like, kilobytes out of bounds), and will silently mark your pointer as "corrupt" (while still faithfully preserving the actual address). Once this happens, offsetting that pointer back in bounds and trying to load/store will fault.

It's annoying but it's not really a problem. It's a system limitation, and if you run afoul of it you will get a deterministic fault. This is much the same as targetting Rust to some little embedded system, having to disable all of libstd, and then still crashing because you were too sloppy with your memory footprint. Or how random parts of std have to be cfg'd out when targetting WASM. Some code just isn't as portable as you'd like, because anything more exotic than x64 has quirky little limitations. Rust is not the intersection of all platform limitations, because that intersection is terrible.

Also I should clarify something because it seems to have been lost to history: wrapping_offset was never the "good" offset. At least in my time as a standard library team member, it was always intended that all Rust code should always be attempting to use offset. This is what the rustonomicon advocates, and how libstd was written. offset is the semantics the language uses for things like borrowing fields. If you access the contents of a slice or collection or anything else in std, that will overwhelmingly be done with offset, because that's The Right Way To Do It.

wrapping_offset is for "I am doing something really bad and can't do things Right". It's useful! I have many times wanted to use it to avoid dealing with some weird case in thin-vec or whatever other horrible unsafe code I'm writing. I generally don't because years of working on std burned Offset Is Right, Do It Right into my brain. It's ok for you to want a bit of "slop" to simplify some nasty unsafe code, but in this case that slop comes with the possibility of the code crashing on a relatively exotic platform.

Yes I know offset says:

Consider using wrapping_offset instead if these constraints are difficult to satisfy. The only advantage of this method is that it enables more aggressive compiler optimizations.

I wrote those docs, so this is my fault, mea culpa. The fact that you "wanted" to use offset was completely burned into my brain, so I didn't even think about mentioning/clarifying that. Like whenever I look at this line my brain is implicitly putting "☠️ IF YOUR CODE IS TERRIBLE, AND YOU ABSOLUTELY MUST ☠️" in front of it, because that was the conventional understanding of these two methods when this was written.

Your code isn't terrible for using wrapping_offset, I just should have made it more clear that it should be regarded as a Last Resort and not "the chill offset for everyone". 😿

Isn't This Model WAY Too Strict?

Probably! My goal is not to define The One True Memory Model for Rust, but to define a painfully simple one that is easy for Rust programmers to understand and make their code conform to by default. The "idea" with strict-provenance is that it's so strict that any coherent model must surely be a weakening of it (i.e. says strictly more code is allowed). In this way, code that happens to conform to strict-provenance (which is most code, as CHERI has demonstrated!) is essentially guaranteed to be correct under any model and to not be miscompiled (barring compiler bugs).

One can imagine ending up with this "tower of weakenings":

• strictest: (stacked-borrows-with-)strict-provenance, a model Rust programmers try their best to conform to.
• strict-ish: "real" stacked-borrows, an actually functional memory-model for the crimes Rust Programmers Crave.
• shrug-emoji: the actual primitives that compiler backends emit, and the optimizations they perform with them.

If your code works higher up the tower, it will definitely work against anything lower down the tower, and the bottom of the tower is the one that "matters", because that's the thing that actually compiles your code.

It is frustrating as a programmer to know that there is this vague memory-model stuff going on, and that compilers are vaguely broken because they don't really have coherent models. By making it easier for code to conform to strict-provenance, we are making it more robust in the face of inconsistent and buggy semantics AND future-proofing that code against any possible "real" model.

Mega Link Pile

The Work On This API:

• My Original Article Proposing It
• Initial Experiment PR
• My Zulip Live Journaling of porting most of the int<->ptr casts to this API in std/rustc
• Final MVP PR
• sptr: The Strict Provenance Polyfill

Prior Art For This API:

• Ralf Discussing this API Concept Long Ago
• cheri_address_set
• The Time We Banished mem::uninitailized To The Shadow Realm And Made Everyone Fix Their Code

CHERI Resources:

• Main CHERI Paper
• CHERI Rust Paper
• CHERI godbolt
• CHERI QEMU

Provenance Resources:

• Current Leading C Proposal for Provenance (PNVI-ae-udi)
• Ralf's Article On How LLVM Is Busted Under "Just Vibes" Provenance
• Ralf's Translation To How Rust Is Also Busted Under "Just Vibes" Provenance
• LLVM's Proposed Byte Type For Formalizing Memcpy Being Magic

Strict Provenance Zulip Threads:

• size_t != uintptr_t != ptraddr_t
• ptr->int->ptr as side effect destroys modular reasoning
• wasm and "function pointers"
• abomonation and strict provenance
• XorLinkedList and union provenance
• Intrusive Linked Lists in SB
• strict provenance: refs that don't shrink provenance
• Does wrapping_offset fizzle in cherry (CHERI) soda?
• Use-cases for unrestricted ptr2int2ptr
• Forging *mut w/o usize as *mut T
• strict provenance std compat notes
• strict provenance in dwarf::eh
• strict provenance and Harvard architectures
• calling conventions that handle int+ptr different?

[Gankra]

The proposed lints in #95199 should be something a user messing with these APIs can opt into to quickly find sketchy places in their code. What's the "right" way to expose an unstable lint? Is it sufficient to make it allow and users can opt in with normal linting stuff, or do we also need a special feature/-Z to opt into the lint existing at all?

[workingjubilee]

Hardcoded MMIO address stuff

We should define a platform-specific way to do this, possibly requiring that you only use volatile access

This should probably be more like core::arch::asm!: it's under arch in module terms but it actually is platform-generic, because it has the same factors in play: it's "architecturally specific in terms of invocation but almost universal because it appears almost everywhere".

The proposed lints in #95199 should be something a user messing with these APIs can opt into to quickly find sketchy places in their code. What's the "right" way to expose an unstable lint? Is it sufficient to make it allow and users can opt in with normal linting stuff, or do we also need a special feature/-Z to opt into the lint existing at all?

I... hm. I think the allow-by-default lint is conservative enough? It shouldn't need a -Z feature unless we get something wild going on like turning miri on to find misbehaving pointers.

[Gankra]

At least in the bootstrap, the compiler will complain if you allow() a lint in your code that doesn't exist. This potentially just means:

• We need to keep the experimental lint around forever even when the experiment is over
• Users can only "safely" invoke it from the command line manually, which is slightly unfortunate for anything like what I did where I used it as a FIXME/WONTFIX marker for the file.

Also due to the "Opaque Function Pointers" / "Harvard Architecture" / "AVR is cursed" issue

rust/library/core/src/ptr/mod.rs

Line 1390 in 9280445

// HACK: The intermediate cast as usize is required for AVR

I think we want the lint broken up into parts:

• #[fuzzy_provenance_casts] - int-to-ptr, totally evil
• #[lossy_provencance_casts] - ptr-to-int, sketchy but valid as long as you actually want .addr() semantics
• #[oxford_casts] - casts that make harvard architectures sad -- fn<->ptr (name is a joke... unless...)

I can't justify discouraging fn <-> int, absent better ways to talk about fn ptrs properly.

[workingjubilee]

At least in the bootstrap, the compiler will complain if you allow() a lint in your code that doesn't exist. This potentially just means:

Hm... I think we can make a lint conditional on #![feature(strict_provenance)] being enabled? I remember seeing at least one lint that is like that.

[Diggsey]

Overall I like this idea for Rust, but it seems incompatible for C interop. It's pretty common in C APIs to use an integer as a "user-data" field intended to store arbitrary values (primarily pointers). For example, the winapi SetWindowLongPtr function accepts a pointer-sized integer.

I could imagine having some kind of built-in "pointer map" type, which behaves like a HashMap<usize. *mut T>: this would allow storing and then later "recovering" the provenance of a pointer based on its address. On CHERI it could be an actual map, but on other architectures it could just be a no-op (at least at the machine level, not in the abstract machine).

[Gankra]

I feel like it's very plausible to define some sort of pointer-int union without messing with ABI for "this is a pointer, the API is lying" since in general, afaict, it's always sound to say something that is actually just an integer is a pointer "for fun" (as ptr::invalid shows) as long as you only deref/offset it when it's a Real Pointer.

[RalfJung]

it's always sound to say something that is actually just an integer is a pointer "for fun"

Yes indeed, pointers are a superset of (equally-sized) integers.