include/punk_observe/po_intern.h

filter: Statementstmt 98.8% 87 / 88 Branchbran 62.0% 36 / 58 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 84.2% 123 / 146 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/svg.xs ↑ Summary xs/alert.xs »
1 /* po_intern.h - the per-segment symbol table.
2 *
3 * Where the compression actually comes from. Not the codecs: this.
4 *
5 * Every attribute key, string value, service name, span name and metric name
6 * in a segment becomes a uint32_t, stored once. A million spans from one
7 * service store the string "checkout" once and a four-byte reference a
8 * million times. It also means predicate evaluation in phase 9 compares
9 * integers rather than strings, which is the difference between a scan that
10 * is memory-bound and one that is not.
11 *
12 * Interning is PER SEGMENT, not global. Phase 4 has no global authority by
13 * design - every worker seals its own segments - so each segment carries its
14 * own table and compaction re-interns globally for the block. The duplication
15 * across N workers is bounded by distinct-strings times workers within one
16 * two-hour block, and it is paid off exactly once, later, off the hot path.
17 */
18 #ifndef PO_INTERN_H
19 #define PO_INTERN_H
20  
21 #include "punk_observe/po_compat.h"
22 #include "punk_observe/po_hash.h"
23 #include "punk_observe/po_rec.h"
24  
25 #define PO_SYM_NONE 0xFFFFFFFFu
26  
27 typedef struct {
28 uint32_t off; /* into the blob */
29 uint32_t len;
30 } po_sym;
31  
32 typedef struct {
33 po_sym *sym;
34 uint32_t *idx; /* open-addressed: hash -> sym index + 1 */
35 uint32_t n, cap, mask;
36 po_arena blob; /* the bytes, owned */
37 } po_intern;
38  
39 269 static int po_intern_init(po_intern *t, uint32_t hint) {
40 269 uint32_t slots = 64;
41 888 ▶ while (slots < hint * 2) slots <<= 1;
Branch: 1 branch
BranchTrueFalseTotal
while (slots < hint * 2) slots <<= 1; 619 269 888
42 269 memset(t, 0, sizeof(*t));
43 269 t->cap = hint < 32 ? 32 : hint;
44 269 t->sym = (po_sym *)calloc(t->cap, sizeof(po_sym));
45 269 ▶ if (!t->sym) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!t->sym) return 0; 0 269 269
46 269 t->idx = (uint32_t *)calloc(slots, sizeof(uint32_t));
47 269 ▶ if (!t->idx) { free(t->sym); t->sym = NULL; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!t->idx) { free(t->sym); t->sym = NULL; return 0; } 0 269 269
48 269 ▶ if (!po_arena_init(&t->blob, 4096)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!po_arena_init(&t->blob, 4096)) { 0 269 269
49 0 free(t->sym); free(t->idx); t->sym = NULL; t->idx = NULL; return 0;
50 }
51 269 t->mask = slots - 1;
52 269 return 1;
53 }
54  
55 269 static void po_intern_free(po_intern *t) {
56 269 free(t->sym); free(t->idx);
57 269 po_arena_free(&t->blob);
58 269 t->sym = NULL; t->idx = NULL; t->n = t->cap = 0;
59 269 }
60  
61 12 static int po_intern_grow(po_intern *t) {
62 12 uint32_t slots = (t->mask + 1) * 2;
63 12 uint32_t *ni = (uint32_t *)calloc(slots, sizeof(uint32_t));
64 uint32_t i;
65 12 ▶ if (!ni) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ni) return 0; 0 12 12
66 7180 ▶ for (i = 0; i < t->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < t->n; i++) { 7168 12 7180
67 7168 uint32_t h = po_hash32(t->blob.base + t->sym[i].off, t->sym[i].len)
68 7168 & (slots - 1);
69 8300 ▶ while (ni[h]) h = (h + 1) & (slots - 1);
Branch: 1 branch
BranchTrueFalseTotal
while (ni[h]) h = (h + 1) & (slots - 1); 1132 7168 8300
70 7168 ni[h] = i + 1;
71 }
72 12 free(t->idx);
73 12 t->idx = ni;
74 12 t->mask = slots - 1;
75 12 return 1;
76 }
77  
78 /* Intern a string, returning its id. Same bytes always give the same id
79 * WITHIN a segment; ids mean nothing across segments, which is why a reader
80 * always resolves through the segment's own table. */
81 32802 static uint32_t po_intern_put(po_intern *t, const char *p, size_t len) {
82 32802 uint32_t h = po_hash32(p, len) & t->mask;
83  
84 6097 for (;;) {
85 38899 uint32_t e = t->idx[h];
86 38899 ▶ if (!e) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) break; 8988 29911 38899
87 {
88 29911 po_sym *s = &t->sym[e - 1];
89 /* memcmp, always: a 32-bit hash match here is a probe hint and
90 * nothing more. */
91 29911 ▶ if (s->len == len &&
Branch: 2 branches
BranchTrueFalseTotal
if (s->len == len && 27272 2639 29911
if (s->len == len && 27272 0 27272
92 27272 ▶ (len == 0 || memcmp(t->blob.base + s->off, p, len) == 0))
Branch: 1 branch
BranchTrueFalseTotal
(len == 0 || memcmp(t->blob.base + s->off, p, len) == 0)) 23814 3458 27272
93 23814 return e - 1;
94 }
95 6097 h = (h + 1) & t->mask;
96 }
97  
98 8988 ▶ if (t->n == t->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (t->n == t->cap) { 12 8976 8988
99 12 uint32_t want = t->cap * 2;
100 12 po_sym *ns = (po_sym *)realloc(t->sym, want * sizeof(po_sym));
101 12 ▶ if (!ns) return PO_SYM_NONE;
Branch: 1 branch
BranchTrueFalseTotal
if (!ns) return PO_SYM_NONE; 0 12 12
102 12 t->sym = ns; t->cap = want;
103 }
104 8988 ▶ if ((t->n + 1) * 2 > t->mask + 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ((t->n + 1) * 2 > t->mask + 1) { 12 8976 8988
105 12 ▶ if (!po_intern_grow(t)) return PO_SYM_NONE;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_intern_grow(t)) return PO_SYM_NONE; 0 12 12
106 12 h = po_hash32(p, len) & t->mask;
107 20 ▶ while (t->idx[h]) h = (h + 1) & t->mask;
Branch: 1 branch
BranchTrueFalseTotal
while (t->idx[h]) h = (h + 1) & t->mask; 8 12 20
108 }
109  
110 {
111 8988 uint32_t off = po_arena_put(&t->blob, p, len);
112 8988 ▶ if (off == PO_ARENA_ERR) return PO_SYM_NONE;
Branch: 1 branch
BranchTrueFalseTotal
if (off == PO_ARENA_ERR) return PO_SYM_NONE; 0 8988 8988
113 8988 t->sym[t->n].off = off;
114 8988 t->sym[t->n].len = (uint32_t)len;
115 8988 t->idx[h] = t->n + 1;
116 8988 return t->n++;
117 }
118 }
119  
120 1104 static const char *po_intern_get(const po_intern *t, uint32_t id, uint32_t *len) {
121 1104 ▶ if (id >= t->n) { if (len) *len = 0; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (id >= t->n) { if (len) *len = 0; return NULL; } 0 1104 1104
if (id >= t->n) { if (len) *len = 0; return NULL; } 0 0 0
122 1104 ▶ if (len) *len = t->sym[id].len;
Branch: 1 branch
BranchTrueFalseTotal
if (len) *len = t->sym[id].len; 1104 0 1104
123 1104 return t->blob.base + t->sym[id].off;
124 }
125  
126 /* Serialise: [count][offsets][blob]. The offsets are relative to the blob, so
127 * the whole region is position-independent once mmap'd. */
128 29 static size_t po_intern_size(const po_intern *t) {
129 29 return 8 + (size_t)t->n * 8 + t->blob.len;
130 }
131  
132 29 static void po_intern_write(const po_intern *t, char *out) {
133 uint32_t i;
134 uint32_t v;
135 29 char *q = out;
136 29 v = po_le32(t->n); memcpy(q, &v, 4); q += 4;
137 29 v = po_le32((uint32_t)t->blob.len); memcpy(q, &v, 4); q += 4;
138 749 ▶ for (i = 0; i < t->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < t->n; i++) { 720 29 749
139 720 v = po_le32(t->sym[i].off); memcpy(q, &v, 4); q += 4;
140 720 v = po_le32(t->sym[i].len); memcpy(q, &v, 4); q += 4;
141 }
142 29 ▶ if (t->blob.len) memcpy(q, t->blob.base, t->blob.len);
Branch: 1 branch
BranchTrueFalseTotal
if (t->blob.len) memcpy(q, t->blob.base, t->blob.len); 29 0 29
143 29 }
144  
145 /* A read-only view over a serialised table, straight out of an mmap. Nothing
146 * is copied and nothing is allocated. */
147 typedef struct {
148 const char *base;
149 uint32_t n;
150 const char *offs; /* n pairs of (off, len) */
151 const char *blob;
152 uint32_t bloblen;
153 } po_intern_view;
154  
155 656 static int po_intern_open(po_intern_view *v, const char *p, size_t len) {
156 uint32_t n, bl;
157 656 ▶ if (len < 8) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (len < 8) return 0; 0 656 656
158 656 memcpy(&n, p, 4); n = po_le32(n);
159 656 memcpy(&bl, p + 4, 4); bl = po_le32(bl);
160 656 ▶ if ((size_t)8 + (size_t)n * 8 + bl > len) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((size_t)8 + (size_t)n * 8 + bl > len) return 0; 0 656 656
161 656 v->base = p; v->n = n;
162 656 v->offs = p + 8;
163 656 v->blob = p + 8 + (size_t)n * 8;
164 656 v->bloblen = bl;
165 656 return 1;
166 }
167  
168 83 static const char *po_intern_view_get(const po_intern_view *v, uint32_t id,
169 uint32_t *len) {
170 uint32_t off, l;
171 83 ▶ if (id >= v->n) { if (len) *len = 0; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (id >= v->n) { if (len) *len = 0; return NULL; } 0 83 83
if (id >= v->n) { if (len) *len = 0; return NULL; } 0 0 0
172 83 memcpy(&off, v->offs + (size_t)id * 8, 4); off = po_le32(off);
173 83 memcpy(&l, v->offs + (size_t)id * 8 + 4, 4); l = po_le32(l);
174 83 ▶ if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; } 0 83 83
if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; } 0 0 0
175 83 ▶ if (len) *len = l;
Branch: 1 branch
BranchTrueFalseTotal
if (len) *len = l; 83 0 83
176 83 return v->blob + off;
177 }
178  
179 #endif /* PO_INTERN_H */
« xs/svg.xs ↑ Summary xs/alert.xs »