]>
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" | |
07b37e8f | 25 | #include "odp-util.h" |
d8ae4d67 | 26 | #include "ofp-util.h" |
b5d97350 | 27 | #include "packets.h" |
0b4f2078 | 28 | #include "ovs-thread.h" |
064af421 | 29 | |
b5d97350 | 30 | static struct cls_table *find_table(const struct classifier *, |
5cb7a798 | 31 | const struct minimask *); |
b5d97350 | 32 | static struct cls_table *insert_table(struct classifier *, |
5cb7a798 | 33 | const struct minimask *); |
b5d97350 | 34 | |
b5d97350 BP |
35 | static void destroy_table(struct classifier *, struct cls_table *); |
36 | ||
4aacd02d BP |
37 | static void update_tables_after_insertion(struct classifier *, |
38 | struct cls_table *, | |
39 | unsigned int new_priority); | |
40 | static void update_tables_after_removal(struct classifier *, | |
41 | struct cls_table *, | |
42 | unsigned int del_priority); | |
43 | ||
b5d97350 BP |
44 | static struct cls_rule *find_match(const struct cls_table *, |
45 | const struct flow *); | |
5cb7a798 BP |
46 | static struct cls_rule *find_equal(struct cls_table *, |
47 | const struct miniflow *, uint32_t hash); | |
4aacd02d BP |
48 | static struct cls_rule *insert_rule(struct classifier *, |
49 | struct cls_table *, struct cls_rule *); | |
b5d97350 | 50 | |
b5d97350 BP |
51 | /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ |
52 | #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ | |
53 | for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) | |
54 | #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ | |
55 | for ((RULE) = (HEAD); \ | |
56 | (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ | |
57 | (RULE) = (NEXT)) | |
58 | ||
955f579d | 59 | static struct cls_rule *next_rule_in_list__(struct cls_rule *); |
b5d97350 | 60 | static struct cls_rule *next_rule_in_list(struct cls_rule *); |
81a76618 BP |
61 | \f |
62 | /* cls_rule. */ | |
b5d97350 | 63 | |
81a76618 | 64 | /* Initializes 'rule' to match packets specified by 'match' at the given |
5cb7a798 BP |
65 | * 'priority'. 'match' must satisfy the invariant described in the comment at |
66 | * the definition of struct match. | |
66642cb4 | 67 | * |
48d28ac1 BP |
68 | * The caller must eventually destroy 'rule' with cls_rule_destroy(). |
69 | * | |
81a76618 BP |
70 | * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but |
71 | * internally Open vSwitch supports a wider range.) */ | |
47284b1f | 72 | void |
81a76618 BP |
73 | cls_rule_init(struct cls_rule *rule, |
74 | const struct match *match, unsigned int priority) | |
47284b1f | 75 | { |
5cb7a798 BP |
76 | minimatch_init(&rule->match, match); |
77 | rule->priority = priority; | |
78 | } | |
79 | ||
80 | /* Same as cls_rule_init() for initialization from a "struct minimatch". */ | |
81 | void | |
82 | cls_rule_init_from_minimatch(struct cls_rule *rule, | |
83 | const struct minimatch *match, | |
84 | unsigned int priority) | |
85 | { | |
86 | minimatch_clone(&rule->match, match); | |
81a76618 | 87 | rule->priority = priority; |
685a51a5 JP |
88 | } |
89 | ||
48d28ac1 BP |
90 | /* Initializes 'dst' as a copy of 'src'. |
91 | * | |
b2c1f00b | 92 | * The caller must eventually destroy 'dst' with cls_rule_destroy(). */ |
48d28ac1 BP |
93 | void |
94 | cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) | |
95 | { | |
5cb7a798 BP |
96 | minimatch_clone(&dst->match, &src->match); |
97 | dst->priority = src->priority; | |
48d28ac1 BP |
98 | } |
99 | ||
b2c1f00b BP |
100 | /* Initializes 'dst' with the data in 'src', destroying 'src'. |
101 | * | |
102 | * The caller must eventually destroy 'dst' with cls_rule_destroy(). */ | |
103 | void | |
104 | cls_rule_move(struct cls_rule *dst, struct cls_rule *src) | |
105 | { | |
106 | minimatch_move(&dst->match, &src->match); | |
107 | dst->priority = src->priority; | |
108 | } | |
109 | ||
48d28ac1 BP |
110 | /* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's |
111 | * normally embedded into a larger structure). | |
112 | * | |
113 | * ('rule' must not currently be in a classifier.) */ | |
114 | void | |
5cb7a798 | 115 | cls_rule_destroy(struct cls_rule *rule) |
48d28ac1 | 116 | { |
5cb7a798 | 117 | minimatch_destroy(&rule->match); |
48d28ac1 BP |
118 | } |
119 | ||
81a76618 BP |
120 | /* Returns true if 'a' and 'b' match the same packets at the same priority, |
121 | * false if they differ in some way. */ | |
193eb874 BP |
122 | bool |
123 | cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) | |
124 | { | |
5cb7a798 | 125 | return a->priority == b->priority && minimatch_equal(&a->match, &b->match); |
193eb874 BP |
126 | } |
127 | ||
81a76618 | 128 | /* Returns a hash value for 'rule', folding in 'basis'. */ |
57452fdc BP |
129 | uint32_t |
130 | cls_rule_hash(const struct cls_rule *rule, uint32_t basis) | |
131 | { | |
5cb7a798 | 132 | return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); |
73f33563 BP |
133 | } |
134 | ||
81a76618 | 135 | /* Appends a string describing 'rule' to 's'. */ |
07b37e8f BP |
136 | void |
137 | cls_rule_format(const struct cls_rule *rule, struct ds *s) | |
138 | { | |
5cb7a798 | 139 | minimatch_format(&rule->match, s, rule->priority); |
064af421 | 140 | } |
3ca1de08 BP |
141 | |
142 | /* Returns true if 'rule' matches every packet, false otherwise. */ | |
143 | bool | |
144 | cls_rule_is_catchall(const struct cls_rule *rule) | |
145 | { | |
5cb7a798 | 146 | return minimask_is_catchall(&rule->match.mask); |
3ca1de08 | 147 | } |
064af421 BP |
148 | \f |
149 | /* Initializes 'cls' as a classifier that initially contains no classification | |
150 | * rules. */ | |
151 | void | |
152 | classifier_init(struct classifier *cls) | |
153 | { | |
064af421 | 154 | cls->n_rules = 0; |
b5d97350 | 155 | hmap_init(&cls->tables); |
1f3c5efc | 156 | list_init(&cls->tables_priority); |
c906cedf | 157 | hmap_init(&cls->partitions); |
0b4f2078 | 158 | ovs_rwlock_init(&cls->rwlock); |
064af421 BP |
159 | } |
160 | ||
161 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
162 | * caller's responsibility. */ | |
163 | void | |
164 | classifier_destroy(struct classifier *cls) | |
165 | { | |
166 | if (cls) { | |
c906cedf | 167 | struct cls_table *partition, *next_partition; |
b5d97350 | 168 | struct cls_table *table, *next_table; |
064af421 | 169 | |
b5d97350 | 170 | HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { |
0c09d44e | 171 | destroy_table(cls, table); |
064af421 | 172 | } |
b5d97350 | 173 | hmap_destroy(&cls->tables); |
c906cedf BP |
174 | |
175 | HMAP_FOR_EACH_SAFE (partition, next_partition, hmap_node, | |
176 | &cls->partitions) { | |
177 | hmap_remove(&cls->partitions, &partition->hmap_node); | |
178 | free(partition); | |
179 | } | |
180 | hmap_destroy(&cls->partitions); | |
0b4f2078 | 181 | ovs_rwlock_destroy(&cls->rwlock); |
064af421 BP |
182 | } |
183 | } | |
184 | ||
b5d97350 | 185 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
186 | bool |
187 | classifier_is_empty(const struct classifier *cls) | |
188 | { | |
189 | return cls->n_rules == 0; | |
190 | } | |
191 | ||
dbda2960 | 192 | /* Returns the number of rules in 'cls'. */ |
064af421 BP |
193 | int |
194 | classifier_count(const struct classifier *cls) | |
195 | { | |
196 | return cls->n_rules; | |
197 | } | |
198 | ||
c906cedf BP |
199 | static uint32_t |
200 | hash_metadata(ovs_be64 metadata_) | |
201 | { | |
202 | uint64_t metadata = (OVS_FORCE uint64_t) metadata_; | |
203 | return hash_2words(metadata, metadata >> 32); | |
204 | } | |
205 | ||
206 | static struct cls_partition * | |
207 | find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash) | |
208 | { | |
209 | struct cls_partition *partition; | |
210 | ||
211 | HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) { | |
212 | if (partition->metadata == metadata) { | |
213 | return partition; | |
214 | } | |
215 | } | |
216 | ||
217 | return NULL; | |
218 | } | |
219 | ||
220 | static struct cls_partition * | |
221 | create_partition(struct classifier *cls, struct cls_table *table, | |
222 | ovs_be64 metadata) | |
223 | { | |
224 | uint32_t hash = hash_metadata(metadata); | |
225 | struct cls_partition *partition = find_partition(cls, metadata, hash); | |
226 | if (!partition) { | |
227 | partition = xmalloc(sizeof *partition); | |
228 | partition->metadata = metadata; | |
229 | partition->tags = 0; | |
183126a1 | 230 | tag_tracker_init(&partition->tracker); |
c906cedf BP |
231 | hmap_insert(&cls->partitions, &partition->hmap_node, hash); |
232 | } | |
183126a1 | 233 | tag_tracker_add(&partition->tracker, &partition->tags, table->tag); |
c906cedf BP |
234 | return partition; |
235 | } | |
236 | ||
b5d97350 BP |
237 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
238 | * must not modify or free it. | |
064af421 BP |
239 | * |
240 | * If 'cls' already contains an identical rule (including wildcards, values of | |
241 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
242 | * rule that was replaced. The caller takes ownership of the returned rule and | |
48d28ac1 BP |
243 | * is thus responsible for destroying it with cls_rule_destroy(), freeing the |
244 | * memory block in which it resides, etc., as necessary. | |
064af421 BP |
245 | * |
246 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
247 | * inserting the new rule. In this case, no rules are displaced by the new | |
248 | * rule, even rules that cannot have any effect because the new rule matches a | |
249 | * superset of their flows and has higher priority. */ | |
250 | struct cls_rule * | |
08944c1d | 251 | classifier_replace(struct classifier *cls, struct cls_rule *rule) |
064af421 | 252 | { |
b5d97350 BP |
253 | struct cls_rule *old_rule; |
254 | struct cls_table *table; | |
255 | ||
5cb7a798 | 256 | table = find_table(cls, &rule->match.mask); |
b5d97350 | 257 | if (!table) { |
5cb7a798 | 258 | table = insert_table(cls, &rule->match.mask); |
b5d97350 BP |
259 | } |
260 | ||
4aacd02d | 261 | old_rule = insert_rule(cls, table, rule); |
b5d97350 | 262 | if (!old_rule) { |
c906cedf BP |
263 | if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) { |
264 | ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow); | |
265 | rule->partition = create_partition(cls, table, metadata); | |
266 | } else { | |
267 | rule->partition = NULL; | |
268 | } | |
269 | ||
b5d97350 | 270 | table->n_table_rules++; |
064af421 | 271 | cls->n_rules++; |
c906cedf BP |
272 | } else { |
273 | rule->partition = old_rule->partition; | |
064af421 | 274 | } |
b5d97350 | 275 | return old_rule; |
064af421 BP |
276 | } |
277 | ||
08944c1d BP |
278 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
279 | * must not modify or free it. | |
280 | * | |
281 | * 'cls' must not contain an identical rule (including wildcards, values of | |
282 | * fixed fields, and priority). Use classifier_find_rule_exactly() to find | |
283 | * such a rule. */ | |
284 | void | |
285 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
286 | { | |
287 | struct cls_rule *displaced_rule = classifier_replace(cls, rule); | |
cb22974d | 288 | ovs_assert(!displaced_rule); |
08944c1d BP |
289 | } |
290 | ||
48d28ac1 BP |
291 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy |
292 | * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule' | |
293 | * resides, etc., as necessary. */ | |
064af421 BP |
294 | void |
295 | classifier_remove(struct classifier *cls, struct cls_rule *rule) | |
296 | { | |
c906cedf | 297 | struct cls_partition *partition; |
b5d97350 BP |
298 | struct cls_rule *head; |
299 | struct cls_table *table; | |
064af421 | 300 | |
5cb7a798 | 301 | table = find_table(cls, &rule->match.mask); |
81a76618 | 302 | head = find_equal(table, &rule->match.flow, rule->hmap_node.hash); |
b5d97350 BP |
303 | if (head != rule) { |
304 | list_remove(&rule->list); | |
305 | } else if (list_is_empty(&rule->list)) { | |
306 | hmap_remove(&table->rules, &rule->hmap_node); | |
307 | } else { | |
308 | struct cls_rule *next = CONTAINER_OF(rule->list.next, | |
309 | struct cls_rule, list); | |
064af421 | 310 | |
b5d97350 BP |
311 | list_remove(&rule->list); |
312 | hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); | |
313 | } | |
064af421 | 314 | |
c906cedf | 315 | partition = rule->partition; |
183126a1 BP |
316 | if (partition) { |
317 | tag_tracker_subtract(&partition->tracker, &partition->tags, | |
318 | table->tag); | |
319 | if (!partition->tags) { | |
320 | hmap_remove(&cls->partitions, &partition->hmap_node); | |
321 | free(partition); | |
322 | } | |
c906cedf BP |
323 | } |
324 | ||
f6acdb44 | 325 | if (--table->n_table_rules == 0) { |
b5d97350 | 326 | destroy_table(cls, table); |
4aacd02d BP |
327 | } else { |
328 | update_tables_after_removal(cls, table, rule->priority); | |
4d935a6b | 329 | } |
b5d97350 | 330 | cls->n_rules--; |
064af421 BP |
331 | } |
332 | ||
48c3de13 BP |
333 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
334 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
74f74083 EJ |
335 | * of equal priority match 'flow', returns one arbitrarily. |
336 | * | |
337 | * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the | |
338 | * set of bits that were significant in the lookup. At some point | |
339 | * earlier, 'wc' should have been initialized (e.g., by | |
340 | * flow_wildcards_init_catchall()). */ | |
48c3de13 | 341 | struct cls_rule * |
74f74083 EJ |
342 | classifier_lookup(const struct classifier *cls, const struct flow *flow, |
343 | struct flow_wildcards *wc) | |
48c3de13 | 344 | { |
c906cedf | 345 | const struct cls_partition *partition; |
b5d97350 BP |
346 | struct cls_table *table; |
347 | struct cls_rule *best; | |
c906cedf BP |
348 | tag_type tags; |
349 | ||
350 | /* Determine 'tags' such that, if 'table->tag' doesn't intersect them, then | |
351 | * 'flow' cannot possibly match in 'table': | |
352 | * | |
353 | * - If flow->metadata maps to a given 'partition', then we can use | |
354 | * 'tags' for 'partition->tags'. | |
355 | * | |
356 | * - If flow->metadata has no partition, then no rule in 'cls' has an | |
357 | * exact-match for flow->metadata. That means that we don't need to | |
358 | * search any table that includes flow->metadata in its mask. | |
359 | * | |
360 | * In either case, we always need to search any cls_tables that do not | |
361 | * include flow->metadata in its mask. One way to do that would be to | |
362 | * check the "cls_table"s explicitly for that, but that would require an | |
363 | * extra branch per table. Instead, we mark such a cls_table's 'tags' as | |
364 | * TAG_ALL and make sure that 'tags' is never empty. This means that | |
365 | * 'tags' always intersects such a cls_table's 'tags', so we don't need a | |
366 | * special case. | |
367 | */ | |
368 | partition = (hmap_is_empty(&cls->partitions) | |
369 | ? NULL | |
370 | : find_partition(cls, flow->metadata, | |
371 | hash_metadata(flow->metadata))); | |
372 | tags = partition ? partition->tags : TAG_ARBITRARY; | |
48c3de13 | 373 | |
b5d97350 | 374 | best = NULL; |
1f3c5efc | 375 | LIST_FOR_EACH (table, list_node, &cls->tables_priority) { |
c906cedf BP |
376 | struct cls_rule *rule; |
377 | ||
378 | if (!tag_intersects(tags, table->tag)) { | |
379 | continue; | |
380 | } | |
74f74083 | 381 | |
c906cedf | 382 | rule = find_match(table, flow); |
74f74083 EJ |
383 | if (wc) { |
384 | flow_wildcards_fold_minimask(wc, &table->mask); | |
385 | } | |
1f3c5efc JR |
386 | if (rule) { |
387 | best = rule; | |
388 | LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) { | |
389 | if (table->max_priority <= best->priority) { | |
390 | /* Tables in descending priority order, | |
391 | * can not find anything better. */ | |
392 | return best; | |
393 | } | |
c906cedf BP |
394 | if (!tag_intersects(tags, table->tag)) { |
395 | continue; | |
396 | } | |
397 | ||
1f3c5efc | 398 | rule = find_match(table, flow); |
74f74083 EJ |
399 | if (wc) { |
400 | flow_wildcards_fold_minimask(wc, &table->mask); | |
401 | } | |
1f3c5efc JR |
402 | if (rule && rule->priority > best->priority) { |
403 | best = rule; | |
404 | } | |
4d935a6b | 405 | } |
1f3c5efc | 406 | break; |
b5d97350 | 407 | } |
48c3de13 | 408 | } |
b5d97350 | 409 | return best; |
48c3de13 BP |
410 | } |
411 | ||
b5d97350 BP |
412 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
413 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
c084ce1d | 414 | * contain an exact match. */ |
064af421 BP |
415 | struct cls_rule * |
416 | classifier_find_rule_exactly(const struct classifier *cls, | |
76ecc721 | 417 | const struct cls_rule *target) |
064af421 | 418 | { |
b5d97350 BP |
419 | struct cls_rule *head, *rule; |
420 | struct cls_table *table; | |
064af421 | 421 | |
5cb7a798 | 422 | table = find_table(cls, &target->match.mask); |
b5d97350 BP |
423 | if (!table) { |
424 | return NULL; | |
064af421 BP |
425 | } |
426 | ||
4d935a6b JR |
427 | /* Skip if there is no hope. */ |
428 | if (target->priority > table->max_priority) { | |
429 | return NULL; | |
430 | } | |
431 | ||
81a76618 | 432 | head = find_equal(table, &target->match.flow, |
5cb7a798 BP |
433 | miniflow_hash_in_minimask(&target->match.flow, |
434 | &target->match.mask, 0)); | |
b5d97350 BP |
435 | FOR_EACH_RULE_IN_LIST (rule, head) { |
436 | if (target->priority >= rule->priority) { | |
437 | return target->priority == rule->priority ? rule : NULL; | |
064af421 BP |
438 | } |
439 | } | |
440 | return NULL; | |
441 | } | |
442 | ||
81a76618 BP |
443 | /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the |
444 | * same matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
445 | * contain an exact match. */ | |
446 | struct cls_rule * | |
447 | classifier_find_match_exactly(const struct classifier *cls, | |
448 | const struct match *target, | |
449 | unsigned int priority) | |
450 | { | |
451 | struct cls_rule *retval; | |
452 | struct cls_rule cr; | |
453 | ||
454 | cls_rule_init(&cr, target, priority); | |
455 | retval = classifier_find_rule_exactly(cls, &cr); | |
48d28ac1 | 456 | cls_rule_destroy(&cr); |
81a76618 BP |
457 | |
458 | return retval; | |
459 | } | |
460 | ||
faa50f40 BP |
461 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
462 | * considered to overlap if both rules have the same priority and a packet | |
463 | * could match both. */ | |
49bdc010 JP |
464 | bool |
465 | classifier_rule_overlaps(const struct classifier *cls, | |
faa50f40 | 466 | const struct cls_rule *target) |
49bdc010 | 467 | { |
b5d97350 | 468 | struct cls_table *table; |
49bdc010 | 469 | |
1f3c5efc JR |
470 | /* Iterate tables in the descending max priority order. */ |
471 | LIST_FOR_EACH (table, list_node, &cls->tables_priority) { | |
5cb7a798 BP |
472 | uint32_t storage[FLOW_U32S]; |
473 | struct minimask mask; | |
b5d97350 | 474 | struct cls_rule *head; |
49bdc010 | 475 | |
4d935a6b | 476 | if (target->priority > table->max_priority) { |
1f3c5efc | 477 | break; /* Can skip this and the rest of the tables. */ |
4d935a6b JR |
478 | } |
479 | ||
5cb7a798 | 480 | minimask_combine(&mask, &target->match.mask, &table->mask, storage); |
b5d97350 | 481 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { |
49bdc010 JP |
482 | struct cls_rule *rule; |
483 | ||
b5d97350 | 484 | FOR_EACH_RULE_IN_LIST (rule, head) { |
4d935a6b JR |
485 | if (rule->priority < target->priority) { |
486 | break; /* Rules in descending priority order. */ | |
487 | } | |
faa50f40 | 488 | if (rule->priority == target->priority |
5cb7a798 BP |
489 | && miniflow_equal_in_minimask(&target->match.flow, |
490 | &rule->match.flow, &mask)) { | |
49bdc010 JP |
491 | return true; |
492 | } | |
493 | } | |
494 | } | |
495 | } | |
496 | ||
497 | return false; | |
498 | } | |
6ceeaa92 BP |
499 | |
500 | /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more | |
501 | * specific than 'criteria'. That is, 'rule' matches 'criteria' and this | |
502 | * function returns true if, for every field: | |
503 | * | |
504 | * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the | |
505 | * field, or | |
506 | * | |
507 | * - 'criteria' wildcards the field, | |
508 | * | |
509 | * Conversely, 'rule' does not match 'criteria' and this function returns false | |
510 | * if, for at least one field: | |
511 | * | |
512 | * - 'criteria' and 'rule' specify different values for the field, or | |
513 | * | |
514 | * - 'criteria' specifies a value for the field but 'rule' wildcards it. | |
515 | * | |
516 | * Equivalently, the truth table for whether a field matches is: | |
517 | * | |
518 | * rule | |
519 | * | |
520 | * c wildcard exact | |
521 | * r +---------+---------+ | |
522 | * i wild | yes | yes | | |
523 | * t card | | | | |
524 | * e +---------+---------+ | |
525 | * r exact | no |if values| | |
526 | * i | |are equal| | |
527 | * a +---------+---------+ | |
528 | * | |
529 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
530 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
531 | * | |
81a76618 | 532 | * Ignores rule->priority. */ |
6ceeaa92 BP |
533 | bool |
534 | cls_rule_is_loose_match(const struct cls_rule *rule, | |
5cb7a798 | 535 | const struct minimatch *criteria) |
6ceeaa92 | 536 | { |
5cb7a798 BP |
537 | return (!minimask_has_extra(&rule->match.mask, &criteria->mask) |
538 | && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow, | |
539 | &criteria->mask)); | |
6ceeaa92 | 540 | } |
b5d97350 | 541 | \f |
5ecc9d81 BP |
542 | /* Iteration. */ |
543 | ||
544 | static bool | |
545 | rule_matches(const struct cls_rule *rule, const struct cls_rule *target) | |
546 | { | |
547 | return (!target | |
5cb7a798 BP |
548 | || miniflow_equal_in_minimask(&rule->match.flow, |
549 | &target->match.flow, | |
550 | &target->match.mask)); | |
5ecc9d81 BP |
551 | } |
552 | ||
553 | static struct cls_rule * | |
554 | search_table(const struct cls_table *table, const struct cls_rule *target) | |
555 | { | |
5cb7a798 | 556 | if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) { |
5ecc9d81 BP |
557 | struct cls_rule *rule; |
558 | ||
559 | HMAP_FOR_EACH (rule, hmap_node, &table->rules) { | |
560 | if (rule_matches(rule, target)) { | |
561 | return rule; | |
562 | } | |
563 | } | |
564 | } | |
565 | return NULL; | |
566 | } | |
567 | ||
6ceeaa92 | 568 | /* Initializes 'cursor' for iterating through rules in 'cls': |
5ecc9d81 | 569 | * |
6ceeaa92 | 570 | * - If 'target' is null, the cursor will visit every rule in 'cls'. |
5ecc9d81 | 571 | * |
6ceeaa92 BP |
572 | * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls' |
573 | * such that cls_rule_is_loose_match(rule, target) returns true. | |
5ecc9d81 | 574 | * |
6ceeaa92 | 575 | * Ignores target->priority. */ |
5ecc9d81 BP |
576 | void |
577 | cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, | |
578 | const struct cls_rule *target) | |
579 | { | |
580 | cursor->cls = cls; | |
3ca1de08 | 581 | cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; |
5ecc9d81 BP |
582 | } |
583 | ||
584 | /* Returns the first matching cls_rule in 'cursor''s iteration, or a null | |
585 | * pointer if there are no matches. */ | |
586 | struct cls_rule * | |
587 | cls_cursor_first(struct cls_cursor *cursor) | |
588 | { | |
589 | struct cls_table *table; | |
590 | ||
7ac8d8cf | 591 | HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) { |
5ecc9d81 BP |
592 | struct cls_rule *rule = search_table(table, cursor->target); |
593 | if (rule) { | |
594 | cursor->table = table; | |
595 | return rule; | |
596 | } | |
597 | } | |
598 | ||
599 | return NULL; | |
600 | } | |
601 | ||
602 | /* Returns the next matching cls_rule in 'cursor''s iteration, or a null | |
603 | * pointer if there are no more matches. */ | |
604 | struct cls_rule * | |
9850cd0f | 605 | cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_) |
5ecc9d81 | 606 | { |
9850cd0f | 607 | struct cls_rule *rule = CONST_CAST(struct cls_rule *, rule_); |
5ecc9d81 BP |
608 | const struct cls_table *table; |
609 | struct cls_rule *next; | |
610 | ||
955f579d BP |
611 | next = next_rule_in_list__(rule); |
612 | if (next->priority < rule->priority) { | |
5ecc9d81 BP |
613 | return next; |
614 | } | |
615 | ||
955f579d BP |
616 | /* 'next' is the head of the list, that is, the rule that is included in |
617 | * the table's hmap. (This is important when the classifier contains rules | |
618 | * that differ only in priority.) */ | |
619 | rule = next; | |
5ecc9d81 BP |
620 | HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { |
621 | if (rule_matches(rule, cursor->target)) { | |
622 | return rule; | |
623 | } | |
624 | } | |
625 | ||
7ac8d8cf BP |
626 | table = cursor->table; |
627 | HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) { | |
5ecc9d81 BP |
628 | rule = search_table(table, cursor->target); |
629 | if (rule) { | |
630 | cursor->table = table; | |
631 | return rule; | |
632 | } | |
633 | } | |
634 | ||
635 | return NULL; | |
636 | } | |
637 | \f | |
b5d97350 | 638 | static struct cls_table * |
5cb7a798 | 639 | find_table(const struct classifier *cls, const struct minimask *mask) |
b5d97350 BP |
640 | { |
641 | struct cls_table *table; | |
064af421 | 642 | |
5cb7a798 | 643 | HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0), |
b5d97350 | 644 | &cls->tables) { |
5cb7a798 | 645 | if (minimask_equal(mask, &table->mask)) { |
b5d97350 | 646 | return table; |
064af421 BP |
647 | } |
648 | } | |
b5d97350 | 649 | return NULL; |
064af421 | 650 | } |
064af421 | 651 | |
b5d97350 | 652 | static struct cls_table * |
5cb7a798 | 653 | insert_table(struct classifier *cls, const struct minimask *mask) |
b5d97350 | 654 | { |
c906cedf | 655 | uint32_t hash = minimask_hash(mask, 0); |
b5d97350 | 656 | struct cls_table *table; |
064af421 | 657 | |
b5d97350 BP |
658 | table = xzalloc(sizeof *table); |
659 | hmap_init(&table->rules); | |
5cb7a798 BP |
660 | minimask_clone(&table->mask, mask); |
661 | hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0)); | |
1f3c5efc | 662 | list_push_back(&cls->tables_priority, &table->list_node); |
c906cedf BP |
663 | table->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX |
664 | ? tag_create_deterministic(hash) | |
665 | : TAG_ALL); | |
064af421 | 666 | |
b5d97350 | 667 | return table; |
064af421 BP |
668 | } |
669 | ||
b5d97350 BP |
670 | static void |
671 | destroy_table(struct classifier *cls, struct cls_table *table) | |
672 | { | |
5cb7a798 | 673 | minimask_destroy(&table->mask); |
b5d97350 BP |
674 | hmap_remove(&cls->tables, &table->hmap_node); |
675 | hmap_destroy(&table->rules); | |
1f3c5efc | 676 | list_remove(&table->list_node); |
b5d97350 BP |
677 | free(table); |
678 | } | |
064af421 | 679 | |
4aacd02d BP |
680 | /* This function performs the following updates for 'table' in 'cls' following |
681 | * the addition of a new rule with priority 'new_priority' to 'table': | |
682 | * | |
683 | * - Update 'table->max_priority' and 'table->max_count' if necessary. | |
684 | * | |
685 | * - Update 'table''s position in 'cls->tables_priority' if necessary. | |
686 | * | |
687 | * This function should only be called after adding a new rule, not after | |
688 | * replacing a rule by an identical one or modifying a rule in-place. */ | |
689 | static void | |
690 | update_tables_after_insertion(struct classifier *cls, struct cls_table *table, | |
691 | unsigned int new_priority) | |
692 | { | |
693 | if (new_priority == table->max_priority) { | |
694 | ++table->max_count; | |
695 | } else if (new_priority > table->max_priority) { | |
696 | struct cls_table *iter; | |
697 | ||
698 | table->max_priority = new_priority; | |
699 | table->max_count = 1; | |
700 | ||
701 | /* Possibly move 'table' earlier in the priority list. If we break out | |
702 | * of the loop, then 'table' should be moved just after that 'iter'. | |
703 | * If the loop terminates normally, then 'iter' will be the list head | |
704 | * and we'll move table just after that (e.g. to the front of the | |
705 | * list). */ | |
706 | iter = table; | |
707 | LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node, | |
708 | &cls->tables_priority) { | |
709 | if (iter->max_priority >= table->max_priority) { | |
710 | break; | |
711 | } | |
712 | } | |
713 | ||
714 | /* Move 'table' just after 'iter' (unless it's already there). */ | |
715 | if (iter->list_node.next != &table->list_node) { | |
716 | list_splice(iter->list_node.next, | |
717 | &table->list_node, table->list_node.next); | |
718 | } | |
719 | } | |
720 | } | |
721 | ||
722 | /* This function performs the following updates for 'table' in 'cls' following | |
723 | * the deletion of a rule with priority 'del_priority' from 'table': | |
724 | * | |
725 | * - Update 'table->max_priority' and 'table->max_count' if necessary. | |
726 | * | |
727 | * - Update 'table''s position in 'cls->tables_priority' if necessary. | |
728 | * | |
729 | * This function should only be called after removing a rule, not after | |
730 | * replacing a rule by an identical one or modifying a rule in-place. */ | |
731 | static void | |
732 | update_tables_after_removal(struct classifier *cls, struct cls_table *table, | |
733 | unsigned int del_priority) | |
734 | { | |
735 | struct cls_table *iter; | |
736 | ||
737 | if (del_priority == table->max_priority && --table->max_count == 0) { | |
738 | struct cls_rule *head; | |
739 | ||
740 | table->max_priority = 0; | |
741 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { | |
742 | if (head->priority > table->max_priority) { | |
743 | table->max_priority = head->priority; | |
744 | table->max_count = 1; | |
745 | } else if (head->priority == table->max_priority) { | |
746 | ++table->max_count; | |
747 | } | |
748 | } | |
749 | ||
750 | /* Possibly move 'table' later in the priority list. If we break out | |
751 | * of the loop, then 'table' should be moved just before that 'iter'. | |
752 | * If the loop terminates normally, then 'iter' will be the list head | |
753 | * and we'll move table just before that (e.g. to the back of the | |
754 | * list). */ | |
755 | iter = table; | |
756 | LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) { | |
757 | if (iter->max_priority <= table->max_priority) { | |
758 | break; | |
759 | } | |
760 | } | |
761 | ||
762 | /* Move 'table' just before 'iter' (unless it's already there). */ | |
763 | if (iter->list_node.prev != &table->list_node) { | |
764 | list_splice(&iter->list_node, | |
765 | &table->list_node, table->list_node.next); | |
766 | } | |
767 | } | |
768 | } | |
769 | ||
064af421 | 770 | static struct cls_rule * |
b5d97350 BP |
771 | find_match(const struct cls_table *table, const struct flow *flow) |
772 | { | |
5cb7a798 | 773 | uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0); |
b5d97350 | 774 | struct cls_rule *rule; |
b5d97350 | 775 | |
5cb7a798 | 776 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) { |
df40c152 | 777 | if (minimatch_matches_flow(&rule->match, flow)) { |
b5d97350 | 778 | return rule; |
064af421 BP |
779 | } |
780 | } | |
c23740be | 781 | |
064af421 BP |
782 | return NULL; |
783 | } | |
784 | ||
785 | static struct cls_rule * | |
5cb7a798 | 786 | find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash) |
064af421 | 787 | { |
b5d97350 | 788 | struct cls_rule *head; |
064af421 | 789 | |
b5d97350 | 790 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { |
5cb7a798 | 791 | if (miniflow_equal(&head->match.flow, flow)) { |
b5d97350 | 792 | return head; |
064af421 BP |
793 | } |
794 | } | |
795 | return NULL; | |
796 | } | |
797 | ||
b5d97350 | 798 | static struct cls_rule * |
4aacd02d BP |
799 | insert_rule(struct classifier *cls, |
800 | struct cls_table *table, struct cls_rule *new) | |
064af421 | 801 | { |
b5d97350 | 802 | struct cls_rule *head; |
4aacd02d | 803 | struct cls_rule *old = NULL; |
064af421 | 804 | |
5cb7a798 BP |
805 | new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow, |
806 | &new->match.mask, 0); | |
064af421 | 807 | |
81a76618 | 808 | head = find_equal(table, &new->match.flow, new->hmap_node.hash); |
b5d97350 BP |
809 | if (!head) { |
810 | hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); | |
811 | list_init(&new->list); | |
4aacd02d | 812 | goto out; |
b5d97350 BP |
813 | } else { |
814 | /* Scan the list for the insertion point that will keep the list in | |
815 | * order of decreasing priority. */ | |
816 | struct cls_rule *rule; | |
817 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
818 | if (new->priority >= rule->priority) { | |
819 | if (rule == head) { | |
820 | /* 'new' is the new highest-priority flow in the list. */ | |
821 | hmap_replace(&table->rules, | |
822 | &rule->hmap_node, &new->hmap_node); | |
823 | } | |
064af421 | 824 | |
b5d97350 BP |
825 | if (new->priority == rule->priority) { |
826 | list_replace(&new->list, &rule->list); | |
4aacd02d BP |
827 | old = rule; |
828 | goto out; | |
b5d97350 BP |
829 | } else { |
830 | list_insert(&rule->list, &new->list); | |
4aacd02d | 831 | goto out; |
b5d97350 BP |
832 | } |
833 | } | |
834 | } | |
064af421 | 835 | |
b5d97350 BP |
836 | /* Insert 'new' at the end of the list. */ |
837 | list_push_back(&head->list, &new->list); | |
064af421 | 838 | } |
4aacd02d BP |
839 | |
840 | out: | |
841 | if (!old) { | |
842 | update_tables_after_insertion(cls, table, new->priority); | |
843 | } | |
844 | return old; | |
064af421 BP |
845 | } |
846 | ||
b5d97350 | 847 | static struct cls_rule * |
955f579d | 848 | next_rule_in_list__(struct cls_rule *rule) |
064af421 | 849 | { |
b5d97350 | 850 | struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); |
955f579d BP |
851 | return next; |
852 | } | |
853 | ||
854 | static struct cls_rule * | |
855 | next_rule_in_list(struct cls_rule *rule) | |
856 | { | |
857 | struct cls_rule *next = next_rule_in_list__(rule); | |
b5d97350 | 858 | return next->priority < rule->priority ? next : NULL; |
064af421 | 859 | } |