[ovs-dev] [PATCH ovn v2 8/9] ofctrl: Incremental processing for flow installation by tracking.

Han Zhou hzhou at ovn.org
Mon Sep 7 06:45:41 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 3000 HVs and 30k lports, the end-to-end latency between
the moment a lflow is updated in SB DB and the moment when all the 3K HVs
complete OVS flow updating has reduced around 60% (from 1s to 400ms).

Below is the perf result for a ovn-controller processing a new port-binding:

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)

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 | 289 ++++++++++++++++++++++++++++++++++++++++++----------
 controller/ofctrl.h |   6 +-
 2 files changed, 240 insertions(+), 55 deletions(-)

diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index bc6a115..a2aa45d 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -101,6 +101,39 @@ struct ovn_flow {
  *
  * The links are updated whenever there is a change in desired flows, which is
  * usually triggered by a SB data change in I-P engine.
+ *
+ * ** 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 desired_flow {
     struct ovn_flow flow;
@@ -117,6 +150,11 @@ struct desired_flow {
 
     /* Node in installed_flow.desired_refs list. */
     struct ovs_list installed_ref_list_node;
+
+    /* For tracking. */
+    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. */
 };
 
 struct sb_to_flow {
@@ -789,6 +827,62 @@ unlink_all_refs_for_installed_flow(struct installed_flow *i)
     }
 }
 

+static void
+track_flow_add_or_modify(struct ovn_desired_flow_table *flow_table,
+                         struct desired_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 desired_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->installed_flow) {
+            /* If it is not installed yet, simply destroy it. */
+            desired_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 desired_flow *f)
+{
+    if (flow_table->change_tracked) {
+        track_flow_del(flow_table, f);
+    } else {
+        if (f->installed_flow) {
+            unlink_installed_to_desired(f->installed_flow, f);
+        }
+        desired_flow_destroy(f);
+    }
+}
+

 static struct sb_to_flow *
 sb_to_flow_find(struct hmap *uuid_flow_table, const struct uuid *sb_uuid)
 {
@@ -861,6 +955,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->flow.hash);
     link_flow_to_sb(flow_table, f, sb_uuid);
+    track_flow_add_or_modify(flow_table, f);
     ovn_flow_log(&f->flow, "ofctrl_add_flow");
 }
 
@@ -912,6 +1007,7 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows,
                     f->flow.hash);
     }
     link_flow_to_sb(desired_flows, f, sb_uuid);
+    track_flow_add_or_modify(desired_flows, f);
 
     if (existing) {
         ovn_flow_log(&f->flow, "ofctrl_add_or_append_flow (append)");
@@ -941,10 +1037,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->installed_flow) {
-                unlink_installed_to_desired(f->installed_flow, f);
-            }
-            desired_flow_destroy(f);
+            track_or_destroy_for_flow_del(flow_table, f);
         }
     }
     hmap_remove(&flow_table->uuid_flow_table, &stf->hmap_node);
@@ -1019,10 +1112,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->installed_flow) {
-                unlink_installed_to_desired(f->installed_flow, f);
-            }
-            desired_flow_destroy(f);
+            track_or_destroy_for_flow_del(flow_table, f);
         } else {
             ovs_list_insert(&to_be_removed, &f->list_node);
         }
@@ -1056,10 +1146,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->installed_flow) {
-            unlink_installed_to_desired(f->installed_flow, f);
-        }
-        desired_flow_destroy(f);
+        track_or_destroy_for_flow_del(flow_table, f);
     }
 
 }
@@ -1105,7 +1192,9 @@ desired_flow_alloc(uint8_t table_id, uint16_t priority, uint64_t cookie,
     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->installed_flow = NULL;
+    f->is_deleted = false;
     ovn_flow_init(&f->flow, table_id, priority, cookie, match, actions);
 
     return f;
@@ -1245,11 +1334,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 desired_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->installed_flow) {
+                unlink_installed_to_desired(f->installed_flow, f);
+            }
+            desired_flow_destroy(f);
+        }
+    }
+
     struct sb_to_flow *stf, *next;
     HMAP_FOR_EACH_SAFE (stf, next, hmap_node,
                         &flow_table->uuid_flow_table) {
@@ -1537,6 +1642,117 @@ 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 installed_flow *i, *next;
+    HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
+        unlink_all_refs_for_installed_flow(i);
+        struct desired_flow *d =
+            desired_flow_lookup(flow_table, &i->flow, NULL);
+        if (!d) {
+            /* Installed flow is no longer desirable.  Delete it from the
+             * switch and from installed_flows. */
+            installed_flow_del(&i->flow, msgs);
+            ovn_flow_log(&i->flow, "removing installed");
+
+            hmap_remove(&installed_flows, &i->match_hmap_node);
+            installed_flow_destroy(i);
+        } else {
+            if (!ofpacts_equal(i->flow.ofpacts, i->flow.ofpacts_len,
+                               d->flow.ofpacts, d->flow.ofpacts_len) ||
+                i->flow.cookie != d->flow.cookie) {
+                installed_flow_mod(&i->flow, &d->flow, msgs);
+                ovn_flow_log(&i->flow, "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 desired_flow *d;
+    HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) {
+        i = installed_flow_lookup(&d->flow);
+        if (!i) {
+            ovn_flow_log(&d->flow, "adding installed");
+            installed_flow_add(&d->flow, msgs);
+
+            /* Copy 'd' from 'flow_table' to installed_flows. */
+            i = installed_flow_dup(d);
+            hmap_insert(&installed_flows, &i->match_hmap_node, i->flow.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 desired_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->installed_flow) {
+                struct installed_flow *i = f->installed_flow;
+                unlink_installed_to_desired(i, f);
+
+                if (!i->desired_flow) {
+                    installed_flow_del(&i->flow, msgs);
+                    ovn_flow_log(&i->flow, "removing installed (tracked)");
+
+                    hmap_remove(&installed_flows, &i->match_hmap_node);
+                    installed_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 desired_flow *d = i->desired_flow;
+                    ovn_flow_log(&i->flow, "updating installed (tracked)");
+                    installed_flow_mod(&i->flow, &d->flow, msgs);
+                }
+            }
+            desired_flow_destroy(f);
+        } else {
+            /* The desired flow was added or modified. */
+            struct installed_flow *i = installed_flow_lookup(&f->flow);
+            if (!i) {
+                /* Adding a new flow. */
+                installed_flow_add(&f->flow, msgs);
+                ovn_flow_log(&f->flow, "adding installed (tracked)");
+
+                /* Copy 'f' from 'flow_table' to installed_flows. */
+                struct installed_flow *new_node = installed_flow_dup(f);
+                hmap_insert(&installed_flows, &new_node->match_hmap_node,
+                            new_node->flow.hash);
+                link_installed_to_desired(new_node, f);
+            } else if (i->desired_flow == f) {
+                /* The installed flow is installed for f, but f has change
+                 * tracked, so it must have been modified. */
+                ovn_flow_log(&i->flow, "updating installed (tracked)");
+                installed_flow_mod(&i->flow, &f->flow, 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
@@ -1651,48 +1867,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 installed_flow *i, *next;
-    HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
-        unlink_all_refs_for_installed_flow(i);
-        struct desired_flow *d = desired_flow_lookup(flow_table, &i->flow,
-                                                     NULL);
-        if (!d) {
-            /* Installed flow is no longer desirable.  Delete it from the
-             * switch and from installed_flows. */
-            installed_flow_del(&i->flow, &msgs);
-            ovn_flow_log(&i->flow, "removing installed");
-            hmap_remove(&installed_flows, &i->match_hmap_node);
-            installed_flow_destroy(i);
-        } else {
-            if (!ofpacts_equal(i->flow.ofpacts, i->flow.ofpacts_len,
-                               d->flow.ofpacts, d->flow.ofpacts_len) ||
-                i->flow.cookie != d->flow.cookie) {
-                ovn_flow_log(&i->flow, "updating installed");
-                installed_flow_mod(&i->flow, &d->flow, &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 desired_flow *d;
-    HMAP_FOR_EACH (d, match_hmap_node, &flow_table->match_flow_table) {
-        i = installed_flow_lookup(&d->flow);
-        if (!i) {
-            installed_flow_add(&d->flow, &msgs);
-            ovn_flow_log(&d->flow, "adding installed");
-
-            /* Copy 'd' from 'flow_table' to installed_flows. */
-            i = installed_flow_dup(d);
-            hmap_insert(&installed_flows, &i->match_hmap_node,
-                        i->flow.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
@@ -1806,6 +1984,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