]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
63e60b86 | 2 | * Copyright (c) 2009, 2010 Nicira Networks. |
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> | |
68d1c8c3 | 22 | #include "dynamic-string.h" |
064af421 BP |
23 | #include "flow.h" |
24 | #include "hash.h" | |
b5d97350 | 25 | #include "packets.h" |
064af421 | 26 | |
b5d97350 BP |
27 | static struct cls_table *find_table(const struct classifier *, |
28 | const struct flow_wildcards *); | |
29 | static struct cls_table *insert_table(struct classifier *, | |
30 | const struct flow_wildcards *); | |
31 | ||
32 | static struct cls_table *classifier_first_table(const struct classifier *); | |
33 | static struct cls_table *classifier_next_table(const struct classifier *, | |
34 | const struct cls_table *); | |
35 | static void destroy_table(struct classifier *, struct cls_table *); | |
36 | ||
37 | static bool should_include(const struct cls_table *, int include); | |
38 | ||
39 | static struct cls_rule *find_match(const struct cls_table *, | |
40 | const struct flow *); | |
41 | static struct cls_rule *find_equal(struct cls_table *, const struct flow *, | |
42 | uint32_t hash); | |
43 | static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *); | |
44 | ||
45 | static bool flow_equal_except(const struct flow *, const struct flow *, | |
46 | const struct flow_wildcards *); | |
47 | static void zero_wildcards(struct flow *, const struct flow_wildcards *); | |
48 | ||
49 | /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ | |
50 | #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ | |
51 | for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) | |
52 | #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ | |
53 | for ((RULE) = (HEAD); \ | |
54 | (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ | |
55 | (RULE) = (NEXT)) | |
56 | ||
57 | static struct cls_rule *next_rule_in_list(struct cls_rule *); | |
58 | ||
59 | static struct cls_table * | |
60 | cls_table_from_hmap_node(const struct hmap_node *node) | |
61 | { | |
62 | return node ? CONTAINER_OF(node, struct cls_table, hmap_node) : NULL; | |
63 | } | |
64 | ||
65 | static struct cls_rule * | |
66 | cls_rule_from_hmap_node(const struct hmap_node *node) | |
67 | { | |
68 | return node ? CONTAINER_OF(node, struct cls_rule, hmap_node) : NULL; | |
69 | } | |
70 | ||
71 | /* Returns the cls_table within 'cls' that has no wildcards, or NULL if there | |
72 | * is none. */ | |
73 | struct cls_table * | |
74 | classifier_exact_table(const struct classifier *cls) | |
75 | { | |
76 | struct flow_wildcards exact_wc; | |
77 | flow_wildcards_init_exact(&exact_wc); | |
78 | return find_table(cls, &exact_wc); | |
79 | } | |
80 | ||
81 | /* Returns the first rule in 'table', or a null pointer if 'table' is NULL. */ | |
82 | struct cls_rule * | |
83 | cls_table_first_rule(const struct cls_table *table) | |
84 | { | |
85 | return table ? cls_rule_from_hmap_node(hmap_first(&table->rules)) : NULL; | |
86 | } | |
87 | ||
88 | /* Returns the next rule in 'table' following 'rule', or a null pointer if | |
89 | * 'rule' is the last rule in 'table'. */ | |
90 | struct cls_rule * | |
91 | cls_table_next_rule(const struct cls_table *table, const struct cls_rule *rule) | |
92 | { | |
93 | struct cls_rule *next | |
94 | = CONTAINER_OF(rule->list.next, struct cls_rule, hmap_node); | |
95 | ||
96 | return (next->priority < rule->priority | |
97 | ? next | |
98 | : cls_rule_from_hmap_node(hmap_next(&table->rules, | |
99 | &next->hmap_node))); | |
100 | } | |
101 | ||
102 | static void | |
103 | cls_rule_init__(struct cls_rule *rule, | |
104 | const struct flow *flow, uint32_t wildcards) | |
105 | { | |
106 | rule->flow = *flow; | |
107 | flow_wildcards_init(&rule->wc, wildcards); | |
52ce26ee | 108 | cls_rule_zero_wildcarded_fields(rule); |
b5d97350 | 109 | } |
064af421 BP |
110 | |
111 | /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given | |
112 | * 'wildcards' and 'priority'.*/ | |
113 | void | |
ae412e7d | 114 | cls_rule_from_flow(const struct flow *flow, uint32_t wildcards, |
659586ef | 115 | unsigned int priority, struct cls_rule *rule) |
064af421 | 116 | { |
b5d97350 | 117 | cls_rule_init__(rule, flow, wildcards); |
064af421 | 118 | rule->priority = priority; |
064af421 BP |
119 | } |
120 | ||
f9bfea14 BP |
121 | /* Converts the ofp_match in 'match' (with format 'flow_format', one of NXFF_*) |
122 | * into a cls_rule in 'rule', with the given 'priority'. 'cookie' is used | |
123 | * when 'flow_format' is NXFF_TUN_ID_FROM_COOKIE. */ | |
064af421 | 124 | void |
659586ef | 125 | cls_rule_from_match(const struct ofp_match *match, unsigned int priority, |
f9bfea14 | 126 | int flow_format, uint64_t cookie, |
659586ef | 127 | struct cls_rule *rule) |
064af421 BP |
128 | { |
129 | uint32_t wildcards; | |
b5d97350 BP |
130 | struct flow flow; |
131 | ||
f9bfea14 | 132 | flow_from_match(match, flow_format, cookie, &flow, &wildcards); |
b5d97350 | 133 | cls_rule_init__(rule, &flow, wildcards); |
064af421 | 134 | rule->priority = rule->wc.wildcards ? priority : UINT16_MAX; |
b5d97350 BP |
135 | } |
136 | ||
cf3fad8a BP |
137 | /* Initializes 'rule' as a "catch-all" rule that matches every packet, with |
138 | * priority 'priority'. */ | |
139 | void | |
140 | cls_rule_init_catchall(struct cls_rule *rule, unsigned int priority) | |
141 | { | |
142 | memset(&rule->flow, 0, sizeof rule->flow); | |
143 | flow_wildcards_init(&rule->wc, OVSFW_ALL); | |
144 | rule->priority = priority; | |
145 | } | |
146 | ||
b5d97350 BP |
147 | /* For each bit or field wildcarded in 'rule', sets the corresponding bit or |
148 | * field in 'flow' to all-0-bits. It is important to maintain this invariant | |
149 | * in a clr_rule that might be inserted into a classifier. | |
150 | * | |
151 | * It is never necessary to call this function directly for a cls_rule that is | |
152 | * initialized or modified only by cls_rule_*() functions. It is useful to | |
153 | * restore the invariant in a cls_rule whose 'wc' member is modified by hand. | |
154 | */ | |
155 | void | |
52ce26ee | 156 | cls_rule_zero_wildcarded_fields(struct cls_rule *rule) |
b5d97350 BP |
157 | { |
158 | zero_wildcards(&rule->flow, &rule->wc); | |
064af421 BP |
159 | } |
160 | ||
64420dfa BP |
161 | void |
162 | cls_rule_set_in_port(struct cls_rule *rule, uint16_t odp_port) | |
163 | { | |
164 | rule->wc.wildcards &= ~OFPFW_IN_PORT; | |
165 | rule->flow.in_port = odp_port; | |
166 | } | |
167 | ||
168 | void | |
169 | cls_rule_set_dl_type(struct cls_rule *rule, ovs_be16 dl_type) | |
170 | { | |
171 | rule->wc.wildcards &= ~OFPFW_DL_TYPE; | |
172 | rule->flow.dl_type = dl_type; | |
173 | } | |
174 | ||
175 | void | |
176 | cls_rule_set_dl_src(struct cls_rule *rule, const uint8_t dl_src[ETH_ADDR_LEN]) | |
177 | { | |
178 | rule->wc.wildcards &= ~OFPFW_DL_SRC; | |
179 | memcpy(rule->flow.dl_src, dl_src, ETH_ADDR_LEN); | |
180 | } | |
181 | ||
182 | void | |
183 | cls_rule_set_dl_dst(struct cls_rule *rule, const uint8_t dl_dst[ETH_ADDR_LEN]) | |
184 | { | |
185 | rule->wc.wildcards &= ~OFPFW_DL_DST; | |
186 | memcpy(rule->flow.dl_dst, dl_dst, ETH_ADDR_LEN); | |
187 | } | |
188 | ||
189 | void | |
190 | cls_rule_set_tp_src(struct cls_rule *rule, ovs_be16 tp_src) | |
191 | { | |
192 | rule->wc.wildcards &= ~OFPFW_TP_SRC; | |
193 | rule->flow.tp_src = tp_src; | |
194 | } | |
195 | ||
196 | void | |
197 | cls_rule_set_tp_dst(struct cls_rule *rule, ovs_be16 tp_dst) | |
198 | { | |
199 | rule->wc.wildcards &= ~OFPFW_TP_DST; | |
200 | rule->flow.tp_dst = tp_dst; | |
201 | } | |
202 | ||
203 | void | |
204 | cls_rule_set_nw_proto(struct cls_rule *rule, uint8_t nw_proto) | |
205 | { | |
206 | rule->wc.wildcards &= ~OFPFW_NW_PROTO; | |
207 | rule->flow.nw_proto = nw_proto; | |
208 | } | |
209 | ||
210 | void | |
211 | cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) | |
212 | { | |
213 | flow_wildcards_set_nw_src_mask(&rule->wc, htonl(UINT32_MAX)); | |
214 | rule->flow.nw_src = nw_src; | |
215 | } | |
216 | ||
217 | void | |
218 | cls_rule_set_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) | |
219 | { | |
220 | flow_wildcards_set_nw_dst_mask(&rule->wc, htonl(UINT32_MAX)); | |
221 | rule->flow.nw_dst = nw_dst; | |
222 | } | |
223 | ||
68d1c8c3 BP |
224 | /* Converts 'rule' to a string and returns the string. The caller must free |
225 | * the string (with free()). */ | |
226 | char * | |
227 | cls_rule_to_string(const struct cls_rule *rule) | |
228 | { | |
229 | struct ds s = DS_EMPTY_INITIALIZER; | |
230 | ds_put_format(&s, "wildcards=%x priority=%u ", | |
231 | rule->wc.wildcards, rule->priority); | |
232 | flow_format(&s, &rule->flow); | |
233 | return ds_cstr(&s); | |
234 | } | |
235 | ||
064af421 BP |
236 | /* Prints cls_rule 'rule', for debugging. |
237 | * | |
238 | * (The output could be improved and expanded, but this was good enough to | |
239 | * debug the classifier.) */ | |
240 | void | |
241 | cls_rule_print(const struct cls_rule *rule) | |
242 | { | |
243 | printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority); | |
244 | flow_print(stdout, &rule->flow); | |
245 | putc('\n', stdout); | |
246 | } | |
064af421 BP |
247 | \f |
248 | /* Initializes 'cls' as a classifier that initially contains no classification | |
249 | * rules. */ | |
250 | void | |
251 | classifier_init(struct classifier *cls) | |
252 | { | |
064af421 | 253 | cls->n_rules = 0; |
b5d97350 | 254 | hmap_init(&cls->tables); |
064af421 BP |
255 | } |
256 | ||
257 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
258 | * caller's responsibility. */ | |
259 | void | |
260 | classifier_destroy(struct classifier *cls) | |
261 | { | |
262 | if (cls) { | |
b5d97350 | 263 | struct cls_table *table, *next_table; |
064af421 | 264 | |
b5d97350 BP |
265 | HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { |
266 | hmap_destroy(&table->rules); | |
267 | hmap_remove(&cls->tables, &table->hmap_node); | |
268 | free(table); | |
064af421 | 269 | } |
b5d97350 | 270 | hmap_destroy(&cls->tables); |
064af421 BP |
271 | } |
272 | } | |
273 | ||
b5d97350 | 274 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
275 | bool |
276 | classifier_is_empty(const struct classifier *cls) | |
277 | { | |
278 | return cls->n_rules == 0; | |
279 | } | |
280 | ||
281 | /* Returns the number of rules in 'classifier'. */ | |
282 | int | |
283 | classifier_count(const struct classifier *cls) | |
284 | { | |
285 | return cls->n_rules; | |
286 | } | |
287 | ||
288 | /* Returns the number of rules in 'classifier' that have no wildcards. */ | |
289 | int | |
290 | classifier_count_exact(const struct classifier *cls) | |
291 | { | |
b5d97350 BP |
292 | struct cls_table *exact_table = classifier_exact_table(cls); |
293 | return exact_table ? exact_table->n_table_rules : 0; | |
064af421 BP |
294 | } |
295 | ||
b5d97350 BP |
296 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
297 | * must not modify or free it. | |
064af421 BP |
298 | * |
299 | * If 'cls' already contains an identical rule (including wildcards, values of | |
300 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
301 | * rule that was replaced. The caller takes ownership of the returned rule and | |
302 | * is thus responsible for freeing it, etc., as necessary. | |
303 | * | |
304 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
305 | * inserting the new rule. In this case, no rules are displaced by the new | |
306 | * rule, even rules that cannot have any effect because the new rule matches a | |
307 | * superset of their flows and has higher priority. */ | |
308 | struct cls_rule * | |
309 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
310 | { | |
b5d97350 BP |
311 | struct cls_rule *old_rule; |
312 | struct cls_table *table; | |
313 | ||
314 | table = find_table(cls, &rule->wc); | |
315 | if (!table) { | |
316 | table = insert_table(cls, &rule->wc); | |
317 | } | |
318 | ||
319 | old_rule = insert_rule(table, rule); | |
320 | if (!old_rule) { | |
321 | table->n_table_rules++; | |
064af421 BP |
322 | cls->n_rules++; |
323 | } | |
b5d97350 | 324 | return old_rule; |
064af421 BP |
325 | } |
326 | ||
b5d97350 BP |
327 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to free |
328 | * 'rule', if this is desirable. */ | |
064af421 BP |
329 | void |
330 | classifier_remove(struct classifier *cls, struct cls_rule *rule) | |
331 | { | |
b5d97350 BP |
332 | struct cls_rule *head; |
333 | struct cls_table *table; | |
064af421 | 334 | |
b5d97350 BP |
335 | table = find_table(cls, &rule->wc); |
336 | head = find_equal(table, &rule->flow, rule->hmap_node.hash); | |
337 | if (head != rule) { | |
338 | list_remove(&rule->list); | |
339 | } else if (list_is_empty(&rule->list)) { | |
340 | hmap_remove(&table->rules, &rule->hmap_node); | |
341 | } else { | |
342 | struct cls_rule *next = CONTAINER_OF(rule->list.next, | |
343 | struct cls_rule, list); | |
064af421 | 344 | |
b5d97350 BP |
345 | list_remove(&rule->list); |
346 | hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); | |
347 | } | |
064af421 | 348 | |
b5d97350 BP |
349 | if (--table->n_table_rules == 0 && !table->n_refs) { |
350 | destroy_table(cls, table); | |
064af421 | 351 | } |
b5d97350 BP |
352 | |
353 | cls->n_rules--; | |
064af421 BP |
354 | } |
355 | ||
48c3de13 BP |
356 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
357 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
358 | * of equal priority match 'flow', returns one arbitrarily. | |
359 | * | |
b5d97350 BP |
360 | * 'include' is a combination of CLS_INC_* values that specify tables to |
361 | * include in the search. */ | |
48c3de13 BP |
362 | struct cls_rule * |
363 | classifier_lookup(const struct classifier *cls, const struct flow *flow, | |
364 | int include) | |
365 | { | |
b5d97350 BP |
366 | struct cls_table *table; |
367 | struct cls_rule *best; | |
48c3de13 | 368 | |
b5d97350 BP |
369 | best = NULL; |
370 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { | |
371 | if (should_include(table, include)) { | |
372 | struct cls_rule *rule = find_match(table, flow); | |
373 | if (rule && (!best || rule->priority > best->priority)) { | |
374 | best = rule; | |
375 | } | |
376 | } | |
48c3de13 | 377 | } |
b5d97350 | 378 | return best; |
48c3de13 BP |
379 | } |
380 | ||
b5d97350 BP |
381 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
382 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
383 | * contain an exact match. | |
384 | * | |
385 | * Priority is ignored for exact-match rules (because OpenFlow 1.0 always | |
386 | * treats exact-match rules as highest priority). */ | |
064af421 BP |
387 | struct cls_rule * |
388 | classifier_find_rule_exactly(const struct classifier *cls, | |
76ecc721 | 389 | const struct cls_rule *target) |
064af421 | 390 | { |
b5d97350 BP |
391 | struct cls_rule *head, *rule; |
392 | struct cls_table *table; | |
064af421 | 393 | |
b5d97350 BP |
394 | table = find_table(cls, &target->wc); |
395 | if (!table) { | |
396 | return NULL; | |
064af421 BP |
397 | } |
398 | ||
b5d97350 BP |
399 | head = find_equal(table, &target->flow, flow_hash(&target->flow, 0)); |
400 | if (!target->wc.wildcards) { | |
401 | return head; | |
402 | } | |
403 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
404 | if (target->priority >= rule->priority) { | |
405 | return target->priority == rule->priority ? rule : NULL; | |
064af421 BP |
406 | } |
407 | } | |
408 | return NULL; | |
409 | } | |
410 | ||
faa50f40 BP |
411 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
412 | * considered to overlap if both rules have the same priority and a packet | |
413 | * could match both. */ | |
49bdc010 JP |
414 | bool |
415 | classifier_rule_overlaps(const struct classifier *cls, | |
faa50f40 | 416 | const struct cls_rule *target) |
49bdc010 | 417 | { |
b5d97350 | 418 | struct cls_table *table; |
49bdc010 | 419 | |
b5d97350 BP |
420 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { |
421 | struct flow_wildcards wc; | |
422 | struct cls_rule *head; | |
49bdc010 | 423 | |
b5d97350 BP |
424 | flow_wildcards_combine(&wc, &target->wc, &table->wc); |
425 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { | |
49bdc010 JP |
426 | struct cls_rule *rule; |
427 | ||
b5d97350 | 428 | FOR_EACH_RULE_IN_LIST (rule, head) { |
faa50f40 | 429 | if (rule->priority == target->priority |
b5d97350 | 430 | && flow_equal_except(&target->flow, &rule->flow, &wc)) { |
49bdc010 JP |
431 | return true; |
432 | } | |
433 | } | |
434 | } | |
435 | } | |
436 | ||
437 | return false; | |
438 | } | |
439 | ||
b5d97350 BP |
440 | /* Searches 'cls' for rules that exactly match 'target' or are more specific |
441 | * than 'target'. That is, a given 'rule' matches 'target' if, for every | |
442 | * field: | |
443 | * | |
444 | * - 'target' and 'rule' specify the same (non-wildcarded) value for the | |
445 | * field, or | |
446 | * | |
447 | * - 'target' wildcards the field, | |
448 | * | |
449 | * but not if: | |
450 | * | |
451 | * - 'target' and 'rule' specify different values for the field, or | |
452 | * | |
453 | * - 'target' specifies a value for the field but 'rule' wildcards it. | |
454 | * | |
455 | * Equivalently, the truth table for whether a field matches is: | |
456 | * | |
457 | * rule | |
458 | * | |
459 | * wildcard exact | |
460 | * +---------+---------+ | |
461 | * t wild | yes | yes | | |
462 | * a card | | | | |
463 | * r +---------+---------+ | |
464 | * g exact | no |if values| | |
465 | * e | |are equal| | |
466 | * t +---------+---------+ | |
467 | * | |
468 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
469 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
470 | * | |
471 | * Ignores target->priority. | |
064af421 BP |
472 | * |
473 | * 'callback' is allowed to delete the rule that is passed as its argument, but | |
b5d97350 BP |
474 | * it must not delete (or move) any other rules in 'cls' that have the same |
475 | * wildcards as the argument rule. */ | |
064af421 | 476 | void |
b5d97350 | 477 | classifier_for_each_match(const struct classifier *cls_, |
064af421 BP |
478 | const struct cls_rule *target, |
479 | int include, cls_cb_func *callback, void *aux) | |
480 | { | |
b5d97350 BP |
481 | struct classifier *cls = (struct classifier *) cls_; |
482 | struct cls_table *table, *next_table; | |
483 | ||
484 | for (table = classifier_first_table(cls); table; table = next_table) { | |
485 | if (should_include(table, include) | |
486 | && !flow_wildcards_has_extra(&table->wc, &target->wc)) { | |
487 | /* We have eliminated the "no" case in the truth table above. Two | |
488 | * of the three remaining cases are trivial. We only need to check | |
489 | * the fourth case, where both 'rule' and 'target' require an exact | |
490 | * match. */ | |
491 | struct cls_rule *head, *next_head; | |
492 | ||
493 | table->n_refs++; | |
494 | HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { | |
495 | if (flow_equal_except(&head->flow, &target->flow, | |
496 | &target->wc)) { | |
497 | struct cls_rule *rule, *next_rule; | |
498 | ||
499 | FOR_EACH_RULE_IN_LIST_SAFE (rule, next_rule, head) { | |
500 | callback(rule, aux); | |
064af421 BP |
501 | } |
502 | } | |
064af421 | 503 | } |
b5d97350 BP |
504 | next_table = classifier_next_table(cls, table); |
505 | if (!--table->n_refs && !table->n_table_rules) { | |
506 | destroy_table(cls, table); | |
064af421 BP |
507 | } |
508 | } else { | |
b5d97350 | 509 | next_table = classifier_next_table(cls, table); |
064af421 BP |
510 | } |
511 | } | |
512 | } | |
513 | ||
514 | /* 'callback' is allowed to delete the rule that is passed as its argument, but | |
b5d97350 BP |
515 | * it must not delete (or move) any other rules in 'cls' that have the same |
516 | * wildcards as the argument rule. | |
35950f0c | 517 | * |
b5d97350 | 518 | * If 'include' is CLS_INC_EXACT then CLASSIFIER_FOR_EACH_EXACT_RULE is |
35950f0c | 519 | * probably easier to use. */ |
064af421 | 520 | void |
b5d97350 BP |
521 | classifier_for_each(const struct classifier *cls_, int include, |
522 | cls_cb_func *callback, void *aux) | |
523 | { | |
524 | struct classifier *cls = (struct classifier *) cls_; | |
525 | struct cls_table *table, *next_table; | |
526 | ||
527 | for (table = classifier_first_table(cls); table; table = next_table) { | |
528 | if (should_include(table, include)) { | |
529 | struct cls_rule *head, *next_head; | |
530 | ||
531 | table->n_refs++; | |
532 | HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { | |
533 | struct cls_rule *rule, *next_rule; | |
534 | ||
535 | FOR_EACH_RULE_IN_LIST_SAFE (rule, next_rule, head) { | |
536 | callback(rule, aux); | |
064af421 BP |
537 | } |
538 | } | |
b5d97350 BP |
539 | next_table = classifier_next_table(cls, table); |
540 | if (!--table->n_refs && !table->n_table_rules) { | |
541 | destroy_table(cls, table); | |
542 | } | |
543 | } else { | |
544 | next_table = classifier_next_table(cls, table); | |
064af421 BP |
545 | } |
546 | } | |
b5d97350 BP |
547 | } |
548 | \f | |
549 | static struct cls_table * | |
550 | find_table(const struct classifier *cls, const struct flow_wildcards *wc) | |
551 | { | |
552 | struct cls_table *table; | |
064af421 | 553 | |
b5d97350 BP |
554 | HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc), |
555 | &cls->tables) { | |
556 | if (flow_wildcards_equal(wc, &table->wc)) { | |
557 | return table; | |
064af421 BP |
558 | } |
559 | } | |
b5d97350 | 560 | return NULL; |
064af421 | 561 | } |
064af421 | 562 | |
b5d97350 BP |
563 | static struct cls_table * |
564 | insert_table(struct classifier *cls, const struct flow_wildcards *wc) | |
565 | { | |
566 | struct cls_table *table; | |
064af421 | 567 | |
b5d97350 BP |
568 | table = xzalloc(sizeof *table); |
569 | hmap_init(&table->rules); | |
570 | table->wc = *wc; | |
571 | hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc)); | |
064af421 | 572 | |
b5d97350 | 573 | return table; |
064af421 BP |
574 | } |
575 | ||
b5d97350 BP |
576 | static struct cls_table * |
577 | classifier_first_table(const struct classifier *cls) | |
064af421 | 578 | { |
b5d97350 | 579 | return cls_table_from_hmap_node(hmap_first(&cls->tables)); |
064af421 BP |
580 | } |
581 | ||
b5d97350 BP |
582 | static struct cls_table * |
583 | classifier_next_table(const struct classifier *cls, | |
584 | const struct cls_table *table) | |
064af421 | 585 | { |
b5d97350 BP |
586 | return cls_table_from_hmap_node(hmap_next(&cls->tables, |
587 | &table->hmap_node)); | |
588 | } | |
064af421 | 589 | |
b5d97350 BP |
590 | static void |
591 | destroy_table(struct classifier *cls, struct cls_table *table) | |
592 | { | |
593 | hmap_remove(&cls->tables, &table->hmap_node); | |
594 | hmap_destroy(&table->rules); | |
595 | free(table); | |
596 | } | |
064af421 | 597 | |
b5d97350 BP |
598 | /* Returns true if 'table' should be included by an operation with the |
599 | * specified 'include' (a combination of CLS_INC_*). */ | |
600 | static bool | |
601 | should_include(const struct cls_table *table, int include) | |
602 | { | |
603 | return include & (table->wc.wildcards ? CLS_INC_WILD : CLS_INC_EXACT); | |
064af421 BP |
604 | } |
605 | ||
064af421 | 606 | static struct cls_rule * |
b5d97350 BP |
607 | find_match(const struct cls_table *table, const struct flow *flow) |
608 | { | |
609 | struct cls_rule *rule; | |
610 | struct flow f; | |
611 | ||
612 | f = *flow; | |
613 | zero_wildcards(&f, &table->wc); | |
614 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0), | |
615 | &table->rules) { | |
616 | if (flow_equal(&f, &rule->flow)) { | |
617 | return rule; | |
064af421 BP |
618 | } |
619 | } | |
064af421 BP |
620 | return NULL; |
621 | } | |
622 | ||
623 | static struct cls_rule * | |
b5d97350 | 624 | find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash) |
064af421 | 625 | { |
b5d97350 | 626 | struct cls_rule *head; |
064af421 | 627 | |
b5d97350 BP |
628 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { |
629 | if (flow_equal(&head->flow, flow)) { | |
630 | return head; | |
064af421 BP |
631 | } |
632 | } | |
633 | return NULL; | |
634 | } | |
635 | ||
b5d97350 BP |
636 | static struct cls_rule * |
637 | insert_rule(struct cls_table *table, struct cls_rule *new) | |
064af421 | 638 | { |
b5d97350 | 639 | struct cls_rule *head; |
064af421 | 640 | |
b5d97350 | 641 | new->hmap_node.hash = flow_hash(&new->flow, 0); |
064af421 | 642 | |
b5d97350 BP |
643 | head = find_equal(table, &new->flow, new->hmap_node.hash); |
644 | if (!head) { | |
645 | hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); | |
646 | list_init(&new->list); | |
647 | return NULL; | |
648 | } else { | |
649 | /* Scan the list for the insertion point that will keep the list in | |
650 | * order of decreasing priority. */ | |
651 | struct cls_rule *rule; | |
652 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
653 | if (new->priority >= rule->priority) { | |
654 | if (rule == head) { | |
655 | /* 'new' is the new highest-priority flow in the list. */ | |
656 | hmap_replace(&table->rules, | |
657 | &rule->hmap_node, &new->hmap_node); | |
658 | } | |
064af421 | 659 | |
b5d97350 BP |
660 | if (new->priority == rule->priority) { |
661 | list_replace(&new->list, &rule->list); | |
662 | return rule; | |
663 | } else { | |
664 | list_insert(&rule->list, &new->list); | |
665 | return NULL; | |
666 | } | |
667 | } | |
668 | } | |
064af421 | 669 | |
b5d97350 BP |
670 | /* Insert 'new' at the end of the list. */ |
671 | list_push_back(&head->list, &new->list); | |
672 | return NULL; | |
064af421 | 673 | } |
064af421 BP |
674 | } |
675 | ||
b5d97350 BP |
676 | static struct cls_rule * |
677 | next_rule_in_list(struct cls_rule *rule) | |
064af421 | 678 | { |
b5d97350 BP |
679 | struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); |
680 | return next->priority < rule->priority ? next : NULL; | |
064af421 BP |
681 | } |
682 | ||
064af421 | 683 | static bool |
b5d97350 BP |
684 | flow_equal_except(const struct flow *a, const struct flow *b, |
685 | const struct flow_wildcards *wildcards) | |
064af421 | 686 | { |
b5d97350 | 687 | const uint32_t wc = wildcards->wildcards; |
49bdc010 | 688 | |
b5d97350 BP |
689 | BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37); |
690 | ||
691 | return ((wc & NXFW_TUN_ID || a->tun_id == b->tun_id) | |
692 | && !((a->nw_src ^ b->nw_src) & wildcards->nw_src_mask) | |
693 | && !((a->nw_dst ^ b->nw_dst) & wildcards->nw_dst_mask) | |
694 | && (wc & OFPFW_IN_PORT || a->in_port == b->in_port) | |
695 | && (wc & OFPFW_DL_VLAN || a->dl_vlan == b->dl_vlan) | |
696 | && (wc & OFPFW_DL_TYPE || a->dl_type == b->dl_type) | |
697 | && (wc & OFPFW_TP_SRC || a->tp_src == b->tp_src) | |
698 | && (wc & OFPFW_TP_DST || a->tp_dst == b->tp_dst) | |
699 | && (wc & OFPFW_DL_SRC || eth_addr_equals(a->dl_src, b->dl_src)) | |
700 | && (wc & OFPFW_DL_DST || eth_addr_equals(a->dl_dst, b->dl_dst)) | |
701 | && (wc & OFPFW_NW_PROTO || a->nw_proto == b->nw_proto) | |
702 | && (wc & OFPFW_DL_VLAN_PCP || a->dl_vlan_pcp == b->dl_vlan_pcp) | |
703 | && (wc & OFPFW_NW_TOS || a->nw_tos == b->nw_tos)); | |
064af421 BP |
704 | } |
705 | ||
b5d97350 BP |
706 | static void |
707 | zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards) | |
064af421 | 708 | { |
b5d97350 | 709 | const uint32_t wc = wildcards->wildcards; |
064af421 | 710 | |
b5d97350 | 711 | BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37); |
064af421 | 712 | |
b5d97350 BP |
713 | if (wc & NXFW_TUN_ID) { |
714 | flow->tun_id = 0; | |
064af421 | 715 | } |
b5d97350 BP |
716 | flow->nw_src &= wildcards->nw_src_mask; |
717 | flow->nw_dst &= wildcards->nw_dst_mask; | |
718 | if (wc & OFPFW_IN_PORT) { | |
719 | flow->in_port = 0; | |
064af421 | 720 | } |
b5d97350 BP |
721 | if (wc & OFPFW_DL_VLAN) { |
722 | flow->dl_vlan = 0; | |
064af421 | 723 | } |
b5d97350 BP |
724 | if (wc & OFPFW_DL_TYPE) { |
725 | flow->dl_type = 0; | |
726 | } | |
727 | if (wc & OFPFW_TP_SRC) { | |
728 | flow->tp_src = 0; | |
729 | } | |
730 | if (wc & OFPFW_TP_DST) { | |
731 | flow->tp_dst = 0; | |
732 | } | |
733 | if (wc & OFPFW_DL_SRC) { | |
734 | memset(flow->dl_src, 0, sizeof flow->dl_src); | |
735 | } | |
736 | if (wc & OFPFW_DL_DST) { | |
737 | memset(flow->dl_dst, 0, sizeof flow->dl_dst); | |
738 | } | |
739 | if (wc & OFPFW_NW_PROTO) { | |
740 | flow->nw_proto = 0; | |
741 | } | |
742 | if (wc & OFPFW_DL_VLAN_PCP) { | |
743 | flow->dl_vlan_pcp = 0; | |
744 | } | |
745 | if (wc & OFPFW_NW_TOS) { | |
746 | flow->nw_tos = 0; | |
064af421 | 747 | } |
064af421 | 748 | } |