include/sa/sa_hist.h

filter: Statementstmt 90.9% 101 / 111 Branchbran 57.6% 53 / 92 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 75.8% 154 / 203 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_hll.h ↑ Summary include/sa/sa_rate.h »
1 #ifndef SA_HIST_H
2 #define SA_HIST_H
3  
4 /* sa_hist.h - a distribution every process adds to at once. Perl-free.
5 *
6 * Recording a value is one atomic add to one bucket. There is no merge step and
7 * no per-process copy: a hundred workers and one worker write the same array,
8 * so a percentile over the whole pool is the same question as a percentile over
9 * one of them.
10 *
11 * ---- why not just keep the values ------------------------------------------
12 *
13 * Because a distribution is wanted continuously and the values are not. Keeping
14 * them means memory proportional to traffic and a sort to answer anything;
15 * bucketing means fixed memory and an answer that is already there. What it
16 * costs is exactness, and the point of the scheme below is that the inexactness
17 * is bounded and known rather than whatever the buckets happened to be.
18 *
19 * ---- log-linear buckets ----------------------------------------------------
20 *
21 * Plain powers of two would put 512 and 1000 in one bucket, which is useless
22 * for latency: those are different answers. Plain linear buckets fine enough
23 * for a microsecond would need millions of them to reach a minute.
24 *
25 * So each power of two is divided into 2^sigbits linear sub-buckets, which is
26 * the scheme HDR histograms use. The relative error of any recorded value is at
27 * most 1/2^sigbits - about 6% at the default of four significant bits, about
28 * 1.5% at six - and it is the SAME at a microsecond and at an hour. Bucket
29 * count grows with the logarithm of the range, so a histogram covering one to
30 * a billion at 6% costs a few hundred buckets.
31 *
32 * Values below 2^sigbits are recorded exactly, because at that size the
33 * sub-bucket is one unit wide.
34 *
35 * ---- what a reader gets ----------------------------------------------------
36 *
37 * A quantile is read while values are still arriving, and no attempt is made to
38 * stop that: the answer describes the histogram as it was walked, which for a
39 * distribution is the honest thing and for anything else would not be. Count
40 * and sum are read the same way, so a mean computed from them can disagree with
41 * the buckets by whatever arrived in between.
42 *
43 * A quantile is reported as the TOP of the bucket it falls in. For a latency
44 * budget that is the useful direction to be wrong in: it never claims the
45 * service was faster than it was.
46 *
47 * Needs sa_arena.h.
48 */
49  
50 #include "sa/sa_arena.h"
51  
52 #define SA_HIST_MAGIC 0x54534948u /* 'H','I','S','T' little-endian */
53  
54 #define SA_HIST_MIN_SIG 1
55 #define SA_HIST_MAX_SIG 8
56  
57 typedef struct {
58 volatile uint32_t magic; /* published LAST at init */
59 uint32_t sigbits;
60 uint64_t max_value;
61 uint64_t nbuckets;
62 uint64_t buckets_off;/* from the HISTOGRAM's base */
63 volatile uint64_t count;
64 volatile uint64_t sum;
65 volatile uint64_t min; /* CAS-updated; UINT64_MAX when empty */
66 volatile uint64_t max;
67 volatile uint64_t over; /* values above max_value, counted apart */
68 volatile unsigned char locks[SA_LOCK_STRIPES];
69 } sa_hist_hdr;
70  
71 #ifndef SA_HIST_FWD
72 #define SA_HIST_FWD
73 typedef struct sa_hist sa_hist;
74 #endif
75 struct sa_hist {
76 sa_region *arena;
77 sa_hist_hdr *hdr;
78 volatile uint64_t *buckets;
79 uint64_t nbuckets;
80 uint32_t sigbits;
81 uint64_t max_value;
82 };
83  
84 /* The position of the highest set bit. Written out rather than
85 * __builtin_clzll, which is not everywhere this claims to build. */
86 3223 static uint32_t sa_hist_msb(uint64_t v) {
87 3223 uint32_t n = 0;
88 3223 ▶ if (v >> 32) { v >>= 32; n += 32; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 32) { v >>= 32; n += 32; } 0 3223 3223
89 3223 ▶ if (v >> 16) { v >>= 16; n += 16; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 16) { v >>= 16; n += 16; } 205 3018 3223
90 3223 ▶ if (v >> 8) { v >>= 8; n += 8; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 8) { v >>= 8; n += 8; } 2010 1213 3223
91 3223 ▶ if (v >> 4) { v >>= 4; n += 4; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 4) { v >>= 4; n += 4; } 1022 2201 3223
92 3223 ▶ if (v >> 2) { v >>= 2; n += 2; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 2) { v >>= 2; n += 2; } 870 2353 3223
93 3223 ▶ if (v >> 1) { n += 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (v >> 1) { n += 1; } 1693 1530 3223
94 3223 return n;
95 }
96  
97 /* Which bucket a value belongs in.
98 *
99 * Below 2^sigbits the buckets are one unit wide, so the value IS the index and
100 * small values are exact. Above it, the index is the power of two and then the
101 * top `sigbits` bits of what is left, which is what makes the relative error
102 * constant across the whole range. */
103 3390 static uint64_t sa_hist_index(uint64_t v, uint32_t sigbits) {
104 3390 uint64_t sub = 1ULL << sigbits;
105 uint32_t msb, shift;
106  
107 3390 ▶ if (v < sub) return v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < sub) return v; 167 3223 3390
108 3223 msb = sa_hist_msb(v);
109 3223 shift = msb - sigbits;
110 3223 return (((uint64_t)shift + 1) << sigbits) + ((v >> shift) & (sub - 1));
111 }
112  
113 /* The lowest value that lands in this bucket. */
114 21 static uint64_t sa_hist_low(uint64_t idx, uint32_t sigbits) {
115 21 uint64_t sub = 1ULL << sigbits;
116 uint64_t shift;
117 21 ▶ if (idx < sub) return idx;
Branch: 1 branch
BranchTrueFalseTotal
if (idx < sub) return idx; 1 20 21
118 20 shift = (idx >> sigbits) - 1;
119 20 return ((idx & (sub - 1)) | sub) << shift;
120 }
121  
122 /* And the highest. A quantile answers with this, so it is never optimistic. */
123 55 static uint64_t sa_hist_high(uint64_t idx, uint32_t sigbits) {
124 55 uint64_t sub = 1ULL << sigbits;
125 uint64_t shift;
126 55 ▶ if (idx < sub) return idx;
Branch: 1 branch
BranchTrueFalseTotal
if (idx < sub) return idx; 37 18 55
127 18 shift = (idx >> sigbits) - 1;
128 18 return sa_hist_low(idx, sigbits) + (1ULL << shift) - 1;
129 }
130  
131 216 static uint64_t sa_hist_buckets_for(uint64_t max_value, uint32_t sigbits) {
132 216 return sa_hist_index(max_value, sigbits) + 1;
133 }
134  
135 162 static uint64_t sa_hist_bytes(uint64_t max_value, uint32_t sigbits) {
136 162 return sa_align_up((uint64_t)sizeof(sa_hist_hdr))
137 162 + sa_hist_buckets_for(max_value, sigbits) * 8u;
138 }
139  
140 54 static sa_hist *sa_hist_bind(sa_region *arena, sa_reg *e,
141 uint64_t max_value, uint32_t sigbits, int *err)
142 {
143 #if !SA_HAVE_ATOMICS
144 (void)arena; (void)e; (void)max_value; (void)sigbits;
145 if (err) *err = SA_E_NOATOMICS;
146 return NULL;
147 #else
148 sa_hist *hs;
149 sa_hist_hdr *h;
150 uint64_t hash;
151  
152 54 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 54 0 54
153 54 ▶ if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 3 branches
BranchTrueFalseTotal
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 54 0 54
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 54 54
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
154  
155 54 h = (sa_hist_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_hist_hdr));
156 54 ▶ if (!h) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 54 54
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
157  
158 54 ▶ if (sa_at_load32_acq(&h->magic) != SA_HIST_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_HIST_MAGIC) { 54 0 54
159 54 hash = sa_at_fnv(e->name, strlen(e->name));
160 54 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 54 0 54
161 54 ▶ if (sa_at_load32_acq(&h->magic) != SA_HIST_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_HIST_MAGIC) { 54 0 54
162 54 ▶ if (!max_value || sigbits < SA_HIST_MIN_SIG
Branch: 2 branches
BranchTrueFalseTotal
if (!max_value || sigbits < SA_HIST_MIN_SIG 54 0 54
if (!max_value || sigbits < SA_HIST_MIN_SIG 54 0 54
163 54 ▶ || sigbits > SA_HIST_MAX_SIG
Branch: 1 branch
BranchTrueFalseTotal
|| sigbits > SA_HIST_MAX_SIG 54 0 54
164 54 ▶ || sa_hist_bytes(max_value, sigbits) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_hist_bytes(max_value, sigbits) > e->len) { 0 54 54
165 0 sa_at_unlock(h->locks, hash);
166 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
167 0 return NULL;
168 }
169 54 memset((void *)h, 0,
170 54 (size_t)sa_hist_bytes(max_value, sigbits));
171 54 h->sigbits = sigbits;
172 54 h->max_value = max_value;
173 54 h->nbuckets = sa_hist_buckets_for(max_value, sigbits);
174 54 h->buckets_off = sa_align_up((uint64_t)sizeof(sa_hist_hdr));
175 /* Empty, so the smallest thing recorded wins outright. */
176 54 h->min = (uint64_t)-1;
177 54 sa_at_store64_rel(&h->min, (uint64_t)-1);
178 54 sa_at_store32_rel(&h->magic, SA_HIST_MAGIC);
179 }
180 54 sa_at_unlock(h->locks, hash);
181 }
182 54 ▶ if (!sa_wait_magic32(&h->magic, SA_HIST_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_HIST_MAGIC)) { 0 54 54
183 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
184 0 return NULL;
185 }
186 }
187  
188 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
189 *
190 * The branch above only checks a size when this process is the one doing
191 * the INITIALISING. A process that finds the magic already set reads the
192 * shape out of the shared header and believed it, so a header claiming
193 * four billion slots put every later read past the end of the mapping.
194 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
195  
196 54 ▶ if ((max_value && h->max_value != max_value)
Branch: 2 branches
BranchTrueFalseTotal
if ((max_value && h->max_value != max_value) 54 0 54
if ((max_value && h->max_value != max_value) 54 0 54
197 54 ▶ || (sigbits && h->sigbits != sigbits)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (sigbits && h->sigbits != sigbits)) { 54 0 54
|| (sigbits && h->sigbits != sigbits)) { 0 54 54
198 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
199 0 return NULL;
200 }
201  
202 54 hs = (sa_hist *)calloc(1, sizeof(sa_hist));
203 54 ▶ if (!hs) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!hs) { if (err) *err = SA_E_NOMEM; return NULL; } 0 54 54
if (!hs) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
204 54 hs->arena = arena;
205 54 hs->hdr = h;
206 54 hs->buckets = (volatile uint64_t *)((char *)h + (size_t)h->buckets_off);
207 54 hs->nbuckets = h->nbuckets;
208 54 hs->sigbits = h->sigbits;
209 54 hs->max_value = h->max_value;
210 54 return hs;
211 #endif
212 }
213  
214 54 static void sa_hist_free(sa_hist *h) { free(h); }
215  
216 /* Record a value `n` times.
217 *
218 * A value above the histogram's ceiling is counted in `over` and NOT clamped
219 * into the top bucket. Clamping would let a flood of enormous values masquerade
220 * as a busy top bucket, and the quantiles would look plausible while being
221 * wrong. Counted separately, an overflow is visible for what it is. */
222 3180 static void sa_hist_record(sa_hist *h, uint64_t v, uint64_t n) {
223 #if SA_HAVE_ATOMICS
224 3180 sa_hist_hdr *hd = h->hdr;
225  
226 3180 ▶ if (!n) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return; 0 3180 3180
227 3180 ▶ if (v > h->max_value) {
Branch: 1 branch
BranchTrueFalseTotal
if (v > h->max_value) { 6 3174 3180
228 6 sa_at_fetch_add64(&hd->over, n);
229 6 return;
230 }
231 3174 sa_at_fetch_add64(&h->buckets[sa_hist_index(v, h->sigbits)], n);
232 3174 sa_at_fetch_add64(&hd->count, n);
233 3174 sa_at_fetch_add64(&hd->sum, v * n);
234  
235 /* min and max are compare-and-swap loops rather than adds, and they are
236 * bounded by contention rather than spinning for ever: whoever loses the
237 * race re-reads and finds the value is no longer smaller. */
238 0 for (;;) {
239 3174 uint64_t cur = sa_at_load64_acq(&hd->min);
240 3174 ▶ if (v >= cur) break;
Branch: 1 branch
BranchTrueFalseTotal
if (v >= cur) break; 3122 52 3174
241 52 ▶ if (sa_at_cas64(&hd->min, cur, v)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(&hd->min, cur, v)) break; 52 0 52
242 }
243 0 for (;;) {
244 3174 uint64_t cur = sa_at_load64_acq(&hd->max);
245 3174 ▶ if (v <= cur) break;
Branch: 1 branch
BranchTrueFalseTotal
if (v <= cur) break; 526 2648 3174
246 2648 ▶ if (sa_at_cas64(&hd->max, cur, v)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas64(&hd->max, cur, v)) break; 2648 0 2648
247 }
248 #else
249 (void)h; (void)v; (void)n;
250 #endif
251 }
252  
253 /* The value at a quantile, as the TOP of the bucket it falls in.
254 *
255 * Walked while values are still arriving, which is deliberate: stopping the
256 * world to read a distribution would cost more than the answer is worth, and
257 * the answer is a description of a moving thing anyway. */
258 52 static uint64_t sa_hist_quantile(sa_hist *h, double q) {
259 #if SA_HAVE_ATOMICS
260 52 uint64_t total = sa_at_load64_acq(&h->hdr->count);
261 52 uint64_t want, seen = 0, i;
262  
263 52 ▶ if (!total) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!total) return 0; 0 52 52
264 52 ▶ if (q <= 0.0) return sa_at_load64_acq(&h->hdr->min);
Branch: 1 branch
BranchTrueFalseTotal
if (q <= 0.0) return sa_at_load64_acq(&h->hdr->min); 0 52 52
265 52 ▶ if (q >= 1.0) return sa_at_load64_acq(&h->hdr->max);
Branch: 1 branch
BranchTrueFalseTotal
if (q >= 1.0) return sa_at_load64_acq(&h->hdr->max); 0 52 52
266  
267 52 want = (uint64_t)((double)total * q + 0.5);
268 52 ▶ if (want < 1) want = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (want < 1) want = 1; 0 52 52
269  
270 3515 ▶ for (i = 0; i < h->nbuckets; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->nbuckets; i++) { 3515 0 3515
271 3515 seen += sa_at_load64_acq(&h->buckets[i]);
272 3515 ▶ if (seen >= want) return sa_hist_high(i, h->sigbits);
Branch: 1 branch
BranchTrueFalseTotal
if (seen >= want) return sa_hist_high(i, h->sigbits); 52 3463 3515
273 }
274 0 return sa_at_load64_acq(&h->hdr->max);
275 #else
276 (void)h; (void)q;
277 return 0;
278 #endif
279 }
280  
281 2 static void sa_hist_reset(sa_hist *h) {
282 #if SA_HAVE_ATOMICS
283 2 uint64_t hash = (uint64_t)(uintptr_t)h->hdr;
284 uint64_t i;
285 2 ▶ if (!sa_at_lock(h->hdr->locks, hash)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(h->hdr->locks, hash)) return; 0 2 2
286 383 ▶ for (i = 0; i < h->nbuckets; i++) sa_at_store64_rel(&h->buckets[i], 0);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->nbuckets; i++) sa_at_store64_rel(&h->buckets[i], 0); 381 2 383
287 2 sa_at_store64_rel(&h->hdr->count, 0);
288 2 sa_at_store64_rel(&h->hdr->sum, 0);
289 2 sa_at_store64_rel(&h->hdr->over, 0);
290 2 sa_at_store64_rel(&h->hdr->max, 0);
291 2 sa_at_store64_rel(&h->hdr->min, (uint64_t)-1);
292 2 sa_at_unlock(h->hdr->locks, hash);
293 #else
294 (void)h;
295 #endif
296 }
297  
298 #endif /* SA_HIST_H */
« include/sa/sa_hll.h ↑ Summary include/sa/sa_rate.h »