1 #ifndef CEPH_CRUSH_CRUSH_H
2 #define CEPH_CRUSH_CRUSH_H
4 #include <linux/types.h>
7 * CRUSH is a pseudo-random data distribution algorithm that
8 * efficiently distributes input values (typically, data objects)
9 * across a heterogeneous, structured storage cluster.
11 * The algorithm was originally described in detail in this paper
12 * (although the algorithm has evolved somewhat since then):
14 * http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
20 #define CRUSH_MAGIC 0x00010000ul /* for detecting algorithm revisions */
22 #define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */
25 #define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */
26 #define CRUSH_ITEM_NONE 0x7fffffff /* no result */
29 * CRUSH uses user-defined "rules" to describe how inputs should be
30 * mapped to devices. A rule consists of sequence of steps to perform
31 * to generate the set of output devices.
33 struct crush_rule_step
{
42 CRUSH_RULE_TAKE
= 1, /* arg1 = value to start with */
43 CRUSH_RULE_CHOOSE_FIRSTN
= 2, /* arg1 = num items to pick */
45 CRUSH_RULE_CHOOSE_INDEP
= 3, /* same */
46 CRUSH_RULE_EMIT
= 4, /* no args */
47 CRUSH_RULE_CHOOSELEAF_FIRSTN
= 6,
48 CRUSH_RULE_CHOOSELEAF_INDEP
= 7,
50 CRUSH_RULE_SET_CHOOSE_TRIES
= 8, /* override choose_total_tries */
51 CRUSH_RULE_SET_CHOOSELEAF_TRIES
= 9, /* override chooseleaf_descend_once */
52 CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES
= 10,
53 CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES
= 11,
57 * for specifying choose num (arg1) relative to the max parameter
60 #define CRUSH_CHOOSE_N 0
61 #define CRUSH_CHOOSE_N_MINUS(x) (-(x))
64 * The rule mask is used to describe what the rule is intended for.
65 * Given a ruleset and size of output set, we search through the
66 * rule list for a matching rule_mask.
68 struct crush_rule_mask
{
77 struct crush_rule_mask mask
;
78 struct crush_rule_step steps
[0];
81 #define crush_rule_size(len) (sizeof(struct crush_rule) + \
82 (len)*sizeof(struct crush_rule_step))
87 * A bucket is a named container of other items (either devices or
88 * other buckets). Items within a bucket are chosen using one of a
89 * few different algorithms. The table summarizes how the speed of
90 * each option measures up against mapping stability when items are
93 * Bucket Alg Speed Additions Removals
94 * ------------------------------------------------
95 * uniform O(1) poor poor
96 * list O(n) optimal poor
97 * tree O(log n) good good
98 * straw O(n) optimal optimal
101 CRUSH_BUCKET_UNIFORM
= 1,
102 CRUSH_BUCKET_LIST
= 2,
103 CRUSH_BUCKET_TREE
= 3,
104 CRUSH_BUCKET_STRAW
= 4
106 extern const char *crush_bucket_alg_name(int alg
);
108 struct crush_bucket
{
109 __s32 id
; /* this'll be negative */
110 __u16 type
; /* non-zero; type=0 is reserved for devices */
111 __u8 alg
; /* one of CRUSH_BUCKET_* */
112 __u8 hash
; /* which hash function to use, CRUSH_HASH_* */
113 __u32 weight
; /* 16-bit fixed point */
114 __u32 size
; /* num items */
118 * cached random permutation: used for uniform bucket and for
119 * the linear search fallback for the other bucket types.
121 __u32 perm_x
; /* @x for which *perm is defined */
122 __u32 perm_n
; /* num elements of *perm that are permuted/defined */
126 struct crush_bucket_uniform
{
127 struct crush_bucket h
;
128 __u32 item_weight
; /* 16-bit fixed point; all items equally weighted */
131 struct crush_bucket_list
{
132 struct crush_bucket h
;
133 __u32
*item_weights
; /* 16-bit fixed point */
134 __u32
*sum_weights
; /* 16-bit fixed point. element i is sum
135 of weights 0..i, inclusive */
138 struct crush_bucket_tree
{
139 struct crush_bucket h
; /* note: h.size is _tree_ size, not number of
145 struct crush_bucket_straw
{
146 struct crush_bucket h
;
147 __u32
*item_weights
; /* 16-bit fixed point */
148 __u32
*straws
; /* 16-bit fixed point */
154 * CRUSH map includes all buckets, rules, etc.
157 struct crush_bucket
**buckets
;
158 struct crush_rule
**rules
;
164 /* choose local retries before re-descent */
165 __u32 choose_local_tries
;
166 /* choose local attempts using a fallback permutation before
168 __u32 choose_local_fallback_tries
;
169 /* choose attempts before giving up */
170 __u32 choose_total_tries
;
171 /* attempt chooseleaf inner descent once for firstn mode; on
172 * reject retry outer descent. Note that this does *not*
173 * apply to a collision: in that case we will retry as we used
175 __u32 chooseleaf_descend_once
;
180 extern int crush_get_bucket_item_weight(const struct crush_bucket
*b
, int pos
);
181 extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform
*b
);
182 extern void crush_destroy_bucket_list(struct crush_bucket_list
*b
);
183 extern void crush_destroy_bucket_tree(struct crush_bucket_tree
*b
);
184 extern void crush_destroy_bucket_straw(struct crush_bucket_straw
*b
);
185 extern void crush_destroy_bucket(struct crush_bucket
*b
);
186 extern void crush_destroy_rule(struct crush_rule
*r
);
187 extern void crush_destroy(struct crush_map
*map
);
189 static inline int crush_calc_tree_node(int i
)
191 return ((i
+1) << 1)-1;