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