From c248cd24febeedeee5c5c1bc7c3d16a759c1e5bf Mon Sep 17 00:00:00 2001 From: sageweil Date: Wed, 17 Oct 2007 18:07:19 +0000 Subject: [PATCH] partial C port of crush git-svn-id: https://ceph.svn.sf.net/svnroot/ceph@1957 29311d96-e01e-0410-9327-a35deaab8ce9 --- trunk/ceph/crush2/Makefile | 26 ++++ trunk/ceph/crush2/buckets.c | 56 +++++++++ trunk/ceph/crush2/buckets.h | 49 ++++++++ trunk/ceph/crush2/crush.c | 236 ++++++++++++++++++++++++++++++++++++ trunk/ceph/crush2/crush.h | 49 ++++++++ trunk/ceph/crush2/hash.h | 80 ++++++++++++ trunk/ceph/crush2/types.h | 11 ++ 7 files changed, 507 insertions(+) create mode 100644 trunk/ceph/crush2/Makefile create mode 100644 trunk/ceph/crush2/buckets.c create mode 100644 trunk/ceph/crush2/buckets.h create mode 100644 trunk/ceph/crush2/crush.c create mode 100644 trunk/ceph/crush2/crush.h create mode 100644 trunk/ceph/crush2/hash.h create mode 100644 trunk/ceph/crush2/types.h diff --git a/trunk/ceph/crush2/Makefile b/trunk/ceph/crush2/Makefile new file mode 100644 index 0000000000000..7db40f789198e --- /dev/null +++ b/trunk/ceph/crush2/Makefile @@ -0,0 +1,26 @@ + +CC = gcc +CFLAGS = -Wall +CFLAGS += -O3 -g +LD = ld +RM = rm + +all: depend libcrush.o + +clean: + rm -f *.o libcrush.o + +%.o: %.c + ${CC} ${CFLAGS} -c $< -o $@ + +libcrush.o: crush.o buckets.o + $(LD) -i -o $@ $^ + +.depend: + touch .depend + +depend: + $(RM) .depend + makedepend -f- -- $(CFLAGS) -- *.c > .depend 2>/dev/null + +include .depend diff --git a/trunk/ceph/crush2/buckets.c b/trunk/ceph/crush2/buckets.c new file mode 100644 index 0000000000000..2a2e170bbbb6c --- /dev/null +++ b/trunk/ceph/crush2/buckets.c @@ -0,0 +1,56 @@ + +#include "hash.h" +#include "buckets.h" + +int +crush_bucket_uniform_choose(struct crush_bucket_uniform *bucket, int x, int r) +{ + unsigned o, p, s; + o = crush_hash32_2(x, bucket->h.id); + p = bucket->primes[crush_hash32_2(bucket->h.id, x) % bucket->h.size]; + s = (x + o + (r+1)*p) % bucket->h.size; + return bucket->h.items[s]; +} + +int +crush_bucket_list_choose(struct crush_bucket_list *bucket, int x, int r) +{ + int i; + __u64 w; + + for (i=0; ih.size; i++) { + w = crush_hash32_4(x, bucket->h.items[i], r, bucket->h.id) & 0xffff; + w = (w * bucket->sum_weights[i]) >> 32; + if (w < bucket->item_weights[i]) + return bucket->h.items[i]; + } + + BUG_ON(1); + return 0; +} + +int +crush_bucket_tree_choose(struct crush_bucket_tree *bucket, int x, int r) +{ + return 0; +} + +int +crush_bucket_straw_choose(struct crush_bucket_straw *bucket, int x, int r) +{ + int i; + int high = 0; + unsigned high_draw = 0; + __u64 draw; + + for (i=0; ih.size; i++) { + draw = (crush_hash32_3(x, bucket->h.items[i], r) & 0xffff) * bucket->straws[i]; + draw = draw >> 32; + if (i == 0 || draw > high_draw) { + high = i; + high_draw = draw; + } + } + + return high; +} diff --git a/trunk/ceph/crush2/buckets.h b/trunk/ceph/crush2/buckets.h new file mode 100644 index 0000000000000..c83d522159ffc --- /dev/null +++ b/trunk/ceph/crush2/buckets.h @@ -0,0 +1,49 @@ +#ifndef _CRUSH_BUCKETS_H +#define _CRUSH_BUCKETS_H + +#include "types.h" + +enum { + CRUSH_BUCKET_UNIFORM = 1, + CRUSH_BUCKET_LIST = 2, + CRUSH_BUCKET_TREE = 3, + CRUSH_BUCKET_STRAW = 4 +}; + +struct crush_bucket { + __u32 id; + __u32 type; + __u32 weight; /* 16-bit fixed point */ + __u32 size; /* num items */ + __s32 *items; +}; + +struct crush_bucket_uniform { + struct crush_bucket h; + __u32 item_weight; /* 16-bit fixed point */ + __u32 item_type; + __u32 *primes; +}; + +struct crush_bucket_list { + struct crush_bucket h; + __u32 *item_weights; /* 16-bit fixed point */ + __u32 *sum_weights; /* 16-bit fixed point */ +}; + +struct crush_bucket_tree { + struct crush_bucket h; + +}; + +struct crush_bucket_straw { + struct crush_bucket h; + __u32 *straws; /* 16-bit fixed point */ +}; + +extern int crush_bucket_uniform_choose(struct crush_bucket_uniform *bucket, int x, int r); +extern int crush_bucket_list_choose(struct crush_bucket_list *bucket, int x, int r); +extern int crush_bucket_tree_choose(struct crush_bucket_tree *bucket, int x, int r); +extern int crush_bucket_straw_choose(struct crush_bucket_straw *bucket, int x, int r); + +#endif diff --git a/trunk/ceph/crush2/crush.c b/trunk/ceph/crush2/crush.c new file mode 100644 index 0000000000000..3b420c43780d7 --- /dev/null +++ b/trunk/ceph/crush2/crush.c @@ -0,0 +1,236 @@ + +#include "crush.h" +#include "hash.h" + +/* + * choose numrep distinct items of given type + */ +static int crush_choose(struct crush_map *map, + struct crush_bucket *bucket, + int x, int numrep, int type, + int *out, int firstn, + int *outmap) +{ + int rep; + int ftotal, flocal; + int retry_rep, skip_rep; + struct crush_bucket *in = bucket; + int r; + int i; + int item; + int itemtype; + int outpos; + int collide, bad; + + outpos = 0; + + for (rep = 0; rep < numrep; rep++) { + /* keep trying until we get a non-out, non-colliding item */ + ftotal = 0; + skip_rep = 0; + + while (1) { + in = bucket; /* initial bucket */ + + /* choose through intervening buckets */ + flocal = 0; + retry_rep = 0; + + while (1) { + r = rep; + if (in->type == CRUSH_BUCKET_UNIFORM) { + /* be careful */ + if (firstn || numrep >= in->size) { + r += ftotal; /* r' = r + f_total */ + } else { + r += numrep * flocal; /* r' = r + n*f_local */ + /* make sure numrep is not a multiple of bucket size */ + if (in->size % numrep == 0) + /* shift seq once per pass through the bucket */ + r += numrep * flocal / in->size; + } + } else { + if (firstn) + r += ftotal; /* r' = r + f_total */ + else + r += numrep * flocal; /* r' = r + n*f_local */ + } + + /* bucket choose */ + switch (in->type) { + case CRUSH_BUCKET_UNIFORM: + item = crush_bucket_uniform_choose((struct crush_bucket_uniform*)in, x, r); + break; + case CRUSH_BUCKET_LIST: + item = crush_bucket_list_choose((struct crush_bucket_list*)in, x, r); + break; + case CRUSH_BUCKET_TREE: + item = crush_bucket_tree_choose((struct crush_bucket_tree*)in, x, r); + break; + case CRUSH_BUCKET_STRAW: + item = crush_bucket_straw_choose((struct crush_bucket_straw*)in, x, r); + break; + default: + BUG_ON(1); + } + + /* desired type? */ + if (in->type == CRUSH_BUCKET_UNIFORM) + itemtype = ((struct crush_bucket_uniform*)in)->item_type; + else if (item < 0) + itemtype = map->buckets[-item].type; + else + itemtype = 0; + + /* keep going? */ + if (itemtype != type) { + in = &map->buckets[-item]; + continue; + } + + /* collision? */ + collide = 0; + for (i=0; i out[item]) + bad = 1; + } + + if (bad || collide) { + ftotal++; + flocal++; + + if (collide && flocal < 3) + continue; /* locally a few times */ + if (ftotal >= 10) { + /* give up, ignore dup, fixme */ + skip_rep = 1; + break; + } + retry_rep = 1; + } + break; + } + + if (retry_rep) continue; + } + + if (skip_rep) continue; + + out[outpos] = item; + outpos++; + } + + return outpos; +} + + +int crush_do_rule(struct crush_map *map, + int ruleno, + int x, int *result, int result_max, + int *outmap, /* array of size max_devices, values 0...0xffff */ + int forcefeed) /* -1 for none */ +{ + int result_len; + int force_stack[CRUSH_MAX_DEPTH]; + int force_pos = -1; + int a[CRUSH_MAX_SET]; + int b[CRUSH_MAX_SET]; + int *w; + int wsize = 0; + int *o; + int osize; + int *tmp; + struct crush_rule *rule; + int step; + int i; + int numrep; + + rule = &map->rules[ruleno]; + result_len = 0; + w = a; + o = b; + + /* determine hierarchical context of forcefeed, if any */ + if (forcefeed >= 0) { + while (1) { + force_stack[++force_pos] = forcefeed; + if (forcefeed >= 0) + forcefeed = map->device_parent_map[forcefeed]; + else + forcefeed = map->bucket_parent_map[-forcefeed]; + if (forcefeed == 0) break; + } + } + + for (step = 0; step < rule->len; step++) { + switch (rule->steps[step].op) { + case CRUSH_RULE_TAKE: + if (force_pos >= 0) { + w[0] = force_stack[force_pos]; + force_pos--; + BUG_ON(w[0] != rule->steps[step].arg1); + } else { + w[0] = rule->steps[step].arg1; + } + wsize = 1; + break; + + case CRUSH_RULE_CHOOSE_FIRSTN: + case CRUSH_RULE_CHOOSE_INDEP: + BUG_ON(wsize == 0); + + /* reset output */ + osize = 0; + + for (i = 0; i < wsize; i++) { + numrep = rule->steps[step].arg1; + + if (force_pos >= 0) { + o[osize++] = force_stack[force_pos]; + force_pos--; + numrep--; + } + if (numrep) + crush_choose(map, + &map->buckets[-w[i]], + x, numrep, rule->steps[step].arg2, + o+osize, rule->steps[step].op == CRUSH_RULE_CHOOSE_FIRSTN, + outmap); + } + + /* swap t and w arrays */ + tmp = o; + o = w; + w = o; + wsize = osize; + break; + + + case CRUSH_RULE_EMIT: + for (i=0; i>13); \ + b=b-c; b=b-a; b=b^(a<<8); \ + c=c-a; c=c-b; c=c^(b>>13); \ + a=a-b; a=a-c; a=a^(c>>12); \ + b=b-c; b=b-a; b=b^(a<<16); \ + c=c-a; c=c-b; c=c^(b>>5); \ + a=a-b; a=a-c; a=a^(c>>3); \ + b=b-c; b=b-a; b=b^(a<<10); \ + c=c-a; c=c-b; c=c^(b>>15); + +#define crush_hash_seed 1315423911 + +static __inline__ unsigned crush_hash32(unsigned a) { + unsigned hash = crush_hash_seed ^ a; + unsigned b = a; + unsigned x = 231232; + unsigned y = 1232; + hashmix(b, x, hash); + hashmix(y, a, hash); + return (hash & 0xFFFFFFFF); +} + +static __inline__ unsigned crush_hash32_2(unsigned a, unsigned b) { + unsigned hash = crush_hash_seed ^ a ^ b; + unsigned x = 231232; + unsigned y = 1232; + hashmix(a, b, hash); + hashmix(x, a, hash); + hashmix(b, y, hash); + return (hash & 0xFFFFFFFF); +} + +static __inline__ unsigned crush_hash32_3(unsigned a, unsigned b, unsigned c) { + unsigned int hash = crush_hash_seed ^ a ^ b ^ c; + unsigned x = 231232; + unsigned y = 1232; + hashmix(a, b, hash); + hashmix(c, x, hash); + hashmix(y, a, hash); + hashmix(b, x, hash); + hashmix(y, c, hash); + return (hash & 0xFFFFFFFF); +} + +static __inline__ unsigned crush_hash32_4(unsigned a, unsigned b, unsigned c, unsigned d) { + unsigned int hash = crush_hash_seed ^a ^ b ^ c ^ d; + unsigned x = 231232; + unsigned y = 1232; + hashmix(a, b, hash); + hashmix(c, d, hash); + hashmix(a, x, hash); + hashmix(y, b, hash); + hashmix(c, x, hash); + hashmix(y, d, hash); + return (hash & 0xFFFFFFFF); +} + +static __inline__ unsigned crush_hash32_5(unsigned a, unsigned b, unsigned c, unsigned d, unsigned e) { + unsigned int hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e; + unsigned x = 231232; + unsigned y = 1232; + hashmix(a, b, hash); + hashmix(c, d, hash); + hashmix(e, x, hash); + hashmix(y, a, hash); + hashmix(b, x, hash); + hashmix(y, c, hash); + hashmix(d, x, hash); + hashmix(y, e, hash); + return (hash & 0xFFFFFFFF); +} + +#endif diff --git a/trunk/ceph/crush2/types.h b/trunk/ceph/crush2/types.h new file mode 100644 index 0000000000000..ea682401e146b --- /dev/null +++ b/trunk/ceph/crush2/types.h @@ -0,0 +1,11 @@ +#ifndef _CRUSH_TYPES_H +#define _CRUSH_TYPES_H + +#include /* just for int types */ + +#ifndef BUG_ON +# include +# define BUG_ON(x) assert(!(x)) +#endif + +#endif -- 2.39.5