http: make HeaderHashMethod hashing all the header values by soulxu · Pull Request #15486 · envoyproxy/envoy

soulxu · 2021-03-15T06:47:15Z

Commit Message: http: make HeaderHashMethod hashing all the header values

Additional Description:
Previously the HeaderHashMehod only hash the first value of the header.
This PR aims to hash all the values of the header. The new behavior also can be
disabled by the new runtime guard envoy.reloadable_features.hash_multiple_header_values.

Risk Level: low
Testing: unit-test added
Docs Changes: n/a
Release Notes: add note for new feature
Fixes #15182

Signed-off-by: He Jie Xu hejie.xu@intel.com

Previously the HeaderHashMehod only hash the first value of header. This commit aims to hash all the values of header. Signed-off-by: He Jie Xu <hejie.xu@intel.com>

source/common/http/hash_policy.cc

jmarantz · 2021-03-16T01:22:29Z

One quick note: I see you force-pushed earlier. Please refrain from doing that for Envoy github reviews; it loses comment threads. Just "merge main".

Thank you!

soulxu · 2021-03-22T06:14:21Z

One quick note: I see you force-pushed earlier. Please refrain from doing that for Envoy github reviews; it loses comment threads. Just "merge main".

Thanks for the reminder. I already that from my first PR. Actually, I force update it since it is the first push and no other comments yet. I will keep that in mind in later update.

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

source/common/common/hash.cc

source/common/http/hash_policy.cc

test/common/common/hash_test.cc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz

Code looks much better now, just a minor nit in the test remains.

test/common/router/config_impl_test.cc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz

Substantively LGTM. I think @snowp should look at this for its impact on load-balancing polices based on headers.

test/common/router/config_impl_test.cc

source/common/http/hash_policy.cc

jmarantz · 2021-03-31T12:53:24Z

Also I'm not sure what's up with CI. Can you merge main? Don't force-push.

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu · 2021-03-31T16:20:18Z

Also I'm not sure what's up with CI. Can you merge main? Don't force-push.

Done

source/common/http/BUILD

source/common/http/hash_policy.cc

test/common/router/config_impl_test.cc

source/common/http/hash_policy.cc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

test/common/http/async_client_impl_test.cc

source/common/http/hash_policy.cc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz

Looks great; just a few comments.

jmarantz · 2021-04-06T12:02:07Z

source/common/common/hash.h

+  static uint64_t xxHash64(absl::InlinedVector<absl::string_view, 1>& input, uint64_t seed = 0) {
+    uint64_t hash = seed;
+    if (input.size() == 0) {
+      hash = XXH64(input.data(), input.size(), hash);


does this case occur?

If so, just use XX64(nullptr, 0, seed)

Or maybe just don't test for that. Remove the if and let it return seed on an empty array.

We didn't use that case when hashing the header value, special with the check num_headers_to_hash:

envoy/source/common/http/hash_policy.cc

Line 71 in ce1e9a7

if (check_multiple_values && (num_headers_to_hash > 1)) {

I just match this behavior with static uint64_t xxHash64(absl::string_view input, uint64_t seed = 0) .
Then those two methods get the same value for empty string and empty vector, you can see that from the unittest

envoy/test/common/common/hash_test.cc

Lines 6 to 19 in ce1e9a7

TEST(Hash, xxHash) {

EXPECT_EQ(3728699739546630719U, HashUtil::xxHash64("foo"));

EXPECT_EQ(5234164152756840025U, HashUtil::xxHash64("bar"));

EXPECT_EQ(8917841378505826757U, HashUtil::xxHash64("foo\nbar"));

EXPECT_EQ(4400747396090729504U, HashUtil::xxHash64("lyft"));

EXPECT_EQ(17241709254077376921U, HashUtil::xxHash64(""));

}

TEST(Hash, xxHashWithVector) {

absl::InlinedVector<absl::string_view, 1> v{"foo", "bar"};

EXPECT_EQ(17745830980996999794U, HashUtil::xxHash64(v));

absl::InlinedVector<absl::string_view, 1> empty_vector;

EXPECT_EQ(17241709254077376921U, HashUtil::xxHash64(empty_vector));

}

The upside to handle this empty vector case is in case someone pass the empty vector, then it will get a same behavior just like the empty string one.

But I'm also ok to remove it if you think it needless to a case we didn't use it today.

source/common/common/hash.h

jmarantz · 2021-04-06T12:04:17Z

source/common/common/hash.h

+      hash = XXH64(input.data(), input.size(), hash);
+    } else {
+      for (auto& i : input) {
+        hash = XXH64(i.data(), i.size(), hash);


Nice I hadn't thought of using the seed arg to XX64 as a carry.

source/common/common/hash.h

jmarantz · 2021-04-06T12:08:19Z

source/common/http/hash_policy.cc

+        }
+      }
+
+      if (check_multiple_values && (num_headers_to_hash > 1)) {


I think Matt commented above but you don't need this conditional. num_headers_hash can be set to a value greater than one online if check_multiple_values is true, and the sorting will be a no-op for size==1.

that is what Matt is look for, better to have @mattklein123 check again. also I have comment about the runtime flag above, it may needn't this check anymore.

See my above comment. I think we do need the flag, but we can just set the size to 1 or not above and then we can collapse all of this logic.

I updated, hope I understand correctly.

test/common/http/async_client_impl_test.cc

source/common/http/hash_policy.cc

source/common/common/hash.h

source/common/http/hash_policy.cc

mattklein123 · 2021-04-06T17:53:55Z

source/common/http/hash_policy.cc

+        }
+      }
+
+      if (check_multiple_values && (num_headers_to_hash > 1)) {


See my above comment. I think we do need the flag, but we can just set the size to 1 or not above and then we can collapse all of this logic.

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz

Looks great, thank you! One tiny comment.

test/common/router/config_impl_test.cc

source/common/common/hash.h

source/common/common/hash.cc

source/common/http/hash_policy.cc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz

Perfect, thanks!

@snowp can do a final pass.

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

snowp

LGTM!

Can you merge main to pick up a CI fix?

mattklein123

Thanks LGTM. Will defer to others for merge.

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu · 2021-04-09T00:51:18Z

Thanks for all the review! just merged with main.

…#15486) Previously the HeaderHashMehod only hash the first value of header. This commit aims to hash all the values of header. Signed-off-by: He Jie Xu <hejie.xu@intel.com>

Make HeaderHashMethod hashing all the header values

163a273

Previously the HeaderHashMehod only hash the first value of header. This commit aims to hash all the values of header. Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu force-pushed the hash_all_values branch from c042b4b to 163a273 Compare March 15, 2021 09:33

soulxu changed the title ~~Make HeaderHashMethod hashing all the header values~~ http: make HeaderHashMethod hashing all the header values Mar 15, 2021

jmarantz reviewed Mar 15, 2021

View reviewed changes

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

jmarantz self-assigned this Mar 16, 2021

soulxu added 3 commits March 27, 2021 06:16

Address comments

21a088d

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

fix unittest

cd04222

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

update

629013c

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz reviewed Mar 29, 2021

View reviewed changes

source/common/common/hash.cc Show resolved Hide resolved

jmarantz reviewed Mar 29, 2021

View reviewed changes

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

jmarantz reviewed Mar 29, 2021

View reviewed changes

test/common/common/hash_test.cc Outdated Show resolved Hide resolved

soulxu added 3 commits March 30, 2021 06:19

Address comments

b7c57d3

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

improve the unittests

35164eb

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

fix format

c79d4ca

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz reviewed Mar 30, 2021

View reviewed changes

test/common/router/config_impl_test.cc Outdated Show resolved Hide resolved

test/common/router/config_impl_test.cc Show resolved Hide resolved

address comments

d8eea4f

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz reviewed Mar 31, 2021

View reviewed changes

jmarantz assigned snowp Mar 31, 2021

soulxu added 2 commits March 31, 2021 16:01

address comments

7296292

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

Merge branch 'main' into hash_all_values

8c03bb1

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu commented Mar 31, 2021

View reviewed changes

source/common/http/BUILD Outdated Show resolved Hide resolved

soulxu commented Mar 31, 2021

View reviewed changes

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

soulxu commented Mar 31, 2021

View reviewed changes

test/common/router/config_impl_test.cc Outdated Show resolved Hide resolved

jmarantz reviewed Mar 31, 2021

View reviewed changes

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

address comments

4ca2cdd

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz reviewed Apr 1, 2021

View reviewed changes

fix format

3ee5730

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

repokitteh-read-only bot removed the waiting label Apr 6, 2021

fix doc

ce1e9a7

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz reviewed Apr 6, 2021

View reviewed changes

soulxu commented Apr 6, 2021

View reviewed changes

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

mattklein123 requested changes Apr 6, 2021

View reviewed changes

mattklein123 added the waiting label Apr 6, 2021

address comments

94a4f0e

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

repokitteh-read-only bot removed the waiting label Apr 7, 2021

soulxu added 2 commits April 7, 2021 03:10

Merge branch 'main' into hash_all_values

9be2cdc

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

using empty()

81ac401

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz previously approved these changes Apr 7, 2021

View reviewed changes

test/common/router/config_impl_test.cc Outdated Show resolved Hide resolved

snowp suggested changes Apr 7, 2021

View reviewed changes

source/common/common/hash.h Outdated Show resolved Hide resolved

source/common/common/hash.cc Outdated Show resolved Hide resolved

source/common/http/hash_policy.cc Outdated Show resolved Hide resolved

source/common/http/hash_policy.cc Show resolved Hide resolved

mattklein123 added the waiting label Apr 7, 2021

address comments

43dbeb5

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu dismissed jmarantz’s stale review via 43dbeb5 April 8, 2021 00:22

repokitteh-read-only bot removed the waiting label Apr 8, 2021

address comment

cfa08d5

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

jmarantz previously approved these changes Apr 8, 2021

View reviewed changes

fix the test

f99f93b

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

soulxu dismissed jmarantz’s stale review via f99f93b April 8, 2021 01:21

jmarantz approved these changes Apr 8, 2021

View reviewed changes

snowp approved these changes Apr 8, 2021

View reviewed changes

mattklein123 approved these changes Apr 8, 2021

View reviewed changes

mattklein123 removed their assignment Apr 8, 2021

Merge branch 'main' into hash_all_values

964e602

Signed-off-by: He Jie Xu <hejie.xu@intel.com>

snowp merged commit 1f642ab into envoyproxy:main Apr 9, 2021

alyssawilk mentioned this pull request Jan 12, 2022

envoy.reloadable_features.hash_multiple_header_values deprecation #19504

Closed

	TEST(Hash, xxHash) {
	EXPECT_EQ(3728699739546630719U, HashUtil::xxHash64("foo"));
	EXPECT_EQ(5234164152756840025U, HashUtil::xxHash64("bar"));
	EXPECT_EQ(8917841378505826757U, HashUtil::xxHash64("foo\nbar"));
	EXPECT_EQ(4400747396090729504U, HashUtil::xxHash64("lyft"));
	EXPECT_EQ(17241709254077376921U, HashUtil::xxHash64(""));
	}

	TEST(Hash, xxHashWithVector) {
	absl::InlinedVector<absl::string_view, 1> v{"foo", "bar"};
	EXPECT_EQ(17745830980996999794U, HashUtil::xxHash64(v));
	absl::InlinedVector<absl::string_view, 1> empty_vector;
	EXPECT_EQ(17241709254077376921U, HashUtil::xxHash64(empty_vector));
	}

Conversation

soulxu commented Mar 15, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

jmarantz commented Mar 16, 2021

Uh oh!

soulxu commented Mar 22, 2021

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jmarantz left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

jmarantz left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jmarantz commented Mar 31, 2021

Uh oh!

soulxu commented Mar 31, 2021

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jmarantz left a comment

Choose a reason for hiding this comment

Uh oh!

jmarantz Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

jmarantz Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

soulxu Apr 6, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

jmarantz Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

jmarantz Apr 6, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

soulxu Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

mattklein123 Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

soulxu Apr 7, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mattklein123 Apr 6, 2021

Choose a reason for hiding this comment

Uh oh!

jmarantz left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

soulxu commented Mar 15, 2021 •

edited

Loading

soulxu Apr 6, 2021 •

edited

Loading

jmarantz Apr 6, 2021 •

edited

Loading