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