include/punk_observe/po_gorilla.h

filter: Statementstmt 100% 112 / 112 Branchbran 87.1% 68 / 78 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 94.7% 180 / 190 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_tsidx.h ↑ Summary include/punk_observe/po_lex.h »
1 /* po_gorilla.h - delta-of-delta timestamps, XOR values.
2 *
3 * A naive point is 16 bytes: 8 of timestamp, 8 of double. A series scraped
4 * every 15 seconds for a day is 5,760 points, 92KB, times however many series
5 * a fleet has. The published Gorilla result is about 1.37 bytes per point,
6 * and the two halves are independent and both simple.
7 *
8 * TIMESTAMPS: DELTA OF DELTA. Points arrive on an interval, so the delta is
9 * nearly constant and the delta of the delta is nearly always zero.
10 *
11 * ONE DEPARTURE FROM THE PAPER, AND IT IS FORCED. Gorilla stores the second
12 * timestamp as a 14-bit delta, because its timestamps are SECONDS. OTLP
13 * timestamps are NANOSECONDS: a 15-second scrape interval is 1.5e10 ns, which
14 * does not fit 14 bits, or 32. So the first delta is written as a full 64
15 * bits. It costs eight bytes ONCE per chunk - amortised over 120 points that
16 * is under a bit each - and taking the published constant unexamined would
17 * have produced a decoder that silently truncates every interval.
18 *
19 * VALUES: XOR AGAINST THE PREVIOUS. A gauge that barely moves and a counter
20 * that increments both XOR to a value with long runs of leading and trailing
21 * zeros.
22 */
23 #ifndef PO_GORILLA_H
24 #define PO_GORILLA_H
25  
26 #include "punk_observe/po_compat.h"
27 #include "punk_observe/po_bits.h"
28  
29 typedef struct {
30 po_bw bw;
31 po_u64 t_prev;
32 po_i64 d_prev; /* the previous delta, signed: points can arrive
33 * out of order and a delta can be negative */
34 po_u64 v_prev; /* the previous value's BIT PATTERN */
35 int lead_prev;
36 int len_prev;
37 uint32_t n;
38 } po_gor_w;
39  
40 49 static int po_gor_w_init(po_gor_w *g) {
41 49 memset(g, 0, sizeof(*g));
42 49 g->lead_prev = -1;
43 49 return po_bw_init(&g->bw, 256);
44 }
45  
46 49 static void po_gor_w_free(po_gor_w *g) { po_bw_free(&g->bw); }
47  
48 /* Append one point. `bits` is the value's BIT PATTERN, not its numeric value.
49 *
50 * Passing the bit pattern rather than a double is deliberate: it makes NaN
51 * payloads, the infinities and negative zero survive exactly, and it means
52 * an integer point (OTLP's as_int) uses the identical path without a lossy
53 * trip through a double. */
54 105037 static void po_gor_put(po_gor_w *g, po_u64 t, po_u64 bits) {
55 105037 ▶ if (g->n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->n == 0) { 49 104988 105037
56 49 po_bw_put(&g->bw, t, 64); /* the anchor timestamp */
57 49 po_bw_put(&g->bw, bits, 64); /* and the anchor value */
58 49 g->t_prev = t;
59 49 g->v_prev = bits;
60 49 g->d_prev = 0;
61 49 g->n = 1;
62 49 return;
63 }
64  
65 104988 ▶ if (g->n == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->n == 1) { 48 104940 104988
66 /* The first delta, in full. See the header note: nanoseconds do not
67 * fit the paper's 14 bits. */
68 48 po_i64 d = (po_i64)(t - g->t_prev);
69 48 po_bw_put(&g->bw, (po_u64)d, 64);
70 48 g->d_prev = d;
71 48 g->t_prev = t;
72 }
73 else {
74 104940 po_i64 d = (po_i64)(t - g->t_prev);
75 104940 po_i64 dod = d - g->d_prev;
76  
77 /* THE RANGES ARE TWO'S-COMPLEMENT RANGES, NOT THE PAPER'S.
78 *
79 * Gorilla is usually written as [-63, 64] in 7 bits, [-255, 256] in
80 * 9, and so on. Those are 128 and 512 distinct values, so they fit -
81 * but only with an offset. Stored DIRECTLY as two's complement, 7
82 * bits holds -64..63, and a dod of 64 written that way reads back as
83 * -64. The point lands in the wrong place and nothing reports it.
84 *
85 * Taking the published constants unexamined put exactly that bug in
86 * here, and the bucket-boundary test caught it. */
87 104940 ▶ if (dod == 0) po_bw_put1(&g->bw, 0);
Branch: 1 branch
BranchTrueFalseTotal
if (dod == 0) po_bw_put1(&g->bw, 0); 104920 20 104940
88 20 ▶ else if (dod >= -64 && dod <= 63) {
Branch: 2 branches
BranchTrueFalseTotal
else if (dod >= -64 && dod <= 63) { 12 8 20
else if (dod >= -64 && dod <= 63) { 2 10 12
89 2 po_bw_put(&g->bw, 0x2, 2); /* 10 */
90 2 po_bw_put(&g->bw, (po_u64)dod & 0x7F, 7);
91 }
92 18 ▶ else if (dod >= -256 && dod <= 255) {
Branch: 2 branches
BranchTrueFalseTotal
else if (dod >= -256 && dod <= 255) { 12 6 18
else if (dod >= -256 && dod <= 255) { 4 8 12
93 4 po_bw_put(&g->bw, 0x6, 3); /* 110 */
94 4 po_bw_put(&g->bw, (po_u64)dod & 0x1FF, 9);
95 }
96 14 ▶ else if (dod >= -2048 && dod <= 2047) {
Branch: 2 branches
BranchTrueFalseTotal
else if (dod >= -2048 && dod <= 2047) { 10 4 14
else if (dod >= -2048 && dod <= 2047) { 4 6 10
97 4 po_bw_put(&g->bw, 0xE, 4); /* 1110 */
98 4 po_bw_put(&g->bw, (po_u64)dod & 0xFFF, 12);
99 }
100 10 ▶ else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) {
Branch: 2 branches
BranchTrueFalseTotal
else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) { 9 1 10
else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) { 7 2 9
101 7 po_bw_put(&g->bw, 0x1E, 5); /* 11110 */
102 7 po_bw_put(&g->bw, (po_u64)dod & 0xFFFFFFFFu, 32);
103 }
104 else {
105 /* The 64-bit escape. Gorilla has no such case because its
106 * timestamps are seconds; nanoseconds reach it whenever a series
107 * genuinely jumps, and without it those points would be lost. */
108 3 po_bw_put(&g->bw, 0x1F, 5); /* 11111 */
109 3 po_bw_put(&g->bw, (po_u64)dod, 64);
110 }
111 104940 g->d_prev = d;
112 104940 g->t_prev = t;
113 }
114  
115 { /* the value */
116 104988 po_u64 x = g->v_prev ^ bits;
117 104988 ▶ if (x == 0) po_bw_put1(&g->bw, 0);
Branch: 1 branch
BranchTrueFalseTotal
if (x == 0) po_bw_put1(&g->bw, 0); 353 104635 104988
118 else {
119 104635 int lead = 0, trail = 0, i;
120 532613 ▶ for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++;
Branch: 2 branches
BranchTrueFalseTotal
for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++; 532613 0 532613
for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++; 427978 104635 532613
121 544918 ▶ for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++;
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++; 544918 0 544918
for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++; 440283 104635 544918
122 104635 ▶ if (lead > 31) lead = 31; /* the field is 5 bits */
Branch: 1 branch
BranchTrueFalseTotal
if (lead > 31) lead = 31; /* the field is 5 bits */ 585 104050 104635
123  
124 104635 po_bw_put1(&g->bw, 1);
125 /* REUSE REQUIRES THE MEANINGFUL BITS TO FIT THE PREVIOUS WINDOW
126 * IN POSITION, NOT MERELY IN WIDTH.
127 *
128 * The previous window covers bits [lead_prev, lead_prev+len_prev),
129 * so reuse is only valid when this xor's meaningful range sits
130 * inside it: lead >= lead_prev AND trail >= trail_prev.
131 *
132 * The first version checked `(64 - lead - trail) <= len_prev` -
133 * the WIDTH fits - which is not the same thing. An xor whose bits
134 * start inside the window but extend past its bottom had the
135 * overhang silently shifted away, and the decoder reconstructed a
136 * different number. No crash, no error: a wrong value on a chart.
137 *
138 * It survived 100,000 random doubles because random values never
139 * take this branch - consecutive random mantissas share nothing,
140 * so every point stores a new window. A smoothly increasing
141 * series takes it on almost every point, which is what most real
142 * metrics are. */
143 104635 ▶ if (g->lead_prev >= 0 && g->len_prev > 0
Branch: 2 branches
BranchTrueFalseTotal
if (g->lead_prev >= 0 && g->len_prev > 0 104591 44 104635
if (g->lead_prev >= 0 && g->len_prev > 0 104591 0 104591
144 104591 ▶ && lead >= g->lead_prev
Branch: 1 branch
BranchTrueFalseTotal
&& lead >= g->lead_prev 104289 302 104591
145 104289 ▶ && trail >= 64 - g->lead_prev - g->len_prev) {
Branch: 1 branch
BranchTrueFalseTotal
&& trail >= 64 - g->lead_prev - g->len_prev) { 104165 124 104289
146 104165 po_bw_put1(&g->bw, 0);
147 104165 po_bw_put(&g->bw, x >> (64 - g->lead_prev - g->len_prev),
148 g->len_prev);
149 }
150 else {
151 470 int len = 64 - lead - trail;
152 470 ▶ if (len < 1) len = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (len < 1) len = 1; 0 470 470
153 470 ▶ if (len > 64) len = 64;
Branch: 1 branch
BranchTrueFalseTotal
if (len > 64) len = 64; 0 470 470
154 470 po_bw_put1(&g->bw, 1);
155 470 po_bw_put(&g->bw, (po_u64)lead, 5);
156 /* 64 is written as 0 in six bits: a length of 0 is
157 * meaningless (that is the xor==0 case), so the encoding is
158 * unambiguous and 64-bit differences stay representable. */
159 470 po_bw_put(&g->bw, (po_u64)(len & 0x3F), 6);
160 470 po_bw_put(&g->bw, x >> trail, len);
161 470 g->lead_prev = lead;
162 470 g->len_prev = len;
163 }
164 }
165 104988 g->v_prev = bits;
166 }
167 104988 g->n++;
168 }
169  
170 /* ---- reading ------------------------------------------------------------- */
171  
172 typedef struct {
173 po_br br;
174 po_u64 t_prev;
175 po_i64 d_prev;
176 po_u64 v_prev;
177 int lead_prev;
178 int len_prev;
179 uint32_t i, n;
180 } po_gor_r;
181  
182 47 static void po_gor_r_init(po_gor_r *g, const void *buf, size_t nbits,
183 uint32_t count) {
184 47 memset(g, 0, sizeof(*g));
185 47 po_br_init(&g->br, buf, nbits);
186 47 g->lead_prev = -1;
187 47 g->n = count;
188 47 }
189  
190 /* Returns 1 and fills *t and *bits, or 0 at the end / on a malformed stream. */
191 105054 static int po_gor_next(po_gor_r *g, po_u64 *t, po_u64 *bits) {
192 105054 ▶ if (g->br.err || g->i >= g->n) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (g->br.err || g->i >= g->n) return 0; 105054 0 105054
if (g->br.err || g->i >= g->n) return 0; 47 105007 105054
193  
194 105007 ▶ if (g->i == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->i == 0) { 47 104960 105007
195 47 g->t_prev = po_br_get(&g->br, 64);
196 47 g->v_prev = po_br_get(&g->br, 64);
197 47 g->d_prev = 0;
198 }
199 104960 ▶ else if (g->i == 1) {
Branch: 1 branch
BranchTrueFalseTotal
else if (g->i == 1) { 46 104914 104960
200 46 po_i64 d = (po_i64)po_br_get(&g->br, 64);
201 46 g->d_prev = d;
202 46 g->t_prev = (po_u64)((po_i64)g->t_prev + d);
203 46 goto value;
204 }
205 else {
206 104914 po_i64 dod = 0;
207 104914 ▶ if (po_br_get1(&g->br) == 0) dod = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (po_br_get1(&g->br) == 0) dod = 0; 104894 20 104914
208 20 ▶ else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 7), 7);
Branch: 1 branch
BranchTrueFalseTotal
else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 7), 7); 2 18 20
209 18 ▶ else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 9), 9);
Branch: 1 branch
BranchTrueFalseTotal
else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 9), 9); 4 14 18
210 14 ▶ else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 12), 12);
Branch: 1 branch
BranchTrueFalseTotal
else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 12), 12); 4 10 14
211 10 ▶ else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 32), 32);
Branch: 1 branch
BranchTrueFalseTotal
else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 32), 32); 7 3 10
212 3 else dod = (po_i64)po_br_get(&g->br, 64);
213  
214 104914 g->d_prev = g->d_prev + dod;
215 104914 g->t_prev = (po_u64)((po_i64)g->t_prev + g->d_prev);
216 104914 goto value;
217 }
218  
219 47 ▶ if (g->br.err) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (g->br.err) return 0; 0 47 47
220 47 *t = g->t_prev; *bits = g->v_prev;
221 47 g->i++;
222 47 return 1;
223  
224 104960 value:
225 {
226 104960 ▶ if (po_br_get1(&g->br) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_br_get1(&g->br) == 0) { 104616 344 104960
227 /* unchanged */
228 }
229 104616 ▶ else if (po_br_get1(&g->br) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
else if (po_br_get1(&g->br) == 0) { 104152 464 104616
230 po_u64 m;
231 104152 ▶ if (g->len_prev <= 0) { g->br.err = 1; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (g->len_prev <= 0) { g->br.err = 1; return 0; } 0 104152 104152
232 104152 m = po_br_get(&g->br, g->len_prev);
233 104152 g->v_prev ^= m << (64 - g->lead_prev - g->len_prev);
234 }
235 else {
236 464 int lead = (int)po_br_get(&g->br, 5);
237 464 int len = (int)po_br_get(&g->br, 6);
238 po_u64 m;
239 464 ▶ if (len == 0) len = 64; /* the 64 encoding, see above */
Branch: 1 branch
BranchTrueFalseTotal
if (len == 0) len = 64; /* the 64 encoding, see above */ 2 462 464
240 464 ▶ if (lead + len > 64) { g->br.err = 1; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (lead + len > 64) { g->br.err = 1; return 0; } 0 464 464
241 464 m = po_br_get(&g->br, len);
242 464 g->v_prev ^= m << (64 - lead - len);
243 464 g->lead_prev = lead;
244 464 g->len_prev = len;
245 }
246 }
247 104960 ▶ if (g->br.err) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (g->br.err) return 0; 0 104960 104960
248 104960 *t = g->t_prev; *bits = g->v_prev;
249 104960 g->i++;
250 104960 return 1;
251 }
252  
253 /* Bit patterns in and out, so a caller that has a double converts explicitly
254 * and a caller that has an integer does not convert at all. */
255 105495 static po_u64 po_d2b(double d) { po_u64 b; memcpy(&b, &d, 8); return b; }
256 67 static double po_b2d(po_u64 b) { double d; memcpy(&d, &b, 8); return d; }
257  
258 #endif /* PO_GORILLA_H */
« include/punk_observe/po_tsidx.h ↑ Summary include/punk_observe/po_lex.h »