[Qemu-block] [RFC v2 2/4] Rolling statistics utilities

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <address@hidden>

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 <address@hidden>
---
 include/qemu/rolling-stats.h |  87 ++++++++++++++++
 include/qemu/typedefs.h      |   1 +
 util/Makefile.objs           |   1 +
 util/rolling-stats.c         | 236 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 325 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..59b9f79
--- /dev/null
+++ b/include/qemu/rolling-stats.h
@@ -0,0 +1,87 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <address@hidden>
+ *
+ * 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);
+
+/**
+ * Returns a freshly allocated 'RollingStats' qapi object containg the data 
from
+ * the RStats.  The data is copied out under lock, but then the caller can
+ * access the RollingStats without needing a lock.  The caller should free
+ * the RollingStats.
+ *
+ * @r: The RStats to copy
+ *
+ * Returns: a RollingStats that should be freed by the caller
+ */
+RollingStats *rstats_as_RollingStats(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..511b2c8
--- /dev/null
+++ b/util/rolling-stats.c
@@ -0,0 +1,236 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <address@hidden>
+ *
+ * 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;
+}
+
+/**
+ * Returns a freshly allocated 'RollingStats' qapi object containg the data 
from
+ * the RStats.  The data is copied out under lock, but then the caller can
+ * access the RollingStats without needing a lock.  The caller should free
+ * the RollingStats.
+ *
+ * @r: The RStats to copy
+ *
+ * Returns: a RollingStats that should be freed by the caller
+ */
+RollingStats *rstats_as_RollingStats(RStats *r)
+{
+    RollingStats *result = g_new0(RollingStats, 1);
+    RollingStatsValueList **list_entry = &(result->values);
+    size_t index;
+
+    qemu_mutex_lock(&r->mutex);
+
+    /* The values list is a linked list that needs individual allocations */
+    for (index = 0; index < r->captured; index++) {
+        size_t source_index;
+
+        *list_entry = g_new0(RollingStatsValueList, 1);
+        (*list_entry)->value = g_new0(RollingStatsValue, 1);
+
+        /*
+         * The array is a rolling buffer, adjust so index=0 always points
+         * to the oldest.
+         */
+        if (r->captured >= r->allocated) {
+            source_index = (index + r->head) % r->allocated;
+        } else {
+            source_index = index;
+        }
+
+       (*list_entry)->value->value = r->values[source_index];
+       (*list_entry)->value->tag = r->tags[source_index];
+
+        list_entry = &(*list_entry)->next;
+    }
+
+    result->count = r->count;
+    result->min = r->min;
+    result->max = r->max;
+    result->mean = r->mean;
+    result->weighted_mean = r->weighted_mean;
+
+    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