use std::marker::PhantomData;
use std::mem;
use std::time::{Duration, Instant};
use nexus_slab::{Full, Slot, bounded, unbounded};
use crate::ConfigError;
use crate::entry::{EntryPtr, WheelEntry, entry_ref};
use crate::handle::TimerHandle;
use crate::level::WheelSlot;
use crate::store::{BoundedStore, SlabStore};
#[derive(Debug, Clone, Copy)]
pub struct TimeoutQueueBuilder {
timeout: Duration,
tick_duration: Duration,
}
impl TimeoutQueueBuilder {
pub fn new(timeout: Duration) -> Self {
TimeoutQueueBuilder {
timeout,
tick_duration: Duration::from_millis(1),
}
}
pub fn tick_duration(mut self, d: Duration) -> Self {
self.tick_duration = d;
self
}
pub fn unbounded(self, chunk_capacity: usize) -> UnboundedTimeoutQueueBuilder {
UnboundedTimeoutQueueBuilder {
config: self,
chunk_capacity,
}
}
pub fn bounded(self, capacity: usize) -> BoundedTimeoutQueueBuilder {
BoundedTimeoutQueueBuilder {
config: self,
capacity,
}
}
fn validate(&self) -> Result<(), ConfigError> {
if self.timeout.is_zero() {
return Err(ConfigError::Invalid("timeout must be non-zero"));
}
if self.tick_duration.is_zero() {
return Err(ConfigError::Invalid("tick_duration must be non-zero"));
}
if self.tick_duration.as_nanos() > u64::MAX as u128 {
return Err(ConfigError::Invalid(
"tick_duration must fit in u64 nanoseconds",
));
}
Ok(())
}
#[inline]
fn tick_ns(&self) -> u64 {
self.tick_duration.as_nanos().min(u64::MAX as u128) as u64
}
#[inline]
fn timeout_ticks(&self) -> u64 {
let tick_ns = self.tick_ns() as u128;
let timeout_ns = self.timeout.as_nanos();
let ticks = timeout_ns.div_ceil(tick_ns);
ticks.min(u64::MAX as u128).max(1) as u64
}
}
#[derive(Debug)]
pub struct UnboundedTimeoutQueueBuilder {
config: TimeoutQueueBuilder,
chunk_capacity: usize,
}
impl UnboundedTimeoutQueueBuilder {
pub fn build<T: 'static>(self, now: Instant) -> Result<TimeoutQueue<T>, ConfigError> {
self.config.validate()?;
let tick_ns = self.config.tick_ns();
let timeout_ticks = self.config.timeout_ticks();
let slab = unsafe { unbounded::Slab::with_chunk_capacity(self.chunk_capacity) };
Ok(TimeoutQueue {
list: WheelSlot::new(),
slab,
timeout_ticks,
tick_ns,
inv_tick_ns: (1u128 << 64) / tick_ns as u128,
epoch: now,
len: 0,
_marker: PhantomData,
})
}
}
#[derive(Debug)]
pub struct BoundedTimeoutQueueBuilder {
config: TimeoutQueueBuilder,
capacity: usize,
}
impl BoundedTimeoutQueueBuilder {
pub fn build<T: 'static>(self, now: Instant) -> Result<BoundedTimeoutQueue<T>, ConfigError> {
self.config.validate()?;
let tick_ns = self.config.tick_ns();
let timeout_ticks = self.config.timeout_ticks();
let slab = unsafe { bounded::Slab::with_capacity(self.capacity) };
Ok(TimeoutQueue {
list: WheelSlot::new(),
slab,
timeout_ticks,
tick_ns,
inv_tick_ns: (1u128 << 64) / tick_ns as u128,
epoch: now,
len: 0,
_marker: PhantomData,
})
}
}
pub struct TimeoutQueue<
T: 'static,
S: SlabStore<Item = WheelEntry<T>> = unbounded::Slab<WheelEntry<T>>,
> {
list: WheelSlot<T>,
slab: S,
timeout_ticks: u64,
tick_ns: u64,
inv_tick_ns: u128,
epoch: Instant,
len: usize,
_marker: PhantomData<*const ()>, }
#[allow(clippy::non_send_fields_in_send_ty)]
unsafe impl<T: Send + 'static, S: SlabStore<Item = WheelEntry<T>>> Send for TimeoutQueue<T, S> {}
pub type BoundedTimeoutQueue<T> = TimeoutQueue<T, bounded::Slab<WheelEntry<T>>>;
impl<T: 'static> TimeoutQueue<T> {
pub fn unbounded(timeout: Duration, chunk_capacity: usize, now: Instant) -> Self {
TimeoutQueueBuilder::new(timeout)
.unbounded(chunk_capacity)
.build(now)
.expect("TimeoutQueue requires a non-zero timeout")
}
}
impl<T: 'static> BoundedTimeoutQueue<T> {
pub fn bounded(timeout: Duration, capacity: usize, now: Instant) -> Self {
TimeoutQueueBuilder::new(timeout)
.bounded(capacity)
.build(now)
.expect("TimeoutQueue requires a non-zero timeout")
}
}
impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
pub fn schedule(&mut self, now: Instant, value: T) -> TimerHandle<T> {
let deadline_ticks = self.deadline_for(now);
let entry = WheelEntry::new(deadline_ticks, value, 2);
let ptr = self.slab.alloc(entry).into_raw();
self.insert_entry(ptr, deadline_ticks);
self.len += 1;
TimerHandle::new(ptr)
}
pub fn schedule_forget(&mut self, now: Instant, value: T) {
let deadline_ticks = self.deadline_for(now);
let entry = WheelEntry::new(deadline_ticks, value, 1);
let ptr = self.slab.alloc(entry).into_raw();
self.insert_entry(ptr, deadline_ticks);
self.len += 1;
}
}
impl<T: 'static, S: BoundedStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
pub fn try_schedule(&mut self, now: Instant, value: T) -> Result<TimerHandle<T>, Full<T>> {
let deadline_ticks = self.deadline_for(now);
let entry = WheelEntry::new(deadline_ticks, value, 2);
match self.slab.try_alloc(entry) {
Ok(slot) => {
let ptr = slot.into_raw();
self.insert_entry(ptr, deadline_ticks);
self.len += 1;
Ok(TimerHandle::new(ptr))
}
Err(full) => Err(Full(recover_value(full))),
}
}
pub fn try_schedule_forget(&mut self, now: Instant, value: T) -> Result<(), Full<T>> {
let deadline_ticks = self.deadline_for(now);
let entry = WheelEntry::new(deadline_ticks, value, 1);
match self.slab.try_alloc(entry) {
Ok(slot) => {
let ptr = slot.into_raw();
self.insert_entry(ptr, deadline_ticks);
self.len += 1;
Ok(())
}
Err(full) => Err(Full(recover_value(full))),
}
}
}
#[inline]
fn recover_value<T>(full: Full<WheelEntry<T>>) -> T {
let wheel_entry = full.into_inner();
unsafe { wheel_entry.take_value() }.expect("entry was just constructed with Some(value)")
}
impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
pub fn cancel(&mut self, handle: TimerHandle<T>) -> Option<T> {
let ptr = handle.ptr;
mem::forget(handle);
let entry = unsafe { entry_ref(ptr) };
let refs = entry.refs();
if refs == 2 {
let value = unsafe { entry.take_value() };
unsafe { self.list.remove_entry(ptr) };
self.len -= 1;
self.slab.free(unsafe { Slot::from_raw(ptr) });
value
} else {
debug_assert_eq!(refs, 1, "unexpected refcount {refs} in cancel");
self.slab.free(unsafe { Slot::from_raw(ptr) });
None
}
}
pub fn free(&mut self, handle: TimerHandle<T>) {
let ptr = handle.ptr;
mem::forget(handle);
let entry = unsafe { entry_ref(ptr) };
let new_refs = entry.dec_refs();
if new_refs == 0 {
self.slab.free(unsafe { Slot::from_raw(ptr) });
}
}
pub fn poll(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
self.poll_with_limit(now, usize::MAX, buf)
}
pub fn poll_with_limit(&mut self, now: Instant, limit: usize, buf: &mut Vec<T>) -> usize {
let now_ticks = self.instant_to_ticks(now);
let mut fired = 0;
while fired < limit {
let ptr = self.list.entry_head();
if ptr.is_null() {
break;
}
let entry = unsafe { entry_ref(ptr) };
#[cfg(test)]
{
poll_examined_inc();
}
if entry.deadline_ticks() > now_ticks {
break;
}
unsafe { self.list.remove_entry(ptr) };
if let Some(value) = self.fire_entry(ptr) {
buf.push(value);
}
fired += 1;
}
fired
}
pub fn next_deadline(&self) -> Option<Instant> {
let head = self.list.entry_head();
if head.is_null() {
return None;
}
let ticks = unsafe { entry_ref(head) }.deadline_ticks();
Some(self.ticks_to_instant(ticks))
}
#[inline]
pub fn len(&self) -> usize {
self.len
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[inline]
fn instant_to_ticks(&self, instant: Instant) -> u64 {
let dur = instant.saturating_duration_since(self.epoch);
let nanos = dur.as_nanos().min(u64::MAX as u128) as u64;
((nanos as u128 * self.inv_tick_ns) >> 64) as u64
}
#[inline]
fn ticks_to_instant(&self, ticks: u64) -> Instant {
self.epoch + Duration::from_nanos(ticks.saturating_mul(self.tick_ns))
}
#[inline]
fn deadline_for(&self, now: Instant) -> u64 {
self.instant_to_ticks(now)
.saturating_add(self.timeout_ticks)
}
#[inline]
fn insert_entry(&mut self, entry_ptr: EntryPtr<T>, deadline_ticks: u64) {
debug_assert!(
{
let tail = self.list.entry_tail();
tail.is_null() || deadline_ticks >= unsafe { entry_ref(tail) }.deadline_ticks()
},
"TimeoutQueue: deadline {deadline_ticks} inserted out of order \
(did `now` go backwards?)",
);
unsafe { self.list.push_entry(entry_ptr) };
}
#[inline]
fn fire_entry(&mut self, entry_ptr: EntryPtr<T>) -> Option<T> {
let entry = unsafe { entry_ref(entry_ptr) };
let value = unsafe { entry.take_value() };
let new_refs = entry.dec_refs();
if new_refs == 0 {
self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
}
self.len -= 1;
value
}
}
impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> Drop for TimeoutQueue<T, S> {
fn drop(&mut self) {
let mut entry_ptr = self.list.entry_head();
while !entry_ptr.is_null() {
let next_entry = unsafe { entry_ref(entry_ptr) }.next();
self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
entry_ptr = next_entry;
}
}
}
#[cfg(test)]
thread_local! {
static POLL_EXAMINED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
#[cfg(test)]
fn poll_examined_inc() {
POLL_EXAMINED.with(|c| c.set(c.get() + 1));
}
#[cfg(test)]
fn poll_examined_reset() {
POLL_EXAMINED.with(|c| c.set(0));
}
#[cfg(test)]
fn poll_examined_get() -> usize {
POLL_EXAMINED.with(std::cell::Cell::get)
}
#[cfg(test)]
mod tests {
use super::*;
use std::time::{Duration, Instant};
fn ms(millis: u64) -> Duration {
Duration::from_millis(millis)
}
fn list_50ms(now: Instant) -> TimeoutQueue<u64> {
TimeoutQueue::unbounded(ms(50), 1024, now)
}
fn assert_send<T: Send>() {}
#[test]
fn timeout_queue_is_send() {
assert_send::<TimeoutQueue<u64>>();
assert_send::<BoundedTimeoutQueue<u64>>();
}
#[test]
fn default_construction() {
let now = Instant::now();
let list = list_50ms(now);
assert!(list.is_empty());
assert_eq!(list.len(), 0);
assert!(list.next_deadline().is_none());
}
#[test]
fn bounded_construction() {
let now = Instant::now();
let list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 128, now);
assert!(list.is_empty());
}
#[track_caller]
fn assert_invalid<T>(result: &Result<T, ConfigError>, expect_substr: &str) {
match result {
Err(ConfigError::Invalid(msg)) => assert!(
msg.contains(expect_substr),
"message {msg:?} does not contain {expect_substr:?}"
),
Ok(_) => panic!("expected ConfigError::Invalid containing {expect_substr:?}, got Ok"),
}
}
#[test]
fn invalid_zero_timeout() {
let now = Instant::now();
let result = TimeoutQueueBuilder::new(Duration::ZERO)
.unbounded(64)
.build::<u64>(now);
assert_invalid(&result, "timeout must be non-zero");
}
#[test]
fn invalid_zero_tick() {
let now = Instant::now();
let result = TimeoutQueueBuilder::new(ms(50))
.tick_duration(Duration::ZERO)
.unbounded(64)
.build::<u64>(now);
assert_invalid(&result, "tick_duration must be non-zero");
}
#[test]
fn invalid_tick_too_large() {
let now = Instant::now();
let result = TimeoutQueueBuilder::new(ms(50))
.tick_duration(Duration::from_secs(20_000_000_000))
.unbounded(64)
.build::<u64>(now);
assert_invalid(&result, "tick_duration must fit in u64 nanoseconds");
}
#[test]
fn schedule_and_cancel() {
let now = Instant::now();
let mut list = list_50ms(now);
let h = list.schedule(now, 42);
assert_eq!(list.len(), 1);
let val = list.cancel(h);
assert_eq!(val, Some(42));
assert_eq!(list.len(), 0);
}
#[test]
fn schedule_forget_fires() {
let now = Instant::now();
let mut list = list_50ms(now);
list.schedule_forget(now, 99);
assert_eq!(list.len(), 1);
let mut buf = Vec::new();
let fired = list.poll(now + ms(60), &mut buf);
assert_eq!(fired, 1);
assert_eq!(buf, vec![99]);
assert_eq!(list.len(), 0);
}
#[test]
fn cancel_after_fire_returns_none() {
let now = Instant::now();
let mut list = list_50ms(now);
let h = list.schedule(now, 42);
let mut buf = Vec::new();
list.poll(now + ms(60), &mut buf);
assert_eq!(buf, vec![42]);
let val = list.cancel(h);
assert_eq!(val, None);
}
#[test]
fn free_active_timer_becomes_fire_and_forget() {
let now = Instant::now();
let mut list = list_50ms(now);
let h = list.schedule(now, 42);
list.free(h); assert_eq!(list.len(), 1);
let mut buf = Vec::new();
list.poll(now + ms(60), &mut buf);
assert_eq!(buf, vec![42]);
assert_eq!(list.len(), 0);
}
#[test]
fn free_zombie_handle() {
let now = Instant::now();
let mut list = list_50ms(now);
let h = list.schedule(now, 42);
let mut buf = Vec::new();
list.poll(now + ms(60), &mut buf);
list.free(h);
}
#[test]
fn bounded_full() {
let now = Instant::now();
let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 2, now);
let h1 = list.try_schedule(now, 1).unwrap();
let h2 = list.try_schedule(now, 2).unwrap();
let err = list.try_schedule(now, 3);
assert!(err.is_err());
let recovered = err.unwrap_err().into_inner();
assert_eq!(recovered, 3);
list.cancel(h1);
let h3 = list.try_schedule(now, 3).unwrap();
list.free(h2);
list.free(h3);
}
#[test]
fn bounded_schedule_forget_full() {
let now = Instant::now();
let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 1, now);
list.try_schedule_forget(now, 1).unwrap();
let err = list.try_schedule_forget(now, 2);
assert!(err.is_err());
assert_eq!(err.unwrap_err().into_inner(), 2);
}
#[test]
fn poll_respects_deadline() {
let now = Instant::now();
let mut list = list_50ms(now);
list.schedule_forget(now, 1); list.schedule_forget(now + ms(40), 2); list.schedule_forget(now + ms(90), 3);
let mut buf = Vec::new();
let fired = list.poll(now + ms(60), &mut buf);
assert_eq!(fired, 1);
assert_eq!(buf, vec![1]);
assert_eq!(list.len(), 2);
buf.clear();
let fired = list.poll(now + ms(100), &mut buf);
assert_eq!(fired, 1);
assert_eq!(buf, vec![2]);
buf.clear();
let fired = list.poll(now + ms(200), &mut buf);
assert_eq!(fired, 1);
assert_eq!(buf, vec![3]);
assert!(list.is_empty());
}
#[test]
fn mid_list_cancel_preserves_fifo() {
let now = Instant::now();
let mut list = list_50ms(now);
let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now + ms(i), i)).collect();
assert_eq!(list.len(), 5);
let v2 = list.cancel(handles.remove(2));
assert_eq!(v2, Some(2));
let v0 = list.cancel(handles.remove(0));
assert_eq!(v0, Some(0));
assert_eq!(list.len(), 3);
let mut buf = Vec::new();
let fired = list.poll(now + ms(1000), &mut buf);
assert_eq!(fired, 3);
assert_eq!(buf, vec![1, 3, 4]);
for h in handles {
assert_eq!(list.cancel(h), None);
}
}
#[test]
fn poll_with_limit_truncation_then_resumption() {
let now = Instant::now();
let mut list = list_50ms(now);
for i in 0..10u64 {
list.schedule_forget(now + ms(i), i);
}
let mut buf = Vec::new();
let poll_at = now + ms(1000);
let fired = list.poll_with_limit(poll_at, 3, &mut buf);
assert_eq!(fired, 3);
assert_eq!(list.len(), 7);
let fired = list.poll_with_limit(poll_at, 3, &mut buf);
assert_eq!(fired, 3);
assert_eq!(list.len(), 4);
let fired = list.poll(poll_at, &mut buf);
assert_eq!(fired, 4);
assert!(list.is_empty());
assert_eq!(buf, (0..10u64).collect::<Vec<_>>());
}
#[test]
fn poll_with_limit_mixed_expiry() {
let now = Instant::now();
let mut list = list_50ms(now);
list.schedule_forget(now, 1);
list.schedule_forget(now, 2);
list.schedule_forget(now, 3);
list.schedule_forget(now + ms(500), 4); list.schedule_forget(now + ms(500), 5);
assert_eq!(list.len(), 5);
let mut buf = Vec::new();
let fired = list.poll_with_limit(now + ms(60), 2, &mut buf);
assert_eq!(fired, 2);
assert_eq!(list.len(), 3);
let fired = list.poll_with_limit(now + ms(60), 5, &mut buf);
assert_eq!(fired, 1); assert_eq!(list.len(), 2);
assert_eq!(buf, vec![1, 2, 3]);
}
#[test]
fn next_deadline_is_head_before_and_after_cancel() {
let now = Instant::now();
let mut list = list_50ms(now);
let h0 = list.schedule(now, 0); list.schedule_forget(now + ms(30), 1); list.schedule_forget(now + ms(60), 2);
let d0 = list.next_deadline().unwrap();
let delta0 = d0.duration_since(now);
assert!(delta0 >= ms(49) && delta0 <= ms(51), "delta0 = {delta0:?}");
assert_eq!(list.cancel(h0), Some(0));
let d1 = list.next_deadline().unwrap();
let delta1 = d1.duration_since(now);
assert!(delta1 >= ms(79) && delta1 <= ms(81), "delta1 = {delta1:?}");
}
#[test]
fn next_deadline_empty_after_drain() {
let now = Instant::now();
let mut list = list_50ms(now);
list.schedule_forget(now, 1);
let mut buf = Vec::new();
list.poll(now + ms(60), &mut buf);
assert!(list.next_deadline().is_none());
}
#[test]
fn nothing_due_poll_examines_only_head() {
let now = Instant::now();
for &population in &[100usize, 1_000, 10_000, 50_000] {
let mut list: TimeoutQueue<u64> =
TimeoutQueue::unbounded(Duration::from_secs(3600), population + 16, now);
for i in 0..population as u64 {
list.schedule_forget(now, i);
}
assert_eq!(list.len(), population);
let mut buf = Vec::new();
poll_examined_reset();
let fired = list.poll(now + ms(1), &mut buf); assert_eq!(fired, 0);
assert!(buf.is_empty());
assert_eq!(
poll_examined_get(),
1,
"population {population}: nothing-due poll examined more than the head",
);
}
}
#[test]
fn nothing_due_poll_empty_examines_zero() {
let now = Instant::now();
let mut list = list_50ms(now);
let mut buf = Vec::new();
poll_examined_reset();
let fired = list.poll(now + ms(1), &mut buf);
assert_eq!(fired, 0);
assert_eq!(poll_examined_get(), 0);
}
#[test]
fn multiple_entries_same_deadline() {
let now = Instant::now();
let mut list = list_50ms(now);
let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now, i)).collect();
assert_eq!(list.len(), 5);
let v2 = list.cancel(handles.remove(2));
assert_eq!(v2, Some(2));
let v0 = list.cancel(handles.remove(0));
assert_eq!(v0, Some(0));
assert_eq!(list.len(), 3);
let mut buf = Vec::new();
let fired = list.poll(now + ms(60), &mut buf);
assert_eq!(fired, 3);
assert_eq!(buf, vec![1, 3, 4]);
for h in handles {
assert_eq!(list.cancel(h), None);
}
}
#[test]
fn reuse_after_full_drain() {
let now = Instant::now();
let mut list = list_50ms(now);
for i in 0..10u64 {
list.schedule_forget(now, i);
}
let mut buf = Vec::new();
list.poll(now + ms(60), &mut buf);
assert_eq!(buf.len(), 10);
assert!(list.is_empty());
buf.clear();
for i in 10..20u64 {
list.schedule_forget(now + ms(100), i);
}
assert_eq!(list.len(), 10);
list.poll(now + ms(200), &mut buf);
assert_eq!(buf.len(), 10);
assert!(list.is_empty());
}
#[test]
fn drop_cleans_up_active_entries() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::Relaxed);
}
}
let dropped = Arc::new(AtomicUsize::new(0));
let now = Instant::now();
let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
for i in 0..100u64 {
list.schedule_forget(now + ms(i), DropCounter(Arc::clone(&dropped)));
}
assert_eq!(list.len(), 100);
drop(list);
assert_eq!(
dropped.load(Ordering::Relaxed),
100,
"every unfired timer's value must be dropped when the list is dropped",
);
}
#[test]
fn drop_with_outstanding_handles() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::Relaxed);
}
}
let dropped = Arc::new(AtomicUsize::new(0));
let now = Instant::now();
let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
for i in 0..100u64 {
let h = list.schedule(now + ms(i), DropCounter(Arc::clone(&dropped)));
std::mem::forget(h); }
assert_eq!(list.len(), 100);
drop(list);
assert_eq!(
dropped.load(Ordering::Relaxed),
100,
"handle-bearing (refs == 2) timer values must be dropped with the list",
);
}
#[test]
fn poll_far_past_deadline_fires() {
let now = Instant::now();
let mut list = list_50ms(now);
list.schedule_forget(now, 42);
let mut buf = Vec::new();
let fired = list.poll(now + ms(10_000), &mut buf);
assert_eq!(fired, 1);
assert_eq!(buf, vec![42]);
}
#[test]
fn miri_schedule_cancel_drop_type() {
let now = Instant::now();
let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
let h = list.schedule(now, "hello".to_string());
let val = list.cancel(h);
assert_eq!(val, Some("hello".to_string()));
assert!(list.is_empty());
}
#[test]
fn miri_poll_fires_drop_type() {
let now = Instant::now();
let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
list.schedule_forget(now, "a".to_string());
list.schedule_forget(now, "b".to_string());
list.schedule_forget(now, "c".to_string());
let mut buf = Vec::new();
let fired = list.poll(now + ms(20), &mut buf);
assert_eq!(fired, 3);
assert_eq!(buf, vec!["a".to_string(), "b".to_string(), "c".to_string()]);
assert!(list.is_empty());
}
#[test]
fn miri_cancel_zombie_drop_type() {
let now = Instant::now();
let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
let h = list.schedule(now, "zombie".to_string());
let mut buf = Vec::new();
list.poll(now + ms(20), &mut buf);
assert_eq!(buf, vec!["zombie".to_string()]);
let val = list.cancel(h);
assert_eq!(val, None);
}
#[test]
fn miri_free_active_and_zombie() {
let now = Instant::now();
let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
let h1 = list.schedule(now, "active".to_string());
list.free(h1);
let mut buf = Vec::new();
list.poll(now + ms(20), &mut buf);
assert_eq!(buf, vec!["active".to_string()]);
let h2 = list.schedule(now, "will-fire".to_string());
buf.clear();
list.poll(now + ms(20), &mut buf);
list.free(h2);
}
#[test]
fn miri_mid_list_unlink_drop_type() {
let now = Instant::now();
let mut list: TimeoutQueue<Vec<u8>> = TimeoutQueue::unbounded(ms(10), 64, now);
let mut handles: Vec<_> = (0..5u8)
.map(|i| list.schedule(now + Duration::from_micros(i as u64), vec![i; 32]))
.collect();
let v2 = list.cancel(handles.remove(2));
assert_eq!(v2.unwrap(), vec![2u8; 32]);
let v0 = list.cancel(handles.remove(0));
assert_eq!(v0.unwrap(), vec![0u8; 32]);
let mut buf = Vec::new();
list.poll(now + ms(20), &mut buf);
assert_eq!(buf.len(), 3);
for h in handles {
assert_eq!(list.cancel(h), None);
}
}
#[test]
fn miri_drop_list_with_entries() {
let now = Instant::now();
let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
for i in 0..20u64 {
list.schedule_forget(now + ms(i), format!("entry-{i}"));
}
assert_eq!(list.len(), 20);
drop(list);
}
#[test]
fn miri_bounded_lifecycle() {
let now = Instant::now();
let mut list: BoundedTimeoutQueue<String> = BoundedTimeoutQueue::bounded(ms(30), 4, now);
let h1 = list.try_schedule(now, "a".to_string()).unwrap();
let h2 = list.try_schedule(now, "b".to_string()).unwrap();
let h3 = list.try_schedule(now, "c".to_string()).unwrap();
let h4 = list.try_schedule(now, "d".to_string()).unwrap();
assert!(list.try_schedule(now, "e".to_string()).is_err());
list.cancel(h1);
let h5 = list.try_schedule(now, "e".to_string()).unwrap();
let mut buf = Vec::new();
list.poll(now + ms(40), &mut buf);
list.free(h2);
list.free(h3);
list.free(h4);
list.free(h5);
}
}
#[cfg(test)]
mod proptests {
use super::*;
use proptest::prelude::*;
use std::collections::{HashMap, HashSet};
use std::time::{Duration, Instant};
const TIMEOUT_MS: u64 = 100;
const EARLY_SLOP_MS: u64 = 1;
#[derive(Debug, Clone)]
enum Op {
Schedule,
ScheduleForget,
Cancel { idx: usize },
Poll,
Advance,
}
fn op_strategy() -> impl Strategy<Value = (Op, u64)> {
let advance = 0u64..500;
let op = prop_oneof![
Just(Op::Schedule),
Just(Op::ScheduleForget),
any::<usize>().prop_map(|idx| Op::Cancel { idx }),
Just(Op::Poll),
Just(Op::Advance),
];
(op, advance)
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(400))]
#[test]
fn fuzz_schedule_cancel_poll(ops in proptest::collection::vec(op_strategy(), 1..300)) {
let now = Instant::now();
let mut list: TimeoutQueue<u64> = TimeoutQueue::unbounded(
Duration::from_millis(TIMEOUT_MS),
4096,
now,
);
let mut live: HashMap<u64, u64> = HashMap::new();
let mut handles: Vec<(TimerHandle<u64>, u64, u64)> = Vec::new();
let mut fired: HashSet<u64> = HashSet::new();
let mut clock: u64 = 0;
let mut next_id: u64 = 0;
for (op, advance) in &ops {
clock += *advance;
match op {
Op::Schedule => {
let id = next_id;
next_id += 1;
let deadline = clock + TIMEOUT_MS;
let h = list.schedule(now + Duration::from_millis(clock), id);
handles.push((h, id, deadline));
live.insert(id, deadline);
}
Op::ScheduleForget => {
let id = next_id;
next_id += 1;
let deadline = clock + TIMEOUT_MS;
list.schedule_forget(now + Duration::from_millis(clock), id);
live.insert(id, deadline);
}
Op::Cancel { idx } => {
if !handles.is_empty() {
let i = idx % handles.len();
let (h, val, _) = handles.swap_remove(i);
let r = list.cancel(h);
prop_assert_eq!(r, Some(val));
prop_assert!(live.remove(&val).is_some());
prop_assert!(!fired.contains(&val));
}
}
Op::Poll => {
let mut buf = Vec::new();
list.poll(now + Duration::from_millis(clock), &mut buf);
let mut prev_deadline = 0u64;
for &v in &buf {
let deadline = *live.get(&v)
.expect("fired value must be live");
prop_assert!(
deadline <= clock + EARLY_SLOP_MS,
"value {} deadline {}ms fired at {}ms",
v, deadline, clock,
);
prop_assert!(deadline >= prev_deadline);
prev_deadline = deadline;
prop_assert!(fired.insert(v));
live.remove(&v);
}
let fired_now: HashSet<u64> = buf.iter().copied().collect();
let mut i = 0;
while i < handles.len() {
if fired_now.contains(&handles[i].1) {
let (h, _, _) = handles.swap_remove(i);
list.free(h);
} else {
i += 1;
}
}
}
Op::Advance => {}
}
prop_assert_eq!(list.len(), live.len());
}
let mut buf = Vec::new();
list.poll(now + Duration::from_secs(1_000_000), &mut buf);
for &v in &buf {
prop_assert!(fired.insert(v));
prop_assert!(live.remove(&v).is_some());
}
for (h, _, _) in handles {
list.free(h);
}
prop_assert!(live.is_empty());
prop_assert!(list.is_empty());
}
}
}