# HG changeset patch # User Vladimir Homutov # Date 1586855785 -10800 # Node ID 167d324767376de2e85dfcadb5a177ee139595f7 # Parent 6ad871b6342293606906909d360ffb2bf9243c46 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. diff --git a/src/event/ngx_event_quic.c b/src/event/ngx_event_quic.c --- 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); diff --git a/src/event/ngx_event_quic_transport.c b/src/event/ngx_event_quic_transport.c --- a/src/event/ngx_event_quic_transport.c +++ b/src/event/ngx_event_quic_transport.c @@ -593,14 +593,14 @@ ngx_quic_parse_frame(ngx_quic_header_t * return NGX_ERROR; } - p = ngx_quic_parse_int(p, end, &f->u.crypto.len); + p = ngx_quic_parse_int(p, end, &f->u.crypto.length); if (p == NULL) { ngx_log_error(NGX_LOG_INFO, pkt->log, 0, "failed to parse crypto frame len"); return NGX_ERROR; } - p = ngx_quic_read_bytes(p, end, f->u.crypto.len, &f->u.crypto.data); + p = ngx_quic_read_bytes(p, end, f->u.crypto.length, &f->u.crypto.data); if (p == NULL) { ngx_log_error(NGX_LOG_INFO, pkt->log, 0, "failed to parse crypto frame data"); @@ -609,11 +609,11 @@ ngx_quic_parse_frame(ngx_quic_header_t * ngx_log_debug3(NGX_LOG_DEBUG_EVENT, pkt->log, 0, "quic CRYPTO frame length: %uL off:%uL pp:%p", - f->u.crypto.len, f->u.crypto.offset, + f->u.crypto.length, f->u.crypto.offset, f->u.crypto.data); ngx_quic_hexdump0(pkt->log, "CRYPTO frame contents", - f->u.crypto.data, f->u.crypto.len); + f->u.crypto.data, f->u.crypto.length); break; case NGX_QUIC_FT_PADDING: @@ -1242,8 +1242,8 @@ ngx_quic_create_crypto(u_char *p, ngx_qu if (p == NULL) { len = ngx_quic_varint_len(NGX_QUIC_FT_CRYPTO); len += ngx_quic_varint_len(crypto->offset); - len += ngx_quic_varint_len(crypto->len); - len += crypto->len; + len += ngx_quic_varint_len(crypto->length); + len += crypto->length; return len; } @@ -1252,8 +1252,8 @@ ngx_quic_create_crypto(u_char *p, ngx_qu ngx_quic_build_int(&p, NGX_QUIC_FT_CRYPTO); ngx_quic_build_int(&p, crypto->offset); - ngx_quic_build_int(&p, crypto->len); - p = ngx_cpymem(p, crypto->data, crypto->len); + ngx_quic_build_int(&p, crypto->length); + p = ngx_cpymem(p, crypto->data, crypto->length); return p - start; } diff --git a/src/event/ngx_event_quic_transport.h b/src/event/ngx_event_quic_transport.h --- a/src/event/ngx_event_quic_transport.h +++ b/src/event/ngx_event_quic_transport.h @@ -111,13 +111,6 @@ typedef struct { typedef struct { - uint64_t offset; - uint64_t len; - u_char *data; -} ngx_quic_crypto_frame_t; - - -typedef struct { uint64_t seqnum; uint64_t retire; uint8_t len; @@ -126,15 +119,31 @@ typedef struct { } ngx_quic_new_conn_id_frame_t; +/* + * common layout for CRYPTO and STREAM frames; + * conceptually, CRYPTO frame is also a stream + * frame lacking some properties + */ typedef struct { + uint64_t offset; + uint64_t length; + u_char *data; +} ngx_quic_ordered_frame_t; + +typedef ngx_quic_ordered_frame_t ngx_quic_crypto_frame_t; + + +typedef struct { + /* initial fields same as in ngx_quic_ordered_frame_t */ + uint64_t offset; + uint64_t length; + u_char *data; + uint8_t type; uint64_t stream_id; - uint64_t offset; - uint64_t length; unsigned off:1; unsigned len:1; unsigned fin:1; - u_char *data; } ngx_quic_stream_frame_t; @@ -218,6 +227,7 @@ struct ngx_quic_frame_s { union { ngx_quic_ack_frame_t ack; ngx_quic_crypto_frame_t crypto; + ngx_quic_ordered_frame_t ord; ngx_quic_new_conn_id_frame_t ncid; ngx_quic_stream_frame_t stream; ngx_quic_max_data_frame_t max_data;