1 /*
2 * Event rate calculation functions.
3 *
4 * Copyright 2000-2010 Willy Tarreau <w@1wt.eu>
5 *
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
13 #include <haproxy/api.h>
14 #include <haproxy/freq_ctr.h>
15 #include <haproxy/time.h>
16 #include <haproxy/tools.h>
17
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.
25 *
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.
29 */
read_freq_ctr(struct freq_ctr * ctr)30 unsigned int read_freq_ctr(struct freq_ctr *ctr)
31 {
32 unsigned int curr, past, _curr, _past;
33 unsigned int age, curr_sec, _curr_sec;
34
35 while (1) {
36 _curr = ctr->curr_ctr;
37 __ha_compiler_barrier();
38 _past = ctr->prev_ctr;
39 __ha_compiler_barrier();
40 _curr_sec = ctr->curr_sec;
41 __ha_compiler_barrier();
42 if (_curr_sec & 0x80000000)
43 continue;
44 curr = ctr->curr_ctr;
45 __ha_compiler_barrier();
46 past = ctr->prev_ctr;
47 __ha_compiler_barrier();
48 curr_sec = ctr->curr_sec;
49 __ha_compiler_barrier();
50 if (_curr == curr && _past == past && _curr_sec == curr_sec)
51 break;
52 }
53
54 age = (global_now >> 32) - curr_sec;
55 if (unlikely(age > 1))
56 return 0;
57
58 if (unlikely(age)) {
59 past = curr;
60 curr = 0;
61 }
62
63 if (past <= 1 && !curr)
64 return past; /* very low rate, avoid flapping */
65
66 return curr + mul32hi(past, ms_left_scaled);
67 }
68
69 /* 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 */
freq_ctr_remain(struct freq_ctr * ctr,unsigned int freq,unsigned int pend)73 unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend)
74 {
75 unsigned int curr, past, _curr, _past;
76 unsigned int age, curr_sec, _curr_sec;
77
78 while (1) {
79 _curr = ctr->curr_ctr;
80 __ha_compiler_barrier();
81 _past = ctr->prev_ctr;
82 __ha_compiler_barrier();
83 _curr_sec = ctr->curr_sec;
84 __ha_compiler_barrier();
85 if (_curr_sec & 0x80000000)
86 continue;
87 curr = ctr->curr_ctr;
88 __ha_compiler_barrier();
89 past = ctr->prev_ctr;
90 __ha_compiler_barrier();
91 curr_sec = ctr->curr_sec;
92 __ha_compiler_barrier();
93 if (_curr == curr && _past == past && _curr_sec == curr_sec)
94 break;
95 }
96
97 age = (global_now >> 32) - curr_sec;
98 if (unlikely(age > 1))
99 curr = 0;
100 else {
101 if (unlikely(age == 1)) {
102 past = curr;
103 curr = 0;
104 }
105 curr += mul32hi(past, ms_left_scaled);
106 }
107 curr += pend;
108
109 if (curr >= freq)
110 return 0;
111 return freq - curr;
112 }
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 */
next_event_delay(struct freq_ctr * ctr,unsigned int freq,unsigned int pend)120 unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend)
121 {
122 unsigned int curr, past, _curr, _past;
123 unsigned int wait, age, curr_sec, _curr_sec;
124
125 while (1) {
126 _curr = ctr->curr_ctr;
127 __ha_compiler_barrier();
128 _past = ctr->prev_ctr;
129 __ha_compiler_barrier();
130 _curr_sec = ctr->curr_sec;
131 __ha_compiler_barrier();
132 if (_curr_sec & 0x80000000)
133 continue;
134 curr = ctr->curr_ctr;
135 __ha_compiler_barrier();
136 past = ctr->prev_ctr;
137 __ha_compiler_barrier();
138 curr_sec = ctr->curr_sec;
139 __ha_compiler_barrier();
140 if (_curr == curr && _past == past && _curr_sec == curr_sec)
141 break;
142 }
143
144 age = (global_now >> 32) - curr_sec;
145 if (unlikely(age > 1))
146 curr = 0;
147 else {
148 if (unlikely(age == 1)) {
149 past = curr;
150 curr = 0;
151 }
152 curr += mul32hi(past, ms_left_scaled);
153 }
154 curr += pend;
155
156 if (curr < freq)
157 return 0;
158
159 wait = 999 / curr;
160 return MAX(wait, 1);
161 }
162
163 /* 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
166 * current global date. The return value has the same precision as one input
167 * 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 */
read_freq_ctr_period(struct freq_ctr_period * ctr,unsigned int period)179 unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period)
180 {
181 unsigned int _curr, _past, curr, past;
182 unsigned int remain, _curr_tick, curr_tick;
183
184 while (1) {
185 _curr = ctr->curr_ctr;
186 __ha_compiler_barrier();
187 _past = ctr->prev_ctr;
188 __ha_compiler_barrier();
189 _curr_tick = ctr->curr_tick;
190 __ha_compiler_barrier();
191 if (_curr_tick & 0x1)
192 continue;
193 curr = ctr->curr_ctr;
194 __ha_compiler_barrier();
195 past = ctr->prev_ctr;
196 __ha_compiler_barrier();
197 curr_tick = ctr->curr_tick;
198 __ha_compiler_barrier();
199 if (_curr == curr && _past == past && _curr_tick == curr_tick)
200 break;
201 };
202
203 remain = curr_tick + period - global_now_ms;
204 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 */
freq_ctr_remain_period(struct freq_ctr_period * ctr,unsigned int period,unsigned int freq,unsigned int pend)225 unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
226 unsigned int freq, unsigned int pend)
227 {
228 unsigned int _curr, _past, curr, past;
229 unsigned int remain, _curr_tick, curr_tick;
230
231 while (1) {
232 _curr = ctr->curr_ctr;
233 __ha_compiler_barrier();
234 _past = ctr->prev_ctr;
235 __ha_compiler_barrier();
236 _curr_tick = ctr->curr_tick;
237 __ha_compiler_barrier();
238 if (_curr_tick & 0x1)
239 continue;
240 curr = ctr->curr_ctr;
241 __ha_compiler_barrier();
242 past = ctr->prev_ctr;
243 __ha_compiler_barrier();
244 curr_tick = ctr->curr_tick;
245 __ha_compiler_barrier();
246 if (_curr == curr && _past == past && _curr_tick == curr_tick)
247 break;
248 };
249
250 remain = curr_tick + period - global_now_ms;
251 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
271
272 /*
273 * Local variables:
274 * c-indent-level: 8
275 * c-basic-offset: 8
276 * End:
277 */
278