From f427bb2d2cc8ad067f1c68673bc5be26844772e6 Mon Sep 17 00:00:00 2001 From: Casey Bodley Date: Wed, 17 Aug 2022 09:27:42 -0400 Subject: [PATCH] common: add abstraction for label-aware perf counter keys a flat representation of a set of prometheus labels, returned as a std::string. this string can either be used for sorting an ordered container of perf counters, or for hashing an unordered container Signed-off-by: Casey Bodley --- src/common/CMakeLists.txt | 1 + src/common/perf_counters_key.cc | 224 ++++++++++++++++++++++ src/common/perf_counters_key.h | 139 ++++++++++++++ src/test/common/CMakeLists.txt | 5 + src/test/common/test_perf_counters_key.cc | 129 +++++++++++++ 5 files changed, 498 insertions(+) create mode 100644 src/common/perf_counters_key.cc create mode 100644 src/common/perf_counters_key.h create mode 100644 src/test/common/test_perf_counters_key.cc diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index 3bf28659e1c6d..498b2662868af 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -84,6 +84,7 @@ set(common_srcs page.cc perf_counters.cc perf_counters_collection.cc + perf_counters_key.cc perf_histogram.cc pick_address.cc random_string.cc diff --git a/src/common/perf_counters_key.cc b/src/common/perf_counters_key.cc new file mode 100644 index 0000000000000..eaa3886bd1f3e --- /dev/null +++ b/src/common/perf_counters_key.cc @@ -0,0 +1,224 @@ +#include "common/perf_counters_key.h" + +#include +#include +#include + +namespace ceph::perf_counters { +namespace 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); +} + +// 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() = default; + 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 +bool label_key_less(const label_pair& lhs, const label_pair& rhs) +{ + return lhs.first < rhs.first; +} +bool label_key_equal(const label_pair& lhs, const label_pair& rhs) +{ + 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; +} + +std::string_view name(const char* begin, const char* end) +{ + auto pos = std::find(begin, end, DELIMITER); + return {begin, pos}; +} + +std::string_view labels(const char* begin, const char* end) +{ + auto pos = std::find(begin, end, DELIMITER); + if (pos == end) { + return {}; + } + return {std::next(pos), end}; +} + +} // namespace detail + + +std::string key_create(std::string_view counter_name) +{ + label_pair* end = nullptr; + return detail::create(counter_name, end, end); +} + +std::string_view key_name(std::string_view key) +{ + return detail::name(key.begin(), key.end()); +} + +label_range key_labels(std::string_view key) +{ + return detail::labels(key.begin(), key.end()); +} + + +label_iterator::label_iterator(base_iterator begin, base_iterator end) + : state(make_state(begin, end)) +{ + static_assert(std::forward_iterator); +} + +void label_iterator::advance(std::optional& s) +{ + auto d = std::find(s->pos, s->end, detail::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, detail::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); +} + +auto label_iterator::make_state(base_iterator begin, base_iterator end) + -> std::optional +{ + std::optional state = iterator_state{begin, end}; + advance(state); + return state; +} + +label_iterator& label_iterator::operator++() +{ + advance(state); + return *this; +} + +label_iterator label_iterator::operator++(int) +{ + label_iterator tmp = *this; + advance(state); + return tmp; +} + +} // namespace ceph::perf_counters diff --git a/src/common/perf_counters_key.h b/src/common/perf_counters_key.h new file mode 100644 index 0000000000000..a476369b1d926 --- /dev/null +++ b/src/common/perf_counters_key.h @@ -0,0 +1,139 @@ +#pragma once + +#include +#include +#include + +namespace ceph::perf_counters { + +/// A key/value pair representing a perf counter label +using label_pair = std::pair; + + +/// \brief Construct a key for a perf counter and set of labels. +/// +/// Returns a string of the form "counter_name\0key1\0val1\0key2\0val2\0", +/// where label pairs are sorted by key with duplicates removed. +/// +/// This string representation avoids extra memory allocations associated +/// with map. It also supports the hashing and comparison +/// operators required for use as a key in unordered and ordered containers. +/// +/// Example: +/// \code +/// std::string key = key_create("counter_name", { +/// {"key1", "val1"}, {"key2", "val2"} +/// }); +/// \endcode +template +std::string key_create(std::string_view counter_name, + label_pair (&&labels)[Count]); + +/// \brief Construct a key for a perf counter without labels. +/// \overload +std::string key_create(std::string_view counter_name); + +/// \brief Insert additional labels into an existing key. +/// +/// This returns a new string without modifying the input. The returned +/// string has labels in sorted order and no duplicate keys. +template +std::string key_insert(std::string_view key, + label_pair (&&labels)[Count]); + +/// \brief Return the counter name for a given key. +std::string_view key_name(std::string_view key); + + +/// A forward iterator over label_pairs encoded in a key +class label_iterator { + public: + using base_iterator = const char*; + 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); + + label_iterator& operator++(); + label_iterator operator++(int); + + reference operator*() const { return state->label; } + pointer operator->() const { return &state->label; } + + auto operator<=>(const label_iterator& rhs) const = default; + + private: + 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); + + // try to parse the first label pair + static auto make_state(base_iterator begin, base_iterator end) + -> std::optional; +}; + +/// A sorted range of label_pairs +class label_range { + std::string_view buffer; + public: + using iterator = label_iterator; + using const_iterator = label_iterator; + + label_range(std::string_view buffer) : buffer(buffer) {} + + const_iterator begin() const { return {buffer.begin(), buffer.end()}; } + const_iterator cbegin() const { return {buffer.begin(), buffer.end()}; } + + const_iterator end() const { return {}; } + const_iterator cend() const { return {}; } +}; + +/// \brief Return the sorted range of label_pairs for a given key. +/// +/// Example: +/// \code +/// for (label_pair label : key_labels(key)) { +/// std::cout << label.first << ":" << label.second << std::endl; +/// } +/// \endcode +label_range key_labels(std::string_view key); + + +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 key_create(std::string_view counter_name, + label_pair (&&labels)[Count]) +{ + return detail::create(counter_name, std::begin(labels), std::end(labels)); +} + +template +std::string 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/CMakeLists.txt b/src/test/common/CMakeLists.txt index 28738c0908538..1179fbdfb8215 100644 --- a/src/test/common/CMakeLists.txt +++ b/src/test/common/CMakeLists.txt @@ -294,6 +294,11 @@ add_executable(unittest_perf_histogram add_ceph_unittest(unittest_perf_histogram) target_link_libraries(unittest_perf_histogram ceph-common) +# unittest_perf_cache_key +add_executable(unittest_perf_counters_key test_perf_counters_key.cc) +add_ceph_unittest(unittest_perf_counters_key) +target_link_libraries(unittest_perf_counters_key ceph-common) + # unittest_global_doublefree if(WITH_CEPHFS) add_executable(unittest_global_doublefree diff --git a/src/test/common/test_perf_counters_key.cc b/src/test/common/test_perf_counters_key.cc new file mode 100644 index 0000000000000..5a156c749b207 --- /dev/null +++ b/src/test/common/test_perf_counters_key.cc @@ -0,0 +1,129 @@ +#include "common/perf_counters_key.h" +#include + +namespace ceph::perf_counters { + +TEST(PerfCounters, key_create) +{ + EXPECT_EQ(key_create(""), + std::string_view("\0", 1)); + + EXPECT_EQ(key_create("perf"), + std::string_view("perf\0", 5)); + + EXPECT_EQ(key_create("perf", {{"",""}}), + std::string_view("perf\0\0\0", 7)); + + EXPECT_EQ(key_create("perf", {{"","a"}, {"",""}}), + std::string_view("perf\0\0a\0", 8)); + + EXPECT_EQ(key_create("perf", {{"a","b"}}), + std::string_view("perf\0a\0b\0", 9)); + + EXPECT_EQ(key_create("perf", {{"y","z"}, {"a","b"}}), + std::string_view("perf\0a\0b\0y\0z\0", 13)); + + EXPECT_EQ(key_create("perf", {{"a","b"}, {"a","c"}}), + std::string_view("perf\0a\0b\0", 9)); + + EXPECT_EQ(key_create("perf", {{"a","z"}, {"a","b"}}), + std::string_view("perf\0a\0z\0", 9)); + + EXPECT_EQ(key_create("perf", {{"d",""}, {"c",""}, {"b",""}, {"a",""}}), + std::string_view("perf\0a\0\0b\0\0c\0\0d\0\0", 17)); +} + +TEST(PerfCounters, key_insert) +{ + EXPECT_EQ(key_insert("", {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(key_insert("", {{"",""}, {"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(key_insert(std::string_view{"\0\0\0", 3}, {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(key_insert(std::string_view{"\0", 1}, {{"",""}}), + std::string_view("\0\0\0", 3)); + + EXPECT_EQ(key_insert("", {{"a","b"}}), + std::string_view("\0a\0b\0", 5)); + + EXPECT_EQ(key_insert(std::string_view{"\0", 1}, {{"a","b"}}), + std::string_view("\0a\0b\0", 5)); + + EXPECT_EQ(key_insert("a", {{"",""}}), + std::string_view("a\0\0\0", 4)); + + EXPECT_EQ(key_insert(std::string_view{"a\0", 2}, {{"",""}}), + std::string_view("a\0\0\0", 4)); + + EXPECT_EQ(key_insert(std::string_view{"p\0", 2}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(key_insert(std::string_view{"p\0a\0a\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(key_insert(std::string_view{"p\0a\0z\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0", 6)); + + EXPECT_EQ(key_insert(std::string_view{"p\0z\0z\0", 6}, {{"a","b"}}), + std::string_view("p\0a\0b\0z\0z\0", 10)); + + EXPECT_EQ(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)); + + EXPECT_EQ(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)); +} + +TEST(PerfCounters, key_name) +{ + EXPECT_EQ(key_name(""), + ""); + EXPECT_EQ(key_name({"\0", 1}), + ""); + EXPECT_EQ(key_name({"perf\0", 5}), + "perf"); + EXPECT_EQ(key_name({"perf\0\0\0", 7}), + "perf"); +} + +TEST(PerfCounters, key_labels) +{ + { + auto labels = key_labels(""); + EXPECT_EQ(labels.begin(), labels.end()); + } + { + auto labels = key_labels({"\0", 1}); + EXPECT_EQ(labels.begin(), labels.end()); + } + { + auto labels = key_labels({"perf\0", 5}); + EXPECT_EQ(labels.begin(), labels.end()); + } + { + auto labels = key_labels({"\0\0\0", 3}); + ASSERT_EQ(1, std::distance(labels.begin(), labels.end())); + EXPECT_EQ(label_pair("", ""), *labels.begin()); + } + { + auto labels = key_labels({"\0a\0b\0", 5}); + ASSERT_EQ(1, std::distance(labels.begin(), labels.end())); + EXPECT_EQ(label_pair("a", "b"), *labels.begin()); + EXPECT_EQ(std::next(labels.begin()), labels.end()); + } + { + auto labels = key_labels({"\0a\0b\0c\0d\0", 9}); + ASSERT_EQ(2, std::distance(labels.begin(), labels.end())); + EXPECT_EQ(label_pair("a", "b"), *labels.begin()); + EXPECT_EQ(label_pair("c", "d"), *std::next(labels.begin())); + EXPECT_EQ(std::next(labels.begin(), 2), labels.end()); + } +} + +} // namespace ceph::perf_counters -- 2.39.5