]>
Commit | Line | Data |
---|---|---|
aed45bef MM |
1 | /* Copyright (c) 2017 Red Hat, Inc. |
2 | * | |
3 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
4 | * you may not use this file except in compliance with the License. | |
5 | * You may obtain a copy of the License at: | |
6 | * | |
7 | * http://www.apache.org/licenses/LICENSE-2.0 | |
8 | * | |
9 | * Unless required by applicable law or agreed to in writing, software | |
10 | * distributed under the License is distributed on an "AS IS" BASIS, | |
11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
12 | * See the License for the specific language governing permissions and | |
13 | * limitations under the License. | |
14 | */ | |
15 | ||
16 | #include <config.h> | |
17 | ||
18 | #include "stopwatch.h" | |
19 | #include "openvswitch/shash.h" | |
20 | #include "openvswitch/vlog.h" | |
21 | #include "unixctl.h" | |
22 | #include "openvswitch/dynamic-string.h" | |
23 | #include "openvswitch/poll-loop.h" | |
24 | #include "ovs-thread.h" | |
25 | #include <unistd.h> | |
26 | #include "socket-util.h" | |
27 | ||
28 | VLOG_DEFINE_THIS_MODULE(stopwatch); | |
29 | ||
30 | struct average { | |
31 | double average; /* Moving average */ | |
32 | double alpha; /* Weight given to new samples */ | |
33 | }; | |
34 | ||
35 | #define MARKERS 5 | |
36 | ||
37 | /* Number of samples to collect before reporting P-square calculated | |
38 | * percentile | |
39 | */ | |
40 | #define P_SQUARE_MIN 50 | |
41 | ||
42 | /* The naming of these fields is based on the naming used in the | |
43 | * P-square algorithm paper. | |
44 | */ | |
45 | struct percentile { | |
46 | int n[MARKERS]; | |
47 | double n_prime[MARKERS]; | |
48 | double q[MARKERS]; | |
49 | double dn[MARKERS]; | |
50 | unsigned long long samples[P_SQUARE_MIN]; | |
51 | double percentile; | |
52 | }; | |
53 | ||
54 | struct stopwatch { | |
55 | enum stopwatch_units units; | |
56 | unsigned long long n_samples; | |
57 | unsigned long long max; | |
58 | unsigned long long min; | |
59 | struct percentile pctl; | |
60 | struct average short_term; | |
61 | struct average long_term; | |
62 | unsigned long long sample_start; | |
63 | bool sample_in_progress; | |
64 | }; | |
65 | ||
66 | enum stopwatch_op { | |
67 | OP_START_SAMPLE, | |
68 | OP_END_SAMPLE, | |
69 | OP_RESET, | |
70 | OP_SHUTDOWN, | |
71 | }; | |
72 | ||
73 | struct stopwatch_packet { | |
74 | enum stopwatch_op op; | |
75 | char name[32]; | |
76 | unsigned long long time; | |
77 | }; | |
78 | ||
79 | static struct shash stopwatches = SHASH_INITIALIZER(&stopwatches); | |
80 | static struct ovs_mutex stopwatches_lock = OVS_MUTEX_INITIALIZER; | |
81 | ||
82 | static int stopwatch_pipe[2]; | |
83 | static pthread_t stopwatch_thread_id; | |
84 | ||
85 | static const char *unit_name[] = { | |
86 | [SW_MS] = "msec", | |
87 | [SW_US] = "usec", | |
88 | [SW_NS] = "nsec", | |
89 | }; | |
90 | ||
91 | /* Percentile value we are calculating */ | |
92 | #define P 0.95 | |
93 | ||
94 | static int | |
95 | comp_samples(const void *left, const void *right) | |
96 | { | |
97 | const double *left_d = left; | |
98 | const double *right_d = right; | |
99 | ||
100 | return (int) *right_d - *left_d; | |
101 | } | |
102 | ||
103 | /* Calculate the percentile using the P-square algorithm. For more | |
104 | * information, see https://www1.cse.wustl.edu/~jain/papers/ftp/psqr.pdf | |
105 | */ | |
106 | static void | |
107 | calc_percentile(unsigned long long n_samples, struct percentile *pctl, | |
108 | unsigned long long new_sample) | |
109 | { | |
110 | ||
111 | if (n_samples < P_SQUARE_MIN) { | |
112 | pctl->samples[n_samples - 1] = new_sample; | |
113 | } | |
114 | ||
115 | /* For the first MARKERS samples, we calculate the percentile | |
116 | * in the traditional way in the pct->q array. | |
117 | */ | |
118 | if (n_samples <= MARKERS) { | |
119 | pctl->q[n_samples - 1] = new_sample; | |
120 | qsort(pctl->q, n_samples, sizeof *pctl->q, comp_samples); | |
121 | if (n_samples == MARKERS) { | |
122 | pctl->n[0] = 0; | |
123 | pctl->n[1] = 1; | |
124 | pctl->n[2] = 2; | |
125 | pctl->n[3] = 3; | |
126 | pctl->n[4] = 4; | |
127 | ||
128 | pctl->n_prime[0] = 0; | |
129 | pctl->n_prime[1] = 2 * P; | |
130 | pctl->n_prime[2] = 4 * P; | |
131 | pctl->n_prime[3] = 2 + 2 * P; | |
132 | pctl->n_prime[4] = 4; | |
133 | ||
134 | pctl->dn[0] = 0; | |
135 | pctl->dn[1] = P / 2; | |
136 | pctl->dn[2] = P; | |
137 | pctl->dn[3] = (1 + P) / 2; | |
138 | pctl->dn[4] = 1; | |
139 | } | |
140 | pctl->percentile = pctl->q[(int) P * n_samples]; | |
141 | return; | |
142 | } | |
143 | ||
144 | /* From here on, update the markers using quadratic spline calculations */ | |
145 | int k; | |
146 | if (new_sample < pctl->q[0]) { | |
147 | k = 0; | |
148 | pctl->q[0] = new_sample; | |
149 | } else if (new_sample < pctl->q[1]) { | |
150 | k = 0; | |
151 | } else if (new_sample < pctl->q[2]) { | |
152 | k = 1; | |
153 | } else if (new_sample < pctl->q[3]) { | |
154 | k = 2; | |
155 | } else if (new_sample <= pctl->q[4]) { | |
156 | k = 3; | |
157 | } else { | |
158 | k = 3; | |
159 | pctl->q[4] = new_sample; | |
160 | } | |
161 | ||
162 | for (int i = k + 1; i < MARKERS; i++) { | |
163 | pctl->n[i]++; | |
164 | } | |
165 | ||
166 | for (int i = 0; i < MARKERS; i++) { | |
167 | pctl->n_prime[i] += pctl->dn[i]; | |
168 | } | |
169 | ||
170 | for (int i = 1; i < MARKERS - 1; i++) { | |
171 | double d = pctl->n_prime[i] - pctl->n[i]; | |
172 | ||
173 | if ((d >= 1 && pctl->n[i + 1] - pctl->n[i] > 1) || | |
174 | (d <= -1 && pctl->n[i - 1] - pctl->n[i] < -1)) { | |
175 | d = d >= 0 ? 1 : -1; | |
176 | ||
177 | double a = d / (pctl->n[i + 1] - pctl->n[i - 1]); | |
178 | double b = (pctl->n[i] - pctl->n[i - 1] + d) * | |
179 | (pctl->q[i + 1] - pctl->q[i]) / (pctl->n[i + 1] - pctl->n[i]); | |
180 | double c = (pctl->n[i + 1] - pctl->n[i] - d) * | |
181 | (pctl->q[i] - pctl->q[i - 1]) / (pctl->n[i] - pctl->n[i - 1]); | |
182 | ||
183 | double candidate = pctl->q[i] + a * (b + c); | |
184 | if (pctl->q[i - 1] < candidate && candidate < pctl->q[i + 1]) { | |
185 | pctl->q[i] = candidate; | |
186 | } else { | |
187 | pctl->q[i] = pctl->q[i] + | |
188 | (d * (pctl->q[i + (int)d] - pctl->q[i]) / | |
189 | (pctl->n[i +(int)d] - pctl->n[i])); | |
190 | } | |
191 | ||
192 | pctl->n[i] += d; | |
193 | } | |
194 | } | |
195 | ||
196 | /* Without enough samples, P-square is not very accurate. Until we reach | |
197 | * P_SQUARE_MIN, use a traditional calculation for the percentile. | |
198 | */ | |
199 | if (n_samples < P_SQUARE_MIN) { | |
200 | qsort(pctl->samples, n_samples, sizeof *pctl->samples, comp_samples); | |
201 | pctl->percentile = pctl->samples[(int) (P * n_samples)]; | |
202 | } else { | |
203 | pctl->percentile = pctl->q[2]; | |
204 | } | |
205 | } | |
206 | ||
207 | static void | |
208 | calc_average(struct average *avg, double new_sample) | |
209 | { | |
210 | avg->average = new_sample * avg->alpha + (1 - avg->alpha) * avg->average; | |
211 | } | |
212 | ||
213 | static void | |
214 | add_sample(struct stopwatch *sw, unsigned long long new_sample) | |
215 | { | |
216 | if (new_sample > sw->max) { | |
217 | sw->max = new_sample; | |
218 | } | |
219 | ||
220 | if (new_sample < sw->min || sw->n_samples == 0) { | |
221 | sw->min = new_sample; | |
222 | } | |
223 | ||
224 | calc_percentile(sw->n_samples, &sw->pctl, new_sample); | |
225 | ||
226 | if (sw->n_samples++ == 0) { | |
227 | sw->short_term.average = sw->long_term.average = new_sample; | |
228 | return; | |
229 | } | |
230 | ||
231 | calc_average(&sw->short_term, new_sample); | |
232 | calc_average(&sw->long_term, new_sample); | |
233 | } | |
234 | ||
235 | static void | |
236 | stopwatch_print(struct stopwatch *sw, const char *name, | |
237 | struct ds *s) | |
238 | { | |
239 | ds_put_format(s, "Statistics for '%s'\n", name); | |
240 | ||
241 | const char *units = unit_name[sw->units]; | |
242 | ds_put_format(s, "\t Total samples: %llu\n", sw->n_samples); | |
243 | ds_put_format(s, "\t Maximum: %llu %s\n", sw->max, units); | |
244 | ds_put_format(s, "\t Minimum: %llu %s\n", sw->min, units); | |
245 | ds_put_format(s, "\t 95th percentile: %f %s\n", | |
246 | sw->pctl.percentile, units); | |
247 | ds_put_format(s, "\t Short term average: %f %s\n", | |
248 | sw->short_term.average, units); | |
249 | ds_put_format(s, "\t Long term average: %f %s\n", | |
250 | sw->long_term.average, units); | |
251 | } | |
252 | ||
253 | static bool | |
254 | stopwatch_show_protected(int argc, const char *argv[], struct ds *s) | |
255 | { | |
256 | struct stopwatch *sw; | |
257 | ||
258 | if (argc > 1) { | |
259 | sw = shash_find_data(&stopwatches, argv[1]); | |
260 | if (!sw) { | |
261 | ds_put_cstr(s, "No such stopwatch"); | |
262 | return false; | |
263 | } | |
264 | stopwatch_print(sw, argv[1], s); | |
265 | } else { | |
266 | struct shash_node *node; | |
267 | SHASH_FOR_EACH (node, &stopwatches) { | |
268 | sw = node->data; | |
269 | stopwatch_print(sw, node->name, s); | |
270 | } | |
271 | } | |
272 | ||
273 | return true; | |
274 | } | |
275 | ||
276 | static void | |
277 | stopwatch_show(struct unixctl_conn *conn, int argc OVS_UNUSED, | |
278 | const char *argv[], void *ignore OVS_UNUSED) | |
279 | { | |
280 | struct ds s = DS_EMPTY_INITIALIZER; | |
281 | bool success; | |
282 | ||
283 | ovs_mutex_lock(&stopwatches_lock); | |
284 | success = stopwatch_show_protected(argc, argv, &s); | |
285 | ovs_mutex_unlock(&stopwatches_lock); | |
286 | ||
287 | if (success) { | |
288 | unixctl_command_reply(conn, ds_cstr(&s)); | |
289 | } else { | |
290 | unixctl_command_reply_error(conn, ds_cstr(&s)); | |
291 | } | |
292 | ds_destroy(&s); | |
293 | } | |
294 | ||
295 | static void | |
296 | stopwatch_reset(struct unixctl_conn *conn, int argc OVS_UNUSED, | |
297 | const char *argv[], void *ignore OVS_UNUSED) | |
298 | { | |
299 | struct stopwatch_packet pkt = { | |
300 | .op = OP_RESET, | |
301 | }; | |
302 | if (argc > 1) { | |
303 | ovs_strlcpy(pkt.name, argv[1], sizeof(pkt.name)); | |
304 | } | |
305 | write(stopwatch_pipe[1], &pkt, sizeof(pkt)); | |
306 | unixctl_command_reply(conn, ""); | |
307 | } | |
308 | ||
309 | static void | |
310 | stopwatch_start_sample_protected(const struct stopwatch_packet *pkt) | |
311 | { | |
312 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
313 | if (!sw || sw->sample_in_progress) { | |
314 | return; | |
315 | } | |
316 | ||
317 | sw->sample_start = pkt->time; | |
318 | sw->sample_in_progress = true; | |
319 | } | |
320 | ||
321 | static void | |
322 | stopwatch_end_sample_protected(const struct stopwatch_packet *pkt) | |
323 | { | |
324 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
325 | if (!sw || !sw->sample_in_progress) { | |
326 | return; | |
327 | } | |
328 | ||
329 | add_sample(sw, pkt->time - sw->sample_start); | |
330 | sw->sample_in_progress = false; | |
331 | } | |
332 | ||
333 | static void reset_stopwatch(struct stopwatch *sw) | |
334 | { | |
335 | sw->short_term.average = 0; | |
336 | sw->long_term.average = 0; | |
337 | sw->pctl.percentile = 0; | |
338 | sw->n_samples = 0; | |
339 | sw->max = 0; | |
340 | sw->min = 0; | |
341 | /* Don't reset sw->sample_start or sw->sample_in_progress. | |
342 | * This way, if a sample was currently in progress, it can be | |
343 | * concluded properly after the reset. | |
344 | */ | |
345 | } | |
346 | ||
347 | static void | |
348 | stopwatch_reset_protected(const struct stopwatch_packet *pkt) | |
349 | { | |
350 | if (pkt->name[0]) { | |
351 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
352 | if (!sw) { | |
353 | return; | |
354 | } | |
355 | reset_stopwatch(sw); | |
356 | return; | |
357 | } | |
358 | ||
359 | struct shash_node *node; | |
360 | SHASH_FOR_EACH (node, &stopwatches) { | |
361 | struct stopwatch *sw = node->data; | |
362 | reset_stopwatch(sw); | |
363 | } | |
364 | } | |
365 | ||
366 | static void * | |
367 | stopwatch_thread(void *ign OVS_UNUSED) | |
368 | { | |
369 | bool should_exit = false; | |
370 | ||
371 | while (!should_exit) { | |
372 | struct stopwatch_packet pkt; | |
373 | while (read(stopwatch_pipe[0], &pkt, sizeof(pkt)) > 0) { | |
374 | ovs_mutex_lock(&stopwatches_lock); | |
375 | switch (pkt.op) { | |
376 | case OP_START_SAMPLE: | |
377 | stopwatch_start_sample_protected(&pkt); | |
378 | break; | |
379 | case OP_END_SAMPLE: | |
380 | stopwatch_end_sample_protected(&pkt); | |
381 | break; | |
382 | case OP_RESET: | |
383 | stopwatch_reset_protected(&pkt); | |
384 | break; | |
385 | case OP_SHUTDOWN: | |
386 | should_exit = true; | |
387 | break; | |
388 | } | |
389 | ovs_mutex_unlock(&stopwatches_lock); | |
390 | } | |
391 | ||
392 | if (!should_exit) { | |
393 | poll_fd_wait(stopwatch_pipe[0], POLLIN); | |
394 | poll_block(); | |
395 | } | |
396 | } | |
397 | ||
398 | return NULL; | |
399 | } | |
400 | ||
401 | static void | |
402 | stopwatch_exit(void) | |
403 | { | |
404 | struct shash_node *node, *node_next; | |
405 | struct stopwatch_packet pkt = { | |
406 | .op = OP_SHUTDOWN, | |
407 | }; | |
408 | ||
409 | write(stopwatch_pipe[1], &pkt, sizeof pkt); | |
410 | xpthread_join(stopwatch_thread_id, NULL); | |
411 | ||
412 | /* Process is exiting and we have joined the only | |
413 | * other competing thread. We are now the sole owners | |
414 | * of all data in the file. | |
415 | */ | |
416 | SHASH_FOR_EACH_SAFE (node, node_next, &stopwatches) { | |
417 | struct stopwatch *sw = node->data; | |
418 | shash_delete(&stopwatches, node); | |
419 | free(sw); | |
420 | } | |
421 | shash_destroy(&stopwatches); | |
422 | ovs_mutex_destroy(&stopwatches_lock); | |
423 | } | |
424 | ||
425 | static void | |
426 | do_init_stopwatch(void) | |
427 | { | |
428 | unixctl_command_register("stopwatch/show", "[NAME]", 0, 1, | |
429 | stopwatch_show, NULL); | |
430 | unixctl_command_register("stopwatch/reset", "[NAME]", 0, 1, | |
431 | stopwatch_reset, NULL); | |
432 | xpipe_nonblocking(stopwatch_pipe); | |
433 | stopwatch_thread_id = ovs_thread_create( | |
434 | "stopwatch", stopwatch_thread, NULL); | |
435 | atexit(stopwatch_exit); | |
436 | } | |
437 | ||
438 | static void | |
439 | stopwatch_init(void) | |
440 | { | |
441 | static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER; | |
442 | if (ovsthread_once_start(&once)) { | |
443 | do_init_stopwatch(); | |
444 | ovsthread_once_done(&once); | |
445 | } | |
446 | } | |
447 | ||
448 | void | |
449 | stopwatch_create(const char *name, enum stopwatch_units units) | |
450 | { | |
451 | stopwatch_init(); | |
452 | ||
453 | struct stopwatch *sw = xzalloc(sizeof *sw); | |
454 | sw->units = units; | |
455 | sw->short_term.alpha = 0.50; | |
456 | sw->long_term.alpha = 0.01; | |
457 | ||
458 | ovs_mutex_lock(&stopwatches_lock); | |
459 | shash_add(&stopwatches, name, sw); | |
460 | ovs_mutex_unlock(&stopwatches_lock); | |
461 | } | |
462 | ||
463 | void | |
464 | stopwatch_start(const char *name, unsigned long long ts) | |
465 | { | |
466 | struct stopwatch_packet pkt = { | |
467 | .op = OP_START_SAMPLE, | |
468 | .time = ts, | |
469 | }; | |
470 | ovs_strlcpy(pkt.name, name, sizeof(pkt.name)); | |
471 | write(stopwatch_pipe[1], &pkt, sizeof(pkt)); | |
472 | } | |
473 | ||
474 | void | |
475 | stopwatch_stop(const char *name, unsigned long long ts) | |
476 | { | |
477 | struct stopwatch_packet pkt = { | |
478 | .op = OP_END_SAMPLE, | |
479 | .time = ts, | |
480 | }; | |
481 | ovs_strlcpy(pkt.name, name, sizeof(pkt.name)); | |
482 | write(stopwatch_pipe[1], &pkt, sizeof(pkt)); | |
483 | } |