| 1 |
|
| # Shared::Arena::Rate - a token bucket per key, shared by every worker. |
| 2 |
|
| |
| 3 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena PREFIX = sar_ |
| 4 |
|
| |
| 5 |
|
| # $arena->rate($name, limit => 100, window => 60, slots => 4096) |
| 6 |
|
| # |
| 7 |
|
| # `limit` is the burst - the most a key may spend at once - and `window` is how |
| 8 |
|
| # long a full refill takes, in seconds. Together they are the sustained rate. |
| 9 |
|
| # Both are the limiter's, not the caller's: a second policy is a second carve, |
| 10 |
|
| # which costs a few kilobytes and cannot be got wrong by two callers passing |
| 11 |
|
| # different numbers for one table. |
| 12 |
|
| SV * |
| 13 |
|
| sar_rate(self, name, ...) |
| 14 |
|
| SV *self |
| 15 |
|
| SV *name |
| 16 |
|
| PREINIT: |
| 17 |
|
| sa_region *arena; |
| 18 |
|
| sa_reg *e; |
| 19 |
|
| sa_rate *rl; |
| 20 |
|
| const char *nm; |
| 21 |
|
| STRLEN nlen; |
| 22 |
35 |
| UV limit = 100, slots = 4096; |
| 23 |
35 |
| double window = 60.0; |
| 24 |
|
| uint64_t nslots, burst_u, window_ms; |
| 25 |
35 |
| int err = SA_E_OK; |
| 26 |
|
| I32 i; |
| 27 |
|
| SV *obj; |
| 28 |
|
| CODE: |
| 29 |
35 |
| arena = SA_SELF(sa_region, self); |
| 30 |
35 |
▶ | if (!arena || !arena->map.base) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!arena || !arena->map.base) |
35 |
0 |
35 |
| if (!arena || !arena->map.base) |
0 |
35 |
35 |
|
| 31 |
0 |
| croak("Shared::Arena: this region is released"); |
| 32 |
35 |
| nm = SvPV(name, nlen); |
| 33 |
140 |
▶ | for (i = 2; i + 1 < items; i += 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 2; i + 1 < items; i += 2) { |
105 |
35 |
140 |
|
| 34 |
105 |
| const char *o = SvPV_nolen(ST(i)); |
| 35 |
105 |
▶ | if (strEQ(o, "limit")) limit = SvUV(ST(i + 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (strEQ(o, "limit")) limit = SvUV(ST(i + 1)); |
35 |
70 |
105 |
|
| 36 |
70 |
▶ | else if (strEQ(o, "window")) window = SvNV(ST(i + 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (strEQ(o, "window")) window = SvNV(ST(i + 1)); |
35 |
35 |
70 |
|
| 37 |
35 |
▶ | else if (strEQ(o, "slots")) slots = SvUV(ST(i + 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (strEQ(o, "slots")) slots = SvUV(ST(i + 1)); |
35 |
0 |
35 |
|
| 38 |
|
| } |
| 39 |
35 |
▶ | if (limit < 1) limit = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (limit < 1) limit = 1; |
0 |
35 |
35 |
|
| 40 |
35 |
▶ | if (!(window > 0.0)) window = 60.0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(window > 0.0)) window = 60.0; |
0 |
35 |
35 |
|
| 41 |
|
| /* A burst is counted in whole requests, so the scaled form has to fit |
| 42 |
|
| * the 32 bits a packed bucket gives it. */ |
| 43 |
35 |
▶ | if (limit > 0x3FFFFFu) limit = 0x3FFFFFu; |
Branch: 1 branch
| Branch | True | False | Total |
| if (limit > 0x3FFFFFu) limit = 0x3FFFFFu; |
1 |
34 |
35 |
|
| 44 |
35 |
| burst_u = (uint64_t)limit * SA_RATE_SCALE; |
| 45 |
35 |
| window_ms = (uint64_t)(window * 1000.0 + 0.5); |
| 46 |
35 |
▶ | if (!window_ms) window_ms = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!window_ms) window_ms = 1; |
0 |
35 |
35 |
|
| 47 |
35 |
| nslots = sa_rate_pow2((uint64_t)slots); |
| 48 |
|
| |
| 49 |
35 |
| e = sa_carve(arena, nm, (size_t)nlen, sa_rate_bytes(nslots), |
| 50 |
|
| SA_T_RATE, &err); |
| 51 |
35 |
▶ | if (!e) croak("Shared::Arena: the limiter '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) croak("Shared::Arena: the limiter '%s' %s", nm, sa_strerror(err)); |
0 |
35 |
35 |
|
| 52 |
|
| |
| 53 |
35 |
| rl = sa_rate_bind(arena, e, nslots, burst_u, window_ms, &err); |
| 54 |
35 |
▶ | if (!rl) croak("Shared::Arena: the limiter '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena: the limiter '%s' %s", nm, sa_strerror(err)); |
1 |
34 |
35 |
|
| 55 |
|
| |
| 56 |
34 |
| obj = newSV(0); |
| 57 |
34 |
| sv_setref_pv(obj, "Shared::Arena::Rate", (void *)rl); |
| 58 |
34 |
| sv_magicext(SvRV(obj), SvRV(self), PERL_MAGIC_ext, NULL, NULL, 0); |
| 59 |
34 |
| SvREFCNT_inc(SvRV(self)); |
| 60 |
34 |
| RETVAL = obj; |
| 61 |
|
| OUTPUT: |
| 62 |
|
| RETVAL |
| 63 |
|
| |
| 64 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena::Rate PREFIX = sart_ |
| 65 |
|
| |
| 66 |
|
| # 1 when the request is within the limit, 0 when it is not. A second argument |
| 67 |
|
| # is the cost, for a caller charging an expensive route more than a cheap one. |
| 68 |
|
| # |
| 69 |
|
| # An INT rather than a list, so `if ($rl->allow($ip))` cannot be read as |
| 70 |
|
| # anything else. The numbers for an X-RateLimit header come from `remaining` |
| 71 |
|
| # and `retry_after`, which do not spend a token. |
| 72 |
|
| int |
| 73 |
|
| sart_allow(self, key, ...) |
| 74 |
|
| SV *self |
| 75 |
|
| SV *key |
| 76 |
|
| PREINIT: |
| 77 |
|
| sa_rate *rl; |
| 78 |
|
| const char *k; |
| 79 |
|
| STRLEN klen; |
| 80 |
120 |
▶ | UV cost = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| UV cost = 1; |
120 |
0 |
120 |
|
| 81 |
|
| CODE: |
| 82 |
120 |
| rl = SA_SELF(sa_rate, self); |
| 83 |
120 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
120 |
120 |
|
| 84 |
120 |
▶ | if (items > 2) cost = SvUV(ST(2)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (items > 2) cost = SvUV(ST(2)); |
0 |
120 |
120 |
|
| 85 |
120 |
▶ | if (cost < 1) cost = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (cost < 1) cost = 1; |
0 |
120 |
120 |
|
| 86 |
120 |
| k = SvPV(key, klen); |
| 87 |
|
| #if SA_HAVE_ATOMICS |
| 88 |
120 |
| RETVAL = sa_rate_take(rl, k, (uint32_t)klen, |
| 89 |
|
| (uint64_t)cost * SA_RATE_SCALE, 0, NULL, NULL); |
| 90 |
|
| #else |
| 91 |
|
| RETVAL = 1; /* no atomics: the limiter is not the reason a good |
| 92 |
|
| * request is refused */ |
| 93 |
|
| #endif |
| 94 |
|
| OUTPUT: |
| 95 |
|
| RETVAL |
| 96 |
|
| |
| 97 |
|
| # What the key could spend right now, in whole requests, WITHOUT spending one. |
| 98 |
|
| NV |
| 99 |
|
| sart_remaining(self, key) |
| 100 |
|
| SV *self |
| 101 |
|
| SV *key |
| 102 |
|
| PREINIT: |
| 103 |
|
| sa_rate *rl; |
| 104 |
|
| const char *k; |
| 105 |
|
| STRLEN klen; |
| 106 |
1 |
▶ | uint64_t left = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t left = 0; |
1 |
0 |
1 |
|
| 107 |
|
| CODE: |
| 108 |
1 |
| rl = SA_SELF(sa_rate, self); |
| 109 |
1 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
1 |
1 |
|
| 110 |
1 |
| k = SvPV(key, klen); |
| 111 |
|
| #if SA_HAVE_ATOMICS |
| 112 |
1 |
| (void)sa_rate_take(rl, k, (uint32_t)klen, |
| 113 |
|
| (uint64_t)SA_RATE_SCALE, 1, &left, NULL); |
| 114 |
1 |
▶ | RETVAL = (NV)left / (NV)SA_RATE_SCALE; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (NV)left / (NV)SA_RATE_SCALE; |
0 |
1 |
1 |
|
| 115 |
|
| #else |
| 116 |
|
| RETVAL = (NV)0; |
| 117 |
|
| #endif |
| 118 |
|
| OUTPUT: |
| 119 |
|
| RETVAL |
| 120 |
|
| |
| 121 |
|
| # Seconds until one more request would be allowed. Zero when one already is. |
| 122 |
|
| # This is the number a Retry-After header wants. |
| 123 |
|
| NV |
| 124 |
|
| sart_retry_after(self, key) |
| 125 |
|
| SV *self |
| 126 |
|
| SV *key |
| 127 |
|
| PREINIT: |
| 128 |
|
| sa_rate *rl; |
| 129 |
|
| const char *k; |
| 130 |
|
| STRLEN klen; |
| 131 |
1 |
▶ | uint64_t retry = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t retry = 0; |
1 |
0 |
1 |
|
| 132 |
|
| CODE: |
| 133 |
1 |
| rl = SA_SELF(sa_rate, self); |
| 134 |
1 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
1 |
1 |
|
| 135 |
1 |
| k = SvPV(key, klen); |
| 136 |
|
| #if SA_HAVE_ATOMICS |
| 137 |
1 |
| (void)sa_rate_take(rl, k, (uint32_t)klen, |
| 138 |
|
| (uint64_t)SA_RATE_SCALE, 1, NULL, &retry); |
| 139 |
1 |
▶ | RETVAL = (NV)retry / (NV)1000.0; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (NV)retry / (NV)1000.0; |
0 |
1 |
1 |
|
| 140 |
|
| #else |
| 141 |
|
| RETVAL = (NV)0; |
| 142 |
|
| #endif |
| 143 |
|
| OUTPUT: |
| 144 |
|
| RETVAL |
| 145 |
|
| |
| 146 |
|
| # Refill one key to full: an operator lifting a limit by hand, or a test. |
| 147 |
|
| void |
| 148 |
|
| sart_reset(self, key) |
| 149 |
|
| SV *self |
| 150 |
|
| SV *key |
| 151 |
|
| PREINIT: |
| 152 |
|
| sa_rate *rl; |
| 153 |
|
| const char *k; |
| 154 |
|
| STRLEN klen; |
| 155 |
|
| CODE: |
| 156 |
1 |
| rl = SA_SELF(sa_rate, self); |
| 157 |
1 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
1 |
1 |
|
| 158 |
1 |
| k = SvPV(key, klen); |
| 159 |
|
| #if SA_HAVE_ATOMICS |
| 160 |
1 |
| sa_rate_reset_key(rl, k, (uint32_t)klen); |
| 161 |
|
| #else |
| 162 |
|
| PERL_UNUSED_VAR(k); |
| 163 |
|
| #endif |
| 164 |
|
| |
| 165 |
|
| # Give the key's slot back, so somebody else can have it. |
| 166 |
|
| void |
| 167 |
|
| sart_forget(self, key) |
| 168 |
|
| SV *self |
| 169 |
|
| SV *key |
| 170 |
|
| PREINIT: |
| 171 |
|
| sa_rate *rl; |
| 172 |
|
| const char *k; |
| 173 |
|
| STRLEN klen; |
| 174 |
|
| CODE: |
| 175 |
1 |
| rl = SA_SELF(sa_rate, self); |
| 176 |
1 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
1 |
1 |
|
| 177 |
1 |
| k = SvPV(key, klen); |
| 178 |
|
| #if SA_HAVE_ATOMICS |
| 179 |
1 |
| sa_rate_forget(rl, k, (uint32_t)klen); |
| 180 |
|
| #else |
| 181 |
|
| PERL_UNUSED_VAR(k); |
| 182 |
|
| #endif |
| 183 |
|
| |
| 184 |
|
| UV |
| 185 |
|
| sart_slots(self) |
| 186 |
|
| SV *self |
| 187 |
|
| PREINIT: |
| 188 |
|
| sa_rate *rl; |
| 189 |
|
| CODE: |
| 190 |
0 |
| rl = SA_SELF(sa_rate, self); |
| 191 |
0 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
0 |
0 |
|
| 192 |
0 |
▶ | RETVAL = (UV)rl->nslots; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (UV)rl->nslots; |
0 |
0 |
0 |
|
| 193 |
|
| OUTPUT: |
| 194 |
|
| RETVAL |
| 195 |
|
| |
| 196 |
|
| # limit / window / slots / keys / allowed / denied / evicted / contended |
| 197 |
|
| # |
| 198 |
|
| # `evicted` is how many live buckets were taken over because the table had no |
| 199 |
|
| # room, which is how you find out the table is too small. `contended` is how |
| 200 |
|
| # many hits gave up on the compare-and-swap and were ALLOWED without being |
| 201 |
|
| # counted against anybody - a limiter that has stopped limiting, which is a |
| 202 |
|
| # thing an operator has to be able to see rather than infer from a suspiciously |
| 203 |
|
| # clean denied count. |
| 204 |
|
| void |
| 205 |
|
| sart_stats(self) |
| 206 |
|
| SV *self |
| 207 |
|
| PREINIT: |
| 208 |
|
| sa_rate *rl; |
| 209 |
|
| PPCODE: |
| 210 |
4 |
| rl = SA_SELF(sa_rate, self); |
| 211 |
4 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
4 |
4 |
|
| 212 |
4 |
▶ | EXTEND(SP, 16); |
Branch: 1 branch
| Branch | True | False | Total |
| EXTEND(SP, 16); |
0 |
4 |
4 |
|
| 213 |
4 |
| mPUSHp("limit", 5); |
| 214 |
4 |
| mPUSHn((NV)rl->burst_u / (NV)SA_RATE_SCALE); |
| 215 |
4 |
| mPUSHp("window", 6); |
| 216 |
4 |
| mPUSHn((NV)rl->window_ms / (NV)1000.0); |
| 217 |
4 |
| mPUSHp("slots", 5); mPUSHu((UV)rl->nslots); |
| 218 |
|
| #if SA_HAVE_ATOMICS |
| 219 |
4 |
| mPUSHp("keys", 4); mPUSHu((UV)sa_rate_used(rl)); |
| 220 |
4 |
| mPUSHp("allowed", 7); mPUSHu((UV)sa_at_load64_acq(&rl->hdr->allowed)); |
| 221 |
4 |
| mPUSHp("denied", 6); mPUSHu((UV)sa_at_load64_acq(&rl->hdr->denied)); |
| 222 |
4 |
| mPUSHp("evicted", 7); mPUSHu((UV)sa_at_load64_acq(&rl->hdr->evicted)); |
| 223 |
4 |
| mPUSHp("contended", 9); |
| 224 |
4 |
| mPUSHu((UV)sa_at_load64_acq(&rl->hdr->contended)); |
| 225 |
|
| #endif |
| 226 |
|
| |
| 227 |
|
| void |
| 228 |
|
| sart_DESTROY(self) |
| 229 |
|
| SV *self |
| 230 |
|
| PREINIT: |
| 231 |
|
| sa_rate *rl; |
| 232 |
|
| CODE: |
| 233 |
34 |
| rl = SA_SELF(sa_rate, self); |
| 234 |
34 |
▶ | if (rl) { sa_rate_free(rl); sv_setiv(SvRV(self), 0); } |
Branch: 1 branch
| Branch | True | False | Total |
| if (rl) { sa_rate_free(rl); sv_setiv(SvRV(self), 0); } |
34 |
0 |
34 |
|
| 235 |
|
| |
| 236 |
|
| # TEST ONLY, and underscore-named because of it. Move a key's stored timestamp |
| 237 |
|
| # forward, which is precisely what a process whose clock reading is a |
| 238 |
|
| # millisecond ahead does to every other caller. |
| 239 |
|
| # |
| 240 |
|
| # The race this reproduces needs three processes and half a second of contention |
| 241 |
|
| # to happen by accident, and then happens 88 times in 1.5M calls. This produces |
| 242 |
|
| # it exactly, once, in one process, with no timing at all. A test that has to |
| 243 |
|
| # win a race to see a bug is a test that will one day stop seeing it. |
| 244 |
|
| void |
| 245 |
|
| sart__skew(self, key, ms) |
| 246 |
|
| SV *self |
| 247 |
|
| SV *key |
| 248 |
|
| IV ms |
| 249 |
|
| PREINIT: |
| 250 |
|
| sa_rate *rl; |
| 251 |
|
| const char *k; |
| 252 |
|
| STRLEN klen; |
| 253 |
|
| uint64_t h, idx, state; |
| 254 |
|
| CODE: |
| 255 |
7 |
| rl = SA_SELF(sa_rate, self); |
| 256 |
7 |
▶ | if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rl) croak("Shared::Arena::Rate: this limiter is released"); |
0 |
7 |
7 |
|
| 257 |
|
| #if SA_HAVE_ATOMICS |
| 258 |
7 |
| k = SvPV(key, klen); |
| 259 |
7 |
| h = sa_at_fnv(k, (size_t)klen); |
| 260 |
7 |
▶ | if (!h) h = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) h = 1; |
0 |
7 |
7 |
|
| 261 |
7 |
| idx = sa_rate_slot_for(rl, h, sa_rate_now_ms(), NULL); |
| 262 |
7 |
| state = sa_at_load64_acq(&rl->slots[idx].state); |
| 263 |
7 |
| sa_at_store64_rel(&rl->slots[idx].state, |
| 264 |
7 |
| SA_RATE_STATE(SA_RATE_TOKENS(state), |
| 265 |
|
| (uint32_t)((uint32_t)SA_RATE_WHEN(state) |
| 266 |
|
| + (uint32_t)(int32_t)ms))); |
| 267 |
|
| #else |
| 268 |
|
| PERL_UNUSED_VAR(key); |
| 269 |
|
| PERL_UNUSED_VAR(ms); |
| 270 |
|
| #endif |