C can't do provenance [LWN.net]

C can't do provenance

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

> 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.

to post comments

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.