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