lib/flow.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
   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 "csum.h"
  30 #include "dynamic-string.h"
  31 #include "hash.h"
  32 #include "ofpbuf.h"
  33 #include "openflow/openflow.h"
  34 #include "packets.h"
  35 #include "unaligned.h"
  36 #include "vlog.h"
  37
  38 VLOG_DEFINE_THIS_MODULE(flow);
  39
  40 COVERAGE_DEFINE(flow_extract);
  41
  42 static struct arp_eth_header *
  43 pull_arp(struct ofpbuf *packet)
  44 {
  45     return ofpbuf_try_pull(packet, ARP_ETH_HEADER_LEN);
  46 }
  47
  48 static struct ip_header *
  49 pull_ip(struct ofpbuf *packet)
  50 {
  51     if (packet->size >= IP_HEADER_LEN) {
  52         struct ip_header *ip = packet->data;
  53         int ip_len = IP_IHL(ip->ip_ihl_ver) * 4;
  54         if (ip_len >= IP_HEADER_LEN && packet->size >= ip_len) {
  55             return ofpbuf_pull(packet, ip_len);
  56         }
  57     }
  58     return NULL;
  59 }
  60
  61 static struct tcp_header *
  62 pull_tcp(struct ofpbuf *packet)
  63 {
  64     if (packet->size >= TCP_HEADER_LEN) {
  65         struct tcp_header *tcp = packet->data;
  66         int tcp_len = TCP_OFFSET(tcp->tcp_ctl) * 4;
  67         if (tcp_len >= TCP_HEADER_LEN && packet->size >= tcp_len) {
  68             return ofpbuf_pull(packet, tcp_len);
  69         }
  70     }
  71     return NULL;
  72 }
  73
  74 static struct udp_header *
  75 pull_udp(struct ofpbuf *packet)
  76 {
  77     return ofpbuf_try_pull(packet, UDP_HEADER_LEN);
  78 }
  79
  80 static struct icmp_header *
  81 pull_icmp(struct ofpbuf *packet)
  82 {
  83     return ofpbuf_try_pull(packet, ICMP_HEADER_LEN);
  84 }
  85
  86 static struct icmp6_hdr *
  87 pull_icmpv6(struct ofpbuf *packet)
  88 {
  89     return ofpbuf_try_pull(packet, sizeof(struct icmp6_hdr));
  90 }
  91
  92 static void
  93 parse_vlan(struct ofpbuf *b, struct flow *flow)
  94 {
  95     struct qtag_prefix {
  96         ovs_be16 eth_type;      /* ETH_TYPE_VLAN */
  97         ovs_be16 tci;
  98     };
  99
 100     if (b->size >= sizeof(struct qtag_prefix) + sizeof(ovs_be16)) {
 101         struct qtag_prefix *qp = ofpbuf_pull(b, sizeof *qp);
 102         flow->vlan_tci = qp->tci | htons(VLAN_CFI);
 103     }
 104 }
 105
 106 static ovs_be16
 107 parse_ethertype(struct ofpbuf *b)
 108 {
 109     struct llc_snap_header *llc;
 110     ovs_be16 proto;
 111
 112     proto = *(ovs_be16 *) ofpbuf_pull(b, sizeof proto);
 113     if (ntohs(proto) >= ETH_TYPE_MIN) {
 114         return proto;
 115     }
 116
 117     if (b->size < sizeof *llc) {
 118         return htons(FLOW_DL_TYPE_NONE);
 119     }
 120
 121     llc = b->data;
 122     if (llc->llc.llc_dsap != LLC_DSAP_SNAP
 123         || llc->llc.llc_ssap != LLC_SSAP_SNAP
 124         || llc->llc.llc_cntl != LLC_CNTL_SNAP
 125         || memcmp(llc->snap.snap_org, SNAP_ORG_ETHERNET,
 126                   sizeof llc->snap.snap_org)) {
 127         return htons(FLOW_DL_TYPE_NONE);
 128     }
 129
 130     ofpbuf_pull(b, sizeof *llc);
 131     return llc->snap.snap_type;
 132 }
 133
 134 static int
 135 parse_ipv6(struct ofpbuf *packet, struct flow *flow)
 136 {
 137     const struct ip6_hdr *nh;
 138     ovs_be32 tc_flow;
 139     int nexthdr;
 140
 141     nh = ofpbuf_try_pull(packet, sizeof *nh);
 142     if (!nh) {
 143         return EINVAL;
 144     }
 145
 146     nexthdr = nh->ip6_nxt;
 147
 148     flow->ipv6_src = nh->ip6_src;
 149     flow->ipv6_dst = nh->ip6_dst;
 150
 151     tc_flow = get_unaligned_be32(&nh->ip6_flow);
 152     flow->nw_tos = ntohl(tc_flow) >> 20;
 153     flow->ipv6_label = tc_flow & htonl(IPV6_LABEL_MASK);
 154     flow->nw_ttl = nh->ip6_hlim;
 155     flow->nw_proto = IPPROTO_NONE;
 156
 157     while (1) {
 158         if ((nexthdr != IPPROTO_HOPOPTS)
 159                 && (nexthdr != IPPROTO_ROUTING)
 160                 && (nexthdr != IPPROTO_DSTOPTS)
 161                 && (nexthdr != IPPROTO_AH)
 162                 && (nexthdr != IPPROTO_FRAGMENT)) {
 163             /* It's either a terminal header (e.g., TCP, UDP) or one we
 164              * don't understand.  In either case, we're done with the
 165              * packet, so use it to fill in 'nw_proto'. */
 166             break;
 167         }
 168
 169         /* We only verify that at least 8 bytes of the next header are
 170          * available, but many of these headers are longer.  Ensure that
 171          * accesses within the extension header are within those first 8
 172          * bytes. All extension headers are required to be at least 8
 173          * bytes. */
 174         if (packet->size < 8) {
 175             return EINVAL;
 176         }
 177
 178         if ((nexthdr == IPPROTO_HOPOPTS)
 179                 || (nexthdr == IPPROTO_ROUTING)
 180                 || (nexthdr == IPPROTO_DSTOPTS)) {
 181             /* These headers, while different, have the fields we care about
 182              * in the same location and with the same interpretation. */
 183             const struct ip6_ext *ext_hdr = packet->data;
 184             nexthdr = ext_hdr->ip6e_nxt;
 185             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 1) * 8)) {
 186                 return EINVAL;
 187             }
 188         } else if (nexthdr == IPPROTO_AH) {
 189             /* A standard AH definition isn't available, but the fields
 190              * we care about are in the same location as the generic
 191              * option header--only the header length is calculated
 192              * differently. */
 193             const struct ip6_ext *ext_hdr = packet->data;
 194             nexthdr = ext_hdr->ip6e_nxt;
 195             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 2) * 4)) {
 196                return EINVAL;
 197             }
 198         } else if (nexthdr == IPPROTO_FRAGMENT) {
 199             const struct ip6_frag *frag_hdr = packet->data;
 200
 201             nexthdr = frag_hdr->ip6f_nxt;
 202             if (!ofpbuf_try_pull(packet, sizeof *frag_hdr)) {
 203                 return EINVAL;
 204             }
 205
 206             /* We only process the first fragment. */
 207             if (frag_hdr->ip6f_offlg != htons(0)) {
 208                 if ((frag_hdr->ip6f_offlg & IP6F_OFF_MASK) == htons(0)) {
 209                     flow->nw_frag = FLOW_NW_FRAG_ANY;
 210                 } else {
 211                     flow->nw_frag |= FLOW_NW_FRAG_LATER;
 212                     nexthdr = IPPROTO_FRAGMENT;
 213                     break;
 214                 }
 215             }
 216         }
 217     }
 218
 219     flow->nw_proto = nexthdr;
 220     return 0;
 221 }
 222
 223 static void
 224 parse_tcp(struct ofpbuf *packet, struct ofpbuf *b, struct flow *flow)
 225 {
 226     const struct tcp_header *tcp = pull_tcp(b);
 227     if (tcp) {
 228         flow->tp_src = tcp->tcp_src;
 229         flow->tp_dst = tcp->tcp_dst;
 230         packet->l7 = b->data;
 231     }
 232 }
 233
 234 static void
 235 parse_udp(struct ofpbuf *packet, struct ofpbuf *b, struct flow *flow)
 236 {
 237     const struct udp_header *udp = pull_udp(b);
 238     if (udp) {
 239         flow->tp_src = udp->udp_src;
 240         flow->tp_dst = udp->udp_dst;
 241         packet->l7 = b->data;
 242     }
 243 }
 244
 245 static bool
 246 parse_icmpv6(struct ofpbuf *b, struct flow *flow)
 247 {
 248     const struct icmp6_hdr *icmp = pull_icmpv6(b);
 249
 250     if (!icmp) {
 251         return false;
 252     }
 253
 254     /* The ICMPv6 type and code fields use the 16-bit transport port
 255      * fields, so we need to store them in 16-bit network byte order. */
 256     flow->tp_src = htons(icmp->icmp6_type);
 257     flow->tp_dst = htons(icmp->icmp6_code);
 258
 259     if (icmp->icmp6_code == 0 &&
 260         (icmp->icmp6_type == ND_NEIGHBOR_SOLICIT ||
 261          icmp->icmp6_type == ND_NEIGHBOR_ADVERT)) {
 262         const struct in6_addr *nd_target;
 263
 264         nd_target = ofpbuf_try_pull(b, sizeof *nd_target);
 265         if (!nd_target) {
 266             return false;
 267         }
 268         flow->nd_target = *nd_target;
 269
 270         while (b->size >= 8) {
 271             /* The minimum size of an option is 8 bytes, which also is
 272              * the size of Ethernet link-layer options. */
 273             const struct nd_opt_hdr *nd_opt = b->data;
 274             int opt_len = nd_opt->nd_opt_len * 8;
 275
 276             if (!opt_len || opt_len > b->size) {
 277                 goto invalid;
 278             }
 279
 280             /* Store the link layer address if the appropriate option is
 281              * provided.  It is considered an error if the same link
 282              * layer option is specified twice. */
 283             if (nd_opt->nd_opt_type == ND_OPT_SOURCE_LINKADDR
 284                     && opt_len == 8) {
 285                 if (eth_addr_is_zero(flow->arp_sha)) {
 286                     memcpy(flow->arp_sha, nd_opt + 1, ETH_ADDR_LEN);
 287                 } else {
 288                     goto invalid;
 289                 }
 290             } else if (nd_opt->nd_opt_type == ND_OPT_TARGET_LINKADDR
 291                     && opt_len == 8) {
 292                 if (eth_addr_is_zero(flow->arp_tha)) {
 293                     memcpy(flow->arp_tha, nd_opt + 1, ETH_ADDR_LEN);
 294                 } else {
 295                     goto invalid;
 296                 }
 297             }
 298
 299             if (!ofpbuf_try_pull(b, opt_len)) {
 300                 goto invalid;
 301             }
 302         }
 303     }
 304
 305     return true;
 306
 307 invalid:
 308     memset(&flow->nd_target, 0, sizeof(flow->nd_target));
 309     memset(flow->arp_sha, 0, sizeof(flow->arp_sha));
 310     memset(flow->arp_tha, 0, sizeof(flow->arp_tha));
 311
 312     return false;
 313
 314 }
 315
 316 /* Initializes 'flow' members from 'packet', 'skb_priority', 'tun_id', and
 317  * 'ofp_in_port'.
 318  *
 319  * Initializes 'packet' header pointers as follows:
 320  *
 321  *    - packet->l2 to the start of the Ethernet header.
 322  *
 323  *    - packet->l3 to just past the Ethernet header, or just past the
 324  *      vlan_header if one is present, to the first byte of the payload of the
 325  *      Ethernet frame.
 326  *
 327  *    - packet->l4 to just past the IPv4 header, if one is present and has a
 328  *      correct length, and otherwise NULL.
 329  *
 330  *    - packet->l7 to just past the TCP or UDP or ICMP header, if one is
 331  *      present and has a correct length, and otherwise NULL.
 332  */
 333 void
 334 flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
 335              uint16_t ofp_in_port, struct flow *flow)
 336 {
 337     struct ofpbuf b = *packet;
 338     struct eth_header *eth;
 339
 340     COVERAGE_INC(flow_extract);
 341
 342     memset(flow, 0, sizeof *flow);
 343     flow->tun_id = tun_id;
 344     flow->in_port = ofp_in_port;
 345     flow->skb_priority = skb_priority;
 346
 347     packet->l2 = b.data;
 348     packet->l3 = NULL;
 349     packet->l4 = NULL;
 350     packet->l7 = NULL;
 351
 352     if (b.size < sizeof *eth) {
 353         return;
 354     }
 355
 356     /* Link layer. */
 357     eth = b.data;
 358     memcpy(flow->dl_src, eth->eth_src, ETH_ADDR_LEN);
 359     memcpy(flow->dl_dst, eth->eth_dst, ETH_ADDR_LEN);
 360
 361     /* dl_type, vlan_tci. */
 362     ofpbuf_pull(&b, ETH_ADDR_LEN * 2);
 363     if (eth->eth_type == htons(ETH_TYPE_VLAN)) {
 364         parse_vlan(&b, flow);
 365     }
 366     flow->dl_type = parse_ethertype(&b);
 367
 368     /* Network layer. */
 369     packet->l3 = b.data;
 370     if (flow->dl_type == htons(ETH_TYPE_IP)) {
 371         const struct ip_header *nh = pull_ip(&b);
 372         if (nh) {
 373             packet->l4 = b.data;
 374
 375             flow->nw_src = get_unaligned_be32(&nh->ip_src);
 376             flow->nw_dst = get_unaligned_be32(&nh->ip_dst);
 377             flow->nw_proto = nh->ip_proto;
 378
 379             flow->nw_tos = nh->ip_tos;
 380             if (IP_IS_FRAGMENT(nh->ip_frag_off)) {
 381                 flow->nw_frag = FLOW_NW_FRAG_ANY;
 382                 if (nh->ip_frag_off & htons(IP_FRAG_OFF_MASK)) {
 383                     flow->nw_frag |= FLOW_NW_FRAG_LATER;
 384                 }
 385             }
 386             flow->nw_ttl = nh->ip_ttl;
 387
 388             if (!(nh->ip_frag_off & htons(IP_FRAG_OFF_MASK))) {
 389                 if (flow->nw_proto == IPPROTO_TCP) {
 390                     parse_tcp(packet, &b, flow);
 391                 } else if (flow->nw_proto == IPPROTO_UDP) {
 392                     parse_udp(packet, &b, flow);
 393                 } else if (flow->nw_proto == IPPROTO_ICMP) {
 394                     const struct icmp_header *icmp = pull_icmp(&b);
 395                     if (icmp) {
 396                         flow->tp_src = htons(icmp->icmp_type);
 397                         flow->tp_dst = htons(icmp->icmp_code);
 398                         packet->l7 = b.data;
 399                     }
 400                 }
 401             }
 402         }
 403     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
 404         if (parse_ipv6(&b, flow)) {
 405             return;
 406         }
 407
 408         packet->l4 = b.data;
 409         if (flow->nw_proto == IPPROTO_TCP) {
 410             parse_tcp(packet, &b, flow);
 411         } else if (flow->nw_proto == IPPROTO_UDP) {
 412             parse_udp(packet, &b, flow);
 413         } else if (flow->nw_proto == IPPROTO_ICMPV6) {
 414             if (parse_icmpv6(&b, flow)) {
 415                 packet->l7 = b.data;
 416             }
 417         }
 418     } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
 419         const struct arp_eth_header *arp = pull_arp(&b);
 420         if (arp && arp->ar_hrd == htons(1)
 421             && arp->ar_pro == htons(ETH_TYPE_IP)
 422             && arp->ar_hln == ETH_ADDR_LEN
 423             && arp->ar_pln == 4) {
 424             /* We only match on the lower 8 bits of the opcode. */
 425             if (ntohs(arp->ar_op) <= 0xff) {
 426                 flow->nw_proto = ntohs(arp->ar_op);
 427             }
 428
 429             if ((flow->nw_proto == ARP_OP_REQUEST)
 430                 || (flow->nw_proto == ARP_OP_REPLY)) {
 431                 flow->nw_src = arp->ar_spa;
 432                 flow->nw_dst = arp->ar_tpa;
 433                 memcpy(flow->arp_sha, arp->ar_sha, ETH_ADDR_LEN);
 434                 memcpy(flow->arp_tha, arp->ar_tha, ETH_ADDR_LEN);
 435             }
 436         }
 437     }
 438 }
 439
 440 /* For every bit of a field that is wildcarded in 'wildcards', sets the
 441  * corresponding bit in 'flow' to zero. */
 442 void
 443 flow_zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards)
 444 {
 445     uint32_t *flow_u32 = (uint32_t *) flow;
 446     const uint32_t *wc_u32 = (const uint32_t *) &wildcards->masks;
 447     size_t i;
 448
 449     for (i = 0; i < FLOW_U32S; i++) {
 450         flow_u32[i] &= wc_u32[i];
 451     }
 452 }
 453
 454 /* Initializes 'fmd' with the metadata found in 'flow'. */
 455 void
 456 flow_get_metadata(const struct flow *flow, struct flow_metadata *fmd)
 457 {
 458     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 17);
 459
 460     fmd->tun_id = flow->tun_id;
 461     fmd->metadata = flow->metadata;
 462     memcpy(fmd->regs, flow->regs, sizeof fmd->regs);
 463     fmd->in_port = flow->in_port;
 464 }
 465
 466 char *
 467 flow_to_string(const struct flow *flow)
 468 {
 469     struct ds ds = DS_EMPTY_INITIALIZER;
 470     flow_format(&ds, flow);
 471     return ds_cstr(&ds);
 472 }
 473
 474 void
 475 flow_format(struct ds *ds, const struct flow *flow)
 476 {
 477     ds_put_format(ds, "priority:%"PRIu32
 478                       ",tunnel:%#"PRIx64
 479                       ",metadata:%#"PRIx64
 480                       ",in_port:%04"PRIx16,
 481                       flow->skb_priority,
 482                       ntohll(flow->tun_id),
 483                       ntohll(flow->metadata),
 484                       flow->in_port);
 485
 486     ds_put_format(ds, ",tci(");
 487     if (flow->vlan_tci) {
 488         ds_put_format(ds, "vlan:%"PRIu16",pcp:%d",
 489                       vlan_tci_to_vid(flow->vlan_tci),
 490                       vlan_tci_to_pcp(flow->vlan_tci));
 491     } else {
 492         ds_put_char(ds, '0');
 493     }
 494     ds_put_format(ds, ") mac("ETH_ADDR_FMT"->"ETH_ADDR_FMT
 495                       ") type:%04"PRIx16,
 496                   ETH_ADDR_ARGS(flow->dl_src),
 497                   ETH_ADDR_ARGS(flow->dl_dst),
 498                   ntohs(flow->dl_type));
 499
 500     if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
 501         ds_put_format(ds, " label:%#"PRIx32" proto:%"PRIu8" tos:%#"PRIx8
 502                           " ttl:%"PRIu8" ipv6(",
 503                       ntohl(flow->ipv6_label), flow->nw_proto,
 504                       flow->nw_tos, flow->nw_ttl);
 505         print_ipv6_addr(ds, &flow->ipv6_src);
 506         ds_put_cstr(ds, "->");
 507         print_ipv6_addr(ds, &flow->ipv6_dst);
 508         ds_put_char(ds, ')');
 509     } else {
 510         ds_put_format(ds, " proto:%"PRIu8" tos:%#"PRIx8" ttl:%"PRIu8
 511                           " ip("IP_FMT"->"IP_FMT")",
 512                           flow->nw_proto, flow->nw_tos, flow->nw_ttl,
 513                           IP_ARGS(&flow->nw_src), IP_ARGS(&flow->nw_dst));
 514     }
 515     if (flow->nw_frag) {
 516         ds_put_format(ds, " frag(%s)",
 517                       flow->nw_frag == FLOW_NW_FRAG_ANY ? "first"
 518                       : flow->nw_frag == (FLOW_NW_FRAG_ANY | FLOW_NW_FRAG_LATER)
 519                       ? "later" : "<error>");
 520     }
 521     if (flow->tp_src || flow->tp_dst) {
 522         ds_put_format(ds, " port(%"PRIu16"->%"PRIu16")",
 523                 ntohs(flow->tp_src), ntohs(flow->tp_dst));
 524     }
 525     if (!eth_addr_is_zero(flow->arp_sha) || !eth_addr_is_zero(flow->arp_tha)) {
 526         ds_put_format(ds, " arp_ha("ETH_ADDR_FMT"->"ETH_ADDR_FMT")",
 527                 ETH_ADDR_ARGS(flow->arp_sha),
 528                 ETH_ADDR_ARGS(flow->arp_tha));
 529     }
 530 }
 531
 532 void
 533 flow_print(FILE *stream, const struct flow *flow)
 534 {
 535     char *s = flow_to_string(flow);
 536     fputs(s, stream);
 537     free(s);
 538 }
 539 \f
 540 /* flow_wildcards functions. */
 541
 542 /* Initializes 'wc' as a set of wildcards that matches every packet. */
 543 void
 544 flow_wildcards_init_catchall(struct flow_wildcards *wc)
 545 {
 546     memset(&wc->masks, 0, sizeof wc->masks);
 547 }
 548
 549 /* Initializes 'wc' as an exact-match set of wildcards; that is, 'wc' does not
 550  * wildcard any bits or fields. */
 551 void
 552 flow_wildcards_init_exact(struct flow_wildcards *wc)
 553 {
 554     memset(&wc->masks, 0xff, sizeof wc->masks);
 555     memset(wc->masks.zeros, 0, sizeof wc->masks.zeros);
 556 }
 557
 558 /* Returns true if 'wc' matches every packet, false if 'wc' fixes any bits or
 559  * fields. */
 560 bool
 561 flow_wildcards_is_catchall(const struct flow_wildcards *wc)
 562 {
 563     const uint32_t *wc_u32 = (const uint32_t *) &wc->masks;
 564     size_t i;
 565
 566     for (i = 0; i < FLOW_U32S; i++) {
 567         if (wc_u32[i]) {
 568             return false;
 569         }
 570     }
 571     return true;
 572 }
 573
 574 /* Initializes 'dst' as the combination of wildcards in 'src1' and 'src2'.
 575  * That is, a bit or a field is wildcarded in 'dst' if it is wildcarded in
 576  * 'src1' or 'src2' or both.  */
 577 void
 578 flow_wildcards_combine(struct flow_wildcards *dst,
 579                        const struct flow_wildcards *src1,
 580                        const struct flow_wildcards *src2)
 581 {
 582     uint32_t *dst_u32 = (uint32_t *) &dst->masks;
 583     const uint32_t *src1_u32 = (const uint32_t *) &src1->masks;
 584     const uint32_t *src2_u32 = (const uint32_t *) &src2->masks;
 585     size_t i;
 586
 587     for (i = 0; i < FLOW_U32S; i++) {
 588         dst_u32[i] = src1_u32[i] & src2_u32[i];
 589     }
 590 }
 591
 592 /* Returns a hash of the wildcards in 'wc'. */
 593 uint32_t
 594 flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis)
 595 {
 596     return flow_hash(&wc->masks, basis);;
 597 }
 598
 599 /* Returns true if 'a' and 'b' represent the same wildcards, false if they are
 600  * different. */
 601 bool
 602 flow_wildcards_equal(const struct flow_wildcards *a,
 603                      const struct flow_wildcards *b)
 604 {
 605     return flow_equal(&a->masks, &b->masks);
 606 }
 607
 608 /* Returns true if at least one bit or field is wildcarded in 'a' but not in
 609  * 'b', false otherwise. */
 610 bool
 611 flow_wildcards_has_extra(const struct flow_wildcards *a,
 612                          const struct flow_wildcards *b)
 613 {
 614     const uint32_t *a_u32 = (const uint32_t *) &a->masks;
 615     const uint32_t *b_u32 = (const uint32_t *) &b->masks;
 616     size_t i;
 617
 618     for (i = 0; i < FLOW_U32S; i++) {
 619         if ((a_u32[i] & b_u32[i]) != b_u32[i]) {
 620             return true;
 621         }
 622     }
 623     return false;
 624 }
 625
 626 /* Returns true if 'a' and 'b' are equal, except that 0-bits (wildcarded bits)
 627  * in 'wc' do not need to be equal in 'a' and 'b'. */
 628 bool
 629 flow_equal_except(const struct flow *a, const struct flow *b,
 630                   const struct flow_wildcards *wc)
 631 {
 632     const uint32_t *a_u32 = (const uint32_t *) a;
 633     const uint32_t *b_u32 = (const uint32_t *) b;
 634     const uint32_t *wc_u32 = (const uint32_t *) &wc->masks;
 635     size_t i;
 636
 637     for (i = 0; i < FLOW_U32S; i++) {
 638         if ((a_u32[i] ^ b_u32[i]) & wc_u32[i]) {
 639             return false;
 640         }
 641     }
 642     return true;
 643 }
 644
 645 /* Sets the wildcard mask for register 'idx' in 'wc' to 'mask'.
 646  * (A 0-bit indicates a wildcard bit.) */
 647 void
 648 flow_wildcards_set_reg_mask(struct flow_wildcards *wc, int idx, uint32_t mask)
 649 {
 650     wc->masks.regs[idx] = mask;
 651 }
 652
 653 /* Hashes 'flow' based on its L2 through L4 protocol information. */
 654 uint32_t
 655 flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis)
 656 {
 657     struct {
 658         union {
 659             ovs_be32 ipv4_addr;
 660             struct in6_addr ipv6_addr;
 661         };
 662         ovs_be16 eth_type;
 663         ovs_be16 vlan_tci;
 664         ovs_be16 tp_port;
 665         uint8_t eth_addr[ETH_ADDR_LEN];
 666         uint8_t ip_proto;
 667     } fields;
 668
 669     int i;
 670
 671     memset(&fields, 0, sizeof fields);
 672     for (i = 0; i < ETH_ADDR_LEN; i++) {
 673         fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
 674     }
 675     fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
 676     fields.eth_type = flow->dl_type;
 677
 678     /* UDP source and destination port are not taken into account because they
 679      * will not necessarily be symmetric in a bidirectional flow. */
 680     if (fields.eth_type == htons(ETH_TYPE_IP)) {
 681         fields.ipv4_addr = flow->nw_src ^ flow->nw_dst;
 682         fields.ip_proto = flow->nw_proto;
 683         if (fields.ip_proto == IPPROTO_TCP) {
 684             fields.tp_port = flow->tp_src ^ flow->tp_dst;
 685         }
 686     } else if (fields.eth_type == htons(ETH_TYPE_IPV6)) {
 687         const uint8_t *a = &flow->ipv6_src.s6_addr[0];
 688         const uint8_t *b = &flow->ipv6_dst.s6_addr[0];
 689         uint8_t *ipv6_addr = &fields.ipv6_addr.s6_addr[0];
 690
 691         for (i=0; i<16; i++) {
 692             ipv6_addr[i] = a[i] ^ b[i];
 693         }
 694         fields.ip_proto = flow->nw_proto;
 695         if (fields.ip_proto == IPPROTO_TCP) {
 696             fields.tp_port = flow->tp_src ^ flow->tp_dst;
 697         }
 698     }
 699     return hash_bytes(&fields, sizeof fields, basis);
 700 }
 701
 702 /* Hashes the portions of 'flow' designated by 'fields'. */
 703 uint32_t
 704 flow_hash_fields(const struct flow *flow, enum nx_hash_fields fields,
 705                  uint16_t basis)
 706 {
 707     switch (fields) {
 708
 709     case NX_HASH_FIELDS_ETH_SRC:
 710         return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
 711
 712     case NX_HASH_FIELDS_SYMMETRIC_L4:
 713         return flow_hash_symmetric_l4(flow, basis);
 714     }
 715
 716     NOT_REACHED();
 717 }
 718
 719 /* Returns a string representation of 'fields'. */
 720 const char *
 721 flow_hash_fields_to_str(enum nx_hash_fields fields)
 722 {
 723     switch (fields) {
 724     case NX_HASH_FIELDS_ETH_SRC: return "eth_src";
 725     case NX_HASH_FIELDS_SYMMETRIC_L4: return "symmetric_l4";
 726     default: return "<unknown>";
 727     }
 728 }
 729
 730 /* Returns true if the value of 'fields' is supported. Otherwise false. */
 731 bool
 732 flow_hash_fields_valid(enum nx_hash_fields fields)
 733 {
 734     return fields == NX_HASH_FIELDS_ETH_SRC
 735         || fields == NX_HASH_FIELDS_SYMMETRIC_L4;
 736 }
 737
 738 /* Sets the VLAN VID that 'flow' matches to 'vid', which is interpreted as an
 739  * OpenFlow 1.0 "dl_vlan" value:
 740  *
 741  *      - If it is in the range 0...4095, 'flow->vlan_tci' is set to match
 742  *        that VLAN.  Any existing PCP match is unchanged (it becomes 0 if
 743  *        'flow' previously matched packets without a VLAN header).
 744  *
 745  *      - If it is OFP_VLAN_NONE, 'flow->vlan_tci' is set to match a packet
 746  *        without a VLAN tag.
 747  *
 748  *      - Other values of 'vid' should not be used. */
 749 void
 750 flow_set_dl_vlan(struct flow *flow, ovs_be16 vid)
 751 {
 752     if (vid == htons(OFP10_VLAN_NONE)) {
 753         flow->vlan_tci = htons(0);
 754     } else {
 755         vid &= htons(VLAN_VID_MASK);
 756         flow->vlan_tci &= ~htons(VLAN_VID_MASK);
 757         flow->vlan_tci |= htons(VLAN_CFI) | vid;
 758     }
 759 }
 760
 761 /* Sets the VLAN VID that 'flow' matches to 'vid', which is interpreted as an
 762  * OpenFlow 1.2 "vlan_vid" value, that is, the low 13 bits of 'vlan_tci' (VID
 763  * plus CFI). */
 764 void
 765 flow_set_vlan_vid(struct flow *flow, ovs_be16 vid)
 766 {
 767     ovs_be16 mask = htons(VLAN_VID_MASK | VLAN_CFI);
 768     flow->vlan_tci &= ~mask;
 769     flow->vlan_tci |= vid & mask;
 770 }
 771
 772 /* Sets the VLAN PCP that 'flow' matches to 'pcp', which should be in the
 773  * range 0...7.
 774  *
 775  * This function has no effect on the VLAN ID that 'flow' matches.
 776  *
 777  * After calling this function, 'flow' will not match packets without a VLAN
 778  * header. */
 779 void
 780 flow_set_vlan_pcp(struct flow *flow, uint8_t pcp)
 781 {
 782     pcp &= 0x07;
 783     flow->vlan_tci &= ~htons(VLAN_PCP_MASK);
 784     flow->vlan_tci |= htons((pcp << VLAN_PCP_SHIFT) | VLAN_CFI);
 785 }
 786
 787 /* Puts into 'b' a packet that flow_extract() would parse as having the given
 788  * 'flow'.
 789  *
 790  * (This is useful only for testing, obviously, and the packet isn't really
 791  * valid. It hasn't got some checksums filled in, for one, and lots of fields
 792  * are just zeroed.) */
 793 void
 794 flow_compose(struct ofpbuf *b, const struct flow *flow)
 795 {
 796     eth_compose(b, flow->dl_dst, flow->dl_src, ntohs(flow->dl_type), 0);
 797     if (flow->dl_type == htons(FLOW_DL_TYPE_NONE)) {
 798         struct eth_header *eth = b->l2;
 799         eth->eth_type = htons(b->size);
 800         return;
 801     }
 802
 803     if (flow->vlan_tci & htons(VLAN_CFI)) {
 804         eth_push_vlan(b, flow->vlan_tci);
 805     }
 806
 807     if (flow->dl_type == htons(ETH_TYPE_IP)) {
 808         struct ip_header *ip;
 809
 810         b->l3 = ip = ofpbuf_put_zeros(b, sizeof *ip);
 811         ip->ip_ihl_ver = IP_IHL_VER(5, 4);
 812         ip->ip_tos = flow->nw_tos;
 813         ip->ip_proto = flow->nw_proto;
 814         ip->ip_src = flow->nw_src;
 815         ip->ip_dst = flow->nw_dst;
 816
 817         if (flow->nw_frag & FLOW_NW_FRAG_ANY) {
 818             ip->ip_frag_off |= htons(IP_MORE_FRAGMENTS);
 819             if (flow->nw_frag & FLOW_NW_FRAG_LATER) {
 820                 ip->ip_frag_off |= htons(100);
 821             }
 822         }
 823         if (!(flow->nw_frag & FLOW_NW_FRAG_ANY)
 824             || !(flow->nw_frag & FLOW_NW_FRAG_LATER)) {
 825             if (flow->nw_proto == IPPROTO_TCP) {
 826                 struct tcp_header *tcp;
 827
 828                 b->l4 = tcp = ofpbuf_put_zeros(b, sizeof *tcp);
 829                 tcp->tcp_src = flow->tp_src;
 830                 tcp->tcp_dst = flow->tp_dst;
 831                 tcp->tcp_ctl = TCP_CTL(0, 5);
 832             } else if (flow->nw_proto == IPPROTO_UDP) {
 833                 struct udp_header *udp;
 834
 835                 b->l4 = udp = ofpbuf_put_zeros(b, sizeof *udp);
 836                 udp->udp_src = flow->tp_src;
 837                 udp->udp_dst = flow->tp_dst;
 838             } else if (flow->nw_proto == IPPROTO_ICMP) {
 839                 struct icmp_header *icmp;
 840
 841                 b->l4 = icmp = ofpbuf_put_zeros(b, sizeof *icmp);
 842                 icmp->icmp_type = ntohs(flow->tp_src);
 843                 icmp->icmp_code = ntohs(flow->tp_dst);
 844                 icmp->icmp_csum = csum(icmp, ICMP_HEADER_LEN);
 845             }
 846         }
 847
 848         ip = b->l3;
 849         ip->ip_tot_len = htons((uint8_t *) b->data + b->size
 850                                - (uint8_t *) b->l3);
 851         ip->ip_csum = csum(ip, sizeof *ip);
 852     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
 853         /* XXX */
 854     } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
 855         struct arp_eth_header *arp;
 856
 857         b->l3 = arp = ofpbuf_put_zeros(b, sizeof *arp);
 858         arp->ar_hrd = htons(1);
 859         arp->ar_pro = htons(ETH_TYPE_IP);
 860         arp->ar_hln = ETH_ADDR_LEN;
 861         arp->ar_pln = 4;
 862         arp->ar_op = htons(flow->nw_proto);
 863
 864         if (flow->nw_proto == ARP_OP_REQUEST ||
 865             flow->nw_proto == ARP_OP_REPLY) {
 866             arp->ar_spa = flow->nw_src;
 867             arp->ar_tpa = flow->nw_dst;
 868             memcpy(arp->ar_sha, flow->arp_sha, ETH_ADDR_LEN);
 869             memcpy(arp->ar_tha, flow->arp_tha, ETH_ADDR_LEN);
 870         }
 871     }
 872 }