From 89d46be4363e5ecdf976c79a5e875fbc0d8dab9b Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Sat, 7 Nov 2009 19:59:05 -0800 Subject: [PATCH] crush: make hash function selectable --- src/crush/CrushWrapper.h | 7 ++++ src/crush/builder.c | 4 +++ src/crush/crush.h | 3 +- src/crush/grammar.h | 51 +++++++++++++++------------- src/crush/hash.c | 73 +++++++++++++++++++++++++++++++++++++--- src/crush/hash.h | 17 ++++++---- src/crush/mapper.c | 16 +++++---- src/crushtool.cc | 3 ++ src/osd/OSDMap.h | 4 +-- 9 files changed, 132 insertions(+), 46 deletions(-) diff --git a/src/crush/CrushWrapper.h b/src/crush/CrushWrapper.h index 432c7593273cc..e24d572d7adcb 100644 --- a/src/crush/CrushWrapper.h +++ b/src/crush/CrushWrapper.h @@ -291,6 +291,11 @@ public: if (IS_ERR(b)) return PTR_ERR(b); return b->alg; } + int get_bucket_hash(int id) { + crush_bucket *b = get_bucket(id); + if (IS_ERR(b)) return PTR_ERR(b); + return b->hash; + } int get_bucket_size(int id) { crush_bucket *b = get_bucket(id); if (IS_ERR(b)) return PTR_ERR(b); @@ -369,6 +374,7 @@ public: ::encode(crush->buckets[i]->id, bl); ::encode(crush->buckets[i]->type, bl); + ::encode(crush->buckets[i]->hash, bl); ::encode(crush->buckets[i]->alg, bl); ::encode(crush->buckets[i]->weight, bl); ::encode(crush->buckets[i]->size, bl); @@ -463,6 +469,7 @@ public: ::decode(crush->buckets[i]->id, blp); ::decode(crush->buckets[i]->type, blp); + ::decode(crush->buckets[i]->hash, blp); ::decode(crush->buckets[i]->alg, blp); ::decode(crush->buckets[i]->weight, blp); ::decode(crush->buckets[i]->size, blp); diff --git a/src/crush/builder.c b/src/crush/builder.c index a10f7a455efbb..c0d9e7a2b404f 100644 --- a/src/crush/builder.c +++ b/src/crush/builder.c @@ -152,6 +152,7 @@ crush_make_uniform_bucket(int type, int size, memset(bucket, 0, sizeof(*bucket)); bucket->h.alg = CRUSH_BUCKET_UNIFORM; bucket->h.type = type; + bucket->h.hash = CRUSH_HASH_RJENKINS1; bucket->h.size = size; bucket->h.weight = size * item_weight; @@ -181,6 +182,7 @@ crush_make_list_bucket(int type, int size, memset(bucket, 0, sizeof(*bucket)); bucket->h.alg = CRUSH_BUCKET_LIST; bucket->h.type = type; + bucket->h.hash = CRUSH_HASH_RJENKINS1; bucket->h.size = size; bucket->h.items = malloc(sizeof(__u32)*size); @@ -239,6 +241,7 @@ crush_make_tree_bucket(int type, int size, memset(bucket, 0, sizeof(*bucket)); bucket->h.alg = CRUSH_BUCKET_TREE; bucket->h.type = type; + bucket->h.hash = CRUSH_HASH_RJENKINS1; bucket->h.size = size; bucket->h.items = malloc(sizeof(__u32)*size); @@ -295,6 +298,7 @@ crush_make_straw_bucket(int type, memset(bucket, 0, sizeof(*bucket)); bucket->h.alg = CRUSH_BUCKET_STRAW; bucket->h.type = type; + bucket->h.hash = CRUSH_HASH_RJENKINS1; bucket->h.size = size; bucket->h.items = malloc(sizeof(__u32)*size); diff --git a/src/crush/crush.h b/src/crush/crush.h index 92c6b3c3a5711..dcd7e75237007 100644 --- a/src/crush/crush.h +++ b/src/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/src/crush/grammar.h b/src/crush/grammar.h index a9b7407c99b9f..272cfd916143d 100644 --- a/src/crush/grammar.h +++ b/src/crush/grammar.h @@ -24,26 +24,26 @@ using namespace boost::spirit; struct crush_grammar : public grammar { - static const int _int = 1; - static const int _posint = 2; - static const int _negint = 3; - static const int _name = 4; - - static const int _device = 12; - static const int _bucket_type = 13; - static const int _bucket_id = 14; - static const int _bucket_alg = 15; - static const int _bucket_item = 16; - static const int _bucket = 17; - - static const int _step_take = 18; - static const int _step_choose = 19; - static const int _step_chooseleaf = 20; - static const int _step_emit = 21; - static const int _step = 22; - static const int _crushrule = 23; - - static const int _crushmap = 24; + enum { + _int = 1, + _posint, + _negint, + _name, + _device, + _bucket_type, + _bucket_id, + _bucket_alg, + _bucket_hash, + _bucket_item, + _bucket, + _step_take, + _step_choose, + _step_chooseleaf, + _step_emit, + _step, + _crushrule, + _crushmap, + }; template struct definition @@ -55,15 +55,16 @@ struct crush_grammar : public grammar rule, parser_tag<_device> > device; - rule, parser_tag<_bucket_type> > bucket_type; + rule, parser_tag<_bucket_type> > bucket_type; rule, parser_tag<_bucket_id> > bucket_id; - rule, parser_tag<_bucket_alg> > bucket_alg; - rule, parser_tag<_bucket_item> > bucket_item; + rule, parser_tag<_bucket_alg> > bucket_alg; + rule, parser_tag<_bucket_hash> > bucket_hash; + rule, parser_tag<_bucket_item> > bucket_item; rule, parser_tag<_bucket> > bucket; rule, parser_tag<_step_take> > step_take; - rule, parser_tag<_step_choose> > step_choose; + rule, parser_tag<_step_choose> > step_choose; rule, parser_tag<_step_chooseleaf> > step_chooseleaf; rule, parser_tag<_step_emit> > step_emit; rule, parser_tag<_step> > step; @@ -93,6 +94,8 @@ struct crush_grammar : public grammar str_p("list") | str_p("tree") | str_p("straw") ); + bucket_hash = str_p("hash") >> ( integer | + str_p("rjenkins1") ); bucket_item = str_p("item") >> name >> !( str_p("weight") >> real_p ) >> !( str_p("pos") >> posint ); diff --git a/src/crush/hash.c b/src/crush/hash.c index b438c5d278161..5873aed694bf5 100644 --- a/src/crush/hash.c +++ b/src/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/src/crush/hash.h b/src/crush/hash.h index 9ce89f85dc7d7..ab7bb532d250e 100644 --- a/src/crush/hash.h +++ b/src/crush/hash.h @@ -1,12 +1,15 @@ #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 + +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/src/crush/mapper.c b/src/crush/mapper.c index 54f3f402af60b..2523d448445c1 100644 --- a/src/crush/mapper.c +++ b/src/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/src/crushtool.cc b/src/crushtool.cc index dd1cf9cdf569e..7fd99a838b5b0 100644 --- a/src/crushtool.cc +++ b/src/crushtool.cc @@ -531,6 +531,9 @@ int decompile_crush(CrushWrapper &crush, ostream &out) } out << "\n"; + int hash = crush.get_bucket_hash(i); + out << "\thash " << hash << "\t# " << crush_hash_name(hash) << "\n"; + for (int j=0; j