diff src/event/ngx_event_quic.c @ 8333:167d32476737 quic

Crypto buffer frames reordering. If offset in CRYPTO frame doesn't match expected, following actions are taken: a) Duplicate frames or frames within [0...current offset] are ignored b) New data from intersecting ranges (starts before current_offset, ends after) is consumed c) "Future" frames are stored in a sorted queue (min offset .. max offset) Once a frame is consumed, current offset is updated and the queue is inspected: we iterate the queue until the gap is found and act as described above for each frame. The amount of data in buffered frames is limited by corresponding macro. The CRYPTO and STREAM frame structures are now compatible: they share the same set of initial fields. This allows to have code that deals with both of this frames. The ordering layer now processes the frame with offset and invokes the handler when it can organise an ordered stream of data.
author Vladimir Homutov <vl@nginx.com>
date Tue, 14 Apr 2020 12:16:25 +0300
parents 6ad871b63422
children 72d20158c814
line wrap: on
line diff
--- a/src/event/ngx_event_quic.c
+++ b/src/event/ngx_event_quic.c
@@ -26,6 +26,12 @@
 #define NGX_QUIC_STREAMS_INC     16
 #define NGX_QUIC_STREAMS_LIMIT   (1ULL < 60)
 
+/*
+ * 7.4.  Cryptographic Message Buffering
+ *       Implementations MUST support buffering at least 4096 bytes of data
+ */
+#define NGX_QUIC_MAX_BUFFERED    65535
+
 
 typedef enum {
     NGX_QUIC_ST_INITIAL,     /* connection just created */
@@ -64,6 +70,15 @@ typedef struct {
 } ngx_quic_send_ctx_t;
 
 
+/* ordered frames stream context */
+typedef struct {
+    uint64_t                          sent;
+    uint64_t                          received;
+    ngx_queue_t                       frames;
+    size_t                            total; /* size of buffered data */
+} ngx_quic_frames_stream_t;
+
+
 struct ngx_quic_connection_s {
     ngx_str_t                         scid;
     ngx_str_t                         dcid;
@@ -78,8 +93,7 @@ struct ngx_quic_connection_s {
     ngx_quic_send_ctx_t               send_ctx[NGX_QUIC_SEND_CTX_LAST];
     ngx_quic_secrets_t                keys[NGX_QUIC_ENCRYPTION_LAST];
     ngx_quic_secrets_t                next_key;
-    uint64_t                          crypto_offset_out[NGX_QUIC_ENCRYPTION_LAST];
-    uint64_t                          crypto_offset_in[NGX_QUIC_ENCRYPTION_LAST];
+    ngx_quic_frames_stream_t          crypto[NGX_QUIC_ENCRYPTION_LAST];
 
     ngx_ssl_t                        *ssl;
 
@@ -147,7 +161,21 @@ static ngx_int_t ngx_quic_handle_ack_fra
 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
     ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max);
 static ngx_int_t ngx_quic_handle_crypto_frame(ngx_connection_t *c,
-    ngx_quic_header_t *pkt, ngx_quic_crypto_frame_t *frame);
+    ngx_quic_header_t *pkt, ngx_quic_frame_t *frame);
+static ngx_int_t ngx_quic_adjust_frame_offset(ngx_connection_t *c,
+    ngx_quic_frame_t *f, uint64_t offset_in);
+static ngx_int_t ngx_quic_buffer_frame(ngx_connection_t *c,
+    ngx_quic_frames_stream_t *stream, ngx_quic_frame_t *f);
+
+typedef ngx_int_t (*ngx_quic_frame_handler_pt)(ngx_connection_t *c,
+    ngx_quic_frame_t *frame);
+
+static ngx_int_t ngx_quic_handle_ordered_frame(ngx_connection_t *c,
+    ngx_quic_frames_stream_t *fs, ngx_quic_frame_t *frame,
+    ngx_quic_frame_handler_pt handler);
+
+static ngx_int_t ngx_quic_crypto_input(ngx_connection_t *c,
+    ngx_quic_frame_t *frame);
 static ngx_int_t ngx_quic_handle_stream_frame(ngx_connection_t *c,
     ngx_quic_header_t *pkt, ngx_quic_stream_frame_t *frame);
 static ngx_int_t ngx_quic_handle_max_streams(ngx_connection_t *c);
@@ -292,12 +320,13 @@ static int
 ngx_quic_add_handshake_data(ngx_ssl_conn_t *ssl_conn,
     enum ssl_encryption_level_t level, const uint8_t *data, size_t len)
 {
-    u_char                 *p, *end;
-    size_t                  client_params_len;
-    const uint8_t          *client_params;
-    ngx_quic_frame_t       *frame;
-    ngx_connection_t       *c;
-    ngx_quic_connection_t  *qc;
+    u_char                    *p, *end;
+    size_t                     client_params_len;
+    const uint8_t             *client_params;
+    ngx_quic_frame_t          *frame;
+    ngx_connection_t          *c;
+    ngx_quic_connection_t     *qc;
+    ngx_quic_frames_stream_t  *fs;
 
     c = ngx_ssl_get_connection((ngx_ssl_conn_t *) ssl_conn);
     qc = c->quic;
@@ -335,6 +364,8 @@ ngx_quic_add_handshake_data(ngx_ssl_conn
         }
     }
 
+    fs = &qc->crypto[level];
+
     frame = ngx_quic_alloc_frame(c, len);
     if (frame == NULL) {
         return 0;
@@ -344,11 +375,11 @@ ngx_quic_add_handshake_data(ngx_ssl_conn
 
     frame->level = level;
     frame->type = NGX_QUIC_FT_CRYPTO;
-    frame->u.crypto.offset += qc->crypto_offset_out[level];
-    frame->u.crypto.len = len;
+    frame->u.crypto.offset += fs->sent;
+    frame->u.crypto.length = len;
     frame->u.crypto.data = frame->data;
 
-    qc->crypto_offset_out[level] += len;
+    fs->sent += len;
 
     ngx_sprintf(frame->info, "crypto, generated by SSL len=%ui level=%d", len, level);
 
@@ -478,10 +509,14 @@ ngx_quic_new_connection(ngx_connection_t
     ngx_rbtree_init(&qc->streams.tree, &qc->streams.sentinel,
                     ngx_quic_rbtree_insert_stream);
 
-    for (i = 0; i < 3; i++) {
+    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);
-     }
+    }
+
+    for (i = 0; i < NGX_QUIC_ENCRYPTION_LAST; i++) {
+        ngx_queue_init(&qc->crypto[i].frames);
+    }
 
     ngx_queue_init(&qc->free_frames);
 
@@ -713,6 +748,8 @@ ngx_quic_close_connection(ngx_connection
 
     ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0, "close quic connection");
 
+    // TODO: free frames from reorder queue if any
+
     qc = c->quic;
 
     if (qc) {
@@ -829,10 +866,26 @@ ngx_quic_input(ngx_connection_t *c, ngx_
             rc = ngx_quic_app_input(c, &pkt);
         }
 
-        if (rc != NGX_OK) {
-            return rc;
+        if (rc == NGX_ERROR) {
+            return NGX_ERROR;
         }
 
+        /* NGX_OK || NGX_DECLINED */
+
+        /*
+         * we get NGX_DECLINED when there are no keys [yet] available
+         * to decrypt packet.
+         * Instead of queueing it, we ignore it and rely on the sender's
+         * retransmission:
+         *
+         * 12.2.  Coalescing Packets:
+         *
+         * For example, if decryption fails (because the keys are
+         * not available or any other reason), the receiver MAY either
+         * discard or buffer the packet for later processing and MUST
+         * attempt to process the remaining packets.
+         */
+
         /* b->pos is at header end, adjust by actual packet length */
         p = b->pos + pkt.len;
         b->pos = p;       /* reset b->pos to the next packet start */
@@ -1119,9 +1172,7 @@ ngx_quic_payload_handler(ngx_connection_
 
         case NGX_QUIC_FT_CRYPTO:
 
-            if (ngx_quic_handle_crypto_frame(c, pkt, &frame.u.crypto)
-                != NGX_OK)
-            {
+            if (ngx_quic_handle_crypto_frame(c, pkt, &frame) != NGX_OK) {
                 return NGX_ERROR;
             }
 
@@ -1373,26 +1424,224 @@ ngx_quic_handle_ack_frame_range(ngx_conn
 
 static ngx_int_t
 ngx_quic_handle_crypto_frame(ngx_connection_t *c, ngx_quic_header_t *pkt,
-    ngx_quic_crypto_frame_t *f)
+    ngx_quic_frame_t *frame)
 {
-    int                     sslerr;
-    ssize_t                 n;
-    uint64_t               *curr_offset;
-    ngx_ssl_conn_t         *ssl_conn;
-    ngx_quic_connection_t  *qc;
+    ngx_quic_connection_t     *qc;
+    ngx_quic_frames_stream_t  *fs;
 
     qc = c->quic;
-
-    curr_offset = &qc->crypto_offset_in[pkt->level];
-
-    if (f->offset != *curr_offset) {
-        ngx_log_error(NGX_LOG_INFO, c->log, 0,
-                      "crypto frame with unexpected offset");
-
-        /* TODO: support reordering/buffering of data */
+    fs = &qc->crypto[pkt->level];
+
+    return ngx_quic_handle_ordered_frame(c, fs, frame, ngx_quic_crypto_input);
+}
+
+
+static ngx_int_t
+ngx_quic_handle_ordered_frame(ngx_connection_t *c, ngx_quic_frames_stream_t *fs,
+    ngx_quic_frame_t *frame, ngx_quic_frame_handler_pt handler)
+{
+    size_t                     full_len;
+    ngx_queue_t               *q;
+    ngx_quic_ordered_frame_t  *f;
+
+    f = &frame->u.ord;
+
+    if (f->offset > fs->received) {
+        ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                       "out-of-order frame: expecting %ui got %ui",
+                       fs->received, f->offset);
+
+        return ngx_quic_buffer_frame(c, fs, frame);
+    }
+
+    if (f->offset < fs->received) {
+
+        if (ngx_quic_adjust_frame_offset(c, frame, fs->received)
+            == NGX_DONE)
+        {
+            /* old/duplicate data range */
+            return NGX_OK;
+        }
+
+        /* intersecting data range, frame modified */
+    }
+
+    /* f->offset == fs->received */
+
+    if (handler(c, frame) != NGX_OK) {
         return NGX_ERROR;
     }
 
+    fs->received += f->length;
+
+    /* now check the queue if we can continue with buffered frames */
+
+    do {
+        q = ngx_queue_head(&fs->frames);
+        if (q == ngx_queue_sentinel(&fs->frames)) {
+            break;
+        }
+
+        frame = ngx_queue_data(q, ngx_quic_frame_t, queue);
+        f = &frame->u.ord;
+
+        if (f->offset > fs->received) {
+            /* gap found, nothing more to do */
+            break;
+        }
+
+        full_len = f->length;
+
+        if (f->offset < fs->received) {
+
+            if (ngx_quic_adjust_frame_offset(c, frame, fs->received)
+                == NGX_DONE)
+            {
+                /* old/duplicate data range */
+                ngx_queue_remove(q);
+                fs->total -= f->length;
+
+                ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                              "skipped buffered frame, total %ui", fs->total);
+                ngx_quic_free_frame(c, frame);
+                continue;
+            }
+
+            /* frame was adjusted, proceed to input */
+        }
+
+        /* f->offset == fs->received */
+
+        if (handler(c, frame) != NGX_OK) {
+            return NGX_ERROR;
+        }
+
+        fs->received += f->length;
+        fs->total -= full_len;
+
+        ngx_queue_remove(q);
+
+        ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                      "consumed buffered frame, total %ui", fs->total);
+
+        ngx_quic_free_frame(c, frame);
+
+    } while (1);
+
+    return NGX_OK;
+}
+
+
+static ngx_int_t
+ngx_quic_adjust_frame_offset(ngx_connection_t *c, ngx_quic_frame_t *frame,
+    uint64_t offset_in)
+{
+    size_t                     tail;
+    ngx_quic_ordered_frame_t  *f;
+
+    f = &frame->u.ord;
+
+    tail = offset_in - f->offset;
+
+    if (tail >= f->length) {
+        /* range preceeding already received data or duplicate, ignore */
+
+        ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                       "old or duplicate data in ordered frame, ignored");
+        return NGX_DONE;
+    }
+
+    ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                   "adjusted ordered frame data start to expected offset");
+
+    /* intersecting range: adjust data size */
+
+    f->offset += tail;
+    f->data += tail;
+    f->length -= tail;
+
+    return NGX_OK;
+}
+
+
+static ngx_int_t
+ngx_quic_buffer_frame(ngx_connection_t *c, ngx_quic_frames_stream_t *fs,
+    ngx_quic_frame_t *frame)
+{
+    u_char                    *data;
+    ngx_queue_t               *q;
+    ngx_quic_frame_t          *dst, *item;
+    ngx_quic_ordered_frame_t  *f, *df;
+
+    ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0, "ngx_quic_buffer_frame");
+
+    f = &frame->u.ord;
+
+    /* frame start offset is in the future, buffer it */
+
+    /* check limit on total size used by all buffered frames, not actual data */
+    if (NGX_QUIC_MAX_BUFFERED - fs->total < f->length) {
+        ngx_log_error(NGX_LOG_INFO, c->log, 0,
+                      "ordered input buffer limit exceeded");
+        return NGX_ERROR;
+    }
+
+    dst = ngx_quic_alloc_frame(c, f->length);
+    if (dst == NULL) {
+        return NGX_ERROR;
+    }
+
+    data = dst->data;
+    ngx_memcpy(dst, frame, sizeof(ngx_quic_frame_t));
+    dst->data = data;
+
+    ngx_memcpy(dst->data, f->data, f->length);
+
+    df = &dst->u.ord;
+    df->data = dst->data;
+
+    fs->total += f->length;
+
+    ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
+                  "ordered frame with unexpected offset: buffered, total %ui",
+                  fs->total);
+
+    /* TODO: do we need some timeout for this queue ?  */
+
+    if (ngx_queue_empty(&fs->frames)) {
+        ngx_queue_insert_after(&fs->frames, &dst->queue);
+        return NGX_OK;
+    }
+
+    for (q = ngx_queue_last(&fs->frames);
+         q != ngx_queue_sentinel(&fs->frames);
+         q = ngx_queue_prev(q))
+    {
+        item = ngx_queue_data(q, ngx_quic_frame_t, queue);
+        f = &item->u.ord;
+
+        if (f->offset < df->offset) {
+            ngx_queue_insert_after(q, &dst->queue);
+            return NGX_OK;
+        }
+    }
+
+    ngx_queue_insert_after(&fs->frames, &dst->queue);
+
+    return NGX_OK;
+}
+
+
+static ngx_int_t
+ngx_quic_crypto_input(ngx_connection_t *c, ngx_quic_frame_t *frame)
+{
+    int                       sslerr;
+    ssize_t                   n;
+    ngx_ssl_conn_t           *ssl_conn;
+    ngx_quic_crypto_frame_t  *f;
+
+    f = &frame->u.crypto;
+
     ssl_conn = c->ssl->connection;
 
     ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
@@ -1401,15 +1650,13 @@ ngx_quic_handle_crypto_frame(ngx_connect
                    (int) SSL_quic_write_level(ssl_conn));
 
     if (!SSL_provide_quic_data(ssl_conn, SSL_quic_read_level(ssl_conn),
-                               f->data, f->len))
+                               f->data, f->length))
     {
         ngx_ssl_error(NGX_LOG_INFO, c->log, 0,
                       "SSL_provide_quic_data() failed");
         return NGX_ERROR;
     }
 
-    *curr_offset += f->len;
-
     n = SSL_do_handshake(ssl_conn);
 
     ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, "SSL_do_handshake: %d", n);