Line data    Source code

       1             : #include "source/extensions/tracers/xray/util.h"
       2             : 
       3             : #include "absl/strings/ascii.h"
       4             : 
       5             : namespace Envoy {
       6             : namespace Extensions {
       7             : namespace Tracers {
       8             : namespace XRay {
       9             : 
      10             : // AWS X-Ray has two sources of sampling rules (wildcard patterns):
      11             : //
      12             : // 1- The manifest file (static config)
      13             : // 2- The X-Ray Service - periodically polled for new rules. (dynamic config)
      14             : //
      15             : // X-Ray will inspect every single request and try to match it against the set of rules it has to
      16             : // decide whether or not a given request should be sampled. That means this wildcard matching
      17             : // routine is on the hot path. I've spent a great deal of time to make this function optimal and not
      18             : // allocate.
      19             : // Using regex matching here has many downsides and it would require us to:
      20             : // 1- escape/lint the user input pattern to avoid messing up its meaning (think '.' character is a
      21             : // valid regex and URL character) 2- compile the regex and store it with every corresponding part of
      22             : // the rule
      23             : //
      24             : // Those two steps would add significant overhead to the tracer. Meanwhile, the following function
      25             : // has a comprehensive test suite and fuzz tests.
      26          77 : bool wildcardMatch(absl::string_view pattern, absl::string_view input) {
      27          77 :   if (pattern.empty()) {
      28           0 :     return input.empty();
      29           0 :   }
      30             : 
      31             :   // Check the special case of a single * pattern, as it's common.
      32          77 :   constexpr char glob = '*';
      33          77 :   if (pattern.size() == 1 && pattern[0] == glob) {
      34           5 :     return true;
      35           5 :   }
      36             : 
      37          72 :   size_t i = 0, p = 0, i_star = input.size(), p_star = 0;
      38        2593 :   while (i < input.size()) {
      39        2537 :     if (p < pattern.size() && absl::ascii_tolower(input[i]) == absl::ascii_tolower(pattern[p])) {
      40        1158 :       ++i;
      41        1158 :       ++p;
      42        1379 :     } else if (p < pattern.size() && '?' == pattern[p]) {
      43         300 :       ++i;
      44         300 :       ++p;
      45        1079 :     } else if (p < pattern.size() && pattern[p] == glob) {
      46         217 :       i_star = i;
      47         217 :       p_star = p++;
      48         862 :     } else if (i_star != input.size()) {
      49         846 :       i = ++i_star;
      50         846 :       p = p_star + 1;
      51         846 :     } else {
      52          16 :       return false;
      53          16 :     }
      54        2537 :   }
      55             : 
      56          90 :   while (p < pattern.size() && pattern[p] == glob) {
      57          34 :     ++p;
      58          34 :   }
      59             : 
      60          56 :   return p == pattern.size() && i == input.size();
      61          72 : }
      62             : 
      63             : } // namespace XRay
      64             : } // namespace Tracers
      65             : } // namespace Extensions
      66             : } // namespace Envoy