include/punk_observe/po_merge.h

filter: Statementstmt 100% 43 / 43 Branchbran 83.3% 25 / 30 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.1% 68 / 73 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_tattr.h ↑ Summary include/punk_observe/po_tsidx.h »
1 /* po_merge.h - the k-way merge that repays phase 4's per-worker writing.
2 *
3 * Phase 4 accepted N segments per block from N workers, because the
4 * alternative was a dedicated writer serialising every ingest. The bill comes
5 * due here, once, off the hot path: N sorted runs become one.
6 *
7 * A loser tree would beat a linear scan of the heads above roughly sixteen
8 * runs. N is the WORKER COUNT - four, eight, sixteen - so the linear scan
9 * wins on cache behaviour and is a tenth of the code. If somebody ever runs
10 * this with sixty-four workers, that is the moment to change it, with the
11 * measurement that justified it.
12 *
13 * THE MERGE IS DETERMINISTIC. The same inputs produce a byte-identical
14 * output, which makes a regression a diff rather than an investigation - and
15 * it means a re-compaction after a crash produces the same segment rather
16 * than a different-but-equivalent one.
17 */
18 #ifndef PO_MERGE_H
19 #define PO_MERGE_H
20  
21 #include "punk_observe/po_compat.h"
22 #include "punk_observe/po_rec.h"
23  
24 #define PO_MERGE_MAX_RUNS 64
25  
26 typedef struct {
27 const po_rec *rec;
28 size_t n, i;
29 } po_run;
30  
31 typedef struct {
32 po_run run[PO_MERGE_MAX_RUNS];
33 int nrun;
34 po_u64 emitted;
35 po_u64 duplicates;
36 } po_merge;
37  
38 16 static void po_merge_init(po_merge *m) { memset(m, 0, sizeof(*m)); }
39  
40 68 static int po_merge_add_run(po_merge *m, const po_rec *r, size_t n) {
41 68 ▶ if (m->nrun >= PO_MERGE_MAX_RUNS) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (m->nrun >= PO_MERGE_MAX_RUNS) return 0; 0 68 68
42 68 m->run[m->nrun].rec = r;
43 68 m->run[m->nrun].n = n;
44 68 m->run[m->nrun].i = 0;
45 68 m->nrun++;
46 68 return 1;
47 }
48  
49 /* The ordering. Time first, then a TOTAL tiebreak - without one the merge is
50 * unstable and two runs of the same inputs differ. */
51 18494 static int po_rec_before(const po_rec *a, const po_rec *b) {
52 18494 ▶ if (a->t_unix_nano != b->t_unix_nano)
Branch: 1 branch
BranchTrueFalseTotal
if (a->t_unix_nano != b->t_unix_nano) 18359 135 18494
53 18359 return a->t_unix_nano < b->t_unix_nano;
54 135 ▶ if (a->series != b->series) return a->series < b->series;
Branch: 1 branch
BranchTrueFalseTotal
if (a->series != b->series) return a->series < b->series; 118 17 135
55 17 ▶ if (a->kind != b->kind) return a->kind < b->kind;
Branch: 1 branch
BranchTrueFalseTotal
if (a->kind != b->kind) return a->kind < b->kind; 1 16 17
56 16 ▶ if (a->span_id != b->span_id) return a->span_id < b->span_id;
Branch: 1 branch
BranchTrueFalseTotal
if (a->span_id != b->span_id) return a->span_id < b->span_id; 0 16 16
57 16 return 0;
58 }
59  
60 20259 static int po_rec_same(const po_rec *a, const po_rec *b) {
61 20259 return a->t_unix_nano == b->t_unix_nano
62 135 ▶ && a->series == b->series
Branch: 1 branch
BranchTrueFalseTotal
&& a->series == b->series 17 118 135
63 17 ▶ && a->kind == b->kind
Branch: 1 branch
BranchTrueFalseTotal
&& a->kind == b->kind 16 1 17
64 16 ▶ && a->span_id == b->span_id
Branch: 1 branch
BranchTrueFalseTotal
&& a->span_id == b->span_id 16 0 16
65 16 ▶ && a->trace_id_hi == b->trace_id_hi
Branch: 1 branch
BranchTrueFalseTotal
&& a->trace_id_hi == b->trace_id_hi 16 0 16
66 20394 ▶ && a->trace_id_lo == b->trace_id_lo;
Branch: 2 branches
BranchTrueFalseTotal
&& a->trace_id_lo == b->trace_id_lo; 135 20124 20259
&& a->trace_id_lo == b->trace_id_lo; 16 0 16
67 }
68  
69 /* Pull the next record. Returns NULL when every run is drained.
70 *
71 * DUPLICATES ARE COLLAPSED HERE. Phase 4's crash window - a WAL consumed into
72 * a segment, then re-consumed after a crash between rename and unlink -
73 * leaves the same records twice. Making the write path idempotent would cost
74 * a fsync and a lookup per batch on the hot path; collapsing on the read side
75 * costs one comparison in a merge that is already comparing. */
76 1829 static const po_rec *po_merge_next(po_merge *m) {
77 1829 int i, best = -1;
78 const po_rec *out;
79  
80 for (;;) {
81 1829 best = -1;
82 22500 ▶ for (i = 0; i < m->nrun; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < m->nrun; i++) { 20671 1829 22500
83 20671 ▶ if (m->run[i].i >= m->run[i].n) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (m->run[i].i >= m->run[i].n) continue; 364 20307 20671
84 38801 if (best < 0 ||
85 18494 po_rec_before(&m->run[i].rec[m->run[i].i],
86 18494 &m->run[best].rec[m->run[best].i]))
87 4204 best = i;
88 }
89 1829 ▶ if (best < 0) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (best < 0) return NULL; 16 1813 1829
90  
91 1813 out = &m->run[best].rec[m->run[best].i];
92 1813 m->run[best].i++;
93  
94 /* Drain any identical record from the other runs. */
95 {
96 1813 int dropped = 0;
97 22416 ▶ for (i = 0; i < m->nrun; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < m->nrun; i++) { 20603 1813 22416
98 40878 while (m->run[i].i < m->run[i].n &&
99 20259 po_rec_same(&m->run[i].rec[m->run[i].i], out)) {
100 16 m->run[i].i++;
101 16 dropped++;
102 }
103 }
104 1813 m->duplicates += (po_u64)dropped;
105 }
106 1813 m->emitted++;
107 1813 return out;
108 }
109 }
110  
111 #endif /* PO_MERGE_H */
« include/punk_observe/po_tattr.h ↑ Summary include/punk_observe/po_tsidx.h »