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