[Qemu-devel] [PATCH 1/2] Rolling statistics utilities

["Dr. David Alan Gilbert (git)" <dgilbert@redhat.com>]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

There are various places where it's useful to hold a series
of values that change over time and get summaries about them.

This provides:

   - a count of the number of items
   - min/max
   - mean
   - a weighted mean (where you can set the weight to determine
                      whether it changes quickly or slowly)
   - the last 'n' values

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 include/qemu/rolling-stats.h | 101 +++++++++++
 include/qemu/typedefs.h      |   1 +
 util/Makefile.objs           |   1 +
 util/rolling-stats.c         | 393 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 496 insertions(+)
 create mode 100644 include/qemu/rolling-stats.h
 create mode 100644 util/rolling-stats.c

diff --git a/include/qemu/rolling-stats.h b/include/qemu/rolling-stats.h
new file mode 100644
index 0000000..d64ce78
--- /dev/null
+++ b/include/qemu/rolling-stats.h
@@ -0,0 +1,101 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <dgilbert@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#ifndef __QEMU_ROLLING_STATS_H
+#define __QEMU_ROLLING_STATS_H 1
+
+#include "qemu/typedefs.h"
+/**
+ * Allocate and initialise an 'RStats' structure.
+ *
+ * @len:    Number of values to hold
+ * @weight: Weight for the weighted average, between 0..1
+ *          smaller values cause the average to update more quickly.
+ *
+ * Returns: A pointer to the RStats structure.
+ */
+RStats *rstats_init(size_t len, double weight);
+
+/**
+ * Deallocate the RStats structure
+ */
+void rstats_destroy(RStats *r);
+
+/**
+ * Add a new value into the RStats record.
+ *
+ * @r: The RStats to update
+ * @value: The new value to be recorded
+ * @tag: A tag to be associated with the value, not used by the calculations
+ *       (e.g. a time or iteration count)
+ */
+void rstats_add_value(RStats *r, double value, uint64_t tag);
+
+/**
+ * Reset the RStats structure
+ *
+ */
+void rstats_reset(RStats *r);
+
+/**
+ * Return a string representing the RStats data, intended for human consumption
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g. (Without the line break!)
+ *   Min/Max: -3.57, 126.3  Mean: 7.83 (weighted: 8.56)  Values: 4.3@458,
+ *   5.8@783, 1.2@950, 7.9@951, 10.3@952
+ */
+char *rstats_as_pretty_string(RStats *r);
+
+/**
+ * Return a string representing the RStats data, intended for JSON parsing
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
+ *      "count": 5678,
+ *      "values": [ 4.3, 5.8, 1.2, 7.9, 10.3 ],
+ *      "tags": [ 458, 783, 950, 951, 952 ] }
+ */
+char *rstats_as_json_string(RStats *r);
+
+/**
+ * Return the mean
+ * @r: The RStats to examine
+ *
+ * Returns: The mean value
+ */
+double rstats_get_mean(const RStats *r);
+
+/**
+ * Return the weighted mean
+ * @r: The RStats to examine
+ *
+ * Returns: The weighted mean
+ */
+double rstats_get_weighted_mean(const RStats *r);
+
+/**
+ * Return the minimum and maximum values
+ * @r: The RStats to examine
+ * @min: Pointer to return the minimum in
+ * @max: Pointer to return the maximum in
+ *
+ */
+void rstats_get_min_max(const RStats *r, double *min, double *max);
+
+#endif
diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
index cde3314..3488dfd 100644
--- a/include/qemu/typedefs.h
+++ b/include/qemu/typedefs.h
@@ -69,6 +69,7 @@ typedef struct QEMUSizedBuffer QEMUSizedBuffer;
 typedef struct QEMUTimerListGroup QEMUTimerListGroup;
 typedef struct QEMUTimer QEMUTimer;
 typedef struct Range Range;
+typedef struct RStats RStats;
 typedef struct SerialState SerialState;
 typedef struct SHPCDevice SHPCDevice;
 typedef struct SMBusDevice SMBusDevice;
diff --git a/util/Makefile.objs b/util/Makefile.objs
index ceaba30..b45af66 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -17,4 +17,5 @@ util-obj-y += throttle.o
 util-obj-y += getauxval.o
 util-obj-y += readline.o
 util-obj-y += rfifolock.o
+util-obj-y += rolling-stats.o
 util-obj-y += rcu.o
diff --git a/util/rolling-stats.c b/util/rolling-stats.c
new file mode 100644
index 0000000..f2f1984
--- /dev/null
+++ b/util/rolling-stats.c
@@ -0,0 +1,393 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <dgilbert@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#include <float.h>
+#include <glib.h>
+#include <stdint.h>
+
+#include "qemu-common.h"
+#include "qemu/rolling-stats.h"
+#include "qemu/thread.h"
+#include "qemu/typedefs.h"
+
+struct RStats {
+    size_t allocated;  /* Amount of space for values */
+    size_t captured;   /* Number of values currently stored */
+    size_t head;       /* Pointer to the next value to be written */
+    size_t count;      /* Count of values which the stats are calculated over */
+    double weight;     /* for weighted_mean calculation */
+    double *values;
+    uint64_t *tags;    /* Tags associated with corresponding values */
+
+    double min, max, mean, weighted_mean;
+
+    /* Allow results to be added and printed from different threads */
+    QemuMutex mutex;
+};
+
+/**
+ * Add a new value into the RStats record.
+ *
+ * @r: The RStats to update
+ * @value: The new value to be recorded
+ * @tag: A tag to be associated with the value, not used by the calculations
+ *       (e.g. a time or iteration count)
+ */
+void rstats_add_value(RStats *r, double value, uint64_t tag)
+{
+    double old_value;
+
+    qemu_mutex_lock(&r->mutex);
+
+    old_value  = r->values[r->head];
+
+    r->tags[r->head] = tag;
+    r->values[r->head++] = value;
+    if (r->head >= r->allocated) {
+        r->head = 0;
+    }
+    if (r->captured < r->allocated) {
+        double tmp;
+
+        tmp = r->mean * r->captured;
+
+        r->captured++;
+
+        r->mean = (tmp + value) / r->captured;
+    } else {
+        r->mean -= old_value / r->allocated;
+        r->mean += value / r->allocated;
+    }
+
+    if (!r->count || value < r->min) {
+        r->min = value;
+    }
+
+    if (!r->count || value > r->max) {
+        r->max = value;
+    }
+
+
+    if (r->count) {
+        r->weighted_mean = r->weighted_mean * r->weight +
+                                      value * (1 - r->weight);
+    } else {
+        r->weighted_mean = value;
+    }
+
+    r->count++;
+
+    qemu_mutex_unlock(&r->mutex);
+}
+
+/**
+ * Reset the RStats structure
+ *
+ */
+void rstats_reset(RStats *r)
+{
+    qemu_mutex_lock(&r->mutex);
+
+    r->captured = 0;
+    r->count = 0;
+    r->head = 0;
+    r->max = 0.0;
+    r->mean = 0.0;
+    r->min = 0.0;
+    r->weighted_mean = 0.0;
+
+    qemu_mutex_unlock(&r->mutex);
+}
+
+/**
+ * Return the mean
+ * @r: The RStats to examine
+ *
+ * Returns: The mean value
+ */
+double rstats_get_mean(const RStats *r)
+{
+    return r->mean;
+}
+
+/**
+ * Return the weighted mean
+ * @r: The RStats to examine
+ *
+ * Returns: The weighted mean
+ */
+double rstats_get_weighted_mean(const RStats *r)
+{
+    return r->weighted_mean;
+}
+
+/**
+ * Return the minimum and maximum values
+ * @r: The RStats to examine
+ * @min: Pointer to return the minimum in
+ * @max: Pointer to return the maximum in
+ *
+ */
+void rstats_get_min_max(const RStats *r, double *min, double *max)
+{
+    *min = r->min;
+    *max = r->max;
+}
+
+
+/*
+ * Helper for the formatters below, updates pointers, reallocates if
+ * needed.
+ *
+ * @printf_out: The result value of an snprintf saying how many chars it
+ *              wanted to print.
+ * @result: The output buffer, maybe reallocated
+ * @current: The pointer to the current text just output, will be updated
+ *           to where the next text should be output
+ * @space: The size of the output buffer, maybe updated
+ * @space_left: The number of characters remaining in the output buffer,
+ *              will be updated
+ */
+static bool maybe_realloc(int printf_out, char **result, char **current,
+                          size_t *space, size_t *space_left)
+{
+    if (printf_out >= *space_left) {
+        char *new_result;
+        *space = *space + 512;
+        new_result = g_try_realloc(*result, *space);
+
+        if (!new_result) {
+            *result = NULL;
+            return false;
+        }
+        *space_left = (*space - 1) - (*current - *result);
+        *current = new_result + (*current - *result);
+        *result = new_result;
+        return true;
+    } else {
+        *current += printf_out;
+        *space_left -= printf_out;
+        return false;
+    }
+}
+/**
+ * Return a string representing the RStats data, intended for human consumption
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *   Min/Max: -3.57, 126.3  Mean: 7.83 (weighted: 8.56)  Values: 4.3@458,
+ *            5.8@783, 1.2@950, 7.9@951, 10.3@952
+ */
+char *rstats_as_pretty_string(RStats *r)
+{
+    char *result, *current;
+    int tmp;
+    size_t index;
+
+    /* lets get a sane initial size, we'll reallocate as we print the values */
+    size_t space, space_left;
+
+    qemu_mutex_lock(&r->mutex);
+    space  = 60 /* for text */ +
+             /* 4 double values (min/max/mean/weighted) + the stored
+              * values, plus a normal guess for the size of them printed
+              * with %g and some padding.  I'm not sure of the worst case.
+              */
+             (4 + r->allocated) * 13 +
+             /* and the count and tags as 64bit ints and some padding */
+             (1 + r->allocated) * 23;
+    space_left = space - 1;
+
+    result = g_try_malloc(space);
+
+    if (!result) {
+        qemu_mutex_unlock(&r->mutex);
+        return NULL;
+    }
+
+    current = result;
+    tmp = snprintf(current, space_left, "Min/Max: %.8g, %.8g Mean: %.8g "
+                                        "(Weighted: %.8g) Count: %" PRIu64
+                                        " Values: ",
+                   r->min, r->max, r->mean, r->weighted_mean, r->count);
+    if (tmp >= space_left) {
+        /* It's very unlikely that the values aren't large enough even for
+         * the summary. */
+        g_free(result);
+        result = NULL;
+        goto out;
+    }
+    current += tmp;
+    space_left -= tmp;
+
+    for (index = 0; index < r->captured; index++) {
+        do {
+            size_t actual_index;
+
+            /*
+             * The array is a rolling buffer, adjust so index=0 always points
+             * to the oldest.
+             */
+            if (r->captured >= r->allocated) {
+                actual_index = (index + r->head) % r->allocated;
+            } else {
+                actual_index = index;
+            }
+            tmp = snprintf(current, space_left,
+                           "%.8g@%" PRIu64 "%s",
+                           r->values[actual_index], r->tags[actual_index],
+                           (index == (r->captured - 1)) ? "" : ", ");
+
+        } while (maybe_realloc(tmp, &result, &current, &space, &space_left));
+
+        if (result == NULL) {
+            break;
+        }
+    }
+
+out:
+    qemu_mutex_unlock(&r->mutex);
+    return result;
+}
+
+/**
+ * Return a string representing the RStats data, intended for JSON parsing
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
+ *      "count": 5678,
+ *      "values": [ { "value": 4.3, "tag": 458 },
+ *                  { "value": 5.8, "tag": 783 },
+ *                  { "value": 1.2, "tag": 950 },
+ *                  { "value": 7.9, "tag": 951 },
+ *                  { "value": 10.3, "tag": 952 } ] }
+ *
+ */
+char *rstats_as_json_string(RStats *r)
+{
+    char *result, *current;
+    int tmp;
+    size_t index;
+
+    /* lets get a sane initial size, we'll reallocate as we print the values */
+    size_t space, space_left;
+
+    qemu_mutex_lock(&r->mutex);
+    space  = 120 /* for text */ +
+             /* 4 double values (min/max/mean/weighted) + the stored
+              * values, plus a normal guess for the size of them printed
+              * with %g and some padding.  I'm not sure of the worst case.
+              */
+             (4 + r->allocated) * 13 +
+             /* and the count and tags as 64bit ints and some padding */
+             (1 + r->allocated) * 23;
+    space_left = space - 1;
+
+    result = g_try_malloc(space);
+
+    if (!result) {
+        qemu_mutex_unlock(&r->mutex);
+        return NULL;
+    }
+
+    current = result;
+    tmp = snprintf(current, space_left, "{ \"min\": %.8g, \"max\": %.8g,"
+                                        " \"mean\": %.8g,"
+                                        " \"weighted_mean\": %.8g,"
+                                        " \"count\": %" PRIu64 ","
+                                        " \"values\": [ %s",
+                   r->min, r->max, r->mean, r->weighted_mean, r->count,
+                   !r->captured ? "] }" : "" );
+    if (tmp >= space_left) {
+        /* It's very unlikely that the values aren't large enough even for
+         * the header. */
+        g_free(result);
+        result = NULL;
+        goto out;
+    }
+    current += tmp;
+    space_left -= tmp;
+
+    for (index = 0; index < r->captured; index++) {
+        do {
+            size_t actual_index;
+
+            /*
+             * The array is a rolling buffer, adjust so index=0 always points
+             * to the oldest.
+             */
+            if (r->captured >= r->allocated) {
+                actual_index = (index + r->head) % r->allocated;
+            } else {
+                actual_index = index;
+            }
+            tmp = snprintf(current, space_left,
+                           "{ \"value\": %.8g, \"tag\": %" PRIu64 "%s",
+                           r->values[actual_index], r->tags[actual_index],
+                           (index == (r->captured - 1)) ? " } ] }" : " }, ");
+
+        } while (maybe_realloc(tmp, &result, &current, &space, &space_left));
+
+        if (result == NULL) {
+            break;
+        }
+    }
+
+out:
+    qemu_mutex_unlock(&r->mutex);
+    return result;
+}
+
+/**
+ * Allocate and initialise an 'RStats' structure.
+ *
+ * @len:    Number of values to hold
+ * @weight: Weight for the weighted average, between 0..1
+ *          smaller values cause the average to update more quickly.
+ *
+ * Returns: A pointer to the RStats structure.
+ */
+RStats *rstats_init(size_t len, double weight)
+{
+    RStats *r = g_new0(RStats, 1);
+
+    r->values = g_new0(double, len);
+    r->tags = g_new0(uint64_t, len);
+    r->allocated = len;
+    r->weight = weight;
+
+    rstats_reset(r);
+
+    qemu_mutex_init(&r->mutex);
+    return r;
+}
+
+/**
+ * Deallocate the RStats structure
+ */
+void rstats_destroy(RStats *r)
+{
+    qemu_mutex_lock(&r->mutex);
+    g_free(r->values);
+    g_free(r->tags);
+    qemu_mutex_unlock(&r->mutex);
+    qemu_mutex_destroy(&r->mutex);
+    g_free(r);
+}
+
+
-- 
2.1.0