| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (first) *first = s->first; |
1004 |
0 |
1004 |
|
| 116 |
1004 |
▶ | if (count) *count = s->count; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && 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 */ |