include/sa/sa_cms.h

filter: Statementstmt 92.7% 90 / 97 Branchbran 52.1% 49 / 94 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 72.7% 139 / 191 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_wake.h ↑ Summary include/sa/sa_ring.h »
1 #ifndef SA_CMS_H
2 #define SA_CMS_H
3  
4 /* sa_cms.h - a count-min sketch: how often, in fixed space. Perl-free.
5 *
6 * ---- the question the other tenants do not answer ---------------------------
7 *
8 * The bloom filter answers "have I seen this key". The histogram answers "what
9 * does the distribution of these numbers look like". Neither answers B<how many
10 * times have I seen THIS key>, and that is the question behind every piece of
11 * abuse detection: which client is hammering the gateway, which query is being
12 * repeated, which key deserves a limit that the others do not.
13 *
14 * A map would answer it exactly and needs a slot per key. Key cardinality is
15 * the one thing an abuse detector cannot bound - the whole problem is that
16 * somebody is generating keys - so the exact structure is the one that falls
17 * over first.
18 *
19 * A sketch does not store keys at all. d rows of w counters, each key hashed to
20 * one counter per row, every add incrementing all d. The estimate is the
21 * SMALLEST of them, because collisions can only ever have added.
22 *
23 * ---- it overestimates, and it never underestimates ---------------------------
24 *
25 * That asymmetry is the whole contract, and it is the right way round. A count
26 * that can only be too high never MISSES a heavy hitter; it can only accuse a
27 * light key of being heavier than it is, and how often it does that is the
28 * number you chose when you sized it.
29 *
30 * With w = e/epsilon and d = ln(1/delta), the estimate exceeds the truth by
31 * more than epsilon * N with probability at most delta, where N is the total
32 * of everything added. Note what the error is relative to: not the key's own
33 * count, but the WHOLE. A sketch sized for one percent on a stream of a million
34 * is accurate to ten thousand, which is useless for a key seen twice and
35 * exactly right for finding the one seen half a million times.
36 *
37 * So `total` is in the header and in the stats. An estimate quoted without it
38 * is a number with no error bar.
39 *
40 * ---- why NOT conservative update --------------------------------------------
41 *
42 * The well-known improvement is to increment only those counters that are at
43 * the current minimum, which cuts overestimation substantially. It is refused
44 * here, and the reason is this dist rather than the algorithm.
45 *
46 * Conservative update is read-then-write: read all d, work out the minimum,
47 * write back some of them. Two processes doing that at once can each decide a
48 * counter needs no increment because the other's is not visible yet, and the
49 * counter then ends up short. A sketch that can UNDERESTIMATE has lost the only
50 * guarantee it offers - a heavy hitter can hide - and it fails silently,
51 * because a low answer looks exactly like a quiet key.
52 *
53 * A plain increment is one fetch-add per row, needs no lock, cannot be lost,
54 * and cannot be corrupted by a process dying between two of them: the worst a
55 * crash leaves behind is a key counted in some rows and not others, which reads
56 * as a slightly LOWER estimate on a structure that was going to be high anyway.
57 *
58 * ---- what it cannot do -------------------------------------------------------
59 *
60 * IT CANNOT LIST ANYTHING. A sketch holds no keys, so it can answer about a key
61 * you name and can never tell you which keys exist. "The top ten" is a
62 * different structure: a candidate set beside the sketch, which is a Map of the
63 * keys currently believed to be heavy, consulted and updated when a key's
64 * estimate crosses the smallest of them.
65 *
66 * IT CANNOT DECREMENT. Subtracting breaks the min estimate the same way
67 * conservative update does, and for the same reason. A sketch is reset, or
68 * rotated, not decremented.
69 *
70 * Needs sa_arena.h.
71 */
72  
73 #include "sa/sa_arena.h"
74  
75 #ifndef SA_NO_LIBM
76 # include <math.h>
77 #endif
78  
79 #define SA_CMS_MAGIC 0x534D4353u /* 'S','C','M','S' little-endian */
80  
81 #define SA_CMS_MAX_ROWS 32
82  
83 typedef struct {
84 volatile uint32_t magic; /* published LAST at init */
85 uint32_t rows; /* d */
86 uint64_t width; /* w, a power of two */
87 uint64_t cells_off; /* from the SKETCH's base */
88 volatile uint64_t total; /* everything ever added, for the error bar */
89 volatile uint64_t adds; /* add() calls */
90 volatile unsigned char locks[SA_LOCK_STRIPES];
91 } sa_cms_hdr;
92  
93 #ifndef SA_CMS_FWD
94 #define SA_CMS_FWD
95 typedef struct sa_cms sa_cms;
96 #endif
97  
98 struct sa_cms {
99 sa_region *arena;
100 sa_cms_hdr *hdr;
101 volatile uint64_t *cells;
102 uint32_t rows;
103 uint64_t width;
104 uint64_t mask;
105 };
106  
107 /* Sixty-four bit counters, not thirty-two.
108 *
109 * A sketch counts a stream, and a stream on a busy gateway passes four billion
110 * in a day. A 32-bit counter would need saturating arithmetic to avoid wrapping
111 * to nearly zero - which is an underestimate, the one thing this structure
112 * promises never to produce - and saturating means a compare-and-swap loop
113 * rather than a fetch-add. Eight bytes a cell buys a plain atomic increment and
114 * a counter nobody has to think about. */
115 111 static uint64_t sa_cms_bytes(uint32_t rows, uint64_t width) {
116 111 return sa_align_up((uint64_t)sizeof(sa_cms_hdr))
117 111 + (uint64_t)rows * width * 8u;
118 }
119  
120 32 static uint64_t sa_cms_pow2(uint64_t n) {
121 32 uint64_t p = 64;
122 32 ▶ if (n < 64) return 64;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 64) return 64; 0 32 32
123 192 ▶ while (p < n && p < (uint64_t)1 << 40) p <<= 1;
Branch: 2 branches
BranchTrueFalseTotal
while (p < n && p < (uint64_t)1 << 40) p <<= 1; 160 32 192
while (p < n && p < (uint64_t)1 << 40) p <<= 1; 160 0 160
124 32 return p;
125 }
126  
127 /* Rows and width from the two numbers a caller actually has: how much error it
128 * will accept as a fraction of the total, and how sure it wants to be.
129 *
130 * w = e / epsilon d = ln(1 / delta)
131 *
132 * The width is rounded UP to a power of two, so the row index is a mask rather
133 * than a division on a path that runs per row per add. Rounding up only reduces
134 * epsilon, so the caller gets at least the accuracy it asked for. */
135 24 static void sa_cms_size(double epsilon, double confidence,
136 uint32_t *rows, uint64_t *width)
137 {
138 uint64_t w;
139 uint32_t d;
140  
141 #ifdef SA_NO_LIBM
142 (void)confidence;
143 if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01;
144 w = (uint64_t)(2.718281828459045 / epsilon + 0.5);
145 d = 5; /* delta about 0.007 */
146 #else
147 double delta;
148 24 ▶ if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01;
Branch: 2 branches
BranchTrueFalseTotal
if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; 24 0 24
if (!(epsilon > 0.0) || epsilon >= 1.0) epsilon = 0.01; 0 24 24
149 24 ▶ if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99;
Branch: 2 branches
BranchTrueFalseTotal
if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99; 24 0 24
if (!(confidence > 0.0) || confidence >= 1.0) confidence = 0.99; 0 24 24
150 24 delta = 1.0 - confidence;
151 24 w = (uint64_t)(2.718281828459045 / epsilon + 0.5);
152 {
153 24 double dd = -log(delta);
154 24 ▶ if (dd < 1.0) dd = 1.0;
Branch: 1 branch
BranchTrueFalseTotal
if (dd < 1.0) dd = 1.0; 0 24 24
155 24 d = (uint32_t)(dd + 0.999);
156 }
157 #endif
158 24 ▶ if (d < 1) d = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (d < 1) d = 1; 0 24 24
159 24 ▶ if (d > SA_CMS_MAX_ROWS) d = SA_CMS_MAX_ROWS;
Branch: 1 branch
BranchTrueFalseTotal
if (d > SA_CMS_MAX_ROWS) d = SA_CMS_MAX_ROWS; 0 24 24
160 24 w = sa_cms_pow2(w);
161 24 ▶ if (rows) *rows = d;
Branch: 1 branch
BranchTrueFalseTotal
if (rows) *rows = d; 24 0 24
162 24 ▶ if (width) *width = w;
Branch: 1 branch
BranchTrueFalseTotal
if (width) *width = w; 24 0 24
163 24 }
164  
165 /* The second hash. A finalising mix rather than a second pass over the key: the
166 * key has been read once already, and reading it again to get an independent
167 * value is the cost this avoids. Kirsch and Mitzenmacher: h1 + i*h2 has the
168 * same behaviour as d independent functions. */
169 152948 static uint64_t sa_cms_mix(uint64_t h) {
170 152948 h ^= h >> 33;
171 152948 h *= 0xff51afd7ed558ccdULL;
172 152948 h ^= h >> 33;
173 152948 h *= 0xc4ceb9fe1a85ec53ULL;
174 152948 h ^= h >> 33;
175 152948 return h;
176 }
177  
178 31 static sa_cms *sa_cms_bind(sa_region *arena, sa_reg *e, uint32_t rows,
179 uint64_t width, int *err)
180 {
181 #if !SA_HAVE_ATOMICS
182 (void)arena; (void)e; (void)rows; (void)width;
183 if (err) *err = SA_E_NOATOMICS;
184 return NULL;
185 #else
186 sa_cms *s;
187 sa_cms_hdr *h;
188 uint64_t hash;
189  
190 31 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 31 0 31
191 31 ▶ 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; } 31 0 31
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 31 31
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
192  
193 31 h = (sa_cms_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_cms_hdr));
194 31 ▶ 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 31 31
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
195  
196 31 ▶ if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { 31 0 31
197 31 hash = sa_at_fnv(e->name, strlen(e->name));
198 31 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 31 0 31
199 31 ▶ if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CMS_MAGIC) { 31 0 31
200 31 ▶ if (!rows || !width || sa_cms_bytes(rows, width) > e->len) {
Branch: 3 branches
BranchTrueFalseTotal
if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { 31 0 31
if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { 31 0 31
if (!rows || !width || sa_cms_bytes(rows, width) > e->len) { 0 31 31
201 0 sa_at_unlock(h->locks, hash);
202 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
203 0 return NULL;
204 }
205 31 memset((void *)h, 0, (size_t)sa_cms_bytes(rows, width));
206 31 h->rows = rows;
207 31 h->width = width;
208 31 h->cells_off = sa_align_up((uint64_t)sizeof(sa_cms_hdr));
209 31 sa_at_store32_rel(&h->magic, SA_CMS_MAGIC);
210 }
211 31 sa_at_unlock(h->locks, hash);
212 }
213 31 ▶ if (!sa_wait_magic32(&h->magic, SA_CMS_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_CMS_MAGIC)) { 0 31 31
214 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
215 0 return NULL;
216 }
217 }
218  
219 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
220 *
221 * The branch above only checks a size when this process is the one doing
222 * the INITIALISING. A process that finds the magic already set reads the
223 * shape out of the shared header and believed it, so a header claiming
224 * four billion slots put every later read past the end of the mapping.
225 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
226  
227 31 ▶ if ((rows && h->rows != rows) || (width && h->width != width)) {
Branch: 4 branches
BranchTrueFalseTotal
if ((rows && h->rows != rows) || (width && h->width != width)) { 31 0 31
if ((rows && h->rows != rows) || (width && h->width != width)) { 31 0 31
if ((rows && h->rows != rows) || (width && h->width != width)) { 31 0 31
if ((rows && h->rows != rows) || (width && h->width != width)) { 0 31 31
228 0 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 0 0 0
229 0 return NULL;
230 }
231  
232 31 s = (sa_cms *)calloc(1, sizeof(sa_cms));
233 31 ▶ if (!s) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!s) { if (err) *err = SA_E_NOMEM; return NULL; } 0 31 31
if (!s) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
234 31 s->arena = arena;
235 31 s->hdr = h;
236 31 s->cells = (volatile uint64_t *)((char *)h + (size_t)h->cells_off);
237 31 s->rows = h->rows;
238 31 s->width = h->width;
239 31 s->mask = h->width - 1;
240 31 return s;
241 #endif
242 }
243  
244 31 static void sa_cms_free(sa_cms *s) { free(s); }
245  
246 #if SA_HAVE_ATOMICS
247  
248 /* Add `n` to a key, and return what the sketch now believes its count to be.
249 *
250 * The answer is the minimum ACROSS THE ROWS AFTER THIS ADD, which is what a
251 * caller asking "has this key just crossed my threshold" wants, and it costs
252 * nothing extra: the values are already in hand.
253 *
254 * One fetch-add per row, no lock, and nothing to undo. A process that dies part
255 * way through has counted its key in some rows and not others, which reads back
256 * as a slightly lower estimate - never a corrupt one. */
257 148925 static uint64_t sa_cms_add(sa_cms *s, const char *key, uint32_t klen,
258 uint64_t n)
259 {
260 148925 uint64_t h1, h2, min = 0;
261 uint32_t i;
262  
263 148925 ▶ if (!s || !n) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!s || !n) return 0; 148925 0 148925
if (!s || !n) return 0; 0 148925 148925
264 148925 h1 = sa_at_fnv(key, (size_t)klen);
265 148925 h2 = sa_cms_mix(h1) | 1u; /* odd, so the rows cannot coincide */
266  
267 842548 ▶ for (i = 0; i < s->rows; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->rows; i++) { 693623 148925 842548
268 693623 uint64_t idx = (h1 + (uint64_t)i * h2) & s->mask;
269 693623 volatile uint64_t *c = &s->cells[(uint64_t)i * s->width + idx];
270 693623 uint64_t was = sa_at_fetch_add64(c, n);
271 693623 ▶ if (i == 0 || was + n < min) min = was + n;
Branch: 2 branches
BranchTrueFalseTotal
if (i == 0 || was + n < min) min = was + n; 544698 148925 693623
if (i == 0 || was + n < min) min = was + n; 101237 443461 544698
272 }
273  
274 148925 sa_at_fetch_add64(&s->hdr->total, n);
275 148925 sa_at_fetch_add64(&s->hdr->adds, 1);
276 148925 return min;
277 }
278  
279 /* What the sketch believes, without adding to it. At most epsilon * total too
280 * high, with the confidence it was sized for, and never too low. */
281 4023 static uint64_t sa_cms_estimate(sa_cms *s, const char *key, uint32_t klen) {
282 4023 uint64_t h1, h2, min = 0;
283 uint32_t i;
284  
285 4023 ▶ if (!s) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!s) return 0; 0 4023 4023
286 4023 h1 = sa_at_fnv(key, (size_t)klen);
287 4023 h2 = sa_cms_mix(h1) | 1u;
288  
289 21134 ▶ for (i = 0; i < s->rows; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->rows; i++) { 17111 4023 21134
290 17111 uint64_t idx = (h1 + (uint64_t)i * h2) & s->mask;
291 17111 uint64_t v = sa_at_load64_acq(&s->cells[(uint64_t)i * s->width + idx]);
292 17111 ▶ if (i == 0 || v < min) min = v;
Branch: 2 branches
BranchTrueFalseTotal
if (i == 0 || v < min) min = v; 13088 4023 17111
if (i == 0 || v < min) min = v; 1519 11569 13088
293 }
294 4023 return min;
295 }
296  
297 /* Forget everything.
298 *
299 * Readers are not locked out, so a count running at the same moment may see the
300 * sketch half cleared and answer low for a key being forgotten - which is the
301 * one direction this structure otherwise never goes. It is the price of a reset
302 * that does not stop the world, and a caller rotating two sketches rather than
303 * clearing one never pays it. */
304 2 static void sa_cms_reset(sa_cms *s) {
305 uint64_t i, n;
306 2 ▶ if (!s) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!s) return; 0 2 2
307 2 n = (uint64_t)s->rows * s->width;
308 2754 ▶ for (i = 0; i < n; i++) sa_at_store64_rel(&s->cells[i], 0);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) sa_at_store64_rel(&s->cells[i], 0); 2752 2 2754
309 2 sa_at_store64_rel(&s->hdr->total, 0);
310 2 sa_at_store64_rel(&s->hdr->adds, 0);
311 }
312  
313 /* The absolute error bound at the current total: an estimate may be this much
314 * too high, and no more, with the confidence the sketch was sized for.
315 *
316 * epsilon is e/w, so this is arithmetic on the shape rather than a number
317 * anybody has to remember. */
318 18 static uint64_t sa_cms_error(sa_cms *s) {
319 18 ▶ if (!s || !s->width) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!s || !s->width) return 0; 18 0 18
if (!s || !s->width) return 0; 0 18 18
320 36 return (uint64_t)((2.718281828459045 / (double)s->width)
321 18 * (double)sa_at_load64_acq(&s->hdr->total));
322 }
323  
324 #else /* !SA_HAVE_ATOMICS */
325  
326 /* No atomics, so no sketch: sa_cms_bind refuses. These answer the way the XSUBs
327 * do in that build, nothing counted and nothing estimated, so that the op doors
328 * and the ABI table have something to point at. */
329 static uint64_t sa_cms_add(sa_cms *s, const char *key, uint32_t klen,
330 uint64_t n)
331 {
332 (void)s; (void)key; (void)klen; (void)n;
333 return 0;
334 }
335  
336 static uint64_t sa_cms_estimate(sa_cms *s, const char *key, uint32_t klen) {
337 (void)s; (void)key; (void)klen;
338 return 0;
339 }
340  
341 static void sa_cms_reset(sa_cms *s) { (void)s; }
342  
343 static uint64_t sa_cms_error(sa_cms *s) { (void)s; return 0; }
344  
345 #endif /* SA_HAVE_ATOMICS */
346  
347 #endif /* SA_CMS_H */
« include/sa/sa_wake.h ↑ Summary include/sa/sa_ring.h »