title: Memory reclamation with crossbeam::epoch
body: <p>I've encountered an issue with memory reclamation in <a href="https://docs.rs/crossbeam/0.3.0/crossbeam/" rel="nofollow noreferrer"><code>crossbeam</code></a>. Say you're implementing a simple thread-safe lock-free container that holds a single value. Any thread can obtain a clone of the stored value, and the value can get updated at any point, after which readers begin observing clones of the new value.</p>
  
  <p>Although the typical use case would be to specify something like <code>Arc&lt;X&gt;</code> as T, the implementation cannot rely on T being pointer-sized - for example, <code>X</code> could be a trait, resulting in a fat-pointer <code>Arc&lt;X&gt;</code>. But lock-free access to an arbitrary T seems like a great fit for <a href="https://aturon.github.io/blog/2015/08/27/epoch/" rel="nofollow noreferrer">epoch-based lock-free code</a>. Based on the examples, I came up with this:</p>
  
  <pre class="lang-rust prettyprint-override"><code>extern crate crossbeam;
  
  use std::thread;
  use std::sync::atomic::Ordering;
  
  use crossbeam::epoch::{self, Atomic, Owned};
  
  struct Container&lt;T: Clone&gt; {
      current: Atomic&lt;T&gt;,
  }
  
  impl&lt;T: Clone&gt; Container&lt;T&gt; {
      fn new(initial: T) -&gt; Container&lt;T&gt; {
          Container { current: Atomic::new(initial) }
      }
  
      fn set_current(&amp;self, new: T) {
          let guard = epoch::pin();
          let prev = self.current.swap(Some(Owned::new(new)),
                                       Ordering::AcqRel, &amp;guard);
          if let Some(prev) = prev {
              unsafe {
                  // once swap has propagated, *PREV will no longer
                  // be observable
                  //drop(::std::ptr::read(*prev));
                  guard.unlinked(prev);
              }
          }
      }
  
      fn get_current(&amp;self) -&gt; T {
          let guard = epoch::pin();
          // clone the latest visible value
          (*self.current.load(Ordering::Acquire, &amp;guard).unwrap()).clone()
      }
  }
  </code></pre>
  
  <p>When used with a type that doesn't allocate, e.g. with <code>T=u64</code>, it works great - <code>set_current</code> and <code>get_current</code> can be called millions of times without leaking. (The process monitor shows minor memory oscillations due to <code>epoch</code> pseudo-gc, as would be expected, but no long-term growth.) However, when T is a type that allocates, e.g. <code>Box&lt;u64&gt;</code>, one can easily observe leaks. For example:</p>
  
  <pre class="lang-rust prettyprint-override"><code>fn main() {
      use std::sync::Arc;
      let c = Arc::new(Container::new(Box::new(0)));
      const ITERS: u64 = 100_000_000;
      let producer = thread::spawn({
          let c = Arc::clone(&amp;c);
          move || {
              for i in 0..ITERS {
                  c.set_current(Box::new(i));
              }
          }
      });
      let consumers: Vec&lt;_&gt; = (0..16).map(|_| {
          let c = Arc::clone(&amp;c);
          thread::spawn(move || {
              let mut last = 0;
              loop {
                  let current = c.get_current();
                  if *current == ITERS - 1 {
                      break;
                  }
                  assert!(*current &gt;= last);
                  last = *current;
              }
          })}).collect();
      producer.join().unwrap();
      for x in consumers {
          x.join().unwrap();
      }
  }
  </code></pre>
  
  <p>Running this program shows a steady and significant increase in memory usage that ends up consuming the amount of memory proportional to the number of iterations.</p>
  
  <p>According to <a href="https://aturon.github.io/blog/2015/08/27/epoch/" rel="nofollow noreferrer">the blog post introducing it</a>, Crossbeam's epoch reclamation "does not run destructors, but merely deallocates memory". The <code>try_pop</code> in the Treiber stack example uses <code>ptr::read(&amp;(*head).data)</code> to move the value contained in <code>head.data</code> out of the <code>head</code> object destined for deallocation. The ownership of the data object is transferred to the caller which will either move it elsewhere or deallocate it when it goes out of scope.</p>
  
  <p>How would that translate to the code above? Is the setter the proper place for <code>guard.unlinked</code>, or how else does one ensure that the <code>drop</code> is run on the underlying object? Uncommenting the explicit <code>drop(ptr::read(*prev))</code> results in failed assertion that checks monotonicity, possibly indicating premature deallocation.</p>