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

Dumitru Ceara dceara at redhat.com
Tue Oct 13 07:17:59 UTC 2020


On 10/13/20 8:58 AM, Han Zhou wrote:
> 
> 
> On Mon, Oct 12, 2020 at 3:16 AM Dumitru Ceara <dceara at redhat.com
> <mailto:dceara at 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 at redhat.com
> <mailto:dceara at redhat.com>
>> > <mailto:dceara at redhat.com <mailto: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>
> <mailto:dceara at redhat.com <mailto:dceara at redhat.com>>
>> >>>> <mailto:dceara at redhat.com <mailto:dceara at redhat.com>
> <mailto: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>
>> >>>>> <mailto:dalvarez at redhat.com <mailto:dalvarez at redhat.com>>
> <mailto:dalvarez at redhat.com <mailto:dalvarez at redhat.com>
>> >>>>> <mailto:dalvarez at redhat.com <mailto:dalvarez at redhat.com>>>> CC:
> Han Zhou <hzhou at ovn.org <mailto:hzhou at ovn.org>
>> >>>>> <mailto:hzhou at ovn.org <mailto:hzhou at ovn.org>>
> <mailto:hzhou at ovn.org <mailto:hzhou at ovn.org>
>> >>>>> <mailto: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>
> <mailto:mmichels at redhat.com <mailto:mmichels at redhat.com>>
>> >>>> <mailto:mmichels at redhat.com <mailto:mmichels at redhat.com>
> <mailto:mmichels at redhat.com <mailto:mmichels at redhat.com>>>>
>> >>>>> Signed-off-by: Dumitru Ceara <dceara at redhat.com
> <mailto:dceara at redhat.com>
>> >>>>> <mailto:dceara at redhat.com <mailto:dceara at redhat.com>>
>> >>>> <mailto:dceara at redhat.com <mailto:dceara at redhat.com>
> <mailto: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>
>> >>>>> <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




More information about the dev mailing list