Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : #include <config.h>
18 : : #include "classifier.h"
19 : : #include "classifier-private.h"
20 : : #include <errno.h>
21 : : #include <netinet/in.h>
22 : : #include "byte-order.h"
23 : : #include "openvswitch/dynamic-string.h"
24 : : #include "odp-util.h"
25 : : #include "openvswitch/ofp-util.h"
26 : : #include "packets.h"
27 : : #include "util.h"
28 : :
29 : : struct trie_ctx;
30 : :
31 : : /* A collection of "struct cls_conjunction"s currently embedded into a
32 : : * cls_match. */
33 : : struct cls_conjunction_set {
34 : : /* Link back to the cls_match.
35 : : *
36 : : * cls_conjunction_set is mostly used during classifier lookup, and, in
37 : : * turn, during classifier lookup the most used member of
38 : : * cls_conjunction_set is the rule's priority, so we cache it here for fast
39 : : * access. */
40 : : struct cls_match *match;
41 : : int priority; /* Cached copy of match->priority. */
42 : :
43 : : /* Conjunction information.
44 : : *
45 : : * 'min_n_clauses' allows some optimization during classifier lookup. */
46 : : unsigned int n; /* Number of elements in 'conj'. */
47 : : unsigned int min_n_clauses; /* Smallest 'n' among elements of 'conj'. */
48 : : struct cls_conjunction conj[];
49 : : };
50 : :
51 : : /* Ports trie depends on both ports sharing the same ovs_be32. */
52 : : #define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4)
53 : : BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4);
54 : : BUILD_ASSERT_DECL(TP_PORTS_OFS32 % 2 == 0);
55 : : #define TP_PORTS_OFS64 (TP_PORTS_OFS32 / 2)
56 : :
57 : : static size_t
58 : 1684 : cls_conjunction_set_size(size_t n)
59 : : {
60 : 1684 : return (sizeof(struct cls_conjunction_set)
61 : 1684 : + n * sizeof(struct cls_conjunction));
62 : : }
63 : :
64 : : static struct cls_conjunction_set *
65 : 490921 : cls_conjunction_set_alloc(struct cls_match *match,
66 : : const struct cls_conjunction conj[], size_t n)
67 : : {
68 [ + + ]: 490921 : if (n) {
69 : 1684 : size_t min_n_clauses = conj[0].n_clauses;
70 [ + + ]: 1691 : for (size_t i = 1; i < n; i++) {
71 : 7 : min_n_clauses = MIN(min_n_clauses, conj[i].n_clauses);
72 : : }
73 : :
74 : 1684 : struct cls_conjunction_set *set = xmalloc(cls_conjunction_set_size(n));
75 : 1684 : set->match = match;
76 : 1684 : set->priority = match->priority;
77 : 1684 : set->n = n;
78 : 1684 : set->min_n_clauses = min_n_clauses;
79 : 1684 : memcpy(set->conj, conj, n * sizeof *conj);
80 : 1684 : return set;
81 : : } else {
82 : 489237 : return NULL;
83 : : }
84 : : }
85 : :
86 : : static struct cls_match *
87 : 490921 : cls_match_alloc(const struct cls_rule *rule, ovs_version_t version,
88 : : const struct cls_conjunction conj[], size_t n)
89 : : {
90 : 490921 : size_t count = miniflow_n_values(rule->match.flow);
91 : :
92 : 490921 : struct cls_match *cls_match
93 : 490921 : = xmalloc(sizeof *cls_match + MINIFLOW_VALUES_SIZE(count));
94 : :
95 : 490921 : ovsrcu_init(&cls_match->next, NULL);
96 : 490921 : *CONST_CAST(const struct cls_rule **, &cls_match->cls_rule) = rule;
97 : 490921 : *CONST_CAST(int *, &cls_match->priority) = rule->priority;
98 : : /* Make rule initially invisible. */
99 : 490921 : cls_match->versions = VERSIONS_INITIALIZER(version, version);
100 : 490921 : miniflow_clone(CONST_CAST(struct miniflow *, &cls_match->flow),
101 : 490921 : rule->match.flow, count);
102 : 490921 : ovsrcu_set_hidden(&cls_match->conj_set,
103 : : cls_conjunction_set_alloc(cls_match, conj, n));
104 : :
105 : 490921 : return cls_match;
106 : : }
107 : :
108 : : static struct cls_subtable *find_subtable(const struct classifier *cls,
109 : : const struct minimask *);
110 : : static struct cls_subtable *insert_subtable(struct classifier *cls,
111 : : const struct minimask *);
112 : : static void destroy_subtable(struct classifier *cls, struct cls_subtable *);
113 : :
114 : : static const struct cls_match *find_match_wc(const struct cls_subtable *,
115 : : ovs_version_t version,
116 : : const struct flow *,
117 : : struct trie_ctx *,
118 : : unsigned int n_tries,
119 : : struct flow_wildcards *);
120 : : static struct cls_match *find_equal(const struct cls_subtable *,
121 : : const struct miniflow *, uint32_t hash);
122 : :
123 : : /* Return the next visible (lower-priority) rule in the list. Multiple
124 : : * identical rules with the same priority may exist transitionally, but when
125 : : * versioning is used at most one of them is ever visible for lookups on any
126 : : * given 'version'. */
127 : : static inline const struct cls_match *
128 : 3657 : next_visible_rule_in_list(const struct cls_match *rule, ovs_version_t version)
129 : : {
130 : : do {
131 : 3657 : rule = cls_match_next(rule);
132 [ + + ][ - + ]: 3657 : } while (rule && !cls_match_visible_in_version(rule, version));
133 : :
134 : 3657 : return rule;
135 : : }
136 : :
137 : : /* Type with maximum supported prefix length. */
138 : : union trie_prefix {
139 : : struct in6_addr ipv6; /* For sizing. */
140 : : ovs_be32 be32; /* For access. */
141 : : };
142 : :
143 : : static unsigned int minimask_get_prefix_len(const struct minimask *,
144 : : const struct mf_field *);
145 : : static void trie_init(struct classifier *cls, int trie_idx,
146 : : const struct mf_field *);
147 : : static unsigned int trie_lookup(const struct cls_trie *, const struct flow *,
148 : : union trie_prefix *plens);
149 : : static unsigned int trie_lookup_value(const rcu_trie_ptr *,
150 : : const ovs_be32 value[], ovs_be32 plens[],
151 : : unsigned int value_bits);
152 : : static void trie_destroy(rcu_trie_ptr *);
153 : : static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen);
154 : : static void trie_insert_prefix(rcu_trie_ptr *, const ovs_be32 *prefix,
155 : : int mlen);
156 : : static void trie_remove(struct cls_trie *, const struct cls_rule *, int mlen);
157 : : static void trie_remove_prefix(rcu_trie_ptr *, const ovs_be32 *prefix,
158 : : int mlen);
159 : : static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs,
160 : : unsigned int n_bits);
161 : : static bool mask_prefix_bits_set(const struct flow_wildcards *,
162 : : uint8_t be32ofs, unsigned int n_bits);
163 : :
164 : : /* cls_rule. */
165 : :
166 : : static inline void
167 : 572468 : cls_rule_init__(struct cls_rule *rule, unsigned int priority)
168 : : {
169 : 572468 : rculist_init(&rule->node);
170 : 572468 : *CONST_CAST(int *, &rule->priority) = priority;
171 : 572468 : ovsrcu_init(&rule->cls_match, NULL);
172 : 572468 : }
173 : :
174 : : /* Initializes 'rule' to match packets specified by 'match' at the given
175 : : * 'priority'. 'match' must satisfy the invariant described in the comment at
176 : : * the definition of struct match.
177 : : *
178 : : * The caller must eventually destroy 'rule' with cls_rule_destroy().
179 : : *
180 : : * Clients should not use priority INT_MIN. (OpenFlow uses priorities between
181 : : * 0 and UINT16_MAX, inclusive.) */
182 : : void
183 : 499353 : cls_rule_init(struct cls_rule *rule, const struct match *match, int priority)
184 : : {
185 : 499353 : cls_rule_init__(rule, priority);
186 : 499353 : minimatch_init(CONST_CAST(struct minimatch *, &rule->match), match);
187 : 499353 : }
188 : :
189 : : /* Same as cls_rule_init() for initialization from a "struct minimatch". */
190 : : void
191 : 5 : cls_rule_init_from_minimatch(struct cls_rule *rule,
192 : : const struct minimatch *match, int priority)
193 : : {
194 : 5 : cls_rule_init__(rule, priority);
195 : 5 : minimatch_clone(CONST_CAST(struct minimatch *, &rule->match), match);
196 : 5 : }
197 : :
198 : : /* Initializes 'dst' as a copy of 'src'.
199 : : *
200 : : * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
201 : : void
202 : 41090 : cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
203 : : {
204 : 41090 : cls_rule_init__(dst, src->priority);
205 : 41090 : minimatch_clone(CONST_CAST(struct minimatch *, &dst->match), &src->match);
206 : 41090 : }
207 : :
208 : : /* Initializes 'dst' with the data in 'src', destroying 'src'.
209 : : *
210 : : * 'src' must be a cls_rule NOT in a classifier.
211 : : *
212 : : * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
213 : : void
214 : 32020 : cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
215 : : {
216 : 32020 : cls_rule_init__(dst, src->priority);
217 : 32020 : minimatch_move(CONST_CAST(struct minimatch *, &dst->match),
218 : 32020 : CONST_CAST(struct minimatch *, &src->match));
219 : 32020 : }
220 : :
221 : : /* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's
222 : : * normally embedded into a larger structure).
223 : : *
224 : : * ('rule' must not currently be in a classifier.) */
225 : : void
226 : 476605 : cls_rule_destroy(struct cls_rule *rule)
227 : : OVS_NO_THREAD_SAFETY_ANALYSIS
228 : : {
229 : : /* Must not be in a classifier. */
230 [ - + ]: 476605 : ovs_assert(!get_cls_match_protected(rule));
231 : :
232 : : /* Check that the rule has been properly removed from the classifier. */
233 [ + + ][ - + ]: 476605 : ovs_assert(rule->node.prev == RCULIST_POISON
234 : : || rculist_is_empty(&rule->node));
235 : 476605 : rculist_poison__(&rule->node); /* Poisons also the next pointer. */
236 : :
237 : 476605 : minimatch_destroy(CONST_CAST(struct minimatch *, &rule->match));
238 : 476604 : }
239 : :
240 : : /* This may only be called by the exclusive writer. */
241 : : void
242 : 0 : cls_rule_set_conjunctions(struct cls_rule *cr,
243 : : const struct cls_conjunction *conj, size_t n)
244 : : {
245 : 0 : struct cls_match *match = get_cls_match_protected(cr);
246 : 0 : struct cls_conjunction_set *old
247 : 0 : = ovsrcu_get_protected(struct cls_conjunction_set *, &match->conj_set);
248 [ # # ]: 0 : struct cls_conjunction *old_conj = old ? old->conj : NULL;
249 [ # # ]: 0 : unsigned int old_n = old ? old->n : 0;
250 : :
251 [ # # ][ # # ]: 0 : if (old_n != n || (n && memcmp(old_conj, conj, n * sizeof *conj))) {
[ # # ]
252 [ # # ]: 0 : if (old) {
253 : 0 : ovsrcu_postpone(free, old);
254 : : }
255 : 0 : ovsrcu_set(&match->conj_set,
256 : : cls_conjunction_set_alloc(match, conj, n));
257 : : }
258 : 0 : }
259 : :
260 : :
261 : : /* Returns true if 'a' and 'b' match the same packets at the same priority,
262 : : * false if they differ in some way. */
263 : : bool
264 : 119156 : cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
265 : : {
266 [ + + ][ + - ]: 119156 : return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
267 : : }
268 : :
269 : : /* Appends a string describing 'rule' to 's'. */
270 : : void
271 : 8790 : cls_rule_format(const struct cls_rule *rule, struct ds *s)
272 : : {
273 : 8790 : minimatch_format(&rule->match, s, rule->priority);
274 : 8790 : }
275 : :
276 : : /* Returns true if 'rule' matches every packet, false otherwise. */
277 : : bool
278 : 270502 : cls_rule_is_catchall(const struct cls_rule *rule)
279 : : {
280 : 270502 : return minimask_is_catchall(rule->match.mask);
281 : : }
282 : :
283 : : /* Makes 'rule' invisible in 'remove_version'. Once that version is used in
284 : : * lookups, the caller should remove 'rule' via ovsrcu_postpone().
285 : : *
286 : : * 'rule' must be in a classifier.
287 : : * This may only be called by the exclusive writer. */
288 : : void
289 : 32102 : cls_rule_make_invisible_in_version(const struct cls_rule *rule,
290 : : ovs_version_t remove_version)
291 : : {
292 : 32102 : struct cls_match *cls_match = get_cls_match_protected(rule);
293 : :
294 [ - + ]: 32102 : ovs_assert(remove_version >= cls_match->versions.add_version);
295 : :
296 : 32102 : cls_match_set_remove_version(cls_match, remove_version);
297 : 32102 : }
298 : :
299 : : /* This undoes the change made by cls_rule_make_invisible_in_version().
300 : : *
301 : : * 'rule' must be in a classifier.
302 : : * This may only be called by the exclusive writer. */
303 : : void
304 : 0 : cls_rule_restore_visibility(const struct cls_rule *rule)
305 : : {
306 : 0 : cls_match_set_remove_version(get_cls_match_protected(rule),
307 : : OVS_VERSION_NOT_REMOVED);
308 : 0 : }
309 : :
310 : : /* Return true if 'rule' is visible in 'version'.
311 : : *
312 : : * 'rule' must be in a classifier. */
313 : : bool
314 : 1850516 : cls_rule_visible_in_version(const struct cls_rule *rule, ovs_version_t version)
315 : : {
316 : 1850516 : struct cls_match *cls_match = get_cls_match(rule);
317 : :
318 [ + ][ + + ]: 1850506 : return cls_match && cls_match_visible_in_version(cls_match, version);
319 : : }
320 : :
321 : : /* Initializes 'cls' as a classifier that initially contains no classification
322 : : * rules. */
323 : : void
324 : 440491 : classifier_init(struct classifier *cls, const uint8_t *flow_segments)
325 : : {
326 : 440491 : cls->n_rules = 0;
327 : 440491 : cmap_init(&cls->subtables_map);
328 : 440491 : pvector_init(&cls->subtables);
329 : 440491 : cls->n_flow_segments = 0;
330 [ + + ]: 440491 : if (flow_segments) {
331 [ + + ]: 835296 : while (cls->n_flow_segments < CLS_MAX_INDICES
332 [ + - ]: 626472 : && *flow_segments < FLOW_U64S) {
333 : 626472 : cls->flow_segments[cls->n_flow_segments++] = *flow_segments++;
334 : : }
335 : : }
336 : 440491 : cls->n_tries = 0;
337 [ + + ]: 1761964 : for (int i = 0; i < CLS_MAX_TRIES; i++) {
338 : 1321473 : trie_init(cls, i, NULL);
339 : : }
340 : 440491 : cls->publish = true;
341 : 440491 : }
342 : :
343 : : /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
344 : : * caller's responsibility.
345 : : * May only be called after all the readers have been terminated. */
346 : : void
347 : 279494 : classifier_destroy(struct classifier *cls)
348 : : {
349 [ + + ]: 279494 : if (cls) {
350 : : struct cls_subtable *subtable;
351 : : int i;
352 : :
353 [ + + ]: 376513 : for (i = 0; i < cls->n_tries; i++) {
354 : 97020 : trie_destroy(&cls->tries[i].root);
355 : : }
356 : :
357 [ - + ][ - + ]: 279493 : CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) {
358 : 0 : destroy_subtable(cls, subtable);
359 : : }
360 : 279493 : cmap_destroy(&cls->subtables_map);
361 : :
362 : 279493 : pvector_destroy(&cls->subtables);
363 : : }
364 : 279494 : }
365 : :
366 : : /* Set the fields for which prefix lookup should be performed. */
367 : : bool
368 : 1401940 : classifier_set_prefix_fields(struct classifier *cls,
369 : : const enum mf_field_id *trie_fields,
370 : : unsigned int n_fields)
371 : : {
372 : : const struct mf_field * new_fields[CLS_MAX_TRIES];
373 : 1401940 : struct mf_bitmap fields = MF_BITMAP_INITIALIZER;
374 : 1401940 : int i, n_tries = 0;
375 : 1401940 : bool changed = false;
376 : :
377 [ + + ][ + - ]: 4205817 : for (i = 0; i < n_fields && n_tries < CLS_MAX_TRIES; i++) {
378 : 2803877 : const struct mf_field *field = mf_from_id(trie_fields[i]);
379 [ + - ][ - + ]: 2803877 : if (field->flow_be32ofs < 0 || field->n_bits % 32) {
380 : : /* Incompatible field. This is the only place where we
381 : : * enforce these requirements, but the rest of the trie code
382 : : * depends on the flow_be32ofs to be non-negative and the
383 : : * field length to be a multiple of 32 bits. */
384 : 0 : continue;
385 : : }
386 : :
387 [ - + ]: 2803877 : if (bitmap_is_set(fields.bm, trie_fields[i])) {
388 : : /* Duplicate field, there is no need to build more than
389 : : * one index for any one field. */
390 : 0 : continue;
391 : : }
392 : 2803877 : bitmap_set1(fields.bm, trie_fields[i]);
393 : :
394 : 2803877 : new_fields[n_tries] = NULL;
395 [ + + ][ + + ]: 2803877 : if (n_tries >= cls->n_tries || field != cls->tries[n_tries].field) {
396 : 416282 : new_fields[n_tries] = field;
397 : 416282 : changed = true;
398 : : }
399 : 2803877 : n_tries++;
400 : : }
401 : :
402 [ + + ][ + + ]: 1401940 : if (changed || n_tries < cls->n_tries) {
403 : : struct cls_subtable *subtable;
404 : :
405 : : /* Trie configuration needs to change. Disable trie lookups
406 : : * for the tries that are changing and wait all the current readers
407 : : * with the old configuration to be done. */
408 : 208143 : changed = false;
409 [ + + ][ + + ]: 208153 : CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) {
410 [ + + ]: 25 : for (i = 0; i < cls->n_tries; i++) {
411 [ + + ][ + - ]: 15 : if ((i < n_tries && new_fields[i]) || i >= n_tries) {
[ + + ]
412 [ + + ]: 10 : if (subtable->trie_plen[i]) {
413 : 4 : subtable->trie_plen[i] = 0;
414 : 4 : changed = true;
415 : : }
416 : : }
417 : : }
418 : : }
419 : : /* Synchronize if any readers were using tries. The readers may
420 : : * temporarily function without the trie lookup based optimizations. */
421 [ + + ]: 208143 : if (changed) {
422 : : /* ovsrcu_synchronize() functions as a memory barrier, so it does
423 : : * not matter that subtable->trie_plen is not atomic. */
424 : 2 : ovsrcu_synchronize();
425 : : }
426 : :
427 : : /* Now set up the tries. */
428 [ + + ]: 624426 : for (i = 0; i < n_tries; i++) {
429 [ + + ]: 416283 : if (new_fields[i]) {
430 : 416282 : trie_init(cls, i, new_fields[i]);
431 : : }
432 : : }
433 : : /* Destroy the rest, if any. */
434 [ + + ]: 208145 : for (; i < cls->n_tries; i++) {
435 : 2 : trie_init(cls, i, NULL);
436 : : }
437 : :
438 : 208143 : cls->n_tries = n_tries;
439 : 208143 : return true;
440 : : }
441 : :
442 : 1401940 : return false; /* No change. */
443 : : }
444 : :
445 : : static void
446 : 1737757 : trie_init(struct classifier *cls, int trie_idx, const struct mf_field *field)
447 : : {
448 : 1737757 : struct cls_trie *trie = &cls->tries[trie_idx];
449 : : struct cls_subtable *subtable;
450 : :
451 [ + + ]: 1737757 : if (trie_idx < cls->n_tries) {
452 : 4 : trie_destroy(&trie->root);
453 : : } else {
454 : 1737753 : ovsrcu_set_hidden(&trie->root, NULL);
455 : : }
456 : 1737757 : trie->field = field;
457 : :
458 : : /* Add existing rules to the new trie. */
459 [ + + ][ + + ]: 1737767 : CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) {
460 : : unsigned int plen;
461 : :
462 [ - + ]: 10 : plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
463 [ - + ]: 10 : if (plen) {
464 : : struct cls_match *head;
465 : :
466 [ # # ][ # # ]: 0 : CMAP_FOR_EACH (head, cmap_node, &subtable->rules) {
467 : 0 : trie_insert(trie, head->cls_rule, plen);
468 : : }
469 : : }
470 : : /* Initialize subtable's prefix length on this field. This will
471 : : * allow readers to use the trie. */
472 : 10 : atomic_thread_fence(memory_order_release);
473 : 10 : subtable->trie_plen[trie_idx] = plen;
474 : : }
475 : 1737757 : }
476 : :
477 : : /* Returns true if 'cls' contains no classification rules, false otherwise.
478 : : * Checking the cmap requires no locking. */
479 : : bool
480 : 39558 : classifier_is_empty(const struct classifier *cls)
481 : : {
482 : 39558 : return cmap_is_empty(&cls->subtables_map);
483 : : }
484 : :
485 : : /* Returns the number of rules in 'cls'. */
486 : : int
487 : 65081 : classifier_count(const struct classifier *cls)
488 : : {
489 : : /* n_rules is an int, so in the presence of concurrent writers this will
490 : : * return either the old or a new value. */
491 : 65081 : return cls->n_rules;
492 : : }
493 : :
494 : 53222 : static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
495 : : {
496 : : /* Could optimize to use the same map if needed for fast path. */
497 [ + - ]: 106444 : return MINIFLOW_GET_BE32(match->flow, tp_src)
498 [ + - ]: 53222 : & MINIFLOW_GET_BE32(&match->mask->masks, tp_src);
499 : : }
500 : :
501 : : /* Inserts 'rule' into 'cls' in 'version'. Until 'rule' is removed from 'cls',
502 : : * the caller must not modify or free it.
503 : : *
504 : : * If 'cls' already contains an identical rule (including wildcards, values of
505 : : * fixed fields, and priority) that is visible in 'version', replaces the old
506 : : * rule by 'rule' and returns the rule that was replaced. The caller takes
507 : : * ownership of the returned rule and is thus responsible for destroying it
508 : : * with cls_rule_destroy(), after RCU grace period has passed (see
509 : : * ovsrcu_postpone()).
510 : : *
511 : : * Returns NULL if 'cls' does not contain a rule with an identical key, after
512 : : * inserting the new rule. In this case, no rules are displaced by the new
513 : : * rule, even rules that cannot have any effect because the new rule matches a
514 : : * superset of their flows and has higher priority.
515 : : */
516 : : const struct cls_rule *
517 : 490921 : classifier_replace(struct classifier *cls, const struct cls_rule *rule,
518 : : ovs_version_t version,
519 : : const struct cls_conjunction *conjs, size_t n_conjs)
520 : : {
521 : : struct cls_match *new;
522 : : struct cls_subtable *subtable;
523 : : uint32_t ihash[CLS_MAX_INDICES];
524 : : struct cls_match *head;
525 : : unsigned int mask_offset;
526 : 490921 : size_t n_rules = 0;
527 : : uint32_t basis;
528 : : uint32_t hash;
529 : : unsigned int i;
530 : :
531 : : /* 'new' is initially invisible to lookups. */
532 : 490921 : new = cls_match_alloc(rule, version, conjs, n_conjs);
533 : 490921 : ovsrcu_set(&CONST_CAST(struct cls_rule *, rule)->cls_match, new);
534 : :
535 : 490921 : subtable = find_subtable(cls, rule->match.mask);
536 [ + + ]: 490921 : if (!subtable) {
537 : 397033 : subtable = insert_subtable(cls, rule->match.mask);
538 : : }
539 : :
540 : : /* Compute hashes in segments. */
541 : 490921 : basis = 0;
542 : 490921 : mask_offset = 0;
543 [ + + ]: 607249 : for (i = 0; i < subtable->n_indices; i++) {
544 : 116328 : ihash[i] = minimatch_hash_range(&rule->match, subtable->index_maps[i],
545 : : &mask_offset, &basis);
546 : : }
547 : 490921 : hash = minimatch_hash_range(&rule->match, subtable->index_maps[i],
548 : : &mask_offset, &basis);
549 : :
550 : 490921 : head = find_equal(subtable, rule->match.flow, hash);
551 [ + + ]: 490921 : if (!head) {
552 : : /* Add rule to tries.
553 : : *
554 : : * Concurrent readers might miss seeing the rule until this update,
555 : : * which might require being fixed up by revalidation later. */
556 [ + + ]: 576887 : for (i = 0; i < cls->n_tries; i++) {
557 [ + + ]: 111072 : if (subtable->trie_plen[i]) {
558 : 51837 : trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
559 : : }
560 : : }
561 : :
562 : : /* Add rule to ports trie. */
563 [ + + ]: 465815 : if (subtable->ports_mask_len) {
564 : : /* We mask the value to be inserted to always have the wildcarded
565 : : * bits in known (zero) state, so we can include them in comparison
566 : : * and they will always match (== their original value does not
567 : : * matter). */
568 : 26643 : ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
569 : :
570 : 26643 : trie_insert_prefix(&subtable->ports_trie, &masked_ports,
571 : : subtable->ports_mask_len);
572 : : }
573 : :
574 : : /* Add new node to segment indices. */
575 [ + + ]: 553506 : for (i = 0; i < subtable->n_indices; i++) {
576 : 87691 : ccmap_inc(&subtable->indices[i], ihash[i]);
577 : : }
578 : 465815 : n_rules = cmap_insert(&subtable->rules, &new->cmap_node, hash);
579 : : } else { /* Equal rules exist in the classifier already. */
580 : : struct cls_match *prev, *iter;
581 : :
582 : : /* Scan the list for the insertion point that will keep the list in
583 : : * order of decreasing priority. Insert after rules marked invisible
584 : : * in any version of the same priority. */
585 [ + + ]: 26928 : FOR_EACH_RULE_IN_LIST_PROTECTED (iter, prev, head) {
586 [ + + ]: 25217 : if (rule->priority > iter->priority
587 [ + + ]: 24897 : || (rule->priority == iter->priority
588 [ + + ]: 24598 : && !cls_match_is_eventually_invisible(iter))) {
589 : : break;
590 : : }
591 : : }
592 : :
593 : : /* Replace 'iter' with 'new' or insert 'new' between 'prev' and
594 : : * 'iter'. */
595 [ + + ]: 25106 : if (iter) {
596 : : struct cls_rule *old;
597 : :
598 [ + + ]: 23395 : if (rule->priority == iter->priority) {
599 : 23075 : cls_match_replace(prev, iter, new);
600 : 23075 : old = CONST_CAST(struct cls_rule *, iter->cls_rule);
601 : : } else {
602 : 320 : cls_match_insert(prev, iter, new);
603 : 320 : old = NULL;
604 : : }
605 : :
606 : : /* Replace the existing head in data structures, if rule is the new
607 : : * head. */
608 [ + + ]: 23395 : if (iter == head) {
609 : 23319 : cmap_replace(&subtable->rules, &head->cmap_node,
610 : : &new->cmap_node, hash);
611 : : }
612 : :
613 [ + + ]: 23395 : if (old) {
614 : : struct cls_conjunction_set *conj_set;
615 : :
616 : 23075 : conj_set = ovsrcu_get_protected(struct cls_conjunction_set *,
617 : : &iter->conj_set);
618 [ - + ]: 23075 : if (conj_set) {
619 : 0 : ovsrcu_postpone(free, conj_set);
620 : : }
621 : :
622 : 23075 : ovsrcu_set(&old->cls_match, NULL); /* Marks old rule as removed
623 : : * from the classifier. */
624 : 23075 : ovsrcu_postpone(cls_match_free_cb, iter);
625 : :
626 : : /* No change in subtable's max priority or max count. */
627 : :
628 : : /* Make 'new' visible to lookups in the appropriate version. */
629 : 23075 : cls_match_set_remove_version(new, OVS_VERSION_NOT_REMOVED);
630 : :
631 : : /* Make rule visible to iterators (immediately). */
632 : 23075 : rculist_replace(CONST_CAST(struct rculist *, &rule->node),
633 : : &old->node);
634 : :
635 : : /* Return displaced rule. Caller is responsible for keeping it
636 : : * around until all threads quiesce. */
637 : 23395 : return old;
638 : : }
639 : : } else {
640 : : /* 'new' is new node after 'prev' */
641 : 1711 : cls_match_insert(prev, iter, new);
642 : : }
643 : : }
644 : :
645 : : /* Make 'new' visible to lookups in the appropriate version. */
646 : 467846 : cls_match_set_remove_version(new, OVS_VERSION_NOT_REMOVED);
647 : :
648 : : /* Make rule visible to iterators (immediately). */
649 : 467846 : rculist_push_back(&subtable->rules_list,
650 : 467846 : CONST_CAST(struct rculist *, &rule->node));
651 : :
652 : : /* Rule was added, not replaced. Update 'subtable's 'max_priority' and
653 : : * 'max_count', if necessary.
654 : : *
655 : : * The rule was already inserted, but concurrent readers may not see the
656 : : * rule yet as the subtables vector is not updated yet. This will have to
657 : : * be fixed by revalidation later. */
658 [ + + ]: 467846 : if (n_rules == 1) {
659 : 397033 : subtable->max_priority = rule->priority;
660 : 397033 : subtable->max_count = 1;
661 : 397033 : pvector_insert(&cls->subtables, subtable, rule->priority);
662 [ + + ]: 70813 : } else if (rule->priority == subtable->max_priority) {
663 : 62472 : ++subtable->max_count;
664 [ + + ]: 8341 : } else if (rule->priority > subtable->max_priority) {
665 : 935 : subtable->max_priority = rule->priority;
666 : 935 : subtable->max_count = 1;
667 : 935 : pvector_change_priority(&cls->subtables, subtable, rule->priority);
668 : : }
669 : :
670 : : /* Nothing was replaced. */
671 : 467846 : cls->n_rules++;
672 : :
673 [ + + ]: 467846 : if (cls->publish) {
674 : 457540 : pvector_publish(&cls->subtables);
675 : : }
676 : :
677 : 490921 : return NULL;
678 : : }
679 : :
680 : : /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
681 : : * must not modify or free it.
682 : : *
683 : : * 'cls' must not contain an identical rule (including wildcards, values of
684 : : * fixed fields, and priority). Use classifier_find_rule_exactly() to find
685 : : * such a rule. */
686 : : void
687 : 434369 : classifier_insert(struct classifier *cls, const struct cls_rule *rule,
688 : : ovs_version_t version, const struct cls_conjunction conj[],
689 : : size_t n_conj)
690 : : {
691 : 434369 : const struct cls_rule *displaced_rule
692 : : = classifier_replace(cls, rule, version, conj, n_conj);
693 [ - + ]: 434369 : ovs_assert(!displaced_rule);
694 : 434369 : }
695 : :
696 : : /* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy
697 : : * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
698 : : * resides, etc., as necessary.
699 : : *
700 : : * Does nothing if 'rule' has been already removed, or was never inserted.
701 : : *
702 : : * Returns the removed rule, or NULL, if it was already removed.
703 : : */
704 : : const struct cls_rule *
705 : 462544 : classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
706 : : {
707 : : struct cls_match *rule, *prev, *next, *head;
708 : : struct cls_conjunction_set *conj_set;
709 : : struct cls_subtable *subtable;
710 : 462544 : uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
711 : : unsigned int mask_offset;
712 : : size_t n_rules;
713 : : unsigned int i;
714 : :
715 : 462544 : rule = get_cls_match_protected(cls_rule);
716 [ + + ]: 462544 : if (!rule) {
717 : 1356 : return NULL;
718 : : }
719 : : /* Mark as removed. */
720 : 461188 : ovsrcu_set(&CONST_CAST(struct cls_rule *, cls_rule)->cls_match, NULL);
721 : :
722 : : /* Remove 'cls_rule' from the subtable's rules list. */
723 : 461188 : rculist_remove(CONST_CAST(struct rculist *, &cls_rule->node));
724 : :
725 : 461188 : subtable = find_subtable(cls, cls_rule->match.mask);
726 [ - + ]: 461188 : ovs_assert(subtable);
727 : :
728 : 461188 : mask_offset = 0;
729 [ + + ]: 550988 : for (i = 0; i < subtable->n_indices; i++) {
730 : 89800 : ihash[i] = minimatch_hash_range(&cls_rule->match,
731 : : subtable->index_maps[i],
732 : : &mask_offset, &basis);
733 : : }
734 : 461188 : hash = minimatch_hash_range(&cls_rule->match, subtable->index_maps[i],
735 : : &mask_offset, &basis);
736 : :
737 : 461188 : head = find_equal(subtable, cls_rule->match.flow, hash);
738 : :
739 : : /* Check if the rule is not the head rule. */
740 [ + + ]: 461188 : if (rule != head) {
741 : : struct cls_match *iter;
742 : :
743 : : /* Not the head rule, but potentially one with the same priority. */
744 : : /* Remove from the list of equal rules. */
745 [ + - ]: 626 : FOR_EACH_RULE_IN_LIST_PROTECTED (iter, prev, head) {
746 [ + + ]: 626 : if (rule == iter) {
747 : 300 : break;
748 : : }
749 : : }
750 [ - + ]: 300 : ovs_assert(iter == rule);
751 : :
752 : 300 : cls_match_remove(prev, rule);
753 : :
754 : 300 : goto check_priority;
755 : : }
756 : :
757 : : /* 'rule' is the head rule. Check if there is another rule to
758 : : * replace 'rule' in the data structures. */
759 : 460888 : next = cls_match_next_protected(rule);
760 [ + + ]: 460888 : if (next) {
761 : 1730 : cmap_replace(&subtable->rules, &rule->cmap_node, &next->cmap_node,
762 : : hash);
763 : 1730 : goto check_priority;
764 : : }
765 : :
766 : : /* 'rule' is last of the kind in the classifier, must remove from all the
767 : : * data structures. */
768 : :
769 [ + + ]: 459158 : if (subtable->ports_mask_len) {
770 : 26579 : ovs_be32 masked_ports = minimatch_get_ports(&cls_rule->match);
771 : :
772 : 26579 : trie_remove_prefix(&subtable->ports_trie,
773 : : &masked_ports, subtable->ports_mask_len);
774 : : }
775 [ + + ]: 568340 : for (i = 0; i < cls->n_tries; i++) {
776 [ + + ]: 109182 : if (subtable->trie_plen[i]) {
777 : 51719 : trie_remove(&cls->tries[i], cls_rule, subtable->trie_plen[i]);
778 : : }
779 : : }
780 : :
781 : : /* Remove rule node from indices. */
782 [ + + ]: 546121 : for (i = 0; i < subtable->n_indices; i++) {
783 : 86963 : ccmap_dec(&subtable->indices[i], ihash[i]);
784 : : }
785 : 459158 : n_rules = cmap_remove(&subtable->rules, &rule->cmap_node, hash);
786 : :
787 [ + + ]: 459158 : if (n_rules == 0) {
788 : 392983 : destroy_subtable(cls, subtable);
789 : : } else {
790 : : check_priority:
791 [ + + ]: 68205 : if (subtable->max_priority == rule->priority
792 [ + + ]: 60786 : && --subtable->max_count == 0) {
793 : : /* Find the new 'max_priority' and 'max_count'. */
794 : 909 : int max_priority = INT_MIN;
795 : : struct cls_match *head;
796 : :
797 [ + + ][ + + ]: 8048 : CMAP_FOR_EACH (head, cmap_node, &subtable->rules) {
798 [ + + ]: 7139 : if (head->priority > max_priority) {
799 : 1924 : max_priority = head->priority;
800 : 1924 : subtable->max_count = 1;
801 [ + + ]: 5215 : } else if (head->priority == max_priority) {
802 : 4 : ++subtable->max_count;
803 : : }
804 : : }
805 : 909 : subtable->max_priority = max_priority;
806 : 909 : pvector_change_priority(&cls->subtables, subtable, max_priority);
807 : : }
808 : : }
809 : :
810 [ + + ]: 461188 : if (cls->publish) {
811 : 407091 : pvector_publish(&cls->subtables);
812 : : }
813 : :
814 : : /* free the rule. */
815 : 461188 : conj_set = ovsrcu_get_protected(struct cls_conjunction_set *,
816 : : &rule->conj_set);
817 [ + + ]: 461188 : if (conj_set) {
818 : 1684 : ovsrcu_postpone(free, conj_set);
819 : : }
820 : 461188 : ovsrcu_postpone(cls_match_free_cb, rule);
821 : 461188 : cls->n_rules--;
822 : :
823 : 462544 : return cls_rule;
824 : : }
825 : :
826 : : /* Prefix tree context. Valid when 'lookup_done' is true. Can skip all
827 : : * subtables which have a prefix match on the trie field, but whose prefix
828 : : * length is not indicated in 'match_plens'. For example, a subtable that
829 : : * has a 8-bit trie field prefix match can be skipped if
830 : : * !be_get_bit_at(&match_plens, 8 - 1). If skipped, 'maskbits' prefix bits
831 : : * must be unwildcarded to make datapath flow only match packets it should. */
832 : : struct trie_ctx {
833 : : const struct cls_trie *trie;
834 : : bool lookup_done; /* Status of the lookup. */
835 : : uint8_t be32ofs; /* U32 offset of the field in question. */
836 : : unsigned int maskbits; /* Prefix length needed to avoid false matches. */
837 : : union trie_prefix match_plens; /* Bitmask of prefix lengths with possible
838 : : * matches. */
839 : : };
840 : :
841 : : static void
842 : 120557850 : trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
843 : : {
844 : 120557850 : ctx->trie = trie;
845 : 120557850 : ctx->be32ofs = trie->field->flow_be32ofs;
846 : 120557850 : ctx->lookup_done = false;
847 : 120557850 : }
848 : :
849 : : struct conjunctive_match {
850 : : struct hmap_node hmap_node;
851 : : uint32_t id;
852 : : uint64_t clauses;
853 : : };
854 : :
855 : : static struct conjunctive_match *
856 : 9129 : find_conjunctive_match__(struct hmap *matches, uint64_t id, uint32_t hash)
857 : : {
858 : : struct conjunctive_match *m;
859 : :
860 [ + + ][ - + ]: 9514 : HMAP_FOR_EACH_IN_BUCKET (m, hmap_node, hash, matches) {
861 [ + + ]: 5012 : if (m->id == id) {
862 : 4627 : return m;
863 : : }
864 : : }
865 : 4502 : return NULL;
866 : : }
867 : :
868 : : static bool
869 : 10973 : find_conjunctive_match(const struct cls_conjunction_set *set,
870 : : unsigned int max_n_clauses, struct hmap *matches,
871 : : struct conjunctive_match *cm_stubs, size_t n_cm_stubs,
872 : : uint32_t *idp)
873 : : {
874 : : const struct cls_conjunction *c;
875 : :
876 [ + + ]: 10973 : if (max_n_clauses < set->min_n_clauses) {
877 : 2375 : return false;
878 : : }
879 : :
880 [ + + ]: 14361 : for (c = set->conj; c < &set->conj[set->n]; c++) {
881 : : struct conjunctive_match *cm;
882 : : uint32_t hash;
883 : :
884 [ + + ]: 9151 : if (c->n_clauses > max_n_clauses) {
885 : 22 : continue;
886 : : }
887 : :
888 : 9129 : hash = hash_int(c->id, 0);
889 : 9129 : cm = find_conjunctive_match__(matches, c->id, hash);
890 [ + + ]: 9129 : if (!cm) {
891 : 4502 : size_t n = hmap_count(matches);
892 : :
893 [ + - ]: 4502 : cm = n < n_cm_stubs ? &cm_stubs[n] : xmalloc(sizeof *cm);
894 : 4502 : hmap_insert(matches, &cm->hmap_node, hash);
895 : 4502 : cm->id = c->id;
896 : 4502 : cm->clauses = UINT64_MAX << (c->n_clauses & 63);
897 : : }
898 : 9129 : cm->clauses |= UINT64_C(1) << c->clause;
899 [ + + ]: 9129 : if (cm->clauses == UINT64_MAX) {
900 : 3388 : *idp = cm->id;
901 : 3388 : return true;
902 : : }
903 : : }
904 : 5210 : return false;
905 : : }
906 : :
907 : : static void
908 : 6343 : free_conjunctive_matches(struct hmap *matches,
909 : : struct conjunctive_match *cm_stubs, size_t n_cm_stubs)
910 : : {
911 [ - + ]: 6343 : if (hmap_count(matches) > n_cm_stubs) {
912 : : struct conjunctive_match *cm, *next;
913 : :
914 [ # # ][ # # ]: 0 : HMAP_FOR_EACH_SAFE (cm, next, hmap_node, matches) {
[ # # ]
915 [ # # ][ # # ]: 0 : if (!(cm >= cm_stubs && cm < &cm_stubs[n_cm_stubs])) {
916 : 0 : free(cm);
917 : : }
918 : : }
919 : : }
920 : 6343 : hmap_destroy(matches);
921 : 6343 : }
922 : :
923 : : /* Like classifier_lookup(), except that support for conjunctive matches can be
924 : : * configured with 'allow_conjunctive_matches'. That feature is not exposed
925 : : * externally because turning off conjunctive matches is only useful to avoid
926 : : * recursion within this function itself.
927 : : *
928 : : * 'flow' is non-const to allow for temporary modifications during the lookup.
929 : : * Any changes are restored before returning. */
930 : : static const struct cls_rule *
931 : 82657090 : classifier_lookup__(const struct classifier *cls, ovs_version_t version,
932 : : struct flow *flow, struct flow_wildcards *wc,
933 : : bool allow_conjunctive_matches)
934 : : {
935 : : struct trie_ctx trie_ctx[CLS_MAX_TRIES];
936 : : const struct cls_match *match;
937 : : /* Highest-priority flow in 'cls' that certainly matches 'flow'. */
938 : 82657090 : const struct cls_match *hard = NULL;
939 : 82657090 : int hard_pri = INT_MIN; /* hard ? hard->priority : INT_MIN. */
940 : :
941 : : /* Highest-priority conjunctive flows in 'cls' matching 'flow'. Since
942 : : * these are (components of) conjunctive flows, we can only know whether
943 : : * the full conjunctive flow matches after seeing multiple of them. Thus,
944 : : * we refer to these as "soft matches". */
945 : : struct cls_conjunction_set *soft_stub[64];
946 : 82657090 : struct cls_conjunction_set **soft = soft_stub;
947 : 82657090 : size_t n_soft = 0, allocated_soft = ARRAY_SIZE(soft_stub);
948 : 82657090 : int soft_pri = INT_MIN; /* n_soft ? MAX(soft[*]->priority) : INT_MIN. */
949 : :
950 : : /* Synchronize for cls->n_tries and subtable->trie_plen. They can change
951 : : * when table configuration changes, which happens typically only on
952 : : * startup. */
953 : 82657090 : atomic_thread_fence(memory_order_acquire);
954 : :
955 : : /* Initialize trie contexts for find_match_wc(). */
956 [ + + ]: 203214940 : for (int i = 0; i < cls->n_tries; i++) {
957 : 120557850 : trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
958 : : }
959 : :
960 : : /* Main loop. */
961 : : struct cls_subtable *subtable;
962 [ + + ]: 169441372 : PVECTOR_FOR_EACH_PRIORITY (subtable, hard_pri + 1, 2, sizeof *subtable,
963 : : &cls->subtables) {
964 : : struct cls_conjunction_set *conj_set;
965 : :
966 : : /* Skip subtables with no match, or where the match is lower-priority
967 : : * than some certain match we've already found. */
968 : 86784282 : match = find_match_wc(subtable, version, flow, trie_ctx, cls->n_tries,
969 : : wc);
970 [ + + ][ - + ]: 86784282 : if (!match || match->priority <= hard_pri) {
971 : 77380580 : continue;
972 : : }
973 : :
974 : 9403702 : conj_set = ovsrcu_get(struct cls_conjunction_set *, &match->conj_set);
975 [ + + ]: 9403702 : if (!conj_set) {
976 : : /* 'match' isn't part of a conjunctive match. It's the best
977 : : * certain match we've got so far, since we know that it's
978 : : * higher-priority than hard_pri.
979 : : *
980 : : * (There might be a higher-priority conjunctive match. We can't
981 : : * tell yet.) */
982 : 9388394 : hard = match;
983 : 9388394 : hard_pri = hard->priority;
984 [ + + ]: 15308 : } else if (allow_conjunctive_matches) {
985 : : /* 'match' is part of a conjunctive match. Add it to the list. */
986 [ - + ]: 12136 : if (OVS_UNLIKELY(n_soft >= allocated_soft)) {
987 : 0 : struct cls_conjunction_set **old_soft = soft;
988 : :
989 : 0 : allocated_soft *= 2;
990 : 0 : soft = xmalloc(allocated_soft * sizeof *soft);
991 : 0 : memcpy(soft, old_soft, n_soft * sizeof *soft);
992 [ # # ]: 0 : if (old_soft != soft_stub) {
993 : 0 : free(old_soft);
994 : : }
995 : : }
996 : 12136 : soft[n_soft++] = conj_set;
997 : :
998 : : /* Keep track of the highest-priority soft match. */
999 [ + + ]: 12136 : if (soft_pri < match->priority) {
1000 : 6340 : soft_pri = match->priority;
1001 : : }
1002 : : }
1003 : : }
1004 : :
1005 : : /* In the common case, at this point we have no soft matches and we can
1006 : : * return immediately. (We do the same thing if we have potential soft
1007 : : * matches but none of them are higher-priority than our hard match.) */
1008 [ + + ]: 82657089 : if (hard_pri >= soft_pri) {
1009 [ - + ]: 82650754 : if (soft != soft_stub) {
1010 : 0 : free(soft);
1011 : : }
1012 [ + + ]: 82650754 : return hard ? hard->cls_rule : NULL;
1013 : : }
1014 : :
1015 : : /* At this point, we have some soft matches. We might also have a hard
1016 : : * match; if so, its priority is lower than the highest-priority soft
1017 : : * match. */
1018 : :
1019 : : /* Soft match loop.
1020 : : *
1021 : : * Check whether soft matches are real matches. */
1022 : : for (;;) {
1023 : : /* Delete soft matches that are null. This only happens in second and
1024 : : * subsequent iterations of the soft match loop, when we drop back from
1025 : : * a high-priority soft match to a lower-priority one.
1026 : : *
1027 : : * Also, delete soft matches whose priority is less than or equal to
1028 : : * the hard match's priority. In the first iteration of the soft
1029 : : * match, these can be in 'soft' because the earlier main loop found
1030 : : * the soft match before the hard match. In second and later iteration
1031 : : * of the soft match loop, these can be in 'soft' because we dropped
1032 : : * back from a high-priority soft match to a lower-priority soft match.
1033 : : *
1034 : : * It is tempting to delete soft matches that cannot be satisfied
1035 : : * because there are fewer soft matches than required to satisfy any of
1036 : : * their conjunctions, but we cannot do that because there might be
1037 : : * lower priority soft or hard matches with otherwise identical
1038 : : * matches. (We could special case those here, but there's no
1039 : : * need--we'll do so at the bottom of the soft match loop anyway and
1040 : : * this duplicates less code.)
1041 : : *
1042 : : * It's also tempting to break out of the soft match loop if 'n_soft ==
1043 : : * 1' but that would also miss lower-priority hard matches. We could
1044 : : * special case that also but again there's no need. */
1045 [ + + ]: 25085 : for (int i = 0; i < n_soft; ) {
1046 [ + + ][ + + ]: 15795 : if (!soft[i] || soft[i]->priority <= hard_pri) {
1047 : 3652 : soft[i] = soft[--n_soft];
1048 : : } else {
1049 : 12143 : i++;
1050 : : }
1051 : : }
1052 [ + + ]: 9290 : if (!n_soft) {
1053 : 2947 : break;
1054 : : }
1055 : :
1056 : : /* Find the highest priority among the soft matches. (We know this
1057 : : * must be higher than the hard match's priority; otherwise we would
1058 : : * have deleted all of the soft matches in the previous loop.) Count
1059 : : * the number of soft matches that have that priority. */
1060 : 6343 : soft_pri = INT_MIN;
1061 : 6343 : int n_soft_pri = 0;
1062 [ + + ]: 18486 : for (int i = 0; i < n_soft; i++) {
1063 [ + + ]: 12143 : if (soft[i]->priority > soft_pri) {
1064 : 6345 : soft_pri = soft[i]->priority;
1065 : 6345 : n_soft_pri = 1;
1066 [ + + ]: 5798 : } else if (soft[i]->priority == soft_pri) {
1067 : 5796 : n_soft_pri++;
1068 : : }
1069 : : }
1070 [ - + ]: 6343 : ovs_assert(soft_pri > hard_pri);
1071 : :
1072 : : /* Look for a real match among the highest-priority soft matches.
1073 : : *
1074 : : * It's unusual to have many conjunctive matches, so we use stubs to
1075 : : * avoid calling malloc() in the common case. An hmap has a built-in
1076 : : * stub for up to 2 hmap_nodes; possibly, we would benefit a variant
1077 : : * with a bigger stub. */
1078 : : struct conjunctive_match cm_stubs[16];
1079 : : struct hmap matches;
1080 : :
1081 : 6343 : hmap_init(&matches);
1082 [ + + ]: 13932 : for (int i = 0; i < n_soft; i++) {
1083 : : uint32_t id;
1084 : :
1085 [ + + ]: 10977 : if (soft[i]->priority == soft_pri
1086 [ + + ]: 10973 : && find_conjunctive_match(soft[i], n_soft_pri, &matches,
1087 : : cm_stubs, ARRAY_SIZE(cm_stubs),
1088 : : &id)) {
1089 : 3388 : uint32_t saved_conj_id = flow->conj_id;
1090 : : const struct cls_rule *rule;
1091 : :
1092 : 3388 : flow->conj_id = id;
1093 : 3388 : rule = classifier_lookup__(cls, version, flow, wc, false);
1094 : 3388 : flow->conj_id = saved_conj_id;
1095 : :
1096 [ + - ]: 3388 : if (rule) {
1097 : 3388 : free_conjunctive_matches(&matches,
1098 : : cm_stubs, ARRAY_SIZE(cm_stubs));
1099 [ - + ]: 3388 : if (soft != soft_stub) {
1100 : 0 : free(soft);
1101 : : }
1102 : 3388 : return rule;
1103 : : }
1104 : : }
1105 : : }
1106 : 2955 : free_conjunctive_matches(&matches, cm_stubs, ARRAY_SIZE(cm_stubs));
1107 : :
1108 : : /* There's no real match among the highest-priority soft matches.
1109 : : * However, if any of those soft matches has a lower-priority but
1110 : : * otherwise identical flow match, then we need to consider those for
1111 : : * soft or hard matches.
1112 : : *
1113 : : * The next iteration of the soft match loop will delete any null
1114 : : * pointers we put into 'soft' (and some others too). */
1115 [ + + ]: 6616 : for (int i = 0; i < n_soft; i++) {
1116 [ + + ]: 3661 : if (soft[i]->priority != soft_pri) {
1117 : 4 : continue;
1118 : : }
1119 : :
1120 : : /* Find next-lower-priority flow with identical flow match. */
1121 : 3657 : match = next_visible_rule_in_list(soft[i]->match, version);
1122 [ + + ]: 3657 : if (match) {
1123 : 9 : soft[i] = ovsrcu_get(struct cls_conjunction_set *,
1124 : : &match->conj_set);
1125 [ + + ]: 9 : if (!soft[i]) {
1126 : : /* The flow is a hard match; don't treat as a soft
1127 : : * match. */
1128 [ + - ]: 2 : if (match->priority > hard_pri) {
1129 : 2 : hard = match;
1130 : 9 : hard_pri = hard->priority;
1131 : : }
1132 : : }
1133 : : } else {
1134 : : /* No such lower-priority flow (probably the common case). */
1135 : 3648 : soft[i] = NULL;
1136 : : }
1137 : : }
1138 : 2955 : }
1139 : :
1140 [ - + ]: 2947 : if (soft != soft_stub) {
1141 : 0 : free(soft);
1142 : : }
1143 [ + + ]: 82657089 : return hard ? hard->cls_rule : NULL;
1144 : : }
1145 : :
1146 : : /* Finds and returns the highest-priority rule in 'cls' that matches 'flow' and
1147 : : * that is visible in 'version'. Returns a null pointer if no rules in 'cls'
1148 : : * match 'flow'. If multiple rules of equal priority match 'flow', returns one
1149 : : * arbitrarily.
1150 : : *
1151 : : * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
1152 : : * set of bits that were significant in the lookup. At some point
1153 : : * earlier, 'wc' should have been initialized (e.g., by
1154 : : * flow_wildcards_init_catchall()).
1155 : : *
1156 : : * 'flow' is non-const to allow for temporary modifications during the lookup.
1157 : : * Any changes are restored before returning. */
1158 : : const struct cls_rule *
1159 : 82653703 : classifier_lookup(const struct classifier *cls, ovs_version_t version,
1160 : : struct flow *flow, struct flow_wildcards *wc)
1161 : : {
1162 : 82653703 : return classifier_lookup__(cls, version, flow, wc, true);
1163 : : }
1164 : :
1165 : : /* Finds and returns a rule in 'cls' with exactly the same priority and
1166 : : * matching criteria as 'target', and that is visible in 'version'.
1167 : : * Only one such rule may ever exist. Returns a null pointer if 'cls' doesn't
1168 : : * contain an exact match. */
1169 : : const struct cls_rule *
1170 : 734278 : classifier_find_rule_exactly(const struct classifier *cls,
1171 : : const struct cls_rule *target,
1172 : : ovs_version_t version)
1173 : : {
1174 : : const struct cls_match *head, *rule;
1175 : : const struct cls_subtable *subtable;
1176 : :
1177 : 734278 : subtable = find_subtable(cls, target->match.mask);
1178 [ + + ]: 734278 : if (!subtable) {
1179 : 14381 : return NULL;
1180 : : }
1181 : :
1182 : 719897 : head = find_equal(subtable, target->match.flow,
1183 : 719897 : miniflow_hash_in_minimask(target->match.flow,
1184 : 719897 : target->match.mask, 0));
1185 [ + + ]: 719897 : if (!head) {
1186 : 24073 : return NULL;
1187 : : }
1188 [ + + ]: 699583 : CLS_MATCH_FOR_EACH (rule, head) {
1189 [ + + ]: 699345 : if (rule->priority < target->priority) {
1190 : 131 : break; /* Not found. */
1191 : : }
1192 [ + + ]: 699214 : if (rule->priority == target->priority
1193 [ + + ]: 695997 : && cls_match_visible_in_version(rule, version)) {
1194 : 695455 : return rule->cls_rule;
1195 : : }
1196 : : }
1197 : 369 : return NULL;
1198 : : }
1199 : :
1200 : : /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
1201 : : * same matching criteria as 'target', and that is visible in 'version'.
1202 : : * Returns a null pointer if 'cls' doesn't contain an exact match visible in
1203 : : * 'version'. */
1204 : : const struct cls_rule *
1205 : 532 : classifier_find_match_exactly(const struct classifier *cls,
1206 : : const struct match *target, int priority,
1207 : : ovs_version_t version)
1208 : : {
1209 : : const struct cls_rule *retval;
1210 : : struct cls_rule cr;
1211 : :
1212 : 532 : cls_rule_init(&cr, target, priority);
1213 : 532 : retval = classifier_find_rule_exactly(cls, &cr, version);
1214 : 532 : cls_rule_destroy(&cr);
1215 : :
1216 : 532 : return retval;
1217 : : }
1218 : :
1219 : : /* Checks if 'target' would overlap any other rule in 'cls' in 'version'. Two
1220 : : * rules are considered to overlap if both rules have the same priority and a
1221 : : * packet could match both, and if both rules are visible in the same version.
1222 : : *
1223 : : * A trivial example of overlapping rules is two rules matching disjoint sets
1224 : : * of fields. E.g., if one rule matches only on port number, while another only
1225 : : * on dl_type, any packet from that specific port and with that specific
1226 : : * dl_type could match both, if the rules also have the same priority. */
1227 : : bool
1228 : 1 : classifier_rule_overlaps(const struct classifier *cls,
1229 : : const struct cls_rule *target, ovs_version_t version)
1230 : : {
1231 : : struct cls_subtable *subtable;
1232 : :
1233 : : /* Iterate subtables in the descending max priority order. */
1234 [ - + ]: 1 : PVECTOR_FOR_EACH_PRIORITY (subtable, target->priority, 2,
1235 : : sizeof(struct cls_subtable), &cls->subtables) {
1236 : : struct {
1237 : : struct minimask mask;
1238 : : uint64_t storage[FLOW_U64S];
1239 : : } m;
1240 : : const struct cls_rule *rule;
1241 : :
1242 : 0 : minimask_combine(&m.mask, target->match.mask, &subtable->mask,
1243 : : m.storage);
1244 : :
1245 [ # # ]: 0 : RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
1246 [ # # ]: 0 : if (rule->priority == target->priority
1247 [ # # ]: 0 : && miniflow_equal_in_minimask(target->match.flow,
1248 : 0 : rule->match.flow, &m.mask)
1249 [ # # ]: 0 : && cls_rule_visible_in_version(rule, version)) {
1250 : 0 : return true;
1251 : : }
1252 : : }
1253 : : }
1254 : 1 : return false;
1255 : : }
1256 : :
1257 : : /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
1258 : : * specific than 'criteria'. That is, 'rule' matches 'criteria' and this
1259 : : * function returns true if, for every field:
1260 : : *
1261 : : * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
1262 : : * field, or
1263 : : *
1264 : : * - 'criteria' wildcards the field,
1265 : : *
1266 : : * Conversely, 'rule' does not match 'criteria' and this function returns false
1267 : : * if, for at least one field:
1268 : : *
1269 : : * - 'criteria' and 'rule' specify different values for the field, or
1270 : : *
1271 : : * - 'criteria' specifies a value for the field but 'rule' wildcards it.
1272 : : *
1273 : : * Equivalently, the truth table for whether a field matches is:
1274 : : *
1275 : : * rule
1276 : : *
1277 : : * c wildcard exact
1278 : : * r +---------+---------+
1279 : : * i wild | yes | yes |
1280 : : * t card | | |
1281 : : * e +---------+---------+
1282 : : * r exact | no |if values|
1283 : : * i | |are equal|
1284 : : * a +---------+---------+
1285 : : *
1286 : : * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
1287 : : * commands and by OpenFlow 1.0 aggregate and flow stats.
1288 : : *
1289 : : * Ignores rule->priority. */
1290 : : bool
1291 : 12477 : cls_rule_is_loose_match(const struct cls_rule *rule,
1292 : : const struct minimatch *criteria)
1293 : : {
1294 : 24954 : return (!minimask_has_extra(rule->match.mask, criteria->mask)
1295 [ + - ][ + - ]: 12477 : && miniflow_equal_in_minimask(rule->match.flow, criteria->flow,
1296 : 12477 : criteria->mask));
1297 : : }
1298 : :
1299 : : /* Iteration. */
1300 : :
1301 : : static bool
1302 : 1760628 : rule_matches(const struct cls_rule *rule, const struct cls_rule *target,
1303 : : ovs_version_t version)
1304 : : {
1305 : : /* Rule may only match a target if it is visible in target's version. */
1306 : 3521256 : return cls_rule_visible_in_version(rule, version)
1307 [ + + ][ + + ]: 1760628 : && (!target || miniflow_equal_in_minimask(rule->match.flow,
[ + + ]
1308 : 545848 : target->match.flow,
1309 : 545848 : target->match.mask));
1310 : : }
1311 : :
1312 : : static const struct cls_rule *
1313 : 443318 : search_subtable(const struct cls_subtable *subtable,
1314 : : struct cls_cursor *cursor)
1315 : : {
1316 [ + + ]: 443318 : if (!cursor->target
1317 [ + + ]: 6574 : || !minimask_has_extra(&subtable->mask, cursor->target->match.mask)) {
1318 : : const struct cls_rule *rule;
1319 : :
1320 [ + + ]: 802241 : RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
1321 [ + + ]: 788893 : if (rule_matches(rule, cursor->target, cursor->version)) {
1322 : 429953 : return rule;
1323 : : }
1324 : : }
1325 : : }
1326 : 13365 : return NULL;
1327 : : }
1328 : :
1329 : : /* Initializes 'cursor' for iterating through rules in 'cls', and returns the
1330 : : * cursor.
1331 : : *
1332 : : * - If 'target' is null, or if the 'target' is a catchall target, the
1333 : : * cursor will visit every rule in 'cls' that is visible in 'version'.
1334 : : *
1335 : : * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
1336 : : * such that cls_rule_is_loose_match(rule, target) returns true and that
1337 : : * the rule is visible in 'version'.
1338 : : *
1339 : : * Ignores target->priority. */
1340 : : struct cls_cursor
1341 : 988549 : cls_cursor_start(const struct classifier *cls, const struct cls_rule *target,
1342 : : ovs_version_t version)
1343 : : {
1344 : : struct cls_cursor cursor;
1345 : : struct cls_subtable *subtable;
1346 : :
1347 : 988549 : cursor.cls = cls;
1348 [ + + ][ + + ]: 988549 : cursor.target = target && !cls_rule_is_catchall(target) ? target : NULL;
1349 : 988549 : cursor.version = version;
1350 : 988549 : cursor.rule = NULL;
1351 : :
1352 : : /* Find first rule. */
1353 [ + + ]: 1001901 : PVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
1354 : : &cursor.cls->subtables) {
1355 : 272152 : const struct cls_rule *rule = search_subtable(subtable, &cursor);
1356 : :
1357 [ + + ]: 272152 : if (rule) {
1358 : 258800 : cursor.subtable = subtable;
1359 : 258800 : cursor.rule = rule;
1360 : 258800 : break;
1361 : : }
1362 : : }
1363 : :
1364 : 988549 : return cursor;
1365 : : }
1366 : :
1367 : : static const struct cls_rule *
1368 : 897788 : cls_cursor_next(struct cls_cursor *cursor)
1369 : : {
1370 : : const struct cls_rule *rule;
1371 : : const struct cls_subtable *subtable;
1372 : :
1373 : 897788 : rule = cursor->rule;
1374 : 897788 : subtable = cursor->subtable;
1375 [ + + ]: 1401688 : RCULIST_FOR_EACH_CONTINUE (rule, node, &subtable->rules_list) {
1376 [ + + ]: 971735 : if (rule_matches(rule, cursor->target, cursor->version)) {
1377 : 467835 : return rule;
1378 : : }
1379 : : }
1380 : :
1381 [ + + ]: 429966 : PVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables) {
1382 : 171166 : rule = search_subtable(subtable, cursor);
1383 [ + + ]: 171166 : if (rule) {
1384 : 171153 : cursor->subtable = subtable;
1385 : 171153 : return rule;
1386 : : }
1387 : : }
1388 : :
1389 : 258800 : return NULL;
1390 : : }
1391 : :
1392 : : /* Sets 'cursor->rule' to the next matching cls_rule in 'cursor''s iteration,
1393 : : * or to null if all matching rules have been visited. */
1394 : : void
1395 : 897788 : cls_cursor_advance(struct cls_cursor *cursor)
1396 : : {
1397 : 897788 : cursor->rule = cls_cursor_next(cursor);
1398 : 897788 : }
1399 : :
1400 : : static struct cls_subtable *
1401 : 1686387 : find_subtable(const struct classifier *cls, const struct minimask *mask)
1402 : : {
1403 : : struct cls_subtable *subtable;
1404 : :
1405 [ + + ]: 1686387 : CMAP_FOR_EACH_WITH_HASH (subtable, cmap_node, minimask_hash(mask, 0),
1406 : : &cls->subtables_map) {
1407 [ + - ]: 1274973 : if (minimask_equal(mask, &subtable->mask)) {
1408 : 1274973 : return subtable;
1409 : : }
1410 : : }
1411 : 411414 : return NULL;
1412 : : }
1413 : :
1414 : : /* Initializes 'map' with a subset of 'miniflow''s maps that includes only the
1415 : : * portions with u64-offset 'i' such that 'start' <= i < 'end'. Does not copy
1416 : : * any data from 'miniflow' to 'map'. */
1417 : : static struct flowmap
1418 : 469156 : miniflow_get_map_in_range(const struct miniflow *miniflow, uint8_t start,
1419 : : uint8_t end)
1420 : : {
1421 : : struct flowmap map;
1422 : 469156 : size_t ofs = 0;
1423 : :
1424 : 469156 : map = miniflow->map;
1425 : :
1426 : : /* Clear the bits before 'start'. */
1427 [ + + ]: 493197 : while (start >= MAP_T_BITS) {
1428 : 24041 : start -= MAP_T_BITS;
1429 : 24041 : ofs += MAP_T_BITS;
1430 : 24041 : map.bits[start / MAP_T_BITS] = 0;
1431 : : }
1432 [ + + ]: 469156 : if (start > 0) {
1433 : 72123 : flowmap_clear(&map, ofs, start);
1434 : : }
1435 : :
1436 : : /* Clear the bits starting at 'end'. */
1437 [ + + ]: 469156 : if (end < FLOW_U64S) {
1438 : : /* flowmap_clear() can handle at most MAP_T_BITS at a time. */
1439 [ - + ]: 72123 : ovs_assert(FLOW_U64S - end <= MAP_T_BITS);
1440 : 72123 : flowmap_clear(&map, end, FLOW_U64S - end);
1441 : : }
1442 : 469156 : return map;
1443 : : }
1444 : :
1445 : : /* The new subtable will be visible to the readers only after this. */
1446 : : static struct cls_subtable *
1447 : 397033 : insert_subtable(struct classifier *cls, const struct minimask *mask)
1448 : : {
1449 : 397033 : uint32_t hash = minimask_hash(mask, 0);
1450 : : struct cls_subtable *subtable;
1451 : 397033 : int i, index = 0;
1452 : : struct flowmap stage_map;
1453 : : uint8_t prev;
1454 : 397033 : size_t count = miniflow_n_values(&mask->masks);
1455 : :
1456 : 397033 : subtable = xzalloc(sizeof *subtable + MINIFLOW_VALUES_SIZE(count));
1457 : 397033 : cmap_init(&subtable->rules);
1458 : 397033 : miniflow_clone(CONST_CAST(struct miniflow *, &subtable->mask.masks),
1459 : : &mask->masks, count);
1460 : :
1461 : : /* Init indices for segmented lookup, if any. */
1462 : 397033 : prev = 0;
1463 [ + + ]: 469156 : for (i = 0; i < cls->n_flow_segments; i++) {
1464 : 72123 : stage_map = miniflow_get_map_in_range(&mask->masks, prev,
1465 : 72123 : cls->flow_segments[i]);
1466 : : /* Add an index if it adds mask bits. */
1467 [ + + ]: 72123 : if (!flowmap_is_empty(stage_map)) {
1468 : 61101 : ccmap_init(&subtable->indices[index]);
1469 : 61101 : *CONST_CAST(struct flowmap *, &subtable->index_maps[index])
1470 : 61101 : = stage_map;
1471 : 61101 : index++;
1472 : : }
1473 : 72123 : prev = cls->flow_segments[i];
1474 : : }
1475 : : /* Map for the final stage. */
1476 : 397033 : *CONST_CAST(struct flowmap *, &subtable->index_maps[index])
1477 : 397033 : = miniflow_get_map_in_range(&mask->masks, prev, FLOW_U64S);
1478 : : /* Check if the final stage adds any bits. */
1479 [ + + ]: 397033 : if (index > 0) {
1480 [ + + ]: 23197 : if (flowmap_is_empty(subtable->index_maps[index])) {
1481 : : /* Remove the last index, as it has the same fields as the rules
1482 : : * map. */
1483 : 5274 : --index;
1484 : 5274 : ccmap_destroy(&subtable->indices[index]);
1485 : : }
1486 : : }
1487 : 397033 : *CONST_CAST(uint8_t *, &subtable->n_indices) = index;
1488 : :
1489 [ + + ]: 444479 : for (i = 0; i < cls->n_tries; i++) {
1490 : 47446 : subtable->trie_plen[i] = minimask_get_prefix_len(mask,
1491 : : cls->tries[i].field);
1492 : : }
1493 : :
1494 : : /* Ports trie. */
1495 : 397033 : ovsrcu_set_hidden(&subtable->ports_trie, NULL);
1496 : 397033 : *CONST_CAST(int *, &subtable->ports_mask_len)
1497 [ + + ]: 397033 : = 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src)));
1498 : :
1499 : : /* List of rules. */
1500 : 397033 : rculist_init(&subtable->rules_list);
1501 : :
1502 : 397033 : cmap_insert(&cls->subtables_map, &subtable->cmap_node, hash);
1503 : :
1504 : 397033 : return subtable;
1505 : : }
1506 : :
1507 : : /* RCU readers may still access the subtable before it is actually freed. */
1508 : : static void
1509 : 392983 : destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
1510 : : {
1511 : : int i;
1512 : :
1513 : 392983 : pvector_remove(&cls->subtables, subtable);
1514 : 392983 : cmap_remove(&cls->subtables_map, &subtable->cmap_node,
1515 : : minimask_hash(&subtable->mask, 0));
1516 : :
1517 [ - + ]: 392983 : ovs_assert(ovsrcu_get_protected(struct trie_node *, &subtable->ports_trie)
1518 : : == NULL);
1519 [ - + ]: 392983 : ovs_assert(cmap_is_empty(&subtable->rules));
1520 [ - + ]: 392983 : ovs_assert(rculist_is_empty(&subtable->rules_list));
1521 : :
1522 [ + + ]: 448568 : for (i = 0; i < subtable->n_indices; i++) {
1523 : 55585 : ccmap_destroy(&subtable->indices[i]);
1524 : : }
1525 : 392983 : cmap_destroy(&subtable->rules);
1526 : 392983 : ovsrcu_postpone(free, subtable);
1527 : 392983 : }
1528 : :
1529 : : static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs);
1530 : :
1531 : : /* Return 'true' if can skip rest of the subtable based on the prefix trie
1532 : : * lookup results. */
1533 : : static inline bool
1534 : 42040444 : check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
1535 : : const unsigned int field_plen[CLS_MAX_TRIES],
1536 : : const struct flowmap range_map, const struct flow *flow,
1537 : : struct flow_wildcards *wc)
1538 : : {
1539 : : int j;
1540 : :
1541 : : /* Check if we could avoid fully unwildcarding the next level of
1542 : : * fields using the prefix tries. The trie checks are done only as
1543 : : * needed to avoid folding in additional bits to the wildcards mask. */
1544 [ + + ]: 125959703 : for (j = 0; j < n_tries; j++) {
1545 : : /* Is the trie field relevant for this subtable, and
1546 : : is the trie field within the current range of fields? */
1547 [ + + + + ]: 161417629 : if (field_plen[j] &&
1548 : 77403837 : flowmap_is_set(&range_map, trie_ctx[j].be32ofs / 2)) {
1549 : 4491669 : struct trie_ctx *ctx = &trie_ctx[j];
1550 : :
1551 : : /* On-demand trie lookup. */
1552 [ + + ]: 4491669 : if (!ctx->lookup_done) {
1553 : 4473475 : memset(&ctx->match_plens, 0, sizeof ctx->match_plens);
1554 : 4473475 : ctx->maskbits = trie_lookup(ctx->trie, flow, &ctx->match_plens);
1555 : 4473475 : ctx->lookup_done = true;
1556 : : }
1557 : : /* Possible to skip the rest of the subtable if subtable's
1558 : : * prefix on the field is not included in the lookup result. */
1559 [ + + ]: 4491669 : if (!be_get_bit_at(&ctx->match_plens.be32, field_plen[j] - 1)) {
1560 : : /* We want the trie lookup to never result in unwildcarding
1561 : : * any bits that would not be unwildcarded otherwise.
1562 : : * Since the trie is shared by the whole classifier, it is
1563 : : * possible that the 'maskbits' contain bits that are
1564 : : * irrelevant for the partition relevant for the current
1565 : : * packet. Hence the checks below. */
1566 : :
1567 : : /* Check that the trie result will not unwildcard more bits
1568 : : * than this subtable would otherwise. */
1569 [ + + ]: 102582 : if (ctx->maskbits <= field_plen[j]) {
1570 : : /* Unwildcard the bits and skip the rest. */
1571 : 90580 : mask_set_prefix_bits(wc, ctx->be32ofs, ctx->maskbits);
1572 : : /* Note: Prerequisite already unwildcarded, as the only
1573 : : * prerequisite of the supported trie lookup fields is
1574 : : * the ethertype, which is always unwildcarded. */
1575 : 90580 : return true;
1576 : : }
1577 : : /* Can skip if the field is already unwildcarded. */
1578 [ + + ]: 12002 : if (mask_prefix_bits_set(wc, ctx->be32ofs, ctx->maskbits)) {
1579 : 3953 : return true;
1580 : : }
1581 : : }
1582 : : }
1583 : : }
1584 : 41945911 : return false;
1585 : : }
1586 : :
1587 : : /* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit
1588 : : * for which 'flow', for which 'mask' has a bit set, specifies a particular
1589 : : * value has the correct value in 'target'.
1590 : : *
1591 : : * This function is equivalent to miniflow_equal_flow_in_minimask(flow,
1592 : : * target, mask) but this is faster because of the invariant that
1593 : : * flow->map and mask->masks.map are the same, and that this version
1594 : : * takes the 'wc'. */
1595 : : static inline bool
1596 : 9434378 : miniflow_and_mask_matches_flow(const struct miniflow *flow,
1597 : : const struct minimask *mask,
1598 : : const struct flow *target)
1599 : : {
1600 : 9434378 : const uint64_t *flowp = miniflow_get_values(flow);
1601 : 9434378 : const uint64_t *maskp = miniflow_get_values(&mask->masks);
1602 : 9434377 : const uint64_t *target_u64 = (const uint64_t *)target;
1603 : : map_t map;
1604 : :
1605 [ + + ]: 28303133 : FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
1606 : : size_t idx;
1607 : :
1608 [ + + ]: 29671605 : MAP_FOR_EACH_INDEX (idx, map) {
1609 [ - + ]: 10802850 : if ((*flowp++ ^ target_u64[idx]) & *maskp++) {
1610 : 0 : return false;
1611 : : }
1612 : : }
1613 : 18868756 : target_u64 += MAP_T_BITS;
1614 : : }
1615 : 9434378 : return true;
1616 : : }
1617 : :
1618 : : static inline const struct cls_match *
1619 : 60756806 : find_match(const struct cls_subtable *subtable, ovs_version_t version,
1620 : : const struct flow *flow, uint32_t hash)
1621 : : {
1622 : : const struct cls_match *head, *rule;
1623 : :
1624 [ + + ]: 60787481 : CMAP_FOR_EACH_WITH_HASH (head, cmap_node, hash, &subtable->rules) {
1625 [ + - ]: 9434378 : if (OVS_LIKELY(miniflow_and_mask_matches_flow(&head->flow,
1626 : : &subtable->mask,
1627 : : flow))) {
1628 : : /* Return highest priority rule that is visible. */
1629 [ + + ]: 9465882 : CLS_MATCH_FOR_EACH (rule, head) {
1630 [ + + ]: 9435207 : if (OVS_LIKELY(cls_match_visible_in_version(rule, version))) {
1631 : 9403672 : return rule;
1632 : : }
1633 : : }
1634 : : }
1635 : : }
1636 : :
1637 : 51353088 : return NULL;
1638 : : }
1639 : :
1640 : : static const struct cls_match *
1641 : 86784285 : find_match_wc(const struct cls_subtable *subtable, ovs_version_t version,
1642 : : const struct flow *flow, struct trie_ctx trie_ctx[CLS_MAX_TRIES],
1643 : : unsigned int n_tries, struct flow_wildcards *wc)
1644 : : {
1645 [ + + ]: 86784285 : if (OVS_UNLIKELY(!wc)) {
1646 : 58720336 : return find_match(subtable, version, flow,
1647 : : flow_hash_in_minimask(flow, &subtable->mask, 0));
1648 : : }
1649 : :
1650 : 28063949 : uint32_t basis = 0, hash;
1651 : 28063949 : const struct cls_match *rule = NULL;
1652 : 28063949 : struct flowmap stages_map = FLOWMAP_EMPTY_INITIALIZER;
1653 : 28063949 : unsigned int mask_offset = 0;
1654 : : int i;
1655 : :
1656 : : /* Try to finish early by checking fields in segments. */
1657 [ + + ]: 42040446 : for (i = 0; i < subtable->n_indices; i++) {
1658 [ + + ]: 39990156 : if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
1659 : : subtable->index_maps[i], flow, wc)) {
1660 : : /* 'wc' bits for the trie field set, now unwildcard the preceding
1661 : : * bits used so far. */
1662 : 80716 : goto no_match;
1663 : : }
1664 : :
1665 : : /* Accumulate the map used so far. */
1666 : 39909440 : stages_map = flowmap_or(stages_map, subtable->index_maps[i]);
1667 : :
1668 : 39909440 : hash = flow_hash_in_minimask_range(flow, &subtable->mask,
1669 : : subtable->index_maps[i],
1670 : : &mask_offset, &basis);
1671 : :
1672 [ + + ]: 39909439 : if (!ccmap_find(&subtable->indices[i], hash)) {
1673 : 25932943 : goto no_match;
1674 : : }
1675 : : }
1676 : : /* Trie check for the final range. */
1677 [ + + ]: 2050290 : if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
1678 : : subtable->index_maps[i], flow, wc)) {
1679 : 13817 : goto no_match;
1680 : : }
1681 : 2036473 : hash = flow_hash_in_minimask_range(flow, &subtable->mask,
1682 : : subtable->index_maps[i],
1683 : : &mask_offset, &basis);
1684 : 2036470 : rule = find_match(subtable, version, flow, hash);
1685 [ + + ][ + + ]: 2036470 : if (!rule && subtable->ports_mask_len) {
1686 : : /* The final stage had ports, but there was no match. Instead of
1687 : : * unwildcarding all the ports bits, use the ports trie to figure out a
1688 : : * smaller set of bits to unwildcard. */
1689 : : unsigned int mbits;
1690 : : ovs_be32 value, plens, mask;
1691 : :
1692 [ + - ]: 140629 : mask = MINIFLOW_GET_BE32(&subtable->mask.masks, tp_src);
1693 : 140629 : value = ((OVS_FORCE ovs_be32 *)flow)[TP_PORTS_OFS32] & mask;
1694 : 140629 : mbits = trie_lookup_value(&subtable->ports_trie, &value, &plens, 32);
1695 : :
1696 : 140629 : ((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |=
1697 : 140629 : mask & be32_prefix_mask(mbits);
1698 : :
1699 : 140629 : goto no_match;
1700 : : }
1701 : :
1702 : : /* Must unwildcard all the fields, as they were looked at. */
1703 : 1895841 : flow_wildcards_fold_minimask(wc, &subtable->mask);
1704 : 1895840 : return rule;
1705 : :
1706 : : no_match:
1707 : : /* Unwildcard the bits in stages so far, as they were used in determining
1708 : : * there is no match. */
1709 : 26168105 : flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, stages_map);
1710 : 86784278 : return NULL;
1711 : : }
1712 : :
1713 : : static struct cls_match *
1714 : 1672006 : find_equal(const struct cls_subtable *subtable, const struct miniflow *flow,
1715 : : uint32_t hash)
1716 : : {
1717 : : struct cls_match *head;
1718 : :
1719 [ + + ]: 1672006 : CMAP_FOR_EACH_WITH_HASH (head, cmap_node, hash, &subtable->rules) {
1720 [ + - ]: 1182118 : if (miniflow_equal(&head->flow, flow)) {
1721 : 1182118 : return head;
1722 : : }
1723 : : }
1724 : 489888 : return NULL;
1725 : : }
1726 : :
1727 : : /* A longest-prefix match tree. */
1728 : :
1729 : : /* Return at least 'plen' bits of the 'prefix', starting at bit offset 'ofs'.
1730 : : * Prefixes are in the network byte order, and the offset 0 corresponds to
1731 : : * the most significant bit of the first byte. The offset can be read as
1732 : : * "how many bits to skip from the start of the prefix starting at 'pr'". */
1733 : : static uint32_t
1734 : 4861295 : raw_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1735 : : {
1736 : : uint32_t prefix;
1737 : :
1738 : 4861295 : pr += ofs / 32; /* Where to start. */
1739 : 4861295 : ofs %= 32; /* How many bits to skip at 'pr'. */
1740 : :
1741 : 4861295 : prefix = ntohl(*pr) << ofs; /* Get the first 32 - ofs bits. */
1742 [ - + ]: 4861295 : if (plen > 32 - ofs) { /* Need more than we have already? */
1743 : 0 : prefix |= ntohl(*++pr) >> (32 - ofs);
1744 : : }
1745 : : /* Return with possible unwanted bits at the end. */
1746 : 4861295 : return prefix;
1747 : : }
1748 : :
1749 : : /* Return min(TRIE_PREFIX_BITS, plen) bits of the 'prefix', starting at bit
1750 : : * offset 'ofs'. Prefixes are in the network byte order, and the offset 0
1751 : : * corresponds to the most significant bit of the first byte. The offset can
1752 : : * be read as "how many bits to skip from the start of the prefix starting at
1753 : : * 'pr'". */
1754 : : static uint32_t
1755 : 56451 : trie_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1756 : : {
1757 [ + + ]: 56451 : if (!plen) {
1758 : 239 : return 0;
1759 : : }
1760 [ + + ]: 56212 : if (plen > TRIE_PREFIX_BITS) {
1761 : 3 : plen = TRIE_PREFIX_BITS; /* Get at most TRIE_PREFIX_BITS. */
1762 : : }
1763 : : /* Return with unwanted bits cleared. */
1764 : 56212 : return raw_get_prefix(pr, ofs, plen) & ~0u << (32 - plen);
1765 : : }
1766 : :
1767 : : /* Return the number of equal bits in 'n_bits' of 'prefix's MSBs and a 'value'
1768 : : * starting at "MSB 0"-based offset 'ofs'. */
1769 : : static unsigned int
1770 : 4805083 : prefix_equal_bits(uint32_t prefix, unsigned int n_bits, const ovs_be32 value[],
1771 : : unsigned int ofs)
1772 : : {
1773 : 4805083 : uint64_t diff = prefix ^ raw_get_prefix(value, ofs, n_bits);
1774 : : /* Set the bit after the relevant bits to limit the result. */
1775 : 4805083 : return raw_clz64(diff << 32 | UINT64_C(1) << (63 - n_bits));
1776 : : }
1777 : :
1778 : : /* Return the number of equal bits in 'node' prefix and a 'prefix' of length
1779 : : * 'plen', starting at "MSB 0"-based offset 'ofs'. */
1780 : : static unsigned int
1781 : 160834 : trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[],
1782 : : unsigned int ofs, unsigned int plen)
1783 : : {
1784 : 160834 : return prefix_equal_bits(node->prefix, MIN(node->n_bits, plen - ofs),
1785 : : prefix, ofs);
1786 : : }
1787 : :
1788 : : /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' can
1789 : : * be greater than 31. */
1790 : : static unsigned int
1791 : 6874887 : be_get_bit_at(const ovs_be32 value[], unsigned int ofs)
1792 : : {
1793 : 6874887 : return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1u;
1794 : : }
1795 : :
1796 : : /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' must
1797 : : * be between 0 and 31, inclusive. */
1798 : : static unsigned int
1799 : 1688 : get_bit_at(const uint32_t prefix, unsigned int ofs)
1800 : : {
1801 : 1688 : return (prefix >> (31 - ofs)) & 1u;
1802 : : }
1803 : :
1804 : : /* Create new branch. */
1805 : : static struct trie_node *
1806 : 56451 : trie_branch_create(const ovs_be32 *prefix, unsigned int ofs, unsigned int plen,
1807 : : unsigned int n_rules)
1808 : : {
1809 : 56451 : struct trie_node *node = xmalloc(sizeof *node);
1810 : :
1811 : 56451 : node->prefix = trie_get_prefix(prefix, ofs, plen);
1812 : :
1813 [ + + ]: 56451 : if (plen <= TRIE_PREFIX_BITS) {
1814 : 56448 : node->n_bits = plen;
1815 : 56448 : ovsrcu_set_hidden(&node->edges[0], NULL);
1816 : 56448 : ovsrcu_set_hidden(&node->edges[1], NULL);
1817 : 56448 : node->n_rules = n_rules;
1818 : : } else { /* Need intermediate nodes. */
1819 : 3 : struct trie_node *subnode = trie_branch_create(prefix,
1820 : : ofs + TRIE_PREFIX_BITS,
1821 : : plen - TRIE_PREFIX_BITS,
1822 : : n_rules);
1823 : 3 : int bit = get_bit_at(subnode->prefix, 0);
1824 : 3 : node->n_bits = TRIE_PREFIX_BITS;
1825 : 3 : ovsrcu_set_hidden(&node->edges[bit], subnode);
1826 : 3 : ovsrcu_set_hidden(&node->edges[!bit], NULL);
1827 : 3 : node->n_rules = 0;
1828 : : }
1829 : 56451 : return node;
1830 : : }
1831 : :
1832 : : static void
1833 : 59606 : trie_node_destroy(const struct trie_node *node)
1834 : : {
1835 : 59606 : ovsrcu_postpone(free, CONST_CAST(struct trie_node *, node));
1836 : 59606 : }
1837 : :
1838 : : /* Copy a trie node for modification and postpone delete the old one. */
1839 : : static struct trie_node *
1840 : 3310 : trie_node_rcu_realloc(const struct trie_node *node)
1841 : : {
1842 : 3310 : struct trie_node *new_node = xmalloc(sizeof *node);
1843 : :
1844 : 3310 : *new_node = *node;
1845 : 3310 : trie_node_destroy(node);
1846 : :
1847 : 3310 : return new_node;
1848 : : }
1849 : :
1850 : : static void
1851 : 97036 : trie_destroy(rcu_trie_ptr *trie)
1852 : : {
1853 : 97036 : struct trie_node *node = ovsrcu_get_protected(struct trie_node *, trie);
1854 : :
1855 [ + + ]: 97036 : if (node) {
1856 : 6 : ovsrcu_set_hidden(trie, NULL);
1857 : 6 : trie_destroy(&node->edges[0]);
1858 : 6 : trie_destroy(&node->edges[1]);
1859 : 6 : trie_node_destroy(node);
1860 : : }
1861 : 97036 : }
1862 : :
1863 : : static bool
1864 : 4222 : trie_is_leaf(const struct trie_node *trie)
1865 : : {
1866 : : /* No children? */
1867 : 4222 : return !ovsrcu_get(struct trie_node *, &trie->edges[0])
1868 [ + - ][ + - ]: 4222 : && !ovsrcu_get(struct trie_node *, &trie->edges[1]);
1869 : : }
1870 : :
1871 : : static void
1872 : 90580 : mask_set_prefix_bits(struct flow_wildcards *wc, uint8_t be32ofs,
1873 : : unsigned int n_bits)
1874 : : {
1875 : 90580 : ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
1876 : : unsigned int i;
1877 : :
1878 [ + + ]: 90670 : for (i = 0; i < n_bits / 32; i++) {
1879 : 90 : mask[i] = OVS_BE32_MAX;
1880 : : }
1881 [ + + ]: 90580 : if (n_bits % 32) {
1882 : 90491 : mask[i] |= htonl(~0u << (32 - n_bits % 32));
1883 : : }
1884 : 90580 : }
1885 : :
1886 : : static bool
1887 : 12002 : mask_prefix_bits_set(const struct flow_wildcards *wc, uint8_t be32ofs,
1888 : : unsigned int n_bits)
1889 : : {
1890 : 12002 : ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
1891 : : unsigned int i;
1892 : 12002 : ovs_be32 zeroes = 0;
1893 : :
1894 [ + + ]: 12294 : for (i = 0; i < n_bits / 32; i++) {
1895 : 292 : zeroes |= ~mask[i];
1896 : : }
1897 [ + + ]: 12002 : if (n_bits % 32) {
1898 : 11710 : zeroes |= ~mask[i] & htonl(~0u << (32 - n_bits % 32));
1899 : : }
1900 : :
1901 : 12002 : return !zeroes; /* All 'n_bits' bits set. */
1902 : : }
1903 : :
1904 : : static rcu_trie_ptr *
1905 : 57137 : trie_next_edge(struct trie_node *node, const ovs_be32 value[],
1906 : : unsigned int ofs)
1907 : : {
1908 : 57137 : return node->edges + be_get_bit_at(value, ofs);
1909 : : }
1910 : :
1911 : : static const struct trie_node *
1912 : 2326081 : trie_next_node(const struct trie_node *node, const ovs_be32 value[],
1913 : : unsigned int ofs)
1914 : : {
1915 : 2326081 : return ovsrcu_get(struct trie_node *,
1916 : : &node->edges[be_get_bit_at(value, ofs)]);
1917 : : }
1918 : :
1919 : : /* Set the bit at ("MSB 0"-based) offset 'ofs'. 'ofs' can be greater than 31.
1920 : : */
1921 : : static void
1922 : 2223847 : be_set_bit_at(ovs_be32 value[], unsigned int ofs)
1923 : : {
1924 : 2223847 : ((uint8_t *)value)[ofs / 8] |= 1u << (7 - ofs % 8);
1925 : 2223847 : }
1926 : :
1927 : : /* Returns the number of bits in the prefix mask necessary to determine a
1928 : : * mismatch, in case there are longer prefixes in the tree below the one that
1929 : : * matched.
1930 : : * '*plens' will have a bit set for each prefix length that may have matching
1931 : : * rules. The caller is responsible for clearing the '*plens' prior to
1932 : : * calling this.
1933 : : */
1934 : : static unsigned int
1935 : 2322390 : trie_lookup_value(const rcu_trie_ptr *trie, const ovs_be32 value[],
1936 : : ovs_be32 plens[], unsigned int n_bits)
1937 : : {
1938 : 2322390 : const struct trie_node *prev = NULL;
1939 : 2322390 : const struct trie_node *node = ovsrcu_get(struct trie_node *, trie);
1940 : 2322390 : unsigned int match_len = 0; /* Number of matching bits. */
1941 : :
1942 [ + + ]: 4648471 : for (; node; prev = node, node = trie_next_node(node, value, match_len)) {
1943 : : unsigned int eqbits;
1944 : : /* Check if this edge can be followed. */
1945 : 4644249 : eqbits = prefix_equal_bits(node->prefix, node->n_bits, value,
1946 : : match_len);
1947 : 4644249 : match_len += eqbits;
1948 [ + + ]: 4644249 : if (eqbits < node->n_bits) { /* Mismatch, nothing more to be found. */
1949 : : /* Bit at offset 'match_len' differed. */
1950 : 98983 : return match_len + 1; /* Includes the first mismatching bit. */
1951 : : }
1952 : : /* Full match, check if rules exist at this prefix length. */
1953 [ + + ]: 4545266 : if (node->n_rules > 0) {
1954 : 2223847 : be_set_bit_at(plens, match_len - 1);
1955 : : }
1956 [ + + ]: 4545266 : if (match_len >= n_bits) {
1957 : 2219185 : return n_bits; /* Full prefix. */
1958 : : }
1959 : : }
1960 : : /* node == NULL. Full match so far, but we tried to follow an
1961 : : * non-existing branch. Need to exclude the other branch if it exists
1962 : : * (it does not if we were called on an empty trie or 'prev' is a leaf
1963 : : * node). */
1964 [ + - ][ - + ]: 4222 : return !prev || trie_is_leaf(prev) ? match_len : match_len + 1;
1965 : : }
1966 : :
1967 : : static unsigned int
1968 : 4473475 : trie_lookup(const struct cls_trie *trie, const struct flow *flow,
1969 : : union trie_prefix *plens)
1970 : : {
1971 : 4473475 : const struct mf_field *mf = trie->field;
1972 : :
1973 : : /* Check that current flow matches the prerequisites for the trie
1974 : : * field. Some match fields are used for multiple purposes, so we
1975 : : * must check that the trie is relevant for this flow. */
1976 [ + + ]: 4473475 : if (mf_are_prereqs_ok(mf, flow, NULL)) {
1977 : 2181761 : return trie_lookup_value(&trie->root,
1978 : 4363522 : &((ovs_be32 *)flow)[mf->flow_be32ofs],
1979 : : &plens->be32, mf->n_bits);
1980 : : }
1981 : 2291714 : memset(plens, 0xff, sizeof *plens); /* All prefixes, no skipping. */
1982 : 2291714 : return 0; /* Value not used in this case. */
1983 : : }
1984 : :
1985 : : /* Returns the length of a prefix match mask for the field 'mf' in 'minimask'.
1986 : : * Returns the u32 offset to the miniflow data in '*miniflow_index', if
1987 : : * 'miniflow_index' is not NULL. */
1988 : : static unsigned int
1989 : 47446 : minimask_get_prefix_len(const struct minimask *minimask,
1990 : : const struct mf_field *mf)
1991 : : {
1992 : 47446 : unsigned int n_bits = 0, mask_tz = 0; /* Non-zero when end of mask seen. */
1993 : 47446 : uint8_t be32_ofs = mf->flow_be32ofs;
1994 : 47446 : uint8_t be32_end = be32_ofs + mf->n_bytes / 4;
1995 : :
1996 [ + + ]: 94898 : for (; be32_ofs < be32_end; ++be32_ofs) {
1997 : 47452 : uint32_t mask = ntohl(minimask_get_be32(minimask, be32_ofs));
1998 : :
1999 : : /* Validate mask, count the mask length. */
2000 [ + + ]: 47452 : if (mask_tz) {
2001 [ - + ]: 3 : if (mask) {
2002 : 0 : return 0; /* No bits allowed after mask ended. */
2003 : : }
2004 : : } else {
2005 [ - + ]: 47449 : if (~mask & (~mask + 1)) {
2006 : 0 : return 0; /* Mask not contiguous. */
2007 : : }
2008 : 47449 : mask_tz = ctz32(mask);
2009 : 47449 : n_bits += 32 - mask_tz;
2010 : : }
2011 : : }
2012 : :
2013 : 47446 : return n_bits;
2014 : : }
2015 : :
2016 : : /*
2017 : : * This is called only when mask prefix is known to be CIDR and non-zero.
2018 : : * Relies on the fact that the flow and mask have the same map, and since
2019 : : * the mask is CIDR, the storage for the flow field exists even if it
2020 : : * happened to be zeros.
2021 : : */
2022 : : static const ovs_be32 *
2023 : 103556 : minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf)
2024 : : {
2025 : 103556 : size_t u64_ofs = mf->flow_be32ofs / 2;
2026 : :
2027 : 103556 : return (OVS_FORCE const ovs_be32 *)miniflow_get__(match->flow, u64_ofs)
2028 : 103556 : + (mf->flow_be32ofs & 1);
2029 : : }
2030 : :
2031 : : /* Insert rule in to the prefix tree.
2032 : : * 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2033 : : * in 'rule'. */
2034 : : static void
2035 : 51837 : trie_insert(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
2036 : : {
2037 : 51837 : trie_insert_prefix(&trie->root,
2038 : : minimatch_get_prefix(&rule->match, trie->field), mlen);
2039 : 51837 : }
2040 : :
2041 : : static void
2042 : 78480 : trie_insert_prefix(rcu_trie_ptr *edge, const ovs_be32 *prefix, int mlen)
2043 : : {
2044 : : struct trie_node *node;
2045 : 78480 : int ofs = 0;
2046 : :
2047 : : /* Walk the tree. */
2048 [ + + ]: 106413 : for (; (node = ovsrcu_get_protected(struct trie_node *, edge));
2049 : 27933 : edge = trie_next_edge(node, prefix, ofs)) {
2050 : 53332 : unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
2051 : 53332 : ofs += eqbits;
2052 [ + + ]: 53332 : if (eqbits < node->n_bits) {
2053 : : /* Mismatch, new node needs to be inserted above. */
2054 : 1685 : int old_branch = get_bit_at(node->prefix, eqbits);
2055 : : struct trie_node *new_parent;
2056 : :
2057 : 1685 : new_parent = trie_branch_create(prefix, ofs - eqbits, eqbits,
2058 : : ofs == mlen ? 1 : 0);
2059 : : /* Copy the node to modify it. */
2060 : 1685 : node = trie_node_rcu_realloc(node);
2061 : : /* Adjust the new node for its new position in the tree. */
2062 : 1685 : node->prefix <<= eqbits;
2063 : 1685 : node->n_bits -= eqbits;
2064 : 1685 : ovsrcu_set_hidden(&new_parent->edges[old_branch], node);
2065 : :
2066 : : /* Check if need a new branch for the new rule. */
2067 [ + + ]: 1685 : if (ofs < mlen) {
2068 : 1682 : ovsrcu_set_hidden(&new_parent->edges[!old_branch],
2069 : : trie_branch_create(prefix, ofs, mlen - ofs,
2070 : : 1));
2071 : : }
2072 : 1685 : ovsrcu_set(edge, new_parent); /* Publish changes. */
2073 : 1685 : return;
2074 : : }
2075 : : /* Full match so far. */
2076 : :
2077 [ + + ]: 51647 : if (ofs == mlen) {
2078 : : /* Full match at the current node, rule needs to be added here. */
2079 : 23714 : node->n_rules++;
2080 : 23714 : return;
2081 : : }
2082 : : }
2083 : : /* Must insert a new tree branch for the new rule. */
2084 : 53081 : ovsrcu_set(edge, trie_branch_create(prefix, ofs, mlen - ofs, 1));
2085 : : }
2086 : :
2087 : : /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2088 : : * in 'rule'. */
2089 : : static void
2090 : 51719 : trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
2091 : : {
2092 : 51719 : trie_remove_prefix(&trie->root,
2093 : : minimatch_get_prefix(&rule->match, trie->field), mlen);
2094 : 51719 : }
2095 : :
2096 : : /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2097 : : * in 'rule'. */
2098 : : static void
2099 : 78298 : trie_remove_prefix(rcu_trie_ptr *root, const ovs_be32 *prefix, int mlen)
2100 : : {
2101 : : struct trie_node *node;
2102 : : rcu_trie_ptr *edges[sizeof(union trie_prefix) * CHAR_BIT];
2103 : 78298 : int depth = 0, ofs = 0;
2104 : :
2105 : : /* Walk the tree. */
2106 [ + - ]: 107502 : for (edges[0] = root;
2107 : 107502 : (node = ovsrcu_get_protected(struct trie_node *, edges[depth]));
2108 : 29204 : edges[++depth] = trie_next_edge(node, prefix, ofs)) {
2109 : 107502 : unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
2110 : :
2111 [ - + ]: 107502 : if (eqbits < node->n_bits) {
2112 : : /* Mismatch, nothing to be removed. This should never happen, as
2113 : : * only rules in the classifier are ever removed. */
2114 : 0 : break; /* Log a warning. */
2115 : : }
2116 : : /* Full match so far. */
2117 : 107502 : ofs += eqbits;
2118 : :
2119 [ + + ]: 107502 : if (ofs == mlen) {
2120 : : /* Full prefix match at the current node, remove rule here. */
2121 [ - + ]: 78298 : if (!node->n_rules) {
2122 : 0 : break; /* Log a warning. */
2123 : : }
2124 : 78298 : node->n_rules--;
2125 : :
2126 : : /* Check if can prune the tree. */
2127 [ + + ]: 79925 : while (!node->n_rules) {
2128 : : struct trie_node *next,
2129 : 56290 : *edge0 = ovsrcu_get_protected(struct trie_node *,
2130 : : &node->edges[0]),
2131 : 56290 : *edge1 = ovsrcu_get_protected(struct trie_node *,
2132 : : &node->edges[1]);
2133 : :
2134 [ + + ][ - + ]: 56290 : if (edge0 && edge1) {
2135 : 0 : break; /* A branching point, cannot prune. */
2136 : : }
2137 : :
2138 : : /* Else have at most one child node, remove this node. */
2139 [ + + ]: 56290 : next = edge0 ? edge0 : edge1;
2140 : :
2141 [ + + ]: 56290 : if (next) {
2142 [ - + ]: 1625 : if (node->n_bits + next->n_bits > TRIE_PREFIX_BITS) {
2143 : 0 : break; /* Cannot combine. */
2144 : : }
2145 : 1625 : next = trie_node_rcu_realloc(next); /* Modify. */
2146 : :
2147 : : /* Combine node with next. */
2148 : 1625 : next->prefix = node->prefix | next->prefix >> node->n_bits;
2149 : 1625 : next->n_bits += node->n_bits;
2150 : : }
2151 : : /* Update the parent's edge. */
2152 : 56290 : ovsrcu_set(edges[depth], next); /* Publish changes. */
2153 : 56290 : trie_node_destroy(node);
2154 : :
2155 [ + + ][ + + ]: 56290 : if (next || !depth) {
2156 : : /* Branch not pruned or at root, nothing more to do. */
2157 : : break;
2158 : : }
2159 : 1627 : node = ovsrcu_get_protected(struct trie_node *,
2160 : : edges[--depth]);
2161 : : }
2162 : 78298 : return;
2163 : : }
2164 : : }
2165 : : /* Cannot go deeper. This should never happen, since only rules
2166 : : * that actually exist in the classifier are ever removed. */
2167 : : }
2168 : :
2169 : :
2170 : : #define CLS_MATCH_POISON (struct cls_match *)(UINTPTR_MAX / 0xf * 0xb)
2171 : :
2172 : : void
2173 : 427752 : cls_match_free_cb(struct cls_match *rule)
2174 : : {
2175 : 427752 : ovsrcu_set_hidden(&rule->next, CLS_MATCH_POISON);
2176 : 427752 : free(rule);
2177 : 427752 : }
|
