diff mbox series

[ovs-dev,v4] ofctrl: Add a predictable resolution for conflicting flow actions.

Message ID 1601451527-19334-1-git-send-email-dceara@redhat.com
State Changes Requested
Headers show
Series [ovs-dev,v4] ofctrl: Add a predictable resolution for conflicting flow actions. | expand

Commit Message

Dumitru Ceara Sept. 30, 2020, 7:38 a.m. UTC
Until now, in case the ACL configuration generates openflows that have
the same match but different actions, ovn-controller was using the
following approach:
1. If the flow being added contains conjunctive actions, merge its
   actions with the already existing flow.
2. Otherwise, if the flow is being added incrementally
   (update_installed_flows_by_track), don't install the new flow but
   instead keep the old one.
3. Otherwise, (update_installed_flows_by_compare), don't install the
   new flow but instead keep the old one.

Even though one can argue that having an ACL with a match that includes
the match of another ACL is a misconfiguration, it can happen that the
users provision OVN like this. Depending on the order of reading and
installing the logical flows, the above operations can yield
unpredictable results, e.g., allow specific traffic but then after
ovn-controller is restarted (or a recompute happens) that specific
traffic starts being dropped.

A simple example of ACL configuration is:
ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
ovn-nbctl acl-add ls to-lport 2 'arp' allow
ovn-nbctl acl-add ls to-lport 1 'ip4' drop

This is a pattern used by most CMSs:
- define a default deny policy.
- punch holes in the default deny policy based on user specific
  configurations.

Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
is unpredictable. Depending on the order of operations traffic might be
dropped or allowed.

It's also quite hard to force the CMS to ensure that such match overlaps
never occur.

To address this issue we now resolve conflicts between flows with the
same match and different actions by giving precedence to less
restrictive flows. This means that if the installed flow has action
"conjunction" and the desired flow doesn't then we prefer the desired
flow. Similarly, if the desired flow has action "conjunction" and the
installed flow doesn't then we prefer the already installed flow.

CC: Daniel Alvarez <dalvarez@redhat.com>
CC: Han Zhou <hzhou@ovn.org>
Reported-at: https://bugzilla.redhat.com/1871931
Acked-by: Mark Michelson <mmichels@redhat.com>
Signed-off-by: Dumitru Ceara <dceara@redhat.com>
---
v4:
- Address Han's comments:
  - make sure only flows with action conjunction are combined.
v3:
- Add Mark's ack.
- Add last missing pcap check in the test.
v2:
- Address Han's comments:
  - Do not delete desired flow that cannot be merged, it might be
    installed later.
  - Fix typos in the commit log.
- Update the test to check the OVS flows.
---
 controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
 tests/ovn.at        | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 332 insertions(+), 26 deletions(-)

Comments

Mark Michelson Oct. 2, 2020, 5:12 p.m. UTC | #1
re-adding my  ack to this version

Acked-by: Mark Michelson <mmichels@redhat.com>

On 9/30/20 3:38 AM, Dumitru Ceara wrote:
> Until now, in case the ACL configuration generates openflows that have
> the same match but different actions, ovn-controller was using the
> following approach:
> 1. If the flow being added contains conjunctive actions, merge its
>     actions with the already existing flow.
> 2. Otherwise, if the flow is being added incrementally
>     (update_installed_flows_by_track), don't install the new flow but
>     instead keep the old one.
> 3. Otherwise, (update_installed_flows_by_compare), don't install the
>     new flow but instead keep the old one.
> 
> Even though one can argue that having an ACL with a match that includes
> the match of another ACL is a misconfiguration, it can happen that the
> users provision OVN like this. Depending on the order of reading and
> installing the logical flows, the above operations can yield
> unpredictable results, e.g., allow specific traffic but then after
> ovn-controller is restarted (or a recompute happens) that specific
> traffic starts being dropped.
> 
> A simple example of ACL configuration is:
> ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
> ovn-nbctl acl-add ls to-lport 2 'arp' allow
> ovn-nbctl acl-add ls to-lport 1 'ip4' drop
> 
> This is a pattern used by most CMSs:
> - define a default deny policy.
> - punch holes in the default deny policy based on user specific
>    configurations.
> 
> Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
> is unpredictable. Depending on the order of operations traffic might be
> dropped or allowed.
> 
> It's also quite hard to force the CMS to ensure that such match overlaps
> never occur.
> 
> To address this issue we now resolve conflicts between flows with the
> same match and different actions by giving precedence to less
> restrictive flows. This means that if the installed flow has action
> "conjunction" and the desired flow doesn't then we prefer the desired
> flow. Similarly, if the desired flow has action "conjunction" and the
> installed flow doesn't then we prefer the already installed flow.
> 
> CC: Daniel Alvarez <dalvarez@redhat.com>
> CC: Han Zhou <hzhou@ovn.org>
> Reported-at: https://bugzilla.redhat.com/1871931
> Acked-by: Mark Michelson <mmichels@redhat.com>
> Signed-off-by: Dumitru Ceara <dceara@redhat.com>
> ---
> v4:
> - Address Han's comments:
>    - make sure only flows with action conjunction are combined.
> v3:
> - Add Mark's ack.
> - Add last missing pcap check in the test.
> v2:
> - Address Han's comments:
>    - Do not delete desired flow that cannot be merged, it might be
>      installed later.
>    - Fix typos in the commit log.
> - Update the test to check the OVS flows.
> ---
>   controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
>   tests/ovn.at        | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 332 insertions(+), 26 deletions(-)
> 
> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
> index 81a00c8..4577413 100644
> --- a/controller/ofctrl.c
> +++ b/controller/ofctrl.c
> @@ -206,6 +206,9 @@ struct installed_flow {
>       struct desired_flow *desired_flow;
>   };
>   
> +typedef bool
> +(*desired_flow_match_cb)(const struct desired_flow *candidate,
> +                         const void *arg);
>   static struct desired_flow *desired_flow_alloc(
>       uint8_t table_id,
>       uint16_t priority,
> @@ -214,8 +217,14 @@ static struct desired_flow *desired_flow_alloc(
>       const struct ofpbuf *actions);
>   static struct desired_flow *desired_flow_lookup(
>       struct ovn_desired_flow_table *,
> +    const struct ovn_flow *target);
> +static struct desired_flow *desired_flow_lookup_by_uuid(
> +    struct ovn_desired_flow_table *,
>       const struct ovn_flow *target,
> -    const struct uuid *sb_uuid);
> +    const struct uuid *);
> +static struct desired_flow *desired_flow_lookup_conjunctive(
> +    struct ovn_desired_flow_table *,
> +    const struct ovn_flow *target);
>   static void desired_flow_destroy(struct desired_flow *);
>   
>   static struct installed_flow *installed_flow_lookup(
> @@ -916,6 +925,33 @@ link_flow_to_sb(struct ovn_desired_flow_table *flow_table,
>       ovs_list_insert(&stf->flows, &sfr->flow_list);
>   }
>   
> +static bool
> +flow_action_has_conj(const struct ovn_flow *f)
> +{
> +    const struct ofpact *a = NULL;
> +
> +    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
> +        if (a->type == OFPACT_CONJUNCTION) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}
> +
> +static void
> +flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
> +                          const struct ovn_flow *f2)
> +{
> +    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
> +    char *f1_s = ovn_flow_to_string(f1);
> +    char *f2_s = ovn_flow_to_string(f2);
> +
> +    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2: %s",
> +                 msg, f1_s, f2_s);
> +    free(f1_s);
> +    free(f2_s);
> +}
> +
>   /* Flow table interfaces to the rest of ovn-controller. */
>   
>   /* Adds a flow to 'desired_flows' with the specified 'match' and 'actions' to
> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table,
>       struct desired_flow *f = desired_flow_alloc(table_id, priority, cookie,
>                                                   match, actions);
>   
> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
> +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
>           if (log_duplicate_flow) {
>               static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 5);
>               if (!VLOG_DROP_DBG(&rl)) {
> @@ -979,14 +1015,15 @@ ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows,
>                             const struct ofpbuf *actions,
>                             const struct uuid *sb_uuid)
>   {
> -    struct desired_flow *f = desired_flow_alloc(table_id, priority, cookie,
> -                                                match, actions);
> -
>       struct desired_flow *existing;
> -    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
> +    struct desired_flow *f;
> +
> +    f = desired_flow_alloc(table_id, priority, cookie, match, actions);
> +    existing = desired_flow_lookup_conjunctive(desired_flows, &f->flow);
>       if (existing) {
> -        /* There's already a flow with this particular match. Append the
> -         * action to that flow rather than adding a new flow
> +        /* There's already a flow with this particular match and action
> +         * 'conjunction'. Append the action to that flow rather than
> +         * adding a new flow.
>            */
>           uint64_t compound_stub[64 / 8];
>           struct ofpbuf compound;
> @@ -1225,15 +1262,11 @@ installed_flow_dup(struct desired_flow *src)
>       return dst;
>   }
>   
> -/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
> - * 'target''s key, or NULL if there is none.
> - *
> - * If sb_uuid is not NULL, the function will also check if the found flow is
> - * referenced by the sb_uuid. */
>   static struct desired_flow *
> -desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> -                    const struct ovn_flow *target,
> -                    const struct uuid *sb_uuid)
> +desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
> +                      const struct ovn_flow *target,
> +                      desired_flow_match_cb match_cb,
> +                      const void *arg)
>   {
>       struct desired_flow *d;
>       HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
> @@ -1242,20 +1275,75 @@ desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
>           if (f->table_id == target->table_id
>               && f->priority == target->priority
>               && minimatch_equal(&f->match, &target->match)) {
> -            if (!sb_uuid) {
> +
> +            if (!match_cb || match_cb(d, arg)) {
>                   return d;
>               }
> -            struct sb_flow_ref *sfr;
> -            LIST_FOR_EACH (sfr, sb_list, &d->references) {
> -                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> -                    return d;
> -                }
> -            }
>           }
>       }
>       return NULL;
>   }
>   
> +/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
> + * 'target''s key, or NULL if there is none.
> + */
> +static struct desired_flow *
> +desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> +                    const struct ovn_flow *target)
> +{
> +    return desired_flow_lookup__(flow_table, target, NULL, NULL);
> +}
> +
> +static bool
> +flow_lookup_match_uuid(const struct desired_flow *candidate, const void *arg)
> +{
> +    const struct uuid *sb_uuid = arg;
> +    struct sb_flow_ref *sfr;
> +
> +    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
> +        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}
> +
> +/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
> + * 'target''s key, or NULL if there is none.
> + *
> + * The function will also check if the found flow is referenced by the
> + * 'sb_uuid'.
> + */
> +static struct desired_flow *
> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table *flow_table,
> +                            const struct ovn_flow *target,
> +                            const struct uuid *sb_uuid)
> +{
> +    return desired_flow_lookup__(flow_table, target, flow_lookup_match_uuid,
> +                                 sb_uuid);
> +}
> +
> +static bool
> +flow_lookup_match_conj(const struct desired_flow *candidate,
> +                       const void *arg OVS_UNUSED)
> +{
> +    return flow_action_has_conj(&candidate->flow);
> +}
> +
> +/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
> + * 'target''s key, or NULL if there is none.
> + *
> + * The function will only return a matching flow if it contains action
> + * 'conjunction'.
> + */
> +static struct desired_flow *
> +desired_flow_lookup_conjunctive(struct ovn_desired_flow_table *flow_table,
> +                                const struct ovn_flow *target)
> +{
> +    return desired_flow_lookup__(flow_table, target, flow_lookup_match_conj,
> +                                 NULL);
> +}
> +
>   /* Finds and returns an installed_flow in installed_flows whose key is
>    * identical to 'target''s key, or NULL if there is none. */
>   static struct installed_flow *
> @@ -1653,8 +1741,7 @@ update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
>       struct installed_flow *i, *next;
>       HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
>           unlink_all_refs_for_installed_flow(i);
> -        struct desired_flow *d =
> -            desired_flow_lookup(flow_table, &i->flow, NULL);
> +        struct desired_flow *d = desired_flow_lookup(flow_table, &i->flow);
>           if (!d) {
>               /* Installed flow is no longer desirable.  Delete it from the
>                * switch and from installed_flows. */
> @@ -1687,6 +1774,18 @@ update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
>               /* Copy 'd' from 'flow_table' to installed_flows. */
>               i = installed_flow_dup(d);
>               hmap_insert(&installed_flows, &i->match_hmap_node, i->flow.hash);
> +        } else if (i->desired_flow != d) {
> +            /* If a matching installed flow was found but its actions are
> +             * conflicting with the desired flow actions, we should chose
> +             * to install the least restrictive one (i.e., no conjunctive
> +             * action).
> +             */
> +            if (flow_action_has_conj(&i->flow) &&
> +                    !flow_action_has_conj(&d->flow)) {
> +                flow_log_actions_conflict("Use new flow", &i->flow, &d->flow);
> +                installed_flow_mod(&i->flow, &d->flow, msgs);
> +                ovn_flow_log(&i->flow, "updating installed");
> +            }
>           }
>           link_installed_to_desired(i, d);
>       }
> @@ -1817,7 +1916,19 @@ update_installed_flows_by_track(struct ovn_desired_flow_table *flow_table,
>                   installed_flow_mod(&i->flow, &f->flow, msgs);
>               } else {
>                   /* Adding a new flow that conflicts with an existing installed
> -                 * flow, so just add it to the link. */
> +                 * flow, so just add it to the link.
> +                 *
> +                 * However, if the existing installed flow is less restrictive
> +                 * (i.e., no conjunctive action), we should chose it over the
> +                 * existing installed flow.
> +                 */
> +                if (flow_action_has_conj(&i->flow) &&
> +                        !flow_action_has_conj(&f->flow)) {
> +                    flow_log_actions_conflict("Use new flow",
> +                                              &i->flow, &f->flow);
> +                    ovn_flow_log(&i->flow, "updating installed (tracked)");
> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
> +                }
>                   link_installed_to_desired(i, f);
>               }
>               /* The track_list_node emptyness is used to check if the node is
> diff --git a/tests/ovn.at b/tests/ovn.at
> index 7769b69..6b77057 100644
> --- a/tests/ovn.at
> +++ b/tests/ovn.at
> @@ -13709,6 +13709,201 @@ grep conjunction.*conjunction.*conjunction | wc -l`])
>   OVN_CLEANUP([hv1])
>   AT_CLEANUP
>   
> +AT_SETUP([ovn -- Superseeding ACLs with 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"
> +
> +ovn-nbctl lsp-add ls1 ls1-lp2 \
> +-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02"
> +
> +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
> +
> +# 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
> +}
> +
> +# Add a default deny ACL and an allow ACL for specific IP traffic.
> +ovn-nbctl acl-add ls1 to-lport 2 'arp' allow
> +ovn-nbctl acl-add ls1 to-lport 1 'ip4' drop
> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.42) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
> +dip=`ip_to_hex 10 0 0 5`
> +for src in `seq 1 2`; do
> +    sip=`ip_to_hex 10 0 0 $src`
> +
> +    test_ip 1 f00000000001 f00000000002 $sip $dip
> +done
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +reset_pcap_file hv1-vif2 hv1/vif2
> +rm -f 2.packets
> +> 2.expected
> +
> +# Add a less restrictive allow ACL for src IP 10.0.0.1
> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the less restrictive flows should have been installed.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.2 -> 10.0.0.5 should be dropped.
> +sip=`ip_to_hex 10 0 0 2`
> +dip=`ip_to_hex 10 0 0 5`
> +test_ip 1 f00000000001 f00000000002 $sip $dip
> +
> +# Traffic 10.0.0.1 -> 10.0.0.5 should be allowed.
> +sip=`ip_to_hex 10 0 0 1`
> +dip=`ip_to_hex 10 0 0 5`
> +test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +reset_pcap_file hv1-vif2 hv1/vif2
> +rm -f 2.packets
> +> 2.expected
> +
> +# Remove the less restrictive allow ACL.
> +ovn-nbctl acl-del ls1 to-lport 3 'ip4.src==10.0.0.1'
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the 10.0.0.1 conjunction should have been reinstalled.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=conjunction(2,2/2),conjunction(3,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
> +dip=`ip_to_hex 10 0 0 5`
> +for src in `seq 1 2`; do
> +    sip=`ip_to_hex 10 0 0 $src`
> +
> +    test_ip 1 f00000000001 f00000000002 $sip $dip
> +done
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +
> +# Re-add the less restrictive allow ACL for src IP 10.0.0.1
> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the less restrictive flows should have been installed.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +   grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +OVN_CLEANUP([hv1])
> +AT_CLEANUP
> +
>   # 3 hypervisors, one logical switch, 3 logical ports per hypervisor
>   AT_SETUP([ovn -- L2 Drop and Allow ACL w/ Stateful ACL])
>   ovn_start
>
Han Zhou Oct. 2, 2020, 8:28 p.m. UTC | #2
Hi Dumitru,

Thanks for the revision. It looks good overall. The major problems left are:
1. it missed updating the active desired_flow in the installed_flow.
2. when a tracked flow deletion is handled, if there are other desired
flows linked to the same installed flow, it should use the same criteria to
decide which flow should become active from the candidate flows.

I also noticed 2 problems of the existing code while reviewing this patch.
I submitted 2 patches:
1.
https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
2.
https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/

1) is required for your solution to work properly. 2) is not directly
related but will cause a merge conflict. Please help review both since they
are closely related to your patch.

Please see more detailed comments below.

On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> Until now, in case the ACL configuration generates openflows that have
> the same match but different actions, ovn-controller was using the
> following approach:
> 1. If the flow being added contains conjunctive actions, merge its
>    actions with the already existing flow.
> 2. Otherwise, if the flow is being added incrementally
>    (update_installed_flows_by_track), don't install the new flow but
>    instead keep the old one.
> 3. Otherwise, (update_installed_flows_by_compare), don't install the
>    new flow but instead keep the old one.
>
> Even though one can argue that having an ACL with a match that includes
> the match of another ACL is a misconfiguration, it can happen that the
> users provision OVN like this. Depending on the order of reading and
> installing the logical flows, the above operations can yield
> unpredictable results, e.g., allow specific traffic but then after
> ovn-controller is restarted (or a recompute happens) that specific
> traffic starts being dropped.
>
> A simple example of ACL configuration is:
> ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
> ovn-nbctl acl-add ls to-lport 2 'arp' allow
> ovn-nbctl acl-add ls to-lport 1 'ip4' drop
>
> This is a pattern used by most CMSs:
> - define a default deny policy.
> - punch holes in the default deny policy based on user specific
>   configurations.
>
> Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
> is unpredictable. Depending on the order of operations traffic might be
> dropped or allowed.
>
> It's also quite hard to force the CMS to ensure that such match overlaps
> never occur.
>
> To address this issue we now resolve conflicts between flows with the
> same match and different actions by giving precedence to less
> restrictive flows. This means that if the installed flow has action
> "conjunction" and the desired flow doesn't then we prefer the desired
> flow. Similarly, if the desired flow has action "conjunction" and the
> installed flow doesn't then we prefer the already installed flow.
>
> CC: Daniel Alvarez <dalvarez@redhat.com>
> CC: Han Zhou <hzhou@ovn.org>
> Reported-at: https://bugzilla.redhat.com/1871931
> Acked-by: Mark Michelson <mmichels@redhat.com>
> Signed-off-by: Dumitru Ceara <dceara@redhat.com>
> ---
> v4:
> - Address Han's comments:
>   - make sure only flows with action conjunction are combined.
> v3:
> - Add Mark's ack.
> - Add last missing pcap check in the test.
> v2:
> - Address Han's comments:
>   - Do not delete desired flow that cannot be merged, it might be
>     installed later.
>   - Fix typos in the commit log.
> - Update the test to check the OVS flows.
> ---
>  controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
>  tests/ovn.at        | 195
++++++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 332 insertions(+), 26 deletions(-)
>
> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
> index 81a00c8..4577413 100644
> --- a/controller/ofctrl.c
> +++ b/controller/ofctrl.c
> @@ -206,6 +206,9 @@ struct installed_flow {
>      struct desired_flow *desired_flow;
>  };
>
> +typedef bool
> +(*desired_flow_match_cb)(const struct desired_flow *candidate,
> +                         const void *arg);
>  static struct desired_flow *desired_flow_alloc(
>      uint8_t table_id,
>      uint16_t priority,
> @@ -214,8 +217,14 @@ static struct desired_flow *desired_flow_alloc(
>      const struct ofpbuf *actions);
>  static struct desired_flow *desired_flow_lookup(
>      struct ovn_desired_flow_table *,
> +    const struct ovn_flow *target);
> +static struct desired_flow *desired_flow_lookup_by_uuid(

The name "by_uuid" is a little misleading. It sounds like it only looks
uuid. But instead, it still looks up by match which it will also compare
uuid. How about: desired_flow_lookup_check_uuid?

> +    struct ovn_desired_flow_table *,
>      const struct ovn_flow *target,
> -    const struct uuid *sb_uuid);
> +    const struct uuid *);
> +static struct desired_flow *desired_flow_lookup_conjunctive(
> +    struct ovn_desired_flow_table *,
> +    const struct ovn_flow *target);
>  static void desired_flow_destroy(struct desired_flow *);
>
>  static struct installed_flow *installed_flow_lookup(
> @@ -916,6 +925,33 @@ link_flow_to_sb(struct ovn_desired_flow_table
*flow_table,
>      ovs_list_insert(&stf->flows, &sfr->flow_list);
>  }
>
> +static bool
> +flow_action_has_conj(const struct ovn_flow *f)
> +{
> +    const struct ofpact *a = NULL;
> +
> +    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
> +        if (a->type == OFPACT_CONJUNCTION) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}
> +
> +static void
> +flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
> +                          const struct ovn_flow *f2)
> +{
> +    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
> +    char *f1_s = ovn_flow_to_string(f1);
> +    char *f2_s = ovn_flow_to_string(f2);
> +
> +    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2:
%s",
> +                 msg, f1_s, f2_s);
> +    free(f1_s);
> +    free(f2_s);
> +}
> +

In this log it would be better to mention which one is selected. It would
be better not only abstracting the logging into a function but also the
logic of comparing flows and determining which one is selected.

>  /* Flow table interfaces to the rest of ovn-controller. */
>
>  /* Adds a flow to 'desired_flows' with the specified 'match' and
'actions' to
> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
ovn_desired_flow_table *flow_table,
>      struct desired_flow *f = desired_flow_alloc(table_id, priority,
cookie,
>                                                  match, actions);
>
> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
> +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
>          if (log_duplicate_flow) {
>              static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5,
5);
>              if (!VLOG_DROP_DBG(&rl)) {
> @@ -979,14 +1015,15 @@ ofctrl_add_or_append_flow(struct
ovn_desired_flow_table *desired_flows,
>                            const struct ofpbuf *actions,
>                            const struct uuid *sb_uuid)
>  {
> -    struct desired_flow *f = desired_flow_alloc(table_id, priority,
cookie,
> -                                                match, actions);
> -
>      struct desired_flow *existing;
> -    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
> +    struct desired_flow *f;
> +
> +    f = desired_flow_alloc(table_id, priority, cookie, match, actions);
> +    existing = desired_flow_lookup_conjunctive(desired_flows, &f->flow);
>      if (existing) {
> -        /* There's already a flow with this particular match. Append the
> -         * action to that flow rather than adding a new flow
> +        /* There's already a flow with this particular match and action
> +         * 'conjunction'. Append the action to that flow rather than
> +         * adding a new flow.
>           */
>          uint64_t compound_stub[64 / 8];
>          struct ofpbuf compound;
> @@ -1225,15 +1262,11 @@ installed_flow_dup(struct desired_flow *src)
>      return dst;
>  }
>
> -/* Finds and returns a desired_flow in 'flow_table' whose key is
identical to
> - * 'target''s key, or NULL if there is none.
> - *
> - * If sb_uuid is not NULL, the function will also check if the found
flow is
> - * referenced by the sb_uuid. */
>  static struct desired_flow *
> -desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> -                    const struct ovn_flow *target,
> -                    const struct uuid *sb_uuid)
> +desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
> +                      const struct ovn_flow *target,
> +                      desired_flow_match_cb match_cb,
> +                      const void *arg)
>  {
>      struct desired_flow *d;
>      HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
> @@ -1242,20 +1275,75 @@ desired_flow_lookup(struct ovn_desired_flow_table
*flow_table,
>          if (f->table_id == target->table_id
>              && f->priority == target->priority
>              && minimatch_equal(&f->match, &target->match)) {
> -            if (!sb_uuid) {
> +
> +            if (!match_cb || match_cb(d, arg)) {
>                  return d;
>              }
> -            struct sb_flow_ref *sfr;
> -            LIST_FOR_EACH (sfr, sb_list, &d->references) {
> -                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> -                    return d;
> -                }
> -            }
>          }
>      }
>      return NULL;
>  }
>
> +/* Finds and returns a desired_flow in 'flow_table' whose key is
identical to
> + * 'target''s key, or NULL if there is none.
> + */
> +static struct desired_flow *
> +desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> +                    const struct ovn_flow *target)
> +{
> +    return desired_flow_lookup__(flow_table, target, NULL, NULL);
> +}
> +
> +static bool
> +flow_lookup_match_uuid(const struct desired_flow *candidate, const void
*arg)

This function is used as a callback, so it would be better to have _cb in
its name to help code reading, e.g. flow_lookup_cb_match_uuid

> +{
> +    const struct uuid *sb_uuid = arg;
> +    struct sb_flow_ref *sfr;
> +
> +    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
> +        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}
> +
> +/* Finds and returns a desired_flow in 'flow_table' whose key is
identical to
> + * 'target''s key, or NULL if there is none.
> + *
> + * The function will also check if the found flow is referenced by the
> + * 'sb_uuid'.
> + */
> +static struct desired_flow *
> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table *flow_table,
> +                            const struct ovn_flow *target,
> +                            const struct uuid *sb_uuid)
> +{
> +    return desired_flow_lookup__(flow_table, target,
flow_lookup_match_uuid,
> +                                 sb_uuid);
> +}
> +
> +static bool
> +flow_lookup_match_conj(const struct desired_flow *candidate,
> +                       const void *arg OVS_UNUSED)

Same as above of the naming.

> +{
> +    return flow_action_has_conj(&candidate->flow);
> +}
> +
> +/* Finds and returns a desired_flow in 'flow_table' whose key is
identical to
> + * 'target''s key, or NULL if there is none.
> + *
> + * The function will only return a matching flow if it contains action
> + * 'conjunction'.
> + */
> +static struct desired_flow *
> +desired_flow_lookup_conjunctive(struct ovn_desired_flow_table
*flow_table,
> +                                const struct ovn_flow *target)
> +{
> +    return desired_flow_lookup__(flow_table, target,
flow_lookup_match_conj,
> +                                 NULL);
> +}
> +
>  /* Finds and returns an installed_flow in installed_flows whose key is
>   * identical to 'target''s key, or NULL if there is none. */
>  static struct installed_flow *
> @@ -1653,8 +1741,7 @@ update_installed_flows_by_compare(struct
ovn_desired_flow_table *flow_table,
>      struct installed_flow *i, *next;
>      HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
>          unlink_all_refs_for_installed_flow(i);
> -        struct desired_flow *d =
> -            desired_flow_lookup(flow_table, &i->flow, NULL);
> +        struct desired_flow *d = desired_flow_lookup(flow_table,
&i->flow);
>          if (!d) {
>              /* Installed flow is no longer desirable.  Delete it from the
>               * switch and from installed_flows. */
> @@ -1687,6 +1774,18 @@ update_installed_flows_by_compare(struct
ovn_desired_flow_table *flow_table,
>              /* Copy 'd' from 'flow_table' to installed_flows. */
>              i = installed_flow_dup(d);
>              hmap_insert(&installed_flows, &i->match_hmap_node,
i->flow.hash);
> +        } else if (i->desired_flow != d) {
> +            /* If a matching installed flow was found but its actions are
> +             * conflicting with the desired flow actions, we should chose
> +             * to install the least restrictive one (i.e., no conjunctive
> +             * action).
> +             */
> +            if (flow_action_has_conj(&i->flow) &&
> +                    !flow_action_has_conj(&d->flow)) {
> +                flow_log_actions_conflict("Use new flow", &i->flow,
&d->flow);
> +                installed_flow_mod(&i->flow, &d->flow, msgs);
> +                ovn_flow_log(&i->flow, "updating installed");
> +            }

Here is a problem. Before this change, the flow actually installed in OVS
is the one found in the previous loop. Now in this case we change the flow
installed, we should update the i->desired_flow to match the one selected.

>          }
>          link_installed_to_desired(i, d);
>      }
> @@ -1817,7 +1916,19 @@ update_installed_flows_by_track(struct
ovn_desired_flow_table *flow_table,
>                  installed_flow_mod(&i->flow, &f->flow, msgs);
>              } else {
>                  /* Adding a new flow that conflicts with an existing
installed
> -                 * flow, so just add it to the link. */
> +                 * flow, so just add it to the link.
> +                 *
> +                 * However, if the existing installed flow is less
restrictive
> +                 * (i.e., no conjunctive action), we should chose it
over the
> +                 * existing installed flow.
> +                 */
> +                if (flow_action_has_conj(&i->flow) &&
> +                        !flow_action_has_conj(&f->flow)) {
> +                    flow_log_actions_conflict("Use new flow",
> +                                              &i->flow, &f->flow);
> +                    ovn_flow_log(&i->flow, "updating installed
(tracked)");
> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
> +                }

We should make sure it is set as the active flow.

In addition, in the other branch in this function when the flow is deleted,
we need to use the same criteria to select the flow to be actively
installed. Currently unlink_installed_to_desired() just pick the first one
from the rest of desired_flows in the linked list. This patch should go
through the list and figure out which one should be selected using the same
criteria.

Thanks,
Han

>                  link_installed_to_desired(i, f);
>              }
>              /* The track_list_node emptyness is used to check if the
node is
> diff --git a/tests/ovn.at b/tests/ovn.at
> index 7769b69..6b77057 100644
> --- a/tests/ovn.at
> +++ b/tests/ovn.at
> @@ -13709,6 +13709,201 @@ grep conjunction.*conjunction.*conjunction | wc
-l`])
>  OVN_CLEANUP([hv1])
>  AT_CLEANUP
>
> +AT_SETUP([ovn -- Superseeding ACLs with 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"
> +
> +ovn-nbctl lsp-add ls1 ls1-lp2 \
> +-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02"
> +
> +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
> +
> +# 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
> +}
> +
> +# Add a default deny ACL and an allow ACL for specific IP traffic.
> +ovn-nbctl acl-add ls1 to-lport 2 'arp' allow
> +ovn-nbctl acl-add ls1 to-lport 1 'ip4' drop
> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 ||
ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 ||
ip4.src==10.0.0.42) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
> +dip=`ip_to_hex 10 0 0 5`
> +for src in `seq 1 2`; do
> +    sip=`ip_to_hex 10 0 0 $src`
> +
> +    test_ip 1 f00000000001 f00000000002 $sip $dip
> +done
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +reset_pcap_file hv1-vif2 hv1/vif2
> +rm -f 2.packets
> +> 2.expected
> +
> +# Add a less restrictive allow ACL for src IP 10.0.0.1
> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the less restrictive flows should have been installed.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.2 -> 10.0.0.5 should be dropped.
> +sip=`ip_to_hex 10 0 0 2`
> +dip=`ip_to_hex 10 0 0 5`
> +test_ip 1 f00000000001 f00000000002 $sip $dip
> +
> +# Traffic 10.0.0.1 -> 10.0.0.5 should be allowed.
> +sip=`ip_to_hex 10 0 0 1`
> +dip=`ip_to_hex 10 0 0 5`
> +test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +reset_pcap_file hv1-vif2 hv1/vif2
> +rm -f 2.packets
> +> 2.expected
> +
> +# Remove the less restrictive allow ACL.
> +ovn-nbctl acl-del ls1 to-lport 3 'ip4.src==10.0.0.1'
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the 10.0.0.1 conjunction should have been reinstalled.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1
actions=conjunction(2,2/2),conjunction(3,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
> +for src in `seq 1 2`; do
> +    for dst in `seq 3 4`; do
> +        sip=`ip_to_hex 10 0 0 $src`
> +        dip=`ip_to_hex 10 0 0 $dst`
> +
> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
> +    done
> +done
> +
> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
> +dip=`ip_to_hex 10 0 0 5`
> +for src in `seq 1 2`; do
> +    sip=`ip_to_hex 10 0 0 $src`
> +
> +    test_ip 1 f00000000001 f00000000002 $sip $dip
> +done
> +
> +cat 2.expected > expout
> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
> +AT_CHECK([cat 2.packets], [0], [expout])
> +
> +# Re-add the less restrictive allow ACL for src IP 10.0.0.1
> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
> +ovn-nbctl --wait=hv sync
> +
> +# Check OVS flows, the less restrictive flows should have been installed.
> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
> +   grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
actions=conjunction(2,1/2),conjunction(3,1/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
> +])
> +
> +OVN_CLEANUP([hv1])
> +AT_CLEANUP
> +
>  # 3 hypervisors, one logical switch, 3 logical ports per hypervisor
>  AT_SETUP([ovn -- L2 Drop and Allow ACL w/ Stateful ACL])
>  ovn_start
> --
> 1.8.3.1
>
Dumitru Ceara Oct. 6, 2020, 8:30 a.m. UTC | #3
On 10/2/20 10:28 PM, Han Zhou wrote:
> 
> Hi Dumitru,
> 

Hi Han,

> Thanks for the revision. It looks good overall. The major problems left are:
> 1. it missed updating the active desired_flow in the installed_flow.
> 2. when a tracked flow deletion is handled, if there are other desired
> flows linked to the same installed flow, it should use the same criteria
> to decide which flow should become active from the candidate flows.
> 

I see, you're right, thanks. I'll fix it in the next revision.

> I also noticed 2 problems of the existing code while reviewing this
> patch. I submitted 2 patches:
> 1.
> https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
> 2.
> https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
> 
> 1) is required for your solution to work properly. 2) is not directly
> related but will cause a merge conflict. Please help review both since
> they are closely related to your patch.
> 

I'll try to review your patches as soon as possible and I'll respin mine
afterwards.

> Please see more detailed comments below.
> 
> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>> wrote:
>>
>> Until now, in case the ACL configuration generates openflows that have
>> the same match but different actions, ovn-controller was using the
>> following approach:
>> 1. If the flow being added contains conjunctive actions, merge its
>>    actions with the already existing flow.
>> 2. Otherwise, if the flow is being added incrementally
>>    (update_installed_flows_by_track), don't install the new flow but
>>    instead keep the old one.
>> 3. Otherwise, (update_installed_flows_by_compare), don't install the
>>    new flow but instead keep the old one.
>>
>> Even though one can argue that having an ACL with a match that includes
>> the match of another ACL is a misconfiguration, it can happen that the
>> users provision OVN like this. Depending on the order of reading and
>> installing the logical flows, the above operations can yield
>> unpredictable results, e.g., allow specific traffic but then after
>> ovn-controller is restarted (or a recompute happens) that specific
>> traffic starts being dropped.
>>
>> A simple example of ACL configuration is:
>> ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
>> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
>> ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
>> ovn-nbctl acl-add ls to-lport 2 'arp' allow
>> ovn-nbctl acl-add ls to-lport 1 'ip4' drop
>>
>> This is a pattern used by most CMSs:
>> - define a default deny policy.
>> - punch holes in the default deny policy based on user specific
>>   configurations.
>>
>> Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
>> is unpredictable. Depending on the order of operations traffic might be
>> dropped or allowed.
>>
>> It's also quite hard to force the CMS to ensure that such match overlaps
>> never occur.
>>
>> To address this issue we now resolve conflicts between flows with the
>> same match and different actions by giving precedence to less
>> restrictive flows. This means that if the installed flow has action
>> "conjunction" and the desired flow doesn't then we prefer the desired
>> flow. Similarly, if the desired flow has action "conjunction" and the
>> installed flow doesn't then we prefer the already installed flow.
>>
>> CC: Daniel Alvarez <dalvarez@redhat.com <mailto:dalvarez@redhat.com>>
>> CC: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>>
>> Reported-at: https://bugzilla.redhat.com/1871931
>> Acked-by: Mark Michelson <mmichels@redhat.com
> <mailto:mmichels@redhat.com>>
>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>>
>> ---
>> v4:
>> - Address Han's comments:
>>   - make sure only flows with action conjunction are combined.
>> v3:
>> - Add Mark's ack.
>> - Add last missing pcap check in the test.
>> v2:
>> - Address Han's comments:
>>   - Do not delete desired flow that cannot be merged, it might be
>>     installed later.
>>   - Fix typos in the commit log.
>> - Update the test to check the OVS flows.
>> ---
>>  controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
>>  tests/ovn.at <http://ovn.at>        | 195
> ++++++++++++++++++++++++++++++++++++++++++++++++++++
>>  2 files changed, 332 insertions(+), 26 deletions(-)
>>
>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
>> index 81a00c8..4577413 100644
>> --- a/controller/ofctrl.c
>> +++ b/controller/ofctrl.c
>> @@ -206,6 +206,9 @@ struct installed_flow {
>>      struct desired_flow *desired_flow;
>>  };
>>
>> +typedef bool
>> +(*desired_flow_match_cb)(const struct desired_flow *candidate,
>> +                         const void *arg);
>>  static struct desired_flow *desired_flow_alloc(
>>      uint8_t table_id,
>>      uint16_t priority,
>> @@ -214,8 +217,14 @@ static struct desired_flow *desired_flow_alloc(
>>      const struct ofpbuf *actions);
>>  static struct desired_flow *desired_flow_lookup(
>>      struct ovn_desired_flow_table *,
>> +    const struct ovn_flow *target);
>> +static struct desired_flow *desired_flow_lookup_by_uuid(
> 
> The name "by_uuid" is a little misleading. It sounds like it only looks
> uuid. But instead, it still looks up by match which it will also compare
> uuid. How about: desired_flow_lookup_check_uuid?
> 
>> +    struct ovn_desired_flow_table *,
>>      const struct ovn_flow *target,
>> -    const struct uuid *sb_uuid);
>> +    const struct uuid *);
>> +static struct desired_flow *desired_flow_lookup_conjunctive(
>> +    struct ovn_desired_flow_table *,
>> +    const struct ovn_flow *target);
>>  static void desired_flow_destroy(struct desired_flow *);
>>
>>  static struct installed_flow *installed_flow_lookup(
>> @@ -916,6 +925,33 @@ link_flow_to_sb(struct ovn_desired_flow_table
> *flow_table,
>>      ovs_list_insert(&stf->flows, &sfr->flow_list);
>>  }
>>
>> +static bool
>> +flow_action_has_conj(const struct ovn_flow *f)
>> +{
>> +    const struct ofpact *a = NULL;
>> +
>> +    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
>> +        if (a->type == OFPACT_CONJUNCTION) {
>> +            return true;
>> +        }
>> +    }
>> +    return false;
>> +}
>> +
>> +static void
>> +flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
>> +                          const struct ovn_flow *f2)
>> +{
>> +    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
>> +    char *f1_s = ovn_flow_to_string(f1);
>> +    char *f2_s = ovn_flow_to_string(f2);
>> +
>> +    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2:
> %s",
>> +                 msg, f1_s, f2_s);
>> +    free(f1_s);
>> +    free(f2_s);
>> +}
>> +
> 
> In this log it would be better to mention which one is selected. It
> would be better not only abstracting the logging into a function but
> also the logic of comparing flows and determining which one is selected.
> 

Ack, sounds better indeed.

>>  /* Flow table interfaces to the rest of ovn-controller. */
>>
>>  /* Adds a flow to 'desired_flows' with the specified 'match' and
> 'actions' to
>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
> ovn_desired_flow_table *flow_table,
>>      struct desired_flow *f = desired_flow_alloc(table_id, priority,
> cookie,
>>                                                  match, actions);
>>
>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
>> +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
>>          if (log_duplicate_flow) {
>>              static struct vlog_rate_limit rl =
> VLOG_RATE_LIMIT_INIT(5, 5);
>>              if (!VLOG_DROP_DBG(&rl)) {
>> @@ -979,14 +1015,15 @@ ofctrl_add_or_append_flow(struct
> ovn_desired_flow_table *desired_flows,
>>                            const struct ofpbuf *actions,
>>                            const struct uuid *sb_uuid)
>>  {
>> -    struct desired_flow *f = desired_flow_alloc(table_id, priority,
> cookie,
>> -                                                match, actions);
>> -
>>      struct desired_flow *existing;
>> -    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
>> +    struct desired_flow *f;
>> +
>> +    f = desired_flow_alloc(table_id, priority, cookie, match, actions);
>> +    existing = desired_flow_lookup_conjunctive(desired_flows, &f->flow);
>>      if (existing) {
>> -        /* There's already a flow with this particular match. Append the
>> -         * action to that flow rather than adding a new flow
>> +        /* There's already a flow with this particular match and action
>> +         * 'conjunction'. Append the action to that flow rather than
>> +         * adding a new flow.
>>           */
>>          uint64_t compound_stub[64 / 8];
>>          struct ofpbuf compound;
>> @@ -1225,15 +1262,11 @@ installed_flow_dup(struct desired_flow *src)
>>      return dst;
>>  }
>>
>> -/* Finds and returns a desired_flow in 'flow_table' whose key is
> identical to
>> - * 'target''s key, or NULL if there is none.
>> - *
>> - * If sb_uuid is not NULL, the function will also check if the found
> flow is
>> - * referenced by the sb_uuid. */
>>  static struct desired_flow *
>> -desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
>> -                    const struct ovn_flow *target,
>> -                    const struct uuid *sb_uuid)
>> +desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
>> +                      const struct ovn_flow *target,
>> +                      desired_flow_match_cb match_cb,
>> +                      const void *arg)
>>  {
>>      struct desired_flow *d;
>>      HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
>> @@ -1242,20 +1275,75 @@ desired_flow_lookup(struct
> ovn_desired_flow_table *flow_table,
>>          if (f->table_id == target->table_id
>>              && f->priority == target->priority
>>              && minimatch_equal(&f->match, &target->match)) {
>> -            if (!sb_uuid) {
>> +
>> +            if (!match_cb || match_cb(d, arg)) {
>>                  return d;
>>              }
>> -            struct sb_flow_ref *sfr;
>> -            LIST_FOR_EACH (sfr, sb_list, &d->references) {
>> -                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
>> -                    return d;
>> -                }
>> -            }
>>          }
>>      }
>>      return NULL;
>>  }
>>
>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> identical to
>> + * 'target''s key, or NULL if there is none.
>> + */
>> +static struct desired_flow *
>> +desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
>> +                    const struct ovn_flow *target)
>> +{
>> +    return desired_flow_lookup__(flow_table, target, NULL, NULL);
>> +}
>> +
>> +static bool
>> +flow_lookup_match_uuid(const struct desired_flow *candidate, const
> void *arg)
> 
> This function is used as a callback, so it would be better to have _cb
> in its name to help code reading, e.g. flow_lookup_cb_match_uuid
> 

Sure.

>> +{
>> +    const struct uuid *sb_uuid = arg;
>> +    struct sb_flow_ref *sfr;
>> +
>> +    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
>> +        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
>> +            return true;
>> +        }
>> +    }
>> +    return false;
>> +}
>> +
>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> identical to
>> + * 'target''s key, or NULL if there is none.
>> + *
>> + * The function will also check if the found flow is referenced by the
>> + * 'sb_uuid'.
>> + */
>> +static struct desired_flow *
>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table *flow_table,
>> +                            const struct ovn_flow *target,
>> +                            const struct uuid *sb_uuid)
>> +{
>> +    return desired_flow_lookup__(flow_table, target,
> flow_lookup_match_uuid,
>> +                                 sb_uuid);
>> +}
>> +
>> +static bool
>> +flow_lookup_match_conj(const struct desired_flow *candidate,
>> +                       const void *arg OVS_UNUSED)
> 
> Same as above of the naming.
> 

Ack.

>> +{
>> +    return flow_action_has_conj(&candidate->flow);
>> +}
>> +
>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> identical to
>> + * 'target''s key, or NULL if there is none.
>> + *
>> + * The function will only return a matching flow if it contains action
>> + * 'conjunction'.
>> + */
>> +static struct desired_flow *
>> +desired_flow_lookup_conjunctive(struct ovn_desired_flow_table
> *flow_table,
>> +                                const struct ovn_flow *target)
>> +{
>> +    return desired_flow_lookup__(flow_table, target,
> flow_lookup_match_conj,
>> +                                 NULL);
>> +}
>> +
>>  /* Finds and returns an installed_flow in installed_flows whose key is
>>   * identical to 'target''s key, or NULL if there is none. */
>>  static struct installed_flow *
>> @@ -1653,8 +1741,7 @@ update_installed_flows_by_compare(struct
> ovn_desired_flow_table *flow_table,
>>      struct installed_flow *i, *next;
>>      HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
>>          unlink_all_refs_for_installed_flow(i);
>> -        struct desired_flow *d =
>> -            desired_flow_lookup(flow_table, &i->flow, NULL);
>> +        struct desired_flow *d = desired_flow_lookup(flow_table,
> &i->flow);
>>          if (!d) {
>>              /* Installed flow is no longer desirable.  Delete it from the
>>               * switch and from installed_flows. */
>> @@ -1687,6 +1774,18 @@ update_installed_flows_by_compare(struct
> ovn_desired_flow_table *flow_table,
>>              /* Copy 'd' from 'flow_table' to installed_flows. */
>>              i = installed_flow_dup(d);
>>              hmap_insert(&installed_flows, &i->match_hmap_node,
> i->flow.hash);
>> +        } else if (i->desired_flow != d) {
>> +            /* If a matching installed flow was found but its actions are
>> +             * conflicting with the desired flow actions, we should chose
>> +             * to install the least restrictive one (i.e., no conjunctive
>> +             * action).
>> +             */
>> +            if (flow_action_has_conj(&i->flow) &&
>> +                    !flow_action_has_conj(&d->flow)) {
>> +                flow_log_actions_conflict("Use new flow", &i->flow,
> &d->flow);
>> +                installed_flow_mod(&i->flow, &d->flow, msgs);
>> +                ovn_flow_log(&i->flow, "updating installed");
>> +            }
> 
> Here is a problem. Before this change, the flow actually installed in
> OVS is the one found in the previous loop. Now in this case we change
> the flow installed, we should update the i->desired_flow to match the
> one selected.
> 

Right, thanks for spotting this.

>>          }
>>          link_installed_to_desired(i, d);
>>      }
>> @@ -1817,7 +1916,19 @@ update_installed_flows_by_track(struct
> ovn_desired_flow_table *flow_table,
>>                  installed_flow_mod(&i->flow, &f->flow, msgs);
>>              } else {
>>                  /* Adding a new flow that conflicts with an existing
> installed
>> -                 * flow, so just add it to the link. */
>> +                 * flow, so just add it to the link.
>> +                 *
>> +                 * However, if the existing installed flow is less
> restrictive
>> +                 * (i.e., no conjunctive action), we should chose it
> over the
>> +                 * existing installed flow.
>> +                 */
>> +                if (flow_action_has_conj(&i->flow) &&
>> +                        !flow_action_has_conj(&f->flow)) {
>> +                    flow_log_actions_conflict("Use new flow",
>> +                                              &i->flow, &f->flow);
>> +                    ovn_flow_log(&i->flow, "updating installed
> (tracked)");
>> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
>> +                }
> 
> We should make sure it is set as the active flow.
> 
> In addition, in the other branch in this function when the flow is
> deleted, we need to use the same criteria to select the flow to be
> actively installed. Currently unlink_installed_to_desired() just pick
> the first one from the rest of desired_flows in the linked list. This
> patch should go through the list and figure out which one should be
> selected using the same criteria.
> 

I think I also need to double check the self test. I thought I was
covering this case too but I guess I was wrong.

Thanks,
Dumitru

> Thanks,
> Han
> 
>>                  link_installed_to_desired(i, f);
>>              }
>>              /* The track_list_node emptyness is used to check if the
> node is
>> diff --git a/tests/ovn.at <http://ovn.at> b/tests/ovn.at <http://ovn.at>
>> index 7769b69..6b77057 100644
>> --- a/tests/ovn.at <http://ovn.at>
>> +++ b/tests/ovn.at <http://ovn.at>
>> @@ -13709,6 +13709,201 @@ grep conjunction.*conjunction.*conjunction |
> wc -l`])
>>  OVN_CLEANUP([hv1])
>>  AT_CLEANUP
>>
>> +AT_SETUP([ovn -- Superseeding ACLs with 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"
>> +
>> +ovn-nbctl lsp-add ls1 ls1-lp2 \
>> +-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02"
>> +
>> +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
>> +
>> +# 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
>> +}
>> +
>> +# Add a default deny ACL and an allow ACL for specific IP traffic.
>> +ovn-nbctl acl-add ls1 to-lport 2 'arp' allow
>> +ovn-nbctl acl-add ls1 to-lport 1 'ip4' drop
>> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 ||
> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
>> +ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 ||
> ip4.src==10.0.0.42) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
>> +ovn-nbctl --wait=hv sync
>> +
>> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
>> +for src in `seq 1 2`; do
>> +    for dst in `seq 3 4`; do
>> +        sip=`ip_to_hex 10 0 0 $src`
>> +        dip=`ip_to_hex 10 0 0 $dst`
>> +
>> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
>> +    done
>> +done
>> +
>> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
>> +dip=`ip_to_hex 10 0 0 5`
>> +for src in `seq 1 2`; do
>> +    sip=`ip_to_hex 10 0 0 $src`
>> +
>> +    test_ip 1 f00000000001 f00000000002 $sip $dip
>> +done
>> +
>> +cat 2.expected > expout
>> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in <http://ovs-pcap.in>"
> hv1/vif2-tx.pcap > 2.packets
>> +AT_CHECK([cat 2.packets], [0], [expout])
>> +reset_pcap_file hv1-vif2 hv1/vif2
>> +rm -f 2.packets
>> +> 2.expected
>> +
>> +# Add a less restrictive allow ACL for src IP 10.0.0.1
>> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
>> +ovn-nbctl --wait=hv sync
>> +
>> +# Check OVS flows, the less restrictive flows should have been installed.
>> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
>> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
>> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
>> +])
>> +
>> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
>> +for src in `seq 1 2`; do
>> +    for dst in `seq 3 4`; do
>> +        sip=`ip_to_hex 10 0 0 $src`
>> +        dip=`ip_to_hex 10 0 0 $dst`
>> +
>> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
>> +    done
>> +done
>> +
>> +# Traffic 10.0.0.2 -> 10.0.0.5 should be dropped.
>> +sip=`ip_to_hex 10 0 0 2`
>> +dip=`ip_to_hex 10 0 0 5`
>> +test_ip 1 f00000000001 f00000000002 $sip $dip
>> +
>> +# Traffic 10.0.0.1 -> 10.0.0.5 should be allowed.
>> +sip=`ip_to_hex 10 0 0 1`
>> +dip=`ip_to_hex 10 0 0 5`
>> +test_ip 1 f00000000001 f00000000002 $sip $dip 2
>> +
>> +cat 2.expected > expout
>> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in <http://ovs-pcap.in>"
> hv1/vif2-tx.pcap > 2.packets
>> +AT_CHECK([cat 2.packets], [0], [expout])
>> +reset_pcap_file hv1-vif2 hv1/vif2
>> +rm -f 2.packets
>> +> 2.expected
>> +
>> +# Remove the less restrictive allow ACL.
>> +ovn-nbctl acl-del ls1 to-lport 3 'ip4.src==10.0.0.1'
>> +ovn-nbctl --wait=hv sync
>> +
>> +# Check OVS flows, the 10.0.0.1 conjunction should have been reinstalled.
>> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
>> +    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
>> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1
> actions=conjunction(2,2/2),conjunction(3,2/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
>> +])
>> +
>> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
>> +for src in `seq 1 2`; do
>> +    for dst in `seq 3 4`; do
>> +        sip=`ip_to_hex 10 0 0 $src`
>> +        dip=`ip_to_hex 10 0 0 $dst`
>> +
>> +        test_ip 1 f00000000001 f00000000002 $sip $dip 2
>> +    done
>> +done
>> +
>> +# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
>> +dip=`ip_to_hex 10 0 0 5`
>> +for src in `seq 1 2`; do
>> +    sip=`ip_to_hex 10 0 0 $src`
>> +
>> +    test_ip 1 f00000000001 f00000000002 $sip $dip
>> +done
>> +
>> +cat 2.expected > expout
>> +$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in <http://ovs-pcap.in>"
> hv1/vif2-tx.pcap > 2.packets
>> +AT_CHECK([cat 2.packets], [0], [expout])
>> +
>> +# Re-add the less restrictive allow ACL for src IP 10.0.0.1
>> +ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
>> +ovn-nbctl --wait=hv sync
>> +
>> +# Check OVS flows, the less restrictive flows should have been installed.
>> +AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
>> +   grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
>> +priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4
> actions=conjunction(2,1/2),conjunction(3,1/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
>> +priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
>> +])
>> +
>> +OVN_CLEANUP([hv1])
>> +AT_CLEANUP
>> +
>>  # 3 hypervisors, one logical switch, 3 logical ports per hypervisor
>>  AT_SETUP([ovn -- L2 Drop and Allow ACL w/ Stateful ACL])
>>  ovn_start
>> --
>> 1.8.3.1
>>
Dumitru Ceara Oct. 11, 2020, 12:13 p.m. UTC | #4
On 10/6/20 10:30 AM, Dumitru Ceara wrote:
> On 10/2/20 10:28 PM, Han Zhou wrote:
>>
>> Hi Dumitru,
>>
> 
> Hi Han,
> 
>> Thanks for the revision. It looks good overall. The major problems left are:
>> 1. it missed updating the active desired_flow in the installed_flow.
>> 2. when a tracked flow deletion is handled, if there are other desired
>> flows linked to the same installed flow, it should use the same criteria
>> to decide which flow should become active from the candidate flows.
>>
> 
> I see, you're right, thanks. I'll fix it in the next revision.
> 
>> I also noticed 2 problems of the existing code while reviewing this
>> patch. I submitted 2 patches:
>> 1.
>> https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
>> 2.
>> https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
>>
>> 1) is required for your solution to work properly. 2) is not directly
>> related but will cause a merge conflict. Please help review both since
>> they are closely related to your patch.
>>
> 
> I'll try to review your patches as soon as possible and I'll respin mine
> afterwards.
> 
>> Please see more detailed comments below.
>>
>> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara <dceara@redhat.com
>> <mailto:dceara@redhat.com>> wrote:
>>>
>>> Until now, in case the ACL configuration generates openflows that have
>>> the same match but different actions, ovn-controller was using the
>>> following approach:
>>> 1. If the flow being added contains conjunctive actions, merge its
>>>    actions with the already existing flow.
>>> 2. Otherwise, if the flow is being added incrementally
>>>    (update_installed_flows_by_track), don't install the new flow but
>>>    instead keep the old one.
>>> 3. Otherwise, (update_installed_flows_by_compare), don't install the
>>>    new flow but instead keep the old one.
>>>
>>> Even though one can argue that having an ACL with a match that includes
>>> the match of another ACL is a misconfiguration, it can happen that the
>>> users provision OVN like this. Depending on the order of reading and
>>> installing the logical flows, the above operations can yield
>>> unpredictable results, e.g., allow specific traffic but then after
>>> ovn-controller is restarted (or a recompute happens) that specific
>>> traffic starts being dropped.
>>>
>>> A simple example of ACL configuration is:
>>> ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
>>> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
>>> ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
>>> ovn-nbctl acl-add ls to-lport 2 'arp' allow
>>> ovn-nbctl acl-add ls to-lport 1 'ip4' drop
>>>
>>> This is a pattern used by most CMSs:
>>> - define a default deny policy.
>>> - punch holes in the default deny policy based on user specific
>>>   configurations.
>>>
>>> Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
>>> is unpredictable. Depending on the order of operations traffic might be
>>> dropped or allowed.
>>>
>>> It's also quite hard to force the CMS to ensure that such match overlaps
>>> never occur.
>>>
>>> To address this issue we now resolve conflicts between flows with the
>>> same match and different actions by giving precedence to less
>>> restrictive flows. This means that if the installed flow has action
>>> "conjunction" and the desired flow doesn't then we prefer the desired
>>> flow. Similarly, if the desired flow has action "conjunction" and the
>>> installed flow doesn't then we prefer the already installed flow.
>>>
>>> CC: Daniel Alvarez <dalvarez@redhat.com <mailto:dalvarez@redhat.com>>
>>> CC: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>>
>>> Reported-at: https://bugzilla.redhat.com/1871931
>>> Acked-by: Mark Michelson <mmichels@redhat.com
>> <mailto:mmichels@redhat.com>>
>>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
>> <mailto:dceara@redhat.com>>
>>> ---
>>> v4:
>>> - Address Han's comments:
>>>   - make sure only flows with action conjunction are combined.
>>> v3:
>>> - Add Mark's ack.
>>> - Add last missing pcap check in the test.
>>> v2:
>>> - Address Han's comments:
>>>   - Do not delete desired flow that cannot be merged, it might be
>>>     installed later.
>>>   - Fix typos in the commit log.
>>> - Update the test to check the OVS flows.
>>> ---
>>>  controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
>>>  tests/ovn.at <http://ovn.at>        | 195
>> ++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>  2 files changed, 332 insertions(+), 26 deletions(-)
>>>
>>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
>>> index 81a00c8..4577413 100644
>>> --- a/controller/ofctrl.c
>>> +++ b/controller/ofctrl.c
>>> @@ -206,6 +206,9 @@ struct installed_flow {
>>>      struct desired_flow *desired_flow;
>>>  };
>>>
>>> +typedef bool
>>> +(*desired_flow_match_cb)(const struct desired_flow *candidate,
>>> +                         const void *arg);
>>>  static struct desired_flow *desired_flow_alloc(
>>>      uint8_t table_id,
>>>      uint16_t priority,
>>> @@ -214,8 +217,14 @@ static struct desired_flow *desired_flow_alloc(
>>>      const struct ofpbuf *actions);
>>>  static struct desired_flow *desired_flow_lookup(
>>>      struct ovn_desired_flow_table *,
>>> +    const struct ovn_flow *target);
>>> +static struct desired_flow *desired_flow_lookup_by_uuid(
>>
>> The name "by_uuid" is a little misleading. It sounds like it only looks
>> uuid. But instead, it still looks up by match which it will also compare
>> uuid. How about: desired_flow_lookup_check_uuid?
>>
>>> +    struct ovn_desired_flow_table *,
>>>      const struct ovn_flow *target,
>>> -    const struct uuid *sb_uuid);
>>> +    const struct uuid *);
>>> +static struct desired_flow *desired_flow_lookup_conjunctive(
>>> +    struct ovn_desired_flow_table *,
>>> +    const struct ovn_flow *target);
>>>  static void desired_flow_destroy(struct desired_flow *);
>>>
>>>  static struct installed_flow *installed_flow_lookup(
>>> @@ -916,6 +925,33 @@ link_flow_to_sb(struct ovn_desired_flow_table
>> *flow_table,
>>>      ovs_list_insert(&stf->flows, &sfr->flow_list);
>>>  }
>>>
>>> +static bool
>>> +flow_action_has_conj(const struct ovn_flow *f)
>>> +{
>>> +    const struct ofpact *a = NULL;
>>> +
>>> +    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
>>> +        if (a->type == OFPACT_CONJUNCTION) {
>>> +            return true;
>>> +        }
>>> +    }
>>> +    return false;
>>> +}
>>> +
>>> +static void
>>> +flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
>>> +                          const struct ovn_flow *f2)
>>> +{
>>> +    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
>>> +    char *f1_s = ovn_flow_to_string(f1);
>>> +    char *f2_s = ovn_flow_to_string(f2);
>>> +
>>> +    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2:
>> %s",
>>> +                 msg, f1_s, f2_s);
>>> +    free(f1_s);
>>> +    free(f2_s);
>>> +}
>>> +
>>
>> In this log it would be better to mention which one is selected. It
>> would be better not only abstracting the logging into a function but
>> also the logic of comparing flows and determining which one is selected.
>>
> 
> Ack, sounds better indeed.
> 
>>>  /* Flow table interfaces to the rest of ovn-controller. */
>>>
>>>  /* Adds a flow to 'desired_flows' with the specified 'match' and
>> 'actions' to
>>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
>> ovn_desired_flow_table *flow_table,
>>>      struct desired_flow *f = desired_flow_alloc(table_id, priority,
>> cookie,
>>>                                                  match, actions);
>>>
>>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
>>> +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
>>>          if (log_duplicate_flow) {
>>>              static struct vlog_rate_limit rl =
>> VLOG_RATE_LIMIT_INIT(5, 5);
>>>              if (!VLOG_DROP_DBG(&rl)) {
>>> @@ -979,14 +1015,15 @@ ofctrl_add_or_append_flow(struct
>> ovn_desired_flow_table *desired_flows,
>>>                            const struct ofpbuf *actions,
>>>                            const struct uuid *sb_uuid)
>>>  {
>>> -    struct desired_flow *f = desired_flow_alloc(table_id, priority,
>> cookie,
>>> -                                                match, actions);
>>> -
>>>      struct desired_flow *existing;
>>> -    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
>>> +    struct desired_flow *f;
>>> +
>>> +    f = desired_flow_alloc(table_id, priority, cookie, match, actions);
>>> +    existing = desired_flow_lookup_conjunctive(desired_flows, &f->flow);
>>>      if (existing) {
>>> -        /* There's already a flow with this particular match. Append the
>>> -         * action to that flow rather than adding a new flow
>>> +        /* There's already a flow with this particular match and action
>>> +         * 'conjunction'. Append the action to that flow rather than
>>> +         * adding a new flow.
>>>           */
>>>          uint64_t compound_stub[64 / 8];
>>>          struct ofpbuf compound;
>>> @@ -1225,15 +1262,11 @@ installed_flow_dup(struct desired_flow *src)
>>>      return dst;
>>>  }
>>>
>>> -/* Finds and returns a desired_flow in 'flow_table' whose key is
>> identical to
>>> - * 'target''s key, or NULL if there is none.
>>> - *
>>> - * If sb_uuid is not NULL, the function will also check if the found
>> flow is
>>> - * referenced by the sb_uuid. */
>>>  static struct desired_flow *
>>> -desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
>>> -                    const struct ovn_flow *target,
>>> -                    const struct uuid *sb_uuid)
>>> +desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
>>> +                      const struct ovn_flow *target,
>>> +                      desired_flow_match_cb match_cb,
>>> +                      const void *arg)
>>>  {
>>>      struct desired_flow *d;
>>>      HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
>>> @@ -1242,20 +1275,75 @@ desired_flow_lookup(struct
>> ovn_desired_flow_table *flow_table,
>>>          if (f->table_id == target->table_id
>>>              && f->priority == target->priority
>>>              && minimatch_equal(&f->match, &target->match)) {
>>> -            if (!sb_uuid) {
>>> +
>>> +            if (!match_cb || match_cb(d, arg)) {
>>>                  return d;
>>>              }
>>> -            struct sb_flow_ref *sfr;
>>> -            LIST_FOR_EACH (sfr, sb_list, &d->references) {
>>> -                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
>>> -                    return d;
>>> -                }
>>> -            }
>>>          }
>>>      }
>>>      return NULL;
>>>  }
>>>
>>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
>> identical to
>>> + * 'target''s key, or NULL if there is none.
>>> + */
>>> +static struct desired_flow *
>>> +desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
>>> +                    const struct ovn_flow *target)
>>> +{
>>> +    return desired_flow_lookup__(flow_table, target, NULL, NULL);
>>> +}
>>> +
>>> +static bool
>>> +flow_lookup_match_uuid(const struct desired_flow *candidate, const
>> void *arg)
>>
>> This function is used as a callback, so it would be better to have _cb
>> in its name to help code reading, e.g. flow_lookup_cb_match_uuid
>>
> 
> Sure.
> 
>>> +{
>>> +    const struct uuid *sb_uuid = arg;
>>> +    struct sb_flow_ref *sfr;
>>> +
>>> +    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
>>> +        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
>>> +            return true;
>>> +        }
>>> +    }
>>> +    return false;
>>> +}
>>> +
>>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
>> identical to
>>> + * 'target''s key, or NULL if there is none.
>>> + *
>>> + * The function will also check if the found flow is referenced by the
>>> + * 'sb_uuid'.
>>> + */
>>> +static struct desired_flow *
>>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table *flow_table,
>>> +                            const struct ovn_flow *target,
>>> +                            const struct uuid *sb_uuid)
>>> +{
>>> +    return desired_flow_lookup__(flow_table, target,
>> flow_lookup_match_uuid,
>>> +                                 sb_uuid);
>>> +}
>>> +
>>> +static bool
>>> +flow_lookup_match_conj(const struct desired_flow *candidate,
>>> +                       const void *arg OVS_UNUSED)
>>
>> Same as above of the naming.
>>
> 
> Ack.
> 
>>> +{
>>> +    return flow_action_has_conj(&candidate->flow);
>>> +}
>>> +
>>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
>> identical to
>>> + * 'target''s key, or NULL if there is none.
>>> + *
>>> + * The function will only return a matching flow if it contains action
>>> + * 'conjunction'.
>>> + */
>>> +static struct desired_flow *
>>> +desired_flow_lookup_conjunctive(struct ovn_desired_flow_table
>> *flow_table,
>>> +                                const struct ovn_flow *target)
>>> +{
>>> +    return desired_flow_lookup__(flow_table, target,
>> flow_lookup_match_conj,
>>> +                                 NULL);
>>> +}
>>> +
>>>  /* Finds and returns an installed_flow in installed_flows whose key is
>>>   * identical to 'target''s key, or NULL if there is none. */
>>>  static struct installed_flow *
>>> @@ -1653,8 +1741,7 @@ update_installed_flows_by_compare(struct
>> ovn_desired_flow_table *flow_table,
>>>      struct installed_flow *i, *next;
>>>      HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
>>>          unlink_all_refs_for_installed_flow(i);
>>> -        struct desired_flow *d =
>>> -            desired_flow_lookup(flow_table, &i->flow, NULL);
>>> +        struct desired_flow *d = desired_flow_lookup(flow_table,
>> &i->flow);
>>>          if (!d) {
>>>              /* Installed flow is no longer desirable.  Delete it from the
>>>               * switch and from installed_flows. */
>>> @@ -1687,6 +1774,18 @@ update_installed_flows_by_compare(struct
>> ovn_desired_flow_table *flow_table,
>>>              /* Copy 'd' from 'flow_table' to installed_flows. */
>>>              i = installed_flow_dup(d);
>>>              hmap_insert(&installed_flows, &i->match_hmap_node,
>> i->flow.hash);
>>> +        } else if (i->desired_flow != d) {
>>> +            /* If a matching installed flow was found but its actions are
>>> +             * conflicting with the desired flow actions, we should chose
>>> +             * to install the least restrictive one (i.e., no conjunctive
>>> +             * action).
>>> +             */
>>> +            if (flow_action_has_conj(&i->flow) &&
>>> +                    !flow_action_has_conj(&d->flow)) {
>>> +                flow_log_actions_conflict("Use new flow", &i->flow,
>> &d->flow);
>>> +                installed_flow_mod(&i->flow, &d->flow, msgs);
>>> +                ovn_flow_log(&i->flow, "updating installed");
>>> +            }
>>
>> Here is a problem. Before this change, the flow actually installed in
>> OVS is the one found in the previous loop. Now in this case we change
>> the flow installed, we should update the i->desired_flow to match the
>> one selected.
>>
> 
> Right, thanks for spotting this.
> 
>>>          }
>>>          link_installed_to_desired(i, d);
>>>      }
>>> @@ -1817,7 +1916,19 @@ update_installed_flows_by_track(struct
>> ovn_desired_flow_table *flow_table,
>>>                  installed_flow_mod(&i->flow, &f->flow, msgs);
>>>              } else {
>>>                  /* Adding a new flow that conflicts with an existing
>> installed
>>> -                 * flow, so just add it to the link. */
>>> +                 * flow, so just add it to the link.
>>> +                 *
>>> +                 * However, if the existing installed flow is less
>> restrictive
>>> +                 * (i.e., no conjunctive action), we should chose it
>> over the
>>> +                 * existing installed flow.
>>> +                 */
>>> +                if (flow_action_has_conj(&i->flow) &&
>>> +                        !flow_action_has_conj(&f->flow)) {
>>> +                    flow_log_actions_conflict("Use new flow",
>>> +                                              &i->flow, &f->flow);
>>> +                    ovn_flow_log(&i->flow, "updating installed
>> (tracked)");
>>> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
>>> +                }
>>
>> We should make sure it is set as the active flow.
>>
>> In addition, in the other branch in this function when the flow is
>> deleted, we need to use the same criteria to select the flow to be
>> actively installed. Currently unlink_installed_to_desired() just pick
>> the first one from the rest of desired_flows in the linked list. This
>> patch should go through the list and figure out which one should be
>> selected using the same criteria.
>>
> 
> I think I also need to double check the self test. I thought I was
> covering this case too but I guess I was wrong.
> 

Hi Han,

I've spent some more time thinking about all we discussed here and
there's another case we didn't cover:

Desired flow ordering can change (due to the order of logical flows in
the IDL) when a recompute happens so we'd always have to walk the
desired list flows to select the "least restrictive" one.

I found a better solution which is to ensure that all desired flows
referring an installed flow are always (partially) sorted in the list.
This can be easily implemented with O(1) complexity and also makes
selection of the "next-least-restrictive-flow" O(1).

I had to make some changes to the existing ofctrl code so I sent v5 as a
series to make it easier to review independent changes:

http://patchwork.ozlabs.org/project/ovn/list/?series=207123

Thanks,
Dumitru
Han Zhou Oct. 11, 2020, 7:40 p.m. UTC | #5
On Sun, Oct 11, 2020 at 5:14 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On 10/6/20 10:30 AM, Dumitru Ceara wrote:
> > On 10/2/20 10:28 PM, Han Zhou wrote:
> >>
> >> Hi Dumitru,
> >>
> >
> > Hi Han,
> >
> >> Thanks for the revision. It looks good overall. The major problems
left are:
> >> 1. it missed updating the active desired_flow in the installed_flow.
> >> 2. when a tracked flow deletion is handled, if there are other desired
> >> flows linked to the same installed flow, it should use the same
criteria
> >> to decide which flow should become active from the candidate flows.
> >>
> >
> > I see, you're right, thanks. I'll fix it in the next revision.
> >
> >> I also noticed 2 problems of the existing code while reviewing this
> >> patch. I submitted 2 patches:
> >> 1.
> >>
https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
> >> 2.
> >>
https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
> >>
> >> 1) is required for your solution to work properly. 2) is not directly
> >> related but will cause a merge conflict. Please help review both since
> >> they are closely related to your patch.
> >>
> >
> > I'll try to review your patches as soon as possible and I'll respin mine
> > afterwards.
> >
> >> Please see more detailed comments below.
> >>
> >> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara <dceara@redhat.com
> >> <mailto:dceara@redhat.com>> wrote:
> >>>
> >>> Until now, in case the ACL configuration generates openflows that have
> >>> the same match but different actions, ovn-controller was using the
> >>> following approach:
> >>> 1. If the flow being added contains conjunctive actions, merge its
> >>>    actions with the already existing flow.
> >>> 2. Otherwise, if the flow is being added incrementally
> >>>    (update_installed_flows_by_track), don't install the new flow but
> >>>    instead keep the old one.
> >>> 3. Otherwise, (update_installed_flows_by_compare), don't install the
> >>>    new flow but instead keep the old one.
> >>>
> >>> Even though one can argue that having an ACL with a match that
includes
> >>> the match of another ACL is a misconfiguration, it can happen that the
> >>> users provision OVN like this. Depending on the order of reading and
> >>> installing the logical flows, the above operations can yield
> >>> unpredictable results, e.g., allow specific traffic but then after
> >>> ovn-controller is restarted (or a recompute happens) that specific
> >>> traffic starts being dropped.
> >>>
> >>> A simple example of ACL configuration is:
> >>> ovn-nbctl acl-add ls to-lport 3 '(ip4.src==10.0.0.1 ||
> >>> ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)'
allow
> >>> ovn-nbctl acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow
> >>> ovn-nbctl acl-add ls to-lport 2 'arp' allow
> >>> ovn-nbctl acl-add ls to-lport 1 'ip4' drop
> >>>
> >>> This is a pattern used by most CMSs:
> >>> - define a default deny policy.
> >>> - punch holes in the default deny policy based on user specific
> >>>   configurations.
> >>>
> >>> Without this commit the behavior for traffic from 10.0.0.1 to 10.0.0.5
> >>> is unpredictable. Depending on the order of operations traffic might
be
> >>> dropped or allowed.
> >>>
> >>> It's also quite hard to force the CMS to ensure that such match
overlaps
> >>> never occur.
> >>>
> >>> To address this issue we now resolve conflicts between flows with the
> >>> same match and different actions by giving precedence to less
> >>> restrictive flows. This means that if the installed flow has action
> >>> "conjunction" and the desired flow doesn't then we prefer the desired
> >>> flow. Similarly, if the desired flow has action "conjunction" and the
> >>> installed flow doesn't then we prefer the already installed flow.
> >>>
> >>> CC: Daniel Alvarez <dalvarez@redhat.com <mailto:dalvarez@redhat.com>>
> >>> CC: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>>
> >>> Reported-at: https://bugzilla.redhat.com/1871931
> >>> Acked-by: Mark Michelson <mmichels@redhat.com
> >> <mailto:mmichels@redhat.com>>
> >>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
> >> <mailto:dceara@redhat.com>>
> >>> ---
> >>> v4:
> >>> - Address Han's comments:
> >>>   - make sure only flows with action conjunction are combined.
> >>> v3:
> >>> - Add Mark's ack.
> >>> - Add last missing pcap check in the test.
> >>> v2:
> >>> - Address Han's comments:
> >>>   - Do not delete desired flow that cannot be merged, it might be
> >>>     installed later.
> >>>   - Fix typos in the commit log.
> >>> - Update the test to check the OVS flows.
> >>> ---
> >>>  controller/ofctrl.c | 163 ++++++++++++++++++++++++++++++++++++-------
> >>>  tests/ovn.at <http://ovn.at>        | 195
> >> ++++++++++++++++++++++++++++++++++++++++++++++++++++
> >>>  2 files changed, 332 insertions(+), 26 deletions(-)
> >>>
> >>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
> >>> index 81a00c8..4577413 100644
> >>> --- a/controller/ofctrl.c
> >>> +++ b/controller/ofctrl.c
> >>> @@ -206,6 +206,9 @@ struct installed_flow {
> >>>      struct desired_flow *desired_flow;
> >>>  };
> >>>
> >>> +typedef bool
> >>> +(*desired_flow_match_cb)(const struct desired_flow *candidate,
> >>> +                         const void *arg);
> >>>  static struct desired_flow *desired_flow_alloc(
> >>>      uint8_t table_id,
> >>>      uint16_t priority,
> >>> @@ -214,8 +217,14 @@ static struct desired_flow *desired_flow_alloc(
> >>>      const struct ofpbuf *actions);
> >>>  static struct desired_flow *desired_flow_lookup(
> >>>      struct ovn_desired_flow_table *,
> >>> +    const struct ovn_flow *target);
> >>> +static struct desired_flow *desired_flow_lookup_by_uuid(
> >>
> >> The name "by_uuid" is a little misleading. It sounds like it only looks
> >> uuid. But instead, it still looks up by match which it will also
compare
> >> uuid. How about: desired_flow_lookup_check_uuid?
> >>
> >>> +    struct ovn_desired_flow_table *,
> >>>      const struct ovn_flow *target,
> >>> -    const struct uuid *sb_uuid);
> >>> +    const struct uuid *);
> >>> +static struct desired_flow *desired_flow_lookup_conjunctive(
> >>> +    struct ovn_desired_flow_table *,
> >>> +    const struct ovn_flow *target);
> >>>  static void desired_flow_destroy(struct desired_flow *);
> >>>
> >>>  static struct installed_flow *installed_flow_lookup(
> >>> @@ -916,6 +925,33 @@ link_flow_to_sb(struct ovn_desired_flow_table
> >> *flow_table,
> >>>      ovs_list_insert(&stf->flows, &sfr->flow_list);
> >>>  }
> >>>
> >>> +static bool
> >>> +flow_action_has_conj(const struct ovn_flow *f)
> >>> +{
> >>> +    const struct ofpact *a = NULL;
> >>> +
> >>> +    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
> >>> +        if (a->type == OFPACT_CONJUNCTION) {
> >>> +            return true;
> >>> +        }
> >>> +    }
> >>> +    return false;
> >>> +}
> >>> +
> >>> +static void
> >>> +flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
> >>> +                          const struct ovn_flow *f2)
> >>> +{
> >>> +    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
> >>> +    char *f1_s = ovn_flow_to_string(f1);
> >>> +    char *f2_s = ovn_flow_to_string(f2);
> >>> +
> >>> +    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2:
> >> %s",
> >>> +                 msg, f1_s, f2_s);
> >>> +    free(f1_s);
> >>> +    free(f2_s);
> >>> +}
> >>> +
> >>
> >> In this log it would be better to mention which one is selected. It
> >> would be better not only abstracting the logging into a function but
> >> also the logic of comparing flows and determining which one is
selected.
> >>
> >
> > Ack, sounds better indeed.
> >
> >>>  /* Flow table interfaces to the rest of ovn-controller. */
> >>>
> >>>  /* Adds a flow to 'desired_flows' with the specified 'match' and
> >> 'actions' to
> >>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
> >> ovn_desired_flow_table *flow_table,
> >>>      struct desired_flow *f = desired_flow_alloc(table_id, priority,
> >> cookie,
> >>>                                                  match, actions);
> >>>
> >>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
> >>> +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
> >>>          if (log_duplicate_flow) {
> >>>              static struct vlog_rate_limit rl =
> >> VLOG_RATE_LIMIT_INIT(5, 5);
> >>>              if (!VLOG_DROP_DBG(&rl)) {
> >>> @@ -979,14 +1015,15 @@ ofctrl_add_or_append_flow(struct
> >> ovn_desired_flow_table *desired_flows,
> >>>                            const struct ofpbuf *actions,
> >>>                            const struct uuid *sb_uuid)
> >>>  {
> >>> -    struct desired_flow *f = desired_flow_alloc(table_id, priority,
> >> cookie,
> >>> -                                                match, actions);
> >>> -
> >>>      struct desired_flow *existing;
> >>> -    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
> >>> +    struct desired_flow *f;
> >>> +
> >>> +    f = desired_flow_alloc(table_id, priority, cookie, match,
actions);
> >>> +    existing = desired_flow_lookup_conjunctive(desired_flows,
&f->flow);
> >>>      if (existing) {
> >>> -        /* There's already a flow with this particular match. Append
the
> >>> -         * action to that flow rather than adding a new flow
> >>> +        /* There's already a flow with this particular match and
action
> >>> +         * 'conjunction'. Append the action to that flow rather than
> >>> +         * adding a new flow.
> >>>           */
> >>>          uint64_t compound_stub[64 / 8];
> >>>          struct ofpbuf compound;
> >>> @@ -1225,15 +1262,11 @@ installed_flow_dup(struct desired_flow *src)
> >>>      return dst;
> >>>  }
> >>>
> >>> -/* Finds and returns a desired_flow in 'flow_table' whose key is
> >> identical to
> >>> - * 'target''s key, or NULL if there is none.
> >>> - *
> >>> - * If sb_uuid is not NULL, the function will also check if the found
> >> flow is
> >>> - * referenced by the sb_uuid. */
> >>>  static struct desired_flow *
> >>> -desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> >>> -                    const struct ovn_flow *target,
> >>> -                    const struct uuid *sb_uuid)
> >>> +desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
> >>> +                      const struct ovn_flow *target,
> >>> +                      desired_flow_match_cb match_cb,
> >>> +                      const void *arg)
> >>>  {
> >>>      struct desired_flow *d;
> >>>      HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
> >>> @@ -1242,20 +1275,75 @@ desired_flow_lookup(struct
> >> ovn_desired_flow_table *flow_table,
> >>>          if (f->table_id == target->table_id
> >>>              && f->priority == target->priority
> >>>              && minimatch_equal(&f->match, &target->match)) {
> >>> -            if (!sb_uuid) {
> >>> +
> >>> +            if (!match_cb || match_cb(d, arg)) {
> >>>                  return d;
> >>>              }
> >>> -            struct sb_flow_ref *sfr;
> >>> -            LIST_FOR_EACH (sfr, sb_list, &d->references) {
> >>> -                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> >>> -                    return d;
> >>> -                }
> >>> -            }
> >>>          }
> >>>      }
> >>>      return NULL;
> >>>  }
> >>>
> >>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> >> identical to
> >>> + * 'target''s key, or NULL if there is none.
> >>> + */
> >>> +static struct desired_flow *
> >>> +desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
> >>> +                    const struct ovn_flow *target)
> >>> +{
> >>> +    return desired_flow_lookup__(flow_table, target, NULL, NULL);
> >>> +}
> >>> +
> >>> +static bool
> >>> +flow_lookup_match_uuid(const struct desired_flow *candidate, const
> >> void *arg)
> >>
> >> This function is used as a callback, so it would be better to have _cb
> >> in its name to help code reading, e.g. flow_lookup_cb_match_uuid
> >>
> >
> > Sure.
> >
> >>> +{
> >>> +    const struct uuid *sb_uuid = arg;
> >>> +    struct sb_flow_ref *sfr;
> >>> +
> >>> +    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
> >>> +        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
> >>> +            return true;
> >>> +        }
> >>> +    }
> >>> +    return false;
> >>> +}
> >>> +
> >>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> >> identical to
> >>> + * 'target''s key, or NULL if there is none.
> >>> + *
> >>> + * The function will also check if the found flow is referenced by
the
> >>> + * 'sb_uuid'.
> >>> + */
> >>> +static struct desired_flow *
> >>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table
*flow_table,
> >>> +                            const struct ovn_flow *target,
> >>> +                            const struct uuid *sb_uuid)
> >>> +{
> >>> +    return desired_flow_lookup__(flow_table, target,
> >> flow_lookup_match_uuid,
> >>> +                                 sb_uuid);
> >>> +}
> >>> +
> >>> +static bool
> >>> +flow_lookup_match_conj(const struct desired_flow *candidate,
> >>> +                       const void *arg OVS_UNUSED)
> >>
> >> Same as above of the naming.
> >>
> >
> > Ack.
> >
> >>> +{
> >>> +    return flow_action_has_conj(&candidate->flow);
> >>> +}
> >>> +
> >>> +/* Finds and returns a desired_flow in 'flow_table' whose key is
> >> identical to
> >>> + * 'target''s key, or NULL if there is none.
> >>> + *
> >>> + * The function will only return a matching flow if it contains
action
> >>> + * 'conjunction'.
> >>> + */
> >>> +static struct desired_flow *
> >>> +desired_flow_lookup_conjunctive(struct ovn_desired_flow_table
> >> *flow_table,
> >>> +                                const struct ovn_flow *target)
> >>> +{
> >>> +    return desired_flow_lookup__(flow_table, target,
> >> flow_lookup_match_conj,
> >>> +                                 NULL);
> >>> +}
> >>> +
> >>>  /* Finds and returns an installed_flow in installed_flows whose key
is
> >>>   * identical to 'target''s key, or NULL if there is none. */
> >>>  static struct installed_flow *
> >>> @@ -1653,8 +1741,7 @@ update_installed_flows_by_compare(struct
> >> ovn_desired_flow_table *flow_table,
> >>>      struct installed_flow *i, *next;
> >>>      HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
> >>>          unlink_all_refs_for_installed_flow(i);
> >>> -        struct desired_flow *d =
> >>> -            desired_flow_lookup(flow_table, &i->flow, NULL);
> >>> +        struct desired_flow *d = desired_flow_lookup(flow_table,
> >> &i->flow);
> >>>          if (!d) {
> >>>              /* Installed flow is no longer desirable.  Delete it
from the
> >>>               * switch and from installed_flows. */
> >>> @@ -1687,6 +1774,18 @@ update_installed_flows_by_compare(struct
> >> ovn_desired_flow_table *flow_table,
> >>>              /* Copy 'd' from 'flow_table' to installed_flows. */
> >>>              i = installed_flow_dup(d);
> >>>              hmap_insert(&installed_flows, &i->match_hmap_node,
> >> i->flow.hash);
> >>> +        } else if (i->desired_flow != d) {
> >>> +            /* If a matching installed flow was found but its
actions are
> >>> +             * conflicting with the desired flow actions, we should
chose
> >>> +             * to install the least restrictive one (i.e., no
conjunctive
> >>> +             * action).
> >>> +             */
> >>> +            if (flow_action_has_conj(&i->flow) &&
> >>> +                    !flow_action_has_conj(&d->flow)) {
> >>> +                flow_log_actions_conflict("Use new flow", &i->flow,
> >> &d->flow);
> >>> +                installed_flow_mod(&i->flow, &d->flow, msgs);
> >>> +                ovn_flow_log(&i->flow, "updating installed");
> >>> +            }
> >>
> >> Here is a problem. Before this change, the flow actually installed in
> >> OVS is the one found in the previous loop. Now in this case we change
> >> the flow installed, we should update the i->desired_flow to match the
> >> one selected.
> >>
> >
> > Right, thanks for spotting this.
> >
> >>>          }
> >>>          link_installed_to_desired(i, d);
> >>>      }
> >>> @@ -1817,7 +1916,19 @@ update_installed_flows_by_track(struct
> >> ovn_desired_flow_table *flow_table,
> >>>                  installed_flow_mod(&i->flow, &f->flow, msgs);
> >>>              } else {
> >>>                  /* Adding a new flow that conflicts with an existing
> >> installed
> >>> -                 * flow, so just add it to the link. */
> >>> +                 * flow, so just add it to the link.
> >>> +                 *
> >>> +                 * However, if the existing installed flow is less
> >> restrictive
> >>> +                 * (i.e., no conjunctive action), we should chose it
> >> over the
> >>> +                 * existing installed flow.
> >>> +                 */
> >>> +                if (flow_action_has_conj(&i->flow) &&
> >>> +                        !flow_action_has_conj(&f->flow)) {
> >>> +                    flow_log_actions_conflict("Use new flow",
> >>> +                                              &i->flow, &f->flow);
> >>> +                    ovn_flow_log(&i->flow, "updating installed
> >> (tracked)");
> >>> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
> >>> +                }
> >>
> >> We should make sure it is set as the active flow.
> >>
> >> In addition, in the other branch in this function when the flow is
> >> deleted, we need to use the same criteria to select the flow to be
> >> actively installed. Currently unlink_installed_to_desired() just pick
> >> the first one from the rest of desired_flows in the linked list. This
> >> patch should go through the list and figure out which one should be
> >> selected using the same criteria.
> >>
> >
> > I think I also need to double check the self test. I thought I was
> > covering this case too but I guess I was wrong.
> >
>
> Hi Han,
>
> I've spent some more time thinking about all we discussed here and
> there's another case we didn't cover:
>
> Desired flow ordering can change (due to the order of logical flows in
> the IDL) when a recompute happens so we'd always have to walk the
> desired list flows to select the "least restrictive" one.
>
> I found a better solution which is to ensure that all desired flows
> referring an installed flow are always (partially) sorted in the list.
> This can be easily implemented with O(1) complexity and also makes
> selection of the "next-least-restrictive-flow" O(1).
>
> I had to make some changes to the existing ofctrl code so I sent v5 as a
> series to make it easier to review independent changes:
>
> http://patchwork.ozlabs.org/project/ovn/list/?series=207123
>
> Thanks,
> Dumitru
>
Thanks Dumitru. After reviewing roughly the new series I have some thoughts
on the approach. It does make the next conflict flow selection O(1) but it
seems to be an optimization that IMHO not really necessary while making the
code more complex. The scenario is when we have conflict flows, which of
course can happen but the number of conflicting flows shouldn't be huge. If
a user configures hundreds or thousands of ACLs that overlap with each
other with the same priority that is crazy and something fundamentally
wrong. In the real world I am expecting 2 - 3 items in the list in most
cases. So I was actually suggesting to traverse the desired_flow list when
selecting the next active flow (on top of your v4). The operation is O(n)
but it should be completely fine if we know n is extremely small (even 100
items . That would keep the code easier to read and maintain - less
implications and constraints to keep in mind. (Of course if we find such
optimization really needed in the future it can always be changed.)
Dumitru Ceara Oct. 12, 2020, 10:16 a.m. UTC | #6
On 10/11/20 9:40 PM, Han Zhou wrote:
> 
> 
> On Sun, Oct 11, 2020 at 5:14 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>> wrote:
>> 
>> On 10/6/20 10:30 AM, Dumitru Ceara wrote:
>>> On 10/2/20 10:28 PM, Han Zhou wrote:
>>>> 
>>>> Hi Dumitru,
>>>> 
>>> 
>>> Hi Han,
>>> 
>>>> Thanks for the revision. It looks good overall. The major
>>>> problems left are: 1. it missed updating the active
>>>> desired_flow in the installed_flow. 2. when a tracked flow
>>>> deletion is handled, if there are other desired flows linked to
>>>> the same installed flow, it should use the same criteria to
>>>> decide which flow should become active from the candidate
>>>> flows.
>>>> 
>>> 
>>> I see, you're right, thanks. I'll fix it in the next revision.
>>> 
>>>> I also noticed 2 problems of the existing code while reviewing
>>>> this patch. I submitted 2 patches: 1. 
>>>> https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
>>
>>>> 
>> 2.
>>>> https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
>>
>>>> 
>> 
>>>> 1) is required for your solution to work properly. 2) is not
>>>> directly related but will cause a merge conflict. Please help
>>>> review both since they are closely related to your patch.
>>>> 
>>> 
>>> I'll try to review your patches as soon as possible and I'll
>>> respin mine afterwards.
>>> 
>>>> Please see more detailed comments below.
>>>> 
>>>> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara
>>>> <dceara@redhat.com <mailto:dceara@redhat.com> 
>>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>> wrote:
>>>>> 
>>>>> Until now, in case the ACL configuration generates openflows
>>>>> that have the same match but different actions,
>>>>> ovn-controller was using the following approach: 1. If the
>>>>> flow being added contains conjunctive actions, merge its 
>>>>> actions with the already existing flow. 2. Otherwise, if the
>>>>> flow is being added incrementally 
>>>>> (update_installed_flows_by_track), don't install the new flow
>>>>> but instead keep the old one. 3. Otherwise,
>>>>> (update_installed_flows_by_compare), don't install the new
>>>>> flow but instead keep the old one.
>>>>> 
>>>>> Even though one can argue that having an ACL with a match
>>>>> that includes the match of another ACL is a misconfiguration,
>>>>> it can happen that the users provision OVN like this.
>>>>> Depending on the order of reading and installing the logical
>>>>> flows, the above operations can yield unpredictable results,
>>>>> e.g., allow specific traffic but then after ovn-controller is
>>>>> restarted (or a recompute happens) that specific traffic
>>>>> starts being dropped.
>>>>> 
>>>>> A simple example of ACL configuration is: ovn-nbctl acl-add
>>>>> ls to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.2) &&
>>>>> (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow ovn-nbctl
>>>>> acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow ovn-nbctl
>>>>> acl-add ls to-lport 2 'arp' allow ovn-nbctl acl-add ls
>>>>> to-lport 1 'ip4' drop
>>>>> 
>>>>> This is a pattern used by most CMSs: - define a default deny
>>>>> policy. - punch holes in the default deny policy based on
>>>>> user specific configurations.
>>>>> 
>>>>> Without this commit the behavior for traffic from 10.0.0.1 to
>>>>> 10.0.0.5 is unpredictable. Depending on the order of
>>>>> operations traffic might be dropped or allowed.
>>>>> 
>>>>> It's also quite hard to force the CMS to ensure that such
>>>>> match overlaps never occur.
>>>>> 
>>>>> To address this issue we now resolve conflicts between flows
>>>>> with the same match and different actions by giving
>>>>> precedence to less restrictive flows. This means that if the
>>>>> installed flow has action "conjunction" and the desired flow
>>>>> doesn't then we prefer the desired flow. Similarly, if the
>>>>> desired flow has action "conjunction" and the installed flow
>>>>> doesn't then we prefer the already installed flow.
>>>>> 
>>>>> CC: Daniel Alvarez <dalvarez@redhat.com
>>>>> <mailto:dalvarez@redhat.com> <mailto:dalvarez@redhat.com
>>>>> <mailto:dalvarez@redhat.com>>> CC: Han Zhou <hzhou@ovn.org
>>>>> <mailto:hzhou@ovn.org> <mailto:hzhou@ovn.org
>>>>> <mailto:hzhou@ovn.org>>> Reported-at:
>>>>> https://bugzilla.redhat.com/1871931 Acked-by: Mark Michelson
>>>>> <mmichels@redhat.com <mailto:mmichels@redhat.com>
>>>> <mailto:mmichels@redhat.com <mailto:mmichels@redhat.com>>>
>>>>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
>>>>> <mailto:dceara@redhat.com>
>>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>>
>>>>> --- v4: - Address Han's comments: - make sure only flows with
>>>>> action conjunction are combined. v3: - Add Mark's ack. - Add
>>>>> last missing pcap check in the test. v2: - Address Han's
>>>>> comments: - Do not delete desired flow that cannot be merged,
>>>>> it might be installed later. - Fix typos in the commit log. -
>>>>> Update the test to check the OVS flows. --- 
>>>>> controller/ofctrl.c | 163
>>>>> ++++++++++++++++++++++++++++++++++++------- tests/ovn.at
>>>>> <http://ovn.at> <http://ovn.at>        | 195
>>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>>> 2 files changed, 332 insertions(+), 26 deletions(-)
>>>>> 
>>>>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c index
>>>>> 81a00c8..4577413 100644 --- a/controller/ofctrl.c +++
>>>>> b/controller/ofctrl.c @@ -206,6 +206,9 @@ struct
>>>>> installed_flow { struct desired_flow *desired_flow; };
>>>>> 
>>>>> +typedef bool +(*desired_flow_match_cb)(const struct
>>>>> desired_flow *candidate, +                         const void
>>>>> *arg); static struct desired_flow *desired_flow_alloc( 
>>>>> uint8_t table_id, uint16_t priority, @@ -214,8 +217,14 @@
>>>>> static struct desired_flow *desired_flow_alloc( const struct
>>>>> ofpbuf *actions); static struct desired_flow
>>>>> *desired_flow_lookup( struct ovn_desired_flow_table *, +
>>>>> const struct ovn_flow *target); +static struct desired_flow
>>>>> *desired_flow_lookup_by_uuid(
>>>> 
>>>> The name "by_uuid" is a little misleading. It sounds like it
>>>> only looks uuid. But instead, it still looks up by match which
>>>> it will also compare uuid. How about:
>>>> desired_flow_lookup_check_uuid?
>>>> 
>>>>> +    struct ovn_desired_flow_table *, const struct ovn_flow
>>>>> *target, -    const struct uuid *sb_uuid); +    const struct
>>>>> uuid *); +static struct desired_flow
>>>>> *desired_flow_lookup_conjunctive( +    struct
>>>>> ovn_desired_flow_table *, +    const struct ovn_flow
>>>>> *target); static void desired_flow_destroy(struct
>>>>> desired_flow *);
>>>>> 
>>>>> static struct installed_flow *installed_flow_lookup( @@
>>>>> -916,6 +925,33 @@ link_flow_to_sb(struct
>>>>> ovn_desired_flow_table
>>>> *flow_table,
>>>>> ovs_list_insert(&stf->flows, &sfr->flow_list); }
>>>>> 
>>>>> +static bool +flow_action_has_conj(const struct ovn_flow *f) 
>>>>> +{ +    const struct ofpact *a = NULL; + +    OFPACT_FOR_EACH
>>>>> (a, f->ofpacts, f->ofpacts_len) { +        if (a->type ==
>>>>> OFPACT_CONJUNCTION) { +            return true; +        } +
>>>>> } +    return false; +} + +static void 
>>>>> +flow_log_actions_conflict(const char *msg, const struct
>>>>> ovn_flow *f1, +                          const struct
>>>>> ovn_flow *f2) +{ +    static struct vlog_rate_limit rl =
>>>>> VLOG_RATE_LIMIT_INIT(5, 1); +    char *f1_s =
>>>>> ovn_flow_to_string(f1); +    char *f2_s =
>>>>> ovn_flow_to_string(f2); + +    VLOG_WARN_RL(&rl, "Flow
>>>>> actions conflict: %s, flow-1: %s, flow-2:
>>>> %s",
>>>>> +                 msg, f1_s, f2_s); +    free(f1_s); +
>>>>> free(f2_s); +} +
>>>> 
>>>> In this log it would be better to mention which one is
>>>> selected. It would be better not only abstracting the logging
>>>> into a function but also the logic of comparing flows and
>>>> determining which one is selected.
>>>> 
>>> 
>>> Ack, sounds better indeed.
>>> 
>>>>> /* Flow table interfaces to the rest of ovn-controller. */
>>>>> 
>>>>> /* Adds a flow to 'desired_flows' with the specified 'match'
>>>>> and
>>>> 'actions' to
>>>>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
>>>> ovn_desired_flow_table *flow_table,
>>>>> struct desired_flow *f = desired_flow_alloc(table_id,
>>>>> priority,
>>>> cookie,
>>>>> match, actions);
>>>>> 
>>>>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid))
>>>>> { +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow,
>>>>> sb_uuid)) { if (log_duplicate_flow) { static struct
>>>>> vlog_rate_limit rl =
>>>> VLOG_RATE_LIMIT_INIT(5, 5);
>>>>> if (!VLOG_DROP_DBG(&rl)) { @@ -979,14 +1015,15 @@
>>>>> ofctrl_add_or_append_flow(struct
>>>> ovn_desired_flow_table *desired_flows,
>>>>> const struct ofpbuf *actions, const struct uuid *sb_uuid) { -
>>>>> struct desired_flow *f = desired_flow_alloc(table_id,
>>>>> priority,
>>>> cookie,
>>>>> -                                                match,
>>>>> actions); - struct desired_flow *existing; -    existing =
>>>>> desired_flow_lookup(desired_flows, &f->flow, NULL); +
>>>>> struct desired_flow *f; + +    f =
>>>>> desired_flow_alloc(table_id, priority, cookie, match,
>>>>> actions); +    existing =
>>>>> desired_flow_lookup_conjunctive(desired_flows, &f->flow); if
>>>>> (existing) { -        /* There's already a flow with this
>>>>> particular match. Append the -         * action to that flow
>>>>> rather than adding a new flow +        /* There's already a
>>>>> flow with this particular match and action +         *
>>>>> 'conjunction'. Append the action to that flow rather than +
>>>>> * adding a new flow. */ uint64_t compound_stub[64 / 8]; 
>>>>> struct ofpbuf compound; @@ -1225,15 +1262,11 @@
>>>>> installed_flow_dup(struct desired_flow *src) return dst; }
>>>>> 
>>>>> -/* Finds and returns a desired_flow in 'flow_table' whose
>>>>> key is
>>>> identical to
>>>>> - * 'target''s key, or NULL if there is none. - * - * If
>>>>> sb_uuid is not NULL, the function will also check if the
>>>>> found
>>>> flow is
>>>>> - * referenced by the sb_uuid. */ static struct desired_flow
>>>>> * -desired_flow_lookup(struct ovn_desired_flow_table
>>>>> *flow_table, -                    const struct ovn_flow
>>>>> *target, -                    const struct uuid *sb_uuid) 
>>>>> +desired_flow_lookup__(struct ovn_desired_flow_table
>>>>> *flow_table, +                      const struct ovn_flow
>>>>> *target, +                      desired_flow_match_cb
>>>>> match_cb, +                      const void *arg) { struct
>>>>> desired_flow *d; HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node,
>>>>> target->hash, @@ -1242,20 +1275,75 @@
>>>>> desired_flow_lookup(struct
>>>> ovn_desired_flow_table *flow_table,
>>>>> if (f->table_id == target->table_id && f->priority ==
>>>>> target->priority && minimatch_equal(&f->match,
>>>>> &target->match)) { -            if (!sb_uuid) { + +
>>>>> if (!match_cb || match_cb(d, arg)) { return d; } -
>>>>> struct sb_flow_ref *sfr; -            LIST_FOR_EACH (sfr,
>>>>> sb_list, &d->references) { -                if
>>>>> (uuid_equals(sb_uuid, &sfr->sb_uuid)) { -
>>>>> return d; -                } -            } } } return NULL; 
>>>>> }
>>>>> 
>>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
>>>>> key is
>>>> identical to
>>>>> + * 'target''s key, or NULL if there is none. + */ +static
>>>>> struct desired_flow * +desired_flow_lookup(struct
>>>>> ovn_desired_flow_table *flow_table, +
>>>>> const struct ovn_flow *target) +{ +    return
>>>>> desired_flow_lookup__(flow_table, target, NULL, NULL); +} + 
>>>>> +static bool +flow_lookup_match_uuid(const struct
>>>>> desired_flow *candidate, const
>>>> void *arg)
>>>> 
>>>> This function is used as a callback, so it would be better to
>>>> have _cb in its name to help code reading, e.g.
>>>> flow_lookup_cb_match_uuid
>>>> 
>>> 
>>> Sure.
>>> 
>>>>> +{ +    const struct uuid *sb_uuid = arg; +    struct
>>>>> sb_flow_ref *sfr; + +    LIST_FOR_EACH (sfr, sb_list,
>>>>> &candidate->references) { +        if (uuid_equals(sb_uuid,
>>>>> &sfr->sb_uuid)) { +            return true; +        } +
>>>>> } +    return false; +} + +/* Finds and returns a
>>>>> desired_flow in 'flow_table' whose key is
>>>> identical to
>>>>> + * 'target''s key, or NULL if there is none. + * + * The
>>>>> function will also check if the found flow is referenced by
>>>>> the + * 'sb_uuid'. + */ +static struct desired_flow * 
>>>>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table
>>>>> *flow_table, +                            const struct
>>>>> ovn_flow *target, +                            const struct
>>>>> uuid *sb_uuid) +{ +    return
>>>>> desired_flow_lookup__(flow_table, target,
>>>> flow_lookup_match_uuid,
>>>>> +                                 sb_uuid); +} + +static
>>>>> bool +flow_lookup_match_conj(const struct desired_flow
>>>>> *candidate, +                       const void *arg
>>>>> OVS_UNUSED)
>>>> 
>>>> Same as above of the naming.
>>>> 
>>> 
>>> Ack.
>>> 
>>>>> +{ +    return flow_action_has_conj(&candidate->flow); +} + 
>>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
>>>>> key is
>>>> identical to
>>>>> + * 'target''s key, or NULL if there is none. + * + * The
>>>>> function will only return a matching flow if it contains
>>>>> action + * 'conjunction'. + */ +static struct desired_flow * 
>>>>> +desired_flow_lookup_conjunctive(struct
>>>>> ovn_desired_flow_table
>>>> *flow_table,
>>>>> +                                const struct ovn_flow
>>>>> *target) +{ +    return desired_flow_lookup__(flow_table,
>>>>> target,
>>>> flow_lookup_match_conj,
>>>>> +                                 NULL); +} + /* Finds and
>>>>> returns an installed_flow in installed_flows whose key is *
>>>>> identical to 'target''s key, or NULL if there is none. */ 
>>>>> static struct installed_flow * @@ -1653,8 +1741,7 @@
>>>>> update_installed_flows_by_compare(struct
>>>> ovn_desired_flow_table *flow_table,
>>>>> struct installed_flow *i, *next; HMAP_FOR_EACH_SAFE (i, next,
>>>>> match_hmap_node, &installed_flows) { 
>>>>> unlink_all_refs_for_installed_flow(i); -        struct
>>>>> desired_flow *d = -
>>>>> desired_flow_lookup(flow_table, &i->flow, NULL); +
>>>>> struct desired_flow *d = desired_flow_lookup(flow_table,
>>>> &i->flow);
>>>>> if (!d) { /* Installed flow is no longer desirable.  Delete
>>>>> it from the * switch and from installed_flows. */ @@ -1687,6
>>>>> +1774,18 @@ update_installed_flows_by_compare(struct
>>>> ovn_desired_flow_table *flow_table,
>>>>> /* Copy 'd' from 'flow_table' to installed_flows. */ i =
>>>>> installed_flow_dup(d); hmap_insert(&installed_flows,
>>>>> &i->match_hmap_node,
>>>> i->flow.hash);
>>>>> +        } else if (i->desired_flow != d) { +            /*
>>>>> If a matching installed flow was found but its actions are +
>>>>> * conflicting with the desired flow actions, we should chose 
>>>>> +             * to install the least restrictive one (i.e.,
>>>>> no conjunctive +             * action). +             */ +
>>>>> if (flow_action_has_conj(&i->flow) && +
>>>>> !flow_action_has_conj(&d->flow)) { +
>>>>> flow_log_actions_conflict("Use new flow", &i->flow,
>>>> &d->flow);
>>>>> +                installed_flow_mod(&i->flow, &d->flow,
>>>>> msgs); +                ovn_flow_log(&i->flow, "updating
>>>>> installed"); +            }
>>>> 
>>>> Here is a problem. Before this change, the flow actually
>>>> installed in OVS is the one found in the previous loop. Now in
>>>> this case we change the flow installed, we should update the
>>>> i->desired_flow to match the one selected.
>>>> 
>>> 
>>> Right, thanks for spotting this.
>>> 
>>>>> } link_installed_to_desired(i, d); } @@ -1817,7 +1916,19 @@
>>>>> update_installed_flows_by_track(struct
>>>> ovn_desired_flow_table *flow_table,
>>>>> installed_flow_mod(&i->flow, &f->flow, msgs); } else { /*
>>>>> Adding a new flow that conflicts with an existing
>>>> installed
>>>>> -                 * flow, so just add it to the link. */ +
>>>>> * flow, so just add it to the link. +                 * +
>>>>> * However, if the existing installed flow is less
>>>> restrictive
>>>>> +                 * (i.e., no conjunctive action), we should
>>>>> chose it
>>>> over the
>>>>> +                 * existing installed flow. +
>>>>> */ +                if (flow_action_has_conj(&i->flow) && +
>>>>> !flow_action_has_conj(&f->flow)) { +
>>>>> flow_log_actions_conflict("Use new flow", +
>>>>> &i->flow, &f->flow); +
>>>>> ovn_flow_log(&i->flow, "updating installed
>>>> (tracked)");
>>>>> +                    installed_flow_mod(&i->flow, &f->flow,
>>>>> msgs); +                }
>>>> 
>>>> We should make sure it is set as the active flow.
>>>> 
>>>> In addition, in the other branch in this function when the flow
>>>> is deleted, we need to use the same criteria to select the flow
>>>> to be actively installed. Currently
>>>> unlink_installed_to_desired() just pick the first one from the
>>>> rest of desired_flows in the linked list. This patch should go
>>>> through the list and figure out which one should be selected
>>>> using the same criteria.
>>>> 
>>> 
>>> I think I also need to double check the self test. I thought I
>>> was covering this case too but I guess I was wrong.
>>> 
>> 
>> Hi Han,
>> 
>> I've spent some more time thinking about all we discussed here and 
>> there's another case we didn't cover:
>> 
>> Desired flow ordering can change (due to the order of logical flows
>> in the IDL) when a recompute happens so we'd always have to walk
>> the desired list flows to select the "least restrictive" one.
>> 
>> I found a better solution which is to ensure that all desired
>> flows referring an installed flow are always (partially) sorted in
>> the list. This can be easily implemented with O(1) complexity and
>> also makes selection of the "next-least-restrictive-flow" O(1).
>> 
>> I had to make some changes to the existing ofctrl code so I sent v5
>> as a series to make it easier to review independent changes:
>> 
>> http://patchwork.ozlabs.org/project/ovn/list/?series=207123
>> 
>> Thanks, Dumitru
>> 
> Thanks Dumitru. After reviewing roughly the new series I have some
> thoughts on the approach. It does make the next conflict flow
> selection O(1) but it seems to be an optimization that IMHO not
> really necessary while making the code more complex. The scenario is
> when we have conflict flows, which of course can happen but the
> number of conflicting flows shouldn't be huge. If a user configures
> hundreds or thousands of ACLs that overlap with each other with the
> same priority that is crazy and something fundamentally wrong. In the
> real world I am expecting 2 - 3 items in the list in most cases. So I
> was actually suggesting to traverse the desired_flow list when
> selecting the next active flow (on top of your v4). The operation is
> O(n) but it should be completely fine if we know n is extremely small
> (even 100 items . That would keep the code easier to read and
> maintain - less implications and constraints to keep in mind. (Of
> course if we find such optimization really needed in the future it
> can always be changed.)

Hi Han,

I think there might be some confusion.  Just to make sure we're discussing
the same problem, considering the following "desired flows":

a. match=M, action=conjunction(..)
b. match=M, action=allow
c. match=M, action=drop

Let's assume flows are installed incrementally in the following order:
a -> b -> c

When flow "b" is added to the "installed" flow, it should replace "a" as
active flow because "b" is less restrictive.  When flow "c" is incrementally
added we can decide if it should replace "b" or not.  Let's assume we don't
replace "b".

At this point, installed flow "i" looks like this:
- desired_flow = "b"
- desired_refs = ["a", "b", "c"]

If a recompute happens, the order in which flows are processed is "random",
depending on the logical flow UUIDs.  Let's say:
a -> c -> b

When flow "c" is processed and added to the "installed" flow, it should
replace "a" as active flow because "c" is less restrictive.  When flow "b" is
processed, using the same logic as above we'll not replace "c".

At this point, installed flow "i" looks like this:
- desired_flow = "c"
- desired_refs = ["a", "c", "b"]

The problem with this is that we're now dropping all traffic that matches
M while before the recompute we were allowing it.

To solve this we can do what you suggested and select the active flow
such that we always give precedence to "allow" over "drop" over "conjunction".
Please see the incremental diff below (it applies on top of patch 1 of v5
[1]).

However, this is basically just an inefficient implementation of a partial
ordering of desired flows within installed_flow->desired_refs.  Moreover, in
my opinion, this doesn't differ much from the implementation where we actually
maintain the sorted list [2].

Do you still think not maintaining the sorted list is less complex?

Also, in any case, I still think patches 2 and 3 in v5 are beneficial for
general code clarity because:
- we don't really need an explicit reference to "desired_flow" if we always
  consider the first element in the list to be the active flow.  That removes
  one appearance of the "desired_flow" identifier in ofctrl.c where in my
  opinion it's already easy to confuse what "desired_flow" we're dealing with.
  An "installed_flow_get_active()" API can hide this implementation and let the
  reader focus on other details.
- we don't really need to use the link_installed_to_desired() and
  unlink_installed_to_desired() APIs that change the order of desired_flows
  when merging opposite changes in merge_tracked_flows().  ovs_list_replace() 
  is enough for that.  That makes the code easier to debug because we don't
  need to rely anymore on constructs like:
            bool del_f_was_active = desired_flow_is_active(del_f);
            [...] /* Do something that might change the order of flows. */
            if (del_f_was_active) {
                desired_flow_set_active(f);
            }

Regards,
Dumitru

[1] http://patchwork.ozlabs.org/project/ovn/patch/20201011120522.3374.57876.stgit@dceara.remote.csb/
[2] http://patchwork.ozlabs.org/project/ovn/patch/20201011120607.3374.49659.stgit@dceara.remote.csb/

diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index 24b55fc..9af9f1c 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -828,6 +828,51 @@ flow_action_has_conj(const struct ovn_flow *f)
     return false;
 }
 
+static bool
+flow_action_has_drop(const struct ovn_flow *f)
+{
+    return f->ofpacts_len == 0;
+}
+
+static void
+installed_flow_select_active(struct installed_flow *i)
+{
+    if (ovs_list_is_empty(&i->desired_refs)) {
+        i->desired_flow = NULL;
+        return;
+    }
+
+    struct desired_flow *d;
+    struct desired_flow *d_conj = NULL;
+    struct desired_flow *d_drop = NULL;
+    struct desired_flow *d_allow = NULL;
+
+    LIST_FOR_EACH (d, installed_ref_list_node, &i->desired_refs) {
+        if (flow_action_has_conj(&d->flow)) {
+            if (!d_conj) {
+                d_conj = d;
+            }
+        } else if (flow_action_has_drop(&d->flow)) {
+            if (!d_drop) {
+                d_drop = d;
+            }
+        } else {
+            if (!d_allow) {
+                d_allow = d;
+            }
+        }
+    }
+
+    /* Prefer allow action over block over conjunction. */
+    if (d_allow) {
+        i->desired_flow = d_allow;
+    } else if (d_drop) {
+        i->desired_flow = d_drop;
+    } else {
+        i->desired_flow = d_conj;
+    }
+}
+
 /* Adds the desired flow to the list of desired flows that have same match
  * conditions as the installed flow.
  *
@@ -840,12 +885,10 @@ static void
 link_installed_to_desired(struct installed_flow *i, struct desired_flow *d)
 {
     ovs_assert(i->desired_flow != d);
-    if (ovs_list_is_empty(&i->desired_refs)) {
-        ovs_assert(!i->desired_flow);
-        i->desired_flow = d;
-    }
     ovs_list_insert(&i->desired_refs, &d->installed_ref_list_node);
     d->installed_flow = i;
+
+    installed_flow_select_active(i);
 }
 
 static void
@@ -855,12 +898,7 @@ unlink_installed_to_desired(struct installed_flow *i, struct desired_flow *d)
     ovs_assert(d && d->installed_flow == i);
     ovs_list_remove(&d->installed_ref_list_node);
     d->installed_flow = NULL;
-    if (i->desired_flow == d) {
-        i->desired_flow = ovs_list_is_empty(&i->desired_refs) ? NULL :
-            CONTAINER_OF(ovs_list_front(&i->desired_refs),
-                         struct desired_flow,
-                         installed_ref_list_node);
-    }
+    installed_flow_select_active(i);
 }
 
 static void
@@ -1789,6 +1827,9 @@ update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
             /* This is a desired_flow that conflicts with one installed
              * previously but not linked yet. */
             link_installed_to_desired(i, d);
+            if (desired_flow_is_active(d)) {
+                installed_flow_mod(&i->flow, &d->flow, msgs);
+            }
         }
     }
 }
@@ -1926,6 +1967,9 @@ update_installed_flows_by_track(struct ovn_desired_flow_table *flow_table,
                 /* Adding a new flow that conflicts with an existing installed
                  * flow, so just add it to the link. */
                 link_installed_to_desired(i, f);
+                if (desired_flow_is_active(f)) {
+                    installed_flow_mod(&i->flow, &f->flow, msgs);
+                }
             }
             /* The track_list_node emptyness is used to check if the node is
              * already added to track list, so initialize it again here. */
Han Zhou Oct. 13, 2020, 6:58 a.m. UTC | #7
On Mon, Oct 12, 2020 at 3:16 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
>
> On 10/11/20 9:40 PM, Han Zhou wrote:
> >
> >
> > On Sun, Oct 11, 2020 at 5:14 AM Dumitru Ceara <dceara@redhat.com
> > <mailto:dceara@redhat.com>> wrote:
> >>
> >> On 10/6/20 10:30 AM, Dumitru Ceara wrote:
> >>> On 10/2/20 10:28 PM, Han Zhou wrote:
> >>>>
> >>>> Hi Dumitru,
> >>>>
> >>>
> >>> Hi Han,
> >>>
> >>>> Thanks for the revision. It looks good overall. The major
> >>>> problems left are: 1. it missed updating the active
> >>>> desired_flow in the installed_flow. 2. when a tracked flow
> >>>> deletion is handled, if there are other desired flows linked to
> >>>> the same installed flow, it should use the same criteria to
> >>>> decide which flow should become active from the candidate
> >>>> flows.
> >>>>
> >>>
> >>> I see, you're right, thanks. I'll fix it in the next revision.
> >>>
> >>>> I also noticed 2 problems of the existing code while reviewing
> >>>> this patch. I submitted 2 patches: 1.
> >>>>
https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
> >>
> >>>>
> >> 2.
> >>>>
https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
> >>
> >>>>
> >>
> >>>> 1) is required for your solution to work properly. 2) is not
> >>>> directly related but will cause a merge conflict. Please help
> >>>> review both since they are closely related to your patch.
> >>>>
> >>>
> >>> I'll try to review your patches as soon as possible and I'll
> >>> respin mine afterwards.
> >>>
> >>>> Please see more detailed comments below.
> >>>>
> >>>> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara
> >>>> <dceara@redhat.com <mailto:dceara@redhat.com>
> >>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>> wrote:
> >>>>>
> >>>>> Until now, in case the ACL configuration generates openflows
> >>>>> that have the same match but different actions,
> >>>>> ovn-controller was using the following approach: 1. If the
> >>>>> flow being added contains conjunctive actions, merge its
> >>>>> actions with the already existing flow. 2. Otherwise, if the
> >>>>> flow is being added incrementally
> >>>>> (update_installed_flows_by_track), don't install the new flow
> >>>>> but instead keep the old one. 3. Otherwise,
> >>>>> (update_installed_flows_by_compare), don't install the new
> >>>>> flow but instead keep the old one.
> >>>>>
> >>>>> Even though one can argue that having an ACL with a match
> >>>>> that includes the match of another ACL is a misconfiguration,
> >>>>> it can happen that the users provision OVN like this.
> >>>>> Depending on the order of reading and installing the logical
> >>>>> flows, the above operations can yield unpredictable results,
> >>>>> e.g., allow specific traffic but then after ovn-controller is
> >>>>> restarted (or a recompute happens) that specific traffic
> >>>>> starts being dropped.
> >>>>>
> >>>>> A simple example of ACL configuration is: ovn-nbctl acl-add
> >>>>> ls to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.2) &&
> >>>>> (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow ovn-nbctl
> >>>>> acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow ovn-nbctl
> >>>>> acl-add ls to-lport 2 'arp' allow ovn-nbctl acl-add ls
> >>>>> to-lport 1 'ip4' drop
> >>>>>
> >>>>> This is a pattern used by most CMSs: - define a default deny
> >>>>> policy. - punch holes in the default deny policy based on
> >>>>> user specific configurations.
> >>>>>
> >>>>> Without this commit the behavior for traffic from 10.0.0.1 to
> >>>>> 10.0.0.5 is unpredictable. Depending on the order of
> >>>>> operations traffic might be dropped or allowed.
> >>>>>
> >>>>> It's also quite hard to force the CMS to ensure that such
> >>>>> match overlaps never occur.
> >>>>>
> >>>>> To address this issue we now resolve conflicts between flows
> >>>>> with the same match and different actions by giving
> >>>>> precedence to less restrictive flows. This means that if the
> >>>>> installed flow has action "conjunction" and the desired flow
> >>>>> doesn't then we prefer the desired flow. Similarly, if the
> >>>>> desired flow has action "conjunction" and the installed flow
> >>>>> doesn't then we prefer the already installed flow.
> >>>>>
> >>>>> CC: Daniel Alvarez <dalvarez@redhat.com
> >>>>> <mailto:dalvarez@redhat.com> <mailto:dalvarez@redhat.com
> >>>>> <mailto:dalvarez@redhat.com>>> CC: Han Zhou <hzhou@ovn.org
> >>>>> <mailto:hzhou@ovn.org> <mailto:hzhou@ovn.org
> >>>>> <mailto:hzhou@ovn.org>>> Reported-at:
> >>>>> https://bugzilla.redhat.com/1871931 Acked-by: Mark Michelson
> >>>>> <mmichels@redhat.com <mailto:mmichels@redhat.com>
> >>>> <mailto:mmichels@redhat.com <mailto:mmichels@redhat.com>>>
> >>>>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
> >>>>> <mailto:dceara@redhat.com>
> >>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>>
> >>>>> --- v4: - Address Han's comments: - make sure only flows with
> >>>>> action conjunction are combined. v3: - Add Mark's ack. - Add
> >>>>> last missing pcap check in the test. v2: - Address Han's
> >>>>> comments: - Do not delete desired flow that cannot be merged,
> >>>>> it might be installed later. - Fix typos in the commit log. -
> >>>>> Update the test to check the OVS flows. ---
> >>>>> controller/ofctrl.c | 163
> >>>>> ++++++++++++++++++++++++++++++++++++------- tests/ovn.at
> >>>>> <http://ovn.at> <http://ovn.at>        | 195
> >>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++
> >>>>> 2 files changed, 332 insertions(+), 26 deletions(-)
> >>>>>
> >>>>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c index
> >>>>> 81a00c8..4577413 100644 --- a/controller/ofctrl.c +++
> >>>>> b/controller/ofctrl.c @@ -206,6 +206,9 @@ struct
> >>>>> installed_flow { struct desired_flow *desired_flow; };
> >>>>>
> >>>>> +typedef bool +(*desired_flow_match_cb)(const struct
> >>>>> desired_flow *candidate, +                         const void
> >>>>> *arg); static struct desired_flow *desired_flow_alloc(
> >>>>> uint8_t table_id, uint16_t priority, @@ -214,8 +217,14 @@
> >>>>> static struct desired_flow *desired_flow_alloc( const struct
> >>>>> ofpbuf *actions); static struct desired_flow
> >>>>> *desired_flow_lookup( struct ovn_desired_flow_table *, +
> >>>>> const struct ovn_flow *target); +static struct desired_flow
> >>>>> *desired_flow_lookup_by_uuid(
> >>>>
> >>>> The name "by_uuid" is a little misleading. It sounds like it
> >>>> only looks uuid. But instead, it still looks up by match which
> >>>> it will also compare uuid. How about:
> >>>> desired_flow_lookup_check_uuid?
> >>>>
> >>>>> +    struct ovn_desired_flow_table *, const struct ovn_flow
> >>>>> *target, -    const struct uuid *sb_uuid); +    const struct
> >>>>> uuid *); +static struct desired_flow
> >>>>> *desired_flow_lookup_conjunctive( +    struct
> >>>>> ovn_desired_flow_table *, +    const struct ovn_flow
> >>>>> *target); static void desired_flow_destroy(struct
> >>>>> desired_flow *);
> >>>>>
> >>>>> static struct installed_flow *installed_flow_lookup( @@
> >>>>> -916,6 +925,33 @@ link_flow_to_sb(struct
> >>>>> ovn_desired_flow_table
> >>>> *flow_table,
> >>>>> ovs_list_insert(&stf->flows, &sfr->flow_list); }
> >>>>>
> >>>>> +static bool +flow_action_has_conj(const struct ovn_flow *f)
> >>>>> +{ +    const struct ofpact *a = NULL; + +    OFPACT_FOR_EACH
> >>>>> (a, f->ofpacts, f->ofpacts_len) { +        if (a->type ==
> >>>>> OFPACT_CONJUNCTION) { +            return true; +        } +
> >>>>> } +    return false; +} + +static void
> >>>>> +flow_log_actions_conflict(const char *msg, const struct
> >>>>> ovn_flow *f1, +                          const struct
> >>>>> ovn_flow *f2) +{ +    static struct vlog_rate_limit rl =
> >>>>> VLOG_RATE_LIMIT_INIT(5, 1); +    char *f1_s =
> >>>>> ovn_flow_to_string(f1); +    char *f2_s =
> >>>>> ovn_flow_to_string(f2); + +    VLOG_WARN_RL(&rl, "Flow
> >>>>> actions conflict: %s, flow-1: %s, flow-2:
> >>>> %s",
> >>>>> +                 msg, f1_s, f2_s); +    free(f1_s); +
> >>>>> free(f2_s); +} +
> >>>>
> >>>> In this log it would be better to mention which one is
> >>>> selected. It would be better not only abstracting the logging
> >>>> into a function but also the logic of comparing flows and
> >>>> determining which one is selected.
> >>>>
> >>>
> >>> Ack, sounds better indeed.
> >>>
> >>>>> /* Flow table interfaces to the rest of ovn-controller. */
> >>>>>
> >>>>> /* Adds a flow to 'desired_flows' with the specified 'match'
> >>>>> and
> >>>> 'actions' to
> >>>>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
> >>>> ovn_desired_flow_table *flow_table,
> >>>>> struct desired_flow *f = desired_flow_alloc(table_id,
> >>>>> priority,
> >>>> cookie,
> >>>>> match, actions);
> >>>>>
> >>>>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid))
> >>>>> { +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow,
> >>>>> sb_uuid)) { if (log_duplicate_flow) { static struct
> >>>>> vlog_rate_limit rl =
> >>>> VLOG_RATE_LIMIT_INIT(5, 5);
> >>>>> if (!VLOG_DROP_DBG(&rl)) { @@ -979,14 +1015,15 @@
> >>>>> ofctrl_add_or_append_flow(struct
> >>>> ovn_desired_flow_table *desired_flows,
> >>>>> const struct ofpbuf *actions, const struct uuid *sb_uuid) { -
> >>>>> struct desired_flow *f = desired_flow_alloc(table_id,
> >>>>> priority,
> >>>> cookie,
> >>>>> -                                                match,
> >>>>> actions); - struct desired_flow *existing; -    existing =
> >>>>> desired_flow_lookup(desired_flows, &f->flow, NULL); +
> >>>>> struct desired_flow *f; + +    f =
> >>>>> desired_flow_alloc(table_id, priority, cookie, match,
> >>>>> actions); +    existing =
> >>>>> desired_flow_lookup_conjunctive(desired_flows, &f->flow); if
> >>>>> (existing) { -        /* There's already a flow with this
> >>>>> particular match. Append the -         * action to that flow
> >>>>> rather than adding a new flow +        /* There's already a
> >>>>> flow with this particular match and action +         *
> >>>>> 'conjunction'. Append the action to that flow rather than +
> >>>>> * adding a new flow. */ uint64_t compound_stub[64 / 8];
> >>>>> struct ofpbuf compound; @@ -1225,15 +1262,11 @@
> >>>>> installed_flow_dup(struct desired_flow *src) return dst; }
> >>>>>
> >>>>> -/* Finds and returns a desired_flow in 'flow_table' whose
> >>>>> key is
> >>>> identical to
> >>>>> - * 'target''s key, or NULL if there is none. - * - * If
> >>>>> sb_uuid is not NULL, the function will also check if the
> >>>>> found
> >>>> flow is
> >>>>> - * referenced by the sb_uuid. */ static struct desired_flow
> >>>>> * -desired_flow_lookup(struct ovn_desired_flow_table
> >>>>> *flow_table, -                    const struct ovn_flow
> >>>>> *target, -                    const struct uuid *sb_uuid)
> >>>>> +desired_flow_lookup__(struct ovn_desired_flow_table
> >>>>> *flow_table, +                      const struct ovn_flow
> >>>>> *target, +                      desired_flow_match_cb
> >>>>> match_cb, +                      const void *arg) { struct
> >>>>> desired_flow *d; HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node,
> >>>>> target->hash, @@ -1242,20 +1275,75 @@
> >>>>> desired_flow_lookup(struct
> >>>> ovn_desired_flow_table *flow_table,
> >>>>> if (f->table_id == target->table_id && f->priority ==
> >>>>> target->priority && minimatch_equal(&f->match,
> >>>>> &target->match)) { -            if (!sb_uuid) { + +
> >>>>> if (!match_cb || match_cb(d, arg)) { return d; } -
> >>>>> struct sb_flow_ref *sfr; -            LIST_FOR_EACH (sfr,
> >>>>> sb_list, &d->references) { -                if
> >>>>> (uuid_equals(sb_uuid, &sfr->sb_uuid)) { -
> >>>>> return d; -                } -            } } } return NULL;
> >>>>> }
> >>>>>
> >>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
> >>>>> key is
> >>>> identical to
> >>>>> + * 'target''s key, or NULL if there is none. + */ +static
> >>>>> struct desired_flow * +desired_flow_lookup(struct
> >>>>> ovn_desired_flow_table *flow_table, +
> >>>>> const struct ovn_flow *target) +{ +    return
> >>>>> desired_flow_lookup__(flow_table, target, NULL, NULL); +} +
> >>>>> +static bool +flow_lookup_match_uuid(const struct
> >>>>> desired_flow *candidate, const
> >>>> void *arg)
> >>>>
> >>>> This function is used as a callback, so it would be better to
> >>>> have _cb in its name to help code reading, e.g.
> >>>> flow_lookup_cb_match_uuid
> >>>>
> >>>
> >>> Sure.
> >>>
> >>>>> +{ +    const struct uuid *sb_uuid = arg; +    struct
> >>>>> sb_flow_ref *sfr; + +    LIST_FOR_EACH (sfr, sb_list,
> >>>>> &candidate->references) { +        if (uuid_equals(sb_uuid,
> >>>>> &sfr->sb_uuid)) { +            return true; +        } +
> >>>>> } +    return false; +} + +/* Finds and returns a
> >>>>> desired_flow in 'flow_table' whose key is
> >>>> identical to
> >>>>> + * 'target''s key, or NULL if there is none. + * + * The
> >>>>> function will also check if the found flow is referenced by
> >>>>> the + * 'sb_uuid'. + */ +static struct desired_flow *
> >>>>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table
> >>>>> *flow_table, +                            const struct
> >>>>> ovn_flow *target, +                            const struct
> >>>>> uuid *sb_uuid) +{ +    return
> >>>>> desired_flow_lookup__(flow_table, target,
> >>>> flow_lookup_match_uuid,
> >>>>> +                                 sb_uuid); +} + +static
> >>>>> bool +flow_lookup_match_conj(const struct desired_flow
> >>>>> *candidate, +                       const void *arg
> >>>>> OVS_UNUSED)
> >>>>
> >>>> Same as above of the naming.
> >>>>
> >>>
> >>> Ack.
> >>>
> >>>>> +{ +    return flow_action_has_conj(&candidate->flow); +} +
> >>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
> >>>>> key is
> >>>> identical to
> >>>>> + * 'target''s key, or NULL if there is none. + * + * The
> >>>>> function will only return a matching flow if it contains
> >>>>> action + * 'conjunction'. + */ +static struct desired_flow *
> >>>>> +desired_flow_lookup_conjunctive(struct
> >>>>> ovn_desired_flow_table
> >>>> *flow_table,
> >>>>> +                                const struct ovn_flow
> >>>>> *target) +{ +    return desired_flow_lookup__(flow_table,
> >>>>> target,
> >>>> flow_lookup_match_conj,
> >>>>> +                                 NULL); +} + /* Finds and
> >>>>> returns an installed_flow in installed_flows whose key is *
> >>>>> identical to 'target''s key, or NULL if there is none. */
> >>>>> static struct installed_flow * @@ -1653,8 +1741,7 @@
> >>>>> update_installed_flows_by_compare(struct
> >>>> ovn_desired_flow_table *flow_table,
> >>>>> struct installed_flow *i, *next; HMAP_FOR_EACH_SAFE (i, next,
> >>>>> match_hmap_node, &installed_flows) {
> >>>>> unlink_all_refs_for_installed_flow(i); -        struct
> >>>>> desired_flow *d = -
> >>>>> desired_flow_lookup(flow_table, &i->flow, NULL); +
> >>>>> struct desired_flow *d = desired_flow_lookup(flow_table,
> >>>> &i->flow);
> >>>>> if (!d) { /* Installed flow is no longer desirable.  Delete
> >>>>> it from the * switch and from installed_flows. */ @@ -1687,6
> >>>>> +1774,18 @@ update_installed_flows_by_compare(struct
> >>>> ovn_desired_flow_table *flow_table,
> >>>>> /* Copy 'd' from 'flow_table' to installed_flows. */ i =
> >>>>> installed_flow_dup(d); hmap_insert(&installed_flows,
> >>>>> &i->match_hmap_node,
> >>>> i->flow.hash);
> >>>>> +        } else if (i->desired_flow != d) { +            /*
> >>>>> If a matching installed flow was found but its actions are +
> >>>>> * conflicting with the desired flow actions, we should chose
> >>>>> +             * to install the least restrictive one (i.e.,
> >>>>> no conjunctive +             * action). +             */ +
> >>>>> if (flow_action_has_conj(&i->flow) && +
> >>>>> !flow_action_has_conj(&d->flow)) { +
> >>>>> flow_log_actions_conflict("Use new flow", &i->flow,
> >>>> &d->flow);
> >>>>> +                installed_flow_mod(&i->flow, &d->flow,
> >>>>> msgs); +                ovn_flow_log(&i->flow, "updating
> >>>>> installed"); +            }
> >>>>
> >>>> Here is a problem. Before this change, the flow actually
> >>>> installed in OVS is the one found in the previous loop. Now in
> >>>> this case we change the flow installed, we should update the
> >>>> i->desired_flow to match the one selected.
> >>>>
> >>>
> >>> Right, thanks for spotting this.
> >>>
> >>>>> } link_installed_to_desired(i, d); } @@ -1817,7 +1916,19 @@
> >>>>> update_installed_flows_by_track(struct
> >>>> ovn_desired_flow_table *flow_table,
> >>>>> installed_flow_mod(&i->flow, &f->flow, msgs); } else { /*
> >>>>> Adding a new flow that conflicts with an existing
> >>>> installed
> >>>>> -                 * flow, so just add it to the link. */ +
> >>>>> * flow, so just add it to the link. +                 * +
> >>>>> * However, if the existing installed flow is less
> >>>> restrictive
> >>>>> +                 * (i.e., no conjunctive action), we should
> >>>>> chose it
> >>>> over the
> >>>>> +                 * existing installed flow. +
> >>>>> */ +                if (flow_action_has_conj(&i->flow) && +
> >>>>> !flow_action_has_conj(&f->flow)) { +
> >>>>> flow_log_actions_conflict("Use new flow", +
> >>>>> &i->flow, &f->flow); +
> >>>>> ovn_flow_log(&i->flow, "updating installed
> >>>> (tracked)");
> >>>>> +                    installed_flow_mod(&i->flow, &f->flow,
> >>>>> msgs); +                }
> >>>>
> >>>> We should make sure it is set as the active flow.
> >>>>
> >>>> In addition, in the other branch in this function when the flow
> >>>> is deleted, we need to use the same criteria to select the flow
> >>>> to be actively installed. Currently
> >>>> unlink_installed_to_desired() just pick the first one from the
> >>>> rest of desired_flows in the linked list. This patch should go
> >>>> through the list and figure out which one should be selected
> >>>> using the same criteria.
> >>>>
> >>>
> >>> I think I also need to double check the self test. I thought I
> >>> was covering this case too but I guess I was wrong.
> >>>
> >>
> >> Hi Han,
> >>
> >> I've spent some more time thinking about all we discussed here and
> >> there's another case we didn't cover:
> >>
> >> Desired flow ordering can change (due to the order of logical flows
> >> in the IDL) when a recompute happens so we'd always have to walk
> >> the desired list flows to select the "least restrictive" one.
> >>
> >> I found a better solution which is to ensure that all desired
> >> flows referring an installed flow are always (partially) sorted in
> >> the list. This can be easily implemented with O(1) complexity and
> >> also makes selection of the "next-least-restrictive-flow" O(1).
> >>
> >> I had to make some changes to the existing ofctrl code so I sent v5
> >> as a series to make it easier to review independent changes:
> >>
> >> http://patchwork.ozlabs.org/project/ovn/list/?series=207123
> >>
> >> Thanks, Dumitru
> >>
> > Thanks Dumitru. After reviewing roughly the new series I have some
> > thoughts on the approach. It does make the next conflict flow
> > selection O(1) but it seems to be an optimization that IMHO not
> > really necessary while making the code more complex. The scenario is
> > when we have conflict flows, which of course can happen but the
> > number of conflicting flows shouldn't be huge. If a user configures
> > hundreds or thousands of ACLs that overlap with each other with the
> > same priority that is crazy and something fundamentally wrong. In the
> > real world I am expecting 2 - 3 items in the list in most cases. So I
> > was actually suggesting to traverse the desired_flow list when
> > selecting the next active flow (on top of your v4). The operation is
> > O(n) but it should be completely fine if we know n is extremely small
> > (even 100 items . That would keep the code easier to read and
> > maintain - less implications and constraints to keep in mind. (Of
> > course if we find such optimization really needed in the future it
> > can always be changed.)
>
> Hi Han,
>
> I think there might be some confusion.  Just to make sure we're discussing
> the same problem, considering the following "desired flows":
>
> a. match=M, action=conjunction(..)
> b. match=M, action=allow
> c. match=M, action=drop
>
> Let's assume flows are installed incrementally in the following order:
> a -> b -> c
>
> When flow "b" is added to the "installed" flow, it should replace "a" as
> active flow because "b" is less restrictive.  When flow "c" is
incrementally
> added we can decide if it should replace "b" or not.  Let's assume we
don't
> replace "b".
>
> At this point, installed flow "i" looks like this:
> - desired_flow = "b"
> - desired_refs = ["a", "b", "c"]
>
> If a recompute happens, the order in which flows are processed is
"random",
> depending on the logical flow UUIDs.  Let's say:
> a -> c -> b
>
> When flow "c" is processed and added to the "installed" flow, it should
> replace "a" as active flow because "c" is less restrictive.  When flow
"b" is
> processed, using the same logic as above we'll not replace "c".
>
> At this point, installed flow "i" looks like this:
> - desired_flow = "c"
> - desired_refs = ["a", "c", "b"]
>
> The problem with this is that we're now dropping all traffic that matches
> M while before the recompute we were allowing it.
>
> To solve this we can do what you suggested and select the active flow
> such that we always give precedence to "allow" over "drop" over
"conjunction".
> Please see the incremental diff below (it applies on top of patch 1 of v5
> [1]).

Yes, this is what I thought how it could be implemented, which is
straightforward and the change is small.

>
> However, this is basically just an inefficient implementation of a partial
> ordering of desired flows within installed_flow->desired_refs.  Moreover,
in
> my opinion, this doesn't differ much from the implementation where we
actually
> maintain the sorted list [2].
>
> Do you still think not maintaining the sorted list is less complex?
>
I think efficiency is not a major concern for this case. However, for
maintaining the partial order while inserting the item to the list v.s.
checking the order while selecting, since the code readability is the same,
I prefer the former (i.e. v5). I think what looks overkill to me in v5 is
the array of lists in patch4. An array of lists to store for 99% cases only
1 item (no confliction) and probably for 99.99% cases only less than 10
items (when there are occasional conflicts) is unnecessary. I think what we
need is just a "compare" function that tells the order between two flows,
which can be used when inserting the conflict flows to the desired_refs
list.

> Also, in any case, I still think patches 2 and 3 in v5 are beneficial for
> general code clarity because:
> - we don't really need an explicit reference to "desired_flow" if we
always
>   consider the first element in the list to be the active flow.  That
removes
>   one appearance of the "desired_flow" identifier in ofctrl.c where in my
>   opinion it's already easy to confuse what "desired_flow" we're dealing
with.
>   An "installed_flow_get_active()" API can hide this implementation and
let the
>   reader focus on other details.
> - we don't really need to use the link_installed_to_desired() and
>   unlink_installed_to_desired() APIs that change the order of
desired_flows
>   when merging opposite changes in merge_tracked_flows().
 ovs_list_replace()
>   is enough for that.  That makes the code easier to debug because we
don't
>   need to rely anymore on constructs like:
>             bool del_f_was_active = desired_flow_is_active(del_f);
>             [...] /* Do something that might change the order of flows. */
>             if (del_f_was_active) {
>                 desired_flow_set_active(f);
>             }
>

This part looks good to me.

Overall, my only suggestion to v5 is to avoid the array in patch 4. I have
merged patch 1 - 3 in v5.

Thanks,
Han


> Regards,
> Dumitru
>
> [1]
http://patchwork.ozlabs.org/project/ovn/patch/20201011120522.3374.57876.stgit@dceara.remote.csb/
> [2]
http://patchwork.ozlabs.org/project/ovn/patch/20201011120607.3374.49659.stgit@dceara.remote.csb/
>
> diff --git a/controller/ofctrl.c b/controller/ofctrl.c
> index 24b55fc..9af9f1c 100644
> --- a/controller/ofctrl.c
> +++ b/controller/ofctrl.c
> @@ -828,6 +828,51 @@ flow_action_has_conj(const struct ovn_flow *f)
>      return false;
>  }
>
> +static bool
> +flow_action_has_drop(const struct ovn_flow *f)
> +{
> +    return f->ofpacts_len == 0;
> +}
> +
> +static void
> +installed_flow_select_active(struct installed_flow *i)
> +{
> +    if (ovs_list_is_empty(&i->desired_refs)) {
> +        i->desired_flow = NULL;
> +        return;
> +    }
> +
> +    struct desired_flow *d;
> +    struct desired_flow *d_conj = NULL;
> +    struct desired_flow *d_drop = NULL;
> +    struct desired_flow *d_allow = NULL;
> +
> +    LIST_FOR_EACH (d, installed_ref_list_node, &i->desired_refs) {
> +        if (flow_action_has_conj(&d->flow)) {
> +            if (!d_conj) {
> +                d_conj = d;
> +            }
> +        } else if (flow_action_has_drop(&d->flow)) {
> +            if (!d_drop) {
> +                d_drop = d;
> +            }
> +        } else {
> +            if (!d_allow) {
> +                d_allow = d;
> +            }
> +        }
> +    }
> +
> +    /* Prefer allow action over block over conjunction. */
> +    if (d_allow) {
> +        i->desired_flow = d_allow;
> +    } else if (d_drop) {
> +        i->desired_flow = d_drop;
> +    } else {
> +        i->desired_flow = d_conj;
> +    }
> +}
> +
>  /* Adds the desired flow to the list of desired flows that have same
match
>   * conditions as the installed flow.
>   *
> @@ -840,12 +885,10 @@ static void
>  link_installed_to_desired(struct installed_flow *i, struct desired_flow
*d)
>  {
>      ovs_assert(i->desired_flow != d);
> -    if (ovs_list_is_empty(&i->desired_refs)) {
> -        ovs_assert(!i->desired_flow);
> -        i->desired_flow = d;
> -    }
>      ovs_list_insert(&i->desired_refs, &d->installed_ref_list_node);
>      d->installed_flow = i;
> +
> +    installed_flow_select_active(i);
>  }
>
>  static void
> @@ -855,12 +898,7 @@ unlink_installed_to_desired(struct installed_flow
*i, struct desired_flow *d)
>      ovs_assert(d && d->installed_flow == i);
>      ovs_list_remove(&d->installed_ref_list_node);
>      d->installed_flow = NULL;
> -    if (i->desired_flow == d) {
> -        i->desired_flow = ovs_list_is_empty(&i->desired_refs) ? NULL :
> -            CONTAINER_OF(ovs_list_front(&i->desired_refs),
> -                         struct desired_flow,
> -                         installed_ref_list_node);
> -    }
> +    installed_flow_select_active(i);
>  }
>
>  static void
> @@ -1789,6 +1827,9 @@ update_installed_flows_by_compare(struct
ovn_desired_flow_table *flow_table,
>              /* This is a desired_flow that conflicts with one installed
>               * previously but not linked yet. */
>              link_installed_to_desired(i, d);
> +            if (desired_flow_is_active(d)) {
> +                installed_flow_mod(&i->flow, &d->flow, msgs);
> +            }
>          }
>      }
>  }
> @@ -1926,6 +1967,9 @@ update_installed_flows_by_track(struct
ovn_desired_flow_table *flow_table,
>                  /* Adding a new flow that conflicts with an existing
installed
>                   * flow, so just add it to the link. */
>                  link_installed_to_desired(i, f);
> +                if (desired_flow_is_active(f)) {
> +                    installed_flow_mod(&i->flow, &f->flow, msgs);
> +                }
>              }
>              /* The track_list_node emptyness is used to check if the
node is
>               * already added to track list, so initialize it again here.
*/
>
Dumitru Ceara Oct. 13, 2020, 7:17 a.m. UTC | #8
On 10/13/20 8:58 AM, Han Zhou wrote:
> 
> 
> On Mon, Oct 12, 2020 at 3:16 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>> wrote:
>>
>>
>> On 10/11/20 9:40 PM, Han Zhou wrote:
>> >
>> >
>> > On Sun, Oct 11, 2020 at 5:14 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>
>> > <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>> wrote:
>> >>
>> >> On 10/6/20 10:30 AM, Dumitru Ceara wrote:
>> >>> On 10/2/20 10:28 PM, Han Zhou wrote:
>> >>>>
>> >>>> Hi Dumitru,
>> >>>>
>> >>>
>> >>> Hi Han,
>> >>>
>> >>>> Thanks for the revision. It looks good overall. The major
>> >>>> problems left are: 1. it missed updating the active
>> >>>> desired_flow in the installed_flow. 2. when a tracked flow
>> >>>> deletion is handled, if there are other desired flows linked to
>> >>>> the same installed flow, it should use the same criteria to
>> >>>> decide which flow should become active from the candidate
>> >>>> flows.
>> >>>>
>> >>>
>> >>> I see, you're right, thanks. I'll fix it in the next revision.
>> >>>
>> >>>> I also noticed 2 problems of the existing code while reviewing
>> >>>> this patch. I submitted 2 patches: 1.
>> >>>>
> https://patchwork.ozlabs.org/project/ovn/patch/1601663136-19111-1-git-send-email-hzhou@ovn.org/
>> >>
>> >>>>
>> >> 2.
>> >>>>
> https://patchwork.ozlabs.org/project/ovn/patch/20201002200504.2954064-1-hzhou@ovn.org/
>> >>
>> >>>>
>> >>
>> >>>> 1) is required for your solution to work properly. 2) is not
>> >>>> directly related but will cause a merge conflict. Please help
>> >>>> review both since they are closely related to your patch.
>> >>>>
>> >>>
>> >>> I'll try to review your patches as soon as possible and I'll
>> >>> respin mine afterwards.
>> >>>
>> >>>> Please see more detailed comments below.
>> >>>>
>> >>>> On Wed, Sep 30, 2020 at 12:39 AM Dumitru Ceara
>> >>>> <dceara@redhat.com <mailto:dceara@redhat.com>
> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>
>> >>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>
> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>>> wrote:
>> >>>>>
>> >>>>> Until now, in case the ACL configuration generates openflows
>> >>>>> that have the same match but different actions,
>> >>>>> ovn-controller was using the following approach: 1. If the
>> >>>>> flow being added contains conjunctive actions, merge its
>> >>>>> actions with the already existing flow. 2. Otherwise, if the
>> >>>>> flow is being added incrementally
>> >>>>> (update_installed_flows_by_track), don't install the new flow
>> >>>>> but instead keep the old one. 3. Otherwise,
>> >>>>> (update_installed_flows_by_compare), don't install the new
>> >>>>> flow but instead keep the old one.
>> >>>>>
>> >>>>> Even though one can argue that having an ACL with a match
>> >>>>> that includes the match of another ACL is a misconfiguration,
>> >>>>> it can happen that the users provision OVN like this.
>> >>>>> Depending on the order of reading and installing the logical
>> >>>>> flows, the above operations can yield unpredictable results,
>> >>>>> e.g., allow specific traffic but then after ovn-controller is
>> >>>>> restarted (or a recompute happens) that specific traffic
>> >>>>> starts being dropped.
>> >>>>>
>> >>>>> A simple example of ACL configuration is: ovn-nbctl acl-add
>> >>>>> ls to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.2) &&
>> >>>>> (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow ovn-nbctl
>> >>>>> acl-add ls to-lport 3 'ip4.src==10.0.0.1' allow ovn-nbctl
>> >>>>> acl-add ls to-lport 2 'arp' allow ovn-nbctl acl-add ls
>> >>>>> to-lport 1 'ip4' drop
>> >>>>>
>> >>>>> This is a pattern used by most CMSs: - define a default deny
>> >>>>> policy. - punch holes in the default deny policy based on
>> >>>>> user specific configurations.
>> >>>>>
>> >>>>> Without this commit the behavior for traffic from 10.0.0.1 to
>> >>>>> 10.0.0.5 is unpredictable. Depending on the order of
>> >>>>> operations traffic might be dropped or allowed.
>> >>>>>
>> >>>>> It's also quite hard to force the CMS to ensure that such
>> >>>>> match overlaps never occur.
>> >>>>>
>> >>>>> To address this issue we now resolve conflicts between flows
>> >>>>> with the same match and different actions by giving
>> >>>>> precedence to less restrictive flows. This means that if the
>> >>>>> installed flow has action "conjunction" and the desired flow
>> >>>>> doesn't then we prefer the desired flow. Similarly, if the
>> >>>>> desired flow has action "conjunction" and the installed flow
>> >>>>> doesn't then we prefer the already installed flow.
>> >>>>>
>> >>>>> CC: Daniel Alvarez <dalvarez@redhat.com <mailto:dalvarez@redhat.com>
>> >>>>> <mailto:dalvarez@redhat.com <mailto:dalvarez@redhat.com>>
> <mailto:dalvarez@redhat.com <mailto:dalvarez@redhat.com>
>> >>>>> <mailto:dalvarez@redhat.com <mailto:dalvarez@redhat.com>>>> CC:
> Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>
>> >>>>> <mailto:hzhou@ovn.org <mailto:hzhou@ovn.org>>
> <mailto:hzhou@ovn.org <mailto:hzhou@ovn.org>
>> >>>>> <mailto:hzhou@ovn.org <mailto:hzhou@ovn.org>>>> Reported-at:
>> >>>>> https://bugzilla.redhat.com/1871931 Acked-by: Mark Michelson
>> >>>>> <mmichels@redhat.com <mailto:mmichels@redhat.com>
> <mailto:mmichels@redhat.com <mailto:mmichels@redhat.com>>
>> >>>> <mailto:mmichels@redhat.com <mailto:mmichels@redhat.com>
> <mailto:mmichels@redhat.com <mailto:mmichels@redhat.com>>>>
>> >>>>> Signed-off-by: Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>
>> >>>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>
>> >>>> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>
> <mailto:dceara@redhat.com <mailto:dceara@redhat.com>>>>
>> >>>>> --- v4: - Address Han's comments: - make sure only flows with
>> >>>>> action conjunction are combined. v3: - Add Mark's ack. - Add
>> >>>>> last missing pcap check in the test. v2: - Address Han's
>> >>>>> comments: - Do not delete desired flow that cannot be merged,
>> >>>>> it might be installed later. - Fix typos in the commit log. -
>> >>>>> Update the test to check the OVS flows. ---
>> >>>>> controller/ofctrl.c | 163
>> >>>>> ++++++++++++++++++++++++++++++++++++------- tests/ovn.at
> <http://ovn.at>
>> >>>>> <http://ovn.at> <http://ovn.at>        | 195
>> >>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++
>> >>>>> 2 files changed, 332 insertions(+), 26 deletions(-)
>> >>>>>
>> >>>>> diff --git a/controller/ofctrl.c b/controller/ofctrl.c index
>> >>>>> 81a00c8..4577413 100644 --- a/controller/ofctrl.c +++
>> >>>>> b/controller/ofctrl.c @@ -206,6 +206,9 @@ struct
>> >>>>> installed_flow { struct desired_flow *desired_flow; };
>> >>>>>
>> >>>>> +typedef bool +(*desired_flow_match_cb)(const struct
>> >>>>> desired_flow *candidate, +                         const void
>> >>>>> *arg); static struct desired_flow *desired_flow_alloc(
>> >>>>> uint8_t table_id, uint16_t priority, @@ -214,8 +217,14 @@
>> >>>>> static struct desired_flow *desired_flow_alloc( const struct
>> >>>>> ofpbuf *actions); static struct desired_flow
>> >>>>> *desired_flow_lookup( struct ovn_desired_flow_table *, +
>> >>>>> const struct ovn_flow *target); +static struct desired_flow
>> >>>>> *desired_flow_lookup_by_uuid(
>> >>>>
>> >>>> The name "by_uuid" is a little misleading. It sounds like it
>> >>>> only looks uuid. But instead, it still looks up by match which
>> >>>> it will also compare uuid. How about:
>> >>>> desired_flow_lookup_check_uuid?
>> >>>>
>> >>>>> +    struct ovn_desired_flow_table *, const struct ovn_flow
>> >>>>> *target, -    const struct uuid *sb_uuid); +    const struct
>> >>>>> uuid *); +static struct desired_flow
>> >>>>> *desired_flow_lookup_conjunctive( +    struct
>> >>>>> ovn_desired_flow_table *, +    const struct ovn_flow
>> >>>>> *target); static void desired_flow_destroy(struct
>> >>>>> desired_flow *);
>> >>>>>
>> >>>>> static struct installed_flow *installed_flow_lookup( @@
>> >>>>> -916,6 +925,33 @@ link_flow_to_sb(struct
>> >>>>> ovn_desired_flow_table
>> >>>> *flow_table,
>> >>>>> ovs_list_insert(&stf->flows, &sfr->flow_list); }
>> >>>>>
>> >>>>> +static bool +flow_action_has_conj(const struct ovn_flow *f)
>> >>>>> +{ +    const struct ofpact *a = NULL; + +    OFPACT_FOR_EACH
>> >>>>> (a, f->ofpacts, f->ofpacts_len) { +        if (a->type ==
>> >>>>> OFPACT_CONJUNCTION) { +            return true; +        } +
>> >>>>> } +    return false; +} + +static void
>> >>>>> +flow_log_actions_conflict(const char *msg, const struct
>> >>>>> ovn_flow *f1, +                          const struct
>> >>>>> ovn_flow *f2) +{ +    static struct vlog_rate_limit rl =
>> >>>>> VLOG_RATE_LIMIT_INIT(5, 1); +    char *f1_s =
>> >>>>> ovn_flow_to_string(f1); +    char *f2_s =
>> >>>>> ovn_flow_to_string(f2); + +    VLOG_WARN_RL(&rl, "Flow
>> >>>>> actions conflict: %s, flow-1: %s, flow-2:
>> >>>> %s",
>> >>>>> +                 msg, f1_s, f2_s); +    free(f1_s); +
>> >>>>> free(f2_s); +} +
>> >>>>
>> >>>> In this log it would be better to mention which one is
>> >>>> selected. It would be better not only abstracting the logging
>> >>>> into a function but also the logic of comparing flows and
>> >>>> determining which one is selected.
>> >>>>
>> >>>
>> >>> Ack, sounds better indeed.
>> >>>
>> >>>>> /* Flow table interfaces to the rest of ovn-controller. */
>> >>>>>
>> >>>>> /* Adds a flow to 'desired_flows' with the specified 'match'
>> >>>>> and
>> >>>> 'actions' to
>> >>>>> @@ -939,7 +975,7 @@ ofctrl_check_and_add_flow(struct
>> >>>> ovn_desired_flow_table *flow_table,
>> >>>>> struct desired_flow *f = desired_flow_alloc(table_id,
>> >>>>> priority,
>> >>>> cookie,
>> >>>>> match, actions);
>> >>>>>
>> >>>>> -    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid))
>> >>>>> { +    if (desired_flow_lookup_by_uuid(flow_table, &f->flow,
>> >>>>> sb_uuid)) { if (log_duplicate_flow) { static struct
>> >>>>> vlog_rate_limit rl =
>> >>>> VLOG_RATE_LIMIT_INIT(5, 5);
>> >>>>> if (!VLOG_DROP_DBG(&rl)) { @@ -979,14 +1015,15 @@
>> >>>>> ofctrl_add_or_append_flow(struct
>> >>>> ovn_desired_flow_table *desired_flows,
>> >>>>> const struct ofpbuf *actions, const struct uuid *sb_uuid) { -
>> >>>>> struct desired_flow *f = desired_flow_alloc(table_id,
>> >>>>> priority,
>> >>>> cookie,
>> >>>>> -                                                match,
>> >>>>> actions); - struct desired_flow *existing; -    existing =
>> >>>>> desired_flow_lookup(desired_flows, &f->flow, NULL); +
>> >>>>> struct desired_flow *f; + +    f =
>> >>>>> desired_flow_alloc(table_id, priority, cookie, match,
>> >>>>> actions); +    existing =
>> >>>>> desired_flow_lookup_conjunctive(desired_flows, &f->flow); if
>> >>>>> (existing) { -        /* There's already a flow with this
>> >>>>> particular match. Append the -         * action to that flow
>> >>>>> rather than adding a new flow +        /* There's already a
>> >>>>> flow with this particular match and action +         *
>> >>>>> 'conjunction'. Append the action to that flow rather than +
>> >>>>> * adding a new flow. */ uint64_t compound_stub[64 / 8];
>> >>>>> struct ofpbuf compound; @@ -1225,15 +1262,11 @@
>> >>>>> installed_flow_dup(struct desired_flow *src) return dst; }
>> >>>>>
>> >>>>> -/* Finds and returns a desired_flow in 'flow_table' whose
>> >>>>> key is
>> >>>> identical to
>> >>>>> - * 'target''s key, or NULL if there is none. - * - * If
>> >>>>> sb_uuid is not NULL, the function will also check if the
>> >>>>> found
>> >>>> flow is
>> >>>>> - * referenced by the sb_uuid. */ static struct desired_flow
>> >>>>> * -desired_flow_lookup(struct ovn_desired_flow_table
>> >>>>> *flow_table, -                    const struct ovn_flow
>> >>>>> *target, -                    const struct uuid *sb_uuid)
>> >>>>> +desired_flow_lookup__(struct ovn_desired_flow_table
>> >>>>> *flow_table, +                      const struct ovn_flow
>> >>>>> *target, +                      desired_flow_match_cb
>> >>>>> match_cb, +                      const void *arg) { struct
>> >>>>> desired_flow *d; HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node,
>> >>>>> target->hash, @@ -1242,20 +1275,75 @@
>> >>>>> desired_flow_lookup(struct
>> >>>> ovn_desired_flow_table *flow_table,
>> >>>>> if (f->table_id == target->table_id && f->priority ==
>> >>>>> target->priority && minimatch_equal(&f->match,
>> >>>>> &target->match)) { -            if (!sb_uuid) { + +
>> >>>>> if (!match_cb || match_cb(d, arg)) { return d; } -
>> >>>>> struct sb_flow_ref *sfr; -            LIST_FOR_EACH (sfr,
>> >>>>> sb_list, &d->references) { -                if
>> >>>>> (uuid_equals(sb_uuid, &sfr->sb_uuid)) { -
>> >>>>> return d; -                } -            } } } return NULL;
>> >>>>> }
>> >>>>>
>> >>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
>> >>>>> key is
>> >>>> identical to
>> >>>>> + * 'target''s key, or NULL if there is none. + */ +static
>> >>>>> struct desired_flow * +desired_flow_lookup(struct
>> >>>>> ovn_desired_flow_table *flow_table, +
>> >>>>> const struct ovn_flow *target) +{ +    return
>> >>>>> desired_flow_lookup__(flow_table, target, NULL, NULL); +} +
>> >>>>> +static bool +flow_lookup_match_uuid(const struct
>> >>>>> desired_flow *candidate, const
>> >>>> void *arg)
>> >>>>
>> >>>> This function is used as a callback, so it would be better to
>> >>>> have _cb in its name to help code reading, e.g.
>> >>>> flow_lookup_cb_match_uuid
>> >>>>
>> >>>
>> >>> Sure.
>> >>>
>> >>>>> +{ +    const struct uuid *sb_uuid = arg; +    struct
>> >>>>> sb_flow_ref *sfr; + +    LIST_FOR_EACH (sfr, sb_list,
>> >>>>> &candidate->references) { +        if (uuid_equals(sb_uuid,
>> >>>>> &sfr->sb_uuid)) { +            return true; +        } +
>> >>>>> } +    return false; +} + +/* Finds and returns a
>> >>>>> desired_flow in 'flow_table' whose key is
>> >>>> identical to
>> >>>>> + * 'target''s key, or NULL if there is none. + * + * The
>> >>>>> function will also check if the found flow is referenced by
>> >>>>> the + * 'sb_uuid'. + */ +static struct desired_flow *
>> >>>>> +desired_flow_lookup_by_uuid(struct ovn_desired_flow_table
>> >>>>> *flow_table, +                            const struct
>> >>>>> ovn_flow *target, +                            const struct
>> >>>>> uuid *sb_uuid) +{ +    return
>> >>>>> desired_flow_lookup__(flow_table, target,
>> >>>> flow_lookup_match_uuid,
>> >>>>> +                                 sb_uuid); +} + +static
>> >>>>> bool +flow_lookup_match_conj(const struct desired_flow
>> >>>>> *candidate, +                       const void *arg
>> >>>>> OVS_UNUSED)
>> >>>>
>> >>>> Same as above of the naming.
>> >>>>
>> >>>
>> >>> Ack.
>> >>>
>> >>>>> +{ +    return flow_action_has_conj(&candidate->flow); +} +
>> >>>>> +/* Finds and returns a desired_flow in 'flow_table' whose
>> >>>>> key is
>> >>>> identical to
>> >>>>> + * 'target''s key, or NULL if there is none. + * + * The
>> >>>>> function will only return a matching flow if it contains
>> >>>>> action + * 'conjunction'. + */ +static struct desired_flow *
>> >>>>> +desired_flow_lookup_conjunctive(struct
>> >>>>> ovn_desired_flow_table
>> >>>> *flow_table,
>> >>>>> +                                const struct ovn_flow
>> >>>>> *target) +{ +    return desired_flow_lookup__(flow_table,
>> >>>>> target,
>> >>>> flow_lookup_match_conj,
>> >>>>> +                                 NULL); +} + /* Finds and
>> >>>>> returns an installed_flow in installed_flows whose key is *
>> >>>>> identical to 'target''s key, or NULL if there is none. */
>> >>>>> static struct installed_flow * @@ -1653,8 +1741,7 @@
>> >>>>> update_installed_flows_by_compare(struct
>> >>>> ovn_desired_flow_table *flow_table,
>> >>>>> struct installed_flow *i, *next; HMAP_FOR_EACH_SAFE (i, next,
>> >>>>> match_hmap_node, &installed_flows) {
>> >>>>> unlink_all_refs_for_installed_flow(i); -        struct
>> >>>>> desired_flow *d = -
>> >>>>> desired_flow_lookup(flow_table, &i->flow, NULL); +
>> >>>>> struct desired_flow *d = desired_flow_lookup(flow_table,
>> >>>> &i->flow);
>> >>>>> if (!d) { /* Installed flow is no longer desirable.  Delete
>> >>>>> it from the * switch and from installed_flows. */ @@ -1687,6
>> >>>>> +1774,18 @@ update_installed_flows_by_compare(struct
>> >>>> ovn_desired_flow_table *flow_table,
>> >>>>> /* Copy 'd' from 'flow_table' to installed_flows. */ i =
>> >>>>> installed_flow_dup(d); hmap_insert(&installed_flows,
>> >>>>> &i->match_hmap_node,
>> >>>> i->flow.hash);
>> >>>>> +        } else if (i->desired_flow != d) { +            /*
>> >>>>> If a matching installed flow was found but its actions are +
>> >>>>> * conflicting with the desired flow actions, we should chose
>> >>>>> +             * to install the least restrictive one (i.e.,
>> >>>>> no conjunctive +             * action). +             */ +
>> >>>>> if (flow_action_has_conj(&i->flow) && +
>> >>>>> !flow_action_has_conj(&d->flow)) { +
>> >>>>> flow_log_actions_conflict("Use new flow", &i->flow,
>> >>>> &d->flow);
>> >>>>> +                installed_flow_mod(&i->flow, &d->flow,
>> >>>>> msgs); +                ovn_flow_log(&i->flow, "updating
>> >>>>> installed"); +            }
>> >>>>
>> >>>> Here is a problem. Before this change, the flow actually
>> >>>> installed in OVS is the one found in the previous loop. Now in
>> >>>> this case we change the flow installed, we should update the
>> >>>> i->desired_flow to match the one selected.
>> >>>>
>> >>>
>> >>> Right, thanks for spotting this.
>> >>>
>> >>>>> } link_installed_to_desired(i, d); } @@ -1817,7 +1916,19 @@
>> >>>>> update_installed_flows_by_track(struct
>> >>>> ovn_desired_flow_table *flow_table,
>> >>>>> installed_flow_mod(&i->flow, &f->flow, msgs); } else { /*
>> >>>>> Adding a new flow that conflicts with an existing
>> >>>> installed
>> >>>>> -                 * flow, so just add it to the link. */ +
>> >>>>> * flow, so just add it to the link. +                 * +
>> >>>>> * However, if the existing installed flow is less
>> >>>> restrictive
>> >>>>> +                 * (i.e., no conjunctive action), we should
>> >>>>> chose it
>> >>>> over the
>> >>>>> +                 * existing installed flow. +
>> >>>>> */ +                if (flow_action_has_conj(&i->flow) && +
>> >>>>> !flow_action_has_conj(&f->flow)) { +
>> >>>>> flow_log_actions_conflict("Use new flow", +
>> >>>>> &i->flow, &f->flow); +
>> >>>>> ovn_flow_log(&i->flow, "updating installed
>> >>>> (tracked)");
>> >>>>> +                    installed_flow_mod(&i->flow, &f->flow,
>> >>>>> msgs); +                }
>> >>>>
>> >>>> We should make sure it is set as the active flow.
>> >>>>
>> >>>> In addition, in the other branch in this function when the flow
>> >>>> is deleted, we need to use the same criteria to select the flow
>> >>>> to be actively installed. Currently
>> >>>> unlink_installed_to_desired() just pick the first one from the
>> >>>> rest of desired_flows in the linked list. This patch should go
>> >>>> through the list and figure out which one should be selected
>> >>>> using the same criteria.
>> >>>>
>> >>>
>> >>> I think I also need to double check the self test. I thought I
>> >>> was covering this case too but I guess I was wrong.
>> >>>
>> >>
>> >> Hi Han,
>> >>
>> >> I've spent some more time thinking about all we discussed here and
>> >> there's another case we didn't cover:
>> >>
>> >> Desired flow ordering can change (due to the order of logical flows
>> >> in the IDL) when a recompute happens so we'd always have to walk
>> >> the desired list flows to select the "least restrictive" one.
>> >>
>> >> I found a better solution which is to ensure that all desired
>> >> flows referring an installed flow are always (partially) sorted in
>> >> the list. This can be easily implemented with O(1) complexity and
>> >> also makes selection of the "next-least-restrictive-flow" O(1).
>> >>
>> >> I had to make some changes to the existing ofctrl code so I sent v5
>> >> as a series to make it easier to review independent changes:
>> >>
>> >> http://patchwork.ozlabs.org/project/ovn/list/?series=207123
>> >>
>> >> Thanks, Dumitru
>> >>
>> > Thanks Dumitru. After reviewing roughly the new series I have some
>> > thoughts on the approach. It does make the next conflict flow
>> > selection O(1) but it seems to be an optimization that IMHO not
>> > really necessary while making the code more complex. The scenario is
>> > when we have conflict flows, which of course can happen but the
>> > number of conflicting flows shouldn't be huge. If a user configures
>> > hundreds or thousands of ACLs that overlap with each other with the
>> > same priority that is crazy and something fundamentally wrong. In the
>> > real world I am expecting 2 - 3 items in the list in most cases. So I
>> > was actually suggesting to traverse the desired_flow list when
>> > selecting the next active flow (on top of your v4). The operation is
>> > O(n) but it should be completely fine if we know n is extremely small
>> > (even 100 items . That would keep the code easier to read and
>> > maintain - less implications and constraints to keep in mind. (Of
>> > course if we find such optimization really needed in the future it
>> > can always be changed.)
>>
>> Hi Han,
>>
>> I think there might be some confusion.  Just to make sure we're discussing
>> the same problem, considering the following "desired flows":
>>
>> a. match=M, action=conjunction(..)
>> b. match=M, action=allow
>> c. match=M, action=drop
>>
>> Let's assume flows are installed incrementally in the following order:
>> a -> b -> c
>>
>> When flow "b" is added to the "installed" flow, it should replace "a" as
>> active flow because "b" is less restrictive.  When flow "c" is
> incrementally
>> added we can decide if it should replace "b" or not.  Let's assume we
> don't
>> replace "b".
>>
>> At this point, installed flow "i" looks like this:
>> - desired_flow = "b"
>> - desired_refs = ["a", "b", "c"]
>>
>> If a recompute happens, the order in which flows are processed is
> "random",
>> depending on the logical flow UUIDs.  Let's say:
>> a -> c -> b
>>
>> When flow "c" is processed and added to the "installed" flow, it should
>> replace "a" as active flow because "c" is less restrictive.  When flow
> "b" is
>> processed, using the same logic as above we'll not replace "c".
>>
>> At this point, installed flow "i" looks like this:
>> - desired_flow = "c"
>> - desired_refs = ["a", "c", "b"]
>>
>> The problem with this is that we're now dropping all traffic that matches
>> M while before the recompute we were allowing it.
>>
>> To solve this we can do what you suggested and select the active flow
>> such that we always give precedence to "allow" over "drop" over
> "conjunction".
>> Please see the incremental diff below (it applies on top of patch 1 of v5
>> [1]).
> 
> Yes, this is what I thought how it could be implemented, which is
> straightforward and the change is small.
> 
>>
>> However, this is basically just an inefficient implementation of a partial
>> ordering of desired flows within installed_flow->desired_refs. 
> Moreover, in
>> my opinion, this doesn't differ much from the implementation where we
> actually
>> maintain the sorted list [2].
>>
>> Do you still think not maintaining the sorted list is less complex?
>>
> I think efficiency is not a major concern for this case. However, for
> maintaining the partial order while inserting the item to the list v.s.
> checking the order while selecting, since the code readability is the
> same, I prefer the former (i.e. v5). I think what looks overkill to me
> in v5 is the array of lists in patch4. An array of lists to store for
> 99% cases only 1 item (no confliction) and probably for 99.99% cases
> only less than 10 items (when there are occasional conflicts) is
> unnecessary. I think what we need is just a "compare" function that
> tells the order between two flows, which can be used when inserting the
> conflict flows to the desired_refs list.
> 
>> Also, in any case, I still think patches 2 and 3 in v5 are beneficial for
>> general code clarity because:
>> - we don't really need an explicit reference to "desired_flow" if we
> always
>>   consider the first element in the list to be the active flow.  That
> removes
>>   one appearance of the "desired_flow" identifier in ofctrl.c where in my
>>   opinion it's already easy to confuse what "desired_flow" we're
> dealing with.
>>   An "installed_flow_get_active()" API can hide this implementation
> and let the
>>   reader focus on other details.
>> - we don't really need to use the link_installed_to_desired() and
>>   unlink_installed_to_desired() APIs that change the order of
> desired_flows
>>   when merging opposite changes in merge_tracked_flows().
>  ovs_list_replace()
>>   is enough for that.  That makes the code easier to debug because we
> don't
>>   need to rely anymore on constructs like:
>>             bool del_f_was_active = desired_flow_is_active(del_f);
>>             [...] /* Do something that might change the order of flows. */
>>             if (del_f_was_active) {
>>                 desired_flow_set_active(f);
>>             }
>>
> 
> This part looks good to me.
> 
> Overall, my only suggestion to v5 is to avoid the array in patch 4. I
> have merged patch 1 - 3 in v5.
> 

Thanks Han for the reviews.  I'll go for the version without an array in
v6 and we can revisit it later if we determine that it's worth avoiding
the walk.

Regards,
Dumitru
diff mbox series

Patch

diff --git a/controller/ofctrl.c b/controller/ofctrl.c
index 81a00c8..4577413 100644
--- a/controller/ofctrl.c
+++ b/controller/ofctrl.c
@@ -206,6 +206,9 @@  struct installed_flow {
     struct desired_flow *desired_flow;
 };
 
+typedef bool
+(*desired_flow_match_cb)(const struct desired_flow *candidate,
+                         const void *arg);
 static struct desired_flow *desired_flow_alloc(
     uint8_t table_id,
     uint16_t priority,
@@ -214,8 +217,14 @@  static struct desired_flow *desired_flow_alloc(
     const struct ofpbuf *actions);
 static struct desired_flow *desired_flow_lookup(
     struct ovn_desired_flow_table *,
+    const struct ovn_flow *target);
+static struct desired_flow *desired_flow_lookup_by_uuid(
+    struct ovn_desired_flow_table *,
     const struct ovn_flow *target,
-    const struct uuid *sb_uuid);
+    const struct uuid *);
+static struct desired_flow *desired_flow_lookup_conjunctive(
+    struct ovn_desired_flow_table *,
+    const struct ovn_flow *target);
 static void desired_flow_destroy(struct desired_flow *);
 
 static struct installed_flow *installed_flow_lookup(
@@ -916,6 +925,33 @@  link_flow_to_sb(struct ovn_desired_flow_table *flow_table,
     ovs_list_insert(&stf->flows, &sfr->flow_list);
 }
 
+static bool
+flow_action_has_conj(const struct ovn_flow *f)
+{
+    const struct ofpact *a = NULL;
+
+    OFPACT_FOR_EACH (a, f->ofpacts, f->ofpacts_len) {
+        if (a->type == OFPACT_CONJUNCTION) {
+            return true;
+        }
+    }
+    return false;
+}
+
+static void
+flow_log_actions_conflict(const char *msg, const struct ovn_flow *f1,
+                          const struct ovn_flow *f2)
+{
+    static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
+    char *f1_s = ovn_flow_to_string(f1);
+    char *f2_s = ovn_flow_to_string(f2);
+
+    VLOG_WARN_RL(&rl, "Flow actions conflict: %s, flow-1: %s, flow-2: %s",
+                 msg, f1_s, f2_s);
+    free(f1_s);
+    free(f2_s);
+}
+
 /* Flow table interfaces to the rest of ovn-controller. */
 
 /* Adds a flow to 'desired_flows' with the specified 'match' and 'actions' to
@@ -939,7 +975,7 @@  ofctrl_check_and_add_flow(struct ovn_desired_flow_table *flow_table,
     struct desired_flow *f = desired_flow_alloc(table_id, priority, cookie,
                                                 match, actions);
 
-    if (desired_flow_lookup(flow_table, &f->flow, sb_uuid)) {
+    if (desired_flow_lookup_by_uuid(flow_table, &f->flow, sb_uuid)) {
         if (log_duplicate_flow) {
             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 5);
             if (!VLOG_DROP_DBG(&rl)) {
@@ -979,14 +1015,15 @@  ofctrl_add_or_append_flow(struct ovn_desired_flow_table *desired_flows,
                           const struct ofpbuf *actions,
                           const struct uuid *sb_uuid)
 {
-    struct desired_flow *f = desired_flow_alloc(table_id, priority, cookie,
-                                                match, actions);
-
     struct desired_flow *existing;
-    existing = desired_flow_lookup(desired_flows, &f->flow, NULL);
+    struct desired_flow *f;
+
+    f = desired_flow_alloc(table_id, priority, cookie, match, actions);
+    existing = desired_flow_lookup_conjunctive(desired_flows, &f->flow);
     if (existing) {
-        /* There's already a flow with this particular match. Append the
-         * action to that flow rather than adding a new flow
+        /* There's already a flow with this particular match and action
+         * 'conjunction'. Append the action to that flow rather than
+         * adding a new flow.
          */
         uint64_t compound_stub[64 / 8];
         struct ofpbuf compound;
@@ -1225,15 +1262,11 @@  installed_flow_dup(struct desired_flow *src)
     return dst;
 }
 
-/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
- * 'target''s key, or NULL if there is none.
- *
- * If sb_uuid is not NULL, the function will also check if the found flow is
- * referenced by the sb_uuid. */
 static struct desired_flow *
-desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
-                    const struct ovn_flow *target,
-                    const struct uuid *sb_uuid)
+desired_flow_lookup__(struct ovn_desired_flow_table *flow_table,
+                      const struct ovn_flow *target,
+                      desired_flow_match_cb match_cb,
+                      const void *arg)
 {
     struct desired_flow *d;
     HMAP_FOR_EACH_WITH_HASH (d, match_hmap_node, target->hash,
@@ -1242,20 +1275,75 @@  desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
         if (f->table_id == target->table_id
             && f->priority == target->priority
             && minimatch_equal(&f->match, &target->match)) {
-            if (!sb_uuid) {
+
+            if (!match_cb || match_cb(d, arg)) {
                 return d;
             }
-            struct sb_flow_ref *sfr;
-            LIST_FOR_EACH (sfr, sb_list, &d->references) {
-                if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
-                    return d;
-                }
-            }
         }
     }
     return NULL;
 }
 
+/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
+ * 'target''s key, or NULL if there is none.
+ */
+static struct desired_flow *
+desired_flow_lookup(struct ovn_desired_flow_table *flow_table,
+                    const struct ovn_flow *target)
+{
+    return desired_flow_lookup__(flow_table, target, NULL, NULL);
+}
+
+static bool
+flow_lookup_match_uuid(const struct desired_flow *candidate, const void *arg)
+{
+    const struct uuid *sb_uuid = arg;
+    struct sb_flow_ref *sfr;
+
+    LIST_FOR_EACH (sfr, sb_list, &candidate->references) {
+        if (uuid_equals(sb_uuid, &sfr->sb_uuid)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
+ * 'target''s key, or NULL if there is none.
+ *
+ * The function will also check if the found flow is referenced by the
+ * 'sb_uuid'.
+ */
+static struct desired_flow *
+desired_flow_lookup_by_uuid(struct ovn_desired_flow_table *flow_table,
+                            const struct ovn_flow *target,
+                            const struct uuid *sb_uuid)
+{
+    return desired_flow_lookup__(flow_table, target, flow_lookup_match_uuid,
+                                 sb_uuid);
+}
+
+static bool
+flow_lookup_match_conj(const struct desired_flow *candidate,
+                       const void *arg OVS_UNUSED)
+{
+    return flow_action_has_conj(&candidate->flow);
+}
+
+/* Finds and returns a desired_flow in 'flow_table' whose key is identical to
+ * 'target''s key, or NULL if there is none.
+ *
+ * The function will only return a matching flow if it contains action
+ * 'conjunction'.
+ */
+static struct desired_flow *
+desired_flow_lookup_conjunctive(struct ovn_desired_flow_table *flow_table,
+                                const struct ovn_flow *target)
+{
+    return desired_flow_lookup__(flow_table, target, flow_lookup_match_conj,
+                                 NULL);
+}
+
 /* Finds and returns an installed_flow in installed_flows whose key is
  * identical to 'target''s key, or NULL if there is none. */
 static struct installed_flow *
@@ -1653,8 +1741,7 @@  update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
     struct installed_flow *i, *next;
     HMAP_FOR_EACH_SAFE (i, next, match_hmap_node, &installed_flows) {
         unlink_all_refs_for_installed_flow(i);
-        struct desired_flow *d =
-            desired_flow_lookup(flow_table, &i->flow, NULL);
+        struct desired_flow *d = desired_flow_lookup(flow_table, &i->flow);
         if (!d) {
             /* Installed flow is no longer desirable.  Delete it from the
              * switch and from installed_flows. */
@@ -1687,6 +1774,18 @@  update_installed_flows_by_compare(struct ovn_desired_flow_table *flow_table,
             /* Copy 'd' from 'flow_table' to installed_flows. */
             i = installed_flow_dup(d);
             hmap_insert(&installed_flows, &i->match_hmap_node, i->flow.hash);
+        } else if (i->desired_flow != d) {
+            /* If a matching installed flow was found but its actions are
+             * conflicting with the desired flow actions, we should chose
+             * to install the least restrictive one (i.e., no conjunctive
+             * action).
+             */
+            if (flow_action_has_conj(&i->flow) &&
+                    !flow_action_has_conj(&d->flow)) {
+                flow_log_actions_conflict("Use new flow", &i->flow, &d->flow);
+                installed_flow_mod(&i->flow, &d->flow, msgs);
+                ovn_flow_log(&i->flow, "updating installed");
+            }
         }
         link_installed_to_desired(i, d);
     }
@@ -1817,7 +1916,19 @@  update_installed_flows_by_track(struct ovn_desired_flow_table *flow_table,
                 installed_flow_mod(&i->flow, &f->flow, msgs);
             } else {
                 /* Adding a new flow that conflicts with an existing installed
-                 * flow, so just add it to the link. */
+                 * flow, so just add it to the link.
+                 *
+                 * However, if the existing installed flow is less restrictive
+                 * (i.e., no conjunctive action), we should chose it over the
+                 * existing installed flow.
+                 */
+                if (flow_action_has_conj(&i->flow) &&
+                        !flow_action_has_conj(&f->flow)) {
+                    flow_log_actions_conflict("Use new flow",
+                                              &i->flow, &f->flow);
+                    ovn_flow_log(&i->flow, "updating installed (tracked)");
+                    installed_flow_mod(&i->flow, &f->flow, msgs);
+                }
                 link_installed_to_desired(i, f);
             }
             /* The track_list_node emptyness is used to check if the node is
diff --git a/tests/ovn.at b/tests/ovn.at
index 7769b69..6b77057 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -13709,6 +13709,201 @@  grep conjunction.*conjunction.*conjunction | wc -l`])
 OVN_CLEANUP([hv1])
 AT_CLEANUP
 
+AT_SETUP([ovn -- Superseeding ACLs with 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"
+
+ovn-nbctl lsp-add ls1 ls1-lp2 \
+-- lsp-set-addresses ls1-lp2 "f0:00:00:00:00:02"
+
+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
+
+# 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
+}
+
+# Add a default deny ACL and an allow ACL for specific IP traffic.
+ovn-nbctl acl-add ls1 to-lport 2 'arp' allow
+ovn-nbctl acl-add ls1 to-lport 1 'ip4' drop
+ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.2) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
+ovn-nbctl acl-add ls1 to-lport 3 '(ip4.src==10.0.0.1 || ip4.src==10.0.0.42) && (ip4.dst == 10.0.0.3 || ip4.dst == 10.0.0.4)' allow
+ovn-nbctl --wait=hv sync
+
+# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
+for src in `seq 1 2`; do
+    for dst in `seq 3 4`; do
+        sip=`ip_to_hex 10 0 0 $src`
+        dip=`ip_to_hex 10 0 0 $dst`
+
+        test_ip 1 f00000000001 f00000000002 $sip $dip 2
+    done
+done
+
+# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
+dip=`ip_to_hex 10 0 0 5`
+for src in `seq 1 2`; do
+    sip=`ip_to_hex 10 0 0 $src`
+
+    test_ip 1 f00000000001 f00000000002 $sip $dip
+done
+
+cat 2.expected > expout
+$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
+AT_CHECK([cat 2.packets], [0], [expout])
+reset_pcap_file hv1-vif2 hv1/vif2
+rm -f 2.packets
+> 2.expected
+
+# Add a less restrictive allow ACL for src IP 10.0.0.1
+ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
+ovn-nbctl --wait=hv sync
+
+# Check OVS flows, the less restrictive flows should have been installed.
+AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
+    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
+priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
+])
+
+# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
+for src in `seq 1 2`; do
+    for dst in `seq 3 4`; do
+        sip=`ip_to_hex 10 0 0 $src`
+        dip=`ip_to_hex 10 0 0 $dst`
+
+        test_ip 1 f00000000001 f00000000002 $sip $dip 2
+    done
+done
+
+# Traffic 10.0.0.2 -> 10.0.0.5 should be dropped.
+sip=`ip_to_hex 10 0 0 2`
+dip=`ip_to_hex 10 0 0 5`
+test_ip 1 f00000000001 f00000000002 $sip $dip
+
+# Traffic 10.0.0.1 -> 10.0.0.5 should be allowed.
+sip=`ip_to_hex 10 0 0 1`
+dip=`ip_to_hex 10 0 0 5`
+test_ip 1 f00000000001 f00000000002 $sip $dip 2
+
+cat 2.expected > expout
+$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
+AT_CHECK([cat 2.packets], [0], [expout])
+reset_pcap_file hv1-vif2 hv1/vif2
+rm -f 2.packets
+> 2.expected
+
+# Remove the less restrictive allow ACL.
+ovn-nbctl acl-del ls1 to-lport 3 'ip4.src==10.0.0.1'
+ovn-nbctl --wait=hv sync
+
+# Check OVS flows, the 10.0.0.1 conjunction should have been reinstalled.
+AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
+    grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
+priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=conjunction(2,2/2),conjunction(3,2/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
+])
+
+# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.3, 10.0.0.4 should be allowed.
+for src in `seq 1 2`; do
+    for dst in `seq 3 4`; do
+        sip=`ip_to_hex 10 0 0 $src`
+        dip=`ip_to_hex 10 0 0 $dst`
+
+        test_ip 1 f00000000001 f00000000002 $sip $dip 2
+    done
+done
+
+# Traffic 10.0.0.1, 10.0.0.2 -> 10.0.0.5 should be dropped.
+dip=`ip_to_hex 10 0 0 5`
+for src in `seq 1 2`; do
+    sip=`ip_to_hex 10 0 0 $src`
+
+    test_ip 1 f00000000001 f00000000002 $sip $dip
+done
+
+cat 2.expected > expout
+$PYTHON "$ovs_srcdir/utilities/ovs-pcap.in" hv1/vif2-tx.pcap > 2.packets
+AT_CHECK([cat 2.packets], [0], [expout])
+
+# Re-add the less restrictive allow ACL for src IP 10.0.0.1
+ovn-nbctl acl-add ls1 to-lport 3 'ip4.src==10.0.0.1' allow
+ovn-nbctl --wait=hv sync
+
+# Check OVS flows, the less restrictive flows should have been installed.
+AT_CHECK([as hv1 ovs-ofctl dump-flows br-int table=45 | \
+   grep "priority=1003" | awk '{print $7 " " $8}' | sort], [0], [dnl
+priority=1003,conj_id=2,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,conj_id=3,ip,metadata=0x1 actions=resubmit(,46)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.3 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_dst=10.0.0.4 actions=conjunction(2,1/2),conjunction(3,1/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.1 actions=resubmit(,46)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.2 actions=conjunction(2,2/2)
+priority=1003,ip,metadata=0x1,nw_src=10.0.0.42 actions=conjunction(3,2/2)
+])
+
+OVN_CLEANUP([hv1])
+AT_CLEANUP
+
 # 3 hypervisors, one logical switch, 3 logical ports per hypervisor
 AT_SETUP([ovn -- L2 Drop and Allow ACL w/ Stateful ACL])
 ovn_start