From: "Dr. David Alan Gilbert" <dgilb...@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 <dgilb...@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 <dgilb...@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 <dgilb...@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, ¤t, &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, ¤t, &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
