/*

 * 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);

quic_rcidm.c:ossl_list_retiring_head

Line

Count

Source

137

DEFINE_LIST_OF(retiring, RCID);

quic_rcidm.c:ossl_list_retiring_next

Line

Count

Source

137

DEFINE_LIST_OF(retiring, RCID);

quic_rcidm.c:ossl_list_retiring_insert_tail

Line

Count

Source

137

DEFINE_LIST_OF(retiring, RCID);

quic_rcidm.c:ossl_list_retiring_prev

Line

Count

Source

137

DEFINE_LIST_OF(retiring, RCID);

quic_rcidm.c:ossl_list_retiring_remove

Line

Count

Source

137

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 void *av, const void *bv)

{

    const RCID *a = av;

    const RCID *b = bv;

    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);

    OSSL_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;

}