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 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 contruction 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 occured 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 expexcted_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 contruction 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 occured 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 expexcted_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_trackable_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_trackable_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 * Gets the standard deviation for the values in the histogram. 277 * 278 * @param h "This" pointer 279 * @return The standard deviation 280 */ 281 double hdr_stddev(const struct hdr_histogram* h); 282 283 /** 284 * Gets the mean for the values in the histogram. 285 * 286 * @param h "This" pointer 287 * @return The mean 288 */ 289 double hdr_mean(const struct hdr_histogram* h); 290 291 /** 292 * Determine if two values are equivalent with the histogram's resolution. 293 * Where "equivalent" means that value samples recorded for any two 294 * equivalent values are counted in a common total count. 295 * 296 * @param h "This" pointer 297 * @param a first value to compare 298 * @param b second value to compare 299 * @return 'true' if values are equivalent with the histogram's resolution. 300 */ 301 bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b); 302 303 /** 304 * Get the lowest value that is equivalent to the given value within 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 value The given value 310 * @return The lowest value that is equivalent to the given value within the histogram's resolution. 311 */ 312 int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value); 313 314 /** 315 * Get the count of recorded values at a specific value 316 * (to within the histogram resolution at the value level). 317 * 318 * @param h "This" pointer 319 * @param value The value for which to provide the recorded count 320 * @return The total count of values recorded in the histogram within the value range that is 321 * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>) 322 */ 323 int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value); 324 325 int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index); 326 327 int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index); 328 329 struct hdr_iter_percentiles 330 { 331 bool seen_last_value; 332 int32_t ticks_per_half_distance; 333 double percentile_to_iterate_to; 334 double percentile; 335 }; 336 337 struct hdr_iter_recorded 338 { 339 int64_t count_added_in_this_iteration_step; 340 }; 341 342 struct hdr_iter_linear 343 { 344 int64_t value_units_per_bucket; 345 int64_t count_added_in_this_iteration_step; 346 int64_t next_value_reporting_level; 347 int64_t next_value_reporting_level_lowest_equivalent; 348 }; 349 350 struct hdr_iter_log 351 { 352 double log_base; 353 int64_t count_added_in_this_iteration_step; 354 int64_t next_value_reporting_level; 355 int64_t next_value_reporting_level_lowest_equivalent; 356 }; 357 358 /** 359 * The basic iterator. This is a generic structure 360 * that supports all of the types of iteration. Use 361 * the appropriate initialiser to get the desired 362 * iteration. 363 * 364 * @ 365 */ 366 struct hdr_iter 367 { 368 const struct hdr_histogram* h; 369 /** raw index into the counts array */ 370 int32_t counts_index; 371 /** snapshot of the length at the time the iterator is created */ 372 int64_t total_count; 373 /** value directly from array for the current counts_index */ 374 int64_t count; 375 /** sum of all of the counts up to and including the count at this index */ 376 int64_t cumulative_count; 377 /** The current value based on counts_index */ 378 int64_t value; 379 int64_t highest_equivalent_value; 380 int64_t lowest_equivalent_value; 381 int64_t median_equivalent_value; 382 int64_t value_iterated_from; 383 int64_t value_iterated_to; 384 385 union 386 { 387 struct hdr_iter_percentiles percentiles; 388 struct hdr_iter_recorded recorded; 389 struct hdr_iter_linear linear; 390 struct hdr_iter_log log; 391 } specifics; 392 393 bool (* _next_fp)(struct hdr_iter* iter); 394 395 }; 396 397 /** 398 * Initalises the basic iterator. 399 * 400 * @param itr 'This' pointer 401 * @param h The histogram to iterate over 402 */ 403 void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h); 404 405 /** 406 * Initialise the iterator for use with percentiles. 407 */ 408 void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance); 409 410 /** 411 * Initialise the iterator for use with recorded values. 412 */ 413 void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h); 414 415 /** 416 * Initialise the iterator for use with linear values. 417 */ 418 void hdr_iter_linear_init( 419 struct hdr_iter* iter, 420 const struct hdr_histogram* h, 421 int64_t value_units_per_bucket); 422 423 /** 424 * Initialise the iterator for use with logarithmic values 425 */ 426 void hdr_iter_log_init( 427 struct hdr_iter* iter, 428 const struct hdr_histogram* h, 429 int64_t value_units_first_bucket, 430 double log_base); 431 432 /** 433 * Iterate to the next value for the iterator. If there are no more values 434 * available return faluse. 435 * 436 * @param itr 'This' pointer 437 * @return 'false' if there are no values remaining for this iterator. 438 */ 439 bool hdr_iter_next(struct hdr_iter* iter); 440 441 typedef enum 442 { 443 CLASSIC, 444 CSV 445 } format_type; 446 447 /** 448 * Print out a percentile based histogram to the supplied stream. Note that 449 * this call will not flush the FILE, this is left up to the user. 450 * 451 * @param h 'This' pointer 452 * @param stream The FILE to write the output to 453 * @param ticks_per_half_distance The number of iteration steps per half-distance to 100% 454 * @param value_scale Scale the output values by this amount 455 * @param format_type Format to use, e.g. CSV. 456 * @return 0 on success, error code on failure. EIO if an error occurs writing 457 * the output. 458 */ 459 int hdr_percentiles_print( 460 struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, 461 double value_scale, format_type format); 462 463 /** 464 * Internal allocation methods, used by hdr_dbl_histogram. 465 */ 466 struct hdr_histogram_bucket_config 467 { 468 int64_t lowest_trackable_value; 469 int64_t highest_trackable_value; 470 int64_t unit_magnitude; 471 int64_t significant_figures; 472 int32_t sub_bucket_half_count_magnitude; 473 int32_t sub_bucket_half_count; 474 int64_t sub_bucket_mask; 475 int32_t sub_bucket_count; 476 int32_t bucket_count; 477 int32_t counts_len; 478 }; 479 480 int hdr_calculate_bucket_config( 481 int64_t lowest_trackable_value, 482 int64_t highest_trackable_value, 483 int significant_figures, 484 struct hdr_histogram_bucket_config* cfg); 485 486 void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg); 487 488 int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value); 489 490 int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value); 491 492 int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value); 493 494 /** 495 * Used to reset counters after importing data manuallying into the histogram, used by the logging code 496 * and other custom serialisation tools. 497 */ 498 void hdr_reset_internal_counters(struct hdr_histogram* h); 499 500 #ifdef __cplusplus 501 } 502 #endif 503 504 #endif 505