One Level Up Top Level

src/event/quic/ngx_event_quic_ack.c - nginx

Data types defined

Functions defined

Macros defined

Source code


  2. /*
  3. * Copyright (C) Nginx, Inc.
  4. */


  7. #include <ngx_config.h>
  8. #include <ngx_core.h>
  9. #include <ngx_event.h>
  10. #include <ngx_event_quic_connection.h>


  13. ‌#define NGX_QUIC_MAX_ACK_GAP                 2

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

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

  23. /* CUBIC parameters x10 */
  24. ‌#define NGX_QUIC_CUBIC_BETA                  7
  25. ‌#define NGX_QUIC_CUBIC_C                     4


  28. /* send time of ACK'ed packets */
  29. ‌typedef struct {
  30.     ngx_msec_t                               max_pn;
  31.     ngx_msec_t                               oldest;
  32.     ngx_msec_t                               newest;
  33. ‌} ngx_quic_ack_stat_t;


  36. static ngx_inline ngx_msec_t ngx_quic_time_threshold(ngx_quic_connection_t *qc);
  37. static uint64_t ngx_quic_packet_threshold(ngx_quic_send_ctx_t *ctx);
  38. static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
  39.     ngx_uint_t level, ngx_msec_t send_time);
  40. static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
  41.     ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max,
  42.     ngx_quic_ack_stat_t *st);
  43. static size_t ngx_quic_congestion_cubic(ngx_connection_t *c);
  44. static void ngx_quic_drop_ack_ranges(ngx_connection_t *c,
  45.     ngx_quic_send_ctx_t *ctx, uint64_t pn);
  46. static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c,
  47.     ngx_quic_ack_stat_t *st);
  48. static ngx_msec_t ngx_quic_congestion_cubic_time(ngx_connection_t *c);
  49. static ngx_msec_t ngx_quic_pcg_duration(ngx_connection_t *c);
  50. static void ngx_quic_persistent_congestion(ngx_connection_t *c);
  51. static ngx_msec_t ngx_quic_oldest_sent_packet(ngx_connection_t *c);
  52. static void ngx_quic_congestion_lost(ngx_connection_t *c,
  53.     ngx_quic_frame_t *frame);
  54. static void ngx_quic_lost_handler(ngx_event_t *ev);


  57. /* RFC 9002, 6.1.2. Time Threshold: kTimeThreshold, kGranularity */
  58. static ngx_inline ngx_msec_t
  59. ‌ngx_quic_time_threshold(ngx_quic_connection_t *qc)
  60. {
  61.     ngx_msec_t  thr;

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

  66.     return ngx_max(thr, NGX_QUIC_TIME_GRANULARITY);
  67. }


  70. static uint64_t
  71. ‌ngx_quic_packet_threshold(ngx_quic_send_ctx_t *ctx)
  72. {
  73.     uint64_t           pkt_thr;
  74.     ngx_queue_t       *q;
  75.     ngx_quic_frame_t  *f;

  77.     if (ngx_queue_empty(&ctx->sent)) {
  78.         return NGX_QUIC_PKT_THR;
  79.     }

  81.     q = ngx_queue_head(&ctx->sent);
  82.     f = ngx_queue_data(q, ngx_quic_frame_t, queue);
  83.     pkt_thr = (ctx->pnum - f->pnum) / 2;

  85.     if (pkt_thr <= NGX_QUIC_PKT_THR) {
  86.         return NGX_QUIC_PKT_THR;
  87.     }

  89.     return pkt_thr;
  90. }


  93. ngx_int_t
  94. ‌ngx_quic_handle_ack_frame(ngx_connection_t *c, ngx_quic_header_t *pkt,
  95.     ngx_quic_frame_t *f)
  96. {
  97.     ssize_t                 n;
  98.     u_char                 *pos, *end;
  99.     uint64_t                min, max, gap, range;
  100.     ngx_uint_t              i;
  101.     ngx_quic_ack_stat_t     send_time;
  102.     ngx_quic_send_ctx_t    *ctx;
  103.     ngx_quic_ack_frame_t   *ack;
  104.     ngx_quic_connection_t  *qc;

  106.     qc = ngx_quic_get_connection(c);

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

  110.     ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
  111.                    "quic ngx_quic_handle_ack_frame level:%ui", pkt->level);

  113.     ack = &f->u.ack;

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

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

  129.     min = ack->largest - ack->first_range;
  130.     max = ack->largest;

  132.     send_time.oldest = NGX_TIMER_INFINITE;
  133.     send_time.newest = NGX_TIMER_INFINITE;

  135.     if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
  136.         != NGX_OK)
  137.     {
  138.         return NGX_ERROR;
  139.     }

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

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

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

  162.     if (f->data) {
  163.         pos = f->data->buf->pos;
  164.         end = f->data->buf->last;

  166.     } else {
  167.         pos = NULL;
  168.         end = NULL;
  169.     }

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

  173.         n = ngx_quic_parse_ack_range(pkt->log, pos, end, &gap, &range);
  174.         if (n == NGX_ERROR) {
  175.             return NGX_ERROR;
  176.         }
  177.         pos += n;

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

  186.         max = min - gap - 2;

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

  195.         min = max - range;

  197.         if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
  198.             != NGX_OK)
  199.         {
  200.             return NGX_ERROR;
  201.         }
  202.     }

  204.     return ngx_quic_detect_lost(c, &send_time);
  205. }


  208. static void
  209. ‌ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
  210.     ngx_uint_t level, ngx_msec_t send_time)
  211. {
  212.     ngx_msec_t              latest_rtt, ack_delay, adjusted_rtt, rttvar_sample;
  213.     ngx_quic_connection_t  *qc;

  215.     qc = ngx_quic_get_connection(c);

  217.     latest_rtt = ngx_current_msec - send_time;
  218.     qc->latest_rtt = latest_rtt;

  220.     if (qc->min_rtt == NGX_TIMER_INFINITE) {
  221.         qc->min_rtt = latest_rtt;
  222.         qc->avg_rtt = latest_rtt;
  223.         qc->rttvar = latest_rtt / 2;
  224.         qc->first_rtt = ngx_current_msec;

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

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

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

  235.         adjusted_rtt = latest_rtt;

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

  241.         rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt));
  242.         qc->rttvar += (rttvar_sample >> 2) - (qc->rttvar >> 2);
  243.         qc->avg_rtt += (adjusted_rtt >> 3) - (qc->avg_rtt >> 3);
  244.     }

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


  252. static ngx_int_t
  253. ‌ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
  254.     uint64_t min, uint64_t max, ngx_quic_ack_stat_t *st)
  255. {
  256.     ngx_uint_t              found;
  257.     ngx_queue_t            *q;
  258.     ngx_quic_frame_t       *f;
  259.     ngx_quic_connection_t  *qc;

  261.     qc = ngx_quic_get_connection(c);

  263.     if (ctx->level == NGX_QUIC_ENCRYPTION_APPLICATION) {
  264.         if (ngx_quic_handle_path_mtu(c, qc->path, min, max) != NGX_OK) {
  265.             return NGX_ERROR;
  266.         }
  267.     }

  269.     st->max_pn = NGX_TIMER_INFINITE;
  270.     found = 0;

  272.     q = ngx_queue_head(&ctx->sent);

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

  276.         f = ngx_queue_data(q, ngx_quic_frame_t, queue);
  277.         q = ngx_queue_next(q);

  279.         if (f->pnum > max) {
  280.             break;
  281.         }

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

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

  292.             case NGX_QUIC_FT_STREAM:
  293.             case NGX_QUIC_FT_RESET_STREAM:
  294.                 ngx_quic_handle_stream_ack(c, f);
  295.                 break;
  296.             }

  298.             if (f->pnum == max) {
  299.                 st->max_pn = f->send_time;
  300.             }

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

  307.             if (st->newest == NGX_TIMER_INFINITE || f->send_time > st->newest) {
  308.                 st->newest = f->send_time;
  309.             }

  311.             ngx_queue_remove(&f->queue);
  312.             ngx_quic_free_frame(c, f);
  313.             found = 1;
  314.         }
  315.     }

  317.     if (!found) {

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

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

  327.         qc->error = NGX_QUIC_ERR_PROTOCOL_VIOLATION;
  328.         qc->error_ftype = NGX_QUIC_FT_ACK;
  329.         qc->error_reason = "unknown packet number";

  331.         return NGX_ERROR;
  332.     }

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

  338.     qc->pto_count = 0;

  340.     return NGX_OK;
  341. }


  344. void
  345. ‌ngx_quic_congestion_ack(ngx_connection_t *c, ngx_quic_frame_t *f)
  346. {
  347.     size_t                  w_cubic;
  348.     ngx_uint_t              blocked;
  349.     ngx_msec_t              now, timer;
  350.     ngx_quic_congestion_t  *cg;
  351.     ngx_quic_connection_t  *qc;

  353.     if (f->plen == 0) {
  354.         return;
  355.     }

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

  360.     if (f->pnum < qc->rst_pnum) {
  361.         return;
  362.     }

  364.     now = ngx_current_msec;

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

  368.     cg->in_flight -= f->plen;

  370.     /* prevent recovery_start from wrapping */

  372.     timer = now - cg->recovery_start;

  374.     if ((ngx_msec_int_t) timer < 0) {
  375.         cg->recovery_start = ngx_quic_oldest_sent_packet(c) - 1;
  376.     }

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

  380.     if ((ngx_msec_int_t) timer <= 0) {
  381.         ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  382.                        "quic congestion ack rec t:%M win:%uz if:%uz",
  383.                        now, cg->window, cg->in_flight);

  385.         goto done;
  386.     }

  388.     if (cg->idle) {
  389.         ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  390.                        "quic congestion ack idle t:%M win:%uz if:%uz",
  391.                        now, cg->window, cg->in_flight);

  393.         goto done;
  394.     }

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

  399.         ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
  400.                        "quic congestion ack ss t:%M win:%uz ss:%z if:%uz",
  401.                        now, cg->window, cg->ssthresh, cg->in_flight);

  403.     } else {

  405.         /* RFC 9438, 4.2. Window Increase Function */

  407.         w_cubic = ngx_quic_congestion_cubic(c);

  409.         if (cg->window < cg->w_prior) {
  410.             cg->w_est += (uint64_t) cg->mtu * f->plen
  411.                          * 3 * (10 - NGX_QUIC_CUBIC_BETA)
  412.                          / (10 + NGX_QUIC_CUBIC_BETA) / cg->window;

  414.         } else {
  415.             cg->w_est += (uint64_t) cg->mtu * f->plen / cg->window;
  416.         }

  418.         if (w_cubic < cg->w_est) {
  419.             cg->window = cg->w_est;

  421.             ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
  422.                        "quic congestion ack reno t:%M win:%uz c:%uz if:%uz",
  423.                        now, cg->window, w_cubic, cg->in_flight);

  425.         } else if (w_cubic > cg->window) {

  427.             if (w_cubic >= cg->window * 3 / 2) {
  428.                 cg->window += cg->mtu / 2;

  430.             } else {
  431.                 cg->window += (uint64_t) cg->mtu * (w_cubic - cg->window)
  432.                               / cg->window;
  433.             }

  435.             ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
  436.                           "quic congestion ack cubic t:%M win:%uz c:%uz if:%uz",
  437.                           now, cg->window, w_cubic, cg->in_flight);

  439.         } else {
  440.             ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
  441.                            "quic congestion ack skip t:%M win:%uz c:%uz if:%uz",
  442.                            now, cg->window, w_cubic, cg->in_flight);
  443.         }
  444.     }

  446. done:

  448.     if (blocked && cg->in_flight < cg->window) {
  449.         ngx_post_event(&qc->push, &ngx_posted_events);
  450.     }
  451. }


  454. static size_t
  455. ‌ngx_quic_congestion_cubic(ngx_connection_t *c)
  456. {
  457.     int64_t                 w, t, cc;
  458.     ngx_msec_t              now;
  459.     ngx_quic_congestion_t  *cg;
  460.     ngx_quic_connection_t  *qc;

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

  465.     ngx_quic_congestion_idle(c, cg->idle);

  467.     now = ngx_current_msec;
  468.     t = (ngx_msec_int_t) (now - cg->k);

  470.     if (t > 1000000) {
  471.         w = NGX_MAX_SIZE_T_VALUE;
  472.         goto done;
  473.     }

  475.     if (t < -1000000) {
  476.         w = 0;
  477.         goto done;
  478.     }

  480.     /*
  481.      * RFC 9438, Figure 1
  482.      *
  483.      *   w_cubic = C * (t_msec / 1000) ^ 3 * mtu + w_max
  484.      */

  486.     cc = 10000000000ll / (int64_t) cg->mtu / NGX_QUIC_CUBIC_C;
  487.     w = t * t * t / cc + (int64_t) cg->w_max;

  489.     if (w > NGX_MAX_SIZE_T_VALUE) {
  490.         w = NGX_MAX_SIZE_T_VALUE;
  491.     }

  493.     if (w < 0) {
  494.         w = 0;
  495.     }

  497. done:

  499.     ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  500.                    "quic cubic t:%L w:%L wm:%uz", t, w, cg->w_max);

  502.     return w;
  503. }


  506. void
  507. ‌ngx_quic_congestion_idle(ngx_connection_t *c, ngx_uint_t idle)
  508. {
  509.     ngx_msec_t              now;
  510.     ngx_quic_congestion_t  *cg;
  511.     ngx_quic_connection_t  *qc;

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

  516.     ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
  517.                    "quic congestion idle:%ui", idle);

  519.     if (cg->window >= cg->ssthresh) {
  520.         /* RFC 9438, 5.8. Behavior for Application-Limited Flows */

  522.         now = ngx_current_msec;

  524.         if (cg->idle) {
  525.             cg->k += now - cg->idle_start;
  526.         }

  528.         cg->idle_start = now;
  529.     }

  531.     cg->idle = idle;
  532. }


  535. static void
  536. ‌ngx_quic_drop_ack_ranges(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
  537.     uint64_t pn)
  538. {
  539.     uint64_t               base;
  540.     ngx_uint_t             i, smallest, largest;
  541.     ngx_quic_ack_range_t  *r;

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

  548.     base = ctx->largest_range;

  550.     if (base == NGX_QUIC_UNSET_PN) {
  551.         return;
  552.     }

  554.     if (ctx->pending_ack != NGX_QUIC_UNSET_PN && pn >= ctx->pending_ack) {
  555.         ctx->pending_ack = NGX_QUIC_UNSET_PN;
  556.     }

  558.     largest = base;
  559.     smallest = largest - ctx->first_range;

  561.     if (pn >= largest) {
  562.         ctx->largest_range = NGX_QUIC_UNSET_PN;
  563.         ctx->first_range = 0;
  564.         ctx->nranges = 0;
  565.         return;
  566.     }

  568.     if (pn >= smallest) {
  569.         ctx->first_range = largest - pn - 1;
  570.         ctx->nranges = 0;
  571.         return;
  572.     }

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

  577.         largest = smallest - r->gap - 2;
  578.         smallest = largest - r->range;

  580.         if (pn >= largest) {
  581.             ctx->nranges = i;
  582.             return;
  583.         }
  584.         if (pn >= smallest) {
  585.             r->range = largest - pn - 1;
  586.             ctx->nranges = i + 1;
  587.             return;
  588.         }
  589.     }
  590. }


  593. static ngx_int_t
  594. ‌ngx_quic_detect_lost(ngx_connection_t *c, ngx_quic_ack_stat_t *st)
  595. {
  596.     uint64_t                pkt_thr;
  597.     ngx_uint_t              i, nlost;
  598.     ngx_msec_t              now, wait, thr, oldest, newest;
  599.     ngx_queue_t            *q;
  600.     ngx_quic_frame_t       *start;
  601.     ngx_quic_send_ctx_t    *ctx;
  602.     ngx_quic_connection_t  *qc;

  604.     qc = ngx_quic_get_connection(c);
  605.     now = ngx_current_msec;
  606.     thr = ngx_quic_time_threshold(qc);

  608. #if (NGX_SUPPRESS_WARN)
  609.     oldest = now;
  610.     newest = now;
  611. #endif

  613.     nlost = 0;

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

  617.         ctx = &qc->send_ctx[i];

  619.         if (ctx->largest_ack == NGX_QUIC_UNSET_PN) {
  620.             continue;
  621.         }

  623.         pkt_thr = ngx_quic_packet_threshold(ctx);

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

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

  630.             if (start->pnum > ctx->largest_ack) {
  631.                 break;
  632.             }

  634.             wait = start->send_time + thr - now;

  636.             ngx_log_debug5(NGX_LOG_DEBUG_EVENT, c->log, 0,
  637.                   "quic detect_lost pnum:%uL thr:%M pthr:%uL wait:%i level:%ui",
  638.                   start->pnum, thr, pkt_thr, (ngx_int_t) wait, start->level);

  640.             if ((ngx_msec_int_t) wait > 0
  641.                 && ctx->largest_ack - start->pnum < pkt_thr)
  642.             {
  643.                 break;
  644.             }

  646.             if ((ngx_msec_int_t) (start->send_time - qc->first_rtt) > 0) {

  648.                 if (nlost == 0
  649.                     || (ngx_msec_int_t) (start->send_time - oldest) < 0)
  650.                 {
  651.                     oldest = start->send_time;
  652.                 }

  654.                 if (nlost == 0
  655.                     || (ngx_msec_int_t) (start->send_time - newest) > 0)
  656.                 {
  657.                     newest = start->send_time;
  658.                 }

  660.                 nlost++;
  661.             }

  663.             ngx_quic_resend_frames(c, ctx);
  664.         }
  665.     }


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

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

  677.     if (st && nlost >= 2 && ((ngx_msec_int_t) (st->newest - oldest) < 0
  678.                              || (ngx_msec_int_t) (st->oldest - newest) > 0))
  679.     {
  680.         if (newest - oldest > ngx_quic_pcg_duration(c)) {
  681.             ngx_quic_persistent_congestion(c);
  682.         }
  683.     }

  685.     ngx_quic_set_lost_timer(c);

  687.     return NGX_OK;
  688. }


  691. static ngx_msec_t
  692. ‌ngx_quic_pcg_duration(ngx_connection_t *c)
  693. {
  694.     ngx_msec_t              duration;
  695.     ngx_quic_connection_t  *qc;

  697.     qc = ngx_quic_get_connection(c);

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

  704.     return duration;
  705. }


  708. static void
  709. ‌ngx_quic_persistent_congestion(ngx_connection_t *c)
  710. {
  711.     ngx_quic_congestion_t  *cg;
  712.     ngx_quic_connection_t  *qc;

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

  717.     cg->mtu = qc->path->mtu;
  718.     cg->recovery_start = ngx_quic_oldest_sent_packet(c) - 1;
  719.     cg->window = cg->mtu * 2;

  721.     ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
  722.                    "quic congestion persistent t:%M win:%uz",
  723.                    ngx_current_msec, cg->window);
  724. }


  727. static ngx_msec_t
  728. ‌ngx_quic_oldest_sent_packet(ngx_connection_t *c)
  729. {
  730.     ngx_msec_t              oldest;
  731.     ngx_uint_t              i;
  732.     ngx_queue_t            *q;
  733.     ngx_quic_frame_t       *start;
  734.     ngx_quic_send_ctx_t    *ctx;
  735.     ngx_quic_connection_t  *qc;

  737.     qc = ngx_quic_get_connection(c);
  738.     oldest = ngx_current_msec;

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

  743.         if (!ngx_queue_empty(&ctx->sent)) {
  744.             q = ngx_queue_head(&ctx->sent);
  745.             start = ngx_queue_data(q, ngx_quic_frame_t, queue);

  747.             if ((ngx_msec_int_t) (start->send_time - oldest) < 0) {
  748.                 oldest = start->send_time;
  749.             }
  750.         }
  751.     }

  753.     return oldest;
  754. }


  757. void
  758. ‌ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  759. {
  760.     uint64_t                pnum;
  761.     ngx_queue_t            *q;
  762.     ngx_quic_frame_t       *f, *start;
  763.     ngx_quic_stream_t      *qs;
  764.     ngx_quic_connection_t  *qc;

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

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

  774.     ngx_quic_congestion_lost(c, start);

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

  779.         if (f->pnum != pnum) {
  780.             break;
  781.         }

  783.         q = ngx_queue_next(q);

  785.         ngx_queue_remove(&f->queue);

  787.         switch (f->type) {
  788.         case NGX_QUIC_FT_ACK:
  789.         case NGX_QUIC_FT_ACK_ECN:
  790.             if (ctx->level == NGX_QUIC_ENCRYPTION_APPLICATION) {
  791.                 /* force generation of most recent acknowledgment */
  792.                 ctx->send_ack = NGX_QUIC_MAX_ACK_GAP;
  793.             }

  795.             ngx_quic_free_frame(c, f);
  796.             break;

  798.         case NGX_QUIC_FT_PING:
  799.         case NGX_QUIC_FT_PATH_CHALLENGE:
  800.         case NGX_QUIC_FT_PATH_RESPONSE:
  801.         case NGX_QUIC_FT_CONNECTION_CLOSE:
  802.             ngx_quic_free_frame(c, f);
  803.             break;

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

  810.         case NGX_QUIC_FT_MAX_STREAMS:
  811.         case NGX_QUIC_FT_MAX_STREAMS2:
  812.             f->u.max_streams.limit = f->u.max_streams.bidi
  813.                                      ? qc->streams.client_max_streams_bidi
  814.                                      : qc->streams.client_max_streams_uni;
  815.             ngx_quic_queue_frame(qc, f);
  816.             break;

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

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

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

  833.             if (qs == NULL
  834.                 || qs->send_state == NGX_QUIC_STREAM_SEND_RESET_SENT
  835.                 || qs->send_state == NGX_QUIC_STREAM_SEND_RESET_RECVD)
  836.             {
  837.                 ngx_quic_free_frame(c, f);
  838.                 break;
  839.             }

  841.             /* fall through */

  843.         default:
  844.             ngx_queue_insert_tail(&ctx->frames, &f->queue);
  845.         }

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

  849.     if (qc->closing) {
  850.         return;
  851.     }

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


  857. static void
  858. ‌ngx_quic_congestion_lost(ngx_connection_t *c, ngx_quic_frame_t *f)
  859. {
  860.     ngx_uint_t              blocked;
  861.     ngx_msec_t              now, timer;
  862.     ngx_quic_congestion_t  *cg;
  863.     ngx_quic_connection_t  *qc;

  865.     if (f->plen == 0) {
  866.         return;
  867.     }

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

  872.     if (f->pnum < qc->rst_pnum) {
  873.         return;
  874.     }

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

  878.     cg->in_flight -= f->plen;
  879.     f->plen = 0;

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

  883.     now = ngx_current_msec;

  885.     if ((ngx_msec_int_t) timer <= 0) {
  886.         ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  887.                        "quic congestion lost rec t:%M win:%uz if:%uz",
  888.                        now, cg->window, cg->in_flight);

  890.         goto done;
  891.     }

  893.     if (f->ignore_loss) {
  894.         ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  895.                        "quic congestion lost ignore t:%M win:%uz if:%uz",
  896.                        now, cg->window, cg->in_flight);

  898.         goto done;
  899.     }

  901.     /* RFC 9438, 4.6. Multiplicative Decrease */

  903.     cg->mtu = qc->path->mtu;
  904.     cg->recovery_start = now;
  905.     cg->w_prior = cg->window;
  906.     /* RFC 9438, 4.7. Fast Convergence */
  907.     cg->w_max = (cg->window < cg->w_max)
  908.                 ? cg->window * (10 + NGX_QUIC_CUBIC_BETA) / 20 : cg->window;
  909.     cg->ssthresh = cg->in_flight * NGX_QUIC_CUBIC_BETA / 10;
  910.     cg->window = ngx_max(cg->ssthresh, cg->mtu * 2);
  911.     cg->w_est = cg->window;
  912.     cg->k = now + ngx_quic_congestion_cubic_time(c);
  913.     cg->idle_start = now;

  915.     ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
  916.                    "quic congestion lost t:%M win:%uz if:%uz",
  917.                    now, cg->window, cg->in_flight);

  919. done:

  921.     if (blocked && cg->in_flight < cg->window) {
  922.         ngx_post_event(&qc->push, &ngx_posted_events);
  923.     }
  924. }


  927. static ngx_msec_t
  928. ‌ngx_quic_congestion_cubic_time(ngx_connection_t *c)
  929. {
  930.     int64_t                 v, x, d, cc;
  931.     ngx_uint_t              n;
  932.     ngx_quic_congestion_t  *cg;
  933.     ngx_quic_connection_t  *qc;

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

  938.     /*
  939.      * RFC 9438, Figure 2
  940.      *
  941.      *   k_msec = ((w_max - cwnd_epoch) / C / mtu) ^ 1/3 * 1000
  942.      */

  944.     if (cg->w_max <= cg->window) {
  945.         return 0;
  946.     }

  948.     cc = 10000000000ll / (int64_t) cg->mtu / NGX_QUIC_CUBIC_C;
  949.     v = (int64_t) (cg->w_max - cg->window) * cc;

  951.     /*
  952.      * Newton-Raphson method for x ^ 3 = v:
  953.      *
  954.      *   x_next = (2 * x_prev + v / x_prev ^ 2) / 3
  955.      */

  957.     x = 5000;

  959.     for (n = 1; n <= 10; n++) {
  960.         d =  (v / x / x - x) / 3;
  961.         x += d;

  963.         if (ngx_abs(d) <= 100) {
  964.             break;
  965.         }
  966.     }

  968.     if (x > NGX_MAX_SIZE_T_VALUE) {
  969.         return NGX_MAX_SIZE_T_VALUE;
  970.     }

  972.     ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
  973.                    "quic cubic time:%L n:%ui", x, n);

  975.     return x;
  976. }


  979. void
  980. ‌ngx_quic_set_lost_timer(ngx_connection_t *c)
  981. {
  982.     uint64_t                pkt_thr;
  983.     ngx_uint_t              i;
  984.     ngx_msec_t              now;
  985.     ngx_queue_t            *q;
  986.     ngx_msec_int_t          lost, pto, w;
  987.     ngx_quic_frame_t       *f;
  988.     ngx_quic_send_ctx_t    *ctx;
  989.     ngx_quic_connection_t  *qc;

  991.     qc = ngx_quic_get_connection(c);
  992.     now = ngx_current_msec;

  994.     lost = -1;
  995.     pto = -1;

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

  1000.         if (ngx_queue_empty(&ctx->sent)) {
  1001.             continue;
  1002.         }

  1004.         if (ctx->largest_ack != NGX_QUIC_UNSET_PN) {
  1005.             q = ngx_queue_head(&ctx->sent);
  1006.             f = ngx_queue_data(q, ngx_quic_frame_t, queue);
  1007.             w = (ngx_msec_int_t)
  1008.                             (f->send_time + ngx_quic_time_threshold(qc) - now);

  1010.             if (f->pnum <= ctx->largest_ack) {
  1011.                 pkt_thr = ngx_quic_packet_threshold(ctx);

  1013.                 if (w < 0 || ctx->largest_ack - f->pnum >= pkt_thr) {
  1014.                     w = 0;
  1015.                 }

  1017.                 if (lost == -1 || w < lost) {
  1018.                     lost = w;
  1019.                 }
  1020.             }
  1021.         }

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

  1028.         if (w < 0) {
  1029.             w = 0;
  1030.         }

  1032.         if (pto == -1 || w < pto) {
  1033.             pto = w;
  1034.         }
  1035.     }

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

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

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

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

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

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


  1063. ngx_msec_t
  1064. ‌ngx_quic_pto(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  1065. {
  1066.     ngx_msec_t              duration;
  1067.     ngx_quic_connection_t  *qc;

  1069.     qc = ngx_quic_get_connection(c);

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

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

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

  1080.     return duration;
  1081. }


  1084. static
  1085. ‌void ngx_quic_lost_handler(ngx_event_t *ev)
  1086. {
  1087.     ngx_connection_t  *c;

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

  1091.     c = ev->data;

  1093.     if (ngx_quic_detect_lost(c, NULL) != NGX_OK) {
  1094.         ngx_quic_close_connection(c, NGX_ERROR);
  1095.         return;
  1096.     }

  1098.     ngx_quic_connstate_dbg(c);
  1099. }


  1102. void
  1103. ‌ngx_quic_pto_handler(ngx_event_t *ev)
  1104. {
  1105.     ngx_uint_t              i, n;
  1106.     ngx_msec_t              now;
  1107.     ngx_queue_t            *q;
  1108.     ngx_msec_int_t          w;
  1109.     ngx_connection_t       *c;
  1110.     ngx_quic_frame_t       *f;
  1111.     ngx_quic_send_ctx_t    *ctx;
  1112.     ngx_quic_connection_t  *qc;

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

  1116.     c = ev->data;
  1117.     qc = ngx_quic_get_connection(c);
  1118.     now = ngx_current_msec;

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

  1122.         ctx = &qc->send_ctx[i];

  1124.         if (ngx_queue_empty(&ctx->sent)) {
  1125.             continue;
  1126.         }

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

  1133.         if (f->pnum <= ctx->largest_ack
  1134.             && ctx->largest_ack != NGX_QUIC_UNSET_PN)
  1135.         {
  1136.             continue;
  1137.         }

  1139.         if (w > 0) {
  1140.             continue;
  1141.         }

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

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

  1149.             f = ngx_quic_alloc_frame(c);
  1150.             if (f == NULL) {
  1151.                 goto failed;
  1152.             }

  1154.             f->level = ctx->level;
  1155.             f->type = NGX_QUIC_FT_PING;
  1156.             f->ignore_congestion = 1;

  1158.             if (ngx_quic_frame_sendto(c, f, 0, qc->path) == NGX_ERROR) {
  1159.                 goto failed;
  1160.             }
  1161.         }
  1162.     }

  1164.     qc->pto_count++;

  1166.     ngx_quic_set_lost_timer(c);

  1168.     ngx_quic_connstate_dbg(c);

  1170.     return;

  1172. failed:

  1174.     ngx_quic_close_connection(c, NGX_ERROR);
  1175.     return;
  1176. }


  1179. ngx_int_t
  1180. ‌ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt)
  1181. {
  1182.     uint64_t                base, largest, smallest, gs, ge, gap, range, pn;
  1183.     uint64_t                prev_pending;
  1184.     ngx_uint_t              i, nr;
  1185.     ngx_quic_send_ctx_t    *ctx;
  1186.     ngx_quic_ack_range_t   *r;
  1187.     ngx_quic_connection_t  *qc;

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

  1191.     qc = ngx_quic_get_connection(c);

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

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

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

  1204.     prev_pending = ctx->pending_ack;

  1206.     if (pkt->need_ack) {

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

  1210.         if (ctx->send_ack == 0) {
  1211.             ctx->ack_delay_start = ngx_current_msec;
  1212.         }

  1214.         ctx->send_ack++;

  1216.         if (ctx->pending_ack == NGX_QUIC_UNSET_PN
  1217.             || ctx->pending_ack < pkt->pn)
  1218.         {
  1219.             ctx->pending_ack = pkt->pn;
  1220.         }
  1221.     }

  1223.     base = ctx->largest_range;
  1224.     pn = pkt->pn;

  1226.     if (base == NGX_QUIC_UNSET_PN) {
  1227.         ctx->largest_range = pn;
  1228.         ctx->largest_received = pkt->received;
  1229.         return NGX_OK;
  1230.     }

  1232.     if (base == pn) {
  1233.         return NGX_OK;
  1234.     }

  1236.     largest = base;
  1237.     smallest = largest - ctx->first_range;

  1239.     if (pn > base) {

  1241.         if (pn - base == 1) {
  1242.             ctx->first_range++;
  1243.             ctx->largest_range = pn;
  1244.             ctx->largest_received = pkt->received;

  1246.             return NGX_OK;

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

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

  1254.                 if (prev_pending != NGX_QUIC_UNSET_PN) {
  1255.                     if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  1256.                         return NGX_ERROR;
  1257.                     }
  1258.                 }

  1260.                 if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
  1261.                     ctx->pending_ack = NGX_QUIC_UNSET_PN;
  1262.                 }
  1263.             }

  1265.             gap = pn - base - 2;
  1266.             range = ctx->first_range;

  1268.             ctx->first_range = 0;
  1269.             ctx->largest_range = pn;
  1270.             ctx->largest_received = pkt->received;

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

  1277.             i = 0;

  1279.             goto insert;
  1280.         }
  1281.     }

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

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

  1290.     if (pn >= smallest && pn <= largest) {
  1291.         return NGX_OK;
  1292.     }

  1294. #if (NGX_SUPPRESS_WARN)
  1295.     r = NULL;
  1296. #endif

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

  1301.         ge = smallest - 1;
  1302.         gs = ge - r->gap;

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

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

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

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

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

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

  1324.                 ctx->nranges--;

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

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

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

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

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

  1345.                 gap = ge - pn - 1;
  1346.                 range = 0;

  1348.                 if (ctx->nranges == NGX_QUIC_MAX_RANGES) {
  1349.                     if (prev_pending != NGX_QUIC_UNSET_PN) {
  1350.                         if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  1351.                             return NGX_ERROR;
  1352.                         }
  1353.                     }

  1355.                     if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
  1356.                         ctx->pending_ack = NGX_QUIC_UNSET_PN;
  1357.                     }
  1358.                 }

  1360.                 r->gap = pn - gs - 1;
  1361.                 goto insert;
  1362.             }

  1364.             return NGX_OK;
  1365.         }

  1367.         largest = smallest - r->gap - 2;
  1368.         smallest = largest - r->range;

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

  1375.     }

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

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

  1383.         } else {
  1384.             r->range++;
  1385.         }

  1387.         return NGX_OK;
  1388.     }

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

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

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

  1399.         return NGX_OK;
  1400.     }

  1402.     gap = smallest - 2 - pn;
  1403.     range = 0;

  1405. insert:

  1407.     if (ctx->nranges < NGX_QUIC_MAX_RANGES) {
  1408.         ctx->nranges++;
  1409.     }

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

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

  1417.     return NGX_OK;
  1418. }


  1421. ngx_int_t
  1422. ‌ngx_quic_generate_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  1423. {
  1424.     ngx_msec_t              delay;
  1425.     ngx_quic_connection_t  *qc;

  1427.     if (!ctx->send_ack) {
  1428.         return NGX_OK;
  1429.     }

  1431.     if (ctx->level == NGX_QUIC_ENCRYPTION_APPLICATION) {

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

  1436.         if (ngx_queue_empty(&ctx->frames)
  1437.             && ctx->send_ack < NGX_QUIC_MAX_ACK_GAP
  1438.             && delay < qc->tp.max_ack_delay)
  1439.         {
  1440.             if (!qc->push.timer_set && !qc->closing) {
  1441.                 ngx_add_timer(&qc->push,
  1442.                               qc->tp.max_ack_delay - delay);
  1443.             }

  1445.             return NGX_OK;
  1446.         }
  1447.     }

  1449.     if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  1450.         return NGX_ERROR;
  1451.     }

  1453.     ctx->send_ack = 0;

  1455.     return NGX_OK;
  1456. }

One Level Up Top Level