include/sa/sa_cuckoo.h

filter: Statementstmt 91.7% 190 / 207 Branchbran 66.3% 138 / 208 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 79.0% 328 / 415 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_hash.h ↑ Summary xs/bloom.xs »
1 #ifndef SA_CUCKOO_H
2 #define SA_CUCKOO_H
3  
4 /* sa_cuckoo.h - a set that answers "no" exactly and "yes" probably, and can
5 * forget. Perl-free.
6 *
7 * ---- the question the bloom filter cannot answer ---------------------------
8 *
9 * A bloom filter never forgets, so a set whose members EXPIRE - nonces inside a
10 * replay window, sessions that end, jobs that finish - has to be rotated whole
11 * rather than tidied. This one stores a short FINGERPRINT per key in one of two
12 * buckets, and a fingerprint that was put somewhere can be taken out again.
13 *
14 * Each key hashes to a 16-bit fingerprint and a home bucket. Its other bucket
15 * is derived from the home and the fingerprint ALONE, which is the part that
16 * matters: a fingerprint can be moved to its other bucket without the key, so a
17 * full bucket makes room by moving an occupant rather than by refusing.
18 *
19 * ---- one bucket is one word ------------------------------------------------
20 *
21 * Four 16-bit fingerprints to a bucket, and a bucket is exactly one 64-bit
22 * word. That is most of the concurrency design:
23 *
24 * - a check is two atomic loads and no lock;
25 * - an add into a bucket with room is one compare-and-swap, and so is a
26 * remove, so neither takes a lock either;
27 * - two processes writing one bucket lose a CAS and look again, rather than
28 * one of them overwriting the other.
29 *
30 * The rate follows from the width. An absent key is reported present when one
31 * of the eight fingerprints in its two buckets happens to equal its own, so the
32 * rate is about 8 * load / 65535: 0.011% at the 90% a filter is sized to reach
33 * at its capacity, and it FALLS as keys are removed. It cannot be tuned, and
34 * that is the trade - a caller who needs a different rate wants the bloom
35 * filter.
36 *
37 * ---- any number of buckets, not only a power of two -------------------------
38 *
39 * The usual cuckoo filter finds the other bucket as `i XOR h(fp)`, which only
40 * stays in range when the bucket count is a power of two, so a filter sized for
41 * a million keys is rounded up to space for two million. Here the other bucket
42 * is `(h(fp) - i) mod n`. That is its own inverse - applied twice it gives back
43 * `i` - which is the only property the scheme needs, and it works for any n.
44 * The home bucket comes from a multiply and a shift rather than a division, so
45 * neither costs one.
46 *
47 * ---- moving keys without losing one -----------------------------------------
48 *
49 * The textbook insert kicks a victim out, puts the new key in its place, and
50 * carries the victim to its other bucket, repeating. For the length of that
51 * walk the victim is in NO bucket, and a check arriving then says "no" about a
52 * key that was added - the one answer this structure promises never to give.
53 * And when the walk runs out of steps, the victim is simply gone.
54 *
55 * So a relocation is PLANNED FIRST and moved LAST-FIRST. A breadth-first search
56 * reads the table without changing it and finds a chain of occupants ending at
57 * an empty slot. The chain is then walked back from the empty end: the last
58 * occupant moves into the empty slot, which frees the slot the one before it
59 * needs, and so on to the front, where the new key goes in. Every step is COPY,
60 * THEN DELETE - a fingerprint is written into its new bucket before it is taken
61 * out of its old one - so at every instant each key is in at least one of its
62 * buckets. A search that finds no chain refuses the add, and nothing already
63 * stored has moved.
64 *
65 * Every step is also a CAS, so a writer that changed the table since the plan
66 * was read makes a step fail rather than be overwritten, and the plan is made
67 * again.
68 *
69 * ---- the one read that copy-then-delete does not protect -------------------
70 *
71 * A check reads its two buckets one after the other. If a fingerprint moves
72 * from the second to the first IN BETWEEN - written into the first after the
73 * check read it, taken out of the second before the check reads that - the
74 * check saw it in neither.
75 *
76 * `moves` closes it. A relocation bumps it between the copy and the delete of
77 * every step, and a check that found nothing compares it before and after:
78 * unchanged means no move overlapped the two reads, so the miss is exact.
79 * Changed means look again. A check that keeps losing that race gives up and
80 * says "probably" - which is always an allowed answer, so a "no" stays exact
81 * even then. `moves` is never reset, because a counter that went back to a
82 * value a reader had already seen would tell it nothing had happened.
83 *
84 * Only a MISS pays for the comparison. A hit is right whatever moved.
85 *
86 * ---- one relocator at a time, and a dead one does not count -----------------
87 *
88 * Relocations are serialised by one lock per filter, because two plans walking
89 * through the same buckets mostly defeat each other. They only happen when both
90 * of a key's buckets are full, so the lock is uncontended until the filter is
91 * nearly full.
92 *
93 * THE LOCK IS FOR PROGRESS, NOT FOR SAFETY. Every step is a CAS against what
94 * is actually there and keeps each key in at least one bucket, so two
95 * relocators running at once cannot lose a key between them.
96 *
97 * It is a WORD HOLDING THE OWNER'S PID rather than a stripe byte, because a
98 * process killed holding a stripe byte holds it for ever, and this is the only
99 * lock for the whole filter: one SIGKILL at the wrong moment would refuse every
100 * later add that needs room made. A waiter that has spun its budget asks
101 * whether the owner is still running, and takes the lock over if it is not.
102 * The worst a dead relocator leaves behind is one fingerprint copied into its
103 * new bucket and not yet deleted from its old one - a key stored twice, which
104 * reads as present, which it is.
105 *
106 * Needs sa_arena.h and sa_peer.h.
107 */
108  
109 #include "sa/sa_arena.h"
110 #include "sa/sa_peer.h"
111  
112 #define SA_CUCKOO_MAGIC 0x4B435543u /* 'C','U','C','K' little-endian */
113  
114 #define SA_CK_LANES 4 /* fingerprints to a bucket, and a word */
115 #define SA_CK_FILL_PCT 90 /* how full `capacity` keys make it */
116 #define SA_CK_MIN_BUCKETS 64
117 #define SA_CK_MAX_BUCKETS ((uint64_t)1 << 32) /* the multiply-shift's range */
118 #define SA_CK_BFS_MAX 512 /* buckets one plan may read */
119 #define SA_CK_CHAIN_MAX 16 /* steps one plan may take */
120 #define SA_CK_PLANS 8 /* plans before an add is refused */
121 #define SA_CK_RETRIES 16 /* looks before a check says "probably" */
122 #define SA_CK_LOCK_SPIN 2000
123 #define SA_CK_LOCK_ROUNDS 64
124 #define SA_CK_LOCK_STALL_US 50
125  
126 typedef struct {
127 volatile uint32_t magic; /* published LAST at init */
128 uint32_t lanes; /* SA_CK_LANES, so a later build cannot
129 * misread one made by this one */
130 /* A test hook, and a FIELD rather than an #ifdef for the reason the
131 * region's is: a forked child has to honour it. Zero unless a test sets
132 * it. See sa_cuckoo_check for what it widens and why that has to be. */
133 volatile uint32_t stall_us;
134 uint32_t spare;
135 uint64_t buckets; /* any count, not only a power of two */
136 uint64_t words_off; /* from the FILTER's base */
137 uint64_t capacity; /* the n it was sized for */
138 volatile uint64_t count; /* fingerprints stored */
139 volatile uint64_t moves; /* relocation steps ever taken; NEVER reset */
140 volatile uint64_t kicks; /* adds that needed room made */
141 volatile uint64_t full; /* adds refused */
142 volatile uint64_t owner; /* pid holding the relocation lock, or 0 */
143 volatile uint64_t recovered; /* locks taken over from a dead owner */
144 volatile unsigned char locks[SA_LOCK_STRIPES];
145 } sa_cuckoo_hdr;
146  
147 #ifndef SA_CUCKOO_FWD
148 #define SA_CUCKOO_FWD
149 typedef struct sa_cuckoo sa_cuckoo;
150 #endif
151  
152 struct sa_cuckoo {
153 sa_region *arena;
154 sa_cuckoo_hdr *hdr;
155 volatile uint64_t *words;
156 uint64_t buckets;
157 };
158  
159 /* Where a key lives: its fingerprint and both of its buckets. */
160 typedef struct {
161 uint64_t i1;
162 uint64_t i2;
163 uint16_t fp;
164 } sa_ck_key;
165  
166 /* Enough buckets that `capacity` keys fill SA_CK_FILL_PCT of the slots. Past
167 * that there is still room - a cuckoo filter of four-slot buckets reaches about
168 * 95% before the search starts failing - but it is room the caller did not ask
169 * for, and the rate quoted for a filter is the rate at its capacity. */
170 21 static uint64_t sa_cuckoo_buckets(uint64_t capacity) {
171 21 uint64_t per = (uint64_t)SA_CK_LANES * SA_CK_FILL_PCT;
172 uint64_t b;
173 21 ▶ if (capacity < 1) capacity = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (capacity < 1) capacity = 1; 0 21 21
174 21 ▶ if (capacity > SA_CK_MAX_BUCKETS * 3u) capacity = SA_CK_MAX_BUCKETS * 3u;
Branch: 1 branch
BranchTrueFalseTotal
if (capacity > SA_CK_MAX_BUCKETS * 3u) capacity = SA_CK_MAX_BUCKETS * 3u; 0 21 21
175 21 b = (capacity * 100u + per - 1u) / per;
176 21 ▶ if (b < SA_CK_MIN_BUCKETS) b = SA_CK_MIN_BUCKETS;
Branch: 1 branch
BranchTrueFalseTotal
if (b < SA_CK_MIN_BUCKETS) b = SA_CK_MIN_BUCKETS; 6 15 21
177 21 ▶ if (b > SA_CK_MAX_BUCKETS) b = SA_CK_MAX_BUCKETS;
Branch: 1 branch
BranchTrueFalseTotal
if (b > SA_CK_MAX_BUCKETS) b = SA_CK_MAX_BUCKETS; 0 21 21
178 21 return b;
179 }
180  
181 79 static uint64_t sa_cuckoo_bytes(uint64_t buckets) {
182 79 return sa_align_up((uint64_t)sizeof(sa_cuckoo_hdr)) + buckets * 8u;
183 }
184  
185 /* The finalising mix, applied to the key's hash so the fingerprint and the
186 * bucket come from well-mixed bits, and to the fingerprint to find the other
187 * bucket. */
188 905094 static uint64_t sa_ck_mix(uint64_t h) {
189 905094 h ^= h >> 33;
190 905094 h *= 0xff51afd7ed558ccdULL;
191 905094 h ^= h >> 33;
192 905094 h *= 0xc4ceb9fe1a85ec53ULL;
193 905094 h ^= h >> 33;
194 905094 return h;
195 }
196  
197 /* The top 32 bits of h, scaled into [0, n). A multiply and a shift, and exact
198 * for any n up to 2^32. */
199 905094 static uint64_t sa_ck_range(uint64_t h, uint64_t n) {
200 905094 return ((h >> 32) * n) >> 32;
201 }
202  
203 /* The other bucket. Depends on the bucket and the fingerprint and nothing
204 * else, which is what lets a fingerprint move without its key. */
205 776757 static uint64_t sa_ck_alt(uint64_t i, uint16_t fp, uint64_t n) {
206 776757 uint64_t h = sa_ck_range(sa_ck_mix((uint64_t)fp), n);
207 776757 ▶ return h >= i ? h - i : h + n - i;
Branch: 1 branch
BranchTrueFalseTotal
return h >= i ? h - i : h + n - i; 401396 375361 776757
208 }
209  
210 /* Zero is an empty lane, so no fingerprint may be zero. */
211 128337 static void sa_ck_hash(const sa_cuckoo *c, const char *key, uint32_t klen,
212 sa_ck_key *k)
213 {
214 128337 uint64_t h = sa_ck_mix(sa_at_fnv(key, (size_t)klen));
215 128337 k->fp = (uint16_t)(h & 0xFFFFu);
216 128337 ▶ if (!k->fp) k->fp = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!k->fp) k->fp = 1; 2 128335 128337
217 128337 k->i1 = sa_ck_range(h, c->buckets);
218 128337 k->i2 = sa_ck_alt(k->i1, k->fp, c->buckets);
219 128337 }
220  
221 #define SA_CK_LANE(w, l) ((uint16_t)(((w) >> ((l) * 16)) & 0xFFFFu))
222  
223 145524 static int sa_ck_has(uint64_t w, uint16_t fp) {
224 134873 ▶ return SA_CK_LANE(w, 0) == fp || SA_CK_LANE(w, 1) == fp
Branch: 1 branch
BranchTrueFalseTotal
return SA_CK_LANE(w, 0) == fp || SA_CK_LANE(w, 1) == fp 124945 9928 134873
225 280397 ▶ || SA_CK_LANE(w, 2) == fp || SA_CK_LANE(w, 3) == fp;
Branch: 3 branches
BranchTrueFalseTotal
|| SA_CK_LANE(w, 2) == fp || SA_CK_LANE(w, 3) == fp; 134873 10651 145524
|| SA_CK_LANE(w, 2) == fp || SA_CK_LANE(w, 3) == fp; 116008 8937 124945
|| SA_CK_LANE(w, 2) == fp || SA_CK_LANE(w, 3) == fp; 7239 108769 116008
226 }
227  
228 19 static sa_cuckoo *sa_cuckoo_bind(sa_region *arena, sa_reg *e,
229 uint64_t buckets, uint64_t capacity, int *err)
230 {
231 #if !SA_HAVE_ATOMICS
232 (void)arena; (void)e; (void)buckets; (void)capacity;
233 if (err) *err = SA_E_NOATOMICS;
234 return NULL;
235 #else
236 sa_cuckoo *c;
237 sa_cuckoo_hdr *h;
238 uint64_t hash;
239  
240 19 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 19 0 19
241 19 ▶ 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; } 19 0 19
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 19 19
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
242  
243 19 h = (sa_cuckoo_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_cuckoo_hdr));
244 19 ▶ 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 19 19
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
245  
246 19 ▶ if (sa_at_load32_acq(&h->magic) != SA_CUCKOO_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CUCKOO_MAGIC) { 17 2 19
247 17 hash = sa_at_fnv(e->name, strlen(e->name));
248 17 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 17 0 17
249 17 ▶ if (sa_at_load32_acq(&h->magic) != SA_CUCKOO_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CUCKOO_MAGIC) { 17 0 17
250 17 ▶ if (!buckets || sa_cuckoo_bytes(buckets) > e->len) {
Branch: 2 branches
BranchTrueFalseTotal
if (!buckets || sa_cuckoo_bytes(buckets) > e->len) { 17 0 17
if (!buckets || sa_cuckoo_bytes(buckets) > e->len) { 0 17 17
251 0 sa_at_unlock(h->locks, hash);
252 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
253 0 return NULL;
254 }
255 17 memset((void *)h, 0, (size_t)sa_cuckoo_bytes(buckets));
256 17 h->lanes = SA_CK_LANES;
257 17 h->buckets = buckets;
258 17 h->words_off = sa_align_up((uint64_t)sizeof(sa_cuckoo_hdr));
259 17 h->capacity = capacity;
260 17 sa_at_store32_rel(&h->magic, SA_CUCKOO_MAGIC);
261 }
262 17 sa_at_unlock(h->locks, hash);
263 }
264 17 ▶ if (!sa_wait_magic32(&h->magic, SA_CUCKOO_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_CUCKOO_MAGIC)) { 0 17 17
265 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
266 0 return NULL;
267 }
268 }
269  
270 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
271 *
272 * A process that finds the magic already set reads the shape out of the
273 * shared header, and a header claiming more buckets than the entry holds
274 * would put every later read past the end of the mapping. So the shape is
275 * checked against the entry's length whoever initialised it, and against
276 * what this caller asked for. */
277 19 ▶ if (h->lanes != SA_CK_LANES || !h->buckets
Branch: 2 branches
BranchTrueFalseTotal
if (h->lanes != SA_CK_LANES || !h->buckets 19 0 19
if (h->lanes != SA_CK_LANES || !h->buckets 19 0 19
278 19 ▶ || h->buckets > SA_CK_MAX_BUCKETS
Branch: 1 branch
BranchTrueFalseTotal
|| h->buckets > SA_CK_MAX_BUCKETS 19 0 19
279 19 ▶ || h->words_off != sa_align_up((uint64_t)sizeof(sa_cuckoo_hdr))
Branch: 1 branch
BranchTrueFalseTotal
|| h->words_off != sa_align_up((uint64_t)sizeof(sa_cuckoo_hdr)) 19 0 19
280 19 ▶ || sa_cuckoo_bytes(h->buckets) > e->len
Branch: 1 branch
BranchTrueFalseTotal
|| sa_cuckoo_bytes(h->buckets) > e->len 19 0 19
281 19 ▶ || (buckets && h->buckets != buckets)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (buckets && h->buckets != buckets)) { 19 0 19
|| (buckets && h->buckets != buckets)) { 1 18 19
282 1 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 1 0 1
283 1 return NULL;
284 }
285  
286 18 c = (sa_cuckoo *)calloc(1, sizeof(sa_cuckoo));
287 18 ▶ if (!c) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!c) { if (err) *err = SA_E_NOMEM; return NULL; } 0 18 18
if (!c) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
288 18 c->arena = arena;
289 18 c->hdr = h;
290 18 c->words = (volatile uint64_t *)((char *)h + (size_t)h->words_off);
291 18 c->buckets = h->buckets;
292 18 return c;
293 #endif
294 }
295  
296 18 static void sa_cuckoo_free(sa_cuckoo *c) { free(c); }
297  
298 #if SA_HAVE_ATOMICS
299  
300 /* Put one copy of fp into any empty lane. 1 if it went in, 0 if the bucket is
301 * full. A lost CAS means another writer changed some lane of this word, so it
302 * is read again rather than given up on - bounded, like every wait here. */
303 66319 static int sa_ck_put(volatile uint64_t *word, uint16_t fp) {
304 long spin;
305 66319 ▶ for (spin = 0; spin < SA_SPIN_MAX; spin++) {
Branch: 1 branch
BranchTrueFalseTotal
for (spin = 0; spin < SA_SPIN_MAX; spin++) { 66319 0 66319
306 66319 uint64_t w = sa_at_load64_acq(word);
307 int l;
308 214154 ▶ for (l = 0; l < SA_CK_LANES; l++)
Branch: 1 branch
BranchTrueFalseTotal
for (l = 0; l < SA_CK_LANES; l++) 191282 22872 214154
309 191282 ▶ if (!SA_CK_LANE(w, l)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!SA_CK_LANE(w, l)) break; 43447 147835 191282
310 66319 ▶ if (l == SA_CK_LANES) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (l == SA_CK_LANES) return 0; 22872 43447 66319
311 43447 ▶ if (sa_at_cas64(word, w, w | ((uint64_t)fp << (l * 16)))) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(word, w, w | ((uint64_t)fp << (l * 16)))) return 1; 43447 0 43447
312 }
313 0 return 0;
314 }
315  
316 /* Take one copy of fp out of whichever lane holds it. Copies of one
317 * fingerprint in one bucket are interchangeable - same fingerprint, same
318 * bucket, so the same other bucket - which is why any lane will do. */
319 4537 static int sa_ck_take(volatile uint64_t *word, uint16_t fp) {
320 long spin;
321 4537 ▶ for (spin = 0; spin < SA_SPIN_MAX; spin++) {
Branch: 1 branch
BranchTrueFalseTotal
for (spin = 0; spin < SA_SPIN_MAX; spin++) { 4537 0 4537
322 4537 uint64_t w = sa_at_load64_acq(word);
323 int l;
324 8725 ▶ for (l = 0; l < SA_CK_LANES; l++)
Branch: 1 branch
BranchTrueFalseTotal
for (l = 0; l < SA_CK_LANES; l++) 8706 19 8725
325 8706 ▶ if (SA_CK_LANE(w, l) == fp) break;
Branch: 1 branch
BranchTrueFalseTotal
if (SA_CK_LANE(w, l) == fp) break; 4518 4188 8706
326 4537 ▶ if (l == SA_CK_LANES) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (l == SA_CK_LANES) return 0; 19 4518 4537
327 4518 ▶ if (sa_at_cas64(word, w, w & ~((uint64_t)0xFFFFu << (l * 16))))
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(word, w, w & ~((uint64_t)0xFFFFu << (l * 16)))) 4518 0 4518
328 4518 return 1;
329 }
330 0 return 0;
331 }
332  
333 /* Down by one, and never below zero. The count can only be driven below the
334 * table's real contents by a reset racing a writer, and a count that wrapped
335 * to eighteen quintillion would say so less usefully than one that stuck. */
336 504 static void sa_ck_count_down(sa_cuckoo *c) {
337 long spin;
338 504 ▶ for (spin = 0; spin < SA_SPIN_MAX; spin++) {
Branch: 1 branch
BranchTrueFalseTotal
for (spin = 0; spin < SA_SPIN_MAX; spin++) { 504 0 504
339 504 uint64_t v = sa_at_load64_acq(&c->hdr->count);
340 504 ▶ if (!v || sa_at_cas64(&c->hdr->count, v, v - 1)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!v || sa_at_cas64(&c->hdr->count, v, v - 1)) return; 504 0 504
if (!v || sa_at_cas64(&c->hdr->count, v, v - 1)) return; 504 0 504
341 }
342 }
343  
344 /* The relocation lock: 1 if taken, 0 if it gave up. Spins, then sleeps, so a
345 * holder that lost its CPU gets it back and hands over rather than every
346 * waiter burning its budget while it is not scheduled. Between rounds, asks
347 * whether the holder is still alive, and takes over from one that is not. */
348 4670 static int sa_ck_lock(sa_cuckoo *c) {
349 4670 volatile uint64_t *o = &c->hdr->owner;
350 4670 uint64_t me = sa_getpid();
351 int round;
352 6334 ▶ for (round = 0; round < SA_CK_LOCK_ROUNDS; round++) {
Branch: 1 branch
BranchTrueFalseTotal
for (round = 0; round < SA_CK_LOCK_ROUNDS; round++) { 6308 26 6334
353 uint64_t cur;
354 long spin;
355 3338308 ▶ for (spin = 0; spin < SA_CK_LOCK_SPIN; spin++)
Branch: 1 branch
BranchTrueFalseTotal
for (spin = 0; spin < SA_CK_LOCK_SPIN; spin++) 3336642 1666 3338308
356 3336642 ▶ if (sa_at_load64_acq(o) == 0 && sa_at_cas64(o, 0, me)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (sa_at_load64_acq(o) == 0 && sa_at_cas64(o, 0, me)) return 1; 4642 3332000 3336642
if (sa_at_load64_acq(o) == 0 && sa_at_cas64(o, 0, me)) return 1; 4642 0 4642
357 /* The holder's pid is compared with our own first: another thread of
358 * this process is alive by definition, and asking the kernel would
359 * only say so. */
360 1666 cur = sa_at_load64_acq(o);
361 1666 ▶ if (cur && cur != me && !sa_pid_alive(cur) && sa_at_cas64(o, cur, me)) {
Branch: 4 branches
BranchTrueFalseTotal
if (cur && cur != me && !sa_pid_alive(cur) && sa_at_cas64(o, cur, me)) { 1666 0 1666
if (cur && cur != me && !sa_pid_alive(cur) && sa_at_cas64(o, cur, me)) { 1666 0 1666
if (cur && cur != me && !sa_pid_alive(cur) && sa_at_cas64(o, cur, me)) { 2 1664 1666
if (cur && cur != me && !sa_pid_alive(cur) && sa_at_cas64(o, cur, me)) { 2 0 2
362 2 sa_at_fetch_add64(&c->hdr->recovered, 1);
363 2 return 1;
364 }
365 1664 sa_stall(SA_CK_LOCK_STALL_US);
366 }
367 26 return 0;
368 }
369  
370 /* A CAS rather than a store: a lock that was taken over from this process in
371 * error - a pid another namespace cannot see, say - is somebody else's now,
372 * and clearing it would free it under them. */
373 4644 static void sa_ck_unlock(sa_cuckoo *c) {
374 4644 (void)sa_at_cas64(&c->hdr->owner, sa_getpid(), 0);
375 4644 }
376  
377 /* One node of a plan: a bucket, the node it was reached from, and the
378 * fingerprint that would move from that node's bucket into this one. */
379 typedef struct {
380 uint64_t bucket;
381 int parent; /* -1 for one of the new key's own two buckets */
382 uint16_t fp;
383 } sa_ck_node;
384  
385 /* Does the chain ending at node n visit any bucket twice? A chain that does
386 * would move a fingerprint into a slot another of its own steps is about to
387 * refill, so it is not used. */
388 3529 static int sa_ck_chain_ok(const sa_ck_node *q, int n) {
389 uint64_t seen[SA_CK_CHAIN_MAX];
390 3529 int len = 0, i;
391 11072 ▶ for (; n >= 0; n = q[n].parent) {
Branch: 1 branch
BranchTrueFalseTotal
for (; n >= 0; n = q[n].parent) { 7543 3529 11072
392 7543 ▶ if (len == SA_CK_CHAIN_MAX) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (len == SA_CK_CHAIN_MAX) return 0; 0 7543 7543
393 12084 ▶ for (i = 0; i < len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) 4541 7543 12084
394 4541 ▶ if (seen[i] == q[n].bucket) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (seen[i] == q[n].bucket) return 0; 0 4541 4541
395 7543 seen[len++] = q[n].bucket;
396 }
397 3529 return 1;
398 }
399  
400 /* Breadth first from the new key's two buckets, reading and never writing, to
401 * the nearest bucket with an empty lane. Returns that node, or -1 when there is
402 * none within SA_CK_BFS_MAX buckets - which is what "full" means here. */
403 4642 static int sa_ck_plan(sa_cuckoo *c, const sa_ck_key *k, sa_ck_node *q) {
404 4642 int head, tail = 0;
405  
406 4642 q[tail].bucket = k->i1; q[tail].parent = -1; q[tail].fp = 0; tail++;
407 4642 ▶ if (k->i2 != k->i1) {
Branch: 1 branch
BranchTrueFalseTotal
if (k->i2 != k->i1) { 4638 4 4642
408 4638 q[tail].bucket = k->i2; q[tail].parent = -1; q[tail].fp = 0; tail++;
409 }
410  
411 595983 ▶ for (head = 0; head < tail; head++) {
Branch: 1 branch
BranchTrueFalseTotal
for (head = 0; head < tail; head++) { 594870 1113 595983
412 594870 uint64_t w = sa_at_load64_acq(&c->words[q[head].bucket]);
413 int l, j;
414  
415 2967840 ▶ for (l = 0; l < SA_CK_LANES; l++)
Branch: 1 branch
BranchTrueFalseTotal
for (l = 0; l < SA_CK_LANES; l++) 2376499 591341 2967840
416 2376499 ▶ if (!SA_CK_LANE(w, l)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!SA_CK_LANE(w, l)) break; 3529 2372970 2376499
417 594870 ▶ if (l < SA_CK_LANES) {
Branch: 1 branch
BranchTrueFalseTotal
if (l < SA_CK_LANES) { 3529 591341 594870
418 3529 ▶ if (sa_ck_chain_ok(q, head)) return head;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_chain_ok(q, head)) return head; 3529 0 3529
419 0 continue;
420 }
421  
422 1241291 ▶ for (l = 0; l < SA_CK_LANES && tail < SA_CK_BFS_MAX; l++) {
Branch: 2 branches
BranchTrueFalseTotal
for (l = 0; l < SA_CK_LANES && tail < SA_CK_BFS_MAX; l++) { 1079364 161927 1241291
for (l = 0; l < SA_CK_LANES && tail < SA_CK_BFS_MAX; l++) { 649950 429414 1079364
423 649950 uint16_t v = SA_CK_LANE(w, l);
424 /* Two copies of one fingerprint go to the same place, so the
425 * second would only spend the budget reading it again. */
426 1619577 ▶ for (j = 0; j < l; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < l; j++) 971157 648420 1619577
427 971157 ▶ if (SA_CK_LANE(w, j) == v) break;
Branch: 1 branch
BranchTrueFalseTotal
if (SA_CK_LANE(w, j) == v) break; 1530 969627 971157
428 649950 ▶ if (j < l) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (j < l) continue; 1530 648420 649950
429 648420 q[tail].bucket = sa_ck_alt(q[head].bucket, v, c->buckets);
430 648420 q[tail].parent = head;
431 648420 q[tail].fp = v;
432 648420 tail++;
433 }
434 }
435 1113 return -1;
436 }
437  
438 /* Walk the chain back from its empty end. Each step is copy, count, delete:
439 * the fingerprint is written into its new bucket before it leaves its old one,
440 * and `moves` is bumped between the two, which is what a check that misses
441 * compares. 1 if the new key went in at the front. */
442 3529 static int sa_ck_walk(sa_cuckoo *c, const sa_ck_node *q, int n, uint16_t fp) {
443 7543 ▶ while (q[n].parent >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (q[n].parent >= 0) { 4014 3529 7543
444 4014 uint64_t to = q[n].bucket;
445 4014 uint64_t from = q[q[n].parent].bucket;
446 /* Filled since the plan was read: stop, and plan again. What has
447 * already moved is in its other bucket, which is a valid place. */
448 4014 ▶ if (!sa_ck_put(&c->words[to], q[n].fp)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_ck_put(&c->words[to], q[n].fp)) return 0; 0 4014 4014
449 4014 sa_at_fetch_add64(&c->hdr->moves, 1);
450 /* Gone from its old bucket means somebody removed it while it was in
451 * both, so there is now one copy too many - and the one to give back
452 * is the one just made. The step after this one finds the room the
453 * remover left, or fails and plans again. */
454 4014 ▶ if (!sa_ck_take(&c->words[from], q[n].fp))
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_ck_take(&c->words[from], q[n].fp)) 0 4014 4014
455 0 (void)sa_ck_take(&c->words[to], q[n].fp);
456 4014 n = q[n].parent;
457 }
458 3529 return sa_ck_put(&c->words[q[n].bucket], fp);
459 }
460  
461 /* Under the lock. 2 when room had appeared by the time the lock was ours, 1
462 * when keys were moved to make it, 0 when there is none to be made. */
463 4642 static int sa_ck_relocate(sa_cuckoo *c, const sa_ck_key *k) {
464 sa_ck_node q[SA_CK_BFS_MAX];
465 int plan;
466 4642 ▶ for (plan = 0; plan < SA_CK_PLANS; plan++) {
Branch: 1 branch
BranchTrueFalseTotal
for (plan = 0; plan < SA_CK_PLANS; plan++) { 4642 0 4642
467 int n;
468 4642 ▶ if (sa_ck_put(&c->words[k->i1], k->fp)
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_put(&c->words[k->i1], k->fp) 4642 0 4642
469 4642 ▶ || sa_ck_put(&c->words[k->i2], k->fp))
Branch: 1 branch
BranchTrueFalseTotal
|| sa_ck_put(&c->words[k->i2], k->fp)) 0 4642 4642
470 0 return 2;
471 4642 n = sa_ck_plan(c, k, q);
472 4642 ▶ if (n < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) return 0; 1113 3529 4642
473 3529 ▶ if (sa_ck_walk(c, q, n, k->fp)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_walk(c, q, n, k->fp)) return 1; 3529 0 3529
474 }
475 0 return 0;
476 }
477  
478 #endif /* SA_HAVE_ATOMICS */
479  
480 /* Add a key: 1 when it is stored, 0 when there is no room for it. A refusal
481 * moves nothing, so every key stored before it is still exactly where a check
482 * will find it.
483 *
484 * EVERY CALL STORES A COPY. A key added twice is in the filter twice and needs
485 * removing twice, and one key can be added at most eight times - its two
486 * buckets, four lanes each - because every copy of it has to live in one of
487 * the same two. */
488 40572 static int sa_cuckoo_add(sa_cuckoo *c, const char *key, uint32_t klen) {
489 #if !SA_HAVE_ATOMICS
490 (void)c; (void)key; (void)klen;
491 return 0;
492 #else
493 sa_ck_key k;
494 40572 int rc = 0;
495  
496 40572 ▶ if (!c) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return 0; 0 40572 40572
497 40572 sa_ck_hash(c, key, klen, &k);
498  
499 40572 ▶ if (sa_ck_put(&c->words[k.i1], k.fp) || sa_ck_put(&c->words[k.i2], k.fp)) {
Branch: 2 branches
BranchTrueFalseTotal
if (sa_ck_put(&c->words[k.i1], k.fp) || sa_ck_put(&c->words[k.i2], k.fp)) { 8920 31652 40572
if (sa_ck_put(&c->words[k.i1], k.fp) || sa_ck_put(&c->words[k.i2], k.fp)) { 4252 4668 8920
500 35904 sa_at_fetch_add64(&c->hdr->count, 1);
501 35904 return 1;
502 }
503  
504 4668 ▶ if (sa_ck_lock(c)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_lock(c)) { 4642 26 4668
505 4642 rc = sa_ck_relocate(c, &k);
506 4642 sa_ck_unlock(c);
507 }
508 4668 ▶ if (!rc) {
Branch: 1 branch
BranchTrueFalseTotal
if (!rc) { 1139 3529 4668
509 1139 sa_at_fetch_add64(&c->hdr->full, 1);
510 1139 return 0;
511 }
512 3529 ▶ if (rc == 1) sa_at_fetch_add64(&c->hdr->kicks, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (rc == 1) sa_at_fetch_add64(&c->hdr->kicks, 1); 3529 0 3529
513 3529 sa_at_fetch_add64(&c->hdr->count, 1);
514 3529 return 1;
515 #endif
516 }
517  
518 /* Has this key probably been added? A 0 is exact; a 1 may be a coincidence of
519 * fingerprints, and is also the answer when this could not be sure - see
520 * `moves` above. */
521 87258 static int sa_cuckoo_check(sa_cuckoo *c, const char *key, uint32_t klen) {
522 #if !SA_HAVE_ATOMICS
523 (void)c; (void)key; (void)klen;
524 return 0;
525 #else
526 sa_ck_key k;
527 int t;
528  
529 87258 ▶ if (!c) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return 0; 0 87258 87258
530 87258 sa_ck_hash(c, key, klen, &k);
531  
532 87258 ▶ for (t = 0; t < SA_CK_RETRIES; t++) {
Branch: 1 branch
BranchTrueFalseTotal
for (t = 0; t < SA_CK_RETRIES; t++) { 87258 0 87258
533 87258 uint64_t m = sa_at_load64_acq(&c->hdr->moves);
534 87258 ▶ if (sa_ck_has(sa_at_load64_acq(&c->words[k.i1]), k.fp)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_has(sa_at_load64_acq(&c->words[k.i1]), k.fp)) return 1; 28992 58266 87258
535 /* THE WINDOW, held open when a test asks. Unwidened it is a few
536 * instructions, and a stress test that races it passes whether or not
537 * the comparison below exists: with it removed, 70,000 relocations
538 * under two readers produced no miss at all. A test that cannot fail
539 * is not evidence, so t/32-cuckoo.t stalls here and relocates
540 * underneath. One load of a header line this already read, and only
541 * on a miss in the first bucket. */
542 58266 ▶ if (c->hdr->stall_us) sa_stall(c->hdr->stall_us);
Branch: 1 branch
BranchTrueFalseTotal
if (c->hdr->stall_us) sa_stall(c->hdr->stall_us); 0 58266 58266
543 58266 ▶ if (sa_ck_has(sa_at_load64_acq(&c->words[k.i2]), k.fp)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_has(sa_at_load64_acq(&c->words[k.i2]), k.fp)) return 1; 7763 50503 58266
544 /* Acquire loads, so this one cannot be satisfied before the two
545 * above were. */
546 50503 ▶ if (sa_at_load64_acq(&c->hdr->moves) == m) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&c->hdr->moves) == m) return 0; 50503 0 50503
547 }
548 0 return 1;
549 #endif
550 }
551  
552 /* Remove one copy of a key: 1 when one was found and taken, 0 when none was.
553 *
554 * ONLY REMOVE WHAT WAS ADDED. A key never added may share its fingerprint and
555 * a bucket with one that was, and removing it takes THAT key's copy - turning
556 * a key that was added into one a check says "no" about. */
557 507 static int sa_cuckoo_remove(sa_cuckoo *c, const char *key, uint32_t klen) {
558 #if !SA_HAVE_ATOMICS
559 (void)c; (void)key; (void)klen;
560 return 0;
561 #else
562 sa_ck_key k;
563 507 int t, got = 0;
564  
565 507 ▶ if (!c) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return 0; 0 507 507
566 507 sa_ck_hash(c, key, klen, &k);
567  
568 /* The same race a check has, and the same counter: a miss is only a miss
569 * if nothing moved while both buckets were being looked at. */
570 1011 ▶ for (t = 0; t < SA_CK_RETRIES && !got; t++) {
Branch: 2 branches
BranchTrueFalseTotal
for (t = 0; t < SA_CK_RETRIES && !got; t++) { 1011 0 1011
for (t = 0; t < SA_CK_RETRIES && !got; t++) { 507 504 1011
571 507 uint64_t m = sa_at_load64_acq(&c->hdr->moves);
572 507 ▶ if (sa_ck_take(&c->words[k.i1], k.fp)
Branch: 1 branch
BranchTrueFalseTotal
if (sa_ck_take(&c->words[k.i1], k.fp) 16 491 507
573 16 ▶ || sa_ck_take(&c->words[k.i2], k.fp))
Branch: 1 branch
BranchTrueFalseTotal
|| sa_ck_take(&c->words[k.i2], k.fp)) 13 3 16
574 504 got = 1;
575 3 ▶ else if (sa_at_load64_acq(&c->hdr->moves) == m)
Branch: 1 branch
BranchTrueFalseTotal
else if (sa_at_load64_acq(&c->hdr->moves) == m) 3 0 3
576 3 return 0;
577 }
578  
579 /* Every look overlapped a move. A check can answer "probably" at this
580 * point; a remove cannot answer anything but the truth, so it stops the
581 * moves and looks once more. */
582 504 ▶ if (!got) {
Branch: 1 branch
BranchTrueFalseTotal
if (!got) { 0 504 504
583 0 ▶ if (!sa_ck_lock(c)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_ck_lock(c)) return 0; 0 0 0
584 0 got = sa_ck_take(&c->words[k.i1], k.fp)
585 0 ▶ || sa_ck_take(&c->words[k.i2], k.fp);
Branch: 2 branches
BranchTrueFalseTotal
|| sa_ck_take(&c->words[k.i2], k.fp); 0 0 0
|| sa_ck_take(&c->words[k.i2], k.fp); 0 0 0
586 0 sa_ck_unlock(c);
587 0 ▶ if (!got) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!got) return 0; 0 0 0
588 }
589  
590 504 sa_ck_count_down(c);
591 504 return 1;
592 #endif
593 }
594  
595 /* Forget everything.
596 *
597 * Under the relocation lock, so no plan is half walked through it. Adds and
598 * removes do not take that lock, so one racing the reset may land either side
599 * of it, and the count can end up describing the other side. `moves` is left
600 * alone - see the note above on why it only ever goes up. */
601 2 static void sa_cuckoo_reset(sa_cuckoo *c) {
602 #if SA_HAVE_ATOMICS
603 uint64_t i;
604 2 ▶ if (!c || !sa_ck_lock(c)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!c || !sa_ck_lock(c)) return; 2 0 2
if (!c || !sa_ck_lock(c)) return; 0 2 2
605 344 ▶ for (i = 0; i < c->buckets; i++) sa_at_store64_rel(&c->words[i], 0);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < c->buckets; i++) sa_at_store64_rel(&c->words[i], 0); 342 2 344
606 2 sa_at_store64_rel(&c->hdr->count, 0);
607 2 sa_at_store64_rel(&c->hdr->kicks, 0);
608 2 sa_at_store64_rel(&c->hdr->full, 0);
609 2 sa_ck_unlock(c);
610 #else
611 (void)c;
612 #endif
613 }
614  
615 #endif /* SA_CUCKOO_H */
« include/sa/sa_hash.h ↑ Summary xs/bloom.xs »