[ovs-dev] [PATCH 3/3] Limit the number of generated conjunctions.

Mark Michelson mmichels at redhat.com
Fri Oct 25 21:06:31 UTC 2019


There is a maximum number of resubmits that can occur during packet
processing. Deliberately creating a flow table that might cross this
threshold is irresponsible.

This commit causes the ofctrl code to track the maximum width and depth
of conjunctions in the desired flow table. By multiplying them, we have
a possible worst case for number of resubmits required. If this number
exceeds a quarter of the maximum resubmits allowed, then we fall back to
forcing crossproducts.

The resulting flow table can end up being a mixture of conjunction and
non-conjunction flows if the limit is exceeded.

Signed-off-by: Mark Michelson <mmichels at redhat.com>
---
 controller/lflow.c  | 11 +++++++++
 controller/ofctrl.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 controller/ofctrl.h |  6 +++++
 include/ovn/expr.h  |  2 ++
 lib/expr.c          |  6 +++++
 5 files changed, 94 insertions(+)

diff --git a/controller/lflow.c b/controller/lflow.c
index 34b7c36a6..318066465 100644
--- a/controller/lflow.c
+++ b/controller/lflow.c
@@ -37,6 +37,13 @@
 VLOG_DEFINE_THIS_MODULE(lflow);
 
 COVERAGE_DEFINE(lflow_run);
+
+/* Limit maximum conjunctions to a quarter of the max
+ * resubmits. Unfortunatley, max resubmits is not publicly
+ * defined in a header file, so if max resubmits is changed
+ * from 4096, we have to make sure to update this as well
+ */
+#define MAX_CONJUNCTIONS (4096 / 4)
 
 /* Symbol table. */
 
@@ -602,6 +609,10 @@ consider_logical_flow(
     struct expr *prereqs;
     char *error;
 
+    uint32_t conj_worst_case;
+    conj_worst_case = flow_table->max_conj_width * flow_table->max_conj_depth;
+    expr_set_force_crossproduct(conj_worst_case >= MAX_CONJUNCTIONS);
+
     error = ovnacts_parse_string(lflow->actions, &pp, &ovnacts, &prereqs);
     if (error) {
         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 1);
diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index afb0036f1..2b2fde3c9 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -686,6 +686,64 @@ ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table,
                   f->uuid_hindex_node.hash);
 }
 
+static void
+get_conjunction_dimensions(const struct ovn_flow *f, uint32_t *conj_width_p,
+                           uint32_t *conj_depth_p)
+{
+    struct ofpact *ofpact;
+    uint32_t conj_width = 0;
+    uint32_t conj_depth = 0;
+    OFPACT_FOR_EACH (ofpact, f->ofpacts, f->ofpacts_len) {
+        if (ofpact->type == OFPACT_CONJUNCTION) {
+            struct ofpact_conjunction *conj = ofpact_get_CONJUNCTION(ofpact);
+            if (conj->n_clauses > conj_depth) {
+                conj_depth = conj->n_clauses;
+            }
+            conj_width++;
+        }
+    }
+
+    *conj_width_p = conj_width;
+    *conj_depth_p = conj_depth;
+}
+
+static void
+adjust_conjunction_count(struct ovn_desired_flow_table *desired_flows,
+                 const struct ovn_flow *f, bool add)
+{
+    uint32_t conj_width;
+    uint32_t conj_depth;
+
+    get_conjunction_dimensions(f, &conj_width, &conj_depth);
+
+    if (add) {
+        if (conj_width > desired_flows->max_conj_width) {
+            desired_flows->max_conj_width = conj_width;
+        }
+        if (conj_depth > desired_flows->max_conj_depth) {
+            desired_flows->max_conj_depth = conj_depth;
+        }
+    } else if (desired_flows->max_conj_width <= conj_width ||
+               desired_flows->max_conj_depth <= conj_depth) {
+        /* Removing either the widest or deepest conjunction.
+         * Walk the table and recalculate maximums
+         */
+        struct ovn_flow *iter;
+        desired_flows->max_conj_width = 0;
+        desired_flows->max_conj_depth = 0;
+        HMAP_FOR_EACH (iter, match_hmap_node,
+                       &desired_flows->match_flow_table) {
+            get_conjunction_dimensions(iter, &conj_width, &conj_depth);
+            if (conj_width > desired_flows->max_conj_width) {
+                desired_flows->max_conj_width = conj_width;
+            }
+            if (conj_depth > desired_flows->max_conj_depth) {
+                desired_flows->max_conj_depth = conj_depth;
+            }
+        }
+    }
+}
+
 /* Removes a bundles of flows from the flow table. */
 void
 ofctrl_remove_flows(struct ovn_desired_flow_table *flow_table,
@@ -697,6 +755,7 @@ ofctrl_remove_flows(struct ovn_desired_flow_table *flow_table,
                                     &flow_table->uuid_flow_table) {
         if (uuid_equals(&f->sb_uuid, sb_uuid)) {
             ovn_flow_log(f, "ofctrl_remove_flow");
+            adjust_conjunction_count(flow_table, f, false);
             hmap_remove(&flow_table->match_flow_table,
                         &f->match_hmap_node);
             hindex_remove(&flow_table->uuid_flow_table, &f->uuid_hindex_node);
@@ -747,6 +806,12 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows,
         existing->ofpacts = xmemdup(compound.data, compound.size);
         existing->ofpacts_len = compound.size;
 
+        /* It's a bit of a cheat that we only call adjust_conjunction_count in
+         * this function and not in ofctrl_add(). However, we know that
+         * conjunctions are only ever added with this function
+         */
+        adjust_conjunction_count(desired_flows, existing, true);
+
         ovn_flow_destroy(f);
     } else {
         hmap_insert(&desired_flows->match_flow_table, &f->match_hmap_node,
@@ -862,6 +927,8 @@ ovn_desired_flow_table_init(struct ovn_desired_flow_table *flow_table)
 {
     hmap_init(&flow_table->match_flow_table);
     hindex_init(&flow_table->uuid_flow_table);
+    flow_table->max_conj_width = 0;
+    flow_table->max_conj_depth = 0;
 }
 
 void
@@ -874,6 +941,8 @@ ovn_desired_flow_table_clear(struct ovn_desired_flow_table *flow_table)
         hindex_remove(&flow_table->uuid_flow_table, &f->uuid_hindex_node);
         ovn_flow_destroy(f);
     }
+    flow_table->max_conj_width = 0;
+    flow_table->max_conj_depth = 0;
 }
 
 void
diff --git a/controller/ofctrl.h b/controller/ofctrl.h
index 21d2ce648..c295c04ed 100644
--- a/controller/ofctrl.h
+++ b/controller/ofctrl.h
@@ -37,6 +37,12 @@ struct ovn_desired_flow_table {
 
     /* SB uuid index for the nodes in match_flow_table.*/
     struct hindex uuid_flow_table;
+
+    /* Highest known number of conjunction() actions in a single flow */
+    uint32_t max_conj_width;
+
+    /* Largest number of clauses for a conjunction in the table */
+    uint32_t max_conj_depth;
 };
 
 /* Interface for OVN main loop. */
diff --git a/include/ovn/expr.h b/include/ovn/expr.h
index 22f633e57..714e21add 100644
--- a/include/ovn/expr.h
+++ b/include/ovn/expr.h
@@ -425,6 +425,8 @@ bool expr_evaluate(const struct expr *, const struct flow *uflow,
                    bool (*lookup_port)(const void *aux, const char *port_name,
                                        unsigned int *portp),
                    const void *aux);
+
+void expr_set_force_crossproduct(bool should_force);
 
 /* Converting expressions to OpenFlow flows. */
 
diff --git a/lib/expr.c b/lib/expr.c
index 71de61543..4c164caed 100644
--- a/lib/expr.c
+++ b/lib/expr.c
@@ -3278,6 +3278,12 @@ expr_evaluate(const struct expr *e, const struct flow *uflow,
         OVS_NOT_REACHED();
     }
 }
+
+void
+expr_set_force_crossproduct(bool should_force)
+{
+    force_crossproduct = should_force;
+}
 
 /* Action parsing helper. */
 
-- 
2.14.5



More information about the dev mailing list