We inspected reference counting and hazard-pointer-based Treiber stacks earlier in this chapter and will follow this approach in this section as well. Fortunately, crossbeam also ships with a Treiber stack implementation, in the crossbeam-rs/crossbeam project, which we'll examine at SHA 89bd6857cd701bff54f7a8bf47ccaa38d5022bfb, which is the source for crossbeam::sync::TreiberStack is in src/sync/treiber_stack.rs. The preamble is almost immediately interesting:

use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
use std::ptr;

use epoch::{self, Atomic, Owned};

What, for instance, are epoch::Atomic and epoch::Owned? Well, we'll explore these here. Unlike the section on hazard pointers, which explored the implementation of conc in a depth-first fashion, we'll take a breadth-first approach here, more or less. The reason being, crossbeam-epoch is intricate—it's easy to get lost. Setting aside the somewhat unknown nature of epoch::Atomic, the TreiberStack and Node structs are similar to what we've seen in other implementations:

#[derive(Debug)]
pub struct TreiberStack<T> {
    head: Atomic<Node<T>>,
}

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Atomic<Node<T>>,
}

As is the creation of a new stack:

impl<T> TreiberStack<T> {
    /// Create a new, empty stack.
    pub fn new() -> TreiberStack<T> {
        TreiberStack {
            head: Atomic::null(),
        }
    }

Pushing a new element also looks familiar:

    pub fn push(&self, t: T) {
        let mut n = Owned::new(Node {
            data: t,
            next: Atomic::null(),
        });
        let guard = epoch::pin();
        loop {
            let head = self.head.load(Relaxed, &guard);
            n.next.store(head, Relaxed);
            match self.head.compare_and_set(head, n, Release, &guard) {
                Ok(_) => break,
                Err(e) => n = e.new,
            }
        }
    }

Except, what is epoch::pin()? This function pins the current thread, returning a crossbeam_epoch::Guard. Much like previous guards we've seen throughout the book, crossbeam_epoch's Guard protects a resource. In this case, the guard protects the pinned nature of the thread. Once the guard drops, the thread is no longer pinned. Okay, great, so what does it mean for a thread to be pinned? Recall that epoch-based reclamation works by a thread entering an epoch, doing some stuff with memory, and then potentially increasing the epoch after finishing up fiddling with memory. This process is observed in crossbeam by pinning. Guard in hand—implying a safe epoch has been entered—the thread is able to take a heap allocation and get a stack reference to it. Just any old heap allocation and stack reference would be unsafe, however. There's no magic here. That's where Atomic and Owned come in. They're analogs to AtomicPtr and Box from the standard library, except that the operations done on them require a reference to crossbeam_epoch::Guard. We saw this technique in Chapter 4, Sync and Send – the Foundation of Rust Concurrency, when discussing hopper, using the type-system to ensure that potentially thread-unsafe operations are done safely by requiring the caller to pass in a guard of some sort. Programmer error can creep in by using AtomicPtr, Box, or any non-epoch unprotected memory accesses, but these will tend to stand out.

Let's look at popping an element off the stack, where we know marking memory as safe to delete will have to happen:

    pub fn try_pop(&self) -> Option<T> {
        let guard = epoch::pin();
        loop {
            let head_shared = self.head.load(Acquire, &guard);
            match unsafe { head_shared.as_ref() } {
                Some(head) => {
                    let next = head.next.load(Relaxed, &guard);
                    if self.head
                        .compare_and_set(head_shared, next, Release, 
                         &guard)
                        .is_ok()
                    {
                        unsafe {
                            guard.defer(move || 
                            head_shared.into_owned());
                            return Some(ptr::read(&(*head).data));
                        }
                    }
                }
                None => return None,
            }
        }
    }

The key things to note are the creation of head_shared by performing a load on an Atomic, the usual compare and set operation, and then this:

    guard.defer(move || head_shared.into_owned());
    return Some(ptr::read(&(*head).data));

head_shared is moved into a closure, converted, and that closure is then passed into the as-yet unexamined defer function of Guard. But, head is dereferenced and the data from it is read out and returned. Absent some special trick, that's dangerous. We need to know more.