blob: 184cdc63385e0edaeae45425a6424a75e94dd052 [file] [log] [blame]
Willy Tarreau7f062c42009-03-05 18:43:00 +01001/*
Willy Tarreau2438f2b2014-06-16 20:24:22 +02002 * 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 */
Willy Tarreau7f062c42009-03-05 18:43:00 +010021
22#ifndef _PROTO_FREQ_CTR_H
23#define _PROTO_FREQ_CTR_H
24
25#include <common/config.h>
Willy Tarreau78ff5d02009-10-01 11:05:26 +020026#include <common/time.h>
Christopher Faulet94b71232017-10-12 09:49:09 +020027#include <common/hathreads.h>
Willy Tarreau7f062c42009-03-05 18:43:00 +010028#include <types/freq_ctr.h>
29
Willy Tarreau7f062c42009-03-05 18:43:00 +010030
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 */
Christopher Fauletde2075f2017-09-01 12:18:36 +020035static inline unsigned int update_freq_ctr(struct freq_ctr *ctr, unsigned int inc)
Willy Tarreau7f062c42009-03-05 18:43:00 +010036{
Emeric Brun6e012862017-10-30 18:04:28 +010037 int elapsed;
Christopher Faulet94b71232017-10-12 09:49:09 +020038 unsigned int curr_sec;
39
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020040
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
Christopher Faulet94b71232017-10-12 09:49:09 +020053 do {
54 /* remove the bit, used for the lock */
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020055 curr_sec &= 0x7fffffff;
56 } while (!_HA_ATOMIC_CAS(&ctr->curr_sec, &curr_sec, curr_sec | 0x80000000));
Olivier Houchardd5f9b192019-03-08 18:47:59 +010057 __ha_barrier_atomic_store();
Willy Tarreau7f062c42009-03-05 18:43:00 +010058
Christopher Faulet94b71232017-10-12 09:49:09 +020059 elapsed = (now.tv_sec & 0x7fffffff)- curr_sec;
Emeric Brun6e012862017-10-30 18:04:28 +010060 if (unlikely(elapsed > 0)) {
Christopher Faulet94b71232017-10-12 09:49:09 +020061 ctr->prev_ctr = ctr->curr_ctr;
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020062 _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr);
Christopher Faulet94b71232017-10-12 09:49:09 +020063 if (likely(elapsed != 1)) {
64 /* we missed more than one second */
65 ctr->prev_ctr = 0;
66 }
Emeric Brun6e012862017-10-30 18:04:28 +010067 curr_sec = now.tv_sec;
Willy Tarreau2970b0b2010-06-20 07:15:43 +020068 }
Christopher Faulet94b71232017-10-12 09:49:09 +020069
Christopher Faulet94b71232017-10-12 09:49:09 +020070 /* release the lock and update the time in case of rotate. */
Olivier Houchardd5f9b192019-03-08 18:47:59 +010071 _HA_ATOMIC_STORE(&ctr->curr_sec, curr_sec & 0x7fffffff);
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020072
73 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
Willy Tarreau2970b0b2010-06-20 07:15:43 +020074}
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 */
Christopher Fauletde2075f2017-09-01 12:18:36 +020081static inline unsigned int update_freq_ctr_period(struct freq_ctr_period *ctr,
82 unsigned int period, unsigned int inc)
Willy Tarreau2970b0b2010-06-20 07:15:43 +020083{
Christopher Faulet94b71232017-10-12 09:49:09 +020084 unsigned int curr_tick;
85
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020086 curr_tick = ctr->curr_tick;
87 if (now_ms - curr_tick < period)
88 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
89
Christopher Faulet94b71232017-10-12 09:49:09 +020090 do {
91 /* remove the bit, used for the lock */
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020092 curr_tick &= ~1;
93 } while (!_HA_ATOMIC_CAS(&ctr->curr_tick, &curr_tick, curr_tick | 0x1));
Olivier Houchardd5f9b192019-03-08 18:47:59 +010094 __ha_barrier_atomic_store();
Christopher Faulet94b71232017-10-12 09:49:09 +020095
96 if (now_ms - curr_tick >= period) {
97 ctr->prev_ctr = ctr->curr_ctr;
Willy Tarreau0d6c75d2019-05-25 19:54:40 +020098 _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr);
Christopher Faulet94b71232017-10-12 09:49:09 +020099 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 }
Willy Tarreau0d6c75d2019-05-25 19:54:40 +0200105 curr_tick &= ~1;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200106 }
Christopher Faulet94b71232017-10-12 09:49:09 +0200107
Christopher Faulet94b71232017-10-12 09:49:09 +0200108 /* release the lock and update the time in case of rotate. */
Willy Tarreau0d6c75d2019-05-25 19:54:40 +0200109 _HA_ATOMIC_STORE(&ctr->curr_tick, curr_tick);
110
111 return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200112}
113
Willy Tarreau7f062c42009-03-05 18:43:00 +0100114/* Read a frequency counter taking history into account for missing time in
115 * current period.
116 */
117unsigned int read_freq_ctr(struct freq_ctr *ctr);
118
Willy Tarreau79584222009-03-06 09:18:27 +0100119/* 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 */
123unsigned 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 */
131unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend);
132
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200133/* process freq counters over configurable periods */
134unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period);
135unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
136 unsigned int freq, unsigned int pend);
137
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200138/* 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
Willy Tarreau37585812016-11-25 11:55:10 +0100205 * 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
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200218 *
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.
Christopher Fauletaacd2fa2019-11-08 14:40:18 +0100251 * The sample is returned. Better if <n> is a power of two. This function is
252 * thread-safe.
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200253 */
254static inline unsigned int swrate_add(unsigned int *sum, unsigned int n, unsigned int v)
255{
Christopher Fauletaacd2fa2019-11-08 14:40:18 +0100256 unsigned int new_sum, old_sum;
257
258 old_sum = *sum;
259 do {
260 new_sum = old_sum - (old_sum + n - 1) / n + v;
261 } while (!_HA_ATOMIC_CAS(sum, &old_sum, new_sum));
262 return new_sum;
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200263}
264
Willy Tarreau627505d2018-10-17 09:24:56 +0200265/* Adds sample value <v> spanning <s> samples to sliding window sum <sum>
266 * configured for <n> samples, where <n> is supposed to be "much larger" than
267 * <s>. The sample is returned. Better if <n> is a power of two. Note that this
268 * is only an approximate. Indeed, as can be seen with two samples only over a
269 * 8-sample window, the original function would return :
270 * sum1 = sum - (sum + 7) / 8 + v
271 * sum2 = sum1 - (sum1 + 7) / 8 + v
272 * = (sum - (sum + 7) / 8 + v) - (sum - (sum + 7) / 8 + v + 7) / 8 + v
273 * ~= 7sum/8 - 7/8 + v - sum/8 + sum/64 - 7/64 - v/8 - 7/8 + v
274 * ~= (3sum/4 + sum/64) - (7/4 + 7/64) + 15v/8
275 *
276 * while the function below would return :
277 * sum = sum + 2*v - (sum + 8) * 2 / 8
278 * = 3sum/4 + 2v - 2
279 *
280 * this presents an error of ~ (sum/64 + 9/64 + v/8) = (sum+n+1)/(n^s) + v/n
281 *
282 * Thus the simplified function effectively replaces a part of the history with
283 * a linear sum instead of applying the exponential one. But as long as s/n is
284 * "small enough", the error fades away and remains small for both small and
Christopher Fauletaacd2fa2019-11-08 14:40:18 +0100285 * large values of n and s (typically < 0.2% measured). This function is
286 * thread-safe.
Willy Tarreau627505d2018-10-17 09:24:56 +0200287 */
288static inline unsigned int swrate_add_scaled(unsigned int *sum, unsigned int n, unsigned int v, unsigned int s)
289{
Christopher Fauletaacd2fa2019-11-08 14:40:18 +0100290 unsigned int new_sum, old_sum;
291
292 old_sum = *sum;
293 do {
294 new_sum = old_sum + v * s - div64_32((unsigned long long)(old_sum + n) * s, n);
295 } while (!_HA_ATOMIC_CAS(sum, &old_sum, new_sum));
296 return new_sum;
Willy Tarreau627505d2018-10-17 09:24:56 +0200297}
298
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200299/* Returns the average sample value for the sum <sum> over a sliding window of
300 * <n> samples. Better if <n> is a power of two. It must be the same <n> as the
301 * one used above in all additions.
302 */
303static inline unsigned int swrate_avg(unsigned int sum, unsigned int n)
304{
305 return (sum + n - 1) / n;
306}
307
Willy Tarreau7f062c42009-03-05 18:43:00 +0100308#endif /* _PROTO_FREQ_CTR_H */
309
310/*
311 * Local variables:
312 * c-indent-level: 8
313 * c-basic-offset: 8
314 * End:
315 */