diff src/event/quic/ngx_event_quic_ack.c @ 8751:bc910a5ec737 quic

QUIC: separate files for output and ack related processing.
author Vladimir Homutov <vl@nginx.com>
date Tue, 13 Apr 2021 14:41:20 +0300
parents
children 915c2f7092ed
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/src/event/quic/ngx_event_quic_ack.c
@@ -0,0 +1,1081 @@
+
+/*
+ * 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
+
+/* quic-recovery, section 6.1.1, Packet Threshold */
+#define NGX_QUIC_PKT_THR                     3 /* packets */
+/* quic-recovery, section 6.1.2, Time Threshold */
+#define NGX_QUIC_TIME_THR                    1.125
+#define NGX_QUIC_TIME_GRANULARITY            1 /* ms */
+
+#define ngx_quic_lost_threshold(qc)                                           \
+    ngx_max(NGX_QUIC_TIME_THR * ngx_max((qc)->latest_rtt, (qc)->avg_rtt),     \
+            NGX_QUIC_TIME_GRANULARITY)
+
+
+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_msec_t *send_time);
+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);
+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);
+
+
+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_msec_t              send_time;
+    ngx_uint_t              i;
+    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;
+
+    /*
+     *  If any computed packet number is negative, an endpoint MUST
+     *  generate a connection error of type FRAME_ENCODING_ERROR.
+     *  (19.3.1)
+     */
+
+    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;
+
+    if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
+        != NGX_OK)
+    {
+        return NGX_ERROR;
+    }
+
+    /* 13.2.3.  Receiver Tracking of 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);
+
+        /*
+         *  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 != NGX_TIMER_INFINITE) {
+            ngx_quic_rtt_sample(c, ack, pkt->level, send_time);
+        }
+    }
+
+    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);
+}
+
+
+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;
+
+    } else {
+        qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt);
+
+        ack_delay = ack->delay * (1 << 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;
+        }
+
+        qc->avg_rtt = 0.875 * qc->avg_rtt + 0.125 * adjusted_rtt;
+        rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt));
+        qc->rttvar = 0.75 * qc->rttvar + 0.25 * rttvar_sample;
+    }
+
+    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_msec_t *send_time)
+{
+    ngx_uint_t              found;
+    ngx_queue_t            *q;
+    ngx_quic_frame_t       *f;
+    ngx_quic_connection_t  *qc;
+
+    qc = ngx_quic_get_connection(c);
+
+    *send_time = NGX_TIMER_INFINITE;
+    found = 0;
+
+    q = ngx_queue_last(&ctx->sent);
+
+    while (q != ngx_queue_sentinel(&ctx->sent)) {
+
+        f = ngx_queue_data(q, ngx_quic_frame_t, queue);
+        q = ngx_queue_prev(q);
+
+        if (f->pnum >= min && f->pnum <= max) {
+            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_STREAM0:
+            case NGX_QUIC_FT_STREAM1:
+            case NGX_QUIC_FT_STREAM2:
+            case NGX_QUIC_FT_STREAM3:
+            case NGX_QUIC_FT_STREAM4:
+            case NGX_QUIC_FT_STREAM5:
+            case NGX_QUIC_FT_STREAM6:
+            case NGX_QUIC_FT_STREAM7:
+                ngx_quic_handle_stream_ack(c, f);
+                break;
+            }
+
+            if (f->pnum == max) {
+                *send_time = f->last;
+            }
+
+            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_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;
+
+    cg->in_flight -= f->plen;
+
+    timer = f->last - 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);
+
+        return;
+    }
+
+    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;
+    }
+}
+
+
+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_uint_t              i;
+    ngx_msec_t              now, wait, thr;
+    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);
+
+    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->last + 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;
+            }
+
+            ngx_quic_resend_frames(c, ctx);
+        }
+    }
+
+    ngx_quic_set_lost_timer(c);
+
+    return NGX_OK;
+}
+
+
+void
+ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
+{
+    size_t                  n;
+    ngx_buf_t              *b;
+    ngx_queue_t            *q;
+    ngx_quic_frame_t       *f, *start;
+    ngx_quic_stream_t      *sn;
+    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);
+
+    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 != start->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_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:
+            sn = ngx_quic_find_stream(&qc->streams.tree,
+                                      f->u.max_stream_data.id);
+            if (sn == NULL) {
+                ngx_quic_free_frame(c, f);
+                break;
+            }
+
+            b = sn->b;
+            n = sn->fs.received + (b->pos - b->start) + (b->end - b->last);
+
+            if (f->u.max_stream_data.limit < n) {
+                f->u.max_stream_data.limit = n;
+            }
+
+            ngx_quic_queue_frame(qc, f);
+            break;
+
+        case NGX_QUIC_FT_STREAM0:
+        case NGX_QUIC_FT_STREAM1:
+        case NGX_QUIC_FT_STREAM2:
+        case NGX_QUIC_FT_STREAM3:
+        case NGX_QUIC_FT_STREAM4:
+        case NGX_QUIC_FT_STREAM5:
+        case NGX_QUIC_FT_STREAM6:
+        case NGX_QUIC_FT_STREAM7:
+            sn = ngx_quic_find_stream(&qc->streams.tree, f->u.stream.stream_id);
+
+            if (sn && sn->c->write->error) {
+                /* RESET_STREAM was sent */
+                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_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;
+
+    cg->in_flight -= f->plen;
+    f->plen = 0;
+
+    timer = f->last - 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);
+
+        return;
+    }
+
+    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);
+}
+
+
+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->last + 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->last + ngx_quic_pto(c, ctx) - 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);
+
+    /* PTO calculation: quic-recovery, Appendix 8 */
+    duration = qc->avg_rtt;
+
+    duration += ngx_max(4 * qc->rttvar, NGX_QUIC_TIME_GRANULARITY);
+    duration <<= qc->pto_count;
+
+    if (qc->congestion.in_flight == 0) { /* no in-flight packets */
+        return duration;
+    }
+
+    if (ctx->level == ssl_encryption_application && c->ssl->handshaked) {
+        duration += qc->ctp.max_ack_delay << qc->pto_count;
+    }
+
+    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) != NGX_OK) {
+        ngx_quic_close_connection(c, NGX_ERROR);
+    }
+
+    ngx_quic_connstate_dbg(c);
+}
+
+
+void
+ngx_quic_pto_handler(ngx_event_t *ev)
+{
+    ngx_uint_t              i;
+    ngx_msec_t              now;
+    ngx_queue_t            *q, *next;
+    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_head(&ctx->sent);
+        f = ngx_queue_data(q, ngx_quic_frame_t, queue);
+
+        if (f->pnum <= ctx->largest_ack
+            && ctx->largest_ack != NGX_QUIC_UNSET_PN)
+        {
+            continue;
+        }
+
+        if ((ngx_msec_int_t) (f->last + ngx_quic_pto(c, ctx) - now) > 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 (q = ngx_queue_head(&ctx->frames);
+             q != ngx_queue_sentinel(&ctx->frames);
+             /* void */)
+        {
+            next = ngx_queue_next(q);
+            f = ngx_queue_data(q, ngx_quic_frame_t, queue);
+
+            if (f->type == NGX_QUIC_FT_PING) {
+                ngx_queue_remove(q);
+                ngx_quic_free_frame(c, f);
+            }
+
+            q = next;
+        }
+
+        for (q = ngx_queue_head(&ctx->sent);
+             q != ngx_queue_sentinel(&ctx->sent);
+             /* void */)
+        {
+            next = ngx_queue_next(q);
+            f = ngx_queue_data(q, ngx_quic_frame_t, queue);
+
+            if (f->type == NGX_QUIC_FT_PING) {
+                ngx_quic_congestion_lost(c, f);
+                ngx_queue_remove(q);
+                ngx_quic_free_frame(c, f);
+            }
+
+            q = next;
+        }
+
+        /* enforce 2 udp datagrams */
+
+        f = ngx_quic_alloc_frame(c);
+        if (f == NULL) {
+            break;
+        }
+
+        f->level = ctx->level;
+        f->type = NGX_QUIC_FT_PING;
+        f->flush = 1;
+
+        ngx_quic_queue_frame(qc, f);
+
+        f = ngx_quic_alloc_frame(c);
+        if (f == NULL) {
+            break;
+        }
+
+        f->level = ctx->level;
+        f->type = NGX_QUIC_FT_PING;
+
+        ngx_quic_queue_frame(qc, f);
+    }
+
+    qc->pto_count++;
+
+    ngx_quic_connstate_dbg(c);
+}
+
+
+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);
+
+    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 (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;
+}