ceph/src/os/bluestore/Allocator.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include "Allocator.h"
   5 #include <bit>
   6 #include "StupidAllocator.h"
   7 #include "BitmapAllocator.h"
   8 #include "AvlAllocator.h"
   9 #include "BtreeAllocator.h"
  10 #include "HybridAllocator.h"
  11 #ifdef HAVE_LIBZBD
  12 #include "ZonedAllocator.h"
  13 #endif
  14 #include "common/debug.h"
  15 #include "common/admin_socket.h"
  16 #define dout_subsys ceph_subsys_bluestore
  17
  18 using std::string;
  19 using std::to_string;
  20
  21 using ceph::bufferlist;
  22 using ceph::Formatter;
  23
  24 class Allocator::SocketHook : public AdminSocketHook {
  25   Allocator *alloc;
  26
  27   friend class Allocator;
  28   std::string name;
  29 public:
  30   SocketHook(Allocator *alloc, std::string_view _name) :
  31     alloc(alloc), name(_name)
  32   {
  33     AdminSocket *admin_socket = g_ceph_context->get_admin_socket();
  34     if (name.empty()) {
  35       name = to_string((uintptr_t)this);
  36     }
  37     if (admin_socket) {
  38       int r = admin_socket->register_command(
  39         ("bluestore allocator dump " + name).c_str(),
  40         this,
  41         "dump allocator free regions");
  42       if (r != 0)
  43         alloc = nullptr; //some collision, disable
  44       if (alloc) {
  45         r = admin_socket->register_command(
  46           ("bluestore allocator score " + name).c_str(),
  47           this,
  48           "give score on allocator fragmentation (0-no fragmentation, 1-absolute fragmentation)");
  49         ceph_assert(r == 0);
  50         r = admin_socket->register_command(
  51           ("bluestore allocator fragmentation " + name).c_str(),
  52           this,
  53           "give allocator fragmentation (0-no fragmentation, 1-absolute fragmentation)");
  54         ceph_assert(r == 0);
  55       }
  56     }
  57   }
  58   ~SocketHook()
  59   {
  60     AdminSocket *admin_socket = g_ceph_context->get_admin_socket();
  61     if (admin_socket && alloc) {
  62       admin_socket->unregister_commands(this);
  63     }
  64   }
  65
  66   int call(std::string_view command,
  67            const cmdmap_t& cmdmap,
  68            const bufferlist&,
  69            Formatter *f,
  70            std::ostream& ss,
  71            bufferlist& out) override {
  72     int r = 0;
  73     if (command == "bluestore allocator dump " + name) {
  74       f->open_object_section("allocator_dump");
  75       f->dump_unsigned("capacity", alloc->get_capacity());
  76       f->dump_unsigned("alloc_unit", alloc->get_block_size());
  77       f->dump_string("alloc_type", alloc->get_type());
  78       f->dump_string("alloc_name", name);
  79
  80       f->open_array_section("extents");
  81       auto iterated_allocation = [&](size_t off, size_t len) {
  82         ceph_assert(len > 0);
  83         f->open_object_section("free");
  84         char off_hex[30];
  85         char len_hex[30];
  86         snprintf(off_hex, sizeof(off_hex) - 1, "0x%zx", off);
  87         snprintf(len_hex, sizeof(len_hex) - 1, "0x%zx", len);
  88         f->dump_string("offset", off_hex);
  89         f->dump_string("length", len_hex);
  90         f->close_section();
  91       };
  92       alloc->foreach(iterated_allocation);
  93       f->close_section();
  94       f->close_section();
  95     } else if (command == "bluestore allocator score " + name) {
  96       f->open_object_section("fragmentation_score");
  97       f->dump_float("fragmentation_rating", alloc->get_fragmentation_score());
  98       f->close_section();
  99     } else if (command == "bluestore allocator fragmentation " + name) {
 100       f->open_object_section("fragmentation");
 101       f->dump_float("fragmentation_rating", alloc->get_fragmentation());
 102       f->close_section();
 103     } else {
 104       ss << "Invalid command" << std::endl;
 105       r = -ENOSYS;
 106     }
 107     return r;
 108   }
 109
 110 };
 111 Allocator::Allocator(std::string_view name,
 112                      int64_t _capacity,
 113                      int64_t _block_size)
 114  : device_size(_capacity),
 115    block_size(_block_size)
 116 {
 117   asok_hook = new SocketHook(this, name);
 118 }
 119
 120
 121 Allocator::~Allocator()
 122 {
 123   delete asok_hook;
 124 }
 125
 126 const string& Allocator::get_name() const {
 127   return asok_hook->name;
 128 }
 129
 130 Allocator *Allocator::create(
 131   CephContext* cct,
 132   std::string_view type,
 133   int64_t size,
 134   int64_t block_size,
 135   int64_t zone_size,
 136   int64_t first_sequential_zone,
 137   std::string_view name)
 138 {
 139   Allocator* alloc = nullptr;
 140   if (type == "stupid") {
 141     alloc = new StupidAllocator(cct, size, block_size, name);
 142   } else if (type == "bitmap") {
 143     alloc = new BitmapAllocator(cct, size, block_size, name);
 144   } else if (type == "avl") {
 145     return new AvlAllocator(cct, size, block_size, name);
 146   } else if (type == "btree") {
 147     return new BtreeAllocator(cct, size, block_size, name);
 148   } else if (type == "hybrid") {
 149     return new HybridAllocator(cct, size, block_size,
 150       cct->_conf.get_val<uint64_t>("bluestore_hybrid_alloc_mem_cap"),
 151       name);
 152 #ifdef HAVE_LIBZBD
 153   } else if (type == "zoned") {
 154     return new ZonedAllocator(cct, size, block_size, zone_size, first_sequential_zone,
 155                               name);
 156 #endif
 157   }
 158   if (alloc == nullptr) {
 159     lderr(cct) << "Allocator::" << __func__ << " unknown alloc type "
 160              << type << dendl;
 161   }
 162   return alloc;
 163 }
 164
 165 void Allocator::release(const PExtentVector& release_vec)
 166 {
 167   interval_set<uint64_t> release_set;
 168   for (auto e : release_vec) {
 169     release_set.insert(e.offset, e.length);
 170   }
 171   release(release_set);
 172 }
 173
 174 /**
 175  * Gives fragmentation a numeric value.
 176  *
 177  * Following algorithm applies value to each existing free unallocated block.
 178  * Value of single block is a multiply of size and per-byte-value.
 179  * Per-byte-value is greater for larger blocks.
 180  * Assume block size X has value per-byte p; then block size 2*X will have per-byte value 1.1*p.
 181  *
 182  * This could be expressed in logarithms, but for speed this is interpolated inside ranges.
 183  * [1]  [2..3] [4..7] [8..15] ...
 184  * ^    ^      ^      ^
 185  * 1.1  1.1^2  1.1^3  1.1^4 ...
 186  *
 187  * Final score is obtained by proportion between score that would have been obtained
 188  * in condition of absolute fragmentation and score in no fragmentation at all.
 189  */
 190 double Allocator::get_fragmentation_score()
 191 {
 192   // this value represents how much worth is 2X bytes in one chunk then in X + X bytes
 193   static const double double_size_worth = 1.1 ;
 194   std::vector<double> scales{1};
 195   double score_sum = 0;
 196   size_t sum = 0;
 197
 198   auto get_score = [&](size_t v) -> double {
 199     size_t sc = sizeof(v) * 8 - std::countl_zero(v) - 1; //assign to grade depending on log2(len)
 200     while (scales.size() <= sc + 1) {
 201       //unlikely expand scales vector
 202       scales.push_back(scales[scales.size() - 1] * double_size_worth);
 203     }
 204
 205     size_t sc_shifted = size_t(1) << sc;
 206     double x = double(v - sc_shifted) / sc_shifted; //x is <0,1) in its scale grade
 207     // linear extrapolation in its scale grade
 208     double score = (sc_shifted    ) * scales[sc]   * (1-x) +
 209                    (sc_shifted * 2) * scales[sc+1] * x;
 210     return score;
 211   };
 212
 213   auto iterated_allocation = [&](size_t off, size_t len) {
 214     ceph_assert(len > 0);
 215     score_sum += get_score(len);
 216     sum += len;
 217   };
 218   foreach(iterated_allocation);
 219
 220
 221   double ideal = get_score(sum);
 222   double terrible = sum * get_score(1);
 223   return (ideal - score_sum) / (ideal - terrible);
 224 }