diff options
author | James M Snell <jasnell@gmail.com> | 2020-06-23 04:06:24 +0300 |
---|---|---|
committer | James M Snell <jasnell@gmail.com> | 2020-06-24 22:32:53 +0300 |
commit | 8a9763a8eacbe69cccc32aede6146b450eb75621 (patch) | |
tree | 0c804ffa3847d1159c151d2223819b4b3063ed19 | |
parent | 6b27d07779f95c5d079d4dd4103cc6c9116c1bc6 (diff) |
deps: update nghttp3
PR-URL: https://github.com/nodejs/node/pull/34033
Reviewed-By: Anna Henningsen <anna@addaleax.net>
Reviewed-By: Jiawen Geng <technicalcute@gmail.com>
Reviewed-By: Daniel Bevenius <daniel.bevenius@gmail.com>
-rw-r--r-- | deps/nghttp3/lib/includes/nghttp3/nghttp3.h | 202 | ||||
-rw-r--r-- | deps/nghttp3/lib/includes/nghttp3/version.h | 4 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_conn.c | 401 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_conn.h | 45 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_conv.c | 4 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_conv.h | 24 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_frame.h | 73 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_gaptr.c | 40 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_http.c | 109 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_ksl.c | 184 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_ksl.h | 33 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_qpack.c | 252 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_qpack.h | 83 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_stream.c | 78 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_stream.h | 37 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_tnode.c | 284 | ||||
-rw-r--r-- | deps/nghttp3/lib/nghttp3_tnode.h | 82 |
17 files changed, 889 insertions, 1046 deletions
diff --git a/deps/nghttp3/lib/includes/nghttp3/nghttp3.h b/deps/nghttp3/lib/includes/nghttp3/nghttp3.h index 5c3a95c4c6f..3ace46856b7 100644 --- a/deps/nghttp3/lib/includes/nghttp3/nghttp3.h +++ b/deps/nghttp3/lib/includes/nghttp3/nghttp3.h @@ -70,6 +70,11 @@ extern "C" { typedef ptrdiff_t nghttp3_ssize; +/* NGHTTP3_ALPN_H3 is a serialized form of HTTP/3 ALPN protocol + identifier this library supports. Notice that the first byte is + the length of the following protocol identifier. */ +#define NGHTTP3_ALPN_H3 "\x5h3-29" + typedef enum { NGHTTP3_ERR_INVALID_ARGUMENT = -101, NGHTTP3_ERR_NOBUF = -102, @@ -476,7 +481,8 @@ typedef enum { NGHTTP3_QPACK_TOKEN_TRANSFER_ENCODING, NGHTTP3_QPACK_TOKEN_UPGRADE, NGHTTP3_QPACK_TOKEN_TE, - NGHTTP3_QPACK_TOKEN__PROTOCOL + NGHTTP3_QPACK_TOKEN__PROTOCOL, + NGHTTP3_QPACK_TOKEN_PRIORITY } nghttp3_qpack_token; /** @@ -670,7 +676,7 @@ nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, */ NGHTTP3_EXTERN int nghttp3_qpack_encoder_add_insert_count(nghttp3_qpack_encoder *encoder, - size_t n); + uint64_t n); /** * @function @@ -748,7 +754,7 @@ nghttp3_qpack_stream_context_del(nghttp3_qpack_stream_context *sctx); * `nghttp3_qpack_stream_context_get_ricnt` returns required insert * count. */ -NGHTTP3_EXTERN size_t +NGHTTP3_EXTERN uint64_t nghttp3_qpack_stream_context_get_ricnt(nghttp3_qpack_stream_context *sctx); struct nghttp3_qpack_decoder; @@ -814,7 +820,7 @@ NGHTTP3_EXTERN nghttp3_ssize nghttp3_qpack_decoder_read_encoder( * * `nghttp3_qpack_decoder_get_icnt` returns insert count. */ -NGHTTP3_EXTERN size_t +NGHTTP3_EXTERN uint64_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder); /** @@ -863,7 +869,7 @@ typedef enum { * due to required insert count. * * When a header field is decoded, an application receives it in |nv|. - * nv->name and nv->value are reference counted buffer, and the their + * nv->name and nv->value are reference counted buffer, and their * reference counts are already incremented for application use. * Therefore, when application finishes processing the header field, * it must call nghttp3_rcbuf_decref(nv->name) and @@ -1201,7 +1207,7 @@ typedef struct { } nghttp3_conn_callbacks; typedef struct { - uint64_t max_header_list_size; + uint64_t max_field_section_size; uint64_t max_pushes; size_t qpack_max_table_capacity; size_t qpack_blocked_streams; @@ -1259,79 +1265,6 @@ NGHTTP3_EXTERN int nghttp3_conn_bind_qpack_streams(nghttp3_conn *conn, int64_t qenc_stream_id, int64_t qdec_stream_id); -typedef enum { - NGHTTP3_FRAME_DATA = 0x00, - NGHTTP3_FRAME_HEADERS = 0x01, - NGHTTP3_FRAME_CANCEL_PUSH = 0x03, - NGHTTP3_FRAME_SETTINGS = 0x04, - NGHTTP3_FRAME_PUSH_PROMISE = 0x05, - NGHTTP3_FRAME_GOAWAY = 0x07, - NGHTTP3_FRAME_MAX_PUSH_ID = 0x0d, -} nghttp3_frame_type; - -typedef struct { - int64_t type; - int64_t length; -} nghttp3_frame_hd; - -typedef struct { - nghttp3_frame_hd hd; -} nghttp3_frame_data; - -typedef struct { - nghttp3_frame_hd hd; - nghttp3_nv *nva; - size_t nvlen; -} nghttp3_frame_headers; - -typedef struct { - nghttp3_frame_hd hd; - int64_t push_id; -} nghttp3_frame_cancel_push; - -#define NGHTTP3_SETTINGS_ID_MAX_HEADER_LIST_SIZE 0x06 -#define NGHTTP3_SETTINGS_ID_QPACK_MAX_TABLE_CAPACITY 0x01 -#define NGHTTP3_SETTINGS_ID_QPACK_BLOCKED_STREAMS 0x07 - -typedef struct { - uint64_t id; - uint64_t value; -} nghttp3_settings_entry; - -typedef struct { - nghttp3_frame_hd hd; - size_t niv; - nghttp3_settings_entry iv[1]; -} nghttp3_frame_settings; - -typedef struct { - nghttp3_frame_hd hd; - nghttp3_nv *nva; - size_t nvlen; - int64_t push_id; -} nghttp3_frame_push_promise; - -typedef struct { - nghttp3_frame_hd hd; - int64_t stream_id; -} nghttp3_frame_goaway; - -typedef struct { - nghttp3_frame_hd hd; - int64_t push_id; -} nghttp3_frame_max_push_id; - -typedef union { - nghttp3_frame_hd hd; - nghttp3_frame_data data; - nghttp3_frame_headers headers; - nghttp3_frame_cancel_push cancel_push; - nghttp3_frame_settings settings; - nghttp3_frame_push_promise push_promise; - nghttp3_frame_goaway goaway; - nghttp3_frame_max_push_id max_push_id; -} nghttp3_frame; - /** * @function * @@ -1393,7 +1326,7 @@ NGHTTP3_EXTERN int nghttp3_conn_add_write_offset(nghttp3_conn *conn, * for stream denoted by |stream_id| QUIC stack has acknowledged. */ NGHTTP3_EXTERN int nghttp3_conn_add_ack_offset(nghttp3_conn *conn, - int64_t stream_id, size_t n); + int64_t stream_id, uint64_t n); /** * @function @@ -1653,6 +1586,96 @@ NGHTTP3_EXTERN int64_t nghttp3_conn_get_frame_payload_left(nghttp3_conn *conn, int64_t stream_id); /** + * @macro + * + * :macro:`NGHTTP3_DEFAULT_URGENCY` is the default urgency level. + */ +#define NGHTTP3_DEFAULT_URGENCY 1 + +/** + * @macro + * + * :macro:`NGHTTP3_URGENCY_HIGH` is the highest urgency level. + */ +#define NGHTTP3_URGENCY_HIGH 0 + +/** + * @macro + * + * :macro:`NGHTTP3_URGENCY_LOW` is the lowest urgency level. + */ +#define NGHTTP3_URGENCY_LOW 7 + +/** + * @macro + * + * :macro:`NGHTTP3_URGENCY_LEVELS` is the number of urgency levels. + */ +#define NGHTTP3_URGENCY_LEVELS (NGHTTP3_URGENCY_LOW + 1) + +/** + * @struct + * + * :type:`nghttp3_pri` represents HTTP priority. + */ +typedef struct nghttp3_pri { + /** + * urgency is the urgency of a stream, it must be in + * [NGHTTP3_URGENCY_HIGH, NGHTTP3_URGENCY_LOW], inclusive, and 0 is + * the highest urgency. + */ + uint32_t urgency; + /** + * inc indicates that a content can be processed incrementally or + * not. If inc is 0, it cannot be processed incrementally. If inc + * is 1, it can be processed incrementally. Other value is not + * permitted. + */ + int inc; +} nghttp3_pri; + +/** + * @function + * + * `nghttp3_conn_get_stream_priority` stores stream priority of a + * stream denoted by |stream_id| into |*dest|. Only server can use + * this function. + * + * This function must not be called if |conn| is initialized as + * client. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * :enum:`NGHTTP3_ERR_STREAM_NOT_FOUND` + * Stream not found. + */ +NGHTTP3_EXTERN int nghttp3_conn_get_stream_priority(nghttp3_conn *conn, + nghttp3_pri *dest, + int64_t stream_id); + +/** + * @function + * + * `nghttp3_conn_set_stream_priority` updates stream priority of a + * stream denoted by |stream_id| by the value pointed by |pri|. + * + * This function must not be called if |conn| is initialized as + * client. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * :enum:`NGHTTP3_ERR_STREAM_NOT_FOUND` + * Stream not found. + * :enum:`NGHTTP3_ERR_NOMEM` + * Out of memory. + */ +NGHTTP3_EXTERN int nghttp3_conn_set_stream_priority(nghttp3_conn *conn, + int64_t stream_id, + const nghttp3_pri *pri); + +/** * @function * * `nghttp3_conn_is_remote_qpack_encoder_stream` returns nonzero if a @@ -1711,6 +1734,25 @@ NGHTTP3_EXTERN int nghttp3_check_header_name(const uint8_t *name, size_t len); NGHTTP3_EXTERN int nghttp3_check_header_value(const uint8_t *value, size_t len); /** + * @function + * + * `nghttp3_http_parse_priority` parses priority HTTP header field + * stored in the buffer pointed by |value| of length |len|. If it + * successfully processed header field value, it stores the result + * into |*dest|. This function just overwrites what it sees in the + * header field value and does not initialize any field in |*dest|. + * + * This function returns 0 if it succeeds, or one of the following + * negative error codes: + * + * :enum:`NGHTTP3_ERR_INVALID_ARGUMENT` + * The function could not parse the provided value. + */ +NGHTTP3_EXTERN int nghttp3_http_parse_priority(nghttp3_pri *dest, + const uint8_t *value, + size_t len); + +/** * @macro * * The age of :type:`nghttp3_info` diff --git a/deps/nghttp3/lib/includes/nghttp3/version.h b/deps/nghttp3/lib/includes/nghttp3/version.h index 8f3108c95fd..69d29e9f140 100644 --- a/deps/nghttp3/lib/includes/nghttp3/version.h +++ b/deps/nghttp3/lib/includes/nghttp3/version.h @@ -31,7 +31,7 @@ * * Version number of the nghttp3 library release. */ -#define NGHTTP3_VERSION "0.1.90" +#define NGHTTP3_VERSION "0.1.0-DEV" /** * @macro @@ -41,6 +41,6 @@ * number, 8 bits for minor and 8 bits for patch. Version 1.2.3 * becomes 0x010203. */ -#define NGHTTP3_VERSION_NUM 0x00015a +#define NGHTTP3_VERSION_NUM 0x000100 #endif /* NGHTTP3_VERSION_H */ diff --git a/deps/nghttp3/lib/nghttp3_conn.c b/deps/nghttp3/lib/nghttp3_conn.c index 457cd5cb6d1..c3c1fb01a31 100644 --- a/deps/nghttp3/lib/nghttp3_conn.c +++ b/deps/nghttp3/lib/nghttp3_conn.c @@ -249,37 +249,36 @@ static int ricnt_less(const nghttp3_pq_entry *lhsx, return lhs->qpack_sctx.ricnt < rhs->qpack_sctx.ricnt; } +static int cycle_less(const nghttp3_pq_entry *lhsx, + const nghttp3_pq_entry *rhsx) { + const nghttp3_tnode *lhs = nghttp3_struct_of(lhsx, nghttp3_tnode, pe); + const nghttp3_tnode *rhs = nghttp3_struct_of(rhsx, nghttp3_tnode, pe); + + if (lhs->cycle == rhs->cycle) { + return lhs->seq < rhs->seq; + } + + return rhs->cycle - lhs->cycle <= NGHTTP3_TNODE_MAX_CYCLE_GAP; +} + static int conn_new(nghttp3_conn **pconn, int server, const nghttp3_conn_callbacks *callbacks, const nghttp3_conn_settings *settings, const nghttp3_mem *mem, void *user_data) { int rv; nghttp3_conn *conn; - nghttp3_node_id nid; + size_t i; conn = nghttp3_mem_calloc(mem, 1, sizeof(nghttp3_conn)); if (conn == NULL) { return NGHTTP3_ERR_NOMEM; } - nghttp3_tnode_init(&conn->root, - nghttp3_node_id_init(&nid, NGHTTP3_NODE_ID_TYPE_ROOT, 0), - 0, NGHTTP3_DEFAULT_WEIGHT, NULL, mem); - - nghttp3_tnode_init(&conn->orphan_root, - nghttp3_node_id_init(&nid, NGHTTP3_NODE_ID_TYPE_ROOT, 1), - 0, NGHTTP3_DEFAULT_WEIGHT, NULL, mem); - rv = nghttp3_map_init(&conn->streams, mem); if (rv != 0) { goto streams_init_fail; } - rv = nghttp3_map_init(&conn->placeholders, mem); - if (rv != 0) { - goto placeholders_init_fail; - } - rv = nghttp3_map_init(&conn->pushes, mem); if (rv != 0) { goto pushes_init_fail; @@ -299,6 +298,10 @@ static int conn_new(nghttp3_conn **pconn, int server, nghttp3_pq_init(&conn->qpack_blocked_streams, ricnt_less, mem); + for (i = 0; i < NGHTTP3_URGENCY_LEVELS; ++i) { + nghttp3_pq_init(&conn->sched[i].spq, cycle_less, mem); + } + rv = nghttp3_idtr_init(&conn->remote.bidi.idtr, server, mem); if (rv != 0) { goto remote_bidi_idtr_init_fail; @@ -330,8 +333,6 @@ qenc_init_fail: qdec_init_fail: nghttp3_map_free(&conn->pushes); pushes_init_fail: - nghttp3_map_free(&conn->placeholders); -placeholders_init_fail: nghttp3_map_free(&conn->streams); streams_init_fail: nghttp3_mem_free(mem, conn); @@ -378,15 +379,6 @@ static int free_push_promise(nghttp3_map_entry *ent, void *ptr) { return 0; } -static int free_placeholder(nghttp3_map_entry *ent, void *ptr) { - nghttp3_placeholder *ph = nghttp3_struct_of(ent, nghttp3_placeholder, me); - const nghttp3_mem *mem = ptr; - - nghttp3_placeholder_del(ph, mem); - - return 0; -} - static int free_stream(nghttp3_map_entry *ent, void *ptr) { nghttp3_stream *stream = nghttp3_struct_of(ent, nghttp3_stream, me); @@ -398,6 +390,8 @@ static int free_stream(nghttp3_map_entry *ent, void *ptr) { } void nghttp3_conn_del(nghttp3_conn *conn) { + size_t i; + if (conn == NULL) { return; } @@ -409,6 +403,10 @@ void nghttp3_conn_del(nghttp3_conn *conn) { nghttp3_idtr_free(&conn->remote.bidi.idtr); + for (i = 0; i < NGHTTP3_URGENCY_LEVELS; ++i) { + nghttp3_pq_free(&conn->sched[i].spq); + } + nghttp3_pq_free(&conn->qpack_blocked_streams); nghttp3_qpack_encoder_free(&conn->qenc); @@ -417,16 +415,9 @@ void nghttp3_conn_del(nghttp3_conn *conn) { nghttp3_map_each_free(&conn->pushes, free_push_promise, (void *)conn->mem); nghttp3_map_free(&conn->pushes); - nghttp3_map_each_free(&conn->placeholders, free_placeholder, - (void *)conn->mem); - nghttp3_map_free(&conn->placeholders); - nghttp3_map_each_free(&conn->streams, free_stream, NULL); nghttp3_map_free(&conn->streams); - nghttp3_tnode_free(&conn->orphan_root); - nghttp3_tnode_free(&conn->root); - nghttp3_mem_free(conn->mem, conn); } @@ -452,8 +443,7 @@ nghttp3_ssize nghttp3_conn_read_stream(nghttp3_conn *conn, int64_t stream_id, return 0; } - rv = nghttp3_conn_create_stream_dependency(conn, &stream, stream_id, 0, - NULL); + rv = nghttp3_conn_create_stream(conn, &stream, stream_id); } if (rv != 0) { return rv; @@ -466,8 +456,7 @@ nghttp3_ssize nghttp3_conn_read_stream(nghttp3_conn *conn, int64_t stream_id, return 0; } - rv = nghttp3_conn_create_stream_dependency(conn, &stream, stream_id, 0, - NULL); + rv = nghttp3_conn_create_stream(conn, &stream, stream_id); if (rv != 0) { return rv; } @@ -1411,6 +1400,25 @@ nghttp3_ssize nghttp3_conn_read_qpack_decoder(nghttp3_conn *conn, return nghttp3_qpack_encoder_read_decoder(&conn->qenc, src, srclen); } +static int conn_update_stream_priority(nghttp3_conn *conn, + nghttp3_stream *stream, uint8_t pri) { + if (stream->node.pri == pri) { + return 0; + } + + nghttp3_conn_unschedule_stream(conn, stream); + + stream->node.pri = pri; + + assert(nghttp3_stream_bidi_or_push(stream)); + + if (nghttp3_stream_require_schedule(stream)) { + return nghttp3_conn_schedule_stream(conn, stream); + } + + return 0; +} + nghttp3_ssize nghttp3_conn_read_bidi(nghttp3_conn *conn, size_t *pnproc, nghttp3_stream *stream, const uint8_t *src, size_t srclen, int fin) { @@ -1423,9 +1431,8 @@ nghttp3_ssize nghttp3_conn_read_bidi(nghttp3_conn *conn, size_t *pnproc, int busy = 0; size_t len; nghttp3_push_promise *pp; - nghttp3_push_promise fake_pp = { - {0}, {{0}, {0}, NULL, NULL, NULL, 0, {0}, 0, 0, 0, 0, 0}, {0}, NULL, -1, - 0}; + nghttp3_push_promise fake_pp = {{0}, {{0}, 0, {0}, 0, 0, 0}, {0}, NULL, -1, + 0}; if (stream->flags & NGHTTP3_STREAM_FLAG_QPACK_DECODE_BLOCKED) { *pnproc = 0; @@ -1784,6 +1791,15 @@ nghttp3_ssize nghttp3_conn_read_bidi(nghttp3_conn *conn, size_t *pnproc, switch (stream->rx.hstate) { case NGHTTP3_HTTP_STATE_REQ_HEADERS_BEGIN: + /* Only server utilizes priority information to schedule + streams. */ + if (conn->server) { + rv = conn_update_stream_priority(conn, stream, stream->rx.http.pri); + if (rv != 0) { + return rv; + } + } + /* fall through */ case NGHTTP3_HTTP_STATE_RESP_HEADERS_BEGIN: rv = conn_call_end_headers(conn, stream); break; @@ -1900,12 +1916,6 @@ int nghttp3_conn_on_push_promise_push_id(nghttp3_conn *conn, int64_t push_id, pp->stream_id = stream->node.nid.id; pp->flags |= NGHTTP3_PUSH_PROMISE_FLAG_BOUND; - - if (!(pp->flags & NGHTTP3_PUSH_PROMISE_FLAG_CANCELLED) && - pp->node.parent == &conn->orphan_root) { - nghttp3_tnode_remove(&pp->node); - nghttp3_tnode_insert(&pp->node, &stream->node); - } } else if (nghttp3_gaptr_is_pushed(push_idtr, (uint64_t)push_id, 1)) { return NGHTTP3_ERR_IGNORE_PUSH_PROMISE; } else { @@ -1914,8 +1924,7 @@ int nghttp3_conn_on_push_promise_push_id(nghttp3_conn *conn, int64_t push_id, return rv; } - rv = nghttp3_conn_create_push_promise( - conn, &pp, push_id, NGHTTP3_DEFAULT_WEIGHT, &stream->node); + rv = nghttp3_conn_create_push_promise(conn, &pp, push_id, &stream->node); if (rv != 0) { return rv; } @@ -1952,8 +1961,7 @@ int nghttp3_conn_on_client_cancel_push(nghttp3_conn *conn, return rv; } - rv = nghttp3_conn_create_push_promise( - conn, &pp, fr->push_id, NGHTTP3_DEFAULT_WEIGHT, &conn->orphan_root); + rv = nghttp3_conn_create_push_promise(conn, &pp, fr->push_id, NULL); if (rv != 0) { return rv; } @@ -1986,6 +1994,14 @@ int nghttp3_conn_on_client_cancel_push(nghttp3_conn *conn, return 0; } +static nghttp3_pq *conn_get_sched_pq(nghttp3_conn *conn, nghttp3_tnode *tnode) { + uint32_t urgency = nghttp3_pri_uint8_urgency(tnode->pri); + + assert(urgency < NGHTTP3_URGENCY_LEVELS); + + return &conn->sched[urgency].spq; +} + int nghttp3_conn_on_server_cancel_push(nghttp3_conn *conn, const nghttp3_frame_cancel_push *fr) { nghttp3_push_promise *pp; @@ -2018,10 +2034,7 @@ int nghttp3_conn_on_server_cancel_push(nghttp3_conn *conn, return 0; } - rv = nghttp3_tnode_squash(&pp->node); - if (rv != 0) { - return rv; - } + nghttp3_tnode_unschedule(&pp->node, conn_get_sched_pq(conn, &pp->node)); conn_delete_push_promise(conn, pp); @@ -2086,8 +2099,7 @@ int nghttp3_conn_on_stream_push_id(nghttp3_conn *conn, nghttp3_stream *stream, /* Don't know the associated stream of PUSH_PROMISE. It doesn't matter because client sends nothing to this stream. */ - rv = nghttp3_conn_create_push_promise( - conn, &pp, push_id, NGHTTP3_DEFAULT_WEIGHT, &conn->orphan_root); + rv = nghttp3_conn_create_push_promise(conn, &pp, push_id, NULL); if (rv != 0) { return rv; } @@ -2116,8 +2128,6 @@ static nghttp3_ssize conn_decode_headers(nghttp3_conn *conn, int trailers = 0; int ignore_pp = 0; - assert(srclen); - if (pp) { request = 1; ignore_pp = pp->stream_id != stream->node.nid.id; @@ -2257,8 +2267,8 @@ int nghttp3_conn_on_settings_entry_received(nghttp3_conn *conn, /* TODO Check for duplicates */ switch (ent->id) { - case NGHTTP3_SETTINGS_ID_MAX_HEADER_LIST_SIZE: - dest->max_header_list_size = ent->value; + case NGHTTP3_SETTINGS_ID_MAX_FIELD_SECTION_SIZE: + dest->max_field_section_size = ent->value; break; case NGHTTP3_SETTINGS_ID_QPACK_MAX_TABLE_CAPACITY: dest->qpack_max_table_capacity = (size_t)ent->value; @@ -2313,22 +2323,14 @@ static int conn_stream_acked_data(nghttp3_stream *stream, int64_t stream_id, int nghttp3_conn_create_stream(nghttp3_conn *conn, nghttp3_stream **pstream, int64_t stream_id) { - return nghttp3_conn_create_stream_dependency( - conn, pstream, stream_id, NGHTTP3_DEFAULT_WEIGHT, &conn->orphan_root); -} - -int nghttp3_conn_create_stream_dependency(nghttp3_conn *conn, - nghttp3_stream **pstream, - int64_t stream_id, uint32_t weight, - nghttp3_tnode *parent) { nghttp3_stream *stream; int rv; nghttp3_stream_callbacks callbacks = { conn_stream_acked_data, }; - rv = nghttp3_stream_new(&stream, stream_id, conn->next_seq, weight, parent, - &callbacks, conn->mem); + rv = nghttp3_stream_new(&stream, stream_id, conn->next_seq, &callbacks, + conn->mem); if (rv != 0) { return rv; } @@ -2347,39 +2349,14 @@ int nghttp3_conn_create_stream_dependency(nghttp3_conn *conn, return 0; } -int nghttp3_conn_create_placeholder(nghttp3_conn *conn, - nghttp3_placeholder **pph, int64_t ph_id, - uint32_t weight, nghttp3_tnode *parent) { - nghttp3_placeholder *ph; - int rv; - - rv = nghttp3_placeholder_new(&ph, ph_id, conn->next_seq, weight, parent, - conn->mem); - if (rv != 0) { - return rv; - } - - rv = nghttp3_map_insert(&conn->placeholders, &ph->me); - if (rv != 0) { - nghttp3_placeholder_del(ph, conn->mem); - return rv; - } - - ++conn->next_seq; - *pph = ph; - - return 0; -} - int nghttp3_conn_create_push_promise(nghttp3_conn *conn, nghttp3_push_promise **ppp, - int64_t push_id, uint32_t weight, - nghttp3_tnode *parent) { + int64_t push_id, nghttp3_tnode *parent) { nghttp3_push_promise *pp; int rv; - rv = nghttp3_push_promise_new(&pp, push_id, conn->next_seq, weight, parent, - conn->mem); + rv = + nghttp3_push_promise_new(&pp, push_id, conn->next_seq, parent, conn->mem); if (rv != 0) { return rv; } @@ -2408,18 +2385,6 @@ nghttp3_stream *nghttp3_conn_find_stream(nghttp3_conn *conn, return nghttp3_struct_of(me, nghttp3_stream, me); } -nghttp3_placeholder *nghttp3_conn_find_placeholder(nghttp3_conn *conn, - int64_t ph_id) { - nghttp3_map_entry *me; - - me = nghttp3_map_find(&conn->placeholders, (key_type)ph_id); - if (me == NULL) { - return NULL; - } - - return nghttp3_struct_of(me, nghttp3_placeholder, me); -} - nghttp3_push_promise *nghttp3_conn_find_push_promise(nghttp3_conn *conn, int64_t push_id) { nghttp3_map_entry *me; @@ -2444,7 +2409,7 @@ int nghttp3_conn_bind_control_stream(nghttp3_conn *conn, int64_t stream_id) { return NGHTTP3_ERR_INVALID_STATE; } - rv = nghttp3_conn_create_stream_dependency(conn, &stream, stream_id, 0, NULL); + rv = nghttp3_conn_create_stream(conn, &stream, stream_id); if (rv != 0) { return rv; } @@ -2478,8 +2443,7 @@ int nghttp3_conn_bind_qpack_streams(nghttp3_conn *conn, int64_t qenc_stream_id, return NGHTTP3_ERR_INVALID_STATE; } - rv = nghttp3_conn_create_stream_dependency(conn, &stream, qenc_stream_id, 0, - NULL); + rv = nghttp3_conn_create_stream(conn, &stream, qenc_stream_id); if (rv != 0) { return rv; } @@ -2493,8 +2457,7 @@ int nghttp3_conn_bind_qpack_streams(nghttp3_conn *conn, int64_t qenc_stream_id, return rv; } - rv = nghttp3_conn_create_stream_dependency(conn, &stream, qdec_stream_id, 0, - NULL); + rv = nghttp3_conn_create_stream(conn, &stream, qdec_stream_id); if (rv != 0) { return rv; } @@ -2613,27 +2576,33 @@ nghttp3_ssize nghttp3_conn_writev_stream(nghttp3_conn *conn, if (nghttp3_stream_bidi_or_push(stream) && !nghttp3_stream_require_schedule(stream)) { - nghttp3_stream_unschedule(stream); + nghttp3_conn_unschedule_stream(conn, stream); } return ncnt; } nghttp3_stream *nghttp3_conn_get_next_tx_stream(nghttp3_conn *conn) { - nghttp3_tnode *node = nghttp3_tnode_get_next(&conn->root); + size_t i; + nghttp3_tnode *tnode; + nghttp3_pq *pq; - if (node == NULL) { - node = nghttp3_tnode_get_next(&conn->orphan_root); - if (node == NULL) { - return NULL; + for (i = 0; i < NGHTTP3_URGENCY_LEVELS; ++i) { + pq = &conn->sched[i].spq; + if (nghttp3_pq_empty(pq)) { + continue; + } + + tnode = nghttp3_struct_of(nghttp3_pq_top(pq), nghttp3_tnode, pe); + + if (tnode->nid.type == NGHTTP3_NODE_ID_TYPE_PUSH) { + return nghttp3_struct_of(tnode, nghttp3_push_promise, node)->stream; } - } - if (node->nid.type == NGHTTP3_NODE_ID_TYPE_PUSH) { - return nghttp3_struct_of(node, nghttp3_push_promise, node)->stream; + return nghttp3_struct_of(tnode, nghttp3_stream, node); } - return nghttp3_struct_of(node, nghttp3_stream, node); + return NULL; } int nghttp3_conn_add_write_offset(nghttp3_conn *conn, int64_t stream_id, @@ -2651,18 +2620,25 @@ int nghttp3_conn_add_write_offset(nghttp3_conn *conn, int64_t stream_id, } stream->unscheduled_nwrite += n; - if (nghttp3_stream_bidi_or_push(stream)) { - if (nghttp3_stream_require_schedule(stream)) { - return nghttp3_stream_schedule(stream); - } - nghttp3_stream_unschedule(stream); + + if (!nghttp3_stream_bidi_or_push(stream)) { + return 0; } - return 0; + if (!nghttp3_stream_require_schedule(stream)) { + nghttp3_conn_unschedule_stream(conn, stream); + return 0; + } + + if (stream->unscheduled_nwrite < NGHTTP3_STREAM_MIN_WRITELEN) { + return 0; + } + + return nghttp3_conn_schedule_stream(conn, stream); } int nghttp3_conn_add_ack_offset(nghttp3_conn *conn, int64_t stream_id, - size_t n) { + uint64_t n) { nghttp3_stream *stream = nghttp3_conn_find_stream(conn, stream_id); if (stream == NULL) { @@ -2705,12 +2681,52 @@ static int conn_submit_headers_data(nghttp3_conn *conn, nghttp3_stream *stream, } if (nghttp3_stream_require_schedule(stream)) { - return nghttp3_stream_schedule(stream); + return nghttp3_conn_schedule_stream(conn, stream); } return 0; } +static nghttp3_tnode *stream_get_dependency_node(nghttp3_stream *stream) { + if (stream->pp) { + assert(stream->type == NGHTTP3_STREAM_TYPE_PUSH); + return &stream->pp->node; + } + + return &stream->node; +} + +int nghttp3_conn_schedule_stream(nghttp3_conn *conn, nghttp3_stream *stream) { + /* Assume that stream stays on the same urgency level */ + int rv; + + rv = nghttp3_tnode_schedule(stream_get_dependency_node(stream), + conn_get_sched_pq(conn, &stream->node), + stream->unscheduled_nwrite); + if (rv != 0) { + return rv; + } + + stream->unscheduled_nwrite = 0; + + return 0; +} + +int nghttp3_conn_ensure_stream_scheduled(nghttp3_conn *conn, + nghttp3_stream *stream) { + if (nghttp3_tnode_is_scheduled(stream_get_dependency_node(stream))) { + return 0; + } + + return nghttp3_conn_schedule_stream(conn, stream); +} + +void nghttp3_conn_unschedule_stream(nghttp3_conn *conn, + nghttp3_stream *stream) { + nghttp3_tnode_unschedule(stream_get_dependency_node(stream), + conn_get_sched_pq(conn, &stream->node)); +} + int nghttp3_conn_submit_request(nghttp3_conn *conn, int64_t stream_id, const nghttp3_nv *nva, size_t nvlen, const nghttp3_data_reader *dr, @@ -2835,8 +2851,7 @@ int nghttp3_conn_submit_push_promise(nghttp3_conn *conn, int64_t *ppush_id, push_id = conn->local.uni.next_push_id; - rv = nghttp3_conn_create_push_promise(conn, &pp, push_id, - NGHTTP3_DEFAULT_WEIGHT, &stream->node); + rv = nghttp3_conn_create_push_promise(conn, &pp, push_id, &stream->node); if (rv != 0) { return rv; } @@ -2862,7 +2877,7 @@ int nghttp3_conn_submit_push_promise(nghttp3_conn *conn, int64_t *ppush_id, *ppush_id = push_id; if (nghttp3_stream_require_schedule(stream)) { - return nghttp3_stream_schedule(stream); + return nghttp3_conn_schedule_stream(conn, stream); } return 0; @@ -2884,7 +2899,7 @@ int nghttp3_conn_bind_push_stream(nghttp3_conn *conn, int64_t push_id, assert(NULL == nghttp3_conn_find_stream(conn, stream_id)); - rv = nghttp3_conn_create_stream_dependency(conn, &stream, stream_id, 0, NULL); + rv = nghttp3_conn_create_stream(conn, &stream, stream_id); if (rv != 0) { return rv; } @@ -2921,23 +2936,26 @@ int nghttp3_conn_server_cancel_push(nghttp3_conn *conn, int64_t push_id) { return NGHTTP3_ERR_INVALID_ARGUMENT; } - if (pp->stream) { - return NGHTTP3_ERR_TOO_LATE; - } + if (!(pp->flags & NGHTTP3_PUSH_PROMISE_FLAG_SENT_CANCEL)) { + frent.fr.hd.type = NGHTTP3_FRAME_CANCEL_PUSH; + frent.fr.cancel_push.push_id = push_id; - frent.fr.hd.type = NGHTTP3_FRAME_CANCEL_PUSH; - frent.fr.cancel_push.push_id = push_id; + rv = nghttp3_stream_frq_add(conn->tx.ctrl, &frent); + if (rv != 0) { + return rv; + } - rv = nghttp3_stream_frq_add(conn->tx.ctrl, &frent); - if (rv != 0) { - return rv; + pp->flags |= NGHTTP3_PUSH_PROMISE_FLAG_SENT_CANCEL; } - rv = nghttp3_tnode_squash(&pp->node); - if (rv != 0) { - return rv; + if (pp->stream) { + /* CANCEL_PUSH will be sent, but it does not affect pushed stream. + Application should explicitly shutdown the stream. */ + return NGHTTP3_ERR_TOO_LATE; } + nghttp3_tnode_unschedule(&pp->node, conn_get_sched_pq(conn, &pp->node)); + conn_delete_push_promise(conn, pp); return 0; @@ -2983,9 +3001,10 @@ int nghttp3_conn_block_stream(nghttp3_conn *conn, int64_t stream_id) { } stream->flags |= NGHTTP3_STREAM_FLAG_FC_BLOCKED; + stream->unscheduled_nwrite = 0; if (nghttp3_stream_bidi_or_push(stream)) { - nghttp3_stream_unschedule(stream); + nghttp3_conn_unschedule_stream(conn, stream); } return 0; @@ -3002,7 +3021,7 @@ int nghttp3_conn_unblock_stream(nghttp3_conn *conn, int64_t stream_id) { if (nghttp3_stream_bidi_or_push(stream) && nghttp3_stream_require_schedule(stream)) { - return nghttp3_stream_ensure_scheduled(stream); + return nghttp3_conn_ensure_stream_scheduled(conn, stream); } return 0; @@ -3019,7 +3038,7 @@ int nghttp3_conn_resume_stream(nghttp3_conn *conn, int64_t stream_id) { if (nghttp3_stream_bidi_or_push(stream) && nghttp3_stream_require_schedule(stream)) { - return nghttp3_stream_ensure_scheduled(stream); + return nghttp3_conn_ensure_stream_scheduled(conn, stream); } return 0; @@ -3028,7 +3047,6 @@ int nghttp3_conn_resume_stream(nghttp3_conn *conn, int64_t stream_id) { int nghttp3_conn_close_stream(nghttp3_conn *conn, int64_t stream_id, uint64_t app_error_code) { nghttp3_stream *stream = nghttp3_conn_find_stream(conn, stream_id); - int rv; if (stream == NULL) { return NGHTTP3_ERR_STREAM_NOT_FOUND; @@ -3042,10 +3060,7 @@ int nghttp3_conn_close_stream(nghttp3_conn *conn, int64_t stream_id, stream->error_code = app_error_code; - rv = nghttp3_stream_squash(stream); - if (rv != 0) { - return rv; - } + nghttp3_conn_unschedule_stream(conn, stream); if (stream->qpack_blocked_pe.index == NGHTTP3_PQ_BAD_INDEX && (conn->server || !stream->pp || @@ -3138,59 +3153,59 @@ int64_t nghttp3_conn_get_frame_payload_left(nghttp3_conn *conn, return stream->rstate.left; } -int nghttp3_conn_is_remote_qpack_encoder_stream(nghttp3_conn *conn, - int64_t stream_id) { - nghttp3_stream *stream; +int nghttp3_conn_get_stream_priority(nghttp3_conn *conn, nghttp3_pri *dest, + int64_t stream_id) { + nghttp3_stream *stream = nghttp3_conn_find_stream(conn, stream_id); - if (!conn_remote_stream_uni(conn, stream_id)) { - return 0; + assert(conn->server); + + if (stream == NULL) { + return NGHTTP3_ERR_STREAM_NOT_FOUND; } - stream = nghttp3_conn_find_stream(conn, stream_id); - return stream && stream->type == NGHTTP3_STREAM_TYPE_QPACK_ENCODER; -} + dest->urgency = nghttp3_pri_uint8_urgency(stream->rx.http.pri); + dest->inc = nghttp3_pri_uint8_inc(stream->rx.http.pri); -void nghttp3_conn_settings_default(nghttp3_conn_settings *settings) { - memset(settings, 0, sizeof(nghttp3_conn_settings)); - settings->max_header_list_size = NGHTTP3_VARINT_MAX; + return 0; } -int nghttp3_placeholder_new(nghttp3_placeholder **pph, int64_t ph_id, - uint64_t seq, uint32_t weight, - nghttp3_tnode *parent, const nghttp3_mem *mem) { - nghttp3_placeholder *ph; - nghttp3_node_id nid; - - ph = nghttp3_mem_calloc(mem, 1, sizeof(nghttp3_placeholder)); - if (ph == NULL) { - return NGHTTP3_ERR_NOMEM; - } +int nghttp3_conn_set_stream_priority(nghttp3_conn *conn, int64_t stream_id, + const nghttp3_pri *pri) { + nghttp3_stream *stream = nghttp3_conn_find_stream(conn, stream_id); - nghttp3_tnode_init( - &ph->node, - nghttp3_node_id_init(&nid, NGHTTP3_NODE_ID_TYPE_PLACEHOLDER, ph_id), seq, - weight, parent, mem); + assert(conn->server); + assert(pri->urgency < NGHTTP3_URGENCY_LEVELS); + assert(pri->inc == 0 || pri->inc == 1); - ph->me.key = (key_type)ph_id; + if (stream == NULL) { + return NGHTTP3_ERR_STREAM_NOT_FOUND; + } - *pph = ph; + stream->rx.http.pri = nghttp3_pri_to_uint8(pri); - return 0; + return conn_update_stream_priority(conn, stream, stream->rx.http.pri); } -void nghttp3_placeholder_del(nghttp3_placeholder *ph, const nghttp3_mem *mem) { - if (ph == NULL) { - return; +int nghttp3_conn_is_remote_qpack_encoder_stream(nghttp3_conn *conn, + int64_t stream_id) { + nghttp3_stream *stream; + + if (!conn_remote_stream_uni(conn, stream_id)) { + return 0; } - nghttp3_tnode_free(&ph->node); + stream = nghttp3_conn_find_stream(conn, stream_id); + return stream && stream->type == NGHTTP3_STREAM_TYPE_QPACK_ENCODER; +} - nghttp3_mem_free(mem, ph); +void nghttp3_conn_settings_default(nghttp3_conn_settings *settings) { + memset(settings, 0, sizeof(nghttp3_conn_settings)); + settings->max_field_section_size = NGHTTP3_VARINT_MAX; } int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id, - uint64_t seq, uint32_t weight, - nghttp3_tnode *parent, const nghttp3_mem *mem) { + uint64_t seq, nghttp3_tnode *parent, + const nghttp3_mem *mem) { nghttp3_push_promise *pp; nghttp3_node_id nid; @@ -3201,14 +3216,16 @@ int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id, nghttp3_tnode_init( &pp->node, nghttp3_node_id_init(&nid, NGHTTP3_NODE_ID_TYPE_PUSH, push_id), - seq, weight, parent, mem); + seq, NGHTTP3_DEFAULT_URGENCY); pp->me.key = (key_type)push_id; pp->node.nid.id = push_id; pp->http.status_code = -1; pp->http.content_length = -1; - if (parent->nid.type == NGHTTP3_NODE_ID_TYPE_STREAM) { + if (parent) { + assert(parent->nid.type == NGHTTP3_NODE_ID_TYPE_STREAM); + pp->stream_id = parent->nid.id; pp->flags |= NGHTTP3_PUSH_PROMISE_FLAG_BOUND; } else { diff --git a/deps/nghttp3/lib/nghttp3_conn.h b/deps/nghttp3/lib/nghttp3_conn.h index a29aeb89f99..81f7a6e22c2 100644 --- a/deps/nghttp3/lib/nghttp3_conn.h +++ b/deps/nghttp3/lib/nghttp3_conn.h @@ -48,11 +48,6 @@ blocked streams for QPACK encoder. */ #define NGHTTP3_QPACK_ENCODER_MAX_BLOCK_STREAMS 100 -typedef struct { - nghttp3_map_entry me; - nghttp3_tnode node; -} nghttp3_placeholder; - typedef enum { NGHTTP3_PUSH_PROMISE_FLAG_NONE = 0x00, /* NGHTTP3_PUSH_PROMISE_FLAG_RECVED is set when PUSH_PROMISE is @@ -64,7 +59,7 @@ typedef enum { opened. */ NGHTTP3_PUSH_PROMISE_FLAG_RECV_CANCEL = 0x02, /* NGHTTP3_PUSH_PROMISE_FLAG_SENT_CANCEL is set when push is - canceled by client. */ + canceled by the local endpoint. */ NGHTTP3_PUSH_PROMISE_FLAG_SENT_CANCEL = 0x04, NGHTTP3_PUSH_PROMISE_FLAG_CANCELLED = NGHTTP3_PUSH_PROMISE_FLAG_RECV_CANCEL | NGHTTP3_PUSH_PROMISE_FLAG_SENT_CANCEL, @@ -114,15 +109,15 @@ typedef enum { } nghttp3_conn_flag; struct nghttp3_conn { - nghttp3_tnode root; - nghttp3_tnode orphan_root; nghttp3_conn_callbacks callbacks; nghttp3_map streams; - nghttp3_map placeholders; nghttp3_map pushes; nghttp3_qpack_decoder qdec; nghttp3_qpack_encoder qenc; nghttp3_pq qpack_blocked_streams; + struct { + nghttp3_pq spq; + } sched[NGHTTP3_URGENCY_LEVELS]; const nghttp3_mem *mem; void *user_data; int server; @@ -177,28 +172,15 @@ struct nghttp3_conn { nghttp3_stream *nghttp3_conn_find_stream(nghttp3_conn *conn, int64_t stream_id); -nghttp3_placeholder *nghttp3_conn_find_placeholder(nghttp3_conn *conn, - int64_t ph_id); - nghttp3_push_promise *nghttp3_conn_find_push_promise(nghttp3_conn *conn, int64_t push_id); int nghttp3_conn_create_stream(nghttp3_conn *conn, nghttp3_stream **pstream, int64_t stream_id); -int nghttp3_conn_create_stream_dependency(nghttp3_conn *conn, - nghttp3_stream **pstream, - int64_t stream_id, uint32_t weight, - nghttp3_tnode *parent); - -int nghttp3_conn_create_placeholder(nghttp3_conn *conn, - nghttp3_placeholder **pph, int64_t ph_id, - uint32_t weight, nghttp3_tnode *parent); - int nghttp3_conn_create_push_promise(nghttp3_conn *conn, nghttp3_push_promise **ppp, - int64_t push_id, uint32_t weight, - nghttp3_tnode *parent); + int64_t push_id, nghttp3_tnode *parent); nghttp3_ssize nghttp3_conn_read_bidi(nghttp3_conn *conn, size_t *pnproc, nghttp3_stream *stream, const uint8_t *src, @@ -258,21 +240,22 @@ int nghttp3_conn_client_cancel_push(nghttp3_conn *conn, int64_t push_id); int nghttp3_conn_submit_max_push_id(nghttp3_conn *conn); +int nghttp3_conn_schedule_stream(nghttp3_conn *conn, nghttp3_stream *stream); + +int nghttp3_conn_ensure_stream_scheduled(nghttp3_conn *conn, + nghttp3_stream *stream); + +void nghttp3_conn_unschedule_stream(nghttp3_conn *conn, nghttp3_stream *stream); + /* * nghttp3_conn_get_next_tx_stream returns next stream to send. It * returns NULL if there is no such stream. */ nghttp3_stream *nghttp3_conn_get_next_tx_stream(nghttp3_conn *conn); -int nghttp3_placeholder_new(nghttp3_placeholder **pph, int64_t ph_id, - uint64_t seq, uint32_t weight, - nghttp3_tnode *parent, const nghttp3_mem *mem); - -void nghttp3_placeholder_del(nghttp3_placeholder *ph, const nghttp3_mem *mem); - int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id, - uint64_t seq, uint32_t weight, - nghttp3_tnode *parent, const nghttp3_mem *mem); + uint64_t seq, nghttp3_tnode *parent, + const nghttp3_mem *mem); void nghttp3_push_promise_del(nghttp3_push_promise *pp, const nghttp3_mem *mem); diff --git a/deps/nghttp3/lib/nghttp3_conv.c b/deps/nghttp3/lib/nghttp3_conv.c index b8a7f8a4d0f..04bf6a0f298 100644 --- a/deps/nghttp3/lib/nghttp3_conv.c +++ b/deps/nghttp3/lib/nghttp3_conv.c @@ -128,3 +128,7 @@ size_t nghttp3_put_varint_len(int64_t n) { uint64_t nghttp3_ord_stream_id(int64_t stream_id) { return (uint64_t)(stream_id >> 2) + 1; } + +uint8_t nghttp3_pri_to_uint8(const nghttp3_pri *pri) { + return (uint8_t)((uint32_t)pri->inc << 7 | pri->urgency); +} diff --git a/deps/nghttp3/lib/nghttp3_conv.h b/deps/nghttp3/lib/nghttp3_conv.h index d14bdaa281b..309332defed 100644 --- a/deps/nghttp3/lib/nghttp3_conv.h +++ b/deps/nghttp3/lib/nghttp3_conv.h @@ -178,4 +178,28 @@ size_t nghttp3_put_varint_len(int64_t n); */ uint64_t nghttp3_ord_stream_id(int64_t stream_id); +/* + * NGHTTP3_PRI_INC_MASK is a bit mask to retrieve incremental bit from + * a value produced by nghttp3_pri_to_uint8. + */ +#define NGHTTP3_PRI_INC_MASK (1 << 7) + +/* + * nghttp3_pri_to_uint8 encodes |pri| into uint8_t variable. + */ +uint8_t nghttp3_pri_to_uint8(const nghttp3_pri *pri); + +/* + * nghttp3_pri_uint8_urgency extracts urgency from |PRI| which is + * supposed to be constructed by nghttp3_pri_to_uint8. + */ +#define nghttp3_pri_uint8_urgency(PRI) \ + ((uint32_t)((PRI) & ~NGHTTP3_PRI_INC_MASK)) + +/* + * nghttp3_pri_uint8_inc extracts inc from |PRI| which is supposed to + * be constructed by nghttp3_pri_to_uint8. + */ +#define nghttp3_pri_uint8_inc(PRI) (((PRI)&NGHTTP3_PRI_INC_MASK) != 0) + #endif /* NGHTTP3_CONV_H */ diff --git a/deps/nghttp3/lib/nghttp3_frame.h b/deps/nghttp3/lib/nghttp3_frame.h index d9245d9fb30..be333e95090 100644 --- a/deps/nghttp3/lib/nghttp3_frame.h +++ b/deps/nghttp3/lib/nghttp3_frame.h @@ -34,6 +34,79 @@ #include "nghttp3_buf.h" +typedef enum { + NGHTTP3_FRAME_DATA = 0x00, + NGHTTP3_FRAME_HEADERS = 0x01, + NGHTTP3_FRAME_CANCEL_PUSH = 0x03, + NGHTTP3_FRAME_SETTINGS = 0x04, + NGHTTP3_FRAME_PUSH_PROMISE = 0x05, + NGHTTP3_FRAME_GOAWAY = 0x07, + NGHTTP3_FRAME_MAX_PUSH_ID = 0x0d, +} nghttp3_frame_type; + +typedef struct { + int64_t type; + int64_t length; +} nghttp3_frame_hd; + +typedef struct { + nghttp3_frame_hd hd; +} nghttp3_frame_data; + +typedef struct { + nghttp3_frame_hd hd; + nghttp3_nv *nva; + size_t nvlen; +} nghttp3_frame_headers; + +typedef struct { + nghttp3_frame_hd hd; + int64_t push_id; +} nghttp3_frame_cancel_push; + +#define NGHTTP3_SETTINGS_ID_MAX_FIELD_SECTION_SIZE 0x06 +#define NGHTTP3_SETTINGS_ID_QPACK_MAX_TABLE_CAPACITY 0x01 +#define NGHTTP3_SETTINGS_ID_QPACK_BLOCKED_STREAMS 0x07 + +typedef struct { + uint64_t id; + uint64_t value; +} nghttp3_settings_entry; + +typedef struct { + nghttp3_frame_hd hd; + size_t niv; + nghttp3_settings_entry iv[1]; +} nghttp3_frame_settings; + +typedef struct { + nghttp3_frame_hd hd; + nghttp3_nv *nva; + size_t nvlen; + int64_t push_id; +} nghttp3_frame_push_promise; + +typedef struct { + nghttp3_frame_hd hd; + int64_t stream_id; +} nghttp3_frame_goaway; + +typedef struct { + nghttp3_frame_hd hd; + int64_t push_id; +} nghttp3_frame_max_push_id; + +typedef union { + nghttp3_frame_hd hd; + nghttp3_frame_data data; + nghttp3_frame_headers headers; + nghttp3_frame_cancel_push cancel_push; + nghttp3_frame_settings settings; + nghttp3_frame_push_promise push_promise; + nghttp3_frame_goaway goaway; + nghttp3_frame_max_push_id max_push_id; +} nghttp3_frame; + /* * nghttp3_frame_write_hd writes frame header |hd| to |dest|. This * function assumes that |dest| has enough space to write |hd|. diff --git a/deps/nghttp3/lib/nghttp3_gaptr.c b/deps/nghttp3/lib/nghttp3_gaptr.c index 7057cfde2cf..1faabbf09f8 100644 --- a/deps/nghttp3/lib/nghttp3_gaptr.c +++ b/deps/nghttp3/lib/nghttp3_gaptr.c @@ -33,7 +33,6 @@ int nghttp3_gaptr_init(nghttp3_gaptr *gaptr, const nghttp3_mem *mem) { int rv; nghttp3_range range = {0, UINT64_MAX}; - nghttp3_ksl_key key; rv = nghttp3_ksl_init(&gaptr->gap, nghttp3_ksl_range_compar, sizeof(nghttp3_range), mem); @@ -41,8 +40,7 @@ int nghttp3_gaptr_init(nghttp3_gaptr *gaptr, const nghttp3_mem *mem) { return rv; } - rv = nghttp3_ksl_insert(&gaptr->gap, NULL, nghttp3_ksl_key_ptr(&key, &range), - NULL); + rv = nghttp3_ksl_insert(&gaptr->gap, NULL, &range, NULL); if (rv != 0) { nghttp3_ksl_free(&gaptr->gap); return rv; @@ -65,38 +63,33 @@ int nghttp3_gaptr_push(nghttp3_gaptr *gaptr, uint64_t offset, size_t datalen) { int rv; nghttp3_range k, m, l, r, q = {offset, offset + datalen}; nghttp3_ksl_it it; - nghttp3_ksl_key key, old_key; - it = - nghttp3_ksl_lower_bound_compar(&gaptr->gap, nghttp3_ksl_key_ptr(&key, &q), - nghttp3_ksl_range_exclusive_compar); + it = nghttp3_ksl_lower_bound_compar(&gaptr->gap, &q, + nghttp3_ksl_range_exclusive_compar); for (; !nghttp3_ksl_it_end(&it);) { - k = *(nghttp3_range *)nghttp3_ksl_it_key(&it).ptr; + k = *(nghttp3_range *)nghttp3_ksl_it_key(&it); m = nghttp3_range_intersect(&q, &k); if (!nghttp3_range_len(&m)) { break; } if (nghttp3_range_eq(&k, &m)) { - nghttp3_ksl_remove(&gaptr->gap, &it, nghttp3_ksl_key_ptr(&key, &k)); + nghttp3_ksl_remove(&gaptr->gap, &it, &k); continue; } nghttp3_range_cut(&l, &r, &k, &m); if (nghttp3_range_len(&l)) { - nghttp3_ksl_update_key(&gaptr->gap, nghttp3_ksl_key_ptr(&old_key, &k), - nghttp3_ksl_key_ptr(&key, &l)); + nghttp3_ksl_update_key(&gaptr->gap, &k, &l); if (nghttp3_range_len(&r)) { - rv = nghttp3_ksl_insert(&gaptr->gap, &it, nghttp3_ksl_key_ptr(&key, &r), - NULL); + rv = nghttp3_ksl_insert(&gaptr->gap, &it, &r, NULL); if (rv != 0) { return rv; } } } else if (nghttp3_range_len(&r)) { - nghttp3_ksl_update_key(&gaptr->gap, nghttp3_ksl_key_ptr(&old_key, &k), - nghttp3_ksl_key_ptr(&key, &r)); + nghttp3_ksl_update_key(&gaptr->gap, &k, &r); } nghttp3_ksl_it_next(&it); } @@ -105,27 +98,22 @@ int nghttp3_gaptr_push(nghttp3_gaptr *gaptr, uint64_t offset, size_t datalen) { uint64_t nghttp3_gaptr_first_gap_offset(nghttp3_gaptr *gaptr) { nghttp3_ksl_it it = nghttp3_ksl_begin(&gaptr->gap); - nghttp3_range r = *(nghttp3_range *)nghttp3_ksl_it_key(&it).ptr; - return r.begin; + return ((nghttp3_range *)nghttp3_ksl_it_key(&it))->begin; } nghttp3_ksl_it nghttp3_gaptr_get_first_gap_after(nghttp3_gaptr *gaptr, uint64_t offset) { nghttp3_range q = {offset, offset + 1}; - nghttp3_ksl_key key; - return nghttp3_ksl_lower_bound_compar(&gaptr->gap, - nghttp3_ksl_key_ptr(&key, &q), + return nghttp3_ksl_lower_bound_compar(&gaptr->gap, &q, nghttp3_ksl_range_exclusive_compar); } int nghttp3_gaptr_is_pushed(nghttp3_gaptr *gaptr, uint64_t offset, size_t datalen) { - nghttp3_ksl_key key; nghttp3_range q = {offset, offset + datalen}; - nghttp3_ksl_it it = - nghttp3_ksl_lower_bound_compar(&gaptr->gap, nghttp3_ksl_key_ptr(&key, &q), - nghttp3_ksl_range_exclusive_compar); - nghttp3_range k = *(nghttp3_range *)nghttp3_ksl_it_key(&it).ptr; - nghttp3_range m = nghttp3_range_intersect(&q, &k); + nghttp3_ksl_it it = nghttp3_ksl_lower_bound_compar( + &gaptr->gap, &q, nghttp3_ksl_range_exclusive_compar); + nghttp3_range m = + nghttp3_range_intersect(&q, (nghttp3_range *)nghttp3_ksl_it_key(&it)); return nghttp3_range_len(&m) == 0; } diff --git a/deps/nghttp3/lib/nghttp3_http.c b/deps/nghttp3/lib/nghttp3_http.c index c66d9c9d306..dc84c16b5d8 100644 --- a/deps/nghttp3/lib/nghttp3_http.c +++ b/deps/nghttp3/lib/nghttp3_http.c @@ -30,6 +30,7 @@ #include "nghttp3_stream.h" #include "nghttp3_macro.h" +#include "nghttp3_conv.h" static uint8_t downcase(uint8_t c) { return 'A' <= c && c <= 'Z' ? (uint8_t)(c - 'A' + 'a') : c; @@ -112,9 +113,95 @@ static int check_path(nghttp3_http_state *http) { (http->flags & NGHTTP3_HTTP_FLAG_PATH_ASTERISK))); } +int nghttp3_http_parse_priority(nghttp3_pri *dest, const uint8_t *value, + size_t len) { + nghttp3_pri pri = *dest; + const uint8_t *p = value, *end = value + len; + + for (;;) { + for (; p != end && (*p == ' ' || *p == '\t'); ++p) + ; + + if (p == end) { + break; + } + + switch (*p) { + case 'u': + ++p; + + if (p + 2 > end || *p++ != '=') { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + if (!('0' <= *p && *p <= '7')) { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + pri.urgency = (uint32_t)(*p++ - '0'); + + if (p == end) { + goto fin; + } + + if (*p++ != ',') { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + break; + case 'i': + ++p; + + if (p == end) { + pri.inc = 1; + goto fin; + } + + if (*p == ',') { + pri.inc = 1; + ++p; + break; + } + + if (p + 3 > end || *p != '=' || *(p + 1) != '?' || + (*(p + 2) != '0' && *(p + 2) != '1')) { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + pri.inc = *(p + 2) == '1'; + + p += 3; + + if (p == end) { + goto fin; + } + + if (*p++ != ',') { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + break; + default: + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + + if (p == end) { + return NGHTTP3_ERR_INVALID_ARGUMENT; + } + } + +fin: + + *dest = pri; + + return 0; +} + static int http_request_on_header(nghttp3_http_state *http, int64_t frame_type, nghttp3_qpack_nv *nv, int trailers, int connect_protocol) { + nghttp3_pri pri; + if (nv->name->base[0] == ':') { if (trailers || (http->flags & NGHTTP3_HTTP_FLAG_PSEUDO_HEADER_DISALLOWED)) { @@ -192,6 +279,13 @@ static int http_request_on_header(nghttp3_http_state *http, int64_t frame_type, } break; case NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH: { + /* https://tools.ietf.org/html/rfc7230#section-4.1.2: A sender + MUST NOT generate a trailer that contains a field necessary for + message framing (e.g., Transfer-Encoding and Content-Length), + ... */ + if (trailers) { + return NGHTTP3_ERR_REMOVE_HTTP_HEADER; + } if (http->content_length != -1) { return NGHTTP3_ERR_MALFORMED_HTTP_HEADER; } @@ -213,6 +307,14 @@ static int http_request_on_header(nghttp3_http_state *http, int64_t frame_type, return NGHTTP3_ERR_MALFORMED_HTTP_HEADER; } break; + case NGHTTP3_QPACK_TOKEN_PRIORITY: + pri.urgency = nghttp3_pri_uint8_urgency(http->pri); + pri.inc = nghttp3_pri_uint8_inc(http->pri); + if (nghttp3_http_parse_priority(&pri, nv->value->base, nv->value->len) == + 0) { + http->pri = nghttp3_pri_to_uint8(&pri); + } + break; default: if (nv->name->base[0] == ':') { return NGHTTP3_ERR_MALFORMED_HTTP_HEADER; @@ -250,6 +352,13 @@ static int http_response_on_header(nghttp3_http_state *http, break; } case NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH: { + /* https://tools.ietf.org/html/rfc7230#section-4.1.2: A sender + MUST NOT generate a trailer that contains a field necessary for + message framing (e.g., Transfer-Encoding and Content-Length), + ... */ + if (trailers) { + return NGHTTP3_ERR_REMOVE_HTTP_HEADER; + } if (http->status_code == 204) { /* content-length header field in 204 response is prohibited by RFC 7230. But some widely used servers send content-length: diff --git a/deps/nghttp3/lib/nghttp3_ksl.c b/deps/nghttp3/lib/nghttp3_ksl.c index 35bae07d1e7..958b03973c3 100644 --- a/deps/nghttp3/lib/nghttp3_ksl.c +++ b/deps/nghttp3/lib/nghttp3_ksl.c @@ -49,30 +49,7 @@ static size_t ksl_blklen(size_t nodelen) { */ static void ksl_node_set_key(nghttp3_ksl *ksl, nghttp3_ksl_node *node, const void *key) { - memcpy(&node->key, key, ksl->keylen); -} - -/* - * ksl_node_key assigns the pointer to key of |node| to key->ptr and - * returns |key|. - */ -static nghttp3_ksl_key *ksl_node_key(nghttp3_ksl_key *key, - nghttp3_ksl_node *node) { - key->ptr = &node->key; - return key; -} - -/* - * ksl_nth_node returns |n|th node under |blk|. - */ -static nghttp3_ksl_node *ksl_nth_node(const nghttp3_ksl *ksl, - nghttp3_ksl_blk *blk, size_t n) { - return (nghttp3_ksl_node *)(void *)(blk->nodes + ksl->nodelen * n); -} - -nghttp3_ksl_node *nghttp3_ksl_nth_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, - size_t n) { - return ksl_nth_node(ksl, blk, n); + memcpy(node->key, key, ksl->keylen); } int nghttp3_ksl_init(nghttp3_ksl *ksl, nghttp3_ksl_compar compar, size_t keylen, @@ -108,7 +85,7 @@ static void ksl_free_blk(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk) { if (!blk->leaf) { for (i = 0; i < blk->n; ++i) { - ksl_free_blk(ksl, ksl_nth_node(ksl, blk, i)->blk); + ksl_free_blk(ksl, nghttp3_ksl_nth_node(ksl, blk, i)->blk); } } @@ -175,7 +152,7 @@ static nghttp3_ksl_blk *ksl_split_blk(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk) { */ static int ksl_split_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) { nghttp3_ksl_node *node; - nghttp3_ksl_blk *lblk = ksl_nth_node(ksl, blk, i)->blk, *rblk; + nghttp3_ksl_blk *lblk = nghttp3_ksl_nth_node(ksl, blk, i)->blk, *rblk; rblk = ksl_split_blk(ksl, lblk); if (rblk == NULL) { @@ -186,13 +163,15 @@ static int ksl_split_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) { blk->nodes + (i + 1) * ksl->nodelen, ksl->nodelen * (blk->n - (i + 1))); - node = ksl_nth_node(ksl, blk, i + 1); + node = nghttp3_ksl_nth_node(ksl, blk, i + 1); node->blk = rblk; ++blk->n; - ksl_node_set_key(ksl, node, &ksl_nth_node(ksl, rblk, rblk->n - 1)->key); + ksl_node_set_key(ksl, node, + nghttp3_ksl_nth_node(ksl, rblk, rblk->n - 1)->key); - node = ksl_nth_node(ksl, blk, i); - ksl_node_set_key(ksl, node, &ksl_nth_node(ksl, lblk, lblk->n - 1)->key); + node = nghttp3_ksl_nth_node(ksl, blk, i); + ksl_node_set_key(ksl, node, + nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); return 0; } @@ -227,12 +206,14 @@ static int ksl_split_head(nghttp3_ksl *ksl) { nhead->n = 2; nhead->leaf = 0; - node = ksl_nth_node(ksl, nhead, 0); - ksl_node_set_key(ksl, node, &ksl_nth_node(ksl, lblk, lblk->n - 1)->key); + node = nghttp3_ksl_nth_node(ksl, nhead, 0); + ksl_node_set_key(ksl, node, + nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); node->blk = lblk; - node = ksl_nth_node(ksl, nhead, 1); - ksl_node_set_key(ksl, node, &ksl_nth_node(ksl, rblk, rblk->n - 1)->key); + node = nghttp3_ksl_nth_node(ksl, nhead, 1); + ksl_node_set_key(ksl, node, + nghttp3_ksl_nth_node(ksl, rblk, rblk->n - 1)->key); node->blk = rblk; ksl->head = nhead; @@ -255,8 +236,8 @@ static void ksl_insert_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i, memmove(blk->nodes + (i + 1) * ksl->nodelen, blk->nodes + i * ksl->nodelen, ksl->nodelen * (blk->n - i)); - node = ksl_nth_node(ksl, blk, i); - ksl_node_set_key(ksl, node, key->ptr); + node = nghttp3_ksl_nth_node(ksl, blk, i); + ksl_node_set_key(ksl, node, key); node->data = data; ++blk->n; @@ -267,12 +248,11 @@ static size_t ksl_bsearch(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, nghttp3_ksl_compar compar) { nghttp3_ssize left = -1, right = (nghttp3_ssize)blk->n, mid; nghttp3_ksl_node *node; - nghttp3_ksl_key node_key; while (right - left > 1) { mid = (left + right) / 2; - node = ksl_nth_node(ksl, blk, (size_t)mid); - if (compar(ksl_node_key(&node_key, node), key)) { + node = nghttp3_ksl_nth_node(ksl, blk, (size_t)mid); + if (compar((nghttp3_ksl_key *)node->key, key)) { left = mid; } else { right = mid; @@ -286,7 +266,6 @@ int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it, const nghttp3_ksl_key *key, void *data) { nghttp3_ksl_blk *blk = ksl->head; nghttp3_ksl_node *node; - nghttp3_ksl_key node_key; size_t i; int rv; @@ -313,15 +292,15 @@ int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it, if (i == blk->n) { /* This insertion extends the largest key in this subtree. */ for (; !blk->leaf;) { - node = ksl_nth_node(ksl, blk, blk->n - 1); + node = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1); if (node->blk->n == NGHTTP3_KSL_MAX_NBLK) { rv = ksl_split_node(ksl, blk, blk->n - 1); if (rv != 0) { return rv; } - node = ksl_nth_node(ksl, blk, blk->n - 1); + node = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1); } - ksl_node_set_key(ksl, node, key->ptr); + ksl_node_set_key(ksl, node, key); blk = node->blk; } ksl_insert_node(ksl, blk, blk->n, key, data); @@ -332,17 +311,17 @@ int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it, return 0; } - node = ksl_nth_node(ksl, blk, i); + node = nghttp3_ksl_nth_node(ksl, blk, i); if (node->blk->n == NGHTTP3_KSL_MAX_NBLK) { rv = ksl_split_node(ksl, blk, i); if (rv != 0) { return rv; } - if (ksl->compar(ksl_node_key(&node_key, node), key)) { - node = ksl_nth_node(ksl, blk, i + 1); - if (ksl->compar(ksl_node_key(&node_key, node), key)) { - ksl_node_set_key(ksl, node, key->ptr); + if (ksl->compar((nghttp3_ksl_key *)node->key, key)) { + node = nghttp3_ksl_nth_node(ksl, blk, i + 1); + if (ksl->compar((nghttp3_ksl_key *)node->key, key)) { + ksl_node_set_key(ksl, node, key); } } } @@ -378,8 +357,8 @@ static nghttp3_ksl_blk *ksl_merge_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, assert(i + 1 < blk->n); - lblk = ksl_nth_node(ksl, blk, i)->blk; - rblk = ksl_nth_node(ksl, blk, i + 1)->blk; + lblk = nghttp3_ksl_nth_node(ksl, blk, i)->blk; + rblk = nghttp3_ksl_nth_node(ksl, blk, i + 1)->blk; assert(lblk->n + rblk->n < NGHTTP3_KSL_MAX_NBLK); @@ -401,8 +380,8 @@ static nghttp3_ksl_blk *ksl_merge_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, ksl->head = lblk; } else { ksl_remove_node(ksl, blk, i + 1); - ksl_node_set_key(ksl, ksl_nth_node(ksl, blk, i), - &ksl_nth_node(ksl, lblk, lblk->n - 1)->key); + ksl_node_set_key(ksl, nghttp3_ksl_nth_node(ksl, blk, i), + nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); } return lblk; @@ -417,17 +396,17 @@ static void ksl_shift_left(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) { assert(i > 0); - lnode = ksl_nth_node(ksl, blk, i - 1); - rnode = ksl_nth_node(ksl, blk, i); + lnode = nghttp3_ksl_nth_node(ksl, blk, i - 1); + rnode = nghttp3_ksl_nth_node(ksl, blk, i); assert(lnode->blk->n < NGHTTP3_KSL_MAX_NBLK); assert(rnode->blk->n > NGHTTP3_KSL_MIN_NBLK); - dest = ksl_nth_node(ksl, lnode->blk, lnode->blk->n); - src = ksl_nth_node(ksl, rnode->blk, 0); + dest = nghttp3_ksl_nth_node(ksl, lnode->blk, lnode->blk->n); + src = nghttp3_ksl_nth_node(ksl, rnode->blk, 0); memcpy(dest, src, ksl->nodelen); - ksl_node_set_key(ksl, lnode, &dest->key); + ksl_node_set_key(ksl, lnode, dest->key); ++lnode->blk->n; --rnode->blk->n; @@ -444,8 +423,8 @@ static void ksl_shift_right(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) { assert(i < blk->n - 1); - lnode = ksl_nth_node(ksl, blk, i); - rnode = ksl_nth_node(ksl, blk, i + 1); + lnode = nghttp3_ksl_nth_node(ksl, blk, i); + rnode = nghttp3_ksl_nth_node(ksl, blk, i + 1); assert(lnode->blk->n > NGHTTP3_KSL_MIN_NBLK); assert(rnode->blk->n < NGHTTP3_KSL_MAX_NBLK); @@ -454,14 +433,15 @@ static void ksl_shift_right(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) { ksl->nodelen * rnode->blk->n); ++rnode->blk->n; - dest = ksl_nth_node(ksl, rnode->blk, 0); - src = ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1); + dest = nghttp3_ksl_nth_node(ksl, rnode->blk, 0); + src = nghttp3_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1); memcpy(dest, src, ksl->nodelen); --lnode->blk->n; - ksl_node_set_key(ksl, lnode, - &ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key); + ksl_node_set_key( + ksl, lnode, + nghttp3_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key); } /* @@ -480,8 +460,8 @@ void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it, size_t i; if (!blk->leaf && blk->n == 2 && - ksl_nth_node(ksl, blk, 0)->blk->n == NGHTTP3_KSL_MIN_NBLK && - ksl_nth_node(ksl, blk, 1)->blk->n == NGHTTP3_KSL_MIN_NBLK) { + nghttp3_ksl_nth_node(ksl, blk, 0)->blk->n == NGHTTP3_KSL_MIN_NBLK && + nghttp3_ksl_nth_node(ksl, blk, 1)->blk->n == NGHTTP3_KSL_MIN_NBLK) { blk = ksl_merge_node(ksl, ksl->head, 0); } @@ -504,15 +484,18 @@ void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it, return; } - node = ksl_nth_node(ksl, blk, i); + node = nghttp3_ksl_nth_node(ksl, blk, i); if (node->blk->n == NGHTTP3_KSL_MIN_NBLK) { - if (i > 0 && - ksl_nth_node(ksl, blk, i - 1)->blk->n > NGHTTP3_KSL_MIN_NBLK) { + if (i > 0 && nghttp3_ksl_nth_node(ksl, blk, i - 1)->blk->n > + NGHTTP3_KSL_MIN_NBLK) { ksl_shift_right(ksl, blk, i - 1); + blk = node->blk; } else if (i + 1 < blk->n && - ksl_nth_node(ksl, blk, i + 1)->blk->n > NGHTTP3_KSL_MIN_NBLK) { + nghttp3_ksl_nth_node(ksl, blk, i + 1)->blk->n > + NGHTTP3_KSL_MIN_NBLK) { ksl_shift_left(ksl, blk, i + 1); + blk = node->blk; } else if (i > 0) { blk = ksl_merge_node(ksl, blk, i - 1); } else { @@ -546,7 +529,7 @@ nghttp3_ksl_it nghttp3_ksl_lower_bound(nghttp3_ksl *ksl, if (i == blk->n) { /* This happens if descendant has smaller key. Fast forward to find last node in this subtree. */ - for (; !blk->leaf; blk = ksl_nth_node(ksl, blk, blk->n - 1)->blk) + for (; !blk->leaf; blk = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1)->blk) ; if (blk->next) { blk = blk->next; @@ -557,7 +540,7 @@ nghttp3_ksl_it nghttp3_ksl_lower_bound(nghttp3_ksl *ksl, nghttp3_ksl_it_init(&it, ksl, blk, i); return it; } - blk = ksl_nth_node(ksl, blk, i)->blk; + blk = nghttp3_ksl_nth_node(ksl, blk, i)->blk; } } @@ -583,7 +566,7 @@ nghttp3_ksl_it nghttp3_ksl_lower_bound_compar(nghttp3_ksl *ksl, if (i == blk->n) { /* This happens if descendant has smaller key. Fast forward to find last node in this subtree. */ - for (; !blk->leaf; blk = ksl_nth_node(ksl, blk, blk->n - 1)->blk) + for (; !blk->leaf; blk = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1)->blk) ; if (blk->next) { blk = blk->next; @@ -594,7 +577,7 @@ nghttp3_ksl_it nghttp3_ksl_lower_bound_compar(nghttp3_ksl *ksl, nghttp3_ksl_it_init(&it, ksl, blk, i); return it; } - blk = ksl_nth_node(ksl, blk, i)->blk; + blk = nghttp3_ksl_nth_node(ksl, blk, i)->blk; } } @@ -602,25 +585,23 @@ void nghttp3_ksl_update_key(nghttp3_ksl *ksl, const nghttp3_ksl_key *old_key, const nghttp3_ksl_key *new_key) { nghttp3_ksl_blk *blk = ksl->head; nghttp3_ksl_node *node; - nghttp3_ksl_key node_key; size_t i; for (;;) { i = ksl_bsearch(ksl, blk, old_key, ksl->compar); assert(i < blk->n); - node = ksl_nth_node(ksl, blk, i); + node = nghttp3_ksl_nth_node(ksl, blk, i); if (blk->leaf) { - assert(key_equal(ksl->compar, ksl_node_key(&node_key, node), old_key)); - ksl_node_set_key(ksl, node, new_key->ptr); + assert(key_equal(ksl->compar, (nghttp3_ksl_key *)node->key, old_key)); + ksl_node_set_key(ksl, node, new_key); return; } - ksl_node_key(&node_key, node); - if (key_equal(ksl->compar, &node_key, old_key) || - ksl->compar(&node_key, new_key)) { - ksl_node_set_key(ksl, node, new_key->ptr); + if (key_equal(ksl->compar, (nghttp3_ksl_key *)node->key, old_key) || + ksl->compar((nghttp3_ksl_key *)node->key, new_key)) { + ksl_node_set_key(ksl, node, new_key); } blk = node->blk; @@ -630,21 +611,20 @@ void nghttp3_ksl_update_key(nghttp3_ksl *ksl, const nghttp3_ksl_key *old_key, static void ksl_print(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t level) { size_t i; nghttp3_ksl_node *node; - nghttp3_ksl_key node_key; fprintf(stderr, "LV=%zu n=%zu\n", level, blk->n); if (blk->leaf) { for (i = 0; i < blk->n; ++i) { - node = ksl_nth_node(ksl, blk, i); - fprintf(stderr, " %" PRId64, *ksl_node_key(&node_key, node)->i); + node = nghttp3_ksl_nth_node(ksl, blk, i); + fprintf(stderr, " %" PRId64, *(int64_t *)(void *)node->key); } fprintf(stderr, "\n"); return; } for (i = 0; i < blk->n; ++i) { - ksl_print(ksl, ksl_nth_node(ksl, blk, i)->blk, level + 1); + ksl_print(ksl, nghttp3_ksl_nth_node(ksl, blk, i)->blk, level + 1); } } @@ -656,7 +636,7 @@ void nghttp3_ksl_clear(nghttp3_ksl *ksl) { if (!ksl->head->leaf) { for (i = 0; i < ksl->head->n; ++i) { - ksl_free_blk(ksl, ksl_nth_node(ksl, ksl->head, i)->blk); + ksl_free_blk(ksl, nghttp3_ksl_nth_node(ksl, ksl->head, i)->blk); } } @@ -693,16 +673,7 @@ void nghttp3_ksl_it_init(nghttp3_ksl_it *it, const nghttp3_ksl *ksl, void *nghttp3_ksl_it_get(const nghttp3_ksl_it *it) { assert(it->i < it->blk->n); - return ksl_nth_node(it->ksl, it->blk, it->i)->data; -} - -void nghttp3_ksl_it_next(nghttp3_ksl_it *it) { - assert(!nghttp3_ksl_it_end(it)); - - if (++it->i == it->blk->n && it->blk->next) { - it->blk = it->blk->next; - it->i = 0; - } + return nghttp3_ksl_nth_node(it->ksl, it->blk, it->i)->data; } void nghttp3_ksl_it_prev(nghttp3_ksl_it *it) { @@ -716,36 +687,19 @@ void nghttp3_ksl_it_prev(nghttp3_ksl_it *it) { } } -int nghttp3_ksl_it_end(const nghttp3_ksl_it *it) { - return it->blk->n == it->i && it->blk->next == NULL; -} - int nghttp3_ksl_it_begin(const nghttp3_ksl_it *it) { return it->i == 0 && it->blk->prev == NULL; } -nghttp3_ksl_key nghttp3_ksl_it_key(const nghttp3_ksl_it *it) { - nghttp3_ksl_key node_key; - - assert(it->i < it->blk->n); - - return *ksl_node_key(&node_key, ksl_nth_node(it->ksl, it->blk, it->i)); -} - -nghttp3_ksl_key *nghttp3_ksl_key_ptr(nghttp3_ksl_key *key, const void *ptr) { - key->ptr = ptr; - return key; -} - int nghttp3_ksl_range_compar(const nghttp3_ksl_key *lhs, const nghttp3_ksl_key *rhs) { - const nghttp3_range *a = lhs->ptr, *b = rhs->ptr; + const nghttp3_range *a = lhs, *b = rhs; return a->begin < b->begin; } int nghttp3_ksl_range_exclusive_compar(const nghttp3_ksl_key *lhs, const nghttp3_ksl_key *rhs) { - const nghttp3_range *a = lhs->ptr, *b = rhs->ptr; + const nghttp3_range *a = lhs, *b = rhs; return a->begin < b->begin && !(nghttp3_max(a->begin, b->begin) < nghttp3_min(a->end, b->end)); } diff --git a/deps/nghttp3/lib/nghttp3_ksl.h b/deps/nghttp3/lib/nghttp3_ksl.h index 89ca732aeb6..88c636b0c1d 100644 --- a/deps/nghttp3/lib/nghttp3_ksl.h +++ b/deps/nghttp3/lib/nghttp3_ksl.h @@ -38,7 +38,7 @@ * Skip List using single key instead of range. */ -#define NGHTTP3_KSL_DEGR 8 +#define NGHTTP3_KSL_DEGR 16 /* NGHTTP3_KSL_MAX_NBLK is the maximum number of nodes which a single block can contain. */ #define NGHTTP3_KSL_MAX_NBLK (2 * NGHTTP3_KSL_DEGR - 1) @@ -49,12 +49,7 @@ /* * nghttp3_ksl_key represents key in nghttp3_ksl. */ -typedef union { - /* i is defined to retrieve int64_t key for convenience. */ - const int64_t *i; - /* ptr points to the key. */ - const void *ptr; -} nghttp3_ksl_key; +typedef void nghttp3_ksl_key; struct nghttp3_ksl_node; typedef struct nghttp3_ksl_node nghttp3_ksl_node; @@ -247,11 +242,10 @@ size_t nghttp3_ksl_len(nghttp3_ksl *ksl); void nghttp3_ksl_clear(nghttp3_ksl *ksl); /* - * nghttp3_ksl_nth_node returns the |n|th node under |blk|. This - * function is provided for unit testing. + * nghttp3_ksl_nth_node returns the |n|th node under |blk|. */ -nghttp3_ksl_node *nghttp3_ksl_nth_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, - size_t n); +#define nghttp3_ksl_nth_node(KSL, BLK, N) \ + ((nghttp3_ksl_node *)(void *)((BLK)->nodes + (KSL)->nodelen * (N))) /* * nghttp3_ksl_print prints its internal state in stderr. It assumes @@ -278,7 +272,10 @@ void *nghttp3_ksl_it_get(const nghttp3_ksl_it *it); * if this function is called when nghttp3_ksl_it_end(it) returns * nonzero. */ -void nghttp3_ksl_it_next(nghttp3_ksl_it *it); +#define nghttp3_ksl_it_next(IT) \ + (++(IT)->i == (IT)->blk->n && (IT)->blk->next \ + ? ((IT)->blk = (IT)->blk->next, (IT)->i = 0) \ + : 0) /* * nghttp3_ksl_it_prev moves backward the iterator by one. It is @@ -291,7 +288,8 @@ void nghttp3_ksl_it_prev(nghttp3_ksl_it *it); * nghttp3_ksl_it_end returns nonzero if |it| points to the beyond the * last node. */ -int nghttp3_ksl_it_end(const nghttp3_ksl_it *it); +#define nghttp3_ksl_it_end(IT) \ + ((IT)->blk->n == (IT)->i && (IT)->blk->next == NULL) /* * nghttp3_ksl_it_begin returns nonzero if |it| points to the first @@ -305,13 +303,8 @@ int nghttp3_ksl_it_begin(const nghttp3_ksl_it *it); * It is undefined to call this function when nghttp3_ksl_it_end(it) * returns nonzero. */ -nghttp3_ksl_key nghttp3_ksl_it_key(const nghttp3_ksl_it *it); - -/* - * nghttp3_ksl_key_ptr is a convenient function which initializes - * |key| with |ptr| and returns |key|. - */ -nghttp3_ksl_key *nghttp3_ksl_key_ptr(nghttp3_ksl_key *key, const void *ptr); +#define nghttp3_ksl_it_key(IT) \ + ((nghttp3_ksl_key *)nghttp3_ksl_nth_node((IT)->ksl, (IT)->blk, (IT)->i)->key) /* * nghttp3_ksl_range_compar is an implementation of diff --git a/deps/nghttp3/lib/nghttp3_qpack.c b/deps/nghttp3/lib/nghttp3_qpack.c index 08303c05be0..370c3eb442b 100644 --- a/deps/nghttp3/lib/nghttp3_qpack.c +++ b/deps/nghttp3/lib/nghttp3_qpack.c @@ -462,6 +462,11 @@ static int32_t qpack_lookup_token(const uint8_t *name, size_t namelen) { return NGHTTP3_QPACK_TOKEN_LOCATION; } break; + case 'y': + if (memeq("priorit", name, 7)) { + return NGHTTP3_QPACK_TOKEN_PRIORITY; + } + break; } break; case 9: @@ -773,7 +778,7 @@ static void qpack_map_remove(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) { * ctx->max_dtable_size. */ static int qpack_context_can_reference(nghttp3_qpack_context *ctx, - size_t absidx) { + uint64_t absidx) { nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); return ctx->dtable_sum - ent->sum <= ctx->max_dtable_size; } @@ -785,7 +790,7 @@ static void encoder_qpack_map_find(nghttp3_qpack_encoder *encoder, nghttp3_qpack_entry **pmatch, nghttp3_qpack_entry **ppb_match, const nghttp3_nv *nv, int32_t token, - uint32_t hash, size_t krcnt, + uint32_t hash, uint64_t krcnt, int allow_blocking, int name_only) { nghttp3_qpack_entry *p; @@ -879,14 +884,14 @@ static int ref_min_cnt_less(const nghttp3_pq_entry *lhsx, } typedef struct { - size_t max_cnt; + uint64_t max_cnt; uint64_t id; } nghttp3_blocked_streams_key; static int max_cnt_greater(const nghttp3_ksl_key *lhs, const nghttp3_ksl_key *rhs) { - const nghttp3_blocked_streams_key *a = lhs->ptr; - const nghttp3_blocked_streams_key *b = rhs->ptr; + const nghttp3_blocked_streams_key *a = lhs; + const nghttp3_blocked_streams_key *b = rhs; return a->max_cnt > b->max_cnt || (a->max_cnt == b->max_cnt && a->id < b->id); } @@ -995,7 +1000,7 @@ int nghttp3_qpack_encoder_set_max_blocked(nghttp3_qpack_encoder *encoder, return 0; } -size_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) { +uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) { assert(!nghttp3_pq_empty(&encoder->min_cnts)); return nghttp3_struct_of(nghttp3_pq_top(&encoder->min_cnts), @@ -1006,7 +1011,7 @@ size_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) { void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) { nghttp3_ringbuf *dtable = &encoder->ctx.dtable; const nghttp3_mem *mem = encoder->ctx.mem; - size_t min_cnt = SIZE_MAX; + uint64_t min_cnt = UINT64_MAX; size_t len; nghttp3_qpack_entry *ent; @@ -1048,13 +1053,13 @@ void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) { * Out of memory. */ static int qpack_encoder_add_stream_ref(nghttp3_qpack_encoder *encoder, - int64_t stream_id, size_t max_cnt, - size_t min_cnt) { + int64_t stream_id, uint64_t max_cnt, + uint64_t min_cnt) { nghttp3_qpack_stream *stream = nghttp3_qpack_encoder_find_stream(encoder, stream_id); nghttp3_qpack_header_block_ref *ref; const nghttp3_mem *mem = encoder->ctx.mem; - size_t prev_max_cnt = 0; + uint64_t prev_max_cnt = 0; int rv; if (stream == NULL) { @@ -1161,7 +1166,9 @@ int nghttp3_qpack_encoder_encode(nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, nghttp3_buf *rbuf, nghttp3_buf *ebuf, int64_t stream_id, const nghttp3_nv *nva, size_t nvlen) { - size_t i, base, max_cnt = 0, min_cnt = SIZE_MAX; + size_t i; + uint64_t max_cnt = 0, min_cnt = UINT64_MAX; + uint64_t base; int rv = 0; int allow_blocking; int blocked_stream; @@ -1196,7 +1203,8 @@ int nghttp3_qpack_encoder_encode(nghttp3_qpack_encoder *encoder, } } - nghttp3_qpack_encoder_write_header_block_prefix(encoder, pbuf, max_cnt, base); + nghttp3_qpack_encoder_write_field_section_prefix(encoder, pbuf, max_cnt, + base); /* TODO If max_cnt == 0, no reference is made to dtable. */ if (!max_cnt) { @@ -1358,10 +1366,10 @@ qpack_encoder_decide_indexing_mode(nghttp3_qpack_encoder *encoder, * minimum insert count which blocked stream requires. */ static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need, - size_t min_cnt) { + uint64_t min_cnt) { size_t avail = 0; size_t len; - size_t gmin_cnt; + uint64_t gmin_cnt; nghttp3_qpack_entry *min_ent, *last_ent; nghttp3_ringbuf *dtable = &encoder->ctx.dtable; @@ -1377,7 +1385,7 @@ static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need, min_cnt = nghttp3_min(min_cnt, gmin_cnt); } - if (min_cnt == SIZE_MAX) { + if (min_cnt == UINT64_MAX) { return encoder->ctx.max_dtable_size >= need; } @@ -1400,7 +1408,7 @@ static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need, * count which blocked stream requires. */ static int qpack_encoder_can_index_nv(nghttp3_qpack_encoder *encoder, - const nghttp3_nv *nv, size_t min_cnt) { + const nghttp3_nv *nv, uint64_t min_cnt) { return qpack_encoder_can_index( encoder, table_space(nv->namelen, nv->valuelen), min_cnt); } @@ -1412,7 +1420,8 @@ static int qpack_encoder_can_index_nv(nghttp3_qpack_encoder *encoder, * stream requires. */ static int qpack_encoder_can_index_duplicate(nghttp3_qpack_encoder *encoder, - size_t absidx, size_t min_cnt) { + uint64_t absidx, + uint64_t min_cnt) { nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); @@ -1425,7 +1434,7 @@ static int qpack_encoder_can_index_duplicate(nghttp3_qpack_encoder *encoder, * |absidx| in dynamic table is one of draining entries. */ static int qpack_context_check_draining(nghttp3_qpack_context *ctx, - size_t absidx) { + uint64_t absidx) { const size_t safe = ctx->max_dtable_size - nghttp3_min(512, ctx->max_dtable_size * 1 / 8); nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); @@ -1434,9 +1443,9 @@ static int qpack_context_check_draining(nghttp3_qpack_context *ctx, } int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder, - size_t *pmax_cnt, size_t *pmin_cnt, + uint64_t *pmax_cnt, uint64_t *pmin_cnt, nghttp3_buf *rbuf, nghttp3_buf *ebuf, - const nghttp3_nv *nv, size_t base, + const nghttp3_nv *nv, uint64_t base, int allow_blocking) { uint32_t hash = 0; int32_t token; @@ -1618,7 +1627,7 @@ nghttp3_qpack_lookup_stable(const nghttp3_nv *nv, int32_t token, nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( nghttp3_qpack_encoder *encoder, const nghttp3_nv *nv, int32_t token, - uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, size_t krcnt, + uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, uint64_t krcnt, int allow_blocking) { nghttp3_qpack_lookup_result res = {-1, 0, -1}; int exact_match = 0; @@ -1639,7 +1648,7 @@ nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( } int nghttp3_qpack_header_block_ref_new(nghttp3_qpack_header_block_ref **pref, - size_t max_cnt, size_t min_cnt, + uint64_t max_cnt, uint64_t min_cnt, const nghttp3_mem *mem) { nghttp3_qpack_header_block_ref *ref = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_header_block_ref)); @@ -1723,7 +1732,7 @@ void nghttp3_qpack_stream_del(nghttp3_qpack_stream *stream, nghttp3_mem_free(mem, stream); } -size_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream) { +uint64_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream) { nghttp3_qpack_header_block_ref *ref; if (nghttp3_pq_empty(&stream->max_cnts)) { @@ -1771,15 +1780,18 @@ void nghttp3_qpack_stream_pop_ref(nghttp3_qpack_stream *stream) { int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, - size_t absidx) { - DEBUGF("qpack::encode: Indexed Header Field (static) absidx=%zu\n", absidx); + uint64_t absidx) { + DEBUGF("qpack::encode: Indexed Field Line (static) absidx=%" PRIu64 "\n", + absidx); return qpack_write_number(rbuf, 0xc0, absidx, 6, encoder->ctx.mem); } int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, - size_t absidx, size_t base) { - DEBUGF("qpack::encode: Indexed Header Field (dynamic) absidx=%zu base=%zu\n", + uint64_t absidx, + uint64_t base) { + DEBUGF("qpack::encode: Indexed Field Line (dynamic) absidx=%" PRIu64 + " base=%" PRIu64 "\n", absidx, base); if (absidx < base) { @@ -1804,7 +1816,7 @@ int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, */ static int qpack_encoder_write_indexed_name(nghttp3_qpack_encoder *encoder, nghttp3_buf *buf, uint8_t fb, - size_t nameidx, size_t prefix, + uint64_t nameidx, size_t prefix, const nghttp3_nv *nv) { int rv; size_t len = nghttp3_qpack_put_varint_len(nameidx, prefix); @@ -1850,24 +1862,24 @@ static int qpack_encoder_write_indexed_name(nghttp3_qpack_encoder *encoder, } int nghttp3_qpack_encoder_write_static_indexed_name( - nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, size_t absidx, + nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, const nghttp3_nv *nv) { uint8_t fb = (uint8_t)(0x50 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x20 : 0)); - DEBUGF("qpack::encode: Literal Header Field With Name Reference (static) " - "absidx=%zu never=%d\n", + DEBUGF("qpack::encode: Literal Field Line With Name Reference (static) " + "absidx=%" PRIu64 " never=%d\n", absidx, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0); return qpack_encoder_write_indexed_name(encoder, rbuf, fb, absidx, 4, nv); } int nghttp3_qpack_encoder_write_dynamic_indexed_name( - nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, size_t absidx, - size_t base, const nghttp3_nv *nv) { + nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, + uint64_t base, const nghttp3_nv *nv) { uint8_t fb; - DEBUGF("qpack::encode: Literal Header Field With Name Reference (dynamic) " - "absidx=%zu base=%zu never=%d\n", + DEBUGF("qpack::encode: Literal Field Line With Name Reference (dynamic) " + "absidx=%" PRIu64 " base=%" PRIu64 " never=%d\n", absidx, base, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0); if (absidx < base) { @@ -1964,22 +1976,26 @@ int nghttp3_qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder, uint8_t fb = (uint8_t)(0x20 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x10 : 0)); - DEBUGF("qpack::encode: Literal Header Field Without Name Reference\n"); + DEBUGF("qpack::encode: Literal Field Line Without Name Reference\n"); return qpack_encoder_write_literal(encoder, rbuf, fb, 3, nv); } int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder, - nghttp3_buf *ebuf, size_t absidx, + nghttp3_buf *ebuf, + uint64_t absidx, const nghttp3_nv *nv) { - DEBUGF("qpack::encode: Insert With Name Reference (static) absidx=%zu\n", + DEBUGF("qpack::encode: Insert With Name Reference (static) absidx=%" PRIu64 + "\n", absidx); return qpack_encoder_write_indexed_name(encoder, ebuf, 0xc0, absidx, 6, nv); } int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, - nghttp3_buf *ebuf, size_t absidx, + nghttp3_buf *ebuf, + uint64_t absidx, const nghttp3_nv *nv) { - DEBUGF("qpack::encode: Insert With Name Reference (dynamic) absidx=%zu\n", + DEBUGF("qpack::encode: Insert With Name Reference (dynamic) absidx=%" PRIu64 + "\n", absidx); return qpack_encoder_write_indexed_name( encoder, ebuf, 0x80, encoder->ctx.next_absidx - absidx - 1, 6, nv); @@ -1987,13 +2003,13 @@ int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, int nghttp3_qpack_encoder_write_duplicate_insert(nghttp3_qpack_encoder *encoder, nghttp3_buf *ebuf, - size_t absidx) { - size_t idx = encoder->ctx.next_absidx - absidx - 1; + uint64_t absidx) { + uint64_t idx = encoder->ctx.next_absidx - absidx - 1; size_t len = nghttp3_qpack_put_varint_len(idx, 5); uint8_t *p; int rv; - DEBUGF("qpack::encode: Insert duplicate absidx=%zu\n", absidx); + DEBUGF("qpack::encode: Insert duplicate absidx=%" PRIu64 "\n", absidx); rv = reserve_buf(ebuf, len, encoder->ctx.mem); if (rv != 0) { @@ -2085,7 +2101,8 @@ fail: } int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, - size_t absidx, const nghttp3_nv *nv, + uint64_t absidx, + const nghttp3_nv *nv, uint32_t hash) { const nghttp3_qpack_static_header *shd; nghttp3_qpack_nv qnv; @@ -2114,7 +2131,7 @@ int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, } int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, - size_t absidx, + uint64_t absidx, const nghttp3_nv *nv, uint32_t hash) { nghttp3_qpack_nv qnv; @@ -2145,7 +2162,7 @@ int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, } int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder, - size_t absidx) { + uint64_t absidx) { nghttp3_qpack_nv qnv; nghttp3_qpack_entry *ent; int rv; @@ -2196,12 +2213,13 @@ int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder, } nghttp3_qpack_entry * -nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, size_t absidx) { +nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx) { size_t relidx; assert(ctx->next_absidx > absidx); + assert(ctx->next_absidx - absidx - 1 < nghttp3_ringbuf_len(&ctx->dtable)); - relidx = ctx->next_absidx - absidx - 1; + relidx = (size_t)(ctx->next_absidx - absidx - 1); return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, relidx); } @@ -2213,7 +2231,7 @@ nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx) { } void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv, - size_t sum, size_t absidx, uint32_t hash) { + size_t sum, uint64_t absidx, uint32_t hash) { ent->nv = *qnv; ent->map_next = NULL; ent->sum = sum; @@ -2236,10 +2254,8 @@ int nghttp3_qpack_encoder_block_stream(nghttp3_qpack_encoder *encoder, nghttp3_qpack_header_block_ref, max_cnts_pe) ->max_cnt, stream->me.key}; - nghttp3_ksl_key key; - return nghttp3_ksl_insert(&encoder->blocked_streams, NULL, - nghttp3_ksl_key_ptr(&key, &bsk), stream); + return nghttp3_ksl_insert(&encoder->blocked_streams, NULL, &bsk, stream); } void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, @@ -2249,32 +2265,27 @@ void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, nghttp3_qpack_header_block_ref, max_cnts_pe) ->max_cnt, stream->me.key}; - nghttp3_ksl_key key; nghttp3_ksl_it it; /* This is purely debugging purpose only */ - it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, - nghttp3_ksl_key_ptr(&key, &bsk)); + it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); assert(!nghttp3_ksl_it_end(&it)); assert(nghttp3_ksl_it_get(&it) == stream); - nghttp3_ksl_remove(&encoder->blocked_streams, NULL, &key); + nghttp3_ksl_remove(&encoder->blocked_streams, NULL, &bsk); } void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder, - size_t max_cnt) { + uint64_t max_cnt) { nghttp3_blocked_streams_key bsk = {max_cnt, 0}; - nghttp3_ksl_key key; nghttp3_ksl_it it; - it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, - nghttp3_ksl_key_ptr(&key, &bsk)); + it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); for (; !nghttp3_ksl_it_end(&it);) { - bsk = *(nghttp3_blocked_streams_key *)nghttp3_ksl_it_key(&it).ptr; - nghttp3_ksl_remove(&encoder->blocked_streams, &it, - nghttp3_ksl_key_ptr(&key, &bsk)); + bsk = *(nghttp3_blocked_streams_key *)nghttp3_ksl_it_key(&it); + nghttp3_ksl_remove(&encoder->blocked_streams, &it, &bsk); } } @@ -2296,8 +2307,8 @@ void nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, ref = *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0); - DEBUGF("qpack::encoder: Header acknowledgement stream=%ld ricnt=%zu " - "krcnt=%zu\n", + DEBUGF("qpack::encoder: Header acknowledgement stream=%ld ricnt=%" PRIu64 + " krcnt=%" PRIu64 "\n", stream_id, ref->max_cnt, encoder->krcnt); if (encoder->krcnt < ref->max_cnt) { @@ -2324,8 +2335,8 @@ void nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, } int nghttp3_qpack_encoder_add_insert_count(nghttp3_qpack_encoder *encoder, - size_t n) { - if (encoder->ctx.next_absidx < encoder->krcnt + n) { + uint64_t n) { + if (encoder->ctx.next_absidx - encoder->krcnt < n) { return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; } encoder->krcnt += n; @@ -2367,21 +2378,21 @@ size_t nghttp3_qpack_encoder_get_num_blocked(nghttp3_qpack_encoder *encoder) { return nghttp3_ksl_len(&encoder->blocked_streams); } -int nghttp3_qpack_encoder_write_header_block_prefix( - nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, size_t ricnt, - size_t base) { +int nghttp3_qpack_encoder_write_field_section_prefix( + nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt, + uint64_t base) { size_t max_ents = encoder->ctx.hard_max_dtable_size / NGHTTP3_QPACK_ENTRY_OVERHEAD; - size_t encricnt = ricnt == 0 ? 0 : (ricnt % (2 * max_ents)) + 1; + uint64_t encricnt = ricnt == 0 ? 0 : (ricnt % (2 * max_ents)) + 1; int sign = base < ricnt; - size_t delta_base = sign ? ricnt - base - 1 : base - ricnt; + uint64_t delta_base = sign ? ricnt - base - 1 : base - ricnt; size_t len = nghttp3_qpack_put_varint_len(encricnt, 8) + nghttp3_qpack_put_varint_len(delta_base, 7); uint8_t *p; int rv; - DEBUGF("qpack::encode: ricnt=%zu base=%zu icnt=%zu\n", ricnt, base, - encoder->ctx.next_absidx); + DEBUGF("qpack::encode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", + ricnt, base, encoder->ctx.next_absidx); rv = reserve_buf(pbuf, len, encoder->ctx.mem); if (rv != 0) { @@ -2510,8 +2521,8 @@ nghttp3_ssize nghttp3_qpack_encoder_read_decoder(nghttp3_qpack_encoder *encoder, switch (encoder->state) { case NGHTTP3_QPACK_DS_STATE_OPCODE: if ((*p) & 0x80) { - DEBUGF("qpack::encode: OPCODE_HEADER_ACK\n"); - encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_HEADER_ACK; + DEBUGF("qpack::encode: OPCODE_SECTION_ACK\n"); + encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK; encoder->rstate.prefix = 7; } else if ((*p) & 0x40) { DEBUGF("qpack::encode: OPCODE_STREAM_CANCEL\n"); @@ -2546,7 +2557,7 @@ nghttp3_ssize nghttp3_qpack_encoder_read_decoder(nghttp3_qpack_encoder *encoder, goto fail; } break; - case NGHTTP3_QPACK_DS_OPCODE_HEADER_ACK: + case NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK: nghttp3_qpack_encoder_ack_header(encoder, (int64_t)encoder->rstate.left); break; @@ -2684,7 +2695,7 @@ static nghttp3_ssize qpack_read_huffman_string(nghttp3_qpack_read_state *rstate, int fin = 0; if (len >= rstate->left) { - len = rstate->left; + len = (size_t)rstate->left; fin = 1; } @@ -2707,7 +2718,7 @@ static nghttp3_ssize qpack_read_string(nghttp3_qpack_read_state *rstate, nghttp3_buf *dest, const uint8_t *begin, const uint8_t *end) { size_t len = (size_t)(end - begin); - size_t n = nghttp3_min(len, rstate->left); + size_t n = (size_t)nghttp3_min((uint64_t)len, rstate->left); dest->last = nghttp3_cpymem(dest->last, begin, n); @@ -2824,9 +2835,10 @@ nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder, rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; goto fail; } - DEBUGF("qpack::decode: Set dtable capacity to %zu\n", + DEBUGF("qpack::decode: Set dtable capacity to %" PRIu64 "\n", decoder->rstate.left); - nghttp3_qpack_decoder_set_dtable_cap(decoder, decoder->rstate.left); + nghttp3_qpack_decoder_set_dtable_cap(decoder, + (size_t)decoder->rstate.left); decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; nghttp3_qpack_read_state_reset(&decoder->rstate); @@ -2877,15 +2889,20 @@ nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder, return p - src; } + if (decoder->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + if (decoder->rstate.huffman_encoded) { decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN; nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); rv = nghttp3_rcbuf_new(&decoder->rstate.name, - decoder->rstate.left * 2 + 1, mem); + (size_t)decoder->rstate.left * 2 + 1, mem); } else { decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME; - rv = nghttp3_rcbuf_new(&decoder->rstate.name, decoder->rstate.left + 1, - mem); + rv = nghttp3_rcbuf_new(&decoder->rstate.name, + (size_t)decoder->rstate.left + 1, mem); } if (rv != 0) { goto fail; @@ -2953,15 +2970,20 @@ nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder, return p - src; } + if (decoder->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { + rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; + goto fail; + } + if (decoder->rstate.huffman_encoded) { decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN; nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); rv = nghttp3_rcbuf_new(&decoder->rstate.value, - decoder->rstate.left * 2 + 1, mem); + (size_t)decoder->rstate.left * 2 + 1, mem); } else { decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE; - rv = nghttp3_rcbuf_new(&decoder->rstate.value, decoder->rstate.left + 1, - mem); + rv = nghttp3_rcbuf_new(&decoder->rstate.value, + (size_t)decoder->rstate.left + 1, mem); } if (rv != 0) { goto fail; @@ -3076,7 +3098,7 @@ void nghttp3_qpack_decoder_set_dtable_cap(nghttp3_qpack_decoder *decoder, } int nghttp3_qpack_decoder_dtable_indexed_add(nghttp3_qpack_decoder *decoder) { - DEBUGF("qpack::decode: Insert With Name Reference (%s) absidx=%zu: " + DEBUGF("qpack::decode: Insert With Name Reference (%s) absidx=%" PRIu64 ": " "value=%*s\n", decoder->rstate.dynamic ? "dynamic" : "static", decoder->rstate.absidx, (int)decoder->rstate.value->len, decoder->rstate.value->base); @@ -3144,7 +3166,7 @@ int nghttp3_qpack_decoder_dtable_duplicate_add(nghttp3_qpack_decoder *decoder) { nghttp3_qpack_entry *ent; nghttp3_qpack_nv qnv; - DEBUGF("qpack::decode: Insert duplicate absidx=%zu\n", + DEBUGF("qpack::decode: Insert duplicate absidx=%" PRIu64 "\n", decoder->rstate.absidx); ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx); @@ -3221,7 +3243,7 @@ void nghttp3_qpack_stream_context_reset(nghttp3_qpack_stream_context *sctx) { nghttp3_qpack_stream_context_init(sctx, sctx->stream_id, sctx->mem); } -size_t +uint64_t nghttp3_qpack_stream_context_get_ricnt(nghttp3_qpack_stream_context *sctx) { return sctx->ricnt; } @@ -3302,8 +3324,9 @@ nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, sctx->base = sctx->ricnt + sctx->rstate.left; } - DEBUGF("qpack::decode: ricnt=%zu base=%zu icnt=%zu\n", sctx->ricnt, - sctx->base, decoder->ctx.next_absidx); + DEBUGF("qpack::decode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 + "\n", + sctx->ricnt, sctx->base, decoder->ctx.next_absidx); if (sctx->ricnt > decoder->ctx.next_absidx) { DEBUGF("qpack::decode: stream blocked\n"); @@ -3434,7 +3457,7 @@ nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, goto almost_ok; } - if (decoder->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { + if (sctx->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; goto fail; } @@ -3442,11 +3465,12 @@ nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, if (sctx->rstate.huffman_encoded) { sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN; nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); - rv = nghttp3_rcbuf_new(&sctx->rstate.name, sctx->rstate.left * 2 + 1, - mem); + rv = nghttp3_rcbuf_new(&sctx->rstate.name, + (size_t)sctx->rstate.left * 2 + 1, mem); } else { sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME; - rv = nghttp3_rcbuf_new(&sctx->rstate.name, sctx->rstate.left + 1, mem); + rv = nghttp3_rcbuf_new(&sctx->rstate.name, + (size_t)sctx->rstate.left + 1, mem); } if (rv != 0) { goto fail; @@ -3513,7 +3537,7 @@ nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, goto almost_ok; } - if (decoder->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { + if (sctx->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; goto fail; } @@ -3521,11 +3545,12 @@ nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, if (sctx->rstate.huffman_encoded) { sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN; nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); - rv = nghttp3_rcbuf_new(&sctx->rstate.value, sctx->rstate.left * 2 + 1, - mem); + rv = nghttp3_rcbuf_new(&sctx->rstate.value, + (size_t)sctx->rstate.left * 2 + 1, mem); } else { sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE; - rv = nghttp3_rcbuf_new(&sctx->rstate.value, sctx->rstate.left + 1, mem); + rv = nghttp3_rcbuf_new(&sctx->rstate.value, + (size_t)sctx->rstate.left + 1, mem); } if (rv != 0) { goto fail; @@ -3629,7 +3654,7 @@ almost_ok: *pflags |= NGHTTP3_QPACK_DECODE_FLAG_FINAL; if (sctx->ricnt) { - rv = nghttp3_qpack_decoder_write_header_ack(decoder, sctx); + rv = nghttp3_qpack_decoder_write_section_ack(decoder, sctx); if (rv != 0) { goto fail; } @@ -3649,7 +3674,7 @@ static int qpack_decoder_dbuf_overflow(nghttp3_qpack_decoder *decoder) { return nghttp3_buf_len(&decoder->dbuf) > limit * 2 * 10; } -int nghttp3_qpack_decoder_write_header_ack( +int nghttp3_qpack_decoder_write_section_ack( nghttp3_qpack_decoder *decoder, const nghttp3_qpack_stream_context *sctx) { nghttp3_buf *dbuf = &decoder->dbuf; uint8_t *p; @@ -3679,7 +3704,7 @@ int nghttp3_qpack_decoder_write_header_ack( size_t nghttp3_qpack_decoder_get_decoder_streamlen(nghttp3_qpack_decoder *decoder) { - size_t n; + uint64_t n; size_t len = 0; if (decoder->written_icnt < decoder->ctx.next_absidx) { @@ -3693,7 +3718,7 @@ nghttp3_qpack_decoder_get_decoder_streamlen(nghttp3_qpack_decoder *decoder) { void nghttp3_qpack_decoder_write_decoder(nghttp3_qpack_decoder *decoder, nghttp3_buf *dbuf) { uint8_t *p; - size_t n = 0; + uint64_t n = 0; size_t len = 0; if (decoder->written_icnt < decoder->ctx.next_absidx) { @@ -3743,7 +3768,7 @@ int nghttp3_qpack_decoder_cancel_stream(nghttp3_qpack_decoder *decoder, } int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, - size_t *dest, size_t encricnt) { + uint64_t *dest, uint64_t encricnt) { uint64_t max_ents, full, max, max_wrapped, ricnt; if (encricnt == 0) { @@ -3780,8 +3805,8 @@ int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, int nghttp3_qpack_decoder_rel2abs(nghttp3_qpack_decoder *decoder, nghttp3_qpack_read_state *rstate) { - DEBUGF("qpack::decode: dynamic=%d relidx=%zu icnt=%zu\n", rstate->dynamic, - rstate->left, decoder->ctx.next_absidx); + DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " icnt=%" PRIu64 "\n", + rstate->dynamic, rstate->left, decoder->ctx.next_absidx); if (rstate->dynamic) { if (decoder->ctx.next_absidx < rstate->left + 1) { @@ -3801,7 +3826,8 @@ int nghttp3_qpack_decoder_brel2abs(nghttp3_qpack_decoder *decoder, nghttp3_qpack_stream_context *sctx) { nghttp3_qpack_read_state *rstate = &sctx->rstate; - DEBUGF("qpack::decode: dynamic=%d relidx=%zu base=%zu icnt=%zu\n", + DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " base=%" PRIu64 + " icnt=%" PRIu64 "\n", rstate->dynamic, rstate->left, sctx->base, decoder->ctx.next_absidx); if (rstate->dynamic) { @@ -3827,8 +3853,8 @@ int nghttp3_qpack_decoder_pbrel2abs(nghttp3_qpack_decoder *decoder, nghttp3_qpack_stream_context *sctx) { nghttp3_qpack_read_state *rstate = &sctx->rstate; - DEBUGF("qpack::decode: pbidx=%zu base=%zu icnt=%zu\n", rstate->left, - sctx->base, decoder->ctx.next_absidx); + DEBUGF("qpack::decode: pbidx=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", + rstate->left, sctx->base, decoder->ctx.next_absidx); assert(rstate->dynamic); @@ -3873,7 +3899,7 @@ qpack_decoder_emit_dynamic_indexed(nghttp3_qpack_decoder *decoder, void nghttp3_qpack_decoder_emit_indexed(nghttp3_qpack_decoder *decoder, nghttp3_qpack_stream_context *sctx, nghttp3_qpack_nv *nv) { - DEBUGF("qpack::decode: Indexed (%s) absidx=%zu\n", + DEBUGF("qpack::decode: Indexed (%s) absidx=%" PRIu64 "\n", sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx); if (sctx->rstate.dynamic) { @@ -3923,7 +3949,7 @@ void nghttp3_qpack_decoder_emit_indexed_name(nghttp3_qpack_decoder *decoder, nghttp3_qpack_nv *nv) { (void)decoder; - DEBUGF("qpack::decode: Indexed name (%s) absidx=%zu value=%*s\n", + DEBUGF("qpack::decode: Indexed name (%s) absidx=%" PRIu64 " value=%*s\n", sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx, (int)sctx->rstate.value->len, sctx->rstate.value->base); @@ -4051,6 +4077,6 @@ void nghttp3_qpack_decoder_del(nghttp3_qpack_decoder *decoder) { nghttp3_mem_free(mem, decoder); } -size_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder) { +uint64_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder) { return decoder->ctx.next_absidx; } diff --git a/deps/nghttp3/lib/nghttp3_qpack.h b/deps/nghttp3/lib/nghttp3_qpack.h index b3ccd7a5ee7..1a3097cae8d 100644 --- a/deps/nghttp3/lib/nghttp3_qpack.h +++ b/deps/nghttp3/lib/nghttp3_qpack.h @@ -76,14 +76,14 @@ struct nghttp3_qpack_entry { value does not contain the space required for this entry. */ size_t sum; /* absidx is the absolute index of this entry. */ - size_t absidx; + uint64_t absidx; /* The hash value for header name (nv.name). */ uint32_t hash; }; /* The entry used for static table. */ typedef struct { - size_t absidx; + uint64_t absidx; int32_t token; uint32_t hash; } nghttp3_qpack_static_entry; @@ -103,16 +103,16 @@ typedef struct { nghttp3_pq_entry max_cnts_pe; nghttp3_pq_entry min_cnts_pe; /* max_cnt is the required insert count. */ - size_t max_cnt; + uint64_t max_cnt; /* min_cnt is the minimum insert count of dynamic table entry it refers to. In other words, this is the minimum absolute index of dynamic header table entry this encoded block refers to plus 1. */ - size_t min_cnt; + uint64_t min_cnt; } nghttp3_qpack_header_block_ref; int nghttp3_qpack_header_block_ref_new(nghttp3_qpack_header_block_ref **pref, - size_t max_cnt, size_t min_cnt, + uint64_t max_cnt, uint64_t min_cnt, const nghttp3_mem *mem); void nghttp3_qpack_header_block_ref_del(nghttp3_qpack_header_block_ref *ref, @@ -136,7 +136,7 @@ int nghttp3_qpack_stream_new(nghttp3_qpack_stream **pstream, int64_t stream_id, void nghttp3_qpack_stream_del(nghttp3_qpack_stream *stream, const nghttp3_mem *mem); -size_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream); +uint64_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream); int nghttp3_qpack_stream_add_ref(nghttp3_qpack_stream *stream, nghttp3_qpack_header_block_ref *ref); @@ -169,7 +169,7 @@ typedef struct { size_t max_blocked; /* next_absidx is the next absolute index for nghttp3_qpack_entry. It is equivalent to insert count. */ - size_t next_absidx; + uint64_t next_absidx; /* If inflate/deflate error occurred, this value is set to 1 and further invocation of inflate/deflate will fail with NGHTTP3_ERR_QPACK_FATAL. */ @@ -185,7 +185,7 @@ typedef struct { uint64_t left; size_t prefix; size_t shift; - size_t absidx; + uint64_t absidx; int never; int dynamic; int huffman_encoded; @@ -212,7 +212,7 @@ typedef enum { stream. */ typedef enum { NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT, - NGHTTP3_QPACK_DS_OPCODE_HEADER_ACK, + NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK, NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL, } nghttp3_qpack_decoder_stream_opcode; @@ -242,7 +242,7 @@ struct nghttp3_qpack_encoder { evicted from dynamic table. */ nghttp3_pq min_cnts; /* krcnt is Known Received Count. */ - size_t krcnt; + uint64_t krcnt; /* state is a current state of reading decoder stream. */ nghttp3_qpack_decoder_stream_state state; /* opcode is a decoder stream opcode being processed. */ @@ -296,9 +296,9 @@ void nghttp3_qpack_encoder_free(nghttp3_qpack_encoder *encoder); * Out of memory. */ int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder, - size_t *pmax_cnt, size_t *pmin_cnt, + uint64_t *pmax_cnt, uint64_t *pmin_cnt, nghttp3_buf *rbuf, nghttp3_buf *ebuf, - const nghttp3_nv *nv, size_t base, + const nghttp3_nv *nv, uint64_t base, int allow_blocking); /* nghttp3_qpack_lookup_result stores a result of table lookup. */ @@ -332,13 +332,13 @@ nghttp3_qpack_lookup_stable(const nghttp3_nv *nv, int32_t token, */ nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( nghttp3_qpack_encoder *encoder, const nghttp3_nv *nv, int32_t token, - uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, size_t krcnt, + uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, uint64_t krcnt, int allow_blocking); /* - * nghttp3_qpack_encoder_write_header_block_prefix writes Header Block - * Prefix into |pbuf|. |ricnt| is Required Insert Count. |base| is - * Base. + * nghttp3_qpack_encoder_write_field_section_prefix writes Encoded + * Field Section Prefix into |pbuf|. |ricnt| is Required Insert + * Count. |base| is Base. * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -346,9 +346,9 @@ nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( * NGHTTP3_ERR_NOMEM * Out of memory. */ -int nghttp3_qpack_encoder_write_header_block_prefix( - nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, size_t ricnt, - size_t base); +int nghttp3_qpack_encoder_write_field_section_prefix( + nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt, + uint64_t base); /* * nghttp3_qpack_encoder_write_static_indexed writes Indexed Header @@ -362,7 +362,7 @@ int nghttp3_qpack_encoder_write_header_block_prefix( */ int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, - size_t absidx); + uint64_t absidx); /* * nghttp3_qpack_encoder_write_dynamic_indexed writes Indexed Header @@ -377,7 +377,7 @@ int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder, */ int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, - size_t absidx, size_t base); + uint64_t absidx, uint64_t base); /* * nghttp3_qpack_encoder_write_static_indexed writes Literal Header @@ -392,7 +392,7 @@ int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, * Out of memory. */ int nghttp3_qpack_encoder_write_static_indexed_name( - nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, size_t absidx, + nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, const nghttp3_nv *nv); /* @@ -408,8 +408,8 @@ int nghttp3_qpack_encoder_write_static_indexed_name( * Out of memory. */ int nghttp3_qpack_encoder_write_dynamic_indexed_name( - nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, size_t absidx, - size_t base, const nghttp3_nv *nv); + nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, + uint64_t base, const nghttp3_nv *nv); /* * nghttp3_qpack_encoder_write_literal writes Literal Header Field @@ -438,7 +438,8 @@ int nghttp3_qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder, * Out of memory. */ int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder, - nghttp3_buf *ebuf, size_t absidx, + nghttp3_buf *ebuf, + uint64_t absidx, const nghttp3_nv *nv); /* @@ -453,7 +454,8 @@ int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder, * Out of memory. */ int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, - nghttp3_buf *ebuf, size_t absidx, + nghttp3_buf *ebuf, + uint64_t absidx, const nghttp3_nv *nv); /* @@ -469,7 +471,7 @@ int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, */ int nghttp3_qpack_encoder_write_duplicate_insert(nghttp3_qpack_encoder *encoder, nghttp3_buf *ebuf, - size_t absidx); + uint64_t absidx); /* * nghttp3_qpack_encoder_write_literal_insert writes Insert Without @@ -511,7 +513,7 @@ void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, * than or equal to |max_cnt|. */ void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder, - size_t max_cnt); + uint64_t max_cnt); /* * nghttp3_qpack_encoder_find_stream returns stream whose stream ID is @@ -522,7 +524,7 @@ nghttp3_qpack_stream * nghttp3_qpack_encoder_find_stream(nghttp3_qpack_encoder *encoder, int64_t stream_id); -size_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder); +uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder); /* * nghttp3_qpack_encoder_shrink_dtable shrinks dynamic table so that @@ -585,7 +587,8 @@ int nghttp3_qpack_context_dtable_add(nghttp3_qpack_context *ctx, * Out of memory. */ int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, - size_t absidx, const nghttp3_nv *nv, + uint64_t absidx, + const nghttp3_nv *nv, uint32_t hash); /* @@ -600,7 +603,7 @@ int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, * Out of memory. */ int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, - size_t absidx, + uint64_t absidx, const nghttp3_nv *nv, uint32_t hash); @@ -615,7 +618,7 @@ int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, * Out of memory. */ int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder, - size_t absidx); + uint64_t absidx); /* * nghttp3_qpack_encoder_dtable_literal_add adds |nv| to dynamic @@ -634,7 +637,7 @@ int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder, * exists. */ nghttp3_qpack_entry * -nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, size_t absidx); +nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx); /* * nghttp3_qpack_context_dtable_top returns latest dynamic table @@ -652,7 +655,7 @@ nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx); * qnv->nv.value. */ void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv, - size_t sum, size_t absidx, uint32_t hash); + size_t sum, uint64_t absidx, uint32_t hash); /* * nghttp3_qpack_entry_free frees memory allocated for |ent|. @@ -739,7 +742,7 @@ struct nghttp3_qpack_decoder { /* dbuf is decoder stream. */ nghttp3_buf dbuf; /* written_icnt is Insert Count written to decoder stream so far. */ - size_t written_icnt; + uint64_t written_icnt; /* max_concurrent_streams is the number of concurrent streams that a remote endpoint can open, including both bidirectional and unidirectional streams which potentially receives QPACK encoded @@ -855,9 +858,9 @@ struct nghttp3_qpack_stream_context { nghttp3_qpack_request_stream_opcode opcode; int64_t stream_id; /* ricnt is Required Insert Count to decode this header block. */ - size_t ricnt; + uint64_t ricnt; /* base is Base in Header Block Prefix. */ - size_t base; + uint64_t base; /* dbase_sign is the delta base sign in Header Block Prefix. */ int dbase_sign; }; @@ -889,7 +892,7 @@ void nghttp3_qpack_stream_context_reset(nghttp3_qpack_stream_context *sctx); * Unable to reconstruct Required Insert Count. */ int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, - size_t *dest, size_t encricnt); + uint64_t *dest, uint64_t encricnt); /* * nghttp3_qpack_decoder_rel2abs converts relative index rstate->left @@ -946,7 +949,7 @@ void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder, nghttp3_qpack_nv *nv); /* - * nghttp3_qpack_decoder_write_header_ack writes Header + * nghttp3_qpack_decoder_write_section_ack writes Section * Acknowledgement to decoder stream. * * This function returns 0 if it succeeds, or one of the following @@ -957,7 +960,7 @@ void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder, * NGHTTP3_ERR_QPACK_FATAL * Decoder stream overflow. */ -int nghttp3_qpack_decoder_write_header_ack( +int nghttp3_qpack_decoder_write_section_ack( nghttp3_qpack_decoder *decoder, const nghttp3_qpack_stream_context *sctx); #endif /* NGHTTP3_QPACK_H */ diff --git a/deps/nghttp3/lib/nghttp3_stream.c b/deps/nghttp3/lib/nghttp3_stream.c index b75d3f7ba0e..bf66d738d78 100644 --- a/deps/nghttp3/lib/nghttp3_stream.c +++ b/deps/nghttp3/lib/nghttp3_stream.c @@ -43,8 +43,7 @@ #define NGHTTP3_MIN_RBLEN 4 int nghttp3_stream_new(nghttp3_stream **pstream, int64_t stream_id, - uint64_t seq, uint32_t weight, nghttp3_tnode *parent, - const nghttp3_stream_callbacks *callbacks, + uint64_t seq, const nghttp3_stream_callbacks *callbacks, const nghttp3_mem *mem) { int rv; nghttp3_stream *stream = nghttp3_mem_calloc(mem, 1, sizeof(nghttp3_stream)); @@ -57,7 +56,7 @@ int nghttp3_stream_new(nghttp3_stream **pstream, int64_t stream_id, nghttp3_tnode_init( &stream->node, nghttp3_node_id_init(&nid, NGHTTP3_NODE_ID_TYPE_STREAM, stream_id), seq, - weight, parent, mem); + NGHTTP3_DEFAULT_URGENCY); rv = nghttp3_ringbuf_init(&stream->frq, 0, sizeof(nghttp3_frame_entry), mem); if (rv != 0) { @@ -86,6 +85,7 @@ int nghttp3_stream_new(nghttp3_stream **pstream, int64_t stream_id, stream->mem = mem; stream->rx.http.status_code = -1; stream->rx.http.content_length = -1; + stream->rx.http.pri = NGHTTP3_DEFAULT_URGENCY; stream->error_code = NGHTTP3_H3_NO_ERROR; if (callbacks) { @@ -380,8 +380,8 @@ int nghttp3_stream_write_settings(nghttp3_stream *stream, fr.settings.niv = 3; iv = &fr.settings.iv[0]; - iv[0].id = NGHTTP3_SETTINGS_ID_MAX_HEADER_LIST_SIZE; - iv[0].value = local_settings->max_header_list_size; + iv[0].id = NGHTTP3_SETTINGS_ID_MAX_FIELD_SECTION_SIZE; + iv[0].value = local_settings->max_field_section_size; iv[1].id = NGHTTP3_SETTINGS_ID_QPACK_MAX_TABLE_CAPACITY; iv[1].value = local_settings->qpack_max_table_capacity; iv[2].id = NGHTTP3_SETTINGS_ID_QPACK_BLOCKED_STREAMS; @@ -846,18 +846,13 @@ int nghttp3_stream_is_blocked(nghttp3_stream *stream) { (stream->flags & NGHTTP3_STREAM_FLAG_READ_DATA_BLOCKED); } -int nghttp3_stream_is_active(nghttp3_stream *stream) { +int nghttp3_stream_require_schedule(nghttp3_stream *stream) { return (!nghttp3_stream_outq_write_done(stream) && !(stream->flags & NGHTTP3_STREAM_FLAG_FC_BLOCKED)) || (nghttp3_ringbuf_len(&stream->frq) && !(stream->flags & NGHTTP3_STREAM_FLAG_READ_DATA_BLOCKED)); } -int nghttp3_stream_require_schedule(nghttp3_stream *stream) { - return nghttp3_stream_is_active(stream) || - nghttp3_tnode_has_active_descendant(&stream->node); -} - nghttp3_ssize nghttp3_stream_writev(nghttp3_stream *stream, int *pfin, nghttp3_vec *vec, size_t veccnt) { nghttp3_ringbuf *outq = &stream->outq; @@ -964,9 +959,9 @@ static int stream_pop_outq_entry(nghttp3_stream *stream, return 0; } -int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, size_t n) { +int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, uint64_t n) { nghttp3_ringbuf *outq = &stream->outq; - size_t offset = stream->ack_offset + n; + uint64_t offset = stream->ack_offset + n; size_t buflen; size_t npopped = 0; size_t nack; @@ -978,7 +973,7 @@ int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, size_t n) { buflen = nghttp3_buf_len(&tbuf->buf); if (tbuf->type == NGHTTP3_BUF_TYPE_ALIEN) { - nack = nghttp3_min(offset, buflen) - stream->ack_done; + nack = (size_t)nghttp3_min(offset, (uint64_t)buflen) - stream->ack_done; if (stream->callbacks.acked_data) { rv = stream->callbacks.acked_data(stream, stream->node.nid.id, nack, stream->user_data); @@ -1022,50 +1017,6 @@ int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, size_t n) { return 0; } -static nghttp3_tnode *stream_get_dependency_node(nghttp3_stream *stream) { - if (stream->pp) { - assert(stream->type == NGHTTP3_STREAM_TYPE_PUSH); - return &stream->pp->node; - } - - return &stream->node; -} - -int nghttp3_stream_schedule(nghttp3_stream *stream) { - int rv; - - rv = nghttp3_tnode_schedule(stream_get_dependency_node(stream), - stream->unscheduled_nwrite); - if (rv != 0) { - return rv; - } - - stream->unscheduled_nwrite = 0; - - return 0; -} - -int nghttp3_stream_ensure_scheduled(nghttp3_stream *stream) { - if (nghttp3_tnode_is_scheduled(stream_get_dependency_node(stream))) { - return 0; - } - - return nghttp3_stream_schedule(stream); -} - -void nghttp3_stream_unschedule(nghttp3_stream *stream) { - nghttp3_tnode_unschedule(stream_get_dependency_node(stream)); -} - -int nghttp3_stream_squash(nghttp3_stream *stream) { - nghttp3_tnode *node = stream_get_dependency_node(stream); - - if (!node->parent) { - return 0; - } - return nghttp3_tnode_squash(stream_get_dependency_node(stream)); -} - int nghttp3_stream_buffer_data(nghttp3_stream *stream, const uint8_t *data, size_t datalen) { nghttp3_ringbuf *inq = &stream->inq; @@ -1126,17 +1077,6 @@ size_t nghttp3_stream_get_buffered_datalen(nghttp3_stream *stream) { return n; } -void nghttp3_stream_clear_buffered_data(nghttp3_stream *stream) { - nghttp3_ringbuf *inq = &stream->inq; - nghttp3_buf *buf; - - for (; nghttp3_ringbuf_len(inq);) { - buf = nghttp3_ringbuf_get(inq, 0); - nghttp3_buf_free(buf, stream->mem); - nghttp3_ringbuf_pop_front(inq); - } -} - int nghttp3_stream_transit_rx_http_state(nghttp3_stream *stream, nghttp3_stream_http_event event) { int rv; diff --git a/deps/nghttp3/lib/nghttp3_stream.h b/deps/nghttp3/lib/nghttp3_stream.h index 116249777c6..1dcc421123a 100644 --- a/deps/nghttp3/lib/nghttp3_stream.h +++ b/deps/nghttp3/lib/nghttp3_stream.h @@ -44,6 +44,10 @@ enough to fill outgoing single QUIC packet. */ #define NGHTTP3_MIN_UNSENT_BYTES 4096 +/* NGHTTP3_STREAM_MIN_WRITELEN is the minimum length of write to cause + the stream to reschedule. */ +#define NGHTTP3_STREAM_MIN_WRITELEN 800 + /* nghttp3_stream_type is unidirectional stream type. */ typedef enum { NGHTTP3_STREAM_TYPE_CONTROL = 0x00, @@ -196,6 +200,8 @@ struct nghttp3_http_state { far. */ int64_t recv_content_length; uint16_t flags; + /* pri is a stream priority produced by nghttp3_pri_to_uint8. */ + uint8_t pri; }; typedef struct nghttp3_http_state nghttp3_http_state; @@ -229,7 +235,7 @@ struct nghttp3_stream { size_t outq_offset; /* ack_offset is offset acknowledged by peer relative to the first element in outq. */ - size_t ack_offset; + uint64_t ack_offset; /* ack_done is the number of bytes notified to an application that they are acknowledged inside the first outq element if it is of type NGHTTP3_BUF_TYPE_ALIEN. */ @@ -267,8 +273,7 @@ typedef struct { } nghttp3_frame_entry; int nghttp3_stream_new(nghttp3_stream **pstream, int64_t stream_id, - uint64_t seq, uint32_t weight, nghttp3_tnode *parent, - const nghttp3_stream_callbacks *callbacks, + uint64_t seq, const nghttp3_stream_callbacks *callbacks, const nghttp3_mem *mem); void nghttp3_stream_del(nghttp3_stream *stream); @@ -338,7 +343,7 @@ int nghttp3_stream_add_outq_offset(nghttp3_stream *stream, size_t n); */ int nghttp3_stream_outq_write_done(nghttp3_stream *stream); -int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, size_t n); +int nghttp3_stream_add_ack_offset(nghttp3_stream *stream, uint64_t n); /* * nghttp3_stream_is_active returns nonzero if |stream| is active. In @@ -354,35 +359,11 @@ int nghttp3_stream_is_active(nghttp3_stream *stream); */ int nghttp3_stream_require_schedule(nghttp3_stream *stream); -/* - * nghttp3_stream_schedule schedules |stream|. This function works - * whether |stream| has already been scheduled or not. If it has been - * scheduled already, it is rescheduled by delaying its pending - * penalty. - */ -int nghttp3_stream_schedule(nghttp3_stream *stream); - -/* - * nghttp3_stream_ensure_scheduled schedules |stream| if it has not - * been scheduled. - */ -int nghttp3_stream_ensure_scheduled(nghttp3_stream *stream); - -void nghttp3_stream_unschedule(nghttp3_stream *stream); - -/* - * nghttp3_stream_squash unschedules |stream| and removes it from - * dependency tree. - */ -int nghttp3_stream_squash(nghttp3_stream *stream); - int nghttp3_stream_buffer_data(nghttp3_stream *stream, const uint8_t *src, size_t srclen); size_t nghttp3_stream_get_buffered_datalen(nghttp3_stream *stream); -void nghttp3_stream_clear_buffered_data(nghttp3_stream *stream); - int nghttp3_stream_ensure_qpack_stream_context(nghttp3_stream *stream); void nghttp3_stream_delete_qpack_stream_context(nghttp3_stream *stream); diff --git a/deps/nghttp3/lib/nghttp3_tnode.c b/deps/nghttp3/lib/nghttp3_tnode.c index b6f6b787436..94dca7dbf76 100644 --- a/deps/nghttp3/lib/nghttp3_tnode.c +++ b/deps/nghttp3/lib/nghttp3_tnode.c @@ -29,6 +29,7 @@ #include "nghttp3_macro.h" #include "nghttp3_stream.h" #include "nghttp3_conn.h" +#include "nghttp3_conv.h" nghttp3_node_id *nghttp3_node_id_init(nghttp3_node_id *nid, nghttp3_node_id_type type, int64_t id) { @@ -41,294 +42,69 @@ int nghttp3_node_id_eq(const nghttp3_node_id *a, const nghttp3_node_id *b) { return a->type == b->type && a->id == b->id; } -static int cycle_less(const nghttp3_pq_entry *lhsx, - const nghttp3_pq_entry *rhsx) { - const nghttp3_tnode *lhs = nghttp3_struct_of(lhsx, nghttp3_tnode, pe); - const nghttp3_tnode *rhs = nghttp3_struct_of(rhsx, nghttp3_tnode, pe); - - if (lhs->cycle == rhs->cycle) { - return lhs->seq < rhs->seq; - } - - return rhs->cycle - lhs->cycle <= NGHTTP3_TNODE_MAX_CYCLE_GAP; -} - void nghttp3_tnode_init(nghttp3_tnode *tnode, const nghttp3_node_id *nid, - uint64_t seq, uint32_t weight, nghttp3_tnode *parent, - const nghttp3_mem *mem) { - nghttp3_pq_init(&tnode->pq, cycle_less, mem); + uint64_t seq, uint8_t pri) { + assert(nghttp3_pri_uint8_urgency(pri) < NGHTTP3_URGENCY_LEVELS); tnode->pe.index = NGHTTP3_PQ_BAD_INDEX; tnode->nid = *nid; tnode->seq = seq; tnode->cycle = 0; - tnode->pending_penalty = 0; - tnode->weight = weight; - tnode->parent = parent; - tnode->first_child = NULL; - tnode->num_children = 0; - tnode->active = 0; - - if (parent) { - tnode->next_sibling = parent->first_child; - parent->first_child = tnode; - ++parent->num_children; - } else { - tnode->next_sibling = NULL; - } + tnode->pri = pri; } -void nghttp3_tnode_free(nghttp3_tnode *tnode) { nghttp3_pq_free(&tnode->pq); } - -int nghttp3_tnode_is_active(nghttp3_tnode *tnode) { - nghttp3_push_promise *pp; +void nghttp3_tnode_free(nghttp3_tnode *tnode) { (void)tnode; } - switch (tnode->nid.type) { - case NGHTTP3_NODE_ID_TYPE_STREAM: - return nghttp3_stream_is_active( - nghttp3_struct_of(tnode, nghttp3_stream, node)); - case NGHTTP3_NODE_ID_TYPE_PUSH: - pp = nghttp3_struct_of(tnode, nghttp3_push_promise, node); - return pp->stream && nghttp3_stream_is_active(pp->stream); - case NGHTTP3_NODE_ID_TYPE_UT: - /* For unit test */ - return tnode->active; - default: - return 0; - } -} - -static void tnode_unschedule(nghttp3_tnode *tnode) { - nghttp3_tnode *parent; - - for (parent = tnode->parent; parent; tnode = parent, parent = tnode->parent) { - assert(tnode->pe.index != NGHTTP3_PQ_BAD_INDEX); - - nghttp3_pq_remove(&parent->pq, &tnode->pe); - tnode->pe.index = NGHTTP3_PQ_BAD_INDEX; - - if (nghttp3_tnode_is_active(parent) || !nghttp3_pq_empty(&parent->pq)) { - return; - } - } -} - -void nghttp3_tnode_unschedule(nghttp3_tnode *tnode) { - if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX || - !nghttp3_pq_empty(&tnode->pq)) { - return; - } +static void tnode_unschedule(nghttp3_tnode *tnode, nghttp3_pq *pq) { + assert(tnode->pe.index != NGHTTP3_PQ_BAD_INDEX); - tnode_unschedule(tnode); + nghttp3_pq_remove(pq, &tnode->pe); + tnode->pe.index = NGHTTP3_PQ_BAD_INDEX; } -void nghttp3_tnode_unschedule_detach(nghttp3_tnode *tnode) { +void nghttp3_tnode_unschedule(nghttp3_tnode *tnode, nghttp3_pq *pq) { if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) { return; } - tnode_unschedule(tnode); -} - -static int tnode_schedule(nghttp3_tnode *tnode, nghttp3_tnode *parent, - uint64_t base_cycle, size_t nwrite) { - uint64_t penalty = - (uint64_t)nwrite * NGHTTP3_MAX_WEIGHT + tnode->pending_penalty; - - tnode->cycle = base_cycle + penalty / tnode->weight; - tnode->pending_penalty = (uint32_t)(penalty % tnode->weight); - - return nghttp3_pq_push(&parent->pq, &tnode->pe); + tnode_unschedule(tnode, pq); } -static uint64_t tnode_get_first_cycle(nghttp3_tnode *tnode) { +static uint64_t pq_get_first_cycle(nghttp3_pq *pq) { nghttp3_tnode *top; - if (nghttp3_pq_empty(&tnode->pq)) { + if (nghttp3_pq_empty(pq)) { return 0; } - top = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe); + top = nghttp3_struct_of(nghttp3_pq_top(pq), nghttp3_tnode, pe); return top->cycle; } -int nghttp3_tnode_schedule(nghttp3_tnode *tnode, size_t nwrite) { - nghttp3_tnode *parent; - uint64_t cycle; - int rv; +int nghttp3_tnode_schedule(nghttp3_tnode *tnode, nghttp3_pq *pq, + size_t nwrite) { + uint64_t penalty = nwrite / NGHTTP3_STREAM_MIN_WRITELEN; - for (parent = tnode->parent; parent; tnode = parent, parent = tnode->parent) { - if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) { - cycle = tnode_get_first_cycle(parent); - } else if (nwrite != 0) { - cycle = tnode->cycle; - nghttp3_pq_remove(&parent->pq, &tnode->pe); - tnode->pe.index = NGHTTP3_PQ_BAD_INDEX; - } else { + if (tnode->pe.index == NGHTTP3_PQ_BAD_INDEX) { + tnode->cycle = pq_get_first_cycle(pq) + + ((nwrite == 0 || !nghttp3_pri_uint8_inc(tnode->pri)) + ? 0 + : nghttp3_max(1, penalty)); + } else if (nwrite > 0) { + if (!nghttp3_pri_uint8_inc(tnode->pri) || nghttp3_pq_size(pq) == 1) { return 0; } - rv = tnode_schedule(tnode, parent, cycle, nwrite); - if (rv != 0) { - return rv; - } + nghttp3_pq_remove(pq, &tnode->pe); + tnode->pe.index = NGHTTP3_PQ_BAD_INDEX; + tnode->cycle += nghttp3_max(1, penalty); + } else { + return 0; } - return 0; + return nghttp3_pq_push(pq, &tnode->pe); } int nghttp3_tnode_is_scheduled(nghttp3_tnode *tnode) { return tnode->pe.index != NGHTTP3_PQ_BAD_INDEX; } - -nghttp3_tnode *nghttp3_tnode_get_next(nghttp3_tnode *tnode) { - if (nghttp3_pq_empty(&tnode->pq)) { - return NULL; - } - - tnode = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe); - - for (;;) { - if (nghttp3_tnode_is_active(tnode)) { - return tnode; - } - assert(!nghttp3_pq_empty(&tnode->pq)); - tnode = nghttp3_struct_of(nghttp3_pq_top(&tnode->pq), nghttp3_tnode, pe); - assert(tnode); - } -} - -void nghttp3_tnode_insert(nghttp3_tnode *tnode, nghttp3_tnode *parent) { - assert(tnode->parent == NULL); - assert(tnode->next_sibling == NULL); - assert(tnode->pe.index == NGHTTP3_PQ_BAD_INDEX); - - tnode->next_sibling = parent->first_child; - parent->first_child = tnode; - tnode->parent = parent; - ++parent->num_children; -} - -int nghttp3_tnode_insert_exclusive(nghttp3_tnode *tnode, - nghttp3_tnode *parent) { - nghttp3_tnode **p, *node; - int rv; - - for (node = parent->first_child; node; node = node->next_sibling) { - node->parent = tnode; - - if (node->pe.index == NGHTTP3_PQ_BAD_INDEX) { - continue; - } - - nghttp3_pq_remove(&parent->pq, &node->pe); - node->pe.index = NGHTTP3_PQ_BAD_INDEX; - } - - for (p = &tnode->first_child; *p; p = &(*p)->next_sibling) - ; - - *p = parent->first_child; - parent->first_child = NULL; - tnode->num_children += parent->num_children; - parent->num_children = 0; - - nghttp3_tnode_insert(tnode, parent); - - for (node = *p; node; node = node->next_sibling) { - if (nghttp3_tnode_is_active(node) || - nghttp3_tnode_has_active_descendant(node)) { - rv = nghttp3_tnode_schedule(node, 0); - if (rv != 0) { - return rv; - } - } - } - - return 0; -} - -void nghttp3_tnode_remove(nghttp3_tnode *tnode) { - nghttp3_tnode *parent = tnode->parent, **p; - - assert(parent); - - if (tnode->pe.index != NGHTTP3_PQ_BAD_INDEX) { - nghttp3_tnode_unschedule_detach(tnode); - } - - for (p = &parent->first_child; *p != tnode; p = &(*p)->next_sibling) - ; - - *p = tnode->next_sibling; - --parent->num_children; - tnode->parent = tnode->next_sibling = NULL; -} - -int nghttp3_tnode_squash(nghttp3_tnode *tnode) { - nghttp3_tnode *parent = tnode->parent, *node, **p, *first, *end; - int rv; - - assert(parent); - - for (p = &parent->first_child; *p != tnode; p = &(*p)->next_sibling) - ; - - *p = tnode->first_child; - - for (; *p; p = &(*p)->next_sibling) { - node = *p; - node->parent = parent; - node->weight = - (uint32_t)(node->weight * tnode->weight / tnode->num_children); - if (node->weight == 0) { - node->weight = 1; - } - - if (node->pe.index == NGHTTP3_PQ_BAD_INDEX) { - continue; - } - - nghttp3_pq_remove(&tnode->pq, &node->pe); - node->pe.index = NGHTTP3_PQ_BAD_INDEX; - } - - *p = tnode->next_sibling; - - first = tnode->first_child; - end = tnode->next_sibling; - - if (tnode->pe.index != NGHTTP3_PQ_BAD_INDEX) { - nghttp3_tnode_unschedule(tnode); - assert(tnode->pe.index == NGHTTP3_PQ_BAD_INDEX); - } - - parent->num_children += tnode->num_children; - tnode->num_children = 0; - tnode->parent = tnode->next_sibling = tnode->first_child = NULL; - - for (node = first; node && node != end; node = node->next_sibling) { - if (nghttp3_tnode_is_active(node) || - nghttp3_tnode_has_active_descendant(node)) { - rv = nghttp3_tnode_schedule(node, 0); - if (rv != 0) { - return rv; - } - } - } - - return 0; -} - -nghttp3_tnode *nghttp3_tnode_find_ascendant(nghttp3_tnode *tnode, - const nghttp3_node_id *nid) { - for (tnode = tnode->parent; tnode && !nghttp3_node_id_eq(nid, &tnode->nid); - tnode = tnode->parent) - ; - - return tnode; -} - -int nghttp3_tnode_has_active_descendant(nghttp3_tnode *tnode) { - return !nghttp3_pq_empty(&tnode->pq); -} diff --git a/deps/nghttp3/lib/nghttp3_tnode.h b/deps/nghttp3/lib/nghttp3_tnode.h index 8e1e5d5bdf9..bf861ed0409 100644 --- a/deps/nghttp3/lib/nghttp3_tnode.h +++ b/deps/nghttp3/lib/nghttp3_tnode.h @@ -33,17 +33,11 @@ #include "nghttp3_pq.h" -#define NGHTTP3_DEFAULT_WEIGHT 16 -#define NGHTTP3_MAX_WEIGHT 256 -#define NGHTTP3_TNODE_MAX_CYCLE_GAP ((1llu << 24) * 256 + 255) +#define NGHTTP3_TNODE_MAX_CYCLE_GAP (1llu << 24) typedef enum { NGHTTP3_NODE_ID_TYPE_STREAM = 0x00, NGHTTP3_NODE_ID_TYPE_PUSH = 0x01, - NGHTTP3_NODE_ID_TYPE_PLACEHOLDER = 0x02, - NGHTTP3_NODE_ID_TYPE_ROOT = 0x03, - /* NGHTTP3_NODE_ID_TYPE_UT is defined for unit test */ - NGHTTP3_NODE_ID_TYPE_UT = 0xff, } nghttp3_node_id_type; typedef struct { @@ -61,95 +55,31 @@ typedef struct nghttp3_tnode nghttp3_tnode; struct nghttp3_tnode { nghttp3_pq_entry pe; - nghttp3_pq pq; - nghttp3_tnode *parent; - nghttp3_tnode *first_child; - nghttp3_tnode *next_sibling; size_t num_children; nghttp3_node_id nid; uint64_t seq; uint64_t cycle; - uint32_t pending_penalty; - uint32_t weight; - /* active is defined for unit test and is nonzero if this node is - active. */ - int active; + /* pri is a stream priority produced by nghttp3_pri_to_uint8. */ + uint8_t pri; }; void nghttp3_tnode_init(nghttp3_tnode *tnode, const nghttp3_node_id *nid, - uint64_t seq, uint32_t weight, nghttp3_tnode *parent, - const nghttp3_mem *mem); + uint64_t seq, uint8_t pri); void nghttp3_tnode_free(nghttp3_tnode *tnode); -/* - * nghttp3_tnode_is_active returns nonzero if |tnode| is active. Only - * NGHTTP3_NODE_ID_TYPE_STREAM and NGHTTP3_NODE_ID_TYPE_PUSH (and - * NGHTTP3_NODE_ID_TYPE_UT for unit test) can become active. - */ -int nghttp3_tnode_is_active(nghttp3_tnode *tnode); - -void nghttp3_tnode_unschedule(nghttp3_tnode *tnode); - -/* - * nghttp3_tnode_unschedule_detach works like - * nghttp3_tnode_unschedule, but it removes |tnode| even if tnode->pq - * is not empty. - */ -void nghttp3_tnode_unschedule_detach(nghttp3_tnode *tnode); +void nghttp3_tnode_unschedule(nghttp3_tnode *tnode, nghttp3_pq *pq); /* * nghttp3_tnode_schedule schedules |tnode| using |nwrite| as penalty. * If |tnode| has already been scheduled, it is rescheduled by the * amount of |nwrite|. */ -int nghttp3_tnode_schedule(nghttp3_tnode *tnode, size_t nwrite); +int nghttp3_tnode_schedule(nghttp3_tnode *tnode, nghttp3_pq *pq, size_t nwrite); /* * nghttp3_tnode_is_scheduled returns nonzero if |tnode| is scheduled. */ int nghttp3_tnode_is_scheduled(nghttp3_tnode *tnode); -/* - * nghttp3_tnode_get_next returns node which has highest priority. - * This function returns NULL if there is no node. - */ -nghttp3_tnode *nghttp3_tnode_get_next(nghttp3_tnode *node); - -/* - * nghttp3_tnode_insert inserts |tnode| as a first child of |parent|. - * |tnode| might have its descendants. - */ -void nghttp3_tnode_insert(nghttp3_tnode *tnode, nghttp3_tnode *parent); - -/* - * nghttp3_tnode_insert_exclusive inserts |tnode| to |parent| as a - * distinct child. The existing direct children of |parent| become - * the children of |tnode|. - */ -int nghttp3_tnode_insert_exclusive(nghttp3_tnode *tnode, nghttp3_tnode *parent); - -/* - * nghttp3_tnode_remove removes |tnode| along with its subtree from - * its parent. - */ -void nghttp3_tnode_remove(nghttp3_tnode *tnode); - -/* - * nghttp3_tnode_squash removes |tnode| from its parent. The weight - * of |tnode| is distributed to the direct descendants of |tnode|. - * They are inserted to the former parent of |tnode|. - */ -int nghttp3_tnode_squash(nghttp3_tnode *tnode); - -/* - * nghttp3_tnode_find_ascendant returns an ascendant of |tnode| whose - * node ID is |nid|. If no such node exists, this function returns - * NULL. - */ -nghttp3_tnode *nghttp3_tnode_find_ascendant(nghttp3_tnode *tnode, - const nghttp3_node_id *nid); - -int nghttp3_tnode_has_active_descendant(nghttp3_tnode *tnode); - #endif /* NGHTTP3_TNODE_H */ |