As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option.
Alternatively you can here view or download the uninterpreted source code file.
For more information about "freq_ctr.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.9.8_vs_2.0.0.

1 /* 2 * include/proto/freq_ctr.h 3 * This file contains macros and inline functions for frequency counters. 4 * 5 * Copyright (C) 2000-2014 Willy Tarreau - w@1wt.eu 6 * 7 * This library is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU Lesser General Public 9 * License as published by the Free Software Foundation, version 2.1 10 * exclusively. 11 * 12 * This library is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with this library; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22 #ifndef _PROTO_FREQ_CTR_H 23 #define _PROTO_FREQ_CTR_H 24 25 #include <common/config.h> 26 #include <common/time.h> 27 #include <common/hathreads.h> 28 #include <types/freq_ctr.h> 29 30 31 /* Update a frequency counter by <inc> incremental units. It is automatically 32 * rotated if the period is over. It is important that it correctly initializes 33 * a null area. 34 */ 35 static inline unsigned int update_freq_ctr(struct freq_ctr *ctr, unsigned int inc) 36 { 37 int elapsed; 38 unsigned int curr_sec; 39 40 41 /* we manipulate curr_ctr using atomic ops out of the lock, since 42 * it's the most frequent access. However if we detect that a change 43 * is needed, it's done under the date lock. We don't care whether 44 * the value we're adding is considered as part of the current or 45 * new period if another thread starts to rotate the period while 46 * we operate, since timing variations would have resulted in the 47 * same uncertainty as well. 48 */ 49 curr_sec = ctr->curr_sec; 50 if (curr_sec == (now.tv_sec & 0x7fffffff)) 51 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc); 52 53 do { 54 /* remove the bit, used for the lock */ 55 curr_sec &= 0x7fffffff; 56 } while (!_HA_ATOMIC_CAS(&ctr->curr_sec, &curr_sec, curr_sec | 0x80000000)); 57 __ha_barrier_atomic_store(); 58 59 elapsed = (now.tv_sec & 0x7fffffff)- curr_sec; 60 if (unlikely(elapsed > 0)) { 61 ctr->prev_ctr = ctr->curr_ctr; 62 _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr); 63 if (likely(elapsed != 1)) { 64 /* we missed more than one second */ 65 ctr->prev_ctr = 0; 66 } 67 curr_sec = now.tv_sec; 68 } 69 70 /* release the lock and update the time in case of rotate. */ 71 _HA_ATOMIC_STORE(&ctr->curr_sec, curr_sec & 0x7fffffff); 72 73 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc); 74 } 75 76 /* Update a frequency counter by <inc> incremental units. It is automatically 77 * rotated if the period is over. It is important that it correctly initializes 78 * a null area. This one works on frequency counters which have a period 79 * different from one second. 80 */ 81 static inline unsigned int update_freq_ctr_period(struct freq_ctr_period *ctr, 82 unsigned int period, unsigned int inc) 83 { 84 unsigned int curr_tick; 85 86 curr_tick = ctr->curr_tick; 87 if (now_ms - curr_tick < period) 88 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc); 89 90 do { 91 /* remove the bit, used for the lock */ 92 curr_tick &= ~1; 93 } while (!_HA_ATOMIC_CAS(&ctr->curr_tick, &curr_tick, curr_tick | 0x1)); 94 __ha_barrier_atomic_store(); 95 96 if (now_ms - curr_tick >= period) { 97 ctr->prev_ctr = ctr->curr_ctr; 98 _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr); 99 curr_tick += period; 100 if (likely(now_ms - curr_tick >= period)) { 101 /* we missed at least two periods */ 102 ctr->prev_ctr = 0; 103 curr_tick = now_ms; 104 } 105 curr_tick &= ~1; 106 } 107 108 /* release the lock and update the time in case of rotate. */ 109 _HA_ATOMIC_STORE(&ctr->curr_tick, curr_tick); 110 111 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc); 112 } 113 114 /* Read a frequency counter taking history into account for missing time in 115 * current period. 116 */ 117 unsigned int read_freq_ctr(struct freq_ctr *ctr); 118 119 /* returns the number of remaining events that can occur on this freq counter 120 * while respecting <freq> and taking into account that <pend> events are 121 * already known to be pending. Returns 0 if limit was reached. 122 */ 123 unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend); 124 125 /* return the expected wait time in ms before the next event may occur, 126 * respecting frequency <freq>, and assuming there may already be some pending 127 * events. It returns zero if we can proceed immediately, otherwise the wait 128 * time, which will be rounded down 1ms for better accuracy, with a minimum 129 * of one ms. 130 */ 131 unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend); 132 133 /* process freq counters over configurable periods */ 134 unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period); 135 unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period, 136 unsigned int freq, unsigned int pend); 137 138 /* While the functions above report average event counts per period, we are 139 * also interested in average values per event. For this we use a different 140 * method. The principle is to rely on a long tail which sums the new value 141 * with a fraction of the previous value, resulting in a sliding window of 142 * infinite length depending on the precision we're interested in. 143 * 144 * The idea is that we always keep (N-1)/N of the sum and add the new sampled 145 * value. The sum over N values can be computed with a simple program for a 146 * constant value 1 at each iteration : 147 * 148 * N 149 * ,--- 150 * \ N - 1 e - 1 151 * > ( --------- )^x ~= N * ----- 152 * / N e 153 * '--- 154 * x = 1 155 * 156 * Note: I'm not sure how to demonstrate this but at least this is easily 157 * verified with a simple program, the sum equals N * 0.632120 for any N 158 * moderately large (tens to hundreds). 159 * 160 * Inserting a constant sample value V here simply results in : 161 * 162 * sum = V * N * (e - 1) / e 163 * 164 * But we don't want to integrate over a small period, but infinitely. Let's 165 * cut the infinity in P periods of N values. Each period M is exactly the same 166 * as period M-1 with a factor of ((N-1)/N)^N applied. A test shows that given a 167 * large N : 168 * 169 * N - 1 1 170 * ( ------- )^N ~= --- 171 * N e 172 * 173 * Our sum is now a sum of each factor times : 174 * 175 * N*P P 176 * ,--- ,--- 177 * \ N - 1 e - 1 \ 1 178 * > v ( --------- )^x ~= VN * ----- * > --- 179 * / N e / e^x 180 * '--- '--- 181 * x = 1 x = 0 182 * 183 * For P "large enough", in tests we get this : 184 * 185 * P 186 * ,--- 187 * \ 1 e 188 * > --- ~= ----- 189 * / e^x e - 1 190 * '--- 191 * x = 0 192 * 193 * This simplifies the sum above : 194 * 195 * N*P 196 * ,--- 197 * \ N - 1 198 * > v ( --------- )^x = VN 199 * / N 200 * '--- 201 * x = 1 202 * 203 * So basically by summing values and applying the last result an (N-1)/N factor 204 * we just get N times the values over the long term, so we can recover the 205 * constant value V by dividing by N. In order to limit the impact of integer 206 * overflows, we'll use this equivalence which saves us one multiply : 207 * 208 * N - 1 1 x0 209 * x1 = x0 * ------- = x0 * ( 1 - --- ) = x0 - ---- 210 * N N N 211 * 212 * And given that x0 is discrete here we'll have to saturate the values before 213 * performing the divide, so the value insertion will become : 214 * 215 * x0 + N - 1 216 * x1 = x0 - ------------ 217 * N 218 * 219 * A value added at the entry of the sliding window of N values will thus be 220 * reduced to 1/e or 36.7% after N terms have been added. After a second batch, 221 * it will only be 1/e^2, or 13.5%, and so on. So practically speaking, each 222 * old period of N values represents only a quickly fading ratio of the global 223 * sum : 224 * 225 * period ratio 226 * 1 36.7% 227 * 2 13.5% 228 * 3 4.98% 229 * 4 1.83% 230 * 5 0.67% 231 * 6 0.25% 232 * 7 0.09% 233 * 8 0.033% 234 * 9 0.012% 235 * 10 0.0045% 236 * 237 * So after 10N samples, the initial value has already faded out by a factor of 238 * 22026, which is quite fast. If the sliding window is 1024 samples wide, it 239 * means that a sample will only count for 1/22k of its initial value after 10k 240 * samples went after it, which results in half of the value it would represent 241 * using an arithmetic mean. The benefit of this method is that it's very cheap 242 * in terms of computations when N is a power of two. This is very well suited 243 * to record response times as large values will fade out faster than with an 244 * arithmetic mean and will depend on sample count and not time. 245 * 246 * Demonstrating all the above assumptions with maths instead of a program is 247 * left as an exercise for the reader. 248 */ 249 250 /* Adds sample value <v> to sliding window sum <sum> configured for <n> samples. 251 * The sample is returned. Better if <n> is a power of two. 252 */ 253 static inline unsigned int swrate_add(unsigned int *sum, unsigned int n, unsigned int v) 254 { 255 return *sum = *sum - (*sum + n - 1) / n + v; 256 } 257 258 /* Adds sample value <v> spanning <s> samples to sliding window sum <sum> 259 * configured for <n> samples, where <n> is supposed to be "much larger" than 260 * <s>. The sample is returned. Better if <n> is a power of two. Note that this 261 * is only an approximate. Indeed, as can be seen with two samples only over a 262 * 8-sample window, the original function would return : 263 * sum1 = sum - (sum + 7) / 8 + v 264 * sum2 = sum1 - (sum1 + 7) / 8 + v 265 * = (sum - (sum + 7) / 8 + v) - (sum - (sum + 7) / 8 + v + 7) / 8 + v 266 * ~= 7sum/8 - 7/8 + v - sum/8 + sum/64 - 7/64 - v/8 - 7/8 + v 267 * ~= (3sum/4 + sum/64) - (7/4 + 7/64) + 15v/8 268 * 269 * while the function below would return : 270 * sum = sum + 2*v - (sum + 8) * 2 / 8 271 * = 3sum/4 + 2v - 2 272 * 273 * this presents an error of ~ (sum/64 + 9/64 + v/8) = (sum+n+1)/(n^s) + v/n 274 * 275 * Thus the simplified function effectively replaces a part of the history with 276 * a linear sum instead of applying the exponential one. But as long as s/n is 277 * "small enough", the error fades away and remains small for both small and 278 * large values of n and s (typically < 0.2% measured). 279 */ 280 static inline unsigned int swrate_add_scaled(unsigned int *sum, unsigned int n, unsigned int v, unsigned int s) 281 { 282 return *sum = *sum + v * s - div64_32((unsigned long long)(*sum + n) * s, n); 283 } 284 285 /* Returns the average sample value for the sum <sum> over a sliding window of 286 * <n> samples. Better if <n> is a power of two. It must be the same <n> as the 287 * one used above in all additions. 288 */ 289 static inline unsigned int swrate_avg(unsigned int sum, unsigned int n) 290 { 291 return (sum + n - 1) / n; 292 } 293 294 #endif /* _PROTO_FREQ_CTR_H */ 295 296 /* 297 * Local variables: 298 * c-indent-level: 8 299 * c-basic-offset: 8 300 * End: 301 */