ceph: make CRUSH hash function a bucket property

Make the integer hash function a property of the bucket it is used on.  This
allows us to gracefully add support for new hash functions without starting
from scatch.

Signed-off-by: Sage Weil <sage@newdream.net>

4 files changed, 91 insertions, 20 deletions

diff --git a/fs/ceph/crush/crush.h b/fs/ceph/crush/crush.h
index 92c6b3c3a57..dcd7e752370 100644
--- a/fs/ceph/crush/crush.h
+++ b/fs/ceph/crush/crush.h
@@ -102,7 +102,8 @@ extern const char *crush_bucket_alg_name(int alg);
 struct crush_bucket {
         __s32 id;        /* this'll be negative */
         __u16 type;      /* non-zero; type=0 is reserved for devices */
-        __u16 alg;       /* one of CRUSH_BUCKET_* */
+        __u8 alg;        /* one of CRUSH_BUCKET_* */
+        __u8 hash;       /* which hash function to use, CRUSH_HASH_* */
         __u32 weight;    /* 16-bit fixed point */
         __u32 size;      /* num items */
         __s32 *items;
diff --git a/fs/ceph/crush/hash.c b/fs/ceph/crush/hash.c
index b438c5d2781..5873aed694b 100644
--- a/fs/ceph/crush/hash.c
+++ b/fs/ceph/crush/hash.c
@@ -1,5 +1,6 @@
 
 #include <linux/types.h>
+#include "hash.h"
 
 /*
  * Robert Jenkins' function for mixing 32-bit values
@@ -20,7 +21,7 @@
 
 #define crush_hash_seed 1315423911
 
-__u32 crush_hash32(__u32 a)
+static __u32 crush_hash32_rjenkins1(__u32 a)
 {
         __u32 hash = crush_hash_seed ^ a;
         __u32 b = a;
@@ -31,7 +32,7 @@ __u32 crush_hash32(__u32 a)
         return hash;
 }
 
-__u32 crush_hash32_2(__u32 a, __u32 b)
+static __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b)
 {
         __u32 hash = crush_hash_seed ^ a ^ b;
         __u32 x = 231232;
@@ -42,7 +43,7 @@ __u32 crush_hash32_2(__u32 a, __u32 b)
         return hash;
 }
 
-__u32 crush_hash32_3(__u32 a, __u32 b, __u32 c)
+static __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c)
 {
         __u32 hash = crush_hash_seed ^ a ^ b ^ c;
         __u32 x = 231232;
@@ -55,7 +56,7 @@ __u32 crush_hash32_3(__u32 a, __u32 b, __u32 c)
         return hash;
 }
 
-__u32 crush_hash32_4(__u32 a, __u32 b, __u32 c, __u32 d)
+static __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d)
 {
         __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d;
         __u32 x = 231232;
@@ -69,7 +70,8 @@ __u32 crush_hash32_4(__u32 a, __u32 b, __u32 c, __u32 d)
         return hash;
 }
 
-__u32 crush_hash32_5(__u32 a, __u32 b, __u32 c, __u32 d, __u32 e)
+static __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d,
+                                      __u32 e)
 {
         __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e;
         __u32 x = 231232;
@@ -84,3 +86,64 @@ __u32 crush_hash32_5(__u32 a, __u32 b, __u32 c, __u32 d, __u32 e)
         crush_hashmix(y, e, hash);
         return hash;
 }
+
+
+__u32 crush_hash32(int type, __u32 a)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return crush_hash32_rjenkins1(a);
+        default:
+                return 0;
+        }
+}
+
+__u32 crush_hash32_2(int type, __u32 a, __u32 b)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return crush_hash32_rjenkins1_2(a, b);
+        default:
+                return 0;
+        }
+}
+
+__u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return crush_hash32_rjenkins1_3(a, b, c);
+        default:
+                return 0;
+        }
+}
+
+__u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return crush_hash32_rjenkins1_4(a, b, c, d);
+        default:
+                return 0;
+        }
+}
+
+__u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return crush_hash32_rjenkins1_5(a, b, c, d, e);
+        default:
+                return 0;
+        }
+}
+
+const char *crush_hash_name(int type)
+{
+        switch (type) {
+        case CRUSH_HASH_RJENKINS1:
+                return "rjenkins1";
+        default:
+                return "unknown";
+        }
+}
diff --git a/fs/ceph/crush/hash.h b/fs/ceph/crush/hash.h
index 9ce89f85dc7..ff48e110e4b 100644
--- a/fs/ceph/crush/hash.h
+++ b/fs/ceph/crush/hash.h
@@ -1,12 +1,17 @@
 #ifndef _CRUSH_HASH_H
 #define _CRUSH_HASH_H
 
-extern __u32 crush_hash32(__u32 a);
-extern __u32 crush_hash32_2(__u32 a, __u32 b);
-extern __u32 crush_hash32_3(__u32 a, __u32 b, __u32 c);
-extern __u32 crush_hash32_4(__u32 a, __u32 b, __u32 c,
-                            __u32 d);
-extern __u32 crush_hash32_5(__u32 a, __u32 b, __u32 c,
-                            __u32 d, __u32 e);
+#define CRUSH_HASH_RJENKINS1   0
+
+#define CRUSH_HASH_DEFAULT CRUSH_HASH_RJENKINS1
+
+extern const char *crush_hash_name(int type);
+
+extern __u32 crush_hash32(int type, __u32 a);
+extern __u32 crush_hash32_2(int type, __u32 a, __u32 b);
+extern __u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c);
+extern __u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d);
+extern __u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d,
+                            __u32 e);
 
 #endif
diff --git a/fs/ceph/crush/mapper.c b/fs/ceph/crush/mapper.c
index 54f3f402af6..2523d448445 100644
--- a/fs/ceph/crush/mapper.c
+++ b/fs/ceph/crush/mapper.c
@@ -78,7 +78,7 @@ static int bucket_perm_choose(struct crush_bucket *bucket,
 
                 /* optimize common r=0 case */
                 if (pr == 0) {
-                        s = crush_hash32_3(x, bucket->id, 0) %
+                        s = crush_hash32_3(bucket->hash, x, bucket->id, 0) %
                                 bucket->size;
                         bucket->perm[0] = s;
                         bucket->perm_n = 0xffff;   /* magic value, see below */
@@ -103,7 +103,7 @@ static int bucket_perm_choose(struct crush_bucket *bucket,
                 unsigned p = bucket->perm_n;
                 /* no point in swapping the final entry */
                 if (p < bucket->size - 1) {
-                        i = crush_hash32_3(x, bucket->id, p) %
+                        i = crush_hash32_3(bucket->hash, x, bucket->id, p) %
                                 (bucket->size - p);
                         if (i) {
                                 unsigned t = bucket->perm[p + i];
@@ -138,8 +138,8 @@ static int bucket_list_choose(struct crush_bucket_list *bucket,
         int i;
 
         for (i = bucket->h.size-1; i >= 0; i--) {
-                __u64 w = crush_hash32_4(x, bucket->h.items[i], r,
-                                         bucket->h.id);
+                __u64 w = crush_hash32_4(bucket->h.hash,x, bucket->h.items[i],
+                                         r, bucket->h.id);
                 w &= 0xffff;
                 dprintk("list_choose i=%d x=%d r=%d item %d weight %x "
                         "sw %x rand %llx",
@@ -198,7 +198,8 @@ static int bucket_tree_choose(struct crush_bucket_tree *bucket,
         while (!terminal(n)) {
                 /* pick point in [0, w) */
                 w = bucket->node_weights[n];
-                t = (__u64)crush_hash32_4(x, n, r, bucket->h.id) * (__u64)w;
+                t = (__u64)crush_hash32_4(bucket->h.hash, x, n, r,
+                                          bucket->h.id) * (__u64)w;
                 t = t >> 32;
 
                 /* descend to the left or right? */
@@ -224,7 +225,7 @@ static int bucket_straw_choose(struct crush_bucket_straw *bucket,
         __u64 draw;
 
         for (i = 0; i < bucket->h.size; i++) {
-                draw = crush_hash32_3(x, bucket->h.items[i], r);
+                draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r);
                 draw &= 0xffff;
                 draw *= bucket->straws[i];
                 if (i == 0 || draw > high_draw) {
@@ -267,7 +268,8 @@ static int is_out(struct crush_map *map, __u32 *weight, int item, int x)
                 return 0;
         if (weight[item] == 0)
                 return 1;
-        if ((crush_hash32_2(x, item) & 0xffff) < weight[item])
+        if ((crush_hash32_2(CRUSH_HASH_RJENKINS1, x, item) & 0xffff)
+            < weight[item])
                 return 0;
         return 1;
 }