← Back to Blog
EN中文

The Counter in the Pointer: Wait-Free Atomic Shared Ptr via 64-bit Address Space

In the deep end of concurrent programming, we're always chasing the perfect primitive: automatic memory management like std::shared_ptr, atomic exchange across threads, and ideally, wait-free guarantees.

Standard C++ std::shared_ptr, despite the name, is not thread-safe for the pointer object itself. Reading and writing to the same shared_ptr instance from multiple threads is a data race. C++20 introduced std::atomic<std::shared_ptr>, but under the hood, it often relies on spinlocks or complex CAS loops that degrade under contention.

Today, we're dissecting a technique found in industrial-grade distributed systems: using the high 16 bits of an x86_64 pointer to store a reference count, enabling truly wait-free pointer acquisition.

Why shared_ptr Isn't Enough

The reference count inside std::shared_ptr's control block is atomic. That's fine. But the shared_ptr object itself consists of two pointers: one to the object, one to the control block.

Updating a shared_ptr is not an atomic operation—it involves writing two words. If a read happens between these writes, you get a race condition: a pointer to a new object with an old control block (or vice versa).

The traditional fix is std::mutex or std::atomic_load. But in high-performance scenarios, locks mean waiting, context switches, and latency spikes.

Pointer Tagging: Squeezing the 64-bit Space

On x86_64, virtual addresses are 64 bits wide, but only the lower 48 bits are actually used (canonical form). The upper 16 bits are effectively wasted space—usually all zeros.

These 16 bits are a gold mine for optimization.

What if we used them to store a "local reference count" or an operation tag?

The Core Magic: Single Atomic Add

Imagine a 64-bit atomic layout:

  • High 16 bits: Reference count (or "acquire count").
  • Low 48 bits: The actual memory address.

To acquire the pointer, we don't need a CAS loop. We don't need a lock. We just need one fetch_add:

// Pseudo-code
let old_value = atomic_ptr.fetch_add(1 << 48, Ordering::SeqCst);
let ptr = old_value & 0x0000_FFFF_FFFF_FFFF;

This single instruction does two things:

  1. Atomically increments the high-bit counter.
  2. Atomically returns the old value (containing the valid pointer) before the increment.

Because it's a single atomic instruction, even with ten thousand threads contending, every thread gets a consistent pointer and correctly increments the count. No thread waits. No loops. This is Wait-Free.

Rust Implementation: A Clean Room Demo

To demonstrate this, I've reconstructed the core mechanism in Rust. Rust's type system makes the ownership semantics much clearer.

use std::sync::atomic::{AtomicU64, Ordering};
use std::marker::PhantomData;

/// A demonstration of Wait-Free Atomic Pointer.
/// Core idea: Use AtomicU64 to store [16-bit counter | 48-bit address]
pub struct WaitFreeAtomicPtr<T> {
    inner: AtomicU64,
    _marker: PhantomData<T>,
}

const ADDR_MASK: u64 = 0x0000_FFFF_FFFF_FFFF;
const COUNT_SHIFT: u32 = 48;
const COUNT_INC: u64 = 1 << COUNT_SHIFT;

impl<T> WaitFreeAtomicPtr<T> {
    pub fn new(data: T) -> Self {
        let boxed = Box::new(data);
        let ptr = Box::into_raw(boxed) as u64;
        // Init: High bits count = 1, Low bits = ptr
        Self {
            inner: AtomicU64::new(COUNT_INC | ptr),
            _marker: PhantomData,
        }
    }

    /// Wait-Free Acquire
    pub fn acquire(&self) -> SharedGuard<T> {
        // The magic: atomic increment high bits, get old ptr
        // No CAS loop, no lock.
        let prev = self.inner.fetch_add(COUNT_INC, Ordering::SeqCst);
        let ptr = (prev & ADDR_MASK) as *mut T;
        
        SharedGuard {
            ptr,
            parent: &self.inner,
        }
    }
}

pub struct SharedGuard<'a, T> {
    ptr: *mut T,
    parent: &'a AtomicU64,
}

impl<'a, T> Drop for SharedGuard<'a, T> {
    fn drop(&mut self) {
        // On drop, atomically decrement high bits
        self.parent.fetch_sub(COUNT_INC, Ordering::SeqCst);
    }
}

Key Takeaways

  1. fetch_add as a Read Lock: This is the soul of the design. Usually, fetch_add is just a counter. Here, it acts as both a "read lock" acquisition and data retrieval. Since the address is in the low bits, adding to the high bits doesn't corrupt the address (unless overflow happens, which is a separate constraint).
  2. Wait-Free Property: Regardless of contention, every acquire completes in a finite number of steps. This is stronger than Lock-Free (which guarantees system progress but allows individual starvation).

Trade-offs and Reality

If this is so great, why doesn't std::shared_ptr do it?

  1. Architecture Dependency: This relies hard on the 48-bit virtual address limit of current x86_64. On 32-bit systems, or future 57-bit address spaces (Intel 5-level paging), this breaks. Standard libraries prioritize portability.
  2. Counter Overflow: 16 bits only hold 65,535 references. For massive concurrency, this isn't enough. Real-world implementations often have a mechanism to "flush" the high-bit counter into a real control block counter periodically, or use fallback paths.
  3. Memory Alignment: Safe bit manipulation usually requires pointers to be aligned (e.g., 8-byte boundaries) so low bits don't carry information that gets corrupted by arithmetic.

Summary

This design illustrates a mindset of extreme systems programming: when standard abstractions (mutexes, CAS) become bottlenecks, break the abstraction and exploit hardware specifics (like address layout).

It's not portable code. It's not safe code by default. But for specific industrial middleware, this kind of bit-level dance—squeezing logic into a single 64-bit integer—is exactly what high performance looks like.