From 0eed13a4969d02eeb23681519f2a23130e51ac59 Mon Sep 17 00:00:00 2001
From: Igor Fedotov <ifed@suse.com>
Date: Mon, 17 May 2021 22:23:26 +0300
Subject: [PATCH] os/bluestore: fix unexpected ENOSPC in Avl/Hybrid allocators.

Avl allocator mode was returning unexpected ENOSPC in first-fit mode if all size-
matching available extents were unaligned but applying the alignment made all of
them shorter than required. Since no lookup retry with smaller size -
ENOSPC is returned.
Additionally we should proceed with a lookup in best-fit mode even when
original size has been truncated to match the avail size.
(force_range_size_alloc==true)

Fixes: https://tracker.ceph.com/issues/50656
Signed-off-by: Igor Fedotov <ifedotov@suse.com>
---
 src/os/bluestore/AvlAllocator.cc       | 39 +++++++++++++++---------
 src/test/objectstore/Allocator_test.cc | 41 ++++++++++++++++++++++++++
 2 files changed, 66 insertions(+), 14 deletions(-)

diff --git a/src/os/bluestore/AvlAllocator.cc b/src/os/bluestore/AvlAllocator.cc
index 799c3ce828ee7..e33965ff7651c 100644
--- a/src/os/bluestore/AvlAllocator.cc
+++ b/src/os/bluestore/AvlAllocator.cc
@@ -223,16 +223,6 @@ int AvlAllocator::_allocate(
     ceph_assert(size > 0);
     force_range_size_alloc = true;
   }
-  /*
-   * Find the largest power of 2 block size that evenly divides the
-   * requested size. This is used to try to allocate blocks with similar
-   * alignment from the same area (i.e. same cursor bucket) but it does
-   * not guarantee that other allocations sizes may exist in the same
-   * region.
-   */
-  const uint64_t align = size & -size;
-  ceph_assert(align != 0);
-  uint64_t *cursor = &lbas[cbits(align) - 1];
 
   const int free_pct = num_free * 100 / device_size;
   uint64_t start = 0;
@@ -243,10 +233,11 @@ int AvlAllocator::_allocate(
   if (force_range_size_alloc ||
       max_size < range_size_alloc_threshold ||
       free_pct < range_size_alloc_free_pct) {
-    *cursor = 0;
+    uint64_t fake_cursor = 0;
     do {
-      start = _block_picker(range_size_tree, cursor, size, unit);
-      if (start != -1ULL || !force_range_size_alloc) {
+      start = _block_picker(range_size_tree, &fake_cursor, size, unit);
+      dout(20) << __func__ << " best fit=" << start << " size=" << size << dendl;
+      if (start != uint64_t(-1ULL)) {
         break;
       }
       // try to collect smaller extents as we could fail to retrieve
@@ -254,7 +245,27 @@ int AvlAllocator::_allocate(
       size = p2align(size >> 1, unit);
     } while (size >= unit);
   } else {
-    start = _block_picker(range_tree, cursor, size, unit);
+    do {
+      /*
+       * Find the largest power of 2 block size that evenly divides the
+       * requested size. This is used to try to allocate blocks with similar
+       * alignment from the same area (i.e. same cursor bucket) but it does
+       * not guarantee that other allocations sizes may exist in the same
+       * region.
+       */
+      uint64_t align = size & -size;
+      ceph_assert(align != 0);
+      uint64_t* cursor = &lbas[cbits(align) - 1];
+
+      start = _block_picker(range_tree, cursor, size, unit);
+      dout(20) << __func__ << " first fit=" << start << " size=" << size << dendl;
+      if (start != uint64_t(-1ULL)) {
+        break;
+      }
+      // try to collect smaller extents as we could fail to retrieve
+      // that large block due to misaligned extents
+      size = p2align(size >> 1, unit);
+    } while (size >= unit);
   }
   if (start == -1ULL) {
     return -ENOSPC;
diff --git a/src/test/objectstore/Allocator_test.cc b/src/test/objectstore/Allocator_test.cc
index d0d208ca61877..29bbd73946f53 100644
--- a/src/test/objectstore/Allocator_test.cc
+++ b/src/test/objectstore/Allocator_test.cc
@@ -517,6 +517,47 @@ TEST_P(AllocTest, test_alloc_47883)
   EXPECT_EQ(got, 0x630000);
 }
 
+TEST_P(AllocTest, test_alloc_50656_best_fit)
+{
+  uint64_t block = 0x1000;
+  uint64_t size = 0x3b9e400000;
+
+  init_alloc(size, block);
+
+  // too few free extents - causes best fit mode for avls
+  for (size_t i = 0; i < 0x10; i++) {
+    alloc->init_add_free(i * 2 * 0x100000, 0x100000);
+  }
+
+  alloc->init_add_free(0x1e1bd13000, 0x404000);
+
+  PExtentVector extents;
+  auto need = 0x400000;
+  auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents);
+  EXPECT_GT(got, 0);
+  EXPECT_EQ(got, 0x400000);
+}
+
+TEST_P(AllocTest, test_alloc_50656_first_fit)
+{
+  uint64_t block = 0x1000;
+  uint64_t size = 0x3b9e400000;
+
+  init_alloc(size, block);
+
+  for (size_t i = 0; i < 0x10000; i += 2) {
+    alloc->init_add_free(i * 0x100000, 0x100000);
+  }
+
+  alloc->init_add_free(0x1e1bd13000, 0x404000);
+
+  PExtentVector extents;
+  auto need = 0x400000;
+  auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents);
+  EXPECT_GT(got, 0);
+  EXPECT_EQ(got, 0x400000);
+}
+
 INSTANTIATE_TEST_SUITE_P(
   Allocator,
   AllocTest,
-- 
2.39.5