ofproto/ofproto-dpif.c

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