[ovs-dev] [PATCH ovn 8/9] ofctrl: Incremental processing for flow installation by tracking.
Han Zhou
hzhou at ovn.org
Fri Aug 21 19:16:22 UTC 2020
With incremental processing for flow computation, the bottle neck of
ovn-controller in large scale environment is in the flow installation
(ofctrl_put()), which does full comparison between the two big flow tables: the
installed flows and desired flows.
This patch implements tracking desired flow changes when flows are
incrementally computed by I-P engine, and then incrementally processing the
flow installation using the tracked information in ofctrl_put(). It falls back
to the full comparison whenever tracking information is unavailable, e.g. when
I-P engine triggers full recompute.
In ovn-scale-test with 1200 HVs and 12k lports, the perf result for binding a
new port:
Beore:
+ 96.76% 0.00% ovn-controller [unknown] [k] 0xffffffffffffffff
+ 90.21% 0.00% ovn-controller ovn-controller [.] main
+ 39.93% 1.19% ovn-controller ovn-controller [.] ofctrl_put
+ 31.27% 12.47% ovn-controller ovn-controller [.] ovn_flow_lookup
+ 22.12% 3.12% ovn-controller ovn-controller [.] encaps_run
+ 18.69% 2.77% ovn-controller ovn-controller [.] minimatch_equal
+ 17.63% 4.11% ovn-controller ovn-controller [.] patch_run
+ 15.91% 0.00% ovn-controller ovn-controller [.] add_bridge_mappings (inlined)
+ 14.03% 12.08% ovn-controller ovn-controller [.] minimask_equal
+ 12.41% 0.00% ovn-controller ovn-controller [.] chassis_tunnel_add (inlined)
+ 11.40% 0.00% ovn-controller ovn-controller [.] tunnel_add (inlined)
+ 9.61% 0.00% ovn-controller ovn-controller [.] ofpacts_equal
+ 8.64% 0.39% ovn-controller ovn-controller [.] physical_run
+ 8.55% 8.29% ovn-controller ovn-controller [.] next_real_row
+ 7.28% 0.00% ovn-controller ovn-controller [.] hmap_first_with_hash (inlined)
+ 6.57% 6.57% ovn-controller ovn-controller [.] ovsdb_idl_next_row
+ 6.44% 0.00% ovn-controller ovn-controller [.] hmap_next (inlined)
+ 6.43% 0.00% ovn-controller libc-2.27.so [.] 0x00007f3f9210ebaa
+ 6.40% 1.33% ovn-controller ovn-controller [.] consider_port_binding
After:
+ 94.59% 0.00% ovn-controller [unknown] [k] 0xffffffffffffffff
+ 83.56% 0.09% ovn-controller ovn-controller [.] main
+ 35.37% 3.13% ovn-controller ovn-controller [.] encaps_run
+ 27.54% 7.53% ovn-controller ovn-controller [.] patch_run
+ 24.86% 0.00% ovn-controller ovn-controller [.] add_bridge_mappings (inlined)
+ 20.01% 0.00% ovn-controller ovn-controller [.] chassis_tunnel_add (inlined)
+ 18.51% 0.00% ovn-controller ovn-controller [.] tunnel_add (inlined)
+ 14.08% 0.17% ovn-controller ovn-controller [.] physical_run
+ 11.37% 11.28% ovn-controller ovn-controller [.] next_real_row
+ 10.50% 2.59% ovn-controller ovn-controller [.] consider_port_binding
...
+ 2.14% 0.32% ovn-controller ovn-controller [.] ofctrl_put ▒
Before the optimization, ofctrl_put took 40% of CPU, and now it disappears from the hot spots.
Signed-off-by: Han Zhou <hzhou at ovn.org>
---
controller/ofctrl.c | 350 ++++++++++++++++++++++++++++++++++++++++++----------
controller/ofctrl.h | 6 +-
2 files changed, 291 insertions(+), 65 deletions(-)
diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index 6b71fa1..6349884 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -51,7 +51,77 @@
VLOG_DEFINE_THIS_MODULE(ofctrl);
-/* An OpenFlow flow. */
+/* An OpenFlow flow.
+ *
+ * There are two types of flows represented using this structure:
+ * - Desired flows, in struct ovn_desired_flow_table. (as output data of I-P
+ * engine)
+ * - Installed flows, in static variable installed_flows.
+ *
+ * Desired flows are updated by I-P engine.
+ * - They are added/removed incrementally when I-P engine is able to process
+ * the changes incrementally, or
+ * - Completely cleared and recomputed by I-P engine when recompute happens.
+ *
+ * Installed flows are updated in ofctrl_put for maintaining the flow
+ * installation to OVS. They are updated according to desired flows: either by
+ * processing the tracked desired flow changes, or by comparing desired flows
+ * with currently installed flows when tracked desired flows changes are not
+ * available.
+ *
+ * In addition, when ofctrl state machine enters S_CLEAR, the installed flows
+ * will be cleared. (This happens in initialization phase and also when
+ * ovs-vswitchd is disconnected/reconnected).
+ *
+ * ** Flow references **
+ *
+ * Links are maintained between desired flows and SB data. The relationship
+ * is M to N. This link is updated whenever there is a change in desired flows,
+ * which is usually triggered by a SB data change in I-P engine.
+ *
+ * Links are maintained between installed flows and desired flows as well. The
+ * relationship is 1 to N. A link is added when a flow addition is processed.
+ * A link is removed when a flow deletion is processed or during desired flow
+ * table clear, or during installed flow table clear.
+ *
+ * NOTE: desired flows and installed flows are different copies existing in
+ * different tables. A installed flow is usually copied (ignoring the link
+ * information) from a desired flow, but they never get *converted* directly to
+ * each other.
+ *
+ * ** Flow tracking **
+ *
+ * A desired flow can be tracked - listed in ovn_desired_flow_table's
+ * tracked_flows.
+ *
+ * Tracked flows is initially empty, and stays empty after the first run of I-P
+ * engine when installed flows are initially populated. After that, flow
+ * changes are tracked when I-P engine incrementally computes flow changes.
+ * Tracked flows are then processed and removed completely in ofctrl_put.
+ * ("processed" means OpenFlow change messages are composed and sent/queued to
+ * OVS, which ensures flows in OVS is always in sync (eventually) with the
+ * installed flows table).
+ *
+ * In case of full recompute of I-P engine, tracked flows are not
+ * added/removed, and ofctrl_put will not rely on tracked flows. (It is I-P
+ * engine's responsibility to ensure the tracked flows are cleared before
+ * recompute).
+ *
+ * Tracked flows can be preserved across multiple I-P engine runs - if in some
+ * iterations ofctrl_put() is skipped. Tracked flows are cleared only when it
+ * is consumed or when flow recompute happens.
+ *
+ * The "change_tracked" member of desired flow table maintains the status of
+ * whether flow changes are tracked or not. It is always set to true when
+ * ofctrl_put is completed, and transition to false whenever
+ * ovn_desired_flow_table_clear is called.
+ *
+ * NOTE: A tracked flow is just a reference to a desired flow, instead of a new
+ * copy. When a desired flow is removed and tracked, it is removed from the
+ * match_flow_table and uuid_flow_table indexes, and added to the tracked_flows
+ * list, marking is_deleted = true, but not immediately destroyed. It is
+ * destroyed when the tracking is processed for installed flow updates.
+ */
struct ovn_flow {
struct hmap_node match_hmap_node; /* For match based hashing. */
struct ovs_list list_node; /* For handling lists of flows. */
@@ -80,7 +150,12 @@ struct ovn_flow {
/* For desired flows only: node in references list. */
struct ovs_list installed_ref_list_node;
- /* Key. */
+ /* For tracked desired flows only. */
+ struct ovs_list track_list_node; /* node in ovn_desired_flow_table's
+ * tracked_flows list. */
+ bool is_deleted; /* If the tracked flow is deleted. */
+
+ /* Match Index Key. */
uint8_t table_id;
uint16_t priority;
struct minimatch match;
@@ -719,6 +794,62 @@ unlink_all_refs_for_installed_flow(struct ovn_flow *i)
}
}
+static void
+track_flow_add_or_modify(struct ovn_desired_flow_table *flow_table,
+ struct ovn_flow *f)
+{
+ if (!flow_table->change_tracked) {
+ return;
+ }
+
+ /* If same node (flow adding/modifying) was tracked, remove it from
+ * tracking first. */
+ if (!ovs_list_is_empty(&f->track_list_node)) {
+ ovs_list_remove(&f->track_list_node);
+ }
+ f->is_deleted = false;
+ ovs_list_push_back(&flow_table->tracked_flows, &f->track_list_node);
+
+}
+
+static void
+track_flow_del(struct ovn_desired_flow_table *flow_table,
+ struct ovn_flow *f)
+{
+ if (!flow_table->change_tracked) {
+ return;
+ }
+ /* If same node (flow adding/modifying) was tracked, remove it from
+ * tracking first. */
+ if (!ovs_list_is_empty(&f->track_list_node)) {
+ ovs_list_remove(&f->track_list_node);
+ if (!f->peer) {
+ /* If it is not installed yet, simply destroy it. */
+ ovn_flow_destroy(f);
+ return;
+ }
+ }
+ f->is_deleted = true;
+ ovs_list_push_back(&flow_table->tracked_flows, &f->track_list_node);
+}
+
+/* When a desired flow is being removed, depending on "change_tracked", this
+ * function either unlinks a desired flow from installed flow and destroy it,
+ * or do nothing but track it. */
+static void
+track_or_destroy_for_flow_del(struct ovn_desired_flow_table *flow_table,
+ struct ovn_flow *f)
+{
+ if (flow_table->change_tracked) {
+ track_flow_del(flow_table, f);
+ } else {
+ if (f->peer) {
+ unlink_installed_to_desired(f->peer, f);
+ }
+ ovn_flow_destroy(f);
+ }
+}
+
static struct sb_to_flow *
sb_to_flow_find(struct hmap *uuid_flow_table, const struct uuid *sb_uuid)
{
@@ -791,6 +922,7 @@ ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table,
hmap_insert(&flow_table->match_flow_table, &f->match_hmap_node,
f->match_hmap_node.hash);
link_flow_to_sb(flow_table, f, sb_uuid);
+ track_flow_add_or_modify(flow_table, f);
ovn_flow_log(f, "ofctrl_add_flow");
}
@@ -835,12 +967,14 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows,
ofpbuf_uninit(&compound);
ovn_flow_destroy(f);
+
f = existing;
} else {
hmap_insert(&desired_flows->match_flow_table, &f->match_hmap_node,
f->match_hmap_node.hash);
}
link_flow_to_sb(desired_flows, f, sb_uuid);
+ track_flow_add_or_modify(desired_flows, f);
if (existing) {
ovn_flow_log(f, "ofctrl_add_or_append_flow (append)");
@@ -870,10 +1004,7 @@ remove_flows_from_sb_to_flow(struct ovn_desired_flow_table *flow_table,
}
hmap_remove(&flow_table->match_flow_table,
&f->match_hmap_node);
- if (f->peer) {
- unlink_installed_to_desired(f->peer, f);
- }
- ovn_flow_destroy(f);
+ track_or_destroy_for_flow_del(flow_table, f);
}
}
hmap_remove(&flow_table->uuid_flow_table, &stf->hmap_node);
@@ -948,10 +1079,7 @@ flood_remove_flows_for_sb_uuid(struct ovn_desired_flow_table *flow_table,
* be empty in most cases. */
hmap_remove(&flow_table->match_flow_table,
&f->match_hmap_node);
- if (f->peer) {
- unlink_installed_to_desired(f->peer, f);
- }
- ovn_flow_destroy(f);
+ track_or_destroy_for_flow_del(flow_table, f);
} else {
ovs_list_insert(&to_be_removed, &f->list_node);
}
@@ -985,10 +1113,7 @@ flood_remove_flows_for_sb_uuid(struct ovn_desired_flow_table *flow_table,
ovs_list_remove(&f->list_node);
hmap_remove(&flow_table->match_flow_table,
&f->match_hmap_node);
- if (f->peer) {
- unlink_installed_to_desired(f->peer, f);
- }
- ovn_flow_destroy(f);
+ track_or_destroy_for_flow_del(flow_table, f);
}
}
@@ -1011,16 +1136,23 @@ ofctrl_flood_remove_flows(struct ovn_desired_flow_table *flow_table,
}
/* ovn_flow. */
+static inline void
+ovn_flow_init(struct ovn_flow *f)
+{
+ ovs_list_init(&f->references);
+ ovs_list_init(&f->list_node);
+ ovs_list_init(&f->installed_ref_list_node);
+ ovs_list_init(&f->track_list_node);
+ f->peer = NULL;
+ f->is_deleted = false;
+}
static struct ovn_flow *
ovn_flow_alloc(uint8_t table_id, uint16_t priority, uint64_t cookie,
const struct match *match, const struct ofpbuf *actions)
{
struct ovn_flow *f = xmalloc(sizeof *f);
- ovs_list_init(&f->references);
- ovs_list_init(&f->list_node);
- ovs_list_init(&f->installed_ref_list_node);
- f->peer = NULL;
+ ovn_flow_init(f);
f->table_id = table_id;
f->priority = priority;
minimatch_init(&f->match, match);
@@ -1045,10 +1177,7 @@ static struct ovn_flow *
ovn_flow_dup(struct ovn_flow *src)
{
struct ovn_flow *dst = xmalloc(sizeof *dst);
- ovs_list_init(&dst->references);
- ovs_list_init(&dst->list_node);
- ovs_list_init(&dst->installed_ref_list_node);
- dst->peer = NULL;
+ ovn_flow_init(dst);
dst->table_id = src->table_id;
dst->priority = src->priority;
minimatch_clone(&dst->match, &src->match);
@@ -1135,11 +1264,27 @@ ovn_desired_flow_table_init(struct ovn_desired_flow_table *flow_table)
{
hmap_init(&flow_table->match_flow_table);
hmap_init(&flow_table->uuid_flow_table);
+ ovs_list_init(&flow_table->tracked_flows);
+ flow_table->change_tracked = false;
}
void
ovn_desired_flow_table_clear(struct ovn_desired_flow_table *flow_table)
{
+ flow_table->change_tracked = false;
+
+ struct ovn_flow *f, *f_next;
+ LIST_FOR_EACH_SAFE (f, f_next, track_list_node,
+ &flow_table->tracked_flows) {
+ ovs_list_remove(&f->track_list_node);
+ if (f->is_deleted) {
+ if (f->peer) {
+ unlink_installed_to_desired(f->peer, f);
+ }
+ ovn_flow_destroy(f);
+ }
+ }
+
struct sb_to_flow *stf, *next;
HMAP_FOR_EACH_SAFE (stf, next, hmap_node,
&flow_table->uuid_flow_table) {
@@ -1425,6 +1570,118 @@ installed_flow_del(struct ovn_flow *i, struct ovs_list *msgs)
add_flow_mod(&fm, msgs);
}
+static void
+update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
+ struct ovs_list *msgs)
+{
+ ovs_assert(ovs_list_is_empty(&flow_table->tracked_flows));
+ /* Iterate through all of the installed flows. If any of them are no
+ * 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, match_hmap_node, &installed_flows) {
+ unlink_all_refs_for_installed_flow(i);
+ struct ovn_flow *d = ovn_flow_lookup(&flow_table->match_flow_table,
+ i, NULL);
+ if (!d) {
+ /* Installed flow is no longer desirable. Delete it from the
+ * switch and from installed_flows. */
+ installed_flow_del(i, msgs);
+ ovn_flow_log(i, "removing installed");
+
+ hmap_remove(&installed_flows, &i->match_hmap_node);
+ ovn_flow_destroy(i);
+ } else {
+ if (!ofpacts_equal(i->ofpacts, i->ofpacts_len,
+ d->ofpacts, d->ofpacts_len) ||
+ i->cookie != d->cookie) {
+ installed_flow_mod(i, d, msgs);
+ ovn_flow_log(i, "updating installed");
+ }
+ link_installed_to_desired(i, d);
+
+ }
+ }
+
+ /* Iterate through the desired flows and add those that aren't found
+ * in the installed flow table. */
+ struct ovn_flow *d;
+ HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) {
+ i = ovn_flow_lookup(&installed_flows, d, NULL);
+ if (!i) {
+ ovn_flow_log(d, "adding installed");
+ installed_flow_add(d, msgs);
+
+ /* Copy 'd' from 'flow_table' to installed_flows. */
+ i = ovn_flow_dup(d);
+ hmap_insert(&installed_flows, &i->match_hmap_node,
+ i->match_hmap_node.hash);
+ }
+ link_installed_to_desired(i, d);
+ }
+}
+
+static void
+update_installed_flows_by_track(struct ovn_desired_flow_table *flow_table,
+ struct ovs_list *msgs)
+{
+ struct ovn_flow *f, *f_next;
+ LIST_FOR_EACH_SAFE (f, f_next, track_list_node,
+ &flow_table->tracked_flows) {
+ ovs_list_remove(&f->track_list_node);
+ if (f->is_deleted) {
+ /* The desired flow was deleted */
+ if (f->peer) {
+ struct ovn_flow *i = f->peer;
+ unlink_installed_to_desired(i, f);
+
+ if (!i->peer) {
+ installed_flow_del(i, msgs);
+ ovn_flow_log(i, "removing installed (tracked)");
+
+ hmap_remove(&installed_flows, &i->match_hmap_node);
+ ovn_flow_destroy(i);
+ } else {
+ /* There are other desired flow(s) referencing this
+ * installed flow, so update the OVS flow for the new
+ * active flow (at least the cookie will be different,
+ * even if the actions are the same). */
+ struct ovn_flow *d = i->peer;
+ ovn_flow_log(i, "updating installed (tracked)");
+ installed_flow_mod(i, d, msgs);
+ }
+ }
+ ovn_flow_destroy(f);
+ } else {
+ /* The desired flow was added or modified. */
+ struct ovn_flow *i = ovn_flow_lookup(&installed_flows, f, NULL);
+ if (!i) {
+ /* Adding a new flow. */
+ installed_flow_add(f, msgs);
+ ovn_flow_log(f, "adding installed (tracked)");
+
+ /* Copy 'f' from 'flow_table' to installed_flows. */
+ struct ovn_flow *new_node = ovn_flow_dup(f);
+ hmap_insert(&installed_flows, &new_node->match_hmap_node,
+ new_node->match_hmap_node.hash);
+ link_installed_to_desired(new_node, f);
+ } else if (i->peer == f) {
+ /* The installed flow is installed for f, but f has change
+ * tracked, so it must have been modified. */
+ ovn_flow_log(i, "updating installed (tracked)");
+ installed_flow_mod(i, f, msgs);
+ } else {
+ /* Adding a new flow that conflicts with an existing installed
+ * flow, so just add it to the link. */
+ link_installed_to_desired(i, f);
+ }
+ /* The track_list_node emptyness is used to check if the node is
+ * already added to track list, so initialize it again here. */
+ ovs_list_init(&f->track_list_node);
+ }
+ }
+}
+
/* 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
@@ -1539,48 +1796,10 @@ ofctrl_put(struct ovn_desired_flow_table *flow_table,
}
}
- /* Iterate through all of the installed flows. If any of them are no
- * 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, match_hmap_node, &installed_flows) {
- unlink_all_refs_for_installed_flow(i);
- struct ovn_flow *d = ovn_flow_lookup(&flow_table->match_flow_table,
- i, NULL);
- if (!d) {
- /* Installed flow is no longer desirable. Delete it from the
- * switch and from installed_flows. */
- installed_flow_del(i, &msgs);
- ovn_flow_log(i, "removing installed");
- hmap_remove(&installed_flows, &i->match_hmap_node);
- ovn_flow_destroy(i);
- } else {
- if (!ofpacts_equal(i->ofpacts, i->ofpacts_len,
- d->ofpacts, d->ofpacts_len) ||
- i->cookie != d->cookie) {
- ovn_flow_log(i, "updating installed");
- installed_flow_mod(i, d, &msgs);
- }
- link_installed_to_desired(i, d);
-
- }
- }
-
- /* Iterate through the desired flows and add those that aren't found
- * in the installed flow table. */
- struct ovn_flow *d;
- HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) {
- i = ovn_flow_lookup(&installed_flows, d, NULL);
- if (!i) {
- installed_flow_add(d, &msgs);
- ovn_flow_log(d, "adding installed");
-
- /* Copy 'd' from 'flow_table' to installed_flows. */
- i= ovn_flow_dup(d);
- hmap_insert(&installed_flows, &i->match_hmap_node,
- i->match_hmap_node.hash);
- }
- link_installed_to_desired(i, d);
+ if (flow_table->change_tracked) {
+ update_installed_flows_by_track(flow_table, &msgs);
+ } else {
+ update_installed_flows_by_compare(flow_table, &msgs);
}
/* Iterate through the installed groups from previous runs. If they
@@ -1694,6 +1913,9 @@ ofctrl_put(struct ovn_desired_flow_table *flow_table,
/* We were completely up-to-date before and still are. */
cur_cfg = nb_cfg;
}
+
+ flow_table->change_tracked = true;
+ ovs_assert(ovs_list_is_empty(&flow_table->tracked_flows));
}
/* Looks up the logical port with the name 'port_name' in 'br_int_'. If
diff --git a/controller/ofctrl.h b/controller/ofctrl.h
index 8789ce4..64b0ea5 100644
--- a/controller/ofctrl.h
+++ b/controller/ofctrl.h
@@ -38,6 +38,11 @@ struct ovn_desired_flow_table {
/* SB uuid index for the cross reference nodes that link to the nodes in
* match_flow_table.*/
struct hmap uuid_flow_table;
+
+ /* Is flow changes tracked. */
+ bool change_tracked;
+ /* Tracked flow changes. */
+ struct ovs_list tracked_flows;
};
/* Interface for OVN main loop. */
@@ -99,7 +104,6 @@ void ofctrl_flood_remove_flows(struct ovn_desired_flow_table *,
struct hmap *flood_remove_nodes);
void ofctrl_flood_remove_add_node(struct hmap *flood_remove_nodes,
const struct uuid *sb_uuid);
-
void ovn_desired_flow_table_init(struct ovn_desired_flow_table *);
void ovn_desired_flow_table_clear(struct ovn_desired_flow_table *);
void ovn_desired_flow_table_destroy(struct ovn_desired_flow_table *);
--
2.1.0
More information about the dev
mailing list