Implement new fragment handling policy.
[openvswitch] / lib / flow.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks.
3  *
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:
7  *
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.
15  */
16 #include <config.h>
17 #include <sys/types.h>
18 #include "flow.h"
19 #include <assert.h>
20 #include <errno.h>
21 #include <inttypes.h>
22 #include <netinet/in.h>
23 #include <netinet/icmp6.h>
24 #include <netinet/ip6.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include "byte-order.h"
28 #include "coverage.h"
29 #include "dynamic-string.h"
30 #include "hash.h"
31 #include "ofpbuf.h"
32 #include "openflow/openflow.h"
33 #include "packets.h"
34 #include "unaligned.h"
35 #include "vlog.h"
36
37 VLOG_DEFINE_THIS_MODULE(flow);
38
39 COVERAGE_DEFINE(flow_extract);
40
41 static struct arp_eth_header *
42 pull_arp(struct ofpbuf *packet)
43 {
44     return ofpbuf_try_pull(packet, ARP_ETH_HEADER_LEN);
45 }
46
47 static struct ip_header *
48 pull_ip(struct ofpbuf *packet)
49 {
50     if (packet->size >= IP_HEADER_LEN) {
51         struct ip_header *ip = packet->data;
52         int ip_len = IP_IHL(ip->ip_ihl_ver) * 4;
53         if (ip_len >= IP_HEADER_LEN && packet->size >= ip_len) {
54             return ofpbuf_pull(packet, ip_len);
55         }
56     }
57     return NULL;
58 }
59
60 static struct tcp_header *
61 pull_tcp(struct ofpbuf *packet)
62 {
63     if (packet->size >= TCP_HEADER_LEN) {
64         struct tcp_header *tcp = packet->data;
65         int tcp_len = TCP_OFFSET(tcp->tcp_ctl) * 4;
66         if (tcp_len >= TCP_HEADER_LEN && packet->size >= tcp_len) {
67             return ofpbuf_pull(packet, tcp_len);
68         }
69     }
70     return NULL;
71 }
72
73 static struct udp_header *
74 pull_udp(struct ofpbuf *packet)
75 {
76     return ofpbuf_try_pull(packet, UDP_HEADER_LEN);
77 }
78
79 static struct icmp_header *
80 pull_icmp(struct ofpbuf *packet)
81 {
82     return ofpbuf_try_pull(packet, ICMP_HEADER_LEN);
83 }
84
85 static struct icmp6_hdr *
86 pull_icmpv6(struct ofpbuf *packet)
87 {
88     return ofpbuf_try_pull(packet, sizeof(struct icmp6_hdr));
89 }
90
91 static void
92 parse_vlan(struct ofpbuf *b, struct flow *flow)
93 {
94     struct qtag_prefix {
95         ovs_be16 eth_type;      /* ETH_TYPE_VLAN */
96         ovs_be16 tci;
97     };
98
99     if (b->size >= sizeof(struct qtag_prefix) + sizeof(ovs_be16)) {
100         struct qtag_prefix *qp = ofpbuf_pull(b, sizeof *qp);
101         flow->vlan_tci = qp->tci | htons(VLAN_CFI);
102     }
103 }
104
105 static ovs_be16
106 parse_ethertype(struct ofpbuf *b)
107 {
108     struct llc_snap_header *llc;
109     ovs_be16 proto;
110
111     proto = *(ovs_be16 *) ofpbuf_pull(b, sizeof proto);
112     if (ntohs(proto) >= ETH_TYPE_MIN) {
113         return proto;
114     }
115
116     if (b->size < sizeof *llc) {
117         return htons(FLOW_DL_TYPE_NONE);
118     }
119
120     llc = b->data;
121     if (llc->llc.llc_dsap != LLC_DSAP_SNAP
122         || llc->llc.llc_ssap != LLC_SSAP_SNAP
123         || llc->llc.llc_cntl != LLC_CNTL_SNAP
124         || memcmp(llc->snap.snap_org, SNAP_ORG_ETHERNET,
125                   sizeof llc->snap.snap_org)) {
126         return htons(FLOW_DL_TYPE_NONE);
127     }
128
129     ofpbuf_pull(b, sizeof *llc);
130     return llc->snap.snap_type;
131 }
132
133 static int
134 parse_ipv6(struct ofpbuf *packet, struct flow *flow)
135 {
136     const struct ip6_hdr *nh;
137     ovs_be32 tc_flow;
138     int nexthdr;
139
140     nh = ofpbuf_try_pull(packet, sizeof *nh);
141     if (!nh) {
142         return EINVAL;
143     }
144
145     nexthdr = nh->ip6_nxt;
146
147     flow->ipv6_src = nh->ip6_src;
148     flow->ipv6_dst = nh->ip6_dst;
149
150     tc_flow = get_unaligned_be32(&nh->ip6_flow);
151     flow->tos_frag = (ntohl(tc_flow) >> 4) & IP_DSCP_MASK;
152     flow->nw_proto = IPPROTO_NONE;
153
154     while (1) {
155         if ((nexthdr != IPPROTO_HOPOPTS)
156                 && (nexthdr != IPPROTO_ROUTING)
157                 && (nexthdr != IPPROTO_DSTOPTS)
158                 && (nexthdr != IPPROTO_AH)
159                 && (nexthdr != IPPROTO_FRAGMENT)) {
160             /* It's either a terminal header (e.g., TCP, UDP) or one we
161              * don't understand.  In either case, we're done with the
162              * packet, so use it to fill in 'nw_proto'. */
163             break;
164         }
165
166         /* We only verify that at least 8 bytes of the next header are
167          * available, but many of these headers are longer.  Ensure that
168          * accesses within the extension header are within those first 8
169          * bytes. All extension headers are required to be at least 8
170          * bytes. */
171         if (packet->size < 8) {
172             return EINVAL;
173         }
174
175         if ((nexthdr == IPPROTO_HOPOPTS)
176                 || (nexthdr == IPPROTO_ROUTING)
177                 || (nexthdr == IPPROTO_DSTOPTS)) {
178             /* These headers, while different, have the fields we care about
179              * in the same location and with the same interpretation. */
180             const struct ip6_ext *ext_hdr = (struct ip6_ext *)packet->data;
181             nexthdr = ext_hdr->ip6e_nxt;
182             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 1) * 8)) {
183                 return EINVAL;
184             }
185         } else if (nexthdr == IPPROTO_AH) {
186             /* A standard AH definition isn't available, but the fields
187              * we care about are in the same location as the generic
188              * option header--only the header length is calculated
189              * differently. */
190             const struct ip6_ext *ext_hdr = (struct ip6_ext *)packet->data;
191             nexthdr = ext_hdr->ip6e_nxt;
192             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 2) * 4)) {
193                return EINVAL;
194             }
195         } else if (nexthdr == IPPROTO_FRAGMENT) {
196             const struct ip6_frag *frag_hdr = (struct ip6_frag *)packet->data;
197
198             nexthdr = frag_hdr->ip6f_nxt;
199             if (!ofpbuf_try_pull(packet, sizeof *frag_hdr)) {
200                 return EINVAL;
201             }
202
203             /* We only process the first fragment. */
204             flow->tos_frag &= ~FLOW_FRAG_MASK;
205             flow->tos_frag |= FLOW_FRAG_ANY;
206             if ((frag_hdr->ip6f_offlg & IP6F_OFF_MASK) != htons(0)) {
207                 flow->tos_frag |= FLOW_FRAG_LATER;
208                 nexthdr = IPPROTO_FRAGMENT;
209                 break;
210             }
211         }
212     }
213
214     flow->nw_proto = nexthdr;
215     return 0;
216 }
217
218 static void
219 parse_tcp(struct ofpbuf *packet, struct ofpbuf *b, struct flow *flow)
220 {
221     const struct tcp_header *tcp = pull_tcp(b);
222     if (tcp) {
223         flow->tp_src = tcp->tcp_src;
224         flow->tp_dst = tcp->tcp_dst;
225         packet->l7 = b->data;
226     }
227 }
228
229 static void
230 parse_udp(struct ofpbuf *packet, struct ofpbuf *b, struct flow *flow)
231 {
232     const struct udp_header *udp = pull_udp(b);
233     if (udp) {
234         flow->tp_src = udp->udp_src;
235         flow->tp_dst = udp->udp_dst;
236         packet->l7 = b->data;
237     }
238 }
239
240 static bool
241 parse_icmpv6(struct ofpbuf *b, struct flow *flow)
242 {
243     const struct icmp6_hdr *icmp = pull_icmpv6(b);
244
245     if (!icmp) {
246         return false;
247     }
248
249     /* The ICMPv6 type and code fields use the 16-bit transport port
250      * fields, so we need to store them in 16-bit network byte order. */
251     flow->tp_src = htons(icmp->icmp6_type);
252     flow->tp_dst = htons(icmp->icmp6_code);
253
254     if (icmp->icmp6_code == 0 &&
255         (icmp->icmp6_type == ND_NEIGHBOR_SOLICIT ||
256          icmp->icmp6_type == ND_NEIGHBOR_ADVERT)) {
257         const struct in6_addr *nd_target;
258
259         nd_target = ofpbuf_try_pull(b, sizeof *nd_target);
260         if (!nd_target) {
261             return false;
262         }
263         flow->nd_target = *nd_target;
264
265         while (b->size >= 8) {
266             /* The minimum size of an option is 8 bytes, which also is
267              * the size of Ethernet link-layer options. */
268             const struct nd_opt_hdr *nd_opt = b->data;
269             int opt_len = nd_opt->nd_opt_len * 8;
270
271             if (!opt_len || opt_len > b->size) {
272                 goto invalid;
273             }
274
275             /* Store the link layer address if the appropriate option is
276              * provided.  It is considered an error if the same link
277              * layer option is specified twice. */
278             if (nd_opt->nd_opt_type == ND_OPT_SOURCE_LINKADDR
279                     && opt_len == 8) {
280                 if (eth_addr_is_zero(flow->arp_sha)) {
281                     memcpy(flow->arp_sha, nd_opt + 1, ETH_ADDR_LEN);
282                 } else {
283                     goto invalid;
284                 }
285             } else if (nd_opt->nd_opt_type == ND_OPT_TARGET_LINKADDR
286                     && opt_len == 8) {
287                 if (eth_addr_is_zero(flow->arp_tha)) {
288                     memcpy(flow->arp_tha, nd_opt + 1, ETH_ADDR_LEN);
289                 } else {
290                     goto invalid;
291                 }
292             }
293
294             if (!ofpbuf_try_pull(b, opt_len)) {
295                 goto invalid;
296             }
297         }
298     }
299
300     return true;
301
302 invalid:
303     memset(&flow->nd_target, 0, sizeof(flow->nd_target));
304     memset(flow->arp_sha, 0, sizeof(flow->arp_sha));
305     memset(flow->arp_tha, 0, sizeof(flow->arp_tha));
306
307     return false;
308
309 }
310
311 /* Initializes 'flow' members from 'packet', 'tun_id', and 'ofp_in_port'.
312  * Initializes 'packet' header pointers as follows:
313  *
314  *    - packet->l2 to the start of the Ethernet header.
315  *
316  *    - packet->l3 to just past the Ethernet header, or just past the
317  *      vlan_header if one is present, to the first byte of the payload of the
318  *      Ethernet frame.
319  *
320  *    - packet->l4 to just past the IPv4 header, if one is present and has a
321  *      correct length, and otherwise NULL.
322  *
323  *    - packet->l7 to just past the TCP or UDP or ICMP header, if one is
324  *      present and has a correct length, and otherwise NULL.
325  */
326 void
327 flow_extract(struct ofpbuf *packet, ovs_be64 tun_id, uint16_t ofp_in_port,
328              struct flow *flow)
329 {
330     struct ofpbuf b = *packet;
331     struct eth_header *eth;
332
333     COVERAGE_INC(flow_extract);
334
335     memset(flow, 0, sizeof *flow);
336     flow->tun_id = tun_id;
337     flow->in_port = ofp_in_port;
338
339     packet->l2 = b.data;
340     packet->l3 = NULL;
341     packet->l4 = NULL;
342     packet->l7 = NULL;
343
344     if (b.size < sizeof *eth) {
345         return;
346     }
347
348     /* Link layer. */
349     eth = b.data;
350     memcpy(flow->dl_src, eth->eth_src, ETH_ADDR_LEN);
351     memcpy(flow->dl_dst, eth->eth_dst, ETH_ADDR_LEN);
352
353     /* dl_type, vlan_tci. */
354     ofpbuf_pull(&b, ETH_ADDR_LEN * 2);
355     if (eth->eth_type == htons(ETH_TYPE_VLAN)) {
356         parse_vlan(&b, flow);
357     }
358     flow->dl_type = parse_ethertype(&b);
359
360     /* Network layer. */
361     packet->l3 = b.data;
362     if (flow->dl_type == htons(ETH_TYPE_IP)) {
363         const struct ip_header *nh = pull_ip(&b);
364         if (nh) {
365             packet->l4 = b.data;
366
367             flow->nw_src = get_unaligned_be32(&nh->ip_src);
368             flow->nw_dst = get_unaligned_be32(&nh->ip_dst);
369             flow->nw_proto = nh->ip_proto;
370
371             flow->tos_frag = nh->ip_tos & IP_DSCP_MASK;
372             if (IP_IS_FRAGMENT(nh->ip_frag_off)) {
373                 flow->tos_frag |= FLOW_FRAG_ANY;
374                 if (nh->ip_frag_off & htons(IP_FRAG_OFF_MASK)) {
375                     flow->tos_frag |= FLOW_FRAG_LATER;
376                 }
377             }
378
379             if (!(nh->ip_frag_off & htons(IP_FRAG_OFF_MASK))) {
380                 if (flow->nw_proto == IPPROTO_TCP) {
381                     parse_tcp(packet, &b, flow);
382                 } else if (flow->nw_proto == IPPROTO_UDP) {
383                     parse_udp(packet, &b, flow);
384                 } else if (flow->nw_proto == IPPROTO_ICMP) {
385                     const struct icmp_header *icmp = pull_icmp(&b);
386                     if (icmp) {
387                         flow->tp_src = htons(icmp->icmp_type);
388                         flow->tp_dst = htons(icmp->icmp_code);
389                         packet->l7 = b.data;
390                     }
391                 }
392             }
393         }
394     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
395         if (parse_ipv6(&b, flow)) {
396             return;
397         }
398
399         packet->l4 = b.data;
400         if (flow->nw_proto == IPPROTO_TCP) {
401             parse_tcp(packet, &b, flow);
402         } else if (flow->nw_proto == IPPROTO_UDP) {
403             parse_udp(packet, &b, flow);
404         } else if (flow->nw_proto == IPPROTO_ICMPV6) {
405             if (parse_icmpv6(&b, flow)) {
406                 packet->l7 = b.data;
407             }
408         }
409     } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
410         const struct arp_eth_header *arp = pull_arp(&b);
411         if (arp && arp->ar_hrd == htons(1)
412             && arp->ar_pro == htons(ETH_TYPE_IP)
413             && arp->ar_hln == ETH_ADDR_LEN
414             && arp->ar_pln == 4) {
415             /* We only match on the lower 8 bits of the opcode. */
416             if (ntohs(arp->ar_op) <= 0xff) {
417                 flow->nw_proto = ntohs(arp->ar_op);
418             }
419
420             if ((flow->nw_proto == ARP_OP_REQUEST)
421                 || (flow->nw_proto == ARP_OP_REPLY)) {
422                 flow->nw_src = arp->ar_spa;
423                 flow->nw_dst = arp->ar_tpa;
424                 memcpy(flow->arp_sha, arp->ar_sha, ETH_ADDR_LEN);
425                 memcpy(flow->arp_tha, arp->ar_tha, ETH_ADDR_LEN);
426             }
427         }
428     }
429 }
430
431 /* For every bit of a field that is wildcarded in 'wildcards', sets the
432  * corresponding bit in 'flow' to zero. */
433 void
434 flow_zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards)
435 {
436     const flow_wildcards_t wc = wildcards->wildcards;
437     int i;
438
439     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 3);
440
441     for (i = 0; i < FLOW_N_REGS; i++) {
442         flow->regs[i] &= wildcards->reg_masks[i];
443     }
444     flow->tun_id &= wildcards->tun_id_mask;
445     flow->nw_src &= wildcards->nw_src_mask;
446     flow->nw_dst &= wildcards->nw_dst_mask;
447     if (wc & FWW_IN_PORT) {
448         flow->in_port = 0;
449     }
450     flow->vlan_tci &= wildcards->vlan_tci_mask;
451     if (wc & FWW_DL_TYPE) {
452         flow->dl_type = 0;
453     }
454     if (wc & FWW_TP_SRC) {
455         flow->tp_src = 0;
456     }
457     if (wc & FWW_TP_DST) {
458         flow->tp_dst = 0;
459     }
460     if (wc & FWW_DL_SRC) {
461         memset(flow->dl_src, 0, sizeof flow->dl_src);
462     }
463     if (wc & FWW_DL_DST) {
464         flow->dl_dst[0] &= 0x01;
465         memset(&flow->dl_dst[1], 0, 5);
466     }
467     if (wc & FWW_ETH_MCAST) {
468         flow->dl_dst[0] &= 0xfe;
469     }
470     if (wc & FWW_NW_PROTO) {
471         flow->nw_proto = 0;
472     }
473     flow->tos_frag &= wildcards->tos_frag_mask;
474     if (wc & FWW_ARP_SHA) {
475         memset(flow->arp_sha, 0, sizeof flow->arp_sha);
476     }
477     if (wc & FWW_ARP_THA) {
478         memset(flow->arp_tha, 0, sizeof flow->arp_tha);
479     }
480     flow->ipv6_src = ipv6_addr_bitand(&flow->ipv6_src,
481             &wildcards->ipv6_src_mask);
482     flow->ipv6_dst = ipv6_addr_bitand(&flow->ipv6_dst,
483             &wildcards->ipv6_dst_mask);
484     if (wc & FWW_ND_TARGET) {
485         memset(&flow->nd_target, 0, sizeof flow->nd_target);
486     }
487 }
488
489 char *
490 flow_to_string(const struct flow *flow)
491 {
492     struct ds ds = DS_EMPTY_INITIALIZER;
493     flow_format(&ds, flow);
494     return ds_cstr(&ds);
495 }
496
497 void
498 flow_format(struct ds *ds, const struct flow *flow)
499 {
500     int frag;
501
502     ds_put_format(ds, "tunnel%#"PRIx64":in_port%04"PRIx16":tci(",
503                   ntohll(flow->tun_id), flow->in_port);
504     if (flow->vlan_tci) {
505         ds_put_format(ds, "vlan%"PRIu16",pcp%d",
506                       vlan_tci_to_vid(flow->vlan_tci),
507                       vlan_tci_to_pcp(flow->vlan_tci));
508     } else {
509         ds_put_char(ds, '0');
510     }
511     ds_put_format(ds, ") mac"ETH_ADDR_FMT"->"ETH_ADDR_FMT
512                       " type%04"PRIx16,
513                   ETH_ADDR_ARGS(flow->dl_src),
514                   ETH_ADDR_ARGS(flow->dl_dst),
515                   ntohs(flow->dl_type));
516
517     if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
518         ds_put_format(ds, " proto%"PRIu8" tos%"PRIu8" ipv6",
519                       flow->nw_proto, flow->tos_frag & IP_DSCP_MASK);
520         print_ipv6_addr(ds, &flow->ipv6_src);
521         ds_put_cstr(ds, "->");
522         print_ipv6_addr(ds, &flow->ipv6_dst);
523
524     } else {
525         ds_put_format(ds, " proto%"PRIu8
526                           " tos%"PRIu8
527                           " ip"IP_FMT"->"IP_FMT,
528                       flow->nw_proto,
529                       flow->tos_frag & IP_DSCP_MASK,
530                       IP_ARGS(&flow->nw_src),
531                       IP_ARGS(&flow->nw_dst));
532     }
533     frag = flow->tos_frag & FLOW_FRAG_MASK;
534     if (frag) {
535         ds_put_format(ds, " frag(%s)",
536                       frag == FLOW_FRAG_ANY ? "first"
537                       : frag == (FLOW_FRAG_ANY | FLOW_FRAG_LATER) ? "later"
538                       : "<error>");
539     }
540     if (flow->tp_src || flow->tp_dst) {
541         ds_put_format(ds, " port%"PRIu16"->%"PRIu16,
542                 ntohs(flow->tp_src), ntohs(flow->tp_dst));
543     }
544     if (!eth_addr_is_zero(flow->arp_sha) || !eth_addr_is_zero(flow->arp_tha)) {
545         ds_put_format(ds, " arp_ha"ETH_ADDR_FMT"->"ETH_ADDR_FMT,
546                 ETH_ADDR_ARGS(flow->arp_sha),
547                 ETH_ADDR_ARGS(flow->arp_tha));
548     }
549 }
550
551 void
552 flow_print(FILE *stream, const struct flow *flow)
553 {
554     char *s = flow_to_string(flow);
555     fputs(s, stream);
556     free(s);
557 }
558 \f
559 /* flow_wildcards functions. */
560
561 /* Initializes 'wc' as a set of wildcards that matches every packet. */
562 void
563 flow_wildcards_init_catchall(struct flow_wildcards *wc)
564 {
565     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 3);
566
567     wc->wildcards = FWW_ALL;
568     wc->tun_id_mask = htonll(0);
569     wc->nw_src_mask = htonl(0);
570     wc->nw_dst_mask = htonl(0);
571     wc->ipv6_src_mask = in6addr_any;
572     wc->ipv6_dst_mask = in6addr_any;
573     memset(wc->reg_masks, 0, sizeof wc->reg_masks);
574     wc->vlan_tci_mask = htons(0);
575     wc->tos_frag_mask = 0;
576     memset(wc->zeros, 0, sizeof wc->zeros);
577 }
578
579 /* Initializes 'wc' as an exact-match set of wildcards; that is, 'wc' does not
580  * wildcard any bits or fields. */
581 void
582 flow_wildcards_init_exact(struct flow_wildcards *wc)
583 {
584     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 3);
585
586     wc->wildcards = 0;
587     wc->tun_id_mask = htonll(UINT64_MAX);
588     wc->nw_src_mask = htonl(UINT32_MAX);
589     wc->nw_dst_mask = htonl(UINT32_MAX);
590     wc->ipv6_src_mask = in6addr_exact;
591     wc->ipv6_dst_mask = in6addr_exact;
592     memset(wc->reg_masks, 0xff, sizeof wc->reg_masks);
593     wc->vlan_tci_mask = htons(UINT16_MAX);
594     wc->tos_frag_mask = UINT8_MAX;
595     memset(wc->zeros, 0, sizeof wc->zeros);
596 }
597
598 /* Returns true if 'wc' is exact-match, false if 'wc' wildcards any bits or
599  * fields. */
600 bool
601 flow_wildcards_is_exact(const struct flow_wildcards *wc)
602 {
603     int i;
604
605     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 3);
606
607     if (wc->wildcards
608         || wc->tun_id_mask != htonll(UINT64_MAX)
609         || wc->nw_src_mask != htonl(UINT32_MAX)
610         || wc->nw_dst_mask != htonl(UINT32_MAX)
611         || wc->vlan_tci_mask != htons(UINT16_MAX)
612         || !ipv6_mask_is_exact(&wc->ipv6_src_mask)
613         || !ipv6_mask_is_exact(&wc->ipv6_dst_mask)
614         || wc->tos_frag_mask != UINT8_MAX) {
615         return false;
616     }
617
618     for (i = 0; i < FLOW_N_REGS; i++) {
619         if (wc->reg_masks[i] != UINT32_MAX) {
620             return false;
621         }
622     }
623
624     return true;
625 }
626
627 /* Returns true if 'wc' matches every packet, false if 'wc' fixes any bits or
628  * fields. */
629 bool
630 flow_wildcards_is_catchall(const struct flow_wildcards *wc)
631 {
632     int i;
633
634     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 3);
635
636     if (wc->wildcards != FWW_ALL
637         || wc->tun_id_mask != htonll(0)
638         || wc->nw_src_mask != htonl(0)
639         || wc->nw_dst_mask != htonl(0)
640         || wc->vlan_tci_mask != htons(0)
641         || !ipv6_mask_is_any(&wc->ipv6_src_mask)
642         || !ipv6_mask_is_any(&wc->ipv6_dst_mask)
643         || wc->tos_frag_mask != 0) {
644         return false;
645     }
646
647     for (i = 0; i < FLOW_N_REGS; i++) {
648         if (wc->reg_masks[i] != 0) {
649             return false;
650         }
651     }
652
653     return true;
654 }
655
656 /* Initializes 'dst' as the combination of wildcards in 'src1' and 'src2'.
657  * That is, a bit or a field is wildcarded in 'dst' if it is wildcarded in
658  * 'src1' or 'src2' or both.  */
659 void
660 flow_wildcards_combine(struct flow_wildcards *dst,
661                        const struct flow_wildcards *src1,
662                        const struct flow_wildcards *src2)
663 {
664     int i;
665
666     dst->wildcards = src1->wildcards | src2->wildcards;
667     dst->tun_id_mask = src1->tun_id_mask & src2->tun_id_mask;
668     dst->nw_src_mask = src1->nw_src_mask & src2->nw_src_mask;
669     dst->nw_dst_mask = src1->nw_dst_mask & src2->nw_dst_mask;
670     dst->ipv6_src_mask = ipv6_addr_bitand(&src1->ipv6_src_mask,
671                                         &src2->ipv6_src_mask);
672     dst->ipv6_dst_mask = ipv6_addr_bitand(&src1->ipv6_dst_mask,
673                                         &src2->ipv6_dst_mask);
674     for (i = 0; i < FLOW_N_REGS; i++) {
675         dst->reg_masks[i] = src1->reg_masks[i] & src2->reg_masks[i];
676     }
677     dst->vlan_tci_mask = src1->vlan_tci_mask & src2->vlan_tci_mask;
678 }
679
680 /* Returns a hash of the wildcards in 'wc'. */
681 uint32_t
682 flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis)
683 {
684     /* If you change struct flow_wildcards and thereby trigger this
685      * assertion, please check that the new struct flow_wildcards has no holes
686      * in it before you update the assertion. */
687     BUILD_ASSERT_DECL(sizeof *wc == 60 + FLOW_N_REGS * 4);
688     return hash_bytes(wc, sizeof *wc, basis);
689 }
690
691 /* Returns true if 'a' and 'b' represent the same wildcards, false if they are
692  * different. */
693 bool
694 flow_wildcards_equal(const struct flow_wildcards *a,
695                      const struct flow_wildcards *b)
696 {
697     int i;
698
699     if (a->wildcards != b->wildcards
700         || a->tun_id_mask != b->tun_id_mask
701         || a->nw_src_mask != b->nw_src_mask
702         || a->nw_dst_mask != b->nw_dst_mask
703         || a->vlan_tci_mask != b->vlan_tci_mask
704         || !ipv6_addr_equals(&a->ipv6_src_mask, &b->ipv6_src_mask)
705         || !ipv6_addr_equals(&a->ipv6_dst_mask, &b->ipv6_dst_mask)) {
706         return false;
707     }
708
709     for (i = 0; i < FLOW_N_REGS; i++) {
710         if (a->reg_masks[i] != b->reg_masks[i]) {
711             return false;
712         }
713     }
714
715     return true;
716 }
717
718 /* Returns true if at least one bit or field is wildcarded in 'a' but not in
719  * 'b', false otherwise. */
720 bool
721 flow_wildcards_has_extra(const struct flow_wildcards *a,
722                          const struct flow_wildcards *b)
723 {
724     int i;
725     struct in6_addr ipv6_masked;
726
727     for (i = 0; i < FLOW_N_REGS; i++) {
728         if ((a->reg_masks[i] & b->reg_masks[i]) != b->reg_masks[i]) {
729             return true;
730         }
731     }
732
733     ipv6_masked = ipv6_addr_bitand(&a->ipv6_src_mask, &b->ipv6_src_mask);
734     if (!ipv6_addr_equals(&ipv6_masked, &b->ipv6_src_mask)) {
735         return true;
736     }
737
738     ipv6_masked = ipv6_addr_bitand(&a->ipv6_dst_mask, &b->ipv6_dst_mask);
739     if (!ipv6_addr_equals(&ipv6_masked, &b->ipv6_dst_mask)) {
740         return true;
741     }
742
743     return (a->wildcards & ~b->wildcards
744             || (a->tun_id_mask & b->tun_id_mask) != b->tun_id_mask
745             || (a->nw_src_mask & b->nw_src_mask) != b->nw_src_mask
746             || (a->nw_dst_mask & b->nw_dst_mask) != b->nw_dst_mask
747             || (a->vlan_tci_mask & b->vlan_tci_mask) != b->vlan_tci_mask);
748 }
749
750 static bool
751 set_nw_mask(ovs_be32 *maskp, ovs_be32 mask)
752 {
753     if (ip_is_cidr(mask)) {
754         *maskp = mask;
755         return true;
756     } else {
757         return false;
758     }
759 }
760
761 /* Sets the IP (or ARP) source wildcard mask to CIDR 'mask' (consisting of N
762  * high-order 1-bit and 32-N low-order 0-bits).  Returns true if successful,
763  * false if 'mask' is not a CIDR mask.  */
764 bool
765 flow_wildcards_set_nw_src_mask(struct flow_wildcards *wc, ovs_be32 mask)
766 {
767     return set_nw_mask(&wc->nw_src_mask, mask);
768 }
769
770 /* Sets the IP (or ARP) destination wildcard mask to CIDR 'mask' (consisting of
771  * N high-order 1-bit and 32-N low-order 0-bits).  Returns true if successful,
772  * false if 'mask' is not a CIDR mask.  */
773 bool
774 flow_wildcards_set_nw_dst_mask(struct flow_wildcards *wc, ovs_be32 mask)
775 {
776     return set_nw_mask(&wc->nw_dst_mask, mask);
777 }
778
779 static bool
780 set_ipv6_mask(struct in6_addr *maskp, const struct in6_addr *mask)
781 {
782     if (ipv6_is_cidr(mask)) {
783         *maskp = *mask;
784         return true;
785     } else {
786         return false;
787     }
788 }
789
790 /* Sets the IPv6 source wildcard mask to CIDR 'mask' (consisting of N
791  * high-order 1-bit and 128-N low-order 0-bits).  Returns true if successful,
792  * false if 'mask' is not a CIDR mask.  */
793 bool
794 flow_wildcards_set_ipv6_src_mask(struct flow_wildcards *wc,
795                                  const struct in6_addr *mask)
796 {
797     return set_ipv6_mask(&wc->ipv6_src_mask, mask);
798 }
799
800 /* Sets the IPv6 destination wildcard mask to CIDR 'mask' (consisting of
801  * N high-order 1-bit and 128-N low-order 0-bits).  Returns true if
802  * successful, false if 'mask' is not a CIDR mask.  */
803 bool
804 flow_wildcards_set_ipv6_dst_mask(struct flow_wildcards *wc,
805                                  const struct in6_addr *mask)
806 {
807     return set_ipv6_mask(&wc->ipv6_dst_mask, mask);
808 }
809
810 /* Sets the wildcard mask for register 'idx' in 'wc' to 'mask'.
811  * (A 0-bit indicates a wildcard bit.) */
812 void
813 flow_wildcards_set_reg_mask(struct flow_wildcards *wc, int idx, uint32_t mask)
814 {
815     wc->reg_masks[idx] = mask;
816 }
817
818 /* Returns the wildcard bitmask for the Ethernet destination address
819  * that 'wc' specifies.  The bitmask has a 0 in each bit that is wildcarded
820  * and a 1 in each bit that must match.  */
821 const uint8_t *
822 flow_wildcards_to_dl_dst_mask(flow_wildcards_t wc)
823 {
824     static const uint8_t    no_wild[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
825     static const uint8_t  addr_wild[] = {0x01, 0x00, 0x00, 0x00, 0x00, 0x00};
826     static const uint8_t mcast_wild[] = {0xfe, 0xff, 0xff, 0xff, 0xff, 0xff};
827     static const uint8_t   all_wild[] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
828
829     switch (wc & (FWW_DL_DST | FWW_ETH_MCAST)) {
830     case 0:                             return no_wild;
831     case FWW_DL_DST:                    return addr_wild;
832     case FWW_ETH_MCAST:                 return mcast_wild;
833     case FWW_DL_DST | FWW_ETH_MCAST:    return all_wild;
834     }
835     NOT_REACHED();
836 }
837
838 /* Returns true if 'mask' is a valid wildcard bitmask for the Ethernet
839  * destination address.  Valid bitmasks are either all-bits-0 or all-bits-1,
840  * except that the multicast bit may differ from the rest of the bits.  So,
841  * there are four possible valid bitmasks:
842  *
843  *  - 00:00:00:00:00:00
844  *  - 01:00:00:00:00:00
845  *  - fe:ff:ff:ff:ff:ff
846  *  - ff:ff:ff:ff:ff:ff
847  *
848  * All other bitmasks are invalid. */
849 bool
850 flow_wildcards_is_dl_dst_mask_valid(const uint8_t mask[ETH_ADDR_LEN])
851 {
852     switch (mask[0]) {
853     case 0x00:
854     case 0x01:
855         return (mask[1] | mask[2] | mask[3] | mask[4] | mask[5]) == 0x00;
856
857     case 0xfe:
858     case 0xff:
859         return (mask[1] & mask[2] & mask[3] & mask[4] & mask[5]) == 0xff;
860
861     default:
862         return false;
863     }
864 }
865
866 /* Returns 'wc' with the FWW_DL_DST and FWW_ETH_MCAST bits modified
867  * appropriately to match 'mask'.
868  *
869  * This function will assert-fail if 'mask' is invalid.  Only 'mask' values
870  * accepted by flow_wildcards_is_dl_dst_mask_valid() are allowed. */
871 flow_wildcards_t
872 flow_wildcards_set_dl_dst_mask(flow_wildcards_t wc,
873                                const uint8_t mask[ETH_ADDR_LEN])
874 {
875     assert(flow_wildcards_is_dl_dst_mask_valid(mask));
876
877     switch (mask[0]) {
878     case 0x00:
879         return wc | FWW_DL_DST | FWW_ETH_MCAST;
880
881     case 0x01:
882         return (wc | FWW_DL_DST) & ~FWW_ETH_MCAST;
883
884     case 0xfe:
885         return (wc & ~FWW_DL_DST) | FWW_ETH_MCAST;
886
887     case 0xff:
888         return wc & ~(FWW_DL_DST | FWW_ETH_MCAST);
889
890     default:
891         NOT_REACHED();
892     }
893 }
894
895 /* Hashes 'flow' based on its L2 through L4 protocol information. */
896 uint32_t
897 flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis)
898 {
899     struct {
900         union {
901             ovs_be32 ipv4_addr;
902             struct in6_addr ipv6_addr;
903         };
904         ovs_be16 eth_type;
905         ovs_be16 vlan_tci;
906         ovs_be16 tp_addr;
907         uint8_t eth_addr[ETH_ADDR_LEN];
908         uint8_t ip_proto;
909     } fields;
910
911     int i;
912
913     memset(&fields, 0, sizeof fields);
914     for (i = 0; i < ETH_ADDR_LEN; i++) {
915         fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
916     }
917     fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
918     fields.eth_type = flow->dl_type;
919
920     /* UDP source and destination port are not taken into account because they
921      * will not necessarily be symmetric in a bidirectional flow. */
922     if (fields.eth_type == htons(ETH_TYPE_IP)) {
923         fields.ipv4_addr = flow->nw_src ^ flow->nw_dst;
924         fields.ip_proto = flow->nw_proto;
925         if (fields.ip_proto == IPPROTO_TCP) {
926             fields.tp_addr = flow->tp_src ^ flow->tp_dst;
927         }
928     } else if (fields.eth_type == htons(ETH_TYPE_IPV6)) {
929         const uint8_t *a = &flow->ipv6_src.s6_addr[0];
930         const uint8_t *b = &flow->ipv6_dst.s6_addr[0];
931         uint8_t *ipv6_addr = &fields.ipv6_addr.s6_addr[0];
932
933         for (i=0; i<16; i++) {
934             ipv6_addr[i] = a[i] ^ b[i];
935         }
936         fields.ip_proto = flow->nw_proto;
937         if (fields.ip_proto == IPPROTO_TCP) {
938             fields.tp_addr = flow->tp_src ^ flow->tp_dst;
939         }
940     }
941     return hash_bytes(&fields, sizeof fields, basis);
942 }
943
944 /* Hashes the portions of 'flow' designated by 'fields'. */
945 uint32_t
946 flow_hash_fields(const struct flow *flow, enum nx_hash_fields fields,
947                  uint16_t basis)
948 {
949     switch (fields) {
950
951     case NX_HASH_FIELDS_ETH_SRC:
952         return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
953
954     case NX_HASH_FIELDS_SYMMETRIC_L4:
955         return flow_hash_symmetric_l4(flow, basis);
956     }
957
958     NOT_REACHED();
959 }
960
961 /* Returns a string representation of 'fields'. */
962 const char *
963 flow_hash_fields_to_str(enum nx_hash_fields fields)
964 {
965     switch (fields) {
966     case NX_HASH_FIELDS_ETH_SRC: return "eth_src";
967     case NX_HASH_FIELDS_SYMMETRIC_L4: return "symmetric_l4";
968     default: return "<unknown>";
969     }
970 }
971
972 /* Returns true if the value of 'fields' is supported. Otherwise false. */
973 bool
974 flow_hash_fields_valid(enum nx_hash_fields fields)
975 {
976     return fields == NX_HASH_FIELDS_ETH_SRC
977         || fields == NX_HASH_FIELDS_SYMMETRIC_L4;
978 }
979
980 /* Puts into 'b' a packet that flow_extract() would parse as having the given
981  * 'flow'.
982  *
983  * (This is useful only for testing, obviously, and the packet isn't really
984  * valid.  It hasn't got any checksums filled in, for one, and lots of fields
985  * are just zeroed.) */
986 void
987 flow_compose(struct ofpbuf *b, const struct flow *flow)
988 {
989     eth_compose(b, flow->dl_dst, flow->dl_src, ntohs(flow->dl_type), 0);
990     if (flow->dl_type == htons(FLOW_DL_TYPE_NONE)) {
991         struct eth_header *eth = b->l2;
992         eth->eth_type = htons(b->size);
993         return;
994     }
995
996     if (flow->vlan_tci & htons(VLAN_CFI)) {
997         eth_push_vlan(b, flow->vlan_tci & ~htons(VLAN_CFI));
998     }
999
1000     if (flow->dl_type == htons(ETH_TYPE_IP)) {
1001         struct ip_header *ip;
1002
1003         b->l3 = ip = ofpbuf_put_zeros(b, sizeof *ip);
1004         ip->ip_ihl_ver = IP_IHL_VER(5, 4);
1005         ip->ip_tos = flow->tos_frag & IP_DSCP_MASK;
1006         ip->ip_proto = flow->nw_proto;
1007         ip->ip_src = flow->nw_src;
1008         ip->ip_dst = flow->nw_dst;
1009
1010         if (flow->tos_frag & FLOW_FRAG_ANY) {
1011             ip->ip_frag_off |= htons(IP_MORE_FRAGMENTS);
1012             if (flow->tos_frag & FLOW_FRAG_LATER) {
1013                 ip->ip_frag_off |= htons(100);
1014             }
1015         }
1016         if (!(flow->tos_frag & FLOW_FRAG_ANY)
1017             || !(flow->tos_frag & FLOW_FRAG_LATER)) {
1018             if (flow->nw_proto == IPPROTO_TCP) {
1019                 struct tcp_header *tcp;
1020
1021                 b->l4 = tcp = ofpbuf_put_zeros(b, sizeof *tcp);
1022                 tcp->tcp_src = flow->tp_src;
1023                 tcp->tcp_dst = flow->tp_dst;
1024             } else if (flow->nw_proto == IPPROTO_UDP) {
1025                 struct udp_header *udp;
1026
1027                 b->l4 = udp = ofpbuf_put_zeros(b, sizeof *udp);
1028                 udp->udp_src = flow->tp_src;
1029                 udp->udp_dst = flow->tp_dst;
1030             } else if (flow->nw_proto == IPPROTO_ICMP) {
1031                 struct icmp_header *icmp;
1032
1033                 b->l4 = icmp = ofpbuf_put_zeros(b, sizeof *icmp);
1034                 icmp->icmp_type = ntohs(flow->tp_src);
1035                 icmp->icmp_code = ntohs(flow->tp_dst);
1036             }
1037         }
1038     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
1039         /* XXX */
1040     } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
1041         struct arp_eth_header *arp;
1042
1043         b->l3 = arp = ofpbuf_put_zeros(b, sizeof *arp);
1044         arp->ar_hrd = htons(1);
1045         arp->ar_pro = htons(ETH_TYPE_IP);
1046         arp->ar_hln = ETH_ADDR_LEN;
1047         arp->ar_pln = 4;
1048         arp->ar_op = htons(flow->nw_proto);
1049
1050         if (flow->nw_proto == ARP_OP_REQUEST ||
1051             flow->nw_proto == ARP_OP_REPLY) {
1052             arp->ar_spa = flow->nw_src;
1053             arp->ar_tpa = flow->nw_dst;
1054             memcpy(arp->ar_sha, flow->arp_sha, ETH_ADDR_LEN);
1055             memcpy(arp->ar_tha, flow->arp_tha, ETH_ADDR_LEN);
1056         }
1057     }
1058 }