tokio/runtime/time/wheel/
level.rs

1use crate::runtime::time::{TimerHandle, TimerShared};
2use crate::util::linked_list::LinkedList;
3
4use std::{array, fmt, ptr::NonNull};
5
6/// Wheel for a single level in the timer. This wheel contains 64 slots.
7pub(crate) struct Level {
8    level: usize,
9
10    /// Bit field tracking which slots currently contain entries.
11    ///
12    /// Using a bit field to track slots that contain entries allows avoiding a
13    /// scan to find entries. This field is updated when entries are added or
14    /// removed from a slot.
15    ///
16    /// The least-significant bit represents slot zero.
17    occupied: u64,
18
19    /// Slots. We access these via the EntryInner `current_list` as well, so this needs to be an `UnsafeCell`.
20    slot: [LinkedList<TimerShared>; LEVEL_MULT],
21}
22
23/// Indicates when a slot must be processed next.
24#[derive(Debug)]
25pub(crate) struct Expiration {
26    /// The level containing the slot.
27    pub(crate) level: usize,
28
29    /// The slot index.
30    pub(crate) slot: usize,
31
32    /// The instant at which the slot needs to be processed.
33    pub(crate) deadline: u64,
34}
35
36/// Level multiplier.
37///
38/// Being a power of 2 is very important.
39const LEVEL_MULT: usize = 64;
40
41impl Level {
42    pub(crate) fn new(level: usize) -> Level {
43        Level {
44            level,
45            occupied: 0,
46            slot: array::from_fn(|_| LinkedList::default()),
47        }
48    }
49
50    /// Finds the slot that needs to be processed next and returns the slot and
51    /// `Instant` at which this slot must be processed.
52    pub(crate) fn next_expiration(&self, now: u64) -> Option<Expiration> {
53        // Use the `occupied` bit field to get the index of the next slot that
54        // needs to be processed.
55        let slot = self.next_occupied_slot(now)?;
56
57        // From the slot index, calculate the `Instant` at which it needs to be
58        // processed. This value *must* be in the future with respect to `now`.
59
60        let level_range = level_range(self.level);
61        let slot_range = slot_range(self.level);
62
63        // Compute the start date of the current level by masking the low bits
64        // of `now` (`level_range` is a power of 2).
65        let level_start = now & !(level_range - 1);
66        let mut deadline = level_start + slot as u64 * slot_range;
67
68        if deadline <= now {
69            // A timer is in a slot "prior" to the current time. This can occur
70            // because we do not have an infinite hierarchy of timer levels, and
71            // eventually a timer scheduled for a very distant time might end up
72            // being placed in a slot that is beyond the end of all of the
73            // arrays.
74            //
75            // To deal with this, we first limit timers to being scheduled no
76            // more than MAX_DURATION ticks in the future; that is, they're at
77            // most one rotation of the top level away. Then, we force timers
78            // that logically would go into the top+1 level, to instead go into
79            // the top level's slots.
80            //
81            // What this means is that the top level's slots act as a
82            // pseudo-ring buffer, and we rotate around them indefinitely. If we
83            // compute a deadline before now, and it's the top level, it
84            // therefore means we're actually looking at a slot in the future.
85            debug_assert_eq!(self.level, super::NUM_LEVELS - 1);
86
87            deadline += level_range;
88        }
89
90        debug_assert!(
91            deadline >= now,
92            "deadline={:016X}; now={:016X}; level={}; lr={:016X}, sr={:016X}, slot={}; occupied={:b}",
93            deadline,
94            now,
95            self.level,
96            level_range,
97            slot_range,
98            slot,
99            self.occupied
100        );
101
102        Some(Expiration {
103            level: self.level,
104            slot,
105            deadline,
106        })
107    }
108
109    fn next_occupied_slot(&self, now: u64) -> Option<usize> {
110        if self.occupied == 0 {
111            return None;
112        }
113
114        // Get the slot for now using Maths
115        let now_slot = (now / slot_range(self.level)) as usize;
116        let occupied = self.occupied.rotate_right(now_slot as u32);
117        let zeros = occupied.trailing_zeros() as usize;
118        let slot = (zeros + now_slot) % LEVEL_MULT;
119
120        Some(slot)
121    }
122
123    pub(crate) unsafe fn add_entry(&mut self, item: TimerHandle) {
124        let slot = slot_for(unsafe { item.registered_when() }, self.level);
125
126        self.slot[slot].push_front(item);
127
128        self.occupied |= occupied_bit(slot);
129    }
130
131    pub(crate) unsafe fn remove_entry(&mut self, item: NonNull<TimerShared>) {
132        let slot = slot_for(unsafe { item.as_ref().registered_when() }, self.level);
133
134        unsafe { self.slot[slot].remove(item) };
135        if self.slot[slot].is_empty() {
136            // The bit is currently set
137            debug_assert!(self.occupied & occupied_bit(slot) != 0);
138
139            // Unset the bit
140            self.occupied ^= occupied_bit(slot);
141        }
142    }
143
144    pub(crate) fn take_slot(&mut self, slot: usize) -> LinkedList<TimerShared> {
145        self.occupied &= !occupied_bit(slot);
146
147        std::mem::take(&mut self.slot[slot])
148    }
149}
150
151impl fmt::Debug for Level {
152    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
153        fmt.debug_struct("Level")
154            .field("occupied", &self.occupied)
155            .finish()
156    }
157}
158
159fn occupied_bit(slot: usize) -> u64 {
160    1 << slot
161}
162
163fn slot_range(level: usize) -> u64 {
164    LEVEL_MULT.pow(level as u32) as u64
165}
166
167fn level_range(level: usize) -> u64 {
168    LEVEL_MULT as u64 * slot_range(level)
169}
170
171/// Converts a duration (milliseconds) and a level to a slot position.
172fn slot_for(duration: u64, level: usize) -> usize {
173    ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
174}
175
176#[cfg(all(test, not(loom)))]
177mod test {
178    use super::*;
179
180    #[test]
181    fn test_slot_for() {
182        for pos in 0..64 {
183            assert_eq!(pos as usize, slot_for(pos, 0));
184        }
185
186        for level in 1..5 {
187            for pos in level..64 {
188                let a = pos * 64_usize.pow(level as u32);
189                assert_eq!(pos, slot_for(a as u64, level));
190            }
191        }
192    }
193}
tokio/runtime/time/wheel/level.rs

tokio/runtime/time/wheel/
level.rs
