openssl/ssl/quic/quic_ackm.c

/*
 * Copyright 2022 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_ackm.h"
#include "internal/common.h"
#include <assert.h>

/*
 * TX Packet History
 * *****************
 *
 * The TX Packet History object tracks information about packets which have been
 * sent for which we later expect to receive an ACK. It is essentially a simple
 * database keeping a list of packet information structures in packet number
 * order which can also be looked up directly by packet number.
 *
 * We currently only allow packets to be appended to the list (i.e. the packet
 * numbers of the packets appended to the list must monotonically increase), as
 * we should not currently need more general functionality such as a sorted list
 * insert.
 */
struct tx_pkt_history_st {
    /* A linked list of all our packets. */
    OSSL_ACKM_TX_PKT *head, *tail;

    /* Number of packets in the list. */
    size_t num_packets;

    /*
     * Mapping from packet numbers (uint64_t) to (OSSL_ACKM_TX_PKT *)
     *
     * Invariant: A packet is in this map if and only if it is in the linked
     *            list.
     */
    LHASH_OF(OSSL_ACKM_TX_PKT) *map;

    /*
     * The lowest packet number which may currently be added to the history list
     * (inclusive). We do not allow packet numbers to be added to the history
     * list non-monotonically, so packet numbers must be greater than or equal
     * to this value.
     */
    uint64_t watermark;

    /*
     * Packet number of the highest packet info structure we have yet appended
     * to the list. This is usually one less than watermark, except when we have
     * not added any packet yet.
     */
    uint64_t highest_sent;
};

DEFINE_LHASH_OF_EX(OSSL_ACKM_TX_PKT);

static unsigned long tx_pkt_info_hash(const OSSL_ACKM_TX_PKT *pkt)
{
    return pkt->pkt_num;
}

static int tx_pkt_info_compare(const OSSL_ACKM_TX_PKT *a,
                               const OSSL_ACKM_TX_PKT *b)
{
    if (a->pkt_num < b->pkt_num)
        return -1;
    if (a->pkt_num > b->pkt_num)
        return 1;
    return 0;
}

static int
tx_pkt_history_init(struct tx_pkt_history_st *h)
{
    h->head = h->tail = NULL;
    h->num_packets  = 0;
    h->watermark    = 0;
    h->highest_sent = 0;

    h->map = lh_OSSL_ACKM_TX_PKT_new(tx_pkt_info_hash, tx_pkt_info_compare);
    if (h->map == NULL)
        return 0;

    return 1;
}

static void
tx_pkt_history_destroy(struct tx_pkt_history_st *h)
{
    lh_OSSL_ACKM_TX_PKT_free(h->map);
    h->map = NULL;
    h->head = h->tail = NULL;
}

static int
tx_pkt_history_add_actual(struct tx_pkt_history_st *h,
                          OSSL_ACKM_TX_PKT *pkt)
{
    OSSL_ACKM_TX_PKT *existing;

    /*
     * There should not be any existing packet with this number
     * in our mapping.
     */
    existing = lh_OSSL_ACKM_TX_PKT_retrieve(h->map, pkt);
    if (!ossl_assert(existing == NULL))
        return 0;

    /* Should not already be in a list. */
    if (!ossl_assert(pkt->next == NULL && pkt->prev == NULL))
        return 0;

    lh_OSSL_ACKM_TX_PKT_insert(h->map, pkt);

    pkt->next = NULL;
    pkt->prev = h->tail;
    if (h->tail != NULL)
        h->tail->next = pkt;
    h->tail = pkt;
    if (h->head == NULL)
        h->head = h->tail;

    ++h->num_packets;
    return 1;
}

/* Adds a packet information structure to the history list. */
static int
tx_pkt_history_add(struct tx_pkt_history_st *h,
                   OSSL_ACKM_TX_PKT *pkt)
{
    if (!ossl_assert(pkt->pkt_num >= h->watermark))
        return 0;

    if (tx_pkt_history_add_actual(h, pkt) < 1)
        return 0;

    h->watermark    = pkt->pkt_num + 1;
    h->highest_sent = pkt->pkt_num;
    return 1;
}

/* Retrieve a packet information structure by packet number. */
static OSSL_ACKM_TX_PKT *
tx_pkt_history_by_pkt_num(struct tx_pkt_history_st *h, uint64_t pkt_num)
{
    OSSL_ACKM_TX_PKT key;

    key.pkt_num = pkt_num;

    return lh_OSSL_ACKM_TX_PKT_retrieve(h->map, &key);
}

/* Remove a packet information structure from the history log. */
static int
tx_pkt_history_remove(struct tx_pkt_history_st *h, uint64_t pkt_num)
{
    OSSL_ACKM_TX_PKT key, *pkt;
    key.pkt_num = pkt_num;

    pkt = tx_pkt_history_by_pkt_num(h, pkt_num);
    if (pkt == NULL)
        return 0;

    if (pkt->prev != NULL)
        pkt->prev->next = pkt->next;
    if (pkt->next != NULL)
        pkt->next->prev = pkt->prev;
    if (h->head == pkt)
        h->head = pkt->next;
    if (h->tail == pkt)
        h->tail = pkt->prev;

    pkt->prev = pkt->next = NULL;

    lh_OSSL_ACKM_TX_PKT_delete(h->map, &key);
    --h->num_packets;
    return 1;
}

/*
 * RX Packet Number Tracking
 * *************************
 *
 * **Background.** The RX side of the ACK manager must track packets we have
 * received for which we have to generate ACK frames. Broadly, this means we
 * store a set of packet numbers which we have received but which we do not know
 * for a fact that the transmitter knows we have received.
 *
 * This must handle various situations:
 *
 *   1. We receive a packet but have not sent an ACK yet, so the transmitter
 *      does not know whether we have received it or not yet.
 *
 *   2. We receive a packet and send an ACK which is lost. We do not
 *      immediately know that the ACK was lost and the transmitter does not know
 *      that we have received the packet.
 *
 *   3. We receive a packet and send an ACK which is received by the
 *      transmitter. The transmitter does not immediately respond with an ACK,
 *      or responds with an ACK which is lost. The transmitter knows that we
 *      have received the packet, but we do not know for sure that it knows,
 *      because the ACK we sent could have been lost.
 *
 *   4. We receive a packet and send an ACK which is received by the
 *      transmitter. The transmitter subsequently sends us an ACK which confirms
 *      its receipt of the ACK we sent, and we successfully receive that ACK, so
 *      we know that the transmitter knows, that we received the original
 *      packet.
 *
 * Only when we reach case (4) are we relieved of any need to track a given
 * packet number we have received, because only in this case do we know for sure
 * that the peer knows we have received the packet. Having reached case (4) we
 * will never again need to generate an ACK containing the PN in question, but
 * until we reach that point, we must keep track of the PN as not having been
 * provably ACKed, as we may have to keep generating ACKs for the given PN not
 * just until the transmitter receives one, but until we know that it has
 * received one. This will be referred to herein as "provably ACKed".
 *
 * **Duplicate handling.** The above discusses the case where we have received a
 * packet with a given PN but are at best unsure whether the sender knows we
 * have received it or not. However, we must also handle the case where we have
 * yet to receive a packet with a given PN in the first place. The reason for
 * this is because of the requirement expressed by RFC 9000 s. 12.3:
 *
 *   "A receiver MUST discard a newly unprotected packet unless it is certain
 *    that it has not processed another packet with the same packet number from
 *    the same packet number space."
 *
 * We must ensure we never process a duplicate PN. As such, each possible PN we
 * can receive must exist in one of the following logical states:
 *
 *   - We have never processed this PN before
 *     (so if we receive such a PN, it can be processed)
 *
 *   - We have processed this PN but it has not yet been provably ACKed
 *     (and should therefore be in any future ACK frame generated;
 *      if we receive such a PN again, it must be ignored)
 *
 *   - We have processed this PN and it has been provably ACKed
 *     (if we receive such a PN again, it must be ignored)
 *
 * However, if we were to track this state for every PN ever used in the history
 * of a connection, the amount of state required would increase unboundedly as
 * the connection goes on (for example, we would have to store a set of every PN
 * ever received.)
 *
 * RFC 9000 s. 12.3 continues:
 *
 *   "Endpoints that track all individual packets for the purposes of detecting
 *    duplicates are at risk of accumulating excessive state. The data required
 *    for detecting duplicates can be limited by maintaining a minimum packet
 *    number below which all packets are immediately dropped."
 *
 * Moreover, RFC 9000 s. 13.2.3 states that:
 *
 *   "A receiver MUST retain an ACK Range unless it can ensure that it will not
 *    subsequently accept packets with numbers in that range. Maintaining a
 *    minimum packet number that increases as ranges are discarded is one way to
 *    achieve this with minimal state."
 *
 * This touches on a subtlety of the original requirement quoted above: the
 * receiver MUST discard a packet unless it is certain that it has not processed
 * another packet with the same PN. However, this does not forbid the receiver
 * from also discarding some PNs even though it has not yet processed them. In
 * other words, implementations must be conservative and err in the direction of
 * assuming a packet is a duplicate, but it is acceptable for this to come at
 * the cost of falsely identifying some packets as duplicates.
 *
 * This allows us to bound the amount of state we must keep, and we adopt the
 * suggested strategy quoted above to do so. We define a watermark PN below
 * which all PNs are in the same state. This watermark is only ever increased.
 * Thus the PNs the state for which needs to be explicitly tracked is limited to
 * only a small number of recent PNs, and all older PNs have an assumed state.
 *
 * Any given PN thus falls into one of the following states:
 *
 *   - (A) The PN is above the watermark but we have not yet received it.
 *
 *         If we receive such a PN, we should process it and record the PN as
 *         received.
 *
 *   - (B) The PN is above the watermark and we have received it.
 *
 *         The PN should be included in any future ACK frame we generate.
 *         If we receive such a PN again, we should ignore it.
 *
 *   - (C) The PN is below the watermark.
 *
 *         We do not know whether a packet with the given PN was received or
 *         not. To be safe, if we receive such a packet, it is not processed.
 *
 * Note that state (C) corresponds to both "we have processed this PN and it has
 * been provably ACKed" logical state and a subset of the PNs in the "we have
 * never processed this PN before" logical state (namely all PNs which were lost
 * and never received, but which are not recent enough to be above the
 * watermark). The reason we can merge these states and avoid tracking states
 * for the PNs in this state is because the provably ACKed and never-received
 * states are functionally identical in terms of how we need to handle them: we
 * don't need to do anything for PNs in either of these states, so we don't have
 * to care about PNs in this state nor do we have to care about distinguishing
 * the two states for a given PN.
 *
 * Note that under this scheme provably ACKed PNs are by definition always below
 * the watermark; therefore, it follows that when a PN becomes provably ACKed,
 * the watermark must be immediately increased to exceed it (otherwise we would
 * keep reporting it in future ACK frames).
 *
 * This is in line with RFC 9000 s. 13.2.4's suggested strategy on when
 * to advance the watermark:
 *
 *   "When a packet containing an ACK frame is sent, the Largest Acknowledged
 *    field in that frame can be saved. When a packet containing an ACK frame is
 *    acknowledged, the receiver can stop acknowledging packets less than or
 *    equal to the Largest Acknowledged field in the sent ACK frame."
 *
 * This is where our scheme's false positives arise. When a packet containing an
 * ACK frame is itself ACK'd, PNs referenced in that ACK frame become provably
 * acked, and the watermark is bumped accordingly. However, the Largest
 * Acknowledged field does not imply that all lower PNs have been received,
 * because there may be gaps expressed in the ranges of PNs expressed by that
 * and previous ACK frames. Thus, some unreceived PNs may be moved below the
 * watermark, and we may subsequently reject those PNs as possibly being
 * duplicates even though we have not actually received those PNs. Since we bump
 * the watermark when a PN becomes provably ACKed, it follows that an unreceived
 * PN falls below the watermark (and thus becomes a false positive for the
 * purposes of duplicate detection) when a higher-numbered PN becomes provably
 * ACKed.
 *
 * Thus, when PN n becomes provably acked, any unreceived PNs in the range [0,
 * n) will no longer be processed. Although datagrams may be reordered in the
 * network, a PN we receive can only become provably ACKed after our own
 * subsequently generated ACK frame is sent in a future TX packet, and then we
 * receive another RX PN acknowleding that TX packet. This means that a given RX
 * PN can only become provably ACKed at least 1 RTT after it is received; it is
 * unlikely that any reordered datagrams will still be "in the network" (and not
 * lost) by this time. If this does occur for whatever reason and a late PN is
 * received, the packet will be discarded unprocessed and the PN is simply
 * handled as though lost (a "written off" PN).
 *
 * **Data structure.** Our state for the RX handling side of the ACK manager, as
 * discussed above, mainly comprises:
 *
 *   a) a logical set of PNs, and
 *   b) a monotonically increasing PN counter (the watermark).
 *
 * For (a), we define a data structure which stores a logical set of PNs, which
 * we use to keep track of which PNs we have received but which have not yet
 * been provably ACKed, and thus will later need to generate an ACK frame for.
 *
 * The correspondance with the logical states discussed above is as follows. A
 * PN is in state (C) if it is below the watermark; otherwise it is in state (B)
 * if it is in the logical set of PNs, and in state (A) otherwise.
 *
 * Note that PNs are only removed from the PN set (when they become provably
 * ACKed or written off) by virtue of advancement of the watermark. Removing PNs
 * from the PN set any other way would be ambiguous as it would be
 * indistinguishable from a PN we have not yet received and risk us processing a
 * duplicate packet. In other words, for a given PN:
 *
 *   - State (A) can transition to state (B) or (C)
 *   - State (B) can transition to state (C) only
 *   - State (C) is the terminal state
 *
 * We can query the logical set data structure for PNs which have been received
 * but which have not been provably ACKed when we want to generate ACK frames.
 * Since ACK frames can be lost and/or we might not know that the peer has
 * successfully received them, we might generate multiple ACK frames covering a
 * given PN until that PN becomes provably ACKed and we finally remove it from
 * our set (by bumping the watermark) as no longer being our concern.
 *
 * The data structure supports the following operations:
 *
 *   Insert Range: Adds an inclusive range of packet numbers [start, end]
 *                 to the set. Equivalent to Insert for each number
 *                 in the range. (Used when we receive a new PN.)
 *
 *   Remove Range: Removes an inclusive range of packet numbers [start, end]
 *                 from the set. Not all of the range need already be in
 *                 the set, but any part of the range in the set is removed.
 *                 (Used when bumping the watermark.)
 *
 *   Query:        Is a PN in the data structure?
 *
 * The data structure can be iterated.
 *
 * For greater efficiency in tracking large numbers of contiguous PNs, we track
 * PN ranges rather than individual PNs. The data structure manages a list of PN
 * ranges [[start, end]...]. Internally this is implemented as a doubly linked
 * sorted list of range structures, which are automatically split and merged as
 * necessary.
 *
 * This data structure requires O(n) traversal of the list for insertion,
 * removal and query when we are not adding/removing ranges which are near the
 * beginning or end of the set of ranges. It is expected that the number of PN
 * ranges needed at any given time will generally be small and that most
 * operations will be close to the beginning or end of the range.
 *
 * Invariant: The data structure is always sorted in ascending order by PN.
 *
 * Invariant: No two adjacent ranges ever 'border' one another (have no
 *            numerical gap between them) as the data structure always ensures
 *            such ranges are merged.
 *
 * Invariant: No two ranges ever overlap.
 *
 * Invariant: No range [a, b] ever has a > b.
 *
 * Invariant: Since ranges are represented using inclusive bounds, no range
 *            item inside the data structure can represent a span of zero PNs.
 *
 * **Possible duplicates.** A PN is considered a possible duplicate when either:
 *
 *  a) its PN is already in the PN set (i.e. has already been received), or
 *  b) its PN is below the watermark (i.e. was provably ACKed or written off).
 *
 * A packet with a given PN is considered 'processable' when that PN is not
 * considered a possible duplicate (see ossl_ackm_is_rx_pn_processable).
 *
 * **TX/RX interaction.** The watermark is bumped whenever an RX packet becomes
 * provably ACKed. This occurs when an ACK frame is received by the TX side of
 * the ACK manager; thus, there is necessary interaction between the TX and RX
 * sides of the ACK manager.
 *
 * This is implemented as follows. When a packet is queued as sent in the TX
 * side of the ACK manager, it may optionally have a Largest Acked value set on
 * it. The user of the ACK manager should do this if the packet being
 * transmitted contains an ACK frame, by setting the field to the Largest Acked
 * field of that frame. Otherwise, this field should be set to QUIC_PN_INVALID.
 * When a TX packet is eventually acknowledged which has this field set, it is
 * used to update the state of the RX side of the ACK manager by bumping the
 * watermark accordingly.
 */
struct pn_set_item_st {
    struct pn_set_item_st *prev, *next;
    OSSL_QUIC_ACK_RANGE    range;
};

struct pn_set_st {
    struct pn_set_item_st *head, *tail;

    /* Number of ranges (not PNs) in the set. */
    size_t                 num_ranges;
};

static void pn_set_init(struct pn_set_st *s)
{
    s->head = s->tail = NULL;
    s->num_ranges = 0;
}

static void pn_set_destroy(struct pn_set_st *s)
{
    struct pn_set_item_st *x, *xnext;

    for (x = s->head; x != NULL; x = xnext) {
        xnext = x->next;
        OPENSSL_free(x);
    }
}

/* Possible merge of x, x->prev */
static void pn_set_merge_adjacent(struct pn_set_st *s, struct pn_set_item_st *x)
{
    struct pn_set_item_st *xprev = x->prev;

    if (xprev == NULL)
        return;

    if (x->range.start - 1 != xprev->range.end)
        return;

    x->range.start = xprev->range.start;
    x->prev = xprev->prev;
    if (x->prev != NULL)
        x->prev->next = x;

    if (s->head == xprev)
        s->head = x;

    OPENSSL_free(xprev);
    --s->num_ranges;
}

/* Returns 1 if there exists a PN x which falls within both ranges a and b. */
static int pn_range_overlaps(const OSSL_QUIC_ACK_RANGE *a,
                             const OSSL_QUIC_ACK_RANGE *b)
{
    return ossl_quic_pn_min(a->end, b->end)
        >= ossl_quic_pn_max(a->start, b->start);
}

/*
 * Insert a range into a PN set. Returns 0 on allocation failure, in which case
 * the PN set is in a valid but undefined state. Otherwise, returns 1. Ranges
 * can overlap existing ranges without limitation. If a range is a subset of
 * an existing range in the set, this is a no-op and returns 1.
 */
static int pn_set_insert(struct pn_set_st *s, const OSSL_QUIC_ACK_RANGE *range)
{
    struct pn_set_item_st *x, *z, *xnext, *f, *fnext;
    QUIC_PN start = range->start, end = range->end;

    if (!ossl_assert(start <= end))
        return 0;

    if (s->head == NULL) {
        /* Nothing in the set yet, so just add this range. */
        x = OPENSSL_zalloc(sizeof(struct pn_set_item_st));
        if (x == NULL)
            return 0;

        x->range.start = start;
        x->range.end   = end;
        s->head = s->tail = x;
        ++s->num_ranges;
        return 1;
    }

    if (start > s->tail->range.end) {
        /*
         * Range is after the latest range in the set, so append.
         *
         * Note: The case where the range is before the earliest range in the
         * set is handled as a degenerate case of the final case below. See
         * optimization note (*) below.
         */
        if (s->tail->range.end + 1 == start) {
            s->tail->range.end = end;
            return 1;
        }

        x = OPENSSL_zalloc(sizeof(struct pn_set_item_st));
        if (x == NULL)
            return 0;

        x->range.start = start;
        x->range.end   = end;
        x->prev        = s->tail;
        if (s->tail != NULL)
            s->tail->next = x;
        s->tail = x;
        ++s->num_ranges;
        return 1;
    }

    if (start <= s->head->range.start && end >= s->tail->range.end) {
        /*
         * New range dwarfs all ranges in our set.
         *
         * Free everything except the first range in the set, which we scavenge
         * and reuse.
         */
        for (x = s->head->next; x != NULL; x = xnext) {
            xnext = x->next;
            OPENSSL_free(x);
        }

        s->head->range.start = start;
        s->head->range.end   = end;
        s->head->next = s->head->prev = NULL;
        s->tail = s->head;
        s->num_ranges = 1;
        return 1;
    }

    /*
     * Walk backwards since we will most often be inserting at the end. As an
     * optimization, test the head node first and skip iterating over the
     * entire list if we are inserting at the start. The assumption is that
     * insertion at the start and end of the space will be the most common
     * operations. (*)
     */
    z = end < s->head->range.start ? s->head : s->tail;

    for (; z != NULL; z = z->prev) {
        /* An existing range dwarfs our new range (optimisation). */
        if (z->range.start <= start && z->range.end >= end)
            return 1;

        if (pn_range_overlaps(&z->range, range)) {
            /*
             * Our new range overlaps an existing range, or possibly several
             * existing ranges.
             */
            struct pn_set_item_st *ovend = z;
            OSSL_QUIC_ACK_RANGE t;
            size_t n = 0;

            t.end = ossl_quic_pn_max(end, z->range.end);

            /* Get earliest overlapping range. */
            for (; z->prev != NULL && pn_range_overlaps(&z->prev->range, range);
                   z = z->prev);

            t.start = ossl_quic_pn_min(start, z->range.start);

            /* Replace sequence of nodes z..ovend with ovend only. */
            ovend->range = t;
            ovend->prev = z->prev;
            if (z->prev != NULL)
                z->prev->next = ovend;
            if (s->head == z)
                s->head = ovend;

            /* Free now unused nodes. */
            for (f = z; f != ovend; f = fnext, ++n) {
                fnext = f->next;
                OPENSSL_free(f);
            }

            s->num_ranges -= n;
            break;
        } else if (end < z->range.start
                    && (z->prev == NULL || start > z->prev->range.end)) {
            if (z->range.start == end + 1) {
                /* We can extend the following range backwards. */
                z->range.start = start;

                /*
                 * If this closes a gap we now need to merge
                 * consecutive nodes.
                 */
                pn_set_merge_adjacent(s, z);
            } else if (z->prev != NULL && z->prev->range.end + 1 == start) {
                /* We can extend the preceding range forwards. */
                z->prev->range.end = end;

                /*
                 * If this closes a gap we now need to merge
                 * consecutive nodes.
                 */
                pn_set_merge_adjacent(s, z);
            } else {
                /*
                 * The new interval is between intervals without overlapping or
                 * touching them, so insert between, preserving sort.
                 */
                x = OPENSSL_zalloc(sizeof(struct pn_set_item_st));
                if (x == NULL)
                    return 0;

                x->range.start = start;
                x->range.end   = end;

                x->next = z;
                x->prev = z->prev;
                if (x->prev != NULL)
                    x->prev->next = x;
                z->prev = x;
                if (s->head == z)
                    s->head = x;

                ++s->num_ranges;
            }
            break;
        }
    }

    return 1;
}

/*
 * Remove a range from the set. Returns 0 on allocation failure, in which case
 * the PN set is unchanged. Otherwise, returns 1. Ranges which are not already
 * in the set can be removed without issue. If a passed range is not in the PN
 * set at all, this is a no-op and returns 1.
 */
static int pn_set_remove(struct pn_set_st *s, const OSSL_QUIC_ACK_RANGE *range)
{
    struct pn_set_item_st *z, *zprev, *y;
    QUIC_PN start = range->start, end = range->end;

    if (!ossl_assert(start <= end))
        return 0;

    /* Walk backwards since we will most often be removing at the end. */
    for (z = s->tail; z != NULL; z = zprev) {
        zprev = z->prev;

        if (start > z->range.end)
            /* No overlapping ranges can exist beyond this point, so stop. */
            break;

        if (start <= z->range.start && end >= z->range.end) {
            /*
             * The range being removed dwarfs this range, so it should be
             * removed.
             */
            if (z->next != NULL)
                z->next->prev = z->prev;
            if (z->prev != NULL)
                z->prev->next = z->next;
            if (s->head == z)
                s->head = z->next;
            if (s->tail == z)
                s->tail = z->prev;

            OPENSSL_free(z);
            --s->num_ranges;
        } else if (start <= z->range.start) {
            /*
             * The range being removed includes start of this range, but does
             * not cover the entire range (as this would be caught by the case
             * above). Shorten the range.
             */
            assert(end < z->range.end);
            z->range.start = end + 1;
        } else if (end >= z->range.end) {
            /*
             * The range being removed includes the end of this range, but does
             * not cover the entire range (as this would be caught by the case
             * above). Shorten the range. We can also stop iterating.
             */
            assert(start > z->range.start);
            assert(start > 0);
            z->range.end = start - 1;
            break;
        } else if (start > z->range.start && end < z->range.end) {
            /*
             * The range being removed falls entirely in this range, so cut it
             * into two. Cases where a zero-length range would be created are
             * handled by the above cases.
             */
            y = OPENSSL_zalloc(sizeof(struct pn_set_item_st));
            if (y == NULL)
                return 0;

            y->range.end   = z->range.end;
            y->range.start = end + 1;
            y->next = z->next;
            y->prev = z;
            if (y->next != NULL)
                y->next->prev = y;

            z->range.end = start - 1;
            z->next = y;

            if (s->tail == z)
                s->tail = y;

            ++s->num_ranges;
            break;
        } else {
            /* Assert no partial overlap; all cases should be covered above. */
            assert(!pn_range_overlaps(&z->range, range));
        }
    }

     return 1;
}

/* Returns 1 iff the given PN is in the PN set. */
static int pn_set_query(const struct pn_set_st *s, QUIC_PN pn)
{
    struct pn_set_item_st *x;

    if (s->head == NULL)
        return 0;

    for (x = s->tail; x != NULL; x = x->prev)
        if (x->range.start <= pn && x->range.end >= pn)
            return 1;
        else if (x->range.end < pn)
            return 0;

    return 0;
}

struct rx_pkt_history_st {
    struct pn_set_st set;

    /*
     * Invariant: PNs below this are not in the set.
     * Invariant: This is monotonic and only ever increases.
     */
    QUIC_PN watermark;
};

static int rx_pkt_history_bump_watermark(struct rx_pkt_history_st *h,
                                         QUIC_PN watermark);

static void rx_pkt_history_init(struct rx_pkt_history_st *h)
{
    pn_set_init(&h->set);
    h->watermark = 0;
}

static void rx_pkt_history_destroy(struct rx_pkt_history_st *h)
{
    pn_set_destroy(&h->set);
}

/*
 * Limit the number of ACK ranges we store to prevent resource consumption DoS
 * attacks.
 */
#define MAX_RX_ACK_RANGES   32

static void rx_pkt_history_trim_range_count(struct rx_pkt_history_st *h)
{
    QUIC_PN highest = QUIC_PN_INVALID;

    while (h->set.num_ranges > MAX_RX_ACK_RANGES) {
        OSSL_QUIC_ACK_RANGE r = h->set.head->range;

        highest = (highest == QUIC_PN_INVALID)
            ? r.end : ossl_quic_pn_max(highest, r.end);

        pn_set_remove(&h->set, &r);
    }

    /*
     * Bump watermark to cover all PNs we removed to avoid accidential
     * reprocessing of packets.
     */
    if (highest != QUIC_PN_INVALID)
        rx_pkt_history_bump_watermark(h, highest + 1);
}

static int rx_pkt_history_add_pn(struct rx_pkt_history_st *h,
                                 QUIC_PN pn)
{
    OSSL_QUIC_ACK_RANGE r;

    r.start = pn;
    r.end   = pn;

    if (pn < h->watermark)
        return 1; /* consider this a success case */

    if (pn_set_insert(&h->set, &r) != 1)
        return 0;

    rx_pkt_history_trim_range_count(h);
    return 1;
}

static int rx_pkt_history_bump_watermark(struct rx_pkt_history_st *h,
                                         QUIC_PN watermark)
{
    OSSL_QUIC_ACK_RANGE r;

    if (watermark <= h->watermark)
        return 1;

    /* Remove existing PNs below the watermark. */
    r.start = 0;
    r.end   = watermark - 1;
    if (pn_set_remove(&h->set, &r) != 1)
        return 0;

    h->watermark = watermark;
    return 1;
}

/*
 * ACK Manager Implementation
 * **************************
 * Implementation of the ACK manager proper.
 */

/* Constants used by the ACK manager; see RFC 9002. */
#define K_GRANULARITY           (1 * OSSL_TIME_MS)
#define K_PKT_THRESHOLD         3
#define K_TIME_THRESHOLD_NUM    9
#define K_TIME_THRESHOLD_DEN    8

/* The maximum number of times we allow PTO to be doubled. */
#define MAX_PTO_COUNT          16

struct ossl_ackm_st {
    /* Our list of transmitted packets. Corresponds to RFC 9002 sent_packets. */
    struct tx_pkt_history_st tx_history[QUIC_PN_SPACE_NUM];

    /* Our list of received PNs which are not yet provably acked. */
    struct rx_pkt_history_st rx_history[QUIC_PN_SPACE_NUM];

    /* Polymorphic dependencies that we consume. */
    OSSL_TIME             (*now)(void *arg);
    void                   *now_arg;
    OSSL_STATM             *statm;
    const OSSL_CC_METHOD   *cc_method;
    OSSL_CC_DATA           *cc_data;

    /* RFC 9002 variables. */
    uint32_t        pto_count;
    QUIC_PN         largest_acked_pkt[QUIC_PN_SPACE_NUM];
    OSSL_TIME       time_of_last_ack_eliciting_pkt[QUIC_PN_SPACE_NUM];
    OSSL_TIME       loss_time[QUIC_PN_SPACE_NUM];
    OSSL_TIME       loss_detection_deadline;

    /* Lowest PN which is still not known to be ACKed. */
    QUIC_PN         lowest_unacked_pkt[QUIC_PN_SPACE_NUM];

    /* Time at which we got our first RTT sample, or 0. */
    OSSL_TIME       first_rtt_sample;

    /*
     * A packet's num_bytes are added to this if it is inflight,
     * and removed again once ack'd/lost/discarded.
     */
    uint64_t        bytes_in_flight;

    /*
     * A packet's num_bytes are added to this if it is both inflight and
     * ack-eliciting, and removed again once ack'd/lost/discarded.
     */
    uint64_t        ack_eliciting_bytes_in_flight[QUIC_PN_SPACE_NUM];

    /* Count of ECN-CE events. */
    uint64_t        peer_ecnce[QUIC_PN_SPACE_NUM];

    /* Set to 1 when the handshake is confirmed. */
    char            handshake_confirmed;

    /* Set to 1 when the peer has completed address validation. */
    char            peer_completed_addr_validation;

    /* Set to 1 when a PN space has been discarded. */
    char            discarded[QUIC_PN_SPACE_NUM];

    /* Set to 1 when we think an ACK frame should be generated. */
    char            rx_ack_desired[QUIC_PN_SPACE_NUM];

    /* Set to 1 if an ACK frame has ever been generated. */
    char            rx_ack_generated[QUIC_PN_SPACE_NUM];

    /* Probe request counts for reporting to the user. */
    OSSL_ACKM_PROBE_INFO    pending_probe;

    /* Generated ACK frames for each PN space. */
    OSSL_QUIC_FRAME_ACK     ack[QUIC_PN_SPACE_NUM];
    OSSL_QUIC_ACK_RANGE     ack_ranges[QUIC_PN_SPACE_NUM][MAX_RX_ACK_RANGES];

    /* Other RX state. */
    /* Largest PN we have RX'd. */
    QUIC_PN         rx_largest_pn[QUIC_PN_SPACE_NUM];

    /* Time at which the PN in rx_largest_pn was RX'd. */
    OSSL_TIME       rx_largest_time[QUIC_PN_SPACE_NUM];

    /*
     * ECN event counters. Each time we receive a packet with a given ECN label,
     * the corresponding ECN counter here is incremented.
     */
    uint64_t        rx_ect0[QUIC_PN_SPACE_NUM];
    uint64_t        rx_ect1[QUIC_PN_SPACE_NUM];
    uint64_t        rx_ecnce[QUIC_PN_SPACE_NUM];

    /*
     * Number of ACK-eliciting packets since last ACK. We use this to defer
     * emitting ACK frames until a threshold number of ACK-eliciting packets
     * have been received.
     */
    uint32_t        rx_ack_eliciting_pkts_since_last_ack[QUIC_PN_SPACE_NUM];

    /*
     * The ACK frame coalescing deadline at which we should flush any unsent ACK
     * frames.
     */
    OSSL_TIME       rx_ack_flush_deadline[QUIC_PN_SPACE_NUM];

    /* Callbacks for deadline updates. */
    void (*loss_detection_deadline_cb)(OSSL_TIME deadline, void *arg);
    void *loss_detection_deadline_cb_arg;

    void (*ack_deadline_cb)(OSSL_TIME deadline, int pkt_space, void *arg);
    void *ack_deadline_cb_arg;
};

static ossl_inline uint32_t min_u32(uint32_t x, uint32_t y)
{
    return x < y ? x : y;
}

/* 
 * Get TX history for a given packet number space. Must not have been
 * discarded.
 */
static struct tx_pkt_history_st *get_tx_history(OSSL_ACKM *ackm, int pkt_space)
{
    assert(!ackm->discarded[pkt_space]);

    return &ackm->tx_history[pkt_space];
}

/*
 * Get RX history for a given packet number space. Must not have been
 * discarded.
 */
static struct rx_pkt_history_st *get_rx_history(OSSL_ACKM *ackm, int pkt_space)
{
    assert(!ackm->discarded[pkt_space]);

    return &ackm->rx_history[pkt_space];
}

/* Does the newly-acknowledged list contain any ack-eliciting packet? */
static int ack_includes_ack_eliciting(OSSL_ACKM_TX_PKT *pkt)
{
    for (; pkt != NULL; pkt = pkt->anext)
        if (pkt->is_ack_eliciting)
            return 1;

    return 0;
}

/* Return number of ACK-eliciting bytes in flight across all PN spaces. */
static uint64_t ackm_ack_eliciting_bytes_in_flight(OSSL_ACKM *ackm)
{
    int i;
    uint64_t total = 0;

    for (i = 0; i < QUIC_PN_SPACE_NUM; ++i)
        total += ackm->ack_eliciting_bytes_in_flight[i];

    return total;
}

/* Return 1 if the range contains the given PN. */
static int range_contains(const OSSL_QUIC_ACK_RANGE *range, QUIC_PN pn)
{
    return pn >= range->start && pn <= range->end;
}

/*
 * Given a logical representation of an ACK frame 'ack', create a singly-linked
 * list of the newly ACK'd frames; that is, of frames which are matched by the
 * list of PN ranges contained in the ACK frame. The packet structures in the
 * list returned are removed from the TX history list. Returns a pointer to the
 * list head (or NULL) if empty.
 */
static OSSL_ACKM_TX_PKT *ackm_detect_and_remove_newly_acked_pkts(OSSL_ACKM *ackm,
                                                                 const OSSL_QUIC_FRAME_ACK *ack,
                                                                 int pkt_space)
{
    OSSL_ACKM_TX_PKT *acked_pkts = NULL, **fixup = &acked_pkts, *pkt, *pprev;
    struct tx_pkt_history_st *h;
    size_t ridx = 0;

    assert(ack->num_ack_ranges > 0);

    /*
     * Our history list is a list of packets sorted in ascending order
     * by packet number.
     *
     * ack->ack_ranges is a list of packet number ranges in descending order.
     *
     * Walk through our history list from the end in order to efficiently detect
     * membership in the specified ack ranges. As an optimization, we use our
     * hashtable to try and skip to the first matching packet. This may fail if
     * the ACK ranges given include nonexistent packets.
     */
    h = get_tx_history(ackm, pkt_space);

    pkt = tx_pkt_history_by_pkt_num(h, ack->ack_ranges[0].end);
    if (pkt == NULL)
        pkt = h->tail;

    for (; pkt != NULL; pkt = pprev) {
        /*
         * Save prev value as it will be zeroed if we remove the packet from the
         * history list below.
         */
        pprev = pkt->prev;

        for (;; ++ridx) {
            if (ridx >= ack->num_ack_ranges) {
                /*
                 * We have exhausted all ranges so stop here, even if there are
                 * more packets to look at.
                 */
                goto stop;
            }

            if (range_contains(&ack->ack_ranges[ridx], pkt->pkt_num)) {
                /* We have matched this range. */
                tx_pkt_history_remove(h, pkt->pkt_num);

                *fixup = pkt;
                fixup = &pkt->anext;
                *fixup = NULL;
                break;
            } else if (pkt->pkt_num > ack->ack_ranges[ridx].end) {
                /*
                 * We have not reached this range yet in our list, so do not
                 * advance ridx.
                 */
                break;
            } else {
                /*
                 * We have moved beyond this range, so advance to the next range
                 * and try matching again.
                 */
                assert(pkt->pkt_num < ack->ack_ranges[ridx].start);
                continue;
            }
        }
    }
stop:

    return acked_pkts;
}

/*
 * Create a singly-linked list of newly detected-lost packets in the given
 * packet number space. Returns the head of the list or NULL if no packets were
 * detected lost. The packets in the list are removed from the TX history list.
 */
static OSSL_ACKM_TX_PKT *ackm_detect_and_remove_lost_pkts(OSSL_ACKM *ackm,
                                                          int pkt_space)
{
    OSSL_ACKM_TX_PKT *lost_pkts = NULL, **fixup = &lost_pkts, *pkt, *pnext;
    OSSL_TIME loss_delay, lost_send_time, now;
    OSSL_RTT_INFO rtt;
    struct tx_pkt_history_st *h;

    assert(ackm->largest_acked_pkt[pkt_space] != QUIC_PN_INVALID);

    ossl_statm_get_rtt_info(ackm->statm, &rtt);

    ackm->loss_time[pkt_space] = ossl_time_zero();

    loss_delay = ossl_time_multiply(ossl_time_max(rtt.latest_rtt,
                                                  rtt.smoothed_rtt),
                                    K_TIME_THRESHOLD_NUM);
    loss_delay = ossl_time_divide(loss_delay, K_TIME_THRESHOLD_DEN);

    /* Minimum time of K_GRANULARITY before packets are deemed lost. */
    loss_delay = ossl_time_max(loss_delay, ossl_ticks2time(K_GRANULARITY));

    /* Packets sent before this time are deemed lost. */
    now = ackm->now(ackm->now_arg);
    lost_send_time = ossl_time_subtract(now, loss_delay);

    h   = get_tx_history(ackm, pkt_space);
    pkt = h->head;

    for (; pkt != NULL; pkt = pnext) {
        assert(pkt_space == pkt->pkt_space);

        /*
         * Save prev value as it will be zeroed if we remove the packet from the
         * history list below.
         */
        pnext = pkt->next;

        if (pkt->pkt_num > ackm->largest_acked_pkt[pkt_space])
            continue;

        /*
         * Mark packet as lost, or set time when it should be marked.
         */
        if (ossl_time_compare(pkt->time, lost_send_time) <= 0
                || ackm->largest_acked_pkt[pkt_space]
                >= pkt->pkt_num + K_PKT_THRESHOLD) {
            tx_pkt_history_remove(h, pkt->pkt_num);

            *fixup = pkt;
            fixup = &pkt->lnext;
            *fixup = NULL;
        } else {
            if (ossl_time_is_zero(ackm->loss_time[pkt_space]))
                ackm->loss_time[pkt_space] =
                    ossl_time_add(pkt->time, loss_delay);
            else
                ackm->loss_time[pkt_space] =
                    ossl_time_min(ackm->loss_time[pkt_space],
                                  ossl_time_add(pkt->time, loss_delay));
        }
    }

    return lost_pkts;
}

static OSSL_TIME ackm_get_loss_time_and_space(OSSL_ACKM *ackm, int *pspace)
{
    OSSL_TIME time = ackm->loss_time[QUIC_PN_SPACE_INITIAL];
    int i, space = QUIC_PN_SPACE_INITIAL;

    for (i = space + 1; i < QUIC_PN_SPACE_NUM; ++i)
        if (ossl_time_is_zero(time)
            || ossl_time_compare(ackm->loss_time[i], time) == -1) {
            time    = ackm->loss_time[i];
            space   = i;
        }

    *pspace = space;
    return time;
}

static OSSL_TIME ackm_get_pto_time_and_space(OSSL_ACKM *ackm, int *space)
{
    OSSL_RTT_INFO rtt;
    OSSL_TIME duration;
    OSSL_TIME pto_timeout = ossl_time_infinite(), t;
    int pto_space = QUIC_PN_SPACE_INITIAL, i;

    ossl_statm_get_rtt_info(ackm->statm, &rtt);

    duration
        = ossl_time_add(rtt.smoothed_rtt,
                        ossl_time_max(ossl_time_multiply(rtt.rtt_variance, 4),
                                      ossl_ticks2time(K_GRANULARITY)));

    duration
        = ossl_time_multiply(duration, 1U << min_u32(ackm->pto_count,
                                                     MAX_PTO_COUNT));

    /* Anti-deadlock PTO starts from the current time. */
    if (ackm_ack_eliciting_bytes_in_flight(ackm) == 0) {
        assert(!ackm->peer_completed_addr_validation);

        *space = ackm->discarded[QUIC_PN_SPACE_INITIAL]
                    ? QUIC_PN_SPACE_HANDSHAKE
                    : QUIC_PN_SPACE_INITIAL;
        return ossl_time_add(ackm->now(ackm->now_arg), duration);
    }

    for (i = QUIC_PN_SPACE_INITIAL; i < QUIC_PN_SPACE_NUM; ++i) {
        if (ackm->ack_eliciting_bytes_in_flight[i] == 0)
            continue;

        if (i == QUIC_PN_SPACE_APP) {
            /* Skip application data until handshake confirmed. */
            if (!ackm->handshake_confirmed)
                break;

            /* Include max_ack_delay and backoff for app data. */
            if (!ossl_time_is_infinite(rtt.max_ack_delay))
                duration
                    = ossl_time_add(duration,
                                    ossl_time_multiply(rtt.max_ack_delay,
                                                       1U << min_u32(ackm->pto_count,
                                                                     MAX_PTO_COUNT)));
        }

        t = ossl_time_add(ackm->time_of_last_ack_eliciting_pkt[i], duration);
        if (ossl_time_compare(t, pto_timeout) < 0) {
            pto_timeout = t;
            pto_space   = i;
        }
    }

    *space = pto_space;
    return pto_timeout;
}

static void ackm_set_loss_detection_timer_actual(OSSL_ACKM *ackm,
                                                 OSSL_TIME deadline)
{
    ackm->loss_detection_deadline = deadline;

    if (ackm->loss_detection_deadline_cb != NULL)
        ackm->loss_detection_deadline_cb(deadline,
                                         ackm->loss_detection_deadline_cb_arg);
}

static int ackm_set_loss_detection_timer(OSSL_ACKM *ackm)
{
    int space;
    OSSL_TIME earliest_loss_time, timeout;

    earliest_loss_time = ackm_get_loss_time_and_space(ackm, &space);
    if (!ossl_time_is_zero(earliest_loss_time)) {
        /* Time threshold loss detection. */
        ackm_set_loss_detection_timer_actual(ackm, earliest_loss_time);
        return 1;
    }

    if (ackm_ack_eliciting_bytes_in_flight(ackm) == 0
            && ackm->peer_completed_addr_validation) {
        /*
         * Nothing to detect lost, so no timer is set. However, the client
         * needs to arm the timer if the server might be blocked by the
         * anti-amplification limit.
         */
        ackm_set_loss_detection_timer_actual(ackm, ossl_time_zero());
        return 1;
    }

    timeout = ackm_get_pto_time_and_space(ackm, &space);
    ackm_set_loss_detection_timer_actual(ackm, timeout);
    return 1;
}

static int ackm_in_persistent_congestion(OSSL_ACKM *ackm,
                                         const OSSL_ACKM_TX_PKT *lpkt)
{
    /* Persistent congestion not currently implemented. */
    return 0;
}

static void ackm_on_pkts_lost(OSSL_ACKM *ackm, int pkt_space,
                              const OSSL_ACKM_TX_PKT *lpkt)
{
    const OSSL_ACKM_TX_PKT *p, *pnext;
    OSSL_RTT_INFO rtt;
    QUIC_PN largest_pn_lost = 0;
    uint64_t num_bytes = 0;

    for (p = lpkt; p != NULL; p = pnext) {
        pnext = p->lnext;

        if (p->is_inflight) {
            ackm->bytes_in_flight -= p->num_bytes;
            if (p->is_ack_eliciting)
                ackm->ack_eliciting_bytes_in_flight[p->pkt_space]
                    -= p->num_bytes;

            if (p->pkt_num > largest_pn_lost)
                largest_pn_lost = p->pkt_num;

            num_bytes += p->num_bytes;
        }

        p->on_lost(p->cb_arg);
    }

    /*
     * Only consider lost packets with regards to congestion after getting an
     * RTT sample.
     */
    ossl_statm_get_rtt_info(ackm->statm, &rtt);

    if (ossl_time_is_zero(ackm->first_rtt_sample))
        return;

    ackm->cc_method->on_data_lost(ackm->cc_data,
        largest_pn_lost,
        ackm->tx_history[pkt_space].highest_sent,
        num_bytes,
        ackm_in_persistent_congestion(ackm, lpkt));
}

static void ackm_on_pkts_acked(OSSL_ACKM *ackm, const OSSL_ACKM_TX_PKT *apkt)
{
    const OSSL_ACKM_TX_PKT *anext;
    OSSL_TIME now;
    uint64_t num_retransmittable_bytes = 0;
    QUIC_PN last_pn_acked = 0;

    now = ackm->now(ackm->now_arg);

    for (; apkt != NULL; apkt = anext) {
        if (apkt->is_inflight) {
            ackm->bytes_in_flight -= apkt->num_bytes;
            if (apkt->is_ack_eliciting)
                ackm->ack_eliciting_bytes_in_flight[apkt->pkt_space]
                    -= apkt->num_bytes;

            num_retransmittable_bytes += apkt->num_bytes;
            if (apkt->pkt_num > last_pn_acked)
                last_pn_acked = apkt->pkt_num;

            if (apkt->largest_acked != QUIC_PN_INVALID)
                /*
                 * This can fail, but it is monotonic; worst case we try again
                 * next time.
                 */
                rx_pkt_history_bump_watermark(get_rx_history(ackm,
                                                             apkt->pkt_space),
                                              apkt->largest_acked + 1);
        }

        anext = apkt->anext;
        apkt->on_acked(apkt->cb_arg); /* may free apkt */
    }

    ackm->cc_method->on_data_acked(ackm->cc_data, now,
        last_pn_acked, num_retransmittable_bytes);
}

OSSL_ACKM *ossl_ackm_new(OSSL_TIME (*now)(void *arg),
                         void *now_arg,
                         OSSL_STATM *statm,
                         const OSSL_CC_METHOD *cc_method,
                         OSSL_CC_DATA *cc_data)
{
    OSSL_ACKM *ackm;
    int i;

    ackm = OPENSSL_zalloc(sizeof(OSSL_ACKM));
    if (ackm == NULL)
        return NULL;

    for (i = 0; i < (int)OSSL_NELEM(ackm->tx_history); ++i) {
        ackm->largest_acked_pkt[i] = QUIC_PN_INVALID;
        ackm->rx_ack_flush_deadline[i] = ossl_time_infinite();
        if (tx_pkt_history_init(&ackm->tx_history[i]) < 1)
            goto err;
    }

    for (i = 0; i < (int)OSSL_NELEM(ackm->rx_history); ++i)
        rx_pkt_history_init(&ackm->rx_history[i]);

    ackm->now       = now;
    ackm->now_arg   = now_arg;
    ackm->statm     = statm;
    ackm->cc_method = cc_method;
    ackm->cc_data   = cc_data;
    return ackm;

err:
    while (--i >= 0)
        tx_pkt_history_destroy(&ackm->tx_history[i]);

    OPENSSL_free(ackm);
    return NULL;
}

void ossl_ackm_free(OSSL_ACKM *ackm)
{
    size_t i;

    if (ackm == NULL)
        return;

    for (i = 0; i < OSSL_NELEM(ackm->tx_history); ++i)
        if (!ackm->discarded[i]) {
            tx_pkt_history_destroy(&ackm->tx_history[i]);
            rx_pkt_history_destroy(&ackm->rx_history[i]);
        }

    OPENSSL_free(ackm);
}

int ossl_ackm_on_tx_packet(OSSL_ACKM *ackm, OSSL_ACKM_TX_PKT *pkt)
{
    struct tx_pkt_history_st *h = get_tx_history(ackm, pkt->pkt_space);

    /* Time must be set and not move backwards. */
    if (ossl_time_is_zero(pkt->time)
        || ossl_time_compare(ackm->time_of_last_ack_eliciting_pkt[pkt->pkt_space],
                             pkt->time) > 0)
        return 0;

    /* Must have non-zero number of bytes. */
    if (pkt->num_bytes == 0)
        return 0;

    if (tx_pkt_history_add(h, pkt) == 0)
        return 0;

    if (pkt->is_inflight) {
        if (pkt->is_ack_eliciting) {
            ackm->time_of_last_ack_eliciting_pkt[pkt->pkt_space] = pkt->time;
            ackm->ack_eliciting_bytes_in_flight[pkt->pkt_space]
                += pkt->num_bytes;
        }

        ackm->bytes_in_flight += pkt->num_bytes;
        ackm_set_loss_detection_timer(ackm);

        ackm->cc_method->on_data_sent(ackm->cc_data, pkt->num_bytes);
    }

    return 1;
}

int ossl_ackm_on_rx_datagram(OSSL_ACKM *ackm, size_t num_bytes)
{
    /* No-op on the client. */
    return 1;
}

static void ackm_on_congestion(OSSL_ACKM *ackm, OSSL_TIME send_time)
{
    /* Not currently implemented. */
}

static void ackm_process_ecn(OSSL_ACKM *ackm, const OSSL_QUIC_FRAME_ACK *ack,
                             int pkt_space)
{
    struct tx_pkt_history_st *h;
    OSSL_ACKM_TX_PKT *pkt;

    /*
     * If the ECN-CE counter reported by the peer has increased, this could
     * be a new congestion event.
     */
    if (ack->ecnce > ackm->peer_ecnce[pkt_space]) {
        ackm->peer_ecnce[pkt_space] = ack->ecnce;

        h = get_tx_history(ackm, pkt_space);
        pkt = tx_pkt_history_by_pkt_num(h, ack->ack_ranges[0].end);
        if (pkt == NULL)
            return;

        ackm_on_congestion(ackm, pkt->time);
    }
}

int ossl_ackm_on_rx_ack_frame(OSSL_ACKM *ackm, const OSSL_QUIC_FRAME_ACK *ack,
                              int pkt_space, OSSL_TIME rx_time)
{
    OSSL_ACKM_TX_PKT *na_pkts, *lost_pkts;
    int must_set_timer = 0;

    if (ackm->largest_acked_pkt[pkt_space] == QUIC_PN_INVALID)
        ackm->largest_acked_pkt[pkt_space] = ack->ack_ranges[0].end;
    else
        ackm->largest_acked_pkt[pkt_space]
            = ossl_quic_pn_max(ackm->largest_acked_pkt[pkt_space],
                               ack->ack_ranges[0].end);

    /*
     * If we get an ACK in the handshake space, address validation is completed.
     * Make sure we update the timer, even if no packets were ACK'd.
     */
    if (!ackm->peer_completed_addr_validation
            && pkt_space == QUIC_PN_SPACE_HANDSHAKE) {
        ackm->peer_completed_addr_validation = 1;
        must_set_timer = 1;
    }

    /*
     * Find packets that are newly acknowledged and remove them from the list.
     */
    na_pkts = ackm_detect_and_remove_newly_acked_pkts(ackm, ack, pkt_space);
    if (na_pkts == NULL) {
        if (must_set_timer)
            ackm_set_loss_detection_timer(ackm);

        return 1;
    }

    /*
     * Update the RTT if the largest acknowledged is newly acked and at least
     * one ACK-eliciting packet was newly acked.
     *
     * First packet in the list is always the one with the largest PN.
     */
    if (na_pkts->pkt_num == ack->ack_ranges[0].end &&
        ack_includes_ack_eliciting(na_pkts)) {
        OSSL_TIME now = ackm->now(ackm->now_arg), ack_delay;
        if (ossl_time_is_zero(ackm->first_rtt_sample))
            ackm->first_rtt_sample = now;

        /* Enforce maximum ACK delay. */
        ack_delay = ack->delay_time;
        if (ackm->handshake_confirmed) {
            OSSL_RTT_INFO rtt;

            ossl_statm_get_rtt_info(ackm->statm, &rtt);
            ack_delay = ossl_time_min(ack_delay, rtt.max_ack_delay);
        }

        ossl_statm_update_rtt(ackm->statm, ack_delay,
                              ossl_time_subtract(now, na_pkts->time));
    }

    /* Process ECN information if present. */
    if (ack->ecn_present)
        ackm_process_ecn(ackm, ack, pkt_space);

    /* Handle inferred loss. */
    lost_pkts = ackm_detect_and_remove_lost_pkts(ackm, pkt_space);
    if (lost_pkts != NULL)
        ackm_on_pkts_lost(ackm, pkt_space, lost_pkts);

    ackm_on_pkts_acked(ackm, na_pkts);

    /*
     * Reset pto_count unless the client is unsure if the server validated the
     * client's address.
     */
    if (ackm->peer_completed_addr_validation)
        ackm->pto_count = 0;

    ackm_set_loss_detection_timer(ackm);
    return 1;
}

int ossl_ackm_on_pkt_space_discarded(OSSL_ACKM *ackm, int pkt_space)
{
    OSSL_ACKM_TX_PKT *pkt, *pnext;
    uint64_t num_bytes_invalidated = 0;

    assert(pkt_space < QUIC_PN_SPACE_APP);

    if (ackm->discarded[pkt_space])
        return 0;

    if (pkt_space == QUIC_PN_SPACE_HANDSHAKE)
        ackm->peer_completed_addr_validation = 1;

    for (pkt = get_tx_history(ackm, pkt_space)->head; pkt != NULL; pkt = pnext) {
        pnext = pkt->next;
        if (pkt->is_inflight) {
            ackm->bytes_in_flight -= pkt->num_bytes;
            num_bytes_invalidated += pkt->num_bytes;
        }

        pkt->on_discarded(pkt->cb_arg); /* may free pkt */
    }

    tx_pkt_history_destroy(&ackm->tx_history[pkt_space]);
    rx_pkt_history_destroy(&ackm->rx_history[pkt_space]);

    if (num_bytes_invalidated > 0)
        ackm->cc_method->on_data_invalidated(ackm->cc_data,
                                             num_bytes_invalidated);

    ackm->time_of_last_ack_eliciting_pkt[pkt_space] = ossl_time_zero();
    ackm->loss_time[pkt_space] = ossl_time_zero();
    ackm->pto_count = 0;
    ackm->discarded[pkt_space] = 1;
    ackm->ack_eliciting_bytes_in_flight[pkt_space] = 0;
    ackm_set_loss_detection_timer(ackm);
    return 1;
}

int ossl_ackm_on_handshake_confirmed(OSSL_ACKM *ackm)
{
    ackm->handshake_confirmed               = 1;
    ackm->peer_completed_addr_validation    = 1;
    ackm_set_loss_detection_timer(ackm);
    return 1;
}

static void ackm_queue_probe_handshake(OSSL_ACKM *ackm)
{
    ++ackm->pending_probe.handshake;
}

static void ackm_queue_probe_padded_initial(OSSL_ACKM *ackm)
{
    ++ackm->pending_probe.padded_initial;
}

static void ackm_queue_probe(OSSL_ACKM *ackm, int pkt_space)
{
    ++ackm->pending_probe.pto[pkt_space];
}

int ossl_ackm_on_timeout(OSSL_ACKM *ackm)
{
    int pkt_space;
    OSSL_TIME earliest_loss_time;
    OSSL_ACKM_TX_PKT *lost_pkts;

    earliest_loss_time = ackm_get_loss_time_and_space(ackm, &pkt_space);
    if (!ossl_time_is_zero(earliest_loss_time)) {
        /* Time threshold loss detection. */
        lost_pkts = ackm_detect_and_remove_lost_pkts(ackm, pkt_space);
        assert(lost_pkts != NULL);
        ackm_on_pkts_lost(ackm, pkt_space, lost_pkts);
        ackm_set_loss_detection_timer(ackm);
        return 1;
    }

    if (ackm_ack_eliciting_bytes_in_flight(ackm) == 0) {
        assert(!ackm->peer_completed_addr_validation);
        /*
         * Client sends an anti-deadlock packet: Initial is padded to earn more
         * anti-amplification credit. A handshake packet proves address
         * ownership.
         */
        if (ackm->discarded[QUIC_PN_SPACE_INITIAL])
            ackm_queue_probe_handshake(ackm);
        else
            ackm_queue_probe_padded_initial(ackm);
    } else {
        /*
         * PTO. The user of the ACKM should send new data if available, else
         * retransmit old data, or if neither is available, send a single PING
         * frame.
         */
        ackm_get_pto_time_and_space(ackm, &pkt_space);
        ackm_queue_probe(ackm, pkt_space);
    }

    ++ackm->pto_count;
    ackm_set_loss_detection_timer(ackm);
    return 1;
}

OSSL_TIME ossl_ackm_get_loss_detection_deadline(OSSL_ACKM *ackm)
{
    return ackm->loss_detection_deadline;
}

int ossl_ackm_get_probe_request(OSSL_ACKM *ackm, int clear,
                                OSSL_ACKM_PROBE_INFO *info)
{
    *info = ackm->pending_probe;

    if (clear != 0)
        memset(&ackm->pending_probe, 0, sizeof(ackm->pending_probe));

    return 1;
}

int ossl_ackm_get_largest_unacked(OSSL_ACKM *ackm, int pkt_space, QUIC_PN *pn)
{
    struct tx_pkt_history_st *h;

    h = get_tx_history(ackm, pkt_space);
    if (h->tail != NULL) {
        *pn = h->tail->pkt_num;
        return 1;
    }

    return 0;
}

/* Number of ACK-eliciting packets RX'd before we always emit an ACK. */
#define PKTS_BEFORE_ACK     2
/* Maximum amount of time to leave an ACK-eliciting packet un-ACK'd. */
#define MAX_ACK_DELAY       (OSSL_TIME_MS * 25)

/*
 * Return 1 if emission of an ACK frame is currently desired.
 *
 * This occurs when one or more of the following conditions occurs:
 *
 *   - We have flagged that we want to send an ACK frame
 *     (for example, due to the packet threshold count being exceeded), or
 *
 *   - We have exceeded the ACK flush deadline, meaning that
 *     we have received at least one ACK-eliciting packet, but held off on
 *     sending an ACK frame immediately in the hope that more ACK-eliciting
 *     packets might come in, but not enough did and we are now requesting
 *     transmission of an ACK frame anyway.
 *
 */
int ossl_ackm_is_ack_desired(OSSL_ACKM *ackm, int pkt_space)
{
    return ackm->rx_ack_desired[pkt_space]
        || (!ossl_time_is_infinite(ackm->rx_ack_flush_deadline[pkt_space])
            && ossl_time_compare(ackm->now(ackm->now_arg),
                                 ackm->rx_ack_flush_deadline[pkt_space]) >= 0);
}

/*
 * Returns 1 if an ACK frame matches a given packet number.
 */
static int ack_contains(const OSSL_QUIC_FRAME_ACK *ack, QUIC_PN pkt_num)
{
    size_t i;

    for (i = 0; i < ack->num_ack_ranges; ++i)
        if (range_contains(&ack->ack_ranges[i], pkt_num))
            return 1;

    return 0;
}

/*
 * Returns 1 iff a PN (which we have just received) was previously reported as
 * implied missing (by us, in an ACK frame we previously generated).
 */
static int ackm_is_missing(OSSL_ACKM *ackm, int pkt_space, QUIC_PN pkt_num)
{
    /*
     * A PN is implied missing if it is not greater than the highest PN in our
     * generated ACK frame, but is not matched by the frame.
     */
    return ackm->ack[pkt_space].num_ack_ranges > 0
        && pkt_num <= ackm->ack[pkt_space].ack_ranges[0].end
        && !ack_contains(&ackm->ack[pkt_space], pkt_num);
}

/*
 * Returns 1 iff our RX of a PN newly establishes the implication of missing
 * packets.
 */
static int ackm_has_newly_missing(OSSL_ACKM *ackm, int pkt_space)
{
    struct rx_pkt_history_st *h;

    h = get_rx_history(ackm, pkt_space);

    if (h->set.tail == NULL)
        return 0;

    /*
     * The second condition here establishes that the highest PN range in our RX
     * history comprises only a single PN. If there is more than one, then this
     * function will have returned 1 during a previous call to
     * ossl_ackm_on_rx_packet assuming the third condition below was met. Thus
     * we only return 1 when the missing PN condition is newly established.
     *
     * The third condition here establishes that the highest PN range in our RX
     * history is beyond (and does not border) the highest PN we have yet
     * reported in any ACK frame. Thus there is a gap of at least one PN between
     * the PNs we have ACK'd previously and the PN we have just received.
     */
    return ackm->ack[pkt_space].num_ack_ranges > 0
        && h->set.tail->range.start == h->set.tail->range.end
        && h->set.tail->range.start
            > ackm->ack[pkt_space].ack_ranges[0].end + 1;
}

static void ackm_set_flush_deadline(OSSL_ACKM *ackm, int pkt_space,
                                    OSSL_TIME deadline)
{
    ackm->rx_ack_flush_deadline[pkt_space] = deadline;

    if (ackm->ack_deadline_cb != NULL)
        ackm->ack_deadline_cb(ossl_ackm_get_ack_deadline(ackm, pkt_space),
                              pkt_space, ackm->ack_deadline_cb_arg);
}

/* Explicitly flags that we want to generate an ACK frame. */
static void ackm_queue_ack(OSSL_ACKM *ackm, int pkt_space)
{
    ackm->rx_ack_desired[pkt_space] = 1;

    /* Cancel deadline. */
    ackm_set_flush_deadline(ackm, pkt_space, ossl_time_infinite());
}

static void ackm_on_rx_ack_eliciting(OSSL_ACKM *ackm,
                                     OSSL_TIME rx_time, int pkt_space,
                                     int was_missing)
{
    if (ackm->rx_ack_desired[pkt_space])
        /* ACK generation already requested so nothing to do. */
        return;

    ++ackm->rx_ack_eliciting_pkts_since_last_ack[pkt_space];

    if (!ackm->rx_ack_generated[pkt_space]
            || was_missing
            || ackm->rx_ack_eliciting_pkts_since_last_ack[pkt_space]
                >= PKTS_BEFORE_ACK
            || ackm_has_newly_missing(ackm, pkt_space)) {
        /*
         * Either:
         *
         *   - We have never yet generated an ACK frame, meaning that this
         *     is the first ever packet received, which we should always
         *     acknowledge immediately, or
         *
         *   - We previously reported the PN that we have just received as
         *     missing in a previous ACK frame (meaning that we should report
         *     the fact that we now have it to the peer immediately), or
         *
         *   - We have exceeded the ACK-eliciting packet threshold count
         *     for the purposes of ACK coalescing, so request transmission
         *     of an ACK frame, or
         *
         *   - The PN we just received and added to our PN RX history
         *     newly implies one or more missing PNs, in which case we should
         *     inform the peer by sending an ACK frame immediately.
         *
         * We do not test the ACK flush deadline here because it is tested
         * separately in ossl_ackm_is_ack_desired.
         */
        ackm_queue_ack(ackm, pkt_space);
        return;
    }

    /*
     * Not emitting an ACK yet.
     *
     * Update the ACK flush deadline.
     */
    if (ossl_time_is_infinite(ackm->rx_ack_flush_deadline[pkt_space]))
        ackm_set_flush_deadline(ackm, pkt_space,
                                ossl_time_add(rx_time,
                                              ossl_ticks2time(MAX_ACK_DELAY)));
    else
        ackm_set_flush_deadline(ackm, pkt_space,
                                ossl_time_min(ackm->rx_ack_flush_deadline[pkt_space],
                                              ossl_time_add(rx_time,
                                                            ossl_ticks2time(MAX_ACK_DELAY))));
}

int ossl_ackm_on_rx_packet(OSSL_ACKM *ackm, const OSSL_ACKM_RX_PKT *pkt)
{
    struct rx_pkt_history_st *h = get_rx_history(ackm, pkt->pkt_space);
    int was_missing;

    if (ossl_ackm_is_rx_pn_processable(ackm, pkt->pkt_num, pkt->pkt_space) != 1)
        /* PN has already been processed or written off, no-op. */
        return 1;

    /*
     * Record the largest PN we have RX'd and the time we received it.
     * We use this to calculate the ACK delay field of ACK frames.
     */
    if (pkt->pkt_num > ackm->rx_largest_pn[pkt->pkt_space]) {
        ackm->rx_largest_pn[pkt->pkt_space]   = pkt->pkt_num;
        ackm->rx_largest_time[pkt->pkt_space] = pkt->time;
    }

    /*
     * If the PN we just received was previously implied missing by virtue of
     * being omitted from a previous ACK frame generated, we skip any packet
     * count thresholds or coalescing delays and emit a new ACK frame
     * immediately.
     */
    was_missing = ackm_is_missing(ackm, pkt->pkt_space, pkt->pkt_num);

    /*
     * Add the packet number to our history list of PNs we have not yet provably
     * acked.
     */
    if (rx_pkt_history_add_pn(h, pkt->pkt_num) != 1)
        return 0;

    /*
     * Receiving this packet may or may not cause us to emit an ACK frame.
     * We may not emit an ACK frame yet if we have not yet received a threshold
     * number of packets.
     */
    if (pkt->is_ack_eliciting)
        ackm_on_rx_ack_eliciting(ackm, pkt->time, pkt->pkt_space, was_missing);

    /* Update the ECN counters according to which ECN signal we got, if any. */
    switch (pkt->ecn) {
    case OSSL_ACKM_ECN_ECT0:
        ++ackm->rx_ect0[pkt->pkt_space];
        break;
    case OSSL_ACKM_ECN_ECT1:
        ++ackm->rx_ect1[pkt->pkt_space];
        break;
    case OSSL_ACKM_ECN_ECNCE:
        ++ackm->rx_ecnce[pkt->pkt_space];
        break;
    default:
        break;
    }

    return 1;
}

static void ackm_fill_rx_ack_ranges(OSSL_ACKM *ackm, int pkt_space,
                                    OSSL_QUIC_FRAME_ACK *ack)
{
    struct rx_pkt_history_st *h = get_rx_history(ackm, pkt_space);
    struct pn_set_item_st *x;
    size_t i = 0;

    /*
     * Copy out ranges from the PN set, starting at the end, until we reach our
     * maximum number of ranges.
     */
    for (x = h->set.tail;
         x != NULL && i < OSSL_NELEM(ackm->ack_ranges);
         x = x->prev, ++i)
        ackm->ack_ranges[pkt_space][i] = x->range;

    ack->ack_ranges     = ackm->ack_ranges[pkt_space];
    ack->num_ack_ranges = i;
}

const OSSL_QUIC_FRAME_ACK *ossl_ackm_get_ack_frame(OSSL_ACKM *ackm,
                                                   int pkt_space)
{
    OSSL_QUIC_FRAME_ACK *ack = &ackm->ack[pkt_space];
    OSSL_TIME now = ackm->now(ackm->now_arg);

    ackm_fill_rx_ack_ranges(ackm, pkt_space, ack);

    if (!ossl_time_is_zero(ackm->rx_largest_time[pkt_space])
            && ossl_time_compare(now, ackm->rx_largest_time[pkt_space]) > 0
            && pkt_space == QUIC_PN_SPACE_APP)
        ack->delay_time =
            ossl_time_subtract(now, ackm->rx_largest_time[pkt_space]);
    else
        ack->delay_time = ossl_time_zero();

    ack->ect0              = ackm->rx_ect0[pkt_space];
    ack->ect1              = ackm->rx_ect1[pkt_space];
    ack->ecnce             = ackm->rx_ecnce[pkt_space];
    ack->ecn_present       = 1;

    ackm->rx_ack_eliciting_pkts_since_last_ack[pkt_space] = 0;

    ackm->rx_ack_generated[pkt_space]       = 1;
    ackm->rx_ack_desired[pkt_space]         = 0;
    ackm_set_flush_deadline(ackm, pkt_space, ossl_time_infinite());
    return ack;
}


OSSL_TIME ossl_ackm_get_ack_deadline(OSSL_ACKM *ackm, int pkt_space)
{
    if (ackm->rx_ack_desired[pkt_space])
        /* Already desired, deadline is now. */
        return ossl_time_zero();

    return ackm->rx_ack_flush_deadline[pkt_space];
}

int ossl_ackm_is_rx_pn_processable(OSSL_ACKM *ackm, QUIC_PN pn, int pkt_space)
{
    struct rx_pkt_history_st *h = get_rx_history(ackm, pkt_space);

    return pn >= h->watermark && pn_set_query(&h->set, pn) == 0;
}

void ossl_ackm_set_loss_detection_deadline_callback(OSSL_ACKM *ackm,
                                                    void (*fn)(OSSL_TIME deadline,
                                                               void *arg),
                                                    void *arg)
{
    ackm->loss_detection_deadline_cb      = fn;
    ackm->loss_detection_deadline_cb_arg  = arg;
}

void ossl_ackm_set_ack_deadline_callback(OSSL_ACKM *ackm,
                                         void (*fn)(OSSL_TIME deadline,
                                                    int pkt_space,
                                                    void *arg),
                                         void *arg)
{
    ackm->ack_deadline_cb     = fn;
    ackm->ack_deadline_cb_arg = arg;
}