use std::mem::MaybeUninit;
use crossbeam_utils::CachePadded;
use super::cell::UnsafeCell;
use super::sync::atomic::{AtomicUsize, Ordering};
use super::sync::{Condvar, Mutex};
pub(crate) struct SubmissionQueue<T> {
slots: Box<[UnsafeCell<MaybeUninit<T>>]>,
tail: CachePadded<AtomicUsize>,
state: Mutex<State>,
not_flushing: Condvar,
capacity: usize,
}
struct State {
pending: usize,
flushing: bool,
}
#[cfg(not(all(test, s3_tm_loom)))]
std::thread_local! {
static SUBMISSION_DEPTH: core::cell::Cell<u32> = const { core::cell::Cell::new(0) };
}
#[cfg(all(test, s3_tm_loom))]
loom::thread_local! {
static SUBMISSION_DEPTH: core::cell::Cell<u32> = core::cell::Cell::new(0);
}
fn incr_depth() -> u32 {
SUBMISSION_DEPTH.with(|c| {
let depth = c.get();
c.set(depth + 1);
depth
})
}
fn decr_depth() {
SUBMISSION_DEPTH.with(|c| c.set(c.get() - 1));
}
unsafe impl<T: Send> Send for SubmissionQueue<T> {}
unsafe impl<T: Send> Sync for SubmissionQueue<T> {}
pub(crate) struct Submission<'a, T> {
sq: &'a SubmissionQueue<T>,
nested: bool,
}
pub(crate) struct SubmissionGuard<'a, T> {
sq: &'a SubmissionQueue<T>,
count: usize,
next: usize,
}
impl<T> SubmissionQueue<T> {
pub(crate) fn new(capacity: usize) -> Self {
assert!(capacity > 0, "capacity must be non-zero");
let slots: Box<[UnsafeCell<MaybeUninit<T>>]> = (0..capacity)
.map(|_| UnsafeCell::new(MaybeUninit::uninit()))
.collect();
Self {
slots,
tail: CachePadded::new(AtomicUsize::new(0)),
state: Mutex::new(State {
pending: 0,
flushing: false,
}),
not_flushing: Condvar::new(),
capacity,
}
}
pub(crate) fn enter(&self) -> Submission<'_, T> {
let depth = incr_depth();
if depth > 0 {
return Submission {
sq: self,
nested: true,
};
}
let mut state = self.state.lock();
let mut parked = false;
while state.flushing {
if !parked {
tracing::trace!(
target: crate::telemetry::TARGET_SCHEDULING,
phase = "enter_blocked",
pending = state.pending,
"enter blocked on flush in progress"
);
parked = true;
}
state = self.not_flushing.wait(state);
}
if parked {
tracing::trace!(
target: crate::telemetry::TARGET_SCHEDULING,
phase = "enter_unblocked",
pending = state.pending,
"enter unblocked"
);
}
state.pending += 1;
Submission {
sq: self,
nested: false,
}
}
#[allow(dead_code)] pub(crate) fn capacity(&self) -> usize {
self.capacity
}
}
impl<'a, T> Submission<'a, T> {
#[inline]
pub(crate) fn push(&self, item: T) -> Result<(), T> {
let idx = self.sq.tail.fetch_add(1, Ordering::Relaxed);
if idx >= self.sq.capacity {
self.sq.tail.fetch_sub(1, Ordering::Relaxed);
return Err(item);
}
self.sq.slots[idx].with_mut(|ptr| unsafe { (*ptr).write(item) });
Ok(())
}
pub(crate) fn submit(self) -> Option<SubmissionGuard<'a, T>> {
decr_depth();
if self.nested {
std::mem::forget(self);
return None;
}
let sq = self.sq;
std::mem::forget(self);
let mut state = sq.state.lock();
state.pending -= 1;
if state.pending == 0 {
state.flushing = true;
drop(state);
let count = sq.tail.swap(0, Ordering::Relaxed).min(sq.capacity);
tracing::trace!(
target: crate::telemetry::TARGET_SCHEDULING,
phase = "flush_start",
count,
"submission flush starting",
);
Some(SubmissionGuard { sq, count, next: 0 })
} else {
None
}
}
}
impl<T> Drop for Submission<'_, T> {
fn drop(&mut self) {
decr_depth();
if self.nested {
return;
}
let mut state = self.sq.state.lock();
state.pending -= 1;
if state.pending == 0 && !state.flushing {
let count = self
.sq
.tail
.swap(0, Ordering::Relaxed)
.min(self.sq.capacity);
for i in 0..count {
self.sq.slots[i].with_mut(|ptr| unsafe { (*ptr).assume_init_drop() });
}
}
}
}
impl<T> SubmissionGuard<'_, T> {
#[allow(dead_code)] pub(crate) fn len(&self) -> usize {
self.count - self.next
}
#[allow(dead_code)] pub(crate) fn is_empty(&self) -> bool {
self.next >= self.count
}
#[allow(dead_code)] pub(crate) fn as_slice(&self) -> &[T] {
unsafe {
let base = self.sq.slots.as_ptr().add(self.next) as *const T;
std::slice::from_raw_parts(base, self.count - self.next)
}
}
#[allow(dead_code)] pub(crate) fn as_mut_slice(&mut self) -> &mut [T] {
unsafe {
let base = self.sq.slots.as_ptr().add(self.next) as *mut T;
std::slice::from_raw_parts_mut(base, self.count - self.next)
}
}
pub(crate) fn drain(&mut self) -> impl Iterator<Item = T> + '_ {
(self.next..self.count).map(|i| {
self.next = i + 1;
self.sq.slots[i].with_mut(|ptr| unsafe { (*ptr).assume_init_read() })
})
}
}
impl<T> Drop for SubmissionGuard<'_, T> {
fn drop(&mut self) {
for i in self.next..self.count {
self.sq.slots[i].with_mut(|ptr| unsafe { (*ptr).assume_init_drop() });
}
let mut state = self.sq.state.lock();
state.flushing = false;
self.sq.not_flushing.notify_all();
tracing::trace!(
target: crate::telemetry::TARGET_SCHEDULING,
phase = "flush_end",
"submission flush complete",
);
}
}
impl<T> Drop for SubmissionQueue<T> {
fn drop(&mut self) {
let count = self.tail.load(Ordering::Relaxed).min(self.capacity);
for i in 0..count {
self.slots[i].with_mut(|ptr| unsafe { (*ptr).assume_init_drop() });
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::Arc;
#[derive(Debug, Clone)]
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::Relaxed);
}
}
fn drop_counter() -> (DropCounter, Arc<AtomicUsize>) {
let count = Arc::new(AtomicUsize::new(0));
(DropCounter(Arc::clone(&count)), count)
}
#[test]
fn single_producer() {
let q = SubmissionQueue::new(8);
let s = q.enter();
for i in [0, 10, 20] {
s.push(i).unwrap();
}
let mut guard = s.submit().expect("single producer is last out");
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![0, 10, 20]);
}
#[test]
fn submit_resets_for_next_round() {
let q = SubmissionQueue::new(8);
let s = q.enter();
s.push(10).unwrap();
s.push(20).unwrap();
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![10, 20]);
drop(guard);
let s = q.enter();
s.push(30).unwrap();
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![30]);
}
#[test]
fn push_returns_err_when_full() {
let q = SubmissionQueue::<i32>::new(2);
let s = q.enter();
s.push(1).unwrap();
s.push(2).unwrap();
assert_eq!(s.push(3), Err(3));
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![1, 2]);
}
#[test]
fn empty_round() {
let q = SubmissionQueue::<i32>::new(8);
let s = q.enter();
let mut guard = s.submit().unwrap();
assert!(guard.is_empty());
assert_eq!(guard.len(), 0);
assert_eq!(guard.drain().count(), 0);
}
#[test]
fn multi_producer_all_items_flushed() {
let q = Arc::new(SubmissionQueue::new(64));
let flushed = Arc::new(AtomicUsize::new(0));
let threads: Vec<_> = (0..8)
.map(|i| {
let q = Arc::clone(&q);
let flushed = Arc::clone(&flushed);
std::thread::spawn(move || {
let s = q.enter();
s.push(i).unwrap();
if let Some(mut guard) = s.submit() {
flushed.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
})
})
.collect();
for t in threads {
t.join().unwrap();
}
assert_eq!(flushed.load(Ordering::Relaxed), 8);
}
#[test]
fn stress_multi_round() {
const ROUNDS: usize = 1000;
const PRODUCERS: usize = 8;
let total = Arc::new(AtomicUsize::new(0));
for _ in 0..ROUNDS {
let q = Arc::new(SubmissionQueue::new(PRODUCERS * 2));
let total = Arc::clone(&total);
let threads: Vec<_> = (0..PRODUCERS)
.map(|i| {
let q = Arc::clone(&q);
let total = Arc::clone(&total);
std::thread::spawn(move || {
let s = q.enter();
s.push(i).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
})
})
.collect();
for t in threads {
t.join().unwrap();
}
}
assert_eq!(total.load(Ordering::Relaxed), ROUNDS * PRODUCERS);
}
#[test]
fn enter_parks_during_flush() {
let q = Arc::new(SubmissionQueue::new(8));
let flushing = Arc::new(AtomicBool::new(false));
let q2 = Arc::clone(&q);
let flushing2 = Arc::clone(&flushing);
let flusher = std::thread::spawn(move || {
let s = q2.enter();
s.push(1).unwrap();
let guard = s.submit().unwrap();
flushing2.store(true, Ordering::Release);
std::thread::sleep(std::time::Duration::from_millis(50));
drop(guard);
});
while !flushing.load(Ordering::Acquire) {
std::thread::yield_now();
}
let start = std::time::Instant::now();
let s = q.enter();
let waited = start.elapsed();
assert!(waited.as_millis() >= 10, "enter should have blocked");
s.submit();
flusher.join().unwrap();
}
#[test]
fn drop_unflushed_items() {
let (dc, drops) = drop_counter();
{
let q = SubmissionQueue::new(8);
let s = q.enter();
s.push(dc.clone()).unwrap();
s.push(dc.clone()).unwrap();
s.push(dc).unwrap();
let _guard = s.submit().unwrap();
}
assert_eq!(drops.load(Ordering::Relaxed), 3);
}
#[test]
fn drain_then_drop_no_double_free() {
let (dc, drops) = drop_counter();
{
let q = SubmissionQueue::new(8);
let s = q.enter();
s.push(dc.clone()).unwrap();
s.push(dc).unwrap();
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
drop(items);
assert_eq!(drops.load(Ordering::Relaxed), 2);
drop(guard);
}
assert_eq!(drops.load(Ordering::Relaxed), 2);
}
#[test]
fn submission_drop_without_submit() {
let (dc, drops) = drop_counter();
let q = SubmissionQueue::new(8);
{
let s = q.enter();
s.push(dc.clone()).unwrap();
}
assert_eq!(drops.load(Ordering::Relaxed), 1);
let s = q.enter();
s.push(dc).unwrap();
let mut guard = s.submit().unwrap();
assert_eq!(guard.drain().count(), 1);
}
#[test]
fn batch_slice_access() {
let q = SubmissionQueue::new(8);
let s = q.enter();
s.push(10).unwrap();
s.push(20).unwrap();
s.push(30).unwrap();
let mut guard = s.submit().unwrap();
assert_eq!(guard.as_slice(), &[10, 20, 30]);
guard.as_mut_slice().reverse();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![30, 20, 10]);
}
#[test]
fn multiple_pushes_per_producer() {
let q = SubmissionQueue::new(8);
let s = q.enter();
for i in 0..5 {
s.push(i).unwrap();
}
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![0, 1, 2, 3, 4]);
}
#[test]
fn concurrent_push_and_flush_interleaving() {
let q = Arc::new(SubmissionQueue::new(64));
let total = Arc::new(AtomicUsize::new(0));
let flushing = Arc::new(AtomicBool::new(false));
let q_a = Arc::clone(&q);
let total_a = Arc::clone(&total);
let flushing_a = Arc::clone(&flushing);
let a = std::thread::spawn(move || {
let s = q_a.enter();
s.push(1).unwrap();
let mut guard = s.submit().unwrap();
flushing_a.store(true, Ordering::Release);
std::thread::sleep(std::time::Duration::from_millis(50));
total_a.fetch_add(guard.drain().count(), Ordering::Relaxed);
drop(guard);
});
while !flushing.load(Ordering::Acquire) {
std::thread::yield_now();
}
let mut handles = vec![];
for _ in 0..2 {
let q = Arc::clone(&q);
let total = Arc::clone(&total);
handles.push(std::thread::spawn(move || {
let s = q.enter();
s.push(1).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
}));
}
a.join().unwrap();
for h in handles {
h.join().unwrap();
}
assert_eq!(total.load(Ordering::Relaxed), 3);
}
#[test]
fn reentrant_enter_does_not_deadlock() {
let q: SubmissionQueue<i32> = SubmissionQueue::new(8);
let outer = q.enter();
outer.push(1).unwrap();
let inner = q.enter();
inner.push(2).unwrap();
assert!(
inner.submit().is_none(),
"nested submit never returns a guard"
);
let mut guard = outer.submit().expect("primary should flush");
let items: Vec<_> = guard.drain().collect();
assert_eq!(items.len(), 2);
assert!(items.contains(&1));
assert!(items.contains(&2));
}
#[test]
fn reentrant_enter_does_not_bump_pending() {
let q: SubmissionQueue<i32> = SubmissionQueue::new(4);
let outer = q.enter();
assert_eq!(q.state.lock().pending, 1);
let inner = q.enter();
assert_eq!(
q.state.lock().pending,
1,
"nested enter must not bump pending"
);
inner.submit();
assert_eq!(
q.state.lock().pending,
1,
"nested submit must not touch pending"
);
outer.submit();
assert_eq!(q.state.lock().pending, 0);
}
#[test]
fn nested_submission_drop_is_safe() {
let q: SubmissionQueue<i32> = SubmissionQueue::new(4);
let outer = q.enter();
outer.push(10).unwrap();
{
let inner = q.enter();
inner.push(20).unwrap();
}
assert_eq!(
q.state.lock().pending,
1,
"nested drop must not change pending"
);
let mut guard = outer.submit().expect("outer should flush");
let items: Vec<_> = guard.drain().collect();
assert_eq!(items.len(), 2, "both items should reach the flush");
}
#[test]
fn cross_thread_entries_still_independent() {
let q = Arc::new(SubmissionQueue::<i32>::new(8));
let q2 = Arc::clone(&q);
let outer = q.enter();
assert_eq!(q.state.lock().pending, 1);
let handle = std::thread::spawn(move || {
let s = q2.enter();
assert_eq!(
q2.state.lock().pending,
2,
"different thread must bump pending"
);
s.push(1).unwrap();
s.submit();
});
handle.join().unwrap();
assert_eq!(q.state.lock().pending, 1);
outer.submit();
}
#[test]
fn reentrant_enter_during_push_overflow() {
let q: SubmissionQueue<i32> = SubmissionQueue::new(2);
let outer = q.enter();
outer.push(1).unwrap();
outer.push(2).unwrap();
let inner = q.enter();
assert!(
inner.push(3).is_err(),
"queue is full, nested push should fail just like outer"
);
inner.submit();
let mut guard = outer.submit().expect("outer flushes");
let items: Vec<_> = guard.drain().collect();
assert_eq!(items.len(), 2);
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::super::sync::atomic::AtomicUsize as LoomAtomicUsize;
use super::super::sync::Arc;
use super::super::thread;
use super::*;
#[test]
fn two_producers_both_flushed() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(4));
let total = Arc::new(LoomAtomicUsize::new(0));
let q2 = Arc::clone(&q);
let t2 = Arc::clone(&total);
let h = thread::spawn(move || {
let s = q2.enter();
s.push(1).unwrap();
if let Some(mut guard) = s.submit() {
t2.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
});
let s = q.enter();
s.push(2).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
h.join().unwrap();
assert_eq!(total.load(Ordering::Relaxed), 2);
});
}
#[test]
fn enter_blocks_during_flush() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(4));
let q2 = Arc::clone(&q);
let h = thread::spawn(move || {
let s = q2.enter();
s.push(10).unwrap();
if let Some(mut guard) = s.submit() {
let _: Vec<_> = guard.drain().collect();
}
});
let s = q.enter();
s.push(20).unwrap();
if let Some(mut guard) = s.submit() {
let _: Vec<_> = guard.drain().collect();
}
h.join().unwrap();
});
}
#[test]
fn capacity_exhaustion() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(1));
let q2 = Arc::clone(&q);
let h = thread::spawn(move || {
let s = q2.enter();
let _ = s.push(1);
if let Some(mut guard) = s.submit() {
let _: Vec<_> = guard.drain().collect();
}
});
let s = q.enter();
let _ = s.push(2);
if let Some(mut guard) = s.submit() {
let _: Vec<_> = guard.drain().collect();
}
h.join().unwrap();
});
}
#[test]
fn drop_without_submit() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(4));
let q2 = Arc::clone(&q);
let h = thread::spawn(move || {
let s = q2.enter();
s.push(1).unwrap();
});
h.join().unwrap();
let s = q.enter();
s.push(2).unwrap();
let mut guard = s.submit().unwrap();
let items: Vec<_> = guard.drain().collect();
assert_eq!(items, vec![2]);
});
}
#[test]
fn partial_drain_then_drop() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(4));
let total = Arc::new(LoomAtomicUsize::new(0));
let q2 = Arc::clone(&q);
let t2 = Arc::clone(&total);
let h = thread::spawn(move || {
let s = q2.enter();
s.push(10).unwrap();
s.push(20).unwrap();
if let Some(mut guard) = s.submit() {
if let Some(_val) = guard.drain().next() {
t2.fetch_add(1, Ordering::Relaxed);
}
}
});
let s = q.enter();
s.push(30).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
h.join().unwrap();
assert!(total.load(Ordering::Relaxed) >= 1);
});
}
#[test]
fn three_producers_multiple_pushes() {
loom::model(|| {
let q = Arc::new(SubmissionQueue::new(8));
let total = Arc::new(LoomAtomicUsize::new(0));
let mut handles = Vec::new();
for _ in 0..2 {
let q = Arc::clone(&q);
let total = Arc::clone(&total);
handles.push(thread::spawn(move || {
let s = q.enter();
s.push(1).unwrap();
s.push(2).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
}));
}
let s = q.enter();
s.push(3).unwrap();
s.push(4).unwrap();
if let Some(mut guard) = s.submit() {
total.fetch_add(guard.drain().count(), Ordering::Relaxed);
}
for h in handles {
h.join().unwrap();
}
assert_eq!(total.load(Ordering::Relaxed), 6);
});
}
}