]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2009, 2010, 2011, 2012 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" |
064af421 | 28 | |
b5d97350 | 29 | static struct cls_table *find_table(const struct classifier *, |
5cb7a798 | 30 | const struct minimask *); |
b5d97350 | 31 | static struct cls_table *insert_table(struct classifier *, |
5cb7a798 | 32 | const struct minimask *); |
b5d97350 | 33 | |
b5d97350 BP |
34 | static void destroy_table(struct classifier *, struct cls_table *); |
35 | ||
b5d97350 BP |
36 | static struct cls_rule *find_match(const struct cls_table *, |
37 | const struct flow *); | |
5cb7a798 BP |
38 | static struct cls_rule *find_equal(struct cls_table *, |
39 | const struct miniflow *, uint32_t hash); | |
b5d97350 BP |
40 | static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *); |
41 | ||
b5d97350 BP |
42 | /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ |
43 | #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ | |
44 | for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) | |
45 | #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ | |
46 | for ((RULE) = (HEAD); \ | |
47 | (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ | |
48 | (RULE) = (NEXT)) | |
49 | ||
955f579d | 50 | static struct cls_rule *next_rule_in_list__(struct cls_rule *); |
b5d97350 | 51 | static struct cls_rule *next_rule_in_list(struct cls_rule *); |
81a76618 BP |
52 | \f |
53 | /* cls_rule. */ | |
b5d97350 | 54 | |
81a76618 | 55 | /* Initializes 'rule' to match packets specified by 'match' at the given |
5cb7a798 BP |
56 | * 'priority'. 'match' must satisfy the invariant described in the comment at |
57 | * the definition of struct match. | |
66642cb4 | 58 | * |
48d28ac1 BP |
59 | * The caller must eventually destroy 'rule' with cls_rule_destroy(). |
60 | * | |
81a76618 BP |
61 | * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but |
62 | * internally Open vSwitch supports a wider range.) */ | |
47284b1f | 63 | void |
81a76618 BP |
64 | cls_rule_init(struct cls_rule *rule, |
65 | const struct match *match, unsigned int priority) | |
47284b1f | 66 | { |
5cb7a798 BP |
67 | minimatch_init(&rule->match, match); |
68 | rule->priority = priority; | |
69 | } | |
70 | ||
71 | /* Same as cls_rule_init() for initialization from a "struct minimatch". */ | |
72 | void | |
73 | cls_rule_init_from_minimatch(struct cls_rule *rule, | |
74 | const struct minimatch *match, | |
75 | unsigned int priority) | |
76 | { | |
77 | minimatch_clone(&rule->match, match); | |
81a76618 | 78 | rule->priority = priority; |
685a51a5 JP |
79 | } |
80 | ||
48d28ac1 BP |
81 | /* Initializes 'dst' as a copy of 'src'. |
82 | * | |
83 | * The caller must eventually destroy 'rule' with cls_rule_destroy(). */ | |
84 | void | |
85 | cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) | |
86 | { | |
5cb7a798 BP |
87 | minimatch_clone(&dst->match, &src->match); |
88 | dst->priority = src->priority; | |
48d28ac1 BP |
89 | } |
90 | ||
91 | /* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's | |
92 | * normally embedded into a larger structure). | |
93 | * | |
94 | * ('rule' must not currently be in a classifier.) */ | |
95 | void | |
5cb7a798 | 96 | cls_rule_destroy(struct cls_rule *rule) |
48d28ac1 | 97 | { |
5cb7a798 | 98 | minimatch_destroy(&rule->match); |
48d28ac1 BP |
99 | } |
100 | ||
81a76618 BP |
101 | /* Returns true if 'a' and 'b' match the same packets at the same priority, |
102 | * false if they differ in some way. */ | |
193eb874 BP |
103 | bool |
104 | cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) | |
105 | { | |
5cb7a798 | 106 | return a->priority == b->priority && minimatch_equal(&a->match, &b->match); |
193eb874 BP |
107 | } |
108 | ||
81a76618 | 109 | /* Returns a hash value for 'rule', folding in 'basis'. */ |
57452fdc BP |
110 | uint32_t |
111 | cls_rule_hash(const struct cls_rule *rule, uint32_t basis) | |
112 | { | |
5cb7a798 | 113 | return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); |
73f33563 BP |
114 | } |
115 | ||
81a76618 | 116 | /* Appends a string describing 'rule' to 's'. */ |
07b37e8f BP |
117 | void |
118 | cls_rule_format(const struct cls_rule *rule, struct ds *s) | |
119 | { | |
5cb7a798 | 120 | minimatch_format(&rule->match, s, rule->priority); |
064af421 | 121 | } |
3ca1de08 BP |
122 | |
123 | /* Returns true if 'rule' matches every packet, false otherwise. */ | |
124 | bool | |
125 | cls_rule_is_catchall(const struct cls_rule *rule) | |
126 | { | |
5cb7a798 | 127 | return minimask_is_catchall(&rule->match.mask); |
3ca1de08 | 128 | } |
064af421 BP |
129 | \f |
130 | /* Initializes 'cls' as a classifier that initially contains no classification | |
131 | * rules. */ | |
132 | void | |
133 | classifier_init(struct classifier *cls) | |
134 | { | |
064af421 | 135 | cls->n_rules = 0; |
b5d97350 | 136 | hmap_init(&cls->tables); |
064af421 BP |
137 | } |
138 | ||
139 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
140 | * caller's responsibility. */ | |
141 | void | |
142 | classifier_destroy(struct classifier *cls) | |
143 | { | |
144 | if (cls) { | |
b5d97350 | 145 | struct cls_table *table, *next_table; |
064af421 | 146 | |
b5d97350 | 147 | HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { |
0c09d44e | 148 | destroy_table(cls, table); |
064af421 | 149 | } |
b5d97350 | 150 | hmap_destroy(&cls->tables); |
064af421 BP |
151 | } |
152 | } | |
153 | ||
b5d97350 | 154 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
155 | bool |
156 | classifier_is_empty(const struct classifier *cls) | |
157 | { | |
158 | return cls->n_rules == 0; | |
159 | } | |
160 | ||
dbda2960 | 161 | /* Returns the number of rules in 'cls'. */ |
064af421 BP |
162 | int |
163 | classifier_count(const struct classifier *cls) | |
164 | { | |
165 | return cls->n_rules; | |
166 | } | |
167 | ||
b5d97350 BP |
168 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
169 | * must not modify or free it. | |
064af421 BP |
170 | * |
171 | * If 'cls' already contains an identical rule (including wildcards, values of | |
172 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
173 | * rule that was replaced. The caller takes ownership of the returned rule and | |
48d28ac1 BP |
174 | * is thus responsible for destroying it with cls_rule_destroy(), freeing the |
175 | * memory block in which it resides, etc., as necessary. | |
064af421 BP |
176 | * |
177 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
178 | * inserting the new rule. In this case, no rules are displaced by the new | |
179 | * rule, even rules that cannot have any effect because the new rule matches a | |
180 | * superset of their flows and has higher priority. */ | |
181 | struct cls_rule * | |
08944c1d | 182 | classifier_replace(struct classifier *cls, struct cls_rule *rule) |
064af421 | 183 | { |
b5d97350 BP |
184 | struct cls_rule *old_rule; |
185 | struct cls_table *table; | |
186 | ||
5cb7a798 | 187 | table = find_table(cls, &rule->match.mask); |
b5d97350 | 188 | if (!table) { |
5cb7a798 | 189 | table = insert_table(cls, &rule->match.mask); |
b5d97350 BP |
190 | } |
191 | ||
192 | old_rule = insert_rule(table, rule); | |
193 | if (!old_rule) { | |
194 | table->n_table_rules++; | |
064af421 BP |
195 | cls->n_rules++; |
196 | } | |
b5d97350 | 197 | return old_rule; |
064af421 BP |
198 | } |
199 | ||
08944c1d BP |
200 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
201 | * must not modify or free it. | |
202 | * | |
203 | * 'cls' must not contain an identical rule (including wildcards, values of | |
204 | * fixed fields, and priority). Use classifier_find_rule_exactly() to find | |
205 | * such a rule. */ | |
206 | void | |
207 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
208 | { | |
209 | struct cls_rule *displaced_rule = classifier_replace(cls, rule); | |
cb22974d | 210 | ovs_assert(!displaced_rule); |
08944c1d BP |
211 | } |
212 | ||
48d28ac1 BP |
213 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy |
214 | * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule' | |
215 | * resides, etc., as necessary. */ | |
064af421 BP |
216 | void |
217 | classifier_remove(struct classifier *cls, struct cls_rule *rule) | |
218 | { | |
b5d97350 BP |
219 | struct cls_rule *head; |
220 | struct cls_table *table; | |
064af421 | 221 | |
5cb7a798 | 222 | table = find_table(cls, &rule->match.mask); |
81a76618 | 223 | head = find_equal(table, &rule->match.flow, rule->hmap_node.hash); |
b5d97350 BP |
224 | if (head != rule) { |
225 | list_remove(&rule->list); | |
226 | } else if (list_is_empty(&rule->list)) { | |
227 | hmap_remove(&table->rules, &rule->hmap_node); | |
228 | } else { | |
229 | struct cls_rule *next = CONTAINER_OF(rule->list.next, | |
230 | struct cls_rule, list); | |
064af421 | 231 | |
b5d97350 BP |
232 | list_remove(&rule->list); |
233 | hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); | |
234 | } | |
064af421 | 235 | |
f6acdb44 | 236 | if (--table->n_table_rules == 0) { |
b5d97350 | 237 | destroy_table(cls, table); |
064af421 | 238 | } |
b5d97350 BP |
239 | |
240 | cls->n_rules--; | |
064af421 BP |
241 | } |
242 | ||
48c3de13 BP |
243 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
244 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
3c4486a5 | 245 | * of equal priority match 'flow', returns one arbitrarily. */ |
48c3de13 | 246 | struct cls_rule * |
3c4486a5 | 247 | classifier_lookup(const struct classifier *cls, const struct flow *flow) |
48c3de13 | 248 | { |
b5d97350 BP |
249 | struct cls_table *table; |
250 | struct cls_rule *best; | |
48c3de13 | 251 | |
b5d97350 BP |
252 | best = NULL; |
253 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { | |
3c4486a5 BP |
254 | struct cls_rule *rule = find_match(table, flow); |
255 | if (rule && (!best || rule->priority > best->priority)) { | |
256 | best = rule; | |
b5d97350 | 257 | } |
48c3de13 | 258 | } |
b5d97350 | 259 | return best; |
48c3de13 BP |
260 | } |
261 | ||
b5d97350 BP |
262 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
263 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
c084ce1d | 264 | * contain an exact match. */ |
064af421 BP |
265 | struct cls_rule * |
266 | classifier_find_rule_exactly(const struct classifier *cls, | |
76ecc721 | 267 | const struct cls_rule *target) |
064af421 | 268 | { |
b5d97350 BP |
269 | struct cls_rule *head, *rule; |
270 | struct cls_table *table; | |
064af421 | 271 | |
5cb7a798 | 272 | table = find_table(cls, &target->match.mask); |
b5d97350 BP |
273 | if (!table) { |
274 | return NULL; | |
064af421 BP |
275 | } |
276 | ||
81a76618 | 277 | head = find_equal(table, &target->match.flow, |
5cb7a798 BP |
278 | miniflow_hash_in_minimask(&target->match.flow, |
279 | &target->match.mask, 0)); | |
b5d97350 BP |
280 | FOR_EACH_RULE_IN_LIST (rule, head) { |
281 | if (target->priority >= rule->priority) { | |
282 | return target->priority == rule->priority ? rule : NULL; | |
064af421 BP |
283 | } |
284 | } | |
285 | return NULL; | |
286 | } | |
287 | ||
81a76618 BP |
288 | /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the |
289 | * same matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
290 | * contain an exact match. */ | |
291 | struct cls_rule * | |
292 | classifier_find_match_exactly(const struct classifier *cls, | |
293 | const struct match *target, | |
294 | unsigned int priority) | |
295 | { | |
296 | struct cls_rule *retval; | |
297 | struct cls_rule cr; | |
298 | ||
299 | cls_rule_init(&cr, target, priority); | |
300 | retval = classifier_find_rule_exactly(cls, &cr); | |
48d28ac1 | 301 | cls_rule_destroy(&cr); |
81a76618 BP |
302 | |
303 | return retval; | |
304 | } | |
305 | ||
faa50f40 BP |
306 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
307 | * considered to overlap if both rules have the same priority and a packet | |
308 | * could match both. */ | |
49bdc010 JP |
309 | bool |
310 | classifier_rule_overlaps(const struct classifier *cls, | |
faa50f40 | 311 | const struct cls_rule *target) |
49bdc010 | 312 | { |
b5d97350 | 313 | struct cls_table *table; |
49bdc010 | 314 | |
b5d97350 | 315 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { |
5cb7a798 BP |
316 | uint32_t storage[FLOW_U32S]; |
317 | struct minimask mask; | |
b5d97350 | 318 | struct cls_rule *head; |
49bdc010 | 319 | |
5cb7a798 | 320 | minimask_combine(&mask, &target->match.mask, &table->mask, storage); |
b5d97350 | 321 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { |
49bdc010 JP |
322 | struct cls_rule *rule; |
323 | ||
b5d97350 | 324 | FOR_EACH_RULE_IN_LIST (rule, head) { |
faa50f40 | 325 | if (rule->priority == target->priority |
5cb7a798 BP |
326 | && miniflow_equal_in_minimask(&target->match.flow, |
327 | &rule->match.flow, &mask)) { | |
49bdc010 JP |
328 | return true; |
329 | } | |
330 | } | |
331 | } | |
332 | } | |
333 | ||
334 | return false; | |
335 | } | |
6ceeaa92 BP |
336 | |
337 | /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more | |
338 | * specific than 'criteria'. That is, 'rule' matches 'criteria' and this | |
339 | * function returns true if, for every field: | |
340 | * | |
341 | * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the | |
342 | * field, or | |
343 | * | |
344 | * - 'criteria' wildcards the field, | |
345 | * | |
346 | * Conversely, 'rule' does not match 'criteria' and this function returns false | |
347 | * if, for at least one field: | |
348 | * | |
349 | * - 'criteria' and 'rule' specify different values for the field, or | |
350 | * | |
351 | * - 'criteria' specifies a value for the field but 'rule' wildcards it. | |
352 | * | |
353 | * Equivalently, the truth table for whether a field matches is: | |
354 | * | |
355 | * rule | |
356 | * | |
357 | * c wildcard exact | |
358 | * r +---------+---------+ | |
359 | * i wild | yes | yes | | |
360 | * t card | | | | |
361 | * e +---------+---------+ | |
362 | * r exact | no |if values| | |
363 | * i | |are equal| | |
364 | * a +---------+---------+ | |
365 | * | |
366 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
367 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
368 | * | |
81a76618 | 369 | * Ignores rule->priority. */ |
6ceeaa92 BP |
370 | bool |
371 | cls_rule_is_loose_match(const struct cls_rule *rule, | |
5cb7a798 | 372 | const struct minimatch *criteria) |
6ceeaa92 | 373 | { |
5cb7a798 BP |
374 | return (!minimask_has_extra(&rule->match.mask, &criteria->mask) |
375 | && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow, | |
376 | &criteria->mask)); | |
6ceeaa92 | 377 | } |
b5d97350 | 378 | \f |
5ecc9d81 BP |
379 | /* Iteration. */ |
380 | ||
381 | static bool | |
382 | rule_matches(const struct cls_rule *rule, const struct cls_rule *target) | |
383 | { | |
384 | return (!target | |
5cb7a798 BP |
385 | || miniflow_equal_in_minimask(&rule->match.flow, |
386 | &target->match.flow, | |
387 | &target->match.mask)); | |
5ecc9d81 BP |
388 | } |
389 | ||
390 | static struct cls_rule * | |
391 | search_table(const struct cls_table *table, const struct cls_rule *target) | |
392 | { | |
5cb7a798 | 393 | if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) { |
5ecc9d81 BP |
394 | struct cls_rule *rule; |
395 | ||
396 | HMAP_FOR_EACH (rule, hmap_node, &table->rules) { | |
397 | if (rule_matches(rule, target)) { | |
398 | return rule; | |
399 | } | |
400 | } | |
401 | } | |
402 | return NULL; | |
403 | } | |
404 | ||
6ceeaa92 | 405 | /* Initializes 'cursor' for iterating through rules in 'cls': |
5ecc9d81 | 406 | * |
6ceeaa92 | 407 | * - If 'target' is null, the cursor will visit every rule in 'cls'. |
5ecc9d81 | 408 | * |
6ceeaa92 BP |
409 | * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls' |
410 | * such that cls_rule_is_loose_match(rule, target) returns true. | |
5ecc9d81 | 411 | * |
6ceeaa92 | 412 | * Ignores target->priority. */ |
5ecc9d81 BP |
413 | void |
414 | cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, | |
415 | const struct cls_rule *target) | |
416 | { | |
417 | cursor->cls = cls; | |
3ca1de08 | 418 | cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; |
5ecc9d81 BP |
419 | } |
420 | ||
421 | /* Returns the first matching cls_rule in 'cursor''s iteration, or a null | |
422 | * pointer if there are no matches. */ | |
423 | struct cls_rule * | |
424 | cls_cursor_first(struct cls_cursor *cursor) | |
425 | { | |
426 | struct cls_table *table; | |
427 | ||
7ac8d8cf | 428 | HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) { |
5ecc9d81 BP |
429 | struct cls_rule *rule = search_table(table, cursor->target); |
430 | if (rule) { | |
431 | cursor->table = table; | |
432 | return rule; | |
433 | } | |
434 | } | |
435 | ||
436 | return NULL; | |
437 | } | |
438 | ||
439 | /* Returns the next matching cls_rule in 'cursor''s iteration, or a null | |
440 | * pointer if there are no more matches. */ | |
441 | struct cls_rule * | |
442 | cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) | |
443 | { | |
444 | const struct cls_table *table; | |
445 | struct cls_rule *next; | |
446 | ||
955f579d BP |
447 | next = next_rule_in_list__(rule); |
448 | if (next->priority < rule->priority) { | |
5ecc9d81 BP |
449 | return next; |
450 | } | |
451 | ||
955f579d BP |
452 | /* 'next' is the head of the list, that is, the rule that is included in |
453 | * the table's hmap. (This is important when the classifier contains rules | |
454 | * that differ only in priority.) */ | |
455 | rule = next; | |
5ecc9d81 BP |
456 | HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { |
457 | if (rule_matches(rule, cursor->target)) { | |
458 | return rule; | |
459 | } | |
460 | } | |
461 | ||
7ac8d8cf BP |
462 | table = cursor->table; |
463 | HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) { | |
5ecc9d81 BP |
464 | rule = search_table(table, cursor->target); |
465 | if (rule) { | |
466 | cursor->table = table; | |
467 | return rule; | |
468 | } | |
469 | } | |
470 | ||
471 | return NULL; | |
472 | } | |
473 | \f | |
b5d97350 | 474 | static struct cls_table * |
5cb7a798 | 475 | find_table(const struct classifier *cls, const struct minimask *mask) |
b5d97350 BP |
476 | { |
477 | struct cls_table *table; | |
064af421 | 478 | |
5cb7a798 | 479 | HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0), |
b5d97350 | 480 | &cls->tables) { |
5cb7a798 | 481 | if (minimask_equal(mask, &table->mask)) { |
b5d97350 | 482 | return table; |
064af421 BP |
483 | } |
484 | } | |
b5d97350 | 485 | return NULL; |
064af421 | 486 | } |
064af421 | 487 | |
b5d97350 | 488 | static struct cls_table * |
5cb7a798 | 489 | insert_table(struct classifier *cls, const struct minimask *mask) |
b5d97350 BP |
490 | { |
491 | struct cls_table *table; | |
064af421 | 492 | |
b5d97350 BP |
493 | table = xzalloc(sizeof *table); |
494 | hmap_init(&table->rules); | |
5cb7a798 BP |
495 | minimask_clone(&table->mask, mask); |
496 | hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0)); | |
064af421 | 497 | |
b5d97350 | 498 | return table; |
064af421 BP |
499 | } |
500 | ||
b5d97350 BP |
501 | static void |
502 | destroy_table(struct classifier *cls, struct cls_table *table) | |
503 | { | |
5cb7a798 | 504 | minimask_destroy(&table->mask); |
b5d97350 BP |
505 | hmap_remove(&cls->tables, &table->hmap_node); |
506 | hmap_destroy(&table->rules); | |
507 | free(table); | |
508 | } | |
064af421 | 509 | |
064af421 | 510 | static struct cls_rule * |
b5d97350 BP |
511 | find_match(const struct cls_table *table, const struct flow *flow) |
512 | { | |
5cb7a798 | 513 | uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0); |
b5d97350 | 514 | struct cls_rule *rule; |
b5d97350 | 515 | |
5cb7a798 BP |
516 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) { |
517 | if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow, | |
518 | &table->mask)) { | |
b5d97350 | 519 | return rule; |
064af421 BP |
520 | } |
521 | } | |
c23740be | 522 | |
064af421 BP |
523 | return NULL; |
524 | } | |
525 | ||
526 | static struct cls_rule * | |
5cb7a798 | 527 | find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash) |
064af421 | 528 | { |
b5d97350 | 529 | struct cls_rule *head; |
064af421 | 530 | |
b5d97350 | 531 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { |
5cb7a798 | 532 | if (miniflow_equal(&head->match.flow, flow)) { |
b5d97350 | 533 | return head; |
064af421 BP |
534 | } |
535 | } | |
536 | return NULL; | |
537 | } | |
538 | ||
b5d97350 BP |
539 | static struct cls_rule * |
540 | insert_rule(struct cls_table *table, struct cls_rule *new) | |
064af421 | 541 | { |
b5d97350 | 542 | struct cls_rule *head; |
064af421 | 543 | |
5cb7a798 BP |
544 | new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow, |
545 | &new->match.mask, 0); | |
064af421 | 546 | |
81a76618 | 547 | head = find_equal(table, &new->match.flow, new->hmap_node.hash); |
b5d97350 BP |
548 | if (!head) { |
549 | hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); | |
550 | list_init(&new->list); | |
551 | return NULL; | |
552 | } else { | |
553 | /* Scan the list for the insertion point that will keep the list in | |
554 | * order of decreasing priority. */ | |
555 | struct cls_rule *rule; | |
556 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
557 | if (new->priority >= rule->priority) { | |
558 | if (rule == head) { | |
559 | /* 'new' is the new highest-priority flow in the list. */ | |
560 | hmap_replace(&table->rules, | |
561 | &rule->hmap_node, &new->hmap_node); | |
562 | } | |
064af421 | 563 | |
b5d97350 BP |
564 | if (new->priority == rule->priority) { |
565 | list_replace(&new->list, &rule->list); | |
566 | return rule; | |
567 | } else { | |
568 | list_insert(&rule->list, &new->list); | |
569 | return NULL; | |
570 | } | |
571 | } | |
572 | } | |
064af421 | 573 | |
b5d97350 BP |
574 | /* Insert 'new' at the end of the list. */ |
575 | list_push_back(&head->list, &new->list); | |
576 | return NULL; | |
064af421 | 577 | } |
064af421 BP |
578 | } |
579 | ||
b5d97350 | 580 | static struct cls_rule * |
955f579d | 581 | next_rule_in_list__(struct cls_rule *rule) |
064af421 | 582 | { |
b5d97350 | 583 | struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); |
955f579d BP |
584 | return next; |
585 | } | |
586 | ||
587 | static struct cls_rule * | |
588 | next_rule_in_list(struct cls_rule *rule) | |
589 | { | |
590 | struct cls_rule *next = next_rule_in_list__(rule); | |
b5d97350 | 591 | return next->priority < rule->priority ? next : NULL; |
064af421 | 592 | } |