One Level Up Top Level

src/event/quic/ngx_event_quic_ack.c - nginx source code

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


  24. /* send time of ACK'ed packets */
  25. ‌typedef struct {
  26.     ngx_msec_t                               max_pn;
  27.     ngx_msec_t                               oldest;
  28.     ngx_msec_t                               newest;
  29. ‌} ngx_quic_ack_stat_t;


  32. static ngx_inline ngx_msec_t ngx_quic_lost_threshold(ngx_quic_connection_t *qc);
  33. static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
  34.     enum ssl_encryption_level_t level, ngx_msec_t send_time);
  35. static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
  36.     ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max,
  37.     ngx_quic_ack_stat_t *st);
  38. static void ngx_quic_drop_ack_ranges(ngx_connection_t *c,
  39.     ngx_quic_send_ctx_t *ctx, uint64_t pn);
  40. static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c,
  41.     ngx_quic_ack_stat_t *st);
  42. static ngx_msec_t ngx_quic_pcg_duration(ngx_connection_t *c);
  43. static void ngx_quic_persistent_congestion(ngx_connection_t *c);
  44. static void ngx_quic_congestion_lost(ngx_connection_t *c,
  45.     ngx_quic_frame_t *frame);
  46. static void ngx_quic_lost_handler(ngx_event_t *ev);


  49. /* RFC 9002, 6.1.2. Time Threshold: kTimeThreshold, kGranularity */
  50. static ngx_inline ngx_msec_t
  51. ‌ngx_quic_lost_threshold(ngx_quic_connection_t *qc)
  52. {
  53.     ngx_msec_t  thr;

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

  58.     return ngx_max(thr, NGX_QUIC_TIME_GRANULARITY);
  59. }


  62. ngx_int_t
  63. ‌ngx_quic_handle_ack_frame(ngx_connection_t *c, ngx_quic_header_t *pkt,
  64.     ngx_quic_frame_t *f)
  65. {
  66.     ssize_t                 n;
  67.     u_char                 *pos, *end;
  68.     uint64_t                min, max, gap, range;
  69.     ngx_uint_t              i;
  70.     ngx_quic_ack_stat_t     send_time;
  71.     ngx_quic_send_ctx_t    *ctx;
  72.     ngx_quic_ack_frame_t   *ack;
  73.     ngx_quic_connection_t  *qc;

  75.     qc = ngx_quic_get_connection(c);

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

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

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

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

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

  98.     min = ack->largest - ack->first_range;
  99.     max = ack->largest;

  101.     send_time.oldest = NGX_TIMER_INFINITE;
  102.     send_time.newest = NGX_TIMER_INFINITE;

  104.     if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
  105.         != NGX_OK)
  106.     {
  107.         return NGX_ERROR;
  108.     }

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

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

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

  131.     if (f->data) {
  132.         pos = f->data->buf->pos;
  133.         end = f->data->buf->last;

  135.     } else {
  136.         pos = NULL;
  137.         end = NULL;
  138.     }

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

  142.         n = ngx_quic_parse_ack_range(pkt->log, pos, end, &gap, &range);
  143.         if (n == NGX_ERROR) {
  144.             return NGX_ERROR;
  145.         }
  146.         pos += n;

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

  155.         max = min - gap - 2;

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

  164.         min = max - range;

  166.         if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time)
  167.             != NGX_OK)
  168.         {
  169.             return NGX_ERROR;
  170.         }
  171.     }

  173.     return ngx_quic_detect_lost(c, &send_time);
  174. }


  177. static void
  178. ‌ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack,
  179.     enum ssl_encryption_level_t level, ngx_msec_t send_time)
  180. {
  181.     ngx_msec_t              latest_rtt, ack_delay, adjusted_rtt, rttvar_sample;
  182.     ngx_quic_connection_t  *qc;

  184.     qc = ngx_quic_get_connection(c);

  186.     latest_rtt = ngx_current_msec - send_time;
  187.     qc->latest_rtt = latest_rtt;

  189.     if (qc->min_rtt == NGX_TIMER_INFINITE) {
  190.         qc->min_rtt = latest_rtt;
  191.         qc->avg_rtt = latest_rtt;
  192.         qc->rttvar = latest_rtt / 2;
  193.         qc->first_rtt = ngx_current_msec;

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

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

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

  204.         adjusted_rtt = latest_rtt;

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

  210.         rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt));
  211.         qc->rttvar += (rttvar_sample >> 2) - (qc->rttvar >> 2);
  212.         qc->avg_rtt += (adjusted_rtt >> 3) - (qc->avg_rtt >> 3);
  213.     }

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


  221. static ngx_int_t
  222. ‌ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
  223.     uint64_t min, uint64_t max, ngx_quic_ack_stat_t *st)
  224. {
  225.     ngx_uint_t              found;
  226.     ngx_queue_t            *q;
  227.     ngx_quic_frame_t       *f;
  228.     ngx_quic_connection_t  *qc;

  230.     qc = ngx_quic_get_connection(c);

  232.     if (ctx->level == ssl_encryption_application) {
  233.         if (ngx_quic_handle_path_mtu(c, qc->path, min, max) != NGX_OK) {
  234.             return NGX_ERROR;
  235.         }
  236.     }

  238.     st->max_pn = NGX_TIMER_INFINITE;
  239.     found = 0;

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

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

  245.         f = ngx_queue_data(q, ngx_quic_frame_t, queue);
  246.         q = ngx_queue_next(q);

  248.         if (f->pnum > max) {
  249.             break;
  250.         }

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

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

  261.             case NGX_QUIC_FT_STREAM:
  262.             case NGX_QUIC_FT_RESET_STREAM:
  263.                 ngx_quic_handle_stream_ack(c, f);
  264.                 break;
  265.             }

  267.             if (f->pnum == max) {
  268.                 st->max_pn = f->send_time;
  269.             }

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

  276.             if (st->newest == NGX_TIMER_INFINITE || f->send_time > st->newest) {
  277.                 st->newest = f->send_time;
  278.             }

  280.             ngx_queue_remove(&f->queue);
  281.             ngx_quic_free_frame(c, f);
  282.             found = 1;
  283.         }
  284.     }

  286.     if (!found) {

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

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

  296.         qc->error = NGX_QUIC_ERR_PROTOCOL_VIOLATION;
  297.         qc->error_ftype = NGX_QUIC_FT_ACK;
  298.         qc->error_reason = "unknown packet number";

  300.         return NGX_ERROR;
  301.     }

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

  307.     qc->pto_count = 0;

  309.     return NGX_OK;
  310. }


  313. void
  314. ‌ngx_quic_congestion_ack(ngx_connection_t *c, ngx_quic_frame_t *f)
  315. {
  316.     ngx_uint_t              blocked;
  317.     ngx_msec_t              timer;
  318.     ngx_quic_congestion_t  *cg;
  319.     ngx_quic_connection_t  *qc;

  321.     if (f->plen == 0) {
  322.         return;
  323.     }

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

  328.     if (f->pnum < qc->rst_pnum) {
  329.         return;
  330.     }

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

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

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

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

  343.         goto done;
  344.     }

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

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

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

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

  361.     /* prevent recovery_start from wrapping */

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

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

  369. done:

  371.     if (blocked && cg->in_flight < cg->window) {
  372.         ngx_post_event(&qc->push, &ngx_posted_events);
  373.     }
  374. }


  377. static void
  378. ‌ngx_quic_drop_ack_ranges(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
  379.     uint64_t pn)
  380. {
  381.     uint64_t               base;
  382.     ngx_uint_t             i, smallest, largest;
  383.     ngx_quic_ack_range_t  *r;

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

  390.     base = ctx->largest_range;

  392.     if (base == NGX_QUIC_UNSET_PN) {
  393.         return;
  394.     }

  396.     if (ctx->pending_ack != NGX_QUIC_UNSET_PN && pn >= ctx->pending_ack) {
  397.         ctx->pending_ack = NGX_QUIC_UNSET_PN;
  398.     }

  400.     largest = base;
  401.     smallest = largest - ctx->first_range;

  403.     if (pn >= largest) {
  404.         ctx->largest_range = NGX_QUIC_UNSET_PN;
  405.         ctx->first_range = 0;
  406.         ctx->nranges = 0;
  407.         return;
  408.     }

  410.     if (pn >= smallest) {
  411.         ctx->first_range = largest - pn - 1;
  412.         ctx->nranges = 0;
  413.         return;
  414.     }

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

  419.         largest = smallest - r->gap - 2;
  420.         smallest = largest - r->range;

  422.         if (pn >= largest) {
  423.             ctx->nranges = i;
  424.             return;
  425.         }
  426.         if (pn >= smallest) {
  427.             r->range = largest - pn - 1;
  428.             ctx->nranges = i + 1;
  429.             return;
  430.         }
  431.     }
  432. }


  435. static ngx_int_t
  436. ‌ngx_quic_detect_lost(ngx_connection_t *c, ngx_quic_ack_stat_t *st)
  437. {
  438.     ngx_uint_t              i, nlost;
  439.     ngx_msec_t              now, wait, thr, oldest, newest;
  440.     ngx_queue_t            *q;
  441.     ngx_quic_frame_t       *start;
  442.     ngx_quic_send_ctx_t    *ctx;
  443.     ngx_quic_connection_t  *qc;

  445.     qc = ngx_quic_get_connection(c);
  446.     now = ngx_current_msec;
  447.     thr = ngx_quic_lost_threshold(qc);

  449.     /* send time of lost packets across all send contexts */
  450.     oldest = NGX_TIMER_INFINITE;
  451.     newest = NGX_TIMER_INFINITE;

  453.     nlost = 0;

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

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

  459.         if (ctx->largest_ack == NGX_QUIC_UNSET_PN) {
  460.             continue;
  461.         }

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

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

  468.             if (start->pnum > ctx->largest_ack) {
  469.                 break;
  470.             }

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

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

  478.             if ((ngx_msec_int_t) wait > 0
  479.                 && ctx->largest_ack - start->pnum < NGX_QUIC_PKT_THR)
  480.             {
  481.                 break;
  482.             }

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

  486.                 if (oldest == NGX_TIMER_INFINITE || start->send_time < oldest) {
  487.                     oldest = start->send_time;
  488.                 }

  490.                 if (newest == NGX_TIMER_INFINITE || start->send_time > newest) {
  491.                     newest = start->send_time;
  492.                 }

  494.                 nlost++;
  495.             }

  497.             ngx_quic_resend_frames(c, ctx);
  498.         }
  499.     }


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

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

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

  513.         if (newest - oldest > ngx_quic_pcg_duration(c)) {
  514.             ngx_quic_persistent_congestion(c);
  515.         }
  516.     }

  518.     ngx_quic_set_lost_timer(c);

  520.     return NGX_OK;
  521. }


  524. static ngx_msec_t
  525. ‌ngx_quic_pcg_duration(ngx_connection_t *c)
  526. {
  527.     ngx_msec_t              duration;
  528.     ngx_quic_connection_t  *qc;

  530.     qc = ngx_quic_get_connection(c);

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

  537.     return duration;
  538. }


  541. static void
  542. ‌ngx_quic_persistent_congestion(ngx_connection_t *c)
  543. {
  544.     ngx_quic_congestion_t  *cg;
  545.     ngx_quic_connection_t  *qc;

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

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

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


  558. void
  559. ‌ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  560. {
  561.     uint64_t                pnum;
  562.     ngx_queue_t            *q;
  563.     ngx_quic_frame_t       *f, *start;
  564.     ngx_quic_stream_t      *qs;
  565.     ngx_quic_connection_t  *qc;

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

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

  575.     ngx_quic_congestion_lost(c, start);

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

  580.         if (f->pnum != pnum) {
  581.             break;
  582.         }

  584.         q = ngx_queue_next(q);

  586.         ngx_queue_remove(&f->queue);

  588.         switch (f->type) {
  589.         case NGX_QUIC_FT_ACK:
  590.         case NGX_QUIC_FT_ACK_ECN:
  591.             if (ctx->level == ssl_encryption_application) {
  592.                 /* force generation of most recent acknowledgment */
  593.                 ctx->send_ack = NGX_QUIC_MAX_ACK_GAP;
  594.             }

  596.             ngx_quic_free_frame(c, f);
  597.             break;

  599.         case NGX_QUIC_FT_PING:
  600.         case NGX_QUIC_FT_PATH_CHALLENGE:
  601.         case NGX_QUIC_FT_PATH_RESPONSE:
  602.         case NGX_QUIC_FT_CONNECTION_CLOSE:
  603.             ngx_quic_free_frame(c, f);
  604.             break;

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

  611.         case NGX_QUIC_FT_MAX_STREAMS:
  612.         case NGX_QUIC_FT_MAX_STREAMS2:
  613.             f->u.max_streams.limit = f->u.max_streams.bidi
  614.                                      ? qc->streams.client_max_streams_bidi
  615.                                      : qc->streams.client_max_streams_uni;
  616.             ngx_quic_queue_frame(qc, f);
  617.             break;

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

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

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

  634.             if (qs == NULL
  635.                 || qs->send_state == NGX_QUIC_STREAM_SEND_RESET_SENT
  636.                 || qs->send_state == NGX_QUIC_STREAM_SEND_RESET_RECVD)
  637.             {
  638.                 ngx_quic_free_frame(c, f);
  639.                 break;
  640.             }

  642.             /* fall through */

  644.         default:
  645.             ngx_queue_insert_tail(&ctx->frames, &f->queue);
  646.         }

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

  650.     if (qc->closing) {
  651.         return;
  652.     }

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


  658. static void
  659. ‌ngx_quic_congestion_lost(ngx_connection_t *c, ngx_quic_frame_t *f)
  660. {
  661.     ngx_uint_t              blocked;
  662.     ngx_msec_t              timer;
  663.     ngx_quic_congestion_t  *cg;
  664.     ngx_quic_connection_t  *qc;

  666.     if (f->plen == 0) {
  667.         return;
  668.     }

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

  673.     if (f->pnum < qc->rst_pnum) {
  674.         return;
  675.     }

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

  679.     cg->in_flight -= f->plen;
  680.     f->plen = 0;

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

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

  689.         goto done;
  690.     }

  692.     cg->recovery_start = ngx_current_msec;
  693.     cg->window /= 2;

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

  699.     cg->ssthresh = cg->window;

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

  705. done:

  707.     if (blocked && cg->in_flight < cg->window) {
  708.         ngx_post_event(&qc->push, &ngx_posted_events);
  709.     }
  710. }


  713. void
  714. ‌ngx_quic_set_lost_timer(ngx_connection_t *c)
  715. {
  716.     ngx_uint_t              i;
  717.     ngx_msec_t              now;
  718.     ngx_queue_t            *q;
  719.     ngx_msec_int_t          lost, pto, w;
  720.     ngx_quic_frame_t       *f;
  721.     ngx_quic_send_ctx_t    *ctx;
  722.     ngx_quic_connection_t  *qc;

  724.     qc = ngx_quic_get_connection(c);
  725.     now = ngx_current_msec;

  727.     lost = -1;
  728.     pto = -1;

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

  733.         if (ngx_queue_empty(&ctx->sent)) {
  734.             continue;
  735.         }

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

  743.             if (f->pnum <= ctx->largest_ack) {
  744.                 if (w < 0 || ctx->largest_ack - f->pnum >= NGX_QUIC_PKT_THR) {
  745.                     w = 0;
  746.                 }

  748.                 if (lost == -1 || w < lost) {
  749.                     lost = w;
  750.                 }
  751.             }
  752.         }

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

  759.         if (w < 0) {
  760.             w = 0;
  761.         }

  763.         if (pto == -1 || w < pto) {
  764.             pto = w;
  765.         }
  766.     }

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

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

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

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

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

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


  794. ngx_msec_t
  795. ‌ngx_quic_pto(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  796. {
  797.     ngx_msec_t              duration;
  798.     ngx_quic_connection_t  *qc;

  800.     qc = ngx_quic_get_connection(c);

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

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

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

  811.     return duration;
  812. }


  815. static
  816. ‌void ngx_quic_lost_handler(ngx_event_t *ev)
  817. {
  818.     ngx_connection_t  *c;

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

  822.     c = ev->data;

  824.     if (ngx_quic_detect_lost(c, NULL) != NGX_OK) {
  825.         ngx_quic_close_connection(c, NGX_ERROR);
  826.         return;
  827.     }

  829.     ngx_quic_connstate_dbg(c);
  830. }


  833. void
  834. ‌ngx_quic_pto_handler(ngx_event_t *ev)
  835. {
  836.     ngx_uint_t              i, n;
  837.     ngx_msec_t              now;
  838.     ngx_queue_t            *q;
  839.     ngx_msec_int_t          w;
  840.     ngx_connection_t       *c;
  841.     ngx_quic_frame_t       *f;
  842.     ngx_quic_send_ctx_t    *ctx;
  843.     ngx_quic_connection_t  *qc;

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

  847.     c = ev->data;
  848.     qc = ngx_quic_get_connection(c);
  849.     now = ngx_current_msec;

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

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

  855.         if (ngx_queue_empty(&ctx->sent)) {
  856.             continue;
  857.         }

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

  864.         if (f->pnum <= ctx->largest_ack
  865.             && ctx->largest_ack != NGX_QUIC_UNSET_PN)
  866.         {
  867.             continue;
  868.         }

  870.         if (w > 0) {
  871.             continue;
  872.         }

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

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

  880.             f = ngx_quic_alloc_frame(c);
  881.             if (f == NULL) {
  882.                 goto failed;
  883.             }

  885.             f->level = ctx->level;
  886.             f->type = NGX_QUIC_FT_PING;
  887.             f->ignore_congestion = 1;

  889.             if (ngx_quic_frame_sendto(c, f, 0, qc->path) == NGX_ERROR) {
  890.                 goto failed;
  891.             }
  892.         }
  893.     }

  895.     qc->pto_count++;

  897.     ngx_quic_set_lost_timer(c);

  899.     ngx_quic_connstate_dbg(c);

  901.     return;

  903. failed:

  905.     ngx_quic_close_connection(c, NGX_ERROR);
  906.     return;
  907. }


  910. ngx_int_t
  911. ‌ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt)
  912. {
  913.     uint64_t                base, largest, smallest, gs, ge, gap, range, pn;
  914.     uint64_t                prev_pending;
  915.     ngx_uint_t              i, nr;
  916.     ngx_quic_send_ctx_t    *ctx;
  917.     ngx_quic_ack_range_t   *r;
  918.     ngx_quic_connection_t  *qc;

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

  922.     qc = ngx_quic_get_connection(c);

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

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

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

  935.     prev_pending = ctx->pending_ack;

  937.     if (pkt->need_ack) {

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

  941.         if (ctx->send_ack == 0) {
  942.             ctx->ack_delay_start = ngx_current_msec;
  943.         }

  945.         ctx->send_ack++;

  947.         if (ctx->pending_ack == NGX_QUIC_UNSET_PN
  948.             || ctx->pending_ack < pkt->pn)
  949.         {
  950.             ctx->pending_ack = pkt->pn;
  951.         }
  952.     }

  954.     base = ctx->largest_range;
  955.     pn = pkt->pn;

  957.     if (base == NGX_QUIC_UNSET_PN) {
  958.         ctx->largest_range = pn;
  959.         ctx->largest_received = pkt->received;
  960.         return NGX_OK;
  961.     }

  963.     if (base == pn) {
  964.         return NGX_OK;
  965.     }

  967.     largest = base;
  968.     smallest = largest - ctx->first_range;

  970.     if (pn > base) {

  972.         if (pn - base == 1) {
  973.             ctx->first_range++;
  974.             ctx->largest_range = pn;
  975.             ctx->largest_received = pkt->received;

  977.             return NGX_OK;

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

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

  985.                 if (prev_pending != NGX_QUIC_UNSET_PN) {
  986.                     if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  987.                         return NGX_ERROR;
  988.                     }
  989.                 }

  991.                 if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
  992.                     ctx->pending_ack = NGX_QUIC_UNSET_PN;
  993.                 }
  994.             }

  996.             gap = pn - base - 2;
  997.             range = ctx->first_range;

  999.             ctx->first_range = 0;
  1000.             ctx->largest_range = pn;
  1001.             ctx->largest_received = pkt->received;

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

  1008.             i = 0;

  1010.             goto insert;
  1011.         }
  1012.     }

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

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

  1021.     if (pn >= smallest && pn <= largest) {
  1022.         return NGX_OK;
  1023.     }

  1025. #if (NGX_SUPPRESS_WARN)
  1026.     r = NULL;
  1027. #endif

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

  1032.         ge = smallest - 1;
  1033.         gs = ge - r->gap;

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

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

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

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

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

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

  1055.                 ctx->nranges--;

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

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

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

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

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

  1076.                 gap = ge - pn - 1;
  1077.                 range = 0;

  1079.                 if (ctx->nranges == NGX_QUIC_MAX_RANGES) {
  1080.                     if (prev_pending != NGX_QUIC_UNSET_PN) {
  1081.                         if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  1082.                             return NGX_ERROR;
  1083.                         }
  1084.                     }

  1086.                     if (prev_pending == ctx->pending_ack || !pkt->need_ack) {
  1087.                         ctx->pending_ack = NGX_QUIC_UNSET_PN;
  1088.                     }
  1089.                 }

  1091.                 r->gap = pn - gs - 1;
  1092.                 goto insert;
  1093.             }

  1095.             return NGX_OK;
  1096.         }

  1098.         largest = smallest - r->gap - 2;
  1099.         smallest = largest - r->range;

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

  1106.     }

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

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

  1114.         } else {
  1115.             r->range++;
  1116.         }

  1118.         return NGX_OK;
  1119.     }

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

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

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

  1130.         return NGX_OK;
  1131.     }

  1133.     gap = smallest - 2 - pn;
  1134.     range = 0;

  1136. insert:

  1138.     if (ctx->nranges < NGX_QUIC_MAX_RANGES) {
  1139.         ctx->nranges++;
  1140.     }

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

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

  1148.     return NGX_OK;
  1149. }


  1152. ngx_int_t
  1153. ‌ngx_quic_generate_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
  1154. {
  1155.     ngx_msec_t              delay;
  1156.     ngx_quic_connection_t  *qc;

  1158.     if (!ctx->send_ack) {
  1159.         return NGX_OK;
  1160.     }

  1162.     if (ctx->level == ssl_encryption_application) {

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

  1167.         if (ngx_queue_empty(&ctx->frames)
  1168.             && ctx->send_ack < NGX_QUIC_MAX_ACK_GAP
  1169.             && delay < qc->tp.max_ack_delay)
  1170.         {
  1171.             if (!qc->push.timer_set && !qc->closing) {
  1172.                 ngx_add_timer(&qc->push,
  1173.                               qc->tp.max_ack_delay - delay);
  1174.             }

  1176.             return NGX_OK;
  1177.         }
  1178.     }

  1180.     if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
  1181.         return NGX_ERROR;
  1182.     }

  1184.     ctx->send_ack = 0;

  1186.     return NGX_OK;
  1187. }

One Level Up Top Level