]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
73f33563 | 2 | * Copyright (c) 2009, 2010, 2011, 2012 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" | |
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 | ||
43 | static bool flow_equal_except(const struct flow *, const struct flow *, | |
44 | const struct flow_wildcards *); | |
b5d97350 BP |
45 | |
46 | /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ | |
47 | #define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ | |
48 | for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) | |
49 | #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ | |
50 | for ((RULE) = (HEAD); \ | |
51 | (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ | |
52 | (RULE) = (NEXT)) | |
53 | ||
955f579d | 54 | static struct cls_rule *next_rule_in_list__(struct cls_rule *); |
b5d97350 BP |
55 | static struct cls_rule *next_rule_in_list(struct cls_rule *); |
56 | ||
b63f2ea7 BP |
57 | /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given |
58 | * 'wildcards' and 'priority'. */ | |
59 | void | |
60 | cls_rule_init(const struct flow *flow, const struct flow_wildcards *wildcards, | |
61 | unsigned int priority, struct cls_rule *rule) | |
b5d97350 BP |
62 | { |
63 | rule->flow = *flow; | |
b63f2ea7 BP |
64 | rule->wc = *wildcards; |
65 | rule->priority = priority; | |
52ce26ee | 66 | cls_rule_zero_wildcarded_fields(rule); |
b5d97350 | 67 | } |
064af421 | 68 | |
b63f2ea7 BP |
69 | /* Converts the flow in 'flow' into an exact-match cls_rule in 'rule', with the |
70 | * given 'priority'. (For OpenFlow 1.0, exact-match rule are always highest | |
71 | * priority, so 'priority' should be at least 65535.) */ | |
064af421 | 72 | void |
b63f2ea7 BP |
73 | cls_rule_init_exact(const struct flow *flow, |
74 | unsigned int priority, struct cls_rule *rule) | |
064af421 | 75 | { |
b63f2ea7 | 76 | rule->flow = *flow; |
deedf7e7 | 77 | rule->flow.skb_priority = 0; |
b63f2ea7 | 78 | flow_wildcards_init_exact(&rule->wc); |
064af421 | 79 | rule->priority = priority; |
064af421 BP |
80 | } |
81 | ||
844dff32 BP |
82 | /* Initializes 'rule' as a "catch-all" rule that matches every packet, with |
83 | * priority 'priority'. */ | |
84 | void | |
85 | cls_rule_init_catchall(struct cls_rule *rule, unsigned int priority) | |
86 | { | |
87 | memset(&rule->flow, 0, sizeof rule->flow); | |
d8ae4d67 | 88 | flow_wildcards_init_catchall(&rule->wc); |
844dff32 BP |
89 | rule->priority = priority; |
90 | } | |
91 | ||
b5d97350 BP |
92 | /* For each bit or field wildcarded in 'rule', sets the corresponding bit or |
93 | * field in 'flow' to all-0-bits. It is important to maintain this invariant | |
94 | * in a clr_rule that might be inserted into a classifier. | |
95 | * | |
96 | * It is never necessary to call this function directly for a cls_rule that is | |
97 | * initialized or modified only by cls_rule_*() functions. It is useful to | |
98 | * restore the invariant in a cls_rule whose 'wc' member is modified by hand. | |
99 | */ | |
100 | void | |
52ce26ee | 101 | cls_rule_zero_wildcarded_fields(struct cls_rule *rule) |
b5d97350 | 102 | { |
993410fb | 103 | flow_zero_wildcards(&rule->flow, &rule->wc); |
064af421 BP |
104 | } |
105 | ||
87542e21 BP |
106 | void |
107 | cls_rule_set_reg(struct cls_rule *rule, unsigned int reg_idx, uint32_t value) | |
108 | { | |
109 | cls_rule_set_reg_masked(rule, reg_idx, value, UINT32_MAX); | |
110 | } | |
111 | ||
112 | void | |
113 | cls_rule_set_reg_masked(struct cls_rule *rule, unsigned int reg_idx, | |
114 | uint32_t value, uint32_t mask) | |
115 | { | |
116 | assert(reg_idx < FLOW_N_REGS); | |
117 | flow_wildcards_set_reg_mask(&rule->wc, reg_idx, mask); | |
118 | rule->flow.regs[reg_idx] = value & mask; | |
119 | } | |
120 | ||
121 | void | |
b9298d3f | 122 | cls_rule_set_tun_id(struct cls_rule *rule, ovs_be64 tun_id) |
87542e21 | 123 | { |
8368c090 BP |
124 | cls_rule_set_tun_id_masked(rule, tun_id, htonll(UINT64_MAX)); |
125 | } | |
126 | ||
127 | void | |
128 | cls_rule_set_tun_id_masked(struct cls_rule *rule, | |
129 | ovs_be64 tun_id, ovs_be64 mask) | |
130 | { | |
131 | rule->wc.tun_id_mask = mask; | |
132 | rule->flow.tun_id = tun_id & mask; | |
87542e21 BP |
133 | } |
134 | ||
64420dfa | 135 | void |
abe529af | 136 | cls_rule_set_in_port(struct cls_rule *rule, uint16_t ofp_port) |
64420dfa | 137 | { |
d8ae4d67 | 138 | rule->wc.wildcards &= ~FWW_IN_PORT; |
abe529af | 139 | rule->flow.in_port = ofp_port; |
64420dfa BP |
140 | } |
141 | ||
142 | void | |
143 | cls_rule_set_dl_type(struct cls_rule *rule, ovs_be16 dl_type) | |
144 | { | |
d8ae4d67 | 145 | rule->wc.wildcards &= ~FWW_DL_TYPE; |
64420dfa BP |
146 | rule->flow.dl_type = dl_type; |
147 | } | |
148 | ||
149 | void | |
150 | cls_rule_set_dl_src(struct cls_rule *rule, const uint8_t dl_src[ETH_ADDR_LEN]) | |
151 | { | |
d8ae4d67 | 152 | rule->wc.wildcards &= ~FWW_DL_SRC; |
64420dfa BP |
153 | memcpy(rule->flow.dl_src, dl_src, ETH_ADDR_LEN); |
154 | } | |
155 | ||
db7f8281 | 156 | /* Modifies 'rule' so that the Ethernet address must match 'dl_dst' exactly. */ |
64420dfa BP |
157 | void |
158 | cls_rule_set_dl_dst(struct cls_rule *rule, const uint8_t dl_dst[ETH_ADDR_LEN]) | |
159 | { | |
d8ae4d67 | 160 | rule->wc.wildcards &= ~(FWW_DL_DST | FWW_ETH_MCAST); |
64420dfa BP |
161 | memcpy(rule->flow.dl_dst, dl_dst, ETH_ADDR_LEN); |
162 | } | |
163 | ||
db7f8281 BP |
164 | /* Modifies 'rule' so that the Ethernet address must match 'dl_dst' after each |
165 | * byte is ANDed with the appropriate byte in 'mask'. | |
166 | * | |
167 | * This function will assert-fail if 'mask' is invalid. Only 'mask' values | |
168 | * accepted by flow_wildcards_is_dl_dst_mask_valid() are allowed. */ | |
169 | void | |
170 | cls_rule_set_dl_dst_masked(struct cls_rule *rule, | |
171 | const uint8_t dl_dst[ETH_ADDR_LEN], | |
172 | const uint8_t mask[ETH_ADDR_LEN]) | |
173 | { | |
174 | flow_wildcards_t *wc = &rule->wc.wildcards; | |
175 | size_t i; | |
176 | ||
177 | *wc = flow_wildcards_set_dl_dst_mask(*wc, mask); | |
178 | for (i = 0; i < ETH_ADDR_LEN; i++) { | |
179 | rule->flow.dl_dst[i] = dl_dst[i] & mask[i]; | |
180 | } | |
181 | } | |
182 | ||
66642cb4 | 183 | void |
81c9dad2 BP |
184 | cls_rule_set_dl_tci(struct cls_rule *rule, ovs_be16 tci) |
185 | { | |
66642cb4 | 186 | cls_rule_set_dl_tci_masked(rule, tci, htons(0xffff)); |
81c9dad2 BP |
187 | } |
188 | ||
66642cb4 | 189 | void |
81c9dad2 BP |
190 | cls_rule_set_dl_tci_masked(struct cls_rule *rule, ovs_be16 tci, ovs_be16 mask) |
191 | { | |
66642cb4 BP |
192 | rule->flow.vlan_tci = tci & mask; |
193 | rule->wc.vlan_tci_mask = mask; | |
194 | } | |
81c9dad2 | 195 | |
66642cb4 BP |
196 | /* Modifies 'rule' so that the VLAN VID is wildcarded. If the PCP is already |
197 | * wildcarded, then 'rule' will match a packet regardless of whether it has an | |
198 | * 802.1Q header or not. */ | |
199 | void | |
200 | cls_rule_set_any_vid(struct cls_rule *rule) | |
201 | { | |
202 | if (rule->wc.vlan_tci_mask & htons(VLAN_PCP_MASK)) { | |
203 | rule->wc.vlan_tci_mask &= ~htons(VLAN_VID_MASK); | |
204 | rule->flow.vlan_tci &= ~htons(VLAN_VID_MASK); | |
205 | } else { | |
206 | cls_rule_set_dl_tci_masked(rule, htons(0), htons(0)); | |
81c9dad2 BP |
207 | } |
208 | } | |
209 | ||
66642cb4 BP |
210 | /* Modifies 'rule' depending on 'dl_vlan': |
211 | * | |
212 | * - If 'dl_vlan' is htons(OFP_VLAN_NONE), makes 'rule' match only packets | |
213 | * without an 802.1Q header. | |
214 | * | |
215 | * - Otherwise, makes 'rule' match only packets with an 802.1Q header whose | |
216 | * VID equals the low 12 bits of 'dl_vlan'. | |
217 | */ | |
81c9dad2 BP |
218 | void |
219 | cls_rule_set_dl_vlan(struct cls_rule *rule, ovs_be16 dl_vlan) | |
220 | { | |
28da1f8f | 221 | flow_set_vlan_vid(&rule->flow, dl_vlan); |
66642cb4 | 222 | if (dl_vlan == htons(OFP_VLAN_NONE)) { |
28da1f8f | 223 | rule->wc.vlan_tci_mask = htons(UINT16_MAX); |
66642cb4 | 224 | } else { |
66642cb4 | 225 | rule->wc.vlan_tci_mask |= htons(VLAN_VID_MASK | VLAN_CFI); |
81c9dad2 | 226 | } |
66642cb4 | 227 | } |
81c9dad2 | 228 | |
66642cb4 BP |
229 | /* Modifies 'rule' so that the VLAN PCP is wildcarded. If the VID is already |
230 | * wildcarded, then 'rule' will match a packet regardless of whether it has an | |
231 | * 802.1Q header or not. */ | |
232 | void | |
233 | cls_rule_set_any_pcp(struct cls_rule *rule) | |
234 | { | |
235 | if (rule->wc.vlan_tci_mask & htons(VLAN_VID_MASK)) { | |
236 | rule->wc.vlan_tci_mask &= ~htons(VLAN_PCP_MASK); | |
237 | rule->flow.vlan_tci &= ~htons(VLAN_PCP_MASK); | |
238 | } else { | |
239 | cls_rule_set_dl_tci_masked(rule, htons(0), htons(0)); | |
240 | } | |
81c9dad2 BP |
241 | } |
242 | ||
66642cb4 BP |
243 | /* Modifies 'rule' so that it matches only packets with an 802.1Q header whose |
244 | * PCP equals the low 3 bits of 'dl_vlan_pcp'. */ | |
81c9dad2 BP |
245 | void |
246 | cls_rule_set_dl_vlan_pcp(struct cls_rule *rule, uint8_t dl_vlan_pcp) | |
247 | { | |
28da1f8f | 248 | flow_set_vlan_pcp(&rule->flow, dl_vlan_pcp); |
66642cb4 | 249 | rule->wc.vlan_tci_mask |= htons(VLAN_CFI | VLAN_PCP_MASK); |
81c9dad2 BP |
250 | } |
251 | ||
64420dfa BP |
252 | void |
253 | cls_rule_set_tp_src(struct cls_rule *rule, ovs_be16 tp_src) | |
254 | { | |
73f33563 BP |
255 | cls_rule_set_tp_src_masked(rule, tp_src, htons(UINT16_MAX)); |
256 | } | |
257 | ||
258 | void | |
259 | cls_rule_set_tp_src_masked(struct cls_rule *rule, ovs_be16 port, ovs_be16 mask) | |
260 | { | |
261 | rule->flow.tp_src = port & mask; | |
262 | rule->wc.tp_src_mask = mask; | |
64420dfa BP |
263 | } |
264 | ||
265 | void | |
266 | cls_rule_set_tp_dst(struct cls_rule *rule, ovs_be16 tp_dst) | |
267 | { | |
73f33563 BP |
268 | cls_rule_set_tp_dst_masked(rule, tp_dst, htons(UINT16_MAX)); |
269 | } | |
270 | ||
271 | void | |
272 | cls_rule_set_tp_dst_masked(struct cls_rule *rule, ovs_be16 port, ovs_be16 mask) | |
273 | { | |
274 | rule->flow.tp_dst = port & mask; | |
275 | rule->wc.tp_dst_mask = mask; | |
64420dfa BP |
276 | } |
277 | ||
278 | void | |
279 | cls_rule_set_nw_proto(struct cls_rule *rule, uint8_t nw_proto) | |
280 | { | |
d8ae4d67 | 281 | rule->wc.wildcards &= ~FWW_NW_PROTO; |
64420dfa BP |
282 | rule->flow.nw_proto = nw_proto; |
283 | } | |
284 | ||
285 | void | |
286 | cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) | |
287 | { | |
209c0b17 JP |
288 | rule->flow.nw_src = nw_src; |
289 | rule->wc.nw_src_mask = htonl(UINT32_MAX); | |
81c9dad2 BP |
290 | } |
291 | ||
209c0b17 JP |
292 | void |
293 | cls_rule_set_nw_src_masked(struct cls_rule *rule, | |
294 | ovs_be32 nw_src, ovs_be32 mask) | |
81c9dad2 | 295 | { |
209c0b17 JP |
296 | rule->flow.nw_src = nw_src & mask; |
297 | rule->wc.nw_src_mask = mask; | |
64420dfa BP |
298 | } |
299 | ||
300 | void | |
301 | cls_rule_set_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) | |
302 | { | |
209c0b17 JP |
303 | rule->flow.nw_dst = nw_dst; |
304 | rule->wc.nw_dst_mask = htonl(UINT32_MAX); | |
81c9dad2 BP |
305 | } |
306 | ||
209c0b17 | 307 | void |
81c9dad2 BP |
308 | cls_rule_set_nw_dst_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) |
309 | { | |
209c0b17 JP |
310 | rule->flow.nw_dst = ip & mask; |
311 | rule->wc.nw_dst_mask = mask; | |
81c9dad2 BP |
312 | } |
313 | ||
314 | void | |
530180fd | 315 | cls_rule_set_nw_dscp(struct cls_rule *rule, uint8_t nw_dscp) |
81c9dad2 | 316 | { |
2486e66a | 317 | rule->wc.wildcards &= ~FWW_NW_DSCP; |
eadef313 JP |
318 | rule->flow.nw_tos &= ~IP_DSCP_MASK; |
319 | rule->flow.nw_tos |= nw_dscp & IP_DSCP_MASK; | |
530180fd JP |
320 | } |
321 | ||
322 | void | |
323 | cls_rule_set_nw_ecn(struct cls_rule *rule, uint8_t nw_ecn) | |
324 | { | |
2486e66a | 325 | rule->wc.wildcards &= ~FWW_NW_ECN; |
eadef313 JP |
326 | rule->flow.nw_tos &= ~IP_ECN_MASK; |
327 | rule->flow.nw_tos |= nw_ecn & IP_ECN_MASK; | |
7257b535 BP |
328 | } |
329 | ||
a61680c6 JP |
330 | void |
331 | cls_rule_set_nw_ttl(struct cls_rule *rule, uint8_t nw_ttl) | |
332 | { | |
333 | rule->wc.wildcards &= ~FWW_NW_TTL; | |
334 | rule->flow.nw_ttl = nw_ttl; | |
335 | } | |
336 | ||
7257b535 | 337 | void |
eadef313 | 338 | cls_rule_set_nw_frag(struct cls_rule *rule, uint8_t nw_frag) |
7257b535 | 339 | { |
eadef313 JP |
340 | rule->wc.nw_frag_mask |= FLOW_NW_FRAG_MASK; |
341 | rule->flow.nw_frag = nw_frag; | |
7257b535 BP |
342 | } |
343 | ||
344 | void | |
eadef313 JP |
345 | cls_rule_set_nw_frag_masked(struct cls_rule *rule, |
346 | uint8_t nw_frag, uint8_t mask) | |
7257b535 | 347 | { |
eadef313 JP |
348 | rule->flow.nw_frag = nw_frag & mask; |
349 | rule->wc.nw_frag_mask = mask; | |
81c9dad2 BP |
350 | } |
351 | ||
352 | void | |
353 | cls_rule_set_icmp_type(struct cls_rule *rule, uint8_t icmp_type) | |
354 | { | |
73f33563 | 355 | cls_rule_set_tp_src(rule, htons(icmp_type)); |
81c9dad2 BP |
356 | } |
357 | ||
358 | void | |
359 | cls_rule_set_icmp_code(struct cls_rule *rule, uint8_t icmp_code) | |
360 | { | |
73f33563 | 361 | cls_rule_set_tp_dst(rule, htons(icmp_code)); |
64420dfa BP |
362 | } |
363 | ||
bad68a99 JP |
364 | void |
365 | cls_rule_set_arp_sha(struct cls_rule *rule, const uint8_t sha[ETH_ADDR_LEN]) | |
366 | { | |
367 | rule->wc.wildcards &= ~FWW_ARP_SHA; | |
368 | memcpy(rule->flow.arp_sha, sha, ETH_ADDR_LEN); | |
369 | } | |
370 | ||
371 | void | |
372 | cls_rule_set_arp_tha(struct cls_rule *rule, const uint8_t tha[ETH_ADDR_LEN]) | |
373 | { | |
374 | rule->wc.wildcards &= ~FWW_ARP_THA; | |
375 | memcpy(rule->flow.arp_tha, tha, ETH_ADDR_LEN); | |
376 | } | |
377 | ||
d31f1109 JP |
378 | void |
379 | cls_rule_set_ipv6_src(struct cls_rule *rule, const struct in6_addr *src) | |
380 | { | |
209c0b17 JP |
381 | rule->flow.ipv6_src = *src; |
382 | rule->wc.ipv6_src_mask = in6addr_exact; | |
d31f1109 JP |
383 | } |
384 | ||
209c0b17 | 385 | void |
d31f1109 JP |
386 | cls_rule_set_ipv6_src_masked(struct cls_rule *rule, const struct in6_addr *src, |
387 | const struct in6_addr *mask) | |
388 | { | |
209c0b17 JP |
389 | rule->flow.ipv6_src = ipv6_addr_bitand(src, mask); |
390 | rule->wc.ipv6_src_mask = *mask; | |
d31f1109 JP |
391 | } |
392 | ||
393 | void | |
394 | cls_rule_set_ipv6_dst(struct cls_rule *rule, const struct in6_addr *dst) | |
395 | { | |
209c0b17 JP |
396 | rule->flow.ipv6_dst = *dst; |
397 | rule->wc.ipv6_dst_mask = in6addr_exact; | |
d31f1109 JP |
398 | } |
399 | ||
209c0b17 | 400 | void |
d31f1109 JP |
401 | cls_rule_set_ipv6_dst_masked(struct cls_rule *rule, const struct in6_addr *dst, |
402 | const struct in6_addr *mask) | |
403 | { | |
209c0b17 JP |
404 | rule->flow.ipv6_dst = ipv6_addr_bitand(dst, mask); |
405 | rule->wc.ipv6_dst_mask = *mask; | |
d31f1109 JP |
406 | } |
407 | ||
fa8223b7 JP |
408 | void |
409 | cls_rule_set_ipv6_label(struct cls_rule *rule, ovs_be32 ipv6_label) | |
410 | { | |
411 | rule->wc.wildcards &= ~FWW_IPV6_LABEL; | |
412 | rule->flow.ipv6_label = ipv6_label; | |
413 | } | |
414 | ||
685a51a5 | 415 | void |
e7ed3a3a | 416 | cls_rule_set_nd_target(struct cls_rule *rule, const struct in6_addr *target) |
685a51a5 JP |
417 | { |
418 | rule->wc.wildcards &= ~FWW_ND_TARGET; | |
e7ed3a3a | 419 | rule->flow.nd_target = *target; |
685a51a5 JP |
420 | } |
421 | ||
193eb874 BP |
422 | /* Returns true if 'a' and 'b' have the same priority, wildcard the same |
423 | * fields, and have the same values for fixed fields, otherwise false. */ | |
424 | bool | |
425 | cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) | |
426 | { | |
427 | return (a->priority == b->priority | |
428 | && flow_wildcards_equal(&a->wc, &b->wc) | |
429 | && flow_equal(&a->flow, &b->flow)); | |
430 | } | |
431 | ||
57452fdc BP |
432 | /* Returns a hash value for the flow, wildcards, and priority in 'rule', |
433 | * starting from 'basis'. */ | |
434 | uint32_t | |
435 | cls_rule_hash(const struct cls_rule *rule, uint32_t basis) | |
436 | { | |
437 | uint32_t h0 = flow_hash(&rule->flow, basis); | |
438 | uint32_t h1 = flow_wildcards_hash(&rule->wc, h0); | |
439 | return hash_int(rule->priority, h1); | |
440 | } | |
441 | ||
07b37e8f BP |
442 | static void |
443 | format_ip_netmask(struct ds *s, const char *name, ovs_be32 ip, | |
444 | ovs_be32 netmask) | |
445 | { | |
446 | if (netmask) { | |
aad29cd1 BP |
447 | ds_put_format(s, "%s=", name); |
448 | ip_format_masked(ip, netmask, s); | |
07b37e8f BP |
449 | ds_put_char(s, ','); |
450 | } | |
451 | } | |
452 | ||
d31f1109 JP |
453 | static void |
454 | format_ipv6_netmask(struct ds *s, const char *name, | |
455 | const struct in6_addr *addr, | |
456 | const struct in6_addr *netmask) | |
457 | { | |
458 | if (!ipv6_mask_is_any(netmask)) { | |
459 | ds_put_format(s, "%s=", name); | |
aad29cd1 | 460 | print_ipv6_masked(s, addr, netmask); |
d31f1109 JP |
461 | ds_put_char(s, ','); |
462 | } | |
463 | } | |
464 | ||
73f33563 BP |
465 | |
466 | static void | |
467 | format_be16_masked(struct ds *s, const char *name, | |
468 | ovs_be16 value, ovs_be16 mask) | |
469 | { | |
470 | if (mask != htons(0)) { | |
471 | ds_put_format(s, "%s=", name); | |
472 | if (mask == htons(UINT16_MAX)) { | |
473 | ds_put_format(s, "%"PRIu16, ntohs(value)); | |
474 | } else { | |
475 | ds_put_format(s, "0x%"PRIx16"/0x%"PRIx16, | |
476 | ntohs(value), ntohs(mask)); | |
477 | } | |
478 | ds_put_char(s, ','); | |
479 | } | |
480 | } | |
481 | ||
07b37e8f BP |
482 | void |
483 | cls_rule_format(const struct cls_rule *rule, struct ds *s) | |
484 | { | |
485 | const struct flow_wildcards *wc = &rule->wc; | |
486 | size_t start_len = s->length; | |
487 | flow_wildcards_t w = wc->wildcards; | |
488 | const struct flow *f = &rule->flow; | |
489 | bool skip_type = false; | |
490 | bool skip_proto = false; | |
491 | ||
492 | int i; | |
493 | ||
e9358af6 | 494 | BUILD_ASSERT_DECL(FLOW_WC_SEQ == 9); |
a877206f | 495 | |
8fe2b968 | 496 | if (rule->priority != OFP_DEFAULT_PRIORITY) { |
07b37e8f BP |
497 | ds_put_format(s, "priority=%d,", rule->priority); |
498 | } | |
499 | ||
500 | if (!(w & FWW_DL_TYPE)) { | |
501 | skip_type = true; | |
502 | if (f->dl_type == htons(ETH_TYPE_IP)) { | |
503 | if (!(w & FWW_NW_PROTO)) { | |
504 | skip_proto = true; | |
6767a2cc | 505 | if (f->nw_proto == IPPROTO_ICMP) { |
07b37e8f | 506 | ds_put_cstr(s, "icmp,"); |
6767a2cc | 507 | } else if (f->nw_proto == IPPROTO_TCP) { |
07b37e8f | 508 | ds_put_cstr(s, "tcp,"); |
6767a2cc | 509 | } else if (f->nw_proto == IPPROTO_UDP) { |
07b37e8f BP |
510 | ds_put_cstr(s, "udp,"); |
511 | } else { | |
512 | ds_put_cstr(s, "ip,"); | |
513 | skip_proto = false; | |
514 | } | |
515 | } else { | |
516 | ds_put_cstr(s, "ip,"); | |
517 | } | |
d31f1109 JP |
518 | } else if (f->dl_type == htons(ETH_TYPE_IPV6)) { |
519 | if (!(w & FWW_NW_PROTO)) { | |
520 | skip_proto = true; | |
521 | if (f->nw_proto == IPPROTO_ICMPV6) { | |
522 | ds_put_cstr(s, "icmp6,"); | |
523 | } else if (f->nw_proto == IPPROTO_TCP) { | |
524 | ds_put_cstr(s, "tcp6,"); | |
525 | } else if (f->nw_proto == IPPROTO_UDP) { | |
526 | ds_put_cstr(s, "udp6,"); | |
527 | } else { | |
528 | ds_put_cstr(s, "ipv6,"); | |
529 | skip_proto = false; | |
530 | } | |
531 | } else { | |
532 | ds_put_cstr(s, "ipv6,"); | |
533 | } | |
07b37e8f BP |
534 | } else if (f->dl_type == htons(ETH_TYPE_ARP)) { |
535 | ds_put_cstr(s, "arp,"); | |
536 | } else { | |
537 | skip_type = false; | |
538 | } | |
539 | } | |
540 | for (i = 0; i < FLOW_N_REGS; i++) { | |
541 | switch (wc->reg_masks[i]) { | |
542 | case 0: | |
543 | break; | |
544 | case UINT32_MAX: | |
545 | ds_put_format(s, "reg%d=0x%"PRIx32",", i, f->regs[i]); | |
546 | break; | |
547 | default: | |
548 | ds_put_format(s, "reg%d=0x%"PRIx32"/0x%"PRIx32",", | |
549 | i, f->regs[i], wc->reg_masks[i]); | |
550 | break; | |
551 | } | |
552 | } | |
8368c090 BP |
553 | switch (wc->tun_id_mask) { |
554 | case 0: | |
555 | break; | |
556 | case CONSTANT_HTONLL(UINT64_MAX): | |
557 | ds_put_format(s, "tun_id=%#"PRIx64",", ntohll(f->tun_id)); | |
558 | break; | |
559 | default: | |
560 | ds_put_format(s, "tun_id=%#"PRIx64"/%#"PRIx64",", | |
561 | ntohll(f->tun_id), ntohll(wc->tun_id_mask)); | |
562 | break; | |
07b37e8f BP |
563 | } |
564 | if (!(w & FWW_IN_PORT)) { | |
abe529af | 565 | ds_put_format(s, "in_port=%"PRIu16",", f->in_port); |
07b37e8f BP |
566 | } |
567 | if (wc->vlan_tci_mask) { | |
568 | ovs_be16 vid_mask = wc->vlan_tci_mask & htons(VLAN_VID_MASK); | |
569 | ovs_be16 pcp_mask = wc->vlan_tci_mask & htons(VLAN_PCP_MASK); | |
570 | ovs_be16 cfi = wc->vlan_tci_mask & htons(VLAN_CFI); | |
571 | ||
572 | if (cfi && f->vlan_tci & htons(VLAN_CFI) | |
573 | && (!vid_mask || vid_mask == htons(VLAN_VID_MASK)) | |
574 | && (!pcp_mask || pcp_mask == htons(VLAN_PCP_MASK)) | |
575 | && (vid_mask || pcp_mask)) { | |
576 | if (vid_mask) { | |
577 | ds_put_format(s, "dl_vlan=%"PRIu16",", | |
578 | vlan_tci_to_vid(f->vlan_tci)); | |
579 | } | |
580 | if (pcp_mask) { | |
581 | ds_put_format(s, "dl_vlan_pcp=%d,", | |
582 | vlan_tci_to_pcp(f->vlan_tci)); | |
583 | } | |
ce0307c4 BP |
584 | } else if (wc->vlan_tci_mask == htons(0xffff)) { |
585 | ds_put_format(s, "vlan_tci=0x%04"PRIx16",", ntohs(f->vlan_tci)); | |
07b37e8f BP |
586 | } else { |
587 | ds_put_format(s, "vlan_tci=0x%04"PRIx16"/0x%04"PRIx16",", | |
588 | ntohs(f->vlan_tci), ntohs(wc->vlan_tci_mask)); | |
589 | } | |
590 | } | |
591 | if (!(w & FWW_DL_SRC)) { | |
592 | ds_put_format(s, "dl_src="ETH_ADDR_FMT",", ETH_ADDR_ARGS(f->dl_src)); | |
593 | } | |
594 | switch (w & (FWW_DL_DST | FWW_ETH_MCAST)) { | |
595 | case 0: | |
596 | ds_put_format(s, "dl_dst="ETH_ADDR_FMT",", ETH_ADDR_ARGS(f->dl_dst)); | |
597 | break; | |
598 | case FWW_DL_DST: | |
599 | ds_put_format(s, "dl_dst="ETH_ADDR_FMT"/01:00:00:00:00:00,", | |
600 | ETH_ADDR_ARGS(f->dl_dst)); | |
601 | break; | |
602 | case FWW_ETH_MCAST: | |
603 | ds_put_format(s, "dl_dst="ETH_ADDR_FMT"/fe:ff:ff:ff:ff:ff,", | |
604 | ETH_ADDR_ARGS(f->dl_dst)); | |
605 | break; | |
606 | case FWW_DL_DST | FWW_ETH_MCAST: | |
607 | break; | |
608 | } | |
609 | if (!skip_type && !(w & FWW_DL_TYPE)) { | |
610 | ds_put_format(s, "dl_type=0x%04"PRIx16",", ntohs(f->dl_type)); | |
611 | } | |
d31f1109 JP |
612 | if (f->dl_type == htons(ETH_TYPE_IPV6)) { |
613 | format_ipv6_netmask(s, "ipv6_src", &f->ipv6_src, &wc->ipv6_src_mask); | |
614 | format_ipv6_netmask(s, "ipv6_dst", &f->ipv6_dst, &wc->ipv6_dst_mask); | |
fa8223b7 JP |
615 | if (!(w & FWW_IPV6_LABEL)) { |
616 | ds_put_format(s, "ipv6_label=0x%05"PRIx32",", ntohl(f->ipv6_label)); | |
617 | } | |
d31f1109 JP |
618 | } else { |
619 | format_ip_netmask(s, "nw_src", f->nw_src, wc->nw_src_mask); | |
620 | format_ip_netmask(s, "nw_dst", f->nw_dst, wc->nw_dst_mask); | |
621 | } | |
07b37e8f BP |
622 | if (!skip_proto && !(w & FWW_NW_PROTO)) { |
623 | if (f->dl_type == htons(ETH_TYPE_ARP)) { | |
fb115f91 | 624 | ds_put_format(s, "arp_op=%"PRIu8",", f->nw_proto); |
07b37e8f | 625 | } else { |
92ec5741 | 626 | ds_put_format(s, "nw_proto=%"PRIu8",", f->nw_proto); |
07b37e8f BP |
627 | } |
628 | } | |
bad68a99 JP |
629 | if (f->dl_type == htons(ETH_TYPE_ARP)) { |
630 | if (!(w & FWW_ARP_SHA)) { | |
631 | ds_put_format(s, "arp_sha="ETH_ADDR_FMT",", | |
632 | ETH_ADDR_ARGS(f->arp_sha)); | |
633 | } | |
634 | if (!(w & FWW_ARP_THA)) { | |
635 | ds_put_format(s, "arp_tha="ETH_ADDR_FMT",", | |
636 | ETH_ADDR_ARGS(f->arp_tha)); | |
637 | } | |
638 | } | |
2486e66a | 639 | if (!(w & FWW_NW_DSCP)) { |
eadef313 | 640 | ds_put_format(s, "nw_tos=%"PRIu8",", f->nw_tos & IP_DSCP_MASK); |
7257b535 | 641 | } |
2486e66a | 642 | if (!(w & FWW_NW_ECN)) { |
eadef313 | 643 | ds_put_format(s, "nw_ecn=%"PRIu8",", f->nw_tos & IP_ECN_MASK); |
530180fd | 644 | } |
a61680c6 JP |
645 | if (!(w & FWW_NW_TTL)) { |
646 | ds_put_format(s, "nw_ttl=%"PRIu8",", f->nw_ttl); | |
647 | } | |
eadef313 JP |
648 | switch (wc->nw_frag_mask) { |
649 | case FLOW_NW_FRAG_ANY | FLOW_NW_FRAG_LATER: | |
650 | ds_put_format(s, "nw_frag=%s,", | |
651 | f->nw_frag & FLOW_NW_FRAG_ANY | |
652 | ? (f->nw_frag & FLOW_NW_FRAG_LATER ? "later" : "first") | |
653 | : (f->nw_frag & FLOW_NW_FRAG_LATER ? "<error>" : "no")); | |
7257b535 BP |
654 | break; |
655 | ||
eadef313 JP |
656 | case FLOW_NW_FRAG_ANY: |
657 | ds_put_format(s, "nw_frag=%s,", | |
658 | f->nw_frag & FLOW_NW_FRAG_ANY ? "yes" : "no"); | |
7257b535 BP |
659 | break; |
660 | ||
eadef313 JP |
661 | case FLOW_NW_FRAG_LATER: |
662 | ds_put_format(s, "nw_frag=%s,", | |
663 | f->nw_frag & FLOW_NW_FRAG_LATER ? "later" : "not_later"); | |
7257b535 | 664 | break; |
07b37e8f | 665 | } |
6767a2cc | 666 | if (f->nw_proto == IPPROTO_ICMP) { |
73f33563 BP |
667 | format_be16_masked(s, "icmp_type", f->tp_src, wc->tp_src_mask); |
668 | format_be16_masked(s, "icmp_code", f->tp_dst, wc->tp_dst_mask); | |
d31f1109 | 669 | } else if (f->nw_proto == IPPROTO_ICMPV6) { |
73f33563 BP |
670 | format_be16_masked(s, "icmp_type", f->tp_src, wc->tp_src_mask); |
671 | format_be16_masked(s, "icmp_code", f->tp_dst, wc->tp_dst_mask); | |
685a51a5 JP |
672 | if (!(w & FWW_ND_TARGET)) { |
673 | ds_put_cstr(s, "nd_target="); | |
674 | print_ipv6_addr(s, &f->nd_target); | |
675 | ds_put_char(s, ','); | |
676 | } | |
677 | if (!(w & FWW_ARP_SHA)) { | |
b53055f4 | 678 | ds_put_format(s, "nd_sll="ETH_ADDR_FMT",", |
685a51a5 JP |
679 | ETH_ADDR_ARGS(f->arp_sha)); |
680 | } | |
681 | if (!(w & FWW_ARP_THA)) { | |
b53055f4 | 682 | ds_put_format(s, "nd_tll="ETH_ADDR_FMT",", |
685a51a5 JP |
683 | ETH_ADDR_ARGS(f->arp_tha)); |
684 | } | |
685 | } else { | |
73f33563 BP |
686 | format_be16_masked(s, "tp_src", f->tp_src, wc->tp_src_mask); |
687 | format_be16_masked(s, "tp_dst", f->tp_dst, wc->tp_dst_mask); | |
07b37e8f BP |
688 | } |
689 | ||
690 | if (s->length > start_len && ds_last(s) == ',') { | |
691 | s->length--; | |
692 | } | |
693 | } | |
694 | ||
68d1c8c3 BP |
695 | /* Converts 'rule' to a string and returns the string. The caller must free |
696 | * the string (with free()). */ | |
697 | char * | |
698 | cls_rule_to_string(const struct cls_rule *rule) | |
699 | { | |
700 | struct ds s = DS_EMPTY_INITIALIZER; | |
07b37e8f BP |
701 | cls_rule_format(rule, &s); |
702 | return ds_steal_cstr(&s); | |
68d1c8c3 BP |
703 | } |
704 | ||
064af421 BP |
705 | void |
706 | cls_rule_print(const struct cls_rule *rule) | |
707 | { | |
07b37e8f BP |
708 | char *s = cls_rule_to_string(rule); |
709 | puts(s); | |
710 | free(s); | |
064af421 | 711 | } |
064af421 BP |
712 | \f |
713 | /* Initializes 'cls' as a classifier that initially contains no classification | |
714 | * rules. */ | |
715 | void | |
716 | classifier_init(struct classifier *cls) | |
717 | { | |
064af421 | 718 | cls->n_rules = 0; |
b5d97350 | 719 | hmap_init(&cls->tables); |
064af421 BP |
720 | } |
721 | ||
722 | /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the | |
723 | * caller's responsibility. */ | |
724 | void | |
725 | classifier_destroy(struct classifier *cls) | |
726 | { | |
727 | if (cls) { | |
b5d97350 | 728 | struct cls_table *table, *next_table; |
064af421 | 729 | |
b5d97350 BP |
730 | HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { |
731 | hmap_destroy(&table->rules); | |
732 | hmap_remove(&cls->tables, &table->hmap_node); | |
733 | free(table); | |
064af421 | 734 | } |
b5d97350 | 735 | hmap_destroy(&cls->tables); |
064af421 BP |
736 | } |
737 | } | |
738 | ||
b5d97350 | 739 | /* Returns true if 'cls' contains no classification rules, false otherwise. */ |
064af421 BP |
740 | bool |
741 | classifier_is_empty(const struct classifier *cls) | |
742 | { | |
743 | return cls->n_rules == 0; | |
744 | } | |
745 | ||
746 | /* Returns the number of rules in 'classifier'. */ | |
747 | int | |
748 | classifier_count(const struct classifier *cls) | |
749 | { | |
750 | return cls->n_rules; | |
751 | } | |
752 | ||
b5d97350 BP |
753 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
754 | * must not modify or free it. | |
064af421 BP |
755 | * |
756 | * If 'cls' already contains an identical rule (including wildcards, values of | |
757 | * fixed fields, and priority), replaces the old rule by 'rule' and returns the | |
758 | * rule that was replaced. The caller takes ownership of the returned rule and | |
759 | * is thus responsible for freeing it, etc., as necessary. | |
760 | * | |
761 | * Returns NULL if 'cls' does not contain a rule with an identical key, after | |
762 | * inserting the new rule. In this case, no rules are displaced by the new | |
763 | * rule, even rules that cannot have any effect because the new rule matches a | |
764 | * superset of their flows and has higher priority. */ | |
765 | struct cls_rule * | |
08944c1d | 766 | classifier_replace(struct classifier *cls, struct cls_rule *rule) |
064af421 | 767 | { |
b5d97350 BP |
768 | struct cls_rule *old_rule; |
769 | struct cls_table *table; | |
770 | ||
771 | table = find_table(cls, &rule->wc); | |
772 | if (!table) { | |
773 | table = insert_table(cls, &rule->wc); | |
774 | } | |
775 | ||
776 | old_rule = insert_rule(table, rule); | |
777 | if (!old_rule) { | |
778 | table->n_table_rules++; | |
064af421 BP |
779 | cls->n_rules++; |
780 | } | |
b5d97350 | 781 | return old_rule; |
064af421 BP |
782 | } |
783 | ||
08944c1d BP |
784 | /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller |
785 | * must not modify or free it. | |
786 | * | |
787 | * 'cls' must not contain an identical rule (including wildcards, values of | |
788 | * fixed fields, and priority). Use classifier_find_rule_exactly() to find | |
789 | * such a rule. */ | |
790 | void | |
791 | classifier_insert(struct classifier *cls, struct cls_rule *rule) | |
792 | { | |
793 | struct cls_rule *displaced_rule = classifier_replace(cls, rule); | |
794 | assert(!displaced_rule); | |
795 | } | |
796 | ||
b5d97350 BP |
797 | /* Removes 'rule' from 'cls'. It is the caller's responsibility to free |
798 | * 'rule', if this is desirable. */ | |
064af421 BP |
799 | void |
800 | classifier_remove(struct classifier *cls, struct cls_rule *rule) | |
801 | { | |
b5d97350 BP |
802 | struct cls_rule *head; |
803 | struct cls_table *table; | |
064af421 | 804 | |
b5d97350 BP |
805 | table = find_table(cls, &rule->wc); |
806 | head = find_equal(table, &rule->flow, rule->hmap_node.hash); | |
807 | if (head != rule) { | |
808 | list_remove(&rule->list); | |
809 | } else if (list_is_empty(&rule->list)) { | |
810 | hmap_remove(&table->rules, &rule->hmap_node); | |
811 | } else { | |
812 | struct cls_rule *next = CONTAINER_OF(rule->list.next, | |
813 | struct cls_rule, list); | |
064af421 | 814 | |
b5d97350 BP |
815 | list_remove(&rule->list); |
816 | hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); | |
817 | } | |
064af421 | 818 | |
f6acdb44 | 819 | if (--table->n_table_rules == 0) { |
b5d97350 | 820 | destroy_table(cls, table); |
064af421 | 821 | } |
b5d97350 BP |
822 | |
823 | cls->n_rules--; | |
064af421 BP |
824 | } |
825 | ||
48c3de13 BP |
826 | /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. |
827 | * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules | |
3c4486a5 | 828 | * of equal priority match 'flow', returns one arbitrarily. */ |
48c3de13 | 829 | struct cls_rule * |
3c4486a5 | 830 | classifier_lookup(const struct classifier *cls, const struct flow *flow) |
48c3de13 | 831 | { |
b5d97350 BP |
832 | struct cls_table *table; |
833 | struct cls_rule *best; | |
48c3de13 | 834 | |
b5d97350 BP |
835 | best = NULL; |
836 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { | |
3c4486a5 BP |
837 | struct cls_rule *rule = find_match(table, flow); |
838 | if (rule && (!best || rule->priority > best->priority)) { | |
839 | best = rule; | |
b5d97350 | 840 | } |
48c3de13 | 841 | } |
b5d97350 | 842 | return best; |
48c3de13 BP |
843 | } |
844 | ||
b5d97350 BP |
845 | /* Finds and returns a rule in 'cls' with exactly the same priority and |
846 | * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't | |
c084ce1d | 847 | * contain an exact match. */ |
064af421 BP |
848 | struct cls_rule * |
849 | classifier_find_rule_exactly(const struct classifier *cls, | |
76ecc721 | 850 | const struct cls_rule *target) |
064af421 | 851 | { |
b5d97350 BP |
852 | struct cls_rule *head, *rule; |
853 | struct cls_table *table; | |
064af421 | 854 | |
b5d97350 BP |
855 | table = find_table(cls, &target->wc); |
856 | if (!table) { | |
857 | return NULL; | |
064af421 BP |
858 | } |
859 | ||
b5d97350 | 860 | head = find_equal(table, &target->flow, flow_hash(&target->flow, 0)); |
b5d97350 BP |
861 | FOR_EACH_RULE_IN_LIST (rule, head) { |
862 | if (target->priority >= rule->priority) { | |
863 | return target->priority == rule->priority ? rule : NULL; | |
064af421 BP |
864 | } |
865 | } | |
866 | return NULL; | |
867 | } | |
868 | ||
faa50f40 BP |
869 | /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are |
870 | * considered to overlap if both rules have the same priority and a packet | |
871 | * could match both. */ | |
49bdc010 JP |
872 | bool |
873 | classifier_rule_overlaps(const struct classifier *cls, | |
faa50f40 | 874 | const struct cls_rule *target) |
49bdc010 | 875 | { |
b5d97350 | 876 | struct cls_table *table; |
49bdc010 | 877 | |
b5d97350 BP |
878 | HMAP_FOR_EACH (table, hmap_node, &cls->tables) { |
879 | struct flow_wildcards wc; | |
880 | struct cls_rule *head; | |
49bdc010 | 881 | |
b5d97350 BP |
882 | flow_wildcards_combine(&wc, &target->wc, &table->wc); |
883 | HMAP_FOR_EACH (head, hmap_node, &table->rules) { | |
49bdc010 JP |
884 | struct cls_rule *rule; |
885 | ||
b5d97350 | 886 | FOR_EACH_RULE_IN_LIST (rule, head) { |
faa50f40 | 887 | if (rule->priority == target->priority |
b5d97350 | 888 | && flow_equal_except(&target->flow, &rule->flow, &wc)) { |
49bdc010 JP |
889 | return true; |
890 | } | |
891 | } | |
892 | } | |
893 | } | |
894 | ||
895 | return false; | |
896 | } | |
b5d97350 | 897 | \f |
5ecc9d81 BP |
898 | /* Iteration. */ |
899 | ||
900 | static bool | |
901 | rule_matches(const struct cls_rule *rule, const struct cls_rule *target) | |
902 | { | |
903 | return (!target | |
904 | || flow_equal_except(&rule->flow, &target->flow, &target->wc)); | |
905 | } | |
906 | ||
907 | static struct cls_rule * | |
908 | search_table(const struct cls_table *table, const struct cls_rule *target) | |
909 | { | |
910 | if (!target || !flow_wildcards_has_extra(&table->wc, &target->wc)) { | |
911 | struct cls_rule *rule; | |
912 | ||
913 | HMAP_FOR_EACH (rule, hmap_node, &table->rules) { | |
914 | if (rule_matches(rule, target)) { | |
915 | return rule; | |
916 | } | |
917 | } | |
918 | } | |
919 | return NULL; | |
920 | } | |
921 | ||
922 | /* Initializes 'cursor' for iterating through 'cls' rules that exactly match | |
923 | * 'target' or are more specific than 'target'. That is, a given 'rule' | |
924 | * matches 'target' if, for every field: | |
925 | * | |
926 | * - 'target' and 'rule' specify the same (non-wildcarded) value for the | |
927 | * field, or | |
928 | * | |
929 | * - 'target' wildcards the field, | |
930 | * | |
931 | * but not if: | |
932 | * | |
933 | * - 'target' and 'rule' specify different values for the field, or | |
934 | * | |
935 | * - 'target' specifies a value for the field but 'rule' wildcards it. | |
936 | * | |
937 | * Equivalently, the truth table for whether a field matches is: | |
938 | * | |
939 | * rule | |
940 | * | |
941 | * wildcard exact | |
942 | * +---------+---------+ | |
943 | * t wild | yes | yes | | |
944 | * a card | | | | |
945 | * r +---------+---------+ | |
946 | * g exact | no |if values| | |
947 | * e | |are equal| | |
948 | * t +---------+---------+ | |
949 | * | |
950 | * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD | |
951 | * commands and by OpenFlow 1.0 aggregate and flow stats. | |
952 | * | |
953 | * Ignores target->priority. | |
954 | * | |
955 | * 'target' may be NULL to iterate over every rule in 'cls'. */ | |
956 | void | |
957 | cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, | |
958 | const struct cls_rule *target) | |
959 | { | |
960 | cursor->cls = cls; | |
961 | cursor->target = target; | |
962 | } | |
963 | ||
964 | /* Returns the first matching cls_rule in 'cursor''s iteration, or a null | |
965 | * pointer if there are no matches. */ | |
966 | struct cls_rule * | |
967 | cls_cursor_first(struct cls_cursor *cursor) | |
968 | { | |
969 | struct cls_table *table; | |
970 | ||
7ac8d8cf | 971 | HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) { |
5ecc9d81 BP |
972 | struct cls_rule *rule = search_table(table, cursor->target); |
973 | if (rule) { | |
974 | cursor->table = table; | |
975 | return rule; | |
976 | } | |
977 | } | |
978 | ||
979 | return NULL; | |
980 | } | |
981 | ||
982 | /* Returns the next matching cls_rule in 'cursor''s iteration, or a null | |
983 | * pointer if there are no more matches. */ | |
984 | struct cls_rule * | |
985 | cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) | |
986 | { | |
987 | const struct cls_table *table; | |
988 | struct cls_rule *next; | |
989 | ||
955f579d BP |
990 | next = next_rule_in_list__(rule); |
991 | if (next->priority < rule->priority) { | |
5ecc9d81 BP |
992 | return next; |
993 | } | |
994 | ||
955f579d BP |
995 | /* 'next' is the head of the list, that is, the rule that is included in |
996 | * the table's hmap. (This is important when the classifier contains rules | |
997 | * that differ only in priority.) */ | |
998 | rule = next; | |
5ecc9d81 BP |
999 | HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { |
1000 | if (rule_matches(rule, cursor->target)) { | |
1001 | return rule; | |
1002 | } | |
1003 | } | |
1004 | ||
7ac8d8cf BP |
1005 | table = cursor->table; |
1006 | HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) { | |
5ecc9d81 BP |
1007 | rule = search_table(table, cursor->target); |
1008 | if (rule) { | |
1009 | cursor->table = table; | |
1010 | return rule; | |
1011 | } | |
1012 | } | |
1013 | ||
1014 | return NULL; | |
1015 | } | |
1016 | \f | |
b5d97350 BP |
1017 | static struct cls_table * |
1018 | find_table(const struct classifier *cls, const struct flow_wildcards *wc) | |
1019 | { | |
1020 | struct cls_table *table; | |
064af421 | 1021 | |
1006cda6 | 1022 | HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc, 0), |
b5d97350 BP |
1023 | &cls->tables) { |
1024 | if (flow_wildcards_equal(wc, &table->wc)) { | |
1025 | return table; | |
064af421 BP |
1026 | } |
1027 | } | |
b5d97350 | 1028 | return NULL; |
064af421 | 1029 | } |
064af421 | 1030 | |
b5d97350 BP |
1031 | static struct cls_table * |
1032 | insert_table(struct classifier *cls, const struct flow_wildcards *wc) | |
1033 | { | |
1034 | struct cls_table *table; | |
064af421 | 1035 | |
b5d97350 BP |
1036 | table = xzalloc(sizeof *table); |
1037 | hmap_init(&table->rules); | |
1038 | table->wc = *wc; | |
c23740be | 1039 | table->is_catchall = flow_wildcards_is_catchall(&table->wc); |
1006cda6 | 1040 | hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc, 0)); |
064af421 | 1041 | |
b5d97350 | 1042 | return table; |
064af421 BP |
1043 | } |
1044 | ||
b5d97350 BP |
1045 | static void |
1046 | destroy_table(struct classifier *cls, struct cls_table *table) | |
1047 | { | |
1048 | hmap_remove(&cls->tables, &table->hmap_node); | |
1049 | hmap_destroy(&table->rules); | |
1050 | free(table); | |
1051 | } | |
064af421 | 1052 | |
064af421 | 1053 | static struct cls_rule * |
b5d97350 BP |
1054 | find_match(const struct cls_table *table, const struct flow *flow) |
1055 | { | |
1056 | struct cls_rule *rule; | |
b5d97350 | 1057 | |
c23740be BP |
1058 | if (table->is_catchall) { |
1059 | HMAP_FOR_EACH (rule, hmap_node, &table->rules) { | |
b5d97350 | 1060 | return rule; |
064af421 | 1061 | } |
c23740be BP |
1062 | } else { |
1063 | struct flow f; | |
1064 | ||
1065 | f = *flow; | |
1066 | flow_zero_wildcards(&f, &table->wc); | |
1067 | HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0), | |
1068 | &table->rules) { | |
1069 | if (flow_equal(&f, &rule->flow)) { | |
1070 | return rule; | |
1071 | } | |
1072 | } | |
064af421 | 1073 | } |
c23740be | 1074 | |
064af421 BP |
1075 | return NULL; |
1076 | } | |
1077 | ||
1078 | static struct cls_rule * | |
b5d97350 | 1079 | find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash) |
064af421 | 1080 | { |
b5d97350 | 1081 | struct cls_rule *head; |
064af421 | 1082 | |
b5d97350 BP |
1083 | HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { |
1084 | if (flow_equal(&head->flow, flow)) { | |
1085 | return head; | |
064af421 BP |
1086 | } |
1087 | } | |
1088 | return NULL; | |
1089 | } | |
1090 | ||
b5d97350 BP |
1091 | static struct cls_rule * |
1092 | insert_rule(struct cls_table *table, struct cls_rule *new) | |
064af421 | 1093 | { |
b5d97350 | 1094 | struct cls_rule *head; |
064af421 | 1095 | |
b5d97350 | 1096 | new->hmap_node.hash = flow_hash(&new->flow, 0); |
064af421 | 1097 | |
b5d97350 BP |
1098 | head = find_equal(table, &new->flow, new->hmap_node.hash); |
1099 | if (!head) { | |
1100 | hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); | |
1101 | list_init(&new->list); | |
1102 | return NULL; | |
1103 | } else { | |
1104 | /* Scan the list for the insertion point that will keep the list in | |
1105 | * order of decreasing priority. */ | |
1106 | struct cls_rule *rule; | |
1107 | FOR_EACH_RULE_IN_LIST (rule, head) { | |
1108 | if (new->priority >= rule->priority) { | |
1109 | if (rule == head) { | |
1110 | /* 'new' is the new highest-priority flow in the list. */ | |
1111 | hmap_replace(&table->rules, | |
1112 | &rule->hmap_node, &new->hmap_node); | |
1113 | } | |
064af421 | 1114 | |
b5d97350 BP |
1115 | if (new->priority == rule->priority) { |
1116 | list_replace(&new->list, &rule->list); | |
1117 | return rule; | |
1118 | } else { | |
1119 | list_insert(&rule->list, &new->list); | |
1120 | return NULL; | |
1121 | } | |
1122 | } | |
1123 | } | |
064af421 | 1124 | |
b5d97350 BP |
1125 | /* Insert 'new' at the end of the list. */ |
1126 | list_push_back(&head->list, &new->list); | |
1127 | return NULL; | |
064af421 | 1128 | } |
064af421 BP |
1129 | } |
1130 | ||
b5d97350 | 1131 | static struct cls_rule * |
955f579d | 1132 | next_rule_in_list__(struct cls_rule *rule) |
064af421 | 1133 | { |
b5d97350 | 1134 | struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); |
955f579d BP |
1135 | return next; |
1136 | } | |
1137 | ||
1138 | static struct cls_rule * | |
1139 | next_rule_in_list(struct cls_rule *rule) | |
1140 | { | |
1141 | struct cls_rule *next = next_rule_in_list__(rule); | |
b5d97350 | 1142 | return next->priority < rule->priority ? next : NULL; |
064af421 BP |
1143 | } |
1144 | ||
d31f1109 JP |
1145 | static bool |
1146 | ipv6_equal_except(const struct in6_addr *a, const struct in6_addr *b, | |
1147 | const struct in6_addr *mask) | |
1148 | { | |
1149 | int i; | |
1150 | ||
1151 | #ifdef s6_addr32 | |
1152 | for (i=0; i<4; i++) { | |
1153 | if ((a->s6_addr32[i] ^ b->s6_addr32[i]) & mask->s6_addr32[i]) { | |
1154 | return false; | |
1155 | } | |
1156 | } | |
1157 | #else | |
1158 | for (i=0; i<16; i++) { | |
1159 | if ((a->s6_addr[i] ^ b->s6_addr[i]) & mask->s6_addr[i]) { | |
1160 | return false; | |
1161 | } | |
1162 | } | |
1163 | #endif | |
1164 | ||
1165 | return true; | |
1166 | } | |
1167 | ||
1168 | ||
064af421 | 1169 | static bool |
b5d97350 BP |
1170 | flow_equal_except(const struct flow *a, const struct flow *b, |
1171 | const struct flow_wildcards *wildcards) | |
064af421 | 1172 | { |
d8ae4d67 | 1173 | const flow_wildcards_t wc = wildcards->wildcards; |
b6c9e612 | 1174 | int i; |
49bdc010 | 1175 | |
e9358af6 | 1176 | BUILD_ASSERT_DECL(FLOW_WC_SEQ == 9); |
b6c9e612 BP |
1177 | |
1178 | for (i = 0; i < FLOW_N_REGS; i++) { | |
1179 | if ((a->regs[i] ^ b->regs[i]) & wildcards->reg_masks[i]) { | |
1180 | return false; | |
1181 | } | |
1182 | } | |
b5d97350 | 1183 | |
8368c090 | 1184 | return (!((a->tun_id ^ b->tun_id) & wildcards->tun_id_mask) |
b5d97350 BP |
1185 | && !((a->nw_src ^ b->nw_src) & wildcards->nw_src_mask) |
1186 | && !((a->nw_dst ^ b->nw_dst) & wildcards->nw_dst_mask) | |
d8ae4d67 | 1187 | && (wc & FWW_IN_PORT || a->in_port == b->in_port) |
66642cb4 | 1188 | && !((a->vlan_tci ^ b->vlan_tci) & wildcards->vlan_tci_mask) |
d8ae4d67 | 1189 | && (wc & FWW_DL_TYPE || a->dl_type == b->dl_type) |
73f33563 BP |
1190 | && !((a->tp_src ^ b->tp_src) & wildcards->tp_src_mask) |
1191 | && !((a->tp_dst ^ b->tp_dst) & wildcards->tp_dst_mask) | |
d8ae4d67 BP |
1192 | && (wc & FWW_DL_SRC || eth_addr_equals(a->dl_src, b->dl_src)) |
1193 | && (wc & FWW_DL_DST | |
1e37a2d7 BP |
1194 | || (!((a->dl_dst[0] ^ b->dl_dst[0]) & 0xfe) |
1195 | && a->dl_dst[1] == b->dl_dst[1] | |
1196 | && a->dl_dst[2] == b->dl_dst[2] | |
1197 | && a->dl_dst[3] == b->dl_dst[3] | |
1198 | && a->dl_dst[4] == b->dl_dst[4] | |
1199 | && a->dl_dst[5] == b->dl_dst[5])) | |
d8ae4d67 BP |
1200 | && (wc & FWW_ETH_MCAST |
1201 | || !((a->dl_dst[0] ^ b->dl_dst[0]) & 0x01)) | |
1202 | && (wc & FWW_NW_PROTO || a->nw_proto == b->nw_proto) | |
a61680c6 | 1203 | && (wc & FWW_NW_TTL || a->nw_ttl == b->nw_ttl) |
2486e66a JP |
1204 | && (wc & FWW_NW_DSCP || !((a->nw_tos ^ b->nw_tos) & IP_DSCP_MASK)) |
1205 | && (wc & FWW_NW_ECN || !((a->nw_tos ^ b->nw_tos) & IP_ECN_MASK)) | |
eadef313 | 1206 | && !((a->nw_frag ^ b->nw_frag) & wildcards->nw_frag_mask) |
bad68a99 | 1207 | && (wc & FWW_ARP_SHA || eth_addr_equals(a->arp_sha, b->arp_sha)) |
d31f1109 | 1208 | && (wc & FWW_ARP_THA || eth_addr_equals(a->arp_tha, b->arp_tha)) |
fa8223b7 | 1209 | && (wc & FWW_IPV6_LABEL || a->ipv6_label == b->ipv6_label) |
d31f1109 JP |
1210 | && ipv6_equal_except(&a->ipv6_src, &b->ipv6_src, |
1211 | &wildcards->ipv6_src_mask) | |
1212 | && ipv6_equal_except(&a->ipv6_dst, &b->ipv6_dst, | |
685a51a5 | 1213 | &wildcards->ipv6_dst_mask) |
b53055f4 | 1214 | && (wc & FWW_ND_TARGET |
685a51a5 | 1215 | || ipv6_addr_equals(&a->nd_target, &b->nd_target))); |
064af421 | 1216 | } |