1 use crate::time::driver::TimerHandle;
2
3 use crate::time::driver::{EntryList, TimerShared};
4
5 use std::{fmt, ptr::NonNull};
6
7 /// Wheel for a single level in the timer. This wheel contains 64 slots.
8 pub(crate) struct Level {
9 level: usize,
10
11 /// Bit field tracking which slots currently contain entries.
12 ///
13 /// Using a bit field to track slots that contain entries allows avoiding a
14 /// scan to find entries. This field is updated when entries are added or
15 /// removed from a slot.
16 ///
17 /// The least-significant bit represents slot zero.
18 occupied: u64,
19
20 /// Slots. We access these via the EntryInner `current_list` as well, so this needs to be an UnsafeCell.
21 slot: [EntryList; LEVEL_MULT],
22 }
23
24 /// Indicates when a slot must be processed next.
25 #[derive(Debug)]
26 pub(crate) struct Expiration {
27 /// The level containing the slot.
28 pub(crate) level: usize,
29
30 /// The slot index.
31 pub(crate) slot: usize,
32
33 /// The instant at which the slot needs to be processed.
34 pub(crate) deadline: u64,
35 }
36
37 /// Level multiplier.
38 ///
39 /// Being a power of 2 is very important.
40 const LEVEL_MULT: usize = 64;
41
42 impl Level {
new(level: usize) -> Level43 pub(crate) fn new(level: usize) -> Level {
44 // A value has to be Copy in order to use syntax like:
45 // let stack = Stack::default();
46 // ...
47 // slots: [stack; 64],
48 //
49 // Alternatively, since Stack is Default one can
50 // use syntax like:
51 // let slots: [Stack; 64] = Default::default();
52 //
53 // However, that is only supported for arrays of size
54 // 32 or fewer. So in our case we have to explicitly
55 // invoke the constructor for each array element.
56 let ctor = || EntryList::default();
57
58 Level {
59 level,
60 occupied: 0,
61 slot: [
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 ctor(),
125 ctor(),
126 ],
127 }
128 }
129
130 /// Finds the slot that needs to be processed next and returns the slot and
131 /// `Instant` at which this slot must be processed.
next_expiration(&self, now: u64) -> Option<Expiration>132 pub(crate) fn next_expiration(&self, now: u64) -> Option<Expiration> {
133 // Use the `occupied` bit field to get the index of the next slot that
134 // needs to be processed.
135 let slot = match self.next_occupied_slot(now) {
136 Some(slot) => slot,
137 None => return None,
138 };
139
140 // From the slot index, calculate the `Instant` at which it needs to be
141 // processed. This value *must* be in the future with respect to `now`.
142
143 let level_range = level_range(self.level);
144 let slot_range = slot_range(self.level);
145
146 // TODO: This can probably be simplified w/ power of 2 math
147 let level_start = now - (now % level_range);
148 let mut deadline = level_start + slot as u64 * slot_range;
149
150 if deadline <= now {
151 // A timer is in a slot "prior" to the current time. This can occur
152 // because we do not have an infinite hierarchy of timer levels, and
153 // eventually a timer scheduled for a very distant time might end up
154 // being placed in a slot that is beyond the end of all of the
155 // arrays.
156 //
157 // To deal with this, we first limit timers to being scheduled no
158 // more than MAX_DURATION ticks in the future; that is, they're at
159 // most one rotation of the top level away. Then, we force timers
160 // that logically would go into the top+1 level, to instead go into
161 // the top level's slots.
162 //
163 // What this means is that the top level's slots act as a
164 // pseudo-ring buffer, and we rotate around them indefinitely. If we
165 // compute a deadline before now, and it's the top level, it
166 // therefore means we're actually looking at a slot in the future.
167 debug_assert_eq!(self.level, super::NUM_LEVELS - 1);
168
169 deadline += level_range;
170 }
171
172 debug_assert!(
173 deadline >= now,
174 "deadline={:016X}; now={:016X}; level={}; lr={:016X}, sr={:016X}, slot={}; occupied={:b}",
175 deadline,
176 now,
177 self.level,
178 level_range,
179 slot_range,
180 slot,
181 self.occupied
182 );
183
184 Some(Expiration {
185 level: self.level,
186 slot,
187 deadline,
188 })
189 }
190
next_occupied_slot(&self, now: u64) -> Option<usize>191 fn next_occupied_slot(&self, now: u64) -> Option<usize> {
192 if self.occupied == 0 {
193 return None;
194 }
195
196 // Get the slot for now using Maths
197 let now_slot = (now / slot_range(self.level)) as usize;
198 let occupied = self.occupied.rotate_right(now_slot as u32);
199 let zeros = occupied.trailing_zeros() as usize;
200 let slot = (zeros + now_slot) % 64;
201
202 Some(slot)
203 }
204
add_entry(&mut self, item: TimerHandle)205 pub(crate) unsafe fn add_entry(&mut self, item: TimerHandle) {
206 let slot = slot_for(item.cached_when(), self.level);
207
208 self.slot[slot].push_front(item);
209
210 self.occupied |= occupied_bit(slot);
211 }
212
remove_entry(&mut self, item: NonNull<TimerShared>)213 pub(crate) unsafe fn remove_entry(&mut self, item: NonNull<TimerShared>) {
214 let slot = slot_for(unsafe { item.as_ref().cached_when() }, self.level);
215
216 unsafe { self.slot[slot].remove(item) };
217 if self.slot[slot].is_empty() {
218 // The bit is currently set
219 debug_assert!(self.occupied & occupied_bit(slot) != 0);
220
221 // Unset the bit
222 self.occupied ^= occupied_bit(slot);
223 }
224 }
225
take_slot(&mut self, slot: usize) -> EntryList226 pub(crate) fn take_slot(&mut self, slot: usize) -> EntryList {
227 self.occupied &= !occupied_bit(slot);
228
229 std::mem::take(&mut self.slot[slot])
230 }
231 }
232
233 impl fmt::Debug for Level {
fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result234 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
235 fmt.debug_struct("Level")
236 .field("occupied", &self.occupied)
237 .finish()
238 }
239 }
240
occupied_bit(slot: usize) -> u64241 fn occupied_bit(slot: usize) -> u64 {
242 1 << slot
243 }
244
slot_range(level: usize) -> u64245 fn slot_range(level: usize) -> u64 {
246 LEVEL_MULT.pow(level as u32) as u64
247 }
248
level_range(level: usize) -> u64249 fn level_range(level: usize) -> u64 {
250 LEVEL_MULT as u64 * slot_range(level)
251 }
252
253 /// Convert a duration (milliseconds) and a level to a slot position
slot_for(duration: u64, level: usize) -> usize254 fn slot_for(duration: u64, level: usize) -> usize {
255 ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
256 }
257
258 #[cfg(all(test, not(loom)))]
259 mod test {
260 use super::*;
261
262 #[test]
test_slot_for()263 fn test_slot_for() {
264 for pos in 0..64 {
265 assert_eq!(pos as usize, slot_for(pos, 0));
266 }
267
268 for level in 1..5 {
269 for pos in level..64 {
270 let a = pos * 64_usize.pow(level as u32);
271 assert_eq!(pos as usize, slot_for(a as u64, level));
272 }
273 }
274 }
275 }
276