safe intrusive collections with pinning: first draft
[web.git] / personal / _drafts / safe-intrusive-collections-with-pinning.md
1 ---
2 title: "Safe Intrusive Collections with Pinning"
3 categories: rust
4 ---
5
6 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
7 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.
8 This post is about another application of pinned references---another API whose safety relies on the pinning guarantees: Intrusive collections.
9 It turns out that pinned references can *almost* be used for this, but not quite.
10 However, this can be fixed by extending the guarantees provided by pinned references, as suggested by @cramertj.
11
12 <!-- MORE -->
13
14 The first part is going to explain how intrusive collections could benefit from `Pin`, were we to accept that additional guarantee.
15 This part assumes some familiarity with the `Pin` API, but not with the formal notions I introduced previously.
16
17 In the second part, I am going to briefly sketch a formal perspective on intrusive collections and the extended pinning guarantees.
18 This builds on the formal model I introduced in my last post.
19
20 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.
21 This extended model will actually call for a change to the `Pin` API (or rather, for a revert to an earlier version).
22
23 ## Safe Intrusive Collections
24
25 Intrusive collections typically are linked data structures that embed the links in the data they contain.
26 In the words of the [intrusive-collections crate](https://crates.io/crates/intrusive-collections):
27 > 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.
28
29 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.
30 The intrusive-collections crate realizes this by taking ownership of the objects.
31 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.
32 This means we cannot add short-lived objects, e.g. stack-allocated objects, to a collection that was created further up the call chain.
33
34 ### An Example Collection
35
36 To get more concrete, consider the following example ([originally proposed by @cramertj](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-372432435)).
37 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:
38 {% highlight rust %}
39 #![feature(pin, arbitrary_self_types, optin_builtin_traits)]
40
41 use std::cell::{Cell, RefCell};
42 use std::mem::Pin;
43 use std::boxed::PinBox;
44 use std::marker::Unpin;
45
46 struct Collection<T> {
47     objects: RefCell<Vec<*const Entry<T>>>,
48 }
49 impl<T> !Unpin for Collection<T> {}
50
51 struct Entry<T> {
52     x: T,
53     collection: Cell<Option<*const Collection<T>>>,
54 }
55 impl<T> !Unpin for Entry<T> {}
56
57 impl<T> Collection<T> {
58     fn new() -> Self {
59         Collection { objects: RefCell::new(Vec::new()) }
60     }
61
62     // Add the entry to the collection
63     fn insert(mut self: Pin<Self>, entry: Pin<Entry<T>>) {
64         if entry.collection.get().is_some() {
65             panic!("Can't insert the same object into multiple collections");
66         }
67         // Pointer from collection to entry
68         let this : &mut Self = unsafe { Pin::get_mut(&mut self) };
69         this.objects.borrow_mut().push(&*entry as *const _);
70         // Pointer from entry to collection
71         entry.collection.set(Some(this as *const _));
72     }
73     
74     // Show all entries of the collection
75     fn print_all(self: Pin<Self>)
76     where T: ::std::fmt::Debug
77     {
78         print!("[");
79         for entry in self.objects.borrow().iter() {
80             let entry : &Entry<T> = unsafe { &**entry };
81             print!(" {:?},", entry.x);
82         }
83         println!(" ]");
84     }
85 }
86
87 impl<T> Drop for Collection<T> {
88     fn drop(&mut self) {
89         // go through the entries to remove pointers to self as `collection`
90         for entry in self.objects.borrow().iter() {
91             let entry : &Entry<T> = unsafe { &**entry };
92             entry.collection.set(None);
93         }
94     }
95 }
96
97 impl<T> Entry<T> {
98     fn new(x: T) -> Self {
99         Entry { x, collection: Cell::new(None) }
100     }
101 }
102
103 impl<T> Drop for Entry<T> {
104     fn drop(&mut self) {
105         // go through `collection` to remove this entry
106         if let Some(collection) = self.collection.get() {
107             let collection : &Collection<T> = unsafe { &*collection };
108             collection.objects.borrow_mut().retain(|ptr| *ptr != self as *const _);
109         }
110     }
111 }
112
113 fn main() {
114     let mut collection = PinBox::new(Collection::new());
115     let mut entry = PinBox::new(Entry::new(42));
116     collection.as_pin().insert(entry.as_pin());
117     collection.as_pin().print_all(); // Prints "[ 42, ]"
118     drop(entry); // Dropping the entry removes it
119     collection.as_pin().print_all(); // Prints "[ ]"
120 }
121 {% endhighlight %}
122 This is lots of code.
123 It is not necessary to fully understand every last detail here.
124 The high-level picture is as follows:
125 The collection is represented by a `Vec` of raw pointers pointing to the entries.
126 Every entry has a "parent" pointer back to the main collection.
127 Inserting an entry into a collection involves adding it to the `Vec` and setting the collection pointer of the entry.
128 When an entry is dropped, if it is in a collection, it gets removed from the `Vec`.
129 When the collection is dropped, all the entire have their collection pointer reset to `None`.
130 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.
131 Then we `drop` the entry, and we can see it has vanished from the collection as well.
132
133 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!
134 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.
135 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*.
136 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.
137
138 ### Pinning Is Not Enough
139
140 However, it turns out pinning as described so far is not enough to guarantee safety.
141 Imagine we added the following method to `PinBox`:
142 {% highlight rust %}
143 fn box_deallocate<T>(x: Box<T>) {
144   let content = *x; // move out of the box
145   mem::forget(content); // do not call drop
146   // Implicitly deallocate the box
147 }
148
149 impl<T> PinBox<T> {
150   // Deallocate the box without calling drop
151   fn deallocate(self) {
152     box_deallocate(self.inner)
153   }
154 }
155 {% endhighlight %}
156 `box_deallocate` is obviously safe on `Box` (we do not use any unsafe code).
157 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.
158 We essentially perform a `memcpy` followed by a `mem::forget`, so nothing really happens aside from calling `free` on the `Box` itself.
159
160 Why is this a problem?  Well, we can now add an entry to a collection and then *deallocate the entry without calling `drop`*.
161 This leads to a dangling pointer inside the collection, which is obviously bad:
162 {% highlight rust %}
163 fn main() {
164     let mut collection = PinBox::new(Collection::new());
165     let mut entry = PinBox::new(Entry::new(42));
166     collection.as_pin().insert(entry.as_pin()); // Register entry in collection
167     entry.deallocate(); // Now the collection still points to the entry
168     collection.as_pin().print_all(); // And now everything explodes
169 }
170 {% endhighlight %}
171
172 ### Requiring Drop To Be Run
173
174 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*.
175 Combining that with the guarantee about moving, we can summarize `Pin` as follows:
176
177 > 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.
178
179 Under our new rules, `PinBox::deallocate` is bogus, and our collection works again.
180
181 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`.
182 That has the same effect: It renders our collection interface unsound.
183
184 Of course, the entire example is artificial as well, and it is not even a proper intrusive collection because the `Vec` is heap-allocated.
185 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.
186 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.
187 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).
188 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.
189
190 ### Some Common Objections
191
192 I hope I convinced you that it is desirable to guarantee that `drop` is run on pinned references.
193 Before we come to the formal part of this post, let me go over some possible objections to this extended guarantee.
194 In fact, I have been opposed to it initially myself, and went to the [Berlin All-Hands](https://blog.rust-lang.org/2018/04/06/all-hands.html) arguing against it, but @cramertj convinced me otherwise.
195 So I will just reiterate my own objections and how I feel about them now.
196
197 The first objection is: Haven't we had this discussion already?
198 [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.
199 However, *leaking pinned data is still allowed*!
200 The guarantee says that *if memory gets deallocated or otherwise invalidated*, we will call `drop`.
201 So, calling `mem::forget` on a `PinBox` is fine.
202 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.
203 So, this proposal does *not* backpedal on memory leak guarantees in Rust.
204 It just adds a pretty limited guarantee about `Pin` only.
205 Both `mem::forget` and `ManaullyDrop` remain sound; what would *not* be sound is adding a way to obtain a `Pin` reference *into* a `ManuallyDrop`.
206 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.
207 (Linear reasoning is typically used to prove properties like memory-leak-freedom.)
208
209 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`?
210 Pinning and calling `drop` are entirely orthogonal concerns!
211 Well, this is certainly true for general leak-freedom.
212 However, the guarantee we are after here is that `drop` will be called *if this memory every gets deallocated*.
213 So, the guarantee is tied to a particular spot in memory---a concept that only makes sense if data is pinned to begin with!
214 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.
215 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).
216 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!
217
218 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).
219 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.
220
221 ## The Formal Perspective
222
223 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.
224 I am going to assume that you have read that post.
225
226 ### The Intrusive Collection Invariant
227
228 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`.
229 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.
230 In contrast, `T.own` is a predicate on *lists of bytes*, and whoever holds an instance of a type will typically assume something along the lines of: I own some memory containing some bytes, and those bytes form a valid `T`. Formally:
231 ```
232 exists |bytes|, ptr.points_to_owned(bytes) && T.own(bytes)
233 ```
234 Given such an assumption, we are free to just forget the `T.own` part, grab ownership of the memory, and use it for our purposes.
235 We could even deallocate it.
236 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.
237
238 With `T.pin`, we have more freedom.
239 `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.
240
241 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.
242 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]
243 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:
244
245 [^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).
246
247 ```
248 Collection<T>.pin(ptr) := exists |entries: List<Pointer>|
249   ptr.points_to_owned(RefCell::new(Vec::from(entries))) &&
250   entries.for_all(|entry| T.pin(entry.offset_to_field(x)) &&
251     entry.offset_to_field(collection).points_to_owned(Cell::new(Some(ptr)))
252   )
253 ```
254 Notice how we iterate over the elements of the list and make sure that we own whatever memory is to own there.
255 (I love how `all` [really exists for iterators](https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html#method.all) so I can express quantification over lists without any hassle. ;)
256
257 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`.
258
259 So, what will `Entry` say in its invariant?
260 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.
261 ```
262 Entry<T>.pin(ptr) := exists |collection: Option<Pointer>|
263   match collection {
264     None => T.pin(ptr.offset_to_field(x)) &&
265       ptr.offset_to_field(collection).points_to_owned(Cell::new(None)),
266     Some(collection) => entry_owned_in_collection(ptr, collection)
267   }
268 ```
269 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.
270 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.
271 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]
272 Actually doing this formally is well beyond the scope of this post.[^2]
273
274 [^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.
275 With fictional ownership, there is always some invariant somewhere that ties it to "less fictional" ownership.
276 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.
277 Similarly, `Collection<T>` owns the "real thing", the memory, and then ties it to the fictional `entry_owned_in_collection`.
278
279 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.
280 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.
281
282 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.
283 In exchange, we obtain an `entry_owned_in_collection`, which can put back into the entry.
284 This means, when we return, the entry is fully valid in the `Some` branch.
285 That's crucial, because it's just a reference and hence borrowed---we have to restore all the invariants before we return!
286
287 ### Requiring Drop To Be Run
288
289 So, how is the new `drop` guarantee we have been talking about reflected in the formal model?
290 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`.
291 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!
292 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`!
293
294 Now, I should make clear that we are entering uncharted territory here.
295 RustBelt does *not* model `drop`.
296 So, I am going to take some guesses here, but these are purely based on my intuition and not at all backed by formal proofs.
297 My intuition has been wrong before.
298
299 With the disclaimer out of the way, let us look at `drop`.
300 First of all, `drop` is not a normal function. If we could just call it, we could write code like
301 {% highlight rust %}
302 let mut v = vec![0];
303 Vec::drop(&mut v);
304 v.push(1); // BOOM!
305 {% endhighlight %}
306 `Vec::drop` leaves the vector in a bad state, and we must not call any normal method on it again afterwards.
307 So, a correctness proof for `drop` is clearly going to be different from a correctness proof for a normal method that takes an `&mut`.
308 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`.
309 In the case of `Vec`, none of the fields implements `Drop`, so let us focus on that special case:
310
311 > **Definition 1: `drop`, special case where no field implements `Drop`.**
312 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.
313
314 > 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:
315
316 > ```
317 { T.pin(ptr) }
318   T::drop(ptr)
319 { exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }
320 ```
321
322 This definition is deliberately narrow; `drop` is complicated and as I mentioned I don't feel ready to fully specify it.
323 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`.
324 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.
325
326 For the concrete case of our `Entry<T>`, we can distinguish two cases:
327 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.
328 Overall, we thus own all the memory backing the entry, so can satisfy the postcondition.
329 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.
330 Then we proceed as above.
331
332 Notice how, if we did *not* remove ourselves from the collection, we would be unable to satisfy the postcondition!
333 This matches the fact that our entire collection would be unsound if we removed the `Entry::drop`.
334 Also, we did not make any kind of reasoning along the lines of "all memory will be deallocated eventually".
335 There is no talking about leaks.
336 We are just concerned with *safety* here: When memory is pinned, it is only safe to deallocate after `drop` has been called.
337
338 Coming back to the general case, it seems quite curious to tie `drop` to pinning like that.
339 What about dropping things that are not pinned?
340 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).
341 Formally speaking, we can always use axiom (a) from my last post to briefly pin it, and then call `drop`.
342 In other words, we can derive the following Hoare triple:
343 ```
344 { exists |bytes| ptr.points_to_owned(bytes) && T.own(bytes) }
345   T::drop(ptr)
346 { exists |bytes| ptr.points_to_owned(bytes) && bytes.len() == mem::size_of<T>() }
347 ```
348 The precondition of this triple implies the precondition of the one in definition 1.
349 That's good enough to show that this second contract for `drop` has to hold if the first holds.
350
351 One funny consequence of definition 1 above becomes apparent if we consider the case where a type does *not* implement `Drop`.
352 This actually incurs a proof obligation!
353 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>()`.
354 (And this is what would go wrong if we were to remove `Entry::drop`.)
355 It seems rather funny that *not* implementing a trait incurs a proof obligation, but there's also nothing fundamentally wrong with that idea.
356
357 ## What if we used shared references?
358
359 Finally, we come to the part where my current model is not good enough.
360 If you paid really, really close attention to my example above, you may have been slightly irritated by the type of `insert`:
361 {% highlight rust %}
362     fn insert(mut self: Pin<Self>, entry: Pin<Entry<T>>)
363 {% endhighlight %}
364 @cramertj originally proposed to use a different type instead:
365 {% highlight rust %}
366     fn insert(mut self: Pin<Self>, entry: &Pin<Entry<T>>)
367 {% endhighlight %}
368 Notice the shared reference on the `entry` argument.
369 Since all the mutation we perform there is via interior mutability, why shouldn't we provide this function for shared pinned data?
370 (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.
371 However, it seems more natural to ask the collection itself to be mutable for insertion, not exposing the fact that we use interior mutability.)
372
373 That's a good question!
374 I can't come up with any counter-example for this.
375 However, the formal model also cannot justify this variant of `insert`: As we defined previously, `Pin<'a, T>.shr` just uses `T.shr`.
376 That made it easy to justify [`Pin::deref`](https://doc.rust-lang.org/nightly/std/mem/struct.Pin.html#method.deref).
377 However, it also means `&Pin<T>` and `&&T` *are the same type*.
378 The two invariants are equivalent.
379 Clearly, `insert` taking `entry: &&T` would be unsound, so we are stuck here.
380
381 I do have an idea for how to solve it: Introduce a *fourth* "mode" or typestate, the "shared pinned" state, with an accompanying invariant.
382 However, I previously argued strongly against introducing such a fourth state, on the grounds that three states is already complicated enough.
383 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.
384 The shared variant got subsequently removed, and I feel somewhat guilty about that now because I strongly pushed for it.
385
386 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.
387 At that point we might as well have a type reflecting it, avoiding the confusion and the double indirection that comes with `&Pin`.
388 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. :/
389 I feel bad about that.  Can we still fix this before everything gets stabilized?
390 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.
391 Thanks for not being convinced by me!
392
393 ## Conclusion
394
395 Leaving aside the last part about shared pinning, I am really excited how all of this fits together so nicely.
396 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.
397 I am happy to learn that I was wrong!
398 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.