Mercurial > hg > nginx
diff src/http/v3/ngx_http_v3_tables.c @ 8456:c9538aef3211 quic
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
author | Roman Arutyunyan <arut@nginx.com> |
---|---|
date | Thu, 02 Jul 2020 15:34:05 +0300 |
parents | 26cb2f3259b1 |
children | 72f9ff4e0a88 |
line wrap: on
line diff
--- a/src/http/v3/ngx_http_v3_tables.c Thu Jul 02 15:15:55 2020 +0300 +++ b/src/http/v3/ngx_http_v3_tables.c Thu Jul 02 15:34:05 2020 +0300 @@ -10,10 +10,22 @@ #include <ngx_http.h> -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_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_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_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 @@ } -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; }