ovn/controller/ofctrl.c

   1 /* Copyright (c) 2015, 2016 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17 #include "bitmap.h"
  18 #include "byte-order.h"
  19 #include "dirs.h"
  20 #include "flow.h"
  21 #include "hash.h"
  22 #include "hindex.h"
  23 #include "ofctrl.h"
  24 #include "openflow/openflow.h"
  25 #include "openvswitch/dynamic-string.h"
  26 #include "openvswitch/hmap.h"
  27 #include "openvswitch/list.h"
  28 #include "openvswitch/match.h"
  29 #include "openvswitch/ofp-actions.h"
  30 #include "openvswitch/ofp-msgs.h"
  31 #include "openvswitch/ofp-parse.h"
  32 #include "openvswitch/ofp-print.h"
  33 #include "openvswitch/ofp-util.h"
  34 #include "openvswitch/ofpbuf.h"
  35 #include "openvswitch/vlog.h"
  36 #include "ovn-controller.h"
  37 #include "ovn/lib/actions.h"
  38 #include "poll-loop.h"
  39 #include "physical.h"
  40 #include "rconn.h"
  41 #include "socket-util.h"
  42 #include "util.h"
  43 #include "vswitch-idl.h"
  44
  45 VLOG_DEFINE_THIS_MODULE(ofctrl);
  46
  47 /* An OpenFlow flow. */
  48 struct ovn_flow {
  49     struct hmap_node match_hmap_node; /* For match based hashing. */
  50     struct hindex_node uuid_hindex_node; /* For uuid based hashing. */
  51     struct ovs_list list_node; /* For handling lists of flows. */
  52
  53     /* Key. */
  54     uint8_t table_id;
  55     uint16_t priority;
  56     struct match match;
  57
  58     /* Data. UUID is used for disambiguation. */
  59     struct uuid uuid;
  60     struct ofpact *ofpacts;
  61     size_t ofpacts_len;
  62 };
  63
  64 static uint32_t ovn_flow_match_hash(const struct ovn_flow *);
  65 static void ovn_flow_lookup(struct hmap *, const struct ovn_flow *target,
  66                             struct ovs_list *answers);
  67 static char *ovn_flow_to_string(const struct ovn_flow *);
  68 static void ovn_flow_log(const struct ovn_flow *, const char *action);
  69 static void ovn_flow_destroy(struct ovn_flow *);
  70
  71 static ovs_be32 queue_msg(struct ofpbuf *);
  72 static void queue_flow_mod(struct ofputil_flow_mod *);
  73
  74 /* OpenFlow connection to the switch. */
  75 static struct rconn *swconn;
  76
  77 static void queue_group_mod(struct ofputil_group_mod *);
  78
  79 /* Last seen sequence number for 'swconn'.  When this differs from
  80  * rconn_get_connection_seqno(rconn), 'swconn' has reconnected. */
  81 static unsigned int seqno;
  82
  83 /* Connection state machine. */
  84 #define STATES                                  \
  85     STATE(S_NEW)                                \
  86     STATE(S_TLV_TABLE_REQUESTED)                \
  87     STATE(S_TLV_TABLE_MOD_SENT)                 \
  88     STATE(S_CLEAR_FLOWS)                        \
  89     STATE(S_UPDATE_FLOWS)
  90 enum ofctrl_state {
  91 #define STATE(NAME) NAME,
  92     STATES
  93 #undef STATE
  94 };
  95
  96 /* Current state. */
  97 static enum ofctrl_state state;
  98
  99 /* Transaction IDs for messages in flight to the switch. */
 100 static ovs_be32 xid, xid2;
 101
 102 /* Counter for in-flight OpenFlow messages on 'swconn'.  We only send a new
 103  * round of flow table modifications to the switch when the counter falls to
 104  * zero, to avoid unbounded buffering. */
 105 static struct rconn_packet_counter *tx_counter;
 106
 107 /* Flow table of "struct ovn_flow"s, that holds the flow table currently
 108  * installed in the switch. */
 109 static struct hmap installed_flows;
 110
 111 /* A reference to the group_table. */
 112 static struct group_table *groups;
 113
 114 /* MFF_* field ID for our Geneve option.  In S_TLV_TABLE_MOD_SENT, this is
 115  * the option we requested (we don't know whether we obtained it yet).  In
 116  * S_CLEAR_FLOWS or S_UPDATE_FLOWS, this is really the option we have. */
 117 static enum mf_field_id mff_ovn_geneve;
 118
 119 static void ovn_flow_table_destroy(void);
 120
 121 static void ovn_group_table_clear(struct group_table *group_table,
 122                                   bool existing);
 123
 124 static void ofctrl_recv(const struct ofp_header *, enum ofptype);
 125
 126 static struct hmap match_flow_table = HMAP_INITIALIZER(&match_flow_table);
 127 static struct hindex uuid_flow_table = HINDEX_INITIALIZER(&uuid_flow_table);
 128
 129 void
 130 ofctrl_init(void)
 131 {
 132     swconn = rconn_create(5, 0, DSCP_DEFAULT, 1 << OFP13_VERSION);
 133     tx_counter = rconn_packet_counter_create();
 134     hmap_init(&installed_flows);
 135 }
 136 \f
 137 /* S_NEW, for a new connection.
 138  *
 139  * Sends NXT_TLV_TABLE_REQUEST and transitions to
 140  * S_TLV_TABLE_REQUESTED. */
 141
 142 static void
 143 run_S_NEW(void)
 144 {
 145     struct ofpbuf *buf = ofpraw_alloc(OFPRAW_NXT_TLV_TABLE_REQUEST,
 146                                       rconn_get_version(swconn), 0);
 147     xid = queue_msg(buf);
 148     state = S_TLV_TABLE_REQUESTED;
 149 }
 150
 151 static void
 152 recv_S_NEW(const struct ofp_header *oh OVS_UNUSED,
 153            enum ofptype type OVS_UNUSED)
 154 {
 155     OVS_NOT_REACHED();
 156 }
 157 \f
 158 /* S_TLV_TABLE_REQUESTED, when NXT_TLV_TABLE_REQUEST has been sent
 159  * and we're waiting for a reply.
 160  *
 161  * If we receive an NXT_TLV_TABLE_REPLY:
 162  *
 163  *     - If it contains our tunnel metadata option, assign its field ID to
 164  *       mff_ovn_geneve and transition to S_CLEAR_FLOWS.
 165  *
 166  *     - Otherwise, if there is an unused tunnel metadata field ID, send
 167  *       NXT_TLV_TABLE_MOD and OFPT_BARRIER_REQUEST, and transition to
 168  *       S_TLV_TABLE_MOD_SENT.
 169  *
 170  *     - Otherwise, log an error, disable Geneve, and transition to
 171  *       S_CLEAR_FLOWS.
 172  *
 173  * If we receive an OFPT_ERROR:
 174  *
 175  *     - Log an error, disable Geneve, and transition to S_CLEAR_FLOWS. */
 176
 177 static void
 178 run_S_TLV_TABLE_REQUESTED(void)
 179 {
 180 }
 181
 182 static void
 183 recv_S_TLV_TABLE_REQUESTED(const struct ofp_header *oh, enum ofptype type)
 184 {
 185     if (oh->xid != xid) {
 186         ofctrl_recv(oh, type);
 187     } else if (type == OFPTYPE_NXT_TLV_TABLE_REPLY) {
 188         struct ofputil_tlv_table_reply reply;
 189         enum ofperr error = ofputil_decode_tlv_table_reply(oh, &reply);
 190         if (error) {
 191             VLOG_ERR("failed to decode TLV table request (%s)",
 192                      ofperr_to_string(error));
 193             goto error;
 194         }
 195
 196         const struct ofputil_tlv_map *map;
 197         uint64_t md_free = UINT64_MAX;
 198         BUILD_ASSERT(TUN_METADATA_NUM_OPTS == 64);
 199
 200         LIST_FOR_EACH (map, list_node, &reply.mappings) {
 201             if (map->option_class == OVN_GENEVE_CLASS
 202                 && map->option_type == OVN_GENEVE_TYPE
 203                 && map->option_len == OVN_GENEVE_LEN) {
 204                 if (map->index >= TUN_METADATA_NUM_OPTS) {
 205                     VLOG_ERR("desired Geneve tunnel option 0x%"PRIx16","
 206                              "%"PRIu8",%"PRIu8" already in use with "
 207                              "unsupported index %"PRIu16,
 208                              map->option_class, map->option_type,
 209                              map->option_len, map->index);
 210                     goto error;
 211                 } else {
 212                     mff_ovn_geneve = MFF_TUN_METADATA0 + map->index;
 213                     state = S_CLEAR_FLOWS;
 214                     return;
 215                 }
 216             }
 217
 218             if (map->index < TUN_METADATA_NUM_OPTS) {
 219                 md_free &= ~(UINT64_C(1) << map->index);
 220             }
 221         }
 222
 223         VLOG_DBG("OVN Geneve option not found");
 224         if (!md_free) {
 225             VLOG_ERR("no Geneve options free for use by OVN");
 226             goto error;
 227         }
 228
 229         unsigned int index = rightmost_1bit_idx(md_free);
 230         mff_ovn_geneve = MFF_TUN_METADATA0 + index;
 231         struct ofputil_tlv_map tm;
 232         tm.option_class = OVN_GENEVE_CLASS;
 233         tm.option_type = OVN_GENEVE_TYPE;
 234         tm.option_len = OVN_GENEVE_LEN;
 235         tm.index = index;
 236
 237         struct ofputil_tlv_table_mod ttm;
 238         ttm.command = NXTTMC_ADD;
 239         ovs_list_init(&ttm.mappings);
 240         ovs_list_push_back(&ttm.mappings, &tm.list_node);
 241
 242         xid = queue_msg(ofputil_encode_tlv_table_mod(OFP13_VERSION, &ttm));
 243         xid2 = queue_msg(ofputil_encode_barrier_request(OFP13_VERSION));
 244         state = S_TLV_TABLE_MOD_SENT;
 245     } else if (type == OFPTYPE_ERROR) {
 246         VLOG_ERR("switch refused to allocate Geneve option (%s)",
 247                  ofperr_to_string(ofperr_decode_msg(oh, NULL)));
 248         goto error;
 249     } else {
 250         char *s = ofp_to_string(oh, ntohs(oh->length), 1);
 251         VLOG_ERR("unexpected reply to TLV table request (%s)",
 252                  s);
 253         free(s);
 254         goto error;
 255     }
 256     return;
 257
 258 error:
 259     mff_ovn_geneve = 0;
 260     state = S_CLEAR_FLOWS;
 261 }
 262 \f
 263 /* S_TLV_TABLE_MOD_SENT, when NXT_TLV_TABLE_MOD and OFPT_BARRIER_REQUEST
 264  * have been sent and we're waiting for a reply to one or the other.
 265  *
 266  * If we receive an OFPT_ERROR:
 267  *
 268  *     - If the error is NXTTMFC_ALREADY_MAPPED or NXTTMFC_DUP_ENTRY, we
 269  *       raced with some other controller.  Transition to S_NEW.
 270  *
 271  *     - Otherwise, log an error, disable Geneve, and transition to
 272  *       S_CLEAR_FLOWS.
 273  *
 274  * If we receive OFPT_BARRIER_REPLY:
 275  *
 276  *     - Set the tunnel metadata field ID to the one that we requested.
 277  *       Transition to S_CLEAR_FLOWS.
 278  */
 279
 280 static void
 281 run_S_TLV_TABLE_MOD_SENT(void)
 282 {
 283 }
 284
 285 static void
 286 recv_S_TLV_TABLE_MOD_SENT(const struct ofp_header *oh, enum ofptype type)
 287 {
 288     if (oh->xid != xid && oh->xid != xid2) {
 289         ofctrl_recv(oh, type);
 290     } else if (oh->xid == xid2 && type == OFPTYPE_BARRIER_REPLY) {
 291         state = S_CLEAR_FLOWS;
 292     } else if (oh->xid == xid && type == OFPTYPE_ERROR) {
 293         enum ofperr error = ofperr_decode_msg(oh, NULL);
 294         if (error == OFPERR_NXTTMFC_ALREADY_MAPPED ||
 295             error == OFPERR_NXTTMFC_DUP_ENTRY) {
 296             VLOG_INFO("raced with another controller adding "
 297                       "Geneve option (%s); trying again",
 298                       ofperr_to_string(error));
 299             state = S_NEW;
 300         } else {
 301             VLOG_ERR("error adding Geneve option (%s)",
 302                      ofperr_to_string(error));
 303             goto error;
 304         }
 305     } else {
 306         char *s = ofp_to_string(oh, ntohs(oh->length), 1);
 307         VLOG_ERR("unexpected reply to Geneve option allocation request (%s)",
 308                  s);
 309         free(s);
 310         goto error;
 311     }
 312     return;
 313
 314 error:
 315     state = S_CLEAR_FLOWS;
 316 }
 317 \f
 318 /* S_CLEAR_FLOWS, after we've established a Geneve metadata field ID and it's
 319  * time to set up some flows.
 320  *
 321  * Sends an OFPT_TABLE_MOD to clear all flows, then transitions to
 322  * S_UPDATE_FLOWS. */
 323
 324 static void
 325 run_S_CLEAR_FLOWS(void)
 326 {
 327     /* Send a flow_mod to delete all flows. */
 328     struct ofputil_flow_mod fm = {
 329         .match = MATCH_CATCHALL_INITIALIZER,
 330         .table_id = OFPTT_ALL,
 331         .command = OFPFC_DELETE,
 332     };
 333     queue_flow_mod(&fm);
 334     VLOG_DBG("clearing all flows");
 335
 336     struct ofputil_group_mod gm;
 337     memset(&gm, 0, sizeof gm);
 338     gm.command = OFPGC11_DELETE;
 339     gm.group_id = OFPG_ALL;
 340     gm.command_bucket_id = OFPG15_BUCKET_ALL;
 341     ovs_list_init(&gm.buckets);
 342     queue_group_mod(&gm);
 343     ofputil_bucket_list_destroy(&gm.buckets);
 344
 345     /* Clear installed_flows, to match the state of the switch. */
 346     ovn_flow_table_clear();
 347
 348     /* Clear existing groups, to match the state of the switch. */
 349     if (groups) {
 350         ovn_group_table_clear(groups, true);
 351     }
 352
 353     state = S_UPDATE_FLOWS;
 354 }
 355
 356 static void
 357 recv_S_CLEAR_FLOWS(const struct ofp_header *oh, enum ofptype type)
 358 {
 359     ofctrl_recv(oh, type);
 360 }
 361 \f
 362 /* S_UPDATE_FLOWS, for maintaining the flow table over time.
 363  *
 364  * Compare the installed flows to the ones we want.  Send OFPT_FLOW_MOD as
 365  * necessary.
 366  *
 367  * This is a terminal state.  We only transition out of it if the connection
 368  * drops. */
 369
 370 static void
 371 run_S_UPDATE_FLOWS(void)
 372 {
 373     /* Nothing to do here.
 374      *
 375      * Being in this state enables ofctrl_put() to work, however. */
 376 }
 377
 378 static void
 379 recv_S_UPDATE_FLOWS(const struct ofp_header *oh, enum ofptype type)
 380 {
 381     ofctrl_recv(oh, type);
 382 }
 383 \f
 384 /* Runs the OpenFlow state machine against 'br_int', which is local to the
 385  * hypervisor on which we are running.  Attempts to negotiate a Geneve option
 386  * field for class OVN_GENEVE_CLASS, type OVN_GENEVE_TYPE.  If successful,
 387  * returns the MFF_* field ID for the option, otherwise returns 0. */
 388 enum mf_field_id
 389 ofctrl_run(const struct ovsrec_bridge *br_int)
 390 {
 391     if (br_int) {
 392         char *target;
 393         target = xasprintf("unix:%s/%s.mgmt", ovs_rundir(), br_int->name);
 394         if (strcmp(target, rconn_get_target(swconn))) {
 395             VLOG_INFO("%s: connecting to switch", target);
 396             rconn_connect(swconn, target, target);
 397         }
 398         free(target);
 399     } else {
 400         rconn_disconnect(swconn);
 401     }
 402
 403     rconn_run(swconn);
 404
 405     if (!rconn_is_connected(swconn)) {
 406         return 0;
 407     }
 408     if (seqno != rconn_get_connection_seqno(swconn)) {
 409         seqno = rconn_get_connection_seqno(swconn);
 410         state = S_NEW;
 411     }
 412
 413     bool progress = true;
 414     for (int i = 0; progress && i < 50; i++) {
 415         /* Allow the state machine to run. */
 416         enum ofctrl_state old_state = state;
 417         switch (state) {
 418 #define STATE(NAME) case NAME: run_##NAME(); break;
 419             STATES
 420 #undef STATE
 421         default:
 422             OVS_NOT_REACHED();
 423         }
 424
 425         /* Try to process a received packet. */
 426         struct ofpbuf *msg = rconn_recv(swconn);
 427         if (msg) {
 428             const struct ofp_header *oh = msg->data;
 429             enum ofptype type;
 430             enum ofperr error;
 431
 432             error = ofptype_decode(&type, oh);
 433             if (!error) {
 434                 switch (state) {
 435 #define STATE(NAME) case NAME: recv_##NAME(oh, type); break;
 436                     STATES
 437 #undef STATE
 438                 default:
 439                     OVS_NOT_REACHED();
 440                 }
 441             } else {
 442                 char *s = ofp_to_string(oh, ntohs(oh->length), 1);
 443                 VLOG_WARN("could not decode OpenFlow message (%s): %s",
 444                           ofperr_to_string(error), s);
 445                 free(s);
 446             }
 447
 448             ofpbuf_delete(msg);
 449         }
 450
 451         /* If we did some work, plan to go around again. */
 452         progress = old_state != state || msg;
 453     }
 454     if (progress) {
 455         /* We bailed out to limit the amount of work we do in one go, to allow
 456          * other code a chance to run.  We were still making progress at that
 457          * point, so ensure that we come back again without waiting. */
 458         poll_immediate_wake();
 459     }
 460
 461     return (state == S_CLEAR_FLOWS || state == S_UPDATE_FLOWS
 462             ? mff_ovn_geneve : 0);
 463 }
 464
 465 void
 466 ofctrl_wait(void)
 467 {
 468     rconn_run_wait(swconn);
 469     rconn_recv_wait(swconn);
 470 }
 471
 472 void
 473 ofctrl_destroy(void)
 474 {
 475     rconn_destroy(swconn);
 476     ovn_flow_table_destroy();
 477     rconn_packet_counter_destroy(tx_counter);
 478 }
 479 \f
 480 static ovs_be32
 481 queue_msg(struct ofpbuf *msg)
 482 {
 483     const struct ofp_header *oh = msg->data;
 484     ovs_be32 xid = oh->xid;
 485     rconn_send(swconn, msg, tx_counter);
 486     return xid;
 487 }
 488
 489 static void
 490 log_openflow_rl(struct vlog_rate_limit *rl, enum vlog_level level,
 491                 const struct ofp_header *oh, const char *title)
 492 {
 493     if (!vlog_should_drop(&this_module, level, rl)) {
 494         char *s = ofp_to_string(oh, ntohs(oh->length), 2);
 495         vlog(&this_module, level, "%s: %s", title, s);
 496         free(s);
 497     }
 498 }
 499
 500 static void
 501 ofctrl_recv(const struct ofp_header *oh, enum ofptype type)
 502 {
 503     if (type == OFPTYPE_ECHO_REQUEST) {
 504         queue_msg(make_echo_reply(oh));
 505     } else if (type == OFPTYPE_ERROR) {
 506         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300);
 507         log_openflow_rl(&rl, VLL_INFO, oh, "OpenFlow error");
 508     } else if (type != OFPTYPE_ECHO_REPLY &&
 509                type != OFPTYPE_BARRIER_REPLY &&
 510                type != OFPTYPE_PACKET_IN &&
 511                type != OFPTYPE_PORT_STATUS &&
 512                type != OFPTYPE_FLOW_REMOVED) {
 513         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300);
 514         log_openflow_rl(&rl, VLL_DBG, oh, "OpenFlow packet ignored");
 515     }
 516 }
 517 \f
 518 /* Flow table interfaces to the rest of ovn-controller. */
 519
 520 static void
 521 log_ovn_flow_rl(struct vlog_rate_limit *rl, enum vlog_level level,
 522                 const struct ovn_flow *flow, const char *title)
 523 {
 524     if (!vlog_should_drop(&this_module, level, rl)) {
 525         char *s = ovn_flow_to_string(flow);
 526         vlog(&this_module, level, "%s for parent "UUID_FMT": %s",
 527              title, UUID_ARGS(&flow->uuid), s);
 528         free(s);
 529     }
 530 }
 531
 532 /* Adds a flow to the collection associated with 'uuid'.  The flow has the
 533  * specified 'match' and 'actions' to the OpenFlow table numbered 'table_id'
 534  * with the given 'priority'.  The caller retains ownership of 'match' and
 535  * 'actions'.
 536  *
 537  * Any number of flows may be associated with a given UUID.  The flows with a
 538  * given UUID must have a unique (table_id, priority, match) tuple.  A
 539  * duplicate within a generally indicates a bug in the ovn-controller code that
 540  * generated it, so this functions logs a warning.
 541  *
 542  * (table_id, priority, match) tuples should also be unique for flows with
 543  * different UUIDs, but it doesn't necessarily indicate a bug in
 544  * ovn-controller, for two reasons.  First, these duplicates could be caused by
 545  * logical flows generated by ovn-northd, which aren't ovn-controller's fault;
 546  * perhaps something should warn about these but the root cause is different.
 547  * Second, these duplicates might be transient, that is, they might go away
 548  * before the next call to ofctrl_run() if a call to ofctrl_remove_flows()
 549  * removes one or the other.
 550  *
 551  * This just assembles the desired flow tables in memory.  Nothing is actually
 552  * sent to the switch until a later call to ofctrl_run(). */
 553 void
 554 ofctrl_add_flow(uint8_t table_id, uint16_t priority,
 555                 const struct match *match, const struct ofpbuf *actions,
 556                 const struct uuid *uuid)
 557 {
 558     /* Structure that uses table_id+priority+various things as hashes. */
 559     struct ovn_flow *f = xmalloc(sizeof *f);
 560     f->table_id = table_id;
 561     f->priority = priority;
 562     f->match = *match;
 563     f->ofpacts = xmemdup(actions->data, actions->size);
 564     f->ofpacts_len = actions->size;
 565     f->uuid = *uuid;
 566     f->match_hmap_node.hash = ovn_flow_match_hash(f);
 567     f->uuid_hindex_node.hash = uuid_hash(&f->uuid);
 568
 569     /* Check to see if other flows exist with the same key (table_id priority,
 570      * match criteria) and uuid.  If so, discard this flow and log a
 571      * warning. */
 572     struct ovs_list existing;
 573     ovn_flow_lookup(&match_flow_table, f, &existing);
 574     struct ovn_flow *d;
 575     LIST_FOR_EACH (d, list_node, &existing) {
 576         if (uuid_equals(&f->uuid, &d->uuid)) {
 577             /* Duplicate flows with the same UUID indicate some kind of bug
 578              * (see the function-level comment), but we distinguish two
 579              * cases:
 580              *
 581              *     - If the actions for the duplicate flow are the same, then
 582              *       it's benign; it's hard to imagine how there could be a
 583              *       real problem.  Log at INFO level.
 584              *
 585              *     - If the actions are different, then one or the other set of
 586              *       actions must be wrong or (perhaps more likely) we've got a
 587              *       new set of actions replacing an old set but the caller
 588              *       neglected to use ofctrl_remove_flows() or
 589              *       ofctrl_set_flow() to do it properly.  Log at WARN level to
 590              *       get some attention.
 591              */
 592             if (ofpacts_equal(f->ofpacts, f->ofpacts_len,
 593                               d->ofpacts, d->ofpacts_len)) {
 594                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
 595                 log_ovn_flow_rl(&rl, VLL_INFO, f, "duplicate flow");
 596             } else {
 597                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
 598                 log_ovn_flow_rl(&rl, VLL_WARN, f,
 599                                 "duplicate flow with modified action");
 600
 601                 /* It seems likely that the newer actions are the correct
 602                  * ones. */
 603                 free(d->ofpacts);
 604                 d->ofpacts = f->ofpacts;
 605                 d->ofpacts_len = f->ofpacts_len;
 606                 f->ofpacts = NULL;
 607             }
 608             ovn_flow_destroy(f);
 609             return;
 610         }
 611     }
 612
 613     /* Otherwise, add the flow. */
 614     hmap_insert(&match_flow_table, &f->match_hmap_node,
 615                 f->match_hmap_node.hash);
 616     hindex_insert(&uuid_flow_table, &f->uuid_hindex_node,
 617                 f->uuid_hindex_node.hash);
 618 }
 619
 620 /* Removes a bundles of flows from the flow table. */
 621 void
 622 ofctrl_remove_flows(const struct uuid *uuid)
 623 {
 624     struct ovn_flow *f, *next;
 625     HINDEX_FOR_EACH_WITH_HASH_SAFE (f, next, uuid_hindex_node, uuid_hash(uuid),
 626                                     &uuid_flow_table) {
 627         if (uuid_equals(&f->uuid, uuid)) {
 628             hmap_remove(&match_flow_table, &f->match_hmap_node);
 629             hindex_remove(&uuid_flow_table, &f->uuid_hindex_node);
 630             ovn_flow_destroy(f);
 631         }
 632     }
 633 }
 634
 635 /* Shortcut to remove all flows matching the supplied UUID and add this
 636  * flow. */
 637 void
 638 ofctrl_set_flow(uint8_t table_id, uint16_t priority,
 639                 const struct match *match, const struct ofpbuf *actions,
 640                 const struct uuid *uuid)
 641 {
 642     ofctrl_remove_flows(uuid);
 643     ofctrl_add_flow(table_id, priority, match, actions, uuid);
 644 }
 645 \f
 646 /* ovn_flow. */
 647
 648 /* Duplicate an ovn_flow structure. */
 649 struct ovn_flow *
 650 ofctrl_dup_flow(struct ovn_flow *src)
 651 {
 652     struct ovn_flow *dst = xmalloc(sizeof *dst);
 653     dst->table_id = src->table_id;
 654     dst->priority = src->priority;
 655     dst->match = src->match;
 656     dst->ofpacts = xmemdup(src->ofpacts, src->ofpacts_len);
 657     dst->ofpacts_len = src->ofpacts_len;
 658     dst->uuid = src->uuid;
 659     dst->match_hmap_node.hash = ovn_flow_match_hash(dst);
 660     dst->uuid_hindex_node.hash = uuid_hash(&src->uuid);
 661     return dst;
 662 }
 663
 664 /* Returns a hash of the match key in 'f'. */
 665 static uint32_t
 666 ovn_flow_match_hash(const struct ovn_flow *f)
 667 {
 668     return hash_2words((f->table_id << 16) | f->priority,
 669                        match_hash(&f->match, 0));
 670 }
 671
 672 /* Compare two flows and return -1, 0, 1 based on whether a if less than,
 673  * equal to or greater than b. */
 674 static int
 675 ovn_flow_compare_flows(struct ovn_flow *a, struct ovn_flow *b)
 676 {
 677     return uuid_compare_3way(&a->uuid, &b->uuid);
 678 }
 679
 680 /* Given a list of ovn_flows, goes through the list and returns
 681  * a single flow, in a deterministic way. */
 682 static struct ovn_flow *
 683 ovn_flow_select_from_list(struct ovs_list *flows)
 684 {
 685     struct ovn_flow *candidate;
 686     struct ovn_flow *answer = NULL;
 687     LIST_FOR_EACH (candidate, list_node, flows) {
 688         if (!answer || ovn_flow_compare_flows(candidate, answer) < 0) {
 689             answer = candidate;
 690         }
 691     }
 692     return answer;
 693 }
 694
 695 /* Initializes and files in the supplied list with ovn_flows from 'flow_table'
 696  * whose key is identical to 'target''s key. */
 697 static void
 698 ovn_flow_lookup(struct hmap *flow_table, const struct ovn_flow *target,
 699                 struct ovs_list *answer)
 700 {
 701     struct ovn_flow *f;
 702
 703     ovs_list_init(answer);
 704     HMAP_FOR_EACH_WITH_HASH (f, match_hmap_node, target->match_hmap_node.hash,
 705                              flow_table) {
 706         if (f->table_id == target->table_id
 707             && f->priority == target->priority
 708             && match_equal(&f->match, &target->match)) {
 709             ovs_list_push_back(answer, &f->list_node);
 710         }
 711     }
 712 }
 713
 714 static char *
 715 ovn_flow_to_string(const struct ovn_flow *f)
 716 {
 717     struct ds s = DS_EMPTY_INITIALIZER;
 718     ds_put_format(&s, "table_id=%"PRIu8", ", f->table_id);
 719     ds_put_format(&s, "priority=%"PRIu16", ", f->priority);
 720     match_format(&f->match, &s, OFP_DEFAULT_PRIORITY);
 721     ds_put_cstr(&s, ", actions=");
 722     ofpacts_format(f->ofpacts, f->ofpacts_len, &s);
 723     return ds_steal_cstr(&s);
 724 }
 725
 726 static void
 727 ovn_flow_log(const struct ovn_flow *f, const char *action)
 728 {
 729     if (VLOG_IS_DBG_ENABLED()) {
 730         char *s = ovn_flow_to_string(f);
 731         VLOG_DBG("%s flow: %s", action, s);
 732         free(s);
 733     }
 734 }
 735
 736 static void
 737 ovn_flow_destroy(struct ovn_flow *f)
 738 {
 739     if (f) {
 740         free(f->ofpacts);
 741         free(f);
 742     }
 743 }
 744 \f
 745 /* Flow tables of struct ovn_flow. */
 746
 747 void
 748 ovn_flow_table_clear(void)
 749 {
 750     struct ovn_flow *f, *next;
 751     HMAP_FOR_EACH_SAFE (f, next, match_hmap_node, &match_flow_table) {
 752         hmap_remove(&match_flow_table, &f->match_hmap_node);
 753         hindex_remove(&uuid_flow_table, &f->uuid_hindex_node);
 754         ovn_flow_destroy(f);
 755     }
 756 }
 757
 758 static void
 759 ovn_flow_table_destroy(void)
 760 {
 761     ovn_flow_table_clear();
 762     hmap_destroy(&match_flow_table);
 763     hindex_destroy(&uuid_flow_table);
 764 }
 765 \f
 766 /* Flow table update. */
 767
 768 static void
 769 queue_flow_mod(struct ofputil_flow_mod *fm)
 770 {
 771     fm->buffer_id = UINT32_MAX;
 772     fm->out_port = OFPP_ANY;
 773     fm->out_group = OFPG_ANY;
 774     queue_msg(ofputil_encode_flow_mod(fm, OFPUTIL_P_OF13_OXM));
 775 }
 776
 777 \f
 778 /* group_table. */
 779
 780 /* Finds and returns a group_info in 'existing_groups' whose key is identical
 781  * to 'target''s key, or NULL if there is none. */
 782 static struct group_info *
 783 ovn_group_lookup(struct hmap *exisiting_groups,
 784                  const struct group_info *target)
 785 {
 786     struct group_info *e;
 787
 788     HMAP_FOR_EACH_WITH_HASH(e, hmap_node, target->hmap_node.hash,
 789                             exisiting_groups) {
 790         if (e->group_id == target->group_id) {
 791             return e;
 792         }
 793    }
 794     return NULL;
 795 }
 796
 797 /* Clear either desired_groups or existing_groups in group_table. */
 798 static void
 799 ovn_group_table_clear(struct group_table *group_table, bool existing)
 800 {
 801     struct group_info *g, *next;
 802     struct hmap *target_group = existing
 803                                 ? &group_table->existing_groups
 804                                 : &group_table->desired_groups;
 805
 806     HMAP_FOR_EACH_SAFE (g, next, hmap_node, target_group) {
 807         hmap_remove(target_group, &g->hmap_node);
 808         bitmap_set0(group_table->group_ids, g->group_id);
 809         ds_destroy(&g->group);
 810         free(g);
 811     }
 812 }
 813
 814 static void
 815 queue_group_mod(struct ofputil_group_mod *gm)
 816 {
 817     queue_msg(ofputil_encode_group_mod(OFP13_VERSION, gm));
 818 }
 819 \f
 820
 821 /* Replaces the flow table on the switch, if possible, by the flows in added
 822  * with ofctrl_add_flow().
 823  *
 824  * Replaces the group table on the switch, if possible, by the groups in
 825  * 'group_table->desired_groups'. Regardless of whether the group table
 826  * is updated, this deletes all the groups from the
 827  * 'group_table->desired_groups' and frees them. (The hmap itself isn't
 828  * destroyed.)
 829  *
 830  * This should be called after ofctrl_run() within the main loop. */
 831 void
 832 ofctrl_put(struct group_table *group_table)
 833 {
 834     if (!groups) {
 835         groups = group_table;
 836     }
 837
 838     /* The flow table can be updated if the connection to the switch is up and
 839      * in the correct state and not backlogged with existing flow_mods.  (Our
 840      * criteria for being backlogged appear very conservative, but the socket
 841      * between ovn-controller and OVS provides some buffering.) */
 842     if (state != S_UPDATE_FLOWS
 843         || rconn_packet_counter_n_packets(tx_counter)) {
 844         ovn_group_table_clear(group_table, false);
 845         return;
 846     }
 847
 848     /* Iterate through all the desired groups. If there are new ones,
 849      * add them to the switch. */
 850     struct group_info *desired;
 851     HMAP_FOR_EACH(desired, hmap_node, &group_table->desired_groups) {
 852         if (!ovn_group_lookup(&group_table->existing_groups, desired)) {
 853             /* Create and install new group. */
 854             struct ofputil_group_mod gm;
 855             enum ofputil_protocol usable_protocols;
 856             char *error;
 857             struct ds group_string = DS_EMPTY_INITIALIZER;
 858             ds_put_format(&group_string, "group_id=%u,%s",
 859                           desired->group_id, ds_cstr(&desired->group));
 860
 861             error = parse_ofp_group_mod_str(&gm, OFPGC11_ADD,
 862                                             ds_cstr(&group_string),
 863                                             &usable_protocols);
 864             if (!error) {
 865                 queue_group_mod(&gm);
 866             } else {
 867                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
 868                 VLOG_ERR_RL(&rl, "new group %s %s", error,
 869                          ds_cstr(&group_string));
 870                 free(error);
 871             }
 872             ds_destroy(&group_string);
 873             ofputil_bucket_list_destroy(&gm.buckets);
 874         }
 875     }
 876
 877     /* Iterate through all of the installed flows.  If any of them are no
 878      * longer desired, delete them; if any of them should have different
 879      * actions, update them. */
 880     struct ovn_flow *i, *next;
 881     HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
 882         struct ovs_list matches;
 883         ovn_flow_lookup(&match_flow_table, i, &matches);
 884         if (ovs_list_is_empty(&matches)) {
 885             /* Installed flow is no longer desirable.  Delete it from the
 886              * switch and from installed_flows. */
 887             struct ofputil_flow_mod fm = {
 888                 .match = i->match,
 889                 .priority = i->priority,
 890                 .table_id = i->table_id,
 891                 .command = OFPFC_DELETE_STRICT,
 892             };
 893             queue_flow_mod(&fm);
 894             ovn_flow_log(i, "removing installed");
 895
 896             hmap_remove(&installed_flows, &i->match_hmap_node);
 897             ovn_flow_destroy(i);
 898         } else {
 899             /* Since we still have desired flows that match this key,
 900              * select one and compare both its actions and uuid.
 901              * If the actions aren't the same, queue and update
 902              * action for the install flow.  If the uuid has changed
 903              * update that as well. */
 904             struct ovn_flow *d = ovn_flow_select_from_list(&matches);
 905             if (!uuid_equals(&i->uuid, &d->uuid)) {
 906                 /* Update installed flow's UUID. */
 907                 i->uuid = d->uuid;
 908             }
 909             if (!ofpacts_equal(i->ofpacts, i->ofpacts_len,
 910                                d->ofpacts, d->ofpacts_len)) {
 911                 /* Update actions in installed flow. */
 912                 struct ofputil_flow_mod fm = {
 913                     .match = i->match,
 914                     .priority = i->priority,
 915                     .table_id = i->table_id,
 916                     .ofpacts = d->ofpacts,
 917                     .ofpacts_len = d->ofpacts_len,
 918                     .command = OFPFC_MODIFY_STRICT,
 919                 };
 920                 queue_flow_mod(&fm);
 921                 ovn_flow_log(i, "updating installed");
 922
 923                 /* Replace 'i''s actions by 'd''s. */
 924                 free(i->ofpacts);
 925                 i->ofpacts = xmemdup(d->ofpacts, d->ofpacts_len);
 926                 i->ofpacts_len = d->ofpacts_len;
 927             }
 928         }
 929     }
 930
 931     /* Iterate through the desired flows and add those that aren't found
 932      * in the installed flow table. */
 933     struct ovn_flow *c;
 934     HMAP_FOR_EACH (c, match_hmap_node, &match_flow_table) {
 935         struct ovs_list matches;
 936         ovn_flow_lookup(&installed_flows, c, &matches);
 937         if (ovs_list_is_empty(&matches)) {
 938             /* We have a key that isn't in the installed flows, so
 939              * look back into the desired flow list for all flows
 940              * that match this key, and select the one to be installed. */
 941             struct ovs_list candidates;
 942             ovn_flow_lookup(&match_flow_table, c, &candidates);
 943             struct ovn_flow *d = ovn_flow_select_from_list(&candidates);
 944             /* Send flow_mod to add flow. */
 945             struct ofputil_flow_mod fm = {
 946                 .match = d->match,
 947                 .priority = d->priority,
 948                 .table_id = d->table_id,
 949                 .ofpacts = d->ofpacts,
 950                 .ofpacts_len = d->ofpacts_len,
 951                 .command = OFPFC_ADD,
 952             };
 953             queue_flow_mod(&fm);
 954             ovn_flow_log(d, "adding installed");
 955
 956             /* Copy 'd' from 'flow_table' to installed_flows. */
 957             struct ovn_flow *new_node = ofctrl_dup_flow(d);
 958             hmap_insert(&installed_flows, &new_node->match_hmap_node,
 959                         new_node->match_hmap_node.hash);
 960         }
 961     }
 962
 963     /* Iterate through the installed groups from previous runs. If they
 964      * are not needed delete them. */
 965     struct group_info *installed, *next_group;
 966     HMAP_FOR_EACH_SAFE(installed, next_group, hmap_node,
 967                        &group_table->existing_groups) {
 968         if (!ovn_group_lookup(&group_table->desired_groups, installed)) {
 969             /* Delete the group. */
 970             struct ofputil_group_mod gm;
 971             enum ofputil_protocol usable_protocols;
 972             char *error;
 973             struct ds group_string = DS_EMPTY_INITIALIZER;
 974             ds_put_format(&group_string, "group_id=%u", installed->group_id);
 975
 976             error = parse_ofp_group_mod_str(&gm, OFPGC11_DELETE,
 977                                             ds_cstr(&group_string),
 978                                             &usable_protocols);
 979             if (!error) {
 980                 queue_group_mod(&gm);
 981             } else {
 982                 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
 983                 VLOG_ERR_RL(&rl, "Error deleting group %d: %s",
 984                          installed->group_id, error);
 985                 free(error);
 986             }
 987             ds_destroy(&group_string);
 988             ofputil_bucket_list_destroy(&gm.buckets);
 989
 990             /* Remove 'installed' from 'group_table->existing_groups' */
 991             hmap_remove(&group_table->existing_groups, &installed->hmap_node);
 992             ds_destroy(&installed->group);
 993
 994             /* Dealloc group_id. */
 995             bitmap_set0(group_table->group_ids, installed->group_id);
 996             free(installed);
 997         }
 998     }
 999
1000     /* Move the contents of desired_groups to existing_groups. */
1001     HMAP_FOR_EACH_SAFE(desired, next_group, hmap_node,
1002                        &group_table->desired_groups) {
1003         hmap_remove(&group_table->desired_groups, &desired->hmap_node);
1004         if (!ovn_group_lookup(&group_table->existing_groups, desired)) {
1005             hmap_insert(&group_table->existing_groups, &desired->hmap_node,
1006                         desired->hmap_node.hash);
1007         } else {
1008             ds_destroy(&desired->group);
1009             free(desired);
1010         }
1011     }
1012 }