From 94983dc90ecacb1ef1771640f5d98ec4e3e47fde Mon Sep 17 00:00:00 2001
From: Sage Weil <sage@newdream.net>
Date: Wed, 13 May 2009 14:07:45 -0700
Subject: [PATCH] crush: ditch prime number theorem; generate random
 permutation on the fly

---
 src/crush/CrushWrapper.h |  6 +-----
 src/crush/builder.c      | 18 ++----------------
 src/crush/crush.c        |  2 +-
 src/crush/crush.h        |  5 ++++-
 src/crush/mapper.c       | 26 +++++++++++++++++++-------
 5 files changed, 27 insertions(+), 30 deletions(-)

diff --git a/src/crush/CrushWrapper.h b/src/crush/CrushWrapper.h
index 50a5004292054..7e3306f13f3ba 100644
--- a/src/crush/CrushWrapper.h
+++ b/src/crush/CrushWrapper.h
@@ -377,8 +377,6 @@ public:
 
       switch (crush->buckets[i]->alg) {
       case CRUSH_BUCKET_UNIFORM:
-	for (unsigned j=0; j<crush->buckets[i]->size; j++)
-	  ::encode(((crush_bucket_uniform*)crush->buckets[i])->primes[j], bl);
 	::encode(((crush_bucket_uniform*)crush->buckets[i])->item_weight, bl);
 	break;
 
@@ -474,10 +472,8 @@ public:
 
       switch (crush->buckets[i]->alg) {
       case CRUSH_BUCKET_UNIFORM:
-	((crush_bucket_uniform*)crush->buckets[i])->primes =
+	((crush_bucket_uniform*)crush->buckets[i])->perm =
 	  (__u32*)malloc(crush->buckets[i]->size * sizeof(__u32));
-	for (unsigned j=0; j<crush->buckets[i]->size; j++)
-	  ::decode(((crush_bucket_uniform*)crush->buckets[i])->primes[j], blp);
 	::decode(((crush_bucket_uniform*)crush->buckets[i])->item_weight, blp);
 	break;
 
diff --git a/src/crush/builder.c b/src/crush/builder.c
index 7f36319da4bd8..ff48a9ccf7124 100644
--- a/src/crush/builder.c
+++ b/src/crush/builder.c
@@ -162,24 +162,10 @@ crush_make_uniform_bucket(int type, int size,
 		bucket->h.items[i] = items[i];
 
 	/* generate some primes */
-	bucket->primes = malloc(sizeof(__u32)*size);
+	bucket->perm = malloc(sizeof(__u32)*size);
 
-	if (size < 1) {
+	if (size < 1)
 		return bucket;
-	}
-
-	x = size + 1;
-	x += crush_hash32(size) % (3*size);  /* make it big */
-	x |= 1;                              /* and odd */
-
-	i=0;
-	while (i < size) {
-		for (j=2; j*j <= x; j++)
-			if (x % j == 0) break;
-		if (j*j > x)
-			bucket->primes[i++] = x;
-		x += 2;
-	}
 
 	return bucket;
 }
diff --git a/src/crush/crush.c b/src/crush/crush.c
index c77c7e8cefa7b..8fb187ea4d3f0 100644
--- a/src/crush/crush.c
+++ b/src/crush/crush.c
@@ -61,7 +61,7 @@ void crush_calc_parents(struct crush_map *map)
 
 void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b)
 {
-	kfree(b->primes);
+	kfree(b->perm);
 	kfree(b->h.items);
 	kfree(b);
 }
diff --git a/src/crush/crush.h b/src/crush/crush.h
index 19aba44b269d4..66d47b533b2a4 100644
--- a/src/crush/crush.h
+++ b/src/crush/crush.h
@@ -118,8 +118,11 @@ struct crush_bucket {
 
 struct crush_bucket_uniform {
 	struct crush_bucket h;
-	__u32 *primes;
 	__u32 item_weight;  /* 16-bit fixed point; all items equally weighted */
+	
+	__u32 perm_x;
+	__u32 perm_n;
+	__u32 *perm;
 };
 
 struct crush_bucket_list {
diff --git a/src/crush/mapper.c b/src/crush/mapper.c
index e3b3e6c56b4d9..22c257761b789 100644
--- a/src/crush/mapper.c
+++ b/src/crush/mapper.c
@@ -57,13 +57,25 @@ int crush_find_rule(struct crush_map *map, int ruleset, int type, int size)
 static int bucket_uniform_choose(struct crush_bucket_uniform *bucket,
 				 int x, int r, int shift)
 {
-	unsigned o = crush_hash32_2(x, bucket->h.id) & 0xffff;
-	/* shift to a new prime/permutation every few r */
-	unsigned oo = crush_hash32_3(r>>2, bucket->h.id, x);
-	unsigned p = bucket->primes[oo % bucket->h.size];
-	unsigned s = (x + o + (r+1)*p) % bucket->h.size;
-	if (shift)
-		s = (s + shift) % bucket->h.size;
+	/*
+	 * generate my permutation, up to r % size
+	 */
+	unsigned i, t;
+	unsigned pr = r % bucket->h.size;
+	if (x != bucket->perm_x) {
+		bucket->perm_x = x;
+		bucket->perm_n = 0;
+		for (i = 0; i < bucket->h.size; i++)
+			bucket->perm[i] = i;
+	}
+	while (bucket->perm_n < (pr+1)) {
+		i = crush_hash32_3(x, bucket->h.id, i) % (bucket->h.size - bucket->perm_n);
+		t = bucket->perm[bucket->perm_n + i];
+		bucket->perm[bucket->perm_n + i] = bucket->perm[bucket->perm_n];
+		bucket->perm[bucket->perm_n] = t;
+		bucket->perm_n++;		
+	}
+	unsigned s = bucket->perm[pr];
 	return bucket->h.items[s];
 }
 
-- 
2.39.5