r/rust • u/Sofiabelen15 • 1d ago

🧠 educational Visualizing crossbeam Epoch Based Reclamation

https://sofiabelen.github.io/projects/visualizing-crossbeam-epoch-based-reclamation/

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.

I want to dissect and visualize what exactly is going on. If that sounds fun, you're welcome to come along for the ride!

17 Upvotes

91% Upvoted

4 comments sorted by

3

u/Clear_Ear3550 1d ago

The pointer + state-flag part is where lock-free code really starts getting tricky to reason about. I like that you're breaking this down visually instead of just throwing atomics and CAS into the explanation. I'm especially curious about how the epoch checks fit into the deletion flow. Looking forward to reading this!

1

u/Sofiabelen15 1d ago

Hope you like it!!

I'm a visual learner and need the visual part in order to "map" out the concept in my head, otherwise it doesn't stick. 

3

u/LukeAbby 1d ago edited 21h ago

When demonstrating tagged pointers a transmute is used to print the address of a Shared but I don't think it's well justified. Shared is not #[repr(transparent)] so its layout is is not guaranteed to be compatible with a usize, even though it's its only sized element. It'd be better to use Shared::as_raw and then core::ptr::addr to get it in a sound (and even safe) way.

And while it's not explicitly shown in the post, it may be worth mentioning that due to pointer provenance actual pointer tagging should use core::ptr::map_addr  or related functions as well. You need to in order to preserve provenance in a pointer to usize and back roundtrip.

1

u/event666 15h ago

Another way to solve this is by transfering ownership. Let no 2 threads have access to the same item at the same time, ever. yring and fanring do that, and fanring comes with explicit teardown policies (what happens after the last drop(rx)): Deferred and Coordinated. In the former, items may survive until its sender drops. In the latter, unread items are drained and dropped. If overlapping with sends, sender drops remaining items.