release/src-rt-6.x.4708/linux/linux-2.6.36/fs/ceph/crush/crush.c

   1
   2 #ifdef __KERNEL__
   3 # include <linux/slab.h>
   4 #else
   5 # include <stdlib.h>
   6 # include <assert.h>
   7 # define kfree(x) do { if (x) free(x); } while (0)
   8 # define BUG_ON(x) assert(!(x))
   9 #endif
  10
  11 #include "crush.h"
  12
  13 const char *crush_bucket_alg_name(int alg)
  14 {
  15         switch (alg) {
  16         case CRUSH_BUCKET_UNIFORM: return "uniform";
  17         case CRUSH_BUCKET_LIST: return "list";
  18         case CRUSH_BUCKET_TREE: return "tree";
  19         case CRUSH_BUCKET_STRAW: return "straw";
  20         default: return "unknown";
  21         }
  22 }
  23
  24 /**
  25  * crush_get_bucket_item_weight - Get weight of an item in given bucket
  26  * @b: bucket pointer
  27  * @p: item index in bucket
  28  */
  29 int crush_get_bucket_item_weight(struct crush_bucket *b, int p)
  30 {
  31         if (p >= b->size)
  32                 return 0;
  33
  34         switch (b->alg) {
  35         case CRUSH_BUCKET_UNIFORM:
  36                 return ((struct crush_bucket_uniform *)b)->item_weight;
  37         case CRUSH_BUCKET_LIST:
  38                 return ((struct crush_bucket_list *)b)->item_weights[p];
  39         case CRUSH_BUCKET_TREE:
  40                 if (p & 1)
  41                         return ((struct crush_bucket_tree *)b)->node_weights[p];
  42                 return 0;
  43         case CRUSH_BUCKET_STRAW:
  44                 return ((struct crush_bucket_straw *)b)->item_weights[p];
  45         }
  46         return 0;
  47 }
  48
  49 /**
  50  * crush_calc_parents - Calculate parent vectors for the given crush map.
  51  * @map: crush_map pointer
  52  */
  53 void crush_calc_parents(struct crush_map *map)
  54 {
  55         int i, b, c;
  56
  57         for (b = 0; b < map->max_buckets; b++) {
  58                 if (map->buckets[b] == NULL)
  59                         continue;
  60                 for (i = 0; i < map->buckets[b]->size; i++) {
  61                         c = map->buckets[b]->items[i];
  62                         BUG_ON(c >= map->max_devices ||
  63                                c < -map->max_buckets);
  64                         if (c >= 0)
  65                                 map->device_parents[c] = map->buckets[b]->id;
  66                         else
  67                                 map->bucket_parents[-1-c] = map->buckets[b]->id;
  68                 }
  69         }
  70 }
  71
  72 void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b)
  73 {
  74         kfree(b->h.perm);
  75         kfree(b->h.items);
  76         kfree(b);
  77 }
  78
  79 void crush_destroy_bucket_list(struct crush_bucket_list *b)
  80 {
  81         kfree(b->item_weights);
  82         kfree(b->sum_weights);
  83         kfree(b->h.perm);
  84         kfree(b->h.items);
  85         kfree(b);
  86 }
  87
  88 void crush_destroy_bucket_tree(struct crush_bucket_tree *b)
  89 {
  90         kfree(b->node_weights);
  91         kfree(b);
  92 }
  93
  94 void crush_destroy_bucket_straw(struct crush_bucket_straw *b)
  95 {
  96         kfree(b->straws);
  97         kfree(b->item_weights);
  98         kfree(b->h.perm);
  99         kfree(b->h.items);
 100         kfree(b);
 101 }
 102
 103 void crush_destroy_bucket(struct crush_bucket *b)
 104 {
 105         switch (b->alg) {
 106         case CRUSH_BUCKET_UNIFORM:
 107                 crush_destroy_bucket_uniform((struct crush_bucket_uniform *)b);
 108                 break;
 109         case CRUSH_BUCKET_LIST:
 110                 crush_destroy_bucket_list((struct crush_bucket_list *)b);
 111                 break;
 112         case CRUSH_BUCKET_TREE:
 113                 crush_destroy_bucket_tree((struct crush_bucket_tree *)b);
 114                 break;
 115         case CRUSH_BUCKET_STRAW:
 116                 crush_destroy_bucket_straw((struct crush_bucket_straw *)b);
 117                 break;
 118         }
 119 }
 120
 121 /**
 122  * crush_destroy - Destroy a crush_map
 123  * @map: crush_map pointer
 124  */
 125 void crush_destroy(struct crush_map *map)
 126 {
 127         int b;
 128
 129         /* buckets */
 130         if (map->buckets) {
 131                 for (b = 0; b < map->max_buckets; b++) {
 132                         if (map->buckets[b] == NULL)
 133                                 continue;
 134                         crush_destroy_bucket(map->buckets[b]);
 135                 }
 136                 kfree(map->buckets);
 137         }
 138
 139         /* rules */
 140         if (map->rules) {
 141                 for (b = 0; b < map->max_rules; b++)
 142                         kfree(map->rules[b]);
 143                 kfree(map->rules);
 144         }
 145
 146         kfree(map->bucket_parents);
 147         kfree(map->device_parents);
 148         kfree(map);
 149 }