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_trackable_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_trackable_value The smallest possible value to be put into the 49 * histogram. 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_trackable_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_trackable_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 count values in the histogram, will round this value of to a 115 * precision at or better than the significant_figure specified at construction 116 * time. 117 * 118 * @param h "This" pointer 119 * @param value Value to add to the histogram 120 * @param count Number of 'value's to add to the histogram 121 * @return false if any value is larger than the highest_trackable_value and can't be recorded, 122 * true otherwise. 123 */ 124 bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count); 125 126 127 /** 128 * Record a value in the histogram and backfill based on an expected interval. 129 * 130 * Records a value in the histogram, will round this value of to a precision at or better 131 * than the significant_figure specified at contruction time. This is specifically used 132 * for recording latency. If the value is larger than the expected_interval then the 133 * latency recording system has experienced co-ordinated omission. This method fills in the 134 * values that would have occured had the client providing the load not been blocked. 135 136 * @param h "This" pointer 137 * @param value Value to add to the histogram 138 * @param expected_interval The delay between recording values. 139 * @return false if the value is larger than the highest_trackable_value and can't be recorded, 140 * true otherwise. 141 */ 142 bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expexcted_interval); 143 /** 144 * Record a value in the histogram 'count' times. Applies the same correcting logic 145 * as 'hdr_record_corrected_value'. 146 * 147 * @param h "This" pointer 148 * @param value Value to add to the histogram 149 * @param count Number of 'value's to add to the histogram 150 * @param expected_interval The delay between recording values. 151 * @return false if the value is larger than the highest_trackable_value and can't be recorded, 152 * true otherwise. 153 */ 154 bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval); 155 156 /** 157 * Adds all of the values from 'from' to 'this' histogram. Will return the 158 * number of values that are dropped when copying. Values will be dropped 159 * if they around outside of h.lowest_trackable_value and 160 * h.highest_trackable_value. 161 * 162 * @param h "This" pointer 163 * @param from Histogram to copy values from. 164 * @return The number of values dropped when copying. 165 */ 166 int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from); 167 168 /** 169 * Adds all of the values from 'from' to 'this' histogram. Will return the 170 * number of values that are dropped when copying. Values will be dropped 171 * if they around outside of h.lowest_trackable_value and 172 * h.highest_trackable_value. 173 * 174 * @param h "This" pointer 175 * @param from Histogram to copy values from. 176 * @return The number of values dropped when copying. 177 */ 178 int64_t hdr_add_while_correcting_for_coordinated_omission( 179 struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval); 180 181 /** 182 * Get minimum value from the histogram. Will return 2^63-1 if the histogram 183 * is empty. 184 * 185 * @param h "This" pointer 186 */ 187 int64_t hdr_min(const struct hdr_histogram* h); 188 189 /** 190 * Get maximum value from the histogram. Will return 0 if the histogram 191 * is empty. 192 * 193 * @param h "This" pointer 194 */ 195 int64_t hdr_max(const struct hdr_histogram* h); 196 197 /** 198 * Get the value at a specific percentile. 199 * 200 * @param h "This" pointer. 201 * @param percentile The percentile to get the value for 202 */ 203 int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile); 204 205 /** 206 * Gets the standard deviation for the values in the histogram. 207 * 208 * @param h "This" pointer 209 * @return The standard deviation 210 */ 211 double hdr_stddev(const struct hdr_histogram* h); 212 213 /** 214 * Gets the mean for the values in the histogram. 215 * 216 * @param h "This" pointer 217 * @return The mean 218 */ 219 double hdr_mean(const struct hdr_histogram* h); 220 221 /** 222 * Determine if two values are equivalent with the histogram's resolution. 223 * Where "equivalent" means that value samples recorded for any two 224 * equivalent values are counted in a common total count. 225 * 226 * @param h "This" pointer 227 * @param a first value to compare 228 * @param b second value to compare 229 * @return 'true' if values are equivalent with the histogram's resolution. 230 */ 231 bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b); 232 233 /** 234 * Get the lowest value that is equivalent to the given value within the histogram's resolution. 235 * Where "equivalent" means that value samples recorded for any two 236 * equivalent values are counted in a common total count. 237 * 238 * @param h "This" pointer 239 * @param value The given value 240 * @return The lowest value that is equivalent to the given value within the histogram's resolution. 241 */ 242 int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value); 243 244 /** 245 * Get the count of recorded values at a specific value 246 * (to within the histogram resolution at the value level). 247 * 248 * @param h "This" pointer 249 * @param value The value for which to provide the recorded count 250 * @return The total count of values recorded in the histogram within the value range that is 251 * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>) 252 */ 253 int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value); 254 255 int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index); 256 257 int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index); 258 259 struct hdr_iter_percentiles 260 { 261 bool seen_last_value; 262 int32_t ticks_per_half_distance; 263 double percentile_to_iterate_to; 264 double percentile; 265 }; 266 267 struct hdr_iter_recorded 268 { 269 int64_t count_added_in_this_iteration_step; 270 }; 271 272 struct hdr_iter_linear 273 { 274 int64_t value_units_per_bucket; 275 int64_t count_added_in_this_iteration_step; 276 int64_t next_value_reporting_level; 277 int64_t next_value_reporting_level_lowest_equivalent; 278 }; 279 280 struct hdr_iter_log 281 { 282 double log_base; 283 int64_t count_added_in_this_iteration_step; 284 int64_t next_value_reporting_level; 285 int64_t next_value_reporting_level_lowest_equivalent; 286 }; 287 288 /** 289 * The basic iterator. This is a generic structure 290 * that supports all of the types of iteration. Use 291 * the appropriate initialiser to get the desired 292 * iteration. 293 * 294 * @ 295 */ 296 struct hdr_iter 297 { 298 const struct hdr_histogram* h; 299 /** raw index into the counts array */ 300 int32_t counts_index; 301 /** snapshot of the length at the time the iterator is created */ 302 int32_t total_count; 303 /** value directly from array for the current counts_index */ 304 int64_t count; 305 /** sum of all of the counts up to and including the count at this index */ 306 int64_t cumulative_count; 307 /** The current value based on counts_index */ 308 int64_t value; 309 int64_t highest_equivalent_value; 310 int64_t lowest_equivalent_value; 311 int64_t median_equivalent_value; 312 int64_t value_iterated_from; 313 int64_t value_iterated_to; 314 315 union 316 { 317 struct hdr_iter_percentiles percentiles; 318 struct hdr_iter_recorded recorded; 319 struct hdr_iter_linear linear; 320 struct hdr_iter_log log; 321 } specifics; 322 323 bool (* _next_fp)(struct hdr_iter* iter); 324 325 }; 326 327 /** 328 * Initalises the basic iterator. 329 * 330 * @param itr 'This' pointer 331 * @param h The histogram to iterate over 332 */ 333 void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h); 334 335 /** 336 * Initialise the iterator for use with percentiles. 337 */ 338 void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance); 339 340 /** 341 * Initialise the iterator for use with recorded values. 342 */ 343 void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h); 344 345 /** 346 * Initialise the iterator for use with linear values. 347 */ 348 void hdr_iter_linear_init( 349 struct hdr_iter* iter, 350 const struct hdr_histogram* h, 351 int64_t value_units_per_bucket); 352 353 /** 354 * Initialise the iterator for use with logarithmic values 355 */ 356 void hdr_iter_log_init( 357 struct hdr_iter* iter, 358 const struct hdr_histogram* h, 359 int64_t value_units_first_bucket, 360 double log_base); 361 362 /** 363 * Iterate to the next value for the iterator. If there are no more values 364 * available return faluse. 365 * 366 * @param itr 'This' pointer 367 * @return 'false' if there are no values remaining for this iterator. 368 */ 369 bool hdr_iter_next(struct hdr_iter* iter); 370 371 typedef enum 372 { 373 CLASSIC, 374 CSV 375 } format_type; 376 377 /** 378 * Print out a percentile based histogram to the supplied stream. Note that 379 * this call will not flush the FILE, this is left up to the user. 380 * 381 * @param h 'This' pointer 382 * @param stream The FILE to write the output to 383 * @param ticks_per_half_distance The number of iteration steps per half-distance to 100% 384 * @param value_scale Scale the output values by this amount 385 * @param format_type Format to use, e.g. CSV. 386 * @return 0 on success, error code on failure. EIO if an error occurs writing 387 * the output. 388 */ 389 int hdr_percentiles_print( 390 struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, 391 double value_scale, format_type format); 392 393 /** 394 * Internal allocation methods, used by hdr_dbl_histogram. 395 */ 396 struct hdr_histogram_bucket_config 397 { 398 int64_t lowest_trackable_value; 399 int64_t highest_trackable_value; 400 int64_t unit_magnitude; 401 int64_t significant_figures; 402 int32_t sub_bucket_half_count_magnitude; 403 int32_t sub_bucket_half_count; 404 int64_t sub_bucket_mask; 405 int32_t sub_bucket_count; 406 int32_t bucket_count; 407 int32_t counts_len; 408 }; 409 410 int hdr_calculate_bucket_config( 411 int64_t lowest_trackable_value, 412 int64_t highest_trackable_value, 413 int significant_figures, 414 struct hdr_histogram_bucket_config* cfg); 415 416 void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg); 417 418 int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value); 419 420 int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value); 421 422 int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value); 423 424 /** 425 * Used to reset counters after importing data manuallying into the histogram, used by the logging code 426 * and other custom serialisation tools. 427 */ 428 void hdr_reset_internal_counters(struct hdr_histogram* h); 429 430 #ifdef __cplusplus 431 } 432 #endif 433 434 #endif