In my previous post we experienced first hand the horrors that can occur when attempting to use lock-free data structures with pointers. We left the question of how to deal with this problem a bit open.

Languages like Java with a garbage collector don’t have this issue, since the runtime collects the memory when it’s unreachable by all threads. I recently learned that one of the ways to solve this in a deterministic manner in Rust is through a method called Epoch-Based Reclamation (EBR), which the crate crossbeam-epoch implements. My goal is not to explain the theoretical concepts, as that endeavour has been already been accomplished by Aaron Turon, the founder of Crossbeam.

Instead, as I’ve done in previous posts, I want to dissect and visualize what exactly is going on. If that sounds fun, you’re welcome to come along for the ride!

I can also recommend another pleasant read that demonstrates the usage of crossbeam-epoch.

You can access the code used in this post.

Q1: When to Drop

We looked at the buggy implementation of a lock-free stack and managed to reproduce the ABA bug. Here’s a diagram for a quick recap:

The fundamental question is:

1. How do we defer drop() until Thread A is no longer reading it, without adding locks or atomic reference counter updates on every single read?

Q2: Updating Pointer and Flag Atomically

Another important question also comes up when removing a node requires two steps. This is the case when working with lock-free linked lists. Check out Timothy Harris’ Paper for a more detailed explanation of this algorithm. Essentially, deleting is done in two parts:

1. Mark the node as deleted (or more specifically, it’s next pointer) so other threads don’t try to insert after it.
2. Physically unlink it via CAS.

There’s a limit set by the hardware that normal CPU atomic instructions can only swap one word (64 bits) at a time. We can’t swap a next pointer and a separate is_deleted: bool flag atomically. This raises a second question, namely:

2. How do we atomically update both a pointer and a state flag in a single CAS instruction, without a double-word atomic write?

Motivation and Goal

When I started writing this, I had planned for just one post visualizing the ABA bug and then analyzing how crossbeam solves it. However, I quickly realized it was too much to pack into just one post, and the ABA problem deserved its own post. Then, as I was writing this continuation, I initially just cared about Q1. However, I came across something that I found really awesome (don’t want to spoil the next section), and I wondered why do we need it… so that’s how I came to Q2, and I couldn’t just leave it out. In the meantime, I was playing around with Loom, so that became its own post. So far in the series:

• Part 1: Visualizing The ABA Problem: What crossbeam-epoch Solves
• Part 2: Using Loom to (Try To) Catch an ABA Bug in Lock-Free Rust
• Part 3: current

Without further ado, the goal of this post is to dissect crossbeam-epoch to better understand how it solves Q1 and Q2.

Q2: Dissecting crossbeam::epoch::Shared

To give a refresher, the building blocks of crossbeam-epoch are:

The Owned<T> holds heap allocated data that isn’t shared yet. You turn an Owned into a Shared or store it inside an Atomic.

Atomic<T> is what you’ll use in your data structures. It holds a pointer that can be updated using CAS (Compare-And-Swap) or other atomic operations.

Shared<'a, T> is obtained by calling .load(&guard) on an Atomic. The lifetime 'g guarantees the pointer cannot be freed by another thread as long as your pin() guard is alive. (We’ll discuss this later).

Using Wasted Alignment Bits for Metadata

Photo by Eduard Delputte on Unsplash

Every type has an alignment requirement. We can imagine that memory is organized in “shelves,” where each variable must sit. This way, you can’t have a variable sitting in between two shelves. Each type has its own alignment requirement (shelf size). In modern 64-bit architectures, a pointer requires 8-byte alignment.

For a type T with 8-byte alignment, every valid pointer to a T is a multiple of 8. If you look at memory addresses that are multiples of 8 in binary, you can see that the lowest 3 bits are in a sense “wasted.” They don’t hold any other useful information, since they’re guaranteed to be always 000.

You can believe this was my face when I learned what crossbeam does with this information.

Crossbeam reclaims those unused low-order bits to store some metadata directly inside the pointer value.

For reading or dereferencing the pointer, crossbeam masks out those bits using bitwise AND to reconstruct the valid address:

Original Address = Raw Pointer & ~ Tag Mask

This is purely awesome. We can store a small piece of metadata, like a “deleted” mark, directly inside the pointer itself. So the pointer and the flag can be updated together in a single CAS, without needing a separate variable.

Taking a Look Inside

To work with crossbeam-epoch, we first allocate data on the heap using Owned<T> (similar to Box<T>). We then transfer this pointer into an Atomic<T> location. This enables us to share it across threads.

Before reading from the Atomic<T>, a thread must pin the current global epoch. We’ll discuss this in a bit, but basically we’re announcing that this thread is actively working with memory, and for as long as this Guard lives, other threads aren’t allowed to drop the object(s) we’re working with. This guaranntees that any Shared<'a, T> references we have remain safe to dereference.

let node = Owned::new(Node { data: 42 } );
let atomic_ptr = Atomic::from(node);

let guard = &epoch::pin();

let shared_ptr = atomic_ptr.load(Ordering::Acquire, guard);

Now that we have our Shared<'a, T> we can play around with it, changing the tag and verifying what happens in memory:

1. Show initial state: tag is 0.

 println!("Initial tag: {}", shared_ptr.tag());
 println!("Initial address: {:#018x}        --> last byte: {:08b}", shared_ptr.as_raw() as usize, shared_ptr.as_raw() as usize & 0xFF);
 println!("----------------------------------");

2. Set tag to 2. with_tag creates a new Shared pointer with updated tag bits.

 let tagged_ptr_2 = shared_ptr.with_tag(2);
 let raw_bits_2 = unsafe { std::mem::transmute::<_, usize>(tagged_ptr_2) };

 println!("Tag: {}", tagged_ptr_2.tag());
 println!("Tagged address (tag 2): {:#018x} --> last byte: {:08b}", &raw_bits_2, &raw_bits_2);
 println!("tagged_ptr_2.as_raw(): {:#018x}", tagged_ptr_2.as_raw() as usize);
 println!("----------------------------------");

3. Update tag to 3.

 let tagged_ptr_3 = tagged_ptr_2.with_tag(3);
 let raw_bits_3 = unsafe { std::mem::transmute::<_, usize>(tagged_ptr_3) };

 println!("Tag: {}", tagged_ptr_3.tag());
 println!("Tagged address (tag 3): {:#018x} --> last byte: {:08b}", &raw_bits_3, &raw_bits_3 & 0xFF);
 println!("tagged_ptr_3.as_raw(): {:#018x}", tagged_ptr_3.as_raw() as usize);
 println!("----------------------------------");

4. Verify that dereferencing ignores tag bits.

 let node_ref: &Node = unsafe { tagged_ptr_3.deref() };
 let physical_addr = (node_ref as *const Node) as usize;

 println!("Clean Physical Address: {:#018x}", physical_addr);
 println!("Node inner data: {}", node_ref.data);

Let’s run it:

Initial tag: 0
Initial address: 0x000056065369dd50        --> last byte: 01010000
----------------------------------
Tag: 2
Tagged address (tag 2): 0x000056065369dd52 --> last byte: 01010010
tagged_ptr_2.as_raw(): 0x000056065369dd50
----------------------------------
Tag: 3
Tagged address (tag 3): 0x000056065369dd53 --> last byte: 01010011
tagged_ptr_3.as_raw(): 0x000056065369dd50
----------------------------------
Clean Physical Address: 0x000056065369dd50
Node inner data: 42

This answers our second question, let’s now tackle the first one:

1. How do we defer drop() until Thread A is no longer reading it, without adding locks or atomic reference counter updates on every single read?

2. How do we atomically update both a pointer and a state flag in a single CAS instruction, without a double-word atomic write?

Q1: Visualizing When a Node Gets Dropped

Now for the first and most awaited question: how does crossbeam-epoch delay drop() until no thread is reading the node?

The idea of epoch-based reclamation was first introduced by Keir Fraser in his PhD thesis, and what a beautiful concept it is! The first implementation of crossbeam-epoch was written by Aaron Turon and the approach is described beautifully in his blog. Please check that out beforehand if it’s your first time exploring this concept, since I don’t go too deep here, just a recap before jumping into the visualization experiment.

Epoch-Based Reclamation Quick Recap

To recap, the global epoch is a mod 3 counter. When a thread wants to access memory, it “pins” itself to the current epoch (it essentially records the epoch it saw when it was pinned). The epoch can advance from e to e + 1 if every pinned thread has already “observed” e. When a thread retires a node (unlinks it from the data structure), it goes into a “bin” labeled with the current epoch.

Why we need only 3 “bins”?

Photo by Claudio Schwarz on Unsplash

My first question when reading about this was “why only 3 epochs”? And the explanation is actually extremely elegant, very clever.

• Bin e (current): Unsafe to free. Threads pinned at e may have loaded the pointer just before it was unlinked and could still be reading it.
• Bin e - 1: Unsafe to free. Threads can be pinned at e - 1 still, since the epoch advanced once everyone had observed e - 1. This check didn’t require them to have moved on. This means that such threads could still hold a pointer to something unlinked in e - 1.
• Bin e - 2: Safe to free. For the epoch to get from e - 2 to e, it had to pass from e - 1 to e, which required that every pinned thread be at e - 1 or later. This guarantees that nobody is still at e - 2. Anyone who could have had a pointer to the node (pinned at e - 2 or earlier, since it was unlinked at e - 2) has since unpinned or re-pinned, and can’t hold that pointer.

This is the theoretical explanation. As for crossbeam, it doesn’t literally keep 3 bins. Each thread has a local bag. “Sealed” bags go into a global queue marked with the corresponding epoch. A bag is freed once the global epoch is at least two ahead of the bag’s mark. The global epoch itself behaves like a mod 3 counter, but is a plain increasing counter. This makes a lot more sense with the diagram!

Experiment #1: Pinned Thread Prevents Drop

Photo by Boys in Bristol Photography on Unsplash

To visualize what exactly it looks like in action, we can use a custom collector. Normally, every 128th call to pin() on a thread automatically triggers a garbage collection attempt (try_advance()). However, in order to control when this happens, we can use a custom collector and explicitly call .flush().

For EBR, a “thread” is just a registered handle. Handles aren’t even required to live on different OS threads, so we can play T1 and T2 from a single thread, just for demonstration purposes.

We can create a custom type that flips a flag when it is dropped. (This flag lives in an Arc, and our object holds a clone to that Arc, so we can still access the flag once the object dies).

struct DropTracker {
    flag: Arc<AtomicBool>,
}

impl Drop for DropTracker {
    fn drop(&mut self) {
        self.flag.store(true, Ordering::SeqCst);
    }
}

We create a custom collector and register two handles, which simulate threads, T1 and T2.

let collector = Collector::new();
let (t1, t2) = (collector.register(), collector.register());

Create instances of the DropTracker holding an Arc containing the flag.

let flag = Arc::new(AtomicBool::new(false));

let tracker = Atomic::new(DropTracker {
    flag: flag.clone()
});

T1 pins, receiving a Guard:

let g1 = t1.pin();

T2 unlinks the value and retires it:

{
    let guard2 = t2.pin();
    let old = tracker.swap(Shared::null(), Ordering::AcqRel, &guard2);

    // defer_destroy is unsafe because the compiler can't
    // verify that nodoby can still reach the pointer
    // Safety: we know nobody can reach the pointer anymore
    // because we've "unlinked" it from our data structure
    unsafe { guard2.defer_destroy(old) };
} // guard2 gets dropped

If we go back to our stack situation, this would be analogous to when T2 pops node A and then drops it. With EBR, instead of dropping it right away, it goes into T2’s garbage bag. It can’t be cleaned up while T1’s guard is still alive. By holding this guard, it stops the global epoch from advancing. The bag only expires once the epoch has moved on.

Photo by fr0ggy5 on Unsplash

This only protects threads reading tracker who pinned it before it was unlinked (swaped out). What happens if a thread pins afterward? In this case, that thread cannot see this node anymore because we’ve already unlinked it from our data structure (or swaped it out, in this case).

Now, while T1’s Guard is still alive, we try to manually trigger the garbage collection by calling .flush() a couple of times:

let mut flushes = 0;

while !flag.load(Ordering::SeqCst) && flushes < 5 {
    // why do we need a fresh pin every time?
    t2.pin().flush();

    flushes += 1;
    println!("flush #{flushes}: flag = {}", flag.load(Ordering::SeqCst));
}

Side note: Why do we need a fresh pin every time for T2?

We need a fresh pin() for T2 every time we try this because Guard records the epoch it was pinned at, and that is the value that try_advance checks. If T2 were to keep one guard alive across flushes, T2 itself becomes the lagging thread blocking the epoch.

We’ll see that until we drop T1’s Guard, our tracker doesn’t get dropped, no matter how many times we try to flush().

flush #1: flag = false
flush #2: flag = false
flush #3: flag = false
flush #4: flag = false
flush #5: flag = false

Let’s drop it and try to flush again:

if !flag.load(Ordering::SeqCst) {
    drop(g1);
    println!("-- T1 unpins --");

    while !flag.load(Ordering::SeqCst) && flushes < 10 {
        t2.pin().flush();
        flushes += 1;
        println!("flush #{}: flag = {}", flushes, flag.load(Ordering::SeqCst));
    }
}

We see that the drop doesn’t happen on the first flush, even though nobody is pinned. The reason for this is the rule from Turon’s post: a bag sealed at epoch e may only be freed once the global epoch has reached e + 2. Each flush advances the epoch by at most one step, so it takes two flushes.

-- T1 unpins --
flush #6: flag = false
flush #7: flag = true

Experiment #2: No Pinned Threads

We can try the same experiment but without T1 holding a guard, to verify that it was indeed that guard that was keeping the epoch from advancing, and, in turn, keeping the node from getting dropped.

flush #1: flag = false
flush #2: flag = true

We see that the first flush doesn’t yet trigger a drop(). Instead, what happens with that first flush, is that the “sealed bag” is passed to the global queue, for it to be dropped the next time the epoch advances.

Visualization

Conclusion

Regarding the first part of this post, I wrote it and was very happy with how it turned out, mainly because I found the idea of reclaiming those “unused” bits so simple yet so elegant. It just made my brain happy.

As for the second part, however, I went through many attempts. I didn’t want to just repeat explanations that already exist, but I wanted to give enough context to make the concepts in my experiments clear. I also went back and forth between different experiment ideas. I then realized I had at some point lost my plot and was overcomplicating things. So, I opted for a simpler demonstration that shows the concept of EBR in practice and how it relates to our original problem of a lock-free stack.

The reason I like writing these posts is to test my understanding of a topic by trying to explain it cohesively, and demonstrating it through code. This makes the concept feel more real to me and helps me make sure I got it. I also love and need lots of diagrams, which might also be useful for someone else.

This one in particular wasn’t so straightforward to write, but it was extremely rewarding! I also enjoyed the feedback I’ve gotten from the community along the way. Some of the chats I’ve had made me feel like a scientist in the 20th century, writing letters back and forth to each other, discussing their findings. This is the sense of community I strive for, so I consider this all worth the effort!

As some already know, I’m currently unemployed, so finding meaning and community through what I’m doing means so much to me. Thank you so much for reading and I hope you enjoyed it as well!

Resources

Epoch-based reclamation

• Keir Fraser, Practical lock-freedom (PhD thesis, University of Cambridge, 2004): where EBR was introduced.
• Aaron Turon, Lock-freedom without garbage collection: the clearest walkthrough of the algorithm, and the origin of crossbeam-epoch. Check it out for a lock-free stack implementation using crossbeam-epoch to conclude the stack journey.

Using crossbeam-epoch

• Learning Rust: crossbeam-epoch
• crossbeam-epoch documentation
• Crossbeam source code

Lock-free linked lists

• Timothy Harris, A Pragmatic Implementation of Non-Blocking Linked-Lists (DISC 2001).

This series

• Part 1: Visualizing The ABA Problem: What crossbeam-epoch Solves
• Part 2: Using Loom to (Try To) Catch an ABA Bug in Lock-Free Rust
• Code for this post