xs/cuckoo.xs

filter: Statementstmt 98.5% 67 / 68 Branchbran 59.0% 26 / 44 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 83.0% 93 / 112 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_cache.h ↑ Summary Arena.xs »
1 # Shared::Arena::Cuckoo - a set that answers "no" exactly, "yes" probably, and
2 # can forget.
3  
4 MODULE = Shared::Arena PACKAGE = Shared::Arena PREFIX = sar_
5  
6 # $arena->cuckoo($name, capacity => N)
7 #
8 # Sized from how many keys it should hold. There is no rate to ask for: the
9 # fingerprint width fixes it, and a caller who needs another wants the bloom
10 # filter.
11 SV *
12 sar_cuckoo(self, name, ...)
13 SV *self
14 SV *name
15 PREINIT:
16 sa_region *arena;
17 sa_reg *e;
18 sa_cuckoo *c;
19 const char *nm;
20 STRLEN nlen;
21 20 UV capacity = 10000;
22 uint64_t buckets;
23 20 int err = SA_E_OK;
24 I32 i;
25 SV *obj;
26 CODE:
27 20 arena = SA_SELF(sa_region, self);
28 20 ▶ if (!arena || !arena->map.base)
Branch: 2 branches
BranchTrueFalseTotal
if (!arena || !arena->map.base) 20 0 20
if (!arena || !arena->map.base) 0 20 20
29 0 croak("Shared::Arena: this region is released");
30 20 nm = SvPV(name, nlen);
31 40 ▶ for (i = 2; i + 1 < items; i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 2; i + 1 < items; i += 2) { 20 20 40
32 20 const char *o = SvPV_nolen(ST(i));
33 20 ▶ if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1));
Branch: 1 branch
BranchTrueFalseTotal
if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1)); 20 0 20
34 }
35 20 buckets = sa_cuckoo_buckets((uint64_t)capacity);
36  
37 20 e = sa_carve(arena, nm, (size_t)nlen, sa_cuckoo_bytes(buckets),
38 SA_T_CUCKOO, &err);
39 20 ▶ if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err));
Branch: 1 branch
BranchTrueFalseTotal
if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); 2 18 20
40  
41 18 c = sa_cuckoo_bind(arena, e, buckets, (uint64_t)capacity, &err);
42 18 ▶ if (!c) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err));
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); 1 17 18
43  
44 17 obj = newSV(0);
45 17 sv_setref_pv(obj, "Shared::Arena::Cuckoo", (void *)c);
46 17 sv_magicext(SvRV(obj), SvRV(self), PERL_MAGIC_ext, NULL, NULL, 0);
47 17 SvREFCNT_inc(SvRV(self));
48 17 RETVAL = obj;
49 OUTPUT:
50 RETVAL
51  
52 MODULE = Shared::Arena PACKAGE = Shared::Arena::Cuckoo PREFIX = sack_
53  
54 # 1 when the key is stored, 0 when there is no room for it. Every call stores a
55 # copy: a key added twice needs removing twice.
56 int
57 sack_add(self, key)
58 SV *self
59 SV *key
60 PREINIT:
61 sa_cuckoo *c;
62 const char *k;
63 STRLEN klen;
64 CODE:
65 1 c = SA_SELF(sa_cuckoo, self);
66 1 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 1 1
67 1 k = SvPV(key, klen);
68 1 RETVAL = sa_cuckoo_add(c, k, (uint32_t)klen);
69 OUTPUT:
70 RETVAL
71  
72 # A false answer is exact. A true one is probably right.
73 int
74 sack_check(self, key)
75 SV *self
76 SV *key
77 PREINIT:
78 sa_cuckoo *c;
79 const char *k;
80 STRLEN klen;
81 CODE:
82 2 c = SA_SELF(sa_cuckoo, self);
83 2 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 2 2
84 2 k = SvPV(key, klen);
85 2 RETVAL = sa_cuckoo_check(c, k, (uint32_t)klen);
86 OUTPUT:
87 RETVAL
88  
89 # 1 when a copy was found and taken out. Only for keys that were added: a key
90 # never added can take another key's copy with it.
91 int
92 sack_remove(self, key)
93 SV *self
94 SV *key
95 PREINIT:
96 sa_cuckoo *c;
97 const char *k;
98 STRLEN klen;
99 CODE:
100 505 c = SA_SELF(sa_cuckoo, self);
101 505 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 505 505
102 505 k = SvPV(key, klen);
103 505 RETVAL = sa_cuckoo_remove(c, k, (uint32_t)klen);
104 OUTPUT:
105 RETVAL
106  
107 void
108 sack_reset(self)
109 SV *self
110 PREINIT:
111 sa_cuckoo *c;
112 CODE:
113 1 c = SA_SELF(sa_cuckoo, self);
114 1 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 1 1
115 1 sa_cuckoo_reset(c);
116  
117 UV
118 sack_count(self)
119 SV *self
120 PREINIT:
121 sa_cuckoo *c;
122 CODE:
123 10232 c = SA_SELF(sa_cuckoo, self);
124 10232 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 10232 10232
125 #if SA_HAVE_ATOMICS
126 10232 RETVAL = (UV)sa_at_load64_acq(&c->hdr->count);
127 #else
128 RETVAL = 0;
129 #endif
130 OUTPUT:
131 RETVAL
132  
133 UV
134 sack_slots(self)
135 SV *self
136 PREINIT:
137 sa_cuckoo *c;
138 CODE:
139 10229 c = SA_SELF(sa_cuckoo, self);
140 10229 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 10229 10229
141 10229 ▶ RETVAL = (UV)(c->buckets * SA_CK_LANES);
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = (UV)(c->buckets * SA_CK_LANES); 0 10229 10229
142 OUTPUT:
143 RETVAL
144  
145 # capacity / slots / buckets / bytes / count / load / fp_rate / kicks / moves /
146 # full / recovered
147 #
148 # `load` is the number to watch: the filter refuses adds somewhere past 0.95,
149 # and `fp_rate` is what the current load makes the chance of a wrong "yes".
150 void
151 sack_stats(self)
152 SV *self
153 PREINIT:
154 sa_cuckoo *c;
155 uint64_t slots, count;
156 double load;
157 PPCODE:
158 5 c = SA_SELF(sa_cuckoo, self);
159 5 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 5 5
160 5 slots = c->buckets * SA_CK_LANES;
161 #if SA_HAVE_ATOMICS
162 5 count = sa_at_load64_acq(&c->hdr->count);
163 #else
164 count = 0;
165 #endif
166 5 ▶ load = slots ? (double)count / (double)slots : 0.0;
Branch: 1 branch
BranchTrueFalseTotal
load = slots ? (double)count / (double)slots : 0.0; 5 0 5
167 5 ▶ EXTEND(SP, 22);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND(SP, 22); 0 5 5
168 5 mPUSHp("capacity", 8); mPUSHu((UV)c->hdr->capacity);
169 5 mPUSHp("slots", 5); mPUSHu((UV)slots);
170 5 mPUSHp("buckets", 7); mPUSHu((UV)c->buckets);
171 5 mPUSHp("bytes", 5); mPUSHu((UV)sa_cuckoo_bytes(c->buckets));
172 5 mPUSHp("count", 5); mPUSHu((UV)count);
173 5 mPUSHp("load", 4); mPUSHn(load);
174 /* Eight fingerprints are compared per check, each matching a random
175 * one with probability 1/65535. */
176 5 mPUSHp("fp_rate", 7); mPUSHn(8.0 * load / 65535.0);
177 #if SA_HAVE_ATOMICS
178 5 mPUSHp("kicks", 5); mPUSHu((UV)sa_at_load64_acq(&c->hdr->kicks));
179 5 mPUSHp("moves", 5); mPUSHu((UV)sa_at_load64_acq(&c->hdr->moves));
180 5 mPUSHp("full", 4); mPUSHu((UV)sa_at_load64_acq(&c->hdr->full));
181 5 mPUSHp("recovered", 9); mPUSHu((UV)sa_at_load64_acq(&c->hdr->recovered));
182 #endif
183  
184 # The pid the relocation lock names, and with an argument, sets it. A test
185 # hook: it is how t/32-cuckoo.t makes a lock holder that has died, without
186 # having to kill one at exactly the wrong instant.
187 UV
188 sack__owner(self, ...)
189 SV *self
190 PREINIT:
191 sa_cuckoo *c;
192 CODE:
193 3 c = SA_SELF(sa_cuckoo, self);
194 3 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 3 3
195 #if SA_HAVE_ATOMICS
196 3 ▶ if (items > 1) sa_at_store64_rel(&c->hdr->owner, (uint64_t)SvUV(ST(1)));
Branch: 1 branch
BranchTrueFalseTotal
if (items > 1) sa_at_store64_rel(&c->hdr->owner, (uint64_t)SvUV(ST(1))); 1 2 3
197 3 RETVAL = (UV)sa_at_load64_acq(&c->hdr->owner);
198 #else
199 RETVAL = 0;
200 #endif
201 OUTPUT:
202 RETVAL
203  
204 # Microseconds every check that misses its first bucket sleeps before reading
205 # its second. A test hook: the window it holds open is otherwise a few
206 # instructions wide, and a test that races it passes whether or not the filter
207 # protects it. Shared by every process on the filter, and zero unless set.
208 UV
209 sack__stall(self, ...)
210 SV *self
211 PREINIT:
212 sa_cuckoo *c;
213 CODE:
214 2 c = SA_SELF(sa_cuckoo, self);
215 2 ▶ if (!c) croak("Shared::Arena::Cuckoo: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!c) croak("Shared::Arena::Cuckoo: this filter is released"); 0 2 2
216 #if SA_HAVE_ATOMICS
217 2 ▶ if (items > 1)
Branch: 1 branch
BranchTrueFalseTotal
if (items > 1) 2 0 2
218 2 sa_at_store32_rel(&c->hdr->stall_us, (uint32_t)SvUV(ST(1)));
219 2 ▶ RETVAL = (UV)sa_at_load32_acq(&c->hdr->stall_us);
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = (UV)sa_at_load32_acq(&c->hdr->stall_us); 0 2 2
220 #else
221 RETVAL = 0;
222 #endif
223 OUTPUT:
224 RETVAL
225  
226 void
227 sack_DESTROY(self)
228 SV *self
229 PREINIT:
230 sa_cuckoo *c;
231 CODE:
232 17 c = SA_SELF(sa_cuckoo, self);
233 17 ▶ if (c) { sa_cuckoo_free(c); sv_setiv(SvRV(self), 0); }
Branch: 1 branch
BranchTrueFalseTotal
if (c) { sa_cuckoo_free(c); sv_setiv(SvRV(self), 0); } 17 0 17
« include/sa/sa_cache.h ↑ Summary Arena.xs »