Epoch Adventures: Breaking Free from ABA in Concurrent Rust

• Introduction
• 📺 Series Overview
• 🎯 What is Epoch-Based Reclamation?
• ⚙️ Implementation with crossbeam
• 🧐 How It Works
• 🧪 Testing
• 🔄 Comparison with Tagged Pointers
• 🎯 Design Philosophy
• 💡 Implementation Complexity
• 🔋 Resource Usage
• 🎮 Use Case Decision Matrix
• 🛠 Migration Considerations
• 🎯 Best Use Cases
• 🔬 Performance Analysis
• 🔒 Understanding the Safety of Unsafe Code
• 🛡️ Safety Guarantees
• 🔍 Memory Ordering Guarantees
• Caveats and Limitations of Epoch-Based Reclamation
• 🔗 Resources
• 🤔 Final Thoughts

Introduction

In our previous post, we explored how to solve the ABA problem using tagged pointers. Today, we’ll dive into another powerful solution: epoch-based reclamation (EBR). This approach offers a different trade-off between complexity and performance, making it an excellent choice for many concurrent data structures.

📺 Series Overview

This is the second post in our three-part series on solving the ABA problem in Rust:

1. ✅ Part 1: Tagged Pointers with Versioning — We covered how to pair pointers with version numbers
2. 🎯 Part 2: Epoch-Based Reclamation — Today’s post on using epochs for safe memory management
3. 📅 Part 3: Hazard Pointers — Coming soon: exploring hazard pointers

🎯 What is Epoch-Based Reclamation?

Epoch-based reclamation is a memory management technique that solves the ABA problem by ensuring memory isn’t reused while any thread might be accessing it. Instead of tracking individual pointers, EBR tracks “epochs” — periods during which threads may access shared data.

Key concepts:

• Epochs: Global time periods that threads can participate in
• Pinning: Threads “pin” themselves to the current epoch when accessing shared data
• Deferred Reclamation: Memory is only freed when no thread is in an epoch that could access it

⚙️ Implementation with crossbeam

Here’s our lock-free stack implementation using crossbeam’s epoch-based reclamation:

Read the full blog post here:
https://minikin.me/blog/epoch-adventures-breaking-free-from-aba-in-concurrent-rust