#![allow(dead_code)]
use std::collections::BTreeMap;
use std::sync::atomic::{AtomicBool, AtomicU64, AtomicU8, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use arc_swap::ArcSwap;
const SEGMENT_LEN: u64 = 64;
const SLOT_EMPTY: u8 = 0;
const SLOT_RESERVED: u8 = 1;
const SLOT_WRITING: u8 = 2;
const SLOT_PUBLISHED: u8 = 3;
const SLOT_POISONED: u8 = 4;
const SLOT_TAKEN: u8 = 5;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum ConsumerHeadState {
Empty,
Reserved,
Published,
Poisoned,
Closed,
Failed,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct DrainSummary {
items: u64,
poisoned: u64,
}
impl DrainSummary {
pub(crate) fn items(self) -> u64 {
self.items
}
pub(crate) fn poisoned(self) -> u64 {
self.poisoned
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum DrainError {
ProducersActive {
count: usize,
},
HeadReserved {
sequence: u64,
},
Failed {
sequence: u64,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct ProducerBoundary {
exclusive: u64,
}
impl ProducerBoundary {
pub(crate) fn exclusive(self) -> u64 {
self.exclusive
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct ConsumerBoundary {
next: u64,
}
impl ConsumerBoundary {
pub(crate) fn next(self) -> u64 {
self.next
}
pub(crate) fn reached(self, boundary: ProducerBoundary) -> bool {
self.next >= boundary.exclusive
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum ReserveError {
Closed,
SequenceExhausted,
Failed,
}
pub(crate) struct PublishError<T> {
value: T,
}
impl<T> PublishError<T> {
pub(crate) fn into_inner(self) -> T {
self.value
}
}
pub(crate) enum ConsumerPoll<T> {
Empty,
Reserved {
sequence: u64,
},
Item {
sequence: u64,
value: T,
},
Poisoned {
sequence: u64,
},
Closed,
Failed,
}
struct Slot<T> {
state: AtomicU8,
value: Mutex<Option<T>>,
}
impl<T> Slot<T> {
fn new() -> Self {
Self {
state: AtomicU8::new(SLOT_EMPTY),
value: Mutex::new(None),
}
}
}
struct Segment<T> {
base: u64,
slots: Box<[Slot<T>]>,
}
impl<T> Segment<T> {
fn new(base: u64) -> Self {
debug_assert_eq!(base % SEGMENT_LEN, 0);
let slots = (0..SEGMENT_LEN)
.map(|_| Slot::new())
.collect::<Vec<_>>()
.into_boxed_slice();
Self {
base,
slots,
}
}
fn slot(&self, sequence: u64) -> &Slot<T> {
debug_assert!(sequence >= self.base && sequence < self.base + SEGMENT_LEN);
&self.slots[(sequence - self.base) as usize]
}
}
struct QueueCore<T> {
next_sequence: AtomicU64,
accepting: AtomicBool,
producer_inflight: AtomicUsize,
reservations: AtomicUsize,
senders: AtomicUsize,
failed: AtomicBool,
tail: ArcSwap<Segment<T>>,
segments: Mutex<BTreeMap<u64, Arc<Segment<T>>>>,
}
impl<T> QueueCore<T> {
fn new() -> Self {
let first = Arc::new(Segment::new(0));
let mut segments = BTreeMap::new();
segments.insert(0, first.clone());
Self {
next_sequence: AtomicU64::new(0),
accepting: AtomicBool::new(true),
producer_inflight: AtomicUsize::new(0),
reservations: AtomicUsize::new(0),
senders: AtomicUsize::new(1),
failed: AtomicBool::new(false),
tail: ArcSwap::from(first),
segments: Mutex::new(segments),
}
}
fn allocate_sequence(&self) -> Result<u64, ReserveError> {
loop {
if self.failed.load(Ordering::Acquire) {
return Err(ReserveError::Failed);
}
if !self.accepting.load(Ordering::SeqCst) {
return Err(ReserveError::Closed);
}
let current = self.next_sequence.load(Ordering::Acquire);
if current == u64::MAX {
self.failed.store(true, Ordering::Release);
self.accepting.store(false, Ordering::SeqCst);
return Err(ReserveError::SequenceExhausted);
}
if self
.next_sequence
.compare_exchange_weak(current, current + 1, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
return Ok(current);
}
}
}
fn enter_producer(&self) -> Result<ProducerSection<'_, T>, ReserveError> {
if !self.accepting.load(Ordering::SeqCst) {
return Err(ReserveError::Closed);
}
self.producer_inflight.fetch_add(1, Ordering::SeqCst);
if !self.accepting.load(Ordering::SeqCst) {
self.producer_inflight.fetch_sub(1, Ordering::SeqCst);
return Err(ReserveError::Closed);
}
Ok(ProducerSection {
core: self,
})
}
fn register_reservation(&self) -> Result<(), ReserveError> {
if self
.reservations
.fetch_update(Ordering::AcqRel, Ordering::Acquire, |value| {
value.checked_add(1)
})
.is_err()
{
self.fail();
return Err(ReserveError::Failed);
}
Ok(())
}
fn finish_reservation(&self) -> bool {
if self
.reservations
.fetch_update(Ordering::AcqRel, Ordering::Acquire, |value| {
value.checked_sub(1)
})
.is_ok()
{
true
} else {
self.fail();
false
}
}
fn segment_for_producer(&self, sequence: u64) -> Arc<Segment<T>> {
let base = sequence / SEGMENT_LEN * SEGMENT_LEN;
let tail = self.tail.load_full();
if tail.base == base {
return tail;
}
let mut segments = self.segments.lock().unwrap_or_else(|e| e.into_inner());
if let Some(segment) = segments.get(&base) {
return segment.clone();
}
let segment = Arc::new(Segment::new(base));
segments.insert(base, segment.clone());
let current_tail = self.tail.load_full();
if base > current_tail.base {
self.tail.store(segment.clone());
}
segment
}
fn segment_for_consumer(&self, sequence: u64) -> Option<Arc<Segment<T>>> {
let base = sequence / SEGMENT_LEN * SEGMENT_LEN;
let tail = self.tail.load_full();
if tail.base == base {
return Some(tail);
}
self.segments
.lock()
.unwrap_or_else(|e| e.into_inner())
.get(&base)
.cloned()
}
fn reclaim_before(&self, consumer_sequence: u64) {
if consumer_sequence == 0 || !consumer_sequence.is_multiple_of(SEGMENT_LEN) {
return;
}
let tail_base = self.tail.load().base;
let mut segments = self.segments.lock().unwrap_or_else(|e| e.into_inner());
segments.retain(|base, _| *base >= consumer_sequence || *base == tail_base);
}
fn fail(&self) {
self.failed.store(true, Ordering::Release);
self.accepting.store(false, Ordering::SeqCst);
}
}
struct ProducerSection<'a, T> {
core: &'a QueueCore<T>,
}
impl<T> Drop for ProducerSection<'_, T> {
fn drop(&mut self) {
self.core.producer_inflight.fetch_sub(1, Ordering::SeqCst);
}
}
pub(crate) struct SequencedSender<T> {
core: Arc<QueueCore<T>>,
}
impl<T> Clone for SequencedSender<T> {
fn clone(&self) -> Self {
self.core.senders.fetch_add(1, Ordering::AcqRel);
Self {
core: self.core.clone(),
}
}
}
impl<T> Drop for SequencedSender<T> {
fn drop(&mut self) {
if self.core.senders.fetch_sub(1, Ordering::AcqRel) == 1 {
self.core.accepting.store(false, Ordering::SeqCst);
}
}
}
impl<T> SequencedSender<T> {
pub(crate) fn reserve(&self) -> Result<Reservation<T>, ReserveError> {
let producer = self.core.enter_producer()?;
let sequence = self.core.allocate_sequence()?;
let segment = self.core.segment_for_producer(sequence);
let slot = segment.slot(sequence);
if slot
.state
.compare_exchange(
SLOT_EMPTY,
SLOT_RESERVED,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
self.core.fail();
return Err(ReserveError::Failed);
}
if let Err(error) = self.core.register_reservation() {
slot.state.store(SLOT_POISONED, Ordering::Release);
return Err(error);
}
drop(producer);
Ok(Reservation {
core: self.core.clone(),
segment,
sequence,
active: true,
})
}
pub(crate) fn offer(&self, value: T) -> Result<u64, OfferError<T>> {
let reservation = match self.reserve() {
Ok(reservation) => reservation,
Err(reason) => {
return Err(OfferError {
reason,
value,
})
}
};
reservation.publish(value).map_err(|failure| OfferError {
reason: ReserveError::Failed,
value: failure.into_inner(),
})
}
pub(crate) fn boundary(&self) -> ProducerBoundary {
ProducerBoundary {
exclusive: self.core.next_sequence.load(Ordering::Acquire),
}
}
pub(crate) fn producer_inflight(&self) -> usize {
self.core.producer_inflight.load(Ordering::SeqCst)
}
pub(crate) fn outstanding_reservations(&self) -> usize {
self.core.reservations.load(Ordering::Acquire)
}
pub(crate) fn close(&self) {
self.core.accepting.store(false, Ordering::SeqCst);
}
pub(crate) fn is_closed(&self) -> bool {
!self.core.accepting.load(Ordering::SeqCst)
}
pub(crate) fn segment_count(&self) -> usize {
self.core
.segments
.lock()
.unwrap_or_else(|e| e.into_inner())
.len()
}
}
pub(crate) struct OfferError<T> {
reason: ReserveError,
value: T,
}
impl<T> OfferError<T> {
pub(crate) fn reason(&self) -> ReserveError {
self.reason
}
pub(crate) fn into_inner(self) -> T {
self.value
}
}
pub(crate) struct Reservation<T> {
core: Arc<QueueCore<T>>,
segment: Arc<Segment<T>>,
sequence: u64,
active: bool,
}
impl<T> Reservation<T> {
pub(crate) fn sequence(&self) -> u64 {
self.sequence
}
pub(crate) fn publish(mut self, value: T) -> Result<u64, PublishError<T>> {
let slot = self.segment.slot(self.sequence);
if slot
.state
.compare_exchange(
SLOT_RESERVED,
SLOT_WRITING,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
self.active = false;
self.core.finish_reservation();
self.core.fail();
return Err(PublishError {
value,
});
}
*slot.value.lock().unwrap_or_else(|e| e.into_inner()) = Some(value);
slot.state.store(SLOT_PUBLISHED, Ordering::Release);
self.active = false;
self.core.finish_reservation();
Ok(self.sequence)
}
}
impl<T> Drop for Reservation<T> {
fn drop(&mut self) {
if !self.active {
return;
}
let slot = self.segment.slot(self.sequence);
if slot
.state
.compare_exchange(
SLOT_RESERVED,
SLOT_POISONED,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
self.core.fail();
}
self.core.finish_reservation();
self.active = false;
}
}
pub(crate) struct SequencedReceiver<T> {
core: Arc<QueueCore<T>>,
next_sequence: u64,
}
impl<T> SequencedReceiver<T> {
pub(crate) fn try_recv(&mut self) -> ConsumerPoll<T> {
if self.core.failed.load(Ordering::Acquire) {
return ConsumerPoll::Failed;
}
let reserved = self.core.next_sequence.load(Ordering::Acquire);
if self.next_sequence >= reserved {
return if self.core.accepting.load(Ordering::SeqCst) {
ConsumerPoll::Empty
} else if self.core.producer_inflight.load(Ordering::SeqCst) > 0 {
ConsumerPoll::Reserved {
sequence: self.next_sequence,
}
} else {
ConsumerPoll::Closed
};
}
self.core.reclaim_before(self.next_sequence);
let Some(segment) = self.core.segment_for_consumer(self.next_sequence) else {
return ConsumerPoll::Reserved {
sequence: self.next_sequence,
};
};
let sequence = self.next_sequence;
let slot = segment.slot(sequence);
match slot.state.load(Ordering::Acquire) {
SLOT_EMPTY | SLOT_RESERVED | SLOT_WRITING => ConsumerPoll::Reserved {
sequence,
},
SLOT_PUBLISHED => {
let Some(value) = slot.value.lock().unwrap_or_else(|e| e.into_inner()).take()
else {
self.core.fail();
return ConsumerPoll::Failed;
};
slot.state.store(SLOT_TAKEN, Ordering::Release);
self.next_sequence += 1;
ConsumerPoll::Item {
sequence,
value,
}
}
SLOT_POISONED => {
slot.state.store(SLOT_TAKEN, Ordering::Release);
self.next_sequence += 1;
ConsumerPoll::Poisoned {
sequence,
}
}
_ => {
self.core.fail();
ConsumerPoll::Failed
}
}
}
pub(crate) fn boundary(&self) -> ConsumerBoundary {
ConsumerBoundary {
next: self.next_sequence,
}
}
pub(crate) fn head_state(&self) -> ConsumerHeadState {
if self.core.failed.load(Ordering::Acquire) {
return ConsumerHeadState::Failed;
}
let reserved = self.core.next_sequence.load(Ordering::Acquire);
if self.next_sequence >= reserved {
return if self.core.accepting.load(Ordering::SeqCst) {
ConsumerHeadState::Empty
} else if self.core.producer_inflight.load(Ordering::SeqCst) > 0 {
ConsumerHeadState::Reserved
} else {
ConsumerHeadState::Closed
};
}
let Some(segment) = self.core.segment_for_consumer(self.next_sequence) else {
return ConsumerHeadState::Reserved;
};
match segment
.slot(self.next_sequence)
.state
.load(Ordering::Acquire)
{
SLOT_EMPTY | SLOT_RESERVED | SLOT_WRITING => ConsumerHeadState::Reserved,
SLOT_PUBLISHED => ConsumerHeadState::Published,
SLOT_POISONED => ConsumerHeadState::Poisoned,
_ => ConsumerHeadState::Failed,
}
}
pub(crate) fn drain_after_producers_stop(
&mut self,
mut consumer: impl FnMut(T),
) -> Result<DrainSummary, DrainError> {
self.core.accepting.store(false, Ordering::SeqCst);
let producers = self.core.producer_inflight.load(Ordering::SeqCst);
if producers != 0 {
return Err(DrainError::ProducersActive {
count: producers,
});
}
let boundary = self.core.next_sequence.load(Ordering::Acquire);
let mut summary = DrainSummary {
items: 0,
poisoned: 0,
};
while self.next_sequence < boundary {
self.core.reclaim_before(self.next_sequence);
let sequence = self.next_sequence;
let Some(segment) = self.core.segment_for_consumer(sequence) else {
return Err(DrainError::HeadReserved {
sequence,
});
};
let slot = segment.slot(sequence);
match slot.state.load(Ordering::Acquire) {
SLOT_PUBLISHED => {
let Some(value) = slot.value.lock().unwrap_or_else(|e| e.into_inner()).take()
else {
self.core.fail();
return Err(DrainError::Failed {
sequence,
});
};
slot.state.store(SLOT_TAKEN, Ordering::Release);
self.next_sequence += 1;
summary.items += 1;
consumer(value);
}
SLOT_POISONED => {
slot.state.store(SLOT_TAKEN, Ordering::Release);
self.next_sequence += 1;
summary.poisoned += 1;
}
SLOT_EMPTY | SLOT_RESERVED | SLOT_WRITING => {
return Err(DrainError::HeadReserved {
sequence,
});
}
_ => {
self.core.fail();
return Err(DrainError::Failed {
sequence,
});
}
}
}
self.core.reclaim_before(self.next_sequence);
Ok(summary)
}
pub(crate) fn close(&self) {
self.core.accepting.store(false, Ordering::SeqCst);
}
pub(crate) fn segment_count(&self) -> usize {
self.core
.segments
.lock()
.unwrap_or_else(|e| e.into_inner())
.len()
}
}
impl<T> Drop for SequencedReceiver<T> {
fn drop(&mut self) {
self.core.accepting.store(false, Ordering::SeqCst);
}
}
pub(crate) fn channel<T>() -> (SequencedSender<T>, SequencedReceiver<T>) {
let core = Arc::new(QueueCore::new());
(
SequencedSender {
core: core.clone(),
},
SequencedReceiver {
core,
next_sequence: 0,
},
)
}