Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups

2018-04-18 Thread Jan Scheurich 
> How about this approach, which should cleanly eliminate the warning?
> 
> diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
> index e1a5c097f3aa..362339a4abb4 100644
> --- a/ofproto/ofproto-dpif.c
> +++ b/ofproto/ofproto-dpif.c
> @@ -4780,22 +4780,17 @@ group_setup_dp_hash_table(struct group_dpif *group, 
> size_t max_hash)
> 
>  /* Use Webster method to distribute hash values over buckets. */
>  for (int hash = 0; hash < n_hash; hash++) {
> -double max_val = 0.0;
> -struct webster *winner;
> -for (i = 0; i < n_buckets; i++) {
> -if (webster[i].value > max_val) {
> -max_val = webster[i].value;
> +struct webster *winner = [0];
> +for (i = 1; i < n_buckets; i++) {
> +if (webster[i].value > winner->value) {
>  winner = [i];
>  }
>  }
> -#pragma GCC diagnostic push
> -#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
>  /* winner is a reference to a webster[] element initialized above. */
>  winner->divisor += 2;
>  winner->value = (double) winner->bucket->weight / winner->divisor;
>  group->hash_map[hash] = winner->bucket;
>  winner->bucket->aux++;
> -#pragma GCC diagnostic pop
>  }

Thank you, Ben, for your thorough checks. Yes, your approach is better and 
compiles w/o warnings. 
 
Regards, Jan


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

Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups

2018-04-17 Thread Ben Pfaff 
On Tue, Apr 17, 2018 at 01:03:17PM -0700, Ben Pfaff wrote:
> On Mon, Apr 16, 2018 at 04:26:27PM +0200, Jan Scheurich wrote:
> > The current implementation of the "dp_hash" selection method suffers
> > from two deficiences: 1. The hash mask and hence the number of dp_hash
> > values is just large enough to cover the number of group buckets, but
> > does not consider the case that buckets have different weights. 2. The
> > xlate-time selection of best bucket from the masked dp_hash value often
> > results in bucket load distributions that are quite different from the
> > bucket weights because the number of available masked dp_hash values
> > is too small (2-6 bits compared to 32 bits of a full hash in the default
> > hash selection method).
> 
> Clang gives me the following errors:
> 
> ../ofproto/ofproto-dpif.c:4792:32: error: unknown warning group 
> '-Wmaybe-uninitialized', ignored [-Werror,-Wunknown-pragmas]
> ../ofproto/ofproto-dpif.c:4814:33: error: initializing 'struct 
> ofputil_group_props *' with an expression of type 'const struct 
> ofputil_group_props *' discards qualifiers 
> [-Werror,-Wincompatible-pointer-types-discards-qualifiers]

How about this approach, which should cleanly eliminate the warning?

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index e1a5c097f3aa..362339a4abb4 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -4780,22 +4780,17 @@ group_setup_dp_hash_table(struct group_dpif *group, 
size_t max_hash)
 
 /* Use Webster method to distribute hash values over buckets. */
 for (int hash = 0; hash < n_hash; hash++) {
-double max_val = 0.0;
-struct webster *winner;
-for (i = 0; i < n_buckets; i++) {
-if (webster[i].value > max_val) {
-max_val = webster[i].value;
+struct webster *winner = [0];
+for (i = 1; i < n_buckets; i++) {
+if (webster[i].value > winner->value) {
 winner = [i];
 }
 }
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 /* winner is a reference to a webster[] element initialized above. */
 winner->divisor += 2;
 winner->value = (double) winner->bucket->weight / winner->divisor;
 group->hash_map[hash] = winner->bucket;
 winner->bucket->aux++;
-#pragma GCC diagnostic pop
 }
 
 LIST_FOR_EACH (bucket, list_node, >up.buckets) {
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups

2018-04-17 Thread Ben Pfaff 
On Mon, Apr 16, 2018 at 04:26:27PM +0200, Jan Scheurich wrote:
> The current implementation of the "dp_hash" selection method suffers
> from two deficiences: 1. The hash mask and hence the number of dp_hash
> values is just large enough to cover the number of group buckets, but
> does not consider the case that buckets have different weights. 2. The
> xlate-time selection of best bucket from the masked dp_hash value often
> results in bucket load distributions that are quite different from the
> bucket weights because the number of available masked dp_hash values
> is too small (2-6 bits compared to 32 bits of a full hash in the default
> hash selection method).

Clang gives me the following errors:

../ofproto/ofproto-dpif.c:4792:32: error: unknown warning group 
'-Wmaybe-uninitialized', ignored [-Werror,-Wunknown-pragmas]
../ofproto/ofproto-dpif.c:4814:33: error: initializing 'struct 
ofputil_group_props *' with an expression of type 'const struct 
ofputil_group_props *' discards qualifiers 
[-Werror,-Wincompatible-pointer-types-discards-qualifiers]

"sparse" gives me the following errors:

../ofproto/ofproto-dpif.c:4742:24: error: Variable length array is used.
../ofproto/ofproto-dpif.c:4814:42: error: incorrect type in initializer 
(different modifiers)
../ofproto/ofproto-dpif.c:4814:42:expected struct ofputil_group_props 
*props
../ofproto/ofproto-dpif.c:4814:42:got struct ofputil_group_props const 
*

Thanks,

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

Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups

2018-04-17 Thread Jan Scheurich 
Hi Ychen,

Thank you for finding yet another corner case. I will fix it in the next 
version with the following incremental:

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 8f71083..674b3b5 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -4762,6 +4762,11 @@ group_setup_dp_hash_table(struct group_dpif *group, 
size_t max_hash)
 VLOG_DBG("  Minimum weight: %d, total weight: %.0f",
  min_weight, total_weight);

+if (total_weight == 0) {
+VLOG_DBG("  Total weight is zero. No active buckets.");
+return false;
+}
+
 uint32_t min_slots = ceil(total_weight / min_weight);
 n_hash = MAX(16, 1L << log_2_ceil(min_slots));

I would like to mention your contribution with Tested-By: tag in the commit 
messages. Would that be ok? What is your real name I should put?

BR, Jan


From: ychen [mailto:ychen103...@163.com]
Sent: Tuesday, 17 April, 2018 13:22
To: Jan Scheurich 
Cc: d...@openvswitch.org; Nitin Katiyar ; 
b...@ovn.org
Subject: Re:[PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for 
select groups

Hi, Jan:
I think the following code should also be modified
 + for (int hash = 0; hash < n_hash; hash++) {
+ double max_val = 0.0;
+ struct webster *winner;

+for (i = 0; i < n_buckets; i++) {

+if (webster[i].value > max_val) {  ===> if 
bucket->weight=0, and there is only one bucket with weight equal to 0, then 
winner will be null

+max_val = webster[i].value;

+winner = [i];

+}

+}



   Test like this command:

   ovs-ofctl add-group br-int -O openflow15 
"group_id=2,type=select,selection_method=dp_hash,bucket=bucket_id=1,weight=0,actions=output:10"

  vswitchd crashed after command put.



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

Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups

2018-04-17 Thread ychen 
Hi, Jan:
I think the following code should also be modified
 + for (int hash = 0; hash < n_hash; hash++) {
+ double max_val = 0.0;
+ struct webster *winner;
+for (i = 0; i < n_buckets; i++) {
+if (webster[i].value > max_val) {  ===> if 
bucket->weight=0, and there is only one bucket with weight equal to 0, then 
winner will be null
+max_val = webster[i].value;
+winner = [i];
+}

+}


   Test like this command:
   ovs-ofctl add-group br-int -O openflow15 
"group_id=2,type=select,selection_method=dp_hash,bucket=bucket_id=1,weight=0,actions=output:10"
  vswitchd crashed after command put.



At 2018-04-16 22:26:27, "Jan Scheurich"  wrote:
>The current implementation of the "dp_hash" selection method suffers
>from two deficiences: 1. The hash mask and hence the number of dp_hash
>values is just large enough to cover the number of group buckets, but
>does not consider the case that buckets have different weights. 2. The
>xlate-time selection of best bucket from the masked dp_hash value often
>results in bucket load distributions that are quite different from the
>bucket weights because the number of available masked dp_hash values
>is too small (2-6 bits compared to 32 bits of a full hash in the default
>hash selection method).
>
>This commit provides a more accurate implementation of the dp_hash
>select group by applying the well known Webster method for distributing
>a small number of "seats" fairly over the weighted "parties"
>(see https://en.wikipedia.org/wiki/Webster/Sainte-Lagu%C3%AB_method).
>The dp_hash mask is autmatically chosen large enough to provide good
>enough accuracy even with widely differing weights.
>
>This distribution happens at group modification time and the resulting
>table is stored with the group-dpif struct. At xlation time, we use the
>masked dp_hash values as index to look up the assigned bucket.
>
>If the bucket should not be live, we do a circular search over the
>mapping table until we find the first live bucket. As the buckets in
>the table are by construction in pseudo-random order with a frequency
>according to their weight, this method maintains correct distribution
>even if one or more buckets are non-live.
>
>Xlation is further simplified by storing some derived select group state
>at group construction in struct group-dpif in a form better suited for
>xlation purposes.
>
>Adapted the unit test case for dp_hash select group accordingly.
>
>Signed-off-by: Jan Scheurich 
>Signed-off-by: Nitin Katiyar 
>Co-authored-by: Nitin Katiyar 
>---
> include/openvswitch/ofp-group.h |   1 +
> ofproto/ofproto-dpif-xlate.c|  74 +---
> ofproto/ofproto-dpif.c  | 146 
> ofproto/ofproto-dpif.h  |  13 
> tests/ofproto-dpif.at   |  18 +++--
> 5 files changed, 221 insertions(+), 31 deletions(-)
>
>diff --git a/include/openvswitch/ofp-group.h b/include/openvswitch/ofp-group.h
>index 8d893a5..af4033d 100644
>--- a/include/openvswitch/ofp-group.h
>+++ b/include/openvswitch/ofp-group.h
>@@ -47,6 +47,7 @@ struct bucket_counter {
> /* Bucket for use in groups. */
> struct ofputil_bucket {
> struct ovs_list list_node;
>+uint16_t aux;   /* Padding. Also used for temporary data. */
> uint16_t weight;/* Relative weight, for "select" groups. */
> ofp_port_t watch_port;  /* Port whose state affects whether this 
> bucket
>  * is live. Only required for fast failover
>diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
>index c8baba1..df245c5 100644
>--- a/ofproto/ofproto-dpif-xlate.c
>+++ b/ofproto/ofproto-dpif-xlate.c
>@@ -4235,35 +4235,55 @@ xlate_hash_fields_select_group(struct xlate_ctx *ctx, 
>struct group_dpif *group,
> }
> }
> 
>+static struct ofputil_bucket *
>+group_dp_hash_best_bucket(struct xlate_ctx *ctx,
>+  const struct group_dpif *group,
>+  uint32_t dp_hash)
>+{
>+struct ofputil_bucket *bucket, *best_bucket = NULL;
>+uint32_t n_hash = group->hash_mask + 1;
>+
>+uint32_t hash = dp_hash &= group->hash_mask;
>+ctx->wc->masks.dp_hash |= group->hash_mask;
>+
>+/* Starting from the original masked dp_hash value iterate over the
>+ * hash mapping table to find the first live bucket. As the buckets
>+ * are quasi-randomly spread over the hash values, this maintains
>+ * a distribution according to bucket weights even when some buckets
>+ * are non-live. */
>+for (int i = 0; i < n_hash; i++) {
>+bucket = group->hash_map[(hash + i) % n_hash];
>+if (bucket_is_alive(ctx, bucket, 0)) {
>+best_bucket = bucket;
>+break;
>+}
>+}
>+
>+return best_bucket;
>+}
>+
> static void
>