#include "bitmap.h"
#include "byte-order.h"
#include "dirs.h"
+#include "flow.h"
#include "hash.h"
+#include "hindex.h"
#include "hmap.h"
#include "ofctrl.h"
#include "openflow/openflow.h"
#include "openvswitch/dynamic-string.h"
+#include "openvswitch/list.h"
#include "openvswitch/match.h"
#include "openvswitch/ofp-actions.h"
#include "openvswitch/ofp-msgs.h"
/* An OpenFlow flow. */
struct ovn_flow {
+ struct hmap_node match_hmap_node; /* For match based hashing. */
+ struct hindex_node uuid_hindex_node; /* For uuid based hashing. */
+ struct ovs_list list_node; /* For handling lists of flows. */
+
/* Key. */
- struct hmap_node hmap_node;
uint8_t table_id;
uint16_t priority;
struct match match;
- /* Data. */
+ /* Data. UUID is used for disambiguation. */
+ struct uuid uuid;
struct ofpact *ofpacts;
size_t ofpacts_len;
};
-static uint32_t ovn_flow_hash(const struct ovn_flow *);
-static struct ovn_flow *ovn_flow_lookup(struct hmap *flow_table,
- const struct ovn_flow *target);
+static uint32_t ovn_flow_match_hash(const struct ovn_flow *);
+static void ovn_flow_lookup(struct hmap *, const struct ovn_flow *target,
+ struct ovs_list *answers);
static char *ovn_flow_to_string(const struct ovn_flow *);
static void ovn_flow_log(const struct ovn_flow *, const char *action);
static void ovn_flow_destroy(struct ovn_flow *);
* S_CLEAR_FLOWS or S_UPDATE_FLOWS, this is really the option we have. */
static enum mf_field_id mff_ovn_geneve;
-static void ovn_flow_table_clear(struct hmap *flow_table);
-static void ovn_flow_table_destroy(struct hmap *flow_table);
+static void ovn_flow_table_destroy(void);
static void ovn_group_table_clear(struct group_table *group_table,
bool existing);
static void ofctrl_recv(const struct ofp_header *, enum ofptype);
+static struct hmap match_flow_table = HMAP_INITIALIZER(&match_flow_table);
+static struct hindex uuid_flow_table = HINDEX_INITIALIZER(&uuid_flow_table);
+
void
ofctrl_init(void)
{
ofputil_bucket_list_destroy(&gm.buckets);
/* Clear installed_flows, to match the state of the switch. */
- ovn_flow_table_clear(&installed_flows);
+ ovn_flow_table_clear();
/* Clear existing groups, to match the state of the switch. */
if (groups) {
ofctrl_destroy(void)
{
rconn_destroy(swconn);
- ovn_flow_table_destroy(&installed_flows);
+ ovn_flow_table_destroy();
rconn_packet_counter_destroy(tx_counter);
}
\f
}
}
\f
-/* Flow table interface to the rest of ovn-controller. */
+/* Flow table interfaces to the rest of ovn-controller. */
-/* Adds a flow to 'desired_flows' with the specified 'match' and 'actions' to
- * the OpenFlow table numbered 'table_id' with the given 'priority'. The
- * caller retains ownership of 'match' and 'actions'.
+/* Adds a flow to the collection associated with 'uuid'. The flow has the
+ * specified 'match' and 'actions' to the OpenFlow table numbered 'table_id'
+ * with the given 'priority'. The caller retains ownership of 'match' and
+ * 'actions'.
+ *
+ * Any number of flows may be associated with a given UUID. The flows with a
+ * given UUID must have a unique (table_id, priority, match) tuple. A
+ * duplicate within a generally indicates a bug in the ovn-controller code that
+ * generated it, so this functions logs a warning.
*
- * This just assembles the desired flow table in memory. Nothing is actually
- * sent to the switch until a later call to ofctrl_run().
+ * (table_id, priority, match) tuples should also be unique for flows with
+ * different UUIDs, but it doesn't necessarily indicate a bug in
+ * ovn-controller, for two reasons. First, these duplicates could be caused by
+ * logical flows generated by ovn-northd, which aren't ovn-controller's fault;
+ * perhaps something should warn about these but the root cause is different.
+ * Second, these duplicates might be transient, that is, they might go away
+ * before the next call to ofctrl_run() if a call to ofctrl_remove_flows()
+ * removes one or the other.
*
- * The caller should initialize its own hmap to hold the flows. */
+ * This just assembles the desired flow tables in memory. Nothing is actually
+ * sent to the switch until a later call to ofctrl_run(). */
void
-ofctrl_add_flow(struct hmap *desired_flows,
- uint8_t table_id, uint16_t priority,
- const struct match *match, const struct ofpbuf *actions)
+ofctrl_add_flow(uint8_t table_id, uint16_t priority,
+ const struct match *match, const struct ofpbuf *actions,
+ const struct uuid *uuid)
{
+ /* Structure that uses table_id+priority+various things as hashes. */
struct ovn_flow *f = xmalloc(sizeof *f);
f->table_id = table_id;
f->priority = priority;
f->match = *match;
f->ofpacts = xmemdup(actions->data, actions->size);
f->ofpacts_len = actions->size;
- f->hmap_node.hash = ovn_flow_hash(f);
-
- if (ovn_flow_lookup(desired_flows, f)) {
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 5);
- if (!VLOG_DROP_INFO(&rl)) {
+ f->uuid = *uuid;
+ f->match_hmap_node.hash = ovn_flow_match_hash(f);
+ f->uuid_hindex_node.hash = uuid_hash(&f->uuid);
+
+ /* Check to see if other flows exist with the same key (table_id priority,
+ * match criteria) and uuid. If so, discard this flow and log a
+ * warning. */
+ struct ovs_list existing;
+ ovn_flow_lookup(&match_flow_table, f, &existing);
+ struct ovn_flow *d;
+ LIST_FOR_EACH (d, list_node, &existing) {
+ if (uuid_equals(&f->uuid, &d->uuid)) {
+ static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
char *s = ovn_flow_to_string(f);
- VLOG_INFO("dropping duplicate flow: %s", s);
+ VLOG_WARN_RL(&rl, "found duplicate flow %s for parent "UUID_FMT,
+ s, UUID_ARGS(&f->uuid));
+ ovn_flow_destroy(f);
free(s);
+ return;
}
+ }
- ovn_flow_destroy(f);
- return;
+ /* Otherwise, add the flow. */
+ hmap_insert(&match_flow_table, &f->match_hmap_node,
+ f->match_hmap_node.hash);
+ hindex_insert(&uuid_flow_table, &f->uuid_hindex_node,
+ f->uuid_hindex_node.hash);
+}
+
+/* Removes a bundles of flows from the flow table. */
+void
+ofctrl_remove_flows(const struct uuid *uuid)
+{
+ struct ovn_flow *f, *next;
+ HINDEX_FOR_EACH_WITH_HASH_SAFE (f, next, uuid_hindex_node, uuid_hash(uuid),
+ &uuid_flow_table) {
+ if (uuid_equals(&f->uuid, uuid)) {
+ hmap_remove(&match_flow_table, &f->match_hmap_node);
+ hindex_remove(&uuid_flow_table, &f->uuid_hindex_node);
+ ovn_flow_destroy(f);
+ }
}
+}
- hmap_insert(desired_flows, &f->hmap_node, f->hmap_node.hash);
+/* Shortcut to remove all flows matching the supplied UUID and add this
+ * flow. */
+void
+ofctrl_set_flow(uint8_t table_id, uint16_t priority,
+ const struct match *match, const struct ofpbuf *actions,
+ const struct uuid *uuid)
+{
+ ofctrl_remove_flows(uuid);
+ ofctrl_add_flow(table_id, priority, match, actions, uuid);
}
\f
/* ovn_flow. */
-/* Returns a hash of the key in 'f'. */
+/* Duplicate an ovn_flow structure. */
+struct ovn_flow *
+ofctrl_dup_flow(struct ovn_flow *src)
+{
+ struct ovn_flow *dst = xmalloc(sizeof *dst);
+ dst->table_id = src->table_id;
+ dst->priority = src->priority;
+ dst->match = src->match;
+ dst->ofpacts = xmemdup(src->ofpacts, src->ofpacts_len);
+ dst->ofpacts_len = src->ofpacts_len;
+ dst->uuid = src->uuid;
+ dst->match_hmap_node.hash = ovn_flow_match_hash(dst);
+ dst->uuid_hindex_node.hash = uuid_hash(&src->uuid);
+ return dst;
+}
+
+/* Returns a hash of the match key in 'f'. */
static uint32_t
-ovn_flow_hash(const struct ovn_flow *f)
+ovn_flow_match_hash(const struct ovn_flow *f)
{
return hash_2words((f->table_id << 16) | f->priority,
match_hash(&f->match, 0));
+}
+/* Compare two flows and return -1, 0, 1 based on whether a if less than,
+ * equal to or greater than b. */
+static int
+ovn_flow_compare_flows(struct ovn_flow *a, struct ovn_flow *b)
+{
+ return uuid_compare_3way(&a->uuid, &b->uuid);
}
-/* Finds and returns an ovn_flow in 'flow_table' whose key is identical to
- * 'target''s key, or NULL if there is none. */
+/* Given a list of ovn_flows, goes through the list and returns
+ * a single flow, in a deterministic way. */
static struct ovn_flow *
-ovn_flow_lookup(struct hmap *flow_table, const struct ovn_flow *target)
+ovn_flow_select_from_list(struct ovs_list *flows)
+{
+ struct ovn_flow *candidate;
+ struct ovn_flow *answer = NULL;
+ LIST_FOR_EACH (candidate, list_node, flows) {
+ if (!answer || ovn_flow_compare_flows(candidate, answer) < 0) {
+ answer = candidate;
+ }
+ }
+ return answer;
+}
+
+/* Initializes and files in the supplied list with ovn_flows from 'flow_table'
+ * whose key is identical to 'target''s key. */
+static void
+ovn_flow_lookup(struct hmap *flow_table, const struct ovn_flow *target,
+ struct ovs_list *answer)
{
struct ovn_flow *f;
- HMAP_FOR_EACH_WITH_HASH (f, hmap_node, target->hmap_node.hash,
+ ovs_list_init(answer);
+ HMAP_FOR_EACH_WITH_HASH (f, match_hmap_node, target->match_hmap_node.hash,
flow_table) {
if (f->table_id == target->table_id
&& f->priority == target->priority
&& match_equal(&f->match, &target->match)) {
- return f;
+ ovs_list_push_back(answer, &f->list_node);
}
}
- return NULL;
}
static char *
\f
/* Flow tables of struct ovn_flow. */
-static void
-ovn_flow_table_clear(struct hmap *flow_table)
+void
+ovn_flow_table_clear(void)
{
- struct ovn_flow *f;
- HMAP_FOR_EACH_POP (f, hmap_node, flow_table) {
+ struct ovn_flow *f, *next;
+ HMAP_FOR_EACH_SAFE (f, next, match_hmap_node, &match_flow_table) {
+ hmap_remove(&match_flow_table, &f->match_hmap_node);
+ hindex_remove(&uuid_flow_table, &f->uuid_hindex_node);
ovn_flow_destroy(f);
}
}
static void
-ovn_flow_table_destroy(struct hmap *flow_table)
+ovn_flow_table_destroy(void)
{
- ovn_flow_table_clear(flow_table);
- hmap_destroy(flow_table);
+ ovn_flow_table_clear();
+ hmap_destroy(&match_flow_table);
+ hindex_destroy(&uuid_flow_table);
}
\f
/* Flow table update. */
}
\f
-/* Replaces the flow table on the switch, if possible, by the flows in
- * 'flow_table', which should have been added with ofctrl_add_flow().
- * Regardless of whether the flow table is updated, this deletes all of the
- * flows from 'flow_table' and frees them. (The hmap itself isn't
- * destroyed.)
+/* Replaces the flow table on the switch, if possible, by the flows in added
+ * with ofctrl_add_flow().
*
* Replaces the group table on the switch, if possible, by the groups in
* 'group_table->desired_groups'. Regardless of whether the group table
*
* This should be called after ofctrl_run() within the main loop. */
void
-ofctrl_put(struct hmap *flow_table, struct group_table *group_table)
+ofctrl_put(struct group_table *group_table)
{
if (!groups) {
groups = group_table;
/* The flow table can be updated if the connection to the switch is up and
* in the correct state and not backlogged with existing flow_mods. (Our
* criteria for being backlogged appear very conservative, but the socket
- * between ovn-controller and OVS provides some buffering.) Otherwise,
- * discard the flows. A solution to either of those problems will cause us
- * to wake up and retry. */
+ * between ovn-controller and OVS provides some buffering.) */
if (state != S_UPDATE_FLOWS
|| rconn_packet_counter_n_packets(tx_counter)) {
- ovn_flow_table_clear(flow_table);
ovn_group_table_clear(group_table, false);
return;
}
* longer desired, delete them; if any of them should have different
* actions, update them. */
struct ovn_flow *i, *next;
- HMAP_FOR_EACH_SAFE (i, next, hmap_node, &installed_flows) {
- struct ovn_flow *d = ovn_flow_lookup(flow_table, i);
- if (!d) {
+ HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
+ struct ovs_list matches;
+ ovn_flow_lookup(&match_flow_table, i, &matches);
+ if (ovs_list_is_empty(&matches)) {
/* Installed flow is no longer desirable. Delete it from the
* switch and from installed_flows. */
struct ofputil_flow_mod fm = {
.command = OFPFC_DELETE_STRICT,
};
queue_flow_mod(&fm);
- ovn_flow_log(i, "removing");
+ ovn_flow_log(i, "removing installed");
- hmap_remove(&installed_flows, &i->hmap_node);
+ hmap_remove(&installed_flows, &i->match_hmap_node);
ovn_flow_destroy(i);
} else {
+ /* Since we still have desired flows that match this key,
+ * select one and compare both its actions and uuid.
+ * If the actions aren't the same, queue and update
+ * action for the install flow. If the uuid has changed
+ * update that as well. */
+ struct ovn_flow *d = ovn_flow_select_from_list(&matches);
+ if (!uuid_equals(&i->uuid, &d->uuid)) {
+ /* Update installed flow's UUID. */
+ i->uuid = d->uuid;
+ }
if (!ofpacts_equal(i->ofpacts, i->ofpacts_len,
d->ofpacts, d->ofpacts_len)) {
/* Update actions in installed flow. */
.command = OFPFC_MODIFY_STRICT,
};
queue_flow_mod(&fm);
- ovn_flow_log(i, "updating");
+ ovn_flow_log(i, "updating installed");
/* Replace 'i''s actions by 'd''s. */
free(i->ofpacts);
- i->ofpacts = d->ofpacts;
+ i->ofpacts = xmemdup(d->ofpacts, d->ofpacts_len);
i->ofpacts_len = d->ofpacts_len;
- d->ofpacts = NULL;
- d->ofpacts_len = 0;
}
-
- hmap_remove(flow_table, &d->hmap_node);
- ovn_flow_destroy(d);
}
}
- /* The previous loop removed from 'flow_table' all of the flows that are
- * already installed. Thus, any flows remaining in 'flow_table' need to
- * be added to the flow table. */
- struct ovn_flow *d;
- HMAP_FOR_EACH_SAFE (d, next, hmap_node, flow_table) {
- /* Send flow_mod to add flow. */
- struct ofputil_flow_mod fm = {
- .match = d->match,
- .priority = d->priority,
- .table_id = d->table_id,
- .ofpacts = d->ofpacts,
- .ofpacts_len = d->ofpacts_len,
- .command = OFPFC_ADD,
- };
- queue_flow_mod(&fm);
- ovn_flow_log(d, "adding");
-
- /* Move 'd' from 'flow_table' to installed_flows. */
- hmap_remove(flow_table, &d->hmap_node);
- hmap_insert(&installed_flows, &d->hmap_node, d->hmap_node.hash);
+ /* Iterate through the desired flows and add those that aren't found
+ * in the installed flow table. */
+ struct ovn_flow *c;
+ HMAP_FOR_EACH (c, match_hmap_node, &match_flow_table) {
+ struct ovs_list matches;
+ ovn_flow_lookup(&installed_flows, c, &matches);
+ if (ovs_list_is_empty(&matches)) {
+ /* We have a key that isn't in the installed flows, so
+ * look back into the desired flow list for all flows
+ * that match this key, and select the one to be installed. */
+ struct ovs_list candidates;
+ ovn_flow_lookup(&match_flow_table, c, &candidates);
+ struct ovn_flow *d = ovn_flow_select_from_list(&candidates);
+ /* Send flow_mod to add flow. */
+ struct ofputil_flow_mod fm = {
+ .match = d->match,
+ .priority = d->priority,
+ .table_id = d->table_id,
+ .ofpacts = d->ofpacts,
+ .ofpacts_len = d->ofpacts_len,
+ .command = OFPFC_ADD,
+ };
+ queue_flow_mod(&fm);
+ ovn_flow_log(d, "adding installed");
+
+ /* Copy 'd' from 'flow_table' to installed_flows. */
+ struct ovn_flow *new_node = ofctrl_dup_flow(d);
+ hmap_insert(&installed_flows, &new_node->match_hmap_node,
+ new_node->match_hmap_node.hash);
+ }
}
/* Iterate through the installed groups from previous runs. If they