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 <string.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 } 232