From ca8471d65fb2cf7d2247d823c5436faa273efda5 Mon Sep 17 00:00:00 2001 From: Rongze Zhu Date: Tue, 11 Nov 2014 00:13:42 +0800 Subject: [PATCH] crush: fix tree bucket functions There are incorrect nodes' weight in tree bucket when construct tree bucket. The tree bucket don't store item id in items array, so the tree bucket will not work correctly. The patch fix above bugs and add a simple test for tree bucket. Signed-off-by: Rongze Zhu (cherry picked from commit 13425488882d360fa740613dfcfd0d098c1b7616) --- src/crush/builder.c | 26 +++++++- src/test/cli/crushtool/add-item-in-tree.t | 10 +++ src/test/cli/crushtool/tree.template | Bin 0 -> 376 bytes src/test/cli/crushtool/tree.template.final | 70 +++++++++++++++++++++ 4 files changed, 105 insertions(+), 1 deletion(-) create mode 100644 src/test/cli/crushtool/add-item-in-tree.t create mode 100644 src/test/cli/crushtool/tree.template create mode 100644 src/test/cli/crushtool/tree.template.final diff --git a/src/crush/builder.c b/src/crush/builder.c index ac765db1592d5..74145a2f5e168 100644 --- a/src/crush/builder.c +++ b/src/crush/builder.c @@ -308,6 +308,10 @@ static int parent(int n) static int calc_depth(int size) { + if (size == 0) { + return 0; + } + int depth = 1; int t = size - 1; while (t) { @@ -336,6 +340,16 @@ crush_make_tree_bucket(int hash, int type, int size, bucket->h.type = type; bucket->h.size = size; + if (size == 0) { + bucket->h.items = NULL; + bucket->h.perm = NULL; + bucket->h.weight = 0; + bucket->node_weights = NULL; + bucket->num_nodes = 0; + /* printf("size 0 depth 0 nodes 0\n"); */ + return bucket; + } + bucket->h.items = malloc(sizeof(__s32)*size); if (!bucket->h.items) goto err; @@ -652,10 +666,19 @@ int crush_add_tree_bucket_item(struct crush_bucket_tree *bucket, int item, int w node = crush_calc_tree_node(newsize-1); bucket->node_weights[node] = weight; + /* if the depth increase, we need to initialize the new root node's weight before add bucket item */ + int root = bucket->num_nodes/2; + if (depth >= 2 && (node - 1) == root) { + /* if the new item is the first node in right sub tree, so + * the root node initial weight is left sub tree's weight + */ + bucket->node_weights[root] = bucket->node_weights[root/2]; + } + for (j=1; jnode_weights[node], weight)) + if (crush_addition_is_unsafe(bucket->node_weights[node], weight)) return -ERANGE; bucket->node_weights[node] += weight; @@ -666,6 +689,7 @@ int crush_add_tree_bucket_item(struct crush_bucket_tree *bucket, int item, int w if (crush_addition_is_unsafe(bucket->h.weight, weight)) return -ERANGE; + bucket->h.items[newsize-1] = item; bucket->h.weight += weight; bucket->h.size++; diff --git a/src/test/cli/crushtool/add-item-in-tree.t b/src/test/cli/crushtool/add-item-in-tree.t new file mode 100644 index 0000000000000..879097725ed03 --- /dev/null +++ b/src/test/cli/crushtool/add-item-in-tree.t @@ -0,0 +1,10 @@ + $ crushtool -i "$TESTDIR/tree.template" --add-item 0 1.0 device0 --loc host host0 --loc cluster cluster0 -o one > /dev/null + $ crushtool -i one --add-item 1 1.0 device1 --loc host host0 --loc cluster cluster0 -o two > /dev/null + $ crushtool -i two --add-item 2 1.0 device2 --loc host host0 --loc cluster cluster0 -o tree > /dev/null + $ crushtool -i tree --add-item 3 1.0 device3 --loc host host0 --loc cluster cluster0 -o four > /dev/null + $ crushtool -i four --add-item 4 1.0 device4 --loc host host0 --loc cluster cluster0 -o five > /dev/null + $ crushtool -i five --add-item 5 1.0 device5 --loc host host0 --loc cluster cluster0 -o six > /dev/null + $ crushtool -i six --add-item 6 1.0 device6 --loc host host0 --loc cluster cluster0 -o seven > /dev/null + $ crushtool -i seven --add-item 7 1.0 device7 --loc host host0 --loc cluster cluster0 -o eight > /dev/null + $ crushtool -d eight -o final + $ cmp final "$TESTDIR/tree.template.final" diff --git a/src/test/cli/crushtool/tree.template b/src/test/cli/crushtool/tree.template new file mode 100644 index 0000000000000000000000000000000000000000..98085787146c543c5676d6b732769ad4d05df2f6 GIT binary patch literal 376 zcmb7=(GG$z3`N_4N_^!<_@&8~XreKJ!RMhP;L)aL# z{^31S0|E&BTygq);h({3_)%ZCoS)-(X#2zPR0YT=U;8}p}Mg_iY4O3{FY0k#{kWAN|gBY7LFG-+%pRR literal 0 HcmV?d00001 diff --git a/src/test/cli/crushtool/tree.template.final b/src/test/cli/crushtool/tree.template.final new file mode 100644 index 0000000000000..6af0701113dce --- /dev/null +++ b/src/test/cli/crushtool/tree.template.final @@ -0,0 +1,70 @@ +# begin crush map + +# devices +device 0 device0 +device 1 device1 +device 2 device2 +device 3 device3 +device 4 device4 +device 5 device5 +device 6 device6 +device 7 device7 + +# types +type 0 device +type 1 host +type 2 cluster + +# buckets +host host0 { + id -2 # do not change unnecessarily + # weight 8.000 + alg tree # do not change pos for existing items unnecessarily + hash 0 # rjenkins1 + item device0 weight 1.000 pos 0 + item device1 weight 1.000 pos 1 + item device2 weight 1.000 pos 2 + item device3 weight 1.000 pos 3 + item device4 weight 1.000 pos 4 + item device5 weight 1.000 pos 5 + item device6 weight 1.000 pos 6 + item device7 weight 1.000 pos 7 +} +cluster cluster0 { + id -1 # do not change unnecessarily + # weight 8.000 + alg tree # do not change pos for existing items unnecessarily + hash 0 # rjenkins1 + item host0 weight 8.000 pos 0 +} + +# rules +rule data { + ruleset 0 + type replicated + min_size 1 + max_size 10 + step take cluster0 + step chooseleaf firstn 0 type host + step emit +} +rule metadata { + ruleset 1 + type replicated + min_size 1 + max_size 10 + step take cluster0 + step chooseleaf firstn 0 type host + step emit +} +rule rbd { + ruleset 2 + type replicated + min_size 1 + max_size 10 + step take cluster0 + step chooseleaf firstn 0 type host + step emit +} + +# end crush map -- 2.39.5