[ovs-dev,v2,1/2] 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.

[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>
---
v1 -> v2:
 - Addressed Dumitru's comments.
 - Moved the unrelated change to a separate patch in the series:
   "lflow.c: Release ref_lflow_node as soon as it is not needed."

 controller/lflow.c | 69 +++++++++++++++++++++++++++++++++++++-----------------
 controller/lflow.h | 27 +++++++++++----------
 tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 112 insertions(+), 33 deletions(-)

Hi Han,

On 9/15/20 8:40 PM, 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

Nit: s/existance/existence

> adding in lflow_resource_add(). To do this check efficiently, hmap is used to
> replace the list struct for the resource-to-lflow index.
> 
> [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>
> ---
> v1 -> v2:
>  - Addressed Dumitru's comments.
>  - Moved the unrelated change to a separate patch in the series:
>    "lflow.c: Release ref_lflow_node as soon as it is not needed."
> 
>  controller/lflow.c | 69 +++++++++++++++++++++++++++++++++++++-----------------
>  controller/lflow.h | 27 +++++++++++----------
>  tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++
>  3 files changed, 112 insertions(+), 33 deletions(-)
> 
> diff --git a/controller/lflow.c b/controller/lflow.c
> index e785866..86a5b76 100644
> --- a/controller/lflow.c
> +++ b/controller/lflow.c
> @@ -74,6 +74,15 @@ consider_logical_flow(const struct sbrec_logical_flow *lflow,
>                        struct lflow_ctx_out *l_ctx_out);
>  static void lflow_resource_add(struct lflow_resource_ref *, enum ref_type,
>                                 const char *ref_name, const struct uuid *);
> +static struct ref_lflow_node * ref_lflow_lookup(struct hmap *ref_lflow_table,
> +                                               enum ref_type,
> +                                               const char *ref_name);

I don't see an explicit rule for pointer return types for functions in
our coding guidelines but from what I see most of the time we prefer to
attach the '*' to the function name.

Or:

Indent needs one more space.

> +static struct lflow_ref_node * lflow_ref_lookup(struct hmap *lflow_ref_table,
> +                                               const struct uuid *lflow_uuid);

Same here.

> +static void ref_lflow_node_destroy(struct ref_lflow_node *);
> +static void lflow_resource_destroy_lflow(struct lflow_resource_ref *,
> +                                         const struct uuid *lflow_uuid);
> +
>  
>  static bool
>  lookup_port_cb(const void *aux_, const char *port_name, unsigned int *portp)
> @@ -161,15 +170,14 @@ 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);
>  
> @@ -224,17 +232,28 @@ lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>  {
>      struct ref_lflow_node *rlfn = ref_lflow_lookup(&lfrr->ref_lflow_table,
>                                                     type, ref_name);
> +    struct lflow_ref_node *lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table,
> +                                                   lflow_uuid);
> +    if (rlfn && lfrn) {
> +        /* Check if the mapping already existed before adding a new one. */

I would move this to a separate function:

static bool
ref_lflow_node_contains_uuid(const struct ref_lflow_node *, const struct
uuid *);

> +        struct lflow_ref_list_node *n;
> +        HMAP_FOR_EACH_WITH_HASH (n, hmap_node, uuid_hash(lflow_uuid),
> +                                &rlfn->lflow_uuids) {

Indent needs an extra space.

> +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
> +                return;
> +            }
> +        }
> +    }
> +
>      if (!rlfn) {
>          rlfn = xzalloc(sizeof *rlfn);
>          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);

As mentioned on the v1 thread, we have lookup functions, it would make
sense to have *_create() functions.

>      }
>  
> -    struct lflow_ref_node *lfrn = lflow_ref_lookup(&lfrr->lflow_ref_table,
> -                                                   lflow_uuid);
>      if (!lfrn) {
>          lfrn = xzalloc(sizeof *lfrn);
>          lfrn->node.hash = uuid_hash(lflow_uuid);

Same here.

> @@ -245,8 +264,17 @@ lflow_resource_add(struct lflow_resource_ref *lfrr, enum ref_type type,
>  
>      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);

Here too.

> +}
> +
> +static void
> +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
> +{
> +    free(rlfn->ref_name);
> +    hmap_destroy(&rlfn->lflow_uuids);
> +    free(rlfn);
>  }
>  
>  static void
> @@ -261,9 +289,9 @@ 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);

Here we remove every lflow_ref_list_node from lflow_ref_head and also
remove it from the lflow_uuids hashmap but in lflow_handle_changed_ref()
we split this operation in two stages: detach and later destroy.

We have a comment in lflow_handle_changed_ref() but I think it would be
cleaner if we had a "lflow_ref_list_node_detach()" and
"lflow_ref_list_node_destroy()" API. We can even add
"ovs_list_remove(&lrln->list_node)" if we're a bit careful and check
that the list_node is used before removing it.

My first impression when reading the code in lflow_handle_changed_ref()
was that we forgot to remove the node from the list.

>          free(lrln);
>      }
>      free(lfrn);
> @@ -531,12 +559,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 +593,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 +632,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);

I think detaching the "lflow_ref_list_node" entries from ref_lflow_node
and freeing them can be part of ref_lflow_node_destroy().

We duplicate this code already in lflow_resource_destroy() and here,
lflow_handle_changed_ref().

>  
>      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 */

Nit: I would align the comments with the one for the 'node' field.

Regards,
Dumitru

> -    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 Wed, Sep 16, 2020 at 5:10 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> Hi Han,
>
> On 9/15/20 8:40 PM, 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
>
> Nit: s/existance/existence

Ack.
>
> > adding in lflow_resource_add(). To do this check efficiently, hmap is
used to
> > replace the list struct for the resource-to-lflow index.
> >
> > [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>
> > ---
> > v1 -> v2:
> >  - Addressed Dumitru's comments.
> >  - Moved the unrelated change to a separate patch in the series:
> >    "lflow.c: Release ref_lflow_node as soon as it is not needed."
> >
> >  controller/lflow.c | 69
+++++++++++++++++++++++++++++++++++++-----------------
> >  controller/lflow.h | 27 +++++++++++----------
> >  tests/ovn.at       | 49 ++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 112 insertions(+), 33 deletions(-)
> >
> > diff --git a/controller/lflow.c b/controller/lflow.c
> > index e785866..86a5b76 100644
> > --- a/controller/lflow.c
> > +++ b/controller/lflow.c
> > @@ -74,6 +74,15 @@ consider_logical_flow(const struct
sbrec_logical_flow *lflow,
> >                        struct lflow_ctx_out *l_ctx_out);
> >  static void lflow_resource_add(struct lflow_resource_ref *, enum
ref_type,
> >                                 const char *ref_name, const struct uuid
*);
> > +static struct ref_lflow_node * ref_lflow_lookup(struct hmap
*ref_lflow_table,
> > +                                               enum ref_type,
> > +                                               const char *ref_name);
>
> I don't see an explicit rule for pointer return types for functions in
> our coding guidelines but from what I see most of the time we prefer to
> attach the '*' to the function name.

Ack.
>
> Or:
>
> Indent needs one more space.
>
> > +static struct lflow_ref_node * lflow_ref_lookup(struct hmap
*lflow_ref_table,
> > +                                               const struct uuid
*lflow_uuid);
>
> Same here.

Ack.
>
> > +static void ref_lflow_node_destroy(struct ref_lflow_node *);
> > +static void lflow_resource_destroy_lflow(struct lflow_resource_ref *,
> > +                                         const struct uuid
*lflow_uuid);
> > +
> >
> >  static bool
> >  lookup_port_cb(const void *aux_, const char *port_name, unsigned int
*portp)
> > @@ -161,15 +170,14 @@ 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);
> >
> > @@ -224,17 +232,28 @@ lflow_resource_add(struct lflow_resource_ref
*lfrr, enum ref_type type,
> >  {
> >      struct ref_lflow_node *rlfn =
ref_lflow_lookup(&lfrr->ref_lflow_table,
> >                                                     type, ref_name);
> > +    struct lflow_ref_node *lfrn =
lflow_ref_lookup(&lfrr->lflow_ref_table,
> > +                                                   lflow_uuid);
> > +    if (rlfn && lfrn) {
> > +        /* Check if the mapping already existed before adding a new
one. */
>
> I would move this to a separate function:
>
> static bool
> ref_lflow_node_contains_uuid(const struct ref_lflow_node *, const struct
> uuid *);

I have no strong opinion on this, but in general I'd prefer fewer functions
if the code is:
1. not reused (not creating redundancy) and
2. the size is small enough (not affecting readability).

>
> > +        struct lflow_ref_list_node *n;
> > +        HMAP_FOR_EACH_WITH_HASH (n, hmap_node, uuid_hash(lflow_uuid),
> > +                                &rlfn->lflow_uuids) {
>
> Indent needs an extra space.

Ack.
>
> > +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
> > +                return;
> > +            }
> > +        }
> > +    }
> > +
> >      if (!rlfn) {
> >          rlfn = xzalloc(sizeof *rlfn);
> >          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);
>
> As mentioned on the v1 thread, we have lookup functions, it would make
> sense to have *_create() functions.
>
Same as above. In addition, I prefer fewer functions because it is easier
(slightly) to tell from the prototypes that those are the only operations
possible for this data structure. In this case, it tells that this is the
only interface that allocates memory for the resource reference table. Of
course with extra functions you can still tell that by checking the code
and realize that there is only one place the _create() functions are
called, but to me that is just more noise (slightly). I don't think every
data structure needs all the constructors and destructors in C. The code
should evolve naturally when such functions are necessary. But if there is
a coding style kind of agreement that makes it a convention then I would
just follow. Again, I don't have a strong opinion in this case.

> >      }
> >
> > -    struct lflow_ref_node *lfrn =
lflow_ref_lookup(&lfrr->lflow_ref_table,
> > -                                                   lflow_uuid);
> >      if (!lfrn) {
> >          lfrn = xzalloc(sizeof *lfrn);
> >          lfrn->node.hash = uuid_hash(lflow_uuid);
>
> Same here.
>
> > @@ -245,8 +264,17 @@ lflow_resource_add(struct lflow_resource_ref
*lfrr, enum ref_type type,
> >
> >      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);
>
> Here too.
>
> > +}
> > +
> > +static void
> > +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
> > +{
> > +    free(rlfn->ref_name);
> > +    hmap_destroy(&rlfn->lflow_uuids);
> > +    free(rlfn);
> >  }
> >
> >  static void
> > @@ -261,9 +289,9 @@ 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);
>
> Here we remove every lflow_ref_list_node from lflow_ref_head and also
> remove it from the lflow_uuids hashmap but in lflow_handle_changed_ref()
> we split this operation in two stages: detach and later destroy.
>
They are different. Remember that we have two indexes to the reference
table, lflow_uuids and resources (in the code I used ref_name + ref_type as
the key for resources, so the data type was named *ref* instead of
*resource*). In this API it is deleting all the entries related to a given
lflow_uuid.

> We have a comment in lflow_handle_changed_ref() but I think it would be
> cleaner if we had a "lflow_ref_list_node_detach()" and
> "lflow_ref_list_node_destroy()" API. We can even add
> "ovs_list_remove(&lrln->list_node)" if we're a bit careful and check
> that the list_node is used before removing it.
>
> My first impression when reading the code in lflow_handle_changed_ref()
> was that we forgot to remove the node from the list.
>

I agree that this is the trickiest part of the whole data structure
operations, but I am not sure if having a "detach" API makes it more clear.
I guess better comments would be more helpful.
In lflow_handle_changed_ref(), we can't simply destroy a node. The cross
reference table needs to be manipulated in different directions in
different stages.
Originally the table looks like this (similar to
https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L80-L100):
 *                   lflow UUIDs

 *                 +-----+-----+-----+-----+-----+-----+-----+

 *                 |     |     |     |     |     |     |     |

 *                 +--+--+--+--+--+--+-----+--+--+--+--+--+--+

 *                    |     |     |           |     |     |

 *  resources         |     |     |           |     |     |
 *     +----+       +-+-+   |   +-+-+         |   +-+-+   |
 *     |    +-------+   +-------+   +-------------+   |   |
 *     +----+       +---+   |   +-+-+         |   +---+   |
 *     |    |               |     |           |           |

 *     +----+               |     |         +-+-+         |

 *     |    +-------------------------------+   |         |
 *     +----+             +---+   |         +---+         |
 *     |    +-------------+   |   |                       |

 *     +----+             +---+   |                       |

 *     |    |                     |                       |

 *     +----+                   +-+-+                   +-+-+
 *     |    +-------------------+   +-------------------+   |

 *     +----+                   +---+                   +---+
 *     |    |

 *     +----+
Now the horizontal direction lists are replaced by hash tables (so it is
even harder to represent in the diagram).

1. For a given resource (ref_type + ref_name), detach all the related nodes
from the table. (Without this, step 3 would be messed up)
2. Traverse the list (now the hmap) of the resource that is detached in
step 1, and do some processing for the lflows and get a new set of lflows
that are to be deleted and re-parsed.
3. For the set of lflows got from step 2, destroy the related nodes in the
cross reference table by calling lflow_resource_destroy_lflow(), and
re-parse it by calling consider_logical_flow(), which would result in
creating new nodes in the cross reference table.
4. Finally, destroy the detached list (now the hmap) from step 1.

So, if following the steps with the help of the above diagram to visualize,
the data structure and operations may become more clear. However, it seems
not easy to abstract this to one of two APIs. It is more of a pattern than
an interface.

These steps were commented in code but are embedded and scattered. Maybe I
could summarize them in the beginning of the function to make it more clear.


> >          free(lrln);
> >      }
> >      free(lfrn);
> > @@ -531,12 +559,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 +593,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 +632,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);
>
> I think detaching the "lflow_ref_list_node" entries from ref_lflow_node
> and freeing them can be part of ref_lflow_node_destroy().
>
> We duplicate this code already in lflow_resource_destroy() and here,
> lflow_handle_changed_ref().
>
They are not duplicated. In lflow_resource_destroy() it is different. It
performs one more operation there: ovs_list_remove(&lrln->list_node);
We can wrap a function that handles both cases: destroy a ref that is
already detached from the cross reference table, and destroy a ref that is
not detached. However, I am not sure if it makes the code more clear or
more confusing. To achieve that, we need to re-init the list node when it
is removed from the list, so that we can later check if it is in a list
before removing it, to avoid double removing. It can work, but it is not a
common practice at least in OVS/OVN code, so I would avoid it since the
whole purpose is to make the code more readable.
> >
> >      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 */
>
> Nit: I would align the comments with the one for the 'node' field.
Ok, but I'd reformat this in a separate patch together with other refactors
if needed, because it is not related to the fix and would add more noise to
the patch itself.

Thanks again for the detailed review and comments. To summarize, for the
comments I responded "Ack", I addressed in v3. For the other comments, we
can continue discussing and when we have agreement let's (either you or
myself) post a separate patch because those are refactors related to
existed code, not to the fix itself. I hope the fix can be merged soon
because it is critical.

>
> Regards,
> Dumitru
>
> > -    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/16/20 8:02 PM, Han Zhou wrote:
> 
> 
> On Wed, Sep 16, 2020 at 5:10 AM Dumitru Ceara <dceara@redhat.com
> <mailto:dceara@redhat.com>> wrote:
>>
>> Hi Han,
>>
>> On 9/15/20 8:40 PM, 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
>>
>> Nit: s/existance/existence
> 
> Ack.
>>
>> > adding in lflow_resource_add(). To do this check efficiently, hmap
> is used to
>> > replace the list struct for the resource-to-lflow index.
>> >
>> > [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>>
>> > ---
>> > v1 -> v2:
>> >  - Addressed Dumitru's comments.
>> >  - Moved the unrelated change to a separate patch in the series:
>> >    "lflow.c: Release ref_lflow_node as soon as it is not needed."
>> >
>> >  controller/lflow.c | 69
> +++++++++++++++++++++++++++++++++++++-----------------
>> >  controller/lflow.h | 27 +++++++++++----------
>> >  tests/ovn.at <http://ovn.at>       | 49
> ++++++++++++++++++++++++++++++++++++++
>> >  3 files changed, 112 insertions(+), 33 deletions(-)
>> >
>> > diff --git a/controller/lflow.c b/controller/lflow.c
>> > index e785866..86a5b76 100644
>> > --- a/controller/lflow.c
>> > +++ b/controller/lflow.c
>> > @@ -74,6 +74,15 @@ consider_logical_flow(const struct
> sbrec_logical_flow *lflow,
>> >                        struct lflow_ctx_out *l_ctx_out);
>> >  static void lflow_resource_add(struct lflow_resource_ref *, enum
> ref_type,
>> >                                 const char *ref_name, const struct
> uuid *);
>> > +static struct ref_lflow_node * ref_lflow_lookup(struct hmap
> *ref_lflow_table,
>> > +                                               enum ref_type,
>> > +                                               const char *ref_name);
>>
>> I don't see an explicit rule for pointer return types for functions in
>> our coding guidelines but from what I see most of the time we prefer to
>> attach the '*' to the function name.
> 
> Ack.
>>
>> Or:
>>
>> Indent needs one more space.
>>
>> > +static struct lflow_ref_node * lflow_ref_lookup(struct hmap
> *lflow_ref_table,
>> > +                                               const struct uuid
> *lflow_uuid);
>>
>> Same here.
> 
> Ack.
>>
>> > +static void ref_lflow_node_destroy(struct ref_lflow_node *);
>> > +static void lflow_resource_destroy_lflow(struct lflow_resource_ref *,
>> > +                                         const struct uuid
> *lflow_uuid);
>> > +
>> >
>> >  static bool
>> >  lookup_port_cb(const void *aux_, const char *port_name, unsigned
> int *portp)
>> > @@ -161,15 +170,14 @@ 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);
>> >
>> > @@ -224,17 +232,28 @@ lflow_resource_add(struct lflow_resource_ref
> *lfrr, enum ref_type type,
>> >  {
>> >      struct ref_lflow_node *rlfn =
> ref_lflow_lookup(&lfrr->ref_lflow_table,
>> >                                                     type, ref_name);
>> > +    struct lflow_ref_node *lfrn =
> lflow_ref_lookup(&lfrr->lflow_ref_table,
>> > +                                                   lflow_uuid);
>> > +    if (rlfn && lfrn) {
>> > +        /* Check if the mapping already existed before adding a new
> one. */
>>
>> I would move this to a separate function:
>>
>> static bool
>> ref_lflow_node_contains_uuid(const struct ref_lflow_node *, const struct
>> uuid *);
> 
> I have no strong opinion on this, but in general I'd prefer fewer
> functions if the code is:
> 1. not reused (not creating redundancy) and
> 2. the size is small enough (not affecting readability).
>

I guess it depends. It's also a matter of preference. But in this case
without the comment "Check if the mapping already existed before adding
a new one" a reader would have to check what the lflow_uuids field
actually is and how it's populated. On the other hand, a call to
something like:

ref_lflow_node_contains_uuid(rlfn, flow_uuid)

should be self-explanatory and has the advantage that the implementation
of the check is close to where the structure and other helpers are defined.

But we can discuss this further if/when we refactor this part of the code.

>>
>> > +        struct lflow_ref_list_node *n;
>> > +        HMAP_FOR_EACH_WITH_HASH (n, hmap_node, uuid_hash(lflow_uuid),
>> > +                                &rlfn->lflow_uuids) {
>>
>> Indent needs an extra space.
> 
> Ack.
>>
>> > +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
>> > +                return;
>> > +            }
>> > +        }
>> > +    }
>> > +
>> >      if (!rlfn) {
>> >          rlfn = xzalloc(sizeof *rlfn);
>> >          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);
>>
>> As mentioned on the v1 thread, we have lookup functions, it would make
>> sense to have *_create() functions.
>>
> Same as above. In addition, I prefer fewer functions because it is
> easier (slightly) to tell from the prototypes that those are the only
> operations possible for this data structure. In this case, it tells that
> this is the only interface that allocates memory for the resource
> reference table. Of course with extra functions you can still tell that
> by checking the code and realize that there is only one place the
> _create() functions are called, but to me that is just more noise
> (slightly). I don't think every data structure needs all the
> constructors and destructors in C. The code should evolve naturally when
> such functions are necessary. But if there is a coding style kind of
> agreement that makes it a convention then I would just follow. Again, I
> don't have a strong opinion in this case.
> 

I tend to agree in general but my concern in this specific case is that
it's very easy to make a typo and write "free(lfrn);" instead of
"free(lrln);".

>> >      }
>> >
>> > -    struct lflow_ref_node *lfrn =
> lflow_ref_lookup(&lfrr->lflow_ref_table,
>> > -                                                   lflow_uuid);
>> >      if (!lfrn) {
>> >          lfrn = xzalloc(sizeof *lfrn);
>> >          lfrn->node.hash = uuid_hash(lflow_uuid);
>>
>> Same here.
>>
>> > @@ -245,8 +264,17 @@ lflow_resource_add(struct lflow_resource_ref
> *lfrr, enum ref_type type,
>> >
>> >      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);
>>
>> Here too.
>>
>> > +}
>> > +
>> > +static void
>> > +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
>> > +{
>> > +    free(rlfn->ref_name);
>> > +    hmap_destroy(&rlfn->lflow_uuids);
>> > +    free(rlfn);
>> >  }
>> >
>> >  static void
>> > @@ -261,9 +289,9 @@ 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);
>>
>> Here we remove every lflow_ref_list_node from lflow_ref_head and also
>> remove it from the lflow_uuids hashmap but in lflow_handle_changed_ref()
>> we split this operation in two stages: detach and later destroy.
>>
> They are different. Remember that we have two indexes to the reference
> table, lflow_uuids and resources (in the code I used ref_name + ref_type
> as the key for resources, so the data type was named *ref* instead of
> *resource*). In this API it is deleting all the entries related to a
> given lflow_uuid.
> 
>> We have a comment in lflow_handle_changed_ref() but I think it would be
>> cleaner if we had a "lflow_ref_list_node_detach()" and
>> "lflow_ref_list_node_destroy()" API. We can even add
>> "ovs_list_remove(&lrln->list_node)" if we're a bit careful and check
>> that the list_node is used before removing it.
>>
>> My first impression when reading the code in lflow_handle_changed_ref()
>> was that we forgot to remove the node from the list.
>>
> 
> I agree that this is the trickiest part of the whole data structure
> operations, but I am not sure if having a "detach" API makes it more
> clear. I guess better comments would be more helpful.
> In lflow_handle_changed_ref(), we can't simply destroy a node. The cross
> reference table needs to be manipulated in different directions in
> different stages.
> Originally the table looks like this (similar to
> https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L80-L100):
>  *                   lflow UUIDs                                        
>                        
>  *                 +-----+-----+-----+-----+-----+-----+-----+          
>                      
>  *                 |     |     |     |     |     |     |     |          
>                      
>  *                 +--+--+--+--+--+--+-----+--+--+--+--+--+--+          
>                      
>  *                    |     |     |           |     |     |            
>                      
>  *  resources         |     |     |           |     |     |
>  *     +----+       +-+-+   |   +-+-+         |   +-+-+   |
>  *     |    +-------+   +-------+   +-------------+   |   |
>  *     +----+       +---+   |   +-+-+         |   +---+   |
>  *     |    |               |     |           |           |            
>                      
>  *     +----+               |     |         +-+-+         |            
>                      
>  *     |    +-------------------------------+   |         |
>  *     +----+             +---+   |         +---+         |
>  *     |    +-------------+   |   |                       |            
>                      
>  *     +----+             +---+   |                       |            
>                      
>  *     |    |                     |                       |            
>                      
>  *     +----+                   +-+-+                   +-+-+
>  *     |    +-------------------+   +-------------------+   |          
>                      
>  *     +----+                   +---+                   +---+
>  *     |    |                                                          
>                      
>  *     +----+             
> 
> Now the horizontal direction lists are replaced by hash tables (so it is
> even harder to represent in the diagram).
> 
> 1. For a given resource (ref_type + ref_name), detach all the related
> nodes from the table. (Without this, step 3 would be messed up)
> 2. Traverse the list (now the hmap) of the resource that is detached in
> step 1, and do some processing for the lflows and get a new set of
> lflows that are to be deleted and re-parsed.
> 3. For the set of lflows got from step 2, destroy the related nodes in
> the cross reference table by calling lflow_resource_destroy_lflow(), and
> re-parse it by calling consider_logical_flow(), which would result in
> creating new nodes in the cross reference table.
> 4. Finally, destroy the detached list (now the hmap) from step 1.
> 
> So, if following the steps with the help of the above diagram to
> visualize, the data structure and operations may become more clear.
> However, it seems not easy to abstract this to one of two APIs. It is
> more of a pattern than an interface.
> 

Right, I thought it was supposed to be like that. Thanks for the
detailed explanation.

> These steps were commented in code but are embedded and scattered. Maybe
> I could summarize them in the beginning of the function to make it more
> clear.
> 

That'd be great!

> 
>> >          free(lrln);
>> >      }
>> >      free(lfrn);
>> > @@ -531,12 +559,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 +593,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 +632,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);
>>
>> I think detaching the "lflow_ref_list_node" entries from ref_lflow_node
>> and freeing them can be part of ref_lflow_node_destroy().
>>
>> We duplicate this code already in lflow_resource_destroy() and here,
>> lflow_handle_changed_ref().
>>
> They are not duplicated. In lflow_resource_destroy() it is different. It
> performs one more operation there: ovs_list_remove(&lrln->list_node);
> We can wrap a function that handles both cases: destroy a ref that is
> already detached from the cross reference table, and destroy a ref that
> is not detached. However, I am not sure if it makes the code more clear
> or more confusing. To achieve that, we need to re-init the list node
> when it is removed from the list, so that we can later check if it is in
> a list before removing it, to avoid double removing. It can work, but it
> is not a common practice at least in OVS/OVN code, so I would avoid it
> since the whole purpose is to make the code more readable.

Right, the only difference is the is the
ovs_list_remove(&lrln->list_node). I had exactly that in mind, reiniting
the list node after removal.

It is a bit unusual but we do use a similar pattern in at least one
place in OVN to check if a node is part of a list, the line where we
crash without your fix:

https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L1108

>> >
>> >      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 */
>>
>> Nit: I would align the comments with the one for the 'node' field.
> Ok, but I'd reformat this in a separate patch together with other
> refactors if needed, because it is not related to the fix and would add
> more noise to the patch itself.
> 
> Thanks again for the detailed review and comments. To summarize, for the
> comments I responded "Ack", I addressed in v3. For the other comments,
> we can continue discussing and when we have agreement let's (either you
> or myself) post a separate patch because those are refactors related to
> existed code, not to the fix itself. I hope the fix can be merged soon
> because it is critical.
> 

Ack, I'll have a look at v3 soon.

Thanks,
Dumitru

On Wed, Sep 16, 2020 at 11:55 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On 9/16/20 8:02 PM, Han Zhou wrote:
> >
> >
> > On Wed, Sep 16, 2020 at 5:10 AM Dumitru Ceara <dceara@redhat.com
> > <mailto:dceara@redhat.com>> wrote:
> >>
> >> Hi Han,
> >>
> >> On 9/15/20 8:40 PM, 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
> >>
> >> Nit: s/existance/existence
> >
> > Ack.
> >>
> >> > adding in lflow_resource_add(). To do this check efficiently, hmap
> > is used to
> >> > replace the list struct for the resource-to-lflow index.
> >> >
> >> > [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>>
> >> > ---
> >> > v1 -> v2:
> >> >  - Addressed Dumitru's comments.
> >> >  - Moved the unrelated change to a separate patch in the series:
> >> >    "lflow.c: Release ref_lflow_node as soon as it is not needed."
> >> >
> >> >  controller/lflow.c | 69
> > +++++++++++++++++++++++++++++++++++++-----------------
> >> >  controller/lflow.h | 27 +++++++++++----------
> >> >  tests/ovn.at <http://ovn.at>       | 49
> > ++++++++++++++++++++++++++++++++++++++
> >> >  3 files changed, 112 insertions(+), 33 deletions(-)
> >> >
> >> > diff --git a/controller/lflow.c b/controller/lflow.c
> >> > index e785866..86a5b76 100644
> >> > --- a/controller/lflow.c
> >> > +++ b/controller/lflow.c
> >> > @@ -74,6 +74,15 @@ consider_logical_flow(const struct
> > sbrec_logical_flow *lflow,
> >> >                        struct lflow_ctx_out *l_ctx_out);
> >> >  static void lflow_resource_add(struct lflow_resource_ref *, enum
> > ref_type,
> >> >                                 const char *ref_name, const struct
> > uuid *);
> >> > +static struct ref_lflow_node * ref_lflow_lookup(struct hmap
> > *ref_lflow_table,
> >> > +                                               enum ref_type,
> >> > +                                               const char
*ref_name);
> >>
> >> I don't see an explicit rule for pointer return types for functions in
> >> our coding guidelines but from what I see most of the time we prefer to
> >> attach the '*' to the function name.
> >
> > Ack.
> >>
> >> Or:
> >>
> >> Indent needs one more space.
> >>
> >> > +static struct lflow_ref_node * lflow_ref_lookup(struct hmap
> > *lflow_ref_table,
> >> > +                                               const struct uuid
> > *lflow_uuid);
> >>
> >> Same here.
> >
> > Ack.
> >>
> >> > +static void ref_lflow_node_destroy(struct ref_lflow_node *);
> >> > +static void lflow_resource_destroy_lflow(struct lflow_resource_ref
*,
> >> > +                                         const struct uuid
> > *lflow_uuid);
> >> > +
> >> >
> >> >  static bool
> >> >  lookup_port_cb(const void *aux_, const char *port_name, unsigned
> > int *portp)
> >> > @@ -161,15 +170,14 @@ 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);
> >> >
> >> > @@ -224,17 +232,28 @@ lflow_resource_add(struct lflow_resource_ref
> > *lfrr, enum ref_type type,
> >> >  {
> >> >      struct ref_lflow_node *rlfn =
> > ref_lflow_lookup(&lfrr->ref_lflow_table,
> >> >                                                     type, ref_name);
> >> > +    struct lflow_ref_node *lfrn =
> > lflow_ref_lookup(&lfrr->lflow_ref_table,
> >> > +                                                   lflow_uuid);
> >> > +    if (rlfn && lfrn) {
> >> > +        /* Check if the mapping already existed before adding a new
> > one. */
> >>
> >> I would move this to a separate function:
> >>
> >> static bool
> >> ref_lflow_node_contains_uuid(const struct ref_lflow_node *, const
struct
> >> uuid *);
> >
> > I have no strong opinion on this, but in general I'd prefer fewer
> > functions if the code is:
> > 1. not reused (not creating redundancy) and
> > 2. the size is small enough (not affecting readability).
> >
>
> I guess it depends. It's also a matter of preference. But in this case
> without the comment "Check if the mapping already existed before adding
> a new one" a reader would have to check what the lflow_uuids field
> actually is and how it's populated. On the other hand, a call to
> something like:
>
> ref_lflow_node_contains_uuid(rlfn, flow_uuid)
>
> should be self-explanatory and has the advantage that the implementation
> of the check is close to where the structure and other helpers are
defined.

The comment was in fact trying to tell why we are checking if
rel_lflow_node contains the uuid. We are checking if the pair exists in the
cross reference table, while the implementation is checking from just one
direction, the direction that has the hmap, for efficiency. From
readability point of view, the comment can be omitted if we have an API
called lflow_resource_check_existence(ref_type, ref_name, lflow_uuid) to
check a given pair in the table, which is more clear, but it would be less
efficient because in this function we would have to find the head nodes for
both directions first, which was already done in the lflow_resource_add().

>
> But we can discuss this further if/when we refactor this part of the code.
>
> >>
> >> > +        struct lflow_ref_list_node *n;
> >> > +        HMAP_FOR_EACH_WITH_HASH (n, hmap_node,
uuid_hash(lflow_uuid),
> >> > +                                &rlfn->lflow_uuids) {
> >>
> >> Indent needs an extra space.
> >
> > Ack.
> >>
> >> > +            if (uuid_equals(&n->lflow_uuid, lflow_uuid)) {
> >> > +                return;
> >> > +            }
> >> > +        }
> >> > +    }
> >> > +
> >> >      if (!rlfn) {
> >> >          rlfn = xzalloc(sizeof *rlfn);
> >> >          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);
> >>
> >> As mentioned on the v1 thread, we have lookup functions, it would make
> >> sense to have *_create() functions.
> >>
> > Same as above. In addition, I prefer fewer functions because it is
> > easier (slightly) to tell from the prototypes that those are the only
> > operations possible for this data structure. In this case, it tells that
> > this is the only interface that allocates memory for the resource
> > reference table. Of course with extra functions you can still tell that
> > by checking the code and realize that there is only one place the
> > _create() functions are called, but to me that is just more noise
> > (slightly). I don't think every data structure needs all the
> > constructors and destructors in C. The code should evolve naturally when
> > such functions are necessary. But if there is a coding style kind of
> > agreement that makes it a convention then I would just follow. Again, I
> > don't have a strong opinion in this case.
> >
>
> I tend to agree in general but my concern in this specific case is that
> it's very easy to make a typo and write "free(lfrn);" instead of
> "free(lrln);".
>
True. But that's more of a variable naming problem. Some may argue that it
is easy to call the wrong function if the function names are similar :)

> >> >      }
> >> >
> >> > -    struct lflow_ref_node *lfrn =
> > lflow_ref_lookup(&lfrr->lflow_ref_table,
> >> > -                                                   lflow_uuid);
> >> >      if (!lfrn) {
> >> >          lfrn = xzalloc(sizeof *lfrn);
> >> >          lfrn->node.hash = uuid_hash(lflow_uuid);
> >>
> >> Same here.
> >>
> >> > @@ -245,8 +264,17 @@ lflow_resource_add(struct lflow_resource_ref
> > *lfrr, enum ref_type type,
> >> >
> >> >      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);
> >>
> >> Here too.
> >>
> >> > +}
> >> > +
> >> > +static void
> >> > +ref_lflow_node_destroy(struct ref_lflow_node *rlfn)
> >> > +{
> >> > +    free(rlfn->ref_name);
> >> > +    hmap_destroy(&rlfn->lflow_uuids);
> >> > +    free(rlfn);
> >> >  }
> >> >
> >> >  static void
> >> > @@ -261,9 +289,9 @@ 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);
> >>
> >> Here we remove every lflow_ref_list_node from lflow_ref_head and also
> >> remove it from the lflow_uuids hashmap but in
lflow_handle_changed_ref()
> >> we split this operation in two stages: detach and later destroy.
> >>
> > They are different. Remember that we have two indexes to the reference
> > table, lflow_uuids and resources (in the code I used ref_name + ref_type
> > as the key for resources, so the data type was named *ref* instead of
> > *resource*). In this API it is deleting all the entries related to a
> > given lflow_uuid.
> >
> >> We have a comment in lflow_handle_changed_ref() but I think it would be
> >> cleaner if we had a "lflow_ref_list_node_detach()" and
> >> "lflow_ref_list_node_destroy()" API. We can even add
> >> "ovs_list_remove(&lrln->list_node)" if we're a bit careful and check
> >> that the list_node is used before removing it.
> >>
> >> My first impression when reading the code in lflow_handle_changed_ref()
> >> was that we forgot to remove the node from the list.
> >>
> >
> > I agree that this is the trickiest part of the whole data structure
> > operations, but I am not sure if having a "detach" API makes it more
> > clear. I guess better comments would be more helpful.
> > In lflow_handle_changed_ref(), we can't simply destroy a node. The cross
> > reference table needs to be manipulated in different directions in
> > different stages.
> > Originally the table looks like this (similar to
> > https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L80-L100
):
> >  *                   lflow UUIDs
> >
> >  *                 +-----+-----+-----+-----+-----+-----+-----+
> >
> >  *                 |     |     |     |     |     |     |     |
> >
> >  *                 +--+--+--+--+--+--+-----+--+--+--+--+--+--+
> >
> >  *                    |     |     |           |     |     |
> >
> >  *  resources         |     |     |           |     |     |
> >  *     +----+       +-+-+   |   +-+-+         |   +-+-+   |
> >  *     |    +-------+   +-------+   +-------------+   |   |
> >  *     +----+       +---+   |   +-+-+         |   +---+   |
> >  *     |    |               |     |           |           |
> >
> >  *     +----+               |     |         +-+-+         |
> >
> >  *     |    +-------------------------------+   |         |
> >  *     +----+             +---+   |         +---+         |
> >  *     |    +-------------+   |   |                       |
> >
> >  *     +----+             +---+   |                       |
> >
> >  *     |    |                     |                       |
> >
> >  *     +----+                   +-+-+                   +-+-+
> >  *     |    +-------------------+   +-------------------+   |
> >
> >  *     +----+                   +---+                   +---+
> >  *     |    |
> >
> >  *     +----+
> >
> > Now the horizontal direction lists are replaced by hash tables (so it is
> > even harder to represent in the diagram).
> >
> > 1. For a given resource (ref_type + ref_name), detach all the related
> > nodes from the table. (Without this, step 3 would be messed up)
> > 2. Traverse the list (now the hmap) of the resource that is detached in
> > step 1, and do some processing for the lflows and get a new set of
> > lflows that are to be deleted and re-parsed.
> > 3. For the set of lflows got from step 2, destroy the related nodes in
> > the cross reference table by calling lflow_resource_destroy_lflow(), and
> > re-parse it by calling consider_logical_flow(), which would result in
> > creating new nodes in the cross reference table.
> > 4. Finally, destroy the detached list (now the hmap) from step 1.
> >
> > So, if following the steps with the help of the above diagram to
> > visualize, the data structure and operations may become more clear.
> > However, it seems not easy to abstract this to one of two APIs. It is
> > more of a pattern than an interface.
> >
>
> Right, I thought it was supposed to be like that. Thanks for the
> detailed explanation.
>
> > These steps were commented in code but are embedded and scattered. Maybe
> > I could summarize them in the beginning of the function to make it more
> > clear.
> >
>
> That'd be great!
>
> >
> >> >          free(lrln);
> >> >      }
> >> >      free(lfrn);
> >> > @@ -531,12 +559,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 +593,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 +632,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);
> >>
> >> I think detaching the "lflow_ref_list_node" entries from ref_lflow_node
> >> and freeing them can be part of ref_lflow_node_destroy().
> >>
> >> We duplicate this code already in lflow_resource_destroy() and here,
> >> lflow_handle_changed_ref().
> >>
> > They are not duplicated. In lflow_resource_destroy() it is different. It
> > performs one more operation there: ovs_list_remove(&lrln->list_node);
> > We can wrap a function that handles both cases: destroy a ref that is
> > already detached from the cross reference table, and destroy a ref that
> > is not detached. However, I am not sure if it makes the code more clear
> > or more confusing. To achieve that, we need to re-init the list node
> > when it is removed from the list, so that we can later check if it is in
> > a list before removing it, to avoid double removing. It can work, but it
> > is not a common practice at least in OVS/OVN code, so I would avoid it
> > since the whole purpose is to make the code more readable.
>
> Right, the only difference is the is the
> ovs_list_remove(&lrln->list_node). I had exactly that in mind, reiniting
> the list node after removal.
>
> It is a bit unusual but we do use a similar pattern in at least one
> place in OVN to check if a node is part of a list, the line where we
> crash without your fix:
>
> https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L1108
>
That's a little different. The assert was to make sure we add the node to
the list at most once in its lifetime (because otherwise there must be
something wrong in the code, as how the bug was discovered). It didn't try
to re-initialize the list_node after removing it from the list and use that
to indicate if it is in the list already.

I did use this trick in one situation:
https://github.com/ovn-org/ovn/blob/master/controller/ofctrl.c#L1825
Without this I would have to add another member variable just to remember
if it is tracked already. Since this was tricky, I added extra comments to
explain. I am still not sure if it is a good idea.

I'd avoid that in simple scenarios like here.

> >> >
> >> >      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 */
> >>
> >> Nit: I would align the comments with the one for the 'node' field.
> > Ok, but I'd reformat this in a separate patch together with other
> > refactors if needed, because it is not related to the fix and would add
> > more noise to the patch itself.
> >
> > Thanks again for the detailed review and comments. To summarize, for the
> > comments I responded "Ack", I addressed in v3. For the other comments,
> > we can continue discussing and when we have agreement let's (either you
> > or myself) post a separate patch because those are refactors related to
> > existed code, not to the fix itself. I hope the fix can be merged soon
> > because it is critical.
> >
>
> Ack, I'll have a look at v3 soon.
>
> Thanks,
> Dumitru
>
>

On 9/16/20 10:05 PM, Han Zhou wrote:
>> > Same as above. In addition, I prefer fewer functions because it is
>> > easier (slightly) to tell from the prototypes that those are the only
>> > operations possible for this data structure. In this case, it tells that
>> > this is the only interface that allocates memory for the resource
>> > reference table. Of course with extra functions you can still tell that
>> > by checking the code and realize that there is only one place the
>> > _create() functions are called, but to me that is just more noise
>> > (slightly). I don't think every data structure needs all the
>> > constructors and destructors in C. The code should evolve naturally when
>> > such functions are necessary. But if there is a coding style kind of
>> > agreement that makes it a convention then I would just follow. Again, I
>> > don't have a strong opinion in this case.
>> >
>>
>> I tend to agree in general but my concern in this specific case is that
>> it's very easy to make a typo and write "free(lfrn);" instead of
>> "free(lrln);".
>>
> True. But that's more of a variable naming problem. Some may argue that
> it is easy to call the wrong function if the function names are similar :)

Well, even if the function names are similar, they would be operating on
different data types so the compiler would complain if we'd try to call
the wrong function.

While free(void *) compiles with any pointer arg :)

In any case, I'll give this more thought coming weeks and I'll try to
see if I can come up with a concrete patch we can discuss on.

Thanks,
Dumitru

On Thu, Sep 17, 2020 at 12:49 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On 9/16/20 10:05 PM, Han Zhou wrote:
> >> > Same as above. In addition, I prefer fewer functions because it is
> >> > easier (slightly) to tell from the prototypes that those are the only
> >> > operations possible for this data structure. In this case, it tells
that
> >> > this is the only interface that allocates memory for the resource
> >> > reference table. Of course with extra functions you can still tell
that
> >> > by checking the code and realize that there is only one place the
> >> > _create() functions are called, but to me that is just more noise
> >> > (slightly). I don't think every data structure needs all the
> >> > constructors and destructors in C. The code should evolve naturally
when
> >> > such functions are necessary. But if there is a coding style kind of
> >> > agreement that makes it a convention then I would just follow.
Again, I
> >> > don't have a strong opinion in this case.
> >> >
> >>
> >> I tend to agree in general but my concern in this specific case is that
> >> it's very easy to make a typo and write "free(lfrn);" instead of
> >> "free(lrln);".
> >>
> > True. But that's more of a variable naming problem. Some may argue that
> > it is easy to call the wrong function if the function names are similar
:)
>
> Well, even if the function names are similar, they would be operating on
> different data types so the compiler would complain if we'd try to call
> the wrong function.
>
> While free(void *) compiles with any pointer arg :)

I meant some like:

ref_lflow_node_destroy(rlfn);
v.s.
lflow_ref_node_destroy(lfrn);

Or even worse:

rl_node_destroy(rlfn);
v.s.
lr_node_destroy(lfrn);

Both would compile, although functions are used. On the other hand, it is
less likely to make a mistake even with just free:

free(resource_node);
v.s.
free(logical_flow_node);

So I'd say the real ones to blame in such cases are probably the naming +
careless programmer and reviewer :)

>
> In any case, I'll give this more thought coming weeks and I'll try to
> see if I can come up with a concrete patch we can discuss on.

Appreciate it!

>
> Thanks,
> Dumitru
>