651547ab22af54beebe1cc9ee05d1e3f8b7c56f7
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 "common.h"
30 #include "plugin.h"
31 #include "utils_latency.h"
33 #include <limits.h>
34 #include <math.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 cdtime_t start_time;
52 cdtime_t sum;
53 size_t num;
55 cdtime_t min;
56 cdtime_t max;
58 cdtime_t bin_width;
59 int histogram[HISTOGRAM_NUM_BINS];
60 };
62 /*
63 * Histogram represents the distribution of data, it has a list of "bins".
64 * Each bin represents an interval and has a count (frequency) of
65 * number of values fall within its interval.
66 *
67 * Histogram's range is determined by the number of bins and the bin width,
68 * There are 1000 bins and all bins have the same width of default 1 millisecond.
69 * When a value above this range is added, Histogram's range is increased by
70 * increasing the bin width (note that number of bins remains always at 1000).
71 * This operation of increasing bin width is little expensive as each bin need
72 * to be visited to update it's count. To reduce frequent change of bin width,
73 * new bin width will be the next nearest power of 2. Example: 2, 4, 8, 16, 32,
74 * 64, 128, 256, 512, 1024, 2048, 5086, ...
75 *
76 * So, if the required bin width is 300, then new bin width will be 512 as it is
77 * the next nearest power of 2.
78 */
79 static void change_bin_width(latency_counter_t *lc, cdtime_t latency) /* {{{ */
80 {
81 /* This function is called because the new value is above histogram's range.
82 * First find the required bin width:
83 * requiredBinWidth = (value + 1) / numBins
84 * then get the next nearest power of 2
85 * newBinWidth = 2^(ceil(log2(requiredBinWidth)))
86 */
87 double required_bin_width =
88 ((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 =
91 (cdtime_t)(pow(2.0, ceil(required_bin_width_logbase2)) + .5);
92 cdtime_t old_bin_width = lc->bin_width;
94 lc->bin_width = new_bin_width;
96 /* bin_width has been increased, now iterate through all bins and move the
97 * old bin's count to new bin. */
98 if (lc->num > 0) // if the histogram has data then iterate else skip
99 {
100 double width_change_ratio =
101 ((double)old_bin_width) / ((double)new_bin_width);
103 for (size_t i = 0; i < HISTOGRAM_NUM_BINS; i++) {
104 size_t new_bin = (size_t)(((double)i) * width_change_ratio);
105 if (i == new_bin)
106 continue;
107 assert(new_bin < i);
109 lc->histogram[new_bin] += lc->histogram[i];
110 lc->histogram[i] = 0;
111 }
112 }
114 DEBUG("utils_latency: change_bin_width: latency = %.3f; "
115 "old_bin_width = %.3f; new_bin_width = %.3f;",
116 CDTIME_T_TO_DOUBLE(latency), 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 change_bin_width(lc, latency);
161 bin = (latency - 1) / lc->bin_width;
162 if (bin >= HISTOGRAM_NUM_BINS) {
163 ERROR("utils_latency: latency_counter_add: Invalid bin: %" PRIu64, bin);
164 return;
165 }
166 }
167 lc->histogram[bin]++;
168 } /* }}} void latency_counter_add */
170 void latency_counter_reset(latency_counter_t *lc) /* {{{ */
171 {
172 if (lc == NULL)
173 return;
175 cdtime_t bin_width = lc->bin_width;
176 cdtime_t max_bin = (lc->max - 1) / lc->bin_width;
178 /*
179 If max latency is REDUCE_THRESHOLD times less than histogram's range,
180 then cut it in half. REDUCE_THRESHOLD must be >= 2.
181 Value of 4 is selected to reduce frequent changes of bin width.
182 */
183 #define REDUCE_THRESHOLD 4
184 if ((lc->num > 0) && (lc->bin_width >= HISTOGRAM_DEFAULT_BIN_WIDTH * 2) &&
185 (max_bin < HISTOGRAM_NUM_BINS / REDUCE_THRESHOLD)) {
186 /* new bin width will be the previous power of 2 */
187 bin_width = bin_width / 2;
189 DEBUG("utils_latency: latency_counter_reset: max_latency = %.3f; "
190 "max_bin = %" PRIu64 "; old_bin_width = %.3f; new_bin_width = %.3f;",
191 CDTIME_T_TO_DOUBLE(lc->max), max_bin,
192 CDTIME_T_TO_DOUBLE(lc->bin_width), CDTIME_T_TO_DOUBLE(bin_width));
193 }
195 memset(lc, 0, sizeof(*lc));
197 /* preserve bin width */
198 lc->bin_width = bin_width;
199 lc->start_time = cdtime();
200 } /* }}} void latency_counter_reset */
202 cdtime_t latency_counter_get_min(latency_counter_t *lc) /* {{{ */
203 {
204 if (lc == NULL)
205 return (0);
206 return (lc->min);
207 } /* }}} cdtime_t latency_counter_get_min */
209 cdtime_t latency_counter_get_max(latency_counter_t *lc) /* {{{ */
210 {
211 if (lc == NULL)
212 return (0);
213 return (lc->max);
214 } /* }}} cdtime_t latency_counter_get_max */
216 cdtime_t latency_counter_get_sum(latency_counter_t *lc) /* {{{ */
217 {
218 if (lc == NULL)
219 return (0);
220 return (lc->sum);
221 } /* }}} cdtime_t latency_counter_get_sum */
223 size_t latency_counter_get_num(latency_counter_t *lc) /* {{{ */
224 {
225 if (lc == NULL)
226 return (0);
227 return (lc->num);
228 } /* }}} size_t latency_counter_get_num */
230 cdtime_t latency_counter_get_average(latency_counter_t *lc) /* {{{ */
231 {
232 double average;
234 if ((lc == NULL) || (lc->num == 0))
235 return (0);
237 average = CDTIME_T_TO_DOUBLE(lc->sum) / ((double)lc->num);
238 return (DOUBLE_TO_CDTIME_T(average));
239 } /* }}} cdtime_t latency_counter_get_average */
241 cdtime_t latency_counter_get_percentile(latency_counter_t *lc, /* {{{ */
242 double percent) {
243 double percent_upper;
244 double percent_lower;
245 double p;
246 cdtime_t latency_lower;
247 cdtime_t latency_interpolated;
248 int sum;
249 size_t i;
251 if ((lc == NULL) || (lc->num == 0) || !((percent > 0.0) && (percent < 100.0)))
252 return (0);
254 /* Find index i so that at least "percent" events are within i+1 ms. */
255 percent_upper = 0.0;
256 percent_lower = 0.0;
257 sum = 0;
258 for (i = 0; i < HISTOGRAM_NUM_BINS; i++) {
259 percent_lower = percent_upper;
260 sum += lc->histogram[i];
261 if (sum == 0)
262 percent_upper = 0.0;
263 else
264 percent_upper = 100.0 * ((double)sum) / ((double)lc->num);
266 if (percent_upper >= percent)
267 break;
268 }
270 if (i >= HISTOGRAM_NUM_BINS)
271 return (0);
273 assert(percent_upper >= percent);
274 assert(percent_lower < percent);
276 if (i == 0)
277 return (lc->bin_width);
279 latency_lower = ((cdtime_t)i) * lc->bin_width;
280 p = (percent - percent_lower) / (percent_upper - percent_lower);
282 latency_interpolated =
283 latency_lower + DOUBLE_TO_CDTIME_T(p * CDTIME_T_TO_DOUBLE(lc->bin_width));
285 DEBUG("latency_counter_get_percentile: latency_interpolated = %.3f",
286 CDTIME_T_TO_DOUBLE(latency_interpolated));
287 return (latency_interpolated);
288 } /* }}} cdtime_t latency_counter_get_percentile */
290 /* vim: set sw=2 sts=2 et fdm=marker : */