Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 371 insertions, 0 deletions

diff --git a/src/os/bluestore/StupidAllocator.cc b/src/os/bluestore/StupidAllocator.cc
new file mode 100644
index 000000000..805a51fb0
--- /dev/null
+++ b/src/os/bluestore/StupidAllocator.cc
@@ -0,0 +1,371 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+#include "StupidAllocator.h"
+#include "bluestore_types.h"
+#include "common/debug.h"
+
+#define dout_context cct
+#define dout_subsys ceph_subsys_bluestore
+#undef dout_prefix
+#define dout_prefix *_dout << "stupidalloc 0x" << this << " "
+
+StupidAllocator::StupidAllocator(CephContext* cct,
+                                 const std::string& name,
+                                 int64_t _size,
+                                 int64_t _block_size)
+  : Allocator(name, _size, _block_size), cct(cct), num_free(0),
+    free(10)
+{
+  ceph_assert(cct != nullptr);
+  bdev_block_size = cct->_conf->bdev_block_size;
+}
+
+StupidAllocator::~StupidAllocator()
+{
+}
+
+unsigned StupidAllocator::_choose_bin(uint64_t orig_len)
+{
+  ceph_assert(bdev_block_size > 0);
+  uint64_t len = orig_len / bdev_block_size;
+  int bin = std::min((int)cbits(len), (int)free.size() - 1);
+  ldout(cct, 30) << __func__ << " len 0x" << std::hex << orig_len
+		 << std::dec << " -> " << bin << dendl;
+  return bin;
+}
+
+void StupidAllocator::_insert_free(uint64_t off, uint64_t len)
+{
+  unsigned bin = _choose_bin(len);
+  ldout(cct, 30) << __func__ << " 0x" << std::hex << off << "~" << len
+		 << std::dec << " in bin " << bin << dendl;
+  while (true) {
+    free[bin].insert(off, len, &off, &len);
+    unsigned newbin = _choose_bin(len);
+    if (newbin == bin)
+      break;
+    ldout(cct, 30) << __func__ << " promoting 0x" << std::hex << off << "~" << len
+		   << std::dec << " to bin " << newbin << dendl;
+    free[bin].erase(off, len);
+    bin = newbin;
+  }
+}
+
+/// return the effective length of the extent if we align to alloc_unit
+uint64_t StupidAllocator::_aligned_len(
+  StupidAllocator::interval_set_t::iterator p,
+  uint64_t alloc_unit)
+{
+  uint64_t skew = p.get_start() % alloc_unit;
+  if (skew)
+    skew = alloc_unit - skew;
+  if (skew > p.get_len())
+    return 0;
+  else
+    return p.get_len() - skew;
+}
+
+int64_t StupidAllocator::allocate_int(
+  uint64_t want_size, uint64_t alloc_unit, int64_t hint,
+  uint64_t *offset, uint32_t *length)
+{
+  std::lock_guard l(lock);
+  ldout(cct, 10) << __func__ << " want_size 0x" << std::hex << want_size
+	   	 << " alloc_unit 0x" << alloc_unit
+	   	 << " hint 0x" << hint << std::dec
+	   	 << dendl;
+  uint64_t want = std::max(alloc_unit, want_size);
+  int bin = _choose_bin(want);
+  int orig_bin = bin;
+
+  auto p = free[0].begin();
+
+  if (!hint)
+    hint = last_alloc;
+
+  // search up (from hint)
+  if (hint) {
+    for (bin = orig_bin; bin < (int)free.size(); ++bin) {
+      p = free[bin].lower_bound(hint);
+      while (p != free[bin].end()) {
+	if (_aligned_len(p, alloc_unit) >= want_size) {
+	  goto found;
+	}
+	++p;
+      }
+    }
+  }
+
+  // search up (from origin, and skip searched extents by hint)
+  for (bin = orig_bin; bin < (int)free.size(); ++bin) {
+    p = free[bin].begin();
+    auto end = hint ? free[bin].lower_bound(hint) : free[bin].end();
+    while (p != end) {
+      if (_aligned_len(p, alloc_unit) >= want_size) {
+	goto found;
+      }
+      ++p;
+    }
+  }
+
+  // search down (hint)
+  if (hint) {
+    for (bin = orig_bin; bin >= 0; --bin) {
+      p = free[bin].lower_bound(hint);
+      while (p != free[bin].end()) {
+	if (_aligned_len(p, alloc_unit) >= alloc_unit) {
+	  goto found;
+	}
+	++p;
+      }
+    }
+  }
+
+  // search down (from origin, and skip searched extents by hint)
+  for (bin = orig_bin; bin >= 0; --bin) {
+    p = free[bin].begin();
+    auto end = hint ? free[bin].lower_bound(hint) : free[bin].end();
+    while (p != end) {
+      if (_aligned_len(p, alloc_unit) >= alloc_unit) {
+	goto found;
+      }
+      ++p;
+    }
+  }
+
+  return -ENOSPC;
+
+ found:
+  uint64_t skew = p.get_start() % alloc_unit;
+  if (skew)
+    skew = alloc_unit - skew;
+  *offset = p.get_start() + skew;
+  *length = std::min(std::max(alloc_unit, want_size), p2align((p.get_len() - skew), alloc_unit));
+  if (cct->_conf->bluestore_debug_small_allocations) {
+    uint64_t max =
+      alloc_unit * (rand() % cct->_conf->bluestore_debug_small_allocations);
+    if (max && *length > max) {
+      ldout(cct, 10) << __func__ << " shortening allocation of 0x" << std::hex
+	       	     << *length << " -> 0x"
+	       	     << max << " due to debug_small_allocations" << std::dec
+		     << dendl;
+      *length = max;
+    }
+  }
+  ldout(cct, 30) << __func__ << " got 0x" << std::hex << *offset << "~" << *length
+	   	 << " from bin " << std::dec << bin << dendl;
+
+  free[bin].erase(*offset, *length);
+  uint64_t off, len;
+  if (*offset && free[bin].contains(*offset - skew - 1, &off, &len)) {
+    int newbin = _choose_bin(len);
+    if (newbin != bin) {
+      ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len
+	       	     << std::dec << " to bin " << newbin << dendl;
+      free[bin].erase(off, len);
+      _insert_free(off, len);
+    }
+  }
+  if (free[bin].contains(*offset + *length, &off, &len)) {
+    int newbin = _choose_bin(len);
+    if (newbin != bin) {
+      ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len
+	       	     << std::dec << " to bin " << newbin << dendl;
+      free[bin].erase(off, len);
+      _insert_free(off, len);
+    }
+  }
+
+  num_free -= *length;
+  ceph_assert(num_free >= 0);
+  last_alloc = *offset + *length;
+  return 0;
+}
+
+int64_t StupidAllocator::allocate(
+  uint64_t want_size,
+  uint64_t alloc_unit,
+  uint64_t max_alloc_size,
+  int64_t hint,
+  PExtentVector *extents)
+{
+  uint64_t allocated_size = 0;
+  uint64_t offset = 0;
+  uint32_t length = 0;
+  int res = 0;
+
+  if (max_alloc_size == 0) {
+    max_alloc_size = want_size;
+  }
+  // cap with 32-bit val
+  max_alloc_size = std::min(max_alloc_size, 0x10000000 - alloc_unit);
+
+  while (allocated_size < want_size) {
+    res = allocate_int(std::min(max_alloc_size, (want_size - allocated_size)),
+       alloc_unit, hint, &offset, &length);
+    if (res != 0) {
+      /*
+       * Allocation failed.
+       */
+      break;
+    }
+    bool can_append = true;
+    if (!extents->empty()) {
+      bluestore_pextent_t &last_extent  = extents->back();
+      if (last_extent.end() == offset) {
+        uint64_t l64 = last_extent.length;
+        l64 += length;
+        if (l64 < 0x100000000 && l64 <= max_alloc_size) {
+	  can_append = false;
+	  last_extent.length += length;
+        }
+      }
+    }
+    if (can_append) {
+      extents->emplace_back(bluestore_pextent_t(offset, length));
+    }
+
+    allocated_size += length;
+    hint = offset + length;
+  }
+
+  if (allocated_size == 0) {
+    return -ENOSPC;
+  }
+  return allocated_size;
+}
+
+void StupidAllocator::release(
+  const interval_set<uint64_t>& release_set)
+{
+  std::lock_guard l(lock);
+  for (interval_set<uint64_t>::const_iterator p = release_set.begin();
+       p != release_set.end();
+       ++p) {
+    const auto offset = p.get_start();
+    const auto length = p.get_len();
+    ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
+		   << std::dec << dendl;
+    _insert_free(offset, length);
+    num_free += length;
+  }
+}
+
+uint64_t StupidAllocator::get_free()
+{
+  std::lock_guard l(lock);
+  return num_free;
+}
+
+double StupidAllocator::get_fragmentation()
+{
+  ceph_assert(get_block_size());
+  double res;
+  uint64_t max_intervals = 0;
+  uint64_t intervals = 0;
+  {
+    std::lock_guard l(lock);
+    max_intervals = p2roundup<uint64_t>(num_free,
+                                        get_block_size()) / get_block_size();
+    for (unsigned bin = 0; bin < free.size(); ++bin) {
+      intervals += free[bin].num_intervals();
+    }
+  }
+  ldout(cct, 30) << __func__ << " " << intervals << "/" << max_intervals 
+                 << dendl;
+  ceph_assert(intervals <= max_intervals);
+  if (!intervals || max_intervals <= 1) {
+    return 0.0;
+  }
+  intervals--;
+  max_intervals--;
+  res = (double)intervals / max_intervals;
+  return res;
+}
+
+void StupidAllocator::dump()
+{
+  std::lock_guard l(lock);
+  for (unsigned bin = 0; bin < free.size(); ++bin) {
+    ldout(cct, 0) << __func__ << " free bin " << bin << ": "
+	    	  << free[bin].num_intervals() << " extents" << dendl;
+    for (auto p = free[bin].begin();
+	 p != free[bin].end();
+	 ++p) {
+      ldout(cct, 0) << __func__ << "  0x" << std::hex << p.get_start() << "~"
+	      	    << p.get_len() << std::dec << dendl;
+    }
+  }
+}
+
+void StupidAllocator::foreach(std::function<void(uint64_t offset, uint64_t length)> notify)
+{
+  std::lock_guard l(lock);
+  for (unsigned bin = 0; bin < free.size(); ++bin) {
+    for (auto p = free[bin].begin(); p != free[bin].end(); ++p) {
+      notify(p.get_start(), p.get_len());
+    }
+  }
+}
+
+void StupidAllocator::init_add_free(uint64_t offset, uint64_t length)
+{
+  if (!length)
+    return;
+  std::lock_guard l(lock);
+  ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
+		 << std::dec << dendl;
+  _insert_free(offset, length);
+  num_free += length;
+}
+
+void StupidAllocator::init_rm_free(uint64_t offset, uint64_t length)
+{
+  if (!length)
+    return;
+  std::lock_guard l(lock);
+  ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length
+	   	 << std::dec << dendl;
+  interval_set_t rm;
+  rm.insert(offset, length);
+  for (unsigned i = 0; i < free.size() && !rm.empty(); ++i) {
+    interval_set_t overlap;
+    overlap.intersection_of(rm, free[i]);
+    if (!overlap.empty()) {
+      ldout(cct, 20) << __func__ << " bin " << i << " rm 0x" << std::hex << overlap
+		     << std::dec << dendl;
+      auto it = overlap.begin();
+      auto it_end = overlap.end();
+      while (it != it_end) {
+        auto o = it.get_start();
+        auto l = it.get_len();
+
+        free[i].erase(o, l,
+          [&](uint64_t off, uint64_t len) {
+            unsigned newbin = _choose_bin(len);
+            if (newbin != i) {
+              ldout(cct, 30) << __func__ << " demoting1 0x" << std::hex << off << "~" << len
+                             << std::dec << " to bin " << newbin << dendl;
+              _insert_free(off, len);
+              return true;
+            }
+            return false;
+          });
+        ++it;
+      }
+
+      rm.subtract(overlap);
+    }
+  }
+  ceph_assert(rm.empty());
+  num_free -= length;
+  ceph_assert(num_free >= 0);
+}
+
+
+void StupidAllocator::shutdown()
+{
+  ldout(cct, 1) << __func__ << dendl;
+}
+