C can't do provenance [LWN.net]

C can't do provenance

Posted Sep 27, 2024 17:24 UTC (Fri) by NYKevin (subscriber, #129325)
In reply to: C can't do provenance by SLi
Parent article: Linus and Dirk on succession, Rust, and more

> Most of the (1) do not realize how little performance there will be left without alias analysis, which cannot be done without pointer provenance.

Neither Rust nor C(++) depend on provenance to do alias analysis. Rust uses lifetime-based alias analysis (i.e. if you have &mut T, it may not alias anything, and if you have &T, the pointee must be immutable or protected by an UnsafeCell) and C and C++ both use type-based alias analysis (i.e. if you have two pointers to distinct types, and neither type is char or a variation of char, then the pointers may not alias). In the case of Rust, it is difficult to uphold those invariants without some degree of provenance, but Rust handles this by splitting the language into safe and unsafe Rust. In safe Rust, borrow checking is far stricter than mere provenance, and in unsafe Rust, there is no such thing as provenance - you can manufacture whatever pointers or references you like, as long as any such references obey the aliasing and lifetime requirements (that is, a reference must always point at a valid allocation for the entire duration of the reference's lifetime, plus the two aliasing requirements mentioned before).

Rust does have a provenance model documented in its ptr module, but it is non-normative and experimental (according to that very same documentation), and there's almost no information about it in the Rustonomicon. Based on a previous discussion we've had on this site, it is my understanding that some people take the view that it is wrong to claim that Rust has no provenance, because of the existence of this non-normative and experimental model. I disagree with that position but will mention it for completeness (and to save those very same people the trouble of telling me that I'm wrong in comment replies). What I think we can agree on, regardless, is the fact that Rust's aliasing analysis, as it is currently implemented in stable versions of the compiler, is not dependent on this (or any other) provenance model.

to post comments

C can't do provenance

Posted Sep 27, 2024 21:34 UTC (Fri) by joib (subscriber, #8541) [Link] (4 responses)

> Neither Rust nor C(++) depend on provenance to do alias analysis.

I don't think this is correct (I don't know enough about the Rust compiler to say much about its internal workings, so the following applies to C(++)). For a trivial example, for something like

int *a = malloc(10);
int *b = malloc(10);

the alias analysis can determine that a and b point to disjoint objects. They may not call it provenance, as that term became popular only relatively recently, but what is if not making use of provenance to help alias analysis? The various provenance proposals are mostly about formalizing what compilers are already doing, and of course covering all (well, more of them at least) the corner cases.

Type-based alias analysis is another bit of data the compiler can use to implement alias analysis, but not the only one.

C can't do provenance

Posted Sep 29, 2024 9:44 UTC (Sun) by NYKevin (subscriber, #129325) [Link] (3 responses)

As I explained, the compiler is required to allow the programmer to reconstitute an arbitrary valid pointer from non-pointer data in multiple ways. So the optimization you describe is only possible if the compiler can either prove that you have not done that in a particular case, or if it can somehow prove that the pointers must not alias despite the fact that they may not obey strict provenance rules. In other words, this optimization only works in "easy" cases, and does not cover all legal uses of pointers. The compiler is required to disable it if it is not provably correct in a given case.

Provenance is not a matter of optimization. It is not "optional," and you cannot simply turn it off when it becomes inconvenient. It is a real feature of some hardware (e.g. CHERI) that makes it impossible to dereference a possibly-invalid pointer. On that hardware, manufacturing (and dereferencing) an arbitrary pointer out of non-pointer data traps. Walking off the end of an array traps. UAF and double free both trap. And there are probably several other things that trap, but I think you get the idea. All of these traps happen even if the pointer is numerically equal to a valid pointer that exists elsewhere in the program, and could be validly dereferenced at the same exact address. This is because, on that hardware, every pointer has associated metadata that tells the hardware whether it is valid, and over what range of addresses, so the hardware can check every dereference for validity (similar to Valgrind's memcheck tool, but much stricter because it is not required to be compatible with C). In the context of programming languages, "pointer provenance" generally means the set of restrictions that must be enforced in order for the language to be compatible with CHERI and similar architectures. I have not seen the term used to refer generically to knowing where some specific pointer came from - that's usually called escape analysis or pointer analysis.

C can't do provenance

Posted Sep 29, 2024 10:43 UTC (Sun) by SLi (subscriber, #53131) [Link] (2 responses)

I do think "where the pointer came from" is a big part of it necessarily. Here's how Rust Unsafe Code Guidelines define it (it admits that "The exact form of provenance in Rust is unclear"):

https://rust-lang.github.io/unsafe-code-guidelines/glossary.html#pointer-provenance

C can't do provenance

Posted Sep 29, 2024 21:55 UTC (Sun) by NYKevin (subscriber, #129325) [Link] (1 responses)

Yes, where the pointer came from is the whole point of provenance. That's because if the pointer came "from nowhere," or from an unrelated pointer, then on CHERI it will not have the correct metadata (or any metadata), and so dereferencing it will trap. The Rust provenance rules are intended to make it possible for a (currently hypothetical) CHERI backend to emit the necessary instructions to preserve every pointer's metadata.

What I'm getting at is that provenance is not an optimization technique. It is a hardware constraint.

C can't do provenance

Posted Sep 29, 2024 22:30 UTC (Sun) by Cyberax (✭ supporter ✭, #52523) [Link]

> Yes, where the pointer came from is the whole point of provenance. That's because if the pointer came "from nowhere," or from an unrelated pointer, then on CHERI it will not have the correct metadata (or any metadata), and so dereferencing it will trap.

This can technically happen with "far" pointers on the 32-bit segmented x86 architecture. Simply reading or trying to create a pointer to an invalid segment can cause an exception.

C can't do provenance

Posted Sep 27, 2024 22:36 UTC (Fri) by SLi (subscriber, #53131) [Link]

Yes, it's definitely possible to do alias analysis (or even remove the need for it) without pointer provenance, in general. I just don't believe it's possible for C or C++.

Rust has provenance

Posted Oct 4, 2024 8:45 UTC (Fri) by deltragon (guest, #159552) [Link]

Since RFC #3559 (titled "Rust Has Provenance") was accepted in February, Rust certainly has provenance. It is true that the documentation has not quite caught up to this yet (and still refers to the Strict/Permissive Provenance APIs as "experimental"), this is also changing along with the stabilisation of these APIs.