91391d6589a354f06fcf0ab4c743f45c39602da2
[openssl.git] / ssl / quic / quic_rcidm.c
1 /*
2  * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
3  *
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
8  */
9
10 #include "internal/quic_rcidm.h"
11 #include "internal/priority_queue.h"
12 #include "internal/list.h"
13 #include "internal/common.h"
14
15 /*
16  * QUIC Remote Connection ID Manager
17  * =================================
18  *
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.
23  *
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
27  * RCIDs in order.
28  *
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.
33  *
34  * We use a priority queue for this purpose.
35  */
36 static void rcidm_update(QUIC_RCIDM *rcidm);
37 static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
38                                      const QUIC_CONN_ID *rcid);
39
40 #define PACKETS_PER_RCID        1000
41
42 #define INITIAL_SEQ_NUM         0
43 #define PREF_ADDR_SEQ_NUM       1
44
45 /*
46  * RCID
47  * ====
48  *
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.
54  *
55  * At any given time an RCID object is in one of these states:
56  *
57  *
58  *      (start)
59  *         |
60  *       [add]
61  *         |
62  *    _____v_____                 ___________                 ____________
63  *   |           |               |           |               |            |
64  *   |  PENDING  | --[select]--> |  CURRENT  | --[retire]--> |  RETIRING  |
65  *   |___________|               |___________|               |____________|
66  *                                                                  |
67  *                                                                [pop]
68  *                                                                  |
69  *                                                                  v
70  *                                                                (fin)
71  *
72  *   The transition through the states is monotonic and irreversible.
73  *   The RCID object is freed when it is popped.
74  *
75  *   PENDING
76  *     Invariants:
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.
82  *
83  *   CURRENT
84  *     Invariants:
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.
90  *
91  *   RETIRING
92  *     Invariants:
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.
98  *
99  *   Invariant: At most one RCID object is in the CURRENT state at any one time.
100  *
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.)
104  *
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.
109  */
110 enum {
111     RCID_STATE_PENDING,
112     RCID_STATE_CUR,
113     RCID_STATE_RETIRING,
114 };
115
116 enum {
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 */
120     /*
121      * INITIAL_ODCID and RETRY_ODCID also conceptually exist but are tracked
122      * separately.
123      */
124 };
125
126 typedef struct rcid_st {
127     OSSL_LIST_MEMBER(retiring, struct rcid_st); /* valid iff retire == 1 */
128
129     QUIC_CONN_ID    cid;        /* The actual CID string for this RCID */
130     uint64_t        seq_num;
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_* */
134 } RCID;
135
136 DEFINE_PRIORITY_QUEUE_OF(RCID);
137 DEFINE_LIST_OF(retiring, RCID);
138
139 /*
140  * RCID Manager
141  * ============
142  *
143  * The following "business logic" invariants also apply to the RCIDM
144  * as a whole:
145  *
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.
148  *
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.
159  *
160  */
161 struct quic_rcidm_st {
162     /*
163      * The current RCID we prefer to use (value undefined if
164      * !have_preferred_rcid).
165      */
166     QUIC_CONN_ID                preferred_rcid;
167
168     /*
169      * These are initialized if the corresponding added_ flags are set.
170      */
171     QUIC_CONN_ID                initial_odcid, retry_odcid;
172
173     /*
174      * Total number of packets sent since we last made a packet count-based RCID
175      * update decision.
176      */
177     uint64_t                    packets_sent;
178
179     /* Number of post-handshake RCID changes we have performed. */
180     uint64_t                    num_changes;
181
182     /*
183      * The Retire Prior To watermark value; max(retire_prior_to) of all received
184      * NCID frames.
185      */
186     uint64_t                    retire_prior_to;
187
188     /* (SORT BY seq_num ASC) -> (RCID *) */
189     PRIORITY_QUEUE_OF(RCID)     *rcids;
190
191     /*
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.
197      */
198     RCID                        *cur_rcid;
199
200     /*
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().
207      */
208     OSSL_LIST(retiring)         retiring_list;
209
210     /* preferred_rcid has been changed? */
211     unsigned int    preferred_rcid_changed          : 1;
212
213     /* Do we have any RCID we can use currently? */
214     unsigned int    have_preferred_rcid             : 1;
215
216     /* QUIC handshake has been completed? */
217     unsigned int    handshake_complete              : 1;
218
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;
227 };
228
229 static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
230                                   unsigned int state);
231
232 /* Check invariants of an RCID */
233 static void rcidm_check_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
234 {
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);
253 }
254
255 static int rcid_cmp(const RCID *a, const RCID *b)
256 {
257     if (a->seq_num < b->seq_num)
258         return -1;
259     if (a->seq_num > b->seq_num)
260         return 1;
261     if ((uintptr_t)a < (uintptr_t)b)
262         return -1;
263     if ((uintptr_t)a > (uintptr_t)b)
264         return 1;
265     return 0;
266 }
267
268 QUIC_RCIDM *ossl_quic_rcidm_new(const QUIC_CONN_ID *initial_odcid)
269 {
270     QUIC_RCIDM *rcidm;
271
272     if ((rcidm = OPENSSL_zalloc(sizeof(*rcidm))) == NULL)
273         return NULL;
274
275     if ((rcidm->rcids = ossl_pqueue_RCID_new(rcid_cmp)) == NULL) {
276         OPENSSL_free(rcidm);
277         return NULL;
278     }
279
280     if (initial_odcid != NULL) {
281         rcidm->initial_odcid        = *initial_odcid;
282         rcidm->added_initial_odcid  = 1;
283     }
284
285     rcidm_update(rcidm);
286     return rcidm;
287 }
288
289 void ossl_quic_rcidm_free(QUIC_RCIDM *rcidm)
290 {
291     RCID *rcid, *rnext;
292
293     if (rcidm == NULL)
294         return;
295
296     OPENSSL_free(rcidm->cur_rcid);
297     while ((rcid = ossl_pqueue_RCID_pop(rcidm->rcids)) != NULL)
298         OPENSSL_free(rcid);
299
300     LIST_FOREACH_DELSAFE(rcid, rnext, retiring, &rcidm->retiring_list)
301         OPENSSL_free(rcid);
302
303     ossl_pqueue_RCID_free(rcidm->rcids);
304     OPENSSL_free(rcidm);
305 }
306
307 static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
308                                      const QUIC_CONN_ID *rcid)
309 {
310     if (rcid == NULL) {
311         rcidm->preferred_rcid_changed   = 1;
312         rcidm->have_preferred_rcid      = 0;
313         return;
314     }
315
316     if (ossl_quic_conn_id_eq(&rcidm->preferred_rcid, rcid))
317         return;
318
319     rcidm->preferred_rcid           = *rcid;
320     rcidm->preferred_rcid_changed   = 1;
321     rcidm->have_preferred_rcid      = 1;
322 }
323
324 /*
325  * RCID Lifecycle Management
326  * =========================
327  */
328 static RCID *rcidm_create_rcid(QUIC_RCIDM *rcidm, uint64_t seq_num,
329                                const QUIC_CONN_ID *cid,
330                                unsigned int type)
331 {
332     RCID *rcid;
333
334     if (cid->id_len < 1 || cid->id_len > QUIC_MAX_CONN_ID_LEN
335         || seq_num > OSSL_QUIC_VLINT_MAX)
336         return NULL;
337
338     if ((rcid = OPENSSL_zalloc(sizeof(*rcid))) == NULL)
339         return NULL;
340
341     rcid->seq_num           = seq_num;
342     rcid->cid               = *cid;
343     rcid->type              = type;
344
345     if (rcid->seq_num >= rcidm->retire_prior_to) {
346         rcid->state = RCID_STATE_PENDING;
347
348         if (!ossl_pqueue_RCID_push(rcidm->rcids, rcid, &rcid->pq_idx)) {
349             assert(0);
350             OPENSSL_free(rcid);
351             return NULL;
352         }
353     } else {
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);
358     }
359
360     rcidm_check_rcid(rcidm, rcid);
361     return rcid;
362 }
363
364 static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
365                                   unsigned int state)
366 {
367     unsigned int old_state = rcid->state;
368
369     assert(state >= old_state && state <= RCID_STATE_RETIRING);
370     rcidm_check_rcid(rcidm, rcid);
371     if (state == old_state)
372         return;
373
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);
377     }
378
379     if (old_state == RCID_STATE_PENDING) {
380         ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
381         rcid->pq_idx = SIZE_MAX;
382     }
383
384     rcid->state = state;
385
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;
391
392         ossl_list_retiring_insert_tail(&rcidm->retiring_list, rcid);
393     }
394
395     rcidm_check_rcid(rcidm, rcid);
396 }
397
398 static void rcidm_free_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
399 {
400     if (rcid == NULL)
401         return;
402
403     rcidm_check_rcid(rcidm, rcid);
404
405     switch (rcid->state) {
406     case RCID_STATE_PENDING:
407         ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
408         break;
409     case RCID_STATE_CUR:
410         rcidm->cur_rcid = NULL;
411         break;
412     case RCID_STATE_RETIRING:
413         ossl_list_retiring_remove(&rcidm->retiring_list, rcid);
414         break;
415     default:
416         assert(0);
417         break;
418     }
419
420     OPENSSL_free(rcid);
421 }
422
423 static void rcidm_handle_retire_prior_to(QUIC_RCIDM *rcidm,
424                                          uint64_t retire_prior_to)
425 {
426     RCID *rcid;
427
428     if (retire_prior_to <= rcidm->retire_prior_to)
429         return;
430
431     /*
432      * Retire the current RCID (if any) if it is affected.
433      */
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);
436
437     /*
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
440      * threshold.
441      */
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);
445
446     rcidm->retire_prior_to = retire_prior_to;
447 }
448
449 /*
450  * Decision Logic
451  * ==============
452  */
453
454 static void rcidm_roll(QUIC_RCIDM *rcidm)
455 {
456     RCID *rcid;
457
458     if ((rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) == NULL)
459         return;
460
461     rcidm_transition_rcid(rcidm, rcid, RCID_STATE_CUR);
462
463     ++rcidm->num_changes;
464     rcidm->roll_requested = 0;
465
466     if (rcidm->packets_sent >= PACKETS_PER_RCID)
467         rcidm->packets_sent %= PACKETS_PER_RCID;
468     else
469         rcidm->packets_sent = 0;
470 }
471
472 static void rcidm_update(QUIC_RCIDM *rcidm)
473 {
474     RCID *rcid;
475
476     /*
477      * If we have no current numbered RCID but have one or more pending, use it.
478      */
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);
483     }
484
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);
489         return;
490     }
491
492     /*
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.
495      */
496     if (rcidm->added_retry_odcid) {
497         rcidm_set_preferred_rcid(rcidm, &rcidm->retry_odcid);
498         return;
499     }
500
501     if (rcidm->added_initial_odcid && !rcidm->handshake_complete) {
502         rcidm_set_preferred_rcid(rcidm, &rcidm->initial_odcid);
503         return;
504     }
505
506     /* We don't know of any usable RCIDs */
507     rcidm_set_preferred_rcid(rcidm, NULL);
508 }
509
510 static int rcidm_should_roll(QUIC_RCIDM *rcidm)
511 {
512     /*
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.
516      */
517     return rcidm->handshake_complete
518         && (rcidm->num_changes == 0
519             || rcidm->packets_sent >= PACKETS_PER_RCID
520             || rcidm->roll_requested);
521 }
522
523 static void rcidm_tick(QUIC_RCIDM *rcidm)
524 {
525     if (rcidm_should_roll(rcidm))
526         rcidm_roll(rcidm);
527
528     rcidm_update(rcidm);
529 }
530
531 /*
532  * Events
533  * ======
534  */
535 void ossl_quic_rcidm_on_handshake_complete(QUIC_RCIDM *rcidm)
536 {
537     if (rcidm->handshake_complete)
538         return;
539
540     rcidm->handshake_complete = 1;
541     rcidm_tick(rcidm);
542 }
543
544 void ossl_quic_rcidm_on_packet_sent(QUIC_RCIDM *rcidm, uint64_t num_packets)
545 {
546     if (num_packets == 0)
547         return;
548
549     rcidm->packets_sent += num_packets;
550     rcidm_tick(rcidm);
551 }
552
553 void ossl_quic_rcidm_request_roll(QUIC_RCIDM *rcidm)
554 {
555     rcidm->roll_requested = 1;
556     rcidm_tick(rcidm);
557 }
558
559 /*
560  * Mutation Operations
561  * ===================
562  */
563 int ossl_quic_rcidm_add_from_initial(QUIC_RCIDM *rcidm,
564                                      const QUIC_CONN_ID *rcid)
565 {
566     RCID *rcid_obj;
567
568     if (rcidm->added_initial_rcid || rcidm->handshake_complete)
569         return 0;
570
571     rcid_obj = rcidm_create_rcid(rcidm, INITIAL_SEQ_NUM,
572                                  rcid, RCID_TYPE_INITIAL);
573     if (rcid_obj == NULL)
574         return 0;
575
576     rcidm->added_initial_rcid = 1;
577     rcidm_tick(rcidm);
578     return 1;
579 }
580
581 int ossl_quic_rcidm_add_from_server_retry(QUIC_RCIDM *rcidm,
582                                           const QUIC_CONN_ID *retry_odcid)
583 {
584     if (rcidm->added_retry_odcid || rcidm->handshake_complete)
585         return 0;
586
587     rcidm->retry_odcid          = *retry_odcid;
588     rcidm->added_retry_odcid    = 1;
589     rcidm_tick(rcidm);
590     return 1;
591 }
592
593 int ossl_quic_rcidm_add_from_ncid(QUIC_RCIDM *rcidm,
594                                   const OSSL_QUIC_FRAME_NEW_CONN_ID *ncid)
595 {
596     RCID *rcid;
597
598     rcid = rcidm_create_rcid(rcidm, ncid->seq_num, &ncid->conn_id, RCID_TYPE_NCID);
599     if (rcid == NULL)
600         return 0;
601
602     rcidm_handle_retire_prior_to(rcidm, ncid->retire_prior_to);
603     rcidm_tick(rcidm);
604     return 1;
605 }
606
607 /*
608  * Queries
609  * =======
610  */
611
612 static int rcidm_get_retire(QUIC_RCIDM *rcidm, uint64_t *seq_num, int peek)
613 {
614     RCID *rcid = ossl_list_retiring_head(&rcidm->retiring_list);
615
616     if (rcid == NULL)
617         return 0;
618
619     if (seq_num != NULL)
620         *seq_num = rcid->seq_num;
621
622     if (!peek)
623         rcidm_free_rcid(rcidm, rcid);
624
625     return 1;
626 }
627
628 int ossl_quic_rcidm_pop_retire_seq_num(QUIC_RCIDM *rcidm,
629                                        uint64_t *seq_num)
630 {
631     return rcidm_get_retire(rcidm, seq_num, /*peek=*/0);
632 }
633
634 int ossl_quic_rcidm_peek_retire_seq_num(QUIC_RCIDM *rcidm,
635                                         uint64_t *seq_num)
636 {
637     return rcidm_get_retire(rcidm, seq_num, /*peek=*/1);
638 }
639
640 int ossl_quic_rcidm_get_preferred_tx_dcid(QUIC_RCIDM *rcidm,
641                                           QUIC_CONN_ID *tx_dcid)
642 {
643     if (!rcidm->have_preferred_rcid)
644         return 0;
645
646     *tx_dcid = rcidm->preferred_rcid;
647     return 1;
648 }
649
650 int ossl_quic_rcidm_get_preferred_tx_dcid_changed(QUIC_RCIDM *rcidm,
651                                                   int clear)
652 {
653     int r = rcidm->preferred_rcid_changed;
654
655     if (clear)
656         rcidm->preferred_rcid_changed = 0;
657
658     return r;
659 }
660
661 // TODO expose counters for enforcement