Those are fantastic results, thanks for passing them along!

On Thu, Feb 08, 2018 at 05:11:26PM -0600, Mark Michelson wrote:
> Hi Numan,
> 
> I did a test with this where I created two address sets with ~1000 addresses
> in them. Then I created a series of ACLs that used these two address sets in
> ACLs like so:
> 
> ovn-nbctl acl-add ls0 to-lport 1000 "outport == \"lsp${COUNT}\" && ip4.src
> == \$set1 && ip4.dst == \$set2" allow
> 
> The ${COUNT} variable would increase with each loop iteration.
> 
> Without your patch, after adding 3 ACLs, it took multiple minutes to add the
> next ACL and ground my system to a halt.
> 
> With your patch, I was able to add hundreds of ACLs. While I did see
> processing slow down, it was several orders of magnitude better than without
> your patch.
> 
> It makes sense. Without your patch, each ACL results in ~1 million flows
> being generated. With your patch, each ACL results in ~2000 flows being
> generated.
> 
> Definitely an improvement! If you make a v2, I'll test it as well.
> 
> Tested-by: Mark Michelson <mmich...@redhat.com>
> 
> 
> On 02/02/2018 09:36 AM, nusid...@redhat.com wrote:
> >From: Numan Siddique <nusid...@redhat.com>
> >
> >Presently, if a logical flow has possible conjunctive matches, OVN expression
> >parser has support for that. But certain fields like ip4.src, ip4.dst are not
> >considered as dimensions in the conjunctive matches.
> >
> >In order to support all the possible fields as dimensions, this patch has 
> >added
> >a new expression type 'EXPR_T_CONJ'. After a expression is simplified by
> >expr_simplify(), before calling expr_normalize(), a new function
> >expr_eval_conj() is called, which evaluates for possible dimensions for
> >conjunctive matches.
> >
> >For example if the match expression is
> >"ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} &&
> >  ip4.dst == {20.0.0.4, 20.0.0.5, 20.0.0.6}"
> >
> >expr_simplify() would have generated the expression as -
> >
> >AND(CMP(IP4),
> >     OR((CMP(ip4.src == 10.0.0.4), CMP(ip4.src == 10.0.0.5),
> >         CMP(ip4.src == 10.0.0.6)),
> >     OR((CMP(ip4.dst == 20.0.0.4), CMP(ip4.src == 20.0.0.5),
> >         CMP(ip4.src == 20.0.0.6))).
> >
> >expr_eval_conj() would return a new expression something like
> >
> >CONJ(AND(CMP(IP4),
> >          OR((CMP(ip4.src == 10.0.0.4), CMP(ip4.src == 10.0.0.5),
> >              CMP(ip4.src == 10.0.0.6))),
> >      AND(CMP(IP4),
> >          OR((CMP(ip4.dst == 20.0.0.4), CMP(ip4.dst == 20.0.0.5),
> >              CMP(ip4.dst == 20.0.0.6))))
> >
> >expr_normalize() would normalize each individual 'AND' clause in the CONJ and
> >expr_to_matches() would add the necessary conjunctive matches.
> >
> >TODO: If the proposed approach is reasonable, then test cases and necessary
> >code comments needs to be added.
> >
> >Signed-off-by: Numan Siddique <nusid...@redhat.com>
> >---
> >  include/ovn/expr.h     |   7 ++-
> >  ovn/controller/lflow.c |   2 +
> >  ovn/lib/expr.c         | 166 
> > +++++++++++++++++++++++++++++++++++++++++++++++++
> >  tests/test-ovn.c       |   2 +-
> >  4 files changed, 175 insertions(+), 2 deletions(-)
> >
> >diff --git a/include/ovn/expr.h b/include/ovn/expr.h
> >index 711713e08..4259e5938 100644
> >--- a/include/ovn/expr.h
> >+++ b/include/ovn/expr.h
> >@@ -295,6 +295,7 @@ enum expr_type {
> >      EXPR_T_CONDITION,           /* Conditional to be evaluated in the
> >                                   * controller during expr_simplify(),
> >                                   * prior to constructing OpenFlow matches. 
> > */
> >+    EXPR_T_CONJ,
> >  };
> >  /* Expression condition type. */
> >@@ -366,12 +367,16 @@ struct expr {
> >              /* XXX Should arguments for conditions be generic? */
> >              char *string;
> >          } cond;
> >+
> >+        /* EXPR_T_CONJ. */
> >+        struct ovs_list conj;
> >      };
> >  };
> >  struct expr *expr_create_boolean(bool b);
> >  struct expr *expr_create_andor(enum expr_type);
> >  struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b);
> >+struct expr *expr_create_conj(enum expr_type);
> >  static inline struct expr *
> >  expr_from_node(const struct ovs_list *node)
> >@@ -500,5 +505,5 @@ void expr_addr_sets_add(struct shash *addr_sets, const 
> >char *name,
> >                          const char * const *values, size_t n_values);
> >  void expr_addr_sets_remove(struct shash *addr_sets, const char *name);
> >  void expr_addr_sets_destroy(struct shash *addr_sets);
> >-
> >+struct expr *expr_eval_conj(struct expr *expr);
> >  #endif /* ovn/expr.h */
> >diff --git a/ovn/controller/lflow.c b/ovn/controller/lflow.c
> >index 1e79a5355..13413c77d 100644
> >--- a/ovn/controller/lflow.c
> >+++ b/ovn/controller/lflow.c
> >@@ -289,6 +289,7 @@ consider_logical_flow(struct controller_ctx *ctx,
> >              expr = expr_combine(EXPR_T_AND, expr, prereqs);
> >              prereqs = NULL;
> >          }
> >+
> >          expr = expr_annotate(expr, &symtab, &error);
> >      }
> >      if (error) {
> >@@ -304,6 +305,7 @@ consider_logical_flow(struct controller_ctx *ctx,
> >      struct condition_aux cond_aux = { ctx->ovnsb_idl, chassis, 
> > active_tunnels,
> >                                        chassis_index};
> >      expr = expr_simplify(expr, is_chassis_resident_cb, &cond_aux);
> >+    expr = expr_eval_conj(expr);
> >      expr = expr_normalize(expr);
> >      uint32_t n_conjs = expr_to_matches(expr, lookup_port_cb, &aux,
> >                                         &matches);
> >diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> >index 79ff45762..3d4c68dd8 100644
> >--- a/ovn/lib/expr.c
> >+++ b/ovn/lib/expr.c
> >@@ -152,6 +152,14 @@ expr_create_andor(enum expr_type type)
> >      return e;
> >  }
> >+struct expr *
> >+expr_create_conj(enum expr_type type)
> >+{
> >+    struct expr *e = xmalloc(sizeof *e);
> >+    e->type = type;
> >+    ovs_list_init(&e->conj);
> >+    return e;
> >+}
> >  /* Returns a logical AND or OR expression (according to 'type', which must 
> > be
> >   * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with 
> > some
> >   * flexibility:
> >@@ -238,6 +246,7 @@ expr_not(struct expr *expr)
> >          expr->cond.not = !expr->cond.not;
> >          break;
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -298,6 +307,7 @@ expr_fix(struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          return expr;
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -442,6 +452,9 @@ expr_format(const struct expr *e, struct ds *s)
> >      case EXPR_T_CONDITION:
> >          expr_format_condition(e, s);
> >          break;
> >+
> >+    case EXPR_T_CONJ:
> >+        break;
> >      }
> >  }
> >@@ -1452,6 +1465,9 @@ expr_get_level(const struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          return EXPR_L_BOOLEAN;
> >+    case EXPR_T_CONJ:
> >+        return EXPR_T_CONJ;
> >+
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -1540,6 +1556,19 @@ expr_clone_condition(struct expr *expr)
> >      return new;
> >  }
> >+static struct expr *
> >+expr_clone_conj(struct expr *expr)
> >+{
> >+    struct expr *new = expr_create_conj(expr->type);
> >+    struct expr *sub;
> >+
> >+    LIST_FOR_EACH (sub, node, &expr->conj) {
> >+        struct expr *new_sub = expr_clone(sub);
> >+        ovs_list_push_back(&new->conj, &new_sub->node);
> >+    }
> >+    return new;
> >+}
> >+
> >  /* Returns a clone of 'expr'.  This is a "deep copy": neither the returned
> >   * expression nor any of its substructure will be shared with 'expr'. */
> >  struct expr *
> >@@ -1558,6 +1587,9 @@ expr_clone(struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          return expr_clone_condition(expr);
> >+
> >+    case EXPR_T_CONJ:
> >+        return expr_clone_conj(expr);
> >      }
> >      OVS_NOT_REACHED();
> >  }
> >@@ -1593,6 +1625,13 @@ expr_destroy(struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          free(expr->cond.string);
> >          break;
> >+
> >+    case EXPR_T_CONJ:
> >+        LIST_FOR_EACH_SAFE (sub, next, node, &expr->conj) {
> >+            ovs_list_remove(&sub->node);
> >+            expr_destroy(sub);
> >+        }
> >+        break;
> >      }
> >      free(expr);
> >  }
> >@@ -1725,6 +1764,7 @@ expr_annotate__(struct expr *expr, const struct shash 
> >*symtab,
> >          *errorp = NULL;
> >          return expr;
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -1918,6 +1958,9 @@ expr_simplify(struct expr *expr,
> >      case EXPR_T_CONDITION:
> >          return expr_simplify_condition(expr, is_chassis_resident, c_aux);
> >+
> >+    case EXPR_T_CONJ:
> >+        OVS_NOT_REACHED();
> >      }
> >      OVS_NOT_REACHED();
> >  }
> >@@ -1946,6 +1989,7 @@ expr_is_cmp(const struct expr *expr)
> >      case EXPR_T_BOOLEAN:
> >      case EXPR_T_CONDITION:
> >+    case EXPR_T_CONJ:
> >          return NULL;
> >      default:
> >@@ -2043,6 +2087,7 @@ crush_and_string(struct expr *expr, const struct 
> >expr_symbol *symbol)
> >              free(new);
> >              break;
> >          case EXPR_T_CONDITION:
> >+        case EXPR_T_CONJ:
> >              OVS_NOT_REACHED();
> >          }
> >      }
> >@@ -2139,6 +2184,7 @@ crush_and_numeric(struct expr *expr, const struct 
> >expr_symbol *symbol)
> >              expr_destroy(new);
> >              break;
> >          case EXPR_T_CONDITION:
> >+        case EXPR_T_CONJ:
> >              OVS_NOT_REACHED();
> >          }
> >      }
> >@@ -2356,6 +2402,7 @@ crush_cmps(struct expr *expr, const struct expr_symbol 
> >*symbol)
> >       * called during expr_normalize, after expr_simplify which resolves
> >       * all conditions. */
> >      case EXPR_T_CONDITION:
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -2564,6 +2611,20 @@ expr_normalize(struct expr *expr)
> >      case EXPR_T_BOOLEAN:
> >          return expr;
> >+    case EXPR_T_CONJ: {
> >+        struct expr *sub, *next;
> >+        LIST_FOR_EACH_SAFE (sub, next, node, &expr->conj) {
> >+            ovs_list_remove(&sub->node);
> >+            struct expr *new_sub = expr_normalize(sub);
> >+            if (!new_sub) {
> >+                expr_destroy(expr);
> >+                return NULL;
> >+            }
> >+            ovs_list_insert(&next->node, &new_sub->node);
> >+        }
> >+        return expr;
> >+    }
> >+
> >      /* Should not hit expression type condition, since expr_normalize is
> >       * only called after expr_simplify, which resolves all conditions. */
> >      case EXPR_T_CONDITION:
> >@@ -2737,6 +2798,7 @@ add_conjunction(const struct expr *and,
> >          case EXPR_T_AND:
> >          case EXPR_T_BOOLEAN:
> >          case EXPR_T_CONDITION:
> >+        case EXPR_T_CONJ:
> >          default:
> >              OVS_NOT_REACHED();
> >          }
> >@@ -2870,6 +2932,34 @@ expr_to_matches(const struct expr *expr,
> >          }
> >          break;
> >+    case EXPR_T_CONJ: {
> >+        struct expr *sub;
> >+        n_conjs = 1;
> >+        size_t n_clauses = ovs_list_size(&expr->conj);
> >+        uint8_t clause = 0;
> >+        LIST_FOR_EACH (sub, node, &expr->conj) {
> >+            struct hmap conj_matches;
> >+            uint32_t sub_conjs = expr_to_matches(sub, lookup_port, aux,
> >+                                                 &conj_matches);
> >+            ovs_assert(sub_conjs == 0);
> >+            struct expr_match *m;
> >+
> >+            HMAP_FOR_EACH (m, hmap_node, &conj_matches) {
> >+                expr_match_add(matches, expr_match_new(&m->match, clause,
> >+                                                       n_clauses, n_conjs));
> >+            }
> >+            clause++;
> >+            expr_matches_destroy(&conj_matches);
> >+        }
> >+
> >+        /* Add the flow that matches on conj_id. */
> >+        struct match match;
> >+        match_init_catchall(&match);
> >+        match_set_conj_id(&match, n_conjs);
> >+        expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
> >+        break;
> >+    }
> >+
> >      /* Should not hit expression type condition, since expr_to_matches is
> >       * only called after expr_simplify, which resolves all conditions. */
> >      case EXPR_T_CONDITION:
> >@@ -2954,6 +3044,7 @@ expr_honors_invariants(const struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          return true;
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -3003,6 +3094,17 @@ expr_is_normalized(const struct expr *expr)
> >      case EXPR_T_CONDITION:
> >          return false;
> >+    case EXPR_T_CONJ: {
> >+        const struct expr *sub;
> >+
> >+        LIST_FOR_EACH (sub, node, &expr->conj) {
> >+            if (!expr_is_normalized(sub)) {
> >+                return false;
> >+            }
> >+        }
> >+        return true;
> >+    }
> >+
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -3100,6 +3202,7 @@ expr_evaluate(const struct expr *e, const struct flow 
> >*uflow,
> >           * is_chassis_resident evaluates as true. */
> >          return (e->cond.not ? false : true);
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -3221,6 +3324,7 @@ expr_parse_microflow__(struct lexer *lexer,
> >      /* Should not hit expression type condition, since
> >       * expr_simplify was called above. */
> >      case EXPR_T_CONDITION:
> >+    case EXPR_T_CONJ:
> >      default:
> >          OVS_NOT_REACHED();
> >      }
> >@@ -3286,3 +3390,65 @@ expr_parse_microflow(const char *s, const struct 
> >shash *symtab,
> >      }
> >      return error;
> >  }
> >+
> >+/* Takes ownership of the simplified 'expr' returned by expr_simplify() and
> >+ * evaluates for possible conjunctive matches if it's of type AND.
> >+ * If the AND 'expr' has 2 or more OR clauses, then it returns a new expr of
> >+ * type EXPR_T_CONJ.
> >+ * Eg. If 'expr' is AND(CMP1, CMP2, CMP3, OR1, OR2, OR3), then it returns
> >+ * as CONJ(AND(CMP1, CMP2, OR1), AND(CMP1, CMP2, OR2), AND(CMP1, CMP2, OR3))
> >+ */
> >+struct expr *
> >+expr_eval_conj(struct expr *expr)
> >+{
> >+    if (expr->type != EXPR_T_AND) {
> >+        return expr;
> >+    }
> >+
> >+    /* We want to sort before checking for possible conjunctive matches.
> >+     * If the 'expr' has multiple OR clauses on the same field, expr_sort
> >+     * will combine them.
> >+     */
> >+    expr = expr_sort(expr);
> >+
> >+    if (expr->type != EXPR_T_AND) {
> >+        return expr;
> >+    }
> >+
> >+    struct expr *sub;
> >+    uint8_t n_dimensions = 0;
> >+    LIST_FOR_EACH (sub, node, &expr->andor) {
> >+        if (sub->type == EXPR_T_OR && ovs_list_size(&sub->andor) > 2) {
> >+            n_dimensions++;
> >+        }
> >+    }
> >+
> >+    if (n_dimensions < 2) {
> >+        return expr;
> >+    }
> >+
> >+    struct expr *conj_expr = expr_create_conj(EXPR_T_CONJ);
> >+    struct expr **conj_clause = xmalloc(n_dimensions * sizeof 
> >*conj_clause);;
> >+    for (uint8_t i = 0; i < n_dimensions; i++) {
> >+        conj_clause[i] = expr_create_andor(EXPR_T_AND);
> >+        ovs_list_push_back(&conj_expr->conj, &conj_clause[i]->node);
> >+    }
> >+
> >+    uint8_t j = 0;
> >+    LIST_FOR_EACH (sub, node, &expr->andor) {
> >+        if (sub->type == EXPR_T_OR && ovs_list_size(&sub->andor) > 2) {
> >+            struct expr *e = expr_clone(sub);
> >+            ovs_list_push_back(&conj_clause[j]->andor, &e->node);
> >+            j++;
> >+        } else {
> >+            for (uint8_t i = 0; i < n_dimensions; i++) {
> >+                struct expr *e = expr_clone(sub);
> >+                ovs_list_push_back(&conj_clause[i]->andor, &e->node);
> >+            }
> >+        }
> >+    }
> >+
> >+    expr_destroy(expr);
> >+    free(conj_clause);
> >+    return conj_expr;
> >+}
> >diff --git a/tests/test-ovn.c b/tests/test-ovn.c
> >index d4dfc8151..915123f54 100644
> >--- a/tests/test-ovn.c
> >+++ b/tests/test-ovn.c
> >@@ -270,6 +270,7 @@ test_parse_expr__(int steps)
> >                  expr = expr_simplify(expr, is_chassis_resident_cb, &ports);
> >              }
> >              if (steps > 2) {
> >+                expr = expr_eval_conj(expr);
> >                  expr = expr_normalize(expr);
> >                  ovs_assert(expr_is_normalized(expr));
> >              }
> >@@ -294,7 +295,6 @@ test_parse_expr__(int steps)
> >          expr_destroy(expr);
> >      }
> >      ds_destroy(&input);
> >-
> >      simap_destroy(&ports);
> >      expr_symtab_destroy(&symtab);
> >      shash_destroy(&symtab);
> >
> 
> _______________________________________________
> dev mailing list
> d...@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Reply via email to