Sage Weil | 5cd068c | 2010-07-07 08:38:17 -0700 | [diff] [blame] | 1 | #ifndef CEPH_CRUSH_CRUSH_H |
| 2 | #define CEPH_CRUSH_CRUSH_H |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 3 | |
| 4 | #include <linux/types.h> |
| 5 | |
| 6 | /* |
| 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. |
| 10 | * |
| 11 | * The algorithm was originally described in detail in this paper |
| 12 | * (although the algorithm has evolved somewhat since then): |
| 13 | * |
| 14 | * http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf |
| 15 | * |
| 16 | * LGPL2 |
| 17 | */ |
| 18 | |
| 19 | |
| 20 | #define CRUSH_MAGIC 0x00010000ul /* for detecting algorithm revisions */ |
| 21 | |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 22 | #define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */ |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 23 | |
| 24 | |
Ilya Dryomov | 9a3b490 | 2013-12-24 21:19:25 +0200 | [diff] [blame] | 25 | #define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */ |
| 26 | #define CRUSH_ITEM_NONE 0x7fffffff /* no result */ |
Ilya Dryomov | c6d98a6 | 2013-12-24 21:19:25 +0200 | [diff] [blame] | 27 | |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 28 | /* |
| 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. |
| 32 | */ |
| 33 | struct crush_rule_step { |
| 34 | __u32 op; |
| 35 | __s32 arg1; |
| 36 | __s32 arg2; |
| 37 | }; |
| 38 | |
| 39 | /* step op codes */ |
| 40 | enum { |
| 41 | CRUSH_RULE_NOOP = 0, |
| 42 | CRUSH_RULE_TAKE = 1, /* arg1 = value to start with */ |
| 43 | CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */ |
| 44 | /* arg2 = type */ |
| 45 | CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ |
| 46 | CRUSH_RULE_EMIT = 4, /* no args */ |
Ilya Dryomov | 917edad | 2013-12-24 21:19:26 +0200 | [diff] [blame] | 47 | CRUSH_RULE_CHOOSELEAF_FIRSTN = 6, |
| 48 | CRUSH_RULE_CHOOSELEAF_INDEP = 7, |
Ilya Dryomov | be3226a | 2013-12-24 21:19:26 +0200 | [diff] [blame] | 49 | |
Ilya Dryomov | cc10df4 | 2013-12-24 21:19:26 +0200 | [diff] [blame] | 50 | CRUSH_RULE_SET_CHOOSE_TRIES = 8, /* override choose_total_tries */ |
Ilya Dryomov | 917edad | 2013-12-24 21:19:26 +0200 | [diff] [blame] | 51 | CRUSH_RULE_SET_CHOOSELEAF_TRIES = 9, /* override chooseleaf_descend_once */ |
Ilya Dryomov | f046bf9 | 2013-12-24 21:19:27 +0200 | [diff] [blame] | 52 | CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES = 10, |
| 53 | CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES = 11, |
Ilya Dryomov | d83ed85 | 2014-03-19 16:58:37 +0200 | [diff] [blame] | 54 | CRUSH_RULE_SET_CHOOSELEAF_VARY_R = 12 |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 55 | }; |
| 56 | |
| 57 | /* |
| 58 | * for specifying choose num (arg1) relative to the max parameter |
| 59 | * passed to do_rule |
| 60 | */ |
| 61 | #define CRUSH_CHOOSE_N 0 |
| 62 | #define CRUSH_CHOOSE_N_MINUS(x) (-(x)) |
| 63 | |
| 64 | /* |
| 65 | * The rule mask is used to describe what the rule is intended for. |
| 66 | * Given a ruleset and size of output set, we search through the |
| 67 | * rule list for a matching rule_mask. |
| 68 | */ |
| 69 | struct crush_rule_mask { |
| 70 | __u8 ruleset; |
| 71 | __u8 type; |
| 72 | __u8 min_size; |
| 73 | __u8 max_size; |
| 74 | }; |
| 75 | |
| 76 | struct crush_rule { |
| 77 | __u32 len; |
| 78 | struct crush_rule_mask mask; |
| 79 | struct crush_rule_step steps[0]; |
| 80 | }; |
| 81 | |
| 82 | #define crush_rule_size(len) (sizeof(struct crush_rule) + \ |
| 83 | (len)*sizeof(struct crush_rule_step)) |
| 84 | |
| 85 | |
| 86 | |
| 87 | /* |
| 88 | * A bucket is a named container of other items (either devices or |
| 89 | * other buckets). Items within a bucket are chosen using one of a |
| 90 | * few different algorithms. The table summarizes how the speed of |
| 91 | * each option measures up against mapping stability when items are |
| 92 | * added or removed. |
| 93 | * |
| 94 | * Bucket Alg Speed Additions Removals |
| 95 | * ------------------------------------------------ |
| 96 | * uniform O(1) poor poor |
| 97 | * list O(n) optimal poor |
| 98 | * tree O(log n) good good |
| 99 | * straw O(n) optimal optimal |
| 100 | */ |
| 101 | enum { |
| 102 | CRUSH_BUCKET_UNIFORM = 1, |
| 103 | CRUSH_BUCKET_LIST = 2, |
| 104 | CRUSH_BUCKET_TREE = 3, |
| 105 | CRUSH_BUCKET_STRAW = 4 |
| 106 | }; |
Sage Weil | c6cf726 | 2009-11-06 16:39:26 -0800 | [diff] [blame] | 107 | extern const char *crush_bucket_alg_name(int alg); |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 108 | |
| 109 | struct crush_bucket { |
| 110 | __s32 id; /* this'll be negative */ |
| 111 | __u16 type; /* non-zero; type=0 is reserved for devices */ |
Sage Weil | fb69039 | 2009-11-07 20:18:22 -0800 | [diff] [blame] | 112 | __u8 alg; /* one of CRUSH_BUCKET_* */ |
| 113 | __u8 hash; /* which hash function to use, CRUSH_HASH_* */ |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 114 | __u32 weight; /* 16-bit fixed point */ |
| 115 | __u32 size; /* num items */ |
| 116 | __s32 *items; |
| 117 | |
| 118 | /* |
| 119 | * cached random permutation: used for uniform bucket and for |
| 120 | * the linear search fallback for the other bucket types. |
| 121 | */ |
| 122 | __u32 perm_x; /* @x for which *perm is defined */ |
| 123 | __u32 perm_n; /* num elements of *perm that are permuted/defined */ |
| 124 | __u32 *perm; |
| 125 | }; |
| 126 | |
| 127 | struct crush_bucket_uniform { |
| 128 | struct crush_bucket h; |
| 129 | __u32 item_weight; /* 16-bit fixed point; all items equally weighted */ |
| 130 | }; |
| 131 | |
| 132 | struct crush_bucket_list { |
| 133 | struct crush_bucket h; |
| 134 | __u32 *item_weights; /* 16-bit fixed point */ |
| 135 | __u32 *sum_weights; /* 16-bit fixed point. element i is sum |
| 136 | of weights 0..i, inclusive */ |
| 137 | }; |
| 138 | |
| 139 | struct crush_bucket_tree { |
| 140 | struct crush_bucket h; /* note: h.size is _tree_ size, not number of |
| 141 | actual items */ |
| 142 | __u8 num_nodes; |
| 143 | __u32 *node_weights; |
| 144 | }; |
| 145 | |
| 146 | struct crush_bucket_straw { |
| 147 | struct crush_bucket h; |
| 148 | __u32 *item_weights; /* 16-bit fixed point */ |
| 149 | __u32 *straws; /* 16-bit fixed point */ |
| 150 | }; |
| 151 | |
| 152 | |
| 153 | |
| 154 | /* |
| 155 | * CRUSH map includes all buckets, rules, etc. |
| 156 | */ |
| 157 | struct crush_map { |
| 158 | struct crush_bucket **buckets; |
| 159 | struct crush_rule **rules; |
| 160 | |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 161 | __s32 max_buckets; |
| 162 | __u32 max_rules; |
| 163 | __s32 max_devices; |
Sage Weil | 546f04e | 2012-07-30 18:15:23 -0700 | [diff] [blame] | 164 | |
| 165 | /* choose local retries before re-descent */ |
| 166 | __u32 choose_local_tries; |
| 167 | /* choose local attempts using a fallback permutation before |
| 168 | * re-descent */ |
| 169 | __u32 choose_local_fallback_tries; |
| 170 | /* choose attempts before giving up */ |
| 171 | __u32 choose_total_tries; |
Ilya Dryomov | f18650a | 2013-12-24 21:19:26 +0200 | [diff] [blame] | 172 | /* attempt chooseleaf inner descent once for firstn mode; on |
| 173 | * reject retry outer descent. Note that this does *not* |
| 174 | * apply to a collision: in that case we will retry as we used |
| 175 | * to. */ |
Jim Schutt | 1604f48 | 2012-11-30 09:15:25 -0700 | [diff] [blame] | 176 | __u32 chooseleaf_descend_once; |
Ilya Dryomov | e2b149c | 2014-03-19 16:58:37 +0200 | [diff] [blame] | 177 | |
| 178 | /* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1) |
| 179 | * bits. a value of 1 is best for new clusters. for legacy clusters |
| 180 | * that want to limit reshuffling, a value of 3 or 4 will make the |
| 181 | * mappings line up a bit better with previous mappings. */ |
| 182 | __u8 chooseleaf_vary_r; |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 183 | }; |
| 184 | |
| 185 | |
| 186 | /* crush.c */ |
Sage Weil | 8b12d47 | 2012-05-07 15:38:35 -0700 | [diff] [blame] | 187 | extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos); |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 188 | extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b); |
| 189 | extern void crush_destroy_bucket_list(struct crush_bucket_list *b); |
| 190 | extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b); |
| 191 | extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b); |
| 192 | extern void crush_destroy_bucket(struct crush_bucket *b); |
Ilya Dryomov | bfb16d7 | 2013-12-24 21:19:24 +0200 | [diff] [blame] | 193 | extern void crush_destroy_rule(struct crush_rule *r); |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 194 | extern void crush_destroy(struct crush_map *map); |
| 195 | |
Sage Weil | f671d4c | 2012-05-07 15:36:49 -0700 | [diff] [blame] | 196 | static inline int crush_calc_tree_node(int i) |
| 197 | { |
| 198 | return ((i+1) << 1)-1; |
| 199 | } |
| 200 | |
Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame] | 201 | #endif |