include/sa/sa_rate.h

filter: Statementstmt 90.4% 133 / 147 Branchbran 60.7% 85 / 140 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 75.9% 218 / 287 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_hist.h ↑ Summary include/sa/sa_lease.h »
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
BranchTrueFalseTotal
if (n < 64) return 64; 0 37 37
154 49 ▶ while (p < n && p < (uint64_t)1 << 40) p <<= 1;
Branch: 2 branches
BranchTrueFalseTotal
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 8641 static uint32_t sa_rate_now_ms(void) {
160 8641 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_RATE_MAGIC) { 36 0 36
185 36 ▶ if (!nslots || !burst_u || !window_ms
Branch: 3 branches
BranchTrueFalseTotal
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
BranchTrueFalseTotal
|| 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_RATE_MAGIC)) { 0 36 36
201 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
|| (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
BranchTrueFalseTotal
|| (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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 39958 static uint64_t sa_rate_refill(const sa_rate *r, uint64_t state, uint32_t now) {
254 39958 uint64_t tokens = SA_RATE_TOKENS(state);
255 39958 int32_t ahead = (int32_t)(now - SA_RATE_WHEN(state));
256 uint32_t elapsed;
257  
258 39958 ▶ if (tokens >= r->burst_u) return r->burst_u;
Branch: 1 branch
BranchTrueFalseTotal
if (tokens >= r->burst_u) return r->burst_u; 2042 37916 39958
259 37916 ▶ if (ahead <= 0) return tokens;
Branch: 1 branch
BranchTrueFalseTotal
if (ahead <= 0) return tokens; 35751 2165 37916
260 2165 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 2165 ▶ if ((uint64_t)elapsed >= r->window_ms) return r->burst_u;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)elapsed >= r->window_ms) return r->burst_u; 11 2154 2165
265 2154 tokens += ((uint64_t)elapsed * r->burst_u) / r->window_ms;
266 2154 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 8550 static uint32_t sa_rate_stamp(uint64_t state, uint32_t now) {
276 8550 uint32_t when = SA_RATE_WHEN(state);
277 8550 ▶ return ((int32_t)(now - when) > 0) ? now : when;
Branch: 1 branch
BranchTrueFalseTotal
return ((int32_t)(now - when) > 0) ? now : when; 90 8460 8550
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 8641 static uint64_t sa_rate_slot_for(sa_rate *r, uint64_t h, uint32_t now,
284 int *took_over)
285 {
286 8641 uint64_t home = h & r->mask;
287 uint64_t i;
288  
289 8641 ▶ if (took_over) *took_over = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (took_over) *took_over = 0; 8632 9 8641
290  
291 39967 ▶ for (i = 0; i < SA_RATE_PROBE; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < SA_RATE_PROBE; i++) { 38030 1937 39967
292 38030 uint64_t idx = (home + i) & r->mask;
293 38030 sa_rate_slot *s = &r->slots[idx];
294 38030 uint64_t have = sa_at_load64_acq(&s->keyhash);
295  
296 38030 ▶ if (have == h) return idx;
Branch: 1 branch
BranchTrueFalseTotal
if (have == h) return idx; 6602 31428 38030
297 31428 ▶ if (!have) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (have != h) { 1937 0 1937
326 1937 ▶ if (sa_at_cas64(&s->keyhash, have, h)) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 8632 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 8632 int took_over = 0, tries;
352  
353 8632 ▶ if (left_u) *left_u = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (left_u) *left_u = 0; 79 8553 8632
354 8632 ▶ if (retry_ms) *retry_ms = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (retry_ms) *retry_ms = 0; 24 8608 8632
355 8632 ▶ if (!r) return 1; /* no limiter: allowed */
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return 1; /* no limiter: allowed */ 0 8632 8632
356  
357 8632 now = sa_rate_now_ms();
358 8632 h = sa_at_fnv(key, (size_t)klen);
359 8632 ▶ if (!h) h = 1; /* 0 marks an empty slot */
Branch: 1 branch
BranchTrueFalseTotal
if (!h) h = 1; /* 0 marks an empty slot */ 0 8632 8632
360  
361 8632 idx = sa_rate_slot_for(r, h, now, &took_over);
362 8632 ▶ if (took_over) sa_at_fetch_add64(&r->hdr->evicted, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (took_over) sa_at_fetch_add64(&r->hdr->evicted, 1); 1937 6695 8632
363 8632 s = &r->slots[idx];
364  
365 8632 ▶ for (tries = 0; tries < SA_RATE_CAS_TRIES; tries++) {
Branch: 1 branch
BranchTrueFalseTotal
for (tries = 0; tries < SA_RATE_CAS_TRIES; tries++) { 8632 0 8632
366 8632 state = sa_at_load64_acq(&s->state);
367 8632 tokens = sa_rate_refill(r, state, now);
368  
369 8632 ▶ if (tokens < cost_u) {
Branch: 1 branch
BranchTrueFalseTotal
if (tokens < cost_u) { 2201 6431 8632
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 2201 ▶ if (!peek)
Branch: 1 branch
BranchTrueFalseTotal
if (!peek) 2181 20 2201
379 2181 (void)sa_at_cas64(&s->state, state,
380 2181 SA_RATE_STATE(tokens, sa_rate_stamp(state, now)));
381 2201 ▶ if (left_u) *left_u = tokens;
Branch: 1 branch
BranchTrueFalseTotal
if (left_u) *left_u = tokens; 14 2187 2201
382 2201 ▶ if (retry_ms && r->burst_u)
Branch: 2 branches
BranchTrueFalseTotal
if (retry_ms && r->burst_u) 10 2191 2201
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 2201 ▶ if (!peek) sa_at_fetch_add64(&r->hdr->denied, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (!peek) sa_at_fetch_add64(&r->hdr->denied, 1); 2181 20 2201
386 2201 return 0;
387 }
388  
389 6431 ▶ if (peek) {
Branch: 1 branch
BranchTrueFalseTotal
if (peek) { 62 6369 6431
390 62 ▶ if (left_u) *left_u = tokens;
Branch: 1 branch
BranchTrueFalseTotal
if (left_u) *left_u = tokens; 57 5 62
391 62 return 1;
392 }
393 6369 ▶ if (sa_at_cas64(&s->state, state,
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(&s->state, state, 6369 0 6369
394 6369 SA_RATE_STATE(tokens - cost_u, sa_rate_stamp(state, now)))) {
395 6369 ▶ if (left_u) *left_u = tokens - cost_u;
Branch: 1 branch
BranchTrueFalseTotal
if (left_u) *left_u = tokens - cost_u; 8 6361 6369
396 6369 sa_at_fetch_add64(&r->hdr->allowed, 1);
397 6369 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!r) return 0; 0 5 5
443 709 ▶ for (i = 0; i < r->nslots; i++)
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 */
« include/sa/sa_hist.h ↑ Summary include/sa/sa_lease.h »