ceph/src/crush/builder.c

   1 #include <string.h>
   2 #include <math.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <assert.h>
   6 #include <errno.h>
   7
   8 #include "crush/crush.h"
   9 #include "builder.h"
  10
  11 #define dprintk(args...) /* printf(args) */
  12
  13 #define BUG_ON(x) assert(!(x))
  14
  15 struct crush_map *crush_create()
  16 {
  17         struct crush_map *m;
  18         m = malloc(sizeof(*m));
  19         if (!m)
  20                 return NULL;
  21         memset(m, 0, sizeof(*m));
  22
  23         set_optimal_crush_map(m);
  24         return m;
  25 }
  26
  27 /*
  28  * finalize should be called _after_ all buckets are added to the map.
  29  */
  30 void crush_finalize(struct crush_map *map)
  31 {
  32         int b;
  33         __u32 i;
  34
  35         /* Calculate the needed working space while we do other
  36            finalization tasks. */
  37         map->working_size = sizeof(struct crush_work);
  38         /* Space for the array of pointers to per-bucket workspace */
  39         map->working_size += map->max_buckets *
  40                 sizeof(struct crush_work_bucket *);
  41
  42         /* calc max_devices */
  43         map->max_devices = 0;
  44         for (b=0; b<map->max_buckets; b++) {
  45                 if (map->buckets[b] == 0)
  46                         continue;
  47                 for (i=0; i<map->buckets[b]->size; i++)
  48                         if (map->buckets[b]->items[i] >= map->max_devices)
  49                                 map->max_devices = map->buckets[b]->items[i] + 1;
  50
  51                 switch (map->buckets[b]->alg) {
  52                 default:
  53                         /* The base case, permutation variables and
  54                            the pointer to the permutation array. */
  55                         map->working_size += sizeof(struct crush_work_bucket);
  56                         break;
  57                 }
  58                 /* Every bucket has a permutation array. */
  59                 map->working_size += map->buckets[b]->size * sizeof(__u32);
  60         }
  61 }
  62
  63
  64
  65 /** rules **/
  66
  67 int crush_add_rule(struct crush_map *map, struct crush_rule *rule, int ruleno)
  68 {
  69         __u32 r;
  70
  71         if (ruleno < 0) {
  72                 for (r=0; r < map->max_rules; r++)
  73                         if (map->rules[r] == 0)
  74                                 break;
  75                 assert(r < CRUSH_MAX_RULES);
  76         }
  77         else
  78                 r = ruleno;
  79
  80         if (r >= map->max_rules) {
  81                 /* expand array */
  82                 int oldsize;
  83                 void *_realloc = NULL;
  84                 if (map->max_rules +1 > CRUSH_MAX_RULES)
  85                         return -ENOSPC;
  86                 oldsize = map->max_rules;
  87                 map->max_rules = r+1;
  88                 if ((_realloc = realloc(map->rules, map->max_rules * sizeof(map->rules[0]))) == NULL) {
  89                         return -ENOMEM;
  90                 } else {
  91                         map->rules = _realloc;
  92                 }
  93                 memset(map->rules + oldsize, 0, (map->max_rules-oldsize) * sizeof(map->rules[0]));
  94         }
  95
  96         /* add it */
  97         map->rules[r] = rule;
  98         return r;
  99 }
 100
 101 struct crush_rule *crush_make_rule(int len, int ruleset, int type, int minsize, int maxsize)
 102 {
 103         struct crush_rule *rule;
 104         rule = malloc(crush_rule_size(len));
 105         if (!rule)
 106                 return NULL;
 107         rule->len = len;
 108         rule->mask.ruleset = ruleset;
 109         rule->mask.type = type;
 110         rule->mask.min_size = minsize;
 111         rule->mask.max_size = maxsize;
 112         return rule;
 113 }
 114
 115 /*
 116  * be careful; this doesn't verify that the buffer you allocated is big enough!
 117  */
 118 void crush_rule_set_step(struct crush_rule *rule, int n, int op, int arg1, int arg2)
 119 {
 120         assert((__u32)n < rule->len);
 121         rule->steps[n].op = op;
 122         rule->steps[n].arg1 = arg1;
 123         rule->steps[n].arg2 = arg2;
 124 }
 125
 126
 127 /** buckets **/
 128 int crush_get_next_bucket_id(struct crush_map *map)
 129 {
 130         int pos;
 131         for (pos=0; pos < map->max_buckets; pos++)
 132                 if (map->buckets[pos] == 0)
 133                         break;
 134         return -1 - pos;
 135 }
 136
 137
 138 int crush_add_bucket(struct crush_map *map,
 139                      int id,
 140                      struct crush_bucket *bucket,
 141                      int *idout)
 142 {
 143         int pos;
 144
 145         /* find a bucket id */
 146         if (id == 0)
 147                 id = crush_get_next_bucket_id(map);
 148         pos = -1 - id;
 149
 150         while (pos >= map->max_buckets) {
 151                 /* expand array */
 152                 int oldsize = map->max_buckets;
 153                 if (map->max_buckets)
 154                         map->max_buckets *= 2;
 155                 else
 156                         map->max_buckets = 8;
 157                 void *_realloc = NULL;
 158                 if ((_realloc = realloc(map->buckets, map->max_buckets * sizeof(map->buckets[0]))) == NULL) {
 159                         return -ENOMEM;
 160                 } else {
 161                         map->buckets = _realloc;
 162                 }
 163                 memset(map->buckets + oldsize, 0, (map->max_buckets-oldsize) * sizeof(map->buckets[0]));
 164         }
 165
 166         if (map->buckets[pos] != 0) {
 167                 return -EEXIST;
 168         }
 169
 170         /* add it */
 171         bucket->id = id;
 172         map->buckets[pos] = bucket;
 173
 174         if (idout) *idout = id;
 175         return 0;
 176 }
 177
 178 int crush_remove_bucket(struct crush_map *map, struct crush_bucket *bucket)
 179 {
 180         int pos = -1 - bucket->id;
 181        assert(pos < map->max_buckets);
 182         map->buckets[pos] = NULL;
 183         crush_destroy_bucket(bucket);
 184         return 0;
 185 }
 186
 187
 188 /* uniform bucket */
 189
 190 struct crush_bucket_uniform *
 191 crush_make_uniform_bucket(int hash, int type, int size,
 192                           int *items,
 193                           int item_weight)
 194 {
 195         int i;
 196         struct crush_bucket_uniform *bucket;
 197
 198         bucket = malloc(sizeof(*bucket));
 199         if (!bucket)
 200                 return NULL;
 201         memset(bucket, 0, sizeof(*bucket));
 202         bucket->h.alg = CRUSH_BUCKET_UNIFORM;
 203         bucket->h.hash = hash;
 204         bucket->h.type = type;
 205         bucket->h.size = size;
 206
 207         if (crush_multiplication_is_unsafe(size, item_weight))
 208                 goto err;
 209
 210         bucket->h.weight = size * item_weight;
 211         bucket->item_weight = item_weight;
 212         bucket->h.items = malloc(sizeof(__s32)*size);
 213
 214         if (!bucket->h.items)
 215                 goto err;
 216
 217         for (i=0; i<size; i++)
 218                 bucket->h.items[i] = items[i];
 219
 220         return bucket;
 221 err:
 222         free(bucket->h.items);
 223         free(bucket);
 224         return NULL;
 225 }
 226
 227
 228 /* list bucket */
 229
 230 struct crush_bucket_list*
 231 crush_make_list_bucket(int hash, int type, int size,
 232                        int *items,
 233                        int *weights)
 234 {
 235         int i;
 236         int w;
 237         struct crush_bucket_list *bucket;
 238
 239         bucket = malloc(sizeof(*bucket));
 240         if (!bucket)
 241                 return NULL;
 242         memset(bucket, 0, sizeof(*bucket));
 243         bucket->h.alg = CRUSH_BUCKET_LIST;
 244         bucket->h.hash = hash;
 245         bucket->h.type = type;
 246         bucket->h.size = size;
 247
 248         bucket->h.items = malloc(sizeof(__s32)*size);
 249         if (!bucket->h.items)
 250                 goto err;
 251
 252
 253         bucket->item_weights = malloc(sizeof(__u32)*size);
 254         if (!bucket->item_weights)
 255                 goto err;
 256         bucket->sum_weights = malloc(sizeof(__u32)*size);
 257         if (!bucket->sum_weights)
 258                 goto err;
 259         w = 0;
 260         for (i=0; i<size; i++) {
 261                 bucket->h.items[i] = items[i];
 262                 bucket->item_weights[i] = weights[i];
 263
 264                 if (crush_addition_is_unsafe(w, weights[i]))
 265                         goto err;
 266
 267                 w += weights[i];
 268                 bucket->sum_weights[i] = w;
 269                 /*dprintk("pos %d item %d weight %d sum %d\n",
 270                   i, items[i], weights[i], bucket->sum_weights[i]);*/
 271         }
 272
 273         bucket->h.weight = w;
 274
 275         return bucket;
 276 err:
 277         free(bucket->sum_weights);
 278         free(bucket->item_weights);
 279         free(bucket->h.items);
 280         free(bucket);
 281         return NULL;
 282 }
 283
 284
 285 /* tree bucket */
 286
 287 static int height(int n) {
 288         int h = 0;
 289         while ((n & 1) == 0) {
 290                 h++;
 291                 n = n >> 1;
 292         }
 293         return h;
 294 }
 295 static int on_right(int n, int h) {
 296         return n & (1 << (h+1));
 297 }
 298 static int parent(int n)
 299 {
 300         int h = height(n);
 301         if (on_right(n, h))
 302                 return n - (1<<h);
 303         else
 304                 return n + (1<<h);
 305 }
 306
 307 static int calc_depth(int size)
 308 {
 309         if (size == 0) {
 310                 return 0;
 311         }
 312
 313         int depth = 1;
 314         int t = size - 1;
 315         while (t) {
 316                 t = t >> 1;
 317                 depth++;
 318         }
 319         return depth;
 320 }
 321
 322 struct crush_bucket_tree*
 323 crush_make_tree_bucket(int hash, int type, int size,
 324                        int *items,    /* in leaf order */
 325                        int *weights)
 326 {
 327         struct crush_bucket_tree *bucket;
 328         int depth;
 329         int node;
 330         int i, j;
 331
 332         bucket = malloc(sizeof(*bucket));
 333         if (!bucket)
 334                 return NULL;
 335         memset(bucket, 0, sizeof(*bucket));
 336         bucket->h.alg = CRUSH_BUCKET_TREE;
 337         bucket->h.hash = hash;
 338         bucket->h.type = type;
 339         bucket->h.size = size;
 340
 341         if (size == 0) {
 342                 bucket->h.items = NULL;
 343                 bucket->h.weight = 0;
 344                 bucket->node_weights = NULL;
 345                 bucket->num_nodes = 0;
 346                 /* printf("size 0 depth 0 nodes 0\n"); */
 347                 return bucket;
 348         }
 349
 350         bucket->h.items = malloc(sizeof(__s32)*size);
 351         if (!bucket->h.items)
 352                 goto err;
 353
 354         /* calc tree depth */
 355         depth = calc_depth(size);
 356         bucket->num_nodes = 1 << depth;
 357         dprintk("size %d depth %d nodes %d\n", size, depth, bucket->num_nodes);
 358
 359         bucket->node_weights = malloc(sizeof(__u32)*bucket->num_nodes);
 360         if (!bucket->node_weights)
 361                 goto err;
 362
 363         memset(bucket->h.items, 0, sizeof(__s32)*bucket->h.size);
 364         memset(bucket->node_weights, 0, sizeof(__u32)*bucket->num_nodes);
 365
 366         for (i=0; i<size; i++) {
 367                 bucket->h.items[i] = items[i];
 368                 node = crush_calc_tree_node(i);
 369                 dprintk("item %d node %d weight %d\n", i, node, weights[i]);
 370                 bucket->node_weights[node] = weights[i];
 371
 372                 if (crush_addition_is_unsafe(bucket->h.weight, weights[i]))
 373                         goto err;
 374
 375                 bucket->h.weight += weights[i];
 376                 for (j=1; j<depth; j++) {
 377                         node = parent(node);
 378
 379                         if (crush_addition_is_unsafe(bucket->node_weights[node], weights[i]))
 380                                 goto err;
 381
 382                         bucket->node_weights[node] += weights[i];
 383                         dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
 384                 }
 385         }
 386         BUG_ON(bucket->node_weights[bucket->num_nodes/2] != bucket->h.weight);
 387
 388         return bucket;
 389 err:
 390         free(bucket->node_weights);
 391         free(bucket->h.items);
 392         free(bucket);
 393         return NULL;
 394 }
 395
 396
 397
 398 /* straw bucket */
 399
 400 /*
 401  * this code was written 8 years ago.  i have a vague recollection of
 402  * drawing boxes underneath bars of different lengths, where the bar
 403  * length represented the probability/weight, and that there was some
 404  * trial and error involved in arriving at this implementation.
 405  * however, reading the code now after all this time, the intuition
 406  * that motivated is lost on me.  lame.  my only excuse is that I now
 407  * know that the approach is fundamentally flawed and am not
 408  * particularly motivated to reconstruct the flawed reasoning.
 409  *
 410  * as best as i can remember, the idea is: sort the weights, and start
 411  * with the smallest.  arbitrarily scale it at 1.0 (16-bit fixed
 412  * point).  look at the next larger weight, and calculate the scaling
 413  * factor for that straw based on the relative difference in weight so
 414  * far.  what's not clear to me now is why we are looking at wnext
 415  * (the delta to the next bigger weight) for all remaining weights,
 416  * and slicing things horizontally instead of considering just the
 417  * next item or set of items.  or why pow() is used the way it is.
 418  *
 419  * note that the original version 1 of this function made special
 420  * accomodation for the case where straw lengths were identical.  this
 421  * is also flawed in a non-obvious way; version 2 drops the special
 422  * handling and appears to work just as well.
 423  *
 424  * moral of the story: if you do something clever, write down why it
 425  * works.
 426  */
 427 int crush_calc_straw(struct crush_map *map, struct crush_bucket_straw *bucket)
 428 {
 429         int *reverse;
 430         int i, j, k;
 431         double straw, wbelow, lastw, wnext, pbelow;
 432         int numleft;
 433         int size = bucket->h.size;
 434         __u32 *weights = bucket->item_weights;
 435
 436         /* reverse sort by weight (simple insertion sort) */
 437         reverse = malloc(sizeof(int) * size);
 438         if (!reverse)
 439                 return -ENOMEM;
 440         if (size)
 441                 reverse[0] = 0;
 442         for (i=1; i<size; i++) {
 443                 for (j=0; j<i; j++) {
 444                         if (weights[i] < weights[reverse[j]]) {
 445                                 /* insert here */
 446                                 for (k=i; k>j; k--)
 447                                         reverse[k] = reverse[k-1];
 448                                 reverse[j] = i;
 449                                 break;
 450                         }
 451                 }
 452                 if (j == i)
 453                         reverse[i] = i;
 454         }
 455
 456         numleft = size;
 457         straw = 1.0;
 458         wbelow = 0;
 459         lastw = 0;
 460
 461         i=0;
 462         while (i < size) {
 463                 if (map->straw_calc_version == 0) {
 464                         /* zero weight items get 0 length straws! */
 465                         if (weights[reverse[i]] == 0) {
 466                                 bucket->straws[reverse[i]] = 0;
 467                                 i++;
 468                                 continue;
 469                         }
 470
 471                         /* set this item's straw */
 472                         bucket->straws[reverse[i]] = straw * 0x10000;
 473                         dprintk("item %d at %d weight %d straw %d (%lf)\n",
 474                                 bucket->h.items[reverse[i]],
 475                                 reverse[i], weights[reverse[i]],
 476                                 bucket->straws[reverse[i]], straw);
 477                         i++;
 478                         if (i == size)
 479                                 break;
 480
 481                         /* same weight as previous? */
 482                         if (weights[reverse[i]] == weights[reverse[i-1]]) {
 483                                 dprintk("same as previous\n");
 484                                 continue;
 485                         }
 486
 487                         /* adjust straw for next guy */
 488                         wbelow += ((double)weights[reverse[i-1]] - lastw) *
 489                                 numleft;
 490                         for (j=i; j<size; j++)
 491                                 if (weights[reverse[j]] == weights[reverse[i]])
 492                                         numleft--;
 493                                 else
 494                                         break;
 495                         wnext = numleft * (weights[reverse[i]] -
 496                                            weights[reverse[i-1]]);
 497                         pbelow = wbelow / (wbelow + wnext);
 498                         dprintk("wbelow %lf  wnext %lf  pbelow %lf  numleft %d\n",
 499                                 wbelow, wnext, pbelow, numleft);
 500
 501                         straw *= pow((double)1.0 / pbelow, (double)1.0 /
 502                                      (double)numleft);
 503
 504                         lastw = weights[reverse[i-1]];
 505                 } else if (map->straw_calc_version >= 1) {
 506                         /* zero weight items get 0 length straws! */
 507                         if (weights[reverse[i]] == 0) {
 508                                 bucket->straws[reverse[i]] = 0;
 509                                 i++;
 510                                 numleft--;
 511                                 continue;
 512                         }
 513
 514                         /* set this item's straw */
 515                         bucket->straws[reverse[i]] = straw * 0x10000;
 516                         dprintk("item %d at %d weight %d straw %d (%lf)\n",
 517                                 bucket->h.items[reverse[i]],
 518                                 reverse[i], weights[reverse[i]],
 519                                 bucket->straws[reverse[i]], straw);
 520                         i++;
 521                         if (i == size)
 522                                 break;
 523
 524                         /* adjust straw for next guy */
 525                         wbelow += ((double)weights[reverse[i-1]] - lastw) *
 526                                 numleft;
 527                         numleft--;
 528                         wnext = numleft * (weights[reverse[i]] -
 529                                            weights[reverse[i-1]]);
 530                         pbelow = wbelow / (wbelow + wnext);
 531                         dprintk("wbelow %lf  wnext %lf  pbelow %lf  numleft %d\n",
 532                                 wbelow, wnext, pbelow, numleft);
 533
 534                         straw *= pow((double)1.0 / pbelow, (double)1.0 /
 535                                      (double)numleft);
 536
 537                         lastw = weights[reverse[i-1]];
 538                 }
 539         }
 540
 541         free(reverse);
 542         return 0;
 543 }
 544
 545 struct crush_bucket_straw *
 546 crush_make_straw_bucket(struct crush_map *map,
 547                         int hash,
 548                         int type,
 549                         int size,
 550                         int *items,
 551                         int *weights)
 552 {
 553         struct crush_bucket_straw *bucket;
 554         int i;
 555
 556         bucket = malloc(sizeof(*bucket));
 557         if (!bucket)
 558                 return NULL;
 559         memset(bucket, 0, sizeof(*bucket));
 560         bucket->h.alg = CRUSH_BUCKET_STRAW;
 561         bucket->h.hash = hash;
 562         bucket->h.type = type;
 563         bucket->h.size = size;
 564
 565         bucket->h.items = malloc(sizeof(__s32)*size);
 566         if (!bucket->h.items)
 567                 goto err;
 568         bucket->item_weights = malloc(sizeof(__u32)*size);
 569         if (!bucket->item_weights)
 570                 goto err;
 571         bucket->straws = malloc(sizeof(__u32)*size);
 572         if (!bucket->straws)
 573                 goto err;
 574
 575         bucket->h.weight = 0;
 576         for (i=0; i<size; i++) {
 577                 bucket->h.items[i] = items[i];
 578                 bucket->h.weight += weights[i];
 579                 bucket->item_weights[i] = weights[i];
 580         }
 581
 582         if (crush_calc_straw(map, bucket) < 0)
 583                 goto err;
 584
 585         return bucket;
 586 err:
 587         free(bucket->straws);
 588         free(bucket->item_weights);
 589         free(bucket->h.items);
 590         free(bucket);
 591         return NULL;
 592 }
 593
 594 struct crush_bucket_straw2 *
 595 crush_make_straw2_bucket(struct crush_map *map,
 596                          int hash,
 597                          int type,
 598                          int size,
 599                          int *items,
 600                          int *weights)
 601 {
 602         struct crush_bucket_straw2 *bucket;
 603         int i;
 604
 605         bucket = malloc(sizeof(*bucket));
 606         if (!bucket)
 607                 return NULL;
 608         memset(bucket, 0, sizeof(*bucket));
 609         bucket->h.alg = CRUSH_BUCKET_STRAW2;
 610         bucket->h.hash = hash;
 611         bucket->h.type = type;
 612         bucket->h.size = size;
 613
 614         bucket->h.items = malloc(sizeof(__s32)*size);
 615         if (!bucket->h.items)
 616                 goto err;
 617         bucket->item_weights = malloc(sizeof(__u32)*size);
 618         if (!bucket->item_weights)
 619                 goto err;
 620
 621         bucket->h.weight = 0;
 622         for (i=0; i<size; i++) {
 623                 bucket->h.items[i] = items[i];
 624                 bucket->h.weight += weights[i];
 625                 bucket->item_weights[i] = weights[i];
 626         }
 627
 628         return bucket;
 629 err:
 630         free(bucket->item_weights);
 631         free(bucket->h.items);
 632         free(bucket);
 633         return NULL;
 634 }
 635
 636
 637
 638 struct crush_bucket*
 639 crush_make_bucket(struct crush_map *map,
 640                   int alg, int hash, int type, int size,
 641                   int *items,
 642                   int *weights)
 643 {
 644         int item_weight;
 645
 646         switch (alg) {
 647         case CRUSH_BUCKET_UNIFORM:
 648                 if (size && weights)
 649                         item_weight = weights[0];
 650                 else
 651                         item_weight = 0;
 652                 return (struct crush_bucket *)crush_make_uniform_bucket(hash, type, size, items, item_weight);
 653
 654         case CRUSH_BUCKET_LIST:
 655                 return (struct crush_bucket *)crush_make_list_bucket(hash, type, size, items, weights);
 656
 657         case CRUSH_BUCKET_TREE:
 658                 return (struct crush_bucket *)crush_make_tree_bucket(hash, type, size, items, weights);
 659
 660         case CRUSH_BUCKET_STRAW:
 661                 return (struct crush_bucket *)crush_make_straw_bucket(map, hash, type, size, items, weights);
 662         case CRUSH_BUCKET_STRAW2:
 663                 return (struct crush_bucket *)crush_make_straw2_bucket(map, hash, type, size, items, weights);
 664         }
 665         return 0;
 666 }
 667
 668
 669 /************************************************/
 670
 671 int crush_add_uniform_bucket_item(struct crush_bucket_uniform *bucket, int item, int weight)
 672 {
 673         int newsize = bucket->h.size + 1;
 674         void *_realloc = NULL;
 675
 676         /* In such situation 'CRUSH_BUCKET_UNIFORM', the weight
 677            provided for the item should be the same as
 678            bucket->item_weight defined with 'crush_make_bucket'. This
 679            assumption is enforced by the return value which is always
 680            0. */
 681         if (bucket->item_weight != weight) {
 682           return -EINVAL;
 683         }
 684
 685         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 686                 return -ENOMEM;
 687         } else {
 688                 bucket->h.items = _realloc;
 689         }
 690
 691         bucket->h.items[newsize-1] = item;
 692
 693         if (crush_addition_is_unsafe(bucket->h.weight, weight))
 694                 return -ERANGE;
 695
 696         bucket->h.weight += weight;
 697         bucket->h.size++;
 698
 699         return 0;
 700 }
 701
 702 int crush_add_list_bucket_item(struct crush_bucket_list *bucket, int item, int weight)
 703 {
 704         int newsize = bucket->h.size + 1;
 705         void *_realloc = NULL;
 706
 707         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 708                 return -ENOMEM;
 709         } else {
 710                 bucket->h.items = _realloc;
 711         }
 712         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
 713                 return -ENOMEM;
 714         } else {
 715                 bucket->item_weights = _realloc;
 716         }
 717         if ((_realloc = realloc(bucket->sum_weights, sizeof(__u32)*newsize)) == NULL) {
 718                 return -ENOMEM;
 719         } else {
 720                 bucket->sum_weights = _realloc;
 721         }
 722
 723         bucket->h.items[newsize-1] = item;
 724         bucket->item_weights[newsize-1] = weight;
 725         if (newsize > 1) {
 726
 727                 if (crush_addition_is_unsafe(bucket->sum_weights[newsize-2], weight))
 728                         return -ERANGE;
 729
 730                 bucket->sum_weights[newsize-1] = bucket->sum_weights[newsize-2] + weight;
 731         }
 732
 733         else {
 734                 bucket->sum_weights[newsize-1] = weight;
 735         }
 736
 737         bucket->h.weight += weight;
 738         bucket->h.size++;
 739         return 0;
 740 }
 741
 742 int crush_add_tree_bucket_item(struct crush_bucket_tree *bucket, int item, int weight)
 743 {
 744         int newsize = bucket->h.size + 1;
 745         int depth = calc_depth(newsize);;
 746         int node;
 747         int j;
 748         void *_realloc = NULL;
 749
 750         bucket->num_nodes = 1 << depth;
 751
 752         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 753                 return -ENOMEM;
 754         } else {
 755                 bucket->h.items = _realloc;
 756         }
 757         if ((_realloc = realloc(bucket->node_weights, sizeof(__u32)*bucket->num_nodes)) == NULL) {
 758                 return -ENOMEM;
 759         } else {
 760                 bucket->node_weights = _realloc;
 761         }
 762
 763         node = crush_calc_tree_node(newsize-1);
 764         bucket->node_weights[node] = weight;
 765
 766         /* if the depth increase, we need to initialize the new root node's weight before add bucket item */
 767         int root = bucket->num_nodes/2;
 768         if (depth >= 2 && (node - 1) == root) {
 769                 /* if the new item is the first node in right sub tree, so
 770                 * the root node initial weight is left sub tree's weight
 771                 */
 772                 bucket->node_weights[root] = bucket->node_weights[root/2];
 773         }
 774
 775         for (j=1; j<depth; j++) {
 776                 node = parent(node);
 777
 778                 if (crush_addition_is_unsafe(bucket->node_weights[node], weight))
 779                         return -ERANGE;
 780
 781                 bucket->node_weights[node] += weight;
 782                 dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
 783         }
 784
 785
 786         if (crush_addition_is_unsafe(bucket->h.weight, weight))
 787                 return -ERANGE;
 788
 789         bucket->h.items[newsize-1] = item;
 790         bucket->h.weight += weight;
 791         bucket->h.size++;
 792
 793         return 0;
 794 }
 795
 796 int crush_add_straw_bucket_item(struct crush_map *map,
 797                                 struct crush_bucket_straw *bucket,
 798                                 int item, int weight)
 799 {
 800         int newsize = bucket->h.size + 1;
 801
 802         void *_realloc = NULL;
 803
 804         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 805                 return -ENOMEM;
 806         } else {
 807                 bucket->h.items = _realloc;
 808         }
 809         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
 810                 return -ENOMEM;
 811         } else {
 812                 bucket->item_weights = _realloc;
 813         }
 814         if ((_realloc = realloc(bucket->straws, sizeof(__u32)*newsize)) == NULL) {
 815                 return -ENOMEM;
 816         } else {
 817                 bucket->straws = _realloc;
 818         }
 819
 820         bucket->h.items[newsize-1] = item;
 821         bucket->item_weights[newsize-1] = weight;
 822
 823         if (crush_addition_is_unsafe(bucket->h.weight, weight))
 824                 return -ERANGE;
 825
 826         bucket->h.weight += weight;
 827         bucket->h.size++;
 828
 829         return crush_calc_straw(map, bucket);
 830 }
 831
 832 int crush_add_straw2_bucket_item(struct crush_map *map,
 833                                  struct crush_bucket_straw2 *bucket,
 834                                  int item, int weight)
 835 {
 836         int newsize = bucket->h.size + 1;
 837
 838         void *_realloc = NULL;
 839
 840         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 841                 return -ENOMEM;
 842         } else {
 843                 bucket->h.items = _realloc;
 844         }
 845         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
 846                 return -ENOMEM;
 847         } else {
 848                 bucket->item_weights = _realloc;
 849         }
 850
 851         bucket->h.items[newsize-1] = item;
 852         bucket->item_weights[newsize-1] = weight;
 853
 854         if (crush_addition_is_unsafe(bucket->h.weight, weight))
 855                 return -ERANGE;
 856
 857         bucket->h.weight += weight;
 858         bucket->h.size++;
 859
 860         return 0;
 861 }
 862
 863 int crush_bucket_add_item(struct crush_map *map,
 864                           struct crush_bucket *b, int item, int weight)
 865 {
 866         switch (b->alg) {
 867         case CRUSH_BUCKET_UNIFORM:
 868                 return crush_add_uniform_bucket_item((struct crush_bucket_uniform *)b, item, weight);
 869         case CRUSH_BUCKET_LIST:
 870                 return crush_add_list_bucket_item((struct crush_bucket_list *)b, item, weight);
 871         case CRUSH_BUCKET_TREE:
 872                 return crush_add_tree_bucket_item((struct crush_bucket_tree *)b, item, weight);
 873         case CRUSH_BUCKET_STRAW:
 874                 return crush_add_straw_bucket_item(map, (struct crush_bucket_straw *)b, item, weight);
 875         case CRUSH_BUCKET_STRAW2:
 876                 return crush_add_straw2_bucket_item(map, (struct crush_bucket_straw2 *)b, item, weight);
 877         default:
 878                 return -1;
 879         }
 880 }
 881
 882 /************************************************/
 883
 884 int crush_remove_uniform_bucket_item(struct crush_bucket_uniform *bucket, int item)
 885 {
 886         unsigned i, j;
 887         int newsize;
 888         void *_realloc = NULL;
 889
 890         for (i = 0; i < bucket->h.size; i++)
 891                 if (bucket->h.items[i] == item)
 892                         break;
 893         if (i == bucket->h.size)
 894                 return -ENOENT;
 895
 896         for (j = i; j < bucket->h.size; j++)
 897                 bucket->h.items[j] = bucket->h.items[j+1];
 898         newsize = --bucket->h.size;
 899         if (bucket->item_weight < bucket->h.weight)
 900                 bucket->h.weight -= bucket->item_weight;
 901         else
 902                 bucket->h.weight = 0;
 903
 904         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 905                 return -ENOMEM;
 906         } else {
 907                 bucket->h.items = _realloc;
 908         }
 909         return 0;
 910 }
 911
 912 int crush_remove_list_bucket_item(struct crush_bucket_list *bucket, int item)
 913 {
 914         unsigned i, j;
 915         int newsize;
 916         unsigned weight;
 917
 918         for (i = 0; i < bucket->h.size; i++)
 919                 if (bucket->h.items[i] == item)
 920                         break;
 921         if (i == bucket->h.size)
 922                 return -ENOENT;
 923
 924         weight = bucket->item_weights[i];
 925         for (j = i; j < bucket->h.size; j++) {
 926                 bucket->h.items[j] = bucket->h.items[j+1];
 927                 bucket->item_weights[j] = bucket->item_weights[j+1];
 928                 bucket->sum_weights[j] = bucket->sum_weights[j+1] - weight;
 929         }
 930         if (weight < bucket->h.weight)
 931                 bucket->h.weight -= weight;
 932         else
 933                 bucket->h.weight = 0;
 934         newsize = --bucket->h.size;
 935
 936         void *_realloc = NULL;
 937
 938         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
 939                 return -ENOMEM;
 940         } else {
 941                 bucket->h.items = _realloc;
 942         }
 943         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
 944                 return -ENOMEM;
 945         } else {
 946                 bucket->item_weights = _realloc;
 947         }
 948         if ((_realloc = realloc(bucket->sum_weights, sizeof(__u32)*newsize)) == NULL) {
 949                 return -ENOMEM;
 950         } else {
 951                 bucket->sum_weights = _realloc;
 952         }
 953         return 0;
 954 }
 955
 956 int crush_remove_tree_bucket_item(struct crush_bucket_tree *bucket, int item)
 957 {
 958         unsigned i;
 959         unsigned newsize;
 960
 961         for (i = 0; i < bucket->h.size; i++) {
 962                 int node;
 963                 unsigned weight;
 964                 int j;
 965                 int depth = calc_depth(bucket->h.size);
 966
 967                 if (bucket->h.items[i] != item)
 968                         continue;
 969
 970                 bucket->h.items[i] = 0;
 971                 node = crush_calc_tree_node(i);
 972                 weight = bucket->node_weights[node];
 973                 bucket->node_weights[node] = 0;
 974
 975                 for (j = 1; j < depth; j++) {
 976                         node = parent(node);
 977                         bucket->node_weights[node] -= weight;
 978                         dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
 979                 }
 980                 if (weight < bucket->h.weight)
 981                         bucket->h.weight -= weight;
 982                 else
 983                         bucket->h.weight = 0;
 984                 break;
 985         }
 986         if (i == bucket->h.size)
 987                 return -ENOENT;
 988
 989         newsize = bucket->h.size;
 990         while (newsize > 0) {
 991                 int node = crush_calc_tree_node(newsize - 1);
 992                 if (bucket->node_weights[node])
 993                         break;
 994                 --newsize;
 995         }
 996
 997         if (newsize != bucket->h.size) {
 998                 int olddepth, newdepth;
 999
1000                 void *_realloc = NULL;
1001
1002                 if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
1003                         return -ENOMEM;
1004                 } else {
1005                         bucket->h.items = _realloc;
1006                 }
1007
1008                 olddepth = calc_depth(bucket->h.size);
1009                 newdepth = calc_depth(newsize);
1010                 if (olddepth != newdepth) {
1011                         bucket->num_nodes = 1 << newdepth;
1012                         if ((_realloc = realloc(bucket->node_weights,
1013                                                 sizeof(__u32)*bucket->num_nodes)) == NULL) {
1014                                 return -ENOMEM;
1015                         } else {
1016                                 bucket->node_weights = _realloc;
1017                         }
1018                 }
1019
1020                 bucket->h.size = newsize;
1021         }
1022         return 0;
1023 }
1024
1025 int crush_remove_straw_bucket_item(struct crush_map *map,
1026                                    struct crush_bucket_straw *bucket, int item)
1027 {
1028         int newsize = bucket->h.size - 1;
1029         unsigned i, j;
1030
1031         for (i = 0; i < bucket->h.size; i++) {
1032                 if (bucket->h.items[i] == item) {
1033                         bucket->h.size--;
1034                         if (bucket->item_weights[i] < bucket->h.weight)
1035                                 bucket->h.weight -= bucket->item_weights[i];
1036                         else
1037                                 bucket->h.weight = 0;
1038                         for (j = i; j < bucket->h.size; j++) {
1039                                 bucket->h.items[j] = bucket->h.items[j+1];
1040                                 bucket->item_weights[j] = bucket->item_weights[j+1];
1041                         }
1042                         break;
1043                 }
1044         }
1045         if (i == bucket->h.size)
1046                 return -ENOENT;
1047
1048         void *_realloc = NULL;
1049
1050         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
1051                 return -ENOMEM;
1052         } else {
1053                 bucket->h.items = _realloc;
1054         }
1055         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
1056                 return -ENOMEM;
1057         } else {
1058                 bucket->item_weights = _realloc;
1059         }
1060         if ((_realloc = realloc(bucket->straws, sizeof(__u32)*newsize)) == NULL) {
1061                 return -ENOMEM;
1062         } else {
1063                 bucket->straws = _realloc;
1064         }
1065
1066         return crush_calc_straw(map, bucket);
1067 }
1068
1069 int crush_remove_straw2_bucket_item(struct crush_map *map,
1070                                     struct crush_bucket_straw2 *bucket, int item)
1071 {
1072         int newsize = bucket->h.size - 1;
1073         unsigned i, j;
1074
1075         for (i = 0; i < bucket->h.size; i++) {
1076                 if (bucket->h.items[i] == item) {
1077                         bucket->h.size--;
1078                         if (bucket->item_weights[i] < bucket->h.weight)
1079                                 bucket->h.weight -= bucket->item_weights[i];
1080                         else
1081                                 bucket->h.weight = 0;
1082                         for (j = i; j < bucket->h.size; j++) {
1083                                 bucket->h.items[j] = bucket->h.items[j+1];
1084                                 bucket->item_weights[j] = bucket->item_weights[j+1];
1085                         }
1086                         break;
1087                 }
1088         }
1089         if (i == bucket->h.size)
1090                 return -ENOENT;
1091
1092         void *_realloc = NULL;
1093
1094         if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
1095                 return -ENOMEM;
1096         } else {
1097                 bucket->h.items = _realloc;
1098         }
1099         if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
1100                 return -ENOMEM;
1101         } else {
1102                 bucket->item_weights = _realloc;
1103         }
1104
1105         return 0;
1106 }
1107
1108 int crush_bucket_remove_item(struct crush_map *map, struct crush_bucket *b, int item)
1109 {
1110         switch (b->alg) {
1111         case CRUSH_BUCKET_UNIFORM:
1112                 return crush_remove_uniform_bucket_item((struct crush_bucket_uniform *)b, item);
1113         case CRUSH_BUCKET_LIST:
1114                 return crush_remove_list_bucket_item((struct crush_bucket_list *)b, item);
1115         case CRUSH_BUCKET_TREE:
1116                 return crush_remove_tree_bucket_item((struct crush_bucket_tree *)b, item);
1117         case CRUSH_BUCKET_STRAW:
1118                 return crush_remove_straw_bucket_item(map, (struct crush_bucket_straw *)b, item);
1119         case CRUSH_BUCKET_STRAW2:
1120                 return crush_remove_straw2_bucket_item(map, (struct crush_bucket_straw2 *)b, item);
1121         default:
1122                 return -1;
1123         }
1124 }
1125
1126
1127 /************************************************/
1128
1129 int crush_adjust_uniform_bucket_item_weight(struct crush_bucket_uniform *bucket, int item, int weight)
1130 {
1131         int diff = (weight - bucket->item_weight) * bucket->h.size;
1132
1133         bucket->item_weight = weight;
1134         bucket->h.weight = bucket->item_weight * bucket->h.size;
1135
1136         return diff;
1137 }
1138
1139 int crush_adjust_list_bucket_item_weight(struct crush_bucket_list *bucket, int item, int weight)
1140 {
1141         int diff;
1142         unsigned i, j;
1143
1144         for (i = 0; i < bucket->h.size; i++) {
1145                 if (bucket->h.items[i] == item)
1146                         break;
1147         }
1148         if (i == bucket->h.size)
1149                 return 0;
1150
1151         diff = weight - bucket->item_weights[i];
1152         bucket->item_weights[i] = weight;
1153         bucket->h.weight += diff;
1154
1155         for (j = i; j < bucket->h.size; j++)
1156                 bucket->sum_weights[j] += diff;
1157
1158         return diff;
1159 }
1160
1161 int crush_adjust_tree_bucket_item_weight(struct crush_bucket_tree *bucket, int item, int weight)
1162 {
1163         int diff;
1164         int node;
1165         unsigned i, j;
1166         unsigned depth = calc_depth(bucket->h.size);
1167
1168         for (i = 0; i < bucket->h.size; i++) {
1169                 if (bucket->h.items[i] == item)
1170                         break;
1171         }
1172         if (i == bucket->h.size)
1173                 return 0;
1174
1175         node = crush_calc_tree_node(i);
1176         diff = weight - bucket->node_weights[node];
1177         bucket->node_weights[node] = weight;
1178         bucket->h.weight += diff;
1179
1180         for (j=1; j<depth; j++) {
1181                 node = parent(node);
1182                 bucket->node_weights[node] += diff;
1183         }
1184
1185         return diff;
1186 }
1187
1188 int crush_adjust_straw_bucket_item_weight(struct crush_map *map,
1189                                           struct crush_bucket_straw *bucket,
1190                                           int item, int weight)
1191 {
1192         unsigned idx;
1193         int diff;
1194         int r;
1195
1196         for (idx = 0; idx < bucket->h.size; idx++)
1197                 if (bucket->h.items[idx] == item)
1198                         break;
1199         if (idx == bucket->h.size)
1200                 return 0;
1201
1202         diff = weight - bucket->item_weights[idx];
1203         bucket->item_weights[idx] = weight;
1204         bucket->h.weight += diff;
1205
1206         r = crush_calc_straw(map, bucket);
1207         if (r < 0)
1208                 return r;
1209
1210         return diff;
1211 }
1212
1213 int crush_adjust_straw2_bucket_item_weight(struct crush_map *map,
1214                                            struct crush_bucket_straw2 *bucket,
1215                                            int item, int weight)
1216 {
1217         unsigned idx;
1218         int diff;
1219
1220         for (idx = 0; idx < bucket->h.size; idx++)
1221                 if (bucket->h.items[idx] == item)
1222                         break;
1223         if (idx == bucket->h.size)
1224                 return 0;
1225
1226         diff = weight - bucket->item_weights[idx];
1227         bucket->item_weights[idx] = weight;
1228         bucket->h.weight += diff;
1229
1230         return diff;
1231 }
1232
1233 int crush_bucket_adjust_item_weight(struct crush_map *map,
1234                                     struct crush_bucket *b,
1235                                     int item, int weight)
1236 {
1237         switch (b->alg) {
1238         case CRUSH_BUCKET_UNIFORM:
1239                 return crush_adjust_uniform_bucket_item_weight((struct crush_bucket_uniform *)b,
1240                                                              item, weight);
1241         case CRUSH_BUCKET_LIST:
1242                 return crush_adjust_list_bucket_item_weight((struct crush_bucket_list *)b,
1243                                                             item, weight);
1244         case CRUSH_BUCKET_TREE:
1245                 return crush_adjust_tree_bucket_item_weight((struct crush_bucket_tree *)b,
1246                                                             item, weight);
1247         case CRUSH_BUCKET_STRAW:
1248                 return crush_adjust_straw_bucket_item_weight(map,
1249                                                              (struct crush_bucket_straw *)b,
1250                                                              item, weight);
1251         case CRUSH_BUCKET_STRAW2:
1252                 return crush_adjust_straw2_bucket_item_weight(map,
1253                                                               (struct crush_bucket_straw2 *)b,
1254                                                              item, weight);
1255         default:
1256                 return -1;
1257         }
1258 }
1259
1260 /************************************************/
1261
1262 static int crush_reweight_uniform_bucket(struct crush_map *map, struct crush_bucket_uniform *bucket)
1263 {
1264         unsigned i;
1265         unsigned sum = 0, n = 0, leaves = 0;
1266
1267         for (i = 0; i < bucket->h.size; i++) {
1268                 int id = bucket->h.items[i];
1269                 if (id < 0) {
1270                         struct crush_bucket *c = map->buckets[-1-id];
1271                         crush_reweight_bucket(map, c);
1272
1273                         if (crush_addition_is_unsafe(sum, c->weight))
1274                                 return -ERANGE;
1275
1276                         sum += c->weight;
1277                         n++;
1278                 } else {
1279                         leaves++;
1280                 }
1281         }
1282
1283         if (n > leaves)
1284                 bucket->item_weight = sum / n;  // more bucket children than leaves, average!
1285         bucket->h.weight = bucket->item_weight * bucket->h.size;
1286
1287         return 0;
1288 }
1289
1290 static int crush_reweight_list_bucket(struct crush_map *map, struct crush_bucket_list *bucket)
1291 {
1292         unsigned i;
1293
1294         bucket->h.weight = 0;
1295         for (i = 0; i < bucket->h.size; i++) {
1296                 int id = bucket->h.items[i];
1297                 if (id < 0) {
1298                         struct crush_bucket *c = map->buckets[-1-id];
1299                         crush_reweight_bucket(map, c);
1300                         bucket->item_weights[i] = c->weight;
1301                 }
1302
1303                 if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
1304                         return -ERANGE;
1305
1306                 bucket->h.weight += bucket->item_weights[i];
1307         }
1308
1309         return 0;
1310 }
1311
1312 static int crush_reweight_tree_bucket(struct crush_map *map, struct crush_bucket_tree *bucket)
1313 {
1314         unsigned i;
1315
1316         bucket->h.weight = 0;
1317         for (i = 0; i < bucket->h.size; i++) {
1318                 int node = crush_calc_tree_node(i);
1319                 int id = bucket->h.items[i];
1320                 if (id < 0) {
1321                         struct crush_bucket *c = map->buckets[-1-id];
1322                         crush_reweight_bucket(map, c);
1323                         bucket->node_weights[node] = c->weight;
1324                 }
1325
1326                 if (crush_addition_is_unsafe(bucket->h.weight, bucket->node_weights[node]))
1327                         return -ERANGE;
1328
1329                 bucket->h.weight += bucket->node_weights[node];
1330
1331
1332         }
1333
1334         return 0;
1335 }
1336
1337 static int crush_reweight_straw_bucket(struct crush_map *map, struct crush_bucket_straw *bucket)
1338 {
1339         unsigned i;
1340
1341         bucket->h.weight = 0;
1342         for (i = 0; i < bucket->h.size; i++) {
1343                 int id = bucket->h.items[i];
1344                 if (id < 0) {
1345                         struct crush_bucket *c = map->buckets[-1-id];
1346                         crush_reweight_bucket(map, c);
1347                         bucket->item_weights[i] = c->weight;
1348                 }
1349
1350                 if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
1351                         return -ERANGE;
1352
1353                 bucket->h.weight += bucket->item_weights[i];
1354         }
1355         crush_calc_straw(map, bucket);
1356
1357         return 0;
1358 }
1359
1360 static int crush_reweight_straw2_bucket(struct crush_map *map, struct crush_bucket_straw2 *bucket)
1361 {
1362         unsigned i;
1363
1364         bucket->h.weight = 0;
1365         for (i = 0; i < bucket->h.size; i++) {
1366                 int id = bucket->h.items[i];
1367                 if (id < 0) {
1368                         struct crush_bucket *c = map->buckets[-1-id];
1369                         crush_reweight_bucket(map, c);
1370                         bucket->item_weights[i] = c->weight;
1371                 }
1372
1373                 if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
1374                         return -ERANGE;
1375
1376                 bucket->h.weight += bucket->item_weights[i];
1377         }
1378
1379         return 0;
1380 }
1381
1382 int crush_reweight_bucket(struct crush_map *map, struct crush_bucket *b)
1383 {
1384         switch (b->alg) {
1385         case CRUSH_BUCKET_UNIFORM:
1386                 return crush_reweight_uniform_bucket(map, (struct crush_bucket_uniform *)b);
1387         case CRUSH_BUCKET_LIST:
1388                 return crush_reweight_list_bucket(map, (struct crush_bucket_list *)b);
1389         case CRUSH_BUCKET_TREE:
1390                 return crush_reweight_tree_bucket(map, (struct crush_bucket_tree *)b);
1391         case CRUSH_BUCKET_STRAW:
1392                 return crush_reweight_straw_bucket(map, (struct crush_bucket_straw *)b);
1393         case CRUSH_BUCKET_STRAW2:
1394                 return crush_reweight_straw2_bucket(map, (struct crush_bucket_straw2 *)b);
1395         default:
1396                 return -1;
1397         }
1398 }
1399
1400 struct crush_choose_arg *crush_make_choose_args(struct crush_map *map, int num_positions)
1401 {
1402   int b;
1403   int sum_bucket_size = 0;
1404   int bucket_count = 0;
1405   for (b = 0; b < map->max_buckets; b++) {
1406     if (map->buckets[b] == 0)
1407       continue;
1408     sum_bucket_size += map->buckets[b]->size;
1409     bucket_count++;
1410   }
1411   dprintk("sum_bucket_size %d max_buckets %d bucket_count %d\n",
1412           sum_bucket_size, map->max_buckets, bucket_count);
1413   int size = (sizeof(struct crush_choose_arg) * map->max_buckets +
1414               sizeof(struct crush_weight_set) * bucket_count * num_positions +
1415               sizeof(__u32) * sum_bucket_size * num_positions + // weights
1416               sizeof(__s32) * sum_bucket_size); // ids
1417   char *space = malloc(size);
1418   struct crush_choose_arg *arg = (struct crush_choose_arg *)space;
1419   struct crush_weight_set *weight_set = (struct crush_weight_set *)(arg + map->max_buckets);
1420   __u32 *weights = (__u32 *)(weight_set + bucket_count * num_positions);
1421   char *weight_set_ends = (char*)weights;
1422   __s32 *ids = (__s32 *)(weights + sum_bucket_size * num_positions);
1423   char *weights_end = (char *)ids;
1424   char *ids_end = (char *)(ids + sum_bucket_size);
1425   BUG_ON(space + size != ids_end);
1426   for (b = 0; b < map->max_buckets; b++) {
1427     if (map->buckets[b] == 0) {
1428       memset(&arg[b], '\0', sizeof(struct crush_choose_arg));
1429       continue;
1430     }
1431     struct crush_bucket_straw2 *bucket = (struct crush_bucket_straw2 *)map->buckets[b];
1432
1433     int position;
1434     for (position = 0; position < num_positions; position++) {
1435       memcpy(weights, bucket->item_weights, sizeof(__u32) * bucket->h.size);
1436       weight_set[position].weights = weights;
1437       weight_set[position].size = bucket->h.size;
1438       dprintk("moving weight %d bytes forward\n", (int)((weights + bucket->h.size) - weights));
1439       weights += bucket->h.size;
1440     }
1441     arg[b].weight_set = weight_set;
1442     arg[b].weight_set_size = num_positions;
1443     weight_set += position;
1444
1445     memcpy(ids, bucket->h.items, sizeof(__s32) * bucket->h.size);
1446     arg[b].ids = ids;
1447     arg[b].ids_size = bucket->h.size;
1448     ids += bucket->h.size;
1449   }
1450   BUG_ON((char*)weight_set_ends != (char*)weight_set);
1451   BUG_ON((char*)weights_end != (char*)weights);
1452   BUG_ON((char*)ids != (char*)ids_end);
1453   return arg;
1454 }
1455
1456 void crush_destroy_choose_args(struct crush_choose_arg *args)
1457 {
1458   free(args);
1459 }
1460
1461 /***************************/
1462
1463 /* methods to check for safe arithmetic operations */
1464
1465 int crush_addition_is_unsafe(__u32 a, __u32 b)
1466 {
1467         if ((((__u32)(-1)) - b) < a)
1468                 return 1;
1469         else
1470                 return 0;
1471 }
1472
1473 int crush_multiplication_is_unsafe(__u32  a, __u32 b)
1474 {
1475         /* prevent division by zero */
1476         if (!a)
1477                 return 0;
1478         if (!b)
1479                 return 1;
1480         if ((((__u32)(-1)) / b) < a)
1481                 return 1;
1482         else
1483                 return 0;
1484 }
1485
1486 /***************************/
1487
1488 /* methods to configure crush_map */
1489
1490 void set_legacy_crush_map(struct crush_map *map) {
1491   /* initialize legacy tunable values */
1492   map->choose_local_tries = 2;
1493   map->choose_local_fallback_tries = 5;
1494   map->choose_total_tries = 19;
1495   map->chooseleaf_descend_once = 0;
1496   map->chooseleaf_vary_r = 0;
1497   map->chooseleaf_stable = 0;
1498   map->straw_calc_version = 0;
1499
1500   // by default, use legacy types, and also exclude tree,
1501   // since it was buggy.
1502   map->allowed_bucket_algs = CRUSH_LEGACY_ALLOWED_BUCKET_ALGS;
1503 }
1504
1505 void set_optimal_crush_map(struct crush_map *map) {
1506   map->choose_local_tries = 0;
1507   map->choose_local_fallback_tries = 0;
1508   map->choose_total_tries = 50;
1509   map->chooseleaf_descend_once = 1;
1510   map->chooseleaf_vary_r = 1;
1511   map->chooseleaf_stable = 1;
1512   map->allowed_bucket_algs = (
1513     (1 << CRUSH_BUCKET_UNIFORM) |
1514     (1 << CRUSH_BUCKET_LIST) |
1515     (1 << CRUSH_BUCKET_STRAW) |
1516     (1 << CRUSH_BUCKET_STRAW2));
1517 }