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