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