Crate mwcas

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.

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.

Structs

HeapPointer

Pointer to data located on heap.

MwCas

Multi-word CAS structure.

U64Pointer

Pointer to u64 data.