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.