I am no longer on the job market
[web.git] / personal / _posts / 2022-04-11-provenance-exposed.md
1 ---
2 title: "Pointers Are Complicated III, or: Pointer-integer casts exposed"
3 categories: rust research
4 license: CC BY-SA 4.0
5 license-url: https://creativecommons.org/licenses/by-sa/4.0/
6 reddit: /rust/comments/u1bbqn/pointers_are_complicated_iii_or_pointerinteger/
7 ---
8
9 In my [previous blog post on pointer provenance]({% post_url 2020-12-14-provenance %}), I have shown that not thinking carefully about pointers can lead to a compiler that is internally inconsistent:
10 programs that are intended to be well-behaved get miscompiled by a sequence of optimizations, each of which seems intuitively correct in isolation.
11 We thus have to remove or at least restrict at least one of these optimizations.
12 In this post I will continue that trend with another example, and then I will lay down my general thoughts on how this relates to the recent [Strict Provenance](https://github.com/rust-lang/rust/issues/95228) proposal, what it could mean for Rust more generally, and compare with C's PNVI-ae-udi.
13 We will end on a very hopeful note about what this could all mean for Rust's memory model.
14 There's a lot of information packed into this post, so better find a comfortable reading position. :)
15
16 <!-- MORE -->
17
18 In case you don't know what I mean by "pointer provenance", you can either read that previous blog post or the [Strict Provenance documentation](https://doc.rust-lang.org/nightly/core/ptr/index.html#provenance).
19 The gist of it is that a pointer consists not only of the address that it points to in memory, but also of its *provenance*: an extra piece of "shadow state" that is carried along with each pointer and that tracks which memory the pointer has permission to access and when.
20 This is required to make sense of restrictions like "use-after-free is Undefined Behavior, even if you checked that there is a new allocation at the same address as the old one".
21 Architectures like CHERI make this "shadow state" explicit (pointers are bigger than usual so that they can explicitly track which part of memory they are allowed to access),
22 but even when compiling for AMD64 CPUs, compilers act "as if" pointers had such extra state -- it is part of the specification, part of the Abstract Machine, even if it is not part of the target CPU.
23
24 ## Dead cast elimination considered harmful
25
26 The key ingredient that will help us understand the nuances of provenance is `restrict`, a C keyword to promise that a given pointer `x` does not alias any other pointer not derived from `x`.[^restrict]
27 This is comparable to the promise that a `&mut T` in Rust is unique.
28 However, just like last time, we want to consider the limits that `restrict` combined with integer-pointer casts put on an optimizing compiler -- so the actual programming language that we have to be concerned with is the IR of that compiler.
29 Nevertheless I will use the more familiar C syntax to write down this example; you should think of this just being notation for the "obvious" equivalent function in LLVM IR, where `restrict` is expressed via `noalias`.
30 Of course, if we learn that the IR has to put some limitations on what code may do, this also applies to the surface language -- so we will be talking about all three (Rust, C, LLVM) quite a bit.
31
32 [^restrict]: The exact semantics of `restrict` are subtle and I am not aware of a formal definition. (Sadly, the one in the C standard does not really work, as you can see when you try to apply it to my example.) My understanding is as follows: `restrict` promises that this pointer, and all pointers derived from it, will not be used to perform memory accesses that *conflict* with any access done by pointers outside of that set. A "conflict" arises when two memory accesses overlap and at least one of them is a write. This promise is scoped to the duration of the function call when `restrict` appears in an argument type; I have no good idea for what the scope of the promise is in other situations.
33
34 With all that out of the way, consider the following program:
35 {% highlight c %}
36 #include <stdio.h>
37 #include <stdint.h>
38
39 static int uwu(int *restrict x, int *restrict y) {
40   *x = 0;
41
42   uintptr_t xaddr = (uintptr_t)x;
43   int *y2 = y-1;
44   uintptr_t y2addr = (uintptr_t)y2;
45   if (xaddr == y2addr) {
46     int *ptr = (int*)xaddr;
47     *ptr = 1;
48   }
49
50   return *x;
51 }
52
53 int main() {
54   int i[2] = {0, 0};
55   int res = uwu(&i[0], &i[1]);
56   // Always prints 1.
57   printf("%d\n", res);
58 }
59 {% endhighlight %}
60 This function takes as argument two `restrict` pointers `x` and `y`. We first write `0` into `*x`.
61 Then we compute `y2` as pointing to the `int` right before `*y`, and cast that and `x` to integers.
62 If the addresses we get are the same, we cast `xaddr` back to a pointer and write `1` to it.
63 Finally, we return the value stored in `*x`.
64
65 The `main` function simply calls `uwu` with two pointers pointing to the first two elements of an array.
66 Note, in particular, that this *will* make `xaddr` and `y2addr` always equal!
67 `&i[1] - 1` denotes the same address as `&i[0]`.
68
69 Now, let us imagine we run a few seemingly obvious optimizations on `uwu`:
70 - Inside the `if`, we can replace `xaddr` by `y2addr` since they are both equal integers.
71 - Since this is a `static` function and the only caller makes `y2addr` always equal to `xaddr`, we know that the conditional in the `if` will always evaluate to `true`. We thus remove the test. (Alternatively, the same transformation can happen by inlining `uwu` into `main` while preserving the alias information, which [LLVM explicitly aims for](https://lists.llvm.org/pipermail/llvm-dev/2019-March/131127.html).)
72 - Finally, we observe that `xaddr` is unused, so we can remove it entirely.
73
74 `uwu` now looks as follows:
75 {% highlight c %}
76 static int uwu(int *restrict x, int *restrict y) {
77   *x = 0;
78
79   int *y2 = y-1;
80   uintptr_t y2addr = (uintptr_t)y2;
81   int *ptr = (int*)y2addr; // <-- using y2addr
82   *ptr = 1;
83
84   return *x;
85 }
86 {% endhighlight %}
87
88 This might still look harmless.
89 However, we can do even more!
90 Notice how this function now consists of a store of `0` to `*x`, then a bunch of code *that does not involve `x` at all*, and then a load from `*x`.
91 Since `x` is a `restrict` pointer, this "code that does not involve `x`" cannot possibly mutate `*x`, as that would be a violation of the `restrict`/`noalias` guarantee.
92 Hence we can optimize the `return *x` to `return 0`.
93 This kind of optimization is the primary reason to have `restrict` annotations in the first place, so this should be uncontroversial.
94 Formally speaking: only pointers "derived from" `x` may access `*x`, and while the details of defining "derived from" are nasty, it should be clear that doing a bunch of operations that literally don't involve `x` at all cannot by any stretch of the imagination produce a result that is "derived from" `x`.
95 (If they could, `restrict` would be basically worthless.)
96
97 Now, the whole program looks like this:
98 {% highlight c %}
99 static int uwu(int *restrict x, int *restrict y) {
100   *x = 0;
101
102   int *y2 = y-1;
103   uintptr_t y2addr = (uintptr_t)y2;
104   int *ptr = (int*)y2addr;
105   *ptr = 1;
106
107   return 0; // <-- hard-coded return value
108 }
109
110 int main() {
111   int i[2] = {0, 0};
112   int res = uwu(&i[0], &i[1]);
113   // Now this prints 0!
114   printf("%d\n", res);
115 }
116 {% endhighlight %}
117 We started out with a program that always prints `1`, and ended up with a program that always prints `0`.
118 This is bad news. Our optimizations changed program behavior. That must not happen! What went wrong?
119
120 Fundamentally, this is the same situation as in the previous blog post: this example demonstrates that either the original program already had Undefined Behavior, or (at least) one of the optimizations is wrong.
121 However, the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip -- and if casting integers to pointers is allowed, *surely* that must work.
122 I will, for the rest of this post, assume that replacing `x` by `(int*)(uintptr_t)x` is always allowed.
123 So, which of the optimizations is the wrong one?
124
125 ## The blame game
126
127 Remember what I said earlier about `restrict` and how it matters which pointer `ptr` is "derived from"?
128 If we follow this lead, it may seem like the bogus optimization is the one that replaced `xaddr` by `y2addr`.
129 After this transformation, `ptr` is obviously "derived from" `y2` (and thus transitively from `y`) and not `x`, and so obviously `uwu` (as called from `main`) is wrong since we are doing two memory accesses (at least one of which is a write) to the same location, using two pointers that are "derived from" different `restrict` pointers!
130
131 However, that optimization doesn't even have anything to do with pointers.
132 It just replaces one equal integer by another!
133 How can that possibly be incorrect?
134
135 What this example shows is that the notion of one value being "derived from" another is not very meaningful when considering an optimizing compiler.[^consume]
136 It *is* possible to "fix" this problem and have a notion of "derived from" that works correctly even with pointer-integer round-trips.
137 However, this requires saying that not only pointers but also *integers carry provenance*, such that casting a pointer to an integer can preserve the provenance.
138 We solved one problem and created many new ones.
139 For once, we have to stop doing optimizations that replace one `==`-equal integer by another, unless we know they carry no provenance.
140 (Alternatively we could say `==`-comparing such integers is Undefined Behavior. But clearly we want to allow people to `==`-compare integers they obtained from pointer-integer casts, so this is not an option.)
141 That seems like a bad deal, since the code that benefits from such optimizations doesn't even do anything shady -- it is the pointer-manipulating code that is causing trouble.
142 The list doesn't end here though, and because of that, this option was discarded by the C standardization process during its provenance work, and they ended up picking a "PNVI" model -- provenance *not* via integers.
143 I think Rust should follow suit.
144
145 [^consume]: This is, in fact, a common problem -- it is what makes the `consume` memory order for atomic accesses basically impossible to specify in a programming language! While instruction sets often have very explicit rules about which instructions are assumed to "depend" on which previous instructions, that notion is hard to rationalize in a language where the compiler can replace `a + (b-a)` by `b` -- and thus *remove* dependencies from the program.
146
147 But, if it's not the replacement of `xaddr` by `y2addr` that is wrong, then which optimization *is* the wrong one?
148 I will argue that the incorrect optimization is the one that removed `xaddr`.
149 More specifically, the bad step was removing the cast `(uintptr_t)x`, irrespective of whether the result of that cast is used or not.
150 Had this cast been preserved, it would have been a marker for the compiler to know that "the `restrict` guarantee of `x` ends here", and it would not have done the final optimization of making `uwu` always return `0`.
151
152 ## Casts have a side-effect
153
154 How can it *not* be correct to remove an operation if its result is unused?
155 If we take a step back, then in general, the answer is simple -- if calling `foo()` has some side-effect on the global state, like changing the value of a global variable, then of course we have to keep the call to `foo` around even if we ignore its return value.
156 But in this case, the operation in question is `(uintptr_t)x`, which has no side-effect -- right?
157
158 Wrong.
159 This is exactly the key lesson that this example teaches us: casting a pointer to an integer *has a side-effect*, and that side-effect has to be preserved even if we don't care about the result of the cast (in this case, the reason we don't care is that we *already know* that `x` and `y2` will cast to the same `uintptr_t`).
160
161 To explain what that side-effect is, we have to get deep into the pointer provenance mindset.
162 `x` and `y` are both pointers, so they carry provenance that tracks which memory they have permission to access.
163 Specifically, `x` has permission to access `i[0]` (declared in `main`), and `y` has permission to access `i[1]`.[^dyn]
164 `y2` just inherits the permission from `y`.
165
166 [^dyn]: As mentioned in a previous footnote, this is not actually how `restrict` works. The exact set of locations these pointers can access is determined *dynamically*, and the only constraint is that they cannot be used to access *the same location* (except if both are just doing a load). However, I carefully picked this example so that these subtleties should not change anything.
167
168 But which permission does `ptr` get?
169 Since integers do not carry provenance, the details of this permission information are lost during a pointer-integer cast, and have to somehow be 'restored' at the integer-pointer cast.
170 And that is exactly the point where our problems begin.
171 In the original program, we argued that doing a pointer-integer-pointer round-trip is allowed (as is the intention of the C standard).
172 It follows that `ptr` must pick up the permission from `x` (or else the write to `*ptr` would be Undefined Behavior: `x` is `restrict`, nothing else can access that memory).
173 However, in the final program, `x` plays literally no role in computing `ptr`!
174 It would be a disaster to say that `ptr` could pick up the permission of `x` -- just imagine all that `y`-manipulating code is moved into a different function.
175 Do we have to assume that any function we call can just do a cast to "steal" `x`'s permission?
176 That would entirely defeat the point of `restrict` and make `noalias` optimizations basically impossible.
177
178 But how can it be okay for `ptr` to pick up `x`'s permission in the original program, and *not* okay for it to pick up the same permission in the final program?
179 The key difference is that in the original program, `x` *has been cast to an integer*.
180 When you cast a pointer to an integer, you are basically declaring that its permission is "up for grabs", and any future integer-pointer cast may end up endowing the resulting pointer with this permission.
181 We say that the permission has been "exposed".
182 And *that* is the side-effect that `(uintptr_t)x` has!
183
184 Yes, this way of resolving the conflict *does* mean we will lose some optimizations.
185 We *have to* lose some optimization, as the example shows.
186 However, the crucial difference to the previous section is that *only code which casts pointers to integers is affected*.
187 This means we can keep the performance cost localized to code that does 'tricky things' around pointers -- that code needs the compiler to be a bit conservative, but all the other code can be optimized without regard for the subtleties of pointer-integer-pointer round-trips.
188 (Specifically, *both* pointer-integer and integer-pointer casts have to be treated as impure operations, but for different reasons.
189 Pointer-integer casts have a side-effect as we have seen.
190 Integer-pointer casts are *non-deterministic* -- they can produce different results even for identical inputs.
191 I moved the discussion of this point into the appendix below.)
192
193 ## Strict provenance: pointer-integer casts *without* side-effects
194
195 This may sound like bad news for low-level coding tricks like pointer tagging (storing a flag in the lowest bit of a pointer).
196 Do we have to optimize this code less just because of corner cases like the above?
197 As it turns out, no we don't -- there are some situations where it is perfectly fine to do a pointer-integer cast *without* having the "exposure" side-effect.
198 Specifically, this is the case if we never intend to cast the integer back to a pointer!
199 That might seem like a niche case, but it turns out that most of the time, we can avoid 'bare' integer-pointer casts, and instead use an operation like [`with_addr`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.with_addr) that explicitly specifies which provenance to use for the newly created pointer.[^with_addr]
200 This is more than enough for low-level pointer shenanigans like pointer tagging, as [Gankra demonstrated](https://gankra.github.io/blah/tower-of-weakenings/#strict-provenance-no-more-getting-lucky).
201 Rust's [Strict Provenance experiment](https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance) aims to determine whether we can use operations like `with_addr` to replace basically all integer-pointer casts.
202
203 [^with_addr]: `with_addr` has been unstably added to the Rust standard library very recently. Such an operation has been floating around in various discussions in the Rust community for quite a while, and it has even made it into [an academic paper](https://iris-project.org/pdfs/2022-popl-vip.pdf) under the name of `copy_alloc_id`. Who knows, maybe one day it will find its way into the C standard as well. :)
204
205 As part of Strict Provenance, Rust now has a second way of casting pointers to integers, `ptr.addr()`, which does *not* "expose" the permission of the underlying pointer, and hence can be treated like a pure operation![^experiment]
206 We can do shenanigans on the integer representation of a pointer *and* have all these juicy optimizations, as long as we don't expect bare integer-pointer casts to work.
207 As a bonus, this also makes Rust work nicely on CHERI *without* a 128bit wide `usize`, and it helps Miri, too.
208
209 [^experiment]: My lawyers advised me to say that all of this is provisional and the specification for `addr` and all other Strict Provenance operations might change until their eventual stabilization.
210
211 But that is not the focus of this blog post, Gankra has [already written most of what there is to say here](https://gankra.github.io/blah/tower-of-weakenings/).
212 For this blog post, we are happy with what we learned about casts between pointers and integers.
213 We have found a way to resolve the conflict uncovered by the example, while keeping performance cost (due to lost optimizations) confined to just the code that is truly ambiguous, and even found alternative APIs that can be used to replace most (all?) uses of ambiguous integer-pointer casts.
214 All is well that ends well?
215 Unfortunately, no -- we are not quite done yet with pointer provenance nightmares.
216
217 ## Let's do some transmutation magic
218
219 Languages like C or Rust typically allow programmers to re-interpret the underlying representation of a value at a different type.
220 In Rust, this is often called "transmutation"; in C, a common term for this is "type punning".
221 The easiest way to do this in Rust is via the [`mem::transmute`](https://doc.rust-lang.org/std/mem/fn.transmute.html) function, but alternatively transmutation is possible via `union`s or by casting a `*mut T` raw pointer to `*mut U`.
222 In C, the easiest way is to use a `memcpy` between variables of different types, but `union`-based type punning is also sometimes allowed, as is loading data of arbitrary type using a character-typed pointer.
223 (Other kinds of pointer-based type punning are forbidden by C's strict aliasing rules, but Rust has no such restriction.)
224 The next question we are going to treat in this blog post is: what happens when we transmute a pointer to an integer?
225
226 Basically, imagine the original example after we replace the two casts (computing `xaddr` and `y2addr`) with a call to a function like
227 {% highlight c %}
228 static uintptr_t transmute_memcpy(int *ptr) {
229     uintptr_t res;
230     memcpy(&res, &ptr, sizeof(uintptr_t));
231     return res;
232 }
233 {% endhighlight %}
234 or
235 {% highlight c %}
236 static uintptr_t transmute_union(int *ptr) {
237     typedef union { uintptr_t res; int *ptr; } Transmute;
238     Transmute t;
239     t.ptr = ptr;
240     return t.res;
241 }
242 {% endhighlight %}
243 All the same optimizations still apply -- right?
244 This requires a compiler that can "see through" `memcpy` or union field accesses, but that does not seem too much to ask.
245 But now we have the same contradiction as before!
246 Either the original program already has Undefined Behavior, or one of the optimizations is incorrect.
247
248 Previously, we resolved this conundrum by saying that removing the "dead cast" `(uintptr_t)x` whose result is unused was incorrect, because that cast had the side-effect of "exposing" the permission of `x` to be picked up by future integer-pointer casts.
249 We could apply the same solution again, but this time, we would have to say that a `union` access (at integer type) or a  `memcpy` (to an integer) can have an "expose" side-effect and hence cannot be entirely removed even if its result is unused.
250 And that sounds quite bad!
251 `(uintptr_t)x` only happens in code that does tricky things with pointers, so urging the compiler to be careful and optimize a bit less seems like a good idea (and at least in Rust, `x.addr()` even provides a way to opt-out of this side-effect).
252 However, `union` and `memcpy` are all over the place.
253 Do we now have to treat *all* of them as having side-effects?
254 In Rust, due to the lack of a strict aliasing restriction (or in C with `-fno-strict-aliasing`), things get even worse, since literally *any* load of an integer from a raw pointer might be doing a pointer-integer transmutation and thus have the "expose" side-effect!
255
256 To me, and speaking from a Rust perspective, that sounds like bad idea.
257 Sure, we want to make it as easy as possible to write low-level code in Rust, and that code sometimes has to do unspeakable things with pointers.
258 But we *don't* like the *entire ecosystem* to carry the cost of that decision by making it harder to remove every raw pointer load everywhere!
259 So what are the alternatives?
260
261 Well, I would argue that the alternative is to treat the original program (after translation to Rust) as having Undefined Behavior.
262 There are, to my knowledge, generally two reasons why people might want to transmute a pointer to an integer:
263 - Chaining many `as` casts is annoying, so calling `mem::transmute` might be shorter.
264 - The code doesn't actually care about the *integer* per se, it just needs *some way* to hold arbitrary data in a container of a given type.
265
266 The first kind of code should just use `as` casts, and we should do what we can (via lints, for example) to identify such code and get it to use casts instead.[^compat]
267 Maybe we can adjust the cast rules to remove the need for chaining, or add some [helper methods](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.expose_addr) that can be used instead.
268
269 [^compat]: We could even, if we are really desperate, decide to special-case `mem::transmute::<*const T, usize>` (and likewise for `*mut T`) and declare that it *does* have the "expose" side-effect if the current crate is using some old edition. Sometimes, you have to do ugly things to move forwards. This would not apply to `union`- or raw-pointer-based transmutation.
270
271 The second kind of code should not use integers!
272 Putting arbitrary data into an integer type is already somewhat suspicious due to the trouble around padding (if we want to make use of those shiny new `noundef` annotations that LLVM offers, we have to disallow transmuting data with padding to integer types).
273 The right type to use for holding arbitrary data is `MaybeUninit`, so e.g. `[MaybeUninit<u8>; 1024]` for up to 1KiB of arbitrary data.
274 `MaybeUninit` can also hold pointers with their provenance without any trouble.
275
276 Because of that, I think we should move towards discouraging, deprecating, or even entirely disallowing pointer-integer transmutation in Rust.
277 That means a cast is the only legal way to turn a pointer into an integer, and after the discussion above we got our casts covered.
278 A [first careful step](https://github.com/rust-lang/rust/pull/95547) has recently been taken on this journey; the `mem::transmute` documentation now cautions against using this function to turn pointers into integers.
279
280 ## A new hope for Rust
281
282 All in all, while the situation may be very complicated, I am actually more hopeful than ever that we can have both -- a precise memory model for Rust *and* all the optimizations we can hope for!
283 The three core pillars of this approach are:
284 - making pointer-integer casts "expose" the pointer's provenance,
285 - offering `ptr.addr()` to learn a pointer's address *without* exposing its provenance,
286 - and disallowing pointer-integer transmutation.
287
288 Together, they imply that we can optimize "nice" code (that follows Strict Provenance, and does not "expose" or use integer-pointer casts) perfectly, without any risk of breaking code that does use pointer-integer round-trips.
289 In the easiest possible approach, the compiler can simply treat pointer-integer and integer-pointer casts as calls to some opaque external function.
290 Even if the rest of the compiler literally entirely ignores the existence of pointer-integer round-trips, it will still support such code correctly!
291
292 However, it's not just compilers and optimizers that benefit from this approach.
293 One of my biggest quests is giving a [precise model](https://plv.mpi-sws.org/rustbelt/stacked-borrows/) of the Rust aliasing rules, and that task has just gotten infinitely easier.
294 I used to worry *a lot* about pointer-integer round-trips while developing Stacked Borrows.
295 This is the entire reason why all of this "untagged pointer" mess exists.
296
297 Under this brave new world, I can entirely ignore pointer-integer round-trips when designing memory models for Rust.
298 Once that design is done, support for pointer-integer round-trips can be added as follows:
299 - When a pointer is cast to an integer, its provenance (whatever information it is that the model attaches to pointers -- in Stacked Borrows, this is called the pointer's *tag*) is marked as "exposed".
300 - When an integer is cast to a pointer, we *guess* the provenance that the new pointer should have from among all the provenances that have been previously marked as "exposed".
301   (And I mean *all* of them, not just the ones that have been exposed "at the same address" or anything like that. People will inevitably do imperfect round-trips where the integer is being offset before being cast back to a pointer, and we should support that. As far as I know, this doesn't really cost us anything in terms of optimizations.)
302
303 This "guess" does not need to be described by an algorithm.
304 Through the magic that is formally known as [angelic non-determinism](https://en.wikipedia.org/wiki/Angelic_non-determinism), we can just wave our hands and say "the guess will be maximally in the programmer's favor": if *any* possible choice of (previously exposed) provenance makes the program work, then that is the provenance the new pointer will get.
305 Only if *all* choices lead to Undefined Behavior, do we consider the program to be ill-defined.
306 This may sound like cheating, but it is actually a legit technique in formal specifications.
307
308 Also note how it's really *just* the integer-pointer casts that are making things so complicated here.
309 If it weren't for them, we would not even need all that "exposure" machinery.
310 Pointer-integer casts on their own are perfectly fine!
311 That's why [`addr`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.addr)+[`with_addr`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.with_addr) is such a nice API from a memory model perspective.[^fake_alloc]
312
313 [^fake_alloc]: Even more specifically, it's the integer-pointer cast as part of a pointer-integer round-trip that are a problem. If you are just casting an integer constant to a pointer because on your platform that's where some fixed memory region lies, and if that memory is entirely outside of the global, stack, and heap allocations that the Rust language itself is aware of, we can still be friends.
314
315 This approach *does* have the disadvantage that it becomes near impossible to write a tool like Miri that precisely matches the specification, since Miri cannot possibly implement this "guessing" accurately.
316 However, Miri can still properly check code that uses Strict Provenance operations, so hopefully this is just yet another incentive (besides the more precise specification and better optimization potential) for programmers to move their code away from integer-pointer casts and towards Strict Provenance.
317 And who knows, maybe there *is* a clever way that Miri can actually get reasonably close to checking this model?
318 It doesn't have to be perfect to be useful.
319
320 What I particularly like about this approach is that it makes pointer-integer round-trips a purely local concern.
321 With an approach like Stacked Borrows "untagged pointers", *every* memory operation has to define how it handles such pointers.
322 Complexity increases globally, and even when reasoning about Strict Provenance code we have to keep in mind that some pointers in other parts of the program might be "untagged".
323 In contrast, this "guessing maximally in your favor"-based approach is entirely local; code that does not syntactically contain exposing pointer-integer or integer-pointer casts can literally forget that such casts exist at all.
324 This is true both for programmers thinking about their `unsafe` code, and for compiler authors thinking about optimizations.
325 Compositionality at its finest!
326
327 ## But what about C?
328
329 I have talked a lot about my vision for "solving" pointer provenance in Rust.
330 What about other languages?
331 As you might have heard, C is moving towards making [PNVI-ae-udi](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf) an official recommendation for how to interpret the C memory model.
332 With C having so much more legacy code to care about and many more stakeholders than Rust does, this is an impressive achievement!
333 How does it compare to all I said above?
334
335 First of all, the "ae" part of the name refers to "address-exposed" -- that's exactly the same mechanism as what I described above!
336 In fact, I have taken the liberty to use their terminology.
337 So, on this front, I see Rust and C as moving into the same direction, which is great.
338 (Now we just need to get LLVM to also move in that direction.)
339 I should mention that PNVI-ae-udi does *not* account for the `restrict` modifier of C, so in a sense it is solving an easier problem than the Rust memory model which has no choice but to contend with interesting questions around aliasing restrictions.
340 However, if/when a more precise model of C with `restrict` emerges, I don't think they will be moving away from the "address-exposed" model -- to the contrary, as I just argued this model means we can specify `restrict` without giving a thought to pointer-integer round-trips.
341
342 The "udi" part of the name means "user disambiguation", and is basically the mechanism by which an integer-pointer cast in C "guesses" the provenance it has to pick up.
343 The details of this are complicated, but the end-to-end effect is basically exactly the same as in the "best possible guess" model I have described above!
344 Here, too, my vision for Rust aligns very well with the direction C is taking.
345 (The set of valid guesses in C is just a lot more restricted since they do not have `wrapping_offset`, and the model does not cover `restrict`.
346 That means they can actually feasibly give an algorithm for how to do the guessing.
347 They don't have to invoke scary terms like "angelic non-determinism", but the end result is the same -- and to me, the fact that it is equivalent to angelic non-determinism is what justifies this as a reasonable semantics.
348 Presenting this as a concrete algorithm to pick a suitable provenance is then just a stylistic choice.)
349 Kudos go to Michael Sammler for opening my eyes to this interpretation of "user disambiguation", and arguing that angelic non-determinism might not be such a crazy idea after all.
350
351 What is left is the question of how to handle pointer-integer transmutation, and this is where the roads are forking.
352 PNVI-ae-udi explicitly says loading from a union field at integer type exposes the provenance of the pointer being loaded, if any.
353 So, the example with `transmute_union` would be allowed, meaning the optimization of removing the "dead" load from the `union` would *not* (in general) be allowed.
354 Same for `transmute_memcpy`, where the proposal says that when we access the contents of `ret` at type `uintptr_t`, that will again implicitly expose the provenance of the pointer.
355
356 I think there are several reasons why this choice makes sense for C, that do not apply to Rust:
357 - There is a *lot* of legacy code. A *LOT*.
358 - There is no alternative like `MaybeUninit` that could be used to hold data without losing provenance.
359 - Strict aliasing means that not *all* loads at integer type have to worry about provenance; only loads at character type are affected.
360
361 On the other hand, I am afraid that this choice might come with a significant cost in terms of lost optimizations.
362 As the example above shows, the compiler has to be very careful when removing any operation that can expose a provenance, since there might be integer-pointer casts later that rely on this.
363 (Of course, until this is actually implemented in GCC or LLVM, it will be hard to know the actual cost.)
364 Because of all that, I think it is reasonable for Rust to make a different choice here.
365
366 ## Conclusion
367
368 This was a long post, but I hope you found it worth reading. :)
369 To summarize, my concrete calls for action in Rust are:
370 - Code that uses pointer-integer transmutation should migrate to regular casts or `MaybeUninit` transmutation ASAP.
371   I think we should declare pointer-integer transmutation Undefined Behavior and not accept such code as well-defined.
372 - Code that uses pointer-integer or integer-pointer *casts* might consider migrating to the Strict Provenance APIs.
373   You can do this even on stable with [this polyfill crate](https://crates.io/crates/sptr).
374   However, such code *is and remains* well-defined. It just might not be optimized as well as one could hope, it might not compile on CHERI, and Miri will probably miss some bugs.
375   If there are important use-cases not covered by Strict Provenance, we'd like to hear about them!
376
377 This is a large undertaking and will require a lot of work!
378 However, at the end of this road is a language with a coherent, well-defined memory model *and* support for doing unspeakable things to pointers *without* incurring a (reasoning or optimization) cost on code that is perfectly nice to its pointers.
379 Let us work towards this future together. :)
380
381 ## Appendix
382
383 #### Integer-pointer casts are not pure, either
384
385 I promised an example of how integer-pointer casts are "impure", in the sense that two casts with the same input integer can produce different pointers:
386
387 {% highlight c %}
388 static int uwu(int *restrict x, int *restrict y) {
389   *x = 0;
390   *y = 0;
391
392   uintptr_t xaddr = (uintptr_t)x;
393   int *y2 = y-1;
394   uintptr_t y2addr = (uintptr_t)y2;
395   assert(xaddr == y2addr);
396
397   int *xcopy = (int*)xaddr;
398   int *y2copy = (int*)y2addr;
399   int *ycopy = y2copy+1;
400
401   return *xcopy + *ycopy;
402 }
403
404 int main() {
405   int i[2] = {0, 0};
406   uwu(&i[0], &i[1]);
407 }
408 {% endhighlight %}
409
410 If we ignore the pointer-integer round-trips, this uses `x` and `xcopy` to access `i[0]`, while using `y` and `ycopy` to access `i[1]`, so this should be uncontroversial.
411 `ycopy` is computed via `(y-1)+1`, but hopefully nobody disagrees with that.
412 Then we just add some pointer-integer round-trips.
413
414 But now, consider that `(int*)xaddr` and `(int*)y2addr` take the same integer as input!
415 If the compiler were to treat integer-pointer casts as a pure, deterministic operation, it could replace `(int*)y2addr` by `xcopy`.
416 However, that would mean `xcopy` and `ycopy` have the same provenance!
417 And there exists no provenance in this program that has access to both `i[0]` and `i[1]`.
418 So, either the cast has to synthesize a new provenance that has never been seen before, or doing common subexpression elimination on integer-pointer casts is wrong.
419
420 My personal stance is that we should not let the cast synthesize a new provenance.
421 This would entirely lose the benefit I discussed above of making pointer-integer round-trips a *local* concern -- if these round-trips produce new, never-before-seen kinds of provenance, then the entire rest of the memory model has to define how it deals with those provenances.
422 We already have no choice but treat pointer-integer casts as an operation with side-effects; let's just do the same with integer-pointer casts and remain sure that no matter what the aliasing rules are, they will work fine even in the presence of pointer-integer round-trips.
423
424 That said, under this model integer-pointer casts still have no side-effect, in the sense that just removing them (if their result is unused) is fine.
425 Hence, it *could* make sense to implicitly perform integer-pointer casts in some situations, like when an integer value (without provenance) is used in a pointer operation (due to an integer-to-pointer transmutation).
426 This breaks some optimizations like load fusion (turning two loads into one assumes the same provenance was picked both times), but most optimizations (in particular dead code elimination) are unaffected.
427
428 #### What about LLVM?
429
430 I discussed above how my vision for Rust relates to the direction C is moving towards.
431 What does that mean for the design space of LLVM?
432 Which changes would have to be made to fix (potential) miscompilations in LLVM and to make it compatible with these ideas for C and/or Rust?
433 Here's the list of open problems I am aware of:
434 - LLVM would have to to stop [removing `inttoptr(ptrtoint(_))`](https://github.com/llvm/llvm-project/issues/33896) and stop doing [replacement of `==`-equal pointers](https://github.com/llvm/llvm-project/issues/34577).
435 - As the first example shows, LLVM also needs to treat `ptrtoint` as a side-effecting operation that has to be kept around even when its result is unused. (Of course, as with everything I say here, there can be special cases where the old optimizations are still correct, but they need extra justification.)
436 - I think LLVM should also treat `inttoptr` as a side-effecting (and, in particular, non-deterministic) operation, as per the last example. However, this could possibly be avoided with a `noalias` model that specifically accounts for new kinds of provenance being synthesized by casts. (I am being vague here since I don't know what that provenance needs to look like.)
437
438 So far, this all applies to LLVM as a Rust and C backend equally, so I don't think there are any good alternatives.
439 On the plus side, adapting this strategy for `inttoptr` and `ptrtoint` means that the recent LLVM ["Full Restrict Support"](https://lists.llvm.org/pipermail/llvm-dev/2019-March/131127.html) can also handle pointer-integer round-trips "for free"!
440
441 Adding `with_addr`/`copy_alloc_id` to LLVM is not strictly necessary, since it can be implemented with `getelementptr` (without `inbounds`).
442 However, optimizations don't seem to always deal well with that pattern, so it might still be a good idea to add this as a primitive operation to LLVM.
443
444 Where things become more subtle is around pointer-integer transmutation.
445 If LLVM wants to keep doing replacement of `==`-equal integers (which I strongly assume to be the case), *something* needs to give: my first example, with casts replaced by transmutation, shows a miscompilation.
446 If we focus on doing an `i64` load of a pointer value (e.g. as in the LLVM IR produced by `transmute_union`, or pointer-based transmutation in Rust), what are the options?
447 Here are the ones I have seen so far (but there might be more, of course):
448 1. The load could be said to behave like `ptrtoint`. This means it strips provenance and as a side-effect, it also exposes the pointer.
449 2. The load could be said to just strip provenance *without* exposing the pointer.
450 3. The load could be simply UB or return `poison`.
451 4. The load could produce an integer with provenance, *and moreover* any computation on such an integer (including `icmp`) is UB (or returns `poison`).
452   This has some subtle consequences, but they might be mostly harmless. For example, `x` can no longer be replaced by `x+0`.
453   We cannot assume that it is safe to compare arbitrary `i64` and branch on the result, even if they are `noundef`. Or maybe `noundef` also excludes provenance?
454   This is certainly the least obvious alternative.
455
456 Except for the first option, these all say that my example with transmutation instead of the pointer-integer casts is UB, which avoids the optimization problems that arise from accepting that example.
457 That is fine for my vision for Rust, but a problem for C with PNVI-ae-udi.
458 Only the first option is compatible with that, but that option also means entirely removing a load is non-trivial even if its result is unused!
459 I hope we can avoid that cost for Rust.
460
461 Another interesting difference between these options is whether the resulting semantics are "monotone" with respect to provenance: is "increasing" the provenance of a value (i.e., letting it access more memory) a legal program transformation?
462 With the last two options, it is not, since adding provenance to a value that did not have it can introduce Undefined Behavior.
463 The first two options are "monotone" in this sense, which seems like a nice property.
464 (This is comparable to how the semantics are "monotone" with respect to `undef` and `poison`: replacing either of them by a fixed value is a legal program transformation. For `undef`/`poison` this is crucially important, for provenance it seems more like a sanity check of the semantics.)
465
466 In all of these cases except the last one, LLVM would probably need something like a [byte type](https://gist.github.com/georgemitenkov/3def898b8845c2cc161bd216cbbdb81f) so that a load of arbitrary data (including a pointer with provenance) can be done without losing the provenance attached to the data.
467
468 A similar question arises for doing a pointer-typed load of a bare integer (integer-pointer transmutation):
469 1. The load could have the effects of a `inttoptr`. This is less clearly bad than a `ptrtoint`, but is still tricky since (at least without extra work) `inttoptr` is non-deterministic and depends on the global set of exposed provenances (so, it cannot be easily reordered up across potentially exposing operations).
470   I also have [another example](https://github.com/rust-lang/unsafe-code-guidelines/issues/286#issuecomment-860189806) showing that if *both* pointer-integer transmutation and integer-pointer transmutation work like the corresponding casts (i.e., if the first of my options is picked for both loads of pointers at integer type, and integers at pointer type), then more optimizations fail:
471   removing a store that follows a load and just writes back the same value that has just been loaded is no longer correct.
472   Yet, I think this is what PNVI-ae-udi mandates. Again I hope Rust can opt-out of this.
473 2. The load could create a pointer with "invalid" provenance.
474   That means transmutation of a pointer to an integer and back produces a pointer that cannot be used to access memory, but avoids all the analysis difficulties that come with an `inttoptr`.
475   This is what I think would be best for Rust.
476 3. The load could produce `poison`, but I see no good reason for doing that.
477
478 Since LLVM generally errs on the side of delaying UB as long as possible if that is not in conflict with optimizations, the second option for both questions feels most "on-brand" to me personally -- but in the end, these are some hard choices that the LLVM community will have to make.
479 I can help evaluate these trade-offs by giving structure to the design space and pointing out the inevitable consequences of certain decisions, but I can only lend a hand here -- while I think and care a lot about LLVM semantics, I haven't done any direct work on LLVM myself.
480 I am also not enough of an expert for which optimizations are important and the performance impact of the various options here, so I hope we can get people with that kind of background involved in the discussion as well.
481 For the sake of the entire ecosystem I mostly hope that LLVM will make *some* choice so that we can, eventually, leave this limbo state we are currently in.
482
483 #### Footnotes