From 7630498c51fd74ab1d803285564b6b27ffe93216 Mon Sep 17 00:00:00 2001
From: Kefu Chai <kchai@redhat.com>
Date: Tue, 1 Jun 2021 19:14:33 +0800
Subject: [PATCH] os/bluestore/AvlAllocator: introduce
 bluestore_avl_alloc_ff_max_search_bytes

so AvlAllocator can switch from the first-first mode to best-fit mode
without walking through the whole space map tree. in the
highly-fragmented system, iterating the whole tree could hurt the
performance of fast storage system a lot.

the idea comes from openzfs's metaslab allocator.

Signed-off-by: Kefu Chai <kchai@redhat.com>
(cherry picked from commit 5a26875049d13130ffe5954428da0e1b9750359f)
Signed-off-by: Mauricio Faria de Oliveira <mfo@canonical.com>

 Conflicts:
	src/common/options/global.yaml.in:
	- Moved new option into src/common/options.cc
---
 src/common/options.cc            |  4 ++++
 src/os/bluestore/AvlAllocator.cc | 10 ++++++++++
 src/os/bluestore/AvlAllocator.h  |  6 ++++++
 3 files changed, 20 insertions(+)

diff --git a/src/common/options.cc b/src/common/options.cc
index e4fd613f7c22a..4fa13e1076b3e 100644
--- a/src/common/options.cc
+++ b/src/common/options.cc
@@ -4720,6 +4720,10 @@ std::vector<Option> get_global_options() {
     .set_default(100)
     .set_description("Search for this many ranges in first-fit mode before switching over to to best-fit mode. 0 to iterate through all ranges for required chunk."),
 
+    Option("bluestore_avl_alloc_ff_max_search_bytes", Option::TYPE_SIZE, Option::LEVEL_DEV)
+    .set_default(16_M)
+    .set_description("Maximum distance to search in first-fit mode before switching over to to best-fit mode. 0 to iterate through all ranges for required chunk."),
+
     Option("bluestore_avl_alloc_bf_threshold", Option::TYPE_UINT, Option::LEVEL_DEV)
     .set_default(131072)
     .set_description(""),
diff --git a/src/os/bluestore/AvlAllocator.cc b/src/os/bluestore/AvlAllocator.cc
index 751e52d58175c..08ddc6b94a189 100644
--- a/src/os/bluestore/AvlAllocator.cc
+++ b/src/os/bluestore/AvlAllocator.cc
@@ -35,6 +35,7 @@ uint64_t AvlAllocator::_pick_block_after(uint64_t *cursor,
 {
   const auto compare = range_tree.key_comp();
   uint32_t search_count = 0;
+  uint64_t search_bytes = 0;
   auto rs_start = range_tree.lower_bound(range_t{*cursor, size}, compare);
   for (auto rs = rs_start; rs != range_tree.end(); ++rs) {
     uint64_t offset = p2roundup(rs->start, align);
@@ -45,6 +46,10 @@ uint64_t AvlAllocator::_pick_block_after(uint64_t *cursor,
     if (max_search_count > 0 && ++search_count > max_search_count) {
       return -1ULL;
     }
+    if (search_bytes = rs->start - rs_start->start;
+	max_search_bytes > 0 && search_bytes > max_search_bytes) {
+      return -1ULL;
+    }
   }
   if (*cursor == 0) {
     // If we already started from beginning, don't bother with searching from beginning
@@ -60,6 +65,9 @@ uint64_t AvlAllocator::_pick_block_after(uint64_t *cursor,
     if (max_search_count > 0 && ++search_count > max_search_count) {
       return -1ULL;
     }
+    if (max_search_bytes > 0 && search_bytes + rs->start > max_search_bytes) {
+      return -1ULL;
+    }
   }
   return -1ULL;
 }
@@ -333,6 +341,8 @@ AvlAllocator::AvlAllocator(CephContext* cct,
     cct->_conf.get_val<uint64_t>("bluestore_avl_alloc_bf_free_pct")),
   max_search_count(
     cct->_conf.get_val<uint64_t>("bluestore_avl_alloc_ff_max_search_count")),
+  max_search_bytes(
+    cct->_conf.get_val<Option::size_t>("bluestore_avl_alloc_ff_max_search_bytes")),
   range_count_cap(max_mem / sizeof(range_seg_t)),
   cct(cct)
 {}
diff --git a/src/os/bluestore/AvlAllocator.h b/src/os/bluestore/AvlAllocator.h
index 023c1a15255dd..b535a22d4c189 100644
--- a/src/os/bluestore/AvlAllocator.h
+++ b/src/os/bluestore/AvlAllocator.h
@@ -169,6 +169,12 @@ private:
    * becomes the performance limiting factor on high-performance storage.
    */
   const uint32_t max_search_count;
+  /*
+   * Maximum distance to search forward from the last offset, without this
+   * limit, fragmented device can see lots of iterations and _block_picker()
+   * becomes the performance limiting factor on high-performance storage.
+   */
+  const uint32_t max_search_bytes;
   /*
   * Max amount of range entries allowed. 0 - unlimited
   */
-- 
2.39.5