1 /**
2 * collectd - src/utils_latency.c
3 * Copyright (C) 2013 Florian Forster
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 *
23 * Authors:
24 * Florian Forster <ff at octo.it>
25 **/
27 #include "collectd.h"
29 #include "plugin.h"
30 #include "utils_latency.h"
31 #include "common.h"
33 #include <math.h>
34 #include <limits.h>
36 #ifndef LLONG_MAX
37 # define LLONG_MAX 9223372036854775807LL
38 #endif
40 #ifndef HISTOGRAM_NUM_BINS
41 # define HISTOGRAM_NUM_BINS 1000
42 #endif
44 #ifndef HISTOGRAM_DEFAULT_BIN_WIDTH
45 /* 1048576 = 2^20 ^= 1/1024 s */
46 # define HISTOGRAM_DEFAULT_BIN_WIDTH 1048576
47 #endif
49 struct latency_counter_s
50 {
51 cdtime_t start_time;
53 cdtime_t sum;
54 size_t num;
56 cdtime_t min;
57 cdtime_t max;
59 cdtime_t bin_width;
60 int histogram[HISTOGRAM_NUM_BINS];
61 };
63 /*
64 * Histogram represents the distribution of data, it has a list of "bins".
65 * Each bin represents an interval and has a count (frequency) of
66 * number of values fall within its interval.
67 *
68 * Histogram's range is determined by the number of bins and the bin width,
69 * There are 1000 bins and all bins have the same width of default 1 millisecond.
70 * When a value above this range is added, Histogram's range is increased by
71 * increasing the bin width (note that number of bins remains always at 1000).
72 * This operation of increasing bin width is little expensive as each bin need
73 * to be visited to update it's count. To reduce frequent change of bin width,
74 * new bin width will be the next nearest power of 2. Example: 2, 4, 8, 16, 32,
75 * 64, 128, 256, 512, 1024, 2048, 5086, ...
76 *
77 * So, if the required bin width is 300, then new bin width will be 512 as it is
78 * the next nearest power of 2.
79 */
80 static void change_bin_width (latency_counter_t *lc, cdtime_t latency) /* {{{ */
81 {
82 /* This function is called because the new value is above histogram's range.
83 * First find the required bin width:
84 * requiredBinWidth = (value + 1) / numBins
85 * then get the next nearest power of 2
86 * newBinWidth = 2^(ceil(log2(requiredBinWidth)))
87 */
88 double required_bin_width = ((double) (latency + 1)) / ((double) HISTOGRAM_NUM_BINS);
89 double required_bin_width_logbase2 = log (required_bin_width) / log (2.0);
90 cdtime_t new_bin_width = (cdtime_t) (pow (2.0, ceil (required_bin_width_logbase2)) + .5);
91 cdtime_t old_bin_width = lc->bin_width;
93 lc->bin_width = new_bin_width;
95 /* bin_width has been increased, now iterate through all bins and move the
96 * old bin's count to new bin. */
97 if (lc->num > 0) // if the histogram has data then iterate else skip
98 {
99 double width_change_ratio = ((double) old_bin_width) / ((double) new_bin_width);
101 for (size_t i = 0; i < HISTOGRAM_NUM_BINS; i++)
102 {
103 size_t new_bin = (size_t) (((double) i) * width_change_ratio);
104 if (i == new_bin)
105 continue;
106 assert (new_bin < i);
108 lc->histogram[new_bin] += lc->histogram[i];
109 lc->histogram[i] = 0;
110 }
111 }
113 DEBUG("utils_latency: change_bin_width: latency = %.3f; "
114 "old_bin_width = %.3f; new_bin_width = %.3f;",
115 CDTIME_T_TO_DOUBLE (latency),
116 CDTIME_T_TO_DOUBLE (old_bin_width),
117 CDTIME_T_TO_DOUBLE (new_bin_width));
118 } /* }}} void change_bin_width */
120 latency_counter_t *latency_counter_create (void) /* {{{ */
121 {
122 latency_counter_t *lc;
124 lc = calloc (1, sizeof (*lc));
125 if (lc == NULL)
126 return (NULL);
128 lc->bin_width = HISTOGRAM_DEFAULT_BIN_WIDTH;
129 latency_counter_reset (lc);
130 return (lc);
131 } /* }}} latency_counter_t *latency_counter_create */
133 void latency_counter_destroy (latency_counter_t *lc) /* {{{ */
134 {
135 sfree (lc);
136 } /* }}} void latency_counter_destroy */
138 void latency_counter_add (latency_counter_t *lc, cdtime_t latency) /* {{{ */
139 {
140 cdtime_t bin;
142 if ((lc == NULL) || (latency == 0) || (latency > ((cdtime_t) LLONG_MAX)))
143 return;
145 lc->sum += latency;
146 lc->num++;
148 if ((lc->min == 0) && (lc->max == 0))
149 lc->min = lc->max = latency;
150 if (lc->min > latency)
151 lc->min = latency;
152 if (lc->max < latency)
153 lc->max = latency;
155 /* A latency of _exactly_ 1.0 ms should be stored in the buffer 0, so
156 * subtract one from the cdtime_t value so that exactly 1.0 ms get sorted
157 * accordingly. */
158 bin = (latency - 1) / lc->bin_width;
159 if (bin >= HISTOGRAM_NUM_BINS)
160 {
161 change_bin_width (lc, latency);
162 bin = (latency - 1) / lc->bin_width;
163 if (bin >= HISTOGRAM_NUM_BINS)
164 {
165 ERROR ("utils_latency: latency_counter_add: Invalid bin: %"PRIu64, bin);
166 return;
167 }
168 }
169 lc->histogram[bin]++;
170 } /* }}} void latency_counter_add */
172 void latency_counter_reset (latency_counter_t *lc) /* {{{ */
173 {
174 if (lc == NULL)
175 return;
177 cdtime_t bin_width = lc->bin_width;
178 cdtime_t max_bin = (lc->max - 1) / lc->bin_width;
180 /*
181 If max latency is REDUCE_THRESHOLD times less than histogram's range,
182 then cut it in half. REDUCE_THRESHOLD must be >= 2.
183 Value of 4 is selected to reduce frequent changes of bin width.
184 */
185 #define REDUCE_THRESHOLD 4
186 if ((lc->num > 0) && (lc->bin_width >= HISTOGRAM_DEFAULT_BIN_WIDTH * 2)
187 && (max_bin < HISTOGRAM_NUM_BINS / REDUCE_THRESHOLD))
188 {
189 /* new bin width will be the previous power of 2 */
190 bin_width = bin_width / 2;
192 DEBUG("utils_latency: latency_counter_reset: max_latency = %.3f; "
193 "max_bin = %"PRIu64"; old_bin_width = %.3f; new_bin_width = %.3f;",
194 CDTIME_T_TO_DOUBLE (lc->max),
195 max_bin,
196 CDTIME_T_TO_DOUBLE (lc->bin_width),
197 CDTIME_T_TO_DOUBLE (bin_width));
198 }
200 memset (lc, 0, sizeof (*lc));
202 /* preserve bin width */
203 lc->bin_width = bin_width;
204 lc->start_time = cdtime ();
205 } /* }}} void latency_counter_reset */
207 cdtime_t latency_counter_get_min (latency_counter_t *lc) /* {{{ */
208 {
209 if (lc == NULL)
210 return (0);
211 return (lc->min);
212 } /* }}} cdtime_t latency_counter_get_min */
214 cdtime_t latency_counter_get_max (latency_counter_t *lc) /* {{{ */
215 {
216 if (lc == NULL)
217 return (0);
218 return (lc->max);
219 } /* }}} cdtime_t latency_counter_get_max */
221 cdtime_t latency_counter_get_sum (latency_counter_t *lc) /* {{{ */
222 {
223 if (lc == NULL)
224 return (0);
225 return (lc->sum);
226 } /* }}} cdtime_t latency_counter_get_sum */
228 size_t latency_counter_get_num (latency_counter_t *lc) /* {{{ */
229 {
230 if (lc == NULL)
231 return (0);
232 return (lc->num);
233 } /* }}} size_t latency_counter_get_num */
235 cdtime_t latency_counter_get_average (latency_counter_t *lc) /* {{{ */
236 {
237 double average;
239 if ((lc == NULL) || (lc->num == 0))
240 return (0);
242 average = CDTIME_T_TO_DOUBLE (lc->sum) / ((double) lc->num);
243 return (DOUBLE_TO_CDTIME_T (average));
244 } /* }}} cdtime_t latency_counter_get_average */
246 cdtime_t latency_counter_get_percentile (latency_counter_t *lc, /* {{{ */
247 double percent)
248 {
249 double percent_upper;
250 double percent_lower;
251 double p;
252 cdtime_t latency_lower;
253 cdtime_t latency_interpolated;
254 int sum;
255 size_t i;
257 if ((lc == NULL) || (lc->num == 0) || !((percent > 0.0) && (percent < 100.0)))
258 return (0);
260 /* Find index i so that at least "percent" events are within i+1 ms. */
261 percent_upper = 0.0;
262 percent_lower = 0.0;
263 sum = 0;
264 for (i = 0; i < HISTOGRAM_NUM_BINS; i++)
265 {
266 percent_lower = percent_upper;
267 sum += lc->histogram[i];
268 if (sum == 0)
269 percent_upper = 0.0;
270 else
271 percent_upper = 100.0 * ((double) sum) / ((double) lc->num);
273 if (percent_upper >= percent)
274 break;
275 }
277 if (i >= HISTOGRAM_NUM_BINS)
278 return (0);
280 assert (percent_upper >= percent);
281 assert (percent_lower < percent);
283 if (i == 0)
284 return (lc->bin_width);
286 latency_lower = ((cdtime_t) i) * lc->bin_width;
287 p = (percent - percent_lower) / (percent_upper - percent_lower);
289 latency_interpolated = latency_lower
290 + DOUBLE_TO_CDTIME_T (p * CDTIME_T_TO_DOUBLE (lc->bin_width));
292 DEBUG ("latency_counter_get_percentile: latency_interpolated = %.3f",
293 CDTIME_T_TO_DOUBLE (latency_interpolated));
294 return (latency_interpolated);
295 } /* }}} cdtime_t latency_counter_get_percentile */
297 cdtime_t latency_counter_get_start_time (const latency_counter_t *lc) /* {{{ */
298 {
299 if (lc == NULL)
300 return (0);
302 return lc->start_time;
303 } /* }}} cdtime_t latency_counter_get_start_time */
305 double latency_counter_get_rate (const latency_counter_t *lc, /* {{{ */
306 const cdtime_t lower, cdtime_t upper, const cdtime_t now)
307 {
308 cdtime_t lower_bin;
309 cdtime_t upper_bin;
310 double p;
311 double sum = 0;
312 size_t i;
314 if ((lc == NULL) || (lc->num == 0))
315 return (0);
317 if (lower < 1) {
318 //sum += lc->zero;
319 //lower = 1;
320 return (0);
321 }
323 if (upper && (upper < lower))
324 return (0);
326 /* A latency of _exactly_ 1.0 ms should be stored in the buffer 0 */
327 lower_bin = (lower - 1) / lc->bin_width;
329 if (upper)
330 upper_bin = (upper - 1) / lc->bin_width;
331 else
332 upper_bin = HISTOGRAM_NUM_BINS - 1;
334 if (lower_bin >= HISTOGRAM_NUM_BINS)
335 lower_bin = HISTOGRAM_NUM_BINS - 1;
337 if (upper_bin >= HISTOGRAM_NUM_BINS) {
338 upper_bin = HISTOGRAM_NUM_BINS - 1;
339 upper = 0;
340 }
342 ERROR("get_rate (%.3f, %.3f): bin_width = %.3f; "
343 "lower_bin = %"PRIu64" (%.3f); upper_bin = %"PRIu64" (%.3f);",
344 CDTIME_T_TO_DOUBLE (lower),
345 CDTIME_T_TO_DOUBLE (upper),
346 CDTIME_T_TO_DOUBLE (lc->bin_width),
347 lower_bin,
348 CDTIME_T_TO_DOUBLE (lc->bin_width * lower_bin),
349 upper_bin,
350 CDTIME_T_TO_DOUBLE (lc->bin_width * upper_bin)
351 );
353 sum = 0;
354 for (i = lower_bin; i <= upper_bin; i++)
355 {
356 ERROR("SUMM, bin: %d (%.3f), v: %d", i, CDTIME_T_TO_DOUBLE(i * lc->bin_width), lc->histogram[i]);
357 sum += lc->histogram[i];
358 }
359 ERROR("sum before interpolations: %.3f", sum);
361 //v1//p = ((double)lower - (double)(lower_bin + 1) * (double)lc->bin_width) / (double)lc->bin_width;
362 p = ((double)lower - (double)(lower_bin + 0) * (double)lc->bin_width - (double)DOUBLE_TO_CDTIME_T(0.001)) / (double)lc->bin_width;
363 ERROR("interpolation 1: p=%lf, 1=%"PRIu64" (%.3f), 2=%"PRIu64" (%.3f), 3=%"PRIu64" (%.3f); lower_bin: %"PRIu64"",
364 p,
365 //1
366 lower - DOUBLE_TO_CDTIME_T(0.001),
367 CDTIME_T_TO_DOUBLE (lower - (double)DOUBLE_TO_CDTIME_T(0.001)),
368 //2
369 (lower_bin + 0) * lc->bin_width,
370 CDTIME_T_TO_DOUBLE ((lower_bin + 0) * lc->bin_width),
371 //3
372 lc->bin_width,
373 CDTIME_T_TO_DOUBLE (lc->bin_width),
374 lower_bin
375 );
376 sum -= p * lc->histogram[lower_bin];
377 /*
378 if (upper && upper_bin == lower_bin) {
379 //p = ((double)(upper_bin + 1) * (double)lc->bin_width - (double)upper) / (double)lc->bin_width;
380 p = (double)(upper_bin + 1) - (double)upper / (double)lc->bin_width;
381 ERROR("interpolation 2: p=%lf, 1=%"PRIu64" (%.3f), 2=%"PRIu64" (%.3f), 3=%.3f (%.3f); upper_bin: %"PRIu64"",
382 p,
383 //1
384 (upper_bin + 1) * lc->bin_width,
385 CDTIME_T_TO_DOUBLE ((upper_bin + 1) * lc->bin_width),
386 //2
387 upper,
388 CDTIME_T_TO_DOUBLE (upper),
389 //3
390 (double)lc->bin_width,
391 CDTIME_T_TO_DOUBLE (lc->bin_width),
392 upper_bin
393 );
394 sum -= p * lc->histogram[upper_bin];
395 }
396 else
397 */
398 if (upper && upper < (upper_bin + 1) * lc->bin_width)
399 {
400 // p = ((upper_bin + 1) * bin_width - upper ) / bin_width;
402 //p = ((double)upper - (double)(upper_bin + 0) * (double)lc->bin_width) / (double)lc->bin_width;
403 p = ((double)(upper_bin + 1) * (double)lc->bin_width - (double)upper) / (double)lc->bin_width;
404 ERROR("interpolation 3: p=%lf, 1=%"PRIu64" (%.3f), 2=%"PRIu64" (%.3f), 3=%"PRIu64" (%.3f); upper_bin: %"PRIu64"",
405 p,
406 //1
407 (upper_bin + 1) * lc->bin_width,
408 CDTIME_T_TO_DOUBLE ((upper_bin + 1) * lc->bin_width),
409 //2
410 upper,
411 CDTIME_T_TO_DOUBLE (upper),
412 //3
413 lc->bin_width,
414 CDTIME_T_TO_DOUBLE (lc->bin_width),
415 upper_bin
416 );
417 sum -= p * lc->histogram[upper_bin];
418 }
419 return sum / (CDTIME_T_TO_DOUBLE (now - lc->start_time));
421 } /* }}} double latency_counter_get_rate */
424 /* vim: set sw=2 sts=2 et fdm=marker : */