blob: 1b84d9fe40991ff143f765ad9005ac9325bfae52 [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 Tarreau47131762021-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 Tarreau47131762021-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 Tarreau47131762021-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 Tarreau3d8c5532009-03-06 14:29:25 +0100159 wait = 999 / curr;
Willy Tarreau79584222009-03-06 09:18:27 +0100160 return MAX(wait, 1);
161}
162
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200163/* Reads a frequency counter taking history into account for missing time in
164 * current period. The period has to be passed in number of ticks and must
165 * match the one used to feed the counter. The counter value is reported for
Willy Tarreau47131762021-03-17 19:10:23 +0100166 * current global date. The return value has the same precision as one input
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200167 * data sample, so low rates over the period will be inaccurate but still
168 * appropriate for max checking. One trick we use for low values is to specially
169 * handle the case where the rate is between 0 and 1 in order to avoid flapping
170 * while waiting for the next event.
171 *
172 * For immediate limit checking, it's recommended to use freq_ctr_period_remain()
173 * instead which does not have the flapping correction, so that even frequencies
174 * as low as one event/period are properly handled.
175 *
176 * For measures over a 1-second period, it's better to use the implicit functions
177 * above.
178 */
179unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period)
180{
Emeric Brun6e012862017-10-30 18:04:28 +0100181 unsigned int _curr, _past, curr, past;
182 unsigned int remain, _curr_tick, curr_tick;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200183
Willy Tarreaua06a5802017-10-31 17:54:15 +0100184 while (1) {
Emeric Brun6e012862017-10-30 18:04:28 +0100185 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200186 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100187 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200188 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100189 _curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200190 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100191 if (_curr_tick & 0x1)
192 continue;
Christopher Faulet94b71232017-10-12 09:49:09 +0200193 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200194 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200195 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200196 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200197 curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200198 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100199 if (_curr == curr && _past == past && _curr_tick == curr_tick)
200 break;
201 };
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200202
Willy Tarreau049602f2021-03-23 08:58:22 +0100203 remain = curr_tick + period - global_now_ms;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200204 if (unlikely((int)remain < 0)) {
205 /* We're past the first period, check if we can still report a
206 * part of last period or if we're too far away.
207 */
208 remain += period;
209 if ((int)remain < 0)
210 return 0;
211 past = curr;
212 curr = 0;
213 }
214 if (past <= 1 && !curr)
215 return past; /* very low rate, avoid flapping */
216
217 curr += div64_32((unsigned long long)past * remain, period);
218 return curr;
219}
220
221/* Returns the number of remaining events that can occur on this freq counter
222 * while respecting <freq> events per period, and taking into account that
223 * <pend> events are already known to be pending. Returns 0 if limit was reached.
224 */
225unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
226 unsigned int freq, unsigned int pend)
227{
Emeric Brun6e012862017-10-30 18:04:28 +0100228 unsigned int _curr, _past, curr, past;
229 unsigned int remain, _curr_tick, curr_tick;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200230
Willy Tarreaua06a5802017-10-31 17:54:15 +0100231 while (1) {
Emeric Brun6e012862017-10-30 18:04:28 +0100232 _curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200233 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100234 _past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200235 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100236 _curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200237 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100238 if (_curr_tick & 0x1)
239 continue;
Christopher Faulet94b71232017-10-12 09:49:09 +0200240 curr = ctr->curr_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200241 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200242 past = ctr->prev_ctr;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200243 __ha_compiler_barrier();
Christopher Faulet94b71232017-10-12 09:49:09 +0200244 curr_tick = ctr->curr_tick;
Willy Tarreau9453ecd2020-05-28 15:29:33 +0200245 __ha_compiler_barrier();
Emeric Brun6e012862017-10-30 18:04:28 +0100246 if (_curr == curr && _past == past && _curr_tick == curr_tick)
247 break;
248 };
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200249
Willy Tarreau049602f2021-03-23 08:58:22 +0100250 remain = curr_tick + period - global_now_ms;
Willy Tarreau2970b0b2010-06-20 07:15:43 +0200251 if (likely((int)remain < 0)) {
252 /* We're past the first period, check if we can still report a
253 * part of last period or if we're too far away.
254 */
255 past = curr;
256 curr = 0;
257 remain += period;
258 if ((int)remain < 0)
259 past = 0;
260 }
261 if (likely(past))
262 curr += div64_32((unsigned long long)past * remain, period);
263
264 curr += pend;
265 freq -= curr;
266 if ((int)freq < 0)
267 freq = 0;
268 return freq;
269}
270
Willy Tarreau7f062c42009-03-05 18:43:00 +0100271
272/*
273 * Local variables:
274 * c-indent-level: 8
275 * c-basic-offset: 8
276 * End:
277 */