From 19fcec84d8d7d21e796c7624e521b60d28ee21ed Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:45:59 +0200 Subject: Adding upstream version 16.2.11+ds. Signed-off-by: Daniel Baumann --- src/os/bluestore/StupidAllocator.cc | 371 ++++++++++++++++++++++++++++++++++++ 1 file changed, 371 insertions(+) create mode 100644 src/os/bluestore/StupidAllocator.cc (limited to 'src/os/bluestore/StupidAllocator.cc') 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& release_set) +{ + std::lock_guard l(lock); + for (interval_set::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(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 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; +} + -- cgit v1.2.3