noq_proto/connection/
timer.rs

1use identity_hash::{IdentityHashable, IntMap};
2
3use crate::{
4    Instant,
5    connection::qlog::{QlogSink, QlogSinkWithTime},
6};
7
8use super::PathId;
9
10#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
11pub(crate) enum Timer {
12    /// Per connection timers.
13    Conn(ConnTimer),
14    /// Per path timers.
15    PerPath(PathId, PathTimer),
16}
17
18#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
19pub(crate) enum ConnTimer {
20    /// When to close the connection after no activity
21    Idle = 0,
22    /// When the close timer expires, the connection has been gracefully terminated.
23    Close = 1,
24    /// When keys are discarded because they should not be needed anymore
25    KeyDiscard = 2,
26    /// When to send a `PING` frame to keep the connection alive
27    KeepAlive = 3,
28    /// When to invalidate old CID and proactively push new one via NEW_CONNECTION_ID frame
29    PushNewCid = 4,
30    /// Grace period after the remote abandoned the last path.
31    ///
32    /// If no new path is opened before this fires, close the connection.
33    /// See <https://www.ietf.org/archive/id/draft-ietf-quic-multipath-21.html#section-3.4-8>
34    NoAvailablePath = 5,
35    /// When to retry NAT traversal probes.
36    ///
37    /// Fires at initial PTO intervals to retransmit probes that got no PATH_RESPONSE.
38    NatTraversalProbeRetry = 6,
39}
40
41impl ConnTimer {
42    const VALUES: [Self; 7] = [
43        Self::Idle,
44        Self::Close,
45        Self::KeyDiscard,
46        Self::KeepAlive,
47        Self::PushNewCid,
48        Self::NoAvailablePath,
49        Self::NatTraversalProbeRetry,
50    ];
51}
52
53#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
54pub(crate) enum PathTimer {
55    /// When to send an ack-eliciting probe packet or declare unacked packets lost
56    LossDetection = 0,
57    /// When to abandon a path after no activity
58    PathIdle = 1,
59    /// When to give up on validating a new path from RFC9000 migration
60    PathValidationFailed = 2,
61    /// When to resend an on-path path challenge deemed lost
62    PathChallengeLost = 3,
63    /// When to send a `PING` frame to keep the path alive
64    PathKeepAlive = 4,
65    /// When pacing will allow us to send a packet
66    Pacing = 5,
67    /// When to send an immediate ACK if there are unacked ack-eliciting packets of the peer
68    MaxAckDelay = 6,
69    /// When to clean up state for an abandoned path
70    PathDrained = 7,
71}
72
73impl PathTimer {
74    pub(super) const VALUES: [Self; 8] = [
75        Self::LossDetection,
76        Self::PathIdle,
77        Self::PathValidationFailed,
78        Self::PathChallengeLost,
79        Self::PathKeepAlive,
80        Self::Pacing,
81        Self::MaxAckDelay,
82        Self::PathDrained,
83    ];
84}
85
86/// Newtype around [`PathId`] that implements [`IdentityHashable`].
87#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Default)]
88struct PathIdKey(PathId);
89
90impl IdentityHashable for PathIdKey {}
91
92impl std::hash::Hash for PathIdKey {
93    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
94        state.write_u32(self.0.0);
95    }
96}
97
98/// Keeps track of the nearest timeout for each `Timer`
99///
100/// The [`TimerTable`] is advanced with [`TimerTable::expire_before`].
101#[derive(Debug, Clone, Default)]
102pub(crate) struct TimerTable {
103    generic: [Option<Instant>; ConnTimer::VALUES.len()],
104    path_timers: SmallMap<PathIdKey, PathTimerTable, STACK_TIMERS>,
105}
106
107/// For how many paths we keep the timers on the stack, before spilling onto the heap.
108const STACK_TIMERS: usize = 4;
109
110/// Works like a `HashMap` but stores up to `SIZE` items on the stack.
111#[derive(Debug, Clone)]
112struct SmallMap<K, V, const SIZE: usize> {
113    stack: [Option<(K, V)>; SIZE],
114    heap: Option<IntMap<K, V>>,
115}
116
117impl<K, V, const SIZE: usize> Default for SmallMap<K, V, SIZE> {
118    fn default() -> Self {
119        Self {
120            stack: [const { None }; SIZE],
121            heap: None,
122        }
123    }
124}
125
126impl<K, V, const SIZE: usize> SmallMap<K, V, SIZE>
127where
128    K: Eq + std::hash::Hash + IdentityHashable,
129{
130    fn insert(&mut self, key: K, value: V) -> Option<V> {
131        // check stack for space
132        for el in self.stack.iter_mut() {
133            match el {
134                Some((k, v)) => {
135                    if *k == key {
136                        let old_value = std::mem::replace(v, value);
137                        return Some(old_value);
138                    }
139                }
140                None => {
141                    // make sure to remove a potentially old value from the heap
142                    let old_heap = self.heap.as_mut().and_then(|h| h.remove(&key));
143                    *el = Some((key, value));
144
145                    return old_heap;
146                }
147            }
148        }
149
150        // No space on the stack, use the heap
151        let heap = self.heap.get_or_insert_default();
152        heap.insert(key, value)
153    }
154
155    #[cfg(test)]
156    fn remove(&mut self, key: &K) -> Option<V> {
157        for el in self.stack.iter_mut() {
158            if let Some((k, _)) = el
159                && key == k
160            {
161                return el.take().map(|(_, v)| v);
162            }
163        }
164
165        self.heap.as_mut().and_then(|h| h.remove(key))
166    }
167
168    fn get(&self, key: &K) -> Option<&V> {
169        for (k, v) in self.stack.iter().filter_map(|v| v.as_ref()) {
170            if k == key {
171                return Some(v);
172            }
173        }
174
175        self.heap.as_ref().and_then(|h| h.get(key))
176    }
177
178    fn get_mut(&mut self, key: &K) -> Option<&mut V> {
179        for (k, v) in self.stack.iter_mut().filter_map(|v| v.as_mut()) {
180            if k == key {
181                return Some(v);
182            }
183        }
184
185        self.heap.as_mut().and_then(|h| h.get_mut(key))
186    }
187
188    #[cfg(test)]
189    fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
190        let a = self
191            .stack
192            .iter()
193            .filter_map(|v| v.as_ref().map(|(k, v)| (k, v)));
194        let b = self.heap.iter().flat_map(|h| h.iter());
195        a.chain(b)
196    }
197
198    fn values(&self) -> impl Iterator<Item = &V> {
199        let a = self.stack.iter().filter_map(|v| v.as_ref().map(|(_, v)| v));
200        let b = self.heap.iter().flat_map(|h| h.values());
201        a.chain(b)
202    }
203
204    fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
205        let a = self
206            .stack
207            .iter_mut()
208            .filter_map(|v| v.as_mut().map(|(k, v)| (&*k, v)));
209        let b = self.heap.iter_mut().flat_map(|h| h.iter_mut());
210        a.chain(b)
211    }
212
213    fn retain<F>(&mut self, mut f: F)
214    where
215        F: FnMut(&K, &mut V) -> bool,
216    {
217        let mut to_remove = [false; SIZE];
218        for (i, el) in self.stack.iter_mut().enumerate() {
219            if let Some((key, value)) = el {
220                to_remove[i] = !f(key, value);
221            }
222        }
223        for (i, to_remove) in to_remove.into_iter().enumerate() {
224            if to_remove {
225                self.stack[i] = None;
226            }
227        }
228
229        if let Some(ref mut heap) = self.heap {
230            heap.retain(f);
231        }
232    }
233
234    fn clear(&mut self) {
235        for el in self.stack.iter_mut() {
236            *el = None;
237        }
238        self.heap = None;
239    }
240}
241
242#[derive(Debug, Clone, Copy, Default)]
243struct PathTimerTable {
244    timers: [Option<Instant>; PathTimer::VALUES.len()],
245}
246
247impl PathTimerTable {
248    fn set(&mut self, timer: PathTimer, time: Instant) {
249        self.timers[timer as usize] = Some(time);
250    }
251
252    fn get(&self, timer: PathTimer) -> Option<Instant> {
253        self.timers[timer as usize]
254    }
255
256    fn stop(&mut self, timer: PathTimer) {
257        self.timers[timer as usize] = None;
258    }
259
260    /// Remove the next timer up until `now`, including it
261    fn expire_before(&mut self, now: Instant) -> Option<(PathTimer, Instant)> {
262        for timer in PathTimer::VALUES {
263            if self.timers[timer as usize].is_some()
264                && self.timers[timer as usize].expect("checked") <= now
265            {
266                return self.timers[timer as usize].take().map(|time| (timer, time));
267            }
268        }
269
270        None
271    }
272}
273
274impl TimerTable {
275    /// Sets the timer unconditionally.
276    ///
277    /// If the timer is already set, this will change the timer's value.
278    pub(super) fn set(&mut self, timer: Timer, time: Instant, qlog: QlogSinkWithTime<'_>) {
279        match timer {
280            Timer::Conn(timer) => {
281                self.generic[timer as usize] = Some(time);
282            }
283            Timer::PerPath(path_id, timer) => match self.path_timers.get_mut(&PathIdKey(path_id)) {
284                None => {
285                    let mut table = PathTimerTable::default();
286                    table.set(timer, time);
287                    self.path_timers.insert(PathIdKey(path_id), table);
288                }
289                Some(table) => {
290                    table.set(timer, time);
291                }
292            },
293        }
294        qlog.emit_timer_set(timer, time);
295    }
296
297    #[allow(unused)]
298    pub(super) fn get(&self, timer: Timer) -> Option<Instant> {
299        match timer {
300            Timer::Conn(timer) => self.generic[timer as usize],
301            Timer::PerPath(path_id, timer) => self.path_timers.get(&PathIdKey(path_id))?.get(timer),
302        }
303    }
304
305    pub(super) fn set_or_stop(
306        &mut self,
307        timer: Timer,
308        time: Option<Instant>,
309        qlog: QlogSinkWithTime<'_>,
310    ) {
311        match time {
312            Some(time) => self.set(timer, time, qlog),
313            None => self.stop(timer, qlog),
314        }
315    }
316
317    pub(super) fn stop(&mut self, timer: Timer, qlog: QlogSinkWithTime<'_>) {
318        match timer {
319            Timer::Conn(timer) => {
320                self.generic[timer as usize] = None;
321            }
322            Timer::PerPath(path_id, timer) => {
323                if let Some(e) = self.path_timers.get_mut(&PathIdKey(path_id)) {
324                    e.stop(timer);
325                }
326            }
327        }
328        qlog.emit_timer_stop(timer);
329    }
330
331    /// Stops all per-path timers
332    pub(super) fn stop_per_path(&mut self, path_id: PathId, qlog: QlogSinkWithTime<'_>) {
333        for timer in PathTimer::VALUES {
334            if let Some(e) = self.path_timers.get_mut(&PathIdKey(path_id)) {
335                e.stop(timer);
336                qlog.emit_timer_stop(Timer::PerPath(path_id, timer));
337            }
338        }
339    }
340
341    /// Get the next queued timeout
342    pub(super) fn peek(&self) -> Option<Instant> {
343        // TODO: this is currently linear in the number of paths
344
345        let min_generic = self.generic.iter().filter_map(|&x| x).min();
346        let min_path = self
347            .path_timers
348            .values()
349            .flat_map(|p| p.timers.iter().filter_map(|&x| x))
350            .min();
351
352        match (min_generic, min_path) {
353            (None, None) => None,
354            (Some(val), None) => Some(val),
355            (Some(a), Some(b)) => Some(a.min(b)),
356            (None, Some(val)) => Some(val),
357        }
358    }
359
360    /// Remove the next timer up until `now`, including it
361    pub(super) fn expire_before(
362        &mut self,
363        now: Instant,
364        qlog: &QlogSink,
365    ) -> Option<(Timer, Instant)> {
366        let (timer, instant) = self.expire_before_inner(now)?;
367        qlog.with_time(now).emit_timer_expire(timer);
368        Some((timer, instant))
369    }
370
371    fn expire_before_inner(&mut self, now: Instant) -> Option<(Timer, Instant)> {
372        // TODO: this is currently linear in the number of paths
373
374        for timer in ConnTimer::VALUES {
375            if self.generic[timer as usize].is_some()
376                && self.generic[timer as usize].expect("checked") <= now
377            {
378                return self.generic[timer as usize]
379                    .take()
380                    .map(|time| (Timer::Conn(timer), time));
381            }
382        }
383
384        let mut res = None;
385        for (PathIdKey(path_id), timers) in self.path_timers.iter_mut() {
386            if let Some((timer, time)) = timers.expire_before(now) {
387                res = Some((Timer::PerPath(*path_id, timer), time));
388                break;
389            }
390        }
391
392        // clear out old timers
393        self.path_timers
394            .retain(|_path_id, timers| timers.timers.iter().any(|t| t.is_some()));
395        res
396    }
397
398    pub(super) fn reset(&mut self) {
399        for timer in ConnTimer::VALUES {
400            self.generic[timer as usize] = None;
401        }
402        self.path_timers.clear();
403    }
404
405    #[cfg(test)]
406    pub(super) fn values(&self) -> Vec<(Timer, Instant)> {
407        let mut values = Vec::new();
408
409        for timer in ConnTimer::VALUES {
410            if let Some(time) = self.generic[timer as usize] {
411                values.push((Timer::Conn(timer), time));
412            }
413        }
414
415        for timer in PathTimer::VALUES {
416            for (PathIdKey(path_id), timers) in self.path_timers.iter() {
417                if let Some(time) = timers.timers[timer as usize] {
418                    values.push((Timer::PerPath(*path_id, timer), time));
419                }
420            }
421        }
422
423        values
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use std::time::Duration;
430
431    use crate::connection::qlog::QlogSink;
432
433    use super::*;
434
435    #[test]
436    fn timer_table() {
437        let mut timers = TimerTable::default();
438        let sec = Duration::from_secs(1);
439        let now = Instant::now() + Duration::from_secs(10);
440        timers.set(
441            Timer::Conn(ConnTimer::Idle),
442            now - 3 * sec,
443            QlogSink::default().with_time(now),
444        );
445        timers.set(
446            Timer::Conn(ConnTimer::Close),
447            now - 2 * sec,
448            QlogSink::default().with_time(now),
449        );
450
451        assert_eq!(timers.peek(), Some(now - 3 * sec));
452        assert_eq!(
453            timers.expire_before(now, &QlogSink::default()),
454            Some((Timer::Conn(ConnTimer::Idle), now - 3 * sec))
455        );
456        assert_eq!(
457            timers.expire_before(now, &QlogSink::default()),
458            Some((Timer::Conn(ConnTimer::Close), now - 2 * sec))
459        );
460        assert_eq!(timers.expire_before(now, &QlogSink::default()), None);
461    }
462
463    #[test]
464    fn test_small_map() {
465        let mut map = SmallMap::<usize, usize, 2>::default();
466
467        // inserts only on the stack
468        assert_eq!(map.insert(1, 1), None);
469        assert!(map.heap.is_none());
470        assert_eq!(map.insert(2, 2), None);
471        assert!(map.heap.is_none());
472
473        // replace on the stack
474        assert_eq!(map.insert(1, 2), Some(1));
475
476        assert_eq!(map.remove(&1), Some(2));
477        assert_eq!(map.insert(3, 3), None);
478        assert!(map.heap.is_none());
479
480        // spill
481        assert_eq!(map.insert(4, 4), None);
482        assert!(map.heap.is_some());
483
484        assert_eq!(
485            map.iter()
486                .map(|(&a, &b)| (a, b))
487                .collect::<Vec<(usize, usize)>>(),
488            vec![(3, 3), (2, 2), (4, 4)]
489        );
490        assert_eq!(
491            map.iter()
492                .map(|(a, b)| (*a, *b))
493                .collect::<Vec<(usize, usize)>>(),
494            map.iter_mut()
495                .map(|(a, b)| (*a, *b))
496                .collect::<Vec<(usize, usize)>>(),
497        );
498
499        assert_eq!(map.heap.as_ref().unwrap().len(), 1);
500
501        for i in 0..10 {
502            map.insert(10 + i, 10 + i);
503        }
504        assert_eq!(map.heap.as_ref().unwrap().len(), 11);
505        map.retain(|k, _v| *k < 10);
506
507        assert_eq!(map.heap.as_ref().unwrap().len(), 1);
508
509        assert_eq!(
510            map.iter()
511                .map(|(&a, &b)| (a, b))
512                .collect::<Vec<(usize, usize)>>(),
513            vec![(3, 3), (2, 2), (4, 4)]
514        );
515
516        assert_eq!(
517            map.iter()
518                .map(|(a, b)| (*a, *b))
519                .collect::<Vec<(usize, usize)>>(),
520            map.iter_mut()
521                .map(|(a, b)| (*a, *b))
522                .collect::<Vec<(usize, usize)>>(),
523        );
524
525        map.clear();
526        assert_eq!(map.iter().collect::<Vec<_>>(), Vec::new());
527        assert!(map.heap.is_none());
528    }
529}
noq_proto/connection/timer.rs

noq_proto/connection/
timer.rs
