include/otel_expo.h

filter: Statementstmt 89.3% 117 / 131 Branchbran 73.2% 82 / 112 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 81.8% 199 / 243 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/otel_grpc.h ↑ Summary include/otel_baggage.h »
1 /* otel_expo.h - the Base2 exponential bucket histogram.
2 *
3 * The intricate one, and the only place in this dist where being slightly
4 * wrong produces a plausible-looking number rather than an obvious failure.
5 *
6 * THE IDEA. Bucket boundaries are powers of a base derived from a `scale`:
7 *
8 * base = 2 ** (2 ** -scale)
9 *
10 * so a value lands in bucket index ceil(log_base(value)). Higher scale means
11 * finer buckets. Because the boundaries are relative rather than absolute,
12 * one configuration covers nanoseconds and hours at the same relative
13 * accuracy - which is the entire reason to prefer this over fixed buckets
14 * somebody has to guess in advance.
15 *
16 * TWO MAPPINGS, and both are needed.
17 *
18 * scale <= 0: the bucket is decided by the EXPONENT alone, so the mapping
19 * is a shift of the IEEE-754 exponent field. No logarithm, no
20 * floating point error, and fast - which matters, because this
21 * runs per measurement.
22 * scale > 0: a logarithm is unavoidable.
23 *
24 * AUTO-SCALING. When the populated range outgrows max_size (160 by default)
25 * the scale is REDUCED and adjacent buckets merged pairwise. That merge must
26 * be exact: a downscale that loses a count is a silently wrong percentile,
27 * which is the worst kind of wrong a histogram can be - it looks like data.
28 *
29 * ZERO, SUBNORMALS, NaN, INFINITY. Zero has its own count (it has no
30 * logarithm). NaN is dropped: it is not a measurement. Infinity is dropped
31 * for the same reason. Negative values go in the negative range, which exists
32 * for instruments that can legitimately record them.
33 */
34  
35 #ifndef OTEL_EXPO_H
36 #define OTEL_EXPO_H
37  
38 #include <math.h>
39  
40 #define OTEL_EXPO_MAX_SIZE 160
41 #define OTEL_EXPO_MAX_SCALE 20
42 #define OTEL_EXPO_MIN_SCALE -10
43  
44 /* One side (positive or negative) of the histogram: a dense window of bucket
45 * counts, with `offset` naming the index of the first. */
46 typedef struct {
47 int offset;
48 int len; /* populated width */
49 IV counts[OTEL_EXPO_MAX_SIZE];
50 } otel_expo_side;
51  
52 typedef struct {
53 int scale;
54 IV count; /* every recorded value, including zeros */
55 double sum, min, max;
56 IV zero_count;
57 double zero_threshold;
58 otel_expo_side pos, neg;
59 } otel_expo;
60  
61 4078 static void otel_expo_init(otel_expo *h, int scale) {
62 4078 Zero(h, 1, otel_expo);
63 4078 h->scale = scale;
64 4078 h->min = 1.0 / 0.0; /* +inf, so the first value wins */
65 4078 h->max = -1.0 / 0.0;
66 4078 h->pos.offset = h->neg.offset = 0;
67 4078 }
68  
69 /* The bucket index for a positive value at a given scale.
70 *
71 * For scale <= 0 this is exponent arithmetic: frexp gives the base-2 exponent
72 * directly, and the bucket is that exponent shifted right by -scale. No
73 * logarithm is involved, which is both faster and free of the rounding that
74 * makes a value near a boundary land in the wrong bucket.
75 *
76 * For scale > 0 a logarithm is unavoidable. */
77 4768 static int otel_expo_index(double v, int scale) {
78 4768 ▶ if (scale <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scale <= 0) { 0 4768 4768
79 int exp2v;
80 0 double frac = frexp(v, &exp2v);
81 /* frexp returns [0.5,1), so a value that IS a power of two reports
82 * one exponent too high; the boundary is inclusive at the top, so
83 * step it back down */
84 0 ▶ if (frac == 0.5) exp2v--;
Branch: 1 branch
BranchTrueFalseTotal
if (frac == 0.5) exp2v--; 0 0 0
85 0 return (exp2v - 1) >> (-scale);
86 }
87 {
88 4768 double scale_factor = ldexp(1.0 / log(2.0), scale);
89 4768 return (int)ceil(log(v) * scale_factor) - 1;
90 }
91 }
92  
93 /* Halve the resolution of one side: bucket i and i+1 become one.
94 *
95 * The pairing is over the INDEX SPACE, not the array, which is why the new
96 * offset is the old offset arithmetically shifted rather than divided - an
97 * offset can be negative, and C division truncates toward zero while the
98 * bucket mapping floors. Getting that wrong shifts every bucket by one at
99 * negative offsets, which silently reports the wrong percentile. */
100 100 static void otel_expo_downscale_side(otel_expo_side *s, int by) {
101 IV merged[OTEL_EXPO_MAX_SIZE];
102 int i, new_off, new_len;
103 100 ▶ if (s->len <= 0 || by <= 0) {
Branch: 2 branches
BranchTrueFalseTotal
if (s->len <= 0 || by <= 0) { 50 50 100
if (s->len <= 0 || by <= 0) { 0 50 50
104 50 ▶ if (s->len <= 0) s->offset >>= by;
Branch: 1 branch
BranchTrueFalseTotal
if (s->len <= 0) s->offset >>= by; 50 0 50
105 50 return;
106 }
107 50 new_off = s->offset >> by; /* arithmetic shift */
108 50 Zero(merged, OTEL_EXPO_MAX_SIZE, IV);
109 50 new_len = 0;
110 4488 ▶ for (i = 0; i < s->len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->len; i++) { 4438 50 4488
111 4438 int idx = (s->offset + i) >> by;
112 4438 int slot = idx - new_off;
113 4438 ▶ if (slot < 0 || slot >= OTEL_EXPO_MAX_SIZE) continue; /* unreachable */
Branch: 2 branches
BranchTrueFalseTotal
if (slot < 0 || slot >= OTEL_EXPO_MAX_SIZE) continue; /* unreachable */ 4438 0 4438
if (slot < 0 || slot >= OTEL_EXPO_MAX_SIZE) continue; /* unreachable */ 0 4438 4438
114 4438 merged[slot] += s->counts[i];
115 4438 ▶ if (slot + 1 > new_len) new_len = slot + 1;
Branch: 1 branch
BranchTrueFalseTotal
if (slot + 1 > new_len) new_len = slot + 1; 1938 2500 4438
116 }
117 50 Copy(merged, s->counts, OTEL_EXPO_MAX_SIZE, IV);
118 50 s->offset = new_off;
119 50 s->len = new_len;
120 }
121  
122 50 static void otel_expo_downscale(otel_expo *h, int by) {
123 50 ▶ if (by <= 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (by <= 0) return; 0 50 50
124 50 otel_expo_downscale_side(&h->pos, by);
125 50 otel_expo_downscale_side(&h->neg, by);
126 50 h->scale -= by;
127 }
128  
129 /* How much to downscale so that `idx` fits alongside what is already there. */
130 4724 static int otel_expo_needed(const otel_expo_side *s, int idx) {
131 4724 int lo, hi, by = 0;
132 4724 ▶ if (s->len <= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (s->len <= 0) return 0; 22 4702 4724
133 4702 lo = s->offset;
134 4702 hi = s->offset + s->len - 1;
135 4702 ▶ if (idx < lo) lo = idx;
Branch: 1 branch
BranchTrueFalseTotal
if (idx < lo) lo = idx; 50 4652 4702
136 4702 ▶ if (idx > hi) hi = idx;
Branch: 1 branch
BranchTrueFalseTotal
if (idx > hi) hi = idx; 434 4268 4702
137 4938 ▶ while ((hi - lo + 1) > OTEL_EXPO_MAX_SIZE) {
Branch: 1 branch
BranchTrueFalseTotal
while ((hi - lo + 1) > OTEL_EXPO_MAX_SIZE) { 236 4702 4938
138 236 lo >>= 1;
139 236 hi >>= 1;
140 236 by++;
141 }
142 4702 return by;
143 }
144  
145 4780 static void otel_expo_side_add(otel_expo_side *s, int idx, IV n) {
146 int i;
147 4780 ▶ if (s->len <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (s->len <= 0) { 22 4758 4780
148 22 s->offset = idx;
149 22 s->len = 1;
150 22 Zero(s->counts, OTEL_EXPO_MAX_SIZE, IV);
151 22 s->counts[0] = n;
152 22 return;
153 }
154 4758 ▶ if (idx < s->offset) {
Branch: 1 branch
BranchTrueFalseTotal
if (idx < s->offset) { 50 4708 4758
155 50 int shift = s->offset - idx;
156 50 ▶ if (s->len + shift > OTEL_EXPO_MAX_SIZE) return; /* caller rescaled */
Branch: 1 branch
BranchTrueFalseTotal
if (s->len + shift > OTEL_EXPO_MAX_SIZE) return; /* caller rescaled */ 0 50 50
157 3932 ▶ for (i = s->len - 1; i >= 0; i--) s->counts[i + shift] = s->counts[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = s->len - 1; i >= 0; i--) s->counts[i + shift] = s->counts[i]; 3882 50 3932
158 1696 ▶ for (i = 0; i < shift; i++) s->counts[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < shift; i++) s->counts[i] = 0; 1646 50 1696
159 50 s->offset = idx;
160 50 s->len += shift;
161 }
162 4708 ▶ else if (idx >= s->offset + s->len) {
Branch: 1 branch
BranchTrueFalseTotal
else if (idx >= s->offset + s->len) { 488 4220 4708
163 488 int want = idx - s->offset + 1;
164 488 ▶ if (want > OTEL_EXPO_MAX_SIZE) return;
Branch: 1 branch
BranchTrueFalseTotal
if (want > OTEL_EXPO_MAX_SIZE) return; 0 488 488
165 3052 ▶ for (i = s->len; i < want; i++) s->counts[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = s->len; i < want; i++) s->counts[i] = 0; 2564 488 3052
166 488 s->len = want;
167 }
168 4758 s->counts[idx - s->offset] += n;
169 }
170  
171 /* Record one value. */
172 4732 static void otel_expo_record(otel_expo *h, double v) {
173 otel_expo_side *side;
174 double av;
175 int idx, by;
176  
177 4732 ▶ if (v != v) return; /* NaN is not a measurement */
Branch: 1 branch
BranchTrueFalseTotal
if (v != v) return; /* NaN is not a measurement */ 2 4730 4732
178 4730 ▶ if (v == 1.0 / 0.0 || v == -1.0 / 0.0) return; /* nor is infinity */
Branch: 2 branches
BranchTrueFalseTotal
if (v == 1.0 / 0.0 || v == -1.0 / 0.0) return; /* nor is infinity */ 4728 2 4730
if (v == 1.0 / 0.0 || v == -1.0 / 0.0) return; /* nor is infinity */ 2 4726 4728
179  
180 4726 h->count++;
181 4726 h->sum += v;
182 4726 ▶ if (v < h->min) h->min = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < h->min) h->min = v; 78 4648 4726
183 4726 ▶ if (v > h->max) h->max = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v > h->max) h->max = v; 776 3950 4726
184  
185 4726 ▶ av = v < 0 ? -v : v;
Branch: 1 branch
BranchTrueFalseTotal
av = v < 0 ? -v : v; 2 4724 4726
186 4726 ▶ if (av <= h->zero_threshold || av == 0.0) { h->zero_count++; return; }
Branch: 2 branches
BranchTrueFalseTotal
if (av <= h->zero_threshold || av == 0.0) { h->zero_count++; return; } 4724 2 4726
if (av <= h->zero_threshold || av == 0.0) { h->zero_count++; return; } 0 4724 4724
187  
188 4724 ▶ side = v < 0 ? &h->neg : &h->pos;
Branch: 1 branch
BranchTrueFalseTotal
side = v < 0 ? &h->neg : &h->pos; 2 4722 4724
189 4724 idx = otel_expo_index(av, h->scale);
190 4724 by = otel_expo_needed(side, idx);
191 4724 ▶ if (by > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (by > 0) { 44 4680 4724
192 44 otel_expo_downscale(h, by);
193 44 idx = otel_expo_index(av, h->scale);
194 }
195 4724 otel_expo_side_add(side, idx, 1);
196 }
197  
198 /* Merge `src` into `dst`, downscaling the finer one first.
199 *
200 * This is where delta-to-cumulative conversion lives, and it is the operation
201 * most likely to lose a count if the two scales are handled carelessly. */
202 2 static void otel_expo_merge(otel_expo *dst, const otel_expo *src) {
203 otel_expo tmp;
204 2 const otel_expo *s = src;
205 int i;
206 2 ▶ if (src->count == 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (src->count == 0) return; 0 2 2
207 2 ▶ if (dst->count == 0 && dst->pos.len == 0 && dst->neg.len == 0) {
Branch: 3 branches
BranchTrueFalseTotal
if (dst->count == 0 && dst->pos.len == 0 && dst->neg.len == 0) { 0 2 2
if (dst->count == 0 && dst->pos.len == 0 && dst->neg.len == 0) { 0 0 0
if (dst->count == 0 && dst->pos.len == 0 && dst->neg.len == 0) { 0 0 0
208 0 int keep_thresh = 0;
209 0 double th = dst->zero_threshold;
210 0 *dst = *src;
211 0 ▶ if (keep_thresh) dst->zero_threshold = th;
Branch: 1 branch
BranchTrueFalseTotal
if (keep_thresh) dst->zero_threshold = th; 0 0 0
212 0 return;
213 }
214 2 ▶ if (src->scale > dst->scale) { /* src is finer: coarsen a copy */
Branch: 1 branch
BranchTrueFalseTotal
if (src->scale > dst->scale) { /* src is finer: coarsen a copy */ 0 2 2
215 0 tmp = *src;
216 0 otel_expo_downscale(&tmp, src->scale - dst->scale);
217 0 s = &tmp;
218 }
219 2 ▶ else if (dst->scale > src->scale) {
Branch: 1 branch
BranchTrueFalseTotal
else if (dst->scale > src->scale) { 0 2 2
220 0 otel_expo_downscale(dst, dst->scale - src->scale);
221 }
222  
223 /* Aligning the scales is not enough. The COMBINED index range may be far
224 * wider than either input - two histograms of similar shape but different
225 * magnitude are exactly the interesting case - and otel_expo_side_add
226 * refuses to widen a window past max_size. Without this both would then
227 * drop buckets silently, which is the specific failure this whole file
228 * exists to avoid. So: work out what the union needs, and coarsen BOTH to
229 * it before adding a single count. */
230 {
231 2 int by = 0, k;
232 6 ▶ for (k = 0; k < 2; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 2; k++) { 4 2 6
233 4 ▶ const otel_expo_side *ss = k ? &s->neg : &s->pos;
Branch: 1 branch
BranchTrueFalseTotal
const otel_expo_side *ss = k ? &s->neg : &s->pos; 2 2 4
234 4 ▶ otel_expo_side *ds = k ? &dst->neg : &dst->pos;
Branch: 1 branch
BranchTrueFalseTotal
otel_expo_side *ds = k ? &dst->neg : &dst->pos; 2 2 4
235 4 int lo, hi, need = 0;
236 4 ▶ if (ss->len <= 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (ss->len <= 0) continue; 2 2 4
237 2 ▶ if (ds->len <= 0) { lo = ss->offset; hi = ss->offset + ss->len - 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (ds->len <= 0) { lo = ss->offset; hi = ss->offset + ss->len - 1; } 0 2 2
238 else {
239 2 lo = ds->offset < ss->offset ? ds->offset : ss->offset;
240 2 hi = (ds->offset + ds->len - 1) > (ss->offset + ss->len - 1)
241 ? (ds->offset + ds->len - 1) : (ss->offset + ss->len - 1);
242 }
243 4 ▶ while ((hi - lo + 1) > OTEL_EXPO_MAX_SIZE) { lo >>= 1; hi >>= 1; need++; }
Branch: 1 branch
BranchTrueFalseTotal
while ((hi - lo + 1) > OTEL_EXPO_MAX_SIZE) { lo >>= 1; hi >>= 1; need++; } 2 2 4
244 2 ▶ if (need > by) by = need;
Branch: 1 branch
BranchTrueFalseTotal
if (need > by) by = need; 2 0 2
245 }
246 2 ▶ if (by > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (by > 0) { 2 0 2
247 2 ▶ if (s == &tmp) otel_expo_downscale(&tmp, by);
Branch: 1 branch
BranchTrueFalseTotal
if (s == &tmp) otel_expo_downscale(&tmp, by); 0 2 2
248 2 else { tmp = *src;
249 2 otel_expo_downscale(&tmp, (src->scale - dst->scale) + by);
250 2 s = &tmp; }
251 2 otel_expo_downscale(dst, by);
252 }
253 }
254 2 dst->count += s->count;
255 2 dst->sum += s->sum;
256 2 dst->zero_count += s->zero_count;
257 2 ▶ if (s->min < dst->min) dst->min = s->min;
Branch: 1 branch
BranchTrueFalseTotal
if (s->min < dst->min) dst->min = s->min; 0 2 2
258 2 ▶ if (s->max > dst->max) dst->max = s->max;
Branch: 1 branch
BranchTrueFalseTotal
if (s->max > dst->max) dst->max = s->max; 2 0 2
259 94 ▶ for (i = 0; i < s->pos.len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->pos.len; i++) 92 2 94
260 92 ▶ if (s->pos.counts[i])
Branch: 1 branch
BranchTrueFalseTotal
if (s->pos.counts[i]) 56 36 92
261 56 otel_expo_side_add(&dst->pos, s->pos.offset + i, s->pos.counts[i]);
262 2 ▶ for (i = 0; i < s->neg.len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->neg.len; i++) 0 2 2
263 0 ▶ if (s->neg.counts[i])
Branch: 1 branch
BranchTrueFalseTotal
if (s->neg.counts[i]) 0 0 0
264 0 otel_expo_side_add(&dst->neg, s->neg.offset + i, s->neg.counts[i]);
265 }
266  
267 /* The total of every bucket plus the zeros, for the invariant the tests
268 * assert: a downscale or a merge must never change it. */
269 30 static IV otel_expo_total(const otel_expo *h) {
270 30 IV n = h->zero_count;
271 int i;
272 2088 ▶ for (i = 0; i < h->pos.len; i++) n += h->pos.counts[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->pos.len; i++) n += h->pos.counts[i]; 2058 30 2088
273 32 ▶ for (i = 0; i < h->neg.len; i++) n += h->neg.counts[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->neg.len; i++) n += h->neg.counts[i]; 2 30 32
274 30 return n;
275 }
276  
277 #endif /* OTEL_EXPO_H */
« include/otel_grpc.h ↑ Summary include/otel_baggage.h »