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.

3 files changed, 293 insertions, 21 deletions

diff --git a/src/event/ngx_event_quic.c b/src/event/ngx_event_quic.c
index ed865c327..40084753c 100644
--- a/src/event/ngx_event_quic.c
+++ b/src/event/ngx_event_quic.c
@@ -93,12 +93,21 @@ 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;
 
 
@@ -230,7 +239,12 @@ 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);
@@ -685,8 +699,13 @@ ngx_quic_new_connection(ngx_connection_t *c, ngx_quic_conf_t *conf,
         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);
     }
@@ -1974,6 +1993,8 @@ ngx_quic_discard_ctx(ngx_connection_t *c, enum ssl_encryption_level_t level)
         ngx_quic_congestion_ack(c, f);
         ngx_quic_free_frame(c, f);
     }
+
+    ctx->send_ack = 0;
 }
 
 
@@ -2109,7 +2130,7 @@ ngx_quic_payload_handler(ngx_connection_t *c, 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;
             }
 
@@ -2274,31 +2295,251 @@ 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)
+ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt)
 {
-    ngx_quic_frame_t  *frame;
+    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;
 
-    c->log->action = "generating acknowledgment";
+        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;
 
-    /* every ACK-eliciting packet is acknowledged, TODO ACK Ranges */
+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;
 
     frame = ngx_quic_alloc_frame(c, 0);
     if (frame == NULL) {
         return NGX_ERROR;
     }
 
-    frame->level = (pkt->level == ssl_encryption_early_data)
-                   ? ssl_encryption_application
-                   : pkt->level;
+    frame->level = ctx->level;
+    frame->type = NGX_QUIC_FT_ACK;
+    frame->u.ack.largest = largest;
+    frame->u.ack.delay = 0;
+    frame->u.ack.range_count = 0;
+    frame->u.ack.first_range = largest - smallest;
+
+    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 = pkt->pn;
-    frame->u.ack.delay = ngx_quic_ack_delay(c, &pkt->received, frame->level);
+    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_sprintf(frame->info, "ACK for PN=%uL from frame handler level=%d",
-                pkt->pn, frame->level);
     ngx_quic_queue_frame(c->quic, frame);
 
+    ctx->send_ack = 0;
+
     return NGX_OK;
 }
 
@@ -3712,6 +3953,7 @@ 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";
@@ -3719,7 +3961,16 @@ ngx_quic_output(ngx_connection_t *c)
     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;
         }
     }
diff --git a/src/event/ngx_event_quic_transport.c b/src/event/ngx_event_quic_transport.c
index 1bd470f26..f81be23c9 100644
--- a/src/event/ngx_event_quic_transport.c
+++ b/src/event/ngx_event_quic_transport.c
@@ -1259,18 +1259,25 @@ ngx_quic_create_frame(u_char *p, ngx_quic_frame_t *f)
 static size_t
 ngx_quic_create_ack(u_char *p, ngx_quic_ack_frame_t *ack)
 {
-    size_t   len;
-    u_char  *start;
+    size_t                 len;
+    u_char                *start;
+    ngx_uint_t             i;
+    ngx_quic_ack_range_t  *ranges;
 
-    /* minimal ACK packet */
+    ranges = (ngx_quic_ack_range_t *) ack->ranges_start;
 
     if (p == NULL) {
         len = ngx_quic_varint_len(NGX_QUIC_FT_ACK);
         len += ngx_quic_varint_len(ack->largest);
         len += ngx_quic_varint_len(ack->delay);
-        len += ngx_quic_varint_len(0);
+        len += ngx_quic_varint_len(ack->range_count);
         len += ngx_quic_varint_len(ack->first_range);
 
+        for (i = 0; i < ack->range_count; i++) {
+            len += ngx_quic_varint_len(ranges[i].gap);
+            len += ngx_quic_varint_len(ranges[i].range);
+        }
+
         return len;
     }
 
@@ -1279,9 +1286,14 @@ ngx_quic_create_ack(u_char *p, ngx_quic_ack_frame_t *ack)
     ngx_quic_build_int(&p, NGX_QUIC_FT_ACK);
     ngx_quic_build_int(&p, ack->largest);
     ngx_quic_build_int(&p, ack->delay);
-    ngx_quic_build_int(&p, 0);
+    ngx_quic_build_int(&p, ack->range_count);
     ngx_quic_build_int(&p, ack->first_range);
 
+    for (i = 0; i < ack->range_count; i++) {
+        ngx_quic_build_int(&p, ranges[i].gap);
+        ngx_quic_build_int(&p, ranges[i].range);
+    }
+
     return p - start;
 }
 
diff --git a/src/event/ngx_event_quic_transport.h b/src/event/ngx_event_quic_transport.h
index 54f903473..12aad5aae 100644
--- a/src/event/ngx_event_quic_transport.h
+++ b/src/event/ngx_event_quic_transport.h
@@ -120,6 +120,15 @@
 #define NGX_QUIC_CID_LEN_MIN                                8
 #define NGX_QUIC_CID_LEN_MAX                               20
 
+#define NGX_QUIC_MAX_RANGES                                10
+
+
+typedef struct {
+    uint64_t                                    gap;
+    uint64_t                                    range;
+} ngx_quic_ack_range_t;
+
+
 typedef struct {
     uint64_t                                    largest;
     uint64_t                                    delay;
@@ -128,8 +137,8 @@ typedef struct {
     uint64_t                                    ect0;
     uint64_t                                    ect1;
     uint64_t                                    ce;
-    u_char                                      *ranges_start;
-    u_char                                      *ranges_end;
+    u_char                                     *ranges_start;
+    u_char                                     *ranges_end;
 } ngx_quic_ack_frame_t;