scsi: pvscsi: check command descriptor ring buffer size (CVE-2016-4952)
[qemu.git] / 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 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 */
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 }