From f6930452bcc41bea8d6b0da35f6c19dd56021225 Mon Sep 17 00:00:00 2001
From: Sage Weil <sage@inktank.com>
Date: Mon, 27 Jan 2014 16:20:04 -0800
Subject: [PATCH] osd: add pg_pool_t::get_random_pg_position()

Return a hash position somewhere inside a given pg.

Signed-off-by: Sage Weil <sage@inktank.com>
---
 src/osd/osd_types.cc  | 17 +++++++++++++++++
 src/osd/osd_types.h   |  3 +++
 src/test/osd/types.cc | 14 ++++++++++++++
 3 files changed, 34 insertions(+)

diff --git a/src/osd/osd_types.cc b/src/osd/osd_types.cc
index 5018062e207..848dc8b7b72 100644
--- a/src/osd/osd_types.cc
+++ b/src/osd/osd_types.cc
@@ -910,6 +910,23 @@ ps_t pg_pool_t::raw_pg_to_pps(pg_t pg) const
   }
 }
 
+uint32_t pg_pool_t::get_random_pg_position(pg_t pg, uint32_t seed) const
+{
+  uint32_t r = crush_hash32_2(CRUSH_HASH_RJENKINS1, seed, 123);
+  if (pg_num == pg_num_mask + 1) {
+    r &= ~pg_num_mask;
+  } else {
+    unsigned smaller_mask = pg_num_mask >> 1;
+    if ((pg.ps() & smaller_mask) < (pg_num & smaller_mask)) {
+      r &= ~pg_num_mask;
+    } else {
+      r &= ~smaller_mask;
+    }
+  }
+  r |= pg.ps();
+  return r;
+}
+
 void pg_pool_t::encode(bufferlist& bl, uint64_t features) const
 {
   if ((features & CEPH_FEATURE_PGPOOL3) == 0) {
diff --git a/src/osd/osd_types.h b/src/osd/osd_types.h
index 3e32b16a90b..8360218790d 100644
--- a/src/osd/osd_types.h
+++ b/src/osd/osd_types.h
@@ -990,6 +990,9 @@ public:
    */
   ps_t raw_pg_to_pps(pg_t pg) const;
 
+  /// choose a random hash position within a pg
+  uint32_t get_random_pg_position(pg_t pgid, uint32_t seed) const;
+
   void encode(bufferlist& bl, uint64_t features) const;
   void decode(bufferlist::iterator& bl);
 
diff --git a/src/test/osd/types.cc b/src/test/osd/types.cc
index d1e62b8fcea..a0d660fa92a 100644
--- a/src/test/osd/types.cc
+++ b/src/test/osd/types.cc
@@ -1186,6 +1186,20 @@ TEST(pg_pool_t_test, get_pg_num_divisor) {
   ASSERT_EQ(16u, p.get_pg_num_divisor(pg_t(11, 1)));
 }
 
+TEST(pg_pool_t_test, get_random_pg_position) {
+  srand(getpid());
+  for (int i = 0; i < 100; ++i) {
+    pg_pool_t p;
+    p.set_pg_num(1 + (rand() % 1000));
+    p.set_pgp_num(p.get_pg_num());
+    pg_t pgid(rand() % p.get_pg_num(), 1);
+    uint32_t h = p.get_random_pg_position(pgid, rand());
+    uint32_t ps = p.raw_hash_to_pg(h);
+    cout << p.get_pg_num() << " " << pgid << ": "
+	 << h << " -> " << pg_t(ps, 1) << std::endl;
+    ASSERT_EQ(pgid.ps(), ps);
+  }
+}
 
 /*
  * Local Variables:
-- 
2.47.3