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.
Currently, MwCas supports only x8664 platform because it exploits
platform specific hacks: MwCas use upper 3 bit of pointer's virtual
address to representing internal state. Today x8664 CPUs use lower 48
bits of virtual address, other 16 bits are 0. Usage of upper 3 bits
described in paper.
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 = crossbeamepoch::pin(); let curptr_val: &String = ptr.read(&guard);
let mut mwcas = MwCas::new(); mwcas.compareexchange(&ptr, curptrval, String::from("newstring")); mwcas.compareexchangeu64(&val, 0, 1);
assert!(mwcas.exec(&guard)); asserteq!(ptr.read(&guard), &String::from("newstring")); assert_eq!(val.read(&guard), 1); ```
Drop of values pointed by HeapPointer which were replaced by new one
during CAS, will be performed by crossbeam_epoch memory
reclamation.