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 */
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 */
57static 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 */
72static 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 */
86static 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 */
97void 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 */
126static 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 */
161void 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 */
188uint64_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 */
201uint64_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 */
214uint64_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 */
225uint64_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}
232