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