]>
git.proxmox.com Git - ovs.git/blob - lib/classifier.c
2 * Copyright (c) 2009, 2010, 2011 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "classifier.h"
21 #include <netinet/in.h>
22 #include "byte-order.h"
23 #include "dynamic-string.h"
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
*);
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
*);
40 static struct cls_rule
*find_match(const struct cls_table
*,
42 static struct cls_rule
*find_equal(struct cls_table
*, const struct flow
*,
44 static struct cls_rule
*insert_rule(struct cls_table
*, struct cls_rule
*);
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
*);
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); \
58 static struct cls_rule
*next_rule_in_list__(struct cls_rule
*);
59 static struct cls_rule
*next_rule_in_list(struct cls_rule
*);
61 static struct cls_table
*
62 cls_table_from_hmap_node(const struct hmap_node
*node
)
64 return node
? CONTAINER_OF(node
, struct cls_table
, hmap_node
) : NULL
;
67 /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given
68 * 'wildcards' and 'priority'. */
70 cls_rule_init(const struct flow
*flow
, const struct flow_wildcards
*wildcards
,
71 unsigned int priority
, struct cls_rule
*rule
)
74 rule
->wc
= *wildcards
;
75 rule
->priority
= priority
;
76 cls_rule_zero_wildcarded_fields(rule
);
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.) */
83 cls_rule_init_exact(const struct flow
*flow
,
84 unsigned int priority
, struct cls_rule
*rule
)
87 flow_wildcards_init_exact(&rule
->wc
);
88 rule
->priority
= priority
;
91 /* Initializes 'rule' as a "catch-all" rule that matches every packet, with
92 * priority 'priority'. */
94 cls_rule_init_catchall(struct cls_rule
*rule
, unsigned int priority
)
96 memset(&rule
->flow
, 0, sizeof rule
->flow
);
97 flow_wildcards_init_catchall(&rule
->wc
);
98 rule
->priority
= priority
;
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.
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.
110 cls_rule_zero_wildcarded_fields(struct cls_rule
*rule
)
112 zero_wildcards(&rule
->flow
, &rule
->wc
);
116 cls_rule_set_reg(struct cls_rule
*rule
, unsigned int reg_idx
, uint32_t value
)
118 cls_rule_set_reg_masked(rule
, reg_idx
, value
, UINT32_MAX
);
122 cls_rule_set_reg_masked(struct cls_rule
*rule
, unsigned int reg_idx
,
123 uint32_t value
, uint32_t mask
)
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
;
131 cls_rule_set_tun_id(struct cls_rule
*rule
, ovs_be64 tun_id
)
133 cls_rule_set_tun_id_masked(rule
, tun_id
, htonll(UINT64_MAX
));
137 cls_rule_set_tun_id_masked(struct cls_rule
*rule
,
138 ovs_be64 tun_id
, ovs_be64 mask
)
140 rule
->wc
.tun_id_mask
= mask
;
141 rule
->flow
.tun_id
= tun_id
& mask
;
145 cls_rule_set_in_port(struct cls_rule
*rule
, uint16_t odp_port
)
147 rule
->wc
.wildcards
&= ~FWW_IN_PORT
;
148 rule
->flow
.in_port
= odp_port
;
152 cls_rule_set_dl_type(struct cls_rule
*rule
, ovs_be16 dl_type
)
154 rule
->wc
.wildcards
&= ~FWW_DL_TYPE
;
155 rule
->flow
.dl_type
= dl_type
;
159 cls_rule_set_dl_src(struct cls_rule
*rule
, const uint8_t dl_src
[ETH_ADDR_LEN
])
161 rule
->wc
.wildcards
&= ~FWW_DL_SRC
;
162 memcpy(rule
->flow
.dl_src
, dl_src
, ETH_ADDR_LEN
);
166 cls_rule_set_dl_dst(struct cls_rule
*rule
, const uint8_t dl_dst
[ETH_ADDR_LEN
])
168 rule
->wc
.wildcards
&= ~(FWW_DL_DST
| FWW_ETH_MCAST
);
169 memcpy(rule
->flow
.dl_dst
, dl_dst
, ETH_ADDR_LEN
);
173 cls_rule_set_dl_tci(struct cls_rule
*rule
, ovs_be16 tci
)
175 cls_rule_set_dl_tci_masked(rule
, tci
, htons(0xffff));
179 cls_rule_set_dl_tci_masked(struct cls_rule
*rule
, ovs_be16 tci
, ovs_be16 mask
)
181 rule
->flow
.vlan_tci
= tci
& mask
;
182 rule
->wc
.vlan_tci_mask
= mask
;
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. */
189 cls_rule_set_any_vid(struct cls_rule
*rule
)
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
);
195 cls_rule_set_dl_tci_masked(rule
, htons(0), htons(0));
199 /* Modifies 'rule' depending on 'dl_vlan':
201 * - If 'dl_vlan' is htons(OFP_VLAN_NONE), makes 'rule' match only packets
202 * without an 802.1Q header.
204 * - Otherwise, makes 'rule' match only packets with an 802.1Q header whose
205 * VID equals the low 12 bits of 'dl_vlan'.
208 cls_rule_set_dl_vlan(struct cls_rule
*rule
, ovs_be16 dl_vlan
)
210 if (dl_vlan
== htons(OFP_VLAN_NONE
)) {
211 cls_rule_set_dl_tci(rule
, htons(0));
213 dl_vlan
&= htons(VLAN_VID_MASK
);
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
);
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. */
224 cls_rule_set_any_pcp(struct cls_rule
*rule
)
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
);
230 cls_rule_set_dl_tci_masked(rule
, htons(0), htons(0));
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'. */
237 cls_rule_set_dl_vlan_pcp(struct cls_rule
*rule
, uint8_t dl_vlan_pcp
)
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
);
246 cls_rule_set_tp_src(struct cls_rule
*rule
, ovs_be16 tp_src
)
248 rule
->wc
.wildcards
&= ~FWW_TP_SRC
;
249 rule
->flow
.tp_src
= tp_src
;
253 cls_rule_set_tp_dst(struct cls_rule
*rule
, ovs_be16 tp_dst
)
255 rule
->wc
.wildcards
&= ~FWW_TP_DST
;
256 rule
->flow
.tp_dst
= tp_dst
;
260 cls_rule_set_nw_proto(struct cls_rule
*rule
, uint8_t nw_proto
)
262 rule
->wc
.wildcards
&= ~FWW_NW_PROTO
;
263 rule
->flow
.nw_proto
= nw_proto
;
267 cls_rule_set_nw_src(struct cls_rule
*rule
, ovs_be32 nw_src
)
269 cls_rule_set_nw_src_masked(rule
, nw_src
, htonl(UINT32_MAX
));
273 cls_rule_set_nw_src_masked(struct cls_rule
*rule
, ovs_be32 ip
, ovs_be32 mask
)
275 if (flow_wildcards_set_nw_src_mask(&rule
->wc
, mask
)) {
276 rule
->flow
.nw_src
= ip
& mask
;
284 cls_rule_set_nw_dst(struct cls_rule
*rule
, ovs_be32 nw_dst
)
286 cls_rule_set_nw_dst_masked(rule
, nw_dst
, htonl(UINT32_MAX
));
290 cls_rule_set_nw_dst_masked(struct cls_rule
*rule
, ovs_be32 ip
, ovs_be32 mask
)
292 if (flow_wildcards_set_nw_dst_mask(&rule
->wc
, mask
)) {
293 rule
->flow
.nw_dst
= ip
& mask
;
301 cls_rule_set_nw_tos(struct cls_rule
*rule
, uint8_t nw_tos
)
303 rule
->wc
.wildcards
&= ~FWW_NW_TOS
;
304 rule
->flow
.nw_tos
= nw_tos
& IP_DSCP_MASK
;
308 cls_rule_set_icmp_type(struct cls_rule
*rule
, uint8_t icmp_type
)
310 rule
->wc
.wildcards
&= ~FWW_TP_SRC
;
311 rule
->flow
.icmp_type
= htons(icmp_type
);
316 cls_rule_set_icmp_code(struct cls_rule
*rule
, uint8_t icmp_code
)
318 rule
->wc
.wildcards
&= ~FWW_TP_DST
;
319 rule
->flow
.icmp_code
= htons(icmp_code
);
323 cls_rule_set_arp_sha(struct cls_rule
*rule
, const uint8_t sha
[ETH_ADDR_LEN
])
325 rule
->wc
.wildcards
&= ~FWW_ARP_SHA
;
326 memcpy(rule
->flow
.arp_sha
, sha
, ETH_ADDR_LEN
);
330 cls_rule_set_arp_tha(struct cls_rule
*rule
, const uint8_t tha
[ETH_ADDR_LEN
])
332 rule
->wc
.wildcards
&= ~FWW_ARP_THA
;
333 memcpy(rule
->flow
.arp_tha
, tha
, ETH_ADDR_LEN
);
337 cls_rule_set_ipv6_src(struct cls_rule
*rule
, const struct in6_addr
*src
)
339 cls_rule_set_ipv6_src_masked(rule
, src
, &in6addr_exact
);
343 cls_rule_set_ipv6_src_masked(struct cls_rule
*rule
, const struct in6_addr
*src
,
344 const struct in6_addr
*mask
)
346 if (flow_wildcards_set_ipv6_src_mask(&rule
->wc
, mask
)) {
347 rule
->flow
.ipv6_src
= ipv6_addr_bitand(src
, mask
);
355 cls_rule_set_ipv6_dst(struct cls_rule
*rule
, const struct in6_addr
*dst
)
357 cls_rule_set_ipv6_dst_masked(rule
, dst
, &in6addr_exact
);
361 cls_rule_set_ipv6_dst_masked(struct cls_rule
*rule
, const struct in6_addr
*dst
,
362 const struct in6_addr
*mask
)
364 if (flow_wildcards_set_ipv6_dst_mask(&rule
->wc
, mask
)) {
365 rule
->flow
.ipv6_dst
= ipv6_addr_bitand(dst
, mask
);
372 /* Returns true if 'a' and 'b' have the same priority, wildcard the same
373 * fields, and have the same values for fixed fields, otherwise false. */
375 cls_rule_equal(const struct cls_rule
*a
, const struct cls_rule
*b
)
377 return (a
->priority
== b
->priority
378 && flow_wildcards_equal(&a
->wc
, &b
->wc
)
379 && flow_equal(&a
->flow
, &b
->flow
));
383 format_ip_netmask(struct ds
*s
, const char *name
, ovs_be32 ip
,
387 ds_put_format(s
, "%s="IP_FMT
, name
, IP_ARGS(&ip
));
388 if (netmask
!= htonl(UINT32_MAX
)) {
389 if (ip_is_cidr(netmask
)) {
390 int wcbits
= ofputil_netmask_to_wcbits(netmask
);
391 ds_put_format(s
, "/%d", 32 - wcbits
);
393 ds_put_format(s
, "/"IP_FMT
, IP_ARGS(&netmask
));
401 format_ipv6_netmask(struct ds
*s
, const char *name
,
402 const struct in6_addr
*addr
,
403 const struct in6_addr
*netmask
)
405 if (!ipv6_mask_is_any(netmask
)) {
406 ds_put_format(s
, "%s=", name
);
407 print_ipv6_addr(s
, addr
);
408 if (!ipv6_mask_is_exact(netmask
)) {
409 if (ipv6_is_cidr(netmask
)) {
410 int cidr_bits
= ipv6_count_cidr_bits(netmask
);
411 ds_put_format(s
, "/%d", cidr_bits
);
414 print_ipv6_addr(s
, netmask
);
422 cls_rule_format(const struct cls_rule
*rule
, struct ds
*s
)
424 const struct flow_wildcards
*wc
= &rule
->wc
;
425 size_t start_len
= s
->length
;
426 flow_wildcards_t w
= wc
->wildcards
;
427 const struct flow
*f
= &rule
->flow
;
428 bool skip_type
= false;
429 bool skip_proto
= false;
433 if (rule
->priority
!= OFP_DEFAULT_PRIORITY
) {
434 ds_put_format(s
, "priority=%d,", rule
->priority
);
437 if (!(w
& FWW_DL_TYPE
)) {
439 if (f
->dl_type
== htons(ETH_TYPE_IP
)) {
440 if (!(w
& FWW_NW_PROTO
)) {
442 if (f
->nw_proto
== IPPROTO_ICMP
) {
443 ds_put_cstr(s
, "icmp,");
444 } else if (f
->nw_proto
== IPPROTO_TCP
) {
445 ds_put_cstr(s
, "tcp,");
446 } else if (f
->nw_proto
== IPPROTO_UDP
) {
447 ds_put_cstr(s
, "udp,");
449 ds_put_cstr(s
, "ip,");
453 ds_put_cstr(s
, "ip,");
455 } else if (f
->dl_type
== htons(ETH_TYPE_IPV6
)) {
456 if (!(w
& FWW_NW_PROTO
)) {
458 if (f
->nw_proto
== IPPROTO_ICMPV6
) {
459 ds_put_cstr(s
, "icmp6,");
460 } else if (f
->nw_proto
== IPPROTO_TCP
) {
461 ds_put_cstr(s
, "tcp6,");
462 } else if (f
->nw_proto
== IPPROTO_UDP
) {
463 ds_put_cstr(s
, "udp6,");
465 ds_put_cstr(s
, "ipv6,");
469 ds_put_cstr(s
, "ipv6,");
471 } else if (f
->dl_type
== htons(ETH_TYPE_ARP
)) {
472 ds_put_cstr(s
, "arp,");
477 for (i
= 0; i
< FLOW_N_REGS
; i
++) {
478 switch (wc
->reg_masks
[i
]) {
482 ds_put_format(s
, "reg%d=0x%"PRIx32
",", i
, f
->regs
[i
]);
485 ds_put_format(s
, "reg%d=0x%"PRIx32
"/0x%"PRIx32
",",
486 i
, f
->regs
[i
], wc
->reg_masks
[i
]);
490 switch (wc
->tun_id_mask
) {
493 case CONSTANT_HTONLL(UINT64_MAX
):
494 ds_put_format(s
, "tun_id=%#"PRIx64
",", ntohll(f
->tun_id
));
497 ds_put_format(s
, "tun_id=%#"PRIx64
"/%#"PRIx64
",",
498 ntohll(f
->tun_id
), ntohll(wc
->tun_id_mask
));
501 if (!(w
& FWW_IN_PORT
)) {
502 ds_put_format(s
, "in_port=%"PRIu16
",",
503 odp_port_to_ofp_port(f
->in_port
));
505 if (wc
->vlan_tci_mask
) {
506 ovs_be16 vid_mask
= wc
->vlan_tci_mask
& htons(VLAN_VID_MASK
);
507 ovs_be16 pcp_mask
= wc
->vlan_tci_mask
& htons(VLAN_PCP_MASK
);
508 ovs_be16 cfi
= wc
->vlan_tci_mask
& htons(VLAN_CFI
);
510 if (cfi
&& f
->vlan_tci
& htons(VLAN_CFI
)
511 && (!vid_mask
|| vid_mask
== htons(VLAN_VID_MASK
))
512 && (!pcp_mask
|| pcp_mask
== htons(VLAN_PCP_MASK
))
513 && (vid_mask
|| pcp_mask
)) {
515 ds_put_format(s
, "dl_vlan=%"PRIu16
",",
516 vlan_tci_to_vid(f
->vlan_tci
));
519 ds_put_format(s
, "dl_vlan_pcp=%d,",
520 vlan_tci_to_pcp(f
->vlan_tci
));
523 ds_put_format(s
, "vlan_tci=0x%04"PRIx16
"/0x%04"PRIx16
",",
524 ntohs(f
->vlan_tci
), ntohs(wc
->vlan_tci_mask
));
527 if (!(w
& FWW_DL_SRC
)) {
528 ds_put_format(s
, "dl_src="ETH_ADDR_FMT
",", ETH_ADDR_ARGS(f
->dl_src
));
530 switch (w
& (FWW_DL_DST
| FWW_ETH_MCAST
)) {
532 ds_put_format(s
, "dl_dst="ETH_ADDR_FMT
",", ETH_ADDR_ARGS(f
->dl_dst
));
535 ds_put_format(s
, "dl_dst="ETH_ADDR_FMT
"/01:00:00:00:00:00,",
536 ETH_ADDR_ARGS(f
->dl_dst
));
539 ds_put_format(s
, "dl_dst="ETH_ADDR_FMT
"/fe:ff:ff:ff:ff:ff,",
540 ETH_ADDR_ARGS(f
->dl_dst
));
542 case FWW_DL_DST
| FWW_ETH_MCAST
:
545 if (!skip_type
&& !(w
& FWW_DL_TYPE
)) {
546 ds_put_format(s
, "dl_type=0x%04"PRIx16
",", ntohs(f
->dl_type
));
548 if (f
->dl_type
== htons(ETH_TYPE_IPV6
)) {
549 format_ipv6_netmask(s
, "ipv6_src", &f
->ipv6_src
, &wc
->ipv6_src_mask
);
550 format_ipv6_netmask(s
, "ipv6_dst", &f
->ipv6_dst
, &wc
->ipv6_dst_mask
);
552 format_ip_netmask(s
, "nw_src", f
->nw_src
, wc
->nw_src_mask
);
553 format_ip_netmask(s
, "nw_dst", f
->nw_dst
, wc
->nw_dst_mask
);
555 if (!skip_proto
&& !(w
& FWW_NW_PROTO
)) {
556 if (f
->dl_type
== htons(ETH_TYPE_ARP
)) {
557 ds_put_format(s
, "opcode=%"PRIu8
",", f
->nw_proto
);
559 ds_put_format(s
, "nw_proto=%"PRIu8
",", f
->nw_proto
);
562 if (f
->dl_type
== htons(ETH_TYPE_ARP
)) {
563 if (!(w
& FWW_ARP_SHA
)) {
564 ds_put_format(s
, "arp_sha="ETH_ADDR_FMT
",",
565 ETH_ADDR_ARGS(f
->arp_sha
));
567 if (!(w
& FWW_ARP_THA
)) {
568 ds_put_format(s
, "arp_tha="ETH_ADDR_FMT
",",
569 ETH_ADDR_ARGS(f
->arp_tha
));
572 if (!(w
& FWW_NW_TOS
)) {
573 ds_put_format(s
, "nw_tos=%"PRIu8
",", f
->nw_tos
);
575 if (f
->nw_proto
== IPPROTO_ICMP
) {
576 if (!(w
& FWW_TP_SRC
)) {
577 ds_put_format(s
, "icmp_type=%"PRIu16
",", ntohs(f
->tp_src
));
579 if (!(w
& FWW_TP_DST
)) {
580 ds_put_format(s
, "icmp_code=%"PRIu16
",", ntohs(f
->tp_dst
));
582 } else if (f
->nw_proto
== IPPROTO_ICMPV6
) {
583 if (!(w
& FWW_TP_SRC
)) {
584 ds_put_format(s
, "icmp_type=%"PRIu16
",", ntohs(f
->tp_src
));
586 if (!(w
& FWW_TP_DST
)) {
587 ds_put_format(s
, "icmp_code=%"PRIu16
",", ntohs(f
->tp_dst
));
590 if (!(w
& FWW_TP_SRC
)) {
591 ds_put_format(s
, "tp_src=%"PRIu16
",", ntohs(f
->tp_src
));
593 if (!(w
& FWW_TP_DST
)) {
594 ds_put_format(s
, "tp_dst=%"PRIu16
",", ntohs(f
->tp_dst
));
598 if (s
->length
> start_len
&& ds_last(s
) == ',') {
603 /* Converts 'rule' to a string and returns the string. The caller must free
604 * the string (with free()). */
606 cls_rule_to_string(const struct cls_rule
*rule
)
608 struct ds s
= DS_EMPTY_INITIALIZER
;
609 cls_rule_format(rule
, &s
);
610 return ds_steal_cstr(&s
);
614 cls_rule_print(const struct cls_rule
*rule
)
616 char *s
= cls_rule_to_string(rule
);
621 /* Initializes 'cls' as a classifier that initially contains no classification
624 classifier_init(struct classifier
*cls
)
627 hmap_init(&cls
->tables
);
630 /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
631 * caller's responsibility. */
633 classifier_destroy(struct classifier
*cls
)
636 struct cls_table
*table
, *next_table
;
638 HMAP_FOR_EACH_SAFE (table
, next_table
, hmap_node
, &cls
->tables
) {
639 hmap_destroy(&table
->rules
);
640 hmap_remove(&cls
->tables
, &table
->hmap_node
);
643 hmap_destroy(&cls
->tables
);
647 /* Returns true if 'cls' contains no classification rules, false otherwise. */
649 classifier_is_empty(const struct classifier
*cls
)
651 return cls
->n_rules
== 0;
654 /* Returns the number of rules in 'classifier'. */
656 classifier_count(const struct classifier
*cls
)
661 /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
662 * must not modify or free it.
664 * If 'cls' already contains an identical rule (including wildcards, values of
665 * fixed fields, and priority), replaces the old rule by 'rule' and returns the
666 * rule that was replaced. The caller takes ownership of the returned rule and
667 * is thus responsible for freeing it, etc., as necessary.
669 * Returns NULL if 'cls' does not contain a rule with an identical key, after
670 * inserting the new rule. In this case, no rules are displaced by the new
671 * rule, even rules that cannot have any effect because the new rule matches a
672 * superset of their flows and has higher priority. */
674 classifier_insert(struct classifier
*cls
, struct cls_rule
*rule
)
676 struct cls_rule
*old_rule
;
677 struct cls_table
*table
;
679 table
= find_table(cls
, &rule
->wc
);
681 table
= insert_table(cls
, &rule
->wc
);
684 old_rule
= insert_rule(table
, rule
);
686 table
->n_table_rules
++;
692 /* Removes 'rule' from 'cls'. It is the caller's responsibility to free
693 * 'rule', if this is desirable. */
695 classifier_remove(struct classifier
*cls
, struct cls_rule
*rule
)
697 struct cls_rule
*head
;
698 struct cls_table
*table
;
700 table
= find_table(cls
, &rule
->wc
);
701 head
= find_equal(table
, &rule
->flow
, rule
->hmap_node
.hash
);
703 list_remove(&rule
->list
);
704 } else if (list_is_empty(&rule
->list
)) {
705 hmap_remove(&table
->rules
, &rule
->hmap_node
);
707 struct cls_rule
*next
= CONTAINER_OF(rule
->list
.next
,
708 struct cls_rule
, list
);
710 list_remove(&rule
->list
);
711 hmap_replace(&table
->rules
, &rule
->hmap_node
, &next
->hmap_node
);
714 if (--table
->n_table_rules
== 0) {
715 destroy_table(cls
, table
);
721 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
722 * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules
723 * of equal priority match 'flow', returns one arbitrarily. */
725 classifier_lookup(const struct classifier
*cls
, const struct flow
*flow
)
727 struct cls_table
*table
;
728 struct cls_rule
*best
;
731 HMAP_FOR_EACH (table
, hmap_node
, &cls
->tables
) {
732 struct cls_rule
*rule
= find_match(table
, flow
);
733 if (rule
&& (!best
|| rule
->priority
> best
->priority
)) {
740 /* Finds and returns a rule in 'cls' with exactly the same priority and
741 * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't
742 * contain an exact match.
744 * Priority is ignored for exact-match rules (because OpenFlow 1.0 always
745 * treats exact-match rules as highest priority). */
747 classifier_find_rule_exactly(const struct classifier
*cls
,
748 const struct cls_rule
*target
)
750 struct cls_rule
*head
, *rule
;
751 struct cls_table
*table
;
753 table
= find_table(cls
, &target
->wc
);
758 head
= find_equal(table
, &target
->flow
, flow_hash(&target
->flow
, 0));
759 if (flow_wildcards_is_exact(&target
->wc
)) {
762 FOR_EACH_RULE_IN_LIST (rule
, head
) {
763 if (target
->priority
>= rule
->priority
) {
764 return target
->priority
== rule
->priority
? rule
: NULL
;
770 /* Checks if 'target' would overlap any other rule in 'cls'. Two rules are
771 * considered to overlap if both rules have the same priority and a packet
772 * could match both. */
774 classifier_rule_overlaps(const struct classifier
*cls
,
775 const struct cls_rule
*target
)
777 struct cls_table
*table
;
779 HMAP_FOR_EACH (table
, hmap_node
, &cls
->tables
) {
780 struct flow_wildcards wc
;
781 struct cls_rule
*head
;
783 flow_wildcards_combine(&wc
, &target
->wc
, &table
->wc
);
784 HMAP_FOR_EACH (head
, hmap_node
, &table
->rules
) {
785 struct cls_rule
*rule
;
787 FOR_EACH_RULE_IN_LIST (rule
, head
) {
788 if (rule
->priority
== target
->priority
789 && flow_equal_except(&target
->flow
, &rule
->flow
, &wc
)) {
802 rule_matches(const struct cls_rule
*rule
, const struct cls_rule
*target
)
805 || flow_equal_except(&rule
->flow
, &target
->flow
, &target
->wc
));
808 static struct cls_rule
*
809 search_table(const struct cls_table
*table
, const struct cls_rule
*target
)
811 if (!target
|| !flow_wildcards_has_extra(&table
->wc
, &target
->wc
)) {
812 struct cls_rule
*rule
;
814 HMAP_FOR_EACH (rule
, hmap_node
, &table
->rules
) {
815 if (rule_matches(rule
, target
)) {
823 /* Initializes 'cursor' for iterating through 'cls' rules that exactly match
824 * 'target' or are more specific than 'target'. That is, a given 'rule'
825 * matches 'target' if, for every field:
827 * - 'target' and 'rule' specify the same (non-wildcarded) value for the
830 * - 'target' wildcards the field,
834 * - 'target' and 'rule' specify different values for the field, or
836 * - 'target' specifies a value for the field but 'rule' wildcards it.
838 * Equivalently, the truth table for whether a field matches is:
843 * +---------+---------+
844 * t wild | yes | yes |
846 * r +---------+---------+
847 * g exact | no |if values|
849 * t +---------+---------+
851 * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
852 * commands and by OpenFlow 1.0 aggregate and flow stats.
854 * Ignores target->priority.
856 * 'target' may be NULL to iterate over every rule in 'cls'. */
858 cls_cursor_init(struct cls_cursor
*cursor
, const struct classifier
*cls
,
859 const struct cls_rule
*target
)
862 cursor
->target
= target
;
865 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
866 * pointer if there are no matches. */
868 cls_cursor_first(struct cls_cursor
*cursor
)
870 struct cls_table
*table
;
872 for (table
= classifier_first_table(cursor
->cls
); table
;
873 table
= classifier_next_table(cursor
->cls
, table
)) {
874 struct cls_rule
*rule
= search_table(table
, cursor
->target
);
876 cursor
->table
= table
;
884 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
885 * pointer if there are no more matches. */
887 cls_cursor_next(struct cls_cursor
*cursor
, struct cls_rule
*rule
)
889 const struct cls_table
*table
;
890 struct cls_rule
*next
;
892 next
= next_rule_in_list__(rule
);
893 if (next
->priority
< rule
->priority
) {
897 /* 'next' is the head of the list, that is, the rule that is included in
898 * the table's hmap. (This is important when the classifier contains rules
899 * that differ only in priority.) */
901 HMAP_FOR_EACH_CONTINUE (rule
, hmap_node
, &cursor
->table
->rules
) {
902 if (rule_matches(rule
, cursor
->target
)) {
907 for (table
= classifier_next_table(cursor
->cls
, cursor
->table
); table
;
908 table
= classifier_next_table(cursor
->cls
, table
)) {
909 rule
= search_table(table
, cursor
->target
);
911 cursor
->table
= table
;
919 static struct cls_table
*
920 find_table(const struct classifier
*cls
, const struct flow_wildcards
*wc
)
922 struct cls_table
*table
;
924 HMAP_FOR_EACH_IN_BUCKET (table
, hmap_node
, flow_wildcards_hash(wc
),
926 if (flow_wildcards_equal(wc
, &table
->wc
)) {
933 static struct cls_table
*
934 insert_table(struct classifier
*cls
, const struct flow_wildcards
*wc
)
936 struct cls_table
*table
;
938 table
= xzalloc(sizeof *table
);
939 hmap_init(&table
->rules
);
941 hmap_insert(&cls
->tables
, &table
->hmap_node
, flow_wildcards_hash(wc
));
946 static struct cls_table
*
947 classifier_first_table(const struct classifier
*cls
)
949 return cls_table_from_hmap_node(hmap_first(&cls
->tables
));
952 static struct cls_table
*
953 classifier_next_table(const struct classifier
*cls
,
954 const struct cls_table
*table
)
956 return cls_table_from_hmap_node(hmap_next(&cls
->tables
,
961 destroy_table(struct classifier
*cls
, struct cls_table
*table
)
963 hmap_remove(&cls
->tables
, &table
->hmap_node
);
964 hmap_destroy(&table
->rules
);
968 static struct cls_rule
*
969 find_match(const struct cls_table
*table
, const struct flow
*flow
)
971 struct cls_rule
*rule
;
975 zero_wildcards(&f
, &table
->wc
);
976 HMAP_FOR_EACH_WITH_HASH (rule
, hmap_node
, flow_hash(&f
, 0),
978 if (flow_equal(&f
, &rule
->flow
)) {
985 static struct cls_rule
*
986 find_equal(struct cls_table
*table
, const struct flow
*flow
, uint32_t hash
)
988 struct cls_rule
*head
;
990 HMAP_FOR_EACH_WITH_HASH (head
, hmap_node
, hash
, &table
->rules
) {
991 if (flow_equal(&head
->flow
, flow
)) {
998 static struct cls_rule
*
999 insert_rule(struct cls_table
*table
, struct cls_rule
*new)
1001 struct cls_rule
*head
;
1003 new->hmap_node
.hash
= flow_hash(&new->flow
, 0);
1005 head
= find_equal(table
, &new->flow
, new->hmap_node
.hash
);
1007 hmap_insert(&table
->rules
, &new->hmap_node
, new->hmap_node
.hash
);
1008 list_init(&new->list
);
1011 /* Scan the list for the insertion point that will keep the list in
1012 * order of decreasing priority. */
1013 struct cls_rule
*rule
;
1014 FOR_EACH_RULE_IN_LIST (rule
, head
) {
1015 if (new->priority
>= rule
->priority
) {
1017 /* 'new' is the new highest-priority flow in the list. */
1018 hmap_replace(&table
->rules
,
1019 &rule
->hmap_node
, &new->hmap_node
);
1022 if (new->priority
== rule
->priority
) {
1023 list_replace(&new->list
, &rule
->list
);
1026 list_insert(&rule
->list
, &new->list
);
1032 /* Insert 'new' at the end of the list. */
1033 list_push_back(&head
->list
, &new->list
);
1038 static struct cls_rule
*
1039 next_rule_in_list__(struct cls_rule
*rule
)
1041 struct cls_rule
*next
= OBJECT_CONTAINING(rule
->list
.next
, next
, list
);
1045 static struct cls_rule
*
1046 next_rule_in_list(struct cls_rule
*rule
)
1048 struct cls_rule
*next
= next_rule_in_list__(rule
);
1049 return next
->priority
< rule
->priority
? next
: NULL
;
1053 ipv6_equal_except(const struct in6_addr
*a
, const struct in6_addr
*b
,
1054 const struct in6_addr
*mask
)
1059 for (i
=0; i
<4; i
++) {
1060 if ((a
->s6_addr32
[i
] ^ b
->s6_addr32
[i
]) & mask
->s6_addr32
[i
]) {
1065 for (i
=0; i
<16; i
++) {
1066 if ((a
->s6_addr
[i
] ^ b
->s6_addr
[i
]) & mask
->s6_addr
[i
]) {
1077 flow_equal_except(const struct flow
*a
, const struct flow
*b
,
1078 const struct flow_wildcards
*wildcards
)
1080 const flow_wildcards_t wc
= wildcards
->wildcards
;
1083 BUILD_ASSERT_DECL(FLOW_SIG_SIZE
== 84 + FLOW_N_REGS
* 4);
1085 for (i
= 0; i
< FLOW_N_REGS
; i
++) {
1086 if ((a
->regs
[i
] ^ b
->regs
[i
]) & wildcards
->reg_masks
[i
]) {
1091 return (!((a
->tun_id
^ b
->tun_id
) & wildcards
->tun_id_mask
)
1092 && !((a
->nw_src
^ b
->nw_src
) & wildcards
->nw_src_mask
)
1093 && !((a
->nw_dst
^ b
->nw_dst
) & wildcards
->nw_dst_mask
)
1094 && (wc
& FWW_IN_PORT
|| a
->in_port
== b
->in_port
)
1095 && !((a
->vlan_tci
^ b
->vlan_tci
) & wildcards
->vlan_tci_mask
)
1096 && (wc
& FWW_DL_TYPE
|| a
->dl_type
== b
->dl_type
)
1097 && (wc
& FWW_TP_SRC
|| a
->tp_src
== b
->tp_src
)
1098 && (wc
& FWW_TP_DST
|| a
->tp_dst
== b
->tp_dst
)
1099 && (wc
& FWW_DL_SRC
|| eth_addr_equals(a
->dl_src
, b
->dl_src
))
1101 || (!((a
->dl_dst
[0] ^ b
->dl_dst
[0]) & 0xfe)
1102 && a
->dl_dst
[1] == b
->dl_dst
[1]
1103 && a
->dl_dst
[2] == b
->dl_dst
[2]
1104 && a
->dl_dst
[3] == b
->dl_dst
[3]
1105 && a
->dl_dst
[4] == b
->dl_dst
[4]
1106 && a
->dl_dst
[5] == b
->dl_dst
[5]))
1107 && (wc
& FWW_ETH_MCAST
1108 || !((a
->dl_dst
[0] ^ b
->dl_dst
[0]) & 0x01))
1109 && (wc
& FWW_NW_PROTO
|| a
->nw_proto
== b
->nw_proto
)
1110 && (wc
& FWW_NW_TOS
|| a
->nw_tos
== b
->nw_tos
)
1111 && (wc
& FWW_ARP_SHA
|| eth_addr_equals(a
->arp_sha
, b
->arp_sha
))
1112 && (wc
& FWW_ARP_THA
|| eth_addr_equals(a
->arp_tha
, b
->arp_tha
))
1113 && ipv6_equal_except(&a
->ipv6_src
, &b
->ipv6_src
,
1114 &wildcards
->ipv6_src_mask
)
1115 && ipv6_equal_except(&a
->ipv6_dst
, &b
->ipv6_dst
,
1116 &wildcards
->ipv6_dst_mask
));
1120 zero_wildcards(struct flow
*flow
, const struct flow_wildcards
*wildcards
)
1122 const flow_wildcards_t wc
= wildcards
->wildcards
;
1125 BUILD_ASSERT_DECL(FLOW_SIG_SIZE
== 84 + 4 * FLOW_N_REGS
);
1127 for (i
= 0; i
< FLOW_N_REGS
; i
++) {
1128 flow
->regs
[i
] &= wildcards
->reg_masks
[i
];
1130 flow
->tun_id
&= wildcards
->tun_id_mask
;
1131 flow
->nw_src
&= wildcards
->nw_src_mask
;
1132 flow
->nw_dst
&= wildcards
->nw_dst_mask
;
1133 if (wc
& FWW_IN_PORT
) {
1136 flow
->vlan_tci
&= wildcards
->vlan_tci_mask
;
1137 if (wc
& FWW_DL_TYPE
) {
1140 if (wc
& FWW_TP_SRC
) {
1143 if (wc
& FWW_TP_DST
) {
1146 if (wc
& FWW_DL_SRC
) {
1147 memset(flow
->dl_src
, 0, sizeof flow
->dl_src
);
1149 if (wc
& FWW_DL_DST
) {
1150 flow
->dl_dst
[0] &= 0x01;
1151 memset(&flow
->dl_dst
[1], 0, 5);
1153 if (wc
& FWW_ETH_MCAST
) {
1154 flow
->dl_dst
[0] &= 0xfe;
1156 if (wc
& FWW_NW_PROTO
) {
1159 if (wc
& FWW_NW_TOS
) {
1162 if (wc
& FWW_ARP_SHA
) {
1163 memset(flow
->arp_sha
, 0, sizeof flow
->arp_sha
);
1165 if (wc
& FWW_ARP_THA
) {
1166 memset(flow
->arp_tha
, 0, sizeof flow
->arp_tha
);
1168 flow
->ipv6_src
= ipv6_addr_bitand(&flow
->ipv6_src
,
1169 &wildcards
->ipv6_src_mask
);
1170 flow
->ipv6_dst
= ipv6_addr_bitand(&flow
->ipv6_dst
,
1171 &wildcards
->ipv6_dst_mask
);