/*
 * Copyright (C) Nginx, Inc.
 */


#include <ngx_config.h>
#include <ngx_core.h>
#include <ngx_event.h>
#include <ngx_event_quic_connection.h>


#define NGX_QUIC_MAX_ACK_GAP                 2

/* RFC 9002, 6.1.1. Packet Threshold: kPacketThreshold */
#define NGX_QUIC_PKT_THR                     3 /* packets */
/* RFC 9002, 6.1.2. Time Threshold: kGranularity */
#define NGX_QUIC_TIME_GRANULARITY            1 /* ms */

/* RFC 9002, 7.6.1. Duration: kPersistentCongestionThreshold */
#define NGX_QUIC_PERSISTENT_CONGESTION_THR   3


/* send time of ACK'ed packets */
typedef struct {
    ngx_msec_t                               max_pn;
    ngx_msec_t                               oldest;
    ngx_msec_t                               newest;
} ngx_quic_ack_stat_t;


static ngx_inline ngx_msec_t ngx_quic_lost_threshold(ngx_quic_connection_t *qc);
static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
    enum ssl_encryption_level_t level, ngx_msec_t send_time);
static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
    ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max,
    ngx_quic_ack_stat_t *st);
static void ngx_quic_drop_ack_ranges(ngx_connection_t *c,
    ngx_quic_send_ctx_t *ctx, uint64_t pn);
static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c,
    ngx_quic_ack_stat_t *st);
static ngx_msec_t ngx_quic_pcg_duration(ngx_connection_t *c);
static void ngx_quic_persistent_congestion(ngx_connection_t *c);
static void ngx_quic_congestion_lost(ngx_connection_t *c,
    ngx_quic_frame_t *frame);
static void ngx_quic_lost_handler(ngx_event_t *ev);


/* RFC 9002, 6.1.2. Time Threshold: kTimeThreshold, kGranularity */
static ngx_inline ngx_msec_t
ngx_quic_lost_threshold(ngx_quic_connection_t *qc)
{
    ngx_msec_t  thr;

    thr = ngx_max(qc->latest_rtt, qc->avg_rtt);
    thr += thr >> 3;

    return ngx_max(thr, NGX_QUIC_TIME_GRANULARITY);
}


ngx_int_t
ngx_quic_handle_ack_frame(ngx_connection_t *c, ngx_quic_header_t *pkt,
    ngx_quic_frame_t *f)
{
    ssize_t                 n;
    u_char                 *pos, *end;
    uint64_t                min, max, gap, range;
    ngx_uint_t              i;
    ngx_quic_ack_stat_t     send_time;
    ngx_quic_send_ctx_t    *ctx;
    ngx_quic_ack_frame_t   *ack;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);

    ctx = ngx_quic_get_send_ctx(qc, pkt->level);

    ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic ngx_quic_handle_ack_frame level:%d", pkt->level);

    ack = &f->u.ack;

    /*
     * RFC 9000, 19.3.1.  ACK Ranges
     *
     *  If any computed packet number is negative, an endpoint MUST
     *  generate a connection error of type FRAME_ENCODING_ERROR.
     */

    if (ack->first_range > ack->largest) {
        qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR;
        ngx_log_error(NGX_LOG_INFO, c->log, 0,
                      "quic invalid first range in ack frame");
        return NGX_ERROR;
    }

    min = ack->largest - ack->first_range;
    max = ack->largest;

    send_time.oldest = NGX_TIMER_INFINITE;
    send_time.newest = NGX_TIMER_INFINITE;

    if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
        != NGX_OK)
    {
        return NGX_ERROR;
    }

    /* RFC 9000, 13.2.4.  Limiting Ranges by Tracking ACK Frames */
    if (ctx->largest_ack < max || ctx->largest_ack == NGX_QUIC_UNSET_PN) {
        ctx->largest_ack = max;
        ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic updated largest received ack:%uL", max);

        /*
         * RFC 9002, 5.1.  Generating RTT Samples
         *
         *  An endpoint generates an RTT sample on receiving an
         *  ACK frame that meets the following two conditions:
         *
         *  - the largest acknowledged packet number is newly acknowledged
         *  - at least one of the newly acknowledged packets was ack-eliciting.
         */

        if (send_time.max_pn != NGX_TIMER_INFINITE) {
            ngx_quic_rtt_sample(c, ack, pkt->level, send_time.max_pn);
        }
    }

    if (f->data) {
        pos = f->data->buf->pos;
        end = f->data->buf->last;

    } else {
        pos = NULL;
        end = NULL;
    }

    for (i = 0; i < ack->range_count; i++) {

        n = ngx_quic_parse_ack_range(pkt->log, pos, end, &gap, &range);
        if (n == NGX_ERROR) {
            return NGX_ERROR;
        }
        pos += n;

        if (gap + 2 > min) {
            qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR;
            ngx_log_error(NGX_LOG_INFO, c->log, 0,
                          "quic invalid range:%ui in ack frame", i);
            return NGX_ERROR;
        }

        max = min - gap - 2;

        if (range > max) {
            qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR;
            ngx_log_error(NGX_LOG_INFO, c->log, 0,
                          "quic invalid range:%ui in ack frame", i);
            return NGX_ERROR;
        }

        min = max - range;

        if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
            != NGX_OK)
        {
            return NGX_ERROR;
        }
    }

    return ngx_quic_detect_lost(c, &send_time);
}


static void
ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
    enum ssl_encryption_level_t level, ngx_msec_t send_time)
{
    ngx_msec_t              latest_rtt, ack_delay, adjusted_rtt, rttvar_sample;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);

    latest_rtt = ngx_current_msec - send_time;
    qc->latest_rtt = latest_rtt;

    if (qc->min_rtt == NGX_TIMER_INFINITE) {
        qc->min_rtt = latest_rtt;
        qc->avg_rtt = latest_rtt;
        qc->rttvar = latest_rtt / 2;
        qc->first_rtt = ngx_current_msec;

    } else {
        qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt);

        ack_delay = (ack->delay << qc->ctp.ack_delay_exponent) / 1000;

        if (c->ssl->handshaked) {
            ack_delay = ngx_min(ack_delay, qc->ctp.max_ack_delay);
        }

        adjusted_rtt = latest_rtt;

        if (qc->min_rtt + ack_delay < latest_rtt) {
            adjusted_rtt -= ack_delay;
        }

        rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt));
        qc->rttvar += (rttvar_sample >> 2) - (qc->rttvar >> 2);
        qc->avg_rtt += (adjusted_rtt >> 3) - (qc->avg_rtt >> 3);
    }

    ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic rtt sample latest:%M min:%M avg:%M var:%M",
                   latest_rtt, qc->min_rtt, qc->avg_rtt, qc->rttvar);
}


static ngx_int_t
ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
    uint64_t min, uint64_t max, ngx_quic_ack_stat_t *st)
{
    ngx_uint_t              found;
    ngx_queue_t            *q;
    ngx_quic_frame_t       *f;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);

    if (ctx->level == ssl_encryption_application) {
        if (ngx_quic_handle_path_mtu(c, qc->path, min, max) != NGX_OK) {
            return NGX_ERROR;
        }
    }

    st->max_pn = NGX_TIMER_INFINITE;
    found = 0;

    q = ngx_queue_head(&ctx->sent);

    while (q != ngx_queue_sentinel(&ctx->sent)) {

        f = ngx_queue_data(q, ngx_quic_frame_t, queue);
        q = ngx_queue_next(q);

        if (f->pnum > max) {
            break;
        }

        if (f->pnum >= min) {
            ngx_quic_congestion_ack(c, f);

            switch (f->type) {
            case NGX_QUIC_FT_ACK:
            case NGX_QUIC_FT_ACK_ECN:
                ngx_quic_drop_ack_ranges(c, ctx, f->u.ack.largest);
                break;

            case NGX_QUIC_FT_STREAM:
            case NGX_QUIC_FT_RESET_STREAM:
                ngx_quic_handle_stream_ack(c, f);
                break;
            }

            if (f->pnum == max) {
                st->max_pn = f->send_time;
            }

            /* save earliest and latest send times of frames ack'ed */
            if (st->oldest == NGX_TIMER_INFINITE || f->send_time < st->oldest) {
                st->oldest = f->send_time;
            }

            if (st->newest == NGX_TIMER_INFINITE || f->send_time > st->newest) {
                st->newest = f->send_time;
            }

            ngx_queue_remove(&f->queue);
            ngx_quic_free_frame(c, f);
            found = 1;
        }
    }

    if (!found) {

        if (max < ctx->pnum) {
            /* duplicate ACK or ACK for non-ack-eliciting frame */
            return NGX_OK;
        }

        ngx_log_error(NGX_LOG_INFO, c->log, 0,
                      "quic ACK for the packet not sent");

        qc->error = NGX_QUIC_ERR_PROTOCOL_VIOLATION;
        qc->error_ftype = NGX_QUIC_FT_ACK;
        qc->error_reason = "unknown packet number";

        return NGX_ERROR;
    }

    if (!qc->push.timer_set) {
        ngx_post_event(&qc->push, &ngx_posted_events);
    }

    qc->pto_count = 0;

    return NGX_OK;
}


void
ngx_quic_congestion_ack(ngx_connection_t *c, ngx_quic_frame_t *f)
{
    ngx_uint_t              blocked;
    ngx_msec_t              timer;
    ngx_quic_congestion_t  *cg;
    ngx_quic_connection_t  *qc;

    if (f->plen == 0) {
        return;
    }

    qc = ngx_quic_get_connection(c);
    cg = &qc->congestion;

    blocked = (cg->in_flight >= cg->window) ? 1 : 0;

    cg->in_flight -= f->plen;

    timer = f->send_time - cg->recovery_start;

    if ((ngx_msec_int_t) timer <= 0) {
        ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic congestion ack recovery win:%uz ss:%z if:%uz",
                       cg->window, cg->ssthresh, cg->in_flight);

        goto done;
    }

    if (cg->window < cg->ssthresh) {
        cg->window += f->plen;

        ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic congestion slow start win:%uz ss:%z if:%uz",
                       cg->window, cg->ssthresh, cg->in_flight);

    } else {
        cg->window += qc->tp.max_udp_payload_size * f->plen / cg->window;

        ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic congestion avoidance win:%uz ss:%z if:%uz",
                       cg->window, cg->ssthresh, cg->in_flight);
    }

    /* prevent recovery_start from wrapping */

    timer = cg->recovery_start - ngx_current_msec + qc->tp.max_idle_timeout * 2;

    if ((ngx_msec_int_t) timer < 0) {
        cg->recovery_start = ngx_current_msec - qc->tp.max_idle_timeout * 2;
    }

done:

    if (blocked && cg->in_flight < cg->window) {
        ngx_post_event(&qc->push, &ngx_posted_events);
    }
}


static void
ngx_quic_drop_ack_ranges(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
    uint64_t pn)
{
    uint64_t               base;
    ngx_uint_t             i, smallest, largest;
    ngx_quic_ack_range_t  *r;

    ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic ngx_quic_drop_ack_ranges pn:%uL largest:%uL"
                   " fr:%uL nranges:%ui", pn, ctx->largest_range,
                   ctx->first_range, ctx->nranges);

    base = ctx->largest_range;

    if (base == NGX_QUIC_UNSET_PN) {
        return;
    }

    if (ctx->pending_ack != NGX_QUIC_UNSET_PN && pn >= ctx->pending_ack) {
        ctx->pending_ack = NGX_QUIC_UNSET_PN;
    }

    largest = base;
    smallest = largest - ctx->first_range;

    if (pn >= largest) {
        ctx->largest_range = NGX_QUIC_UNSET_PN;
        ctx->first_range = 0;
        ctx->nranges = 0;
        return;
    }

    if (pn >= smallest) {
        ctx->first_range = largest - pn - 1;
        ctx->nranges = 0;
        return;
    }

    for (i = 0; i < ctx->nranges; i++) {
        r = &ctx->ranges[i];

        largest = smallest - r->gap - 2;
        smallest = largest - r->range;

        if (pn >= largest) {
            ctx->nranges = i;
            return;
        }
        if (pn >= smallest) {
            r->range = largest - pn - 1;
            ctx->nranges = i + 1;
            return;
        }
    }
}


static ngx_int_t
ngx_quic_detect_lost(ngx_connection_t *c, ngx_quic_ack_stat_t *st)
{
    ngx_uint_t              i, nlost;
    ngx_msec_t              now, wait, thr, oldest, newest;
    ngx_queue_t            *q;
    ngx_quic_frame_t       *start;
    ngx_quic_send_ctx_t    *ctx;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);
    now = ngx_current_msec;
    thr = ngx_quic_lost_threshold(qc);

    /* send time of lost packets across all send contexts */
    oldest = NGX_TIMER_INFINITE;
    newest = NGX_TIMER_INFINITE;

    nlost = 0;

    for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) {

        ctx = &qc->send_ctx[i];

        if (ctx->largest_ack == NGX_QUIC_UNSET_PN) {
            continue;
        }

        while (!ngx_queue_empty(&ctx->sent)) {

            q = ngx_queue_head(&ctx->sent);
            start = ngx_queue_data(q, ngx_quic_frame_t, queue);

            if (start->pnum > ctx->largest_ack) {
                break;
            }

            wait = start->send_time + thr - now;

            ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
                           "quic detect_lost pnum:%uL thr:%M wait:%i level:%d",
                           start->pnum, thr, (ngx_int_t) wait, start->level);

            if ((ngx_msec_int_t) wait > 0
                && ctx->largest_ack - start->pnum < NGX_QUIC_PKT_THR)
            {
                break;
            }

            if (start->send_time > qc->first_rtt) {

                if (oldest == NGX_TIMER_INFINITE || start->send_time < oldest) {
                    oldest = start->send_time;
                }

                if (newest == NGX_TIMER_INFINITE || start->send_time > newest) {
                    newest = start->send_time;
                }

                nlost++;
            }

            ngx_quic_resend_frames(c, ctx);
        }
    }


    /* RFC 9002, 7.6.2.  Establishing Persistent Congestion */

    /*
     * Once acknowledged, packets are no longer tracked. Thus no send time
     * information is available for such packets. This limits persistent
     * congestion algorithm to packets mentioned within ACK ranges of the
     * latest ACK frame.
     */

    if (st && nlost >= 2 && (st->newest < oldest || st->oldest > newest)) {

        if (newest - oldest > ngx_quic_pcg_duration(c)) {
            ngx_quic_persistent_congestion(c);
        }
    }

    ngx_quic_set_lost_timer(c);

    return NGX_OK;
}


static ngx_msec_t
ngx_quic_pcg_duration(ngx_connection_t *c)
{
    ngx_msec_t              duration;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);

    duration = qc->avg_rtt;
    duration += ngx_max(4 * qc->rttvar, NGX_QUIC_TIME_GRANULARITY);
    duration += qc->ctp.max_ack_delay;
    duration *= NGX_QUIC_PERSISTENT_CONGESTION_THR;

    return duration;
}


static void
ngx_quic_persistent_congestion(ngx_connection_t *c)
{
    ngx_quic_congestion_t  *cg;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);
    cg = &qc->congestion;

    cg->recovery_start = ngx_current_msec;
    cg->window = qc->tp.max_udp_payload_size * 2;

    ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic persistent congestion win:%uz", cg->window);
}


void
ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
{
    uint64_t                pnum;
    ngx_queue_t            *q;
    ngx_quic_frame_t       *f, *start;
    ngx_quic_stream_t      *qs;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);
    q = ngx_queue_head(&ctx->sent);
    start = ngx_queue_data(q, ngx_quic_frame_t, queue);
    pnum = start->pnum;

    ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic resend packet pnum:%uL", start->pnum);

    ngx_quic_congestion_lost(c, start);

    do {
        f = ngx_queue_data(q, ngx_quic_frame_t, queue);

        if (f->pnum != pnum) {
            break;
        }

        q = ngx_queue_next(q);

        ngx_queue_remove(&f->queue);

        switch (f->type) {
        case NGX_QUIC_FT_ACK:
        case NGX_QUIC_FT_ACK_ECN:
            if (ctx->level == ssl_encryption_application) {
                /* force generation of most recent acknowledgment */
                ctx->send_ack = NGX_QUIC_MAX_ACK_GAP;
            }

            ngx_quic_free_frame(c, f);
            break;

        case NGX_QUIC_FT_PING:
        case NGX_QUIC_FT_PATH_CHALLENGE:
        case NGX_QUIC_FT_PATH_RESPONSE:
        case NGX_QUIC_FT_CONNECTION_CLOSE:
            ngx_quic_free_frame(c, f);
            break;

        case NGX_QUIC_FT_MAX_DATA:
            f->u.max_data.max_data = qc->streams.recv_max_data;
            ngx_quic_queue_frame(qc, f);
            break;

        case NGX_QUIC_FT_MAX_STREAMS:
        case NGX_QUIC_FT_MAX_STREAMS2:
            f->u.max_streams.limit = f->u.max_streams.bidi
                                     ? qc->streams.client_max_streams_bidi
                                     : qc->streams.client_max_streams_uni;
            ngx_quic_queue_frame(qc, f);
            break;

        case NGX_QUIC_FT_MAX_STREAM_DATA:
            qs = ngx_quic_find_stream(&qc->streams.tree,
                                      f->u.max_stream_data.id);
            if (qs == NULL) {
                ngx_quic_free_frame(c, f);
                break;
            }

            f->u.max_stream_data.limit = qs->recv_max_data;
            ngx_quic_queue_frame(qc, f);
            break;

        case NGX_QUIC_FT_STREAM:
            qs = ngx_quic_find_stream(&qc->streams.tree, f->u.stream.stream_id);

            if (qs) {
                if (qs->send_state == NGX_QUIC_STREAM_SEND_RESET_SENT
                    || qs->send_state == NGX_QUIC_STREAM_SEND_RESET_RECVD)
                {
                    ngx_quic_free_frame(c, f);
                    break;
                }
            }

            /* fall through */

        default:
            ngx_queue_insert_tail(&ctx->frames, &f->queue);
        }

    } while (q != ngx_queue_sentinel(&ctx->sent));

    if (qc->closing) {
        return;
    }

    ngx_post_event(&qc->push, &ngx_posted_events);
}


static void
ngx_quic_congestion_lost(ngx_connection_t *c, ngx_quic_frame_t *f)
{
    ngx_uint_t              blocked;
    ngx_msec_t              timer;
    ngx_quic_congestion_t  *cg;
    ngx_quic_connection_t  *qc;

    if (f->plen == 0) {
        return;
    }

    qc = ngx_quic_get_connection(c);
    cg = &qc->congestion;

    blocked = (cg->in_flight >= cg->window) ? 1 : 0;

    cg->in_flight -= f->plen;
    f->plen = 0;

    timer = f->send_time - cg->recovery_start;

    if ((ngx_msec_int_t) timer <= 0) {
        ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic congestion lost recovery win:%uz ss:%z if:%uz",
                       cg->window, cg->ssthresh, cg->in_flight);

        goto done;
    }

    cg->recovery_start = ngx_current_msec;
    cg->window /= 2;

    if (cg->window < qc->tp.max_udp_payload_size * 2) {
        cg->window = qc->tp.max_udp_payload_size * 2;
    }

    cg->ssthresh = cg->window;

    ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic congestion lost win:%uz ss:%z if:%uz",
                   cg->window, cg->ssthresh, cg->in_flight);

done:

    if (blocked && cg->in_flight < cg->window) {
        ngx_post_event(&qc->push, &ngx_posted_events);
    }
}


void
ngx_quic_set_lost_timer(ngx_connection_t *c)
{
    ngx_uint_t              i;
    ngx_msec_t              now;
    ngx_queue_t            *q;
    ngx_msec_int_t          lost, pto, w;
    ngx_quic_frame_t       *f;
    ngx_quic_send_ctx_t    *ctx;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);
    now = ngx_current_msec;

    lost = -1;
    pto = -1;

    for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) {
        ctx = &qc->send_ctx[i];

        if (ngx_queue_empty(&ctx->sent)) {
            continue;
        }

        if (ctx->largest_ack != NGX_QUIC_UNSET_PN) {
            q = ngx_queue_head(&ctx->sent);
            f = ngx_queue_data(q, ngx_quic_frame_t, queue);
            w = (ngx_msec_int_t)
                            (f->send_time + ngx_quic_lost_threshold(qc) - now);

            if (f->pnum <= ctx->largest_ack) {
                if (w < 0 || ctx->largest_ack - f->pnum >= NGX_QUIC_PKT_THR) {
                    w = 0;
                }

                if (lost == -1 || w < lost) {
                    lost = w;
                }
            }
        }

        q = ngx_queue_last(&ctx->sent);
        f = ngx_queue_data(q, ngx_quic_frame_t, queue);
        w = (ngx_msec_int_t)
                (f->send_time + (ngx_quic_pto(c, ctx) << qc->pto_count) - now);

        if (w < 0) {
            w = 0;
        }

        if (pto == -1 || w < pto) {
            pto = w;
        }
    }

    if (qc->pto.timer_set) {
        ngx_del_timer(&qc->pto);
    }

    if (lost != -1) {
        ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic lost timer lost:%M", lost);

        qc->pto.handler = ngx_quic_lost_handler;
        ngx_add_timer(&qc->pto, lost);
        return;
    }

    if (pto != -1) {
        ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic lost timer pto:%M", pto);

        qc->pto.handler = ngx_quic_pto_handler;
        ngx_add_timer(&qc->pto, pto);
        return;
    }

    ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0, "quic lost timer unset");
}


ngx_msec_t
ngx_quic_pto(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
{
    ngx_msec_t              duration;
    ngx_quic_connection_t  *qc;

    qc = ngx_quic_get_connection(c);

    /* RFC 9002, Appendix A.8.  Setting the Loss Detection Timer */

    duration = qc->avg_rtt;
    duration += ngx_max(4 * qc->rttvar, NGX_QUIC_TIME_GRANULARITY);

    if (ctx->level == ssl_encryption_application && c->ssl->handshaked) {
        duration += qc->ctp.max_ack_delay;
    }

    return duration;
}


static
void ngx_quic_lost_handler(ngx_event_t *ev)
{
    ngx_connection_t  *c;

    ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic lost timer");

    c = ev->data;

    if (ngx_quic_detect_lost(c, NULL) != NGX_OK) {
        ngx_quic_close_connection(c, NGX_ERROR);
        return;
    }

    ngx_quic_connstate_dbg(c);
}


void
ngx_quic_pto_handler(ngx_event_t *ev)
{
    ngx_uint_t              i, n;
    ngx_msec_t              now;
    ngx_queue_t            *q;
    ngx_msec_int_t          w;
    ngx_connection_t       *c;
    ngx_quic_frame_t       *f;
    ngx_quic_send_ctx_t    *ctx;
    ngx_quic_connection_t  *qc;

    ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic pto timer");

    c = ev->data;
    qc = ngx_quic_get_connection(c);
    now = ngx_current_msec;

    for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) {

        ctx = &qc->send_ctx[i];

        if (ngx_queue_empty(&ctx->sent)) {
            continue;
        }

        q = ngx_queue_last(&ctx->sent);
        f = ngx_queue_data(q, ngx_quic_frame_t, queue);
        w = (ngx_msec_int_t)
                (f->send_time + (ngx_quic_pto(c, ctx) << qc->pto_count) - now);

        if (f->pnum <= ctx->largest_ack
            && ctx->largest_ack != NGX_QUIC_UNSET_PN)
        {
            continue;
        }

        if (w > 0) {
            continue;
        }

        ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
                       "quic pto %s pto_count:%ui",
                       ngx_quic_level_name(ctx->level), qc->pto_count);

        for (n = 0; n < 2; n++) {

            f = ngx_quic_alloc_frame(c);
            if (f == NULL) {
                goto failed;
            }

            f->level = ctx->level;
            f->type = NGX_QUIC_FT_PING;
            f->ignore_congestion = 1;

            if (ngx_quic_frame_sendto(c, f, 0, qc->path) == NGX_ERROR) {
                goto failed;
            }
        }
    }

    qc->pto_count++;

    ngx_quic_set_lost_timer(c);

    ngx_quic_connstate_dbg(c);

    return;

failed:

    ngx_quic_close_connection(c, NGX_ERROR);
    return;
}


ngx_int_t
ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt)
{
    uint64_t                base, largest, smallest, gs, ge, gap, range, pn;
    uint64_t                prev_pending;
    ngx_uint_t              i, nr;
    ngx_quic_send_ctx_t    *ctx;
    ngx_quic_ack_range_t   *r;
    ngx_quic_connection_t  *qc;

    c->log->action = "preparing ack";

    qc = ngx_quic_get_connection(c);

    ctx = ngx_quic_get_send_ctx(qc, pkt->level);

    ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
                   "quic ngx_quic_ack_packet pn:%uL largest %L fr:%uL"
                   " nranges:%ui", pkt->pn, (int64_t) ctx->largest_range,
                   ctx->first_range, ctx->nranges);

    if (!ngx_quic_keys_available(qc->keys, ctx->level, 1)) {
        return NGX_OK;
    }

    prev_pending = ctx->pending_ack;

    if (pkt->need_ack) {

        ngx_post_event(&qc->push, &ngx_posted_events);

        if (ctx->send_ack == 0) {
            ctx->ack_delay_start = ngx_current_msec;
        }

        ctx->send_ack++;

        if (ctx->pending_ack == NGX_QUIC_UNSET_PN
            || ctx->pending_ack < pkt->pn)
        {
            ctx->pending_ack = pkt->pn;
        }
    }

    base = ctx->largest_range;
    pn = pkt->pn;

    if (base == NGX_QUIC_UNSET_PN) {
        ctx->largest_range = pn;
        ctx->largest_received = pkt->received;
        return NGX_OK;
    }

    if (base == pn) {
        return NGX_OK;
    }

    largest = base;
    smallest = largest - ctx->first_range;

    if (pn > base) {

        if (pn - base == 1) {
            ctx->first_range++;
            ctx->largest_range = pn;
            ctx->largest_received = pkt->received;

            return NGX_OK;

        } else {
            /* new gap in front of current largest */

            /* no place for new range, send current range as is */
            if (ctx->nranges == NGX_QUIC_MAX_RANGES) {

                if (prev_pending != NGX_QUIC_UNSET_PN) {
                    if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
                        return NGX_ERROR;
                    }
                }

                if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
                    ctx->pending_ack = NGX_QUIC_UNSET_PN;
                }
            }

            gap = pn - base - 2;
            range = ctx->first_range;

            ctx->first_range = 0;
            ctx->largest_range = pn;
            ctx->largest_received = pkt->received;

            /* packet is out of order, force send */
            if (pkt->need_ack) {
                ctx->send_ack = NGX_QUIC_MAX_ACK_GAP;
            }

            i = 0;

            goto insert;
        }
    }

    /*  pn < base, perform lookup in existing ranges */

    /* packet is out of order */
    if (pkt->need_ack) {
        ctx->send_ack = NGX_QUIC_MAX_ACK_GAP;
    }

    if (pn >= smallest && pn <= largest) {
        return NGX_OK;
    }

#if (NGX_SUPPRESS_WARN)
    r = NULL;
#endif

    for (i = 0; i < ctx->nranges; i++) {
        r = &ctx->ranges[i];

        ge = smallest - 1;
        gs = ge - r->gap;

        if (pn >= gs && pn <= ge) {

            if (gs == ge) {
                /* gap size is exactly one packet, now filled */

                /* data moves to previous range, current is removed */

                if (i == 0) {
                    ctx->first_range += r->range + 2;

                } else {
                    ctx->ranges[i - 1].range += r->range + 2;
                }

                nr = ctx->nranges - i - 1;
                if (nr) {
                    ngx_memmove(&ctx->ranges[i], &ctx->ranges[i + 1],
                                sizeof(ngx_quic_ack_range_t) * nr);
                }

                ctx->nranges--;

            } else if (pn == gs) {
                /* current gap shrinks from tail (current range grows) */
                r->gap--;
                r->range++;

            } else if (pn == ge) {
                /* current gap shrinks from head (previous range grows) */
                r->gap--;

                if (i == 0) {
                    ctx->first_range++;

                } else {
                    ctx->ranges[i - 1].range++;
                }

            } else {
                /* current gap is split into two parts */

                gap = ge - pn - 1;
                range = 0;

                if (ctx->nranges == NGX_QUIC_MAX_RANGES) {
                    if (prev_pending != NGX_QUIC_UNSET_PN) {
                        if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
                            return NGX_ERROR;
                        }
                    }

                    if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
                        ctx->pending_ack = NGX_QUIC_UNSET_PN;
                    }
                }

                r->gap = pn - gs - 1;
                goto insert;
            }

            return NGX_OK;
        }

        largest = smallest - r->gap - 2;
        smallest = largest - r->range;

        if (pn >= smallest && pn <= largest) {
            /* this packet number is already known */
            return NGX_OK;
        }

    }

    if (pn == smallest - 1) {
        /* extend first or last range */

        if (i == 0) {
            ctx->first_range++;

        } else {
            r->range++;
        }

        return NGX_OK;
    }

    /* nothing found, add new range at the tail  */

    if (ctx->nranges == NGX_QUIC_MAX_RANGES) {
        /* packet is too old to keep it */

        if (pkt->need_ack) {
            return ngx_quic_send_ack_range(c, ctx, pn, pn);
        }

        return NGX_OK;
    }

    gap = smallest - 2 - pn;
    range = 0;

insert:

    if (ctx->nranges < NGX_QUIC_MAX_RANGES) {
        ctx->nranges++;
    }

    ngx_memmove(&ctx->ranges[i + 1], &ctx->ranges[i],
                sizeof(ngx_quic_ack_range_t) * (ctx->nranges - i - 1));

    ctx->ranges[i].gap = gap;
    ctx->ranges[i].range = range;

    return NGX_OK;
}


ngx_int_t
ngx_quic_generate_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
{
    ngx_msec_t              delay;
    ngx_quic_connection_t  *qc;

    if (!ctx->send_ack) {
        return NGX_OK;
    }

    if (ctx->level == ssl_encryption_application) {

        delay = ngx_current_msec - ctx->ack_delay_start;
        qc = ngx_quic_get_connection(c);

        if (ngx_queue_empty(&ctx->frames)
            && ctx->send_ack < NGX_QUIC_MAX_ACK_GAP
            && delay < qc->tp.max_ack_delay)
        {
            if (!qc->push.timer_set && !qc->closing) {
                ngx_add_timer(&qc->push,
                              qc->tp.max_ack_delay - delay);
            }

            return NGX_OK;
        }
    }

    if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
        return NGX_ERROR;
    }

    ctx->send_ack = 0;

    return NGX_OK;
}