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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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