]>
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> | |
844dff32 | 22 | #include "byte-order.h" |
68d1c8c3 | 23 | #include "dynamic-string.h" |
064af421 BP |
24 | #include "flow.h" |
25 | #include "hash.h" | |
d8ae4d67 | 26 | #include "ofp-util.h" |
b5d97350 | 27 | #include "packets.h" |
064af421 | 28 | |
b5d97350 BP |
29 | static struct cls_table *find_table(const struct classifier *, |
30 | const struct flow_wildcards *); | |
31 | static struct cls_table *insert_table(struct classifier *, | |
32 | const struct flow_wildcards *); | |
33 | ||
34 | static struct cls_table *classifier_first_table(const struct classifier *); | |
35 | static struct cls_table *classifier_next_table(const struct classifier *, | |
36 | const struct cls_table *); | |
37 | static void destroy_table(struct classifier *, struct cls_table *); | |
38 | ||
b5d97350 BP |
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 | ||
955f579d | 57 | static struct cls_rule *next_rule_in_list__(struct cls_rule *); |
b5d97350 BP |
58 | static struct cls_rule *next_rule_in_list(struct cls_rule *); |
59 | ||
60 | static struct cls_table * | |
61 | cls_table_from_hmap_node(const struct hmap_node *node) | |
62 | { | |
63 | return node ? CONTAINER_OF(node, struct cls_table, hmap_node) : NULL; | |
64 | } | |
65 | ||
b63f2ea7 BP |
66 | /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given |
67 | * 'wildcards' and 'priority'. */ | |
68 | void | |
69 | cls_rule_init(const struct flow *flow, const struct flow_wildcards *wildcards, | |
70 | unsigned int priority, struct cls_rule *rule) | |
b5d97350 BP |
71 | { |
72 | rule->flow = *flow; | |
b63f2ea7 BP |
73 | rule->wc = *wildcards; |
74 | rule->priority = priority; | |
52ce26ee | 75 | cls_rule_zero_wildcarded_fields(rule); |
b5d97350 | 76 | } |
064af421 | 77 | |
b63f2ea7 BP |
78 | /* Converts the flow in 'flow' into an exact-match cls_rule in 'rule', with the |
79 | * given 'priority'. (For OpenFlow 1.0, exact-match rule are always highest | |
80 | * priority, so 'priority' should be at least 65535.) */ | |
064af421 | 81 | void |
b63f2ea7 BP |
82 | cls_rule_init_exact(const struct flow *flow, |
83 | unsigned int priority, struct cls_rule *rule) | |
064af421 | 84 | { |
b63f2ea7 BP |
85 | rule->flow = *flow; |
86 | flow_wildcards_init_exact(&rule->wc); | |
064af421 | 87 | rule->priority = priority; |
064af421 BP |
88 | } |
89 | ||
844dff32 BP |
90 | /* Initializes 'rule' as a "catch-all" rule that matches every packet, with |
91 | * priority 'priority'. */ | |
92 | void | |
93 | cls_rule_init_catchall(struct cls_rule *rule, unsigned int priority) | |
94 | { | |
95 | memset(&rule->flow, 0, sizeof rule->flow); | |
d8ae4d67 | 96 | flow_wildcards_init_catchall(&rule->wc); |
844dff32 BP |
97 | rule->priority = priority; |
98 | } | |
99 | ||
b5d97350 BP |
100 | /* For each bit or field wildcarded in 'rule', sets the corresponding bit or |
101 | * field in 'flow' to all-0-bits. It is important to maintain this invariant | |
102 | * in a clr_rule that might be inserted into a classifier. | |
103 | * | |
104 | * It is never necessary to call this function directly for a cls_rule that is | |
105 | * initialized or modified only by cls_rule_*() functions. It is useful to | |
106 | * restore the invariant in a cls_rule whose 'wc' member is modified by hand. | |
107 | */ | |
108 | void | |
52ce26ee | 109 | cls_rule_zero_wildcarded_fields(struct cls_rule *rule) |
b5d97350 BP |
110 | { |
111 | zero_wildcards(&rule->flow, &rule->wc); | |
064af421 BP |
112 | } |
113 | ||
64420dfa BP |
114 | void |
115 | cls_rule_set_in_port(struct cls_rule *rule, uint16_t odp_port) | |
116 | { | |
d8ae4d67 | 117 | rule->wc.wildcards &= ~FWW_IN_PORT; |
64420dfa BP |
118 | rule->flow.in_port = odp_port; |
119 | } | |
120 | ||
121 | void | |
122 | cls_rule_set_dl_type(struct cls_rule *rule, ovs_be16 dl_type) | |
123 | { | |
d8ae4d67 | 124 | rule->wc.wildcards &= ~FWW_DL_TYPE; |
64420dfa BP |
125 | rule->flow.dl_type = dl_type; |
126 | } | |
127 | ||
128 | void | |
129 | cls_rule_set_dl_src(struct cls_rule *rule, const uint8_t dl_src[ETH_ADDR_LEN]) | |
130 | { | |
d8ae4d67 | 131 | rule->wc.wildcards &= ~FWW_DL_SRC; |
64420dfa BP |
132 | memcpy(rule->flow.dl_src, dl_src, ETH_ADDR_LEN); |
133 | } | |
134 | ||
135 | void | |
136 | cls_rule_set_dl_dst(struct cls_rule *rule, const uint8_t dl_dst[ETH_ADDR_LEN]) | |
137 | { | |
d8ae4d67 | 138 | rule->wc.wildcards &= ~(FWW_DL_DST | FWW_ETH_MCAST); |
64420dfa BP |
139 | memcpy(rule->flow.dl_dst, dl_dst, ETH_ADDR_LEN); |
140 | } | |
141 | ||
66642cb4 | 142 | void |
81c9dad2 BP |
143 | cls_rule_set_dl_tci(struct cls_rule *rule, ovs_be16 tci) |
144 | { | |
66642cb4 | 145 | cls_rule_set_dl_tci_masked(rule, tci, htons(0xffff)); |
81c9dad2 BP |
146 | } |
147 | ||
66642cb4 | 148 | void |
81c9dad2 BP |
149 | cls_rule_set_dl_tci_masked(struct cls_rule *rule, ovs_be16 tci, ovs_be16 mask) |
150 | { | |
66642cb4 BP |
151 | rule->flow.vlan_tci = tci & mask; |
152 | rule->wc.vlan_tci_mask = mask; | |
153 | } | |
81c9dad2 | 154 | |
66642cb4 BP |
155 | /* Modifies 'rule' so that the VLAN VID is wildcarded. If the PCP is already |
156 | * wildcarded, then 'rule' will match a packet regardless of whether it has an | |
157 | * 802.1Q header or not. */ | |
158 | void | |
159 | cls_rule_set_any_vid(struct cls_rule *rule) | |
160 | { | |
161 | if (rule->wc.vlan_tci_mask & htons(VLAN_PCP_MASK)) { | |
162 | rule->wc.vlan_tci_mask &= ~htons(VLAN_VID_MASK); | |
163 | rule->flow.vlan_tci &= ~htons(VLAN_VID_MASK); | |
164 | } else { | |
165 | cls_rule_set_dl_tci_masked(rule, htons(0), htons(0)); | |
81c9dad2 BP |
166 | } |
167 | } | |
168 | ||
66642cb4 BP |
169 | /* Modifies 'rule' depending on 'dl_vlan': |
170 | * | |
171 | * - If 'dl_vlan' is htons(OFP_VLAN_NONE), makes 'rule' match only packets | |
172 | * without an 802.1Q header. | |
173 | * | |
174 | * - Otherwise, makes 'rule' match only packets with an 802.1Q header whose | |
175 | * VID equals the low 12 bits of 'dl_vlan'. | |
176 | */ | |
81c9dad2 BP |
177 | void |
178 | cls_rule_set_dl_vlan(struct cls_rule *rule, ovs_be16 dl_vlan) | |
179 | { | |
66642cb4 BP |
180 | if (dl_vlan == htons(OFP_VLAN_NONE)) { |
181 | cls_rule_set_dl_tci(rule, htons(0)); | |
182 | } else { | |
81c9dad2 | 183 | dl_vlan &= htons(VLAN_VID_MASK); |
66642cb4 BP |
184 | rule->flow.vlan_tci &= ~htons(VLAN_VID_MASK); |
185 | rule->flow.vlan_tci |= htons(VLAN_CFI) | dl_vlan; | |
186 | rule->wc.vlan_tci_mask |= htons(VLAN_VID_MASK | VLAN_CFI); | |
81c9dad2 | 187 | } |
66642cb4 | 188 | } |
81c9dad2 | 189 | |
66642cb4 BP |
190 | /* Modifies 'rule' so that the VLAN PCP is wildcarded. If the VID is already |
191 | * wildcarded, then 'rule' will match a packet regardless of whether it has an | |
192 | * 802.1Q header or not. */ | |
193 | void | |
194 | cls_rule_set_any_pcp(struct cls_rule *rule) | |
195 | { | |
196 | if (rule->wc.vlan_tci_mask & htons(VLAN_VID_MASK)) { | |
197 | rule->wc.vlan_tci_mask &= ~htons(VLAN_PCP_MASK); | |
198 | rule->flow.vlan_tci &= ~htons(VLAN_PCP_MASK); | |
199 | } else { | |
200 | cls_rule_set_dl_tci_masked(rule, htons(0), htons(0)); | |
201 | } | |
81c9dad2 BP |
202 | } |
203 | ||
66642cb4 BP |
204 | /* Modifies 'rule' so that it matches only packets with an 802.1Q header whose |
205 | * PCP equals the low 3 bits of 'dl_vlan_pcp'. */ | |
81c9dad2 BP |
206 | void |
207 | cls_rule_set_dl_vlan_pcp(struct cls_rule *rule, uint8_t dl_vlan_pcp) | |
208 | { | |
66642cb4 BP |
209 | dl_vlan_pcp &= 0x07; |
210 | rule->flow.vlan_tci &= ~htons(VLAN_PCP_MASK); | |
211 | rule->flow.vlan_tci |= htons((dl_vlan_pcp << VLAN_PCP_SHIFT) | VLAN_CFI); | |
212 | rule->wc.vlan_tci_mask |= htons(VLAN_CFI | VLAN_PCP_MASK); | |
81c9dad2 BP |
213 | } |
214 | ||
64420dfa BP |
215 | void |
216 | cls_rule_set_tp_src(struct cls_rule *rule, ovs_be16 tp_src) | |
217 | { | |
d8ae4d67 | 218 | rule->wc.wildcards &= ~FWW_TP_SRC; |
64420dfa BP |
219 | rule->flow.tp_src = tp_src; |
220 | } | |
221 | ||
222 | void | |
223 | cls_rule_set_tp_dst(struct cls_rule *rule, ovs_be16 tp_dst) | |
224 | { | |
d8ae4d67 | 225 | rule->wc.wildcards &= ~FWW_TP_DST; |
64420dfa BP |
226 | rule->flow.tp_dst = tp_dst; |
227 | } | |
228 | ||
229 | void | |
230 | cls_rule_set_nw_proto(struct cls_rule *rule, uint8_t nw_proto) | |
231 | { | |
d8ae4d67 | 232 | rule->wc.wildcards &= ~FWW_NW_PROTO; |
64420dfa BP |
233 | rule->flow.nw_proto = nw_proto; |
234 | } | |
235 | ||
236 | void | |
237 | cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) | |
238 | { | |
81c9dad2 BP |
239 | cls_rule_set_nw_src_masked(rule, nw_src, htonl(UINT32_MAX)); |
240 | } | |
241 | ||
242 | bool | |
243 | cls_rule_set_nw_src_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) | |
244 | { | |
245 | if (flow_wildcards_set_nw_src_mask(&rule->wc, mask)) { | |
246 | rule->flow.nw_src = ip & mask; | |
247 | return true; | |
248 | } else { | |
249 | return false; | |
250 | } | |
64420dfa BP |
251 | } |
252 | ||
253 | void | |
254 | cls_rule_set_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) | |
255 | { | |
81c9dad2 BP |
256 | cls_rule_set_nw_dst_masked(rule, nw_dst, htonl(UINT32_MAX)); |
257 | } | |
258 | ||
259 | bool | |
260 | cls_rule_set_nw_dst_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) | |
261 | { | |
262 | if (flow_wildcards_set_nw_dst_mask(&rule->wc, mask)) { | |
263 | rule->flow.nw_dst = ip & mask; | |
264 | return true; | |
265 | } else { | |
266 | return false; | |
267 | } | |
268 | } | |
269 | ||
270 | void | |
271 | cls_rule_set_nw_tos(struct cls_rule *rule, uint8_t nw_tos) | |
272 | { | |
d8ae4d67 | 273 | rule->wc.wildcards &= ~FWW_NW_TOS; |
81c9dad2 BP |
274 | rule->flow.nw_tos = nw_tos & IP_DSCP_MASK; |
275 | } | |
276 | ||
277 | void | |
278 | cls_rule_set_icmp_type(struct cls_rule *rule, uint8_t icmp_type) | |
279 | { | |
d8ae4d67 | 280 | rule->wc.wildcards &= ~FWW_TP_SRC; |
81c9dad2 BP |
281 | rule->flow.icmp_type = htons(icmp_type); |
282 | ||
283 | } | |
284 | ||
285 | void | |
286 | cls_rule_set_icmp_code(struct cls_rule *rule, uint8_t icmp_code) | |
287 | { | |
d8ae4d67 | 288 | rule->wc.wildcards &= ~FWW_TP_DST; |
81c9dad2 | 289 | rule->flow.icmp_code = htons(icmp_code); |
64420dfa BP |
290 | } |
291 | ||
193eb874 BP |
292 | /* Returns true if 'a' and 'b' have the same priority, wildcard the same |
293 | * fields, and have the same values for fixed fields, otherwise false. */ | |
294 | bool | |
295 | cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) | |
296 | { | |
297 | return (a->priority == b->priority | |
298 | && flow_wildcards_equal(&a->wc, &b->wc) | |
299 | && flow_equal(&a->flow, &b->flow)); | |
300 | } | |
301 | ||
68d1c8c3 BP |
302 | /* Converts 'rule' to a string and returns the string. The caller must free |
303 | * the string (with free()). */ | |
304 | char * | |
305 | cls_rule_to_string(const struct cls_rule *rule) | |
306 | { | |
307 | struct ds s = DS_EMPTY_INITIALIZER; | |
308 | ds_put_format(&s, "wildcards=%x priority=%u ", | |
309 | rule->wc.wildcards, rule->priority); | |
310 | flow_format(&s, &rule->flow); | |
311 | return ds_cstr(&s); | |
312 | } | |
313 | ||
064af421 BP |
314 | /* Prints cls_rule 'rule', for debugging. |
315 | * | |
316 | * (The output could be improved and expanded, but this was good enough to | |
317 | * debug the classifier.) */ | |
318 | void | |
319 | cls_rule_print(const struct cls_rule *rule) | |
320 | { | |
321 | printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority); | |
322 | flow_print(stdout, &rule->flow); | |
323 | putc('\n', stdout); | |
324 | } | |
064af421 BP |
325 | \f |
326 | /* Initializes 'cls' as a classifier that initially contains no classification | |
327 | * rules. */ | |
328 | void | |
329 | classifier_init(struct classifier *cls) | |
330 | { | |
064af421 | 331 | cls->n_rules = 0; |
b5d97350 | 332 | hmap_init(&cls->tables); |
064af421 BP |
333 | } |
334 | ||
335 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
336 | * caller's responsibility. */ | |
337 | void | |
338 | classifier_destroy(struct classifier *cls) | |
339 | { | |
340 | if (cls) { | |
b5d97350 | 341 | struct cls_table *table, *next_table; |
064af421 | 342 | |
b5d97350 BP |
343 | HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { |
344 | hmap_destroy(&table->rules); | |
345 | hmap_remove(&cls->tables, &table->hmap_node); | |
346 | free(table); | |
064af421 | 347 | } |
b5d97350 | 348 | hmap_destroy(&cls->tables); |
064af421 BP |
349 | } |
350 | } | |
351 | ||
b5d97350 | 352 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
353 | bool |
354 | classifier_is_empty(const struct classifier *cls) | |
355 | { | |
356 | return cls->n_rules == 0; | |
357 | } | |
358 | ||
359 | /* Returns the number of rules in 'classifier'. */ | |
360 | int | |
361 | classifier_count(const struct classifier *cls) | |
362 | { | |
363 | return cls->n_rules; | |
364 | } | |
365 | ||
b5d97350 BP |
366 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
367 | * must not modify or free it. | |
064af421 BP |
368 | * |
369 | * If 'cls' already contains an identical rule (including wildcards, values of | |
370 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
371 | * rule that was replaced. The caller takes ownership of the returned rule and | |
372 | * is thus responsible for freeing it, etc., as necessary. | |
373 | * | |
374 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
375 | * inserting the new rule. In this case, no rules are displaced by the new | |
376 | * rule, even rules that cannot have any effect because the new rule matches a | |
377 | * superset of their flows and has higher priority. */ | |
378 | struct cls_rule * | |
379 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
380 | { | |
b5d97350 BP |
381 | struct cls_rule *old_rule; |
382 | struct cls_table *table; | |
383 | ||
384 | table = find_table(cls, &rule->wc); | |
385 | if (!table) { | |
386 | table = insert_table(cls, &rule->wc); | |
387 | } | |
388 | ||
389 | old_rule = insert_rule(table, rule); | |
390 | if (!old_rule) { | |
391 | table->n_table_rules++; | |
064af421 BP |
392 | cls->n_rules++; |
393 | } | |
b5d97350 | 394 | return old_rule; |
064af421 BP |
395 | } |
396 | ||
b5d97350 BP |
397 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to free |
398 | * 'rule', if this is desirable. */ | |
064af421 BP |
399 | void |
400 | classifier_remove(struct classifier *cls, struct cls_rule *rule) | |
401 | { | |
b5d97350 BP |
402 | struct cls_rule *head; |
403 | struct cls_table *table; | |
064af421 | 404 | |
b5d97350 BP |
405 | table = find_table(cls, &rule->wc); |
406 | head = find_equal(table, &rule->flow, rule->hmap_node.hash); | |
407 | if (head != rule) { | |
408 | list_remove(&rule->list); | |
409 | } else if (list_is_empty(&rule->list)) { | |
410 | hmap_remove(&table->rules, &rule->hmap_node); | |
411 | } else { | |
412 | struct cls_rule *next = CONTAINER_OF(rule->list.next, | |
413 | struct cls_rule, list); | |
064af421 | 414 | |
b5d97350 BP |
415 | list_remove(&rule->list); |
416 | hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); | |
417 | } | |
064af421 | 418 | |
f6acdb44 | 419 | if (--table->n_table_rules == 0) { |
b5d97350 | 420 | destroy_table(cls, table); |
064af421 | 421 | } |
b5d97350 BP |
422 | |
423 | cls->n_rules--; | |
064af421 BP |
424 | } |
425 | ||
48c3de13 BP |
426 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
427 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
3c4486a5 | 428 | * of equal priority match 'flow', returns one arbitrarily. */ |
48c3de13 | 429 | struct cls_rule * |
3c4486a5 | 430 | classifier_lookup(const struct classifier *cls, const struct flow *flow) |
48c3de13 | 431 | { |
b5d97350 BP |
432 | struct cls_table *table; |
433 | struct cls_rule *best; | |
48c3de13 | 434 | |
b5d97350 BP |
435 | best = NULL; |
436 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { | |
3c4486a5 BP |
437 | struct cls_rule *rule = find_match(table, flow); |
438 | if (rule && (!best || rule->priority > best->priority)) { | |
439 | best = rule; | |
b5d97350 | 440 | } |
48c3de13 | 441 | } |
b5d97350 | 442 | return best; |
48c3de13 BP |
443 | } |
444 | ||
b5d97350 BP |
445 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
446 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
447 | * contain an exact match. | |
448 | * | |
449 | * Priority is ignored for exact-match rules (because OpenFlow 1.0 always | |
450 | * treats exact-match rules as highest priority). */ | |
064af421 BP |
451 | struct cls_rule * |
452 | classifier_find_rule_exactly(const struct classifier *cls, | |
76ecc721 | 453 | const struct cls_rule *target) |
064af421 | 454 | { |
b5d97350 BP |
455 | struct cls_rule *head, *rule; |
456 | struct cls_table *table; | |
064af421 | 457 | |
b5d97350 BP |
458 | table = find_table(cls, &target->wc); |
459 | if (!table) { | |
460 | return NULL; | |
064af421 BP |
461 | } |
462 | ||
b5d97350 | 463 | head = find_equal(table, &target->flow, flow_hash(&target->flow, 0)); |
00561f41 | 464 | if (flow_wildcards_is_exact(&target->wc)) { |
b5d97350 BP |
465 | return head; |
466 | } | |
467 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
468 | if (target->priority >= rule->priority) { | |
469 | return target->priority == rule->priority ? rule : NULL; | |
064af421 BP |
470 | } |
471 | } | |
472 | return NULL; | |
473 | } | |
474 | ||
faa50f40 BP |
475 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
476 | * considered to overlap if both rules have the same priority and a packet | |
477 | * could match both. */ | |
49bdc010 JP |
478 | bool |
479 | classifier_rule_overlaps(const struct classifier *cls, | |
faa50f40 | 480 | const struct cls_rule *target) |
49bdc010 | 481 | { |
b5d97350 | 482 | struct cls_table *table; |
49bdc010 | 483 | |
b5d97350 BP |
484 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { |
485 | struct flow_wildcards wc; | |
486 | struct cls_rule *head; | |
49bdc010 | 487 | |
b5d97350 BP |
488 | flow_wildcards_combine(&wc, &target->wc, &table->wc); |
489 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { | |
49bdc010 JP |
490 | struct cls_rule *rule; |
491 | ||
b5d97350 | 492 | FOR_EACH_RULE_IN_LIST (rule, head) { |
faa50f40 | 493 | if (rule->priority == target->priority |
b5d97350 | 494 | && flow_equal_except(&target->flow, &rule->flow, &wc)) { |
49bdc010 JP |
495 | return true; |
496 | } | |
497 | } | |
498 | } | |
499 | } | |
500 | ||
501 | return false; | |
502 | } | |
b5d97350 | 503 | \f |
5ecc9d81 BP |
504 | /* Iteration. */ |
505 | ||
506 | static bool | |
507 | rule_matches(const struct cls_rule *rule, const struct cls_rule *target) | |
508 | { | |
509 | return (!target | |
510 | || flow_equal_except(&rule->flow, &target->flow, &target->wc)); | |
511 | } | |
512 | ||
513 | static struct cls_rule * | |
514 | search_table(const struct cls_table *table, const struct cls_rule *target) | |
515 | { | |
516 | if (!target || !flow_wildcards_has_extra(&table->wc, &target->wc)) { | |
517 | struct cls_rule *rule; | |
518 | ||
519 | HMAP_FOR_EACH (rule, hmap_node, &table->rules) { | |
520 | if (rule_matches(rule, target)) { | |
521 | return rule; | |
522 | } | |
523 | } | |
524 | } | |
525 | return NULL; | |
526 | } | |
527 | ||
528 | /* Initializes 'cursor' for iterating through 'cls' rules that exactly match | |
529 | * 'target' or are more specific than 'target'. That is, a given 'rule' | |
530 | * matches 'target' if, for every field: | |
531 | * | |
532 | * - 'target' and 'rule' specify the same (non-wildcarded) value for the | |
533 | * field, or | |
534 | * | |
535 | * - 'target' wildcards the field, | |
536 | * | |
537 | * but not if: | |
538 | * | |
539 | * - 'target' and 'rule' specify different values for the field, or | |
540 | * | |
541 | * - 'target' specifies a value for the field but 'rule' wildcards it. | |
542 | * | |
543 | * Equivalently, the truth table for whether a field matches is: | |
544 | * | |
545 | * rule | |
546 | * | |
547 | * wildcard exact | |
548 | * +---------+---------+ | |
549 | * t wild | yes | yes | | |
550 | * a card | | | | |
551 | * r +---------+---------+ | |
552 | * g exact | no |if values| | |
553 | * e | |are equal| | |
554 | * t +---------+---------+ | |
555 | * | |
556 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
557 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
558 | * | |
559 | * Ignores target->priority. | |
560 | * | |
561 | * 'target' may be NULL to iterate over every rule in 'cls'. */ | |
562 | void | |
563 | cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, | |
564 | const struct cls_rule *target) | |
565 | { | |
566 | cursor->cls = cls; | |
567 | cursor->target = target; | |
568 | } | |
569 | ||
570 | /* Returns the first matching cls_rule in 'cursor''s iteration, or a null | |
571 | * pointer if there are no matches. */ | |
572 | struct cls_rule * | |
573 | cls_cursor_first(struct cls_cursor *cursor) | |
574 | { | |
575 | struct cls_table *table; | |
576 | ||
577 | for (table = classifier_first_table(cursor->cls); table; | |
578 | table = classifier_next_table(cursor->cls, table)) { | |
579 | struct cls_rule *rule = search_table(table, cursor->target); | |
580 | if (rule) { | |
581 | cursor->table = table; | |
582 | return rule; | |
583 | } | |
584 | } | |
585 | ||
586 | return NULL; | |
587 | } | |
588 | ||
589 | /* Returns the next matching cls_rule in 'cursor''s iteration, or a null | |
590 | * pointer if there are no more matches. */ | |
591 | struct cls_rule * | |
592 | cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) | |
593 | { | |
594 | const struct cls_table *table; | |
595 | struct cls_rule *next; | |
596 | ||
955f579d BP |
597 | next = next_rule_in_list__(rule); |
598 | if (next->priority < rule->priority) { | |
5ecc9d81 BP |
599 | return next; |
600 | } | |
601 | ||
955f579d BP |
602 | /* 'next' is the head of the list, that is, the rule that is included in |
603 | * the table's hmap. (This is important when the classifier contains rules | |
604 | * that differ only in priority.) */ | |
605 | rule = next; | |
5ecc9d81 BP |
606 | HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { |
607 | if (rule_matches(rule, cursor->target)) { | |
608 | return rule; | |
609 | } | |
610 | } | |
611 | ||
612 | for (table = classifier_next_table(cursor->cls, cursor->table); table; | |
613 | table = classifier_next_table(cursor->cls, table)) { | |
614 | rule = search_table(table, cursor->target); | |
615 | if (rule) { | |
616 | cursor->table = table; | |
617 | return rule; | |
618 | } | |
619 | } | |
620 | ||
621 | return NULL; | |
622 | } | |
623 | \f | |
b5d97350 BP |
624 | static struct cls_table * |
625 | find_table(const struct classifier *cls, const struct flow_wildcards *wc) | |
626 | { | |
627 | struct cls_table *table; | |
064af421 | 628 | |
b5d97350 BP |
629 | HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc), |
630 | &cls->tables) { | |
631 | if (flow_wildcards_equal(wc, &table->wc)) { | |
632 | return table; | |
064af421 BP |
633 | } |
634 | } | |
b5d97350 | 635 | return NULL; |
064af421 | 636 | } |
064af421 | 637 | |
b5d97350 BP |
638 | static struct cls_table * |
639 | insert_table(struct classifier *cls, const struct flow_wildcards *wc) | |
640 | { | |
641 | struct cls_table *table; | |
064af421 | 642 | |
b5d97350 BP |
643 | table = xzalloc(sizeof *table); |
644 | hmap_init(&table->rules); | |
645 | table->wc = *wc; | |
646 | hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc)); | |
064af421 | 647 | |
b5d97350 | 648 | return table; |
064af421 BP |
649 | } |
650 | ||
b5d97350 BP |
651 | static struct cls_table * |
652 | classifier_first_table(const struct classifier *cls) | |
064af421 | 653 | { |
b5d97350 | 654 | return cls_table_from_hmap_node(hmap_first(&cls->tables)); |
064af421 BP |
655 | } |
656 | ||
b5d97350 BP |
657 | static struct cls_table * |
658 | classifier_next_table(const struct classifier *cls, | |
659 | const struct cls_table *table) | |
064af421 | 660 | { |
b5d97350 BP |
661 | return cls_table_from_hmap_node(hmap_next(&cls->tables, |
662 | &table->hmap_node)); | |
663 | } | |
064af421 | 664 | |
b5d97350 BP |
665 | static void |
666 | destroy_table(struct classifier *cls, struct cls_table *table) | |
667 | { | |
668 | hmap_remove(&cls->tables, &table->hmap_node); | |
669 | hmap_destroy(&table->rules); | |
670 | free(table); | |
671 | } | |
064af421 | 672 | |
064af421 | 673 | static struct cls_rule * |
b5d97350 BP |
674 | find_match(const struct cls_table *table, const struct flow *flow) |
675 | { | |
676 | struct cls_rule *rule; | |
677 | struct flow f; | |
678 | ||
679 | f = *flow; | |
680 | zero_wildcards(&f, &table->wc); | |
681 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0), | |
682 | &table->rules) { | |
683 | if (flow_equal(&f, &rule->flow)) { | |
684 | return rule; | |
064af421 BP |
685 | } |
686 | } | |
064af421 BP |
687 | return NULL; |
688 | } | |
689 | ||
690 | static struct cls_rule * | |
b5d97350 | 691 | find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash) |
064af421 | 692 | { |
b5d97350 | 693 | struct cls_rule *head; |
064af421 | 694 | |
b5d97350 BP |
695 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { |
696 | if (flow_equal(&head->flow, flow)) { | |
697 | return head; | |
064af421 BP |
698 | } |
699 | } | |
700 | return NULL; | |
701 | } | |
702 | ||
b5d97350 BP |
703 | static struct cls_rule * |
704 | insert_rule(struct cls_table *table, struct cls_rule *new) | |
064af421 | 705 | { |
b5d97350 | 706 | struct cls_rule *head; |
064af421 | 707 | |
b5d97350 | 708 | new->hmap_node.hash = flow_hash(&new->flow, 0); |
064af421 | 709 | |
b5d97350 BP |
710 | head = find_equal(table, &new->flow, new->hmap_node.hash); |
711 | if (!head) { | |
712 | hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); | |
713 | list_init(&new->list); | |
714 | return NULL; | |
715 | } else { | |
716 | /* Scan the list for the insertion point that will keep the list in | |
717 | * order of decreasing priority. */ | |
718 | struct cls_rule *rule; | |
719 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
720 | if (new->priority >= rule->priority) { | |
721 | if (rule == head) { | |
722 | /* 'new' is the new highest-priority flow in the list. */ | |
723 | hmap_replace(&table->rules, | |
724 | &rule->hmap_node, &new->hmap_node); | |
725 | } | |
064af421 | 726 | |
b5d97350 BP |
727 | if (new->priority == rule->priority) { |
728 | list_replace(&new->list, &rule->list); | |
729 | return rule; | |
730 | } else { | |
731 | list_insert(&rule->list, &new->list); | |
732 | return NULL; | |
733 | } | |
734 | } | |
735 | } | |
064af421 | 736 | |
b5d97350 BP |
737 | /* Insert 'new' at the end of the list. */ |
738 | list_push_back(&head->list, &new->list); | |
739 | return NULL; | |
064af421 | 740 | } |
064af421 BP |
741 | } |
742 | ||
b5d97350 | 743 | static struct cls_rule * |
955f579d | 744 | next_rule_in_list__(struct cls_rule *rule) |
064af421 | 745 | { |
b5d97350 | 746 | struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); |
955f579d BP |
747 | return next; |
748 | } | |
749 | ||
750 | static struct cls_rule * | |
751 | next_rule_in_list(struct cls_rule *rule) | |
752 | { | |
753 | struct cls_rule *next = next_rule_in_list__(rule); | |
b5d97350 | 754 | return next->priority < rule->priority ? next : NULL; |
064af421 BP |
755 | } |
756 | ||
064af421 | 757 | static bool |
b5d97350 BP |
758 | flow_equal_except(const struct flow *a, const struct flow *b, |
759 | const struct flow_wildcards *wildcards) | |
064af421 | 760 | { |
d8ae4d67 | 761 | const flow_wildcards_t wc = wildcards->wildcards; |
b6c9e612 | 762 | int i; |
49bdc010 | 763 | |
66642cb4 | 764 | BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 36 + FLOW_N_REGS * 4); |
b6c9e612 BP |
765 | |
766 | for (i = 0; i < FLOW_N_REGS; i++) { | |
767 | if ((a->regs[i] ^ b->regs[i]) & wildcards->reg_masks[i]) { | |
768 | return false; | |
769 | } | |
770 | } | |
b5d97350 | 771 | |
d8ae4d67 | 772 | return ((wc & FWW_TUN_ID || a->tun_id == b->tun_id) |
b5d97350 BP |
773 | && !((a->nw_src ^ b->nw_src) & wildcards->nw_src_mask) |
774 | && !((a->nw_dst ^ b->nw_dst) & wildcards->nw_dst_mask) | |
d8ae4d67 | 775 | && (wc & FWW_IN_PORT || a->in_port == b->in_port) |
66642cb4 | 776 | && !((a->vlan_tci ^ b->vlan_tci) & wildcards->vlan_tci_mask) |
d8ae4d67 BP |
777 | && (wc & FWW_DL_TYPE || a->dl_type == b->dl_type) |
778 | && (wc & FWW_TP_SRC || a->tp_src == b->tp_src) | |
779 | && (wc & FWW_TP_DST || a->tp_dst == b->tp_dst) | |
780 | && (wc & FWW_DL_SRC || eth_addr_equals(a->dl_src, b->dl_src)) | |
781 | && (wc & FWW_DL_DST | |
1e37a2d7 BP |
782 | || (!((a->dl_dst[0] ^ b->dl_dst[0]) & 0xfe) |
783 | && a->dl_dst[1] == b->dl_dst[1] | |
784 | && a->dl_dst[2] == b->dl_dst[2] | |
785 | && a->dl_dst[3] == b->dl_dst[3] | |
786 | && a->dl_dst[4] == b->dl_dst[4] | |
787 | && a->dl_dst[5] == b->dl_dst[5])) | |
d8ae4d67 BP |
788 | && (wc & FWW_ETH_MCAST |
789 | || !((a->dl_dst[0] ^ b->dl_dst[0]) & 0x01)) | |
790 | && (wc & FWW_NW_PROTO || a->nw_proto == b->nw_proto) | |
d8ae4d67 | 791 | && (wc & FWW_NW_TOS || a->nw_tos == b->nw_tos)); |
064af421 BP |
792 | } |
793 | ||
b5d97350 BP |
794 | static void |
795 | zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards) | |
064af421 | 796 | { |
d8ae4d67 | 797 | const flow_wildcards_t wc = wildcards->wildcards; |
b6c9e612 | 798 | int i; |
064af421 | 799 | |
66642cb4 | 800 | BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 36 + 4 * FLOW_N_REGS); |
064af421 | 801 | |
b6c9e612 BP |
802 | for (i = 0; i < FLOW_N_REGS; i++) { |
803 | flow->regs[i] &= wildcards->reg_masks[i]; | |
804 | } | |
d8ae4d67 | 805 | if (wc & FWW_TUN_ID) { |
b5d97350 | 806 | flow->tun_id = 0; |
064af421 | 807 | } |
b5d97350 BP |
808 | flow->nw_src &= wildcards->nw_src_mask; |
809 | flow->nw_dst &= wildcards->nw_dst_mask; | |
d8ae4d67 | 810 | if (wc & FWW_IN_PORT) { |
b5d97350 | 811 | flow->in_port = 0; |
064af421 | 812 | } |
66642cb4 | 813 | flow->vlan_tci &= wildcards->vlan_tci_mask; |
d8ae4d67 | 814 | if (wc & FWW_DL_TYPE) { |
b5d97350 BP |
815 | flow->dl_type = 0; |
816 | } | |
d8ae4d67 | 817 | if (wc & FWW_TP_SRC) { |
b5d97350 BP |
818 | flow->tp_src = 0; |
819 | } | |
d8ae4d67 | 820 | if (wc & FWW_TP_DST) { |
b5d97350 BP |
821 | flow->tp_dst = 0; |
822 | } | |
d8ae4d67 | 823 | if (wc & FWW_DL_SRC) { |
b5d97350 BP |
824 | memset(flow->dl_src, 0, sizeof flow->dl_src); |
825 | } | |
d8ae4d67 | 826 | if (wc & FWW_DL_DST) { |
1e37a2d7 BP |
827 | flow->dl_dst[0] &= 0x01; |
828 | memset(&flow->dl_dst[1], 0, 5); | |
829 | } | |
830 | if (wc & FWW_ETH_MCAST) { | |
831 | flow->dl_dst[0] &= 0xfe; | |
b5d97350 | 832 | } |
d8ae4d67 | 833 | if (wc & FWW_NW_PROTO) { |
b5d97350 BP |
834 | flow->nw_proto = 0; |
835 | } | |
d8ae4d67 | 836 | if (wc & FWW_NW_TOS) { |
b5d97350 | 837 | flow->nw_tos = 0; |
064af421 | 838 | } |
064af421 | 839 | } |