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