From a8a7ad74fd37995f3a9e13f436ef6108c1ced41c Mon Sep 17 00:00:00 2001 From: Casey Bodley Date: Wed, 17 Aug 2022 19:55:25 -0400 Subject: [PATCH] common: ceph::perf_counters::cache_key_insert() Signed-off-by: Casey Bodley --- src/common/CMakeLists.txt | 1 + src/common/perf_counters_cache_key.cc | 213 +++++++++++++++++++++++++ src/common/perf_counters_cache_key.h | 87 +++++----- src/test/common/test_perf_cache_key.cc | 80 +++++++--- 4 files changed, 314 insertions(+), 67 deletions(-) create mode 100644 src/common/perf_counters_cache_key.cc diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index 3bf28659e1c6d..fc32906193cbb 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -83,6 +83,7 @@ set(common_srcs options.cc page.cc perf_counters.cc + perf_counters_cache_key.cc perf_counters_collection.cc perf_histogram.cc pick_address.cc diff --git a/src/common/perf_counters_cache_key.cc b/src/common/perf_counters_cache_key.cc new file mode 100644 index 0000000000000..753b53f02c799 --- /dev/null +++ b/src/common/perf_counters_cache_key.cc @@ -0,0 +1,213 @@ +#include +#include +#include +#include +#include "common/perf_counters_cache_key.h" + +namespace ceph::perf_counters::detail { + +// use a null character to delimit strings +constexpr char delimiter = '\0'; + + +// write a delimited string to the output +auto write(std::string_view str, std::output_iterator auto out) +{ + out = std::copy(str.begin(), str.end(), out); + *(out++) = delimiter; + return out; +} + +// return the encoded size of a label +inline std::size_t label_size(const label_pair& l) +{ + return l.first.size() + sizeof(delimiter) + + l.second.size() + sizeof(delimiter); +} + +// a forward iterator over label_pairs encoded on a flat buffer +class label_iterator { + using base_iterator = const char*; + + struct iterator_state { + base_iterator pos; // end of current label + base_iterator end; // end of buffer + label_pair label; // current label + + auto operator<=>(const iterator_state& rhs) const = default; + }; + // an empty state represents a past-the-end iterator + std::optional state; + + // find the next two delimiters and construct the label string views + static void advance(std::optional& s) + { + auto d = std::find(s->pos, s->end, delimiter); + if (d == s->end) { // no delimiter for label key + s = std::nullopt; + return; + } + s->label.first = std::string_view{s->pos, d}; + s->pos = std::next(d); + + d = std::find(s->pos, s->end, delimiter); + if (d == s->end) { // no delimiter for label name + s = std::nullopt; + return; + } + s->label.second = std::string_view{s->pos, d}; + s->pos = std::next(d); + } + + // try to parse the first label pair + static auto make_state(base_iterator begin, base_iterator end) + { + std::optional state = iterator_state{begin, end}; + advance(state); + return state; + } + + public: + using difference_type = std::ptrdiff_t; + using value_type = label_pair; + using pointer = const value_type*; + using reference = const value_type&; + + label_iterator() = default; + label_iterator(base_iterator begin, base_iterator end) + : state(make_state(begin, end)) { + static_assert(std::forward_iterator); + } + + label_iterator& operator++() { + advance(state); + return *this; + } + label_iterator operator++(int) { + label_iterator tmp = *this; + advance(state); + return tmp; + } + + reference operator*() const { return state->label; } + pointer operator->() const { return &state->label; } + + auto operator<=>(const label_iterator& rhs) const = default; +}; + +// an output iterator that writes label_pairs to a flat buffer +template +class label_insert_iterator { + using base_iterator = Iterator; + + struct label_writer { + base_iterator pos; // write position + + label_writer& operator=(const label_pair& l) { + pos = write(l.first, pos); + pos = write(l.second, pos); + return *this; + } + }; + label_writer label; + + public: + using difference_type = std::ptrdiff_t; + using value_type = label_writer; + using reference = value_type&; + + label_insert_iterator(base_iterator begin) : label{begin} { + static_assert(std::output_iterator); + } + + // increments are noops + label_insert_iterator& operator++() { return *this; } + label_insert_iterator operator++(int) { return *this; } + + // can only dereference to assign + reference operator*() { return label; } + + // return the wrapped iterator position + base_iterator base() { return label.pos; } +}; + +// compare label_pairs by their key only +struct label_key_less { + bool operator()(const label_pair& lhs, const label_pair& rhs) const { + return lhs.first < rhs.first; + } +}; +struct label_key_equal { + bool operator()(const label_pair& lhs, const label_pair& rhs) const { + return lhs.first == rhs.first; + } +}; + +std::string create(std::string_view counter_name, + label_pair* begin, label_pair* end) +{ + // sort the input labels and remove duplicate keys + std::sort(begin, end, label_key_less{}); + end = std::unique(begin, end, label_key_equal{}); + + // calculate the total size and preallocate the buffer + auto size = std::accumulate(begin, end, + counter_name.size() + sizeof(delimiter), + [] (std::size_t sum, const label_pair& l) { + return sum + label_size(l); + }); + std::string result; + result.resize(size); + + // copy out the counter name and labels + auto out = result.begin(); + out = write(counter_name, out); + std::copy(begin, end, label_insert_iterator{out}); + + return result; +} + +std::string insert(const char* begin1, const char* end1, + label_pair* begin2, label_pair* end2) +{ + // sort the input labels and remove duplicate keys + std::sort(begin2, end2, label_key_less{}); + end2 = std::unique(begin2, end2, label_key_equal{}); + + // find the first delimiter that marks the end of the counter name + auto pos = std::find(begin1, end1, delimiter); + + // calculate the total size and preallocate the buffer + auto size = std::distance(begin1, end1); + if (pos == end1) { // add a delimiter if the key doesn't have one + size += sizeof(delimiter); + } + size = std::accumulate(begin2, end2, size, + [] (std::size_t sum, const label_pair& l) { + return sum + label_size(l); + }); + std::string result; + result.resize(size); + + // copy the counter name without the delimiter + auto out = std::copy(begin1, pos, result.begin()); + if (pos != end1) { + ++pos; // advance past the delimiter + } + *(out++) = delimiter; + + // merge the two sorted input ranges, drop any duplicate keys, and write + // them to output. the begin2 range is first so that new input labels can + // replace existing duplicates + auto end = std::set_union(begin2, end2, + label_iterator{pos, end1}, + label_iterator{end1, end1}, + label_insert_iterator{out}, + label_key_less{}); + // fix up the size in case set_union() removed any duplicates + result.resize(std::distance(result.begin(), end.base())); + + return result; +} + +} // namespace ceph::perf_counters::detail diff --git a/src/common/perf_counters_cache_key.h b/src/common/perf_counters_cache_key.h index 67250811fbd5c..42d296780d52c 100644 --- a/src/common/perf_counters_cache_key.h +++ b/src/common/perf_counters_cache_key.h @@ -1,9 +1,6 @@ #pragma once -#include -#include -#include -#include +#include #include namespace ceph::perf_counters { @@ -13,54 +10,52 @@ using label_pair = std::pair; /// construct a cache key for a perf counter and set of labels. returns a string -/// of the form "counter_name\0key1\0value1\0key2\0value2\0", where label pairs -/// are insertion-sorted by key then value +/// of the form "counter_name\0key1\0val1\0key2\0val2\0", where label pairs +/// are sorted by key with duplicates removed template -constexpr std::string make_cache_key(std::string_view counter_name, - label_pair (&&sorted)[Count]) +std::string cache_key(std::string_view counter_name, + label_pair (&&labels)[Count]); + +/// \overload +std::string cache_key(std::string_view counter_name); + +/// insert additional labels to an existing label set. this returns a new +/// string without modifying the existing one. the returned string has labels +/// in sorted order and no duplicate keys +template +std::string cache_key_insert(std::string_view key, + label_pair (&&labels)[Count]); + + +namespace detail { + +std::string create(std::string_view counter_name, + label_pair* begin, label_pair* end); + +std::string insert(const char* begin1, const char* end1, + label_pair* begin2, label_pair* end2); + +} // namespace detail + +template +std::string cache_key(std::string_view counter_name, + label_pair (&&labels)[Count]) { - std::sort(std::begin(sorted), std::end(sorted)); - - // use a null character to delimit strings - constexpr char delimiter = '\0'; - - // calculate the total size and preallocate the buffer - auto size = std::accumulate(std::begin(sorted), std::end(sorted), - counter_name.size() + sizeof(delimiter), - [] (std::size_t sum, const label_pair& l) { - return sum + l.first.size() + sizeof(delimiter) - + l.second.size() + sizeof(delimiter); - }); - - std::string result; - result.resize(size); - - auto pos = result.begin(); - pos = std::copy(counter_name.begin(), counter_name.end(), pos); - *(pos++) = delimiter; - - for (const auto& label : sorted) { - pos = std::copy(label.first.begin(), label.first.end(), pos); - *(pos++) = delimiter; - pos = std::copy(label.second.begin(), label.second.end(), pos); - *(pos++) = delimiter; - } - - return result; + return detail::create(counter_name, std::begin(labels), std::end(labels)); } -constexpr std::string make_cache_key(std::string_view counter_name) +std::string cache_key(std::string_view counter_name) { - constexpr char delimiter = '\0'; - const auto size = counter_name.size() + sizeof(delimiter); - std::string result; - result.resize(size); - auto pos = result.begin(); - pos = std::copy(counter_name.begin(), counter_name.end(), pos); - *(pos++) = delimiter; - return result; + label_pair* end = nullptr; + return detail::create(counter_name, end, end); } -// TODO: cache_key_insert() to add more labels to an existing string +template +std::string cache_key_insert(std::string_view key, + label_pair (&&labels)[Count]) +{ + return detail::insert(key.begin(), key.end(), + std::begin(labels), std::end(labels)); +} } // namespace ceph::perf_counters diff --git a/src/test/common/test_perf_cache_key.cc b/src/test/common/test_perf_cache_key.cc index 6ba186ad7ac8c..570d4b2daf8fc 100644 --- a/src/test/common/test_perf_cache_key.cc +++ b/src/test/common/test_perf_cache_key.cc @@ -3,43 +3,81 @@ namespace ceph::perf_counters { -TEST(PerfCounters, CacheKey) +TEST(PerfCounters, cache_key) { - EXPECT_EQ(make_cache_key(""), + EXPECT_EQ(cache_key(""), std::string_view("\0", 1)); - EXPECT_EQ(make_cache_key("perf"), + EXPECT_EQ(cache_key("perf"), std::string_view("perf\0", 5)); - EXPECT_EQ(make_cache_key("perf", {{"",""}}), + EXPECT_EQ(cache_key("perf", {{"",""}}), std::string_view("perf\0\0\0", 7)); - EXPECT_EQ(make_cache_key("perf", {{"",""}, {"",""}}), - std::string_view("perf\0\0\0\0\0", 9)); + EXPECT_EQ(cache_key("perf", {{"","a"}, {"",""}}), + std::string_view("perf\0\0a\0", 8)); - EXPECT_EQ(make_cache_key("perf", {{"a","b"}}), + EXPECT_EQ(cache_key("perf", {{"a","b"}}), std::string_view("perf\0a\0b\0", 9)); - EXPECT_EQ(make_cache_key("perf", {{"y","z"}, {"a","b"}}), + EXPECT_EQ(cache_key("perf", {{"y","z"}, {"a","b"}}), std::string_view("perf\0a\0b\0y\0z\0", 13)); - EXPECT_EQ(make_cache_key("perf", {{"a","b"}, {"a","c"}}), - std::string_view("perf\0a\0b\0a\0c\0", 13)); + EXPECT_EQ(cache_key("perf", {{"a","b"}, {"a","c"}}), + std::string_view("perf\0a\0b\0", 9)); - EXPECT_EQ(make_cache_key("perf", {{"a","z"}, {"a","b"}}), - std::string_view("perf\0a\0b\0a\0z\0", 13)); + EXPECT_EQ(cache_key("perf", {{"a","z"}, {"a","b"}}), + std::string_view("perf\0a\0z\0", 9)); - EXPECT_EQ(make_cache_key("perf", {{"d",""}, {"c",""}, {"b",""}, {"a",""}}), + EXPECT_EQ(cache_key("perf", {{"d",""}, {"c",""}, {"b",""}, {"a",""}}), std::string_view("perf\0a\0\0b\0\0c\0\0d\0\0", 17)); +} + +TEST(PerfCounters, cache_key_insert) +{ + EXPECT_EQ(cache_key_insert("", {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(cache_key_insert("", {{"",""}, {"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(cache_key_insert(std::string_view{"\0\0\0", 3}, {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(cache_key_insert(std::string_view{"\0", 1}, {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(cache_key_insert("", {{"a","b"}}), + std::string_view("\0a\0b\0", 5)); + + EXPECT_EQ(cache_key_insert(std::string_view{"\0", 1}, {{"a","b"}}), + std::string_view("\0a\0b\0", 5)); + + EXPECT_EQ(cache_key_insert("a", {{"",""}}), + std::string_view("a\0\0\0", 4)); + + EXPECT_EQ(cache_key_insert(std::string_view{"a\0", 2}, {{"",""}}), + std::string_view("a\0\0\0", 4)); + + EXPECT_EQ(cache_key_insert(std::string_view{"p\0", 2}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(cache_key_insert(std::string_view{"p\0a\0a\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(cache_key_insert(std::string_view{"p\0a\0z\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(cache_key_insert(std::string_view{"p\0z\0z\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0z\0z\0", 10)); + + EXPECT_EQ(cache_key_insert(std::string_view{"p\0b\0b\0", 6}, + {{"a","a"}, {"c","c"}}), + std::string_view("p\0a\0a\0b\0b\0c\0c\0", 14)); - // error: ‘ceph::perf_counters::make_cache_key(...)’ is not a constant - // expression because it refers to a result of ‘operator new’ -#if 0 - constexpr auto constexpr_key = make_cache_key("perf", { - {"d",""},{"c",""},{"b",""},{"a",""} - }); - EXPECT_EQ(constexpr_key, std::string_view("perf\0a\0\0b\0\0c\0\0d\0\0", 17)); -#endif + EXPECT_EQ(cache_key_insert(std::string_view{"p\0a\0a\0b\0b\0c\0c\0", 14}, + {{"z","z"}, {"b","z"}}), + std::string_view("p\0a\0a\0b\0z\0c\0c\0z\0z\0", 18)); } } // namespace ceph::perf_counters -- 2.39.5