1 | /** |
2 | * hdr_histogram.h |
3 | * Written by Michael Barker and released to the public domain, |
4 | * as explained at http://creativecommons.org/publicdomain/zero/1.0/ |
5 | * |
6 | * The source for the hdr_histogram utilises a few C99 constructs, specifically |
7 | * the use of stdint/stdbool and inline variable declaration. |
8 | */ |
9 | |
10 | #ifndef HDR_HISTOGRAM_H |
11 | #define HDR_HISTOGRAM_H 1 |
12 | |
13 | #include <stdint.h> |
14 | #include <stdbool.h> |
15 | #include <stdio.h> |
16 | |
17 | struct hdr_histogram |
18 | { |
19 | int64_t lowest_discernible_value; |
20 | int64_t highest_trackable_value; |
21 | int32_t unit_magnitude; |
22 | int32_t significant_figures; |
23 | int32_t sub_bucket_half_count_magnitude; |
24 | int32_t sub_bucket_half_count; |
25 | int64_t sub_bucket_mask; |
26 | int32_t sub_bucket_count; |
27 | int32_t bucket_count; |
28 | int64_t min_value; |
29 | int64_t max_value; |
30 | int32_t normalizing_index_offset; |
31 | double conversion_ratio; |
32 | int32_t counts_len; |
33 | int64_t total_count; |
34 | int64_t* counts; |
35 | }; |
36 | |
37 | #ifdef __cplusplus |
38 | extern "C" { |
39 | #endif |
40 | |
41 | /** |
42 | * Allocate the memory and initialise the hdr_histogram. |
43 | * |
44 | * Due to the size of the histogram being the result of some reasonably |
45 | * involved math on the input parameters this function it is tricky to stack allocate. |
46 | * The histogram should be released with hdr_close |
47 | * |
48 | * @param lowest_discernible_value The smallest possible value that is distinguishable from 0. |
49 | * Must be a positive integer that is >= 1. May be internally rounded down to nearest power of 2. |
50 | * @param highest_trackable_value The largest possible value to be put into the |
51 | * histogram. |
52 | * @param significant_figures The level of precision for this histogram, i.e. the number |
53 | * of figures in a decimal number that will be maintained. E.g. a value of 3 will mean |
54 | * the results from the histogram will be accurate up to the first three digits. Must |
55 | * be a value between 1 and 5 (inclusive). |
56 | * @param result Output parameter to capture allocated histogram. |
57 | * @return 0 on success, EINVAL if lowest_discernible_value is < 1 or the |
58 | * significant_figure value is outside of the allowed range, ENOMEM if malloc |
59 | * failed. |
60 | */ |
61 | int hdr_init( |
62 | int64_t lowest_discernible_value, |
63 | int64_t highest_trackable_value, |
64 | int significant_figures, |
65 | struct hdr_histogram** result); |
66 | |
67 | /** |
68 | * Free the memory and close the hdr_histogram. |
69 | * |
70 | * @param h The histogram you want to close. |
71 | */ |
72 | void hdr_close(struct hdr_histogram* h); |
73 | |
74 | /** |
75 | * Allocate the memory and initialise the hdr_histogram. This is the equivalent of calling |
76 | * hdr_init(1, highest_trackable_value, significant_figures, result); |
77 | * |
78 | * @deprecated use hdr_init. |
79 | */ |
80 | int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result); |
81 | |
82 | |
83 | /** |
84 | * Reset a histogram to zero - empty out a histogram and re-initialise it |
85 | * |
86 | * If you want to re-use an existing histogram, but reset everything back to zero, this |
87 | * is the routine to use. |
88 | * |
89 | * @param h The histogram you want to reset to empty. |
90 | * |
91 | */ |
92 | void hdr_reset(struct hdr_histogram* h); |
93 | |
94 | /** |
95 | * Get the memory size of the hdr_histogram. |
96 | * |
97 | * @param h "This" pointer |
98 | * @return The amount of memory used by the hdr_histogram in bytes |
99 | */ |
100 | size_t hdr_get_memory_size(struct hdr_histogram* h); |
101 | |
102 | /** |
103 | * Records a value in the histogram, will round this value of to a precision at or better |
104 | * than the significant_figure specified at construction time. |
105 | * |
106 | * @param h "This" pointer |
107 | * @param value Value to add to the histogram |
108 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
109 | * true otherwise. |
110 | */ |
111 | bool hdr_record_value(struct hdr_histogram* h, int64_t value); |
112 | |
113 | /** |
114 | * Records a value in the histogram, will round this value of to a precision at or better |
115 | * than the significant_figure specified at construction time. |
116 | * |
117 | * Will record this value atomically, however the whole structure may appear inconsistent |
118 | * when read concurrently with this update. Do NOT mix calls to this method with calls |
119 | * to non-atomic updates. |
120 | * |
121 | * @param h "This" pointer |
122 | * @param value Value to add to the histogram |
123 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
124 | * true otherwise. |
125 | */ |
126 | bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value); |
127 | |
128 | /** |
129 | * Records count values in the histogram, will round this value of to a |
130 | * precision at or better than the significant_figure specified at construction |
131 | * time. |
132 | * |
133 | * @param h "This" pointer |
134 | * @param value Value to add to the histogram |
135 | * @param count Number of 'value's to add to the histogram |
136 | * @return false if any value is larger than the highest_trackable_value and can't be recorded, |
137 | * true otherwise. |
138 | */ |
139 | bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count); |
140 | |
141 | /** |
142 | * Records count values in the histogram, will round this value of to a |
143 | * precision at or better than the significant_figure specified at construction |
144 | * time. |
145 | * |
146 | * Will record this value atomically, however the whole structure may appear inconsistent |
147 | * when read concurrently with this update. Do NOT mix calls to this method with calls |
148 | * to non-atomic updates. |
149 | * |
150 | * @param h "This" pointer |
151 | * @param value Value to add to the histogram |
152 | * @param count Number of 'value's to add to the histogram |
153 | * @return false if any value is larger than the highest_trackable_value and can't be recorded, |
154 | * true otherwise. |
155 | */ |
156 | bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count); |
157 | |
158 | /** |
159 | * Record a value in the histogram and backfill based on an expected interval. |
160 | * |
161 | * Records a value in the histogram, will round this value of to a precision at or better |
162 | * than the significant_figure specified at construction time. This is specifically used |
163 | * for recording latency. If the value is larger than the expected_interval then the |
164 | * latency recording system has experienced co-ordinated omission. This method fills in the |
165 | * values that would have occurred had the client providing the load not been blocked. |
166 | |
167 | * @param h "This" pointer |
168 | * @param value Value to add to the histogram |
169 | * @param expected_interval The delay between recording values. |
170 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
171 | * true otherwise. |
172 | */ |
173 | bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval); |
174 | |
175 | /** |
176 | * Record a value in the histogram and backfill based on an expected interval. |
177 | * |
178 | * Records a value in the histogram, will round this value of to a precision at or better |
179 | * than the significant_figure specified at construction time. This is specifically used |
180 | * for recording latency. If the value is larger than the expected_interval then the |
181 | * latency recording system has experienced co-ordinated omission. This method fills in the |
182 | * values that would have occurred had the client providing the load not been blocked. |
183 | * |
184 | * Will record this value atomically, however the whole structure may appear inconsistent |
185 | * when read concurrently with this update. Do NOT mix calls to this method with calls |
186 | * to non-atomic updates. |
187 | * |
188 | * @param h "This" pointer |
189 | * @param value Value to add to the histogram |
190 | * @param expected_interval The delay between recording values. |
191 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
192 | * true otherwise. |
193 | */ |
194 | bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval); |
195 | |
196 | /** |
197 | * Record a value in the histogram 'count' times. Applies the same correcting logic |
198 | * as 'hdr_record_corrected_value'. |
199 | * |
200 | * @param h "This" pointer |
201 | * @param value Value to add to the histogram |
202 | * @param count Number of 'value's to add to the histogram |
203 | * @param expected_interval The delay between recording values. |
204 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
205 | * true otherwise. |
206 | */ |
207 | bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval); |
208 | |
209 | /** |
210 | * Record a value in the histogram 'count' times. Applies the same correcting logic |
211 | * as 'hdr_record_corrected_value'. |
212 | * |
213 | * Will record this value atomically, however the whole structure may appear inconsistent |
214 | * when read concurrently with this update. Do NOT mix calls to this method with calls |
215 | * to non-atomic updates. |
216 | * |
217 | * @param h "This" pointer |
218 | * @param value Value to add to the histogram |
219 | * @param count Number of 'value's to add to the histogram |
220 | * @param expected_interval The delay between recording values. |
221 | * @return false if the value is larger than the highest_trackable_value and can't be recorded, |
222 | * true otherwise. |
223 | */ |
224 | bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval); |
225 | |
226 | /** |
227 | * Adds all of the values from 'from' to 'this' histogram. Will return the |
228 | * number of values that are dropped when copying. Values will be dropped |
229 | * if they around outside of h.lowest_discernible_value and |
230 | * h.highest_trackable_value. |
231 | * |
232 | * @param h "This" pointer |
233 | * @param from Histogram to copy values from. |
234 | * @return The number of values dropped when copying. |
235 | */ |
236 | int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from); |
237 | |
238 | /** |
239 | * Adds all of the values from 'from' to 'this' histogram. Will return the |
240 | * number of values that are dropped when copying. Values will be dropped |
241 | * if they around outside of h.lowest_discernible_value and |
242 | * h.highest_trackable_value. |
243 | * |
244 | * @param h "This" pointer |
245 | * @param from Histogram to copy values from. |
246 | * @return The number of values dropped when copying. |
247 | */ |
248 | int64_t hdr_add_while_correcting_for_coordinated_omission( |
249 | struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval); |
250 | |
251 | /** |
252 | * Get minimum value from the histogram. Will return 2^63-1 if the histogram |
253 | * is empty. |
254 | * |
255 | * @param h "This" pointer |
256 | */ |
257 | int64_t hdr_min(const struct hdr_histogram* h); |
258 | |
259 | /** |
260 | * Get maximum value from the histogram. Will return 0 if the histogram |
261 | * is empty. |
262 | * |
263 | * @param h "This" pointer |
264 | */ |
265 | int64_t hdr_max(const struct hdr_histogram* h); |
266 | |
267 | /** |
268 | * Get the value at a specific percentile. |
269 | * |
270 | * @param h "This" pointer. |
271 | * @param percentile The percentile to get the value for |
272 | */ |
273 | int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile); |
274 | |
275 | /** |
276 | * Get the values at the given percentiles. |
277 | * |
278 | * @param h "This" pointer. |
279 | * @param percentiles The ordered percentiles array to get the values for. |
280 | * @param length Number of elements in the arrays. |
281 | * @param values Destination array containing the values at the given percentiles. |
282 | * The values array should be allocated by the caller. |
283 | * @return 0 on success, ENOMEM if the provided destination array is null. |
284 | */ |
285 | int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length); |
286 | |
287 | /** |
288 | * Gets the standard deviation for the values in the histogram. |
289 | * |
290 | * @param h "This" pointer |
291 | * @return The standard deviation |
292 | */ |
293 | double hdr_stddev(const struct hdr_histogram* h); |
294 | |
295 | /** |
296 | * Gets the mean for the values in the histogram. |
297 | * |
298 | * @param h "This" pointer |
299 | * @return The mean |
300 | */ |
301 | double hdr_mean(const struct hdr_histogram* h); |
302 | |
303 | /** |
304 | * Determine if two values are equivalent with the histogram's resolution. |
305 | * Where "equivalent" means that value samples recorded for any two |
306 | * equivalent values are counted in a common total count. |
307 | * |
308 | * @param h "This" pointer |
309 | * @param a first value to compare |
310 | * @param b second value to compare |
311 | * @return 'true' if values are equivalent with the histogram's resolution. |
312 | */ |
313 | bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b); |
314 | |
315 | /** |
316 | * Get the lowest value that is equivalent to the given value within the histogram's resolution. |
317 | * Where "equivalent" means that value samples recorded for any two |
318 | * equivalent values are counted in a common total count. |
319 | * |
320 | * @param h "This" pointer |
321 | * @param value The given value |
322 | * @return The lowest value that is equivalent to the given value within the histogram's resolution. |
323 | */ |
324 | int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value); |
325 | |
326 | /** |
327 | * Get the count of recorded values at a specific value |
328 | * (to within the histogram resolution at the value level). |
329 | * |
330 | * @param h "This" pointer |
331 | * @param value The value for which to provide the recorded count |
332 | * @return The total count of values recorded in the histogram within the value range that is |
333 | * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>) |
334 | */ |
335 | int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value); |
336 | |
337 | int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index); |
338 | |
339 | int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index); |
340 | |
341 | struct hdr_iter_percentiles |
342 | { |
343 | bool seen_last_value; |
344 | int32_t ticks_per_half_distance; |
345 | double percentile_to_iterate_to; |
346 | double percentile; |
347 | }; |
348 | |
349 | struct hdr_iter_recorded |
350 | { |
351 | int64_t count_added_in_this_iteration_step; |
352 | }; |
353 | |
354 | struct hdr_iter_linear |
355 | { |
356 | int64_t value_units_per_bucket; |
357 | int64_t count_added_in_this_iteration_step; |
358 | int64_t next_value_reporting_level; |
359 | int64_t next_value_reporting_level_lowest_equivalent; |
360 | }; |
361 | |
362 | struct hdr_iter_log |
363 | { |
364 | double log_base; |
365 | int64_t count_added_in_this_iteration_step; |
366 | int64_t next_value_reporting_level; |
367 | int64_t next_value_reporting_level_lowest_equivalent; |
368 | }; |
369 | |
370 | /** |
371 | * The basic iterator. This is a generic structure |
372 | * that supports all of the types of iteration. Use |
373 | * the appropriate initialiser to get the desired |
374 | * iteration. |
375 | * |
376 | * @ |
377 | */ |
378 | struct hdr_iter |
379 | { |
380 | const struct hdr_histogram* h; |
381 | /** raw index into the counts array */ |
382 | int32_t counts_index; |
383 | /** snapshot of the length at the time the iterator is created */ |
384 | int64_t total_count; |
385 | /** value directly from array for the current counts_index */ |
386 | int64_t count; |
387 | /** sum of all of the counts up to and including the count at this index */ |
388 | int64_t cumulative_count; |
389 | /** The current value based on counts_index */ |
390 | int64_t value; |
391 | int64_t highest_equivalent_value; |
392 | int64_t lowest_equivalent_value; |
393 | int64_t median_equivalent_value; |
394 | int64_t value_iterated_from; |
395 | int64_t value_iterated_to; |
396 | |
397 | union |
398 | { |
399 | struct hdr_iter_percentiles percentiles; |
400 | struct hdr_iter_recorded recorded; |
401 | struct hdr_iter_linear linear; |
402 | struct hdr_iter_log log; |
403 | } specifics; |
404 | |
405 | bool (* _next_fp)(struct hdr_iter* iter); |
406 | |
407 | }; |
408 | |
409 | /** |
410 | * Initalises the basic iterator. |
411 | * |
412 | * @param itr 'This' pointer |
413 | * @param h The histogram to iterate over |
414 | */ |
415 | void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h); |
416 | |
417 | /** |
418 | * Initialise the iterator for use with percentiles. |
419 | */ |
420 | void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance); |
421 | |
422 | /** |
423 | * Initialise the iterator for use with recorded values. |
424 | */ |
425 | void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h); |
426 | |
427 | /** |
428 | * Initialise the iterator for use with linear values. |
429 | */ |
430 | void hdr_iter_linear_init( |
431 | struct hdr_iter* iter, |
432 | const struct hdr_histogram* h, |
433 | int64_t value_units_per_bucket); |
434 | |
435 | /** |
436 | * Update the iterator value units per bucket |
437 | */ |
438 | void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket); |
439 | |
440 | /** |
441 | * Initialise the iterator for use with logarithmic values |
442 | */ |
443 | void hdr_iter_log_init( |
444 | struct hdr_iter* iter, |
445 | const struct hdr_histogram* h, |
446 | int64_t value_units_first_bucket, |
447 | double log_base); |
448 | |
449 | /** |
450 | * Iterate to the next value for the iterator. If there are no more values |
451 | * available return faluse. |
452 | * |
453 | * @param itr 'This' pointer |
454 | * @return 'false' if there are no values remaining for this iterator. |
455 | */ |
456 | bool hdr_iter_next(struct hdr_iter* iter); |
457 | |
458 | typedef enum |
459 | { |
460 | CLASSIC, |
461 | CSV |
462 | } format_type; |
463 | |
464 | /** |
465 | * Print out a percentile based histogram to the supplied stream. Note that |
466 | * this call will not flush the FILE, this is left up to the user. |
467 | * |
468 | * @param h 'This' pointer |
469 | * @param stream The FILE to write the output to |
470 | * @param ticks_per_half_distance The number of iteration steps per half-distance to 100% |
471 | * @param value_scale Scale the output values by this amount |
472 | * @param format_type Format to use, e.g. CSV. |
473 | * @return 0 on success, error code on failure. EIO if an error occurs writing |
474 | * the output. |
475 | */ |
476 | int hdr_percentiles_print( |
477 | struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, |
478 | double value_scale, format_type format); |
479 | |
480 | /** |
481 | * Internal allocation methods, used by hdr_dbl_histogram. |
482 | */ |
483 | struct hdr_histogram_bucket_config |
484 | { |
485 | int64_t lowest_discernible_value; |
486 | int64_t highest_trackable_value; |
487 | int64_t unit_magnitude; |
488 | int64_t significant_figures; |
489 | int32_t sub_bucket_half_count_magnitude; |
490 | int32_t sub_bucket_half_count; |
491 | int64_t sub_bucket_mask; |
492 | int32_t sub_bucket_count; |
493 | int32_t bucket_count; |
494 | int32_t counts_len; |
495 | }; |
496 | |
497 | int hdr_calculate_bucket_config( |
498 | int64_t lowest_discernible_value, |
499 | int64_t highest_trackable_value, |
500 | int significant_figures, |
501 | struct hdr_histogram_bucket_config* cfg); |
502 | |
503 | void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg); |
504 | |
505 | int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value); |
506 | |
507 | int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value); |
508 | |
509 | int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value); |
510 | |
511 | /** |
512 | * Used to reset counters after importing data manually into the histogram, used by the logging code |
513 | * and other custom serialisation tools. |
514 | */ |
515 | void hdr_reset_internal_counters(struct hdr_histogram* h); |
516 | |
517 | #ifdef __cplusplus |
518 | } |
519 | #endif |
520 | |
521 | #endif |
522 | |