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
17struct 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
38extern "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 */
61int 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 */
72void 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 */
80int 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 */
92void 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 */
100size_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 */
111bool 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 */
126bool 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 */
139bool 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 */
156bool 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 */
173bool 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 */
194bool 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 */
207bool 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 */
224bool 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 */
236int64_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 */
248int64_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 */
257int64_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 */
265int64_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 */
273int64_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 */
285int 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 */
293double 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 */
301double 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 */
313bool 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 */
324int64_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 */
335int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value);
336
337int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index);
338
339int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index);
340
341struct 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
349struct hdr_iter_recorded
350{
351 int64_t count_added_in_this_iteration_step;
352};
353
354struct 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
362struct 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 */
378struct 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 */
415void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h);
416
417/**
418 * Initialise the iterator for use with percentiles.
419 */
420void 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 */
425void 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 */
430void 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 */
438void 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 */
443void 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 */
456bool hdr_iter_next(struct hdr_iter* iter);
457
458typedef 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 */
476int 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*/
483struct 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
497int 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
503void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg);
504
505int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value);
506
507int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value);
508
509int64_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 */
515void hdr_reset_internal_counters(struct hdr_histogram* h);
516
517#ifdef __cplusplus
518}
519#endif
520
521#endif
522