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

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

};

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;
#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
5cd068c2 SW	1	#ifndef CEPH_CRUSH_CRUSH_H
5cd068c2 SW	2	#define CEPH_CRUSH_CRUSH_H
5ecc0a0f	3
b459be73 ID	4	#ifdef __KERNEL__
	5	# include <linux/types.h>
	6	#else
	7	# include "crush_compat.h"
	8	#endif
5ecc0a0f SW	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
5ecc0a0f	26	#define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */
b459be73 ID	27	#define CRUSH_MAX_RULESET (1<<8) /* max crush ruleset number */
b459be73 ID	28	#define CRUSH_MAX_RULES CRUSH_MAX_RULESET /* should be the same as max rulesets */
5ecc0a0f	29
b459be73 ID	30	#define CRUSH_MAX_DEVICE_WEIGHT (100u * 0x10000u)
b459be73 ID	31	#define CRUSH_MAX_BUCKET_WEIGHT (65535u * 0x10000u)
5ecc0a0f	32
9a3b490a ID	33	#define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */
9a3b490a ID	34	#define CRUSH_ITEM_NONE 0x7fffffff /* no result */
c6d98a60	35
5ecc0a0f SW	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 */
917edad5 ID	55	CRUSH_RULE_CHOOSELEAF_FIRSTN = 6,
917edad5 ID	56	CRUSH_RULE_CHOOSELEAF_INDEP = 7,
be3226ac	57
cc10df4a	58	CRUSH_RULE_SET_CHOOSE_TRIES = 8, /* override choose_total_tries */
917edad5	59	CRUSH_RULE_SET_CHOOSELEAF_TRIES = 9, /* override chooseleaf_descend_once */
f046bf92 ID	60	CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES = 10,
f046bf92 ID	61	CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES = 11,
dc6ae6d8 ID	62	CRUSH_RULE_SET_CHOOSELEAF_VARY_R = 12,
dc6ae6d8 ID	63	CRUSH_RULE_SET_CHOOSELEAF_STABLE = 13
5ecc0a0f SW	64	};
	65
	66	/*
	67	* for specifying choose num (arg1) relative to the max parameter
	68	* passed to do_rule
	69	*/
	70	#define CRUSH_CHOOSE_N 0
	71	#define CRUSH_CHOOSE_N_MINUS(x) (-(x))
	72
	73	/*
	74	* The rule mask is used to describe what the rule is intended for.
	75	* Given a ruleset and size of output set, we search through the
	76	* rule list for a matching rule_mask.
	77	*/
	78	struct crush_rule_mask {
	79	__u8 ruleset;
	80	__u8 type;
	81	__u8 min_size;
	82	__u8 max_size;
	83	};
	84
	85	struct crush_rule {
	86	__u32 len;
	87	struct crush_rule_mask mask;
	88	struct crush_rule_step steps[0];
	89	};
	90
	91	#define crush_rule_size(len) (sizeof(struct crush_rule) + \
	92	(len)*sizeof(struct crush_rule_step))
	93
	94
	95
	96	/*
	97	* A bucket is a named container of other items (either devices or
	98	* other buckets). Items within a bucket are chosen using one of a
	99	* few different algorithms. The table summarizes how the speed of
	100	* each option measures up against mapping stability when items are
	101	* added or removed.
	102	*
	103	* Bucket Alg Speed Additions Removals
	104	* ------------------------------------------------
	105	* uniform O(1) poor poor
	106	* list O(n) optimal poor
	107	* tree O(log n) good good
958a2765 ID	108	* straw O(n) better better
958a2765 ID	109	* straw2 O(n) optimal optimal
5ecc0a0f SW	110	*/
	111	enum {
	112	CRUSH_BUCKET_UNIFORM = 1,
	113	CRUSH_BUCKET_LIST = 2,
	114	CRUSH_BUCKET_TREE = 3,
958a2765 ID	115	CRUSH_BUCKET_STRAW = 4,
958a2765 ID	116	CRUSH_BUCKET_STRAW2 = 5,
5ecc0a0f	117	};
c6cf7263	118	extern const char *crush_bucket_alg_name(int alg);
5ecc0a0f	119
b459be73 ID	120	/*
	121	* although tree was a legacy algorithm, it has been buggy, so
	122	* exclude it.
	123	*/
	124	#define CRUSH_LEGACY_ALLOWED_BUCKET_ALGS ( \
	125	(1 << CRUSH_BUCKET_UNIFORM) \| \
	126	(1 << CRUSH_BUCKET_LIST) \| \
	127	(1 << CRUSH_BUCKET_STRAW))
	128
5ecc0a0f SW	129	struct crush_bucket {
	130	__s32 id; /* this'll be negative */
	131	__u16 type; /* non-zero; type=0 is reserved for devices */
fb690390 SW	132	__u8 alg; /* one of CRUSH_BUCKET_* */
fb690390 SW	133	__u8 hash; /* which hash function to use, CRUSH_HASH_* */
5ecc0a0f SW	134	__u32 weight; /* 16-bit fixed point */
	135	__u32 size; /* num items */
	136	__s32 *items;
	137
5ecc0a0f SW	138	};
	139
	140	struct crush_bucket_uniform {
	141	struct crush_bucket h;
	142	__u32 item_weight; /* 16-bit fixed point; all items equally weighted */
	143	};
	144
	145	struct crush_bucket_list {
	146	struct crush_bucket h;
	147	__u32 item_weights; / 16-bit fixed point */
	148	__u32 sum_weights; / 16-bit fixed point. element i is sum
	149	of weights 0..i, inclusive */
	150	};
	151
	152	struct crush_bucket_tree {
	153	struct crush_bucket h; /* note: h.size is _tree_ size, not number of
	154	actual items */
	155	__u8 num_nodes;
	156	__u32 *node_weights;
	157	};
	158
	159	struct crush_bucket_straw {
	160	struct crush_bucket h;
	161	__u32 item_weights; / 16-bit fixed point */
	162	__u32 straws; / 16-bit fixed point */
	163	};
	164
958a2765 ID	165	struct crush_bucket_straw2 {
	166	struct crush_bucket h;
	167	__u32 item_weights; / 16-bit fixed point */
	168	};
	169
5ecc0a0f SW	170
	171
	172	/*
	173	* CRUSH map includes all buckets, rules, etc.
	174	*/
	175	struct crush_map {
	176	struct crush_bucket **buckets;
	177	struct crush_rule **rules;
	178
5ecc0a0f SW	179	__s32 max_buckets;
	180	__u32 max_rules;
	181	__s32 max_devices;
546f04ef SW	182
	183	/* choose local retries before re-descent */
	184	__u32 choose_local_tries;
	185	/* choose local attempts using a fallback permutation before
	186	* re-descent */
	187	__u32 choose_local_fallback_tries;
b459be73	188	/* choose attempts before giving up */
546f04ef	189	__u32 choose_total_tries;
f18650ac ID	190	/* attempt chooseleaf inner descent once for firstn mode; on
	191	* reject retry outer descent. Note that this does not
	192	* apply to a collision: in that case we will retry as we used
	193	* to. */
1604f488	194	__u32 chooseleaf_descend_once;
e2b149cc ID	195
	196	/* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1)
	197	* bits. a value of 1 is best for new clusters. for legacy clusters
	198	* that want to limit reshuffling, a value of 3 or 4 will make the
	199	* mappings line up a bit better with previous mappings. */
	200	__u8 chooseleaf_vary_r;
b459be73	201
dc6ae6d8 ID	202	/* if true, it makes chooseleaf firstn to return stable results (if
	203	* no local retry) so that data migrations would be optimal when some
	204	* device fails. */
	205	__u8 chooseleaf_stable;
	206
66a0e2d5 ID	207	/*
	208	* This value is calculated after decode or construction by
	209	* the builder. It is exposed here (rather than having a
	210	* 'build CRUSH working space' function) so that callers can
	211	* reserve a static buffer, allocate space on the stack, or
	212	* otherwise avoid calling into the heap allocator if they
	213	* want to. The size of the working space depends on the map,
	214	* while the size of the scratch vector passed to the mapper
	215	* depends on the size of the desired result set.
	216	*
	217	* Nothing stops the caller from allocating both in one swell
	218	* foop and passing in two points, though.
	219	*/
	220	size_t working_size;
	221
b459be73 ID	222	#ifndef __KERNEL__
	223	/*
	224	* version 0 (original) of straw_calc has various flaws. version 1
	225	* fixes a few of them.
	226	*/
	227	__u8 straw_calc_version;
	228
	229	/*
	230	* allowed bucket algs is a bitmask, here the bit positions
	231	* are CRUSH_BUCKET_. note that these are bits* and
	232	* CRUSH_BUCKET_* values are not, so we need to or together (1
	233	* << CRUSH_BUCKET_WHATEVER). The 0th bit is not used to
	234	* minimize confusion (bucket type values start at 1).
	235	*/
	236	__u32 allowed_bucket_algs;
	237
	238	__u32 *choose_tries;
	239	#endif
5ecc0a0f SW	240	};
	241
	242
	243	/* crush.c */
8b12d47b	244	extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos);
5ecc0a0f SW	245	extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b);
	246	extern void crush_destroy_bucket_list(struct crush_bucket_list *b);
	247	extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b);
	248	extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b);
958a2765	249	extern void crush_destroy_bucket_straw2(struct crush_bucket_straw2 *b);
5ecc0a0f	250	extern void crush_destroy_bucket(struct crush_bucket *b);
bfb16d7d	251	extern void crush_destroy_rule(struct crush_rule *r);
5ecc0a0f SW	252	extern void crush_destroy(struct crush_map *map);
5ecc0a0f SW	253
f671d4cd SW	254	static inline int crush_calc_tree_node(int i)
	255	{
	256	return ((i+1) << 1)-1;
	257	}
	258
66a0e2d5 ID	259	/*
	260	* These data structures are private to the CRUSH implementation. They
	261	* are exposed in this header file because builder needs their
	262	* definitions to calculate the total working size.
	263	*
	264	* Moving this out of the crush map allow us to treat the CRUSH map as
	265	* immutable within the mapper and removes the requirement for a CRUSH
	266	* map lock.
	267	*/
	268	struct crush_work_bucket {
	269	__u32 perm_x; /* @x for which perm is defined /
	270	__u32 perm_n; /* num elements of perm that are permuted/defined /
	271	__u32 perm; / Permutation of the bucket's items */
	272	};
	273
	274	struct crush_work {
	275	struct crush_work_bucket *work; / Per-bucket working store */
	276	};
	277
5ecc0a0f	278	#endif