lib/coverage.c

   1 /*
   2  * Copyright (c) 2009 Nicira Networks.
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include <config.h>
  18 #include "coverage.h"
  19 #include <inttypes.h>
  20 #include <stdlib.h>
  21 #include "coverage-counters.h"
  22 #include "dynamic-string.h"
  23 #include "hash.h"
  24 #include "util.h"
  25
  26 #define THIS_MODULE VLM_coverage
  27 #include "vlog.h"
  28
  29 static unsigned int epoch;
  30
  31 /* Sorts coverage counters in descending order by count, within equal counts
  32  * alphabetically by name. */
  33 static int
  34 compare_coverage_counters(const void *a_, const void *b_)
  35 {
  36     const struct coverage_counter *const *ap = a_;
  37     const struct coverage_counter *const *bp = b_;
  38     const struct coverage_counter *a = *ap;
  39     const struct coverage_counter *b = *bp;
  40     if (a->count != b->count) {
  41         return a->count < b->count ? 1 : -1;
  42     } else {
  43         return strcmp(a->name, b->name);
  44     }
  45 }
  46
  47 static uint32_t
  48 coverage_hash(void)
  49 {
  50     struct coverage_counter **c;
  51     uint32_t hash = 0;
  52     int n_groups, i;
  53
  54     /* Sort coverage counters into groups with equal counts. */
  55     c = xmalloc(coverage_n_counters * sizeof *c);
  56     for (i = 0; i < coverage_n_counters; i++) {
  57         c[i] = coverage_counters[i];
  58     }
  59     qsort(c, coverage_n_counters, sizeof *c, compare_coverage_counters);
  60
  61     /* Hash the names in each group along with the rank. */
  62     n_groups = 0;
  63     for (i = 0; i < coverage_n_counters; ) {
  64         int j;
  65
  66         if (!c[i]->count) {
  67             break;
  68         }
  69         n_groups++;
  70         hash = hash_int(i, hash);
  71         for (j = i; j < coverage_n_counters; j++) {
  72             if (c[j]->count != c[i]->count) {
  73                 break;
  74             }
  75             hash = hash_string(c[j]->name, hash);
  76         }
  77         i = j;
  78     }
  79
  80     free(c);
  81
  82     return hash_int(n_groups, hash);
  83 }
  84
  85 static bool
  86 coverage_hit(uint32_t hash)
  87 {
  88     enum { HIT_BITS = 1024, BITS_PER_WORD = 32 };
  89     static uint32_t hit[HIT_BITS / BITS_PER_WORD];
  90     BUILD_ASSERT_DECL(IS_POW2(HIT_BITS));
  91
  92     unsigned int bit_index = hash & (HIT_BITS - 1);
  93     unsigned int word_index = bit_index / BITS_PER_WORD;
  94     unsigned int word_mask = 1u << (bit_index % BITS_PER_WORD);
  95
  96     if (hit[word_index] & word_mask) {
  97         return true;
  98     } else {
  99         hit[word_index] |= word_mask;
 100         return false;
 101     }
 102 }
 103
 104 static void
 105 coverage_log_counter(enum vlog_level level, const struct coverage_counter *c)
 106 {
 107     VLOG(level, "%-24s %5u / %9llu", c->name, c->count, c->count + c->total);
 108 }
 109
 110 /* Logs the coverage counters at the given vlog 'level'. */
 111 void
 112 coverage_log(enum vlog_level level)
 113 {
 114     size_t n_never_hit;
 115     uint32_t hash;
 116     size_t i;
 117
 118     if (!vlog_is_enabled(THIS_MODULE, level)) {
 119         return;
 120     }
 121
 122     hash = coverage_hash();
 123     if (coverage_hit(hash)) {
 124         VLOG(level, "Skipping details of duplicate event coverage for "
 125              "hash=%08"PRIx32" in epoch %u", hash, epoch);
 126         return;
 127     }
 128
 129     n_never_hit = 0;
 130     VLOG(level, "Event coverage (epoch %u/entire run), hash=%08"PRIx32":",
 131          epoch, hash);
 132     for (i = 0; i < coverage_n_counters; i++) {
 133         struct coverage_counter *c = coverage_counters[i];
 134         if (c->count) {
 135             coverage_log_counter(level, c);
 136         }
 137     }
 138     for (i = 0; i < coverage_n_counters; i++) {
 139         struct coverage_counter *c = coverage_counters[i];
 140         if (!c->count) {
 141             if (c->total) {
 142                 coverage_log_counter(level, c);
 143             } else {
 144                 n_never_hit++;
 145             }
 146         }
 147     }
 148     VLOG(level, "%zu events never hit", n_never_hit);
 149 }
 150
 151 /* Advances to the next epoch of coverage, resetting all the counters to 0. */
 152 void
 153 coverage_clear(void)
 154 {
 155     size_t i;
 156
 157     epoch++;
 158     for (i = 0; i < coverage_n_counters; i++) {
 159         struct coverage_counter *c = coverage_counters[i];
 160         c->total += c->count;
 161         c->count = 0;
 162     }
 163 }