add some comments to code snippets

[web.git] / personal / _posts / 2022-04-11-provenance-exposed.md

diff --git a/personal/_posts/2022-04-11-provenance-exposed.md b/personal/_posts/2022-04-11-provenance-exposed.md
index ae036243e1765f0312f550fa3b1d7e7a8f09cdf3..5265df60efbcfa4da7b7f33fed1498eed98d0b83 100644 (file)
--- a/personal/_posts/2022-04-11-provenance-exposed.md
+++ b/personal/_posts/2022-04-11-provenance-exposed.md
@@ -23,12 +23,14 @@ but even when compiling for AMD64 CPUs, compilers act "as if" pointers had such
 
 ## Dead cast elimination considered harmful
 
 
 ## Dead cast elimination considered harmful
 

-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`.
+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]

 This is comparable to the promise that a `&mut T` in Rust is unique.
 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.
 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`.
 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.
 
 This is comparable to the promise that a `&mut T` in Rust is unique.
 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.
 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`.
 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.
 

+[^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.
+

 With all that out of the way, consider the following program:
 {% highlight c %}
 #include <stdio.h>
 With all that out of the way, consider the following program:
 {% highlight c %}
 #include <stdio.h>


@@ -76,7 +78,7 @@ static int uwu(int *restrict x, int *restrict y) {
 
   int *y2 = y-1;
   uintptr_t y2addr = (uintptr_t)y2;
 
   int *y2 = y-1;
   uintptr_t y2addr = (uintptr_t)y2;

-  int *ptr = (int*)y2addr;
+  int *ptr = (int*)y2addr; // <-- using y2addr

   *ptr = 1;
 
   return *x;
   *ptr = 1;
 
   return *x;


@@ -102,12 +104,12 @@ static int uwu(int *restrict x, int *restrict y) {
   int *ptr = (int*)y2addr;
   *ptr = 1;
 
   int *ptr = (int*)y2addr;
   *ptr = 1;
 

-  return 0;
+  return 0; // <-- hard-coded return value

 }
 
 int main() {
 }
 
 int main() {

-  int i = 0;
-  int res = uwu(&i, &i);
+  int i[2] = {0, 0};
+  int res = uwu(&i[0], &i[1]);

   // Now this prints 0!
   printf("%d\n", res);
 }
   // Now this prints 0!
   printf("%d\n", res);
 }


@@ -115,9 +117,9 @@ int main() {
 We started out with a program that always prints `1`, and ended up with a program that always prints `0`.
 This is bad news. Our optimizations changed program behavior. That must not happen! What went wrong?
 
 We started out with a program that always prints `1`, and ended up with a program that always prints `0`.
 This is bad news. Our optimizations changed program behavior. That must not happen! What went wrong?
 

-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. 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.
+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.
+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.
+I will, for the rest of this post, assume that replacing `x` by `(int*)(uintptr_t)x` is always allowed.

 So, which of the optimizations is the wrong one?
 
 ## The blame game
 So, which of the optimizations is the wrong one?
 
 ## The blame game


@@ -161,7 +163,7 @@ To explain what that side-effect is, we have to get deep into the pointer proven
 Specifically, `x` has permission to access `i[0]` (declared in `main`), and `y` has permission to access `i[1]`.[^dyn]
 `y2` just inherits the permission from `y`.
 
 Specifically, `x` has permission to access `i[0]` (declared in `main`), and `y` has permission to access `i[1]`.[^dyn]
 `y2` just inherits the permission from `y`.
 

-[^dyn]: Actually, this is not quite 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 do not change anything.
+[^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.

 
 But which permission does `ptr` get?
 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.
 
 But which permission does `ptr` get?
 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.


@@ -417,7 +419,7 @@ I discussed above how my vision for Rust relates to the direction C is moving to
 What does that mean for the design space of LLVM?
 Which changes need to be made to fix (potential) miscompilations in LLVM and to make it compatible with these ideas for C and/or Rust?
 Here's the list of open problems I am aware of:
 What does that mean for the design space of LLVM?
 Which changes need to be made to fix (potential) miscompilations in LLVM and to make it compatible with these ideas for C and/or Rust?
 Here's the list of open problems I am aware of:

-- LLVM needs to stop [removing `inttoptr(ptrtoint(_))`](https://bugs.llvm.org/show_bug.cgi?id=34548) and stop doing [replacement of `==`-equal pointers](https://bugs.llvm.org/show_bug.cgi?id=35229).
+- LLVM needs 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).

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