nginx: src/event/ngx_event_quic.c comparison

comparison src/event/ngx_event_quic.c @ 8587:61f1c6ac8967 quic

QUIC: added ACK frame range support. The history of acknowledged packet is kept in send context as ranges. Up to NGX_QUIC_MAX_RANGES ranges is stored. As a result, instead of separate ack frames, single frame with ranges is sent.

author	Vladimir Homutov <vl@nginx.com>
date	Wed, 14 Oct 2020 23:21:36 +0300
parents	02ee77f8d53d
children	018baa412c0d

comparison

equal deleted inserted replaced

-:7621ffaa79b3
+:61f1c6ac8967
 */
 typedef struct {
 ngx_quic_secret_t                 client_secret;
 ngx_quic_secret_t                 server_secret;
+enum ssl_encryption_level_t       level;
 uint64_t                          pnum;        /* to be sent */
 uint64_t                          largest_ack; /* received from peer */
 uint64_t                          largest_pn;  /* received from peer */
 ngx_queue_t                       frames;
 ngx_queue_t                       sent;
+uint64_t                          largest_range;
+uint64_t                          first_range;
+ngx_uint_t                        nranges;
+ngx_quic_ack_range_t              ranges[NGX_QUIC_MAX_RANGES];
+struct timeval                    ack_received;
+ngx_uint_t                        send_ack;    /* unsigned send_ack:1 */
 } ngx_quic_send_ctx_t;
 struct ngx_quic_connection_s {
 ngx_str_t                         scid;  /* initial client ID */
 enum ssl_encryption_level_t level);
 static ngx_int_t ngx_quic_check_peer(ngx_quic_connection_t *qc,
 ngx_quic_header_t *pkt);
 static ngx_int_t ngx_quic_payload_handler(ngx_connection_t *c,
 ngx_quic_header_t *pkt);
-static ngx_int_t ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_header_t *pkt);
+static ngx_int_t ngx_quic_ack_packet(ngx_connection_t *c,
+ngx_quic_header_t *pkt);
+static ngx_int_t ngx_quic_send_ack_range(ngx_connection_t *c,
+ngx_quic_send_ctx_t *ctx, uint64_t smallest, uint64_t largest);
+static ngx_int_t ngx_quic_send_ack(ngx_connection_t *c,
+ngx_quic_send_ctx_t *ctx);
 static ngx_int_t ngx_quic_ack_delay(ngx_connection_t *c,
 struct timeval *received, enum ssl_encryption_level_t level);
 static ngx_int_t ngx_quic_send_cc(ngx_connection_t *c);
 static ngx_int_t ngx_quic_send_new_token(ngx_connection_t *c);
 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) {
 ngx_queue_init(&qc->send_ctx[i].frames);
 ngx_queue_init(&qc->send_ctx[i].sent);
 qc->send_ctx[i].largest_pn = (uint64_t) -1;
 qc->send_ctx[i].largest_ack = (uint64_t) -1;
-}
+qc->send_ctx[i].largest_range = (uint64_t) -1;
+}
+qc->send_ctx[0].level = ssl_encryption_initial;
+qc->send_ctx[1].level = ssl_encryption_handshake;
+qc->send_ctx[2].level = ssl_encryption_application;
 for (i = 0; i < NGX_QUIC_ENCRYPTION_LAST; i++) {
 ngx_queue_init(&qc->crypto[i].frames);
 }
 f = ngx_queue_data(q, ngx_quic_frame_t, queue);
 ngx_quic_congestion_ack(c, f);
 ngx_quic_free_frame(c, f);
 }
+ctx->send_ack = 0;
 }
 static ngx_int_t
 ngx_quic_check_peer(ngx_quic_connection_t *qc, ngx_quic_header_t *pkt)
 }
 /* got there with ack-eliciting packet */
 if (!ack_sent) {
-if (ngx_quic_send_ack(c, pkt) != NGX_OK) {
+if (ngx_quic_ack_packet(c, pkt) != NGX_OK) {
 return NGX_ERROR;
 }
 ack_sent = 1;
 }
 return NGX_OK;
 }
 static ngx_int_t
-ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_header_t *pkt)
+ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt)
+{
+uint64_t               base, largest, smallest, gs, ge, gap, range, pn;
+ngx_uint_t             i, j, nr;
+ngx_quic_send_ctx_t   *ctx;
+ngx_quic_ack_range_t  *r;
+c->log->action = "preparing ack";
+ctx = ngx_quic_get_send_ctx(c->quic, pkt->level);
+ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
+"ngx_quic_ack_packet pn %uL largest %uL nranges %ui",
+pkt->pn, ctx->largest_range, ctx->nranges);
+if (!ctx->send_ack) {
+ngx_post_event(&c->quic->push, &ngx_posted_events);
+}
+ctx->send_ack = 1;
+base = ctx->largest_range;
+pn = pkt->pn;
+if (base == (uint64_t) -1) {
+ctx->largest_range = pn;
+ctx->ack_received = pkt->received;
+return NGX_OK;
+}
+if (base == pn) {
+return NGX_OK;
+}
+largest = base;
+smallest = largest - ctx->first_range;
+if (pn > base) {
+ctx->largest_range = pn;
+ctx->ack_received = pkt->received;
+if (pn - base == 1) {
+ctx->first_range++;
+return NGX_OK;
+} else {
+/* new gap in front of current largest */
+gap = pn - base - 2;
+range = ctx->first_range;
+ctx->first_range = 0;
+i = 0;
+goto insert;
+}
+}
+/*  pn < base, perform lookup in existing ranges */
+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 */
+r->gap = pn - gs - 1;
+gap = ge - pn - 1;
+range = 0;
+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 */
+return ngx_quic_send_ack_range(c, ctx, pn, pn);
+}
+gap = smallest - 2 - pn;
+range = 0;
+insert:
+nr = ctx->nranges - i;
+if (ctx->nranges == NGX_QUIC_MAX_RANGES) {
+/* last range is dropped and reused for newer data */
+for (j = i; j < ctx->nranges; j++) {
+largest = smallest - ctx->ranges[j].gap - 2;
+smallest = largest - ctx->ranges[j].range;
+}
+if (ngx_quic_send_ack_range(c, ctx, smallest, largest) != NGX_OK) {
+return NGX_ERROR;
+}
+nr--;
+} else {
+ctx->nranges++;
+}
+ngx_memmove(&ctx->ranges[i + 1], &ctx->ranges[i],
+sizeof(ngx_quic_ack_range_t) * nr);
+ctx->ranges[i].gap = gap;
+ctx->ranges[i].range = range;
+return NGX_OK;
+}
+static ngx_int_t
+ngx_quic_send_ack_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx,
+uint64_t smallest, uint64_t largest)
 {
 ngx_quic_frame_t  *frame;
-c->log->action = "generating acknowledgment";
-/* every ACK-eliciting packet is acknowledged, TODO ACK Ranges */
 frame = ngx_quic_alloc_frame(c, 0);
 if (frame == NULL) {
 return NGX_ERROR;
 }
-frame->level = (pkt->level == ssl_encryption_early_data)
+frame->level = ctx->level;
-? ssl_encryption_application
-: pkt->level;
 frame->type = NGX_QUIC_FT_ACK;
-frame->u.ack.largest = pkt->pn;
+frame->u.ack.largest = largest;
-frame->u.ack.delay = ngx_quic_ack_delay(c, &pkt->received, frame->level);
+frame->u.ack.delay = 0;
+frame->u.ack.range_count = 0;
-ngx_sprintf(frame->info, "ACK for PN=%uL from frame handler level=%d",
+frame->u.ack.first_range = largest - smallest;
-pkt->pn, frame->level);
+ngx_sprintf(frame->info, "ACK for PN=%uL..%uL 0 ranges level=%d",
+largest, smallest, frame->level);
+return NGX_OK;
+}
+static ngx_int_t
+ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx)
+{
+size_t             ranges_len;
+ngx_quic_frame_t  *frame;
+ranges_len = sizeof(ngx_quic_ack_range_t) * ctx->nranges;
+frame = ngx_quic_alloc_frame(c, ranges_len);
+if (frame == NULL) {
+return NGX_ERROR;
+}
+ngx_memcpy(frame->data, ctx->ranges, ranges_len);
+frame->level = ctx->level;
+frame->type = NGX_QUIC_FT_ACK;
+frame->u.ack.largest = ctx->largest_range;
+frame->u.ack.delay = ngx_quic_ack_delay(c, &ctx->ack_received, ctx->level);
+frame->u.ack.range_count = ctx->nranges;
+frame->u.ack.first_range = ctx->first_range;
+frame->u.ack.ranges_start = frame->data;
+frame->u.ack.ranges_end = frame->data + ranges_len;
+ngx_sprintf(frame->info, "ACK for PN=%uL %ui ranges level=%d",
+ctx->largest_range, ctx->nranges, frame->level);
 ngx_quic_queue_frame(c->quic, frame);
+ctx->send_ack = 0;
 return NGX_OK;
 }
 static ngx_int_t
 ngx_quic_output(ngx_connection_t *c)
 {
 ngx_uint_t              i;
+ngx_quic_send_ctx_t    *ctx;
 ngx_quic_connection_t  *qc;
 c->log->action = "sending frames";
 qc = c->quic;
 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) {
-if (ngx_quic_output_frames(c, &qc->send_ctx[i]) != NGX_OK) {
+ctx = &qc->send_ctx[i];
+if (ctx->send_ack) {
+if (ngx_quic_send_ack(c, ctx) != NGX_OK) {
+return NGX_ERROR;
+}
+}
+if (ngx_quic_output_frames(c, ctx) != NGX_OK) {
 return NGX_ERROR;
 }
 }
 if (!qc->send_timer_set && !qc->closing) {

Mercurial > hg > nginx

comparison src/event/ngx_event_quic.c @ 8587:61f1c6ac8967 quic