use crate::runtime::sync::sync::atomic::{AtomicUsize, Ordering};
const RUNNING: usize = 1;
const EPOCH_STEP: usize = 2;
enum Acquire {
Runner { epoch: usize },
Recorded,
}
enum Release {
Idle,
Pending(usize),
}
struct GateState {
packed: AtomicUsize,
}
impl GateState {
fn new() -> Self {
Self {
packed: AtomicUsize::new(0),
}
}
fn acquire(&self) -> Acquire {
loop {
let s = self.packed.load(Ordering::SeqCst);
if s & RUNNING == 0 {
if self
.packed
.compare_exchange_weak(s, s | RUNNING, Ordering::SeqCst, Ordering::SeqCst)
.is_ok()
{
return Acquire::Runner { epoch: s >> 1 };
}
} else {
if self
.packed
.compare_exchange_weak(s, s + EPOCH_STEP, Ordering::SeqCst, Ordering::SeqCst)
.is_ok()
{
return Acquire::Recorded;
}
}
}
}
fn release(&self, observed: usize) -> Release {
let expected = (observed << 1) | RUNNING;
let idle = observed << 1; match self
.packed
.compare_exchange(expected, idle, Ordering::SeqCst, Ordering::SeqCst)
{
Ok(_) => Release::Idle,
Err(actual) => Release::Pending(actual >> 1),
}
}
fn force_idle(&self) {
self.packed.fetch_and(!RUNNING, Ordering::SeqCst);
}
}
pub(in crate::scheduler) struct GenerateWorkGate {
state: GateState,
}
impl GenerateWorkGate {
pub(in crate::scheduler) fn new() -> Self {
Self {
state: GateState::new(),
}
}
pub(in crate::scheduler) fn try_acquire(&self) -> Option<GenerateWorkPermit<'_>> {
match self.state.acquire() {
Acquire::Runner { epoch } => Some(GenerateWorkPermit {
gate: self,
seen_epoch: epoch,
released: false,
}),
Acquire::Recorded => None,
}
}
}
pub(in crate::scheduler) struct GenerateWorkPermit<'a> {
gate: &'a GenerateWorkGate,
seen_epoch: usize,
released: bool,
}
impl GenerateWorkPermit<'_> {
pub(in crate::scheduler) fn try_release(&mut self) -> bool {
match self.gate.state.release(self.seen_epoch) {
Release::Idle => {
self.released = true;
true
}
Release::Pending(new_epoch) => {
self.seen_epoch = new_epoch;
false
}
}
}
}
impl Drop for GenerateWorkPermit<'_> {
fn drop(&mut self) {
if !self.released {
self.gate.state.force_idle();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn new_is_idle_epoch_zero() {
let g = GateState::new();
assert_eq!(g.packed.load(Ordering::Relaxed), 0);
}
#[test]
fn acquire_from_idle_becomes_runner() {
let g = GateState::new();
match g.acquire() {
Acquire::Runner { epoch } => assert_eq!(epoch, 0),
Acquire::Recorded => panic!("expected Runner"),
}
assert_eq!(g.packed.load(Ordering::Relaxed), RUNNING);
}
#[test]
fn acquire_while_running_records_and_bumps_epoch() {
let g = GateState::new();
let Acquire::Runner { .. } = g.acquire() else {
panic!("expected Runner");
};
match g.acquire() {
Acquire::Recorded => {}
Acquire::Runner { .. } => panic!("expected Recorded"),
}
assert_eq!(g.packed.load(Ordering::Relaxed), RUNNING | (1 << 1));
}
#[test]
fn release_at_same_epoch_goes_idle() {
let g = GateState::new();
let Acquire::Runner { epoch } = g.acquire() else {
panic!("expected Runner");
};
match g.release(epoch) {
Release::Idle => {}
Release::Pending(_) => panic!("expected Idle"),
}
assert_eq!(g.packed.load(Ordering::Relaxed), 0);
}
#[test]
fn release_at_stale_epoch_reports_pending() {
let g = GateState::new();
let Acquire::Runner { epoch } = g.acquire() else {
panic!("expected Runner");
};
g.acquire(); match g.release(epoch) {
Release::Pending(new_epoch) => assert_eq!(new_epoch, 1),
Release::Idle => panic!("expected Pending"),
}
assert_eq!(g.packed.load(Ordering::Relaxed) & RUNNING, RUNNING);
}
#[test]
fn multiple_bumps_then_release() {
let g = GateState::new();
let Acquire::Runner { epoch } = g.acquire() else {
panic!("expected Runner");
};
assert_eq!(epoch, 0);
g.acquire(); g.acquire(); g.acquire(); match g.release(epoch) {
Release::Pending(new) => assert_eq!(new, 3),
Release::Idle => panic!("expected Pending"),
}
match g.release(3) {
Release::Idle => {}
Release::Pending(_) => panic!("expected Idle"),
}
assert_eq!(g.packed.load(Ordering::Relaxed), 3 << 1); }
#[test]
fn force_idle_clears_running_preserves_epoch() {
let g = GateState::new();
g.acquire(); g.acquire(); g.force_idle();
let s = g.packed.load(Ordering::Relaxed);
assert_eq!(s & RUNNING, 0, "should be idle");
assert_eq!(s >> 1, 1, "epoch should be preserved");
}
#[test]
fn acquire_after_force_idle_gets_preserved_epoch() {
let g = GateState::new();
g.acquire(); g.acquire(); g.force_idle();
match g.acquire() {
Acquire::Runner { epoch } => assert_eq!(epoch, 1),
Acquire::Recorded => panic!("expected Runner"),
}
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::GenerateWorkGate;
use loom::sync::atomic::{AtomicUsize, Ordering};
use loom::sync::Arc;
use loom::thread;
const TARGET: usize = 1;
const UNBOUNDED: usize = usize::MAX;
struct GateHarness {
gate: GenerateWorkGate,
ready: AtomicUsize,
processed: AtomicUsize,
dispatched: AtomicUsize,
max_seen: AtomicUsize,
target: usize,
k: usize,
}
impl GateHarness {
fn new() -> Self {
Self::with(TARGET, UNBOUNDED)
}
fn with(target: usize, k: usize) -> Self {
Self {
gate: GenerateWorkGate::new(),
ready: AtomicUsize::new(0),
processed: AtomicUsize::new(0),
dispatched: AtomicUsize::new(0),
max_seen: AtomicUsize::new(0),
target,
k,
}
}
fn insert_and_drive(&self) {
self.ready.fetch_add(1, Ordering::SeqCst);
let Some(mut permit) = self.gate.try_acquire() else {
return;
};
loop {
let n = self.ready.swap(0, Ordering::SeqCst);
self.processed.fetch_add(n, Ordering::SeqCst);
if permit.try_release() {
break;
}
}
}
fn has_capacity(&self) -> bool {
self.dispatched.load(Ordering::Relaxed) < self.target
}
fn recheck_capacity(&self) -> bool {
self.dispatched.fetch_add(0, Ordering::SeqCst) < self.target
}
fn run_pass(&self) {
while self.has_capacity() && self.ready.load(Ordering::SeqCst) > 0 {
self.ready.fetch_sub(1, Ordering::SeqCst);
let n = self.dispatched.fetch_add(1, Ordering::Relaxed) + 1;
self.processed.fetch_add(1, Ordering::SeqCst);
self.max_seen.fetch_max(n, Ordering::Relaxed);
}
}
fn generate_work(&self) {
let Some(mut permit) = self.gate.try_acquire() else {
return;
};
let mut passes = 0usize;
'generate: loop {
self.run_pass();
passes += 1;
loop {
if permit.try_release() {
return;
}
if self.recheck_capacity() {
if passes < self.k || self.dispatched.fetch_add(0, Ordering::SeqCst) == 0 {
continue 'generate;
}
}
}
}
}
fn complete_one(&self) {
self.dispatched.fetch_sub(1, Ordering::Relaxed);
self.generate_work();
}
}
#[test]
fn generate_work_gate_no_lost_wake() {
loom::model(|| {
let h = Arc::new(GateHarness::new());
let h1 = h.clone();
let t1 = thread::spawn(move || h1.insert_and_drive());
let h2 = h.clone();
let t2 = thread::spawn(move || h2.insert_and_drive());
t1.join().unwrap();
t2.join().unwrap();
assert_eq!(
h.ready.load(Ordering::SeqCst),
0,
"work stranded: a generate_work wake was lost"
);
assert_eq!(
h.processed.load(Ordering::SeqCst),
2,
"both published items must be generated"
);
});
}
#[test]
fn generate_work_gate_no_lost_wake_three_callers() {
loom::model(|| {
let h = Arc::new(GateHarness::new());
let handles: Vec<_> = (0..3)
.map(|_| {
let h = h.clone();
thread::spawn(move || h.insert_and_drive())
})
.collect();
for t in handles {
t.join().unwrap();
}
assert_eq!(
h.ready.load(Ordering::SeqCst),
0,
"work stranded: a generate_work wake was lost"
);
assert_eq!(
h.processed.load(Ordering::SeqCst),
3,
"all three published items must be generated"
);
});
}
#[test]
fn generate_work_gate_no_lost_wake_at_capacity() {
loom::model(|| {
let h = Arc::new(GateHarness::new());
h.dispatched.store(1, Ordering::Relaxed);
h.max_seen.store(1, Ordering::Relaxed);
h.ready.store(1, Ordering::SeqCst);
let hr = h.clone();
let runner = thread::spawn(move || hr.generate_work());
let hc = h.clone();
let completion = thread::spawn(move || hc.complete_one());
runner.join().unwrap();
completion.join().unwrap();
assert_eq!(
h.ready.load(Ordering::SeqCst),
0,
"work stranded at capacity: a completion-edge wake was lost"
);
assert_eq!(
h.processed.load(Ordering::SeqCst),
1,
"the queued item must be dispatched once the slot frees"
);
assert_eq!(
h.max_seen.load(Ordering::Relaxed),
TARGET,
"dispatched exceeded the concurrency target"
);
});
}
#[test]
fn generate_work_gate_no_lost_wake_at_capacity_with_producer() {
loom::model(|| {
let h = Arc::new(GateHarness::new());
h.dispatched.store(1, Ordering::Relaxed);
h.max_seen.store(1, Ordering::Relaxed);
h.ready.store(1, Ordering::SeqCst);
let hr = h.clone();
let runner = thread::spawn(move || hr.generate_work());
let hc = h.clone();
let completion = thread::spawn(move || hc.complete_one());
let hp = h.clone();
let producer = thread::spawn(move || {
hp.ready.fetch_add(1, Ordering::SeqCst);
hp.generate_work();
});
runner.join().unwrap();
completion.join().unwrap();
producer.join().unwrap();
let ready = h.ready.load(Ordering::SeqCst);
let dispatched = h.dispatched.load(Ordering::Relaxed);
let processed = h.processed.load(Ordering::SeqCst);
let max_seen = h.max_seen.load(Ordering::Relaxed);
let wedge = ready > 0 && dispatched < TARGET;
assert!(
!wedge,
"WEDGE: ready={ready} dispatched={dispatched} processed={processed} max_seen={max_seen}"
);
assert!(
max_seen <= TARGET,
"dispatched exceeded target: max_seen={max_seen} processed={processed}"
);
});
}
#[test]
fn generate_work_gate_bounded_handoff_corner() {
loom::model(|| {
let h = Arc::new(GateHarness::with(3, 1));
h.dispatched.store(1, Ordering::Relaxed);
h.max_seen.store(1, Ordering::Relaxed);
let hr = h.clone();
let runner = thread::spawn(move || hr.generate_work());
let hc = h.clone();
let completion = thread::spawn(move || hc.complete_one());
let hp = h.clone();
let producer = thread::spawn(move || {
hp.ready.fetch_add(1, Ordering::SeqCst);
hp.generate_work();
});
runner.join().unwrap();
completion.join().unwrap();
producer.join().unwrap();
let ready = h.ready.load(Ordering::SeqCst);
let dispatched = h.dispatched.load(Ordering::Relaxed);
let processed = h.processed.load(Ordering::SeqCst);
let max_seen = h.max_seen.load(Ordering::Relaxed);
let wedge = ready > 0 && dispatched == 0;
assert!(
!wedge,
"WEDGE (epoch corner): ready={ready} dispatched={dispatched} processed={processed} max_seen={max_seen}"
);
assert!(
max_seen <= 3,
"dispatched exceeded target: max_seen={max_seen}"
);
});
}
#[test]
fn generate_work_gate_bounded_handoff() {
loom::model(|| {
let h = Arc::new(GateHarness::with(3, 1));
h.dispatched.store(1, Ordering::Relaxed);
h.max_seen.store(1, Ordering::Relaxed);
h.ready.store(1, Ordering::SeqCst);
let hr = h.clone();
let runner = thread::spawn(move || hr.generate_work());
let hc = h.clone();
let completion = thread::spawn(move || hc.complete_one());
let hp = h.clone();
let producer = thread::spawn(move || {
hp.ready.fetch_add(1, Ordering::SeqCst);
hp.generate_work();
});
runner.join().unwrap();
completion.join().unwrap();
producer.join().unwrap();
let ready = h.ready.load(Ordering::SeqCst);
let dispatched = h.dispatched.load(Ordering::Relaxed);
let processed = h.processed.load(Ordering::SeqCst);
let max_seen = h.max_seen.load(Ordering::Relaxed);
let wedge = ready > 0 && dispatched == 0;
assert!(
!wedge,
"WEDGE (epoch handoff): ready={ready} dispatched={dispatched} processed={processed} max_seen={max_seen}"
);
assert!(
max_seen <= 3,
"dispatched exceeded target: max_seen={max_seen}"
);
});
}
#[test]
fn generate_work_gate_corner_unbounded() {
loom::model(|| {
let h = Arc::new(GateHarness::with(3, UNBOUNDED));
h.dispatched.store(1, Ordering::Relaxed);
h.max_seen.store(1, Ordering::Relaxed);
let hr = h.clone();
let runner = thread::spawn(move || hr.generate_work());
let hc = h.clone();
let completion = thread::spawn(move || hc.complete_one());
let hp = h.clone();
let producer = thread::spawn(move || {
hp.ready.fetch_add(1, Ordering::SeqCst);
hp.generate_work();
});
runner.join().unwrap();
completion.join().unwrap();
producer.join().unwrap();
let ready = h.ready.load(Ordering::SeqCst);
let dispatched = h.dispatched.load(Ordering::Relaxed);
let processed = h.processed.load(Ordering::SeqCst);
let max_seen = h.max_seen.load(Ordering::Relaxed);
let wedge = ready > 0 && dispatched == 0;
assert!(
!wedge,
"WEDGE (epoch corner unbounded): ready={ready} dispatched={dispatched} processed={processed} max_seen={max_seen}"
);
assert!(
max_seen <= 3,
"dispatched exceeded target: max_seen={max_seen}"
);
});
}
#[test]
fn generate_work_gate_no_lost_wake_drive_path() {
loom::model(|| {
let h = Arc::new(GateHarness::with(usize::MAX, UNBOUNDED));
let h1 = h.clone();
let t1 = thread::spawn(move || {
h1.ready.fetch_add(1, Ordering::SeqCst);
h1.generate_work();
});
let h2 = h.clone();
let t2 = thread::spawn(move || {
h2.ready.fetch_add(1, Ordering::SeqCst);
h2.generate_work();
});
t1.join().unwrap();
t2.join().unwrap();
assert_eq!(
h.ready.load(Ordering::SeqCst),
0,
"work stranded: a generate_work wake was lost"
);
assert_eq!(
h.processed.load(Ordering::SeqCst),
2,
"both published items must be generated"
);
});
}
}