(hopefully) final tweaks
[web.git] / personal / _posts / 2018-07-24-pointers-and-bytes.md
1 ---
2 title: "Pointers Are Complicated, or: What's in a Byte?"
3 categories: internship rust
4 forum: https://internals.rust-lang.org/t/pointers-are-complicated-or-whats-in-a-byte/8045
5 ---
6
7 This summer, I am again [working on Rust full-time]({% post_url 2018-07-11-research-assistant %}), and again I will work (amongst other things) on a "memory model" for Rust/MIR.
8 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".
9 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.
10
11 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?
12 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?
13 Again, it turns out "it's just an 8-bit integer" does not actually work as the answer.
14
15 I hope that by the end of this post, you will agree with me on both of these statements. :)
16
17 <!-- MORE -->
18
19 ## Pointers Are Complicated
20
21 What is the problem with "pointers are just integers"?  Let us consider the following example:<br>
22 (I am using C++ code here mostly because writing unsafe code is easier in C++ than in Rust, and unsafe code is where these problems really show up. C has all the same issues, as does unsafe Rust.)
23 {% highlight c++ %}
24 int test() {
25     auto x = new int[8];
26     auto y = new int[8];
27     y[0] = 42;
28     int i = /* some side-effect-free computation */;
29     auto x_ptr = &x[i];
30     *x_ptr = 23;
31     return y[0];
32 }
33 {% endhighlight %}
34 It would be beneficial to be able to optimize the final read of `y[0]` to just return `42`.
35 C++ compilers regularly perform such optimizations as they are crucial for generating high-quality assembly.[^perf]
36 The justification for this optimization is that writing to `x_ptr`, which points into `x`, cannot change `y`.
37
38 [^perf]: To be fair, the are *claimed* to be crucial for generating high-quality assembly. The claim sounds plausible to me, but unfortunately, I do not know of a systematic study exploring the performance benefits of such optimizations.
39
40 However, given how low-level a language C++ is, we can actually break this assumption by setting `i` to `y-x`.
41 Since `&x[i]` is the same as `x+i`, this means we are actually writing `23` to `&y[0]`.
42
43 Of course, that does not stop C++ compilers from doing these optimizations.
44 To allow this, the standard declares our code to have [undefined behavior]({% post_url 2017-07-14-undefined-behavior %}).[^0]
45
46 [^0]: An argument could be made that compilers should just not do such optimizations to make the programming model simpler. This is a discussion worth having, but the point of this post is not to explore this trade-off, it is to explore the consequences of the choices made in C++.
47
48 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).
49 Our program violates this rule: `x[i]` is outside of `x`, so this is undefined behavior.
50 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]
51
52 [^1]: It turns out that `i = 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.
53
54 But we are not done yet: This rule has a special exception that we can exploit to our advantage.
55 If the arithmetic ends up computing a pointer *just past* the end of an allocation, that computation is fine.
56 (This exception is necessary to permit computing `vec.end()` for the usual kind of C++98 iterator loop.)
57
58 So let us change this example a bit:
59 {% highlight c++ %}
60 int test() {
61     auto x = new int[8];
62     auto y = new int[8];
63     y[0] = 42;
64     auto x_ptr = x+8; // one past the end
65     if (x_ptr == &y[0])
66       *x_ptr = 23;
67     return y[0];
68 }
69 {% endhighlight %}
70 Now, imagine that `x` and `y` have been allocated *right next to each other*, with `y` having the higher address.
71 Then `x_ptr` actually points *right at the beginning* of `y`!
72 The conditional is true and the write happens.
73 Still, there is no UB due to out-of-bounds pointer arithmetic.
74
75 This seems to break the optimization.
76 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.
77 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".
78 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).)
79
80 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:
81 `&y[0]` points to the first element of `y`; `x_ptr` points past the end of `x`.
82 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.
83
84 This is worth repeating:
85
86 > *Just because two pointers point to the same address, does not mean they are equal and can be used interchangeably.*
87
88 If this sounds subtle, it is.
89 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).
90
91 Also notice that this one-past-the-end rule is not the only part of C/C++ where this effect can be witnessed.
92 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:
93 {% highlight c %}
94 int foo(int *restrict x, int *restrict y) {
95     *x = 42;
96     if (x == y) {
97         *y = 23;
98     }
99     return *x;
100 }
101
102 int test() {
103     int x;
104     return foo(&x, &x);
105 }
106 {% endhighlight %}
107 Calling `test()` triggers UB because the two accesses in `foo` must not alias.
108 Replacing `*y` by `*x` in `foo` changes the meaning of the program such that it no longer has UB.
109 So, again, even though `x` and `y` have the same address, they cannot be used interchangeably.
110
111 Pointers are definitely not integers.
112
113 ## A Simple Pointer Model
114
115 So, what *is* a pointer?
116 I don't know the full answer to this.
117 In fact, this is an open area of research.
118
119 One important point to stress here is that we are just looking for an *abstract model* of the pointer.
120 Of course, on the actual machine, pointers are integers.
121 But the actual machine also does not do the kind of optimizations that modern C++ compilers do, so it can get away with that.
122 If we wrote the above programs in assembly, there would be no UB, and no optimizations.
123 C++ and Rust employ a more "high-level" view of memory and pointers, restricting the programmer for the benefit of optimizations.
124 When formally describing what the programmer may and may not do in these languages, as we have seen, the model of pointers as integers falls apart, so we have to look for something else.
125 This is another example of using a "virtual machine" that's different from the real machine for specification purposes, which is an idea [I have blogged about before]({% post_url 2017-06-06-MIR-semantics %}).
126
127 Here's a simple proposal (in fact, this is the model of pointers used in [CompCert](https://hal.inria.fr/hal-00703441/document) and my [RustBelt work]({% post_url 2017-07-08-rustbelt %}), and it is also how [miri](https://github.com/solson/miri/) implements [pointers](https://github.com/rust-lang/rust/blob/fefe81605d6111faa8dbb3635ab2c51d59de740a/src/librustc/mir/interpret/mod.rs#L121-L124)):
128 A pointer is a pair of some kind of ID uniquely identifying the *allocation*, and an *offset* into the allocation.
129 If we defined this in Rust, we might write
130 {% highlight rust %}
131 struct Pointer {
132     alloc_id: usize,
133     offset: isize,
134 }
135 {% endhighlight %}
136 Adding/subtracting an integer to/from a pointer just acts on the offset, and can thus never leave the allocation.
137 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]
138
139 [^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).
140
141 It turns out (and miri shows) that this model can get us very far.
142 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.
143 That's how miri can detect that our second example (with `&x[8]`) is UB.
144
145 ## The Model Falls Apart
146
147 In this model, pointers are not integers, but they are at least simple.
148 However, this simple model starts to fall apart once you consider pointer-integer casts.
149 In miri, casting a pointer to an integer does not actually do anything, we now just have an integer variable (i.e., its *type* says it is an integer) whose *value* is a pointer (i.e., an allocation-offset pair).
150 However, multiplying that "integer" by 2 leads to an error, because it is entirely unclear what it means to multiply such an abstract pointer by 2.
151
152 I should clarify that this is *not* a good solution when defining language semantics.
153 It works fine for an interpreter though.
154 It is the most lazy thing to do, and we do it because it is not clear what else to do (other than not supporting these casts at all -- but this way, miri can run more programs):
155 In our abstract machine, there just is no single coherent "address space" that all allocations live in, that we could use to map every pointer to a distinct integer.
156 Every allocation is just identified by an (unobservable) ID.
157 We could now start to enrich this model with extra data like a base address for each allocation, and somehow use that when casting an integer back to a pointer... but that's where it gets really complicated, and anyway discussing such a model is not the point of this post.
158 The point it to discuss the *need* for such a model.
159 If you are interested, I suggest you read [this paper](http://www.cis.upenn.edu/%7Estevez/papers/KHM+15.pdf) that explores the above idea of adding a base address.
160
161 Long story short, pointer-integer casts are messy and hard to define formally when also considering optimizations like we discussed above.
162 There is a conflict between the high-level view that is required to enable optimizations, and the low-level view that is required to explain casting a pointer to an integer and back.
163 We mostly just ignore the problem in miri and opportunistically do as much as we can, given the simple model we are working with.
164 A full definition of a language like C++ or Rust of course cannot take this shortcut, it has to explain what really happens here.
165 To my knowledge, no satisfying solution exists, but academic research is [getting closer](http://sf.snu.ac.kr/publications/llvmtwin.pdf).
166
167 **Update:** This was by no means meant to be an exhaustive list of academic research on C in general. I do not know of other work that focuses directly on the interplay of integer-pointer casts and optimizations, but other noteworthy work on formalizing C includes [KCC](https://github.com/kframework/c-semantics), [Robbert Krebber's PhD thesis](https://robbertkrebbers.nl/thesis.html) and [Cerberus](https://www.cl.cam.ac.uk/~pes20/cerberus/). **/Update**
168
169 This is why pointers are not simple, either.
170
171 ## From Pointers to Bytes
172
173 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.
174 However, this means that a simple operation like loading a byte from memory cannot just return a `u8`.
175 Imagine we [implement `memcpy`](https://github.com/alexcrichton/rlibc/blob/defb486e765846417a8e73329e8c5196f1dca49a/src/lib.rs#L39) by loading (in turn) every byte of the source into some local variable `v`, and then storing it to the target.
176 What if that byte is part of a pointer?  When a pointer is a pair of allocation and offset, what is its first byte?
177 We have to say what the value of `v` is, so we have to find some way to answer this question.
178 (And this is an entirely separate issue from the problem with multiplication that came up in the last section. We just assume some abstract type `Pointer`.)
179
180 We cannot represent a byte of a pointer as an element of `0..256`.
181 Essentially, if we use a naive model of memory, the extra "hidden" part of a pointer (the one that makes it more than just an integer) would be lost when a pointer is stored to memory and loaded again.
182 We have to fix this, so we have to extend our notion of a "byte" to accomodate that extra state.
183 So, a byte is now *either* an element of `0..256` ("raw bits"), *or* the n-th byte of some abstract pointer.
184 If we were to implement our memory model in Rust, this might look as follows:
185 {% highlight rust %}
186 enum ByteV1 {
187   Bits(u8),
188   PtrFragment(Pointer, u8),
189 }
190 {% endhighlight %}
191 For example, a `PtrFragment(ptr, 0)` represents the first byte of `ptr`.
192 This way, `memcpy` can "take apart" a pointer into the individual bytes that represent this pointer in memory, and copy them separately.
193 On a 32bit architecture, the full value representing `ptr` consists of the following 4 bytes:
194 ```
195 [PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
196 ```
197 Such a representation supports performing all byte-level "data moving" operations on pointers, which is sufficient for `memcpy`.
198 Arithmetic or bit-level operations are not fully supported; as already mentioned above, that requires a more sophisticated pointer representation.
199
200 ## Uninitialized Memory
201
202 However, we are not done yet with our definition of a "byte".
203 To fully describe program behavior, we need to take one more possibility into account: A byte in memory could be *uninitialized*.
204 The final definition for a byte (assuming we have a type `Pointer` for pointers) thus looks as follows:
205 {% highlight rust %}
206 enum Byte {
207   Bits(u8),
208   PtrFragment(Pointer, u8),
209   Uninit,
210 }
211 {% endhighlight %}
212
213 `Uninit` is the value we use for all bytes that have been allocated, but not yet written to.
214 Reading uninitialized memory is fine, but actually *doing* anything with those bytes (like, using them in integer arithmetic) is undefined behavior.
215
216 This is very similar to the rules LLVM has for its special value called `poison`.
217 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).
218
219 You may wonder why we have a special `Uninit` value at all.
220 Couldn't we just pick some arbitrary `b: u8` for each newly allocated byte, and then use `Bits(b)` as the initial value?
221 That would indeed also be an option.
222 However, first of all, pretty much all compilers have converged to having a sentinel value for uninitialized memory.
223 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.
224 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.
225
226 For example, the following C code becomes easier to optimize with `Uninit`:
227 {% highlight c %}
228 int test() {
229     int x;
230     if (condA()) x = 1;
231     // Lots of hard to analyze code that will definitely return when condA()
232     // does NOT hold, but will not change x.
233     use(x); // want to optimize x to 1.
234 }
235 {% endhighlight %}
236 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.
237 Without `Uninit`, however, `x` is either "some arbitrary bit pattern" or `1`, and doing the same optimization becomes much harder to justify.[^3]
238
239 [^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.
240
241 Finally, `Uninit` is also a better choice for interpreters like miri.
242 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.
243 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.
244
245 **Update:** Since writing this section, I have written an entire [post dedicated to uninitialized memory and "real hardware"]({% post_url 2019-07-14-uninit %}) with more details, examples and references. **/Update**
246
247 ## Conclusion
248
249 We have seen that in languages like C++ and Rust (unlike on real hardware), 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`.
250 This is also why calling C "portable assembly" may have been appropriate in 1978, but is a dangerously misleading statement nowadays.
251 With this, I think we are ready to look at a first draft of my "2018 memory model" (working title ;) -- in the next post. :)
252
253 Thanks to @rkruppe and @nagisa for help in finding arguments for why `Uninit` is needed.
254 If you have any questions, feel free to [ask in the forums](https://internals.rust-lang.org/t/pointers-are-complicated-or-whats-in-a-byte/8045)!
255
256 #### Footnotes