In my previous post, I wrote about building an executor from scratch and how cooperative async tasks actually interact with OS threads. After getting cooperative multitasking working, the next logical milestone was implementing timers: giving tasks the ability to sleep(duration).await.
Deceived by how effortless tokio::time::sleep looks from the outside, I challenged myself to build timers for my own runtime, thinking it would be straightforward. My approach was to store deadlines in a BinaryHeap, park a background thread until the earliest deadline at the head of the heap, and wake up the corresponding task as soon as the thread woke up.
// Naive approach: O(log N) insertion
// (Ord / Eq implemented by comparing `deadline`)
struct TimerEntry {
deadline: Instant,
waker: Option<Waker>,
}
let mut heap: BinaryHeap<Reverse<TimerEntry>> = BinaryHeap::new();
For a small-scale runtime, a BinaryHeap is more than fast enough. Still, getting it working sparked my curiosity: how does a production runtime like Tokio handle millions of concurrent timers under massive throughput?
I peeked inside Tokio’s timer subsystem, and the implementation completely blew my mind. Instead of a heap, what I found looked less like typical Rust and more like dark systems magic: bitwise odometers, raw pointer manipulation, hardware bit rotations, and PhantomPinned.
This post serves as a guided tour of Tokio’s timer internals, tracing a single sleep(duration).await from registration to wakeup.
Overall Architecture: The sleep() Lifecycle
Before diving into the dark systems magic of bitwise math and raw pointers, here is how all the moving pieces of Tokio’s timer subsystem fit together from setup to task wakeup:
flowchart TD
subgraph Setup["1. Runtime & Driver Setup"]
RT["Builder::build()"] --> TD["time::Driver::new()"]
TD --> TH["time::Handle (Context / Thread Local Storage)"]
TH --> Inner["Mutex#lt;InnerState#gt;
- Wheel (6 levels x 64 slots)
- next_wake: Option#lt;NonZeroU64#gt;"]
end
subgraph Ingest["2. Timer Ingestion (sleep.await)"]
Sleep["tokio::time::sleep(duration).await"] --> Tick["when = Convert Instant to wheel tick
(ms since runtime start)"]
Tick --> Locate["Locate Level & Slot
level = level_for(elapsed, when)
slot = slot_for(when, level)"]
Locate --> Slot["Insert TimerShared into levels[level].slot[slot]
Set occupied bitmask |= (1 #lt;#lt; slot)"]
Slot --> CheckWake{"when #lt; next_wake?"}
CheckWake -- "Yes (Earlier deadline)" --> Unpark["IoHandle::unpark()
Wake sleeping driver early"]
CheckWake -- "No" --> Pending["Return Poll::Pending"]
end
subgraph Consume["3. Driving Time & Waking (process_at_time)"]
Drive["Driver::park_internal() or 61-tick poll"] --> PollWheel["Wheel::poll(now)"]
PollWheel --> NextExp["next_expiration()
Find earliest occupied slot across levels"]
NextExp --> SlotDue{"expiration.deadline #lt;= now?"}
SlotDue -- "Yes" --> TakeSlot["process_expiration()
Take entries from expired slot"]
SlotDue -- "No (Not due yet)" --> AdvanceNow["set_elapsed(now)"]
TakeSlot --> EntryDue{"entry.true_when() #lt;= deadline?"}
EntryDue -- "No (Time remaining)" --> Reinsert["Cascade entry down to lower level"]
Reinsert --> NextExp
EntryDue -- "Yes (Expired)" --> PushPending["Move expired entries to Wheel::pending"]
PushPending --> Batch["Try pop pending into WakeList
(local array buffer up to 32)"]
AdvanceNow --> Batch
Batch --> DropLock["Drop Mutex#lt;InnerState#gt;"]
DropLock --> WakeAll["WakeList::wake_all()
Push tasks to scheduler run queue"]
end
Setup --> Ingest
Ingest --> Consume
Component Breakdown (Ordered by Lifecycle)
You can read straight through to follow a timer’s journey, or jump directly to any component below:
- The Core Data Structure: The 6-Level Timer Wheel: Instead of sorting deadlines in a
BinaryHeap, Tokio buckets timers into 6 circular arrays (levels) of 64 slots each, achievingO(1)insertion andO(1)cancellation across an unbounded time horizon (using Level 5 as a 2.17-year pseudo-ring buffer). - Ingesting a Timer: The Bitwise Odometer: When
sleep(duration).awaitis polled, Tokio converts the deadline into a millisecond tick, uses an XOR odometer to find the level in 4 CPU instructions (level_for), and shifts the bits to index the exact slot (slot_for). - Storing and Resetting Timers: Intrusive Linked Lists: To eliminate memory allocations on the heap every time a timer is inserted or moved, each
Sleepfuture embeds its ownprev/nextpointers (PhantomPinned) and tracksregistered_whenvstrue_when()forO(1)resets. - Finding the Next Deadline: Hardware Bit Rotation: Each level tracks non-empty slots inside a single
u64bitmask (occupied), usingrotate_rightandtrailing_zeros()to locate the next due timer inO(1)time without looping. - Who Turns the Wheel?
TryLock<Driver>: Tokio has no dedicated timer thread; instead worker threads take turns acquiring a non-blockingTryLock<Driver>so at most one worker sleeps on the OS poller or advances the wheel at a time. - Preempting a Sleeping Driver:
next_wakeandunpark: Tokio caches the currently parked wakeup tick insidenext_wake. If another worker inserts a timer that expires earlier thannext_wake, it callsunpark.unpark()(mio::Waker) to interrupt the sleeping driver holder immediately. - Waking Tasks Safely:
WakeListandDropGuard: To avoid deadlocks, Tokio never wakes tasks while holding the wheel lock. Instead, it buffers up to 32 expiredWakers in a local array (WakeList), drops the mutex, and wakes them in panic-safe FIFO order without heap allocations.
The Core Data Structure: The 6-Level Timer Wheel
In a high-throughput network server, almost every incoming request sets a timeout that gets cancelled milliseconds later when a response arrives. While my naive BinaryHeap approach requires O(log N) to insert and cannot cheaply remove cancelled timers from the middle (O(N)), Tokio achieves both insertion and cancellation in O(1) time.
It does this using a Hierarchical Timing Wheel, an algorithm introduced in a 1987 paper by George Varghese and Tony Lauck titled “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility”.
The idea is modeled after a mechanical clock:
- Instead of keeping all deadlines in a sorted queue, you organize time into circular arrays (wheels) divided into fixed “slots”.
- Just like a clock has a second hand, a minute hand, and an hour hand, a hierarchical timer wheel has multiple levels:
- Level 0 (The second hand): Moves rapidly, handling near-term deadlines with 1ms resolution.
- Higher Levels (The minute/hour hands): Move slowly, handling distant deadlines with coarser resolution.
As time advances, timers on higher levels “cascade” down into lower levels until they finally land in Level 0 and fire. This same architecture powers both the Linux kernel’s timer wheel and Apache Kafka’s Request Purgatory.
Tokio’s 6-Level Clock Gearbox
In Tokio’s timer wheel, time is structured into 6 levels, with each level containing 64 slots (2^6):
Level 0: 64 slots × 1 ms = 64 ms total span
Level 1: 64 slots × 64 ms ≈ 4.1 seconds total span
Level 2: 64 slots × 4.1 sec ≈ 4.3 minutes total span
Level 3: 64 slots × 4.3 min ≈ 4.6 hours total span
Level 4: 64 slots × 4.6 hr ≈ 12.4 days total span
Level 5: 64 slots × 12.4 day ≈ 2.17 years total span
The time represented by a single slot at level N is:
slot_range(N) = 64^N milliseconds
Notice that a single full rotation of Level 5 spans 2.17 years (MAX_DURATION = 1 << 36 ms, or roughly 795 days).
Does this mean Tokio cannot handle timers beyond two years? Not at all. Timers in Tokio are unbounded (up to u64::MAX milliseconds, or roughly 584 million years). Instead of adding infinite levels to the wheel, Tokio treats Level 5 as a pseudo-ring buffer:
- Any timer scheduled further than 2.17 years into the future (exceeding one full Level 5 rotation) is placed directly into Level 5.
- When Level 5 completes a 2.17-year revolution and visits that slot,
process_expirationchecks the timer’s exact target deadline. - If the deadline is still years away, Tokio sees the timer has not expired yet and reinserts it right back into Level 5 for another lap.
- Once the remaining duration finally falls within 2.17 years of current time, the timer cascades down to lower levels just like any other.
By recycling Level 5 as an unbounded circular buffer, Tokio supports arbitrarily distant deadlines while keeping the entire wheel fixed at 6 levels of 64 slots (384 slots, or roughly 6 KB total), which is compact enough to live permanently inside the CPU’s L1 cache.
Ingesting a Timer: The Bitwise Odometer
When a task calls tokio::time::sleep(duration).await, Tokio converts its Instant deadline into a u64 tick (when, measured in milliseconds since the runtime started) and compares it against the wheel’s current tick (elapsed).
Now Tokio must answer: which of the 6 levels should hold this timer?
The naive approach to determine the level is to check whether elapsed and when fall within the same wheel boundary using an if/else chain:
// Naive approach: chained divisions and branches
fn level_for_naive(elapsed: u64, when: u64) -> usize {
if (elapsed / 64) == (when / 64) {
0 // Same 64ms epoch
} else if (elapsed / 4_096) == (when / 4_096) {
1 // Same 4.1-second epoch (64^2)
} else if (elapsed / 262_144) == (when / 262_144) {
2 // Same 4.3-minute epoch (64^3)
} else if (elapsed / 16_777_216) == (when / 16_777_216) {
3 // Same 4.6-hour epoch (64^4)
} else if (elapsed / 1_073_741_824) == (when / 1_073_741_824) {
4 // Same 12.4-day epoch (64^5)
} else {
5
}
}
In a high-throughput runtime, executing repeated 64-bit integer divisions and unpredictable if/else branches on every timer registration is expensive. Because each level is a power of 64 (2^6), Tokio replaces the entire if/else ladder by treating time as a binary odometer:
fn level_for(elapsed: u64, when: u64) -> usize {
const SLOT_MASK: u64 = (1 << 6) - 1;
let masked = elapsed ^ when | SLOT_MASK;
if masked >= MAX_DURATION {
// Fudge distant timers into the top level pseudo-ring buffer
return NUM_LEVELS - 1;
}
masked.ilog2() as usize / 6
}
Three simple bitwise steps make this work in roughly 4 CPU instructions:
A. The XOR (^) Odometer Trick
On a 4-dial car odometer, when the mileage ticks from 0123 to 0128, only the rightmost dial (3 → 8, Level 0) moves. When it rolls over from 0129 to 0130, the second dial (2 → 3, Level 1) clicks forward.
In binary, each 6-bit chunk represents a level (2^6 = 64):
Bit position: [63 .. 36] [35 .. 30] [29 .. 24] [23 .. 18] [17 .. 12] [11 .. 6] [5 .. 0]
────────── ────────── ────────── ────────── ────────── ───────── ────────
Target level: Level 5* Level 5 Level 4 Level 3 Level 2 Level 1 Level 0
(*clamped by masked >= MAX_DURATION)
The XOR operator (elapsed ^ when) outputs a 0 for every bit that hasn’t changed and a 1 for every bit that has. Taking the base-2 logarithm via masked.ilog2() finds the bit position of the highest 1 bit, and dividing by 6 maps that bit directly to the highest dial on the odometer that differs between elapsed and when.
B. The SLOT_MASK Safety Floor
Level 0 handles differences between 0 and 63 milliseconds (the bottom 6 bits). By OR-ing with SLOT_MASK (0b111111), Tokio forces the lowest 6 bits to always be 1.
Why? If a timer is scheduled for the exact current millisecond (when == elapsed), elapsed ^ when is 0. Calculating 0.ilog2() would panic. SLOT_MASK sets a hard floor so masked is always at least 63, keeping same-tick timers safely at Level 0.
C. The MAX_DURATION Ring-Buffer Cap
If the time difference exceeds 36 bits (masked >= MAX_DURATION, or roughly 2.17 years), Tokio avoids computing the logarithm and immediately returns NUM_LEVELS - 1 (Level 5), routing distant timers straight into the top-level pseudo-ring buffer.
D. Reading the Dial: slot_for(when, level)
Once level_for identifies which 6-bit gear on the odometer changed, Tokio still needs to know which of the 64 slots (0..63) on that gear to drop the timer into.
Think about how you would isolate a specific digit on a regular base-10 odometer, such as extracting the hundreds digit (3) from 1,357. First, you divide by 100 (10^2) to chop off the last two digits (1357 / 100 = 13). Then, you take the remainder after dividing by 10 (13 % 10 = 3).
In binary, shifting bits to the right (>>) is the exact same thing as integer division by a power of two: shifting right by 6 bits divides by 2^6 (64), shifting right by 12 bits divides by 2^12 (4,096), and in general shifting right by level * 6 bits divides when by 2^(level * 6) (that level’s slot width) to chop off all the lower odometer dials. Taking % 64 then grabs the remainder (0..63), giving us the exact slot on that dial:
fn slot_for(duration: u64, level: usize) -> usize {
((duration >> (level * 6)) % 64) as usize
}
Storing and Resetting Timers: Intrusive Linked Lists
Once level_for and slot_for pick the target level and slot index idx, Tokio needs a way to store the timer inside levels[level].slot[idx]. Because each level only has 64 slots, many timers will inevitably land on the same slot, so Tokio chains multiple timers together in a linked list under each slot.
In standard Rust collections, pushing to a LinkedList<T> allocates a heap Node containing prev, next, and value. Allocating and freeing millions of wrapper nodes as timeouts are created and cancelled would thrash the memory allocator.
Tokio avoids heap allocation on insertion by using an intrusive linked list:
pub(crate) struct TimerShared {
pointers: linked_list::Pointers<TimerShared>, // Intrusive prev/next pointers stored inline
registered_when: AtomicU64, // Tick where this node is currently slotted in the wheel
state: StateCell, // Holds the true target deadline (retrieved via true_when()) and Waker
_p: PhantomPinned,
}
impl TimerShared {
pub(super) fn true_when(&self) -> u64 {
self.state.when().expect("Timer already fired")
}
}
Instead of wrapping TimerShared in a separate node, the prev and next pointers live inside TimerShared itself. Inserting or cancelling a timer simply rewires raw NonNull<TimerShared> pointers in O(1) time with zero heap allocations.
Why TimerShared Needs PhantomPinned
Intrusive linked lists break two assumptions that Rust normally makes about structs:
- Structs can be moved in memory: In Rust, moving a value copies its bytes to a new memory address. If a
TimerSharednode moved while linked into a wheel slot, theprevandnextpointers on neighboring timers would instantly become dangling pointers. - Mutable references are exclusive (
noalias): Normally, when a task polls a future through a mutable reference, Rust tells its code-generation backend (LLVM) that no other pointer in the program can access that struct at the same time. In an intrusive list, that isn’t true, because the timer wheel holds rawprevandnextpointers toTimerSharedat the exact same time. If the compiler assumes exclusive access, it can reorder or optimize away pointer updates and silently corrupt the list.
Adding _p: PhantomPinned marks TimerShared as !Unpin, solving both problems at once: it locks the struct to a fixed memory address once pinned, and it turns off the exclusive-aliasing (noalias) optimization so every pointer read and write is emitted faithfully.
Why Timers Track Two Deadlines: registered_when vs true_when()
Looking at TimerShared above, you might wonder why Tokio stores a registered_when timestamp alongside the actual target deadline inside state: StateCell (retrieved via true_when()).
The reason comes down to the difference between coarse slot buckets and exact expiration times:
Coarse Wheel Buckets (
true_when()): Higher-level slots represent coarse time ranges rather than exact milliseconds. For example, a timer for tick95mssits in Level 1’s[64ms..128ms)bucket. When that bucket expires at tick64ms, the slot only knows its base timestamp (64ms), so the timer must remember its exact target insideStateCell(true_when() == 95ms) to know it still needs to cascade down rather than fire immediately.O(1)Resets and Cancellations (registered_when): If a task callssleep.reset(new_deadline)or cancels the timer, Tokio may need to unlink the node from its current slot. UpdatingStateCelloverwrites the target deadline, so Tokio preservesregistered_when(the timestamp used when the node was placed into the wheel) to locate and unlink the node from its old slot inO(1)time before re-inserting it.
Finding the Next Deadline: Hardware Bit Rotation
Once timers are sitting in the wheel, the driver needs to know how long it can go to sleep. To compute that timeout, each level must answer: “Starting from now, what is the next slot that actually contains a timer?”
Because each level is a circular ring of 64 slots, a naive search would loop from now_slot to 63 and wrap around from 0 to now_slot. Instead, Tokio packs each level’s occupancy into a single u64 bitmask (self.occupied, where Bit i = Slot i) and finds the next occupied slot in O(1) without loops:
fn next_occupied_slot(&self, now: u64) -> Option<usize> {
if self.occupied == 0 {
return None;
}
let now_slot: usize = (now / slot_range(self.level)) as usize;
let occupied: u64 = self.occupied.rotate_right(now_slot as u32);
let zeros: usize = occupied.trailing_zeros() as usize;
let slot: usize = (zeros + now_slot) % LEVEL_MULT;
Some(slot)
}
rotate_right(now_slot): Rotates the bitmask so our current position (now_slot) becomes the starting line at Bit 0. All upcoming slots now line up in clockwise order after it, with lower-indexed slots (0..now_slot) wrapping around to the upper bits.trailing_zeros(): Uses a single hardware instruction (tzcnt) to count how many zeros sit at the bottom of the register. This directly tells us how many slots forward we need to travel to reach the next timer.(zeros + now_slot) % 64: Adds that distance tonow_slotto get the final slot index.
To visualize this, imagine an 8-slot wheel where our clock hand is at Slot 5, and the only active timer is at Slot 1:
Before rotation (self.occupied = 0b0000_0010):
Bit position: Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
Slot index: Slot 7 Slot 6 Slot 5 Slot 4 Slot 3 Slot 2 Slot 1 Slot 0
Value: 0 0 0 0 0 0 1 0
[ NOW ] [TIMER]
1. rotate_right(5) shifts bits right by 5 (bringing Slot 5 to Bit 0 on the right):
Bit position: Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
Mapped slot: Slot 4 Slot 3 Slot 2 Slot 1 Slot 0 Slot 7 Slot 6 Slot 5
Value: 0 0 0 1 0 0 0 0
[TIMER] <--- 4 trailing zeros -> [ NOW ]
2. trailing_zeros(): 4 zeros on the right -> the timer is 4 steps ahead.
3. (5 + 4) % 8: 5 + 4 = 9 -> 9 % 8 = Slot 1.
Even though Slot 1 sat “behind” Slot 5 in array order, rotating the clock face so “now” sits at index 0 allows hardware trailing-zero detection to resolve circular wrap-around in a single instruction.
Who Turns the Wheel? TryLock<Driver>
Unlike my naive mini-rt timer, Tokio does not spawn a dedicated background timer thread, and there is no permanent “main thread” in its multi-threaded scheduler. All worker threads are equal peers sharing the timer wheel behind Mutex<InnerState>.
So who actually calls Wheel::poll(now) to advance time and cascade timers? Tokio splits this across two regimes:
Regime A: When Workers Are Idle (TryLock<Driver>)
In Tokio’s multi-threaded scheduler, the I/O and timer driver is guarded by a non-blocking TryLock<Driver>:
- The Winner (The Temporary Driver Thread): The first idle worker thread to park acquires
shared.driver.try_lock(). It querieswheel.next_expiration()and blocks inside the OS poller (epoll_wait/kevent) for that duration. - The Losers (
CondvarWorkers): Any other workers that run out of tasks failtry_lock()and sleep on a standardstd::sync::Condvar, waiting only for new tasks to be spawned.
Because TryLock<Driver> is exclusive, at most one worker thread in the entire runtime is ever sleeping on the timer wheel deadline at any time.
Regime B: When Workers Are Busy (Every 61 Ticks)
What if all worker threads are 100% busy polling CPU-heavy tasks and never park? To keep timers and I/O from starving, every worker increments a tick counter on each scheduler step. Every 61 ticks (event_interval = 61), a busy worker tries to lock the driver and calls driver.park_timeout(Duration::ZERO), performing a non-blocking poll of the OS selector and advancing the timer wheel up to now before immediately resuming task execution.
Cascading Timers
When the driver turns the wheel via Wheel::poll(now), it calls next_expiration() to find the earliest occupied slot across all levels (Expiration { level, slot, deadline }). Once that slot’s deadline is reached (expiration.deadline <= now), process_expiration() drains all entries from the slot and checks each timer’s exact target deadline:
- If
entry.true_when() <= deadline: The timer is due now, so Tokio marks it as pending (item.mark_pending(deadline)) and pushes it intoself.pendingto be fired. - If
entry.true_when() > deadline: The timer is not due yet (for example, a timer for tick95mssitting in Level 1’s[64ms..128ms)slot when tick64msarrives). Tokio recomputeslevel_for(deadline, entry.true_when())and cascades the entry down into a lower, finer-grained level.
Preempting a Sleeping Driver: next_wake and unpark
When the driver-holding thread parks in the OS poller (epoll_wait / kevent) for the next timer deadline, another active worker thread might register a shorter timer while it is asleep. For example, if Worker 1 blocks on a 100ms deadline and 2ms later Worker 2 registers a 10ms timer, Worker 2 must interrupt Worker 1’s sleep so the 10ms timer does not fire 90ms late:
sequenceDiagram
autonumber
participant W1 as Worker 1 (Driver Holder)
participant D as OS Poller (epoll / kqueue)
participant W2 as Worker 2 (Active Task)
participant T as Timer Wheel & next_wake
Note over W1,D: Worker 1 is idle and acquires driver.try_lock()
W1->>T: next_expiration() -> 100ms
Note over T: Stores next_wake = Some(100)
W1->>D: Blocks in epoll_wait(timeout = 100ms)
Note over W2: Worker 2 spawns sleep(10ms)
W2->>T: Inserts 10ms timer into Wheel
Note over T: 10ms < next_wake (100ms)
W2->>D: Calls unpark.unpark() (mio::Waker)
D-->>W1: Interrupts epoll_wait immediately
W1->>T: Re-polls wheel & checks next_expiration() -> 10ms
Note over T: Updates next_wake = Some(10)
W1->>D: Re-enters epoll_wait(timeout = 10ms)
Worker 1 caches its wakeup tick inside lock.next_wake before blocking in the OS poller. Whenever another worker inserts a timer into the wheel, it compares the new timer’s tick when against lock.next_wake:
match unsafe { lock.wheel.insert(entry) } {
Ok(when) => {
if lock
.next_wake
.is_none_or(|next_wake| when < next_wake.get())
{
unpark.unpark();
}
None
}
// ...
}
Only when when < next_wake (or when next_wake is None, meaning the driver parked indefinitely with an empty wheel) does Worker 2 call unpark.unpark() (mio::Waker, backed by eventfd on Linux and EVFILT_USER on macOS) to wake the sleeping driver thread. If when >= next_wake, Worker 2 skips the syscall entirely because Worker 1 is already scheduled to wake up earlier.
Waking Tasks Safely: WakeList and DropGuard
Once expired timers are popped from Wheel::poll(now), Tokio extracts their Wakers and wakes the sleeping tasks. However, calling waker.wake() while holding Mutex<InnerState> is dangerous: a custom Waker could immediately register or cancel another timer on the same thread, deadlocking on InnerState.
To wake tasks outside the mutex with zero heap allocations, Tokio collects wakers into a local buffer called WakeList:
const NUM_WAKERS: usize = 32;
pub(crate) struct WakeList {
inner: [MaybeUninit<Waker>; NUM_WAKERS],
curr: usize,
}
Whenever waker_list fills up (32 wakers), the driver temporarily drops the mutex, fires the batch, and re-acquires the lock to continue polling the wheel:
let mut waker_list = WakeList::new();
let mut lock = self.inner.lock();
while let Some(entry) = lock.wheel.poll(now) {
if let Some(waker) = unsafe { entry.fire(Ok(())) } {
waker_list.push(waker);
if !waker_list.can_push() {
// Wake a batch of wakers with the lock temporarily dropped to avoid deadlock.
drop(lock);
waker_list.wake_all();
lock = self.inner.lock();
}
}
}
drop(lock);
waker_list.wake_all();
Why wake_all() Uses Raw Pointers and DropGuard
Inside WakeList::wake_all(), instead of a simple for i in 0..self.curr loop, Tokio uses a raw-pointer DropGuard:
pub(crate) fn wake_all(&mut self) {
struct DropGuard {
start: *mut Waker,
end: *mut Waker,
}
impl Drop for DropGuard {
fn drop(&mut self) {
let len = unsafe { self.end.offset_from(self.start) } as usize;
let slice = ptr::slice_from_raw_parts_mut(self.start, len);
unsafe { ptr::drop_in_place(slice) };
}
}
let mut guard = {
let start = self.inner.as_mut_ptr().cast::<Waker>();
let end = unsafe { start.add(self.curr) };
// Transfer drop responsibility of the wakers to DropGuard
self.curr = 0;
DropGuard { start, end }
};
while !ptr::eq(guard.start, guard.end) {
let waker = unsafe { ptr::read(guard.start) };
guard.start = unsafe { guard.start.add(1) };
// If this panics, `guard` will clean up the remaining wakers
waker.wake();
}
}
At first glance, DropGuard looks like overkill for iterating over a 32-element array, until we trace what happens if a waker panics:
- Why a naive
forloop causes a double-free:waker.wake()consumes theWakerby value and can panic. If a naivefor i in 0..self.currloop panicked at index 2 (out of 5), stack unwinding would runWakeList::dropon0..self.curr, causing a double-free on indices0and1after.wake()already consumed them. - Why not just pop from the back (LIFO vs. FIFO fairness): We could avoid that double-free with a single counter by popping from the back (
self.curr -= 1before each.wake()), since0..self.currwould always track the remaining unconsumed items. However, LIFO order is unfair because the earliest-expiring timer would be woken last, so we need to consume the array from front to back (FIFO).
DropGuard gives us FIFO wake order without risking a double-free by transferring the drop obligation out of WakeList. Setting self.curr = 0 upfront resets WakeList for reuse and ensures WakeList::drop does nothing if a panic unwinds the stack. Meanwhile, guard.start advances from front to back before each waker.wake() call so DropGuard::drop only ever cleans up the remaining unconsumed slice [guard.start..guard.end].
Conclusion
Tracing tokio::time::sleep from end to end turned what initially looked like cryptic bit-twiddling into a cohesive engineering story:
- A 6-level × 64-slot hierarchical wheel gives
O(1)timer insertion and cancellation across an unbounded time horizon by turning Level 5 into a pseudo-ring buffer and cascading coarse buckets down to 1ms precision as deadlines approach. - Bitwise odometers (
elapsed ^ when | SLOT_MASK) and bit rotations (rotate_right+tzcnt) replace loops and branches with constant-time bit math. - Intrusive linked lists (
TimerShared) and fixed-capacity wake buffers (WakeListandDropGuard) eliminate heap allocations on the hot path while keeping wakeups FIFO-fair and panic-safe. - Cooperative driver locking (
TryLock<Driver>,next_wake, andunpark) keeps timers accurate across worker threads without spawning a dedicated timer thread.
Unpacking how Tokio’s timer wheel works under the hood got me excited to try building a simplified version of it myself. My next experiment is to replace the naive BinaryHeap timer in mini-rt with a hierarchical timer wheel of my own.
References
- Varghese, G., & Lauck, T. (1987): “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility”, Proceedings of the Eleventh ACM Symposium on Operating Systems Principles (SOSP ‘87), 25-38 (DOI:
10.1145/41457.37504). - Linux Kernel: The hierarchical timer wheel subsystem for low-resolution kernel timeouts.
- Apache Kafka: The hierarchical timing wheel implementation in Request Purgatory.
- Tokio Runtime Source: The time driver, hierarchical wheel, and
WakeListmodules in the Tokio repository.