From 1a5f08f32400330c25b05ed3f2ef54af3bbf3000 Mon Sep 17 00:00:00 2001
From: David Zafman <dzafman@redhat.com>
Date: Thu, 14 Nov 2019 21:10:28 -0800
Subject: [PATCH] osd: ceph_pg_upmaps() use max_deviation to determine perfect
 distribution

Signed-off-by: David Zafman <dzafman@redhat.com>
(cherry picked from commit 7f4ae9312314c329b63c850e09b403a95ad18bed)

Conflicts:
	src/pybind/mgr/balancer/module.py (upmap_max_deviation config option
					   handled differently)
---
 src/common/options.cc             |  5 --
 src/mgr/PyOSDMap.cc               |  4 +-
 src/osd/OSDMap.cc                 | 86 ++++++++++++++-----------------
 src/osd/OSDMap.h                  |  2 +-
 src/pybind/mgr/balancer/module.py |  2 +-
 src/test/osd/TestOSDMap.cc        |  6 +--
 src/tools/osdmaptool.cc           |  8 ++-
 7 files changed, 51 insertions(+), 62 deletions(-)

diff --git a/src/common/options.cc b/src/common/options.cc
index 3969faa88e3..4f6adf30323 100644
--- a/src/common/options.cc
+++ b/src/common/options.cc
@@ -1659,11 +1659,6 @@ std::vector<Option> get_global_options() {
                      "by doing a fairly exhaustive search of existing PGs "
                      "that can be unmapped or upmapped"),
 
-    Option("osd_calc_pg_upmaps_max_stddev", Option::TYPE_FLOAT, Option::LEVEL_ADVANCED)
-    .set_default(1.0)
-    .set_description("standard deviation below which there is no attempt made "
-                     "while trying to calculate PG upmaps"),
-
     Option("osd_calc_pg_upmaps_local_fallback_retries", Option::TYPE_UINT, Option::LEVEL_ADVANCED)
     .set_default(100)
     .set_description("Maximum number of PGs we can attempt to unmap or upmap "
diff --git a/src/mgr/PyOSDMap.cc b/src/mgr/PyOSDMap.cc
index b67f2a14743..35d403c1c4d 100644
--- a/src/mgr/PyOSDMap.cc
+++ b/src/mgr/PyOSDMap.cc
@@ -114,9 +114,9 @@ static PyObject *osdmap_calc_pg_upmaps(BasePyOSDMap* self, PyObject *args)
 {
   PyObject *pool_list;
   BasePyOSDMapIncremental *incobj;
-  double max_deviation = 0;
+  int max_deviation = 0;
   int max_iterations = 0;
-  if (!PyArg_ParseTuple(args, "OdiO:calc_pg_upmaps",
+  if (!PyArg_ParseTuple(args, "OiiO:calc_pg_upmaps",
 			&incobj, &max_deviation,
 			&max_iterations, &pool_list)) {
     return nullptr;
diff --git a/src/osd/OSDMap.cc b/src/osd/OSDMap.cc
index e0ae6770c25..5d329585563 100644
--- a/src/osd/OSDMap.cc
+++ b/src/osd/OSDMap.cc
@@ -3998,13 +3998,16 @@ bool OSDMap::try_pg_upmap(
 
 int OSDMap::calc_pg_upmaps(
   CephContext *cct,
-  float max_deviation_ratio,
+  uint32_t max_deviation,
   int max,
   const set<int64_t>& only_pools,
   OSDMap::Incremental *pending_inc)
 {
   ldout(cct, 10) << __func__ << " pools " << only_pools << dendl;
   OSDMap tmp;
+  // Can't be less than 1 pg
+  if (max_deviation < 1)
+    max_deviation = 1;
   tmp.deepish_copy_from(*this);
   int num_changed = 0;
   map<int,set<pg_t>> pgs_by_osd;
@@ -4066,10 +4069,10 @@ int OSDMap::calc_pg_upmaps(
     lderr(cct) << __func__ << " abort due to max <= 0" << dendl;
     return 0;
   }
-  float decay_factor = 1.0 / float(max);
   float stddev = 0;
   map<int,float> osd_deviation;       // osd, deviation(pgs)
   multimap<float,int> deviation_osd;  // deviation(pgs), osd
+  float cur_max_deviation = 0;
   for (auto& i : pgs_by_osd) {
     // make sure osd is still there (belongs to this crush-tree)
     ceph_assert(osd_weight.count(i.first));
@@ -4083,8 +4086,11 @@ int OSDMap::calc_pg_upmaps(
     osd_deviation[i.first] = deviation;
     deviation_osd.insert(make_pair(deviation, i.first));
     stddev += deviation * deviation;
+    if (fabsf(deviation) > cur_max_deviation)
+      cur_max_deviation = fabsf(deviation);
   }
-  if (stddev <= cct->_conf->get_val<double>("osd_calc_pg_upmaps_max_stddev")) {
+  ldout(cct, 20) << " stdev " << stddev << " max_deviation " << cur_max_deviation << dendl;
+  if (cur_max_deviation <= max_deviation) {
     ldout(cct, 10) << __func__ << " distribution is almost perfect"
                    << dendl;
     return 0;
@@ -4095,50 +4101,28 @@ int OSDMap::calc_pg_upmaps(
   auto local_fallback_retries =
     cct->_conf->get_val<uint64_t>("osd_calc_pg_upmaps_local_fallback_retries");
   while (max--) {
+    ldout(cct, 30) << "Top of loop #" << max+1 << dendl;
     // build overfull and underfull
     set<int> overfull;
     vector<int> underfull;
-    float decay = 0;
-    int decay_count = 0;
-    while (overfull.empty()) {
-      for (auto i = deviation_osd.rbegin(); i != deviation_osd.rend(); i++) {
-        if (i->first >= (1.0 - decay))
-          overfull.insert(i->second);
+    for (auto i = deviation_osd.rbegin(); i != deviation_osd.rend(); i++) {
+        ldout(cct, 30) << " check " << i->first << " <= " << max_deviation << dendl;
+        if (i->first <= max_deviation)
+	  break;
+	ldout(cct, 30) << " add overfull osd." << i->second << dendl;
+        overfull.insert(i->second);
       }
-      if (!overfull.empty())
-        break;
-      decay_count++;
-      decay = decay_factor * decay_count;
-      if (decay >= 1.0)
-        break;
-      ldout(cct, 30) << " decay_factor = " << decay_factor
-                     << " decay_count = " << decay_count
-                     << " decay (overfull) = " << decay
-                     << dendl;
-    }
     if (overfull.empty()) {
       ldout(cct, 20) << __func__ << " failed to build overfull" << dendl;
       break;
     }
 
-    decay = 0;
-    decay_count = 0;
-    while (underfull.empty()) {
-      for (auto i = deviation_osd.begin(); i != deviation_osd.end(); i++) {
-        if (i->first >= (-.999 + decay))
+    for (auto i = deviation_osd.begin(); i != deviation_osd.end(); i++) {
+        ldout(cct, 30) << " check " << i->first << " >= " << -(int)max_deviation << dendl;
+        if (i->first >= -(int)max_deviation)
           break;
+	ldout(cct, 30) << " add underfull osd." << i->second << dendl;
         underfull.push_back(i->second);
-      }
-      if (!underfull.empty())
-        break;
-      decay_count++;
-      decay = decay_factor * decay_count;
-      if (decay >= .999)
-        break;
-      ldout(cct, 30) << " decay_factor = " << decay_factor
-                     << " decay_count = " << decay_count
-                     << " decay (underfull) = " << decay
-                     << dendl;
     }
     if (underfull.empty()) {
       ldout(cct, 20) << __func__ << " failed to build underfull" << dendl;
@@ -4165,14 +4149,16 @@ int OSDMap::calc_pg_upmaps(
       int osd = p->second;
       float deviation = p->first;
       float target = osd_weight[osd] * pgs_per_weight;
+      ldout(cct, 10) << " Overfull search osd." << osd
+                       << " target " << target
+                       << " deviation " << deviation
+		       << dendl;
       ceph_assert(target > 0);
-      float deviation_ratio = deviation / target;
-      if (deviation_ratio < max_deviation_ratio) {
+      if (deviation <= max_deviation) {
 	ldout(cct, 10) << " osd." << osd
                        << " target " << target
                        << " deviation " << deviation
-                       << " -> ratio " << deviation_ratio
-                       << " < max ratio " << max_deviation_ratio
+                       << " < max deviation " << max_deviation
                        << dendl;
 	break;
       }
@@ -4311,14 +4297,13 @@ int OSDMap::calc_pg_upmaps(
       float deviation = p.first;
       float target = osd_weight[osd] * pgs_per_weight;
       ceph_assert(target > 0);
-      float deviation_ratio = abs(deviation / target);
-      if (deviation_ratio < max_deviation_ratio) {
-        // respect max_deviation_ratio too
+      if (fabsf(deviation) < max_deviation) {
+        // respect max_deviation too
         ldout(cct, 10) << " osd." << osd
                        << " target " << target
                        << " deviation " << deviation
-                       << " -> absolute ratio " << deviation_ratio
-                       << " < max ratio " << max_deviation_ratio
+                       << " -> absolute " << fabsf(deviation)
+                       << " < max " << max_deviation
                        << dendl;
         break;
       }
@@ -4404,6 +4389,7 @@ int OSDMap::calc_pg_upmaps(
     float new_stddev = 0;
     map<int,float> temp_osd_deviation;
     multimap<float,int> temp_deviation_osd;
+    float cur_max_deviation = 0;
     for (auto& i : temp_pgs_by_osd) {
       // make sure osd is still there (belongs to this crush-tree)
       ceph_assert(osd_weight.count(i.first));
@@ -4416,7 +4402,9 @@ int OSDMap::calc_pg_upmaps(
                      << dendl;
       temp_osd_deviation[i.first] = deviation;
       temp_deviation_osd.insert(make_pair(deviation, i.first));
-      new_stddev += deviation * deviation;
+       new_stddev += deviation * deviation;
+      if (fabsf(deviation) > cur_max_deviation)
+        cur_max_deviation = fabsf(deviation);
     }
     ldout(cct, 10) << " stddev " << stddev << " -> " << new_stddev << dendl;
     if (new_stddev >= stddev) {
@@ -4468,6 +4456,12 @@ int OSDMap::calc_pg_upmaps(
       pending_inc->new_pg_upmap_items[i.first] = i.second;
       ++num_changed;
     }
+    ldout(cct, 20) << " stdev " << stddev << " max_deviation " << cur_max_deviation << dendl;
+    if (cur_max_deviation <= max_deviation) {
+      ldout(cct, 10) << __func__ << " Optimization plan is almost perfect"
+                     << dendl;
+      break;
+    }
   }
   ldout(cct, 10) << " num_changed = " << num_changed << dendl;
   return num_changed;
diff --git a/src/osd/OSDMap.h b/src/osd/OSDMap.h
index 5aefb06fd87..1a9f693b820 100644
--- a/src/osd/OSDMap.h
+++ b/src/osd/OSDMap.h
@@ -1332,7 +1332,7 @@ public:
 
   int calc_pg_upmaps(
     CephContext *cct,
-    float max_deviation, ///< max deviation from target (value < 1.0)
+    uint32_t max_deviation, ///< max deviation from target (value >= 1)
     int max_iterations,  ///< max iterations to run
     const set<int64_t>& pools,        ///< [optional] restrict to pool
     Incremental *pending_inc
diff --git a/src/pybind/mgr/balancer/module.py b/src/pybind/mgr/balancer/module.py
index 46232c9a451..6b1abc0ad37 100644
--- a/src/pybind/mgr/balancer/module.py
+++ b/src/pybind/mgr/balancer/module.py
@@ -745,7 +745,7 @@ class Module(MgrModule):
     def do_upmap(self, plan):
         self.log.info('do_upmap')
         max_iterations = int(self.get_config('upmap_max_iterations', 10))
-        max_deviation = float(self.get_config('upmap_max_deviation', .01))
+        max_deviation = int(self.get_config('upmap_max_deviation', 1))
 
         ms = plan.initial
         if len(plan.pools):
diff --git a/src/test/osd/TestOSDMap.cc b/src/test/osd/TestOSDMap.cc
index af7e2336bfb..aee60be3218 100644
--- a/src/test/osd/TestOSDMap.cc
+++ b/src/test/osd/TestOSDMap.cc
@@ -1287,15 +1287,11 @@ TEST_F(OSDMapTest, BUG_38897) {
 
   // ready to go
   {
-    // require perfect distribution!
-    auto ret = g_ceph_context->_conf->set_val(
-      "osd_calc_pg_upmaps_max_stddev", "0");
-    ASSERT_EQ(0, ret);
-    g_ceph_context->_conf->apply_changes(nullptr);
     set<int64_t> only_pools;
     ASSERT_TRUE(pool_1_id >= 0);
     only_pools.insert(pool_1_id);
     OSDMap::Incremental pending_inc(osdmap.get_epoch() + 1);
+    // require perfect distribution! (max deviation 0)
     osdmap.calc_pg_upmaps(g_ceph_context,
                           0, // so we can force optimizing
                           100,
diff --git a/src/tools/osdmaptool.cc b/src/tools/osdmaptool.cc
index 5800e578768..f15a9ba4871 100644
--- a/src/tools/osdmaptool.cc
+++ b/src/tools/osdmaptool.cc
@@ -49,7 +49,7 @@ void usage()
   cout << "                           writing commands to <file> [default: - for stdout]" << std::endl;
   cout << "   --upmap-max <max-count> set max upmap entries to calculate [default: 10]" << std::endl;
   cout << "   --upmap-deviation <max-deviation>" << std::endl;
-  cout << "                           max deviation from target [default: .01]" << std::endl;
+  cout << "                           max deviation from target [default: 1]" << std::endl;
   cout << "   --upmap-pool <poolname> restrict upmap balancing to 1 or more pools" << std::endl;
   cout << "   --upmap-save            write modified OSDMap with upmap changes" << std::endl;
   exit(1);
@@ -129,7 +129,7 @@ int main(int argc, const char **argv)
   bool health = false;
   std::string upmap_file = "-";
   int upmap_max = 10;
-  float upmap_deviation = .01;
+  int upmap_deviation = 1;
   std::set<std::string> upmap_pools;
   int64_t pg_num = -1;
   bool test_map_pgs_dump_all = false;
@@ -238,6 +238,10 @@ int main(int argc, const char **argv)
     cerr << me << ": too many arguments" << std::endl;
     usage();
   }
+  if (upmap_deviation < 1) {
+    cerr << me << ": upmap-deviation must be >= 1" << std::endl;
+    usage();
+  }
   fn = args[0];
 
   if (range_first >= 0 && range_last >= 0) {
-- 
2.47.3