Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "envoy/matcher/matcher.h"
       4             : #include "envoy/network/filter.h"
       5             : #include "envoy/server/factory_context.h"
       6             : 
       7             : #include "source/common/matcher/matcher.h"
       8             : #include "source/common/network/lc_trie.h"
       9             : #include "source/common/network/utility.h"
      10             : 
      11             : #include "xds/type/matcher/v3/ip.pb.h"
      12             : #include "xds/type/matcher/v3/ip.pb.validate.h"
      13             : 
      14             : namespace Envoy {
      15             : namespace Extensions {
      16             : namespace Common {
      17             : namespace Matcher {
      18             : 
      19             : using ::Envoy::Matcher::DataInputFactoryCb;
      20             : using ::Envoy::Matcher::DataInputGetResult;
      21             : using ::Envoy::Matcher::DataInputPtr;
      22             : using ::Envoy::Matcher::evaluateMatch;
      23             : using ::Envoy::Matcher::MatchState;
      24             : using ::Envoy::Matcher::MatchTree;
      25             : using ::Envoy::Matcher::OnMatch;
      26             : using ::Envoy::Matcher::OnMatchFactory;
      27             : using ::Envoy::Matcher::OnMatchFactoryCb;
      28             : 
      29             : template <class DataType> struct TrieNode {
      30             :   size_t index_;
      31             :   uint32_t prefix_len_;
      32             :   bool exclusive_;
      33             :   std::shared_ptr<OnMatch<DataType>> on_match_;
      34             : 
      35           0 :   friend bool operator==(const TrieNode<DataType>& lhs, const TrieNode<DataType>& rhs) {
      36           0 :     return lhs.index_ == rhs.index_ && lhs.prefix_len_ == rhs.prefix_len_ &&
      37           0 :            lhs.exclusive_ == rhs.exclusive_ && lhs.on_match_ == rhs.on_match_;
      38           0 :   }
      39             :   template <typename H>
      40             :   friend H AbslHashValue(H h, // NOLINT(readability-identifier-naming)
      41           0 :                          const TrieNode<DataType>& node) {
      42           0 :     return H::combine(std::move(h), node.index_, node.prefix_len_, node.exclusive_, node.on_match_);
      43           0 :   }
      44             : };
      45             : 
      46             : template <class DataType> struct TrieNodeComparator {
      47           0 :   inline bool operator()(const TrieNode<DataType>& lhs, const TrieNode<DataType>& rhs) const {
      48           0 :     if (lhs.prefix_len_ > rhs.prefix_len_) {
      49           0 :       return true;
      50           0 :     }
      51           0 :     if (lhs.prefix_len_ == rhs.prefix_len_ && lhs.index_ < rhs.index_) {
      52           0 :       return true;
      53           0 :     }
      54           0 :     return false;
      55           0 :   }
      56             : };
      57             : 
      58             : /**
      59             :  * Implementation of a `sublinear` LC-trie matcher.
      60             :  */
      61             : template <class DataType> class TrieMatcher : public MatchTree<DataType> {
      62             : public:
      63             :   TrieMatcher(DataInputPtr<DataType>&& data_input, absl::optional<OnMatch<DataType>> on_no_match,
      64             :               const std::shared_ptr<Network::LcTrie::LcTrie<TrieNode<DataType>>>& trie)
      65           0 :       : data_input_(std::move(data_input)), on_no_match_(std::move(on_no_match)), trie_(trie) {
      66           0 :     auto input_type = data_input_->dataInputType();
      67           0 :     if (input_type != Envoy::Matcher::DefaultMatchingDataType) {
      68           0 :       throw EnvoyException(
      69           0 :           absl::StrCat("Unsupported data input type: ", input_type,
      70           0 :                        ", currently only string type is supported in trie matcher"));
      71           0 :     }
      72           0 :   }
      73             : 
      74           0 :   typename MatchTree<DataType>::MatchResult match(const DataType& data) override {
      75           0 :     const auto input = data_input_->get(data);
      76           0 :     if (input.data_availability_ != DataInputGetResult::DataAvailability::AllDataAvailable) {
      77           0 :       return {MatchState::UnableToMatch, absl::nullopt};
      78           0 :     }
      79           0 :     if (absl::holds_alternative<absl::monostate>(input.data_)) {
      80           0 :       return {MatchState::MatchComplete, on_no_match_};
      81           0 :     }
      82           0 :     const Network::Address::InstanceConstSharedPtr addr =
      83           0 :         Network::Utility::parseInternetAddressNoThrow(absl::get<std::string>(input.data_));
      84           0 :     if (!addr) {
      85           0 :       return {MatchState::MatchComplete, on_no_match_};
      86           0 :     }
      87           0 :     auto values = trie_->getData(addr);
      88             :     // The candidates returned by the LC trie are not in any specific order, so we
      89             :     // sort them by the prefix length first (longest first), and the order of declaration second.
      90           0 :     std::sort(values.begin(), values.end(), TrieNodeComparator<DataType>());
      91           0 :     bool first = true;
      92           0 :     for (const auto& node : values) {
      93           0 :       if (!first && node.exclusive_) {
      94           0 :         continue;
      95           0 :       }
      96           0 :       if (node.on_match_->action_cb_) {
      97           0 :         return {MatchState::MatchComplete, OnMatch<DataType>{node.on_match_->action_cb_, nullptr}};
      98           0 :       }
      99             :       // Resume any subtree matching to preserve backtracking progress.
     100           0 :       auto matched = evaluateMatch(*node.on_match_->matcher_, data);
     101           0 :       if (matched.match_state_ == MatchState::UnableToMatch) {
     102           0 :         return {MatchState::UnableToMatch, absl::nullopt};
     103           0 :       }
     104           0 :       if (matched.match_state_ == MatchState::MatchComplete && matched.result_) {
     105           0 :         return {MatchState::MatchComplete, OnMatch<DataType>{matched.result_, nullptr}};
     106           0 :       }
     107           0 :       if (first) {
     108           0 :         first = false;
     109           0 :       }
     110           0 :     }
     111           0 :     return {MatchState::MatchComplete, on_no_match_};
     112           0 :   }
     113             : 
     114             : private:
     115             :   const DataInputPtr<DataType> data_input_;
     116             :   const absl::optional<OnMatch<DataType>> on_no_match_;
     117             :   std::shared_ptr<Network::LcTrie::LcTrie<TrieNode<DataType>>> trie_;
     118             : };
     119             : 
     120             : template <class DataType>
     121             : class TrieMatcherFactoryBase : public ::Envoy::Matcher::CustomMatcherFactory<DataType> {
     122             : public:
     123             :   ::Envoy::Matcher::MatchTreeFactoryCb<DataType>
     124             :   createCustomMatcherFactoryCb(const Protobuf::Message& config,
     125             :                                Server::Configuration::ServerFactoryContext& factory_context,
     126             :                                DataInputFactoryCb<DataType> data_input,
     127             :                                absl::optional<OnMatchFactoryCb<DataType>> on_no_match,
     128           0 :                                OnMatchFactory<DataType>& on_match_factory) override {
     129           0 :     const auto& typed_config =
     130           0 :         MessageUtil::downcastAndValidate<const xds::type::matcher::v3::IPMatcher&>(
     131           0 :             config, factory_context.messageValidationVisitor());
     132           0 :     std::vector<OnMatchFactoryCb<DataType>> match_children;
     133           0 :     match_children.reserve(typed_config.range_matchers().size());
     134           0 :     for (const auto& range_matcher : typed_config.range_matchers()) {
     135           0 :       match_children.push_back(*on_match_factory.createOnMatch(range_matcher.on_match()));
     136           0 :     }
     137           0 :     std::vector<std::pair<TrieNode<DataType>, std::vector<Network::Address::CidrRange>>> data;
     138           0 :     data.reserve(match_children.size());
     139           0 :     size_t i = 0;
     140             :     // Ranges might have variable prefix length so we cannot combine them into one node because
     141             :     // then the matched prefix length cannot be determined.
     142           0 :     for (const auto& range_matcher : typed_config.range_matchers()) {
     143           0 :       auto on_match = std::make_shared<OnMatch<DataType>>(match_children[i++]());
     144           0 :       for (const auto& range : range_matcher.ranges()) {
     145           0 :         TrieNode<DataType> node = {i, range.prefix_len().value(), range_matcher.exclusive(),
     146           0 :                                    on_match};
     147           0 :         data.push_back({node, {Network::Address::CidrRange::create(range)}});
     148           0 :       }
     149           0 :     }
     150           0 :     auto lc_trie = std::make_shared<Network::LcTrie::LcTrie<TrieNode<DataType>>>(data);
     151           0 :     return [data_input, lc_trie, on_no_match]() {
     152           0 :       return std::make_unique<TrieMatcher<DataType>>(
     153           0 :           data_input(), on_no_match ? absl::make_optional(on_no_match.value()()) : absl::nullopt,
     154           0 :           lc_trie);
     155           0 :     };
     156           0 :   };
     157           2 :   ProtobufTypes::MessagePtr createEmptyConfigProto() override {
     158           2 :     return std::make_unique<xds::type::matcher::v3::IPMatcher>();
     159           2 :   }
     160          78 :   std::string name() const override { return "envoy.matching.custom_matchers.trie_matcher"; }
     161             : };
     162             : 
     163             : class NetworkTrieMatcherFactory : public TrieMatcherFactoryBase<Network::MatchingData> {};
     164             : class UdpNetworkTrieMatcherFactory : public TrieMatcherFactoryBase<Network::UdpMatchingData> {};
     165             : class HttpTrieMatcherFactory : public TrieMatcherFactoryBase<Http::HttpMatchingData> {};
     166             : 
     167             : } // namespace Matcher
     168             : } // namespace Common
     169             : } // namespace Extensions
     170             : } // namespace Envoy