blob: c10ddf2aa85bc27b133c15aff4156dc0a9e41625 [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 tot_inc;
39 unsigned int curr_sec;
40
41 do {
42 /* remove the bit, used for the lock */
43 curr_sec = ctr->curr_sec & 0x7fffffff;
Willy Tarreau7f062c42009-03-05 18:43:00 +010044 }
Emeric Brun6e012862017-10-30 18:04:28 +010045 while (!HA_ATOMIC_CAS(&ctr->curr_sec, &curr_sec, curr_sec | 0x80000000));
Willy Tarreau7f062c42009-03-05 18:43:00 +010046
Christopher Faulet94b71232017-10-12 09:49:09 +020047 elapsed = (now.tv_sec & 0x7fffffff)- curr_sec;
Emeric Brun6e012862017-10-30 18:04:28 +010048 if (unlikely(elapsed > 0)) {
Christopher Faulet94b71232017-10-12 09:49:09 +020049 ctr->prev_ctr = ctr->curr_ctr;
50 ctr->curr_ctr = 0;
51 if (likely(elapsed != 1)) {
52 /* we missed more than one second */
53 ctr->prev_ctr = 0;
54 }
Emeric Brun6e012862017-10-30 18:04:28 +010055 curr_sec = now.tv_sec;
Willy Tarreau2970b0b2010-06-20 07:15:43 +020056 }
Christopher Faulet94b71232017-10-12 09:49:09 +020057
58 ctr->curr_ctr += inc;
59 tot_inc = ctr->curr_ctr;
60
61 /* release the lock and update the time in case of rotate. */
Emeric Brun6e012862017-10-30 18:04:28 +010062 HA_ATOMIC_STORE(&ctr->curr_sec, curr_sec & 0x7fffffff);
Christopher Faulet94b71232017-10-12 09:49:09 +020063 return tot_inc;
64 /* Note: later we may want to propagate the update to other counters */
Willy Tarreau2970b0b2010-06-20 07:15:43 +020065}
66
67/* Update a frequency counter by <inc> incremental units. It is automatically
68 * rotated if the period is over. It is important that it correctly initializes
69 * a null area. This one works on frequency counters which have a period
70 * different from one second.
71 */
Christopher Fauletde2075f2017-09-01 12:18:36 +020072static inline unsigned int update_freq_ctr_period(struct freq_ctr_period *ctr,
73 unsigned int period, unsigned int inc)
Willy Tarreau2970b0b2010-06-20 07:15:43 +020074{
Christopher Faulet94b71232017-10-12 09:49:09 +020075 unsigned int tot_inc;
76 unsigned int curr_tick;
77
78 do {
79 /* remove the bit, used for the lock */
80 curr_tick = (ctr->curr_tick >> 1) << 1;
81 }
82 while (!HA_ATOMIC_CAS(&ctr->curr_tick, &curr_tick, curr_tick | 0x1));
83
84 if (now_ms - curr_tick >= period) {
85 ctr->prev_ctr = ctr->curr_ctr;
86 ctr->curr_ctr = 0;
87 curr_tick += period;
88 if (likely(now_ms - curr_tick >= period)) {
89 /* we missed at least two periods */
90 ctr->prev_ctr = 0;
91 curr_tick = now_ms;
92 }
Willy Tarreau2970b0b2010-06-20 07:15:43 +020093 }
Christopher Faulet94b71232017-10-12 09:49:09 +020094
95 ctr->curr_ctr += inc;
96 tot_inc = ctr->curr_ctr;
97 /* release the lock and update the time in case of rotate. */
98 HA_ATOMIC_STORE(&ctr->curr_tick, (curr_tick >> 1) << 1);
99 return tot_inc;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200100 /* Note: later we may want to propagate the update to other counters */
101}
102
Willy Tarreau7f062c42009-03-05 18:43:00 +0100103/* Read a frequency counter taking history into account for missing time in
104 * current period.
105 */
106unsigned int read_freq_ctr(struct freq_ctr *ctr);
107
Willy Tarreau79584222009-03-06 09:18:27 +0100108/* returns the number of remaining events that can occur on this freq counter
109 * while respecting <freq> and taking into account that <pend> events are
110 * already known to be pending. Returns 0 if limit was reached.
111 */
112unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend);
113
114/* return the expected wait time in ms before the next event may occur,
115 * respecting frequency <freq>, and assuming there may already be some pending
116 * events. It returns zero if we can proceed immediately, otherwise the wait
117 * time, which will be rounded down 1ms for better accuracy, with a minimum
118 * of one ms.
119 */
120unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend);
121
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200122/* process freq counters over configurable periods */
123unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period);
124unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
125 unsigned int freq, unsigned int pend);
126
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200127/* While the functions above report average event counts per period, we are
128 * also interested in average values per event. For this we use a different
129 * method. The principle is to rely on a long tail which sums the new value
130 * with a fraction of the previous value, resulting in a sliding window of
131 * infinite length depending on the precision we're interested in.
132 *
133 * The idea is that we always keep (N-1)/N of the sum and add the new sampled
134 * value. The sum over N values can be computed with a simple program for a
135 * constant value 1 at each iteration :
136 *
137 * N
138 * ,---
139 * \ N - 1 e - 1
140 * > ( --------- )^x ~= N * -----
141 * / N e
142 * '---
143 * x = 1
144 *
145 * Note: I'm not sure how to demonstrate this but at least this is easily
146 * verified with a simple program, the sum equals N * 0.632120 for any N
147 * moderately large (tens to hundreds).
148 *
149 * Inserting a constant sample value V here simply results in :
150 *
151 * sum = V * N * (e - 1) / e
152 *
153 * But we don't want to integrate over a small period, but infinitely. Let's
154 * cut the infinity in P periods of N values. Each period M is exactly the same
155 * as period M-1 with a factor of ((N-1)/N)^N applied. A test shows that given a
156 * large N :
157 *
158 * N - 1 1
159 * ( ------- )^N ~= ---
160 * N e
161 *
162 * Our sum is now a sum of each factor times :
163 *
164 * N*P P
165 * ,--- ,---
166 * \ N - 1 e - 1 \ 1
167 * > v ( --------- )^x ~= VN * ----- * > ---
168 * / N e / e^x
169 * '--- '---
170 * x = 1 x = 0
171 *
172 * For P "large enough", in tests we get this :
173 *
174 * P
175 * ,---
176 * \ 1 e
177 * > --- ~= -----
178 * / e^x e - 1
179 * '---
180 * x = 0
181 *
182 * This simplifies the sum above :
183 *
184 * N*P
185 * ,---
186 * \ N - 1
187 * > v ( --------- )^x = VN
188 * / N
189 * '---
190 * x = 1
191 *
192 * So basically by summing values and applying the last result an (N-1)/N factor
193 * we just get N times the values over the long term, so we can recover the
Willy Tarreau37585812016-11-25 11:55:10 +0100194 * constant value V by dividing by N. In order to limit the impact of integer
195 * overflows, we'll use this equivalence which saves us one multiply :
196 *
197 * N - 1 1 x0
198 * x1 = x0 * ------- = x0 * ( 1 - --- ) = x0 - ----
199 * N N N
200 *
201 * And given that x0 is discrete here we'll have to saturate the values before
202 * performing the divide, so the value insertion will become :
203 *
204 * x0 + N - 1
205 * x1 = x0 - ------------
206 * N
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200207 *
208 * A value added at the entry of the sliding window of N values will thus be
209 * reduced to 1/e or 36.7% after N terms have been added. After a second batch,
210 * it will only be 1/e^2, or 13.5%, and so on. So practically speaking, each
211 * old period of N values represents only a quickly fading ratio of the global
212 * sum :
213 *
214 * period ratio
215 * 1 36.7%
216 * 2 13.5%
217 * 3 4.98%
218 * 4 1.83%
219 * 5 0.67%
220 * 6 0.25%
221 * 7 0.09%
222 * 8 0.033%
223 * 9 0.012%
224 * 10 0.0045%
225 *
226 * So after 10N samples, the initial value has already faded out by a factor of
227 * 22026, which is quite fast. If the sliding window is 1024 samples wide, it
228 * means that a sample will only count for 1/22k of its initial value after 10k
229 * samples went after it, which results in half of the value it would represent
230 * using an arithmetic mean. The benefit of this method is that it's very cheap
231 * in terms of computations when N is a power of two. This is very well suited
232 * to record response times as large values will fade out faster than with an
233 * arithmetic mean and will depend on sample count and not time.
234 *
235 * Demonstrating all the above assumptions with maths instead of a program is
236 * left as an exercise for the reader.
237 */
238
239/* Adds sample value <v> to sliding window sum <sum> configured for <n> samples.
240 * The sample is returned. Better if <n> is a power of two.
241 */
242static inline unsigned int swrate_add(unsigned int *sum, unsigned int n, unsigned int v)
243{
Willy Tarreau37585812016-11-25 11:55:10 +0100244 return *sum = *sum - (*sum + n - 1) / n + v;
Willy Tarreau2438f2b2014-06-16 20:24:22 +0200245}
246
247/* Returns the average sample value for the sum <sum> over a sliding window of
248 * <n> samples. Better if <n> is a power of two. It must be the same <n> as the
249 * one used above in all additions.
250 */
251static inline unsigned int swrate_avg(unsigned int sum, unsigned int n)
252{
253 return (sum + n - 1) / n;
254}
255
Willy Tarreau7f062c42009-03-05 18:43:00 +0100256#endif /* _PROTO_FREQ_CTR_H */
257
258/*
259 * Local variables:
260 * c-indent-level: 8
261 * c-basic-offset: 8
262 * End:
263 */