nexus_timer/timeout_queue.rs
1//! Fixed-duration timeout queue — a sorted front-end over the wheel machinery.
2//!
3//! `TimeoutQueue<T, S>` schedules every timer with the **same** duration, fixed
4//! at construction. Because the duration is constant and the clock is monotone,
5//! deadlines are monotone in insertion order: appending each new entry at the
6//! tail of one intrusive DLL keeps the list sorted with no comparisons. Poll
7//! then walks from the head and stops at the first not-due entry — **O(fired)**,
8//! not O(population) as the wheel's per-entry scan is. `next_deadline()` is the
9//! head's deadline: exact, O(1), no cache.
10//!
11//! # When to use this instead of [`TimerWheel`](crate::TimerWheel)
12//!
13//! A wheel earns its keep when deadlines are *arbitrary* — timers interleaved
14//! among earlier and later expirations. But a large class of callers schedule
15//! **one fixed timeout for everything** (a flat 5 s deadline on every item).
16//! For that workload the wheel buckets by deadline and walks buckets to solve
17//! an ordering problem that does not exist. `TimeoutQueue` exploits the single
18//! duration directly.
19//!
20//! # The invariant is structural, not documented
21//!
22//! There is no per-call `deadline` parameter anywhere in this API. Deadlines
23//! are computed internally as `now + timeout`. Out-of-order insertion is
24//! *unrepresentable*, not merely prohibited — one caller passing a shorter
25//! deadline would break ordering and fire timers late, the worst failure shape
26//! because it is invisible until it matters. A `debug_assert!` on insert is the
27//! backstop for clock weirdness (a `now` that goes backwards).
28//!
29//! # Reuse
30//!
31//! [`WheelEntry`], [`TimerHandle`], the slab
32//! [`store`](crate::store) traits, and the DLL splice logic (`WheelSlot`) are
33//! shared verbatim with the wheel — this front-end is the same machinery with
34//! one head/tail pair in place of `Vec<Level>`, and the whole `min_deadline`
35//! cache removed (the head *is* the min).
36
37use std::marker::PhantomData;
38use std::mem;
39use std::time::{Duration, Instant};
40
41use nexus_slab::{Full, Slot, bounded, unbounded};
42
43use crate::ConfigError;
44use crate::entry::{EntryPtr, WheelEntry, entry_ref};
45use crate::handle::TimerHandle;
46use crate::level::WheelSlot;
47use crate::store::{BoundedStore, SlabStore};
48
49// =============================================================================
50// TimeoutQueueBuilder (typestate)
51// =============================================================================
52
53/// Builder for a [`TimeoutQueue`], mirroring [`WheelBuilder`](crate::WheelBuilder).
54///
55/// The timeout duration is fixed up front in [`new`](Self::new) — that is the
56/// whole point of the type, so it cannot be a per-schedule parameter later.
57///
58/// # Examples
59///
60/// ```
61/// use std::time::{Duration, Instant};
62/// use nexus_timer::{TimeoutQueue, TimeoutQueueBuilder};
63///
64/// let now = Instant::now();
65///
66/// // 5-second timeout, unbounded storage, default 1ms tick.
67/// let list: TimeoutQueue<u64> = TimeoutQueueBuilder::new(Duration::from_secs(5))
68/// .unbounded(4096)
69/// .build(now)
70/// .unwrap();
71///
72/// // Custom tick, bounded storage.
73/// let list: nexus_timer::BoundedTimeoutQueue<u64> =
74/// TimeoutQueueBuilder::new(Duration::from_millis(250))
75/// .tick_duration(Duration::from_micros(100))
76/// .bounded(1024)
77/// .build(now)
78/// .unwrap();
79/// ```
80#[derive(Debug, Clone, Copy)]
81pub struct TimeoutQueueBuilder {
82 timeout: Duration,
83 tick_duration: Duration,
84}
85
86impl TimeoutQueueBuilder {
87 /// Creates a builder with the fixed timeout every timer will use.
88 ///
89 /// Tick duration defaults to 1ms. The timeout must be non-zero — this is not
90 /// checked here but enforced at [`build`](UnboundedTimeoutQueueBuilder::build),
91 /// which returns [`ConfigError`] otherwise.
92 pub fn new(timeout: Duration) -> Self {
93 TimeoutQueueBuilder {
94 timeout,
95 tick_duration: Duration::from_millis(1),
96 }
97 }
98
99 /// Sets the tick duration (internal time quantum). Default: 1ms.
100 pub fn tick_duration(mut self, d: Duration) -> Self {
101 self.tick_duration = d;
102 self
103 }
104
105 /// Transitions to an unbounded (growable) builder.
106 ///
107 /// `chunk_capacity` is the slab chunk size (entries per chunk); the slab
108 /// grows by adding chunks as needed.
109 pub fn unbounded(self, chunk_capacity: usize) -> UnboundedTimeoutQueueBuilder {
110 UnboundedTimeoutQueueBuilder {
111 config: self,
112 chunk_capacity,
113 }
114 }
115
116 /// Transitions to a bounded (fixed-capacity) builder.
117 ///
118 /// `capacity` is the maximum number of concurrent timers.
119 pub fn bounded(self, capacity: usize) -> BoundedTimeoutQueueBuilder {
120 BoundedTimeoutQueueBuilder {
121 config: self,
122 capacity,
123 }
124 }
125
126 fn validate(&self) -> Result<(), ConfigError> {
127 if self.timeout.is_zero() {
128 return Err(ConfigError::Invalid("timeout must be non-zero"));
129 }
130 if self.tick_duration.is_zero() {
131 return Err(ConfigError::Invalid("tick_duration must be non-zero"));
132 }
133 // tick_ns() narrows as_nanos() (u128) to u64; reject a tick that would
134 // not fit so build() cannot produce a zero tick (divide-by-zero). See
135 // WheelBuilder::validate.
136 if self.tick_duration.as_nanos() > u64::MAX as u128 {
137 return Err(ConfigError::Invalid(
138 "tick_duration must fit in u64 nanoseconds",
139 ));
140 }
141 Ok(())
142 }
143
144 #[inline]
145 fn tick_ns(&self) -> u64 {
146 self.tick_duration.as_nanos().min(u64::MAX as u128) as u64
147 }
148
149 /// Fixed timeout expressed in whole ticks (rounded up, minimum 1 tick).
150 ///
151 /// Ceiling division so the effective timeout is never *shorter* than
152 /// requested. Computed once at build time — never on the hot path.
153 #[inline]
154 fn timeout_ticks(&self) -> u64 {
155 let tick_ns = self.tick_ns() as u128;
156 let timeout_ns = self.timeout.as_nanos();
157 let ticks = timeout_ns.div_ceil(tick_ns);
158 ticks.min(u64::MAX as u128).max(1) as u64
159 }
160}
161
162/// Terminal builder for an unbounded [`TimeoutQueue`].
163///
164/// Created via [`TimeoutQueueBuilder::unbounded`]. The only method is `.build()`.
165#[derive(Debug)]
166pub struct UnboundedTimeoutQueueBuilder {
167 config: TimeoutQueueBuilder,
168 chunk_capacity: usize,
169}
170
171impl UnboundedTimeoutQueueBuilder {
172 /// Builds the unbounded timeout queue, validating the configuration.
173 ///
174 /// # Errors
175 ///
176 /// Returns [`ConfigError`] if the configuration is invalid (zero timeout, or a
177 /// tick duration that is zero or exceeds u64 nanoseconds).
178 pub fn build<T: 'static>(self, now: Instant) -> Result<TimeoutQueue<T>, ConfigError> {
179 self.config.validate()?;
180 let tick_ns = self.config.tick_ns();
181 let timeout_ticks = self.config.timeout_ticks();
182 // SAFETY: TimeoutQueue is single-threaded (!Sync). Every slot is freed
183 // via Slot::from_raw() + slab.free() before the list drops. The slab is
184 // never shared across threads.
185 let slab = unsafe { unbounded::Slab::with_chunk_capacity(self.chunk_capacity) };
186 Ok(TimeoutQueue {
187 list: WheelSlot::new(),
188 slab,
189 timeout_ticks,
190 tick_ns,
191 inv_tick_ns: (1u128 << 64) / tick_ns as u128,
192 epoch: now,
193 len: 0,
194 _marker: PhantomData,
195 })
196 }
197}
198
199/// Terminal builder for a bounded [`TimeoutQueue`].
200///
201/// Created via [`TimeoutQueueBuilder::bounded`]. The only method is `.build()`.
202#[derive(Debug)]
203pub struct BoundedTimeoutQueueBuilder {
204 config: TimeoutQueueBuilder,
205 capacity: usize,
206}
207
208impl BoundedTimeoutQueueBuilder {
209 /// Builds the bounded timeout queue, validating the configuration.
210 ///
211 /// # Errors
212 ///
213 /// Returns [`ConfigError`] if the configuration is invalid (zero timeout, or a
214 /// tick duration that is zero or exceeds u64 nanoseconds).
215 pub fn build<T: 'static>(self, now: Instant) -> Result<BoundedTimeoutQueue<T>, ConfigError> {
216 self.config.validate()?;
217 let tick_ns = self.config.tick_ns();
218 let timeout_ticks = self.config.timeout_ticks();
219 // SAFETY: TimeoutQueue is single-threaded (!Sync). Every slot is freed
220 // via Slot::from_raw() + slab.free() before the list drops. The slab is
221 // never shared across threads.
222 let slab = unsafe { bounded::Slab::with_capacity(self.capacity) };
223 Ok(TimeoutQueue {
224 list: WheelSlot::new(),
225 slab,
226 timeout_ticks,
227 tick_ns,
228 inv_tick_ns: (1u128 << 64) / tick_ns as u128,
229 epoch: now,
230 len: 0,
231 _marker: PhantomData,
232 })
233 }
234}
235
236// =============================================================================
237// TimeoutQueue
238// =============================================================================
239
240/// A fixed-duration timeout queue with O(fired) poll and O(1) exact next-deadline.
241///
242/// Generic over:
243/// - `T` — the user payload stored with each timer.
244/// - `S` — the slab storage backend. Defaults to `unbounded::Slab`.
245///
246/// Every timer uses the same duration, fixed at construction. See the
247/// [module docs](crate::timeout_queue) for the invariant this exploits.
248///
249/// # No `reschedule`
250///
251/// Rescheduling *later* is push-to-tail and stays ordered, but rescheduling
252/// *earlier* would break the sort — and the two are indistinguishable in a
253/// single API. So no `reschedule` is offered: callers `cancel` and re-`schedule`,
254/// which is the same two operations without the ordering hazard. (This mirrors
255/// the wheel's `reschedule`, deliberately omitted here.)
256///
257/// # Thread Safety
258///
259/// `Send` but `!Sync`. Can be moved to a thread at setup but must not be
260/// shared. All internal raw pointers point into owned allocations (slab
261/// chunks) — moving the list moves the heap data with it.
262pub struct TimeoutQueue<
263 T: 'static,
264 S: SlabStore<Item = WheelEntry<T>> = unbounded::Slab<WheelEntry<T>>,
265> {
266 /// The whole sorted list: one head/tail intrusive DLL. Reuses the wheel's
267 /// `WheelSlot` splice logic (push at tail, unlink from anywhere).
268 list: WheelSlot<T>,
269 slab: S,
270 /// Fixed timeout in ticks. Added to `now` on every schedule.
271 timeout_ticks: u64,
272 tick_ns: u64,
273 inv_tick_ns: u128,
274 epoch: Instant,
275 len: usize,
276 _marker: PhantomData<*const ()>, // !Send (overridden below), !Sync
277}
278
279// SAFETY: TimeoutQueue<T, S> exclusively owns all memory behind its raw
280// pointers. The slot head/tail and the WheelEntry prev/next links point into
281// slab-owned memory (SlotCell in a slab chunk, a Vec<SlotCell<T>> heap
282// allocation). When the list is moved, those heap allocations stay at their
283// addresses, so the internal pointers remain valid. No thread-local state, no
284// shared ownership.
285//
286// T: Send is required because timer values cross the thread boundary with the
287// list. S is NOT required to be Send: slab types are !Send (raw pointers,
288// Cell), but the list exclusively owns its slab — no shared access, no
289// aliasing. Outstanding TimerHandle<T> values are !Send and cannot follow the
290// list across threads; they become inert (consuming one requires &mut
291// TimeoutQueue, which the original thread no longer has). Worst case is a slot
292// leak (refcount stuck at 1), not unsoundness — the same reasoning as the
293// wheel.
294#[allow(clippy::non_send_fields_in_send_ty)]
295unsafe impl<T: Send + 'static, S: SlabStore<Item = WheelEntry<T>>> Send for TimeoutQueue<T, S> {}
296
297/// A timeout queue backed by a fixed-capacity slab.
298pub type BoundedTimeoutQueue<T> = TimeoutQueue<T, bounded::Slab<WheelEntry<T>>>;
299
300// =============================================================================
301// Construction convenience
302// =============================================================================
303
304impl<T: 'static> TimeoutQueue<T> {
305 /// Creates an unbounded timeout queue with the default 1ms tick.
306 ///
307 /// Every timer fires `timeout` after the `now` passed to `schedule`. The
308 /// `now` here fixes the reference epoch — pass one monotone clock source
309 /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For a custom
310 /// tick duration, use [`TimeoutQueueBuilder`].
311 ///
312 /// # Panics
313 ///
314 /// Panics if `timeout` is zero. Use [`TimeoutQueueBuilder::build`] to handle
315 /// a runtime-sourced timeout without panicking.
316 pub fn unbounded(timeout: Duration, chunk_capacity: usize, now: Instant) -> Self {
317 TimeoutQueueBuilder::new(timeout)
318 .unbounded(chunk_capacity)
319 .build(now)
320 .expect("TimeoutQueue requires a non-zero timeout")
321 }
322}
323
324impl<T: 'static> BoundedTimeoutQueue<T> {
325 /// Creates a bounded timeout queue with the default 1ms tick.
326 ///
327 /// Every timer fires `timeout` after the `now` passed to `schedule`. The
328 /// `now` here fixes the reference epoch — pass one monotone clock source
329 /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For a custom
330 /// tick duration, use [`TimeoutQueueBuilder`].
331 ///
332 /// # Panics
333 ///
334 /// Panics if `timeout` is zero. Use [`TimeoutQueueBuilder::build`] to handle
335 /// a runtime-sourced timeout without panicking.
336 pub fn bounded(timeout: Duration, capacity: usize, now: Instant) -> Self {
337 TimeoutQueueBuilder::new(timeout)
338 .bounded(capacity)
339 .build(now)
340 .expect("TimeoutQueue requires a non-zero timeout")
341 }
342}
343
344// =============================================================================
345// Schedule
346// =============================================================================
347
348impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
349 /// Schedules a timer for `now + timeout` and returns a handle for cancellation.
350 ///
351 /// The handle must be consumed via [`cancel`](Self::cancel) or
352 /// [`free`](Self::free). Dropping it is a programming error.
353 ///
354 /// `now` must be monotonically non-decreasing across calls (a plain
355 /// `Instant::now()` at each call site satisfies this). A `now` that goes
356 /// backwards trips a `debug_assert!` in debug builds.
357 ///
358 /// # Panics
359 ///
360 /// Panics if the backing slab is at capacity (bounded slabs only). This is
361 /// a capacity planning error — size the list for peak load.
362 pub fn schedule(&mut self, now: Instant, value: T) -> TimerHandle<T> {
363 let deadline_ticks = self.deadline_for(now);
364 let entry = WheelEntry::new(deadline_ticks, value, 2);
365 let ptr = self.slab.alloc(entry).into_raw();
366 self.insert_entry(ptr, deadline_ticks);
367 self.len += 1;
368 TimerHandle::new(ptr)
369 }
370
371 /// Schedules a fire-and-forget timer for `now + timeout` (no handle returned).
372 ///
373 /// The timer fires during poll and its value is collected. It cannot be
374 /// cancelled. See [`schedule`](Self::schedule) for the `now` monotonicity
375 /// requirement.
376 ///
377 /// # Panics
378 ///
379 /// Panics if the backing slab is at capacity (bounded slabs only).
380 pub fn schedule_forget(&mut self, now: Instant, value: T) {
381 let deadline_ticks = self.deadline_for(now);
382 let entry = WheelEntry::new(deadline_ticks, value, 1);
383 let ptr = self.slab.alloc(entry).into_raw();
384 self.insert_entry(ptr, deadline_ticks);
385 self.len += 1;
386 }
387}
388
389// =============================================================================
390// Schedule — fallible (bounded slabs only)
391// =============================================================================
392
393impl<T: 'static, S: BoundedStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
394 /// Attempts to schedule a timer, returning a handle on success.
395 ///
396 /// Returns `Err(Full(value))` — with the caller's `T` recovered, not the
397 /// internal `WheelEntry` — if the slab is at capacity. Use this when
398 /// capacity exhaustion should be handled gracefully; otherwise use
399 /// [`schedule`](Self::schedule).
400 pub fn try_schedule(&mut self, now: Instant, value: T) -> Result<TimerHandle<T>, Full<T>> {
401 let deadline_ticks = self.deadline_for(now);
402 let entry = WheelEntry::new(deadline_ticks, value, 2);
403 match self.slab.try_alloc(entry) {
404 Ok(slot) => {
405 let ptr = slot.into_raw();
406 self.insert_entry(ptr, deadline_ticks);
407 self.len += 1;
408 Ok(TimerHandle::new(ptr))
409 }
410 Err(full) => Err(Full(recover_value(full))),
411 }
412 }
413
414 /// Attempts to schedule a fire-and-forget timer.
415 ///
416 /// Returns `Err(Full(value))` — with the caller's `T` recovered — if the
417 /// slab is at capacity. Otherwise use [`schedule_forget`](Self::schedule_forget).
418 pub fn try_schedule_forget(&mut self, now: Instant, value: T) -> Result<(), Full<T>> {
419 let deadline_ticks = self.deadline_for(now);
420 let entry = WheelEntry::new(deadline_ticks, value, 1);
421 match self.slab.try_alloc(entry) {
422 Ok(slot) => {
423 let ptr = slot.into_raw();
424 self.insert_entry(ptr, deadline_ticks);
425 self.len += 1;
426 Ok(())
427 }
428 Err(full) => Err(Full(recover_value(full))),
429 }
430 }
431}
432
433/// Extracts the user's `T` from a `Full<WheelEntry<T>>` produced by a rejected
434/// `try_alloc`. The entry was just constructed with `Some(value)` and never
435/// inserted, so the value is present.
436#[inline]
437fn recover_value<T>(full: Full<WheelEntry<T>>) -> T {
438 let wheel_entry = full.into_inner();
439 // SAFETY: entry was just constructed with Some(value) and never inserted
440 // into the list — no other code has accessed it. Single-threaded.
441 unsafe { wheel_entry.take_value() }.expect("entry was just constructed with Some(value)")
442}
443
444// =============================================================================
445// Cancel / Free / Poll / Query — generic over any store
446// =============================================================================
447
448impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
449 /// Cancels a timer and returns its value.
450 ///
451 /// - Still active (refs == 2): unlinks from the list, extracts the value,
452 /// frees the slab entry. Returns `Some(T)`. O(1) — a mid-list unlink,
453 /// no residency, no tombstone.
454 /// - Already fired (zombie handle, refs == 1): frees the slab entry.
455 /// Returns `None`.
456 ///
457 /// Consumes the handle (no Drop runs).
458 pub fn cancel(&mut self, handle: TimerHandle<T>) -> Option<T> {
459 let ptr = handle.ptr;
460 // Consume handle without running Drop.
461 mem::forget(handle);
462
463 // SAFETY: handle guarantees ptr is valid and allocated from our slab.
464 let entry = unsafe { entry_ref(ptr) };
465 let refs = entry.refs();
466
467 if refs == 2 {
468 // Active timer with handle — unlink, extract, free.
469 // SAFETY: single-threaded; entry is still in the list (refs == 2),
470 // so the value has not been taken by fire_entry.
471 let value = unsafe { entry.take_value() };
472 // SAFETY: ptr is in self.list's DLL (invariant from insert_entry).
473 unsafe { self.list.remove_entry(ptr) };
474 self.len -= 1;
475 // SAFETY: ptr was allocated from our slab via into_raw().
476 self.slab.free(unsafe { Slot::from_raw(ptr) });
477 value
478 } else {
479 // refs == 1: the list already fired this (zombie). The fire path
480 // decremented 2 -> 1 and left the entry for us to free.
481 debug_assert_eq!(refs, 1, "unexpected refcount {refs} in cancel");
482 // SAFETY: ptr was allocated from our slab via into_raw().
483 self.slab.free(unsafe { Slot::from_raw(ptr) });
484 None
485 }
486 }
487
488 /// Releases a timer handle without cancelling.
489 ///
490 /// - Still active: converts to fire-and-forget (refs 2 -> 1). The timer
491 /// stays in the list and fires normally during poll.
492 /// - Already fired (zombie): frees the slab entry (refs 1 -> 0).
493 ///
494 /// Consumes the handle (no Drop runs).
495 pub fn free(&mut self, handle: TimerHandle<T>) {
496 let ptr = handle.ptr;
497 mem::forget(handle);
498
499 // SAFETY: handle guarantees ptr is valid.
500 let entry = unsafe { entry_ref(ptr) };
501 let new_refs = entry.dec_refs();
502
503 if new_refs == 0 {
504 // Was a zombie (fired already, refs was 1) — free the entry.
505 // SAFETY: ptr was allocated from our slab via into_raw().
506 self.slab.free(unsafe { Slot::from_raw(ptr) });
507 }
508 // new_refs == 1: timer is now fire-and-forget, stays in the list.
509 }
510
511 /// Fires all expired timers, collecting their values into `buf`.
512 ///
513 /// Returns the number of timers fired. O(fired): the list is sorted, so
514 /// this walks from the head and stops at the first not-due entry.
515 pub fn poll(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
516 self.poll_with_limit(now, usize::MAX, buf)
517 }
518
519 /// Fires expired timers up to `limit`, collecting values into `buf`.
520 ///
521 /// Returns the number fired in this call. Truncation is resumable: this
522 /// stops at a head that is either not-due or beyond `limit`, and the next
523 /// call picks up at exactly that head. No bookmark is needed — the sorted
524 /// list *is* the cursor. (The wheel needs a resumption argument because it
525 /// re-derives its scan position each call; here there is nothing to
526 /// re-derive.)
527 pub fn poll_with_limit(&mut self, now: Instant, limit: usize, buf: &mut Vec<T>) -> usize {
528 let now_ticks = self.instant_to_ticks(now);
529 let mut fired = 0;
530
531 while fired < limit {
532 let ptr = self.list.entry_head();
533 if ptr.is_null() {
534 break;
535 }
536 // SAFETY: ptr is the non-null head of self.list's DLL.
537 let entry = unsafe { entry_ref(ptr) };
538
539 #[cfg(test)]
540 {
541 poll_examined_inc();
542 }
543
544 if entry.deadline_ticks() > now_ticks {
545 // Sorted: nothing behind the head is due either.
546 break;
547 }
548
549 // SAFETY: ptr is the current head of self.list's DLL.
550 unsafe { self.list.remove_entry(ptr) };
551 if let Some(value) = self.fire_entry(ptr) {
552 buf.push(value);
553 }
554 fired += 1;
555 }
556
557 fired
558 }
559
560 /// Returns the `Instant` of the next timer that will fire, or `None` if empty.
561 ///
562 /// O(1), exact: the sorted list's head *is* the minimum deadline. No cache.
563 pub fn next_deadline(&self) -> Option<Instant> {
564 let head = self.list.entry_head();
565 if head.is_null() {
566 return None;
567 }
568 // SAFETY: head is non-null and points into self.list's DLL.
569 let ticks = unsafe { entry_ref(head) }.deadline_ticks();
570 Some(self.ticks_to_instant(ticks))
571 }
572
573 /// Returns the number of timers currently in the list.
574 #[inline]
575 pub fn len(&self) -> usize {
576 self.len
577 }
578
579 /// Returns true if the list contains no timers.
580 #[inline]
581 pub fn is_empty(&self) -> bool {
582 self.len == 0
583 }
584
585 // =========================================================================
586 // Internal: tick conversion (replicated from the wheel)
587 // =========================================================================
588
589 #[inline]
590 fn instant_to_ticks(&self, instant: Instant) -> u64 {
591 let dur = instant.saturating_duration_since(self.epoch);
592 let nanos = dur.as_nanos().min(u64::MAX as u128) as u64;
593 ((nanos as u128 * self.inv_tick_ns) >> 64) as u64
594 }
595
596 #[inline]
597 fn ticks_to_instant(&self, ticks: u64) -> Instant {
598 self.epoch + Duration::from_nanos(ticks.saturating_mul(self.tick_ns))
599 }
600
601 /// Deadline in ticks for a timer scheduled at `now`: `now + fixed timeout`.
602 ///
603 /// Saturating add guards the (unrealistic, ~584-year) case where `now` is
604 /// far enough out that the tick count plus the timeout would overflow u64.
605 #[inline]
606 fn deadline_for(&self, now: Instant) -> u64 {
607 self.instant_to_ticks(now)
608 .saturating_add(self.timeout_ticks)
609 }
610
611 // =========================================================================
612 // Internal: insert / fire
613 // =========================================================================
614
615 /// Appends an entry at the tail of the sorted list.
616 ///
617 /// Correctness rests on the caller's `deadline_ticks` being >= the current
618 /// tail's — guaranteed by a monotone `now` and a constant timeout. The
619 /// `debug_assert!` is the backstop for a clock that goes backwards.
620 #[inline]
621 fn insert_entry(&mut self, entry_ptr: EntryPtr<T>, deadline_ticks: u64) {
622 // The entry's `level`/`slot_idx` stay at their `WheelEntry::new` default
623 // of (0, 0): a single sorted list has no slot to record, and the unlink
624 // path (`WheelSlot::remove_entry`) splices via prev/next and never reads
625 // location. So there is no `set_location` write on this hot path.
626 debug_assert!(
627 {
628 let tail = self.list.entry_tail();
629 // SAFETY: tail, when non-null, points into self.list's DLL.
630 tail.is_null() || deadline_ticks >= unsafe { entry_ref(tail) }.deadline_ticks()
631 },
632 "TimeoutQueue: deadline {deadline_ticks} inserted out of order \
633 (did `now` go backwards?)",
634 );
635
636 // SAFETY: entry_ptr is valid (just allocated) and not in any DLL yet.
637 unsafe { self.list.push_entry(entry_ptr) };
638 }
639
640 /// Fires a single entry: extracts value, decrements refcount, possibly frees.
641 ///
642 /// Returns `Some(T)` if the value was still present (not already cancelled).
643 /// The caller has already unlinked `entry_ptr` from the list.
644 #[inline]
645 fn fire_entry(&mut self, entry_ptr: EntryPtr<T>) -> Option<T> {
646 // SAFETY: entry_ptr was the head we just unlinked; still a live slab slot.
647 let entry = unsafe { entry_ref(entry_ptr) };
648
649 // SAFETY: single-threaded.
650 let value = unsafe { entry.take_value() };
651
652 let new_refs = entry.dec_refs();
653 if new_refs == 0 {
654 // Fire-and-forget (was refs == 1) — free the slab entry immediately.
655 // SAFETY: entry_ptr was allocated from our slab via into_raw().
656 self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
657 }
658 // new_refs == 1: handle exists (was refs == 2), entry becomes a zombie.
659 // The handle holder frees it via cancel() or free().
660
661 self.len -= 1;
662 value
663 }
664}
665
666// =============================================================================
667// Drop
668// =============================================================================
669
670impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> Drop for TimeoutQueue<T, S> {
671 fn drop(&mut self) {
672 // Walk the single list, free every remaining entry so nothing leaks.
673 let mut entry_ptr = self.list.entry_head();
674 while !entry_ptr.is_null() {
675 // SAFETY: entry_ptr is in self.list's DLL.
676 let next_entry = unsafe { entry_ref(entry_ptr) }.next();
677 // SAFETY: entry_ptr was allocated from our slab via into_raw().
678 self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
679 entry_ptr = next_entry;
680 }
681 }
682}
683
684// =============================================================================
685// Test-only instrumentation: entries examined during poll
686// =============================================================================
687//
688// A nothing-due poll must be flat across population — it examines only the
689// head (one deadline compare) and fires nothing, never scanning the list the
690// way the wheel does. This counter proves that: tests reset it, poll, and
691// assert the count is 1 (non-empty, nothing due) regardless of population.
692
693#[cfg(test)]
694thread_local! {
695 static POLL_EXAMINED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
696}
697
698#[cfg(test)]
699fn poll_examined_inc() {
700 POLL_EXAMINED.with(|c| c.set(c.get() + 1));
701}
702
703#[cfg(test)]
704fn poll_examined_reset() {
705 POLL_EXAMINED.with(|c| c.set(0));
706}
707
708#[cfg(test)]
709fn poll_examined_get() -> usize {
710 POLL_EXAMINED.with(std::cell::Cell::get)
711}
712
713// =============================================================================
714// Tests
715// =============================================================================
716
717#[cfg(test)]
718mod tests {
719 use super::*;
720 use std::time::{Duration, Instant};
721
722 fn ms(millis: u64) -> Duration {
723 Duration::from_millis(millis)
724 }
725
726 fn list_50ms(now: Instant) -> TimeoutQueue<u64> {
727 TimeoutQueue::unbounded(ms(50), 1024, now)
728 }
729
730 // -------------------------------------------------------------------------
731 // Thread safety
732 // -------------------------------------------------------------------------
733
734 fn assert_send<T: Send>() {}
735
736 #[test]
737 fn timeout_queue_is_send() {
738 assert_send::<TimeoutQueue<u64>>();
739 assert_send::<BoundedTimeoutQueue<u64>>();
740 }
741
742 // -------------------------------------------------------------------------
743 // Construction
744 // -------------------------------------------------------------------------
745
746 #[test]
747 fn default_construction() {
748 let now = Instant::now();
749 let list = list_50ms(now);
750 assert!(list.is_empty());
751 assert_eq!(list.len(), 0);
752 assert!(list.next_deadline().is_none());
753 }
754
755 #[test]
756 fn bounded_construction() {
757 let now = Instant::now();
758 let list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 128, now);
759 assert!(list.is_empty());
760 }
761
762 /// Asserts `result` is `Err(ConfigError::Invalid(_))` whose message contains
763 /// `expect_substr`. Generic over the Ok type so it needs no `Debug` bound.
764 #[track_caller]
765 fn assert_invalid<T>(result: &Result<T, ConfigError>, expect_substr: &str) {
766 match result {
767 Err(ConfigError::Invalid(msg)) => assert!(
768 msg.contains(expect_substr),
769 "message {msg:?} does not contain {expect_substr:?}"
770 ),
771 Ok(_) => panic!("expected ConfigError::Invalid containing {expect_substr:?}, got Ok"),
772 }
773 }
774
775 #[test]
776 fn invalid_zero_timeout() {
777 let now = Instant::now();
778 let result = TimeoutQueueBuilder::new(Duration::ZERO)
779 .unbounded(64)
780 .build::<u64>(now);
781 assert_invalid(&result, "timeout must be non-zero");
782 }
783
784 #[test]
785 fn invalid_zero_tick() {
786 let now = Instant::now();
787 let result = TimeoutQueueBuilder::new(ms(50))
788 .tick_duration(Duration::ZERO)
789 .unbounded(64)
790 .build::<u64>(now);
791 assert_invalid(&result, "tick_duration must be non-zero");
792 }
793
794 #[test]
795 fn invalid_tick_too_large() {
796 let now = Instant::now();
797 // as_nanos() would exceed u64::MAX and truncate on the cast — reject.
798 let result = TimeoutQueueBuilder::new(ms(50))
799 .tick_duration(Duration::from_secs(20_000_000_000))
800 .unbounded(64)
801 .build::<u64>(now);
802 assert_invalid(&result, "tick_duration must fit in u64 nanoseconds");
803 }
804
805 // -------------------------------------------------------------------------
806 // Lifecycle (ported from wheel.rs)
807 // -------------------------------------------------------------------------
808
809 #[test]
810 fn schedule_and_cancel() {
811 let now = Instant::now();
812 let mut list = list_50ms(now);
813
814 let h = list.schedule(now, 42);
815 assert_eq!(list.len(), 1);
816
817 let val = list.cancel(h);
818 assert_eq!(val, Some(42));
819 assert_eq!(list.len(), 0);
820 }
821
822 #[test]
823 fn schedule_forget_fires() {
824 let now = Instant::now();
825 let mut list = list_50ms(now);
826
827 list.schedule_forget(now, 99);
828 assert_eq!(list.len(), 1);
829
830 let mut buf = Vec::new();
831 let fired = list.poll(now + ms(60), &mut buf);
832 assert_eq!(fired, 1);
833 assert_eq!(buf, vec![99]);
834 assert_eq!(list.len(), 0);
835 }
836
837 #[test]
838 fn cancel_after_fire_returns_none() {
839 let now = Instant::now();
840 let mut list = list_50ms(now);
841
842 let h = list.schedule(now, 42);
843
844 let mut buf = Vec::new();
845 list.poll(now + ms(60), &mut buf);
846 assert_eq!(buf, vec![42]);
847
848 // Handle is now a zombie.
849 let val = list.cancel(h);
850 assert_eq!(val, None);
851 }
852
853 #[test]
854 fn free_active_timer_becomes_fire_and_forget() {
855 let now = Instant::now();
856 let mut list = list_50ms(now);
857
858 let h = list.schedule(now, 42);
859 list.free(h); // releases handle, timer stays
860 assert_eq!(list.len(), 1);
861
862 let mut buf = Vec::new();
863 list.poll(now + ms(60), &mut buf);
864 assert_eq!(buf, vec![42]);
865 assert_eq!(list.len(), 0);
866 }
867
868 #[test]
869 fn free_zombie_handle() {
870 let now = Instant::now();
871 let mut list = list_50ms(now);
872
873 let h = list.schedule(now, 42);
874
875 let mut buf = Vec::new();
876 list.poll(now + ms(60), &mut buf);
877
878 // Handle is a zombie, free cleans up.
879 list.free(h);
880 }
881
882 // -------------------------------------------------------------------------
883 // Bounded full
884 // -------------------------------------------------------------------------
885
886 #[test]
887 fn bounded_full() {
888 let now = Instant::now();
889 let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 2, now);
890
891 let h1 = list.try_schedule(now, 1).unwrap();
892 let h2 = list.try_schedule(now, 2).unwrap();
893
894 let err = list.try_schedule(now, 3);
895 assert!(err.is_err());
896 // The caller's T is recovered, not the WheelEntry wrapper.
897 let recovered = err.unwrap_err().into_inner();
898 assert_eq!(recovered, 3);
899
900 // Cancel one, room again.
901 list.cancel(h1);
902 let h3 = list.try_schedule(now, 3).unwrap();
903
904 list.free(h2);
905 list.free(h3);
906 }
907
908 #[test]
909 fn bounded_schedule_forget_full() {
910 let now = Instant::now();
911 let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 1, now);
912
913 list.try_schedule_forget(now, 1).unwrap();
914 let err = list.try_schedule_forget(now, 2);
915 assert!(err.is_err());
916 assert_eq!(err.unwrap_err().into_inner(), 2);
917 }
918
919 // -------------------------------------------------------------------------
920 // Ordering / FIFO
921 // -------------------------------------------------------------------------
922
923 #[test]
924 fn poll_respects_deadline() {
925 let now = Instant::now();
926 let mut list = list_50ms(now);
927
928 // Fixed 50ms timeout; schedule at staggered `now`s.
929 list.schedule_forget(now, 1); // deadline ~50ms
930 list.schedule_forget(now + ms(40), 2); // deadline ~90ms
931 list.schedule_forget(now + ms(90), 3); // deadline ~140ms
932
933 let mut buf = Vec::new();
934
935 let fired = list.poll(now + ms(60), &mut buf);
936 assert_eq!(fired, 1);
937 assert_eq!(buf, vec![1]);
938 assert_eq!(list.len(), 2);
939
940 buf.clear();
941 let fired = list.poll(now + ms(100), &mut buf);
942 assert_eq!(fired, 1);
943 assert_eq!(buf, vec![2]);
944
945 buf.clear();
946 let fired = list.poll(now + ms(200), &mut buf);
947 assert_eq!(fired, 1);
948 assert_eq!(buf, vec![3]);
949
950 assert!(list.is_empty());
951 }
952
953 #[test]
954 fn mid_list_cancel_preserves_fifo() {
955 let now = Instant::now();
956 let mut list = list_50ms(now);
957
958 // Five timers at strictly increasing `now`s → strictly increasing
959 // deadlines, in insertion order.
960 let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now + ms(i), i)).collect();
961 assert_eq!(list.len(), 5);
962
963 // Cancel index 2 (value 2), then index 0 (value 0). Remaining, in
964 // list order: [1, 3, 4].
965 let v2 = list.cancel(handles.remove(2));
966 assert_eq!(v2, Some(2));
967 let v0 = list.cancel(handles.remove(0));
968 assert_eq!(v0, Some(0));
969 assert_eq!(list.len(), 3);
970
971 let mut buf = Vec::new();
972 let fired = list.poll(now + ms(1000), &mut buf);
973 assert_eq!(fired, 3);
974 // Exact Vec equality — FIFO order, not sorted-after-the-fact.
975 assert_eq!(buf, vec![1, 3, 4]);
976
977 // Remaining handles are zombies now.
978 for h in handles {
979 assert_eq!(list.cancel(h), None);
980 }
981 }
982
983 // -------------------------------------------------------------------------
984 // poll_with_limit truncation + resumption
985 // -------------------------------------------------------------------------
986
987 #[test]
988 fn poll_with_limit_truncation_then_resumption() {
989 let now = Instant::now();
990 let mut list = list_50ms(now);
991
992 for i in 0..10u64 {
993 list.schedule_forget(now + ms(i), i);
994 }
995
996 let mut buf = Vec::new();
997 let poll_at = now + ms(1000);
998
999 let fired = list.poll_with_limit(poll_at, 3, &mut buf);
1000 assert_eq!(fired, 3);
1001 assert_eq!(list.len(), 7);
1002
1003 let fired = list.poll_with_limit(poll_at, 3, &mut buf);
1004 assert_eq!(fired, 3);
1005 assert_eq!(list.len(), 4);
1006
1007 let fired = list.poll(poll_at, &mut buf);
1008 assert_eq!(fired, 4);
1009 assert!(list.is_empty());
1010
1011 // Full set, in order, across the truncated calls.
1012 assert_eq!(buf, (0..10u64).collect::<Vec<_>>());
1013 }
1014
1015 #[test]
1016 fn poll_with_limit_mixed_expiry() {
1017 let now = Instant::now();
1018 let mut list = list_50ms(now);
1019
1020 // Three due at poll time, two not.
1021 list.schedule_forget(now, 1);
1022 list.schedule_forget(now, 2);
1023 list.schedule_forget(now, 3);
1024 list.schedule_forget(now + ms(500), 4); // deadline ~550ms
1025 list.schedule_forget(now + ms(500), 5);
1026 assert_eq!(list.len(), 5);
1027
1028 let mut buf = Vec::new();
1029
1030 let fired = list.poll_with_limit(now + ms(60), 2, &mut buf);
1031 assert_eq!(fired, 2);
1032 assert_eq!(list.len(), 3);
1033
1034 let fired = list.poll_with_limit(now + ms(60), 5, &mut buf);
1035 assert_eq!(fired, 1); // only the third due entry; 4 and 5 not due
1036 assert_eq!(list.len(), 2);
1037
1038 assert_eq!(buf, vec![1, 2, 3]);
1039 }
1040
1041 // -------------------------------------------------------------------------
1042 // next_deadline
1043 // -------------------------------------------------------------------------
1044
1045 #[test]
1046 fn next_deadline_is_head_before_and_after_cancel() {
1047 let now = Instant::now();
1048 let mut list = list_50ms(now);
1049
1050 let h0 = list.schedule(now, 0); // deadline ~ now+50
1051 list.schedule_forget(now + ms(30), 1); // deadline ~ now+80
1052 list.schedule_forget(now + ms(60), 2); // deadline ~ now+110
1053
1054 // Head is the first-scheduled: ~ now + 50ms.
1055 let d0 = list.next_deadline().unwrap();
1056 let delta0 = d0.duration_since(now);
1057 assert!(delta0 >= ms(49) && delta0 <= ms(51), "delta0 = {delta0:?}");
1058
1059 // Cancel the head — next deadline becomes the second entry (~now+80ms).
1060 assert_eq!(list.cancel(h0), Some(0));
1061 let d1 = list.next_deadline().unwrap();
1062 let delta1 = d1.duration_since(now);
1063 assert!(delta1 >= ms(79) && delta1 <= ms(81), "delta1 = {delta1:?}");
1064 }
1065
1066 #[test]
1067 fn next_deadline_empty_after_drain() {
1068 let now = Instant::now();
1069 let mut list = list_50ms(now);
1070 list.schedule_forget(now, 1);
1071
1072 let mut buf = Vec::new();
1073 list.poll(now + ms(60), &mut buf);
1074 assert!(list.next_deadline().is_none());
1075 }
1076
1077 // -------------------------------------------------------------------------
1078 // Nothing-due poll touches (examines) only the head — flat across population
1079 // -------------------------------------------------------------------------
1080
1081 #[test]
1082 fn nothing_due_poll_examines_only_head() {
1083 let now = Instant::now();
1084
1085 for &population in &[100usize, 1_000, 10_000, 50_000] {
1086 // Big timeout so nothing is due at poll time.
1087 let mut list: TimeoutQueue<u64> =
1088 TimeoutQueue::unbounded(Duration::from_secs(3600), population + 16, now);
1089 for i in 0..population as u64 {
1090 list.schedule_forget(now, i);
1091 }
1092 assert_eq!(list.len(), population);
1093
1094 let mut buf = Vec::new();
1095 poll_examined_reset();
1096 let fired = list.poll(now + ms(1), &mut buf); // nothing due
1097 assert_eq!(fired, 0);
1098 assert!(buf.is_empty());
1099
1100 // Exactly one entry examined (the head), regardless of population.
1101 // This is the O(1) nothing-due property — no population scan.
1102 assert_eq!(
1103 poll_examined_get(),
1104 1,
1105 "population {population}: nothing-due poll examined more than the head",
1106 );
1107 }
1108 }
1109
1110 #[test]
1111 fn nothing_due_poll_empty_examines_zero() {
1112 let now = Instant::now();
1113 let mut list = list_50ms(now);
1114
1115 let mut buf = Vec::new();
1116 poll_examined_reset();
1117 let fired = list.poll(now + ms(1), &mut buf);
1118 assert_eq!(fired, 0);
1119 // Empty list: literally zero entries touched.
1120 assert_eq!(poll_examined_get(), 0);
1121 }
1122
1123 // -------------------------------------------------------------------------
1124 // Same-deadline entries (all scheduled at the same `now`)
1125 // -------------------------------------------------------------------------
1126
1127 #[test]
1128 fn multiple_entries_same_deadline() {
1129 let now = Instant::now();
1130 let mut list = list_50ms(now);
1131
1132 let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now, i)).collect();
1133 assert_eq!(list.len(), 5);
1134
1135 let v2 = list.cancel(handles.remove(2));
1136 assert_eq!(v2, Some(2));
1137 let v0 = list.cancel(handles.remove(0));
1138 assert_eq!(v0, Some(0));
1139 assert_eq!(list.len(), 3);
1140
1141 let mut buf = Vec::new();
1142 let fired = list.poll(now + ms(60), &mut buf);
1143 assert_eq!(fired, 3);
1144 assert_eq!(buf, vec![1, 3, 4]);
1145
1146 for h in handles {
1147 assert_eq!(list.cancel(h), None);
1148 }
1149 }
1150
1151 // -------------------------------------------------------------------------
1152 // Reuse after drain
1153 // -------------------------------------------------------------------------
1154
1155 #[test]
1156 fn reuse_after_full_drain() {
1157 let now = Instant::now();
1158 let mut list = list_50ms(now);
1159
1160 for i in 0..10u64 {
1161 list.schedule_forget(now, i);
1162 }
1163 let mut buf = Vec::new();
1164 list.poll(now + ms(60), &mut buf);
1165 assert_eq!(buf.len(), 10);
1166 assert!(list.is_empty());
1167
1168 buf.clear();
1169 for i in 10..20u64 {
1170 list.schedule_forget(now + ms(100), i);
1171 }
1172 assert_eq!(list.len(), 10);
1173 list.poll(now + ms(200), &mut buf);
1174 assert_eq!(buf.len(), 10);
1175 assert!(list.is_empty());
1176 }
1177
1178 // -------------------------------------------------------------------------
1179 // Drop
1180 // -------------------------------------------------------------------------
1181
1182 #[test]
1183 fn drop_cleans_up_active_entries() {
1184 // Prove the list drops the VALUES of unfired timers on `Drop`, not just
1185 // that it reclaims the slab slots. `unbounded::Slab::free` drops the
1186 // value (store.rs), but nothing else in the suite verifies it — the miri
1187 // run uses `-Zmiri-ignore-leaks`, so a value leak would slip straight
1188 // past. A `Drop`-counting value makes the property observable.
1189 use std::sync::Arc;
1190 use std::sync::atomic::{AtomicUsize, Ordering};
1191
1192 struct DropCounter(Arc<AtomicUsize>);
1193 impl Drop for DropCounter {
1194 fn drop(&mut self) {
1195 self.0.fetch_add(1, Ordering::Relaxed);
1196 }
1197 }
1198
1199 let dropped = Arc::new(AtomicUsize::new(0));
1200 let now = Instant::now();
1201 let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
1202 for i in 0..100u64 {
1203 list.schedule_forget(now + ms(i), DropCounter(Arc::clone(&dropped)));
1204 }
1205 assert_eq!(list.len(), 100);
1206
1207 drop(list);
1208 assert_eq!(
1209 dropped.load(Ordering::Relaxed),
1210 100,
1211 "every unfired timer's value must be dropped when the list is dropped",
1212 );
1213 }
1214
1215 #[test]
1216 fn drop_with_outstanding_handles() {
1217 // Dropping the list must free the VALUES of handle-bearing (refs == 2)
1218 // entries too, even when the handles were never consumed — the one Drop
1219 // path `drop_cleans_up_active_entries` (refs == 1) does not cover. The
1220 // handles are `mem::forget`ed to stand in for "still outstanding"
1221 // without tripping `TimerHandle`'s drop debug_assert.
1222 use std::sync::Arc;
1223 use std::sync::atomic::{AtomicUsize, Ordering};
1224
1225 struct DropCounter(Arc<AtomicUsize>);
1226 impl Drop for DropCounter {
1227 fn drop(&mut self) {
1228 self.0.fetch_add(1, Ordering::Relaxed);
1229 }
1230 }
1231
1232 let dropped = Arc::new(AtomicUsize::new(0));
1233 let now = Instant::now();
1234 let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
1235 for i in 0..100u64 {
1236 let h = list.schedule(now + ms(i), DropCounter(Arc::clone(&dropped)));
1237 std::mem::forget(h); // outstanding handle — never consumed (refs stays 2)
1238 }
1239 assert_eq!(list.len(), 100);
1240
1241 drop(list);
1242 assert_eq!(
1243 dropped.load(Ordering::Relaxed),
1244 100,
1245 "handle-bearing (refs == 2) timer values must be dropped with the list",
1246 );
1247 }
1248
1249 // -------------------------------------------------------------------------
1250 // Deadline-in-the-past fires immediately
1251 // -------------------------------------------------------------------------
1252
1253 #[test]
1254 fn poll_far_past_deadline_fires() {
1255 let now = Instant::now();
1256 let mut list = list_50ms(now);
1257
1258 list.schedule_forget(now, 42);
1259 let mut buf = Vec::new();
1260 // Way past the 50ms deadline.
1261 let fired = list.poll(now + ms(10_000), &mut buf);
1262 assert_eq!(fired, 1);
1263 assert_eq!(buf, vec![42]);
1264 }
1265
1266 // -------------------------------------------------------------------------
1267 // Miri-compatible tests (raw-pointer paths with a Drop type)
1268 // -------------------------------------------------------------------------
1269
1270 #[test]
1271 fn miri_schedule_cancel_drop_type() {
1272 let now = Instant::now();
1273 let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
1274
1275 let h = list.schedule(now, "hello".to_string());
1276 let val = list.cancel(h);
1277 assert_eq!(val, Some("hello".to_string()));
1278 assert!(list.is_empty());
1279 }
1280
1281 #[test]
1282 fn miri_poll_fires_drop_type() {
1283 let now = Instant::now();
1284 let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1285
1286 list.schedule_forget(now, "a".to_string());
1287 list.schedule_forget(now, "b".to_string());
1288 list.schedule_forget(now, "c".to_string());
1289
1290 let mut buf = Vec::new();
1291 let fired = list.poll(now + ms(20), &mut buf);
1292 assert_eq!(fired, 3);
1293 assert_eq!(buf, vec!["a".to_string(), "b".to_string(), "c".to_string()]);
1294 assert!(list.is_empty());
1295 }
1296
1297 #[test]
1298 fn miri_cancel_zombie_drop_type() {
1299 let now = Instant::now();
1300 let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1301
1302 let h = list.schedule(now, "zombie".to_string());
1303
1304 let mut buf = Vec::new();
1305 list.poll(now + ms(20), &mut buf);
1306 assert_eq!(buf, vec!["zombie".to_string()]);
1307
1308 let val = list.cancel(h);
1309 assert_eq!(val, None);
1310 }
1311
1312 #[test]
1313 fn miri_free_active_and_zombie() {
1314 let now = Instant::now();
1315 let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1316
1317 // Active → fire-and-forget via free.
1318 let h1 = list.schedule(now, "active".to_string());
1319 list.free(h1);
1320
1321 let mut buf = Vec::new();
1322 list.poll(now + ms(20), &mut buf);
1323 assert_eq!(buf, vec!["active".to_string()]);
1324
1325 // Zombie → free.
1326 let h2 = list.schedule(now, "will-fire".to_string());
1327 buf.clear();
1328 list.poll(now + ms(20), &mut buf);
1329 list.free(h2);
1330 }
1331
1332 #[test]
1333 fn miri_mid_list_unlink_drop_type() {
1334 let now = Instant::now();
1335 let mut list: TimeoutQueue<Vec<u8>> = TimeoutQueue::unbounded(ms(10), 64, now);
1336
1337 let mut handles: Vec<_> = (0..5u8)
1338 .map(|i| list.schedule(now + Duration::from_micros(i as u64), vec![i; 32]))
1339 .collect();
1340
1341 // Cancel middle, then head.
1342 let v2 = list.cancel(handles.remove(2));
1343 assert_eq!(v2.unwrap(), vec![2u8; 32]);
1344 let v0 = list.cancel(handles.remove(0));
1345 assert_eq!(v0.unwrap(), vec![0u8; 32]);
1346
1347 let mut buf = Vec::new();
1348 list.poll(now + ms(20), &mut buf);
1349 assert_eq!(buf.len(), 3);
1350
1351 for h in handles {
1352 assert_eq!(list.cancel(h), None);
1353 }
1354 }
1355
1356 #[test]
1357 fn miri_drop_list_with_entries() {
1358 let now = Instant::now();
1359 let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
1360
1361 for i in 0..20u64 {
1362 list.schedule_forget(now + ms(i), format!("entry-{i}"));
1363 }
1364 assert_eq!(list.len(), 20);
1365 drop(list);
1366 }
1367
1368 #[test]
1369 fn miri_bounded_lifecycle() {
1370 let now = Instant::now();
1371 let mut list: BoundedTimeoutQueue<String> = BoundedTimeoutQueue::bounded(ms(30), 4, now);
1372
1373 let h1 = list.try_schedule(now, "a".to_string()).unwrap();
1374 let h2 = list.try_schedule(now, "b".to_string()).unwrap();
1375 let h3 = list.try_schedule(now, "c".to_string()).unwrap();
1376 let h4 = list.try_schedule(now, "d".to_string()).unwrap();
1377
1378 assert!(list.try_schedule(now, "e".to_string()).is_err());
1379
1380 list.cancel(h1);
1381 let h5 = list.try_schedule(now, "e".to_string()).unwrap();
1382
1383 let mut buf = Vec::new();
1384 list.poll(now + ms(40), &mut buf);
1385
1386 // Everything fired; remaining handles are zombies.
1387 list.free(h2);
1388 list.free(h3);
1389 list.free(h4);
1390 list.free(h5);
1391 }
1392}
1393
1394// =============================================================================
1395// Property tests
1396// =============================================================================
1397
1398#[cfg(test)]
1399mod proptests {
1400 use super::*;
1401 use proptest::prelude::*;
1402 use std::collections::{HashMap, HashSet};
1403 use std::time::{Duration, Instant};
1404
1405 const TIMEOUT_MS: u64 = 100;
1406 // With a 1ms tick and an exact-multiple timeout, the reciprocal tick
1407 // conversion is at most one tick low, so a timer can fire at most 1ms
1408 // before its nominal `schedule_now + TIMEOUT_MS` deadline.
1409 const EARLY_SLOP_MS: u64 = 1;
1410
1411 #[derive(Debug, Clone)]
1412 enum Op {
1413 Schedule,
1414 ScheduleForget,
1415 Cancel { idx: usize },
1416 Poll,
1417 Advance,
1418 }
1419
1420 fn op_strategy() -> impl Strategy<Value = (Op, u64)> {
1421 // Every op carries a non-negative clock advance, keeping `now`
1422 // monotone so the fixed-timeout deadlines stay sorted.
1423 let advance = 0u64..500;
1424 let op = prop_oneof![
1425 Just(Op::Schedule),
1426 Just(Op::ScheduleForget),
1427 any::<usize>().prop_map(|idx| Op::Cancel { idx }),
1428 Just(Op::Poll),
1429 Just(Op::Advance),
1430 ];
1431 (op, advance)
1432 }
1433
1434 proptest! {
1435 #![proptest_config(ProptestConfig::with_cases(400))]
1436
1437 /// Random schedule / schedule_forget / cancel / poll interleaving.
1438 ///
1439 /// Invariants:
1440 /// - `len` always matches the live (scheduled, not cancelled, not
1441 /// fired) count.
1442 /// - every value fires exactly once.
1443 /// - no value fires before its deadline (within 1ms tick slop).
1444 /// - each poll's output is non-decreasing in deadline.
1445 #[test]
1446 fn fuzz_schedule_cancel_poll(ops in proptest::collection::vec(op_strategy(), 1..300)) {
1447 let now = Instant::now();
1448 let mut list: TimeoutQueue<u64> = TimeoutQueue::unbounded(
1449 Duration::from_millis(TIMEOUT_MS),
1450 4096,
1451 now,
1452 );
1453
1454 // value -> nominal deadline_ms (schedule clock + TIMEOUT_MS)
1455 let mut live: HashMap<u64, u64> = HashMap::new();
1456 // outstanding active handles: (handle, value, deadline_ms)
1457 let mut handles: Vec<(TimerHandle<u64>, u64, u64)> = Vec::new();
1458 let mut fired: HashSet<u64> = HashSet::new();
1459 let mut clock: u64 = 0;
1460 let mut next_id: u64 = 0;
1461
1462 for (op, advance) in &ops {
1463 clock += *advance; // monotone
1464
1465 match op {
1466 Op::Schedule => {
1467 let id = next_id;
1468 next_id += 1;
1469 let deadline = clock + TIMEOUT_MS;
1470 let h = list.schedule(now + Duration::from_millis(clock), id);
1471 handles.push((h, id, deadline));
1472 live.insert(id, deadline);
1473 }
1474 Op::ScheduleForget => {
1475 let id = next_id;
1476 next_id += 1;
1477 let deadline = clock + TIMEOUT_MS;
1478 list.schedule_forget(now + Duration::from_millis(clock), id);
1479 live.insert(id, deadline);
1480 }
1481 Op::Cancel { idx } => {
1482 if !handles.is_empty() {
1483 let i = idx % handles.len();
1484 let (h, val, _) = handles.swap_remove(i);
1485 // Handles only ever hold active timers here (zombies
1486 // are freed right after each poll), so cancel returns
1487 // Some.
1488 let r = list.cancel(h);
1489 prop_assert_eq!(r, Some(val));
1490 prop_assert!(live.remove(&val).is_some());
1491 prop_assert!(!fired.contains(&val));
1492 }
1493 }
1494 Op::Poll => {
1495 let mut buf = Vec::new();
1496 list.poll(now + Duration::from_millis(clock), &mut buf);
1497
1498 let mut prev_deadline = 0u64;
1499 for &v in &buf {
1500 let deadline = *live.get(&v)
1501 .expect("fired value must be live");
1502 // No early fire (within tick slop).
1503 prop_assert!(
1504 deadline <= clock + EARLY_SLOP_MS,
1505 "value {} deadline {}ms fired at {}ms",
1506 v, deadline, clock,
1507 );
1508 // Non-decreasing in deadline within this poll.
1509 prop_assert!(deadline >= prev_deadline);
1510 prev_deadline = deadline;
1511 // Fires exactly once.
1512 prop_assert!(fired.insert(v));
1513 live.remove(&v);
1514 }
1515
1516 // Free zombie handles whose timers just fired.
1517 let fired_now: HashSet<u64> = buf.iter().copied().collect();
1518 let mut i = 0;
1519 while i < handles.len() {
1520 if fired_now.contains(&handles[i].1) {
1521 let (h, _, _) = handles.swap_remove(i);
1522 list.free(h);
1523 } else {
1524 i += 1;
1525 }
1526 }
1527 }
1528 Op::Advance => {}
1529 }
1530
1531 prop_assert_eq!(list.len(), live.len());
1532 }
1533
1534 // Fire everything remaining.
1535 let mut buf = Vec::new();
1536 list.poll(now + Duration::from_secs(1_000_000), &mut buf);
1537 for &v in &buf {
1538 prop_assert!(fired.insert(v));
1539 prop_assert!(live.remove(&v).is_some());
1540 }
1541 // All remaining handles are zombies now.
1542 for (h, _, _) in handles {
1543 list.free(h);
1544 }
1545
1546 prop_assert!(live.is_empty());
1547 prop_assert!(list.is_empty());
1548 }
1549 }
1550}