[Qemu-devel] [RFC v2 0/4] Rolling statistics utilities

[Qemu-devel] [RFC v2 0/4] Rolling statistics utilities

[Dr. David Alan Gilbert (git)]

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

Hi,
  This is an attempt at a generic rolling statistics utility to
allow data (e.g. bandwidth usage, times etc) to be collected
easily.  They hold some basic values (min/max/mean/weighted mean)
and the last 'n' raw values.    I'd like to use this
maybe with fault-tolerance code and want to read the means
within qemu but also want to provide the values to higher levels
of the stack and to watch what is going on.

  This version is lightly tested, and I'm still more interested
in if it's the right shape/idea rather than a detailed review.

  I've included an example use in watching the 'expected downtime'
in migration; rather than the current single value we get:

HMP:
expected downtime stats: Min/Max: 222, 1634 Mean: 983.8 (Weighted:
1005.1253) Count: 141 Values: 1248@39356292, 981@39356395, 774@39356497,
876@39356599, 1040@39356702

QMP:
        "expected-downtime-stats": {
            "min": 222,
            "count": 378,
            "mean": 1100.2,
            "max": 1942,
            "weighted-mean": 1115.710848,
            "values": [
                {
                    "tag": 39380740,
                    "value": 1118
                },
                {
                    "tag": 39380842,
                    "value": 953
                },
                {
                    "tag": 39380945,
                    "value": 1017
                },
                {
                    "tag": 39381048,
                    "value": 1336
                },
                {
                    "tag": 39381150,
                    "value": 1077
                }
            ]
        }


Dave

RFC v2
  Wired up a qapi type so that the output is done via qapi; it
  still seems best to have a separate type with the data and
  the locking etc.
  Although that has lost my test harness that was built on my
  manual formatters.

Dr. David Alan Gilbert (4):
  RollingStats qapi type
  Rolling statistics utilities
  hmp: Add a helper function for printing out a Rolling Statistics set
  Example use of rolling statistics in migration

 hmp.c                         |  24 +++++
 include/migration/migration.h |   1 +
 include/qemu/rolling-stats.h  |  87 ++++++++++++++++
 include/qemu/typedefs.h       |   1 +
 migration/migration.c         |  15 +++
 qapi-schema.json              |  36 ++++++-
 util/Makefile.objs            |   1 +
 util/rolling-stats.c          | 236 ++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 400 insertions(+), 1 deletion(-)
 create mode 100644 include/qemu/rolling-stats.h
 create mode 100644 util/rolling-stats.c

-- 
2.1.0

[Qemu-devel] [RFC v2 1/4] RollingStats qapi type

[Dr. David Alan Gilbert (git)]

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

This adds a QAPI type that holds the results of statistics collected
by RStats.

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 qapi-schema.json | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/qapi-schema.json b/qapi-schema.json
index e16f8eb..9f5cdce 100644
--- a/qapi-schema.json
+++ b/qapi-schema.json
@@ -353,6 +353,36 @@
 { 'command': 'query-events', 'returns': ['EventInfo'] }
 
 ##
+# @RollingStatsValue:
+#
+# A value/tag tuple used in 'RollingStats'
+#
+# @value: An arbitrary measurement value
+#
+# @tag: An arbitrary integer tag value
+#
+##
+{ 'type': 'RollingStatsValue', 'data': {'value': 'number', 'tag': 'uint64'} }
+
+##
+# @RollingStats:
+#
+# A set of statistics that are measured repeatedly.
+#
+# @count: The number of measurements that have contributed to the statistics
+# @min: The minimum value over the measurement period
+# @max: The maximum value over the measurement period
+# @mean: A rolling mean
+# @weighted-mean: A weighted mean (the weight set at startup)
+# @values: A list of the most recent values stored.  Note that the
+#          stastics above are calculated over the whole set.
+##
+{ 'type': 'RollingStats', 'data': {'count': 'int',
+                                   'min': 'number', 'max': 'number',
+                                   'mean': 'number', 'weighted-mean': 'number',
+                                   'values': ['RollingStatsValue'] } }
+
+##
 # @MigrationStats
 #
 # Detailed migration status.
-- 
2.1.0

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

[Dr. David Alan Gilbert (git)]

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 |  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 <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);
+
+/**
+ * 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 <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;
+}
+
+/**
+ * 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

[Qemu-devel] [RFC v2 3/4] hmp: Add a helper function for printing out a Rolling Statistics set

[Dr. David Alan Gilbert (git)]

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

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 hmp.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/hmp.c b/hmp.c
index 735097c..20241d8 100644
--- a/hmp.c
+++ b/hmp.c
@@ -138,6 +138,27 @@ void hmp_info_mice(Monitor *mon, const QDict *qdict)
     qapi_free_MouseInfoList(mice_list);
 }
 
+__attribute__ (( unused )) /* Until later in patch series */
+static void monitor_printf_RollingStats(Monitor *mon, const char *title,
+                                        RollingStats *r)
+{
+    RollingStatsValueList *list_entry = r->values;
+
+    monitor_printf(mon, "%s: Min/Max: %.8g, %.8g Mean: %.8g "
+                        "(Weighted: %.8g) Count: %" PRIu64
+                        " Values: ",
+                   title, r->min, r->max, r->mean, r->weighted_mean, r->count);
+
+    while (list_entry) {
+        monitor_printf(mon, "%.8g@%" PRIu64 "%s",
+                       list_entry->value->value,
+                       list_entry->value->tag,
+                       list_entry->next ? ", " : "");
+        list_entry = list_entry->next;
+    }
+    monitor_printf(mon, "\n");
+}
+
 void hmp_info_migrate(Monitor *mon, const QDict *qdict)
 {
     MigrationInfo *info;
-- 
2.1.0

[Qemu-devel] [RFC v2 4/4] Example use of rolling statistics in migration

[Dr. David Alan Gilbert (git)]

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

This is an example use of the rolling statistics to
watch the 'expected downtime' in a bit more detail than
the current summary figure.

Example outputs from a simple run:

HMP:
expected downtime stats: Min/Max: 222, 1634 Mean: 983.8 (Weighted:
1005.1253) Count: 141 Values: 1248@39356292, 981@39356395, 774@39356497,
876@39356599, 1040@39356702

QMP:
        "expected-downtime-stats": {
            "min": 222,
            "count": 378,
            "mean": 1100.2,
            "max": 1942,
            "weighted-mean": 1115.710848,
            "values": [
                {
                    "tag": 39380740,
                    "value": 1118
                },
                {
                    "tag": 39380842,
                    "value": 953
                },
                {
                    "tag": 39380945,
                    "value": 1017
                },
                {
                    "tag": 39381048,
                    "value": 1336
                },
                {
                    "tag": 39381150,
                    "value": 1077
                }
            ]
        }

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 hmp.c                         |  5 ++++-
 include/migration/migration.h |  1 +
 migration/migration.c         | 15 +++++++++++++++
 qapi-schema.json              |  6 +++++-
 4 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/hmp.c b/hmp.c
index 20241d8..6bd19b2 100644
--- a/hmp.c
+++ b/hmp.c
@@ -138,7 +138,6 @@ void hmp_info_mice(Monitor *mon, const QDict *qdict)
     qapi_free_MouseInfoList(mice_list);
 }
 
-__attribute__ (( unused )) /* Until later in patch series */
 static void monitor_printf_RollingStats(Monitor *mon, const char *title,
                                         RollingStats *r)
 {
@@ -186,6 +185,10 @@ void hmp_info_migrate(Monitor *mon, const QDict *qdict)
             monitor_printf(mon, "expected downtime: %" PRIu64 " milliseconds\n",
                            info->expected_downtime);
         }
+        if (info->has_expected_downtime_stats) {
+            monitor_printf_RollingStats(mon, "expected downtime stats",
+                           info->expected_downtime_stats);
+        }
         if (info->has_downtime) {
             monitor_printf(mon, "downtime: %" PRIu64 " milliseconds\n",
                            info->downtime);
diff --git a/include/migration/migration.h b/include/migration/migration.h
index 703b7d7..b37ec0c 100644
--- a/include/migration/migration.h
+++ b/include/migration/migration.h
@@ -63,6 +63,7 @@ struct MigrationState
     int64_t xbzrle_cache_size;
     int64_t setup_time;
     int64_t dirty_sync_count;
+    RStats *expected_downtime_stats;
 };
 
 void process_incoming_migration(QEMUFile *f);
diff --git a/migration/migration.c b/migration/migration.c
index b3adbc6..4041823 100644
--- a/migration/migration.c
+++ b/migration/migration.c
@@ -24,6 +24,7 @@
 #include "migration/block.h"
 #include "qemu/thread.h"
 #include "qmp-commands.h"
+#include "qemu/rolling-stats.h"
 #include "trace.h"
 
 enum {
@@ -201,6 +202,9 @@ MigrationInfo *qmp_query_migrate(Error **errp)
             - s->total_time;
         info->has_expected_downtime = true;
         info->expected_downtime = s->expected_downtime;
+        info->expected_downtime_stats =
+            rstats_as_RollingStats(s->expected_downtime_stats);
+        info->has_expected_downtime_stats = true;
         info->has_setup_time = true;
         info->setup_time = s->setup_time;
 
@@ -238,6 +242,9 @@ MigrationInfo *qmp_query_migrate(Error **errp)
         info->downtime = s->downtime;
         info->has_setup_time = true;
         info->setup_time = s->setup_time;
+        info->expected_downtime_stats =
+            rstats_as_RollingStats(s->expected_downtime_stats);
+        info->has_expected_downtime_stats = true;
 
         info->has_ram = true;
         info->ram = g_malloc0(sizeof(*info->ram));
@@ -389,12 +396,18 @@ static MigrationState *migrate_init(const MigrationParams *params)
     memcpy(enabled_capabilities, s->enabled_capabilities,
            sizeof(enabled_capabilities));
 
+    /* Resets the current state */
     memset(s, 0, sizeof(*s));
     s->params = *params;
     memcpy(s->enabled_capabilities, enabled_capabilities,
            sizeof(enabled_capabilities));
     s->xbzrle_cache_size = xbzrle_cache_size;
 
+    if (!s->expected_downtime_stats) {
+        s->expected_downtime_stats = rstats_init(5, 0.2);
+    } else {
+        rstats_reset(s->expected_downtime_stats);
+    }
     s->bandwidth_limit = bandwidth_limit;
     s->state = MIG_STATE_SETUP;
     trace_migrate_set_state(MIG_STATE_SETUP);
@@ -658,6 +671,8 @@ static void *migration_thread(void *opaque)
                10000 is a small enough number for our purposes */
             if (s->dirty_bytes_rate && transferred_bytes > 10000) {
                 s->expected_downtime = s->dirty_bytes_rate / bandwidth;
+                rstats_add_value(s->expected_downtime_stats,
+                                 s->expected_downtime, current_time);
             }
 
             qemu_file_reset_rate_limit(s->file);
diff --git a/qapi-schema.json b/qapi-schema.json
index 9f5cdce..c43f0e7 100644
--- a/qapi-schema.json
+++ b/qapi-schema.json
@@ -480,6 +480,9 @@
 #        may be expensive, but do not actually occur during the iterative
 #        migration rounds themselves. (since 1.6)
 #
+# @expected-downtime-stats: #optional more detailed statistics from the
+#        downtime estimation.
+#
 # Since: 0.14.0
 ##
 { 'type': 'MigrationInfo',
@@ -489,7 +492,8 @@
            '*total-time': 'int',
            '*expected-downtime': 'int',
            '*downtime': 'int',
-           '*setup-time': 'int'} }
+           '*setup-time': 'int',
+           '*expected-downtime-stats': 'RollingStats' } }
 
 ##
 # @query-migrate
-- 
2.1.0