vendor/tokio-util/src/time/wheel/level.rs

   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> {
  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.
 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 deadline = level_start + slot as u64 * slot_range;
 144
 145         debug_assert!(
 146             deadline >= now,
 147             "deadline={}; now={}; level={}; slot={}; occupied={:b}",
 148             deadline,
 149             now,
 150             self.level,
 151             slot,
 152             self.occupied
 153         );
 154
 155         Some(Expiration {
 156             level: self.level,
 157             slot,
 158             deadline,
 159         })
 160     }
 161
 162     fn next_occupied_slot(&self, now: u64) -> Option<usize> {
 163         if self.occupied == 0 {
 164             return None;
 165         }
 166
 167         // Get the slot for now using Maths
 168         let now_slot = (now / slot_range(self.level)) as usize;
 169         let occupied = self.occupied.rotate_right(now_slot as u32);
 170         let zeros = occupied.trailing_zeros() as usize;
 171         let slot = (zeros + now_slot) % 64;
 172
 173         Some(slot)
 174     }
 175
 176     pub(crate) fn add_entry(&mut self, when: u64, item: T::Owned, store: &mut T::Store) {
 177         let slot = slot_for(when, self.level);
 178
 179         self.slot[slot].push(item, store);
 180         self.occupied |= occupied_bit(slot);
 181     }
 182
 183     pub(crate) fn remove_entry(&mut self, when: u64, item: &T::Borrowed, store: &mut T::Store) {
 184         let slot = slot_for(when, self.level);
 185
 186         self.slot[slot].remove(item, store);
 187
 188         if self.slot[slot].is_empty() {
 189             // The bit is currently set
 190             debug_assert!(self.occupied & occupied_bit(slot) != 0);
 191
 192             // Unset the bit
 193             self.occupied ^= occupied_bit(slot);
 194         }
 195     }
 196
 197     pub(crate) fn pop_entry_slot(&mut self, slot: usize, store: &mut T::Store) -> Option<T::Owned> {
 198         let ret = self.slot[slot].pop(store);
 199
 200         if ret.is_some() && self.slot[slot].is_empty() {
 201             // The bit is currently set
 202             debug_assert!(self.occupied & occupied_bit(slot) != 0);
 203
 204             self.occupied ^= occupied_bit(slot);
 205         }
 206
 207         ret
 208     }
 209 }
 210
 211 impl<T> fmt::Debug for Level<T> {
 212     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 213         fmt.debug_struct("Level")
 214             .field("occupied", &self.occupied)
 215             .finish()
 216     }
 217 }
 218
 219 fn occupied_bit(slot: usize) -> u64 {
 220     1 << slot
 221 }
 222
 223 fn slot_range(level: usize) -> u64 {
 224     LEVEL_MULT.pow(level as u32) as u64
 225 }
 226
 227 fn level_range(level: usize) -> u64 {
 228     LEVEL_MULT as u64 * slot_range(level)
 229 }
 230
 231 /// Convert a duration (milliseconds) and a level to a slot position
 232 fn slot_for(duration: u64, level: usize) -> usize {
 233     ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
 234 }
 235
 236 #[cfg(all(test, not(loom)))]
 237 mod test {
 238     use super::*;
 239
 240     #[test]
 241     fn test_slot_for() {
 242         for pos in 0..64 {
 243             assert_eq!(pos as usize, slot_for(pos, 0));
 244         }
 245
 246         for level in 1..5 {
 247             for pos in level..64 {
 248                 let a = pos * 64_usize.pow(level as u32);
 249                 assert_eq!(pos as usize, slot_for(a as u64, level));
 250             }
 251         }
 252     }
 253 }