[Qemu-devel] [PATCH v3 3/3] util: Infrastructure for computing recent averages

[Benoît Canet]

The module takes care of computing minimal and maximal
values over the time slice duration.

Suggested-by: Paolo Bonzini <address@hidden>
Signed-off-by: Benoît Canet <address@hidden>
---
 include/qemu/timed-average.h |  60 +++++++++++++
 tests/Makefile               |   2 +
 tests/test-timed-average.c   |  89 ++++++++++++++++++
 util/Makefile.objs           |   1 +
 util/timed-average.c         | 208 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 360 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..8150ead
--- /dev/null
+++ b/include/qemu/timed-average.h
@@ -0,0 +1,60 @@
+/*
+ * QEMU timed average computation
+ *
+ * Copyright (C) Nodalink, EURL. 2014
+ *
+ * Author:
+ *   Benoît Canet <address@hidden>
+ *
+ * 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 of the License, or
+ * (at your option) version 3 or any later version.
+ *
+ * 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 Window {
+    uint64_t      min;           /* minimal value accounted in the window */
+    uint64_t      max;           /* maximal value accounted in the window */
+    uint64_t      sum;           /* sum of the discrete values */
+    uint64_t      count;         /* number of values */
+    int64_t       expiration;    /* the end of the current window in ns */
+} Window;
+
+typedef struct TimedAverage {
+    Window        windows[2];    /* two overlapping windows of period
+                                  * nanoseconds with an offset of period / 2
+                                  * between them
+                                  */
+
+    uint64_t      period;        /* period in nanoseconds */
+    uint64_t      current;       /* the current window index: it's also the
+                                  * oldest window index
+                                  */
+    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_min(TimedAverage *ta);
+uint64_t timed_average_avg(TimedAverage *ta);
+uint64_t timed_average_max(TimedAverage *ta);
+
+#endif
diff --git a/tests/Makefile b/tests/Makefile
index 469c0a5..d3669f4 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 stubs/clock-warp.o stubs/cpu-get-icount.o stubs/notify-event.o
 
 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..5091589
--- /dev/null
+++ b/tests/test-timed-average.c
@@ -0,0 +1,89 @@
+/*
+ * Timed average computation tests
+ *
+ * Copyright Nodalink, EURL. 2014
+ *
+ * Authors:
+ *  Benoît Canet     <address@hidden>
+ *
+ * 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 int64_t my_clock_value;
+
+int64_t cpu_get_clock(void)
+{
+    return my_clock_value;
+}
+
+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;
+    int i;
+
+    /* we will compute some average on a period of 1 second */
+    timed_average_init(&ta, QEMU_CLOCK_VIRTUAL, 1);
+
+    result = timed_average_min(&ta);
+    g_assert(result == 0);
+    result = timed_average_avg(&ta);
+    g_assert(result == 0);
+    result = timed_average_max(&ta);
+    g_assert(result == 0);
+
+    for (i = 0; i < 100; i++) {
+        account(&ta);
+        result = timed_average_min(&ta);
+        g_assert(result == 1);
+        result = timed_average_avg(&ta);
+        g_assert(result == 3);
+        result = timed_average_max(&ta);
+        g_assert(result == 5);
+        my_clock_value += NANOSECONDS_PER_SECOND / 10;
+    }
+
+    my_clock_value += (int64_t) NANOSECONDS_PER_SECOND * 100;
+
+    result = timed_average_min(&ta);
+    g_assert(result == 0);
+    result = timed_average_avg(&ta);
+    g_assert(result == 0);
+    result = timed_average_max(&ta);
+    g_assert(result == 0);
+
+    for (i = 0; i < 100; i++) {
+        account(&ta);
+        result = timed_average_min(&ta);
+        g_assert(result == 1);
+        result = timed_average_avg(&ta);
+        g_assert(result == 3);
+        result = timed_average_max(&ta);
+        g_assert(result == 5);
+        my_clock_value += NANOSECONDS_PER_SECOND / 10;
+    }
+}
+
+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..e594d37
--- /dev/null
+++ b/util/timed-average.c
@@ -0,0 +1,208 @@
+/*
+ * QEMU timed average computation
+ *
+ * Copyright (C) Nodalink, EURL. 2014
+ *
+ * Author:
+ *   Benoît Canet <address@hidden>
+ *
+ * This program is free sofware: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Sofware Foundation, either version 2 of the License, or
+ * (at your option) version 3 or any later version.
+ *
+ * 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 nanoseconds
+ *
+ * Algorithm:
+ *
+ * - create two windows, with the suggested expiration period, and offsetted by
+ *   period / 2 then return min/avg/max from the oldest window.
+ *
+ * Example:
+ *
+ *        t=0          |t=0.5           |t=1          |t=1.5            |t=2
+ *        wnd0: [0,0.5)|wnd0: [0.5,1.5) |             |wnd0: [1.5,2.5)  |
+ *        wnd1: [0,1)  |                |wnd1: [1,2)  |                 |
+ *
+ * Values are returned from:
+ *
+ *        wnd0---------|wnd1------------|wnd0---------|wnd1-------------|
+ */
+
+/* Update the expiration of a ta->period nanoseconds time window
+ *
+ * @w:      the window used
+ * @now:    the current time in nanoseconds
+ * @period: the expiration period in nanoseconds
+ */
+static void update_expiration(Window *w, int64_t now, int64_t period)
+{
+    /* time delta elapsed since last theorical expiration */
+    int64_t delta = (now - w->expiration) % period;
+    /* time remaininging until next theorical expiration */
+    int64_t remaining = period - delta;
+    /* compute expiration */
+    w->expiration = now + remaining;
+}
+
+/* Reset a window
+ *
+ * @w: the window to reset
+ */
+static void window_reset(Window *w)
+{
+    w->min = UINT64_MAX;
+    w->max = 0;
+    w->sum = 0;
+    w->count = 0;
+}
+
+/* Get the current window
+ *
+ * @ta:  the TimedAverage we are working with
+ * @ret: a pointer to the current window
+ */
+static Window *current_window(TimedAverage *ta)
+{
+     return &ta->windows[ta->current % 2];
+}
+
+/* Check if one or the two ta->period nanoseconds time window have expired
+ *
+ * If a window has expired its counters will be reset and its expiration time
+ * updated
+ *
+ * @ta: the timed average structure used
+ */
+static void check_expirations(TimedAverage *ta)
+{
+    int64_t now = qemu_clock_get_ns(ta->clock_type);
+    int i;
+
+    /* check that both window are not expired
+     * if a window is expired reset it and update it's expiration time
+     */
+    for (i = 0; i < 2; i++) {
+        Window *w = current_window(ta);
+        if (now < w->expiration) {
+            continue;
+        }
+        window_reset(w);
+        update_expiration(w, now, ta->period);
+        ta->current++;
+    }
+}
+
+/* initialize a TimedAverage structure
+ *
+ * @ta:         the timed average structure used
+ * @clock_type: the type of clock to use
+ * @period:     the time window period in seconds
+ */
+void timed_average_init(TimedAverage *ta, QEMUClockType clock_type,
+                        uint64_t period)
+{
+    int64_t now = qemu_clock_get_ns(clock_type);
+
+    /* reset the struct content */
+    memset(ta, 0, sizeof(TimedAverage));
+
+    ta->period = period * NANOSECONDS_PER_SECOND;
+    ta->clock_type = clock_type;
+
+    window_reset(&ta->windows[0]);
+    window_reset(&ta->windows[1]);
+
+    /* first window expiration offsetted by an half period */
+    ta->windows[0].expiration = now + ta->period / 2;
+    ta->windows[1].expiration = now + ta->period;
+}
+
+/* Account a value
+ *
+ * @ta:    the timed average structure used
+ * @value: the value to account in the average
+ */
+void timed_average_account(TimedAverage *ta, uint64_t value)
+{
+    int i;
+    check_expirations(ta);
+
+    /* do the accouting in the two windows at the same time */
+    for (i = 0; i < 2; i++) {
+        Window *w = &ta->windows[i];
+
+        w->sum += value;
+        w->count++;
+
+        if (value < w->min) {
+            w->min = value;
+        }
+
+        if (value > w->max) {
+            w->max = value;
+        }
+    }
+}
+
+/* Get the minimal value
+ *
+ * @ta:  the timed average structure used
+ * @ret: the minimal value
+ */
+uint64_t timed_average_min(TimedAverage *ta)
+{
+    Window *w;
+    check_expirations(ta);
+
+    w = current_window(ta);
+
+    if (w->min == UINT64_MAX) {
+        return 0;
+    }
+
+    return w->min;
+}
+
+/* Get the average value
+ *
+ * @ta:  the timed average structure used
+ * @ret: the average value
+ */
+uint64_t timed_average_avg(TimedAverage *ta)
+{
+    Window *w;
+    check_expirations(ta);
+
+    w = current_window(ta);
+
+    if (w->count) {
+        return w->sum / w->count;
+    }
+
+    return 0;
+}
+
+/* Get the maximum value
+ *
+ * @ta:  the timed average structure used
+ * @ret: the maximal value
+ */
+uint64_t timed_average_max(TimedAverage *ta)
+{
+    check_expirations(ta);
+    return current_window(ta)->max;
+}
-- 
2.1.1