Debian Codegraph @

third_party/rust/neqo-transport/src/cid.rs

raw
1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4 // option. This file may not be copied, modified, or distributed
5 // except according to those terms.
6
7 // Representation and management of connection IDs.
8
9 use std::{
10 borrow::Borrow,
11 cell::{Ref, RefCell},
12 cmp::{max, min},
13 fmt::{self, Debug, Display, Formatter},
14 ops::Deref,
15 rc::Rc,
16 };
17
18 use neqo_common::{hex, hex_with_len, qdebug, qinfo, Decoder, Encoder};
19 use neqo_crypto::{random, randomize};
20 use smallvec::{smallvec, SmallVec};
21
22 use crate::{
23 frame::FrameType, packet::PacketBuilder, recovery::RecoveryToken, stats::FrameStats, Error, Res,
24 };
25
26 pub const MAX_CONNECTION_ID_LEN: usize = 20;
27 pub const LOCAL_ACTIVE_CID_LIMIT: usize = 8;
28 pub const CONNECTION_ID_SEQNO_INITIAL: u64 = 0;
29 pub const CONNECTION_ID_SEQNO_PREFERRED: u64 = 1;
30 /// A special value. See `ConnectionIdManager::add_odcid`.
31 const CONNECTION_ID_SEQNO_ODCID: u64 = u64::MAX;
32 /// A special value. See `ConnectionIdEntry::empty_remote`.
33 const CONNECTION_ID_SEQNO_EMPTY: u64 = u64::MAX - 1;
34
35 #[derive(Clone, Default, Eq, Hash, PartialEq)]
36 pub struct ConnectionId {
37 cid: SmallVec<[u8; MAX_CONNECTION_ID_LEN]>,
38 }
39
40 impl ConnectionId {
41 /// # Panics
42 /// When `len` is larger than `MAX_CONNECTION_ID_LEN`.
43 #[must_use]
44 pub fn generate(len: usize) -> Self {
45 assert!(matches!(len, 0..=MAX_CONNECTION_ID_LEN));
46 let mut cid = smallvec![0; len];
47 randomize(&mut cid);
48 Self { cid }
49 }
50
51 // Apply a wee bit of greasing here in picking a length between 8 and 20 bytes long.
52 #[must_use]
53 pub fn generate_initial() -> Self {
54 let v = random::<1>()[0];
55 // Bias selection toward picking 8 (>50% of the time).
56 let len: usize = max(8, 5 + (v & (v >> 4))).into();
57 Self::generate(len)
58 }
59
60 #[must_use]
61 pub fn as_cid_ref(&self) -> ConnectionIdRef {
62 ConnectionIdRef::from(&self.cid[..])
63 }
64 }
65
66 impl AsRef<[u8]> for ConnectionId {
67 fn as_ref(&self) -> &[u8] {
68 self.borrow()
69 }
70 }
71
72 impl Borrow<[u8]> for ConnectionId {
73 fn borrow(&self) -> &[u8] {
74 &self.cid
75 }
76 }
77
78 impl From<SmallVec<[u8; MAX_CONNECTION_ID_LEN]>> for ConnectionId {
79 fn from(cid: SmallVec<[u8; MAX_CONNECTION_ID_LEN]>) -> Self {
80 Self { cid }
81 }
82 }
83
84 impl<T: AsRef<[u8]> + ?Sized> From<&T> for ConnectionId {
85 fn from(buf: &T) -> Self {
86 Self::from(SmallVec::from_slice(buf.as_ref()))
87 }
88 }
89
90 impl<'a> From<ConnectionIdRef<'a>> for ConnectionId {
91 fn from(cidref: ConnectionIdRef<'a>) -> Self {
92 Self::from(SmallVec::from_slice(cidref.cid))
93 }
94 }
95
96 impl Deref for ConnectionId {
97 type Target = [u8];
98
99 fn deref(&self) -> &Self::Target {
100 &self.cid
101 }
102 }
103
104 impl Debug for ConnectionId {
105 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
106 write!(f, "CID {}", hex_with_len(&self.cid))
107 }
108 }
109
110 impl Display for ConnectionId {
111 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
112 write!(f, "{}", hex(&self.cid))
113 }
114 }
115
116 impl<'a> PartialEq<ConnectionIdRef<'a>> for ConnectionId {
117 fn eq(&self, other: &ConnectionIdRef<'a>) -> bool {
118 &self.cid[..] == other.cid
119 }
120 }
121
122 #[derive(Hash, Eq, PartialEq, Clone, Copy)]
123 pub struct ConnectionIdRef<'a> {
124 cid: &'a [u8],
125 }
126
127 impl Debug for ConnectionIdRef<'_> {
128 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
129 write!(f, "CID {}", hex_with_len(self.cid))
130 }
131 }
132
133 impl Display for ConnectionIdRef<'_> {
134 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
135 write!(f, "{}", hex(self.cid))
136 }
137 }
138
139 impl<'a, T: AsRef<[u8]> + ?Sized> From<&'a T> for ConnectionIdRef<'a> {
140 fn from(cid: &'a T) -> Self {
141 Self { cid: cid.as_ref() }
142 }
143 }
144
145 impl Deref for ConnectionIdRef<'_> {
146 type Target = [u8];
147
148 fn deref(&self) -> &Self::Target {
149 self.cid
150 }
151 }
152
153 impl PartialEq<ConnectionId> for ConnectionIdRef<'_> {
154 fn eq(&self, other: &ConnectionId) -> bool {
155 self.cid == &other.cid[..]
156 }
157 }
158
159 pub trait ConnectionIdDecoder {
160 /// Decodes a connection ID from the provided decoder.
161 fn decode_cid<'a>(&self, dec: &mut Decoder<'a>) -> Option<ConnectionIdRef<'a>>;
162 }
163
164 pub trait ConnectionIdGenerator: ConnectionIdDecoder {
165 /// Generates a connection ID. This can return `None` if the generator
166 /// is exhausted.
167 fn generate_cid(&mut self) -> Option<ConnectionId>;
168 /// Indicates whether the connection IDs are zero-length.
169 /// If this returns true, `generate_cid` must always produce an empty value
170 /// and never `None`.
171 /// If this returns false, `generate_cid` must never produce an empty value,
172 /// though it can return `None`.
173 ///
174 /// You should not need to implement this: if you want zero-length connection IDs,
175 /// use `EmptyConnectionIdGenerator` instead.
176 fn generates_empty_cids(&self) -> bool {
177 false
178 }
179 fn as_decoder(&self) -> &dyn ConnectionIdDecoder;
180 }
181
182 /// An `EmptyConnectionIdGenerator` generates empty connection IDs.
183 #[derive(Default)]
184 pub struct EmptyConnectionIdGenerator {}
185
186 impl ConnectionIdDecoder for EmptyConnectionIdGenerator {
187 fn decode_cid<'a>(&self, _: &mut Decoder<'a>) -> Option<ConnectionIdRef<'a>> {
188 Some(ConnectionIdRef::from(&[]))
189 }
190 }
191
192 impl ConnectionIdGenerator for EmptyConnectionIdGenerator {
193 fn generate_cid(&mut self) -> Option<ConnectionId> {
194 Some(ConnectionId::from(&[]))
195 }
196 fn as_decoder(&self) -> &dyn ConnectionIdDecoder {
197 self
198 }
199 fn generates_empty_cids(&self) -> bool {
200 true
201 }
202 }
203
204 /// An `RandomConnectionIdGenerator` produces connection IDs of
205 /// a fixed length and random content. No effort is made to
206 /// prevent collisions.
207 pub struct RandomConnectionIdGenerator {
208 len: usize,
209 }
210
211 impl RandomConnectionIdGenerator {
212 #[must_use]
213 pub const fn new(len: usize) -> Self {
214 Self { len }
215 }
216 }
217
218 impl ConnectionIdDecoder for RandomConnectionIdGenerator {
219 fn decode_cid<'a>(&self, dec: &mut Decoder<'a>) -> Option<ConnectionIdRef<'a>> {
220 dec.decode(self.len).map(ConnectionIdRef::from)
221 }
222 }
223
224 impl ConnectionIdGenerator for RandomConnectionIdGenerator {
225 fn generate_cid(&mut self) -> Option<ConnectionId> {
226 let mut buf = smallvec![0; self.len];
227 randomize(&mut buf);
228 Some(ConnectionId::from(buf))
229 }
230
231 fn as_decoder(&self) -> &dyn ConnectionIdDecoder {
232 self
233 }
234
235 fn generates_empty_cids(&self) -> bool {
236 self.len == 0
237 }
238 }
239
240 /// A single connection ID, as saved from `NEW_CONNECTION_ID`.
241 /// This is templated so that the connection ID entries from a peer can be
242 /// saved with a stateless reset token. Local entries don't need that.
243 #[derive(Debug, PartialEq, Eq, Clone)]
244 pub struct ConnectionIdEntry<SRT: Clone + PartialEq> {
245 /// The sequence number.
246 seqno: u64,
247 /// The connection ID.
248 cid: ConnectionId,
249 /// The corresponding stateless reset token.
250 srt: SRT,
251 }
252
253 impl ConnectionIdEntry<[u8; 16]> {
254 /// Create a random stateless reset token so that it is hard to guess the correct
255 /// value and reset the connection.
256 pub fn random_srt() -> [u8; 16] {
257 random::<16>()
258 }
259
260 /// Create the first entry, which won't have a stateless reset token.
261 pub fn initial_remote(cid: ConnectionId) -> Self {
262 Self::new(CONNECTION_ID_SEQNO_INITIAL, cid, Self::random_srt())
263 }
264
265 /// Create an empty for when the peer chooses empty connection IDs.
266 /// This uses a special sequence number just because it can.
267 pub fn empty_remote() -> Self {
268 Self::new(
269 CONNECTION_ID_SEQNO_EMPTY,
270 ConnectionId::from(&[]),
271 Self::random_srt(),
272 )
273 }
274
275 fn token_equal(a: &[u8; 16], b: &[u8; 16]) -> bool {
276 // rustc might decide to optimize this and make this non-constant-time
277 // with respect to `t`, but it doesn't appear to currently.
278 let mut c = 0;
279 for (&a, &b) in a.iter().zip(b) {
280 c |= a ^ b;
281 }
282 c == 0
283 }
284
285 /// Determine whether this is a valid stateless reset.
286 pub fn is_stateless_reset(&self, token: &[u8; 16]) -> bool {
287 // A sequence number of 2^62 or more has no corresponding stateless reset token.
288 (self.seqno < (1 << 62)) && Self::token_equal(&self.srt, token)
289 }
290
291 /// Return true if the two contain any equal parts.
292 fn any_part_equal(&self, other: &Self) -> bool {
293 self.seqno == other.seqno || self.cid == other.cid || self.srt == other.srt
294 }
295
296 /// The sequence number of this entry.
297 pub const fn sequence_number(&self) -> u64 {
298 self.seqno
299 }
300
301 /// Write the entry out in a `NEW_CONNECTION_ID` frame.
302 /// Returns `true` if the frame was written, `false` if there is insufficient space.
303 pub fn write(&self, builder: &mut PacketBuilder, stats: &mut FrameStats) -> bool {
304 let len = 1 + Encoder::varint_len(self.seqno) + 1 + 1 + self.cid.len() + 16;
305 if builder.remaining() < len {
306 return false;
307 }
308
309 builder.encode_varint(FrameType::NewConnectionId);
310 builder.encode_varint(self.seqno);
311 builder.encode_varint(0u64);
312 builder.encode_vec(1, &self.cid);
313 builder.encode(&self.srt);
314 stats.new_connection_id += 1;
315 true
316 }
317
318 pub fn is_empty(&self) -> bool {
319 self.seqno == CONNECTION_ID_SEQNO_EMPTY || self.cid.is_empty()
320 }
321 }
322
323 impl ConnectionIdEntry<()> {
324 /// Create an initial entry.
325 pub const fn initial_local(cid: ConnectionId) -> Self {
326 Self::new(0, cid, ())
327 }
328 }
329
330 impl<SRT: Clone + PartialEq> ConnectionIdEntry<SRT> {
331 pub const fn new(seqno: u64, cid: ConnectionId, srt: SRT) -> Self {
332 Self { seqno, cid, srt }
333 }
334
335 /// Update the stateless reset token. This panics if the sequence number is non-zero.
336 pub fn set_stateless_reset_token(&mut self, srt: SRT) {
337 assert_eq!(self.seqno, CONNECTION_ID_SEQNO_INITIAL);
338 self.srt = srt;
339 }
340
341 /// Replace the connection ID. This panics if the sequence number is non-zero.
342 pub fn update_cid(&mut self, cid: ConnectionId) {
343 assert_eq!(self.seqno, CONNECTION_ID_SEQNO_INITIAL);
344 self.cid = cid;
345 }
346
347 pub const fn connection_id(&self) -> &ConnectionId {
348 &self.cid
349 }
350
351 pub const fn reset_token(&self) -> &SRT {
352 &self.srt
353 }
354 }
355
356 pub type RemoteConnectionIdEntry = ConnectionIdEntry<[u8; 16]>;
357
358 /// A collection of connection IDs that are indexed by a sequence number.
359 /// Used to store connection IDs that are provided by a peer.
360 #[derive(Debug, Default)]
361 pub struct ConnectionIdStore<SRT: Clone + PartialEq> {
362 cids: SmallVec<[ConnectionIdEntry<SRT>; 8]>,
363 }
364
365 impl<SRT: Clone + PartialEq> ConnectionIdStore<SRT> {
366 pub fn retire(&mut self, seqno: u64) {
367 self.cids.retain(|c| c.seqno != seqno);
368 }
369
370 pub fn contains(&self, cid: ConnectionIdRef) -> bool {
371 self.cids.iter().any(|c| c.cid == cid)
372 }
373
374 pub fn next(&mut self) -> Option<ConnectionIdEntry<SRT>> {
375 if self.cids.is_empty() {
376 None
377 } else {
378 Some(self.cids.remove(0))
379 }
380 }
381
382 pub fn len(&self) -> usize {
383 self.cids.len()
384 }
385 }
386
387 impl ConnectionIdStore<[u8; 16]> {
388 pub fn add_remote(&mut self, entry: ConnectionIdEntry<[u8; 16]>) -> Res<()> {
389 // It's OK if this perfectly matches an existing entry.
390 if self.cids.iter().any(|c| c == &entry) {
391 return Ok(());
392 }
393 // It's not OK if any individual piece matches though.
394 if self.cids.iter().any(|c| c.any_part_equal(&entry)) {
395 qinfo!("ConnectionIdStore found reused part in NEW_CONNECTION_ID");
396 return Err(Error::ProtocolViolation);
397 }
398
399 // Insert in order so that we use them in order where possible.
400 if let Err(idx) = self.cids.binary_search_by_key(&entry.seqno, |e| e.seqno) {
401 self.cids.insert(idx, entry);
402 Ok(())
403 } else {
404 Err(Error::ProtocolViolation)
405 }
406 }
407
408 // Retire connection IDs and return the sequence numbers of those that were retired.
409 pub fn retire_prior_to(&mut self, retire_prior: u64) -> Vec<u64> {
410 let mut retired = Vec::new();
411 self.cids.retain(|e| {
412 if !e.is_empty() && e.seqno < retire_prior {
413 retired.push(e.seqno);
414 false
415 } else {
416 true
417 }
418 });
419 retired
420 }
421 }
422
423 impl ConnectionIdStore<()> {
424 fn add_local(&mut self, entry: ConnectionIdEntry<()>) {
425 self.cids.push(entry);
426 }
427 }
428
429 pub struct ConnectionIdDecoderRef<'a> {
430 generator: Ref<'a, dyn ConnectionIdGenerator>,
431 }
432
433 // Ideally this would be an implementation of `Deref`, but it doesn't
434 // seem to be possible to convince the compiler to build anything useful.
435 impl<'a: 'b, 'b> ConnectionIdDecoderRef<'a> {
436 pub fn as_ref(&'a self) -> &'b dyn ConnectionIdDecoder {
437 self.generator.as_decoder()
438 }
439 }
440
441 /// A connection ID manager looks after the generation of connection IDs,
442 /// the set of connection IDs that are valid for the connection, and the
443 /// generation of `NEW_CONNECTION_ID` frames.
444 pub struct ConnectionIdManager {
445 /// The `ConnectionIdGenerator` instance that is used to create connection IDs.
446 generator: Rc<RefCell<dyn ConnectionIdGenerator>>,
447 /// The connection IDs that we will accept.
448 /// This includes any we advertise in `NEW_CONNECTION_ID` that haven't been bound to a path
449 /// yet. During the handshake at the server, it also includes the randomized DCID pick by
450 /// the client.
451 connection_ids: ConnectionIdStore<()>,
452 /// The maximum number of connection IDs this will accept. This is at least 2 and won't
453 /// be more than `LOCAL_ACTIVE_CID_LIMIT`.
454 limit: usize,
455 /// The next sequence number that will be used for sending `NEW_CONNECTION_ID` frames.
456 next_seqno: u64,
457 /// Outstanding, but lost `NEW_CONNECTION_ID` frames will be stored here.
458 lost_new_connection_id: Vec<ConnectionIdEntry<[u8; 16]>>,
459 }
460
461 impl ConnectionIdManager {
462 pub fn new(generator: Rc<RefCell<dyn ConnectionIdGenerator>>, initial: ConnectionId) -> Self {
463 let mut connection_ids = ConnectionIdStore::default();
464 connection_ids.add_local(ConnectionIdEntry::initial_local(initial));
465 Self {
466 generator,
467 connection_ids,
468 // A note about initializing the limit to 2.
469 // For a server, the number of connection IDs that are tracked at the point that
470 // it is first possible to send `NEW_CONNECTION_ID` is 2. One is the client-generated
471 // destination connection (stored with a sequence number of `HANDSHAKE_SEQNO`); the
472 // other being the handshake value (seqno 0). As a result, `NEW_CONNECTION_ID`
473 // won't be sent until until after the handshake completes, because this initial
474 // value remains until the connection completes and transport parameters are handled.
475 limit: 2,
476 next_seqno: 1,
477 lost_new_connection_id: Vec::new(),
478 }
479 }
480
481 pub fn generator(&self) -> Rc<RefCell<dyn ConnectionIdGenerator>> {
482 Rc::clone(&self.generator)
483 }
484
485 pub fn decoder(&self) -> ConnectionIdDecoderRef {
486 ConnectionIdDecoderRef {
487 generator: self.generator.deref().borrow(),
488 }
489 }
490
491 /// Generate a connection ID and stateless reset token for a preferred address.
492 pub fn preferred_address_cid(&mut self) -> Res<(ConnectionId, [u8; 16])> {
493 if self.generator.deref().borrow().generates_empty_cids() {
494 return Err(Error::ConnectionIdsExhausted);
495 }
496 if let Some(cid) = self.generator.borrow_mut().generate_cid() {
497 assert_ne!(cid.len(), 0);
498 debug_assert_eq!(self.next_seqno, CONNECTION_ID_SEQNO_PREFERRED);
499 self.connection_ids
500 .add_local(ConnectionIdEntry::new(self.next_seqno, cid.clone(), ()));
501 self.next_seqno += 1;
502
503 let srt = ConnectionIdEntry::random_srt();
504 Ok((cid, srt))
505 } else {
506 Err(Error::ConnectionIdsExhausted)
507 }
508 }
509
510 pub fn is_valid(&self, cid: ConnectionIdRef) -> bool {
511 self.connection_ids.contains(cid)
512 }
513
514 pub fn retire(&mut self, seqno: u64) {
515 // TODO(mt) - consider keeping connection IDs around for a short while.
516
517 let empty_cid = seqno == CONNECTION_ID_SEQNO_EMPTY
518 || self
519 .connection_ids
520 .cids
521 .iter()
522 .any(|c| c.seqno == seqno && c.cid.is_empty());
523 if empty_cid {
524 qdebug!("Connection ID {seqno} is zero-length, not retiring");
525 } else {
526 self.connection_ids.retire(seqno);
527 self.lost_new_connection_id.retain(|cid| cid.seqno != seqno);
528 }
529 }
530
531 /// During the handshake, a server needs to regard the client's choice of destination
532 /// connection ID as valid. This function saves it in the store in a special place.
533 /// Note that this is only done *after* an Initial packet from the client is
534 /// successfully processed.
535 pub fn add_odcid(&mut self, cid: ConnectionId) {
536 let entry = ConnectionIdEntry::new(CONNECTION_ID_SEQNO_ODCID, cid, ());
537 self.connection_ids.add_local(entry);
538 }
539
540 /// Stop treating the original destination connection ID as valid.
541 pub fn remove_odcid(&mut self) {
542 self.connection_ids.retire(CONNECTION_ID_SEQNO_ODCID);
543 }
544
545 pub fn set_limit(&mut self, limit: u64) {
546 debug_assert!(limit >= 2);
547 self.limit = min(
548 LOCAL_ACTIVE_CID_LIMIT,
549 usize::try_from(limit).unwrap_or(LOCAL_ACTIVE_CID_LIMIT),
550 );
551 }
552
553 pub fn write_frames(
554 &mut self,
555 builder: &mut PacketBuilder,
556 tokens: &mut Vec<RecoveryToken>,
557 stats: &mut FrameStats,
558 ) {
559 if self.generator.deref().borrow().generates_empty_cids() {
560 debug_assert_eq!(
561 self.generator
562 .borrow_mut()
563 .generate_cid()
564 .expect("OK in debug assert")
565 .len(),
566 0
567 );
568 return;
569 }
570
571 while let Some(entry) = self.lost_new_connection_id.pop() {
572 if entry.write(builder, stats) {
573 tokens.push(RecoveryToken::NewConnectionId(entry));
574 } else {
575 // This shouldn't happen often.
576 self.lost_new_connection_id.push(entry);
577 break;
578 }
579 }
580
581 // Keep writing while we have fewer than the limit of active connection IDs
582 // and while there is room for more. This uses the longest connection ID
583 // length to simplify (assuming Retire Prior To is just 1 byte).
584 while self.connection_ids.len() < self.limit && builder.remaining() >= 47 {
585 let maybe_cid = self.generator.borrow_mut().generate_cid();
586 if let Some(cid) = maybe_cid {
587 assert_ne!(cid.len(), 0);
588 // TODO: generate the stateless reset tokens from the connection ID and a key.
589 let srt = ConnectionIdEntry::random_srt();
590
591 let seqno = self.next_seqno;
592 self.next_seqno += 1;
593 self.connection_ids
594 .add_local(ConnectionIdEntry::new(seqno, cid.clone(), ()));
595
596 let entry = ConnectionIdEntry::new(seqno, cid, srt);
597 entry.write(builder, stats);
598 tokens.push(RecoveryToken::NewConnectionId(entry));
599 }
600 }
601 }
602
603 pub fn lost(&mut self, entry: &ConnectionIdEntry<[u8; 16]>) {
604 self.lost_new_connection_id.push(entry.clone());
605 }
606
607 pub fn acked(&mut self, entry: &ConnectionIdEntry<[u8; 16]>) {
608 self.lost_new_connection_id
609 .retain(|e| e.seqno != entry.seqno);
610 }
611 }
612
613 #[cfg(test)]
614 mod tests {
615 use test_fixture::fixture_init;
616
617 use crate::{cid::MAX_CONNECTION_ID_LEN, ConnectionId};
618
619 #[test]
620 fn generate_initial_cid() {
621 fixture_init();
622 for _ in 0..100 {
623 let cid = ConnectionId::generate_initial();
624 assert!(
625 matches!(cid.len(), 8..=MAX_CONNECTION_ID_LEN),
626 "connection ID length {cid:?}",
627 );
628 }
629 }
630 }