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
