PM / Wakeup: Show wakeup sources statistics in debugfs
[linux-2.6.git] / net / 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 <linux/crush/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 }
150
151