Lock-Free Graph Refactoring with C11 Atomics

The Problem with Locks and the Promise of Atomics

A lock, fundamentally, protects a critical section of code. An atomic operation, in contrast, protects a single piece of data. It guarantees that a modification to a variable (like an integer or a pointer) is indivisible. While one thread is performing an atomic read-modify-write operation, no other thread can see the data in a half-modified state.

To see why this matters, consider a classic race condition when inserting a node into a linked list, a structure analogous to our graph connections.

Atomic operations provide a way to perform these updates safely without a lock.

Introducing C11 Atomics

The C11 standard introduced the <stdatomic.h> header, which provides a portable way to access these powerful hardware features. Let's explore the fundamentals with a clear, practical guide.

As you've just read, an atomic variable guarantees two things:

1. Atomicity: Read and write operations are indivisible. For a simple _Atomic int x;, another thread will see the value of x either before or after a write, never a partially-written value.
2. Synchronization: An atomic write in one thread synchronizes with a subsequent atomic read of the same variable in another thread. This forces memory visibility. All memory writes (even to non-atomic variables) that happened before the atomic write in thread 1 become visible to thread 2 after its atomic read.

Key Atomic Operations

While simple assignment (x = 5;) to an atomic variable is atomic, compound operations like x = x + 1; are not, as they involve a separate read and a write. <stdatomic.h> provides atomic versions of these common patterns.

The most important operations you'll use are:

• Atomic Read-Modify-Write Operators: For built-in types, operators like +=, -=, ++, --, |=, &= are overloaded to be atomic. So, atomic_counter++ is a safe, single atomic operation.
• atomic_fetch_add(obj, arg): Atomically adds arg to *obj and returns the value *obj held before the addition. There are also _sub, _or, _and, etc.
• atomic_load(obj): Atomically reads and returns the value of *obj.
• atomic_store(obj, desired): Atomically writes desired into *obj.
• atomic_compare_exchange_strong(obj, expected, desired): This is the workhorse of most lock-free algorithms. It works like this, as a single, indivisible hardware operation:
  1. Atomically, it reads the current value at *obj.
  2. It compares this value to what's in *expected.
  3. If they are equal, it means the value hasn't changed since we last looked. It then atomically writes desired into *obj and returns true.
  4. If they are not equal, it means another thread modified *obj. The write does not happen. Instead, the current value of *obj is written into *expected, and the function returns false. This conveniently gives you the new value so you can retry your operation.

This "compare-and-swap" (CAS) pattern is fundamental. A typical usage is a loop:

// Attempt to atomically change 'ptr' from 'old_val' to 'new_val'
_Atomic some_ptr_t ptr;
some_ptr_t old_val = atomic_load(&ptr);
some_ptr_t new_val = /* calculate new value */;

// Keep trying until the CAS succeeds.
// If another thread changes ptr, the CAS will fail, 
// old_val will be updated with the new current value, and we loop.
while (!atomic_compare_exchange_strong(&ptr, &old_val, new_val)) {
    // The value changed. Recalculate new_val based on the updated old_val.
    new_val = /* recalculate based on new old_val */;
}

A Quick Word on Memory Ordering

As Beej's Guide noted, atomic operations also define memory ordering. By default, C11 atomics provide sequential consistency (memory_order_seq_cst). This is the most intuitive model: it guarantees that all threads agree on a single global timeline of operations. For performance-critical code, you can use "weaker" memory orders like memory_order_acquire and memory_order_release (or even memory_order_relaxed) to give the compiler and CPU more freedom to reorder instructions.

This is an advanced topic, but the core idea is:

• An acquire operation (like a load) prevents subsequent memory operations from being moved before it.
• A release operation (like a store) prevents preceding memory operations from being moved after it.

For now, we will stick with the default sequential consistency, which is always safe.

Applying Atomics to the HNSW Graph

Now, let's refactor our hnsw_index_t structure. Previously, any change to graph metadata required a full write lock. Let's identify candidates for atomic variables.

// Original structure
typedef struct {
    // ...
    pthread_rwlock_t lock;
    
    hnsw_node_id_t entry_point;
    int max_layer;
    size_t count; // Total number of vectors
    
    memory_arena_t node_pool;
} hnsw_index_t;

// Refactored structure



#include <stdatomic.h>

typedef struct {
    // ...
    pthread_rwlock_t lock; // Still needed for complex structural changes
    
    _Atomic hnsw_node_id_t entry_point;
    _Atomic int max_layer;
    _Atomic size_t count; // Total number of vectors
    
    memory_arena_t node_pool;
} hnsw_index_t;

By making entry_point, max_layer, and count atomic, we can now update them without acquiring the main rwlock.

Updating the element count:

• Before:

  pthread_rwlock_wrlock(&graph->lock);
  graph->count++;
  pthread_rwlock_unlock(&graph->lock);
  

• After:

  // This is an atomic read-modify-write operation.
  // memory_order_relaxed is often sufficient for a simple counter
  // if no other memory operations depend on its ordering.
  // However, the default sequential consistency is always safe to start with.
  atomic_fetch_add(&graph->count, 1);
  

Updating the entry point:

The entry point only changes if a new node is inserted at a layer higher than any existing node. This is a more complex operation, but the final pointer swap can be made atomic.

• Before:

  pthread_rwlock_wrlock(&graph->lock);
  // ... logic to determine if new_node is the new entry point ...
  if (is_new_entry_point) {
      graph->entry_point = new_node_id;
      graph->max_layer = new_node_layer;
  }
  pthread_rwlock_unlock(&graph->lock);
  

• After: The complex logic of finding neighbors for the new node might still need a lock, but the final update to the shared entry_point and max_layer can be atomic stores. This separates the concerns.

  // A release operation ensures all writes that constructed the new node
  // are visible before the entry_point is updated.
  atomic_store_explicit(&graph->max_layer, new_node_layer, memory_order_release);
  atomic_store_explicit(&graph->entry_point, new_node_id, memory_order_release);
  

  Readers would then use atomic_load_explicit(&graph->entry_point, memory_order_acquire) to ensure they see a consistent state.

The ABA Problem: A Lock-Free "Gotcha"

Lock-free programming is powerful, but full of subtleties. One of the most famous is the ABA problem. Imagine a CAS loop trying to pop from a stack.

1. Thread 1 reads the head of the stack, pointer A.
2. Thread 1 is preempted.
3. Thread 2 pops A, then pops B, then pushes A back on top. The stack's head is A again, but the underlying state (B is gone) is different.
4. Thread 1 resumes. Its CAS operation checks if the head is still A. It is! The CAS succeeds, but it operates on a stack that has changed in a way it didn't detect.

This is a deep topic, but understanding its existence is key to appreciating the complexities of this domain.

For our current refactoring of simple counters and pointers, the ABA problem is not an immediate concern. However, as you build more complex lock-free data structures, it's a critical hazard to be aware of.

Conclusion

In this lesson, we have opened the door to lock-free programming, a cornerstone of high-performance systems. You've moved from the coarse-grained protection of a read-write lock to the fine-grained, hardware-level guarantees of C11 atomics.

Key Takeaways:

• Atomic operations are indivisible (all-or-nothing) and provide memory synchronization guarantees between threads.
• They allow you to avoid locks for simple data updates, reducing overhead and eliminating certain blocking scenarios.
• The C11 <stdatomic.h> header provides types like _Atomic int and functions like atomic_fetch_add and atomic_compare_exchange_strong (CAS).
• CAS is the fundamental primitive for building complex lock-free algorithms, allowing you to atomically "swap if equal" in a retry loop.
• We've identified and refactored simple counters and pointers (count, entry_point, max_layer) in our HNSW graph to use atomic types, reducing the scope of our coarse-grained write lock.

We still have our pthread_rwlock_t for protecting more complex structural modifications, like adding and pruning connections, which involve multiple, non-atomic memory locations. Our system now uses a hybrid approach: lock-free operations for simple state and locks for complex critical sections. This mix of synchronization primitives can, however, introduce new challenges. In our next lesson, we will analyze the most dangerous of these: deadlocks. You'll learn how they arise and how to design your locking strategies to prevent them.