metrics: Add support for histograms.

This will enable us to add e.g. circuit build metrics (#40717).

Signed-off-by: Gabriela Moldovan <gabi@torproject.org>

7 files changed, 264 insertions, 13 deletions

diff --git a/src/lib/metrics/metrics_common.c b/src/lib/metrics/metrics_common.c
index f3f7e22d88..5836a581f1 100644
--- a/src/lib/metrics/metrics_common.c
+++ b/src/lib/metrics/metrics_common.c
@@ -24,6 +24,8 @@ metrics_type_to_str(const metrics_type_t type)
     return "counter";
   case METRICS_TYPE_GAUGE:
     return "gauge";
+  case METRICS_TYPE_HISTOGRAM:
+    return "histogram";
   default:
     tor_assert_unreached();
   }
diff --git a/src/lib/metrics/metrics_common.h b/src/lib/metrics/metrics_common.h
index 3644ad3d50..6c8e8bdbdc 100644
--- a/src/lib/metrics/metrics_common.h
+++ b/src/lib/metrics/metrics_common.h
@@ -10,6 +10,7 @@
 #define TOR_LIB_METRICS_METRICS_COMMON_H
 
 #include "lib/cc/torint.h"
+#include "lib/container/smartlist.h"
 
 /** Helper macro that must be used to construct the right namespaced metrics
  * name. A name is a string so stringify the result. */
@@ -28,8 +29,18 @@ typedef enum {
   METRICS_TYPE_COUNTER,
   /* Can go up or down. */
   METRICS_TYPE_GAUGE,
+  /* Cumulative counters for multiple observation buckets. */
+  METRICS_TYPE_HISTOGRAM,
 } metrics_type_t;
 
+typedef struct metrics_histogram_bucket_t {
+  /* The value of the counter of this bucket. */
+  uint64_t value;
+  /* Technically, this should be a floating point value, but in practice, we
+   * can make do with integer buckets. */
+  int64_t bucket;
+} metrics_histogram_bucket_t;
+
 /** Metric counter object (METRICS_TYPE_COUNTER). */
 typedef struct metrics_counter_t {
   uint64_t value;
@@ -40,6 +51,18 @@ typedef struct metrics_gauge_t {
   int64_t value;
 } metrics_gauge_t;
 
+/** Metric histogram object (METRICS_TYPE_HISTOGRAM). */
+typedef struct metrics_histogram_t {
+  /* The observation buckets. */
+  metrics_histogram_bucket_t *buckets;
+  /* The number of observation buckets. */
+  size_t bucket_count;
+  /* The sum of all observations */
+  int64_t sum;
+  /* The total number of observations */
+  uint64_t count;
+} metrics_histogram_t;
+
 const char *metrics_type_to_str(const metrics_type_t type);
 
 /* Helpers. */
diff --git a/src/lib/metrics/metrics_store.c b/src/lib/metrics/metrics_store.c
index b017e97688..db80ca029b 100644
--- a/src/lib/metrics/metrics_store.c
+++ b/src/lib/metrics/metrics_store.c
@@ -107,7 +107,9 @@ metrics_store_get_all(const metrics_store_t *store, const char *name)
  * unique identifier. The help string can be omitted. */
 metrics_store_entry_t *
 metrics_store_add(metrics_store_t *store, metrics_type_t type,
-                  const char *name, const char *help)
+                  const char *name, const char *help, size_t bucket_count,
+                  const int64_t *buckets)
+
 {
   smartlist_t *entries;
   metrics_store_entry_t *entry;
@@ -120,7 +122,7 @@ metrics_store_add(metrics_store_t *store, metrics_type_t type,
     entries = smartlist_new();
     strmap_set(store->entries, name, entries);
   }
-  entry = metrics_store_entry_new(type, name, help);
+  entry = metrics_store_entry_new(type, name, help, bucket_count, buckets);
   smartlist_add(entries, entry);
 
   return entry;
diff --git a/src/lib/metrics/metrics_store.h b/src/lib/metrics/metrics_store.h
index d85f484bd6..d06c87303c 100644
--- a/src/lib/metrics/metrics_store.h
+++ b/src/lib/metrics/metrics_store.h
@@ -26,8 +26,10 @@ metrics_store_t *metrics_store_new(void);
 
 /* Modifiers. */
 metrics_store_entry_t *metrics_store_add(metrics_store_t *store,
-                                         metrics_type_t type,
-                                         const char *name, const char *help);
+                                         metrics_type_t type, const char *name,
+                                         const char *help, size_t bucket_count,
+                                         const int64_t *buckets);
+
 void metrics_store_reset(metrics_store_t *store);
 
 /* Accessors. */
diff --git a/src/lib/metrics/metrics_store_entry.c b/src/lib/metrics/metrics_store_entry.c
index 971d9379bd..649fd660c3 100644
--- a/src/lib/metrics/metrics_store_entry.c
+++ b/src/lib/metrics/metrics_store_entry.c
@@ -6,6 +6,7 @@
  * @brief Metrics store entry which contains the gathered data.
  **/
 
+#include "metrics_common.h"
 #define METRICS_STORE_ENTRY_PRIVATE
 
 #include <string.h>
@@ -22,10 +23,11 @@
  * Public API.
  */
 
-/** Return newly allocated store entry of type COUNTER. */
+/** Return newly allocated store entry of the specified type. */
 metrics_store_entry_t *
 metrics_store_entry_new(const metrics_type_t type, const char *name,
-                        const char *help)
+                        const char *help, size_t bucket_count,
+                        const int64_t *buckets)
 {
   metrics_store_entry_t *entry = tor_malloc_zero(sizeof(*entry));
 
@@ -38,6 +40,18 @@ metrics_store_entry_new(const metrics_type_t type, const char *name,
     entry->help = tor_strdup(help);
   }
 
+  if (type == METRICS_TYPE_HISTOGRAM && bucket_count > 0) {
+    tor_assert(buckets);
+
+    entry->u.histogram.bucket_count = bucket_count;
+    entry->u.histogram.buckets =
+        tor_malloc_zero(sizeof(metrics_histogram_bucket_t) * bucket_count);
+
+    for (size_t i = 0; i < bucket_count; ++i) {
+      entry->u.histogram.buckets[i].bucket = buckets[i];
+    }
+  }
+
   return entry;
 }
 
@@ -52,6 +66,11 @@ metrics_store_entry_free_(metrics_store_entry_t *entry)
   smartlist_free(entry->labels);
   tor_free(entry->name);
   tor_free(entry->help);
+
+  if (entry->type == METRICS_TYPE_HISTOGRAM) {
+    tor_free(entry->u.histogram.buckets);
+  }
+
   tor_free(entry);
 }
 
@@ -61,6 +80,11 @@ metrics_store_entry_update(metrics_store_entry_t *entry, const int64_t value)
 {
   tor_assert(entry);
 
+  /* Histogram values are updated using metrics_store_hist_entry_update */
+  if (BUG(entry->type == METRICS_TYPE_HISTOGRAM)) {
+    return;
+  }
+
   switch (entry->type) {
   case METRICS_TYPE_COUNTER:
     /* Counter can ONLY be positive. */
@@ -73,6 +97,43 @@ metrics_store_entry_update(metrics_store_entry_t *entry, const int64_t value)
     /* Gauge can increment or decrement. And can be positive or negative. */
     entry->u.gauge.value += value;
     break;
+  case METRICS_TYPE_HISTOGRAM:
+    tor_assert_unreached();
+  }
+}
+
+/** Update a store entry with value for the specified observation obs.
+ *
+ * Note: entry **must** be a histogram. */
+void
+metrics_store_hist_entry_update(metrics_store_entry_t *entry,
+                                const int64_t value, const int64_t obs)
+{
+  if (BUG(entry->type != METRICS_TYPE_HISTOGRAM)) {
+    return;
+  }
+
+  /* Counter can ONLY be positive for histograms. */
+  if (BUG(value < 0)) {
+    return;
+  }
+
+  /* If we're about to overflow or underflow the sum, reset all counters back
+   * to 0 before recording the observation. */
+  if (PREDICT_UNLIKELY(
+          (obs > 0 && entry->u.histogram.sum > INT64_MAX - obs) ||
+          (obs < 0 && entry->u.histogram.sum < INT64_MIN - obs))) {
+    metrics_store_entry_reset(entry);
+  }
+
+  entry->u.histogram.count += value;
+  entry->u.histogram.sum += obs;
+
+  for (size_t i = 0; i < entry->u.histogram.bucket_count; ++i) {
+    metrics_histogram_bucket_t *hb = &entry->u.histogram.buckets[i];
+    if (obs <= hb->bucket) {
+      hb->value += value;
+    }
   }
 }
 
@@ -81,8 +142,22 @@ void
 metrics_store_entry_reset(metrics_store_entry_t *entry)
 {
   tor_assert(entry);
-  /* Everything back to 0. */
-  memset(&entry->u, 0, sizeof(entry->u));
+
+  switch (entry->type) {
+  case METRICS_TYPE_COUNTER: FALLTHROUGH;
+  case METRICS_TYPE_GAUGE:
+    /* Everything back to 0. */
+    memset(&entry->u, 0, sizeof(entry->u));
+    break;
+  case METRICS_TYPE_HISTOGRAM:
+    for (size_t i = 0; i < entry->u.histogram.bucket_count; ++i) {
+      metrics_histogram_bucket_t *hb = &entry->u.histogram.buckets[i];
+      hb->value = 0;
+    }
+    entry->u.histogram.sum = 0;
+    entry->u.histogram.count = 0;
+    break;
+  }
 }
 
 /** Return store entry value. */
@@ -91,6 +166,11 @@ metrics_store_entry_get_value(const metrics_store_entry_t *entry)
 {
   tor_assert(entry);
 
+  /* Histogram values are accessed using metrics_store_hist_entry_get_value. */
+  if (BUG(entry->type == METRICS_TYPE_HISTOGRAM)) {
+    return 0;
+  }
+
   switch (entry->type) {
   case METRICS_TYPE_COUNTER:
     if (entry->u.counter.value > INT64_MAX) {
@@ -99,6 +179,9 @@ metrics_store_entry_get_value(const metrics_store_entry_t *entry)
     return entry->u.counter.value;
   case METRICS_TYPE_GAUGE:
     return entry->u.gauge.value;
+  case METRICS_TYPE_HISTOGRAM:
+    tor_assert_unreached();
+    return 0;
   }
 
   // LCOV_EXCL_START
@@ -106,6 +189,35 @@ metrics_store_entry_get_value(const metrics_store_entry_t *entry)
   // LCOV_EXCL_STOP
 }
 
+/** Return store entry value for the specified bucket.
+ *
+ * Note: entry **must** be a histogram. */
+uint64_t
+metrics_store_hist_entry_get_value(const metrics_store_entry_t *entry,
+                                   const int64_t bucket)
+{
+  tor_assert(entry);
+
+  if (BUG(entry->type != METRICS_TYPE_HISTOGRAM)) {
+    return 0;
+  }
+
+  for (size_t i = 0; i <= entry->u.histogram.bucket_count; ++i) {
+    metrics_histogram_bucket_t hb = entry->u.histogram.buckets[i];
+    if (bucket == hb.bucket) {
+      if (hb.value > INT64_MAX) {
+        return INT64_MAX;
+      } else {
+        return hb.value;
+      }
+    }
+  }
+
+  tor_assertf_nonfatal(false, "attempted to get the value of non-existent "
+                       "bucket %" PRId64, bucket);
+  return 0;
+}
+
 /** Add a label into the given entry.*/
 void
 metrics_store_entry_add_label(metrics_store_entry_t *entry,
@@ -147,3 +259,40 @@ metrics_store_find_entry_with_label(const smartlist_t *entries,
 
   return NULL;
 }
+
+/** Return true iff the specified entry is a histogram. */
+bool
+metrics_store_entry_is_histogram(const metrics_store_entry_t *entry)
+{
+  if (entry->type == METRICS_TYPE_HISTOGRAM) {
+    return true;
+  }
+
+  return false;
+}
+
+/** Return the total number of observations for the specified histogram. */
+uint64_t
+metrics_store_hist_entry_get_count(const metrics_store_entry_t *entry)
+{
+  tor_assert(entry);
+
+  if (BUG(entry->type != METRICS_TYPE_HISTOGRAM)) {
+    return 0;
+  }
+
+  return entry->u.histogram.count;
+}
+
+/** Return the sum of all observations for the specified histogram. */
+int64_t
+metrics_store_hist_entry_get_sum(const metrics_store_entry_t *entry)
+{
+  tor_assert(entry);
+
+  if (BUG(entry->type != METRICS_TYPE_HISTOGRAM)) {
+    return 0;
+  }
+
+  return entry->u.histogram.sum;
+}
diff --git a/src/lib/metrics/metrics_store_entry.h b/src/lib/metrics/metrics_store_entry.h
index 0e09e099fe..53fa437406 100644
--- a/src/lib/metrics/metrics_store_entry.h
+++ b/src/lib/metrics/metrics_store_entry.h
@@ -38,6 +38,7 @@ struct metrics_store_entry_t {
   union {
     metrics_counter_t counter;
     metrics_gauge_t gauge;
+    metrics_histogram_t histogram;
   } u;
 };
 
@@ -48,7 +49,9 @@ typedef struct metrics_store_entry_t metrics_store_entry_t;
 /* Allocators. */
 metrics_store_entry_t *metrics_store_entry_new(const metrics_type_t type,
                                                const char *name,
-                                               const char *help);
+                                               const char *help,
+                                               size_t bucket_count,
+                                               const int64_t *buckets);
 
 void metrics_store_entry_free_(metrics_store_entry_t *entry);
 #define metrics_store_entry_free(entry) \
@@ -56,10 +59,16 @@ void metrics_store_entry_free_(metrics_store_entry_t *entry);
 
 /* Accessors. */
 int64_t metrics_store_entry_get_value(const metrics_store_entry_t *entry);
+uint64_t metrics_store_hist_entry_get_value(const metrics_store_entry_t *entry,
+                                           const int64_t bucket);
 bool metrics_store_entry_has_label(const metrics_store_entry_t *entry,
                                    const char *label);
 metrics_store_entry_t *metrics_store_find_entry_with_label(
         const smartlist_t *entries, const char *label);
+bool metrics_store_entry_is_histogram(const metrics_store_entry_t *entry);
+uint64_t metrics_store_hist_entry_get_count(
+        const metrics_store_entry_t *entry);
+int64_t metrics_store_hist_entry_get_sum(const metrics_store_entry_t *entry);
 
 /* Modifiers. */
 void metrics_store_entry_add_label(metrics_store_entry_t *entry,
@@ -67,5 +76,7 @@ void metrics_store_entry_add_label(metrics_store_entry_t *entry,
 void metrics_store_entry_reset(metrics_store_entry_t *entry);
 void metrics_store_entry_update(metrics_store_entry_t *entry,
                                 const int64_t value);
+void metrics_store_hist_entry_update(metrics_store_entry_t *entry,
+                                const int64_t value, const int64_t obs);
 
 #endif /* !defined(TOR_LIB_METRICS_METRICS_STORE_ENTRY_H) */
diff --git a/src/lib/metrics/prometheus.c b/src/lib/metrics/prometheus.c
index aac23ac92e..2f98f8ebb6 100644
--- a/src/lib/metrics/prometheus.c
+++ b/src/lib/metrics/prometheus.c
@@ -17,6 +17,8 @@
 
 #include "lib/metrics/prometheus.h"
 
+#include <string.h>
+
 /** Return a static buffer containing all the labels properly formatted
  * for the output as a string.
  *
@@ -33,13 +35,54 @@ format_labels(smartlist_t *labels)
   }
 
   line = smartlist_join_strings(labels, ",", 0, NULL);
-  tor_snprintf(buf, sizeof(buf), "{%s}", line);
+  tor_snprintf(buf, sizeof(buf), "%s", line);
 
  end:
   tor_free(line);
   return buf;
 }
 
+/** Write the string representation of the histogram entry to the specified
+ * buffer.
+ *
+ * Note: entry **must** be a histogram.
+ */
+static void
+format_histogram(const metrics_store_entry_t *entry, buf_t *data)
+{
+  tor_assert(entry->type == METRICS_TYPE_HISTOGRAM);
+
+  const char *labels = format_labels(entry->labels);
+
+  for (size_t i = 0; i < entry->u.histogram.bucket_count; ++i) {
+    metrics_histogram_bucket_t hb = entry->u.histogram.buckets[i];
+    if (strlen(labels) > 0) {
+      buf_add_printf(data, "%s_bucket{%s,le=\"%.2f\"} %" PRIi64 "\n",
+                     entry->name, labels, (double)hb.bucket, hb.value);
+    } else {
+      buf_add_printf(data, "%s_bucket{le=\"%.2f\"} %" PRIi64 "\n",
+                     entry->name, (double)hb.bucket, hb.value);
+    }
+  }
+
+  if (strlen(labels) > 0) {
+    buf_add_printf(data, "%s_bucket{%s,le=\"+Inf\"} %" PRIi64 "\n",
+                   entry->name, labels,
+                   metrics_store_hist_entry_get_count(entry));
+    buf_add_printf(data, "%s_sum{%s} %" PRIi64 "\n", entry->name, labels,
+                   metrics_store_hist_entry_get_sum(entry));
+    buf_add_printf(data, "%s_count{%s} %" PRIi64 "\n", entry->name, labels,
+                   metrics_store_hist_entry_get_count(entry));
+  } else {
+    buf_add_printf(data, "%s_bucket{le=\"+Inf\"} %" PRIi64 "\n", entry->name,
+                   metrics_store_hist_entry_get_count(entry));
+    buf_add_printf(data, "%s_sum %" PRIi64 "\n", entry->name,
+                   metrics_store_hist_entry_get_sum(entry));
+    buf_add_printf(data, "%s_count %" PRIi64 "\n", entry->name,
+                   metrics_store_hist_entry_get_count(entry));
+  }
+}
+
 /** Format the given entry in to the buffer data. */
 void
 prometheus_format_store_entry(const metrics_store_entry_t *entry, buf_t *data,
@@ -53,7 +96,26 @@ prometheus_format_store_entry(const metrics_store_entry_t *entry, buf_t *data,
     buf_add_printf(data, "# TYPE %s %s\n", entry->name,
                    metrics_type_to_str(entry->type));
   }
-  buf_add_printf(data, "%s%s %" PRIi64 "\n", entry->name,
-                 format_labels(entry->labels),
-                 metrics_store_entry_get_value(entry));
+
+  switch (entry->type) {
+  case METRICS_TYPE_COUNTER: FALLTHROUGH;
+  case METRICS_TYPE_GAUGE:
+  {
+    const char *labels = format_labels(entry->labels);
+    if (strlen(labels) > 0) {
+      buf_add_printf(data, "%s{%s} %" PRIi64 "\n", entry->name,
+                     labels,
+                     metrics_store_entry_get_value(entry));
+    } else {
+      buf_add_printf(data, "%s %" PRIi64 "\n", entry->name,
+                     metrics_store_entry_get_value(entry));
+    }
+    break;
+  }
+  case METRICS_TYPE_HISTOGRAM:
+    format_histogram(entry, data);
+    break;
+  default:
+    tor_assert_unreached();
+  }
 }