include/linux/crush/crush.h

   1 #ifndef CEPH_CRUSH_CRUSH_H
   2 #define CEPH_CRUSH_CRUSH_H
   3
   4 #ifdef __KERNEL__
   5 # include <linux/types.h>
   6 #else
   7 # include "crush_compat.h"
   8 #endif
   9
  10 /*
  11  * CRUSH is a pseudo-random data distribution algorithm that
  12  * efficiently distributes input values (typically, data objects)
  13  * across a heterogeneous, structured storage cluster.
  14  *
  15  * The algorithm was originally described in detail in this paper
  16  * (although the algorithm has evolved somewhat since then):
  17  *
  18  *     http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
  19  *
  20  * LGPL2
  21  */
  22
  23
  24 #define CRUSH_MAGIC 0x00010000ul   /* for detecting algorithm revisions */
  25
  26 #define CRUSH_MAX_DEPTH 10  /* max crush hierarchy depth */
  27 #define CRUSH_MAX_RULESET (1<<8)  /* max crush ruleset number */
  28 #define CRUSH_MAX_RULES CRUSH_MAX_RULESET  /* should be the same as max rulesets */
  29
  30 #define CRUSH_MAX_DEVICE_WEIGHT (100u * 0x10000u)
  31 #define CRUSH_MAX_BUCKET_WEIGHT (65535u * 0x10000u)
  32
  33 #define CRUSH_ITEM_UNDEF  0x7ffffffe  /* undefined result (internal use only) */
  34 #define CRUSH_ITEM_NONE   0x7fffffff  /* no result */
  35
  36 /*
  37  * CRUSH uses user-defined "rules" to describe how inputs should be
  38  * mapped to devices.  A rule consists of sequence of steps to perform
  39  * to generate the set of output devices.
  40  */
  41 struct crush_rule_step {
  42         __u32 op;
  43         __s32 arg1;
  44         __s32 arg2;
  45 };
  46
  47 /* step op codes */
  48 enum {
  49         CRUSH_RULE_NOOP = 0,
  50         CRUSH_RULE_TAKE = 1,          /* arg1 = value to start with */
  51         CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */
  52                                       /* arg2 = type */
  53         CRUSH_RULE_CHOOSE_INDEP = 3,  /* same */
  54         CRUSH_RULE_EMIT = 4,          /* no args */
  55         CRUSH_RULE_CHOOSELEAF_FIRSTN = 6,
  56         CRUSH_RULE_CHOOSELEAF_INDEP = 7,
  57
  58         CRUSH_RULE_SET_CHOOSE_TRIES = 8, /* override choose_total_tries */
  59         CRUSH_RULE_SET_CHOOSELEAF_TRIES = 9, /* override chooseleaf_descend_once */
  60         CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES = 10,
  61         CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES = 11,
  62         CRUSH_RULE_SET_CHOOSELEAF_VARY_R = 12
  63 };
  64
  65 /*
  66  * for specifying choose num (arg1) relative to the max parameter
  67  * passed to do_rule
  68  */
  69 #define CRUSH_CHOOSE_N            0
  70 #define CRUSH_CHOOSE_N_MINUS(x)   (-(x))
  71
  72 /*
  73  * The rule mask is used to describe what the rule is intended for.
  74  * Given a ruleset and size of output set, we search through the
  75  * rule list for a matching rule_mask.
  76  */
  77 struct crush_rule_mask {
  78         __u8 ruleset;
  79         __u8 type;
  80         __u8 min_size;
  81         __u8 max_size;
  82 };
  83
  84 struct crush_rule {
  85         __u32 len;
  86         struct crush_rule_mask mask;
  87         struct crush_rule_step steps[0];
  88 };
  89
  90 #define crush_rule_size(len) (sizeof(struct crush_rule) + \
  91                               (len)*sizeof(struct crush_rule_step))
  92
  93
  94
  95 /*
  96  * A bucket is a named container of other items (either devices or
  97  * other buckets).  Items within a bucket are chosen using one of a
  98  * few different algorithms.  The table summarizes how the speed of
  99  * each option measures up against mapping stability when items are
 100  * added or removed.
 101  *
 102  *  Bucket Alg     Speed       Additions    Removals
 103  *  ------------------------------------------------
 104  *  uniform         O(1)       poor         poor
 105  *  list            O(n)       optimal      poor
 106  *  tree            O(log n)   good         good
 107  *  straw           O(n)       better       better
 108  *  straw2          O(n)       optimal      optimal
 109  */
 110 enum {
 111         CRUSH_BUCKET_UNIFORM = 1,
 112         CRUSH_BUCKET_LIST = 2,
 113         CRUSH_BUCKET_TREE = 3,
 114         CRUSH_BUCKET_STRAW = 4,
 115         CRUSH_BUCKET_STRAW2 = 5,
 116 };
 117 extern const char *crush_bucket_alg_name(int alg);
 118
 119 /*
 120  * although tree was a legacy algorithm, it has been buggy, so
 121  * exclude it.
 122  */
 123 #define CRUSH_LEGACY_ALLOWED_BUCKET_ALGS (      \
 124                 (1 << CRUSH_BUCKET_UNIFORM) |   \
 125                 (1 << CRUSH_BUCKET_LIST) |      \
 126                 (1 << CRUSH_BUCKET_STRAW))
 127
 128 struct crush_bucket {
 129         __s32 id;        /* this'll be negative */
 130         __u16 type;      /* non-zero; type=0 is reserved for devices */
 131         __u8 alg;        /* one of CRUSH_BUCKET_* */
 132         __u8 hash;       /* which hash function to use, CRUSH_HASH_* */
 133         __u32 weight;    /* 16-bit fixed point */
 134         __u32 size;      /* num items */
 135         __s32 *items;
 136
 137         /*
 138          * cached random permutation: used for uniform bucket and for
 139          * the linear search fallback for the other bucket types.
 140          */
 141         __u32 perm_x;  /* @x for which *perm is defined */
 142         __u32 perm_n;  /* num elements of *perm that are permuted/defined */
 143         __u32 *perm;
 144 };
 145
 146 struct crush_bucket_uniform {
 147         struct crush_bucket h;
 148         __u32 item_weight;  /* 16-bit fixed point; all items equally weighted */
 149 };
 150
 151 struct crush_bucket_list {
 152         struct crush_bucket h;
 153         __u32 *item_weights;  /* 16-bit fixed point */
 154         __u32 *sum_weights;   /* 16-bit fixed point.  element i is sum
 155                                  of weights 0..i, inclusive */
 156 };
 157
 158 struct crush_bucket_tree {
 159         struct crush_bucket h;  /* note: h.size is _tree_ size, not number of
 160                                    actual items */
 161         __u8 num_nodes;
 162         __u32 *node_weights;
 163 };
 164
 165 struct crush_bucket_straw {
 166         struct crush_bucket h;
 167         __u32 *item_weights;   /* 16-bit fixed point */
 168         __u32 *straws;         /* 16-bit fixed point */
 169 };
 170
 171 struct crush_bucket_straw2 {
 172         struct crush_bucket h;
 173         __u32 *item_weights;   /* 16-bit fixed point */
 174 };
 175
 176
 177
 178 /*
 179  * CRUSH map includes all buckets, rules, etc.
 180  */
 181 struct crush_map {
 182         struct crush_bucket **buckets;
 183         struct crush_rule **rules;
 184
 185         __s32 max_buckets;
 186         __u32 max_rules;
 187         __s32 max_devices;
 188
 189         /* choose local retries before re-descent */
 190         __u32 choose_local_tries;
 191         /* choose local attempts using a fallback permutation before
 192          * re-descent */
 193         __u32 choose_local_fallback_tries;
 194         /* choose attempts before giving up */
 195         __u32 choose_total_tries;
 196         /* attempt chooseleaf inner descent once for firstn mode; on
 197          * reject retry outer descent.  Note that this does *not*
 198          * apply to a collision: in that case we will retry as we used
 199          * to. */
 200         __u32 chooseleaf_descend_once;
 201
 202         /* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1)
 203          * bits.  a value of 1 is best for new clusters.  for legacy clusters
 204          * that want to limit reshuffling, a value of 3 or 4 will make the
 205          * mappings line up a bit better with previous mappings. */
 206         __u8 chooseleaf_vary_r;
 207
 208 #ifndef __KERNEL__
 209         /*
 210          * version 0 (original) of straw_calc has various flaws.  version 1
 211          * fixes a few of them.
 212          */
 213         __u8 straw_calc_version;
 214
 215         /*
 216          * allowed bucket algs is a bitmask, here the bit positions
 217          * are CRUSH_BUCKET_*.  note that these are *bits* and
 218          * CRUSH_BUCKET_* values are not, so we need to or together (1
 219          * << CRUSH_BUCKET_WHATEVER).  The 0th bit is not used to
 220          * minimize confusion (bucket type values start at 1).
 221          */
 222         __u32 allowed_bucket_algs;
 223
 224         __u32 *choose_tries;
 225 #endif
 226 };
 227
 228
 229 /* crush.c */
 230 extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos);
 231 extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b);
 232 extern void crush_destroy_bucket_list(struct crush_bucket_list *b);
 233 extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b);
 234 extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b);
 235 extern void crush_destroy_bucket_straw2(struct crush_bucket_straw2 *b);
 236 extern void crush_destroy_bucket(struct crush_bucket *b);
 237 extern void crush_destroy_rule(struct crush_rule *r);
 238 extern void crush_destroy(struct crush_map *map);
 239
 240 static inline int crush_calc_tree_node(int i)
 241 {
 242         return ((i+1) << 1)-1;
 243 }
 244
 245 #endif