2 * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
10 #include "internal/quic_rcidm.h"
11 #include "internal/priority_queue.h"
12 #include "internal/list.h"
13 #include "internal/common.h"
16 * QUIC Remote Connection ID Manager
17 * =================================
19 * We can receive an arbitrary number of RCIDs via NCID frames. Periodically, we
20 * may desire (for example for anti-connection fingerprinting reasons, etc.)
21 * to switch to a new RCID according to some arbitrary policy such as the number
22 * of packets we have sent.
24 * When we do this we should move to the next RCID in the sequence of received
25 * RCIDs ordered by sequence number. For example, if a peer sends us three NCID
26 * frames with sequence numbers 10, 11, 12, we should seek to consume these
29 * However, due to the possibility of packet reordering in the network, NCID
30 * frames might be received out of order. Thus if a peer sends us NCID frames
31 * with sequence numbers 12, 10, 11, we should still consume the RCID with
32 * sequence number 10 before consuming the RCIDs with sequence numbers 11 or 12.
34 * We use a priority queue for this purpose.
36 static void rcidm_update(QUIC_RCIDM *rcidm);
37 static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
38 const QUIC_CONN_ID *rcid);
40 #define PACKETS_PER_RCID 1000
42 #define INITIAL_SEQ_NUM 0
43 #define PREF_ADDR_SEQ_NUM 1
49 * The RCID structure is used to track RCIDs which have sequence numbers (i.e.,
50 * INITIAL, PREF_ADDR and NCID type RCIDs). The RCIDs without sequence numbers
51 * (Initial ODCIDs and Retry ODCIDs), hereafter referred to as unnumbered RCIDs,
52 * can logically be viewed as their own type of RCID but are tracked separately
53 * as singletons without needing a discrete structure.
55 * At any given time an RCID object is in one of these states:
62 * _____v_____ ___________ ____________
64 * | PENDING | --[select]--> | CURRENT | --[retire]--> | RETIRING |
65 * |___________| |___________| |____________|
72 * The transition through the states is monotonic and irreversible.
73 * The RCID object is freed when it is popped.
77 * rcid->state == RCID_STATE_PENDING;
78 * rcid->pq_idx != SIZE_MAX (debug assert only);
79 * the RCID is not the current RCID, rcidm->cur_rcid != rcid;
80 * the RCID is in the priority queue;
81 * the RCID is not in the retiring_list.
85 * rcid->state == RCID_STATE_CUR;
86 * rcid->pq_idx == SIZE_MAX (debug assert only);
87 * the RCID is the current RCID, rcidm->cur_rcid == rcid;
88 * the RCID is not in the priority queue;
89 * the RCID is not in the retiring_list.
93 * rcid->state == RCID_STATE_RETIRING;
94 * rcid->pq_idx == SIZE_MAX (debug assert only);
95 * the RCID is not the current RCID, rcidm->cur_rcid != rcid;
96 * the RCID is not in the priority queue;
97 * the RCID is in the retiring_list.
99 * Invariant: At most one RCID object is in the CURRENT state at any one time.
101 * (If no RCID object is in the CURRENT state, this means either
102 * an unnumbered RCID is being used as the preferred RCID
103 * or we currently have no preferred RCID.)
105 * All of the above states can be considered substates of the 'ACTIVE' state
106 * for an RCID as specified in RFC 9000. A CID only ceases to be active
107 * when we send a RETIRE_CONN_ID frame, which is the responsibility of the
108 * user of the RCIDM and happens after the above state machine is terminated.
117 RCID_TYPE_INITIAL, /* CID is from an peer INITIAL packet (seq 0) */
118 RCID_TYPE_PREF_ADDR, /* CID is from a preferred_address TPARAM (seq 1) */
119 RCID_TYPE_NCID, /* CID is from a NCID frame */
121 * INITIAL_ODCID and RETRY_ODCID also conceptually exist but are tracked
126 typedef struct rcid_st {
127 OSSL_LIST_MEMBER(retiring, struct rcid_st); /* valid iff retire == 1 */
129 QUIC_CONN_ID cid; /* The actual CID string for this RCID */
131 size_t pq_idx; /* Index of entry into priority queue */
132 unsigned int state : 2; /* RCID_STATE_* */
133 unsigned int type : 2; /* RCID_TYPE_* */
136 DEFINE_PRIORITY_QUEUE_OF(RCID);
137 DEFINE_LIST_OF(retiring, RCID);
143 * The following "business logic" invariants also apply to the RCIDM
146 * Invariant: An RCID of INITIAL type has a sequence number of 0.
147 * Invariant: An RCID of PREF_ADDR type has a sequence number of 1.
149 * Invariant: There is never more than one Initial ODCID
150 * added throughout the lifetime of an RCIDM.
151 * Invariant: There is never more than one Retry ODCID
152 * added throughout the lifetime of an RCIDM.
153 * Invariant: There is never more than one INITIAL RCID created
154 * throughout the lifetime of an RCIDM.
155 * Invariant: There is never more than one PREF_ADDR RCID created
156 * throughout the lifetime of an RCIDM.
157 * Invariant: No INITIAL or PREF_ADDR RCID may be added after
158 * the handshake is completed.
161 struct quic_rcidm_st {
163 * The current RCID we prefer to use (value undefined if
164 * !have_preferred_rcid).
166 QUIC_CONN_ID preferred_rcid;
169 * These are initialized if the corresponding added_ flags are set.
171 QUIC_CONN_ID initial_odcid, retry_odcid;
174 * Total number of packets sent since we last made a packet count-based RCID
177 uint64_t packets_sent;
179 /* Number of post-handshake RCID changes we have performed. */
180 uint64_t num_changes;
183 * The Retire Prior To watermark value; max(retire_prior_to) of all received
186 uint64_t retire_prior_to;
188 /* (SORT BY seq_num ASC) -> (RCID *) */
189 PRIORITY_QUEUE_OF(RCID) *rcids;
192 * Current RCID we are using. This may differ from the first item in the
193 * priority queue if we received NCID frames out of order. For example if we
194 * get seq 5, switch to it immediately, then get seq 4, we want to keep
195 * using seq 5 until we decide to roll again rather than immediately switch
196 * to seq 4. Never points to an object on the retiring_list.
201 * When a RCID becomes pending-retirement, it is moved to the retiring_list,
202 * then freed when it is popped from the retired queue. We use a list for
203 * this rather than a priority queue as the order in which items are freed
204 * does not matter. We always append to the tail of the list in order to
205 * maintain the guarantee that the head (if present) only changes when a
206 * caller calls pop().
208 OSSL_LIST(retiring) retiring_list;
210 /* preferred_rcid has been changed? */
211 unsigned int preferred_rcid_changed : 1;
213 /* Do we have any RCID we can use currently? */
214 unsigned int have_preferred_rcid : 1;
216 /* QUIC handshake has been completed? */
217 unsigned int handshake_complete : 1;
219 /* odcid was set (not necessarily still valid as a RCID)? */
220 unsigned int added_initial_odcid : 1;
221 /* retry_odcid was set (not necessarily still valid as a RCID?) */
222 unsigned int added_retry_odcid : 1;
223 /* An initial RCID was added as an RCID structure? */
224 unsigned int added_initial_rcid : 1;
225 /* Has a RCID roll been manually requested? */
226 unsigned int roll_requested : 1;
229 static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
232 /* Check invariants of an RCID */
233 static void rcidm_check_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
235 assert(rcid->state == RCID_STATE_PENDING
236 || rcid->state == RCID_STATE_CUR
237 || rcid->state == RCID_STATE_RETIRING);
238 assert((rcid->state == RCID_STATE_PENDING)
239 == (rcid->pq_idx != SIZE_MAX));
240 assert((rcid->state == RCID_STATE_CUR)
241 == (rcidm->cur_rcid == rcid));
242 assert((ossl_list_retiring_next(rcid) != NULL
243 || ossl_list_retiring_prev(rcid) != NULL
244 || ossl_list_retiring_head(&rcidm->retiring_list) == rcid)
245 == (rcid->state == RCID_STATE_RETIRING));
246 assert(rcid->type != RCID_TYPE_INITIAL || rcid->seq_num == 0);
247 assert(rcid->type != RCID_TYPE_PREF_ADDR || rcid->seq_num == 1);
248 assert(rcid->seq_num <= OSSL_QUIC_VLINT_MAX);
249 assert(rcid->cid.id_len > 0 && rcid->cid.id_len <= QUIC_MAX_CONN_ID_LEN);
250 assert(rcid->seq_num >= rcidm->retire_prior_to
251 || rcid->state == RCID_STATE_RETIRING);
252 assert(rcidm->num_changes == 0 || rcidm->handshake_complete);
255 static int rcid_cmp(const RCID *a, const RCID *b)
257 if (a->seq_num < b->seq_num)
259 if (a->seq_num > b->seq_num)
261 if ((uintptr_t)a < (uintptr_t)b)
263 if ((uintptr_t)a > (uintptr_t)b)
268 QUIC_RCIDM *ossl_quic_rcidm_new(const QUIC_CONN_ID *initial_odcid)
272 if ((rcidm = OPENSSL_zalloc(sizeof(*rcidm))) == NULL)
275 if ((rcidm->rcids = ossl_pqueue_RCID_new(rcid_cmp)) == NULL) {
280 if (initial_odcid != NULL) {
281 rcidm->initial_odcid = *initial_odcid;
282 rcidm->added_initial_odcid = 1;
289 void ossl_quic_rcidm_free(QUIC_RCIDM *rcidm)
296 OPENSSL_free(rcidm->cur_rcid);
297 while ((rcid = ossl_pqueue_RCID_pop(rcidm->rcids)) != NULL)
300 LIST_FOREACH_DELSAFE(rcid, rnext, retiring, &rcidm->retiring_list)
303 ossl_pqueue_RCID_free(rcidm->rcids);
307 static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
308 const QUIC_CONN_ID *rcid)
311 rcidm->preferred_rcid_changed = 1;
312 rcidm->have_preferred_rcid = 0;
316 if (ossl_quic_conn_id_eq(&rcidm->preferred_rcid, rcid))
319 rcidm->preferred_rcid = *rcid;
320 rcidm->preferred_rcid_changed = 1;
321 rcidm->have_preferred_rcid = 1;
325 * RCID Lifecycle Management
326 * =========================
328 static RCID *rcidm_create_rcid(QUIC_RCIDM *rcidm, uint64_t seq_num,
329 const QUIC_CONN_ID *cid,
334 if (cid->id_len < 1 || cid->id_len > QUIC_MAX_CONN_ID_LEN
335 || seq_num > OSSL_QUIC_VLINT_MAX)
338 if ((rcid = OPENSSL_zalloc(sizeof(*rcid))) == NULL)
341 rcid->seq_num = seq_num;
345 if (rcid->seq_num >= rcidm->retire_prior_to) {
346 rcid->state = RCID_STATE_PENDING;
348 if (!ossl_pqueue_RCID_push(rcidm->rcids, rcid, &rcid->pq_idx)) {
354 /* RCID is immediately retired upon creation. */
355 rcid->state = RCID_STATE_RETIRING;
356 rcid->pq_idx = SIZE_MAX;
357 ossl_list_retiring_insert_tail(&rcidm->retiring_list, rcid);
360 rcidm_check_rcid(rcidm, rcid);
364 static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
367 unsigned int old_state = rcid->state;
369 assert(state >= old_state && state <= RCID_STATE_RETIRING);
370 rcidm_check_rcid(rcidm, rcid);
371 if (state == old_state)
374 if (rcidm->cur_rcid != NULL && state == RCID_STATE_CUR) {
375 rcidm_transition_rcid(rcidm, rcidm->cur_rcid, RCID_STATE_RETIRING);
376 assert(rcidm->cur_rcid == NULL);
379 if (old_state == RCID_STATE_PENDING) {
380 ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
381 rcid->pq_idx = SIZE_MAX;
386 if (state == RCID_STATE_CUR) {
387 rcidm->cur_rcid = rcid;
388 } else if (state == RCID_STATE_RETIRING) {
389 if (old_state == RCID_STATE_CUR)
390 rcidm->cur_rcid = NULL;
392 ossl_list_retiring_insert_tail(&rcidm->retiring_list, rcid);
395 rcidm_check_rcid(rcidm, rcid);
398 static void rcidm_free_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
403 rcidm_check_rcid(rcidm, rcid);
405 switch (rcid->state) {
406 case RCID_STATE_PENDING:
407 ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
410 rcidm->cur_rcid = NULL;
412 case RCID_STATE_RETIRING:
413 ossl_list_retiring_remove(&rcidm->retiring_list, rcid);
423 static void rcidm_handle_retire_prior_to(QUIC_RCIDM *rcidm,
424 uint64_t retire_prior_to)
428 if (retire_prior_to <= rcidm->retire_prior_to)
432 * Retire the current RCID (if any) if it is affected.
434 if (rcidm->cur_rcid != NULL && rcidm->cur_rcid->seq_num < retire_prior_to)
435 rcidm_transition_rcid(rcidm, rcidm->cur_rcid, RCID_STATE_RETIRING);
438 * Any other RCIDs needing retirement will be at the start of the priority
439 * queue, so just stop once we see a higher sequence number exceeding the
442 while ((rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) != NULL
443 && rcid->seq_num < retire_prior_to)
444 rcidm_transition_rcid(rcidm, rcid, RCID_STATE_RETIRING);
446 rcidm->retire_prior_to = retire_prior_to;
454 static void rcidm_roll(QUIC_RCIDM *rcidm)
458 if ((rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) == NULL)
461 rcidm_transition_rcid(rcidm, rcid, RCID_STATE_CUR);
463 ++rcidm->num_changes;
464 rcidm->roll_requested = 0;
466 if (rcidm->packets_sent >= PACKETS_PER_RCID)
467 rcidm->packets_sent %= PACKETS_PER_RCID;
469 rcidm->packets_sent = 0;
472 static void rcidm_update(QUIC_RCIDM *rcidm)
477 * If we have no current numbered RCID but have one or more pending, use it.
479 if (rcidm->cur_rcid == NULL
480 && (rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) != NULL) {
481 rcidm_transition_rcid(rcidm, rcid, RCID_STATE_CUR);
482 assert(rcidm->cur_rcid != NULL);
485 /* Prefer use of any current numbered RCID we have, if possible. */
486 if (rcidm->cur_rcid != NULL) {
487 rcidm_check_rcid(rcidm, rcidm->cur_rcid);
488 rcidm_set_preferred_rcid(rcidm, &rcidm->cur_rcid->cid);
493 * If there are no RCIDs from NCID frames we can use, go through the various
494 * kinds of bootstrapping RCIDs we can use in order of priority.
496 if (rcidm->added_retry_odcid) {
497 rcidm_set_preferred_rcid(rcidm, &rcidm->retry_odcid);
501 if (rcidm->added_initial_odcid && !rcidm->handshake_complete) {
502 rcidm_set_preferred_rcid(rcidm, &rcidm->initial_odcid);
506 /* We don't know of any usable RCIDs */
507 rcidm_set_preferred_rcid(rcidm, NULL);
510 static int rcidm_should_roll(QUIC_RCIDM *rcidm)
513 * Always switch as soon as possible if handshake completes;
514 * and every n packets after handshake completes or the last roll; and
515 * whenever manually requested.
517 return rcidm->handshake_complete
518 && (rcidm->num_changes == 0
519 || rcidm->packets_sent >= PACKETS_PER_RCID
520 || rcidm->roll_requested);
523 static void rcidm_tick(QUIC_RCIDM *rcidm)
525 if (rcidm_should_roll(rcidm))
535 void ossl_quic_rcidm_on_handshake_complete(QUIC_RCIDM *rcidm)
537 if (rcidm->handshake_complete)
540 rcidm->handshake_complete = 1;
544 void ossl_quic_rcidm_on_packet_sent(QUIC_RCIDM *rcidm, uint64_t num_packets)
546 if (num_packets == 0)
549 rcidm->packets_sent += num_packets;
553 void ossl_quic_rcidm_request_roll(QUIC_RCIDM *rcidm)
555 rcidm->roll_requested = 1;
560 * Mutation Operations
561 * ===================
563 int ossl_quic_rcidm_add_from_initial(QUIC_RCIDM *rcidm,
564 const QUIC_CONN_ID *rcid)
568 if (rcidm->added_initial_rcid || rcidm->handshake_complete)
571 rcid_obj = rcidm_create_rcid(rcidm, INITIAL_SEQ_NUM,
572 rcid, RCID_TYPE_INITIAL);
573 if (rcid_obj == NULL)
576 rcidm->added_initial_rcid = 1;
581 int ossl_quic_rcidm_add_from_server_retry(QUIC_RCIDM *rcidm,
582 const QUIC_CONN_ID *retry_odcid)
584 if (rcidm->added_retry_odcid || rcidm->handshake_complete)
587 rcidm->retry_odcid = *retry_odcid;
588 rcidm->added_retry_odcid = 1;
593 int ossl_quic_rcidm_add_from_ncid(QUIC_RCIDM *rcidm,
594 const OSSL_QUIC_FRAME_NEW_CONN_ID *ncid)
598 rcid = rcidm_create_rcid(rcidm, ncid->seq_num, &ncid->conn_id, RCID_TYPE_NCID);
602 rcidm_handle_retire_prior_to(rcidm, ncid->retire_prior_to);
612 static int rcidm_get_retire(QUIC_RCIDM *rcidm, uint64_t *seq_num, int peek)
614 RCID *rcid = ossl_list_retiring_head(&rcidm->retiring_list);
620 *seq_num = rcid->seq_num;
623 rcidm_free_rcid(rcidm, rcid);
628 int ossl_quic_rcidm_pop_retire_seq_num(QUIC_RCIDM *rcidm,
631 return rcidm_get_retire(rcidm, seq_num, /*peek=*/0);
634 int ossl_quic_rcidm_peek_retire_seq_num(QUIC_RCIDM *rcidm,
637 return rcidm_get_retire(rcidm, seq_num, /*peek=*/1);
640 int ossl_quic_rcidm_get_preferred_tx_dcid(QUIC_RCIDM *rcidm,
641 QUIC_CONN_ID *tx_dcid)
643 if (!rcidm->have_preferred_rcid)
646 *tx_dcid = rcidm->preferred_rcid;
650 int ossl_quic_rcidm_get_preferred_tx_dcid_changed(QUIC_RCIDM *rcidm,
653 int r = rcidm->preferred_rcid_changed;
656 rcidm->preferred_rcid_changed = 0;
661 // TODO expose counters for enforcement