quic_rcidm.c
/*
* Copyright 2023-2024 The OpenSSL Project Authors. All Rights Reserved.
*
* Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
* in the file LICENSE in the source distribution or at
* https://www.openssl.org/source/license.html
*/
#include "internal/quic_rcidm.h"
#include "internal/priority_queue.h"
#include "internal/list.h"
#include "internal/common.h"
/*
* QUIC Remote Connection ID Manager
* =================================
*
* We can receive an arbitrary number of RCIDs via NCID frames. Periodically, we
* may desire (for example for anti-connection fingerprinting reasons, etc.)
* to switch to a new RCID according to some arbitrary policy such as the number
* of packets we have sent.
*
* When we do this we should move to the next RCID in the sequence of received
* RCIDs ordered by sequence number. For example, if a peer sends us three NCID
* frames with sequence numbers 10, 11, 12, we should seek to consume these
* RCIDs in order.
*
* However, due to the possibility of packet reordering in the network, NCID
* frames might be received out of order. Thus if a peer sends us NCID frames
* with sequence numbers 12, 10, 11, we should still consume the RCID with
* sequence number 10 before consuming the RCIDs with sequence numbers 11 or 12.
*
* We use a priority queue for this purpose.
*/
static void rcidm_update(QUIC_RCIDM *rcidm);
static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
const QUIC_CONN_ID *rcid);
#define PACKETS_PER_RCID 10000
#define INITIAL_SEQ_NUM 0
#define PREF_ADDR_SEQ_NUM 1
/*
* RCID
* ====
*
* The RCID structure is used to track RCIDs which have sequence numbers (i.e.,
* INITIAL, PREF_ADDR and NCID type RCIDs). The RCIDs without sequence numbers
* (Initial ODCIDs and Retry ODCIDs), hereafter referred to as unnumbered RCIDs,
* can logically be viewed as their own type of RCID but are tracked separately
* as singletons without needing a discrete structure.
*
* At any given time an RCID object is in one of these states:
*
*
* (start)
* |
* [add]
* |
* _____v_____ ___________ ____________
* | | | | | |
* | PENDING | --[select]--> | CURRENT | --[retire]--> | RETIRING |
* |___________| |___________| |____________|
* |
* [pop]
* |
* v
* (fin)
*
* The transition through the states is monotonic and irreversible.
* The RCID object is freed when it is popped.
*
* PENDING
* Invariants:
* rcid->state == RCID_STATE_PENDING;
* rcid->pq_idx != SIZE_MAX (debug assert only);
* the RCID is not the current RCID, rcidm->cur_rcid != rcid;
* the RCID is in the priority queue;
* the RCID is not in the retiring_list.
*
* CURRENT
* Invariants:
* rcid->state == RCID_STATE_CUR;
* rcid->pq_idx == SIZE_MAX (debug assert only);
* the RCID is the current RCID, rcidm->cur_rcid == rcid;
* the RCID is not in the priority queue;
* the RCID is not in the retiring_list.
*
* RETIRING
* Invariants:
* rcid->state == RCID_STATE_RETIRING;
* rcid->pq_idx == SIZE_MAX (debug assert only);
* the RCID is not the current RCID, rcidm->cur_rcid != rcid;
* the RCID is not in the priority queue;
* the RCID is in the retiring_list.
*
* Invariant: At most one RCID object is in the CURRENT state at any one time.
*
* (If no RCID object is in the CURRENT state, this means either
* an unnumbered RCID is being used as the preferred RCID
* or we currently have no preferred RCID.)
*
* All of the above states can be considered substates of the 'ACTIVE' state
* for an RCID as specified in RFC 9000. A CID only ceases to be active
* when we send a RETIRE_CONN_ID frame, which is the responsibility of the
* user of the RCIDM and happens after the above state machine is terminated.
*/
enum {
RCID_STATE_PENDING,
RCID_STATE_CUR,
RCID_STATE_RETIRING
};
enum {
RCID_TYPE_INITIAL, /* CID is from an peer INITIAL packet (seq 0) */
RCID_TYPE_PREF_ADDR, /* CID is from a preferred_address TPARAM (seq 1) */
RCID_TYPE_NCID /* CID is from a NCID frame */
/*
* INITIAL_ODCID and RETRY_ODCID also conceptually exist but are tracked
* separately.
*/
};
typedef struct rcid_st {
OSSL_LIST_MEMBER(retiring, struct rcid_st); /* valid iff RETIRING */
QUIC_CONN_ID cid; /* The actual CID string for this RCID */
uint64_t seq_num;
size_t pq_idx; /* Index of entry into priority queue */
unsigned int state : 2; /* RCID_STATE_* */
unsigned int type : 2; /* RCID_TYPE_* */
} RCID;
DEFINE_PRIORITY_QUEUE_OF(RCID);
DEFINE_LIST_OF(retiring, RCID);
/*
* RCID Manager
* ============
*
* The following "business logic" invariants also apply to the RCIDM
* as a whole:
*
* Invariant: An RCID of INITIAL type has a sequence number of 0.
* Invariant: An RCID of PREF_ADDR type has a sequence number of 1.
*
* Invariant: There is never more than one Initial ODCID
* added throughout the lifetime of an RCIDM.
* Invariant: There is never more than one Retry ODCID
* added throughout the lifetime of an RCIDM.
* Invariant: There is never more than one INITIAL RCID created
* throughout the lifetime of an RCIDM.
* Invariant: There is never more than one PREF_ADDR RCID created
* throughout the lifetime of an RCIDM.
* Invariant: No INITIAL or PREF_ADDR RCID may be added after
* the handshake is completed.
*
*/
struct quic_rcidm_st {
/*
* The current RCID we prefer to use (value undefined if
* !have_preferred_rcid).
*
* This is preferentially set to a numbered RCID (represented by an RCID
* object) if we have one (in which case preferred_rcid == cur_rcid->cid);
* otherwise it is set to one of the unnumbered RCIDs (the Initial ODCID or
* Retry ODCID) if available (and cur_rcid == NULL).
*/
QUIC_CONN_ID preferred_rcid;
/*
* These are initialized if the corresponding added_ flags are set.
*/
QUIC_CONN_ID initial_odcid, retry_odcid;
/*
* Total number of packets sent since we last made a packet count-based RCID
* update decision.
*/
uint64_t packets_sent;
/* Number of post-handshake RCID changes we have performed. */
uint64_t num_changes;
/*
* The Retire Prior To watermark value; max(retire_prior_to) of all received
* NCID frames.
*/
uint64_t retire_prior_to;
/* (SORT BY seq_num ASC) -> (RCID *) */
PRIORITY_QUEUE_OF(RCID) *rcids;
/*
* Current RCID object we are using. This may differ from the first item in
* the priority queue if we received NCID frames out of order. For example
* if we get seq 5, switch to it immediately, then get seq 4, we want to
* keep using seq 5 until we decide to roll again rather than immediately
* switch to seq 4. Never points to an object on the retiring_list.
*/
RCID *cur_rcid;
/*
* When a RCID becomes pending-retirement, it is moved to the retiring_list,
* then freed when it is popped from the retired queue. We use a list for
* this rather than a priority queue as the order in which items are freed
* does not matter. We always append to the tail of the list in order to
* maintain the guarantee that the head (if present) only changes when a
* caller calls pop().
*/
OSSL_LIST(retiring) retiring_list;
/* Number of entries on the retiring_list. */
size_t num_retiring;
/* preferred_rcid has been changed? */
unsigned int preferred_rcid_changed : 1;
/* Do we have any RCID we can use currently? */
unsigned int have_preferred_rcid : 1;
/* QUIC handshake has been completed? */
unsigned int handshake_complete : 1;
/* odcid was set (not necessarily still valid as a RCID)? */
unsigned int added_initial_odcid : 1;
/* retry_odcid was set (not necessarily still valid as a RCID?) */
unsigned int added_retry_odcid : 1;
/* An initial RCID was added as an RCID structure? */
unsigned int added_initial_rcid : 1;
/* Has a RCID roll been manually requested? */
unsigned int roll_requested : 1;
};
/*
* Caller must periodically pop retired RCIDs and handle them. If the caller
* fails to do so, fail safely rather than start exhibiting integer rollover.
* Limit the total number of numbered RCIDs to an implausibly large but safe
* value.
*/
#define MAX_NUMBERED_RCIDS (SIZE_MAX / 2)
static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
unsigned int state);
/* Check invariants of an RCID */
static void rcidm_check_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
{
assert(rcid->state == RCID_STATE_PENDING
|| rcid->state == RCID_STATE_CUR
|| rcid->state == RCID_STATE_RETIRING);
assert((rcid->state == RCID_STATE_PENDING)
== (rcid->pq_idx != SIZE_MAX));
assert((rcid->state == RCID_STATE_CUR)
== (rcidm->cur_rcid == rcid));
assert((ossl_list_retiring_next(rcid) != NULL
|| ossl_list_retiring_prev(rcid) != NULL
|| ossl_list_retiring_head(&rcidm->retiring_list) == rcid)
== (rcid->state == RCID_STATE_RETIRING));
assert(rcid->type != RCID_TYPE_INITIAL || rcid->seq_num == 0);
assert(rcid->type != RCID_TYPE_PREF_ADDR || rcid->seq_num == 1);
assert(rcid->seq_num <= OSSL_QUIC_VLINT_MAX);
assert(rcid->cid.id_len > 0 && rcid->cid.id_len <= QUIC_MAX_CONN_ID_LEN);
assert(rcid->seq_num >= rcidm->retire_prior_to
|| rcid->state == RCID_STATE_RETIRING);
assert(rcidm->num_changes == 0 || rcidm->handshake_complete);
assert(rcid->state != RCID_STATE_RETIRING || rcidm->num_retiring > 0);
}
static int rcid_cmp(const RCID *a, const RCID *b)
{
if (a->seq_num < b->seq_num)
return -1;
if (a->seq_num > b->seq_num)
return 1;
return 0;
}
QUIC_RCIDM *ossl_quic_rcidm_new(const QUIC_CONN_ID *initial_odcid)
{
QUIC_RCIDM *rcidm;
if ((rcidm = OPENSSL_zalloc(sizeof(*rcidm))) == NULL)
return NULL;
if ((rcidm->rcids = ossl_pqueue_RCID_new(rcid_cmp)) == NULL) {
OPENSSL_free(rcidm);
return NULL;
}
if (initial_odcid != NULL) {
rcidm->initial_odcid = *initial_odcid;
rcidm->added_initial_odcid = 1;
}
rcidm_update(rcidm);
return rcidm;
}
void ossl_quic_rcidm_free(QUIC_RCIDM *rcidm)
{
RCID *rcid, *rnext;
if (rcidm == NULL)
return;
OPENSSL_free(rcidm->cur_rcid);
while ((rcid = ossl_pqueue_RCID_pop(rcidm->rcids)) != NULL)
OPENSSL_free(rcid);
LIST_FOREACH_DELSAFE(rcid, rnext, retiring, &rcidm->retiring_list)
OPENSSL_free(rcid);
ossl_pqueue_RCID_free(rcidm->rcids);
OPENSSL_free(rcidm);
}
static void rcidm_set_preferred_rcid(QUIC_RCIDM *rcidm,
const QUIC_CONN_ID *rcid)
{
if (rcid == NULL) {
rcidm->preferred_rcid_changed = 1;
rcidm->have_preferred_rcid = 0;
return;
}
if (ossl_quic_conn_id_eq(&rcidm->preferred_rcid, rcid))
return;
rcidm->preferred_rcid = *rcid;
rcidm->preferred_rcid_changed = 1;
rcidm->have_preferred_rcid = 1;
}
/*
* RCID Lifecycle Management
* =========================
*/
static RCID *rcidm_create_rcid(QUIC_RCIDM *rcidm, uint64_t seq_num,
const QUIC_CONN_ID *cid,
unsigned int type)
{
RCID *rcid;
if (cid->id_len < 1 || cid->id_len > QUIC_MAX_CONN_ID_LEN
|| seq_num > OSSL_QUIC_VLINT_MAX
|| ossl_pqueue_RCID_num(rcidm->rcids) + rcidm->num_retiring
> MAX_NUMBERED_RCIDS)
return NULL;
if ((rcid = OPENSSL_zalloc(sizeof(*rcid))) == NULL)
return NULL;
rcid->seq_num = seq_num;
rcid->cid = *cid;
rcid->type = type;
if (rcid->seq_num >= rcidm->retire_prior_to) {
rcid->state = RCID_STATE_PENDING;
if (!ossl_pqueue_RCID_push(rcidm->rcids, rcid, &rcid->pq_idx)) {
OPENSSL_free(rcid);
return NULL;
}
} else {
/* RCID is immediately retired upon creation. */
rcid->state = RCID_STATE_RETIRING;
rcid->pq_idx = SIZE_MAX;
ossl_list_retiring_insert_tail(&rcidm->retiring_list, rcid);
++rcidm->num_retiring;
}
rcidm_check_rcid(rcidm, rcid);
return rcid;
}
static void rcidm_transition_rcid(QUIC_RCIDM *rcidm, RCID *rcid,
unsigned int state)
{
unsigned int old_state = rcid->state;
assert(state >= old_state && state <= RCID_STATE_RETIRING);
rcidm_check_rcid(rcidm, rcid);
if (state == old_state)
return;
if (rcidm->cur_rcid != NULL && state == RCID_STATE_CUR) {
rcidm_transition_rcid(rcidm, rcidm->cur_rcid, RCID_STATE_RETIRING);
assert(rcidm->cur_rcid == NULL);
}
if (old_state == RCID_STATE_PENDING) {
ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
rcid->pq_idx = SIZE_MAX;
}
rcid->state = state;
if (state == RCID_STATE_CUR) {
rcidm->cur_rcid = rcid;
} else if (state == RCID_STATE_RETIRING) {
if (old_state == RCID_STATE_CUR)
rcidm->cur_rcid = NULL;
ossl_list_retiring_insert_tail(&rcidm->retiring_list, rcid);
++rcidm->num_retiring;
}
rcidm_check_rcid(rcidm, rcid);
}
static void rcidm_free_rcid(QUIC_RCIDM *rcidm, RCID *rcid)
{
if (rcid == NULL)
return;
rcidm_check_rcid(rcidm, rcid);
switch (rcid->state) {
case RCID_STATE_PENDING:
ossl_pqueue_RCID_remove(rcidm->rcids, rcid->pq_idx);
break;
case RCID_STATE_CUR:
rcidm->cur_rcid = NULL;
break;
case RCID_STATE_RETIRING:
ossl_list_retiring_remove(&rcidm->retiring_list, rcid);
--rcidm->num_retiring;
break;
default:
assert(0);
break;
}
OPENSSL_free(rcid);
}
static void rcidm_handle_retire_prior_to(QUIC_RCIDM *rcidm,
uint64_t retire_prior_to)
{
RCID *rcid;
if (retire_prior_to <= rcidm->retire_prior_to)
return;
/*
* Retire the current RCID (if any) if it is affected.
*/
if (rcidm->cur_rcid != NULL && rcidm->cur_rcid->seq_num < retire_prior_to)
rcidm_transition_rcid(rcidm, rcidm->cur_rcid, RCID_STATE_RETIRING);
/*
* Any other RCIDs needing retirement will be at the start of the priority
* queue, so just stop once we see a higher sequence number exceeding the
* threshold.
*/
while ((rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) != NULL
&& rcid->seq_num < retire_prior_to)
rcidm_transition_rcid(rcidm, rcid, RCID_STATE_RETIRING);
rcidm->retire_prior_to = retire_prior_to;
}
/*
* Decision Logic
* ==============
*/
static void rcidm_roll(QUIC_RCIDM *rcidm)
{
RCID *rcid;
if ((rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) == NULL)
return;
rcidm_transition_rcid(rcidm, rcid, RCID_STATE_CUR);
++rcidm->num_changes;
rcidm->roll_requested = 0;
if (rcidm->packets_sent >= PACKETS_PER_RCID)
rcidm->packets_sent %= PACKETS_PER_RCID;
else
rcidm->packets_sent = 0;
}
static void rcidm_update(QUIC_RCIDM *rcidm)
{
RCID *rcid;
/*
* If we have no current numbered RCID but have one or more pending, use it.
*/
if (rcidm->cur_rcid == NULL
&& (rcid = ossl_pqueue_RCID_peek(rcidm->rcids)) != NULL) {
rcidm_transition_rcid(rcidm, rcid, RCID_STATE_CUR);
assert(rcidm->cur_rcid != NULL);
}
/* Prefer use of any current numbered RCID we have, if possible. */
if (rcidm->cur_rcid != NULL) {
rcidm_check_rcid(rcidm, rcidm->cur_rcid);
rcidm_set_preferred_rcid(rcidm, &rcidm->cur_rcid->cid);
return;
}
/*
* If there are no RCIDs from NCID frames we can use, go through the various
* kinds of bootstrapping RCIDs we can use in order of priority.
*/
if (rcidm->added_retry_odcid && !rcidm->handshake_complete) {
rcidm_set_preferred_rcid(rcidm, &rcidm->retry_odcid);
return;
}
if (rcidm->added_initial_odcid && !rcidm->handshake_complete) {
rcidm_set_preferred_rcid(rcidm, &rcidm->initial_odcid);
return;
}
/* We don't know of any usable RCIDs */
rcidm_set_preferred_rcid(rcidm, NULL);
}
static int rcidm_should_roll(QUIC_RCIDM *rcidm)
{
/*
* Always switch as soon as possible if handshake completes;
* and every n packets after handshake completes or the last roll; and
* whenever manually requested.
*/
return rcidm->handshake_complete
&& (rcidm->num_changes == 0
|| rcidm->packets_sent >= PACKETS_PER_RCID
|| rcidm->roll_requested);
}
static void rcidm_tick(QUIC_RCIDM *rcidm)
{
if (rcidm_should_roll(rcidm))
rcidm_roll(rcidm);
rcidm_update(rcidm);
}
/*
* Events
* ======
*/
void ossl_quic_rcidm_on_handshake_complete(QUIC_RCIDM *rcidm)
{
if (rcidm->handshake_complete)
return;
rcidm->handshake_complete = 1;
rcidm_tick(rcidm);
}
void ossl_quic_rcidm_on_packet_sent(QUIC_RCIDM *rcidm, uint64_t num_packets)
{
if (num_packets == 0)
return;
rcidm->packets_sent += num_packets;
rcidm_tick(rcidm);
}
void ossl_quic_rcidm_request_roll(QUIC_RCIDM *rcidm)
{
rcidm->roll_requested = 1;
rcidm_tick(rcidm);
}
/*
* Mutation Operations
* ===================
*/
int ossl_quic_rcidm_add_from_initial(QUIC_RCIDM *rcidm,
const QUIC_CONN_ID *rcid)
{
RCID *rcid_obj;
if (rcidm->added_initial_rcid || rcidm->handshake_complete)
return 0;
rcid_obj = rcidm_create_rcid(rcidm, INITIAL_SEQ_NUM,
rcid, RCID_TYPE_INITIAL);
if (rcid_obj == NULL)
return 0;
rcidm->added_initial_rcid = 1;
rcidm_tick(rcidm);
return 1;
}
int ossl_quic_rcidm_add_from_server_retry(QUIC_RCIDM *rcidm,
const QUIC_CONN_ID *retry_odcid)
{
if (rcidm->added_retry_odcid || rcidm->handshake_complete)
return 0;
rcidm->retry_odcid = *retry_odcid;
rcidm->added_retry_odcid = 1;
rcidm_tick(rcidm);
return 1;
}
int ossl_quic_rcidm_add_from_ncid(QUIC_RCIDM *rcidm,
const OSSL_QUIC_FRAME_NEW_CONN_ID *ncid)
{
RCID *rcid;
rcid = rcidm_create_rcid(rcidm, ncid->seq_num, &ncid->conn_id, RCID_TYPE_NCID);
if (rcid == NULL)
return 0;
rcidm_handle_retire_prior_to(rcidm, ncid->retire_prior_to);
rcidm_tick(rcidm);
return 1;
}
/*
* Queries
* =======
*/
static int rcidm_get_retire(QUIC_RCIDM *rcidm, uint64_t *seq_num, int peek)
{
RCID *rcid = ossl_list_retiring_head(&rcidm->retiring_list);
if (rcid == NULL)
return 0;
if (seq_num != NULL)
*seq_num = rcid->seq_num;
if (!peek)
rcidm_free_rcid(rcidm, rcid);
return 1;
}
int ossl_quic_rcidm_pop_retire_seq_num(QUIC_RCIDM *rcidm,
uint64_t *seq_num)
{
return rcidm_get_retire(rcidm, seq_num, /*peek=*/0);
}
int ossl_quic_rcidm_peek_retire_seq_num(QUIC_RCIDM *rcidm,
uint64_t *seq_num)
{
return rcidm_get_retire(rcidm, seq_num, /*peek=*/1);
}
int ossl_quic_rcidm_get_preferred_tx_dcid(QUIC_RCIDM *rcidm,
QUIC_CONN_ID *tx_dcid)
{
if (!rcidm->have_preferred_rcid)
return 0;
*tx_dcid = rcidm->preferred_rcid;
return 1;
}
int ossl_quic_rcidm_get_preferred_tx_dcid_changed(QUIC_RCIDM *rcidm,
int clear)
{
int r = rcidm->preferred_rcid_changed;
if (clear)
rcidm->preferred_rcid_changed = 0;
return r;
}
size_t ossl_quic_rcidm_get_num_active(const QUIC_RCIDM *rcidm)
{
return ossl_pqueue_RCID_num(rcidm->rcids)
+ (rcidm->cur_rcid != NULL ? 1 : 0)
+ ossl_quic_rcidm_get_num_retiring(rcidm);
}
size_t ossl_quic_rcidm_get_num_retiring(const QUIC_RCIDM *rcidm)
{
return rcidm->num_retiring;
}
