| 1 |
|
| #ifndef SA_RATE_H |
| 2 |
|
| #define SA_RATE_H |
| 3 |
|
| |
| 4 |
|
| /* sa_rate.h - a token bucket per key, shared by every process. Perl-free. |
| 5 |
|
| * |
| 6 |
|
| * ---- the problem this exists for -------------------------------------------- |
| 7 |
|
| * |
| 8 |
|
| * A limit of 100/min enforced in a pre-forked pool is not a limit of 100/min. |
| 9 |
|
| * Each worker keeps its own counter, so the real limit is workers x 100/min, |
| 10 |
|
| * and the number moves when the pool is resized. The sibling implementation in |
| 11 |
|
| * Hyperman says the same thing in its own words, and the dist before that put |
| 12 |
|
| * the counters in a FILE to escape it - which buys correctness back at the |
| 13 |
|
| * price of a syscall on every request. |
| 14 |
|
| * |
| 15 |
|
| * The state belongs in memory every worker already shares. That is this. |
| 16 |
|
| * |
| 17 |
|
| * ---- a token bucket, not a fixed window ------------------------------------- |
| 18 |
|
| * |
| 19 |
|
| * A fixed window is the obvious implementation and it has a hole in it: the |
| 20 |
|
| * window boundary. A caller limited to 100 per minute can spend 100 at 11:59:59 |
| 21 |
|
| * and 100 more at 12:00:00, which is 200 requests in one second and is exactly |
| 22 |
|
| * what the limit was written to prevent. The bug is invisible in testing |
| 23 |
|
| * because it needs the clock to be in a particular place. |
| 24 |
|
| * |
| 25 |
|
| * A bucket has no boundary to stand on. It holds up to `limit` tokens, refills |
| 26 |
|
| * continuously at `limit` per `window`, and a request takes one. Sustained rate |
| 27 |
|
| * and burst size become two numbers a caller can set independently, which is |
| 28 |
|
| * what a caller actually wants: 100/min with a burst of 100 is a different |
| 29 |
|
| * policy from 100/min with a burst of 10, and a window cannot express either. |
| 30 |
|
| * |
| 31 |
|
| * ---- the whole bucket is ONE WORD, and that is the design ------------------- |
| 32 |
|
| * |
| 33 |
|
| * Tokens and the moment they were last refilled are packed into one uint64: |
| 34 |
|
| * |
| 35 |
|
| * bits 63..32 tokens, in units of 1/1024 of a token |
| 36 |
|
| * bits 31..0 when they were counted, in milliseconds |
| 37 |
|
| * |
| 38 |
|
| * So a hit is a compare-and-swap, and the limiter needs no lock on its hot |
| 39 |
|
| * path at all. That matters for more than speed. Hyperman's takes a striped |
| 40 |
|
| * spinlock per hit and FAILS OPEN when the spin is exhausted - which means |
| 41 |
|
| * that under exactly the load a rate limiter exists for, it quietly stops |
| 42 |
|
| * limiting. This cannot do that: a CAS either wins or is retried, and the |
| 43 |
|
| * retries are counted rather than being a silent hole. |
| 44 |
|
| * |
| 45 |
|
| * It is also why a crash cannot corrupt it. A process that dies mid-update has |
| 46 |
|
| * either landed its CAS or not; there is no half-written bucket to find, |
| 47 |
|
| * nothing to repair, and no need for the peer table that the ring depends on. |
| 48 |
|
| * Of every structure in this dist, this is the one whose crash story is "there |
| 49 |
|
| * is nothing to say". |
| 50 |
|
| * |
| 51 |
|
| * THE TIMESTAMP WRAPS, deliberately. Thirty-two bits of milliseconds is 49.7 |
| 52 |
|
| * days, and the elapsed time is a SIGNED difference, which is correct across a |
| 53 |
|
| * wrap for any interval up to half of that. A key idle for longer than 24.9 |
| 54 |
|
| * days measures short and so refills slower than it should, once, for one hit. |
| 55 |
|
| * That is the direction to be wrong in, and the alternative is a wider field |
| 56 |
|
| * that makes every bucket bigger to fix a case that ends in one extra allowed |
| 57 |
|
| * request. |
| 58 |
|
| * |
| 59 |
|
| * Signed, not unsigned, because a caller's clock reading can be BEHIND the |
| 60 |
|
| * timestamp another process already stored, and unsigned subtraction reads |
| 61 |
|
| * that as forty-nine days of refill. See sa_rate_refill. |
| 62 |
|
| * |
| 63 |
|
| * The clock is sa_now_us, monotonic where the build has one (sa_time.h). A |
| 64 |
|
| * wall-clock step on the host is otherwise a step in every bucket's clock at |
| 65 |
|
| * once: back by 0.6s, and for 0.6s nothing refills; forward by an hour, and |
| 66 |
|
| * every bucket is full. |
| 67 |
|
| * |
| 68 |
|
| * ---- when the table is full -------------------------------------------------- |
| 69 |
|
| * |
| 70 |
|
| * Open addressing, and no free list - the arena has no free anywhere and this |
| 71 |
|
| * is not the structure to invent one in. A slot is reclaimable when its bucket |
| 72 |
|
| * is FULL, because a full bucket is indistinguishable from a key that has never |
| 73 |
|
| * been seen: both allow the next `limit` requests. So an idle key's slot is |
| 74 |
|
| * handed to a new key with nothing lost, and the table drains itself with no |
| 75 |
|
| * sweep and no timer. |
| 76 |
|
| * |
| 77 |
|
| * When every slot holds a bucket that is NOT full - the table is genuinely |
| 78 |
|
| * over capacity - a new key takes over its home slot, which resets a live |
| 79 |
|
| * bucket. THAT LEAKS LOOSER, NEVER TIGHTER: the victim gets more requests than |
| 80 |
|
| * it should, never fewer, so an over-full table cannot turn into an outage. |
| 81 |
|
| * Size the table above the peak count of distinct keys in a window, and read |
| 82 |
|
| * `evicted` to find out whether you did. |
| 83 |
|
| * |
| 84 |
|
| * Needs sa_arena.h. |
| 85 |
|
| */ |
| 86 |
|
| |
| 87 |
|
| #include "sa/sa_arena.h" |
| 88 |
|
| |
| 89 |
|
| #define SA_RATE_MAGIC 0x45544152u /* 'R','A','T','E' little-endian */ |
| 90 |
|
| |
| 91 |
|
| /* Tokens are integers in units of 1/1024, so a refill of a fraction of a token |
| 92 |
|
| * is not lost to truncation. A limiter of 100/min refills 1.7 tokens a second, |
| 93 |
|
| * which as an integer count of tokens per millisecond is zero. */ |
| 94 |
|
| #define SA_RATE_SCALE 1024u |
| 95 |
|
| |
| 96 |
|
| /* A hit is a CAS loop. This bounds it, for the same reason every wait in this |
| 97 |
|
| * dist is bounded - but reaching it is not "fail open and say nothing", it is |
| 98 |
|
| * counted in `contended`, because a limiter that has stopped limiting is |
| 99 |
|
| * something an operator has to be able to discover. */ |
| 100 |
|
| #define SA_RATE_CAS_TRIES 64 |
| 101 |
|
| |
| 102 |
|
| /* How far an insert probes before it gives up and takes the home slot. */ |
| 103 |
|
| #define SA_RATE_PROBE 16 |
| 104 |
|
| |
| 105 |
|
| typedef struct { |
| 106 |
|
| volatile uint64_t keyhash; /* 0 = empty */ |
| 107 |
|
| volatile uint64_t state; /* (tokens_u << 32) | last_ms */ |
| 108 |
|
| } sa_rate_slot; |
| 109 |
|
| |
| 110 |
|
| typedef struct { |
| 111 |
|
| volatile uint32_t magic; /* published LAST at init */ |
| 112 |
|
| uint32_t pad; |
| 113 |
|
| uint64_t nslots; /* a power of two */ |
| 114 |
|
| uint64_t slots_off; /* from the LIMITER's base */ |
| 115 |
|
| uint64_t burst_u; /* the full bucket, in 1/1024 tokens */ |
| 116 |
|
| uint64_t window_ms; /* time to refill from empty to full */ |
| 117 |
|
| volatile uint64_t allowed; |
| 118 |
|
| volatile uint64_t denied; |
| 119 |
|
| volatile uint64_t evicted; /* live buckets taken over: the table is small */ |
| 120 |
|
| volatile uint64_t contended; /* CAS loops that gave up and allowed */ |
| 121 |
|
| volatile unsigned char locks[SA_LOCK_STRIPES]; |
| 122 |
|
| } sa_rate_hdr; |
| 123 |
|
| |
| 124 |
|
| #ifndef SA_RATE_FWD |
| 125 |
|
| #define SA_RATE_FWD |
| 126 |
|
| typedef struct sa_rate sa_rate; |
| 127 |
|
| #endif |
| 128 |
|
| |
| 129 |
|
| struct sa_rate { |
| 130 |
|
| sa_region *arena; |
| 131 |
|
| sa_rate_hdr *hdr; |
| 132 |
|
| sa_rate_slot *slots; |
| 133 |
|
| uint64_t nslots; |
| 134 |
|
| uint64_t mask; |
| 135 |
|
| uint64_t burst_u; |
| 136 |
|
| uint64_t window_ms; |
| 137 |
|
| }; |
| 138 |
|
| |
| 139 |
|
| #define SA_RATE_TOKENS(st) ((uint64_t)((st) >> 32)) |
| 140 |
|
| #define SA_RATE_WHEN(st) ((uint32_t)((st) & 0xFFFFFFFFu)) |
| 141 |
|
| #define SA_RATE_STATE(t, ms) \ |
| 142 |
|
| ((((uint64_t)(t)) << 32) | (uint64_t)(uint32_t)(ms)) |
| 143 |
|
| |
| 144 |
109 |
| static uint64_t sa_rate_bytes(uint64_t nslots) { |
| 145 |
109 |
| return sa_align_up((uint64_t)sizeof(sa_rate_hdr)) |
| 146 |
109 |
| + nslots * (uint64_t)sizeof(sa_rate_slot); |
| 147 |
|
| } |
| 148 |
|
| |
| 149 |
|
| /* Round up to a power of two, so the slot index is a mask rather than a |
| 150 |
|
| * division on the hot path. */ |
| 151 |
37 |
| static uint64_t sa_rate_pow2(uint64_t n) { |
| 152 |
37 |
| uint64_t p = 64; |
| 153 |
37 |
▶ | if (n < 64) return 64; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n < 64) return 64; |
0 |
37 |
37 |
|
| 154 |
49 |
▶ | while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
Branch: 2 branches
| Branch | True | False | Total |
| while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
12 |
37 |
49 |
| while (p < n && p < (uint64_t)1 << 40) p <<= 1; |
12 |
0 |
12 |
|
| 155 |
37 |
| return p; |
| 156 |
|
| } |
| 157 |
|
| |
| 158 |
|
| /* Milliseconds, in the same 32-bit space the slots store. */ |
| 159 |
8622 |
| static uint32_t sa_rate_now_ms(void) { |
| 160 |
8622 |
| return (uint32_t)(sa_now_us() / 1000u); |
| 161 |
|
| } |
| 162 |
|
| |
| 163 |
37 |
| static sa_rate *sa_rate_bind(sa_region *arena, sa_reg *e, uint64_t nslots, |
| 164 |
|
| uint64_t burst_u, uint64_t window_ms, int *err) |
| 165 |
|
| { |
| 166 |
|
| #if !SA_HAVE_ATOMICS |
| 167 |
|
| (void)arena; (void)e; (void)nslots; (void)burst_u; (void)window_ms; |
| 168 |
|
| if (err) *err = SA_E_NOATOMICS; |
| 169 |
|
| return NULL; |
| 170 |
|
| #else |
| 171 |
|
| sa_rate *r; |
| 172 |
|
| sa_rate_hdr *h; |
| 173 |
|
| uint64_t hash; |
| 174 |
|
| |
| 175 |
37 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
37 |
0 |
37 |
|
| 176 |
37 |
▶ | if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 3 branches
| Branch | True | False | Total |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
37 |
0 |
37 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
37 |
37 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 177 |
|
| |
| 178 |
37 |
| h = (sa_rate_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_rate_hdr)); |
| 179 |
37 |
▶ | if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
37 |
37 |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 180 |
|
| |
| 181 |
37 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_RATE_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_RATE_MAGIC) { |
36 |
1 |
37 |
|
| 182 |
36 |
| hash = sa_at_fnv(e->name, strlen(e->name)); |
| 183 |
36 |
▶ | if (sa_at_lock(h->locks, hash)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_lock(h->locks, hash)) { |
36 |
0 |
36 |
|
| 184 |
36 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_RATE_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_RATE_MAGIC) { |
36 |
0 |
36 |
|
| 185 |
36 |
▶ | if (!nslots || !burst_u || !window_ms |
Branch: 3 branches
| Branch | True | False | Total |
| if (!nslots || !burst_u || !window_ms |
36 |
0 |
36 |
| if (!nslots || !burst_u || !window_ms |
36 |
0 |
36 |
| if (!nslots || !burst_u || !window_ms |
36 |
0 |
36 |
|
| 186 |
36 |
▶ | || sa_rate_bytes(nslots) > e->len) { |
Branch: 1 branch
| Branch | True | False | Total |
| || sa_rate_bytes(nslots) > e->len) { |
0 |
36 |
36 |
|
| 187 |
0 |
| sa_at_unlock(h->locks, hash); |
| 188 |
0 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
0 |
0 |
0 |
|
| 189 |
0 |
| return NULL; |
| 190 |
|
| } |
| 191 |
36 |
| memset((void *)h, 0, (size_t)sa_rate_bytes(nslots)); |
| 192 |
36 |
| h->nslots = nslots; |
| 193 |
36 |
| h->slots_off = sa_align_up((uint64_t)sizeof(sa_rate_hdr)); |
| 194 |
36 |
| h->burst_u = burst_u; |
| 195 |
36 |
| h->window_ms = window_ms; |
| 196 |
36 |
| sa_at_store32_rel(&h->magic, SA_RATE_MAGIC); |
| 197 |
|
| } |
| 198 |
36 |
| sa_at_unlock(h->locks, hash); |
| 199 |
|
| } |
| 200 |
36 |
▶ | if (!sa_wait_magic32(&h->magic, SA_RATE_MAGIC)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_RATE_MAGIC)) { |
0 |
36 |
36 |
|
| 201 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_MAGIC; |
0 |
0 |
0 |
|
| 202 |
0 |
| return NULL; |
| 203 |
|
| } |
| 204 |
|
| } |
| 205 |
|
| |
| 206 |
|
| /* A caller asking for a policy the limiter does not have would be counting |
| 207 |
|
| * against somebody else's numbers. Say no, as every other tenant does. */ |
| 208 |
37 |
▶ | if ((nslots && h->nslots != nslots) |
Branch: 2 branches
| Branch | True | False | Total |
| if ((nslots && h->nslots != nslots) |
37 |
0 |
37 |
| if ((nslots && h->nslots != nslots) |
37 |
0 |
37 |
|
| 209 |
37 |
▶ | || (burst_u && h->burst_u != burst_u) |
Branch: 2 branches
| Branch | True | False | Total |
| || (burst_u && h->burst_u != burst_u) |
37 |
0 |
37 |
| || (burst_u && h->burst_u != burst_u) |
36 |
1 |
37 |
|
| 210 |
36 |
▶ | || (window_ms && h->window_ms != window_ms)) { |
Branch: 2 branches
| Branch | True | False | Total |
| || (window_ms && h->window_ms != window_ms)) { |
36 |
0 |
36 |
| || (window_ms && h->window_ms != window_ms)) { |
0 |
36 |
36 |
|
| 211 |
1 |
▶ | if (err) *err = SA_E_SHAPE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_SHAPE; |
1 |
0 |
1 |
|
| 212 |
1 |
| return NULL; |
| 213 |
|
| } |
| 214 |
|
| |
| 215 |
36 |
| r = (sa_rate *)calloc(1, sizeof(sa_rate)); |
| 216 |
36 |
▶ | if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
36 |
36 |
| if (!r) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
0 |
0 |
|
| 217 |
36 |
| r->arena = arena; |
| 218 |
36 |
| r->hdr = h; |
| 219 |
36 |
| r->slots = (sa_rate_slot *)((char *)h + (size_t)h->slots_off); |
| 220 |
36 |
| r->nslots = h->nslots; |
| 221 |
36 |
| r->mask = h->nslots - 1; |
| 222 |
36 |
| r->burst_u = h->burst_u; |
| 223 |
36 |
| r->window_ms = h->window_ms; |
| 224 |
36 |
| return r; |
| 225 |
|
| #endif |
| 226 |
|
| } |
| 227 |
|
| |
| 228 |
36 |
| static void sa_rate_free(sa_rate *r) { free(r); } |
| 229 |
|
| |
| 230 |
|
| #if SA_HAVE_ATOMICS |
| 231 |
|
| |
| 232 |
|
| /* What the bucket holds NOW, given what it held when it was last touched. |
| 233 |
|
| * |
| 234 |
|
| * ELAPSED IS SIGNED, AND THAT IS THE WHOLE OF IT. |
| 235 |
|
| * |
| 236 |
|
| * A caller reads the clock once and then races for the slot. In between, |
| 237 |
|
| * another process can write a timestamp LATER than the one this caller is |
| 238 |
|
| * holding, so `now` is behind what the slot says. Unsigned subtraction turns |
| 239 |
|
| * that one millisecond into 4,294,967,295 of them, which clears any window, so |
| 240 |
|
| * the bucket comes back FULL and the limiter has stopped limiting. |
| 241 |
|
| * |
| 242 |
|
| * That is not a corner case. Measured with three processes on one key: 88 |
| 243 |
|
| * backwards readings in 1.5M calls, and 88 refills to full, which is 88 million |
| 244 |
|
| * tokens handed to a bucket that holds one million. Every request was allowed |
| 245 |
|
| * and `denied` was zero. |
| 246 |
|
| * |
| 247 |
|
| * The difference is taken as int32_t instead, which is serial-number |
| 248 |
|
| * arithmetic: a reading slightly behind is a small negative and means no time |
| 249 |
|
| * has passed for this caller, while a genuine forward interval stays correct |
| 250 |
|
| * across the field's wrap. The cost is that the longest measurable idle drops |
| 251 |
|
| * from 49.7 days to 24.9, and beyond that a key measures short and refills |
| 252 |
|
| * slower than it should for one hit. That is the direction to be wrong in. */ |
| 253 |
39939 |
| static uint64_t sa_rate_refill(const sa_rate *r, uint64_t state, uint32_t now) { |
| 254 |
39939 |
| uint64_t tokens = SA_RATE_TOKENS(state); |
| 255 |
39939 |
| int32_t ahead = (int32_t)(now - SA_RATE_WHEN(state)); |
| 256 |
|
| uint32_t elapsed; |
| 257 |
|
| |
| 258 |
39939 |
▶ | if (tokens >= r->burst_u) return r->burst_u; |
Branch: 1 branch
| Branch | True | False | Total |
| if (tokens >= r->burst_u) return r->burst_u; |
2042 |
37897 |
39939 |
|
| 259 |
37897 |
▶ | if (ahead <= 0) return tokens; |
Branch: 1 branch
| Branch | True | False | Total |
| if (ahead <= 0) return tokens; |
35506 |
2391 |
37897 |
|
| 260 |
2391 |
| elapsed = (uint32_t)ahead; |
| 261 |
|
| /* Clamped before the multiply, not after: a key idle for a month would |
| 262 |
|
| * otherwise overflow the intermediate on its way to an answer that is |
| 263 |
|
| * simply "full". */ |
| 264 |
2391 |
▶ | if ((uint64_t)elapsed >= r->window_ms) return r->burst_u; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)elapsed >= r->window_ms) return r->burst_u; |
11 |
2380 |
2391 |
|
| 265 |
2380 |
| tokens += ((uint64_t)elapsed * r->burst_u) / r->window_ms; |
| 266 |
2380 |
| return tokens > r->burst_u ? r->burst_u : tokens; |
| 267 |
|
| } |
| 268 |
|
| |
| 269 |
|
| /* The timestamp to store beside a token count. |
| 270 |
|
| * |
| 271 |
|
| * Never the caller's own reading when the slot already holds a later one: |
| 272 |
|
| * writing a stale `now` drags the bucket's clock backwards, throwing away time |
| 273 |
|
| * a competing process had already accounted for and making the next caller |
| 274 |
|
| * more likely to read backwards in turn. Keep whichever is further ahead. */ |
| 275 |
8531 |
| static uint32_t sa_rate_stamp(uint64_t state, uint32_t now) { |
| 276 |
8531 |
| uint32_t when = SA_RATE_WHEN(state); |
| 277 |
8531 |
▶ | return ((int32_t)(now - when) > 0) ? now : when; |
Branch: 1 branch
| Branch | True | False | Total |
| return ((int32_t)(now - when) > 0) ? now : when; |
64 |
8467 |
8531 |
|
| 278 |
|
| } |
| 279 |
|
| |
| 280 |
|
| /* The slot this key lives in, claiming or reclaiming one if it has none. |
| 281 |
|
| * Returns the index, or the home slot when the table is full of live buckets. |
| 282 |
|
| * `*took_over` is set when a bucket that was NOT full had to be evicted. */ |
| 283 |
8622 |
| static uint64_t sa_rate_slot_for(sa_rate *r, uint64_t h, uint32_t now, |
| 284 |
|
| int *took_over) |
| 285 |
|
| { |
| 286 |
8622 |
| uint64_t home = h & r->mask; |
| 287 |
|
| uint64_t i; |
| 288 |
|
| |
| 289 |
8622 |
▶ | if (took_over) *took_over = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (took_over) *took_over = 0; |
8613 |
9 |
8622 |
|
| 290 |
|
| |
| 291 |
39948 |
▶ | for (i = 0; i < SA_RATE_PROBE; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < SA_RATE_PROBE; i++) { |
38011 |
1937 |
39948 |
|
| 292 |
38011 |
| uint64_t idx = (home + i) & r->mask; |
| 293 |
38011 |
| sa_rate_slot *s = &r->slots[idx]; |
| 294 |
38011 |
| uint64_t have = sa_at_load64_acq(&s->keyhash); |
| 295 |
|
| |
| 296 |
38011 |
▶ | if (have == h) return idx; |
Branch: 1 branch
| Branch | True | False | Total |
| if (have == h) return idx; |
6583 |
31428 |
38011 |
|
| 297 |
31428 |
▶ | if (!have) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!have) { |
102 |
31326 |
31428 |
|
| 298 |
|
| /* An empty slot. Losing the race for it is not a problem: the |
| 299 |
|
| * winner is either us or somebody whose key we then probe past. */ |
| 300 |
102 |
▶ | if (sa_at_cas64(&s->keyhash, 0, h)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&s->keyhash, 0, h)) { |
102 |
0 |
102 |
|
| 301 |
102 |
| sa_at_store64_rel(&s->state, SA_RATE_STATE(r->burst_u, now)); |
| 302 |
102 |
| return idx; |
| 303 |
|
| } |
| 304 |
0 |
▶ | if (sa_at_load64_acq(&s->keyhash) == h) return idx; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->keyhash) == h) return idx; |
0 |
0 |
0 |
|
| 305 |
0 |
| continue; |
| 306 |
|
| } |
| 307 |
|
| /* Somebody else's key. A FULL bucket is indistinguishable from a key |
| 308 |
|
| * that has never been seen, so taking it over loses nothing. */ |
| 309 |
31326 |
▶ | if (sa_rate_refill(r, sa_at_load64_acq(&s->state), now) >= r->burst_u) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_rate_refill(r, sa_at_load64_acq(&s->state), now) >= r->burst_u) { |
0 |
31326 |
31326 |
|
| 310 |
0 |
▶ | if (sa_at_cas64(&s->keyhash, have, h)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&s->keyhash, have, h)) { |
0 |
0 |
0 |
|
| 311 |
0 |
| sa_at_store64_rel(&s->state, SA_RATE_STATE(r->burst_u, now)); |
| 312 |
0 |
| return idx; |
| 313 |
|
| } |
| 314 |
0 |
▶ | if (sa_at_load64_acq(&s->keyhash) == h) return idx; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->keyhash) == h) return idx; |
0 |
0 |
0 |
|
| 315 |
|
| } |
| 316 |
|
| } |
| 317 |
|
| |
| 318 |
|
| /* Every slot in reach holds a bucket somebody is still spending from. Take |
| 319 |
|
| * the home slot, which resets ONE live bucket: the victim gets more |
| 320 |
|
| * requests than it should, never fewer, so a table that is too small |
| 321 |
|
| * cannot turn into an outage. */ |
| 322 |
|
| { |
| 323 |
1937 |
| sa_rate_slot *s = &r->slots[home]; |
| 324 |
1937 |
| uint64_t have = sa_at_load64_acq(&s->keyhash); |
| 325 |
1937 |
▶ | if (have != h) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (have != h) { |
1937 |
0 |
1937 |
|
| 326 |
1937 |
▶ | if (sa_at_cas64(&s->keyhash, have, h)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&s->keyhash, have, h)) { |
1937 |
0 |
1937 |
|
| 327 |
1937 |
| sa_at_store64_rel(&s->state, SA_RATE_STATE(r->burst_u, now)); |
| 328 |
1937 |
▶ | if (took_over) *took_over = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (took_over) *took_over = 1; |
1937 |
0 |
1937 |
|
| 329 |
|
| } |
| 330 |
|
| } |
| 331 |
|
| } |
| 332 |
1937 |
| return home; |
| 333 |
|
| } |
| 334 |
|
| |
| 335 |
|
| /* Take `cost_u` from the key's bucket. |
| 336 |
|
| * |
| 337 |
|
| * Returns 1 when the request is allowed, 0 when it is not. `*left_u` is what |
| 338 |
|
| * remains afterwards and `*retry_ms` how long until the bucket holds enough, |
| 339 |
|
| * both filled whether the answer was yes or no, because the caller wants them |
| 340 |
|
| * for its headers either way. |
| 341 |
|
| * |
| 342 |
|
| * `peek` takes nothing and only reports, for a caller that wants to show a |
| 343 |
|
| * budget without spending one. */ |
| 344 |
8613 |
| static int sa_rate_take(sa_rate *r, const char *key, uint32_t klen, |
| 345 |
|
| uint64_t cost_u, int peek, |
| 346 |
|
| uint64_t *left_u, uint64_t *retry_ms) |
| 347 |
|
| { |
| 348 |
|
| uint64_t h, idx, state, tokens; |
| 349 |
|
| uint32_t now; |
| 350 |
|
| sa_rate_slot *s; |
| 351 |
8613 |
| int took_over = 0, tries; |
| 352 |
|
| |
| 353 |
8613 |
▶ | if (left_u) *left_u = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (left_u) *left_u = 0; |
79 |
8534 |
8613 |
|
| 354 |
8613 |
▶ | if (retry_ms) *retry_ms = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (retry_ms) *retry_ms = 0; |
24 |
8589 |
8613 |
|
| 355 |
8613 |
▶ | if (!r) return 1; /* no limiter: allowed */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!r) return 1; /* no limiter: allowed */ |
0 |
8613 |
8613 |
|
| 356 |
|
| |
| 357 |
8613 |
| now = sa_rate_now_ms(); |
| 358 |
8613 |
| h = sa_at_fnv(key, (size_t)klen); |
| 359 |
8613 |
▶ | if (!h) h = 1; /* 0 marks an empty slot */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) h = 1; /* 0 marks an empty slot */ |
0 |
8613 |
8613 |
|
| 360 |
|
| |
| 361 |
8613 |
| idx = sa_rate_slot_for(r, h, now, &took_over); |
| 362 |
8613 |
▶ | if (took_over) sa_at_fetch_add64(&r->hdr->evicted, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (took_over) sa_at_fetch_add64(&r->hdr->evicted, 1); |
1937 |
6676 |
8613 |
|
| 363 |
8613 |
| s = &r->slots[idx]; |
| 364 |
|
| |
| 365 |
8613 |
▶ | for (tries = 0; tries < SA_RATE_CAS_TRIES; tries++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (tries = 0; tries < SA_RATE_CAS_TRIES; tries++) { |
8613 |
0 |
8613 |
|
| 366 |
8613 |
| state = sa_at_load64_acq(&s->state); |
| 367 |
8613 |
| tokens = sa_rate_refill(r, state, now); |
| 368 |
|
| |
| 369 |
8613 |
▶ | if (tokens < cost_u) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (tokens < cost_u) { |
2182 |
6431 |
8613 |
|
| 370 |
|
| /* Denied. The refill is written back so the timestamp advances and |
| 371 |
|
| * the next caller does not recompute the same elapsed window from |
| 372 |
|
| * scratch; losing that CAS costs nothing, because whoever won |
| 373 |
|
| * wrote the same answer. |
| 374 |
|
| * |
| 375 |
|
| * NOT WHEN PEEKING. `remaining` is asked from a status page and |
| 376 |
|
| * from a header, and a read that writes is a read two processes |
| 377 |
|
| * can contend on for nothing. */ |
| 378 |
2182 |
▶ | if (!peek) |
Branch: 1 branch
| Branch | True | False | Total |
| if (!peek) |
2163 |
19 |
2182 |
|
| 379 |
2163 |
| (void)sa_at_cas64(&s->state, state, |
| 380 |
2163 |
| SA_RATE_STATE(tokens, sa_rate_stamp(state, now))); |
| 381 |
2182 |
▶ | if (left_u) *left_u = tokens; |
Branch: 1 branch
| Branch | True | False | Total |
| if (left_u) *left_u = tokens; |
13 |
2169 |
2182 |
|
| 382 |
2182 |
▶ | if (retry_ms && r->burst_u) |
Branch: 2 branches
| Branch | True | False | Total |
| if (retry_ms && r->burst_u) |
10 |
2172 |
2182 |
| if (retry_ms && r->burst_u) |
10 |
0 |
10 |
|
| 383 |
10 |
| *retry_ms = ((cost_u - tokens) * r->window_ms + r->burst_u - 1) |
| 384 |
10 |
| / r->burst_u; |
| 385 |
2182 |
▶ | if (!peek) sa_at_fetch_add64(&r->hdr->denied, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!peek) sa_at_fetch_add64(&r->hdr->denied, 1); |
2163 |
19 |
2182 |
|
| 386 |
2182 |
| return 0; |
| 387 |
|
| } |
| 388 |
|
| |
| 389 |
6431 |
▶ | if (peek) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (peek) { |
63 |
6368 |
6431 |
|
| 390 |
63 |
▶ | if (left_u) *left_u = tokens; |
Branch: 1 branch
| Branch | True | False | Total |
| if (left_u) *left_u = tokens; |
58 |
5 |
63 |
|
| 391 |
63 |
| return 1; |
| 392 |
|
| } |
| 393 |
6368 |
▶ | if (sa_at_cas64(&s->state, state, |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_cas64(&s->state, state, |
6368 |
0 |
6368 |
|
| 394 |
6368 |
| SA_RATE_STATE(tokens - cost_u, sa_rate_stamp(state, now)))) { |
| 395 |
6368 |
▶ | if (left_u) *left_u = tokens - cost_u; |
Branch: 1 branch
| Branch | True | False | Total |
| if (left_u) *left_u = tokens - cost_u; |
8 |
6360 |
6368 |
|
| 396 |
6368 |
| sa_at_fetch_add64(&r->hdr->allowed, 1); |
| 397 |
6368 |
| return 1; |
| 398 |
|
| } |
| 399 |
|
| /* Somebody else spent from this bucket first. Read it again. */ |
| 400 |
|
| } |
| 401 |
|
| |
| 402 |
|
| /* FAILS OPEN, AND SAYS SO. Under contention this heavy the honest answer |
| 403 |
|
| * is that the limiter did not get to decide, and an operator needs to know |
| 404 |
|
| * that rather than reading a clean `denied` count and believing it. */ |
| 405 |
0 |
| sa_at_fetch_add64(&r->hdr->contended, 1); |
| 406 |
0 |
▶ | if (left_u) *left_u = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (left_u) *left_u = 0; |
0 |
0 |
0 |
|
| 407 |
0 |
| return 1; |
| 408 |
|
| } |
| 409 |
|
| |
| 410 |
|
| /* Refill one key to full, for an operator lifting a limit by hand. */ |
| 411 |
2 |
| static void sa_rate_reset_key(sa_rate *r, const char *key, uint32_t klen) { |
| 412 |
|
| uint64_t h, idx; |
| 413 |
|
| uint32_t now; |
| 414 |
2 |
▶ | if (!r) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!r) return; |
0 |
2 |
2 |
|
| 415 |
2 |
| now = sa_rate_now_ms(); |
| 416 |
2 |
| h = sa_at_fnv(key, (size_t)klen); |
| 417 |
2 |
▶ | if (!h) h = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) h = 1; |
0 |
2 |
2 |
|
| 418 |
2 |
| idx = sa_rate_slot_for(r, h, now, NULL); |
| 419 |
2 |
| sa_at_store64_rel(&r->slots[idx].state, SA_RATE_STATE(r->burst_u, now)); |
| 420 |
|
| } |
| 421 |
|
| |
| 422 |
|
| /* Give the key's slot back, so the table has room for somebody else. */ |
| 423 |
2 |
| static void sa_rate_forget(sa_rate *r, const char *key, uint32_t klen) { |
| 424 |
|
| uint64_t h, home, i; |
| 425 |
2 |
▶ | if (!r) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!r) return; |
0 |
2 |
2 |
|
| 426 |
2 |
| h = sa_at_fnv(key, (size_t)klen); |
| 427 |
2 |
▶ | if (!h) h = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) h = 1; |
0 |
2 |
2 |
|
| 428 |
2 |
| home = h & r->mask; |
| 429 |
2 |
▶ | for (i = 0; i < SA_RATE_PROBE; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < SA_RATE_PROBE; i++) { |
2 |
0 |
2 |
|
| 430 |
2 |
| uint64_t idx = (home + i) & r->mask; |
| 431 |
2 |
▶ | if (sa_at_load64_acq(&r->slots[idx].keyhash) == h) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&r->slots[idx].keyhash) == h) { |
2 |
0 |
2 |
|
| 432 |
2 |
| sa_at_store64_rel(&r->slots[idx].state, 0); |
| 433 |
2 |
| sa_at_store64_rel(&r->slots[idx].keyhash, 0); |
| 434 |
2 |
| return; |
| 435 |
|
| } |
| 436 |
|
| } |
| 437 |
|
| } |
| 438 |
|
| |
| 439 |
|
| /* How many slots hold a key. Walks the table, so this is for a status page. */ |
| 440 |
5 |
| static uint64_t sa_rate_used(sa_rate *r) { |
| 441 |
5 |
| uint64_t i, n = 0; |
| 442 |
5 |
▶ | if (!r) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!r) return 0; |
0 |
5 |
5 |
|
| 443 |
709 |
▶ | for (i = 0; i < r->nslots; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->nslots; i++) |
704 |
5 |
709 |
|
| 444 |
704 |
▶ | if (sa_at_load64_acq(&r->slots[i].keyhash)) n++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&r->slots[i].keyhash)) n++; |
69 |
635 |
704 |
|
| 445 |
5 |
| return n; |
| 446 |
|
| } |
| 447 |
|
| |
| 448 |
|
| #else /* !SA_HAVE_ATOMICS */ |
| 449 |
|
| |
| 450 |
|
| /* No atomics, so no limiter: sa_rate_bind refuses. These FAIL OPEN, as the |
| 451 |
|
| * XSUBs do in that build and as a NULL limiter does everywhere: a limiter must |
| 452 |
|
| * never be the reason a good request is refused. */ |
| 453 |
|
| static int sa_rate_take(sa_rate *r, const char *key, uint32_t klen, |
| 454 |
|
| uint64_t cost_u, int peek, |
| 455 |
|
| uint64_t *left_u, uint64_t *retry_ms) |
| 456 |
|
| { |
| 457 |
|
| (void)r; (void)key; (void)klen; (void)cost_u; (void)peek; |
| 458 |
|
| if (left_u) *left_u = 0; |
| 459 |
|
| if (retry_ms) *retry_ms = 0; |
| 460 |
|
| return 1; |
| 461 |
|
| } |
| 462 |
|
| |
| 463 |
|
| static void sa_rate_reset_key(sa_rate *r, const char *key, uint32_t klen) { |
| 464 |
|
| (void)r; (void)key; (void)klen; |
| 465 |
|
| } |
| 466 |
|
| |
| 467 |
|
| static void sa_rate_forget(sa_rate *r, const char *key, uint32_t klen) { |
| 468 |
|
| (void)r; (void)key; (void)klen; |
| 469 |
|
| } |
| 470 |
|
| |
| 471 |
|
| static uint64_t sa_rate_used(sa_rate *r) { (void)r; return 0; } |
| 472 |
|
| |
| 473 |
|
| #endif /* SA_HAVE_ATOMICS */ |
| 474 |
|
| |
| 475 |
|
| #endif /* SA_RATE_H */ |