[ovs-dev] lflow.c: Avoid adding redundant resource refs for port-bindings.

When a lport is referenced by a logical flow where port-binding refs
needs to be added, currently it can add the same reference pair multiple
times in below situations (introduced in commit ade4e77):

1) In add_matches_to_flow_table(), different matches from same lflow
   can have same inport/outport.

2) In is_chassis_resident_cb(), a lflow can have multiple is_chassis_resident
   check for same lport (although not very common), and at the same time
   the lport used in is_chassis_resident can overlap with the inport/
   outport of the same flow.

Now because of the redundant entries added, it results in unexpected behavior
such as same lflow being processed multiple times as a waste of processing.
More severely, after commit 580aea72e it can result in orphaned pointer leading
to crash, as reported in [0].

This patch fixes the problems by checking existance of same reference before
adding in lflow_resource_add(). To do this check efficiently, hmap is used to
replace the list struct for the resource-to-lflow index.

This patch also handles freeing the hmap entries in
lflow_resource_ref.ref_lflow_table, which was not addressed before.  Without
this it could result in memory growth continuously until a recompute is
triggered.

[0] https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html

Reported-by: Dumitru Ceara <dceara@redhat.com>
Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
Fixes: ade4e779d3fb ("ovn-controller: Use the tracked runtime data changes for flow calculation.")
Fixes: 580aea72e26f ("ovn-controller: Fix conjunction handling with incremental processing.")
Signed-off-by: Han Zhou <hzhou@ovn.org>
---
 controller/lflow.c | 62 +++++++++++++++++++++++++++++++++++++-----------------
 controller/lflow.h | 27 +++++++++++++-----------
 tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 107 insertions(+), 31 deletions(-)

Bleep bloop.  Greetings Han Zhou, I am a robot and I have tried out your patch.
Thanks for your contribution.

I encountered some error that I wasn't expecting.  See the details below.


checkpatch:
ERROR: Improper whitespace around control block
#110 FILE: controller/lflow.c:258:
        HMAP_FOR_EACH_WITH_HASH(n, hmap_node, uuid_hash(lflow_uuid),

Lines checked: 290, Warnings: 0, Errors: 1


Please check this out.  If you feel there has been an error, please email aconole@redhat.com

Thanks,
0-day Robot

On 9/15/20 10:15 AM, Han Zhou wrote:
> When a lport is referenced by a logical flow where port-binding refs
> needs to be added, currently it can add the same reference pair multiple
> times in below situations (introduced in commit ade4e77):
> 
> 1) In add_matches_to_flow_table(), different matches from same lflow
>    can have same inport/outport.
> 
> 2) In is_chassis_resident_cb(), a lflow can have multiple is_chassis_resident
>    check for same lport (although not very common), and at the same time
>    the lport used in is_chassis_resident can overlap with the inport/
>    outport of the same flow.
> 
> Now because of the redundant entries added, it results in unexpected behavior
> such as same lflow being processed multiple times as a waste of processing.
> More severely, after commit 580aea72e it can result in orphaned pointer leading
> to crash, as reported in [0].
> 
> This patch fixes the problems by checking existance of same reference before
> adding in lflow_resource_add(). To do this check efficiently, hmap is used to
> replace the list struct for the resource-to-lflow index.
> 
> This patch also handles freeing the hmap entries in
> lflow_resource_ref.ref_lflow_table, which was not addressed before.  Without
> this it could result in memory growth continuously until a recompute is
> triggered.
> 
> [0] https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
> 
> Reported-by: Dumitru Ceara <dceara@redhat.com>
> Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
> Fixes: ade4e779d3fb ("ovn-controller: Use the tracked runtime data changes for flow calculation.")
> Fixes: 580aea72e26f ("ovn-controller: Fix conjunction handling with incremental processing.")
> Signed-off-by: Han Zhou <hzhou@ovn.org>


Hi Han,

Thanks for the fix. This is not a complete review yet but I do have some
preliminary comments.

> ---
>  controller/lflow.c | 62 +++++++++++++++++++++++++++++++++++++-----------------
>  controller/lflow.h | 27 +++++++++++++-----------
>  tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 107 insertions(+), 31 deletions(-)
> 
> diff --git a/controller/lflow.c b/controller/lflow.c
> index e785866..2d2bbee 100644
> --- a/controller/lflow.c
> +++ b/controller/lflow.c
> @@ -156,20 +156,27 @@ lflow_resource_init(struct lflow_resource_ref *lfrr)
>      hmap_init(&lfrr->lflow_ref_table);
>  }
>  
> +static void
> +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
> +{
> +    free(rlfn->ref_name);
> +    hmap_destroy(&rlfn->lflow_uuids);
> +    free(rlfn);
> +}
> +
In my opinion it would be cleaner if we also have a function to do the
init/lookup part. Actually, I think this comment is valid for all
structures: ref_lflow_node, lflow_ref_node, lflow_resource_ref. It might
be a bit of additional code but now it's quite hard to follow what gets
created/destroyed where.

>  void
>  lflow_resource_destroy(struct lflow_resource_ref *lfrr)
>  {
>      struct ref_lflow_node *rlfn, *rlfn_next;
>      HMAP_FOR_EACH_SAFE (rlfn, rlfn_next, node, &lfrr->ref_lflow_table) {
> -        free(rlfn->ref_name);
>          struct lflow_ref_list_node *lrln, *next;
> -        LIST_FOR_EACH_SAFE (lrln, next, ref_list, &rlfn->ref_lflow_head) {
> -            ovs_list_remove(&lrln->ref_list);
> -            ovs_list_remove(&lrln->lflow_list);
> +        HMAP_FOR_EACH_SAFE (lrln, next, hmap_node, &rlfn->lflow_uuids) {
> +            ovs_list_remove(&lrln->list_node);
> +            hmap_remove(&rlfn->lflow_uuids, &lrln->hmap_node);
>              free(lrln);
>          }
>          hmap_remove(&lfrr->ref_lflow_table, &rlfn->node);
> -        free(rlfn);
> +        ref_lflow_node_destroy(rlfn);
>      }
>      hmap_destroy(&lfrr->ref_lflow_table);
>  
> @@ -222,6 +229,7 @@ static void
>  lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>                     const char *ref_name, const struct uuid *lflow_uuid)
>  {
> +    bool is_new = false;

I would avoid this variable because in my opinion it makes the code more
complicated to follow.

>      struct ref_lflow_node *rlfn = ref_lflow_lookup(&lfrr->ref_lflow_table,
>                                                     type, ref_name);
>      if (!rlfn) {
> @@ -229,8 +237,9 @@ lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>          rlfn->node.hash = hash_string(ref_name, type);
>          rlfn->type = type;
>          rlfn->ref_name = xstrdup(ref_name);
> -        ovs_list_init(&rlfn->ref_lflow_head);
> +        hmap_init(&rlfn->lflow_uuids);
>          hmap_insert(&lfrr->ref_lflow_table, &rlfn->node, rlfn->node.hash);
> +        is_new = true;
>      }
>  
>      struct lflow_ref_node *lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table,
> @@ -241,12 +250,24 @@ lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>          lfrn->lflow_uuid = *lflow_uuid;
>          ovs_list_init(&lfrn->lflow_ref_head);
>          hmap_insert(&lfrr->lflow_ref_table, &lfrn->node, lfrn->node.hash);
> +        is_new = true;
>      }
>  
> +    if (!is_new) {
> +        struct lflow_ref_list_node *n;
> +        HMAP_FOR_EACH_WITH_HASH(n, hmap_node, uuid_hash(lflow_uuid),
> +                                &rlfn->lflow_uuids) {
> +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
> +                /* The mapping already existed */
> +                return;
> +            }
> +        }
> +    }
>      struct lflow_ref_list_node *lrln = xzalloc(sizeof *lrln);
>      lrln->lflow_uuid = *lflow_uuid;
> -    ovs_list_push_back(&rlfn->ref_lflow_head, &lrln->ref_list);
> -    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->lflow_list);
> +    lrln->rlfn = rlfn;
> +    hmap_insert(&rlfn->lflow_uuids, &lrln->hmap_node, uuid_hash(lflow_uuid));
> +    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->list_node);
>  }

I think rewriting this function in a different way might make it more
readable. E.g., pseudocode:

rlfn = ref_lflow_lookup(&lfrr->ref_lflow_table, type, ref_name);
lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table, lflow_uuid);

if (rlfn && lfrn) {
    /* Check for duplicates here. */
} else {
    if (!rlfn) {
        /* Allocate, init, insert rlfn. */
        /* Maybe we can have a function for this? */
    }
    if (!lfrn) {
        /* Allocate, init, insert lfrn. */
        /* Maybe we can have a function for this? */
    }
}

/* Allocate, init, insert lrln. */
[...]

Also, it might be me but these variable names are so close to each other
that it's quite confusing. Maybe we can find some more explicit names?

>  
>  static void
> @@ -261,9 +282,13 @@ lflow_resource_destroy_lflow(struct lflow_resource_ref *lfrr,
>  
>      hmap_remove(&lfrr->lflow_ref_table, &lfrn->node);
>      struct lflow_ref_list_node *lrln, *next;
> -    LIST_FOR_EACH_SAFE (lrln, next, lflow_list, &lfrn->lflow_ref_head) {
> -        ovs_list_remove(&lrln->ref_list);
> -        ovs_list_remove(&lrln->lflow_list);
> +    LIST_FOR_EACH_SAFE (lrln, next, list_node, &lfrn->lflow_ref_head) {
> +        ovs_list_remove(&lrln->list_node);
> +        hmap_remove(&lrln->rlfn->lflow_uuids, &lrln->hmap_node);

I think a comment here explaining why we can't remove the node would be
helpful.

Thanks,
Dumitru

> +        if (hmap_is_empty(&lrln->rlfn->lflow_uuids)) {
> +            hmap_remove(&lfrr->ref_lflow_table, &lrln->rlfn->node);
> +            ref_lflow_node_destroy(lrln->rlfn);
> +        }
>          free(lrln);
>      }
>      free(lfrn);
> @@ -531,12 +556,12 @@ lflow_handle_changed_ref(enum ref_type ref_type, const char *ref_name,
>      hmap_remove(&l_ctx_out->lfrr->ref_lflow_table, &rlfn->node);
>  
>      struct lflow_ref_list_node *lrln, *next;
> -    /* Detach the rlfn->ref_lflow_head nodes from the lfrr table and clean
> +    /* Detach the rlfn->lflow_uuids nodes from the lfrr table and clean
>       * up all other nodes related to the lflows that uses the resource,
>       * so that the old nodes won't interfere with updating the lfrr table
>       * when reparsing the lflows. */
> -    LIST_FOR_EACH (lrln, ref_list, &rlfn->ref_lflow_head) {
> -        ovs_list_remove(&lrln->lflow_list);
> +    HMAP_FOR_EACH (lrln, hmap_node, &rlfn->lflow_uuids) {
> +        ovs_list_remove(&lrln->list_node);
>      }
>  
>      struct hmap dhcp_opts = HMAP_INITIALIZER(&dhcp_opts);
> @@ -565,7 +590,7 @@ lflow_handle_changed_ref(enum ref_type ref_type, const char *ref_name,
>      /* Firstly, flood remove the flows from desired flow table. */
>      struct hmap flood_remove_nodes = HMAP_INITIALIZER(&flood_remove_nodes);
>      struct ofctrl_flood_remove_node *ofrn, *ofrn_next;
> -    LIST_FOR_EACH (lrln, ref_list, &rlfn->ref_lflow_head) {
> +    HMAP_FOR_EACH (lrln, hmap_node, &rlfn->lflow_uuids) {
>          VLOG_DBG("Reprocess lflow "UUID_FMT" for resource type: %d,"
>                   " name: %s.",
>                   UUID_ARGS(&lrln->lflow_uuid),
> @@ -604,12 +629,11 @@ lflow_handle_changed_ref(enum ref_type ref_type, const char *ref_name,
>      }
>      hmap_destroy(&flood_remove_nodes);
>  
> -    LIST_FOR_EACH_SAFE (lrln, next, ref_list, &rlfn->ref_lflow_head) {
> -        ovs_list_remove(&lrln->ref_list);
> +    HMAP_FOR_EACH_SAFE (lrln, next, hmap_node, &rlfn->lflow_uuids) {
> +        hmap_remove(&rlfn->lflow_uuids, &lrln->hmap_node);
>          free(lrln);
>      }
> -    free(rlfn->ref_name);
> -    free(rlfn);
> +    ref_lflow_node_destroy(rlfn);
>  
>      dhcp_opts_destroy(&dhcp_opts);
>      dhcp_opts_destroy(&dhcpv6_opts);
> diff --git a/controller/lflow.h b/controller/lflow.h
> index c66b318..1251fb0 100644
> --- a/controller/lflow.h
> +++ b/controller/lflow.h
> @@ -78,25 +78,28 @@ enum ref_type {
>      REF_TYPE_PORTBINDING
>  };
>  
> -/* Maintains the relationship for a pair of named resource and
> - * a lflow, indexed by both ref_lflow_table and lflow_ref_table. */
> -struct lflow_ref_list_node {
> -    struct ovs_list lflow_list; /* list for same lflow */
> -    struct ovs_list ref_list; /* list for same ref */
> -    struct uuid lflow_uuid;
> -};
> -
>  struct ref_lflow_node {
> -    struct hmap_node node;
> +    struct hmap_node node; /* node in lflow_resource_ref.ref_lflow_table. */
>      enum ref_type type; /* key */
>      char *ref_name; /* key */
> -    struct ovs_list ref_lflow_head;
> +    struct hmap lflow_uuids; /* Contains lflow_ref_list_node. Use hmap instead
> +                                of list so that lflow_resource_add() can check
> +                                and avoid adding redundant entires in O(1). */
>  };
>  
>  struct lflow_ref_node {
> -    struct hmap_node node;
> +    struct hmap_node node; /* node in lflow_resource_ref.lflow_ref_table. */
>      struct uuid lflow_uuid; /* key */
> -    struct ovs_list lflow_ref_head;
> +    struct ovs_list lflow_ref_head; /* Contains lflow_ref_list_node. */
> +};
> +
> +/* Maintains the relationship for a pair of named resource and
> + * a lflow, indexed by both ref_lflow_table and lflow_ref_table. */
> +struct lflow_ref_list_node {
> +    struct ovs_list list_node; /* node in lflow_ref_node.lflow_ref_head. */
> +    struct hmap_node hmap_node; /* node in ref_lflow_node.lflow_uuids. */
> +    struct uuid lflow_uuid;
> +    struct ref_lflow_node *rlfn;
>  };
>  
>  struct lflow_resource_ref {
> diff --git a/tests/ovn.at b/tests/ovn.at
> index 41fe577..d368fb9 100644
> --- a/tests/ovn.at
> +++ b/tests/ovn.at
> @@ -22117,3 +22117,52 @@ OVN_CHECK_PACKETS([hv1/vif1-tx.pcap], [1.expected])
>  
>  OVN_CLEANUP([hv1])
>  AT_CLEANUP
> +
> +AT_SETUP([ovn -- port bind/unbind change handling with conj flows - IPv6])
> +ovn_start
> +
> +ovn-nbctl ls-add ls1
> +
> +ovn-nbctl lsp-add ls1 lsp1 \
> +    -- lsp-set-addresses lsp1 "f0:00:00:00:00:01 2001::1" \
> +    -- lsp-set-port-security lsp1 "f0:00:00:00:00:01 2001::1"
> +
> +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=lsp1 \
> +    options:tx_pcap=hv1/vif1-tx.pcap \
> +    options:rxq_pcap=hv1/vif1-rx.pcap \
> +    ofport-request=1
> +
> +ovn-nbctl --wait=hv sync
> +
> +# Expected conjunction flows:
> +# ... nd_tll=00:00:00:00:00:00 actions=conjunction(2,2/2)
> +# ... nd_tll=f0:00:00:00:00:01 actions=conjunction(2,2/2)
> +# ... nd_target=fe80::f200:ff:fe00:1 actions=conjunction(2,1/2)
> +# ... nd_target=2001::1 actions=conjunction(2,1/2)
> +OVS_WAIT_UNTIL([test 4 = `as hv1 ovs-ofctl dump-flows br-int | \
> +grep conjunction | wc -l`])
> +
> +# unbind the port
> +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=foo
> +OVS_WAIT_UNTIL([test 0 = `as hv1 ovs-ofctl dump-flows br-int | \
> +grep conjunction | wc -l`])
> +
> +# bind the port again
> +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=lsp1
> +OVS_WAIT_UNTIL([test 4 = `as hv1 ovs-ofctl dump-flows br-int | \
> +grep conjunction | wc -l`])
> +
> +# unbind the port again
> +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=foo
> +OVS_WAIT_UNTIL([test 0 = `as hv1 ovs-ofctl dump-flows br-int | \
> +grep conjunction | wc -l`])
> +
> +OVN_CLEANUP([hv1])
> +AT_CLEANUP
>

On Tue, Sep 15, 2020 at 8:19 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On 9/15/20 10:15 AM, Han Zhou wrote:
> > When a lport is referenced by a logical flow where port-binding refs
> > needs to be added, currently it can add the same reference pair multiple
> > times in below situations (introduced in commit ade4e77):
> >
> > 1) In add_matches_to_flow_table(), different matches from same lflow
> >    can have same inport/outport.
> >
> > 2) In is_chassis_resident_cb(), a lflow can have multiple
is_chassis_resident
> >    check for same lport (although not very common), and at the same time
> >    the lport used in is_chassis_resident can overlap with the inport/
> >    outport of the same flow.
> >
> > Now because of the redundant entries added, it results in unexpected
behavior
> > such as same lflow being processed multiple times as a waste of
processing.
> > More severely, after commit 580aea72e it can result in orphaned pointer
leading
> > to crash, as reported in [0].
> >
> > This patch fixes the problems by checking existance of same reference
before
> > adding in lflow_resource_add(). To do this check efficiently, hmap is
used to
> > replace the list struct for the resource-to-lflow index.
> >
> > This patch also handles freeing the hmap entries in
> > lflow_resource_ref.ref_lflow_table, which was not addressed before.
Without
> > this it could result in memory growth continuously until a recompute is
> > triggered.
> >
> > [0]
https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
> >
> > Reported-by: Dumitru Ceara <dceara@redhat.com>
> > Reported-at:
https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
> > Fixes: ade4e779d3fb ("ovn-controller: Use the tracked runtime data
changes for flow calculation.")
> > Fixes: 580aea72e26f ("ovn-controller: Fix conjunction handling with
incremental processing.")
> > Signed-off-by: Han Zhou <hzhou@ovn.org>
>
>
> Hi Han,
>
> Thanks for the fix. This is not a complete review yet but I do have some
> preliminary comments.
>
Hi Dumitru,

Thanks for your review. I addressed some of your comment in v2:
https://patchwork.ozlabs.org/project/ovn/list/?series=201891
To avoid more confusion I moved the part that is not directly related to
the fix to a separate patch in the series.
Please see my response below to your comments.

> > ---
> >  controller/lflow.c | 62
+++++++++++++++++++++++++++++++++++++-----------------
> >  controller/lflow.h | 27 +++++++++++++-----------
> >  tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 107 insertions(+), 31 deletions(-)
> >
> > diff --git a/controller/lflow.c b/controller/lflow.c
> > index e785866..2d2bbee 100644
> > --- a/controller/lflow.c
> > +++ b/controller/lflow.c
> > @@ -156,20 +156,27 @@ lflow_resource_init(struct lflow_resource_ref
*lfrr)
> >      hmap_init(&lfrr->lflow_ref_table);
> >  }
> >
> > +static void
> > +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
> > +{
> > +    free(rlfn->ref_name);
> > +    hmap_destroy(&rlfn->lflow_uuids);
> > +    free(rlfn);
> > +}
> > +
> In my opinion it would be cleaner if we also have a function to do the
> init/lookup part. Actually, I think this comment is valid for all
> structures: ref_lflow_node, lflow_ref_node, lflow_resource_ref. It might
> be a bit of additional code but now it's quite hard to follow what gets
> created/destroyed where.
>
In fact we have the lookup functions already. For destroy, the struct
ref_lflow_node is the only one that needs a function to wrap the destroy,
because it has a string to free and a hmap to destroy. For the other nodes
it is just free().

In v2 I put this new function together with the other static functions so
that it is easier to follow. (To avoid moving all the earlier functions
which would add more noise for the code review, I added the function
prototypes for the related static functions).

> >  void
> >  lflow_resource_destroy(struct lflow_resource_ref *lfrr)
> >  {
> >      struct ref_lflow_node *rlfn, *rlfn_next;
> >      HMAP_FOR_EACH_SAFE (rlfn, rlfn_next, node, &lfrr->ref_lflow_table)
{
> > -        free(rlfn->ref_name);
> >          struct lflow_ref_list_node *lrln, *next;
> > -        LIST_FOR_EACH_SAFE (lrln, next, ref_list,
&rlfn->ref_lflow_head) {
> > -            ovs_list_remove(&lrln->ref_list);
> > -            ovs_list_remove(&lrln->lflow_list);
> > +        HMAP_FOR_EACH_SAFE (lrln, next, hmap_node, &rlfn->lflow_uuids)
{
> > +            ovs_list_remove(&lrln->list_node);
> > +            hmap_remove(&rlfn->lflow_uuids, &lrln->hmap_node);
> >              free(lrln);
> >          }
> >          hmap_remove(&lfrr->ref_lflow_table, &rlfn->node);
> > -        free(rlfn);
> > +        ref_lflow_node_destroy(rlfn);
> >      }
> >      hmap_destroy(&lfrr->ref_lflow_table);
> >
> > @@ -222,6 +229,7 @@ static void
> >  lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
> >                     const char *ref_name, const struct uuid *lflow_uuid)
> >  {
> > +    bool is_new = false;
>
> I would avoid this variable because in my opinion it makes the code more
> complicated to follow.
>
Ack. I revised the function as suggested. I didn't add extra functions for
init, because all the allocations happen in this function only, and the
function is small and clear.

> >      struct ref_lflow_node *rlfn =
ref_lflow_lookup(&lfrr->ref_lflow_table,
> >                                                     type, ref_name);
> >      if (!rlfn) {
> > @@ -229,8 +237,9 @@ lflow_resource_add(struct lflow_resource_ref *lfrr,
enum ref_type type,
> >          rlfn->node.hash = hash_string(ref_name, type);
> >          rlfn->type = type;
> >          rlfn->ref_name = xstrdup(ref_name);
> > -        ovs_list_init(&rlfn->ref_lflow_head);
> > +        hmap_init(&rlfn->lflow_uuids);
> >          hmap_insert(&lfrr->ref_lflow_table, &rlfn->node,
rlfn->node.hash);
> > +        is_new = true;
> >      }
> >
> >      struct lflow_ref_node *lfrn =
lflow_ref_lookup(&lfrr->lflow_ref_table,
> > @@ -241,12 +250,24 @@ lflow_resource_add(struct lflow_resource_ref
*lfrr, enum ref_type type,
> >          lfrn->lflow_uuid = *lflow_uuid;
> >          ovs_list_init(&lfrn->lflow_ref_head);
> >          hmap_insert(&lfrr->lflow_ref_table, &lfrn->node,
lfrn->node.hash);
> > +        is_new = true;
> >      }
> >
> > +    if (!is_new) {
> > +        struct lflow_ref_list_node *n;
> > +        HMAP_FOR_EACH_WITH_HASH(n, hmap_node, uuid_hash(lflow_uuid),
> > +                                &rlfn->lflow_uuids) {
> > +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
> > +                /* The mapping already existed */
> > +                return;
> > +            }
> > +        }
> > +    }
> >      struct lflow_ref_list_node *lrln = xzalloc(sizeof *lrln);
> >      lrln->lflow_uuid = *lflow_uuid;
> > -    ovs_list_push_back(&rlfn->ref_lflow_head, &lrln->ref_list);
> > -    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->lflow_list);
> > +    lrln->rlfn = rlfn;
> > +    hmap_insert(&rlfn->lflow_uuids, &lrln->hmap_node,
uuid_hash(lflow_uuid));
> > +    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->list_node);
> >  }
>
> I think rewriting this function in a different way might make it more
> readable. E.g., pseudocode:
>
> rlfn = ref_lflow_lookup(&lfrr->ref_lflow_table, type, ref_name);
> lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table, lflow_uuid);
>
> if (rlfn && lfrn) {
>     /* Check for duplicates here. */
> } else {
>     if (!rlfn) {
>         /* Allocate, init, insert rlfn. */
>         /* Maybe we can have a function for this? */
>     }
>     if (!lfrn) {
>         /* Allocate, init, insert lfrn. */
>         /* Maybe we can have a function for this? */
>     }
> }
>
> /* Allocate, init, insert lrln. */
> [...]
>
> Also, it might be me but these variable names are so close to each other
> that it's quite confusing. Maybe we can find some more explicit names?
>
> >
> >  static void
> > @@ -261,9 +282,13 @@ lflow_resource_destroy_lflow(struct
lflow_resource_ref *lfrr,
> >
> >      hmap_remove(&lfrr->lflow_ref_table, &lfrn->node);
> >      struct lflow_ref_list_node *lrln, *next;
> > -    LIST_FOR_EACH_SAFE (lrln, next, lflow_list, &lfrn->lflow_ref_head)
{
> > -        ovs_list_remove(&lrln->ref_list);
> > -        ovs_list_remove(&lrln->lflow_list);
> > +    LIST_FOR_EACH_SAFE (lrln, next, list_node, &lfrn->lflow_ref_head) {
> > +        ovs_list_remove(&lrln->list_node);
> > +        hmap_remove(&lrln->rlfn->lflow_uuids, &lrln->hmap_node);
>
> I think a comment here explaining why we can't remove the node would be
> helpful.

Sorry, I didn't get it. We do remove the node here. Let me explain.
Originally both directions of the references are linked lists. Now one of
the directions is replaced by hmap, as explained in the commit message.
The change here merely replaces the operation ovs_list_remove operation to
hmap_remove operation for the direction that has the data structure change.
The other line is also updated because of the rename of the list node field
(because the older field names were more confusing).

Thanks,
Han

>
> Thanks,
> Dumitru
>
> > +        if (hmap_is_empty(&lrln->rlfn->lflow_uuids)) {
> > +            hmap_remove(&lfrr->ref_lflow_table, &lrln->rlfn->node);
> > +            ref_lflow_node_destroy(lrln->rlfn);
> > +        }
> >          free(lrln);
> >      }
> >      free(lfrn);
> > @@ -531,12 +556,12 @@ lflow_handle_changed_ref(enum ref_type ref_type,
const char *ref_name,
> >      hmap_remove(&l_ctx_out->lfrr->ref_lflow_table, &rlfn->node);
> >
> >      struct lflow_ref_list_node *lrln, *next;
> > -    /* Detach the rlfn->ref_lflow_head nodes from the lfrr table and
clean
> > +    /* Detach the rlfn->lflow_uuids nodes from the lfrr table and clean
> >       * up all other nodes related to the lflows that uses the resource,
> >       * so that the old nodes won't interfere with updating the lfrr
table
> >       * when reparsing the lflows. */
> > -    LIST_FOR_EACH (lrln, ref_list, &rlfn->ref_lflow_head) {
> > -        ovs_list_remove(&lrln->lflow_list);
> > +    HMAP_FOR_EACH (lrln, hmap_node, &rlfn->lflow_uuids) {
> > +        ovs_list_remove(&lrln->list_node);
> >      }
> >
> >      struct hmap dhcp_opts = HMAP_INITIALIZER(&dhcp_opts);
> > @@ -565,7 +590,7 @@ lflow_handle_changed_ref(enum ref_type ref_type,
const char *ref_name,
> >      /* Firstly, flood remove the flows from desired flow table. */
> >      struct hmap flood_remove_nodes =
HMAP_INITIALIZER(&flood_remove_nodes);
> >      struct ofctrl_flood_remove_node *ofrn, *ofrn_next;
> > -    LIST_FOR_EACH (lrln, ref_list, &rlfn->ref_lflow_head) {
> > +    HMAP_FOR_EACH (lrln, hmap_node, &rlfn->lflow_uuids) {
> >          VLOG_DBG("Reprocess lflow "UUID_FMT" for resource type: %d,"
> >                   " name: %s.",
> >                   UUID_ARGS(&lrln->lflow_uuid),
> > @@ -604,12 +629,11 @@ lflow_handle_changed_ref(enum ref_type ref_type,
const char *ref_name,
> >      }
> >      hmap_destroy(&flood_remove_nodes);
> >
> > -    LIST_FOR_EACH_SAFE (lrln, next, ref_list, &rlfn->ref_lflow_head) {
> > -        ovs_list_remove(&lrln->ref_list);
> > +    HMAP_FOR_EACH_SAFE (lrln, next, hmap_node, &rlfn->lflow_uuids) {
> > +        hmap_remove(&rlfn->lflow_uuids, &lrln->hmap_node);
> >          free(lrln);
> >      }
> > -    free(rlfn->ref_name);
> > -    free(rlfn);
> > +    ref_lflow_node_destroy(rlfn);
> >
> >      dhcp_opts_destroy(&dhcp_opts);
> >      dhcp_opts_destroy(&dhcpv6_opts);
> > diff --git a/controller/lflow.h b/controller/lflow.h
> > index c66b318..1251fb0 100644
> > --- a/controller/lflow.h
> > +++ b/controller/lflow.h
> > @@ -78,25 +78,28 @@ enum ref_type {
> >      REF_TYPE_PORTBINDING
> >  };
> >
> > -/* Maintains the relationship for a pair of named resource and
> > - * a lflow, indexed by both ref_lflow_table and lflow_ref_table. */
> > -struct lflow_ref_list_node {
> > -    struct ovs_list lflow_list; /* list for same lflow */
> > -    struct ovs_list ref_list; /* list for same ref */
> > -    struct uuid lflow_uuid;
> > -};
> > -
> >  struct ref_lflow_node {
> > -    struct hmap_node node;
> > +    struct hmap_node node; /* node in
lflow_resource_ref.ref_lflow_table. */
> >      enum ref_type type; /* key */
> >      char *ref_name; /* key */
> > -    struct ovs_list ref_lflow_head;
> > +    struct hmap lflow_uuids; /* Contains lflow_ref_list_node. Use hmap
instead
> > +                                of list so that lflow_resource_add()
can check
> > +                                and avoid adding redundant entires in
O(1). */
> >  };
> >
> >  struct lflow_ref_node {
> > -    struct hmap_node node;
> > +    struct hmap_node node; /* node in
lflow_resource_ref.lflow_ref_table. */
> >      struct uuid lflow_uuid; /* key */
> > -    struct ovs_list lflow_ref_head;
> > +    struct ovs_list lflow_ref_head; /* Contains lflow_ref_list_node. */
> > +};
> > +
> > +/* Maintains the relationship for a pair of named resource and
> > + * a lflow, indexed by both ref_lflow_table and lflow_ref_table. */
> > +struct lflow_ref_list_node {
> > +    struct ovs_list list_node; /* node in
lflow_ref_node.lflow_ref_head. */
> > +    struct hmap_node hmap_node; /* node in ref_lflow_node.lflow_uuids.
*/
> > +    struct uuid lflow_uuid;
> > +    struct ref_lflow_node *rlfn;
> >  };
> >
> >  struct lflow_resource_ref {
> > diff --git a/tests/ovn.at b/tests/ovn.at
> > index 41fe577..d368fb9 100644
> > --- a/tests/ovn.at
> > +++ b/tests/ovn.at
> > @@ -22117,3 +22117,52 @@ OVN_CHECK_PACKETS([hv1/vif1-tx.pcap],
[1.expected])
> >
> >  OVN_CLEANUP([hv1])
> >  AT_CLEANUP
> > +
> > +AT_SETUP([ovn -- port bind/unbind change handling with conj flows -
IPv6])
> > +ovn_start
> > +
> > +ovn-nbctl ls-add ls1
> > +
> > +ovn-nbctl lsp-add ls1 lsp1 \
> > +    -- lsp-set-addresses lsp1 "f0:00:00:00:00:01 2001::1" \
> > +    -- lsp-set-port-security lsp1 "f0:00:00:00:00:01 2001::1"
> > +
> > +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=lsp1 \
> > +    options:tx_pcap=hv1/vif1-tx.pcap \
> > +    options:rxq_pcap=hv1/vif1-rx.pcap \
> > +    ofport-request=1
> > +
> > +ovn-nbctl --wait=hv sync
> > +
> > +# Expected conjunction flows:
> > +# ... nd_tll=00:00:00:00:00:00 actions=conjunction(2,2/2)
> > +# ... nd_tll=f0:00:00:00:00:01 actions=conjunction(2,2/2)
> > +# ... nd_target=fe80::f200:ff:fe00:1 actions=conjunction(2,1/2)
> > +# ... nd_target=2001::1 actions=conjunction(2,1/2)
> > +OVS_WAIT_UNTIL([test 4 = `as hv1 ovs-ofctl dump-flows br-int | \
> > +grep conjunction | wc -l`])
> > +
> > +# unbind the port
> > +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=foo
> > +OVS_WAIT_UNTIL([test 0 = `as hv1 ovs-ofctl dump-flows br-int | \
> > +grep conjunction | wc -l`])
> > +
> > +# bind the port again
> > +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=lsp1
> > +OVS_WAIT_UNTIL([test 4 = `as hv1 ovs-ofctl dump-flows br-int | \
> > +grep conjunction | wc -l`])
> > +
> > +# unbind the port again
> > +ovs-vsctl set interface hv1-vif1 external_ids:iface-id=foo
> > +OVS_WAIT_UNTIL([test 0 = `as hv1 ovs-ofctl dump-flows br-int | \
> > +grep conjunction | wc -l`])
> > +
> > +OVN_CLEANUP([hv1])
> > +AT_CLEANUP
> >
>

On 9/15/20 9:14 PM, Han Zhou wrote:
> 
> 
> On Tue, Sep 15, 2020 at 8:19 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>> wrote:
>>
>> On 9/15/20 10:15 AM, Han Zhou wrote:
>> > When a lport is referenced by a logical flow where port-binding refs
>> > needs to be added, currently it can add the same reference pair multiple
>> > times in below situations (introduced in commit ade4e77):
>> >
>> > 1) In add_matches_to_flow_table(), different matches from same lflow
>> >    can have same inport/outport.
>> >
>> > 2) In is_chassis_resident_cb(), a lflow can have multiple
> is_chassis_resident
>> >    check for same lport (although not very common), and at the same time
>> >    the lport used in is_chassis_resident can overlap with the inport/
>> >    outport of the same flow.
>> >
>> > Now because of the redundant entries added, it results in unexpected
> behavior
>> > such as same lflow being processed multiple times as a waste of
> processing.
>> > More severely, after commit 580aea72e it can result in orphaned
> pointer leading
>> > to crash, as reported in [0].
>> >
>> > This patch fixes the problems by checking existance of same
> reference before
>> > adding in lflow_resource_add(). To do this check efficiently, hmap
> is used to
>> > replace the list struct for the resource-to-lflow index.
>> >
>> > This patch also handles freeing the hmap entries in
>> > lflow_resource_ref.ref_lflow_table, which was not addressed before. 
> Without
>> > this it could result in memory growth continuously until a recompute is
>> > triggered.
>> >
>> > [0]
> https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
>> >
>> > Reported-by: Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>>
>> > Reported-at:
> https://mail.openvswitch.org/pipermail/ovs-dev/2020-September/374991.html
>> > Fixes: ade4e779d3fb ("ovn-controller: Use the tracked runtime data
> changes for flow calculation.")
>> > Fixes: 580aea72e26f ("ovn-controller: Fix conjunction handling with
> incremental processing.")
>> > Signed-off-by: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>>
>>
>>
>> Hi Han,
>>
>> Thanks for the fix. This is not a complete review yet but I do have some
>> preliminary comments.
>>
> Hi Dumitru,
> 
> Thanks for your review. I addressed some of your comment in v2:
> https://patchwork.ozlabs.org/project/ovn/list/?series=201891
> To avoid more confusion I moved the part that is not directly related to
> the fix to a separate patch in the series.
> Please see my response below to your comments.
> 
>> > ---
>> >  controller/lflow.c | 62
> +++++++++++++++++++++++++++++++++++++-----------------
>> >  controller/lflow.h | 27 +++++++++++++-----------
>> >  tests/ovn.at <http://ovn.at>       | 49
> ++++++++++++++++++++++++++++++++++++++++++
>> >  3 files changed, 107 insertions(+), 31 deletions(-)
>> >
>> > diff --git a/controller/lflow.c b/controller/lflow.c
>> > index e785866..2d2bbee 100644
>> > --- a/controller/lflow.c
>> > +++ b/controller/lflow.c
>> > @@ -156,20 +156,27 @@ lflow_resource_init(struct lflow_resource_ref
> *lfrr)
>> >      hmap_init(&lfrr->lflow_ref_table);
>> >  }
>> >
>> > +static void
>> > +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
>> > +{
>> > +    free(rlfn->ref_name);
>> > +    hmap_destroy(&rlfn->lflow_uuids);
>> > +    free(rlfn);
>> > +}
>> > +
>> In my opinion it would be cleaner if we also have a function to do the
>> init/lookup part. Actually, I think this comment is valid for all
>> structures: ref_lflow_node, lflow_ref_node, lflow_resource_ref. It might
>> be a bit of additional code but now it's quite hard to follow what gets
>> created/destroyed where.
>>
> In fact we have the lookup functions already. For destroy, the struct
> ref_lflow_node is the only one that needs a function to wrap the
> destroy, because it has a string to free and a hmap to destroy. For the
> other nodes it is just free().
> 

Hi Han,

It's confusing for me if we have a ref_lflow_node_destroy() function and
not a ref_lflow_node_create().

Also I'd prefer having a ref_lflow_node_contains(const struct
ref_lflow_node *, const struct uuid *) instead of doing the hashmap
lookup directly inside lflow_resource_add().

Now that we're discussing this part of the code, a side question:
why doesn't lflow_resource_destroy() call
lflow_resource_destroy_lflow()? They seem to share quite a lot of code
or am I missing something?

I'll have a look at v2 soon.

> In v2 I put this new function together with the other static functions
> so that it is easier to follow. (To avoid moving all the earlier
> functions which would add more noise for the code review, I added the
> function prototypes for the related static functions).
> 
>> >  void
>> >  lflow_resource_destroy(struct lflow_resource_ref *lfrr)
>> >  {
>> >      struct ref_lflow_node *rlfn, *rlfn_next;
>> >      HMAP_FOR_EACH_SAFE (rlfn, rlfn_next, node,
> &lfrr->ref_lflow_table) {
>> > -        free(rlfn->ref_name);
>> >          struct lflow_ref_list_node *lrln, *next;
>> > -        LIST_FOR_EACH_SAFE (lrln, next, ref_list,
> &rlfn->ref_lflow_head) {
>> > -            ovs_list_remove(&lrln->ref_list);
>> > -            ovs_list_remove(&lrln->lflow_list);
>> > +        HMAP_FOR_EACH_SAFE (lrln, next, hmap_node,
> &rlfn->lflow_uuids) {
>> > +            ovs_list_remove(&lrln->list_node);
>> > +            hmap_remove(&rlfn->lflow_uuids, &lrln->hmap_node);
>> >              free(lrln);
>> >          }
>> >          hmap_remove(&lfrr->ref_lflow_table, &rlfn->node);
>> > -        free(rlfn);
>> > +        ref_lflow_node_destroy(rlfn);
>> >      }
>> >      hmap_destroy(&lfrr->ref_lflow_table);
>> >
>> > @@ -222,6 +229,7 @@ static void
>> >  lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>> >                     const char *ref_name, const struct uuid *lflow_uuid)
>> >  {
>> > +    bool is_new = false;
>>
>> I would avoid this variable because in my opinion it makes the code more
>> complicated to follow.
>>
> Ack. I revised the function as suggested. I didn't add extra functions
> for init, because all the allocations happen in this function only, and
> the function is small and clear.
>

In my opinion it's more clear if we separate the initialization part for
each data structure. Adding a function, ref_lflow_node_create(),
wouldn't make the lflow_resource_add() less clear and would also make it
less error prone if we ever decide to create struct rel_lflow_node
objects in other parts of the code in the future.

>> >      struct ref_lflow_node *rlfn =
> ref_lflow_lookup(&lfrr->ref_lflow_table,
>> >                                                     type, ref_name);
>> >      if (!rlfn) {
>> > @@ -229,8 +237,9 @@ lflow_resource_add(struct lflow_resource_ref
> *lfrr, enum ref_type type,
>> >          rlfn->node.hash = hash_string(ref_name, type);
>> >          rlfn->type = type;
>> >          rlfn->ref_name = xstrdup(ref_name);
>> > -        ovs_list_init(&rlfn->ref_lflow_head);
>> > +        hmap_init(&rlfn->lflow_uuids);
>> >          hmap_insert(&lfrr->ref_lflow_table, &rlfn->node,
> rlfn->node.hash);
>> > +        is_new = true;
>> >      }
>> >
>> >      struct lflow_ref_node *lfrn =
> lflow_ref_lookup(&lfrr->lflow_ref_table,
>> > @@ -241,12 +250,24 @@ lflow_resource_add(struct lflow_resource_ref
> *lfrr, enum ref_type type,
>> >          lfrn->lflow_uuid = *lflow_uuid;
>> >          ovs_list_init(&lfrn->lflow_ref_head);
>> >          hmap_insert(&lfrr->lflow_ref_table, &lfrn->node,
> lfrn->node.hash);
>> > +        is_new = true;
>> >      }
>> >
>> > +    if (!is_new) {
>> > +        struct lflow_ref_list_node *n;
>> > +        HMAP_FOR_EACH_WITH_HASH(n, hmap_node, uuid_hash(lflow_uuid),
>> > +                                &rlfn->lflow_uuids) {
>> > +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
>> > +                /* The mapping already existed */
>> > +                return;
>> > +            }
>> > +        }
>> > +    }
>> >      struct lflow_ref_list_node *lrln = xzalloc(sizeof *lrln);
>> >      lrln->lflow_uuid = *lflow_uuid;
>> > -    ovs_list_push_back(&rlfn->ref_lflow_head, &lrln->ref_list);
>> > -    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->lflow_list);
>> > +    lrln->rlfn = rlfn;
>> > +    hmap_insert(&rlfn->lflow_uuids, &lrln->hmap_node,
> uuid_hash(lflow_uuid));
>> > +    ovs_list_push_back(&lfrn->lflow_ref_head, &lrln->list_node);
>> >  }
>>
>> I think rewriting this function in a different way might make it more
>> readable. E.g., pseudocode:
>>
>> rlfn = ref_lflow_lookup(&lfrr->ref_lflow_table, type, ref_name);
>> lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table, lflow_uuid);
>>
>> if (rlfn && lfrn) {
>>     /* Check for duplicates here. */
>> } else {
>>     if (!rlfn) {
>>         /* Allocate, init, insert rlfn. */
>>         /* Maybe we can have a function for this? */
>>     }
>>     if (!lfrn) {
>>         /* Allocate, init, insert lfrn. */
>>         /* Maybe we can have a function for this? */
>>     }
>> }
>>
>> /* Allocate, init, insert lrln. */
>> [...]
>>
>> Also, it might be me but these variable names are so close to each other
>> that it's quite confusing. Maybe we can find some more explicit names?
>>

What about the variable naming part? Can we address it somehow?

>> >
>> >  static void
>> > @@ -261,9 +282,13 @@ lflow_resource_destroy_lflow(struct
> lflow_resource_ref *lfrr,
>> >
>> >      hmap_remove(&lfrr->lflow_ref_table, &lfrn->node);
>> >      struct lflow_ref_list_node *lrln, *next;
>> > -    LIST_FOR_EACH_SAFE (lrln, next, lflow_list,
> &lfrn->lflow_ref_head) {
>> > -        ovs_list_remove(&lrln->ref_list);
>> > -        ovs_list_remove(&lrln->lflow_list);
>> > +    LIST_FOR_EACH_SAFE (lrln, next, list_node, &lfrn->lflow_ref_head) {
>> > +        ovs_list_remove(&lrln->list_node);
>> > +        hmap_remove(&lrln->rlfn->lflow_uuids, &lrln->hmap_node);
>>
>> I think a comment here explaining why we can't remove the node would be
>> helpful.
> 
> Sorry, I didn't get it. We do remove the node here. Let me explain.
> Originally both directions of the references are linked lists. Now one
> of the directions is replaced by hmap, as explained in the commit message.
> The change here merely replaces the operation ovs_list_remove operation
> to hmap_remove operation for the direction that has the data structure
> change. The other line is also updated because of the rename of the list
> node field (because the older field names were more confusing).
> 

I actually meant the line below. I see you moved it in a separate patch
in v2, I'll comment there.

Thanks,
Dumitru