include/punk_observe/po_labels.h

filter: Statementstmt 98.4% 64 / 65 Branchbran 78.2% 36 / 46 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 90.0% 100 / 111 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/exec.xs ↑ Summary include/punk_observe/po_qexec.h »
1 /* po_labels.h - the series id, derived rather than assigned.
2 *
3 * The obvious design hands the compactor a dictionary and has it allocate
4 * dense monotonic ids. That needs a single authority, and phase 4 has just
5 * removed the one place an authority could live: every worker seals its own
6 * segments, so an assigner would be a lock on the hottest path in the system.
7 *
8 * It is also unnecessary. A series IS its label set, so:
9 *
10 * series_id = H128(canonical sorted label block)
11 *
12 * Two workers computing that independently get the same answer with no
13 * coordination, no lock and no shared file. That single property is what
14 * makes per-worker writing affordable.
15 *
16 * The canonical block is what po_attrs_encode already produces in phase 1 -
17 * sorted by key, then tag, then value bytes - and the sort is load-bearing
18 * here rather than tidiness: if the input order leaked into the bytes, the
19 * same series would get two ids, storage would double, and the cardinality
20 * cap would count everything twice.
21 *
22 * AND THE HASH IS STILL VERIFIED. Every lookup compares the full block with
23 * memcmp before returning an existing id. 128 bits makes a collision
24 * vanishingly unlikely; the memcmp makes it impossible. A hash that is only
25 * probably unique is not an identity, and the failure it would cause - two
26 * unrelated services silently merged into one chart - is one nobody would
27 * ever find.
28 */
29 #ifndef PO_LABELS_H
30 #define PO_LABELS_H
31  
32 #include "punk_observe/po_compat.h"
33 #include "punk_observe/po_hash.h"
34 #include "punk_observe/po_rec.h"
35  
36 /* One interned series: its id, and where its label block lives. */
37 typedef struct {
38 po_h128 id;
39 uint32_t off; /* into the owning arena */
40 uint32_t len;
41 uint32_t slot; /* dense ordinal within this segment */
42 } po_series;
43  
44 typedef struct {
45 po_series *ent;
46 uint32_t *idx; /* open-addressed: hash -> ent index + 1, 0 = empty */
47 uint32_t n;
48 uint32_t cap; /* entries */
49 uint32_t mask; /* idx is a power of two */
50 po_arena *arena; /* borrowed: where label blocks live */
51 uint32_t collisions; /* full-hash collisions caught by memcmp */
52 } po_series_tab;
53  
54 38 static int po_series_tab_init(po_series_tab *t, po_arena *arena, uint32_t hint) {
55 38 uint32_t slots = 64;
56 119 ▶ while (slots < hint * 2) slots <<= 1;
Branch: 1 branch
BranchTrueFalseTotal
while (slots < hint * 2) slots <<= 1; 81 38 119
57 38 memset(t, 0, sizeof(*t));
58 38 t->cap = hint < 32 ? 32 : hint;
59 38 t->ent = (po_series *)calloc(t->cap, sizeof(po_series));
60 38 ▶ if (!t->ent) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!t->ent) return 0; 0 38 38
61 38 t->idx = (uint32_t *)calloc(slots, sizeof(uint32_t));
62 38 ▶ if (!t->idx) { free(t->ent); t->ent = NULL; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!t->idx) { free(t->ent); t->ent = NULL; return 0; } 0 38 38
63 38 t->mask = slots - 1;
64 38 t->arena = arena;
65 38 return 1;
66 }
67  
68 38 static void po_series_tab_free(po_series_tab *t) {
69 38 free(t->ent); free(t->idx);
70 38 t->ent = NULL; t->idx = NULL; t->n = t->cap = 0;
71 38 }
72  
73 26 static int po_series_grow(po_series_tab *t) {
74 26 uint32_t slots = (t->mask + 1) * 2;
75 26 uint32_t *ni = (uint32_t *)calloc(slots, sizeof(uint32_t));
76 uint32_t i;
77 26 ▶ if (!ni) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ni) return 0; 0 26 26
78 18842 ▶ for (i = 0; i < t->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < t->n; i++) { 18816 26 18842
79 18816 uint32_t h = (uint32_t)(t->ent[i].id.lo) & (slots - 1);
80 21900 ▶ while (ni[h]) h = (h + 1) & (slots - 1);
Branch: 1 branch
BranchTrueFalseTotal
while (ni[h]) h = (h + 1) & (slots - 1); 3084 18816 21900
81 18816 ni[h] = i + 1;
82 }
83 26 free(t->idx);
84 26 t->idx = ni;
85 26 t->mask = slots - 1;
86 26 return 1;
87 }
88  
89 /* Look up or intern. `block` is the canonical attribute block from
90 * po_attrs_encode. Returns the dense slot, or 0xFFFFFFFF on failure.
91 *
92 * `created` is set when this call introduced the series - which is the ONLY
93 * moment the cardinality cap can be enforced, because it is the only moment
94 * anything knows the set is new. */
95 #define PO_SERIES_ERR 0xFFFFFFFFu
96  
97 15277 static uint32_t po_series_intern(po_series_tab *t,
98 const char *block, uint32_t len,
99 po_h128 *id_out, int *created) {
100 15277 po_h128 h = po_murmur3_128(block, (size_t)len, 0);
101 15277 uint32_t pos = (uint32_t)h.lo & t->mask;
102  
103 15277 ▶ if (created) *created = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (created) *created = 0; 15273 4 15277
104  
105 9497 for (;;) {
106 24774 uint32_t e = t->idx[pos];
107 24774 ▶ if (!e) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) break; 12636 12138 24774
108 {
109 12138 po_series *s = &t->ent[e - 1];
110 12138 ▶ if (po_h128_eq(s->id, h)) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_h128_eq(s->id, h)) { 2641 9497 12138
111 /* The hash matched. Now VERIFY, because a 128-bit match is
112 * not proof and the failure it would hide is invisible. */
113 2641 ▶ if (s->len == len &&
Branch: 2 branches
BranchTrueFalseTotal
if (s->len == len && 2641 0 2641
if (s->len == len && 2640 1 2641
114 2640 ▶ (len == 0 || memcmp(t->arena->base + s->off, block, len) == 0)) {
Branch: 1 branch
BranchTrueFalseTotal
(len == 0 || memcmp(t->arena->base + s->off, block, len) == 0)) { 2640 0 2640
115 2641 ▶ if (id_out) *id_out = h;
Branch: 1 branch
BranchTrueFalseTotal
if (id_out) *id_out = h; 2641 0 2641
116 2641 return s->slot;
117 }
118 /* A genuine full-hash collision on different bytes. Counted,
119 * because if this is ever non-zero in the field it is worth
120 * knowing rather than guessing at. */
121 0 t->collisions++;
122 }
123 }
124 9497 pos = (pos + 1) & t->mask;
125 }
126  
127 12636 ▶ if (t->n == t->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (t->n == t->cap) { 26 12610 12636
128 26 uint32_t want = t->cap * 2;
129 26 po_series *ne = (po_series *)realloc(t->ent, want * sizeof(po_series));
130 26 ▶ if (!ne) return PO_SERIES_ERR;
Branch: 1 branch
BranchTrueFalseTotal
if (!ne) return PO_SERIES_ERR; 0 26 26
131 26 t->ent = ne; t->cap = want;
132 }
133 12636 ▶ if ((t->n + 1) * 2 > t->mask + 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ((t->n + 1) * 2 > t->mask + 1) { 26 12610 12636
134 26 ▶ if (!po_series_grow(t)) return PO_SERIES_ERR;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_series_grow(t)) return PO_SERIES_ERR; 0 26 26
135 26 pos = (uint32_t)h.lo & t->mask;
136 30 ▶ while (t->idx[pos]) pos = (pos + 1) & t->mask;
Branch: 1 branch
BranchTrueFalseTotal
while (t->idx[pos]) pos = (pos + 1) & t->mask; 4 26 30
137 }
138  
139 {
140 12636 ▶ uint32_t off = len ? po_arena_put(t->arena, block, (size_t)len) : 0;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t off = len ? po_arena_put(t->arena, block, (size_t)len) : 0; 12635 1 12636
141 po_series *s;
142 12636 ▶ if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR;
Branch: 2 branches
BranchTrueFalseTotal
if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR; 12635 1 12636
if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR; 0 12635 12635
143 12636 s = &t->ent[t->n];
144 12636 s->id = h;
145 12636 s->off = off;
146 12636 s->len = len;
147 12636 s->slot = t->n;
148 12636 t->idx[pos] = t->n + 1;
149 12636 t->n++;
150 12636 ▶ if (id_out) *id_out = h;
Branch: 1 branch
BranchTrueFalseTotal
if (id_out) *id_out = h; 12636 0 12636
151 12636 ▶ if (created) *created = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (created) *created = 1; 12632 4 12636
152 12636 return s->slot;
153 }
154 }
155  
156 /* The 64 bits stored in po_rec.series. The full 128 live in the segment's
157 * series table; the record carries the low half plus its dense slot, which is
158 * all a reader needs to get back to the whole thing. */
159 715 static po_u64 po_series_key(po_h128 id) { return id.lo; }
160  
161 #endif /* PO_LABELS_H */
« xs/exec.xs ↑ Summary include/punk_observe/po_qexec.h »