> On Jul 24, 2017, at 11:42 AM, Valentin V. Bartenev <vbart@nginx.com> wrote:
>
> On Thursday 22 June 2017 18:23:46 Vlad Krasnov via nginx-devel wrote:
>> # HG changeset patch
>> # User Vlad Krasnov <vlad@cloudflare.com <mailto: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.

OK.

>
>
>
>> 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?

Internal reasons, but I decided to keep it in the patch, because maybe not everyone wants that overhead.

>
>
>> --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?

Yeah, I don’t think it would be faster.

>
>
>> + 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.
>

I can make it configurable fairly easily, but then it will require an extra allocation.

Cheers,
Vlad

> wbr, Valentin V. Bartenev
>
> _______________________________________________
> nginx-devel mailing list
> nginx-devel@nginx.org <mailto:nginx-devel@nginx.org>
> http://mailman.nginx.org/mailman/listinfo/nginx-devel http://mailman.nginx.org/mailman/listinfo/nginx-devel
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel