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 <cbodley@redhat.com>

3 files changed, 364 insertions, 0 deletions

diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 3bf28659e1c..498b2662868 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 00000000000..eaa3886bd1f
--- /dev/null
+++ b/src/common/perf_counters_key.cc
@@ -0,0 +1,224 @@
+#include "common/perf_counters_key.h"
+
+#include <algorithm>
+#include <iterator>
+#include <numeric>
+
+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<char> 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 <std::contiguous_iterator Iterator>
+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<label_insert_iterator, label_pair>);
+  }
+
+  // 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<label_iterator>);
+}
+
+void label_iterator::advance(std::optional<iterator_state>& 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<iterator_state>
+{
+  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 00000000000..a476369b1d9
--- /dev/null
+++ b/src/common/perf_counters_key.h
@@ -0,0 +1,139 @@
+#pragma once
+
+#include <optional>
+#include <string>
+#include <utility>
+
+namespace ceph::perf_counters {
+
+/// A key/value pair representing a perf counter label
+using label_pair = std::pair<std::string_view, std::string_view>;
+
+
+/// \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<string, string>. 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::size_t Count>
+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::size_t Count>
+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<iterator_state> state;
+
+  // find the next two delimiters and construct the label string views
+  static void advance(std::optional<iterator_state>& s);
+
+  // try to parse the first label pair
+  static auto make_state(base_iterator begin, base_iterator end)
+      -> std::optional<iterator_state>;
+};
+
+/// 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::size_t Count>
+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::size_t Count>
+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