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 */ 124 static void check_expirations(TimedAverage *ta) 125 { 126 int64_t now = qemu_clock_get_ns(ta->clock_type); 127 int i; 128 129 assert(ta->period != 0); 130 131 /* Check if the windows have expired */ 132 for (i = 0; i < 2; i++) { 133 TimedAverageWindow *w = &ta->windows[i]; 134 if (w->expiration <= now) { 135 window_reset(w); 136 update_expiration(w, now, ta->period); 137 } 138 } 139 140 /* Make ta->current point to the oldest window */ 141 if (ta->windows[0].expiration < ta->windows[1].expiration) { 142 ta->current = 0; 143 } else { 144 ta->current = 1; 145 } 146 } 147 148 /* Account a value 149 * 150 * @ta: the TimedAverage structure 151 * @value: the value to account 152 */ 153 void timed_average_account(TimedAverage *ta, uint64_t value) 154 { 155 int i; 156 check_expirations(ta); 157 158 /* Do the accounting in both windows at the same time */ 159 for (i = 0; i < 2; i++) { 160 TimedAverageWindow *w = &ta->windows[i]; 161 162 w->sum += value; 163 w->count++; 164 165 if (value < w->min) { 166 w->min = value; 167 } 168 169 if (value > w->max) { 170 w->max = value; 171 } 172 } 173 } 174 175 /* Get the minimum value 176 * 177 * @ta: the TimedAverage structure 178 * @ret: the minimum value 179 */ 180 uint64_t timed_average_min(TimedAverage *ta) 181 { 182 TimedAverageWindow *w; 183 check_expirations(ta); 184 w = current_window(ta); 185 return w->min < UINT64_MAX ? w->min : 0; 186 } 187 188 /* Get the average value 189 * 190 * @ta: the TimedAverage structure 191 * @ret: the average value 192 */ 193 uint64_t timed_average_avg(TimedAverage *ta) 194 { 195 TimedAverageWindow *w; 196 check_expirations(ta); 197 w = current_window(ta); 198 return w->count > 0 ? w->sum / w->count : 0; 199 } 200 201 /* Get the maximum value 202 * 203 * @ta: the TimedAverage structure 204 * @ret: the maximum value 205 */ 206 uint64_t timed_average_max(TimedAverage *ta) 207 { 208 check_expirations(ta); 209 return current_window(ta)->max; 210 } 211