1 | use crate::runtime::time::{EntryList, TimerHandle, TimerShared}; |
2 | |
3 | use std::{fmt, ptr::NonNull}; |
4 | |
5 | /// Wheel for a single level in the timer. This wheel contains 64 slots. |
6 | pub(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)] |
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 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 | |
232 | impl fmt::Debug for Level { |
233 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { |
234 | fmt.debug_struct("Level" ) |
235 | .field("occupied" , &self.occupied) |
236 | .finish() |
237 | } |
238 | } |
239 | |
240 | fn occupied_bit(slot: usize) -> u64 { |
241 | 1 << slot |
242 | } |
243 | |
244 | fn slot_range(level: usize) -> u64 { |
245 | LEVEL_MULT.pow(level as u32) as u64 |
246 | } |
247 | |
248 | fn 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. |
253 | fn 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)))] |
258 | mod 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 | |