From cb719ac3eba7b32fd45ca9a39d3800a220653427 Mon Sep 17 00:00:00 2001
From: Sage Weil <sage@newdream.net>
Date: Tue, 16 Jun 2009 15:03:50 -0700
Subject: [PATCH] crush: fix perm_choose bug

We would get incorrect results if we calculated the same mapping
twice in a row in certain cases.  Der.  Also, the permutation
calculation was basically just wrong.
---
 src/crush/crush.h  |  2 +-
 src/crush/mapper.c | 42 ++++++++++++++++++++++--------------------
 2 files changed, 23 insertions(+), 21 deletions(-)

diff --git a/src/crush/crush.h b/src/crush/crush.h
index 97520aade7d77..58e79a0e8ec5c 100644
--- a/src/crush/crush.h
+++ b/src/crush/crush.h
@@ -120,7 +120,7 @@ struct crush_bucket {
 	 * the linear search fallback for the other bucket types.
 	 */
 	__u32 perm_x;  /* @x for which *perm is defined */
-	__u32 perm_n;  /* how much of *perm has been calculated */
+	__u32 perm_n;  /* num elements of *perm that are permuted/defined */
 	__u32 *perm;
 };
 
diff --git a/src/crush/mapper.c b/src/crush/mapper.c
index 99d13db9c307f..773428cffc04a 100644
--- a/src/crush/mapper.c
+++ b/src/crush/mapper.c
@@ -59,9 +59,8 @@ int crush_find_rule(struct crush_map *map, int ruleset, int type, int size)
 static int bucket_perm_choose(struct crush_bucket *bucket,
 				int x, int r)
 {
-	unsigned i, t;
 	unsigned pr = r % bucket->size;
-	unsigned s;
+	unsigned i, s;
 
 	/* start a new permutation if @x has changed */
 	if (bucket->perm_x != x || bucket->perm_n == 0) {
@@ -74,15 +73,14 @@ static int bucket_perm_choose(struct crush_bucket *bucket,
 				bucket->size;
 			bucket->perm[0] = s;
 			bucket->perm_n = 0xffff;
-			return bucket->items[s];
-		} else {
-			for (i = 0; i < bucket->size; i++)
-				bucket->perm[i] = i;
-			bucket->perm_n = 0;
+			goto out;
 		}
-	}
-
-	if (bucket->perm_n == 0xffff) {
+		
+		for (i = 0; i < bucket->size; i++)
+			bucket->perm[i] = i;
+		bucket->perm_n = 0;
+	} else if (bucket->perm_n == 0xffff) {
+		/* clean up after the r=0 case above */
 		for (i = 1; i < bucket->size; i++)
 			bucket->perm[i] = i;
 		bucket->perm[bucket->perm[0]] = 0;
@@ -92,22 +90,26 @@ static int bucket_perm_choose(struct crush_bucket *bucket,
 	/* calculate permutation up to pr */
 	for (i = 0; i < bucket->perm_n; i++) 
 		dprintk(" perm_choose have %d: %d\n", i, bucket->perm[i]);
-	while (bucket->perm_n < pr) {
-		bucket->perm_n++;		
-		if (bucket->perm_n < bucket->size -1) {
-			i = crush_hash32_3(x, bucket->id, bucket->perm_n) %
-				(bucket->size - bucket->perm_n);
-			t = bucket->perm[bucket->perm_n + i];
-			bucket->perm[bucket->perm_n + i] =
-				bucket->perm[bucket->perm_n - 1];
-			bucket->perm[bucket->perm_n - 1] = t;
-			dprintk(" perm_choose swap %d with %d\n", bucket->perm_n-1, i);
+	while (bucket->perm_n <= pr) {
+		unsigned p = bucket->perm_n;
+		/* no point in swapping the final entry */
+		if (p < bucket->size - 1) {
+			i = crush_hash32_3(x, bucket->id, p) %
+				(bucket->size - p);
+			if (i) {
+				unsigned t = bucket->perm[p + i];
+				bucket->perm[p + i] = bucket->perm[p];
+				bucket->perm[p] = t;
+			}
+			dprintk(" perm_choose swap %d with %d\n", p, p+i);
 		}
+		bucket->perm_n++;
 	}
 	for (i = 0; i < bucket->size; i++) 
 		dprintk(" perm_choose  %d: %d\n", i, bucket->perm[i]);
 
 	s = bucket->perm[pr];
+out:
 	dprintk(" perm_choose %d sz=%d x=%d r=%d (%d) s=%d\n", bucket->id, bucket->size, x, r, pr, s);
 	return bucket->items[s];
 }
-- 
2.39.5