lib/coverage.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012, 2013 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 "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 void
 250 coverage_clear(void)
 251 {
 252     long long int now, *thread_time;
 253
 254     now = time_msec();
 255     thread_time = coverage_clear_time_get();
 256
 257     /* Initialize the coverage_clear_time. */
 258     if (*thread_time == LLONG_MIN) {
 259         *thread_time = now + COVERAGE_CLEAR_INTERVAL;
 260     }
 261
 262     if (now >= *thread_time) {
 263         size_t i;
 264
 265         ovs_mutex_lock(&coverage_mutex);
 266         for (i = 0; i < n_coverage_counters; i++) {
 267             struct coverage_counter *c = coverage_counters[i];
 268             c->total += c->count();
 269         }
 270         ovs_mutex_unlock(&coverage_mutex);
 271         *thread_time = now + COVERAGE_CLEAR_INTERVAL;
 272     }
 273 }
 274
 275 /* Runs approximately every COVERAGE_RUN_INTERVAL amount of time to update the
 276  * coverage counters' 'min' and 'hr' array.  'min' array is for cumulating
 277  * per second counts into per minute count.  'hr' array is for cumulating per
 278  * minute counts into per hour count.  Every thread may call this function. */
 279 void
 280 coverage_run(void)
 281 {
 282     /* Defines the moving average array index variables. */
 283     static unsigned int min_idx, hr_idx;
 284     struct coverage_counter **c = coverage_counters;
 285     long long int now;
 286
 287     ovs_mutex_lock(&coverage_mutex);
 288     now = time_msec();
 289     /* Initialize the coverage_run_time. */
 290     if (coverage_run_time == LLONG_MIN) {
 291         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 292     }
 293
 294     if (now >= coverage_run_time) {
 295         size_t i, j;
 296         /* Computes the number of COVERAGE_RUN_INTERVAL slots, since
 297          * it is possible that the actual run interval is multiple of
 298          * COVERAGE_RUN_INTERVAL. */
 299         int slots = (now - coverage_run_time) / COVERAGE_RUN_INTERVAL + 1;
 300
 301         for (i = 0; i < n_coverage_counters; i++) {
 302             unsigned int count, portion;
 303             unsigned int m_idx = min_idx;
 304             unsigned int h_idx = hr_idx;
 305             unsigned int idx = idx_count;
 306
 307             /* Computes the differences between the current total and the one
 308              * recorded in last invocation of coverage_run(). */
 309             count = c[i]->total - c[i]->last_total;
 310             c[i]->last_total = c[i]->total;
 311             /* The count over the time interval is evenly distributed
 312              * among slots by calculating the portion. */
 313             portion = count / slots;
 314
 315             for (j = 0; j < slots; j++) {
 316                 /* Updates the index variables. */
 317                 /* The m_idx is increased from 0 to MIN_AVG_LEN - 1. Every
 318                  * time the m_idx finishes a cycle (a cycle is one minute),
 319                  * the h_idx is incremented by 1. */
 320                 m_idx = idx % MIN_AVG_LEN;
 321                 h_idx = idx / MIN_AVG_LEN;
 322
 323                 c[i]->min[m_idx] = portion + (j == (slots - 1)
 324                                               ? count % slots : 0);
 325                 c[i]->hr[h_idx] = m_idx == 0
 326                                   ? c[i]->min[m_idx]
 327                                   : (c[i]->hr[h_idx] + c[i]->min[m_idx]);
 328                 /* This is to guarantee that h_idx ranges from 0 to 59. */
 329                 idx = (idx + 1) % (MIN_AVG_LEN * HR_AVG_LEN);
 330             }
 331         }
 332
 333         /* Updates the global index variables. */
 334         idx_count = (idx_count + slots) % (MIN_AVG_LEN * HR_AVG_LEN);
 335         min_idx = idx_count % MIN_AVG_LEN;
 336         hr_idx  = idx_count / MIN_AVG_LEN;
 337         /* Updates the run time. */
 338         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 339     }
 340     ovs_mutex_unlock(&coverage_mutex);
 341 }
 342
 343 static unsigned int
 344 coverage_array_sum(const unsigned int *arr, const unsigned int len)
 345 {
 346     unsigned int sum = 0;
 347     size_t i;
 348
 349     ovs_mutex_lock(&coverage_mutex);
 350     for (i = 0; i < len; i++) {
 351         sum += arr[i];
 352     }
 353     ovs_mutex_unlock(&coverage_mutex);
 354     return sum;
 355 }