@@ -222,6 +222,8 @@ lib_libopenvswitch_la_SOURCES = \
lib/pcap-file.h \
lib/perf-counter.h \
lib/perf-counter.c \
+ lib/performance.h \
+ lib/performance.c \
lib/poll-loop.c \
lib/process.c \
lib/process.h \
new file mode 100644
@@ -0,0 +1,480 @@
+/* Copyright (c) 2017 Red Hat, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "performance.h"
+#include "openvswitch/shash.h"
+#include "openvswitch/vlog.h"
+#include "unixctl.h"
+#include "openvswitch/dynamic-string.h"
+#include "openvswitch/poll-loop.h"
+#include "ovs-thread.h"
+#include <unistd.h>
+#include "socket-util.h"
+
+VLOG_DEFINE_THIS_MODULE(performance);
+
+struct sample {
+ unsigned long long start_time; /* Time when we started this sample */
+ unsigned long long end_time; /* Time when we ended this sample */
+};
+
+struct average {
+ double average; /* Moving average */
+ double alpha; /* Weight given to new samples */
+};
+
+#define MARKERS 5
+
+/* The naming of these fields is based on the naming used in the
+ * P-square algorithm paper.
+ */
+struct percentile {
+ int n[MARKERS];
+ double n_prime[MARKERS];
+ double q[MARKERS];
+ double dn[MARKERS];
+ double percentile;
+};
+
+struct performance {
+ struct sample cur_sample;
+ enum performance_units units;
+ unsigned long long samples;
+ unsigned long long max;
+ unsigned long long min;
+ struct percentile pctl;
+ struct average short_term;
+ struct average long_term;
+};
+
+enum performance_op {
+ OP_START_SAMPLE,
+ OP_END_SAMPLE,
+ OP_RESET,
+ OP_SHUTDOWN,
+};
+
+struct performance_packet {
+ enum performance_op op;
+ char name[32];
+ unsigned long long time;
+};
+
+static struct shash performances = SHASH_INITIALIZER(&performances);
+static struct ovs_mutex performances_lock = OVS_MUTEX_INITIALIZER;
+
+static int performance_pipe[2];
+static pthread_t performance_thread_id;
+
+const char *unit_name[] = {
+ [PERF_MS] = "msec",
+ [PERF_US] = "usec",
+ [PERF_NS] = "nsec",
+};
+
+/* Percentile value we are calculating */
+#define P 0.95
+
+static int
+comp_samples(const void *left, const void *right)
+{
+ const double *left_d = left;
+ const double *right_d = right;
+
+ return (int) *right_d - *left_d;
+}
+
+/* Calculate the percentile using the P-square algorithm. For more
+ * information, see https://www1.cse.wustl.edu/~jain/papers/ftp/psqr.pdf
+ */
+static void
+calc_percentile(unsigned long long samples, struct percentile *pctl,
+ double new_sample)
+{
+ /* For the first MARKERS samples, we calculate the percentile
+ * in the traditional way
+ */
+ if (samples <= MARKERS) {
+ pctl->q[samples - 1] = new_sample;
+ qsort(pctl->q, samples, sizeof *pctl->q, comp_samples);
+ if (samples == MARKERS) {
+ pctl->n[0] = 0;
+ pctl->n[1] = 1;
+ pctl->n[2] = 2;
+ pctl->n[3] = 3;
+ pctl->n[4] = 4;
+
+ pctl->n_prime[0] = 0;
+ pctl->n_prime[1] = 2 * P;
+ pctl->n_prime[2] = 4 * P;
+ pctl->n_prime[3] = 2 + 2 * P;
+ pctl->n_prime[4] = 4;
+
+ pctl->dn[0] = 0;
+ pctl->dn[1] = P / 2;
+ pctl->dn[2] = P;
+ pctl->dn[3] = (1 + P) / 2;
+ pctl->dn[4] = 1;
+ }
+ pctl->percentile = pctl->q[(int) P * samples];
+ return;
+ }
+
+ /* From here on, update the markers using quadratic spline calculations */
+ int k;
+ if (new_sample < pctl->q[0]) {
+ k = 0;
+ pctl->q[0] = new_sample;
+ } else if (new_sample < pctl->q[1]) {
+ k = 0;
+ } else if (new_sample < pctl->q[2]) {
+ k = 1;
+ } else if (new_sample < pctl->q[3]) {
+ k = 2;
+ } else if (new_sample <= pctl->q[4]) {
+ k = 3;
+ } else {
+ k = 3;
+ pctl->q[4] = new_sample;
+ }
+
+ for (int i = k + 1; i < MARKERS; i++) {
+ pctl->n[i]++;
+ }
+
+ for (int i = 0; i < MARKERS; i++) {
+ pctl->n_prime[i] += pctl->dn[i];
+ }
+
+ for (int i = 1; i < MARKERS - 1; i++) {
+ double d = pctl->n_prime[i] - pctl->n[i];
+
+ if ((d >= 1 && pctl->n[i + 1] - pctl->n[i] > 1) ||
+ (d <= -1 && pctl->n[i - 1] - pctl->n[i] < -1)) {
+ d = d >= 0 ? 1 : -1;
+
+ double a = d / (pctl->n[i + 1] - pctl->n[i - 1]);
+ double b = (pctl->n[i] - pctl->n[i - 1] + d) *
+ (pctl->q[i + 1] - pctl->q[i]) / (pctl->n[i + 1] - pctl->n[i]);
+ double c = (pctl->n[i + 1] - pctl->n[i] - d) *
+ (pctl->q[i] - pctl->q[i - 1]) / (pctl->n[i] - pctl->n[i - 1]);
+
+ double candidate = pctl->q[i] + a * (b + c);
+ if (pctl->q[i - 1] < candidate && candidate < pctl->q[i + 1]) {
+ pctl->q[i] = candidate;
+ } else {
+ pctl->q[i] = pctl->q[i] +
+ (d * (pctl->q[i + (int)d] - pctl->q[i]) /
+ (pctl->n[i +(int)d] - pctl->n[i]));
+ }
+
+ pctl->n[i] += d;
+ }
+ }
+
+ pctl->percentile = pctl->q[2];
+}
+
+static void
+calc_average(struct average *avg, double new_sample)
+{
+ avg->average = new_sample * avg->alpha + (1 - avg->alpha) * avg->average;
+}
+
+static void
+add_sample(struct performance *perf, double new_sample)
+{
+ if (new_sample > perf->max) {
+ perf->max = new_sample;
+ } else if (new_sample < perf->min) {
+ perf->min = new_sample;
+ }
+
+ calc_percentile(perf->samples, &perf->pctl, new_sample);
+
+ if (perf->samples++ == 0) {
+ perf->short_term.average = perf->long_term.average = new_sample;
+ return;
+ }
+
+ calc_average(&perf->short_term, new_sample);
+ calc_average(&perf->long_term, new_sample);
+}
+
+static void
+performance_print(struct performance *perf, const char *name,
+ struct ds *s)
+{
+ ds_put_format(s, "Statistics for '%s'\n", name);
+
+ const char *units = unit_name[perf->units];
+ ds_put_format(s, "\t Total samples: %llu\n", perf->samples);
+ ds_put_format(s, "\t Maximum: %llu %s\n", perf->max, units);
+ ds_put_format(s, "\t Minimum: %llu %s\n", perf->min, units);
+ ds_put_format(s, "\t 95th percentile: %f %s\n",
+ perf->pctl.percentile, units);
+ ds_put_format(s, "\t Short term average: %f %s\n",
+ perf->short_term.average, units);
+ ds_put_format(s, "\t Long term average: %f %s\n",
+ perf->long_term.average, units);
+}
+
+static bool
+performance_show_protected(int argc, const char *argv[], struct ds *s)
+{
+ struct performance *perf;
+
+ if (argc > 1) {
+ perf = shash_find_data(&performances, argv[1]);
+ if (!perf) {
+ ds_put_cstr(s, "No such performance");
+ return false;
+ }
+ performance_print(perf, argv[1], s);
+ } else {
+ struct shash_node *node;
+ SHASH_FOR_EACH (node, &performances) {
+ perf = node->data;
+ performance_print(perf, node->name, s);
+ }
+ }
+
+ return true;
+}
+
+static void
+performance_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
+ const char *argv[], void *ignore OVS_UNUSED)
+{
+ struct ds s = DS_EMPTY_INITIALIZER;
+ bool success;
+
+ ovs_mutex_lock(&performances_lock);
+ success = performance_show_protected(argc, argv, &s);
+ ovs_mutex_unlock(&performances_lock);
+
+ if (success) {
+ unixctl_command_reply(conn, ds_cstr(&s));
+ } else {
+ unixctl_command_reply_error(conn, ds_cstr(&s));
+ }
+ ds_destroy(&s);
+}
+
+static void
+performance_reset(struct unixctl_conn *conn, int argc OVS_UNUSED,
+ const char *argv[], void *ignore OVS_UNUSED)
+{
+ struct performance_packet pkt = {
+ .op = OP_RESET,
+ };
+ if (argc > 1) {
+ ovs_strlcpy(pkt.name, argv[1], sizeof(pkt.name));
+ }
+ write(performance_pipe[1], &pkt, sizeof(pkt));
+ unixctl_command_reply(conn, "");
+}
+
+static bool
+performance_start_sample_protected(const struct performance_packet *pkt)
+{
+ struct performance *perf = shash_find_data(&performances, pkt->name);
+ if (!perf) {
+ return false;
+ }
+
+ /* We already started sampling. Need an end before
+ * we start another sample
+ */
+ if (perf->cur_sample.start_time) {
+ return false;
+ }
+
+ perf->cur_sample.start_time = pkt->time;
+ return true;
+}
+
+static bool
+performance_end_sample_protected(const struct performance_packet *pkt)
+{
+ struct performance *perf = shash_find_data(&performances, pkt->name);
+ if (!perf) {
+ return false;
+ }
+
+ /* We can't end a sample if we haven't started one */
+ if (!perf->cur_sample.start_time) {
+ return false;
+ }
+
+ perf->cur_sample.end_time = pkt->time;
+ add_sample(perf, perf->cur_sample.end_time - perf->cur_sample.start_time);
+ perf->cur_sample.start_time = perf->cur_sample.end_time = 0;
+ return true;
+}
+
+static void reset_performance(struct performance *perf)
+{
+ perf->short_term.average = 0;
+ perf->long_term.average = 0;
+ perf->pctl.percentile = 0;
+ perf->samples = 0;
+ perf->max = 0;
+ perf->min = 0;
+}
+
+static void
+performance_reset_protected(const struct performance_packet *pkt)
+{
+ if (pkt->name[0]) {
+ struct performance *perf = shash_find_data(&performances, pkt->name);
+ if (!perf) {
+ return;
+ }
+ reset_performance(perf);
+ return;
+ }
+
+ struct shash_node *node;
+ SHASH_FOR_EACH (node, &performances) {
+ struct performance *perf = node->data;
+ reset_performance(perf);
+ }
+}
+
+static void *
+performance_thread(void *ign OVS_UNUSED)
+{
+ bool should_exit = false;
+
+ while (!should_exit) {
+ struct performance_packet pkt;
+ while (read(performance_pipe[0], &pkt, sizeof(pkt)) > 0) {
+ ovs_mutex_lock(&performances_lock);
+ switch (pkt.op) {
+ case OP_START_SAMPLE:
+ performance_start_sample_protected(&pkt);
+ break;
+ case OP_END_SAMPLE:
+ performance_end_sample_protected(&pkt);
+ break;
+ case OP_RESET:
+ performance_reset_protected(&pkt);
+ break;
+ case OP_SHUTDOWN:
+ should_exit = true;
+ break;
+ }
+ ovs_mutex_unlock(&performances_lock);
+ }
+
+ if (!should_exit) {
+ poll_fd_wait(performance_pipe[0], POLLIN);
+ poll_block();
+ }
+ }
+
+ return NULL;
+}
+
+static void
+performance_exit(void)
+{
+ struct shash_node *node, *node_next;
+ struct performance_packet pkt = {
+ .op = OP_SHUTDOWN,
+ };
+
+ write(performance_pipe[1], &pkt, sizeof pkt);
+ xpthread_join(performance_thread_id, NULL);
+
+ /* Process is exiting and we have joined the only
+ * other competing thread. We are now the sole owners
+ * of all data in the file.
+ */
+ SHASH_FOR_EACH_SAFE (node, node_next, &performances) {
+ struct performance *perf = node->data;
+ shash_delete(&performances, node);
+ free(perf);
+ }
+ shash_destroy(&performances);
+ ovs_mutex_destroy(&performances_lock);
+}
+
+static void
+do_init_performance(void)
+{
+ unixctl_command_register("performance/show", "[NAME]", 0, 1,
+ performance_show, NULL);
+ unixctl_command_register("performance/reset", "[NAME]", 0, 1,
+ performance_reset, NULL);
+ xpipe_nonblocking(performance_pipe);
+ performance_thread_id = ovs_thread_create(
+ "performance", performance_thread, NULL);
+ atexit(performance_exit);
+}
+
+static void
+performance_init(void)
+{
+ static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
+ if (ovsthread_once_start(&once)) {
+ do_init_performance();
+ ovsthread_once_done(&once);
+ }
+}
+
+void
+performance_create(const char *name, enum performance_units units)
+{
+ performance_init();
+
+ struct performance *perf = xzalloc(sizeof *perf);
+ perf->units = units;
+ perf->short_term.alpha = 0.50;
+ perf->long_term.alpha = 0.01;
+
+ ovs_mutex_lock(&performances_lock);
+ shash_add(&performances, name, perf);
+ ovs_mutex_unlock(&performances_lock);
+}
+
+bool
+performance_start_sample(const char *name, unsigned long long ts)
+{
+ struct performance_packet pkt = {
+ .op = OP_START_SAMPLE,
+ .time = ts,
+ };
+ ovs_strlcpy(pkt.name, name, sizeof(pkt.name));
+ write(performance_pipe[1], &pkt, sizeof(pkt));
+
+ return true;
+}
+
+bool
+performance_end_sample(const char *name, unsigned long long ts)
+{
+ struct performance_packet pkt = {
+ .op = OP_END_SAMPLE,
+ .time = ts,
+ };
+ ovs_strlcpy(pkt.name, name, sizeof(pkt.name));
+ write(performance_pipe[1], &pkt, sizeof(pkt));
+
+ return true;
+}
new file mode 100644
@@ -0,0 +1,42 @@
+/* Copyright (c) 2017 Red Hat, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef PERFORMANCE_H
+#define PERFORMANCE_H 1
+
+#include <stdbool.h>
+
+enum performance_units {
+ PERF_MS,
+ PERF_US,
+ PERF_NS,
+};
+
+/* Create a new performance measurement.
+ * The "units" are not used for any calculations but are printed when
+ * statistics are requested.
+ */
+void performance_create(const char *name, enum performance_units units);
+
+/* Indicate that a performance measurement is beginning. */
+bool performance_start_sample(const char *name, unsigned long long ts);
+
+/* Indicate that a performance measurement has ended. The
+ * sample will be added to the history of performance
+ * measurements for this tracker
+ */
+bool performance_end_sample(const char *name, unsigned long long ts);
+
+#endif /* performance.h */
This is similar to the existing coverage and perf-counter APIs in OVS. However, rather than keeping counters, this is aimed at timing how long operations take to perform. "Operations" in this case can be anything from a loop iteration, to a function, to something more complex. The library will keep track of how long it takes to perform the particular operations and will maintain statistics of those running times. Statistics for a particular operation can be queried from the command line by using ovs-appctl -t <target> performance/show <operation name>. The API is designed to be pretty small. The expected steps are as follows: 1) Create a performance measurement, providing a unique name, using performance_create() 2) Add calls to start_sample() and end_sample() to mark the start and stop of the operation you wish to measure. Two CLI commands have been added: * Display statistics for a particular measurement. * Reset a particular measurement. Signed-off-by: Mark Michelson <mmichels@redhat.com> --- lib/automake.mk | 2 + lib/performance.c | 480 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/performance.h | 42 +++++ 3 files changed, 524 insertions(+) create mode 100644 lib/performance.c create mode 100644 lib/performance.h