| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_CUCKOO_MAGIC)) { |
0 |
17 |
17 |
|
| 265 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| || sa_cuckoo_bytes(h->buckets) > e->len |
19 |
0 |
19 |
|
| 281 |
19 |
▶ | || (buckets && h->buckets != buckets)) { |
Branch: 2 branches
| Branch | True | False | Total |
| || (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (l = 0; l < SA_CK_LANES; l++) |
191282 |
22872 |
214154 |
|
| 309 |
191282 |
▶ | if (!SA_CK_LANE(w, l)) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!SA_CK_LANE(w, l)) break; |
43447 |
147835 |
191282 |
|
| 310 |
66319 |
▶ | if (l == SA_CK_LANES) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (l = 0; l < SA_CK_LANES; l++) |
8706 |
19 |
8725 |
|
| 325 |
8706 |
▶ | if (SA_CK_LANE(w, l) == fp) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (SA_CK_LANE(w, l) == fp) break; |
4518 |
4188 |
8706 |
|
| 326 |
4537 |
▶ | if (l == SA_CK_LANES) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (; n >= 0; n = q[n].parent) { |
7543 |
3529 |
11072 |
|
| 392 |
7543 |
▶ | if (len == SA_CK_CHAIN_MAX) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len == SA_CK_CHAIN_MAX) return 0; |
0 |
7543 |
7543 |
|
| 393 |
12084 |
▶ | for (i = 0; i < len; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < len; i++) |
4541 |
7543 |
12084 |
|
| 394 |
4541 |
▶ | if (seen[i] == q[n].bucket) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (l = 0; l < SA_CK_LANES; l++) |
2376499 |
591341 |
2967840 |
|
| 416 |
2376499 |
▶ | if (!SA_CK_LANE(w, l)) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!SA_CK_LANE(w, l)) break; |
3529 |
2372970 |
2376499 |
|
| 417 |
594870 |
▶ | if (l < SA_CK_LANES) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (l < SA_CK_LANES) { |
3529 |
591341 |
594870 |
|
| 418 |
3529 |
▶ | if (sa_ck_chain_ok(q, head)) return head; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (j = 0; j < l; j++) |
971157 |
648420 |
1619577 |
|
| 427 |
971157 |
▶ | if (SA_CK_LANE(w, j) == v) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (SA_CK_LANE(w, j) == v) break; |
1530 |
969627 |
971157 |
|
| 428 |
649950 |
▶ | if (j < l) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| if (n < 0) return 0; |
1113 |
3529 |
4642 |
|
| 473 |
3529 |
▶ | if (sa_ck_walk(c, q, n, k->fp)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!got) { |
0 |
504 |
504 |
|
| 583 |
0 |
▶ | if (!sa_ck_lock(c)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 */ |