ceph/crush/mapper.c

58  * bucket choose methods
60  * For each bucket algorithm, we have a "choose" method that, given a
62  * will produce an item in the bucket.
66  * Choose based on a random permutation of the bucket.
70  * calculate an actual random permutation of the bucket members.
74 static int bucket_perm_choose(const struct crush_bucket *bucket,
78 	unsigned int pr = r % bucket->size;
83 		dprintk("bucket %d new x=%d\n", bucket->id, x);
88 			s = crush_hash32_3(bucket->hash, x, bucket->id, 0) %
89 				bucket->size;
95 		for (i = 0; i < bucket->size; i++)
100 		for (i = 1; i < bucket->size; i++)
112 		if (p < bucket->size - 1) {
113 			i = crush_hash32_3(bucket->hash, x, bucket->id, p) %
114 				(bucket->size - p);
124 	for (i = 0; i < bucket->size; i++)
129 	dprintk(" perm_choose %d sz=%d x=%d r=%d (%d) s=%d\n", bucket->id,
130 		bucket->size, x, r, pr, s);
131 	return bucket->items[s];
135 static int bucket_uniform_choose(const struct crush_bucket_uniform *bucket,
138 	return bucket_perm_choose(&bucket->h, work, x, r);
142 static int bucket_list_choose(const struct crush_bucket_list *bucket,
147 	for (i = bucket->h.size-1; i >= 0; i--) {
148 		__u64 w = crush_hash32_4(bucket->h.hash, x, bucket->h.items[i],
149 					 r, bucket->h.id);
153 			i, x, r, bucket->h.items[i], bucket->item_weights[i],
154 			bucket->sum_weights[i], w);
155 		w *= bucket->sum_weights[i];
158 		if (w < bucket->item_weights[i]) {
159 			return bucket->h.items[i];
163 	dprintk("bad list sums for bucket %d\n", bucket->h.id);
164 	return bucket->h.items[0];
196 static int bucket_tree_choose(const struct crush_bucket_tree *bucket,
204 	n = bucket->num_nodes >> 1;
209 		w = bucket->node_weights[n];
210 		t = (__u64)crush_hash32_4(bucket->h.hash, x, n, r,
211 					  bucket->h.id) * (__u64)w;
216 		if (t < bucket->node_weights[l])
222 	return bucket->h.items[n >> 1];
228 static int bucket_straw_choose(const struct crush_bucket_straw *bucket,
236 	for (i = 0; i < bucket->h.size; i++) {
237 		draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r);
239 		draw *= bucket->straws[i];
245 	return bucket->h.items[high];
305 static __u32 *get_choose_arg_weights(const struct crush_bucket_straw2 *bucket,
310 		return bucket->item_weights;
317 static __s32 *get_choose_arg_ids(const struct crush_bucket_straw2 *bucket,
321 		return bucket->h.items;
326 static int bucket_straw2_choose(const struct crush_bucket_straw2 *bucket,
334 	__u32 *weights = get_choose_arg_weights(bucket, arg, position);
335 	__s32 *ids = get_choose_arg_ids(bucket, arg);
337 	for (i = 0; i < bucket->h.size; i++) {
340 			u = crush_hash32_3(bucket->h.hash, x, ids[i], r);
372 	return bucket->h.items[high];
404 		dprintk("unknown bucket %d alg %d\n", in->id, in->alg);
432  * @bucket: the bucket we are choose an item from
451 			       const struct crush_bucket *bucket,
470 	const struct crush_bucket *in = bucket;
478 	dprintk("CHOOSE%s bucket %d x %d outpos %d numrep %d tries %d recurse_tries %d local_retries %d local_fallback_retries %d parent_r %d stable %d\n",
480 		bucket->id, x, outpos, numrep,
490 			in = bucket;               /* initial bucket */
501 				/* bucket choose */
603 						/* exhaustive bucket search */
645 			       const struct crush_bucket *bucket,
656 	const struct crush_bucket *in = bucket;
666 	dprintk("CHOOSE%s INDEP bucket %d x %d outpos %d numrep %d\n", recurse_to_leaf ? "_LEAF" : "",
667 		bucket->id, x, outpos, numrep);
695 			in = bucket;  /* initial bucket */
701 				 * if the first layer chooses the same bucket
703 				 * choose a different item in that bucket.
718 				/* bucket choose */
720 					dprintk("   empty bucket\n");
892  * @choose_args: weights and ids for each known bucket
1013 				/* make sure bucket id is valid */