atomic-tagged-ptr

A high-performance, zero-overhead, platform-adaptive atomic tagged pointer implementation in Rust.

Specially tailored for lock-free intrusive data structures (such as Treiber Stack) with ABA protection, supporting 32-bit and 64-bit platforms, as well as 48-bit, 52-bit, and 57-bit virtual address spaces (such as Intel 5-level paging) without pointer truncation, provenance loss, or memory corruption.

Core Features
Hardware Realities & Memory Layout Design
Auto-Detection & Environment Variables
Installation
Usage Examples
- Concurrent Treiber Stack Implementation
API Overview
Robust CI Testing in QEMU VM
License

Core Features

Platform-Adaptive Memory Layout: Dynamically adjusts layout to fit 48-bit, 52-bit, and 57-bit virtual address limits at build time, optimizing tag bits while preventing pointer corruption.
Zero Overhead: Direct hardware mapping to atomic operations (cmpxchg on x86_64, ldrex/strex or cas on AArch64, cmpxchg8b on x86-32, ldrd/strd on ARMv7-A) without locking.
Preserves Strict Provenance: Utilizes modern core::ptr::with_exposed_provenance_mut to avoid unsafe pointer hacks, aligning with the latest Rust strict provenance guidelines.
Robust Fallback: Automatically falls back to Mutex/spinlock-based synchronization on platforms lacking native 64-bit atomics, ensuring 100% compilation and API consistency. If std is enabled, it uses std::sync::Mutex (or a faster parking_lot::Mutex if the parking_lot feature is enabled). If std is disabled, it uses a lightweight, dependency-free spinlock.
#![no_std] Support: Core functions work in no_std environments by default. When native 64-bit atomics are unavailable, it seamlessly falls back to a custom spinlock-based implementation without requiring the std feature.
Comprehensive CI Verification: Verified via real QEMU virtual machine emulation on GitHub Actions to test and assert correctness under actual 57-bit virtual address spaces (Intel 5-level paging).

Hardware Realities & Memory Layout Design

In lock-free concurrent programming, the ABA problem frequently arises. The traditional mitigation involves pairing the physical pointer with a generation tag, updating both atomically. However, 64-bit pointer packing faces strict hardware constraints:

1. 64-bit Platforms (Standard 48-bit Virtual Address Space)

For standard 64-bit architectures (like Apple M-series, x86_64 with 4-level paging) where virtual addresses use at most 48 bits, we pack a 16-bit generation tag and a 48-bit pointer into a single 64-bit usize word.

 63            48 47                                             0
+----------------+------------------------------------------------+
|  16-Bit Tag    |               48-Bit Pointer                   |
+----------------+------------------------------------------------+

2. 64-bit Platforms (Intel 5-level Paging / 57-bit Address Space / ARMv8.2 52-bit)

On modern servers with Intel 5-level paging (supporting up to 57-bit address spaces) or ARMv8.2 with 52-bit virtual addresses, assuming a 48-bit limit causes immediate truncation and kernel crashes.

To resolve this, atomic-tagged-ptr automatically transitions to a 56-bit pointer and 8-bit tag layout. Since user-space addresses in 57-bit systems reside within the positive half [0, 0x007f_ffff_ffff_ffff], the pointer fits perfectly within 56 bits without any truncation, while providing an 8-bit tag for ABA protection.

 63        56 55                                                 0
+------------+----------------------------------------------------+
| 8-Bit Tag  |               56-Bit Pointer                       |
+------------+----------------------------------------------------+

3. 32-bit Platforms (Direct 64-bit Atomic Packing)

On 32-bit systems, the pointer fits entirely in 32 bits. We pair it with a 32-bit generation tag to form a double-word 64-bit integer, and utilize native double-word 64-bit atomic operations (cmpxchg8b on x86, ldrd/strd on ARM) to perform lock-free CAS.

 63                            32 31                             0
+--------------------------------+--------------------------------+
|          32-Bit Tag            |         32-Bit Pointer         |
+--------------------------------+--------------------------------+

4. Fallback Systems

On platforms where native 64-bit atomics are unavailable (or forced fallback is requested), atomic-tagged-ptr automatically switches to Mutex/spinlock-based wrapping. The tag and pointer occupy full usize widths (providing maximum generation range) while offering identical API signatures. When the std feature is enabled, it uses std::sync::Mutex (or parking_lot::Mutex if the parking_lot feature is enabled). When the std feature is disabled (i.e. no_std), it uses a custom lightweight spinlock backend, requiring zero external dependencies.

Auto-Detection & Environment Variables

The build.rs script automatically identifies target capabilities:

Apple Targets: Statically defaults to the 48-bit layout (16-bit tag), since Apple Silicon and iOS utilize 48-bit virtual address limits.
Local Native Compilation: Runs run-time checks on the host OS. On Windows, it queries GetSystemInfo to determine virtual address space boundaries. On Linux, it probes /proc/cpuinfo and performs high-address mmap checks to see if 5-level paging is active.
Cross-Compilation / Unknown Targets: Conservatively defaults to the 57-bit layout (8-bit tag) to ensure absolute pointer safety.

Control Environment Variables

ATOMIC_TAGGED_PTR_FORCE_VIRT_ADDR=48: Override detection and force the 48-bit layout (16-bit tag, 256x stronger ABA protection).
ATOMIC_TAGGED_PTR_FORCE_VIRT_ADDR=57: Override detection and force the 57-bit layout (8-bit tag).
ATOMIC_TAGGED_PTR_PRINT_AUTODETECT=true: Output auto-detection diagnostic logs during crate compilation.

Installation

Add this to your Cargo.toml:

[dependencies]
atomic-tagged-ptr = "0.3.2"

To use in no_std environments, disable the default features:

[dependencies]
atomic-tagged-ptr = { version = "0.3.2", default-features = false }

Usage Examples

Concurrent Treiber Stack Implementation

Below is a complete, concurrent lock-free Treiber Stack implementation using AtomicTaggedPtr to defend against the ABA problem:

use core::ptr::NonNull;
use core::sync::atomic::Ordering;
use atomic_tagged_ptr::{AtomicTaggedPtr, Tag};

/// A node in the intrusive Treiber Stack.
pub struct StackNode {
    pub value: usize,
    // Intrusive next pointer slot
    next: AtomicTaggedPtr<StackNode>,
}

/// A lock-free intrusive Treiber Stack.
pub struct TreiberStack {
    // Head pointer along with generation tag for ABA defense
    head: AtomicTaggedPtr<StackNode>,
}

impl TreiberStack {
    pub fn new() -> Self {
        Self {
            head: AtomicTaggedPtr::default(),
        }
    }

    /// Pushes a node onto the stack.
    pub fn push(&self, node: &StackNode) {
        let node_ptr = NonNull::from(node);
        let mut bits = self.head.load(Ordering::Acquire);
        loop {
            // Link our node to the current head pointer
            node.next.store(bits, Ordering::Release);

            // Increment the generation tag to defend against ABA
            let next_tag = bits.tag.wrapping_add(1);

            match self.head.compare_exchange_weak(
                bits,
                (node_ptr, next_tag),
                Ordering::Release,
                Ordering::Acquire,
            ) {
                Ok(_) => break,
                Err(actual) => bits = actual,
            }
        }
    }

    /// Pops a node from the stack.
    ///
    /// # Safety
    /// Popped nodes must remain valid. This example assumes static nodes or standard GC.
    pub unsafe fn pop(&self) -> Option<&StackNode> {
        let mut bits = self.head.load(Ordering::Acquire);
        loop {
            let head_ptr = bits.ptr.option()?;

            // Read the next node intrusively
            let next_state = head_ptr.as_ref().next.load(Ordering::Acquire);

            // Increment the generation tag to defend against ABA
            let next_tag = bits.tag.wrapping_add(1);

            match self.head.compare_exchange_weak(
                bits,
                (next_state.ptr, next_tag),
                Ordering::Release,
                Ordering::Acquire,
            ) {
                Ok(_) => return Some(head_ptr.as_ref()),
                Err(actual) => bits = actual,
            }
        }
    }
}

API Overview