serious revision of the intrusive collections post

[web.git] / personal / _drafts / safe-intrusive-collections-with-pinning.md

diff --git a/personal/_drafts/safe-intrusive-collections-with-pinning.md b/personal/_drafts/safe-intrusive-collections-with-pinning.md
index a845dc2392cdd0c6d626d942e8c60b9f9ddd2ba4..3074503f7474a38ee77db95df5f2ed3edbe70150 100644 (file)
--- a/personal/_drafts/safe-intrusive-collections-with-pinning.md
+++ b/personal/_drafts/safe-intrusive-collections-with-pinning.md
@@ -3,7 +3,7 @@ title: "Safe Intrusive Collections with Pinning"
 categories: rust
 ---
 
 categories: rust
 ---
 

-In my [last post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}), I talked about the new ["pinned references"](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md) which guarantee that the data at the memory it points to will not, ever, be moved elsewhere
+In my [last post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}), I talked about the new ["pinned references"](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md) which guarantee that the data at the memory it points to will not, ever, be moved elsewhere.

 I explained how they enable giving a safe API to code that could previously only be exposed with `unsafe`, and how one could go about proving such a thing.
 This post is about another application of pinned references---another API whose safety relies on the pinning guarantees: Intrusive collections.
 It turns out that pinned references can *almost* be used for this, but not quite.
 I explained how they enable giving a safe API to code that could previously only be exposed with `unsafe`, and how one could go about proving such a thing.
 This post is about another application of pinned references---another API whose safety relies on the pinning guarantees: Intrusive collections.
 It turns out that pinned references can *almost* be used for this, but not quite.


@@ -12,29 +12,34 @@ However, this can be fixed by extending the guarantees provided by pinned refere
 <!-- MORE -->
 
 The first part is going to explain how intrusive collections could benefit from `Pin`, were we to accept that additional guarantee.
 <!-- MORE -->
 
 The first part is going to explain how intrusive collections could benefit from `Pin`, were we to accept that additional guarantee.

-This part assumes some familiarity with the `Pin` API, but not with the formal notions I introduced previously.
+This part assumes some familiarity with the `Pin` API, but not with the formal model I introduced previously.

 
 In the second part, I am going to briefly sketch a formal perspective on intrusive collections and the extended pinning guarantees.
 
 In the second part, I am going to briefly sketch a formal perspective on intrusive collections and the extended pinning guarantees.

-This builds on the formal model I introduced in my last post.
+This builds on the formal notation I introduced in my last post.

 
 Finally, I will discuss a variant of our "running example" intrusive collection that this model can *not* handle, and how the model could be extended.
 This extended model will actually call for a change to the `Pin` API (or rather, for a revert to an earlier version).
 
 
 Finally, I will discuss a variant of our "running example" intrusive collection that this model can *not* handle, and how the model could be extended.
 This extended model will actually call for a change to the `Pin` API (or rather, for a revert to an earlier version).
 

-## Safe Intrusive Collections
+(Btw, I'm sorry for this blog post being *even longer* than the previous.  I guess I am just enjoying that there is no page limit (like there is in papers) when writing blog posts, so I can just ramble as much as I like.)
+
+## 1 Safe Intrusive Collections

 
 Intrusive collections typically are linked data structures that embed the links in the data they contain.
 In the words of the [intrusive-collections crate](https://crates.io/crates/intrusive-collections):
 
 Intrusive collections typically are linked data structures that embed the links in the data they contain.
 In the words of the [intrusive-collections crate](https://crates.io/crates/intrusive-collections):

-> The main difference between an intrusive collection and a normal one is that while normal collections allocate memory behind your back to keep track of a set of values, intrusive collections never allocate memory themselves and instead keep track of a set of objects. Such collections are called intrusive because they requires explicit support in objects to allow them to be inserted into a collection.
+> The main difference between an intrusive collection and a normal one is that while normal collections allocate memory behind your back to keep track of a set of *values*, intrusive collections never allocate memory themselves and instead keep track of a set of *objects*. Such collections are called intrusive because they requires explicit support in objects to allow them to be inserted into a collection.

 
 To make this work safely, we better make sure that the "objects" (allocated and managed by the user of the collection) are not moved around or deallocated while they are part of the collection.
 The intrusive-collections crate realizes this by taking ownership of the objects.
 The crate also offers a [more advanced API](https://docs.rs/intrusive-collections/0.7.0/intrusive_collections/#scoped-collections) that works with borrowed data, but in this case the objects must outlive the entire collection.
 This means we cannot add short-lived objects, e.g. stack-allocated objects, to a collection that was created further up the call chain.
 
 To make this work safely, we better make sure that the "objects" (allocated and managed by the user of the collection) are not moved around or deallocated while they are part of the collection.
 The intrusive-collections crate realizes this by taking ownership of the objects.
 The crate also offers a [more advanced API](https://docs.rs/intrusive-collections/0.7.0/intrusive_collections/#scoped-collections) that works with borrowed data, but in this case the objects must outlive the entire collection.
 This means we cannot add short-lived objects, e.g. stack-allocated objects, to a collection that was created further up the call chain.

+How could we go about lifting that restriction?

 
 

-### An Example Collection
+### 1.1 An Example Collection

 
 To get more concrete, consider the following example ([originally proposed by @cramertj](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-372432435)).
 
 To get more concrete, consider the following example ([originally proposed by @cramertj](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-372432435)).

-This is not *really* an intrusive collections, but it has all the same properties and problems: The collection involves pointers to elements allocated by the user, and hence risks dangling pointers if they get moved or deallocated:
+This is not *really* an intrusive collections, but it has all the same properties and problems: The collection involves pointers to elements allocated by the user, and hence risks dangling pointers if they get moved or deallocated.
+(If I were to make this a proper intrusive linked list, the code would be twice as long and I would most definitely get the re-linking wrong.
+I will leave [writing linked lists](http://cglab.ca/~abeinges/blah/too-many-lists/book/) to others.)

 {% highlight rust %}
 #![feature(pin, arbitrary_self_types, optin_builtin_traits)]
 
 {% highlight rust %}
 #![feature(pin, arbitrary_self_types, optin_builtin_traits)]
 


@@ -50,6 +55,7 @@ impl<T> !Unpin for Collection<T> {}
 
 struct Entry<T> {
     x: T,
 
 struct Entry<T> {
     x: T,

+    // set to Some if we are part of some collection

     collection: Cell<Option<*const Collection<T>>>,
 }
 impl<T> !Unpin for Entry<T> {}
     collection: Cell<Option<*const Collection<T>>>,
 }
 impl<T> !Unpin for Entry<T> {}


@@ -86,7 +92,7 @@ impl<T> Collection<T> {
 
 impl<T> Drop for Collection<T> {
     fn drop(&mut self) {
 
 impl<T> Drop for Collection<T> {
     fn drop(&mut self) {

-        // go through the entries to remove pointers to self as `collection`
+        // Go through the entries to remove pointers to collection

         for entry in self.objects.borrow().iter() {
             let entry : &Entry<T> = unsafe { &**entry };
             entry.collection.set(None);
         for entry in self.objects.borrow().iter() {
             let entry : &Entry<T> = unsafe { &**entry };
             entry.collection.set(None);


@@ -102,7 +108,7 @@ impl<T> Entry<T> {
 
 impl<T> Drop for Entry<T> {
     fn drop(&mut self) {
 
 impl<T> Drop for Entry<T> {
     fn drop(&mut self) {

-        // go through `collection` to remove this entry
+        // Go through collection to remove this entry

         if let Some(collection) = self.collection.get() {
             let collection : &Collection<T> = unsafe { &*collection };
             collection.objects.borrow_mut().retain(|ptr| *ptr != self as *const _);
         if let Some(collection) = self.collection.get() {
             let collection : &Collection<T> = unsafe { &*collection };
             collection.objects.borrow_mut().retain(|ptr| *ptr != self as *const _);


@@ -120,22 +126,24 @@ fn main() {
 }
 {% endhighlight %}
 This is lots of code.
 }
 {% endhighlight %}
 This is lots of code.

-It is not necessary to fully understand every last detail here.

 The high-level picture is as follows:
 The collection is represented by a `Vec` of raw pointers pointing to the entries.
 The high-level picture is as follows:
 The collection is represented by a `Vec` of raw pointers pointing to the entries.

-Every entry has a "parent" pointer back to the main collection.
+Every entry has a "parent" pointer `self.collection` back to the main collection.

 Inserting an entry into a collection involves adding it to the `Vec` and setting the collection pointer of the entry.
 When an entry is dropped, if it is in a collection, it gets removed from the `Vec`.
 Inserting an entry into a collection involves adding it to the `Vec` and setting the collection pointer of the entry.
 When an entry is dropped, if it is in a collection, it gets removed from the `Vec`.

-When the collection is dropped, all the entire have their collection pointer reset to `None`.
-This is demonstrated by the example code in `main`: First we add an entry containing `42` to the collection, and `print_all` shows that it is there.
-Then we `drop` the entry, and we can see it has vanished from the collection as well.
+When the collection is dropped, all the entries have their collection pointer reset to `None`.
+
+The example code in `main` demonstrates how the collection could be used: First we add an entry containing `42` to the collection.
+This is possible despite there being no guarantee that the entry will outlive the collection.
+`print_all` shows that it is there.
+Then we `drop` the entry while the collection still exists, and we can see it has vanished from the collection as well.

 
 Notice that using `Pin` in the `insert` method above is crucial: If the collection of the entry were to move around, their respective pointers would get stale!
 This is fundamentally the same problem as [`SelfReferential` in my previous post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}), and `Pin` helps.
 
 Notice that using `Pin` in the `insert` method above is crucial: If the collection of the entry were to move around, their respective pointers would get stale!
 This is fundamentally the same problem as [`SelfReferential` in my previous post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}), and `Pin` helps.

-This is very different from the intrusive-collections crate, and as a consequence, `insert` can be called with entries *that do not outlive the collection*.
+Thanks to this guarantee, and unlike in the intrusive-collections crate, `insert` can be called with entries *that do not outlive the collection*.

 With an [API for stack pinning](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension), we could even have put the `entry` in `main` on the stack.
 
 With an [API for stack pinning](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension), we could even have put the `entry` in `main` on the stack.
 

-### Pinning Is Not Enough
+### 1.2 Pinning Is Not Enough

 
 However, it turns out pinning as described so far is not enough to guarantee safety.
 Imagine we added the following method to `PinBox`:
 
 However, it turns out pinning as described so far is not enough to guarantee safety.
 Imagine we added the following method to `PinBox`:


@@ -155,7 +163,7 @@ impl<T> PinBox<T> {
 {% endhighlight %}
 `box_deallocate` is obviously safe on `Box` (we do not use any unsafe code).
 Moreover, from what I said so far, it is also safe to add to `PinBox`: While, technically, the data *does* get moved inside `box_deallocate`, that's just a NOP.
 {% endhighlight %}
 `box_deallocate` is obviously safe on `Box` (we do not use any unsafe code).
 Moreover, from what I said so far, it is also safe to add to `PinBox`: While, technically, the data *does* get moved inside `box_deallocate`, that's just a NOP.

-We essentially perform a `memcpy` followed by a `mem::forget`, so nothing really happens aside from calling `free` on the `Box` itself.
+We essentially perform a `memcpy` (the move in `box_deallocate`) followed by a `mem::forget`, so nothing really happens aside from calling `free` on the `Box` itself.

 
 Why is this a problem?  Well, we can now add an entry to a collection and then *deallocate the entry without calling `drop`*.
 This leads to a dangling pointer inside the collection, which is obviously bad:
 
 Why is this a problem?  Well, we can now add an entry to a collection and then *deallocate the entry without calling `drop`*.
 This leads to a dangling pointer inside the collection, which is obviously bad:


@@ -169,25 +177,29 @@ fn main() {
 }
 {% endhighlight %}
 
 }
 {% endhighlight %}
 

-### Requiring Drop To Be Run
+Now, `PinBox::deallocate` is pretty artificial, but in fact the [API for stack pinning](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension) that is drafted in the RFC, together with [`ManuallyDrop`](https://doc.rust-lang.org/beta/std/mem/union.ManuallyDrop.html), make it possible to obtain a `Pin<T>` to a stack-allocated `T` and subsequently pop the stack frame without calling `drop` on the `T`.
+That has the same effect as `PinBox::deallocate`: It renders our collection interface unsound.
+The concern about dropping pinned data is real.
+
+
+### 1.3 Requiring Drop To Be Run
+
+@cramertj has [suggested](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-374702107) to fix this situation by adding a new guarantee to `Pin`: *If the memory a `Pin<T>` points to is ever deallocated or otherwise invalidated, `drop` has been called on it*.
+This just changes the way we have to think about pinned data, but does not affect the API at all.

 
 

-We can fix this situation by declaring that *if the memory a `Pin<T>` points to is ever deallocated or otherwise invalidated, `drop` has been called on it*.

 Combining that with the guarantee about moving, we can summarize `Pin` as follows:
 
 > Given a `Pin<'a, T>`, the data it points to will remain at the given location until it is dropped.  In particular, if it is never dropped, it will remain at the given location forever.
 
 Under our new rules, `PinBox::deallocate` is bogus, and our collection works again.
 
 Combining that with the guarantee about moving, we can summarize `Pin` as follows:
 
 > Given a `Pin<'a, T>`, the data it points to will remain at the given location until it is dropped.  In particular, if it is never dropped, it will remain at the given location forever.
 
 Under our new rules, `PinBox::deallocate` is bogus, and our collection works again.
 

-Now, this function we added is pretty artificial, but in fact the [API for stack pinning](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension) that is drafted in the PR, together with [`ManuallyDrop`](https://doc.rust-lang.org/beta/std/mem/union.ManuallyDrop.html), make it possible to obtain a `Pin<T>` to a stack-allocated `T` and subsequently pop the stack frame without calling `drop` on the `T`.
-That has the same effect: It renders our collection interface unsound.
-
-Of course, the entire example is artificial as well, and it is not even a proper intrusive collection because the `Vec` is heap-allocated.
-However, a proper intrusive collection would have the same problem: When an entry in an intrusive doubly-linked list gets deallocated, we better make sure that the watch the pointers from the neighboring elements or else they will soon be dangling.
+And not just our artificial little example collection would benefit from this guarantee.
+A proper intrusive collection would have the same problem: When an entry in an intrusive doubly-linked list gets deallocated, we better make sure that we patch the pointers from the neighboring elements or else they will soon be dangling.

 Moreover, this has applications not just for container data structures but also for GC integration: When a stack-allocated root has been registered with the GC, we have to make sure it gets deregistered before the stack frame pops.
 In fact, the trick of using `ManuallyDrop` to cause havoc has originally been [discovered in the context of GC integration](https://internals.rust-lang.org/t/rust-1-20-caused-pinning-to-become-incorrect/6695).
 If `Pin` obtains the guarantee described above, a GC API can just take something along the lines of `Pin<GcRoot<T>>`, relying on the fact that `GcRoot::drop` will get called before this memory gets deallocated.
 
 Moreover, this has applications not just for container data structures but also for GC integration: When a stack-allocated root has been registered with the GC, we have to make sure it gets deregistered before the stack frame pops.
 In fact, the trick of using `ManuallyDrop` to cause havoc has originally been [discovered in the context of GC integration](https://internals.rust-lang.org/t/rust-1-20-caused-pinning-to-become-incorrect/6695).
 If `Pin` obtains the guarantee described above, a GC API can just take something along the lines of `Pin<GcRoot<T>>`, relying on the fact that `GcRoot::drop` will get called before this memory gets deallocated.
 

-### Some Common Objections
+### 1.4 Some Common Objections

 
 I hope I convinced you that it is desirable to guarantee that `drop` is run on pinned references.
 Before we come to the formal part of this post, let me go over some possible objections to this extended guarantee.
 
 I hope I convinced you that it is desirable to guarantee that `drop` is run on pinned references.
 Before we come to the formal part of this post, let me go over some possible objections to this extended guarantee.


@@ -195,35 +207,35 @@ In fact, I have been opposed to it initially myself, and went to the [Berlin All
 So I will just reiterate my own objections and how I feel about them now.
 
 The first objection is: Haven't we had this discussion already?
 So I will just reiterate my own objections and how I feel about them now.
 
 The first objection is: Haven't we had this discussion already?

-[Leakpocalypse](http://cglab.ca/~abeinges/blah/everyone-poops/) happened back in 2015, and every since then everyone knows that in Rust, you can leak memory, period.
-However, *leaking pinned data is still allowed*!
+[Leakpocalypse](http://cglab.ca/~abeinges/blah/everyone-poops/) happened back in 2015, and ever since then everyone knows that in Rust, you can leak memory, period.
+However, even if we accept this proposal *leaking pinned data is still allowed*!

 The guarantee says that *if memory gets deallocated or otherwise invalidated*, we will call `drop`.
 So, calling `mem::forget` on a `PinBox` is fine.
 And indeed, that's fine for our collection as well---the entry will just stay in the collection, but the pointers to it will also remain valid.
 So, this proposal does *not* backpedal on memory leak guarantees in Rust.
 The guarantee says that *if memory gets deallocated or otherwise invalidated*, we will call `drop`.
 So, calling `mem::forget` on a `PinBox` is fine.
 And indeed, that's fine for our collection as well---the entry will just stay in the collection, but the pointers to it will also remain valid.
 So, this proposal does *not* backpedal on memory leak guarantees in Rust.

-It just adds a pretty limited guarantee about `Pin` only.
-Both `mem::forget` and `ManaullyDrop` remain sound; what would *not* be sound is adding a way to obtain a `Pin` reference *into* a `ManuallyDrop`.
-In the formal part of this post, we will see that we can express the new guarantee without resorting to "linear reasoning", which is reasoning about resources not going unused.
+Both `mem::forget` and `ManaullyDrop` remain sound.
+What would *not* be sound is adding a way to obtain a `Pin` reference *into* a `ManuallyDrop`.
+In the formal part of this post, we will see that we can express the new guarantee without resorting to "linear reasoning", which is reasoning that forbids resources to not get used.

 (Linear reasoning is typically used to prove properties like memory-leak-freedom.)
 
 Okay, so maybe this is much weaker than leek-freedom and we have some good reasons to want such a limited `drop`-guarantee, but why should this be coupled together with `Pin`?
 Pinning and calling `drop` are entirely orthogonal concerns!
 Well, this is certainly true for general leak-freedom.
 (Linear reasoning is typically used to prove properties like memory-leak-freedom.)
 
 Okay, so maybe this is much weaker than leek-freedom and we have some good reasons to want such a limited `drop`-guarantee, but why should this be coupled together with `Pin`?
 Pinning and calling `drop` are entirely orthogonal concerns!
 Well, this is certainly true for general leak-freedom.

-However, the guarantee we are after here is that `drop` will be called *if this memory every gets deallocated*.
+However, the guarantee we are after here is that `drop` will be called *if this memory ever gets deallocated*.

 So, the guarantee is tied to a particular spot in memory---a concept that only makes sense if data is pinned to begin with!
 While `Pin` without the `drop`-guarantee makes sense (and is useful, e.g., for [async IO](https://boats.gitlab.io/blog/post/2018-03-20-async-vi/)), the `drop`-guarantee really only makes sense for pinned data.
 Given that async IO is not bothered by this additional guarantee (it doesn't want to do anything that would violate the guarnatee), it seems preferable to have just one notion of pinned data as opposed to two (one where `drop` will be called, and one where it may not be called).
 So, the guarantee is tied to a particular spot in memory---a concept that only makes sense if data is pinned to begin with!
 While `Pin` without the `drop`-guarantee makes sense (and is useful, e.g., for [async IO](https://boats.gitlab.io/blog/post/2018-03-20-async-vi/)), the `drop`-guarantee really only makes sense for pinned data.
 Given that async IO is not bothered by this additional guarantee (it doesn't want to do anything that would violate the guarnatee), it seems preferable to have just one notion of pinned data as opposed to two (one where `drop` will be called, and one where it may not be called).

-In fact, as well see in the formal part, the way I have set up formal reasoning about pinning last time, we would have to do *extra work* to *not* get this guarantee!
+In fact, as we will see in the formal part, the way I have set up formal reasoning about pinning last time, we would have to do *extra work* to *not* get this guarantee!

 
 The only remaining downside is that the more ergonomic stack pinning API [proposed in the RFC](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension) becomes unsound, and we have to use a less ergonomic [closure-based API instead](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-374702107).
 For now, that seems worth it; if one day we decide that pinning ought to be more ergonomic, we could have a built-in type of `&pin` references with ergonomic stack pinning enforced by the compiler.
 
 
 The only remaining downside is that the more ergonomic stack pinning API [proposed in the RFC](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md#stack-pinning-api-potential-future-extension) becomes unsound, and we have to use a less ergonomic [closure-based API instead](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-374702107).
 For now, that seems worth it; if one day we decide that pinning ought to be more ergonomic, we could have a built-in type of `&pin` references with ergonomic stack pinning enforced by the compiler.
 

-## The Formal Perspective
+## 2 The Formal Perspective

 
 In this second part of the post, we are going to try and apply the formal methodology from the [previous post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}) to the intrusive collection example above.
 I am going to assume that you have read that post.
 
 
 In this second part of the post, we are going to try and apply the formal methodology from the [previous post]({{ site.baseurl }}{% post_url 2018-04-05-a-formal-look-at-pinning %}) to the intrusive collection example above.
 I am going to assume that you have read that post.
 

-### The Intrusive Collection Invariant
+### 2.1 The Intrusive Collection Invariant

 
 Remember that, in my model, every type comes with three separate invariants, each matching a "mode" or "typestate" the type can be in: `T.own`, `T.shr`, and `T.pin`.
 The key point we are going to exploit here is that `T.pin` is a predicate on *pointers*, and it is the job of the type `T` to say how the memory behind that pointer is managed.
 
 Remember that, in my model, every type comes with three separate invariants, each matching a "mode" or "typestate" the type can be in: `T.own`, `T.shr`, and `T.pin`.
 The key point we are going to exploit here is that `T.pin` is a predicate on *pointers*, and it is the job of the type `T` to say how the memory behind that pointer is managed.


@@ -235,11 +247,11 @@ Given such an assumption, we are free to just forget the `T.own` part, grab owne
 We could even deallocate it.
 In fact, this is exactly what happens in the `box_deallocate` function I wrote above---and as we have seen, it is a disaster for intrusive collections.
 
 We could even deallocate it.
 In fact, this is exactly what happens in the `box_deallocate` function I wrote above---and as we have seen, it is a disaster for intrusive collections.
 

-With `T.pin`, we have more freedom.
+With `T.pin`, we have more freedom to choose our invariant.

 `T.pin` does not *have to* say that it owns the memory the pointer points to---and for `Entry`, this is exactly what we are going to do.
 
 But let us start with `Collection`: The idea is that a pinned `Collection` is going to *own* the memory of all the entries it contains.
 `T.pin` does not *have to* say that it owns the memory the pointer points to---and for `Entry`, this is exactly what we are going to do.
 
 But let us start with `Collection`: The idea is that a pinned `Collection` is going to *own* the memory of all the entries it contains.

-All these raw pointers in the `Vec` point to memory we own containing an `Entry<T>`, i.e., a pair of a (pinned) `T` and a raw pointer back to the collection.[^1]
+All these raw pointers in the `Vec` point to memory we own and containing an `Entry<T>`, i.e., a pair of a (pinned) `T` and a raw pointer back to the collection.[^1]

 Actually saying this fully formally would require us to talk about the `RefCell` and the `Vec` in there, which we do not want to do, so the following is a very rough sketch:
 
 [^1]: The fact that the inner `T` are pinned here is an arbitrary choice.  We could also make them fully owned.  This is a choice every collection has to make.  Of course, if they decide to go for pinning, they have to uphold all the pinning guarantees, including calling destructors---which, for example, [`VecDeque` does not](https://internals.rust-lang.org/t/rust-1-20-caused-pinning-to-become-incorrect/6695/12?u=ralfjung).
 Actually saying this fully formally would require us to talk about the `RefCell` and the `Vec` in there, which we do not want to do, so the following is a very rough sketch:
 
 [^1]: The fact that the inner `T` are pinned here is an arbitrary choice.  We could also make them fully owned.  This is a choice every collection has to make.  Of course, if they decide to go for pinning, they have to uphold all the pinning guarantees, including calling destructors---which, for example, [`VecDeque` does not](https://internals.rust-lang.org/t/rust-1-20-caused-pinning-to-become-incorrect/6695/12?u=ralfjung).


@@ -247,7 +259,7 @@ Actually saying this fully formally would require us to talk about the `RefCell`
 ```
 Collection<T>.pin(ptr) := exists |entries: List<Pointer>|
   ptr.points_to_owned(RefCell::new(Vec::from(entries))) &&
 ```
 Collection<T>.pin(ptr) := exists |entries: List<Pointer>|
   ptr.points_to_owned(RefCell::new(Vec::from(entries))) &&

-  entries.for_all(|entry| T.pin(entry.offset_to_field(x)) &&
+  entries.all(|entry| T.pin(entry.offset_to_field(x)) &&

     entry.offset_to_field(collection).points_to_owned(Cell::new(Some(ptr)))
   )
 ```
     entry.offset_to_field(collection).points_to_owned(Cell::new(Some(ptr)))
   )
 ```


@@ -256,7 +268,7 @@ Notice how we iterate over the elements of the list and make sure that we own wh
 
 This invariant already justifies `print_all`: All the entries we are going to see there are in the list, so we have their `T.pin` at our disposal and are free to call `Debug::fmt`.
 
 
 This invariant already justifies `print_all`: All the entries we are going to see there are in the list, so we have their `T.pin` at our disposal and are free to call `Debug::fmt`.
 

-So, what will `Entry` say in its invariant?
+So, what will `Entry` say in its pinned invariant?

 Essentially, there is a case distinction: If `collection` is `None`, we own the memory, otherwise all we know is that we are inside that collection.
 ```
 Entry<T>.pin(ptr) := exists |collection: Option<Pointer>|
 Essentially, there is a case distinction: If `collection` is `None`, we own the memory, otherwise all we know is that we are inside that collection.
 ```
 Entry<T>.pin(ptr) := exists |collection: Option<Pointer>|


@@ -268,28 +280,25 @@ Entry<T>.pin(ptr) := exists |collection: Option<Pointer>|
 ```
 The `entry_owned_in_collection` here does not only assert that this entry is a part of that collection, it also asserts *ownership* of that membership, which means that nobody else can remove the entry from the collection.
 This is our first example of "fictional ownership": Ownership not of part of the memory, but of some made-up resource that has no resemblance in the actual machine.
 ```
 The `entry_owned_in_collection` here does not only assert that this entry is a part of that collection, it also asserts *ownership* of that membership, which means that nobody else can remove the entry from the collection.
 This is our first example of "fictional ownership": Ownership not of part of the memory, but of some made-up resource that has no resemblance in the actual machine.

-Fictional ownership is an extremely powerful concept---it forms the very basis of the [mathematical framework we use in RustBelt](http://iris-project.org/).[^2]
-Actually doing this formally is well beyond the scope of this post.[^2]
+Fictional ownership is an extremely powerful concept---it forms the very basis of the [mathematical framework we use in RustBelt](http://iris-project.org/).
+However, actually doing this formally is well beyond the scope of this post.[^2]

 
 

-[^2] For example, for fictional ownership to actually work, we would have to extend `Collection<T>.pin` to be set up as "the other end" of this ownership relation.
-With fictional ownership, there is always some invariant somewhere that ties it to "less fictional" ownership.
-Think of how a check is just fictional money that is "tied to" real money by the bank, and how "real" money used to be tied to some actual value, namely gold, by the central reserve.
-Similarly, `Collection<T>` owns the "real thing", the memory, and then ties it to the fictional `entry_owned_in_collection`.
+[^2]: For example, for fictional ownership to actually work, we would have to extend `Collection<T>.pin` to be set up as "the other end" of this ownership relation. With fictional ownership, there is always some invariant somewhere that ties it to "less fictional" ownership. Think of how a check is just fictional money that is "tied to" real money by the bank, and how "real" money used to be tied to some actual value, namely gold, by the central reserve. Similarly, `Collection<T>` owns the "real thing", the memory, and then ties it to the fictional `entry_owned_in_collection`.

 
 This justifies `Entry::drop`: If we enter the `if let`, we know we are in the `Some` branch, so we will for sure find ourselves in that collection.
 
 This justifies `Entry::drop`: If we enter the `if let`, we know we are in the `Some` branch, so we will for sure find ourselves in that collection.

-To remove ourselves, we have to give up ownership of `entry_owned_in_collection`, but in exchange we gain the `points_to_owned` and the `T.pin` which the collection now needs to longer.
+To remove ourselves, we have to give up ownership of `entry_owned_in_collection`, but in exchange we gain the `points_to_owned` and the `T.pin` for the entry which the collection now needs to longer.

 
 This is the inverse of what happens in `Collection::insert`: After we made sure that the entry is in the `None` branch, we can take its ownership and put it into the collection.
 In exchange, we obtain an `entry_owned_in_collection`, which can put back into the entry.
 This means, when we return, the entry is fully valid in the `Some` branch.
 That's crucial, because it's just a reference and hence borrowed---we have to restore all the invariants before we return!
 
 
 This is the inverse of what happens in `Collection::insert`: After we made sure that the entry is in the `None` branch, we can take its ownership and put it into the collection.
 In exchange, we obtain an `entry_owned_in_collection`, which can put back into the entry.
 This means, when we return, the entry is fully valid in the `Some` branch.
 That's crucial, because it's just a reference and hence borrowed---we have to restore all the invariants before we return!
 

-### Requiring Drop To Be Run
+### 2.2 Requiring Drop To Be Run

 
 So, how is the new `drop` guarantee we have been talking about reflected in the formal model?
 First of all, notice that---due to the nature of `T.pin` taking a pointer, as discussed above---we can already not justify our fictional `PinBox::deallocate`.
 The `PinBox` owns a `T.pin(ptr)`, which it is free to throw away, but it has no way to just gain access to the underlying memory covered by the pointer and deallocate it!
 
 So, how is the new `drop` guarantee we have been talking about reflected in the formal model?
 First of all, notice that---due to the nature of `T.pin` taking a pointer, as discussed above---we can already not justify our fictional `PinBox::deallocate`.
 The `PinBox` owns a `T.pin(ptr)`, which it is free to throw away, but it has no way to just gain access to the underlying memory covered by the pointer and deallocate it!

-So, the question is not actually how we can enforce the guarantee, the question is how we can justify the correctness of dropping a `PinBox`!
+So, the question is not actually how we can enforce the guarantee, the question is how we can justify the correctness of dropping a `PinBox`.

 
 Now, I should make clear that we are entering uncharted territory here.
 RustBelt does *not* model `drop`.
 
 Now, I should make clear that we are entering uncharted territory here.
 RustBelt does *not* model `drop`.


@@ -308,91 +317,135 @@ So, a correctness proof for `drop` is clearly going to be different from a corre
 Before `drop`, we can assume that all the invariants of the type are satisfied; after `drop`, all we know is that the fields of the vector are themselves ready for `drop`.
 In the case of `Vec`, none of the fields implements `Drop`, so let us focus on that special case:
 
 Before `drop`, we can assume that all the invariants of the type are satisfied; after `drop`, all we know is that the fields of the vector are themselves ready for `drop`.
 In the case of `Vec`, none of the fields implements `Drop`, so let us focus on that special case:
 

+{% raw %}

 > **Definition 1: `drop`, special case where no field implements `Drop`.**
 > **Definition 1: `drop`, special case where no field implements `Drop`.**

-The `drop` function must satisfy the following contract: `T::drop(ptr)` is safe to call whenever `T.pin(ptr)` holds, and when `drop` returns, we own the memory `ptr` points to.
-
-> We write these contracts as "Hoare triples" that consist of a precondition between curly braces, followed by the code that is executed, followed by the postcondition in curly braces:
+The `drop` function must satisfy the following specification (or contract): `T::drop(ptr)` is safe to call whenever `T.pin(ptr)` holds, and when `drop` returns, we own the memory `ptr` points to.

 
 

-> ```
-{ T.pin(ptr) }
+> We write these specifications as "Hoare triples" that consist of a precondition between double curly braces, followed by the code that is executed, followed by the postcondition in double curly braces:
+```
+{{ T.pin(ptr) }}

   T::drop(ptr)
   T::drop(ptr)

-{ exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }
+{{ exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }}

 ```
 ```

+(The usual notation just uses single curly braces, but with me using Rust syntax here that looks too much like a block.)
+{% endraw %}

 
 This definition is deliberately narrow; `drop` is complicated and as I mentioned I don't feel ready to fully specify it.
 But we can already see the interaction between the pinned typestate and dropping: If we move to the pinned typestate, we can call `drop` to re-gain ownership of the memory backing the `T`.
 
 This definition is deliberately narrow; `drop` is complicated and as I mentioned I don't feel ready to fully specify it.
 But we can already see the interaction between the pinned typestate and dropping: If we move to the pinned typestate, we can call `drop` to re-gain ownership of the memory backing the `T`.

-This is what happens when a `PinBox<t>` gets deallocated: It first calls `T::drop` on the contents (which it can do, because it as `T` pinned), obtaining ownership of the mem0ory as expressed in the postcondition above, and then uses that ownership to deallocate the memory.
+This is what happens when a `PinBox<t>` gets deallocated: It first calls `T::drop` on the contents (which it can do, because it as `T` pinned and hence the precondition is satisfied), obtaining ownership of the memory as expressed in the postcondition above, and then uses that ownership to deallocate the memory.

 
 

-For the concrete case of our `Entry<T>`, we can distinguish two cases:
+Let us look at `Entry<T>` as an example `drop` implementation, and see how we can justify that it satisfies the specification in definition 1.
+We proceed by case distinction on `Entry<T>.pin`:

 1. We are in the `None` branch.  Then we already own the memory for the `collection` field, and calling `T::drop` on `x` is guaranteed to give us the ownership of the first field as well.
 1. We are in the `None` branch.  Then we already own the memory for the `collection` field, and calling `T::drop` on `x` is guaranteed to give us the ownership of the first field as well.

-Overall, we thus own all the memory backing the entry, so can satisfy the postcondition.
+Overall, we thus own all the memory backing the entry, so we can satisfy the postcondition.

 2. We are in the `Some` branch. As already discussed, we then give up ownership of `entry_owned_in_collection` to remove ourselves from the collection, obtaining ownership of our own memory.
 Then we proceed as above.
 
 2. We are in the `Some` branch. As already discussed, we then give up ownership of `entry_owned_in_collection` to remove ourselves from the collection, obtaining ownership of our own memory.
 Then we proceed as above.
 

-Notice how, if we did *not* remove ourselves from the collection, we would be unable to satisfy the postcondition!
-This matches the fact that our entire collection would be unsound if we removed the `Entry::drop`.
-Also, we did not make any kind of reasoning along the lines of "all memory will be deallocated eventually".
+Noticeably, we did not make any kind of reasoning along the lines of "all memory will be deallocated eventually".

 There is no talking about leaks.
 We are just concerned with *safety* here: When memory is pinned, it is only safe to deallocate after `drop` has been called.
 
 There is no talking about leaks.
 We are just concerned with *safety* here: When memory is pinned, it is only safe to deallocate after `drop` has been called.
 

+One important observation is that if we did *not* remove the entry from the collection, we would be unable to satisfy the postcondition!
+This matches the fact that our entire collection would be unsound if we removed the `Entry::drop`.
+In other words, if we do *not* implement `Drop`, this actually incurs a proof obligation!
+We have to show that *not doing anything* can turn the precondition `T.pin(ptr)` into the postconditon `exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>()`.
+This is the part that would go wrong if we were to remove `Entry::drop`.
+It seems rather funny that *not* implementing a trait incurs a proof obligation, but there's also nothing fundamentally wrong with that idea.
+

 Coming back to the general case, it seems quite curious to tie `drop` to pinning like that.
 What about dropping things that are not pinned?
 Coming back to the general case, it seems quite curious to tie `drop` to pinning like that.
 What about dropping things that are not pinned?

-The answer is taht it is always legal to start pinning something that we fully own (as it has to be the case when we drop something).
-Formally speaking, we can always use axiom (a) from my last post to briefly pin it, and then call `drop`.
+The answer is that it is always legal to start pinning something that we fully own.
+Formally speaking, we can always use axiom (b) from my last post to briefly pin it, and then call `drop`.

 In other words, we can derive the following Hoare triple:
 ```
 { exists |bytes| ptr.points_to_owned(bytes) && T.own(bytes) }
   T::drop(ptr)
 { exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }
 ```
 In other words, we can derive the following Hoare triple:
 ```
 { exists |bytes| ptr.points_to_owned(bytes) && T.own(bytes) }
   T::drop(ptr)
 { exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }
 ```

-The precondition of this triple implies the precondition of the one in definition 1.
-That's good enough to show that this second contract for `drop` has to hold if the first holds.
+Using axiom (b), the precondition of this triple implies the precondition of the one in definition 1.
+That's good enough to show that this second specification for `drop` has to hold if the first holds.
+So, if I use an arbitrary type while being oblivious to pinning, I can keep using the `drop` specification above.
+This matches the locality of pinning that I described last time: Code that does not do pinning, does not have to care.

 
 

-One funny consequence of definition 1 above becomes apparent if we consider the case where a type does *not* implement `Drop`.
-This actually incurs a proof obligation!
-We have to show that *not doing anything* can turn the precondition `T.pin(ptr)` into the postconditon `exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>()`.
-(And this is what would go wrong if we were to remove `Entry::drop`.)
-It seems rather funny that *not* implementing a trait incurs a proof obligation, but there's also nothing fundamentally wrong with that idea.
+To complete the locality story, we have to think not only about *using* some arbitrary `T`, but also about *defining* a `T` without caring about pinning.
+As discussed last time, we will then pick `T.pin` to just piggy-back on `T.own`:
+```
+T.pin(ptr) := exists |bytes| ptr.points_to_owned(bytes) && T.own(bytes)
+```
+For such `T`, the two different specifications for `drop` that I showed above are actually equivalent.
+Such types can prove their `drop` correct with respect to the `T.own`-based specification and automatically satisfy the pinning guarantees.
+In particular, if they do not implement `Drop`, this specification holds trivially.[^3]
+The funny proof obligation incurred by not implementing `Drop` only arises for types that care about pinning.

 
 

-## What if we used shared references?
+[^3]: This uses the fact that `T.own(bytes)` implies `bytes.len() == mem::size_of<T>()`.  This is another axiom that has to hold for all types, one that did not come up in previous discussion.
+
+## 3 What About Shared References?

 
 Finally, we come to the part where my current model is not good enough.
 
 Finally, we come to the part where my current model is not good enough.

-If you paid really, really close attention to my example above, you may have been slightly irritated by the type of `insert`:
+If you paid really, really close attention to my example above, you may have been irritated by the type of `insert`:

 {% highlight rust %}
     fn insert(mut self: Pin<Self>, entry: Pin<Entry<T>>)
 {% endhighlight %}
 {% highlight rust %}
     fn insert(mut self: Pin<Self>, entry: Pin<Entry<T>>)
 {% endhighlight %}

-@cramertj originally proposed to use a different type instead:
+@cramertj originally proposed to use a slightly different type instead:

 {% highlight rust %}
     fn insert(mut self: Pin<Self>, entry: &Pin<Entry<T>>)
 {% endhighlight %}
 Notice the shared reference on the `entry` argument.
 {% highlight rust %}
     fn insert(mut self: Pin<Self>, entry: &Pin<Entry<T>>)
 {% endhighlight %}
 Notice the shared reference on the `entry` argument.

-Since all the mutation we perform there is via interior mutability, why shouldn't we provide this function for shared pinned data?
-(In my version, the collection itself is also using `RefCell`, which I believe @cramertj just forgot to do---the write access from `Entry::drop` would be unsound otherwise.
-However, it seems more natural to ask the collection itself to be mutable for insertion, not exposing the fact that we use interior mutability.)
+Since all the mutation we perform there happens inside a `Cell`, why shouldn't we provide this function for shared pinned data?[^4]
+
+[^4]: In my version, the collection itself is also using `RefCell`, which I believe @cramertj just forgot to do---the write access from `Entry::drop` would be unsound otherwise. However, it seems more natural to ask the collection itself to be mutable for insertion, not exposing the fact that we use interior mutability.

 
 That's a good question!
 
 That's a good question!

-I can't come up with any counter-example for this.
+It seems perfectly fine to change `insert` to take `&Pin<Entry<T>>`.
+I can't come up with any counter-example.

 However, the formal model also cannot justify this variant of `insert`: As we defined previously, `Pin<'a, T>.shr` just uses `T.shr`.
 That made it easy to justify [`Pin::deref`](https://doc.rust-lang.org/nightly/std/mem/struct.Pin.html#method.deref).
 However, it also means `&Pin<T>` and `&&T` *are the same type*.
 The two invariants are equivalent.
 However, the formal model also cannot justify this variant of `insert`: As we defined previously, `Pin<'a, T>.shr` just uses `T.shr`.
 That made it easy to justify [`Pin::deref`](https://doc.rust-lang.org/nightly/std/mem/struct.Pin.html#method.deref).
 However, it also means `&Pin<T>` and `&&T` *are the same type*.
 The two invariants are equivalent.

-Clearly, `insert` taking `entry: &&T` would be unsound, so we are stuck here.
+We could literally write functions transmuting between the two, and we could justify them in my model.
+Clearly, `insert` taking `entry: &&T` would be unsound as nothing stops the entry from being moved later:
+{% highlight rust %}
+fn main() {
+    let mut collection = PinBox::new(Collection::new());
+    let entry = {
+      let mut entry = Box::new(Entry::new(42));
+      collection.as_pin().insert(&&*entry); // Register boxed entry in collection
+      *entry // Move entry out of the Box, and drop the box
+    };
+    // We keep the entry so it does not get dropped.
+    // The collection still points to the now deallocated box!
+    collection.as_pin().print_all(); // Fireworks happen
+}
+{% endhighlight %}
+This shows that the version of `insert` that takes a shared reference cannot be sound in the model.

 
 

-I do have an idea for how to solve it: Introduce a *fourth* "mode" or typestate, the "shared pinned" state, with an accompanying invariant.
-However, I previously argued strongly against introducing such a fourth state, on the grounds that three states is already complicated enough.
-In fact, an earlier version of the `Pin` API used to have two kinds of pinned references---shared and mutable---reflecting the "shared pinned" and "(owned) pinned" state.
+I do have an idea for how to solve this problem: Introduce a *fourth* "mode" or typestate, the "shared pinned" state, with an accompanying invariant.
+However, I previously argued strongly against introducing such a fourth state, on the grounds that three typestates is already complicated enough.
+In fact, an earlier version of the `Pin` API used to have two kinds of pinned references (shared and mutable) reflecting the two distinct "shared pinned" and "(owned) pinned" typestates.

 The shared variant got subsequently removed, and I feel somewhat guilty about that now because I strongly pushed for it.
 The shared variant got subsequently removed, and I feel somewhat guilty about that now because I strongly pushed for it.

+It seems, after all, that the fourth typestate arises anyway.

 
 

-I now think that may have been a mistake: It turns out that, if we want to allow an intrusive collection like the above that works with `&Pin`, we need the fourth state anyway.
+We have to make a decision here, before stabilizing `Pin`: Do we want `insert` with a shared reference to be legal?
+Or do want to declare that `&Pin<T>` and `&&T` are interchangeable types?
+One may argue that adding an entry to a collection logically changes that entry, so really this should require an exclusive pinned reference.
+However, given that the changed API seems entirely safe to use, I have to admit that's a somewhat weak argument.
+Converting between `&Pin<T>` and `&&T` seems to have no tangible benefit other than satisfying my model.
+
+For these reasons, I now think that removing the shared pinned reference may have been a mistake: It turns out that, if we want to allow an intrusive collection like the above that works with `&Pin`, we need the fourth typestate anyway.

 At that point we might as well have a type reflecting it, avoiding the confusion and the double indirection that comes with `&Pin`.
 At that point we might as well have a type reflecting it, avoiding the confusion and the double indirection that comes with `&Pin`.

-However, now we already have a [version of the futures crate] using the revised `Pin`, so I don't know if changing it again is realistic. :/
+I hope we do not end up in a situation where `insert` with a shared reference is legal, but we do not have a type for shared pinned references.
+That just seems like the worst of both worlds.
+
+However, now we already have a [version of the futures crate](https://aturon.github.io/2018/04/06/futures2/) using the revised `Pin`, so I don't know if changing it again is realistic. :/

 I feel bad about that.  Can we still fix this before everything gets stabilized?
 Others [have](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-373206171) [argued](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-378555691) for a shared pinned reference after it got removed from the API, and I am repentantly joining their choir now after arguing against them previously.
 I feel bad about that.  Can we still fix this before everything gets stabilized?
 Others [have](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-373206171) [argued](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-378555691) for a shared pinned reference after it got removed from the API, and I am repentantly joining their choir now after arguing against them previously.

-Thanks for not being convinced by me!
+Sorry for that, and thanks for not being convinced by me!

 
 

-## Conclusion
+## 4 Conclusion

 
 Leaving aside the last part about shared pinning, I am really excited how all of this fits together so nicely.
 Back when I was learning Rust, I remember thinking how intrusive collections with entries on the stack (as they are commonly used, for example, in the Linux kernel) unfortunately cannot be given a safe interface in Rust.
 I am happy to learn that I was wrong!
 I am impressed by the creativity that went into coming up with these APIs, and looking forward to analyzing more of them in the future.
 
 Leaving aside the last part about shared pinning, I am really excited how all of this fits together so nicely.
 Back when I was learning Rust, I remember thinking how intrusive collections with entries on the stack (as they are commonly used, for example, in the Linux kernel) unfortunately cannot be given a safe interface in Rust.
 I am happy to learn that I was wrong!
 I am impressed by the creativity that went into coming up with these APIs, and looking forward to analyzing more of them in the future.

+
+#### Footnotes