Reverts -lm error (XCC)
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 30 May 2013 05:56:31 +0000 (22:56 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Thu, 30 May 2013 05:56:31 +0000 (22:56 -0700)
This fixes the change from 6f3a1535f7, where all applications linked
with -lm.  In lieu of libm, parlib won't use any math, and whatever
utilities I come up with will just get dumped in benchutil.

The problem was that the cross-compiler can't bootstrap itself if there
was not an existing installation with -lm.  It would work only after
everything was installed, and it took a reinstall with no existing
toolchain to detect it.

The make process for benchutil was just a copy of parlib's.  We probably
ought to take a better look at all of userspace's makes, including where
we drop files in the toolchain directories.

If you have compilation issues, make clean and rm your toolchain
installation.

GNUmakefile
tests/Makefrag
tools/compilers/gcc-glibc/gcc-4.6.1-ros/gcc/config/ros.h
user/benchutil/Makefile [new file with mode: 0644]
user/benchutil/include/measure.h [new file with mode: 0644]
user/benchutil/measure.c [new file with mode: 0644]
user/parlib/include/measure.h [deleted file]
user/parlib/measure.c [deleted file]

index 53b46e6..7e8dbcf 100644 (file)
@@ -172,7 +172,7 @@ realtests: $(TESTS_EXECS_C) $(TESTS_EXECS_CPP)
 #      @mkdir -p fs/$(TARGET_ARCH)/tests
 #      cp -R $(OBJDIR)/$(TESTS_DIR)/* $(TOP_DIR)/fs/$(TARGET_ARCH)/tests
 
-USER_LIBS = parlib pthread
+USER_LIBS = parlib pthread benchutil
 # for now, c3po can't be built for non-i686
 ifeq ($(TARGET_ARCH),i686)
 USER_LIBS += c3po
index 3766866..e7b13be 100644 (file)
@@ -6,7 +6,7 @@ TESTS_CFLAGS += $(USER_CFLAGS) -g
 TESTS_CXXFLAGS += $(USER_CXXFLAGS) -g
 TESTS_LDFLAGS += $(USER_LDFLAGS)
 
-TESTS_LDLIBS := -lpthread
+TESTS_LDLIBS := -lpthread -lbenchutil -lm
 
 TESTS_SRCS_C = $(shell ls $(TESTS_DIR)/*.c)
 TESTS_SRCS_CPP = $(shell ls $(TESTS_DIR)/*.cc)
index 29fca09..5ff8bbf 100644 (file)
@@ -40,5 +40,5 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 
 #undef LINK_GCC_C_SEQUENCE_SPEC
 #define LINK_GCC_C_SEQUENCE_SPEC \
-  "--whole-archive -lparlib -lm --no-whole-archive " \
+  "--whole-archive -lparlib --no-whole-archive " \
   "%{static:--start-group} %G %L %{static:--end-group}%{!static:%G}"
diff --git a/user/benchutil/Makefile b/user/benchutil/Makefile
new file mode 100644 (file)
index 0000000..09efc1d
--- /dev/null
@@ -0,0 +1,54 @@
+TARGET_ARCH ?= none    # catch bugs
+CFLAGS = -O2 -std=gnu99 -static -fomit-frame-pointer -g
+LIBNAME = benchutil
+V ?= @
+
+GCCPREFIX := $(TARGET_ARCH)-ros-
+CC := $(GCCPREFIX)gcc
+GCC_ROOT := $(shell which $(CC) | xargs dirname)/../
+
+SRCDIR := 
+OBJDIR := $(SRCDIR)obj
+INCDIR = $(SRCDIR)include
+
+INCS = -I. -I$(INCDIR) 
+FINALLIB = $(OBJDIR)/lib$(LIBNAME).a
+
+uc = $(shell echo $(1) | tr a-z A-Z)
+
+LIBUCNAME := $(call uc, $(LIBNAME))
+HEADERS := $(shell find $(INCDIR) -name *.h)
+CFILES  := $(wildcard $(SRCDIR)*.c)
+CFILES  += $(wildcard $(SRCDIR)$(TARGET_ARCH)/*.c)
+SFILES  := $(wildcard $(SRCDIR)$(TARGET_ARCH)/*.S)
+OBJS    := $(patsubst %.c, $(OBJDIR)/%.o, $(CFILES)) \
+           $(patsubst %.S, $(OBJDIR)/%.o, $(SFILES))
+
+all: $(FINALLIB)
+
+$(OBJDIR)/$(TARGET_ARCH)/%.o: $(SRCDIR)$(TARGET_ARCH)/%.S $(HEADERS)
+       @echo + as [$(LIBUCNAME)] $<
+       @mkdir -p $(@D)
+       $(V)$(CC) $(CFLAGS) $(INCS) -o $@ -c $<
+
+$(OBJDIR)/%.o: $(SRCDIR)%.c $(HEADERS)
+       @echo + cc [$(LIBUCNAME)] $<
+       @mkdir -p $(@D)
+       $(V)$(CC) $(CFLAGS) $(INCS) -o $@ -c $<
+
+$(FINALLIB): $(OBJS)
+       @echo + ar [$(LIBUCNAME)] $@
+       @mkdir -p $(@D)
+       $(V)$(AR) rc $@ $(OBJS)
+
+install: $(FINALLIB)
+       cp $(FINALLIB) $(GCC_ROOT)/$(TARGET_ARCH)-ros/lib/
+       cp -R $(INCDIR)/* $(GCC_ROOT)/$(TARGET_ARCH)-ros/sys-include/
+       rm -rf $(GCC_ROOT)/$(TARGET_ARCH)-ros/sys-include/benchutil
+       ln -fs . $(GCC_ROOT)/$(TARGET_ARCH)-ros/sys-include/benchutil
+
+clean: 
+       @echo + clean [$(LIBUCNAME)]
+       $(V)rm -rf $(FINALLIB)
+       $(V)rm -rf $(OBJDIR)
+       
diff --git a/user/benchutil/include/measure.h b/user/benchutil/include/measure.h
new file mode 100644 (file)
index 0000000..ff6a6f3
--- /dev/null
@@ -0,0 +1,52 @@
+/* Copyright (c) 2013 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Userspace functions for various measurements.
+ *
+ * For now, this is built into parlib.  We can pull it out in the future.  Many
+ * of the larger functions are in flux (interfaces, options, etc). */
+
+#include <ros/common.h>
+
+/* Basic stats computation and printing.
+ *
+ * All of these expect a 2D collection of samples, where the first array is an
+ * array of arrays of samples.  The first array's members are something like
+ * per-thread samples, where each thread fills in its
+ * data[thread_id][sample_number].  The samples should be ordered in
+ * chronological order.  Ultimately, the sample needs to produce a uint64_t
+ * (e.g. TSC tick). */
+
+struct sample_stats {
+       int (*get_sample)(void **data, int i, int j, uint64_t *sample);
+       uint64_t                                        avg_time;
+       uint64_t                                        var_time;
+       uint64_t                                        max_time;
+       uint64_t                                        min_time;
+       unsigned int                            lat_50;
+       unsigned int                            lat_75;
+       unsigned int                            lat_90;
+       unsigned int                            lat_99;
+       uint64_t                                        total_samples;
+};
+
+/* Computes basic stats and prints histograms, stats returned via *stats */
+void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats);
+
+/* Prints the throughput of events in **data */
+void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
+                      unsigned int nr_print_steps, uint64_t start_time,
+                      int nr_i, int nr_j,
+                      int (*get_sample)(void **data, int i, int j,
+                                        uint64_t *sample));
+
+/* Conversion btw tsc ticks and time units.  From Akaros's kern/src/time.c */
+uint64_t tsc2sec(uint64_t tsc_time);
+uint64_t tsc2msec(uint64_t tsc_time);
+uint64_t tsc2usec(uint64_t tsc_time);
+uint64_t tsc2nsec(uint64_t tsc_time);
+uint64_t sec2tsc(uint64_t sec);
+uint64_t msec2tsc(uint64_t msec);
+uint64_t usec2tsc(uint64_t usec);
+uint64_t nsec2tsc(uint64_t nsec);
diff --git a/user/benchutil/measure.c b/user/benchutil/measure.c
new file mode 100644 (file)
index 0000000..0ce3071
--- /dev/null
@@ -0,0 +1,360 @@
+/* Copyright (c) 2013 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Userspace functions for various measurements.
+ *
+ * For now, this is built into parlib.  We can pull it out in the future.  Many
+ * of the larger functions are in flux. */
+
+#include <ros/common.h>
+#include <tsc-compat.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/param.h>
+#include <measure.h>
+
+/* Basic stats computation and printing.
+ *
+ * All of these expect a 2D collection of samples, where the first array is an
+ * array of arrays of samples.  The first array's members are something like
+ * per-thread samples, where each thread fills in its
+ * data[thread_id][sample_number].  The samples should be ordered in
+ * chronological order.  Ultimately, the sample needs to produce a uint64_t
+ * (e.g. TSC tick). */
+
+static void init_stats(struct sample_stats *stats)
+{
+       stats->avg_time = 0;
+       stats->var_time = 0;
+       stats->max_time = 0;
+       stats->min_time = UINT64_MAX;
+       stats->lat_50 = 0;
+       stats->lat_75 = 0;
+       stats->lat_90 = 0;
+       stats->lat_99 = 0;
+       stats->total_samples = 0;
+}
+
+/* Could have options for printing for how many rows we want, how much we want
+ * to trim the max/min, and how many samples per bin. */
+void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats)
+{
+       uint64_t sample_time, hist_max_time, hist_min_time,
+                lat_max_time, lat_min_time;
+       size_t hist_idx, lat_idx, hist_bin_sz, lat_bin_sz;
+       float accum_samples = 0.0, coef_var;
+       unsigned int *hist_times;
+       unsigned int *lat_times;
+       unsigned int nr_hist_bins = 75;         /* looks reasonable when printed */
+       unsigned int nr_lat_bins = 500;         /* affects granularity of lat perc */
+       unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
+       unsigned int max_hist_bin = 0;
+       #define HI_COEF_VAR 1.0
+
+       init_stats(stats);
+       /* First pass, figure out the min, max, avg, etc. */
+       for (int i = 0; i < nr_i; i++) {
+               for (int j = 0; j < nr_j; j++) {
+                       /* get_sample returns 0 on success.  o/w, skip the sample */
+                       if (stats->get_sample(data, i, j, &sample_time))
+                               continue;       /* depending on semantics, we could break */
+                       stats->total_samples++;
+                       stats->avg_time += sample_time;
+                       stats->max_time = sample_time > stats->max_time ? sample_time
+                                                                       : stats->max_time;
+                       stats->min_time = sample_time < stats->min_time ? sample_time
+                                                                       : stats->min_time;
+               }
+       }
+       if (stats->total_samples < 2) {
+               printf("Not enough samples (%d) for avg and var\n",
+                      stats->total_samples);
+               return;
+       }
+       stats->avg_time /= stats->total_samples;
+       /* Second pass, compute the variance.  Want to do this before the
+        * histograms, so we can trim the serious outliers */
+       for (int i = 0; i < nr_i; i++) {
+               for (int j = 0; j < nr_j; j++) {
+                       if (stats->get_sample(data, i, j, &sample_time))
+                               continue;
+                       /* var: (sum_i=1..n { (x_i - xbar)^2 }) / (n - 1) */
+                       stats->var_time += (sample_time - stats->avg_time) *
+                                          (sample_time - stats->avg_time);
+               }
+       }
+       stats->var_time /= stats->total_samples - 1;
+       /* We have two histogram structures.  The main one is for printing, and the
+        * other is for computing latency percentiles.  The only real diff btw the
+        * two is the number of bins.  The latency one has a lot more, for finer
+        * granularity, and the regular one has fewer for better printing.
+        *
+        * Both have the same max and min bin values.  Any excesses get put in the
+        * smallest or biggest bin.  This keeps the granularity reasonable in the
+        * face of very large outliers.  Normally, I trim off anything outside 3
+        * stddev.
+        * 
+        * High variation will throw off our histogram bins, so we adjust.  A
+        * coef_var > 1 is considered high variance.  The numbers I picked are just
+        * heuristics to catch SMM interference and make the output look nice. */
+       coef_var = sqrt(stats->var_time) / stats->avg_time;
+       if (coef_var > HI_COEF_VAR) {
+               hist_max_time = stats->avg_time * 3;
+               hist_min_time = stats->avg_time / 3;
+       } else {        /* 'normal' data */
+               /* trimming the printable hist at 3 stddevs, which for normal data is
+                * 99.7% of the data.  For most any data, it gets 89% (Chebyshev's
+                * inequality) */
+               hist_max_time = stats->avg_time + 3 * sqrt(stats->var_time);
+               hist_min_time = stats->avg_time - 3 * sqrt(stats->var_time);
+               if (hist_min_time > hist_max_time)
+                       hist_min_time = 0;
+       }
+       lat_max_time = hist_max_time;
+       lat_min_time = hist_min_time;
+       hist_bin_sz = (hist_max_time - hist_min_time) / nr_hist_bins + 1;
+       lat_bin_sz = (lat_max_time - lat_min_time) / nr_lat_bins + 1;
+       hist_times = malloc(sizeof(unsigned int) * nr_hist_bins);
+       lat_times = malloc(sizeof(unsigned int) * nr_lat_bins);
+       if (!hist_times || !lat_times) {
+               perror("compute_stats failed to alloc hist/lat arrays:");
+               free(hist_times);
+               free(lat_times);
+               return;
+       }
+       memset(hist_times, 0, sizeof(unsigned int) * nr_hist_bins);
+       memset(lat_times, 0, sizeof(unsigned int) * nr_lat_bins);
+       /* third pass, fill the bins for the histogram and latencies */
+       for (int i = 0; i < nr_i; i++) {
+               for (int j = 0; j < nr_j; j++) {
+                       if (stats->get_sample(data, i, j, &sample_time))
+                               continue;
+                       /* need to shift, offset by min_time.  anything too small is 0 and
+                        * will go into the first bin.  anything too large will go into the
+                        * last bin. */
+                       lat_idx = sample_time < lat_min_time
+                                 ? 0
+                                 : (sample_time - lat_min_time) / lat_bin_sz;
+                       lat_idx = MIN(lat_idx, nr_lat_bins - 1);
+                       lat_times[lat_idx]++;
+                       hist_idx = sample_time < hist_min_time
+                                  ? 0
+                                  : (sample_time - hist_min_time) / hist_bin_sz;
+                       hist_idx = MIN(hist_idx, nr_hist_bins - 1);
+                       hist_times[hist_idx]++;
+                       /* useful for formatting the ***s */
+                       max_hist_bin = (hist_times[hist_idx] > max_hist_bin)
+                                      ? hist_times[hist_idx]
+                                      : max_hist_bin;
+               }
+       }
+       /* Compute latency percentiles */
+       for (int i = 0; i < nr_lat_bins; i++) {
+               accum_samples += lat_times[i];
+               /* (i + 1), since we've just accumulated one bucket's worth */
+               if (!stats->lat_50 && accum_samples / stats->total_samples > 0.50)
+                       stats->lat_50 = (i + 1) * lat_bin_sz + lat_min_time;
+               if (!stats->lat_75 && accum_samples / stats->total_samples > 0.75)
+                       stats->lat_75 = (i + 1) * lat_bin_sz + lat_min_time;
+               if (!stats->lat_90 && accum_samples / stats->total_samples > 0.90)
+                       stats->lat_90 = (i + 1) * lat_bin_sz + lat_min_time;
+               if (!stats->lat_99 && accum_samples / stats->total_samples > 0.99)
+                       stats->lat_99 = (i + 1) * lat_bin_sz + lat_min_time;
+       }
+       for (int i = 0; i < nr_hist_bins; i++) {
+               uint64_t interval_start = i * hist_bin_sz + hist_min_time;
+               uint64_t interval_end = (i + 1) * hist_bin_sz + hist_min_time;
+               /* customize the first and last entries */
+               if (i == 0)
+                       interval_start = MIN(interval_start, stats->min_time);
+               if (i == nr_hist_bins - 1) {
+                       interval_end = MAX(interval_end, stats->max_time);
+                       /* but not at the sake of formatting! (8 spaces) */
+                       interval_end = MIN(interval_end, 99999999);
+               }
+               printf("    [%8llu - %8llu] %7d: ", interval_start, interval_end,
+                      hist_times[i]);
+               /* nr_dots = hist_times[i] * nr_dots_per_sample
+                *         = hist_times[i] * (max_num_dots / max_hist_bin) */
+               int nr_dots = hist_times[i] * max_dots_per_row / max_hist_bin;
+               for (int j = 0; j < nr_dots; j++)
+                       printf("*");
+               printf("\n");
+       }
+       printf("\n");
+       printf("Samples per dot: %d\n", max_hist_bin / max_dots_per_row);
+       printf("Total samples: %llu\n", stats->total_samples);
+       printf("Avg time   : %llu\n", stats->avg_time);
+       printf("Stdev time : %f\n", sqrt(stats->var_time));
+       printf("Coef Var   : %f\n", coef_var);
+       if (coef_var > HI_COEF_VAR)
+               printf("\tHigh coeff of var with serious outliers, adjusted bins\n");
+       /* numbers are overestimates by at most a lat bin */
+       printf("50/75/90/99: %d / %d / %d / %d (-<%d)\n", stats->lat_50,
+              stats->lat_75, stats->lat_90, stats->lat_99, lat_bin_sz);
+       printf("Min / Max  : %llu / %llu\n", stats->min_time, stats->max_time);
+       printf("\n");
+       free(hist_times);
+       free(lat_times);
+}
+
+/* Prints the throughput of certain events over nr_steps of interval time.  Will
+ * print the overall throughput of the entire time (total events / steps),
+ * and print out each step up to nr_print_steps.
+ *
+ * Assumes a 2D data structure, where the events in each data[i][] (for a
+ * specific i) are in order.  The 'nr_i'es are typically threads or something
+ * similar.  nr_j would be how many samples per thread.  The func ptr should
+ * return the time of the data[i][j]'th event via *sample and return 0 on
+ * success, and any other value for 'no data'.  If start_time is 0, we'll start
+ * the clock right before the first event. */
+void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
+                      unsigned int nr_print_steps, uint64_t start_time,
+                      int nr_i, int nr_j,
+                      int (*get_sample)(void **data, int i, int j,
+                                        uint64_t *sample))
+{
+       uint64_t time_now, sample;
+       /* next_sample[] tracks each thread's next lock that was acquired */
+       unsigned int *next_sample;
+       unsigned int *step_events;
+       unsigned int most_step_events = 1;
+       unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
+       unsigned int total_events = 0;
+
+       if (!nr_steps)
+               return;
+       nr_print_steps = MIN(nr_print_steps, nr_steps);
+       next_sample = malloc(sizeof(unsigned int) * nr_i);
+       step_events = malloc(sizeof(unsigned int) * nr_steps);
+       if (!next_sample || !step_events) {
+               perror("print_throughput failed alloc:");
+               free(next_sample);
+               free(step_events);
+               return;
+       }
+       memset(next_sample, 0, sizeof(unsigned int) * nr_i);
+       memset(step_events, 0, sizeof(unsigned int) * nr_steps);
+       if (start_time) {
+               time_now = start_time;
+       } else {
+               time_now = UINT64_MAX;
+               /* Set the replay to start right before the first event */
+               for (int i = 0; i < nr_i; i++) {
+                       if (get_sample(data, i, 0, &sample))
+                               continue;
+                       time_now = MIN(time_now, sample);
+               }
+               if (time_now != 0)
+                       time_now--;
+       }
+       for (int k = 0; k < nr_steps; k++) {
+               time_now += interval;
+               /* for every 'thread', we'll figure out how many events occurred, and
+                * advance next_sample to track the next one to consider */
+               for (int i = 0; i < nr_i; i++) {
+                       /* count nr locks that have happened, advance per thread tracker */
+                       for ( ; next_sample[i] < nr_j; next_sample[i]++) {
+                               /* skip this thread if it has no more data */
+                               if (get_sample(data, i, next_sample[i], &sample))
+                                       continue;
+                               /* break when we found one that hasn't happened yet */
+                               if (!(sample <= time_now))
+                                       break;
+                               step_events[k]++;
+                       }
+               }
+               total_events += step_events[k];
+               /* for dynamically scaling the *'s */
+               most_step_events = MAX(most_step_events, step_events[k]);
+       }
+       if (nr_print_steps)
+               printf("Events per dot: %d\n", most_step_events / max_dots_per_row);
+       for (int k = 0; k < nr_print_steps; k++) {
+               /* Last step isn't accurate, will only be partially full */
+               if (k == nr_steps - 1)
+                       break;
+               printf("%6d: ", k);
+               printf("%6d ", step_events[k]);
+               /* nr_dots = step_events[k] * nr_dots_per_event
+                *         = step_events[k] * (max_dots_per_row / most_step_events) */
+               int nr_dots = step_events[k] * max_dots_per_row / most_step_events;
+               for (int i = 0; i < nr_dots; i++)
+                       printf("*");
+               printf("\n");
+       }
+       printf("Total events: %d, Avg events/step: %d\n", total_events,
+              total_events / nr_steps);
+       free(next_sample);
+       free(step_events);
+}
+
+/* Conversion btw tsc ticks and time units.  From Akaros's kern/src/time.c */
+
+/* We can overflow/wraparound when we multiply up, but we have to divide last,
+ * or else we lose precision.  If we're too big and will overflow, we'll
+ * sacrifice precision for correctness, and degrade to the next lower level
+ * (losing 3 digits worth).  The recursive case shouldn't overflow, since it
+ * called something that scaled down the tsc_time by more than 1000. */
+uint64_t tsc2sec(uint64_t tsc_time)
+{
+       return tsc_time / get_tsc_freq();
+}
+
+uint64_t tsc2msec(uint64_t tsc_time)
+{
+       if (mult_will_overflow_u64(tsc_time, 1000))
+               return tsc2sec(tsc_time) * 1000;
+       else 
+               return (tsc_time * 1000) / get_tsc_freq();
+}
+
+uint64_t tsc2usec(uint64_t tsc_time)
+{
+       if (mult_will_overflow_u64(tsc_time, 1000000))
+               return tsc2msec(tsc_time) * 1000;
+       else
+               return (tsc_time * 1000000) / get_tsc_freq();
+}
+
+uint64_t tsc2nsec(uint64_t tsc_time)
+{
+       if (mult_will_overflow_u64(tsc_time, 1000000000))
+               return tsc2usec(tsc_time) * 1000;
+       else
+               return (tsc_time * 1000000000) / get_tsc_freq();
+}
+
+uint64_t sec2tsc(uint64_t sec)
+{
+       if (mult_will_overflow_u64(sec, get_tsc_freq()))
+               return (uint64_t)(-1);
+       else
+               return sec * get_tsc_freq();
+}
+
+uint64_t msec2tsc(uint64_t msec)
+{
+       if (mult_will_overflow_u64(msec, get_tsc_freq()))
+               return sec2tsc(msec / 1000);
+       else
+               return (msec * get_tsc_freq()) / 1000;
+}
+
+uint64_t usec2tsc(uint64_t usec)
+{
+       if (mult_will_overflow_u64(usec, get_tsc_freq()))
+               return msec2tsc(usec / 1000);
+       else
+               return (usec * get_tsc_freq()) / 1000000;
+}
+
+uint64_t nsec2tsc(uint64_t nsec)
+{
+       if (mult_will_overflow_u64(nsec, get_tsc_freq()))
+               return usec2tsc(nsec / 1000);
+       else
+               return (nsec * get_tsc_freq()) / 1000000000;
+}
diff --git a/user/parlib/include/measure.h b/user/parlib/include/measure.h
deleted file mode 100644 (file)
index ff6a6f3..0000000
+++ /dev/null
@@ -1,52 +0,0 @@
-/* Copyright (c) 2013 The Regents of the University of California
- * Barret Rhoden <brho@cs.berkeley.edu>
- * See LICENSE for details.
- *
- * Userspace functions for various measurements.
- *
- * For now, this is built into parlib.  We can pull it out in the future.  Many
- * of the larger functions are in flux (interfaces, options, etc). */
-
-#include <ros/common.h>
-
-/* Basic stats computation and printing.
- *
- * All of these expect a 2D collection of samples, where the first array is an
- * array of arrays of samples.  The first array's members are something like
- * per-thread samples, where each thread fills in its
- * data[thread_id][sample_number].  The samples should be ordered in
- * chronological order.  Ultimately, the sample needs to produce a uint64_t
- * (e.g. TSC tick). */
-
-struct sample_stats {
-       int (*get_sample)(void **data, int i, int j, uint64_t *sample);
-       uint64_t                                        avg_time;
-       uint64_t                                        var_time;
-       uint64_t                                        max_time;
-       uint64_t                                        min_time;
-       unsigned int                            lat_50;
-       unsigned int                            lat_75;
-       unsigned int                            lat_90;
-       unsigned int                            lat_99;
-       uint64_t                                        total_samples;
-};
-
-/* Computes basic stats and prints histograms, stats returned via *stats */
-void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats);
-
-/* Prints the throughput of events in **data */
-void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
-                      unsigned int nr_print_steps, uint64_t start_time,
-                      int nr_i, int nr_j,
-                      int (*get_sample)(void **data, int i, int j,
-                                        uint64_t *sample));
-
-/* Conversion btw tsc ticks and time units.  From Akaros's kern/src/time.c */
-uint64_t tsc2sec(uint64_t tsc_time);
-uint64_t tsc2msec(uint64_t tsc_time);
-uint64_t tsc2usec(uint64_t tsc_time);
-uint64_t tsc2nsec(uint64_t tsc_time);
-uint64_t sec2tsc(uint64_t sec);
-uint64_t msec2tsc(uint64_t msec);
-uint64_t usec2tsc(uint64_t usec);
-uint64_t nsec2tsc(uint64_t nsec);
diff --git a/user/parlib/measure.c b/user/parlib/measure.c
deleted file mode 100644 (file)
index 0ce3071..0000000
+++ /dev/null
@@ -1,360 +0,0 @@
-/* Copyright (c) 2013 The Regents of the University of California
- * Barret Rhoden <brho@cs.berkeley.edu>
- * See LICENSE for details.
- *
- * Userspace functions for various measurements.
- *
- * For now, this is built into parlib.  We can pull it out in the future.  Many
- * of the larger functions are in flux. */
-
-#include <ros/common.h>
-#include <tsc-compat.h>
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <sys/param.h>
-#include <measure.h>
-
-/* Basic stats computation and printing.
- *
- * All of these expect a 2D collection of samples, where the first array is an
- * array of arrays of samples.  The first array's members are something like
- * per-thread samples, where each thread fills in its
- * data[thread_id][sample_number].  The samples should be ordered in
- * chronological order.  Ultimately, the sample needs to produce a uint64_t
- * (e.g. TSC tick). */
-
-static void init_stats(struct sample_stats *stats)
-{
-       stats->avg_time = 0;
-       stats->var_time = 0;
-       stats->max_time = 0;
-       stats->min_time = UINT64_MAX;
-       stats->lat_50 = 0;
-       stats->lat_75 = 0;
-       stats->lat_90 = 0;
-       stats->lat_99 = 0;
-       stats->total_samples = 0;
-}
-
-/* Could have options for printing for how many rows we want, how much we want
- * to trim the max/min, and how many samples per bin. */
-void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats)
-{
-       uint64_t sample_time, hist_max_time, hist_min_time,
-                lat_max_time, lat_min_time;
-       size_t hist_idx, lat_idx, hist_bin_sz, lat_bin_sz;
-       float accum_samples = 0.0, coef_var;
-       unsigned int *hist_times;
-       unsigned int *lat_times;
-       unsigned int nr_hist_bins = 75;         /* looks reasonable when printed */
-       unsigned int nr_lat_bins = 500;         /* affects granularity of lat perc */
-       unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
-       unsigned int max_hist_bin = 0;
-       #define HI_COEF_VAR 1.0
-
-       init_stats(stats);
-       /* First pass, figure out the min, max, avg, etc. */
-       for (int i = 0; i < nr_i; i++) {
-               for (int j = 0; j < nr_j; j++) {
-                       /* get_sample returns 0 on success.  o/w, skip the sample */
-                       if (stats->get_sample(data, i, j, &sample_time))
-                               continue;       /* depending on semantics, we could break */
-                       stats->total_samples++;
-                       stats->avg_time += sample_time;
-                       stats->max_time = sample_time > stats->max_time ? sample_time
-                                                                       : stats->max_time;
-                       stats->min_time = sample_time < stats->min_time ? sample_time
-                                                                       : stats->min_time;
-               }
-       }
-       if (stats->total_samples < 2) {
-               printf("Not enough samples (%d) for avg and var\n",
-                      stats->total_samples);
-               return;
-       }
-       stats->avg_time /= stats->total_samples;
-       /* Second pass, compute the variance.  Want to do this before the
-        * histograms, so we can trim the serious outliers */
-       for (int i = 0; i < nr_i; i++) {
-               for (int j = 0; j < nr_j; j++) {
-                       if (stats->get_sample(data, i, j, &sample_time))
-                               continue;
-                       /* var: (sum_i=1..n { (x_i - xbar)^2 }) / (n - 1) */
-                       stats->var_time += (sample_time - stats->avg_time) *
-                                          (sample_time - stats->avg_time);
-               }
-       }
-       stats->var_time /= stats->total_samples - 1;
-       /* We have two histogram structures.  The main one is for printing, and the
-        * other is for computing latency percentiles.  The only real diff btw the
-        * two is the number of bins.  The latency one has a lot more, for finer
-        * granularity, and the regular one has fewer for better printing.
-        *
-        * Both have the same max and min bin values.  Any excesses get put in the
-        * smallest or biggest bin.  This keeps the granularity reasonable in the
-        * face of very large outliers.  Normally, I trim off anything outside 3
-        * stddev.
-        * 
-        * High variation will throw off our histogram bins, so we adjust.  A
-        * coef_var > 1 is considered high variance.  The numbers I picked are just
-        * heuristics to catch SMM interference and make the output look nice. */
-       coef_var = sqrt(stats->var_time) / stats->avg_time;
-       if (coef_var > HI_COEF_VAR) {
-               hist_max_time = stats->avg_time * 3;
-               hist_min_time = stats->avg_time / 3;
-       } else {        /* 'normal' data */
-               /* trimming the printable hist at 3 stddevs, which for normal data is
-                * 99.7% of the data.  For most any data, it gets 89% (Chebyshev's
-                * inequality) */
-               hist_max_time = stats->avg_time + 3 * sqrt(stats->var_time);
-               hist_min_time = stats->avg_time - 3 * sqrt(stats->var_time);
-               if (hist_min_time > hist_max_time)
-                       hist_min_time = 0;
-       }
-       lat_max_time = hist_max_time;
-       lat_min_time = hist_min_time;
-       hist_bin_sz = (hist_max_time - hist_min_time) / nr_hist_bins + 1;
-       lat_bin_sz = (lat_max_time - lat_min_time) / nr_lat_bins + 1;
-       hist_times = malloc(sizeof(unsigned int) * nr_hist_bins);
-       lat_times = malloc(sizeof(unsigned int) * nr_lat_bins);
-       if (!hist_times || !lat_times) {
-               perror("compute_stats failed to alloc hist/lat arrays:");
-               free(hist_times);
-               free(lat_times);
-               return;
-       }
-       memset(hist_times, 0, sizeof(unsigned int) * nr_hist_bins);
-       memset(lat_times, 0, sizeof(unsigned int) * nr_lat_bins);
-       /* third pass, fill the bins for the histogram and latencies */
-       for (int i = 0; i < nr_i; i++) {
-               for (int j = 0; j < nr_j; j++) {
-                       if (stats->get_sample(data, i, j, &sample_time))
-                               continue;
-                       /* need to shift, offset by min_time.  anything too small is 0 and
-                        * will go into the first bin.  anything too large will go into the
-                        * last bin. */
-                       lat_idx = sample_time < lat_min_time
-                                 ? 0
-                                 : (sample_time - lat_min_time) / lat_bin_sz;
-                       lat_idx = MIN(lat_idx, nr_lat_bins - 1);
-                       lat_times[lat_idx]++;
-                       hist_idx = sample_time < hist_min_time
-                                  ? 0
-                                  : (sample_time - hist_min_time) / hist_bin_sz;
-                       hist_idx = MIN(hist_idx, nr_hist_bins - 1);
-                       hist_times[hist_idx]++;
-                       /* useful for formatting the ***s */
-                       max_hist_bin = (hist_times[hist_idx] > max_hist_bin)
-                                      ? hist_times[hist_idx]
-                                      : max_hist_bin;
-               }
-       }
-       /* Compute latency percentiles */
-       for (int i = 0; i < nr_lat_bins; i++) {
-               accum_samples += lat_times[i];
-               /* (i + 1), since we've just accumulated one bucket's worth */
-               if (!stats->lat_50 && accum_samples / stats->total_samples > 0.50)
-                       stats->lat_50 = (i + 1) * lat_bin_sz + lat_min_time;
-               if (!stats->lat_75 && accum_samples / stats->total_samples > 0.75)
-                       stats->lat_75 = (i + 1) * lat_bin_sz + lat_min_time;
-               if (!stats->lat_90 && accum_samples / stats->total_samples > 0.90)
-                       stats->lat_90 = (i + 1) * lat_bin_sz + lat_min_time;
-               if (!stats->lat_99 && accum_samples / stats->total_samples > 0.99)
-                       stats->lat_99 = (i + 1) * lat_bin_sz + lat_min_time;
-       }
-       for (int i = 0; i < nr_hist_bins; i++) {
-               uint64_t interval_start = i * hist_bin_sz + hist_min_time;
-               uint64_t interval_end = (i + 1) * hist_bin_sz + hist_min_time;
-               /* customize the first and last entries */
-               if (i == 0)
-                       interval_start = MIN(interval_start, stats->min_time);
-               if (i == nr_hist_bins - 1) {
-                       interval_end = MAX(interval_end, stats->max_time);
-                       /* but not at the sake of formatting! (8 spaces) */
-                       interval_end = MIN(interval_end, 99999999);
-               }
-               printf("    [%8llu - %8llu] %7d: ", interval_start, interval_end,
-                      hist_times[i]);
-               /* nr_dots = hist_times[i] * nr_dots_per_sample
-                *         = hist_times[i] * (max_num_dots / max_hist_bin) */
-               int nr_dots = hist_times[i] * max_dots_per_row / max_hist_bin;
-               for (int j = 0; j < nr_dots; j++)
-                       printf("*");
-               printf("\n");
-       }
-       printf("\n");
-       printf("Samples per dot: %d\n", max_hist_bin / max_dots_per_row);
-       printf("Total samples: %llu\n", stats->total_samples);
-       printf("Avg time   : %llu\n", stats->avg_time);
-       printf("Stdev time : %f\n", sqrt(stats->var_time));
-       printf("Coef Var   : %f\n", coef_var);
-       if (coef_var > HI_COEF_VAR)
-               printf("\tHigh coeff of var with serious outliers, adjusted bins\n");
-       /* numbers are overestimates by at most a lat bin */
-       printf("50/75/90/99: %d / %d / %d / %d (-<%d)\n", stats->lat_50,
-              stats->lat_75, stats->lat_90, stats->lat_99, lat_bin_sz);
-       printf("Min / Max  : %llu / %llu\n", stats->min_time, stats->max_time);
-       printf("\n");
-       free(hist_times);
-       free(lat_times);
-}
-
-/* Prints the throughput of certain events over nr_steps of interval time.  Will
- * print the overall throughput of the entire time (total events / steps),
- * and print out each step up to nr_print_steps.
- *
- * Assumes a 2D data structure, where the events in each data[i][] (for a
- * specific i) are in order.  The 'nr_i'es are typically threads or something
- * similar.  nr_j would be how many samples per thread.  The func ptr should
- * return the time of the data[i][j]'th event via *sample and return 0 on
- * success, and any other value for 'no data'.  If start_time is 0, we'll start
- * the clock right before the first event. */
-void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
-                      unsigned int nr_print_steps, uint64_t start_time,
-                      int nr_i, int nr_j,
-                      int (*get_sample)(void **data, int i, int j,
-                                        uint64_t *sample))
-{
-       uint64_t time_now, sample;
-       /* next_sample[] tracks each thread's next lock that was acquired */
-       unsigned int *next_sample;
-       unsigned int *step_events;
-       unsigned int most_step_events = 1;
-       unsigned int max_dots_per_row = 45;     /* looks good with 80-wide col */
-       unsigned int total_events = 0;
-
-       if (!nr_steps)
-               return;
-       nr_print_steps = MIN(nr_print_steps, nr_steps);
-       next_sample = malloc(sizeof(unsigned int) * nr_i);
-       step_events = malloc(sizeof(unsigned int) * nr_steps);
-       if (!next_sample || !step_events) {
-               perror("print_throughput failed alloc:");
-               free(next_sample);
-               free(step_events);
-               return;
-       }
-       memset(next_sample, 0, sizeof(unsigned int) * nr_i);
-       memset(step_events, 0, sizeof(unsigned int) * nr_steps);
-       if (start_time) {
-               time_now = start_time;
-       } else {
-               time_now = UINT64_MAX;
-               /* Set the replay to start right before the first event */
-               for (int i = 0; i < nr_i; i++) {
-                       if (get_sample(data, i, 0, &sample))
-                               continue;
-                       time_now = MIN(time_now, sample);
-               }
-               if (time_now != 0)
-                       time_now--;
-       }
-       for (int k = 0; k < nr_steps; k++) {
-               time_now += interval;
-               /* for every 'thread', we'll figure out how many events occurred, and
-                * advance next_sample to track the next one to consider */
-               for (int i = 0; i < nr_i; i++) {
-                       /* count nr locks that have happened, advance per thread tracker */
-                       for ( ; next_sample[i] < nr_j; next_sample[i]++) {
-                               /* skip this thread if it has no more data */
-                               if (get_sample(data, i, next_sample[i], &sample))
-                                       continue;
-                               /* break when we found one that hasn't happened yet */
-                               if (!(sample <= time_now))
-                                       break;
-                               step_events[k]++;
-                       }
-               }
-               total_events += step_events[k];
-               /* for dynamically scaling the *'s */
-               most_step_events = MAX(most_step_events, step_events[k]);
-       }
-       if (nr_print_steps)
-               printf("Events per dot: %d\n", most_step_events / max_dots_per_row);
-       for (int k = 0; k < nr_print_steps; k++) {
-               /* Last step isn't accurate, will only be partially full */
-               if (k == nr_steps - 1)
-                       break;
-               printf("%6d: ", k);
-               printf("%6d ", step_events[k]);
-               /* nr_dots = step_events[k] * nr_dots_per_event
-                *         = step_events[k] * (max_dots_per_row / most_step_events) */
-               int nr_dots = step_events[k] * max_dots_per_row / most_step_events;
-               for (int i = 0; i < nr_dots; i++)
-                       printf("*");
-               printf("\n");
-       }
-       printf("Total events: %d, Avg events/step: %d\n", total_events,
-              total_events / nr_steps);
-       free(next_sample);
-       free(step_events);
-}
-
-/* Conversion btw tsc ticks and time units.  From Akaros's kern/src/time.c */
-
-/* We can overflow/wraparound when we multiply up, but we have to divide last,
- * or else we lose precision.  If we're too big and will overflow, we'll
- * sacrifice precision for correctness, and degrade to the next lower level
- * (losing 3 digits worth).  The recursive case shouldn't overflow, since it
- * called something that scaled down the tsc_time by more than 1000. */
-uint64_t tsc2sec(uint64_t tsc_time)
-{
-       return tsc_time / get_tsc_freq();
-}
-
-uint64_t tsc2msec(uint64_t tsc_time)
-{
-       if (mult_will_overflow_u64(tsc_time, 1000))
-               return tsc2sec(tsc_time) * 1000;
-       else 
-               return (tsc_time * 1000) / get_tsc_freq();
-}
-
-uint64_t tsc2usec(uint64_t tsc_time)
-{
-       if (mult_will_overflow_u64(tsc_time, 1000000))
-               return tsc2msec(tsc_time) * 1000;
-       else
-               return (tsc_time * 1000000) / get_tsc_freq();
-}
-
-uint64_t tsc2nsec(uint64_t tsc_time)
-{
-       if (mult_will_overflow_u64(tsc_time, 1000000000))
-               return tsc2usec(tsc_time) * 1000;
-       else
-               return (tsc_time * 1000000000) / get_tsc_freq();
-}
-
-uint64_t sec2tsc(uint64_t sec)
-{
-       if (mult_will_overflow_u64(sec, get_tsc_freq()))
-               return (uint64_t)(-1);
-       else
-               return sec * get_tsc_freq();
-}
-
-uint64_t msec2tsc(uint64_t msec)
-{
-       if (mult_will_overflow_u64(msec, get_tsc_freq()))
-               return sec2tsc(msec / 1000);
-       else
-               return (msec * get_tsc_freq()) / 1000;
-}
-
-uint64_t usec2tsc(uint64_t usec)
-{
-       if (mult_will_overflow_u64(usec, get_tsc_freq()))
-               return msec2tsc(usec / 1000);
-       else
-               return (usec * get_tsc_freq()) / 1000000;
-}
-
-uint64_t nsec2tsc(uint64_t nsec)
-{
-       if (mult_will_overflow_u64(nsec, get_tsc_freq()))
-               return usec2tsc(nsec / 1000);
-       else
-               return (nsec * get_tsc_freq()) / 1000000000;
-}