From 19692b88f119fc1cae6e06168e632051deeb05e4 Mon Sep 17 00:00:00 2001 From: Igor Fedotov Date: Fri, 2 Feb 2024 21:16:18 +0300 Subject: [PATCH] os/bluestore: refactor allocator histogram to use ExtentCollectionTraits Signed-off-by: Igor Fedotov --- src/os/bluestore/Allocator.cc | 108 ++++++++---------- src/os/bluestore/Allocator.h | 61 +++++++--- src/test/objectstore/Allocator_bench.cc | 28 +++-- src/test/objectstore/allocator_replay_test.cc | 27 +++-- 4 files changed, 123 insertions(+), 101 deletions(-) diff --git a/src/os/bluestore/Allocator.cc b/src/os/bluestore/Allocator.cc index 082e5fea5ef93..d522cbce9ff79 100644 --- a/src/os/bluestore/Allocator.cc +++ b/src/os/bluestore/Allocator.cc @@ -113,7 +113,7 @@ public: } else if (command == "bluestore allocator fragmentation histogram " + name) { int64_t alloc_unit = 4096; cmd_getval(cmdmap, "alloc_unit", alloc_unit); - if (alloc_unit == 0 || + if (alloc_unit <= 0 || p2align(alloc_unit, alloc->get_block_size()) != alloc_unit) { ss << "Invalid allocation unit: '" << alloc_unit << ", to be aligned with: '" << alloc->get_block_size() @@ -128,20 +128,22 @@ public: return -EINVAL; } - Allocator::FreeStateHistogram hist; - hist.resize(num_buckets); - alloc->build_free_state_histogram(alloc_unit, hist); + Allocator::FreeStateHistogram hist(num_buckets); + alloc->foreach( + [&](size_t off, size_t len) { + hist.record_extent(uint64_t(alloc_unit), off, len); + }); f->open_array_section("extent_counts"); - for(int i = 0; i < num_buckets; i++) { - f->open_object_section("c"); - f->dump_unsigned("max_len", - hist[i].get_max(i, num_buckets) - ); - f->dump_unsigned("total", hist[i].total); - f->dump_unsigned("aligned", hist[i].aligned); - f->dump_unsigned("units", hist[i].alloc_units); - f->close_section(); - } + hist.foreach( + [&](uint64_t max_len, uint64_t total, uint64_t aligned, uint64_t units) { + f->open_object_section("c"); + f->dump_unsigned("max_len", max_len); + f->dump_unsigned("total", total); + f->dump_unsigned("aligned", aligned); + f->dump_unsigned("units", units); + f->close_section(); + } + ); f->close_section(); } else { ss << "Invalid command" << std::endl; @@ -283,50 +285,40 @@ double Allocator::get_fragmentation_score() return (ideal - score_sum) / (ideal - terrible); } -void Allocator::build_free_state_histogram( - size_t alloc_unit, Allocator::FreeStateHistogram& hist) -{ - auto num_buckets = hist.size(); - ceph_assert(num_buckets); +/************* +* Allocator::FreeStateHistogram +*************/ +using std::function; - auto base = free_state_hist_bucket::base; - auto base_bits = free_state_hist_bucket::base_bits; - auto mux = free_state_hist_bucket::mux; - // maximum chunk size we track, - // provided by the bucket before the last one - size_t max = - free_state_hist_bucket::get_max(num_buckets - 2, num_buckets); - - auto iterated_allocation = [&](size_t off, size_t len) { - size_t idx; - if (len <= base) { - idx = 0; - } else if (len > max) { - idx = num_buckets - 1; - } else { - size_t most_bit = cbits(uint64_t(len-1)) - 1; - idx = 1 + ((most_bit - base_bits) / mux); - } - ceph_assert(idx < num_buckets); - ++hist[idx].total; - - // now calculate the bucket for the chunk after alignment, - // resulting chunks shorter than alloc_unit are discarded - auto delta = p2roundup(off, alloc_unit) - off; - if (len >= delta + alloc_unit) { - len -= delta; - if (len <= base) { - idx = 0; - } else if (len > max) { - idx = num_buckets - 1; - } else { - size_t most_bit = cbits(uint64_t(len-1)) - 1; - idx = 1 + ((most_bit - base_bits) / mux); - } - ++hist[idx].aligned; - hist[idx].alloc_units += len / alloc_unit; - } - }; +void Allocator::FreeStateHistogram::record_extent(uint64_t alloc_unit, + uint64_t off, + uint64_t len) +{ + size_t idx = myTraits._get_p2_size_bucket(len); + ceph_assert(idx < buckets.size()); + ++buckets[idx].total; - foreach(iterated_allocation); + // now calculate the bucket for the chunk after alignment, + // resulting chunks shorter than alloc_unit are discarded + auto delta = p2roundup(off, alloc_unit) - off; + if (len >= delta + alloc_unit) { + len -= delta; + idx = myTraits._get_p2_size_bucket(len); + ceph_assert(idx < buckets.size()); + ++buckets[idx].aligned; + buckets[idx].alloc_units += len / alloc_unit; + } +} +void Allocator::FreeStateHistogram::foreach( + function cb) +{ + size_t i = 0; + for (const auto& b : buckets) { + cb(myTraits._get_p2_size_bucket_max(i), + b.total, b.aligned, b.alloc_units); + ++i; + } } diff --git a/src/os/bluestore/Allocator.h b/src/os/bluestore/Allocator.h index e3d719a300502..163c2bf98cdfd 100644 --- a/src/os/bluestore/Allocator.h +++ b/src/os/bluestore/Allocator.h @@ -66,6 +66,16 @@ protected: ceph_assert(idx < num_buckets); return idx; } + /* + * returns upper bound of the bucket with log2(len) indexing. + */ + inline size_t _get_p2_size_bucket_max(size_t bucket) const { + return + bucket < num_buckets - 1 ? + base << (factor * bucket) : + std::numeric_limits::max(); + }; + /* * Determines bucket index for a given extent's length in a bucket collection * with linear (len / min_extent_size) indexing. @@ -76,6 +86,16 @@ protected: idx = idx < num_buckets ? idx : num_buckets - 1; return idx; } + /* + * returns upper bound of the bucket with + * linear(len / min_extent_size) indexing. + */ + inline size_t _get_linear_size_bucket_max(size_t bucket) const { + return + bucket < num_buckets - 1 ? + base * factor * (1 + bucket) : + std::numeric_limits::max(); + }; }; /* @@ -266,7 +286,7 @@ public: return block_size; } - // The following code build Allocator's free extents histogram. + // The following class implements Allocator's free extents histogram. // Which is a set of N buckets to track extents layout. // Extent matches a bucket depending on its length using the following // length spans: @@ -276,27 +296,30 @@ public: // - amount of extents aligned with allocation boundary // - amount of allocation units in aligned extents // - struct free_state_hist_bucket { - static const size_t base_bits = 12; - static const size_t base = 1ull << base_bits; - static const size_t mux = 2; + class FreeStateHistogram { + const Allocator::ExtentCollectionTraits myTraits; + enum { + BASE_BITS = 12, // 4096 bytes + FACTOR = 2, + }; + struct free_state_hist_bucket { + size_t total = 0; + size_t aligned = 0; + size_t alloc_units = 0; + }; + std::vector buckets; + public: - size_t total = 0; - size_t aligned = 0; - size_t alloc_units = 0; + FreeStateHistogram(size_t num_buckets) + : myTraits(num_buckets, BASE_BITS, FACTOR) { + buckets.resize(num_buckets); + } - // returns upper bound of the bucket - static size_t get_max(size_t bucket, size_t num_buckets) { - return - bucket < num_buckets - 1 ? - base << (mux * bucket) : - std::numeric_limits::max(); - }; + void record_extent(uint64_t alloc_unit, uint64_t off, uint64_t len); + void foreach( + std::function cb); }; - typedef std::vector FreeStateHistogram; - void build_free_state_histogram(size_t alloc_unit, FreeStateHistogram& hist); - private: class SocketHook; SocketHook* asok_hook = nullptr; @@ -305,4 +328,4 @@ protected: const int64_t block_size = 0; }; -#endif +#endif \ No newline at end of file diff --git a/src/test/objectstore/Allocator_bench.cc b/src/test/objectstore/Allocator_bench.cc index ec0c806a55948..1758d8c338e00 100644 --- a/src/test/objectstore/Allocator_bench.cc +++ b/src/test/objectstore/Allocator_bench.cc @@ -292,18 +292,22 @@ struct OverwriteTextContext : public Thread { } void build_histogram() { - size_t num_buckets = 8; - Allocator::FreeStateHistogram hist; - hist.resize(num_buckets); - alloc->build_free_state_histogram(alloc_unit, hist); - for (size_t i = 0; i < num_buckets; i++) { - uint64_t a_bytes = (hist[i].alloc_units * alloc_unit); - std::cout << "<=" << hist[i].get_max(i, num_buckets) - << " -> " << hist[i].total << "/" << hist[i].aligned - << " a_bytes " << a_bytes - << " " << ((float)a_bytes / alloc->get_capacity() * 100) << "%" - << std::endl; - } + const size_t num_buckets = 8; + Allocator::FreeStateHistogram hist(num_buckets); + alloc->foreach( + [&](size_t off, size_t len) { + hist.record_extent(uint64_t(alloc_unit), off, len); + }); + + hist.foreach( + [&](uint64_t max_len, uint64_t total, uint64_t aligned, uint64_t units) { + uint64_t a_bytes = units * alloc_unit; + std::cout << "<=" << max_len + << " -> " << total << "/" << aligned + << " a_bytes " << a_bytes + << " " << ((float)a_bytes / alloc->get_capacity() * 100) << "%" + << std::endl; + }); } void* entry() override { diff --git a/src/test/objectstore/allocator_replay_test.cc b/src/test/objectstore/allocator_replay_test.cc index 4229abe89c4ca..4a7682d10af2d 100644 --- a/src/test/objectstore/allocator_replay_test.cc +++ b/src/test/objectstore/allocator_replay_test.cc @@ -773,20 +773,23 @@ int main(int argc, char **argv) std::cout << "Allocation unit:" << alloc_unit << std::endl; - Allocator::FreeStateHistogram hist; - hist.resize(num_buckets); - a->build_free_state_histogram(alloc_unit, hist); + Allocator::FreeStateHistogram hist(num_buckets); + a->foreach( + [&](size_t off, size_t len) { + hist.record_extent(uint64_t(alloc_unit), off, len); + }); uint64_t s = 0; - for(int i = 0; i < num_buckets; i++) { - uint64_t e = hist[i].get_max(i, num_buckets); - std::cout << "(" << s << ".." << e << "]" - << " -> " << hist[i].total - << " chunks, " << hist[i].aligned << " aligned with " - << hist[i].alloc_units << " alloc_units." - << std::endl; - s = e; - } + hist.foreach( + [&](uint64_t max_len, uint64_t total, uint64_t aligned, uint64_t units) { + uint64_t e = max_len; + std::cout << "(" << s << ".." << e << "]" + << " -> " << total + << " chunks, " << aligned << " aligned with " + << units << " alloc_units." + << std::endl; + s = e; + }); return 0; }); } else if (strcmp(argv[2], "export_binary") == 0) { -- 2.39.5