[mirror_ubuntu-bionic-kernel.git] / include / linux / crush / crush.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef CEPH_CRUSH_CRUSH_H
#define CEPH_CRUSH_CRUSH_H

#ifdef __KERNEL__
# include <linux/rbtree.h>
# 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) */
#define CRUSH_ITEM_NONE   0x7fffffff  /* no result */

/*
 * 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;
};

/* step op codes */
enum {
	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).  Items within a bucket are chosen using one of a
 * few different algorithms.  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
 *  tree            O(log n)   good         good
 *  straw           O(n)       better       better
 *  straw2          O(n)       optimal      optimal
 */
enum {
	CRUSH_BUCKET_UNIFORM = 1,
	CRUSH_BUCKET_LIST = 2,
	CRUSH_BUCKET_TREE = 3,
	CRUSH_BUCKET_STRAW = 4,
	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))

struct crush_bucket {
	__s32 id;        /* this'll be negative */
	__u16 type;      /* non-zero; type=0 is reserved for devices */
	__u8 alg;        /* one of CRUSH_BUCKET_* */
	__u8 hash;       /* which hash function to use, CRUSH_HASH_* */
	__u32 weight;    /* 16-bit fixed point */
	__u32 size;      /* num items */
	__s32 *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 {
#ifdef __KERNEL__
	struct rb_node node;
	s64 choose_args_index;
#endif
	struct crush_choose_arg *args; /*!< replacement for each bucket
                                            in the crushmap */
	__u32 size;                    /*!< size of the __args__ array */
};

struct crush_bucket_uniform {
	struct crush_bucket h;
	__u32 item_weight;  /* 16-bit fixed point; all items equally weighted */
};

struct crush_bucket_list {
	struct crush_bucket h;
	__u32 *item_weights;  /* 16-bit fixed point */
	__u32 *sum_weights;   /* 16-bit fixed point.  element i is sum
				 of weights 0..i, inclusive */
};

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 */
};

struct crush_bucket_straw2 {
	struct crush_bucket h;
	__u32 *item_weights;   /* 16-bit fixed point */
};


/*
 * CRUSH map includes all buckets, rules, etc.
 */
struct crush_map {
	struct crush_bucket **buckets;
	struct crush_rule **rules;

	__s32 max_buckets;
	__u32 max_rules;
	__s32 max_devices;

	/* choose local retries before re-descent */
	__u32 choose_local_tries;
	/* choose local attempts using a fallback permutation before
	 * re-descent */
	__u32 choose_local_fallback_tries;
	/* choose attempts before giving up */
	__u32 choose_total_tries;
	/* 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;

	/* 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;

	/* if true, it makes chooseleaf firstn to return stable results (if
	 * no local retry) so that data migrations would be optimal when some
	 * device fails. */
	__u8 chooseleaf_stable;

	/*
	 * 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__
	/*
	 * version 0 (original) of straw_calc has various flaws.  version 1
	 * fixes a few of them.
	 */
	__u8 straw_calc_version;

	/*
	 * 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;
#else
	/* CrushWrapper::choose_args */
	struct rb_root choose_args;
#endif
};


/* crush.c */
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);
extern void crush_destroy_bucket(struct crush_bucket *b);
extern void crush_destroy_rule(struct crush_rule *r);
extern void crush_destroy(struct crush_map *map);

static inline int crush_calc_tree_node(int i)
{
	return ((i+1) << 1)-1;
}

/*
 * 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
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
5cd068c2 SW	2	#ifndef CEPH_CRUSH_CRUSH_H
5cd068c2 SW	3	#define CEPH_CRUSH_CRUSH_H
5ecc0a0f	4
b459be73	5	#ifdef __KERNEL__
5cf9c4a9	6	# include <linux/rbtree.h>
b459be73 ID	7	# include <linux/types.h>
	8	#else
	9	# include "crush_compat.h"
	10	#endif
5ecc0a0f SW	11
	12	/*
	13	* CRUSH is a pseudo-random data distribution algorithm that
	14	* efficiently distributes input values (typically, data objects)
	15	* across a heterogeneous, structured storage cluster.
	16	*
	17	* The algorithm was originally described in detail in this paper
	18	* (although the algorithm has evolved somewhat since then):
	19	*
	20	* http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
	21	*
	22	* LGPL2
	23	*/
	24
	25
	26	#define CRUSH_MAGIC 0x00010000ul /* for detecting algorithm revisions */
	27
5ecc0a0f	28	#define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */
b459be73 ID	29	#define CRUSH_MAX_RULESET (1<<8) /* max crush ruleset number */
b459be73 ID	30	#define CRUSH_MAX_RULES CRUSH_MAX_RULESET /* should be the same as max rulesets */
5ecc0a0f	31
b459be73 ID	32	#define CRUSH_MAX_DEVICE_WEIGHT (100u * 0x10000u)
b459be73 ID	33	#define CRUSH_MAX_BUCKET_WEIGHT (65535u * 0x10000u)
5ecc0a0f	34
9a3b490a ID	35	#define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */
9a3b490a ID	36	#define CRUSH_ITEM_NONE 0x7fffffff /* no result */
c6d98a60	37
5ecc0a0f SW	38	/*
	39	* CRUSH uses user-defined "rules" to describe how inputs should be
	40	* mapped to devices. A rule consists of sequence of steps to perform
	41	* to generate the set of output devices.
	42	*/
	43	struct crush_rule_step {
	44	__u32 op;
	45	__s32 arg1;
	46	__s32 arg2;
	47	};
	48
	49	/* step op codes */
	50	enum {
	51	CRUSH_RULE_NOOP = 0,
	52	CRUSH_RULE_TAKE = 1, /* arg1 = value to start with */
	53	CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */
	54	/* arg2 = type */
	55	CRUSH_RULE_CHOOSE_INDEP = 3, /* same */
	56	CRUSH_RULE_EMIT = 4, /* no args */
917edad5 ID	57	CRUSH_RULE_CHOOSELEAF_FIRSTN = 6,
917edad5 ID	58	CRUSH_RULE_CHOOSELEAF_INDEP = 7,
be3226ac	59
cc10df4a	60	CRUSH_RULE_SET_CHOOSE_TRIES = 8, /* override choose_total_tries */
917edad5	61	CRUSH_RULE_SET_CHOOSELEAF_TRIES = 9, /* override chooseleaf_descend_once */
f046bf92 ID	62	CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES = 10,
f046bf92 ID	63	CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES = 11,
dc6ae6d8 ID	64	CRUSH_RULE_SET_CHOOSELEAF_VARY_R = 12,
dc6ae6d8 ID	65	CRUSH_RULE_SET_CHOOSELEAF_STABLE = 13
5ecc0a0f SW	66	};
	67
	68	/*
	69	* for specifying choose num (arg1) relative to the max parameter
	70	* passed to do_rule
	71	*/
	72	#define CRUSH_CHOOSE_N 0
	73	#define CRUSH_CHOOSE_N_MINUS(x) (-(x))
	74
	75	/*
	76	* The rule mask is used to describe what the rule is intended for.
	77	* Given a ruleset and size of output set, we search through the
	78	* rule list for a matching rule_mask.
	79	*/
	80	struct crush_rule_mask {
	81	__u8 ruleset;
	82	__u8 type;
	83	__u8 min_size;
	84	__u8 max_size;
	85	};
	86
	87	struct crush_rule {
	88	__u32 len;
	89	struct crush_rule_mask mask;
	90	struct crush_rule_step steps[0];
	91	};
	92
	93	#define crush_rule_size(len) (sizeof(struct crush_rule) + \
	94	(len)*sizeof(struct crush_rule_step))
	95
	96
	97
	98	/*
	99	* A bucket is a named container of other items (either devices or
	100	* other buckets). Items within a bucket are chosen using one of a
	101	* few different algorithms. The table summarizes how the speed of
	102	* each option measures up against mapping stability when items are
	103	* added or removed.
	104	*
	105	* Bucket Alg Speed Additions Removals
	106	* ------------------------------------------------
	107	* uniform O(1) poor poor
	108	* list O(n) optimal poor
	109	* tree O(log n) good good
958a2765 ID	110	* straw O(n) better better
958a2765 ID	111	* straw2 O(n) optimal optimal
5ecc0a0f SW	112	*/
	113	enum {
	114	CRUSH_BUCKET_UNIFORM = 1,
	115	CRUSH_BUCKET_LIST = 2,
	116	CRUSH_BUCKET_TREE = 3,
958a2765 ID	117	CRUSH_BUCKET_STRAW = 4,
958a2765 ID	118	CRUSH_BUCKET_STRAW2 = 5,
5ecc0a0f	119	};
c6cf7263	120	extern const char *crush_bucket_alg_name(int alg);
5ecc0a0f	121
b459be73 ID	122	/*
	123	* although tree was a legacy algorithm, it has been buggy, so
	124	* exclude it.
	125	*/
	126	#define CRUSH_LEGACY_ALLOWED_BUCKET_ALGS ( \
	127	(1 << CRUSH_BUCKET_UNIFORM) \| \
	128	(1 << CRUSH_BUCKET_LIST) \| \
	129	(1 << CRUSH_BUCKET_STRAW))
	130
5ecc0a0f SW	131	struct crush_bucket {
	132	__s32 id; /* this'll be negative */
	133	__u16 type; /* non-zero; type=0 is reserved for devices */
fb690390 SW	134	__u8 alg; /* one of CRUSH_BUCKET_* */
fb690390 SW	135	__u8 hash; /* which hash function to use, CRUSH_HASH_* */
5ecc0a0f SW	136	__u32 weight; /* 16-bit fixed point */
	137	__u32 size; /* num items */
	138	__s32 *items;
	139
5ecc0a0f SW	140	};
5ecc0a0f SW	141
069f3222 ID	142	/** @ingroup API
	143	*
	144	* Replacement weights for each item in a bucket. The size of the
	145	* array must be exactly the size of the straw2 bucket, just as the
	146	* item_weights array.
	147	*
	148	*/
	149	struct crush_weight_set {
	150	__u32 weights; /!< 16.16 fixed point weights
	151	in the same order as items */
	152	__u32 size; /!< size of the __weights__ array /
	153	};
	154
	155	/** @ingroup API
	156	*
	157	* Replacement weights and ids for a given straw2 bucket, for
	158	* placement purposes.
	159	*
	160	* When crush_do_rule() chooses the Nth item from a straw2 bucket, the
	161	* replacement weights found at __weight_set[N]__ are used instead of
	162	* the weights from __item_weights__. If __N__ is greater than
	163	* __weight_set_size__, the weights found at __weight_set_size-1__ are
	164	* used instead. For instance if __weight_set__ is:
	165	*
	166	* [ [ 0x10000, 0x20000 ], // position 0
	167	* [ 0x20000, 0x40000 ] ] // position 1
	168	*
	169	* choosing the 0th item will use position 0 weights [ 0x10000, 0x20000 ]
	170	* choosing the 1th item will use position 1 weights [ 0x20000, 0x40000 ]
	171	* choosing the 2th item will use position 1 weights [ 0x20000, 0x40000 ]
	172	* etc.
	173	*
	174	*/
	175	struct crush_choose_arg {
	176	__s32 ids; /!< values to use instead of items */
	177	__u32 ids_size; /!< size of the __ids__ array /
	178	struct crush_weight_set weight_set; /!< weight replacements for
	179	a given position */
	180	__u32 weight_set_size; /!< size of the __weight_set__ array /
	181	};
	182
	183	/** @ingroup API
	184	*
	185	* Replacement weights and ids for each bucket in the crushmap. The
	186	* __size__ of the __args__ array must be exactly the same as the
	187	* __map->max_buckets__.
	188	*
	189	* The __crush_choose_arg__ at index N will be used when choosing
	190	* an item from the bucket __map->buckets[N]__ bucket, provided it
	191	* is a straw2 bucket.
	192	*
	193	*/
	194	struct crush_choose_arg_map {
5cf9c4a9 ID	195	#ifdef __KERNEL__
5cf9c4a9 ID	196	struct rb_node node;
e17e8969	197	s64 choose_args_index;
5cf9c4a9	198	#endif
069f3222 ID	199	struct crush_choose_arg args; /!< replacement for each bucket
	200	in the crushmap */
	201	__u32 size; /!< size of the __args__ array /
	202	};
	203
5ecc0a0f SW	204	struct crush_bucket_uniform {
	205	struct crush_bucket h;
	206	__u32 item_weight; /* 16-bit fixed point; all items equally weighted */
	207	};
	208
	209	struct crush_bucket_list {
	210	struct crush_bucket h;
	211	__u32 item_weights; / 16-bit fixed point */
	212	__u32 sum_weights; / 16-bit fixed point. element i is sum
	213	of weights 0..i, inclusive */
	214	};
	215
	216	struct crush_bucket_tree {
	217	struct crush_bucket h; /* note: h.size is _tree_ size, not number of
	218	actual items */
	219	__u8 num_nodes;
	220	__u32 *node_weights;
	221	};
	222
	223	struct crush_bucket_straw {
	224	struct crush_bucket h;
	225	__u32 item_weights; / 16-bit fixed point */
	226	__u32 straws; / 16-bit fixed point */
	227	};
	228
958a2765 ID	229	struct crush_bucket_straw2 {
	230	struct crush_bucket h;
	231	__u32 item_weights; / 16-bit fixed point */
	232	};
	233
5ecc0a0f SW	234
	235
	236	/*
	237	* CRUSH map includes all buckets, rules, etc.
	238	*/
	239	struct crush_map {
	240	struct crush_bucket **buckets;
	241	struct crush_rule **rules;
	242
5ecc0a0f SW	243	__s32 max_buckets;
	244	__u32 max_rules;
	245	__s32 max_devices;
546f04ef SW	246
	247	/* choose local retries before re-descent */
	248	__u32 choose_local_tries;
	249	/* choose local attempts using a fallback permutation before
	250	* re-descent */
	251	__u32 choose_local_fallback_tries;
b459be73	252	/* choose attempts before giving up */
546f04ef	253	__u32 choose_total_tries;
f18650ac ID	254	/* attempt chooseleaf inner descent once for firstn mode; on
	255	* reject retry outer descent. Note that this does not
	256	* apply to a collision: in that case we will retry as we used
	257	* to. */
1604f488	258	__u32 chooseleaf_descend_once;
e2b149cc ID	259
	260	/* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1)
	261	* bits. a value of 1 is best for new clusters. for legacy clusters
	262	* that want to limit reshuffling, a value of 3 or 4 will make the
	263	* mappings line up a bit better with previous mappings. */
	264	__u8 chooseleaf_vary_r;
b459be73	265
dc6ae6d8 ID	266	/* if true, it makes chooseleaf firstn to return stable results (if
	267	* no local retry) so that data migrations would be optimal when some
	268	* device fails. */
	269	__u8 chooseleaf_stable;
	270
66a0e2d5 ID	271	/*
	272	* This value is calculated after decode or construction by
	273	* the builder. It is exposed here (rather than having a
	274	* 'build CRUSH working space' function) so that callers can
	275	* reserve a static buffer, allocate space on the stack, or
	276	* otherwise avoid calling into the heap allocator if they
	277	* want to. The size of the working space depends on the map,
	278	* while the size of the scratch vector passed to the mapper
	279	* depends on the size of the desired result set.
	280	*
	281	* Nothing stops the caller from allocating both in one swell
	282	* foop and passing in two points, though.
	283	*/
	284	size_t working_size;
	285
b459be73 ID	286	#ifndef __KERNEL__
	287	/*
	288	* version 0 (original) of straw_calc has various flaws. version 1
	289	* fixes a few of them.
	290	*/
	291	__u8 straw_calc_version;
	292
	293	/*
	294	* allowed bucket algs is a bitmask, here the bit positions
	295	* are CRUSH_BUCKET_. note that these are bits* and
	296	* CRUSH_BUCKET_* values are not, so we need to or together (1
	297	* << CRUSH_BUCKET_WHATEVER). The 0th bit is not used to
	298	* minimize confusion (bucket type values start at 1).
	299	*/
	300	__u32 allowed_bucket_algs;
	301
	302	__u32 *choose_tries;
5cf9c4a9 ID	303	#else
	304	/* CrushWrapper::choose_args */
	305	struct rb_root choose_args;
b459be73	306	#endif
5ecc0a0f SW	307	};
	308
	309
	310	/* crush.c */
8b12d47b	311	extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos);
5ecc0a0f SW	312	extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b);
	313	extern void crush_destroy_bucket_list(struct crush_bucket_list *b);
	314	extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b);
	315	extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b);
958a2765	316	extern void crush_destroy_bucket_straw2(struct crush_bucket_straw2 *b);
5ecc0a0f	317	extern void crush_destroy_bucket(struct crush_bucket *b);
bfb16d7d	318	extern void crush_destroy_rule(struct crush_rule *r);
5ecc0a0f SW	319	extern void crush_destroy(struct crush_map *map);
5ecc0a0f SW	320
f671d4cd SW	321	static inline int crush_calc_tree_node(int i)
	322	{
	323	return ((i+1) << 1)-1;
	324	}
	325
66a0e2d5 ID	326	/*
	327	* These data structures are private to the CRUSH implementation. They
	328	* are exposed in this header file because builder needs their
	329	* definitions to calculate the total working size.
	330	*
	331	* Moving this out of the crush map allow us to treat the CRUSH map as
	332	* immutable within the mapper and removes the requirement for a CRUSH
	333	* map lock.
	334	*/
	335	struct crush_work_bucket {
	336	__u32 perm_x; /* @x for which perm is defined /
	337	__u32 perm_n; /* num elements of perm that are permuted/defined /
	338	__u32 perm; / Permutation of the bucket's items */
	339	};
	340
	341	struct crush_work {
	342	struct crush_work_bucket *work; / Per-bucket working store */
	343	};
	344
5ecc0a0f	345	#endif