AUTHORS: Add James Page.
[sliver-openvswitch.git] / lib / coverage.c
1 /*
2  * Copyright (c) 2009, 2010, 2011, 2012 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(NAME) COVERAGE_DEFINE__(NAME);
39 #include "coverage.def"
40 #undef COVERAGE_COUNTER
41
42 struct coverage_counter *coverage_counters[] = {
43 #define COVERAGE_COUNTER(NAME) &counter_##NAME,
44 #include "coverage.def"
45 #undef COVERAGE_COUNTER
46 };
47 #define n_coverage_counters ARRAY_SIZE(coverage_counters)
48 #endif  /* !USE_LINKER_SECTIONS */
49
50 static unsigned int epoch;
51
52 static void coverage_read(struct svec *);
53
54 static void
55 coverage_unixctl_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
56                      const char *argv[] OVS_UNUSED, void *aux OVS_UNUSED)
57 {
58     struct svec lines;
59     char *reply;
60
61     svec_init(&lines);
62     coverage_read(&lines);
63     reply = svec_join(&lines, "\n", "\n");
64     unixctl_command_reply(conn, reply);
65     free(reply);
66     svec_destroy(&lines);
67 }
68
69 void
70 coverage_init(void)
71 {
72     unixctl_command_register("coverage/show", "", 0, 0,
73                              coverage_unixctl_show, NULL);
74 }
75
76 /* Sorts coverage counters in descending order by count, within equal counts
77  * alphabetically by name. */
78 static int
79 compare_coverage_counters(const void *a_, const void *b_)
80 {
81     const struct coverage_counter *const *ap = a_;
82     const struct coverage_counter *const *bp = b_;
83     const struct coverage_counter *a = *ap;
84     const struct coverage_counter *b = *bp;
85     if (a->count != b->count) {
86         return a->count < b->count ? 1 : -1;
87     } else {
88         return strcmp(a->name, b->name);
89     }
90 }
91
92 static uint32_t
93 coverage_hash(void)
94 {
95     struct coverage_counter **c;
96     uint32_t hash = 0;
97     int n_groups, i;
98
99     /* Sort coverage counters into groups with equal counts. */
100     c = xmalloc(n_coverage_counters * sizeof *c);
101     for (i = 0; i < n_coverage_counters; i++) {
102         c[i] = coverage_counters[i];
103     }
104     qsort(c, n_coverage_counters, sizeof *c, compare_coverage_counters);
105
106     /* Hash the names in each group along with the rank. */
107     n_groups = 0;
108     for (i = 0; i < n_coverage_counters; ) {
109         int j;
110
111         if (!c[i]->count) {
112             break;
113         }
114         n_groups++;
115         hash = hash_int(i, hash);
116         for (j = i; j < n_coverage_counters; j++) {
117             if (c[j]->count != c[i]->count) {
118                 break;
119             }
120             hash = hash_string(c[j]->name, hash);
121         }
122         i = j;
123     }
124
125     free(c);
126
127     return hash_int(n_groups, hash);
128 }
129
130 static bool
131 coverage_hit(uint32_t hash)
132 {
133     enum { HIT_BITS = 1024, BITS_PER_WORD = 32 };
134     static uint32_t hit[HIT_BITS / BITS_PER_WORD];
135     BUILD_ASSERT_DECL(IS_POW2(HIT_BITS));
136
137     static long long int next_clear = LLONG_MIN;
138
139     unsigned int bit_index = hash & (HIT_BITS - 1);
140     unsigned int word_index = bit_index / BITS_PER_WORD;
141     unsigned int word_mask = 1u << (bit_index % BITS_PER_WORD);
142
143     /* Expire coverage hash suppression once a day. */
144     if (time_msec() >= next_clear) {
145         memset(hit, 0, sizeof hit);
146         next_clear = time_msec() + 60 * 60 * 24 * 1000LL;
147     }
148
149     if (hit[word_index] & word_mask) {
150         return true;
151     } else {
152         hit[word_index] |= word_mask;
153         return false;
154     }
155 }
156
157 /* Logs the coverage counters, unless a similar set of events has already been
158  * logged.
159  *
160  * This function logs at log level VLL_INFO.  Use care before adjusting this
161  * level, because depending on its configuration, syslogd can write changes
162  * synchronously, which can cause the coverage messages to take several seconds
163  * to write. */
164 void
165 coverage_log(void)
166 {
167     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 3);
168
169     if (!VLOG_DROP_INFO(&rl)) {
170         uint32_t hash = coverage_hash();
171         if (coverage_hit(hash)) {
172             VLOG_INFO("Skipping details of duplicate event coverage for "
173                       "hash=%08"PRIx32" in epoch %u", hash, epoch);
174         } else {
175             struct svec lines;
176             const char *line;
177             size_t i;
178
179             svec_init(&lines);
180             coverage_read(&lines);
181             SVEC_FOR_EACH (i, line, &lines) {
182                 VLOG_INFO("%s", line);
183             }
184             svec_destroy(&lines);
185         }
186     }
187 }
188
189 static void
190 coverage_read_counter(struct svec *lines, const struct coverage_counter *c)
191 {
192     svec_add_nocopy(lines, xasprintf("%-24s %5u / %9llu",
193                                      c->name, c->count, c->count + c->total));
194 }
195
196 /* Adds coverage counter information to 'lines'. */
197 static void
198 coverage_read(struct svec *lines)
199 {
200     size_t n_never_hit;
201     uint32_t hash;
202     size_t i;
203
204     hash = coverage_hash();
205
206     n_never_hit = 0;
207     svec_add_nocopy(lines, xasprintf("Event coverage (epoch %u/entire run), "
208                                      "hash=%08"PRIx32":", epoch, hash));
209     for (i = 0; i < n_coverage_counters; i++) {
210         struct coverage_counter *c = coverage_counters[i];
211         if (c->count) {
212             coverage_read_counter(lines, c);
213         }
214     }
215     for (i = 0; i < n_coverage_counters; i++) {
216         struct coverage_counter *c = coverage_counters[i];
217         if (!c->count) {
218             if (c->total) {
219                 coverage_read_counter(lines, c);
220             } else {
221                 n_never_hit++;
222             }
223         }
224     }
225     svec_add_nocopy(lines, xasprintf("%zu events never hit", n_never_hit));
226 }
227
228 /* Advances to the next epoch of coverage, resetting all the counters to 0. */
229 void
230 coverage_clear(void)
231 {
232     size_t i;
233
234     epoch++;
235     for (i = 0; i < n_coverage_counters; i++) {
236         struct coverage_counter *c = coverage_counters[i];
237         c->total += c->count;
238         c->count = 0;
239     }
240 }