xref: /openbmc/linux/net/ceph/crush/mapper.c (revision afc98d90)
1 
2 #ifdef __KERNEL__
3 # include <linux/string.h>
4 # include <linux/slab.h>
5 # include <linux/bug.h>
6 # include <linux/kernel.h>
7 # ifndef dprintk
8 #  define dprintk(args...)
9 # endif
10 #else
11 # include <string.h>
12 # include <stdio.h>
13 # include <stdlib.h>
14 # include <assert.h>
15 # define BUG_ON(x) assert(!(x))
16 # define dprintk(args...) /* printf(args) */
17 # define kmalloc(x, f) malloc(x)
18 # define kfree(x) free(x)
19 #endif
20 
21 #include <linux/crush/crush.h>
22 #include <linux/crush/hash.h>
23 #include <linux/crush/mapper.h>
24 
25 /*
26  * Implement the core CRUSH mapping algorithm.
27  */
28 
29 /**
30  * crush_find_rule - find a crush_rule id for a given ruleset, type, and size.
31  * @map: the crush_map
32  * @ruleset: the storage ruleset id (user defined)
33  * @type: storage ruleset type (user defined)
34  * @size: output set size
35  */
36 int crush_find_rule(const struct crush_map *map, int ruleset, int type, int size)
37 {
38 	__u32 i;
39 
40 	for (i = 0; i < map->max_rules; i++) {
41 		if (map->rules[i] &&
42 		    map->rules[i]->mask.ruleset == ruleset &&
43 		    map->rules[i]->mask.type == type &&
44 		    map->rules[i]->mask.min_size <= size &&
45 		    map->rules[i]->mask.max_size >= size)
46 			return i;
47 	}
48 	return -1;
49 }
50 
51 
52 /*
53  * bucket choose methods
54  *
55  * For each bucket algorithm, we have a "choose" method that, given a
56  * crush input @x and replica position (usually, position in output set) @r,
57  * will produce an item in the bucket.
58  */
59 
60 /*
61  * Choose based on a random permutation of the bucket.
62  *
63  * We used to use some prime number arithmetic to do this, but it
64  * wasn't very random, and had some other bad behaviors.  Instead, we
65  * calculate an actual random permutation of the bucket members.
66  * Since this is expensive, we optimize for the r=0 case, which
67  * captures the vast majority of calls.
68  */
69 static int bucket_perm_choose(struct crush_bucket *bucket,
70 			      int x, int r)
71 {
72 	unsigned int pr = r % bucket->size;
73 	unsigned int i, s;
74 
75 	/* start a new permutation if @x has changed */
76 	if (bucket->perm_x != (__u32)x || bucket->perm_n == 0) {
77 		dprintk("bucket %d new x=%d\n", bucket->id, x);
78 		bucket->perm_x = x;
79 
80 		/* optimize common r=0 case */
81 		if (pr == 0) {
82 			s = crush_hash32_3(bucket->hash, x, bucket->id, 0) %
83 				bucket->size;
84 			bucket->perm[0] = s;
85 			bucket->perm_n = 0xffff;   /* magic value, see below */
86 			goto out;
87 		}
88 
89 		for (i = 0; i < bucket->size; i++)
90 			bucket->perm[i] = i;
91 		bucket->perm_n = 0;
92 	} else if (bucket->perm_n == 0xffff) {
93 		/* clean up after the r=0 case above */
94 		for (i = 1; i < bucket->size; i++)
95 			bucket->perm[i] = i;
96 		bucket->perm[bucket->perm[0]] = 0;
97 		bucket->perm_n = 1;
98 	}
99 
100 	/* calculate permutation up to pr */
101 	for (i = 0; i < bucket->perm_n; i++)
102 		dprintk(" perm_choose have %d: %d\n", i, bucket->perm[i]);
103 	while (bucket->perm_n <= pr) {
104 		unsigned int p = bucket->perm_n;
105 		/* no point in swapping the final entry */
106 		if (p < bucket->size - 1) {
107 			i = crush_hash32_3(bucket->hash, x, bucket->id, p) %
108 				(bucket->size - p);
109 			if (i) {
110 				unsigned int t = bucket->perm[p + i];
111 				bucket->perm[p + i] = bucket->perm[p];
112 				bucket->perm[p] = t;
113 			}
114 			dprintk(" perm_choose swap %d with %d\n", p, p+i);
115 		}
116 		bucket->perm_n++;
117 	}
118 	for (i = 0; i < bucket->size; i++)
119 		dprintk(" perm_choose  %d: %d\n", i, bucket->perm[i]);
120 
121 	s = bucket->perm[pr];
122 out:
123 	dprintk(" perm_choose %d sz=%d x=%d r=%d (%d) s=%d\n", bucket->id,
124 		bucket->size, x, r, pr, s);
125 	return bucket->items[s];
126 }
127 
128 /* uniform */
129 static int bucket_uniform_choose(struct crush_bucket_uniform *bucket,
130 				 int x, int r)
131 {
132 	return bucket_perm_choose(&bucket->h, x, r);
133 }
134 
135 /* list */
136 static int bucket_list_choose(struct crush_bucket_list *bucket,
137 			      int x, int r)
138 {
139 	int i;
140 
141 	for (i = bucket->h.size-1; i >= 0; i--) {
142 		__u64 w = crush_hash32_4(bucket->h.hash,x, bucket->h.items[i],
143 					 r, bucket->h.id);
144 		w &= 0xffff;
145 		dprintk("list_choose i=%d x=%d r=%d item %d weight %x "
146 			"sw %x rand %llx",
147 			i, x, r, bucket->h.items[i], bucket->item_weights[i],
148 			bucket->sum_weights[i], w);
149 		w *= bucket->sum_weights[i];
150 		w = w >> 16;
151 		/*dprintk(" scaled %llx\n", w);*/
152 		if (w < bucket->item_weights[i])
153 			return bucket->h.items[i];
154 	}
155 
156 	dprintk("bad list sums for bucket %d\n", bucket->h.id);
157 	return bucket->h.items[0];
158 }
159 
160 
161 /* (binary) tree */
162 static int height(int n)
163 {
164 	int h = 0;
165 	while ((n & 1) == 0) {
166 		h++;
167 		n = n >> 1;
168 	}
169 	return h;
170 }
171 
172 static int left(int x)
173 {
174 	int h = height(x);
175 	return x - (1 << (h-1));
176 }
177 
178 static int right(int x)
179 {
180 	int h = height(x);
181 	return x + (1 << (h-1));
182 }
183 
184 static int terminal(int x)
185 {
186 	return x & 1;
187 }
188 
189 static int bucket_tree_choose(struct crush_bucket_tree *bucket,
190 			      int x, int r)
191 {
192 	int n;
193 	__u32 w;
194 	__u64 t;
195 
196 	/* start at root */
197 	n = bucket->num_nodes >> 1;
198 
199 	while (!terminal(n)) {
200 		int l;
201 		/* pick point in [0, w) */
202 		w = bucket->node_weights[n];
203 		t = (__u64)crush_hash32_4(bucket->h.hash, x, n, r,
204 					  bucket->h.id) * (__u64)w;
205 		t = t >> 32;
206 
207 		/* descend to the left or right? */
208 		l = left(n);
209 		if (t < bucket->node_weights[l])
210 			n = l;
211 		else
212 			n = right(n);
213 	}
214 
215 	return bucket->h.items[n >> 1];
216 }
217 
218 
219 /* straw */
220 
221 static int bucket_straw_choose(struct crush_bucket_straw *bucket,
222 			       int x, int r)
223 {
224 	__u32 i;
225 	int high = 0;
226 	__u64 high_draw = 0;
227 	__u64 draw;
228 
229 	for (i = 0; i < bucket->h.size; i++) {
230 		draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r);
231 		draw &= 0xffff;
232 		draw *= bucket->straws[i];
233 		if (i == 0 || draw > high_draw) {
234 			high = i;
235 			high_draw = draw;
236 		}
237 	}
238 	return bucket->h.items[high];
239 }
240 
241 static int crush_bucket_choose(struct crush_bucket *in, int x, int r)
242 {
243 	dprintk(" crush_bucket_choose %d x=%d r=%d\n", in->id, x, r);
244 	BUG_ON(in->size == 0);
245 	switch (in->alg) {
246 	case CRUSH_BUCKET_UNIFORM:
247 		return bucket_uniform_choose((struct crush_bucket_uniform *)in,
248 					  x, r);
249 	case CRUSH_BUCKET_LIST:
250 		return bucket_list_choose((struct crush_bucket_list *)in,
251 					  x, r);
252 	case CRUSH_BUCKET_TREE:
253 		return bucket_tree_choose((struct crush_bucket_tree *)in,
254 					  x, r);
255 	case CRUSH_BUCKET_STRAW:
256 		return bucket_straw_choose((struct crush_bucket_straw *)in,
257 					   x, r);
258 	default:
259 		dprintk("unknown bucket %d alg %d\n", in->id, in->alg);
260 		return in->items[0];
261 	}
262 }
263 
264 /*
265  * true if device is marked "out" (failed, fully offloaded)
266  * of the cluster
267  */
268 static int is_out(const struct crush_map *map,
269 		  const __u32 *weight, int weight_max,
270 		  int item, int x)
271 {
272 	if (item >= weight_max)
273 		return 1;
274 	if (weight[item] >= 0x10000)
275 		return 0;
276 	if (weight[item] == 0)
277 		return 1;
278 	if ((crush_hash32_2(CRUSH_HASH_RJENKINS1, x, item) & 0xffff)
279 	    < weight[item])
280 		return 0;
281 	return 1;
282 }
283 
284 /**
285  * crush_choose_firstn - choose numrep distinct items of given type
286  * @map: the crush_map
287  * @bucket: the bucket we are choose an item from
288  * @x: crush input value
289  * @numrep: the number of items to choose
290  * @type: the type of item to choose
291  * @out: pointer to output vector
292  * @outpos: our position in that vector
293  * @tries: number of attempts to make
294  * @recurse_tries: number of attempts to have recursive chooseleaf make
295  * @local_tries: localized retries
296  * @local_fallback_tries: localized fallback retries
297  * @recurse_to_leaf: true if we want one device under each item of given type (chooseleaf instead of choose)
298  * @out2: second output vector for leaf items (if @recurse_to_leaf)
299  */
300 static int crush_choose_firstn(const struct crush_map *map,
301 			       struct crush_bucket *bucket,
302 			       const __u32 *weight, int weight_max,
303 			       int x, int numrep, int type,
304 			       int *out, int outpos,
305 			       unsigned int tries,
306 			       unsigned int recurse_tries,
307 			       unsigned int local_tries,
308 			       unsigned int local_fallback_tries,
309 			       int recurse_to_leaf,
310 			       int *out2)
311 {
312 	int rep;
313 	unsigned int ftotal, flocal;
314 	int retry_descent, retry_bucket, skip_rep;
315 	struct crush_bucket *in = bucket;
316 	int r;
317 	int i;
318 	int item = 0;
319 	int itemtype;
320 	int collide, reject;
321 
322 	dprintk("CHOOSE%s bucket %d x %d outpos %d numrep %d\n", recurse_to_leaf ? "_LEAF" : "",
323 		bucket->id, x, outpos, numrep);
324 
325 	for (rep = outpos; rep < numrep; rep++) {
326 		/* keep trying until we get a non-out, non-colliding item */
327 		ftotal = 0;
328 		skip_rep = 0;
329 		do {
330 			retry_descent = 0;
331 			in = bucket;               /* initial bucket */
332 
333 			/* choose through intervening buckets */
334 			flocal = 0;
335 			do {
336 				collide = 0;
337 				retry_bucket = 0;
338 				r = rep;
339 				/* r' = r + f_total */
340 				r += ftotal;
341 
342 				/* bucket choose */
343 				if (in->size == 0) {
344 					reject = 1;
345 					goto reject;
346 				}
347 				if (local_fallback_tries > 0 &&
348 				    flocal >= (in->size>>1) &&
349 				    flocal > local_fallback_tries)
350 					item = bucket_perm_choose(in, x, r);
351 				else
352 					item = crush_bucket_choose(in, x, r);
353 				if (item >= map->max_devices) {
354 					dprintk("   bad item %d\n", item);
355 					skip_rep = 1;
356 					break;
357 				}
358 
359 				/* desired type? */
360 				if (item < 0)
361 					itemtype = map->buckets[-1-item]->type;
362 				else
363 					itemtype = 0;
364 				dprintk("  item %d type %d\n", item, itemtype);
365 
366 				/* keep going? */
367 				if (itemtype != type) {
368 					if (item >= 0 ||
369 					    (-1-item) >= map->max_buckets) {
370 						dprintk("   bad item type %d\n", type);
371 						skip_rep = 1;
372 						break;
373 					}
374 					in = map->buckets[-1-item];
375 					retry_bucket = 1;
376 					continue;
377 				}
378 
379 				/* collision? */
380 				for (i = 0; i < outpos; i++) {
381 					if (out[i] == item) {
382 						collide = 1;
383 						break;
384 					}
385 				}
386 
387 				reject = 0;
388 				if (!collide && recurse_to_leaf) {
389 					if (item < 0) {
390 						if (crush_choose_firstn(map,
391 							 map->buckets[-1-item],
392 							 weight, weight_max,
393 							 x, outpos+1, 0,
394 							 out2, outpos,
395 							 recurse_tries, 0,
396 							 local_tries,
397 							 local_fallback_tries,
398 							 0,
399 							 NULL) <= outpos)
400 							/* didn't get leaf */
401 							reject = 1;
402 					} else {
403 						/* we already have a leaf! */
404 						out2[outpos] = item;
405 					}
406 				}
407 
408 				if (!reject) {
409 					/* out? */
410 					if (itemtype == 0)
411 						reject = is_out(map, weight,
412 								weight_max,
413 								item, x);
414 					else
415 						reject = 0;
416 				}
417 
418 reject:
419 				if (reject || collide) {
420 					ftotal++;
421 					flocal++;
422 
423 					if (collide && flocal <= local_tries)
424 						/* retry locally a few times */
425 						retry_bucket = 1;
426 					else if (local_fallback_tries > 0 &&
427 						 flocal <= in->size + local_fallback_tries)
428 						/* exhaustive bucket search */
429 						retry_bucket = 1;
430 					else if (ftotal <= tries)
431 						/* then retry descent */
432 						retry_descent = 1;
433 					else
434 						/* else give up */
435 						skip_rep = 1;
436 					dprintk("  reject %d  collide %d  "
437 						"ftotal %u  flocal %u\n",
438 						reject, collide, ftotal,
439 						flocal);
440 				}
441 			} while (retry_bucket);
442 		} while (retry_descent);
443 
444 		if (skip_rep) {
445 			dprintk("skip rep\n");
446 			continue;
447 		}
448 
449 		dprintk("CHOOSE got %d\n", item);
450 		out[outpos] = item;
451 		outpos++;
452 	}
453 
454 	dprintk("CHOOSE returns %d\n", outpos);
455 	return outpos;
456 }
457 
458 
459 /**
460  * crush_choose_indep: alternative breadth-first positionally stable mapping
461  *
462  */
463 static void crush_choose_indep(const struct crush_map *map,
464 			       struct crush_bucket *bucket,
465 			       const __u32 *weight, int weight_max,
466 			       int x, int left, int numrep, int type,
467 			       int *out, int outpos,
468 			       unsigned int tries,
469 			       unsigned int recurse_tries,
470 			       int recurse_to_leaf,
471 			       int *out2,
472 			       int parent_r)
473 {
474 	struct crush_bucket *in = bucket;
475 	int endpos = outpos + left;
476 	int rep;
477 	unsigned int ftotal;
478 	int r;
479 	int i;
480 	int item = 0;
481 	int itemtype;
482 	int collide;
483 
484 	dprintk("CHOOSE%s INDEP bucket %d x %d outpos %d numrep %d\n", recurse_to_leaf ? "_LEAF" : "",
485 		bucket->id, x, outpos, numrep);
486 
487 	/* initially my result is undefined */
488 	for (rep = outpos; rep < endpos; rep++) {
489 		out[rep] = CRUSH_ITEM_UNDEF;
490 		if (out2)
491 			out2[rep] = CRUSH_ITEM_UNDEF;
492 	}
493 
494 	for (ftotal = 0; left > 0 && ftotal < tries; ftotal++) {
495 		for (rep = outpos; rep < endpos; rep++) {
496 			if (out[rep] != CRUSH_ITEM_UNDEF)
497 				continue;
498 
499 			in = bucket;  /* initial bucket */
500 
501 			/* choose through intervening buckets */
502 			for (;;) {
503 				/* note: we base the choice on the position
504 				 * even in the nested call.  that means that
505 				 * if the first layer chooses the same bucket
506 				 * in a different position, we will tend to
507 				 * choose a different item in that bucket.
508 				 * this will involve more devices in data
509 				 * movement and tend to distribute the load.
510 				 */
511 				r = rep + parent_r;
512 
513 				/* be careful */
514 				if (in->alg == CRUSH_BUCKET_UNIFORM &&
515 				    in->size % numrep == 0)
516 					/* r'=r+(n+1)*f_total */
517 					r += (numrep+1) * ftotal;
518 				else
519 					/* r' = r + n*f_total */
520 					r += numrep * ftotal;
521 
522 				/* bucket choose */
523 				if (in->size == 0) {
524 					dprintk("   empty bucket\n");
525 					break;
526 				}
527 
528 				item = crush_bucket_choose(in, x, r);
529 				if (item >= map->max_devices) {
530 					dprintk("   bad item %d\n", item);
531 					out[rep] = CRUSH_ITEM_NONE;
532 					if (out2)
533 						out2[rep] = CRUSH_ITEM_NONE;
534 					left--;
535 					break;
536 				}
537 
538 				/* desired type? */
539 				if (item < 0)
540 					itemtype = map->buckets[-1-item]->type;
541 				else
542 					itemtype = 0;
543 				dprintk("  item %d type %d\n", item, itemtype);
544 
545 				/* keep going? */
546 				if (itemtype != type) {
547 					if (item >= 0 ||
548 					    (-1-item) >= map->max_buckets) {
549 						dprintk("   bad item type %d\n", type);
550 						out[rep] = CRUSH_ITEM_NONE;
551 						if (out2)
552 							out2[rep] =
553 								CRUSH_ITEM_NONE;
554 						left--;
555 						break;
556 					}
557 					in = map->buckets[-1-item];
558 					continue;
559 				}
560 
561 				/* collision? */
562 				collide = 0;
563 				for (i = outpos; i < endpos; i++) {
564 					if (out[i] == item) {
565 						collide = 1;
566 						break;
567 					}
568 				}
569 				if (collide)
570 					break;
571 
572 				if (recurse_to_leaf) {
573 					if (item < 0) {
574 						crush_choose_indep(map,
575 						   map->buckets[-1-item],
576 						   weight, weight_max,
577 						   x, 1, numrep, 0,
578 						   out2, rep,
579 						   recurse_tries, 0,
580 						   0, NULL, r);
581 						if (out2[rep] == CRUSH_ITEM_NONE) {
582 							/* placed nothing; no leaf */
583 							break;
584 						}
585 					} else {
586 						/* we already have a leaf! */
587 						out2[rep] = item;
588 					}
589 				}
590 
591 				/* out? */
592 				if (itemtype == 0 &&
593 				    is_out(map, weight, weight_max, item, x))
594 					break;
595 
596 				/* yay! */
597 				out[rep] = item;
598 				left--;
599 				break;
600 			}
601 		}
602 	}
603 	for (rep = outpos; rep < endpos; rep++) {
604 		if (out[rep] == CRUSH_ITEM_UNDEF) {
605 			out[rep] = CRUSH_ITEM_NONE;
606 		}
607 		if (out2 && out2[rep] == CRUSH_ITEM_UNDEF) {
608 			out2[rep] = CRUSH_ITEM_NONE;
609 		}
610 	}
611 }
612 
613 /**
614  * crush_do_rule - calculate a mapping with the given input and rule
615  * @map: the crush_map
616  * @ruleno: the rule id
617  * @x: hash input
618  * @result: pointer to result vector
619  * @result_max: maximum result size
620  * @weight: weight vector (for map leaves)
621  * @weight_max: size of weight vector
622  * @scratch: scratch vector for private use; must be >= 3 * result_max
623  */
624 int crush_do_rule(const struct crush_map *map,
625 		  int ruleno, int x, int *result, int result_max,
626 		  const __u32 *weight, int weight_max,
627 		  int *scratch)
628 {
629 	int result_len;
630 	int *a = scratch;
631 	int *b = scratch + result_max;
632 	int *c = scratch + result_max*2;
633 	int recurse_to_leaf;
634 	int *w;
635 	int wsize = 0;
636 	int *o;
637 	int osize;
638 	int *tmp;
639 	struct crush_rule *rule;
640 	__u32 step;
641 	int i, j;
642 	int numrep;
643 	int choose_tries = map->choose_total_tries;
644 	int choose_local_tries = map->choose_local_tries;
645 	int choose_local_fallback_tries = map->choose_local_fallback_tries;
646 	int choose_leaf_tries = 0;
647 
648 	if ((__u32)ruleno >= map->max_rules) {
649 		dprintk(" bad ruleno %d\n", ruleno);
650 		return 0;
651 	}
652 
653 	rule = map->rules[ruleno];
654 	result_len = 0;
655 	w = a;
656 	o = b;
657 
658 	for (step = 0; step < rule->len; step++) {
659 		int firstn = 0;
660 		struct crush_rule_step *curstep = &rule->steps[step];
661 
662 		switch (curstep->op) {
663 		case CRUSH_RULE_TAKE:
664 			w[0] = curstep->arg1;
665 			wsize = 1;
666 			break;
667 
668 		case CRUSH_RULE_SET_CHOOSE_TRIES:
669 			if (curstep->arg1 > 0)
670 				choose_tries = curstep->arg1;
671 			break;
672 
673 		case CRUSH_RULE_SET_CHOOSELEAF_TRIES:
674 			if (curstep->arg1 > 0)
675 				choose_leaf_tries = curstep->arg1;
676 			break;
677 
678 		case CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES:
679 			if (curstep->arg1 > 0)
680 				choose_local_tries = curstep->arg1;
681 			break;
682 
683 		case CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES:
684 			if (curstep->arg1 > 0)
685 				choose_local_fallback_tries = curstep->arg1;
686 			break;
687 
688 		case CRUSH_RULE_CHOOSELEAF_FIRSTN:
689 		case CRUSH_RULE_CHOOSE_FIRSTN:
690 			firstn = 1;
691 			/* fall through */
692 		case CRUSH_RULE_CHOOSELEAF_INDEP:
693 		case CRUSH_RULE_CHOOSE_INDEP:
694 			if (wsize == 0)
695 				break;
696 
697 			recurse_to_leaf =
698 				curstep->op ==
699 				 CRUSH_RULE_CHOOSELEAF_FIRSTN ||
700 				curstep->op ==
701 				CRUSH_RULE_CHOOSELEAF_INDEP;
702 
703 			/* reset output */
704 			osize = 0;
705 
706 			for (i = 0; i < wsize; i++) {
707 				/*
708 				 * see CRUSH_N, CRUSH_N_MINUS macros.
709 				 * basically, numrep <= 0 means relative to
710 				 * the provided result_max
711 				 */
712 				numrep = curstep->arg1;
713 				if (numrep <= 0) {
714 					numrep += result_max;
715 					if (numrep <= 0)
716 						continue;
717 				}
718 				j = 0;
719 				if (firstn) {
720 					int recurse_tries;
721 					if (choose_leaf_tries)
722 						recurse_tries =
723 							choose_leaf_tries;
724 					else if (map->chooseleaf_descend_once)
725 						recurse_tries = 1;
726 					else
727 						recurse_tries = choose_tries;
728 					osize += crush_choose_firstn(
729 						map,
730 						map->buckets[-1-w[i]],
731 						weight, weight_max,
732 						x, numrep,
733 						curstep->arg2,
734 						o+osize, j,
735 						choose_tries,
736 						recurse_tries,
737 						choose_local_tries,
738 						choose_local_fallback_tries,
739 						recurse_to_leaf,
740 						c+osize);
741 				} else {
742 					crush_choose_indep(
743 						map,
744 						map->buckets[-1-w[i]],
745 						weight, weight_max,
746 						x, numrep, numrep,
747 						curstep->arg2,
748 						o+osize, j,
749 						choose_tries,
750 						choose_leaf_tries ?
751 						   choose_leaf_tries : 1,
752 						recurse_to_leaf,
753 						c+osize,
754 						0);
755 					osize += numrep;
756 				}
757 			}
758 
759 			if (recurse_to_leaf)
760 				/* copy final _leaf_ values to output set */
761 				memcpy(o, c, osize*sizeof(*o));
762 
763 			/* swap o and w arrays */
764 			tmp = o;
765 			o = w;
766 			w = tmp;
767 			wsize = osize;
768 			break;
769 
770 
771 		case CRUSH_RULE_EMIT:
772 			for (i = 0; i < wsize && result_len < result_max; i++) {
773 				result[result_len] = w[i];
774 				result_len++;
775 			}
776 			wsize = 0;
777 			break;
778 
779 		default:
780 			dprintk(" unknown op %d at step %d\n",
781 				curstep->op, step);
782 			break;
783 		}
784 	}
785 	return result_len;
786 }
787 
788 
789