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