ceph/src/os/bluestore/StupidAllocator.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 "StupidAllocator.h"
   5 #include "bluestore_types.h"
   6 #include "common/debug.h"
   7
   8 #define dout_context cct
   9 #define dout_subsys ceph_subsys_bluestore
  10 #undef dout_prefix
  11 #define dout_prefix *_dout << "stupidalloc 0x" << this << " "
  12
  13 StupidAllocator::StupidAllocator(CephContext* cct,
  14                                  int64_t capacity,
  15                                  int64_t _block_size,
  16                                  std::string_view name)
  17   : Allocator(name, capacity, _block_size),
  18     cct(cct), num_free(0),
  19     free(10)
  20 {
  21   ceph_assert(cct != nullptr);
  22   ceph_assert(block_size > 0);
  23 }
  24
  25 StupidAllocator::~StupidAllocator()
  26 {
  27 }
  28
  29 unsigned StupidAllocator::_choose_bin(uint64_t orig_len)
  30 {
  31   uint64_t len = orig_len / block_size;
  32   int bin = std::min((int)cbits(len), (int)free.size() - 1);
  33   ldout(cct, 30) << __func__ << " len 0x" << std::hex << orig_len
  34                  << std::dec << " -> " << bin << dendl;
  35   return bin;
  36 }
  37
  38 void StupidAllocator::_insert_free(uint64_t off, uint64_t len)
  39 {
  40   unsigned bin = _choose_bin(len);
  41   ldout(cct, 30) << __func__ << " 0x" << std::hex << off << "~" << len
  42                  << std::dec << " in bin " << bin << dendl;
  43   while (true) {
  44     free[bin].insert(off, len, &off, &len);
  45     unsigned newbin = _choose_bin(len);
  46     if (newbin == bin)
  47       break;
  48     ldout(cct, 30) << __func__ << " promoting 0x" << std::hex << off << "~" << len
  49                    << std::dec << " to bin " << newbin << dendl;
  50     free[bin].erase(off, len);
  51     bin = newbin;
  52   }
  53 }
  54
  55 /// return the effective length of the extent if we align to alloc_unit
  56 uint64_t StupidAllocator::_aligned_len(
  57   StupidAllocator::interval_set_t::iterator p,
  58   uint64_t alloc_unit)
  59 {
  60   uint64_t skew = p.get_start() % alloc_unit;
  61   if (skew)
  62     skew = alloc_unit - skew;
  63   if (skew > p.get_len())
  64     return 0;
  65   else
  66     return p.get_len() - skew;
  67 }
  68
  69 int64_t StupidAllocator::allocate_int(
  70   uint64_t want_size, uint64_t alloc_unit, int64_t hint,
  71   uint64_t *offset, uint32_t *length)
  72 {
  73   std::lock_guard l(lock);
  74   ldout(cct, 10) << __func__ << " want_size 0x" << std::hex << want_size
  75                  << " alloc_unit 0x" << alloc_unit
  76                  << " hint 0x" << hint << std::dec
  77                  << dendl;
  78   uint64_t want = std::max(alloc_unit, want_size);
  79   int bin = _choose_bin(want);
  80   int orig_bin = bin;
  81
  82   auto p = free[0].begin();
  83
  84   if (!hint)
  85     hint = last_alloc;
  86
  87   // search up (from hint)
  88   if (hint) {
  89     for (bin = orig_bin; bin < (int)free.size(); ++bin) {
  90       p = free[bin].lower_bound(hint);
  91       while (p != free[bin].end()) {
  92         if (_aligned_len(p, alloc_unit) >= want_size) {
  93           goto found;
  94         }
  95         ++p;
  96       }
  97     }
  98   }
  99
 100   // search up (from origin, and skip searched extents by hint)
 101   for (bin = orig_bin; bin < (int)free.size(); ++bin) {
 102     p = free[bin].begin();
 103     auto end = hint ? free[bin].lower_bound(hint) : free[bin].end();
 104     while (p != end) {
 105       if (_aligned_len(p, alloc_unit) >= want_size) {
 106         goto found;
 107       }
 108       ++p;
 109     }
 110   }
 111
 112   // search down (hint)
 113   if (hint) {
 114     for (bin = orig_bin; bin >= 0; --bin) {
 115       p = free[bin].lower_bound(hint);
 116       while (p != free[bin].end()) {
 117         if (_aligned_len(p, alloc_unit) >= alloc_unit) {
 118           goto found;
 119         }
 120         ++p;
 121       }
 122     }
 123   }
 124
 125   // search down (from origin, and skip searched extents by hint)
 126   for (bin = orig_bin; bin >= 0; --bin) {
 127     p = free[bin].begin();
 128     auto end = hint ? free[bin].lower_bound(hint) : free[bin].end();
 129     while (p != end) {
 130       if (_aligned_len(p, alloc_unit) >= alloc_unit) {
 131         goto found;
 132       }
 133       ++p;
 134     }
 135   }
 136
 137   return -ENOSPC;
 138
 139  found:
 140   uint64_t skew = p.get_start() % alloc_unit;
 141   if (skew)
 142     skew = alloc_unit - skew;
 143   *offset = p.get_start() + skew;
 144   *length = std::min(std::max(alloc_unit, want_size), p2align((p.get_len() - skew), alloc_unit));
 145   if (cct->_conf->bluestore_debug_small_allocations) {
 146     uint64_t max =
 147       alloc_unit * (rand() % cct->_conf->bluestore_debug_small_allocations);
 148     if (max && *length > max) {
 149       ldout(cct, 10) << __func__ << " shortening allocation of 0x" << std::hex
 150                      << *length << " -> 0x"
 151                      << max << " due to debug_small_allocations" << std::dec
 152                      << dendl;
 153       *length = max;
 154     }
 155   }
 156   ldout(cct, 30) << __func__ << " got 0x" << std::hex << *offset << "~" << *length
 157                  << " from bin " << std::dec << bin << dendl;
 158
 159   free[bin].erase(*offset, *length);
 160   uint64_t off, len;
 161   if (*offset && free[bin].contains(*offset - skew - 1, &off, &len)) {
 162     int newbin = _choose_bin(len);
 163     if (newbin != bin) {
 164       ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len
 165                      << std::dec << " to bin " << newbin << dendl;
 166       free[bin].erase(off, len);
 167       _insert_free(off, len);
 168     }
 169   }
 170   if (free[bin].contains(*offset + *length, &off, &len)) {
 171     int newbin = _choose_bin(len);
 172     if (newbin != bin) {
 173       ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len
 174                      << std::dec << " to bin " << newbin << dendl;
 175       free[bin].erase(off, len);
 176       _insert_free(off, len);
 177     }
 178   }
 179
 180   num_free -= *length;
 181   ceph_assert(num_free >= 0);
 182   last_alloc = *offset + *length;
 183   return 0;
 184 }
 185
 186 int64_t StupidAllocator::allocate(
 187   uint64_t want_size,
 188   uint64_t alloc_unit,
 189   uint64_t max_alloc_size,
 190   int64_t hint,
 191   PExtentVector *extents)
 192 {
 193   uint64_t allocated_size = 0;
 194   uint64_t offset = 0;
 195   uint32_t length = 0;
 196   int res = 0;
 197
 198   if (max_alloc_size == 0) {
 199     max_alloc_size = want_size;
 200   }
 201   // cap with 32-bit val
 202   max_alloc_size = std::min(max_alloc_size, 0x10000000 - alloc_unit);
 203
 204   while (allocated_size < want_size) {
 205     res = allocate_int(std::min(max_alloc_size, (want_size - allocated_size)),
 206        alloc_unit, hint, &offset, &length);
 207     if (res != 0) {
 208       /*
 209        * Allocation failed.
 210        */
 211       break;
 212     }
 213     bool can_append = true;
 214     if (!extents->empty()) {
 215       bluestore_pextent_t &last_extent  = extents->back();
 216       if (last_extent.end() == offset) {
 217         uint64_t l64 = last_extent.length;
 218         l64 += length;
 219         if (l64 < 0x100000000 && l64 <= max_alloc_size) {
 220           can_append = false;
 221           last_extent.length += length;
 222         }
 223       }
 224     }
 225     if (can_append) {
 226       extents->emplace_back(bluestore_pextent_t(offset, length));
 227     }
 228
 229     allocated_size += length;
 230     hint = offset + length;
 231   }
 232
 233   if (allocated_size == 0) {
 234     return -ENOSPC;
 235   }
 236   return allocated_size;
 237 }
 238
 239 void StupidAllocator::release(
 240   const interval_set<uint64_t>& release_set)
 241 {
 242   std::lock_guard l(lock);
 243   for (interval_set<uint64_t>::const_iterator p = release_set.begin();
 244        p != release_set.end();
 245        ++p) {
 246     const auto offset = p.get_start();
 247     const auto length = p.get_len();
 248     ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
 249                    << std::dec << dendl;
 250     _insert_free(offset, length);
 251     num_free += length;
 252   }
 253 }
 254
 255 uint64_t StupidAllocator::get_free()
 256 {
 257   std::lock_guard l(lock);
 258   return num_free;
 259 }
 260
 261 double StupidAllocator::get_fragmentation()
 262 {
 263   ceph_assert(get_block_size());
 264   double res;
 265   uint64_t max_intervals = 0;
 266   uint64_t intervals = 0;
 267   {
 268     std::lock_guard l(lock);
 269     max_intervals = p2roundup<uint64_t>(num_free,
 270                                         get_block_size()) / get_block_size();
 271     for (unsigned bin = 0; bin < free.size(); ++bin) {
 272       intervals += free[bin].num_intervals();
 273     }
 274   }
 275   ldout(cct, 30) << __func__ << " " << intervals << "/" << max_intervals
 276                  << dendl;
 277   ceph_assert(intervals <= max_intervals);
 278   if (!intervals || max_intervals <= 1) {
 279     return 0.0;
 280   }
 281   intervals--;
 282   max_intervals--;
 283   res = (double)intervals / max_intervals;
 284   return res;
 285 }
 286
 287 void StupidAllocator::dump()
 288 {
 289   std::lock_guard l(lock);
 290   for (unsigned bin = 0; bin < free.size(); ++bin) {
 291     ldout(cct, 0) << __func__ << " free bin " << bin << ": "
 292                   << free[bin].num_intervals() << " extents" << dendl;
 293     for (auto p = free[bin].begin();
 294          p != free[bin].end();
 295          ++p) {
 296       ldout(cct, 0) << __func__ << "  0x" << std::hex << p.get_start() << "~"
 297                     << p.get_len() << std::dec << dendl;
 298     }
 299   }
 300 }
 301
 302 void StupidAllocator::foreach(std::function<void(uint64_t offset, uint64_t length)> notify)
 303 {
 304   std::lock_guard l(lock);
 305   for (unsigned bin = 0; bin < free.size(); ++bin) {
 306     for (auto p = free[bin].begin(); p != free[bin].end(); ++p) {
 307       notify(p.get_start(), p.get_len());
 308     }
 309   }
 310 }
 311
 312 void StupidAllocator::init_add_free(uint64_t offset, uint64_t length)
 313 {
 314   if (!length)
 315     return;
 316   std::lock_guard l(lock);
 317   ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
 318                  << std::dec << dendl;
 319   _insert_free(offset, length);
 320   num_free += length;
 321 }
 322
 323 void StupidAllocator::init_rm_free(uint64_t offset, uint64_t length)
 324 {
 325   if (!length)
 326     return;
 327   std::lock_guard l(lock);
 328   ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
 329                  << std::dec << dendl;
 330   interval_set_t rm;
 331   rm.insert(offset, length);
 332   for (unsigned i = 0; i < free.size() && !rm.empty(); ++i) {
 333     interval_set_t overlap;
 334     overlap.intersection_of(rm, free[i]);
 335     if (!overlap.empty()) {
 336       ldout(cct, 20) << __func__ << " bin " << i << " rm 0x" << std::hex << overlap
 337                      << std::dec << dendl;
 338       auto it = overlap.begin();
 339       auto it_end = overlap.end();
 340       while (it != it_end) {
 341         auto o = it.get_start();
 342         auto l = it.get_len();
 343
 344         free[i].erase(o, l,
 345           [&](uint64_t off, uint64_t len) {
 346             unsigned newbin = _choose_bin(len);
 347             if (newbin != i) {
 348               ldout(cct, 30) << __func__ << " demoting1 0x" << std::hex << off << "~" << len
 349                              << std::dec << " to bin " << newbin << dendl;
 350               _insert_free(off, len);
 351               return true;
 352             }
 353             return false;
 354           });
 355         ++it;
 356       }
 357
 358       rm.subtract(overlap);
 359     }
 360   }
 361   ceph_assert(rm.empty());
 362   num_free -= length;
 363   ceph_assert(num_free >= 0);
 364 }
 365
 366
 367 void StupidAllocator::shutdown()
 368 {
 369   ldout(cct, 1) << __func__ << dendl;
 370 }
 371