include/punk_observe/po_bloom.h

filter: Statementstmt 97.0% 65 / 67 Branchbran 92.1% 35 / 38 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.2% 100 / 105 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_lex.h ↑ Summary xs/query.xs »
1 /* po_bloom.h - a trigram bloom filter, one per log block.
2 *
3 * The problem: a log search must not decompress every block the label filter
4 * leaves. The classic answers are both wrong here.
5 *
6 * - Index every term (the Elasticsearch shape). The index approaches the
7 * size of the data and a high-cardinality field inflates it without
8 * bound.
9 * - Index nothing and scan (the plain Loki shape). Correct, and it
10 * decompresses everything the labels leave.
11 *
12 * This filter is the third option: it stores NO TEXT and answers exactly one
13 * question, "can this block possibly contain that substring". A block whose
14 * answer is no is skipped unopened. A block whose answer is yes is
15 * decompressed and matched EXACTLY, so a false positive costs one
16 * decompression and never a wrong answer.
17 *
18 * THE ASYMMETRY IS THE WHOLE DESIGN.
19 *
20 * A false positive = a wasted decompression.
21 * A false negative = A LOST LOG LINE.
22 *
23 * There is no acceptable rate of the second, so the bit count is derived from
24 * the measured distinct-trigram count rather than picked, and t/0041-bloom.t
25 * asserts zero false negatives over a generated corpus. That test is the
26 * reason this file exists in this shape.
27 *
28 * (Search::Trigram was the obvious candidate and is not usable: sg_abi.h:66-69
29 * copies each document's text INTO the index and the table has no serialise
30 * at all, so it is an in-memory document store rather than something a sealed
31 * segment can carry.)
32 */
33 #ifndef PO_BLOOM_H
34 #define PO_BLOOM_H
35  
36 #include "punk_observe/po_compat.h"
37 #include "punk_observe/po_hash.h"
38  
39 /* Two independent hashes, derived from one 128-bit murmur by taking its two
40 * halves. Kirsch-Mitzenmacher: h_i = h1 + i*h2 gives k hashes from two with no
41 * measurable loss, so this costs one hash per trigram rather than k. */
42 #define PO_BLOOM_K 4
43  
44 typedef struct {
45 unsigned char *bits;
46 uint32_t nbits; /* always a power of two, so masking works */
47 uint32_t mask;
48 uint32_t added; /* trigrams inserted, for the sizing report */
49 } po_bloom;
50  
51 /* Size from the expected distinct-trigram count and a target false-positive
52 * rate. The optimal m/n for rate p is -ln(p)/(ln2)^2; for p = 1% that is
53 * about 9.6 bits per element, which this rounds up to the next power of two
54 * so the index can mask instead of dividing. */
55 242 static uint32_t po_bloom_bits_for(uint32_t n) {
56 242 po_u64 want = (po_u64)n * 10 + 64; /* ~10 bits each, plus a floor */
57 242 uint32_t p = 64;
58 2027 ▶ while ((po_u64)p < want && p < (1u << 30)) p <<= 1;
Branch: 2 branches
BranchTrueFalseTotal
while ((po_u64)p < want && p < (1u << 30)) p <<= 1; 1785 242 2027
while ((po_u64)p < want && p < (1u << 30)) p <<= 1; 1785 0 1785
59 242 return p;
60 }
61  
62 242 static int po_bloom_init(po_bloom *b, uint32_t expect) {
63 242 memset(b, 0, sizeof(*b));
64 242 b->nbits = po_bloom_bits_for(expect);
65 242 b->mask = b->nbits - 1;
66 242 b->bits = (unsigned char *)calloc((b->nbits + 7) / 8, 1);
67 242 return b->bits != NULL;
68 }
69  
70 242 static void po_bloom_free(po_bloom *b) { free(b->bits); b->bits = NULL; }
71  
72 1293917 static void po_bloom_set(po_bloom *b, const char *p, size_t len) {
73 1293917 po_h128 h = po_murmur3_128(p, len, 0);
74 int i;
75 6469585 ▶ for (i = 0; i < PO_BLOOM_K; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < PO_BLOOM_K; i++) { 5175668 1293917 6469585
76 5175668 uint32_t bit = (uint32_t)((h.lo + (po_u64)i * h.hi) & b->mask);
77 5175668 b->bits[bit >> 3] |= (unsigned char)(1 << (bit & 7));
78 }
79 1293917 b->added++;
80 1293917 }
81  
82 183050 static int po_bloom_test_raw(const unsigned char *bits, uint32_t mask,
83 const char *p, size_t len) {
84 183050 po_h128 h = po_murmur3_128(p, len, 0);
85 int i;
86 903572 ▶ for (i = 0; i < PO_BLOOM_K; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < PO_BLOOM_K; i++) { 723628 179944 903572
87 723628 uint32_t bit = (uint32_t)((h.lo + (po_u64)i * h.hi) & mask);
88 723628 ▶ if (!(bits[bit >> 3] & (1 << (bit & 7)))) return 0; /* definitely not */
Branch: 1 branch
BranchTrueFalseTotal
if (!(bits[bit >> 3] & (1 << (bit & 7)))) return 0; /* definitely not */ 3106 720522 723628
89 }
90 179944 return 1; /* possibly */
91 }
92  
93 0 static int po_bloom_test(const po_bloom *b, const char *p, size_t len) {
94 0 return po_bloom_test_raw(b->bits, b->mask, p, len);
95 }
96  
97 /* ---- trigrams -------------------------------------------------------------
98 *
99 * BYTE trigrams, not character ones. A trigram may split a UTF-8 codepoint,
100 * which is harmless BECAUSE the filter only ever prunes and the surviving
101 * block is matched exactly - and because the query is split by the identical
102 * rule, so the same split happens on both sides. Documented here so nobody
103 * later "fixes" it into a codepoint-aware version that no longer matches what
104 * was indexed.
105 *
106 * Case folding is applied at BOTH index and query time. Folding only at query
107 * time would skip blocks containing the term in another case, which is a
108 * false negative wearing a disguise.
109 */
110 8486848 static unsigned char po_fold(unsigned char c) {
111 8486848 ▶ return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c;
Branch: 2 branches
BranchTrueFalseTotal
return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c; 4910266 3576582 8486848
return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c; 445142 4465124 4910266
112 }
113  
114 typedef void (*po_trigram_cb)(void *ud, const char *tri);
115  
116 180050 static void po_trigrams(const char *p, size_t len, po_trigram_cb cb, void *ud) {
117 size_t i;
118 char t[3];
119 180050 ▶ if (len < 3) return; /* see po_bloom_query_usable */
Branch: 1 branch
BranchTrueFalseTotal
if (len < 3) return; /* see po_bloom_query_usable */ 0 180050 180050
120 2972294 ▶ for (i = 0; i + 3 <= len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i + 3 <= len; i++) { 2792244 180050 2972294
121 2792244 t[0] = (char)po_fold((unsigned char)p[i]);
122 2792244 t[1] = (char)po_fold((unsigned char)p[i + 1]);
123 2792244 t[2] = (char)po_fold((unsigned char)p[i + 2]);
124 2792244 cb(ud, t);
125 }
126 }
127  
128 1293917 static void po_bloom_add_cb(void *ud, const char *tri) {
129 1293917 po_bloom_set((po_bloom *)ud, tri, 3);
130 1293917 }
131  
132 242 static void po_bloom_add_text(po_bloom *b, const char *p, size_t len) {
133 242 po_trigrams(p, len, po_bloom_add_cb, b);
134 242 }
135  
136 /* Count distinct trigrams, so a block can be sized from what it actually
137 * holds rather than from a guess. Uses a small open set; blocks are ~1MB so
138 * the distinct count is bounded well under 2^24. */
139 typedef struct { unsigned char seen[1 << 21]; uint32_t n; } po_tri_count;
140  
141 1293917 static void po_tri_count_cb(void *ud, const char *tri) {
142 1293917 po_tri_count *c = (po_tri_count *)ud;
143 1293917 uint32_t h = po_hash32(tri, 3) & ((1u << 24) - 1);
144 1293917 uint32_t byte = h >> 3;
145 1293917 unsigned char m = (unsigned char)(1 << (h & 7));
146 1293917 ▶ if (!(c->seen[byte] & m)) { c->seen[byte] |= m; c->n++; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(c->seen[byte] & m)) { c->seen[byte] |= m; c->n++; } 195162 1098755 1293917
147 1293917 }
148  
149 /* CAN THIS QUERY USE THE FILTER AT ALL?
150 *
151 * A query shorter than three bytes has NO trigrams, so testing it would test
152 * nothing and "no trigram matched" would wrongly prune every block. A search
153 * for "ok" must fall through to scanning the candidates, not silently return
154 * empty. This is the bug that would make short searches quietly wrong, so it
155 * is a named predicate rather than an implicit length check somewhere. */
156 180801 static int po_bloom_query_usable(size_t qlen) { return qlen >= 3; }
157  
158 /* Test every trigram of the query. ANY absent trigram means the block cannot
159 * contain the query. */
160 typedef struct { const unsigned char *bits; uint32_t mask; int possible; }
161 po_bloom_probe;
162  
163 204410 static void po_bloom_probe_cb(void *ud, const char *tri) {
164 204410 po_bloom_probe *p = (po_bloom_probe *)ud;
165 204410 ▶ if (!p->possible) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!p->possible) return; 21360 183050 204410
166 183050 ▶ if (!po_bloom_test_raw(p->bits, p->mask, tri, 3)) p->possible = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_bloom_test_raw(p->bits, p->mask, tri, 3)) p->possible = 0; 3106 179944 183050
167 }
168  
169 179571 static int po_bloom_may_contain(const unsigned char *bits, uint32_t mask,
170 const char *q, size_t qlen) {
171 po_bloom_probe p;
172 179571 ▶ if (!po_bloom_query_usable(qlen)) return 1; /* cannot prune: assume yes */
Branch: 1 branch
BranchTrueFalseTotal
if (!po_bloom_query_usable(qlen)) return 1; /* cannot prune: assume yes */ 5 179566 179571
173 179566 p.bits = bits; p.mask = mask; p.possible = 1;
174 179566 po_trigrams(q, qlen, po_bloom_probe_cb, &p);
175 179566 return p.possible;
176 }
177  
178 /* The exact match that runs AFTER the filter says "possible". Case-folded to
179 * agree with the filter, and a plain byte search: the filter prunes, this
180 * decides. */
181 1783 static const char *po_memfind(const char *hay, size_t hn,
182 const char *needle, size_t nn) {
183 size_t i, j;
184 1783 ▶ if (nn == 0 || nn > hn) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (nn == 0 || nn > hn) return NULL; 1783 0 1783
if (nn == 0 || nn > hn) return NULL; 240 1543 1783
185 52376 ▶ for (i = 0; i + nn <= hn; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i + nn <= hn; i++) { 51251 1125 52376
186 55476 ▶ for (j = 0; j < nn; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < nn; j++) 55058 418 55476
187 110116 ▶ if (po_fold((unsigned char)hay[i + j]) !=
Branch: 1 branch
BranchTrueFalseTotal
if (po_fold((unsigned char)hay[i + j]) != 50833 4225 55058
188 105891 po_fold((unsigned char)needle[j])) break;
189 51251 ▶ if (j == nn) return hay + i;
Branch: 1 branch
BranchTrueFalseTotal
if (j == nn) return hay + i; 418 50833 51251
190 }
191 1125 return NULL;
192 }
193  
194 #endif /* PO_BLOOM_H */
« include/punk_observe/po_lex.h ↑ Summary xs/query.xs »