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