| Message ID | 20180202153639.11368-1-nusiddiq@redhat.com |
|---|---|
| State | RFC |
| Headers | show |
| Series | Enhance conjunctive match support in OVN | expand |
On Fri, Feb 02, 2018 at 09:06:39PM +0530, nusiddiq@redhat.com wrote: > From: Numan Siddique <nusiddiq@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. I think I like this approach, but I also think that it's worthwhile trying to figure out whether it's possible to do it without adding the extra EXPR_T_CONJ type and the extra processing step. I started playing with that idea yesterday. I think it's possible, but I didn't actually finish implementing it. I did come up with a few independent patches to improve the expr code, though. Would you take a look? They are at: https://patchwork.ozlabs.org/project/openvswitch/list/?series=27221 This patch causes one warning from Clang (and I think it's right that this code is fishy): ../ovn/lib/expr.c:1470:16: error: implicit conversion from enumeration type 'enum expr_type' to different enumeration type 'enum expr_level' [-Werror,-Wenum-conversion] Thanks, Ben.
On Tue, Feb 6, 2018 at 11:31 PM, Ben Pfaff <blp@ovn.org> wrote: > On Fri, Feb 02, 2018 at 09:06:39PM +0530, nusiddiq@redhat.com wrote: > > From: Numan Siddique <nusiddiq@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. > > I think I like this approach, but I also think that it's worthwhile > trying to figure out whether it's possible to do it without adding the > extra EXPR_T_CONJ type and the extra processing step. I started playing > with that idea yesterday. I think it's possible, but I didn't actually > finish implementing it. > > That's great. Looking forward for those patches whenever they are ready :). > I did come up with a few independent patches to improve the expr code, > though. Would you take a look? They are at: > https://patchwork.ozlabs.org/project/openvswitch/list/? > series=27221 Thanks Ben. I will try out these patches tomorrow. Thanks Numan > > This patch causes one warning from Clang (and I think it's right that > this code is fishy): > > ../ovn/lib/expr.c:1470:16: error: implicit conversion from enumeration > type 'enum expr_type' to different enumeration type 'enum expr_level' > [-Werror,-Wenum-conversion] > > Thanks, > > Ben. >
On Wed, Feb 07, 2018 at 12:12:38AM +0530, Numan Siddique wrote: > On Tue, Feb 6, 2018 at 11:31 PM, Ben Pfaff <blp@ovn.org> wrote: > > > On Fri, Feb 02, 2018 at 09:06:39PM +0530, nusiddiq@redhat.com wrote: > > > From: Numan Siddique <nusiddiq@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. > > > > I think I like this approach, but I also think that it's worthwhile > > trying to figure out whether it's possible to do it without adding the > > extra EXPR_T_CONJ type and the extra processing step. I started playing > > with that idea yesterday. I think it's possible, but I didn't actually > > finish implementing it. > > > > > That's great. Looking forward for those patches whenever they are ready :). Oh, I didn't want to take over the series from you, I'm suggesting a possible direction. Is that a direction you could try to go?
On Feb 7, 2018 1:06 AM, "Ben Pfaff" <blp@ovn.org> wrote: On Wed, Feb 07, 2018 at 12:12:38AM +0530, Numan Siddique wrote: > On Tue, Feb 6, 2018 at 11:31 PM, Ben Pfaff <blp@ovn.org> wrote: > > > On Fri, Feb 02, 2018 at 09:06:39PM +0530, nusiddiq@redhat.com wrote: > > > From: Numan Siddique <nusiddiq@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. > > > > I think I like this approach, but I also think that it's worthwhile > > trying to figure out whether it's possible to do it without adding the > > extra EXPR_T_CONJ type and the extra processing step. I started playing > > with that idea yesterday. I think it's possible, but I didn't actually > > finish implementing it. > > > > > That's great. Looking forward for those patches whenever they are ready :). Oh, I didn't want to take over the series from you, I'm suggesting a possible direction. Is that a direction you could try to go? Ok. Got it. I will try to explore in that direction. Thanks Numan
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 <mmichels@redhat.com>
On 02/02/2018 09:36 AM, nusiddiq@redhat.com wrote:
> From: Numan Siddique <nusiddiq@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 <nusiddiq@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);
>
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 <mmichels@redhat.com> > > > On 02/02/2018 09:36 AM, nusiddiq@redhat.com wrote: > >From: Numan Siddique <nusiddiq@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 <nusiddiq@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 > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
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 <mmichels@redhat.com> > > > > > > On 02/02/2018 09:36 AM, nusiddiq@redhat.com wrote: > > >From: Numan Siddique <nusiddiq@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 <nusiddiq@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 > > dev@openvswitch.org > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
On Feb 9, 2018 11:19 PM, "Ben Pfaff" <blp@ovn.org> wrote: 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. Yeah. Sure. I will do that. Thanks Mark for testing it out and sharing the results. Thanks Numan 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 <mmichels@redhat.com> > > > > > > On 02/02/2018 09:36 AM, nusiddiq@redhat.com wrote: > > >From: Numan Siddique <nusiddiq@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 <nusiddiq@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 > > dev@openvswitch.org > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
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);