ralf/_posts/2018-01-31-sharing-for-a-lifetime.md

   1 ---
   2 title: "Sharing for a Lifetime"
   3 categories: research rust
   4 forum: https://internals.rust-lang.org/t/sharing-for-a-lifetime/6675
   5 ---
   6
   7 This post is about an aspect of the [RustBelt paper]({% post_url 2017-07-08-rustbelt %}).
   8 Concretely, I'd like to share some of our thoughts on the nature of types and shared references.
   9 Let's see how well this goes. :)
  10
  11 Shared references are an extremely powerful mechanism in the Rust type system, and we've had quite some trouble finding a good way of handling them in our [formal model]({% post_url 2015-10-12-formalizing-rust %}).
  12 In this post, I will present the model that we came up with.
  13 <!-- MORE -->
  14 Let's get started by discussing what a "model" of a type looks like, and what's so hard about handling shared references.
  15
  16 ## Immutable Sharing
  17
  18 The reason shared references are so subtle is [interior mutability](https://doc.rust-lang.org/1.22.0/reference/interior-mutability.html).
  19 This fundamentally changes the nature of shared references.
  20 To see how, I will briefly assume that Rust does *not* permit interior mutability, and describe how a model of Rust types could roughly look like.
  21
  22 ### What's in a Type?
  23
  24 I've already [written]({% post_url 2015-10-12-formalizing-rust %}) [about]({% post_url 2016-01-09-the-scope-of-unsafe %}) the idea of "semantic types", which essentially boils down to the concept that types can impose *additional invariants* on their fields, like `self.cap >= self.len` (for `Vec`) or `!is_zero(self.0)` (for `NonZero`).
  25 So, whenever I say "(semantic) type", I really mean "a type's (syntactic) definition (aka the data layout) **and** the additional invariants that the module imposes on this type".
  26 Two types may be syntactically equal but have different invariants, and then clearly casting from one to the other would be horribly unsafe -- so, these would be completely different types despite their syntactic similarity.
  27 What really matters for a type is the answer to the question: *Given some sequence of bytes, is this sequence a valid inhabitant of the type?*[^1]
  28 If we can answer this question for every Rust type, we have found a "(semantic) model" of the Rust type system.
  29 The (syntactic) data layout imposes some basic structure on the permitted sequences (like their length), but the invariants can arbitrarily *refine* the set of sequences that are allowed at the given type by imposing additional requirements.
  30 (Indeed, [refinement types](https://en.wikipedia.org/wiki/Refinement_(computing)#Refinement_types) are a way to reflect these additional restrictions into the type system, but that's not what I want to talk about today.)
  31
  32 [^1]: I should mention at this point that "sequences of bytes" is a subtle concept because of complications like uninitialized memory and pointers. I hope to come back to this in a future post; it should not matter much here.
  33
  34 For example, the sequence of four `0` bytes is valid at `i32` but not at `NonZero<i32>`.
  35 As another example, a pointer is valid at `Box<i32>` if it points to four bytes of *owned* memory[^2], and these four bytes are a valid `i32`.
  36 Finally, a pointer is valid at `&'a mut T` if it points to `size_of::<T>()` many bytes of memory[^3] that are *borrowed for lifetime `'a`*, and those bytes are valid at `T`.
  37
  38 [^2]: I will also mostly ignore how the concept of *ownership* can be made more precise.  If you want to dig deeper, the keyword is [separation logic](https://en.wikipedia.org/wiki/Separation_logic).  We had to extend separation logic to be able to handle borrowing as well, but the details of all of this don't matter for this post.    That's the plan, anyway.
  39
  40 [^3]: Yes, we do ignore unsized types here.
  41
  42 So, the path to handling shared references in our model seems clear:  We have to find out when a pointer is valid at `&'a T`.
  43 Since we ignore interior mutability, we can answer this question fairly easily (at least if don't want to go fully formal on this, which right now, we do not ;):  While the lifetime `'a` lasts, the pointer has to point to `size_of::<T>()` many *immutable* bytes of memory (meaning the bytes do not change during this lifetime; we impose no restrictions on earlier or later modifications); and moreover, those bytes are valid at `T`.
  44
  45 Given this model, we can now explain why `*x` works for *any* `x: &'a T` if `T: Copy`:
  46 The access can only happen during the lifetime `'a`, so we can dereference the pointer.
  47 Moreover, since `T: Copy`, we know that we can copy the bytes and have *both* sequences (the original and the copy) be valid at `T` (remember that "being a valid sequence" could impose ownership requirements like `Box<i32>` does, so this kind of duplication is not possible in general for all `T`).
  48 Finally, since we know the memory is immutable, we can do this access even though we don't fully own the memory:  We can rely on everyone else (i.e., other threads) also just performing read operations on this memory.
  49 Overall, we conclude that we did not violate any of the invariants imposed on `x`, and the data we copied is a valid `T`.
  50
  51 ## Interior Mutability
  52
  53 Interior mutability however breaks this model of `&'a T`:  We just cannot declare that the pointed-to memory is read-only in general.
  54 If we did, [`Cell::set`](https://doc.rust-lang.org/stable/std/cell/struct.Cell.html#method.set) and many more operations would be blatantly unsafe.
  55 Indeed this is the reason shared references are not called "immutable references" even though they are generally considered the dual of mutable references.
  56 (My personal thinking is that mutable references should really be called "unique references" to instill the point that the distinction between the two is about uniqueness, not about mutability.  Oh well.)
  57
  58 So, with our old model broken, what could we do instead?  Let us consider some examples.
  59
  60 ### `&Cell<T>`
  61
  62 Why is `Cell::set` a safe operation?
  63 The reason is twofold.
  64 First of all, `Cell<T>` is not `Sync`, so it is not possible to send an `&Cell<T>` from one thread to another.
  65 As a consequence, all shared references to a given `Cell` always reside in the same thread.
  66 This already excludes the possibility of data races.
  67 Secondly, `Cell<T>` does not permit obtaining a *deep pointer* into the data.
  68 So, changing a `Cell<Result<bool, i32>>` from `Ok(true)` to `Err(42)` cannot invalidate any pointers that still expect a `bool` in the `Result`.
  69
  70 Coming back to our model, we could say that `&'a Cell<T>` is a pointer that points to `size_of::<T>()` many bytes of memory that, for the duration of `'a`, may *be accessed by any code running in the current thread, but not by any other code*; and moreover, those bytes are valid at `T`.
  71 This definition forces `&Cell<T>` to *not* be `Send` (because the model refers to the "current thread", so changing that thread could violate the invariant) and hence `Cell<T>` must not be `Sync`.
  72 It also rules out pointers into a `Cell<Result<bool, i32>>`:  Say we would want to have a pointer to the `Ok` data, which would have type `&Cell<bool>`.
  73 We could not show that this pointer is actually valid at the given type, because anyone in the current thread could modify the (outer) `Cell<Result<bool, i32>>` at any time, and if they write an `Err(42)` in it they will violate the requirements that an `&Cell<bool>` only ever points to a valid `bool`!
  74 So, both of the restrictions that we discussed above follow directly from the invariant for `&Cell<T>`.
  75
  76 ### `&Mutex<T>`
  77
  78 Coming to `Mutex`, the justification for why `Mutex::lock` and `MutexGuard::deref_mut` are safe operations is again different:
  79 A `Mutex` implements *mutual exclusion* (hence the name), so only one thread can ever hold the lock.
  80 As a result, giving that thread mutable access to the inner data cannot result in any data races or other conflicts with other threads.
  81
  82 In the model (and I'm going to gloss over more and more details here), we will say that `&'a Mutex<T>` is valid if everyone accessing the memory it points to during the lifetime `'a` follows the locking discipline.
  83 A `MutexGuard` is valid if we actually own the lock of the corresponding `Mutex`.
  84 Together, this is sufficient to justify safety of all the `Mutex` and `MutexGuard` operations.
  85
  86 ## Sharing is Different
  87
  88 We now come back to the question: *When is a pointer valid at type `&'a T`?*
  89 As we have seen above, the answer to this question actually depends significantly on the type `T`!
  90 For `i32` or `bool`, our old read-only model still works, but for `Cell` or `Mutex`, we need entirely different invariants that are very specific to the respective type.
  91
  92 To be able to handle this diversity, we have to *change our idea of what a type is*.
  93 I've said above that a type is all about the question: *Given some sequence of bytes, is this sequence a valid inhabitant of the type?*
  94 We now extend this by saying a type *also* has to be able to answer the question: *Given a pointer and a lifetime, is this pointer a valid shared reference to this type for the given lifetime?*
  95 In other words, **every type gets to *pick* for itself what it means to share this type**.
  96
  97 While I let that sink in, let me remark that this also explains why Rust has `Send` *and* `Sync`, and why neither implies the other even though they seem so closely related.
  98 This has certainly puzzled me when I first learned about these marker traits.
  99 The reason is that `T` and `&T` are really very different types; the author of `T` picks the invariants for both of these types (mostly) *independently* -- so one of them being safe to send to another thread has no bearing on the other one.
 100
 101 The main consequence of this choice is that for every type with extra invariants, we have to pick *two* invariants:
 102 1. An invariant specifying the sequences of bytes that are valid for the *owned* case (this includes mutable references), and
 103 1. An invariant specifying the pointers that are valid for the *shared* case at a given lifetime.
 104
 105 In principle, this applies to *all* types, even types like `Vec` that don't really care about interior mutability themselves.
 106 However, because we have to handle types like `&Vec<Mutex<T>>`, we cannot just skip this problem; interior mutability as a feature "infects" the entire type system.
 107 This should however usually not be a big problem: `&'a Vec<T>` can just have the invariant that `len` and `cap` are read-only, and all the initialized elements of the vector are themselves shared for lifetime `'a`.
 108 This strategy of just using the shared invariant of the "inner type" and making the rest read-only should be applicable to the vast majority of types.
 109
 110 ## Unsharing
 111
 112 Of course, the two invariants making up a type cannot be entirely unrelated.
 113 First of all, given some `y: T`, it must be possible to somehow "start sharing" it and obtain `&y: &T`.
 114 Moreover, if `T: Copy`, then it must be possible to read `*x` where `x: &T` and obtain a copy of a `T`.
 115 This was automatically the case in our first model where sharing was uniformly defined as being read-only memory, but now that we made sharing "configurable", we have to explicitly require this property.
 116
 117 However, that's not enough: At some point, sharing will end, and some part of the program expects the owned invariant to hold again.
 118 Somehow, everything that happened when sharing started must be un-done -- I think of this as "un-sharing".
 119 This is tricky because shared references can be, well, shared (d'oh).
 120 Even for the simple case of read-only sharing, we need to make sure that *nobody* still uses the old read-only access to the memory covered by the shared reference.
 121 In Rust, this works because the lifetime of these old shared references will have expired when the "un-sharing" happens.
 122
 123 This is why, in our model, *sharing is inherently connected to a lifetime*.
 124 If you go back to what I wrote above about a type being two invariants, you will notice that the second invariant is about sharing an inhabitant of `T` *for some lifetime*.
 125 There is no sharing without a lifetime.
 126 Whenever you start sharing something (i.e., whenever a `&x` is created from previously owned data), our model demands that you announce the lifetime for which this sharing will last.
 127 Once the lifetime ends, un-sharing happens automatically, so we don't need to explicitly talk about it in our model.
 128 (Of course, the proof effort related to this does not just go away.  Indeed we now have to follow the rules for what one can do with things that are only owned for some lifetime, and those rules are restrictive enough to guarantee that un-sharing is always possible.)
 129
 130 ## Conclusion
 131
 132 I have explained the idea of types having a separate "sharing invariant" that we came up with in the RustBelt paper to be able to handle interior mutability.
 133 To my knowledge, this is the only formal treatment of interior mutability to date, so we were all kind of stabbing in the dark until we found an approach that worked.
 134 This is not so say that the last word on interior mutability has been spoken; there may well be other ways of justifying why `Mutex<T>` or `Cell<T>` are safe.
 135
 136 Either way, this model has certainly helped me not only in the formal work on RustBelt, but also in thinking about the Rust type system itself.
 137 For example, I briefly wondered why `Cell` is not covariant.
 138 Indeed, if `T <: U`, then it is perfectly safe to turn a `Cell<T>` into a `Cell<U>` -- that is to say, whenever some sequence of bytes is valid at `Cell<T>`, it is also valid at `Cell<U>`.
 139 (In fact, the owned invariant for `Cell<T>` is *exactly the same* as the one for `T`!)
 140 That's precisely what we need for covariance, right?
 141 Well, not exactly -- because our types have two invariants, we also have to require that whenever a pointer is a shared `Cell<T>`, it is a shared `Cell<U>`, and that is decisively *not* true!
 142 So, *owned* `Cell`s are covariant, but shared `Cell`s are not.
 143 One could think of an extension to the Rust type system that separates owned subtyping from shared subtyping, and then `Cell` could indeed be "owned-covariant".
 144
 145 In closing this post, I'd like to leave you with some more general thoughts.
 146 One way to explain the role of shared references in the Rust type system more abstractly is that `&T` switches `T` into "shared mode".
 147 Every type comes with two modes, "owned" and "shared", and we typically think only of the "owned" mode because that's the one that's relevant for `x: T`.
 148 However, Rust provides a way to switch into the other mode, and types can have a completely different "face" there -- for example, `Cell<T>` and `T` are *equal* in "owned" mode, but very different in "shared" mode.
 149 I don't know of any other type system having a comparable concept.
 150 However, I've also not seen Rust's shared references being discussed as a super-special magic feature (though, after doing this research, I think they are!) -- it's rather the mutable references that seem special due to their unique nature (and this *was* a revolution, called mutpocalypse).
 151 So, maybe this is some extremely ingenious idea that the Rust devs had without even realizing, or maybe it's just some artifact of our model that's not worth losing many words about.
 152 (I do have my opinion, of course. ;)
 153
 154 And then there is the question: Why exactly two modes? Would it be worth having more?
 155 I honestly don't know, but I had to think of this a while back when I read [this post by glaebhoerl](https://internals.rust-lang.org/t/impl-t-clone-for-cell-rc-t/5397), the first part of which I would translate as "`Cell` could be considered a mode".
 156
 157 If you have any comments or thoughts on this, please join the [discussion in the Rust forums](https://internals.rust-lang.org/t/sharing-for-a-lifetime/6675)!
 158 I'd also be interested in feedback on how understandable this post is; this is my first attempt at translating research results into a blog post.