1use crate::runtime::time::{EntryList, TimerHandle, TimerShared};
2
3use std::{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 // A value has to be Copy in order to use syntax like:
43 // let stack = Stack::default();
44 // ...
45 // slots: [stack; 64],
46 //
47 // Alternatively, since Stack is Default one can
48 // use syntax like:
49 // let slots: [Stack; 64] = Default::default();
50 //
51 // However, that is only supported for arrays of size
52 // 32 or fewer. So in our case we have to explicitly
53 // invoke the constructor for each array element.
54 let ctor = EntryList::default;
55
56 Level {
57 level,
58 occupied: 0,
59 slot: [
60 ctor(),
61 ctor(),
62 ctor(),
63 ctor(),
64 ctor(),
65 ctor(),
66 ctor(),
67 ctor(),
68 ctor(),
69 ctor(),
70 ctor(),
71 ctor(),
72 ctor(),
73 ctor(),
74 ctor(),
75 ctor(),
76 ctor(),
77 ctor(),
78 ctor(),
79 ctor(),
80 ctor(),
81 ctor(),
82 ctor(),
83 ctor(),
84 ctor(),
85 ctor(),
86 ctor(),
87 ctor(),
88 ctor(),
89 ctor(),
90 ctor(),
91 ctor(),
92 ctor(),
93 ctor(),
94 ctor(),
95 ctor(),
96 ctor(),
97 ctor(),
98 ctor(),
99 ctor(),
100 ctor(),
101 ctor(),
102 ctor(),
103 ctor(),
104 ctor(),
105 ctor(),
106 ctor(),
107 ctor(),
108 ctor(),
109 ctor(),
110 ctor(),
111 ctor(),
112 ctor(),
113 ctor(),
114 ctor(),
115 ctor(),
116 ctor(),
117 ctor(),
118 ctor(),
119 ctor(),
120 ctor(),
121 ctor(),
122 ctor(),
123 ctor(),
124 ],
125 }
126 }
127
128 /// Finds the slot that needs to be processed next and returns the slot and
129 /// `Instant` at which this slot must be processed.
130 pub(crate) fn next_expiration(&self, now: u64) -> Option<Expiration> {
131 // Use the `occupied` bit field to get the index of the next slot that
132 // needs to be processed.
133 let slot = match self.next_occupied_slot(now) {
134 Some(slot) => slot,
135 None => return None,
136 };
137
138 // From the slot index, calculate the `Instant` at which it needs to be
139 // processed. This value *must* be in the future with respect to `now`.
140
141 let level_range = level_range(self.level);
142 let slot_range = slot_range(self.level);
143
144 // Compute the start date of the current level by masking the low bits
145 // of `now` (`level_range` is a power of 2).
146 let level_start = now & !(level_range - 1);
147 let mut deadline = level_start + slot as u64 * slot_range;
148
149 if deadline <= now {
150 // A timer is in a slot "prior" to the current time. This can occur
151 // because we do not have an infinite hierarchy of timer levels, and
152 // eventually a timer scheduled for a very distant time might end up
153 // being placed in a slot that is beyond the end of all of the
154 // arrays.
155 //
156 // To deal with this, we first limit timers to being scheduled no
157 // more than MAX_DURATION ticks in the future; that is, they're at
158 // most one rotation of the top level away. Then, we force timers
159 // that logically would go into the top+1 level, to instead go into
160 // the top level's slots.
161 //
162 // What this means is that the top level's slots act as a
163 // pseudo-ring buffer, and we rotate around them indefinitely. If we
164 // compute a deadline before now, and it's the top level, it
165 // therefore means we're actually looking at a slot in the future.
166 debug_assert_eq!(self.level, super::NUM_LEVELS - 1);
167
168 deadline += level_range;
169 }
170
171 debug_assert!(
172 deadline >= now,
173 "deadline={:016X}; now={:016X}; level={}; lr={:016X}, sr={:016X}, slot={}; occupied={:b}",
174 deadline,
175 now,
176 self.level,
177 level_range,
178 slot_range,
179 slot,
180 self.occupied
181 );
182
183 Some(Expiration {
184 level: self.level,
185 slot,
186 deadline,
187 })
188 }
189
190 fn next_occupied_slot(&self, now: u64) -> Option<usize> {
191 if self.occupied == 0 {
192 return None;
193 }
194
195 // Get the slot for now using Maths
196 let now_slot = (now / slot_range(self.level)) as usize;
197 let occupied = self.occupied.rotate_right(now_slot as u32);
198 let zeros = occupied.trailing_zeros() as usize;
199 let slot = (zeros + now_slot) % 64;
200
201 Some(slot)
202 }
203
204 pub(crate) unsafe fn add_entry(&mut self, item: TimerHandle) {
205 let slot = slot_for(item.cached_when(), self.level);
206
207 self.slot[slot].push_front(item);
208
209 self.occupied |= occupied_bit(slot);
210 }
211
212 pub(crate) unsafe fn remove_entry(&mut self, item: NonNull<TimerShared>) {
213 let slot = slot_for(unsafe { item.as_ref().cached_when() }, self.level);
214
215 unsafe { self.slot[slot].remove(item) };
216 if self.slot[slot].is_empty() {
217 // The bit is currently set
218 debug_assert!(self.occupied & occupied_bit(slot) != 0);
219
220 // Unset the bit
221 self.occupied ^= occupied_bit(slot);
222 }
223 }
224
225 pub(crate) fn take_slot(&mut self, slot: usize) -> EntryList {
226 self.occupied &= !occupied_bit(slot);
227
228 std::mem::take(&mut self.slot[slot])
229 }
230}
231
232impl fmt::Debug for Level {
233 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
234 fmt&mut DebugStruct<'_, '_>.debug_struct("Level")
235 .field(name:"occupied", &self.occupied)
236 .finish()
237 }
238}
239
240fn occupied_bit(slot: usize) -> u64 {
241 1 << slot
242}
243
244fn slot_range(level: usize) -> u64 {
245 LEVEL_MULT.pow(exp:level as u32) as u64
246}
247
248fn level_range(level: usize) -> u64 {
249 LEVEL_MULT as u64 * slot_range(level)
250}
251
252/// Converts a duration (milliseconds) and a level to a slot position.
253fn slot_for(duration: u64, level: usize) -> usize {
254 ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
255}
256
257#[cfg(all(test, not(loom)))]
258mod test {
259 use super::*;
260
261 #[test]
262 fn test_slot_for() {
263 for pos in 0..64 {
264 assert_eq!(pos as usize, slot_for(pos, 0));
265 }
266
267 for level in 1..5 {
268 for pos in level..64 {
269 let a = pos * 64_usize.pow(level as u32);
270 assert_eq!(pos as usize, slot_for(a as u64, level));
271 }
272 }
273 }
274}
275