Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Han Zhou]

On Fri, Apr 13, 2018 at 2:40 PM, Han Zhou  wrote:
>
>
>
> On Fri, Apr 13, 2018 at 1:42 PM, Ben Pfaff  wrote:
> >
> > On Fri, Apr 13, 2018 at 01:33:26PM -0700, Han Zhou wrote:
> > > On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff  wrote:
> > > > I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
> > > > n_ipv6_addrs, because of the allocation strategy.  If port groups
get
> > > > big (and they will eventually even if they do not today, because
scale)
> > > > I think that it would be better to expand the allocations
exponentially.
> > >
> > > Sorry that I didn't find it a problem. For each group, there are i
ports,
> > > and for each port there are j address groups (e.g. mac ip1 ip2 ip3
...),
> > > and for each address group there are k addresses (some of them can be
ipv4
> > > and some can be ipv6).
> > > Although there are nested loops, this implementation iterates each
ipv4 and
> > > ipv6 address only once, so if the total number of ipv4 and ipv6
addresses
> > > are n, then it should be O(n). Please correct me if I missed
something here.
> >
> > I agree that the function visits and inserts each ipv4 and ipv6 address
> > once, which is O(n).  The issue is that xrealloc() has to copy all of
> > the addresses each time.  Suppose, for example, that there are 50
> > addresses in an address set, 1 per port.  This yields a sequence of 50
> > xrealloc() calls that copy 0, 1, 2, ..., 49 addresses, respectively,
> > which is O(n**2) copies.  The usual solution is to expand the array by
> > (roughly) doubling, so that there are only 0 + 1 + 2 + 4 + 8 + 16 + 32
> > copies total, which is O(n) copies.
>
> Now I got your point! I will send V3 with this addressed. Thanks Ben!

Hi Ben,

V3 is here: https://patchwork.ozlabs.org/patch/898123/

All comments are addressed except that I kept the xcalloc() there as
initial allocation for the exponential allocations. Please take a look.

Thanks,
Han
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Han Zhou]

On Fri, Apr 13, 2018 at 1:42 PM, Ben Pfaff  wrote:
>
> On Fri, Apr 13, 2018 at 01:33:26PM -0700, Han Zhou wrote:
> > On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff  wrote:
> > > I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
> > > n_ipv6_addrs, because of the allocation strategy.  If port groups get
> > > big (and they will eventually even if they do not today, because
scale)
> > > I think that it would be better to expand the allocations
exponentially.
> >
> > Sorry that I didn't find it a problem. For each group, there are i
ports,
> > and for each port there are j address groups (e.g. mac ip1 ip2 ip3 ...),
> > and for each address group there are k addresses (some of them can be
ipv4
> > and some can be ipv6).
> > Although there are nested loops, this implementation iterates each ipv4
and
> > ipv6 address only once, so if the total number of ipv4 and ipv6
addresses
> > are n, then it should be O(n). Please correct me if I missed something
here.
>
> I agree that the function visits and inserts each ipv4 and ipv6 address
> once, which is O(n).  The issue is that xrealloc() has to copy all of
> the addresses each time.  Suppose, for example, that there are 50
> addresses in an address set, 1 per port.  This yields a sequence of 50
> xrealloc() calls that copy 0, 1, 2, ..., 49 addresses, respectively,
> which is O(n**2) copies.  The usual solution is to expand the array by
> (roughly) doubling, so that there are only 0 + 1 + 2 + 4 + 8 + 16 + 32
> copies total, which is O(n) copies.

Now I got your point! I will send V3 with this addressed. Thanks Ben!
>
> Thanks,
>
> Ben.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Ben Pfaff]

On Fri, Apr 13, 2018 at 01:33:26PM -0700, Han Zhou wrote:
> On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff  wrote:
> > I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
> > n_ipv6_addrs, because of the allocation strategy.  If port groups get
> > big (and they will eventually even if they do not today, because scale)
> > I think that it would be better to expand the allocations exponentially.
> 
> Sorry that I didn't find it a problem. For each group, there are i ports,
> and for each port there are j address groups (e.g. mac ip1 ip2 ip3 ...),
> and for each address group there are k addresses (some of them can be ipv4
> and some can be ipv6).
> Although there are nested loops, this implementation iterates each ipv4 and
> ipv6 address only once, so if the total number of ipv4 and ipv6 addresses
> are n, then it should be O(n). Please correct me if I missed something here.

I agree that the function visits and inserts each ipv4 and ipv6 address
once, which is O(n).  The issue is that xrealloc() has to copy all of
the addresses each time.  Suppose, for example, that there are 50
addresses in an address set, 1 per port.  This yields a sequence of 50
xrealloc() calls that copy 0, 1, 2, ..., 49 addresses, respectively,
which is O(n**2) copies.  The usual solution is to expand the array by
(roughly) doubling, so that there are only 0 + 1 + 2 + 4 + 8 + 16 + 32
copies total, which is O(n) copies.

Thanks,

Ben.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Han Zhou]

On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff  wrote:
>
> On Wed, Apr 04, 2018 at 05:51:48PM -0700, Han Zhou wrote:
> > Address sets are automatically generated from corresponding port
> > groups, and can be used directly in ACL match conditions.
>
> Thanks!
>
> I think that sync_address_sets() has a memory leak, because I don't see
> any free() calls that match up with the xstrdup() calls.  (I'm not sure
> that the xstrdup() calls are actually needed.)

Oops! Yes, before freeing the ipv4_addrs and ipv6_addrs, I forgot to free
the strings in them. I will fix with V3.
The xstrdup() calls are still needed, since the strings there are from char
arrays (rather than dynamic char *) in the local variable laddrs, which is
destroyed in every iteration.

>
> I don't think the xcalloc() calls are needed.  I think you can just
> initialize ipv4_addrs and ipv6_addrs to NULL.

Sure!
>
> I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
> n_ipv6_addrs, because of the allocation strategy.  If port groups get
> big (and they will eventually even if they do not today, because scale)
> I think that it would be better to expand the allocations exponentially.

Sorry that I didn't find it a problem. For each group, there are i ports,
and for each port there are j address groups (e.g. mac ip1 ip2 ip3 ...),
and for each address group there are k addresses (some of them can be ipv4
and some can be ipv6).
Although there are nested loops, this implementation iterates each ipv4 and
ipv6 address only once, so if the total number of ipv4 and ipv6 addresses
are n, then it should be O(n). Please correct me if I missed something here.

Thanks for the review!
Han
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Ben Pfaff]

On Wed, Apr 04, 2018 at 05:51:48PM -0700, Han Zhou wrote:
> Address sets are automatically generated from corresponding port
> groups, and can be used directly in ACL match conditions.

Thanks!

I think that sync_address_sets() has a memory leak, because I don't see
any free() calls that match up with the xstrdup() calls.  (I'm not sure
that the xstrdup() calls are actually needed.)

I don't think the xcalloc() calls are needed.  I think you can just
initialize ipv4_addrs and ipv6_addrs to NULL.

I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
n_ipv6_addrs, because of the allocation strategy.  If port groups get
big (and they will eventually even if they do not today, because scale)
I think that it would be better to expand the allocations exponentially.

Thanks,

Ben.
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Daniel Alvarez Sanchez]

Acked-by: Daniel Alvarez 

Thanks Han! Everything LGTM and the tests pass okay against current master.

On Thu, Apr 5, 2018 at 2:51 AM, Han Zhou  wrote:

> Address sets are automatically generated from corresponding port
> groups, and can be used directly in ACL match conditions.
>
> There are two address sets generated for each port group:
>
> _ip4
> _ip6
>
> For example, if port_group1 is created, we can directly use below
> match condition in ACL:
> "outport == @port_group1 && ip4.src == $port_group1_ip4"
>
> This will simplify OVN client implementation, and avoid some tricky
> problems such as race conditions when maintaining address set
> memberships as discussed in the link below.
>
> Reported-by: Lucas Alvares Gomes 
> Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-
> February/046174.html
> Reviewed-by: Mark Michelson 
> Reviewed-by: Daniel Alvarez 
> Signed-off-by: Han Zhou 
> ---
>
> Notes:
> v1->v2: rebase
>
>  NEWS|   3 +-
>  ovn/northd/ovn-northd.c |  87 ---
>  ovn/ovn-nb.xml  |  18 
>  ovn/ovn-sb.xml  |  23 -
>  tests/ovn.at| 226 ++
> ++
>  5 files changed, 340 insertions(+), 17 deletions(-)
>
> diff --git a/NEWS b/NEWS
> index ba9f0d8..c20edfc 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -16,7 +16,8 @@ Post-v2.9.0
> - Linux kernel 4.14
>   * Add support for compiling OVS with the latest Linux 4.14 kernel
> - OVN:
> - * Port_Group is supported in ACL match conditions.
> + * Port_Group and generated address sets are supported in ACL match
> +   conditions. See ovn-nb(5) and ovn-sb(5) for details.
>
>  v2.9.0 - 19 Feb 2018
>  
> diff --git a/ovn/northd/ovn-northd.c b/ovn/northd/ovn-northd.c
> index d4addf6..244e0cd 100644
> --- a/ovn/northd/ovn-northd.c
> +++ b/ovn/northd/ovn-northd.c
> @@ -6141,9 +6141,32 @@ build_lflows(struct northd_context *ctx, struct
> hmap *datapaths,
>  hmap_destroy();
>  }
>
> -/* OVN_Northbound and OVN_Southbound have an identical Address_Set table.
> - * We always update OVN_Southbound to match the current data in
> - * OVN_Northbound, so that the address sets used in Logical_Flows in
> +static void
> +sync_address_set(struct northd_context *ctx, const char *name,
> + const char **addrs, size_t n_addrs,
> + struct shash *sb_address_sets)
> +{
> +const struct sbrec_address_set *sb_address_set;
> +sb_address_set = shash_find_and_delete(sb_address_sets,
> +   name);
> +if (!sb_address_set) {
> +sb_address_set = sbrec_address_set_insert(ctx->ovnsb_txn);
> +sbrec_address_set_set_name(sb_address_set, name);
> +}
> +
> +sbrec_address_set_set_addresses(sb_address_set,
> +addrs, n_addrs);
> +}
> +
> +/* OVN_Southbound Address_Set table contains same records as in north
> + * bound, plus the records generated from Port_Group table in north bound.
> + *
> + * There are 2 records generated from each port group, one for IPv4, and
> + * one for IPv6, named in the format: _ip4 and
> + * _ip6 respectively. MAC addresses are ignored.
> + *
> + * We always update OVN_Southbound to match the Address_Set and Port_Group
> + * in OVN_Northbound, so that the address sets used in Logical_Flows in
>   * OVN_Southbound is checked against the proper set.*/
>  static void
>  sync_address_sets(struct northd_context *ctx)
> @@ -6155,19 +6178,55 @@ sync_address_sets(struct northd_context *ctx)
>  shash_add(_address_sets, sb_address_set->name, sb_address_set);
>  }
>
> -const struct nbrec_address_set *nb_address_set;
> -NBREC_ADDRESS_SET_FOR_EACH (nb_address_set, ctx->ovnnb_idl) {
> -sb_address_set = shash_find_and_delete(_address_sets,
> -   nb_address_set->name);
> -if (!sb_address_set) {
> -sb_address_set = sbrec_address_set_insert(ctx->ovnsb_txn);
> -sbrec_address_set_set_name(sb_address_set,
> nb_address_set->name);
> +/* sync port group generated address sets first */
> +const struct nbrec_port_group *nb_port_group;
> +NBREC_PORT_GROUP_FOR_EACH (nb_port_group, ctx->ovnnb_idl) {
> +const char **ipv4_addrs = xcalloc(1, sizeof *ipv4_addrs);
> +size_t n_ipv4_addrs = 0;
> +const char **ipv6_addrs = xcalloc(1, sizeof *ipv6_addrs);
> +size_t n_ipv6_addrs = 0;
> +for (size_t i = 0; i < nb_port_group->n_ports; i++) {
> +for (size_t j = 0; j < nb_port_group->ports[i]->n_addresses;
> j++) {
> +struct lport_addresses laddrs;
> +extract_lsp_addresses(nb_port_
> group->ports[i]->addresses[j],
> + );
> +ipv4_addrs = 

[ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

[Han Zhou]

Address sets are automatically generated from corresponding port
groups, and can be used directly in ACL match conditions.

There are two address sets generated for each port group:

_ip4
_ip6

For example, if port_group1 is created, we can directly use below
match condition in ACL:
"outport == @port_group1 && ip4.src == $port_group1_ip4"

This will simplify OVN client implementation, and avoid some tricky
problems such as race conditions when maintaining address set
memberships as discussed in the link below.

Reported-by: Lucas Alvares Gomes 
Reported-at: 
https://mail.openvswitch.org/pipermail/ovs-discuss/2018-February/046174.html
Reviewed-by: Mark Michelson 
Reviewed-by: Daniel Alvarez 
Signed-off-by: Han Zhou 
---

Notes:
v1->v2: rebase

 NEWS|   3 +-
 ovn/northd/ovn-northd.c |  87 ---
 ovn/ovn-nb.xml  |  18 
 ovn/ovn-sb.xml  |  23 -
 tests/ovn.at| 226 
 5 files changed, 340 insertions(+), 17 deletions(-)

diff --git a/NEWS b/NEWS
index ba9f0d8..c20edfc 100644
--- a/NEWS
+++ b/NEWS
@@ -16,7 +16,8 @@ Post-v2.9.0
- Linux kernel 4.14
  * Add support for compiling OVS with the latest Linux 4.14 kernel
- OVN:
- * Port_Group is supported in ACL match conditions.
+ * Port_Group and generated address sets are supported in ACL match
+   conditions. See ovn-nb(5) and ovn-sb(5) for details.
 
 v2.9.0 - 19 Feb 2018
 
diff --git a/ovn/northd/ovn-northd.c b/ovn/northd/ovn-northd.c
index d4addf6..244e0cd 100644
--- a/ovn/northd/ovn-northd.c
+++ b/ovn/northd/ovn-northd.c
@@ -6141,9 +6141,32 @@ build_lflows(struct northd_context *ctx, struct hmap 
*datapaths,
 hmap_destroy();
 }
 
-/* OVN_Northbound and OVN_Southbound have an identical Address_Set table.
- * We always update OVN_Southbound to match the current data in
- * OVN_Northbound, so that the address sets used in Logical_Flows in
+static void
+sync_address_set(struct northd_context *ctx, const char *name,
+ const char **addrs, size_t n_addrs,
+ struct shash *sb_address_sets)
+{
+const struct sbrec_address_set *sb_address_set;
+sb_address_set = shash_find_and_delete(sb_address_sets,
+   name);
+if (!sb_address_set) {
+sb_address_set = sbrec_address_set_insert(ctx->ovnsb_txn);
+sbrec_address_set_set_name(sb_address_set, name);
+}
+
+sbrec_address_set_set_addresses(sb_address_set,
+addrs, n_addrs);
+}
+
+/* OVN_Southbound Address_Set table contains same records as in north
+ * bound, plus the records generated from Port_Group table in north bound.
+ *
+ * There are 2 records generated from each port group, one for IPv4, and
+ * one for IPv6, named in the format: _ip4 and
+ * _ip6 respectively. MAC addresses are ignored.
+ *
+ * We always update OVN_Southbound to match the Address_Set and Port_Group
+ * in OVN_Northbound, so that the address sets used in Logical_Flows in
  * OVN_Southbound is checked against the proper set.*/
 static void
 sync_address_sets(struct northd_context *ctx)
@@ -6155,19 +6178,55 @@ sync_address_sets(struct northd_context *ctx)
 shash_add(_address_sets, sb_address_set->name, sb_address_set);
 }
 
-const struct nbrec_address_set *nb_address_set;
-NBREC_ADDRESS_SET_FOR_EACH (nb_address_set, ctx->ovnnb_idl) {
-sb_address_set = shash_find_and_delete(_address_sets,
-   nb_address_set->name);
-if (!sb_address_set) {
-sb_address_set = sbrec_address_set_insert(ctx->ovnsb_txn);
-sbrec_address_set_set_name(sb_address_set, nb_address_set->name);
+/* sync port group generated address sets first */
+const struct nbrec_port_group *nb_port_group;
+NBREC_PORT_GROUP_FOR_EACH (nb_port_group, ctx->ovnnb_idl) {
+const char **ipv4_addrs = xcalloc(1, sizeof *ipv4_addrs);
+size_t n_ipv4_addrs = 0;
+const char **ipv6_addrs = xcalloc(1, sizeof *ipv6_addrs);
+size_t n_ipv6_addrs = 0;
+for (size_t i = 0; i < nb_port_group->n_ports; i++) {
+for (size_t j = 0; j < nb_port_group->ports[i]->n_addresses; j++) {
+struct lport_addresses laddrs;
+extract_lsp_addresses(nb_port_group->ports[i]->addresses[j],
+ );
+ipv4_addrs = xrealloc(ipv4_addrs,
+(n_ipv4_addrs + laddrs.n_ipv4_addrs)
+* sizeof *ipv4_addrs);
+for (size_t k = 0; k < laddrs.n_ipv4_addrs; k++) {
+ipv4_addrs[n_ipv4_addrs++] =
+xstrdup(laddrs.ipv4_addrs[k].addr_s);
+}
+ipv6_addrs = xrealloc(ipv6_addrs,
+