[Qemu-devel] [PATCH v3 0/3] timed average infrastructure for use in block statistics

[Qemu-devel] [PATCH v3 0/3] timed average infrastructure for use in block statistics

[Benoît Canet]

Hi,

Here is the new iteration of the timed average module.

A better algorithm avoiding unwanted noise has been implemented and the test
have been rewritten as suggested.

Best regards

in V3:
        Add Eric rev by of patch 2
        drop unneeded (double) casts [Eric]
        Implement new algorithm [Paolo]
        rewrite commit message [Markus]
        stub cpu_get_clock in tests [Paolo]

Benoît

Benoît Canet (3):
  throttle: Make NANOSECONDS_PER_SECOND an integer
  timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse
  util: Infrastructure for computing recent averages

 include/qemu/throttle.h      |   2 -
 include/qemu/timed-average.h |  60 +++++++++++++
 include/qemu/timer.h         |   2 +
 tests/Makefile               |   2 +
 tests/test-timed-average.c   |  89 ++++++++++++++++++
 util/Makefile.objs           |   1 +
 util/timed-average.c         | 208 +++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 362 insertions(+), 2 deletions(-)
 create mode 100644 include/qemu/timed-average.h
 create mode 100644 tests/test-timed-average.c
 create mode 100644 util/timed-average.c

-- 
2.1.1

[Qemu-devel] [PATCH v3 1/3] throttle: Make NANOSECONDS_PER_SECOND an integer

[Benoît Canet]

We will want to reuse this define in the future by making it common to multiple
QEMU modules.
It would be safer that this define be an integer so we avoid strange float
rounding errors.
Do this conversion.

Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
---
 include/qemu/throttle.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
index b890613..8f9e611 100644
--- a/include/qemu/throttle.h
+++ b/include/qemu/throttle.h
@@ -27,7 +27,7 @@
 #include "qemu-common.h"
 #include "qemu/timer.h"
 
-#define NANOSECONDS_PER_SECOND  1000000000.0
+#define NANOSECONDS_PER_SECOND  1000000000
 
 typedef enum {
     THROTTLE_BPS_TOTAL,
-- 
2.1.1

Re: [Qemu-devel] [PATCH v3 1/3] throttle: Make NANOSECONDS_PER_SECOND an integer

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 987 bytes --]

On 09/24/2014 09:21 AM, Benoît Canet wrote:
> We will want to reuse this define in the future by making it common to multiple
> QEMU modules.
> It would be safer that this define be an integer so we avoid strange float
> rounding errors.
> Do this conversion.
> 
> Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> ---
>  include/qemu/throttle.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

Reviewed-by: Eric Blake <eblake@redhat.com>

> 
> diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
> index b890613..8f9e611 100644
> --- a/include/qemu/throttle.h
> +++ b/include/qemu/throttle.h
> @@ -27,7 +27,7 @@
>  #include "qemu-common.h"
>  #include "qemu/timer.h"
>  
> -#define NANOSECONDS_PER_SECOND  1000000000.0
> +#define NANOSECONDS_PER_SECOND  1000000000
>  
>  typedef enum {
>      THROTTLE_BPS_TOTAL,
> 

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 539 bytes --]

[Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Benoît Canet]

Reviewed-by: Eric Blake <eblake@redhat.com>
Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
---
 include/qemu/throttle.h | 2 --
 include/qemu/timer.h    | 2 ++
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
index 8f9e611..1c639d2 100644
--- a/include/qemu/throttle.h
+++ b/include/qemu/throttle.h
@@ -27,8 +27,6 @@
 #include "qemu-common.h"
 #include "qemu/timer.h"
 
-#define NANOSECONDS_PER_SECOND  1000000000
-
 typedef enum {
     THROTTLE_BPS_TOTAL,
     THROTTLE_BPS_READ,
diff --git a/include/qemu/timer.h b/include/qemu/timer.h
index 5f5210d..0884e72 100644
--- a/include/qemu/timer.h
+++ b/include/qemu/timer.h
@@ -5,6 +5,8 @@
 #include "qemu-common.h"
 #include "qemu/notify.h"
 
+#define NANOSECONDS_PER_SECOND  1000000000
+
 /* timers */
 
 #define SCALE_MS 1000000
-- 
2.1.1

Re: [Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Paolo Bonzini]

Il 24/09/2014 17:21, Benoît Canet ha scritto:
> Reviewed-by: Eric Blake <eblake@redhat.com>
> Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> ---
>  include/qemu/throttle.h | 2 --
>  include/qemu/timer.h    | 2 ++
>  2 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
> index 8f9e611..1c639d2 100644
> --- a/include/qemu/throttle.h
> +++ b/include/qemu/throttle.h
> @@ -27,8 +27,6 @@
>  #include "qemu-common.h"
>  #include "qemu/timer.h"
>  
> -#define NANOSECONDS_PER_SECOND  1000000000
> -
>  typedef enum {
>      THROTTLE_BPS_TOTAL,
>      THROTTLE_BPS_READ,
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index 5f5210d..0884e72 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -5,6 +5,8 @@
>  #include "qemu-common.h"
>  #include "qemu/notify.h"
>  
> +#define NANOSECONDS_PER_SECOND  1000000000
> +
>  /* timers */
>  
>  #define SCALE_MS 1000000
> 

Went through all uses, for the two that matter:

util/throttle.c:    leak = (bkt->avg * (double) delta_ns) / NANOSECONDS_PER_SECOND;
util/throttle.c:    double wait = extra * NANOSECONDS_PER_SECOND;

the other operand is already double.

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Re: [Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Paolo Bonzini]

Il 24/09/2014 17:21, Benoît Canet ha scritto:
> Reviewed-by: Eric Blake <eblake@redhat.com>
> Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> ---
>  include/qemu/throttle.h | 2 --
>  include/qemu/timer.h    | 2 ++
>  2 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
> index 8f9e611..1c639d2 100644
> --- a/include/qemu/throttle.h
> +++ b/include/qemu/throttle.h
> @@ -27,8 +27,6 @@
>  #include "qemu-common.h"
>  #include "qemu/timer.h"
>  
> -#define NANOSECONDS_PER_SECOND  1000000000
> -
>  typedef enum {
>      THROTTLE_BPS_TOTAL,
>      THROTTLE_BPS_READ,
> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> index 5f5210d..0884e72 100644
> --- a/include/qemu/timer.h
> +++ b/include/qemu/timer.h
> @@ -5,6 +5,8 @@
>  #include "qemu-common.h"
>  #include "qemu/notify.h"
>  
> +#define NANOSECONDS_PER_SECOND  1000000000
> +
>  /* timers */
>  
>  #define SCALE_MS 1000000
> 

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

:)

Re: [Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Benoît Canet]

On Wed, Sep 24, 2014 at 05:33:45PM +0200, Paolo Bonzini wrote:
> Il 24/09/2014 17:21, Benoît Canet ha scritto:
> > Reviewed-by: Eric Blake <eblake@redhat.com>
> > Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> > ---
> >  include/qemu/throttle.h | 2 --
> >  include/qemu/timer.h    | 2 ++
> >  2 files changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
> > index 8f9e611..1c639d2 100644
> > --- a/include/qemu/throttle.h
> > +++ b/include/qemu/throttle.h
> > @@ -27,8 +27,6 @@
> >  #include "qemu-common.h"
> >  #include "qemu/timer.h"
> >  
> > -#define NANOSECONDS_PER_SECOND  1000000000
> > -
> >  typedef enum {
> >      THROTTLE_BPS_TOTAL,
> >      THROTTLE_BPS_READ,
> > diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> > index 5f5210d..0884e72 100644
> > --- a/include/qemu/timer.h
> > +++ b/include/qemu/timer.h
> > @@ -5,6 +5,8 @@
> >  #include "qemu-common.h"
> >  #include "qemu/notify.h"
> >  
> > +#define NANOSECONDS_PER_SECOND  1000000000
> > +
> >  /* timers */
> >  
> >  #define SCALE_MS 1000000
> > 
> 
> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>
> 
> :)

Two rev by for one commit are better than one but does this belong to
the third commit ? :)

Best regards

Benoît

Re: [Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Paolo Bonzini]

Il 29/09/2014 18:04, Benoît Canet ha scritto:
> On Wed, Sep 24, 2014 at 05:33:45PM +0200, Paolo Bonzini wrote:
>> Il 24/09/2014 17:21, Benoît Canet ha scritto:
>>> Reviewed-by: Eric Blake <eblake@redhat.com>
>>> Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
>>> ---
>>>  include/qemu/throttle.h | 2 --
>>>  include/qemu/timer.h    | 2 ++
>>>  2 files changed, 2 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
>>> index 8f9e611..1c639d2 100644
>>> --- a/include/qemu/throttle.h
>>> +++ b/include/qemu/throttle.h
>>> @@ -27,8 +27,6 @@
>>>  #include "qemu-common.h"
>>>  #include "qemu/timer.h"
>>>  
>>> -#define NANOSECONDS_PER_SECOND  1000000000
>>> -
>>>  typedef enum {
>>>      THROTTLE_BPS_TOTAL,
>>>      THROTTLE_BPS_READ,
>>> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
>>> index 5f5210d..0884e72 100644
>>> --- a/include/qemu/timer.h
>>> +++ b/include/qemu/timer.h
>>> @@ -5,6 +5,8 @@
>>>  #include "qemu-common.h"
>>>  #include "qemu/notify.h"
>>>  
>>> +#define NANOSECONDS_PER_SECOND  1000000000
>>> +
>>>  /* timers */
>>>  
>>>  #define SCALE_MS 1000000
>>>
>>
>> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>
>>
>> :)
> 
> Two rev by for one commit are better than one but does this belong to
> the third commit ? :)

The rev-bys belong to the first and second.  The third's on my list...

Paolo

Re: [Qemu-devel] [PATCH v3 2/3] timers: Move NANOSECONDS_PER_SECONDS to timer.h for future reuse

[Benoît Canet]

On Mon, Sep 29, 2014 at 11:54:47PM +0200, Paolo Bonzini wrote:
> Il 29/09/2014 18:04, Benoît Canet ha scritto:
> > On Wed, Sep 24, 2014 at 05:33:45PM +0200, Paolo Bonzini wrote:
> >> Il 24/09/2014 17:21, Benoît Canet ha scritto:
> >>> Reviewed-by: Eric Blake <eblake@redhat.com>
> >>> Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
> >>> ---
> >>>  include/qemu/throttle.h | 2 --
> >>>  include/qemu/timer.h    | 2 ++
> >>>  2 files changed, 2 insertions(+), 2 deletions(-)
> >>>
> >>> diff --git a/include/qemu/throttle.h b/include/qemu/throttle.h
> >>> index 8f9e611..1c639d2 100644
> >>> --- a/include/qemu/throttle.h
> >>> +++ b/include/qemu/throttle.h
> >>> @@ -27,8 +27,6 @@
> >>>  #include "qemu-common.h"
> >>>  #include "qemu/timer.h"
> >>>  
> >>> -#define NANOSECONDS_PER_SECOND  1000000000
> >>> -
> >>>  typedef enum {
> >>>      THROTTLE_BPS_TOTAL,
> >>>      THROTTLE_BPS_READ,
> >>> diff --git a/include/qemu/timer.h b/include/qemu/timer.h
> >>> index 5f5210d..0884e72 100644
> >>> --- a/include/qemu/timer.h
> >>> +++ b/include/qemu/timer.h
> >>> @@ -5,6 +5,8 @@
> >>>  #include "qemu-common.h"
> >>>  #include "qemu/notify.h"
> >>>  
> >>> +#define NANOSECONDS_PER_SECOND  1000000000
> >>> +
> >>>  /* timers */
> >>>  
> >>>  #define SCALE_MS 1000000
> >>>
> >>
> >> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>
> >>
> >> :)
> > 
> > Two rev by for one commit are better than one but does this belong to
> > the third commit ? :)
> 
> The rev-bys belong to the first and second.  The third's on my list...
> 

I misread (freudian slip) the 20 seconds delta between the two rev-by as 20 min.
20 min was credible but 20 seconds is not despite you being fast :)

Best regards

Benoît

> Paolo
> 

[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 <pbonzini@redhat.com>
Signed-off-by: Benoît Canet <benoit.canet@nodalink.com>
---
 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 <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 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     <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 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 <benoit.canet@nodalink.com>
+ *
+ * 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

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

[Paolo Bonzini]

Il 24/09/2014 17:21, Benoît Canet ha scritto:
> The module takes care of computing minimal and maximal
> values over the time slice duration.

The code looks good, just two comments:

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

First, do we want this to return double?

Second, this will return the min/max/avg in an unknown amount of time
between period/2 and period---on average period*3/4, e.g. 0.75 seconds
for a period equal to one second.

Would it make sense to tweak the TimedAverage period to be higher, e.g.
1.33 seconds/80 seconds/80 minutes, so that the _average_ period is 1
second/1 minute/1 hour?

This only applies to how the code is used, not to TimedAverage itself;
hence, feel free to post the patch with Reviewed-by once
timed_average_avg's return type is changed to a double.

Paolo

> +    }
> +
> +    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;
> +}
> 

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

[Benoît Canet]

On Mon, Oct 13, 2014 at 02:05:34PM +0200, Paolo Bonzini wrote:
> Il 24/09/2014 17:21, Benoît Canet ha scritto:
> > The module takes care of computing minimal and maximal
> > values over the time slice duration.
> 
> The code looks good, just two comments:
> 
> > +/* 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;
> 
> First, do we want this to return double?
> 
> Second, this will return the min/max/avg in an unknown amount of time
> between period/2 and period---on average period*3/4, e.g. 0.75 seconds
> for a period equal to one second.
> 
> Would it make sense to tweak the TimedAverage period to be higher, e.g.
> 1.33 seconds/80 seconds/80 minutes, so that the _average_ period is 1
> second/1 minute/1 hour?
> 
> This only applies to how the code is used, not to TimedAverage itself;
> hence, feel free to post the patch with Reviewed-by once
> timed_average_avg's return type is changed to a double.

This would require either changing _init period units or making it a float
or baking the 1.33 ratio in timed average.

Which one would you prefer ?

Best regards

Benoît

Thanks for reviewing.

> 
> Paolo
> 
> > +    }
> > +
> > +    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;
> > +}
> > 
>