# HG changeset patch # User Roman Arutyunyan # Date 1593693245 -10800 # Node ID c9538aef3211f6f8c686a2acd5feb3e360436c8c # Parent b0e81f49d7c0f202ffe23f036b5ab7ca64cd294a HTTP/3: refactored dynamic table implementation. Previously dynamic table was not functional because of zero limit on its size set by default. Now the following changes enable it: - new directives to set SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS - send settings with SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS to the client - send Insert Count Increment to the client - send Header Acknowledgement to the client - evict old dynamic table entries on overflow - decode Required Insert Count from client - block stream if Required Insert Count is not reached diff --git a/src/http/ngx_http_request.c b/src/http/ngx_http_request.c --- a/src/http/ngx_http_request.c +++ b/src/http/ngx_http_request.c @@ -223,7 +223,17 @@ ngx_http_init_connection(ngx_connection_ #if (NGX_HTTP_V3) if (c->type == SOCK_DGRAM) { - hc = ngx_pcalloc(c->pool, sizeof(ngx_http_v3_connection_t)); + ngx_http_v3_connection_t *h3c; + + h3c = ngx_pcalloc(c->pool, sizeof(ngx_http_v3_connection_t)); + if (h3c == NULL) { + ngx_http_close_connection(c); + return; + } + + ngx_queue_init(&h3c->blocked); + + hc = &h3c->hc; hc->quic = 1; hc->ssl = 1; @@ -414,6 +424,13 @@ ngx_http_quic_stream_handler(ngx_connect pc = c->qs->parent; h3c = pc->data; + if (!h3c->settings_sent) { + h3c->settings_sent = 1; + + /* TODO close QUIC connection on error */ + (void) ngx_http_v3_send_settings(c); + } + if (c->qs->id & NGX_QUIC_STREAM_UNIDIRECTIONAL) { ngx_http_v3_handle_client_uni_stream(c); return; @@ -1255,7 +1272,7 @@ ngx_http_process_request_line(ngx_event_ break; } - if (rc == NGX_DONE) { + if (rc == NGX_BUSY) { if (ngx_handle_read_event(rev, 0) != NGX_OK) { ngx_http_close_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR); return; diff --git a/src/http/v3/ngx_http_v3.h b/src/http/v3/ngx_http_v3.h --- a/src/http/v3/ngx_http_v3.h +++ b/src/http/v3/ngx_http_v3.h @@ -48,20 +48,8 @@ #define NGX_HTTP_V3_MAX_KNOWN_STREAM 6 #define NGX_HTTP_V3_DEFAULT_MAX_FIELD_SIZE 4096 - - -typedef struct { - ngx_quic_tp_t quic; - size_t max_field_size; -} ngx_http_v3_srv_conf_t; - - -typedef struct { - ngx_http_connection_t hc; - - ngx_array_t *dynamic; - ngx_connection_t *known_streams[NGX_HTTP_V3_MAX_KNOWN_STREAM]; -} ngx_http_v3_connection_t; +#define NGX_HTTP_V3_DEFAULT_MAX_TABLE_CAPACITY 16384 +#define NGX_HTTP_V3_DEFAULT_MAX_BLOCKED_STREAMS 16 #define ngx_http_v3_get_module_srv_conf(c, module) \ @@ -71,11 +59,39 @@ typedef struct { typedef struct { - ngx_str_t name; - ngx_str_t value; + ngx_quic_tp_t quic; + size_t max_field_size; + size_t max_table_capacity; + ngx_uint_t max_blocked_streams; +} ngx_http_v3_srv_conf_t; + + +typedef struct { + ngx_str_t name; + ngx_str_t value; } ngx_http_v3_header_t; +typedef struct { + ngx_http_v3_header_t **elts; + ngx_uint_t nelts; + ngx_uint_t base; + size_t size; + size_t capacity; +} ngx_http_v3_dynamic_table_t; + + +typedef struct { + ngx_http_connection_t hc; + ngx_http_v3_dynamic_table_t table; + ngx_queue_t blocked; + ngx_uint_t nblocked; + ngx_uint_t settings_sent; + /* unsigned settings_sent:1; */ + ngx_connection_t *known_streams[NGX_HTTP_V3_MAX_KNOWN_STREAM]; +} ngx_http_v3_connection_t; + + ngx_int_t ngx_http_v3_parse_request(ngx_http_request_t *r, ngx_buf_t *b); ngx_int_t ngx_http_v3_parse_header(ngx_http_request_t *r, ngx_buf_t *b, ngx_uint_t allow_underscores); @@ -88,6 +104,7 @@ uintptr_t ngx_http_v3_encode_varlen_int( uintptr_t ngx_http_v3_encode_prefix_int(u_char *p, uint64_t value, ngx_uint_t prefix); +ngx_int_t ngx_http_v3_send_settings(ngx_connection_t *c); void ngx_http_v3_handle_client_uni_stream(ngx_connection_t *c); ngx_int_t ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic, @@ -99,8 +116,12 @@ ngx_int_t ngx_http_v3_duplicate(ngx_conn ngx_int_t ngx_http_v3_ack_header(ngx_connection_t *c, ngx_uint_t stream_id); ngx_int_t ngx_http_v3_cancel_stream(ngx_connection_t *c, ngx_uint_t stream_id); ngx_int_t ngx_http_v3_inc_insert_count(ngx_connection_t *c, ngx_uint_t inc); -ngx_http_v3_header_t *ngx_http_v3_lookup_table(ngx_connection_t *c, - ngx_uint_t dynamic, ngx_uint_t index); +ngx_int_t ngx_http_v3_lookup_static(ngx_connection_t *c, ngx_uint_t index, + ngx_str_t *name, ngx_str_t *value); +ngx_int_t ngx_http_v3_lookup(ngx_connection_t *c, ngx_uint_t index, + ngx_str_t *name, ngx_str_t *value); +ngx_int_t ngx_http_v3_decode_insert_count(ngx_connection_t *c, + ngx_uint_t *insert_count); ngx_int_t ngx_http_v3_check_insert_count(ngx_connection_t *c, ngx_uint_t insert_count); ngx_int_t ngx_http_v3_set_param(ngx_connection_t *c, uint64_t id, diff --git a/src/http/v3/ngx_http_v3_module.c b/src/http/v3/ngx_http_v3_module.c --- a/src/http/v3/ngx_http_v3_module.c +++ b/src/http/v3/ngx_http_v3_module.c @@ -125,6 +125,20 @@ static ngx_command_t ngx_http_v3_comman offsetof(ngx_http_v3_srv_conf_t, max_field_size), NULL }, + { ngx_string("http3_max_table_capacity"), + NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_CONF_TAKE1, + ngx_conf_set_size_slot, + NGX_HTTP_SRV_CONF_OFFSET, + offsetof(ngx_http_v3_srv_conf_t, max_table_capacity), + NULL }, + + { ngx_string("http3_max_blocked_streams"), + NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_CONF_TAKE1, + ngx_conf_set_num_slot, + NGX_HTTP_SRV_CONF_OFFSET, + offsetof(ngx_http_v3_srv_conf_t, max_blocked_streams), + NULL }, + ngx_null_command }; @@ -276,6 +290,8 @@ ngx_http_v3_create_srv_conf(ngx_conf_t * v3cf->quic.retry = NGX_CONF_UNSET; v3cf->max_field_size = NGX_CONF_UNSET_SIZE; + v3cf->max_table_capacity = NGX_CONF_UNSET_SIZE; + v3cf->max_blocked_streams = NGX_CONF_UNSET_UINT; return v3cf; } @@ -342,6 +358,14 @@ ngx_http_v3_merge_srv_conf(ngx_conf_t *c prev->max_field_size, NGX_HTTP_V3_DEFAULT_MAX_FIELD_SIZE); + ngx_conf_merge_size_value(conf->max_table_capacity, + prev->max_table_capacity, + NGX_HTTP_V3_DEFAULT_MAX_TABLE_CAPACITY); + + ngx_conf_merge_uint_value(conf->max_blocked_streams, + prev->max_blocked_streams, + NGX_HTTP_V3_DEFAULT_MAX_BLOCKED_STREAMS); + return NGX_CONF_OK; } diff --git a/src/http/v3/ngx_http_v3_parse.c b/src/http/v3/ngx_http_v3_parse.c --- a/src/http/v3/ngx_http_v3_parse.c +++ b/src/http/v3/ngx_http_v3_parse.c @@ -10,6 +10,10 @@ #include +static ngx_int_t ngx_http_v3_parse_lookup(ngx_connection_t *c, + ngx_uint_t dynamic, ngx_uint_t index, ngx_str_t *name, ngx_str_t *value); + + ngx_int_t ngx_http_v3_parse_varlen_int(ngx_connection_t *c, ngx_http_v3_parse_varlen_int_t *st, u_char ch) @@ -144,6 +148,7 @@ ngx_http_v3_parse_headers(ngx_connection sw_start = 0, sw_length, sw_prefix, + sw_verify, sw_header_rep, sw_done }; @@ -195,8 +200,19 @@ ngx_http_v3_parse_headers(ngx_connection return NGX_ERROR; } + st->state = sw_verify; + break; + + case sw_verify: + + rc = ngx_http_v3_check_insert_count(c, st->prefix.insert_count); + if (rc != NGX_OK) { + return rc; + } + st->state = sw_header_rep; - break; + + /* fall through */ case sw_header_rep: @@ -228,6 +244,12 @@ done: ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 parse headers done"); + if (st->prefix.insert_count > 0) { + if (ngx_http_v3_client_ack_header(c, c->qs->id) != NGX_OK) { + return NGX_ERROR; + } + } + st->state = sw_start; return NGX_DONE; } @@ -286,6 +308,10 @@ ngx_http_v3_parse_header_block_prefix(ng done: + if (ngx_http_v3_decode_insert_count(c, &st->insert_count) != NGX_OK) { + return NGX_ERROR; + } + if (st->sign) { st->base = st->insert_count - st->delta_base - 1; } else { @@ -294,7 +320,7 @@ done: ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 parse header block prefix done " - "i:%ui, s:%ui, d:%ui, base:%uL", + "insert_count:%ui, sign:%ui, delta_base:%ui, base:%uL", st->insert_count, st->sign, st->delta_base, st->base); st->state = sw_start; @@ -479,7 +505,6 @@ ngx_int_t ngx_http_v3_parse_header_ri(ngx_connection_t *c, ngx_http_v3_parse_header_t *st, u_char ch) { - ngx_http_v3_header_t *h; enum { sw_start = 0, sw_index @@ -518,15 +543,14 @@ done: st->index = st->base - st->index - 1; } - h = ngx_http_v3_lookup_table(c, st->dynamic, st->index); - if (h == NULL) { + if (ngx_http_v3_parse_lookup(c, st->dynamic, st->index, &st->name, + &st->value) + != NGX_OK) + { return NGX_ERROR; } - st->name = h->name; - st->value = h->value; st->state = sw_start; - return NGX_DONE; } @@ -535,8 +559,7 @@ ngx_int_t ngx_http_v3_parse_header_lri(ngx_connection_t *c, ngx_http_v3_parse_header_t *st, u_char ch) { - ngx_int_t rc; - ngx_http_v3_header_t *h; + ngx_int_t rc; enum { sw_start = 0, sw_index, @@ -616,12 +639,12 @@ done: st->index = st->base - st->index - 1; } - h = ngx_http_v3_lookup_table(c, st->dynamic, st->index); - if (h == NULL) { + if (ngx_http_v3_parse_lookup(c, st->dynamic, st->index, &st->name, NULL) + != NGX_OK) + { return NGX_ERROR; } - st->name = h->name; st->state = sw_start; return NGX_DONE; } @@ -735,7 +758,6 @@ ngx_int_t ngx_http_v3_parse_header_pbi(ngx_connection_t *c, ngx_http_v3_parse_header_t *st, u_char ch) { - ngx_http_v3_header_t *h; enum { sw_start = 0, sw_index @@ -768,13 +790,13 @@ done: ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 parse header pbi done dynamic[+%ui]", st->index); - h = ngx_http_v3_lookup_table(c, 1, st->base + st->index); - if (h == NULL) { + if (ngx_http_v3_parse_lookup(c, 1, st->base + st->index, &st->name, + &st->value) + != NGX_OK) + { return NGX_ERROR; } - st->name = h->name; - st->value = h->value; st->state = sw_start; return NGX_DONE; } @@ -784,8 +806,7 @@ ngx_int_t ngx_http_v3_parse_header_lpbi(ngx_connection_t *c, ngx_http_v3_parse_header_t *st, u_char ch) { - ngx_int_t rc; - ngx_http_v3_header_t *h; + ngx_int_t rc; enum { sw_start = 0, sw_index, @@ -860,17 +881,57 @@ done: "http3 parse header lpbi done dynamic[+%ui] \"%V\"", st->index, &st->value); - h = ngx_http_v3_lookup_table(c, 1, st->base + st->index); - if (h == NULL) { + if (ngx_http_v3_parse_lookup(c, 1, st->base + st->index, &st->name, NULL) + != NGX_OK) + { return NGX_ERROR; } - st->name = h->name; st->state = sw_start; return NGX_DONE; } +static ngx_int_t +ngx_http_v3_parse_lookup(ngx_connection_t *c, ngx_uint_t dynamic, + ngx_uint_t index, ngx_str_t *name, ngx_str_t *value) +{ + u_char *p; + + if (!dynamic) { + return ngx_http_v3_lookup_static(c, index, name, value); + } + + if (ngx_http_v3_lookup(c, index, name, value) != NGX_OK) { + return NGX_ERROR; + } + + if (name) { + p = ngx_pnalloc(c->pool, name->len + 1); + if (p == NULL) { + return NGX_ERROR; + } + + ngx_memcpy(p, name->data, name->len); + p[name->len] = '\0'; + name->data = p; + } + + if (value) { + p = ngx_pnalloc(c->pool, value->len + 1); + if (p == NULL) { + return NGX_ERROR; + } + + ngx_memcpy(p, value->data, value->len); + p[value->len] = '\0'; + value->data = p; + } + + return NGX_OK; +} + + ngx_int_t ngx_http_v3_parse_control(ngx_connection_t *c, void *data, u_char ch) { @@ -1145,7 +1206,7 @@ done: "http3 parse encoder instruction done"); st->state = sw_start; - return NGX_DONE; + return NGX_AGAIN; } @@ -1429,7 +1490,7 @@ done: "http3 parse decoder instruction done"); st->state = sw_start; - return NGX_DONE; + return NGX_AGAIN; } diff --git a/src/http/v3/ngx_http_v3_request.c b/src/http/v3/ngx_http_v3_request.c --- a/src/http/v3/ngx_http_v3_request.c +++ b/src/http/v3/ngx_http_v3_request.c @@ -64,12 +64,18 @@ ngx_http_v3_parse_request(ngx_http_reque } while (b->pos < b->last) { - rc = ngx_http_v3_parse_headers(c, st, *b->pos++); + rc = ngx_http_v3_parse_headers(c, st, *b->pos); if (rc == NGX_ERROR) { goto failed; } + if (rc == NGX_BUSY) { + return NGX_BUSY; + } + + b->pos++; + if (rc == NGX_AGAIN) { continue; } diff --git a/src/http/v3/ngx_http_v3_streams.c b/src/http/v3/ngx_http_v3_streams.c --- a/src/http/v3/ngx_http_v3_streams.c +++ b/src/http/v3/ngx_http_v3_streams.c @@ -34,10 +34,6 @@ ngx_http_v3_handle_client_uni_stream(ngx { ngx_http_v3_uni_stream_t *us; - ngx_http_v3_get_uni_stream(c, NGX_HTTP_V3_STREAM_CONTROL); - ngx_http_v3_get_uni_stream(c, NGX_HTTP_V3_STREAM_ENCODER); - ngx_http_v3_get_uni_stream(c, NGX_HTTP_V3_STREAM_DECODER); - ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 new uni stream id:0x%uxL", c->qs->id); @@ -341,6 +337,56 @@ failed: ngx_int_t +ngx_http_v3_send_settings(ngx_connection_t *c) +{ + u_char *p, buf[NGX_HTTP_V3_VARLEN_INT_LEN * 6]; + size_t n; + ngx_connection_t *cc; + ngx_http_v3_srv_conf_t *v3cf; + ngx_http_v3_connection_t *h3c; + + ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 send settings"); + + cc = ngx_http_v3_get_uni_stream(c, NGX_HTTP_V3_STREAM_CONTROL); + if (cc == NULL) { + return NGX_ERROR; + } + + h3c = c->qs->parent->data; + v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, ngx_http_v3_module); + + n = ngx_http_v3_encode_varlen_int(NULL, + NGX_HTTP_V3_PARAM_MAX_TABLE_CAPACITY); + n += ngx_http_v3_encode_varlen_int(NULL, v3cf->max_table_capacity); + n += ngx_http_v3_encode_varlen_int(NULL, NGX_HTTP_V3_PARAM_BLOCKED_STREAMS); + n += ngx_http_v3_encode_varlen_int(NULL, v3cf->max_blocked_streams); + + p = (u_char *) ngx_http_v3_encode_varlen_int(buf, + NGX_HTTP_V3_FRAME_SETTINGS); + p = (u_char *) ngx_http_v3_encode_varlen_int(p, n); + p = (u_char *) ngx_http_v3_encode_varlen_int(p, + NGX_HTTP_V3_PARAM_MAX_TABLE_CAPACITY); + p = (u_char *) ngx_http_v3_encode_varlen_int(p, v3cf->max_table_capacity); + p = (u_char *) ngx_http_v3_encode_varlen_int(p, + NGX_HTTP_V3_PARAM_BLOCKED_STREAMS); + p = (u_char *) ngx_http_v3_encode_varlen_int(p, v3cf->max_blocked_streams); + n = p - buf; + + if (cc->send(cc, buf, n) != (ssize_t) n) { + goto failed; + } + + return NGX_OK; + +failed: + + ngx_http_v3_close_uni_stream(cc); + + return NGX_ERROR; +} + + +ngx_int_t ngx_http_v3_client_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic, ngx_uint_t index, ngx_str_t *value) { diff --git a/src/http/v3/ngx_http_v3_tables.c b/src/http/v3/ngx_http_v3_tables.c --- a/src/http/v3/ngx_http_v3_tables.c +++ b/src/http/v3/ngx_http_v3_tables.c @@ -10,10 +10,22 @@ #include -static ngx_array_t *ngx_http_v3_get_dynamic_table(ngx_connection_t *c); +#define ngx_http_v3_table_entry_size(n, v) ((n)->len + (v)->len + 32) + + +static ngx_int_t ngx_http_v3_evict(ngx_connection_t *c, size_t need); +static void ngx_http_v3_cleanup_table(void *data); +static void ngx_http_v3_unblock(void *data); static ngx_int_t ngx_http_v3_new_header(ngx_connection_t *c); +typedef struct { + ngx_queue_t queue; + ngx_connection_t *connection; + ngx_uint_t *nblocked; +} ngx_http_v3_block_t; + + static ngx_http_v3_header_t ngx_http_v3_static_table[] = { { ngx_string(":authority"), ngx_string("") }, @@ -148,89 +160,74 @@ ngx_int_t ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic, ngx_uint_t index, ngx_str_t *value) { - ngx_array_t *dt; - ngx_connection_t *pc; - ngx_http_v3_header_t *ref, *h; + ngx_str_t name; - ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0, - "http3 ref insert %s[$ui] \"%V\"", - dynamic ? "dynamic" : "static", index, value); + if (dynamic) { + ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 ref insert dynamic[%ui] \"%V\"", index, value); - pc = c->qs->parent; + if (ngx_http_v3_lookup(c, index, &name, NULL) != NGX_OK) { + return NGX_ERROR; + } - ref = ngx_http_v3_lookup_table(c, dynamic, index); - if (ref == NULL) { - return NGX_ERROR; - } + } else { + ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 ref insert static[%ui] \"%V\"", index, value); - dt = ngx_http_v3_get_dynamic_table(c); - if (dt == NULL) { - return NGX_ERROR; + if (ngx_http_v3_lookup_static(c, index, &name, NULL) != NGX_OK) { + return NGX_ERROR; + } } - h = ngx_array_push(dt); - if (h == NULL) { - return NGX_ERROR; - } - - h->name = ref->name; - - h->value.data = ngx_pstrdup(pc->pool, value); - if (h->value.data == NULL) { - h->value.len = 0; - return NGX_ERROR; - } - - h->value.len = value->len; - - if (ngx_http_v3_new_header(c) != NGX_OK) { - return NGX_ERROR; - } - - return NGX_OK; + return ngx_http_v3_insert(c, &name, value); } ngx_int_t -ngx_http_v3_insert(ngx_connection_t *c, ngx_str_t *name, - ngx_str_t *value) +ngx_http_v3_insert(ngx_connection_t *c, ngx_str_t *name, ngx_str_t *value) { - ngx_array_t *dt; - ngx_connection_t *pc; - ngx_http_v3_header_t *h; + u_char *p; + size_t size; + ngx_http_v3_header_t *h; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; - ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, - "http3 insert \"%V\":\"%V\"", name, value); + size = ngx_http_v3_table_entry_size(name, value); - pc = c->qs->parent; - - dt = ngx_http_v3_get_dynamic_table(c); - if (dt == NULL) { + if (ngx_http_v3_evict(c, size) != NGX_OK) { return NGX_ERROR; } - h = ngx_array_push(dt); - if (h == NULL) { + h3c = c->qs->parent->data; + dt = &h3c->table; + + ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 insert [%ui] \"%V\":\"%V\", size:%uz", + dt->base + dt->nelts, name, value, size); + + p = ngx_alloc(sizeof(ngx_http_v3_header_t) + name->len + value->len, + c->log); + if (p == NULL) { return NGX_ERROR; } - h->name.data = ngx_pstrdup(pc->pool, name); - if (h->name.data == NULL) { - h->name.len = 0; - h->value.len = 0; + h = (ngx_http_v3_header_t *) p; + + h->name.data = p + sizeof(ngx_http_v3_header_t); + h->name.len = name->len; + h->value.data = ngx_cpymem(h->name.data, name->data, name->len); + h->value.len = value->len; + ngx_memcpy(h->value.data, value->data, value->len); + + dt->elts[dt->nelts++] = h; + dt->size += size; + + /* TODO increment can be sent less often */ + + if (ngx_http_v3_client_inc_insert_count(c, 1) != NGX_OK) { return NGX_ERROR; } - h->name.len = name->len; - - h->value.data = ngx_pstrdup(pc->pool, value); - if (h->value.data == NULL) { - h->value.len = 0; - return NGX_ERROR; - } - - h->value.len = value->len; - if (ngx_http_v3_new_header(c) != NGX_OK) { return NGX_ERROR; } @@ -242,10 +239,120 @@ ngx_http_v3_insert(ngx_connection_t *c, ngx_int_t ngx_http_v3_set_capacity(ngx_connection_t *c, ngx_uint_t capacity) { + ngx_uint_t max, prev_max; + ngx_connection_t *pc; + ngx_pool_cleanup_t *cln; + ngx_http_v3_header_t **elts; + ngx_http_v3_srv_conf_t *v3cf; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; + ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 set capacity %ui", capacity); - /* XXX ignore capacity */ + pc = c->qs->parent; + h3c = pc->data; + v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, ngx_http_v3_module); + + if (capacity > v3cf->max_table_capacity) { + ngx_log_error(NGX_LOG_INFO, c->log, 0, + "client exceeded http3_max_table_capacity limit"); + return NGX_ERROR; + } + + dt = &h3c->table; + + if (dt->size > capacity) { + if (ngx_http_v3_evict(c, dt->size - capacity) != NGX_OK) { + return NGX_ERROR; + } + } + + max = capacity / 32; + prev_max = dt->capacity / 32; + + if (max > prev_max) { + elts = ngx_alloc(max * sizeof(void *), c->log); + if (elts == NULL) { + return NGX_ERROR; + } + + if (dt->elts == NULL) { + cln = ngx_pool_cleanup_add(pc->pool, 0); + if (cln == NULL) { + return NGX_ERROR; + } + + cln->handler = ngx_http_v3_cleanup_table; + cln->data = dt; + + } else { + ngx_memcpy(elts, dt->elts, dt->nelts * sizeof(void *)); + ngx_free(dt->elts); + } + + dt->elts = elts; + } + + dt->capacity = capacity; + + return NGX_OK; +} + + +static void +ngx_http_v3_cleanup_table(void *data) +{ + ngx_http_v3_dynamic_table_t *dt = data; + + ngx_uint_t n; + + for (n = 0; n < dt->nelts; n++) { + ngx_free(dt->elts[n]); + } + + ngx_free(dt->elts); +} + + +static ngx_int_t +ngx_http_v3_evict(ngx_connection_t *c, size_t need) +{ + size_t size, target; + ngx_uint_t n; + ngx_http_v3_header_t *h; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; + + h3c = c->qs->parent->data; + dt = &h3c->table; + + if (need > dt->capacity) { + ngx_log_error(NGX_LOG_ERR, c->log, 0, + "not enough dynamic table capacity"); + return NGX_ERROR; + } + + target = dt->capacity - need; + n = 0; + + while (dt->size > target) { + h = dt->elts[n++]; + size = ngx_http_v3_table_entry_size(&h->name, &h->value); + + ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 evict [%ui] \"%V\":\"%V\" size:%uz", + dt->base, &h->name, &h->value, size); + + ngx_free(h); + dt->size -= size; + } + + if (n) { + dt->nelts -= n; + dt->base += n; + ngx_memmove(dt->elts, &dt->elts[n], dt->nelts * sizeof(void *)); + } return NGX_OK; } @@ -254,33 +361,26 @@ ngx_http_v3_set_capacity(ngx_connection_ ngx_int_t ngx_http_v3_duplicate(ngx_connection_t *c, ngx_uint_t index) { - ngx_array_t *dt; - ngx_http_v3_header_t *ref, *h; + ngx_str_t name, value; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 duplicate %ui", index); - ref = ngx_http_v3_lookup_table(c, 1, index); - if (ref == NULL) { + h3c = c->qs->parent->data; + dt = &h3c->table; + + if (dt->base + dt->nelts <= index) { return NGX_ERROR; } - dt = ngx_http_v3_get_dynamic_table(c); - if (dt == NULL) { + index = dt->base + dt->nelts - 1 - index; + + if (ngx_http_v3_lookup(c, index, &name, &value) != NGX_OK) { return NGX_ERROR; } - h = ngx_array_push(dt); - if (h == NULL) { - return NGX_ERROR; - } - - *h = *ref; - - if (ngx_http_v3_new_header(c) != NGX_OK) { - return NGX_ERROR; - } - - return NGX_OK; + return ngx_http_v3_insert(c, &name, &value); } @@ -320,94 +420,237 @@ ngx_http_v3_inc_insert_count(ngx_connect } -static ngx_array_t * -ngx_http_v3_get_dynamic_table(ngx_connection_t *c) +ngx_int_t +ngx_http_v3_lookup_static(ngx_connection_t *c, ngx_uint_t index, + ngx_str_t *name, ngx_str_t *value) { - ngx_connection_t *pc; - ngx_http_v3_connection_t *h3c; + ngx_uint_t nelts; + ngx_http_v3_header_t *h; - pc = c->qs->parent; - h3c = pc->data; + nelts = sizeof(ngx_http_v3_static_table) + / sizeof(ngx_http_v3_static_table[0]); - if (h3c->dynamic) { - return h3c->dynamic; + if (index >= nelts) { + ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 static[%ui] lookup out of bounds: %ui", + index, nelts); + return NGX_ERROR; } - ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 create dynamic table"); + h = &ngx_http_v3_static_table[index]; + + ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 static[%ui] lookup \"%V\":\"%V\"", + index, &h->name, &h->value); - h3c->dynamic = ngx_array_create(pc->pool, 1, sizeof(ngx_http_v3_header_t)); + if (name) { + *name = h->name; + } - return h3c->dynamic; + if (value) { + *value = h->value; + } + + return NGX_OK; } -ngx_http_v3_header_t * -ngx_http_v3_lookup_table(ngx_connection_t *c, ngx_uint_t dynamic, - ngx_uint_t index) +ngx_int_t +ngx_http_v3_lookup(ngx_connection_t *c, ngx_uint_t index, ngx_str_t *name, + ngx_str_t *value) { - ngx_uint_t nelts; - ngx_array_t *dt; - ngx_http_v3_header_t *table; + ngx_http_v3_header_t *h; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; + + h3c = c->qs->parent->data; + dt = &h3c->table; + + if (index < dt->base || index - dt->base >= dt->nelts) { + ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 dynamic[%ui] lookup out of bounds: [%ui,%ui]", + index, dt->base, dt->base + dt->nelts); + return NGX_ERROR; + } + + h = dt->elts[index - dt->base]; + + ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 dynamic[%ui] lookup \"%V\":\"%V\"", + index, &h->name, &h->value); + + if (name) { + *name = h->name; + } + + if (value) { + *value = h->value; + } + + return NGX_OK; +} - ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 lookup %s[%ui]", - dynamic ? "dynamic" : "static", index); + +ngx_int_t +ngx_http_v3_decode_insert_count(ngx_connection_t *c, ngx_uint_t *insert_count) +{ + ngx_uint_t max_entries, full_range, max_value, + max_wrapped, req_insert_count; + ngx_http_v3_srv_conf_t *v3cf; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; + + /* QPACK 4.5.1.1. Required Insert Count */ + + if (*insert_count == 0) { + return NGX_OK; + } - if (dynamic) { - dt = ngx_http_v3_get_dynamic_table(c); - if (dt == NULL) { - return NULL; + h3c = c->qs->parent->data; + dt = &h3c->table; + + v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, ngx_http_v3_module); + + max_entries = v3cf->max_table_capacity / 32; + full_range = 2 * max_entries; + + if (*insert_count > full_range) { + return NGX_ERROR; + } + + max_value = dt->base + dt->nelts + max_entries; + max_wrapped = (max_value / full_range) * full_range; + req_insert_count = max_wrapped + *insert_count - 1; + + if (req_insert_count > max_value) { + if (req_insert_count <= full_range) { + return NGX_ERROR; } - table = dt->elts; - nelts = dt->nelts; + req_insert_count -= full_range; + } - } else { - table = ngx_http_v3_static_table; - nelts = sizeof(ngx_http_v3_static_table) - / sizeof(ngx_http_v3_static_table[0]); + if (req_insert_count == 0) { + return NGX_ERROR; } - if (index >= nelts) { - ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, - "http3 lookup out of bounds: %ui", nelts); - return NULL; - } + ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 decode insert_count %ui -> %ui", + *insert_count, req_insert_count); - ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 lookup \"%V\":\"%V\"", - &table[index].name, &table[index].value); + *insert_count = req_insert_count; - return &table[index]; + return NGX_OK; } ngx_int_t ngx_http_v3_check_insert_count(ngx_connection_t *c, ngx_uint_t insert_count) { - size_t n; - ngx_http_v3_connection_t *h3c; + size_t n; + ngx_connection_t *pc; + ngx_pool_cleanup_t *cln; + ngx_http_v3_block_t *block; + ngx_http_v3_srv_conf_t *v3cf; + ngx_http_v3_connection_t *h3c; + ngx_http_v3_dynamic_table_t *dt; - h3c = c->qs->parent->data; - n = h3c->dynamic ? h3c->dynamic->nelts : 0; + pc = c->qs->parent; + h3c = pc->data; + dt = &h3c->table; + + n = dt->base + dt->nelts; ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, - "http3 check insert count %ui/%ui", insert_count, n); + "http3 check insert count req:%ui, have:%ui", + insert_count, n); + + if (n >= insert_count) { + return NGX_OK; + } + + ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 block stream"); + + block = NULL; - if (n < insert_count) { - /* XXX how to get notified? */ - /* XXX wake all streams on any arrival to the encoder stream? */ - return NGX_AGAIN; + for (cln = c->pool->cleanup; cln; cln = cln->next) { + if (cln->handler == ngx_http_v3_unblock) { + block = cln->data; + break; + } + } + + if (block == NULL) { + cln = ngx_pool_cleanup_add(c->pool, sizeof(ngx_http_v3_block_t)); + if (cln == NULL) { + return NGX_ERROR; + } + + cln->handler = ngx_http_v3_unblock; + + block = cln->data; + block->queue.prev = NULL; + block->connection = c; + block->nblocked = &h3c->nblocked; } - return NGX_OK; + if (block->queue.prev == NULL) { + v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, + ngx_http_v3_module); + + if (h3c->nblocked == v3cf->max_blocked_streams) { + ngx_log_error(NGX_LOG_INFO, c->log, 0, + "client exceeded http3_max_blocked_streams limit"); + return NGX_ERROR; + } + + h3c->nblocked++; + ngx_queue_insert_tail(&h3c->blocked, &block->queue); + } + + ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 blocked:%ui", h3c->nblocked); + + return NGX_BUSY; +} + + +static void +ngx_http_v3_unblock(void *data) +{ + ngx_http_v3_block_t *block = data; + + if (block->queue.prev) { + ngx_queue_remove(&block->queue); + block->queue.prev = NULL; + (*block->nblocked)--; + } } static ngx_int_t ngx_http_v3_new_header(ngx_connection_t *c) { - ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 new dynamic header"); + ngx_queue_t *q; + ngx_connection_t *bc; + ngx_http_v3_block_t *block; + ngx_http_v3_connection_t *h3c; + + h3c = c->qs->parent->data; + + ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, + "http3 new dynamic header, blocked:%ui", h3c->nblocked); - /* XXX report all waiting streams of a new header */ + while (!ngx_queue_empty(&h3c->blocked)) { + q = ngx_queue_head(&h3c->blocked); + block = (ngx_http_v3_block_t *) q; + bc = block->connection; + + ngx_log_debug0(NGX_LOG_DEBUG_HTTP, bc->log, 0, "http3 unblock stream"); + + ngx_http_v3_unblock(block); + ngx_post_event(bc->read, &ngx_posted_events); + } return NGX_OK; }