Synchronization Primitives

Compare-and-Swap

Compare-and-Swap (CAS) is the foundational atomic read-modify-write primitive for lock-free algorithms. It compares an atomic variable's current value against an expected value and, if and only if they are equal, replaces the variable's value with new in a single indivisible hardware step, returning Result<T, T> containing the value observed before the operation.

compare_exchange vs. compare_exchange_weak

Rust's atomic types provide two compare-and-swap methods (plus the closure-based .fetch_update() helper):

pub fn compare_exchange(
    &self,
    current: T,
    new: T,
    success: Ordering,
    failure: Ordering,
) -> Result<T, T>;

pub fn compare_exchange_weak(
    &self,
    current: T,
    new: T,
    success: Ordering,
    failure: Ordering,
) -> Result<T, T>;
Method Can Fail Spuriously When *self == current? Best Used When
compare_exchange No (Err(actual) is returned only when actual != current) Single-shot state transitions (if state.compare_exchange(IDLE, RUNNING, ...).is_ok())
compare_exchange_weak Yes (on LL/SC architectures like ARM/RISC-V, a cache-line interruption can cause Err(actual) even when actual == current) Inside a retry loop (while let Err(actual) = ...), where it compiles to a single fast LL/SC pair on ARM instead of a nested hardware loop!
fetch_update(set_order, fetch_order, f) Wraps a compare_exchange_weak loop automatically Computing a new value Option<T> as a pure function of the current value 
CAS Retry Loop (`compare_exchange_weak`):

  let mut cur = atomic.load(Ordering::Relaxed);
  loop {
      let next = compute_from(cur);
      match atomic.compare_exchange_weak(cur, next, Ordering::AcqRel, Ordering::Relaxed) {
          Ok(prev) => break prev,       // Succeeded! `atomic` is now `next`
          Err(actual) => cur = actual,  // Another thread modified `atomic` (or spurious fail);
      }                                 // retry immediately with the fresh `actual` value!
  }

Implementing Conditional Saturating Subtraction with a CAS Loop and fetch_update

Because hardware does not provide a single instruction for "subtract amount only if balance >= amount, otherwise leave unchanged", this operation is implemented using either a compare_exchange_weak loop or .fetch_update(...):

use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;

fn try_withdraw_cas(balance: &AtomicU64, amount: u64) -> Result<u64, u64> {
    let mut current = balance.load(Ordering::Relaxed);
    loop {
        if current < amount {
            return Err(current);
        }
        let next = current - amount;
        match balance.compare_exchange_weak(
            current,
            next,
            Ordering::AcqRel,
            Ordering::Relaxed,
        ) {
            Ok(_) => return Ok(next),
            Err(actual) => current = actual,
        }
    }
}

fn multiply_capped(value: &AtomicU64, factor: u64, cap: u64) -> u64 {
    // `.fetch_update()` runs the `compare_exchange_weak` loop automatically:
    value
        .fetch_update(Ordering::AcqRel, Ordering::Relaxed, |cur| {
            Some((cur * factor).min(cap))
        })
        .unwrap()
}

fn main() {
    let account = AtomicU64::new(250);

    thread::scope(|s| {
        for _ in 0..4 {
            s.spawn(|| {
                let _ = try_withdraw_cas(&account, 100);
            });
        }
    });

    // Only two 100-unit withdrawals can succeed out of 250 -> 50 remains!
    println!("remaining balance after 4x100 attempts: {}", account.load(Ordering::Relaxed));

    multiply_capped(&account, 10, 300);
    println!("after capped multiply:                  {}", account.load(Ordering::Relaxed));
}

remaining balance after 4x100 attempts: 50
after capped multiply:                  300