Message ID | 20180216135440.26304-1-nusiddiq@redhat.com |
---|---|
State | Not Applicable |
Headers | show |
Series | [ovs-dev,v1] Enhance conjunctive match support in OVN | expand |
"bump" :) I'm doing a review of the patch. Did we want to look into alternatives or is this one fine? I believe this is an important improvement for the openstack usage case (security groups). Best regards, Miguel Ángel. On Fri, Feb 16, 2018 at 2:55 PM <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. > > Mark Michelson tested the RFC version of this patch [1] and found > significant > improvement in ACL processing and reduced the OF flows from an order of 1 > million > to few thousounds. [2] > > It is possible to support this feature without adding new expression type > 'EXPR_T_CONJ' and a new processing step, which can be considered for > future work. > > [1] - > https://mail.openvswitch.org/pipermail/ovs-dev/2018-February/344092.html > [2] - > https://mail.openvswitch.org/pipermail/ovs-dev/2018-February/344311.html > > Signed-off-by: Numan Siddique <nusiddiq@redhat.com> > --- > include/ovn/expr.h | 10 ++- > ovn/controller/lflow.c | 1 + > ovn/lib/expr.c | 175 ++++++++++++++++++++++++++++++++++++++++++++ > tests/ovn.at | 195 > +++++++++++++++++++++++++++++++++++++++++++++++++ > tests/test-ovn.c | 2 +- > 5 files changed, 380 insertions(+), 3 deletions(-) > > diff --git a/include/ovn/expr.h b/include/ovn/expr.h > index 711713e08..52aa74ed4 100644 > --- a/include/ovn/expr.h > +++ b/include/ovn/expr.h > @@ -295,6 +295,8 @@ enum expr_type { > EXPR_T_CONDITION, /* Conditional to be evaluated in the > * controller during expr_simplify(), > * prior to constructing OpenFlow > matches. */ > + EXPR_T_CONJ, /* Conjunction of 2 or more Logical AND > + * subexpressions. */ > }; > > /* Expression condition type. */ > @@ -333,7 +335,8 @@ bool expr_relop_from_token(enum lex_type type, enum > expr_relop *relop); > * > * The expr_honors_invariants() function can check invariants. */ > struct expr { > - struct ovs_list node; /* In parent EXPR_T_AND or EXPR_T_OR if > any. */ > + struct ovs_list node; /* In parent EXPR_T_AND, EXPR_T_OR or > + * EXPR_T_CONJ if any. */ > enum expr_type type; /* Expression type. */ > > union { > @@ -366,6 +369,9 @@ struct expr { > /* XXX Should arguments for conditions be generic? */ > char *string; > } cond; > + > + /* EXPR_T_CONJ. */ > + struct ovs_list conj; > }; > }; > > @@ -397,6 +403,7 @@ struct expr *expr_simplify(struct expr *, > const char > *port_name), > const void *c_aux); > struct expr *expr_normalize(struct expr *); > +struct expr *expr_eval_conj(struct expr *); > > bool expr_honors_invariants(const struct expr *); > bool expr_is_simplified(const struct expr *); > @@ -500,5 +507,4 @@ 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); > - > #endif /* ovn/expr.h */ > diff --git a/ovn/controller/lflow.c b/ovn/controller/lflow.c > index df125b188..88340df13 100644 > --- a/ovn/controller/lflow.c > +++ b/ovn/controller/lflow.c > @@ -284,6 +284,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 b0aa6726b..b0441f9a3 100644 > --- a/ovn/lib/expr.c > +++ b/ovn/lib/expr.c > @@ -152,6 +152,14 @@ expr_create_andor(enum expr_type type) > return e; > } > > +static 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,7 @@ expr_get_level(const struct expr *expr) > case EXPR_T_CONDITION: > return EXPR_L_BOOLEAN; > > + case EXPR_T_CONJ: > default: > OVS_NOT_REACHED(); > } > @@ -1540,6 +1554,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 +1585,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 +1623,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 +1762,7 @@ expr_annotate__(struct expr *expr, const struct > shash *symtab, > *errorp = NULL; > return expr; > > + case EXPR_T_CONJ: > default: > OVS_NOT_REACHED(); > } > @@ -1918,6 +1956,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(); > } > @@ -1951,6 +1992,7 @@ expr_get_unique_symbol(const struct expr *expr) > > case EXPR_T_BOOLEAN: > case EXPR_T_CONDITION: > + case EXPR_T_CONJ: > return NULL; > > default: > @@ -2048,6 +2090,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(); > } > } > @@ -2144,6 +2187,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(); > } > } > @@ -2361,6 +2405,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(); > } > @@ -2579,6 +2624,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: > @@ -2752,6 +2811,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(); > } > @@ -2885,6 +2945,40 @@ 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); > + if (sub_conjs) { > + /* We don't support sub conjunctive flows. */ > + expr_matches_destroy(&conj_matches); > + expr_matches_destroy(matches); > + return 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: > @@ -2969,6 +3063,7 @@ expr_honors_invariants(const struct expr *expr) > case EXPR_T_CONDITION: > return true; > > + case EXPR_T_CONJ: > default: > OVS_NOT_REACHED(); > } > @@ -3019,6 +3114,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(); > } > @@ -3116,6 +3222,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(); > } > @@ -3237,6 +3344,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(); > } > @@ -3302,3 +3410,70 @@ 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) { > + /* Consider for dimension only if the number of children is > 2. > + * One example is if the logical flow has "ip && ...", then a > + * sub will be OR(CMP(ip4), CMP(ip6)) and we will add it as a > + * dimension which may be incorrect. > + */ > + 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/ovn.at b/tests/ovn.at > index 8ee3bf0b5..d37e23481 100644 > --- a/tests/ovn.at > +++ b/tests/ovn.at > @@ -657,6 +657,74 @@ ip,nw_src=8.0.0.0/8.0.0.0 > ]) > AT_CLEANUP > > +AT_SETUP([ovn -- converting expressions to flows -- conjunction]) > +AT_KEYWORDS([conjunction]) > +expr_to_flow () { > + echo "$1" | ovstest test-ovn expr-to-flows | sort > +} > + > +lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > +ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3}" > +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +conj_id=1 > +ip,nw_dst=20.0.0.1: conjunction(1, 1/2) > +ip,nw_dst=20.0.0.2: conjunction(1, 1/2) > +ip,nw_dst=20.0.0.3: conjunction(1, 1/2) > +ip,nw_src=10.0.0.1: conjunction(1, 0/2) > +ip,nw_src=10.0.0.2: conjunction(1, 0/2) > +ip,nw_src=10.0.0.3: conjunction(1, 0/2) > +]) > + > +lflow="ip && (!ct.est || (ct.est && ct_label.blocked == 1))" > +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +ct_state=+est+trk,ct_label=0x1/0x1,ip > +ct_state=+est+trk,ct_label=0x1/0x1,ipv6 > +ct_state=-est+trk,ip > +ct_state=-est+trk,ipv6 > +]) > + > +# ip4.dst has only 2 items. So it shouldn't be considered as a > +# dimension. > +lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > +ip4.dst == {20.0.0.1, 20.0.0.2}" > +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +ip,nw_src=10.0.0.1,nw_dst=20.0.0.1 > +ip,nw_src=10.0.0.1,nw_dst=20.0.0.2 > +ip,nw_src=10.0.0.2,nw_dst=20.0.0.1 > +ip,nw_src=10.0.0.2,nw_dst=20.0.0.2 > +ip,nw_src=10.0.0.3,nw_dst=20.0.0.1 > +ip,nw_src=10.0.0.3,nw_dst=20.0.0.2 > +]) > + > +lflow="ip4 && ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > +ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3} && \ > +tcp.dst >= 1000 && tcp.dst <= 1010" > + > +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +conj_id=1 > +tcp,nw_dst=20.0.0.1: conjunction(1, 2/3) > +tcp,nw_dst=20.0.0.2: conjunction(1, 2/3) > +tcp,nw_dst=20.0.0.3: conjunction(1, 2/3) > +tcp,nw_src=10.0.0.1: conjunction(1, 1/3) > +tcp,nw_src=10.0.0.2: conjunction(1, 1/3) > +tcp,nw_src=10.0.0.3: conjunction(1, 1/3) > +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 0/3) > +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 0/3) > +tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 0/3) > +tcp,tp_dst=1000: conjunction(1, 0/3) > +tcp,tp_dst=1001: conjunction(1, 0/3) > +tcp,tp_dst=1010: conjunction(1, 0/3) > +]) > + > +lflow="ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} && \ > +((ip4.dst == {20.0.0.4, 20.0.0.7, 20.0.0.8} && tcp.dst >= 1000 && \ > +tcp.dst <= 2000 && tcp.src >=1000 && tcp.src <= 2000) \ > +|| ip4.dst == 20.0.0.5 || ip4.dst == 20.0.0.6)" > + > +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +]) > +AT_CLEANUP > + > AT_SETUP([ovn -- action parsing]) > dnl Unindented text is input (a set of OVN logical actions). > dnl Indented text is expected output. > @@ -9329,3 +9397,130 @@ ra_test 000005dc 40 80 40 > aef00000000000000000000000000000 30 fd0f00000000000000 > > OVN_CLEANUP([hv1],[hv2]) > AT_CLEANUP > + > +AT_SETUP([ovn -- ACL conjunction]) > +ovn_start > + > +ovn-nbctl ls-add ls1 > + > +ovn-nbctl lsp-add ls1 ls1-lp1 \ > +-- lsp-set-addresses ls1-lp1 "f0:00:00:00:00:01 10.0.0.4" > + > +ovn-nbctl lsp-set-port-security ls1-lp1 "f0:00:00:00:00:01 10.0.0.4" > + > +ovn-nbctl lsp-add ls1 ls1-lp2 \ > +-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02 10.0.0.6" > + > +ovn-nbctl lsp-set-port-security ls1-lp2 "f0:00:00:00:00:02 10.0.0.6" > + > +net_add n1 > +sim_add hv1 > + > +as hv1 > +ovs-vsctl add-br br-phys > +ovn_attach n1 br-phys 192.168.0.1 > +ovs-vsctl -- add-port br-int hv1-vif1 -- \ > + set interface hv1-vif1 external-ids:iface-id=ls1-lp1 \ > + options:tx_pcap=hv1/vif1-tx.pcap \ > + options:rxq_pcap=hv1/vif1-rx.pcap \ > + ofport-request=1 > + > +ovs-vsctl -- add-port br-int hv1-vif2 -- \ > + set interface hv1-vif2 external-ids:iface-id=ls1-lp2 \ > + options:tx_pcap=hv1/vif2-tx.pcap \ > + options:rxq_pcap=hv1/vif2-rx.pcap \ > + ofport-request=2 > + > +ovn-nbctl create Address_Set name=set1 \ > +addresses=\"10.0.0.4\",\"10.0.0.5\",\"10.0.0.6\" > +ovn-nbctl create Address_Set name=set2 \ > +addresses=\"10.0.0.7\",\"10.0.0.8\",\"10.0.0.9\" > +ovn-nbctl acl-add ls1 to-lport 1002 \ > +'ip4 && ip4.src == $set1 && ip4.dst == $set1' allow > +ovn-nbctl acl-add ls1 to-lport 1001 \ > +'ip4 && ip4.src == $set1 && ip4.dst == $set2' drop > + > +# test_ip INPORT SRC_MAC DST_MAC SRC_IP DST_IP OUTPORT... > +# > +# This shell function causes an ip packet to be received on INPORT. > +# The packet's content has Ethernet destination DST and source SRC > +# (each exactly 12 hex digits) and Ethernet type ETHTYPE (4 hex digits). > +# The OUTPORTs (zero or more) list the VIFs on which the packet should > +# be received. INPORT and the OUTPORTs are specified as logical switch > +# port numbers, e.g. 11 for vif11. > +test_ip() { > + # This packet has bad checksums but logical L3 routing doesn't check. > + local inport=$1 src_mac=$2 dst_mac=$3 src_ip=$4 dst_ip=$5 > + local > packet=${dst_mac}${src_mac}08004500001c0000000040110000${src_ip}\ > +${dst_ip}0035111100080000 > + shift; shift; shift; shift; shift > + as hv1 ovs-appctl netdev-dummy/receive hv1-vif1 $packet > + for outport; do > + echo $packet >> $outport.expected > + done > +} > + > +ip_to_hex() { > + printf "%02x%02x%02x%02x" "$@" > +} > + > +reset_pcap_file() { > + local iface=$1 > + local pcap_file=$2 > + ovs-vsctl -- set Interface $iface options:tx_pcap=dummy-tx.pcap \ > +options:rxq_pcap=dummy-rx.pcap > + rm -f ${pcap_file}*.pcap > + ovs-vsctl -- set Interface $iface > options:tx_pcap=${pcap_file}-tx.pcap \ > +options:rxq_pcap=${pcap_file}-rx.pcap > +} > + > + > +sip=`ip_to_hex 10 0 0 4` > +dip=`ip_to_hex 10 0 0 6` > + > +test_ip 1 f00000000001 f00000000002 $sip $dip 2 > + > +cat 2.expected > expout > +$PYTHON "$top_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets > +AT_CHECK([cat 2.packets], [0], [expout]) > + > +# There should be total of 12 flows present with conjunction action and 2 > flows > +# with conj match. Eg. > +# table=44, priority=2002,conj_id=2,metadata=0x1 actions=resubmit(,45) > +# table=44, priority=2001,conj_id=3,metadata=0x1 actions=drop > +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.6 actions=conjunction(2,2/2) > +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,2/2) > +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.5 actions=conjunction(2,2/2) > +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.7 actions=conjunction(3,2/2) > +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.9 actions=conjunction(3,2/2) > +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.8 actions=conjunction(3,2/2) > +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.6 actions=conjunction(2,1/2) > +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.4 actions=conjunction(2,1/2) > +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.5 actions=conjunction(2,1/2) > +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.6 actions=conjunction(3,1/2) > +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.4 actions=conjunction(3,1/2) > +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.5 actions=conjunction(3,1/2) > + > +OVS_WAIT_UNTIL([test 12 = `as hv1 ovs-ofctl dump-flows br-int | \ > +grep conjunction | wc -l`]) > +OVS_WAIT_UNTIL([test 2 = `as hv1 ovs-ofctl dump-flows br-int | \ > +grep conj_id | wc -l`]) > + > +as hv1 ovs-ofctl dump-flows br-int > + > +# Set the ip address for ls1-lp2 from set2 so that the drop ACL flow is > hit. > +ovn-nbctl lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02 10.0.0.7 20.0.0.4" > +ovn-nbctl lsp-set-port-security ls1-lp2 "f0:00:00:00:00:02 10.0.0.7 > 20.0.0.4" > + > +reset_pcap_file hv1-vif2 hv1/vif2 > + > +rm -f 2.packets > + > +sip=`ip_to_hex 10 0 0 4` > +dip=`ip_to_hex 10 0 0 7` > + > +test_ip 1 f00000000001 f00000000002 $sip $dip > +$PYTHON "$top_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets > +AT_CHECK([cat 2.packets], [0], []) > + > +AT_CLEANUP > diff --git a/tests/test-ovn.c b/tests/test-ovn.c > index 745275318..c7d54a865 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); > -- > 2.14.3 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev >
Hi Numan, I've started reviewing your patch and it occurred to me that we can complicate the annotation a bit (but not much) and achieve the same effect. Please take a look at the proposed change [1]. It seems to be passing your tests, with the changes as below: 1) I believe sets with just two items should also be considered a dimension, unless I'm reading ovs-fields man-page wrong. 2) It turns out we can apply conjunctive matching to the last "crazy" expression from your test as well. Quite surprising what the expression-to-matches converter spits out. Looking forward to hearing what you think about it. Thanks, Jakub [1] https://patchwork.ozlabs.org/patch/905334/ ---8<--- --- tests/ovn.at | 83 ++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 58 insertions(+), 25 deletions(-) diff --git a/tests/ovn.at b/tests/ovn.at index 5f2c04c39..8fe4c522a 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -685,13 +685,13 @@ expr_to_flow () { lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3}" AT_CHECK([expr_to_flow "$lflow"], [0], [dnl -conj_id=1 -ip,nw_dst=20.0.0.1: conjunction(1, 1/2) -ip,nw_dst=20.0.0.2: conjunction(1, 1/2) -ip,nw_dst=20.0.0.3: conjunction(1, 1/2) -ip,nw_src=10.0.0.1: conjunction(1, 0/2) -ip,nw_src=10.0.0.2: conjunction(1, 0/2) -ip,nw_src=10.0.0.3: conjunction(1, 0/2) +conj_id=1,ip +ip,nw_dst=20.0.0.1: conjunction(1, 0/2) +ip,nw_dst=20.0.0.2: conjunction(1, 0/2) +ip,nw_dst=20.0.0.3: conjunction(1, 0/2) +ip,nw_src=10.0.0.1: conjunction(1, 1/2) +ip,nw_src=10.0.0.2: conjunction(1, 1/2) +ip,nw_src=10.0.0.3: conjunction(1, 1/2) ]) lflow="ip && (!ct.est || (ct.est && ct_label.blocked == 1))" @@ -702,17 +702,15 @@ ct_state=-est+trk,ip ct_state=-est+trk,ipv6 ]) -# ip4.dst has only 2 items. So it shouldn't be considered as a -# dimension. lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ ip4.dst == {20.0.0.1, 20.0.0.2}" AT_CHECK([expr_to_flow "$lflow"], [0], [dnl -ip,nw_src=10.0.0.1,nw_dst=20.0.0.1 -ip,nw_src=10.0.0.1,nw_dst=20.0.0.2 -ip,nw_src=10.0.0.2,nw_dst=20.0.0.1 -ip,nw_src=10.0.0.2,nw_dst=20.0.0.2 -ip,nw_src=10.0.0.3,nw_dst=20.0.0.1 -ip,nw_src=10.0.0.3,nw_dst=20.0.0.2 +conj_id=1,ip +ip,nw_dst=20.0.0.1: conjunction(1, 0/2) +ip,nw_dst=20.0.0.2: conjunction(1, 0/2) +ip,nw_src=10.0.0.1: conjunction(1, 1/2) +ip,nw_src=10.0.0.2: conjunction(1, 1/2) +ip,nw_src=10.0.0.3: conjunction(1, 1/2) ]) lflow="ip4 && ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ @@ -720,19 +718,19 @@ ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3} && \ tcp.dst >= 1000 && tcp.dst <= 1010" AT_CHECK([expr_to_flow "$lflow"], [0], [dnl -conj_id=1 -tcp,nw_dst=20.0.0.1: conjunction(1, 2/3) -tcp,nw_dst=20.0.0.2: conjunction(1, 2/3) -tcp,nw_dst=20.0.0.3: conjunction(1, 2/3) +conj_id=1,tcp +tcp,nw_dst=20.0.0.1: conjunction(1, 0/3) +tcp,nw_dst=20.0.0.2: conjunction(1, 0/3) +tcp,nw_dst=20.0.0.3: conjunction(1, 0/3) tcp,nw_src=10.0.0.1: conjunction(1, 1/3) tcp,nw_src=10.0.0.2: conjunction(1, 1/3) tcp,nw_src=10.0.0.3: conjunction(1, 1/3) -tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 0/3) -tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 0/3) -tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 0/3) -tcp,tp_dst=1000: conjunction(1, 0/3) -tcp,tp_dst=1001: conjunction(1, 0/3) -tcp,tp_dst=1010: conjunction(1, 0/3) +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 2/3) +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 2/3) +tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 2/3) +tcp,tp_dst=1000: conjunction(1, 2/3) +tcp,tp_dst=1001: conjunction(1, 2/3) +tcp,tp_dst=1010: conjunction(1, 2/3) ]) lflow="ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} && \ @@ -741,6 +739,41 @@ tcp.dst <= 2000 && tcp.src >=1000 && tcp.src <= 2000) \ || ip4.dst == 20.0.0.5 || ip4.dst == 20.0.0.6)" AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +conj_id=1,tcp +ip,nw_src=10.0.0.4,nw_dst=20.0.0.5 +ip,nw_src=10.0.0.4,nw_dst=20.0.0.6 +ip,nw_src=10.0.0.5,nw_dst=20.0.0.5 +ip,nw_src=10.0.0.5,nw_dst=20.0.0.6 +ip,nw_src=10.0.0.6,nw_dst=20.0.0.5 +ip,nw_src=10.0.0.6,nw_dst=20.0.0.6 +tcp,nw_dst=20.0.0.4: conjunction(1, 0/4) +tcp,nw_dst=20.0.0.7: conjunction(1, 0/4) +tcp,nw_dst=20.0.0.8: conjunction(1, 0/4) +tcp,nw_src=10.0.0.4: conjunction(1, 1/4) +tcp,nw_src=10.0.0.5: conjunction(1, 1/4) +tcp,nw_src=10.0.0.6: conjunction(1, 1/4) +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 2/4) +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 2/4) +tcp,tp_dst=0x3f0/0xfff0: conjunction(1, 2/4) +tcp,tp_dst=0x400/0xfe00: conjunction(1, 2/4) +tcp,tp_dst=0x600/0xff00: conjunction(1, 2/4) +tcp,tp_dst=0x700/0xff80: conjunction(1, 2/4) +tcp,tp_dst=0x780/0xffc0: conjunction(1, 2/4) +tcp,tp_dst=0x7c0/0xfff0: conjunction(1, 2/4) +tcp,tp_dst=1000: conjunction(1, 2/4) +tcp,tp_dst=1001: conjunction(1, 2/4) +tcp,tp_dst=2000: conjunction(1, 2/4) +tcp,tp_src=0x3ea/0xfffe: conjunction(1, 3/4) +tcp,tp_src=0x3ec/0xfffc: conjunction(1, 3/4) +tcp,tp_src=0x3f0/0xfff0: conjunction(1, 3/4) +tcp,tp_src=0x400/0xfe00: conjunction(1, 3/4) +tcp,tp_src=0x600/0xff00: conjunction(1, 3/4) +tcp,tp_src=0x700/0xff80: conjunction(1, 3/4) +tcp,tp_src=0x780/0xffc0: conjunction(1, 3/4) +tcp,tp_src=0x7c0/0xfff0: conjunction(1, 3/4) +tcp,tp_src=1000: conjunction(1, 3/4) +tcp,tp_src=1001: conjunction(1, 3/4) +tcp,tp_src=2000: conjunction(1, 3/4) ]) AT_CLEANUP -- 2.14.3
On Fri, Apr 27, 2018 at 1:41 AM, Jakub Sitnicki <jkbs@redhat.com> wrote: > Hi Numan, > > I've started reviewing your patch and it occurred to me that we can > complicate > the annotation a bit (but not much) and achieve the same effect. Please > take a > look at the proposed change [1]. > > It seems to be passing your tests, with the changes as below: > > 1) I believe sets with just two items should also be considered a > dimension, > unless I'm reading ovs-fields man-page wrong. > > 2) It turns out we can apply conjunctive matching to the last "crazy" > expression > from your test as well. Quite surprising what the expression-to-matches > converter spits out. > > Looking forward to hearing what you think about it. > That's great Jacub. I will try it out and let you know. Thanks Numan > > Thanks, > Jakub > > [1] https://patchwork.ozlabs.org/patch/905334/ > > ---8<--- > > --- > tests/ovn.at | 83 ++++++++++++++++++++++++++++++ > ++++++++++++------------------ > 1 file changed, 58 insertions(+), 25 deletions(-) > > diff --git a/tests/ovn.at b/tests/ovn.at > index 5f2c04c39..8fe4c522a 100644 > --- a/tests/ovn.at > +++ b/tests/ovn.at > @@ -685,13 +685,13 @@ expr_to_flow () { > lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3}" > AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > -conj_id=1 > -ip,nw_dst=20.0.0.1: conjunction(1, 1/2) > -ip,nw_dst=20.0.0.2: conjunction(1, 1/2) > -ip,nw_dst=20.0.0.3: conjunction(1, 1/2) > -ip,nw_src=10.0.0.1: conjunction(1, 0/2) > -ip,nw_src=10.0.0.2: conjunction(1, 0/2) > -ip,nw_src=10.0.0.3: conjunction(1, 0/2) > +conj_id=1,ip > +ip,nw_dst=20.0.0.1: conjunction(1, 0/2) > +ip,nw_dst=20.0.0.2: conjunction(1, 0/2) > +ip,nw_dst=20.0.0.3: conjunction(1, 0/2) > +ip,nw_src=10.0.0.1: conjunction(1, 1/2) > +ip,nw_src=10.0.0.2: conjunction(1, 1/2) > +ip,nw_src=10.0.0.3: conjunction(1, 1/2) > ]) > > lflow="ip && (!ct.est || (ct.est && ct_label.blocked == 1))" > @@ -702,17 +702,15 @@ ct_state=-est+trk,ip > ct_state=-est+trk,ipv6 > ]) > > -# ip4.dst has only 2 items. So it shouldn't be considered as a > -# dimension. > lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > ip4.dst == {20.0.0.1, 20.0.0.2}" > AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > -ip,nw_src=10.0.0.1,nw_dst=20.0.0.1 > -ip,nw_src=10.0.0.1,nw_dst=20.0.0.2 > -ip,nw_src=10.0.0.2,nw_dst=20.0.0.1 > -ip,nw_src=10.0.0.2,nw_dst=20.0.0.2 > -ip,nw_src=10.0.0.3,nw_dst=20.0.0.1 > -ip,nw_src=10.0.0.3,nw_dst=20.0.0.2 > +conj_id=1,ip > +ip,nw_dst=20.0.0.1: conjunction(1, 0/2) > +ip,nw_dst=20.0.0.2: conjunction(1, 0/2) > +ip,nw_src=10.0.0.1: conjunction(1, 1/2) > +ip,nw_src=10.0.0.2: conjunction(1, 1/2) > +ip,nw_src=10.0.0.3: conjunction(1, 1/2) > ]) > > lflow="ip4 && ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ > @@ -720,19 +718,19 @@ ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3} && \ > tcp.dst >= 1000 && tcp.dst <= 1010" > > AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > -conj_id=1 > -tcp,nw_dst=20.0.0.1: conjunction(1, 2/3) > -tcp,nw_dst=20.0.0.2: conjunction(1, 2/3) > -tcp,nw_dst=20.0.0.3: conjunction(1, 2/3) > +conj_id=1,tcp > +tcp,nw_dst=20.0.0.1: conjunction(1, 0/3) > +tcp,nw_dst=20.0.0.2: conjunction(1, 0/3) > +tcp,nw_dst=20.0.0.3: conjunction(1, 0/3) > tcp,nw_src=10.0.0.1: conjunction(1, 1/3) > tcp,nw_src=10.0.0.2: conjunction(1, 1/3) > tcp,nw_src=10.0.0.3: conjunction(1, 1/3) > -tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 0/3) > -tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 0/3) > -tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 0/3) > -tcp,tp_dst=1000: conjunction(1, 0/3) > -tcp,tp_dst=1001: conjunction(1, 0/3) > -tcp,tp_dst=1010: conjunction(1, 0/3) > +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 2/3) > +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 2/3) > +tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 2/3) > +tcp,tp_dst=1000: conjunction(1, 2/3) > +tcp,tp_dst=1001: conjunction(1, 2/3) > +tcp,tp_dst=1010: conjunction(1, 2/3) > ]) > > lflow="ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} && \ > @@ -741,6 +739,41 @@ tcp.dst <= 2000 && tcp.src >=1000 && tcp.src <= 2000) > \ > || ip4.dst == 20.0.0.5 || ip4.dst == 20.0.0.6)" > > AT_CHECK([expr_to_flow "$lflow"], [0], [dnl > +conj_id=1,tcp > +ip,nw_src=10.0.0.4,nw_dst=20.0.0.5 > +ip,nw_src=10.0.0.4,nw_dst=20.0.0.6 > +ip,nw_src=10.0.0.5,nw_dst=20.0.0.5 > +ip,nw_src=10.0.0.5,nw_dst=20.0.0.6 > +ip,nw_src=10.0.0.6,nw_dst=20.0.0.5 > +ip,nw_src=10.0.0.6,nw_dst=20.0.0.6 > +tcp,nw_dst=20.0.0.4: conjunction(1, 0/4) > +tcp,nw_dst=20.0.0.7: conjunction(1, 0/4) > +tcp,nw_dst=20.0.0.8: conjunction(1, 0/4) > +tcp,nw_src=10.0.0.4: conjunction(1, 1/4) > +tcp,nw_src=10.0.0.5: conjunction(1, 1/4) > +tcp,nw_src=10.0.0.6: conjunction(1, 1/4) > +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 2/4) > +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 2/4) > +tcp,tp_dst=0x3f0/0xfff0: conjunction(1, 2/4) > +tcp,tp_dst=0x400/0xfe00: conjunction(1, 2/4) > +tcp,tp_dst=0x600/0xff00: conjunction(1, 2/4) > +tcp,tp_dst=0x700/0xff80: conjunction(1, 2/4) > +tcp,tp_dst=0x780/0xffc0: conjunction(1, 2/4) > +tcp,tp_dst=0x7c0/0xfff0: conjunction(1, 2/4) > +tcp,tp_dst=1000: conjunction(1, 2/4) > +tcp,tp_dst=1001: conjunction(1, 2/4) > +tcp,tp_dst=2000: conjunction(1, 2/4) > +tcp,tp_src=0x3ea/0xfffe: conjunction(1, 3/4) > +tcp,tp_src=0x3ec/0xfffc: conjunction(1, 3/4) > +tcp,tp_src=0x3f0/0xfff0: conjunction(1, 3/4) > +tcp,tp_src=0x400/0xfe00: conjunction(1, 3/4) > +tcp,tp_src=0x600/0xff00: conjunction(1, 3/4) > +tcp,tp_src=0x700/0xff80: conjunction(1, 3/4) > +tcp,tp_src=0x780/0xffc0: conjunction(1, 3/4) > +tcp,tp_src=0x7c0/0xfff0: conjunction(1, 3/4) > +tcp,tp_src=1000: conjunction(1, 3/4) > +tcp,tp_src=1001: conjunction(1, 3/4) > +tcp,tp_src=2000: conjunction(1, 3/4) > ]) > AT_CLEANUP > > -- > 2.14.3 >
diff --git a/include/ovn/expr.h b/include/ovn/expr.h index 711713e08..52aa74ed4 100644 --- a/include/ovn/expr.h +++ b/include/ovn/expr.h @@ -295,6 +295,8 @@ enum expr_type { EXPR_T_CONDITION, /* Conditional to be evaluated in the * controller during expr_simplify(), * prior to constructing OpenFlow matches. */ + EXPR_T_CONJ, /* Conjunction of 2 or more Logical AND + * subexpressions. */ }; /* Expression condition type. */ @@ -333,7 +335,8 @@ bool expr_relop_from_token(enum lex_type type, enum expr_relop *relop); * * The expr_honors_invariants() function can check invariants. */ struct expr { - struct ovs_list node; /* In parent EXPR_T_AND or EXPR_T_OR if any. */ + struct ovs_list node; /* In parent EXPR_T_AND, EXPR_T_OR or + * EXPR_T_CONJ if any. */ enum expr_type type; /* Expression type. */ union { @@ -366,6 +369,9 @@ struct expr { /* XXX Should arguments for conditions be generic? */ char *string; } cond; + + /* EXPR_T_CONJ. */ + struct ovs_list conj; }; }; @@ -397,6 +403,7 @@ struct expr *expr_simplify(struct expr *, const char *port_name), const void *c_aux); struct expr *expr_normalize(struct expr *); +struct expr *expr_eval_conj(struct expr *); bool expr_honors_invariants(const struct expr *); bool expr_is_simplified(const struct expr *); @@ -500,5 +507,4 @@ 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); - #endif /* ovn/expr.h */ diff --git a/ovn/controller/lflow.c b/ovn/controller/lflow.c index df125b188..88340df13 100644 --- a/ovn/controller/lflow.c +++ b/ovn/controller/lflow.c @@ -284,6 +284,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 b0aa6726b..b0441f9a3 100644 --- a/ovn/lib/expr.c +++ b/ovn/lib/expr.c @@ -152,6 +152,14 @@ expr_create_andor(enum expr_type type) return e; } +static 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,7 @@ expr_get_level(const struct expr *expr) case EXPR_T_CONDITION: return EXPR_L_BOOLEAN; + case EXPR_T_CONJ: default: OVS_NOT_REACHED(); } @@ -1540,6 +1554,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 +1585,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 +1623,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 +1762,7 @@ expr_annotate__(struct expr *expr, const struct shash *symtab, *errorp = NULL; return expr; + case EXPR_T_CONJ: default: OVS_NOT_REACHED(); } @@ -1918,6 +1956,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(); } @@ -1951,6 +1992,7 @@ expr_get_unique_symbol(const struct expr *expr) case EXPR_T_BOOLEAN: case EXPR_T_CONDITION: + case EXPR_T_CONJ: return NULL; default: @@ -2048,6 +2090,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(); } } @@ -2144,6 +2187,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(); } } @@ -2361,6 +2405,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(); } @@ -2579,6 +2624,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: @@ -2752,6 +2811,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(); } @@ -2885,6 +2945,40 @@ 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); + if (sub_conjs) { + /* We don't support sub conjunctive flows. */ + expr_matches_destroy(&conj_matches); + expr_matches_destroy(matches); + return 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: @@ -2969,6 +3063,7 @@ expr_honors_invariants(const struct expr *expr) case EXPR_T_CONDITION: return true; + case EXPR_T_CONJ: default: OVS_NOT_REACHED(); } @@ -3019,6 +3114,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(); } @@ -3116,6 +3222,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(); } @@ -3237,6 +3344,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(); } @@ -3302,3 +3410,70 @@ 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) { + /* Consider for dimension only if the number of children is > 2. + * One example is if the logical flow has "ip && ...", then a + * sub will be OR(CMP(ip4), CMP(ip6)) and we will add it as a + * dimension which may be incorrect. + */ + 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/ovn.at b/tests/ovn.at index 8ee3bf0b5..d37e23481 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -657,6 +657,74 @@ ip,nw_src=8.0.0.0/8.0.0.0 ]) AT_CLEANUP +AT_SETUP([ovn -- converting expressions to flows -- conjunction]) +AT_KEYWORDS([conjunction]) +expr_to_flow () { + echo "$1" | ovstest test-ovn expr-to-flows | sort +} + +lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ +ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3}" +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +conj_id=1 +ip,nw_dst=20.0.0.1: conjunction(1, 1/2) +ip,nw_dst=20.0.0.2: conjunction(1, 1/2) +ip,nw_dst=20.0.0.3: conjunction(1, 1/2) +ip,nw_src=10.0.0.1: conjunction(1, 0/2) +ip,nw_src=10.0.0.2: conjunction(1, 0/2) +ip,nw_src=10.0.0.3: conjunction(1, 0/2) +]) + +lflow="ip && (!ct.est || (ct.est && ct_label.blocked == 1))" +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +ct_state=+est+trk,ct_label=0x1/0x1,ip +ct_state=+est+trk,ct_label=0x1/0x1,ipv6 +ct_state=-est+trk,ip +ct_state=-est+trk,ipv6 +]) + +# ip4.dst has only 2 items. So it shouldn't be considered as a +# dimension. +lflow="ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ +ip4.dst == {20.0.0.1, 20.0.0.2}" +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +ip,nw_src=10.0.0.1,nw_dst=20.0.0.1 +ip,nw_src=10.0.0.1,nw_dst=20.0.0.2 +ip,nw_src=10.0.0.2,nw_dst=20.0.0.1 +ip,nw_src=10.0.0.2,nw_dst=20.0.0.2 +ip,nw_src=10.0.0.3,nw_dst=20.0.0.1 +ip,nw_src=10.0.0.3,nw_dst=20.0.0.2 +]) + +lflow="ip4 && ip4.src == {10.0.0.1, 10.0.0.2, 10.0.0.3} && \ +ip4.dst == {20.0.0.1, 20.0.0.2, 20.0.0.3} && \ +tcp.dst >= 1000 && tcp.dst <= 1010" + +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +conj_id=1 +tcp,nw_dst=20.0.0.1: conjunction(1, 2/3) +tcp,nw_dst=20.0.0.2: conjunction(1, 2/3) +tcp,nw_dst=20.0.0.3: conjunction(1, 2/3) +tcp,nw_src=10.0.0.1: conjunction(1, 1/3) +tcp,nw_src=10.0.0.2: conjunction(1, 1/3) +tcp,nw_src=10.0.0.3: conjunction(1, 1/3) +tcp,tp_dst=0x3ea/0xfffe: conjunction(1, 0/3) +tcp,tp_dst=0x3ec/0xfffc: conjunction(1, 0/3) +tcp,tp_dst=0x3f0/0xfffe: conjunction(1, 0/3) +tcp,tp_dst=1000: conjunction(1, 0/3) +tcp,tp_dst=1001: conjunction(1, 0/3) +tcp,tp_dst=1010: conjunction(1, 0/3) +]) + +lflow="ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} && \ +((ip4.dst == {20.0.0.4, 20.0.0.7, 20.0.0.8} && tcp.dst >= 1000 && \ +tcp.dst <= 2000 && tcp.src >=1000 && tcp.src <= 2000) \ +|| ip4.dst == 20.0.0.5 || ip4.dst == 20.0.0.6)" + +AT_CHECK([expr_to_flow "$lflow"], [0], [dnl +]) +AT_CLEANUP + AT_SETUP([ovn -- action parsing]) dnl Unindented text is input (a set of OVN logical actions). dnl Indented text is expected output. @@ -9329,3 +9397,130 @@ ra_test 000005dc 40 80 40 aef00000000000000000000000000000 30 fd0f00000000000000 OVN_CLEANUP([hv1],[hv2]) AT_CLEANUP + +AT_SETUP([ovn -- ACL conjunction]) +ovn_start + +ovn-nbctl ls-add ls1 + +ovn-nbctl lsp-add ls1 ls1-lp1 \ +-- lsp-set-addresses ls1-lp1 "f0:00:00:00:00:01 10.0.0.4" + +ovn-nbctl lsp-set-port-security ls1-lp1 "f0:00:00:00:00:01 10.0.0.4" + +ovn-nbctl lsp-add ls1 ls1-lp2 \ +-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02 10.0.0.6" + +ovn-nbctl lsp-set-port-security ls1-lp2 "f0:00:00:00:00:02 10.0.0.6" + +net_add n1 +sim_add hv1 + +as hv1 +ovs-vsctl add-br br-phys +ovn_attach n1 br-phys 192.168.0.1 +ovs-vsctl -- add-port br-int hv1-vif1 -- \ + set interface hv1-vif1 external-ids:iface-id=ls1-lp1 \ + options:tx_pcap=hv1/vif1-tx.pcap \ + options:rxq_pcap=hv1/vif1-rx.pcap \ + ofport-request=1 + +ovs-vsctl -- add-port br-int hv1-vif2 -- \ + set interface hv1-vif2 external-ids:iface-id=ls1-lp2 \ + options:tx_pcap=hv1/vif2-tx.pcap \ + options:rxq_pcap=hv1/vif2-rx.pcap \ + ofport-request=2 + +ovn-nbctl create Address_Set name=set1 \ +addresses=\"10.0.0.4\",\"10.0.0.5\",\"10.0.0.6\" +ovn-nbctl create Address_Set name=set2 \ +addresses=\"10.0.0.7\",\"10.0.0.8\",\"10.0.0.9\" +ovn-nbctl acl-add ls1 to-lport 1002 \ +'ip4 && ip4.src == $set1 && ip4.dst == $set1' allow +ovn-nbctl acl-add ls1 to-lport 1001 \ +'ip4 && ip4.src == $set1 && ip4.dst == $set2' drop + +# test_ip INPORT SRC_MAC DST_MAC SRC_IP DST_IP OUTPORT... +# +# This shell function causes an ip packet to be received on INPORT. +# The packet's content has Ethernet destination DST and source SRC +# (each exactly 12 hex digits) and Ethernet type ETHTYPE (4 hex digits). +# The OUTPORTs (zero or more) list the VIFs on which the packet should +# be received. INPORT and the OUTPORTs are specified as logical switch +# port numbers, e.g. 11 for vif11. +test_ip() { + # This packet has bad checksums but logical L3 routing doesn't check. + local inport=$1 src_mac=$2 dst_mac=$3 src_ip=$4 dst_ip=$5 + local packet=${dst_mac}${src_mac}08004500001c0000000040110000${src_ip}\ +${dst_ip}0035111100080000 + shift; shift; shift; shift; shift + as hv1 ovs-appctl netdev-dummy/receive hv1-vif1 $packet + for outport; do + echo $packet >> $outport.expected + done +} + +ip_to_hex() { + printf "%02x%02x%02x%02x" "$@" +} + +reset_pcap_file() { + local iface=$1 + local pcap_file=$2 + ovs-vsctl -- set Interface $iface options:tx_pcap=dummy-tx.pcap \ +options:rxq_pcap=dummy-rx.pcap + rm -f ${pcap_file}*.pcap + ovs-vsctl -- set Interface $iface options:tx_pcap=${pcap_file}-tx.pcap \ +options:rxq_pcap=${pcap_file}-rx.pcap +} + + +sip=`ip_to_hex 10 0 0 4` +dip=`ip_to_hex 10 0 0 6` + +test_ip 1 f00000000001 f00000000002 $sip $dip 2 + +cat 2.expected > expout +$PYTHON "$top_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets +AT_CHECK([cat 2.packets], [0], [expout]) + +# There should be total of 12 flows present with conjunction action and 2 flows +# with conj match. Eg. +# table=44, priority=2002,conj_id=2,metadata=0x1 actions=resubmit(,45) +# table=44, priority=2001,conj_id=3,metadata=0x1 actions=drop +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.6 actions=conjunction(2,2/2) +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,2/2) +# priority=2002,ip,metadata=0x1,nw_dst=10.0.0.5 actions=conjunction(2,2/2) +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.7 actions=conjunction(3,2/2) +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.9 actions=conjunction(3,2/2) +# priority=2001,ip,metadata=0x1,nw_dst=10.0.0.8 actions=conjunction(3,2/2) +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.6 actions=conjunction(2,1/2) +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.4 actions=conjunction(2,1/2) +# priority=2002,ip,metadata=0x1,nw_src=10.0.0.5 actions=conjunction(2,1/2) +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.6 actions=conjunction(3,1/2) +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.4 actions=conjunction(3,1/2) +# priority=2001,ip,metadata=0x1,nw_src=10.0.0.5 actions=conjunction(3,1/2) + +OVS_WAIT_UNTIL([test 12 = `as hv1 ovs-ofctl dump-flows br-int | \ +grep conjunction | wc -l`]) +OVS_WAIT_UNTIL([test 2 = `as hv1 ovs-ofctl dump-flows br-int | \ +grep conj_id | wc -l`]) + +as hv1 ovs-ofctl dump-flows br-int + +# Set the ip address for ls1-lp2 from set2 so that the drop ACL flow is hit. +ovn-nbctl lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02 10.0.0.7 20.0.0.4" +ovn-nbctl lsp-set-port-security ls1-lp2 "f0:00:00:00:00:02 10.0.0.7 20.0.0.4" + +reset_pcap_file hv1-vif2 hv1/vif2 + +rm -f 2.packets + +sip=`ip_to_hex 10 0 0 4` +dip=`ip_to_hex 10 0 0 7` + +test_ip 1 f00000000001 f00000000002 $sip $dip +$PYTHON "$top_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets +AT_CHECK([cat 2.packets], [0], []) + +AT_CLEANUP diff --git a/tests/test-ovn.c b/tests/test-ovn.c index 745275318..c7d54a865 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);