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