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>
# 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
http://mailman.nginx.org/mailman/listinfo/nginx-devel