include/punk_observe/po_traceidx.h

filter: Statementstmt 96.7% 60 / 62 Branchbran 74.0% 37 / 50 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 86.6% 97 / 112 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_chunk.h ↑ Summary include/punk_observe/po_log.h »
1 /* po_traceidx.h - trace id to spans, in one probe.
2 *
3 * Trace ids are random 128-bit values. There is no locality to exploit, no
4 * range to scan, and a sorted index would cost a binary search over a large
5 * file with a cache miss at every level. The question is a POINT LOOKUP, so
6 * the structure is a hash table.
7 *
8 * Open-addressed, power-of-two, linear probing, mmap'd straight out of the
9 * segment. A lookup is one hash, one probe that is almost always the first
10 * slot, and one read of the spans at that offset. The whole point is that
11 * looking up a trace does not depend on how much data the tenant has.
12 *
13 * THE SLOT STORES THE FULL SIXTEEN BYTES.
14 *
15 * A 64-bit hash alone would collide, and the failure that produces is two
16 * unrelated traces MERGED into one - a waterfall showing spans from somebody
17 * else's request. That is the most confusing thing this system could do, and
18 * nobody would ever guess at the cause. Sixteen bytes per slot is cheap
19 * insurance against it.
20 *
21 * SIZED FROM THE DISTINCT TRACE COUNT, NOT THE SPAN COUNT. A segment with a
22 * million spans across ten thousand traces needs ten thousand slots. Sizing
23 * from the span count would waste 99% of the table; sizing from a guess would
24 * make every probe a scan.
25 */
26 #ifndef PO_TRACEIDX_H
27 #define PO_TRACEIDX_H
28  
29 #include "punk_observe/po_compat.h"
30 #include "punk_observe/po_span.h"
31  
32 /* 32 bytes: the id, where its spans start, and how many. */
33 typedef struct {
34 po_u64 trace_hi, trace_lo;
35 uint32_t first; /* ordinal of the first span of this trace */
36 uint32_t count;
37 uint32_t flags;
38 uint32_t pad;
39 } po_tslot;
40  
41 #define PO_TSLOT_SIZE 32
42 #define PO_TIDX_LOAD 2 /* slots = distinct * 2, so load factor 0.5 */
43  
44 typedef struct {
45 po_tslot *slot;
46 uint32_t slots, mask;
47 uint32_t n;
48 po_u64 probes; /* total probes performed, for the measurement */
49 po_u64 lookups;
50 } po_traceidx;
51  
52 /* The hash. The id is already random, so this only needs to mix the two
53 * halves; murmur's finaliser is right there and costs nothing. */
54 3980 static uint32_t po_trace_hash(po_u64 hi, po_u64 lo) {
55 3980 return (uint32_t)(po_fmix64(hi ^ (lo * (po_u64)0x9E3779B97F4A7C15ULL)));
56 }
57  
58 21 static int po_traceidx_init(po_traceidx *t, uint32_t distinct) {
59 21 uint32_t slots = 16;
60 21 memset(t, 0, sizeof(*t));
61 51 ▶ while (slots < distinct * PO_TIDX_LOAD) slots <<= 1;
Branch: 1 branch
BranchTrueFalseTotal
while (slots < distinct * PO_TIDX_LOAD) slots <<= 1; 30 21 51
62 21 t->slot = (po_tslot *)calloc(slots, sizeof(po_tslot));
63 21 ▶ if (!t->slot) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!t->slot) return 0; 0 21 21
64 21 t->slots = slots;
65 21 t->mask = slots - 1;
66 21 return 1;
67 }
68  
69 21 static void po_traceidx_free(po_traceidx *t) {
70 21 free(t->slot); t->slot = NULL; t->slots = t->n = 0;
71 21 }
72  
73 6223 static int po_tslot_empty(const po_tslot *s) {
74 /* An all-zero trace id is invalid and is refused at ingest, so zero is a
75 * safe empty marker rather than a value that could collide with a real
76 * id. Phase 1 enforces that; this depends on it. */
77 6223 ▶ return s->trace_hi == 0 && s->trace_lo == 0;
Branch: 2 branches
BranchTrueFalseTotal
return s->trace_hi == 0 && s->trace_lo == 0; 2976 3247 6223
return s->trace_hi == 0 && s->trace_lo == 0; 2976 0 2976
78 }
79  
80 2776 static int po_traceidx_put(po_traceidx *t, po_u64 hi, po_u64 lo,
81 uint32_t first, uint32_t count) {
82 2776 uint32_t h = po_trace_hash(hi, lo) & t->mask;
83 2776 ▶ if (!po_trace_id_valid(hi, lo)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!po_trace_id_valid(hi, lo)) return 0; 2776 0 2776
if (!po_trace_id_valid(hi, lo)) return 0; 0 0 0
84 1407 for (;;) {
85 4183 po_tslot *s = &t->slot[h];
86 4183 ▶ if (po_tslot_empty(s)) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_tslot_empty(s)) { 2776 1407 4183
87 2776 s->trace_hi = hi; s->trace_lo = lo;
88 2776 s->first = first; s->count = count;
89 2776 t->n++;
90 2776 return 1;
91 }
92 1407 ▶ if (s->trace_hi == hi && s->trace_lo == lo) {
Branch: 2 branches
BranchTrueFalseTotal
if (s->trace_hi == hi && s->trace_lo == lo) { 0 1407 1407
if (s->trace_hi == hi && s->trace_lo == lo) { 0 0 0
93 /* Same trace seen again in this segment: extend the run. Spans
94 * are sorted by trace, so the run is contiguous. */
95 0 s->count += count;
96 0 return 1;
97 }
98 1407 h = (h + 1) & t->mask;
99 }
100 }
101  
102 /* Returns 1 and fills first/count, or 0. Counts probes so a test can assert
103 * the table is doing its job rather than degenerating into a scan. */
104 1204 static int po_traceidx_get(po_traceidx *t, po_u64 hi, po_u64 lo,
105 uint32_t *first, uint32_t *count) {
106 1204 uint32_t h = po_trace_hash(hi, lo) & t->mask;
107 1204 uint32_t probed = 0;
108 1204 t->lookups++;
109 836 for (;;) {
110 2040 po_tslot *s = &t->slot[h];
111 2040 probed++;
112 2040 ▶ if (po_tslot_empty(s)) { t->probes += probed; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (po_tslot_empty(s)) { t->probes += probed; return 0; } 200 1840 2040
113 /* The FULL comparison. A hash match is a probe hint, never proof. */
114 1840 ▶ if (s->trace_hi == hi && s->trace_lo == lo) {
Branch: 2 branches
BranchTrueFalseTotal
if (s->trace_hi == hi && s->trace_lo == lo) { 1004 836 1840
if (s->trace_hi == hi && s->trace_lo == lo) { 1004 0 1004
115 1004 ▶ if (first) *first = s->first;
Branch: 1 branch
BranchTrueFalseTotal
if (first) *first = s->first; 1004 0 1004
116 1004 ▶ if (count) *count = s->count;
Branch: 1 branch
BranchTrueFalseTotal
if (count) *count = s->count; 1004 0 1004
117 1004 t->probes += probed;
118 1004 return 1;
119 }
120 836 h = (h + 1) & t->mask;
121 836 ▶ if (probed > t->slots) { t->probes += probed; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (probed > t->slots) { t->probes += probed; return 0; } 0 836 836
122 }
123 }
124  
125 /* Build the index from spans already sorted by (trace, start). Because they
126 * are sorted, each trace is one contiguous run and the index is built in a
127 * single pass with no counting phase. */
128 21 static int po_traceidx_build(po_traceidx *t, const po_span *s, uint32_t n) {
129 21 uint32_t i = 0, distinct = 0;
130  
131 /* Count distinct traces first: the table is sized from THIS, not n. */
132 2797 ▶ while (i < n) {
Branch: 1 branch
BranchTrueFalseTotal
while (i < n) { 2776 21 2797
133 2776 uint32_t j = i + 1;
134 9595 ▶ while (j < n && s[j].trace_hi == s[i].trace_hi
Branch: 1 branch
BranchTrueFalseTotal
while (j < n && s[j].trace_hi == s[i].trace_hi 4064 2755 6819
135 6840 ▶ && s[j].trace_lo == s[i].trace_lo) j++;
Branch: 2 branches
BranchTrueFalseTotal
&& s[j].trace_lo == s[i].trace_lo) j++; 6819 20 6839
&& s[j].trace_lo == s[i].trace_lo) j++; 4063 1 4064
136 2776 distinct++;
137 2776 i = j;
138 }
139 21 ▶ if (!po_traceidx_init(t, distinct ? distinct : 1)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!po_traceidx_init(t, distinct ? distinct : 1)) return 0; 20 1 21
if (!po_traceidx_init(t, distinct ? distinct : 1)) return 0; 0 21 21
140  
141 21 i = 0;
142 2797 ▶ while (i < n) {
Branch: 1 branch
BranchTrueFalseTotal
while (i < n) { 2776 21 2797
143 2776 uint32_t j = i + 1;
144 9595 ▶ while (j < n && s[j].trace_hi == s[i].trace_hi
Branch: 1 branch
BranchTrueFalseTotal
while (j < n && s[j].trace_hi == s[i].trace_hi 4064 2755 6819
145 6840 ▶ && s[j].trace_lo == s[i].trace_lo) j++;
Branch: 2 branches
BranchTrueFalseTotal
&& s[j].trace_lo == s[i].trace_lo) j++; 6819 20 6839
&& s[j].trace_lo == s[i].trace_lo) j++; 4063 1 4064
146 2776 po_traceidx_put(t, s[i].trace_hi, s[i].trace_lo, i, j - i);
147 2776 i = j;
148 }
149 21 return 1;
150 }
151  
152 #endif /* PO_TRACEIDX_H */
« include/punk_observe/po_chunk.h ↑ Summary include/punk_observe/po_log.h »