lib/coverage.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "coverage.h"
  19 #include <inttypes.h>
  20 #include <stdlib.h>
  21 #include "dynamic-string.h"
  22 #include "hash.h"
  23 #include "svec.h"
  24 #include "timeval.h"
  25 #include "unixctl.h"
  26 #include "util.h"
  27 #include "openvswitch/vlog.h"
  28
  29 VLOG_DEFINE_THIS_MODULE(coverage);
  30
  31 /* The coverage counters. */
  32 static struct coverage_counter **coverage_counters = NULL;
  33 static size_t n_coverage_counters = 0;
  34 static size_t allocated_coverage_counters = 0;
  35
  36 static struct ovs_mutex coverage_mutex = OVS_MUTEX_INITIALIZER;
  37
  38 DEFINE_STATIC_PER_THREAD_DATA(long long int, coverage_clear_time, LLONG_MIN);
  39 static long long int coverage_run_time = LLONG_MIN;
  40
  41 /* Index counter used to compute the moving average array's index. */
  42 static unsigned int idx_count = 0;
  43
  44 static void coverage_read(struct svec *);
  45 static unsigned int coverage_array_sum(const unsigned int *arr,
  46                                        const unsigned int len);
  47
  48 /* Registers a coverage counter with the coverage core */
  49 void
  50 coverage_counter_register(struct coverage_counter* counter)
  51 {
  52     if (n_coverage_counters >= allocated_coverage_counters) {
  53         coverage_counters = x2nrealloc(coverage_counters,
  54                                        &allocated_coverage_counters,
  55                                        sizeof(struct coverage_counter*));
  56     }
  57     coverage_counters[n_coverage_counters++] = counter;
  58 }
  59
  60 static void
  61 coverage_unixctl_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
  62                      const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
  63 {
  64     struct svec lines;
  65     char *reply;
  66
  67     svec_init(&lines);
  68     coverage_read(&lines);
  69     reply = svec_join(&lines, "\n", "\n");
  70     unixctl_command_reply(conn, reply);
  71     free(reply);
  72     svec_destroy(&lines);
  73 }
  74
  75 void
  76 coverage_init(void)
  77 {
  78     unixctl_command_register("coverage/show", "", 0, 0,
  79                              coverage_unixctl_show, NULL);
  80 }
  81
  82 /* Sorts coverage counters in descending order by total, within equal
  83  * totals alphabetically by name. */
  84 static int
  85 compare_coverage_counters(const void *a_, const void *b_)
  86 {
  87     const struct coverage_counter *const *ap = a_;
  88     const struct coverage_counter *const *bp = b_;
  89     const struct coverage_counter *a = *ap;
  90     const struct coverage_counter *b = *bp;
  91     if (a->total != b->total) {
  92         return a->total < b->total ? 1 : -1;
  93     } else {
  94         return strcmp(a->name, b->name);
  95     }
  96 }
  97
  98 static uint32_t
  99 coverage_hash(void)
 100 {
 101     struct coverage_counter **c;
 102     uint32_t hash = 0;
 103     int n_groups, i;
 104
 105     /* Sort coverage counters into groups with equal totals. */
 106     c = xmalloc(n_coverage_counters * sizeof *c);
 107     ovs_mutex_lock(&coverage_mutex);
 108     for (i = 0; i < n_coverage_counters; i++) {
 109         c[i] = coverage_counters[i];
 110     }
 111     ovs_mutex_unlock(&coverage_mutex);
 112     qsort(c, n_coverage_counters, sizeof *c, compare_coverage_counters);
 113
 114     /* Hash the names in each group along with the rank. */
 115     n_groups = 0;
 116     for (i = 0; i < n_coverage_counters; ) {
 117         int j;
 118
 119         if (!c[i]->total) {
 120             break;
 121         }
 122         n_groups++;
 123         hash = hash_int(i, hash);
 124         for (j = i; j < n_coverage_counters; j++) {
 125             if (c[j]->total != c[i]->total) {
 126                 break;
 127             }
 128             hash = hash_string(c[j]->name, hash);
 129         }
 130         i = j;
 131     }
 132
 133     free(c);
 134
 135     return hash_int(n_groups, hash);
 136 }
 137
 138 static bool
 139 coverage_hit(uint32_t hash)
 140 {
 141     enum { HIT_BITS = 1024, BITS_PER_WORD = 32 };
 142     static uint32_t hit[HIT_BITS / BITS_PER_WORD];
 143     BUILD_ASSERT_DECL(IS_POW2(HIT_BITS));
 144
 145     static long long int next_clear = LLONG_MIN;
 146
 147     unsigned int bit_index = hash & (HIT_BITS - 1);
 148     unsigned int word_index = bit_index / BITS_PER_WORD;
 149     unsigned int word_mask = 1u << (bit_index % BITS_PER_WORD);
 150
 151     /* Expire coverage hash suppression once a day. */
 152     if (time_msec() >= next_clear) {
 153         memset(hit, 0, sizeof hit);
 154         next_clear = time_msec() + 60 * 60 * 24 * 1000LL;
 155     }
 156
 157     if (hit[word_index] & word_mask) {
 158         return true;
 159     } else {
 160         hit[word_index] |= word_mask;
 161         return false;
 162     }
 163 }
 164
 165 /* Logs the coverage counters, unless a similar set of events has already been
 166  * logged.
 167  *
 168  * This function logs at log level VLL_INFO.  Use care before adjusting this
 169  * level, because depending on its configuration, syslogd can write changes
 170  * synchronously, which can cause the coverage messages to take several seconds
 171  * to write. */
 172 void
 173 coverage_log(void)
 174 {
 175     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 3);
 176
 177     if (!VLOG_DROP_INFO(&rl)) {
 178         uint32_t hash = coverage_hash();
 179         if (coverage_hit(hash)) {
 180             VLOG_INFO("Skipping details of duplicate event coverage for "
 181                       "hash=%08"PRIx32, hash);
 182         } else {
 183             struct svec lines;
 184             const char *line;
 185             size_t i;
 186
 187             svec_init(&lines);
 188             coverage_read(&lines);
 189             SVEC_FOR_EACH (i, line, &lines) {
 190                 VLOG_INFO("%s", line);
 191             }
 192             svec_destroy(&lines);
 193         }
 194     }
 195 }
 196
 197 /* Adds coverage counter information to 'lines'. */
 198 static void
 199 coverage_read(struct svec *lines)
 200 {
 201     struct coverage_counter **c = coverage_counters;
 202     unsigned long long int *totals;
 203     size_t n_never_hit;
 204     uint32_t hash;
 205     size_t i;
 206
 207     hash = coverage_hash();
 208
 209     n_never_hit = 0;
 210     svec_add_nocopy(lines,
 211                     xasprintf("Event coverage, avg rate over last: %d "
 212                               "seconds, last minute, last hour,  "
 213                               "hash=%08"PRIx32":",
 214                               COVERAGE_RUN_INTERVAL/1000, hash));
 215
 216     totals = xmalloc(n_coverage_counters * sizeof *totals);
 217     ovs_mutex_lock(&coverage_mutex);
 218     for (i = 0; i < n_coverage_counters; i++) {
 219         totals[i] = c[i]->total;
 220     }
 221     ovs_mutex_unlock(&coverage_mutex);
 222
 223     for (i = 0; i < n_coverage_counters; i++) {
 224         if (totals[i]) {
 225             /* Shows the averaged per-second rates for the last
 226              * COVERAGE_RUN_INTERVAL interval, the last minute and
 227              * the last hour. */
 228             svec_add_nocopy(lines,
 229                 xasprintf("%-24s %5.1f/sec %9.3f/sec "
 230                           "%13.4f/sec   total: %llu",
 231                           c[i]->name,
 232                           (c[i]->min[(idx_count - 1) % MIN_AVG_LEN]
 233                            * 1000.0 / COVERAGE_RUN_INTERVAL),
 234                           coverage_array_sum(c[i]->min, MIN_AVG_LEN) / 60.0,
 235                           coverage_array_sum(c[i]->hr,  HR_AVG_LEN) / 3600.0,
 236                           totals[i]));
 237         } else {
 238             n_never_hit++;
 239         }
 240     }
 241
 242     svec_add_nocopy(lines, xasprintf("%"PRIuSIZE" events never hit", n_never_hit));
 243     free(totals);
 244 }
 245
 246 /* Runs approximately every COVERAGE_CLEAR_INTERVAL amount of time to
 247  * synchronize per-thread counters with global counters. Every thread maintains
 248  * a separate timer to ensure all counters are periodically aggregated.
 249  *
 250  * Uses 'ovs_mutex_trylock()' if 'trylock' is true.  This is to prevent
 251  * multiple performance-critical threads contending over the 'coverage_mutex'.
 252  *
 253  * */
 254 static void
 255 coverage_clear__(bool trylock)
 256 {
 257     long long int now, *thread_time;
 258
 259     now = time_msec();
 260     thread_time = coverage_clear_time_get();
 261
 262     /* Initialize the coverage_clear_time. */
 263     if (*thread_time == LLONG_MIN) {
 264         *thread_time = now + COVERAGE_CLEAR_INTERVAL;
 265     }
 266
 267     if (now >= *thread_time) {
 268         size_t i;
 269
 270         if (trylock) {
 271             /* Returns if cannot acquire lock. */
 272             if (ovs_mutex_trylock(&coverage_mutex)) {
 273                 return;
 274             }
 275         } else {
 276             ovs_mutex_lock(&coverage_mutex);
 277         }
 278
 279         for (i = 0; i < n_coverage_counters; i++) {
 280             struct coverage_counter *c = coverage_counters[i];
 281             c->total += c->count();
 282         }
 283         ovs_mutex_unlock(&coverage_mutex);
 284         *thread_time = now + COVERAGE_CLEAR_INTERVAL;
 285     }
 286 }
 287
 288 void
 289 coverage_clear(void)
 290 {
 291     coverage_clear__(false);
 292 }
 293
 294 void
 295 coverage_try_clear(void)
 296 {
 297     coverage_clear__(true);
 298 }
 299
 300 /* Runs approximately every COVERAGE_RUN_INTERVAL amount of time to update the
 301  * coverage counters' 'min' and 'hr' array.  'min' array is for cumulating
 302  * per second counts into per minute count.  'hr' array is for cumulating per
 303  * minute counts into per hour count.  Every thread may call this function. */
 304 void
 305 coverage_run(void)
 306 {
 307     struct coverage_counter **c = coverage_counters;
 308     long long int now;
 309
 310     ovs_mutex_lock(&coverage_mutex);
 311     now = time_msec();
 312     /* Initialize the coverage_run_time. */
 313     if (coverage_run_time == LLONG_MIN) {
 314         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 315     }
 316
 317     if (now >= coverage_run_time) {
 318         size_t i, j;
 319         /* Computes the number of COVERAGE_RUN_INTERVAL slots, since
 320          * it is possible that the actual run interval is multiple of
 321          * COVERAGE_RUN_INTERVAL. */
 322         int slots = (now - coverage_run_time) / COVERAGE_RUN_INTERVAL + 1;
 323
 324         for (i = 0; i < n_coverage_counters; i++) {
 325             unsigned int count, portion;
 326             unsigned int idx = idx_count;
 327
 328             /* Computes the differences between the current total and the one
 329              * recorded in last invocation of coverage_run(). */
 330             count = c[i]->total - c[i]->last_total;
 331             c[i]->last_total = c[i]->total;
 332             /* The count over the time interval is evenly distributed
 333              * among slots by calculating the portion. */
 334             portion = count / slots;
 335
 336             for (j = 0; j < slots; j++) {
 337                 /* Updates the index variables. */
 338                 /* The m_idx is increased from 0 to MIN_AVG_LEN - 1. Every
 339                  * time the m_idx finishes a cycle (a cycle is one minute),
 340                  * the h_idx is incremented by 1. */
 341                 unsigned int m_idx = idx % MIN_AVG_LEN;
 342                 unsigned int h_idx = idx / MIN_AVG_LEN;
 343
 344                 c[i]->min[m_idx] = portion + (j == (slots - 1)
 345                                               ? count % slots : 0);
 346                 c[i]->hr[h_idx] = m_idx == 0
 347                                   ? c[i]->min[m_idx]
 348                                   : (c[i]->hr[h_idx] + c[i]->min[m_idx]);
 349                 /* This is to guarantee that h_idx ranges from 0 to 59. */
 350                 idx = (idx + 1) % (MIN_AVG_LEN * HR_AVG_LEN);
 351             }
 352         }
 353
 354         /* Updates the global index variables. */
 355         idx_count = (idx_count + slots) % (MIN_AVG_LEN * HR_AVG_LEN);
 356         /* Updates the run time. */
 357         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 358     }
 359     ovs_mutex_unlock(&coverage_mutex);
 360 }
 361
 362 static unsigned int
 363 coverage_array_sum(const unsigned int *arr, const unsigned int len)
 364 {
 365     unsigned int sum = 0;
 366     size_t i;
 367
 368     ovs_mutex_lock(&coverage_mutex);
 369     for (i = 0; i < len; i++) {
 370         sum += arr[i];
 371     }
 372     ovs_mutex_unlock(&coverage_mutex);
 373     return sum;
 374 }