From 0a9c9868e1e3bb47be29fb5367c14b92c4a51343 Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Wed, 17 Sep 2008 14:37:39 -0700 Subject: [PATCH] crush: chooseleaf --- src/crush/CrushWrapper.h | 6 ++++++ src/crush/crush.h | 6 ++++-- src/crush/grammar.h | 7 ++++--- src/crush/mapper.c | 24 +++++++++++++++++++++--- src/crushtool.cc | 20 ++++++++++++++------ 5 files changed, 49 insertions(+), 14 deletions(-) diff --git a/src/crush/CrushWrapper.h b/src/crush/CrushWrapper.h index 7c4d3e80c249a..ed82f67140fdf 100644 --- a/src/crush/CrushWrapper.h +++ b/src/crush/CrushWrapper.h @@ -241,6 +241,12 @@ public: int set_rule_step_choose_indep(unsigned ruleno, unsigned step, int val, int type) { return set_rule_step(ruleno, step, CRUSH_RULE_CHOOSE_INDEP, val, type); } + int set_rule_step_choose_leaf_firstn(unsigned ruleno, unsigned step, int val, int type) { + return set_rule_step(ruleno, step, CRUSH_RULE_CHOOSE_LEAF_FIRSTN, val, type); + } + int set_rule_step_choose_leaf_indep(unsigned ruleno, unsigned step, int val, int type) { + return set_rule_step(ruleno, step, CRUSH_RULE_CHOOSE_LEAF_INDEP, val, type); + } int set_rule_step_emit(unsigned ruleno, unsigned step) { return set_rule_step(ruleno, step, CRUSH_RULE_EMIT, 0, 0); } diff --git a/src/crush/crush.h b/src/crush/crush.h index 4259a9bec4b32..8fd5f61839b85 100644 --- a/src/crush/crush.h +++ b/src/crush/crush.h @@ -21,8 +21,10 @@ enum { CRUSH_RULE_TAKE = 1, /* arg1 = value to start with */ CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */ /* arg2 = type */ - CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ - CRUSH_RULE_EMIT = 4 /* no args */ + CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ + CRUSH_RULE_EMIT = 4, /* no args */ + CRUSH_RULE_CHOOSE_LEAF_FIRSTN = 6, + CRUSH_RULE_CHOOSE_LEAF_INDEP = 7, }; #define CRUSH_MAX_DEPTH 10 diff --git a/src/crush/grammar.h b/src/crush/grammar.h index a4c17d0752805..090d0c75c8b4d 100644 --- a/src/crush/grammar.h +++ b/src/crush/grammar.h @@ -101,9 +101,10 @@ struct crush_grammar : public grammar // rules step_take = str_p("take") >> str_p("root"); - step_choose = str_p("choose") >> ( str_p("indep") | str_p("firstn") ) - >> integer - >> str_p("type") >> name; + step_choose = (str_p("choose") | str_p("chooseleaf")) + >> ( str_p("indep") | str_p("firstn") ) + >> integer + >> str_p("type") >> name; step_emit = str_p("emit"); step = str_p("step") >> ( step_take | step_choose | diff --git a/src/crush/mapper.c b/src/crush/mapper.c index e3b0cbf1b01f8..b0a08549617b4 100644 --- a/src/crush/mapper.c +++ b/src/crush/mapper.c @@ -164,7 +164,9 @@ static int is_out(struct crush_map *map, int item, int x) static int crush_choose(struct crush_map *map, struct crush_bucket *bucket, int x, int numrep, int type, - int *out, int outpos, int firstn) + int *out, int outpos, + int firstn, int recurse_to_leaf, + int *out2) { int rep; int ftotal, flocal; @@ -251,6 +253,11 @@ static int crush_choose(struct crush_map *map, reject = is_out(map, item, x); else reject = 0; + if (recurse_to_leaf && + !crush_choose(map, bucket, x, 1, 0, + out2+outpos, 0, + firstn, 0, 0)) + reject = 1; if (reject || collide) { ftotal++; @@ -285,6 +292,8 @@ int crush_do_rule(struct crush_map *map, int force_pos = -1; int a[CRUSH_MAX_SET]; int b[CRUSH_MAX_SET]; + int c[CRUSH_MAX_SET]; + int recurse_to_leaf; int *w; int wsize = 0; int *o; @@ -335,11 +344,15 @@ int crush_do_rule(struct crush_map *map, case CRUSH_RULE_CHOOSE_FIRSTN: case CRUSH_RULE_CHOOSE_INDEP: + case CRUSH_RULE_CHOOSE_LEAF_FIRSTN: + case CRUSH_RULE_CHOOSE_LEAF_INDEP: BUG_ON(wsize == 0); /* reset output */ osize = 0; + recurse_to_leaf = rule->steps[step].op >= + CRUSH_RULE_CHOOSE_LEAF_FIRSTN; for (i = 0; i < wsize; i++) { /* * see CRUSH_N, CRUSH_N_MINUS macros. @@ -361,9 +374,14 @@ int crush_do_rule(struct crush_map *map, osize += crush_choose(map, map->buckets[-1-w[i]], x, numrep, rule->steps[step].arg2, - o+osize, j, rule->steps[step].op == CRUSH_RULE_CHOOSE_FIRSTN); + o+osize, j, rule->steps[step].op == CRUSH_RULE_CHOOSE_FIRSTN, + recurse_to_leaf, c+osize); } - + + if (recurse_to_leaf) + /* copy final _leaf_ values to output set */ + memcpy(o, c, osize*sizeof(*o)); + /* swap t and w arrays */ tmp = o; o = w; diff --git a/src/crushtool.cc b/src/crushtool.cc index e4e116f538981..fca974d3370cb 100644 --- a/src/crushtool.cc +++ b/src/crushtool.cc @@ -298,13 +298,21 @@ void parse_rule(iter_t const& i, CrushWrapper &crush) cerr << "in rule '" << rname << "' type '" << type << "' not defined" << std::endl; exit(1); } + string choose = string_node(s->children[0]); string mode = string_node(s->children[1]); - if (mode == "firstn") - crush.set_rule_step_choose_firstn(ruleno, step++, int_node(s->children[2]), type_id[type]); - else if (mode == "indep") - crush.set_rule_step_choose_indep(ruleno, step++, int_node(s->children[2]), type_id[type]); - else - assert(0); + if (choose == "choose") { + if (mode == "firstn") + crush.set_rule_step_choose_firstn(ruleno, step++, int_node(s->children[2]), type_id[type]); + else if (mode == "indep") + crush.set_rule_step_choose_indep(ruleno, step++, int_node(s->children[2]), type_id[type]); + else assert(0); + } else if (choose == "chooseleaf") { + if (mode == "firstn") + crush.set_rule_step_choose_leaf_firstn(ruleno, step++, int_node(s->children[2]), type_id[type]); + else if (mode == "indep") + crush.set_rule_step_choose_leaf_indep(ruleno, step++, int_node(s->children[2]), type_id[type]); + else assert(0); + } else assert(0); } break; -- 2.39.5