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