2 unstable releases
0.2.0 | Oct 20, 2022 |
---|---|
0.1.0 | Jul 4, 2021 |
#486 in Concurrency
Used in bztree
43KB
755 lines
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.
Dependencies
~260KB