Lock-Free Data Structures with Generics

Lesson 734: Lock-Free Data Structures with Generics

In this lesson, you will learn how to build a thread-safe, lock-free stack by using generics alongside AtomicPtr to manage memory without traditional mutexes.

The Challenge of Generic Atomic Access

When we create a lock-free stack, we aren't protecting data with a lock; instead, we rely on the AtomicPtr<T> type to perform "Compare and Swap" (CAS) operations. A lock-free stack usually consists of a linked list where nodes are pushed or popped by updating the head pointer atomically.

To make this generic, we define a node structure that can hold any type T:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

pub struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
}

Implementing Push with Generics

The core of a lock-free push operation is to read the current head, set the new node's next pointer to that head, and then attempt to swap the head to point to our new node. If another thread changes the head while we are preparing our update, the CAS operation fails, and we retry.

impl<T> LockFreeStack<T> {
    pub fn push(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node { data, next: ptr::null_mut() }));
        loop {
            let head = self.head.load(Ordering::Relaxed);
            unsafe { (*new_node).next = head; }
            
            if self.head.compare_exchange(head, new_node, Ordering::Release, Ordering::Relaxed).is_ok() {
                break;
            }
        }
    }
}

Why Generics Matter Here

By using generics, we decouple the memory management logic from the specific type being stored. The atomic pointer doesn't care what T is; it only cares about the memory address of the Node<T>. Because Rust’s type system enforces that our generic T satisfies safety constraints at compile time, we can ensure that our lock-free operations are sound, provided we carefully manage the Unsafe blocks required to manipulate raw pointers. This allows us to write highly performant, re-usable concurrent primitives that work for integers, strings, or custom structs without duplicating code.

Key Takeaway: Generics allow us to encapsulate low-level atomic pointer manipulation into reusable, type-safe structures while maintaining the performance benefits of lock-free concurrency.