1 use crate::time::wheel::Stack;
2
3 use std::fmt;
4
5 /// Wheel for a single level in the timer. This wheel contains 64 slots.
6 pub(crate) struct Level<T> {
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
19 slot: [T; LEVEL_MULT],
20 }
21
22 /// Indicates when a slot must be processed next.
23 #[derive(Debug)]
24 pub(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.
38 const LEVEL_MULT: usize = 64;
39
40 impl<T: Stack> Level<T> {
new(level: usize) -> Level<T>41 pub(crate) fn new(level: usize) -> Level<T> {
42 // Rust's derived implementations for arrays require that the value
43 // contained by the array be `Copy`. So, here we have to manually
44 // initialize every single slot.
45 macro_rules! s {
46 () => {
47 T::default()
48 };
49 }
50
51 Level {
52 level,
53 occupied: 0,
54 slot: [
55 // It does not look like the necessary traits are
56 // derived for [T; 64].
57 s!(),
58 s!(),
59 s!(),
60 s!(),
61 s!(),
62 s!(),
63 s!(),
64 s!(),
65 s!(),
66 s!(),
67 s!(),
68 s!(),
69 s!(),
70 s!(),
71 s!(),
72 s!(),
73 s!(),
74 s!(),
75 s!(),
76 s!(),
77 s!(),
78 s!(),
79 s!(),
80 s!(),
81 s!(),
82 s!(),
83 s!(),
84 s!(),
85 s!(),
86 s!(),
87 s!(),
88 s!(),
89 s!(),
90 s!(),
91 s!(),
92 s!(),
93 s!(),
94 s!(),
95 s!(),
96 s!(),
97 s!(),
98 s!(),
99 s!(),
100 s!(),
101 s!(),
102 s!(),
103 s!(),
104 s!(),
105 s!(),
106 s!(),
107 s!(),
108 s!(),
109 s!(),
110 s!(),
111 s!(),
112 s!(),
113 s!(),
114 s!(),
115 s!(),
116 s!(),
117 s!(),
118 s!(),
119 s!(),
120 s!(),
121 ],
122 }
123 }
124
125 /// Finds the slot that needs to be processed next and returns the slot and
126 /// `Instant` at which this slot must be processed.
next_expiration(&self, now: u64) -> Option<Expiration>127 pub(crate) fn next_expiration(&self, now: u64) -> Option<Expiration> {
128 // Use the `occupied` bit field to get the index of the next slot that
129 // needs to be processed.
130 let slot = match self.next_occupied_slot(now) {
131 Some(slot) => slot,
132 None => return None,
133 };
134
135 // From the slot index, calculate the `Instant` at which it needs to be
136 // processed. This value *must* be in the future with respect to `now`.
137
138 let level_range = level_range(self.level);
139 let slot_range = slot_range(self.level);
140
141 // TODO: This can probably be simplified w/ power of 2 math
142 let level_start = now - (now % level_range);
143 let mut deadline = level_start + slot as u64 * slot_range;
144 if deadline < now {
145 // A timer is in a slot "prior" to the current time. This can occur
146 // because we do not have an infinite hierarchy of timer levels, and
147 // eventually a timer scheduled for a very distant time might end up
148 // being placed in a slot that is beyond the end of all of the
149 // arrays.
150 //
151 // To deal with this, we first limit timers to being scheduled no
152 // more than MAX_DURATION ticks in the future; that is, they're at
153 // most one rotation of the top level away. Then, we force timers
154 // that logically would go into the top+1 level, to instead go into
155 // the top level's slots.
156 //
157 // What this means is that the top level's slots act as a
158 // pseudo-ring buffer, and we rotate around them indefinitely. If we
159 // compute a deadline before now, and it's the top level, it
160 // therefore means we're actually looking at a slot in the future.
161 debug_assert_eq!(self.level, super::NUM_LEVELS - 1);
162
163 deadline += level_range;
164 }
165 debug_assert!(
166 deadline >= now,
167 "deadline={:016X}; now={:016X}; level={}; slot={}; occupied={:b}",
168 deadline,
169 now,
170 self.level,
171 slot,
172 self.occupied
173 );
174
175 Some(Expiration {
176 level: self.level,
177 slot,
178 deadline,
179 })
180 }
181
next_occupied_slot(&self, now: u64) -> Option<usize>182 fn next_occupied_slot(&self, now: u64) -> Option<usize> {
183 if self.occupied == 0 {
184 return None;
185 }
186
187 // Get the slot for now using Maths
188 let now_slot = (now / slot_range(self.level)) as usize;
189 let occupied = self.occupied.rotate_right(now_slot as u32);
190 let zeros = occupied.trailing_zeros() as usize;
191 let slot = (zeros + now_slot) % 64;
192
193 Some(slot)
194 }
195
add_entry(&mut self, when: u64, item: T::Owned, store: &mut T::Store)196 pub(crate) fn add_entry(&mut self, when: u64, item: T::Owned, store: &mut T::Store) {
197 let slot = slot_for(when, self.level);
198
199 self.slot[slot].push(item, store);
200 self.occupied |= occupied_bit(slot);
201 }
202
remove_entry(&mut self, when: u64, item: &T::Borrowed, store: &mut T::Store)203 pub(crate) fn remove_entry(&mut self, when: u64, item: &T::Borrowed, store: &mut T::Store) {
204 let slot = slot_for(when, self.level);
205
206 self.slot[slot].remove(item, store);
207
208 if self.slot[slot].is_empty() {
209 // The bit is currently set
210 debug_assert!(self.occupied & occupied_bit(slot) != 0);
211
212 // Unset the bit
213 self.occupied ^= occupied_bit(slot);
214 }
215 }
216
pop_entry_slot(&mut self, slot: usize, store: &mut T::Store) -> Option<T::Owned>217 pub(crate) fn pop_entry_slot(&mut self, slot: usize, store: &mut T::Store) -> Option<T::Owned> {
218 let ret = self.slot[slot].pop(store);
219
220 if ret.is_some() && self.slot[slot].is_empty() {
221 // The bit is currently set
222 debug_assert!(self.occupied & occupied_bit(slot) != 0);
223
224 self.occupied ^= occupied_bit(slot);
225 }
226
227 ret
228 }
229
peek_entry_slot(&self, slot: usize) -> Option<T::Owned>230 pub(crate) fn peek_entry_slot(&self, slot: usize) -> Option<T::Owned> {
231 self.slot[slot].peek()
232 }
233 }
234
235 impl<T> fmt::Debug for Level<T> {
fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result236 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
237 fmt.debug_struct("Level")
238 .field("occupied", &self.occupied)
239 .finish()
240 }
241 }
242
occupied_bit(slot: usize) -> u64243 fn occupied_bit(slot: usize) -> u64 {
244 1 << slot
245 }
246
slot_range(level: usize) -> u64247 fn slot_range(level: usize) -> u64 {
248 LEVEL_MULT.pow(level as u32) as u64
249 }
250
level_range(level: usize) -> u64251 fn level_range(level: usize) -> u64 {
252 LEVEL_MULT as u64 * slot_range(level)
253 }
254
255 /// Convert a duration (milliseconds) and a level to a slot position
slot_for(duration: u64, level: usize) -> usize256 fn slot_for(duration: u64, level: usize) -> usize {
257 ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
258 }
259
260 #[cfg(all(test, not(loom)))]
261 mod test {
262 use super::*;
263
264 #[test]
test_slot_for()265 fn test_slot_for() {
266 for pos in 0..64 {
267 assert_eq!(pos as usize, slot_for(pos, 0));
268 }
269
270 for level in 1..5 {
271 for pos in level..64 {
272 let a = pos * 64_usize.pow(level as u32);
273 assert_eq!(pos as usize, slot_for(a as u64, level));
274 }
275 }
276 }
277 }
278