search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
94.95k stars 12.24k forks source link

Tracking Issue for strict_provenance #95228

Open Gankra opened 2 years ago

Gankra commented 2 years ago

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:

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

Unresolved Questions

Gankra commented 2 years ago

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):

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":

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:

Prior Art For This API:

CHERI Resources:

Provenance Resources:

Strict Provenance Zulip Threads:

Gankra commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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:

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

https://github.com/rust-lang/rust/blob/92804455704cc59d6d8272faf72f442c6125d395/library/core/src/ptr/mod.rs#L1390

I think we want the lint broken up into parts:

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

workingjubilee commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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.

Diggsey commented 2 years ago

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"

But then you can't mechanically map C signatures to Rust, because you can't know whether an integer should be treated as a pointer or not.

Today, basically everything you can do in C, you can also do in unsafe Rust, which makes it possible to call APIs designed to be called from C, but if Rust can't just "do what C does", then it makes that interop a lot harder.

Gankra commented 2 years ago

I mean, yes, but if you actually use the API and it expects you to pass it a dereferenceable pointer where it says the arg is an integer, then at that point you can go "ah, this API is lying" and do whatever needs to be done about that. Blindly charging forward, slamming into problems, and forcing ourselves to figure out what "do whatever needs to be done" should look like is the primary mission statement of this experiment.

Lokathor commented 2 years ago

So, for that specific API, SetWindowLongPtrW, the official signature looks like this:

LONG_PTR SetWindowLongPtrW(
  [in] HWND     hWnd,
  [in] int      nIndex,
  [in] LONG_PTR dwNewLong
);

where HWND is a *mut c_void (or other opaque pointer of choice), and LONG_PTR is isize (more specifically documented as "an integer the size of a pointer").

So in "real programs" you're expected to:

Also, while it's sometimes UB to declare the wrong foreign signature, that's because of cross-lang LTO, and we never normally compile user32, so we can just declare the wrong signature and type the function as:

extern "system" {
  pub fn SetWindowLongPtrW(hwnd: *mut c_void, index: c_int, new_long: *mut c_void) -> *mut c_void
}

And now we "don't have to" perform pointer to int casting ourselves, it just silently happens during the foreign interfacing.

All that said, when we get the pointer back from GetWindowLongPtrW, we've still lost out provenance info. So we're still hosed. We still need to be able to send a pointer to foreign-land, get it back from foreign-land later, and have the pointer continue to be usable by rust.

Gankra commented 2 years ago

Could you elaborate on why provenance "must" be lost?

If you're operating on a system that actually dynamically maintains provenance, the information must be maintained by the callee anyway or the OS literally doesn't function.

If you're operating under a model where the rust abstract machine just needs to be self-consistent, then presumably having the API signature reflect "pointer goes in, pointer goes out" is sufficient? Like yes the compiler doesn't "know" where those pointers go or come from, but the compiler also doesn't "do" global analysis and therefore must be able to cope with calling a native rust function with a (*mut) -> *mut signature, right?

Lokathor commented 2 years ago

Well if there's no global analysis then that's fine, sure.

RalfJung commented 2 years ago

Agreed with @Gankra.

Diggsey commented 2 years ago

(This assume GetWindowLongPtrW returns a type that can carry provenance, like *mut c_void.)

It does not, it returns an integer, but presumably you are suggesting redefining the function such that the return type preserves provenance.

RalfJung commented 2 years ago

Yes, @Lokathor suggested above to adjust the signature of SetWindowLongPtrW so I assume the same is done to the other related functions.

arichardson commented 2 years ago

So, for that specific API, SetWindowLongPtrW, the official signature looks like this:

LONG_PTR SetWindowLongPtrW(
  [in] HWND     hWnd,
  [in] int      nIndex,
  [in] LONG_PTR dwNewLong
);
extern "system" {
  pub fn SetWindowLongPtrW(hwnd: *mut c_void, index: c_int, new_long: *mut c_void) -> *mut c_void
}

Just as a note, this is in fact what the LLVM IR function signature looks like when building C/C++ with CHERI LLVM (https://cheri-compiler-explorer.cl.cam.ac.uk/z/KG5oqq).

intptr_t is lowered to i8 addrspace(200)*, so this retains provenance information and the signature would also be correct for cross-language LTO in the CHERI case.

Diggsey commented 2 years ago

@arichardson presumably that's because intptr_t is typedef'd to some special intrinsic type that is lowered to a pointer only for CHERI? That's an additional incompatibility then, because Rust's isize is how we map intptr_t, but isize does not store provenance.

Gankra commented 2 years ago

@Diggsey yes, see "A secondary goal" in the top comment and "But CHERI Runs C Code Fine?" in the FAQ.

Diggsey commented 2 years ago

I think my concerns with C interop basically boil down to this: Rust might need a way to interoperate with the PNVI-ae-udi model (assuming that is what C goes with) and I'm not convinced that the boundary between Rust's provenance model and the C provenance model can lie precisely on the FFI boundary. I think there will always be cases where we need unsafe Rust to be able to "act like C" for that interop to be practical.

If that concern turns out to be well-founded, it doesn't mean we can't still do better than C though. For example, we could use the same model, but have the "act of exposing a pointer" be an explicit compiler intrinsic intended for unsafe FFI code, rather than happening on all pointer-to-int casts.

Gankra commented 2 years ago

Yes it's probable there will need to be a way to say "I give up" and use a Ptr16/Ptr32/Ptr64/Ptr128 "integer type" that is exactly like how CHERI handles intptr_t. Solutions like this will be considered more seriously as we attempt to "migrate" more code to stricter semantics and run into limitations with the MVP.

In terms of things like interoperating with PNVI-ae-udi at the level of cross-language LTO -- it is wholy premature to at all think about that. Like, 5-10 years premature, realistically. Having a proposed experimental memory model is in a completely different galaxy from actually emitting aliasing metadata into LLVM.

RalfJung commented 2 years ago

If we don't consider cross-language LTO, then the FFI boundary is where such interop happens and I don't think we need to worry much about PNVI. Interactions all happen on the 'target machine' level, where most of the time there is no provenance (and when there is, like on CHERI, it is very explicit and propagates through integer and pointer types equally).

If we do consider cross-language LTO, then really the interactions are described by a "shared abstract machine" that the optimizations happen on -- probably the LLVM IR Abstract Machine. It is anyone's guess how that one will account for PNVI, but given that the trade-offs are very different between surface languages and IRs (and given that LLVM IR does not enforce TBAA on all accesses) I doubt they will just copy PNVI. So it is rather futile IMO to try and prepare for this future. (And @Gankra wrote basically the same thing at the same time.^^)

comex commented 2 years ago

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.

Is the "you must" meant to refer to strict provenance or the status quo? I don't see why under PNVI you wouldn't be able to allocate the nodes wherever you want, modulo aliasing concerns. Of course, this would not work on CHERI.

Gankra commented 2 years ago

All discussion is with respect to strict provenance, because that is the thing we are experimenting with.

RalfJung commented 2 years ago

For XOR lists also see this horrible hack ;)

workingjubilee commented 2 years ago

There are several different PNVI models with distinct implications, including ones that the paper did not fully explore, and allusions to other possibilities. Please do not truncate them to merely "PNVI" unless genuinely referring to all possible ones, as XorLinkedList by the usual methods does not work under PNVI-roll-a-die, which in the case of any question regarding provenance simply rolls a die and assigns a random provenance.

Diggsey commented 2 years ago

@RalfJung surely if one were determined to make XOR lists work, it would be better to define an XOR operation on pointers (ie. that XORs the address part and performs some operation with the same operator axioms as XOR (but not necessarily XOR) on the provenance part). Theoretically that could also work on CHERI if a suitable operator could be created, and if it can't then this XOR would just not be available for pointers on that architecture.

RalfJung commented 2 years ago

some operation with the same operator axioms as XOR (but not necessarily XOR) on the provenance part

I don't think such an operation necessarily exists, and even if it does then I would not agree. Rather we should have better operations to explicitly and separately manipulate the provenance and the address bytes of a pointer.

But anyway this is veering wildly into off-topic terrain. Let's continue on Zulip, if we must. :)

RalfJung commented 2 years ago

Ralf Discussing this API Concept Long Ago

For the record, I did not invent this API, though it's also a bit hard to track its history now. I posted a very similar API in the UCG stream in May 2020, but that was just copied from... somewhere. I think I first learned about the idea to kill int2ptr and replace it by an API with explicit provenance from @digama0.

brooksdavis commented 2 years ago

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

    • [ ] High-bit Tagging - rustc::ty does this because it makes common addressing modes Free Untagging Realestate

From a CHERI perspective, this can be made to work so long as the capability encoding knows what the useable address space is and ignores high bits appropriately with cheri_address_set. I can't remember if Morello supports TBI or not. The big downside is that it really has to be architectural (if potentially mode-dependent) since you're sacrificing addressable virtual address space.

  • APIs We Want To Add/Change?

    • A lot of uses of .addr() are for alignment checks, .is_aligned(), .is_aligned_to(usize)?

In CHERI C we added __builtin_is_aligned, __builtin_align_up, and __builtin_align_down and upstreamed them to LLVM. We also have/had some macros that could be builtins for dealing with low tags, but currently don't need them much.

Gankra commented 2 years ago

Problem that CHERI people might have some good answers for: AtomicPtr has a very limited API and currently people use AtomicUsize in its place for even basic stuff like the moral equivalent of wrapping_offset. Do you have APIs for that / llvm plumbing for that? In particular it would be ideal if all platforms could do some more complex ops on AtomicPtrs without "dropping" provenance.

Gankra commented 2 years ago

YESSSSS IT LANDED

ok i will properly post a public announcement for this when it hits nightly and I can link the docs

vbe0201 commented 2 years ago

Another "problematic but should work" thing I would like to bring attention to is hardware APIs that provide the programmer with opaque memory addresses to refer to. Examples being AArch64 TTBR_EL registers like this one.

I assume such cases will be naturally addressed by the idea of pointer::with_addr, but I figured it's worth pointing it out anyway.

Here's a strongly simplified, currently problematic example of how a programmer might go about implementing paging with it:

pub struct PageTable {
    l1_tables: [PhysAddr; 2],
    num_blocks: [usize; 2],
}

impl PageTable {
    pub fn new() -> Self {
        // Read L1 table locations and their sizes from system registers...
        Self {
            l1_tables: [
                PhysAddr::new(align_down(unsafe { TTBR0_EL1.get() }, PAGE_SIZE)),
                PhysAddr::new(align_down(unsafe { TTBR1_EL1.get() }, PAGE_SIZE)),
            ],
            num_blocks: [
                unsafe { TCR_EL1.read(TCR_EL1::T0SZ) } / L1_BLOCK_SIZE,
                unsafe { TCR_EL1.read(TCR_EL1::T1SZ) } / L1_BLOCK_SIZE,
            ],
        }
    }

    // Public APIs will be built on top of this.
    // `L1PageTableDescriptor` is a set of information for a page table entry.
    fn get_l1_descriptor(&mut self, address: VirtAddr) -> &mut L1PageTableDescriptor {
        let idx = (address.as_usize() >> 63) & 1;
        unsafe {
            // SAFETY: Even with re-established provenance for pointers to L1 tables,
            // what would be considered the "allocated object" to make `.add` and the
            // pointer deref safe to do here?
            &mut *self.l1_tables[idx]
                .as_mut_ptr::<L1PageTableDescriptor>()
                .add((address.as_usize() / L1_BLOCK_SIZE) & (self.num_blocks[idx] - 1))
        }
    }
}
jrtc27 commented 2 years ago

Problem that CHERI people might have some good answers for: AtomicPtr has a very limited API and currently people use AtomicUsize in its place for even basic stuff like the moral equivalent of wrapping_offset. Do you have APIs for that / llvm plumbing for that? In particular it would be ideal if all platforms could do some more complex ops on AtomicPtrs without "dropping" provenance.

We have the full set of RMW atomics; they're implemented as you would imagine, with the same rules as normal uintptr_t arithmetic in terms of the requirements for maintaining provenance (i.e. stay within representable bounds). Like C(++)11's atomics, the first operand is the pointer and the second operand is a plain integer (though I think we're lazy and shove the integer in a pointer type whose metadata is ignored as that way we don't need to update everywhere that deals with atomics to separate the types, but that's an implementation detail and not part of the model).

Gankra commented 2 years ago

Ok so basically all the machinery for doing arbitrary atomics with pointers (cross platform?) is already in LLVM, and rustc/std just needs to wire it up and expose it? (I am... incredibly fuzzy on what it means for a compiler to "preserve" provenance in a way that llvm and the CHERI backend will "get it".)

jrtc27 commented 2 years ago

We support all the C11 atomics, yes; for example: https://cheri-compiler-explorer.cl.cam.ac.uk/z/ezess6

thomcc commented 2 years ago

Sadly, it also needs fetch_or and fetch_and equivalents, or a lot of atomic code (https://github.com/Amanieu/parking_lot/blob/master/core/src/word_lock.rs for example) will not be able to be ported to AtomicPtr. That seems unsupported on pointers on compiler explorer, and it also brings up design questions.

jrtc27 commented 2 years ago

It works at the IR level, we're just missing a bit of plumbing for the Clang frontend for anything other than add/sub I guess: https://cheri-compiler-explorer.cl.cam.ac.uk/z/G7GcK7

jrtc27 commented 2 years ago

Oh, right, because C doesn't let you do that on "real" pointers at all, you need to use uintptr_t and then everything works: https://cheri-compiler-explorer.cl.cam.ac.uk/z/9MrKWP

Gankra commented 2 years ago

Just filed a bunch of issues for stuff off the top of my head under https://github.com/rust-lang/rust/labels/A-strict-provenance

Gankra commented 2 years ago

Today I learned that the m68k has the dubious honor of having an actual ABI where "pointer-sized-integer" and "pointer" actually have different ABIs just to keep you on your toes, so anyone who thinks m68k is Cool needs to stop all pointer-int-punning crimes immediately and report to the Type Correctness Ward.

(if you're gonna pun them, which is still largely super reasonable, you should still prefer a pointer over an integer for the pun, because that will still work better everywhere it can work)

pcwalton commented 2 years ago

Sorry to be this way, but I'm pretty worried about adding more undefined behavior to Rust to support a niche project like CHERI. Rust UB is already very hard to avoid. If this is an experiment, fine, but if an RFC gets filed I would probably be opposed at this point.

Gankra commented 2 years ago

Please see "Isn't This Model WAY Too Strict?" in the FAQ

devsnek commented 2 years ago

this is pretty cool. thank you for putting together such an understandable writeup :pray:

pcwalton commented 2 years ago

To address that FAQ issue, I don't think that it's frustrating at all for programmers that provenance is vaguely broken. I think it's frustrating for compiler writers and people who work on memory models. But most programmers happily go about their day not thinking about provenance. To that end, I'm much more interested in fixing the notion of provenance to comply with the unsafe code that people have written in the wild than in overhauling our pointer types and declaring large swathes of code UB. Yes, that will be "ugly"; it's our job to deal with that.

A valid reaction to what I've written above might be "but you'd be equally skeptical of stacked borrows then, right?" And yes, I am also skeptical of stacked borrows.

pcwalton commented 2 years ago

To be more concrete, I'd prefer we just use something like PNVI-ae-udi. Maybe we could tighten things up a little, but that seems like a good place to start.

thomcc commented 2 years ago

Yeah. I get that PNVI-ae-udi is a bit of a messy model semantically, but it has the property that code that does ptr->int->ptr merely misses out on optimizations, rather than being UB. That is a really nice property.

RalfJung commented 2 years ago

FWIW while Stacked Borrows is a lot easier to define on top of strict provenance, it is possible to define it in a way that ptr-int-ptr roundtrips always work and just pessimize the optimizer. However, the resulting model is... ghastly. About as ghastly as PNVI-ae-udi would be if it supported restrict (which it doesn't). Not something you'd want to implement in Miri. If you thought Stacked Borrows as-is is complicated, you really won't like this model. ;)

But Stacked Borrows vs no aliasing rules is in first approximation orthogonal to strict provenance vs allowing ptr-int-ptr roundtrips.

RalfJung commented 2 years ago

Also PNVI-ae-udi relies on C things like strict aliasing, which we don't want in Rust. This creates further problems and makes it a non-solution for us IMO. (If you remove strict aliasing, then I am fairly sure PNVI-ae-udi means that dead load elimination -- as in, removing loads whose result is unused -- is not a legal optimization. I promise I will write this up properly some day...)

joshtriplett commented 2 years ago

@Gankra Would you consider adding a FAQ entry for "Why don't compiler backends like LLVM just stop doing this provenance thing entirely so we don't have to track it?" I'd expect that to be a common question, right after "what is provenance and why is it a thing?".

As far as I can tell, the answer to the former question is something roughly like "We don't know a good way to do that. C isn't going to drive it, so it won't happen, unless someone comes along wanting to do a couple of PhDs in compilers and memory models. Meanwhile, this approach allows us to coexist with what compiler backends currently do.".

(I'd love an answer to the latter question as well that's more satisfying than "here's this weird C example involving pointer comparisons and out-of-bounds accesses that doesn't seem comparable to anything real-world code should ever actually do", which is how the int y, x, *p = &x + 1 example always seems to me.)

Clarifying something here: I'm actually genuinely asking for these FAQ entries, regardless of what path we go. Separately from that, I wish that there were another path we could go, but I don't actually know what that path would be or whether it's possible. So I really do want to have a clear answer for why we need this, but I'm not attempting to argue that we don't or that there's a better option.