lib/flow.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 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 <errno.h>
  20 #include <inttypes.h>
  21 #include <limits.h>
  22 #include <netinet/in.h>
  23 #include <netinet/icmp6.h>
  24 #include <netinet/ip6.h>
  25 #include <stdint.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include "byte-order.h"
  29 #include "coverage.h"
  30 #include "csum.h"
  31 #include "dynamic-string.h"
  32 #include "hash.h"
  33 #include "jhash.h"
  34 #include "match.h"
  35 #include "ofpbuf.h"
  36 #include "openflow/openflow.h"
  37 #include "packets.h"
  38 #include "odp-util.h"
  39 #include "random.h"
  40 #include "unaligned.h"
  41
  42 COVERAGE_DEFINE(flow_extract);
  43 COVERAGE_DEFINE(miniflow_malloc);
  44
  45 /* U32 indices for segmented flow classification. */
  46 const uint8_t flow_segment_u32s[4] = {
  47     FLOW_SEGMENT_1_ENDS_AT / 4,
  48     FLOW_SEGMENT_2_ENDS_AT / 4,
  49     FLOW_SEGMENT_3_ENDS_AT / 4,
  50     FLOW_U32S
  51 };
  52
  53 static struct arp_eth_header *
  54 pull_arp(struct ofpbuf *packet)
  55 {
  56     return ofpbuf_try_pull(packet, ARP_ETH_HEADER_LEN);
  57 }
  58
  59 static struct ip_header *
  60 pull_ip(struct ofpbuf *packet)
  61 {
  62     if (packet->size >= IP_HEADER_LEN) {
  63         struct ip_header *ip = packet->data;
  64         int ip_len = IP_IHL(ip->ip_ihl_ver) * 4;
  65         if (ip_len >= IP_HEADER_LEN && packet->size >= ip_len) {
  66             return ofpbuf_pull(packet, ip_len);
  67         }
  68     }
  69     return NULL;
  70 }
  71
  72 static struct icmp_header *
  73 pull_icmp(struct ofpbuf *packet)
  74 {
  75     return ofpbuf_try_pull(packet, ICMP_HEADER_LEN);
  76 }
  77
  78 static struct icmp6_hdr *
  79 pull_icmpv6(struct ofpbuf *packet)
  80 {
  81     return ofpbuf_try_pull(packet, sizeof(struct icmp6_hdr));
  82 }
  83
  84 static void
  85 parse_mpls(struct ofpbuf *b, struct flow *flow)
  86 {
  87     struct mpls_hdr *mh;
  88     int idx = 0;
  89
  90     while ((mh = ofpbuf_try_pull(b, sizeof *mh))) {
  91         if (idx < FLOW_MAX_MPLS_LABELS) {
  92             flow->mpls_lse[idx++] = mh->mpls_lse;
  93         }
  94         if (mh->mpls_lse & htonl(MPLS_BOS_MASK)) {
  95             break;
  96         }
  97     }
  98 }
  99
 100 static void
 101 parse_vlan(struct ofpbuf *b, struct flow *flow)
 102 {
 103     struct qtag_prefix {
 104         ovs_be16 eth_type;      /* ETH_TYPE_VLAN */
 105         ovs_be16 tci;
 106     };
 107
 108     if (b->size >= sizeof(struct qtag_prefix) + sizeof(ovs_be16)) {
 109         struct qtag_prefix *qp = ofpbuf_pull(b, sizeof *qp);
 110         flow->vlan_tci = qp->tci | htons(VLAN_CFI);
 111     }
 112 }
 113
 114 static ovs_be16
 115 parse_ethertype(struct ofpbuf *b)
 116 {
 117     struct llc_snap_header *llc;
 118     ovs_be16 proto;
 119
 120     proto = *(ovs_be16 *) ofpbuf_pull(b, sizeof proto);
 121     if (ntohs(proto) >= ETH_TYPE_MIN) {
 122         return proto;
 123     }
 124
 125     if (b->size < sizeof *llc) {
 126         return htons(FLOW_DL_TYPE_NONE);
 127     }
 128
 129     llc = b->data;
 130     if (llc->llc.llc_dsap != LLC_DSAP_SNAP
 131         || llc->llc.llc_ssap != LLC_SSAP_SNAP
 132         || llc->llc.llc_cntl != LLC_CNTL_SNAP
 133         || memcmp(llc->snap.snap_org, SNAP_ORG_ETHERNET,
 134                   sizeof llc->snap.snap_org)) {
 135         return htons(FLOW_DL_TYPE_NONE);
 136     }
 137
 138     ofpbuf_pull(b, sizeof *llc);
 139
 140     if (ntohs(llc->snap.snap_type) >= ETH_TYPE_MIN) {
 141         return llc->snap.snap_type;
 142     }
 143
 144     return htons(FLOW_DL_TYPE_NONE);
 145 }
 146
 147 static int
 148 parse_ipv6(struct ofpbuf *packet, struct flow *flow)
 149 {
 150     const struct ovs_16aligned_ip6_hdr *nh;
 151     ovs_be32 tc_flow;
 152     int nexthdr;
 153
 154     nh = ofpbuf_try_pull(packet, sizeof *nh);
 155     if (!nh) {
 156         return EINVAL;
 157     }
 158
 159     nexthdr = nh->ip6_nxt;
 160
 161     memcpy(&flow->ipv6_src, &nh->ip6_src, sizeof flow->ipv6_src);
 162     memcpy(&flow->ipv6_dst, &nh->ip6_dst, sizeof flow->ipv6_dst);
 163
 164     tc_flow = get_16aligned_be32(&nh->ip6_flow);
 165     flow->nw_tos = ntohl(tc_flow) >> 20;
 166     flow->ipv6_label = tc_flow & htonl(IPV6_LABEL_MASK);
 167     flow->nw_ttl = nh->ip6_hlim;
 168     flow->nw_proto = IPPROTO_NONE;
 169
 170     while (1) {
 171         if ((nexthdr != IPPROTO_HOPOPTS)
 172                 && (nexthdr != IPPROTO_ROUTING)
 173                 && (nexthdr != IPPROTO_DSTOPTS)
 174                 && (nexthdr != IPPROTO_AH)
 175                 && (nexthdr != IPPROTO_FRAGMENT)) {
 176             /* It's either a terminal header (e.g., TCP, UDP) or one we
 177              * don't understand.  In either case, we're done with the
 178              * packet, so use it to fill in 'nw_proto'. */
 179             break;
 180         }
 181
 182         /* We only verify that at least 8 bytes of the next header are
 183          * available, but many of these headers are longer.  Ensure that
 184          * accesses within the extension header are within those first 8
 185          * bytes. All extension headers are required to be at least 8
 186          * bytes. */
 187         if (packet->size < 8) {
 188             return EINVAL;
 189         }
 190
 191         if ((nexthdr == IPPROTO_HOPOPTS)
 192                 || (nexthdr == IPPROTO_ROUTING)
 193                 || (nexthdr == IPPROTO_DSTOPTS)) {
 194             /* These headers, while different, have the fields we care about
 195              * in the same location and with the same interpretation. */
 196             const struct ip6_ext *ext_hdr = packet->data;
 197             nexthdr = ext_hdr->ip6e_nxt;
 198             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 1) * 8)) {
 199                 return EINVAL;
 200             }
 201         } else if (nexthdr == IPPROTO_AH) {
 202             /* A standard AH definition isn't available, but the fields
 203              * we care about are in the same location as the generic
 204              * option header--only the header length is calculated
 205              * differently. */
 206             const struct ip6_ext *ext_hdr = packet->data;
 207             nexthdr = ext_hdr->ip6e_nxt;
 208             if (!ofpbuf_try_pull(packet, (ext_hdr->ip6e_len + 2) * 4)) {
 209                return EINVAL;
 210             }
 211         } else if (nexthdr == IPPROTO_FRAGMENT) {
 212             const struct ovs_16aligned_ip6_frag *frag_hdr = packet->data;
 213
 214             nexthdr = frag_hdr->ip6f_nxt;
 215             if (!ofpbuf_try_pull(packet, sizeof *frag_hdr)) {
 216                 return EINVAL;
 217             }
 218
 219             /* We only process the first fragment. */
 220             if (frag_hdr->ip6f_offlg != htons(0)) {
 221                 flow->nw_frag = FLOW_NW_FRAG_ANY;
 222                 if ((frag_hdr->ip6f_offlg & IP6F_OFF_MASK) != htons(0)) {
 223                     flow->nw_frag |= FLOW_NW_FRAG_LATER;
 224                     nexthdr = IPPROTO_FRAGMENT;
 225                     break;
 226                 }
 227             }
 228         }
 229     }
 230
 231     flow->nw_proto = nexthdr;
 232     return 0;
 233 }
 234
 235 static void
 236 parse_tcp(struct ofpbuf *b, struct flow *flow)
 237 {
 238     if (b->size >= TCP_HEADER_LEN) {
 239         const struct tcp_header *tcp = b->data;
 240
 241         flow->tp_src = tcp->tcp_src;
 242         flow->tp_dst = tcp->tcp_dst;
 243         flow->tcp_flags = tcp->tcp_ctl & htons(0x0fff);
 244     }
 245 }
 246
 247 static void
 248 parse_udp(struct ofpbuf *b, struct flow *flow)
 249 {
 250     if (b->size >= UDP_HEADER_LEN) {
 251         const struct udp_header *udp = b->data;
 252
 253         flow->tp_src = udp->udp_src;
 254         flow->tp_dst = udp->udp_dst;
 255     }
 256 }
 257
 258 static void
 259 parse_sctp(struct ofpbuf *b, struct flow *flow)
 260 {
 261     if (b->size >= SCTP_HEADER_LEN) {
 262         const struct sctp_header *sctp = b->data;
 263
 264         flow->tp_src = sctp->sctp_src;
 265         flow->tp_dst = sctp->sctp_dst;
 266     }
 267 }
 268
 269 static void
 270 parse_icmpv6(struct ofpbuf *b, struct flow *flow)
 271 {
 272     const struct icmp6_hdr *icmp = pull_icmpv6(b);
 273
 274     if (!icmp) {
 275         return;
 276     }
 277
 278     /* The ICMPv6 type and code fields use the 16-bit transport port
 279      * fields, so we need to store them in 16-bit network byte order. */
 280     flow->tp_src = htons(icmp->icmp6_type);
 281     flow->tp_dst = htons(icmp->icmp6_code);
 282
 283     if (icmp->icmp6_code == 0 &&
 284         (icmp->icmp6_type == ND_NEIGHBOR_SOLICIT ||
 285          icmp->icmp6_type == ND_NEIGHBOR_ADVERT)) {
 286         const struct in6_addr *nd_target;
 287
 288         nd_target = ofpbuf_try_pull(b, sizeof *nd_target);
 289         if (!nd_target) {
 290             return;
 291         }
 292         flow->nd_target = *nd_target;
 293
 294         while (b->size >= 8) {
 295             /* The minimum size of an option is 8 bytes, which also is
 296              * the size of Ethernet link-layer options. */
 297             const struct nd_opt_hdr *nd_opt = b->data;
 298             int opt_len = nd_opt->nd_opt_len * 8;
 299
 300             if (!opt_len || opt_len > b->size) {
 301                 goto invalid;
 302             }
 303
 304             /* Store the link layer address if the appropriate option is
 305              * provided.  It is considered an error if the same link
 306              * layer option is specified twice. */
 307             if (nd_opt->nd_opt_type == ND_OPT_SOURCE_LINKADDR
 308                     && opt_len == 8) {
 309                 if (eth_addr_is_zero(flow->arp_sha)) {
 310                     memcpy(flow->arp_sha, nd_opt + 1, ETH_ADDR_LEN);
 311                 } else {
 312                     goto invalid;
 313                 }
 314             } else if (nd_opt->nd_opt_type == ND_OPT_TARGET_LINKADDR
 315                     && opt_len == 8) {
 316                 if (eth_addr_is_zero(flow->arp_tha)) {
 317                     memcpy(flow->arp_tha, nd_opt + 1, ETH_ADDR_LEN);
 318                 } else {
 319                     goto invalid;
 320                 }
 321             }
 322
 323             if (!ofpbuf_try_pull(b, opt_len)) {
 324                 goto invalid;
 325             }
 326         }
 327     }
 328
 329     return;
 330
 331 invalid:
 332     memset(&flow->nd_target, 0, sizeof(flow->nd_target));
 333     memset(flow->arp_sha, 0, sizeof(flow->arp_sha));
 334     memset(flow->arp_tha, 0, sizeof(flow->arp_tha));
 335
 336     return;
 337 }
 338
 339 /* Initializes 'flow' members from 'packet' and 'md'
 340  *
 341  * Initializes 'packet' header l2 pointer to the start of the Ethernet
 342  * header, and the layer offsets as follows:
 343  *
 344  *    - packet->l2_5_ofs to the start of the MPLS shim header, or UINT16_MAX
 345  *      when there is no MPLS shim header.
 346  *
 347  *    - packet->l3_ofs to just past the Ethernet header, or just past the
 348  *      vlan_header if one is present, to the first byte of the payload of the
 349  *      Ethernet frame.  UINT16_MAX if the frame is too short to contain an
 350  *      Ethernet header.
 351  *
 352  *    - packet->l4_ofs to just past the IPv4 header, if one is present and
 353  *      has at least the content used for the fields of interest for the flow,
 354  *      otherwise UINT16_MAX.
 355  */
 356 void
 357 flow_extract(struct ofpbuf *packet, const struct pkt_metadata *md,
 358              struct flow *flow)
 359 {
 360     struct ofpbuf b = *packet;
 361     struct eth_header *eth;
 362
 363     COVERAGE_INC(flow_extract);
 364
 365     memset(flow, 0, sizeof *flow);
 366
 367     if (md) {
 368         flow->tunnel = md->tunnel;
 369         flow->in_port = md->in_port;
 370         flow->skb_priority = md->skb_priority;
 371         flow->pkt_mark = md->pkt_mark;
 372     }
 373
 374     packet->l2   = b.data;
 375     ofpbuf_set_l2_5(packet, NULL);
 376     ofpbuf_set_l3(packet, NULL);
 377     ofpbuf_set_l4(packet, NULL);
 378
 379     if (b.size < sizeof *eth) {
 380         return;
 381     }
 382
 383     /* Link layer. */
 384     eth = b.data;
 385     memcpy(flow->dl_src, eth->eth_src, ETH_ADDR_LEN);
 386     memcpy(flow->dl_dst, eth->eth_dst, ETH_ADDR_LEN);
 387
 388     /* dl_type, vlan_tci. */
 389     ofpbuf_pull(&b, ETH_ADDR_LEN * 2);
 390     if (eth->eth_type == htons(ETH_TYPE_VLAN)) {
 391         parse_vlan(&b, flow);
 392     }
 393     flow->dl_type = parse_ethertype(&b);
 394
 395     /* Parse mpls, copy l3 ttl. */
 396     if (eth_type_mpls(flow->dl_type)) {
 397         ofpbuf_set_l2_5(packet, b.data);
 398         parse_mpls(&b, flow);
 399     }
 400
 401     /* Network layer. */
 402     ofpbuf_set_l3(packet, b.data);
 403     if (flow->dl_type == htons(ETH_TYPE_IP)) {
 404         const struct ip_header *nh = pull_ip(&b);
 405         if (nh) {
 406             ofpbuf_set_l4(packet, b.data);
 407
 408             flow->nw_src = get_16aligned_be32(&nh->ip_src);
 409             flow->nw_dst = get_16aligned_be32(&nh->ip_dst);
 410             flow->nw_proto = nh->ip_proto;
 411
 412             flow->nw_tos = nh->ip_tos;
 413             if (IP_IS_FRAGMENT(nh->ip_frag_off)) {
 414                 flow->nw_frag = FLOW_NW_FRAG_ANY;
 415                 if (nh->ip_frag_off & htons(IP_FRAG_OFF_MASK)) {
 416                     flow->nw_frag |= FLOW_NW_FRAG_LATER;
 417                 }
 418             }
 419             flow->nw_ttl = nh->ip_ttl;
 420
 421             if (!(nh->ip_frag_off & htons(IP_FRAG_OFF_MASK))) {
 422                 if (flow->nw_proto == IPPROTO_TCP) {
 423                     parse_tcp(&b, flow);
 424                 } else if (flow->nw_proto == IPPROTO_UDP) {
 425                     parse_udp(&b, flow);
 426                 } else if (flow->nw_proto == IPPROTO_SCTP) {
 427                     parse_sctp(&b, flow);
 428                 } else if (flow->nw_proto == IPPROTO_ICMP) {
 429                     const struct icmp_header *icmp = pull_icmp(&b);
 430                     if (icmp) {
 431                         flow->tp_src = htons(icmp->icmp_type);
 432                         flow->tp_dst = htons(icmp->icmp_code);
 433                     }
 434                 }
 435             }
 436         }
 437     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
 438         if (parse_ipv6(&b, flow)) {
 439             return;
 440         }
 441
 442         ofpbuf_set_l4(packet, b.data);
 443         if (flow->nw_proto == IPPROTO_TCP) {
 444             parse_tcp(&b, flow);
 445         } else if (flow->nw_proto == IPPROTO_UDP) {
 446             parse_udp(&b, flow);
 447         } else if (flow->nw_proto == IPPROTO_SCTP) {
 448             parse_sctp(&b, flow);
 449         } else if (flow->nw_proto == IPPROTO_ICMPV6) {
 450             parse_icmpv6(&b, flow);
 451         }
 452     } else if (flow->dl_type == htons(ETH_TYPE_ARP) ||
 453                flow->dl_type == htons(ETH_TYPE_RARP)) {
 454         const struct arp_eth_header *arp = pull_arp(&b);
 455         if (arp && arp->ar_hrd == htons(1)
 456             && arp->ar_pro == htons(ETH_TYPE_IP)
 457             && arp->ar_hln == ETH_ADDR_LEN
 458             && arp->ar_pln == 4) {
 459             /* We only match on the lower 8 bits of the opcode. */
 460             if (ntohs(arp->ar_op) <= 0xff) {
 461                 flow->nw_proto = ntohs(arp->ar_op);
 462             }
 463
 464             flow->nw_src = get_16aligned_be32(&arp->ar_spa);
 465             flow->nw_dst = get_16aligned_be32(&arp->ar_tpa);
 466             memcpy(flow->arp_sha, arp->ar_sha, ETH_ADDR_LEN);
 467             memcpy(flow->arp_tha, arp->ar_tha, ETH_ADDR_LEN);
 468         }
 469     }
 470 }
 471
 472 /* For every bit of a field that is wildcarded in 'wildcards', sets the
 473  * corresponding bit in 'flow' to zero. */
 474 void
 475 flow_zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards)
 476 {
 477     uint32_t *flow_u32 = (uint32_t *) flow;
 478     const uint32_t *wc_u32 = (const uint32_t *) &wildcards->masks;
 479     size_t i;
 480
 481     for (i = 0; i < FLOW_U32S; i++) {
 482         flow_u32[i] &= wc_u32[i];
 483     }
 484 }
 485
 486 void
 487 flow_unwildcard_tp_ports(const struct flow *flow, struct flow_wildcards *wc)
 488 {
 489     if (flow->nw_proto != IPPROTO_ICMP) {
 490         memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
 491         memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
 492     } else {
 493         wc->masks.tp_src = htons(0xff);
 494         wc->masks.tp_dst = htons(0xff);
 495     }
 496 }
 497
 498 /* Initializes 'fmd' with the metadata found in 'flow'. */
 499 void
 500 flow_get_metadata(const struct flow *flow, struct flow_metadata *fmd)
 501 {
 502     BUILD_ASSERT_DECL(FLOW_WC_SEQ == 25);
 503
 504     fmd->dp_hash = flow->dp_hash;
 505     fmd->recirc_id = flow->recirc_id;
 506     fmd->tun_id = flow->tunnel.tun_id;
 507     fmd->tun_src = flow->tunnel.ip_src;
 508     fmd->tun_dst = flow->tunnel.ip_dst;
 509     fmd->metadata = flow->metadata;
 510     memcpy(fmd->regs, flow->regs, sizeof fmd->regs);
 511     fmd->pkt_mark = flow->pkt_mark;
 512     fmd->in_port = flow->in_port.ofp_port;
 513 }
 514
 515 char *
 516 flow_to_string(const struct flow *flow)
 517 {
 518     struct ds ds = DS_EMPTY_INITIALIZER;
 519     flow_format(&ds, flow);
 520     return ds_cstr(&ds);
 521 }
 522
 523 const char *
 524 flow_tun_flag_to_string(uint32_t flags)
 525 {
 526     switch (flags) {
 527     case FLOW_TNL_F_DONT_FRAGMENT:
 528         return "df";
 529     case FLOW_TNL_F_CSUM:
 530         return "csum";
 531     case FLOW_TNL_F_KEY:
 532         return "key";
 533     default:
 534         return NULL;
 535     }
 536 }
 537
 538 void
 539 format_flags(struct ds *ds, const char *(*bit_to_string)(uint32_t),
 540              uint32_t flags, char del)
 541 {
 542     uint32_t bad = 0;
 543
 544     if (!flags) {
 545         return;
 546     }
 547     while (flags) {
 548         uint32_t bit = rightmost_1bit(flags);
 549         const char *s;
 550
 551         s = bit_to_string(bit);
 552         if (s) {
 553             ds_put_format(ds, "%s%c", s, del);
 554         } else {
 555             bad |= bit;
 556         }
 557
 558         flags &= ~bit;
 559     }
 560
 561     if (bad) {
 562         ds_put_format(ds, "0x%"PRIx32"%c", bad, del);
 563     }
 564     ds_chomp(ds, del);
 565 }
 566
 567 void
 568 format_flags_masked(struct ds *ds, const char *name,
 569                     const char *(*bit_to_string)(uint32_t), uint32_t flags,
 570                     uint32_t mask)
 571 {
 572     if (name) {
 573         ds_put_format(ds, "%s=", name);
 574     }
 575     while (mask) {
 576         uint32_t bit = rightmost_1bit(mask);
 577         const char *s = bit_to_string(bit);
 578
 579         ds_put_format(ds, "%s%s", (flags & bit) ? "+" : "-",
 580                       s ? s : "[Unknown]");
 581         mask &= ~bit;
 582     }
 583 }
 584
 585 void
 586 flow_format(struct ds *ds, const struct flow *flow)
 587 {
 588     struct match match;
 589
 590     match_wc_init(&match, flow);
 591     match_format(&match, ds, OFP_DEFAULT_PRIORITY);
 592 }
 593
 594 void
 595 flow_print(FILE *stream, const struct flow *flow)
 596 {
 597     char *s = flow_to_string(flow);
 598     fputs(s, stream);
 599     free(s);
 600 }
 601 \f
 602 /* flow_wildcards functions. */
 603
 604 /* Initializes 'wc' as a set of wildcards that matches every packet. */
 605 void
 606 flow_wildcards_init_catchall(struct flow_wildcards *wc)
 607 {
 608     memset(&wc->masks, 0, sizeof wc->masks);
 609 }
 610
 611 /* Clear the metadata and register wildcard masks. They are not packet
 612  * header fields. */
 613 void
 614 flow_wildcards_clear_non_packet_fields(struct flow_wildcards *wc)
 615 {
 616     memset(&wc->masks.metadata, 0, sizeof wc->masks.metadata);
 617     memset(&wc->masks.regs, 0, sizeof wc->masks.regs);
 618 }
 619
 620 /* Returns true if 'wc' matches every packet, false if 'wc' fixes any bits or
 621  * fields. */
 622 bool
 623 flow_wildcards_is_catchall(const struct flow_wildcards *wc)
 624 {
 625     const uint32_t *wc_u32 = (const uint32_t *) &wc->masks;
 626     size_t i;
 627
 628     for (i = 0; i < FLOW_U32S; i++) {
 629         if (wc_u32[i]) {
 630             return false;
 631         }
 632     }
 633     return true;
 634 }
 635
 636 /* Sets 'dst' as the bitwise AND of wildcards in 'src1' and 'src2'.
 637  * That is, a bit or a field is wildcarded in 'dst' if it is wildcarded
 638  * in 'src1' or 'src2' or both.  */
 639 void
 640 flow_wildcards_and(struct flow_wildcards *dst,
 641                    const struct flow_wildcards *src1,
 642                    const struct flow_wildcards *src2)
 643 {
 644     uint32_t *dst_u32 = (uint32_t *) &dst->masks;
 645     const uint32_t *src1_u32 = (const uint32_t *) &src1->masks;
 646     const uint32_t *src2_u32 = (const uint32_t *) &src2->masks;
 647     size_t i;
 648
 649     for (i = 0; i < FLOW_U32S; i++) {
 650         dst_u32[i] = src1_u32[i] & src2_u32[i];
 651     }
 652 }
 653
 654 /* Sets 'dst' as the bitwise OR of wildcards in 'src1' and 'src2'.  That
 655  * is, a bit or a field is wildcarded in 'dst' if it is neither
 656  * wildcarded in 'src1' nor 'src2'. */
 657 void
 658 flow_wildcards_or(struct flow_wildcards *dst,
 659                   const struct flow_wildcards *src1,
 660                   const struct flow_wildcards *src2)
 661 {
 662     uint32_t *dst_u32 = (uint32_t *) &dst->masks;
 663     const uint32_t *src1_u32 = (const uint32_t *) &src1->masks;
 664     const uint32_t *src2_u32 = (const uint32_t *) &src2->masks;
 665     size_t i;
 666
 667     for (i = 0; i < FLOW_U32S; i++) {
 668         dst_u32[i] = src1_u32[i] | src2_u32[i];
 669     }
 670 }
 671
 672 /* Perform a bitwise OR of miniflow 'src' flow data with the equivalent
 673  * fields in 'dst', storing the result in 'dst'. */
 674 static void
 675 flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
 676 {
 677     uint32_t *dst_u32 = (uint32_t *) dst;
 678     const uint32_t *p = src->values;
 679     uint64_t map;
 680
 681     for (map = src->map; map; map = zero_rightmost_1bit(map)) {
 682         dst_u32[raw_ctz(map)] |= *p++;
 683     }
 684 }
 685
 686 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
 687 void
 688 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
 689                              const struct minimask *mask)
 690 {
 691     flow_union_with_miniflow(&wc->masks, &mask->masks);
 692 }
 693
 694 uint64_t
 695 miniflow_get_map_in_range(const struct miniflow *miniflow,
 696                           uint8_t start, uint8_t end, unsigned int *offset)
 697 {
 698     uint64_t map = miniflow->map;
 699     *offset = 0;
 700
 701     if (start > 0) {
 702         uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
 703         *offset = count_1bits(map & msk);
 704         map &= ~msk;
 705     }
 706     if (end < FLOW_U32S) {
 707         uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
 708         map &= msk;
 709     }
 710     return map;
 711 }
 712
 713 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
 714  * in range [start, end). */
 715 void
 716 flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
 717                                    const struct minimask *mask,
 718                                    uint8_t start, uint8_t end)
 719 {
 720     uint32_t *dst_u32 = (uint32_t *)&wc->masks;
 721     unsigned int offset;
 722     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
 723                                              &offset);
 724     const uint32_t *p = mask->masks.values + offset;
 725
 726     for (; map; map = zero_rightmost_1bit(map)) {
 727         dst_u32[raw_ctz(map)] |= *p++;
 728     }
 729 }
 730
 731 /* Returns a hash of the wildcards in 'wc'. */
 732 uint32_t
 733 flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis)
 734 {
 735     return flow_hash(&wc->masks, basis);
 736 }
 737
 738 /* Returns true if 'a' and 'b' represent the same wildcards, false if they are
 739  * different. */
 740 bool
 741 flow_wildcards_equal(const struct flow_wildcards *a,
 742                      const struct flow_wildcards *b)
 743 {
 744     return flow_equal(&a->masks, &b->masks);
 745 }
 746
 747 /* Returns true if at least one bit or field is wildcarded in 'a' but not in
 748  * 'b', false otherwise. */
 749 bool
 750 flow_wildcards_has_extra(const struct flow_wildcards *a,
 751                          const struct flow_wildcards *b)
 752 {
 753     const uint32_t *a_u32 = (const uint32_t *) &a->masks;
 754     const uint32_t *b_u32 = (const uint32_t *) &b->masks;
 755     size_t i;
 756
 757     for (i = 0; i < FLOW_U32S; i++) {
 758         if ((a_u32[i] & b_u32[i]) != b_u32[i]) {
 759             return true;
 760         }
 761     }
 762     return false;
 763 }
 764
 765 /* Returns true if 'a' and 'b' are equal, except that 0-bits (wildcarded bits)
 766  * in 'wc' do not need to be equal in 'a' and 'b'. */
 767 bool
 768 flow_equal_except(const struct flow *a, const struct flow *b,
 769                   const struct flow_wildcards *wc)
 770 {
 771     const uint32_t *a_u32 = (const uint32_t *) a;
 772     const uint32_t *b_u32 = (const uint32_t *) b;
 773     const uint32_t *wc_u32 = (const uint32_t *) &wc->masks;
 774     size_t i;
 775
 776     for (i = 0; i < FLOW_U32S; i++) {
 777         if ((a_u32[i] ^ b_u32[i]) & wc_u32[i]) {
 778             return false;
 779         }
 780     }
 781     return true;
 782 }
 783
 784 /* Sets the wildcard mask for register 'idx' in 'wc' to 'mask'.
 785  * (A 0-bit indicates a wildcard bit.) */
 786 void
 787 flow_wildcards_set_reg_mask(struct flow_wildcards *wc, int idx, uint32_t mask)
 788 {
 789     wc->masks.regs[idx] = mask;
 790 }
 791
 792 /* Calculates the 5-tuple hash from the given flow. */
 793 uint32_t
 794 flow_hash_5tuple(const struct flow *flow, uint32_t basis)
 795 {
 796     uint32_t hash = 0;
 797
 798     if (!flow) {
 799         return 0;
 800     }
 801
 802     hash = mhash_add(basis, (OVS_FORCE uint32_t) flow->nw_src);
 803     hash = mhash_add(hash, (OVS_FORCE uint32_t) flow->nw_dst);
 804     hash = mhash_add(hash, ((OVS_FORCE uint32_t) flow->tp_src << 16)
 805                            | (OVS_FORCE uint32_t) flow->tp_dst);
 806     hash = mhash_add(hash, flow->nw_proto);
 807
 808     return mhash_finish(hash, 13);
 809 }
 810
 811 /* Hashes 'flow' based on its L2 through L4 protocol information. */
 812 uint32_t
 813 flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis)
 814 {
 815     struct {
 816         union {
 817             ovs_be32 ipv4_addr;
 818             struct in6_addr ipv6_addr;
 819         };
 820         ovs_be16 eth_type;
 821         ovs_be16 vlan_tci;
 822         ovs_be16 tp_port;
 823         uint8_t eth_addr[ETH_ADDR_LEN];
 824         uint8_t ip_proto;
 825     } fields;
 826
 827     int i;
 828
 829     memset(&fields, 0, sizeof fields);
 830     for (i = 0; i < ETH_ADDR_LEN; i++) {
 831         fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
 832     }
 833     fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
 834     fields.eth_type = flow->dl_type;
 835
 836     /* UDP source and destination port are not taken into account because they
 837      * will not necessarily be symmetric in a bidirectional flow. */
 838     if (fields.eth_type == htons(ETH_TYPE_IP)) {
 839         fields.ipv4_addr = flow->nw_src ^ flow->nw_dst;
 840         fields.ip_proto = flow->nw_proto;
 841         if (fields.ip_proto == IPPROTO_TCP || fields.ip_proto == IPPROTO_SCTP) {
 842             fields.tp_port = flow->tp_src ^ flow->tp_dst;
 843         }
 844     } else if (fields.eth_type == htons(ETH_TYPE_IPV6)) {
 845         const uint8_t *a = &flow->ipv6_src.s6_addr[0];
 846         const uint8_t *b = &flow->ipv6_dst.s6_addr[0];
 847         uint8_t *ipv6_addr = &fields.ipv6_addr.s6_addr[0];
 848
 849         for (i=0; i<16; i++) {
 850             ipv6_addr[i] = a[i] ^ b[i];
 851         }
 852         fields.ip_proto = flow->nw_proto;
 853         if (fields.ip_proto == IPPROTO_TCP || fields.ip_proto == IPPROTO_SCTP) {
 854             fields.tp_port = flow->tp_src ^ flow->tp_dst;
 855         }
 856     }
 857     return jhash_bytes(&fields, sizeof fields, basis);
 858 }
 859
 860 /* Initialize a flow with random fields that matter for nx_hash_fields. */
 861 void
 862 flow_random_hash_fields(struct flow *flow)
 863 {
 864     uint16_t rnd = random_uint16();
 865
 866     /* Initialize to all zeros. */
 867     memset(flow, 0, sizeof *flow);
 868
 869     eth_addr_random(flow->dl_src);
 870     eth_addr_random(flow->dl_dst);
 871
 872     flow->vlan_tci = (OVS_FORCE ovs_be16) (random_uint16() & VLAN_VID_MASK);
 873
 874     /* Make most of the random flows IPv4, some IPv6, and rest random. */
 875     flow->dl_type = rnd < 0x8000 ? htons(ETH_TYPE_IP) :
 876         rnd < 0xc000 ? htons(ETH_TYPE_IPV6) : (OVS_FORCE ovs_be16)rnd;
 877
 878     if (dl_type_is_ip_any(flow->dl_type)) {
 879         if (flow->dl_type == htons(ETH_TYPE_IP)) {
 880             flow->nw_src = (OVS_FORCE ovs_be32)random_uint32();
 881             flow->nw_dst = (OVS_FORCE ovs_be32)random_uint32();
 882         } else {
 883             random_bytes(&flow->ipv6_src, sizeof flow->ipv6_src);
 884             random_bytes(&flow->ipv6_dst, sizeof flow->ipv6_dst);
 885         }
 886         /* Make most of IP flows TCP, some UDP or SCTP, and rest random. */
 887         rnd = random_uint16();
 888         flow->nw_proto = rnd < 0x8000 ? IPPROTO_TCP :
 889             rnd < 0xc000 ? IPPROTO_UDP :
 890             rnd < 0xd000 ? IPPROTO_SCTP : (uint8_t)rnd;
 891         if (flow->nw_proto == IPPROTO_TCP ||
 892             flow->nw_proto == IPPROTO_UDP ||
 893             flow->nw_proto == IPPROTO_SCTP) {
 894             flow->tp_src = (OVS_FORCE ovs_be16)random_uint16();
 895             flow->tp_dst = (OVS_FORCE ovs_be16)random_uint16();
 896         }
 897     }
 898 }
 899
 900 /* Masks the fields in 'wc' that are used by the flow hash 'fields'. */
 901 void
 902 flow_mask_hash_fields(const struct flow *flow, struct flow_wildcards *wc,
 903                       enum nx_hash_fields fields)
 904 {
 905     switch (fields) {
 906     case NX_HASH_FIELDS_ETH_SRC:
 907         memset(&wc->masks.dl_src, 0xff, sizeof wc->masks.dl_src);
 908         break;
 909
 910     case NX_HASH_FIELDS_SYMMETRIC_L4:
 911         memset(&wc->masks.dl_src, 0xff, sizeof wc->masks.dl_src);
 912         memset(&wc->masks.dl_dst, 0xff, sizeof wc->masks.dl_dst);
 913         if (flow->dl_type == htons(ETH_TYPE_IP)) {
 914             memset(&wc->masks.nw_src, 0xff, sizeof wc->masks.nw_src);
 915             memset(&wc->masks.nw_dst, 0xff, sizeof wc->masks.nw_dst);
 916         } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
 917             memset(&wc->masks.ipv6_src, 0xff, sizeof wc->masks.ipv6_src);
 918             memset(&wc->masks.ipv6_dst, 0xff, sizeof wc->masks.ipv6_dst);
 919         }
 920         if (is_ip_any(flow)) {
 921             memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
 922             flow_unwildcard_tp_ports(flow, wc);
 923         }
 924         wc->masks.vlan_tci |= htons(VLAN_VID_MASK | VLAN_CFI);
 925         break;
 926
 927     default:
 928         OVS_NOT_REACHED();
 929     }
 930 }
 931
 932 /* Hashes the portions of 'flow' designated by 'fields'. */
 933 uint32_t
 934 flow_hash_fields(const struct flow *flow, enum nx_hash_fields fields,
 935                  uint16_t basis)
 936 {
 937     switch (fields) {
 938
 939     case NX_HASH_FIELDS_ETH_SRC:
 940         return jhash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
 941
 942     case NX_HASH_FIELDS_SYMMETRIC_L4:
 943         return flow_hash_symmetric_l4(flow, basis);
 944     }
 945
 946     OVS_NOT_REACHED();
 947 }
 948
 949 /* Returns a string representation of 'fields'. */
 950 const char *
 951 flow_hash_fields_to_str(enum nx_hash_fields fields)
 952 {
 953     switch (fields) {
 954     case NX_HASH_FIELDS_ETH_SRC: return "eth_src";
 955     case NX_HASH_FIELDS_SYMMETRIC_L4: return "symmetric_l4";
 956     default: return "<unknown>";
 957     }
 958 }
 959
 960 /* Returns true if the value of 'fields' is supported. Otherwise false. */
 961 bool
 962 flow_hash_fields_valid(enum nx_hash_fields fields)
 963 {
 964     return fields == NX_HASH_FIELDS_ETH_SRC
 965         || fields == NX_HASH_FIELDS_SYMMETRIC_L4;
 966 }
 967
 968 /* Returns a hash value for the bits of 'flow' that are active based on
 969  * 'wc', given 'basis'. */
 970 uint32_t
 971 flow_hash_in_wildcards(const struct flow *flow,
 972                        const struct flow_wildcards *wc, uint32_t basis)
 973 {
 974     const uint32_t *wc_u32 = (const uint32_t *) &wc->masks;
 975     const uint32_t *flow_u32 = (const uint32_t *) flow;
 976     uint32_t hash;
 977     size_t i;
 978
 979     hash = basis;
 980     for (i = 0; i < FLOW_U32S; i++) {
 981         hash = mhash_add(hash, flow_u32[i] & wc_u32[i]);
 982     }
 983     return mhash_finish(hash, 4 * FLOW_U32S);
 984 }
 985
 986 /* Sets the VLAN VID that 'flow' matches to 'vid', which is interpreted as an
 987  * OpenFlow 1.0 "dl_vlan" value:
 988  *
 989  *      - If it is in the range 0...4095, 'flow->vlan_tci' is set to match
 990  *        that VLAN.  Any existing PCP match is unchanged (it becomes 0 if
 991  *        'flow' previously matched packets without a VLAN header).
 992  *
 993  *      - If it is OFP_VLAN_NONE, 'flow->vlan_tci' is set to match a packet
 994  *        without a VLAN tag.
 995  *
 996  *      - Other values of 'vid' should not be used. */
 997 void
 998 flow_set_dl_vlan(struct flow *flow, ovs_be16 vid)
 999 {
1000     if (vid == htons(OFP10_VLAN_NONE)) {
1001         flow->vlan_tci = htons(0);
1002     } else {
1003         vid &= htons(VLAN_VID_MASK);
1004         flow->vlan_tci &= ~htons(VLAN_VID_MASK);
1005         flow->vlan_tci |= htons(VLAN_CFI) | vid;
1006     }
1007 }
1008
1009 /* Sets the VLAN VID that 'flow' matches to 'vid', which is interpreted as an
1010  * OpenFlow 1.2 "vlan_vid" value, that is, the low 13 bits of 'vlan_tci' (VID
1011  * plus CFI). */
1012 void
1013 flow_set_vlan_vid(struct flow *flow, ovs_be16 vid)
1014 {
1015     ovs_be16 mask = htons(VLAN_VID_MASK | VLAN_CFI);
1016     flow->vlan_tci &= ~mask;
1017     flow->vlan_tci |= vid & mask;
1018 }
1019
1020 /* Sets the VLAN PCP that 'flow' matches to 'pcp', which should be in the
1021  * range 0...7.
1022  *
1023  * This function has no effect on the VLAN ID that 'flow' matches.
1024  *
1025  * After calling this function, 'flow' will not match packets without a VLAN
1026  * header. */
1027 void
1028 flow_set_vlan_pcp(struct flow *flow, uint8_t pcp)
1029 {
1030     pcp &= 0x07;
1031     flow->vlan_tci &= ~htons(VLAN_PCP_MASK);
1032     flow->vlan_tci |= htons((pcp << VLAN_PCP_SHIFT) | VLAN_CFI);
1033 }
1034
1035 /* Returns the number of MPLS LSEs present in 'flow'
1036  *
1037  * Returns 0 if the 'dl_type' of 'flow' is not an MPLS ethernet type.
1038  * Otherwise traverses 'flow''s MPLS label stack stopping at the
1039  * first entry that has the BoS bit set. If no such entry exists then
1040  * the maximum number of LSEs that can be stored in 'flow' is returned.
1041  */
1042 int
1043 flow_count_mpls_labels(const struct flow *flow, struct flow_wildcards *wc)
1044 {
1045     if (wc) {
1046         wc->masks.dl_type = OVS_BE16_MAX;
1047     }
1048     if (eth_type_mpls(flow->dl_type)) {
1049         int i;
1050         int len = FLOW_MAX_MPLS_LABELS;
1051
1052         for (i = 0; i < len; i++) {
1053             if (wc) {
1054                 wc->masks.mpls_lse[i] |= htonl(MPLS_BOS_MASK);
1055             }
1056             if (flow->mpls_lse[i] & htonl(MPLS_BOS_MASK)) {
1057                 return i + 1;
1058             }
1059         }
1060
1061         return len;
1062     } else {
1063         return 0;
1064     }
1065 }
1066
1067 /* Returns the number consecutive of MPLS LSEs, starting at the
1068  * innermost LSE, that are common in 'a' and 'b'.
1069  *
1070  * 'an' must be flow_count_mpls_labels(a).
1071  * 'bn' must be flow_count_mpls_labels(b).
1072  */
1073 int
1074 flow_count_common_mpls_labels(const struct flow *a, int an,
1075                               const struct flow *b, int bn,
1076                               struct flow_wildcards *wc)
1077 {
1078     int min_n = MIN(an, bn);
1079     if (min_n == 0) {
1080         return 0;
1081     } else {
1082         int common_n = 0;
1083         int a_last = an - 1;
1084         int b_last = bn - 1;
1085         int i;
1086
1087         for (i = 0; i < min_n; i++) {
1088             if (wc) {
1089                 wc->masks.mpls_lse[a_last - i] = OVS_BE32_MAX;
1090                 wc->masks.mpls_lse[b_last - i] = OVS_BE32_MAX;
1091             }
1092             if (a->mpls_lse[a_last - i] != b->mpls_lse[b_last - i]) {
1093                 break;
1094             } else {
1095                 common_n++;
1096             }
1097         }
1098
1099         return common_n;
1100     }
1101 }
1102
1103 /* Adds a new outermost MPLS label to 'flow' and changes 'flow''s Ethernet type
1104  * to 'mpls_eth_type', which must be an MPLS Ethertype.
1105  *
1106  * If the new label is the first MPLS label in 'flow', it is generated as;
1107  *
1108  *     - label: 2, if 'flow' is IPv6, otherwise 0.
1109  *
1110  *     - TTL: IPv4 or IPv6 TTL, if present and nonzero, otherwise 64.
1111  *
1112  *     - TC: IPv4 or IPv6 TOS, if present, otherwise 0.
1113  *
1114  *     - BoS: 1.
1115  *
1116  * If the new label is the second or label MPLS label in 'flow', it is
1117  * generated as;
1118  *
1119  *     - label: Copied from outer label.
1120  *
1121  *     - TTL: Copied from outer label.
1122  *
1123  *     - TC: Copied from outer label.
1124  *
1125  *     - BoS: 0.
1126  *
1127  * 'n' must be flow_count_mpls_labels(flow).  'n' must be less than
1128  * FLOW_MAX_MPLS_LABELS (because otherwise flow->mpls_lse[] would overflow).
1129  */
1130 void
1131 flow_push_mpls(struct flow *flow, int n, ovs_be16 mpls_eth_type,
1132                struct flow_wildcards *wc)
1133 {
1134     ovs_assert(eth_type_mpls(mpls_eth_type));
1135     ovs_assert(n < FLOW_MAX_MPLS_LABELS);
1136
1137     memset(wc->masks.mpls_lse, 0xff, sizeof wc->masks.mpls_lse);
1138     if (n) {
1139         int i;
1140
1141         for (i = n; i >= 1; i--) {
1142             flow->mpls_lse[i] = flow->mpls_lse[i - 1];
1143         }
1144         flow->mpls_lse[0] = (flow->mpls_lse[1]
1145                              & htonl(~MPLS_BOS_MASK));
1146     } else {
1147         int label = 0;          /* IPv4 Explicit Null. */
1148         int tc = 0;
1149         int ttl = 64;
1150
1151         if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
1152             label = 2;
1153         }
1154
1155         if (is_ip_any(flow)) {
1156             tc = (flow->nw_tos & IP_DSCP_MASK) >> 2;
1157             wc->masks.nw_tos |= IP_DSCP_MASK;
1158
1159             if (flow->nw_ttl) {
1160                 ttl = flow->nw_ttl;
1161             }
1162             wc->masks.nw_ttl = 0xff;
1163         }
1164
1165         flow->mpls_lse[0] = set_mpls_lse_values(ttl, tc, 1, htonl(label));
1166
1167         /* Clear all L3 and L4 fields. */
1168         BUILD_ASSERT(FLOW_WC_SEQ == 25);
1169         memset((char *) flow + FLOW_SEGMENT_2_ENDS_AT, 0,
1170                sizeof(struct flow) - FLOW_SEGMENT_2_ENDS_AT);
1171     }
1172     flow->dl_type = mpls_eth_type;
1173 }
1174
1175 /* Tries to remove the outermost MPLS label from 'flow'.  Returns true if
1176  * successful, false otherwise.  On success, sets 'flow''s Ethernet type to
1177  * 'eth_type'.
1178  *
1179  * 'n' must be flow_count_mpls_labels(flow). */
1180 bool
1181 flow_pop_mpls(struct flow *flow, int n, ovs_be16 eth_type,
1182               struct flow_wildcards *wc)
1183 {
1184     int i;
1185
1186     if (n == 0) {
1187         /* Nothing to pop. */
1188         return false;
1189     } else if (n == FLOW_MAX_MPLS_LABELS
1190                && !(flow->mpls_lse[n - 1] & htonl(MPLS_BOS_MASK))) {
1191         /* Can't pop because we don't know what to fill in mpls_lse[n - 1]. */
1192         return false;
1193     }
1194
1195     memset(wc->masks.mpls_lse, 0xff, sizeof wc->masks.mpls_lse);
1196     for (i = 1; i < n; i++) {
1197         flow->mpls_lse[i - 1] = flow->mpls_lse[i];
1198     }
1199     flow->mpls_lse[n - 1] = 0;
1200     flow->dl_type = eth_type;
1201     return true;
1202 }
1203
1204 /* Sets the MPLS Label that 'flow' matches to 'label', which is interpreted
1205  * as an OpenFlow 1.1 "mpls_label" value. */
1206 void
1207 flow_set_mpls_label(struct flow *flow, int idx, ovs_be32 label)
1208 {
1209     set_mpls_lse_label(&flow->mpls_lse[idx], label);
1210 }
1211
1212 /* Sets the MPLS TTL that 'flow' matches to 'ttl', which should be in the
1213  * range 0...255. */
1214 void
1215 flow_set_mpls_ttl(struct flow *flow, int idx, uint8_t ttl)
1216 {
1217     set_mpls_lse_ttl(&flow->mpls_lse[idx], ttl);
1218 }
1219
1220 /* Sets the MPLS TC that 'flow' matches to 'tc', which should be in the
1221  * range 0...7. */
1222 void
1223 flow_set_mpls_tc(struct flow *flow, int idx, uint8_t tc)
1224 {
1225     set_mpls_lse_tc(&flow->mpls_lse[idx], tc);
1226 }
1227
1228 /* Sets the MPLS BOS bit that 'flow' matches to which should be 0 or 1. */
1229 void
1230 flow_set_mpls_bos(struct flow *flow, int idx, uint8_t bos)
1231 {
1232     set_mpls_lse_bos(&flow->mpls_lse[idx], bos);
1233 }
1234
1235 /* Sets the entire MPLS LSE. */
1236 void
1237 flow_set_mpls_lse(struct flow *flow, int idx, ovs_be32 lse)
1238 {
1239     flow->mpls_lse[idx] = lse;
1240 }
1241
1242 static size_t
1243 flow_compose_l4(struct ofpbuf *b, const struct flow *flow)
1244 {
1245     size_t l4_len = 0;
1246
1247     if (!(flow->nw_frag & FLOW_NW_FRAG_ANY)
1248         || !(flow->nw_frag & FLOW_NW_FRAG_LATER)) {
1249         if (flow->nw_proto == IPPROTO_TCP) {
1250             struct tcp_header *tcp;
1251
1252             l4_len = sizeof *tcp;
1253             tcp = ofpbuf_put_zeros(b, l4_len);
1254             tcp->tcp_src = flow->tp_src;
1255             tcp->tcp_dst = flow->tp_dst;
1256             tcp->tcp_ctl = TCP_CTL(ntohs(flow->tcp_flags), 5);
1257         } else if (flow->nw_proto == IPPROTO_UDP) {
1258             struct udp_header *udp;
1259
1260             l4_len = sizeof *udp;
1261             udp = ofpbuf_put_zeros(b, l4_len);
1262             udp->udp_src = flow->tp_src;
1263             udp->udp_dst = flow->tp_dst;
1264         } else if (flow->nw_proto == IPPROTO_SCTP) {
1265             struct sctp_header *sctp;
1266
1267             l4_len = sizeof *sctp;
1268             sctp = ofpbuf_put_zeros(b, l4_len);
1269             sctp->sctp_src = flow->tp_src;
1270             sctp->sctp_dst = flow->tp_dst;
1271         } else if (flow->nw_proto == IPPROTO_ICMP) {
1272             struct icmp_header *icmp;
1273
1274             l4_len = sizeof *icmp;
1275             icmp = ofpbuf_put_zeros(b, l4_len);
1276             icmp->icmp_type = ntohs(flow->tp_src);
1277             icmp->icmp_code = ntohs(flow->tp_dst);
1278             icmp->icmp_csum = csum(icmp, ICMP_HEADER_LEN);
1279         } else if (flow->nw_proto == IPPROTO_ICMPV6) {
1280             struct icmp6_hdr *icmp;
1281
1282             l4_len = sizeof *icmp;
1283             icmp = ofpbuf_put_zeros(b, l4_len);
1284             icmp->icmp6_type = ntohs(flow->tp_src);
1285             icmp->icmp6_code = ntohs(flow->tp_dst);
1286
1287             if (icmp->icmp6_code == 0 &&
1288                 (icmp->icmp6_type == ND_NEIGHBOR_SOLICIT ||
1289                  icmp->icmp6_type == ND_NEIGHBOR_ADVERT)) {
1290                 struct in6_addr *nd_target;
1291                 struct nd_opt_hdr *nd_opt;
1292
1293                 l4_len += sizeof *nd_target;
1294                 nd_target = ofpbuf_put_zeros(b, sizeof *nd_target);
1295                 *nd_target = flow->nd_target;
1296
1297                 if (!eth_addr_is_zero(flow->arp_sha)) {
1298                     l4_len += 8;
1299                     nd_opt = ofpbuf_put_zeros(b, 8);
1300                     nd_opt->nd_opt_len = 1;
1301                     nd_opt->nd_opt_type = ND_OPT_SOURCE_LINKADDR;
1302                     memcpy(nd_opt + 1, flow->arp_sha, ETH_ADDR_LEN);
1303                 }
1304                 if (!eth_addr_is_zero(flow->arp_tha)) {
1305                     l4_len += 8;
1306                     nd_opt = ofpbuf_put_zeros(b, 8);
1307                     nd_opt->nd_opt_len = 1;
1308                     nd_opt->nd_opt_type = ND_OPT_TARGET_LINKADDR;
1309                     memcpy(nd_opt + 1, flow->arp_tha, ETH_ADDR_LEN);
1310                 }
1311             }
1312             icmp->icmp6_cksum = (OVS_FORCE uint16_t)
1313                 csum(icmp, (char *)ofpbuf_tail(b) - (char *)icmp);
1314         }
1315     }
1316     return l4_len;
1317 }
1318
1319 /* Puts into 'b' a packet that flow_extract() would parse as having the given
1320  * 'flow'.
1321  *
1322  * (This is useful only for testing, obviously, and the packet isn't really
1323  * valid. It hasn't got some checksums filled in, for one, and lots of fields
1324  * are just zeroed.) */
1325 void
1326 flow_compose(struct ofpbuf *b, const struct flow *flow)
1327 {
1328     size_t l4_len;
1329
1330     /* eth_compose() sets l3 pointer and makes sure it is 32-bit aligned. */
1331     eth_compose(b, flow->dl_dst, flow->dl_src, ntohs(flow->dl_type), 0);
1332     if (flow->dl_type == htons(FLOW_DL_TYPE_NONE)) {
1333         struct eth_header *eth = b->l2;
1334         eth->eth_type = htons(b->size);
1335         return;
1336     }
1337
1338     if (flow->vlan_tci & htons(VLAN_CFI)) {
1339         eth_push_vlan(b, htons(ETH_TYPE_VLAN), flow->vlan_tci);
1340     }
1341
1342     if (flow->dl_type == htons(ETH_TYPE_IP)) {
1343         struct ip_header *ip;
1344
1345         ip = ofpbuf_put_zeros(b, sizeof *ip);
1346         ip->ip_ihl_ver = IP_IHL_VER(5, 4);
1347         ip->ip_tos = flow->nw_tos;
1348         ip->ip_ttl = flow->nw_ttl;
1349         ip->ip_proto = flow->nw_proto;
1350         put_16aligned_be32(&ip->ip_src, flow->nw_src);
1351         put_16aligned_be32(&ip->ip_dst, flow->nw_dst);
1352
1353         if (flow->nw_frag & FLOW_NW_FRAG_ANY) {
1354             ip->ip_frag_off |= htons(IP_MORE_FRAGMENTS);
1355             if (flow->nw_frag & FLOW_NW_FRAG_LATER) {
1356                 ip->ip_frag_off |= htons(100);
1357             }
1358         }
1359
1360         ofpbuf_set_l4(b, ofpbuf_tail(b));
1361
1362         l4_len = flow_compose_l4(b, flow);
1363
1364         ip->ip_tot_len = htons(b->l4_ofs - b->l3_ofs + l4_len);
1365         ip->ip_csum = csum(ip, sizeof *ip);
1366     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
1367         struct ovs_16aligned_ip6_hdr *nh;
1368
1369         nh = ofpbuf_put_zeros(b, sizeof *nh);
1370         put_16aligned_be32(&nh->ip6_flow, htonl(6 << 28) |
1371                            htonl(flow->nw_tos << 20) | flow->ipv6_label);
1372         nh->ip6_hlim = flow->nw_ttl;
1373         nh->ip6_nxt = flow->nw_proto;
1374
1375         memcpy(&nh->ip6_src, &flow->ipv6_src, sizeof(nh->ip6_src));
1376         memcpy(&nh->ip6_dst, &flow->ipv6_dst, sizeof(nh->ip6_dst));
1377
1378         ofpbuf_set_l4(b, ofpbuf_tail(b));
1379
1380         l4_len = flow_compose_l4(b, flow);
1381
1382         nh->ip6_plen = htons(l4_len);
1383     } else if (flow->dl_type == htons(ETH_TYPE_ARP) ||
1384                flow->dl_type == htons(ETH_TYPE_RARP)) {
1385         struct arp_eth_header *arp;
1386
1387         arp = ofpbuf_put_zeros(b, sizeof *arp);
1388         ofpbuf_set_l3(b, arp);
1389         arp->ar_hrd = htons(1);
1390         arp->ar_pro = htons(ETH_TYPE_IP);
1391         arp->ar_hln = ETH_ADDR_LEN;
1392         arp->ar_pln = 4;
1393         arp->ar_op = htons(flow->nw_proto);
1394
1395         if (flow->nw_proto == ARP_OP_REQUEST ||
1396             flow->nw_proto == ARP_OP_REPLY) {
1397             put_16aligned_be32(&arp->ar_spa, flow->nw_src);
1398             put_16aligned_be32(&arp->ar_tpa, flow->nw_dst);
1399             memcpy(arp->ar_sha, flow->arp_sha, ETH_ADDR_LEN);
1400             memcpy(arp->ar_tha, flow->arp_tha, ETH_ADDR_LEN);
1401         }
1402     }
1403
1404     if (eth_type_mpls(flow->dl_type)) {
1405         int n;
1406
1407         b->l2_5_ofs = b->l3_ofs;
1408         for (n = 1; n < FLOW_MAX_MPLS_LABELS; n++) {
1409             if (flow->mpls_lse[n - 1] & htonl(MPLS_BOS_MASK)) {
1410                 break;
1411             }
1412         }
1413         while (n > 0) {
1414             push_mpls(b, flow->dl_type, flow->mpls_lse[--n]);
1415         }
1416     }
1417 }
1418 \f
1419 /* Compressed flow. */
1420
1421 static int
1422 miniflow_n_values(const struct miniflow *flow)
1423 {
1424     return count_1bits(flow->map);
1425 }
1426
1427 static uint32_t *
1428 miniflow_alloc_values(struct miniflow *flow, int n)
1429 {
1430     if (n <= MINI_N_INLINE) {
1431         return flow->inline_values;
1432     } else {
1433         COVERAGE_INC(miniflow_malloc);
1434         return xmalloc(n * sizeof *flow->values);
1435     }
1436 }
1437
1438 /* Completes an initialization of 'dst' as a miniflow copy of 'src' begun by
1439  * the caller.  The caller must have already initialized 'dst->map' properly
1440  * to indicate the significant uint32_t elements of 'src'.  'n' must be the
1441  * number of 1-bits in 'dst->map'.
1442  *
1443  * Normally the significant elements are the ones that are non-zero.  However,
1444  * when a miniflow is initialized from a (mini)mask, the values can be zeroes,
1445  * so that the flow and mask always have the same maps.
1446  *
1447  * This function initializes 'dst->values' (either inline if possible or with
1448  * malloc() otherwise) and copies the uint32_t elements of 'src' indicated by
1449  * 'dst->map' into it. */
1450 static void
1451 miniflow_init__(struct miniflow *dst, const struct flow *src, int n)
1452 {
1453     const uint32_t *src_u32 = (const uint32_t *) src;
1454     unsigned int ofs;
1455     uint64_t map;
1456
1457     dst->values = miniflow_alloc_values(dst, n);
1458     ofs = 0;
1459     for (map = dst->map; map; map = zero_rightmost_1bit(map)) {
1460         dst->values[ofs++] = src_u32[raw_ctz(map)];
1461     }
1462 }
1463
1464 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
1465  * with miniflow_destroy(). */
1466 void
1467 miniflow_init(struct miniflow *dst, const struct flow *src)
1468 {
1469     const uint32_t *src_u32 = (const uint32_t *) src;
1470     unsigned int i;
1471     int n;
1472
1473     /* Initialize dst->map, counting the number of nonzero elements. */
1474     n = 0;
1475     dst->map = 0;
1476
1477     for (i = 0; i < FLOW_U32S; i++) {
1478         if (src_u32[i]) {
1479             dst->map |= UINT64_C(1) << i;
1480             n++;
1481         }
1482     }
1483
1484     miniflow_init__(dst, src, n);
1485 }
1486
1487 /* Initializes 'dst' as a copy of 'src', using 'mask->map' as 'dst''s map.  The
1488  * caller must eventually free 'dst' with miniflow_destroy(). */
1489 void
1490 miniflow_init_with_minimask(struct miniflow *dst, const struct flow *src,
1491                             const struct minimask *mask)
1492 {
1493     dst->map = mask->masks.map;
1494     miniflow_init__(dst, src, miniflow_n_values(dst));
1495 }
1496
1497 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
1498  * with miniflow_destroy(). */
1499 void
1500 miniflow_clone(struct miniflow *dst, const struct miniflow *src)
1501 {
1502     int n = miniflow_n_values(src);
1503     dst->map = src->map;
1504     dst->values = miniflow_alloc_values(dst, n);
1505     memcpy(dst->values, src->values, n * sizeof *dst->values);
1506 }
1507
1508 /* Initializes 'dst' with the data in 'src', destroying 'src'.
1509  * The caller must eventually free 'dst' with miniflow_destroy(). */
1510 void
1511 miniflow_move(struct miniflow *dst, struct miniflow *src)
1512 {
1513     if (src->values == src->inline_values) {
1514         dst->values = dst->inline_values;
1515         memcpy(dst->values, src->values,
1516                miniflow_n_values(src) * sizeof *dst->values);
1517     } else {
1518         dst->values = src->values;
1519     }
1520     dst->map = src->map;
1521 }
1522
1523 /* Frees any memory owned by 'flow'.  Does not free the storage in which 'flow'
1524  * itself resides; the caller is responsible for that. */
1525 void
1526 miniflow_destroy(struct miniflow *flow)
1527 {
1528     if (flow->values != flow->inline_values) {
1529         free(flow->values);
1530     }
1531 }
1532
1533 /* Initializes 'dst' as a copy of 'src'. */
1534 void
1535 miniflow_expand(const struct miniflow *src, struct flow *dst)
1536 {
1537     memset(dst, 0, sizeof *dst);
1538     flow_union_with_miniflow(dst, src);
1539 }
1540
1541 static const uint32_t *
1542 miniflow_get__(const struct miniflow *flow, unsigned int u32_ofs)
1543 {
1544     if (!(flow->map & (UINT64_C(1) << u32_ofs))) {
1545         static const uint32_t zero = 0;
1546         return &zero;
1547     }
1548     return flow->values +
1549            count_1bits(flow->map & ((UINT64_C(1) << u32_ofs) - 1));
1550 }
1551
1552 /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'flow'
1553  * were expanded into a "struct flow". */
1554 uint32_t
1555 miniflow_get(const struct miniflow *flow, unsigned int u32_ofs)
1556 {
1557     return *miniflow_get__(flow, u32_ofs);
1558 }
1559
1560 /* Returns the ovs_be16 that would be at byte offset 'u8_ofs' if 'flow' were
1561  * expanded into a "struct flow". */
1562 static ovs_be16
1563 miniflow_get_be16(const struct miniflow *flow, unsigned int u8_ofs)
1564 {
1565     const uint32_t *u32p = miniflow_get__(flow, u8_ofs / 4);
1566     const ovs_be16 *be16p = (const ovs_be16 *) u32p;
1567     return be16p[u8_ofs % 4 != 0];
1568 }
1569
1570 /* Returns the VID within the vlan_tci member of the "struct flow" represented
1571  * by 'flow'. */
1572 uint16_t
1573 miniflow_get_vid(const struct miniflow *flow)
1574 {
1575     ovs_be16 tci = miniflow_get_be16(flow, offsetof(struct flow, vlan_tci));
1576     return vlan_tci_to_vid(tci);
1577 }
1578
1579 /* Returns true if 'a' and 'b' are the same flow, false otherwise.  */
1580 bool
1581 miniflow_equal(const struct miniflow *a, const struct miniflow *b)
1582 {
1583     const uint32_t *ap = a->values;
1584     const uint32_t *bp = b->values;
1585     const uint64_t a_map = a->map;
1586     const uint64_t b_map = b->map;
1587     uint64_t map;
1588
1589     if (a_map == b_map) {
1590         for (map = a_map; map; map = zero_rightmost_1bit(map)) {
1591             if (*ap++ != *bp++) {
1592                 return false;
1593             }
1594         }
1595     } else {
1596         for (map = a_map | b_map; map; map = zero_rightmost_1bit(map)) {
1597             uint64_t bit = rightmost_1bit(map);
1598             uint64_t a_value = a_map & bit ? *ap++ : 0;
1599             uint64_t b_value = b_map & bit ? *bp++ : 0;
1600
1601             if (a_value != b_value) {
1602                 return false;
1603             }
1604         }
1605     }
1606
1607     return true;
1608 }
1609
1610 /* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
1611  * in 'mask', false if they differ. */
1612 bool
1613 miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
1614                            const struct minimask *mask)
1615 {
1616     const uint32_t *p;
1617     uint64_t map;
1618
1619     p = mask->masks.values;
1620
1621     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
1622         int ofs = raw_ctz(map);
1623
1624         if ((miniflow_get(a, ofs) ^ miniflow_get(b, ofs)) & *p) {
1625             return false;
1626         }
1627         p++;
1628     }
1629
1630     return true;
1631 }
1632
1633 /* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
1634  * in 'mask', false if they differ. */
1635 bool
1636 miniflow_equal_flow_in_minimask(const struct miniflow *a, const struct flow *b,
1637                                 const struct minimask *mask)
1638 {
1639     const uint32_t *b_u32 = (const uint32_t *) b;
1640     const uint32_t *p;
1641     uint64_t map;
1642
1643     p = mask->masks.values;
1644
1645     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
1646         int ofs = raw_ctz(map);
1647
1648         if ((miniflow_get(a, ofs) ^ b_u32[ofs]) & *p) {
1649             return false;
1650         }
1651         p++;
1652     }
1653
1654     return true;
1655 }
1656
1657 /* Returns a hash value for 'flow', given 'basis'. */
1658 uint32_t
1659 miniflow_hash(const struct miniflow *flow, uint32_t basis)
1660 {
1661     const uint32_t *p = flow->values;
1662     uint32_t hash = basis;
1663     uint64_t hash_map = 0;
1664     uint64_t map;
1665
1666     for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
1667         if (*p) {
1668             hash = mhash_add(hash, *p);
1669             hash_map |= rightmost_1bit(map);
1670         }
1671         p++;
1672     }
1673     hash = mhash_add(hash, hash_map);
1674     hash = mhash_add(hash, hash_map >> 32);
1675
1676     return mhash_finish(hash, p - flow->values);
1677 }
1678
1679 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
1680  * 'mask', given 'basis'.
1681  *
1682  * The hash values returned by this function are the same as those returned by
1683  * flow_hash_in_minimask(), only the form of the arguments differ. */
1684 uint32_t
1685 miniflow_hash_in_minimask(const struct miniflow *flow,
1686                           const struct minimask *mask, uint32_t basis)
1687 {
1688     const uint32_t *p = mask->masks.values;
1689     uint32_t hash;
1690     uint64_t map;
1691
1692     hash = basis;
1693
1694     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
1695         hash = mhash_add(hash, miniflow_get(flow, raw_ctz(map)) & *p++);
1696     }
1697
1698     return mhash_finish(hash, (p - mask->masks.values) * 4);
1699 }
1700
1701 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
1702  * 'mask', given 'basis'.
1703  *
1704  * The hash values returned by this function are the same as those returned by
1705  * miniflow_hash_in_minimask(), only the form of the arguments differ. */
1706 uint32_t
1707 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
1708                       uint32_t basis)
1709 {
1710     const uint32_t *flow_u32 = (const uint32_t *)flow;
1711     const uint32_t *p = mask->masks.values;
1712     uint32_t hash;
1713     uint64_t map;
1714
1715     hash = basis;
1716     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
1717         hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
1718     }
1719
1720     return mhash_finish(hash, (p - mask->masks.values) * 4);
1721 }
1722
1723 /* Returns a hash value for the bits of range [start, end) in 'flow',
1724  * where there are 1-bits in 'mask', given 'hash'.
1725  *
1726  * The hash values returned by this function are the same as those returned by
1727  * minimatch_hash_range(), only the form of the arguments differ. */
1728 uint32_t
1729 flow_hash_in_minimask_range(const struct flow *flow,
1730                             const struct minimask *mask,
1731                             uint8_t start, uint8_t end, uint32_t *basis)
1732 {
1733     const uint32_t *flow_u32 = (const uint32_t *)flow;
1734     unsigned int offset;
1735     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
1736                                              &offset);
1737     const uint32_t *p = mask->masks.values + offset;
1738     uint32_t hash = *basis;
1739
1740     for (; map; map = zero_rightmost_1bit(map)) {
1741         hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
1742     }
1743
1744     *basis = hash; /* Allow continuation from the unfinished value. */
1745     return mhash_finish(hash, (p - mask->masks.values) * 4);
1746 }
1747
1748 \f
1749 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
1750  * with minimask_destroy(). */
1751 void
1752 minimask_init(struct minimask *mask, const struct flow_wildcards *wc)
1753 {
1754     miniflow_init(&mask->masks, &wc->masks);
1755 }
1756
1757 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'
1758  * with minimask_destroy(). */
1759 void
1760 minimask_clone(struct minimask *dst, const struct minimask *src)
1761 {
1762     miniflow_clone(&dst->masks, &src->masks);
1763 }
1764
1765 /* Initializes 'dst' with the data in 'src', destroying 'src'.
1766  * The caller must eventually free 'dst' with minimask_destroy(). */
1767 void
1768 minimask_move(struct minimask *dst, struct minimask *src)
1769 {
1770     miniflow_move(&dst->masks, &src->masks);
1771 }
1772
1773 /* Initializes 'dst_' as the bit-wise "and" of 'a_' and 'b_'.
1774  *
1775  * The caller must provide room for FLOW_U32S "uint32_t"s in 'storage', for use
1776  * by 'dst_'.  The caller must *not* free 'dst_' with minimask_destroy(). */
1777 void
1778 minimask_combine(struct minimask *dst_,
1779                  const struct minimask *a_, const struct minimask *b_,
1780                  uint32_t storage[FLOW_U32S])
1781 {
1782     struct miniflow *dst = &dst_->masks;
1783     const struct miniflow *a = &a_->masks;
1784     const struct miniflow *b = &b_->masks;
1785     uint64_t map;
1786     int n = 0;
1787
1788     dst->values = storage;
1789
1790     dst->map = 0;
1791     for (map = a->map & b->map; map; map = zero_rightmost_1bit(map)) {
1792         int ofs = raw_ctz(map);
1793         uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
1794
1795         if (mask) {
1796             dst->map |= rightmost_1bit(map);
1797             dst->values[n++] = mask;
1798         }
1799     }
1800 }
1801
1802 /* Frees any memory owned by 'mask'.  Does not free the storage in which 'mask'
1803  * itself resides; the caller is responsible for that. */
1804 void
1805 minimask_destroy(struct minimask *mask)
1806 {
1807     miniflow_destroy(&mask->masks);
1808 }
1809
1810 /* Initializes 'dst' as a copy of 'src'. */
1811 void
1812 minimask_expand(const struct minimask *mask, struct flow_wildcards *wc)
1813 {
1814     miniflow_expand(&mask->masks, &wc->masks);
1815 }
1816
1817 /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'mask'
1818  * were expanded into a "struct flow_wildcards". */
1819 uint32_t
1820 minimask_get(const struct minimask *mask, unsigned int u32_ofs)
1821 {
1822     return miniflow_get(&mask->masks, u32_ofs);
1823 }
1824
1825 /* Returns the VID mask within the vlan_tci member of the "struct
1826  * flow_wildcards" represented by 'mask'. */
1827 uint16_t
1828 minimask_get_vid_mask(const struct minimask *mask)
1829 {
1830     return miniflow_get_vid(&mask->masks);
1831 }
1832
1833 /* Returns true if 'a' and 'b' are the same flow mask, false otherwise.  */
1834 bool
1835 minimask_equal(const struct minimask *a, const struct minimask *b)
1836 {
1837     return miniflow_equal(&a->masks, &b->masks);
1838 }
1839
1840 /* Returns a hash value for 'mask', given 'basis'. */
1841 uint32_t
1842 minimask_hash(const struct minimask *mask, uint32_t basis)
1843 {
1844     return miniflow_hash(&mask->masks, basis);
1845 }
1846
1847 /* Returns true if at least one bit is wildcarded in 'a_' but not in 'b_',
1848  * false otherwise. */
1849 bool
1850 minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
1851 {
1852     const struct miniflow *a = &a_->masks;
1853     const struct miniflow *b = &b_->masks;
1854     uint64_t map;
1855
1856     for (map = a->map | b->map; map; map = zero_rightmost_1bit(map)) {
1857         int ofs = raw_ctz(map);
1858         uint32_t a_u32 = miniflow_get(a, ofs);
1859         uint32_t b_u32 = miniflow_get(b, ofs);
1860
1861         if ((a_u32 & b_u32) != b_u32) {
1862             return true;
1863         }
1864     }
1865
1866     return false;
1867 }
1868
1869 /* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
1870  * or fields. */
1871 bool
1872 minimask_is_catchall(const struct minimask *mask_)
1873 {
1874     const struct miniflow *mask = &mask_->masks;
1875     const uint32_t *p = mask->values;
1876     uint64_t map;
1877
1878     for (map = mask->map; map; map = zero_rightmost_1bit(map)) {
1879         if (*p++) {
1880             return false;
1881         }
1882     }
1883     return true;
1884 }