From fb690390e305ea51e1883b105c7d3c52d7100ba5 Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Sat, 7 Nov 2009 20:18:22 -0800 Subject: [PATCH] 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 --- fs/ceph/crush/crush.h | 3 +- fs/ceph/crush/hash.c | 73 +++++++++++++++++++++++++++++++++++++++--- fs/ceph/crush/hash.h | 19 +++++++---- fs/ceph/crush/mapper.c | 16 +++++---- fs/ceph/osdmap.c | 3 +- 5 files changed, 93 insertions(+), 21 deletions(-) diff --git a/fs/ceph/crush/crush.h b/fs/ceph/crush/crush.h index 92c6b3c3a571..dcd7e7523700 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 b438c5d27816..5873aed694bf 100644 --- a/fs/ceph/crush/hash.c +++ b/fs/ceph/crush/hash.c @@ -1,5 +1,6 @@ #include +#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 9ce89f85dc7d..ff48e110e4bb 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 54f3f402af60..2523d448445c 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; } diff --git a/fs/ceph/osdmap.c b/fs/ceph/osdmap.c index 68478270ad70..8c994c714781 100644 --- a/fs/ceph/osdmap.c +++ b/fs/ceph/osdmap.c @@ -210,7 +210,8 @@ static struct crush_map *crush_decode(void *pbyval, void *end) ceph_decode_need(p, end, 4*sizeof(u32), bad); b->id = ceph_decode_32(p); b->type = ceph_decode_16(p); - b->alg = ceph_decode_16(p); + b->alg = ceph_decode_8(p); + b->hash = ceph_decode_8(p); b->weight = ceph_decode_32(p); b->size = ceph_decode_32(p); -- 2.39.5