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 int64_t unit_magnitude; 22 int64_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[0]; 35 }; 36 37 /** 38 * Allocate the memory and initialise the hdr_histogram. 39 * 40 * Due to the size of the histogram being the result of some reasonably 41 * involved math on the input parameters this function it is tricky to stack allocate. 42 * The histogram is allocated in a single contigious block so can be delete via free, 43 * without any structure specific destructor. 44 * 45 * @param lowest_trackable_value The smallest possible value to be put into the 46 * histogram. 47 * @param highest_trackable_value The largest possible value to be put into the 48 * histogram. 49 * @param significant_figures The level of precision for this histogram, i.e. the number 50 * of figures in a decimal number that will be maintained. E.g. a value of 3 will mean 51 * the results from the histogram will be accurate up to the first three digits. Must 52 * be a value between 1 and 5 (inclusive). 53 * @param result Output parameter to capture allocated histogram. 54 * @return 0 on success, EINVAL if lowest_trackable_value is < 1 or the 55 * significant_figure value is outside of the allowed range, ENOMEM if malloc 56 * failed. 57 */ 58 int hdr_init( 59 int64_t lowest_trackable_value, 60 int64_t highest_trackable_value, 61 int significant_figures, 62 struct hdr_histogram** result); 63 64 /** 65 * Allocate the memory and initialise the hdr_histogram. This is the equivalent of calling 66 * hdr_init(1, highest_trackable_value, significant_figures, result); 67 * 68 * @deprecated use hdr_init. 69 */ 70 int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result); 71 72 73 /** 74 * Reset a histogram to zero - empty out a histogram and re-initialise it 75 * 76 * If you want to re-use an existing histogram, but reset everything back to zero, this 77 * is the routine to use. 78 * 79 * @param h The histogram you want to reset to empty. 80 * 81 */ 82 void hdr_reset(struct hdr_histogram *h); 83 84 /** 85 * Get the memory size of the hdr_histogram. 86 * 87 * @param h "This" pointer 88 * @return The amount of memory used by the hdr_histogram in bytes 89 */ 90 size_t hdr_get_memory_size(struct hdr_histogram *h); 91 92 /** 93 * Records a value in the histogram, will round this value of to a precision at or better 94 * than the significant_figure specified at construction time. 95 * 96 * @param h "This" pointer 97 * @param value Value to add to the histogram 98 * @return false if the value is larger than the highest_trackable_value and can't be recorded, 99 * true otherwise. 100 */ 101 bool hdr_record_value(struct hdr_histogram* h, int64_t value); 102 103 /** 104 * Records count values in the histogram, will round this value of to a 105 * precision at or better than the significant_figure specified at construction 106 * time. 107 * 108 * @param h "This" pointer 109 * @param value Value to add to the histogram 110 * @return false if the value is larger than the highest_trackable_value and can't be recorded, 111 * true otherwise. 112 */ 113 bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count); 114 115 116 /** 117 * Record a value in the histogram and backfill based on an expected interval. 118 * 119 * Records a value in the histogram, will round this value of to a precision at or better 120 * than the significant_figure specified at contruction time. This is specifically used 121 * for recording latency. If the value is larger than the expected_interval then the 122 * latency recording system has experienced co-ordinated omission. This method fills in the 123 * values that would have occured had the client providing the load not been blocked. 124 125 * @param h "This" pointer 126 * @param value Value to add to the histogram 127 * @param expected_interval The delay between recording values. 128 * @return false if the value is larger than the highest_trackable_value and can't be recorded, 129 * true otherwise. 130 */ 131 bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expexcted_interval); 132 133 /** 134 * Adds all of the values from 'from' to 'this' histogram. Will return the 135 * number of values that are dropped when copying. Values will be dropped 136 * if they around outside of h.lowest_trackable_value and 137 * h.highest_trackable_value. 138 * 139 * @param h "This" pointer 140 * @param from Histogram to copy values from. 141 * @return The number of values dropped when copying. 142 */ 143 int64_t hdr_add(struct hdr_histogram* h, struct hdr_histogram* from); 144 145 /* 146 * Create a new histogram representing the delta between 'base' and 'update'. 147 */ 148 struct hdr_histogram *hdr_diff(struct hdr_histogram *base, struct hdr_histogram *update); 149 150 int64_t hdr_min(struct hdr_histogram* h); 151 int64_t hdr_max(struct hdr_histogram* h); 152 int64_t hdr_value_at_percentile(struct hdr_histogram* h, double percentile); 153 154 double hdr_mean(struct hdr_histogram* h); 155 bool hdr_values_are_equivalent(struct hdr_histogram* h, int64_t a, int64_t b); 156 int64_t hdr_lowest_equivalent_value(struct hdr_histogram* h, int64_t value); 157 int64_t hdr_count_at_value(struct hdr_histogram* h, int64_t value); 158 int64_t hdr_count_at_index(struct hdr_histogram* h, int32_t index); 159 int64_t hdr_value_at_index(struct hdr_histogram* h, int32_t index); 160 161 struct hdr_iter_percentiles 162 { 163 bool seen_last_value; 164 int32_t ticks_per_half_distance; 165 double percentile_to_iterate_to; 166 double percentile; 167 }; 168 169 struct hdr_iter_recorded 170 { 171 int64_t count_added_in_this_iteration_step; 172 }; 173 174 struct hdr_iter_linear 175 { 176 int64_t value_units_per_bucket; 177 int64_t count_added_in_this_iteration_step; 178 int64_t next_value_reporting_level; 179 int64_t next_value_reporting_level_lowest_equivalent; 180 }; 181 182 struct hdr_iter_log 183 { 184 int64_t value_units_first_bucket; 185 double log_base; 186 int64_t count_added_in_this_iteration_step; 187 int64_t next_value_reporting_level; 188 int64_t next_value_reporting_level_lowest_equivalent; 189 }; 190 191 /** 192 * The basic iterator. This is the equivlent of the 193 * AllValues iterator from the Java implementation. It iterates 194 * through all entries in the histogram whether or not a value 195 * is recorded. 196 */ 197 struct hdr_iter 198 { 199 struct hdr_histogram* h; 200 int32_t bucket_index; 201 int32_t sub_bucket_index; 202 int64_t count_at_index; 203 int64_t count_to_index; 204 int64_t value_from_index; 205 int64_t highest_equivalent_value; 206 207 union 208 { 209 struct hdr_iter_percentiles percentiles; 210 struct hdr_iter_recorded recorded; 211 struct hdr_iter_linear linear; 212 struct hdr_iter_log log; 213 } specifics; 214 215 bool (*_next_fp)(struct hdr_iter* iter); 216 }; 217 218 /** 219 * Initalises the basic iterator. 220 * 221 * @param itr 'This' pointer 222 * @param h The histogram to iterate over 223 */ 224 void hdr_iter_init(struct hdr_iter* iter, struct hdr_histogram* h); 225 226 /** 227 * Initialise the iterator for use with percentiles. 228 */ 229 void hdr_iter_percentile_init(struct hdr_iter* iter, struct hdr_histogram* h, int32_t ticks_per_half_distance); 230 231 /** 232 * Initialise the iterator for use with recorded values. 233 */ 234 void hdr_iter_recorded_init(struct hdr_iter* iter, struct hdr_histogram* h); 235 236 /** 237 * Initialise the iterator for use with linear values. 238 */ 239 void hdr_iter_linear_init( 240 struct hdr_iter* iter, 241 struct hdr_histogram* h, 242 int64_t value_units_per_bucket); 243 244 /** 245 * Initialise the iterator for use with logarithmic values 246 */ 247 void hdr_iter_log_init( 248 struct hdr_iter* iter, 249 struct hdr_histogram* h, 250 int64_t value_units_first_bucket, 251 double log_base); 252 253 /** 254 * Iterate to the next value for the iterator. If there are no more values 255 * available return faluse. 256 * 257 * @param itr 'This' pointer 258 * @return 'false' if there are no values remaining for this iterator. 259 */ 260 bool hdr_iter_next(struct hdr_iter* iter); 261 262 typedef enum { 263 CLASSIC, 264 CSV 265 } format_type; 266 267 /** 268 * Print out a percentile based histogram to the supplied stream. Note that 269 * this call will not flush the FILE, this is left up to the user. 270 * 271 * @param h 'This' pointer 272 * @param stream The FILE to write the output to 273 * @param ticks_per_half_distance The number of iteration steps per half-distance to 100% 274 * @param value_scale Scale the output values by this amount 275 * @param format_type Format to use, e.g. CSV. 276 * @return 0 on success, error code on failure. EIO if an error occurs writing 277 * the output. 278 */ 279 int hdr_percentiles_print( 280 struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, 281 double value_scale, format_type format); 282 283 /** 284 * Internal allocation methods, used by hdr_dbl_histogram. 285 */ 286 struct hdr_histogram_bucket_config 287 { 288 int64_t lowest_trackable_value; 289 int64_t highest_trackable_value; 290 int64_t unit_magnitude; 291 int64_t significant_figures; 292 int32_t sub_bucket_half_count_magnitude; 293 int32_t sub_bucket_half_count; 294 int64_t sub_bucket_mask; 295 int32_t sub_bucket_count; 296 int32_t bucket_count; 297 int32_t counts_len; 298 }; 299 300 int hdr_calculate_bucket_config( 301 int64_t lowest_trackable_value, 302 int64_t highest_trackable_value, 303 int significant_figures, 304 struct hdr_histogram_bucket_config* cfg); 305 306 void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg); 307 308 bool hdr_shift_values_left(struct hdr_histogram* h, int32_t binary_orders_of_magnitude); 309 bool hdr_shift_values_right(struct hdr_histogram* h, int32_t shift); 310 311 #endif 312