header: New HeaderMatcher and StringMatcher type - Contains by shivanshu21 · Pull Request #12623 · envoyproxy/envoy

shivanshu21 · 2020-08-12T23:52:55Z

Fixes: 12590

Signed-off-by: Shivanshu Goswami shigoswami@ebay.com

For an explanation of how to fill out the fields, please see the relevant section
in PULL_REQUESTS.md

Commit Message: header: New HeaderMatcher type - Contains
Additional Description: For matching values in the header that might be somewhere in the middle of the header, the present option is to use Regex in the form .Search-Pattern.. This can cause catastrophic backtracking as described in #7728
As a solution, I have introduced another header match type called contains which is based on absl::StrContains().

Risk Level: Low
Testing: Unit tests are included and manual testing was performed.
Docs Changes:
Release Notes:
[Optional Runtime guard:]
[Optional Fixes #Issue]
[Optional Deprecated:]

repokitteh-read-only · 2020-08-12T23:53:01Z

CC @envoyproxy/api-shepherds: Your approval is needed for changes made to (api/envoy[\w/]*/(v1alpha\d?|v1|v2alpha\d?|v2))|(api/envoy/type/(matcher/)?\w+.proto).
CC @envoyproxy/api-shepherds: Your approval is needed for changes made to api/envoy/.
CC @envoyproxy/api-watchers: FYI only for changes made to api/envoy/.

🐱

Caused by: #12623 was opened by shivanshu21.

see: more, trace.

shivanshu21 · 2020-08-13T03:36:51Z

Tests passing in local

shigoswami@LM-SJL-11016036 ~/gitcode/envoy: /private/vbazel test -c opt //test/common/http:header_utility_test
INFO: Analyzed target //test/common/http:header_utility_test (0 packages loaded, 0 targets configured).
INFO: Found 1 test target...
Target //test/common/http:header_utility_test up-to-date:
  bazel-bin/test/common/http/header_utility_test
INFO: Elapsed time: 14.771s, Critical Path: 13.52s
INFO: 3 processes: 3 darwin-sandbox.
INFO: Build completed successfully, 4 total actions
//test/common/http:header_utility_test                                   PASSED in 0.1s

Executed 1 out of 1 test: 1 test passes.
INFO: Build completed successfully, 4 total actions
shigoswami@LM-SJL-11016036 ~/gitcode/envoy:

lizan · 2020-08-13T05:08:25Z

api/envoy/api/v2/route/route_components.proto

v2 is deprecated and freezed, no change is allowed in v2.

Removed v2 api changes.

htuch · 2020-08-13T16:03:31Z

api/envoy/api/v2/route/route_components.proto

I wonder if we just want to add support general globs, rather than special casing this.

@htuch This is being added for issue opened here: #12590

This is no more a special case than suffix-match or present-match. @htuch and @mattklein123 Later today I will add the same matcher for StringMatcher as well. Please let me know if we want to proceed this way.

Is there another PR or design doc available for wildcard based matches? Regex matching with std::regex can cause catastrophic backtracking and occasional crashes. Is there such a possibility with glob/wildcard matching too? Substring matches are O(n) as they are based on KMP.

@htuch I did a little more digging. I see that the Xray tracer extension has a wildcard match:
https://github.com/envoyproxy/envoy/pull/8526/files#diff-620892d553c2be71cf26761d0c9db408R26

I am still breaking it down but right now it looks like it supports ? and * which is good enough for our case.

Do you want just these two wildcards or a full set? If you're okay with this I can refactor the code a little to reuse the same matcher.

I think we would want a syntax more like #7763. Maybe we should go with a simple contains for now.

htuch · 2020-08-14T21:45:47Z

@shivanshu21 one other question, do you get catastophic backtracing with RE2 for this case? Do you know what the performance penalty of using RE2 vs. a strcontains operation is here?

shivanshu21 · 2020-08-14T22:28:47Z

@shivanshu21 one other question, do you get catastophic backtracing with RE2 for this case? Do you know what the performance penalty of using RE2 vs. a strcontains operation is here?

@htuch We haven't tried with Safe Regex as the definition says this:

(type.matcher.v3.RegexMatcher) If specified, this regex string is a regular expression rule which implies the entire request header value must match the regex. The rule will not match if only a subsequence of the request header value matches the regex.

The rule will not match if only a subsequence of the header matches the regex. So looks like strContains() case won't be handled here.

We have however tried comparing deprecated regex to RE2 and RE2 outperforms significantly.

shivanshu21 · 2020-08-14T22:33:03Z

Matchers test passing in local

shigoswami@LM-SJL-11016036 ~/gitcode/envoy: bazel test -c opt //test/common/common:matchers_test
INFO: Analyzed target //test/common/common:matchers_test (0 packages loaded, 0 targets configured).
INFO: Found 1 test target...
Target //test/common/common:matchers_test up-to-date:
  bazel-bin/test/common/common/matchers_test
INFO: Elapsed time: 12.590s, Critical Path: 11.52s
INFO: 3 processes: 3 darwin-sandbox.
INFO: Build completed successfully, 4 total actions
//test/common/common:matchers_test                                       PASSED in 0.1s

Executed 1 out of 1 test: 1 test passes.
INFO: Build completed successfully, 4 total actions

htuch · 2020-08-18T00:35:24Z

RE2 should work, as long as you glob at the start and end, e.g. .*<string>.*.

htuch · 2020-08-18T00:43:31Z

LGTM, but just want to check with other @envoyproxy/api-shepherds that this makes sense. I think that RE2 is not the right answer for performance here, but do we want to essentially open up arbitrary string predicates as first class API elements?

shivanshu21 · 2020-08-18T00:44:47Z

Thanks! I will wait for API shepherds to respond before merging.

shivanshu21 · 2020-08-18T20:47:52Z

@lizan PTAL

shivanshu21 · 2020-08-19T17:01:36Z

@envoyproxy/api-shepherds , @lizan This PR has been awaiting review. Please take a look.

lizan

API LGTM

lizan · 2020-08-19T21:00:28Z

source/common/common/matchers.cc

can we cache the lowered matcher_.contains somewhere for this case?

Fixes: 12590 Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

…string Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

shivanshu21 · 2020-08-20T00:08:22Z

Matchers and Header utility tests passing

Target //test/common/common:matchers_test up-to-date:
  bazel-bin/test/common/common/matchers_test
INFO: Elapsed time: 346.251s, Critical Path: 70.60s
INFO: 359 processes: 359 darwin-sandbox.
INFO: Build completed successfully, 385 total actions
//test/common/common:matchers_test                                       PASSED in 0.2s

Executed 1 out of 1 test: 1 test passes.
INFO: Build completed successfully, 385 total actions
shigoswami@LM-SJL-11016036 ~/gitcode/envoy:

shigoswami@LM-SJL-11016036 ~/gitcode/envoy: bazel test -c opt //test/common/http:header_utility_test
INFO: Analyzed target //test/common/http:header_utility_test (1 packages loaded, 2 targets configured).
INFO: Found 1 test target...
Target //test/common/http:header_utility_test up-to-date:
  bazel-bin/test/common/http/header_utility_test
INFO: Elapsed time: 17.793s, Critical Path: 17.06s
INFO: 3 processes: 3 darwin-sandbox.
INFO: Build completed successfully, 4 total actions
//test/common/http:header_utility_test                                   PASSED in 0.1s

Executed 1 out of 1 test: 1 test passes.
INFO: Build completed successfully, 4 total actions

@lizan I have added the lowercase string to the class so that it is only computed once. PTAL.

shivanshu21 · 2020-08-20T01:07:15Z

/retest

repokitteh-read-only · 2020-08-20T01:07:18Z

Retrying Azure Pipelines, to retry CircleCI checks, use /retest-circle.
Cannot retry non-completed check: envoy-presubmit (Linux-x64 compile_time_options), please wait.

🐱

Caused by: a #12623 (comment) was created by @shivanshu21.

see: more, trace.

htuch

LGTM but can you also add release notes? Thanks.

dio · 2020-08-20T12:25:05Z

docs/root/version_history/current.rst

Usually, we link the added field here. In this case, probably:

* matcher: added :ref:`contains <envoy_v3_api_field_type.matcher.v3.StringMatcher.contains>` to ...

And, it seems like you have another one for route as well.

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

shivanshu21 · 2020-08-20T22:49:23Z

@mattklein123 How do we remove the v2 api blocker labels? Merging is blocked because of that.

@lizan and Htuch have both LGTMed and Lizan has LGTMed for API changes as well.
There are No v2 api changes in this PR.

I have addressed all the comments including adding release notes with proper links.

mattklein123

LGTM with small comment, thanks!

/wait

mattklein123 · 2020-08-20T23:37:37Z

api/envoy/type/matcher/string.proto


 // Specifies the way to match a string.
-// [#next-free-field: 7]
+// [#next-free-field: 8]


This is still modifying a v2 API. Please revert this.

Oh! I thought all the v2 apis are in api/envoy/api/v2 folder. Reverting.

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

shivanshu21 · 2020-08-21T03:14:01Z

@mattklein123

Addressed the comment. Please take a look and suggest ways to unblock the merge.

shivanshu21 · 2020-08-21T19:19:33Z

Thanks Lizan! The API shepherds hold is removed.

But owing to this:

I cannot merge till @mattklein123 clicks this:

* envoy/master: (90 commits) cleanup: use structured binding (envoyproxy#12791) docs: fix header name for retries in gRPC services (envoyproxy#12790) docs: clarify meaning of HeaderValueOption.append (envoyproxy#12792) doc: clarify handling of duplicate xDS resource names (envoyproxy#12756) Dependencies: build updates. (envoyproxy#12786) Ratelimit: Add optional descriptor key to generic_key action (envoyproxy#12734) test: refactor header inclusion to speed up building (for test/mocks/upstream:upstream_mocks) (envoyproxy#12407) docs: Fix omitted word (envoyproxy#12782) ci: avoid uploading dwp as separate artifact (envoyproxy#12777) doc: Fix small typos (envoyproxy#12769) fix cache factory category (envoyproxy#12765) docs: fix typo v1.15.0.rst (envoyproxy#12680) Add clang-cl RBE toolchain for Windows (envoyproxy#12776) fuzz: add router fuzz proto (envoyproxy#12727) header: New HeaderMatcher and StringMatcher type - Contains (envoyproxy#12623) tcp_proxy: use dynamicMetadata() from StreamInfo for load balancing (envoyproxy#12595) network: add io handle recv function for http inspector (envoyproxy#12736) jwt_authn: supports jwt payload without "iss" field (envoyproxy#12744) Add support for nested JSON format in json logging mode (envoyproxy#12602) http: fixing a fuzz flake by setting details on connection teardown (envoyproxy#12737) ... Signed-off-by: Scott LaVigne <lavignes@amazon.com>

repokitteh-read-only bot added v2-freeze api labels Aug 12, 2020

shivanshu21 mentioned this pull request Aug 12, 2020

Introduce New header match type to avoid Regex - Contains #12590

Closed

lizan reviewed Aug 13, 2020

View reviewed changes

htuch reviewed Aug 13, 2020

View reviewed changes

shivanshu21 requested review from htuch and lizan August 13, 2020 21:04

shivanshu21 changed the title ~~[WIP] header: New HeaderMatcher type - Contains~~ header: New HeaderMatcher type - Contains Aug 14, 2020

shivanshu21 changed the title ~~header: New HeaderMatcher type - Contains~~ header: New HeaderMatcher and StringMatcher type - Contains Aug 14, 2020

jmarantz assigned htuch Aug 15, 2020

lizan reviewed Aug 19, 2020

View reviewed changes

source/common/common/matchers.cc Outdated

Copy link
Copy Markdown

Member

lizan Aug 19, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can we cache the lowered matcher_.contains somewhere for this case?

Shivanshu Goswami added 5 commits August 19, 2020 16:57

header: New HeaderMatcher type - Contains

2c17d1a

Fixes: 12590 Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

Fixing failing test

4e805d6

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

Remove changes from V2 api

3faedea

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

Adding contains match to string matcher

1d1f223

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

Addressing comments - Caching lowercase conversion of Contains match …

e498b89

…string Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

shivanshu21 requested a review from lizan August 20, 2020 00:37

htuch reviewed Aug 20, 2020

View reviewed changes

dio reviewed Aug 20, 2020

View reviewed changes

Updating release notes

dc28bef

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

mattklein123 requested changes Aug 20, 2020

View reviewed changes

repokitteh-read-only bot added the waiting label Aug 20, 2020

Reverting V2 api change for String matcher

d4cb21f

Signed-off-by: Shivanshu Goswami <shigoswami@ebay.com>

repokitteh-read-only bot removed the waiting label Aug 21, 2020

shivanshu21 requested a review from mattklein123 August 21, 2020 18:22

lizan approved these changes Aug 21, 2020

View reviewed changes

repokitteh-read-only bot removed the api label Aug 21, 2020

htuch approved these changes Aug 21, 2020

View reviewed changes

htuch merged commit e322daa into envoyproxy:master Aug 21, 2020

shivanshu21 deleted the contains branch August 21, 2020 20:13

Conversation

shivanshu21 commented Aug 12, 2020

Uh oh!

repokitteh-read-only bot commented Aug 12, 2020

Uh oh!

shivanshu21 commented Aug 13, 2020

Tests passing in local

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

htuch commented Aug 14, 2020

Uh oh!

shivanshu21 commented Aug 14, 2020

Uh oh!

shivanshu21 commented Aug 14, 2020

Matchers test passing in local

Uh oh!

htuch commented Aug 18, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

htuch commented Aug 18, 2020

Uh oh!

shivanshu21 commented Aug 18, 2020

Uh oh!

shivanshu21 commented Aug 18, 2020

Uh oh!

shivanshu21 commented Aug 19, 2020

Uh oh!

lizan left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

shivanshu21 commented Aug 20, 2020

Matchers and Header utility tests passing

Uh oh!

shivanshu21 commented Aug 20, 2020

Uh oh!

repokitteh-read-only bot commented Aug 20, 2020

Uh oh!

htuch left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dio Aug 20, 2020 • 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!

shivanshu21 commented Aug 20, 2020

Uh oh!

mattklein123 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

shivanshu21 commented Aug 21, 2020

Uh oh!

shivanshu21 commented Aug 21, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

htuch commented Aug 18, 2020 •

edited

Loading

dio Aug 20, 2020 •

edited

Loading