Fixes XCC texinfo dependency
[akaros.git] / user / parlib / measure.c
1 /* Copyright (c) 2013 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Userspace functions for various measurements.
6  *
7  * For now, this is built into parlib.  We can pull it out in the future.  Many
8  * of the larger functions are in flux. */
9
10 #include <ros/common.h>
11 #include <tsc-compat.h>
12 #include <math.h>
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <sys/param.h>
16 #include <measure.h>
17
18 /* Basic stats computation and printing.
19  *
20  * All of these expect a 2D collection of samples, where the first array is an
21  * array of arrays of samples.  The first array's members are something like
22  * per-thread samples, where each thread fills in its
23  * data[thread_id][sample_number].  The samples should be ordered in
24  * chronological order.  Ultimately, the sample needs to produce a uint64_t
25  * (e.g. TSC tick). */
26
27 static void init_stats(struct sample_stats *stats)
28 {
29         stats->avg_time = 0;
30         stats->var_time = 0;
31         stats->max_time = 0;
32         stats->min_time = UINT64_MAX;
33         stats->lat_50 = 0;
34         stats->lat_75 = 0;
35         stats->lat_90 = 0;
36         stats->lat_99 = 0;
37         stats->total_samples = 0;
38 }
39
40 /* Could have options for printing for how many rows we want, how much we want
41  * to trim the max/min, and how many samples per bin. */
42 void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats)
43 {
44         uint64_t sample_time, hist_max_time, hist_min_time,
45                  lat_max_time, lat_min_time;
46         size_t hist_idx, lat_idx, hist_bin_sz, lat_bin_sz;
47         float accum_samples = 0.0, coef_var;
48         unsigned int *hist_times;
49         unsigned int *lat_times;
50         unsigned int nr_hist_bins = 75;         /* looks reasonable when printed */
51         unsigned int nr_lat_bins = 500;         /* affects granularity of lat perc */
52         unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
53         unsigned int max_hist_bin = 0;
54         #define HI_COEF_VAR 1.0
55
56         init_stats(stats);
57         /* First pass, figure out the min, max, avg, etc. */
58         for (int i = 0; i < nr_i; i++) {
59                 for (int j = 0; j < nr_j; j++) {
60                         /* get_sample returns 0 on success.  o/w, skip the sample */
61                         if (stats->get_sample(data, i, j, &sample_time))
62                                 continue;       /* depending on semantics, we could break */
63                         stats->total_samples++;
64                         stats->avg_time += sample_time;
65                         stats->max_time = sample_time > stats->max_time ? sample_time
66                                                                         : stats->max_time;
67                         stats->min_time = sample_time < stats->min_time ? sample_time
68                                                                         : stats->min_time;
69                 }
70         }
71         if (stats->total_samples < 2) {
72                 printf("Not enough samples (%d) for avg and var\n",
73                        stats->total_samples);
74                 return;
75         }
76         stats->avg_time /= stats->total_samples;
77         /* Second pass, compute the variance.  Want to do this before the
78          * histograms, so we can trim the serious outliers */
79         for (int i = 0; i < nr_i; i++) {
80                 for (int j = 0; j < nr_j; j++) {
81                         if (stats->get_sample(data, i, j, &sample_time))
82                                 continue;
83                         /* var: (sum_i=1..n { (x_i - xbar)^2 }) / (n - 1) */
84                         stats->var_time += (sample_time - stats->avg_time) *
85                                            (sample_time - stats->avg_time);
86                 }
87         }
88         stats->var_time /= stats->total_samples - 1;
89         /* We have two histogram structures.  The main one is for printing, and the
90          * other is for computing latency percentiles.  The only real diff btw the
91          * two is the number of bins.  The latency one has a lot more, for finer
92          * granularity, and the regular one has fewer for better printing.
93          *
94          * Both have the same max and min bin values.  Any excesses get put in the
95          * smallest or biggest bin.  This keeps the granularity reasonable in the
96          * face of very large outliers.  Normally, I trim off anything outside 3
97          * stddev.
98          * 
99          * High variation will throw off our histogram bins, so we adjust.  A
100          * coef_var > 1 is considered high variance.  The numbers I picked are just
101          * heuristics to catch SMM interference and make the output look nice. */
102         coef_var = sqrt(stats->var_time) / stats->avg_time;
103         if (coef_var > HI_COEF_VAR) {
104                 hist_max_time = stats->avg_time * 3;
105                 hist_min_time = stats->avg_time / 3;
106         } else {        /* 'normal' data */
107                 /* trimming the printable hist at 3 stddevs, which for normal data is
108                  * 99.7% of the data.  For most any data, it gets 89% (Chebyshev's
109                  * inequality) */
110                 hist_max_time = stats->avg_time + 3 * sqrt(stats->var_time);
111                 hist_min_time = stats->avg_time - 3 * sqrt(stats->var_time);
112                 if (hist_min_time > hist_max_time)
113                         hist_min_time = 0;
114         }
115         lat_max_time = hist_max_time;
116         lat_min_time = hist_min_time;
117         hist_bin_sz = (hist_max_time - hist_min_time) / nr_hist_bins + 1;
118         lat_bin_sz = (lat_max_time - lat_min_time) / nr_lat_bins + 1;
119         hist_times = malloc(sizeof(unsigned int) * nr_hist_bins);
120         lat_times = malloc(sizeof(unsigned int) * nr_lat_bins);
121         if (!hist_times || !lat_times) {
122                 perror("compute_stats failed to alloc hist/lat arrays:");
123                 free(hist_times);
124                 free(lat_times);
125                 return;
126         }
127         memset(hist_times, 0, sizeof(unsigned int) * nr_hist_bins);
128         memset(lat_times, 0, sizeof(unsigned int) * nr_lat_bins);
129         /* third pass, fill the bins for the histogram and latencies */
130         for (int i = 0; i < nr_i; i++) {
131                 for (int j = 0; j < nr_j; j++) {
132                         if (stats->get_sample(data, i, j, &sample_time))
133                                 continue;
134                         /* need to shift, offset by min_time.  anything too small is 0 and
135                          * will go into the first bin.  anything too large will go into the
136                          * last bin. */
137                         lat_idx = sample_time < lat_min_time
138                                   ? 0
139                                   : (sample_time - lat_min_time) / lat_bin_sz;
140                         lat_idx = MIN(lat_idx, nr_lat_bins - 1);
141                         lat_times[lat_idx]++;
142                         hist_idx = sample_time < hist_min_time
143                                    ? 0
144                                    : (sample_time - hist_min_time) / hist_bin_sz;
145                         hist_idx = MIN(hist_idx, nr_hist_bins - 1);
146                         hist_times[hist_idx]++;
147                         /* useful for formatting the ***s */
148                         max_hist_bin = (hist_times[hist_idx] > max_hist_bin)
149                                        ? hist_times[hist_idx]
150                                        : max_hist_bin;
151                 }
152         }
153         /* Compute latency percentiles */
154         for (int i = 0; i < nr_lat_bins; i++) {
155                 accum_samples += lat_times[i];
156                 /* (i + 1), since we've just accumulated one bucket's worth */
157                 if (!stats->lat_50 && accum_samples / stats->total_samples > 0.50)
158                         stats->lat_50 = (i + 1) * lat_bin_sz + lat_min_time;
159                 if (!stats->lat_75 && accum_samples / stats->total_samples > 0.75)
160                         stats->lat_75 = (i + 1) * lat_bin_sz + lat_min_time;
161                 if (!stats->lat_90 && accum_samples / stats->total_samples > 0.90)
162                         stats->lat_90 = (i + 1) * lat_bin_sz + lat_min_time;
163                 if (!stats->lat_99 && accum_samples / stats->total_samples > 0.99)
164                         stats->lat_99 = (i + 1) * lat_bin_sz + lat_min_time;
165         }
166         for (int i = 0; i < nr_hist_bins; i++) {
167                 uint64_t interval_start = i * hist_bin_sz + hist_min_time;
168                 uint64_t interval_end = (i + 1) * hist_bin_sz + hist_min_time;
169                 /* customize the first and last entries */
170                 if (i == 0)
171                         interval_start = MIN(interval_start, stats->min_time);
172                 if (i == nr_hist_bins - 1) {
173                         interval_end = MAX(interval_end, stats->max_time);
174                         /* but not at the sake of formatting! (8 spaces) */
175                         interval_end = MIN(interval_end, 99999999);
176                 }
177                 printf("    [%8llu - %8llu] %7d: ", interval_start, interval_end,
178                        hist_times[i]);
179                 /* nr_dots = hist_times[i] * nr_dots_per_sample
180                  *         = hist_times[i] * (max_num_dots / max_hist_bin) */
181                 int nr_dots = hist_times[i] * max_dots_per_row / max_hist_bin;
182                 for (int j = 0; j < nr_dots; j++)
183                         printf("*");
184                 printf("\n");
185         }
186         printf("\n");
187         printf("Samples per dot: %d\n", max_hist_bin / max_dots_per_row);
188         printf("Total samples: %llu\n", stats->total_samples);
189         printf("Avg time   : %llu\n", stats->avg_time);
190         printf("Stdev time : %f\n", sqrt(stats->var_time));
191         printf("Coef Var   : %f\n", coef_var);
192         if (coef_var > HI_COEF_VAR)
193                 printf("\tHigh coeff of var with serious outliers, adjusted bins\n");
194         /* numbers are overestimates by at most a lat bin */
195         printf("50/75/90/99: %d / %d / %d / %d (-<%d)\n", stats->lat_50,
196                stats->lat_75, stats->lat_90, stats->lat_99, lat_bin_sz);
197         printf("Min / Max  : %llu / %llu\n", stats->min_time, stats->max_time);
198         printf("\n");
199         free(hist_times);
200         free(lat_times);
201 }
202
203 /* Prints the throughput of certain events over nr_steps of interval time.  Will
204  * print the overall throughput of the entire time (total events / steps),
205  * and print out each step up to nr_print_steps.
206  *
207  * Assumes a 2D data structure, where the events in each data[i][] (for a
208  * specific i) are in order.  The 'nr_i'es are typically threads or something
209  * similar.  nr_j would be how many samples per thread.  The func ptr should
210  * return the time of the data[i][j]'th event via *sample and return 0 on
211  * success, and any other value for 'no data'.  If start_time is 0, we'll start
212  * the clock right before the first event. */
213 void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
214                       unsigned int nr_print_steps, uint64_t start_time,
215                       int nr_i, int nr_j,
216                       int (*get_sample)(void **data, int i, int j,
217                                         uint64_t *sample))
218 {
219         uint64_t time_now, sample;
220         /* next_sample[] tracks each thread's next lock that was acquired */
221         unsigned int *next_sample;
222         unsigned int *step_events;
223         unsigned int most_step_events = 1;
224         unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
225         unsigned int total_events = 0;
226
227         if (!nr_steps)
228                 return;
229         nr_print_steps = MIN(nr_print_steps, nr_steps);
230         next_sample = malloc(sizeof(unsigned int) * nr_i);
231         step_events = malloc(sizeof(unsigned int) * nr_steps);
232         if (!next_sample || !step_events) {
233                 perror("print_throughput failed alloc:");
234                 free(next_sample);
235                 free(step_events);
236                 return;
237         }
238         memset(next_sample, 0, sizeof(unsigned int) * nr_i);
239         memset(step_events, 0, sizeof(unsigned int) * nr_steps);
240         if (start_time) {
241                 time_now = start_time;
242         } else {
243                 time_now = UINT64_MAX;
244                 /* Set the replay to start right before the first event */
245                 for (int i = 0; i < nr_i; i++) {
246                         if (get_sample(data, i, 0, &sample))
247                                 continue;
248                         time_now = MIN(time_now, sample);
249                 }
250                 if (time_now != 0)
251                         time_now--;
252         }
253         for (int k = 0; k < nr_steps; k++) {
254                 time_now += interval;
255                 /* for every 'thread', we'll figure out how many events occurred, and
256                  * advance next_sample to track the next one to consider */
257                 for (int i = 0; i < nr_i; i++) {
258                         /* count nr locks that have happened, advance per thread tracker */
259                         for ( ; next_sample[i] < nr_j; next_sample[i]++) {
260                                 /* skip this thread if it has no more data */
261                                 if (get_sample(data, i, next_sample[i], &sample))
262                                         continue;
263                                 /* break when we found one that hasn't happened yet */
264                                 if (!(sample <= time_now))
265                                         break;
266                                 step_events[k]++;
267                         }
268                 }
269                 total_events += step_events[k];
270                 /* for dynamically scaling the *'s */
271                 most_step_events = MAX(most_step_events, step_events[k]);
272         }
273         if (nr_print_steps)
274                 printf("Events per dot: %d\n", most_step_events / max_dots_per_row);
275         for (int k = 0; k < nr_print_steps; k++) {
276                 /* Last step isn't accurate, will only be partially full */
277                 if (k == nr_steps - 1)
278                         break;
279                 printf("%6d: ", k);
280                 printf("%6d ", step_events[k]);
281                 /* nr_dots = step_events[k] * nr_dots_per_event
282                  *         = step_events[k] * (max_dots_per_row / most_step_events) */
283                 int nr_dots = step_events[k] * max_dots_per_row / most_step_events;
284                 for (int i = 0; i < nr_dots; i++)
285                         printf("*");
286                 printf("\n");
287         }
288         printf("Total events: %d, Avg events/step: %d\n", total_events,
289                total_events / nr_steps);
290         free(next_sample);
291         free(step_events);
292 }
293
294 /* Conversion btw tsc ticks and time units.  From Akaros's kern/src/time.c */
295
296 /* We can overflow/wraparound when we multiply up, but we have to divide last,
297  * or else we lose precision.  If we're too big and will overflow, we'll
298  * sacrifice precision for correctness, and degrade to the next lower level
299  * (losing 3 digits worth).  The recursive case shouldn't overflow, since it
300  * called something that scaled down the tsc_time by more than 1000. */
301 uint64_t tsc2sec(uint64_t tsc_time)
302 {
303         return tsc_time / get_tsc_freq();
304 }
305
306 uint64_t tsc2msec(uint64_t tsc_time)
307 {
308         if (mult_will_overflow_u64(tsc_time, 1000))
309                 return tsc2sec(tsc_time) * 1000;
310         else 
311                 return (tsc_time * 1000) / get_tsc_freq();
312 }
313
314 uint64_t tsc2usec(uint64_t tsc_time)
315 {
316         if (mult_will_overflow_u64(tsc_time, 1000000))
317                 return tsc2msec(tsc_time) * 1000;
318         else
319                 return (tsc_time * 1000000) / get_tsc_freq();
320 }
321
322 uint64_t tsc2nsec(uint64_t tsc_time)
323 {
324         if (mult_will_overflow_u64(tsc_time, 1000000000))
325                 return tsc2usec(tsc_time) * 1000;
326         else
327                 return (tsc_time * 1000000000) / get_tsc_freq();
328 }
329
330 uint64_t sec2tsc(uint64_t sec)
331 {
332         if (mult_will_overflow_u64(sec, get_tsc_freq()))
333                 return (uint64_t)(-1);
334         else
335                 return sec * get_tsc_freq();
336 }
337
338 uint64_t msec2tsc(uint64_t msec)
339 {
340         if (mult_will_overflow_u64(msec, get_tsc_freq()))
341                 return sec2tsc(msec / 1000);
342         else
343                 return (msec * get_tsc_freq()) / 1000;
344 }
345
346 uint64_t usec2tsc(uint64_t usec)
347 {
348         if (mult_will_overflow_u64(usec, get_tsc_freq()))
349                 return msec2tsc(usec / 1000);
350         else
351                 return (usec * get_tsc_freq()) / 1000000;
352 }
353
354 uint64_t nsec2tsc(uint64_t nsec)
355 {
356         if (mult_will_overflow_u64(nsec, get_tsc_freq()))
357                 return usec2tsc(nsec / 1000);
358         else
359                 return (nsec * get_tsc_freq()) / 1000000000;
360 }