On Thursday 22 June 2017 18:23:46 Vlad Krasnov via nginx-devel wrote:
> # HG changeset patch
> # User Vlad Krasnov <vlad@cloudflare.com>
> # Date 1498167669 25200
> # Thu Jun 22 14:41:09 2017 -0700
> # Node ID 895cea03ac21fb18d2c2ba32389cd67dc74ddbd0
> # Parent a39bc74873faf9e5bea616561b43f6ecc55229f9
> HTTP/2: add support for HPACK encoding
>
> Add support for full HPACK encoding as per RFC7541.
> This modification improves header compression ratio by 5-10% for the first
> response, and by 40-95% for consequential responses on the connection.
> The implementation is similar to the one used by Cloudflare.
>

First of all, there's no way for a patch to be committed with so
many style issues.

Please, examine how existing nginx sources are formatted and mimic
this style.



> diff -r a39bc74873fa -r 895cea03ac21 auto/modules
> --- a/auto/modules Mon Jun 19 14:25:42 2017 +0300
> +++ b/auto/modules Thu Jun 22 14:41:09 2017 -0700
> @@ -436,6 +436,10 @@
> . auto/module
> fi
>
> + if [ $HTTP_V2_HPACK_ENC = YES ]; then
> + have=NGX_HTTP_V2_HPACK_ENC . auto/have
> + fi
> +
> if :; then
> ngx_module_name=ngx_http_static_module
> ngx_module_incs=
> diff -r a39bc74873fa -r 895cea03ac21 auto/options
> --- a/auto/options Mon Jun 19 14:25:42 2017 +0300
> +++ b/auto/options Thu Jun 22 14:41:09 2017 -0700
> @@ -59,6 +59,7 @@
> HTTP_GZIP=YES
> HTTP_SSL=NO
> HTTP_V2=NO
> +HTTP_V2_HPACK_ENC=NO
> HTTP_SSI=YES
> HTTP_POSTPONE=NO
> HTTP_REALIP=NO
> @@ -221,6 +222,7 @@
>
> --with-http_ssl_module) HTTP_SSL=YES ;;
> --with-http_v2_module) HTTP_V2=YES ;;
> + --with-http_v2_hpack_enc) HTTP_V2_HPACK_ENC=YES ;;

What's the reason for conditional compilation?


> --with-http_realip_module) HTTP_REALIP=YES ;;
> --with-http_addition_module) HTTP_ADDITION=YES ;;
> --with-http_xslt_module) HTTP_XSLT=YES ;;
> @@ -430,6 +432,7 @@
>
> --with-http_ssl_module enable ngx_http_ssl_module
> --with-http_v2_module enable ngx_http_v2_module
> + --with-http_v2_hpack_enc enable ngx_http_v2_hpack_enc
> --with-http_realip_module enable ngx_http_realip_module
> --with-http_addition_module enable ngx_http_addition_module
> --with-http_xslt_module enable ngx_http_xslt_module
> diff -r a39bc74873fa -r 895cea03ac21 src/core/ngx_murmurhash.c
> --- a/src/core/ngx_murmurhash.c Mon Jun 19 14:25:42 2017 +0300
> +++ b/src/core/ngx_murmurhash.c Thu Jun 22 14:41:09 2017 -0700
> @@ -50,3 +50,63 @@
>
> return h;
> }
> +
> +
> +uint64_t
> +ngx_murmur_hash2_64(u_char *data, size_t len, uint64_t seed)
> +{
> + uint64_t h, k;
> +
> + h = seed ^ len;
> +
> + while (len >= 8) {
> + k = data[0];
> + k |= data[1] << 8;
> + k |= data[2] << 16;
> + k |= data[3] << 24;
> + k |= (uint64_t)data[4] << 32;
> + k |= (uint64_t)data[5] << 40;
> + k |= (uint64_t)data[6] << 48;
> + k |= (uint64_t)data[7] << 56;
> +
> + k *= 0xc6a4a7935bd1e995ull;
> + k ^= k >> 47;
> + k *= 0xc6a4a7935bd1e995ull;
> +
> + h ^= k;
> + h *= 0xc6a4a7935bd1e995ull;
> +
> + data += 8;
> + len -= 8;
> + }
> +
> + switch (len) {
> + case 7:
> + h ^= (uint64_t)data[6] << 48;
> + /* fall through */
> + case 6:
> + h ^= (uint64_t)data[5] << 40;
> + /* fall through */
> + case 5:
> + h ^= (uint64_t)data[4] << 32;
> + /* fall through */
> + case 4:
> + h ^= data[3] << 24;
> + /* fall through */
> + case 3:
> + h ^= data[2] << 16;
> + /* fall through */
> + case 2:
> + h ^= data[1] << 8;
> + /* fall through */
> + case 1:
> + h ^= data[0];
> + h *= 0xc6a4a7935bd1e995ull;
> + }
> +
> + h ^= h >> 47;
> + h *= 0xc6a4a7935bd1e995ull;
> + h ^= h >> 47;
> +
> + return h;
> +}
> diff -r a39bc74873fa -r 895cea03ac21 src/core/ngx_murmurhash.h
> --- a/src/core/ngx_murmurhash.h Mon Jun 19 14:25:42 2017 +0300
> +++ b/src/core/ngx_murmurhash.h Thu Jun 22 14:41:09 2017 -0700
> @@ -15,5 +15,7 @@
>
> uint32_t ngx_murmur_hash2(u_char *data, size_t len);
>
> +uint64_t ngx_murmur_hash2_64(u_char *data, size_t len, uint64_t seed);
> +
>
> #endif /* _NGX_MURMURHASH_H_INCLUDED_ */
> diff -r a39bc74873fa -r 895cea03ac21 src/http/v2/ngx_http_v2.c
> --- a/src/http/v2/ngx_http_v2.c Mon Jun 19 14:25:42 2017 +0300
> +++ b/src/http/v2/ngx_http_v2.c Thu Jun 22 14:41:09 2017 -0700
> @@ -245,6 +245,8 @@
>
> h2c->frame_size = NGX_HTTP_V2_DEFAULT_FRAME_SIZE;
>
> + h2c->max_hpack_table_size = NGX_HTTP_V2_DEFAULT_HPACK_TABLE_SIZE;
> +
> h2scf = ngx_http_get_module_srv_conf(hc->conf_ctx, ngx_http_v2_module);
>
> h2c->pool = ngx_create_pool(h2scf->pool_size, h2c->connection->log);
> @@ -2018,6 +2020,17 @@
> h2c->frame_size = value;
> break;
>
> + case NGX_HTTP_V2_HEADER_TABLE_SIZE_SETTING:
> +
> + if (value > NGX_HTTP_V2_MAX_HPACK_TABLE_SIZE) {
> + h2c->max_hpack_table_size = NGX_HTTP_V2_MAX_HPACK_TABLE_SIZE;
> + } else {
> + h2c->max_hpack_table_size = value;
> + }
> +
> + h2c->indicate_resize = 1;
> + break;
> +
> default:
> break;
> }
> diff -r a39bc74873fa -r 895cea03ac21 src/http/v2/ngx_http_v2.h
> --- a/src/http/v2/ngx_http_v2.h Mon Jun 19 14:25:42 2017 +0300
> +++ b/src/http/v2/ngx_http_v2.h Thu Jun 22 14:41:09 2017 -0700
> @@ -49,6 +49,13 @@
> #define NGX_HTTP_V2_MAX_WINDOW ((1U << 31) - 1)
> #define NGX_HTTP_V2_DEFAULT_WINDOW 65535
>
> +#define HPACK_ENC_HTABLE_SZ 128 /* better to keep a PoT < 64k */
> +#define HPACK_ENC_HTABLE_ENTRIES ((HPACK_ENC_HTABLE_SZ * 100) / 128)
> +#define HPACK_ENC_DYNAMIC_KEY_TBL_SZ 10 /* 10 is sufficient for most */
> +#define HPACK_ENC_MAX_ENTRY 512 /* longest header size to match */
> +
> +#define NGX_HTTP_V2_DEFAULT_HPACK_TABLE_SIZE 4096
> +#define NGX_HTTP_V2_MAX_HPACK_TABLE_SIZE 16384 /* < 64k */
>
> typedef struct ngx_http_v2_connection_s ngx_http_v2_connection_t;
> typedef struct ngx_http_v2_node_s ngx_http_v2_node_t;
> @@ -110,6 +117,46 @@
> } ngx_http_v2_hpack_t;
>
>
> +#if (NGX_HTTP_V2_HPACK_ENC)
> +typedef struct {
> + uint64_t hash_val;
> + uint32_t index;
> + uint16_t pos;
> + uint16_t klen, vlen;
> + uint16_t size;
> + uint16_t next;
> +} ngx_http_v2_hpack_enc_entry_t;
> +
> +
> +typedef struct {
> + uint64_t hash_val;
> + uint32_t index;
> + uint16_t pos;
> + uint16_t klen;
> +} ngx_http_v2_hpack_name_entry_t;
> +
> +
> +typedef struct {
> + size_t size; /* size as defined in RFC 7541 */
> + uint32_t top; /* the last entry */
> + uint32_t pos;
> + uint16_t n_elems; /* number of elements */
> + uint16_t base; /* index of the oldest entry */
> + uint16_t last; /* index of the newest entry */
> +
> + /* hash table for dynamic entries, instead using a generic hash table,
> + which would be too slow to process a significant amount of headers,
> + this table is not determenistic, and might ocasionally fail to insert
> + a value, at the cost of slightly worse compression, but significantly
> + faster performance */

Have you considered rbtree as an option?


> + ngx_http_v2_hpack_enc_entry_t htable[HPACK_ENC_HTABLE_SZ];
> + ngx_http_v2_hpack_name_entry_t heads[HPACK_ENC_DYNAMIC_KEY_TBL_SZ];
> + u_char storage[NGX_HTTP_V2_MAX_HPACK_TABLE_SIZE +
> + HPACK_ENC_MAX_ENTRY];
> +} ngx_http_v2_hpack_enc_t;
> +#endif
> +
> +

Well, it means that even idle connection will consume 18+ KB more
memory than before.

That doesn't look like a generic solution suitable for most of our users.
It should be at least configurable.

wbr, Valentin V. Bartenev

_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel