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