[ovs-dev] [PATCH v8 15/16] ofproto-dpif: Translation of select groups

[Ben Pfaff]

On Wed, Oct 30, 2013 at 06:17:19PM +0900, Simon Horman wrote:
> Select bucket from those that are alive based on a hash of the destination
> ethernet address of the packet.
> 
> Support for weights is proposed by a subsequent patch.
> 
> The selection is based on a hash of the destination ethernet
> address of the flow. It should be possible to extend
> this to cover a hash of user-specified elements of the flow.
> 
> Signed-off-by: Simon Horman <horms at verge.net.au>

The method used to select a group seemed really heavyweight to me.  I
replaced by a simpler "highest random weight" implementation:

diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
index 6537205..5c22db3 100644
--- a/ofproto/ofproto-dpif-xlate.c
+++ b/ofproto/ofproto-dpif-xlate.c
@@ -796,20 +796,31 @@ group_first_live_bucket(const struct xlate_ctx *ctx,
     return NULL;
 }
 
-static void
-group_all_live_buckets(const struct xlate_ctx *ctx,
+static const struct ofputil_bucket *
+group_best_live_bucket(const struct xlate_ctx *ctx,
                        const struct group_dpif *group,
-                       struct ofpbuf *live_buckets)
+                       uint32_t basis)
 {
-    struct ofputil_bucket *bucket;
+    const struct ofputil_bucket *best_bucket = NULL;
+    uint32_t best_score = 0;
+    int i = 0;
+
+    const struct ofputil_bucket *bucket;
     const struct list *buckets;
 
     group_dpif_get_buckets(group, &buckets);
     LIST_FOR_EACH (bucket, list_node, buckets) {
         if (bucket_is_alive(ctx, bucket, 0)) {
-            ofpbuf_push(live_buckets, &bucket, sizeof bucket);
+            uint32_t score = hash_int(i, basis);
+            if (score >= best_score) {
+                best_bucket = bucket;
+                best_score = score;
+            }
         }
+        i++;
     }
+
+    return best_bucket;
 }
 
 static bool
@@ -1932,27 +1943,15 @@ static void
 xlate_select_group(struct xlate_ctx *ctx, struct group_dpif *group)
 {
     struct flow_wildcards *wc = &ctx->xout->wc;
-    const struct ofputil_bucket **bucket;
-    struct ofputil_bucket *stub[1024 / sizeof *bucket];
-    struct ofpbuf live_buckets;
-    uint32_t hash;
+    const struct ofputil_bucket *bucket;
+    uint32_t basis;
 
-    ofpbuf_use_stub(&live_buckets, stub, sizeof stub);
-    group_all_live_buckets(ctx, group, &live_buckets);
-    if (live_buckets.size == 0) {
-        goto out;
+    basis = hash_bytes(ctx->xin->flow.dl_dst, sizeof ctx->xin->flow.dl_dst, 0);
+    bucket = group_best_live_bucket(ctx, group, basis);
+    if (bucket) {
+        memset(&wc->masks.dl_dst, 0xff, sizeof wc->masks.dl_dst);
+        xlate_group_bucket(ctx, bucket);
     }
-
-    memset(&wc->masks.dl_dst, 0xff, sizeof wc->masks.dl_dst);
-
-    hash = hash_bytes(ctx->xin->flow.dl_dst, sizeof ctx->xin->flow.dl_dst, 0);
-    bucket = ofpbuf_at_assert(&live_buckets,
-                              (hash % (live_buckets.size / sizeof *bucket)) *
-                               sizeof *bucket, sizeof *bucket);
-    xlate_group_bucket(ctx, *bucket);
-
-out:
-    ofpbuf_uninit(&live_buckets);
 }
 
 static void