--- /dev/null
+#ifndef CEPH_CRUSH_CRUSH_H
+#define CEPH_CRUSH_CRUSH_H
+
+#ifdef __KERNEL__
+# include <linux/types.h>
+#else
+# include "crush_compat.h"
+#endif
+
+/*
+ * CRUSH is a pseudo-random data distribution algorithm that
+ * efficiently distributes input values (typically, data objects)
+ * across a heterogeneous, structured storage cluster.
+ *
+ * The algorithm was originally described in detail in this paper
+ * (although the algorithm has evolved somewhat since then):
+ *
+ * http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
+ *
+ * LGPL2
+ */
+
+
+#define CRUSH_MAGIC 0x00010000ul /* for detecting algorithm revisions */
+
+#define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */
+#define CRUSH_MAX_RULESET (1<<8) /* max crush ruleset number */
+#define CRUSH_MAX_RULES CRUSH_MAX_RULESET /* should be the same as max rulesets */
+
+#define CRUSH_MAX_DEVICE_WEIGHT (100u * 0x10000u)
+#define CRUSH_MAX_BUCKET_WEIGHT (65535u * 0x10000u)
+
+#define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */
+/** @ingroup API
+ * The equivalent of NULL for an item, i.e. the absence of an item.
+ */
+#define CRUSH_ITEM_NONE 0x7fffffff
+
+/*
+ * CRUSH uses user-defined "rules" to describe how inputs should be
+ * mapped to devices. A rule consists of sequence of steps to perform
+ * to generate the set of output devices.
+ */
+struct crush_rule_step {
+ __u32 op;
+ __s32 arg1;
+ __s32 arg2;
+};
+
+/** @ingroup API
+ */
+enum crush_opcodes {
+ /*! do nothing
+ */
+ CRUSH_RULE_NOOP = 0,
+ CRUSH_RULE_TAKE = 1, /* arg1 = value to start with */
+ CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */
+ /* arg2 = type */
+ CRUSH_RULE_CHOOSE_INDEP = 3, /* same */
+ CRUSH_RULE_EMIT = 4, /* no args */
+ CRUSH_RULE_CHOOSELEAF_FIRSTN = 6,
+ CRUSH_RULE_CHOOSELEAF_INDEP = 7,
+
+ CRUSH_RULE_SET_CHOOSE_TRIES = 8, /* override choose_total_tries */
+ CRUSH_RULE_SET_CHOOSELEAF_TRIES = 9, /* override chooseleaf_descend_once */
+ CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES = 10,
+ CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES = 11,
+ CRUSH_RULE_SET_CHOOSELEAF_VARY_R = 12,
+ CRUSH_RULE_SET_CHOOSELEAF_STABLE = 13
+};
+
+/*
+ * for specifying choose num (arg1) relative to the max parameter
+ * passed to do_rule
+ */
+#define CRUSH_CHOOSE_N 0
+#define CRUSH_CHOOSE_N_MINUS(x) (-(x))
+
+/*
+ * The rule mask is used to describe what the rule is intended for.
+ * Given a ruleset and size of output set, we search through the
+ * rule list for a matching rule_mask.
+ */
+struct crush_rule_mask {
+ __u8 ruleset;
+ __u8 type;
+ __u8 min_size;
+ __u8 max_size;
+};
+
+struct crush_rule {
+ __u32 len;
+ struct crush_rule_mask mask;
+ struct crush_rule_step steps[0];
+};
+
+#define crush_rule_size(len) (sizeof(struct crush_rule) + \
+ (len)*sizeof(struct crush_rule_step))
+
+
+
+/*
+ * A bucket is a named container of other items (either devices or
+ * other buckets).
+ */
+
+/** @ingroup API
+ *
+ * Items within a bucket are chosen with crush_do_rule() using one of
+ * three algorithms representing a tradeoff between performance and
+ * reorganization efficiency. If you are unsure of which bucket type
+ * to use, we recommend using ::CRUSH_BUCKET_STRAW2.
+ *
+ * The table summarizes how the speed of each option measures up
+ * against mapping stability when items are added or removed.
+ *
+ * Bucket Alg Speed Additions Removals
+ * ------------------------------------------------
+ * uniform O(1) poor poor
+ * list O(n) optimal poor
+ * straw2 O(n) optimal optimal
+ */
+enum crush_algorithm {
+ /*!
+ * Devices are rarely added individually in a large system.
+ * Instead, new storage is typically deployed in blocks of identical
+ * devices, often as an additional shelf in a server rack or perhaps
+ * an entire cabinet. Devices reaching their end of life are often
+ * similarly decommissioned as a set (individual failures aside),
+ * making it natural to treat them as a unit. CRUSH uniform buckets
+ * are used to represent an identical set of devices in such
+ * circumstances. The key advantage in doing so is performance
+ * related: CRUSH can map replicas into uniform buckets in constant
+ * time. In cases where the uniformity restrictions are not
+ * appropriate, other bucket types can be used. If the size of a
+ * uniform bucket changes, there is a complete reshuffling of data
+ * between devices, much like conventional hash-based distribution
+ * strategies.
+ */
+ CRUSH_BUCKET_UNIFORM = 1,
+ /*!
+ * List buckets structure their contents as a linked list, and
+ * can contain items with arbitrary weights. To place a
+ * replica, CRUSH begins at the head of the list with the most
+ * recently added item and compares its weight to the sum of
+ * all remaining items' weights. Depending on the value of
+ * hash( x , r , item), either the current item is chosen with
+ * the appropriate probability, or the process continues
+ * recursively down the list. This is a natural and intuitive
+ * choice for an expanding cluster: either an object is
+ * relocated to the newest device with some appropriate
+ * probability, or it remains on the older devices as before.
+ * The result is optimal data migration when items are added
+ * to the bucket. Items removed from the middle or tail of the
+ * list, however, can result in a significant amount of
+ * unnecessary movement, making list buckets most suitable for
+ * circumstances in which they never (or very rarely) shrink.
+ */
+ CRUSH_BUCKET_LIST = 2,
+ /*! @cond INTERNAL */
+ CRUSH_BUCKET_TREE = 3,
+ CRUSH_BUCKET_STRAW = 4,
+ /*! @endcond */
+ /*!
+ * List and tree buckets are structured such that a limited
+ * number of hash values need to be calculated and compared to
+ * weights in order to select a bucket item. In doing so,
+ * they divide and conquer in a way that either gives certain
+ * items precedence (e. g., those at the beginning of a list)
+ * or obviates the need to consider entire subtrees of items
+ * at all. That improves the performance of the replica
+ * placement process, but can also introduce suboptimal
+ * reorganization behavior when the contents of a bucket
+ * change due an addition, removal, or re-weighting of an
+ * item.
+ *
+ * The straw2 bucket type allows all items to fairly "compete"
+ * against each other for replica placement through a process
+ * analogous to a draw of straws. To place a replica, a straw
+ * of random length is drawn for each item in the bucket. The
+ * item with the longest straw wins. The length of each straw
+ * is initially a value in a fixed range. Each straw length
+ * is scaled by a factor based on the item's weight so that
+ * heavily weighted items are more likely to win the draw.
+ * Although this process is almost twice as slow (on average)
+ * than a list bucket and even slower than a tree bucket
+ * (which scales logarithmically), straw2 buckets result in
+ * optimal data movement between nested items when modified.
+ */
+ CRUSH_BUCKET_STRAW2 = 5,
+};
+extern const char *crush_bucket_alg_name(int alg);
+
+/*
+ * although tree was a legacy algorithm, it has been buggy, so
+ * exclude it.
+ */
+#define CRUSH_LEGACY_ALLOWED_BUCKET_ALGS ( \
+ (1 << CRUSH_BUCKET_UNIFORM) | \
+ (1 << CRUSH_BUCKET_LIST) | \
+ (1 << CRUSH_BUCKET_STRAW))
+
+/** @ingroup API
+ *
+ * A bucket contains __size__ __items__ which are either positive
+ * numbers or negative numbers that reference other buckets and is
+ * uniquely identified with __id__ which is a negative number. The
+ * __weight__ of a bucket is the cumulative weight of all its
+ * children. A bucket is assigned a ::crush_algorithm that is used by
+ * crush_do_rule() to draw an item depending on its weight. A bucket
+ * can be assigned a strictly positive (> 0) __type__ defined by the
+ * caller. The __type__ can be used by crush_do_rule(), when it is
+ * given as an argument of a rule step.
+ *
+ * A pointer to crush_bucket can safely be cast into the following
+ * structure, depending on the value of __alg__:
+ *
+ * - __alg__ == ::CRUSH_BUCKET_UNIFORM cast to crush_bucket_uniform
+ * - __alg__ == ::CRUSH_BUCKET_LIST cast to crush_bucket_list
+ * - __alg__ == ::CRUSH_BUCKET_STRAW2 cast to crush_bucket_straw2
+ *
+ * The weight of each item depends on the algorithm and the
+ * information about it is available in the corresponding structure
+ * (crush_bucket_uniform, crush_bucket_list or crush_bucket_straw2).
+ *
+ * See crush_map for more information on how __id__ is used
+ * to reference the bucket.
+ */
+struct crush_bucket {
+ __s32 id; /*!< bucket identifier, < 0 and unique within a crush_map */
+ __u16 type; /*!< > 0 bucket type, defined by the caller */
+ __u8 alg; /*!< the item selection ::crush_algorithm */
+ /*! @cond INTERNAL */
+ __u8 hash; /* which hash function to use, CRUSH_HASH_* */
+ /*! @endcond */
+ __u32 weight; /*!< 16.16 fixed point cumulated children weight */
+ __u32 size; /*!< size of the __items__ array */
+ __s32 *items; /*!< array of children: < 0 are buckets, >= 0 items */
+};
+
+/** @ingroup API
+ *
+ * Replacement weights for each item in a bucket. The size of the
+ * array must be exactly the size of the straw2 bucket, just as the
+ * item_weights array.
+ *
+ */
+struct crush_weight_set {
+ __u32 *weights; /*!< 16.16 fixed point weights in the same order as items */
+ __u32 size; /*!< size of the __weights__ array */
+};
+
+/** @ingroup API
+ *
+ * Replacement weights and ids for a given straw2 bucket, for
+ * placement purposes.
+ *
+ * When crush_do_rule() chooses the Nth item from a straw2 bucket, the
+ * replacement weights found at __weight_set[N]__ are used instead of
+ * the weights from __item_weights__. If __N__ is greater than
+ * __weight_set_size__, the weights found at __weight_set_size-1__ are
+ * used instead. For instance if __weight_set__ is:
+ *
+ * [ [ 0x10000, 0x20000 ], // position 0
+ * [ 0x20000, 0x40000 ] ] // position 1
+ *
+ * choosing the 0th item will use position 0 weights [ 0x10000, 0x20000 ]
+ * choosing the 1th item will use position 1 weights [ 0x20000, 0x40000 ]
+ * choosing the 2th item will use position 1 weights [ 0x20000, 0x40000 ]
+ * etc.
+ *
+ */
+struct crush_choose_arg {
+ __s32 *ids; /*!< values to use instead of items */
+ __u32 ids_size; /*!< size of the __ids__ array */
+ struct crush_weight_set *weight_set; /*!< weight replacements for a given position */
+ __u32 weight_set_size; /*!< size of the __weight_set__ array */
+};
+
+/** @ingroup API
+ *
+ * Replacement weights and ids for each bucket in the crushmap. The
+ * __size__ of the __args__ array must be exactly the same as the
+ * __map->max_buckets__.
+ *
+ * The __crush_choose_arg__ at index N will be used when choosing
+ * an item from the bucket __map->buckets[N]__ bucket, provided it
+ * is a straw2 bucket.
+ *
+ */
+struct crush_choose_arg_map {
+ struct crush_choose_arg *args; /*!< replacement for each bucket in the crushmap */
+ __u32 size; /*!< size of the __args__ array */
+};
+
+/** @ingroup API
+ * The weight of each item in the bucket when
+ * __h.alg__ == ::CRUSH_BUCKET_UNIFORM.
+ */
+struct crush_bucket_uniform {
+ struct crush_bucket h; /*!< generic bucket information */
+ __u32 item_weight; /*!< 16.16 fixed point weight for each item */
+};
+
+/** @ingroup API
+ * The weight of each item in the bucket when
+ * __h.alg__ == ::CRUSH_BUCKET_LIST.
+ *
+ * The weight of __h.items[i]__ is __item_weights[i]__ for i in
+ * [0,__h.size__[. The __sum_weight__[i] is the sum of the __item_weights[j]__
+ * for j in [0,i[.
+ *
+ */
+struct crush_bucket_list {
+ struct crush_bucket h; /*!< generic bucket information */
+ __u32 *item_weights; /*!< 16.16 fixed point weight for each item */
+ __u32 *sum_weights; /*!< 16.16 fixed point sum of the weights */
+};
+
+struct crush_bucket_tree {
+ struct crush_bucket h; /* note: h.size is _tree_ size, not number of
+ actual items */
+ __u8 num_nodes;
+ __u32 *node_weights;
+};
+
+struct crush_bucket_straw {
+ struct crush_bucket h;
+ __u32 *item_weights; /* 16-bit fixed point */
+ __u32 *straws; /* 16-bit fixed point */
+};
+
+/** @ingroup API
+ * The weight of each item in the bucket when
+ * __h.alg__ == ::CRUSH_BUCKET_STRAW2.
+ *
+ * The weight of __h.items[i]__ is __item_weights[i]__ for i in
+ * [0,__h.size__[.
+ */
+struct crush_bucket_straw2 {
+ struct crush_bucket h; /*!< generic bucket information */
+ __u32 *item_weights; /*!< 16.16 fixed point weight for each item */
+};
+
+
+
+/** @ingroup API
+ *
+ * A crush map define a hierarchy of crush_bucket that end with leaves
+ * (buckets and leaves are called items) and a set of crush_rule to
+ * map an integer to items with the crush_do_rule() function.
+ *
+ */
+struct crush_map {
+ /*! An array of crush_bucket pointers of size __max_buckets__.
+ * An element of the array may be NULL if the bucket was removed with
+ * crush_remove_bucket(). The buckets must be added with crush_add_bucket().
+ * The bucket found at __buckets[i]__ must have a crush_bucket.id == -1-i.
+ */
+ struct crush_bucket **buckets;
+ /*! An array of crush_rule pointers of size __max_rules__.
+ * An element of the array may be NULL if the rule was removed (there is
+ * no API to do so but there may be one in the future). The rules must be added
+ * with crush_add_rule().
+ */
+ struct crush_rule **rules;
+ __s32 max_buckets; /*!< the size of __buckets__ */
+ __u32 max_rules; /*!< the size of __rules__ */
+ /*! The value of the highest item stored in the crush_map + 1
+ */
+ __s32 max_devices;
+
+ /*! Backward compatibility tunable. It implements a bad solution
+ * and must always be set to 0 except for backward compatibility
+ * purposes
+ */
+ __u32 choose_local_tries;
+ /*! Backward compatibility tunable. It implements a bad solution
+ * and must always be set to 0 except for backward compatibility
+ * purposes
+ */
+ __u32 choose_local_fallback_tries;
+ /*! Tunable. The default value when the CHOOSE_TRIES or
+ * CHOOSELEAF_TRIES steps are omitted in a rule. See the
+ * documentation for crush_rule_set_step() for more
+ * information
+ */
+ __u32 choose_total_tries;
+ /*! Backward compatibility tunable. It should always be set
+ * to 1 except for backward compatibility. Implemented in 2012
+ * it was generalized late 2013 and is mostly unused except
+ * in one border case, reason why it must be set to 1.
+ *
+ * Attempt chooseleaf inner descent once for firstn mode; on
+ * reject retry outer descent. Note that this does *not*
+ * apply to a collision: in that case we will retry as we
+ * used to.
+ */
+ __u32 chooseleaf_descend_once;
+ /*! Backward compatibility tunable. It is a fix for bad
+ * mappings implemented in 2014 at
+ * https://github.com/ceph/ceph/pull/1185. It should always
+ * be set to 1 except for backward compatibility.
+ *
+ * If non-zero, feed r into chooseleaf, bit-shifted right by
+ * (r-1) bits. a value of 1 is best for new clusters. for
+ * legacy clusters that want to limit reshuffling, a value of
+ * 3 or 4 will make the mappings line up a bit better with
+ * previous mappings.
+ */
+ __u8 chooseleaf_vary_r;
+
+ /*! Backward compatibility tunable. It is an improvement that
+ * avoids unnecessary mapping changes, implemented at
+ * https://github.com/ceph/ceph/pull/6572 and explained in
+ * this post: "chooseleaf may cause some unnecessary pg
+ * migrations" in October 2015
+ * https://www.mail-archive.com/ceph-devel@vger.kernel.org/msg26075.html
+ * It should always be set to 1 except for backward compatibility.
+ */
+ __u8 chooseleaf_stable;
+
+ /*! @cond INTERNAL */
+ /* This value is calculated after decode or construction by
+ the builder. It is exposed here (rather than having a
+ 'build CRUSH working space' function) so that callers can
+ reserve a static buffer, allocate space on the stack, or
+ otherwise avoid calling into the heap allocator if they
+ want to. The size of the working space depends on the map,
+ while the size of the scratch vector passed to the mapper
+ depends on the size of the desired result set.
+
+ Nothing stops the caller from allocating both in one swell
+ foop and passing in two points, though. */
+ size_t working_size;
+
+#ifndef __KERNEL__
+ /*! @endcond */
+ /*! Backward compatibility tunable. It is a fix for the straw
+ * scaler values for the straw algorithm which is deprecated
+ * (straw2 replaces it) implemented at
+ * https://github.com/ceph/ceph/pull/3057. It should always
+ * be set to 1 except for backward compatibility.
+ *
+ */
+ __u8 straw_calc_version;
+
+ /*! @cond INTERNAL */
+ /*
+ * allowed bucket algs is a bitmask, here the bit positions
+ * are CRUSH_BUCKET_*. note that these are *bits* and
+ * CRUSH_BUCKET_* values are not, so we need to or together (1
+ * << CRUSH_BUCKET_WHATEVER). The 0th bit is not used to
+ * minimize confusion (bucket type values start at 1).
+ */
+ __u32 allowed_bucket_algs;
+
+ __u32 *choose_tries;
+#endif
+ /*! @endcond */
+};
+
+
+/* crush.c */
+/** @ingroup API
+ *
+ * Return the 16.16 fixed point weight of the item at __pos__ (zero
+ * based index) within the bucket __b__. If __pos__ is negative or
+ * greater or equal to the number of items in the bucket, return 0.
+ *
+ * @param b the bucket containing items
+ * @param pos the zero based index of the item
+ *
+ * @returns the 16.16 fixed point item weight
+ */
+extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos);
+extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b);
+extern void crush_destroy_bucket_list(struct crush_bucket_list *b);
+extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b);
+extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b);
+extern void crush_destroy_bucket_straw2(struct crush_bucket_straw2 *b);
+/** @ingroup API
+ *
+ * Deallocate a bucket created via crush_add_bucket().
+ *
+ * @param b the bucket to deallocate
+ */
+extern void crush_destroy_bucket(struct crush_bucket *b);
+/** @ingroup API
+ *
+ * Deallocate a rule created via crush_add_rule().
+ *
+ * @param r the rule to deallocate
+ */
+extern void crush_destroy_rule(struct crush_rule *r);
+/** @ingroup API
+ *
+ * Deallocate the __map__, previously allocated with crush_create.
+ *
+ * @param map the crush map
+ */
+extern void crush_destroy(struct crush_map *map);
+
+static inline int crush_calc_tree_node(int i)
+{
+ return ((i+1) << 1)-1;
+}
+
+static inline const char *crush_alg_name(int alg)
+{
+ switch (alg) {
+ case CRUSH_BUCKET_UNIFORM:
+ return "uniform";
+ case CRUSH_BUCKET_LIST:
+ return "list";
+ case CRUSH_BUCKET_TREE:
+ return "tree";
+ case CRUSH_BUCKET_STRAW:
+ return "straw";
+ case CRUSH_BUCKET_STRAW2:
+ return "straw2";
+ default:
+ return "unknown";
+ }
+}
+
+/* ---------------------------------------------------------------------
+ Private
+ --------------------------------------------------------------------- */
+
+/* These data structures are private to the CRUSH implementation. They
+ are exposed in this header file because builder needs their
+ definitions to calculate the total working size.
+
+ Moving this out of the crush map allow us to treat the CRUSH map as
+ immutable within the mapper and removes the requirement for a CRUSH
+ map lock. */
+
+struct crush_work_bucket {
+ __u32 perm_x; /* @x for which *perm is defined */
+ __u32 perm_n; /* num elements of *perm that are permuted/defined */
+ __u32 *perm; /* Permutation of the bucket's items */
+};
+
+struct crush_work {
+ struct crush_work_bucket **work; /* Per-bucket working store */
+};
+
+#endif
Code Review / stor4nfv.git / blobdiff