Line data Source code
1 : #pragma once
2 :
3 : #include "envoy/config/common/matcher/v3/matcher.pb.h"
4 :
5 : #include "source/common/buffer/buffer_impl.h"
6 : #include "source/common/http/header_utility.h"
7 :
8 : namespace Envoy {
9 : namespace Extensions {
10 : namespace Common {
11 : namespace Matcher {
12 :
13 : class Matcher;
14 : using MatcherPtr = std::unique_ptr<Matcher>;
15 :
16 : /**
17 : * Base class for context used by individual matchers.
18 : * The context may be required by matchers which are called multiple times
19 : * and need to carry state between the calls. For example body matchers may
20 : * store information how any bytes of the body have been already processed
21 : * or what what has been already found in the body and what has yet to be found.
22 : */
23 : class MatcherCtx {
24 : public:
25 0 : virtual ~MatcherCtx() = default;
26 : };
27 :
28 : /**
29 : * Base class for all matchers.
30 : *
31 : * A high level note on the design of matching which is different from other matching in Envoy
32 : * due to a requirement to support streaming matching (match as new data arrives versus
33 : * calculating the match given all available data at once).
34 : * - The matching system is composed of a constant matching configuration. This is essentially
35 : * a tree of matchers given logical AND, OR, NOT, etc.
36 : * - A per-stream/request matching status must be kept in order to compute interim match status.
37 : * - In order to make this computationally efficient, the matching tree is kept in a vector, with
38 : * all references to other matchers implemented using an index into the vector. The vector is
39 : * effectively a preorder traversal flattened N-ary tree.
40 : * - The previous point allows the creation of a per-stream/request vector of match statuses of
41 : * the same size as the matcher vector. Then, when match status is updated given new
42 : * information, the vector of match statuses can be easily updated using the same indexes as in
43 : * the constant match configuration.
44 : * - Finally, a matches() function can be trivially implemented by looking in the status vector at
45 : * the index position that the current matcher is located in.
46 : */
47 : class Matcher {
48 : public:
49 : struct MatchStatus {
50 0 : bool operator==(const MatchStatus& rhs) const {
51 0 : return matches_ == rhs.matches_ && might_change_status_ == rhs.might_change_status_;
52 0 : }
53 :
54 : bool matches_{false}; // Does the matcher currently match?
55 : bool might_change_status_{true}; // Is it possible for matches_ to change in subsequent updates?
56 : std::unique_ptr<MatcherCtx> ctx_{}; // Context used by matchers to save interim context.
57 : };
58 :
59 : using MatchStatusVector = std::vector<MatchStatus>;
60 :
61 : /**
62 : * Base class constructor for a matcher.
63 : * @param matchers supplies the match tree vector being built.
64 : */
65 : Matcher(const std::vector<MatcherPtr>& matchers)
66 : // NOTE: This code assumes that the index for the matcher being constructed has already been
67 : // allocated, which is why my_index_ is set to size() - 1. See buildMatcher() in
68 : // matcher.cc.
69 0 : : my_index_(matchers.size() - 1) {}
70 :
71 0 : virtual ~Matcher() = default;
72 :
73 : /**
74 : * @return the matcher's index in the match tree vector (see above).
75 : */
76 0 : size_t index() { return my_index_; }
77 :
78 : /**
79 : * Update match status when a stream is created. This might be an HTTP stream, a TCP connection,
80 : * etc. This allows any matchers to flip to an initial state of true if applicable.
81 : */
82 : virtual void onNewStream(MatchStatusVector& statuses) const PURE;
83 :
84 : /**
85 : * Update match status given HTTP request headers.
86 : * @param request_headers supplies the request headers.
87 : * @param statuses supplies the per-stream-request match status vector which must be the same
88 : * size as the match tree vector (see above).
89 : */
90 : virtual void onHttpRequestHeaders(const Http::RequestHeaderMap& request_headers,
91 : MatchStatusVector& statuses) const PURE;
92 :
93 : /**
94 : * Update match status given HTTP request trailers.
95 : * @param request_trailers supplies the request trailers.
96 : * @param statuses supplies the per-stream-request match status vector which must be the same
97 : * size as the match tree vector (see above).
98 : */
99 : virtual void onHttpRequestTrailers(const Http::RequestTrailerMap& request_trailers,
100 : MatchStatusVector& statuses) const PURE;
101 :
102 : /**
103 : * Update match status given HTTP response headers.
104 : * @param response_headers supplies the response headers.
105 : * @param statuses supplies the per-stream-request match status vector which must be the same
106 : * size as the match tree vector (see above).
107 : */
108 : virtual void onHttpResponseHeaders(const Http::ResponseHeaderMap& response_headers,
109 : MatchStatusVector& statuses) const PURE;
110 :
111 : /**
112 : * Update match status given HTTP response trailers.
113 : * @param response_headers supplies the response trailers.
114 : * @param statuses supplies the per-stream-request match status vector which must be the same
115 : * size as the match tree vector (see above).
116 : */
117 : virtual void onHttpResponseTrailers(const Http::ResponseTrailerMap& response_trailers,
118 : MatchStatusVector& statuses) const PURE;
119 :
120 : /**
121 : * Update match status given HTTP request body.
122 : * @param data supplies the request body.
123 : * @param statuses supplies the per-stream-request match status vector which must be the same
124 : * size as the match tree vector (see above).
125 : */
126 : virtual void onRequestBody(const Buffer::Instance& data, MatchStatusVector& statuses) PURE;
127 :
128 : /**
129 : * Update match status given HTTP response body.
130 : * @param data supplies the response body.
131 : * @param statuses supplies the per-stream-request match status vector which must be the same
132 : * size as the match tree vector (see above).
133 : */
134 : virtual void onResponseBody(const Buffer::Instance& data, MatchStatusVector& statuses) PURE;
135 :
136 : /**
137 : * @return whether given currently available information, the matcher matches.
138 : * @param statuses supplies the per-stream-request match status vector which must be the same
139 : * size as the match tree vector (see above).
140 : */
141 0 : const MatchStatus& matchStatus(const MatchStatusVector& statuses) const {
142 0 : return statuses[my_index_];
143 0 : }
144 :
145 : protected:
146 : const size_t my_index_;
147 : };
148 :
149 : /**
150 : * Factory method to build a matcher given a match config. Calling this function may end
151 : * up recursively building many matchers, which will all be added to the passed in vector
152 : * of matchers. See the comments in matcher.h for the general structure of how matchers work.
153 : */
154 : void buildMatcher(const envoy::config::common::matcher::v3::MatchPredicate& match_config,
155 : std::vector<MatcherPtr>& matchers);
156 :
157 : /**
158 : * Base class for logic matchers that need to forward update calls to child matchers.
159 : */
160 : class LogicMatcherBase : public Matcher {
161 : public:
162 : using Matcher::Matcher;
163 :
164 0 : void onNewStream(MatchStatusVector& statuses) const override {
165 0 : updateLocalStatus(statuses,
166 0 : [](Matcher& m, MatchStatusVector& statuses) { m.onNewStream(statuses); });
167 0 : }
168 : void onHttpRequestHeaders(const Http::RequestHeaderMap& request_headers,
169 0 : MatchStatusVector& statuses) const override {
170 0 : updateLocalStatus(statuses, [&request_headers](Matcher& m, MatchStatusVector& statuses) {
171 0 : m.onHttpRequestHeaders(request_headers, statuses);
172 0 : });
173 0 : }
174 : void onHttpRequestTrailers(const Http::RequestTrailerMap& request_trailers,
175 0 : MatchStatusVector& statuses) const override {
176 0 : updateLocalStatus(statuses, [&request_trailers](Matcher& m, MatchStatusVector& statuses) {
177 0 : m.onHttpRequestTrailers(request_trailers, statuses);
178 0 : });
179 0 : }
180 : void onHttpResponseHeaders(const Http::ResponseHeaderMap& response_headers,
181 0 : MatchStatusVector& statuses) const override {
182 0 : updateLocalStatus(statuses, [&response_headers](Matcher& m, MatchStatusVector& statuses) {
183 0 : m.onHttpResponseHeaders(response_headers, statuses);
184 0 : });
185 0 : }
186 : void onHttpResponseTrailers(const Http::ResponseTrailerMap& response_trailers,
187 0 : MatchStatusVector& statuses) const override {
188 0 : updateLocalStatus(statuses, [&response_trailers](Matcher& m, MatchStatusVector& statuses) {
189 0 : m.onHttpResponseTrailers(response_trailers, statuses);
190 0 : });
191 0 : }
192 0 : void onRequestBody(const Buffer::Instance& data, MatchStatusVector& statuses) override {
193 0 : updateLocalStatus(statuses, [&data](Matcher& m, MatchStatusVector& statuses) {
194 0 : m.onRequestBody(data, statuses);
195 0 : });
196 0 : }
197 0 : void onResponseBody(const Buffer::Instance& data, MatchStatusVector& statuses) override {
198 0 : updateLocalStatus(statuses, [&data](Matcher& m, MatchStatusVector& statuses) {
199 0 : m.onResponseBody(data, statuses);
200 0 : });
201 0 : }
202 :
203 : protected:
204 : using UpdateFunctor = std::function<void(Matcher&, MatchStatusVector&)>;
205 : virtual void updateLocalStatus(MatchStatusVector& statuses,
206 : const UpdateFunctor& functor) const PURE;
207 : };
208 :
209 : /**
210 : * Matcher for implementing set logic.
211 : */
212 : class SetLogicMatcher : public LogicMatcherBase {
213 : public:
214 : enum class Type { And, Or };
215 :
216 : SetLogicMatcher(const envoy::config::common::matcher::v3::MatchPredicate::MatchSet& configs,
217 : std::vector<MatcherPtr>& matchers, Type type);
218 :
219 : private:
220 : void updateLocalStatus(MatchStatusVector& statuses, const UpdateFunctor& functor) const override;
221 :
222 : std::vector<MatcherPtr>& matchers_;
223 : std::vector<size_t> indexes_;
224 : const Type type_;
225 : };
226 :
227 : /**
228 : * Not matcher.
229 : */
230 : class NotMatcher : public LogicMatcherBase {
231 : public:
232 : NotMatcher(const envoy::config::common::matcher::v3::MatchPredicate& config,
233 : std::vector<MatcherPtr>& matchers);
234 :
235 : private:
236 : void updateLocalStatus(MatchStatusVector& statuses, const UpdateFunctor& functor) const override;
237 :
238 : std::vector<MatcherPtr>& matchers_;
239 : const size_t not_index_;
240 : };
241 :
242 : /**
243 : * A base class for a matcher that generally wants to return default values, but might override
244 : * a single update function.
245 : */
246 : class SimpleMatcher : public Matcher {
247 : public:
248 : using Matcher::Matcher;
249 :
250 0 : void onNewStream(MatchStatusVector&) const override {}
251 0 : void onHttpRequestHeaders(const Http::RequestHeaderMap&, MatchStatusVector&) const override {}
252 0 : void onHttpRequestTrailers(const Http::RequestTrailerMap&, MatchStatusVector&) const override {}
253 0 : void onHttpResponseHeaders(const Http::ResponseHeaderMap&, MatchStatusVector&) const override {}
254 0 : void onHttpResponseTrailers(const Http::ResponseTrailerMap&, MatchStatusVector&) const override {}
255 0 : void onRequestBody(const Buffer::Instance&, MatchStatusVector&) override {}
256 0 : void onResponseBody(const Buffer::Instance&, MatchStatusVector&) override {}
257 : };
258 :
259 : /**
260 : * Any matcher (always matches).
261 : */
262 : class AnyMatcher : public SimpleMatcher {
263 : public:
264 : using SimpleMatcher::SimpleMatcher;
265 :
266 0 : void onNewStream(MatchStatusVector& statuses) const override {
267 0 : statuses[my_index_].matches_ = true;
268 0 : statuses[my_index_].might_change_status_ = false;
269 0 : }
270 : };
271 :
272 : /**
273 : * Base class for the various HTTP header matchers.
274 : */
275 : class HttpHeaderMatcherBase : public SimpleMatcher {
276 : public:
277 : HttpHeaderMatcherBase(const envoy::config::common::matcher::v3::HttpHeadersMatch& config,
278 : const std::vector<MatcherPtr>& matchers);
279 :
280 : protected:
281 : void matchHeaders(const Http::HeaderMap& headers, MatchStatusVector& statuses) const;
282 :
283 : const std::vector<Http::HeaderUtility::HeaderDataPtr> headers_to_match_;
284 : };
285 :
286 : /**
287 : * HTTP request headers matcher.
288 : */
289 : class HttpRequestHeadersMatcher : public HttpHeaderMatcherBase {
290 : public:
291 : using HttpHeaderMatcherBase::HttpHeaderMatcherBase;
292 :
293 : void onHttpRequestHeaders(const Http::RequestHeaderMap& request_headers,
294 0 : MatchStatusVector& statuses) const override {
295 0 : matchHeaders(request_headers, statuses);
296 0 : }
297 : };
298 :
299 : /**
300 : * HTTP request trailers matcher.
301 : */
302 : class HttpRequestTrailersMatcher : public HttpHeaderMatcherBase {
303 : public:
304 : using HttpHeaderMatcherBase::HttpHeaderMatcherBase;
305 :
306 : void onHttpRequestTrailers(const Http::RequestTrailerMap& request_trailers,
307 0 : MatchStatusVector& statuses) const override {
308 0 : matchHeaders(request_trailers, statuses);
309 0 : }
310 : };
311 :
312 : /**
313 : * HTTP response headers matcher.
314 : */
315 : class HttpResponseHeadersMatcher : public HttpHeaderMatcherBase {
316 : public:
317 : using HttpHeaderMatcherBase::HttpHeaderMatcherBase;
318 :
319 : void onHttpResponseHeaders(const Http::ResponseHeaderMap& response_headers,
320 0 : MatchStatusVector& statuses) const override {
321 0 : matchHeaders(response_headers, statuses);
322 0 : }
323 : };
324 :
325 : /**
326 : * HTTP response trailers matcher.
327 : */
328 : class HttpResponseTrailersMatcher : public HttpHeaderMatcherBase {
329 : public:
330 : using HttpHeaderMatcherBase::HttpHeaderMatcherBase;
331 :
332 : void onHttpResponseTrailers(const Http::ResponseTrailerMap& response_trailers,
333 0 : MatchStatusVector& statuses) const override {
334 0 : matchHeaders(response_trailers, statuses);
335 0 : }
336 : };
337 :
338 : /**
339 : * Base class for body matchers.
340 : */
341 : class HttpBodyMatcherBase : public SimpleMatcher {
342 : public:
343 0 : HttpBodyMatcherBase(const std::vector<MatcherPtr>& matchers) : SimpleMatcher(matchers) {}
344 :
345 : protected:
346 : // Limit search to specified number of bytes.
347 : // Value equal to zero means no limit.
348 : uint32_t limit_{};
349 : };
350 :
351 : /**
352 : * Context is used by HttpGenericBodyMatcher to:
353 : * - track how many bytes has been processed
354 : * - track patterns which have been found
355 : * - store last several seen bytes of the HTTP body (when pattern starts at the end of previous body
356 : * chunk and continues at the beginning of the next body chunk)
357 : */
358 : class HttpGenericBodyMatcherCtx : public MatcherCtx {
359 : public:
360 : HttpGenericBodyMatcherCtx(const std::shared_ptr<std::vector<std::string>>& patterns,
361 : size_t overlap_size)
362 0 : : patterns_(patterns) {
363 0 : // Initialize overlap_ buffer's capacity to fit the longest pattern - 1.
364 0 : // The length of the longest pattern is known and passed here as overlap_size.
365 0 : patterns_index_.resize(patterns_->size());
366 0 : std::iota(patterns_index_.begin(), patterns_index_.end(), 0);
367 0 : overlap_.reserve(overlap_size);
368 0 : capacity_ = overlap_size;
369 0 : }
370 0 : ~HttpGenericBodyMatcherCtx() override = default;
371 :
372 : // The context is initialized per each http request. The patterns_
373 : // shared pointer attaches to matcher's list of patterns, so patterns
374 : // can be referenced without copying data.
375 : const std::shared_ptr<const std::vector<std::string>> patterns_;
376 : // List stores indexes of patterns in patterns_ shared memory which
377 : // still need to be located in the body. When a pattern is found
378 : // its index is removed from the list.
379 : // When all patterns have been found, the list is empty.
380 : std::list<uint32_t> patterns_index_;
381 : // Buffer to store the last bytes from previous body chunk(s).
382 : // It will store only as many bytes as is the length of the longest
383 : // pattern to be found minus 1.
384 : // It is necessary to locate patterns which are spread across 2 or more
385 : // body chunks.
386 : std::vector<char> overlap_;
387 : // capacity_ tells how many bytes should be buffered. overlap_'s initial
388 : // capacity is set to the length of the longest pattern - 1. As patterns
389 : // are found, there is a possibility that not as many bytes are required to be buffered.
390 : // It must be tracked outside of vector, because vector::reserve does not
391 : // change capacity when new value is lower than current capacity.
392 : uint32_t capacity_{};
393 : // processed_bytes_ tracks how many bytes of HTTP body have been processed.
394 : uint32_t processed_bytes_{};
395 : };
396 :
397 : class HttpGenericBodyMatcher : public HttpBodyMatcherBase {
398 : public:
399 : HttpGenericBodyMatcher(const envoy::config::common::matcher::v3::HttpGenericBodyMatch& config,
400 : const std::vector<MatcherPtr>& matchers);
401 :
402 : protected:
403 : void onBody(const Buffer::Instance&, MatchStatusVector&);
404 0 : void onNewStream(MatchStatusVector& statuses) const override {
405 0 : // Allocate a new context used for the new stream.
406 0 : statuses[my_index_].ctx_ =
407 0 : std::make_unique<HttpGenericBodyMatcherCtx>(patterns_, overlap_size_);
408 0 : statuses[my_index_].matches_ = false;
409 0 : statuses[my_index_].might_change_status_ = true;
410 0 : }
411 : bool locatePatternAcrossChunks(const std::string& pattern, const Buffer::Instance& data,
412 : const HttpGenericBodyMatcherCtx* ctx);
413 : void bufferLastBytes(const Buffer::Instance& data, HttpGenericBodyMatcherCtx* ctx);
414 :
415 : size_t calcLongestPatternSize(const std::list<uint32_t>& indexes) const;
416 : void resizeOverlapBuffer(HttpGenericBodyMatcherCtx* ctx);
417 :
418 : private:
419 : // The following fields are initialized based on matcher config and are used
420 : // by all HTTP matchers.
421 : // List of strings which body must contain to get match.
422 : std::shared_ptr<std::vector<std::string>> patterns_;
423 : // Stores the length of the longest pattern.
424 : size_t overlap_size_{};
425 : };
426 :
427 : class HttpRequestGenericBodyMatcher : public HttpGenericBodyMatcher {
428 : public:
429 : using HttpGenericBodyMatcher::HttpGenericBodyMatcher;
430 :
431 0 : void onRequestBody(const Buffer::Instance& data, MatchStatusVector& statuses) override {
432 0 : onBody(data, statuses);
433 0 : }
434 : };
435 :
436 : class HttpResponseGenericBodyMatcher : public HttpGenericBodyMatcher {
437 : public:
438 : using HttpGenericBodyMatcher::HttpGenericBodyMatcher;
439 :
440 0 : void onResponseBody(const Buffer::Instance& data, MatchStatusVector& statuses) override {
441 0 : onBody(data, statuses);
442 0 : }
443 : };
444 :
445 : } // namespace Matcher
446 : } // namespace Common
447 : } // namespace Extensions
448 : } // namespace Envoy
|
