+++ /dev/null
----
-title: "Pointers Are Complicated, or: What's in a Byte?"
-categories: internship rust
----
-
-This summer, I am again [working on Rust full-time]({{ site.baseurl }}{% post_url 2018-07-11-research-assistant %}), and again I will work (amongst other things) on a "memory model" for Rust/MIR.
-However, before I can talk about the ideas I have for this year, I have to finally take the time and dispel the myth that "pointers are simple: they are just integers".
-Both parts of this statement are false, at least in languages with unsafe features like Rust or C: Pointers are neither simple nor (just) integers.
-
-I also want to define a piece of the memory model that has to be fixed before we can even talk about some of the more complex parts: Just what *is* the data that is stored in memory?
-It is organized in bytes, the minimal addressable unit and the smallest piece that can be accessed (at least on most platforms), but what are the possible values of a byte?
-Again, it turns out "it's just an 8-bit integer" does not actually work as the answer.
-
-I hope that by the end of this post, you will agree with me on both of these statements. :)
-
-<!-- MORE -->
-
-## Pointers Are Complicated
-
-What is the problem with "pointers are just integers"? Let us consider the following example:<br>
-(I am using C++ code here mostly because writing unsafe code is easier in C++, and unsafe code is where these problems really show up.)
-{% highlight c++ %}
-int test() {
- auto x = new int[8];
- auto y = new int[8];
- y[0] = 42;
- int i = /* some side-effect-free computation */;
- auto x_ptr = &x[i];
- *x_ptr = 23;
- return y[0];
-}
-{% endhighlight %}
-It would be beneficial to be able to optimize the final read of `y[0]` to just return `42`.
-The justification for this optimization is that writing to `x_ptr`, which points into `x`, cannot change `y`.
-
-However, given how low-level a language C++ is, we can actually break this assumption by setting `i` to `y-x`.
-Since `&x[i]` is the same as `x+i`, this means we are actually writing `23` to `&y[0]`.
-
-Of course, that does not stop C++ compilers from doing these optimizations.
-To allow this, the standard declares our code to have [undefined behavior]({{ site.baseurl }}{% post_url 2017-07-14-undefined-behavior %}).
-
-First of all, it is not allowed to perform pointer arithmetic (like `&x[i]` does) that goes [beyond either end of the array it started in](https://timsong-cpp.github.io/cppwp/n4140/expr.add#5).
-Our program violates this rule: `x[i]` is outside of `x`, so this is undefined behavior.
-To be clear: Just the *computation* of `x_ptr` is already UB, we don't even get to the part where we want to *use* this pointer![^1]
-
-[^1]: It turns out that `y-x` is also undefined behavior because [one may only subtract pointers into the same allocation](https://timsong-cpp.github.io/cppwp/n4140/expr.add#6). However, we could use `i = ((size_t)y - (size_t)x)/sizeof(int)` to work around that.
-
-But we are not done yet: This rule has a special exception that we can exploit to our advantage.
-If the arithmetic ends up computing a pointer *just past* the end of an allocation, that computation is fine.
-(This exception is necessary to permit computing `vec.end()` for the usual kind of C++98 iterator loop.)
-
-So let us change this example a bit:
-{% highlight c++ %}
-int test() {
- auto x = new int[8];
- auto y = new int[8];
- y[0] = 42;
- auto x_ptr = &x[8]; // one past the end
- if (x_ptr == &y[0])
- *x_ptr = 23;
- return y[0];
-}
-{% endhighlight %}
-Now, imagine that `x` and `y` have been allocated *right next to each other*, with `y` having the higher address.
-Then `x_ptr` actually points *right at the beginning* of `y`!
-The conditional is true and the write happens.
-Still, there is no UB due to out-of-bounds pointer arithmetic.
-
-This seems to break the optimization.
-However, the C++ standard has another trick up its sleeve to help compiler writers: It doesn't actually allow us to *use* our `x_ptr` above.
-According to what the standard says about [addition on pointers](https://timsong-cpp.github.io/cppwp/n4140/expr.add#5), `x_ptr` points "one past the last element of the array object".
-It does *not* point at an actual element of another object *even if they have the same address*. (At least, that is the common interpretation of the standard based on which [LLVM optimizes this code](https://godbolt.org/g/vxmtej).)
-
-The key point here is that just because `x_ptr` and `&y[0]` point to the same *address*, that does not make them *the same pointer*, i.e., they cannot be used interchangeably:
-`&y[0]` points to the first element of `y`; `x_ptr` points past the end of `x`.
-If we replace `*x_ptr = 23` by `*&y[0] = 0`, we change the meaning of the program, even though the two pointers have been tested for equality.
-
-This is worth repeating:
-
-> *Just because two pointers point to the same address, does not mean they are equal and can be used interchangeably.*
-
-If this sounds subtle, it is.
-In fact, this still causes miscompilations in both [LLVM](https://bugs.llvm.org/show_bug.cgi?id=35229) and [GCC](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752).
-
-Also notice that this one-past-the-end rule is not the only part of C/C++ where this effect can be witnessed.
-Another example is the [`restrict`](https://en.wikipedia.org/wiki/Restrict) keyword in C, which can be used to express that pointers do not alias:
-{% highlight c %}
-int foo(int *restrict x, int *restrict y) {
- *x = 42;
- if (x == y) {
- *y = 23;
- }
- return *x;
-}
-
-int test() {
- int x;
- return foo(&x, &x);
-}
-{% endhighlight %}
-Calling `test()` triggers UB because the two accesses in `foo` must not alias.
-Replacing `*y` by `*x` in `foo` changes the meaning of the program such that it no longer has UB.
-So, again, even though `x` and `y` have the same address, they cannot be used interchangeably.
-
-Pointers are definitely not integers.
-
-## A Simple Pointer Model
-
-So, what *is* a pointer?
-I don't know the full answer to this.
-In fact, this is an open area of research.
-
-Here's a simple proposal (in fact, this is the model used in my [RustBelt work]({{ site.baseurl }}{% post_url 2017-07-08-rustbelt %}), and it is also how [miri](https://github.com/solson/miri/) implements pointers):
-A pointer is a pair of some kind of ID uniquely identifying the *allocation*, and an *offset* into the allocation.
-Adding/subtracting an integer to/from a pointer just acts on the offset, and can thus never leave the allocation.
-Subtracting a pointer from another is only allowed when both point to the same allocation (matching [C++](https://timsong-cpp.github.io/cppwp/n4140/expr.add#6)).[^2]
-
-[^2]: As we have seen, the C++ standard actually applies these rules on the level of arrays, not allocations. However, LLVM applies the rule on a [per-allocation level](https://llvm.org/docs/LangRef.html#getelementptr-instruction).
-
-It turns out (and miri shows) that this model can get us very far.
-We always remember which allocation a pointer points to, so we can differentiate a pointer "one past the end" of one allocation from a pointer to the beginning of another allocation.
-That's how miri can detect that our second example (with `&x[8]`) is UB.
-
-In this model, pointers are not integers, but they are at least simple.
-However, this simple model starts to fall apart once you consider pointer-integer casts.
-In miri, casting a pointer to an integer does not actually do anything, we now just have an integer variable whose value is a pointer (i.e., an allocation-offset pair).
-Multiplying that integer by 2 leads to an error, because it is entirely unclear what it means to multiply such a pair by 2.
-A full definition of a language like C++ or Rust of course cannot take this shortcut, it has to explain what really happens here.
-To my knowledge, no satisfying solution exists, but we are [getting](http://www.cis.upenn.edu/%7Estevez/papers/KHM+15.pdf) [closer](http://sf.snu.ac.kr/publications/llvmtwin.pdf).
-This is why pointers are not simple, either.
-
-## From Pointers to Bytes
-
-I hope I made a convincing argument that integers are not the only data one has to consider when formally specifying low-level languages such as C++ or (the unsafe parts of) Rust.
-However, this means that a simple operation like loading a byte from memory cannot just return a `u8`.
-What if that byte is part of a pointer? When a pointer is a pair of allocation and offset, what is its first byte?
-We cannot represent this as a `u8`.
-Instead, we will remember both the pointer, and which byte of the pointer we got.
-If we were to implement our memory model in Rust, this might look as follows:
-{% highlight rust %}
-enum ByteV1 {
- Bits(u8),
- PtrFragment(Pointer, u8),
-}
-{% endhighlight %}
-For example, a `PtrFragment(ptr, 0)` represents the first byte of `ptr`.
-This way, we can "take apart" a pointer into the individual bytes that represent this pointer in memory, and assemble it back together.
-On a 32bit architecture, the full value representing `ptr` consists of the following 4 bytes:
-```
-[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
-```
-Such a representation supports performing all byte-level "data moving" operations on pointers, like implementing `memcpy` by copying one byte at a time.
-Arithmetic or bit-level operations are not fully supported; as already mentioned above, that requires a more sophisticated pointer representation.
-
-## Uninitialized Memory
-
-However, we are not done yet with our definition of a "byte".
-To fully describe program behavior, we need to take one more possibility into account: A byte in memory could be *uninitialized*.
-The final definition for a byte (assuming we have a type `Pointer` for pointers) thus looks as follows:
-{% highlight rust %}
-enum Byte {
- Bits(u8),
- PtrFragment(Pointer, u8),
- Uninit,
-}
-{% endhighlight %}
-
-`Uninit` is the value we use for all bytes that have been allocated, but not yet written to.
-Reading uninitialized memory is fine, but actually *doing* anything with those bytes (like, using them in integer arithmetic) is undefined behavior.
-
-This is very similar to the rules LLVM has for its special value called `poison`.
-Note that LLVM *also* has a value called `undef`, which it uses for uninitialized memory and which works somewhat differently -- however, compiling our `Uninit` to `undef` is actually correct (`undef` is in some sense "weaker"), and there are proposals to [remove `undef` from LLVM and use `poison` instead](http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf).
-
-You may wonder why we have a special `Uninit` value at all.
-Couldn't we just pick some arbitrary `b: u8` for each newly allocated byte, and then use `Bits(b)` as the initial value?
-That would indeed also be an option.
-However, first of all, pretty much all compilers have converged to having a sentinel value for uninitialized memory.
-Not doing that would not only pose trouble when compiling through LLVM, it would also require reevaluating many optimizations to make sure they work correctly with this changed model.
-The key point is that it is always safe, during compilation, to replace `Uninit` by any value: Any operation that actually observes this value is UB anyway.
-
-For example, the following C code becomes easier to optimize with `Uninit`:
-{% highlight c %}
-int test() {
- int x;
- if (condA()) x = 1;
- // Lots of hard to analyze code that will definitely return when condA()
- // does NOT hold, but will not change x.
- use(x); // want to optimize x to 1.
-}
-{% endhighlight %}
-With `Uninit`, we can easily argue that `x` is either `Uninit` or `1`, and since replacing `Uninit` by `1` is okay, the optimization is easily justified.
-Without `Uninit`, however, `x` is either "some arbitrary bit pattern" or `1`, and doing the same optimization becomes much harder to justify.[^3]
-
-[^3]: We could argue that we can reorder when the non-deterministic choice is made, but then we have to prove that the hard to analyze code does not observe `x`. `Uninit` avoids that unnecessary extra proof burden.
-
-Finally, `Uninit` is also a better choice for interpreters like miri.
-Such interpreters have a hard time dealing with operations of the form "just choose any of these values" (i.e., non-deterministic operations), because if they want to fully explore all possible program executions, that means they have to try every possible value.
-Using `Uninit` instead of an arbitrary bit pattern means miri can, in a single execution, reliably tell you if your programs uses uninitialized values incorrectly.
-
-## Conclusion
-
-We have seen that pointers can be different even when they point to the same address, and that a byte is more than just a number in `0..256`.
-With this, I think we are ready to look at a first draft of my "2018 memory model" (working title ;) -- in the next post. :)
-<!-- If you have any questions, feel free to [ask in the forums]! -->
-
-#### Footnotes
projects / web.git / blobdiff