+++ /dev/null
-#include <string.h>
-#include <math.h>
-#include <stdlib.h>
-#include <stdio.h>
-#include <assert.h>
-#include <errno.h>
-
-#include "crush/crush.h"
-#include "builder.h"
-
-#define dprintk(args...) /* printf(args) */
-
-#define BUG_ON(x) assert(!(x))
-
-struct crush_map *crush_create()
-{
- struct crush_map *m;
- m = malloc(sizeof(*m));
- if (!m)
- return NULL;
- memset(m, 0, sizeof(*m));
-
- set_optimal_crush_map(m);
- return m;
-}
-
-/*
- * finalize should be called _after_ all buckets are added to the map.
- */
-void crush_finalize(struct crush_map *map)
-{
- int b;
- __u32 i;
-
- /* Calculate the needed working space while we do other
- finalization tasks. */
- map->working_size = sizeof(struct crush_work);
- /* Space for the array of pointers to per-bucket workspace */
- map->working_size += map->max_buckets *
- sizeof(struct crush_work_bucket *);
-
- /* calc max_devices */
- map->max_devices = 0;
- for (b=0; b<map->max_buckets; b++) {
- if (map->buckets[b] == 0)
- continue;
- for (i=0; i<map->buckets[b]->size; i++)
- if (map->buckets[b]->items[i] >= map->max_devices)
- map->max_devices = map->buckets[b]->items[i] + 1;
-
- switch (map->buckets[b]->alg) {
- default:
- /* The base case, permutation variables and
- the pointer to the permutation array. */
- map->working_size += sizeof(struct crush_work_bucket);
- break;
- }
- /* Every bucket has a permutation array. */
- map->working_size += map->buckets[b]->size * sizeof(__u32);
- }
-}
-
-
-
-/** rules **/
-
-int crush_add_rule(struct crush_map *map, struct crush_rule *rule, int ruleno)
-{
- __u32 r;
-
- if (ruleno < 0) {
- for (r=0; r < map->max_rules; r++)
- if (map->rules[r] == 0)
- break;
- assert(r < CRUSH_MAX_RULES);
- }
- else
- r = ruleno;
-
- if (r >= map->max_rules) {
- /* expand array */
- int oldsize;
- void *_realloc = NULL;
- if (map->max_rules +1 > CRUSH_MAX_RULES)
- return -ENOSPC;
- oldsize = map->max_rules;
- map->max_rules = r+1;
- if ((_realloc = realloc(map->rules, map->max_rules * sizeof(map->rules[0]))) == NULL) {
- return -ENOMEM;
- } else {
- map->rules = _realloc;
- }
- memset(map->rules + oldsize, 0, (map->max_rules-oldsize) * sizeof(map->rules[0]));
- }
-
- /* add it */
- map->rules[r] = rule;
- return r;
-}
-
-struct crush_rule *crush_make_rule(int len, int ruleset, int type, int minsize, int maxsize)
-{
- struct crush_rule *rule;
- rule = malloc(crush_rule_size(len));
- if (!rule)
- return NULL;
- rule->len = len;
- rule->mask.ruleset = ruleset;
- rule->mask.type = type;
- rule->mask.min_size = minsize;
- rule->mask.max_size = maxsize;
- return rule;
-}
-
-/*
- * be careful; this doesn't verify that the buffer you allocated is big enough!
- */
-void crush_rule_set_step(struct crush_rule *rule, int n, int op, int arg1, int arg2)
-{
- assert((__u32)n < rule->len);
- rule->steps[n].op = op;
- rule->steps[n].arg1 = arg1;
- rule->steps[n].arg2 = arg2;
-}
-
-
-/** buckets **/
-int crush_get_next_bucket_id(struct crush_map *map)
-{
- int pos;
- for (pos=0; pos < map->max_buckets; pos++)
- if (map->buckets[pos] == 0)
- break;
- return -1 - pos;
-}
-
-
-int crush_add_bucket(struct crush_map *map,
- int id,
- struct crush_bucket *bucket,
- int *idout)
-{
- int pos;
-
- /* find a bucket id */
- if (id == 0)
- id = crush_get_next_bucket_id(map);
- pos = -1 - id;
-
- while (pos >= map->max_buckets) {
- /* expand array */
- int oldsize = map->max_buckets;
- if (map->max_buckets)
- map->max_buckets *= 2;
- else
- map->max_buckets = 8;
- void *_realloc = NULL;
- if ((_realloc = realloc(map->buckets, map->max_buckets * sizeof(map->buckets[0]))) == NULL) {
- return -ENOMEM;
- } else {
- map->buckets = _realloc;
- }
- memset(map->buckets + oldsize, 0, (map->max_buckets-oldsize) * sizeof(map->buckets[0]));
- }
-
- if (map->buckets[pos] != 0) {
- return -EEXIST;
- }
-
- /* add it */
- bucket->id = id;
- map->buckets[pos] = bucket;
-
- if (idout) *idout = id;
- return 0;
-}
-
-int crush_remove_bucket(struct crush_map *map, struct crush_bucket *bucket)
-{
- int pos = -1 - bucket->id;
- assert(pos < map->max_buckets);
- map->buckets[pos] = NULL;
- crush_destroy_bucket(bucket);
- return 0;
-}
-
-
-/* uniform bucket */
-
-struct crush_bucket_uniform *
-crush_make_uniform_bucket(int hash, int type, int size,
- int *items,
- int item_weight)
-{
- int i;
- struct crush_bucket_uniform *bucket;
-
- bucket = malloc(sizeof(*bucket));
- if (!bucket)
- return NULL;
- memset(bucket, 0, sizeof(*bucket));
- bucket->h.alg = CRUSH_BUCKET_UNIFORM;
- bucket->h.hash = hash;
- bucket->h.type = type;
- bucket->h.size = size;
-
- if (crush_multiplication_is_unsafe(size, item_weight))
- goto err;
-
- bucket->h.weight = size * item_weight;
- bucket->item_weight = item_weight;
- bucket->h.items = malloc(sizeof(__s32)*size);
-
- if (!bucket->h.items)
- goto err;
-
- for (i=0; i<size; i++)
- bucket->h.items[i] = items[i];
-
- return bucket;
-err:
- free(bucket->h.items);
- free(bucket);
- return NULL;
-}
-
-
-/* list bucket */
-
-struct crush_bucket_list*
-crush_make_list_bucket(int hash, int type, int size,
- int *items,
- int *weights)
-{
- int i;
- int w;
- struct crush_bucket_list *bucket;
-
- bucket = malloc(sizeof(*bucket));
- if (!bucket)
- return NULL;
- memset(bucket, 0, sizeof(*bucket));
- bucket->h.alg = CRUSH_BUCKET_LIST;
- bucket->h.hash = hash;
- bucket->h.type = type;
- bucket->h.size = size;
-
- bucket->h.items = malloc(sizeof(__s32)*size);
- if (!bucket->h.items)
- goto err;
-
-
- bucket->item_weights = malloc(sizeof(__u32)*size);
- if (!bucket->item_weights)
- goto err;
- bucket->sum_weights = malloc(sizeof(__u32)*size);
- if (!bucket->sum_weights)
- goto err;
- w = 0;
- for (i=0; i<size; i++) {
- bucket->h.items[i] = items[i];
- bucket->item_weights[i] = weights[i];
-
- if (crush_addition_is_unsafe(w, weights[i]))
- goto err;
-
- w += weights[i];
- bucket->sum_weights[i] = w;
- /*dprintk("pos %d item %d weight %d sum %d\n",
- i, items[i], weights[i], bucket->sum_weights[i]);*/
- }
-
- bucket->h.weight = w;
-
- return bucket;
-err:
- free(bucket->sum_weights);
- free(bucket->item_weights);
- free(bucket->h.items);
- free(bucket);
- return NULL;
-}
-
-
-/* tree bucket */
-
-static int height(int n) {
- int h = 0;
- while ((n & 1) == 0) {
- h++;
- n = n >> 1;
- }
- return h;
-}
-static int on_right(int n, int h) {
- return n & (1 << (h+1));
-}
-static int parent(int n)
-{
- int h = height(n);
- if (on_right(n, h))
- return n - (1<<h);
- else
- return n + (1<<h);
-}
-
-static int calc_depth(int size)
-{
- if (size == 0) {
- return 0;
- }
-
- int depth = 1;
- int t = size - 1;
- while (t) {
- t = t >> 1;
- depth++;
- }
- return depth;
-}
-
-struct crush_bucket_tree*
-crush_make_tree_bucket(int hash, int type, int size,
- int *items, /* in leaf order */
- int *weights)
-{
- struct crush_bucket_tree *bucket;
- int depth;
- int node;
- int i, j;
-
- bucket = malloc(sizeof(*bucket));
- if (!bucket)
- return NULL;
- memset(bucket, 0, sizeof(*bucket));
- bucket->h.alg = CRUSH_BUCKET_TREE;
- bucket->h.hash = hash;
- bucket->h.type = type;
- bucket->h.size = size;
-
- if (size == 0) {
- bucket->h.items = NULL;
- bucket->h.weight = 0;
- bucket->node_weights = NULL;
- bucket->num_nodes = 0;
- /* printf("size 0 depth 0 nodes 0\n"); */
- return bucket;
- }
-
- bucket->h.items = malloc(sizeof(__s32)*size);
- if (!bucket->h.items)
- goto err;
-
- /* calc tree depth */
- depth = calc_depth(size);
- bucket->num_nodes = 1 << depth;
- dprintk("size %d depth %d nodes %d\n", size, depth, bucket->num_nodes);
-
- bucket->node_weights = malloc(sizeof(__u32)*bucket->num_nodes);
- if (!bucket->node_weights)
- goto err;
-
- memset(bucket->h.items, 0, sizeof(__s32)*bucket->h.size);
- memset(bucket->node_weights, 0, sizeof(__u32)*bucket->num_nodes);
-
- for (i=0; i<size; i++) {
- bucket->h.items[i] = items[i];
- node = crush_calc_tree_node(i);
- dprintk("item %d node %d weight %d\n", i, node, weights[i]);
- bucket->node_weights[node] = weights[i];
-
- if (crush_addition_is_unsafe(bucket->h.weight, weights[i]))
- goto err;
-
- bucket->h.weight += weights[i];
- for (j=1; j<depth; j++) {
- node = parent(node);
-
- if (crush_addition_is_unsafe(bucket->node_weights[node], weights[i]))
- goto err;
-
- bucket->node_weights[node] += weights[i];
- dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
- }
- }
- BUG_ON(bucket->node_weights[bucket->num_nodes/2] != bucket->h.weight);
-
- return bucket;
-err:
- free(bucket->node_weights);
- free(bucket->h.items);
- free(bucket);
- return NULL;
-}
-
-
-
-/* straw bucket */
-
-/*
- * this code was written 8 years ago. i have a vague recollection of
- * drawing boxes underneath bars of different lengths, where the bar
- * length represented the probability/weight, and that there was some
- * trial and error involved in arriving at this implementation.
- * however, reading the code now after all this time, the intuition
- * that motivated is lost on me. lame. my only excuse is that I now
- * know that the approach is fundamentally flawed and am not
- * particularly motivated to reconstruct the flawed reasoning.
- *
- * as best as i can remember, the idea is: sort the weights, and start
- * with the smallest. arbitrarily scale it at 1.0 (16-bit fixed
- * point). look at the next larger weight, and calculate the scaling
- * factor for that straw based on the relative difference in weight so
- * far. what's not clear to me now is why we are looking at wnext
- * (the delta to the next bigger weight) for all remaining weights,
- * and slicing things horizontally instead of considering just the
- * next item or set of items. or why pow() is used the way it is.
- *
- * note that the original version 1 of this function made special
- * accomodation for the case where straw lengths were identical. this
- * is also flawed in a non-obvious way; version 2 drops the special
- * handling and appears to work just as well.
- *
- * moral of the story: if you do something clever, write down why it
- * works.
- */
-int crush_calc_straw(struct crush_map *map, struct crush_bucket_straw *bucket)
-{
- int *reverse;
- int i, j, k;
- double straw, wbelow, lastw, wnext, pbelow;
- int numleft;
- int size = bucket->h.size;
- __u32 *weights = bucket->item_weights;
-
- /* reverse sort by weight (simple insertion sort) */
- reverse = malloc(sizeof(int) * size);
- if (!reverse)
- return -ENOMEM;
- if (size)
- reverse[0] = 0;
- for (i=1; i<size; i++) {
- for (j=0; j<i; j++) {
- if (weights[i] < weights[reverse[j]]) {
- /* insert here */
- for (k=i; k>j; k--)
- reverse[k] = reverse[k-1];
- reverse[j] = i;
- break;
- }
- }
- if (j == i)
- reverse[i] = i;
- }
-
- numleft = size;
- straw = 1.0;
- wbelow = 0;
- lastw = 0;
-
- i=0;
- while (i < size) {
- if (map->straw_calc_version == 0) {
- /* zero weight items get 0 length straws! */
- if (weights[reverse[i]] == 0) {
- bucket->straws[reverse[i]] = 0;
- i++;
- continue;
- }
-
- /* set this item's straw */
- bucket->straws[reverse[i]] = straw * 0x10000;
- dprintk("item %d at %d weight %d straw %d (%lf)\n",
- bucket->h.items[reverse[i]],
- reverse[i], weights[reverse[i]],
- bucket->straws[reverse[i]], straw);
- i++;
- if (i == size)
- break;
-
- /* same weight as previous? */
- if (weights[reverse[i]] == weights[reverse[i-1]]) {
- dprintk("same as previous\n");
- continue;
- }
-
- /* adjust straw for next guy */
- wbelow += ((double)weights[reverse[i-1]] - lastw) *
- numleft;
- for (j=i; j<size; j++)
- if (weights[reverse[j]] == weights[reverse[i]])
- numleft--;
- else
- break;
- wnext = numleft * (weights[reverse[i]] -
- weights[reverse[i-1]]);
- pbelow = wbelow / (wbelow + wnext);
- dprintk("wbelow %lf wnext %lf pbelow %lf numleft %d\n",
- wbelow, wnext, pbelow, numleft);
-
- straw *= pow((double)1.0 / pbelow, (double)1.0 /
- (double)numleft);
-
- lastw = weights[reverse[i-1]];
- } else if (map->straw_calc_version >= 1) {
- /* zero weight items get 0 length straws! */
- if (weights[reverse[i]] == 0) {
- bucket->straws[reverse[i]] = 0;
- i++;
- numleft--;
- continue;
- }
-
- /* set this item's straw */
- bucket->straws[reverse[i]] = straw * 0x10000;
- dprintk("item %d at %d weight %d straw %d (%lf)\n",
- bucket->h.items[reverse[i]],
- reverse[i], weights[reverse[i]],
- bucket->straws[reverse[i]], straw);
- i++;
- if (i == size)
- break;
-
- /* adjust straw for next guy */
- wbelow += ((double)weights[reverse[i-1]] - lastw) *
- numleft;
- numleft--;
- wnext = numleft * (weights[reverse[i]] -
- weights[reverse[i-1]]);
- pbelow = wbelow / (wbelow + wnext);
- dprintk("wbelow %lf wnext %lf pbelow %lf numleft %d\n",
- wbelow, wnext, pbelow, numleft);
-
- straw *= pow((double)1.0 / pbelow, (double)1.0 /
- (double)numleft);
-
- lastw = weights[reverse[i-1]];
- }
- }
-
- free(reverse);
- return 0;
-}
-
-struct crush_bucket_straw *
-crush_make_straw_bucket(struct crush_map *map,
- int hash,
- int type,
- int size,
- int *items,
- int *weights)
-{
- struct crush_bucket_straw *bucket;
- int i;
-
- bucket = malloc(sizeof(*bucket));
- if (!bucket)
- return NULL;
- memset(bucket, 0, sizeof(*bucket));
- bucket->h.alg = CRUSH_BUCKET_STRAW;
- bucket->h.hash = hash;
- bucket->h.type = type;
- bucket->h.size = size;
-
- bucket->h.items = malloc(sizeof(__s32)*size);
- if (!bucket->h.items)
- goto err;
- bucket->item_weights = malloc(sizeof(__u32)*size);
- if (!bucket->item_weights)
- goto err;
- bucket->straws = malloc(sizeof(__u32)*size);
- if (!bucket->straws)
- goto err;
-
- bucket->h.weight = 0;
- for (i=0; i<size; i++) {
- bucket->h.items[i] = items[i];
- bucket->h.weight += weights[i];
- bucket->item_weights[i] = weights[i];
- }
-
- if (crush_calc_straw(map, bucket) < 0)
- goto err;
-
- return bucket;
-err:
- free(bucket->straws);
- free(bucket->item_weights);
- free(bucket->h.items);
- free(bucket);
- return NULL;
-}
-
-struct crush_bucket_straw2 *
-crush_make_straw2_bucket(struct crush_map *map,
- int hash,
- int type,
- int size,
- int *items,
- int *weights)
-{
- struct crush_bucket_straw2 *bucket;
- int i;
-
- bucket = malloc(sizeof(*bucket));
- if (!bucket)
- return NULL;
- memset(bucket, 0, sizeof(*bucket));
- bucket->h.alg = CRUSH_BUCKET_STRAW2;
- bucket->h.hash = hash;
- bucket->h.type = type;
- bucket->h.size = size;
-
- bucket->h.items = malloc(sizeof(__s32)*size);
- if (!bucket->h.items)
- goto err;
- bucket->item_weights = malloc(sizeof(__u32)*size);
- if (!bucket->item_weights)
- goto err;
-
- bucket->h.weight = 0;
- for (i=0; i<size; i++) {
- bucket->h.items[i] = items[i];
- bucket->h.weight += weights[i];
- bucket->item_weights[i] = weights[i];
- }
-
- return bucket;
-err:
- free(bucket->item_weights);
- free(bucket->h.items);
- free(bucket);
- return NULL;
-}
-
-
-
-struct crush_bucket*
-crush_make_bucket(struct crush_map *map,
- int alg, int hash, int type, int size,
- int *items,
- int *weights)
-{
- int item_weight;
-
- switch (alg) {
- case CRUSH_BUCKET_UNIFORM:
- if (size && weights)
- item_weight = weights[0];
- else
- item_weight = 0;
- return (struct crush_bucket *)crush_make_uniform_bucket(hash, type, size, items, item_weight);
-
- case CRUSH_BUCKET_LIST:
- return (struct crush_bucket *)crush_make_list_bucket(hash, type, size, items, weights);
-
- case CRUSH_BUCKET_TREE:
- return (struct crush_bucket *)crush_make_tree_bucket(hash, type, size, items, weights);
-
- case CRUSH_BUCKET_STRAW:
- return (struct crush_bucket *)crush_make_straw_bucket(map, hash, type, size, items, weights);
- case CRUSH_BUCKET_STRAW2:
- return (struct crush_bucket *)crush_make_straw2_bucket(map, hash, type, size, items, weights);
- }
- return 0;
-}
-
-
-/************************************************/
-
-int crush_add_uniform_bucket_item(struct crush_bucket_uniform *bucket, int item, int weight)
-{
- int newsize = bucket->h.size + 1;
- void *_realloc = NULL;
-
- /* In such situation 'CRUSH_BUCKET_UNIFORM', the weight
- provided for the item should be the same as
- bucket->item_weight defined with 'crush_make_bucket'. This
- assumption is enforced by the return value which is always
- 0. */
- if (bucket->item_weight != weight) {
- return -EINVAL;
- }
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
-
- bucket->h.items[newsize-1] = item;
-
- if (crush_addition_is_unsafe(bucket->h.weight, weight))
- return -ERANGE;
-
- bucket->h.weight += weight;
- bucket->h.size++;
-
- return 0;
-}
-
-int crush_add_list_bucket_item(struct crush_bucket_list *bucket, int item, int weight)
-{
- int newsize = bucket->h.size + 1;
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
- if ((_realloc = realloc(bucket->sum_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->sum_weights = _realloc;
- }
-
- bucket->h.items[newsize-1] = item;
- bucket->item_weights[newsize-1] = weight;
- if (newsize > 1) {
-
- if (crush_addition_is_unsafe(bucket->sum_weights[newsize-2], weight))
- return -ERANGE;
-
- bucket->sum_weights[newsize-1] = bucket->sum_weights[newsize-2] + weight;
- }
-
- else {
- bucket->sum_weights[newsize-1] = weight;
- }
-
- bucket->h.weight += weight;
- bucket->h.size++;
- return 0;
-}
-
-int crush_add_tree_bucket_item(struct crush_bucket_tree *bucket, int item, int weight)
-{
- int newsize = bucket->h.size + 1;
- int depth = calc_depth(newsize);;
- int node;
- int j;
- void *_realloc = NULL;
-
- bucket->num_nodes = 1 << depth;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->node_weights, sizeof(__u32)*bucket->num_nodes)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->node_weights = _realloc;
- }
-
- node = crush_calc_tree_node(newsize-1);
- bucket->node_weights[node] = weight;
-
- /* if the depth increase, we need to initialize the new root node's weight before add bucket item */
- int root = bucket->num_nodes/2;
- if (depth >= 2 && (node - 1) == root) {
- /* if the new item is the first node in right sub tree, so
- * the root node initial weight is left sub tree's weight
- */
- bucket->node_weights[root] = bucket->node_weights[root/2];
- }
-
- for (j=1; j<depth; j++) {
- node = parent(node);
-
- if (crush_addition_is_unsafe(bucket->node_weights[node], weight))
- return -ERANGE;
-
- bucket->node_weights[node] += weight;
- dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
- }
-
-
- if (crush_addition_is_unsafe(bucket->h.weight, weight))
- return -ERANGE;
-
- bucket->h.items[newsize-1] = item;
- bucket->h.weight += weight;
- bucket->h.size++;
-
- return 0;
-}
-
-int crush_add_straw_bucket_item(struct crush_map *map,
- struct crush_bucket_straw *bucket,
- int item, int weight)
-{
- int newsize = bucket->h.size + 1;
-
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
- if ((_realloc = realloc(bucket->straws, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->straws = _realloc;
- }
-
- bucket->h.items[newsize-1] = item;
- bucket->item_weights[newsize-1] = weight;
-
- if (crush_addition_is_unsafe(bucket->h.weight, weight))
- return -ERANGE;
-
- bucket->h.weight += weight;
- bucket->h.size++;
-
- return crush_calc_straw(map, bucket);
-}
-
-int crush_add_straw2_bucket_item(struct crush_map *map,
- struct crush_bucket_straw2 *bucket,
- int item, int weight)
-{
- int newsize = bucket->h.size + 1;
-
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
-
- bucket->h.items[newsize-1] = item;
- bucket->item_weights[newsize-1] = weight;
-
- if (crush_addition_is_unsafe(bucket->h.weight, weight))
- return -ERANGE;
-
- bucket->h.weight += weight;
- bucket->h.size++;
-
- return 0;
-}
-
-int crush_bucket_add_item(struct crush_map *map,
- struct crush_bucket *b, int item, int weight)
-{
- switch (b->alg) {
- case CRUSH_BUCKET_UNIFORM:
- return crush_add_uniform_bucket_item((struct crush_bucket_uniform *)b, item, weight);
- case CRUSH_BUCKET_LIST:
- return crush_add_list_bucket_item((struct crush_bucket_list *)b, item, weight);
- case CRUSH_BUCKET_TREE:
- return crush_add_tree_bucket_item((struct crush_bucket_tree *)b, item, weight);
- case CRUSH_BUCKET_STRAW:
- return crush_add_straw_bucket_item(map, (struct crush_bucket_straw *)b, item, weight);
- case CRUSH_BUCKET_STRAW2:
- return crush_add_straw2_bucket_item(map, (struct crush_bucket_straw2 *)b, item, weight);
- default:
- return -1;
- }
-}
-
-/************************************************/
-
-int crush_remove_uniform_bucket_item(struct crush_bucket_uniform *bucket, int item)
-{
- unsigned i, j;
- int newsize;
- void *_realloc = NULL;
-
- for (i = 0; i < bucket->h.size; i++)
- if (bucket->h.items[i] == item)
- break;
- if (i == bucket->h.size)
- return -ENOENT;
-
- for (j = i; j < bucket->h.size; j++)
- bucket->h.items[j] = bucket->h.items[j+1];
- newsize = --bucket->h.size;
- if (bucket->item_weight < bucket->h.weight)
- bucket->h.weight -= bucket->item_weight;
- else
- bucket->h.weight = 0;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- return 0;
-}
-
-int crush_remove_list_bucket_item(struct crush_bucket_list *bucket, int item)
-{
- unsigned i, j;
- int newsize;
- unsigned weight;
-
- for (i = 0; i < bucket->h.size; i++)
- if (bucket->h.items[i] == item)
- break;
- if (i == bucket->h.size)
- return -ENOENT;
-
- weight = bucket->item_weights[i];
- for (j = i; j < bucket->h.size; j++) {
- bucket->h.items[j] = bucket->h.items[j+1];
- bucket->item_weights[j] = bucket->item_weights[j+1];
- bucket->sum_weights[j] = bucket->sum_weights[j+1] - weight;
- }
- if (weight < bucket->h.weight)
- bucket->h.weight -= weight;
- else
- bucket->h.weight = 0;
- newsize = --bucket->h.size;
-
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
- if ((_realloc = realloc(bucket->sum_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->sum_weights = _realloc;
- }
- return 0;
-}
-
-int crush_remove_tree_bucket_item(struct crush_bucket_tree *bucket, int item)
-{
- unsigned i;
- unsigned newsize;
-
- for (i = 0; i < bucket->h.size; i++) {
- int node;
- unsigned weight;
- int j;
- int depth = calc_depth(bucket->h.size);
-
- if (bucket->h.items[i] != item)
- continue;
-
- bucket->h.items[i] = 0;
- node = crush_calc_tree_node(i);
- weight = bucket->node_weights[node];
- bucket->node_weights[node] = 0;
-
- for (j = 1; j < depth; j++) {
- node = parent(node);
- bucket->node_weights[node] -= weight;
- dprintk(" node %d weight %d\n", node, bucket->node_weights[node]);
- }
- if (weight < bucket->h.weight)
- bucket->h.weight -= weight;
- else
- bucket->h.weight = 0;
- break;
- }
- if (i == bucket->h.size)
- return -ENOENT;
-
- newsize = bucket->h.size;
- while (newsize > 0) {
- int node = crush_calc_tree_node(newsize - 1);
- if (bucket->node_weights[node])
- break;
- --newsize;
- }
-
- if (newsize != bucket->h.size) {
- int olddepth, newdepth;
-
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
-
- olddepth = calc_depth(bucket->h.size);
- newdepth = calc_depth(newsize);
- if (olddepth != newdepth) {
- bucket->num_nodes = 1 << newdepth;
- if ((_realloc = realloc(bucket->node_weights,
- sizeof(__u32)*bucket->num_nodes)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->node_weights = _realloc;
- }
- }
-
- bucket->h.size = newsize;
- }
- return 0;
-}
-
-int crush_remove_straw_bucket_item(struct crush_map *map,
- struct crush_bucket_straw *bucket, int item)
-{
- int newsize = bucket->h.size - 1;
- unsigned i, j;
-
- for (i = 0; i < bucket->h.size; i++) {
- if (bucket->h.items[i] == item) {
- if (bucket->item_weights[i] < bucket->h.weight)
- bucket->h.weight -= bucket->item_weights[i];
- else
- bucket->h.weight = 0;
- for (j = i; j < bucket->h.size - 1; j++) {
- bucket->h.items[j] = bucket->h.items[j+1];
- bucket->item_weights[j] = bucket->item_weights[j+1];
- }
- break;
- }
- }
- if (i == bucket->h.size)
- return -ENOENT;
- bucket->h.size--;
- if (bucket->h.size == 0) {
- /* don't bother reallocating */
- return 0;
- }
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
- if ((_realloc = realloc(bucket->straws, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->straws = _realloc;
- }
-
- return crush_calc_straw(map, bucket);
-}
-
-int crush_remove_straw2_bucket_item(struct crush_map *map,
- struct crush_bucket_straw2 *bucket, int item)
-{
- int newsize = bucket->h.size - 1;
- unsigned i, j;
-
- for (i = 0; i < bucket->h.size; i++) {
- if (bucket->h.items[i] == item) {
- if (bucket->item_weights[i] < bucket->h.weight)
- bucket->h.weight -= bucket->item_weights[i];
- else
- bucket->h.weight = 0;
- for (j = i; j < bucket->h.size - 1; j++) {
- bucket->h.items[j] = bucket->h.items[j+1];
- bucket->item_weights[j] = bucket->item_weights[j+1];
- }
- break;
- }
- }
- if (i == bucket->h.size)
- return -ENOENT;
-
- bucket->h.size--;
- if (!newsize) {
- /* don't bother reallocating a 0-length array. */
- return 0;
- }
-
- void *_realloc = NULL;
-
- if ((_realloc = realloc(bucket->h.items, sizeof(__s32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->h.items = _realloc;
- }
- if ((_realloc = realloc(bucket->item_weights, sizeof(__u32)*newsize)) == NULL) {
- return -ENOMEM;
- } else {
- bucket->item_weights = _realloc;
- }
-
- return 0;
-}
-
-int crush_bucket_remove_item(struct crush_map *map, struct crush_bucket *b, int item)
-{
- switch (b->alg) {
- case CRUSH_BUCKET_UNIFORM:
- return crush_remove_uniform_bucket_item((struct crush_bucket_uniform *)b, item);
- case CRUSH_BUCKET_LIST:
- return crush_remove_list_bucket_item((struct crush_bucket_list *)b, item);
- case CRUSH_BUCKET_TREE:
- return crush_remove_tree_bucket_item((struct crush_bucket_tree *)b, item);
- case CRUSH_BUCKET_STRAW:
- return crush_remove_straw_bucket_item(map, (struct crush_bucket_straw *)b, item);
- case CRUSH_BUCKET_STRAW2:
- return crush_remove_straw2_bucket_item(map, (struct crush_bucket_straw2 *)b, item);
- default:
- return -1;
- }
-}
-
-
-/************************************************/
-
-int crush_adjust_uniform_bucket_item_weight(struct crush_bucket_uniform *bucket, int item, int weight)
-{
- int diff = (weight - bucket->item_weight) * bucket->h.size;
-
- bucket->item_weight = weight;
- bucket->h.weight = bucket->item_weight * bucket->h.size;
-
- return diff;
-}
-
-int crush_adjust_list_bucket_item_weight(struct crush_bucket_list *bucket, int item, int weight)
-{
- int diff;
- unsigned i, j;
-
- for (i = 0; i < bucket->h.size; i++) {
- if (bucket->h.items[i] == item)
- break;
- }
- if (i == bucket->h.size)
- return 0;
-
- diff = weight - bucket->item_weights[i];
- bucket->item_weights[i] = weight;
- bucket->h.weight += diff;
-
- for (j = i; j < bucket->h.size; j++)
- bucket->sum_weights[j] += diff;
-
- return diff;
-}
-
-int crush_adjust_tree_bucket_item_weight(struct crush_bucket_tree *bucket, int item, int weight)
-{
- int diff;
- int node;
- unsigned i, j;
- unsigned depth = calc_depth(bucket->h.size);
-
- for (i = 0; i < bucket->h.size; i++) {
- if (bucket->h.items[i] == item)
- break;
- }
- if (i == bucket->h.size)
- return 0;
-
- node = crush_calc_tree_node(i);
- diff = weight - bucket->node_weights[node];
- bucket->node_weights[node] = weight;
- bucket->h.weight += diff;
-
- for (j=1; j<depth; j++) {
- node = parent(node);
- bucket->node_weights[node] += diff;
- }
-
- return diff;
-}
-
-int crush_adjust_straw_bucket_item_weight(struct crush_map *map,
- struct crush_bucket_straw *bucket,
- int item, int weight)
-{
- unsigned idx;
- int diff;
- int r;
-
- for (idx = 0; idx < bucket->h.size; idx++)
- if (bucket->h.items[idx] == item)
- break;
- if (idx == bucket->h.size)
- return 0;
-
- diff = weight - bucket->item_weights[idx];
- bucket->item_weights[idx] = weight;
- bucket->h.weight += diff;
-
- r = crush_calc_straw(map, bucket);
- if (r < 0)
- return r;
-
- return diff;
-}
-
-int crush_adjust_straw2_bucket_item_weight(struct crush_map *map,
- struct crush_bucket_straw2 *bucket,
- int item, int weight)
-{
- unsigned idx;
- int diff;
-
- for (idx = 0; idx < bucket->h.size; idx++)
- if (bucket->h.items[idx] == item)
- break;
- if (idx == bucket->h.size)
- return 0;
-
- diff = weight - bucket->item_weights[idx];
- bucket->item_weights[idx] = weight;
- bucket->h.weight += diff;
-
- return diff;
-}
-
-int crush_bucket_adjust_item_weight(struct crush_map *map,
- struct crush_bucket *b,
- int item, int weight)
-{
- switch (b->alg) {
- case CRUSH_BUCKET_UNIFORM:
- return crush_adjust_uniform_bucket_item_weight((struct crush_bucket_uniform *)b,
- item, weight);
- case CRUSH_BUCKET_LIST:
- return crush_adjust_list_bucket_item_weight((struct crush_bucket_list *)b,
- item, weight);
- case CRUSH_BUCKET_TREE:
- return crush_adjust_tree_bucket_item_weight((struct crush_bucket_tree *)b,
- item, weight);
- case CRUSH_BUCKET_STRAW:
- return crush_adjust_straw_bucket_item_weight(map,
- (struct crush_bucket_straw *)b,
- item, weight);
- case CRUSH_BUCKET_STRAW2:
- return crush_adjust_straw2_bucket_item_weight(map,
- (struct crush_bucket_straw2 *)b,
- item, weight);
- default:
- return -1;
- }
-}
-
-/************************************************/
-
-static int crush_reweight_uniform_bucket(struct crush_map *map, struct crush_bucket_uniform *bucket)
-{
- unsigned i;
- unsigned sum = 0, n = 0, leaves = 0;
-
- for (i = 0; i < bucket->h.size; i++) {
- int id = bucket->h.items[i];
- if (id < 0) {
- struct crush_bucket *c = map->buckets[-1-id];
- crush_reweight_bucket(map, c);
-
- if (crush_addition_is_unsafe(sum, c->weight))
- return -ERANGE;
-
- sum += c->weight;
- n++;
- } else {
- leaves++;
- }
- }
-
- if (n > leaves)
- bucket->item_weight = sum / n; // more bucket children than leaves, average!
- bucket->h.weight = bucket->item_weight * bucket->h.size;
-
- return 0;
-}
-
-static int crush_reweight_list_bucket(struct crush_map *map, struct crush_bucket_list *bucket)
-{
- unsigned i;
-
- bucket->h.weight = 0;
- for (i = 0; i < bucket->h.size; i++) {
- int id = bucket->h.items[i];
- if (id < 0) {
- struct crush_bucket *c = map->buckets[-1-id];
- crush_reweight_bucket(map, c);
- bucket->item_weights[i] = c->weight;
- }
-
- if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
- return -ERANGE;
-
- bucket->h.weight += bucket->item_weights[i];
- }
-
- return 0;
-}
-
-static int crush_reweight_tree_bucket(struct crush_map *map, struct crush_bucket_tree *bucket)
-{
- unsigned i;
-
- bucket->h.weight = 0;
- for (i = 0; i < bucket->h.size; i++) {
- int node = crush_calc_tree_node(i);
- int id = bucket->h.items[i];
- if (id < 0) {
- struct crush_bucket *c = map->buckets[-1-id];
- crush_reweight_bucket(map, c);
- bucket->node_weights[node] = c->weight;
- }
-
- if (crush_addition_is_unsafe(bucket->h.weight, bucket->node_weights[node]))
- return -ERANGE;
-
- bucket->h.weight += bucket->node_weights[node];
-
-
- }
-
- return 0;
-}
-
-static int crush_reweight_straw_bucket(struct crush_map *map, struct crush_bucket_straw *bucket)
-{
- unsigned i;
-
- bucket->h.weight = 0;
- for (i = 0; i < bucket->h.size; i++) {
- int id = bucket->h.items[i];
- if (id < 0) {
- struct crush_bucket *c = map->buckets[-1-id];
- crush_reweight_bucket(map, c);
- bucket->item_weights[i] = c->weight;
- }
-
- if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
- return -ERANGE;
-
- bucket->h.weight += bucket->item_weights[i];
- }
- crush_calc_straw(map, bucket);
-
- return 0;
-}
-
-static int crush_reweight_straw2_bucket(struct crush_map *map, struct crush_bucket_straw2 *bucket)
-{
- unsigned i;
-
- bucket->h.weight = 0;
- for (i = 0; i < bucket->h.size; i++) {
- int id = bucket->h.items[i];
- if (id < 0) {
- struct crush_bucket *c = map->buckets[-1-id];
- crush_reweight_bucket(map, c);
- bucket->item_weights[i] = c->weight;
- }
-
- if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
- return -ERANGE;
-
- bucket->h.weight += bucket->item_weights[i];
- }
-
- return 0;
-}
-
-int crush_reweight_bucket(struct crush_map *map, struct crush_bucket *b)
-{
- switch (b->alg) {
- case CRUSH_BUCKET_UNIFORM:
- return crush_reweight_uniform_bucket(map, (struct crush_bucket_uniform *)b);
- case CRUSH_BUCKET_LIST:
- return crush_reweight_list_bucket(map, (struct crush_bucket_list *)b);
- case CRUSH_BUCKET_TREE:
- return crush_reweight_tree_bucket(map, (struct crush_bucket_tree *)b);
- case CRUSH_BUCKET_STRAW:
- return crush_reweight_straw_bucket(map, (struct crush_bucket_straw *)b);
- case CRUSH_BUCKET_STRAW2:
- return crush_reweight_straw2_bucket(map, (struct crush_bucket_straw2 *)b);
- default:
- return -1;
- }
-}
-
-struct crush_choose_arg *crush_make_choose_args(struct crush_map *map, int num_positions)
-{
- int b;
- int sum_bucket_size = 0;
- int bucket_count = 0;
- for (b = 0; b < map->max_buckets; b++) {
- if (map->buckets[b] == 0)
- continue;
- sum_bucket_size += map->buckets[b]->size;
- bucket_count++;
- }
- dprintk("sum_bucket_size %d max_buckets %d bucket_count %d\n",
- sum_bucket_size, map->max_buckets, bucket_count);
- int size = (sizeof(struct crush_choose_arg) * map->max_buckets +
- sizeof(struct crush_weight_set) * bucket_count * num_positions +
- sizeof(__u32) * sum_bucket_size * num_positions + // weights
- sizeof(__s32) * sum_bucket_size); // ids
- char *space = malloc(size);
- struct crush_choose_arg *arg = (struct crush_choose_arg *)space;
- struct crush_weight_set *weight_set = (struct crush_weight_set *)(arg + map->max_buckets);
- __u32 *weights = (__u32 *)(weight_set + bucket_count * num_positions);
- char *weight_set_ends = (char*)weights;
- __s32 *ids = (__s32 *)(weights + sum_bucket_size * num_positions);
- char *weights_end = (char *)ids;
- char *ids_end = (char *)(ids + sum_bucket_size);
- BUG_ON(space + size != ids_end);
- for (b = 0; b < map->max_buckets; b++) {
- if (map->buckets[b] == 0) {
- memset(&arg[b], '\0', sizeof(struct crush_choose_arg));
- continue;
- }
- struct crush_bucket_straw2 *bucket = (struct crush_bucket_straw2 *)map->buckets[b];
-
- int position;
- for (position = 0; position < num_positions; position++) {
- memcpy(weights, bucket->item_weights, sizeof(__u32) * bucket->h.size);
- weight_set[position].weights = weights;
- weight_set[position].size = bucket->h.size;
- dprintk("moving weight %d bytes forward\n", (int)((weights + bucket->h.size) - weights));
- weights += bucket->h.size;
- }
- arg[b].weight_set = weight_set;
- arg[b].weight_set_size = num_positions;
- weight_set += position;
-
- memcpy(ids, bucket->h.items, sizeof(__s32) * bucket->h.size);
- arg[b].ids = ids;
- arg[b].ids_size = bucket->h.size;
- ids += bucket->h.size;
- }
- BUG_ON((char*)weight_set_ends != (char*)weight_set);
- BUG_ON((char*)weights_end != (char*)weights);
- BUG_ON((char*)ids != (char*)ids_end);
- return arg;
-}
-
-void crush_destroy_choose_args(struct crush_choose_arg *args)
-{
- free(args);
-}
-
-/***************************/
-
-/* methods to check for safe arithmetic operations */
-
-int crush_addition_is_unsafe(__u32 a, __u32 b)
-{
- if ((((__u32)(-1)) - b) < a)
- return 1;
- else
- return 0;
-}
-
-int crush_multiplication_is_unsafe(__u32 a, __u32 b)
-{
- /* prevent division by zero */
- if (!a)
- return 0;
- if (!b)
- return 1;
- if ((((__u32)(-1)) / b) < a)
- return 1;
- else
- return 0;
-}
-
-/***************************/
-
-/* methods to configure crush_map */
-
-void set_legacy_crush_map(struct crush_map *map) {
- /* initialize legacy tunable values */
- map->choose_local_tries = 2;
- map->choose_local_fallback_tries = 5;
- map->choose_total_tries = 19;
- map->chooseleaf_descend_once = 0;
- map->chooseleaf_vary_r = 0;
- map->chooseleaf_stable = 0;
- map->straw_calc_version = 0;
-
- // by default, use legacy types, and also exclude tree,
- // since it was buggy.
- map->allowed_bucket_algs = CRUSH_LEGACY_ALLOWED_BUCKET_ALGS;
-}
-
-void set_optimal_crush_map(struct crush_map *map) {
- map->choose_local_tries = 0;
- map->choose_local_fallback_tries = 0;
- map->choose_total_tries = 50;
- map->chooseleaf_descend_once = 1;
- map->chooseleaf_vary_r = 1;
- map->chooseleaf_stable = 1;
- map->allowed_bucket_algs = (
- (1 << CRUSH_BUCKET_UNIFORM) |
- (1 << CRUSH_BUCKET_LIST) |
- (1 << CRUSH_BUCKET_STRAW) |
- (1 << CRUSH_BUCKET_STRAW2));
-}
Code Review / stor4nfv.git / blobdiff