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    pub(super) fn get(&self, timer: Timer) -> Option<Instant> {
298        match timer {
299            Timer::Conn(timer) => self.generic[timer as usize],
300            Timer::PerPath(path_id, timer) => self.path_timers.get(&PathIdKey(path_id))?.get(timer),
301        }
302    }
303
304    pub(super) fn set_or_stop(
305        &mut self,
306        timer: Timer,
307        time: Option<Instant>,
308        qlog: QlogSinkWithTime<'_>,
309    ) {
310        match time {
311            Some(time) => self.set(timer, time, qlog),
312            None => self.stop(timer, qlog),
313        }
314    }
315
316    pub(super) fn stop(&mut self, timer: Timer, qlog: QlogSinkWithTime<'_>) {
317        match timer {
318            Timer::Conn(timer) => {
319                self.generic[timer as usize] = None;
320            }
321            Timer::PerPath(path_id, timer) => {
322                if let Some(e) = self.path_timers.get_mut(&PathIdKey(path_id)) {
323                    e.stop(timer);
324                }
325            }
326        }
327        qlog.emit_timer_stop(timer);
328    }
329
330    /// Stops all per-path timers
331    pub(super) fn stop_per_path(&mut self, path_id: PathId, qlog: QlogSinkWithTime<'_>) {
332        for timer in PathTimer::VALUES {
333            if let Some(e) = self.path_timers.get_mut(&PathIdKey(path_id)) {
334                e.stop(timer);
335                qlog.emit_timer_stop(Timer::PerPath(path_id, timer));
336            }
337        }
338    }
339
340    /// Get the next queued timeout
341    pub(super) fn peek(&self) -> Option<Instant> {
342        // TODO: this is currently linear in the number of paths
343
344        let min_generic = self.generic.iter().filter_map(|&x| x).min();
345        let min_path = self
346            .path_timers
347            .values()
348            .flat_map(|p| p.timers.iter().filter_map(|&x| x))
349            .min();
350
351        match (min_generic, min_path) {
352            (None, None) => None,
353            (Some(val), None) => Some(val),
354            (Some(a), Some(b)) => Some(a.min(b)),
355            (None, Some(val)) => Some(val),
356        }
357    }
358
359    /// Remove the next timer up until `now`, including it
360    pub(super) fn expire_before(
361        &mut self,
362        now: Instant,
363        qlog: &QlogSink,
364    ) -> Option<(Timer, Instant)> {
365        let (timer, instant) = self.expire_before_inner(now)?;
366        qlog.with_time(now).emit_timer_expire(timer);
367        Some((timer, instant))
368    }
369
370    fn expire_before_inner(&mut self, now: Instant) -> Option<(Timer, Instant)> {
371        // TODO: this is currently linear in the number of paths
372
373        for timer in ConnTimer::VALUES {
374            if self.generic[timer as usize].is_some()
375                && self.generic[timer as usize].expect("checked") <= now
376            {
377                return self.generic[timer as usize]
378                    .take()
379                    .map(|time| (Timer::Conn(timer), time));
380            }
381        }
382
383        let mut res = None;
384        for (PathIdKey(path_id), timers) in self.path_timers.iter_mut() {
385            if let Some((timer, time)) = timers.expire_before(now) {
386                res = Some((Timer::PerPath(*path_id, timer), time));
387                break;
388            }
389        }
390
391        // clear out old timers
392        self.path_timers
393            .retain(|_path_id, timers| timers.timers.iter().any(|t| t.is_some()));
394        res
395    }
396
397    pub(super) fn reset(&mut self) {
398        for timer in ConnTimer::VALUES {
399            self.generic[timer as usize] = None;
400        }
401        self.path_timers.clear();
402    }
403
404    #[cfg(test)]
405    pub(super) fn values(&self) -> Vec<(Timer, Instant)> {
406        let mut values = Vec::new();
407
408        for timer in ConnTimer::VALUES {
409            if let Some(time) = self.generic[timer as usize] {
410                values.push((Timer::Conn(timer), time));
411            }
412        }
413
414        for timer in PathTimer::VALUES {
415            for (PathIdKey(path_id), timers) in self.path_timers.iter() {
416                if let Some(time) = timers.timers[timer as usize] {
417                    values.push((Timer::PerPath(*path_id, timer), time));
418                }
419            }
420        }
421
422        values
423    }
424}
425
426#[cfg(test)]
427mod tests {
428    use std::time::Duration;
429
430    use crate::connection::qlog::QlogSink;
431
432    use super::*;
433
434    #[test]
435    fn timer_table() {
436        let mut timers = TimerTable::default();
437        let sec = Duration::from_secs(1);
438        let now = Instant::now() + Duration::from_secs(10);
439        timers.set(
440            Timer::Conn(ConnTimer::Idle),
441            now - 3 * sec,
442            QlogSink::default().with_time(now),
443        );
444        timers.set(
445            Timer::Conn(ConnTimer::Close),
446            now - 2 * sec,
447            QlogSink::default().with_time(now),
448        );
449
450        assert_eq!(timers.peek(), Some(now - 3 * sec));
451        assert_eq!(
452            timers.expire_before(now, &QlogSink::default()),
453            Some((Timer::Conn(ConnTimer::Idle), now - 3 * sec))
454        );
455        assert_eq!(
456            timers.expire_before(now, &QlogSink::default()),
457            Some((Timer::Conn(ConnTimer::Close), now - 2 * sec))
458        );
459        assert_eq!(timers.expire_before(now, &QlogSink::default()), None);
460    }
461
462    #[test]
463    fn test_small_map() {
464        let mut map = SmallMap::<usize, usize, 2>::default();
465
466        // inserts only on the stack
467        assert_eq!(map.insert(1, 1), None);
468        assert!(map.heap.is_none());
469        assert_eq!(map.insert(2, 2), None);
470        assert!(map.heap.is_none());
471
472        // replace on the stack
473        assert_eq!(map.insert(1, 2), Some(1));
474
475        assert_eq!(map.remove(&1), Some(2));
476        assert_eq!(map.insert(3, 3), None);
477        assert!(map.heap.is_none());
478
479        // spill
480        assert_eq!(map.insert(4, 4), None);
481        assert!(map.heap.is_some());
482
483        assert_eq!(
484            map.iter()
485                .map(|(&a, &b)| (a, b))
486                .collect::<Vec<(usize, usize)>>(),
487            vec![(3, 3), (2, 2), (4, 4)]
488        );
489        assert_eq!(
490            map.iter()
491                .map(|(a, b)| (*a, *b))
492                .collect::<Vec<(usize, usize)>>(),
493            map.iter_mut()
494                .map(|(a, b)| (*a, *b))
495                .collect::<Vec<(usize, usize)>>(),
496        );
497
498        assert_eq!(map.heap.as_ref().unwrap().len(), 1);
499
500        for i in 0..10 {
501            map.insert(10 + i, 10 + i);
502        }
503        assert_eq!(map.heap.as_ref().unwrap().len(), 11);
504        map.retain(|k, _v| *k < 10);
505
506        assert_eq!(map.heap.as_ref().unwrap().len(), 1);
507
508        assert_eq!(
509            map.iter()
510                .map(|(&a, &b)| (a, b))
511                .collect::<Vec<(usize, usize)>>(),
512            vec![(3, 3), (2, 2), (4, 4)]
513        );
514
515        assert_eq!(
516            map.iter()
517                .map(|(a, b)| (*a, *b))
518                .collect::<Vec<(usize, usize)>>(),
519            map.iter_mut()
520                .map(|(a, b)| (*a, *b))
521                .collect::<Vec<(usize, usize)>>(),
522        );
523
524        map.clear();
525        assert_eq!(map.iter().collect::<Vec<_>>(), Vec::new());
526        assert!(map.heap.is_none());
527    }
528}
noq_proto/connection/timer.rs

noq_proto/connection/
timer.rs
