Merge remote-tracking branch 'remotes/pmaydell/tags/pull-target-arm-20210330' into...
[qemu/ar7.git] / util / timed-average.c
blob2b49d532ceef308c57c18cfc84ce8d3f8c98f722
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 software: you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software 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  */
25 #include "qemu/osdep.h"
27 #include "qemu/timed-average.h"
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  */
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)
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;
68 /* Reset a window
69  *
70  * @w: the window to reset
71  */
72 static void window_reset(TimedAverageWindow *w)
74     w->min = UINT64_MAX;
75     w->max = 0;
76     w->sum = 0;
77     w->count = 0;
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)
88      return &ta->windows[ta->current];
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)
100     int64_t now = qemu_clock_get_ns(clock_type);
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;
111     window_reset(&ta->windows[0]);
112     window_reset(&ta->windows[1]);
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;
119 /* Check if the time windows have expired, updating their counters and
120  * expiration time if that's the case.
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)
128     int64_t now = qemu_clock_get_ns(ta->clock_type);
129     int i;
131     assert(ta->period != 0);
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     }
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     }
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     }
156 /* Account a value
158  * @ta:    the TimedAverage structure
159  * @value: the value to account
160  */
161 void timed_average_account(TimedAverage *ta, uint64_t value)
163     int i;
164     check_expirations(ta, NULL);
166     /* Do the accounting in both windows at the same time */
167     for (i = 0; i < 2; i++) {
168         TimedAverageWindow *w = &ta->windows[i];
170         w->sum += value;
171         w->count++;
173         if (value < w->min) {
174             w->min = value;
175         }
177         if (value > w->max) {
178             w->max = value;
179         }
180     }
183 /* Get the minimum value
185  * @ta:  the TimedAverage structure
186  * @ret: the minimum value
187  */
188 uint64_t timed_average_min(TimedAverage *ta)
190     TimedAverageWindow *w;
191     check_expirations(ta, NULL);
192     w = current_window(ta);
193     return w->min < UINT64_MAX ? w->min : 0;
196 /* Get the average value
198  * @ta:  the TimedAverage structure
199  * @ret: the average value
200  */
201 uint64_t timed_average_avg(TimedAverage *ta)
203     TimedAverageWindow *w;
204     check_expirations(ta, NULL);
205     w = current_window(ta);
206     return w->count > 0 ? w->sum / w->count : 0;
209 /* Get the maximum value
211  * @ta:  the TimedAverage structure
212  * @ret: the maximum value
213  */
214 uint64_t timed_average_max(TimedAverage *ta)
216     check_expirations(ta, NULL);
217     return current_window(ta)->max;
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)
227     TimedAverageWindow *w;
228     check_expirations(ta, elapsed);
229     w = current_window(ta);
230     return w->sum;