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 <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