1 /* 2 * Ceph - scalable distributed file system 3 * 4 * Copyright (C) 2015 Intel Corporation All Rights Reserved 5 * 6 * This is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Lesser General Public 8 * License version 2.1, as published by the Free Software 9 * Foundation. See file COPYING. 10 * 11 */ 12 13 #ifdef __KERNEL__ 14 # include <linux/string.h> 15 # include <linux/slab.h> 16 # include <linux/bug.h> 17 # include <linux/kernel.h> 18 # include <linux/crush/crush.h> 19 # include <linux/crush/hash.h> 20 # include <linux/crush/mapper.h> 21 #else 22 # include "crush_compat.h" 23 # include "crush.h" 24 # include "hash.h" 25 # include "mapper.h" 26 #endif 27 #include "crush_ln_table.h" 28 29 #define dprintk(args...) /* printf(args) */ 30 31 /* 32 * Implement the core CRUSH mapping algorithm. 33 */ 34 35 /** 36 * crush_find_rule - find a crush_rule id for a given ruleset, type, and size. 37 * @map: the crush_map 38 * @ruleset: the storage ruleset id (user defined) 39 * @type: storage ruleset type (user defined) 40 * @size: output set size 41 */ 42 int crush_find_rule(const struct crush_map *map, int ruleset, int type, int size) 43 { 44 __u32 i; 45 46 for (i = 0; i < map->max_rules; i++) { 47 if (map->rules[i] && 48 map->rules[i]->mask.ruleset == ruleset && 49 map->rules[i]->mask.type == type && 50 map->rules[i]->mask.min_size <= size && 51 map->rules[i]->mask.max_size >= size) 52 return i; 53 } 54 return -1; 55 } 56 57 /* 58 * bucket choose methods 59 * 60 * For each bucket algorithm, we have a "choose" method that, given a 61 * crush input @x and replica position (usually, position in output set) @r, 62 * will produce an item in the bucket. 63 */ 64 65 /* 66 * Choose based on a random permutation of the bucket. 67 * 68 * We used to use some prime number arithmetic to do this, but it 69 * wasn't very random, and had some other bad behaviors. Instead, we 70 * calculate an actual random permutation of the bucket members. 71 * Since this is expensive, we optimize for the r=0 case, which 72 * captures the vast majority of calls. 73 */ 74 static int bucket_perm_choose(const struct crush_bucket *bucket, 75 struct crush_work_bucket *work, 76 int x, int r) 77 { 78 unsigned int pr = r % bucket->size; 79 unsigned int i, s; 80 81 /* start a new permutation if @x has changed */ 82 if (work->perm_x != (__u32)x || work->perm_n == 0) { 83 dprintk("bucket %d new x=%d\n", bucket->id, x); 84 work->perm_x = x; 85 86 /* optimize common r=0 case */ 87 if (pr == 0) { 88 s = crush_hash32_3(bucket->hash, x, bucket->id, 0) % 89 bucket->size; 90 work->perm[0] = s; 91 work->perm_n = 0xffff; /* magic value, see below */ 92 goto out; 93 } 94 95 for (i = 0; i < bucket->size; i++) 96 work->perm[i] = i; 97 work->perm_n = 0; 98 } else if (work->perm_n == 0xffff) { 99 /* clean up after the r=0 case above */ 100 for (i = 1; i < bucket->size; i++) 101 work->perm[i] = i; 102 work->perm[work->perm[0]] = 0; 103 work->perm_n = 1; 104 } 105 106 /* calculate permutation up to pr */ 107 for (i = 0; i < work->perm_n; i++) 108 dprintk(" perm_choose have %d: %d\n", i, bucket->perm[i]); 109 while (work->perm_n <= pr) { 110 unsigned int p = work->perm_n; 111 /* no point in swapping the final entry */ 112 if (p < bucket->size - 1) { 113 i = crush_hash32_3(bucket->hash, x, bucket->id, p) % 114 (bucket->size - p); 115 if (i) { 116 unsigned int t = work->perm[p + i]; 117 work->perm[p + i] = work->perm[p]; 118 work->perm[p] = t; 119 } 120 dprintk(" perm_choose swap %d with %d\n", p, p+i); 121 } 122 work->perm_n++; 123 } 124 for (i = 0; i < bucket->size; i++) 125 dprintk(" perm_choose %d: %d\n", i, bucket->perm[i]); 126 127 s = work->perm[pr]; 128 out: 129 dprintk(" perm_choose %d sz=%d x=%d r=%d (%d) s=%d\n", bucket->id, 130 bucket->size, x, r, pr, s); 131 return bucket->items[s]; 132 } 133 134 /* uniform */ 135 static int bucket_uniform_choose(const struct crush_bucket_uniform *bucket, 136 struct crush_work_bucket *work, int x, int r) 137 { 138 return bucket_perm_choose(&bucket->h, work, x, r); 139 } 140 141 /* list */ 142 static int bucket_list_choose(const struct crush_bucket_list *bucket, 143 int x, int r) 144 { 145 int i; 146 147 for (i = bucket->h.size-1; i >= 0; i--) { 148 __u64 w = crush_hash32_4(bucket->h.hash, x, bucket->h.items[i], 149 r, bucket->h.id); 150 w &= 0xffff; 151 dprintk("list_choose i=%d x=%d r=%d item %d weight %x " 152 "sw %x rand %llx", 153 i, x, r, bucket->h.items[i], bucket->item_weights[i], 154 bucket->sum_weights[i], w); 155 w *= bucket->sum_weights[i]; 156 w = w >> 16; 157 /*dprintk(" scaled %llx\n", w);*/ 158 if (w < bucket->item_weights[i]) { 159 return bucket->h.items[i]; 160 } 161 } 162 163 dprintk("bad list sums for bucket %d\n", bucket->h.id); 164 return bucket->h.items[0]; 165 } 166 167 168 /* (binary) tree */ 169 static int height(int n) 170 { 171 int h = 0; 172 while ((n & 1) == 0) { 173 h++; 174 n = n >> 1; 175 } 176 return h; 177 } 178 179 static int left(int x) 180 { 181 int h = height(x); 182 return x - (1 << (h-1)); 183 } 184 185 static int right(int x) 186 { 187 int h = height(x); 188 return x + (1 << (h-1)); 189 } 190 191 static int terminal(int x) 192 { 193 return x & 1; 194 } 195 196 static int bucket_tree_choose(const struct crush_bucket_tree *bucket, 197 int x, int r) 198 { 199 int n; 200 __u32 w; 201 __u64 t; 202 203 /* start at root */ 204 n = bucket->num_nodes >> 1; 205 206 while (!terminal(n)) { 207 int l; 208 /* pick point in [0, w) */ 209 w = bucket->node_weights[n]; 210 t = (__u64)crush_hash32_4(bucket->h.hash, x, n, r, 211 bucket->h.id) * (__u64)w; 212 t = t >> 32; 213 214 /* descend to the left or right? */ 215 l = left(n); 216 if (t < bucket->node_weights[l]) 217 n = l; 218 else 219 n = right(n); 220 } 221 222 return bucket->h.items[n >> 1]; 223 } 224 225 226 /* straw */ 227 228 static int bucket_straw_choose(const struct crush_bucket_straw *bucket, 229 int x, int r) 230 { 231 __u32 i; 232 int high = 0; 233 __u64 high_draw = 0; 234 __u64 draw; 235 236 for (i = 0; i < bucket->h.size; i++) { 237 draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r); 238 draw &= 0xffff; 239 draw *= bucket->straws[i]; 240 if (i == 0 || draw > high_draw) { 241 high = i; 242 high_draw = draw; 243 } 244 } 245 return bucket->h.items[high]; 246 } 247 248 /* compute 2^44*log2(input+1) */ 249 static __u64 crush_ln(unsigned int xin) 250 { 251 unsigned int x = xin; 252 int iexpon, index1, index2; 253 __u64 RH, LH, LL, xl64, result; 254 255 x++; 256 257 /* normalize input */ 258 iexpon = 15; 259 260 /* 261 * figure out number of bits we need to shift and 262 * do it in one step instead of iteratively 263 */ 264 if (!(x & 0x18000)) { 265 int bits = __builtin_clz(x & 0x1FFFF) - 16; 266 x <<= bits; 267 iexpon = 15 - bits; 268 } 269 270 index1 = (x >> 8) << 1; 271 /* RH ~ 2^56/index1 */ 272 RH = __RH_LH_tbl[index1 - 256]; 273 /* LH ~ 2^48 * log2(index1/256) */ 274 LH = __RH_LH_tbl[index1 + 1 - 256]; 275 276 /* RH*x ~ 2^48 * (2^15 + xf), xf<2^8 */ 277 xl64 = (__s64)x * RH; 278 xl64 >>= 48; 279 280 result = iexpon; 281 result <<= (12 + 32); 282 283 index2 = xl64 & 0xff; 284 /* LL ~ 2^48*log2(1.0+index2/2^15) */ 285 LL = __LL_tbl[index2]; 286 287 LH = LH + LL; 288 289 LH >>= (48 - 12 - 32); 290 result += LH; 291 292 return result; 293 } 294 295 296 /* 297 * straw2 298 * 299 * for reference, see: 300 * 301 * http://en.wikipedia.org/wiki/Exponential_distribution#Distribution_of_the_minimum_of_exponential_random_variables 302 * 303 */ 304 305 static int bucket_straw2_choose(const struct crush_bucket_straw2 *bucket, 306 int x, int r) 307 { 308 unsigned int i, high = 0; 309 unsigned int u; 310 unsigned int w; 311 __s64 ln, draw, high_draw = 0; 312 313 for (i = 0; i < bucket->h.size; i++) { 314 w = bucket->item_weights[i]; 315 if (w) { 316 u = crush_hash32_3(bucket->h.hash, x, 317 bucket->h.items[i], r); 318 u &= 0xffff; 319 320 /* 321 * for some reason slightly less than 0x10000 produces 322 * a slightly more accurate distribution... probably a 323 * rounding effect. 324 * 325 * the natural log lookup table maps [0,0xffff] 326 * (corresponding to real numbers [1/0x10000, 1] to 327 * [0, 0xffffffffffff] (corresponding to real numbers 328 * [-11.090355,0]). 329 */ 330 ln = crush_ln(u) - 0x1000000000000ll; 331 332 /* 333 * divide by 16.16 fixed-point weight. note 334 * that the ln value is negative, so a larger 335 * weight means a larger (less negative) value 336 * for draw. 337 */ 338 draw = div64_s64(ln, w); 339 } else { 340 draw = S64_MIN; 341 } 342 343 if (i == 0 || draw > high_draw) { 344 high = i; 345 high_draw = draw; 346 } 347 } 348 349 return bucket->h.items[high]; 350 } 351 352 353 static int crush_bucket_choose(const struct crush_bucket *in, 354 struct crush_work_bucket *work, 355 int x, int r) 356 { 357 dprintk(" crush_bucket_choose %d x=%d r=%d\n", in->id, x, r); 358 BUG_ON(in->size == 0); 359 switch (in->alg) { 360 case CRUSH_BUCKET_UNIFORM: 361 return bucket_uniform_choose( 362 (const struct crush_bucket_uniform *)in, 363 work, x, r); 364 case CRUSH_BUCKET_LIST: 365 return bucket_list_choose((const struct crush_bucket_list *)in, 366 x, r); 367 case CRUSH_BUCKET_TREE: 368 return bucket_tree_choose((const struct crush_bucket_tree *)in, 369 x, r); 370 case CRUSH_BUCKET_STRAW: 371 return bucket_straw_choose( 372 (const struct crush_bucket_straw *)in, 373 x, r); 374 case CRUSH_BUCKET_STRAW2: 375 return bucket_straw2_choose( 376 (const struct crush_bucket_straw2 *)in, 377 x, r); 378 default: 379 dprintk("unknown bucket %d alg %d\n", in->id, in->alg); 380 return in->items[0]; 381 } 382 } 383 384 /* 385 * true if device is marked "out" (failed, fully offloaded) 386 * of the cluster 387 */ 388 static int is_out(const struct crush_map *map, 389 const __u32 *weight, int weight_max, 390 int item, int x) 391 { 392 if (item >= weight_max) 393 return 1; 394 if (weight[item] >= 0x10000) 395 return 0; 396 if (weight[item] == 0) 397 return 1; 398 if ((crush_hash32_2(CRUSH_HASH_RJENKINS1, x, item) & 0xffff) 399 < weight[item]) 400 return 0; 401 return 1; 402 } 403 404 /** 405 * crush_choose_firstn - choose numrep distinct items of given type 406 * @map: the crush_map 407 * @bucket: the bucket we are choose an item from 408 * @x: crush input value 409 * @numrep: the number of items to choose 410 * @type: the type of item to choose 411 * @out: pointer to output vector 412 * @outpos: our position in that vector 413 * @out_size: size of the out vector 414 * @tries: number of attempts to make 415 * @recurse_tries: number of attempts to have recursive chooseleaf make 416 * @local_retries: localized retries 417 * @local_fallback_retries: localized fallback retries 418 * @recurse_to_leaf: true if we want one device under each item of given type (chooseleaf instead of choose) 419 * @stable: stable mode starts rep=0 in the recursive call for all replicas 420 * @vary_r: pass r to recursive calls 421 * @out2: second output vector for leaf items (if @recurse_to_leaf) 422 * @parent_r: r value passed from the parent 423 */ 424 static int crush_choose_firstn(const struct crush_map *map, 425 struct crush_work *work, 426 const struct crush_bucket *bucket, 427 const __u32 *weight, int weight_max, 428 int x, int numrep, int type, 429 int *out, int outpos, 430 int out_size, 431 unsigned int tries, 432 unsigned int recurse_tries, 433 unsigned int local_retries, 434 unsigned int local_fallback_retries, 435 int recurse_to_leaf, 436 unsigned int vary_r, 437 unsigned int stable, 438 int *out2, 439 int parent_r) 440 { 441 int rep; 442 unsigned int ftotal, flocal; 443 int retry_descent, retry_bucket, skip_rep; 444 const struct crush_bucket *in = bucket; 445 int r; 446 int i; 447 int item = 0; 448 int itemtype; 449 int collide, reject; 450 int count = out_size; 451 452 dprintk("CHOOSE%s bucket %d x %d outpos %d numrep %d tries %d recurse_tries %d local_retries %d local_fallback_retries %d parent_r %d stable %d\n", 453 recurse_to_leaf ? "_LEAF" : "", 454 bucket->id, x, outpos, numrep, 455 tries, recurse_tries, local_retries, local_fallback_retries, 456 parent_r, stable); 457 458 for (rep = stable ? 0 : outpos; rep < numrep && count > 0 ; rep++) { 459 /* keep trying until we get a non-out, non-colliding item */ 460 ftotal = 0; 461 skip_rep = 0; 462 do { 463 retry_descent = 0; 464 in = bucket; /* initial bucket */ 465 466 /* choose through intervening buckets */ 467 flocal = 0; 468 do { 469 collide = 0; 470 retry_bucket = 0; 471 r = rep + parent_r; 472 /* r' = r + f_total */ 473 r += ftotal; 474 475 /* bucket choose */ 476 if (in->size == 0) { 477 reject = 1; 478 goto reject; 479 } 480 if (local_fallback_retries > 0 && 481 flocal >= (in->size>>1) && 482 flocal > local_fallback_retries) 483 item = bucket_perm_choose( 484 in, work->work[-1-in->id], 485 x, r); 486 else 487 item = crush_bucket_choose( 488 in, work->work[-1-in->id], 489 x, r); 490 if (item >= map->max_devices) { 491 dprintk(" bad item %d\n", item); 492 skip_rep = 1; 493 break; 494 } 495 496 /* desired type? */ 497 if (item < 0) 498 itemtype = map->buckets[-1-item]->type; 499 else 500 itemtype = 0; 501 dprintk(" item %d type %d\n", item, itemtype); 502 503 /* keep going? */ 504 if (itemtype != type) { 505 if (item >= 0 || 506 (-1-item) >= map->max_buckets) { 507 dprintk(" bad item type %d\n", type); 508 skip_rep = 1; 509 break; 510 } 511 in = map->buckets[-1-item]; 512 retry_bucket = 1; 513 continue; 514 } 515 516 /* collision? */ 517 for (i = 0; i < outpos; i++) { 518 if (out[i] == item) { 519 collide = 1; 520 break; 521 } 522 } 523 524 reject = 0; 525 if (!collide && recurse_to_leaf) { 526 if (item < 0) { 527 int sub_r; 528 if (vary_r) 529 sub_r = r >> (vary_r-1); 530 else 531 sub_r = 0; 532 if (crush_choose_firstn( 533 map, 534 work, 535 map->buckets[-1-item], 536 weight, weight_max, 537 x, stable ? 1 : outpos+1, 0, 538 out2, outpos, count, 539 recurse_tries, 0, 540 local_retries, 541 local_fallback_retries, 542 0, 543 vary_r, 544 stable, 545 NULL, 546 sub_r) <= outpos) 547 /* didn't get leaf */ 548 reject = 1; 549 } else { 550 /* we already have a leaf! */ 551 out2[outpos] = item; 552 } 553 } 554 555 if (!reject) { 556 /* out? */ 557 if (itemtype == 0) 558 reject = is_out(map, weight, 559 weight_max, 560 item, x); 561 else 562 reject = 0; 563 } 564 565 reject: 566 if (reject || collide) { 567 ftotal++; 568 flocal++; 569 570 if (collide && flocal <= local_retries) 571 /* retry locally a few times */ 572 retry_bucket = 1; 573 else if (local_fallback_retries > 0 && 574 flocal <= in->size + local_fallback_retries) 575 /* exhaustive bucket search */ 576 retry_bucket = 1; 577 else if (ftotal < tries) 578 /* then retry descent */ 579 retry_descent = 1; 580 else 581 /* else give up */ 582 skip_rep = 1; 583 dprintk(" reject %d collide %d " 584 "ftotal %u flocal %u\n", 585 reject, collide, ftotal, 586 flocal); 587 } 588 } while (retry_bucket); 589 } while (retry_descent); 590 591 if (skip_rep) { 592 dprintk("skip rep\n"); 593 continue; 594 } 595 596 dprintk("CHOOSE got %d\n", item); 597 out[outpos] = item; 598 outpos++; 599 count--; 600 #ifndef __KERNEL__ 601 if (map->choose_tries && ftotal <= map->choose_total_tries) 602 map->choose_tries[ftotal]++; 603 #endif 604 } 605 606 dprintk("CHOOSE returns %d\n", outpos); 607 return outpos; 608 } 609 610 611 /** 612 * crush_choose_indep: alternative breadth-first positionally stable mapping 613 * 614 */ 615 static void crush_choose_indep(const struct crush_map *map, 616 struct crush_work *work, 617 const struct crush_bucket *bucket, 618 const __u32 *weight, int weight_max, 619 int x, int left, int numrep, int type, 620 int *out, int outpos, 621 unsigned int tries, 622 unsigned int recurse_tries, 623 int recurse_to_leaf, 624 int *out2, 625 int parent_r) 626 { 627 const struct crush_bucket *in = bucket; 628 int endpos = outpos + left; 629 int rep; 630 unsigned int ftotal; 631 int r; 632 int i; 633 int item = 0; 634 int itemtype; 635 int collide; 636 637 dprintk("CHOOSE%s INDEP bucket %d x %d outpos %d numrep %d\n", recurse_to_leaf ? "_LEAF" : "", 638 bucket->id, x, outpos, numrep); 639 640 /* initially my result is undefined */ 641 for (rep = outpos; rep < endpos; rep++) { 642 out[rep] = CRUSH_ITEM_UNDEF; 643 if (out2) 644 out2[rep] = CRUSH_ITEM_UNDEF; 645 } 646 647 for (ftotal = 0; left > 0 && ftotal < tries; ftotal++) { 648 #ifdef DEBUG_INDEP 649 if (out2 && ftotal) { 650 dprintk("%u %d a: ", ftotal, left); 651 for (rep = outpos; rep < endpos; rep++) { 652 dprintk(" %d", out[rep]); 653 } 654 dprintk("\n"); 655 dprintk("%u %d b: ", ftotal, left); 656 for (rep = outpos; rep < endpos; rep++) { 657 dprintk(" %d", out2[rep]); 658 } 659 dprintk("\n"); 660 } 661 #endif 662 for (rep = outpos; rep < endpos; rep++) { 663 if (out[rep] != CRUSH_ITEM_UNDEF) 664 continue; 665 666 in = bucket; /* initial bucket */ 667 668 /* choose through intervening buckets */ 669 for (;;) { 670 /* note: we base the choice on the position 671 * even in the nested call. that means that 672 * if the first layer chooses the same bucket 673 * in a different position, we will tend to 674 * choose a different item in that bucket. 675 * this will involve more devices in data 676 * movement and tend to distribute the load. 677 */ 678 r = rep + parent_r; 679 680 /* be careful */ 681 if (in->alg == CRUSH_BUCKET_UNIFORM && 682 in->size % numrep == 0) 683 /* r'=r+(n+1)*f_total */ 684 r += (numrep+1) * ftotal; 685 else 686 /* r' = r + n*f_total */ 687 r += numrep * ftotal; 688 689 /* bucket choose */ 690 if (in->size == 0) { 691 dprintk(" empty bucket\n"); 692 break; 693 } 694 695 item = crush_bucket_choose( 696 in, work->work[-1-in->id], 697 x, r); 698 if (item >= map->max_devices) { 699 dprintk(" bad item %d\n", item); 700 out[rep] = CRUSH_ITEM_NONE; 701 if (out2) 702 out2[rep] = CRUSH_ITEM_NONE; 703 left--; 704 break; 705 } 706 707 /* desired type? */ 708 if (item < 0) 709 itemtype = map->buckets[-1-item]->type; 710 else 711 itemtype = 0; 712 dprintk(" item %d type %d\n", item, itemtype); 713 714 /* keep going? */ 715 if (itemtype != type) { 716 if (item >= 0 || 717 (-1-item) >= map->max_buckets) { 718 dprintk(" bad item type %d\n", type); 719 out[rep] = CRUSH_ITEM_NONE; 720 if (out2) 721 out2[rep] = 722 CRUSH_ITEM_NONE; 723 left--; 724 break; 725 } 726 in = map->buckets[-1-item]; 727 continue; 728 } 729 730 /* collision? */ 731 collide = 0; 732 for (i = outpos; i < endpos; i++) { 733 if (out[i] == item) { 734 collide = 1; 735 break; 736 } 737 } 738 if (collide) 739 break; 740 741 if (recurse_to_leaf) { 742 if (item < 0) { 743 crush_choose_indep( 744 map, 745 work, 746 map->buckets[-1-item], 747 weight, weight_max, 748 x, 1, numrep, 0, 749 out2, rep, 750 recurse_tries, 0, 751 0, NULL, r); 752 if (out2[rep] == CRUSH_ITEM_NONE) { 753 /* placed nothing; no leaf */ 754 break; 755 } 756 } else { 757 /* we already have a leaf! */ 758 out2[rep] = item; 759 } 760 } 761 762 /* out? */ 763 if (itemtype == 0 && 764 is_out(map, weight, weight_max, item, x)) 765 break; 766 767 /* yay! */ 768 out[rep] = item; 769 left--; 770 break; 771 } 772 } 773 } 774 for (rep = outpos; rep < endpos; rep++) { 775 if (out[rep] == CRUSH_ITEM_UNDEF) { 776 out[rep] = CRUSH_ITEM_NONE; 777 } 778 if (out2 && out2[rep] == CRUSH_ITEM_UNDEF) { 779 out2[rep] = CRUSH_ITEM_NONE; 780 } 781 } 782 #ifndef __KERNEL__ 783 if (map->choose_tries && ftotal <= map->choose_total_tries) 784 map->choose_tries[ftotal]++; 785 #endif 786 #ifdef DEBUG_INDEP 787 if (out2) { 788 dprintk("%u %d a: ", ftotal, left); 789 for (rep = outpos; rep < endpos; rep++) { 790 dprintk(" %d", out[rep]); 791 } 792 dprintk("\n"); 793 dprintk("%u %d b: ", ftotal, left); 794 for (rep = outpos; rep < endpos; rep++) { 795 dprintk(" %d", out2[rep]); 796 } 797 dprintk("\n"); 798 } 799 #endif 800 } 801 802 803 /* 804 * This takes a chunk of memory and sets it up to be a shiny new 805 * working area for a CRUSH placement computation. It must be called 806 * on any newly allocated memory before passing it in to 807 * crush_do_rule. It may be used repeatedly after that, so long as the 808 * map has not changed. If the map /has/ changed, you must make sure 809 * the working size is no smaller than what was allocated and re-run 810 * crush_init_workspace. 811 * 812 * If you do retain the working space between calls to crush, make it 813 * thread-local. 814 */ 815 void crush_init_workspace(const struct crush_map *map, void *v) 816 { 817 struct crush_work *w = v; 818 __s32 b; 819 820 /* 821 * We work by moving through the available space and setting 822 * values and pointers as we go. 823 * 824 * It's a bit like Forth's use of the 'allot' word since we 825 * set the pointer first and then reserve the space for it to 826 * point to by incrementing the point. 827 */ 828 v += sizeof(struct crush_work *); 829 w->work = v; 830 v += map->max_buckets * sizeof(struct crush_work_bucket *); 831 for (b = 0; b < map->max_buckets; ++b) { 832 if (!map->buckets[b]) 833 continue; 834 835 w->work[b] = v; 836 switch (map->buckets[b]->alg) { 837 default: 838 v += sizeof(struct crush_work_bucket); 839 break; 840 } 841 w->work[b]->perm_x = 0; 842 w->work[b]->perm_n = 0; 843 w->work[b]->perm = v; 844 v += map->buckets[b]->size * sizeof(__u32); 845 } 846 BUG_ON(v - (void *)w != map->working_size); 847 } 848 849 /** 850 * crush_do_rule - calculate a mapping with the given input and rule 851 * @map: the crush_map 852 * @ruleno: the rule id 853 * @x: hash input 854 * @result: pointer to result vector 855 * @result_max: maximum result size 856 * @weight: weight vector (for map leaves) 857 * @weight_max: size of weight vector 858 * @cwin: pointer to at least map->working_size bytes of memory 859 * @scratch: scratch vector for private use; must be >= 3 * result_max 860 */ 861 int crush_do_rule(const struct crush_map *map, 862 int ruleno, int x, int *result, int result_max, 863 const __u32 *weight, int weight_max, 864 void *cwin, int *scratch) 865 { 866 int result_len; 867 struct crush_work *cw = cwin; 868 int *a = scratch; 869 int *b = scratch + result_max; 870 int *c = scratch + result_max*2; 871 int recurse_to_leaf; 872 int *w; 873 int wsize = 0; 874 int *o; 875 int osize; 876 int *tmp; 877 const struct crush_rule *rule; 878 __u32 step; 879 int i, j; 880 int numrep; 881 int out_size; 882 /* 883 * the original choose_total_tries value was off by one (it 884 * counted "retries" and not "tries"). add one. 885 */ 886 int choose_tries = map->choose_total_tries + 1; 887 int choose_leaf_tries = 0; 888 /* 889 * the local tries values were counted as "retries", though, 890 * and need no adjustment 891 */ 892 int choose_local_retries = map->choose_local_tries; 893 int choose_local_fallback_retries = map->choose_local_fallback_tries; 894 895 int vary_r = map->chooseleaf_vary_r; 896 int stable = map->chooseleaf_stable; 897 898 if ((__u32)ruleno >= map->max_rules) { 899 dprintk(" bad ruleno %d\n", ruleno); 900 return 0; 901 } 902 903 rule = map->rules[ruleno]; 904 result_len = 0; 905 w = a; 906 o = b; 907 908 for (step = 0; step < rule->len; step++) { 909 int firstn = 0; 910 const struct crush_rule_step *curstep = &rule->steps[step]; 911 912 switch (curstep->op) { 913 case CRUSH_RULE_TAKE: 914 if ((curstep->arg1 >= 0 && 915 curstep->arg1 < map->max_devices) || 916 (-1-curstep->arg1 >= 0 && 917 -1-curstep->arg1 < map->max_buckets && 918 map->buckets[-1-curstep->arg1])) { 919 w[0] = curstep->arg1; 920 wsize = 1; 921 } else { 922 dprintk(" bad take value %d\n", curstep->arg1); 923 } 924 break; 925 926 case CRUSH_RULE_SET_CHOOSE_TRIES: 927 if (curstep->arg1 > 0) 928 choose_tries = curstep->arg1; 929 break; 930 931 case CRUSH_RULE_SET_CHOOSELEAF_TRIES: 932 if (curstep->arg1 > 0) 933 choose_leaf_tries = curstep->arg1; 934 break; 935 936 case CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES: 937 if (curstep->arg1 >= 0) 938 choose_local_retries = curstep->arg1; 939 break; 940 941 case CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES: 942 if (curstep->arg1 >= 0) 943 choose_local_fallback_retries = curstep->arg1; 944 break; 945 946 case CRUSH_RULE_SET_CHOOSELEAF_VARY_R: 947 if (curstep->arg1 >= 0) 948 vary_r = curstep->arg1; 949 break; 950 951 case CRUSH_RULE_SET_CHOOSELEAF_STABLE: 952 if (curstep->arg1 >= 0) 953 stable = curstep->arg1; 954 break; 955 956 case CRUSH_RULE_CHOOSELEAF_FIRSTN: 957 case CRUSH_RULE_CHOOSE_FIRSTN: 958 firstn = 1; 959 /* fall through */ 960 case CRUSH_RULE_CHOOSELEAF_INDEP: 961 case CRUSH_RULE_CHOOSE_INDEP: 962 if (wsize == 0) 963 break; 964 965 recurse_to_leaf = 966 curstep->op == 967 CRUSH_RULE_CHOOSELEAF_FIRSTN || 968 curstep->op == 969 CRUSH_RULE_CHOOSELEAF_INDEP; 970 971 /* reset output */ 972 osize = 0; 973 974 for (i = 0; i < wsize; i++) { 975 int bno; 976 /* 977 * see CRUSH_N, CRUSH_N_MINUS macros. 978 * basically, numrep <= 0 means relative to 979 * the provided result_max 980 */ 981 numrep = curstep->arg1; 982 if (numrep <= 0) { 983 numrep += result_max; 984 if (numrep <= 0) 985 continue; 986 } 987 j = 0; 988 /* make sure bucket id is valid */ 989 bno = -1 - w[i]; 990 if (bno < 0 || bno >= map->max_buckets) { 991 /* w[i] is probably CRUSH_ITEM_NONE */ 992 dprintk(" bad w[i] %d\n", w[i]); 993 continue; 994 } 995 if (firstn) { 996 int recurse_tries; 997 if (choose_leaf_tries) 998 recurse_tries = 999 choose_leaf_tries; 1000 else if (map->chooseleaf_descend_once) 1001 recurse_tries = 1; 1002 else 1003 recurse_tries = choose_tries; 1004 osize += crush_choose_firstn( 1005 map, 1006 cw, 1007 map->buckets[bno], 1008 weight, weight_max, 1009 x, numrep, 1010 curstep->arg2, 1011 o+osize, j, 1012 result_max-osize, 1013 choose_tries, 1014 recurse_tries, 1015 choose_local_retries, 1016 choose_local_fallback_retries, 1017 recurse_to_leaf, 1018 vary_r, 1019 stable, 1020 c+osize, 1021 0); 1022 } else { 1023 out_size = ((numrep < (result_max-osize)) ? 1024 numrep : (result_max-osize)); 1025 crush_choose_indep( 1026 map, 1027 cw, 1028 map->buckets[bno], 1029 weight, weight_max, 1030 x, out_size, numrep, 1031 curstep->arg2, 1032 o+osize, j, 1033 choose_tries, 1034 choose_leaf_tries ? 1035 choose_leaf_tries : 1, 1036 recurse_to_leaf, 1037 c+osize, 1038 0); 1039 osize += out_size; 1040 } 1041 } 1042 1043 if (recurse_to_leaf) 1044 /* copy final _leaf_ values to output set */ 1045 memcpy(o, c, osize*sizeof(*o)); 1046 1047 /* swap o and w arrays */ 1048 tmp = o; 1049 o = w; 1050 w = tmp; 1051 wsize = osize; 1052 break; 1053 1054 1055 case CRUSH_RULE_EMIT: 1056 for (i = 0; i < wsize && result_len < result_max; i++) { 1057 result[result_len] = w[i]; 1058 result_len++; 1059 } 1060 wsize = 0; 1061 break; 1062 1063 default: 1064 dprintk(" unknown op %d at step %d\n", 1065 curstep->op, step); 1066 break; 1067 } 1068 } 1069 1070 return result_len; 1071 } 1072