[Qemu-devel] [PATCH 2/2] util: Add an utility infrastructure used to compute an average on a time slice

["Benoît Canet" <benoit.canet@nodalink.com>]

The algorithm used was defined on the list while discussing the new IO accounting
overhaul.
See http://lists.nongnu.org/archive/html/qemu-devel/2014-08/msg04954.html

Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
---
 include/qemu/timed-average.h |  45 +++++++++++++++++++
 tests/Makefile               |   2 +
 tests/test-timed-average.c   |  53 ++++++++++++++++++++++
 util/Makefile.objs           |   1 +
 util/timed-average.c         | 102 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 203 insertions(+)
 create mode 100644 include/qemu/timed-average.h
 create mode 100644 tests/test-timed-average.c
 create mode 100644 util/timed-average.c

diff --git a/include/qemu/timed-average.h b/include/qemu/timed-average.h
new file mode 100644
index 0000000..abe583a
--- /dev/null
+++ b/include/qemu/timed-average.h
@@ -0,0 +1,45 @@
+/*
+ * QEMU timed average computation
+ *
+ * Copyright (C) Nodalink, EURL. 2014
+ *
+ * Author:
+ *   Benoît Canet <benoit.canet@nodalink.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 or
+ * (at your option) version 3 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef TIMED_AVERAGE_H
+#define TIMED_AVERAGE_H
+
+#include <stdint.h>
+
+#include "qemu/timer.h"
+
+typedef struct TimedAverage {
+    uint64_t      sum;           /* sum of the discrete values */
+    uint64_t      count;         /* number of values */
+    uint64_t      period;        /* period in seconds */
+    int64_t       expiration;    /* the end of the current period slice in ns */
+    QEMUClockType clock_type;    /* the clock used */
+} TimedAverage;
+
+void timed_average_init(TimedAverage *ta, QEMUClockType clock_type,
+                        uint64_t period);
+
+void timed_average_account(TimedAverage *ta, uint64_t value);
+
+uint64_t timed_average_get(TimedAverage *ta);
+
+#endif
diff --git a/tests/Makefile b/tests/Makefile
index 469c0a5..9b51b32 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -64,6 +64,7 @@ gcov-files-check-qom-interface-y = qom/object.c
 check-unit-$(CONFIG_POSIX) += tests/test-vmstate$(EXESUF)
 check-unit-y += tests/test-qemu-opts$(EXESUF)
 gcov-files-test-qemu-opts-y = qom/test-qemu-opts.c
+check-unit-y += tests/test-timed-average$(EXESUF)
 
 check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
 
@@ -259,6 +260,7 @@ tests/test-qdev-global-props$(EXESUF): tests/test-qdev-global-props.o \
 tests/test-vmstate$(EXESUF): tests/test-vmstate.o \
 	vmstate.o qemu-file.o \
 	libqemuutil.a
+tests/test-timed-average$(EXESUF): tests/test-timed-average.o qemu-timer.o libqemuutil.a libqemustub.a
 
 tests/test-qapi-types.c tests/test-qapi-types.h :\
 $(SRC_PATH)/tests/qapi-schema/qapi-schema-test.json $(SRC_PATH)/scripts/qapi-types.py
diff --git a/tests/test-timed-average.c b/tests/test-timed-average.c
new file mode 100644
index 0000000..170b394
--- /dev/null
+++ b/tests/test-timed-average.c
@@ -0,0 +1,53 @@
+/*
+ * Timed average computation tests
+ *
+ * Copyright Nodalink, EURL. 2014
+ *
+ * Authors:
+ *  Benoît Canet     <benoit.canet@nodalink.com>
+ *
+ * This work is licensed under the terms of the GNU LGPL, version 2 or later.
+ * See the COPYING.LIB file in the top-level directory.
+ */
+
+#include <glib.h>
+#include <unistd.h>
+
+#include "qemu/timed-average.h"
+
+static void account(TimedAverage *ta)
+{
+    timed_average_account(ta, 1);
+    timed_average_account(ta, 5);
+    timed_average_account(ta, 2);
+    timed_average_account(ta, 4);
+    timed_average_account(ta, 3);
+}
+
+static void test_average(void)
+{
+    TimedAverage ta;
+    uint64_t result;
+
+    /* we will compute some average on a period of 1 second */
+    timed_average_init(&ta, QEMU_CLOCK_HOST, 1);
+    account(&ta);
+    result = timed_average_get(&ta);
+    g_assert(result == 3);
+
+    /* sleep a while so the current slice expires */
+    sleep(1);
+
+    /* recompute the same average */
+    account(&ta);
+    result = timed_average_get(&ta);
+    g_assert(result == 3);
+}
+int main(int argc, char **argv)
+{
+    /* tests in the same order as the header function declarations */
+    g_test_init(&argc, &argv, NULL);
+    g_test_add_func("/timed-average/average", test_average);
+    return g_test_run();
+}
+
diff --git a/util/Makefile.objs b/util/Makefile.objs
index 6b3c83b..97d82ce 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -15,3 +15,4 @@ util-obj-y += throttle.o
 util-obj-y += getauxval.o
 util-obj-y += readline.o
 util-obj-y += rfifolock.o
+util-obj-y += timed-average.o
diff --git a/util/timed-average.c b/util/timed-average.c
new file mode 100644
index 0000000..2e687a5
--- /dev/null
+++ b/util/timed-average.c
@@ -0,0 +1,102 @@
+/*
+ * QEMU timed average computation
+ *
+ * Copyright (C) Nodalink, EURL. 2014
+ *
+ * Author:
+ *   Benoît Canet <benoit.canet@nodalink.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 or
+ * (at your option) version 3 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <string.h>
+
+#include "qemu/timed-average.h"
+
+/* This module compute an average on a time slice of ta->period seconds
+ */
+
+/* Set the expiration of the ta->periods seconds time slice
+ *
+ * @ta: the timed average structure used
+ */
+static void timed_average_set_expiration(TimedAverage *ta)
+{
+    int64_t period = ta->period * NANOSECONDS_PER_SECOND;
+    int64_t now = qemu_clock_get_ns(ta->clock_type);
+    ta->expiration = ROUND_UP(now + 1, period);
+}
+
+/* Check if the ta->periods seconds time slice has expired
+ *
+ * If the slice has expired the counters will be reseted
+ *
+ * @ta: the timed average structure used
+ */
+static void timed_average_check_expiration(TimedAverage *ta)
+{
+    int64_t now = qemu_clock_get_ns(ta->clock_type);
+
+    /* if we are still in the period slice do nothing */
+    if (now < ta->expiration) {
+        return;
+    }
+
+    /* the slice has expired -> create a new slice */
+    ta->sum = 0;
+    ta->count = 0;
+    timed_average_set_expiration(ta);
+}
+
+/* Initialize a TimedAverage structure
+ *
+ * @ta:         the timed average structure used
+ * @clock_type: the type of clock to use
+ * @period:     the time slice period in seconds
+ */
+void timed_average_init(TimedAverage *ta, QEMUClockType clock_type,
+                        uint64_t period)
+{
+    memset(ta, 0, sizeof(TimedAverage));
+    ta->clock_type = clock_type;
+    ta->period = period;
+    timed_average_set_expiration(ta);
+}
+
+/* Account a value in the average
+ *
+ * @ta:    the timed average structure used
+ * @value: the value to account in the average
+ */
+void timed_average_account(TimedAverage *ta, uint64_t value)
+{
+    timed_average_check_expiration(ta);
+    ta->sum += value;
+    ta->count++;
+}
+
+/* Get the resulting average value
+ *
+ * @ta:    the timed average structure used
+ */
+uint64_t timed_average_get(TimedAverage *ta)
+{
+    timed_average_check_expiration(ta);
+
+    if (ta->count) {
+        return ta->sum / ta->count;
+    }
+
+    return 0;
+}
-- 
2.1.0