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         put->mask = NULL;
3465         put->mask_len = 0;
3466         if (want_path == SF_FAST_PATH) {
3467             put->actions = facet->xout.odp_actions.data;
3468             put->actions_len = facet->xout.odp_actions.size;
3469         } else {
3470             compose_slow_path(ofproto, &miss->flow, facet->xout.slow,
3471                               op->slow_stub, sizeof op->slow_stub,
3472                               &put->actions, &put->actions_len);
3473         }
3474         put->stats = NULL;
3475     }
3476 }
3477
3478 /* Handles flow miss 'miss'.  May add any required datapath operations
3479  * to 'ops', incrementing '*n_ops' for each new op. */
3480 static void
3481 handle_flow_miss(struct flow_miss *miss, struct flow_miss_op *ops,
3482                  size_t *n_ops)
3483 {
3484     struct ofproto_dpif *ofproto = miss->ofproto;
3485     struct dpif_flow_stats stats__;
3486     struct dpif_flow_stats *stats = &stats__;
3487     struct ofpbuf *packet;
3488     struct facet *facet;
3489     long long int now;
3490
3491     now = time_msec();
3492     memset(stats, 0, sizeof *stats);
3493     stats->used = now;
3494     LIST_FOR_EACH (packet, list_node, &miss->packets) {
3495         stats->tcp_flags |= packet_get_tcp_flags(packet, &miss->flow);
3496         stats->n_bytes += packet->size;
3497         stats->n_packets++;
3498     }
3499
3500     facet = facet_lookup_valid(ofproto, &miss->flow);
3501     if (!facet) {
3502         struct flow_wildcards wc;
3503         struct rule_dpif *rule;
3504         struct xlate_out xout;
3505         struct xlate_in xin;
3506
3507         flow_wildcards_init_catchall(&wc);
3508         rule = rule_dpif_lookup(ofproto, &miss->flow, &wc);
3509         rule_credit_stats(rule, stats);
3510
3511         xlate_in_init(&xin, ofproto, &miss->flow, rule, stats->tcp_flags,
3512                       NULL);
3513         xin.resubmit_stats = stats;
3514         xin.may_learn = true;
3515         xlate_actions(&xin, &xout);
3516         flow_wildcards_or(&xout.wc, &xout.wc, &wc);
3517
3518         /* There does not exist a bijection between 'struct flow' and datapath
3519          * flow keys with fitness ODP_FIT_TO_LITTLE.  This breaks a fundamental
3520          * assumption used throughout the facet and subfacet handling code.
3521          * Since we have to handle these misses in userspace anyway, we simply
3522          * skip facet creation, avoiding the problem altogether. */
3523         if (miss->key_fitness == ODP_FIT_TOO_LITTLE
3524             || !flow_miss_should_make_facet(miss, &xout.wc)) {
3525             handle_flow_miss_without_facet(rule, &xout, miss, ops, n_ops);
3526             return;
3527         }
3528
3529         facet = facet_create(miss, rule, &xout, stats);
3530         stats = NULL;
3531     }
3532     handle_flow_miss_with_facet(miss, facet, now, stats, ops, n_ops);
3533 }
3534
3535 static struct drop_key *
3536 drop_key_lookup(const struct dpif_backer *backer, const struct nlattr *key,
3537                 size_t key_len)
3538 {
3539     struct drop_key *drop_key;
3540
3541     HMAP_FOR_EACH_WITH_HASH (drop_key, hmap_node, hash_bytes(key, key_len, 0),
3542                              &backer->drop_keys) {
3543         if (drop_key->key_len == key_len
3544             && !memcmp(drop_key->key, key, key_len)) {
3545             return drop_key;
3546         }
3547     }
3548     return NULL;
3549 }
3550
3551 static void
3552 drop_key_clear(struct dpif_backer *backer)
3553 {
3554     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 15);
3555     struct drop_key *drop_key, *next;
3556
3557     HMAP_FOR_EACH_SAFE (drop_key, next, hmap_node, &backer->drop_keys) {
3558         int error;
3559
3560         error = dpif_flow_del(backer->dpif, drop_key->key, drop_key->key_len,
3561                               NULL);
3562         if (error && !VLOG_DROP_WARN(&rl)) {
3563             struct ds ds = DS_EMPTY_INITIALIZER;
3564             odp_flow_key_format(drop_key->key, drop_key->key_len, &ds);
3565             VLOG_WARN("Failed to delete drop key (%s) (%s)", strerror(error),
3566                       ds_cstr(&ds));
3567             ds_destroy(&ds);
3568         }
3569
3570         hmap_remove(&backer->drop_keys, &drop_key->hmap_node);
3571         free(drop_key->key);
3572         free(drop_key);
3573     }
3574 }
3575
3576 /* Given a datpath, packet, and flow metadata ('backer', 'packet', and 'key'
3577  * respectively), populates 'flow' with the result of odp_flow_key_to_flow().
3578  * Optionally, if nonnull, populates 'fitnessp' with the fitness of 'flow' as
3579  * returned by odp_flow_key_to_flow().  Also, optionally populates 'ofproto'
3580  * with the ofproto_dpif, and 'odp_in_port' with the datapath in_port, that
3581  * 'packet' ingressed.
3582  *
3583  * If 'ofproto' is nonnull, requires 'flow''s in_port to exist.  Otherwise sets
3584  * 'flow''s in_port to OFPP_NONE.
3585  *
3586  * This function does post-processing on data returned from
3587  * odp_flow_key_to_flow() to help make VLAN splinters transparent to the rest
3588  * of the upcall processing logic.  In particular, if the extracted in_port is
3589  * a VLAN splinter port, it replaces flow->in_port by the "real" port, sets
3590  * flow->vlan_tci correctly for the VLAN of the VLAN splinter port, and pushes
3591  * a VLAN header onto 'packet' (if it is nonnull).
3592  *
3593  * Similarly, this function also includes some logic to help with tunnels.  It
3594  * may modify 'flow' as necessary to make the tunneling implementation
3595  * transparent to the upcall processing logic.
3596  *
3597  * Returns 0 if successful, ENODEV if the parsed flow has no associated ofport,
3598  * or some other positive errno if there are other problems. */
3599 static int
3600 ofproto_receive(const struct dpif_backer *backer, struct ofpbuf *packet,
3601                 const struct nlattr *key, size_t key_len,
3602                 struct flow *flow, enum odp_key_fitness *fitnessp,
3603                 struct ofproto_dpif **ofproto, uint32_t *odp_in_port)
3604 {
3605     const struct ofport_dpif *port;
3606     enum odp_key_fitness fitness;
3607     int error = ENODEV;
3608
3609     fitness = odp_flow_key_to_flow(key, key_len, flow);
3610     if (fitness == ODP_FIT_ERROR) {
3611         error = EINVAL;
3612         goto exit;
3613     }
3614
3615     if (odp_in_port) {
3616         *odp_in_port = flow->in_port;
3617     }
3618
3619     port = (tnl_port_should_receive(flow)
3620             ? ofport_dpif_cast(tnl_port_receive(flow))
3621             : odp_port_to_ofport(backer, flow->in_port));
3622     flow->in_port = port ? port->up.ofp_port : OFPP_NONE;
3623     if (!port) {
3624         goto exit;
3625     }
3626
3627     /* XXX: Since the tunnel module is not scoped per backer, for a tunnel port
3628      * it's theoretically possible that we'll receive an ofport belonging to an
3629      * entirely different datapath.  In practice, this can't happen because no
3630      * platforms has two separate datapaths which each support tunneling. */
3631     ovs_assert(ofproto_dpif_cast(port->up.ofproto)->backer == backer);
3632
3633     if (vsp_adjust_flow(ofproto_dpif_cast(port->up.ofproto), flow)) {
3634         if (packet) {
3635             /* Make the packet resemble the flow, so that it gets sent to
3636              * an OpenFlow controller properly, so that it looks correct
3637              * for sFlow, and so that flow_extract() will get the correct
3638              * vlan_tci if it is called on 'packet'.
3639              *
3640              * The allocated space inside 'packet' probably also contains
3641              * 'key', that is, both 'packet' and 'key' are probably part of
3642              * a struct dpif_upcall (see the large comment on that
3643              * structure definition), so pushing data on 'packet' is in
3644              * general not a good idea since it could overwrite 'key' or
3645              * free it as a side effect.  However, it's OK in this special
3646              * case because we know that 'packet' is inside a Netlink
3647              * attribute: pushing 4 bytes will just overwrite the 4-byte
3648              * "struct nlattr", which is fine since we don't need that
3649              * header anymore. */
3650             eth_push_vlan(packet, flow->vlan_tci);
3651         }
3652         /* We can't reproduce 'key' from 'flow'. */
3653         fitness = fitness == ODP_FIT_PERFECT ? ODP_FIT_TOO_MUCH : fitness;
3654     }
3655     error = 0;
3656
3657     if (ofproto) {
3658         *ofproto = ofproto_dpif_cast(port->up.ofproto);
3659     }
3660
3661 exit:
3662     if (fitnessp) {
3663         *fitnessp = fitness;
3664     }
3665     return error;
3666 }
3667
3668 static void
3669 handle_miss_upcalls(struct dpif_backer *backer, struct dpif_upcall *upcalls,
3670                     size_t n_upcalls)
3671 {
3672     struct dpif_upcall *upcall;
3673     struct flow_miss *miss;
3674     struct flow_miss misses[FLOW_MISS_MAX_BATCH];
3675     struct flow_miss_op flow_miss_ops[FLOW_MISS_MAX_BATCH * 2];
3676     struct dpif_op *dpif_ops[FLOW_MISS_MAX_BATCH * 2];
3677     struct hmap todo;
3678     int n_misses;
3679     size_t n_ops;
3680     size_t i;
3681
3682     if (!n_upcalls) {
3683         return;
3684     }
3685
3686     /* Construct the to-do list.
3687      *
3688      * This just amounts to extracting the flow from each packet and sticking
3689      * the packets that have the same flow in the same "flow_miss" structure so
3690      * that we can process them together. */
3691     hmap_init(&todo);
3692     n_misses = 0;
3693     for (upcall = upcalls; upcall < &upcalls[n_upcalls]; upcall++) {
3694         struct flow_miss *miss = &misses[n_misses];
3695         struct flow_miss *existing_miss;
3696         struct ofproto_dpif *ofproto;
3697         uint32_t odp_in_port;
3698         struct flow flow;
3699         uint32_t hash;
3700         int error;
3701
3702         error = ofproto_receive(backer, upcall->packet, upcall->key,
3703                                 upcall->key_len, &flow, &miss->key_fitness,
3704                                 &ofproto, &odp_in_port);
3705         if (error == ENODEV) {
3706             struct drop_key *drop_key;
3707
3708             /* Received packet on datapath port for which we couldn't
3709              * associate an ofproto.  This can happen if a port is removed
3710              * while traffic is being received.  Print a rate-limited message
3711              * in case it happens frequently.  Install a drop flow so
3712              * that future packets of the flow are inexpensively dropped
3713              * in the kernel. */
3714             VLOG_INFO_RL(&rl, "received packet on unassociated datapath port "
3715                               "%"PRIu32, odp_in_port);
3716
3717             drop_key = drop_key_lookup(backer, upcall->key, upcall->key_len);
3718             if (!drop_key) {
3719                 drop_key = xmalloc(sizeof *drop_key);
3720                 drop_key->key = xmemdup(upcall->key, upcall->key_len);
3721                 drop_key->key_len = upcall->key_len;
3722
3723                 hmap_insert(&backer->drop_keys, &drop_key->hmap_node,
3724                             hash_bytes(drop_key->key, drop_key->key_len, 0));
3725                 dpif_flow_put(backer->dpif, DPIF_FP_CREATE | DPIF_FP_MODIFY,
3726                               drop_key->key, drop_key->key_len,
3727                               NULL, 0, NULL, 0, NULL);
3728             }
3729             continue;
3730         }
3731         if (error) {
3732             continue;
3733         }
3734
3735         ofproto->n_missed++;
3736         flow_extract(upcall->packet, flow.skb_priority, flow.skb_mark,
3737                      &flow.tunnel, flow.in_port, &miss->flow);
3738
3739         /* Add other packets to a to-do list. */
3740         hash = flow_hash(&miss->flow, 0);
3741         existing_miss = flow_miss_find(&todo, ofproto, &miss->flow, hash);
3742         if (!existing_miss) {
3743             hmap_insert(&todo, &miss->hmap_node, hash);
3744             miss->ofproto = ofproto;
3745             miss->key = upcall->key;
3746             miss->key_len = upcall->key_len;
3747             miss->upcall_type = upcall->type;
3748             list_init(&miss->packets);
3749
3750             n_misses++;
3751         } else {
3752             miss = existing_miss;
3753         }
3754         list_push_back(&miss->packets, &upcall->packet->list_node);
3755     }
3756
3757     /* Process each element in the to-do list, constructing the set of
3758      * operations to batch. */
3759     n_ops = 0;
3760     HMAP_FOR_EACH (miss, hmap_node, &todo) {
3761         handle_flow_miss(miss, flow_miss_ops, &n_ops);
3762     }
3763     ovs_assert(n_ops <= ARRAY_SIZE(flow_miss_ops));
3764
3765     /* Execute batch. */
3766     for (i = 0; i < n_ops; i++) {
3767         dpif_ops[i] = &flow_miss_ops[i].dpif_op;
3768     }
3769     dpif_operate(backer->dpif, dpif_ops, n_ops);
3770
3771     /* Free memory. */
3772     for (i = 0; i < n_ops; i++) {
3773         if (flow_miss_ops[i].xout_garbage) {
3774             xlate_out_uninit(&flow_miss_ops[i].xout);
3775         }
3776     }
3777     hmap_destroy(&todo);
3778 }
3779
3780 static enum { SFLOW_UPCALL, MISS_UPCALL, BAD_UPCALL, FLOW_SAMPLE_UPCALL,
3781               IPFIX_UPCALL }
3782 classify_upcall(const struct dpif_upcall *upcall)
3783 {
3784     size_t userdata_len;
3785     union user_action_cookie cookie;
3786
3787     /* First look at the upcall type. */
3788     switch (upcall->type) {
3789     case DPIF_UC_ACTION:
3790         break;
3791
3792     case DPIF_UC_MISS:
3793         return MISS_UPCALL;
3794
3795     case DPIF_N_UC_TYPES:
3796     default:
3797         VLOG_WARN_RL(&rl, "upcall has unexpected type %"PRIu32, upcall->type);
3798         return BAD_UPCALL;
3799     }
3800
3801     /* "action" upcalls need a closer look. */
3802     if (!upcall->userdata) {
3803         VLOG_WARN_RL(&rl, "action upcall missing cookie");
3804         return BAD_UPCALL;
3805     }
3806     userdata_len = nl_attr_get_size(upcall->userdata);
3807     if (userdata_len < sizeof cookie.type
3808         || userdata_len > sizeof cookie) {
3809         VLOG_WARN_RL(&rl, "action upcall cookie has unexpected size %zu",
3810                      userdata_len);
3811         return BAD_UPCALL;
3812     }
3813     memset(&cookie, 0, sizeof cookie);
3814     memcpy(&cookie, nl_attr_get(upcall->userdata), userdata_len);
3815     if (userdata_len == sizeof cookie.sflow
3816         && cookie.type == USER_ACTION_COOKIE_SFLOW) {
3817         return SFLOW_UPCALL;
3818     } else if (userdata_len == sizeof cookie.slow_path
3819                && cookie.type == USER_ACTION_COOKIE_SLOW_PATH) {
3820         return MISS_UPCALL;
3821     } else if (userdata_len == sizeof cookie.flow_sample
3822                && cookie.type == USER_ACTION_COOKIE_FLOW_SAMPLE) {
3823         return FLOW_SAMPLE_UPCALL;
3824     } else if (userdata_len == sizeof cookie.ipfix
3825                && cookie.type == USER_ACTION_COOKIE_IPFIX) {
3826         return IPFIX_UPCALL;
3827     } else {
3828         VLOG_WARN_RL(&rl, "invalid user cookie of type %"PRIu16
3829                      " and size %zu", cookie.type, userdata_len);
3830         return BAD_UPCALL;
3831     }
3832 }
3833
3834 static void
3835 handle_sflow_upcall(struct dpif_backer *backer,
3836                     const struct dpif_upcall *upcall)
3837 {
3838     struct ofproto_dpif *ofproto;
3839     union user_action_cookie cookie;
3840     struct flow flow;
3841     uint32_t odp_in_port;
3842
3843     if (ofproto_receive(backer, upcall->packet, upcall->key, upcall->key_len,
3844                         &flow, NULL, &ofproto, &odp_in_port)
3845         || !ofproto->sflow) {
3846         return;
3847     }
3848
3849     memset(&cookie, 0, sizeof cookie);
3850     memcpy(&cookie, nl_attr_get(upcall->userdata), sizeof cookie.sflow);
3851     dpif_sflow_received(ofproto->sflow, upcall->packet, &flow,
3852                         odp_in_port, &cookie);
3853 }
3854
3855 static void
3856 handle_flow_sample_upcall(struct dpif_backer *backer,
3857                           const struct dpif_upcall *upcall)
3858 {
3859     struct ofproto_dpif *ofproto;
3860     union user_action_cookie cookie;
3861     struct flow flow;
3862
3863     if (ofproto_receive(backer, upcall->packet, upcall->key, upcall->key_len,
3864                         &flow, NULL, &ofproto, NULL)
3865         || !ofproto->ipfix) {
3866         return;
3867     }
3868
3869     memset(&cookie, 0, sizeof cookie);
3870     memcpy(&cookie, nl_attr_get(upcall->userdata), sizeof cookie.flow_sample);
3871
3872     /* The flow reflects exactly the contents of the packet.  Sample
3873      * the packet using it. */
3874     dpif_ipfix_flow_sample(ofproto->ipfix, upcall->packet, &flow,
3875                            cookie.flow_sample.collector_set_id,
3876                            cookie.flow_sample.probability,
3877                            cookie.flow_sample.obs_domain_id,
3878                            cookie.flow_sample.obs_point_id);
3879 }
3880
3881 static void
3882 handle_ipfix_upcall(struct dpif_backer *backer,
3883                     const struct dpif_upcall *upcall)
3884 {
3885     struct ofproto_dpif *ofproto;
3886     struct flow flow;
3887
3888     if (ofproto_receive(backer, upcall->packet, upcall->key, upcall->key_len,
3889                         &flow, NULL, &ofproto, NULL)
3890         || !ofproto->ipfix) {
3891         return;
3892     }
3893
3894     /* The flow reflects exactly the contents of the packet.  Sample
3895      * the packet using it. */
3896     dpif_ipfix_bridge_sample(ofproto->ipfix, upcall->packet, &flow);
3897 }
3898
3899 static int
3900 handle_upcalls(struct dpif_backer *backer, unsigned int max_batch)
3901 {
3902     struct dpif_upcall misses[FLOW_MISS_MAX_BATCH];
3903     struct ofpbuf miss_bufs[FLOW_MISS_MAX_BATCH];
3904     uint64_t miss_buf_stubs[FLOW_MISS_MAX_BATCH][4096 / 8];
3905     int n_processed;
3906     int n_misses;
3907     int i;
3908
3909     ovs_assert(max_batch <= FLOW_MISS_MAX_BATCH);
3910
3911     n_misses = 0;
3912     for (n_processed = 0; n_processed < max_batch; n_processed++) {
3913         struct dpif_upcall *upcall = &misses[n_misses];
3914         struct ofpbuf *buf = &miss_bufs[n_misses];
3915         int error;
3916
3917         ofpbuf_use_stub(buf, miss_buf_stubs[n_misses],
3918                         sizeof miss_buf_stubs[n_misses]);
3919         error = dpif_recv(backer->dpif, upcall, buf);
3920         if (error) {
3921             ofpbuf_uninit(buf);
3922             break;
3923         }
3924
3925         switch (classify_upcall(upcall)) {
3926         case MISS_UPCALL:
3927             /* Handle it later. */
3928             n_misses++;
3929             break;
3930
3931         case SFLOW_UPCALL:
3932             handle_sflow_upcall(backer, upcall);
3933             ofpbuf_uninit(buf);
3934             break;
3935
3936         case FLOW_SAMPLE_UPCALL:
3937             handle_flow_sample_upcall(backer, upcall);
3938             ofpbuf_uninit(buf);
3939             break;
3940
3941         case IPFIX_UPCALL:
3942             handle_ipfix_upcall(backer, upcall);
3943             ofpbuf_uninit(buf);
3944             break;
3945
3946         case BAD_UPCALL:
3947             ofpbuf_uninit(buf);
3948             break;
3949         }
3950     }
3951
3952     /* Handle deferred MISS_UPCALL processing. */
3953     handle_miss_upcalls(backer, misses, n_misses);
3954     for (i = 0; i < n_misses; i++) {
3955         ofpbuf_uninit(&miss_bufs[i]);
3956     }
3957
3958     return n_processed;
3959 }
3960 \f
3961 /* Flow expiration. */
3962
3963 static int subfacet_max_idle(const struct dpif_backer *);
3964 static void update_stats(struct dpif_backer *);
3965 static void rule_expire(struct rule_dpif *);
3966 static void expire_subfacets(struct dpif_backer *, int dp_max_idle);
3967
3968 /* This function is called periodically by run().  Its job is to collect
3969  * updates for the flows that have been installed into the datapath, most
3970  * importantly when they last were used, and then use that information to
3971  * expire flows that have not been used recently.
3972  *
3973  * Returns the number of milliseconds after which it should be called again. */
3974 static int
3975 expire(struct dpif_backer *backer)
3976 {
3977     struct ofproto_dpif *ofproto;
3978     size_t n_subfacets;
3979     int max_idle;
3980
3981     /* Periodically clear out the drop keys in an effort to keep them
3982      * relatively few. */
3983     drop_key_clear(backer);
3984
3985     /* Update stats for each flow in the backer. */
3986     update_stats(backer);
3987
3988     n_subfacets = hmap_count(&backer->subfacets);
3989     if (n_subfacets) {
3990         struct subfacet *subfacet;
3991         long long int total, now;
3992
3993         total = 0;
3994         now = time_msec();
3995         HMAP_FOR_EACH (subfacet, hmap_node, &backer->subfacets) {
3996             total += now - subfacet->created;
3997         }
3998         backer->avg_subfacet_life += total / n_subfacets;
3999     }
4000     backer->avg_subfacet_life /= 2;
4001
4002     backer->avg_n_subfacet += n_subfacets;
4003     backer->avg_n_subfacet /= 2;
4004
4005     backer->max_n_subfacet = MAX(backer->max_n_subfacet, n_subfacets);
4006
4007     max_idle = subfacet_max_idle(backer);
4008     expire_subfacets(backer, max_idle);
4009
4010     HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
4011         struct rule *rule, *next_rule;
4012
4013         if (ofproto->backer != backer) {
4014             continue;
4015         }
4016
4017         /* Expire OpenFlow flows whose idle_timeout or hard_timeout
4018          * has passed. */
4019         LIST_FOR_EACH_SAFE (rule, next_rule, expirable,
4020                             &ofproto->up.expirable) {
4021             rule_expire(rule_dpif_cast(rule));
4022         }
4023
4024         /* All outstanding data in existing flows has been accounted, so it's a
4025          * good time to do bond rebalancing. */
4026         if (ofproto->has_bonded_bundles) {
4027             struct ofbundle *bundle;
4028
4029             HMAP_FOR_EACH (bundle, hmap_node, &ofproto->bundles) {
4030                 if (bundle->bond) {
4031                     bond_rebalance(bundle->bond, &backer->revalidate_set);
4032                 }
4033             }
4034         }
4035     }
4036
4037     return MIN(max_idle, 1000);
4038 }
4039
4040 /* Updates flow table statistics given that the datapath just reported 'stats'
4041  * as 'subfacet''s statistics. */
4042 static void
4043 update_subfacet_stats(struct subfacet *subfacet,
4044                       const struct dpif_flow_stats *stats)
4045 {
4046     struct facet *facet = subfacet->facet;
4047     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4048     struct dpif_flow_stats diff;
4049
4050     diff.tcp_flags = stats->tcp_flags;
4051     diff.used = stats->used;
4052
4053     if (stats->n_packets >= subfacet->dp_packet_count) {
4054         diff.n_packets = stats->n_packets - subfacet->dp_packet_count;
4055     } else {
4056         VLOG_WARN_RL(&rl, "unexpected packet count from the datapath");
4057         diff.n_packets = 0;
4058     }
4059
4060     if (stats->n_bytes >= subfacet->dp_byte_count) {
4061         diff.n_bytes = stats->n_bytes - subfacet->dp_byte_count;
4062     } else {
4063         VLOG_WARN_RL(&rl, "unexpected byte count from datapath");
4064         diff.n_bytes = 0;
4065     }
4066
4067     ofproto->n_hit += diff.n_packets;
4068     subfacet->dp_packet_count = stats->n_packets;
4069     subfacet->dp_byte_count = stats->n_bytes;
4070     subfacet_update_stats(subfacet, &diff);
4071
4072     if (facet->accounted_bytes < facet->byte_count) {
4073         facet_learn(facet);
4074         facet_account(facet);
4075         facet->accounted_bytes = facet->byte_count;
4076     }
4077 }
4078
4079 /* 'key' with length 'key_len' bytes is a flow in 'dpif' that we know nothing
4080  * about, or a flow that shouldn't be installed but was anyway.  Delete it. */
4081 static void
4082 delete_unexpected_flow(struct dpif_backer *backer,
4083                        const struct nlattr *key, size_t key_len)
4084 {
4085     if (!VLOG_DROP_WARN(&rl)) {
4086         struct ds s;
4087
4088         ds_init(&s);
4089         odp_flow_key_format(key, key_len, &s);
4090         VLOG_WARN("unexpected flow: %s", ds_cstr(&s));
4091         ds_destroy(&s);
4092     }
4093
4094     COVERAGE_INC(facet_unexpected);
4095     dpif_flow_del(backer->dpif, key, key_len, NULL);
4096 }
4097
4098 /* Update 'packet_count', 'byte_count', and 'used' members of installed facets.
4099  *
4100  * This function also pushes statistics updates to rules which each facet
4101  * resubmits into.  Generally these statistics will be accurate.  However, if a
4102  * facet changes the rule it resubmits into at some time in between
4103  * update_stats() runs, it is possible that statistics accrued to the
4104  * old rule will be incorrectly attributed to the new rule.  This could be
4105  * avoided by calling update_stats() whenever rules are created or
4106  * deleted.  However, the performance impact of making so many calls to the
4107  * datapath do not justify the benefit of having perfectly accurate statistics.
4108  *
4109  * In addition, this function maintains per ofproto flow hit counts. The patch
4110  * port is not treated specially. e.g. A packet ingress from br0 patched into
4111  * br1 will increase the hit count of br0 by 1, however, does not affect
4112  * the hit or miss counts of br1.
4113  */
4114 static void
4115 update_stats(struct dpif_backer *backer)
4116 {
4117     const struct dpif_flow_stats *stats;
4118     struct dpif_flow_dump dump;
4119     const struct nlattr *key;
4120     size_t key_len;
4121
4122     dpif_flow_dump_start(&dump, backer->dpif);
4123     while (dpif_flow_dump_next(&dump, &key, &key_len,
4124                                NULL, NULL, NULL, NULL, &stats)) {
4125         struct subfacet *subfacet;
4126         uint32_t key_hash;
4127
4128         key_hash = odp_flow_key_hash(key, key_len);
4129         subfacet = subfacet_find(backer, key, key_len, key_hash);
4130         switch (subfacet ? subfacet->path : SF_NOT_INSTALLED) {
4131         case SF_FAST_PATH:
4132             update_subfacet_stats(subfacet, stats);
4133             break;
4134
4135         case SF_SLOW_PATH:
4136             /* Stats are updated per-packet. */
4137             break;
4138
4139         case SF_NOT_INSTALLED:
4140         default:
4141             delete_unexpected_flow(backer, key, key_len);
4142             break;
4143         }
4144         run_fast_rl();
4145     }
4146     dpif_flow_dump_done(&dump);
4147
4148     update_moving_averages(backer);
4149 }
4150
4151 /* Calculates and returns the number of milliseconds of idle time after which
4152  * subfacets should expire from the datapath.  When a subfacet expires, we fold
4153  * its statistics into its facet, and when a facet's last subfacet expires, we
4154  * fold its statistic into its rule. */
4155 static int
4156 subfacet_max_idle(const struct dpif_backer *backer)
4157 {
4158     /*
4159      * Idle time histogram.
4160      *
4161      * Most of the time a switch has a relatively small number of subfacets.
4162      * When this is the case we might as well keep statistics for all of them
4163      * in userspace and to cache them in the kernel datapath for performance as
4164      * well.
4165      *
4166      * As the number of subfacets increases, the memory required to maintain
4167      * statistics about them in userspace and in the kernel becomes
4168      * significant.  However, with a large number of subfacets it is likely
4169      * that only a few of them are "heavy hitters" that consume a large amount
4170      * of bandwidth.  At this point, only heavy hitters are worth caching in
4171      * the kernel and maintaining in userspaces; other subfacets we can
4172      * discard.
4173      *
4174      * The technique used to compute the idle time is to build a histogram with
4175      * N_BUCKETS buckets whose width is BUCKET_WIDTH msecs each.  Each subfacet
4176      * that is installed in the kernel gets dropped in the appropriate bucket.
4177      * After the histogram has been built, we compute the cutoff so that only
4178      * the most-recently-used 1% of subfacets (but at least
4179      * flow_eviction_threshold flows) are kept cached.  At least
4180      * the most-recently-used bucket of subfacets is kept, so actually an
4181      * arbitrary number of subfacets can be kept in any given expiration run
4182      * (though the next run will delete most of those unless they receive
4183      * additional data).
4184      *
4185      * This requires a second pass through the subfacets, in addition to the
4186      * pass made by update_stats(), because the former function never looks at
4187      * uninstallable subfacets.
4188      */
4189     enum { BUCKET_WIDTH = ROUND_UP(100, TIME_UPDATE_INTERVAL) };
4190     enum { N_BUCKETS = 5000 / BUCKET_WIDTH };
4191     int buckets[N_BUCKETS] = { 0 };
4192     int total, subtotal, bucket;
4193     struct subfacet *subfacet;
4194     long long int now;
4195     int i;
4196
4197     total = hmap_count(&backer->subfacets);
4198     if (total <= flow_eviction_threshold) {
4199         return N_BUCKETS * BUCKET_WIDTH;
4200     }
4201
4202     /* Build histogram. */
4203     now = time_msec();
4204     HMAP_FOR_EACH (subfacet, hmap_node, &backer->subfacets) {
4205         long long int idle = now - subfacet->used;
4206         int bucket = (idle <= 0 ? 0
4207                       : idle >= BUCKET_WIDTH * N_BUCKETS ? N_BUCKETS - 1
4208                       : (unsigned int) idle / BUCKET_WIDTH);
4209         buckets[bucket]++;
4210     }
4211
4212     /* Find the first bucket whose flows should be expired. */
4213     subtotal = bucket = 0;
4214     do {
4215         subtotal += buckets[bucket++];
4216     } while (bucket < N_BUCKETS &&
4217              subtotal < MAX(flow_eviction_threshold, total / 100));
4218
4219     if (VLOG_IS_DBG_ENABLED()) {
4220         struct ds s;
4221
4222         ds_init(&s);
4223         ds_put_cstr(&s, "keep");
4224         for (i = 0; i < N_BUCKETS; i++) {
4225             if (i == bucket) {
4226                 ds_put_cstr(&s, ", drop");
4227             }
4228             if (buckets[i]) {
4229                 ds_put_format(&s, " %d:%d", i * BUCKET_WIDTH, buckets[i]);
4230             }
4231         }
4232         VLOG_INFO("%s (msec:count)", ds_cstr(&s));
4233         ds_destroy(&s);
4234     }
4235
4236     return bucket * BUCKET_WIDTH;
4237 }
4238
4239 static void
4240 expire_subfacets(struct dpif_backer *backer, int dp_max_idle)
4241 {
4242     /* Cutoff time for most flows. */
4243     long long int normal_cutoff = time_msec() - dp_max_idle;
4244
4245     /* We really want to keep flows for special protocols around, so use a more
4246      * conservative cutoff. */
4247     long long int special_cutoff = time_msec() - 10000;
4248
4249     struct subfacet *subfacet, *next_subfacet;
4250     struct subfacet *batch[SUBFACET_DESTROY_MAX_BATCH];
4251     int n_batch;
4252
4253     n_batch = 0;
4254     HMAP_FOR_EACH_SAFE (subfacet, next_subfacet, hmap_node,
4255                         &backer->subfacets) {
4256         long long int cutoff;
4257
4258         cutoff = (subfacet->facet->xout.slow & (SLOW_CFM | SLOW_BFD | SLOW_LACP
4259                                                 | SLOW_STP)
4260                   ? special_cutoff
4261                   : normal_cutoff);
4262         if (subfacet->used < cutoff) {
4263             if (subfacet->path != SF_NOT_INSTALLED) {
4264                 batch[n_batch++] = subfacet;
4265                 if (n_batch >= SUBFACET_DESTROY_MAX_BATCH) {
4266                     subfacet_destroy_batch(backer, batch, n_batch);
4267                     n_batch = 0;
4268                 }
4269             } else {
4270                 subfacet_destroy(subfacet);
4271             }
4272         }
4273     }
4274
4275     if (n_batch > 0) {
4276         subfacet_destroy_batch(backer, batch, n_batch);
4277     }
4278 }
4279
4280 /* If 'rule' is an OpenFlow rule, that has expired according to OpenFlow rules,
4281  * then delete it entirely. */
4282 static void
4283 rule_expire(struct rule_dpif *rule)
4284 {
4285     struct facet *facet, *next_facet;
4286     long long int now;
4287     uint8_t reason;
4288
4289     if (rule->up.pending) {
4290         /* We'll have to expire it later. */
4291         return;
4292     }
4293
4294     /* Has 'rule' expired? */
4295     now = time_msec();
4296     if (rule->up.hard_timeout
4297         && now > rule->up.modified + rule->up.hard_timeout * 1000) {
4298         reason = OFPRR_HARD_TIMEOUT;
4299     } else if (rule->up.idle_timeout
4300                && now > rule->up.used + rule->up.idle_timeout * 1000) {
4301         reason = OFPRR_IDLE_TIMEOUT;
4302     } else {
4303         return;
4304     }
4305
4306     COVERAGE_INC(ofproto_dpif_expired);
4307
4308     /* Update stats.  (This is a no-op if the rule expired due to an idle
4309      * timeout, because that only happens when the rule has no facets left.) */
4310     LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
4311         facet_remove(facet);
4312     }
4313
4314     /* Get rid of the rule. */
4315     ofproto_rule_expire(&rule->up, reason);
4316 }
4317 \f
4318 /* Facets. */
4319
4320 /* Creates and returns a new facet based on 'miss'.
4321  *
4322  * The caller must already have determined that no facet with an identical
4323  * 'miss->flow' exists in 'miss->ofproto'.
4324  *
4325  * 'rule' and 'xout' must have been created based on 'miss'.
4326  *
4327  * 'facet'' statistics are initialized based on 'stats'.
4328  *
4329  * The facet will initially have no subfacets.  The caller should create (at
4330  * least) one subfacet with subfacet_create(). */
4331 static struct facet *
4332 facet_create(const struct flow_miss *miss, struct rule_dpif *rule,
4333              struct xlate_out *xout, struct dpif_flow_stats *stats)
4334 {
4335     struct ofproto_dpif *ofproto = miss->ofproto;
4336     struct facet *facet;
4337     struct match match;
4338
4339     facet = xzalloc(sizeof *facet);
4340     facet->packet_count = facet->prev_packet_count = stats->n_packets;
4341     facet->byte_count = facet->prev_byte_count = stats->n_bytes;
4342     facet->tcp_flags = stats->tcp_flags;
4343     facet->used = stats->used;
4344     facet->flow = miss->flow;
4345     facet->learn_rl = time_msec() + 500;
4346     facet->rule = rule;
4347
4348     list_push_back(&facet->rule->facets, &facet->list_node);
4349     list_init(&facet->subfacets);
4350     netflow_flow_init(&facet->nf_flow);
4351     netflow_flow_update_time(ofproto->netflow, &facet->nf_flow, facet->used);
4352
4353     xlate_out_copy(&facet->xout, xout);
4354
4355     match_init(&match, &facet->flow, &facet->xout.wc);
4356     cls_rule_init(&facet->cr, &match, OFP_DEFAULT_PRIORITY);
4357     classifier_insert(&ofproto->facets, &facet->cr);
4358
4359     facet->nf_flow.output_iface = facet->xout.nf_output_iface;
4360
4361     return facet;
4362 }
4363
4364 static void
4365 facet_free(struct facet *facet)
4366 {
4367     if (facet) {
4368         xlate_out_uninit(&facet->xout);
4369         free(facet);
4370     }
4371 }
4372
4373 /* Executes, within 'ofproto', the 'n_actions' actions in 'actions' on
4374  * 'packet', which arrived on 'in_port'. */
4375 static bool
4376 execute_odp_actions(struct ofproto_dpif *ofproto, const struct flow *flow,
4377                     const struct nlattr *odp_actions, size_t actions_len,
4378                     struct ofpbuf *packet)
4379 {
4380     struct odputil_keybuf keybuf;
4381     struct ofpbuf key;
4382     int error;
4383
4384     ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
4385     odp_flow_key_from_flow(&key, flow,
4386                            ofp_port_to_odp_port(ofproto, flow->in_port));
4387
4388     error = dpif_execute(ofproto->backer->dpif, key.data, key.size,
4389                          odp_actions, actions_len, packet);
4390     return !error;
4391 }
4392
4393 /* Remove 'facet' from its ofproto and free up the associated memory:
4394  *
4395  *   - If 'facet' was installed in the datapath, uninstalls it and updates its
4396  *     rule's statistics, via subfacet_uninstall().
4397  *
4398  *   - Removes 'facet' from its rule and from ofproto->facets.
4399  */
4400 static void
4401 facet_remove(struct facet *facet)
4402 {
4403     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4404     struct subfacet *subfacet, *next_subfacet;
4405
4406     ovs_assert(!list_is_empty(&facet->subfacets));
4407
4408     /* First uninstall all of the subfacets to get final statistics. */
4409     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
4410         subfacet_uninstall(subfacet);
4411     }
4412
4413     /* Flush the final stats to the rule.
4414      *
4415      * This might require us to have at least one subfacet around so that we
4416      * can use its actions for accounting in facet_account(), which is why we
4417      * have uninstalled but not yet destroyed the subfacets. */
4418     facet_flush_stats(facet);
4419
4420     /* Now we're really all done so destroy everything. */
4421     LIST_FOR_EACH_SAFE (subfacet, next_subfacet, list_node,
4422                         &facet->subfacets) {
4423         subfacet_destroy__(subfacet);
4424     }
4425     classifier_remove(&ofproto->facets, &facet->cr);
4426     cls_rule_destroy(&facet->cr);
4427     list_remove(&facet->list_node);
4428     facet_free(facet);
4429 }
4430
4431 /* Feed information from 'facet' back into the learning table to keep it in
4432  * sync with what is actually flowing through the datapath. */
4433 static void
4434 facet_learn(struct facet *facet)
4435 {
4436     long long int now = time_msec();
4437
4438     if (!facet->xout.has_fin_timeout && now < facet->learn_rl) {
4439         return;
4440     }
4441
4442     facet->learn_rl = now + 500;
4443
4444     if (!facet->xout.has_learn
4445         && !facet->xout.has_normal
4446         && (!facet->xout.has_fin_timeout
4447             || !(facet->tcp_flags & (TCP_FIN | TCP_RST)))) {
4448         return;
4449     }
4450
4451     facet_push_stats(facet, true);
4452 }
4453
4454 static void
4455 facet_account(struct facet *facet)
4456 {
4457     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4458     const struct nlattr *a;
4459     unsigned int left;
4460     ovs_be16 vlan_tci;
4461     uint64_t n_bytes;
4462
4463     if (!facet->xout.has_normal || !ofproto->has_bonded_bundles) {
4464         return;
4465     }
4466     n_bytes = facet->byte_count - facet->accounted_bytes;
4467
4468     /* This loop feeds byte counters to bond_account() for rebalancing to use
4469      * as a basis.  We also need to track the actual VLAN on which the packet
4470      * is going to be sent to ensure that it matches the one passed to
4471      * bond_choose_output_slave().  (Otherwise, we will account to the wrong
4472      * hash bucket.)
4473      *
4474      * We use the actions from an arbitrary subfacet because they should all
4475      * be equally valid for our purpose. */
4476     vlan_tci = facet->flow.vlan_tci;
4477     NL_ATTR_FOR_EACH_UNSAFE (a, left, facet->xout.odp_actions.data,
4478                              facet->xout.odp_actions.size) {
4479         const struct ovs_action_push_vlan *vlan;
4480         struct ofport_dpif *port;
4481
4482         switch (nl_attr_type(a)) {
4483         case OVS_ACTION_ATTR_OUTPUT:
4484             port = get_odp_port(ofproto, nl_attr_get_u32(a));
4485             if (port && port->bundle && port->bundle->bond) {
4486                 bond_account(port->bundle->bond, &facet->flow,
4487                              vlan_tci_to_vid(vlan_tci), n_bytes);
4488             }
4489             break;
4490
4491         case OVS_ACTION_ATTR_POP_VLAN:
4492             vlan_tci = htons(0);
4493             break;
4494
4495         case OVS_ACTION_ATTR_PUSH_VLAN:
4496             vlan = nl_attr_get(a);
4497             vlan_tci = vlan->vlan_tci;
4498             break;
4499         }
4500     }
4501 }
4502
4503 /* Returns true if the only action for 'facet' is to send to the controller.
4504  * (We don't report NetFlow expiration messages for such facets because they
4505  * are just part of the control logic for the network, not real traffic). */
4506 static bool
4507 facet_is_controller_flow(struct facet *facet)
4508 {
4509     if (facet) {
4510         const struct rule *rule = &facet->rule->up;
4511         const struct ofpact *ofpacts = rule->ofpacts;
4512         size_t ofpacts_len = rule->ofpacts_len;
4513
4514         if (ofpacts_len > 0 &&
4515             ofpacts->type == OFPACT_CONTROLLER &&
4516             ofpact_next(ofpacts) >= ofpact_end(ofpacts, ofpacts_len)) {
4517             return true;
4518         }
4519     }
4520     return false;
4521 }
4522
4523 /* Folds all of 'facet''s statistics into its rule.  Also updates the
4524  * accounting ofhook and emits a NetFlow expiration if appropriate.  All of
4525  * 'facet''s statistics in the datapath should have been zeroed and folded into
4526  * its packet and byte counts before this function is called. */
4527 static void
4528 facet_flush_stats(struct facet *facet)
4529 {
4530     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4531     struct subfacet *subfacet;
4532
4533     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
4534         ovs_assert(!subfacet->dp_byte_count);
4535         ovs_assert(!subfacet->dp_packet_count);
4536     }
4537
4538     facet_push_stats(facet, false);
4539     if (facet->accounted_bytes < facet->byte_count) {
4540         facet_account(facet);
4541         facet->accounted_bytes = facet->byte_count;
4542     }
4543
4544     if (ofproto->netflow && !facet_is_controller_flow(facet)) {
4545         struct ofexpired expired;
4546         expired.flow = facet->flow;
4547         expired.packet_count = facet->packet_count;
4548         expired.byte_count = facet->byte_count;
4549         expired.used = facet->used;
4550         netflow_expire(ofproto->netflow, &facet->nf_flow, &expired);
4551     }
4552
4553     /* Reset counters to prevent double counting if 'facet' ever gets
4554      * reinstalled. */
4555     facet_reset_counters(facet);
4556
4557     netflow_flow_clear(&facet->nf_flow);
4558     facet->tcp_flags = 0;
4559 }
4560
4561 /* Searches 'ofproto''s table of facets for one which would be responsible for
4562  * 'flow'.  Returns it if found, otherwise a null pointer.
4563  *
4564  * The returned facet might need revalidation; use facet_lookup_valid()
4565  * instead if that is important. */
4566 static struct facet *
4567 facet_find(struct ofproto_dpif *ofproto, const struct flow *flow)
4568 {
4569     struct cls_rule *cr = classifier_lookup(&ofproto->facets, flow, NULL);
4570     return cr ? CONTAINER_OF(cr, struct facet, cr) : NULL;
4571 }
4572
4573 /* Searches 'ofproto''s table of facets for one capable that covers
4574  * 'flow'.  Returns it if found, otherwise a null pointer.
4575  *
4576  * The returned facet is guaranteed to be valid. */
4577 static struct facet *
4578 facet_lookup_valid(struct ofproto_dpif *ofproto, const struct flow *flow)
4579 {
4580     struct facet *facet;
4581
4582     facet = facet_find(ofproto, flow);
4583     if (facet
4584         && (ofproto->backer->need_revalidate
4585             || tag_set_intersects(&ofproto->backer->revalidate_set,
4586                                   facet->xout.tags))
4587         && !facet_revalidate(facet)) {
4588         return NULL;
4589     }
4590
4591     return facet;
4592 }
4593
4594 static bool
4595 facet_check_consistency(struct facet *facet)
4596 {
4597     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 15);
4598
4599     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4600
4601     struct xlate_out xout;
4602     struct xlate_in xin;
4603
4604     struct rule_dpif *rule;
4605     bool ok;
4606
4607     /* Check the rule for consistency. */
4608     rule = rule_dpif_lookup(ofproto, &facet->flow, NULL);
4609     if (rule != facet->rule) {
4610         if (!VLOG_DROP_WARN(&rl)) {
4611             struct ds s = DS_EMPTY_INITIALIZER;
4612
4613             flow_format(&s, &facet->flow);
4614             ds_put_format(&s, ": facet associated with wrong rule (was "
4615                           "table=%"PRIu8",", facet->rule->up.table_id);
4616             cls_rule_format(&facet->rule->up.cr, &s);
4617             ds_put_format(&s, ") (should have been table=%"PRIu8",",
4618                           rule->up.table_id);
4619             cls_rule_format(&rule->up.cr, &s);
4620             ds_put_char(&s, ')');
4621
4622             VLOG_WARN("%s", ds_cstr(&s));
4623             ds_destroy(&s);
4624         }
4625         return false;
4626     }
4627
4628     /* Check the datapath actions for consistency. */
4629     xlate_in_init(&xin, ofproto, &facet->flow, rule, 0, NULL);
4630     xlate_actions(&xin, &xout);
4631
4632     ok = ofpbuf_equal(&facet->xout.odp_actions, &xout.odp_actions)
4633         && facet->xout.slow == xout.slow;
4634     if (!ok && !VLOG_DROP_WARN(&rl)) {
4635         struct ds s = DS_EMPTY_INITIALIZER;
4636
4637         flow_format(&s, &facet->flow);
4638         ds_put_cstr(&s, ": inconsistency in facet");
4639
4640         if (!ofpbuf_equal(&facet->xout.odp_actions, &xout.odp_actions)) {
4641             ds_put_cstr(&s, " (actions were: ");
4642             format_odp_actions(&s, facet->xout.odp_actions.data,
4643                                facet->xout.odp_actions.size);
4644             ds_put_cstr(&s, ") (correct actions: ");
4645             format_odp_actions(&s, xout.odp_actions.data,
4646                                xout.odp_actions.size);
4647             ds_put_char(&s, ')');
4648         }
4649
4650         if (facet->xout.slow != xout.slow) {
4651             ds_put_format(&s, " slow path incorrect. should be %d", xout.slow);
4652         }
4653
4654         VLOG_WARN("%s", ds_cstr(&s));
4655         ds_destroy(&s);
4656     }
4657     xlate_out_uninit(&xout);
4658
4659     return ok;
4660 }
4661
4662 /* Re-searches the classifier for 'facet':
4663  *
4664  *   - If the rule found is different from 'facet''s current rule, moves
4665  *     'facet' to the new rule and recompiles its actions.
4666  *
4667  *   - If the rule found is the same as 'facet''s current rule, leaves 'facet'
4668  *     where it is and recompiles its actions anyway.
4669  *
4670  *   - If any of 'facet''s subfacets correspond to a new flow according to
4671  *     ofproto_receive(), 'facet' is removed.
4672  *
4673  *   Returns true if 'facet' is still valid.  False if 'facet' was removed. */
4674 static bool
4675 facet_revalidate(struct facet *facet)
4676 {
4677     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4678     struct rule_dpif *new_rule;
4679     struct subfacet *subfacet;
4680     struct flow_wildcards wc;
4681     struct xlate_out xout;
4682     struct xlate_in xin;
4683
4684     COVERAGE_INC(facet_revalidate);
4685
4686     /* Check that child subfacets still correspond to this facet.  Tunnel
4687      * configuration changes could cause a subfacet's OpenFlow in_port to
4688      * change. */
4689     LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
4690         struct ofproto_dpif *recv_ofproto;
4691         struct flow recv_flow;
4692         int error;
4693
4694         error = ofproto_receive(ofproto->backer, NULL, subfacet->key,
4695                                 subfacet->key_len, &recv_flow, NULL,
4696                                 &recv_ofproto, NULL);
4697         if (error
4698             || recv_ofproto != ofproto
4699             || facet != facet_find(ofproto, &recv_flow)) {
4700             facet_remove(facet);
4701             return false;
4702         }
4703     }
4704
4705     flow_wildcards_init_catchall(&wc);
4706     new_rule = rule_dpif_lookup(ofproto, &facet->flow, &wc);
4707
4708     /* Calculate new datapath actions.
4709      *
4710      * We do not modify any 'facet' state yet, because we might need to, e.g.,
4711      * emit a NetFlow expiration and, if so, we need to have the old state
4712      * around to properly compose it. */
4713     xlate_in_init(&xin, ofproto, &facet->flow, new_rule, 0, NULL);
4714     xlate_actions(&xin, &xout);
4715     flow_wildcards_or(&xout.wc, &xout.wc, &wc);
4716
4717     /* A facet's slow path reason should only change under dramatic
4718      * circumstances.  Rather than try to update everything, it's simpler to
4719      * remove the facet and start over.
4720      *
4721      * More importantly, if a facet's wildcards change, it will be relatively
4722      * difficult to figure out if its subfacets still belong to it, and if not
4723      * which facet they may belong to.  Again, to avoid the complexity, we
4724      * simply give up instead. */
4725     if (facet->xout.slow != xout.slow
4726         || memcmp(&facet->xout.wc, &xout.wc, sizeof xout.wc)) {
4727         facet_remove(facet);
4728         xlate_out_uninit(&xout);
4729         return false;
4730     }
4731
4732     if (!ofpbuf_equal(&facet->xout.odp_actions, &xout.odp_actions)) {
4733         LIST_FOR_EACH(subfacet, list_node, &facet->subfacets) {
4734             if (subfacet->path == SF_FAST_PATH) {
4735                 struct dpif_flow_stats stats;
4736
4737                 subfacet_install(subfacet, &xout.odp_actions, &stats);
4738                 subfacet_update_stats(subfacet, &stats);
4739             }
4740         }
4741
4742         facet_flush_stats(facet);
4743
4744         ofpbuf_clear(&facet->xout.odp_actions);
4745         ofpbuf_put(&facet->xout.odp_actions, xout.odp_actions.data,
4746                    xout.odp_actions.size);
4747     }
4748
4749     /* Update 'facet' now that we've taken care of all the old state. */
4750     facet->xout.tags = xout.tags;
4751     facet->xout.slow = xout.slow;
4752     facet->xout.has_learn = xout.has_learn;
4753     facet->xout.has_normal = xout.has_normal;
4754     facet->xout.has_fin_timeout = xout.has_fin_timeout;
4755     facet->xout.nf_output_iface = xout.nf_output_iface;
4756     facet->xout.mirrors = xout.mirrors;
4757     facet->nf_flow.output_iface = facet->xout.nf_output_iface;
4758
4759     if (facet->rule != new_rule) {
4760         COVERAGE_INC(facet_changed_rule);
4761         list_remove(&facet->list_node);
4762         list_push_back(&new_rule->facets, &facet->list_node);
4763         facet->rule = new_rule;
4764         facet->used = new_rule->up.created;
4765         facet->prev_used = facet->used;
4766     }
4767
4768     xlate_out_uninit(&xout);
4769     return true;
4770 }
4771
4772 static void
4773 facet_reset_counters(struct facet *facet)
4774 {
4775     facet->packet_count = 0;
4776     facet->byte_count = 0;
4777     facet->prev_packet_count = 0;
4778     facet->prev_byte_count = 0;
4779     facet->accounted_bytes = 0;
4780 }
4781
4782 static void
4783 facet_push_stats(struct facet *facet, bool may_learn)
4784 {
4785     struct dpif_flow_stats stats;
4786
4787     ovs_assert(facet->packet_count >= facet->prev_packet_count);
4788     ovs_assert(facet->byte_count >= facet->prev_byte_count);
4789     ovs_assert(facet->used >= facet->prev_used);
4790
4791     stats.n_packets = facet->packet_count - facet->prev_packet_count;
4792     stats.n_bytes = facet->byte_count - facet->prev_byte_count;
4793     stats.used = facet->used;
4794     stats.tcp_flags = facet->tcp_flags;
4795
4796     if (may_learn || stats.n_packets || facet->used > facet->prev_used) {
4797         struct ofproto_dpif *ofproto =
4798             ofproto_dpif_cast(facet->rule->up.ofproto);
4799
4800         struct ofport_dpif *in_port;
4801         struct xlate_in xin;
4802
4803         facet->prev_packet_count = facet->packet_count;
4804         facet->prev_byte_count = facet->byte_count;
4805         facet->prev_used = facet->used;
4806
4807         in_port = get_ofp_port(ofproto, facet->flow.in_port);
4808         if (in_port && in_port->tnl_port) {
4809             netdev_vport_inc_rx(in_port->up.netdev, &stats);
4810         }
4811
4812         rule_credit_stats(facet->rule, &stats);
4813         netflow_flow_update_time(ofproto->netflow, &facet->nf_flow,
4814                                  facet->used);
4815         netflow_flow_update_flags(&facet->nf_flow, facet->tcp_flags);
4816         update_mirror_stats(ofproto, facet->xout.mirrors, stats.n_packets,
4817                             stats.n_bytes);
4818
4819         xlate_in_init(&xin, ofproto, &facet->flow, facet->rule,
4820                       stats.tcp_flags, NULL);
4821         xin.resubmit_stats = &stats;
4822         xin.may_learn = may_learn;
4823         xlate_actions_for_side_effects(&xin);
4824     }
4825 }
4826
4827 static void
4828 push_all_stats__(bool run_fast)
4829 {
4830     static long long int rl = LLONG_MIN;
4831     struct ofproto_dpif *ofproto;
4832
4833     if (time_msec() < rl) {
4834         return;
4835     }
4836
4837     HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
4838         struct cls_cursor cursor;
4839         struct facet *facet;
4840
4841         cls_cursor_init(&cursor, &ofproto->facets, NULL);
4842         CLS_CURSOR_FOR_EACH (facet, cr, &cursor) {
4843             facet_push_stats(facet, false);
4844             if (run_fast) {
4845                 run_fast_rl();
4846             }
4847         }
4848     }
4849
4850     rl = time_msec() + 100;
4851 }
4852
4853 static void
4854 push_all_stats(void)
4855 {
4856     push_all_stats__(true);
4857 }
4858
4859 void
4860 rule_credit_stats(struct rule_dpif *rule, const struct dpif_flow_stats *stats)
4861 {
4862     rule->packet_count += stats->n_packets;
4863     rule->byte_count += stats->n_bytes;
4864     ofproto_rule_update_used(&rule->up, stats->used);
4865 }
4866 \f
4867 /* Subfacets. */
4868
4869 static struct subfacet *
4870 subfacet_find(struct dpif_backer *backer, const struct nlattr *key,
4871               size_t key_len, uint32_t key_hash)
4872 {
4873     struct subfacet *subfacet;
4874
4875     HMAP_FOR_EACH_WITH_HASH (subfacet, hmap_node, key_hash,
4876                              &backer->subfacets) {
4877         if (subfacet->key_len == key_len
4878             && !memcmp(key, subfacet->key, key_len)) {
4879             return subfacet;
4880         }
4881     }
4882
4883     return NULL;
4884 }
4885
4886 /* Searches 'facet' (within 'ofproto') for a subfacet with the specified
4887  * 'key_fitness', 'key', and 'key_len' members in 'miss'.  Returns the
4888  * existing subfacet if there is one, otherwise creates and returns a
4889  * new subfacet. */
4890 static struct subfacet *
4891 subfacet_create(struct facet *facet, struct flow_miss *miss,
4892                 long long int now)
4893 {
4894     struct dpif_backer *backer = miss->ofproto->backer;
4895     enum odp_key_fitness key_fitness = miss->key_fitness;
4896     const struct nlattr *key = miss->key;
4897     size_t key_len = miss->key_len;
4898     uint32_t key_hash;
4899     struct subfacet *subfacet;
4900
4901     key_hash = odp_flow_key_hash(key, key_len);
4902
4903     if (list_is_empty(&facet->subfacets)) {
4904         subfacet = &facet->one_subfacet;
4905     } else {
4906         subfacet = subfacet_find(backer, key, key_len, key_hash);
4907         if (subfacet) {
4908             if (subfacet->facet == facet) {
4909                 return subfacet;
4910             }
4911
4912             /* This shouldn't happen. */
4913             VLOG_ERR_RL(&rl, "subfacet with wrong facet");
4914             subfacet_destroy(subfacet);
4915         }
4916
4917         subfacet = xmalloc(sizeof *subfacet);
4918     }
4919
4920     hmap_insert(&backer->subfacets, &subfacet->hmap_node, key_hash);
4921     list_push_back(&facet->subfacets, &subfacet->list_node);
4922     subfacet->facet = facet;
4923     subfacet->key_fitness = key_fitness;
4924     subfacet->key = xmemdup(key, key_len);
4925     subfacet->key_len = key_len;
4926     subfacet->used = now;
4927     subfacet->created = now;
4928     subfacet->dp_packet_count = 0;
4929     subfacet->dp_byte_count = 0;
4930     subfacet->path = SF_NOT_INSTALLED;
4931     subfacet->backer = backer;
4932
4933     backer->subfacet_add_count++;
4934     return subfacet;
4935 }
4936
4937 /* Uninstalls 'subfacet' from the datapath, if it is installed, removes it from
4938  * its facet within 'ofproto', and frees it. */
4939 static void
4940 subfacet_destroy__(struct subfacet *subfacet)
4941 {
4942     struct facet *facet = subfacet->facet;
4943     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
4944
4945     /* Update ofproto stats before uninstall the subfacet. */
4946     ofproto->backer->subfacet_del_count++;
4947
4948     subfacet_uninstall(subfacet);
4949     hmap_remove(&subfacet->backer->subfacets, &subfacet->hmap_node);
4950     list_remove(&subfacet->list_node);
4951     free(subfacet->key);
4952     if (subfacet != &facet->one_subfacet) {
4953         free(subfacet);
4954     }
4955 }
4956
4957 /* Destroys 'subfacet', as with subfacet_destroy__(), and then if this was the
4958  * last remaining subfacet in its facet destroys the facet too. */
4959 static void
4960 subfacet_destroy(struct subfacet *subfacet)
4961 {
4962     struct facet *facet = subfacet->facet;
4963
4964     if (list_is_singleton(&facet->subfacets)) {
4965         /* facet_remove() needs at least one subfacet (it will remove it). */
4966         facet_remove(facet);
4967     } else {
4968         subfacet_destroy__(subfacet);
4969     }
4970 }
4971
4972 static void
4973 subfacet_destroy_batch(struct dpif_backer *backer,
4974                        struct subfacet **subfacets, int n)
4975 {
4976     struct dpif_op ops[SUBFACET_DESTROY_MAX_BATCH];
4977     struct dpif_op *opsp[SUBFACET_DESTROY_MAX_BATCH];
4978     struct dpif_flow_stats stats[SUBFACET_DESTROY_MAX_BATCH];
4979     int i;
4980
4981     for (i = 0; i < n; i++) {
4982         ops[i].type = DPIF_OP_FLOW_DEL;
4983         ops[i].u.flow_del.key = subfacets[i]->key;
4984         ops[i].u.flow_del.key_len = subfacets[i]->key_len;
4985         ops[i].u.flow_del.stats = &stats[i];
4986         opsp[i] = &ops[i];
4987     }
4988
4989     dpif_operate(backer->dpif, opsp, n);
4990     for (i = 0; i < n; i++) {
4991         subfacet_reset_dp_stats(subfacets[i], &stats[i]);
4992         subfacets[i]->path = SF_NOT_INSTALLED;
4993         subfacet_destroy(subfacets[i]);
4994         run_fast_rl();
4995     }
4996 }
4997
4998 /* Updates 'subfacet''s datapath flow, setting its actions to 'actions_len'
4999  * bytes of actions in 'actions'.  If 'stats' is non-null, statistics counters
5000  * in the datapath will be zeroed and 'stats' will be updated with traffic new
5001  * since 'subfacet' was last updated.
5002  *
5003  * Returns 0 if successful, otherwise a positive errno value. */
5004 static int
5005 subfacet_install(struct subfacet *subfacet, const struct ofpbuf *odp_actions,
5006                  struct dpif_flow_stats *stats)
5007 {
5008     struct facet *facet = subfacet->facet;
5009     struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
5010     enum subfacet_path path = facet->xout.slow ? SF_SLOW_PATH : SF_FAST_PATH;
5011     const struct nlattr *actions = odp_actions->data;
5012     size_t actions_len = odp_actions->size;
5013
5014     uint64_t slow_path_stub[128 / 8];
5015     enum dpif_flow_put_flags flags;
5016     int ret;
5017
5018     flags = DPIF_FP_CREATE | DPIF_FP_MODIFY;
5019     if (stats) {
5020         flags |= DPIF_FP_ZERO_STATS;
5021     }
5022
5023     if (path == SF_SLOW_PATH) {
5024         compose_slow_path(ofproto, &facet->flow, facet->xout.slow,
5025                           slow_path_stub, sizeof slow_path_stub,
5026                           &actions, &actions_len);
5027     }
5028
5029     ret = dpif_flow_put(ofproto->backer->dpif, flags, subfacet->key,
5030                         subfacet->key_len,  NULL, 0,
5031                         actions, actions_len, stats);
5032
5033     if (stats) {
5034         subfacet_reset_dp_stats(subfacet, stats);
5035     }
5036
5037     if (!ret) {
5038         subfacet->path = path;
5039     }
5040     return ret;
5041 }
5042
5043 /* If 'subfacet' is installed in the datapath, uninstalls it. */
5044 static void
5045 subfacet_uninstall(struct subfacet *subfacet)
5046 {
5047     if (subfacet->path != SF_NOT_INSTALLED) {
5048         struct rule_dpif *rule = subfacet->facet->rule;
5049         struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
5050         struct dpif_flow_stats stats;
5051         int error;
5052
5053         error = dpif_flow_del(ofproto->backer->dpif, subfacet->key,
5054                               subfacet->key_len, &stats);
5055         subfacet_reset_dp_stats(subfacet, &stats);
5056         if (!error) {
5057             subfacet_update_stats(subfacet, &stats);
5058         }
5059         subfacet->path = SF_NOT_INSTALLED;
5060     } else {
5061         ovs_assert(subfacet->dp_packet_count == 0);
5062         ovs_assert(subfacet->dp_byte_count == 0);
5063     }
5064 }
5065
5066 /* Resets 'subfacet''s datapath statistics counters.  This should be called
5067  * when 'subfacet''s statistics are cleared in the datapath.  If 'stats' is
5068  * non-null, it should contain the statistics returned by dpif when 'subfacet'
5069  * was reset in the datapath.  'stats' will be modified to include only
5070  * statistics new since 'subfacet' was last updated. */
5071 static void
5072 subfacet_reset_dp_stats(struct subfacet *subfacet,
5073                         struct dpif_flow_stats *stats)
5074 {
5075     if (stats
5076         && subfacet->dp_packet_count <= stats->n_packets
5077         && subfacet->dp_byte_count <= stats->n_bytes) {
5078         stats->n_packets -= subfacet->dp_packet_count;
5079         stats->n_bytes -= subfacet->dp_byte_count;
5080     }
5081
5082     subfacet->dp_packet_count = 0;
5083     subfacet->dp_byte_count = 0;
5084 }
5085
5086 /* Folds the statistics from 'stats' into the counters in 'subfacet'.
5087  *
5088  * Because of the meaning of a subfacet's counters, it only makes sense to do
5089  * this if 'stats' are not tracked in the datapath, that is, if 'stats'
5090  * represents a packet that was sent by hand or if it represents statistics
5091  * that have been cleared out of the datapath. */
5092 static void
5093 subfacet_update_stats(struct subfacet *subfacet,
5094                       const struct dpif_flow_stats *stats)
5095 {
5096     if (stats->n_packets || stats->used > subfacet->used) {
5097         struct facet *facet = subfacet->facet;
5098
5099         subfacet->used = MAX(subfacet->used, stats->used);
5100         facet->used = MAX(facet->used, stats->used);
5101         facet->packet_count += stats->n_packets;
5102         facet->byte_count += stats->n_bytes;
5103         facet->tcp_flags |= stats->tcp_flags;
5104     }
5105 }
5106 \f
5107 /* Rules. */
5108
5109 /* Lookup 'flow' in 'ofproto''s classifier.  If 'wc' is non-null, sets
5110  * the fields that were relevant as part of the lookup. */
5111 static struct rule_dpif *
5112 rule_dpif_lookup(struct ofproto_dpif *ofproto, const struct flow *flow,
5113                  struct flow_wildcards *wc)
5114 {
5115     struct rule_dpif *rule;
5116
5117     rule = rule_dpif_lookup_in_table(ofproto, flow, wc, 0);
5118     if (rule) {
5119         return rule;
5120     }
5121
5122     return rule_dpif_miss_rule(ofproto, flow);
5123 }
5124
5125 struct rule_dpif *
5126 rule_dpif_lookup_in_table(struct ofproto_dpif *ofproto,
5127                           const struct flow *flow, struct flow_wildcards *wc,
5128                           uint8_t table_id)
5129 {
5130     struct cls_rule *cls_rule;
5131     struct classifier *cls;
5132     bool frag;
5133
5134     if (table_id >= N_TABLES) {
5135         return NULL;
5136     }
5137
5138     if (wc) {
5139         wc->masks.nw_frag |= FLOW_NW_FRAG_MASK;
5140     }
5141
5142     cls = &ofproto->up.tables[table_id].cls;
5143     frag = (flow->nw_frag & FLOW_NW_FRAG_ANY) != 0;
5144     if (frag && ofproto->up.frag_handling == OFPC_FRAG_NORMAL) {
5145         /* We must pretend that transport ports are unavailable. */
5146         struct flow ofpc_normal_flow = *flow;
5147         ofpc_normal_flow.tp_src = htons(0);
5148         ofpc_normal_flow.tp_dst = htons(0);
5149         cls_rule = classifier_lookup(cls, &ofpc_normal_flow, wc);
5150     } else if (frag && ofproto->up.frag_handling == OFPC_FRAG_DROP) {
5151         cls_rule = &ofproto->drop_frags_rule->up.cr;
5152         if (wc) {
5153             flow_wildcards_init_exact(wc);
5154         }
5155     } else {
5156         cls_rule = classifier_lookup(cls, flow, wc);
5157     }
5158     return rule_dpif_cast(rule_from_cls_rule(cls_rule));
5159 }
5160
5161 struct rule_dpif *
5162 rule_dpif_miss_rule(struct ofproto_dpif *ofproto, const struct flow *flow)
5163 {
5164     struct ofport_dpif *port;
5165
5166     port = get_ofp_port(ofproto, flow->in_port);
5167     if (!port) {
5168         VLOG_WARN_RL(&rl, "packet-in on unknown port %"PRIu16, flow->in_port);
5169         return ofproto->miss_rule;
5170     }
5171
5172     if (port->up.pp.config & OFPUTIL_PC_NO_PACKET_IN) {
5173         return ofproto->no_packet_in_rule;
5174     }
5175     return ofproto->miss_rule;
5176 }
5177
5178 static void
5179 complete_operation(struct rule_dpif *rule)
5180 {
5181     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
5182
5183     rule_invalidate(rule);
5184     if (clogged) {
5185         struct dpif_completion *c = xmalloc(sizeof *c);
5186         c->op = rule->up.pending;
5187         list_push_back(&ofproto->completions, &c->list_node);
5188     } else {
5189         ofoperation_complete(rule->up.pending, 0);
5190     }
5191 }
5192
5193 static struct rule *
5194 rule_alloc(void)
5195 {
5196     struct rule_dpif *rule = xmalloc(sizeof *rule);
5197     return &rule->up;
5198 }
5199
5200 static void
5201 rule_dealloc(struct rule *rule_)
5202 {
5203     struct rule_dpif *rule = rule_dpif_cast(rule_);
5204     free(rule);
5205 }
5206
5207 static enum ofperr
5208 rule_construct(struct rule *rule_)
5209 {
5210     struct rule_dpif *rule = rule_dpif_cast(rule_);
5211     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
5212     struct rule_dpif *victim;
5213     uint8_t table_id;
5214
5215     rule->packet_count = 0;
5216     rule->byte_count = 0;
5217
5218     victim = rule_dpif_cast(ofoperation_get_victim(rule->up.pending));
5219     if (victim && !list_is_empty(&victim->facets)) {
5220         struct facet *facet;
5221
5222         rule->facets = victim->facets;
5223         list_moved(&rule->facets);
5224         LIST_FOR_EACH (facet, list_node, &rule->facets) {
5225             /* XXX: We're only clearing our local counters here.  It's possible
5226              * that quite a few packets are unaccounted for in the datapath
5227              * statistics.  These will be accounted to the new rule instead of
5228              * cleared as required.  This could be fixed by clearing out the
5229              * datapath statistics for this facet, but currently it doesn't
5230              * seem worth it. */
5231             facet_reset_counters(facet);
5232             facet->rule = rule;
5233         }
5234     } else {
5235         /* Must avoid list_moved() in this case. */
5236         list_init(&rule->facets);
5237     }
5238
5239     table_id = rule->up.table_id;
5240     if (victim) {
5241         rule->tag = victim->tag;
5242     } else if (table_id == 0) {
5243         rule->tag = 0;
5244     } else {
5245         struct flow flow;
5246
5247         miniflow_expand(&rule->up.cr.match.flow, &flow);
5248         rule->tag = rule_calculate_tag(&flow, &rule->up.cr.match.mask,
5249                                        ofproto->tables[table_id].basis);
5250     }
5251
5252     complete_operation(rule);
5253     return 0;
5254 }
5255
5256 static void
5257 rule_destruct(struct rule *rule_)
5258 {
5259     struct rule_dpif *rule = rule_dpif_cast(rule_);
5260     struct facet *facet, *next_facet;
5261
5262     LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
5263         facet_revalidate(facet);
5264     }
5265
5266     complete_operation(rule);
5267 }
5268
5269 static void
5270 rule_get_stats(struct rule *rule_, uint64_t *packets, uint64_t *bytes)
5271 {
5272     struct rule_dpif *rule = rule_dpif_cast(rule_);
5273
5274     /* push_all_stats() can handle flow misses which, when using the learn
5275      * action, can cause rules to be added and deleted.  This can corrupt our
5276      * caller's datastructures which assume that rule_get_stats() doesn't have
5277      * an impact on the flow table. To be safe, we disable miss handling. */
5278     push_all_stats__(false);
5279
5280     /* Start from historical data for 'rule' itself that are no longer tracked
5281      * in facets.  This counts, for example, facets that have expired. */
5282     *packets = rule->packet_count;
5283     *bytes = rule->byte_count;
5284 }
5285
5286 static void
5287 rule_dpif_execute(struct rule_dpif *rule, const struct flow *flow,
5288                   struct ofpbuf *packet)
5289 {
5290     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
5291     struct dpif_flow_stats stats;
5292     struct xlate_out xout;
5293     struct xlate_in xin;
5294
5295     dpif_flow_stats_extract(flow, packet, time_msec(), &stats);
5296     rule_credit_stats(rule, &stats);
5297
5298     xlate_in_init(&xin, ofproto, flow, rule, stats.tcp_flags, packet);
5299     xin.resubmit_stats = &stats;
5300     xlate_actions(&xin, &xout);
5301
5302     execute_odp_actions(ofproto, flow, xout.odp_actions.data,
5303                         xout.odp_actions.size, packet);
5304
5305     xlate_out_uninit(&xout);
5306 }
5307
5308 static enum ofperr
5309 rule_execute(struct rule *rule, const struct flow *flow,
5310              struct ofpbuf *packet)
5311 {
5312     rule_dpif_execute(rule_dpif_cast(rule), flow, packet);
5313     ofpbuf_delete(packet);
5314     return 0;
5315 }
5316
5317 static void
5318 rule_modify_actions(struct rule *rule_)
5319 {
5320     struct rule_dpif *rule = rule_dpif_cast(rule_);
5321
5322     complete_operation(rule);
5323 }
5324 \f
5325 /* Sends 'packet' out 'ofport'.
5326  * May modify 'packet'.
5327  * Returns 0 if successful, otherwise a positive errno value. */
5328 static int
5329 send_packet(const struct ofport_dpif *ofport, struct ofpbuf *packet)
5330 {
5331     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport->up.ofproto);
5332     uint64_t odp_actions_stub[1024 / 8];
5333     struct ofpbuf key, odp_actions;
5334     struct dpif_flow_stats stats;
5335     struct odputil_keybuf keybuf;
5336     struct ofpact_output output;
5337     struct xlate_out xout;
5338     struct xlate_in xin;
5339     struct flow flow;
5340     int error;
5341
5342     ofpbuf_use_stub(&odp_actions, odp_actions_stub, sizeof odp_actions_stub);
5343     ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
5344
5345     /* Use OFPP_NONE as the in_port to avoid special packet processing. */
5346     flow_extract(packet, 0, 0, NULL, OFPP_NONE, &flow);
5347     odp_flow_key_from_flow(&key, &flow, ofp_port_to_odp_port(ofproto,
5348                                                              OFPP_LOCAL));
5349     dpif_flow_stats_extract(&flow, packet, time_msec(), &stats);
5350
5351     ofpact_init(&output.ofpact, OFPACT_OUTPUT, sizeof output);
5352     output.port = ofport->up.ofp_port;
5353     output.max_len = 0;
5354
5355     xlate_in_init(&xin, ofproto, &flow, NULL, 0, packet);
5356     xin.ofpacts_len = sizeof output;
5357     xin.ofpacts = &output.ofpact;
5358     xin.resubmit_stats = &stats;
5359     xlate_actions(&xin, &xout);
5360
5361     error = dpif_execute(ofproto->backer->dpif,
5362                          key.data, key.size,
5363                          xout.odp_actions.data, xout.odp_actions.size,
5364                          packet);
5365     xlate_out_uninit(&xout);
5366
5367     if (error) {
5368         VLOG_WARN_RL(&rl, "%s: failed to send packet on port %s (%s)",
5369                      ofproto->up.name, netdev_get_name(ofport->up.netdev),
5370                      strerror(error));
5371     }
5372
5373     ofproto->stats.tx_packets++;
5374     ofproto->stats.tx_bytes += packet->size;
5375     return error;
5376 }
5377
5378 /* Composes an ODP action for a "slow path" action for 'flow' within 'ofproto'.
5379  * The action will state 'slow' as the reason that the action is in the slow
5380  * path.  (This is purely informational: it allows a human viewing "ovs-dpctl
5381  * dump-flows" output to see why a flow is in the slow path.)
5382  *
5383  * The 'stub_size' bytes in 'stub' will be used to store the action.
5384  * 'stub_size' must be large enough for the action.
5385  *
5386  * The action and its size will be stored in '*actionsp' and '*actions_lenp',
5387  * respectively. */
5388 static void
5389 compose_slow_path(const struct ofproto_dpif *ofproto, const struct flow *flow,
5390                   enum slow_path_reason slow,
5391                   uint64_t *stub, size_t stub_size,
5392                   const struct nlattr **actionsp, size_t *actions_lenp)
5393 {
5394     union user_action_cookie cookie;
5395     struct ofpbuf buf;
5396
5397     cookie.type = USER_ACTION_COOKIE_SLOW_PATH;
5398     cookie.slow_path.unused = 0;
5399     cookie.slow_path.reason = slow;
5400
5401     ofpbuf_use_stack(&buf, stub, stub_size);
5402     if (slow & (SLOW_CFM | SLOW_BFD | SLOW_LACP | SLOW_STP)) {
5403         uint32_t pid = dpif_port_get_pid(ofproto->backer->dpif, UINT32_MAX);
5404         odp_put_userspace_action(pid, &cookie, sizeof cookie.slow_path, &buf);
5405     } else {
5406         put_userspace_action(ofproto, &buf, flow, &cookie,
5407                              sizeof cookie.slow_path);
5408     }
5409     *actionsp = buf.data;
5410     *actions_lenp = buf.size;
5411 }
5412
5413 size_t
5414 put_userspace_action(const struct ofproto_dpif *ofproto,
5415                      struct ofpbuf *odp_actions,
5416                      const struct flow *flow,
5417                      const union user_action_cookie *cookie,
5418                      const size_t cookie_size)
5419 {
5420     uint32_t pid;
5421
5422     pid = dpif_port_get_pid(ofproto->backer->dpif,
5423                             ofp_port_to_odp_port(ofproto, flow->in_port));
5424
5425     return odp_put_userspace_action(pid, cookie, cookie_size, odp_actions);
5426 }
5427
5428
5429 static void
5430 update_mirror_stats(struct ofproto_dpif *ofproto, mirror_mask_t mirrors,
5431                     uint64_t packets, uint64_t bytes)
5432 {
5433     if (!mirrors) {
5434         return;
5435     }
5436
5437     for (; mirrors; mirrors = zero_rightmost_1bit(mirrors)) {
5438         struct ofmirror *m;
5439
5440         m = ofproto->mirrors[mirror_mask_ffs(mirrors) - 1];
5441
5442         if (!m) {
5443             /* In normal circumstances 'm' will not be NULL.  However,
5444              * if mirrors are reconfigured, we can temporarily get out
5445              * of sync in facet_revalidate().  We could "correct" the
5446              * mirror list before reaching here, but doing that would
5447              * not properly account the traffic stats we've currently
5448              * accumulated for previous mirror configuration. */
5449             continue;
5450         }
5451
5452         m->packet_count += packets;
5453         m->byte_count += bytes;
5454     }
5455 }
5456
5457 \f
5458 /* Optimized flow revalidation.
5459  *
5460  * It's a difficult problem, in general, to tell which facets need to have
5461  * their actions recalculated whenever the OpenFlow flow table changes.  We
5462  * don't try to solve that general problem: for most kinds of OpenFlow flow
5463  * table changes, we recalculate the actions for every facet.  This is
5464  * relatively expensive, but it's good enough if the OpenFlow flow table
5465  * doesn't change very often.
5466  *
5467  * However, we can expect one particular kind of OpenFlow flow table change to
5468  * happen frequently: changes caused by MAC learning.  To avoid wasting a lot
5469  * of CPU on revalidating every facet whenever MAC learning modifies the flow
5470  * table, we add a special case that applies to flow tables in which every rule
5471  * has the same form (that is, the same wildcards), except that the table is
5472  * also allowed to have a single "catch-all" flow that matches all packets.  We
5473  * optimize this case by tagging all of the facets that resubmit into the table
5474  * and invalidating the same tag whenever a flow changes in that table.  The
5475  * end result is that we revalidate just the facets that need it (and sometimes
5476  * a few more, but not all of the facets or even all of the facets that
5477  * resubmit to the table modified by MAC learning). */
5478
5479 /* Calculates the tag to use for 'flow' and mask 'mask' when it is inserted
5480  * into an OpenFlow table with the given 'basis'. */
5481 tag_type
5482 rule_calculate_tag(const struct flow *flow, const struct minimask *mask,
5483                    uint32_t secret)
5484 {
5485     if (minimask_is_catchall(mask)) {
5486         return 0;
5487     } else {
5488         uint32_t hash = flow_hash_in_minimask(flow, mask, secret);
5489         return tag_create_deterministic(hash);
5490     }
5491 }
5492
5493 /* Following a change to OpenFlow table 'table_id' in 'ofproto', update the
5494  * taggability of that table.
5495  *
5496  * This function must be called after *each* change to a flow table.  If you
5497  * skip calling it on some changes then the pointer comparisons at the end can
5498  * be invalid if you get unlucky.  For example, if a flow removal causes a
5499  * cls_table to be destroyed and then a flow insertion causes a cls_table with
5500  * different wildcards to be created with the same address, then this function
5501  * will incorrectly skip revalidation. */
5502 static void
5503 table_update_taggable(struct ofproto_dpif *ofproto, uint8_t table_id)
5504 {
5505     struct table_dpif *table = &ofproto->tables[table_id];
5506     const struct oftable *oftable = &ofproto->up.tables[table_id];
5507     struct cls_table *catchall, *other;
5508     struct cls_table *t;
5509
5510     catchall = other = NULL;
5511
5512     switch (hmap_count(&oftable->cls.tables)) {
5513     case 0:
5514         /* We could tag this OpenFlow table but it would make the logic a
5515          * little harder and it's a corner case that doesn't seem worth it
5516          * yet. */
5517         break;
5518
5519     case 1:
5520     case 2:
5521         HMAP_FOR_EACH (t, hmap_node, &oftable->cls.tables) {
5522             if (cls_table_is_catchall(t)) {
5523                 catchall = t;
5524             } else if (!other) {
5525                 other = t;
5526             } else {
5527                 /* Indicate that we can't tag this by setting both tables to
5528                  * NULL.  (We know that 'catchall' is already NULL.) */
5529                 other = NULL;
5530             }
5531         }
5532         break;
5533
5534     default:
5535         /* Can't tag this table. */
5536         break;
5537     }
5538
5539     if (table->catchall_table != catchall || table->other_table != other) {
5540         table->catchall_table = catchall;
5541         table->other_table = other;
5542         ofproto->backer->need_revalidate = REV_FLOW_TABLE;
5543     }
5544 }
5545
5546 /* Given 'rule' that has changed in some way (either it is a rule being
5547  * inserted, a rule being deleted, or a rule whose actions are being
5548  * modified), marks facets for revalidation to ensure that packets will be
5549  * forwarded correctly according to the new state of the flow table.
5550  *
5551  * This function must be called after *each* change to a flow table.  See
5552  * the comment on table_update_taggable() for more information. */
5553 static void
5554 rule_invalidate(const struct rule_dpif *rule)
5555 {
5556     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
5557
5558     table_update_taggable(ofproto, rule->up.table_id);
5559
5560     if (!ofproto->backer->need_revalidate) {
5561         struct table_dpif *table = &ofproto->tables[rule->up.table_id];
5562
5563         if (table->other_table && rule->tag) {
5564             tag_set_add(&ofproto->backer->revalidate_set, rule->tag);
5565         } else {
5566             ofproto->backer->need_revalidate = REV_FLOW_TABLE;
5567         }
5568     }
5569 }
5570 \f
5571 static bool
5572 set_frag_handling(struct ofproto *ofproto_,
5573                   enum ofp_config_flags frag_handling)
5574 {
5575     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
5576     if (frag_handling != OFPC_FRAG_REASM) {
5577         ofproto->backer->need_revalidate = REV_RECONFIGURE;
5578         return true;
5579     } else {
5580         return false;
5581     }
5582 }
5583
5584 static enum ofperr
5585 packet_out(struct ofproto *ofproto_, struct ofpbuf *packet,
5586            const struct flow *flow,
5587            const struct ofpact *ofpacts, size_t ofpacts_len)
5588 {
5589     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
5590     struct odputil_keybuf keybuf;
5591     struct dpif_flow_stats stats;
5592     struct xlate_out xout;
5593     struct xlate_in xin;
5594     struct ofpbuf key;
5595
5596
5597     ofpbuf_use_stack(&key, &keybuf, sizeof keybuf);
5598     odp_flow_key_from_flow(&key, flow,
5599                            ofp_port_to_odp_port(ofproto, flow->in_port));
5600
5601     dpif_flow_stats_extract(flow, packet, time_msec(), &stats);
5602
5603     xlate_in_init(&xin, ofproto, flow, NULL, stats.tcp_flags, packet);
5604     xin.resubmit_stats = &stats;
5605     xin.ofpacts_len = ofpacts_len;
5606     xin.ofpacts = ofpacts;
5607
5608     xlate_actions(&xin, &xout);
5609     dpif_execute(ofproto->backer->dpif, key.data, key.size,
5610                  xout.odp_actions.data, xout.odp_actions.size, packet);
5611     xlate_out_uninit(&xout);
5612
5613     return 0;
5614 }
5615 \f
5616 /* NetFlow. */
5617
5618 static int
5619 set_netflow(struct ofproto *ofproto_,
5620             const struct netflow_options *netflow_options)
5621 {
5622     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
5623
5624     if (netflow_options) {
5625         if (!ofproto->netflow) {
5626             ofproto->netflow = netflow_create();
5627             ofproto->backer->need_revalidate = REV_RECONFIGURE;
5628         }
5629         return netflow_set_options(ofproto->netflow, netflow_options);
5630     } else if (ofproto->netflow) {
5631         ofproto->backer->need_revalidate = REV_RECONFIGURE;
5632         netflow_destroy(ofproto->netflow);
5633         ofproto->netflow = NULL;
5634     }
5635
5636     return 0;
5637 }
5638
5639 static void
5640 get_netflow_ids(const struct ofproto *ofproto_,
5641                 uint8_t *engine_type, uint8_t *engine_id)
5642 {
5643     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
5644
5645     dpif_get_netflow_ids(ofproto->backer->dpif, engine_type, engine_id);
5646 }
5647
5648 static void
5649 send_active_timeout(struct ofproto_dpif *ofproto, struct facet *facet)
5650 {
5651     if (!facet_is_controller_flow(facet) &&
5652         netflow_active_timeout_expired(ofproto->netflow, &facet->nf_flow)) {
5653         struct subfacet *subfacet;
5654         struct ofexpired expired;
5655
5656         LIST_FOR_EACH (subfacet, list_node, &facet->subfacets) {
5657             if (subfacet->path == SF_FAST_PATH) {
5658                 struct dpif_flow_stats stats;
5659
5660                 subfacet_install(subfacet, &facet->xout.odp_actions,
5661                                  &stats);
5662                 subfacet_update_stats(subfacet, &stats);
5663             }
5664         }
5665
5666         expired.flow = facet->flow;
5667         expired.packet_count = facet->packet_count;
5668         expired.byte_count = facet->byte_count;
5669         expired.used = facet->used;
5670         netflow_expire(ofproto->netflow, &facet->nf_flow, &expired);
5671     }
5672 }
5673
5674 static void
5675 send_netflow_active_timeouts(struct ofproto_dpif *ofproto)
5676 {
5677     struct cls_cursor cursor;
5678     struct facet *facet;
5679
5680     cls_cursor_init(&cursor, &ofproto->facets, NULL);
5681     CLS_CURSOR_FOR_EACH (facet, cr, &cursor) {
5682         send_active_timeout(ofproto, facet);
5683     }
5684 }
5685 \f
5686 static struct ofproto_dpif *
5687 ofproto_dpif_lookup(const char *name)
5688 {
5689     struct ofproto_dpif *ofproto;
5690
5691     HMAP_FOR_EACH_WITH_HASH (ofproto, all_ofproto_dpifs_node,
5692                              hash_string(name, 0), &all_ofproto_dpifs) {
5693         if (!strcmp(ofproto->up.name, name)) {
5694             return ofproto;
5695         }
5696     }
5697     return NULL;
5698 }
5699
5700 static void
5701 ofproto_unixctl_fdb_flush(struct unixctl_conn *conn, int argc,
5702                           const char *argv[], void *aux OVS_UNUSED)
5703 {
5704     struct ofproto_dpif *ofproto;
5705
5706     if (argc > 1) {
5707         ofproto = ofproto_dpif_lookup(argv[1]);
5708         if (!ofproto) {
5709             unixctl_command_reply_error(conn, "no such bridge");
5710             return;
5711         }
5712         mac_learning_flush(ofproto->ml, &ofproto->backer->revalidate_set);
5713     } else {
5714         HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
5715             mac_learning_flush(ofproto->ml, &ofproto->backer->revalidate_set);
5716         }
5717     }
5718
5719     unixctl_command_reply(conn, "table successfully flushed");
5720 }
5721
5722 static void
5723 ofproto_unixctl_fdb_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
5724                          const char *argv[], void *aux OVS_UNUSED)
5725 {
5726     struct ds ds = DS_EMPTY_INITIALIZER;
5727     const struct ofproto_dpif *ofproto;
5728     const struct mac_entry *e;
5729
5730     ofproto = ofproto_dpif_lookup(argv[1]);
5731     if (!ofproto) {
5732         unixctl_command_reply_error(conn, "no such bridge");
5733         return;
5734     }
5735
5736     ds_put_cstr(&ds, " port  VLAN  MAC                Age\n");
5737     LIST_FOR_EACH (e, lru_node, &ofproto->ml->lrus) {
5738         struct ofbundle *bundle = e->port.p;
5739         ds_put_format(&ds, "%5d  %4d  "ETH_ADDR_FMT"  %3d\n",
5740                       ofbundle_get_a_port(bundle)->odp_port,
5741                       e->vlan, ETH_ADDR_ARGS(e->mac),
5742                       mac_entry_age(ofproto->ml, e));
5743     }
5744     unixctl_command_reply(conn, ds_cstr(&ds));
5745     ds_destroy(&ds);
5746 }
5747
5748 struct trace_ctx {
5749     struct xlate_out xout;
5750     struct xlate_in xin;
5751     struct flow flow;
5752     struct ds *result;
5753 };
5754
5755 static void
5756 trace_format_rule(struct ds *result, int level, const struct rule_dpif *rule)
5757 {
5758     ds_put_char_multiple(result, '\t', level);
5759     if (!rule) {
5760         ds_put_cstr(result, "No match\n");
5761         return;
5762     }
5763
5764     ds_put_format(result, "Rule: table=%"PRIu8" cookie=%#"PRIx64" ",
5765                   rule ? rule->up.table_id : 0, ntohll(rule->up.flow_cookie));
5766     cls_rule_format(&rule->up.cr, result);
5767     ds_put_char(result, '\n');
5768
5769     ds_put_char_multiple(result, '\t', level);
5770     ds_put_cstr(result, "OpenFlow ");
5771     ofpacts_format(rule->up.ofpacts, rule->up.ofpacts_len, result);
5772     ds_put_char(result, '\n');
5773 }
5774
5775 static void
5776 trace_format_flow(struct ds *result, int level, const char *title,
5777                   struct trace_ctx *trace)
5778 {
5779     ds_put_char_multiple(result, '\t', level);
5780     ds_put_format(result, "%s: ", title);
5781     if (flow_equal(&trace->xin.flow, &trace->flow)) {
5782         ds_put_cstr(result, "unchanged");
5783     } else {
5784         flow_format(result, &trace->xin.flow);
5785         trace->flow = trace->xin.flow;
5786     }
5787     ds_put_char(result, '\n');
5788 }
5789
5790 static void
5791 trace_format_regs(struct ds *result, int level, const char *title,
5792                   struct trace_ctx *trace)
5793 {
5794     size_t i;
5795
5796     ds_put_char_multiple(result, '\t', level);
5797     ds_put_format(result, "%s:", title);
5798     for (i = 0; i < FLOW_N_REGS; i++) {
5799         ds_put_format(result, " reg%zu=0x%"PRIx32, i, trace->flow.regs[i]);
5800     }
5801     ds_put_char(result, '\n');
5802 }
5803
5804 static void
5805 trace_format_odp(struct ds *result, int level, const char *title,
5806                  struct trace_ctx *trace)
5807 {
5808     struct ofpbuf *odp_actions = &trace->xout.odp_actions;
5809
5810     ds_put_char_multiple(result, '\t', level);
5811     ds_put_format(result, "%s: ", title);
5812     format_odp_actions(result, odp_actions->data, odp_actions->size);
5813     ds_put_char(result, '\n');
5814 }
5815
5816 static void
5817 trace_resubmit(struct xlate_in *xin, struct rule_dpif *rule, int recurse)
5818 {
5819     struct trace_ctx *trace = CONTAINER_OF(xin, struct trace_ctx, xin);
5820     struct ds *result = trace->result;
5821
5822     ds_put_char(result, '\n');
5823     trace_format_flow(result, recurse + 1, "Resubmitted flow", trace);
5824     trace_format_regs(result, recurse + 1, "Resubmitted regs", trace);
5825     trace_format_odp(result,  recurse + 1, "Resubmitted  odp", trace);
5826     trace_format_rule(result, recurse + 1, rule);
5827 }
5828
5829 static void
5830 trace_report(struct xlate_in *xin, const char *s, int recurse)
5831 {
5832     struct trace_ctx *trace = CONTAINER_OF(xin, struct trace_ctx, xin);
5833     struct ds *result = trace->result;
5834
5835     ds_put_char_multiple(result, '\t', recurse);
5836     ds_put_cstr(result, s);
5837     ds_put_char(result, '\n');
5838 }
5839
5840 static void
5841 ofproto_unixctl_trace(struct unixctl_conn *conn, int argc, const char *argv[],
5842                       void *aux OVS_UNUSED)
5843 {
5844     const struct dpif_backer *backer;
5845     struct ofproto_dpif *ofproto;
5846     struct ofpbuf odp_key;
5847     struct ofpbuf *packet;
5848     struct ds result;
5849     struct flow flow;
5850     char *s;
5851
5852     packet = NULL;
5853     backer = NULL;
5854     ds_init(&result);
5855     ofpbuf_init(&odp_key, 0);
5856
5857     /* Handle "-generate" or a hex string as the last argument. */
5858     if (!strcmp(argv[argc - 1], "-generate")) {
5859         packet = ofpbuf_new(0);
5860         argc--;
5861     } else {
5862         const char *error = eth_from_hex(argv[argc - 1], &packet);
5863         if (!error) {
5864             argc--;
5865         } else if (argc == 4) {
5866             /* The 3-argument form must end in "-generate' or a hex string. */
5867             unixctl_command_reply_error(conn, error);
5868             goto exit;
5869         }
5870     }
5871
5872     /* Parse the flow and determine whether a datapath or
5873      * bridge is specified. If function odp_flow_key_from_string()
5874      * returns 0, the flow is a odp_flow. If function
5875      * parse_ofp_exact_flow() returns 0, the flow is a br_flow. */
5876     if (!odp_flow_from_string(argv[argc - 1], NULL, &odp_key, NULL)) {
5877         /* If the odp_flow is the second argument,
5878          * the datapath name is the first argument. */
5879         if (argc == 3) {
5880             const char *dp_type;
5881             if (!strncmp(argv[1], "ovs-", 4)) {
5882                 dp_type = argv[1] + 4;
5883             } else {
5884                 dp_type = argv[1];
5885             }
5886             backer = shash_find_data(&all_dpif_backers, dp_type);
5887             if (!backer) {
5888                 unixctl_command_reply_error(conn, "Cannot find datapath "
5889                                "of this name");
5890                 goto exit;
5891             }
5892         } else {
5893             /* No datapath name specified, so there should be only one
5894              * datapath. */
5895             struct shash_node *node;
5896             if (shash_count(&all_dpif_backers) != 1) {
5897                 unixctl_command_reply_error(conn, "Must specify datapath "
5898                          "name, there is more than one type of datapath");
5899                 goto exit;
5900             }
5901             node = shash_first(&all_dpif_backers);
5902             backer = node->data;
5903         }
5904
5905         /* Extract the ofproto_dpif object from the ofproto_receive()
5906          * function. */
5907         if (ofproto_receive(backer, NULL, odp_key.data,
5908                             odp_key.size, &flow, NULL, &ofproto, NULL)) {
5909             unixctl_command_reply_error(conn, "Invalid datapath flow");
5910             goto exit;
5911         }
5912         ds_put_format(&result, "Bridge: %s\n", ofproto->up.name);
5913     } else if (!parse_ofp_exact_flow(&flow, argv[argc - 1])) {
5914         if (argc != 3) {
5915             unixctl_command_reply_error(conn, "Must specify bridge name");
5916             goto exit;
5917         }
5918
5919         ofproto = ofproto_dpif_lookup(argv[1]);
5920         if (!ofproto) {
5921             unixctl_command_reply_error(conn, "Unknown bridge name");
5922             goto exit;
5923         }
5924     } else {
5925         unixctl_command_reply_error(conn, "Bad flow syntax");
5926         goto exit;
5927     }
5928
5929     /* Generate a packet, if requested. */
5930     if (packet) {
5931         if (!packet->size) {
5932             flow_compose(packet, &flow);
5933         } else {
5934             ds_put_cstr(&result, "Packet: ");
5935             s = ofp_packet_to_string(packet->data, packet->size);
5936             ds_put_cstr(&result, s);
5937             free(s);
5938
5939             /* Use the metadata from the flow and the packet argument
5940              * to reconstruct the flow. */
5941             flow_extract(packet, flow.skb_priority, flow.skb_mark, NULL,
5942                          flow.in_port, &flow);
5943         }
5944     }
5945
5946     ofproto_trace(ofproto, &flow, packet, &result);
5947     unixctl_command_reply(conn, ds_cstr(&result));
5948
5949 exit:
5950     ds_destroy(&result);
5951     ofpbuf_delete(packet);
5952     ofpbuf_uninit(&odp_key);
5953 }
5954
5955 void
5956 ofproto_trace(struct ofproto_dpif *ofproto, const struct flow *flow,
5957               const struct ofpbuf *packet, struct ds *ds)
5958 {
5959     struct rule_dpif *rule;
5960
5961     ds_put_cstr(ds, "Flow: ");
5962     flow_format(ds, flow);
5963     ds_put_char(ds, '\n');
5964
5965     rule = rule_dpif_lookup(ofproto, flow, NULL);
5966
5967     trace_format_rule(ds, 0, rule);
5968     if (rule == ofproto->miss_rule) {
5969         ds_put_cstr(ds, "\nNo match, flow generates \"packet in\"s.\n");
5970     } else if (rule == ofproto->no_packet_in_rule) {
5971         ds_put_cstr(ds, "\nNo match, packets dropped because "
5972                     "OFPPC_NO_PACKET_IN is set on in_port.\n");
5973     } else if (rule == ofproto->drop_frags_rule) {
5974         ds_put_cstr(ds, "\nPackets dropped because they are IP fragments "
5975                     "and the fragment handling mode is \"drop\".\n");
5976     }
5977
5978     if (rule) {
5979         uint64_t odp_actions_stub[1024 / 8];
5980         struct ofpbuf odp_actions;
5981         struct trace_ctx trace;
5982         struct match match;
5983         uint8_t tcp_flags;
5984
5985         tcp_flags = packet ? packet_get_tcp_flags(packet, flow) : 0;
5986         trace.result = ds;
5987         trace.flow = *flow;
5988         ofpbuf_use_stub(&odp_actions,
5989                         odp_actions_stub, sizeof odp_actions_stub);
5990         xlate_in_init(&trace.xin, ofproto, flow, rule, tcp_flags, packet);
5991         trace.xin.resubmit_hook = trace_resubmit;
5992         trace.xin.report_hook = trace_report;
5993
5994         xlate_actions(&trace.xin, &trace.xout);
5995
5996         ds_put_char(ds, '\n');
5997         trace_format_flow(ds, 0, "Final flow", &trace);
5998
5999         match_init(&match, flow, &trace.xout.wc);
6000         ds_put_cstr(ds, "Relevant fields: ");
6001         match_format(&match, ds, OFP_DEFAULT_PRIORITY);
6002         ds_put_char(ds, '\n');
6003
6004         ds_put_cstr(ds, "Datapath actions: ");
6005         format_odp_actions(ds, trace.xout.odp_actions.data,
6006                            trace.xout.odp_actions.size);
6007
6008         if (trace.xout.slow) {
6009             ds_put_cstr(ds, "\nThis flow is handled by the userspace "
6010                         "slow path because it:");
6011             switch (trace.xout.slow) {
6012             case SLOW_CFM:
6013                 ds_put_cstr(ds, "\n\t- Consists of CFM packets.");
6014                 break;
6015             case SLOW_LACP:
6016                 ds_put_cstr(ds, "\n\t- Consists of LACP packets.");
6017                 break;
6018             case SLOW_STP:
6019                 ds_put_cstr(ds, "\n\t- Consists of STP packets.");
6020                 break;
6021             case SLOW_BFD:
6022                 ds_put_cstr(ds, "\n\t- Consists of BFD packets.");
6023                 break;
6024             case SLOW_CONTROLLER:
6025                 ds_put_cstr(ds, "\n\t- Sends \"packet-in\" messages "
6026                             "to the OpenFlow controller.");
6027                 break;
6028             case __SLOW_MAX:
6029                 NOT_REACHED();
6030             }
6031         }
6032
6033         xlate_out_uninit(&trace.xout);
6034     }
6035 }
6036
6037 static void
6038 ofproto_dpif_clog(struct unixctl_conn *conn OVS_UNUSED, int argc OVS_UNUSED,
6039                   const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
6040 {
6041     clogged = true;
6042     unixctl_command_reply(conn, NULL);
6043 }
6044
6045 static void
6046 ofproto_dpif_unclog(struct unixctl_conn *conn OVS_UNUSED, int argc OVS_UNUSED,
6047                     const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
6048 {
6049     clogged = false;
6050     unixctl_command_reply(conn, NULL);
6051 }
6052
6053 /* Runs a self-check of flow translations in 'ofproto'.  Appends a message to
6054  * 'reply' describing the results. */
6055 static void
6056 ofproto_dpif_self_check__(struct ofproto_dpif *ofproto, struct ds *reply)
6057 {
6058     struct cls_cursor cursor;
6059     struct facet *facet;
6060     int errors;
6061
6062     errors = 0;
6063     cls_cursor_init(&cursor, &ofproto->facets, NULL);
6064     CLS_CURSOR_FOR_EACH (facet, cr, &cursor) {
6065         if (!facet_check_consistency(facet)) {
6066             errors++;
6067         }
6068     }
6069     if (errors) {
6070         ofproto->backer->need_revalidate = REV_INCONSISTENCY;
6071     }
6072
6073     if (errors) {
6074         ds_put_format(reply, "%s: self-check failed (%d errors)\n",
6075                       ofproto->up.name, errors);
6076     } else {
6077         ds_put_format(reply, "%s: self-check passed\n", ofproto->up.name);
6078     }
6079 }
6080
6081 static void
6082 ofproto_dpif_self_check(struct unixctl_conn *conn,
6083                         int argc, const char *argv[], void *aux OVS_UNUSED)
6084 {
6085     struct ds reply = DS_EMPTY_INITIALIZER;
6086     struct ofproto_dpif *ofproto;
6087
6088     if (argc > 1) {
6089         ofproto = ofproto_dpif_lookup(argv[1]);
6090         if (!ofproto) {
6091             unixctl_command_reply_error(conn, "Unknown ofproto (use "
6092                                         "ofproto/list for help)");
6093             return;
6094         }
6095         ofproto_dpif_self_check__(ofproto, &reply);
6096     } else {
6097         HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
6098             ofproto_dpif_self_check__(ofproto, &reply);
6099         }
6100     }
6101
6102     unixctl_command_reply(conn, ds_cstr(&reply));
6103     ds_destroy(&reply);
6104 }
6105
6106 /* Store the current ofprotos in 'ofproto_shash'.  Returns a sorted list
6107  * of the 'ofproto_shash' nodes.  It is the responsibility of the caller
6108  * to destroy 'ofproto_shash' and free the returned value. */
6109 static const struct shash_node **
6110 get_ofprotos(struct shash *ofproto_shash)
6111 {
6112     const struct ofproto_dpif *ofproto;
6113
6114     HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
6115         char *name = xasprintf("%s@%s", ofproto->up.type, ofproto->up.name);
6116         shash_add_nocopy(ofproto_shash, name, ofproto);
6117     }
6118
6119     return shash_sort(ofproto_shash);
6120 }
6121
6122 static void
6123 ofproto_unixctl_dpif_dump_dps(struct unixctl_conn *conn, int argc OVS_UNUSED,
6124                               const char *argv[] OVS_UNUSED,
6125                               void *aux OVS_UNUSED)
6126 {
6127     struct ds ds = DS_EMPTY_INITIALIZER;
6128     struct shash ofproto_shash;
6129     const struct shash_node **sorted_ofprotos;
6130     int i;
6131
6132     shash_init(&ofproto_shash);
6133     sorted_ofprotos = get_ofprotos(&ofproto_shash);
6134     for (i = 0; i < shash_count(&ofproto_shash); i++) {
6135         const struct shash_node *node = sorted_ofprotos[i];
6136         ds_put_format(&ds, "%s\n", node->name);
6137     }
6138
6139     shash_destroy(&ofproto_shash);
6140     free(sorted_ofprotos);
6141
6142     unixctl_command_reply(conn, ds_cstr(&ds));
6143     ds_destroy(&ds);
6144 }
6145
6146 static void
6147 show_dp_rates(struct ds *ds, const char *heading,
6148               const struct avg_subfacet_rates *rates)
6149 {
6150     ds_put_format(ds, "%s add rate: %5.3f/min, del rate: %5.3f/min\n",
6151                   heading, rates->add_rate, rates->del_rate);
6152 }
6153
6154 static void
6155 dpif_show_backer(const struct dpif_backer *backer, struct ds *ds)
6156 {
6157     const struct shash_node **ofprotos;
6158     struct ofproto_dpif *ofproto;
6159     struct shash ofproto_shash;
6160     uint64_t n_hit, n_missed;
6161     long long int minutes;
6162     size_t i;
6163
6164     n_hit = n_missed = 0;
6165     HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
6166         if (ofproto->backer == backer) {
6167             n_missed += ofproto->n_missed;
6168             n_hit += ofproto->n_hit;
6169         }
6170     }
6171
6172     ds_put_format(ds, "%s: hit:%"PRIu64" missed:%"PRIu64"\n",
6173                   dpif_name(backer->dpif), n_hit, n_missed);
6174     ds_put_format(ds, "\tflows: cur: %zu, avg: %u, max: %u,"
6175                   " life span: %lldms\n", hmap_count(&backer->subfacets),
6176                   backer->avg_n_subfacet, backer->max_n_subfacet,
6177                   backer->avg_subfacet_life);
6178
6179     minutes = (time_msec() - backer->created) / (1000 * 60);
6180     if (minutes >= 60) {
6181         show_dp_rates(ds, "\thourly avg:", &backer->hourly);
6182     }
6183     if (minutes >= 60 * 24) {
6184         show_dp_rates(ds, "\tdaily avg:",  &backer->daily);
6185     }
6186     show_dp_rates(ds, "\toverall avg:",  &backer->lifetime);
6187
6188     shash_init(&ofproto_shash);
6189     ofprotos = get_ofprotos(&ofproto_shash);
6190     for (i = 0; i < shash_count(&ofproto_shash); i++) {
6191         struct ofproto_dpif *ofproto = ofprotos[i]->data;
6192         const struct shash_node **ports;
6193         size_t j;
6194
6195         if (ofproto->backer != backer) {
6196             continue;
6197         }
6198
6199         ds_put_format(ds, "\t%s: hit:%"PRIu64" missed:%"PRIu64"\n",
6200                       ofproto->up.name, ofproto->n_hit, ofproto->n_missed);
6201
6202         ports = shash_sort(&ofproto->up.port_by_name);
6203         for (j = 0; j < shash_count(&ofproto->up.port_by_name); j++) {
6204             const struct shash_node *node = ports[j];
6205             struct ofport *ofport = node->data;
6206             struct smap config;
6207             uint32_t odp_port;
6208
6209             ds_put_format(ds, "\t\t%s %u/", netdev_get_name(ofport->netdev),
6210                           ofport->ofp_port);
6211
6212             odp_port = ofp_port_to_odp_port(ofproto, ofport->ofp_port);
6213             if (odp_port != OVSP_NONE) {
6214                 ds_put_format(ds, "%"PRIu32":", odp_port);
6215             } else {
6216                 ds_put_cstr(ds, "none:");
6217             }
6218
6219             ds_put_format(ds, " (%s", netdev_get_type(ofport->netdev));
6220
6221             smap_init(&config);
6222             if (!netdev_get_config(ofport->netdev, &config)) {
6223                 const struct smap_node **nodes;
6224                 size_t i;
6225
6226                 nodes = smap_sort(&config);
6227                 for (i = 0; i < smap_count(&config); i++) {
6228                     const struct smap_node *node = nodes[i];
6229                     ds_put_format(ds, "%c %s=%s", i ? ',' : ':',
6230                                   node->key, node->value);
6231                 }
6232                 free(nodes);
6233             }
6234             smap_destroy(&config);
6235
6236             ds_put_char(ds, ')');
6237             ds_put_char(ds, '\n');
6238         }
6239         free(ports);
6240     }
6241     shash_destroy(&ofproto_shash);
6242     free(ofprotos);
6243 }
6244
6245 static void
6246 ofproto_unixctl_dpif_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
6247                           const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
6248 {
6249     struct ds ds = DS_EMPTY_INITIALIZER;
6250     const struct shash_node **backers;
6251     int i;
6252
6253     backers = shash_sort(&all_dpif_backers);
6254     for (i = 0; i < shash_count(&all_dpif_backers); i++) {
6255         dpif_show_backer(backers[i]->data, &ds);
6256     }
6257     free(backers);
6258
6259     unixctl_command_reply(conn, ds_cstr(&ds));
6260     ds_destroy(&ds);
6261 }
6262
6263 /* Dump the megaflow (facet) cache.  This is useful to check the
6264  * correctness of flow wildcarding, since the same mechanism is used for
6265  * both xlate caching and kernel wildcarding.
6266  *
6267  * It's important to note that in the output the flow description uses
6268  * OpenFlow (OFP) ports, but the actions use datapath (ODP) ports.
6269  *
6270  * This command is only needed for advanced debugging, so it's not
6271  * documented in the man page. */
6272 static void
6273 ofproto_unixctl_dpif_dump_megaflows(struct unixctl_conn *conn,
6274                                     int argc OVS_UNUSED, const char *argv[],
6275                                     void *aux OVS_UNUSED)
6276 {
6277     struct ds ds = DS_EMPTY_INITIALIZER;
6278     const struct ofproto_dpif *ofproto;
6279     long long int now = time_msec();
6280     struct cls_cursor cursor;
6281     struct facet *facet;
6282
6283     ofproto = ofproto_dpif_lookup(argv[1]);
6284     if (!ofproto) {
6285         unixctl_command_reply_error(conn, "no such bridge");
6286         return;
6287     }
6288
6289     cls_cursor_init(&cursor, &ofproto->facets, NULL);
6290     CLS_CURSOR_FOR_EACH (facet, cr, &cursor) {
6291         cls_rule_format(&facet->cr, &ds);
6292         ds_put_cstr(&ds, ", ");
6293         ds_put_format(&ds, "n_subfacets:%zu, ", list_size(&facet->subfacets));
6294         ds_put_format(&ds, "used:%.3fs, ", (now - facet->used) / 1000.0);
6295         ds_put_cstr(&ds, "Datapath actions: ");
6296         if (facet->xout.slow) {
6297             uint64_t slow_path_stub[128 / 8];
6298             const struct nlattr *actions;
6299             size_t actions_len;
6300
6301             compose_slow_path(ofproto, &facet->flow, facet->xout.slow,
6302                               slow_path_stub, sizeof slow_path_stub,
6303                               &actions, &actions_len);
6304             format_odp_actions(&ds, actions, actions_len);
6305         } else {
6306             format_odp_actions(&ds, facet->xout.odp_actions.data,
6307                                facet->xout.odp_actions.size);
6308         }
6309         ds_put_cstr(&ds, "\n");
6310     }
6311
6312     ds_chomp(&ds, '\n');
6313     unixctl_command_reply(conn, ds_cstr(&ds));
6314     ds_destroy(&ds);
6315 }
6316
6317 static void
6318 ofproto_unixctl_dpif_dump_flows(struct unixctl_conn *conn,
6319                                 int argc OVS_UNUSED, const char *argv[],
6320                                 void *aux OVS_UNUSED)
6321 {
6322     struct ds ds = DS_EMPTY_INITIALIZER;
6323     const struct ofproto_dpif *ofproto;
6324     struct subfacet *subfacet;
6325
6326     ofproto = ofproto_dpif_lookup(argv[1]);
6327     if (!ofproto) {
6328         unixctl_command_reply_error(conn, "no such bridge");
6329         return;
6330     }
6331
6332     update_stats(ofproto->backer);
6333
6334     HMAP_FOR_EACH (subfacet, hmap_node, &ofproto->backer->subfacets) {
6335         struct facet *facet = subfacet->facet;
6336
6337         if (ofproto_dpif_cast(facet->rule->up.ofproto) != ofproto) {
6338             continue;
6339         }
6340
6341         odp_flow_key_format(subfacet->key, subfacet->key_len, &ds);
6342
6343         ds_put_format(&ds, ", packets:%"PRIu64", bytes:%"PRIu64", used:",
6344                       subfacet->dp_packet_count, subfacet->dp_byte_count);
6345         if (subfacet->used) {
6346             ds_put_format(&ds, "%.3fs",
6347                           (time_msec() - subfacet->used) / 1000.0);
6348         } else {
6349             ds_put_format(&ds, "never");
6350         }
6351         if (subfacet->facet->tcp_flags) {
6352             ds_put_cstr(&ds, ", flags:");
6353             packet_format_tcp_flags(&ds, subfacet->facet->tcp_flags);
6354         }
6355
6356         ds_put_cstr(&ds, ", actions:");
6357         if (facet->xout.slow) {
6358             uint64_t slow_path_stub[128 / 8];
6359             const struct nlattr *actions;
6360             size_t actions_len;
6361
6362             compose_slow_path(ofproto, &facet->flow, facet->xout.slow,
6363                               slow_path_stub, sizeof slow_path_stub,
6364                               &actions, &actions_len);
6365             format_odp_actions(&ds, actions, actions_len);
6366         } else {
6367             format_odp_actions(&ds, facet->xout.odp_actions.data,
6368                                facet->xout.odp_actions.size);
6369         }
6370         ds_put_char(&ds, '\n');
6371     }
6372
6373     unixctl_command_reply(conn, ds_cstr(&ds));
6374     ds_destroy(&ds);
6375 }
6376
6377 static void
6378 ofproto_unixctl_dpif_del_flows(struct unixctl_conn *conn,
6379                                int argc OVS_UNUSED, const char *argv[],
6380                                void *aux OVS_UNUSED)
6381 {
6382     struct ds ds = DS_EMPTY_INITIALIZER;
6383     struct ofproto_dpif *ofproto;
6384
6385     ofproto = ofproto_dpif_lookup(argv[1]);
6386     if (!ofproto) {
6387         unixctl_command_reply_error(conn, "no such bridge");
6388         return;
6389     }
6390
6391     flush(&ofproto->up);
6392
6393     unixctl_command_reply(conn, ds_cstr(&ds));
6394     ds_destroy(&ds);
6395 }
6396
6397 static void
6398 ofproto_dpif_unixctl_init(void)
6399 {
6400     static bool registered;
6401     if (registered) {
6402         return;
6403     }
6404     registered = true;
6405
6406     unixctl_command_register(
6407         "ofproto/trace",
6408         "[dp_name]|bridge odp_flow|br_flow [-generate|packet]",
6409         1, 3, ofproto_unixctl_trace, NULL);
6410     unixctl_command_register("fdb/flush", "[bridge]", 0, 1,
6411                              ofproto_unixctl_fdb_flush, NULL);
6412     unixctl_command_register("fdb/show", "bridge", 1, 1,
6413                              ofproto_unixctl_fdb_show, NULL);
6414     unixctl_command_register("ofproto/clog", "", 0, 0,
6415                              ofproto_dpif_clog, NULL);
6416     unixctl_command_register("ofproto/unclog", "", 0, 0,
6417                              ofproto_dpif_unclog, NULL);
6418     unixctl_command_register("ofproto/self-check", "[bridge]", 0, 1,
6419                              ofproto_dpif_self_check, NULL);
6420     unixctl_command_register("dpif/dump-dps", "", 0, 0,
6421                              ofproto_unixctl_dpif_dump_dps, NULL);
6422     unixctl_command_register("dpif/show", "", 0, 0, ofproto_unixctl_dpif_show,
6423                              NULL);
6424     unixctl_command_register("dpif/dump-flows", "bridge", 1, 1,
6425                              ofproto_unixctl_dpif_dump_flows, NULL);
6426     unixctl_command_register("dpif/del-flows", "bridge", 1, 1,
6427                              ofproto_unixctl_dpif_del_flows, NULL);
6428     unixctl_command_register("dpif/dump-megaflows", "bridge", 1, 1,
6429                              ofproto_unixctl_dpif_dump_megaflows, NULL);
6430 }
6431 \f
6432 /* Linux VLAN device support (e.g. "eth0.10" for VLAN 10.)
6433  *
6434  * This is deprecated.  It is only for compatibility with broken device drivers
6435  * in old versions of Linux that do not properly support VLANs when VLAN
6436  * devices are not used.  When broken device drivers are no longer in
6437  * widespread use, we will delete these interfaces. */
6438
6439 static int
6440 set_realdev(struct ofport *ofport_, uint16_t realdev_ofp_port, int vid)
6441 {
6442     struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofport_->ofproto);
6443     struct ofport_dpif *ofport = ofport_dpif_cast(ofport_);
6444
6445     if (realdev_ofp_port == ofport->realdev_ofp_port
6446         && vid == ofport->vlandev_vid) {
6447         return 0;
6448     }
6449
6450     ofproto->backer->need_revalidate = REV_RECONFIGURE;
6451
6452     if (ofport->realdev_ofp_port) {
6453         vsp_remove(ofport);
6454     }
6455     if (realdev_ofp_port && ofport->bundle) {
6456         /* vlandevs are enslaved to their realdevs, so they are not allowed to
6457          * themselves be part of a bundle. */
6458         bundle_set(ofport->up.ofproto, ofport->bundle, NULL);
6459     }
6460
6461     ofport->realdev_ofp_port = realdev_ofp_port;
6462     ofport->vlandev_vid = vid;
6463
6464     if (realdev_ofp_port) {
6465         vsp_add(ofport, realdev_ofp_port, vid);
6466     }
6467
6468     return 0;
6469 }
6470
6471 static uint32_t
6472 hash_realdev_vid(uint16_t realdev_ofp_port, int vid)
6473 {
6474     return hash_2words(realdev_ofp_port, vid);
6475 }
6476
6477 /* Returns the OFP port number of the Linux VLAN device that corresponds to
6478  * 'vlan_tci' on the network device with port number 'realdev_ofp_port' in
6479  * 'struct ofport_dpif'.  For example, given 'realdev_ofp_port' of eth0 and
6480  * 'vlan_tci' 9, it would return the port number of eth0.9.
6481  *
6482  * Unless VLAN splinters are enabled for port 'realdev_ofp_port', this
6483  * function just returns its 'realdev_ofp_port' argument. */
6484 uint16_t
6485 vsp_realdev_to_vlandev(const struct ofproto_dpif *ofproto,
6486                        uint16_t realdev_ofp_port, ovs_be16 vlan_tci)
6487 {
6488     if (!hmap_is_empty(&ofproto->realdev_vid_map)) {
6489         int vid = vlan_tci_to_vid(vlan_tci);
6490         const struct vlan_splinter *vsp;
6491
6492         HMAP_FOR_EACH_WITH_HASH (vsp, realdev_vid_node,
6493                                  hash_realdev_vid(realdev_ofp_port, vid),
6494                                  &ofproto->realdev_vid_map) {
6495             if (vsp->realdev_ofp_port == realdev_ofp_port
6496                 && vsp->vid == vid) {
6497                 return vsp->vlandev_ofp_port;
6498             }
6499         }
6500     }
6501     return realdev_ofp_port;
6502 }
6503
6504 static struct vlan_splinter *
6505 vlandev_find(const struct ofproto_dpif *ofproto, uint16_t vlandev_ofp_port)
6506 {
6507     struct vlan_splinter *vsp;
6508
6509     HMAP_FOR_EACH_WITH_HASH (vsp, vlandev_node, hash_int(vlandev_ofp_port, 0),
6510                              &ofproto->vlandev_map) {
6511         if (vsp->vlandev_ofp_port == vlandev_ofp_port) {
6512             return vsp;
6513         }
6514     }
6515
6516     return NULL;
6517 }
6518
6519 /* Returns the OpenFlow port number of the "real" device underlying the Linux
6520  * VLAN device with OpenFlow port number 'vlandev_ofp_port' and stores the
6521  * VLAN VID of the Linux VLAN device in '*vid'.  For example, given
6522  * 'vlandev_ofp_port' of eth0.9, it would return the OpenFlow port number of
6523  * eth0 and store 9 in '*vid'.
6524  *
6525  * Returns 0 and does not modify '*vid' if 'vlandev_ofp_port' is not a Linux
6526  * VLAN device.  Unless VLAN splinters are enabled, this is what this function
6527  * always does.*/
6528 static uint16_t
6529 vsp_vlandev_to_realdev(const struct ofproto_dpif *ofproto,
6530                        uint16_t vlandev_ofp_port, int *vid)
6531 {
6532     if (!hmap_is_empty(&ofproto->vlandev_map)) {
6533         const struct vlan_splinter *vsp;
6534
6535         vsp = vlandev_find(ofproto, vlandev_ofp_port);
6536         if (vsp) {
6537             if (vid) {
6538                 *vid = vsp->vid;
6539             }
6540             return vsp->realdev_ofp_port;
6541         }
6542     }
6543     return 0;
6544 }
6545
6546 /* Given 'flow', a flow representing a packet received on 'ofproto', checks
6547  * whether 'flow->in_port' represents a Linux VLAN device.  If so, changes
6548  * 'flow->in_port' to the "real" device backing the VLAN device, sets
6549  * 'flow->vlan_tci' to the VLAN VID, and returns true.  Otherwise (which is
6550  * always the case unless VLAN splinters are enabled), returns false without
6551  * making any changes. */
6552 static bool
6553 vsp_adjust_flow(const struct ofproto_dpif *ofproto, struct flow *flow)
6554 {
6555     uint16_t realdev;
6556     int vid;
6557
6558     realdev = vsp_vlandev_to_realdev(ofproto, flow->in_port, &vid);
6559     if (!realdev) {
6560         return false;
6561     }
6562
6563     /* Cause the flow to be processed as if it came in on the real device with
6564      * the VLAN device's VLAN ID. */
6565     flow->in_port = realdev;
6566     flow->vlan_tci = htons((vid & VLAN_VID_MASK) | VLAN_CFI);
6567     return true;
6568 }
6569
6570 static void
6571 vsp_remove(struct ofport_dpif *port)
6572 {
6573     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
6574     struct vlan_splinter *vsp;
6575
6576     vsp = vlandev_find(ofproto, port->up.ofp_port);
6577     if (vsp) {
6578         hmap_remove(&ofproto->vlandev_map, &vsp->vlandev_node);
6579         hmap_remove(&ofproto->realdev_vid_map, &vsp->realdev_vid_node);
6580         free(vsp);
6581
6582         port->realdev_ofp_port = 0;
6583     } else {
6584         VLOG_ERR("missing vlan device record");
6585     }
6586 }
6587
6588 static void
6589 vsp_add(struct ofport_dpif *port, uint16_t realdev_ofp_port, int vid)
6590 {
6591     struct ofproto_dpif *ofproto = ofproto_dpif_cast(port->up.ofproto);
6592
6593     if (!vsp_vlandev_to_realdev(ofproto, port->up.ofp_port, NULL)
6594         && (vsp_realdev_to_vlandev(ofproto, realdev_ofp_port, htons(vid))
6595             == realdev_ofp_port)) {
6596         struct vlan_splinter *vsp;
6597
6598         vsp = xmalloc(sizeof *vsp);
6599         hmap_insert(&ofproto->vlandev_map, &vsp->vlandev_node,
6600                     hash_int(port->up.ofp_port, 0));
6601         hmap_insert(&ofproto->realdev_vid_map, &vsp->realdev_vid_node,
6602                     hash_realdev_vid(realdev_ofp_port, vid));
6603         vsp->realdev_ofp_port = realdev_ofp_port;
6604         vsp->vlandev_ofp_port = port->up.ofp_port;
6605         vsp->vid = vid;
6606
6607         port->realdev_ofp_port = realdev_ofp_port;
6608     } else {
6609         VLOG_ERR("duplicate vlan device record");
6610     }
6611 }
6612
6613 uint32_t
6614 ofp_port_to_odp_port(const struct ofproto_dpif *ofproto, uint16_t ofp_port)
6615 {
6616     const struct ofport_dpif *ofport = get_ofp_port(ofproto, ofp_port);
6617     return ofport ? ofport->odp_port : OVSP_NONE;
6618 }
6619
6620 static struct ofport_dpif *
6621 odp_port_to_ofport(const struct dpif_backer *backer, uint32_t odp_port)
6622 {
6623     struct ofport_dpif *port;
6624
6625     HMAP_FOR_EACH_IN_BUCKET (port, odp_port_node,
6626                              hash_int(odp_port, 0),
6627                              &backer->odp_to_ofport_map) {
6628         if (port->odp_port == odp_port) {
6629             return port;
6630         }
6631     }
6632
6633     return NULL;
6634 }
6635
6636 static uint16_t
6637 odp_port_to_ofp_port(const struct ofproto_dpif *ofproto, uint32_t odp_port)
6638 {
6639     struct ofport_dpif *port;
6640
6641     port = odp_port_to_ofport(ofproto->backer, odp_port);
6642     if (port && &ofproto->up == port->up.ofproto) {
6643         return port->up.ofp_port;
6644     } else {
6645         return OFPP_NONE;
6646     }
6647 }
6648
6649 /* Compute exponentially weighted moving average, adding 'new' as the newest,
6650  * most heavily weighted element.  'base' designates the rate of decay: after
6651  * 'base' further updates, 'new''s weight in the EWMA decays to about 1/e
6652  * (about .37). */
6653 static void
6654 exp_mavg(double *avg, int base, double new)
6655 {
6656     *avg = (*avg * (base - 1) + new) / base;
6657 }
6658
6659 static void
6660 update_moving_averages(struct dpif_backer *backer)
6661 {
6662     const int min_ms = 60 * 1000; /* milliseconds in one minute. */
6663     long long int minutes = (time_msec() - backer->created) / min_ms;
6664
6665     if (minutes > 0) {
6666         backer->lifetime.add_rate = (double) backer->total_subfacet_add_count
6667             / minutes;
6668         backer->lifetime.del_rate = (double) backer->total_subfacet_del_count
6669             / minutes;
6670     } else {
6671         backer->lifetime.add_rate = 0.0;
6672         backer->lifetime.del_rate = 0.0;
6673     }
6674
6675     /* Update hourly averages on the minute boundaries. */
6676     if (time_msec() - backer->last_minute >= min_ms) {
6677         exp_mavg(&backer->hourly.add_rate, 60, backer->subfacet_add_count);
6678         exp_mavg(&backer->hourly.del_rate, 60, backer->subfacet_del_count);
6679
6680         /* Update daily averages on the hour boundaries. */
6681         if ((backer->last_minute - backer->created) / min_ms % 60 == 59) {
6682             exp_mavg(&backer->daily.add_rate, 24, backer->hourly.add_rate);
6683             exp_mavg(&backer->daily.del_rate, 24, backer->hourly.del_rate);
6684         }
6685
6686         backer->total_subfacet_add_count += backer->subfacet_add_count;
6687         backer->total_subfacet_del_count += backer->subfacet_del_count;
6688         backer->subfacet_add_count = 0;
6689         backer->subfacet_del_count = 0;
6690         backer->last_minute += min_ms;
6691     }
6692 }
6693
6694 const struct ofproto_class ofproto_dpif_class = {
6695     init,
6696     enumerate_types,
6697     enumerate_names,
6698     del,
6699     port_open_type,
6700     type_run,
6701     type_run_fast,
6702     type_wait,
6703     alloc,
6704     construct,
6705     destruct,
6706     dealloc,
6707     run,
6708     run_fast,
6709     wait,
6710     get_memory_usage,
6711     flush,
6712     get_features,
6713     get_tables,
6714     port_alloc,
6715     port_construct,
6716     port_destruct,
6717     port_dealloc,
6718     port_modified,
6719     port_reconfigured,
6720     port_query_by_name,
6721     port_add,
6722     port_del,
6723     port_get_stats,
6724     port_dump_start,
6725     port_dump_next,
6726     port_dump_done,
6727     port_poll,
6728     port_poll_wait,
6729     port_is_lacp_current,
6730     NULL,                       /* rule_choose_table */
6731     rule_alloc,
6732     rule_construct,
6733     rule_destruct,
6734     rule_dealloc,
6735     rule_get_stats,
6736     rule_execute,
6737     rule_modify_actions,
6738     set_frag_handling,
6739     packet_out,
6740     set_netflow,
6741     get_netflow_ids,
6742     set_sflow,
6743     set_ipfix,
6744     set_cfm,
6745     get_cfm_status,
6746     set_bfd,
6747     get_bfd_status,
6748     set_stp,
6749     get_stp_status,
6750     set_stp_port,
6751     get_stp_port_status,
6752     set_queues,
6753     bundle_set,
6754     bundle_remove,
6755     mirror_set,
6756     mirror_get_stats,
6757     set_flood_vlans,
6758     is_mirror_output_bundle,
6759     forward_bpdu_changed,
6760     set_mac_table_config,
6761     set_realdev,
6762 };