nexus_timer/wheel.rs
1//! Timer wheel — the main data structure.
2//!
3//! `TimerWheel<T, S>` is a multi-level, rebalancing timer wheel. Entries are
4//! placed into a level based on how far in the future their deadline is, and
5//! **rebalanced** down to finer levels as their deadline approaches; `poll`
6//! then collects ready timers from the small, exact fine-level slots. Timers
7//! fire at their exact tick, never early, never missed.
8
9use std::cell::Cell;
10use std::marker::PhantomData;
11use std::mem;
12use std::time::{Duration, Instant};
13
14use nexus_slab::{Full, Slot, bounded, unbounded};
15
16use crate::entry::{EntryPtr, WheelEntry, entry_ref};
17use crate::handle::TimerHandle;
18use crate::level::Level;
19use crate::store::{BoundedStore, SlabStore};
20
21/// Error returned by a builder's `build` when the configuration is invalid.
22///
23/// A wheel / queue is configured at construction from your own constants, so an
24/// invalid config is a programmer error — but it is *returned* rather than
25/// panicked, both for consistency with the rest of the workspace and so a caller
26/// that sources configuration from runtime input can handle it. The message
27/// names the constraint that was violated.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum ConfigError {
30 /// A configuration value is out of range; the message names the constraint.
31 Invalid(&'static str),
32}
33
34impl std::fmt::Display for ConfigError {
35 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36 match self {
37 Self::Invalid(msg) => write!(f, "timer configuration error: {msg}"),
38 }
39 }
40}
41
42impl std::error::Error for ConfigError {}
43
44// =============================================================================
45// WheelBuilder (typestate)
46// =============================================================================
47
48/// Builder for configuring a timer wheel.
49///
50/// Defaults match the Linux kernel timer wheel (1ms tick, 64 slots/level,
51/// 8x multiplier, 7 levels → ~4.7 hour range).
52///
53/// # Examples
54///
55/// ```
56/// use std::time::{Duration, Instant};
57/// use nexus_timer::{Wheel, WheelBuilder};
58///
59/// let now = Instant::now();
60///
61/// // All defaults
62/// let wheel: Wheel<u64> = WheelBuilder::default().unbounded(4096).build(now).unwrap();
63///
64/// // Custom config
65/// let wheel: Wheel<u64> = WheelBuilder::default()
66/// .tick_duration(Duration::from_micros(100))
67/// .slots_per_level(32)
68/// .unbounded(4096)
69/// .build(now)
70/// .unwrap();
71/// ```
72#[derive(Debug, Clone, Copy)]
73pub struct WheelBuilder {
74 tick_duration: Duration,
75 slots_per_level: usize,
76 clk_shift: u32,
77 num_levels: usize,
78 max_rebalances_per_poll: usize,
79}
80
81impl Default for WheelBuilder {
82 fn default() -> Self {
83 WheelBuilder {
84 tick_duration: Duration::from_millis(1),
85 slots_per_level: 64,
86 clk_shift: 3,
87 num_levels: 7,
88 max_rebalances_per_poll: usize::MAX,
89 }
90 }
91}
92
93impl WheelBuilder {
94 /// Creates a new builder with default configuration.
95 pub fn new() -> Self {
96 Self::default()
97 }
98
99 /// Sets the tick duration. Default: 1ms.
100 pub fn tick_duration(mut self, d: Duration) -> Self {
101 self.tick_duration = d;
102 self
103 }
104
105 /// Sets the number of slots per level. Must be a power of 2, at most 64, and
106 /// greater than `2^clk_shift` so a rebalance always moves an entry to a
107 /// strictly finer level (`clk_shift` and `slots_per_level` are validated
108 /// together at [`build`](UnboundedWheelBuilder::build)). Default: 64.
109 pub fn slots_per_level(mut self, n: usize) -> Self {
110 self.slots_per_level = n;
111 self
112 }
113
114 /// Sets the bit shift between levels (multiplier = 2^clk_shift). Must satisfy
115 /// `2^clk_shift < slots_per_level` so a rebalance always moves an entry to a
116 /// strictly finer level (validated at build); with the default 64 slots that
117 /// allows `clk_shift` up to 5. Default: 3 (8x).
118 pub fn clk_shift(mut self, s: u32) -> Self {
119 self.clk_shift = s;
120 self
121 }
122
123 /// Sets the number of levels. Default: 7.
124 pub fn num_levels(mut self, n: usize) -> Self {
125 self.num_levels = n;
126 self
127 }
128
129 /// Sets the maximum number of entries **rebalanced** (moved to a finer
130 /// level) per [`poll_and_rebalance`](TimerWheel::poll_and_rebalance).
131 /// Default: `usize::MAX` (unbounded).
132 ///
133 /// Rebalancing is maintenance: as time advances, a timer scheduled far in
134 /// the future is placed in a coarse level, and when its slot comes due it is
135 /// moved down to a finer level so it is not re-scanned on every future poll.
136 /// Unbounded (the default), one poll rebalances a whole slot at once — least
137 /// total work, but a rare poll can spike. A cap spreads that work across
138 /// several polls: each poll rebalances at most `n` entries and leaves the
139 /// rest in place, trading the rare spike for slightly more total work (the
140 /// leftover entries are walked again on a later poll).
141 ///
142 /// **This bounds only rebalancing, never firing.** Every due timer is still
143 /// collected at its exact deadline regardless of the cap, because a
144 /// not-yet-due entry left un-rebalanced simply fires from whatever level it
145 /// is sitting in when its time comes. The cap can therefore never make a
146 /// timer fire late or be missed; it is purely a latency-smoothing knob for
147 /// the poll hot path.
148 ///
149 /// **Recommended to tune** for latency-sensitive loops: pick `n` large
150 /// enough to keep up with the steady rebalance rate (roughly
151 /// `population * num_levels / average_timeout_in_ticks`) so entries do not
152 /// backlog, yet small enough that no single poll stalls.
153 pub fn max_rebalances_per_poll(mut self, n: usize) -> Self {
154 self.max_rebalances_per_poll = n;
155 self
156 }
157
158 /// Transitions to an unbounded wheel builder.
159 ///
160 /// `chunk_capacity` is the slab chunk size (entries per chunk). The slab
161 /// grows by adding new chunks as needed.
162 pub fn unbounded(self, chunk_capacity: usize) -> UnboundedWheelBuilder {
163 UnboundedWheelBuilder {
164 config: self,
165 chunk_capacity,
166 }
167 }
168
169 /// Transitions to a bounded wheel builder.
170 ///
171 /// `capacity` is the maximum number of concurrent timers.
172 pub fn bounded(self, capacity: usize) -> BoundedWheelBuilder {
173 BoundedWheelBuilder {
174 config: self,
175 capacity,
176 }
177 }
178
179 fn validate(&self) -> Result<(), ConfigError> {
180 if !self.slots_per_level.is_power_of_two() {
181 return Err(ConfigError::Invalid("slots_per_level must be a power of 2"));
182 }
183 if self.slots_per_level > 64 {
184 return Err(ConfigError::Invalid(
185 "slots_per_level must be <= 64 (u64 bitmask)",
186 ));
187 }
188 if self.num_levels == 0 {
189 return Err(ConfigError::Invalid("num_levels must be > 0"));
190 }
191 if self.num_levels > 8 {
192 return Err(ConfigError::Invalid("num_levels must be <= 8 (u8 bitmask)"));
193 }
194 if self.clk_shift == 0 {
195 return Err(ConfigError::Invalid("clk_shift must be > 0"));
196 }
197 if self.tick_duration.is_zero() {
198 return Err(ConfigError::Invalid("tick_duration must be non-zero"));
199 }
200 // tick_ns() narrows as_nanos() (u128) to u64; a duration whose nanos
201 // exceed u64::MAX would truncate — and a nonzero multiple of 2^64 would
202 // truncate to 0, making inv_tick_ns a divide-by-zero. Reject up front so
203 // build() stays panic-free.
204 if self.tick_duration.as_nanos() > u64::MAX as u128 {
205 return Err(ConfigError::Invalid(
206 "tick_duration must fit in u64 nanoseconds",
207 ));
208 }
209 let max_shift = (self.num_levels - 1) as u64 * self.clk_shift as u64;
210 if max_shift >= 64 {
211 return Err(ConfigError::Invalid(
212 "(num_levels - 1) * clk_shift must be < 64",
213 ));
214 }
215 let slots_log2 = self.slots_per_level.trailing_zeros() as u64;
216 if slots_log2 + max_shift >= 64 {
217 return Err(ConfigError::Invalid(
218 "slots_per_level << max_shift would overflow u64",
219 ));
220 }
221 // Rebalance progress guard. When a due slot is polled, a not-yet-due
222 // entry is relocated to a strictly finer level (see `TimerWheel::poll_level`);
223 // that requires 2^clk_shift < slots_per_level (both powers of two, so
224 // `clk_shift < slots_log2`, avoiding a shift that could overflow for
225 // absurd clk_shift). Checked last so a config that also overflows reports
226 // the overflow first.
227 if (self.clk_shift as u64) >= slots_log2 {
228 return Err(ConfigError::Invalid(
229 "2^clk_shift must be < slots_per_level so rebalancing relocates to a strictly finer level",
230 ));
231 }
232 Ok(())
233 }
234
235 fn tick_ns(&self) -> u64 {
236 self.tick_duration.as_nanos() as u64
237 }
238}
239
240/// Terminal builder for an unbounded timer wheel.
241///
242/// Created via [`WheelBuilder::unbounded`]. The only method is `.build()`.
243#[derive(Debug)]
244pub struct UnboundedWheelBuilder {
245 config: WheelBuilder,
246 chunk_capacity: usize,
247}
248
249impl UnboundedWheelBuilder {
250 /// Builds the unbounded timer wheel, validating the configuration.
251 ///
252 /// # Errors
253 ///
254 /// Returns [`ConfigError`] if the configuration is invalid (e.g.
255 /// non-power-of-2 `slots_per_level`, out-of-range `num_levels` / `clk_shift`,
256 /// zero tick duration, or `2^clk_shift >= slots_per_level`).
257 pub fn build<T: 'static>(self, now: Instant) -> Result<Wheel<T>, ConfigError> {
258 self.config.validate()?;
259 // SAFETY: Timer wheel is single-threaded (!Send, !Sync). All slots
260 // are freed via Slot::from_raw() + slab.free() before the wheel drops.
261 // The slab is never shared across threads.
262 let slab = unsafe { unbounded::Slab::with_chunk_capacity(self.chunk_capacity) };
263 let levels = build_levels::<T>(&self.config);
264 let tick_ns = self.config.tick_ns();
265 Ok(TimerWheel {
266 slab,
267 num_levels: self.config.num_levels,
268 levels,
269 current_ticks: 0,
270 tick_ns,
271 inv_tick_ns: (1u128 << 64) / tick_ns as u128,
272 epoch: now,
273 active_levels: 0,
274 len: 0,
275 min_deadline: Cell::new(None),
276 max_rebalances_per_poll: self.config.max_rebalances_per_poll,
277 _marker: PhantomData,
278 })
279 }
280}
281
282/// Terminal builder for a bounded timer wheel.
283///
284/// Created via [`WheelBuilder::bounded`]. The only method is `.build()`.
285#[derive(Debug)]
286pub struct BoundedWheelBuilder {
287 config: WheelBuilder,
288 capacity: usize,
289}
290
291impl BoundedWheelBuilder {
292 /// Builds the bounded timer wheel, validating the configuration.
293 ///
294 /// # Errors
295 ///
296 /// Returns [`ConfigError`] if the configuration is invalid (e.g.
297 /// non-power-of-2 `slots_per_level`, out-of-range `num_levels` / `clk_shift`,
298 /// zero tick duration, or `2^clk_shift >= slots_per_level`).
299 pub fn build<T: 'static>(self, now: Instant) -> Result<BoundedWheel<T>, ConfigError> {
300 self.config.validate()?;
301 // SAFETY: Timer wheel is single-threaded (!Send, !Sync). All slots
302 // are freed via Slot::from_raw() + slab.free() before the wheel drops.
303 // The slab is never shared across threads.
304 let slab = unsafe { bounded::Slab::with_capacity(self.capacity) };
305 let levels = build_levels::<T>(&self.config);
306 let tick_ns = self.config.tick_ns();
307 Ok(TimerWheel {
308 slab,
309 num_levels: self.config.num_levels,
310 levels,
311 current_ticks: 0,
312 tick_ns,
313 inv_tick_ns: (1u128 << 64) / tick_ns as u128,
314 epoch: now,
315 active_levels: 0,
316 len: 0,
317 min_deadline: Cell::new(None),
318 max_rebalances_per_poll: self.config.max_rebalances_per_poll,
319 _marker: PhantomData,
320 })
321 }
322}
323
324// =============================================================================
325// TimerWheel
326// =============================================================================
327
328/// A multi-level, rebalancing timer wheel.
329///
330/// Generic over:
331/// - `T` — the user payload stored with each timer.
332/// - `S` — the slab storage backend. Defaults to `unbounded::Slab`.
333///
334/// # Thread Safety
335///
336/// `Send` but `!Sync`. Can be moved to a thread at setup but must not
337/// be shared. All internal raw pointers point into owned allocations
338/// (slab chunks, level slot arrays) — moving the wheel moves the heap
339/// data with it.
340pub struct TimerWheel<
341 T: 'static,
342 S: SlabStore<Item = WheelEntry<T>> = unbounded::Slab<WheelEntry<T>>,
343> {
344 slab: S,
345 levels: Vec<Level<T>>,
346 num_levels: usize,
347 active_levels: u8,
348 current_ticks: u64,
349 tick_ns: u64,
350 inv_tick_ns: u128,
351 epoch: Instant,
352 len: usize,
353 min_deadline: Cell<Option<u64>>,
354 /// Max entries rebalanced (moved to a finer level) per poll_and_rebalance (see
355 /// [`WheelBuilder::max_rebalances_per_poll`]). `usize::MAX` = unbounded.
356 max_rebalances_per_poll: usize,
357 _marker: PhantomData<*const ()>, // !Send (overridden below), !Sync
358}
359
360// SAFETY: TimerWheel<T, S> exclusively owns all memory behind its raw pointers.
361//
362// Pointer inventory and ownership:
363// - Slot `entry_head`/`entry_tail` — point into slab-owned memory (SlotCell
364// in a slab chunk). Slab chunks are Vec<SlotCell<T>> heap allocations.
365// - DLL links (`WheelEntry::prev`, `WheelEntry::next`) — point to other
366// SlotCells in the same slab.
367// - `Level::slots` — `Box<[WheelSlot<T>]>`, owned by the level.
368//
369// All pointed-to memory lives inside owned collections (Vec, Box<[T]>).
370// When TimerWheel is moved, the heap allocations stay at their addresses —
371// the internal pointers remain valid. No thread-local state. No shared
372// ownership.
373//
374// T: Send is required because timer values cross the thread boundary with
375// the wheel.
376//
377// S is NOT required to be Send. Slab types are !Send (raw pointers, Cell)
378// but the wheel exclusively owns its slab — no shared access, no aliasing.
379// Moving the wheel moves the slab; heap allocations stay at their addresses
380// so internal pointers remain valid.
381//
382// Outstanding TimerHandle<T> values are !Send and cannot follow the wheel
383// across threads. They become inert — consuming them requires &mut
384// TimerWheel which the original thread no longer has. The debug_assert in
385// TimerHandle::drop catches this as a programming error. Worst case is a
386// slot leak (refcount stuck at 1), not unsoundness.
387#[allow(clippy::non_send_fields_in_send_ty)]
388unsafe impl<T: Send + 'static, S: SlabStore<Item = WheelEntry<T>>> Send for TimerWheel<T, S> {}
389
390/// A timer wheel backed by a fixed-capacity slab.
391pub type BoundedWheel<T> = TimerWheel<T, bounded::Slab<WheelEntry<T>>>;
392
393/// A timer wheel backed by a growable slab.
394pub type Wheel<T> = TimerWheel<T, unbounded::Slab<WheelEntry<T>>>;
395
396// =============================================================================
397// Construction
398// =============================================================================
399
400impl<T: 'static> Wheel<T> {
401 /// Creates an unbounded timer wheel with default configuration.
402 ///
403 /// `now` fixes the reference epoch — pass one monotone clock source
404 /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For custom
405 /// configuration, use [`WheelBuilder`].
406 pub fn unbounded(chunk_capacity: usize, now: Instant) -> Self {
407 WheelBuilder::default()
408 .unbounded(chunk_capacity)
409 .build(now)
410 .expect("default WheelBuilder config is valid")
411 }
412}
413
414impl<T: 'static> BoundedWheel<T> {
415 /// Creates a bounded timer wheel with default configuration.
416 ///
417 /// `now` fixes the reference epoch — pass one monotone clock source
418 /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For custom
419 /// configuration, use [`WheelBuilder`].
420 pub fn bounded(capacity: usize, now: Instant) -> Self {
421 WheelBuilder::default()
422 .bounded(capacity)
423 .build(now)
424 .expect("default WheelBuilder config is valid")
425 }
426}
427
428fn build_levels<T: 'static>(config: &WheelBuilder) -> Vec<Level<T>> {
429 (0..config.num_levels)
430 .map(|i| Level::new(config.slots_per_level, i, config.clk_shift))
431 .collect()
432}
433
434// =============================================================================
435// Schedule
436// =============================================================================
437
438impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
439 /// Schedules a timer and returns a handle for cancellation.
440 ///
441 /// The handle must be consumed via [`cancel`](Self::cancel) or
442 /// [`free`](Self::free). Dropping it is a programming error.
443 ///
444 /// # Panics
445 ///
446 /// Panics if the backing slab is at capacity (bounded slabs only).
447 /// This is a capacity planning error — size your wheel for peak load.
448 pub fn schedule(&mut self, deadline: Instant, value: T) -> TimerHandle<T> {
449 let deadline_ticks = self.instant_to_ticks(deadline);
450 let entry = WheelEntry::new(deadline_ticks, value, 2);
451 let slot = self.slab.alloc(entry);
452 let ptr = slot.into_raw();
453 self.insert_entry(ptr, deadline_ticks);
454 self.len += 1;
455 TimerHandle::new(ptr)
456 }
457
458 /// Schedules a fire-and-forget timer (no handle returned).
459 ///
460 /// The timer will fire during poll and the value will be collected.
461 /// Cannot be cancelled.
462 ///
463 /// # Panics
464 ///
465 /// Panics if the backing slab is at capacity (bounded slabs only).
466 /// This is a capacity planning error — size your wheel for peak load.
467 pub fn schedule_forget(&mut self, deadline: Instant, value: T) {
468 let deadline_ticks = self.instant_to_ticks(deadline);
469 let entry = WheelEntry::new(deadline_ticks, value, 1);
470 let slot = self.slab.alloc(entry);
471 let ptr = slot.into_raw();
472 self.insert_entry(ptr, deadline_ticks);
473 self.len += 1;
474 }
475}
476
477// =============================================================================
478// Schedule — fallible (bounded slabs only)
479// =============================================================================
480
481impl<T: 'static, S: BoundedStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
482 /// Attempts to schedule a timer, returning a handle on success.
483 ///
484 /// Returns `Err(Full(value))` if the slab is at capacity. Use this
485 /// when you need graceful error handling. For the common case where
486 /// capacity exhaustion is fatal, use [`schedule`](Self::schedule).
487 pub fn try_schedule(&mut self, deadline: Instant, value: T) -> Result<TimerHandle<T>, Full<T>> {
488 let deadline_ticks = self.instant_to_ticks(deadline);
489 let entry = WheelEntry::new(deadline_ticks, value, 2);
490 match self.slab.try_alloc(entry) {
491 Ok(slot) => {
492 let ptr = slot.into_raw();
493 self.insert_entry(ptr, deadline_ticks);
494 self.len += 1;
495 Ok(TimerHandle::new(ptr))
496 }
497 Err(full) => {
498 // Extract the user's T from the WheelEntry wrapper
499 let wheel_entry = full.into_inner();
500 // SAFETY: entry was just constructed with Some(value) and never inserted
501 // into the wheel — no other code has accessed it. Single-threaded.
502 let value = unsafe { wheel_entry.take_value() }
503 .expect("entry was just constructed with Some(value)");
504 Err(Full(value))
505 }
506 }
507 }
508
509 /// Attempts to schedule a fire-and-forget timer.
510 ///
511 /// Returns `Err(Full(value))` if the slab is at capacity. Use this
512 /// when you need graceful error handling. For the common case where
513 /// capacity exhaustion is fatal, use [`schedule_forget`](Self::schedule_forget).
514 pub fn try_schedule_forget(&mut self, deadline: Instant, value: T) -> Result<(), Full<T>> {
515 let deadline_ticks = self.instant_to_ticks(deadline);
516 let entry = WheelEntry::new(deadline_ticks, value, 1);
517 match self.slab.try_alloc(entry) {
518 Ok(slot) => {
519 let ptr = slot.into_raw();
520 self.insert_entry(ptr, deadline_ticks);
521 self.len += 1;
522 Ok(())
523 }
524 Err(full) => {
525 let wheel_entry = full.into_inner();
526 // SAFETY: entry was just constructed with Some(value) and never inserted
527 // into the wheel — no other code has accessed it. Single-threaded.
528 let value = unsafe { wheel_entry.take_value() }
529 .expect("entry was just constructed with Some(value)");
530 Err(Full(value))
531 }
532 }
533 }
534}
535
536// =============================================================================
537// Cancel / Free / Poll / Query — generic over any store
538// =============================================================================
539
540impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
541 /// Cancels a timer and returns its value.
542 ///
543 /// - If the timer is still active: unlinks from the wheel, extracts value,
544 /// frees the slab entry. Returns `Some(T)`.
545 /// - If the timer already fired (zombie handle): frees the slab entry.
546 /// Returns `None`.
547 ///
548 /// Consumes the handle (no Drop runs).
549 pub fn cancel(&mut self, handle: TimerHandle<T>) -> Option<T> {
550 let ptr = handle.ptr;
551 // Consume handle without running Drop
552 mem::forget(handle);
553
554 // SAFETY: handle guarantees ptr is valid and allocated from our slab.
555 let entry = unsafe { entry_ref(ptr) };
556 let refs = entry.refs();
557
558 if refs == 2 {
559 // Active timer with handle — unlink, extract, free
560 // SAFETY: single-threaded access; entry is still in the wheel (refs==2),
561 // so the value has not been taken by fire_entry.
562 let value = unsafe { entry.take_value() };
563 let cancelled_deadline = entry.deadline_ticks();
564 self.remove_entry(ptr);
565 self.len -= 1;
566 if self.len == 0 {
567 self.min_deadline.set(None);
568 } else if let Some(cur) = self.min_deadline.get()
569 && cancelled_deadline == cur
570 {
571 self.min_deadline.set(None);
572 }
573 // SAFETY: ptr was allocated from our slab via into_raw()
574 self.slab.free(unsafe { Slot::from_raw(ptr) });
575 value
576 } else {
577 // refs == 1 means the wheel already fired this (zombie).
578 // The fire path decremented 2→1 and left the entry for us to free.
579 debug_assert_eq!(refs, 1, "unexpected refcount {refs} in cancel");
580 // SAFETY: ptr was allocated from our slab via into_raw()
581 self.slab.free(unsafe { Slot::from_raw(ptr) });
582 None
583 }
584 }
585
586 /// Releases a timer handle without cancelling.
587 ///
588 /// - If the timer is still active: converts to fire-and-forget (refs 2→1).
589 /// Timer stays in the wheel and will fire normally during poll.
590 /// - If the timer already fired (zombie): frees the slab entry (refs 1→0).
591 ///
592 /// Consumes the handle (no Drop runs).
593 pub fn free(&mut self, handle: TimerHandle<T>) {
594 let ptr = handle.ptr;
595 mem::forget(handle);
596
597 // SAFETY: handle guarantees ptr is valid
598 let entry = unsafe { entry_ref(ptr) };
599 let new_refs = entry.dec_refs();
600
601 if new_refs == 0 {
602 // Was a zombie (fired already, refs was 1) — free the entry
603 // SAFETY: ptr was allocated from our slab via into_raw()
604 self.slab.free(unsafe { Slot::from_raw(ptr) });
605 }
606 // new_refs == 1: timer is now fire-and-forget, stays in wheel
607 }
608
609 /// Reschedules an active timer to a new deadline.
610 ///
611 /// Moves the entry from its current slot to the correct slot for
612 /// `new_deadline` without extracting or reconstructing the value.
613 ///
614 /// # Panics
615 ///
616 /// Panics if the timer has already fired (zombie handle). Only active
617 /// timers (refs == 2) can be rescheduled.
618 ///
619 /// Consumes and returns a new handle (same entry, new position).
620 pub fn reschedule(&mut self, handle: TimerHandle<T>, new_deadline: Instant) -> TimerHandle<T> {
621 let ptr = handle.ptr;
622 mem::forget(handle);
623
624 // SAFETY: handle guarantees ptr is valid
625 let entry = unsafe { entry_ref(ptr) };
626 assert_eq!(entry.refs(), 2, "cannot reschedule a fired timer");
627
628 let old_deadline = entry.deadline_ticks();
629
630 // Remove from current position
631 self.remove_entry(ptr);
632
633 // Update deadline and reinsert
634 let new_ticks = self.instant_to_ticks(new_deadline);
635 entry.set_deadline_ticks(new_ticks);
636 self.insert_entry(ptr, new_ticks);
637
638 // Cache: if old deadline was the cached min and new is later,
639 // we may have lost the min. insert_entry already handles
640 // new < old (lowers cache), but can't detect old == cached
641 // when moving later.
642 if let Some(cur) = self.min_deadline.get()
643 && old_deadline == cur
644 && new_ticks > cur
645 {
646 self.min_deadline.set(None);
647 }
648
649 TimerHandle::new(ptr)
650 }
651
652 /// Collects all ready (due) timers into `buf`, **without rebalancing**, and
653 /// returns how many were collected.
654 ///
655 /// This is the minimal poll: it hands back the timers whose deadline has
656 /// passed and does no maintenance, so a not-yet-due entry stays in whatever
657 /// level it was placed in. Cheap on any single call — but if you *only* ever
658 /// call `poll`, entries are never moved to finer levels and a busy wheel
659 /// degrades to an O(population) scan per poll. For steady low-latency
660 /// polling, prefer [`poll_and_rebalance`](Self::poll_and_rebalance)
661 /// (collect + maintain in one pass).
662 pub fn poll(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
663 self.poll_with_limit(now, usize::MAX, buf)
664 }
665
666 /// Collects up to `limit` ready timers into `buf`, without rebalancing.
667 ///
668 /// Resumable: if the limit is hit, the next call continues where this one
669 /// left off (as long as `now` hasn't changed). See [`poll`](Self::poll) for
670 /// the rebalancing tradeoff.
671 ///
672 /// Returns the number collected in this call.
673 pub fn poll_with_limit(&mut self, now: Instant, limit: usize, buf: &mut Vec<T>) -> usize {
674 // Rebalance budget 0 → collect only, never move an entry to a finer level.
675 self.poll_inner(now, limit, 0, buf)
676 }
677
678 /// Collects all ready timers into `buf` **and rebalances** the wheel in the
679 /// same pass — the batteries-included poll. Returns how many were collected.
680 ///
681 /// Collecting is unbounded; **rebalancing** (moving not-yet-due entries to
682 /// finer levels so future polls stay cheap) is capped at
683 /// [`max_rebalances_per_poll`](WheelBuilder::max_rebalances_per_poll)
684 /// (default unbounded). The cap only smooths rebalance work across polls — it
685 /// never delays or drops a fire.
686 pub fn poll_and_rebalance(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
687 self.poll_and_rebalance_with_limit(now, usize::MAX, buf)
688 }
689
690 /// Collects up to `limit` ready timers into `buf` and rebalances the wheel.
691 ///
692 /// The collect phase is resumable like
693 /// [`poll_with_limit`](Self::poll_with_limit); rebalancing is capped by
694 /// [`max_rebalances_per_poll`](WheelBuilder::max_rebalances_per_poll).
695 /// Returns the number collected in this call.
696 pub fn poll_and_rebalance_with_limit(
697 &mut self,
698 now: Instant,
699 limit: usize,
700 buf: &mut Vec<T>,
701 ) -> usize {
702 self.poll_inner(now, limit, self.max_rebalances_per_poll, buf)
703 }
704
705 /// **Proactively** rebalances the wheel: moves up to `limit` not-yet-due
706 /// entries down to the finest level they now belong in, and returns how many
707 /// moved. Does **not** collect or fire anything.
708 ///
709 /// This is the maintenance half of [`poll_and_rebalance`](Self::poll_and_rebalance),
710 /// exposed on its own so you can move it *off* the collect hot path.
711 ///
712 /// # When to reach for this
713 ///
714 /// Use `poll` + `rebalance` (instead of `poll_and_rebalance`) when you have a
715 /// **large number of outstanding timers and want to cut the poll tail**. The
716 /// cost of a poll that has work is dominated by walking a fat coarse slot to
717 /// find the ready timers; by pulling entries down to exact fine-level slots
718 /// *before* their slot comes due, `rebalance` keeps that walk small, so the
719 /// collect stays cheap and flat. In practice this moves the poll-tail work
720 /// off the hot path onto `rebalance`, roughly quartering the collect's p99.9
721 /// on a busy wheel — at the price of doing the maintenance yourself, when it
722 /// suits you.
723 ///
724 /// # Recommended pattern: opportunistic + bounded
725 ///
726 /// Rebalance only when a poll came back empty — i.e. during genuine slack —
727 /// and bound each call so a high-frequency loop spreads the work instead of
728 /// stalling on one big sweep (`rebalance` is resumable; the next call
729 /// continues):
730 ///
731 /// ```ignore
732 /// let collected = wheel.poll(now, &mut buf);
733 /// if collected == 0 {
734 /// // nothing to deliver — maintain during the slack, a bounded slice
735 /// wheel.rebalance(now, REBALANCE_BUDGET);
736 /// }
737 /// ```
738 ///
739 /// This self-tunes to load: busy iterations pay only the cheap collect, and
740 /// the maintenance lands exactly on the idle ones. A fixed cadence (rebalance
741 /// every N iterations) also works — just avoid rebalancing on *every* poll,
742 /// which re-walks the look-ahead window and is pure overhead.
743 ///
744 /// # Safety of skipping it
745 ///
746 /// `rebalance` only visits slots whose earliest entry is already within a
747 /// finer level's reach, and moving nothing is always safe: an un-rebalanced
748 /// entry simply fires from wherever it is sitting when its time comes. If you
749 /// never call it, the wheel still works — it just degrades to walking coarse
750 /// slots on the collect path (which is what [`poll_and_rebalance`] does for
751 /// you in one call).
752 ///
753 /// [`poll_and_rebalance`]: Self::poll_and_rebalance
754 pub fn rebalance(&mut self, now: Instant, limit: usize) -> usize {
755 let now_ticks = self.instant_to_ticks(now);
756 self.current_ticks = now_ticks; // select_level / rebalance_level read this.
757
758 let mut moved = 0;
759 // Level 0 is already the finest — nothing to pull down from it. Ascending
760 // order; select_level places each entry at its correct level directly, so
761 // no entry is touched twice.
762 let mut mask = self.active_levels & !1;
763 while mask != 0 && moved < limit {
764 let lvl_idx = mask.trailing_zeros() as usize;
765 mask &= mask - 1;
766 // An entry at this level belongs at a finer one once it is within the
767 // next-finer level's range; a slot is worth visiting only if its
768 // earliest entry has reached that window.
769 let finer_reach = now_ticks.saturating_add(self.levels[lvl_idx - 1].range());
770 moved += self.rebalance_level(lvl_idx, finer_reach, limit - moved);
771 }
772
773 // Entries moved and per-slot minima changed; refresh the global-min cache.
774 self.min_deadline.set(self.walk_min_deadline());
775 moved
776 }
777
778 /// Shared poll body: collect ready timers (up to `limit`) and rebalance
779 /// not-yet-due entries to finer levels (up to `rebalance_budget`).
780 /// `rebalance_budget == 0` is collect-only.
781 fn poll_inner(
782 &mut self,
783 now: Instant,
784 limit: usize,
785 rebalance_budget: usize,
786 buf: &mut Vec<T>,
787 ) -> usize {
788 let now_ticks = self.instant_to_ticks(now);
789 self.current_ticks = now_ticks; // MUST precede the early return — select_level reads it.
790
791 // Fast path: if the cached global minimum is beyond now, nothing is due,
792 // so skip the level walk entirely — and with nothing due there is nothing
793 // to rebalance either. The cache may be stale-low (a lower bound), so this
794 // is conservative: it can miss the shortcut, never fire late.
795 if let Some(min) = self.min_deadline.get()
796 && min > now_ticks
797 {
798 return 0;
799 }
800
801 let mut fired = 0;
802 // Rebalance budget for this whole poll. Bounds only rebalancing, never
803 // collection — so the level loop below is NOT gated on it; due entries
804 // keep being collected after the budget is spent.
805 let mut rebalances = 0;
806 let mut mask = self.active_levels;
807
808 while mask != 0 && fired < limit {
809 let lvl_idx = mask.trailing_zeros() as usize;
810 mask &= mask - 1; // clear lowest set bit
811 fired += self.poll_level(
812 lvl_idx,
813 now_ticks,
814 limit - fired,
815 rebalance_budget,
816 &mut rebalances,
817 buf,
818 );
819 }
820
821 // Refresh the global-min cache from the (now-healed) per-slot minima.
822 // poll_level heals every slot it walks, so this recomputes an accurate
823 // minimum (> now when nothing is due). Without it the cache can stay
824 // stale-low (<= now) after a cancel or a no-fire poll, permanently
825 // defeating the early-exit above and making next_deadline() report a
826 // past instant. Cheap now — one compare per active slot. (If a limit
827 // truncated the poll, a walked-but-not-drained slot stays stale-low, so
828 // the cache stays <= now and the next poll correctly re-enters.)
829 self.min_deadline.set(self.walk_min_deadline());
830
831 fired
832 }
833
834 /// Returns an `Instant` no later than when the next timer fires, or `None`
835 /// if the wheel is empty.
836 ///
837 /// **Lower bound, not exact.** The per-slot minima are stale-low after a
838 /// cancel/fire (they are not recomputed on removal — see the design), so the
839 /// returned instant may be *earlier* than the true next deadline, never
840 /// later. It is safe as a sleep/wake bound: you may wake early and find
841 /// nothing due, but you can never miss a timer.
842 ///
843 /// O(1) on cache hit; otherwise ~one compare per active slot to recompute.
844 pub fn next_deadline(&self) -> Option<Instant> {
845 if let Some(ticks) = self.min_deadline.get() {
846 return Some(self.ticks_to_instant(ticks));
847 }
848 if self.len == 0 {
849 return None;
850 }
851 let min_ticks = self.walk_min_deadline();
852 self.min_deadline.set(min_ticks);
853 min_ticks.map(|t| self.ticks_to_instant(t))
854 }
855
856 /// Recomputes the wheel's minimum deadline from the per-slot minima —
857 /// ~one compare per active slot, not one per entry.
858 ///
859 /// The per-slot minima may be stale-low (see `WheelSlot::min_deadline`), so
860 /// the result is a **lower bound**: it may be earlier than the true minimum,
861 /// never later. Callers (`next_deadline`, the poll early-exit) treat it
862 /// conservatively — an under-estimate only ever costs extra work.
863 #[cold]
864 fn walk_min_deadline(&self) -> Option<u64> {
865 // `any` (not `min_ticks != u64::MAX`) is the emptiness test: a real
866 // far-future deadline can saturate to exactly u64::MAX in
867 // `instant_to_ticks`, so the sentinel value is a legitimate minimum.
868 let mut min_ticks = u64::MAX;
869 let mut any = false;
870 let mut lvl_mask = self.active_levels;
871 while lvl_mask != 0 {
872 let lvl_idx = lvl_mask.trailing_zeros() as usize;
873 lvl_mask &= lvl_mask - 1;
874 let level = &self.levels[lvl_idx];
875 let mut slot_mask = level.active_slots();
876 while slot_mask != 0 {
877 let slot_idx = slot_mask.trailing_zeros() as usize;
878 slot_mask &= slot_mask - 1;
879 any = true;
880 min_ticks = min_ticks.min(level.slot(slot_idx).min_deadline());
881 }
882 }
883 any.then_some(min_ticks)
884 }
885
886 /// Test-only **exact** minimum deadline via a full entry walk (ignoring the
887 /// per-slot minima) — the ground truth the lower-bound [`next_deadline`] is
888 /// checked against.
889 #[cfg(test)]
890 fn next_deadline_uncached(&self) -> Option<Instant> {
891 let mut min_ticks: Option<u64> = None;
892 let mut lvl_mask = self.active_levels;
893 while lvl_mask != 0 {
894 let lvl_idx = lvl_mask.trailing_zeros() as usize;
895 lvl_mask &= lvl_mask - 1;
896 let level = &self.levels[lvl_idx];
897 let mut slot_mask = level.active_slots();
898 while slot_mask != 0 {
899 let slot_idx = slot_mask.trailing_zeros() as usize;
900 slot_mask &= slot_mask - 1;
901 let slot = level.slot(slot_idx);
902 let mut entry_ptr = slot.entry_head();
903 while !entry_ptr.is_null() {
904 // SAFETY: entry_ptr is in this slot's DLL
905 let entry = unsafe { entry_ref(entry_ptr) };
906 let dt = entry.deadline_ticks();
907 min_ticks = Some(min_ticks.map_or(dt, |c| c.min(dt)));
908 entry_ptr = entry.next();
909 }
910 }
911 }
912 min_ticks.map(|t| self.ticks_to_instant(t))
913 }
914
915 /// Returns the number of timers currently in the wheel.
916 #[inline]
917 pub fn len(&self) -> usize {
918 self.len
919 }
920
921 /// Returns true if the wheel contains no timers.
922 #[inline]
923 pub fn is_empty(&self) -> bool {
924 self.len == 0
925 }
926
927 // =========================================================================
928 // Internal: tick conversion
929 // =========================================================================
930
931 #[inline]
932 fn instant_to_ticks(&self, instant: Instant) -> u64 {
933 let dur = instant.saturating_duration_since(self.epoch);
934 let nanos = dur.as_nanos().min(u64::MAX as u128) as u64;
935 ((nanos as u128 * self.inv_tick_ns) >> 64) as u64
936 }
937
938 #[inline]
939 fn ticks_to_instant(&self, ticks: u64) -> Instant {
940 self.epoch + Duration::from_nanos(ticks.saturating_mul(self.tick_ns))
941 }
942
943 // =========================================================================
944 // Internal: level selection
945 // =========================================================================
946
947 /// Selects the appropriate level for a deadline.
948 ///
949 /// Walks levels from finest to coarsest, picking the first level whose
950 /// range can represent the delta. Clamps to the highest level if the
951 /// deadline exceeds the wheel's total range.
952 #[inline]
953 fn select_level(&self, deadline_ticks: u64) -> usize {
954 let delta = deadline_ticks.saturating_sub(self.current_ticks);
955
956 for (i, level) in self.levels.iter().enumerate() {
957 if delta < level.range() {
958 return i;
959 }
960 }
961
962 // Beyond max range — clamp to highest level
963 self.num_levels - 1
964 }
965
966 // =========================================================================
967 // Internal: entry insertion into a level's slot
968 // =========================================================================
969
970 /// Inserts an entry into the appropriate level and slot.
971 ///
972 /// Records the level and slot index on the entry so `remove_entry` can
973 /// find it without recomputing (which would be unsound after time advances).
974 #[inline]
975 #[allow(clippy::needless_pass_by_ref_mut)]
976 fn insert_entry(&mut self, entry_ptr: EntryPtr<T>, deadline_ticks: u64) {
977 let lvl_idx = self.select_level(deadline_ticks);
978 let slot_idx = self.levels[lvl_idx].slot_index(deadline_ticks);
979
980 // Record location on the entry for O(1) lookup at cancel time.
981 // SAFETY: entry_ptr is valid (just allocated)
982 let entry = unsafe { entry_ref(entry_ptr) };
983 entry.set_location(lvl_idx as u8, slot_idx as u16);
984
985 // SAFETY: entry_ptr is valid (just allocated), not in any DLL yet
986 unsafe { self.levels[lvl_idx].slot(slot_idx).push_entry(entry_ptr) };
987
988 // Per-slot min: this entry may lower the slot's minimum. (Maintained here,
989 // not in push_entry, so TimeoutQueue's shared slot pays nothing.)
990 {
991 let slot = self.levels[lvl_idx].slot(slot_idx);
992 slot.set_min_deadline(slot.min_deadline().min(deadline_ticks));
993 }
994
995 // Activate slot and level (idempotent — OR is a no-op if already set)
996 self.levels[lvl_idx].activate_slot(slot_idx);
997 self.active_levels |= 1 << lvl_idx;
998
999 // Cache: new entry may lower the minimum.
1000 // len is incremented by the caller AFTER insert_entry returns,
1001 // so self.len == 0 means the wheel was empty before this insert.
1002 match self.min_deadline.get() {
1003 None if self.len == 0 => {
1004 self.min_deadline.set(Some(deadline_ticks));
1005 }
1006 Some(cur) if deadline_ticks < cur => {
1007 self.min_deadline.set(Some(deadline_ticks));
1008 }
1009 _ => {}
1010 }
1011 }
1012
1013 /// Removes an entry from its level's slot DLL.
1014 ///
1015 /// Reads the stored level and slot index from the entry (set at insertion
1016 /// time). Does NOT recompute from delta — that would be unsound after
1017 /// `current_ticks` advances.
1018 #[inline]
1019 #[allow(clippy::needless_pass_by_ref_mut)]
1020 fn remove_entry(&mut self, entry_ptr: EntryPtr<T>) {
1021 // SAFETY: entry_ptr is valid (caller guarantee)
1022 let entry = unsafe { entry_ref(entry_ptr) };
1023
1024 let lvl_idx = entry.level() as usize;
1025 let slot_idx = entry.slot_idx() as usize;
1026
1027 // SAFETY: entry_ptr is in this slot's DLL (invariant from insert_entry)
1028 unsafe { self.levels[lvl_idx].slot(slot_idx).remove_entry(entry_ptr) };
1029
1030 if self.levels[lvl_idx].slot(slot_idx).is_empty() {
1031 // Drained: reset the slot min so an empty slot never reports a
1032 // stale-low deadline. A non-empty slot is left stale-low on purpose
1033 // (safe — see WheelSlot::min_deadline).
1034 self.levels[lvl_idx]
1035 .slot(slot_idx)
1036 .set_min_deadline(u64::MAX);
1037 self.levels[lvl_idx].deactivate_slot(slot_idx);
1038 if !self.levels[lvl_idx].is_active() {
1039 self.active_levels &= !(1 << lvl_idx);
1040 }
1041 }
1042 }
1043
1044 // =========================================================================
1045 // Internal: fire an entry
1046 // =========================================================================
1047
1048 /// Fires a single entry: extracts value, decrements refcount, possibly frees.
1049 ///
1050 /// Returns `Some(T)` if the value was still present (not already cancelled).
1051 #[inline]
1052 fn fire_entry(&mut self, entry_ptr: EntryPtr<T>) -> Option<T> {
1053 // SAFETY: entry_ptr is valid (we're walking the DLL)
1054 let entry = unsafe { entry_ref(entry_ptr) };
1055
1056 let fired_deadline = entry.deadline_ticks();
1057
1058 // Extract value
1059 // SAFETY: single-threaded
1060 let value = unsafe { entry.take_value() };
1061
1062 let new_refs = entry.dec_refs();
1063 if new_refs == 0 {
1064 // Fire-and-forget (was refs=1) — free the slab entry immediately
1065 // SAFETY: entry_ptr was allocated from our slab via into_raw()
1066 self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
1067 }
1068 // new_refs == 1: handle exists (was refs=2), entry becomes zombie.
1069 // Handle holder will free via cancel() or free().
1070
1071 self.len -= 1;
1072
1073 if self.len == 0 {
1074 self.min_deadline.set(None);
1075 } else if let Some(cur) = self.min_deadline.get()
1076 && fired_deadline == cur
1077 {
1078 self.min_deadline.set(None);
1079 }
1080
1081 value
1082 }
1083
1084 // =========================================================================
1085 // Internal: poll a single level
1086 // =========================================================================
1087
1088 /// Polls a single level for expired entries up to `limit`.
1089 ///
1090 fn poll_level(
1091 &mut self,
1092 lvl_idx: usize,
1093 now_ticks: u64,
1094 limit: usize,
1095 rebalance_budget: usize,
1096 rebalances: &mut usize,
1097 buf: &mut Vec<T>,
1098 ) -> usize {
1099 let mut fired = 0;
1100 let mut mask = self.levels[lvl_idx].active_slots();
1101
1102 while mask != 0 && fired < limit {
1103 let slot_idx = mask.trailing_zeros() as usize;
1104 mask &= mask - 1;
1105
1106 let slot_ptr = self.levels[lvl_idx].slot(slot_idx) as *const crate::level::WheelSlot<T>;
1107 // SAFETY: slot_ptr points into self.levels[lvl_idx].slots
1108 // (Box<[WheelSlot<T>]>), a stable heap allocation never reallocated
1109 // during poll. fire_entry and insert_entry mutate self.slab, self.len,
1110 // self.active_levels, self.min_deadline, and *other* levels' slots —
1111 // rebalancing relocates only to strictly finer levels (< lvl_idx), never
1112 // this slot — so this slot's backing memory is untouched and `slot`
1113 // stays valid across the loop.
1114 let slot = unsafe { &*slot_ptr };
1115
1116 // Slot-skip: if the slot's minimum deadline is beyond now, nothing
1117 // in it is due — do not touch a single entry. Stale-low is safe: it
1118 // only costs an unnecessary walk (handled below), never a skip.
1119 if slot.min_deadline() > now_ticks {
1120 continue;
1121 }
1122
1123 let mut new_min = u64::MAX; // min over entries that stay in this slot
1124 let mut entry_ptr = slot.entry_head();
1125
1126 while !entry_ptr.is_null() && fired < limit {
1127 // SAFETY: entry_ptr is in this slot's DLL
1128 let entry = unsafe { entry_ref(entry_ptr) };
1129 let next_entry = entry.next(); // captured before any unlink below
1130 let dt = entry.deadline_ticks();
1131
1132 if dt <= now_ticks {
1133 // Due — fire it.
1134 // SAFETY: entry_ptr is in this slot's DLL (from entry_head,
1135 // walked via next pointers within the same slot).
1136 unsafe { slot.remove_entry(entry_ptr) };
1137 if let Some(value) = self.fire_entry(entry_ptr) {
1138 buf.push(value);
1139 }
1140 fired += 1;
1141 } else if *rebalances < rebalance_budget && self.select_level(dt) < lvl_idx {
1142 // Not due, it now belongs at a strictly finer level, and we are
1143 // still under the per-poll rebalance budget: relocate it down
1144 // instead of re-walking it every poll until this slot's span
1145 // passes. The target (< lvl_idx) is never this slot, so the walk
1146 // terminates and the entry is not re-processed this poll (finer
1147 // levels are polled first). current_ticks == now_ticks (set in
1148 // poll_inner before this loop), so insert_entry selects the
1149 // correct finer level.
1150 // SAFETY: entry_ptr is in this slot's DLL.
1151 unsafe { slot.remove_entry(entry_ptr) };
1152 self.insert_entry(entry_ptr, dt);
1153 *rebalances += 1;
1154 } else {
1155 // Not due, and left in place — either it still belongs at this
1156 // level (a far entry sharing the slot via the modular index:
1157 // deadlines a full level-range apart map to the same slot), or
1158 // the per-poll rebalance budget is spent. Either way it stays put
1159 // and fires (or rebalances) on a later poll from wherever it sits;
1160 // track it as the slot's surviving minimum. A spent budget can
1161 // never make a timer fire late — poll still fires it the moment
1162 // dt <= now, regardless of which level it is in.
1163 new_min = new_min.min(dt);
1164 }
1165
1166 entry_ptr = next_entry;
1167 }
1168
1169 // If we walked the whole slot, its minimum is exactly the min over the
1170 // entries that stayed (u64::MAX — the empty sentinel — when the slot
1171 // drained via fires + rebalances). A limit-truncated walk (entry_ptr
1172 // non-null) leaves the min stale-low; the next poll re-walks and heals.
1173 if entry_ptr.is_null() {
1174 slot.set_min_deadline(new_min);
1175 }
1176
1177 if slot.is_empty() {
1178 self.levels[lvl_idx].deactivate_slot(slot_idx);
1179 }
1180 }
1181
1182 // Deactivate level if all slots drained
1183 if !self.levels[lvl_idx].is_active() {
1184 self.active_levels &= !(1 << lvl_idx);
1185 }
1186
1187 fired
1188 }
1189
1190 /// Proactively pulls not-yet-due entries at `lvl_idx` down to a finer level.
1191 /// Visits only active slots whose earliest entry has reached `finer_reach`
1192 /// (is within the next-finer level's range) and relocates each entry that now
1193 /// belongs at a strictly finer level, up to `limit`. Returns how many moved.
1194 /// Fires nothing.
1195 fn rebalance_level(&mut self, lvl_idx: usize, finer_reach: u64, limit: usize) -> usize {
1196 let mut moved = 0;
1197 let mut mask = self.levels[lvl_idx].active_slots();
1198
1199 while mask != 0 && moved < limit {
1200 let slot_idx = mask.trailing_zeros() as usize;
1201 mask &= mask - 1;
1202
1203 let slot_ptr = self.levels[lvl_idx].slot(slot_idx) as *const crate::level::WheelSlot<T>;
1204 // SAFETY: same argument as poll_level — slot_ptr points into the
1205 // stable Box<[WheelSlot<T>]>; insert_entry only ever relocates to a
1206 // strictly finer level (< lvl_idx), never this slot, so `slot` stays
1207 // valid across the loop.
1208 let slot = unsafe { &*slot_ptr };
1209
1210 // Nothing to pull down yet if the earliest entry hasn't reached the
1211 // finer level's window.
1212 if slot.min_deadline() >= finer_reach {
1213 continue;
1214 }
1215
1216 let mut new_min = u64::MAX;
1217 let mut entry_ptr = slot.entry_head();
1218
1219 while !entry_ptr.is_null() && moved < limit {
1220 // SAFETY: entry_ptr is in this slot's DLL.
1221 let entry = unsafe { entry_ref(entry_ptr) };
1222 let next_entry = entry.next();
1223 let dt = entry.deadline_ticks();
1224
1225 if self.select_level(dt) < lvl_idx {
1226 // SAFETY: entry_ptr is in this slot's DLL.
1227 unsafe { slot.remove_entry(entry_ptr) };
1228 self.insert_entry(entry_ptr, dt);
1229 moved += 1;
1230 } else {
1231 // Still belongs at this level (modular-index neighbor a full
1232 // range away, or budget-truncated). Leave it; track its min.
1233 new_min = new_min.min(dt);
1234 }
1235
1236 entry_ptr = next_entry;
1237 }
1238
1239 // Fully-walked slot: its min is exactly the min over entries that
1240 // stayed. A limit-truncated walk (entry_ptr non-null) leaves it
1241 // stale-low; the next rebalance/poll re-walks and heals it.
1242 if entry_ptr.is_null() {
1243 slot.set_min_deadline(new_min);
1244 }
1245
1246 if slot.is_empty() {
1247 self.levels[lvl_idx].deactivate_slot(slot_idx);
1248 }
1249 }
1250
1251 moved
1252 }
1253}
1254
1255// =============================================================================
1256// Drop
1257// =============================================================================
1258
1259impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> Drop for TimerWheel<T, S> {
1260 fn drop(&mut self) {
1261 // Walk active levels and slots via bitmasks, free every entry.
1262 let mut lvl_mask = self.active_levels;
1263 while lvl_mask != 0 {
1264 let lvl_idx = lvl_mask.trailing_zeros() as usize;
1265 lvl_mask &= lvl_mask - 1;
1266
1267 let level = &self.levels[lvl_idx];
1268 let mut slot_mask = level.active_slots();
1269 while slot_mask != 0 {
1270 let slot_idx = slot_mask.trailing_zeros() as usize;
1271 slot_mask &= slot_mask - 1;
1272
1273 let slot = level.slot(slot_idx);
1274 let mut entry_ptr = slot.entry_head();
1275 while !entry_ptr.is_null() {
1276 // SAFETY: entry_ptr is in this slot's DLL
1277 let entry = unsafe { entry_ref(entry_ptr) };
1278 let next_entry = entry.next();
1279
1280 // SAFETY: entry_ptr was allocated from our slab via into_raw()
1281 self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
1282
1283 entry_ptr = next_entry;
1284 }
1285 }
1286 }
1287 }
1288}
1289
1290// =============================================================================
1291// Tests
1292// =============================================================================
1293
1294#[cfg(test)]
1295mod tests {
1296 use super::*;
1297 use std::time::{Duration, Instant};
1298
1299 fn ms(millis: u64) -> Duration {
1300 Duration::from_millis(millis)
1301 }
1302
1303 // -------------------------------------------------------------------------
1304 // Thread safety
1305 // -------------------------------------------------------------------------
1306
1307 fn assert_send<T: Send>() {}
1308
1309 #[test]
1310 fn wheel_is_send() {
1311 assert_send::<Wheel<u64>>();
1312 assert_send::<BoundedWheel<u64>>();
1313 }
1314
1315 // -------------------------------------------------------------------------
1316 // Construction
1317 // -------------------------------------------------------------------------
1318
1319 #[test]
1320 fn default_config() {
1321 let now = Instant::now();
1322 let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1323 assert!(wheel.is_empty());
1324 assert_eq!(wheel.len(), 0);
1325 }
1326
1327 #[test]
1328 fn bounded_construction() {
1329 let now = Instant::now();
1330 let wheel: BoundedWheel<u64> = BoundedWheel::bounded(128, now);
1331 assert!(wheel.is_empty());
1332 }
1333
1334 #[test]
1335 fn invalid_config_non_power_of_two() {
1336 let now = Instant::now();
1337 let result = WheelBuilder::default()
1338 .slots_per_level(65)
1339 .unbounded(1024)
1340 .build::<u64>(now);
1341 assert_invalid(&result, "power of 2");
1342 }
1343
1344 // -------------------------------------------------------------------------
1345 // Schedule + Cancel
1346 // -------------------------------------------------------------------------
1347
1348 #[test]
1349 fn schedule_and_cancel() {
1350 let now = Instant::now();
1351 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1352
1353 let h = wheel.schedule(now + ms(50), 42);
1354 assert_eq!(wheel.len(), 1);
1355
1356 let val = wheel.cancel(h);
1357 assert_eq!(val, Some(42));
1358 assert_eq!(wheel.len(), 0);
1359 }
1360
1361 #[test]
1362 fn schedule_forget_fires() {
1363 let now = Instant::now();
1364 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1365
1366 wheel.schedule_forget(now + ms(10), 99);
1367 assert_eq!(wheel.len(), 1);
1368
1369 let mut buf = Vec::new();
1370 let fired = wheel.poll(now + ms(20), &mut buf);
1371 assert_eq!(fired, 1);
1372 assert_eq!(buf, vec![99]);
1373 assert_eq!(wheel.len(), 0);
1374 }
1375
1376 #[test]
1377 fn cancel_after_fire_returns_none() {
1378 let now = Instant::now();
1379 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1380
1381 let h = wheel.schedule(now + ms(10), 42);
1382
1383 let mut buf = Vec::new();
1384 wheel.poll(now + ms(20), &mut buf);
1385 assert_eq!(buf, vec![42]);
1386
1387 // Handle is now a zombie
1388 let val = wheel.cancel(h);
1389 assert_eq!(val, None);
1390 }
1391
1392 #[test]
1393 fn free_active_timer_becomes_fire_and_forget() {
1394 let now = Instant::now();
1395 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1396
1397 let h = wheel.schedule(now + ms(10), 42);
1398 wheel.free(h); // releases handle, timer stays
1399 assert_eq!(wheel.len(), 1);
1400
1401 let mut buf = Vec::new();
1402 wheel.poll(now + ms(20), &mut buf);
1403 assert_eq!(buf, vec![42]);
1404 assert_eq!(wheel.len(), 0);
1405 }
1406
1407 #[test]
1408 fn free_zombie_handle() {
1409 let now = Instant::now();
1410 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1411
1412 let h = wheel.schedule(now + ms(10), 42);
1413
1414 let mut buf = Vec::new();
1415 wheel.poll(now + ms(20), &mut buf);
1416
1417 // Handle is zombie, free should clean up
1418 wheel.free(h);
1419 }
1420
1421 // -------------------------------------------------------------------------
1422 // Bounded wheel
1423 // -------------------------------------------------------------------------
1424
1425 #[test]
1426 fn bounded_full() {
1427 let now = Instant::now();
1428 let mut wheel: BoundedWheel<u64> = BoundedWheel::bounded(2, now);
1429
1430 let h1 = wheel.try_schedule(now + ms(10), 1).unwrap();
1431 let h2 = wheel.try_schedule(now + ms(20), 2).unwrap();
1432
1433 let err = wheel.try_schedule(now + ms(30), 3);
1434 assert!(err.is_err());
1435 let recovered = err.unwrap_err().into_inner();
1436 assert_eq!(recovered, 3);
1437
1438 // Cancel one, should have room
1439 wheel.cancel(h1);
1440 let h3 = wheel.try_schedule(now + ms(30), 3).unwrap();
1441
1442 // Clean up handles
1443 wheel.free(h2);
1444 wheel.free(h3);
1445 }
1446
1447 #[test]
1448 fn bounded_schedule_forget_full() {
1449 let now = Instant::now();
1450 let mut wheel: BoundedWheel<u64> = BoundedWheel::bounded(1, now);
1451
1452 wheel.try_schedule_forget(now + ms(10), 1).unwrap();
1453 let err = wheel.try_schedule_forget(now + ms(20), 2);
1454 assert!(err.is_err());
1455 }
1456
1457 // -------------------------------------------------------------------------
1458 // Poll
1459 // -------------------------------------------------------------------------
1460
1461 #[test]
1462 fn poll_respects_deadline() {
1463 let now = Instant::now();
1464 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1465
1466 wheel.schedule_forget(now + ms(10), 1);
1467 wheel.schedule_forget(now + ms(50), 2);
1468 wheel.schedule_forget(now + ms(100), 3);
1469
1470 let mut buf = Vec::new();
1471
1472 // At 20ms: only timer 1 should fire
1473 let fired = wheel.poll(now + ms(20), &mut buf);
1474 assert_eq!(fired, 1);
1475 assert_eq!(buf, vec![1]);
1476 assert_eq!(wheel.len(), 2);
1477
1478 // At 60ms: timer 2 fires
1479 buf.clear();
1480 let fired = wheel.poll(now + ms(60), &mut buf);
1481 assert_eq!(fired, 1);
1482 assert_eq!(buf, vec![2]);
1483
1484 // At 200ms: timer 3 fires
1485 buf.clear();
1486 let fired = wheel.poll(now + ms(200), &mut buf);
1487 assert_eq!(fired, 1);
1488 assert_eq!(buf, vec![3]);
1489
1490 assert!(wheel.is_empty());
1491 }
1492
1493 #[test]
1494 fn poll_with_limit() {
1495 let now = Instant::now();
1496 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1497
1498 for i in 0..10 {
1499 wheel.schedule_forget(now + ms(1), i);
1500 }
1501
1502 let mut buf = Vec::new();
1503
1504 // Fire 3 at a time
1505 let fired = wheel.poll_with_limit(now + ms(5), 3, &mut buf);
1506 assert_eq!(fired, 3);
1507 assert_eq!(wheel.len(), 7);
1508
1509 let fired = wheel.poll_with_limit(now + ms(5), 3, &mut buf);
1510 assert_eq!(fired, 3);
1511 assert_eq!(wheel.len(), 4);
1512
1513 // Fire remaining
1514 let fired = wheel.poll(now + ms(5), &mut buf);
1515 assert_eq!(fired, 4);
1516 assert!(wheel.is_empty());
1517 assert_eq!(buf.len(), 10);
1518 }
1519
1520 // -------------------------------------------------------------------------
1521 // Multi-level
1522 // -------------------------------------------------------------------------
1523
1524 #[test]
1525 fn timers_across_levels() {
1526 let now = Instant::now();
1527 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1528
1529 // Level 0: 0-63ms
1530 wheel.schedule_forget(now + ms(5), 0);
1531 // Level 1: 64-511ms
1532 wheel.schedule_forget(now + ms(200), 1);
1533 // Level 2: 512-4095ms
1534 wheel.schedule_forget(now + ms(1000), 2);
1535
1536 let mut buf = Vec::new();
1537
1538 wheel.poll(now + ms(10), &mut buf);
1539 assert_eq!(buf, vec![0]);
1540
1541 buf.clear();
1542 wheel.poll(now + ms(250), &mut buf);
1543 assert_eq!(buf, vec![1]);
1544
1545 buf.clear();
1546 wheel.poll(now + ms(1500), &mut buf);
1547 assert_eq!(buf, vec![2]);
1548
1549 assert!(wheel.is_empty());
1550 }
1551
1552 // -------------------------------------------------------------------------
1553 // next_deadline
1554 // -------------------------------------------------------------------------
1555
1556 #[test]
1557 fn next_deadline_empty() {
1558 let now = Instant::now();
1559 let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1560 assert!(wheel.next_deadline().is_none());
1561 }
1562
1563 #[test]
1564 fn next_deadline_returns_earliest() {
1565 let now = Instant::now();
1566 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1567
1568 wheel.schedule_forget(now + ms(100), 1);
1569 wheel.schedule_forget(now + ms(50), 2);
1570 wheel.schedule_forget(now + ms(200), 3);
1571
1572 let next = wheel.next_deadline().unwrap();
1573 // Should be close to now + 50ms (within tick granularity)
1574 let delta = next.duration_since(now);
1575 assert!(delta >= ms(49) && delta <= ms(51));
1576 }
1577
1578 #[test]
1579 fn next_deadline_cache_invalidates_on_cancel() {
1580 let now = Instant::now();
1581 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1582
1583 let h1 = wheel.schedule(now + ms(50), 1);
1584 wheel.schedule_forget(now + ms(100), 2);
1585 wheel.schedule_forget(now + ms(200), 3);
1586
1587 // Cached at 50ms
1588 let d1 = wheel.next_deadline().unwrap();
1589 assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1590
1591 // Cancel the earliest — cache invalidated, should return ~100ms
1592 wheel.cancel(h1);
1593 let d2 = wheel.next_deadline().unwrap();
1594 assert!(d2.duration_since(now) >= ms(99) && d2.duration_since(now) <= ms(101));
1595 }
1596
1597 #[test]
1598 fn next_deadline_cache_invalidates_on_fire() {
1599 let now = Instant::now();
1600 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1601
1602 wheel.schedule_forget(now + ms(50), 1);
1603 wheel.schedule_forget(now + ms(100), 2);
1604 wheel.schedule_forget(now + ms(200), 3);
1605
1606 // Prime cache
1607 let _ = wheel.next_deadline();
1608
1609 // Fire earliest via poll
1610 let mut buf = Vec::new();
1611 wheel.poll(now + ms(60), &mut buf);
1612 assert_eq!(buf, vec![1]);
1613
1614 // Cache invalidated, should return ~100ms
1615 let d = wheel.next_deadline().unwrap();
1616 assert!(d.duration_since(now) >= ms(99) && d.duration_since(now) <= ms(101));
1617 }
1618
1619 #[test]
1620 fn next_deadline_cache_updates_on_insert() {
1621 let now = Instant::now();
1622 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1623
1624 wheel.schedule_forget(now + ms(100), 1);
1625 let d1 = wheel.next_deadline().unwrap();
1626 assert!(d1.duration_since(now) >= ms(99) && d1.duration_since(now) <= ms(101));
1627
1628 // Insert an earlier timer — cache should update
1629 wheel.schedule_forget(now + ms(30), 2);
1630 let d2 = wheel.next_deadline().unwrap();
1631 assert!(d2.duration_since(now) >= ms(29) && d2.duration_since(now) <= ms(31));
1632 }
1633
1634 #[test]
1635 fn next_deadline_after_reschedule_later() {
1636 let now = Instant::now();
1637 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1638
1639 let h_a = wheel.schedule(now + ms(50), 1);
1640 wheel.schedule_forget(now + ms(100), 2);
1641
1642 let d1 = wheel.next_deadline().unwrap();
1643 assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1644
1645 // Reschedule A later — B becomes earliest
1646 let h_a = wheel.reschedule(h_a, now + ms(200));
1647 let d2 = wheel.next_deadline().unwrap();
1648 assert!(d2.duration_since(now) >= ms(99) && d2.duration_since(now) <= ms(101));
1649 mem::forget(h_a);
1650 }
1651
1652 #[test]
1653 fn next_deadline_after_reschedule_earlier() {
1654 let now = Instant::now();
1655 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1656
1657 let h_a = wheel.schedule(now + ms(100), 1);
1658 wheel.schedule_forget(now + ms(50), 2);
1659
1660 let d1 = wheel.next_deadline().unwrap();
1661 assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1662
1663 // Reschedule A earlier — A becomes new earliest
1664 let h_a = wheel.reschedule(h_a, now + ms(25));
1665 let d2 = wheel.next_deadline().unwrap();
1666 assert!(d2.duration_since(now) >= ms(24) && d2.duration_since(now) <= ms(26));
1667 mem::forget(h_a);
1668 }
1669
1670 #[test]
1671 fn next_deadline_repeated_calls_stable() {
1672 let now = Instant::now();
1673 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1674
1675 wheel.schedule_forget(now + ms(50), 1);
1676 wheel.schedule_forget(now + ms(100), 2);
1677 wheel.schedule_forget(now + ms(200), 3);
1678
1679 let d1 = wheel.next_deadline();
1680 let d2 = wheel.next_deadline();
1681 let d3 = wheel.next_deadline();
1682 assert_eq!(d1, d2);
1683 assert_eq!(d2, d3);
1684 }
1685
1686 // -------------------------------------------------------------------------
1687 // Reciprocal precision
1688 // -------------------------------------------------------------------------
1689
1690 #[test]
1691 fn reciprocal_instant_to_ticks_precision() {
1692 // Reciprocal multiply is at most 1 tick low vs true integer division.
1693 // Verify across multiple tick_ns values and multiples.
1694 let now = Instant::now();
1695
1696 for &tick_ns in &[1_000_000u64, 1_000, 100, 999_999, 7_500_000] {
1697 let wheel: Wheel<u64> = WheelBuilder::default()
1698 .tick_duration(Duration::from_nanos(tick_ns))
1699 .unbounded(64)
1700 .build(now)
1701 .unwrap();
1702
1703 for n in 0..500u64 {
1704 let nanos = n * tick_ns;
1705 let instant = now + Duration::from_nanos(nanos);
1706 let got = wheel.instant_to_ticks(instant);
1707 let exact = nanos / tick_ns;
1708 let diff = exact as i64 - got as i64;
1709 assert!(
1710 diff >= 0 && diff <= 1,
1711 "tick_ns={tick_ns}, n={n}: exact={exact}, got={got}, diff={diff}",
1712 );
1713 }
1714 }
1715 }
1716
1717 // -------------------------------------------------------------------------
1718 // Deadline in the past
1719 // -------------------------------------------------------------------------
1720
1721 #[test]
1722 fn deadline_in_the_past_fires_immediately() {
1723 let now = Instant::now();
1724 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1725
1726 // Schedule at epoch (which is "now" at construction)
1727 wheel.schedule_forget(now, 42);
1728
1729 let mut buf = Vec::new();
1730 let fired = wheel.poll(now + ms(1), &mut buf);
1731 assert_eq!(fired, 1);
1732 assert_eq!(buf, vec![42]);
1733 }
1734
1735 // -------------------------------------------------------------------------
1736 // Deadline beyond max range — clamped
1737 // -------------------------------------------------------------------------
1738
1739 #[test]
1740 fn deadline_beyond_max_range_clamped() {
1741 let now = Instant::now();
1742 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1743
1744 // Way in the future — should clamp to highest level
1745 let h = wheel.schedule(now + Duration::from_secs(100_000), 99);
1746 assert_eq!(wheel.len(), 1);
1747
1748 // Won't fire at any reasonable time but will fire when enough ticks pass
1749 let mut buf = Vec::new();
1750 wheel.poll(now + Duration::from_secs(100_001), &mut buf);
1751 assert_eq!(buf, vec![99]);
1752
1753 // Note: handle was already consumed by the poll (fire-and-forget path won't
1754 // apply since refs=2). Actually the handle still exists. Let's clean up.
1755 // The timer already fired, so cancel returns None.
1756 // Actually buf got the value, which means it fired. But handle still needs cleanup.
1757 // We already pushed the value so we need to handle the zombie.
1758 // Wait — we used schedule (refs=2), poll fired it (refs 2→1 zombie), handle `h` exists.
1759 // Actually we consumed it with the poll — no we didn't, we still have `h`.
1760
1761 // h is a zombie handle now
1762 let val = wheel.cancel(h);
1763 assert_eq!(val, None);
1764 }
1765
1766 // -------------------------------------------------------------------------
1767 // Drop
1768 // -------------------------------------------------------------------------
1769
1770 #[test]
1771 fn drop_cleans_up_active_entries() {
1772 let now = Instant::now();
1773 let mut wheel: Wheel<String> = Wheel::unbounded(1024, now);
1774
1775 for i in 0..100 {
1776 wheel.schedule_forget(now + ms(i * 10), format!("timer-{i}"));
1777 }
1778
1779 assert_eq!(wheel.len(), 100);
1780 // Drop should free all entries without leaking
1781 drop(wheel);
1782 }
1783
1784 #[test]
1785 fn drop_with_outstanding_handles() {
1786 let now = Instant::now();
1787 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1788
1789 // Schedule but DON'T cancel — just free the handles
1790 let h1 = wheel.schedule(now + ms(10), 1);
1791 let h2 = wheel.schedule(now + ms(20), 2);
1792
1793 // Free the handles (convert to fire-and-forget) so they don't debug_assert
1794 wheel.free(h1);
1795 wheel.free(h2);
1796
1797 // Drop the wheel — should clean up the entries
1798 drop(wheel);
1799 }
1800
1801 // -------------------------------------------------------------------------
1802 // Level selection
1803 // -------------------------------------------------------------------------
1804
1805 #[test]
1806 fn level_selection_boundaries() {
1807 let now = Instant::now();
1808 let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1809
1810 // Level 0: delta < 64
1811 assert_eq!(wheel.select_level(0), 0);
1812 assert_eq!(wheel.select_level(63), 0);
1813
1814 // Level 1: 64 <= delta < 512
1815 assert_eq!(wheel.select_level(64), 1);
1816 assert_eq!(wheel.select_level(511), 1);
1817
1818 // Level 2: 512 <= delta < 4096
1819 assert_eq!(wheel.select_level(512), 2);
1820 }
1821
1822 // -------------------------------------------------------------------------
1823 // Bug fix validation: cancel after time advance
1824 // -------------------------------------------------------------------------
1825
1826 #[test]
1827 fn cancel_after_time_advance() {
1828 // The critical bug: schedule at T+500ms (level 2, delta=500 ticks),
1829 // poll at T+400ms (no fire, but current_ticks advances to 400),
1830 // cancel at T+400ms. Old code would recompute delta = 500-400 = 100
1831 // → level 1. But the entry is in level 2. Stored location fixes this.
1832 let now = Instant::now();
1833 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1834
1835 let h = wheel.schedule(now + ms(500), 42);
1836 assert_eq!(wheel.len(), 1);
1837
1838 // Advance time — timer doesn't fire (deadline is 500ms)
1839 let mut buf = Vec::new();
1840 let fired = wheel.poll(now + ms(400), &mut buf);
1841 assert_eq!(fired, 0);
1842 assert!(buf.is_empty());
1843
1844 // Cancel after time advance — must find the entry in the correct slot
1845 let val = wheel.cancel(h);
1846 assert_eq!(val, Some(42));
1847 assert_eq!(wheel.len(), 0);
1848 }
1849
1850 // -------------------------------------------------------------------------
1851 // Per-slot min: stale-low safety
1852 // -------------------------------------------------------------------------
1853
1854 #[test]
1855 fn slot_min_stale_low_after_cancel_still_fires() {
1856 // Cancelling the earliest entry in a non-empty slot leaves that slot's
1857 // cached min stale-low (the per-slot minima are not recomputed on
1858 // remove). Poll must still fire the SURVIVORS at the right times — never
1859 // skip a due entry, never fire an early one.
1860 let now = Instant::now();
1861 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1862
1863 // 3000 / 3001 / 3002 ms all land in the same level-2 slot.
1864 let h0 = wheel.schedule(now + ms(3000), 0);
1865 wheel.schedule_forget(now + ms(3001), 1);
1866 wheel.schedule_forget(now + ms(3002), 2);
1867
1868 // Cancel the earliest — the slot min now points at 3000 (gone): stale-low.
1869 assert_eq!(wheel.cancel(h0), Some(0));
1870
1871 let mut buf = Vec::new();
1872 assert_eq!(wheel.poll(now + ms(3000), &mut buf), 0, "nothing due yet");
1873 assert!(buf.is_empty());
1874
1875 let fired = wheel.poll(now + ms(3002), &mut buf);
1876 assert_eq!(fired, 2, "both survivors fire once due");
1877 buf.sort_unstable();
1878 assert_eq!(buf, vec![1, 2]);
1879 }
1880
1881 #[test]
1882 fn slot_min_resets_on_drain_and_reinsert() {
1883 // A drained slot resets its min to u64::MAX; a later insert must set the
1884 // min fresh, not inherit a stale value.
1885 let now = Instant::now();
1886 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1887
1888 wheel.schedule_forget(now + ms(3000), 0);
1889 let mut buf = Vec::new();
1890 assert_eq!(wheel.poll(now + ms(3000), &mut buf), 1);
1891 assert!(wheel.is_empty());
1892 assert!(wheel.next_deadline().is_none());
1893
1894 // Re-insert (likely into the same drained slot).
1895 wheel.schedule_forget(now + ms(3000), 1);
1896 let nd = wheel.next_deadline().expect("non-empty");
1897 assert!(nd <= now + ms(3000)); // lower bound — never later than the true deadline
1898 buf.clear();
1899 assert_eq!(wheel.poll(now + ms(2999), &mut buf), 0);
1900 assert_eq!(wheel.poll(now + ms(3000), &mut buf), 1);
1901 }
1902
1903 #[test]
1904 fn poll_refreshes_stale_low_cache() {
1905 // Cancelling the slot-min entry leaves the slot min — and, once read, the
1906 // global cache — stale-low, pointing at the cancelled deadline. A poll
1907 // that finds nothing due must refresh the cache off that stale value;
1908 // otherwise it stays <= now forever, defeating the early-exit and making
1909 // next_deadline() report a past instant.
1910 let now = Instant::now();
1911 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1912
1913 // 3000 / 3002 ms share a slot. Cancel the earlier one.
1914 let h0 = wheel.schedule(now + ms(3000), 0);
1915 wheel.schedule_forget(now + ms(3002), 1);
1916 assert_eq!(wheel.cancel(h0), Some(0));
1917
1918 // Populate the (now stale-low) cache: it points at the cancelled 3000.
1919 let stale = wheel.next_deadline().expect("non-empty");
1920 assert!(stale <= now + ms(3000));
1921
1922 // Poll past 3000 but before 3002 — nothing fires; the slot heals to 3002
1923 // and the cache is refreshed at the end of the poll.
1924 let mut buf = Vec::new();
1925 assert_eq!(wheel.poll(now + ms(3001), &mut buf), 0);
1926
1927 // Regression: without the poll-end refresh this would still be the
1928 // cancelled ~3000 (in the past). It must now reflect the survivor —
1929 // compared against the captured stale value so tick-rounding is irrelevant.
1930 let refreshed = wheel.next_deadline().expect("non-empty");
1931 assert!(
1932 refreshed > stale,
1933 "cache must refresh past the stale-low value after a no-fire poll",
1934 );
1935 }
1936
1937 // -------------------------------------------------------------------------
1938 // Same-slot entries
1939 // -------------------------------------------------------------------------
1940
1941 #[test]
1942 fn multiple_entries_same_slot() {
1943 let now = Instant::now();
1944 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1945
1946 // All 5 timers at the same deadline → same slot
1947 let mut handles = Vec::new();
1948 for i in 0..5 {
1949 handles.push(wheel.schedule(now + ms(10), i));
1950 }
1951 assert_eq!(wheel.len(), 5);
1952
1953 // Cancel the middle ones
1954 let v2 = wheel.cancel(handles.remove(2));
1955 assert_eq!(v2, Some(2));
1956 let v0 = wheel.cancel(handles.remove(0));
1957 assert_eq!(v0, Some(0));
1958 assert_eq!(wheel.len(), 3);
1959
1960 // Poll — remaining 3 should fire
1961 let mut buf = Vec::new();
1962 let fired = wheel.poll(now + ms(20), &mut buf);
1963 assert_eq!(fired, 3);
1964
1965 // Clean up zombie handles
1966 for h in handles {
1967 let val = wheel.cancel(h);
1968 assert_eq!(val, None); // already fired
1969 }
1970 }
1971
1972 // -------------------------------------------------------------------------
1973 // Level boundary
1974 // -------------------------------------------------------------------------
1975
1976 #[test]
1977 fn entry_at_level_boundary() {
1978 // Default config: level 0 range = 64 ticks (64ms).
1979 // A deadline at exactly tick 64 should go to level 1, not level 0.
1980 let now = Instant::now();
1981 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1982
1983 let h = wheel.schedule(now + ms(64), 99);
1984 assert_eq!(wheel.len(), 1);
1985
1986 // Should NOT fire at 63ms
1987 let mut buf = Vec::new();
1988 let fired = wheel.poll(now + ms(63), &mut buf);
1989 assert_eq!(fired, 0);
1990
1991 // Should fire at 64ms
1992 let fired = wheel.poll(now + ms(65), &mut buf);
1993 assert_eq!(fired, 1);
1994 assert_eq!(buf, vec![99]);
1995
1996 // Clean up zombie handle
1997 wheel.cancel(h);
1998 }
1999
2000 // -------------------------------------------------------------------------
2001 // Bookmark/resumption with mixed expiry
2002 // -------------------------------------------------------------------------
2003
2004 #[test]
2005 fn poll_with_limit_mixed_expiry() {
2006 let now = Instant::now();
2007 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2008
2009 // 3 expired at poll time, 2 not
2010 wheel.schedule_forget(now + ms(5), 1);
2011 wheel.schedule_forget(now + ms(5), 2);
2012 wheel.schedule_forget(now + ms(5), 3);
2013 wheel.schedule_forget(now + ms(500), 4); // not expired
2014 wheel.schedule_forget(now + ms(500), 5); // not expired
2015 assert_eq!(wheel.len(), 5);
2016
2017 let mut buf = Vec::new();
2018
2019 // Fire 2 of the 3 expired
2020 let fired = wheel.poll_with_limit(now + ms(10), 2, &mut buf);
2021 assert_eq!(fired, 2);
2022 assert_eq!(wheel.len(), 3);
2023
2024 // Fire remaining expired (1 more)
2025 let fired = wheel.poll_with_limit(now + ms(10), 5, &mut buf);
2026 assert_eq!(fired, 1);
2027 assert_eq!(wheel.len(), 2);
2028
2029 // The 2 unexpired should still be there
2030 assert_eq!(buf.len(), 3);
2031 }
2032
2033 // -------------------------------------------------------------------------
2034 // Re-add after drain
2035 // -------------------------------------------------------------------------
2036
2037 #[test]
2038 fn reuse_after_full_drain() {
2039 let now = Instant::now();
2040 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2041
2042 // Round 1: schedule and drain
2043 for i in 0..10 {
2044 wheel.schedule_forget(now + ms(1), i);
2045 }
2046 let mut buf = Vec::new();
2047 wheel.poll(now + ms(5), &mut buf);
2048 assert_eq!(buf.len(), 10);
2049 assert!(wheel.is_empty());
2050
2051 // Round 2: schedule and drain again — wheel must work normally
2052 buf.clear();
2053 for i in 10..20 {
2054 wheel.schedule_forget(now + ms(100), i);
2055 }
2056 assert_eq!(wheel.len(), 10);
2057
2058 wheel.poll(now + ms(200), &mut buf);
2059 assert_eq!(buf.len(), 10);
2060 assert!(wheel.is_empty());
2061 }
2062
2063 // -------------------------------------------------------------------------
2064 // All levels active simultaneously
2065 // -------------------------------------------------------------------------
2066
2067 #[test]
2068 fn all_levels_active() {
2069 let now = Instant::now();
2070 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2071
2072 // Schedule one timer per level with increasing distances.
2073 // Level 0: <64ms, Level 1: 64-511ms, Level 2: 512-4095ms, etc.
2074 let distances = [10, 100, 1000, 5000, 40_000, 300_000, 3_000_000];
2075 let mut handles: Vec<TimerHandle<u64>> = Vec::new();
2076 for (i, &d) in distances.iter().enumerate() {
2077 handles.push(wheel.schedule(now + ms(d), i as u64));
2078 }
2079 assert_eq!(wheel.len(), 7);
2080
2081 // Cancel in a shuffled order: 4, 1, 6, 0, 3, 5, 2
2082 let order = [4, 1, 6, 0, 3, 5, 2];
2083 // Take ownership by swapping with dummies — actually we need to
2084 // cancel by index. Let's use Option to track.
2085 let mut opt_handles: Vec<Option<TimerHandle<u64>>> =
2086 handles.into_iter().map(Some).collect();
2087
2088 for &idx in &order {
2089 let h = opt_handles[idx].take().unwrap();
2090 let val = wheel.cancel(h);
2091 assert_eq!(val, Some(idx as u64));
2092 }
2093 assert!(wheel.is_empty());
2094 }
2095
2096 // -------------------------------------------------------------------------
2097 // Poll values match
2098 // -------------------------------------------------------------------------
2099
2100 #[test]
2101 fn poll_values_match() {
2102 let now = Instant::now();
2103 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2104
2105 let expected: Vec<u64> = (100..110).collect();
2106 for &v in &expected {
2107 wheel.schedule_forget(now + ms(5), v);
2108 }
2109
2110 let mut buf = Vec::new();
2111 wheel.poll(now + ms(10), &mut buf);
2112
2113 buf.sort_unstable();
2114 assert_eq!(buf, expected);
2115 }
2116
2117 // -------------------------------------------------------------------------
2118 // Reschedule
2119 // -------------------------------------------------------------------------
2120
2121 #[test]
2122 fn reschedule_moves_deadline() {
2123 let now = Instant::now();
2124 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2125
2126 let h = wheel.schedule(now + ms(100), 42);
2127 assert_eq!(wheel.len(), 1);
2128
2129 // Reschedule to earlier
2130 let h = wheel.reschedule(h, now + ms(50));
2131 assert_eq!(wheel.len(), 1);
2132
2133 // Should NOT fire at 40ms
2134 let mut buf = Vec::new();
2135 let fired = wheel.poll(now + ms(40), &mut buf);
2136 assert_eq!(fired, 0);
2137
2138 // Should fire at 50ms
2139 let fired = wheel.poll(now + ms(55), &mut buf);
2140 assert_eq!(fired, 1);
2141 assert_eq!(buf, vec![42]);
2142
2143 // Clean up zombie
2144 wheel.cancel(h);
2145 }
2146
2147 #[test]
2148 fn reschedule_to_later() {
2149 let now = Instant::now();
2150 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2151
2152 let h = wheel.schedule(now + ms(50), 7);
2153
2154 // Reschedule to later
2155 let h = wheel.reschedule(h, now + ms(200));
2156
2157 // Should NOT fire at original deadline
2158 let mut buf = Vec::new();
2159 let fired = wheel.poll(now + ms(60), &mut buf);
2160 assert_eq!(fired, 0);
2161
2162 // Should fire at new deadline
2163 let fired = wheel.poll(now + ms(210), &mut buf);
2164 assert_eq!(fired, 1);
2165 assert_eq!(buf, vec![7]);
2166
2167 wheel.cancel(h);
2168 }
2169
2170 #[test]
2171 #[should_panic(expected = "cannot reschedule a fired timer")]
2172 fn reschedule_panics_on_zombie() {
2173 let now = Instant::now();
2174 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2175
2176 let h = wheel.schedule(now + ms(10), 42);
2177
2178 let mut buf = Vec::new();
2179 wheel.poll(now + ms(20), &mut buf);
2180
2181 // h is now a zombie — reschedule should panic
2182 let _h = wheel.reschedule(h, now + ms(100));
2183 }
2184
2185 // -------------------------------------------------------------------------
2186 // Non-default builder configurations (L13)
2187 // -------------------------------------------------------------------------
2188
2189 #[test]
2190 fn custom_slots_per_level() {
2191 let now = Instant::now();
2192 // 32 slots/level instead of default 64
2193 let mut wheel: Wheel<u64> = WheelBuilder::default()
2194 .slots_per_level(32)
2195 .unbounded(256)
2196 .build(now)
2197 .unwrap();
2198
2199 // Level 0 range = 32 ticks (32ms with 1ms tick)
2200 // Deadline at 20ms should go to level 0
2201 let h1 = wheel.schedule(now + ms(20), 1);
2202 // Deadline at 40ms should go to level 1 (>= 32 ticks)
2203 let h2 = wheel.schedule(now + ms(40), 2);
2204
2205 let mut buf = Vec::new();
2206 wheel.poll(now + ms(25), &mut buf);
2207 assert_eq!(buf, vec![1]);
2208
2209 buf.clear();
2210 wheel.poll(now + ms(50), &mut buf);
2211 assert_eq!(buf, vec![2]);
2212
2213 wheel.cancel(h1);
2214 wheel.cancel(h2);
2215 }
2216
2217 #[test]
2218 fn custom_clk_shift() {
2219 let now = Instant::now();
2220 // clk_shift=2 means 4x multiplier between levels (instead of 8x)
2221 let mut wheel: Wheel<u64> = WheelBuilder::default()
2222 .clk_shift(2)
2223 .unbounded(256)
2224 .build(now)
2225 .unwrap();
2226
2227 // Level 0: 64 slots × 1ms = 64ms range
2228 // Level 1: 64 slots × 4ms = 256ms range (with 4x multiplier)
2229 let h1 = wheel.schedule(now + ms(50), 1); // level 0
2230 let h2 = wheel.schedule(now + ms(100), 2); // level 1 (>= 64 ticks, <256 ticks)
2231
2232 let mut buf = Vec::new();
2233 wheel.poll(now + ms(55), &mut buf);
2234 assert_eq!(buf, vec![1]);
2235
2236 buf.clear();
2237 wheel.poll(now + ms(110), &mut buf);
2238 assert_eq!(buf, vec![2]);
2239
2240 wheel.cancel(h1);
2241 wheel.cancel(h2);
2242 }
2243
2244 #[test]
2245 fn custom_num_levels() {
2246 let now = Instant::now();
2247 // Only 3 levels instead of 7
2248 let mut wheel: Wheel<u64> = WheelBuilder::default()
2249 .num_levels(3)
2250 .unbounded(256)
2251 .build(now)
2252 .unwrap();
2253
2254 // Level 0: 64ms, Level 1: 512ms, Level 2: 4096ms
2255 // Max range is level 2 = 4096ms. Beyond that, clamped.
2256 let h = wheel.schedule(now + ms(3000), 42);
2257 assert_eq!(wheel.len(), 1);
2258
2259 let mut buf = Vec::new();
2260 wheel.poll(now + ms(3100), &mut buf);
2261 assert_eq!(buf, vec![42]);
2262
2263 wheel.cancel(h);
2264 }
2265
2266 #[test]
2267 fn custom_tick_duration() {
2268 let now = Instant::now();
2269 // 100μs ticks instead of 1ms
2270 let mut wheel: Wheel<u64> = WheelBuilder::default()
2271 .tick_duration(Duration::from_micros(100))
2272 .unbounded(256)
2273 .build(now)
2274 .unwrap();
2275
2276 // 1ms = 10 ticks, should be level 0 (< 64 ticks)
2277 wheel.schedule_forget(now + ms(1), 1);
2278 // 10ms = 100 ticks, should be level 1 (>= 64 ticks)
2279 wheel.schedule_forget(now + ms(10), 2);
2280
2281 let mut buf = Vec::new();
2282 wheel.poll(now + ms(2), &mut buf);
2283 assert_eq!(buf, vec![1]);
2284
2285 buf.clear();
2286 wheel.poll(now + ms(15), &mut buf);
2287 assert_eq!(buf, vec![2]);
2288 }
2289
2290 #[test]
2291 fn bounded_custom_config() {
2292 let now = Instant::now();
2293 let mut wheel: BoundedWheel<u64> = WheelBuilder::default()
2294 .slots_per_level(16)
2295 .num_levels(4)
2296 .bounded(8)
2297 .build(now)
2298 .unwrap();
2299
2300 // Fill to capacity
2301 let mut handles = Vec::new();
2302 for i in 0..8 {
2303 handles.push(wheel.try_schedule(now + ms(i * 10 + 10), i).unwrap());
2304 }
2305 assert!(wheel.try_schedule(now + ms(100), 99).is_err());
2306
2307 // Cancel one, schedule another
2308 wheel.cancel(handles.remove(0));
2309 let h = wheel.try_schedule(now + ms(100), 99).unwrap();
2310 handles.push(h);
2311
2312 // Clean up
2313 for h in handles {
2314 wheel.cancel(h);
2315 }
2316 }
2317
2318 // -------------------------------------------------------------------------
2319 // Builder validation (L13)
2320 // -------------------------------------------------------------------------
2321
2322 /// Asserts `result` is `Err(ConfigError::Invalid(_))` whose message contains
2323 /// `expect_substr`. Generic over the Ok type so it needs no `Debug` bound on
2324 /// the built wheel.
2325 #[track_caller]
2326 fn assert_invalid<T>(result: &Result<T, ConfigError>, expect_substr: &str) {
2327 match result {
2328 Err(ConfigError::Invalid(msg)) => assert!(
2329 msg.contains(expect_substr),
2330 "message {msg:?} does not contain {expect_substr:?}"
2331 ),
2332 Ok(_) => panic!("expected ConfigError::Invalid containing {expect_substr:?}, got Ok"),
2333 }
2334 }
2335
2336 #[test]
2337 fn invalid_config_too_many_slots() {
2338 let now = Instant::now();
2339 let result = WheelBuilder::default()
2340 .slots_per_level(128)
2341 .unbounded(1024)
2342 .build::<u64>(now);
2343 assert_invalid(&result, "slots_per_level must be <= 64");
2344 }
2345
2346 #[test]
2347 fn invalid_config_zero_levels() {
2348 let now = Instant::now();
2349 let result = WheelBuilder::default()
2350 .num_levels(0)
2351 .unbounded(1024)
2352 .build::<u64>(now);
2353 assert_invalid(&result, "num_levels must be > 0");
2354 }
2355
2356 #[test]
2357 fn invalid_config_too_many_levels() {
2358 let now = Instant::now();
2359 let result = WheelBuilder::default()
2360 .num_levels(9)
2361 .unbounded(1024)
2362 .build::<u64>(now);
2363 assert_invalid(&result, "num_levels must be <= 8");
2364 }
2365
2366 #[test]
2367 fn invalid_config_zero_shift() {
2368 let now = Instant::now();
2369 let result = WheelBuilder::default()
2370 .clk_shift(0)
2371 .unbounded(1024)
2372 .build::<u64>(now);
2373 assert_invalid(&result, "clk_shift must be > 0");
2374 }
2375
2376 #[test]
2377 fn invalid_config_zero_tick() {
2378 let now = Instant::now();
2379 let result = WheelBuilder::default()
2380 .tick_duration(Duration::ZERO)
2381 .unbounded(1024)
2382 .build::<u64>(now);
2383 assert_invalid(&result, "tick_duration must be non-zero");
2384 }
2385
2386 #[test]
2387 fn invalid_config_tick_too_large() {
2388 let now = Instant::now();
2389 // as_nanos() would exceed u64::MAX (~584 years), which would truncate on
2390 // the cast to u64 — must be rejected, not silently narrowed (a nonzero
2391 // multiple of 2^64 would truncate to 0 → divide-by-zero in build()).
2392 let result = WheelBuilder::default()
2393 .tick_duration(Duration::from_secs(20_000_000_000))
2394 .unbounded(1024)
2395 .build::<u64>(now);
2396 assert_invalid(&result, "tick_duration must fit in u64 nanoseconds");
2397 }
2398
2399 #[test]
2400 fn invalid_config_shift_overflow() {
2401 let now = Instant::now();
2402 // 8 levels × clk_shift=8 = 56 bits shift on level 7
2403 // Plus 64 slots (6 bits) = 62 bits, should be OK
2404 // But 8 levels × clk_shift=9 = 63 + 6 = 69 bits — overflow
2405 let result = WheelBuilder::default()
2406 .num_levels(8)
2407 .clk_shift(9)
2408 .unbounded(1024)
2409 .build::<u64>(now);
2410 assert_invalid(&result, "overflow");
2411 }
2412
2413 #[test]
2414 fn invalid_config_rebalance_progress() {
2415 let now = Instant::now();
2416 // slots_per_level = 4 (2^2), clk_shift = 3 → 2^3 = 8 >= 4, so a not-due
2417 // entry could rebalance to the *same* level and poll would live-lock.
2418 // Must be rejected at build time.
2419 let result = WheelBuilder::default()
2420 .slots_per_level(4)
2421 .clk_shift(3)
2422 .num_levels(2)
2423 .unbounded(64)
2424 .build::<u64>(now);
2425 assert_invalid(&result, "strictly finer level");
2426 }
2427
2428 // -------------------------------------------------------------------------
2429 // Rebalance tests (#668)
2430 // -------------------------------------------------------------------------
2431
2432 #[test]
2433 fn rebalanced_entry_fires_at_its_deadline() {
2434 let now = Instant::now();
2435 let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2436
2437 // Both deadlines land in the same level-2 slot (46): 3000>>6 == 3005>>6.
2438 // At now=3000 the slot's min (3000) is due, so the slot is walked: 3000
2439 // is collected, and 3005 (not yet due) is rebalanced to a finer level
2440 // rather than being re-walked. It must still fire at its exact deadline.
2441 wheel.schedule_forget(now + ms(3000), 1);
2442 wheel.schedule_forget(now + ms(3005), 2);
2443
2444 let mut buf = Vec::new();
2445 wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2446 assert_eq!(buf, vec![1], "3000 collected, 3005 rebalanced");
2447
2448 buf.clear();
2449 wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2450 assert_eq!(buf, vec![2], "rebalanced entry fires at its exact deadline");
2451 assert!(wheel.is_empty());
2452 }
2453
2454 #[test]
2455 fn cancel_after_rebalance() {
2456 let now = Instant::now();
2457 let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2458
2459 wheel.schedule_forget(now + ms(3000), 1);
2460 let h = wheel.schedule(now + ms(3005), 2); // rebalanced on the 3000 poll
2461
2462 let mut buf = Vec::new();
2463 wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2464 assert_eq!(buf, vec![1]);
2465 assert_eq!(wheel.len(), 1, "rebalanced entry still live");
2466
2467 // cancel must find the entry at its new (finer) location and return it.
2468 assert_eq!(wheel.cancel(h), Some(2));
2469 assert_eq!(wheel.len(), 0);
2470 }
2471
2472 #[test]
2473 fn bounded_rebalance_still_fires_everything_on_time() {
2474 let now = Instant::now();
2475 // Cap = 1 rebalance per poll — a herd of not-yet-due entries in one
2476 // coarse slot drains over many polls instead of all at once, but every
2477 // timer must still fire at its exact deadline.
2478 let mut wheel: Wheel<u64> = WheelBuilder::default()
2479 .max_rebalances_per_poll(1)
2480 .unbounded(256)
2481 .build(now)
2482 .unwrap();
2483
2484 // 20 deadlines spread across one level-2 slot (all map to slot 46).
2485 let mut expected: Vec<u64> = Vec::new();
2486 for i in 0..20u64 {
2487 let d = 2950 + i * 2; // 2950, 2952, ... 2988 — all in level-2 slot 46
2488 wheel.schedule_forget(now + ms(d), d);
2489 expected.push(d);
2490 }
2491
2492 let mut fired: Vec<u64> = Vec::new();
2493 let mut buf = Vec::new();
2494 for t in 0..=3000u64 {
2495 buf.clear();
2496 wheel.poll_and_rebalance(now + ms(t), &mut buf);
2497 for &v in &buf {
2498 assert!(v <= t, "timer {v} fired early at {t}");
2499 fired.push(v);
2500 }
2501 }
2502 fired.sort_unstable();
2503 assert_eq!(fired, expected, "every timer fires exactly once, on time");
2504 assert!(wheel.is_empty());
2505 }
2506
2507 #[test]
2508 fn rebalance_cap_zero_is_collect_only() {
2509 let now = Instant::now();
2510 // Cap = 0: no rebalancing at all — entries never move levels and fire
2511 // from wherever they were placed (pure drip-fire). Must still be correct.
2512 let mut wheel: Wheel<u64> = WheelBuilder::default()
2513 .max_rebalances_per_poll(0)
2514 .unbounded(256)
2515 .build(now)
2516 .unwrap();
2517
2518 wheel.schedule_forget(now + ms(3000), 1);
2519 wheel.schedule_forget(now + ms(3005), 2); // would rebalance if the cap allowed
2520
2521 let mut buf = Vec::new();
2522 wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2523 assert_eq!(buf, vec![1]); // 3000 collected; 3005 left in its coarse slot
2524 buf.clear();
2525 wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2526 assert_eq!(buf, vec![2]); // fires on time from its original slot
2527 assert!(wheel.is_empty());
2528 }
2529
2530 #[test]
2531 fn proactive_rebalance_moves_and_preserves_firing() {
2532 let now = Instant::now();
2533 let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2534
2535 // 10 deadlines at level 2 (delta ~3000 ∈ [512, 4096)).
2536 let mut expected = Vec::new();
2537 for i in 0..10u64 {
2538 let d = 3000 + i * 4;
2539 wheel.schedule_forget(now + ms(d), d);
2540 expected.push(d);
2541 }
2542
2543 // Far from the deadlines, nothing is within a finer level's reach.
2544 assert_eq!(
2545 wheel.rebalance(now, usize::MAX),
2546 0,
2547 "nothing to pull down yet"
2548 );
2549
2550 // Drive the timeline with proactive rebalance + collect-only poll. Every
2551 // timer must still fire exactly once, on time — and rebalance must have
2552 // actually pulled entries down as they approached.
2553 let mut fired = Vec::new();
2554 let mut buf = Vec::new();
2555 let mut total_moved = 0;
2556 for t in 0..=3040u64 {
2557 total_moved += wheel.rebalance(now + ms(t), usize::MAX);
2558 buf.clear();
2559 wheel.poll(now + ms(t), &mut buf);
2560 for &v in &buf {
2561 assert!(v <= t, "timer {v} fired early at {t}");
2562 fired.push(v);
2563 }
2564 }
2565 assert!(
2566 total_moved > 0,
2567 "rebalance pulled entries down as they neared"
2568 );
2569 fired.sort_unstable();
2570 assert_eq!(fired, expected, "every timer fires once, on time");
2571 assert!(wheel.is_empty());
2572 }
2573
2574 // -------------------------------------------------------------------------
2575 // Miri-compatible tests (L12)
2576 // -------------------------------------------------------------------------
2577 // These tests exercise the raw pointer paths (DLL operations, entry
2578 // lifecycle, poll) with Drop types to catch UB under Miri.
2579
2580 #[test]
2581 fn miri_schedule_cancel_drop_type() {
2582 let now = Instant::now();
2583 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2584
2585 let h = wheel.schedule(now + ms(50), "hello".to_string());
2586 let val = wheel.cancel(h);
2587 assert_eq!(val, Some("hello".to_string()));
2588 assert!(wheel.is_empty());
2589 }
2590
2591 #[test]
2592 fn miri_poll_fires_drop_type() {
2593 let now = Instant::now();
2594 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2595
2596 wheel.schedule_forget(now + ms(10), "a".to_string());
2597 wheel.schedule_forget(now + ms(10), "b".to_string());
2598 wheel.schedule_forget(now + ms(10), "c".to_string());
2599
2600 let mut buf = Vec::new();
2601 let fired = wheel.poll(now + ms(20), &mut buf);
2602 assert_eq!(fired, 3);
2603 assert_eq!(buf.len(), 3);
2604 assert!(wheel.is_empty());
2605 }
2606
2607 #[test]
2608 fn miri_cancel_zombie_drop_type() {
2609 let now = Instant::now();
2610 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2611
2612 let h = wheel.schedule(now + ms(10), "zombie".to_string());
2613
2614 let mut buf = Vec::new();
2615 wheel.poll(now + ms(20), &mut buf);
2616 assert_eq!(buf, vec!["zombie".to_string()]);
2617
2618 // h is now a zombie — cancel frees the entry
2619 let val = wheel.cancel(h);
2620 assert_eq!(val, None);
2621 }
2622
2623 #[test]
2624 fn miri_free_active_and_zombie() {
2625 let now = Instant::now();
2626 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2627
2628 // Active → fire-and-forget via free
2629 let h1 = wheel.schedule(now + ms(10), "active".to_string());
2630 wheel.free(h1);
2631
2632 // Poll fires the fire-and-forget entry
2633 let mut buf = Vec::new();
2634 wheel.poll(now + ms(20), &mut buf);
2635 assert_eq!(buf, vec!["active".to_string()]);
2636
2637 // Zombie → free
2638 let h2 = wheel.schedule(now + ms(10), "will-fire".to_string());
2639 buf.clear();
2640 wheel.poll(now + ms(20), &mut buf);
2641 wheel.free(h2); // zombie cleanup
2642 }
2643
2644 #[test]
2645 fn miri_reschedule_drop_type() {
2646 let now = Instant::now();
2647 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2648
2649 let h = wheel.schedule(now + ms(100), "moveme".to_string());
2650 let h = wheel.reschedule(h, now + ms(50));
2651
2652 let mut buf = Vec::new();
2653 wheel.poll(now + ms(55), &mut buf);
2654 assert_eq!(buf, vec!["moveme".to_string()]);
2655
2656 wheel.cancel(h);
2657 }
2658
2659 #[test]
2660 fn miri_dll_multi_entry_same_slot() {
2661 // Multiple entries in same slot exercises DLL push/remove paths
2662 let now = Instant::now();
2663 let mut wheel: Wheel<Vec<u8>> = Wheel::unbounded(64, now);
2664
2665 let mut handles = Vec::new();
2666 for i in 0..5 {
2667 handles.push(wheel.schedule(now + ms(10), vec![i; 32]));
2668 }
2669
2670 // Cancel middle, then head, then tail
2671 let v2 = wheel.cancel(handles.remove(2));
2672 assert_eq!(v2.unwrap(), vec![2; 32]);
2673
2674 let v0 = wheel.cancel(handles.remove(0));
2675 assert_eq!(v0.unwrap(), vec![0; 32]);
2676
2677 // Poll remaining
2678 let mut buf = Vec::new();
2679 wheel.poll(now + ms(20), &mut buf);
2680 assert_eq!(buf.len(), 3);
2681
2682 // Clean up zombie handles
2683 for h in handles {
2684 wheel.cancel(h);
2685 }
2686 }
2687
2688 #[test]
2689 fn miri_drop_wheel_with_entries() {
2690 let now = Instant::now();
2691 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2692
2693 // Schedule entries across multiple levels
2694 for i in 0..20 {
2695 wheel.schedule_forget(now + ms(i * 100), format!("entry-{i}"));
2696 }
2697 assert_eq!(wheel.len(), 20);
2698
2699 // Drop with active entries — must not leak or UB
2700 drop(wheel);
2701 }
2702
2703 #[test]
2704 fn miri_bounded_lifecycle() {
2705 let now = Instant::now();
2706 let mut wheel: BoundedWheel<String> = BoundedWheel::bounded(4, now);
2707
2708 let h1 = wheel.try_schedule(now + ms(10), "a".to_string()).unwrap();
2709 let h2 = wheel.try_schedule(now + ms(20), "b".to_string()).unwrap();
2710 let h3 = wheel.try_schedule(now + ms(30), "c".to_string()).unwrap();
2711 let h4 = wheel.try_schedule(now + ms(40), "d".to_string()).unwrap();
2712
2713 // Full
2714 let err = wheel.try_schedule(now + ms(50), "e".to_string());
2715 assert!(err.is_err());
2716
2717 // Cancel and reuse
2718 wheel.cancel(h1);
2719 let h5 = wheel.try_schedule(now + ms(50), "e".to_string()).unwrap();
2720
2721 // Poll fires some
2722 let mut buf = Vec::new();
2723 wheel.poll(now + ms(25), &mut buf);
2724
2725 // Clean up all remaining handles
2726 wheel.cancel(h2);
2727 wheel.free(h3);
2728 wheel.free(h4);
2729 wheel.free(h5);
2730 }
2731
2732 #[test]
2733 fn miri_rebalance_relocate_drop_type() {
2734 // Exercises the rebalance relocate path (insert_entry called while this
2735 // slot's `&WheelSlot` is held) with a Drop type, to catch any aliasing
2736 // UB in that hot-path borrow. Must use poll_and_rebalance — plain poll
2737 // never relocates, so it would not exercise the path.
2738 let now = Instant::now();
2739 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2740
2741 // Same level-2 slot: 3000>>6 == 3005>>6. At now=3000 the "collected"
2742 // entry fires and the "rebalanced" entry relocates to a finer level.
2743 wheel.schedule_forget(now + ms(3000), "collected".to_string());
2744 wheel.schedule_forget(now + ms(3005), "rebalanced".to_string());
2745
2746 let mut buf = Vec::new();
2747 wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2748 assert_eq!(buf, vec!["collected".to_string()]);
2749
2750 buf.clear();
2751 wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2752 assert_eq!(buf, vec!["rebalanced".to_string()]);
2753 assert!(wheel.is_empty());
2754 }
2755
2756 #[test]
2757 fn miri_rebalance_method_drop_type() {
2758 // Standalone rebalance() uses the same insert_entry-while-slot-borrowed
2759 // pattern as poll_and_rebalance; exercise it with a Drop type.
2760 let now = Instant::now();
2761 let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2762 wheel.schedule_forget(now + ms(3000), "a".to_string());
2763 wheel.schedule_forget(now + ms(3004), "b".to_string());
2764
2765 // Advance so both are within a finer level's reach, then rebalance.
2766 let moved = wheel.rebalance(now + ms(2960), usize::MAX);
2767 assert!(moved >= 1);
2768
2769 let mut buf = Vec::new();
2770 wheel.poll(now + ms(3004), &mut buf);
2771 buf.sort();
2772 assert_eq!(buf, vec!["a".to_string(), "b".to_string()]);
2773 assert!(wheel.is_empty());
2774 }
2775}
2776
2777#[cfg(test)]
2778mod proptests {
2779 use super::*;
2780 use proptest::prelude::*;
2781 use std::collections::HashSet;
2782 use std::mem;
2783 use std::time::{Duration, Instant};
2784
2785 /// Operation in a schedule/cancel interleaving.
2786 #[derive(Debug, Clone)]
2787 enum Op {
2788 /// Schedule a timer at `deadline_ms` milliseconds from epoch.
2789 Schedule { deadline_ms: u64 },
2790 /// Cancel the timer at the given index (modulo outstanding handles).
2791 Cancel { idx: usize },
2792 }
2793
2794 fn op_strategy() -> impl Strategy<Value = Op> {
2795 prop_oneof![
2796 // Schedule with deadlines from 1ms to 10_000ms
2797 (1u64..10_000).prop_map(|deadline_ms| Op::Schedule { deadline_ms }),
2798 // Cancel at random index
2799 any::<usize>().prop_map(|idx| Op::Cancel { idx }),
2800 ]
2801 }
2802
2803 proptest! {
2804 #![proptest_config(ProptestConfig::with_cases(500))]
2805
2806 /// Fuzz schedule/cancel interleaving.
2807 ///
2808 /// Random sequence of schedule and cancel operations. Invariants:
2809 /// - `len` always matches outstanding active timers
2810 /// - cancel on active handle returns `Some`
2811 /// - poll collects all un-cancelled values
2812 #[test]
2813 fn fuzz_schedule_cancel_interleaving(ops in proptest::collection::vec(op_strategy(), 1..200)) {
2814 let now = Instant::now();
2815 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2816
2817 let mut handles: Vec<TimerHandle<u64>> = Vec::new();
2818 let mut active_values: HashSet<u64> = HashSet::new();
2819 let mut next_id: u64 = 0;
2820
2821 for op in &ops {
2822 match op {
2823 Op::Schedule { deadline_ms } => {
2824 let id = next_id;
2825 next_id += 1;
2826 let h = wheel.schedule(now + Duration::from_millis(*deadline_ms), id);
2827 handles.push(h);
2828 active_values.insert(id);
2829 }
2830 Op::Cancel { idx } => {
2831 if !handles.is_empty() {
2832 let i = idx % handles.len();
2833 let h = handles.swap_remove(i);
2834 let val = wheel.cancel(h);
2835 // Value should be Some (all handles are for active timers)
2836 let v = val.unwrap();
2837 assert!(active_values.remove(&v));
2838 }
2839 }
2840 }
2841 // len must match active values
2842 prop_assert_eq!(wheel.len(), active_values.len());
2843 }
2844
2845 // Poll everything — should collect exactly the remaining active values
2846 let mut buf = Vec::new();
2847 // Use a far-future time to fire everything
2848 wheel.poll(now + Duration::from_secs(100_000), &mut buf);
2849
2850 // Clean up zombie handles (poll fired them, handles still exist)
2851 for h in handles {
2852 mem::forget(h);
2853 }
2854
2855 let fired_set: HashSet<u64> = buf.into_iter().collect();
2856 prop_assert_eq!(fired_set, active_values);
2857 prop_assert!(wheel.is_empty());
2858 }
2859
2860 /// Fuzz poll timing.
2861 ///
2862 /// Schedule N timers with random deadlines. Poll at random increasing
2863 /// times. Assert every timer fires exactly once, fired deadlines are
2864 /// all <= poll time, unfired deadlines are all > poll time.
2865 #[test]
2866 fn fuzz_poll_timing(
2867 deadlines in proptest::collection::vec(1u64..5000, 1..100),
2868 poll_times in proptest::collection::vec(1u64..10_000, 1..20),
2869 ) {
2870 let now = Instant::now();
2871 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2872
2873 // Schedule all timers (fire-and-forget)
2874 for (i, &d) in deadlines.iter().enumerate() {
2875 wheel.schedule_forget(now + Duration::from_millis(d), i as u64);
2876 }
2877
2878 // Sort poll times to be monotonically increasing
2879 let mut sorted_times: Vec<u64> = poll_times;
2880 sorted_times.sort_unstable();
2881 sorted_times.dedup();
2882
2883 let mut all_fired: Vec<u64> = Vec::new();
2884
2885 for &t in &sorted_times {
2886 let mut buf = Vec::new();
2887 wheel.poll(now + Duration::from_millis(t), &mut buf);
2888
2889 // Every fired entry should have deadline_ms <= t
2890 for &id in &buf {
2891 let deadline_ms = deadlines[id as usize];
2892 prop_assert!(deadline_ms <= t,
2893 "Timer {} with deadline {}ms fired at {}ms", id, deadline_ms, t);
2894 }
2895
2896 all_fired.extend(buf);
2897 }
2898
2899 // Fire everything remaining
2900 let mut final_buf = Vec::new();
2901 wheel.poll(now + Duration::from_secs(100_000), &mut final_buf);
2902 all_fired.extend(final_buf);
2903
2904 // Every timer should have fired exactly once
2905 all_fired.sort_unstable();
2906 let expected: Vec<u64> = (0..deadlines.len() as u64).collect();
2907 prop_assert_eq!(all_fired, expected, "Not all timers fired exactly once");
2908 prop_assert!(wheel.is_empty());
2909 }
2910
2911 /// Fuzz next_deadline cache correctness.
2912 ///
2913 /// Random sequence of schedule, schedule_forget, cancel, reschedule,
2914 /// and poll operations. After each operation, verifies the cached
2915 /// `next_deadline()` matches the uncached full walk.
2916 #[test]
2917 fn fuzz_next_deadline_cache(
2918 ops in proptest::collection::vec(deadline_op_strategy(), 1..300),
2919 ) {
2920 let now = Instant::now();
2921 let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2922 let mut handles: Vec<(TimerHandle<u64>, u64)> = Vec::new();
2923 let mut next_id: u64 = 0;
2924
2925 for op in &ops {
2926 match op {
2927 DeadlineOp::Schedule { deadline_ms } => {
2928 let h = wheel.schedule(now + Duration::from_millis(*deadline_ms), next_id);
2929 handles.push((h, *deadline_ms));
2930 next_id += 1;
2931 }
2932 DeadlineOp::ScheduleForget { deadline_ms } => {
2933 wheel.schedule_forget(now + Duration::from_millis(*deadline_ms), next_id);
2934 next_id += 1;
2935 }
2936 DeadlineOp::Cancel { idx } => {
2937 if !handles.is_empty() {
2938 let i = idx % handles.len();
2939 let (h, _) = handles.swap_remove(i);
2940 wheel.cancel(h);
2941 }
2942 }
2943 DeadlineOp::Reschedule { idx, new_deadline_ms } => {
2944 if !handles.is_empty() {
2945 let i = idx % handles.len();
2946 let (h, _) = handles.swap_remove(i);
2947 let new_h = wheel.reschedule(h, now + Duration::from_millis(*new_deadline_ms));
2948 handles.push((new_h, *new_deadline_ms));
2949 }
2950 }
2951 DeadlineOp::Poll { at_ms } => {
2952 let mut buf = Vec::new();
2953 wheel.poll(now + Duration::from_millis(*at_ms), &mut buf);
2954 // Free zombie handles whose timers just fired.
2955 // A handle is a zombie if its deadline_ms <= at_ms.
2956 let at = *at_ms;
2957 let mut i = 0;
2958 while i < handles.len() {
2959 if handles[i].1 <= at {
2960 let (h, _) = handles.swap_remove(i);
2961 wheel.free(h);
2962 } else {
2963 i += 1;
2964 }
2965 }
2966 }
2967 }
2968
2969 // Contract: `next_deadline()` is a LOWER BOUND — the per-slot
2970 // minima are stale-low after removal, so it may report earlier
2971 // than the true next fire, never later. Assert it never exceeds
2972 // the exact minimum, and that emptiness agrees.
2973 let cached = wheel.next_deadline();
2974 let exact = wheel.next_deadline_uncached();
2975 prop_assert_eq!(
2976 cached.is_none(),
2977 exact.is_none(),
2978 "emptiness disagrees after {:?}",
2979 op
2980 );
2981 if let (Some(c), Some(e)) = (cached, exact) {
2982 prop_assert!(
2983 c <= e,
2984 "next_deadline {:?} exceeded exact {:?} after {:?}",
2985 c,
2986 e,
2987 op
2988 );
2989 }
2990 }
2991
2992 for (h, _) in handles {
2993 mem::forget(h);
2994 }
2995 }
2996 }
2997
2998 #[derive(Debug, Clone)]
2999 enum DeadlineOp {
3000 Schedule { deadline_ms: u64 },
3001 ScheduleForget { deadline_ms: u64 },
3002 Cancel { idx: usize },
3003 Reschedule { idx: usize, new_deadline_ms: u64 },
3004 Poll { at_ms: u64 },
3005 }
3006
3007 fn deadline_op_strategy() -> impl Strategy<Value = DeadlineOp> {
3008 prop_oneof![
3009 (1u64..10_000).prop_map(|deadline_ms| DeadlineOp::Schedule { deadline_ms }),
3010 (1u64..10_000).prop_map(|deadline_ms| DeadlineOp::ScheduleForget { deadline_ms }),
3011 any::<usize>().prop_map(|idx| DeadlineOp::Cancel { idx }),
3012 (any::<usize>(), 1u64..10_000).prop_map(|(idx, new_deadline_ms)| {
3013 DeadlineOp::Reschedule {
3014 idx,
3015 new_deadline_ms,
3016 }
3017 }),
3018 (1u64..10_000).prop_map(|at_ms| DeadlineOp::Poll { at_ms }),
3019 ]
3020 }
3021}