xs/rate.xs

filter: Statementstmt 95.1% 79 / 83 Branchbran 54.8% 34 / 62 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 77.9% 113 / 145 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/region.xs ↑ Summary include/sa/sa_hash.h »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
else if (strEQ(o, "slots")) slots = SvUV(ST(i + 1)); 35 0 35
38 }
39 35 ▶ if (limit < 1) limit = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (limit < 1) limit = 1; 0 35 35
40 35 ▶ if (!(window > 0.0)) window = 60.0;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (items > 2) cost = SvUV(ST(2)); 0 120 120
85 120 ▶ if (cost < 1) cost = 1;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!rl) croak("Shared::Arena::Rate: this limiter is released"); 0 0 0
192 0 ▶ RETVAL = (UV)rl->nslots;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!rl) croak("Shared::Arena::Rate: this limiter is released"); 0 4 4
212 4 ▶ EXTEND(SP, 16);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
« xs/region.xs ↑ Summary include/sa/sa_hash.h »