]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
4aacd02d | 2 | * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
15 | */ |
16 | ||
17 | #include <config.h> | |
18 | #include "classifier.h" | |
064af421 BP |
19 | #include <errno.h> |
20 | #include <netinet/in.h> | |
844dff32 | 21 | #include "byte-order.h" |
68d1c8c3 | 22 | #include "dynamic-string.h" |
064af421 BP |
23 | #include "flow.h" |
24 | #include "hash.h" | |
52054c15 JR |
25 | #include "hindex.h" |
26 | #include "hmap.h" | |
27 | #include "list.h" | |
07b37e8f | 28 | #include "odp-util.h" |
d8ae4d67 | 29 | #include "ofp-util.h" |
0b4f2078 | 30 | #include "ovs-thread.h" |
13751fd8 | 31 | #include "packets.h" |
fe7cfa5c | 32 | #include "pvector.h" |
52054c15 JR |
33 | #include "tag.h" |
34 | #include "util.h" | |
13751fd8 JR |
35 | #include "vlog.h" |
36 | ||
37 | VLOG_DEFINE_THIS_MODULE(classifier); | |
064af421 | 38 | |
cabd4c43 | 39 | struct trie_node; |
69d6040e JR |
40 | struct trie_ctx; |
41 | ||
42 | /* Ports trie depends on both ports sharing the same ovs_be32. */ | |
43 | #define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4) | |
44 | BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4); | |
cabd4c43 JR |
45 | |
46 | /* Prefix trie for a 'field' */ | |
47 | struct cls_trie { | |
48 | const struct mf_field *field; /* Trie field, or NULL. */ | |
49 | struct trie_node *root; /* NULL if none. */ | |
50 | }; | |
51 | ||
627fb667 JR |
52 | enum { |
53 | CLS_MAX_INDICES = 3 /* Maximum number of lookup indices per subtable. */ | |
54 | }; | |
55 | ||
cabd4c43 | 56 | struct cls_classifier { |
5a87054c | 57 | int n_rules; /* Total number of rules. */ |
cabd4c43 JR |
58 | uint8_t n_flow_segments; |
59 | uint8_t flow_segments[CLS_MAX_INDICES]; /* Flow segment boundaries to use | |
60 | * for staged lookup. */ | |
5a87054c | 61 | struct hmap subtables_map; /* Contains "struct cls_subtable"s. */ |
fe7cfa5c | 62 | struct pvector subtables; |
5a87054c | 63 | struct hmap partitions; /* Contains "struct cls_partition"s. */ |
cabd4c43 JR |
64 | struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */ |
65 | unsigned int n_tries; | |
66 | }; | |
67 | ||
68 | /* A set of rules that all have the same fields wildcarded. */ | |
69 | struct cls_subtable { | |
5a87054c | 70 | struct hmap_node hmap_node; /* Within struct cls_classifier 'subtables_map' |
cabd4c43 | 71 | * hmap. */ |
cabd4c43 | 72 | struct hmap rules; /* Contains "struct cls_rule"s. */ |
cabd4c43 JR |
73 | int n_rules; /* Number of rules, including duplicates. */ |
74 | unsigned int max_priority; /* Max priority of any rule in the subtable. */ | |
75 | unsigned int max_count; /* Count of max_priority rules. */ | |
76 | tag_type tag; /* Tag generated from mask for partitioning. */ | |
77 | uint8_t n_indices; /* How many indices to use. */ | |
78 | uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 flow segment boundaries. */ | |
79 | struct hindex indices[CLS_MAX_INDICES]; /* Staged lookup indices. */ | |
80 | unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'. */ | |
69d6040e JR |
81 | int ports_mask_len; |
82 | struct trie_node *ports_trie; /* NULL if none. */ | |
3016f3e4 JR |
83 | struct minimask mask; /* Wildcards for fields. */ |
84 | /* 'mask' must be the last field. */ | |
cabd4c43 JR |
85 | }; |
86 | ||
87 | /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata | |
88 | * field) with tags for the "cls_subtable"s that contain rules that match that | |
89 | * metadata value. */ | |
90 | struct cls_partition { | |
91 | struct hmap_node hmap_node; /* In struct cls_classifier's 'partitions' | |
92 | * hmap. */ | |
93 | ovs_be64 metadata; /* metadata value for this partition. */ | |
94 | tag_type tags; /* OR of each flow's cls_subtable tag. */ | |
95 | struct tag_tracker tracker; /* Tracks the bits in 'tags'. */ | |
96 | }; | |
97 | ||
627fb667 JR |
98 | /* Internal representation of a rule in a "struct cls_subtable". */ |
99 | struct cls_match { | |
100 | struct cls_rule *cls_rule; | |
101 | struct hindex_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's | |
102 | * 'indices'. */ | |
103 | struct hmap_node hmap_node; /* Within struct cls_subtable 'rules'. */ | |
104 | unsigned int priority; /* Larger numbers are higher priorities. */ | |
105 | struct cls_partition *partition; | |
106 | struct list list; /* List of identical, lower-priority rules. */ | |
3016f3e4 JR |
107 | struct miniflow flow; /* Matching rule. Mask is in the subtable. */ |
108 | /* 'flow' must be the last field. */ | |
627fb667 | 109 | }; |
cabd4c43 | 110 | |
627fb667 JR |
111 | static struct cls_match * |
112 | cls_match_alloc(struct cls_rule *rule) | |
113 | { | |
3016f3e4 JR |
114 | int count = count_1bits(rule->match.flow.map); |
115 | ||
116 | struct cls_match *cls_match | |
117 | = xmalloc(sizeof *cls_match - sizeof cls_match->flow.inline_values | |
118 | + MINIFLOW_VALUES_SIZE(count)); | |
627fb667 JR |
119 | |
120 | cls_match->cls_rule = rule; | |
3016f3e4 | 121 | miniflow_clone_inline(&cls_match->flow, &rule->match.flow, count); |
627fb667 JR |
122 | cls_match->priority = rule->priority; |
123 | rule->cls_match = cls_match; | |
124 | ||
125 | return cls_match; | |
126 | } | |
cabd4c43 | 127 | |
cabd4c43 | 128 | static struct cls_subtable *find_subtable(const struct cls_classifier *, |
03868246 | 129 | const struct minimask *); |
cabd4c43 | 130 | static struct cls_subtable *insert_subtable(struct cls_classifier *, |
03868246 | 131 | const struct minimask *); |
b5d97350 | 132 | |
cabd4c43 | 133 | static void destroy_subtable(struct cls_classifier *, struct cls_subtable *); |
b5d97350 | 134 | |
627fb667 JR |
135 | static struct cls_match *find_match_wc(const struct cls_subtable *, |
136 | const struct flow *, struct trie_ctx *, | |
137 | unsigned int n_tries, | |
138 | struct flow_wildcards *); | |
139 | static struct cls_match *find_equal(struct cls_subtable *, | |
140 | const struct miniflow *, uint32_t hash); | |
141 | static struct cls_match *insert_rule(struct cls_classifier *, | |
142 | struct cls_subtable *, struct cls_rule *); | |
b5d97350 | 143 | |
b5d97350 BP |
144 | /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ |
145 | #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ | |
146 | for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) | |
147 | #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ | |
148 | for ((RULE) = (HEAD); \ | |
149 | (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ | |
150 | (RULE) = (NEXT)) | |
151 | ||
627fb667 JR |
152 | static struct cls_match *next_rule_in_list__(struct cls_match *); |
153 | static struct cls_match *next_rule_in_list(struct cls_match *); | |
13751fd8 JR |
154 | |
155 | static unsigned int minimask_get_prefix_len(const struct minimask *, | |
156 | const struct mf_field *); | |
cabd4c43 | 157 | static void trie_init(struct cls_classifier *, int trie_idx, |
13751fd8 JR |
158 | const struct mf_field *); |
159 | static unsigned int trie_lookup(const struct cls_trie *, const struct flow *, | |
160 | unsigned int *checkbits); | |
69d6040e JR |
161 | static unsigned int trie_lookup_value(const struct trie_node *, |
162 | const ovs_be32 value[], | |
f0e5aa11 | 163 | unsigned int value_bits, |
69d6040e | 164 | unsigned int *checkbits); |
13751fd8 JR |
165 | static void trie_destroy(struct trie_node *); |
166 | static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen); | |
69d6040e JR |
167 | static void trie_insert_prefix(struct trie_node **, const ovs_be32 *prefix, |
168 | int mlen); | |
13751fd8 | 169 | static void trie_remove(struct cls_trie *, const struct cls_rule *, int mlen); |
69d6040e JR |
170 | static void trie_remove_prefix(struct trie_node **, const ovs_be32 *prefix, |
171 | int mlen); | |
13751fd8 JR |
172 | static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs, |
173 | unsigned int nbits); | |
174 | static bool mask_prefix_bits_set(const struct flow_wildcards *, | |
175 | uint8_t be32ofs, unsigned int nbits); | |
3d91d909 JR |
176 | \f |
177 | /* flow/miniflow/minimask/minimatch utilities. | |
178 | * These are only used by the classifier, so place them here to allow | |
179 | * for better optimization. */ | |
180 | ||
181 | static inline uint64_t | |
182 | miniflow_get_map_in_range(const struct miniflow *miniflow, | |
183 | uint8_t start, uint8_t end, unsigned int *offset) | |
184 | { | |
185 | uint64_t map = miniflow->map; | |
186 | *offset = 0; | |
187 | ||
188 | if (start > 0) { | |
189 | uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */ | |
190 | *offset = count_1bits(map & msk); | |
191 | map &= ~msk; | |
192 | } | |
193 | if (end < FLOW_U32S) { | |
194 | uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */ | |
195 | map &= msk; | |
196 | } | |
197 | return map; | |
198 | } | |
199 | ||
200 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
201 | * 'mask', given 'basis'. | |
202 | * | |
203 | * The hash values returned by this function are the same as those returned by | |
204 | * miniflow_hash_in_minimask(), only the form of the arguments differ. */ | |
205 | static inline uint32_t | |
206 | flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, | |
207 | uint32_t basis) | |
208 | { | |
27bbe15d | 209 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); |
3d91d909 | 210 | const uint32_t *flow_u32 = (const uint32_t *)flow; |
27bbe15d | 211 | const uint32_t *p = mask_values; |
3d91d909 JR |
212 | uint32_t hash; |
213 | uint64_t map; | |
214 | ||
215 | hash = basis; | |
216 | for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { | |
217 | hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); | |
218 | } | |
219 | ||
27bbe15d | 220 | return mhash_finish(hash, (p - mask_values) * 4); |
3d91d909 JR |
221 | } |
222 | ||
223 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
224 | * 'mask', given 'basis'. | |
225 | * | |
226 | * The hash values returned by this function are the same as those returned by | |
227 | * flow_hash_in_minimask(), only the form of the arguments differ. */ | |
228 | static inline uint32_t | |
229 | miniflow_hash_in_minimask(const struct miniflow *flow, | |
230 | const struct minimask *mask, uint32_t basis) | |
231 | { | |
27bbe15d JR |
232 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); |
233 | const uint32_t *p = mask_values; | |
3d91d909 JR |
234 | uint32_t hash = basis; |
235 | uint32_t flow_u32; | |
236 | ||
237 | MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { | |
238 | hash = mhash_add(hash, flow_u32 & *p++); | |
239 | } | |
240 | ||
27bbe15d | 241 | return mhash_finish(hash, (p - mask_values) * 4); |
3d91d909 JR |
242 | } |
243 | ||
244 | /* Returns a hash value for the bits of range [start, end) in 'flow', | |
245 | * where there are 1-bits in 'mask', given 'hash'. | |
246 | * | |
247 | * The hash values returned by this function are the same as those returned by | |
248 | * minimatch_hash_range(), only the form of the arguments differ. */ | |
249 | static inline uint32_t | |
250 | flow_hash_in_minimask_range(const struct flow *flow, | |
251 | const struct minimask *mask, | |
252 | uint8_t start, uint8_t end, uint32_t *basis) | |
253 | { | |
27bbe15d | 254 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); |
3d91d909 JR |
255 | const uint32_t *flow_u32 = (const uint32_t *)flow; |
256 | unsigned int offset; | |
257 | uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, | |
258 | &offset); | |
27bbe15d | 259 | const uint32_t *p = mask_values + offset; |
3d91d909 JR |
260 | uint32_t hash = *basis; |
261 | ||
262 | for (; map; map = zero_rightmost_1bit(map)) { | |
263 | hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++); | |
264 | } | |
265 | ||
266 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
27bbe15d | 267 | return mhash_finish(hash, (p - mask_values) * 4); |
3d91d909 JR |
268 | } |
269 | ||
270 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ | |
271 | static inline void | |
272 | flow_wildcards_fold_minimask(struct flow_wildcards *wc, | |
273 | const struct minimask *mask) | |
274 | { | |
275 | flow_union_with_miniflow(&wc->masks, &mask->masks); | |
276 | } | |
277 | ||
278 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask | |
279 | * in range [start, end). */ | |
280 | static inline void | |
281 | flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, | |
282 | const struct minimask *mask, | |
283 | uint8_t start, uint8_t end) | |
284 | { | |
285 | uint32_t *dst_u32 = (uint32_t *)&wc->masks; | |
286 | unsigned int offset; | |
287 | uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, | |
288 | &offset); | |
27bbe15d | 289 | const uint32_t *p = miniflow_get_u32_values(&mask->masks) + offset; |
3d91d909 JR |
290 | |
291 | for (; map; map = zero_rightmost_1bit(map)) { | |
292 | dst_u32[raw_ctz(map)] |= *p++; | |
293 | } | |
294 | } | |
295 | ||
296 | /* Returns a hash value for 'flow', given 'basis'. */ | |
297 | static inline uint32_t | |
298 | miniflow_hash(const struct miniflow *flow, uint32_t basis) | |
299 | { | |
27bbe15d JR |
300 | const uint32_t *values = miniflow_get_u32_values(flow); |
301 | const uint32_t *p = values; | |
3d91d909 JR |
302 | uint32_t hash = basis; |
303 | uint64_t hash_map = 0; | |
304 | uint64_t map; | |
305 | ||
306 | for (map = flow->map; map; map = zero_rightmost_1bit(map)) { | |
307 | if (*p) { | |
308 | hash = mhash_add(hash, *p); | |
309 | hash_map |= rightmost_1bit(map); | |
310 | } | |
311 | p++; | |
312 | } | |
313 | hash = mhash_add(hash, hash_map); | |
314 | hash = mhash_add(hash, hash_map >> 32); | |
315 | ||
27bbe15d | 316 | return mhash_finish(hash, p - values); |
3d91d909 JR |
317 | } |
318 | ||
319 | /* Returns a hash value for 'mask', given 'basis'. */ | |
320 | static inline uint32_t | |
321 | minimask_hash(const struct minimask *mask, uint32_t basis) | |
322 | { | |
323 | return miniflow_hash(&mask->masks, basis); | |
324 | } | |
325 | ||
326 | /* Returns a hash value for 'match', given 'basis'. */ | |
327 | static inline uint32_t | |
328 | minimatch_hash(const struct minimatch *match, uint32_t basis) | |
329 | { | |
330 | return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis)); | |
331 | } | |
332 | ||
333 | /* Returns a hash value for the bits of range [start, end) in 'minimatch', | |
334 | * given 'basis'. | |
335 | * | |
336 | * The hash values returned by this function are the same as those returned by | |
337 | * flow_hash_in_minimask_range(), only the form of the arguments differ. */ | |
338 | static inline uint32_t | |
339 | minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, | |
340 | uint32_t *basis) | |
341 | { | |
342 | unsigned int offset; | |
343 | const uint32_t *p, *q; | |
344 | uint32_t hash = *basis; | |
345 | int n, i; | |
346 | ||
347 | n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end, | |
348 | &offset)); | |
27bbe15d JR |
349 | q = miniflow_get_u32_values(&match->mask.masks) + offset; |
350 | p = miniflow_get_u32_values(&match->flow) + offset; | |
3d91d909 JR |
351 | |
352 | for (i = 0; i < n; i++) { | |
353 | hash = mhash_add(hash, p[i] & q[i]); | |
354 | } | |
355 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
356 | return mhash_finish(hash, (offset + n) * 4); | |
357 | } | |
358 | ||
81a76618 BP |
359 | \f |
360 | /* cls_rule. */ | |
b5d97350 | 361 | |
81a76618 | 362 | /* Initializes 'rule' to match packets specified by 'match' at the given |
5cb7a798 BP |
363 | * 'priority'. 'match' must satisfy the invariant described in the comment at |
364 | * the definition of struct match. | |
66642cb4 | 365 | * |
48d28ac1 BP |
366 | * The caller must eventually destroy 'rule' with cls_rule_destroy(). |
367 | * | |
81a76618 BP |
368 | * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but |
369 | * internally Open vSwitch supports a wider range.) */ | |
47284b1f | 370 | void |
81a76618 BP |
371 | cls_rule_init(struct cls_rule *rule, |
372 | const struct match *match, unsigned int priority) | |
47284b1f | 373 | { |
5cb7a798 BP |
374 | minimatch_init(&rule->match, match); |
375 | rule->priority = priority; | |
627fb667 | 376 | rule->cls_match = NULL; |
5cb7a798 BP |
377 | } |
378 | ||
379 | /* Same as cls_rule_init() for initialization from a "struct minimatch". */ | |
380 | void | |
381 | cls_rule_init_from_minimatch(struct cls_rule *rule, | |
382 | const struct minimatch *match, | |
383 | unsigned int priority) | |
384 | { | |
385 | minimatch_clone(&rule->match, match); | |
81a76618 | 386 | rule->priority = priority; |
627fb667 | 387 | rule->cls_match = NULL; |
685a51a5 JP |
388 | } |
389 | ||
48d28ac1 BP |
390 | /* Initializes 'dst' as a copy of 'src'. |
391 | * | |
b2c1f00b | 392 | * The caller must eventually destroy 'dst' with cls_rule_destroy(). */ |
48d28ac1 BP |
393 | void |
394 | cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) | |
395 | { | |
5cb7a798 BP |
396 | minimatch_clone(&dst->match, &src->match); |
397 | dst->priority = src->priority; | |
627fb667 | 398 | dst->cls_match = NULL; |
48d28ac1 BP |
399 | } |
400 | ||
b2c1f00b BP |
401 | /* Initializes 'dst' with the data in 'src', destroying 'src'. |
402 | * | |
403 | * The caller must eventually destroy 'dst' with cls_rule_destroy(). */ | |
404 | void | |
405 | cls_rule_move(struct cls_rule *dst, struct cls_rule *src) | |
406 | { | |
407 | minimatch_move(&dst->match, &src->match); | |
408 | dst->priority = src->priority; | |
627fb667 | 409 | dst->cls_match = NULL; |
b2c1f00b BP |
410 | } |
411 | ||
48d28ac1 BP |
412 | /* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's |
413 | * normally embedded into a larger structure). | |
414 | * | |
415 | * ('rule' must not currently be in a classifier.) */ | |
416 | void | |
5cb7a798 | 417 | cls_rule_destroy(struct cls_rule *rule) |
48d28ac1 | 418 | { |
627fb667 | 419 | ovs_assert(!rule->cls_match); |
5cb7a798 | 420 | minimatch_destroy(&rule->match); |
48d28ac1 BP |
421 | } |
422 | ||
81a76618 BP |
423 | /* Returns true if 'a' and 'b' match the same packets at the same priority, |
424 | * false if they differ in some way. */ | |
193eb874 BP |
425 | bool |
426 | cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) | |
427 | { | |
5cb7a798 | 428 | return a->priority == b->priority && minimatch_equal(&a->match, &b->match); |
193eb874 BP |
429 | } |
430 | ||
81a76618 | 431 | /* Returns a hash value for 'rule', folding in 'basis'. */ |
57452fdc BP |
432 | uint32_t |
433 | cls_rule_hash(const struct cls_rule *rule, uint32_t basis) | |
434 | { | |
5cb7a798 | 435 | return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); |
73f33563 BP |
436 | } |
437 | ||
81a76618 | 438 | /* Appends a string describing 'rule' to 's'. */ |
07b37e8f BP |
439 | void |
440 | cls_rule_format(const struct cls_rule *rule, struct ds *s) | |
441 | { | |
5cb7a798 | 442 | minimatch_format(&rule->match, s, rule->priority); |
064af421 | 443 | } |
3ca1de08 BP |
444 | |
445 | /* Returns true if 'rule' matches every packet, false otherwise. */ | |
446 | bool | |
447 | cls_rule_is_catchall(const struct cls_rule *rule) | |
448 | { | |
5cb7a798 | 449 | return minimask_is_catchall(&rule->match.mask); |
3ca1de08 | 450 | } |
064af421 BP |
451 | \f |
452 | /* Initializes 'cls' as a classifier that initially contains no classification | |
453 | * rules. */ | |
454 | void | |
cabd4c43 | 455 | classifier_init(struct classifier *cls_, const uint8_t *flow_segments) |
064af421 | 456 | { |
cabd4c43 JR |
457 | struct cls_classifier *cls = xmalloc(sizeof *cls); |
458 | ||
459 | fat_rwlock_init(&cls_->rwlock); | |
460 | ||
461 | cls_->cls = cls; | |
462 | ||
064af421 | 463 | cls->n_rules = 0; |
5a87054c | 464 | hmap_init(&cls->subtables_map); |
fe7cfa5c | 465 | pvector_init(&cls->subtables); |
c906cedf | 466 | hmap_init(&cls->partitions); |
476f36e8 JR |
467 | cls->n_flow_segments = 0; |
468 | if (flow_segments) { | |
469 | while (cls->n_flow_segments < CLS_MAX_INDICES | |
470 | && *flow_segments < FLOW_U32S) { | |
471 | cls->flow_segments[cls->n_flow_segments++] = *flow_segments++; | |
472 | } | |
473 | } | |
13751fd8 | 474 | cls->n_tries = 0; |
064af421 BP |
475 | } |
476 | ||
477 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
478 | * caller's responsibility. */ | |
479 | void | |
cabd4c43 | 480 | classifier_destroy(struct classifier *cls_) |
064af421 | 481 | { |
cabd4c43 JR |
482 | if (cls_) { |
483 | struct cls_classifier *cls = cls_->cls; | |
42181540 | 484 | struct cls_partition *partition, *next_partition; |
03868246 | 485 | struct cls_subtable *subtable, *next_subtable; |
13751fd8 JR |
486 | int i; |
487 | ||
cabd4c43 JR |
488 | fat_rwlock_destroy(&cls_->rwlock); |
489 | if (!cls) { | |
490 | return; | |
491 | } | |
492 | ||
13751fd8 JR |
493 | for (i = 0; i < cls->n_tries; i++) { |
494 | trie_destroy(cls->tries[i].root); | |
495 | } | |
064af421 | 496 | |
03868246 | 497 | HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node, |
5a87054c | 498 | &cls->subtables_map) { |
03868246 | 499 | destroy_subtable(cls, subtable); |
064af421 | 500 | } |
5a87054c | 501 | hmap_destroy(&cls->subtables_map); |
c906cedf BP |
502 | |
503 | HMAP_FOR_EACH_SAFE (partition, next_partition, hmap_node, | |
504 | &cls->partitions) { | |
505 | hmap_remove(&cls->partitions, &partition->hmap_node); | |
506 | free(partition); | |
507 | } | |
508 | hmap_destroy(&cls->partitions); | |
cabd4c43 | 509 | |
fe7cfa5c | 510 | pvector_destroy(&cls->subtables); |
cabd4c43 | 511 | free(cls); |
064af421 BP |
512 | } |
513 | } | |
514 | ||
13751fd8 JR |
515 | /* We use uint64_t as a set for the fields below. */ |
516 | BUILD_ASSERT_DECL(MFF_N_IDS <= 64); | |
517 | ||
518 | /* Set the fields for which prefix lookup should be performed. */ | |
519 | void | |
cabd4c43 | 520 | classifier_set_prefix_fields(struct classifier *cls_, |
13751fd8 JR |
521 | const enum mf_field_id *trie_fields, |
522 | unsigned int n_fields) | |
523 | { | |
cabd4c43 | 524 | struct cls_classifier *cls = cls_->cls; |
13751fd8 JR |
525 | uint64_t fields = 0; |
526 | int i, trie; | |
527 | ||
528 | for (i = 0, trie = 0; i < n_fields && trie < CLS_MAX_TRIES; i++) { | |
529 | const struct mf_field *field = mf_from_id(trie_fields[i]); | |
530 | if (field->flow_be32ofs < 0 || field->n_bits % 32) { | |
531 | /* Incompatible field. This is the only place where we | |
532 | * enforce these requirements, but the rest of the trie code | |
533 | * depends on the flow_be32ofs to be non-negative and the | |
534 | * field length to be a multiple of 32 bits. */ | |
535 | continue; | |
536 | } | |
537 | ||
538 | if (fields & (UINT64_C(1) << trie_fields[i])) { | |
539 | /* Duplicate field, there is no need to build more than | |
540 | * one index for any one field. */ | |
541 | continue; | |
542 | } | |
543 | fields |= UINT64_C(1) << trie_fields[i]; | |
544 | ||
545 | if (trie >= cls->n_tries || field != cls->tries[trie].field) { | |
546 | trie_init(cls, trie, field); | |
547 | } | |
548 | trie++; | |
549 | } | |
550 | ||
551 | /* Destroy the rest. */ | |
552 | for (i = trie; i < cls->n_tries; i++) { | |
553 | trie_init(cls, i, NULL); | |
554 | } | |
555 | cls->n_tries = trie; | |
556 | } | |
557 | ||
558 | static void | |
cabd4c43 | 559 | trie_init(struct cls_classifier *cls, int trie_idx, |
13751fd8 JR |
560 | const struct mf_field *field) |
561 | { | |
562 | struct cls_trie *trie = &cls->tries[trie_idx]; | |
563 | struct cls_subtable *subtable; | |
564 | ||
565 | if (trie_idx < cls->n_tries) { | |
566 | trie_destroy(trie->root); | |
567 | } | |
568 | trie->root = NULL; | |
569 | trie->field = field; | |
570 | ||
571 | /* Add existing rules to the trie. */ | |
fe7cfa5c | 572 | HMAP_FOR_EACH (subtable, hmap_node, &cls->subtables_map) { |
13751fd8 JR |
573 | unsigned int plen; |
574 | ||
575 | plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0; | |
576 | /* Initialize subtable's prefix length on this field. */ | |
577 | subtable->trie_plen[trie_idx] = plen; | |
578 | ||
579 | if (plen) { | |
627fb667 | 580 | struct cls_match *head; |
13751fd8 JR |
581 | |
582 | HMAP_FOR_EACH (head, hmap_node, &subtable->rules) { | |
627fb667 | 583 | struct cls_match *match; |
13751fd8 | 584 | |
627fb667 JR |
585 | FOR_EACH_RULE_IN_LIST (match, head) { |
586 | trie_insert(trie, match->cls_rule, plen); | |
13751fd8 JR |
587 | } |
588 | } | |
589 | } | |
590 | } | |
591 | } | |
592 | ||
b5d97350 | 593 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
594 | bool |
595 | classifier_is_empty(const struct classifier *cls) | |
596 | { | |
cabd4c43 | 597 | return cls->cls->n_rules == 0; |
064af421 BP |
598 | } |
599 | ||
dbda2960 | 600 | /* Returns the number of rules in 'cls'. */ |
064af421 BP |
601 | int |
602 | classifier_count(const struct classifier *cls) | |
603 | { | |
cabd4c43 | 604 | return cls->cls->n_rules; |
064af421 BP |
605 | } |
606 | ||
c906cedf BP |
607 | static uint32_t |
608 | hash_metadata(ovs_be64 metadata_) | |
609 | { | |
610 | uint64_t metadata = (OVS_FORCE uint64_t) metadata_; | |
965607c8 | 611 | return hash_uint64(metadata); |
c906cedf BP |
612 | } |
613 | ||
614 | static struct cls_partition * | |
cabd4c43 JR |
615 | find_partition(const struct cls_classifier *cls, ovs_be64 metadata, |
616 | uint32_t hash) | |
c906cedf BP |
617 | { |
618 | struct cls_partition *partition; | |
619 | ||
620 | HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) { | |
621 | if (partition->metadata == metadata) { | |
622 | return partition; | |
623 | } | |
624 | } | |
625 | ||
626 | return NULL; | |
627 | } | |
628 | ||
629 | static struct cls_partition * | |
cabd4c43 | 630 | create_partition(struct cls_classifier *cls, struct cls_subtable *subtable, |
c906cedf BP |
631 | ovs_be64 metadata) |
632 | { | |
633 | uint32_t hash = hash_metadata(metadata); | |
634 | struct cls_partition *partition = find_partition(cls, metadata, hash); | |
635 | if (!partition) { | |
636 | partition = xmalloc(sizeof *partition); | |
637 | partition->metadata = metadata; | |
638 | partition->tags = 0; | |
183126a1 | 639 | tag_tracker_init(&partition->tracker); |
c906cedf BP |
640 | hmap_insert(&cls->partitions, &partition->hmap_node, hash); |
641 | } | |
03868246 | 642 | tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag); |
c906cedf BP |
643 | return partition; |
644 | } | |
645 | ||
69d6040e JR |
646 | static inline ovs_be32 minimatch_get_ports(const struct minimatch *match) |
647 | { | |
648 | /* Could optimize to use the same map if needed for fast path. */ | |
649 | return MINIFLOW_GET_BE32(&match->flow, tp_src) | |
650 | & MINIFLOW_GET_BE32(&match->mask.masks, tp_src); | |
651 | } | |
652 | ||
b5d97350 BP |
653 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
654 | * must not modify or free it. | |
064af421 BP |
655 | * |
656 | * If 'cls' already contains an identical rule (including wildcards, values of | |
657 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
658 | * rule that was replaced. The caller takes ownership of the returned rule and | |
48d28ac1 BP |
659 | * is thus responsible for destroying it with cls_rule_destroy(), freeing the |
660 | * memory block in which it resides, etc., as necessary. | |
064af421 BP |
661 | * |
662 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
663 | * inserting the new rule. In this case, no rules are displaced by the new | |
664 | * rule, even rules that cannot have any effect because the new rule matches a | |
665 | * superset of their flows and has higher priority. */ | |
666 | struct cls_rule * | |
cabd4c43 | 667 | classifier_replace(struct classifier *cls_, struct cls_rule *rule) |
064af421 | 668 | { |
cabd4c43 | 669 | struct cls_classifier *cls = cls_->cls; |
627fb667 | 670 | struct cls_match *old_rule; |
03868246 | 671 | struct cls_subtable *subtable; |
b5d97350 | 672 | |
03868246 JR |
673 | subtable = find_subtable(cls, &rule->match.mask); |
674 | if (!subtable) { | |
675 | subtable = insert_subtable(cls, &rule->match.mask); | |
b5d97350 BP |
676 | } |
677 | ||
03868246 | 678 | old_rule = insert_rule(cls, subtable, rule); |
b5d97350 | 679 | if (!old_rule) { |
13751fd8 JR |
680 | int i; |
681 | ||
627fb667 | 682 | rule->cls_match->partition = NULL; |
c906cedf BP |
683 | if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) { |
684 | ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow); | |
627fb667 JR |
685 | rule->cls_match->partition = create_partition(cls, subtable, |
686 | metadata); | |
c906cedf BP |
687 | } |
688 | ||
064af421 | 689 | cls->n_rules++; |
13751fd8 JR |
690 | |
691 | for (i = 0; i < cls->n_tries; i++) { | |
692 | if (subtable->trie_plen[i]) { | |
693 | trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]); | |
694 | } | |
695 | } | |
69d6040e JR |
696 | |
697 | /* Ports trie. */ | |
698 | if (subtable->ports_mask_len) { | |
699 | /* We mask the value to be inserted to always have the wildcarded | |
700 | * bits in known (zero) state, so we can include them in comparison | |
701 | * and they will always match (== their original value does not | |
702 | * matter). */ | |
703 | ovs_be32 masked_ports = minimatch_get_ports(&rule->match); | |
704 | ||
705 | trie_insert_prefix(&subtable->ports_trie, &masked_ports, | |
706 | subtable->ports_mask_len); | |
707 | } | |
708 | ||
627fb667 | 709 | return NULL; |
c906cedf | 710 | } else { |
627fb667 JR |
711 | struct cls_rule *old_cls_rule = old_rule->cls_rule; |
712 | ||
713 | rule->cls_match->partition = old_rule->partition; | |
714 | old_cls_rule->cls_match = NULL; | |
715 | free(old_rule); | |
716 | return old_cls_rule; | |
064af421 | 717 | } |
064af421 BP |
718 | } |
719 | ||
08944c1d BP |
720 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
721 | * must not modify or free it. | |
722 | * | |
723 | * 'cls' must not contain an identical rule (including wildcards, values of | |
724 | * fixed fields, and priority). Use classifier_find_rule_exactly() to find | |
725 | * such a rule. */ | |
726 | void | |
727 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
728 | { | |
729 | struct cls_rule *displaced_rule = classifier_replace(cls, rule); | |
cb22974d | 730 | ovs_assert(!displaced_rule); |
08944c1d BP |
731 | } |
732 | ||
48d28ac1 BP |
733 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy |
734 | * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule' | |
735 | * resides, etc., as necessary. */ | |
064af421 | 736 | void |
cabd4c43 | 737 | classifier_remove(struct classifier *cls_, struct cls_rule *rule) |
064af421 | 738 | { |
cabd4c43 | 739 | struct cls_classifier *cls = cls_->cls; |
c906cedf | 740 | struct cls_partition *partition; |
627fb667 JR |
741 | struct cls_match *cls_match = rule->cls_match; |
742 | struct cls_match *head; | |
03868246 | 743 | struct cls_subtable *subtable; |
476f36e8 | 744 | int i; |
064af421 | 745 | |
627fb667 JR |
746 | ovs_assert(cls_match); |
747 | ||
03868246 | 748 | subtable = find_subtable(cls, &rule->match.mask); |
627fb667 JR |
749 | ovs_assert(subtable); |
750 | ||
69d6040e JR |
751 | if (subtable->ports_mask_len) { |
752 | ovs_be32 masked_ports = minimatch_get_ports(&rule->match); | |
753 | ||
754 | trie_remove_prefix(&subtable->ports_trie, | |
755 | &masked_ports, subtable->ports_mask_len); | |
756 | } | |
13751fd8 JR |
757 | for (i = 0; i < cls->n_tries; i++) { |
758 | if (subtable->trie_plen[i]) { | |
759 | trie_remove(&cls->tries[i], rule, subtable->trie_plen[i]); | |
760 | } | |
761 | } | |
762 | ||
476f36e8 JR |
763 | /* Remove rule node from indices. */ |
764 | for (i = 0; i < subtable->n_indices; i++) { | |
627fb667 | 765 | hindex_remove(&subtable->indices[i], &cls_match->index_nodes[i]); |
476f36e8 JR |
766 | } |
767 | ||
627fb667 JR |
768 | head = find_equal(subtable, &rule->match.flow, cls_match->hmap_node.hash); |
769 | if (head != cls_match) { | |
770 | list_remove(&cls_match->list); | |
771 | } else if (list_is_empty(&cls_match->list)) { | |
772 | hmap_remove(&subtable->rules, &cls_match->hmap_node); | |
b5d97350 | 773 | } else { |
627fb667 JR |
774 | struct cls_match *next = CONTAINER_OF(cls_match->list.next, |
775 | struct cls_match, list); | |
064af421 | 776 | |
627fb667 JR |
777 | list_remove(&cls_match->list); |
778 | hmap_replace(&subtable->rules, &cls_match->hmap_node, | |
779 | &next->hmap_node); | |
b5d97350 | 780 | } |
064af421 | 781 | |
627fb667 | 782 | partition = cls_match->partition; |
183126a1 BP |
783 | if (partition) { |
784 | tag_tracker_subtract(&partition->tracker, &partition->tags, | |
03868246 | 785 | subtable->tag); |
183126a1 BP |
786 | if (!partition->tags) { |
787 | hmap_remove(&cls->partitions, &partition->hmap_node); | |
788 | free(partition); | |
789 | } | |
c906cedf BP |
790 | } |
791 | ||
03868246 JR |
792 | if (--subtable->n_rules == 0) { |
793 | destroy_subtable(cls, subtable); | |
fe7cfa5c JR |
794 | } else if (subtable->max_priority == cls_match->priority |
795 | && --subtable->max_count == 0) { | |
796 | /* Find the new 'max_priority' and 'max_count'. */ | |
797 | struct cls_match *head; | |
798 | unsigned int max_priority = 0; | |
799 | ||
800 | HMAP_FOR_EACH (head, hmap_node, &subtable->rules) { | |
801 | if (head->priority > max_priority) { | |
802 | max_priority = head->priority; | |
803 | subtable->max_count = 1; | |
804 | } else if (head->priority == max_priority) { | |
805 | ++subtable->max_count; | |
806 | } | |
807 | } | |
808 | subtable->max_priority = max_priority; | |
809 | pvector_change_priority(&cls->subtables, subtable, max_priority); | |
4d935a6b | 810 | } |
13751fd8 | 811 | |
b5d97350 | 812 | cls->n_rules--; |
627fb667 JR |
813 | |
814 | rule->cls_match = NULL; | |
815 | free(cls_match); | |
064af421 BP |
816 | } |
817 | ||
13751fd8 JR |
818 | /* Prefix tree context. Valid when 'lookup_done' is true. Can skip all |
819 | * subtables which have more than 'match_plen' bits in their corresponding | |
820 | * field at offset 'be32ofs'. If skipped, 'maskbits' prefix bits should be | |
821 | * unwildcarded to quarantee datapath flow matches only packets it should. */ | |
822 | struct trie_ctx { | |
823 | const struct cls_trie *trie; | |
824 | bool lookup_done; /* Status of the lookup. */ | |
825 | uint8_t be32ofs; /* U32 offset of the field in question. */ | |
826 | unsigned int match_plen; /* Longest prefix than could possibly match. */ | |
827 | unsigned int maskbits; /* Prefix length needed to avoid false matches. */ | |
828 | }; | |
829 | ||
830 | static void | |
831 | trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie) | |
832 | { | |
833 | ctx->trie = trie; | |
834 | ctx->be32ofs = trie->field->flow_be32ofs; | |
835 | ctx->lookup_done = false; | |
836 | } | |
837 | ||
48c3de13 BP |
838 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
839 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
74f74083 EJ |
840 | * of equal priority match 'flow', returns one arbitrarily. |
841 | * | |
842 | * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the | |
843 | * set of bits that were significant in the lookup. At some point | |
844 | * earlier, 'wc' should have been initialized (e.g., by | |
845 | * flow_wildcards_init_catchall()). */ | |
48c3de13 | 846 | struct cls_rule * |
cabd4c43 | 847 | classifier_lookup(const struct classifier *cls_, const struct flow *flow, |
74f74083 | 848 | struct flow_wildcards *wc) |
48c3de13 | 849 | { |
cabd4c43 | 850 | struct cls_classifier *cls = cls_->cls; |
c906cedf | 851 | const struct cls_partition *partition; |
c906cedf | 852 | tag_type tags; |
ec988646 | 853 | int64_t best_priority = -1; |
fe7cfa5c JR |
854 | const struct cls_match *best; |
855 | struct trie_ctx trie_ctx[CLS_MAX_TRIES]; | |
856 | struct cls_subtable *subtable; | |
c906cedf | 857 | |
03868246 JR |
858 | /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them, |
859 | * then 'flow' cannot possibly match in 'subtable': | |
c906cedf BP |
860 | * |
861 | * - If flow->metadata maps to a given 'partition', then we can use | |
862 | * 'tags' for 'partition->tags'. | |
863 | * | |
864 | * - If flow->metadata has no partition, then no rule in 'cls' has an | |
865 | * exact-match for flow->metadata. That means that we don't need to | |
03868246 | 866 | * search any subtable that includes flow->metadata in its mask. |
c906cedf | 867 | * |
03868246 | 868 | * In either case, we always need to search any cls_subtables that do not |
c906cedf | 869 | * include flow->metadata in its mask. One way to do that would be to |
03868246 JR |
870 | * check the "cls_subtable"s explicitly for that, but that would require an |
871 | * extra branch per subtable. Instead, we mark such a cls_subtable's | |
872 | * 'tags' as TAG_ALL and make sure that 'tags' is never empty. This means | |
873 | * that 'tags' always intersects such a cls_subtable's 'tags', so we don't | |
874 | * need a special case. | |
c906cedf BP |
875 | */ |
876 | partition = (hmap_is_empty(&cls->partitions) | |
877 | ? NULL | |
878 | : find_partition(cls, flow->metadata, | |
879 | hash_metadata(flow->metadata))); | |
880 | tags = partition ? partition->tags : TAG_ARBITRARY; | |
48c3de13 | 881 | |
13751fd8 | 882 | /* Initialize trie contexts for match_find_wc(). */ |
fe7cfa5c | 883 | for (int i = 0; i < cls->n_tries; i++) { |
13751fd8 JR |
884 | trie_ctx_init(&trie_ctx[i], &cls->tries[i]); |
885 | } | |
ec988646 | 886 | |
b5d97350 | 887 | best = NULL; |
fe7cfa5c JR |
888 | PVECTOR_FOR_EACH_PRIORITY(subtable, best_priority, 2, |
889 | sizeof(struct cls_subtable), &cls->subtables) { | |
627fb667 | 890 | struct cls_match *rule; |
c906cedf | 891 | |
fe7cfa5c | 892 | if (!tag_intersects(tags, subtable->tag)) { |
c906cedf BP |
893 | continue; |
894 | } | |
74f74083 | 895 | |
fe7cfa5c | 896 | rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc); |
ec988646 JR |
897 | if (rule && (int64_t)rule->priority > best_priority) { |
898 | best_priority = (int64_t)rule->priority; | |
1f3c5efc | 899 | best = rule; |
b5d97350 | 900 | } |
48c3de13 | 901 | } |
13751fd8 | 902 | |
627fb667 | 903 | return best ? best->cls_rule : NULL; |
48c3de13 BP |
904 | } |
905 | ||
2abf78ff | 906 | /* Returns true if 'target' satisifies 'match', that is, if each bit for which |
3016f3e4 JR |
907 | * 'match' specifies a particular value has the correct value in 'target'. |
908 | * | |
909 | * 'flow' and 'mask' have the same mask! */ | |
2abf78ff | 910 | static bool |
3016f3e4 JR |
911 | miniflow_and_mask_matches_miniflow(const struct miniflow *flow, |
912 | const struct minimask *mask, | |
913 | const struct miniflow *target) | |
2abf78ff | 914 | { |
3016f3e4 JR |
915 | const uint32_t *flowp = miniflow_get_u32_values(flow); |
916 | const uint32_t *maskp = miniflow_get_u32_values(&mask->masks); | |
2abf78ff JR |
917 | uint32_t target_u32; |
918 | ||
3016f3e4 | 919 | MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) { |
2abf78ff JR |
920 | if ((*flowp++ ^ target_u32) & *maskp++) { |
921 | return false; | |
922 | } | |
923 | } | |
924 | ||
925 | return true; | |
926 | } | |
927 | ||
627fb667 | 928 | static inline struct cls_match * |
2abf78ff JR |
929 | find_match_miniflow(const struct cls_subtable *subtable, |
930 | const struct miniflow *flow, | |
931 | uint32_t hash) | |
932 | { | |
627fb667 | 933 | struct cls_match *rule; |
2abf78ff JR |
934 | |
935 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) { | |
3016f3e4 JR |
936 | if (miniflow_and_mask_matches_miniflow(&rule->flow, &subtable->mask, |
937 | flow)) { | |
2abf78ff JR |
938 | return rule; |
939 | } | |
940 | } | |
941 | ||
942 | return NULL; | |
943 | } | |
944 | ||
945 | /* Finds and returns the highest-priority rule in 'cls' that matches | |
946 | * 'miniflow'. Returns a null pointer if no rules in 'cls' match 'flow'. | |
947 | * If multiple rules of equal priority match 'flow', returns one arbitrarily. | |
948 | * | |
949 | * This function is optimized for the userspace datapath, which only ever has | |
950 | * one priority value for it's flows! | |
951 | */ | |
cabd4c43 | 952 | struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls_, |
2abf78ff JR |
953 | const struct miniflow *flow) |
954 | { | |
cabd4c43 | 955 | struct cls_classifier *cls = cls_->cls; |
2abf78ff JR |
956 | struct cls_subtable *subtable; |
957 | ||
fe7cfa5c | 958 | PVECTOR_FOR_EACH (subtable, &cls->subtables) { |
627fb667 | 959 | struct cls_match *rule; |
2abf78ff JR |
960 | |
961 | rule = find_match_miniflow(subtable, flow, | |
962 | miniflow_hash_in_minimask(flow, | |
963 | &subtable->mask, | |
964 | 0)); | |
965 | if (rule) { | |
627fb667 | 966 | return rule->cls_rule; |
2abf78ff JR |
967 | } |
968 | } | |
969 | ||
970 | return NULL; | |
971 | } | |
972 | ||
b5d97350 BP |
973 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
974 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
c084ce1d | 975 | * contain an exact match. */ |
064af421 | 976 | struct cls_rule * |
cabd4c43 | 977 | classifier_find_rule_exactly(const struct classifier *cls_, |
76ecc721 | 978 | const struct cls_rule *target) |
064af421 | 979 | { |
cabd4c43 | 980 | struct cls_classifier *cls = cls_->cls; |
627fb667 | 981 | struct cls_match *head, *rule; |
03868246 | 982 | struct cls_subtable *subtable; |
064af421 | 983 | |
03868246 JR |
984 | subtable = find_subtable(cls, &target->match.mask); |
985 | if (!subtable) { | |
b5d97350 | 986 | return NULL; |
064af421 BP |
987 | } |
988 | ||
4d935a6b | 989 | /* Skip if there is no hope. */ |
03868246 | 990 | if (target->priority > subtable->max_priority) { |
4d935a6b JR |
991 | return NULL; |
992 | } | |
993 | ||
03868246 | 994 | head = find_equal(subtable, &target->match.flow, |
5cb7a798 BP |
995 | miniflow_hash_in_minimask(&target->match.flow, |
996 | &target->match.mask, 0)); | |
b5d97350 BP |
997 | FOR_EACH_RULE_IN_LIST (rule, head) { |
998 | if (target->priority >= rule->priority) { | |
627fb667 | 999 | return target->priority == rule->priority ? rule->cls_rule : NULL; |
064af421 BP |
1000 | } |
1001 | } | |
1002 | return NULL; | |
1003 | } | |
1004 | ||
81a76618 BP |
1005 | /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the |
1006 | * same matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
1007 | * contain an exact match. */ | |
1008 | struct cls_rule * | |
1009 | classifier_find_match_exactly(const struct classifier *cls, | |
1010 | const struct match *target, | |
1011 | unsigned int priority) | |
1012 | { | |
1013 | struct cls_rule *retval; | |
1014 | struct cls_rule cr; | |
1015 | ||
1016 | cls_rule_init(&cr, target, priority); | |
1017 | retval = classifier_find_rule_exactly(cls, &cr); | |
48d28ac1 | 1018 | cls_rule_destroy(&cr); |
81a76618 BP |
1019 | |
1020 | return retval; | |
1021 | } | |
1022 | ||
faa50f40 BP |
1023 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
1024 | * considered to overlap if both rules have the same priority and a packet | |
1025 | * could match both. */ | |
49bdc010 | 1026 | bool |
cabd4c43 | 1027 | classifier_rule_overlaps(const struct classifier *cls_, |
faa50f40 | 1028 | const struct cls_rule *target) |
49bdc010 | 1029 | { |
cabd4c43 | 1030 | struct cls_classifier *cls = cls_->cls; |
03868246 | 1031 | struct cls_subtable *subtable; |
fe7cfa5c | 1032 | int64_t stop_at_priority = (int64_t)target->priority - 1; |
49bdc010 | 1033 | |
03868246 | 1034 | /* Iterate subtables in the descending max priority order. */ |
fe7cfa5c JR |
1035 | PVECTOR_FOR_EACH_PRIORITY (subtable, stop_at_priority, 2, |
1036 | sizeof(struct cls_subtable), &cls->subtables) { | |
5cb7a798 BP |
1037 | uint32_t storage[FLOW_U32S]; |
1038 | struct minimask mask; | |
627fb667 | 1039 | struct cls_match *head; |
49bdc010 | 1040 | |
03868246 JR |
1041 | minimask_combine(&mask, &target->match.mask, &subtable->mask, storage); |
1042 | HMAP_FOR_EACH (head, hmap_node, &subtable->rules) { | |
627fb667 | 1043 | struct cls_match *rule; |
49bdc010 | 1044 | |
b5d97350 | 1045 | FOR_EACH_RULE_IN_LIST (rule, head) { |
4d935a6b JR |
1046 | if (rule->priority < target->priority) { |
1047 | break; /* Rules in descending priority order. */ | |
1048 | } | |
faa50f40 | 1049 | if (rule->priority == target->priority |
5cb7a798 | 1050 | && miniflow_equal_in_minimask(&target->match.flow, |
3016f3e4 | 1051 | &rule->flow, &mask)) { |
49bdc010 JP |
1052 | return true; |
1053 | } | |
1054 | } | |
1055 | } | |
1056 | } | |
1057 | ||
1058 | return false; | |
1059 | } | |
6ceeaa92 BP |
1060 | |
1061 | /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more | |
1062 | * specific than 'criteria'. That is, 'rule' matches 'criteria' and this | |
1063 | * function returns true if, for every field: | |
1064 | * | |
1065 | * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the | |
1066 | * field, or | |
1067 | * | |
1068 | * - 'criteria' wildcards the field, | |
1069 | * | |
1070 | * Conversely, 'rule' does not match 'criteria' and this function returns false | |
1071 | * if, for at least one field: | |
1072 | * | |
1073 | * - 'criteria' and 'rule' specify different values for the field, or | |
1074 | * | |
1075 | * - 'criteria' specifies a value for the field but 'rule' wildcards it. | |
1076 | * | |
1077 | * Equivalently, the truth table for whether a field matches is: | |
1078 | * | |
1079 | * rule | |
1080 | * | |
1081 | * c wildcard exact | |
1082 | * r +---------+---------+ | |
1083 | * i wild | yes | yes | | |
1084 | * t card | | | | |
1085 | * e +---------+---------+ | |
1086 | * r exact | no |if values| | |
1087 | * i | |are equal| | |
1088 | * a +---------+---------+ | |
1089 | * | |
1090 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
1091 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
1092 | * | |
81a76618 | 1093 | * Ignores rule->priority. */ |
6ceeaa92 BP |
1094 | bool |
1095 | cls_rule_is_loose_match(const struct cls_rule *rule, | |
5cb7a798 | 1096 | const struct minimatch *criteria) |
6ceeaa92 | 1097 | { |
5cb7a798 BP |
1098 | return (!minimask_has_extra(&rule->match.mask, &criteria->mask) |
1099 | && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow, | |
1100 | &criteria->mask)); | |
6ceeaa92 | 1101 | } |
b5d97350 | 1102 | \f |
5ecc9d81 BP |
1103 | /* Iteration. */ |
1104 | ||
1105 | static bool | |
627fb667 | 1106 | rule_matches(const struct cls_match *rule, const struct cls_rule *target) |
5ecc9d81 BP |
1107 | { |
1108 | return (!target | |
3016f3e4 | 1109 | || miniflow_equal_in_minimask(&rule->flow, |
5cb7a798 BP |
1110 | &target->match.flow, |
1111 | &target->match.mask)); | |
5ecc9d81 BP |
1112 | } |
1113 | ||
627fb667 | 1114 | static struct cls_match * |
03868246 JR |
1115 | search_subtable(const struct cls_subtable *subtable, |
1116 | const struct cls_rule *target) | |
5ecc9d81 | 1117 | { |
03868246 | 1118 | if (!target || !minimask_has_extra(&subtable->mask, &target->match.mask)) { |
627fb667 | 1119 | struct cls_match *rule; |
5ecc9d81 | 1120 | |
03868246 | 1121 | HMAP_FOR_EACH (rule, hmap_node, &subtable->rules) { |
5ecc9d81 BP |
1122 | if (rule_matches(rule, target)) { |
1123 | return rule; | |
1124 | } | |
1125 | } | |
1126 | } | |
1127 | return NULL; | |
1128 | } | |
1129 | ||
6ceeaa92 | 1130 | /* Initializes 'cursor' for iterating through rules in 'cls': |
5ecc9d81 | 1131 | * |
6ceeaa92 | 1132 | * - If 'target' is null, the cursor will visit every rule in 'cls'. |
5ecc9d81 | 1133 | * |
6ceeaa92 BP |
1134 | * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls' |
1135 | * such that cls_rule_is_loose_match(rule, target) returns true. | |
5ecc9d81 | 1136 | * |
6ceeaa92 | 1137 | * Ignores target->priority. */ |
5ecc9d81 BP |
1138 | void |
1139 | cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, | |
1140 | const struct cls_rule *target) | |
1141 | { | |
cabd4c43 | 1142 | cursor->cls = cls->cls; |
3ca1de08 | 1143 | cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; |
5ecc9d81 BP |
1144 | } |
1145 | ||
1146 | /* Returns the first matching cls_rule in 'cursor''s iteration, or a null | |
1147 | * pointer if there are no matches. */ | |
1148 | struct cls_rule * | |
1149 | cls_cursor_first(struct cls_cursor *cursor) | |
1150 | { | |
03868246 | 1151 | struct cls_subtable *subtable; |
5ecc9d81 | 1152 | |
5a87054c | 1153 | HMAP_FOR_EACH (subtable, hmap_node, &cursor->cls->subtables_map) { |
627fb667 | 1154 | struct cls_match *rule = search_subtable(subtable, cursor->target); |
5ecc9d81 | 1155 | if (rule) { |
03868246 | 1156 | cursor->subtable = subtable; |
627fb667 | 1157 | return rule->cls_rule; |
5ecc9d81 BP |
1158 | } |
1159 | } | |
1160 | ||
1161 | return NULL; | |
1162 | } | |
1163 | ||
1164 | /* Returns the next matching cls_rule in 'cursor''s iteration, or a null | |
1165 | * pointer if there are no more matches. */ | |
1166 | struct cls_rule * | |
9850cd0f | 1167 | cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_) |
5ecc9d81 | 1168 | { |
627fb667 | 1169 | struct cls_match *rule = CONST_CAST(struct cls_match *, rule_->cls_match); |
03868246 | 1170 | const struct cls_subtable *subtable; |
627fb667 | 1171 | struct cls_match *next; |
5ecc9d81 | 1172 | |
955f579d BP |
1173 | next = next_rule_in_list__(rule); |
1174 | if (next->priority < rule->priority) { | |
627fb667 | 1175 | return next->cls_rule; |
5ecc9d81 BP |
1176 | } |
1177 | ||
955f579d | 1178 | /* 'next' is the head of the list, that is, the rule that is included in |
03868246 JR |
1179 | * the subtable's hmap. (This is important when the classifier contains |
1180 | * rules that differ only in priority.) */ | |
955f579d | 1181 | rule = next; |
03868246 | 1182 | HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->subtable->rules) { |
5ecc9d81 | 1183 | if (rule_matches(rule, cursor->target)) { |
627fb667 | 1184 | return rule->cls_rule; |
5ecc9d81 BP |
1185 | } |
1186 | } | |
1187 | ||
03868246 | 1188 | subtable = cursor->subtable; |
5a87054c | 1189 | HMAP_FOR_EACH_CONTINUE (subtable, hmap_node, &cursor->cls->subtables_map) { |
03868246 | 1190 | rule = search_subtable(subtable, cursor->target); |
5ecc9d81 | 1191 | if (rule) { |
03868246 | 1192 | cursor->subtable = subtable; |
627fb667 | 1193 | return rule->cls_rule; |
5ecc9d81 BP |
1194 | } |
1195 | } | |
1196 | ||
1197 | return NULL; | |
1198 | } | |
1199 | \f | |
03868246 | 1200 | static struct cls_subtable * |
cabd4c43 | 1201 | find_subtable(const struct cls_classifier *cls, const struct minimask *mask) |
b5d97350 | 1202 | { |
03868246 | 1203 | struct cls_subtable *subtable; |
064af421 | 1204 | |
03868246 | 1205 | HMAP_FOR_EACH_IN_BUCKET (subtable, hmap_node, minimask_hash(mask, 0), |
5a87054c | 1206 | &cls->subtables_map) { |
03868246 JR |
1207 | if (minimask_equal(mask, &subtable->mask)) { |
1208 | return subtable; | |
064af421 BP |
1209 | } |
1210 | } | |
b5d97350 | 1211 | return NULL; |
064af421 | 1212 | } |
064af421 | 1213 | |
03868246 | 1214 | static struct cls_subtable * |
cabd4c43 | 1215 | insert_subtable(struct cls_classifier *cls, const struct minimask *mask) |
b5d97350 | 1216 | { |
c906cedf | 1217 | uint32_t hash = minimask_hash(mask, 0); |
03868246 | 1218 | struct cls_subtable *subtable; |
476f36e8 JR |
1219 | int i, index = 0; |
1220 | struct flow_wildcards old, new; | |
1221 | uint8_t prev; | |
3016f3e4 | 1222 | int count = count_1bits(mask->masks.map); |
064af421 | 1223 | |
3016f3e4 JR |
1224 | subtable = xzalloc(sizeof *subtable - sizeof mask->masks.inline_values |
1225 | + MINIFLOW_VALUES_SIZE(count)); | |
03868246 | 1226 | hmap_init(&subtable->rules); |
3016f3e4 | 1227 | miniflow_clone_inline(&subtable->mask.masks, &mask->masks, count); |
476f36e8 JR |
1228 | |
1229 | /* Init indices for segmented lookup, if any. */ | |
1230 | flow_wildcards_init_catchall(&new); | |
1231 | old = new; | |
1232 | prev = 0; | |
1233 | for (i = 0; i < cls->n_flow_segments; i++) { | |
1234 | flow_wildcards_fold_minimask_range(&new, mask, prev, | |
1235 | cls->flow_segments[i]); | |
1236 | /* Add an index if it adds mask bits. */ | |
1237 | if (!flow_wildcards_equal(&new, &old)) { | |
1238 | hindex_init(&subtable->indices[index]); | |
1239 | subtable->index_ofs[index] = cls->flow_segments[i]; | |
1240 | index++; | |
1241 | old = new; | |
1242 | } | |
1243 | prev = cls->flow_segments[i]; | |
1244 | } | |
1245 | /* Check if the rest of the subtable's mask adds any bits, | |
1246 | * and remove the last index if it doesn't. */ | |
1247 | if (index > 0) { | |
1248 | flow_wildcards_fold_minimask_range(&new, mask, prev, FLOW_U32S); | |
1249 | if (flow_wildcards_equal(&new, &old)) { | |
1250 | --index; | |
1251 | subtable->index_ofs[index] = 0; | |
1252 | hindex_destroy(&subtable->indices[index]); | |
1253 | } | |
1254 | } | |
1255 | subtable->n_indices = index; | |
1256 | ||
03868246 JR |
1257 | subtable->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX |
1258 | ? tag_create_deterministic(hash) | |
1259 | : TAG_ALL); | |
064af421 | 1260 | |
13751fd8 JR |
1261 | for (i = 0; i < cls->n_tries; i++) { |
1262 | subtable->trie_plen[i] = minimask_get_prefix_len(mask, | |
1263 | cls->tries[i].field); | |
1264 | } | |
1265 | ||
69d6040e JR |
1266 | /* Ports trie. */ |
1267 | subtable->ports_trie = NULL; | |
1268 | subtable->ports_mask_len | |
1269 | = 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src))); | |
1270 | ||
5a87054c | 1271 | hmap_insert(&cls->subtables_map, &subtable->hmap_node, hash); |
ec988646 | 1272 | |
03868246 | 1273 | return subtable; |
064af421 BP |
1274 | } |
1275 | ||
b5d97350 | 1276 | static void |
cabd4c43 | 1277 | destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable) |
b5d97350 | 1278 | { |
476f36e8 JR |
1279 | int i; |
1280 | ||
fe7cfa5c | 1281 | pvector_remove(&cls->subtables, subtable); |
69d6040e JR |
1282 | trie_destroy(subtable->ports_trie); |
1283 | ||
476f36e8 JR |
1284 | for (i = 0; i < subtable->n_indices; i++) { |
1285 | hindex_destroy(&subtable->indices[i]); | |
1286 | } | |
5a87054c | 1287 | hmap_remove(&cls->subtables_map, &subtable->hmap_node); |
fe7cfa5c | 1288 | minimask_destroy(&subtable->mask); |
03868246 | 1289 | hmap_destroy(&subtable->rules); |
fe7cfa5c | 1290 | ovsrcu_postpone(free, subtable); |
4aacd02d BP |
1291 | } |
1292 | ||
13751fd8 JR |
1293 | struct range { |
1294 | uint8_t start; | |
1295 | uint8_t end; | |
1296 | }; | |
1297 | ||
1298 | /* Return 'true' if can skip rest of the subtable based on the prefix trie | |
1299 | * lookup results. */ | |
1300 | static inline bool | |
1301 | check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries, | |
1302 | const unsigned int field_plen[CLS_MAX_TRIES], | |
1303 | const struct range ofs, const struct flow *flow, | |
1304 | struct flow_wildcards *wc) | |
1305 | { | |
1306 | int j; | |
1307 | ||
1308 | /* Check if we could avoid fully unwildcarding the next level of | |
1309 | * fields using the prefix tries. The trie checks are done only as | |
1310 | * needed to avoid folding in additional bits to the wildcards mask. */ | |
1311 | for (j = 0; j < n_tries; j++) { | |
1312 | /* Is the trie field relevant for this subtable? */ | |
1313 | if (field_plen[j]) { | |
1314 | struct trie_ctx *ctx = &trie_ctx[j]; | |
1315 | uint8_t be32ofs = ctx->be32ofs; | |
1316 | ||
1317 | /* Is the trie field within the current range of fields? */ | |
1318 | if (be32ofs >= ofs.start && be32ofs < ofs.end) { | |
1319 | /* On-demand trie lookup. */ | |
1320 | if (!ctx->lookup_done) { | |
1321 | ctx->match_plen = trie_lookup(ctx->trie, flow, | |
1322 | &ctx->maskbits); | |
1323 | ctx->lookup_done = true; | |
1324 | } | |
1325 | /* Possible to skip the rest of the subtable if subtable's | |
1326 | * prefix on the field is longer than what is known to match | |
1327 | * based on the trie lookup. */ | |
1328 | if (field_plen[j] > ctx->match_plen) { | |
1329 | /* RFC: We want the trie lookup to never result in | |
1330 | * unwildcarding any bits that would not be unwildcarded | |
1331 | * otherwise. Since the trie is shared by the whole | |
1332 | * classifier, it is possible that the 'maskbits' contain | |
1333 | * bits that are irrelevant for the partition of the | |
1334 | * classifier relevant for the current flow. */ | |
1335 | ||
1336 | /* Can skip if the field is already unwildcarded. */ | |
1337 | if (mask_prefix_bits_set(wc, be32ofs, ctx->maskbits)) { | |
1338 | return true; | |
1339 | } | |
1340 | /* Check that the trie result will not unwildcard more bits | |
1341 | * than this stage will. */ | |
1342 | if (ctx->maskbits <= field_plen[j]) { | |
1343 | /* Unwildcard the bits and skip the rest. */ | |
1344 | mask_set_prefix_bits(wc, be32ofs, ctx->maskbits); | |
1345 | /* Note: Prerequisite already unwildcarded, as the only | |
1346 | * prerequisite of the supported trie lookup fields is | |
1347 | * the ethertype, which is currently always | |
1348 | * unwildcarded. | |
1349 | */ | |
1350 | return true; | |
1351 | } | |
1352 | } | |
1353 | } | |
1354 | } | |
1355 | } | |
1356 | return false; | |
1357 | } | |
1358 | ||
3016f3e4 JR |
1359 | /* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit |
1360 | * for which 'flow', for which 'mask' has a bit set, specifies a particular | |
1361 | * value has the correct value in 'target'. | |
1362 | * | |
1363 | * This function is equivalent to miniflow_equal_flow_in_minimask(flow, | |
1364 | * target, mask) but it is faster because of the invariant that | |
1365 | * flow->map and mask->masks.map are the same. */ | |
1366 | static inline bool | |
1367 | miniflow_and_mask_matches_flow(const struct miniflow *flow, | |
1368 | const struct minimask *mask, | |
1369 | const struct flow *target) | |
1370 | { | |
1371 | const uint32_t *flowp = miniflow_get_u32_values(flow); | |
1372 | const uint32_t *maskp = miniflow_get_u32_values(&mask->masks); | |
1373 | uint32_t target_u32; | |
1374 | ||
1375 | FLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) { | |
1376 | if ((*flowp++ ^ target_u32) & *maskp++) { | |
1377 | return false; | |
1378 | } | |
1379 | } | |
1380 | ||
1381 | return true; | |
1382 | } | |
1383 | ||
627fb667 | 1384 | static inline struct cls_match * |
476f36e8 JR |
1385 | find_match(const struct cls_subtable *subtable, const struct flow *flow, |
1386 | uint32_t hash) | |
b5d97350 | 1387 | { |
627fb667 | 1388 | struct cls_match *rule; |
b5d97350 | 1389 | |
03868246 | 1390 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) { |
3016f3e4 JR |
1391 | if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask, |
1392 | flow)) { | |
b5d97350 | 1393 | return rule; |
064af421 BP |
1394 | } |
1395 | } | |
c23740be | 1396 | |
064af421 BP |
1397 | return NULL; |
1398 | } | |
1399 | ||
627fb667 | 1400 | static struct cls_match * |
476f36e8 | 1401 | find_match_wc(const struct cls_subtable *subtable, const struct flow *flow, |
13751fd8 JR |
1402 | struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries, |
1403 | struct flow_wildcards *wc) | |
476f36e8 JR |
1404 | { |
1405 | uint32_t basis = 0, hash; | |
627fb667 | 1406 | struct cls_match *rule = NULL; |
476f36e8 | 1407 | int i; |
13751fd8 | 1408 | struct range ofs; |
476f36e8 | 1409 | |
ec988646 | 1410 | if (OVS_UNLIKELY(!wc)) { |
476f36e8 JR |
1411 | return find_match(subtable, flow, |
1412 | flow_hash_in_minimask(flow, &subtable->mask, 0)); | |
1413 | } | |
1414 | ||
13751fd8 | 1415 | ofs.start = 0; |
476f36e8 JR |
1416 | /* Try to finish early by checking fields in segments. */ |
1417 | for (i = 0; i < subtable->n_indices; i++) { | |
1418 | struct hindex_node *inode; | |
13751fd8 | 1419 | ofs.end = subtable->index_ofs[i]; |
476f36e8 | 1420 | |
13751fd8 JR |
1421 | if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow, |
1422 | wc)) { | |
1423 | goto range_out; | |
1424 | } | |
1425 | hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start, | |
1426 | ofs.end, &basis); | |
1427 | ofs.start = ofs.end; | |
476f36e8 JR |
1428 | inode = hindex_node_with_hash(&subtable->indices[i], hash); |
1429 | if (!inode) { | |
1430 | /* No match, can stop immediately, but must fold in the mask | |
1431 | * covered so far. */ | |
13751fd8 | 1432 | goto range_out; |
476f36e8 JR |
1433 | } |
1434 | ||
1435 | /* If we have narrowed down to a single rule already, check whether | |
1436 | * that rule matches. If it does match, then we're done. If it does | |
1437 | * not match, then we know that we will never get a match, but we do | |
1438 | * not yet know how many wildcards we need to fold into 'wc' so we | |
1439 | * continue iterating through indices to find that out. (We won't | |
3016f3e4 JR |
1440 | * waste time calling miniflow_and_mask_matches_flow() again because |
1441 | * we've set 'rule' nonnull.) | |
476f36e8 JR |
1442 | * |
1443 | * This check shows a measurable benefit with non-trivial flow tables. | |
1444 | * | |
1445 | * (Rare) hash collisions may cause us to miss the opportunity for this | |
1446 | * optimization. */ | |
1447 | if (!inode->s && !rule) { | |
1448 | ASSIGN_CONTAINER(rule, inode - i, index_nodes); | |
3016f3e4 JR |
1449 | if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask, |
1450 | flow)) { | |
476f36e8 JR |
1451 | goto out; |
1452 | } | |
1453 | } | |
1454 | } | |
13751fd8 JR |
1455 | ofs.end = FLOW_U32S; |
1456 | /* Trie check for the final range. */ | |
1457 | if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow, wc)) { | |
1458 | goto range_out; | |
1459 | } | |
476f36e8 JR |
1460 | if (!rule) { |
1461 | /* Multiple potential matches exist, look for one. */ | |
13751fd8 JR |
1462 | hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start, |
1463 | ofs.end, &basis); | |
476f36e8 JR |
1464 | rule = find_match(subtable, flow, hash); |
1465 | } else { | |
1466 | /* We already narrowed the matching candidates down to just 'rule', | |
1467 | * but it didn't match. */ | |
1468 | rule = NULL; | |
1469 | } | |
69d6040e JR |
1470 | if (!rule && subtable->ports_mask_len) { |
1471 | /* Ports are always part of the final range, if any. | |
1472 | * No match was found for the ports. Use the ports trie to figure out | |
1473 | * which ports bits to unwildcard. */ | |
1474 | unsigned int mbits; | |
1475 | ovs_be32 value, mask; | |
1476 | ||
1477 | mask = MINIFLOW_GET_BE32(&subtable->mask.masks, tp_src); | |
1478 | value = ((OVS_FORCE ovs_be32 *)flow)[TP_PORTS_OFS32] & mask; | |
f0e5aa11 | 1479 | trie_lookup_value(subtable->ports_trie, &value, 32, &mbits); |
69d6040e JR |
1480 | |
1481 | ((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |= | |
1482 | mask & htonl(~0 << (32 - mbits)); | |
1483 | ||
1484 | ofs.start = TP_PORTS_OFS32; | |
1485 | goto range_out; | |
1486 | } | |
476f36e8 | 1487 | out: |
13751fd8 | 1488 | /* Must unwildcard all the fields, as they were looked at. */ |
476f36e8 JR |
1489 | flow_wildcards_fold_minimask(wc, &subtable->mask); |
1490 | return rule; | |
13751fd8 JR |
1491 | |
1492 | range_out: | |
1493 | /* Must unwildcard the fields looked up so far, if any. */ | |
1494 | if (ofs.start) { | |
1495 | flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0, ofs.start); | |
1496 | } | |
1497 | return NULL; | |
476f36e8 JR |
1498 | } |
1499 | ||
627fb667 | 1500 | static struct cls_match * |
03868246 JR |
1501 | find_equal(struct cls_subtable *subtable, const struct miniflow *flow, |
1502 | uint32_t hash) | |
064af421 | 1503 | { |
627fb667 | 1504 | struct cls_match *head; |
064af421 | 1505 | |
03868246 | 1506 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &subtable->rules) { |
3016f3e4 | 1507 | if (miniflow_equal(&head->flow, flow)) { |
b5d97350 | 1508 | return head; |
064af421 BP |
1509 | } |
1510 | } | |
1511 | return NULL; | |
1512 | } | |
1513 | ||
627fb667 | 1514 | static struct cls_match * |
cabd4c43 | 1515 | insert_rule(struct cls_classifier *cls, struct cls_subtable *subtable, |
03868246 | 1516 | struct cls_rule *new) |
064af421 | 1517 | { |
627fb667 JR |
1518 | struct cls_match *cls_match = cls_match_alloc(new); |
1519 | struct cls_match *head; | |
1520 | struct cls_match *old = NULL; | |
476f36e8 JR |
1521 | int i; |
1522 | uint32_t basis = 0, hash; | |
13751fd8 | 1523 | uint8_t prev_be32ofs = 0; |
476f36e8 JR |
1524 | |
1525 | /* Add new node to segment indices. */ | |
1526 | for (i = 0; i < subtable->n_indices; i++) { | |
13751fd8 | 1527 | hash = minimatch_hash_range(&new->match, prev_be32ofs, |
476f36e8 | 1528 | subtable->index_ofs[i], &basis); |
627fb667 | 1529 | hindex_insert(&subtable->indices[i], &cls_match->index_nodes[i], hash); |
13751fd8 | 1530 | prev_be32ofs = subtable->index_ofs[i]; |
476f36e8 | 1531 | } |
13751fd8 | 1532 | hash = minimatch_hash_range(&new->match, prev_be32ofs, FLOW_U32S, &basis); |
476f36e8 | 1533 | head = find_equal(subtable, &new->match.flow, hash); |
b5d97350 | 1534 | if (!head) { |
627fb667 JR |
1535 | hmap_insert(&subtable->rules, &cls_match->hmap_node, hash); |
1536 | list_init(&cls_match->list); | |
4aacd02d | 1537 | goto out; |
b5d97350 BP |
1538 | } else { |
1539 | /* Scan the list for the insertion point that will keep the list in | |
1540 | * order of decreasing priority. */ | |
627fb667 | 1541 | struct cls_match *rule; |
476f36e8 | 1542 | |
627fb667 | 1543 | cls_match->hmap_node.hash = hash; /* Otherwise done by hmap_insert. */ |
476f36e8 | 1544 | |
b5d97350 | 1545 | FOR_EACH_RULE_IN_LIST (rule, head) { |
627fb667 | 1546 | if (cls_match->priority >= rule->priority) { |
b5d97350 | 1547 | if (rule == head) { |
fe7cfa5c JR |
1548 | /* 'cls_match' is the new highest-priority flow in the |
1549 | * list. */ | |
03868246 | 1550 | hmap_replace(&subtable->rules, |
627fb667 | 1551 | &rule->hmap_node, &cls_match->hmap_node); |
b5d97350 | 1552 | } |
064af421 | 1553 | |
627fb667 JR |
1554 | if (cls_match->priority == rule->priority) { |
1555 | list_replace(&cls_match->list, &rule->list); | |
4aacd02d | 1556 | old = rule; |
b5d97350 | 1557 | } else { |
627fb667 | 1558 | list_insert(&rule->list, &cls_match->list); |
b5d97350 | 1559 | } |
fe7cfa5c | 1560 | goto out; |
b5d97350 BP |
1561 | } |
1562 | } | |
064af421 | 1563 | |
b5d97350 | 1564 | /* Insert 'new' at the end of the list. */ |
627fb667 | 1565 | list_push_back(&head->list, &cls_match->list); |
064af421 | 1566 | } |
4aacd02d BP |
1567 | |
1568 | out: | |
1569 | if (!old) { | |
fe7cfa5c JR |
1570 | subtable->n_rules++; |
1571 | ||
1572 | /* Rule was added, not replaced. Update 'subtable's 'max_priority' | |
1573 | * and 'max_count', if necessary. */ | |
1574 | if (subtable->n_rules == 1) { | |
1575 | subtable->max_priority = cls_match->priority; | |
1576 | subtable->max_count = 1; | |
1577 | pvector_insert(&cls->subtables, subtable, cls_match->priority); | |
1578 | } else if (subtable->max_priority == cls_match->priority) { | |
1579 | ++subtable->max_count; | |
1580 | } else if (cls_match->priority > subtable->max_priority) { | |
1581 | subtable->max_priority = cls_match->priority; | |
1582 | subtable->max_count = 1; | |
1583 | pvector_change_priority(&cls->subtables, subtable, cls_match->priority); | |
1584 | } | |
476f36e8 JR |
1585 | } else { |
1586 | /* Remove old node from indices. */ | |
1587 | for (i = 0; i < subtable->n_indices; i++) { | |
1588 | hindex_remove(&subtable->indices[i], &old->index_nodes[i]); | |
1589 | } | |
4aacd02d BP |
1590 | } |
1591 | return old; | |
064af421 BP |
1592 | } |
1593 | ||
627fb667 JR |
1594 | static struct cls_match * |
1595 | next_rule_in_list__(struct cls_match *rule) | |
064af421 | 1596 | { |
627fb667 | 1597 | struct cls_match *next = OBJECT_CONTAINING(rule->list.next, next, list); |
955f579d BP |
1598 | return next; |
1599 | } | |
1600 | ||
627fb667 JR |
1601 | static struct cls_match * |
1602 | next_rule_in_list(struct cls_match *rule) | |
955f579d | 1603 | { |
627fb667 | 1604 | struct cls_match *next = next_rule_in_list__(rule); |
b5d97350 | 1605 | return next->priority < rule->priority ? next : NULL; |
064af421 | 1606 | } |
13751fd8 JR |
1607 | \f |
1608 | /* A longest-prefix match tree. */ | |
1609 | struct trie_node { | |
1610 | uint32_t prefix; /* Prefix bits for this node, MSB first. */ | |
1611 | uint8_t nbits; /* Never zero, except for the root node. */ | |
1612 | unsigned int n_rules; /* Number of rules that have this prefix. */ | |
1613 | struct trie_node *edges[2]; /* Both NULL if leaf. */ | |
1614 | }; | |
1615 | ||
1616 | /* Max bits per node. Must fit in struct trie_node's 'prefix'. | |
1617 | * Also tested with 16, 8, and 5 to stress the implementation. */ | |
1618 | #define TRIE_PREFIX_BITS 32 | |
1619 | ||
1620 | /* Return at least 'plen' bits of the 'prefix', starting at bit offset 'ofs'. | |
1621 | * Prefixes are in the network byte order, and the offset 0 corresponds to | |
1622 | * the most significant bit of the first byte. The offset can be read as | |
1623 | * "how many bits to skip from the start of the prefix starting at 'pr'". */ | |
1624 | static uint32_t | |
1625 | raw_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen) | |
1626 | { | |
1627 | uint32_t prefix; | |
1628 | ||
1629 | pr += ofs / 32; /* Where to start. */ | |
1630 | ofs %= 32; /* How many bits to skip at 'pr'. */ | |
1631 | ||
1632 | prefix = ntohl(*pr) << ofs; /* Get the first 32 - ofs bits. */ | |
1633 | if (plen > 32 - ofs) { /* Need more than we have already? */ | |
1634 | prefix |= ntohl(*++pr) >> (32 - ofs); | |
1635 | } | |
1636 | /* Return with possible unwanted bits at the end. */ | |
1637 | return prefix; | |
1638 | } | |
1639 | ||
1640 | /* Return min(TRIE_PREFIX_BITS, plen) bits of the 'prefix', starting at bit | |
1641 | * offset 'ofs'. Prefixes are in the network byte order, and the offset 0 | |
1642 | * corresponds to the most significant bit of the first byte. The offset can | |
1643 | * be read as "how many bits to skip from the start of the prefix starting at | |
1644 | * 'pr'". */ | |
1645 | static uint32_t | |
1646 | trie_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen) | |
1647 | { | |
1648 | if (!plen) { | |
1649 | return 0; | |
1650 | } | |
1651 | if (plen > TRIE_PREFIX_BITS) { | |
1652 | plen = TRIE_PREFIX_BITS; /* Get at most TRIE_PREFIX_BITS. */ | |
1653 | } | |
1654 | /* Return with unwanted bits cleared. */ | |
1655 | return raw_get_prefix(pr, ofs, plen) & ~0u << (32 - plen); | |
1656 | } | |
1657 | ||
1658 | /* Return the number of equal bits in 'nbits' of 'prefix's MSBs and a 'value' | |
1659 | * starting at "MSB 0"-based offset 'ofs'. */ | |
1660 | static unsigned int | |
1661 | prefix_equal_bits(uint32_t prefix, unsigned int nbits, const ovs_be32 value[], | |
1662 | unsigned int ofs) | |
1663 | { | |
1664 | uint64_t diff = prefix ^ raw_get_prefix(value, ofs, nbits); | |
1665 | /* Set the bit after the relevant bits to limit the result. */ | |
1666 | return raw_clz64(diff << 32 | UINT64_C(1) << (63 - nbits)); | |
1667 | } | |
1668 | ||
1669 | /* Return the number of equal bits in 'node' prefix and a 'prefix' of length | |
1670 | * 'plen', starting at "MSB 0"-based offset 'ofs'. */ | |
1671 | static unsigned int | |
1672 | trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[], | |
1673 | unsigned int ofs, unsigned int plen) | |
1674 | { | |
1675 | return prefix_equal_bits(node->prefix, MIN(node->nbits, plen - ofs), | |
1676 | prefix, ofs); | |
1677 | } | |
1678 | ||
1679 | /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' can | |
1680 | * be greater than 31. */ | |
1681 | static unsigned int | |
1682 | be_get_bit_at(const ovs_be32 value[], unsigned int ofs) | |
1683 | { | |
1684 | return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1u; | |
1685 | } | |
1686 | ||
1687 | /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' must | |
1688 | * be between 0 and 31, inclusive. */ | |
1689 | static unsigned int | |
1690 | get_bit_at(const uint32_t prefix, unsigned int ofs) | |
1691 | { | |
1692 | return (prefix >> (31 - ofs)) & 1u; | |
1693 | } | |
1694 | ||
1695 | /* Create new branch. */ | |
1696 | static struct trie_node * | |
1697 | trie_branch_create(const ovs_be32 *prefix, unsigned int ofs, unsigned int plen, | |
1698 | unsigned int n_rules) | |
1699 | { | |
1700 | struct trie_node *node = xmalloc(sizeof *node); | |
1701 | ||
1702 | node->prefix = trie_get_prefix(prefix, ofs, plen); | |
1703 | ||
1704 | if (plen <= TRIE_PREFIX_BITS) { | |
1705 | node->nbits = plen; | |
1706 | node->edges[0] = NULL; | |
1707 | node->edges[1] = NULL; | |
1708 | node->n_rules = n_rules; | |
1709 | } else { /* Need intermediate nodes. */ | |
1710 | struct trie_node *subnode = trie_branch_create(prefix, | |
1711 | ofs + TRIE_PREFIX_BITS, | |
1712 | plen - TRIE_PREFIX_BITS, | |
1713 | n_rules); | |
1714 | int bit = get_bit_at(subnode->prefix, 0); | |
1715 | node->nbits = TRIE_PREFIX_BITS; | |
1716 | node->edges[bit] = subnode; | |
1717 | node->edges[!bit] = NULL; | |
1718 | node->n_rules = 0; | |
1719 | } | |
1720 | return node; | |
1721 | } | |
1722 | ||
1723 | static void | |
1724 | trie_node_destroy(struct trie_node *node) | |
1725 | { | |
1726 | free(node); | |
1727 | } | |
1728 | ||
1729 | static void | |
1730 | trie_destroy(struct trie_node *node) | |
1731 | { | |
1732 | if (node) { | |
1733 | trie_destroy(node->edges[0]); | |
1734 | trie_destroy(node->edges[1]); | |
1735 | free(node); | |
1736 | } | |
1737 | } | |
1738 | ||
1739 | static bool | |
1740 | trie_is_leaf(const struct trie_node *trie) | |
1741 | { | |
1742 | return !trie->edges[0] && !trie->edges[1]; /* No children. */ | |
1743 | } | |
1744 | ||
1745 | static void | |
1746 | mask_set_prefix_bits(struct flow_wildcards *wc, uint8_t be32ofs, | |
1747 | unsigned int nbits) | |
1748 | { | |
1749 | ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs]; | |
1750 | unsigned int i; | |
1751 | ||
1752 | for (i = 0; i < nbits / 32; i++) { | |
1753 | mask[i] = OVS_BE32_MAX; | |
1754 | } | |
1755 | if (nbits % 32) { | |
1756 | mask[i] |= htonl(~0u << (32 - nbits % 32)); | |
1757 | } | |
1758 | } | |
1759 | ||
1760 | static bool | |
1761 | mask_prefix_bits_set(const struct flow_wildcards *wc, uint8_t be32ofs, | |
1762 | unsigned int nbits) | |
1763 | { | |
1764 | ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs]; | |
1765 | unsigned int i; | |
1766 | ovs_be32 zeroes = 0; | |
1767 | ||
1768 | for (i = 0; i < nbits / 32; i++) { | |
1769 | zeroes |= ~mask[i]; | |
1770 | } | |
1771 | if (nbits % 32) { | |
1772 | zeroes |= ~mask[i] & htonl(~0u << (32 - nbits % 32)); | |
1773 | } | |
1774 | ||
1775 | return !zeroes; /* All 'nbits' bits set. */ | |
1776 | } | |
1777 | ||
1778 | static struct trie_node ** | |
1779 | trie_next_edge(struct trie_node *node, const ovs_be32 value[], | |
1780 | unsigned int ofs) | |
1781 | { | |
1782 | return node->edges + be_get_bit_at(value, ofs); | |
1783 | } | |
1784 | ||
1785 | static const struct trie_node * | |
1786 | trie_next_node(const struct trie_node *node, const ovs_be32 value[], | |
1787 | unsigned int ofs) | |
1788 | { | |
1789 | return node->edges[be_get_bit_at(value, ofs)]; | |
1790 | } | |
1791 | ||
1792 | /* Return the prefix mask length necessary to find the longest-prefix match for | |
1793 | * the '*value' in the prefix tree 'node'. | |
1794 | * '*checkbits' is set to the number of bits in the prefix mask necessary to | |
1795 | * determine a mismatch, in case there are longer prefixes in the tree below | |
1796 | * the one that matched. | |
1797 | */ | |
1798 | static unsigned int | |
1799 | trie_lookup_value(const struct trie_node *node, const ovs_be32 value[], | |
f0e5aa11 | 1800 | unsigned int n_bits, unsigned int *checkbits) |
13751fd8 | 1801 | { |
197573ac | 1802 | unsigned int ofs = 0, match_len = 0; |
13751fd8 JR |
1803 | const struct trie_node *prev = NULL; |
1804 | ||
197573ac | 1805 | for (; node; prev = node, node = trie_next_node(node, value, ofs)) { |
13751fd8 JR |
1806 | unsigned int eqbits; |
1807 | /* Check if this edge can be followed. */ | |
197573ac JR |
1808 | eqbits = prefix_equal_bits(node->prefix, node->nbits, value, ofs); |
1809 | ofs += eqbits; | |
13751fd8 | 1810 | if (eqbits < node->nbits) { /* Mismatch, nothing more to be found. */ |
197573ac JR |
1811 | /* Bit at offset 'ofs' differed. */ |
1812 | *checkbits = ofs + 1; /* Includes the first mismatching bit. */ | |
13751fd8 JR |
1813 | return match_len; |
1814 | } | |
1815 | /* Full match, check if rules exist at this prefix length. */ | |
1816 | if (node->n_rules > 0) { | |
197573ac | 1817 | match_len = ofs; |
13751fd8 | 1818 | } |
f0e5aa11 JR |
1819 | if (ofs >= n_bits) { |
1820 | *checkbits = n_bits; /* Full prefix. */ | |
1821 | return match_len; | |
1822 | } | |
13751fd8 | 1823 | } |
f0e5aa11 JR |
1824 | /* node == NULL. Full match so far, but we came to a dead end. |
1825 | * need to exclude the other branch if it exists. */ | |
197573ac | 1826 | *checkbits = !prev || trie_is_leaf(prev) ? ofs : ofs + 1; |
13751fd8 JR |
1827 | return match_len; |
1828 | } | |
1829 | ||
1830 | static unsigned int | |
1831 | trie_lookup(const struct cls_trie *trie, const struct flow *flow, | |
1832 | unsigned int *checkbits) | |
1833 | { | |
1834 | const struct mf_field *mf = trie->field; | |
1835 | ||
1836 | /* Check that current flow matches the prerequisites for the trie | |
1837 | * field. Some match fields are used for multiple purposes, so we | |
1838 | * must check that the trie is relevant for this flow. */ | |
1839 | if (mf_are_prereqs_ok(mf, flow)) { | |
1840 | return trie_lookup_value(trie->root, | |
1841 | &((ovs_be32 *)flow)[mf->flow_be32ofs], | |
f0e5aa11 | 1842 | mf->n_bits, checkbits); |
13751fd8 JR |
1843 | } |
1844 | *checkbits = 0; /* Value not used in this case. */ | |
1845 | return UINT_MAX; | |
1846 | } | |
1847 | ||
1848 | /* Returns the length of a prefix match mask for the field 'mf' in 'minimask'. | |
1849 | * Returns the u32 offset to the miniflow data in '*miniflow_index', if | |
1850 | * 'miniflow_index' is not NULL. */ | |
1851 | static unsigned int | |
1852 | minimask_get_prefix_len(const struct minimask *minimask, | |
1853 | const struct mf_field *mf) | |
1854 | { | |
1855 | unsigned int nbits = 0, mask_tz = 0; /* Non-zero when end of mask seen. */ | |
1856 | uint8_t u32_ofs = mf->flow_be32ofs; | |
1857 | uint8_t u32_end = u32_ofs + mf->n_bytes / 4; | |
1858 | ||
1859 | for (; u32_ofs < u32_end; ++u32_ofs) { | |
1860 | uint32_t mask; | |
1861 | mask = ntohl((OVS_FORCE ovs_be32)minimask_get(minimask, u32_ofs)); | |
1862 | ||
1863 | /* Validate mask, count the mask length. */ | |
1864 | if (mask_tz) { | |
1865 | if (mask) { | |
1866 | return 0; /* No bits allowed after mask ended. */ | |
1867 | } | |
1868 | } else { | |
1869 | if (~mask & (~mask + 1)) { | |
1870 | return 0; /* Mask not contiguous. */ | |
1871 | } | |
1872 | mask_tz = ctz32(mask); | |
1873 | nbits += 32 - mask_tz; | |
1874 | } | |
1875 | } | |
1876 | ||
1877 | return nbits; | |
1878 | } | |
1879 | ||
1880 | /* | |
1881 | * This is called only when mask prefix is known to be CIDR and non-zero. | |
1882 | * Relies on the fact that the flow and mask have the same map, and since | |
1883 | * the mask is CIDR, the storage for the flow field exists even if it | |
1884 | * happened to be zeros. | |
1885 | */ | |
1886 | static const ovs_be32 * | |
1887 | minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf) | |
1888 | { | |
27bbe15d | 1889 | return miniflow_get_be32_values(&match->flow) + |
13751fd8 JR |
1890 | count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1)); |
1891 | } | |
1892 | ||
1893 | /* Insert rule in to the prefix tree. | |
1894 | * 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask | |
1895 | * in 'rule'. */ | |
1896 | static void | |
1897 | trie_insert(struct cls_trie *trie, const struct cls_rule *rule, int mlen) | |
1898 | { | |
69d6040e JR |
1899 | trie_insert_prefix(&trie->root, |
1900 | minimatch_get_prefix(&rule->match, trie->field), mlen); | |
1901 | } | |
1902 | ||
1903 | static void | |
1904 | trie_insert_prefix(struct trie_node **edge, const ovs_be32 *prefix, int mlen) | |
1905 | { | |
13751fd8 | 1906 | struct trie_node *node; |
13751fd8 JR |
1907 | int ofs = 0; |
1908 | ||
1909 | /* Walk the tree. */ | |
69d6040e | 1910 | for (; (node = *edge) != NULL; |
13751fd8 JR |
1911 | edge = trie_next_edge(node, prefix, ofs)) { |
1912 | unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen); | |
1913 | ofs += eqbits; | |
1914 | if (eqbits < node->nbits) { | |
1915 | /* Mismatch, new node needs to be inserted above. */ | |
1916 | int old_branch = get_bit_at(node->prefix, eqbits); | |
1917 | ||
1918 | /* New parent node. */ | |
1919 | *edge = trie_branch_create(prefix, ofs - eqbits, eqbits, | |
1920 | ofs == mlen ? 1 : 0); | |
1921 | ||
1922 | /* Adjust old node for its new position in the tree. */ | |
1923 | node->prefix <<= eqbits; | |
1924 | node->nbits -= eqbits; | |
1925 | (*edge)->edges[old_branch] = node; | |
1926 | ||
1927 | /* Check if need a new branch for the new rule. */ | |
1928 | if (ofs < mlen) { | |
1929 | (*edge)->edges[!old_branch] | |
1930 | = trie_branch_create(prefix, ofs, mlen - ofs, 1); | |
1931 | } | |
1932 | return; | |
1933 | } | |
1934 | /* Full match so far. */ | |
1935 | ||
1936 | if (ofs == mlen) { | |
1937 | /* Full match at the current node, rule needs to be added here. */ | |
1938 | node->n_rules++; | |
1939 | return; | |
1940 | } | |
1941 | } | |
1942 | /* Must insert a new tree branch for the new rule. */ | |
1943 | *edge = trie_branch_create(prefix, ofs, mlen - ofs, 1); | |
1944 | } | |
1945 | ||
1946 | /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask | |
1947 | * in 'rule'. */ | |
1948 | static void | |
1949 | trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen) | |
1950 | { | |
69d6040e JR |
1951 | trie_remove_prefix(&trie->root, |
1952 | minimatch_get_prefix(&rule->match, trie->field), mlen); | |
1953 | } | |
1954 | ||
1955 | /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask | |
1956 | * in 'rule'. */ | |
1957 | static void | |
1958 | trie_remove_prefix(struct trie_node **root, const ovs_be32 *prefix, int mlen) | |
1959 | { | |
13751fd8 JR |
1960 | struct trie_node *node; |
1961 | struct trie_node **edges[sizeof(union mf_value) * 8]; | |
1962 | int depth = 0, ofs = 0; | |
1963 | ||
1964 | /* Walk the tree. */ | |
69d6040e | 1965 | for (edges[0] = root; |
13751fd8 JR |
1966 | (node = *edges[depth]) != NULL; |
1967 | edges[++depth] = trie_next_edge(node, prefix, ofs)) { | |
1968 | unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen); | |
69d6040e | 1969 | |
13751fd8 JR |
1970 | if (eqbits < node->nbits) { |
1971 | /* Mismatch, nothing to be removed. This should never happen, as | |
1972 | * only rules in the classifier are ever removed. */ | |
1973 | break; /* Log a warning. */ | |
1974 | } | |
1975 | /* Full match so far. */ | |
1976 | ofs += eqbits; | |
1977 | ||
1978 | if (ofs == mlen) { | |
1979 | /* Full prefix match at the current node, remove rule here. */ | |
1980 | if (!node->n_rules) { | |
1981 | break; /* Log a warning. */ | |
1982 | } | |
1983 | node->n_rules--; | |
1984 | ||
1985 | /* Check if can prune the tree. */ | |
1986 | while (!node->n_rules && !(node->edges[0] && node->edges[1])) { | |
1987 | /* No rules and at most one child node, remove this node. */ | |
1988 | struct trie_node *next; | |
1989 | next = node->edges[0] ? node->edges[0] : node->edges[1]; | |
1990 | ||
1991 | if (next) { | |
1992 | if (node->nbits + next->nbits > TRIE_PREFIX_BITS) { | |
1993 | break; /* Cannot combine. */ | |
1994 | } | |
1995 | /* Combine node with next. */ | |
1996 | next->prefix = node->prefix | next->prefix >> node->nbits; | |
1997 | next->nbits += node->nbits; | |
1998 | } | |
1999 | trie_node_destroy(node); | |
2000 | /* Update the parent's edge. */ | |
2001 | *edges[depth] = next; | |
2002 | if (next || !depth) { | |
2003 | /* Branch not pruned or at root, nothing more to do. */ | |
2004 | break; | |
2005 | } | |
2006 | node = *edges[--depth]; | |
2007 | } | |
2008 | return; | |
2009 | } | |
2010 | } | |
2011 | /* Cannot go deeper. This should never happen, since only rules | |
2012 | * that actually exist in the classifier are ever removed. */ | |
2013 | VLOG_WARN("Trying to remove non-existing rule from a prefix trie."); | |
2014 | } |