1 /* Copyright (c) 2017 Red Hat, Inc.
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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "stopwatch.h"
19 #include "openvswitch/shash.h"
20 #include "openvswitch/vlog.h"
22 #include "openvswitch/dynamic-string.h"
23 #include "openvswitch/poll-loop.h"
24 #include "ovs-thread.h"
26 #include "socket-util.h"
29 #include "guarded-list.h"
31 VLOG_DEFINE_THIS_MODULE(stopwatch
);
34 double average
; /* Moving average */
35 double alpha
; /* Weight given to new samples */
40 /* Number of samples to collect before reporting P-square calculated
43 #define P_SQUARE_MIN 50
45 /* The naming of these fields is based on the naming used in the
46 * P-square algorithm paper.
50 double n_prime
[MARKERS
];
53 unsigned long long samples
[P_SQUARE_MIN
];
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
;
77 struct stopwatch_packet
{
78 struct ovs_list list_node
;
81 unsigned long long time
;
84 static struct shash stopwatches
= SHASH_INITIALIZER(&stopwatches
);
85 static struct ovs_mutex stopwatches_lock
= OVS_MUTEX_INITIALIZER
;
86 static pthread_cond_t stopwatches_sync
= PTHREAD_COND_INITIALIZER
;
88 static struct latch stopwatch_latch
;
89 static struct guarded_list stopwatch_commands
;
90 static pthread_t stopwatch_thread_id
;
92 static const char *unit_name
[] = {
98 /* Percentile value we are calculating */
102 comp_samples(const void *left
, const void *right
)
104 const double *left_d
= left
;
105 const double *right_d
= right
;
107 return (int) *right_d
- *left_d
;
110 /* Calculate the percentile using the P-square algorithm. For more
111 * information, see https://www1.cse.wustl.edu/~jain/papers/ftp/psqr.pdf
114 calc_percentile(unsigned long long n_samples
, struct percentile
*pctl
,
115 unsigned long long new_sample
)
118 if (n_samples
< P_SQUARE_MIN
) {
119 pctl
->samples
[n_samples
- 1] = new_sample
;
122 /* For the first MARKERS samples, we calculate the percentile
123 * in the traditional way in the pct->q array.
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
) {
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;
144 pctl
->dn
[3] = (1 + P
) / 2;
147 pctl
->percentile
= pctl
->q
[(int) P
* n_samples
];
151 /* From here on, update the markers using quadratic spline calculations */
153 if (new_sample
< pctl
->q
[0]) {
155 pctl
->q
[0] = new_sample
;
156 } else if (new_sample
< pctl
->q
[1]) {
158 } else if (new_sample
< pctl
->q
[2]) {
160 } else if (new_sample
< pctl
->q
[3]) {
162 } else if (new_sample
<= pctl
->q
[4]) {
166 pctl
->q
[4] = new_sample
;
169 for (int i
= k
+ 1; i
< MARKERS
; i
++) {
173 for (int i
= 0; i
< MARKERS
; i
++) {
174 pctl
->n_prime
[i
] += pctl
->dn
[i
];
177 for (int i
= 1; i
< MARKERS
- 1; i
++) {
178 double d
= pctl
->n_prime
[i
] - pctl
->n
[i
];
180 if ((d
>= 1 && pctl
->n
[i
+ 1] - pctl
->n
[i
] > 1) ||
181 (d
<= -1 && pctl
->n
[i
- 1] - pctl
->n
[i
] < -1)) {
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]);
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
;
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
]));
203 /* Without enough samples, P-square is not very accurate. Until we reach
204 * P_SQUARE_MIN, use a traditional calculation for the percentile.
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
)];
210 pctl
->percentile
= pctl
->q
[2];
215 calc_average(struct average
*avg
, double new_sample
)
217 avg
->average
= new_sample
* avg
->alpha
+ (1 - avg
->alpha
) * avg
->average
;
221 add_sample(struct stopwatch
*sw
, unsigned long long new_sample
)
223 if (new_sample
> sw
->max
) {
224 sw
->max
= new_sample
;
227 if (new_sample
< sw
->min
|| sw
->n_samples
== 0) {
228 sw
->min
= new_sample
;
231 calc_percentile(sw
->n_samples
, &sw
->pctl
, new_sample
);
233 if (sw
->n_samples
++ == 0) {
234 sw
->short_term
.average
= sw
->long_term
.average
= new_sample
;
238 calc_average(&sw
->short_term
, new_sample
);
239 calc_average(&sw
->long_term
, new_sample
);
243 stopwatch_get_stats_protected(const char *name
,
244 struct stopwatch_stats
*stats
)
246 struct stopwatch
*perf
;
248 perf
= shash_find_data(&stopwatches
, name
);
253 stats
->count
= perf
->n_samples
;
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
;
265 stopwatch_get_stats(const char *name
, struct stopwatch_stats
*stats
)
269 ovs_mutex_lock(&stopwatches_lock
);
270 found
= stopwatch_get_stats_protected(name
, stats
);
271 ovs_mutex_unlock(&stopwatches_lock
);
277 stopwatch_print(struct stopwatch
*sw
, const char *name
,
280 ds_put_format(s
, "Statistics for '%s'\n", name
);
282 const char *units
= unit_name
[sw
->units
];
283 ds_put_format(s
, "\t Total samples: %llu\n", sw
->n_samples
);
284 ds_put_format(s
, "\t Maximum: %llu %s\n", sw
->max
, units
);
285 ds_put_format(s
, "\t Minimum: %llu %s\n", sw
->min
, units
);
286 ds_put_format(s
, "\t 95th percentile: %f %s\n",
287 sw
->pctl
.percentile
, units
);
288 ds_put_format(s
, "\t Short term average: %f %s\n",
289 sw
->short_term
.average
, units
);
290 ds_put_format(s
, "\t Long term average: %f %s\n",
291 sw
->long_term
.average
, units
);
295 stopwatch_show_protected(int argc
, const char *argv
[], struct ds
*s
)
297 struct stopwatch
*sw
;
300 sw
= shash_find_data(&stopwatches
, argv
[1]);
302 ds_put_cstr(s
, "No such stopwatch");
305 stopwatch_print(sw
, argv
[1], s
);
307 struct shash_node
*node
;
308 SHASH_FOR_EACH (node
, &stopwatches
) {
310 stopwatch_print(sw
, node
->name
, s
);
318 stopwatch_show(struct unixctl_conn
*conn
, int argc OVS_UNUSED
,
319 const char *argv
[], void *aux OVS_UNUSED
)
321 struct ds s
= DS_EMPTY_INITIALIZER
;
324 ovs_mutex_lock(&stopwatches_lock
);
325 success
= stopwatch_show_protected(argc
, argv
, &s
);
326 ovs_mutex_unlock(&stopwatches_lock
);
329 unixctl_command_reply(conn
, ds_cstr(&s
));
331 unixctl_command_reply_error(conn
, ds_cstr(&s
));
336 static struct stopwatch_packet
*
337 stopwatch_packet_create(enum stopwatch_op op
)
339 struct stopwatch_packet
*pkt
;
341 pkt
= xzalloc(sizeof *pkt
);
348 stopwatch_packet_write(struct stopwatch_packet
*pkt
)
350 guarded_list_push_back(&stopwatch_commands
, &pkt
->list_node
, SIZE_MAX
);
351 latch_set(&stopwatch_latch
);
355 stopwatch_reset(struct unixctl_conn
*conn
, int argc OVS_UNUSED
,
356 const char *argv
[], void *aux OVS_UNUSED
)
358 struct stopwatch_packet
*pkt
= stopwatch_packet_create(OP_RESET
);
360 ovs_strlcpy(pkt
->name
, argv
[1], sizeof pkt
->name
);
362 stopwatch_packet_write(pkt
);
363 unixctl_command_reply(conn
, "");
367 stopwatch_start_sample_protected(const struct stopwatch_packet
*pkt
)
369 struct stopwatch
*sw
= shash_find_data(&stopwatches
, pkt
->name
);
370 if (!sw
|| sw
->sample_in_progress
) {
374 sw
->sample_start
= pkt
->time
;
375 sw
->sample_in_progress
= true;
379 stopwatch_end_sample_protected(const struct stopwatch_packet
*pkt
)
381 struct stopwatch
*sw
= shash_find_data(&stopwatches
, pkt
->name
);
382 if (!sw
|| !sw
->sample_in_progress
) {
386 add_sample(sw
, pkt
->time
- sw
->sample_start
);
387 sw
->sample_in_progress
= false;
390 static void reset_stopwatch(struct stopwatch
*sw
)
392 sw
->short_term
.average
= 0;
393 sw
->long_term
.average
= 0;
394 sw
->pctl
.percentile
= 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.
405 stopwatch_reset_protected(const struct stopwatch_packet
*pkt
)
408 struct stopwatch
*sw
= shash_find_data(&stopwatches
, pkt
->name
);
416 struct shash_node
*node
;
417 SHASH_FOR_EACH (node
, &stopwatches
) {
418 struct stopwatch
*sw
= node
->data
;
424 stopwatch_thread(void *ign OVS_UNUSED
)
426 bool should_exit
= false;
428 while (!should_exit
) {
429 struct ovs_list command_list
;
430 struct stopwatch_packet
*pkt
;
432 latch_poll(&stopwatch_latch
);
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
) {
437 case OP_START_SAMPLE
:
438 stopwatch_start_sample_protected(pkt
);
441 stopwatch_end_sample_protected(pkt
);
444 xpthread_cond_signal(&stopwatches_sync
);
447 stopwatch_reset_protected(pkt
);
454 ovs_mutex_unlock(&stopwatches_lock
);
457 latch_wait(&stopwatch_latch
);
468 struct shash_node
*node
, *node_next
;
469 struct stopwatch_packet
*pkt
= stopwatch_packet_create(OP_SHUTDOWN
);
470 stopwatch_packet_write(pkt
);
471 xpthread_join(stopwatch_thread_id
, NULL
);
473 /* Process is exiting and we have joined the only
474 * other competing thread. We are now the sole owners
475 * of all data in the file.
477 SHASH_FOR_EACH_SAFE (node
, node_next
, &stopwatches
) {
478 struct stopwatch
*sw
= node
->data
;
479 shash_delete(&stopwatches
, node
);
482 shash_destroy(&stopwatches
);
483 ovs_mutex_destroy(&stopwatches_lock
);
484 guarded_list_destroy(&stopwatch_commands
);
485 latch_destroy(&stopwatch_latch
);
489 do_init_stopwatch(void)
491 unixctl_command_register("stopwatch/show", "[NAME]", 0, 1,
492 stopwatch_show
, NULL
);
493 unixctl_command_register("stopwatch/reset", "[NAME]", 0, 1,
494 stopwatch_reset
, NULL
);
495 guarded_list_init(&stopwatch_commands
);
496 latch_init(&stopwatch_latch
);
497 stopwatch_thread_id
= ovs_thread_create(
498 "stopwatch", stopwatch_thread
, NULL
);
499 atexit(stopwatch_exit
);
505 static struct ovsthread_once once
= OVSTHREAD_ONCE_INITIALIZER
;
506 if (ovsthread_once_start(&once
)) {
508 ovsthread_once_done(&once
);
513 stopwatch_create(const char *name
, enum stopwatch_units units
)
517 struct stopwatch
*sw
= xzalloc(sizeof *sw
);
519 sw
->short_term
.alpha
= 0.50;
520 sw
->long_term
.alpha
= 0.01;
522 ovs_mutex_lock(&stopwatches_lock
);
523 shash_add(&stopwatches
, name
, sw
);
524 ovs_mutex_unlock(&stopwatches_lock
);
528 stopwatch_start(const char *name
, unsigned long long ts
)
530 struct stopwatch_packet
*pkt
= stopwatch_packet_create(OP_START_SAMPLE
);
531 ovs_strlcpy(pkt
->name
, name
, sizeof pkt
->name
);
533 stopwatch_packet_write(pkt
);
537 stopwatch_stop(const char *name
, unsigned long long ts
)
539 struct stopwatch_packet
*pkt
= stopwatch_packet_create(OP_END_SAMPLE
);
540 ovs_strlcpy(pkt
->name
, name
, sizeof pkt
->name
);
542 stopwatch_packet_write(pkt
);
548 struct stopwatch_packet
*pkt
= stopwatch_packet_create(OP_SYNC
);
549 ovs_mutex_lock(&stopwatches_lock
);
550 stopwatch_packet_write(pkt
);
551 ovs_mutex_cond_wait(&stopwatches_sync
, &stopwatches_lock
);
552 ovs_mutex_unlock(&stopwatches_lock
);