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 #if USE_LINKER_SECTIONS
  33 extern struct coverage_counter *__start_coverage[];
  34 extern struct coverage_counter *__stop_coverage[];
  35 #define coverage_counters __start_coverage
  36 #define n_coverage_counters  (__stop_coverage - __start_coverage)
  37 #else  /* !USE_LINKER_SECTIONS */
  38 #define COVERAGE_COUNTER(COUNTER)                                       \
  39         DECLARE_EXTERN_PER_THREAD_DATA(unsigned int,                    \
  40                                        counter_##COUNTER);              \
  41         DEFINE_EXTERN_PER_THREAD_DATA(counter_##COUNTER, 0);            \
  42         static unsigned int COUNTER##_count(void)                       \
  43         {                                                               \
  44             unsigned int *countp = counter_##COUNTER##_get();           \
  45             unsigned int count = *countp;                               \
  46             *countp = 0;                                                \
  47             return count;                                               \
  48         }                                                               \
  49         extern struct coverage_counter counter_##COUNTER;               \
  50         struct coverage_counter counter_##COUNTER                       \
  51             = { #COUNTER, COUNTER##_count, 0 };
  52 #include "coverage.def"
  53 #undef COVERAGE_COUNTER
  54
  55 extern struct coverage_counter *coverage_counters[];
  56 struct coverage_counter *coverage_counters[] = {
  57 #define COVERAGE_COUNTER(NAME) &counter_##NAME,
  58 #include "coverage.def"
  59 #undef COVERAGE_COUNTER
  60 };
  61 #define n_coverage_counters ARRAY_SIZE(coverage_counters)
  62 #endif  /* !USE_LINKER_SECTIONS */
  63
  64 static struct ovs_mutex coverage_mutex = OVS_MUTEX_INITIALIZER;
  65
  66 static long long int coverage_run_time = LLONG_MIN;
  67
  68 /* Index counter used to compute the moving average array's index. */
  69 static unsigned int idx_count = 0;
  70
  71 static void coverage_read(struct svec *);
  72 static unsigned int coverage_array_sum(const unsigned int *arr,
  73                                        const unsigned int len);
  74
  75 static void
  76 coverage_unixctl_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
  77                      const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
  78 {
  79     struct svec lines;
  80     char *reply;
  81
  82     svec_init(&lines);
  83     coverage_read(&lines);
  84     reply = svec_join(&lines, "\n", "\n");
  85     unixctl_command_reply(conn, reply);
  86     free(reply);
  87     svec_destroy(&lines);
  88 }
  89
  90 void
  91 coverage_init(void)
  92 {
  93     unixctl_command_register("coverage/show", "", 0, 0,
  94                              coverage_unixctl_show, NULL);
  95 }
  96
  97 /* Sorts coverage counters in descending order by total, within equal
  98  * totals alphabetically by name. */
  99 static int
 100 compare_coverage_counters(const void *a_, const void *b_)
 101 {
 102     const struct coverage_counter *const *ap = a_;
 103     const struct coverage_counter *const *bp = b_;
 104     const struct coverage_counter *a = *ap;
 105     const struct coverage_counter *b = *bp;
 106     if (a->total != b->total) {
 107         return a->total < b->total ? 1 : -1;
 108     } else {
 109         return strcmp(a->name, b->name);
 110     }
 111 }
 112
 113 static uint32_t
 114 coverage_hash(void)
 115 {
 116     struct coverage_counter **c;
 117     uint32_t hash = 0;
 118     int n_groups, i;
 119
 120     /* Sort coverage counters into groups with equal totals. */
 121     c = xmalloc(n_coverage_counters * sizeof *c);
 122     ovs_mutex_lock(&coverage_mutex);
 123     for (i = 0; i < n_coverage_counters; i++) {
 124         c[i] = coverage_counters[i];
 125     }
 126     ovs_mutex_unlock(&coverage_mutex);
 127     qsort(c, n_coverage_counters, sizeof *c, compare_coverage_counters);
 128
 129     /* Hash the names in each group along with the rank. */
 130     n_groups = 0;
 131     for (i = 0; i < n_coverage_counters; ) {
 132         int j;
 133
 134         if (!c[i]->total) {
 135             break;
 136         }
 137         n_groups++;
 138         hash = hash_int(i, hash);
 139         for (j = i; j < n_coverage_counters; j++) {
 140             if (c[j]->total != c[i]->total) {
 141                 break;
 142             }
 143             hash = hash_string(c[j]->name, hash);
 144         }
 145         i = j;
 146     }
 147
 148     free(c);
 149
 150     return hash_int(n_groups, hash);
 151 }
 152
 153 static bool
 154 coverage_hit(uint32_t hash)
 155 {
 156     enum { HIT_BITS = 1024, BITS_PER_WORD = 32 };
 157     static uint32_t hit[HIT_BITS / BITS_PER_WORD];
 158     BUILD_ASSERT_DECL(IS_POW2(HIT_BITS));
 159
 160     static long long int next_clear = LLONG_MIN;
 161
 162     unsigned int bit_index = hash & (HIT_BITS - 1);
 163     unsigned int word_index = bit_index / BITS_PER_WORD;
 164     unsigned int word_mask = 1u << (bit_index % BITS_PER_WORD);
 165
 166     /* Expire coverage hash suppression once a day. */
 167     if (time_msec() >= next_clear) {
 168         memset(hit, 0, sizeof hit);
 169         next_clear = time_msec() + 60 * 60 * 24 * 1000LL;
 170     }
 171
 172     if (hit[word_index] & word_mask) {
 173         return true;
 174     } else {
 175         hit[word_index] |= word_mask;
 176         return false;
 177     }
 178 }
 179
 180 /* Logs the coverage counters, unless a similar set of events has already been
 181  * logged.
 182  *
 183  * This function logs at log level VLL_INFO.  Use care before adjusting this
 184  * level, because depending on its configuration, syslogd can write changes
 185  * synchronously, which can cause the coverage messages to take several seconds
 186  * to write. */
 187 void
 188 coverage_log(void)
 189 {
 190     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 3);
 191
 192     if (!VLOG_DROP_INFO(&rl)) {
 193         uint32_t hash = coverage_hash();
 194         if (coverage_hit(hash)) {
 195             VLOG_INFO("Skipping details of duplicate event coverage for "
 196                       "hash=%08"PRIx32, hash);
 197         } else {
 198             struct svec lines;
 199             const char *line;
 200             size_t i;
 201
 202             svec_init(&lines);
 203             coverage_read(&lines);
 204             SVEC_FOR_EACH (i, line, &lines) {
 205                 VLOG_INFO("%s", line);
 206             }
 207             svec_destroy(&lines);
 208         }
 209     }
 210 }
 211
 212 /* Adds coverage counter information to 'lines'. */
 213 static void
 214 coverage_read(struct svec *lines)
 215 {
 216     struct coverage_counter **c = coverage_counters;
 217     unsigned long long int *totals;
 218     size_t n_never_hit;
 219     uint32_t hash;
 220     size_t i;
 221
 222     hash = coverage_hash();
 223
 224     n_never_hit = 0;
 225     svec_add_nocopy(lines,
 226                     xasprintf("Event coverage, avg rate over last: %d "
 227                               "seconds, last minute, last hour,  "
 228                               "hash=%08"PRIx32":",
 229                               COVERAGE_RUN_INTERVAL/1000, hash));
 230
 231     totals = xmalloc(n_coverage_counters * sizeof *totals);
 232     ovs_mutex_lock(&coverage_mutex);
 233     for (i = 0; i < n_coverage_counters; i++) {
 234         totals[i] = c[i]->total;
 235     }
 236     ovs_mutex_unlock(&coverage_mutex);
 237
 238     for (i = 0; i < n_coverage_counters; i++) {
 239         if (totals[i]) {
 240             /* Shows the averaged per-second rates for the last
 241              * COVERAGE_RUN_INTERVAL interval, the last minute and
 242              * the last hour. */
 243             svec_add_nocopy(lines,
 244                 xasprintf("%-24s %5.1f/sec %9.3f/sec "
 245                           "%13.4f/sec   total: %llu",
 246                           c[i]->name,
 247                           (c[i]->min[(idx_count - 1) % MIN_AVG_LEN]
 248                            * 1000.0 / COVERAGE_RUN_INTERVAL),
 249                           coverage_array_sum(c[i]->min, MIN_AVG_LEN) / 60.0,
 250                           coverage_array_sum(c[i]->hr,  HR_AVG_LEN) / 3600.0,
 251                           totals[i]));
 252         } else {
 253             n_never_hit++;
 254         }
 255     }
 256
 257     svec_add_nocopy(lines, xasprintf("%zu events never hit", n_never_hit));
 258     free(totals);
 259 }
 260
 261 void
 262 coverage_clear(void)
 263 {
 264     size_t i;
 265
 266     ovs_mutex_lock(&coverage_mutex);
 267     for (i = 0; i < n_coverage_counters; i++) {
 268         struct coverage_counter *c = coverage_counters[i];
 269         c->total += c->count();
 270     }
 271     ovs_mutex_unlock(&coverage_mutex);
 272 }
 273
 274 /* Runs approximately every COVERAGE_RUN_INTERVAL amount of time to update the
 275  * coverage counters' 'min' and 'hr' array.  'min' array is for cumulating
 276  * per second counts into per minute count.  'hr' array is for cumulating per
 277  * minute counts into per hour count.  Every thread may call this function. */
 278 void
 279 coverage_run(void)
 280 {
 281     /* Defines the moving average array index variables. */
 282     static unsigned int min_idx, hr_idx;
 283     struct coverage_counter **c = coverage_counters;
 284     long long int now;
 285
 286     ovs_mutex_lock(&coverage_mutex);
 287     now = time_msec();
 288     /* Initialize the coverage_run_time. */
 289     if (coverage_run_time == LLONG_MIN) {
 290         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 291     }
 292
 293     if (now >= coverage_run_time) {
 294         size_t i, j;
 295         /* Computes the number of COVERAGE_RUN_INTERVAL slots, since
 296          * it is possible that the actual run interval is multiple of
 297          * COVERAGE_RUN_INTERVAL. */
 298         int slots = (now - coverage_run_time) / COVERAGE_RUN_INTERVAL + 1;
 299
 300         for (i = 0; i < n_coverage_counters; i++) {
 301             unsigned int count, portion;
 302             unsigned int m_idx = min_idx;
 303             unsigned int h_idx = hr_idx;
 304             unsigned int idx = idx_count;
 305
 306             /* Computes the differences between the current total and the one
 307              * recorded in last invocation of coverage_run(). */
 308             count = c[i]->total - c[i]->last_total;
 309             c[i]->last_total = c[i]->total;
 310             /* The count over the time interval is evenly distributed
 311              * among slots by calculating the portion. */
 312             portion = count / slots;
 313
 314             for (j = 0; j < slots; j++) {
 315                 /* Updates the index variables. */
 316                 /* The m_idx is increased from 0 to MIN_AVG_LEN - 1. Every
 317                  * time the m_idx finishes a cycle (a cycle is one minute),
 318                  * the h_idx is incremented by 1. */
 319                 m_idx = idx % MIN_AVG_LEN;
 320                 h_idx = idx / MIN_AVG_LEN;
 321
 322                 c[i]->min[m_idx] = portion + (j == (slots - 1)
 323                                               ? count % slots : 0);
 324                 c[i]->hr[h_idx] = m_idx == 0
 325                                   ? c[i]->min[m_idx]
 326                                   : (c[i]->hr[h_idx] + c[i]->min[m_idx]);
 327                 /* This is to guarantee that h_idx ranges from 0 to 59. */
 328                 idx = (idx + 1) % (MIN_AVG_LEN * HR_AVG_LEN);
 329             }
 330         }
 331
 332         /* Updates the global index variables. */
 333         idx_count = (idx_count + slots) % (MIN_AVG_LEN * HR_AVG_LEN);
 334         min_idx = idx_count % MIN_AVG_LEN;
 335         hr_idx  = idx_count / MIN_AVG_LEN;
 336         /* Updates the run time. */
 337         coverage_run_time = now + COVERAGE_RUN_INTERVAL;
 338     }
 339     ovs_mutex_unlock(&coverage_mutex);
 340 }
 341
 342 static unsigned int
 343 coverage_array_sum(const unsigned int *arr, const unsigned int len)
 344 {
 345     unsigned int sum = 0;
 346     size_t i;
 347
 348     ovs_mutex_lock(&coverage_mutex);
 349     for (i = 0; i < len; i++) {
 350         sum += arr[i];
 351     }
 352     ovs_mutex_unlock(&coverage_mutex);
 353     return sum;
 354 }