[ovs-dev] ovn-controller: Reduce the number of flows by use conjunction action
diff mbox series

Message ID c6a79ed9-3cab-45ee-9e2c-a4865368ee9e@DESKTOP-LBPO59B.local
State Changes Requested
Delegated to: Ben Pfaff
Headers show
Series
  • [ovs-dev] ovn-controller: Reduce the number of flows by use conjunction action
Related show

Commit Message

Wei Li Oct. 18, 2017, 2:50 a.m. UTC
This patch convert ovn-sb lflow match expr "(1 or 2) and (3 or 4)" to
match 1 aciton connjunction(1, 1/2)
match 2 aciton connjunction(1, 1/2)
match 3 aciton connjunction(1, 2/2)
match 4 aciton connjunction(1, 2/2)
match conj_id=1, action=XXX

NOT support nested conjunction, only use conjunction action in situation "or in level 0"
Like (1 or 2) and (3 or ((4 or 5) and (6 or 7))), (4 or 5) and (6 or 7) will not be converted conjunction action,
We could call this situation as "or in level 1", in this situation (4 or 5) and (6 or 7) will be crossproduct,
so (1 or 2) and (3 or ((4 or 5) and (6 or 7))) -> (1 or 2) and (3 or (4 and 6) or (4 and 7) or (5 and 6) or (5 and 7))

In openstack, security group rule will match remote security group and tcp port, like
match=(ip4.src == $as_ip4_6a8f4283_ba60_4d1c_9dec_28d027eadef2 && tcp.dst >= 10000 && tcp.dst <= 20000))

Use this patch, the number of flows will be significantly reduced

Signed-off-by: wei <liw@dtdream.com>
---
 ovn/lib/expr.c | 95 ++++++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 66 insertions(+), 29 deletions(-)

Patch
diff mbox series

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 79ff45762..a7e72cef7 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -2426,12 +2426,12 @@  expr_sort(struct expr *expr)
     return expr;
 }
 
-static struct expr *expr_normalize_or(struct expr *expr);
+static struct expr *expr_normalize_or(struct expr *expr, int level);
 
 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
  * a clause is a cmp or a disjunction of cmps on a single field. */
 static struct expr *
-expr_normalize_and(struct expr *expr)
+expr_normalize_and(struct expr *expr, int level)
 {
     ovs_assert(expr->type == EXPR_T_AND);
 
@@ -2472,40 +2472,55 @@  expr_normalize_and(struct expr *expr)
         }
 
         ovs_assert(sub->type == EXPR_T_OR);
-        const struct expr_symbol *symbol = expr_is_cmp(sub);
-        if (!symbol || symbol->must_crossproduct) {
-            struct expr *or = expr_create_andor(EXPR_T_OR);
-            struct expr *k;
-
-            LIST_FOR_EACH (k, node, &sub->andor) {
-                struct expr *and = expr_create_andor(EXPR_T_AND);
-                struct expr *m;
-
-                LIST_FOR_EACH (m, node, &expr->andor) {
-                    struct expr *term = m == sub ? k : m;
-                    if (term->type == EXPR_T_AND) {
-                        struct expr *p;
-
-                        LIST_FOR_EACH (p, node, &term->andor) {
-                            struct expr *new = expr_clone(p);
+        if (level == 0) {
+            LIST_FOR_EACH_SAFE (a, b, node, &sub->andor) {
+                if (a->type == EXPR_T_CMP) {
+                    continue;
+                } else if (a->type == EXPR_T_AND) {
+                    ovs_list_remove(&a->node);
+                    struct expr *new = expr_normalize_and(a, level + 1);
+                    ovs_assert(new->type == EXPR_T_CMP || new->type == EXPR_T_AND || new->type == EXPR_T_OR);
+                    expr_insert_andor(sub, b, new);
+                } else {
+                    OVS_NOT_REACHED();
+                }
+            }
+        } else {
+            const struct expr_symbol *symbol = expr_is_cmp(sub);
+            if (!symbol || symbol->must_crossproduct) {
+                struct expr *or = expr_create_andor(EXPR_T_OR);
+                struct expr *k;
+
+                LIST_FOR_EACH (k, node, &sub->andor) {
+                    struct expr *and = expr_create_andor(EXPR_T_AND);
+                    struct expr *m;
+
+                    LIST_FOR_EACH (m, node, &expr->andor) {
+                        struct expr *term = m == sub ? k : m;
+                        if (term->type == EXPR_T_AND) {
+                            struct expr *p;
+
+                            LIST_FOR_EACH (p, node, &term->andor) {
+                                struct expr *new = expr_clone(p);
+                                ovs_list_push_back(&and->andor, &new->node);
+                            }
+                        } else {
+                            struct expr *new = expr_clone(term);
                             ovs_list_push_back(&and->andor, &new->node);
                         }
-                    } else {
-                        struct expr *new = expr_clone(term);
-                        ovs_list_push_back(&and->andor, &new->node);
                     }
+                    ovs_list_push_back(&or->andor, &and->node);
                 }
-                ovs_list_push_back(&or->andor, &and->node);
+                expr_destroy(expr);
+                return expr_normalize_or(or, level + 1);
             }
-            expr_destroy(expr);
-            return expr_normalize_or(or);
         }
     }
     return expr;
 }
 
 static struct expr *
-expr_normalize_or(struct expr *expr)
+expr_normalize_or(struct expr *expr, int level)
 {
     struct expr *sub, *next;
 
@@ -2513,7 +2528,7 @@  expr_normalize_or(struct expr *expr)
         if (sub->type == EXPR_T_AND) {
             ovs_list_remove(&sub->node);
 
-            struct expr *new = expr_normalize_and(sub);
+            struct expr *new = expr_normalize_and(sub, level);
             if (new->type == EXPR_T_BOOLEAN) {
                 if (new->boolean) {
                     expr_destroy(expr);
@@ -2556,10 +2571,10 @@  expr_normalize(struct expr *expr)
         return expr;
 
     case EXPR_T_AND:
-        return expr_normalize_and(expr);
+        return expr_normalize_and(expr, 0);
 
     case EXPR_T_OR:
-        return expr_normalize_or(expr);
+        return expr_normalize_or(expr, 0);
 
     case EXPR_T_BOOLEAN:
         return expr;
@@ -2695,9 +2710,31 @@  add_disjunction(const struct expr *or,
 
     ovs_assert(or->type == EXPR_T_OR);
     LIST_FOR_EACH (sub, node, &or->andor) {
+        bool match_correct = true;
         struct expr_match *match = expr_match_new(m, clause, n_clauses,
                                                   conj_id);
-        if (constrain_match(sub, lookup_port, aux, &match->match)) {
+        if (sub->type == EXPR_T_CMP) {
+            if (!constrain_match(sub, lookup_port, aux, &match->match)) {
+                match_correct = false;
+            }
+        } else if (sub->type == EXPR_T_AND) {
+            struct expr *subsub;
+
+            LIST_FOR_EACH (subsub, node, &sub->andor) {
+                if (subsub->type == EXPR_T_CMP) {
+                    if (!constrain_match(subsub, lookup_port, aux, &match->match)) {
+                        match_correct = false;
+                        break;
+                    }
+                } else {
+                    OVS_NOT_REACHED();
+                }
+            }
+        } else {
+            OVS_NOT_REACHED();
+        }
+
+        if (match_correct) {
             expr_match_add(matches, match);
             n++;
         } else {