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