]>
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" | |
098ab9f1 | 27 | #include "util.h" |
484f7dbd MM |
28 | #include "latch.h" |
29 | #include "guarded-list.h" | |
aed45bef MM |
30 | |
31 | VLOG_DEFINE_THIS_MODULE(stopwatch); | |
32 | ||
33 | struct average { | |
34 | double average; /* Moving average */ | |
35 | double alpha; /* Weight given to new samples */ | |
36 | }; | |
37 | ||
38 | #define MARKERS 5 | |
39 | ||
40 | /* Number of samples to collect before reporting P-square calculated | |
41 | * percentile | |
42 | */ | |
43 | #define P_SQUARE_MIN 50 | |
44 | ||
45 | /* The naming of these fields is based on the naming used in the | |
46 | * P-square algorithm paper. | |
47 | */ | |
48 | struct percentile { | |
49 | int n[MARKERS]; | |
50 | double n_prime[MARKERS]; | |
51 | double q[MARKERS]; | |
52 | double dn[MARKERS]; | |
53 | unsigned long long samples[P_SQUARE_MIN]; | |
54 | double percentile; | |
55 | }; | |
56 | ||
57 | struct stopwatch { | |
58 | enum stopwatch_units units; | |
59 | unsigned long long n_samples; | |
60 | unsigned long long max; | |
61 | unsigned long long min; | |
62 | struct percentile pctl; | |
63 | struct average short_term; | |
64 | struct average long_term; | |
65 | unsigned long long sample_start; | |
66 | bool sample_in_progress; | |
67 | }; | |
68 | ||
69 | enum stopwatch_op { | |
70 | OP_START_SAMPLE, | |
71 | OP_END_SAMPLE, | |
0e124db8 | 72 | OP_SYNC, |
aed45bef MM |
73 | OP_RESET, |
74 | OP_SHUTDOWN, | |
75 | }; | |
76 | ||
77 | struct stopwatch_packet { | |
484f7dbd | 78 | struct ovs_list list_node; |
aed45bef MM |
79 | enum stopwatch_op op; |
80 | char name[32]; | |
81 | unsigned long long time; | |
82 | }; | |
83 | ||
84 | static struct shash stopwatches = SHASH_INITIALIZER(&stopwatches); | |
85 | static struct ovs_mutex stopwatches_lock = OVS_MUTEX_INITIALIZER; | |
0e124db8 | 86 | static pthread_cond_t stopwatches_sync = PTHREAD_COND_INITIALIZER; |
aed45bef | 87 | |
484f7dbd MM |
88 | static struct latch stopwatch_latch; |
89 | static struct guarded_list stopwatch_commands; | |
aed45bef MM |
90 | static pthread_t stopwatch_thread_id; |
91 | ||
92 | static const char *unit_name[] = { | |
93 | [SW_MS] = "msec", | |
94 | [SW_US] = "usec", | |
95 | [SW_NS] = "nsec", | |
96 | }; | |
97 | ||
98 | /* Percentile value we are calculating */ | |
99 | #define P 0.95 | |
100 | ||
101 | static int | |
102 | comp_samples(const void *left, const void *right) | |
103 | { | |
104 | const double *left_d = left; | |
105 | const double *right_d = right; | |
106 | ||
ea2b6223 | 107 | return *right_d > *left_d ? -1 : *right_d < *left_d; |
aed45bef MM |
108 | } |
109 | ||
110 | /* Calculate the percentile using the P-square algorithm. For more | |
111 | * information, see https://www1.cse.wustl.edu/~jain/papers/ftp/psqr.pdf | |
112 | */ | |
113 | static void | |
114 | calc_percentile(unsigned long long n_samples, struct percentile *pctl, | |
115 | unsigned long long new_sample) | |
116 | { | |
117 | ||
118 | if (n_samples < P_SQUARE_MIN) { | |
119 | pctl->samples[n_samples - 1] = new_sample; | |
120 | } | |
121 | ||
122 | /* For the first MARKERS samples, we calculate the percentile | |
123 | * in the traditional way in the pct->q array. | |
124 | */ | |
125 | if (n_samples <= MARKERS) { | |
126 | pctl->q[n_samples - 1] = new_sample; | |
127 | qsort(pctl->q, n_samples, sizeof *pctl->q, comp_samples); | |
128 | if (n_samples == MARKERS) { | |
129 | pctl->n[0] = 0; | |
130 | pctl->n[1] = 1; | |
131 | pctl->n[2] = 2; | |
132 | pctl->n[3] = 3; | |
133 | pctl->n[4] = 4; | |
134 | ||
135 | pctl->n_prime[0] = 0; | |
136 | pctl->n_prime[1] = 2 * P; | |
137 | pctl->n_prime[2] = 4 * P; | |
138 | pctl->n_prime[3] = 2 + 2 * P; | |
139 | pctl->n_prime[4] = 4; | |
140 | ||
141 | pctl->dn[0] = 0; | |
142 | pctl->dn[1] = P / 2; | |
143 | pctl->dn[2] = P; | |
144 | pctl->dn[3] = (1 + P) / 2; | |
145 | pctl->dn[4] = 1; | |
146 | } | |
147 | pctl->percentile = pctl->q[(int) P * n_samples]; | |
148 | return; | |
149 | } | |
150 | ||
151 | /* From here on, update the markers using quadratic spline calculations */ | |
152 | int k; | |
153 | if (new_sample < pctl->q[0]) { | |
154 | k = 0; | |
155 | pctl->q[0] = new_sample; | |
156 | } else if (new_sample < pctl->q[1]) { | |
157 | k = 0; | |
158 | } else if (new_sample < pctl->q[2]) { | |
159 | k = 1; | |
160 | } else if (new_sample < pctl->q[3]) { | |
161 | k = 2; | |
162 | } else if (new_sample <= pctl->q[4]) { | |
163 | k = 3; | |
164 | } else { | |
165 | k = 3; | |
166 | pctl->q[4] = new_sample; | |
167 | } | |
168 | ||
169 | for (int i = k + 1; i < MARKERS; i++) { | |
170 | pctl->n[i]++; | |
171 | } | |
172 | ||
173 | for (int i = 0; i < MARKERS; i++) { | |
174 | pctl->n_prime[i] += pctl->dn[i]; | |
175 | } | |
176 | ||
177 | for (int i = 1; i < MARKERS - 1; i++) { | |
178 | double d = pctl->n_prime[i] - pctl->n[i]; | |
179 | ||
180 | if ((d >= 1 && pctl->n[i + 1] - pctl->n[i] > 1) || | |
181 | (d <= -1 && pctl->n[i - 1] - pctl->n[i] < -1)) { | |
182 | d = d >= 0 ? 1 : -1; | |
183 | ||
184 | double a = d / (pctl->n[i + 1] - pctl->n[i - 1]); | |
185 | double b = (pctl->n[i] - pctl->n[i - 1] + d) * | |
186 | (pctl->q[i + 1] - pctl->q[i]) / (pctl->n[i + 1] - pctl->n[i]); | |
187 | double c = (pctl->n[i + 1] - pctl->n[i] - d) * | |
188 | (pctl->q[i] - pctl->q[i - 1]) / (pctl->n[i] - pctl->n[i - 1]); | |
189 | ||
190 | double candidate = pctl->q[i] + a * (b + c); | |
191 | if (pctl->q[i - 1] < candidate && candidate < pctl->q[i + 1]) { | |
192 | pctl->q[i] = candidate; | |
193 | } else { | |
194 | pctl->q[i] = pctl->q[i] + | |
195 | (d * (pctl->q[i + (int)d] - pctl->q[i]) / | |
196 | (pctl->n[i +(int)d] - pctl->n[i])); | |
197 | } | |
198 | ||
199 | pctl->n[i] += d; | |
200 | } | |
201 | } | |
202 | ||
203 | /* Without enough samples, P-square is not very accurate. Until we reach | |
204 | * P_SQUARE_MIN, use a traditional calculation for the percentile. | |
205 | */ | |
206 | if (n_samples < P_SQUARE_MIN) { | |
207 | qsort(pctl->samples, n_samples, sizeof *pctl->samples, comp_samples); | |
208 | pctl->percentile = pctl->samples[(int) (P * n_samples)]; | |
209 | } else { | |
210 | pctl->percentile = pctl->q[2]; | |
211 | } | |
212 | } | |
213 | ||
214 | static void | |
215 | calc_average(struct average *avg, double new_sample) | |
216 | { | |
217 | avg->average = new_sample * avg->alpha + (1 - avg->alpha) * avg->average; | |
218 | } | |
219 | ||
220 | static void | |
221 | add_sample(struct stopwatch *sw, unsigned long long new_sample) | |
222 | { | |
223 | if (new_sample > sw->max) { | |
224 | sw->max = new_sample; | |
225 | } | |
226 | ||
227 | if (new_sample < sw->min || sw->n_samples == 0) { | |
228 | sw->min = new_sample; | |
229 | } | |
230 | ||
231 | calc_percentile(sw->n_samples, &sw->pctl, new_sample); | |
232 | ||
233 | if (sw->n_samples++ == 0) { | |
234 | sw->short_term.average = sw->long_term.average = new_sample; | |
235 | return; | |
236 | } | |
237 | ||
238 | calc_average(&sw->short_term, new_sample); | |
239 | calc_average(&sw->long_term, new_sample); | |
240 | } | |
241 | ||
89189388 | 242 | static bool |
0e124db8 | 243 | stopwatch_get_stats_protected(const char *name, |
463ec406 | 244 | struct stopwatch_stats *stats) |
89189388 | 245 | { |
0e124db8 | 246 | struct stopwatch *perf; |
89189388 | 247 | |
0e124db8 | 248 | perf = shash_find_data(&stopwatches, name); |
89189388 JS |
249 | if (!perf) { |
250 | return false; | |
251 | } | |
252 | ||
44c82814 | 253 | stats->count = perf->n_samples; |
89189388 JS |
254 | stats->unit = perf->units; |
255 | stats->max = perf->max; | |
256 | stats->min = perf->min; | |
257 | stats->pctl_95 = perf->pctl.percentile; | |
258 | stats->ewma_50 = perf->short_term.average; | |
259 | stats->ewma_1 = perf->long_term.average; | |
260 | ||
261 | return true; | |
262 | } | |
263 | ||
264 | bool | |
0e124db8 | 265 | stopwatch_get_stats(const char *name, struct stopwatch_stats *stats) |
89189388 JS |
266 | { |
267 | bool found = false; | |
268 | ||
0e124db8 JS |
269 | ovs_mutex_lock(&stopwatches_lock); |
270 | found = stopwatch_get_stats_protected(name, stats); | |
271 | ovs_mutex_unlock(&stopwatches_lock); | |
89189388 JS |
272 | |
273 | return found; | |
274 | } | |
275 | ||
aed45bef MM |
276 | static void |
277 | stopwatch_print(struct stopwatch *sw, const char *name, | |
278 | struct ds *s) | |
279 | { | |
280 | ds_put_format(s, "Statistics for '%s'\n", name); | |
281 | ||
282 | const char *units = unit_name[sw->units]; | |
957ee508 BP |
283 | ds_put_format(s, " Total samples: %llu\n", sw->n_samples); |
284 | ds_put_format(s, " Maximum: %llu %s\n", sw->max, units); | |
285 | ds_put_format(s, " Minimum: %llu %s\n", sw->min, units); | |
286 | ds_put_format(s, " 95th percentile: %f %s\n", | |
aed45bef | 287 | sw->pctl.percentile, units); |
957ee508 | 288 | ds_put_format(s, " Short term average: %f %s\n", |
aed45bef | 289 | sw->short_term.average, units); |
957ee508 | 290 | ds_put_format(s, " Long term average: %f %s\n", |
aed45bef MM |
291 | sw->long_term.average, units); |
292 | } | |
293 | ||
294 | static bool | |
295 | stopwatch_show_protected(int argc, const char *argv[], struct ds *s) | |
296 | { | |
297 | struct stopwatch *sw; | |
298 | ||
299 | if (argc > 1) { | |
300 | sw = shash_find_data(&stopwatches, argv[1]); | |
301 | if (!sw) { | |
302 | ds_put_cstr(s, "No such stopwatch"); | |
303 | return false; | |
304 | } | |
305 | stopwatch_print(sw, argv[1], s); | |
306 | } else { | |
307 | struct shash_node *node; | |
308 | SHASH_FOR_EACH (node, &stopwatches) { | |
309 | sw = node->data; | |
310 | stopwatch_print(sw, node->name, s); | |
311 | } | |
312 | } | |
313 | ||
314 | return true; | |
315 | } | |
316 | ||
317 | static void | |
318 | stopwatch_show(struct unixctl_conn *conn, int argc OVS_UNUSED, | |
463ec406 | 319 | const char *argv[], void *aux OVS_UNUSED) |
aed45bef MM |
320 | { |
321 | struct ds s = DS_EMPTY_INITIALIZER; | |
322 | bool success; | |
323 | ||
324 | ovs_mutex_lock(&stopwatches_lock); | |
325 | success = stopwatch_show_protected(argc, argv, &s); | |
326 | ovs_mutex_unlock(&stopwatches_lock); | |
327 | ||
328 | if (success) { | |
329 | unixctl_command_reply(conn, ds_cstr(&s)); | |
330 | } else { | |
331 | unixctl_command_reply_error(conn, ds_cstr(&s)); | |
332 | } | |
333 | ds_destroy(&s); | |
334 | } | |
335 | ||
484f7dbd MM |
336 | static struct stopwatch_packet * |
337 | stopwatch_packet_create(enum stopwatch_op op) | |
338 | { | |
339 | struct stopwatch_packet *pkt; | |
340 | ||
341 | pkt = xzalloc(sizeof *pkt); | |
342 | pkt->op = op; | |
343 | ||
344 | return pkt; | |
345 | } | |
346 | ||
347 | static void | |
348 | stopwatch_packet_write(struct stopwatch_packet *pkt) | |
349 | { | |
350 | guarded_list_push_back(&stopwatch_commands, &pkt->list_node, SIZE_MAX); | |
351 | latch_set(&stopwatch_latch); | |
352 | } | |
353 | ||
aed45bef MM |
354 | static void |
355 | stopwatch_reset(struct unixctl_conn *conn, int argc OVS_UNUSED, | |
463ec406 | 356 | const char *argv[], void *aux OVS_UNUSED) |
aed45bef | 357 | { |
484f7dbd | 358 | struct stopwatch_packet *pkt = stopwatch_packet_create(OP_RESET); |
aed45bef | 359 | if (argc > 1) { |
484f7dbd | 360 | ovs_strlcpy(pkt->name, argv[1], sizeof pkt->name); |
aed45bef | 361 | } |
484f7dbd | 362 | stopwatch_packet_write(pkt); |
aed45bef MM |
363 | unixctl_command_reply(conn, ""); |
364 | } | |
365 | ||
366 | static void | |
367 | stopwatch_start_sample_protected(const struct stopwatch_packet *pkt) | |
368 | { | |
369 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
370 | if (!sw || sw->sample_in_progress) { | |
371 | return; | |
372 | } | |
373 | ||
374 | sw->sample_start = pkt->time; | |
375 | sw->sample_in_progress = true; | |
376 | } | |
377 | ||
378 | static void | |
379 | stopwatch_end_sample_protected(const struct stopwatch_packet *pkt) | |
380 | { | |
381 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
382 | if (!sw || !sw->sample_in_progress) { | |
383 | return; | |
384 | } | |
385 | ||
386 | add_sample(sw, pkt->time - sw->sample_start); | |
387 | sw->sample_in_progress = false; | |
388 | } | |
389 | ||
390 | static void reset_stopwatch(struct stopwatch *sw) | |
391 | { | |
392 | sw->short_term.average = 0; | |
393 | sw->long_term.average = 0; | |
394 | sw->pctl.percentile = 0; | |
395 | sw->n_samples = 0; | |
396 | sw->max = 0; | |
397 | sw->min = 0; | |
398 | /* Don't reset sw->sample_start or sw->sample_in_progress. | |
399 | * This way, if a sample was currently in progress, it can be | |
400 | * concluded properly after the reset. | |
401 | */ | |
402 | } | |
403 | ||
404 | static void | |
405 | stopwatch_reset_protected(const struct stopwatch_packet *pkt) | |
406 | { | |
407 | if (pkt->name[0]) { | |
408 | struct stopwatch *sw = shash_find_data(&stopwatches, pkt->name); | |
409 | if (!sw) { | |
410 | return; | |
411 | } | |
412 | reset_stopwatch(sw); | |
413 | return; | |
414 | } | |
415 | ||
416 | struct shash_node *node; | |
417 | SHASH_FOR_EACH (node, &stopwatches) { | |
418 | struct stopwatch *sw = node->data; | |
419 | reset_stopwatch(sw); | |
420 | } | |
421 | } | |
422 | ||
423 | static void * | |
424 | stopwatch_thread(void *ign OVS_UNUSED) | |
425 | { | |
426 | bool should_exit = false; | |
427 | ||
428 | while (!should_exit) { | |
484f7dbd MM |
429 | struct ovs_list command_list; |
430 | struct stopwatch_packet *pkt; | |
431 | ||
0f3d9fb4 | 432 | latch_poll(&stopwatch_latch); |
484f7dbd MM |
433 | guarded_list_pop_all(&stopwatch_commands, &command_list); |
434 | ovs_mutex_lock(&stopwatches_lock); | |
435 | LIST_FOR_EACH_POP (pkt, list_node, &command_list) { | |
436 | switch (pkt->op) { | |
aed45bef | 437 | case OP_START_SAMPLE: |
484f7dbd | 438 | stopwatch_start_sample_protected(pkt); |
aed45bef MM |
439 | break; |
440 | case OP_END_SAMPLE: | |
484f7dbd | 441 | stopwatch_end_sample_protected(pkt); |
aed45bef | 442 | break; |
0e124db8 JS |
443 | case OP_SYNC: |
444 | xpthread_cond_signal(&stopwatches_sync); | |
445 | break; | |
aed45bef | 446 | case OP_RESET: |
484f7dbd | 447 | stopwatch_reset_protected(pkt); |
aed45bef MM |
448 | break; |
449 | case OP_SHUTDOWN: | |
450 | should_exit = true; | |
451 | break; | |
452 | } | |
294637e9 | 453 | free(pkt); |
aed45bef | 454 | } |
484f7dbd | 455 | ovs_mutex_unlock(&stopwatches_lock); |
aed45bef MM |
456 | |
457 | if (!should_exit) { | |
484f7dbd | 458 | latch_wait(&stopwatch_latch); |
aed45bef MM |
459 | poll_block(); |
460 | } | |
461 | } | |
462 | ||
463 | return NULL; | |
464 | } | |
465 | ||
466 | static void | |
467 | stopwatch_exit(void) | |
468 | { | |
469 | struct shash_node *node, *node_next; | |
484f7dbd MM |
470 | struct stopwatch_packet *pkt = stopwatch_packet_create(OP_SHUTDOWN); |
471 | stopwatch_packet_write(pkt); | |
aed45bef MM |
472 | xpthread_join(stopwatch_thread_id, NULL); |
473 | ||
474 | /* Process is exiting and we have joined the only | |
475 | * other competing thread. We are now the sole owners | |
476 | * of all data in the file. | |
477 | */ | |
478 | SHASH_FOR_EACH_SAFE (node, node_next, &stopwatches) { | |
479 | struct stopwatch *sw = node->data; | |
480 | shash_delete(&stopwatches, node); | |
481 | free(sw); | |
482 | } | |
483 | shash_destroy(&stopwatches); | |
484 | ovs_mutex_destroy(&stopwatches_lock); | |
484f7dbd MM |
485 | guarded_list_destroy(&stopwatch_commands); |
486 | latch_destroy(&stopwatch_latch); | |
aed45bef MM |
487 | } |
488 | ||
489 | static void | |
490 | do_init_stopwatch(void) | |
491 | { | |
492 | unixctl_command_register("stopwatch/show", "[NAME]", 0, 1, | |
493 | stopwatch_show, NULL); | |
494 | unixctl_command_register("stopwatch/reset", "[NAME]", 0, 1, | |
495 | stopwatch_reset, NULL); | |
484f7dbd MM |
496 | guarded_list_init(&stopwatch_commands); |
497 | latch_init(&stopwatch_latch); | |
aed45bef MM |
498 | stopwatch_thread_id = ovs_thread_create( |
499 | "stopwatch", stopwatch_thread, NULL); | |
500 | atexit(stopwatch_exit); | |
501 | } | |
502 | ||
503 | static void | |
504 | stopwatch_init(void) | |
505 | { | |
506 | static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER; | |
507 | if (ovsthread_once_start(&once)) { | |
508 | do_init_stopwatch(); | |
509 | ovsthread_once_done(&once); | |
510 | } | |
511 | } | |
512 | ||
513 | void | |
514 | stopwatch_create(const char *name, enum stopwatch_units units) | |
515 | { | |
516 | stopwatch_init(); | |
517 | ||
518 | struct stopwatch *sw = xzalloc(sizeof *sw); | |
519 | sw->units = units; | |
520 | sw->short_term.alpha = 0.50; | |
521 | sw->long_term.alpha = 0.01; | |
522 | ||
523 | ovs_mutex_lock(&stopwatches_lock); | |
524 | shash_add(&stopwatches, name, sw); | |
525 | ovs_mutex_unlock(&stopwatches_lock); | |
526 | } | |
527 | ||
528 | void | |
529 | stopwatch_start(const char *name, unsigned long long ts) | |
530 | { | |
484f7dbd MM |
531 | struct stopwatch_packet *pkt = stopwatch_packet_create(OP_START_SAMPLE); |
532 | ovs_strlcpy(pkt->name, name, sizeof pkt->name); | |
533 | pkt->time = ts; | |
534 | stopwatch_packet_write(pkt); | |
aed45bef MM |
535 | } |
536 | ||
537 | void | |
538 | stopwatch_stop(const char *name, unsigned long long ts) | |
539 | { | |
484f7dbd MM |
540 | struct stopwatch_packet *pkt = stopwatch_packet_create(OP_END_SAMPLE); |
541 | ovs_strlcpy(pkt->name, name, sizeof pkt->name); | |
542 | pkt->time = ts; | |
543 | stopwatch_packet_write(pkt); | |
aed45bef | 544 | } |
0e124db8 JS |
545 | |
546 | void | |
547 | stopwatch_sync(void) | |
548 | { | |
484f7dbd | 549 | struct stopwatch_packet *pkt = stopwatch_packet_create(OP_SYNC); |
0e124db8 | 550 | ovs_mutex_lock(&stopwatches_lock); |
484f7dbd | 551 | stopwatch_packet_write(pkt); |
0e124db8 JS |
552 | ovs_mutex_cond_wait(&stopwatches_sync, &stopwatches_lock); |
553 | ovs_mutex_unlock(&stopwatches_lock); | |
554 | } |