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

Han Zhou hzhou at ovn.org
Sun Oct 11 19:40:44 UTC 2020


On Sun, Oct 11, 2020 at 5:14 AM Dumitru Ceara <dceara at 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 at redhat.com
> >> <mailto:dceara at 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 at redhat.com <mailto:dalvarez at redhat.com>>
> >>> CC: Han Zhou <hzhou at ovn.org <mailto:hzhou at ovn.org>>
> >>> Reported-at: https://bugzilla.redhat.com/1871931
> >>> Acked-by: Mark Michelson <mmichels at redhat.com
> >> <mailto:mmichels at redhat.com>>
> >>> Signed-off-by: Dumitru Ceara <dceara at redhat.com
> >> <mailto:dceara at 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.)


More information about the dev mailing list