blob: 42fbc1cea60cb27458121f3394a34d58a291a347 [file] [log] [blame]
Willy Tarreau7f062c42009-03-05 18:43:00 +01001/*
2 * Event rate calculation functions.
3 *
Willy Tarreau2970b0b2010-06-20 07:15:43 +02004 * Copyright 2000-2010 Willy Tarreau <w@1wt.eu>
Willy Tarreau7f062c42009-03-05 18:43:00 +01005 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 *
11 */
12
Willy Tarreau4c7e4b72020-05-27 12:58:42 +020013#include <haproxy/api.h>
Willy Tarreau66347942020-06-01 12:18:08 +020014#include <haproxy/freq_ctr.h>
Willy Tarreaub2551052020-06-09 09:07:15 +020015#include <haproxy/time.h>
16#include <haproxy/tools.h>
Willy Tarreau7f062c42009-03-05 18:43:00 +010017
18/* Read a frequency counter taking history into account for missing time in
19 * current period. Current second is sub-divided in 1000 chunks of one ms,
20 * and the missing ones are read proportionally from previous value. The
21 * return value has the same precision as one input data sample, so low rates
22 * will be inaccurate still appropriate for max checking. One trick we use for
23 * low values is to specially handle the case where the rate is between 0 and 1
24 * in order to avoid flapping while waiting for the next event.
Willy Tarreau79584222009-03-06 09:18:27 +010025 *
26 * For immediate limit checking, it's recommended to use freq_ctr_remain() and
27 * next_event_delay() instead which do not have the flapping correction, so
28 * that even frequencies as low as one event/period are properly handled.
Willy Tarreau7f062c42009-03-05 18:43:00 +010029 */
30unsigned int read_freq_ctr(struct freq_ctr *ctr)
31{
Emeric Brun6e012862017-10-30 18:04:28 +010032 unsigned int curr, past, _curr, _past;
33 unsigned int age, curr_sec, _curr_sec;
Willy Tarreau7f062c42009-03-05 18:43:00 +010034
Willy Tarreaua06a5802017-10-31 17:54:15 +010035 while (1) {
36 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020037 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010038 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020039 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010040 _curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020041 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +010042 if (_curr_sec & 0x80000000)
43 continue;
Willy Tarreaua06a5802017-10-31 17:54:15 +010044 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020045 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010046 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020047 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010048 curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020049 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +010050 if (_curr == curr && _past == past && _curr_sec == curr_sec)
51 break;
52 }
Christopher Faulet94b71232017-10-12 09:49:09 +020053
Willy Tarreaua1ecbca2021-03-17 19:10:23 +010054 age = (global_now >> 32) - curr_sec;
Willy Tarreau3d8c5532009-03-06 14:29:25 +010055 if (unlikely(age > 1))
56 return 0;
57
Christopher Faulet94b71232017-10-12 09:49:09 +020058 if (unlikely(age)) {
59 past = curr;
60 curr = 0;
Willy Tarreau3d8c5532009-03-06 14:29:25 +010061 }
Willy Tarreau7f062c42009-03-05 18:43:00 +010062
Willy Tarreau3d8c5532009-03-06 14:29:25 +010063 if (past <= 1 && !curr)
64 return past; /* very low rate, avoid flapping */
65
Willy Tarreaueab777c2012-12-29 21:50:07 +010066 return curr + mul32hi(past, ms_left_scaled);
Willy Tarreau7f062c42009-03-05 18:43:00 +010067}
68
Willy Tarreau79584222009-03-06 09:18:27 +010069/* returns the number of remaining events that can occur on this freq counter
70 * while respecting <freq> and taking into account that <pend> events are
71 * already known to be pending. Returns 0 if limit was reached.
72 */
73unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend)
74{
Emeric Brun6e012862017-10-30 18:04:28 +010075 unsigned int curr, past, _curr, _past;
76 unsigned int age, curr_sec, _curr_sec;
Willy Tarreau79584222009-03-06 09:18:27 +010077
Willy Tarreaua06a5802017-10-31 17:54:15 +010078 while (1) {
79 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020080 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010081 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020082 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010083 _curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020084 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +010085 if (_curr_sec & 0x80000000)
86 continue;
Willy Tarreaua06a5802017-10-31 17:54:15 +010087 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020088 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010089 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020090 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +010091 curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +020092 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +010093 if (_curr == curr && _past == past && _curr_sec == curr_sec)
94 break;
95 }
Willy Tarreau79584222009-03-06 09:18:27 +010096
Willy Tarreaua1ecbca2021-03-17 19:10:23 +010097 age = (global_now >> 32) - curr_sec;
Christopher Faulet94b71232017-10-12 09:49:09 +020098 if (unlikely(age > 1))
99 curr = 0;
100 else {
101 if (unlikely(age == 1)) {
102 past = curr;
103 curr = 0;
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100104 }
Willy Tarreaueab777c2012-12-29 21:50:07 +0100105 curr += mul32hi(past, ms_left_scaled);
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100106 }
107 curr += pend;
108
109 if (curr >= freq)
Willy Tarreau79584222009-03-06 09:18:27 +0100110 return 0;
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100111 return freq - curr;
Willy Tarreau79584222009-03-06 09:18:27 +0100112}
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{
Emeric Brun6e012862017-10-30 18:04:28 +0100122 unsigned int curr, past, _curr, _past;
123 unsigned int wait, age, curr_sec, _curr_sec;
Willy Tarreau79584222009-03-06 09:18:27 +0100124
Willy Tarreaua06a5802017-10-31 17:54:15 +0100125 while (1) {
126 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200127 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +0100128 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200129 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +0100130 _curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200131 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100132 if (_curr_sec & 0x80000000)
133 continue;
Willy Tarreaua06a5802017-10-31 17:54:15 +0100134 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200135 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +0100136 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200137 __ha_compiler_barrier();
Willy Tarreaua06a5802017-10-31 17:54:15 +0100138 curr_sec = ctr->curr_sec;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200139 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100140 if (_curr == curr && _past == past && _curr_sec == curr_sec)
141 break;
142 }
Willy Tarreau79584222009-03-06 09:18:27 +0100143
Willy Tarreaua1ecbca2021-03-17 19:10:23 +0100144 age = (global_now >> 32) - curr_sec;
Christopher Faulet94b71232017-10-12 09:49:09 +0200145 if (unlikely(age > 1))
146 curr = 0;
147 else {
148 if (unlikely(age == 1)) {
149 past = curr;
150 curr = 0;
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100151 }
Willy Tarreaueab777c2012-12-29 21:50:07 +0100152 curr += mul32hi(past, ms_left_scaled);
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100153 }
154 curr += pend;
Willy Tarreau79584222009-03-06 09:18:27 +0100155
Willy Tarreau3d8c5532009-03-06 14:29:25 +0100156 if (curr < freq)
Willy Tarreau79584222009-03-06 09:18:27 +0100157 return 0;
158
Willy Tarreaue4d247e2021-02-09 17:39:08 +0100159 /* too many events already, let's count how long to wait before they're
160 * processed. For this we'll subtract from the number of pending events
161 * the ones programmed for the current period, to know how long to wait
162 * for the next period. Each event takes 1/freq sec, thus 1000/freq ms.
163 */
164 curr -= freq;
165 wait = curr * 1000 / (freq ? freq : 1);
Willy Tarreau79584222009-03-06 09:18:27 +0100166 return MAX(wait, 1);
167}
168
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200169/* Reads a frequency counter taking history into account for missing time in
170 * current period. The period has to be passed in number of ticks and must
171 * match the one used to feed the counter. The counter value is reported for
Willy Tarreaua1ecbca2021-03-17 19:10:23 +0100172 * current global date. The return value has the same precision as one input
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200173 * data sample, so low rates over the period will be inaccurate but still
174 * appropriate for max checking. One trick we use for low values is to specially
175 * handle the case where the rate is between 0 and 1 in order to avoid flapping
176 * while waiting for the next event.
177 *
178 * For immediate limit checking, it's recommended to use freq_ctr_period_remain()
179 * instead which does not have the flapping correction, so that even frequencies
180 * as low as one event/period are properly handled.
181 *
182 * For measures over a 1-second period, it's better to use the implicit functions
183 * above.
184 */
185unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period)
186{
Emeric Brun6e012862017-10-30 18:04:28 +0100187 unsigned int _curr, _past, curr, past;
188 unsigned int remain, _curr_tick, curr_tick;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200189
Willy Tarreaua06a5802017-10-31 17:54:15 +0100190 while (1) {
Emeric Brun6e012862017-10-30 18:04:28 +0100191 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200192 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100193 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200194 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100195 _curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200196 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100197 if (_curr_tick & 0x1)
198 continue;
Christopher Faulet94b71232017-10-12 09:49:09 +0200199 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200200 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200201 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200202 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200203 curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200204 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100205 if (_curr == curr && _past == past && _curr_tick == curr_tick)
206 break;
207 };
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200208
Willy Tarreau8cc586c2021-03-23 08:58:22 +0100209 remain = curr_tick + period - global_now_ms;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200210 if (unlikely((int)remain < 0)) {
211 /* We're past the first period, check if we can still report a
212 * part of last period or if we're too far away.
213 */
214 remain += period;
215 if ((int)remain < 0)
216 return 0;
217 past = curr;
218 curr = 0;
219 }
220 if (past <= 1 && !curr)
221 return past; /* very low rate, avoid flapping */
222
223 curr += div64_32((unsigned long long)past * remain, period);
224 return curr;
225}
226
227/* Returns the number of remaining events that can occur on this freq counter
228 * while respecting <freq> events per period, and taking into account that
229 * <pend> events are already known to be pending. Returns 0 if limit was reached.
230 */
231unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
232 unsigned int freq, unsigned int pend)
233{
Emeric Brun6e012862017-10-30 18:04:28 +0100234 unsigned int _curr, _past, curr, past;
235 unsigned int remain, _curr_tick, curr_tick;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200236
Willy Tarreaua06a5802017-10-31 17:54:15 +0100237 while (1) {
Emeric Brun6e012862017-10-30 18:04:28 +0100238 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200239 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100240 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200241 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100242 _curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200243 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100244 if (_curr_tick & 0x1)
245 continue;
Christopher Faulet94b71232017-10-12 09:49:09 +0200246 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200247 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200248 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200249 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200250 curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200251 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100252 if (_curr == curr && _past == past && _curr_tick == curr_tick)
253 break;
254 };
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200255
Willy Tarreau8cc586c2021-03-23 08:58:22 +0100256 remain = curr_tick + period - global_now_ms;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200257 if (likely((int)remain < 0)) {
258 /* We're past the first period, check if we can still report a
259 * part of last period or if we're too far away.
260 */
261 past = curr;
262 curr = 0;
263 remain += period;
264 if ((int)remain < 0)
265 past = 0;
266 }
267 if (likely(past))
268 curr += div64_32((unsigned long long)past * remain, period);
269
270 curr += pend;
271 freq -= curr;
272 if ((int)freq < 0)
273 freq = 0;
274 return freq;
275}
276
Willy Tarreau7f062c42009-03-05 18:43:00 +0100277
278/*
279 * Local variables:
280 * c-indent-level: 8
281 * c-basic-offset: 8
282 * End:
283 */