linux/crush/crush.h

1 /* SPDX-License-Identifier: GPL-2.0 */
13  * CRUSH is a pseudo-random data distribution algorithm that
20  *     https://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
39  * CRUSH uses user-defined "rules" to describe how inputs should be
73 #define CRUSH_CHOOSE_N_MINUS(x)   (-(x))
77  * Given a ruleset and size of output set, we search through the
106  *  ------------------------------------------------
133 	__u16 type;      /* non-zero; type=0 is reserved for devices */
136 	__u32 weight;    /* 16-bit fixed point */
137 	__u32 size;      /* num items */  member
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
150 	__u32 *weights; /*!< 16.16 fixed point weights
152 	__u32 size;     /*!< size of the __weights__ array */  member
163  * __weight_set_size__, the weights found at __weight_set_size-1__ are
177 	__u32 ids_size;        /*!< size of the __ids__ array */
180 	__u32 weight_set_size; /*!< size of the __weight_set__ array */
187  * __map->max_buckets__.
190  * an item from the bucket __map->buckets[N]__ bucket, provided it
201 	__u32 size;                    /*!< size of the __args__ array */  member
206 	__u32 item_weight;  /* 16-bit fixed point; all items equally weighted */
211 	__u32 *item_weights;  /* 16-bit fixed point */
212 	__u32 *sum_weights;   /* 16-bit fixed point.  element i is sum
217 	struct crush_bucket h;  /* note: h.size is _tree_ size, not number of
225 	__u32 *item_weights;   /* 16-bit fixed point */
226 	__u32 *straws;         /* 16-bit fixed point */
231 	__u32 *item_weights;   /* 16-bit fixed point */
247 	/* choose local retries before re-descent */
250 	 * re-descent */
260 	/* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1)
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.
304 	/* device/bucket type id -> type name (CrushWrapper::type_map) */
307 	/* device/bucket id -> name (CrushWrapper::name_map) */
329 	return ((i+1) << 1)-1;  in crush_calc_tree_node()
335  * definitions to calculate the total working size.
348 	struct crush_work_bucket **work; /* Per-bucket working store */