util/timed-average.c

   1 /*
   2  * QEMU timed average computation
   3  *
   4  * Copyright (C) Nodalink, EURL. 2014
   5  * Copyright (C) Igalia, S.L. 2015
   6  *
   7  * Authors:
   8  *   Benoît Canet <benoit.canet@nodalink.com>
   9  *   Alberto Garcia <berto@igalia.com>
  10  *
  11  * This program is free sofware: you can redistribute it and/or modify
  12  * it under the terms of the GNU General Public License as published by
  13  * the Free Sofware Foundation, either version 2 of the License, or
  14  * (at your option) version 3 or any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  23  */
  24
  25 #include "qemu/osdep.h"
  26
  27 #include "qemu/timed-average.h"
  28
  29 /* This module computes an average of a set of values within a time
  30  * window.
  31  *
  32  * Algorithm:
  33  *
  34  * - Create two windows with a certain expiration period, and
  35  *   offsetted by period / 2.
  36  * - Each time you want to account a new value, do it in both windows.
  37  * - The minimum / maximum / average values are always returned from
  38  *   the oldest window.
  39  *
  40  * Example:
  41  *
  42  *        t=0          |t=0.5           |t=1          |t=1.5            |t=2
  43  *        wnd0: [0,0.5)|wnd0: [0.5,1.5) |             |wnd0: [1.5,2.5)  |
  44  *        wnd1: [0,1)  |                |wnd1: [1,2)  |                 |
  45  *
  46  * Values are returned from:
  47  *
  48  *        wnd0---------|wnd1------------|wnd0---------|wnd1-------------|
  49  */
  50
  51 /* Update the expiration of a time window
  52  *
  53  * @w:      the window used
  54  * @now:    the current time in nanoseconds
  55  * @period: the expiration period in nanoseconds
  56  */
  57 static void update_expiration(TimedAverageWindow *w, int64_t now,
  58                               int64_t period)
  59 {
  60     /* time elapsed since the last theoretical expiration */
  61     int64_t elapsed = (now - w->expiration) % period;
  62     /* time remaininging until the next expiration */
  63     int64_t remaining = period - elapsed;
  64     /* compute expiration */
  65     w->expiration = now + remaining;
  66 }
  67
  68 /* Reset a window
  69  *
  70  * @w: the window to reset
  71  */
  72 static void window_reset(TimedAverageWindow *w)
  73 {
  74     w->min = UINT64_MAX;
  75     w->max = 0;
  76     w->sum = 0;
  77     w->count = 0;
  78 }
  79
  80 /* Get the current window (that is, the one with the earliest
  81  * expiration time).
  82  *
  83  * @ta:  the TimedAverage structure
  84  * @ret: a pointer to the current window
  85  */
  86 static TimedAverageWindow *current_window(TimedAverage *ta)
  87 {
  88      return &ta->windows[ta->current];
  89 }
  90
  91 /* Initialize a TimedAverage structure
  92  *
  93  * @ta:         the TimedAverage structure
  94  * @clock_type: the type of clock to use
  95  * @period:     the time window period in nanoseconds
  96  */
  97 void timed_average_init(TimedAverage *ta, QEMUClockType clock_type,
  98                         uint64_t period)
  99 {
 100     int64_t now = qemu_clock_get_ns(clock_type);
 101
 102     /* Returned values are from the oldest window, so they belong to
 103      * the interval [ta->period/2,ta->period). By adjusting the
 104      * requested period by 4/3, we guarantee that they're in the
 105      * interval [2/3 period,4/3 period), closer to the requested
 106      * period on average */
 107     ta->period = (uint64_t) period * 4 / 3;
 108     ta->clock_type = clock_type;
 109     ta->current = 0;
 110
 111     window_reset(&ta->windows[0]);
 112     window_reset(&ta->windows[1]);
 113
 114     /* Both windows are offsetted by half a period */
 115     ta->windows[0].expiration = now + ta->period / 2;
 116     ta->windows[1].expiration = now + ta->period;
 117 }
 118
 119 /* Check if the time windows have expired, updating their counters and
 120  * expiration time if that's the case.
 121  *
 122  * @ta: the TimedAverage structure
 123  * @elapsed: if non-NULL, the elapsed time (in ns) within the current
 124  *           window will be stored here
 125  */
 126 static void check_expirations(TimedAverage *ta, uint64_t *elapsed)
 127 {
 128     int64_t now = qemu_clock_get_ns(ta->clock_type);
 129     int i;
 130
 131     assert(ta->period != 0);
 132
 133     /* Check if the windows have expired */
 134     for (i = 0; i < 2; i++) {
 135         TimedAverageWindow *w = &ta->windows[i];
 136         if (w->expiration <= now) {
 137             window_reset(w);
 138             update_expiration(w, now, ta->period);
 139         }
 140     }
 141
 142     /* Make ta->current point to the oldest window */
 143     if (ta->windows[0].expiration < ta->windows[1].expiration) {
 144         ta->current = 0;
 145     } else {
 146         ta->current = 1;
 147     }
 148
 149     /* Calculate the elapsed time within the current window */
 150     if (elapsed) {
 151         int64_t remaining = ta->windows[ta->current].expiration - now;
 152         *elapsed = ta->period - remaining;
 153     }
 154 }
 155
 156 /* Account a value
 157  *
 158  * @ta:    the TimedAverage structure
 159  * @value: the value to account
 160  */
 161 void timed_average_account(TimedAverage *ta, uint64_t value)
 162 {
 163     int i;
 164     check_expirations(ta, NULL);
 165
 166     /* Do the accounting in both windows at the same time */
 167     for (i = 0; i < 2; i++) {
 168         TimedAverageWindow *w = &ta->windows[i];
 169
 170         w->sum += value;
 171         w->count++;
 172
 173         if (value < w->min) {
 174             w->min = value;
 175         }
 176
 177         if (value > w->max) {
 178             w->max = value;
 179         }
 180     }
 181 }
 182
 183 /* Get the minimum value
 184  *
 185  * @ta:  the TimedAverage structure
 186  * @ret: the minimum value
 187  */
 188 uint64_t timed_average_min(TimedAverage *ta)
 189 {
 190     TimedAverageWindow *w;
 191     check_expirations(ta, NULL);
 192     w = current_window(ta);
 193     return w->min < UINT64_MAX ? w->min : 0;
 194 }
 195
 196 /* Get the average value
 197  *
 198  * @ta:  the TimedAverage structure
 199  * @ret: the average value
 200  */
 201 uint64_t timed_average_avg(TimedAverage *ta)
 202 {
 203     TimedAverageWindow *w;
 204     check_expirations(ta, NULL);
 205     w = current_window(ta);
 206     return w->count > 0 ? w->sum / w->count : 0;
 207 }
 208
 209 /* Get the maximum value
 210  *
 211  * @ta:  the TimedAverage structure
 212  * @ret: the maximum value
 213  */
 214 uint64_t timed_average_max(TimedAverage *ta)
 215 {
 216     check_expirations(ta, NULL);
 217     return current_window(ta)->max;
 218 }
 219
 220 /* Get the sum of all accounted values
 221  * @ta:      the TimedAverage structure
 222  * @elapsed: if non-NULL, the elapsed time (in ns) will be stored here
 223  * @ret:     the sum of all accounted values
 224  */
 225 uint64_t timed_average_sum(TimedAverage *ta, uint64_t *elapsed)
 226 {
 227     TimedAverageWindow *w;
 228     check_expirations(ta, elapsed);
 229     w = current_window(ta);
 230     return w->sum;
 231 }