Multi-word CAS.

Rust standard library provides atomic types in atomic package. Atomic types provide lock-free way to atomically update value of one pointer. Many concurrent data structures usually requires atomic update for more than 1 pointer at time. For example, BzTree described in paper(implementation in Rust).

This crate provides concurrency primitive called MwCas which can atomically update several pointers at time. It is based on paper Easy Lock-Free Indexing in Non-Volatile Memory. Current implementation doesn't provide features for non-volatile memory(persistent memory) and only covers DRAM multi-word CAS.

Platform support

Currently, MwCas supports only x86_64 platform because it exploits platform specific hacks: MwCas use upper 3 bit of pointer's virtual address to representing internal state. Today x86_64 CPUs use lower 48 bits of virtual address, other 16 bits are 0. Usage of upper 3 bits described in paper.

Usage

Multi-word CAS API represented by MwCas struct which can operate on 2 types of pointers:

• pointer to heap allocated data(HeapPointer)
• pointer to u64(U64Pointer)

HeapPointer can be used to execute multi-word CAS on any data type, but with cost of heap allocation. U64Pointer do not allocate anything on heap and has memory overhead same as u64.

MwCas is a container for chain of compare_exchange operations. When caller adds all required CASes, it performs multi-word CAS by calling exec method. exec method returns bool which indicate is MwCAS was successful.

Example of MwCAS usage:

use mwcas::{MwCas, HeapPointer, U64Pointer};

let ptr = HeapPointer::new(String::new());
let val = U64Pointer::new(0);
let guard = crossbeam_epoch::pin();
let cur_ptr_val: &String = ptr.read(&guard);

let mut mwcas = MwCas::new();
mwcas.compare_exchange(&ptr, cur_ptr_val, String::from("new_string"));
mwcas.compare_exchange_u64(&val, 0, 1);

assert!(mwcas.exec(&guard));
assert_eq!(ptr.read(&guard), &String::from("new_string"));
assert_eq!(val.read(&guard), 1);

Memory reclamation

Drop of values pointed by HeapPointer which were replaced by new one during CAS, will be performed by crossbeam_epoch memory reclamation.