[XTF PATCH v1 08/15] common: add primitives for measurements

[dmukhin@xxxxxxxx]

From: Denis Mukhin <dmukhin@xxxxxxxx>

Add new module (hvm64 only) to enable measurements aggregation and
printing from the XTF.

Signed-off-by: Denis Mukhin <dmukhin@xxxxxxxx>
---
 build/files.mk           |   1 +
 common/statistics.c      | 364 +++++++++++++++++++++++++++++++++++++++
 include/xtf/statistics.h |  23 +++
 3 files changed, 388 insertions(+)
 create mode 100644 common/statistics.c
 create mode 100644 include/xtf/statistics.h

diff --git a/build/files.mk b/build/files.mk
index 11624a89a21c..8a7d6f8d588f 100644
--- a/build/files.mk
+++ b/build/files.mk
@@ -55,4 +55,5 @@ $(foreach env,$(32BIT_ENVIRONMENTS),$(eval obj-$(env) += 
$(obj-32)))
 
 # 64bit specific objects
 obj-64  += $(ROOT)/arch/x86/entry_64.o
+obj-64  += $(ROOT)/common/statistics.o
 $(foreach env,$(64BIT_ENVIRONMENTS),$(eval obj-$(env) += $(obj-64)))
diff --git a/common/statistics.c b/common/statistics.c
new file mode 100644
index 000000000000..00292d97c8cb
--- /dev/null
+++ b/common/statistics.c
@@ -0,0 +1,364 @@
+#include <xtf/lib.h>
+#include <xtf/statistics.h>
+#include <xtf/time.h>
+#include <xtf.h>
+
+#define HIST_WIDTH 50
+
+static const uint64_t bucket_limit[] = {
+    /* 0 .. 10, step 1. */
+    1ull, 2ull, 3ull, 4ull, 5ull,
+    6ull, 7ull, 8ull, 9ull, 10ull,
+
+    /* 10 .. 100, step 10. */
+    20ull, 30ull, 40ull, 50ull, 60ull,
+    70ull, 80ull, 90ull, 100ull,
+
+    /* 100 .. 500, step 10. */
+    110ull, 120ull, 130ull, 140ull, 150ull,
+    160ull, 170ull, 180ull, 190ull, 200ull,
+    210ull, 220ull, 230ull, 240ull, 250ull,
+    260ull, 270ull, 280ull, 290ull, 300ull,
+    310ull, 320ull, 330ull, 340ull, 350ull,
+    360ull, 370ull, 380ull, 390ull, 400ull,
+    410ull, 420ull, 430ull, 440ull, 450ull,
+    460ull, 470ull, 480ull, 490ull, 500ull,
+
+    /* 500 .. 1000, step 50. */
+    550ull, 600ull, 650ull, 700ull, 750ull,
+    800ull, 850ull, 900ull, 950ull, 1000ull,
+
+    /* 1000 .. 5000, step 100. */
+    1100ull, 1200ull, 1300ull, 1400ull, 1500ull,
+    1600ull, 1700ull, 1800ull, 1900ull, 2000ull,
+    2100ull, 2200ull, 2300ull, 2400ull, 2500ull,
+    2600ull, 2700ull, 2800ull, 2900ull, 3000ull,
+    3100ull, 3200ull, 3300ull, 3400ull, 3500ull,
+    3600ull, 3700ull, 3800ull, 3900ull, 4000ull,
+    4100ull, 4200ull, 4300ull, 4400ull, 4500ull,
+    4600ull, 4700ull, 4800ull, 4900ull, 5000ull,
+
+    /* 5000 .. 10000, step 100. */
+    5100ull, 5200ull, 5300ull, 5400ull, 5500ull,
+    5600ull, 5700ull, 5800ull, 5900ull, 6000ull,
+    6100ull, 6200ull, 6300ull, 6400ull, 6500ull,
+    6600ull, 6700ull, 6800ull, 6900ull, 7000ull,
+    7100ull, 7200ull, 7300ull, 7400ull, 7500ull,
+    7600ull, 7700ull, 7800ull, 7900ull, 8000ull,
+    8100ull, 8200ull, 8300ull, 8400ull, 8500ull,
+    8600ull, 8700ull, 8800ull, 8900ull, 9000ull,
+    9100ull, 9200ull, 9300ull, 9400ull, 9500ull,
+    9600ull, 9700ull, 9800ull, 9900ull, 10000ull,
+
+    /* 10000 .. 100000, step 1000. */
+    11000ull, 12000ull, 13000ull, 14000ull, 15000ull,
+    16000ull, 17000ull, 18000ull, 19000ull, 20000ull,
+    21000ull, 22000ull, 23000ull, 24000ull, 25000ull,
+    26000ull, 27000ull, 28000ull, 29000ull, 30000ull,
+    31000ull, 32000ull, 33000ull, 34000ull, 35000ull,
+    36000ull, 37000ull, 38000ull, 39000ull, 40000ull,
+    41000ull, 42000ull, 43000ull, 44000ull, 45000ull,
+    46000ull, 47000ull, 48000ull, 49000ull, 50000ull,
+    51000ull, 52000ull, 53000ull, 54000ull, 55000ull,
+    56000ull, 57000ull, 58000ull, 59000ull, 60000ull,
+    61000ull, 62000ull, 63000ull, 64000ull, 65000ull,
+    66000ull, 67000ull, 68000ull, 69000ull, 70000ull,
+    71000ull, 72000ull, 73000ull, 74000ull, 75000ull,
+    76000ull, 77000ull, 78000ull, 79000ull, 80000ull,
+    81000ull, 82000ull, 83000ull, 84000ull, 85000ull,
+    86000ull, 87000ull, 88000ull, 89000ull, 90000ull,
+    91000ull, 92000ull, 93000ull, 94000ull, 95000ull,
+    96000ull, 97000ull, 98000ull, 99000ull, 100000ull,
+
+    /* 100000 .. 1000000, step 50000. */
+    150000ull, 200000ull, 250000ull, 300000ull, 350000ull,
+    400000ull, 450000ull, 500000ull, 550000ull, 600000ull,
+    650000ull, 700000ull, 750000ull, 800000ull, 850000ull,
+    900000ull, 950000ull, 1000000ull,
+
+    /* Coarse tail buckets. */
+    10000000ull, 100000000ull, 1000000000ull, ~0ull,
+};
+
+_Static_assert(ARRAY_SIZE(bucket_limit) == NR_BUCKETS,
+               "NR_BUCKETS must match bucket_limit[]");
+
+/* First bucket whose upper limit is strictly greater than sample. */
+static unsigned int find_bucket_gt(uint64_t sample)
+{
+    unsigned int lo = 0, hi = NR_BUCKETS - 1;
+
+    while ( lo < hi )
+    {
+        unsigned int mid = lo + (hi - lo) / 2;
+
+        if ( sample < bucket_limit[mid] )
+            hi = mid;
+        else
+            lo = mid + 1;
+    }
+
+    return lo;
+}
+
+void xtf_add_sample(struct statistics *s, uint64_t sample)
+{
+    if ( sample < s->min )
+        s->min = sample;
+
+    if ( sample > s->max )
+        s->max = sample;
+
+    s->sum += sample;
+    s->count++;
+    s->bucket[find_bucket_gt(sample)]++;
+}
+
+/* Nearest-rank percentile, expressed as a rational number. */
+static unsigned int get_bucket_by_quantile(const struct statistics *s,
+                                           unsigned int numerator,
+                                           unsigned int denominator)
+{
+    uint64_t target, seen = 0;
+    unsigned int i;
+
+    if ( !s->count )
+        return 0;
+
+    target = (s->count / denominator) * numerator;
+    target += ((s->count % denominator) * numerator + denominator - 1) /
+              denominator;
+
+    for ( i = 0; i < NR_BUCKETS; ++i )
+    {
+        seen += s->bucket[i];
+
+        if ( seen >= target )
+            return i;
+    }
+
+    return NR_BUCKETS - 1;
+}
+
+static uint64_t get_bucket_value(unsigned int bucket)
+{
+    /* Last bucket is open-ended; report its lower bound. */
+    if ( bucket >= NR_BUCKETS - 1 )
+        bucket = NR_BUCKETS - 2;
+
+    return bucket_limit[bucket];
+}
+
+/*
+ * Choose units by magnitude while preserving nanosecond precision:
+ *   < 1 us: integer ns
+ *   < 1 ms: us with three fractional digits
+ *  >= 1 ms: ms with six fractional digits
+ *
+ * Select units independently for each histogram boundary.
+ */
+enum time_unit {
+    TIME_NS,
+    TIME_US,
+    TIME_MS,
+};
+
+static enum time_unit get_time_unit(uint64_t ns)
+{
+    if ( ns >= 1000000 )
+        return TIME_MS;
+
+    return ns >= 1000 ? TIME_US : TIME_NS;
+}
+
+/* Fixed-width time field for histogram and summary columns. */
+static void print_time_field(uint64_t ns)
+{
+    switch ( get_time_unit(ns) )
+    {
+    case TIME_NS:
+        printk("%15"PRIu64" ns", ns);
+        break;
+
+    case TIME_US:
+        printk("%11"PRIu64".%03"PRIu64" us",
+               ns / 1000, ns % 1000);
+        break;
+
+    case TIME_MS:
+        printk("%8"PRIu64".%06"PRIu64" ms",
+               ns / 1000000, ns % 1000000);
+        break;
+    }
+}
+
+static void print_metric_value(const char *op, uint64_t cycles)
+{
+    printk("%2s %12"PRIu64"  ", op, cycles);
+    print_time_field(cycles_to_ns(cycles));
+}
+
+void xtf_print_histogram(const struct statistics *s)
+{
+    uint64_t low = 0, hits = 0, peak = 0;
+    unsigned int i, entries = 0;
+
+    for ( i = 0; i < NR_BUCKETS; ++i )
+        if ( s->bucket[i] > peak )
+            peak = s->bucket[i];
+
+    for ( i = 0; i < NR_BUCKETS; ++i )
+    {
+        uint64_t count = s->bucket[i];
+
+        if ( count )
+        {
+            uint64_t pct;
+            unsigned int width, j;
+
+            hits += count;
+            entries++;
+
+            /* Per-bucket percentage rounded to 0.00001%. */
+            pct = (count * 10000000ull + s->count / 2) / s->count;
+
+            /* Round up and show at least one marker for a nonempty bucket. */
+            width = (count * HIST_WIDTH + peak - 1) / peak;
+
+            if ( i == NR_BUCKETS - 1 )
+                printk("  >=%12"PRIu64"%12s", low, "");
+            else
+                printk("%12"PRIu64" .. %12"PRIu64,
+                       low, bucket_limit[i] - 1);
+
+            printk(" | ");
+
+            if ( i == NR_BUCKETS - 1 )
+            {
+                printk("  >=");
+                print_time_field(cycles_to_ns(low));
+                printk("%18s", "");
+            }
+            else
+            {
+                print_time_field(cycles_to_ns(low));
+                printk(" .. ");
+                print_time_field(cycles_to_ns(bucket_limit[i] - 1));
+            }
+
+            printk(" | ");
+
+            for ( j = 0; j < HIST_WIDTH; ++j )
+                printk("%c", j < width ? '#' : ' ');
+
+            printk(" | %3"PRIu64".%05"PRIu64"%% | %10"PRIu64"\n",
+                   pct / 100000, pct % 100000, count);
+        }
+
+        if ( i != NR_BUCKETS - 1 )
+            low = bucket_limit[i];
+    }
+
+    ASSERT( hits == s->count );
+
+    printk("\nTotals:\n");
+    printk("    Hits: %"PRIu64"\n", s->count);
+    printk("    Entries: %u\n", entries);
+    printk("\n");
+}
+
+void xtf_finalize_statistics(struct statistics *s)
+{
+    s->p99 = get_bucket_value(get_bucket_by_quantile(s, 99, 100));
+}
+
+enum metric_id {
+    METRIC_MIN,
+    METRIC_AVG,
+    METRIC_P50,
+    METRIC_P99,
+    METRIC_P999,
+    METRIC_P9999,
+    METRIC_P99999,
+    METRIC_MAX,
+};
+
+static const struct {
+    const char *name;
+    unsigned int numerator, denominator;
+} metric[] = {
+    [METRIC_MIN]    = { "min",     0,     0 },
+    [METRIC_AVG]    = { "avg",     0,     0 },
+    [METRIC_P50]    = { "p50",    50,   100 },
+    [METRIC_P99]    = { "p99",    99,   100 },
+    [METRIC_P999]   = { "p99.9", 999,  1000 },
+    [METRIC_P9999]  = { "p99.99", 9999, 10000 },
+    [METRIC_P99999] = { "p99.999", 99999, 100000 },
+    [METRIC_MAX]    = { "max",     0,     0 },
+};
+
+static void print_metric_column(const struct statistics *s, unsigned int id)
+{
+    uint64_t cycles;
+    const char *op = "";
+
+    if ( !s->count )
+    {
+        printk("%2s %12s  %18s", "", "-", "-");
+        return;
+    }
+
+    if ( id == METRIC_MIN )
+        cycles = s->min;
+    else if ( id == METRIC_AVG )
+        cycles = s->sum / s->count;
+    else if ( id == METRIC_MAX )
+        cycles = s->max;
+    else
+    {
+        unsigned int bucket = get_bucket_by_quantile(
+            s, metric[id].numerator, metric[id].denominator);
+
+        op = bucket == NR_BUCKETS - 1 ? ">=" : "<";
+        cycles = get_bucket_value(bucket);
+    }
+
+    print_metric_value(op, cycles);
+}
+
+void xtf_print_metrics(const struct statistics *s, const struct statistics *t)
+{
+    unsigned int i;
+
+    if ( t )
+    {
+        printk("A: %s (%"PRIu64" samples)\n", s->name, s->count);
+        printk("B: %s (%"PRIu64" samples)\n", t->name, t->count);
+    }
+    else
+        printk("%s (%"PRIu64" samples)\n", s->name, s->count);
+
+    if ( t )
+    {
+        printk("%-8s %2s %12s  %18s", "metric", "", "cycles A", "time A");
+        printk(  " | %2s %12s  %18s",           "", "cycles B", "time B");
+    }
+    else
+        printk("%-8s %2s %12s  %18s", "metric", "", "cycles",   "time");
+
+    printk("\n");
+
+    for ( i = 0; i < ARRAY_SIZE(metric); ++i )
+    {
+        printk("%-8s ", metric[i].name);
+        print_metric_column(s, i);
+
+        if ( t )
+        {
+            printk(" | ");
+            print_metric_column(t, i);
+        }
+
+        printk("\n");
+    }
+}
diff --git a/include/xtf/statistics.h b/include/xtf/statistics.h
new file mode 100644
index 000000000000..e074435ed5ad
--- /dev/null
+++ b/include/xtf/statistics.h
@@ -0,0 +1,23 @@
+#ifndef __XTF_STATISTICS_H_
+#define __XTF_STATISTICS_H_
+
+#include <stdint.h>
+
+#define NR_BUCKETS  271u
+
+struct statistics {
+    uint64_t bucket[NR_BUCKETS];
+    uint64_t min;
+    uint64_t max;
+    uint64_t p99;
+    uint64_t sum;
+    uint64_t count;
+    const char *name;
+};
+
+void xtf_add_sample(struct statistics *s, uint64_t sample);
+void xtf_finalize_statistics(struct statistics *s);
+void xtf_print_histogram(const struct statistics *s);
+void xtf_print_metrics(const struct statistics *s, const struct statistics *t);
+
+#endif /* __XTF_STATISTICS_H_ */
-- 
2.55.0