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 | |
Willy Tarreau | 4c7e4b7 | 2020-05-27 12:58:42 +0200 | [diff] [blame] | 13 | #include <haproxy/api.h> |
Willy Tarreau | 6634794 | 2020-06-01 12:18:08 +0200 | [diff] [blame] | 14 | #include <haproxy/freq_ctr.h> |
Willy Tarreau | b255105 | 2020-06-09 09:07:15 +0200 | [diff] [blame] | 15 | #include <haproxy/time.h> |
| 16 | #include <haproxy/tools.h> |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 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. |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 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. |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 29 | */ |
| 30 | unsigned int read_freq_ctr(struct freq_ctr *ctr) |
| 31 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 32 | unsigned int curr, past, _curr, _past; |
| 33 | unsigned int age, curr_sec, _curr_sec; |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 34 | |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 35 | while (1) { |
| 36 | _curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 37 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 38 | _past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 39 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 40 | _curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 41 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 42 | if (_curr_sec & 0x80000000) |
| 43 | continue; |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 44 | curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 45 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 46 | past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 47 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 48 | curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 49 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 50 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 51 | break; |
| 52 | } |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 53 | |
Willy Tarreau | a1ecbca | 2021-03-17 19:10:23 +0100 | [diff] [blame] | 54 | age = (global_now >> 32) - curr_sec; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 55 | if (unlikely(age > 1)) |
| 56 | return 0; |
| 57 | |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 58 | if (unlikely(age)) { |
| 59 | past = curr; |
| 60 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 61 | } |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 62 | |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 63 | if (past <= 1 && !curr) |
| 64 | return past; /* very low rate, avoid flapping */ |
| 65 | |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 66 | return curr + mul32hi(past, ms_left_scaled); |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 67 | } |
| 68 | |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 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 | */ |
| 73 | unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend) |
| 74 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 75 | unsigned int curr, past, _curr, _past; |
| 76 | unsigned int age, curr_sec, _curr_sec; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 77 | |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 78 | while (1) { |
| 79 | _curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 80 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 81 | _past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 82 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 83 | _curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 84 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 85 | if (_curr_sec & 0x80000000) |
| 86 | continue; |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 87 | curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 88 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 89 | past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 90 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 91 | curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 92 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 93 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 94 | break; |
| 95 | } |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 96 | |
Willy Tarreau | a1ecbca | 2021-03-17 19:10:23 +0100 | [diff] [blame] | 97 | age = (global_now >> 32) - curr_sec; |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 98 | if (unlikely(age > 1)) |
| 99 | curr = 0; |
| 100 | else { |
| 101 | if (unlikely(age == 1)) { |
| 102 | past = curr; |
| 103 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 104 | } |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 105 | curr += mul32hi(past, ms_left_scaled); |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 106 | } |
| 107 | curr += pend; |
| 108 | |
| 109 | if (curr >= freq) |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 110 | return 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 111 | return freq - curr; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 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 | */ |
| 120 | unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend) |
| 121 | { |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 122 | unsigned int curr, past, _curr, _past; |
| 123 | unsigned int wait, age, curr_sec, _curr_sec; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 124 | |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 125 | while (1) { |
| 126 | _curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 127 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 128 | _past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 129 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 130 | _curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 131 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 132 | if (_curr_sec & 0x80000000) |
| 133 | continue; |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 134 | curr = ctr->curr_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 135 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 136 | past = ctr->prev_ctr; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 137 | __ha_compiler_barrier(); |
Willy Tarreau | a06a580 | 2017-10-31 17:54:15 +0100 | [diff] [blame] | 138 | curr_sec = ctr->curr_sec; |
Willy Tarreau | 9453ecd | 2020-05-28 15:29:33 +0200 | [diff] [blame] | 139 | __ha_compiler_barrier(); |
Emeric Brun | 6e01286 | 2017-10-30 18:04:28 +0100 | [diff] [blame] | 140 | if (_curr == curr && _past == past && _curr_sec == curr_sec) |
| 141 | break; |
| 142 | } |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 143 | |
Willy Tarreau | a1ecbca | 2021-03-17 19:10:23 +0100 | [diff] [blame] | 144 | age = (global_now >> 32) - curr_sec; |
Christopher Faulet | 94b7123 | 2017-10-12 09:49:09 +0200 | [diff] [blame] | 145 | if (unlikely(age > 1)) |
| 146 | curr = 0; |
| 147 | else { |
| 148 | if (unlikely(age == 1)) { |
| 149 | past = curr; |
| 150 | curr = 0; |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 151 | } |
Willy Tarreau | eab777c | 2012-12-29 21:50:07 +0100 | [diff] [blame] | 152 | curr += mul32hi(past, ms_left_scaled); |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 153 | } |
| 154 | curr += pend; |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 155 | |
Willy Tarreau | 3d8c553 | 2009-03-06 14:29:25 +0100 | [diff] [blame] | 156 | if (curr < freq) |
Willy Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 157 | return 0; |
| 158 | |
Willy Tarreau | e4d247e | 2021-02-09 17:39:08 +0100 | [diff] [blame] | 159 | /* 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 Tarreau | 7958422 | 2009-03-06 09:18:27 +0100 | [diff] [blame] | 166 | return MAX(wait, 1); |
| 167 | } |
| 168 | |
Willy Tarreau | f3a9f8d | 2021-04-11 00:38:06 +0200 | [diff] [blame] | 169 | /* Returns the total number of events over the current + last period, including |
| 170 | * a number of already pending events <pend>. The average frequency will be |
| 171 | * obtained by dividing the output by <period>. This is essentially made to |
| 172 | * ease implementation of higher-level read functions. |
| 173 | * |
| 174 | * As a special case, if pend < 0, it's assumed there are no pending |
| 175 | * events and a flapping correction must be applied at the end. This is used by |
| 176 | * read_freq_ctr_period() to avoid reporting ups and downs on low-frequency |
| 177 | * events when the past value is <= 1. |
| 178 | */ |
| 179 | ullong freq_ctr_total(struct freq_ctr_period *ctr, uint period, int pend) |
| 180 | { |
| 181 | ullong curr, past; |
| 182 | uint curr_tick; |
| 183 | int remain; |
| 184 | |
| 185 | for (;; __ha_cpu_relax()) { |
| 186 | curr = ctr->curr_ctr; |
| 187 | past = ctr->prev_ctr; |
| 188 | curr_tick = ctr->curr_tick; |
| 189 | |
| 190 | /* now let's make sure the second loads retrieve the most |
| 191 | * up-to-date values. If no value changed after a load barrier, |
| 192 | * we're certain the values we got were stable. |
| 193 | */ |
| 194 | __ha_barrier_load(); |
| 195 | |
| 196 | if (curr_tick & 0x1) |
| 197 | continue; |
| 198 | |
| 199 | if (curr != ctr->curr_ctr) |
| 200 | continue; |
| 201 | |
| 202 | if (past != ctr->prev_ctr) |
| 203 | continue; |
| 204 | |
| 205 | if (curr_tick != ctr->curr_tick) |
| 206 | continue; |
| 207 | break; |
| 208 | }; |
| 209 | |
| 210 | remain = curr_tick + period - global_now_ms; |
| 211 | if (unlikely(remain < 0)) { |
| 212 | /* We're past the first period, check if we can still report a |
| 213 | * part of last period or if we're too far away. |
| 214 | */ |
| 215 | remain += period; |
| 216 | past = (remain >= 0) ? curr : 0; |
| 217 | curr = 0; |
| 218 | } |
| 219 | |
| 220 | if (pend < 0) { |
| 221 | /* enable flapping correction at very low rates */ |
| 222 | pend = 0; |
| 223 | if (!curr && past <= 1) |
| 224 | return past * period; |
| 225 | } |
| 226 | |
| 227 | /* compute the total number of confirmed events over the period */ |
| 228 | return past * remain + (curr + pend) * period; |
| 229 | } |
Willy Tarreau | 7f062c4 | 2009-03-05 18:43:00 +0100 | [diff] [blame] | 230 | |
| 231 | /* |
| 232 | * Local variables: |
| 233 | * c-indent-level: 8 |
| 234 | * c-basic-offset: 8 |
| 235 | * End: |
| 236 | */ |