As a new Rust convert (Rustacean?) coming from C++, it can be all too tempting to believe Rust’s ownership model is the panacea, the cure for all our problems. While it is truly groundbreaking, I’m beginning to learn about the cases where it can’t really save us. But there’s hope, let’s not panic!
Ever since I watched Fedor Pikus talk on atomics (highly recommend!), I’ve had an interest in lock-free programming. I played around with implementing my own SPMC queue in C++, and have since started (and not finished) some books, trying specially hard to wrap my head around memory ordering. But I’ve come to realize I’ve been a bit stuck in tutorial hell, so this post is the beginning of me getting unstuck.
My goal is to poke at the crossbeam crate, with the hopes of gaining a better understanding of a real-world use case and hopefully gain some insight which might help me contribute something back.
Let’s start from the beginning, exploring what is one of the problems that crossbeam-epoch tackles.
See all the code and experiments over at my GitHub.
Side note: the two-faced statue in the thumbnail is the Roman god Janus, who looks toward the past and future simultaneously. In a moment you’ll see what this has to do with our pointers in the ABA problem.
The Question of When to drop() in Lock-Free Code
It turns out, one of the cases where Rust’s ownership model isn’t enough is lock-free code.
Normally, every value has a single owner, and when that owner goes out of scope, Rust calls drop() to first execute its destructor and then free its memory. If we’re using a Mutex, we can rest assured that while one thread is mutating or destroying a node in our data structure, no other thread can hold a reference to it.
If we want to do this the lock-free way, we’d use a CAS (Compare-And-Swap) loop instead of a Mutex. This way, multiple threads could read and modify different nodes in the data structure simultaneously, without waiting for one another.
What CAS Guarantees
So what does CAS actually promise?
fn compare_exchange(
&self,
current: T,
new: T,
success: Ordering,
failure: Ordering,
) -> Result<T, T>;
In simple terms, what this says is: “if the current value equals current, swap it for the new one, atomically.” The intuition is that we usually want to modify a variable based on what it currently holds. If, in between reading it and attempting to change it, another thread has modified it from under our feet, we’d need to update our notion of what’s the current value before we can change it. This is the usual usecase for the CAS loop.
Here’s the simplest example, of incrementing a counter using a CAS loop:
use std::sync::atomic::{AtomicUsize, Ordering};
fn increment(counter: &AtomicUsize) {
loop {
let current = counter.load(Ordering::Relaxed);
let new = current + 1;
if counter
.compare_exchange_weak(current, new, Ordering::Release, Ordering::Relaxed)
.is_ok()
{
break;
}
// else: someone else changed it first, retry
}
}
What if I told you there’s a scenario when this promise isn’t enough and our intuition can betray us into a false sense of correctness? When the A we saw first is not the same as the current A, even though the value is exactly the same? When A ≠ A?
My first time hearing about this, I was in utter disbelief. I had a hard time imagining, in pure mathematical/abstract terms, why in the world would it matter that the value has changed, if it’s ultimately been “restored” to the same value? Surely our previous assumptions still hold and we’re free to continue with our operation…
What is The ABA Problem
Maybe you’ve guessed that the case where our normal intuition starts falling apart is when we are working not with values directly but with pointers. How does the old saying go? All problems in computer science are caused by adding a level of indirection? The important thing to understand is that a pointer can point to the same memory but that memory may not be the same.
Let’s picture this scenario:
- Current shape of our stack
[A, B]. - Thread 1 reads
head = A, reads thatA.next = B, then gets descheduled right before the CAS loop. - Thread 2 pops
Aand deallocates the memory. - Thread 2 pops
B. - Thread 2 allocates a new node object at the newly freed memory with address
A, and pushesAto the stack.A.nextis therefore set to null (the stack is now just[A]). - Thread 1 resumes. Its
compare_exchange(expected = A, new = B)succeeds, becauseheadis in factAagain. However, it should’ve failed because it’s not the same A. Thread 1 had no way of knowing this though. The CAS setshead = B, butBwas already popped and deallocated in step 3. Now the stack’s head is a dangling pointer to freed memory.
The worst thing about this bug is that it’s very easy to miss. It needs precise conditions to be met: the interleaving of the two threads as well as the allocator to actually reuse the recently freed address. (stick with me, promised diagram coming up).
Reproducing The ABA Problem
I had opened a can of worms. I still didn’t understand why it was the first time in my career hearing about this strange kind of bug. Needless to say, I was intrigued, I felt the urge to try to reproduce it myself, hoping that maybe that’d help build my intuition for detecting this kind of bugs that weren’t under my radar before. It turned out to be harder than I expected.
These next few sections are me hitting my head against a wall until I got the basics down. Feel free to skip if you’re familiar with these concepts already :)
Rust’s *mut T
The first roadblock I came across when trying to build my lock-free stack, was understanding raw pointers (*mut), since using something like Arc would defeat the lock-free effort. This is another rabbit hole, but what’s important to understand for us, is that it requires an unsafe block for dereferencing. You can pass around raw pointers, that’s fine, but when dereferencing it to read or write to the memory behind *mut T, the compiler can’t guarantee memory safety, hence the need for unsafe.
So, our nodes would look like:
struct Node<T> {
value: T,
next: *mut Node<T>,
}
We’d dereference it like:
unsafe { (*node).next = another_node }
Also important to remember, dropping a *mut T does NOT run T’s Drop or free its heap memory. For that, we can manually convert it back to an owned type and let it handle the cleanup automatically when it goes out of scope.
??? do we need to assign it?
let node = unsafe { Box::from_raw(current_head) };
Similarly, we use Box::new for allocating memory, and then Box::into_raw for taking ownership of the underlying *mut T.
let node = Box::new(Node::new(value));
let new_head = Box::into_raw(node);
Why Passing &self is Enough
My first instinct when typing out the pop and push methods was to use &mut self. This made sense at first, since in both cases we’d be modifying the stack. However, I soon realized that if I wanted to pass a reference of the same stack to multiple threads, it’d have to be a shared reference. It sounds obvious in retrospect, I mean, that’s the whole point of what we’re trying to achieve!
The reason why &self is enough is because atomics (AtomicPtr) handle thread synchronization internally at the hardware level, essentially bypassing the compiler’s borrow rules. They can be mutated behind a shared (&self) reference using atomic instructions, like CAS.
Sharing Across Threads
By wrapping our stack in an Arc, each thread gets a cloned shared handle pointing to the same stack memory address, allowing concurrent calls to pop(&self) and push(&self, value: T).
However, one thing is still missing. It turns out that Rust automatically disables Send and Sync for any type containing raw pointers.
Send: Safe to transfer ownership to another thread.Sync: Safe to share references (&Stack<T>) across multiple threads simultaneously.
So we need to explicitly implement those traits (though technically we only need Sync for our example):
unsafe impl<T: Send> Send for Stack<T> {}
unsafe impl<T: Send> Sync for Stack<T> {}
We can conclude our final picture of what it looks like in memory:
Buggy Lock-Free Stack
So, for my naive implementation of a lock-free stack, this is what push turned out like:
fn push(&self, value: T) {
let mut current_head = self.head.load(Ordering::Relaxed);
let node = Box::new(Node::new(value));
let new_head = Box::into_raw(node);
loop {
unsafe { (*new_head).next = current_head };
match self.head.compare_exchange_weak(
current_head,
new_head,
Ordering::AcqRel,
Ordering::Relaxed
) {
Ok(_) => break,
Err(actual_head) => {
current_head = actual_head;
},
}
}
}
And pop:
fn pop(&self) -> Option<T> {
let mut current_head = self.head.load(Ordering::Relaxed);
loop {
if current_head.is_null() { return None; }
// Safety: how do we know no other read is modifying this?
let new_head = unsafe { (*current_head).next };
match self.head.compare_exchange_weak(
current_head,
new_head,
Ordering::AcqRel,
Ordering::Relaxed) {
Ok(_) => {
// Safety: as I'm writing this, rust forces me to think about the safety of the unsafe operations,
// and the fact that I can't write a safety statement should be a red flag
let node = unsafe { Box::from_raw(current_head) };
return Some(node.value); // our ptr gets dropped as the Box goes out of scope
},
Err(actual_head) => {
current_head = actual_head;
}
}
}
}
Reproducing It (Why No SegFault?)
Now for the moment we’ve all been waiting for. I’ve made use of some thread::sleeps to trigger the (un)desired order of operations.
Expand to view the aba test
#[test]
fn aba() {
let stack = Arc::new(Stack::<i32>::new());
let stack_clone = stack.clone();
stack.push(2);
stack.push(1);
// stack at this point: head -> [1] -> [2] -> nullptr
thread::scope(|s| {
// This thread pops, but with a delay between reading head and the CAS loop
// By the time it enters the CAS loop, the second thread has essentially
// replaced the head, [1], with [3] that shares the same memory address as [1]
// original: head -> [1] -> [2]
// now : head -> [3] -> nullptr
s.spawn(|| {
println!("thread 1 starts pop operation");
let node = stack.pop_with_delay();
// If this pop shows up as [3] this means the CAS succeeded,
// and we were able to reproduce the bug, yay!
println!("thread 1 pop: {:?}", node);
});
// During the first thread's delay window:
// 1. This thread pops [1]
// 2. Then pops [2]
// 3. Pushes a new node [3], with the same address as [1]
s.spawn(|| {
// We wait a little to make sure the first thread gets a head-start (pun intended)
thread::sleep(Duration::from_millis(20));
println!("thread 2 pops: [{}]", stack_clone.pop().unwrap());
println!("thread 2 pops: [{}]", stack_clone.pop().unwrap());
// Let's hope the system heap allocator reuses the memory that was just freed
// Stack now: head -> [3] -> nullptr
stack_clone.push(3);
println!("thread 2 pushes [3]");
});
thread::sleep(Duration::from_millis(500));
// Current stack: head -> [2 (freed)]
println!("Final pop: [{:?}]", stack.pop());
});
}The output, surprisingly:
thread 1 starts pop operation
thread 2 pops: [1]
thread 2 pops: [2]
thread 2 pushes [3]
thread 1 pop: Some(3)
Final pop: [None]
Essentially, we’ve shown that this is what happens:
But…
The output is a bit anticlimactic, isn’t it? I was expecting explosions or a segfault at least.
If we didn’t know what we were looking for, we might see the output and believe it’s completely normal and all is well. What actually happens is undefined behaviour (UB). Why not segfault necessarily? Well, because in this scenario the memory behind the freed object is most likely still mapped, meaning that because it still belongs to the process, the OS doesn’t raise a segmentation fault.
However, if you want to see chaos, there’s still hope!
Miri
What the crossbeam devs use for testing is Miri. Quoting Miri’s official repo README:
Miri is an Undefined Behavior detection tool for Rust. It can run binaries and test suites of cargo projects and detect unsafe code that fails to uphold its safety requirements. For instance:
- Out-of-bounds memory accesses and use-after-free
- Invalid use of uninitialized data
- Violation of intrinsic preconditions (an unreachable_unchecked being reached, calling copy_nonoverlapping with overlapping ranges, …)
- Not sufficiently aligned memory accesses and references
- Violation of basic type invariants (a bool that is not 0 or 1, for example, or an invalid enum discriminant)
- Data races and emulation of some weak memory effects, i.e., atomic reads can return outdated values
Wonderful, exactly what we need!!
Let’s try it:
cargo +nightly miri test aba_problem::tests::aba
It caught our bug! Notice how it explicitly mentions “Undefined Behaviour” due to a data race.
test aba_problem::tests::aba ... error: Undefined Behavior: Data race detected between (1) thread `unnamed-2` and (2) thread `unnamed-3` at alloc44257
--> /home/sofia/.../alloc/src/boxed.rs:1578:9
|
1578 | Box(unsafe { Unique::new_unchecked(raw) }, alloc)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (2) retag write happened here
|
help: and (1) occurred earlier here
--> src/aba_problem.rs:67:37
|
67 | let new_head = unsafe { (*current_head).next };
| ^^^^^^^^^^^^^^^^^^^^ (1) non-atomic read
|
= help: retags occur on all (re)borrows and as well as when references are copied or moved
= help: retags permit optimizations that insert speculative reads or writes
= help: therefore from the perspective of data races, a retag has the same implications as a read or write
= help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
= note: this is on thread `unnamed-3`
[ Click to expand full backtrace ]
= note: stack backtrace:
0: std::boxed::Box::<aba_problem::Node<i32>>::from_raw_in
at /home/sofia/.../alloc/src/boxed.rs:1578:9
1: std::boxed::Box::<aba_problem::Node<i32>>::from_raw
at /home/sofia/.../alloc/src/boxed.rs:1345:18
2: aba_problem::Stack::<i32>::pop_internal
at src/aba_problem.rs:83:41
3: aba_problem::Stack::<i32>::pop
at src/aba_problem.rs:53:9
4: aba_problem::tests::aba::{closure#0}::{closure#1}
at src/aba_problem.rs:138:49
note: the last function in that backtrace got called indirectly due to this code
--> src/aba_problem.rs:134:13
|
134 | / s.spawn(|| {
135 | | // We wait a little to make sure the first thread gets a head start
136 | | thread::sleep(Duration::from_millis(20));
... |
144 | | println!("thread 2 pushes [3]");
145 | | });
| |______________^
There is still much to learn about Miri, like what exactly is a “retag” operation, but for now, we can be happy that it helped us detect our bug.
The fix
The big question now is, okay, what do we do about it? I won’t go into detail in this post, but some of the techniques include:
- Tagged pointers: adding a tag to the pointer, that is incremented every time the pointer changes.
- Hazard pointers: threads use hazard pointers to mark the objects they are working on so they don’t get dropped.
- Deferred reclamation
- garbage collection
- epoch-based reclamation (EBR) –> what crossbeam-epoch provides :) stay tuned for the next post exploring this!
Check out this post by Aaron Turon, the creator of crossbeam, for a very detailed and easy to follow deep dive into how epoch-based reclamation works.
Conclusion
It was a fun experiment trying to reproduce this and seeing first hand how non-trivial it actually is to catch.
My takeaway: If it was so tricky to reproduce knowing from the start what we’re looking for, imagine how hard it’d be to detect in production code, if we’re not vigilant?
My plan for the future is to continue learning how crossbeam works and hopefully create a second post dissecting crossbeam-epoch. Thank you so much for reading, hope you enjoyed it as much as I enjoyed writing it!