Re: [ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups
> 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
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
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
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 ScheurichCc: 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
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 >
[ovs-dev] [PATCH v2 2/3] ofproto-dpif: Improve dp_hash selection method for select groups
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 ScheurichSigned-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 xlate_dp_hash_select_group(struct xlate_ctx *ctx, struct group_dpif *group, bool is_last_action) { -struct ofputil_bucket *bucket; - /* dp_hash value 0 is special since it means that the dp_hash has not been * computed, as all computed dp_hash values are non-zero. Therefore * compare to zero can be used to decide if the dp_hash value is valid * without masking the dp_hash field. */ if (!ctx->xin->flow.dp_hash) { -uint64_t param = group->up.props.selection_method_param; - -ctx_trigger_recirculate_with_hash(ctx, param >> 32, (uint32_t)param); +ctx_trigger_recirculate_with_hash(ctx, group->hash_alg, + group->hash_basis); +if (ctx->xin->xcache) { +ofproto_group_unref(>up); +} } else { -