include/punk_observe/po_logidx.h

filter: Statementstmt 67.3% 33 / 49 Branchbran 70.4% 31 / 44 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 68.8% 64 / 93 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/store.xs ↑ Summary xs/plot.xs »
1 /* po_logidx.h - the block directory, and the label allowlist.
2 *
3 * Two jobs, and the second one is the one that keeps the store alive.
4 *
5 * THE DIRECTORY. One entry per block, carrying the stream, the time span, the
6 * offsets and the bloom. A time filter skips a block by reading 48 bytes,
7 * WITHOUT INFLATING IT - which is the entire point of having a directory at
8 * all, and the reason t_min/t_max live here and not inside the compressed
9 * bytes.
10 *
11 * THE ALLOWLIST. A stream is a label set, and a label set with a request id in
12 * it is one stream per request. That is the cardinality explosion wearing a
13 * different costume, and it arrives the same way it always does: somebody
14 * adds `user_id` or a full URL as a resource attribute.
15 *
16 * So ONLY configured attributes become stream labels. Everything else stays
17 * in the record, searchable by residual filter but not indexed. Without this,
18 * one customer takes the store down and the store is RIGHT to refuse.
19 */
20 #ifndef PO_LOGIDX_H
21 #define PO_LOGIDX_H
22  
23 #include "punk_observe/po_compat.h"
24 #include "punk_observe/po_log.h"
25  
26 #define PO_LABEL_MAX 32
27 #define PO_LABEL_KEYMAX 128
28  
29 /* The default allowlist. Deliberately short: these are the dimensions people
30 * actually filter logs by, and every addition multiplies the stream count.
31 * An operator can extend it; the point is that the default is safe rather
32 * than convenient. */
33 static const char *const PO_DEFAULT_LABELS[] = {
34 "service.name",
35 "severity",
36 "host.name",
37 "deployment.environment",
38 NULL
39 };
40  
41 typedef struct {
42 char key[PO_LABEL_MAX][PO_LABEL_KEYMAX];
43 uint32_t klen[PO_LABEL_MAX];
44 int n;
45 } po_labelset;
46  
47 10 static void po_labelset_default(po_labelset *s) {
48 int i;
49 10 memset(s, 0, sizeof(*s));
50 50 ▶ for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) {
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) { 40 10 50
for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) { 40 0 40
51 40 size_t l = strlen(PO_DEFAULT_LABELS[i]);
52 40 memcpy(s->key[i], PO_DEFAULT_LABELS[i], l);
53 40 s->klen[i] = (uint32_t)l;
54 40 s->n++;
55 }
56 10 }
57  
58 5 static int po_labelset_add(po_labelset *s, const char *k, size_t len) {
59 5 ▶ if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0; 5 0 5
if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0; 0 5 5
60 5 memcpy(s->key[s->n], k, len);
61 5 s->klen[s->n] = (uint32_t)len;
62 5 s->n++;
63 5 return 1;
64 }
65  
66 /* Is this attribute a stream label, or does it stay in the record?
67 *
68 * The answer decides whether an attribute multiplies the stream count. A
69 * `user_id` answering yes here is how a log store dies. */
70 65 static int po_is_label(const po_labelset *s, const char *k, size_t len) {
71 int i;
72 150 ▶ for (i = 0; i < s->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->n; i++) 93 57 150
73 93 ▶ if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0)
Branch: 2 branches
BranchTrueFalseTotal
if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0) 10 83 93
if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0) 8 2 10
74 8 return 1;
75 57 return 0;
76 }
77  
78 /* ---- the directory -------------------------------------------------------- */
79  
80 typedef struct {
81 po_block_hdr h;
82 po_u64 off; /* of the compressed bytes within the region */
83 po_u64 bloom_off; /* of the bloom bits */
84 } po_dir_ent;
85  
86 typedef struct {
87 po_dir_ent *e;
88 uint32_t n, cap;
89 } po_blockdir;
90  
91 0 static int po_blockdir_init(po_blockdir *d) {
92 0 memset(d, 0, sizeof(*d));
93 0 d->cap = 16;
94 0 d->e = (po_dir_ent *)calloc(d->cap, sizeof(po_dir_ent));
95 0 return d->e != NULL;
96 }
97  
98 0 static void po_blockdir_free(po_blockdir *d) {
99 0 free(d->e); d->e = NULL; d->n = d->cap = 0;
100 0 }
101  
102 0 static int po_blockdir_add(po_blockdir *d, const po_dir_ent *ent) {
103 0 ▶ if (d->n == d->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (d->n == d->cap) { 0 0 0
104 0 uint32_t want = d->cap * 2;
105 0 po_dir_ent *ne = (po_dir_ent *)realloc(d->e, want * sizeof(po_dir_ent));
106 0 ▶ if (!ne) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ne) return 0; 0 0 0
107 0 d->e = ne; d->cap = want;
108 }
109 0 d->e[d->n++] = *ent;
110 0 return 1;
111 }
112  
113 /* THE PRUNE. Given a time range, a stream filter and a search term, which
114 * blocks must actually be opened?
115 *
116 * Three tests in increasing cost order, and the order is the design:
117 * 1. the stream - an integer compare
118 * 2. the time span - two integer compares, no inflation
119 * 3. the bloom - a few hashes over the query's trigrams
120 *
121 * Only a block surviving all three is decompressed, and then it is matched
122 * exactly. `opened` reports how many survived, so a test can assert that the
123 * pruning actually pruned rather than trusting that it did. */
124 typedef struct {
125 uint32_t considered;
126 uint32_t skipped_stream;
127 uint32_t skipped_time;
128 uint32_t skipped_bloom;
129 uint32_t candidates;
130 } po_prune_stats;
131  
132 1252 static int po_block_candidate(const po_dir_ent *e,
133 int have_stream, po_u64 stream,
134 po_u64 from, po_u64 to,
135 const unsigned char *bloom_bits,
136 const char *q, size_t qlen,
137 po_prune_stats *st) {
138 1252 ▶ if (st) st->considered++;
Branch: 1 branch
BranchTrueFalseTotal
if (st) st->considered++; 1252 0 1252
139  
140 1252 ▶ if (have_stream && e->h.stream != stream) {
Branch: 2 branches
BranchTrueFalseTotal
if (have_stream && e->h.stream != stream) { 2 1250 1252
if (have_stream && e->h.stream != stream) { 1 1 2
141 1 ▶ if (st) st->skipped_stream++;
Branch: 1 branch
BranchTrueFalseTotal
if (st) st->skipped_stream++; 1 0 1
142 1 return 0;
143 }
144 1251 ▶ if (e->h.t_min > to || e->h.t_max < from) {
Branch: 2 branches
BranchTrueFalseTotal
if (e->h.t_min > to || e->h.t_max < from) { 1248 3 1251
if (e->h.t_min > to || e->h.t_max < from) { 12 1236 1248
145 15 ▶ if (st) st->skipped_time++;
Branch: 1 branch
BranchTrueFalseTotal
if (st) st->skipped_time++; 15 0 15
146 15 return 0;
147 }
148 1236 ▶ if (qlen && bloom_bits && po_bloom_query_usable(qlen)) {
Branch: 3 branches
BranchTrueFalseTotal
if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { 1226 10 1236
if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { 1226 0 1226
if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { 1218 8 1226
149 1218 ▶ if (!po_bloom_may_contain(bloom_bits, e->h.bloom_bits - 1, q, qlen)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!po_bloom_may_contain(bloom_bits, e->h.bloom_bits - 1, q, qlen)) { 613 605 1218
150 613 ▶ if (st) st->skipped_bloom++;
Branch: 1 branch
BranchTrueFalseTotal
if (st) st->skipped_bloom++; 613 0 613
151 613 return 0;
152 }
153 }
154 623 ▶ if (st) st->candidates++;
Branch: 1 branch
BranchTrueFalseTotal
if (st) st->candidates++; 623 0 623
155 623 return 1;
156 }
157  
158 #endif /* PO_LOGIDX_H */
« xs/store.xs ↑ Summary xs/plot.xs »