]>
Commit | Line | Data |
---|---|---|
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- | |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2013 Inktank <info@inktank.com> | |
7 | * | |
8 | * LGPL2.1 (see COPYING-LGPL2.1) or later | |
9 | */ | |
10 | ||
11 | #include <iostream> | |
12 | #include <memory> | |
13 | #include <gtest/gtest.h> | |
14 | ||
15 | #include "include/stringify.h" | |
16 | ||
17 | #include "crush/CrushWrapper.h" | |
18 | #include "osd/osd_types.h" | |
19 | ||
20 | #include <set> | |
21 | ||
22 | std::unique_ptr<CrushWrapper> build_indep_map(CephContext *cct, int num_rack, | |
23 | int num_host, int num_osd) | |
24 | { | |
25 | std::unique_ptr<CrushWrapper> c(new CrushWrapper); | |
26 | c->create(); | |
27 | ||
28 | c->set_type_name(5, "root"); | |
29 | c->set_type_name(4, "row"); | |
30 | c->set_type_name(3, "rack"); | |
31 | c->set_type_name(2, "chasis"); | |
32 | c->set_type_name(1, "host"); | |
33 | c->set_type_name(0, "osd"); | |
34 | ||
35 | int rootno; | |
36 | c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1, | |
37 | 5, 0, NULL, NULL, &rootno); | |
38 | c->set_item_name(rootno, "default"); | |
39 | ||
40 | map<string,string> loc; | |
41 | loc["root"] = "default"; | |
42 | ||
43 | int osd = 0; | |
44 | for (int r=0; r<num_rack; ++r) { | |
45 | loc["rack"] = string("rack-") + stringify(r); | |
46 | for (int h=0; h<num_host; ++h) { | |
47 | loc["host"] = string("host-") + stringify(r) + string("-") + stringify(h); | |
48 | for (int o=0; o<num_osd; ++o, ++osd) { | |
49 | c->insert_item(cct, osd, 1.0, string("osd.") + stringify(osd), loc); | |
50 | } | |
51 | } | |
52 | } | |
53 | int ret; | |
54 | int ruleno = 0; | |
55 | ret = c->add_rule(ruleno, 4, 123, 1, 20); | |
56 | assert(ret == ruleno); | |
57 | ret = c->set_rule_step(ruleno, 0, CRUSH_RULE_SET_CHOOSELEAF_TRIES, 10, 0); | |
58 | assert(ret == 0); | |
59 | ret = c->set_rule_step(ruleno, 1, CRUSH_RULE_TAKE, rootno, 0); | |
60 | assert(ret == 0); | |
61 | ret = c->set_rule_step(ruleno, 2, CRUSH_RULE_CHOOSELEAF_INDEP, CRUSH_CHOOSE_N, 1); | |
62 | assert(ret == 0); | |
63 | ret = c->set_rule_step(ruleno, 3, CRUSH_RULE_EMIT, 0, 0); | |
64 | assert(ret == 0); | |
65 | c->set_rule_name(ruleno, "data"); | |
66 | ||
67 | c->finalize(); | |
68 | ||
69 | if (false) { | |
70 | Formatter *f = Formatter::create("json-pretty"); | |
71 | f->open_object_section("crush_map"); | |
72 | c->dump(f); | |
73 | f->close_section(); | |
74 | f->flush(cout); | |
75 | delete f; | |
76 | } | |
77 | ||
78 | return c; | |
79 | } | |
80 | ||
81 | int get_num_dups(const vector<int>& v) | |
82 | { | |
83 | std::set<int> s; | |
84 | int dups = 0; | |
85 | for (unsigned i=0; i<v.size(); ++i) { | |
86 | if (s.count(v[i])) | |
87 | ++dups; | |
88 | else if (v[i] != CRUSH_ITEM_NONE) | |
89 | s.insert(v[i]); | |
90 | } | |
91 | return dups; | |
92 | } | |
93 | ||
94 | TEST(CRUSH, indep_toosmall) { | |
95 | std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 1, 3, 1)); | |
96 | vector<__u32> weight(c->get_max_devices(), 0x10000); | |
97 | c->dump_tree(&cout, NULL); | |
98 | ||
99 | for (int x = 0; x < 100; ++x) { | |
100 | vector<int> out; | |
101 | c->do_rule(0, x, out, 5, weight, 0); | |
102 | cout << x << " -> " << out << std::endl; | |
103 | int num_none = 0; | |
104 | for (unsigned i=0; i<out.size(); ++i) { | |
105 | if (out[i] == CRUSH_ITEM_NONE) | |
106 | num_none++; | |
107 | } | |
108 | ASSERT_EQ(2, num_none); | |
109 | ASSERT_EQ(0, get_num_dups(out)); | |
110 | } | |
111 | } | |
112 | ||
113 | TEST(CRUSH, indep_basic) { | |
114 | std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3)); | |
115 | vector<__u32> weight(c->get_max_devices(), 0x10000); | |
116 | c->dump_tree(&cout, NULL); | |
117 | ||
118 | for (int x = 0; x < 100; ++x) { | |
119 | vector<int> out; | |
120 | c->do_rule(0, x, out, 5, weight, 0); | |
121 | cout << x << " -> " << out << std::endl; | |
122 | int num_none = 0; | |
123 | for (unsigned i=0; i<out.size(); ++i) { | |
124 | if (out[i] == CRUSH_ITEM_NONE) | |
125 | num_none++; | |
126 | } | |
127 | ASSERT_EQ(0, num_none); | |
128 | ASSERT_EQ(0, get_num_dups(out)); | |
129 | } | |
130 | } | |
131 | ||
132 | TEST(CRUSH, indep_out_alt) { | |
133 | std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3)); | |
134 | vector<__u32> weight(c->get_max_devices(), 0x10000); | |
135 | ||
136 | // mark a bunch of osds out | |
137 | int num = 3*3*3; | |
138 | for (int i=0; i<num / 2; ++i) | |
139 | weight[i*2] = 0; | |
140 | c->dump_tree(&cout, NULL); | |
141 | ||
142 | // need more retries to get 9/9 hosts for x in 0..99 | |
143 | c->set_choose_total_tries(100); | |
144 | for (int x = 0; x < 100; ++x) { | |
145 | vector<int> out; | |
146 | c->do_rule(0, x, out, 9, weight, 0); | |
147 | cout << x << " -> " << out << std::endl; | |
148 | int num_none = 0; | |
149 | for (unsigned i=0; i<out.size(); ++i) { | |
150 | if (out[i] == CRUSH_ITEM_NONE) | |
151 | num_none++; | |
152 | } | |
153 | ASSERT_EQ(0, num_none); | |
154 | ASSERT_EQ(0, get_num_dups(out)); | |
155 | } | |
156 | } | |
157 | ||
158 | TEST(CRUSH, indep_out_contig) { | |
159 | std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3)); | |
160 | vector<__u32> weight(c->get_max_devices(), 0x10000); | |
161 | ||
162 | // mark a bunch of osds out | |
163 | int num = 3*3*3; | |
164 | for (int i=0; i<num / 3; ++i) | |
165 | weight[i] = 0; | |
166 | c->dump_tree(&cout, NULL); | |
167 | ||
168 | c->set_choose_total_tries(100); | |
169 | for (int x = 0; x < 100; ++x) { | |
170 | vector<int> out; | |
171 | c->do_rule(0, x, out, 7, weight, 0); | |
172 | cout << x << " -> " << out << std::endl; | |
173 | int num_none = 0; | |
174 | for (unsigned i=0; i<out.size(); ++i) { | |
175 | if (out[i] == CRUSH_ITEM_NONE) | |
176 | num_none++; | |
177 | } | |
178 | ASSERT_EQ(1, num_none); | |
179 | ASSERT_EQ(0, get_num_dups(out)); | |
180 | } | |
181 | } | |
182 | ||
183 | ||
184 | TEST(CRUSH, indep_out_progressive) { | |
185 | std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3)); | |
186 | c->set_choose_total_tries(100); | |
187 | vector<__u32> tweight(c->get_max_devices(), 0x10000); | |
188 | c->dump_tree(&cout, NULL); | |
189 | ||
190 | int tchanged = 0; | |
191 | for (int x = 1; x < 5; ++x) { | |
192 | vector<__u32> weight(c->get_max_devices(), 0x10000); | |
193 | ||
194 | std::map<int,unsigned> pos; | |
195 | vector<int> prev; | |
196 | for (unsigned i=0; i<weight.size(); ++i) { | |
197 | vector<int> out; | |
198 | c->do_rule(0, x, out, 7, weight, 0); | |
199 | cout << "(" << i << "/" << weight.size() << " out) " | |
200 | << x << " -> " << out << std::endl; | |
201 | int num_none = 0; | |
202 | for (unsigned k=0; k<out.size(); ++k) { | |
203 | if (out[k] == CRUSH_ITEM_NONE) | |
204 | num_none++; | |
205 | } | |
206 | ASSERT_EQ(0, get_num_dups(out)); | |
207 | ||
208 | // make sure nothing moved | |
209 | int moved = 0; | |
210 | int changed = 0; | |
211 | for (unsigned j=0; j<out.size(); ++j) { | |
212 | if (i && out[j] != prev[j]) { | |
213 | ++changed; | |
214 | ++tchanged; | |
215 | } | |
216 | if (out[j] == CRUSH_ITEM_NONE) { | |
217 | continue; | |
218 | } | |
219 | if (i && pos.count(out[j])) { | |
220 | // result shouldn't have moved position | |
221 | if (j != pos[out[j]]) { | |
222 | cout << " " << out[j] << " moved from " << pos[out[j]] << " to " << j << std::endl; | |
223 | ++moved; | |
224 | } | |
225 | //ASSERT_EQ(j, pos[out[j]]); | |
226 | } | |
227 | } | |
228 | if (moved || changed) | |
229 | cout << " " << moved << " moved, " << changed << " changed" << std::endl; | |
230 | ASSERT_LE(moved, 1); | |
231 | ASSERT_LE(changed, 3); | |
232 | ||
233 | // mark another osd out | |
234 | weight[i] = 0; | |
235 | prev = out; | |
236 | pos.clear(); | |
237 | for (unsigned j=0; j<out.size(); ++j) { | |
238 | if (out[j] != CRUSH_ITEM_NONE) | |
239 | pos[out[j]] = j; | |
240 | } | |
241 | } | |
242 | } | |
243 | cout << tchanged << " total changed" << std::endl; | |
244 | ||
245 | } | |
246 | ||
247 | TEST(CRUSH, straw_zero) { | |
248 | // zero weight items should have no effect on placement. | |
249 | ||
250 | std::unique_ptr<CrushWrapper> c(new CrushWrapper); | |
251 | const int ROOT_TYPE = 1; | |
252 | c->set_type_name(ROOT_TYPE, "root"); | |
253 | const int OSD_TYPE = 0; | |
254 | c->set_type_name(OSD_TYPE, "osd"); | |
255 | ||
256 | int n = 5; | |
257 | int items[n], weights[n]; | |
258 | for (int i=0; i <n; ++i) { | |
259 | items[i] = i; | |
260 | weights[i] = 0x10000 * (n-i-1); | |
261 | } | |
262 | ||
263 | c->set_max_devices(n); | |
264 | ||
265 | string root_name0("root0"); | |
266 | int root0; | |
267 | EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1, | |
268 | ROOT_TYPE, n, items, weights, &root0)); | |
269 | EXPECT_EQ(0, c->set_item_name(root0, root_name0)); | |
270 | ||
271 | string name0("rule0"); | |
272 | int rule0 = c->add_simple_rule(name0, root_name0, "osd", "", | |
273 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
274 | EXPECT_EQ(0, rule0); | |
275 | ||
276 | string root_name1("root1"); | |
277 | int root1; | |
278 | EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1, | |
279 | ROOT_TYPE, n-1, items, weights, &root1)); | |
280 | EXPECT_EQ(0, c->set_item_name(root1, root_name1)); | |
281 | ||
282 | string name1("rule1"); | |
283 | int rule1 = c->add_simple_rule(name1, root_name1, "osd", "", | |
284 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
285 | EXPECT_EQ(1, rule1); | |
286 | ||
287 | c->finalize(); | |
288 | ||
289 | vector<unsigned> reweight(n, 0x10000); | |
290 | for (int i=0; i<10000; ++i) { | |
291 | vector<int> out0, out1; | |
292 | c->do_rule(rule0, i, out0, 1, reweight, 0); | |
293 | ASSERT_EQ(1u, out0.size()); | |
294 | c->do_rule(rule1, i, out1, 1, reweight, 0); | |
295 | ASSERT_EQ(1u, out1.size()); | |
296 | ASSERT_EQ(out0[0], out1[0]); | |
297 | //cout << i << "\t" << out0 << "\t" << out1 << std::endl; | |
298 | } | |
299 | } | |
300 | ||
301 | TEST(CRUSH, straw_same) { | |
302 | // items with the same weight should map about the same as items | |
303 | // with very similar weights. | |
304 | // | |
305 | // give the 0 vector a paired stair pattern, with dup weights. note | |
306 | // that the original straw flaw does not appear when there are 2 of | |
307 | // the initial weight, but it does when there is just 1. | |
308 | // | |
309 | // give the 1 vector a similar stair pattern, but make the same | |
310 | // steps weights slightly different (no dups). this works. | |
311 | // | |
312 | // compare the result and verify that the resulting mapping is | |
313 | // almost identical. | |
314 | ||
315 | std::unique_ptr<CrushWrapper> c(new CrushWrapper); | |
316 | const int ROOT_TYPE = 1; | |
317 | c->set_type_name(ROOT_TYPE, "root"); | |
318 | const int OSD_TYPE = 0; | |
319 | c->set_type_name(OSD_TYPE, "osd"); | |
320 | ||
321 | int n = 10; | |
322 | int items[n], weights[n]; | |
323 | for (int i=0; i <n; ++i) { | |
324 | items[i] = i; | |
325 | weights[i] = 0x10000 * ((i+1)/2 + 1); | |
326 | } | |
327 | ||
328 | c->set_max_devices(n); | |
329 | ||
330 | string root_name0("root0"); | |
331 | int root0; | |
332 | EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1, | |
333 | ROOT_TYPE, n, items, weights, &root0)); | |
334 | EXPECT_EQ(0, c->set_item_name(root0, root_name0)); | |
335 | ||
336 | string name0("rule0"); | |
337 | int rule0 = c->add_simple_rule(name0, root_name0, "osd", "", | |
338 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
339 | EXPECT_EQ(0, rule0); | |
340 | ||
341 | for (int i=0; i <n; ++i) { | |
342 | items[i] = i; | |
343 | weights[i] = 0x10000 * ((i+1)/2 + 1) + (i%2)*100; | |
344 | } | |
345 | ||
346 | string root_name1("root1"); | |
347 | int root1; | |
348 | EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1, | |
349 | ROOT_TYPE, n, items, weights, &root1)); | |
350 | EXPECT_EQ(0, c->set_item_name(root1, root_name1)); | |
351 | ||
352 | string name1("rule1"); | |
353 | int rule1 = c->add_simple_rule(name1, root_name1, "osd", "", | |
354 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
355 | EXPECT_EQ(1, rule1); | |
356 | ||
357 | if (0) { | |
358 | crush_bucket_straw *sb0 = reinterpret_cast<crush_bucket_straw*>(c->get_crush_map()->buckets[-1-root0]); | |
359 | crush_bucket_straw *sb1 = reinterpret_cast<crush_bucket_straw*>(c->get_crush_map()->buckets[-1-root1]); | |
360 | ||
361 | for (int i=0; i<n; ++i) { | |
362 | cout << i | |
363 | << "\t" << sb0->item_weights[i] | |
364 | << "\t" << sb1->item_weights[i] | |
365 | << "\t" | |
366 | << "\t" << sb0->straws[i] | |
367 | << "\t" << sb1->straws[i] | |
368 | << std::endl; | |
369 | } | |
370 | } | |
371 | ||
372 | if (0) { | |
373 | JSONFormatter jf(true); | |
374 | jf.open_object_section("crush"); | |
375 | c->dump(&jf); | |
376 | jf.close_section(); | |
377 | jf.flush(cout); | |
378 | } | |
379 | ||
380 | c->finalize(); | |
381 | ||
382 | vector<int> sum0(n, 0), sum1(n, 0); | |
383 | vector<unsigned> reweight(n, 0x10000); | |
384 | int different = 0; | |
385 | int max = 100000; | |
386 | for (int i=0; i<max; ++i) { | |
387 | vector<int> out0, out1; | |
388 | c->do_rule(rule0, i, out0, 1, reweight, 0); | |
389 | ASSERT_EQ(1u, out0.size()); | |
390 | c->do_rule(rule1, i, out1, 1, reweight, 0); | |
391 | ASSERT_EQ(1u, out1.size()); | |
392 | sum0[out0[0]]++; | |
393 | sum1[out1[0]]++; | |
394 | if (out0[0] != out1[0]) | |
395 | different++; | |
396 | } | |
397 | for (int i=0; i<n; ++i) { | |
398 | cout << i | |
399 | << "\t" << ((double)weights[i] / (double)weights[0]) | |
400 | << "\t" << sum0[i] << "\t" << ((double)sum0[i]/(double)sum0[0]) | |
401 | << "\t" << sum1[i] << "\t" << ((double)sum1[i]/(double)sum1[0]) | |
402 | << std::endl; | |
403 | } | |
404 | double ratio = ((double)different / (double)max); | |
405 | cout << different << " of " << max << " = " | |
406 | << ratio | |
407 | << " different" << std::endl; | |
408 | ASSERT_LT(ratio, .001); | |
409 | } | |
410 | ||
411 | double calc_straw2_stddev(int *weights, int n, bool verbose) | |
412 | { | |
413 | std::unique_ptr<CrushWrapper> c(new CrushWrapper); | |
414 | const int ROOT_TYPE = 2; | |
415 | c->set_type_name(ROOT_TYPE, "root"); | |
416 | const int HOST_TYPE = 1; | |
417 | c->set_type_name(HOST_TYPE, "host"); | |
418 | const int OSD_TYPE = 0; | |
419 | c->set_type_name(OSD_TYPE, "osd"); | |
420 | ||
421 | int items[n]; | |
422 | for (int i=0; i <n; ++i) { | |
423 | items[i] = i; | |
424 | } | |
425 | ||
426 | c->set_max_devices(n); | |
427 | ||
428 | string root_name0("root0"); | |
429 | int root0; | |
430 | crush_bucket *b0 = crush_make_bucket(c->get_crush_map(), | |
431 | CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1, | |
432 | ROOT_TYPE, n, items, weights); | |
433 | crush_add_bucket(c->get_crush_map(), 0, b0, &root0); | |
434 | c->set_item_name(root0, root_name0); | |
435 | ||
436 | string name0("rule0"); | |
437 | int rule0 = c->add_simple_rule(name0, root_name0, "osd", "", | |
438 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
439 | ||
440 | int sum[n]; | |
441 | double totalweight = 0; | |
442 | vector<unsigned> reweight(n); | |
443 | for (int i=0; i<n; ++i) { | |
444 | sum[i] = 0; | |
445 | reweight[i] = 0x10000; | |
446 | totalweight += weights[i]; | |
447 | } | |
448 | totalweight /= (double)0x10000; | |
449 | double avgweight = totalweight / n; | |
450 | ||
451 | c->finalize(); | |
452 | ||
453 | int total = 1000000; | |
454 | for (int i=0; i<total; ++i) { | |
455 | vector<int> out; | |
456 | c->do_rule(rule0, i, out, 1, reweight, 0); | |
457 | sum[out[0]]++; | |
458 | } | |
459 | ||
460 | double expected = (double)total / (double)n; | |
461 | if (verbose) | |
462 | cout << "expect\t\t\t" << expected << std::endl; | |
463 | double stddev = 0; | |
464 | double exptotal = 0; | |
465 | if (verbose) | |
466 | cout << "osd\tweight\tcount\tadjusted\n"; | |
467 | std::streamsize p = cout.precision(); | |
468 | cout << std::setprecision(4); | |
469 | for (int i=0; i<n; ++i) { | |
470 | double w = (double)weights[i] / (double)0x10000; | |
471 | double adj = (double)sum[i] * avgweight / w; | |
472 | stddev += (adj - expected) * (adj - expected); | |
473 | exptotal += adj; | |
474 | if (verbose) | |
475 | cout << i | |
476 | << "\t" << w | |
477 | << "\t" << sum[i] | |
478 | << "\t" << (int)adj | |
479 | << std::endl; | |
480 | } | |
481 | cout << std::setprecision(p); | |
482 | { | |
483 | stddev = sqrt(stddev / (double)n); | |
484 | if (verbose) | |
485 | cout << "std dev " << stddev << std::endl; | |
486 | ||
487 | double p = 1.0 / (double)n; | |
488 | double estddev = sqrt(exptotal * p * (1.0 - p)); | |
489 | if (verbose) | |
490 | cout << " vs " << estddev << "\t(expected)" << std::endl; | |
491 | } | |
492 | return stddev; | |
493 | } | |
494 | ||
495 | TEST(CRUSH, straw2_stddev) | |
496 | { | |
497 | int n = 15; | |
498 | int weights[n]; | |
499 | cout << "maxskew\tstddev\n"; | |
500 | for (double step = 1.0; step < 2; step += .25) { | |
501 | int w = 0x10000; | |
502 | for (int i = 0; i < n; ++i) { | |
503 | weights[i] = w; | |
504 | w *= step; | |
505 | } | |
506 | double stddev = calc_straw2_stddev(weights, n, true); | |
507 | cout << ((double)weights[n-1]/(double)weights[0]) | |
508 | << "\t" << stddev << std::endl; | |
509 | } | |
510 | } | |
511 | ||
512 | TEST(CRUSH, straw2_reweight) { | |
513 | // when we adjust the weight of an item in a straw2 bucket, | |
514 | // we should *only* see movement from or to that item, never | |
515 | // between other items. | |
516 | int weights[] = { | |
517 | 0x10000, | |
518 | 0x10000, | |
519 | 0x20000, | |
520 | 0x20000, | |
521 | 0x30000, | |
522 | 0x50000, | |
523 | 0x8000, | |
524 | 0x20000, | |
525 | 0x10000, | |
526 | 0x10000, | |
527 | 0x20000, | |
528 | 0x10000, | |
529 | 0x10000, | |
530 | 0x20000, | |
531 | 0x300000, | |
532 | 0x10000, | |
533 | 0x20000 | |
534 | }; | |
535 | int n = 15; | |
536 | ||
537 | std::unique_ptr<CrushWrapper> c(new CrushWrapper); | |
538 | const int ROOT_TYPE = 2; | |
539 | c->set_type_name(ROOT_TYPE, "root"); | |
540 | const int HOST_TYPE = 1; | |
541 | c->set_type_name(HOST_TYPE, "host"); | |
542 | const int OSD_TYPE = 0; | |
543 | c->set_type_name(OSD_TYPE, "osd"); | |
544 | ||
545 | int items[n]; | |
546 | for (int i=0; i <n; ++i) { | |
547 | items[i] = i; | |
548 | //weights[i] = 0x10000; | |
549 | } | |
550 | ||
551 | c->set_max_devices(n); | |
552 | ||
553 | string root_name0("root0"); | |
554 | int root0; | |
555 | crush_bucket *b0 = crush_make_bucket(c->get_crush_map(), | |
556 | CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1, | |
557 | ROOT_TYPE, n, items, weights); | |
558 | EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b0, &root0)); | |
559 | EXPECT_EQ(0, c->set_item_name(root0, root_name0)); | |
560 | ||
561 | string name0("rule0"); | |
562 | int rule0 = c->add_simple_rule(name0, root_name0, "osd", "", | |
563 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
564 | EXPECT_EQ(0, rule0); | |
565 | ||
566 | int changed = 1; | |
567 | weights[changed] = weights[changed] / 10 * (rand() % 10); | |
568 | ||
569 | string root_name1("root1"); | |
570 | int root1; | |
571 | crush_bucket *b1 = crush_make_bucket(c->get_crush_map(), | |
572 | CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1, | |
573 | ROOT_TYPE, n, items, weights); | |
574 | EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b1, &root1)); | |
575 | EXPECT_EQ(0, c->set_item_name(root1, root_name1)); | |
576 | ||
577 | string name1("rule1"); | |
578 | int rule1 = c->add_simple_rule(name1, root_name1, "osd", "", | |
579 | "firstn", pg_pool_t::TYPE_REPLICATED); | |
580 | EXPECT_EQ(1, rule1); | |
581 | ||
582 | int sum[n]; | |
583 | double totalweight = 0; | |
584 | vector<unsigned> reweight(n); | |
585 | for (int i=0; i<n; ++i) { | |
586 | sum[i] = 0; | |
587 | reweight[i] = 0x10000; | |
588 | totalweight += weights[i]; | |
589 | } | |
590 | totalweight /= (double)0x10000; | |
591 | double avgweight = totalweight / n; | |
592 | ||
593 | c->finalize(); | |
594 | ||
595 | int total = 1000000; | |
596 | for (int i=0; i<total; ++i) { | |
597 | vector<int> out0, out1; | |
598 | c->do_rule(rule0, i, out0, 1, reweight, 0); | |
599 | ASSERT_EQ(1u, out0.size()); | |
600 | ||
601 | c->do_rule(rule1, i, out1, 1, reweight, 0); | |
602 | ASSERT_EQ(1u, out1.size()); | |
603 | ||
604 | sum[out1[0]]++; | |
605 | //sum[rand()%n]++; | |
606 | ||
607 | if (out1[0] == changed) { | |
608 | ASSERT_EQ(changed, out0[0]); | |
609 | } else if (out0[0] != changed) { | |
610 | ASSERT_EQ(out0[0], out1[0]); | |
611 | } | |
612 | } | |
613 | ||
614 | double expected = (double)total / (double)n; | |
615 | cout << "expect\t\t\t" << expected << std::endl; | |
616 | double stddev = 0; | |
617 | cout << "osd\tweight\tcount\tadjusted\n"; | |
618 | std::streamsize p = cout.precision(); | |
619 | cout << std::setprecision(4); | |
620 | for (int i=0; i<n; ++i) { | |
621 | double w = (double)weights[i] / (double)0x10000; | |
622 | double adj = (double)sum[i] * avgweight / w; | |
623 | stddev += (adj - expected) * (adj - expected); | |
624 | cout << i | |
625 | << "\t" << w | |
626 | << "\t" << sum[i] | |
627 | << "\t" << (int)adj | |
628 | << std::endl; | |
629 | } | |
630 | cout << std::setprecision(p); | |
631 | { | |
632 | stddev = sqrt(stddev / (double)n); | |
633 | cout << "std dev " << stddev << std::endl; | |
634 | ||
635 | double p = 1.0 / (double)n; | |
636 | double estddev = sqrt((double)total * p * (1.0 - p)); | |
637 | cout << " vs " << estddev << std::endl; | |
638 | } | |
639 | } |