ofproto/ofproto-dpif.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "ofproto/ofproto-provider.h"
  20
  21 #include <errno.h>
  22
  23 #include "autopath.h"
  24 #include "bond.h"
  25 #include "bundle.h"
  26 #include "byte-order.h"
  27 #include "connmgr.h"
  28 #include "coverage.h"
  29 #include "cfm.h"
  30 #include "dpif.h"
  31 #include "dynamic-string.h"
  32 #include "fail-open.h"
  33 #include "hmapx.h"
  34 #include "lacp.h"
  35 #include "learn.h"
  36 #include "mac-learning.h"
  37 #include "meta-flow.h"
  38 #include "multipath.h"
  39 #include "netdev.h"
  40 #include "netlink.h"
  41 #include "nx-match.h"
  42 #include "odp-util.h"
  43 #include "ofp-util.h"
  44 #include "ofpbuf.h"
  45 #include "ofp-print.h"
  46 #include "ofproto-dpif-governor.h"
  47 #include "ofproto-dpif-sflow.h"
  48 #include "poll-loop.h"
  49 #include "timer.h"
  50 #include "unaligned.h"
  51 #include "unixctl.h"
  52 #include "vlan-bitmap.h"
  53 #include "vlog.h"
  54
  55 VLOG_DEFINE_THIS_MODULE(ofproto_dpif);
  56
  57 COVERAGE_DEFINE(ofproto_dpif_ctlr_action);
  58 COVERAGE_DEFINE(ofproto_dpif_expired);
  59 COVERAGE_DEFINE(ofproto_dpif_no_packet_in);
  60 COVERAGE_DEFINE(ofproto_dpif_xlate);
  61 COVERAGE_DEFINE(facet_changed_rule);
  62 COVERAGE_DEFINE(facet_invalidated);
  63 COVERAGE_DEFINE(facet_revalidate);
  64 COVERAGE_DEFINE(facet_unexpected);
  65 COVERAGE_DEFINE(facet_suppress);
  66
  67 /* Maximum depth of flow table recursion (due to resubmit actions) in a
  68  * flow translation. */
  69 #define MAX_RESUBMIT_RECURSION 32
  70
  71 /* Number of implemented OpenFlow tables. */
  72 enum { N_TABLES = 255 };
  73 BUILD_ASSERT_DECL(N_TABLES >= 1 && N_TABLES <= 255);
  74
  75 struct ofport_dpif;
  76 struct ofproto_dpif;
  77
  78 struct rule_dpif {
  79     struct rule up;
  80
  81     /* These statistics:
  82      *
  83      *   - Do include packets and bytes from facets that have been deleted or
  84      *     whose own statistics have been folded into the rule.
  85      *
  86      *   - Do include packets and bytes sent "by hand" that were accounted to
  87      *     the rule without any facet being involved (this is a rare corner
  88      *     case in rule_execute()).
  89      *
  90      *   - Do not include packet or bytes that can be obtained from any facet's
  91      *     packet_count or byte_count member or that can be obtained from the
  92      *     datapath by, e.g., dpif_flow_get() for any subfacet.
  93      */
  94     uint64_t packet_count;       /* Number of packets received. */
  95     uint64_t byte_count;         /* Number of bytes received. */
  96
  97     tag_type tag;                /* Caches rule_calculate_tag() result. */
  98
  99     struct list facets;          /* List of "struct facet"s. */
 100 };
 101
 102 static struct rule_dpif *rule_dpif_cast(const struct rule *rule)
 103 {
 104     return rule ? CONTAINER_OF(rule, struct rule_dpif, up) : NULL;
 105 }
 106
 107 static struct rule_dpif *rule_dpif_lookup(struct ofproto_dpif *,
 108                                           const struct flow *, uint8_t table);
 109
 110 static void rule_credit_stats(struct rule_dpif *,
 111                               const struct dpif_flow_stats *);
 112 static void flow_push_stats(struct rule_dpif *, const struct flow *,
 113                             const struct dpif_flow_stats *);
 114 static tag_type rule_calculate_tag(const struct flow *,
 115                                    const struct flow_wildcards *,
 116                                    uint32_t basis);
 117 static void rule_invalidate(const struct rule_dpif *);
 118
 119 #define MAX_MIRRORS 32
 120 typedef uint32_t mirror_mask_t;
 121 #define MIRROR_MASK_C(X) UINT32_C(X)
 122 BUILD_ASSERT_DECL(sizeof(mirror_mask_t) * CHAR_BIT >= MAX_MIRRORS);
 123 struct ofmirror {
 124     struct ofproto_dpif *ofproto; /* Owning ofproto. */
 125     size_t idx;                 /* In ofproto's "mirrors" array. */
 126     void *aux;                  /* Key supplied by ofproto's client. */
 127     char *name;                 /* Identifier for log messages. */
 128
 129     /* Selection criteria. */
 130     struct hmapx srcs;          /* Contains "struct ofbundle *"s. */
 131     struct hmapx dsts;          /* Contains "struct ofbundle *"s. */
 132     unsigned long *vlans;       /* Bitmap of chosen VLANs, NULL selects all. */
 133
 134     /* Output (exactly one of out == NULL and out_vlan == -1 is true). */
 135     struct ofbundle *out;       /* Output port or NULL. */
 136     int out_vlan;               /* Output VLAN or -1. */
 137     mirror_mask_t dup_mirrors;  /* Bitmap of mirrors with the same output. */
 138
 139     /* Counters. */
 140     int64_t packet_count;       /* Number of packets sent. */
 141     int64_t byte_count;         /* Number of bytes sent. */
 142 };
 143
 144 static void mirror_destroy(struct ofmirror *);
 145 static void update_mirror_stats(struct ofproto_dpif *ofproto,
 146                                 mirror_mask_t mirrors,
 147                                 uint64_t packets, uint64_t bytes);
 148
 149 struct ofbundle {
 150     struct hmap_node hmap_node; /* In struct ofproto's "bundles" hmap. */
 151     struct ofproto_dpif *ofproto; /* Owning ofproto. */
 152     void *aux;                  /* Key supplied by ofproto's client. */
 153     char *name;                 /* Identifier for log messages. */
 154
 155     /* Configuration. */
 156     struct list ports;          /* Contains "struct ofport"s. */
 157     enum port_vlan_mode vlan_mode; /* VLAN mode */
 158     int vlan;                   /* -1=trunk port, else a 12-bit VLAN ID. */
 159     unsigned long *trunks;      /* Bitmap of trunked VLANs, if 'vlan' == -1.
 160                                  * NULL if all VLANs are trunked. */
 161     struct lacp *lacp;          /* LACP if LACP is enabled, otherwise NULL. */
 162     struct bond *bond;          /* Nonnull iff more than one port. */
 163     bool use_priority_tags;     /* Use 802.1p tag for frames in VLAN 0? */
 164
 165     /* Status. */
 166     bool floodable;          /* True if no port has OFPUTIL_PC_NO_FLOOD set. */
 167
 168     /* Port mirroring info. */
 169     mirror_mask_t src_mirrors;  /* Mirrors triggered when packet received. */
 170     mirror_mask_t dst_mirrors;  /* Mirrors triggered when packet sent. */
 171     mirror_mask_t mirror_out;   /* Mirrors that output to this bundle. */
 172 };
 173
 174 static void bundle_remove(struct ofport *);
 175 static void bundle_update(struct ofbundle *);
 176 static void bundle_destroy(struct ofbundle *);
 177 static void bundle_del_port(struct ofport_dpif *);
 178 static void bundle_run(struct ofbundle *);
 179 static void bundle_wait(struct ofbundle *);
 180 static struct ofbundle *lookup_input_bundle(struct ofproto_dpif *,
 181                                             uint16_t in_port, bool warn);
 182
 183 /* A controller may use OFPP_NONE as the ingress port to indicate that
 184  * it did not arrive on a "real" port.  'ofpp_none_bundle' exists for
 185  * when an input bundle is needed for validation (e.g., mirroring or
 186  * OFPP_NORMAL processing).  It is not connected to an 'ofproto' or have
 187  * any 'port' structs, so care must be taken when dealing with it. */
 188 static struct ofbundle ofpp_none_bundle = {
 189     .name      = "OFPP_NONE",
 190     .vlan_mode = PORT_VLAN_TRUNK
 191 };
 192
 193 static void stp_run(struct ofproto_dpif *ofproto);
 194 static void stp_wait(struct ofproto_dpif *ofproto);
 195 static int set_stp_port(struct ofport *,
 196                         const struct ofproto_port_stp_settings *);
 197
 198 static bool ofbundle_includes_vlan(const struct ofbundle *, uint16_t vlan);
 199
 200 struct action_xlate_ctx {
 201 /* action_xlate_ctx_init() initializes these members. */
 202
 203     /* The ofproto. */
 204     struct ofproto_dpif *ofproto;
 205
 206     /* Flow to which the OpenFlow actions apply.  xlate_actions() will modify
 207      * this flow when actions change header fields. */
 208     struct flow flow;
 209
 210     /* The packet corresponding to 'flow', or a null pointer if we are
 211      * revalidating without a packet to refer to. */
 212     const struct ofpbuf *packet;
 213
 214     /* Should OFPP_NORMAL update the MAC learning table?  Should "learn"
 215      * actions update the flow table?
 216      *
 217      * We want to update these tables if we are actually processing a packet,
 218      * or if we are accounting for packets that the datapath has processed, but
 219      * not if we are just revalidating. */
 220     bool may_learn;
 221
 222     /* The rule that we are currently translating, or NULL. */
 223     struct rule_dpif *rule;
 224
 225     /* Union of the set of TCP flags seen so far in this flow.  (Used only by
 226      * NXAST_FIN_TIMEOUT.  Set to zero to avoid updating updating rules'
 227      * timeouts.) */
 228     uint8_t tcp_flags;
 229
 230     /* If nonnull, flow translation calls this function just before executing a
 231      * resubmit or OFPP_TABLE action.  In addition, disables logging of traces
 232      * when the recursion depth is exceeded.
 233      *
 234      * 'rule' is the rule being submitted into.  It will be null if the
 235      * resubmit or OFPP_TABLE action didn't find a matching rule.
 236      *
 237      * This is normally null so the client has to set it manually after
 238      * calling action_xlate_ctx_init(). */
 239     void (*resubmit_hook)(struct action_xlate_ctx *, struct rule_dpif *rule);
 240
 241     /* If nonnull, flow translation credits the specified statistics to each
 242      * rule reached through a resubmit or OFPP_TABLE action.
 243      *
 244      * This is normally null so the client has to set it manually after
 245      * calling action_xlate_ctx_init(). */
 246     const struct dpif_flow_stats *resubmit_stats;
 247
 248 /* xlate_actions() initializes and uses these members.  The client might want
 249  * to look at them after it returns. */
 250
 251     struct ofpbuf *odp_actions; /* Datapath actions. */
 252     tag_type tags;              /* Tags associated with actions. */
 253     bool may_set_up_flow;       /* True ordinarily; false if the actions must
 254                                  * be reassessed for every packet. */
 255     bool has_learn;             /* Actions include NXAST_LEARN? */
 256     bool has_normal;            /* Actions output to OFPP_NORMAL? */
 257     bool has_fin_timeout;       /* Actions include NXAST_FIN_TIMEOUT? */
 258     uint16_t nf_output_iface;   /* Output interface index for NetFlow. */
 259     mirror_mask_t mirrors;      /* Bitmap of associated mirrors. */
 260
 261 /* xlate_actions() initializes and uses these members, but the client has no
 262  * reason to look at them. */
 263
 264     int recurse;                /* Recursion level, via xlate_table_action. */
 265     bool max_resubmit_trigger;  /* Recursed too deeply during translation. */
 266     struct flow base_flow;      /* Flow at the last commit. */
 267     uint32_t orig_skb_priority; /* Priority when packet arrived. */
 268     uint8_t table_id;           /* OpenFlow table ID where flow was found. */
 269     uint32_t sflow_n_outputs;   /* Number of output ports. */
 270     uint16_t sflow_odp_port;    /* Output port for composing sFlow action. */
 271     uint16_t user_cookie_offset;/* Used for user_action_cookie fixup. */
 272     bool exit;                  /* No further actions should be processed. */
 273 };
 274
 275 static void action_xlate_ctx_init(struct action_xlate_ctx *,
 276                                   struct ofproto_dpif *, const struct flow *,
 277                                   ovs_be16 initial_tci, struct rule_dpif *,
 278                                   uint8_t tcp_flags, const struct ofpbuf *);
 279 static void xlate_actions(struct action_xlate_ctx *,
 280                           const union ofp_action *in, size_t n_in,
 281                           struct ofpbuf *odp_actions);
 282 static void xlate_actions_for_side_effects(struct action_xlate_ctx *,
 283                                            const union ofp_action *in,
 284                                            size_t n_in);
 285
 286 /* A dpif flow and actions associated with a facet.
 287  *
 288  * See also the large comment on struct facet. */
 289 struct subfacet {
 290     /* Owners. */
 291     struct hmap_node hmap_node; /* In struct ofproto_dpif 'subfacets' list. */
 292     struct list list_node;      /* In struct facet's 'facets' list. */
 293     struct facet *facet;        /* Owning facet. */
 294
 295     /* Key.
 296      *
 297      * To save memory in the common case, 'key' is NULL if 'key_fitness' is
 298      * ODP_FIT_PERFECT, that is, odp_flow_key_from_flow() can accurately
 299      * regenerate the ODP flow key from ->facet->flow. */
 300     enum odp_key_fitness key_fitness;
 301     struct nlattr *key;
 302     int key_len;
 303
 304     long long int used;         /* Time last used; time created if not used. */
 305
 306     uint64_t dp_packet_count;   /* Last known packet count in the datapath. */
 307     uint64_t dp_byte_count;     /* Last known byte count in the datapath. */
 308
 309     /* Datapath actions.
 310      *
 311      * These should be essentially identical for every subfacet in a facet, but
 312      * may differ in trivial ways due to VLAN splinters. */
 313     size_t actions_len;         /* Number of bytes in actions[]. */
 314     struct nlattr *actions;     /* Datapath actions. */
 315
 316     bool installed;             /* Installed in datapath? */
 317
 318     /* This value is normally the same as ->facet->flow.vlan_tci.  Only VLAN
 319      * splinters can cause it to differ.  This value should be removed when
 320      * the VLAN splinters feature is no longer needed.  */
 321     ovs_be16 initial_tci;       /* Initial VLAN TCI value. */
 322 };
 323
 324 static struct subfacet *subfacet_create(struct facet *, enum odp_key_fitness,
 325                                         const struct nlattr *key,
 326                                         size_t key_len, ovs_be16 initial_tci);
 327 static struct subfacet *subfacet_find(struct ofproto_dpif *,
 328                                       const struct nlattr *key, size_t key_len);
 329 static void subfacet_destroy(struct subfacet *);
 330 static void subfacet_destroy__(struct subfacet *);
 331 static void subfacet_get_key(struct subfacet *, struct odputil_keybuf *,
 332                              struct ofpbuf *key);
 333 static void subfacet_reset_dp_stats(struct subfacet *,
 334                                     struct dpif_flow_stats *);
 335 static void subfacet_update_time(struct subfacet *, long long int used);
 336 static void subfacet_update_stats(struct subfacet *,
 337                                   const struct dpif_flow_stats *);
 338 static void subfacet_make_actions(struct subfacet *,
 339                                   const struct ofpbuf *packet,
 340                                   struct ofpbuf *odp_actions);
 341 static int subfacet_install(struct subfacet *,
 342                             const struct nlattr *actions, size_t actions_len,
 343                             struct dpif_flow_stats *);
 344 static void subfacet_uninstall(struct subfacet *);
 345
 346 /* An exact-match instantiation of an OpenFlow flow.
 347  *
 348  * A facet associates a "struct flow", which represents the Open vSwitch
 349  * userspace idea of an exact-match flow, with one or more subfacets.  Each
 350  * subfacet tracks the datapath's idea of the exact-match flow equivalent to
 351  * the facet.  When the kernel module (or other dpif implementation) and Open
 352  * vSwitch userspace agree on the definition of a flow key, there is exactly
 353  * one subfacet per facet.  If the dpif implementation supports more-specific
 354  * flow matching than userspace, however, a facet can have more than one
 355  * subfacet, each of which corresponds to some distinction in flow that
 356  * userspace simply doesn't understand.
 357  *
 358  * Flow expiration works in terms of subfacets, so a facet must have at least
 359  * one subfacet or it will never expire, leaking memory. */
 360 struct facet {
 361     /* Owners. */
 362     struct hmap_node hmap_node;  /* In owning ofproto's 'facets' hmap. */
 363     struct list list_node;       /* In owning rule's 'facets' list. */
 364     struct rule_dpif *rule;      /* Owning rule. */
 365
 366     /* Owned data. */
 367     struct list subfacets;
 368     long long int used;         /* Time last used; time created if not used. */
 369
 370     /* Key. */
 371     struct flow flow;
 372
 373     /* These statistics:
 374      *
 375      *   - Do include packets and bytes sent "by hand", e.g. with
 376      *     dpif_execute().
 377      *
 378      *   - Do include packets and bytes that were obtained from the datapath
 379      *     when a subfacet's statistics were reset (e.g. dpif_flow_put() with
 380      *     DPIF_FP_ZERO_STATS).
 381      *
 382      *   - Do not include packets or bytes that can be obtained from the
 383      *     datapath for any existing subfacet.
 384      */
 385     uint64_t packet_count;       /* Number of packets received. */
 386     uint64_t byte_count;         /* Number of bytes received. */
 387
 388     /* Resubmit statistics. */
 389     uint64_t prev_packet_count;  /* Number of packets from last stats push. */
 390     uint64_t prev_byte_count;    /* Number of bytes from last stats push. */
 391     long long int prev_used;     /* Used time from last stats push. */
 392
 393     /* Accounting. */
 394     uint64_t accounted_bytes;    /* Bytes processed by facet_account(). */
 395     struct netflow_flow nf_flow; /* Per-flow NetFlow tracking data. */
 396     uint8_t tcp_flags;           /* TCP flags seen for this 'rule'. */
 397
 398     /* Properties of datapath actions.
 399      *
 400      * Every subfacet has its own actions because actions can differ slightly
 401      * between splintered and non-splintered subfacets due to the VLAN tag
 402      * being initially different (present vs. absent).  All of them have these
 403      * properties in common so we just store one copy of them here. */
 404     bool may_install;            /* Reassess actions for every packet? */
 405     bool has_learn;              /* Actions include NXAST_LEARN? */
 406     bool has_normal;             /* Actions output to OFPP_NORMAL? */
 407     bool has_fin_timeout;        /* Actions include NXAST_FIN_TIMEOUT? */
 408     tag_type tags;               /* Tags that would require revalidation. */
 409     mirror_mask_t mirrors;       /* Bitmap of dependent mirrors. */
 410
 411     /* Storage for a single subfacet, to reduce malloc() time and space
 412      * overhead.  (A facet always has at least one subfacet and in the common
 413      * case has exactly one subfacet.) */
 414     struct subfacet one_subfacet;
 415 };
 416
 417 static struct facet *facet_create(struct rule_dpif *,
 418                                   const struct flow *, uint32_t hash);
 419 static void facet_remove(struct facet *);
 420 static void facet_free(struct facet *);
 421
 422 static struct facet *facet_find(struct ofproto_dpif *,
 423                                 const struct flow *, uint32_t hash);
 424 static struct facet *facet_lookup_valid(struct ofproto_dpif *,
 425                                         const struct flow *, uint32_t hash);
 426 static bool facet_revalidate(struct facet *);
 427 static bool facet_check_consistency(struct facet *);
 428
 429 static void facet_flush_stats(struct facet *);
 430
 431 static void facet_update_time(struct facet *, long long int used);
 432 static void facet_reset_counters(struct facet *);
 433 static void facet_push_stats(struct facet *);
 434 static void facet_learn(struct facet *);
 435 static void facet_account(struct facet *);
 436
 437 static bool facet_is_controller_flow(struct facet *);
 438
 439 struct ofport_dpif {
 440     struct ofport up;
 441
 442     uint32_t odp_port;
 443     struct ofbundle *bundle;    /* Bundle that contains this port, if any. */
 444     struct list bundle_node;    /* In struct ofbundle's "ports" list. */
 445     struct cfm *cfm;            /* Connectivity Fault Management, if any. */
 446     tag_type tag;               /* Tag associated with this port. */
 447     uint32_t bond_stable_id;    /* stable_id to use as bond slave, or 0. */
 448     bool may_enable;            /* May be enabled in bonds. */
 449     long long int carrier_seq;  /* Carrier status changes. */
 450
 451     /* Spanning tree. */
 452     struct stp_port *stp_port;  /* Spanning Tree Protocol, if any. */
 453     enum stp_state stp_state;   /* Always STP_DISABLED if STP not in use. */
 454     long long int stp_state_entered;
 455
 456     struct hmap priorities;     /* Map of attached 'priority_to_dscp's. */
 457
 458     /* Linux VLAN device support (e.g. "eth0.10" for VLAN 10.)
 459      *
 460      * This is deprecated.  It is only for compatibility with broken device
 461      * drivers in old versions of Linux that do not properly support VLANs when
 462      * VLAN devices are not used.  When broken device drivers are no longer in
 463      * widespread use, we will delete these interfaces. */
 464     uint16_t realdev_ofp_port;
 465     int vlandev_vid;
 466 };
 467
 468 /* Node in 'ofport_dpif''s 'priorities' map.  Used to maintain a map from
 469  * 'priority' (the datapath's term for QoS queue) to the dscp bits which all
 470  * traffic egressing the 'ofport' with that priority should be marked with. */
 471 struct priority_to_dscp {
 472     struct hmap_node hmap_node; /* Node in 'ofport_dpif''s 'priorities' map. */
 473     uint32_t priority;          /* Priority of this queue (see struct flow). */
 474
 475     uint8_t dscp;               /* DSCP bits to mark outgoing traffic with. */
 476 };
 477
 478 /* Linux VLAN device support (e.g. "eth0.10" for VLAN 10.)
 479  *
 480  * This is deprecated.  It is only for compatibility with broken device drivers
 481  * in old versions of Linux that do not properly support VLANs when VLAN
 482  * devices are not used.  When broken device drivers are no longer in
 483  * widespread use, we will delete these interfaces. */
 484 struct vlan_splinter {
 485     struct hmap_node realdev_vid_node;
 486     struct hmap_node vlandev_node;
 487     uint16_t realdev_ofp_port;
 488     uint16_t vlandev_ofp_port;
 489     int vid;
 490 };
 491
 492 static uint32_t vsp_realdev_to_vlandev(const struct ofproto_dpif *,
 493                                        uint32_t realdev, ovs_be16 vlan_tci);
 494 static uint16_t vsp_vlandev_to_realdev(const struct ofproto_dpif *,
 495                                        uint16_t vlandev, int *vid);
 496 static void vsp_remove(struct ofport_dpif *);
 497 static void vsp_add(struct ofport_dpif *, uint16_t realdev_ofp_port, int vid);
 498
 499 static struct ofport_dpif *
 500 ofport_dpif_cast(const struct ofport *ofport)
 501 {
 502     assert(ofport->ofproto->ofproto_class == &ofproto_dpif_class);
 503     return ofport ? CONTAINER_OF(ofport, struct ofport_dpif, up) : NULL;
 504 }
 505
 506 static void port_run(struct ofport_dpif *);
 507 static void port_wait(struct ofport_dpif *);
 508 static int set_cfm(struct ofport *, const struct cfm_settings *);
 509 static void ofport_clear_priorities(struct ofport_dpif *);
 510
 511 struct dpif_completion {
 512     struct list list_node;
 513     struct ofoperation *op;
 514 };
 515
 516 /* Extra information about a classifier table.
 517  * Currently used just for optimized flow revalidation. */
 518 struct table_dpif {
 519     /* If either of these is nonnull, then this table has a form that allows
 520      * flows to be tagged to avoid revalidating most flows for the most common
 521      * kinds of flow table changes. */
 522     struct cls_table *catchall_table; /* Table that wildcards all fields. */
 523     struct cls_table *other_table;    /* Table with any other wildcard set. */
 524     uint32_t basis;                   /* Keeps each table's tags separate. */
 525 };
 526
 527 struct ofproto_dpif {
 528     struct hmap_node all_ofproto_dpifs_node; /* In 'all_ofproto_dpifs'. */
 529     struct ofproto up;
 530     struct dpif *dpif;
 531     int max_ports;
 532
 533     /* Statistics. */
 534     uint64_t n_matches;
 535
 536     /* Bridging. */
 537     struct netflow *netflow;
 538     struct dpif_sflow *sflow;
 539     struct hmap bundles;        /* Contains "struct ofbundle"s. */
 540     struct mac_learning *ml;
 541     struct ofmirror *mirrors[MAX_MIRRORS];
 542     bool has_bonded_bundles;
 543
 544     /* Expiration. */
 545     struct timer next_expiration;
 546
 547     /* Facets. */
 548     struct hmap facets;
 549     struct hmap subfacets;
 550     struct governor *governor;
 551
 552     /* Revalidation. */
 553     struct table_dpif tables[N_TABLES];
 554     bool need_revalidate;
 555     struct tag_set revalidate_set;
 556
 557     /* Support for debugging async flow mods. */
 558     struct list completions;
 559
 560     bool has_bundle_action; /* True when the first bundle action appears. */
 561     struct netdev_stats stats; /* To account packets generated and consumed in
 562                                 * userspace. */
 563
 564     /* Spanning tree. */
 565     struct stp *stp;
 566     long long int stp_last_tick;
 567
 568     /* VLAN splinters. */
 569     struct hmap realdev_vid_map; /* (realdev,vid) -> vlandev. */
 570     struct hmap vlandev_map;     /* vlandev -> (realdev,vid). */
 571 };
 572
 573 /* Defer flow mod completion until "ovs-appctl ofproto/unclog"?  (Useful only
 574  * for debugging the asynchronous flow_mod implementation.) */
 575 static bool clogged;
 576
 577 /* All existing ofproto_dpif instances, indexed by ->up.name. */
 578 static struct hmap all_ofproto_dpifs = HMAP_INITIALIZER(&all_ofproto_dpifs);
 579
 580 static void ofproto_dpif_unixctl_init(void);
 581
 582 static struct ofproto_dpif *
 583 ofproto_dpif_cast(const struct ofproto *ofproto)
 584 {
 585     assert(ofproto->ofproto_class == &ofproto_dpif_class);
 586     return CONTAINER_OF(ofproto, struct ofproto_dpif, up);
 587 }
 588
 589 static struct ofport_dpif *get_ofp_port(struct ofproto_dpif *,
 590                                         uint16_t ofp_port);
 591 static struct ofport_dpif *get_odp_port(struct ofproto_dpif *,
 592                                         uint32_t odp_port);
 593 static void ofproto_trace(struct ofproto_dpif *, const struct flow *,
 594                           const struct ofpbuf *, ovs_be16 initial_tci,
 595                           struct ds *);
 596
 597 /* Packet processing. */
 598 static void update_learning_table(struct ofproto_dpif *,
 599                                   const struct flow *, int vlan,
 600                                   struct ofbundle *);
 601 /* Upcalls. */
 602 #define FLOW_MISS_MAX_BATCH 50
 603 static int handle_upcalls(struct ofproto_dpif *, unsigned int max_batch);
 604
 605 /* Flow expiration. */
 606 static int expire(struct ofproto_dpif *);
 607
 608 /* NetFlow. */
 609 static void send_netflow_active_timeouts(struct ofproto_dpif *);
 610
 611 /* Utilities. */
 612 static int send_packet(const struct ofport_dpif *, struct ofpbuf *packet);
 613 static size_t
 614 compose_sflow_action(const struct ofproto_dpif *, struct ofpbuf *odp_actions,
 615                      const struct flow *, uint32_t odp_port);
 616 static void add_mirror_actions(struct action_xlate_ctx *ctx,
 617                                const struct flow *flow);
 618 /* Global variables. */
 619 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
 620 \f
 621 /* Factory functions. */
 622
 623 static void
 624 enumerate_types(struct sset *types)
 625 {
 626     dp_enumerate_types(types);
 627 }
 628
 629 static int
 630 enumerate_names(const char *type, struct sset *names)
 631 {
 632     return dp_enumerate_names(type, names);
 633 }
 634
 635 static int
 636 del(const char *type, const char *name)
 637 {
 638     struct dpif *dpif;
 639     int error;
 640
 641     error = dpif_open(name, type, &dpif);
 642     if (!error) {
 643         error = dpif_delete(dpif);
 644         dpif_close(dpif);
 645     }
 646     return error;
 647 }
 648 \f
 649 /* Basic life-cycle. */
 650
 651 static struct ofproto *
 652 alloc(void)
 653 {
 654     struct ofproto_dpif *ofproto = xmalloc(sizeof *ofproto);
 655     return &ofproto->up;
 656 }
 657
 658 static void
 659 dealloc(struct ofproto *ofproto_)
 660 {
 661     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 662     free(ofproto);
 663 }
 664
 665 static int
 666 construct(struct ofproto *ofproto_)
 667 {
 668     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 669     const char *name = ofproto->up.name;
 670     int error;
 671     int i;
 672
 673     error = dpif_create_and_open(name, ofproto->up.type, &ofproto->dpif);
 674     if (error) {
 675         VLOG_ERR("failed to open datapath %s: %s", name, strerror(error));
 676         return error;
 677     }
 678
 679     ofproto->max_ports = dpif_get_max_ports(ofproto->dpif);
 680     ofproto->n_matches = 0;
 681
 682     dpif_flow_flush(ofproto->dpif);
 683     dpif_recv_purge(ofproto->dpif);
 684
 685     error = dpif_recv_set(ofproto->dpif, true);
 686     if (error) {
 687         VLOG_ERR("failed to listen on datapath %s: %s", name, strerror(error));
 688         dpif_close(ofproto->dpif);
 689         return error;
 690     }
 691
 692     ofproto->netflow = NULL;
 693     ofproto->sflow = NULL;
 694     ofproto->stp = NULL;
 695     hmap_init(&ofproto->bundles);
 696     ofproto->ml = mac_learning_create(MAC_ENTRY_DEFAULT_IDLE_TIME);
 697     for (i = 0; i < MAX_MIRRORS; i++) {
 698         ofproto->mirrors[i] = NULL;
 699     }
 700     ofproto->has_bonded_bundles = false;
 701
 702     timer_set_duration(&ofproto->next_expiration, 1000);
 703
 704     hmap_init(&ofproto->facets);
 705     hmap_init(&ofproto->subfacets);
 706     ofproto->governor = NULL;
 707
 708     for (i = 0; i < N_TABLES; i++) {
 709         struct table_dpif *table = &ofproto->tables[i];
 710
 711         table->catchall_table = NULL;
 712         table->other_table = NULL;
 713         table->basis = random_uint32();
 714     }
 715     ofproto->need_revalidate = false;
 716     tag_set_init(&ofproto->revalidate_set);
 717
 718     list_init(&ofproto->completions);
 719
 720     ofproto_dpif_unixctl_init();
 721
 722     ofproto->has_bundle_action = false;
 723
 724     hmap_init(&ofproto->vlandev_map);
 725     hmap_init(&ofproto->realdev_vid_map);
 726
 727     hmap_insert(&all_ofproto_dpifs, &ofproto->all_ofproto_dpifs_node,
 728                 hash_string(ofproto->up.name, 0));
 729     memset(&ofproto->stats, 0, sizeof ofproto->stats);
 730
 731     ofproto_init_tables(ofproto_, N_TABLES);
 732
 733     return 0;
 734 }
 735
 736 static void
 737 complete_operations(struct ofproto_dpif *ofproto)
 738 {
 739     struct dpif_completion *c, *next;
 740
 741     LIST_FOR_EACH_SAFE (c, next, list_node, &ofproto->completions) {
 742         ofoperation_complete(c->op, 0);
 743         list_remove(&c->list_node);
 744         free(c);
 745     }
 746 }
 747
 748 static void
 749 destruct(struct ofproto *ofproto_)
 750 {
 751     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 752     struct rule_dpif *rule, *next_rule;
 753     struct oftable *table;
 754     int i;
 755
 756     hmap_remove(&all_ofproto_dpifs, &ofproto->all_ofproto_dpifs_node);
 757     complete_operations(ofproto);
 758
 759     OFPROTO_FOR_EACH_TABLE (table, &ofproto->up) {
 760         struct cls_cursor cursor;
 761
 762         cls_cursor_init(&cursor, &table->cls, NULL);
 763         CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, up.cr, &cursor) {
 764             ofproto_rule_destroy(&rule->up);
 765         }
 766     }
 767
 768     for (i = 0; i < MAX_MIRRORS; i++) {
 769         mirror_destroy(ofproto->mirrors[i]);
 770     }
 771
 772     netflow_destroy(ofproto->netflow);
 773     dpif_sflow_destroy(ofproto->sflow);
 774     hmap_destroy(&ofproto->bundles);
 775     mac_learning_destroy(ofproto->ml);
 776
 777     hmap_destroy(&ofproto->facets);
 778     hmap_destroy(&ofproto->subfacets);
 779     governor_destroy(ofproto->governor);
 780
 781     hmap_destroy(&ofproto->vlandev_map);
 782     hmap_destroy(&ofproto->realdev_vid_map);
 783
 784     dpif_close(ofproto->dpif);
 785 }
 786
 787 static int
 788 run_fast(struct ofproto *ofproto_)
 789 {
 790     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 791     unsigned int work;
 792
 793     /* Handle one or more batches of upcalls, until there's nothing left to do
 794      * or until we do a fixed total amount of work.
 795      *
 796      * We do work in batches because it can be much cheaper to set up a number
 797      * of flows and fire off their patches all at once.  We do multiple batches
 798      * because in some cases handling a packet can cause another packet to be
 799      * queued almost immediately as part of the return flow.  Both
 800      * optimizations can make major improvements on some benchmarks and
 801      * presumably for real traffic as well. */
 802     work = 0;
 803     while (work < FLOW_MISS_MAX_BATCH) {
 804         int retval = handle_upcalls(ofproto, FLOW_MISS_MAX_BATCH - work);
 805         if (retval <= 0) {
 806             return -retval;
 807         }
 808         work += retval;
 809     }
 810     return 0;
 811 }
 812
 813 static int
 814 run(struct ofproto *ofproto_)
 815 {
 816     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 817     struct ofport_dpif *ofport;
 818     struct ofbundle *bundle;
 819     int error;
 820
 821     if (!clogged) {
 822         complete_operations(ofproto);
 823     }
 824     dpif_run(ofproto->dpif);
 825
 826     error = run_fast(ofproto_);
 827     if (error) {
 828         return error;
 829     }
 830
 831     if (timer_expired(&ofproto->next_expiration)) {
 832         int delay = expire(ofproto);
 833         timer_set_duration(&ofproto->next_expiration, delay);
 834     }
 835
 836     if (ofproto->netflow) {
 837         if (netflow_run(ofproto->netflow)) {
 838             send_netflow_active_timeouts(ofproto);
 839         }
 840     }
 841     if (ofproto->sflow) {
 842         dpif_sflow_run(ofproto->sflow);
 843     }
 844
 845     HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
 846         port_run(ofport);
 847     }
 848     HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
 849         bundle_run(bundle);
 850     }
 851
 852     stp_run(ofproto);
 853     mac_learning_run(ofproto->ml, &ofproto->revalidate_set);
 854
 855     /* Now revalidate if there's anything to do. */
 856     if (ofproto->need_revalidate
 857         || !tag_set_is_empty(&ofproto->revalidate_set)) {
 858         struct tag_set revalidate_set = ofproto->revalidate_set;
 859         bool revalidate_all = ofproto->need_revalidate;
 860         struct facet *facet, *next;
 861
 862         /* Clear the revalidation flags. */
 863         tag_set_init(&ofproto->revalidate_set);
 864         ofproto->need_revalidate = false;
 865
 866         HMAP_FOR_EACH_SAFE (facet, next, hmap_node, &ofproto->facets) {
 867             if (revalidate_all
 868                 || tag_set_intersects(&revalidate_set, facet->tags)) {
 869                 facet_revalidate(facet);
 870             }
 871         }
 872     }
 873
 874     /* Check the consistency of a random facet, to aid debugging. */
 875     if (!hmap_is_empty(&ofproto->facets) && !ofproto->need_revalidate) {
 876         struct facet *facet;
 877
 878         facet = CONTAINER_OF(hmap_random_node(&ofproto->facets),
 879                              struct facet, hmap_node);
 880         if (!tag_set_intersects(&ofproto->revalidate_set, facet->tags)) {
 881             if (!facet_check_consistency(facet)) {
 882                 ofproto->need_revalidate = true;
 883             }
 884         }
 885     }
 886
 887     if (ofproto->governor) {
 888         size_t n_subfacets;
 889
 890         governor_run(ofproto->governor);
 891
 892         /* If the governor has shrunk to its minimum size and the number of
 893          * subfacets has dwindled, then drop the governor entirely.
 894          *
 895          * For hysteresis, the number of subfacets to drop the governor is
 896          * smaller than the number needed to trigger its creation. */
 897         n_subfacets = hmap_count(&ofproto->subfacets);
 898         if (n_subfacets * 4 < ofproto->up.flow_eviction_threshold
 899             && governor_is_idle(ofproto->governor)) {
 900             governor_destroy(ofproto->governor);
 901             ofproto->governor = NULL;
 902         }
 903     }
 904
 905     return 0;
 906 }
 907
 908 static void
 909 wait(struct ofproto *ofproto_)
 910 {
 911     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 912     struct ofport_dpif *ofport;
 913     struct ofbundle *bundle;
 914
 915     if (!clogged && !list_is_empty(&ofproto->completions)) {
 916         poll_immediate_wake();
 917     }
 918
 919     dpif_wait(ofproto->dpif);
 920     dpif_recv_wait(ofproto->dpif);
 921     if (ofproto->sflow) {
 922         dpif_sflow_wait(ofproto->sflow);
 923     }
 924     if (!tag_set_is_empty(&ofproto->revalidate_set)) {
 925         poll_immediate_wake();
 926     }
 927     HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
 928         port_wait(ofport);
 929     }
 930     HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
 931         bundle_wait(bundle);
 932     }
 933     if (ofproto->netflow) {
 934         netflow_wait(ofproto->netflow);
 935     }
 936     mac_learning_wait(ofproto->ml);
 937     stp_wait(ofproto);
 938     if (ofproto->need_revalidate) {
 939         /* Shouldn't happen, but if it does just go around again. */
 940         VLOG_DBG_RL(&rl, "need revalidate in ofproto_wait_cb()");
 941         poll_immediate_wake();
 942     } else {
 943         timer_wait(&ofproto->next_expiration);
 944     }
 945     if (ofproto->governor) {
 946         governor_wait(ofproto->governor);
 947     }
 948 }
 949
 950 static void
 951 flush(struct ofproto *ofproto_)
 952 {
 953     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 954     struct facet *facet, *next_facet;
 955
 956     HMAP_FOR_EACH_SAFE (facet, next_facet, hmap_node, &ofproto->facets) {
 957         /* Mark the facet as not installed so that facet_remove() doesn't
 958          * bother trying to uninstall it.  There is no point in uninstalling it
 959          * individually since we are about to blow away all the facets with
 960          * dpif_flow_flush(). */
 961         struct subfacet *subfacet;
 962
 963         LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
 964             subfacet->installed = false;
 965             subfacet->dp_packet_count = 0;
 966             subfacet->dp_byte_count = 0;
 967         }
 968         facet_remove(facet);
 969     }
 970     dpif_flow_flush(ofproto->dpif);
 971 }
 972
 973 static void
 974 get_features(struct ofproto *ofproto_ OVS_UNUSED,
 975              bool *arp_match_ip, enum ofputil_action_bitmap *actions)
 976 {
 977     *arp_match_ip = true;
 978     *actions = (OFPUTIL_A_OUTPUT |
 979                 OFPUTIL_A_SET_VLAN_VID |
 980                 OFPUTIL_A_SET_VLAN_PCP |
 981                 OFPUTIL_A_STRIP_VLAN |
 982                 OFPUTIL_A_SET_DL_SRC |
 983                 OFPUTIL_A_SET_DL_DST |
 984                 OFPUTIL_A_SET_NW_SRC |
 985                 OFPUTIL_A_SET_NW_DST |
 986                 OFPUTIL_A_SET_NW_TOS |
 987                 OFPUTIL_A_SET_TP_SRC |
 988                 OFPUTIL_A_SET_TP_DST |
 989                 OFPUTIL_A_ENQUEUE);
 990 }
 991
 992 static void
 993 get_tables(struct ofproto *ofproto_, struct ofp_table_stats *ots)
 994 {
 995     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
 996     struct dpif_dp_stats s;
 997
 998     strcpy(ots->name, "classifier");
 999
1000     dpif_get_dp_stats(ofproto->dpif, &s);
1001     put_32aligned_be64(&ots->lookup_count, htonll(s.n_hit + s.n_missed));
1002     put_32aligned_be64(&ots->matched_count,
1003                        htonll(s.n_hit + ofproto->n_matches));
1004 }
1005
1006 static struct ofport *
1007 port_alloc(void)
1008 {
1009     struct ofport_dpif *port = xmalloc(sizeof *port);
1010     return &port->up;
1011 }
1012
1013 static void
1014 port_dealloc(struct ofport *port_)
1015 {
1016     struct ofport_dpif *port = ofport_dpif_cast(port_);
1017     free(port);
1018 }
1019
1020 static int
1021 port_construct(struct ofport *port_)
1022 {
1023     struct ofport_dpif *port = ofport_dpif_cast(port_);
1024     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
1025
1026     ofproto->need_revalidate = true;
1027     port->odp_port = ofp_port_to_odp_port(port->up.ofp_port);
1028     port->bundle = NULL;
1029     port->cfm = NULL;
1030     port->tag = tag_create_random();
1031     port->may_enable = true;
1032     port->stp_port = NULL;
1033     port->stp_state = STP_DISABLED;
1034     hmap_init(&port->priorities);
1035     port->realdev_ofp_port = 0;
1036     port->vlandev_vid = 0;
1037     port->carrier_seq = netdev_get_carrier_resets(port->up.netdev);
1038
1039     if (ofproto->sflow) {
1040         dpif_sflow_add_port(ofproto->sflow, port_);
1041     }
1042
1043     return 0;
1044 }
1045
1046 static void
1047 port_destruct(struct ofport *port_)
1048 {
1049     struct ofport_dpif *port = ofport_dpif_cast(port_);
1050     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
1051
1052     ofproto->need_revalidate = true;
1053     bundle_remove(port_);
1054     set_cfm(port_, NULL);
1055     if (ofproto->sflow) {
1056         dpif_sflow_del_port(ofproto->sflow, port->odp_port);
1057     }
1058
1059     ofport_clear_priorities(port);
1060     hmap_destroy(&port->priorities);
1061 }
1062
1063 static void
1064 port_modified(struct ofport *port_)
1065 {
1066     struct ofport_dpif *port = ofport_dpif_cast(port_);
1067
1068     if (port->bundle && port->bundle->bond) {
1069         bond_slave_set_netdev(port->bundle->bond, port, port->up.netdev);
1070     }
1071 }
1072
1073 static void
1074 port_reconfigured(struct ofport *port_, enum ofputil_port_config old_config)
1075 {
1076     struct ofport_dpif *port = ofport_dpif_cast(port_);
1077     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
1078     enum ofputil_port_config changed = old_config ^ port->up.pp.config;
1079
1080     if (changed & (OFPUTIL_PC_NO_RECV | OFPUTIL_PC_NO_RECV_STP |
1081                    OFPUTIL_PC_NO_FWD | OFPUTIL_PC_NO_FLOOD)) {
1082         ofproto->need_revalidate = true;
1083
1084         if (changed & OFPUTIL_PC_NO_FLOOD && port->bundle) {
1085             bundle_update(port->bundle);
1086         }
1087     }
1088 }
1089
1090 static int
1091 set_sflow(struct ofproto *ofproto_,
1092           const struct ofproto_sflow_options *sflow_options)
1093 {
1094     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
1095     struct dpif_sflow *ds = ofproto->sflow;
1096
1097     if (sflow_options) {
1098         if (!ds) {
1099             struct ofport_dpif *ofport;
1100
1101             ds = ofproto->sflow = dpif_sflow_create(ofproto->dpif);
1102             HMAP_FOR_EACH (ofport, up.hmap_node, &ofproto->up.ports) {
1103                 dpif_sflow_add_port(ds, &ofport->up);
1104             }
1105             ofproto->need_revalidate = true;
1106         }
1107         dpif_sflow_set_options(ds, sflow_options);
1108     } else {
1109         if (ds) {
1110             dpif_sflow_destroy(ds);
1111             ofproto->need_revalidate = true;
1112             ofproto->sflow = NULL;
1113         }
1114     }
1115     return 0;
1116 }
1117
1118 static int
1119 set_cfm(struct ofport *ofport_, const struct cfm_settings *s)
1120 {
1121     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1122     int error;
1123
1124     if (!s) {
1125         error = 0;
1126     } else {
1127         if (!ofport->cfm) {
1128             struct ofproto_dpif *ofproto;
1129
1130             ofproto = ofproto_dpif_cast(ofport->up.ofproto);
1131             ofproto->need_revalidate = true;
1132             ofport->cfm = cfm_create(netdev_get_name(ofport->up.netdev));
1133         }
1134
1135         if (cfm_configure(ofport->cfm, s)) {
1136             return 0;
1137         }
1138
1139         error = EINVAL;
1140     }
1141     cfm_destroy(ofport->cfm);
1142     ofport->cfm = NULL;
1143     return error;
1144 }
1145
1146 static int
1147 get_cfm_fault(const struct ofport *ofport_)
1148 {
1149     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1150
1151     return ofport->cfm ? cfm_get_fault(ofport->cfm) : -1;
1152 }
1153
1154 static int
1155 get_cfm_remote_mpids(const struct ofport *ofport_, const uint64_t **rmps,
1156                      size_t *n_rmps)
1157 {
1158     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1159
1160     if (ofport->cfm) {
1161         cfm_get_remote_mpids(ofport->cfm, rmps, n_rmps);
1162         return 0;
1163     } else {
1164         return -1;
1165     }
1166 }
1167
1168 static int
1169 get_cfm_health(const struct ofport *ofport_)
1170 {
1171     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1172
1173     return ofport->cfm ? cfm_get_health(ofport->cfm) : -1;
1174 }
1175 \f
1176 /* Spanning Tree. */
1177
1178 static void
1179 send_bpdu_cb(struct ofpbuf *pkt, int port_num, void *ofproto_)
1180 {
1181     struct ofproto_dpif *ofproto = ofproto_;
1182     struct stp_port *sp = stp_get_port(ofproto->stp, port_num);
1183     struct ofport_dpif *ofport;
1184
1185     ofport = stp_port_get_aux(sp);
1186     if (!ofport) {
1187         VLOG_WARN_RL(&rl, "%s: cannot send BPDU on unknown port %d",
1188                      ofproto->up.name, port_num);
1189     } else {
1190         struct eth_header *eth = pkt->l2;
1191
1192         netdev_get_etheraddr(ofport->up.netdev, eth->eth_src);
1193         if (eth_addr_is_zero(eth->eth_src)) {
1194             VLOG_WARN_RL(&rl, "%s: cannot send BPDU on port %d "
1195                          "with unknown MAC", ofproto->up.name, port_num);
1196         } else {
1197             send_packet(ofport, pkt);
1198         }
1199     }
1200     ofpbuf_delete(pkt);
1201 }
1202
1203 /* Configures STP on 'ofproto_' using the settings defined in 's'. */
1204 static int
1205 set_stp(struct ofproto *ofproto_, const struct ofproto_stp_settings *s)
1206 {
1207     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
1208
1209     /* Only revalidate flows if the configuration changed. */
1210     if (!s != !ofproto->stp) {
1211         ofproto->need_revalidate = true;
1212     }
1213
1214     if (s) {
1215         if (!ofproto->stp) {
1216             ofproto->stp = stp_create(ofproto_->name, s->system_id,
1217                                       send_bpdu_cb, ofproto);
1218             ofproto->stp_last_tick = time_msec();
1219         }
1220
1221         stp_set_bridge_id(ofproto->stp, s->system_id);
1222         stp_set_bridge_priority(ofproto->stp, s->priority);
1223         stp_set_hello_time(ofproto->stp, s->hello_time);
1224         stp_set_max_age(ofproto->stp, s->max_age);
1225         stp_set_forward_delay(ofproto->stp, s->fwd_delay);
1226     }  else {
1227         struct ofport *ofport;
1228
1229         HMAP_FOR_EACH (ofport, hmap_node, &ofproto->up.ports) {
1230             set_stp_port(ofport, NULL);
1231         }
1232
1233         stp_destroy(ofproto->stp);
1234         ofproto->stp = NULL;
1235     }
1236
1237     return 0;
1238 }
1239
1240 static int
1241 get_stp_status(struct ofproto *ofproto_, struct ofproto_stp_status *s)
1242 {
1243     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
1244
1245     if (ofproto->stp) {
1246         s->enabled = true;
1247         s->bridge_id = stp_get_bridge_id(ofproto->stp);
1248         s->designated_root = stp_get_designated_root(ofproto->stp);
1249         s->root_path_cost = stp_get_root_path_cost(ofproto->stp);
1250     } else {
1251         s->enabled = false;
1252     }
1253
1254     return 0;
1255 }
1256
1257 static void
1258 update_stp_port_state(struct ofport_dpif *ofport)
1259 {
1260     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
1261     enum stp_state state;
1262
1263     /* Figure out new state. */
1264     state = ofport->stp_port ? stp_port_get_state(ofport->stp_port)
1265                              : STP_DISABLED;
1266
1267     /* Update state. */
1268     if (ofport->stp_state != state) {
1269         enum ofputil_port_state of_state;
1270         bool fwd_change;
1271
1272         VLOG_DBG_RL(&rl, "port %s: STP state changed from %s to %s",
1273                     netdev_get_name(ofport->up.netdev),
1274                     stp_state_name(ofport->stp_state),
1275                     stp_state_name(state));
1276         if (stp_learn_in_state(ofport->stp_state)
1277                 != stp_learn_in_state(state)) {
1278             /* xxx Learning action flows should also be flushed. */
1279             mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
1280         }
1281         fwd_change = stp_forward_in_state(ofport->stp_state)
1282                         != stp_forward_in_state(state);
1283
1284         ofproto->need_revalidate = true;
1285         ofport->stp_state = state;
1286         ofport->stp_state_entered = time_msec();
1287
1288         if (fwd_change && ofport->bundle) {
1289             bundle_update(ofport->bundle);
1290         }
1291
1292         /* Update the STP state bits in the OpenFlow port description. */
1293         of_state = ofport->up.pp.state & ~OFPUTIL_PS_STP_MASK;
1294         of_state |= (state == STP_LISTENING ? OFPUTIL_PS_STP_LISTEN
1295                      : state == STP_LEARNING ? OFPUTIL_PS_STP_LEARN
1296                      : state == STP_FORWARDING ? OFPUTIL_PS_STP_FORWARD
1297                      : state == STP_BLOCKING ?  OFPUTIL_PS_STP_BLOCK
1298                      : 0);
1299         ofproto_port_set_state(&ofport->up, of_state);
1300     }
1301 }
1302
1303 /* Configures STP on 'ofport_' using the settings defined in 's'.  The
1304  * caller is responsible for assigning STP port numbers and ensuring
1305  * there are no duplicates. */
1306 static int
1307 set_stp_port(struct ofport *ofport_,
1308              const struct ofproto_port_stp_settings *s)
1309 {
1310     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1311     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
1312     struct stp_port *sp = ofport->stp_port;
1313
1314     if (!s || !s->enable) {
1315         if (sp) {
1316             ofport->stp_port = NULL;
1317             stp_port_disable(sp);
1318             update_stp_port_state(ofport);
1319         }
1320         return 0;
1321     } else if (sp && stp_port_no(sp) != s->port_num
1322             && ofport == stp_port_get_aux(sp)) {
1323         /* The port-id changed, so disable the old one if it's not
1324          * already in use by another port. */
1325         stp_port_disable(sp);
1326     }
1327
1328     sp = ofport->stp_port = stp_get_port(ofproto->stp, s->port_num);
1329     stp_port_enable(sp);
1330
1331     stp_port_set_aux(sp, ofport);
1332     stp_port_set_priority(sp, s->priority);
1333     stp_port_set_path_cost(sp, s->path_cost);
1334
1335     update_stp_port_state(ofport);
1336
1337     return 0;
1338 }
1339
1340 static int
1341 get_stp_port_status(struct ofport *ofport_,
1342                     struct ofproto_port_stp_status *s)
1343 {
1344     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1345     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
1346     struct stp_port *sp = ofport->stp_port;
1347
1348     if (!ofproto->stp || !sp) {
1349         s->enabled = false;
1350         return 0;
1351     }
1352
1353     s->enabled = true;
1354     s->port_id = stp_port_get_id(sp);
1355     s->state = stp_port_get_state(sp);
1356     s->sec_in_state = (time_msec() - ofport->stp_state_entered) / 1000;
1357     s->role = stp_port_get_role(sp);
1358     stp_port_get_counts(sp, &s->tx_count, &s->rx_count, &s->error_count);
1359
1360     return 0;
1361 }
1362
1363 static void
1364 stp_run(struct ofproto_dpif *ofproto)
1365 {
1366     if (ofproto->stp) {
1367         long long int now = time_msec();
1368         long long int elapsed = now - ofproto->stp_last_tick;
1369         struct stp_port *sp;
1370
1371         if (elapsed > 0) {
1372             stp_tick(ofproto->stp, MIN(INT_MAX, elapsed));
1373             ofproto->stp_last_tick = now;
1374         }
1375         while (stp_get_changed_port(ofproto->stp, &sp)) {
1376             struct ofport_dpif *ofport = stp_port_get_aux(sp);
1377
1378             if (ofport) {
1379                 update_stp_port_state(ofport);
1380             }
1381         }
1382
1383         if (stp_check_and_reset_fdb_flush(ofproto->stp)) {
1384             mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
1385         }
1386     }
1387 }
1388
1389 static void
1390 stp_wait(struct ofproto_dpif *ofproto)
1391 {
1392     if (ofproto->stp) {
1393         poll_timer_wait(1000);
1394     }
1395 }
1396
1397 /* Returns true if STP should process 'flow'. */
1398 static bool
1399 stp_should_process_flow(const struct flow *flow)
1400 {
1401     return eth_addr_equals(flow->dl_dst, eth_addr_stp);
1402 }
1403
1404 static void
1405 stp_process_packet(const struct ofport_dpif *ofport,
1406                    const struct ofpbuf *packet)
1407 {
1408     struct ofpbuf payload = *packet;
1409     struct eth_header *eth = payload.data;
1410     struct stp_port *sp = ofport->stp_port;
1411
1412     /* Sink packets on ports that have STP disabled when the bridge has
1413      * STP enabled. */
1414     if (!sp || stp_port_get_state(sp) == STP_DISABLED) {
1415         return;
1416     }
1417
1418     /* Trim off padding on payload. */
1419     if (payload.size > ntohs(eth->eth_type) + ETH_HEADER_LEN) {
1420         payload.size = ntohs(eth->eth_type) + ETH_HEADER_LEN;
1421     }
1422
1423     if (ofpbuf_try_pull(&payload, ETH_HEADER_LEN + LLC_HEADER_LEN)) {
1424         stp_received_bpdu(sp, payload.data, payload.size);
1425     }
1426 }
1427 \f
1428 static struct priority_to_dscp *
1429 get_priority(const struct ofport_dpif *ofport, uint32_t priority)
1430 {
1431     struct priority_to_dscp *pdscp;
1432     uint32_t hash;
1433
1434     hash = hash_int(priority, 0);
1435     HMAP_FOR_EACH_IN_BUCKET (pdscp, hmap_node, hash, &ofport->priorities) {
1436         if (pdscp->priority == priority) {
1437             return pdscp;
1438         }
1439     }
1440     return NULL;
1441 }
1442
1443 static void
1444 ofport_clear_priorities(struct ofport_dpif *ofport)
1445 {
1446     struct priority_to_dscp *pdscp, *next;
1447
1448     HMAP_FOR_EACH_SAFE (pdscp, next, hmap_node, &ofport->priorities) {
1449         hmap_remove(&ofport->priorities, &pdscp->hmap_node);
1450         free(pdscp);
1451     }
1452 }
1453
1454 static int
1455 set_queues(struct ofport *ofport_,
1456            const struct ofproto_port_queue *qdscp_list,
1457            size_t n_qdscp)
1458 {
1459     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
1460     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
1461     struct hmap new = HMAP_INITIALIZER(&new);
1462     size_t i;
1463
1464     for (i = 0; i < n_qdscp; i++) {
1465         struct priority_to_dscp *pdscp;
1466         uint32_t priority;
1467         uint8_t dscp;
1468
1469         dscp = (qdscp_list[i].dscp << 2) & IP_DSCP_MASK;
1470         if (dpif_queue_to_priority(ofproto->dpif, qdscp_list[i].queue,
1471                                    &priority)) {
1472             continue;
1473         }
1474
1475         pdscp = get_priority(ofport, priority);
1476         if (pdscp) {
1477             hmap_remove(&ofport->priorities, &pdscp->hmap_node);
1478         } else {
1479             pdscp = xmalloc(sizeof *pdscp);
1480             pdscp->priority = priority;
1481             pdscp->dscp = dscp;
1482             ofproto->need_revalidate = true;
1483         }
1484
1485         if (pdscp->dscp != dscp) {
1486             pdscp->dscp = dscp;
1487             ofproto->need_revalidate = true;
1488         }
1489
1490         hmap_insert(&new, &pdscp->hmap_node, hash_int(pdscp->priority, 0));
1491     }
1492
1493     if (!hmap_is_empty(&ofport->priorities)) {
1494         ofport_clear_priorities(ofport);
1495         ofproto->need_revalidate = true;
1496     }
1497
1498     hmap_swap(&new, &ofport->priorities);
1499     hmap_destroy(&new);
1500
1501     return 0;
1502 }
1503 \f
1504 /* Bundles. */
1505
1506 /* Expires all MAC learning entries associated with 'bundle' and forces its
1507  * ofproto to revalidate every flow.
1508  *
1509  * Normally MAC learning entries are removed only from the ofproto associated
1510  * with 'bundle', but if 'all_ofprotos' is true, then the MAC learning entries
1511  * are removed from every ofproto.  When patch ports and SLB bonds are in use
1512  * and a VM migration happens and the gratuitous ARPs are somehow lost, this
1513  * avoids a MAC_ENTRY_IDLE_TIME delay before the migrated VM can communicate
1514  * with the host from which it migrated. */
1515 static void
1516 bundle_flush_macs(struct ofbundle *bundle, bool all_ofprotos)
1517 {
1518     struct ofproto_dpif *ofproto = bundle->ofproto;
1519     struct mac_learning *ml = ofproto->ml;
1520     struct mac_entry *mac, *next_mac;
1521
1522     ofproto->need_revalidate = true;
1523     LIST_FOR_EACH_SAFE (mac, next_mac, lru_node, &ml->lrus) {
1524         if (mac->port.p == bundle) {
1525             if (all_ofprotos) {
1526                 struct ofproto_dpif *o;
1527
1528                 HMAP_FOR_EACH (o, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
1529                     if (o != ofproto) {
1530                         struct mac_entry *e;
1531
1532                         e = mac_learning_lookup(o->ml, mac->mac, mac->vlan,
1533                                                 NULL);
1534                         if (e) {
1535                             tag_set_add(&o->revalidate_set, e->tag);
1536                             mac_learning_expire(o->ml, e);
1537                         }
1538                     }
1539                 }
1540             }
1541
1542             mac_learning_expire(ml, mac);
1543         }
1544     }
1545 }
1546
1547 static struct ofbundle *
1548 bundle_lookup(const struct ofproto_dpif *ofproto, void *aux)
1549 {
1550     struct ofbundle *bundle;
1551
1552     HMAP_FOR_EACH_IN_BUCKET (bundle, hmap_node, hash_pointer(aux, 0),
1553                              &ofproto->bundles) {
1554         if (bundle->aux == aux) {
1555             return bundle;
1556         }
1557     }
1558     return NULL;
1559 }
1560
1561 /* Looks up each of the 'n_auxes' pointers in 'auxes' as bundles and adds the
1562  * ones that are found to 'bundles'. */
1563 static void
1564 bundle_lookup_multiple(struct ofproto_dpif *ofproto,
1565                        void **auxes, size_t n_auxes,
1566                        struct hmapx *bundles)
1567 {
1568     size_t i;
1569
1570     hmapx_init(bundles);
1571     for (i = 0; i < n_auxes; i++) {
1572         struct ofbundle *bundle = bundle_lookup(ofproto, auxes[i]);
1573         if (bundle) {
1574             hmapx_add(bundles, bundle);
1575         }
1576     }
1577 }
1578
1579 static void
1580 bundle_update(struct ofbundle *bundle)
1581 {
1582     struct ofport_dpif *port;
1583
1584     bundle->floodable = true;
1585     LIST_FOR_EACH (port, bundle_node, &bundle->ports) {
1586         if (port->up.pp.config & OFPUTIL_PC_NO_FLOOD
1587             || !stp_forward_in_state(port->stp_state)) {
1588             bundle->floodable = false;
1589             break;
1590         }
1591     }
1592 }
1593
1594 static void
1595 bundle_del_port(struct ofport_dpif *port)
1596 {
1597     struct ofbundle *bundle = port->bundle;
1598
1599     bundle->ofproto->need_revalidate = true;
1600
1601     list_remove(&port->bundle_node);
1602     port->bundle = NULL;
1603
1604     if (bundle->lacp) {
1605         lacp_slave_unregister(bundle->lacp, port);
1606     }
1607     if (bundle->bond) {
1608         bond_slave_unregister(bundle->bond, port);
1609     }
1610
1611     bundle_update(bundle);
1612 }
1613
1614 static bool
1615 bundle_add_port(struct ofbundle *bundle, uint32_t ofp_port,
1616                 struct lacp_slave_settings *lacp,
1617                 uint32_t bond_stable_id)
1618 {
1619     struct ofport_dpif *port;
1620
1621     port = get_ofp_port(bundle->ofproto, ofp_port);
1622     if (!port) {
1623         return false;
1624     }
1625
1626     if (port->bundle != bundle) {
1627         bundle->ofproto->need_revalidate = true;
1628         if (port->bundle) {
1629             bundle_del_port(port);
1630         }
1631
1632         port->bundle = bundle;
1633         list_push_back(&bundle->ports, &port->bundle_node);
1634         if (port->up.pp.config & OFPUTIL_PC_NO_FLOOD
1635             || !stp_forward_in_state(port->stp_state)) {
1636             bundle->floodable = false;
1637         }
1638     }
1639     if (lacp) {
1640         port->bundle->ofproto->need_revalidate = true;
1641         lacp_slave_register(bundle->lacp, port, lacp);
1642     }
1643
1644     port->bond_stable_id = bond_stable_id;
1645
1646     return true;
1647 }
1648
1649 static void
1650 bundle_destroy(struct ofbundle *bundle)
1651 {
1652     struct ofproto_dpif *ofproto;
1653     struct ofport_dpif *port, *next_port;
1654     int i;
1655
1656     if (!bundle) {
1657         return;
1658     }
1659
1660     ofproto = bundle->ofproto;
1661     for (i = 0; i < MAX_MIRRORS; i++) {
1662         struct ofmirror *m = ofproto->mirrors[i];
1663         if (m) {
1664             if (m->out == bundle) {
1665                 mirror_destroy(m);
1666             } else if (hmapx_find_and_delete(&m->srcs, bundle)
1667                        || hmapx_find_and_delete(&m->dsts, bundle)) {
1668                 ofproto->need_revalidate = true;
1669             }
1670         }
1671     }
1672
1673     LIST_FOR_EACH_SAFE (port, next_port, bundle_node, &bundle->ports) {
1674         bundle_del_port(port);
1675     }
1676
1677     bundle_flush_macs(bundle, true);
1678     hmap_remove(&ofproto->bundles, &bundle->hmap_node);
1679     free(bundle->name);
1680     free(bundle->trunks);
1681     lacp_destroy(bundle->lacp);
1682     bond_destroy(bundle->bond);
1683     free(bundle);
1684 }
1685
1686 static int
1687 bundle_set(struct ofproto *ofproto_, void *aux,
1688            const struct ofproto_bundle_settings *s)
1689 {
1690     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
1691     bool need_flush = false;
1692     struct ofport_dpif *port;
1693     struct ofbundle *bundle;
1694     unsigned long *trunks;
1695     int vlan;
1696     size_t i;
1697     bool ok;
1698
1699     if (!s) {
1700         bundle_destroy(bundle_lookup(ofproto, aux));
1701         return 0;
1702     }
1703
1704     assert(s->n_slaves == 1 || s->bond != NULL);
1705     assert((s->lacp != NULL) == (s->lacp_slaves != NULL));
1706
1707     bundle = bundle_lookup(ofproto, aux);
1708     if (!bundle) {
1709         bundle = xmalloc(sizeof *bundle);
1710
1711         bundle->ofproto = ofproto;
1712         hmap_insert(&ofproto->bundles, &bundle->hmap_node,
1713                     hash_pointer(aux, 0));
1714         bundle->aux = aux;
1715         bundle->name = NULL;
1716
1717         list_init(&bundle->ports);
1718         bundle->vlan_mode = PORT_VLAN_TRUNK;
1719         bundle->vlan = -1;
1720         bundle->trunks = NULL;
1721         bundle->use_priority_tags = s->use_priority_tags;
1722         bundle->lacp = NULL;
1723         bundle->bond = NULL;
1724
1725         bundle->floodable = true;
1726
1727         bundle->src_mirrors = 0;
1728         bundle->dst_mirrors = 0;
1729         bundle->mirror_out = 0;
1730     }
1731
1732     if (!bundle->name || strcmp(s->name, bundle->name)) {
1733         free(bundle->name);
1734         bundle->name = xstrdup(s->name);
1735     }
1736
1737     /* LACP. */
1738     if (s->lacp) {
1739         if (!bundle->lacp) {
1740             ofproto->need_revalidate = true;
1741             bundle->lacp = lacp_create();
1742         }
1743         lacp_configure(bundle->lacp, s->lacp);
1744     } else {
1745         lacp_destroy(bundle->lacp);
1746         bundle->lacp = NULL;
1747     }
1748
1749     /* Update set of ports. */
1750     ok = true;
1751     for (i = 0; i < s->n_slaves; i++) {
1752         if (!bundle_add_port(bundle, s->slaves[i],
1753                              s->lacp ? &s->lacp_slaves[i] : NULL,
1754                              s->bond_stable_ids ? s->bond_stable_ids[i] : 0)) {
1755             ok = false;
1756         }
1757     }
1758     if (!ok || list_size(&bundle->ports) != s->n_slaves) {
1759         struct ofport_dpif *next_port;
1760
1761         LIST_FOR_EACH_SAFE (port, next_port, bundle_node, &bundle->ports) {
1762             for (i = 0; i < s->n_slaves; i++) {
1763                 if (s->slaves[i] == port->up.ofp_port) {
1764                     goto found;
1765                 }
1766             }
1767
1768             bundle_del_port(port);
1769         found: ;
1770         }
1771     }
1772     assert(list_size(&bundle->ports) <= s->n_slaves);
1773
1774     if (list_is_empty(&bundle->ports)) {
1775         bundle_destroy(bundle);
1776         return EINVAL;
1777     }
1778
1779     /* Set VLAN tagging mode */
1780     if (s->vlan_mode != bundle->vlan_mode
1781         || s->use_priority_tags != bundle->use_priority_tags) {
1782         bundle->vlan_mode = s->vlan_mode;
1783         bundle->use_priority_tags = s->use_priority_tags;
1784         need_flush = true;
1785     }
1786
1787     /* Set VLAN tag. */
1788     vlan = (s->vlan_mode == PORT_VLAN_TRUNK ? -1
1789             : s->vlan >= 0 && s->vlan <= 4095 ? s->vlan
1790             : 0);
1791     if (vlan != bundle->vlan) {
1792         bundle->vlan = vlan;
1793         need_flush = true;
1794     }
1795
1796     /* Get trunked VLANs. */
1797     switch (s->vlan_mode) {
1798     case PORT_VLAN_ACCESS:
1799         trunks = NULL;
1800         break;
1801
1802     case PORT_VLAN_TRUNK:
1803         trunks = (unsigned long *) s->trunks;
1804         break;
1805
1806     case PORT_VLAN_NATIVE_UNTAGGED:
1807     case PORT_VLAN_NATIVE_TAGGED:
1808         if (vlan != 0 && (!s->trunks
1809                           || !bitmap_is_set(s->trunks, vlan)
1810                           || bitmap_is_set(s->trunks, 0))) {
1811             /* Force trunking the native VLAN and prohibit trunking VLAN 0. */
1812             if (s->trunks) {
1813                 trunks = bitmap_clone(s->trunks, 4096);
1814             } else {
1815                 trunks = bitmap_allocate1(4096);
1816             }
1817             bitmap_set1(trunks, vlan);
1818             bitmap_set0(trunks, 0);
1819         } else {
1820             trunks = (unsigned long *) s->trunks;
1821         }
1822         break;
1823
1824     default:
1825         NOT_REACHED();
1826     }
1827     if (!vlan_bitmap_equal(trunks, bundle->trunks)) {
1828         free(bundle->trunks);
1829         if (trunks == s->trunks) {
1830             bundle->trunks = vlan_bitmap_clone(trunks);
1831         } else {
1832             bundle->trunks = trunks;
1833             trunks = NULL;
1834         }
1835         need_flush = true;
1836     }
1837     if (trunks != s->trunks) {
1838         free(trunks);
1839     }
1840
1841     /* Bonding. */
1842     if (!list_is_short(&bundle->ports)) {
1843         bundle->ofproto->has_bonded_bundles = true;
1844         if (bundle->bond) {
1845             if (bond_reconfigure(bundle->bond, s->bond)) {
1846                 ofproto->need_revalidate = true;
1847             }
1848         } else {
1849             bundle->bond = bond_create(s->bond);
1850             ofproto->need_revalidate = true;
1851         }
1852
1853         LIST_FOR_EACH (port, bundle_node, &bundle->ports) {
1854             bond_slave_register(bundle->bond, port, port->bond_stable_id,
1855                                 port->up.netdev);
1856         }
1857     } else {
1858         bond_destroy(bundle->bond);
1859         bundle->bond = NULL;
1860     }
1861
1862     /* If we changed something that would affect MAC learning, un-learn
1863      * everything on this port and force flow revalidation. */
1864     if (need_flush) {
1865         bundle_flush_macs(bundle, false);
1866     }
1867
1868     return 0;
1869 }
1870
1871 static void
1872 bundle_remove(struct ofport *port_)
1873 {
1874     struct ofport_dpif *port = ofport_dpif_cast(port_);
1875     struct ofbundle *bundle = port->bundle;
1876
1877     if (bundle) {
1878         bundle_del_port(port);
1879         if (list_is_empty(&bundle->ports)) {
1880             bundle_destroy(bundle);
1881         } else if (list_is_short(&bundle->ports)) {
1882             bond_destroy(bundle->bond);
1883             bundle->bond = NULL;
1884         }
1885     }
1886 }
1887
1888 static void
1889 send_pdu_cb(void *port_, const void *pdu, size_t pdu_size)
1890 {
1891     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 10);
1892     struct ofport_dpif *port = port_;
1893     uint8_t ea[ETH_ADDR_LEN];
1894     int error;
1895
1896     error = netdev_get_etheraddr(port->up.netdev, ea);
1897     if (!error) {
1898         struct ofpbuf packet;
1899         void *packet_pdu;
1900
1901         ofpbuf_init(&packet, 0);
1902         packet_pdu = eth_compose(&packet, eth_addr_lacp, ea, ETH_TYPE_LACP,
1903                                  pdu_size);
1904         memcpy(packet_pdu, pdu, pdu_size);
1905
1906         send_packet(port, &packet);
1907         ofpbuf_uninit(&packet);
1908     } else {
1909         VLOG_ERR_RL(&rl, "port %s: cannot obtain Ethernet address of iface "
1910                     "%s (%s)", port->bundle->name,
1911                     netdev_get_name(port->up.netdev), strerror(error));
1912     }
1913 }
1914
1915 static void
1916 bundle_send_learning_packets(struct ofbundle *bundle)
1917 {
1918     struct ofproto_dpif *ofproto = bundle->ofproto;
1919     int error, n_packets, n_errors;
1920     struct mac_entry *e;
1921
1922     error = n_packets = n_errors = 0;
1923     LIST_FOR_EACH (e, lru_node, &ofproto->ml->lrus) {
1924         if (e->port.p != bundle) {
1925             struct ofpbuf *learning_packet;
1926             struct ofport_dpif *port;
1927             void *port_void;
1928             int ret;
1929
1930             /* The assignment to "port" is unnecessary but makes "grep"ing for
1931              * struct ofport_dpif more effective. */
1932             learning_packet = bond_compose_learning_packet(bundle->bond,
1933                                                            e->mac, e->vlan,
1934                                                            &port_void);
1935             port = port_void;
1936             ret = send_packet(port, learning_packet);
1937             ofpbuf_delete(learning_packet);
1938             if (ret) {
1939                 error = ret;
1940                 n_errors++;
1941             }
1942             n_packets++;
1943         }
1944     }
1945
1946     if (n_errors) {
1947         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
1948         VLOG_WARN_RL(&rl, "bond %s: %d errors sending %d gratuitous learning "
1949                      "packets, last error was: %s",
1950                      bundle->name, n_errors, n_packets, strerror(error));
1951     } else {
1952         VLOG_DBG("bond %s: sent %d gratuitous learning packets",
1953                  bundle->name, n_packets);
1954     }
1955 }
1956
1957 static void
1958 bundle_run(struct ofbundle *bundle)
1959 {
1960     if (bundle->lacp) {
1961         lacp_run(bundle->lacp, send_pdu_cb);
1962     }
1963     if (bundle->bond) {
1964         struct ofport_dpif *port;
1965
1966         LIST_FOR_EACH (port, bundle_node, &bundle->ports) {
1967             bond_slave_set_may_enable(bundle->bond, port, port->may_enable);
1968         }
1969
1970         bond_run(bundle->bond, &bundle->ofproto->revalidate_set,
1971                  lacp_status(bundle->lacp));
1972         if (bond_should_send_learning_packets(bundle->bond)) {
1973             bundle_send_learning_packets(bundle);
1974         }
1975     }
1976 }
1977
1978 static void
1979 bundle_wait(struct ofbundle *bundle)
1980 {
1981     if (bundle->lacp) {
1982         lacp_wait(bundle->lacp);
1983     }
1984     if (bundle->bond) {
1985         bond_wait(bundle->bond);
1986     }
1987 }
1988 \f
1989 /* Mirrors. */
1990
1991 static int
1992 mirror_scan(struct ofproto_dpif *ofproto)
1993 {
1994     int idx;
1995
1996     for (idx = 0; idx < MAX_MIRRORS; idx++) {
1997         if (!ofproto->mirrors[idx]) {
1998             return idx;
1999         }
2000     }
2001     return -1;
2002 }
2003
2004 static struct ofmirror *
2005 mirror_lookup(struct ofproto_dpif *ofproto, void *aux)
2006 {
2007     int i;
2008
2009     for (i = 0; i < MAX_MIRRORS; i++) {
2010         struct ofmirror *mirror = ofproto->mirrors[i];
2011         if (mirror && mirror->aux == aux) {
2012             return mirror;
2013         }
2014     }
2015
2016     return NULL;
2017 }
2018
2019 /* Update the 'dup_mirrors' member of each of the ofmirrors in 'ofproto'. */
2020 static void
2021 mirror_update_dups(struct ofproto_dpif *ofproto)
2022 {
2023     int i;
2024
2025     for (i = 0; i < MAX_MIRRORS; i++) {
2026         struct ofmirror *m = ofproto->mirrors[i];
2027
2028         if (m) {
2029             m->dup_mirrors = MIRROR_MASK_C(1) << i;
2030         }
2031     }
2032
2033     for (i = 0; i < MAX_MIRRORS; i++) {
2034         struct ofmirror *m1 = ofproto->mirrors[i];
2035         int j;
2036
2037         if (!m1) {
2038             continue;
2039         }
2040
2041         for (j = i + 1; j < MAX_MIRRORS; j++) {
2042             struct ofmirror *m2 = ofproto->mirrors[j];
2043
2044             if (m2 && m1->out == m2->out && m1->out_vlan == m2->out_vlan) {
2045                 m1->dup_mirrors |= MIRROR_MASK_C(1) << j;
2046                 m2->dup_mirrors |= m1->dup_mirrors;
2047             }
2048         }
2049     }
2050 }
2051
2052 static int
2053 mirror_set(struct ofproto *ofproto_, void *aux,
2054            const struct ofproto_mirror_settings *s)
2055 {
2056     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2057     mirror_mask_t mirror_bit;
2058     struct ofbundle *bundle;
2059     struct ofmirror *mirror;
2060     struct ofbundle *out;
2061     struct hmapx srcs;          /* Contains "struct ofbundle *"s. */
2062     struct hmapx dsts;          /* Contains "struct ofbundle *"s. */
2063     int out_vlan;
2064
2065     mirror = mirror_lookup(ofproto, aux);
2066     if (!s) {
2067         mirror_destroy(mirror);
2068         return 0;
2069     }
2070     if (!mirror) {
2071         int idx;
2072
2073         idx = mirror_scan(ofproto);
2074         if (idx < 0) {
2075             VLOG_WARN("bridge %s: maximum of %d port mirrors reached, "
2076                       "cannot create %s",
2077                       ofproto->up.name, MAX_MIRRORS, s->name);
2078             return EFBIG;
2079         }
2080
2081         mirror = ofproto->mirrors[idx] = xzalloc(sizeof *mirror);
2082         mirror->ofproto = ofproto;
2083         mirror->idx = idx;
2084         mirror->aux = aux;
2085         mirror->out_vlan = -1;
2086         mirror->name = NULL;
2087     }
2088
2089     if (!mirror->name || strcmp(s->name, mirror->name)) {
2090         free(mirror->name);
2091         mirror->name = xstrdup(s->name);
2092     }
2093
2094     /* Get the new configuration. */
2095     if (s->out_bundle) {
2096         out = bundle_lookup(ofproto, s->out_bundle);
2097         if (!out) {
2098             mirror_destroy(mirror);
2099             return EINVAL;
2100         }
2101         out_vlan = -1;
2102     } else {
2103         out = NULL;
2104         out_vlan = s->out_vlan;
2105     }
2106     bundle_lookup_multiple(ofproto, s->srcs, s->n_srcs, &srcs);
2107     bundle_lookup_multiple(ofproto, s->dsts, s->n_dsts, &dsts);
2108
2109     /* If the configuration has not changed, do nothing. */
2110     if (hmapx_equals(&srcs, &mirror->srcs)
2111         && hmapx_equals(&dsts, &mirror->dsts)
2112         && vlan_bitmap_equal(mirror->vlans, s->src_vlans)
2113         && mirror->out == out
2114         && mirror->out_vlan == out_vlan)
2115     {
2116         hmapx_destroy(&srcs);
2117         hmapx_destroy(&dsts);
2118         return 0;
2119     }
2120
2121     hmapx_swap(&srcs, &mirror->srcs);
2122     hmapx_destroy(&srcs);
2123
2124     hmapx_swap(&dsts, &mirror->dsts);
2125     hmapx_destroy(&dsts);
2126
2127     free(mirror->vlans);
2128     mirror->vlans = vlan_bitmap_clone(s->src_vlans);
2129
2130     mirror->out = out;
2131     mirror->out_vlan = out_vlan;
2132
2133     /* Update bundles. */
2134     mirror_bit = MIRROR_MASK_C(1) << mirror->idx;
2135     HMAP_FOR_EACH (bundle, hmap_node, &mirror->ofproto->bundles) {
2136         if (hmapx_contains(&mirror->srcs, bundle)) {
2137             bundle->src_mirrors |= mirror_bit;
2138         } else {
2139             bundle->src_mirrors &= ~mirror_bit;
2140         }
2141
2142         if (hmapx_contains(&mirror->dsts, bundle)) {
2143             bundle->dst_mirrors |= mirror_bit;
2144         } else {
2145             bundle->dst_mirrors &= ~mirror_bit;
2146         }
2147
2148         if (mirror->out == bundle) {
2149             bundle->mirror_out |= mirror_bit;
2150         } else {
2151             bundle->mirror_out &= ~mirror_bit;
2152         }
2153     }
2154
2155     ofproto->need_revalidate = true;
2156     mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
2157     mirror_update_dups(ofproto);
2158
2159     return 0;
2160 }
2161
2162 static void
2163 mirror_destroy(struct ofmirror *mirror)
2164 {
2165     struct ofproto_dpif *ofproto;
2166     mirror_mask_t mirror_bit;
2167     struct ofbundle *bundle;
2168
2169     if (!mirror) {
2170         return;
2171     }
2172
2173     ofproto = mirror->ofproto;
2174     ofproto->need_revalidate = true;
2175     mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
2176
2177     mirror_bit = MIRROR_MASK_C(1) << mirror->idx;
2178     HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
2179         bundle->src_mirrors &= ~mirror_bit;
2180         bundle->dst_mirrors &= ~mirror_bit;
2181         bundle->mirror_out &= ~mirror_bit;
2182     }
2183
2184     hmapx_destroy(&mirror->srcs);
2185     hmapx_destroy(&mirror->dsts);
2186     free(mirror->vlans);
2187
2188     ofproto->mirrors[mirror->idx] = NULL;
2189     free(mirror->name);
2190     free(mirror);
2191
2192     mirror_update_dups(ofproto);
2193 }
2194
2195 static int
2196 mirror_get_stats(struct ofproto *ofproto_, void *aux,
2197                  uint64_t *packets, uint64_t *bytes)
2198 {
2199     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2200     struct ofmirror *mirror = mirror_lookup(ofproto, aux);
2201
2202     if (!mirror) {
2203         *packets = *bytes = UINT64_MAX;
2204         return 0;
2205     }
2206
2207     *packets = mirror->packet_count;
2208     *bytes = mirror->byte_count;
2209
2210     return 0;
2211 }
2212
2213 static int
2214 set_flood_vlans(struct ofproto *ofproto_, unsigned long *flood_vlans)
2215 {
2216     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2217     if (mac_learning_set_flood_vlans(ofproto->ml, flood_vlans)) {
2218         mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
2219     }
2220     return 0;
2221 }
2222
2223 static bool
2224 is_mirror_output_bundle(const struct ofproto *ofproto_, void *aux)
2225 {
2226     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2227     struct ofbundle *bundle = bundle_lookup(ofproto, aux);
2228     return bundle && bundle->mirror_out != 0;
2229 }
2230
2231 static void
2232 forward_bpdu_changed(struct ofproto *ofproto_)
2233 {
2234     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2235     /* Revalidate cached flows whenever forward_bpdu option changes. */
2236     ofproto->need_revalidate = true;
2237 }
2238
2239 static void
2240 set_mac_idle_time(struct ofproto *ofproto_, unsigned int idle_time)
2241 {
2242     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2243     mac_learning_set_idle_time(ofproto->ml, idle_time);
2244 }
2245 \f
2246 /* Ports. */
2247
2248 static struct ofport_dpif *
2249 get_ofp_port(struct ofproto_dpif *ofproto, uint16_t ofp_port)
2250 {
2251     struct ofport *ofport = ofproto_get_port(&ofproto->up, ofp_port);
2252     return ofport ? ofport_dpif_cast(ofport) : NULL;
2253 }
2254
2255 static struct ofport_dpif *
2256 get_odp_port(struct ofproto_dpif *ofproto, uint32_t odp_port)
2257 {
2258     return get_ofp_port(ofproto, odp_port_to_ofp_port(odp_port));
2259 }
2260
2261 static void
2262 ofproto_port_from_dpif_port(struct ofproto_port *ofproto_port,
2263                             struct dpif_port *dpif_port)
2264 {
2265     ofproto_port->name = dpif_port->name;
2266     ofproto_port->type = dpif_port->type;
2267     ofproto_port->ofp_port = odp_port_to_ofp_port(dpif_port->port_no);
2268 }
2269
2270 static void
2271 port_run(struct ofport_dpif *ofport)
2272 {
2273     long long int carrier_seq = netdev_get_carrier_resets(ofport->up.netdev);
2274     bool carrier_changed = carrier_seq != ofport->carrier_seq;
2275     bool enable = netdev_get_carrier(ofport->up.netdev);
2276
2277     ofport->carrier_seq = carrier_seq;
2278
2279     if (ofport->cfm) {
2280         cfm_run(ofport->cfm);
2281
2282         if (cfm_should_send_ccm(ofport->cfm)) {
2283             struct ofpbuf packet;
2284
2285             ofpbuf_init(&packet, 0);
2286             cfm_compose_ccm(ofport->cfm, &packet, ofport->up.pp.hw_addr);
2287             send_packet(ofport, &packet);
2288             ofpbuf_uninit(&packet);
2289         }
2290
2291         enable = enable && !cfm_get_fault(ofport->cfm)
2292             && cfm_get_opup(ofport->cfm);
2293     }
2294
2295     if (ofport->bundle) {
2296         enable = enable && lacp_slave_may_enable(ofport->bundle->lacp, ofport);
2297         if (carrier_changed) {
2298             lacp_slave_carrier_changed(ofport->bundle->lacp, ofport);
2299         }
2300     }
2301
2302     if (ofport->may_enable != enable) {
2303         struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
2304
2305         if (ofproto->has_bundle_action) {
2306             ofproto->need_revalidate = true;
2307         }
2308     }
2309
2310     ofport->may_enable = enable;
2311 }
2312
2313 static void
2314 port_wait(struct ofport_dpif *ofport)
2315 {
2316     if (ofport->cfm) {
2317         cfm_wait(ofport->cfm);
2318     }
2319 }
2320
2321 static int
2322 port_query_by_name(const struct ofproto *ofproto_, const char *devname,
2323                    struct ofproto_port *ofproto_port)
2324 {
2325     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2326     struct dpif_port dpif_port;
2327     int error;
2328
2329     error = dpif_port_query_by_name(ofproto->dpif, devname, &dpif_port);
2330     if (!error) {
2331         ofproto_port_from_dpif_port(ofproto_port, &dpif_port);
2332     }
2333     return error;
2334 }
2335
2336 static int
2337 port_add(struct ofproto *ofproto_, struct netdev *netdev, uint16_t *ofp_portp)
2338 {
2339     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2340     uint16_t odp_port;
2341     int error;
2342
2343     error = dpif_port_add(ofproto->dpif, netdev, &odp_port);
2344     if (!error) {
2345         *ofp_portp = odp_port_to_ofp_port(odp_port);
2346     }
2347     return error;
2348 }
2349
2350 static int
2351 port_del(struct ofproto *ofproto_, uint16_t ofp_port)
2352 {
2353     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2354     int error;
2355
2356     error = dpif_port_del(ofproto->dpif, ofp_port_to_odp_port(ofp_port));
2357     if (!error) {
2358         struct ofport_dpif *ofport = get_ofp_port(ofproto, ofp_port);
2359         if (ofport) {
2360             /* The caller is going to close ofport->up.netdev.  If this is a
2361              * bonded port, then the bond is using that netdev, so remove it
2362              * from the bond.  The client will need to reconfigure everything
2363              * after deleting ports, so then the slave will get re-added. */
2364             bundle_remove(&ofport->up);
2365         }
2366     }
2367     return error;
2368 }
2369
2370 static int
2371 port_get_stats(const struct ofport *ofport_, struct netdev_stats *stats)
2372 {
2373     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
2374     int error;
2375
2376     error = netdev_get_stats(ofport->up.netdev, stats);
2377
2378     if (!error && ofport->odp_port == OVSP_LOCAL) {
2379         struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
2380
2381         /* ofproto->stats.tx_packets represents packets that we created
2382          * internally and sent to some port (e.g. packets sent with
2383          * send_packet()).  Account for them as if they had come from
2384          * OFPP_LOCAL and got forwarded. */
2385
2386         if (stats->rx_packets != UINT64_MAX) {
2387             stats->rx_packets += ofproto->stats.tx_packets;
2388         }
2389
2390         if (stats->rx_bytes != UINT64_MAX) {
2391             stats->rx_bytes += ofproto->stats.tx_bytes;
2392         }
2393
2394         /* ofproto->stats.rx_packets represents packets that were received on
2395          * some port and we processed internally and dropped (e.g. STP).
2396          * Account fro them as if they had been forwarded to OFPP_LOCAL. */
2397
2398         if (stats->tx_packets != UINT64_MAX) {
2399             stats->tx_packets += ofproto->stats.rx_packets;
2400         }
2401
2402         if (stats->tx_bytes != UINT64_MAX) {
2403             stats->tx_bytes += ofproto->stats.rx_bytes;
2404         }
2405     }
2406
2407     return error;
2408 }
2409
2410 /* Account packets for LOCAL port. */
2411 static void
2412 ofproto_update_local_port_stats(const struct ofproto *ofproto_,
2413                                 size_t tx_size, size_t rx_size)
2414 {
2415     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2416
2417     if (rx_size) {
2418         ofproto->stats.rx_packets++;
2419         ofproto->stats.rx_bytes += rx_size;
2420     }
2421     if (tx_size) {
2422         ofproto->stats.tx_packets++;
2423         ofproto->stats.tx_bytes += tx_size;
2424     }
2425 }
2426
2427 struct port_dump_state {
2428     struct dpif_port_dump dump;
2429     bool done;
2430 };
2431
2432 static int
2433 port_dump_start(const struct ofproto *ofproto_, void **statep)
2434 {
2435     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2436     struct port_dump_state *state;
2437
2438     *statep = state = xmalloc(sizeof *state);
2439     dpif_port_dump_start(&state->dump, ofproto->dpif);
2440     state->done = false;
2441     return 0;
2442 }
2443
2444 static int
2445 port_dump_next(const struct ofproto *ofproto_ OVS_UNUSED, void *state_,
2446                struct ofproto_port *port)
2447 {
2448     struct port_dump_state *state = state_;
2449     struct dpif_port dpif_port;
2450
2451     if (dpif_port_dump_next(&state->dump, &dpif_port)) {
2452         ofproto_port_from_dpif_port(port, &dpif_port);
2453         return 0;
2454     } else {
2455         int error = dpif_port_dump_done(&state->dump);
2456         state->done = true;
2457         return error ? error : EOF;
2458     }
2459 }
2460
2461 static int
2462 port_dump_done(const struct ofproto *ofproto_ OVS_UNUSED, void *state_)
2463 {
2464     struct port_dump_state *state = state_;
2465
2466     if (!state->done) {
2467         dpif_port_dump_done(&state->dump);
2468     }
2469     free(state);
2470     return 0;
2471 }
2472
2473 static int
2474 port_poll(const struct ofproto *ofproto_, char **devnamep)
2475 {
2476     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2477     return dpif_port_poll(ofproto->dpif, devnamep);
2478 }
2479
2480 static void
2481 port_poll_wait(const struct ofproto *ofproto_)
2482 {
2483     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
2484     dpif_port_poll_wait(ofproto->dpif);
2485 }
2486
2487 static int
2488 port_is_lacp_current(const struct ofport *ofport_)
2489 {
2490     const struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
2491     return (ofport->bundle && ofport->bundle->lacp
2492             ? lacp_slave_is_current(ofport->bundle->lacp, ofport)
2493             : -1);
2494 }
2495 \f
2496 /* Upcall handling. */
2497
2498 /* Flow miss batching.
2499  *
2500  * Some dpifs implement operations faster when you hand them off in a batch.
2501  * To allow batching, "struct flow_miss" queues the dpif-related work needed
2502  * for a given flow.  Each "struct flow_miss" corresponds to sending one or
2503  * more packets, plus possibly installing the flow in the dpif.
2504  *
2505  * So far we only batch the operations that affect flow setup time the most.
2506  * It's possible to batch more than that, but the benefit might be minimal. */
2507 struct flow_miss {
2508     struct hmap_node hmap_node;
2509     struct flow flow;
2510     enum odp_key_fitness key_fitness;
2511     const struct nlattr *key;
2512     size_t key_len;
2513     ovs_be16 initial_tci;
2514     struct list packets;
2515 };
2516
2517 struct flow_miss_op {
2518     struct dpif_op dpif_op;
2519     struct subfacet *subfacet;  /* Subfacet  */
2520     void *garbage;              /* Pointer to pass to free(), NULL if none. */
2521     uint64_t stub[1024 / 8];    /* Temporary buffer. */
2522 };
2523
2524 /* Sends an OFPT_PACKET_IN message for 'packet' of type OFPR_NO_MATCH to each
2525  * OpenFlow controller as necessary according to their individual
2526  * configurations. */
2527 static void
2528 send_packet_in_miss(struct ofproto_dpif *ofproto, const struct ofpbuf *packet,
2529                     const struct flow *flow)
2530 {
2531     struct ofputil_packet_in pin;
2532
2533     pin.packet = packet->data;
2534     pin.packet_len = packet->size;
2535     pin.reason = OFPR_NO_MATCH;
2536     pin.controller_id = 0;
2537
2538     pin.table_id = 0;
2539     pin.cookie = 0;
2540
2541     pin.send_len = 0;           /* not used for flow table misses */
2542
2543     flow_get_metadata(flow, &pin.fmd);
2544
2545     /* Registers aren't meaningful on a miss. */
2546     memset(pin.fmd.reg_masks, 0, sizeof pin.fmd.reg_masks);
2547
2548     connmgr_send_packet_in(ofproto->up.connmgr, &pin);
2549 }
2550
2551 static bool
2552 process_special(struct ofproto_dpif *ofproto, const struct flow *flow,
2553                 const struct ofpbuf *packet)
2554 {
2555     struct ofport_dpif *ofport = get_ofp_port(ofproto, flow->in_port);
2556
2557     if (!ofport) {
2558         return false;
2559     }
2560
2561     if (ofport->cfm && cfm_should_process_flow(ofport->cfm, flow)) {
2562         if (packet) {
2563             cfm_process_heartbeat(ofport->cfm, packet);
2564         }
2565         return true;
2566     } else if (ofport->bundle && ofport->bundle->lacp
2567                && flow->dl_type == htons(ETH_TYPE_LACP)) {
2568         if (packet) {
2569             lacp_process_packet(ofport->bundle->lacp, ofport, packet);
2570         }
2571         return true;
2572     } else if (ofproto->stp && stp_should_process_flow(flow)) {
2573         if (packet) {
2574             stp_process_packet(ofport, packet);
2575         }
2576         return true;
2577     }
2578     return false;
2579 }
2580
2581 static struct flow_miss *
2582 flow_miss_find(struct hmap *todo, const struct flow *flow, uint32_t hash)
2583 {
2584     struct flow_miss *miss;
2585
2586     HMAP_FOR_EACH_WITH_HASH (miss, hmap_node, hash, todo) {
2587         if (flow_equal(&miss->flow, flow)) {
2588             return miss;
2589         }
2590     }
2591
2592     return NULL;
2593 }
2594
2595 /* Partially Initializes 'op' as an "execute" operation for 'miss' and
2596  * 'packet'.  The caller must initialize op->actions and op->actions_len.  If
2597  * 'miss' is associated with a subfacet the caller must also initialize the
2598  * returned op->subfacet, and if anything needs to be freed after processing
2599  * the op, the caller must initialize op->garbage also. */
2600 static void
2601 init_flow_miss_execute_op(struct flow_miss *miss, struct ofpbuf *packet,
2602                           struct flow_miss_op *op)
2603 {
2604     if (miss->flow.vlan_tci != miss->initial_tci) {
2605         /* This packet was received on a VLAN splinter port.  We
2606          * added a VLAN to the packet to make the packet resemble
2607          * the flow, but the actions were composed assuming that
2608          * the packet contained no VLAN.  So, we must remove the
2609          * VLAN header from the packet before trying to execute the
2610          * actions. */
2611         eth_pop_vlan(packet);
2612     }
2613
2614     op->subfacet = NULL;
2615     op->garbage = NULL;
2616     op->dpif_op.type = DPIF_OP_EXECUTE;
2617     op->dpif_op.u.execute.key = miss->key;
2618     op->dpif_op.u.execute.key_len = miss->key_len;
2619     op->dpif_op.u.execute.packet = packet;
2620 }
2621
2622 /* Helper for handle_flow_miss_without_facet() and
2623  * handle_flow_miss_with_facet(). */
2624 static void
2625 handle_flow_miss_common(struct rule_dpif *rule,
2626                         struct ofpbuf *packet, const struct flow *flow)
2627 {
2628     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
2629
2630     ofproto->n_matches++;
2631
2632     if (rule->up.cr.priority == FAIL_OPEN_PRIORITY) {
2633         /*
2634          * Extra-special case for fail-open mode.
2635          *
2636          * We are in fail-open mode and the packet matched the fail-open
2637          * rule, but we are connected to a controller too.  We should send
2638          * the packet up to the controller in the hope that it will try to
2639          * set up a flow and thereby allow us to exit fail-open.
2640          *
2641          * See the top-level comment in fail-open.c for more information.
2642          */
2643         send_packet_in_miss(ofproto, packet, flow);
2644     }
2645 }
2646
2647 /* Figures out whether a flow that missed in 'ofproto', whose details are in
2648  * 'miss', is likely to be worth tracking in detail in userspace and (usually)
2649  * installing a datapath flow.  The answer is usually "yes" (a return value of
2650  * true).  However, for short flows the cost of bookkeeping is much higher than
2651  * the benefits, so when the datapath holds a large number of flows we impose
2652  * some heuristics to decide which flows are likely to be worth tracking. */
2653 static bool
2654 flow_miss_should_make_facet(struct ofproto_dpif *ofproto,
2655                             struct flow_miss *miss, uint32_t hash)
2656 {
2657     if (!ofproto->governor) {
2658         size_t n_subfacets;
2659
2660         n_subfacets = hmap_count(&ofproto->subfacets);
2661         if (n_subfacets * 2 <= ofproto->up.flow_eviction_threshold) {
2662             return true;
2663         }
2664
2665         ofproto->governor = governor_create(ofproto->up.name);
2666     }
2667
2668     return governor_should_install_flow(ofproto->governor, hash,
2669                                         list_size(&miss->packets));
2670 }
2671
2672 /* Handles 'miss', which matches 'rule', without creating a facet or subfacet
2673  * or creating any datapath flow.  May add an "execute" operation to 'ops' and
2674  * increment '*n_ops'. */
2675 static void
2676 handle_flow_miss_without_facet(struct flow_miss *miss,
2677                                struct rule_dpif *rule,
2678                                struct flow_miss_op *ops, size_t *n_ops)
2679 {
2680     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
2681     struct action_xlate_ctx ctx;
2682     struct ofpbuf *packet;
2683
2684     LIST_FOR_EACH (packet, list_node, &miss->packets) {
2685         struct flow_miss_op *op = &ops[*n_ops];
2686         struct dpif_flow_stats stats;
2687         struct ofpbuf odp_actions;
2688
2689         COVERAGE_INC(facet_suppress);
2690
2691         ofpbuf_use_stub(&odp_actions, op->stub, sizeof op->stub);
2692
2693         dpif_flow_stats_extract(&miss->flow, packet, &stats);
2694         rule_credit_stats(rule, &stats);
2695
2696         action_xlate_ctx_init(&ctx, ofproto, &miss->flow, miss->initial_tci,
2697                               rule, 0, packet);
2698         ctx.resubmit_stats = &stats;
2699         xlate_actions(&ctx, rule->up.actions, rule->up.n_actions,
2700                       &odp_actions);
2701
2702         if (odp_actions.size) {
2703             struct dpif_execute *execute = &op->dpif_op.u.execute;
2704
2705             init_flow_miss_execute_op(miss, packet, op);
2706             execute->actions = odp_actions.data;
2707             execute->actions_len = odp_actions.size;
2708             op->garbage = ofpbuf_get_uninit_pointer(&odp_actions);
2709
2710             (*n_ops)++;
2711         } else {
2712             ofpbuf_uninit(&odp_actions);
2713         }
2714     }
2715 }
2716
2717 /* Handles 'miss', which matches 'facet'.  May add any required datapath
2718  * operations to 'ops', incrementing '*n_ops' for each new op. */
2719 static void
2720 handle_flow_miss_with_facet(struct flow_miss *miss, struct facet *facet,
2721                             struct flow_miss_op *ops, size_t *n_ops)
2722 {
2723     struct subfacet *subfacet;
2724     struct ofpbuf *packet;
2725
2726     subfacet = subfacet_create(facet,
2727                                miss->key_fitness, miss->key, miss->key_len,
2728                                miss->initial_tci);
2729
2730     LIST_FOR_EACH (packet, list_node, &miss->packets) {
2731         struct flow_miss_op *op = &ops[*n_ops];
2732         struct dpif_flow_stats stats;
2733         struct ofpbuf odp_actions;
2734
2735         handle_flow_miss_common(facet->rule, packet, &miss->flow);
2736
2737         ofpbuf_use_stub(&odp_actions, op->stub, sizeof op->stub);
2738         if (!facet->may_install || !subfacet->actions) {
2739             subfacet_make_actions(subfacet, packet, &odp_actions);
2740         }
2741
2742         dpif_flow_stats_extract(&facet->flow, packet, &stats);
2743         subfacet_update_stats(subfacet, &stats);
2744
2745         if (subfacet->actions_len) {
2746             struct dpif_execute *execute = &op->dpif_op.u.execute;
2747
2748             init_flow_miss_execute_op(miss, packet, op);
2749             op->subfacet = subfacet;
2750             if (facet->may_install) {
2751                 execute->actions = subfacet->actions;
2752                 execute->actions_len = subfacet->actions_len;
2753                 ofpbuf_uninit(&odp_actions);
2754             } else {
2755                 execute->actions = odp_actions.data;
2756                 execute->actions_len = odp_actions.size;
2757                 op->garbage = ofpbuf_get_uninit_pointer(&odp_actions);
2758             }
2759
2760             (*n_ops)++;
2761         } else {
2762             ofpbuf_uninit(&odp_actions);
2763         }
2764     }
2765
2766     if (facet->may_install && subfacet->key_fitness != ODP_FIT_TOO_LITTLE) {
2767         struct flow_miss_op *op = &ops[(*n_ops)++];
2768         struct dpif_flow_put *put = &op->dpif_op.u.flow_put;
2769
2770         op->subfacet = subfacet;
2771         op->garbage = NULL;
2772         op->dpif_op.type = DPIF_OP_FLOW_PUT;
2773         put->flags = DPIF_FP_CREATE | DPIF_FP_MODIFY;
2774         put->key = miss->key;
2775         put->key_len = miss->key_len;
2776         put->actions = subfacet->actions;
2777         put->actions_len = subfacet->actions_len;
2778         put->stats = NULL;
2779     }
2780 }
2781
2782 /* Handles flow miss 'miss' on 'ofproto'.  The flow does not match any flow in
2783  * the OpenFlow flow table. */
2784 static void
2785 handle_flow_miss_no_rule(struct ofproto_dpif *ofproto, struct flow_miss *miss)
2786 {
2787     uint16_t in_port = miss->flow.in_port;
2788     struct ofport_dpif *port = get_ofp_port(ofproto, in_port);
2789
2790     if (!port) {
2791         VLOG_WARN_RL(&rl, "packet-in on unknown port %"PRIu16, in_port);
2792     }
2793
2794     if (port && port->up.pp.config & OFPUTIL_PC_NO_PACKET_IN) {
2795         /* XXX install 'drop' flow entry */
2796         COVERAGE_INC(ofproto_dpif_no_packet_in);
2797     } else {
2798         const struct ofpbuf *packet;
2799
2800         LIST_FOR_EACH (packet, list_node, &miss->packets) {
2801             send_packet_in_miss(ofproto, packet, &miss->flow);
2802         }
2803     }
2804 }
2805
2806 /* Handles flow miss 'miss' on 'ofproto'.  May add any required datapath
2807  * operations to 'ops', incrementing '*n_ops' for each new op. */
2808 static void
2809 handle_flow_miss(struct ofproto_dpif *ofproto, struct flow_miss *miss,
2810                  struct flow_miss_op *ops, size_t *n_ops)
2811 {
2812     struct facet *facet;
2813     uint32_t hash;
2814
2815     /* The caller must ensure that miss->hmap_node.hash contains
2816      * flow_hash(miss->flow, 0). */
2817     hash = miss->hmap_node.hash;
2818
2819     facet = facet_lookup_valid(ofproto, &miss->flow, hash);
2820     if (!facet) {
2821         struct rule_dpif *rule = rule_dpif_lookup(ofproto, &miss->flow, 0);
2822         if (!rule) {
2823             handle_flow_miss_no_rule(ofproto, miss);
2824             return;
2825         } else if (!flow_miss_should_make_facet(ofproto, miss, hash)) {
2826             handle_flow_miss_without_facet(miss, rule, ops, n_ops);
2827             return;
2828         }
2829
2830         facet = facet_create(rule, &miss->flow, hash);
2831     }
2832     handle_flow_miss_with_facet(miss, facet, ops, n_ops);
2833 }
2834
2835 /* Like odp_flow_key_to_flow(), this function converts the 'key_len' bytes of
2836  * OVS_KEY_ATTR_* attributes in 'key' to a flow structure in 'flow' and returns
2837  * an ODP_FIT_* value that indicates how well 'key' fits our expectations for
2838  * what a flow key should contain.
2839  *
2840  * This function also includes some logic to help make VLAN splinters
2841  * transparent to the rest of the upcall processing logic.  In particular, if
2842  * the extracted in_port is a VLAN splinter port, it replaces flow->in_port by
2843  * the "real" port, sets flow->vlan_tci correctly for the VLAN of the VLAN
2844  * splinter port, and pushes a VLAN header onto 'packet' (if it is nonnull).
2845  *
2846  * Sets '*initial_tci' to the VLAN TCI with which the packet was really
2847  * received, that is, the actual VLAN TCI extracted by odp_flow_key_to_flow().
2848  * (This differs from the value returned in flow->vlan_tci only for packets
2849  * received on VLAN splinters.)
2850  */
2851 static enum odp_key_fitness
2852 ofproto_dpif_extract_flow_key(const struct ofproto_dpif *ofproto,
2853                               const struct nlattr *key, size_t key_len,
2854                               struct flow *flow, ovs_be16 *initial_tci,
2855                               struct ofpbuf *packet)
2856 {
2857     enum odp_key_fitness fitness;
2858     uint16_t realdev;
2859     int vid;
2860
2861     fitness = odp_flow_key_to_flow(key, key_len, flow);
2862     if (fitness == ODP_FIT_ERROR) {
2863         return fitness;
2864     }
2865     *initial_tci = flow->vlan_tci;
2866
2867     realdev = vsp_vlandev_to_realdev(ofproto, flow->in_port, &vid);
2868     if (realdev) {
2869         /* Cause the flow to be processed as if it came in on the real device
2870          * with the VLAN device's VLAN ID. */
2871         flow->in_port = realdev;
2872         flow->vlan_tci = htons((vid & VLAN_VID_MASK) | VLAN_CFI);
2873         if (packet) {
2874             /* Make the packet resemble the flow, so that it gets sent to an
2875              * OpenFlow controller properly, so that it looks correct for
2876              * sFlow, and so that flow_extract() will get the correct vlan_tci
2877              * if it is called on 'packet'.
2878              *
2879              * The allocated space inside 'packet' probably also contains
2880              * 'key', that is, both 'packet' and 'key' are probably part of a
2881              * struct dpif_upcall (see the large comment on that structure
2882              * definition), so pushing data on 'packet' is in general not a
2883              * good idea since it could overwrite 'key' or free it as a side
2884              * effect.  However, it's OK in this special case because we know
2885              * that 'packet' is inside a Netlink attribute: pushing 4 bytes
2886              * will just overwrite the 4-byte "struct nlattr", which is fine
2887              * since we don't need that header anymore. */
2888             eth_push_vlan(packet, flow->vlan_tci);
2889         }
2890
2891         /* Let the caller know that we can't reproduce 'key' from 'flow'. */
2892         if (fitness == ODP_FIT_PERFECT) {
2893             fitness = ODP_FIT_TOO_MUCH;
2894         }
2895     }
2896
2897     return fitness;
2898 }
2899
2900 static void
2901 handle_miss_upcalls(struct ofproto_dpif *ofproto, struct dpif_upcall *upcalls,
2902                     size_t n_upcalls)
2903 {
2904     struct dpif_upcall *upcall;
2905     struct flow_miss *miss;
2906     struct flow_miss misses[FLOW_MISS_MAX_BATCH];
2907     struct flow_miss_op flow_miss_ops[FLOW_MISS_MAX_BATCH * 2];
2908     struct dpif_op *dpif_ops[FLOW_MISS_MAX_BATCH * 2];
2909     struct hmap todo;
2910     int n_misses;
2911     size_t n_ops;
2912     size_t i;
2913
2914     if (!n_upcalls) {
2915         return;
2916     }
2917
2918     /* Construct the to-do list.
2919      *
2920      * This just amounts to extracting the flow from each packet and sticking
2921      * the packets that have the same flow in the same "flow_miss" structure so
2922      * that we can process them together. */
2923     hmap_init(&todo);
2924     n_misses = 0;
2925     for (upcall = upcalls; upcall < &upcalls[n_upcalls]; upcall++) {
2926         struct flow_miss *miss = &misses[n_misses];
2927         struct flow_miss *existing_miss;
2928         uint32_t hash;
2929
2930         /* Obtain metadata and check userspace/kernel agreement on flow match,
2931          * then set 'flow''s header pointers. */
2932         miss->key_fitness = ofproto_dpif_extract_flow_key(
2933             ofproto, upcall->key, upcall->key_len,
2934             &miss->flow, &miss->initial_tci, upcall->packet);
2935         if (miss->key_fitness == ODP_FIT_ERROR) {
2936             continue;
2937         }
2938         flow_extract(upcall->packet, miss->flow.skb_priority,
2939                      miss->flow.tun_id, miss->flow.in_port, &miss->flow);
2940
2941         /* Handle 802.1ag, LACP, and STP specially. */
2942         if (process_special(ofproto, &miss->flow, upcall->packet)) {
2943             ofproto_update_local_port_stats(&ofproto->up,
2944                                             0, upcall->packet->size);
2945             ofproto->n_matches++;
2946             continue;
2947         }
2948
2949         /* Add other packets to a to-do list. */
2950         hash = flow_hash(&miss->flow, 0);
2951         existing_miss = flow_miss_find(&todo, &miss->flow, hash);
2952         if (!existing_miss) {
2953             hmap_insert(&todo, &miss->hmap_node, hash);
2954             miss->key = upcall->key;
2955             miss->key_len = upcall->key_len;
2956             list_init(&miss->packets);
2957
2958             n_misses++;
2959         } else {
2960             miss = existing_miss;
2961         }
2962         list_push_back(&miss->packets, &upcall->packet->list_node);
2963     }
2964
2965     /* Process each element in the to-do list, constructing the set of
2966      * operations to batch. */
2967     n_ops = 0;
2968     HMAP_FOR_EACH (miss, hmap_node, &todo) {
2969         handle_flow_miss(ofproto, miss, flow_miss_ops, &n_ops);
2970     }
2971     assert(n_ops <= ARRAY_SIZE(flow_miss_ops));
2972
2973     /* Execute batch. */
2974     for (i = 0; i < n_ops; i++) {
2975         dpif_ops[i] = &flow_miss_ops[i].dpif_op;
2976     }
2977     dpif_operate(ofproto->dpif, dpif_ops, n_ops);
2978
2979     /* Free memory and update facets. */
2980     for (i = 0; i < n_ops; i++) {
2981         struct flow_miss_op *op = &flow_miss_ops[i];
2982
2983         switch (op->dpif_op.type) {
2984         case DPIF_OP_EXECUTE:
2985             break;
2986
2987         case DPIF_OP_FLOW_PUT:
2988             if (!op->dpif_op.error) {
2989                 op->subfacet->installed = true;
2990             }
2991             break;
2992
2993         case DPIF_OP_FLOW_DEL:
2994             NOT_REACHED();
2995         }
2996
2997         free(op->garbage);
2998     }
2999     hmap_destroy(&todo);
3000 }
3001
3002 static void
3003 handle_userspace_upcall(struct ofproto_dpif *ofproto,
3004                         struct dpif_upcall *upcall)
3005 {
3006     struct user_action_cookie cookie;
3007     enum odp_key_fitness fitness;
3008     ovs_be16 initial_tci;
3009     struct flow flow;
3010
3011     memcpy(&cookie, &upcall->userdata, sizeof(cookie));
3012
3013     fitness = ofproto_dpif_extract_flow_key(ofproto, upcall->key,
3014                                             upcall->key_len, &flow,
3015                                             &initial_tci, upcall->packet);
3016     if (fitness == ODP_FIT_ERROR) {
3017         return;
3018     }
3019
3020     if (cookie.type == USER_ACTION_COOKIE_SFLOW) {
3021         if (ofproto->sflow) {
3022             dpif_sflow_received(ofproto->sflow, upcall->packet, &flow,
3023                                 &cookie);
3024         }
3025     } else {
3026         VLOG_WARN_RL(&rl, "invalid user cookie : 0x%"PRIx64, upcall->userdata);
3027     }
3028 }
3029
3030 static int
3031 handle_upcalls(struct ofproto_dpif *ofproto, unsigned int max_batch)
3032 {
3033     struct dpif_upcall misses[FLOW_MISS_MAX_BATCH];
3034     struct ofpbuf miss_bufs[FLOW_MISS_MAX_BATCH];
3035     uint64_t miss_buf_stubs[FLOW_MISS_MAX_BATCH][4096 / 8];
3036     int n_processed;
3037     int n_misses;
3038     int i;
3039
3040     assert(max_batch <= FLOW_MISS_MAX_BATCH);
3041
3042     n_processed = 0;
3043     n_misses = 0;
3044     for (n_processed = 0; n_processed < max_batch; n_processed++) {
3045         struct dpif_upcall *upcall = &misses[n_misses];
3046         struct ofpbuf *buf = &miss_bufs[n_misses];
3047         int error;
3048
3049         ofpbuf_use_stub(buf, miss_buf_stubs[n_misses],
3050                         sizeof miss_buf_stubs[n_misses]);
3051         error = dpif_recv(ofproto->dpif, upcall, buf);
3052         if (error) {
3053             ofpbuf_uninit(buf);
3054             break;
3055         }
3056
3057         switch (upcall->type) {
3058         case DPIF_UC_ACTION:
3059             handle_userspace_upcall(ofproto, upcall);
3060             ofpbuf_uninit(buf);
3061             break;
3062
3063         case DPIF_UC_MISS:
3064             /* Handle it later. */
3065             n_misses++;
3066             break;
3067
3068         case DPIF_N_UC_TYPES:
3069         default:
3070             VLOG_WARN_RL(&rl, "upcall has unexpected type %"PRIu32,
3071                          upcall->type);
3072             break;
3073         }
3074     }
3075
3076     handle_miss_upcalls(ofproto, misses, n_misses);
3077     for (i = 0; i < n_misses; i++) {
3078         ofpbuf_uninit(&miss_bufs[i]);
3079     }
3080
3081     return n_processed;
3082 }
3083 \f
3084 /* Flow expiration. */
3085
3086 static int subfacet_max_idle(const struct ofproto_dpif *);
3087 static void update_stats(struct ofproto_dpif *);
3088 static void rule_expire(struct rule_dpif *);
3089 static void expire_subfacets(struct ofproto_dpif *, int dp_max_idle);
3090
3091 /* This function is called periodically by run().  Its job is to collect
3092  * updates for the flows that have been installed into the datapath, most
3093  * importantly when they last were used, and then use that information to
3094  * expire flows that have not been used recently.
3095  *
3096  * Returns the number of milliseconds after which it should be called again. */
3097 static int
3098 expire(struct ofproto_dpif *ofproto)
3099 {
3100     struct rule_dpif *rule, *next_rule;
3101     struct oftable *table;
3102     int dp_max_idle;
3103
3104     /* Update stats for each flow in the datapath. */
3105     update_stats(ofproto);
3106
3107     /* Expire subfacets that have been idle too long. */
3108     dp_max_idle = subfacet_max_idle(ofproto);
3109     expire_subfacets(ofproto, dp_max_idle);
3110
3111     /* Expire OpenFlow flows whose idle_timeout or hard_timeout has passed. */
3112     OFPROTO_FOR_EACH_TABLE (table, &ofproto->up) {
3113         struct cls_cursor cursor;
3114
3115         cls_cursor_init(&cursor, &table->cls, NULL);
3116         CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, up.cr, &cursor) {
3117             rule_expire(rule);
3118         }
3119     }
3120
3121     /* All outstanding data in existing flows has been accounted, so it's a
3122      * good time to do bond rebalancing. */
3123     if (ofproto->has_bonded_bundles) {
3124         struct ofbundle *bundle;
3125
3126         HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
3127             if (bundle->bond) {
3128                 bond_rebalance(bundle->bond, &ofproto->revalidate_set);
3129             }
3130         }
3131     }
3132
3133     return MIN(dp_max_idle, 1000);
3134 }
3135
3136 /* Update 'packet_count', 'byte_count', and 'used' members of installed facets.
3137  *
3138  * This function also pushes statistics updates to rules which each facet
3139  * resubmits into.  Generally these statistics will be accurate.  However, if a
3140  * facet changes the rule it resubmits into at some time in between
3141  * update_stats() runs, it is possible that statistics accrued to the
3142  * old rule will be incorrectly attributed to the new rule.  This could be
3143  * avoided by calling update_stats() whenever rules are created or
3144  * deleted.  However, the performance impact of making so many calls to the
3145  * datapath do not justify the benefit of having perfectly accurate statistics.
3146  */
3147 static void
3148 update_stats(struct ofproto_dpif *p)
3149 {
3150     const struct dpif_flow_stats *stats;
3151     struct dpif_flow_dump dump;
3152     const struct nlattr *key;
3153     size_t key_len;
3154
3155     dpif_flow_dump_start(&dump, p->dpif);
3156     while (dpif_flow_dump_next(&dump, &key, &key_len, NULL, NULL, &stats)) {
3157         struct subfacet *subfacet;
3158
3159         subfacet = subfacet_find(p, key, key_len);
3160         if (subfacet && subfacet->installed) {
3161             struct facet *facet = subfacet->facet;
3162
3163             if (stats->n_packets >= subfacet->dp_packet_count) {
3164                 uint64_t extra = stats->n_packets - subfacet->dp_packet_count;
3165                 facet->packet_count += extra;
3166             } else {
3167                 VLOG_WARN_RL(&rl, "unexpected packet count from the datapath");
3168             }
3169
3170             if (stats->n_bytes >= subfacet->dp_byte_count) {
3171                 facet->byte_count += stats->n_bytes - subfacet->dp_byte_count;
3172             } else {
3173                 VLOG_WARN_RL(&rl, "unexpected byte count from datapath");
3174             }
3175
3176             subfacet->dp_packet_count = stats->n_packets;
3177             subfacet->dp_byte_count = stats->n_bytes;
3178
3179             facet->tcp_flags |= stats->tcp_flags;
3180
3181             subfacet_update_time(subfacet, stats->used);
3182             if (facet->accounted_bytes < facet->byte_count) {
3183                 facet_learn(facet);
3184                 facet_account(facet);
3185                 facet->accounted_bytes = facet->byte_count;
3186             }
3187             facet_push_stats(facet);
3188         } else {
3189             if (!VLOG_DROP_WARN(&rl)) {
3190                 struct ds s;
3191
3192                 ds_init(&s);
3193                 odp_flow_key_format(key, key_len, &s);
3194                 VLOG_WARN("unexpected flow from datapath %s", ds_cstr(&s));
3195                 ds_destroy(&s);
3196             }
3197
3198             COVERAGE_INC(facet_unexpected);
3199             /* There's a flow in the datapath that we know nothing about, or a
3200              * flow that shouldn't be installed but was anyway.  Delete it. */
3201             dpif_flow_del(p->dpif, key, key_len, NULL);
3202         }
3203     }
3204     dpif_flow_dump_done(&dump);
3205 }
3206
3207 /* Calculates and returns the number of milliseconds of idle time after which
3208  * subfacets should expire from the datapath.  When a subfacet expires, we fold
3209  * its statistics into its facet, and when a facet's last subfacet expires, we
3210  * fold its statistic into its rule. */
3211 static int
3212 subfacet_max_idle(const struct ofproto_dpif *ofproto)
3213 {
3214     /*
3215      * Idle time histogram.
3216      *
3217      * Most of the time a switch has a relatively small number of subfacets.
3218      * When this is the case we might as well keep statistics for all of them
3219      * in userspace and to cache them in the kernel datapath for performance as
3220      * well.
3221      *
3222      * As the number of subfacets increases, the memory required to maintain
3223      * statistics about them in userspace and in the kernel becomes
3224      * significant.  However, with a large number of subfacets it is likely
3225      * that only a few of them are "heavy hitters" that consume a large amount
3226      * of bandwidth.  At this point, only heavy hitters are worth caching in
3227      * the kernel and maintaining in userspaces; other subfacets we can
3228      * discard.
3229      *
3230      * The technique used to compute the idle time is to build a histogram with
3231      * N_BUCKETS buckets whose width is BUCKET_WIDTH msecs each.  Each subfacet
3232      * that is installed in the kernel gets dropped in the appropriate bucket.
3233      * After the histogram has been built, we compute the cutoff so that only
3234      * the most-recently-used 1% of subfacets (but at least
3235      * ofproto->up.flow_eviction_threshold flows) are kept cached.  At least
3236      * the most-recently-used bucket of subfacets is kept, so actually an
3237      * arbitrary number of subfacets can be kept in any given expiration run
3238      * (though the next run will delete most of those unless they receive
3239      * additional data).
3240      *
3241      * This requires a second pass through the subfacets, in addition to the
3242      * pass made by update_stats(), because the former function never looks at
3243      * uninstallable subfacets.
3244      */
3245     enum { BUCKET_WIDTH = ROUND_UP(100, TIME_UPDATE_INTERVAL) };
3246     enum { N_BUCKETS = 5000 / BUCKET_WIDTH };
3247     int buckets[N_BUCKETS] = { 0 };
3248     int total, subtotal, bucket;
3249     struct subfacet *subfacet;
3250     long long int now;
3251     int i;
3252
3253     total = hmap_count(&ofproto->subfacets);
3254     if (total <= ofproto->up.flow_eviction_threshold) {
3255         return N_BUCKETS * BUCKET_WIDTH;
3256     }
3257
3258     /* Build histogram. */
3259     now = time_msec();
3260     HMAP_FOR_EACH (subfacet, hmap_node, &ofproto->subfacets) {
3261         long long int idle = now - subfacet->used;
3262         int bucket = (idle <= 0 ? 0
3263                       : idle >= BUCKET_WIDTH * N_BUCKETS ? N_BUCKETS - 1
3264                       : (unsigned int) idle / BUCKET_WIDTH);
3265         buckets[bucket]++;
3266     }
3267
3268     /* Find the first bucket whose flows should be expired. */
3269     subtotal = bucket = 0;
3270     do {
3271         subtotal += buckets[bucket++];
3272     } while (bucket < N_BUCKETS &&
3273              subtotal < MAX(ofproto->up.flow_eviction_threshold, total / 100));
3274
3275     if (VLOG_IS_DBG_ENABLED()) {
3276         struct ds s;
3277
3278         ds_init(&s);
3279         ds_put_cstr(&s, "keep");
3280         for (i = 0; i < N_BUCKETS; i++) {
3281             if (i == bucket) {
3282                 ds_put_cstr(&s, ", drop");
3283             }
3284             if (buckets[i]) {
3285                 ds_put_format(&s, " %d:%d", i * BUCKET_WIDTH, buckets[i]);
3286             }
3287         }
3288         VLOG_INFO("%s: %s (msec:count)", ofproto->up.name, ds_cstr(&s));
3289         ds_destroy(&s);
3290     }
3291
3292     return bucket * BUCKET_WIDTH;
3293 }
3294
3295 enum { EXPIRE_MAX_BATCH = 50 };
3296
3297 static void
3298 expire_batch(struct ofproto_dpif *ofproto, struct subfacet **subfacets, int n)
3299 {
3300     struct odputil_keybuf keybufs[EXPIRE_MAX_BATCH];
3301     struct dpif_op ops[EXPIRE_MAX_BATCH];
3302     struct dpif_op *opsp[EXPIRE_MAX_BATCH];
3303     struct ofpbuf keys[EXPIRE_MAX_BATCH];
3304     struct dpif_flow_stats stats[EXPIRE_MAX_BATCH];
3305     int i;
3306
3307     for (i = 0; i < n; i++) {
3308         ops[i].type = DPIF_OP_FLOW_DEL;
3309         subfacet_get_key(subfacets[i], &keybufs[i], &keys[i]);
3310         ops[i].u.flow_del.key = keys[i].data;
3311         ops[i].u.flow_del.key_len = keys[i].size;
3312         ops[i].u.flow_del.stats = &stats[i];
3313         opsp[i] = &ops[i];
3314     }
3315
3316     dpif_operate(ofproto->dpif, opsp, n);
3317     for (i = 0; i < n; i++) {
3318         subfacet_reset_dp_stats(subfacets[i], &stats[i]);
3319         subfacets[i]->installed = false;
3320         subfacet_destroy(subfacets[i]);
3321     }
3322 }
3323
3324 static void
3325 expire_subfacets(struct ofproto_dpif *ofproto, int dp_max_idle)
3326 {
3327     long long int cutoff = time_msec() - dp_max_idle;
3328
3329     struct subfacet *subfacet, *next_subfacet;
3330     struct subfacet *batch[EXPIRE_MAX_BATCH];
3331     int n_batch;
3332
3333     n_batch = 0;
3334     HMAP_FOR_EACH_SAFE (subfacet, next_subfacet, hmap_node,
3335                         &ofproto->subfacets) {
3336         if (subfacet->used < cutoff) {
3337             if (subfacet->installed) {
3338                 batch[n_batch++] = subfacet;
3339                 if (n_batch >= EXPIRE_MAX_BATCH) {
3340                     expire_batch(ofproto, batch, n_batch);
3341                     n_batch = 0;
3342                 }
3343             } else {
3344                 subfacet_destroy(subfacet);
3345             }
3346         }
3347     }
3348
3349     if (n_batch > 0) {
3350         expire_batch(ofproto, batch, n_batch);
3351     }
3352 }
3353
3354 /* If 'rule' is an OpenFlow rule, that has expired according to OpenFlow rules,
3355  * then delete it entirely. */
3356 static void
3357 rule_expire(struct rule_dpif *rule)
3358 {
3359     struct facet *facet, *next_facet;
3360     long long int now;
3361     uint8_t reason;
3362
3363     /* Has 'rule' expired? */
3364     now = time_msec();
3365     if (rule->up.hard_timeout
3366         && now > rule->up.modified + rule->up.hard_timeout * 1000) {
3367         reason = OFPRR_HARD_TIMEOUT;
3368     } else if (rule->up.idle_timeout
3369                && now > rule->up.used + rule->up.idle_timeout * 1000) {
3370         reason = OFPRR_IDLE_TIMEOUT;
3371     } else {
3372         return;
3373     }
3374
3375     COVERAGE_INC(ofproto_dpif_expired);
3376
3377     /* Update stats.  (This is a no-op if the rule expired due to an idle
3378      * timeout, because that only happens when the rule has no facets left.) */
3379     LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
3380         facet_remove(facet);
3381     }
3382
3383     /* Get rid of the rule. */
3384     ofproto_rule_expire(&rule->up, reason);
3385 }
3386 \f
3387 /* Facets. */
3388
3389 /* Creates and returns a new facet owned by 'rule', given a 'flow'.
3390  *
3391  * The caller must already have determined that no facet with an identical
3392  * 'flow' exists in 'ofproto' and that 'flow' is the best match for 'rule' in
3393  * the ofproto's classifier table.
3394  *
3395  * 'hash' must be the return value of flow_hash(flow, 0).
3396  *
3397  * The facet will initially have no subfacets.  The caller should create (at
3398  * least) one subfacet with subfacet_create(). */
3399 static struct facet *
3400 facet_create(struct rule_dpif *rule, const struct flow *flow, uint32_t hash)
3401 {
3402     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
3403     struct facet *facet;
3404
3405     facet = xzalloc(sizeof *facet);
3406     facet->used = time_msec();
3407     hmap_insert(&ofproto->facets, &facet->hmap_node, hash);
3408     list_push_back(&rule->facets, &facet->list_node);
3409     facet->rule = rule;
3410     facet->flow = *flow;
3411     list_init(&facet->subfacets);
3412     netflow_flow_init(&facet->nf_flow);
3413     netflow_flow_update_time(ofproto->netflow, &facet->nf_flow, facet->used);
3414
3415     return facet;
3416 }
3417
3418 static void
3419 facet_free(struct facet *facet)
3420 {
3421     free(facet);
3422 }
3423
3424 /* Executes, within 'ofproto', the 'n_actions' actions in 'actions' on
3425  * 'packet', which arrived on 'in_port'.
3426  *
3427  * Takes ownership of 'packet'. */
3428 static bool
3429 execute_odp_actions(struct ofproto_dpif *ofproto, const struct flow *flow,
3430                     const struct nlattr *odp_actions, size_t actions_len,
3431                     struct ofpbuf *packet)
3432 {
3433     struct odputil_keybuf keybuf;
3434     struct ofpbuf key;
3435     int error;
3436
3437     ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
3438     odp_flow_key_from_flow(&key, flow);
3439
3440     error = dpif_execute(ofproto->dpif, key.data, key.size,
3441                          odp_actions, actions_len, packet);
3442
3443     ofpbuf_delete(packet);
3444     return !error;
3445 }
3446
3447 /* Remove 'facet' from 'ofproto' and free up the associated memory:
3448  *
3449  *   - If 'facet' was installed in the datapath, uninstalls it and updates its
3450  *     rule's statistics, via subfacet_uninstall().
3451  *
3452  *   - Removes 'facet' from its rule and from ofproto->facets.
3453  */
3454 static void
3455 facet_remove(struct facet *facet)
3456 {
3457     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3458     struct subfacet *subfacet, *next_subfacet;
3459
3460     assert(!list_is_empty(&facet->subfacets));
3461
3462     /* First uninstall all of the subfacets to get final statistics. */
3463     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
3464         subfacet_uninstall(subfacet);
3465     }
3466
3467     /* Flush the final stats to the rule.
3468      *
3469      * This might require us to have at least one subfacet around so that we
3470      * can use its actions for accounting in facet_account(), which is why we
3471      * have uninstalled but not yet destroyed the subfacets. */
3472     facet_flush_stats(facet);
3473
3474     /* Now we're really all done so destroy everything. */
3475     LIST_FOR_EACH_SAFE (subfacet, next_subfacet, list_node,
3476                         &facet->subfacets) {
3477         subfacet_destroy__(subfacet);
3478     }
3479     hmap_remove(&ofproto->facets, &facet->hmap_node);
3480     list_remove(&facet->list_node);
3481     facet_free(facet);
3482 }
3483
3484 /* Feed information from 'facet' back into the learning table to keep it in
3485  * sync with what is actually flowing through the datapath. */
3486 static void
3487 facet_learn(struct facet *facet)
3488 {
3489     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3490     struct action_xlate_ctx ctx;
3491
3492     if (!facet->has_learn
3493         && !facet->has_normal
3494         && (!facet->has_fin_timeout
3495             || !(facet->tcp_flags & (TCP_FIN | TCP_RST)))) {
3496         return;
3497     }
3498
3499     action_xlate_ctx_init(&ctx, ofproto, &facet->flow,
3500                           facet->flow.vlan_tci,
3501                           facet->rule, facet->tcp_flags, NULL);
3502     ctx.may_learn = true;
3503     xlate_actions_for_side_effects(&ctx, facet->rule->up.actions,
3504                                    facet->rule->up.n_actions);
3505 }
3506
3507 static void
3508 facet_account(struct facet *facet)
3509 {
3510     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3511     struct subfacet *subfacet;
3512     const struct nlattr *a;
3513     unsigned int left;
3514     ovs_be16 vlan_tci;
3515     uint64_t n_bytes;
3516
3517     if (!facet->has_normal || !ofproto->has_bonded_bundles) {
3518         return;
3519     }
3520     n_bytes = facet->byte_count - facet->accounted_bytes;
3521
3522     /* This loop feeds byte counters to bond_account() for rebalancing to use
3523      * as a basis.  We also need to track the actual VLAN on which the packet
3524      * is going to be sent to ensure that it matches the one passed to
3525      * bond_choose_output_slave().  (Otherwise, we will account to the wrong
3526      * hash bucket.)
3527      *
3528      * We use the actions from an arbitrary subfacet because they should all
3529      * be equally valid for our purpose. */
3530     subfacet = CONTAINER_OF(list_front(&facet->subfacets),
3531                             struct subfacet, list_node);
3532     vlan_tci = facet->flow.vlan_tci;
3533     NL_ATTR_FOR_EACH_UNSAFE (a, left,
3534                              subfacet->actions, subfacet->actions_len) {
3535         const struct ovs_action_push_vlan *vlan;
3536         struct ofport_dpif *port;
3537
3538         switch (nl_attr_type(a)) {
3539         case OVS_ACTION_ATTR_OUTPUT:
3540             port = get_odp_port(ofproto, nl_attr_get_u32(a));
3541             if (port && port->bundle && port->bundle->bond) {
3542                 bond_account(port->bundle->bond, &facet->flow,
3543                              vlan_tci_to_vid(vlan_tci), n_bytes);
3544             }
3545             break;
3546
3547         case OVS_ACTION_ATTR_POP_VLAN:
3548             vlan_tci = htons(0);
3549             break;
3550
3551         case OVS_ACTION_ATTR_PUSH_VLAN:
3552             vlan = nl_attr_get(a);
3553             vlan_tci = vlan->vlan_tci;
3554             break;
3555         }
3556     }
3557 }
3558
3559 /* Returns true if the only action for 'facet' is to send to the controller.
3560  * (We don't report NetFlow expiration messages for such facets because they
3561  * are just part of the control logic for the network, not real traffic). */
3562 static bool
3563 facet_is_controller_flow(struct facet *facet)
3564 {
3565     return (facet
3566             && facet->rule->up.n_actions == 1
3567             && action_outputs_to_port(&facet->rule->up.actions[0],
3568                                       htons(OFPP_CONTROLLER)));
3569 }
3570
3571 /* Folds all of 'facet''s statistics into its rule.  Also updates the
3572  * accounting ofhook and emits a NetFlow expiration if appropriate.  All of
3573  * 'facet''s statistics in the datapath should have been zeroed and folded into
3574  * its packet and byte counts before this function is called. */
3575 static void
3576 facet_flush_stats(struct facet *facet)
3577 {
3578     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3579     struct subfacet *subfacet;
3580
3581     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
3582         assert(!subfacet->dp_byte_count);
3583         assert(!subfacet->dp_packet_count);
3584     }
3585
3586     facet_push_stats(facet);
3587     if (facet->accounted_bytes < facet->byte_count) {
3588         facet_account(facet);
3589         facet->accounted_bytes = facet->byte_count;
3590     }
3591
3592     if (ofproto->netflow && !facet_is_controller_flow(facet)) {
3593         struct ofexpired expired;
3594         expired.flow = facet->flow;
3595         expired.packet_count = facet->packet_count;
3596         expired.byte_count = facet->byte_count;
3597         expired.used = facet->used;
3598         netflow_expire(ofproto->netflow, &facet->nf_flow, &expired);
3599     }
3600
3601     facet->rule->packet_count += facet->packet_count;
3602     facet->rule->byte_count += facet->byte_count;
3603
3604     /* Reset counters to prevent double counting if 'facet' ever gets
3605      * reinstalled. */
3606     facet_reset_counters(facet);
3607
3608     netflow_flow_clear(&facet->nf_flow);
3609     facet->tcp_flags = 0;
3610 }
3611
3612 /* Searches 'ofproto''s table of facets for one exactly equal to 'flow'.
3613  * Returns it if found, otherwise a null pointer.
3614  *
3615  * 'hash' must be the return value of flow_hash(flow, 0).
3616  *
3617  * The returned facet might need revalidation; use facet_lookup_valid()
3618  * instead if that is important. */
3619 static struct facet *
3620 facet_find(struct ofproto_dpif *ofproto,
3621            const struct flow *flow, uint32_t hash)
3622 {
3623     struct facet *facet;
3624
3625     HMAP_FOR_EACH_WITH_HASH (facet, hmap_node, hash, &ofproto->facets) {
3626         if (flow_equal(flow, &facet->flow)) {
3627             return facet;
3628         }
3629     }
3630
3631     return NULL;
3632 }
3633
3634 /* Searches 'ofproto''s table of facets for one exactly equal to 'flow'.
3635  * Returns it if found, otherwise a null pointer.
3636  *
3637  * 'hash' must be the return value of flow_hash(flow, 0).
3638  *
3639  * The returned facet is guaranteed to be valid. */
3640 static struct facet *
3641 facet_lookup_valid(struct ofproto_dpif *ofproto, const struct flow *flow,
3642                    uint32_t hash)
3643 {
3644     struct facet *facet = facet_find(ofproto, flow, hash);
3645
3646     /* The facet we found might not be valid, since we could be in need of
3647      * revalidation.  If it is not valid, don't return it. */
3648     if (facet
3649         && (ofproto->need_revalidate
3650             || tag_set_intersects(&ofproto->revalidate_set, facet->tags))
3651         && !facet_revalidate(facet)) {
3652         COVERAGE_INC(facet_invalidated);
3653         return NULL;
3654     }
3655
3656     return facet;
3657 }
3658
3659 static bool
3660 facet_check_consistency(struct facet *facet)
3661 {
3662     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 15);
3663
3664     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3665
3666     uint64_t odp_actions_stub[1024 / 8];
3667     struct ofpbuf odp_actions;
3668
3669     struct rule_dpif *rule;
3670     struct subfacet *subfacet;
3671     bool may_log = false;
3672     bool ok;
3673
3674     /* Check the rule for consistency. */
3675     rule = rule_dpif_lookup(ofproto, &facet->flow, 0);
3676     if (!rule) {
3677         if (!VLOG_DROP_WARN(&rl)) {
3678             char *s = flow_to_string(&facet->flow);
3679             VLOG_WARN("%s: facet should not exist", s);
3680             free(s);
3681         }
3682         return false;
3683     } else if (rule != facet->rule) {
3684         may_log = !VLOG_DROP_WARN(&rl);
3685         ok = false;
3686         if (may_log) {
3687             struct ds s;
3688
3689             ds_init(&s);
3690             flow_format(&s, &facet->flow);
3691             ds_put_format(&s, ": facet associated with wrong rule (was "
3692                           "table=%"PRIu8",", facet->rule->up.table_id);
3693             cls_rule_format(&facet->rule->up.cr, &s);
3694             ds_put_format(&s, ") (should have been table=%"PRIu8",",
3695                           rule->up.table_id);
3696             cls_rule_format(&rule->up.cr, &s);
3697             ds_put_char(&s, ')');
3698
3699             VLOG_WARN("%s", ds_cstr(&s));
3700             ds_destroy(&s);
3701         }
3702     } else {
3703         ok = true;
3704     }
3705
3706     /* Check the datapath actions for consistency. */
3707     ofpbuf_use_stub(&odp_actions, odp_actions_stub, sizeof odp_actions_stub);
3708     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
3709         struct action_xlate_ctx ctx;
3710         bool actions_changed;
3711         bool should_install;
3712
3713         action_xlate_ctx_init(&ctx, ofproto, &facet->flow,
3714                               subfacet->initial_tci, rule, 0, NULL);
3715         xlate_actions(&ctx, rule->up.actions, rule->up.n_actions,
3716                       &odp_actions);
3717
3718         should_install = (ctx.may_set_up_flow
3719                           && subfacet->key_fitness != ODP_FIT_TOO_LITTLE);
3720         if (!should_install && !subfacet->installed) {
3721             /* The actions for uninstallable flows may vary from one packet to
3722              * the next, so don't compare the actions. */
3723             continue;
3724         }
3725
3726         actions_changed = (subfacet->actions_len != odp_actions.size
3727                            || memcmp(subfacet->actions, odp_actions.data,
3728                                      subfacet->actions_len));
3729         if (should_install != subfacet->installed || actions_changed) {
3730             if (ok) {
3731                 may_log = !VLOG_DROP_WARN(&rl);
3732                 ok = false;
3733             }
3734
3735             if (may_log) {
3736                 struct odputil_keybuf keybuf;
3737                 struct ofpbuf key;
3738                 struct ds s;
3739
3740                 ds_init(&s);
3741                 subfacet_get_key(subfacet, &keybuf, &key);
3742                 odp_flow_key_format(key.data, key.size, &s);
3743
3744                 ds_put_cstr(&s, ": inconsistency in subfacet");
3745                 if (should_install != subfacet->installed) {
3746                     enum odp_key_fitness fitness = subfacet->key_fitness;
3747
3748                     ds_put_format(&s, " (should%s have been installed)",
3749                                   should_install ? "" : " not");
3750                     ds_put_format(&s, " (may_set_up_flow=%s, fitness=%s)",
3751                                   ctx.may_set_up_flow ? "true" : "false",
3752                                   odp_key_fitness_to_string(fitness));
3753                 }
3754                 if (actions_changed) {
3755                     ds_put_cstr(&s, " (actions were: ");
3756                     format_odp_actions(&s, subfacet->actions,
3757                                        subfacet->actions_len);
3758                     ds_put_cstr(&s, ") (correct actions: ");
3759                     format_odp_actions(&s, odp_actions.data, odp_actions.size);
3760                     ds_put_char(&s, ')');
3761                 } else {
3762                     ds_put_cstr(&s, " (actions: ");
3763                     format_odp_actions(&s, subfacet->actions,
3764                                        subfacet->actions_len);
3765                     ds_put_char(&s, ')');
3766                 }
3767                 VLOG_WARN("%s", ds_cstr(&s));
3768                 ds_destroy(&s);
3769             }
3770         }
3771     }
3772     ofpbuf_uninit(&odp_actions);
3773
3774     return ok;
3775 }
3776
3777 /* Re-searches the classifier for 'facet':
3778  *
3779  *   - If the rule found is different from 'facet''s current rule, moves
3780  *     'facet' to the new rule and recompiles its actions.
3781  *
3782  *   - If the rule found is the same as 'facet''s current rule, leaves 'facet'
3783  *     where it is and recompiles its actions anyway.
3784  *
3785  *   - If there is none, destroys 'facet'.
3786  *
3787  * Returns true if 'facet' still exists, false if it has been destroyed. */
3788 static bool
3789 facet_revalidate(struct facet *facet)
3790 {
3791     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3792     struct actions {
3793         struct nlattr *odp_actions;
3794         size_t actions_len;
3795     };
3796     struct actions *new_actions;
3797
3798     struct action_xlate_ctx ctx;
3799     uint64_t odp_actions_stub[1024 / 8];
3800     struct ofpbuf odp_actions;
3801
3802     struct rule_dpif *new_rule;
3803     struct subfacet *subfacet;
3804     bool actions_changed;
3805     int i;
3806
3807     COVERAGE_INC(facet_revalidate);
3808
3809     /* Determine the new rule. */
3810     new_rule = rule_dpif_lookup(ofproto, &facet->flow, 0);
3811     if (!new_rule) {
3812         /* No new rule, so delete the facet. */
3813         facet_remove(facet);
3814         return false;
3815     }
3816
3817     /* Calculate new datapath actions.
3818      *
3819      * We do not modify any 'facet' state yet, because we might need to, e.g.,
3820      * emit a NetFlow expiration and, if so, we need to have the old state
3821      * around to properly compose it. */
3822
3823     /* If the datapath actions changed or the installability changed,
3824      * then we need to talk to the datapath. */
3825     i = 0;
3826     new_actions = NULL;
3827     memset(&ctx, 0, sizeof ctx);
3828     ofpbuf_use_stub(&odp_actions, odp_actions_stub, sizeof odp_actions_stub);
3829     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
3830         bool should_install;
3831
3832         action_xlate_ctx_init(&ctx, ofproto, &facet->flow,
3833                               subfacet->initial_tci, new_rule, 0, NULL);
3834         xlate_actions(&ctx, new_rule->up.actions, new_rule->up.n_actions,
3835                       &odp_actions);
3836         actions_changed = (subfacet->actions_len != odp_actions.size
3837                            || memcmp(subfacet->actions, odp_actions.data,
3838                                      subfacet->actions_len));
3839
3840         should_install = (ctx.may_set_up_flow
3841                           && subfacet->key_fitness != ODP_FIT_TOO_LITTLE);
3842         if (actions_changed || should_install != subfacet->installed) {
3843             if (should_install) {
3844                 struct dpif_flow_stats stats;
3845
3846                 subfacet_install(subfacet,
3847                                  odp_actions.data, odp_actions.size, &stats);
3848                 subfacet_update_stats(subfacet, &stats);
3849             } else {
3850                 subfacet_uninstall(subfacet);
3851             }
3852
3853             if (!new_actions) {
3854                 new_actions = xcalloc(list_size(&facet->subfacets),
3855                                       sizeof *new_actions);
3856             }
3857             new_actions[i].odp_actions = xmemdup(odp_actions.data,
3858                                                  odp_actions.size);
3859             new_actions[i].actions_len = odp_actions.size;
3860         }
3861
3862         i++;
3863     }
3864     ofpbuf_uninit(&odp_actions);
3865
3866     if (new_actions) {
3867         facet_flush_stats(facet);
3868     }
3869
3870     /* Update 'facet' now that we've taken care of all the old state. */
3871     facet->tags = ctx.tags;
3872     facet->nf_flow.output_iface = ctx.nf_output_iface;
3873     facet->may_install = ctx.may_set_up_flow;
3874     facet->has_learn = ctx.has_learn;
3875     facet->has_normal = ctx.has_normal;
3876     facet->has_fin_timeout = ctx.has_fin_timeout;
3877     facet->mirrors = ctx.mirrors;
3878     if (new_actions) {
3879         i = 0;
3880         LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
3881             if (new_actions[i].odp_actions) {
3882                 free(subfacet->actions);
3883                 subfacet->actions = new_actions[i].odp_actions;
3884                 subfacet->actions_len = new_actions[i].actions_len;
3885             }
3886             i++;
3887         }
3888         free(new_actions);
3889     }
3890     if (facet->rule != new_rule) {
3891         COVERAGE_INC(facet_changed_rule);
3892         list_remove(&facet->list_node);
3893         list_push_back(&new_rule->facets, &facet->list_node);
3894         facet->rule = new_rule;
3895         facet->used = new_rule->up.created;
3896         facet->prev_used = facet->used;
3897     }
3898
3899     return true;
3900 }
3901
3902 /* Updates 'facet''s used time.  Caller is responsible for calling
3903  * facet_push_stats() to update the flows which 'facet' resubmits into. */
3904 static void
3905 facet_update_time(struct facet *facet, long long int used)
3906 {
3907     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
3908     if (used > facet->used) {
3909         facet->used = used;
3910         ofproto_rule_update_used(&facet->rule->up, used);
3911         netflow_flow_update_time(ofproto->netflow, &facet->nf_flow, used);
3912     }
3913 }
3914
3915 static void
3916 facet_reset_counters(struct facet *facet)
3917 {
3918     facet->packet_count = 0;
3919     facet->byte_count = 0;
3920     facet->prev_packet_count = 0;
3921     facet->prev_byte_count = 0;
3922     facet->accounted_bytes = 0;
3923 }
3924
3925 static void
3926 facet_push_stats(struct facet *facet)
3927 {
3928     struct dpif_flow_stats stats;
3929
3930     assert(facet->packet_count >= facet->prev_packet_count);
3931     assert(facet->byte_count >= facet->prev_byte_count);
3932     assert(facet->used >= facet->prev_used);
3933
3934     stats.n_packets = facet->packet_count - facet->prev_packet_count;
3935     stats.n_bytes = facet->byte_count - facet->prev_byte_count;
3936     stats.used = facet->used;
3937     stats.tcp_flags = 0;
3938
3939     if (stats.n_packets || stats.n_bytes || facet->used > facet->prev_used) {
3940         facet->prev_packet_count = facet->packet_count;
3941         facet->prev_byte_count = facet->byte_count;
3942         facet->prev_used = facet->used;
3943
3944         flow_push_stats(facet->rule, &facet->flow, &stats);
3945
3946         update_mirror_stats(ofproto_dpif_cast(facet->rule->up.ofproto),
3947                             facet->mirrors, stats.n_packets, stats.n_bytes);
3948     }
3949 }
3950
3951 static void
3952 rule_credit_stats(struct rule_dpif *rule, const struct dpif_flow_stats *stats)
3953 {
3954     rule->packet_count += stats->n_packets;
3955     rule->byte_count += stats->n_bytes;
3956     ofproto_rule_update_used(&rule->up, stats->used);
3957 }
3958
3959 /* Pushes flow statistics to the rules which 'flow' resubmits into given
3960  * 'rule''s actions and mirrors. */
3961 static void
3962 flow_push_stats(struct rule_dpif *rule,
3963                 const struct flow *flow, const struct dpif_flow_stats *stats)
3964 {
3965     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
3966     struct action_xlate_ctx ctx;
3967
3968     ofproto_rule_update_used(&rule->up, stats->used);
3969
3970     action_xlate_ctx_init(&ctx, ofproto, flow, flow->vlan_tci, rule,
3971                           0, NULL);
3972     ctx.resubmit_stats = stats;
3973     xlate_actions_for_side_effects(&ctx, rule->up.actions, rule->up.n_actions);
3974 }
3975 \f
3976 /* Subfacets. */
3977
3978 static struct subfacet *
3979 subfacet_find__(struct ofproto_dpif *ofproto,
3980                 const struct nlattr *key, size_t key_len, uint32_t key_hash,
3981                 const struct flow *flow)
3982 {
3983     struct subfacet *subfacet;
3984
3985     HMAP_FOR_EACH_WITH_HASH (subfacet, hmap_node, key_hash,
3986                              &ofproto->subfacets) {
3987         if (subfacet->key
3988             ? (subfacet->key_len == key_len
3989                && !memcmp(key, subfacet->key, key_len))
3990             : flow_equal(flow, &subfacet->facet->flow)) {
3991             return subfacet;
3992         }
3993     }
3994
3995     return NULL;
3996 }
3997
3998 /* Searches 'facet' (within 'ofproto') for a subfacet with the specified
3999  * 'key_fitness', 'key', and 'key_len'.  Returns the existing subfacet if
4000  * there is one, otherwise creates and returns a new subfacet.
4001  *
4002  * If the returned subfacet is new, then subfacet->actions will be NULL, in
4003  * which case the caller must populate the actions with
4004  * subfacet_make_actions(). */
4005 static struct subfacet *
4006 subfacet_create(struct facet *facet, enum odp_key_fitness key_fitness,
4007                 const struct nlattr *key, size_t key_len, ovs_be16 initial_tci)
4008 {
4009     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4010     uint32_t key_hash = odp_flow_key_hash(key, key_len);
4011     struct subfacet *subfacet;
4012
4013     subfacet = subfacet_find__(ofproto, key, key_len, key_hash, &facet->flow);
4014     if (subfacet) {
4015         if (subfacet->facet == facet) {
4016             return subfacet;
4017         }
4018
4019         /* This shouldn't happen. */
4020         VLOG_ERR_RL(&rl, "subfacet with wrong facet");
4021         subfacet_destroy(subfacet);
4022     }
4023
4024     subfacet = (list_is_empty(&facet->subfacets)
4025                 ? &facet->one_subfacet
4026                 : xmalloc(sizeof *subfacet));
4027     hmap_insert(&ofproto->subfacets, &subfacet->hmap_node, key_hash);
4028     list_push_back(&facet->subfacets, &subfacet->list_node);
4029     subfacet->facet = facet;
4030     subfacet->key_fitness = key_fitness;
4031     if (key_fitness != ODP_FIT_PERFECT) {
4032         subfacet->key = xmemdup(key, key_len);
4033         subfacet->key_len = key_len;
4034     } else {
4035         subfacet->key = NULL;
4036         subfacet->key_len = 0;
4037     }
4038     subfacet->used = time_msec();
4039     subfacet->dp_packet_count = 0;
4040     subfacet->dp_byte_count = 0;
4041     subfacet->actions_len = 0;
4042     subfacet->actions = NULL;
4043     subfacet->installed = false;
4044     subfacet->initial_tci = initial_tci;
4045
4046     return subfacet;
4047 }
4048
4049 /* Searches 'ofproto' for a subfacet with the given 'key', 'key_len', and
4050  * 'flow'.  Returns the subfacet if one exists, otherwise NULL. */
4051 static struct subfacet *
4052 subfacet_find(struct ofproto_dpif *ofproto,
4053               const struct nlattr *key, size_t key_len)
4054 {
4055     uint32_t key_hash = odp_flow_key_hash(key, key_len);
4056     enum odp_key_fitness fitness;
4057     struct flow flow;
4058
4059     fitness = odp_flow_key_to_flow(key, key_len, &flow);
4060     if (fitness == ODP_FIT_ERROR) {
4061         return NULL;
4062     }
4063
4064     return subfacet_find__(ofproto, key, key_len, key_hash, &flow);
4065 }
4066
4067 /* Uninstalls 'subfacet' from the datapath, if it is installed, removes it from
4068  * its facet within 'ofproto', and frees it. */
4069 static void
4070 subfacet_destroy__(struct subfacet *subfacet)
4071 {
4072     struct facet *facet = subfacet->facet;
4073     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4074
4075     subfacet_uninstall(subfacet);
4076     hmap_remove(&ofproto->subfacets, &subfacet->hmap_node);
4077     list_remove(&subfacet->list_node);
4078     free(subfacet->key);
4079     free(subfacet->actions);
4080     if (subfacet != &facet->one_subfacet) {
4081         free(subfacet);
4082     }
4083 }
4084
4085 /* Destroys 'subfacet', as with subfacet_destroy__(), and then if this was the
4086  * last remaining subfacet in its facet destroys the facet too. */
4087 static void
4088 subfacet_destroy(struct subfacet *subfacet)
4089 {
4090     struct facet *facet = subfacet->facet;
4091
4092     if (list_is_singleton(&facet->subfacets)) {
4093         /* facet_remove() needs at least one subfacet (it will remove it). */
4094         facet_remove(facet);
4095     } else {
4096         subfacet_destroy__(subfacet);
4097     }
4098 }
4099
4100 /* Initializes 'key' with the sequence of OVS_KEY_ATTR_* Netlink attributes
4101  * that can be used to refer to 'subfacet'.  The caller must provide 'keybuf'
4102  * for use as temporary storage. */
4103 static void
4104 subfacet_get_key(struct subfacet *subfacet, struct odputil_keybuf *keybuf,
4105                  struct ofpbuf *key)
4106 {
4107     if (!subfacet->key) {
4108         ofpbuf_use_stack(key, keybuf, sizeof *keybuf);
4109         odp_flow_key_from_flow(key, &subfacet->facet->flow);
4110     } else {
4111         ofpbuf_use_const(key, subfacet->key, subfacet->key_len);
4112     }
4113 }
4114
4115 /* Composes the datapath actions for 'subfacet' based on its rule's actions.
4116  * Translates the actions into 'odp_actions', which the caller must have
4117  * initialized and is responsible for uninitializing. */
4118 static void
4119 subfacet_make_actions(struct subfacet *subfacet, const struct ofpbuf *packet,
4120                       struct ofpbuf *odp_actions)
4121 {
4122     struct facet *facet = subfacet->facet;
4123     struct rule_dpif *rule = facet->rule;
4124     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4125
4126     struct action_xlate_ctx ctx;
4127
4128     action_xlate_ctx_init(&ctx, ofproto, &facet->flow, subfacet->initial_tci,
4129                           rule, 0, packet);
4130     xlate_actions(&ctx, rule->up.actions, rule->up.n_actions, odp_actions);
4131     facet->tags = ctx.tags;
4132     facet->may_install = ctx.may_set_up_flow;
4133     facet->has_learn = ctx.has_learn;
4134     facet->has_normal = ctx.has_normal;
4135     facet->has_fin_timeout = ctx.has_fin_timeout;
4136     facet->nf_flow.output_iface = ctx.nf_output_iface;
4137     facet->mirrors = ctx.mirrors;
4138
4139     if (subfacet->actions_len != odp_actions->size
4140         || memcmp(subfacet->actions, odp_actions->data, odp_actions->size)) {
4141         free(subfacet->actions);
4142         subfacet->actions_len = odp_actions->size;
4143         subfacet->actions = xmemdup(odp_actions->data, odp_actions->size);
4144     }
4145 }
4146
4147 /* Updates 'subfacet''s datapath flow, setting its actions to 'actions_len'
4148  * bytes of actions in 'actions'.  If 'stats' is non-null, statistics counters
4149  * in the datapath will be zeroed and 'stats' will be updated with traffic new
4150  * since 'subfacet' was last updated.
4151  *
4152  * Returns 0 if successful, otherwise a positive errno value. */
4153 static int
4154 subfacet_install(struct subfacet *subfacet,
4155                  const struct nlattr *actions, size_t actions_len,
4156                  struct dpif_flow_stats *stats)
4157 {
4158     struct facet *facet = subfacet->facet;
4159     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4160     struct odputil_keybuf keybuf;
4161     enum dpif_flow_put_flags flags;
4162     struct ofpbuf key;
4163     int ret;
4164
4165     flags = DPIF_FP_CREATE | DPIF_FP_MODIFY;
4166     if (stats) {
4167         flags |= DPIF_FP_ZERO_STATS;
4168     }
4169
4170     subfacet_get_key(subfacet, &keybuf, &key);
4171     ret = dpif_flow_put(ofproto->dpif, flags, key.data, key.size,
4172                         actions, actions_len, stats);
4173
4174     if (stats) {
4175         subfacet_reset_dp_stats(subfacet, stats);
4176     }
4177
4178     return ret;
4179 }
4180
4181 /* If 'subfacet' is installed in the datapath, uninstalls it. */
4182 static void
4183 subfacet_uninstall(struct subfacet *subfacet)
4184 {
4185     if (subfacet->installed) {
4186         struct rule_dpif *rule = subfacet->facet->rule;
4187         struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4188         struct odputil_keybuf keybuf;
4189         struct dpif_flow_stats stats;
4190         struct ofpbuf key;
4191         int error;
4192
4193         subfacet_get_key(subfacet, &keybuf, &key);
4194         error = dpif_flow_del(ofproto->dpif, key.data, key.size, &stats);
4195         subfacet_reset_dp_stats(subfacet, &stats);
4196         if (!error) {
4197             subfacet_update_stats(subfacet, &stats);
4198         }
4199         subfacet->installed = false;
4200     } else {
4201         assert(subfacet->dp_packet_count == 0);
4202         assert(subfacet->dp_byte_count == 0);
4203     }
4204 }
4205
4206 /* Resets 'subfacet''s datapath statistics counters.  This should be called
4207  * when 'subfacet''s statistics are cleared in the datapath.  If 'stats' is
4208  * non-null, it should contain the statistics returned by dpif when 'subfacet'
4209  * was reset in the datapath.  'stats' will be modified to include only
4210  * statistics new since 'subfacet' was last updated. */
4211 static void
4212 subfacet_reset_dp_stats(struct subfacet *subfacet,
4213                         struct dpif_flow_stats *stats)
4214 {
4215     if (stats
4216         && subfacet->dp_packet_count <= stats->n_packets
4217         && subfacet->dp_byte_count <= stats->n_bytes) {
4218         stats->n_packets -= subfacet->dp_packet_count;
4219         stats->n_bytes -= subfacet->dp_byte_count;
4220     }
4221
4222     subfacet->dp_packet_count = 0;
4223     subfacet->dp_byte_count = 0;
4224 }
4225
4226 /* Updates 'subfacet''s used time.  The caller is responsible for calling
4227  * facet_push_stats() to update the flows which 'subfacet' resubmits into. */
4228 static void
4229 subfacet_update_time(struct subfacet *subfacet, long long int used)
4230 {
4231     if (used > subfacet->used) {
4232         subfacet->used = used;
4233         facet_update_time(subfacet->facet, used);
4234     }
4235 }
4236
4237 /* Folds the statistics from 'stats' into the counters in 'subfacet'.
4238  *
4239  * Because of the meaning of a subfacet's counters, it only makes sense to do
4240  * this if 'stats' are not tracked in the datapath, that is, if 'stats'
4241  * represents a packet that was sent by hand or if it represents statistics
4242  * that have been cleared out of the datapath. */
4243 static void
4244 subfacet_update_stats(struct subfacet *subfacet,
4245                       const struct dpif_flow_stats *stats)
4246 {
4247     if (stats->n_packets || stats->used > subfacet->used) {
4248         struct facet *facet = subfacet->facet;
4249
4250         subfacet_update_time(subfacet, stats->used);
4251         facet->packet_count += stats->n_packets;
4252         facet->byte_count += stats->n_bytes;
4253         facet->tcp_flags |= stats->tcp_flags;
4254         facet_push_stats(facet);
4255         netflow_flow_update_flags(&facet->nf_flow, stats->tcp_flags);
4256     }
4257 }
4258 \f
4259 /* Rules. */
4260
4261 static struct rule_dpif *
4262 rule_dpif_lookup(struct ofproto_dpif *ofproto, const struct flow *flow,
4263                  uint8_t table_id)
4264 {
4265     struct cls_rule *cls_rule;
4266     struct classifier *cls;
4267
4268     if (table_id >= N_TABLES) {
4269         return NULL;
4270     }
4271
4272     cls = &ofproto->up.tables[table_id].cls;
4273     if (flow->nw_frag & FLOW_NW_FRAG_ANY
4274         && ofproto->up.frag_handling == OFPC_FRAG_NORMAL) {
4275         /* For OFPC_NORMAL frag_handling, we must pretend that transport ports
4276          * are unavailable. */
4277         struct flow ofpc_normal_flow = *flow;
4278         ofpc_normal_flow.tp_src = htons(0);
4279         ofpc_normal_flow.tp_dst = htons(0);
4280         cls_rule = classifier_lookup(cls, &ofpc_normal_flow);
4281     } else {
4282         cls_rule = classifier_lookup(cls, flow);
4283     }
4284     return rule_dpif_cast(rule_from_cls_rule(cls_rule));
4285 }
4286
4287 static void
4288 complete_operation(struct rule_dpif *rule)
4289 {
4290     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4291
4292     rule_invalidate(rule);
4293     if (clogged) {
4294         struct dpif_completion *c = xmalloc(sizeof *c);
4295         c->op = rule->up.pending;
4296         list_push_back(&ofproto->completions, &c->list_node);
4297     } else {
4298         ofoperation_complete(rule->up.pending, 0);
4299     }
4300 }
4301
4302 static struct rule *
4303 rule_alloc(void)
4304 {
4305     struct rule_dpif *rule = xmalloc(sizeof *rule);
4306     return &rule->up;
4307 }
4308
4309 static void
4310 rule_dealloc(struct rule *rule_)
4311 {
4312     struct rule_dpif *rule = rule_dpif_cast(rule_);
4313     free(rule);
4314 }
4315
4316 static enum ofperr
4317 rule_construct(struct rule *rule_)
4318 {
4319     struct rule_dpif *rule = rule_dpif_cast(rule_);
4320     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4321     struct rule_dpif *victim;
4322     uint8_t table_id;
4323     enum ofperr error;
4324
4325     error = validate_actions(rule->up.actions, rule->up.n_actions,
4326                              &rule->up.cr.flow, ofproto->max_ports);
4327     if (error) {
4328         return error;
4329     }
4330
4331     rule->packet_count = 0;
4332     rule->byte_count = 0;
4333
4334     victim = rule_dpif_cast(ofoperation_get_victim(rule->up.pending));
4335     if (victim && !list_is_empty(&victim->facets)) {
4336         struct facet *facet;
4337
4338         rule->facets = victim->facets;
4339         list_moved(&rule->facets);
4340         LIST_FOR_EACH (facet, list_node, &rule->facets) {
4341             /* XXX: We're only clearing our local counters here.  It's possible
4342              * that quite a few packets are unaccounted for in the datapath
4343              * statistics.  These will be accounted to the new rule instead of
4344              * cleared as required.  This could be fixed by clearing out the
4345              * datapath statistics for this facet, but currently it doesn't
4346              * seem worth it. */
4347             facet_reset_counters(facet);
4348             facet->rule = rule;
4349         }
4350     } else {
4351         /* Must avoid list_moved() in this case. */
4352         list_init(&rule->facets);
4353     }
4354
4355     table_id = rule->up.table_id;
4356     rule->tag = (victim ? victim->tag
4357                  : table_id == 0 ? 0
4358                  : rule_calculate_tag(&rule->up.cr.flow, &rule->up.cr.wc,
4359                                       ofproto->tables[table_id].basis));
4360
4361     complete_operation(rule);
4362     return 0;
4363 }
4364
4365 static void
4366 rule_destruct(struct rule *rule_)
4367 {
4368     struct rule_dpif *rule = rule_dpif_cast(rule_);
4369     struct facet *facet, *next_facet;
4370
4371     LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
4372         facet_revalidate(facet);
4373     }
4374
4375     complete_operation(rule);
4376 }
4377
4378 static void
4379 rule_get_stats(struct rule *rule_, uint64_t *packets, uint64_t *bytes)
4380 {
4381     struct rule_dpif *rule = rule_dpif_cast(rule_);
4382     struct facet *facet;
4383
4384     /* Start from historical data for 'rule' itself that are no longer tracked
4385      * in facets.  This counts, for example, facets that have expired. */
4386     *packets = rule->packet_count;
4387     *bytes = rule->byte_count;
4388
4389     /* Add any statistics that are tracked by facets.  This includes
4390      * statistical data recently updated by ofproto_update_stats() as well as
4391      * stats for packets that were executed "by hand" via dpif_execute(). */
4392     LIST_FOR_EACH (facet, list_node, &rule->facets) {
4393         *packets += facet->packet_count;
4394         *bytes += facet->byte_count;
4395     }
4396 }
4397
4398 static enum ofperr
4399 rule_execute(struct rule *rule_, const struct flow *flow,
4400              struct ofpbuf *packet)
4401 {
4402     struct rule_dpif *rule = rule_dpif_cast(rule_);
4403     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4404
4405     struct dpif_flow_stats stats;
4406
4407     struct action_xlate_ctx ctx;
4408     uint64_t odp_actions_stub[1024 / 8];
4409     struct ofpbuf odp_actions;
4410
4411     dpif_flow_stats_extract(flow, packet, &stats);
4412     rule_credit_stats(rule, &stats);
4413
4414     ofpbuf_use_stub(&odp_actions, odp_actions_stub, sizeof odp_actions_stub);
4415     action_xlate_ctx_init(&ctx, ofproto, flow, flow->vlan_tci,
4416                           rule, stats.tcp_flags, packet);
4417     ctx.resubmit_stats = &stats;
4418     xlate_actions(&ctx, rule->up.actions, rule->up.n_actions, &odp_actions);
4419
4420     execute_odp_actions(ofproto, flow, odp_actions.data,
4421                         odp_actions.size, packet);
4422
4423     ofpbuf_uninit(&odp_actions);
4424
4425     return 0;
4426 }
4427
4428 static void
4429 rule_modify_actions(struct rule *rule_)
4430 {
4431     struct rule_dpif *rule = rule_dpif_cast(rule_);
4432     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
4433     enum ofperr error;
4434
4435     error = validate_actions(rule->up.actions, rule->up.n_actions,
4436                              &rule->up.cr.flow, ofproto->max_ports);
4437     if (error) {
4438         ofoperation_complete(rule->up.pending, error);
4439         return;
4440     }
4441
4442     complete_operation(rule);
4443 }
4444 \f
4445 /* Sends 'packet' out 'ofport'.
4446  * May modify 'packet'.
4447  * Returns 0 if successful, otherwise a positive errno value. */
4448 static int
4449 send_packet(const struct ofport_dpif *ofport, struct ofpbuf *packet)
4450 {
4451     const struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
4452     struct ofpbuf key, odp_actions;
4453     struct odputil_keybuf keybuf;
4454     uint16_t odp_port;
4455     struct flow flow;
4456     int error;
4457
4458     flow_extract((struct ofpbuf *) packet, 0, 0, 0, &flow);
4459     odp_port = vsp_realdev_to_vlandev(ofproto, ofport->odp_port,
4460                                       flow.vlan_tci);
4461     if (odp_port != ofport->odp_port) {
4462         eth_pop_vlan(packet);
4463         flow.vlan_tci = htons(0);
4464     }
4465
4466     ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
4467     odp_flow_key_from_flow(&key, &flow);
4468
4469     ofpbuf_init(&odp_actions, 32);
4470     compose_sflow_action(ofproto, &odp_actions, &flow, odp_port);
4471
4472     nl_msg_put_u32(&odp_actions, OVS_ACTION_ATTR_OUTPUT, odp_port);
4473     error = dpif_execute(ofproto->dpif,
4474                          key.data, key.size,
4475                          odp_actions.data, odp_actions.size,
4476                          packet);
4477     ofpbuf_uninit(&odp_actions);
4478
4479     if (error) {
4480         VLOG_WARN_RL(&rl, "%s: failed to send packet on port %"PRIu32" (%s)",
4481                      ofproto->up.name, odp_port, strerror(error));
4482     }
4483     ofproto_update_local_port_stats(ofport->up.ofproto, packet->size, 0);
4484     return error;
4485 }
4486 \f
4487 /* OpenFlow to datapath action translation. */
4488
4489 static void do_xlate_actions(const union ofp_action *in, size_t n_in,
4490                              struct action_xlate_ctx *ctx);
4491 static void xlate_normal(struct action_xlate_ctx *);
4492
4493 static size_t
4494 put_userspace_action(const struct ofproto_dpif *ofproto,
4495                      struct ofpbuf *odp_actions,
4496                      const struct flow *flow,
4497                      const struct user_action_cookie *cookie)
4498 {
4499     uint32_t pid;
4500
4501     pid = dpif_port_get_pid(ofproto->dpif,
4502                             ofp_port_to_odp_port(flow->in_port));
4503
4504     return odp_put_userspace_action(pid, cookie, odp_actions);
4505 }
4506
4507 /* Compose SAMPLE action for sFlow. */
4508 static size_t
4509 compose_sflow_action(const struct ofproto_dpif *ofproto,
4510                      struct ofpbuf *odp_actions,
4511                      const struct flow *flow,
4512                      uint32_t odp_port)
4513 {
4514     uint32_t port_ifindex;
4515     uint32_t probability;
4516     struct user_action_cookie cookie;
4517     size_t sample_offset, actions_offset;
4518     int cookie_offset, n_output;
4519
4520     if (!ofproto->sflow || flow->in_port == OFPP_NONE) {
4521         return 0;
4522     }
4523
4524     if (odp_port == OVSP_NONE) {
4525         port_ifindex = 0;
4526         n_output = 0;
4527     } else {
4528         port_ifindex = dpif_sflow_odp_port_to_ifindex(ofproto->sflow, odp_port);
4529         n_output = 1;
4530     }
4531
4532     sample_offset = nl_msg_start_nested(odp_actions, OVS_ACTION_ATTR_SAMPLE);
4533
4534     /* Number of packets out of UINT_MAX to sample. */
4535     probability = dpif_sflow_get_probability(ofproto->sflow);
4536     nl_msg_put_u32(odp_actions, OVS_SAMPLE_ATTR_PROBABILITY, probability);
4537
4538     actions_offset = nl_msg_start_nested(odp_actions, OVS_SAMPLE_ATTR_ACTIONS);
4539
4540     cookie.type = USER_ACTION_COOKIE_SFLOW;
4541     cookie.data = port_ifindex;
4542     cookie.n_output = n_output;
4543     cookie.vlan_tci = 0;
4544     cookie_offset = put_userspace_action(ofproto, odp_actions, flow, &cookie);
4545
4546     nl_msg_end_nested(odp_actions, actions_offset);
4547     nl_msg_end_nested(odp_actions, sample_offset);
4548     return cookie_offset;
4549 }
4550
4551 /* SAMPLE action must be first action in any given list of actions.
4552  * At this point we do not have all information required to build it. So try to
4553  * build sample action as complete as possible. */
4554 static void
4555 add_sflow_action(struct action_xlate_ctx *ctx)
4556 {
4557     ctx->user_cookie_offset = compose_sflow_action(ctx->ofproto,
4558                                                    ctx->odp_actions,
4559                                                    &ctx->flow, OVSP_NONE);
4560     ctx->sflow_odp_port = 0;
4561     ctx->sflow_n_outputs = 0;
4562 }
4563
4564 /* Fix SAMPLE action according to data collected while composing ODP actions.
4565  * We need to fix SAMPLE actions OVS_SAMPLE_ATTR_ACTIONS attribute, i.e. nested
4566  * USERSPACE action's user-cookie which is required for sflow. */
4567 static void
4568 fix_sflow_action(struct action_xlate_ctx *ctx)
4569 {
4570     const struct flow *base = &ctx->base_flow;
4571     struct user_action_cookie *cookie;
4572
4573     if (!ctx->user_cookie_offset) {
4574         return;
4575     }
4576
4577     cookie = ofpbuf_at(ctx->odp_actions, ctx->user_cookie_offset,
4578                      sizeof(*cookie));
4579     assert(cookie != NULL);
4580     assert(cookie->type == USER_ACTION_COOKIE_SFLOW);
4581
4582     if (ctx->sflow_n_outputs) {
4583         cookie->data = dpif_sflow_odp_port_to_ifindex(ctx->ofproto->sflow,
4584                                                     ctx->sflow_odp_port);
4585     }
4586     if (ctx->sflow_n_outputs >= 255) {
4587         cookie->n_output = 255;
4588     } else {
4589         cookie->n_output = ctx->sflow_n_outputs;
4590     }
4591     cookie->vlan_tci = base->vlan_tci;
4592 }
4593
4594 static void
4595 compose_output_action__(struct action_xlate_ctx *ctx, uint16_t ofp_port,
4596                         bool check_stp)
4597 {
4598     const struct ofport_dpif *ofport = get_ofp_port(ctx->ofproto, ofp_port);
4599     uint16_t odp_port = ofp_port_to_odp_port(ofp_port);
4600     ovs_be16 flow_vlan_tci = ctx->flow.vlan_tci;
4601     uint8_t flow_nw_tos = ctx->flow.nw_tos;
4602     uint16_t out_port;
4603
4604     if (ofport) {
4605         struct priority_to_dscp *pdscp;
4606
4607         if (ofport->up.pp.config & OFPUTIL_PC_NO_FWD
4608             || (check_stp && !stp_forward_in_state(ofport->stp_state))) {
4609             return;
4610         }
4611
4612         pdscp = get_priority(ofport, ctx->flow.skb_priority);
4613         if (pdscp) {
4614             ctx->flow.nw_tos &= ~IP_DSCP_MASK;
4615             ctx->flow.nw_tos |= pdscp->dscp;
4616         }
4617     } else {
4618         /* We may not have an ofport record for this port, but it doesn't hurt
4619          * to allow forwarding to it anyhow.  Maybe such a port will appear
4620          * later and we're pre-populating the flow table.  */
4621     }
4622
4623     out_port = vsp_realdev_to_vlandev(ctx->ofproto, odp_port,
4624                                       ctx->flow.vlan_tci);
4625     if (out_port != odp_port) {
4626         ctx->flow.vlan_tci = htons(0);
4627     }
4628     commit_odp_actions(&ctx->flow, &ctx->base_flow, ctx->odp_actions);
4629     nl_msg_put_u32(ctx->odp_actions, OVS_ACTION_ATTR_OUTPUT, out_port);
4630
4631     ctx->sflow_odp_port = odp_port;
4632     ctx->sflow_n_outputs++;
4633     ctx->nf_output_iface = ofp_port;
4634     ctx->flow.vlan_tci = flow_vlan_tci;
4635     ctx->flow.nw_tos = flow_nw_tos;
4636 }
4637
4638 static void
4639 compose_output_action(struct action_xlate_ctx *ctx, uint16_t ofp_port)
4640 {
4641     compose_output_action__(ctx, ofp_port, true);
4642 }
4643
4644 static void
4645 xlate_table_action(struct action_xlate_ctx *ctx,
4646                    uint16_t in_port, uint8_t table_id)
4647 {
4648     if (ctx->recurse < MAX_RESUBMIT_RECURSION) {
4649         struct ofproto_dpif *ofproto = ctx->ofproto;
4650         struct rule_dpif *rule;
4651         uint16_t old_in_port;
4652         uint8_t old_table_id;
4653
4654         old_table_id = ctx->table_id;
4655         ctx->table_id = table_id;
4656
4657         /* Look up a flow with 'in_port' as the input port. */
4658         old_in_port = ctx->flow.in_port;
4659         ctx->flow.in_port = in_port;
4660         rule = rule_dpif_lookup(ofproto, &ctx->flow, table_id);
4661
4662         /* Tag the flow. */
4663         if (table_id > 0 && table_id < N_TABLES) {
4664             struct table_dpif *table = &ofproto->tables[table_id];
4665             if (table->other_table) {
4666                 ctx->tags |= (rule && rule->tag
4667                               ? rule->tag
4668                               : rule_calculate_tag(&ctx->flow,
4669                                                    &table->other_table->wc,
4670                                                    table->basis));
4671             }
4672         }
4673
4674         /* Restore the original input port.  Otherwise OFPP_NORMAL and
4675          * OFPP_IN_PORT will have surprising behavior. */
4676         ctx->flow.in_port = old_in_port;
4677
4678         if (ctx->resubmit_hook) {
4679             ctx->resubmit_hook(ctx, rule);
4680         }
4681
4682         if (rule) {
4683             struct rule_dpif *old_rule = ctx->rule;
4684
4685             if (ctx->resubmit_stats) {
4686                 rule_credit_stats(rule, ctx->resubmit_stats);
4687             }
4688
4689             ctx->recurse++;
4690             ctx->rule = rule;
4691             do_xlate_actions(rule->up.actions, rule->up.n_actions, ctx);
4692             ctx->rule = old_rule;
4693             ctx->recurse--;
4694         }
4695
4696         ctx->table_id = old_table_id;
4697     } else {
4698         static struct vlog_rate_limit recurse_rl = VLOG_RATE_LIMIT_INIT(1, 1);
4699
4700         VLOG_ERR_RL(&recurse_rl, "resubmit actions recursed over %d times",
4701                     MAX_RESUBMIT_RECURSION);
4702         ctx->max_resubmit_trigger = true;
4703     }
4704 }
4705
4706 static void
4707 xlate_resubmit_table(struct action_xlate_ctx *ctx,
4708                      const struct nx_action_resubmit *nar)
4709 {
4710     uint16_t in_port;
4711     uint8_t table_id;
4712
4713     in_port = (nar->in_port == htons(OFPP_IN_PORT)
4714                ? ctx->flow.in_port
4715                : ntohs(nar->in_port));
4716     table_id = nar->table == 255 ? ctx->table_id : nar->table;
4717
4718     xlate_table_action(ctx, in_port, table_id);
4719 }
4720
4721 static void
4722 flood_packets(struct action_xlate_ctx *ctx, bool all)
4723 {
4724     struct ofport_dpif *ofport;
4725
4726     HMAP_FOR_EACH (ofport, up.hmap_node, &ctx->ofproto->up.ports) {
4727         uint16_t ofp_port = ofport->up.ofp_port;
4728
4729         if (ofp_port == ctx->flow.in_port) {
4730             continue;
4731         }
4732
4733         if (all) {
4734             compose_output_action__(ctx, ofp_port, false);
4735         } else if (!(ofport->up.pp.config & OFPUTIL_PC_NO_FLOOD)) {
4736             compose_output_action(ctx, ofp_port);
4737         }
4738     }
4739
4740     ctx->nf_output_iface = NF_OUT_FLOOD;
4741 }
4742
4743 static void
4744 execute_controller_action(struct action_xlate_ctx *ctx, int len,
4745                           enum ofp_packet_in_reason reason,
4746                           uint16_t controller_id)
4747 {
4748     struct ofputil_packet_in pin;
4749     struct ofpbuf *packet;
4750
4751     ctx->may_set_up_flow = false;
4752     if (!ctx->packet) {
4753         return;
4754     }
4755
4756     packet = ofpbuf_clone(ctx->packet);
4757
4758     if (packet->l2 && packet->l3) {
4759         struct eth_header *eh;
4760
4761         eth_pop_vlan(packet);
4762         eh = packet->l2;
4763
4764         /* If the Ethernet type is less than ETH_TYPE_MIN, it's likely an 802.2
4765          * LLC frame.  Calculating the Ethernet type of these frames is more
4766          * trouble than seems appropriate for a simple assertion. */
4767         assert(ntohs(eh->eth_type) < ETH_TYPE_MIN
4768                || eh->eth_type == ctx->flow.dl_type);
4769
4770         memcpy(eh->eth_src, ctx->flow.dl_src, sizeof eh->eth_src);
4771         memcpy(eh->eth_dst, ctx->flow.dl_dst, sizeof eh->eth_dst);
4772
4773         if (ctx->flow.vlan_tci & htons(VLAN_CFI)) {
4774             eth_push_vlan(packet, ctx->flow.vlan_tci);
4775         }
4776
4777         if (packet->l4) {
4778             if (ctx->flow.dl_type == htons(ETH_TYPE_IP)) {
4779                 packet_set_ipv4(packet, ctx->flow.nw_src, ctx->flow.nw_dst,
4780                                 ctx->flow.nw_tos, ctx->flow.nw_ttl);
4781             }
4782
4783             if (packet->l7) {
4784                 if (ctx->flow.nw_proto == IPPROTO_TCP) {
4785                     packet_set_tcp_port(packet, ctx->flow.tp_src,
4786                                         ctx->flow.tp_dst);
4787                 } else if (ctx->flow.nw_proto == IPPROTO_UDP) {
4788                     packet_set_udp_port(packet, ctx->flow.tp_src,
4789                                         ctx->flow.tp_dst);
4790                 }
4791             }
4792         }
4793     }
4794
4795     pin.packet = packet->data;
4796     pin.packet_len = packet->size;
4797     pin.reason = reason;
4798     pin.controller_id = controller_id;
4799     pin.table_id = ctx->table_id;
4800     pin.cookie = ctx->rule ? ctx->rule->up.flow_cookie : 0;
4801
4802     pin.send_len = len;
4803     flow_get_metadata(&ctx->flow, &pin.fmd);
4804
4805     connmgr_send_packet_in(ctx->ofproto->up.connmgr, &pin);
4806     ofpbuf_delete(packet);
4807 }
4808
4809 static bool
4810 compose_dec_ttl(struct action_xlate_ctx *ctx)
4811 {
4812     if (ctx->flow.dl_type != htons(ETH_TYPE_IP) &&
4813         ctx->flow.dl_type != htons(ETH_TYPE_IPV6)) {
4814         return false;
4815     }
4816
4817     if (ctx->flow.nw_ttl > 1) {
4818         ctx->flow.nw_ttl--;
4819         return false;
4820     } else {
4821         execute_controller_action(ctx, UINT16_MAX, OFPR_INVALID_TTL, 0);
4822
4823         /* Stop processing for current table. */
4824         return true;
4825     }
4826 }
4827
4828 static void
4829 xlate_output_action__(struct action_xlate_ctx *ctx,
4830                       uint16_t port, uint16_t max_len)
4831 {
4832     uint16_t prev_nf_output_iface = ctx->nf_output_iface;
4833
4834     ctx->nf_output_iface = NF_OUT_DROP;
4835
4836     switch (port) {
4837     case OFPP_IN_PORT:
4838         compose_output_action(ctx, ctx->flow.in_port);
4839         break;
4840     case OFPP_TABLE:
4841         xlate_table_action(ctx, ctx->flow.in_port, ctx->table_id);
4842         break;
4843     case OFPP_NORMAL:
4844         xlate_normal(ctx);
4845         break;
4846     case OFPP_FLOOD:
4847         flood_packets(ctx,  false);
4848         break;
4849     case OFPP_ALL:
4850         flood_packets(ctx, true);
4851         break;
4852     case OFPP_CONTROLLER:
4853         execute_controller_action(ctx, max_len, OFPR_ACTION, 0);
4854         break;
4855     case OFPP_NONE:
4856         break;
4857     case OFPP_LOCAL:
4858     default:
4859         if (port != ctx->flow.in_port) {
4860             compose_output_action(ctx, port);
4861         }
4862         break;
4863     }
4864
4865     if (prev_nf_output_iface == NF_OUT_FLOOD) {
4866         ctx->nf_output_iface = NF_OUT_FLOOD;
4867     } else if (ctx->nf_output_iface == NF_OUT_DROP) {
4868         ctx->nf_output_iface = prev_nf_output_iface;
4869     } else if (prev_nf_output_iface != NF_OUT_DROP &&
4870                ctx->nf_output_iface != NF_OUT_FLOOD) {
4871         ctx->nf_output_iface = NF_OUT_MULTI;
4872     }
4873 }
4874
4875 static void
4876 xlate_output_reg_action(struct action_xlate_ctx *ctx,
4877                         const struct nx_action_output_reg *naor)
4878 {
4879     struct mf_subfield src;
4880     uint64_t ofp_port;
4881
4882     nxm_decode(&src, naor->src, naor->ofs_nbits);
4883     ofp_port = mf_get_subfield(&src, &ctx->flow);
4884
4885     if (ofp_port <= UINT16_MAX) {
4886         xlate_output_action__(ctx, ofp_port, ntohs(naor->max_len));
4887     }
4888 }
4889
4890 static void
4891 xlate_output_action(struct action_xlate_ctx *ctx,
4892                     const struct ofp_action_output *oao)
4893 {
4894     xlate_output_action__(ctx, ntohs(oao->port), ntohs(oao->max_len));
4895 }
4896
4897 static void
4898 xlate_enqueue_action(struct action_xlate_ctx *ctx,
4899                      const struct ofp_action_enqueue *oae)
4900 {
4901     uint16_t ofp_port;
4902     uint32_t flow_priority, priority;
4903     int error;
4904
4905     error = dpif_queue_to_priority(ctx->ofproto->dpif, ntohl(oae->queue_id),
4906                                    &priority);
4907     if (error) {
4908         /* Fall back to ordinary output action. */
4909         xlate_output_action__(ctx, ntohs(oae->port), 0);
4910         return;
4911     }
4912
4913     /* Figure out datapath output port. */
4914     ofp_port = ntohs(oae->port);
4915     if (ofp_port == OFPP_IN_PORT) {
4916         ofp_port = ctx->flow.in_port;
4917     } else if (ofp_port == ctx->flow.in_port) {
4918         return;
4919     }
4920
4921     /* Add datapath actions. */
4922     flow_priority = ctx->flow.skb_priority;
4923     ctx->flow.skb_priority = priority;
4924     compose_output_action(ctx, ofp_port);
4925     ctx->flow.skb_priority = flow_priority;
4926
4927     /* Update NetFlow output port. */
4928     if (ctx->nf_output_iface == NF_OUT_DROP) {
4929         ctx->nf_output_iface = ofp_port;
4930     } else if (ctx->nf_output_iface != NF_OUT_FLOOD) {
4931         ctx->nf_output_iface = NF_OUT_MULTI;
4932     }
4933 }
4934
4935 static void
4936 xlate_set_queue_action(struct action_xlate_ctx *ctx,
4937                        const struct nx_action_set_queue *nasq)
4938 {
4939     uint32_t priority;
4940     int error;
4941
4942     error = dpif_queue_to_priority(ctx->ofproto->dpif, ntohl(nasq->queue_id),
4943                                    &priority);
4944     if (error) {
4945         /* Couldn't translate queue to a priority, so ignore.  A warning
4946          * has already been logged. */
4947         return;
4948     }
4949
4950     ctx->flow.skb_priority = priority;
4951 }
4952
4953 struct xlate_reg_state {
4954     ovs_be16 vlan_tci;
4955     ovs_be64 tun_id;
4956 };
4957
4958 static void
4959 xlate_autopath(struct action_xlate_ctx *ctx,
4960                const struct nx_action_autopath *naa)
4961 {
4962     uint16_t ofp_port = ntohl(naa->id);
4963     struct ofport_dpif *port = get_ofp_port(ctx->ofproto, ofp_port);
4964
4965     if (!port || !port->bundle) {
4966         ofp_port = OFPP_NONE;
4967     } else if (port->bundle->bond) {
4968         /* Autopath does not support VLAN hashing. */
4969         struct ofport_dpif *slave = bond_choose_output_slave(
4970             port->bundle->bond, &ctx->flow, 0, &ctx->tags);
4971         if (slave) {
4972             ofp_port = slave->up.ofp_port;
4973         }
4974     }
4975     autopath_execute(naa, &ctx->flow, ofp_port);
4976 }
4977
4978 static bool
4979 slave_enabled_cb(uint16_t ofp_port, void *ofproto_)
4980 {
4981     struct ofproto_dpif *ofproto = ofproto_;
4982     struct ofport_dpif *port;
4983
4984     switch (ofp_port) {
4985     case OFPP_IN_PORT:
4986     case OFPP_TABLE:
4987     case OFPP_NORMAL:
4988     case OFPP_FLOOD:
4989     case OFPP_ALL:
4990     case OFPP_NONE:
4991         return true;
4992     case OFPP_CONTROLLER: /* Not supported by the bundle action. */
4993         return false;
4994     default:
4995         port = get_ofp_port(ofproto, ofp_port);
4996         return port ? port->may_enable : false;
4997     }
4998 }
4999
5000 static void
5001 xlate_learn_action(struct action_xlate_ctx *ctx,
5002                    const struct nx_action_learn *learn)
5003 {
5004     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
5005     struct ofputil_flow_mod fm;
5006     int error;
5007
5008     learn_execute(learn, &ctx->flow, &fm);
5009
5010     error = ofproto_flow_mod(&ctx->ofproto->up, &fm);
5011     if (error && !VLOG_DROP_WARN(&rl)) {
5012         VLOG_WARN("learning action failed to modify flow table (%s)",
5013                   ofperr_get_name(error));
5014     }
5015
5016     free(fm.actions);
5017 }
5018
5019 /* Reduces '*timeout' to no more than 'max'.  A value of zero in either case
5020  * means "infinite". */
5021 static void
5022 reduce_timeout(uint16_t max, uint16_t *timeout)
5023 {
5024     if (max && (!*timeout || *timeout > max)) {
5025         *timeout = max;
5026     }
5027 }
5028
5029 static void
5030 xlate_fin_timeout(struct action_xlate_ctx *ctx,
5031                   const struct nx_action_fin_timeout *naft)
5032 {
5033     if (ctx->tcp_flags & (TCP_FIN | TCP_RST) && ctx->rule) {
5034         struct rule_dpif *rule = ctx->rule;
5035
5036         reduce_timeout(ntohs(naft->fin_idle_timeout), &rule->up.idle_timeout);
5037         reduce_timeout(ntohs(naft->fin_hard_timeout), &rule->up.hard_timeout);
5038     }
5039 }
5040
5041 static bool
5042 may_receive(const struct ofport_dpif *port, struct action_xlate_ctx *ctx)
5043 {
5044     if (port->up.pp.config & (eth_addr_equals(ctx->flow.dl_dst, eth_addr_stp)
5045                               ? OFPUTIL_PC_NO_RECV_STP
5046                               : OFPUTIL_PC_NO_RECV)) {
5047         return false;
5048     }
5049
5050     /* Only drop packets here if both forwarding and learning are
5051      * disabled.  If just learning is enabled, we need to have
5052      * OFPP_NORMAL and the learning action have a look at the packet
5053      * before we can drop it. */
5054     if (!stp_forward_in_state(port->stp_state)
5055             && !stp_learn_in_state(port->stp_state)) {
5056         return false;
5057     }
5058
5059     return true;
5060 }
5061
5062 static void
5063 do_xlate_actions(const union ofp_action *in, size_t n_in,
5064                  struct action_xlate_ctx *ctx)
5065 {
5066     const struct ofport_dpif *port;
5067     const union ofp_action *ia;
5068     bool was_evictable = true;
5069     size_t left;
5070
5071     port = get_ofp_port(ctx->ofproto, ctx->flow.in_port);
5072     if (port && !may_receive(port, ctx)) {
5073         /* Drop this flow. */
5074         return;
5075     }
5076
5077     if (ctx->rule) {
5078         /* Don't let the rule we're working on get evicted underneath us. */
5079         was_evictable = ctx->rule->up.evictable;
5080         ctx->rule->up.evictable = false;
5081     }
5082     OFPUTIL_ACTION_FOR_EACH_UNSAFE (ia, left, in, n_in) {
5083         const struct ofp_action_dl_addr *oada;
5084         const struct nx_action_resubmit *nar;
5085         const struct nx_action_set_tunnel *nast;
5086         const struct nx_action_set_queue *nasq;
5087         const struct nx_action_multipath *nam;
5088         const struct nx_action_autopath *naa;
5089         const struct nx_action_bundle *nab;
5090         const struct nx_action_output_reg *naor;
5091         const struct nx_action_controller *nac;
5092         enum ofputil_action_code code;
5093         ovs_be64 tun_id;
5094
5095         if (ctx->exit) {
5096             break;
5097         }
5098
5099         code = ofputil_decode_action_unsafe(ia);
5100         switch (code) {
5101         case OFPUTIL_OFPAT10_OUTPUT:
5102             xlate_output_action(ctx, &ia->output);
5103             break;
5104
5105         case OFPUTIL_OFPAT10_SET_VLAN_VID:
5106             ctx->flow.vlan_tci &= ~htons(VLAN_VID_MASK);
5107             ctx->flow.vlan_tci |= ia->vlan_vid.vlan_vid | htons(VLAN_CFI);
5108             break;
5109
5110         case OFPUTIL_OFPAT10_SET_VLAN_PCP:
5111             ctx->flow.vlan_tci &= ~htons(VLAN_PCP_MASK);
5112             ctx->flow.vlan_tci |= htons(
5113                 (ia->vlan_pcp.vlan_pcp << VLAN_PCP_SHIFT) | VLAN_CFI);
5114             break;
5115
5116         case OFPUTIL_OFPAT10_STRIP_VLAN:
5117             ctx->flow.vlan_tci = htons(0);
5118             break;
5119
5120         case OFPUTIL_OFPAT10_SET_DL_SRC:
5121             oada = ((struct ofp_action_dl_addr *) ia);
5122             memcpy(ctx->flow.dl_src, oada->dl_addr, ETH_ADDR_LEN);
5123             break;
5124
5125         case OFPUTIL_OFPAT10_SET_DL_DST:
5126             oada = ((struct ofp_action_dl_addr *) ia);
5127             memcpy(ctx->flow.dl_dst, oada->dl_addr, ETH_ADDR_LEN);
5128             break;
5129
5130         case OFPUTIL_OFPAT10_SET_NW_SRC:
5131             ctx->flow.nw_src = ia->nw_addr.nw_addr;
5132             break;
5133
5134         case OFPUTIL_OFPAT10_SET_NW_DST:
5135             ctx->flow.nw_dst = ia->nw_addr.nw_addr;
5136             break;
5137
5138         case OFPUTIL_OFPAT10_SET_NW_TOS:
5139             /* OpenFlow 1.0 only supports IPv4. */
5140             if (ctx->flow.dl_type == htons(ETH_TYPE_IP)) {
5141                 ctx->flow.nw_tos &= ~IP_DSCP_MASK;
5142                 ctx->flow.nw_tos |= ia->nw_tos.nw_tos & IP_DSCP_MASK;
5143             }
5144             break;
5145
5146         case OFPUTIL_OFPAT10_SET_TP_SRC:
5147             ctx->flow.tp_src = ia->tp_port.tp_port;
5148             break;
5149
5150         case OFPUTIL_OFPAT10_SET_TP_DST:
5151             ctx->flow.tp_dst = ia->tp_port.tp_port;
5152             break;
5153
5154         case OFPUTIL_OFPAT10_ENQUEUE:
5155             xlate_enqueue_action(ctx, (const struct ofp_action_enqueue *) ia);
5156             break;
5157
5158         case OFPUTIL_NXAST_RESUBMIT:
5159             nar = (const struct nx_action_resubmit *) ia;
5160             xlate_table_action(ctx, ntohs(nar->in_port), ctx->table_id);
5161             break;
5162
5163         case OFPUTIL_NXAST_RESUBMIT_TABLE:
5164             xlate_resubmit_table(ctx, (const struct nx_action_resubmit *) ia);
5165             break;
5166
5167         case OFPUTIL_NXAST_SET_TUNNEL:
5168             nast = (const struct nx_action_set_tunnel *) ia;
5169             tun_id = htonll(ntohl(nast->tun_id));
5170             ctx->flow.tun_id = tun_id;
5171             break;
5172
5173         case OFPUTIL_NXAST_SET_QUEUE:
5174             nasq = (const struct nx_action_set_queue *) ia;
5175             xlate_set_queue_action(ctx, nasq);
5176             break;
5177
5178         case OFPUTIL_NXAST_POP_QUEUE:
5179             ctx->flow.skb_priority = ctx->orig_skb_priority;
5180             break;
5181
5182         case OFPUTIL_NXAST_REG_MOVE:
5183             nxm_execute_reg_move((const struct nx_action_reg_move *) ia,
5184                                  &ctx->flow);
5185             break;
5186
5187         case OFPUTIL_NXAST_REG_LOAD:
5188             nxm_execute_reg_load((const struct nx_action_reg_load *) ia,
5189                                  &ctx->flow);
5190             break;
5191
5192         case OFPUTIL_NXAST_NOTE:
5193             /* Nothing to do. */
5194             break;
5195
5196         case OFPUTIL_NXAST_SET_TUNNEL64:
5197             tun_id = ((const struct nx_action_set_tunnel64 *) ia)->tun_id;
5198             ctx->flow.tun_id = tun_id;
5199             break;
5200
5201         case OFPUTIL_NXAST_MULTIPATH:
5202             nam = (const struct nx_action_multipath *) ia;
5203             multipath_execute(nam, &ctx->flow);
5204             break;
5205
5206         case OFPUTIL_NXAST_AUTOPATH:
5207             naa = (const struct nx_action_autopath *) ia;
5208             xlate_autopath(ctx, naa);
5209             break;
5210
5211         case OFPUTIL_NXAST_BUNDLE:
5212             ctx->ofproto->has_bundle_action = true;
5213             nab = (const struct nx_action_bundle *) ia;
5214             xlate_output_action__(ctx, bundle_execute(nab, &ctx->flow,
5215                                                       slave_enabled_cb,
5216                                                       ctx->ofproto), 0);
5217             break;
5218
5219         case OFPUTIL_NXAST_BUNDLE_LOAD:
5220             ctx->ofproto->has_bundle_action = true;
5221             nab = (const struct nx_action_bundle *) ia;
5222             bundle_execute_load(nab, &ctx->flow, slave_enabled_cb,
5223                                 ctx->ofproto);
5224             break;
5225
5226         case OFPUTIL_NXAST_OUTPUT_REG:
5227             naor = (const struct nx_action_output_reg *) ia;
5228             xlate_output_reg_action(ctx, naor);
5229             break;
5230
5231         case OFPUTIL_NXAST_LEARN:
5232             ctx->has_learn = true;
5233             if (ctx->may_learn) {
5234                 xlate_learn_action(ctx, (const struct nx_action_learn *) ia);
5235             }
5236             break;
5237
5238         case OFPUTIL_NXAST_DEC_TTL:
5239             if (compose_dec_ttl(ctx)) {
5240                 goto out;
5241             }
5242             break;
5243
5244         case OFPUTIL_NXAST_EXIT:
5245             ctx->exit = true;
5246             break;
5247
5248         case OFPUTIL_NXAST_FIN_TIMEOUT:
5249             ctx->has_fin_timeout = true;
5250             xlate_fin_timeout(ctx, (const struct nx_action_fin_timeout *) ia);
5251             break;
5252
5253         case OFPUTIL_NXAST_CONTROLLER:
5254             nac = (const struct nx_action_controller *) ia;
5255             execute_controller_action(ctx, ntohs(nac->max_len), nac->reason,
5256                                       ntohs(nac->controller_id));
5257             break;
5258         }
5259     }
5260
5261 out:
5262     /* We've let OFPP_NORMAL and the learning action look at the packet,
5263      * so drop it now if forwarding is disabled. */
5264     if (port && !stp_forward_in_state(port->stp_state)) {
5265         ofpbuf_clear(ctx->odp_actions);
5266         add_sflow_action(ctx);
5267     }
5268     if (ctx->rule) {
5269         ctx->rule->up.evictable = was_evictable;
5270     }
5271 }
5272
5273 static void
5274 action_xlate_ctx_init(struct action_xlate_ctx *ctx,
5275                       struct ofproto_dpif *ofproto, const struct flow *flow,
5276                       ovs_be16 initial_tci, struct rule_dpif *rule,
5277                       uint8_t tcp_flags, const struct ofpbuf *packet)
5278 {
5279     ctx->ofproto = ofproto;
5280     ctx->flow = *flow;
5281     ctx->base_flow = ctx->flow;
5282     ctx->base_flow.tun_id = 0;
5283     ctx->base_flow.vlan_tci = initial_tci;
5284     ctx->rule = rule;
5285     ctx->packet = packet;
5286     ctx->may_learn = packet != NULL;
5287     ctx->tcp_flags = tcp_flags;
5288     ctx->resubmit_hook = NULL;
5289     ctx->resubmit_stats = NULL;
5290 }
5291
5292 /* Translates the 'n_in' "union ofp_action"s in 'in' into datapath actions in
5293  * 'odp_actions', using 'ctx'. */
5294 static void
5295 xlate_actions(struct action_xlate_ctx *ctx,
5296               const union ofp_action *in, size_t n_in,
5297               struct ofpbuf *odp_actions)
5298 {
5299     struct flow orig_flow = ctx->flow;
5300
5301     COVERAGE_INC(ofproto_dpif_xlate);
5302
5303     ofpbuf_clear(odp_actions);
5304     ofpbuf_reserve(odp_actions, NL_A_U32_SIZE);
5305
5306     ctx->odp_actions = odp_actions;
5307     ctx->tags = 0;
5308     ctx->may_set_up_flow = true;
5309     ctx->has_learn = false;
5310     ctx->has_normal = false;
5311     ctx->has_fin_timeout = false;
5312     ctx->nf_output_iface = NF_OUT_DROP;
5313     ctx->mirrors = 0;
5314     ctx->recurse = 0;
5315     ctx->max_resubmit_trigger = false;
5316     ctx->orig_skb_priority = ctx->flow.skb_priority;
5317     ctx->table_id = 0;
5318     ctx->exit = false;
5319
5320     if (ctx->flow.nw_frag & FLOW_NW_FRAG_ANY) {
5321         switch (ctx->ofproto->up.frag_handling) {
5322         case OFPC_FRAG_NORMAL:
5323             /* We must pretend that transport ports are unavailable. */
5324             ctx->flow.tp_src = ctx->base_flow.tp_src = htons(0);
5325             ctx->flow.tp_dst = ctx->base_flow.tp_dst = htons(0);
5326             break;
5327
5328         case OFPC_FRAG_DROP:
5329             return;
5330
5331         case OFPC_FRAG_REASM:
5332             NOT_REACHED();
5333
5334         case OFPC_FRAG_NX_MATCH:
5335             /* Nothing to do. */
5336             break;
5337
5338         case OFPC_INVALID_TTL_TO_CONTROLLER:
5339             NOT_REACHED();
5340         }
5341     }
5342
5343     if (process_special(ctx->ofproto, &ctx->flow, ctx->packet)) {
5344         ctx->may_set_up_flow = false;
5345     } else {
5346         static struct vlog_rate_limit trace_rl = VLOG_RATE_LIMIT_INIT(1, 1);
5347         struct flow original_flow = ctx->flow;
5348         ovs_be16 initial_tci = ctx->base_flow.vlan_tci;
5349
5350         add_sflow_action(ctx);
5351         do_xlate_actions(in, n_in, ctx);
5352
5353         if (ctx->max_resubmit_trigger && !ctx->resubmit_hook
5354             && !VLOG_DROP_ERR(&trace_rl)) {
5355             struct ds ds = DS_EMPTY_INITIALIZER;
5356
5357             ofproto_trace(ctx->ofproto, &original_flow, ctx->packet,
5358                           initial_tci, &ds);
5359             VLOG_ERR("Trace triggered by excessive resubmit recursion:\n%s",
5360                      ds_cstr(&ds));
5361             ds_destroy(&ds);
5362         }
5363
5364         if (!connmgr_may_set_up_flow(ctx->ofproto->up.connmgr, &ctx->flow,
5365                                      ctx->odp_actions->data,
5366                                      ctx->odp_actions->size)) {
5367             ctx->may_set_up_flow = false;
5368             if (ctx->packet
5369                 && connmgr_msg_in_hook(ctx->ofproto->up.connmgr, &ctx->flow,
5370                                        ctx->packet)) {
5371                 compose_output_action(ctx, OFPP_LOCAL);
5372             }
5373         }
5374         add_mirror_actions(ctx, &orig_flow);
5375         fix_sflow_action(ctx);
5376     }
5377 }
5378
5379 /* Translates the 'n_in' "union ofp_action"s in 'in' into datapath actions,
5380  * using 'ctx', and discards the datapath actions. */
5381 static void
5382 xlate_actions_for_side_effects(struct action_xlate_ctx *ctx,
5383                                const union ofp_action *in, size_t n_in)
5384 {
5385     uint64_t odp_actions_stub[1024 / 8];
5386     struct ofpbuf odp_actions;
5387
5388     ofpbuf_use_stub(&odp_actions, odp_actions_stub, sizeof odp_actions_stub);
5389     xlate_actions(ctx, in, n_in, &odp_actions);
5390     ofpbuf_uninit(&odp_actions);
5391 }
5392 \f
5393 /* OFPP_NORMAL implementation. */
5394
5395 static struct ofport_dpif *ofbundle_get_a_port(const struct ofbundle *);
5396
5397 /* Given 'vid', the VID obtained from the 802.1Q header that was received as
5398  * part of a packet (specify 0 if there was no 802.1Q header), and 'in_bundle',
5399  * the bundle on which the packet was received, returns the VLAN to which the
5400  * packet belongs.
5401  *
5402  * Both 'vid' and the return value are in the range 0...4095. */
5403 static uint16_t
5404 input_vid_to_vlan(const struct ofbundle *in_bundle, uint16_t vid)
5405 {
5406     switch (in_bundle->vlan_mode) {
5407     case PORT_VLAN_ACCESS:
5408         return in_bundle->vlan;
5409         break;
5410
5411     case PORT_VLAN_TRUNK:
5412         return vid;
5413
5414     case PORT_VLAN_NATIVE_UNTAGGED:
5415     case PORT_VLAN_NATIVE_TAGGED:
5416         return vid ? vid : in_bundle->vlan;
5417
5418     default:
5419         NOT_REACHED();
5420     }
5421 }
5422
5423 /* Checks whether a packet with the given 'vid' may ingress on 'in_bundle'.
5424  * If so, returns true.  Otherwise, returns false and, if 'warn' is true, logs
5425  * a warning.
5426  *
5427  * 'vid' should be the VID obtained from the 802.1Q header that was received as
5428  * part of a packet (specify 0 if there was no 802.1Q header), in the range
5429  * 0...4095. */
5430 static bool
5431 input_vid_is_valid(uint16_t vid, struct ofbundle *in_bundle, bool warn)
5432 {
5433     /* Allow any VID on the OFPP_NONE port. */
5434     if (in_bundle == &ofpp_none_bundle) {
5435         return true;
5436     }
5437
5438     switch (in_bundle->vlan_mode) {
5439     case PORT_VLAN_ACCESS:
5440         if (vid) {
5441             if (warn) {
5442                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5443                 VLOG_WARN_RL(&rl, "bridge %s: dropping VLAN %"PRIu16" tagged "
5444                              "packet received on port %s configured as VLAN "
5445                              "%"PRIu16" access port",
5446                              in_bundle->ofproto->up.name, vid,
5447                              in_bundle->name, in_bundle->vlan);
5448             }
5449             return false;
5450         }
5451         return true;
5452
5453     case PORT_VLAN_NATIVE_UNTAGGED:
5454     case PORT_VLAN_NATIVE_TAGGED:
5455         if (!vid) {
5456             /* Port must always carry its native VLAN. */
5457             return true;
5458         }
5459         /* Fall through. */
5460     case PORT_VLAN_TRUNK:
5461         if (!ofbundle_includes_vlan(in_bundle, vid)) {
5462             if (warn) {
5463                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5464                 VLOG_WARN_RL(&rl, "bridge %s: dropping VLAN %"PRIu16" packet "
5465                              "received on port %s not configured for trunking "
5466                              "VLAN %"PRIu16,
5467                              in_bundle->ofproto->up.name, vid,
5468                              in_bundle->name, vid);
5469             }
5470             return false;
5471         }
5472         return true;
5473
5474     default:
5475         NOT_REACHED();
5476     }
5477
5478 }
5479
5480 /* Given 'vlan', the VLAN that a packet belongs to, and
5481  * 'out_bundle', a bundle on which the packet is to be output, returns the VID
5482  * that should be included in the 802.1Q header.  (If the return value is 0,
5483  * then the 802.1Q header should only be included in the packet if there is a
5484  * nonzero PCP.)
5485  *
5486  * Both 'vlan' and the return value are in the range 0...4095. */
5487 static uint16_t
5488 output_vlan_to_vid(const struct ofbundle *out_bundle, uint16_t vlan)
5489 {
5490     switch (out_bundle->vlan_mode) {
5491     case PORT_VLAN_ACCESS:
5492         return 0;
5493
5494     case PORT_VLAN_TRUNK:
5495     case PORT_VLAN_NATIVE_TAGGED:
5496         return vlan;
5497
5498     case PORT_VLAN_NATIVE_UNTAGGED:
5499         return vlan == out_bundle->vlan ? 0 : vlan;
5500
5501     default:
5502         NOT_REACHED();
5503     }
5504 }
5505
5506 static void
5507 output_normal(struct action_xlate_ctx *ctx, const struct ofbundle *out_bundle,
5508               uint16_t vlan)
5509 {
5510     struct ofport_dpif *port;
5511     uint16_t vid;
5512     ovs_be16 tci, old_tci;
5513
5514     vid = output_vlan_to_vid(out_bundle, vlan);
5515     if (!out_bundle->bond) {
5516         port = ofbundle_get_a_port(out_bundle);
5517     } else {
5518         port = bond_choose_output_slave(out_bundle->bond, &ctx->flow,
5519                                         vid, &ctx->tags);
5520         if (!port) {
5521             /* No slaves enabled, so drop packet. */
5522             return;
5523         }
5524     }
5525
5526     old_tci = ctx->flow.vlan_tci;
5527     tci = htons(vid);
5528     if (tci || out_bundle->use_priority_tags) {
5529         tci |= ctx->flow.vlan_tci & htons(VLAN_PCP_MASK);
5530         if (tci) {
5531             tci |= htons(VLAN_CFI);
5532         }
5533     }
5534     ctx->flow.vlan_tci = tci;
5535
5536     compose_output_action(ctx, port->up.ofp_port);
5537     ctx->flow.vlan_tci = old_tci;
5538 }
5539
5540 static int
5541 mirror_mask_ffs(mirror_mask_t mask)
5542 {
5543     BUILD_ASSERT_DECL(sizeof(unsigned int) >= sizeof(mask));
5544     return ffs(mask);
5545 }
5546
5547 static bool
5548 ofbundle_trunks_vlan(const struct ofbundle *bundle, uint16_t vlan)
5549 {
5550     return (bundle->vlan_mode != PORT_VLAN_ACCESS
5551             && (!bundle->trunks || bitmap_is_set(bundle->trunks, vlan)));
5552 }
5553
5554 static bool
5555 ofbundle_includes_vlan(const struct ofbundle *bundle, uint16_t vlan)
5556 {
5557     return vlan == bundle->vlan || ofbundle_trunks_vlan(bundle, vlan);
5558 }
5559
5560 /* Returns an arbitrary interface within 'bundle'. */
5561 static struct ofport_dpif *
5562 ofbundle_get_a_port(const struct ofbundle *bundle)
5563 {
5564     return CONTAINER_OF(list_front(&bundle->ports),
5565                         struct ofport_dpif, bundle_node);
5566 }
5567
5568 static bool
5569 vlan_is_mirrored(const struct ofmirror *m, int vlan)
5570 {
5571     return !m->vlans || bitmap_is_set(m->vlans, vlan);
5572 }
5573
5574 /* Returns true if a packet with Ethernet destination MAC 'dst' may be mirrored
5575  * to a VLAN.  In general most packets may be mirrored but we want to drop
5576  * protocols that may confuse switches. */
5577 static bool
5578 eth_dst_may_rspan(const uint8_t dst[ETH_ADDR_LEN])
5579 {
5580     /* If you change this function's behavior, please update corresponding
5581      * documentation in vswitch.xml at the same time. */
5582     if (dst[0] != 0x01) {
5583         /* All the currently banned MACs happen to start with 01 currently, so
5584          * this is a quick way to eliminate most of the good ones. */
5585     } else {
5586         if (eth_addr_is_reserved(dst)) {
5587             /* Drop STP, IEEE pause frames, and other reserved protocols
5588              * (01-80-c2-00-00-0x). */
5589             return false;
5590         }
5591
5592         if (dst[0] == 0x01 && dst[1] == 0x00 && dst[2] == 0x0c) {
5593             /* Cisco OUI. */
5594             if ((dst[3] & 0xfe) == 0xcc &&
5595                 (dst[4] & 0xfe) == 0xcc &&
5596                 (dst[5] & 0xfe) == 0xcc) {
5597                 /* Drop the following protocols plus others following the same
5598                    pattern:
5599
5600                    CDP, VTP, DTP, PAgP  (01-00-0c-cc-cc-cc)
5601                    Spanning Tree PVSTP+ (01-00-0c-cc-cc-cd)
5602                    STP Uplink Fast      (01-00-0c-cd-cd-cd) */
5603                 return false;
5604             }
5605
5606             if (!(dst[3] | dst[4] | dst[5])) {
5607                 /* Drop Inter Switch Link packets (01-00-0c-00-00-00). */
5608                 return false;
5609             }
5610         }
5611     }
5612     return true;
5613 }
5614
5615 static void
5616 add_mirror_actions(struct action_xlate_ctx *ctx, const struct flow *orig_flow)
5617 {
5618     struct ofproto_dpif *ofproto = ctx->ofproto;
5619     mirror_mask_t mirrors;
5620     struct ofbundle *in_bundle;
5621     uint16_t vlan;
5622     uint16_t vid;
5623     const struct nlattr *a;
5624     size_t left;
5625
5626     in_bundle = lookup_input_bundle(ctx->ofproto, orig_flow->in_port,
5627                                     ctx->packet != NULL);
5628     if (!in_bundle) {
5629         return;
5630     }
5631     mirrors = in_bundle->src_mirrors;
5632
5633     /* Drop frames on bundles reserved for mirroring. */
5634     if (in_bundle->mirror_out) {
5635         if (ctx->packet != NULL) {
5636             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5637             VLOG_WARN_RL(&rl, "bridge %s: dropping packet received on port "
5638                          "%s, which is reserved exclusively for mirroring",
5639                          ctx->ofproto->up.name, in_bundle->name);
5640         }
5641         return;
5642     }
5643
5644     /* Check VLAN. */
5645     vid = vlan_tci_to_vid(orig_flow->vlan_tci);
5646     if (!input_vid_is_valid(vid, in_bundle, ctx->packet != NULL)) {
5647         return;
5648     }
5649     vlan = input_vid_to_vlan(in_bundle, vid);
5650
5651     /* Look at the output ports to check for destination selections. */
5652
5653     NL_ATTR_FOR_EACH (a, left, ctx->odp_actions->data,
5654                       ctx->odp_actions->size) {
5655         enum ovs_action_attr type = nl_attr_type(a);
5656         struct ofport_dpif *ofport;
5657
5658         if (type != OVS_ACTION_ATTR_OUTPUT) {
5659             continue;
5660         }
5661
5662         ofport = get_odp_port(ofproto, nl_attr_get_u32(a));
5663         if (ofport && ofport->bundle) {
5664             mirrors |= ofport->bundle->dst_mirrors;
5665         }
5666     }
5667
5668     if (!mirrors) {
5669         return;
5670     }
5671
5672     /* Restore the original packet before adding the mirror actions. */
5673     ctx->flow = *orig_flow;
5674
5675     while (mirrors) {
5676         struct ofmirror *m;
5677
5678         m = ofproto->mirrors[mirror_mask_ffs(mirrors) - 1];
5679
5680         if (!vlan_is_mirrored(m, vlan)) {
5681             mirrors &= mirrors - 1;
5682             continue;
5683         }
5684
5685         mirrors &= ~m->dup_mirrors;
5686         ctx->mirrors |= m->dup_mirrors;
5687         if (m->out) {
5688             output_normal(ctx, m->out, vlan);
5689         } else if (eth_dst_may_rspan(orig_flow->dl_dst)
5690                    && vlan != m->out_vlan) {
5691             struct ofbundle *bundle;
5692
5693             HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
5694                 if (ofbundle_includes_vlan(bundle, m->out_vlan)
5695                     && !bundle->mirror_out) {
5696                     output_normal(ctx, bundle, m->out_vlan);
5697                 }
5698             }
5699         }
5700     }
5701 }
5702
5703 static void
5704 update_mirror_stats(struct ofproto_dpif *ofproto, mirror_mask_t mirrors,
5705                     uint64_t packets, uint64_t bytes)
5706 {
5707     if (!mirrors) {
5708         return;
5709     }
5710
5711     for (; mirrors; mirrors &= mirrors - 1) {
5712         struct ofmirror *m;
5713
5714         m = ofproto->mirrors[mirror_mask_ffs(mirrors) - 1];
5715
5716         if (!m) {
5717             /* In normal circumstances 'm' will not be NULL.  However,
5718              * if mirrors are reconfigured, we can temporarily get out
5719              * of sync in facet_revalidate().  We could "correct" the
5720              * mirror list before reaching here, but doing that would
5721              * not properly account the traffic stats we've currently
5722              * accumulated for previous mirror configuration. */
5723             continue;
5724         }
5725
5726         m->packet_count += packets;
5727         m->byte_count += bytes;
5728     }
5729 }
5730
5731 /* A VM broadcasts a gratuitous ARP to indicate that it has resumed after
5732  * migration.  Older Citrix-patched Linux DomU used gratuitous ARP replies to
5733  * indicate this; newer upstream kernels use gratuitous ARP requests. */
5734 static bool
5735 is_gratuitous_arp(const struct flow *flow)
5736 {
5737     return (flow->dl_type == htons(ETH_TYPE_ARP)
5738             && eth_addr_is_broadcast(flow->dl_dst)
5739             && (flow->nw_proto == ARP_OP_REPLY
5740                 || (flow->nw_proto == ARP_OP_REQUEST
5741                     && flow->nw_src == flow->nw_dst)));
5742 }
5743
5744 static void
5745 update_learning_table(struct ofproto_dpif *ofproto,
5746                       const struct flow *flow, int vlan,
5747                       struct ofbundle *in_bundle)
5748 {
5749     struct mac_entry *mac;
5750
5751     /* Don't learn the OFPP_NONE port. */
5752     if (in_bundle == &ofpp_none_bundle) {
5753         return;
5754     }
5755
5756     if (!mac_learning_may_learn(ofproto->ml, flow->dl_src, vlan)) {
5757         return;
5758     }
5759
5760     mac = mac_learning_insert(ofproto->ml, flow->dl_src, vlan);
5761     if (is_gratuitous_arp(flow)) {
5762         /* We don't want to learn from gratuitous ARP packets that are
5763          * reflected back over bond slaves so we lock the learning table. */
5764         if (!in_bundle->bond) {
5765             mac_entry_set_grat_arp_lock(mac);
5766         } else if (mac_entry_is_grat_arp_locked(mac)) {
5767             return;
5768         }
5769     }
5770
5771     if (mac_entry_is_new(mac) || mac->port.p != in_bundle) {
5772         /* The log messages here could actually be useful in debugging,
5773          * so keep the rate limit relatively high. */
5774         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300);
5775         VLOG_DBG_RL(&rl, "bridge %s: learned that "ETH_ADDR_FMT" is "
5776                     "on port %s in VLAN %d",
5777                     ofproto->up.name, ETH_ADDR_ARGS(flow->dl_src),
5778                     in_bundle->name, vlan);
5779
5780         mac->port.p = in_bundle;
5781         tag_set_add(&ofproto->revalidate_set,
5782                     mac_learning_changed(ofproto->ml, mac));
5783     }
5784 }
5785
5786 static struct ofbundle *
5787 lookup_input_bundle(struct ofproto_dpif *ofproto, uint16_t in_port, bool warn)
5788 {
5789     struct ofport_dpif *ofport;
5790
5791     /* Special-case OFPP_NONE, which a controller may use as the ingress
5792      * port for traffic that it is sourcing. */
5793     if (in_port == OFPP_NONE) {
5794         return &ofpp_none_bundle;
5795     }
5796
5797     /* Find the port and bundle for the received packet. */
5798     ofport = get_ofp_port(ofproto, in_port);
5799     if (ofport && ofport->bundle) {
5800         return ofport->bundle;
5801     }
5802
5803     /* Odd.  A few possible reasons here:
5804      *
5805      * - We deleted a port but there are still a few packets queued up
5806      *   from it.
5807      *
5808      * - Someone externally added a port (e.g. "ovs-dpctl add-if") that
5809      *   we don't know about.
5810      *
5811      * - The ofproto client didn't configure the port as part of a bundle.
5812      */
5813     if (warn) {
5814         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5815
5816         VLOG_WARN_RL(&rl, "bridge %s: received packet on unknown "
5817                      "port %"PRIu16, ofproto->up.name, in_port);
5818     }
5819     return NULL;
5820 }
5821
5822 /* Determines whether packets in 'flow' within 'ofproto' should be forwarded or
5823  * dropped.  Returns true if they may be forwarded, false if they should be
5824  * dropped.
5825  *
5826  * 'in_port' must be the ofport_dpif that corresponds to flow->in_port.
5827  * 'in_port' must be part of a bundle (e.g. in_port->bundle must be nonnull).
5828  *
5829  * 'vlan' must be the VLAN that corresponds to flow->vlan_tci on 'in_port', as
5830  * returned by input_vid_to_vlan().  It must be a valid VLAN for 'in_port', as
5831  * checked by input_vid_is_valid().
5832  *
5833  * May also add tags to '*tags', although the current implementation only does
5834  * so in one special case.
5835  */
5836 static bool
5837 is_admissible(struct ofproto_dpif *ofproto, const struct flow *flow,
5838               struct ofport_dpif *in_port, uint16_t vlan, tag_type *tags)
5839 {
5840     struct ofbundle *in_bundle = in_port->bundle;
5841
5842     /* Drop frames for reserved multicast addresses
5843      * only if forward_bpdu option is absent. */
5844     if (eth_addr_is_reserved(flow->dl_dst) && !ofproto->up.forward_bpdu) {
5845         return false;
5846     }
5847
5848     if (in_bundle->bond) {
5849         struct mac_entry *mac;
5850
5851         switch (bond_check_admissibility(in_bundle->bond, in_port,
5852                                          flow->dl_dst, tags)) {
5853         case BV_ACCEPT:
5854             break;
5855
5856         case BV_DROP:
5857             return false;
5858
5859         case BV_DROP_IF_MOVED:
5860             mac = mac_learning_lookup(ofproto->ml, flow->dl_src, vlan, NULL);
5861             if (mac && mac->port.p != in_bundle &&
5862                 (!is_gratuitous_arp(flow)
5863                  || mac_entry_is_grat_arp_locked(mac))) {
5864                 return false;
5865             }
5866             break;
5867         }
5868     }
5869
5870     return true;
5871 }
5872
5873 static void
5874 xlate_normal(struct action_xlate_ctx *ctx)
5875 {
5876     struct ofport_dpif *in_port;
5877     struct ofbundle *in_bundle;
5878     struct mac_entry *mac;
5879     uint16_t vlan;
5880     uint16_t vid;
5881
5882     ctx->has_normal = true;
5883
5884     in_bundle = lookup_input_bundle(ctx->ofproto, ctx->flow.in_port,
5885                                   ctx->packet != NULL);
5886     if (!in_bundle) {
5887         return;
5888     }
5889
5890     /* We know 'in_port' exists unless it is "ofpp_none_bundle",
5891      * since lookup_input_bundle() succeeded. */
5892     in_port = get_ofp_port(ctx->ofproto, ctx->flow.in_port);
5893
5894     /* Drop malformed frames. */
5895     if (ctx->flow.dl_type == htons(ETH_TYPE_VLAN) &&
5896         !(ctx->flow.vlan_tci & htons(VLAN_CFI))) {
5897         if (ctx->packet != NULL) {
5898             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5899             VLOG_WARN_RL(&rl, "bridge %s: dropping packet with partial "
5900                          "VLAN tag received on port %s",
5901                          ctx->ofproto->up.name, in_bundle->name);
5902         }
5903         return;
5904     }
5905
5906     /* Drop frames on bundles reserved for mirroring. */
5907     if (in_bundle->mirror_out) {
5908         if (ctx->packet != NULL) {
5909             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
5910             VLOG_WARN_RL(&rl, "bridge %s: dropping packet received on port "
5911                          "%s, which is reserved exclusively for mirroring",
5912                          ctx->ofproto->up.name, in_bundle->name);
5913         }
5914         return;
5915     }
5916
5917     /* Check VLAN. */
5918     vid = vlan_tci_to_vid(ctx->flow.vlan_tci);
5919     if (!input_vid_is_valid(vid, in_bundle, ctx->packet != NULL)) {
5920         return;
5921     }
5922     vlan = input_vid_to_vlan(in_bundle, vid);
5923
5924     /* Check other admissibility requirements. */
5925     if (in_port &&
5926          !is_admissible(ctx->ofproto, &ctx->flow, in_port, vlan, &ctx->tags)) {
5927         return;
5928     }
5929
5930     /* Learn source MAC. */
5931     if (ctx->may_learn) {
5932         update_learning_table(ctx->ofproto, &ctx->flow, vlan, in_bundle);
5933     }
5934
5935     /* Determine output bundle. */
5936     mac = mac_learning_lookup(ctx->ofproto->ml, ctx->flow.dl_dst, vlan,
5937                               &ctx->tags);
5938     if (mac) {
5939         if (mac->port.p != in_bundle) {
5940             output_normal(ctx, mac->port.p, vlan);
5941         }
5942     } else {
5943         struct ofbundle *bundle;
5944
5945         HMAP_FOR_EACH (bundle, hmap_node, &ctx->ofproto->bundles) {
5946             if (bundle != in_bundle
5947                 && ofbundle_includes_vlan(bundle, vlan)
5948                 && bundle->floodable
5949                 && !bundle->mirror_out) {
5950                 output_normal(ctx, bundle, vlan);
5951             }
5952         }
5953         ctx->nf_output_iface = NF_OUT_FLOOD;
5954     }
5955 }
5956 \f
5957 /* Optimized flow revalidation.
5958  *
5959  * It's a difficult problem, in general, to tell which facets need to have
5960  * their actions recalculated whenever the OpenFlow flow table changes.  We
5961  * don't try to solve that general problem: for most kinds of OpenFlow flow
5962  * table changes, we recalculate the actions for every facet.  This is
5963  * relatively expensive, but it's good enough if the OpenFlow flow table
5964  * doesn't change very often.
5965  *
5966  * However, we can expect one particular kind of OpenFlow flow table change to
5967  * happen frequently: changes caused by MAC learning.  To avoid wasting a lot
5968  * of CPU on revalidating every facet whenever MAC learning modifies the flow
5969  * table, we add a special case that applies to flow tables in which every rule
5970  * has the same form (that is, the same wildcards), except that the table is
5971  * also allowed to have a single "catch-all" flow that matches all packets.  We
5972  * optimize this case by tagging all of the facets that resubmit into the table
5973  * and invalidating the same tag whenever a flow changes in that table.  The
5974  * end result is that we revalidate just the facets that need it (and sometimes
5975  * a few more, but not all of the facets or even all of the facets that
5976  * resubmit to the table modified by MAC learning). */
5977
5978 /* Calculates the tag to use for 'flow' and wildcards 'wc' when it is inserted
5979  * into an OpenFlow table with the given 'basis'. */
5980 static tag_type
5981 rule_calculate_tag(const struct flow *flow, const struct flow_wildcards *wc,
5982                    uint32_t secret)
5983 {
5984     if (flow_wildcards_is_catchall(wc)) {
5985         return 0;
5986     } else {
5987         struct flow tag_flow = *flow;
5988         flow_zero_wildcards(&tag_flow, wc);
5989         return tag_create_deterministic(flow_hash(&tag_flow, secret));
5990     }
5991 }
5992
5993 /* Following a change to OpenFlow table 'table_id' in 'ofproto', update the
5994  * taggability of that table.
5995  *
5996  * This function must be called after *each* change to a flow table.  If you
5997  * skip calling it on some changes then the pointer comparisons at the end can
5998  * be invalid if you get unlucky.  For example, if a flow removal causes a
5999  * cls_table to be destroyed and then a flow insertion causes a cls_table with
6000  * different wildcards to be created with the same address, then this function
6001  * will incorrectly skip revalidation. */
6002 static void
6003 table_update_taggable(struct ofproto_dpif *ofproto, uint8_t table_id)
6004 {
6005     struct table_dpif *table = &ofproto->tables[table_id];
6006     const struct oftable *oftable = &ofproto->up.tables[table_id];
6007     struct cls_table *catchall, *other;
6008     struct cls_table *t;
6009
6010     catchall = other = NULL;
6011
6012     switch (hmap_count(&oftable->cls.tables)) {
6013     case 0:
6014         /* We could tag this OpenFlow table but it would make the logic a
6015          * little harder and it's a corner case that doesn't seem worth it
6016          * yet. */
6017         break;
6018
6019     case 1:
6020     case 2:
6021         HMAP_FOR_EACH (t, hmap_node, &oftable->cls.tables) {
6022             if (cls_table_is_catchall(t)) {
6023                 catchall = t;
6024             } else if (!other) {
6025                 other = t;
6026             } else {
6027                 /* Indicate that we can't tag this by setting both tables to
6028                  * NULL.  (We know that 'catchall' is already NULL.) */
6029                 other = NULL;
6030             }
6031         }
6032         break;
6033
6034     default:
6035         /* Can't tag this table. */
6036         break;
6037     }
6038
6039     if (table->catchall_table != catchall || table->other_table != other) {
6040         table->catchall_table = catchall;
6041         table->other_table = other;
6042         ofproto->need_revalidate = true;
6043     }
6044 }
6045
6046 /* Given 'rule' that has changed in some way (either it is a rule being
6047  * inserted, a rule being deleted, or a rule whose actions are being
6048  * modified), marks facets for revalidation to ensure that packets will be
6049  * forwarded correctly according to the new state of the flow table.
6050  *
6051  * This function must be called after *each* change to a flow table.  See
6052  * the comment on table_update_taggable() for more information. */
6053 static void
6054 rule_invalidate(const struct rule_dpif *rule)
6055 {
6056     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
6057
6058     table_update_taggable(ofproto, rule->up.table_id);
6059
6060     if (!ofproto->need_revalidate) {
6061         struct table_dpif *table = &ofproto->tables[rule->up.table_id];
6062
6063         if (table->other_table && rule->tag) {
6064             tag_set_add(&ofproto->revalidate_set, rule->tag);
6065         } else {
6066             ofproto->need_revalidate = true;
6067         }
6068     }
6069 }
6070 \f
6071 static bool
6072 set_frag_handling(struct ofproto *ofproto_,
6073                   enum ofp_config_flags frag_handling)
6074 {
6075     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
6076
6077     if (frag_handling != OFPC_FRAG_REASM) {
6078         ofproto->need_revalidate = true;
6079         return true;
6080     } else {
6081         return false;
6082     }
6083 }
6084
6085 static enum ofperr
6086 packet_out(struct ofproto *ofproto_, struct ofpbuf *packet,
6087            const struct flow *flow,
6088            const union ofp_action *ofp_actions, size_t n_ofp_actions)
6089 {
6090     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
6091     enum ofperr error;
6092
6093     if (flow->in_port >= ofproto->max_ports && flow->in_port < OFPP_MAX) {
6094         return OFPERR_NXBRC_BAD_IN_PORT;
6095     }
6096
6097     error = validate_actions(ofp_actions, n_ofp_actions, flow,
6098                              ofproto->max_ports);
6099     if (!error) {
6100         struct odputil_keybuf keybuf;
6101         struct dpif_flow_stats stats;
6102
6103         struct ofpbuf key;
6104
6105         struct action_xlate_ctx ctx;
6106         uint64_t odp_actions_stub[1024 / 8];
6107         struct ofpbuf odp_actions;
6108
6109         ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
6110         odp_flow_key_from_flow(&key, flow);
6111
6112         dpif_flow_stats_extract(flow, packet, &stats);
6113
6114         action_xlate_ctx_init(&ctx, ofproto, flow, flow->vlan_tci, NULL,
6115                               packet_get_tcp_flags(packet, flow), packet);
6116         ctx.resubmit_stats = &stats;
6117
6118         ofpbuf_use_stub(&odp_actions,
6119                         odp_actions_stub, sizeof odp_actions_stub);
6120         xlate_actions(&ctx, ofp_actions, n_ofp_actions, &odp_actions);
6121         dpif_execute(ofproto->dpif, key.data, key.size,
6122                      odp_actions.data, odp_actions.size, packet);
6123         ofpbuf_uninit(&odp_actions);
6124     }
6125     return error;
6126 }
6127 \f
6128 /* NetFlow. */
6129
6130 static int
6131 set_netflow(struct ofproto *ofproto_,
6132             const struct netflow_options *netflow_options)
6133 {
6134     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
6135
6136     if (netflow_options) {
6137         if (!ofproto->netflow) {
6138             ofproto->netflow = netflow_create();
6139         }
6140         return netflow_set_options(ofproto->netflow, netflow_options);
6141     } else {
6142         netflow_destroy(ofproto->netflow);
6143         ofproto->netflow = NULL;
6144         return 0;
6145     }
6146 }
6147
6148 static void
6149 get_netflow_ids(const struct ofproto *ofproto_,
6150                 uint8_t *engine_type, uint8_t *engine_id)
6151 {
6152     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
6153
6154     dpif_get_netflow_ids(ofproto->dpif, engine_type, engine_id);
6155 }
6156
6157 static void
6158 send_active_timeout(struct ofproto_dpif *ofproto, struct facet *facet)
6159 {
6160     if (!facet_is_controller_flow(facet) &&
6161         netflow_active_timeout_expired(ofproto->netflow, &facet->nf_flow)) {
6162         struct subfacet *subfacet;
6163         struct ofexpired expired;
6164
6165         LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
6166             if (subfacet->installed) {
6167                 struct dpif_flow_stats stats;
6168
6169                 subfacet_install(subfacet, subfacet->actions,
6170                                  subfacet->actions_len, &stats);
6171                 subfacet_update_stats(subfacet, &stats);
6172             }
6173         }
6174
6175         expired.flow = facet->flow;
6176         expired.packet_count = facet->packet_count;
6177         expired.byte_count = facet->byte_count;
6178         expired.used = facet->used;
6179         netflow_expire(ofproto->netflow, &facet->nf_flow, &expired);
6180     }
6181 }
6182
6183 static void
6184 send_netflow_active_timeouts(struct ofproto_dpif *ofproto)
6185 {
6186     struct facet *facet;
6187
6188     HMAP_FOR_EACH (facet, hmap_node, &ofproto->facets) {
6189         send_active_timeout(ofproto, facet);
6190     }
6191 }
6192 \f
6193 static struct ofproto_dpif *
6194 ofproto_dpif_lookup(const char *name)
6195 {
6196     struct ofproto_dpif *ofproto;
6197
6198     HMAP_FOR_EACH_WITH_HASH (ofproto, all_ofproto_dpifs_node,
6199                              hash_string(name, 0), &all_ofproto_dpifs) {
6200         if (!strcmp(ofproto->up.name, name)) {
6201             return ofproto;
6202         }
6203     }
6204     return NULL;
6205 }
6206
6207 static void
6208 ofproto_unixctl_fdb_flush(struct unixctl_conn *conn, int argc,
6209                           const char *argv[], void *aux OVS_UNUSED)
6210 {
6211     struct ofproto_dpif *ofproto;
6212
6213     if (argc > 1) {
6214         ofproto = ofproto_dpif_lookup(argv[1]);
6215         if (!ofproto) {
6216             unixctl_command_reply_error(conn, "no such bridge");
6217             return;
6218         }
6219         mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
6220     } else {
6221         HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
6222             mac_learning_flush(ofproto->ml, &ofproto->revalidate_set);
6223         }
6224     }
6225
6226     unixctl_command_reply(conn, "table successfully flushed");
6227 }
6228
6229 static void
6230 ofproto_unixctl_fdb_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
6231                          const char *argv[], void *aux OVS_UNUSED)
6232 {
6233     struct ds ds = DS_EMPTY_INITIALIZER;
6234     const struct ofproto_dpif *ofproto;
6235     const struct mac_entry *e;
6236
6237     ofproto = ofproto_dpif_lookup(argv[1]);
6238     if (!ofproto) {
6239         unixctl_command_reply_error(conn, "no such bridge");
6240         return;
6241     }
6242
6243     ds_put_cstr(&ds, " port  VLAN  MAC                Age\n");
6244     LIST_FOR_EACH (e, lru_node, &ofproto->ml->lrus) {
6245         struct ofbundle *bundle = e->port.p;
6246         ds_put_format(&ds, "%5d  %4d  "ETH_ADDR_FMT"  %3d\n",
6247                       ofbundle_get_a_port(bundle)->odp_port,
6248                       e->vlan, ETH_ADDR_ARGS(e->mac),
6249                       mac_entry_age(ofproto->ml, e));
6250     }
6251     unixctl_command_reply(conn, ds_cstr(&ds));
6252     ds_destroy(&ds);
6253 }
6254
6255 struct trace_ctx {
6256     struct action_xlate_ctx ctx;
6257     struct flow flow;
6258     struct ds *result;
6259 };
6260
6261 static void
6262 trace_format_rule(struct ds *result, uint8_t table_id, int level,
6263                   const struct rule_dpif *rule)
6264 {
6265     ds_put_char_multiple(result, '\t', level);
6266     if (!rule) {
6267         ds_put_cstr(result, "No match\n");
6268         return;
6269     }
6270
6271     ds_put_format(result, "Rule: table=%"PRIu8" cookie=%#"PRIx64" ",
6272                   table_id, ntohll(rule->up.flow_cookie));
6273     cls_rule_format(&rule->up.cr, result);
6274     ds_put_char(result, '\n');
6275
6276     ds_put_char_multiple(result, '\t', level);
6277     ds_put_cstr(result, "OpenFlow ");
6278     ofp_print_actions(result, rule->up.actions, rule->up.n_actions);
6279     ds_put_char(result, '\n');
6280 }
6281
6282 static void
6283 trace_format_flow(struct ds *result, int level, const char *title,
6284                  struct trace_ctx *trace)
6285 {
6286     ds_put_char_multiple(result, '\t', level);
6287     ds_put_format(result, "%s: ", title);
6288     if (flow_equal(&trace->ctx.flow, &trace->flow)) {
6289         ds_put_cstr(result, "unchanged");
6290     } else {
6291         flow_format(result, &trace->ctx.flow);
6292         trace->flow = trace->ctx.flow;
6293     }
6294     ds_put_char(result, '\n');
6295 }
6296
6297 static void
6298 trace_format_regs(struct ds *result, int level, const char *title,
6299                   struct trace_ctx *trace)
6300 {
6301     size_t i;
6302
6303     ds_put_char_multiple(result, '\t', level);
6304     ds_put_format(result, "%s:", title);
6305     for (i = 0; i < FLOW_N_REGS; i++) {
6306         ds_put_format(result, " reg%zu=0x%"PRIx32, i, trace->flow.regs[i]);
6307     }
6308     ds_put_char(result, '\n');
6309 }
6310
6311 static void
6312 trace_format_odp(struct ds *result, int level, const char *title,
6313                  struct trace_ctx *trace)
6314 {
6315     struct ofpbuf *odp_actions = trace->ctx.odp_actions;
6316
6317     ds_put_char_multiple(result, '\t', level);
6318     ds_put_format(result, "%s: ", title);
6319     format_odp_actions(result, odp_actions->data, odp_actions->size);
6320     ds_put_char(result, '\n');
6321 }
6322
6323 static void
6324 trace_resubmit(struct action_xlate_ctx *ctx, struct rule_dpif *rule)
6325 {
6326     struct trace_ctx *trace = CONTAINER_OF(ctx, struct trace_ctx, ctx);
6327     struct ds *result = trace->result;
6328
6329     ds_put_char(result, '\n');
6330     trace_format_flow(result, ctx->recurse + 1, "Resubmitted flow", trace);
6331     trace_format_regs(result, ctx->recurse + 1, "Resubmitted regs", trace);
6332     trace_format_odp(result,  ctx->recurse + 1, "Resubmitted  odp", trace);
6333     trace_format_rule(result, ctx->table_id, ctx->recurse + 1, rule);
6334 }
6335
6336 static void
6337 ofproto_unixctl_trace(struct unixctl_conn *conn, int argc, const char *argv[],
6338                       void *aux OVS_UNUSED)
6339 {
6340     const char *dpname = argv[1];
6341     struct ofproto_dpif *ofproto;
6342     struct ofpbuf odp_key;
6343     struct ofpbuf *packet;
6344     ovs_be16 initial_tci;
6345     struct ds result;
6346     struct flow flow;
6347     char *s;
6348
6349     packet = NULL;
6350     ofpbuf_init(&odp_key, 0);
6351     ds_init(&result);
6352
6353     ofproto = ofproto_dpif_lookup(dpname);
6354     if (!ofproto) {
6355         unixctl_command_reply_error(conn, "Unknown ofproto (use ofproto/list "
6356                                     "for help)");
6357         goto exit;
6358     }
6359     if (argc == 3 || (argc == 4 && !strcmp(argv[3], "-generate"))) {
6360         /* ofproto/trace dpname flow [-generate] */
6361         const char *flow_s = argv[2];
6362         const char *generate_s = argv[3];
6363         int error;
6364
6365         /* Convert string to datapath key. */
6366         ofpbuf_init(&odp_key, 0);
6367         error = odp_flow_key_from_string(flow_s, NULL, &odp_key);
6368         if (error) {
6369             unixctl_command_reply_error(conn, "Bad flow syntax");
6370             goto exit;
6371         }
6372
6373         /* Convert odp_key to flow. */
6374         error = ofproto_dpif_extract_flow_key(ofproto, odp_key.data,
6375                                               odp_key.size, &flow,
6376                                               &initial_tci, NULL);
6377         if (error == ODP_FIT_ERROR) {
6378             unixctl_command_reply_error(conn, "Invalid flow");
6379             goto exit;
6380         }
6381
6382         /* Generate a packet, if requested. */
6383         if (generate_s) {
6384             packet = ofpbuf_new(0);
6385             flow_compose(packet, &flow);
6386         }
6387     } else if (argc == 6) {
6388         /* ofproto/trace dpname priority tun_id in_port packet */
6389         const char *priority_s = argv[2];
6390         const char *tun_id_s = argv[3];
6391         const char *in_port_s = argv[4];
6392         const char *packet_s = argv[5];
6393         uint16_t in_port = ofp_port_to_odp_port(atoi(in_port_s));
6394         ovs_be64 tun_id = htonll(strtoull(tun_id_s, NULL, 0));
6395         uint32_t priority = atoi(priority_s);
6396         const char *msg;
6397
6398         msg = eth_from_hex(packet_s, &packet);
6399         if (msg) {
6400             unixctl_command_reply_error(conn, msg);
6401             goto exit;
6402         }
6403
6404         ds_put_cstr(&result, "Packet: ");
6405         s = ofp_packet_to_string(packet->data, packet->size);
6406         ds_put_cstr(&result, s);
6407         free(s);
6408
6409         flow_extract(packet, priority, tun_id, in_port, &flow);
6410         initial_tci = flow.vlan_tci;
6411     } else {
6412         unixctl_command_reply_error(conn, "Bad command syntax");
6413         goto exit;
6414     }
6415
6416     ofproto_trace(ofproto, &flow, packet, initial_tci, &result);
6417     unixctl_command_reply(conn, ds_cstr(&result));
6418
6419 exit:
6420     ds_destroy(&result);
6421     ofpbuf_delete(packet);
6422     ofpbuf_uninit(&odp_key);
6423 }
6424
6425 static void
6426 ofproto_trace(struct ofproto_dpif *ofproto, const struct flow *flow,
6427               const struct ofpbuf *packet, ovs_be16 initial_tci,
6428               struct ds *ds)
6429 {
6430     struct rule_dpif *rule;
6431
6432     ds_put_cstr(ds, "Flow: ");
6433     flow_format(ds, flow);
6434     ds_put_char(ds, '\n');
6435
6436     rule = rule_dpif_lookup(ofproto, flow, 0);
6437     trace_format_rule(ds, 0, 0, rule);
6438     if (rule) {
6439         uint64_t odp_actions_stub[1024 / 8];
6440         struct ofpbuf odp_actions;
6441
6442         struct trace_ctx trace;
6443         uint8_t tcp_flags;
6444
6445         tcp_flags = packet ? packet_get_tcp_flags(packet, flow) : 0;
6446         trace.result = ds;
6447         trace.flow = *flow;
6448         ofpbuf_use_stub(&odp_actions,
6449                         odp_actions_stub, sizeof odp_actions_stub);
6450         action_xlate_ctx_init(&trace.ctx, ofproto, flow, initial_tci,
6451                               rule, tcp_flags, packet);
6452         trace.ctx.resubmit_hook = trace_resubmit;
6453         xlate_actions(&trace.ctx, rule->up.actions, rule->up.n_actions,
6454                       &odp_actions);
6455
6456         ds_put_char(ds, '\n');
6457         trace_format_flow(ds, 0, "Final flow", &trace);
6458         ds_put_cstr(ds, "Datapath actions: ");
6459         format_odp_actions(ds, odp_actions.data, odp_actions.size);
6460         ofpbuf_uninit(&odp_actions);
6461
6462         if (!trace.ctx.may_set_up_flow) {
6463             if (packet) {
6464                 ds_put_cstr(ds, "\nThis flow is not cachable.");
6465             } else {
6466                 ds_put_cstr(ds, "\nThe datapath actions are incomplete--"
6467                             "for complete actions, please supply a packet.");
6468             }
6469         }
6470     }
6471 }
6472
6473 static void
6474 ofproto_dpif_clog(struct unixctl_conn *conn OVS_UNUSED, int argc OVS_UNUSED,
6475                   const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
6476 {
6477     clogged = true;
6478     unixctl_command_reply(conn, NULL);
6479 }
6480
6481 static void
6482 ofproto_dpif_unclog(struct unixctl_conn *conn OVS_UNUSED, int argc OVS_UNUSED,
6483                     const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
6484 {
6485     clogged = false;
6486     unixctl_command_reply(conn, NULL);
6487 }
6488
6489 /* Runs a self-check of flow translations in 'ofproto'.  Appends a message to
6490  * 'reply' describing the results. */
6491 static void
6492 ofproto_dpif_self_check__(struct ofproto_dpif *ofproto, struct ds *reply)
6493 {
6494     struct facet *facet;
6495     int errors;
6496
6497     errors = 0;
6498     HMAP_FOR_EACH (facet, hmap_node, &ofproto->facets) {
6499         if (!facet_check_consistency(facet)) {
6500             errors++;
6501         }
6502     }
6503     if (errors) {
6504         ofproto->need_revalidate = true;
6505     }
6506
6507     if (errors) {
6508         ds_put_format(reply, "%s: self-check failed (%d errors)\n",
6509                       ofproto->up.name, errors);
6510     } else {
6511         ds_put_format(reply, "%s: self-check passed\n", ofproto->up.name);
6512     }
6513 }
6514
6515 static void
6516 ofproto_dpif_self_check(struct unixctl_conn *conn,
6517                         int argc, const char *argv[], void *aux OVS_UNUSED)
6518 {
6519     struct ds reply = DS_EMPTY_INITIALIZER;
6520     struct ofproto_dpif *ofproto;
6521
6522     if (argc > 1) {
6523         ofproto = ofproto_dpif_lookup(argv[1]);
6524         if (!ofproto) {
6525             unixctl_command_reply_error(conn, "Unknown ofproto (use "
6526                                         "ofproto/list for help)");
6527             return;
6528         }
6529         ofproto_dpif_self_check__(ofproto, &reply);
6530     } else {
6531         HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
6532             ofproto_dpif_self_check__(ofproto, &reply);
6533         }
6534     }
6535
6536     unixctl_command_reply(conn, ds_cstr(&reply));
6537     ds_destroy(&reply);
6538 }
6539
6540 static void
6541 ofproto_dpif_unixctl_init(void)
6542 {
6543     static bool registered;
6544     if (registered) {
6545         return;
6546     }
6547     registered = true;
6548
6549     unixctl_command_register(
6550         "ofproto/trace",
6551         "bridge {tun_id in_port packet | odp_flow [-generate]}",
6552         2, 5, ofproto_unixctl_trace, NULL);
6553     unixctl_command_register("fdb/flush", "[bridge]", 0, 1,
6554                              ofproto_unixctl_fdb_flush, NULL);
6555     unixctl_command_register("fdb/show", "bridge", 1, 1,
6556                              ofproto_unixctl_fdb_show, NULL);
6557     unixctl_command_register("ofproto/clog", "", 0, 0,
6558                              ofproto_dpif_clog, NULL);
6559     unixctl_command_register("ofproto/unclog", "", 0, 0,
6560                              ofproto_dpif_unclog, NULL);
6561     unixctl_command_register("ofproto/self-check", "[bridge]", 0, 1,
6562                              ofproto_dpif_self_check, NULL);
6563 }
6564 \f
6565 /* Linux VLAN device support (e.g. "eth0.10" for VLAN 10.)
6566  *
6567  * This is deprecated.  It is only for compatibility with broken device drivers
6568  * in old versions of Linux that do not properly support VLANs when VLAN
6569  * devices are not used.  When broken device drivers are no longer in
6570  * widespread use, we will delete these interfaces. */
6571
6572 static int
6573 set_realdev(struct ofport *ofport_, uint16_t realdev_ofp_port, int vid)
6574 {
6575     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport_->ofproto);
6576     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
6577
6578     if (realdev_ofp_port == ofport->realdev_ofp_port
6579         && vid == ofport->vlandev_vid) {
6580         return 0;
6581     }
6582
6583     ofproto->need_revalidate = true;
6584
6585     if (ofport->realdev_ofp_port) {
6586         vsp_remove(ofport);
6587     }
6588     if (realdev_ofp_port && ofport->bundle) {
6589         /* vlandevs are enslaved to their realdevs, so they are not allowed to
6590          * themselves be part of a bundle. */
6591         bundle_set(ofport->up.ofproto, ofport->bundle, NULL);
6592     }
6593
6594     ofport->realdev_ofp_port = realdev_ofp_port;
6595     ofport->vlandev_vid = vid;
6596
6597     if (realdev_ofp_port) {
6598         vsp_add(ofport, realdev_ofp_port, vid);
6599     }
6600
6601     return 0;
6602 }
6603
6604 static uint32_t
6605 hash_realdev_vid(uint16_t realdev_ofp_port, int vid)
6606 {
6607     return hash_2words(realdev_ofp_port, vid);
6608 }
6609
6610 /* Returns the ODP port number of the Linux VLAN device that corresponds to
6611  * 'vlan_tci' on the network device with port number 'realdev_odp_port' in
6612  * 'ofproto'.  For example, given 'realdev_odp_port' of eth0 and 'vlan_tci' 9,
6613  * it would return the port number of eth0.9.
6614  *
6615  * Unless VLAN splinters are enabled for port 'realdev_odp_port', this
6616  * function just returns its 'realdev_odp_port' argument. */
6617 static uint32_t
6618 vsp_realdev_to_vlandev(const struct ofproto_dpif *ofproto,
6619                        uint32_t realdev_odp_port, ovs_be16 vlan_tci)
6620 {
6621     if (!hmap_is_empty(&ofproto->realdev_vid_map)) {
6622         uint16_t realdev_ofp_port = odp_port_to_ofp_port(realdev_odp_port);
6623         int vid = vlan_tci_to_vid(vlan_tci);
6624         const struct vlan_splinter *vsp;
6625
6626         HMAP_FOR_EACH_WITH_HASH (vsp, realdev_vid_node,
6627                                  hash_realdev_vid(realdev_ofp_port, vid),
6628                                  &ofproto->realdev_vid_map) {
6629             if (vsp->realdev_ofp_port == realdev_ofp_port
6630                 && vsp->vid == vid) {
6631                 return ofp_port_to_odp_port(vsp->vlandev_ofp_port);
6632             }
6633         }
6634     }
6635     return realdev_odp_port;
6636 }
6637
6638 static struct vlan_splinter *
6639 vlandev_find(const struct ofproto_dpif *ofproto, uint16_t vlandev_ofp_port)
6640 {
6641     struct vlan_splinter *vsp;
6642
6643     HMAP_FOR_EACH_WITH_HASH (vsp, vlandev_node, hash_int(vlandev_ofp_port, 0),
6644                              &ofproto->vlandev_map) {
6645         if (vsp->vlandev_ofp_port == vlandev_ofp_port) {
6646             return vsp;
6647         }
6648     }
6649
6650     return NULL;
6651 }
6652
6653 /* Returns the OpenFlow port number of the "real" device underlying the Linux
6654  * VLAN device with OpenFlow port number 'vlandev_ofp_port' and stores the
6655  * VLAN VID of the Linux VLAN device in '*vid'.  For example, given
6656  * 'vlandev_ofp_port' of eth0.9, it would return the OpenFlow port number of
6657  * eth0 and store 9 in '*vid'.
6658  *
6659  * Returns 0 and does not modify '*vid' if 'vlandev_ofp_port' is not a Linux
6660  * VLAN device.  Unless VLAN splinters are enabled, this is what this function
6661  * always does.*/
6662 static uint16_t
6663 vsp_vlandev_to_realdev(const struct ofproto_dpif *ofproto,
6664                        uint16_t vlandev_ofp_port, int *vid)
6665 {
6666     if (!hmap_is_empty(&ofproto->vlandev_map)) {
6667         const struct vlan_splinter *vsp;
6668
6669         vsp = vlandev_find(ofproto, vlandev_ofp_port);
6670         if (vsp) {
6671             if (vid) {
6672                 *vid = vsp->vid;
6673             }
6674             return vsp->realdev_ofp_port;
6675         }
6676     }
6677     return 0;
6678 }
6679
6680 static void
6681 vsp_remove(struct ofport_dpif *port)
6682 {
6683     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
6684     struct vlan_splinter *vsp;
6685
6686     vsp = vlandev_find(ofproto, port->up.ofp_port);
6687     if (vsp) {
6688         hmap_remove(&ofproto->vlandev_map, &vsp->vlandev_node);
6689         hmap_remove(&ofproto->realdev_vid_map, &vsp->realdev_vid_node);
6690         free(vsp);
6691
6692         port->realdev_ofp_port = 0;
6693     } else {
6694         VLOG_ERR("missing vlan device record");
6695     }
6696 }
6697
6698 static void
6699 vsp_add(struct ofport_dpif *port, uint16_t realdev_ofp_port, int vid)
6700 {
6701     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
6702
6703     if (!vsp_vlandev_to_realdev(ofproto, port->up.ofp_port, NULL)
6704         && (vsp_realdev_to_vlandev(ofproto, realdev_ofp_port, htons(vid))
6705             == realdev_ofp_port)) {
6706         struct vlan_splinter *vsp;
6707
6708         vsp = xmalloc(sizeof *vsp);
6709         hmap_insert(&ofproto->vlandev_map, &vsp->vlandev_node,
6710                     hash_int(port->up.ofp_port, 0));
6711         hmap_insert(&ofproto->realdev_vid_map, &vsp->realdev_vid_node,
6712                     hash_realdev_vid(realdev_ofp_port, vid));
6713         vsp->realdev_ofp_port = realdev_ofp_port;
6714         vsp->vlandev_ofp_port = port->up.ofp_port;
6715         vsp->vid = vid;
6716
6717         port->realdev_ofp_port = realdev_ofp_port;
6718     } else {
6719         VLOG_ERR("duplicate vlan device record");
6720     }
6721 }
6722 \f
6723 const struct ofproto_class ofproto_dpif_class = {
6724     enumerate_types,
6725     enumerate_names,
6726     del,
6727     alloc,
6728     construct,
6729     destruct,
6730     dealloc,
6731     run,
6732     run_fast,
6733     wait,
6734     flush,
6735     get_features,
6736     get_tables,
6737     port_alloc,
6738     port_construct,
6739     port_destruct,
6740     port_dealloc,
6741     port_modified,
6742     port_reconfigured,
6743     port_query_by_name,
6744     port_add,
6745     port_del,
6746     port_get_stats,
6747     port_dump_start,
6748     port_dump_next,
6749     port_dump_done,
6750     port_poll,
6751     port_poll_wait,
6752     port_is_lacp_current,
6753     NULL,                       /* rule_choose_table */
6754     rule_alloc,
6755     rule_construct,
6756     rule_destruct,
6757     rule_dealloc,
6758     rule_get_stats,
6759     rule_execute,
6760     rule_modify_actions,
6761     set_frag_handling,
6762     packet_out,
6763     set_netflow,
6764     get_netflow_ids,
6765     set_sflow,
6766     set_cfm,
6767     get_cfm_fault,
6768     get_cfm_remote_mpids,
6769     get_cfm_health,
6770     set_stp,
6771     get_stp_status,
6772     set_stp_port,
6773     get_stp_port_status,
6774     set_queues,
6775     bundle_set,
6776     bundle_remove,
6777     mirror_set,
6778     mirror_get_stats,
6779     set_flood_vlans,
6780     is_mirror_output_bundle,
6781     forward_bpdu_changed,
6782     set_mac_idle_time,
6783     set_realdev,
6784 };