X-Git-Url: https://git.ralfj.de/web.git/blobdiff_plain/9fecf69dc7af127a585a1b3ac8aa53d983c4104a..dde32ff9b91932b3874aef01377732ba78900536:/ralf/_posts/2018-07-24-pointers-and-bytes.md

diff --git a/ralf/_posts/2018-07-24-pointers-and-bytes.md b/ralf/_posts/2018-07-24-pointers-and-bytes.md
index b3a74c4..05690b3 100644
--- a/ralf/_posts/2018-07-24-pointers-and-bytes.md
+++ b/ralf/_posts/2018-07-24-pointers-and-bytes.md
@@ -19,7 +19,7 @@ I hope that by the end of this post, you will agree with me on both of these sta
 ## 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.)
+(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. C has all the same issues, as does unsafe Rust.)
 {% highlight c++ %}
 int test() {
     auto x = new int[8];
@@ -130,21 +130,40 @@ 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.
 
+## The Model Falls Apart
+
 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.
+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).
+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.
+
+This 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).
+In our abstract machine, there is no single coherent "address space" that all allocations live in, that we could use to map every pointer to a distinct integer.
+Every allocation is just identified by an (unobservable) ID.
+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.
+The point it to discuss the *need* for such a model.
+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.
+
+Long story short, pointer-integer casts are messy and hard to define formally when also considering optimizations like we discussed above.
+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.
+We mostly just ignore the problem in miri and opportunistically do as much as we can, given the simple model we are working with.
 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).
+To my knowledge, no satisfying solution exists, but academic research is [getting 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`.
+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.
 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`.
+We have to say what the value of `v` is, so we have to find some way to answer this question.
+(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`.)
+
+We cannot represent a byte of a pointer as an element of `0..256`.
 Instead, we will remember both the pointer, and which byte of the pointer we got.
+So, a byte is now *either* an element of `0..256` ("raw bits"), *or* the n-th byte of some abstract pointer.
 If we were to implement our memory model in Rust, this might look as follows:
 {% highlight rust %}
 enum ByteV1 {
@@ -153,12 +172,12 @@ enum ByteV1 {
 }
 {% 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.
+This way, `memcpy` can "take apart" a pointer into the individual bytes that represent this pointer in memory, and copy them separately.
 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.
+Such a representation supports performing all byte-level "data moving" operations on pointers, which is sufficient for `memcpy`.
 Arithmetic or bit-level operations are not fully supported; as already mentioned above, that requires a more sophisticated pointer representation.
 
 ## Uninitialized Memory
@@ -209,6 +228,7 @@ Using `Uninit` instead of an arbitrary bit pattern means miri can, in a single e
 ## Conclusion
 
 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`.
+This is also why calling C "portable assembly" may have been appropriate in 1978, but is a dangerously misleading statement nowadays.
 With this, I think we are ready to look at a first draft of my "2018 memory model" (working title ;) -- in the next post. :)
 
 Thanks to @rkruppe and @nagisa for help in finding arguments for why `Uninit` is needed.