include/sa/sa_bloom.h

filter: Statementstmt 93.2% 96 / 103 Branchbran 52.5% 42 / 80 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 75.4% 138 / 183 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_scoreboard.h ↑ Summary include/sa/sa_hist.h »
1 #ifndef SA_BLOOM_H
2 #define SA_BLOOM_H
3  
4 /* sa_bloom.h - a set that answers "no" exactly and "yes" probably. Perl-free.
5 *
6 * A bit array and k hash functions. Adding a key sets k bits; asking about a
7 * key tests them. If any is clear the key was definitely never added; if all
8 * are set it probably was, and the probability is a number you chose when you
9 * sized the filter.
10 *
11 * ---- why this fits an arena so well ----------------------------------------
12 *
13 * There is nothing to allocate after the first moment, nothing to free ever,
14 * and no way for two processes to disagree about a write: setting a bit is one
15 * atomic OR, and two processes setting the same bit both simply set it. It is
16 * the only structure here that needs no lock at all, on either side.
17 *
18 * ---- what it cannot do -----------------------------------------------------
19 *
20 * NO DELETION. Clearing a bit would clear it for every other key that happens
21 * to share it, turning a definite "no" into a wrong one. A filter only fills
22 * up; when it is too full, it is replaced.
23 *
24 * NO COUNT. `estimated_items` is arithmetic on how many bits are set, and it is
25 * an estimate that gets worse as the filter saturates.
26 *
27 * ---- sizing ----------------------------------------------------------------
28 *
29 * From an expected item count n and an acceptable false-positive rate p, the
30 * standard result gives the bits m and the hash count k:
31 *
32 * m = -n ln p / (ln 2)^2 k = (m/n) ln 2
33 *
34 * A filter sized for a million items at one percent needs about 1.2 MB and
35 * seven hash probes. Ask for what you expect, not for bits.
36 *
37 * The rate is what you get AT that item count. Past it the rate climbs, and it
38 * climbs quickly, which is why the fill is in the stats and why a caller that
39 * cares rotates rather than hoping.
40 *
41 * ---- two hashes, not k -----------------------------------------------------
42 *
43 * Computing k independent hashes of every key would be k times the work for no
44 * benefit: Kirsch and Mitzenmacher showed that h1 + i*h2 gives the same false
45 * positive rate as k independent functions. So there are two, and the rest is
46 * arithmetic. h2 is forced odd so the probe sequence cannot get stuck on a
47 * subset of the array.
48 *
49 * Needs sa_arena.h.
50 */
51  
52 #include "sa/sa_arena.h"
53  
54 #ifndef SA_NO_LIBM
55 # include <math.h>
56 #endif
57  
58 #define SA_BLOOM_MAGIC 0x4D4F4C42u /* 'B','L','O','M' little-endian */
59  
60 #define SA_BLOOM_MAX_K 32
61  
62 typedef struct {
63 volatile uint32_t magic; /* published LAST at init */
64 uint32_t nhash; /* k */
65 uint64_t nbits; /* m, a multiple of 64 */
66 uint64_t bits_off; /* from the FILTER's base */
67 uint64_t capacity; /* the n it was sized for */
68 volatile uint64_t added; /* add() calls that set at least one bit */
69 volatile uint64_t seen; /* add() calls that found every bit set */
70 volatile unsigned char locks[SA_LOCK_STRIPES];
71 } sa_bloom_hdr;
72  
73 #ifndef SA_BLOOM_FWD
74 #define SA_BLOOM_FWD
75 typedef struct sa_bloom sa_bloom;
76 #endif
77 struct sa_bloom {
78 sa_region *arena;
79 sa_bloom_hdr *hdr;
80 volatile uint64_t *words;
81 uint64_t nbits;
82 uint64_t nwords;
83 uint32_t nhash;
84 };
85  
86 /* Round the bits up to a whole number of 64-bit words. */
87 70 static uint64_t sa_bloom_words(uint64_t nbits) {
88 70 return (nbits + 63u) / 64u;
89 }
90  
91 42 static uint64_t sa_bloom_bytes(uint64_t nbits) {
92 42 return sa_align_up((uint64_t)sizeof(sa_bloom_hdr))
93 42 + sa_bloom_words(nbits) * 8u;
94 }
95  
96 /* The bits and hash count for n items at a false-positive rate p.
97 *
98 * Falls back to eight bits per item and five hashes where there is no libm,
99 * which is roughly p = 0.02 - a working filter rather than none at all, and the
100 * build says so at configure time. */
101 13 static void sa_bloom_size(uint64_t n, double p, uint64_t *nbits, uint32_t *k) {
102 uint64_t m;
103 uint32_t kk;
104  
105 13 ▶ if (n < 1) n = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 1) n = 1; 0 13 13
106 #ifdef SA_NO_LIBM
107 (void)p;
108 m = n * 8u;
109 kk = 5;
110 #else
111 13 ▶ if (!(p > 0.0) || p >= 1.0) p = 0.01;
Branch: 2 branches
BranchTrueFalseTotal
if (!(p > 0.0) || p >= 1.0) p = 0.01; 13 0 13
if (!(p > 0.0) || p >= 1.0) p = 0.01; 0 13 13
112 {
113 13 double ln2 = 0.6931471805599453;
114 13 double md = -((double)n) * log(p) / (ln2 * ln2);
115 13 ▶ if (md < 64.0) md = 64.0;
Branch: 1 branch
BranchTrueFalseTotal
if (md < 64.0) md = 64.0; 0 13 13
116 13 m = (uint64_t)(md + 0.5);
117 13 kk = (uint32_t)((md / (double)n) * ln2 + 0.5);
118 }
119 #endif
120 13 ▶ if (kk < 1) kk = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (kk < 1) kk = 1; 0 13 13
121 13 ▶ if (kk > SA_BLOOM_MAX_K) kk = SA_BLOOM_MAX_K;
Branch: 1 branch
BranchTrueFalseTotal
if (kk > SA_BLOOM_MAX_K) kk = SA_BLOOM_MAX_K; 0 13 13
122 13 m = sa_bloom_words(m) * 64u; /* whole words */
123 13 ▶ if (nbits) *nbits = m;
Branch: 1 branch
BranchTrueFalseTotal
if (nbits) *nbits = m; 13 0 13
124 13 ▶ if (k) *k = kk;
Branch: 1 branch
BranchTrueFalseTotal
if (k) *k = kk; 13 0 13
125 13 }
126  
127 /* The second hash. A finalising mix rather than a second pass over the key: the
128 * key has already been read once and reading it again to get an independent
129 * value is the cost this avoids. */
130 59038 static uint64_t sa_bloom_mix(uint64_t h) {
131 59038 h ^= h >> 33;
132 59038 h *= 0xff51afd7ed558ccdULL;
133 59038 h ^= h >> 33;
134 59038 h *= 0xc4ceb9fe1a85ec53ULL;
135 59038 h ^= h >> 33;
136 59038 return h;
137 }
138  
139 14 static sa_bloom *sa_bloom_bind(sa_region *arena, sa_reg *e,
140 uint64_t nbits, uint32_t nhash, int *err)
141 {
142 #if !SA_HAVE_ATOMICS
143 (void)arena; (void)e; (void)nbits; (void)nhash;
144 if (err) *err = SA_E_NOATOMICS;
145 return NULL;
146 #else
147 sa_bloom *b;
148 sa_bloom_hdr *h;
149 uint64_t hash;
150  
151 14 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 14 0 14
152 14 ▶ 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; } 14 0 14
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 14 14
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
153  
154 14 h = (sa_bloom_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_bloom_hdr));
155 14 ▶ 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 14 14
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
156  
157 14 ▶ if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { 14 0 14
158 14 hash = sa_at_fnv(e->name, strlen(e->name));
159 14 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 14 0 14
160 14 ▶ if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_BLOOM_MAGIC) { 14 0 14
161 14 ▶ if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) {
Branch: 3 branches
BranchTrueFalseTotal
if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { 14 0 14
if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { 14 0 14
if (!nbits || !nhash || sa_bloom_bytes(nbits) > e->len) { 0 14 14
162 0 sa_at_unlock(h->locks, hash);
163 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
164 0 return NULL;
165 }
166 14 memset((void *)h, 0, (size_t)sa_bloom_bytes(nbits));
167 14 h->nbits = nbits;
168 14 h->nhash = nhash;
169 14 h->bits_off = sa_align_up((uint64_t)sizeof(sa_bloom_hdr));
170 14 sa_at_store32_rel(&h->magic, SA_BLOOM_MAGIC);
171 }
172 14 sa_at_unlock(h->locks, hash);
173 }
174 14 ▶ if (!sa_wait_magic32(&h->magic, SA_BLOOM_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_BLOOM_MAGIC)) { 0 14 14
175 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
176 0 return NULL;
177 }
178 }
179  
180 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
181 *
182 * The branch above only checks a size when this process is the one doing
183 * the INITIALISING. A process that finds the magic already set reads the
184 * shape out of the shared header and believed it, so a header claiming
185 * four billion slots put every later read past the end of the mapping.
186 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
187  
188 14 ▶ if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) {
Branch: 4 branches
BranchTrueFalseTotal
if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { 14 0 14
if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { 14 0 14
if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { 14 0 14
if ((nbits && h->nbits != nbits) || (nhash && h->nhash != nhash)) { 0 14 14
189 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
190 0 return NULL;
191 }
192  
193 14 b = (sa_bloom *)calloc(1, sizeof(sa_bloom));
194 14 ▶ if (!b) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!b) { if (err) *err = SA_E_NOMEM; return NULL; } 0 14 14
if (!b) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
195 14 b->arena = arena;
196 14 b->hdr = h;
197 14 b->words = (volatile uint64_t *)((char *)h + (size_t)h->bits_off);
198 14 b->nbits = h->nbits;
199 14 b->nwords = sa_bloom_words(h->nbits);
200 14 b->nhash = h->nhash;
201 14 return b;
202 #endif
203 }
204  
205 14 static void sa_bloom_free(sa_bloom *b) { free(b); }
206  
207 /* Add a key. Returns 1 when every bit was ALREADY set - meaning the key had
208 * probably been added before - and 0 when this call set at least one.
209 *
210 * THAT ANSWER IS PER BIT, NOT PER KEY. Two processes adding the same key at the
211 * same instant can both be told it was new, because each set some of the bits
212 * the other was about to set. For a filter that is harmless; for a caller using
213 * this to do a job exactly once it is not, and that caller wants a lock or a
214 * compare-and-set, not a bloom filter. */
215 25820 static int sa_bloom_add(sa_bloom *b, const char *key, uint32_t klen) {
216 #if !SA_HAVE_ATOMICS
217 (void)b; (void)key; (void)klen;
218 return 0;
219 #else
220 25820 uint64_t h1 = sa_at_fnv(key, klen);
221 25820 uint64_t h2 = sa_bloom_mix(h1) | 1u; /* odd, so the walk covers */
222 uint32_t i;
223 25820 int all_set = 1;
224  
225 206560 ▶ for (i = 0; i < b->nhash; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->nhash; i++) { 180740 25820 206560
226 180740 uint64_t bit = (h1 + (uint64_t)i * h2) % b->nbits;
227 180740 uint64_t mask = 1ULL << (bit & 63u);
228 180740 uint64_t was = sa_at_fetch_or64(&b->words[bit >> 6], mask);
229 180740 ▶ if (!(was & mask)) all_set = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!(was & mask)) all_set = 0; 128901 51839 180740
230 }
231  
232 25820 ▶ if (all_set) sa_at_fetch_add64(&b->hdr->seen, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (all_set) sa_at_fetch_add64(&b->hdr->seen, 1); 50 25770 25820
233 25770 else sa_at_fetch_add64(&b->hdr->added, 1);
234 25820 return all_set;
235 #endif
236 }
237  
238 /* Has this key probably been added? A 0 is exact; a 1 may be a coincidence. */
239 33218 static int sa_bloom_check(sa_bloom *b, const char *key, uint32_t klen) {
240 #if !SA_HAVE_ATOMICS
241 (void)b; (void)key; (void)klen;
242 return 0;
243 #else
244 33218 uint64_t h1 = sa_at_fnv(key, klen);
245 33218 uint64_t h2 = sa_bloom_mix(h1) | 1u;
246 uint32_t i;
247  
248 147039 ▶ for (i = 0; i < b->nhash; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->nhash; i++) { 133638 13401 147039
249 133638 uint64_t bit = (h1 + (uint64_t)i * h2) % b->nbits;
250 133638 uint64_t mask = 1ULL << (bit & 63u);
251 /* One clear bit is a definite no, and there is no point reading the
252 * rest. A miss is the common case in every use this has. */
253 133638 ▶ if (!(sa_at_load64_acq(&b->words[bit >> 6]) & mask)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!(sa_at_load64_acq(&b->words[bit >> 6]) & mask)) return 0; 19817 113821 133638
254 }
255 13401 return 1;
256 #endif
257 }
258  
259 /* How many bits are set. O(m/64), so it is a question for a status page rather
260 * than for a request path. */
261 14 static uint64_t sa_bloom_popcount(sa_bloom *b) {
262 #if !SA_HAVE_ATOMICS
263 (void)b;
264 return 0;
265 #else
266 14 uint64_t i, n = 0;
267 13498 ▶ for (i = 0; i < b->nwords; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->nwords; i++) { 13484 14 13498
268 13484 uint64_t w = sa_at_load64_acq(&b->words[i]);
269 /* The SWAR popcount rather than a builtin: __builtin_popcountll is not
270 * everywhere, and this is a status query, not a hot path. */
271 13484 w = w - ((w >> 1) & 0x5555555555555555ULL);
272 13484 w = (w & 0x3333333333333333ULL) + ((w >> 2) & 0x3333333333333333ULL);
273 13484 w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
274 13484 n += (w * 0x0101010101010101ULL) >> 56;
275 }
276 14 return n;
277 #endif
278 }
279  
280 /* Forget everything.
281 *
282 * Under the lock, but readers do not take it: a check running concurrently may
283 * see some words cleared and some not, and answer either way for a key that is
284 * being forgotten. That is exactly what it would have answered a moment either
285 * side, so there is nothing to protect it from - but it is the reason this is
286 * `reset` and not a transaction. */
287 2 static void sa_bloom_reset(sa_bloom *b) {
288 #if SA_HAVE_ATOMICS
289 2 uint64_t hash = (uint64_t)(uintptr_t)b->hdr;
290 uint64_t i;
291 2 ▶ if (!sa_at_lock(b->hdr->locks, hash)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(b->hdr->locks, hash)) return; 0 2 2
292 302 ▶ for (i = 0; i < b->nwords; i++) sa_at_store64_rel(&b->words[i], 0);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->nwords; i++) sa_at_store64_rel(&b->words[i], 0); 300 2 302
293 2 sa_at_store64_rel(&b->hdr->added, 0);
294 2 sa_at_store64_rel(&b->hdr->seen, 0);
295 2 sa_at_unlock(b->hdr->locks, hash);
296 #else
297 (void)b;
298 #endif
299 }
300  
301 /* How many distinct keys the set bits suggest. An estimate, and one that gets
302 * worse as the filter fills: n* = -(m/k) ln(1 - X/m). */
303 6 static uint64_t sa_bloom_estimate(sa_bloom *b) {
304 #if defined(SA_NO_LIBM) || !SA_HAVE_ATOMICS
305 return sa_bloom_popcount(b) / (b->nhash ? b->nhash : 1);
306 #else
307 6 uint64_t set = sa_bloom_popcount(b);
308 6 double m = (double)b->nbits, k = (double)b->nhash;
309 6 ▶ if (set == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (set == 0) return 0; 2 4 6
310 4 ▶ if ((double)set >= m) return (uint64_t)-1; /* saturated */
Branch: 1 branch
BranchTrueFalseTotal
if ((double)set >= m) return (uint64_t)-1; /* saturated */ 0 4 4
311 4 return (uint64_t)(-(m / k) * log(1.0 - (double)set / m) + 0.5);
312 #endif
313 }
314  
315 #endif /* SA_BLOOM_H */
« include/sa/sa_scoreboard.h ↑ Summary include/sa/sa_hist.h »