noq_proto/connection/cid_state.rs
1//! Maintain the state of local connection IDs
2use std::collections::VecDeque;
3
4use rustc_hash::FxHashSet;
5use tracing::{debug, trace};
6
7use crate::{Duration, Instant, TransportError, shared::IssuedCid};
8
9/// Local connection ID management
10#[derive(Debug)]
11pub(super) struct CidState {
12 /// Timestamp when issued cids should be retired
13 ///
14 /// Each entry indicates the expiration of all timestamps up to the sequence number in
15 /// the entry. This means one entry can expire multiple CIDs if the sequence number
16 /// jumps by more than 1 between entries.
17 retire_timestamp: VecDeque<CidTimestamp>,
18 /// Number of local connection IDs that have been issued in NEW_CONNECTION_ID frames.
19 ///
20 /// This is thus also the sequence number of the next CID to be issued.
21 issued: u64,
22 /// Sequence numbers of local connection IDs not yet retired by the peer
23 active_seq: FxHashSet<u64>,
24 /// Sequence number the peer has already retired all CIDs below at our request via `retire_prior_to`
25 prev_retire_seq: u64,
26 /// Sequence number to set in retire_prior_to field in NEW_CONNECTION_ID frame
27 retire_seq: u64,
28 /// cid length used to decode short packet
29 cid_len: usize,
30 /// cid lifetime
31 cid_lifetime: Option<Duration>,
32}
33
34impl CidState {
35 pub(crate) fn new(
36 cid_len: usize,
37 cid_lifetime: Option<Duration>,
38 now: Instant,
39 issued: u64,
40 ) -> Self {
41 let mut active_seq = FxHashSet::default();
42 // Add sequence number of CIDs used in handshaking into tracking set
43 for seq in 0..issued {
44 active_seq.insert(seq);
45 }
46 let mut this = Self {
47 retire_timestamp: VecDeque::new(),
48 issued,
49 active_seq,
50 prev_retire_seq: 0,
51 retire_seq: 0,
52 cid_len,
53 cid_lifetime,
54 };
55 // Track lifetime of CIDs used in handshaking
56 for seq in 0..issued {
57 this.track_lifetime(seq, now);
58 }
59 this
60 }
61
62 /// Find the earliest time when previously issued CID should be retired
63 pub(crate) fn next_timeout(&self) -> Option<Instant> {
64 self.retire_timestamp.front().map(|nc| {
65 trace!("CID {} will expire at {:?}", nc.sequence, nc.timestamp);
66 nc.timestamp
67 })
68 }
69
70 /// Track the lifetime of issued cids in `retire_timestamp`
71 fn track_lifetime(&mut self, new_cid_seq: u64, now: Instant) {
72 let Some(lifetime) = self.cid_lifetime else {
73 return;
74 };
75 let Some(expire_at) = now.checked_add(lifetime) else {
76 return;
77 };
78
79 let last_record = self.retire_timestamp.back_mut();
80 if let Some(last) = last_record {
81 // Compare the timestamp with the last inserted record
82 // Combine into a single batch if timestamp of current cid is same as the last record
83 if expire_at == last.timestamp {
84 debug_assert!(new_cid_seq > last.sequence);
85 last.sequence = new_cid_seq;
86 return;
87 }
88 }
89
90 self.retire_timestamp.push_back(CidTimestamp {
91 sequence: new_cid_seq,
92 timestamp: expire_at,
93 });
94 }
95
96 /// Update local CID state when previously issued CID is retired
97 ///
98 /// Return whether a new CID needs to be pushed that notifies remote peer to respond `RETIRE_CONNECTION_ID`
99 pub(crate) fn on_cid_timeout(&mut self) -> bool {
100 // Whether the peer hasn't retired all the CIDs we asked it to yet
101 let unretired_ids_found =
102 (self.prev_retire_seq..self.retire_seq).any(|seq| self.active_seq.contains(&seq));
103
104 let current_retire_prior_to = self.retire_seq;
105 let next_retire_sequence = self
106 .retire_timestamp
107 .pop_front()
108 .map(|seq| seq.sequence + 1);
109
110 // According to RFC:
111 // Endpoints SHOULD NOT issue updates of the Retire Prior To field
112 // before receiving RETIRE_CONNECTION_ID frames that retire all
113 // connection IDs indicated by the previous Retire Prior To value.
114 // https://tools.ietf.org/html/draft-ietf-quic-transport-29#section-5.1.2
115 if !unretired_ids_found {
116 // All Cids are retired, `prev_retire_cid_seq` can be assigned to `retire_cid_seq`
117 self.prev_retire_seq = self.retire_seq;
118 // Advance `retire_seq` if next cid that needs to be retired exists
119 if let Some(next_retire_prior_to) = next_retire_sequence {
120 self.retire_seq = next_retire_prior_to;
121 }
122 }
123
124 // Check if retirement of all CIDs that reach their lifetime is still needed
125 // According to RFC:
126 // An endpoint MUST NOT
127 // provide more connection IDs than the peer's limit. An endpoint MAY
128 // send connection IDs that temporarily exceed a peer's limit if the
129 // NEW_CONNECTION_ID frame also requires the retirement of any excess,
130 // by including a sufficiently large value in the Retire Prior To field.
131 //
132 // If yes (return true), a new CID must be pushed with updated `retire_prior_to` field to remote peer.
133 // If no (return false), it means CIDs that reach the end of lifetime have been retired already. Do not push a new CID in order to avoid violating above RFC.
134 (current_retire_prior_to..self.retire_seq).any(|seq| self.active_seq.contains(&seq))
135 }
136
137 /// Update cid state when `NewIdentifiers` event is received
138 ///
139 /// These are newly generated CIDs which we'll send to the peer in
140 /// (PATH_)NEW_CONNECTION_ID frames in the next packet that is sent. This records them
141 /// and tracks their lifetime.
142 pub(crate) fn new_cids(&mut self, ids: &[IssuedCid], now: Instant) {
143 // `ids` could be `None` once active_connection_id_limit is set to 1 by peer
144 let Some(last_cid) = ids.last() else {
145 return;
146 };
147 self.issued += ids.len() as u64;
148 // Record the timestamp of CID with the largest seq number
149 let sequence = last_cid.sequence;
150 ids.iter().for_each(|frame| {
151 self.active_seq.insert(frame.sequence);
152 });
153 self.track_lifetime(sequence, now);
154 }
155
156 /// Update CidState for receipt of a `RETIRE_CONNECTION_ID` frame
157 ///
158 /// Returns whether a new CID can be issued, or an error if the frame was illegal.
159 pub(crate) fn on_cid_retirement(
160 &mut self,
161 sequence: u64,
162 limit: u64,
163 ) -> Result<bool, TransportError> {
164 if self.cid_len == 0 {
165 return Err(TransportError::PROTOCOL_VIOLATION(
166 "RETIRE_CONNECTION_ID when CIDs aren't in use",
167 ));
168 }
169 if sequence > self.issued {
170 debug!(
171 sequence,
172 "got RETIRE_CONNECTION_ID for unissued sequence number"
173 );
174 return Err(TransportError::PROTOCOL_VIOLATION(
175 "RETIRE_CONNECTION_ID for unissued sequence number",
176 ));
177 }
178 self.active_seq.remove(&sequence);
179 // Consider a scenario where peer A has active remote cid 0,1,2.
180 // Peer B first send a NEW_CONNECTION_ID with cid 3 and retire_prior_to set to 1.
181 // Peer A processes this NEW_CONNECTION_ID frame; update remote cid to 1,2,3
182 // and meanwhile send a RETIRE_CONNECTION_ID to retire cid 0 to peer B.
183 // If peer B doesn't check the cid limit here and send a new cid again, peer A will then face CONNECTION_ID_LIMIT_ERROR
184 Ok(limit > self.active_seq.len() as u64)
185 }
186
187 /// Length of local Connection IDs
188 pub(crate) fn cid_len(&self) -> usize {
189 self.cid_len
190 }
191
192 /// The value for `retire_prior_to` field in `NEW_CONNECTION_ID` frame
193 pub(crate) fn retire_prior_to(&self) -> u64 {
194 self.retire_seq
195 }
196
197 pub(crate) fn active_seq(&self) -> (u64, u64) {
198 let mut min = u64::MAX;
199 let mut max = u64::MIN;
200 for n in self.active_seq.iter() {
201 if n < &min {
202 min = *n;
203 }
204 if n > &max {
205 max = *n;
206 }
207 }
208 (min, max)
209 }
210
211 #[cfg(test)]
212 pub(crate) fn assign_retire_seq(&mut self, v: u64) -> u64 {
213 // Cannot retire more CIDs than what have been issued
214 debug_assert!(v <= *self.active_seq.iter().max().unwrap() + 1);
215 let n = v.checked_sub(self.retire_seq).unwrap();
216 self.retire_seq = v;
217 n
218 }
219}
220
221/// Data structure that records when issued cids should be retired
222#[derive(Debug, Copy, Clone, Eq, PartialEq)]
223struct CidTimestamp {
224 /// Highest cid sequence number created in a batch
225 sequence: u64,
226 /// Timestamp when cid needs to be retired
227 timestamp: Instant,
228}