Oh, and Numan, would you mind including these results or a least a link
to them in the archives in the next version of the patch? It's OK if
they aren't completely up-to-date, the idea is to make it clear from
someone reading the commit log later that there was a big benefit.
On Fri, Feb 09, 2018 at 09:41:57AM -0800, Ben Pfaff wrote:
> 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 <[email protected]>
> >
> >
> > On 02/02/2018 09:36 AM, [email protected] wrote:
> > >From: Numan Siddique <[email protected]>
> > >
> > >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 <[email protected]>
> > >---
> > > 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
> > [email protected]
> > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
