use std::collections::BTreeMap;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Ordering {
Relaxed,
Acquire,
Release,
AcqRel,
SeqCst,
}
impl Ordering {
pub(crate) fn is_acquire(self) -> bool {
matches!(
self,
Ordering::Acquire | Ordering::AcqRel | Ordering::SeqCst
)
}
pub(crate) fn is_release(self) -> bool {
matches!(
self,
Ordering::Release | Ordering::AcqRel | Ordering::SeqCst
)
}
}
pub(crate) type Key = u64;
pub(crate) fn key(block: u32, thread: u32) -> Key {
((block as u64) << 32) | thread as u64
}
#[derive(Clone, Default, Debug)]
pub(crate) struct Clock(BTreeMap<Key, u64>);
impl Clock {
pub(crate) fn get(&self, k: Key) -> u64 {
self.0.get(&k).copied().unwrap_or(0)
}
pub(crate) fn observe(&mut self, k: Key, seq: u64) {
let slot = self.0.entry(k).or_insert(0);
if seq > *slot {
*slot = seq;
}
}
pub(crate) fn join(&mut self, other: &Clock) {
for (&k, &seq) in &other.0 {
self.observe(k, seq);
}
}
pub(crate) fn is_empty(&self) -> bool {
self.0.is_empty()
}
}
pub(crate) struct SyncState {
seq: Vec<u64>,
clock: Vec<Clock>,
fence_release: Vec<Clock>,
fence_acquire: Vec<Clock>,
block: Vec<Clock>,
}
impl SyncState {
pub(crate) fn new(threads: usize, blocks: usize) -> Self {
SyncState {
seq: vec![0; threads],
clock: vec![Clock::default(); threads],
fence_release: vec![Clock::default(); threads],
fence_acquire: vec![Clock::default(); threads],
block: vec![Clock::default(); blocks],
}
}
pub(crate) fn barrier_arrive(&mut self, gid: usize, block: usize) {
let mine = self.clock[gid].clone();
self.block[block].join(&mine);
}
pub(crate) fn barrier_depart(&mut self, gid: usize, block: usize) {
let shared = self.block[block].clone();
self.clock[gid].join(&shared);
}
pub(crate) fn tick(&mut self, gid: usize, k: Key) -> u64 {
self.seq[gid] += 1;
let seq = self.seq[gid];
self.clock[gid].observe(k, seq);
seq
}
pub(crate) fn clock(&self, gid: usize) -> &Clock {
&self.clock[gid]
}
pub(crate) fn release(&mut self, gid: usize, target: &mut Clock, ordering: Ordering) {
if ordering.is_release() {
let mine = self.clock[gid].clone();
target.join(&mine);
}
if !self.fence_release[gid].is_empty() {
let fenced = self.fence_release[gid].clone();
target.join(&fenced);
}
}
pub(crate) fn acquire(&mut self, gid: usize, source: &Clock, ordering: Ordering) {
if source.is_empty() {
return;
}
if ordering.is_acquire() {
self.clock[gid].join(source);
} else {
self.fence_acquire[gid].join(source);
}
}
pub(crate) fn fence(&mut self, gid: usize, ordering: Ordering) {
if ordering.is_acquire() {
let pending = std::mem::take(&mut self.fence_acquire[gid]);
self.clock[gid].join(&pending);
}
if ordering.is_release() {
self.fence_release[gid] = self.clock[gid].clone();
}
}
}