Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Event rate calculation functions. |
| 3 | * |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 4 | * Copyright 2000-2010 Willy Tarreau <w@1wt.eu> |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 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 <common/config.h> |
| 14 | #include <common/standard.h> |
| 15 | #include <common/time.h> |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 16 | #include <common/tools.h> |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 17 | #include <proto/freq_ctr.h> |
| 18 | |
| 19 | /* Read a frequency counter taking history into account for missing time in |
| 20 | * current period. Current second is sub-divided in 1000 chunks of one ms, |
| 21 | * and the missing ones are read proportionally from previous value. The |
| 22 | * return value has the same precision as one input data sample, so low rates |
| 23 | * will be inaccurate still appropriate for max checking. One trick we use for |
| 24 | * low values is to specially handle the case where the rate is between 0 and 1 |
| 25 | * in order to avoid flapping while waiting for the next event. |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 26 | * |
| 27 | * For immediate limit checking, it's recommended to use freq_ctr_remain() and |
| 28 | * next_event_delay() instead which do not have the flapping correction, so |
| 29 | * that even frequencies as low as one event/period are properly handled. |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 30 | */ |
| 31 | unsigned int read_freq_ctr(struct freq_ctr *ctr) |
| 32 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 33 | unsigned int curr, past, _curr, _past; |
| 34 | unsigned int age, curr_sec, _curr_sec; |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 35 | |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 36 | while(1) { |
| 37 | _curr = (volatile unsigned int)ctr->curr_ctr; |
| 38 | _past = (volatile unsigned int)ctr->prev_ctr; |
| 39 | _curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 40 | if (_curr_sec & 0x80000000) |
| 41 | continue; |
| 42 | curr = (volatile unsigned int)ctr->curr_ctr; |
| 43 | past = (volatile unsigned int)ctr->prev_ctr; |
| 44 | curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 45 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 46 | break; |
| 47 | } |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 48 | |
| 49 | age = now.tv_sec - curr_sec; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 50 | if (unlikely(age > 1)) |
| 51 | return 0; |
| 52 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 53 | if (unlikely(age)) { |
| 54 | past = curr; |
| 55 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 56 | } |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 57 | |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 58 | if (past <= 1 && !curr) |
| 59 | return past; /* very low rate, avoid flapping */ |
| 60 | |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 61 | return curr + mul32hi(past, ms_left_scaled); |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 62 | } |
| 63 | |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 64 | /* returns the number of remaining events that can occur on this freq counter |
| 65 | * while respecting <freq> and taking into account that <pend> events are |
| 66 | * already known to be pending. Returns 0 if limit was reached. |
| 67 | */ |
| 68 | unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend) |
| 69 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 70 | unsigned int curr, past, _curr, _past; |
| 71 | unsigned int age, curr_sec, _curr_sec; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 72 | |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 73 | while(1) { |
| 74 | _curr = (volatile unsigned int)ctr->curr_ctr; |
| 75 | _past = (volatile unsigned int)ctr->prev_ctr; |
| 76 | _curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 77 | if (_curr_sec & 0x80000000) |
| 78 | continue; |
| 79 | curr = (volatile unsigned int)ctr->curr_ctr; |
| 80 | past = (volatile unsigned int)ctr->prev_ctr; |
| 81 | curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 82 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 83 | break; |
| 84 | } |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 85 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 86 | age = now.tv_sec - curr_sec; |
| 87 | if (unlikely(age > 1)) |
| 88 | curr = 0; |
| 89 | else { |
| 90 | if (unlikely(age == 1)) { |
| 91 | past = curr; |
| 92 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 93 | } |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 94 | curr += mul32hi(past, ms_left_scaled); |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 95 | } |
| 96 | curr += pend; |
| 97 | |
| 98 | if (curr >= freq) |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 99 | return 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 100 | return freq - curr; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 101 | } |
| 102 | |
| 103 | /* return the expected wait time in ms before the next event may occur, |
| 104 | * respecting frequency <freq>, and assuming there may already be some pending |
| 105 | * events. It returns zero if we can proceed immediately, otherwise the wait |
| 106 | * time, which will be rounded down 1ms for better accuracy, with a minimum |
| 107 | * of one ms. |
| 108 | */ |
| 109 | unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend) |
| 110 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 111 | unsigned int curr, past, _curr, _past; |
| 112 | unsigned int wait, age, curr_sec, _curr_sec; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 113 | |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 114 | while(1) { |
| 115 | _curr = (volatile unsigned int)ctr->curr_ctr; |
| 116 | _past = (volatile unsigned int)ctr->prev_ctr; |
| 117 | _curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 118 | if (_curr_sec & 0x80000000) |
| 119 | continue; |
| 120 | curr = (volatile unsigned int)ctr->curr_ctr; |
| 121 | past = (volatile unsigned int)ctr->prev_ctr; |
| 122 | curr_sec = (volatile unsigned int)ctr->curr_sec; |
| 123 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 124 | break; |
| 125 | } |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 126 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 127 | age = now.tv_sec - curr_sec; |
| 128 | if (unlikely(age > 1)) |
| 129 | curr = 0; |
| 130 | else { |
| 131 | if (unlikely(age == 1)) { |
| 132 | past = curr; |
| 133 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 134 | } |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 135 | curr += mul32hi(past, ms_left_scaled); |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 136 | } |
| 137 | curr += pend; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 138 | |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 139 | if (curr < freq) |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 140 | return 0; |
| 141 | |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 142 | wait = 999 / curr; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 143 | return MAX(wait, 1); |
| 144 | } |
| 145 | |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 146 | /* Reads a frequency counter taking history into account for missing time in |
| 147 | * current period. The period has to be passed in number of ticks and must |
| 148 | * match the one used to feed the counter. The counter value is reported for |
| 149 | * current date (now_ms). The return value has the same precision as one input |
| 150 | * data sample, so low rates over the period will be inaccurate but still |
| 151 | * appropriate for max checking. One trick we use for low values is to specially |
| 152 | * handle the case where the rate is between 0 and 1 in order to avoid flapping |
| 153 | * while waiting for the next event. |
| 154 | * |
| 155 | * For immediate limit checking, it's recommended to use freq_ctr_period_remain() |
| 156 | * instead which does not have the flapping correction, so that even frequencies |
| 157 | * as low as one event/period are properly handled. |
| 158 | * |
| 159 | * For measures over a 1-second period, it's better to use the implicit functions |
| 160 | * above. |
| 161 | */ |
| 162 | unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period) |
| 163 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 164 | unsigned int _curr, _past, curr, past; |
| 165 | unsigned int remain, _curr_tick, curr_tick; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 166 | |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 167 | while(1) { |
| 168 | _curr = ctr->curr_ctr; |
| 169 | _past = ctr->prev_ctr; |
| 170 | _curr_tick = ctr->curr_tick; |
| 171 | if (_curr_tick & 0x1) |
| 172 | continue; |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 173 | curr = ctr->curr_ctr; |
| 174 | past = ctr->prev_ctr; |
| 175 | curr_tick = ctr->curr_tick; |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 176 | if (_curr == curr && _past == past && _curr_tick == curr_tick) |
| 177 | break; |
| 178 | }; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 179 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 180 | remain = curr_tick + period - now_ms; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 181 | if (unlikely((int)remain < 0)) { |
| 182 | /* We're past the first period, check if we can still report a |
| 183 | * part of last period or if we're too far away. |
| 184 | */ |
| 185 | remain += period; |
| 186 | if ((int)remain < 0) |
| 187 | return 0; |
| 188 | past = curr; |
| 189 | curr = 0; |
| 190 | } |
| 191 | if (past <= 1 && !curr) |
| 192 | return past; /* very low rate, avoid flapping */ |
| 193 | |
| 194 | curr += div64_32((unsigned long long)past * remain, period); |
| 195 | return curr; |
| 196 | } |
| 197 | |
| 198 | /* Returns the number of remaining events that can occur on this freq counter |
| 199 | * while respecting <freq> events per period, and taking into account that |
| 200 | * <pend> events are already known to be pending. Returns 0 if limit was reached. |
| 201 | */ |
| 202 | unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period, |
| 203 | unsigned int freq, unsigned int pend) |
| 204 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 205 | unsigned int _curr, _past, curr, past; |
| 206 | unsigned int remain, _curr_tick, curr_tick; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 207 | |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 208 | while(1) { |
| 209 | _curr = ctr->curr_ctr; |
| 210 | _past = ctr->prev_ctr; |
| 211 | _curr_tick = ctr->curr_tick; |
| 212 | if (_curr_tick & 0x1) |
| 213 | continue; |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 214 | curr = ctr->curr_ctr; |
| 215 | past = ctr->prev_ctr; |
| 216 | curr_tick = ctr->curr_tick; |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame^] | 217 | if (_curr == curr && _past == past && _curr_tick == curr_tick) |
| 218 | break; |
| 219 | }; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 220 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 221 | remain = curr_tick + period - now_ms; |
Willy Tarreau | 2970b0b | 2010-06-20 07:15:43 +0200 | [diff] [blame] | 222 | if (likely((int)remain < 0)) { |
| 223 | /* We're past the first period, check if we can still report a |
| 224 | * part of last period or if we're too far away. |
| 225 | */ |
| 226 | past = curr; |
| 227 | curr = 0; |
| 228 | remain += period; |
| 229 | if ((int)remain < 0) |
| 230 | past = 0; |
| 231 | } |
| 232 | if (likely(past)) |
| 233 | curr += div64_32((unsigned long long)past * remain, period); |
| 234 | |
| 235 | curr += pend; |
| 236 | freq -= curr; |
| 237 | if ((int)freq < 0) |
| 238 | freq = 0; |
| 239 | return freq; |
| 240 | } |
| 241 | |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 242 | |
| 243 | /* |
| 244 | * Local variables: |
| 245 | * c-indent-level: 8 |
| 246 | * c-basic-offset: 8 |
| 247 | * End: |
| 248 | */ |