sljtest.c

Go to the documentation of this file.

#define _GNU_SOURCE

#include <stdio.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>
#include <unistd.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>

#ifdef _WIN32
#include <windows.h>
#include "getopt.h"
#else /* _WIN32 */
#include "replgetopt.h"
#endif /* _WIN32 */

#ifdef  CPU_AFFINITY
#define __USE_GNU
#include <sched.h>
#include "bitmask.h"
#endif  /* CPU_AFFINITY */

#if defined(_WIN32)
#include <sys/timeb.h>
#define WIN32_HIGHRES_TIME
extern int optind;
extern char *optarg;
int getopt(int, char *const *, const char *);
#   define SLEEP_SEC(x) Sleep((x)*1000)

#   define SLEEP_MSEC(x) Sleep(x)

#else

#   define SLEEP_SEC(x) sleep(x)

#   define SLEEP_MSEC(x) \
                do{ \
                        if ((x) >= 1000){ \
                                sleep((x) / 1000); \
                                usleep((x) % 1000 * 1000); \
                        } \
                        else{ \
                                usleep((x)*1000); \
                        } \
                }while (0)
#endif /* _WIN32 */


#define DEF_BINS                20

#define DEF_CPU                 NULL

#define DEF_OUTFILE             NULL

#define DEF_KNEE                50

#define DEF_MIN                 10

#define DEF_OUTBUF              10000

#define DEF_PAUSE               0

#define DEF_RUNTIME             1

#define DEF_SUM                 0

#define DEF_LINEWID             79

#define rdtsc(x) \
        do { \
                uint32_t hi, lo; \
                asm volatile ("rdtsc" : "=a" (lo), "=d" (hi)); \
                x = (uint64_t)hi << 32 | lo; \
        } while (0)

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

typedef struct args_stct {
        int bins;
#ifdef  CPU_AFFINITY

        char *cpu;
#endif  /* CPU_AFFINITY */

        char *outfile;
        uint64_t knee;
        uint64_t min;
        int outbuf;
        int pause;
        int runtime;
        int sum;
        int linewid;
} args_t;

typedef struct bin_stct {
        uint64_t ub;
        int delta_count;
        int delta_sum;
} bin_t;

typedef struct outlier_stct {
        uint64_t when;
        uint64_t delta;
} outlier_t;

args_t args = {
        DEF_BINS,
#ifdef  CPU_AFFINITY
        DEF_CPU,
#endif  /* CPU_AFFINITY */
        DEF_OUTFILE,
        DEF_KNEE,
        DEF_MIN,
        DEF_OUTBUF,
        DEF_PAUSE,
        DEF_RUNTIME,
        DEF_SUM,
        DEF_LINEWID,
};

const struct option OptTable[] = {
        {"bins",    required_argument, NULL, 'b'},
#ifdef  CPU_AFFINITY
        {"cpu",     required_argument, NULL, 'c'},
#endif  /* CPU_AFFINITY */
        {"outfile", required_argument, NULL, 'f'},
        {"help",          no_argument, NULL, 'h'},
        {"knee",    required_argument, NULL, 'k'},
        {"min",     required_argument, NULL, 'm'},
        {"outbuf",  required_argument, NULL, 'o'},
        {"pause",   required_argument, NULL, 'p'},
        {"runtime", required_argument, NULL, 'r'},
        {"sum",           no_argument, NULL, 's'},
        {"width",   required_argument, NULL, 'w'},
};

#ifdef  CPU_AFFINITY
const char *OptString = "b:c:f:hk:m:o:p:r:sw:";
const char *usage = "[-b bins] [-c cpu] [-f file] [-h] [-k knee] [-m min] [-o outbuf] [-p pause] [-r runtime] [-s] [-w width]";

#else   /* CPU_AFFINITY */
const char *OptString = "b:f:hk:m:o:p:r:sw:";
const char *usage = "[-b bins] [-f file] [-h] [-k knee] [-m min] [-o outbuf] [-p pause] [-r runtime] [-s] [-w width]";
#endif  /* CPU_AFFINITY */

const char *version = "SLJ Test 1.0";

bin_t *histo;

outlier_t *outbuf = NULL;
FILE *outfile = NULL;

#ifdef  CPU_AFFINITY

static void
set_affinity(const char* affinity) {
        struct bitmask *bm;

        fprintf(stderr, "Requesting CPU affinity on core %s\n", affinity);
        if ((bm=bitmask_alloc(__CPU_SETSIZE)) == NULL) {
                fprintf(stderr, "bitmask_alloc failed\n");
                exit(1);
        }
        if (bitmask_parselist(affinity, bm) != 0) {
                fprintf(stderr, "bitmask_parselist failed\n");
                exit(1);
        }
        if (sched_setaffinity(0, bitmask_nbytes(bm),
            (cpu_set_t *)bitmask_mask(bm)) < 0) {
                fprintf(stderr, "%s: failed to set affinity to %s\n", affinity);
        }
}
#endif  /* CPU_AFFINITY */

#ifndef HAVE_ASPRINTF

int
#define RET_MAX_LEN 10  /* Maximum length of return string */
asprintf(char **ret, const char *format, ...) {
        va_list ap;

        va_start(ap, format);
        if ((*ret=malloc(RET_MAX_LEN)) == NULL) {
                fprintf(stderr, "asprintf: malloc() failed\n");
                return(-1);
        }
        vsnprintf(*ret, RET_MAX_LEN, format, ap);
        va_end(ap);
        return(0);
}
#endif  /* HAVE_ASPRINTF */

char *
t2ts(uint64_t ticks, double tpns) {
        double ns = ticks/tpns;
        char *s;

             if (ns < 1E3 ) asprintf(&s, "%4.3gns", ns);
        else if (ns < 1E6 ) asprintf(&s, "%4.3gus", ns/1E3);
        else if (ns < 1E9 ) asprintf(&s, "%4.3gms", ns/1E6);
        else if (ns < 1E12) asprintf(&s, "%4.3gs",  ns/1E9);
        else                asprintf(&s, "Infini");

        return (s);
}

/*
 * \brief  Parse command line arguments.
 * \param  argc Count of arguments as passed to main().
 * \param  argv Argument vector as passed to main().
 * \return 0 if no parse errors, 1 otherwise.
 */
int
args_parse(int argc, char *argv[]) {
        int c;

        while ((c=getopt_long(argc, argv, OptString, OptTable, NULL)) != EOF) {
                switch (c) {

                case 'b':
                        args.bins    = atoi(optarg);
                        break;

#ifdef  CPU_AFFINITY
                case 'c':
                        args.cpu     = strdup(optarg);
                        break;
#endif  /* CPU_AFFINITY */

                case 'f':
                        args.outfile = strdup(optarg);
                        break;

                case 'k':
                        args.knee    = atoi(optarg);
                        break;

                case 'm':
                        args.min     = atoi(optarg);
                        break;

                case 'p':
                        args.pause   = atoi(optarg);
                        break;

                case 'r':
                        args.runtime = atoi(optarg);
                        break;

                case 's':
                        args.sum++;
                        break;

                case 'w':
                        args.linewid = atoi(optarg);
                        break;

                case 'h':
                default:
                        return (1);
                }
        }
        return (0);
}

void
outliers_setup() {
        if ((outbuf=(outlier_t *)calloc(args.outbuf, sizeof(outlier_t))) == NULL) {
                fprintf(stderr, "Couldn't allocate memory for outlier buffer\n");
                exit(1);
        }
        if ((outfile=fopen(args.outfile, "w")) == NULL) {
                fprintf(stderr, "Unable to create outliers file %s\n",
                    args.outfile);
                perror(args.outfile);
                exit(1);
        }
}

void
histo_setup() {
        bin_t *bp;

        /* Allocate memory for histogram */
        if ((histo=(bin_t *)malloc(sizeof(bin_t)*args.bins)) == NULL) {
                fprintf(stderr, "Couldn't allocate memory for histogram bins\n");
                exit(1);
        }

        /*
         * Fill first half of histogram table with values up to knee.
         * Evenly divide upper bound values through knee among bins.
         */
        for (bp=histo; bp<histo+(args.bins/2); bp++) {
                bp->ub = args.min+(args.knee-args.min)*(bp-histo+1)/(args.bins/2);
                bp->delta_count = 0;
                bp->delta_sum   = 0;
        }
        /* Fill second half of histogram table with values above knee */
        /* Advance each bin upper bound by 1/2 an order of magnitude */
        uint64_t mult = args.knee;
        for (        ; bp<histo+args.bins; bp++) {
                bp->ub = mult*2;
                bp->delta_count = 0;
                bp->delta_sum   = 0;
                bp++;

                mult *= 10;
                bp->ub = mult;
                bp->delta_count = 0;
                bp->delta_sum   = 0;
        }
        histo[args.bins-1].ub = UINT64_MAX;     /* Sentinel */
}

int
main(int argc, char *argv[]) {
        int errflag;
        uint64_t start_us, stop_us, now_us; /* Start, stop, and time now in microseconds */
        uint64_t start_tsc, stop_tsc;   /* Start and stop in TSC ticks */
        bin_t *bp;
        uint64_t deltas[10], *dp;
        uint64_t min, max;              /* Min and max deltas (ticks) */
        struct timeval now_gtod;        /* Time now as timeval */
        /* The following two headers are assumed to have the same string length */
        const char *cnt_graph_hdr = "Time    Ticks    Count        Percent    Cumulative  ";
        const char *sum_graph_hdr = "Time    Ticks    Sum          Percent    Cumulative  ";
        const char *graph_str = "*******************************************************************";
        outlier_t *obp;         /* Pointer to next open entry in outlier buffer */
        int didwrap;            /* True when outlier buffer wrapped around */

        errflag = args_parse(argc, argv);

        /* Argument validity checks */
        if (args.knee <= args.min) {
                fprintf(stderr, "Min (%" PRIu64
                    ") must be < knee (%" PRIu64 ")\n",
                    args.min, args.knee);
                errflag++;
        }
        if (args.knee-args.min < args.bins/2) {
                fprintf(stderr, "Too few (%" PRIu64
                    ") discrete values between min (%" PRIu64
                    ") and knee (%" PRIu64 ") for linear histogram bins (%d)\n",
                    args.knee-args.min, args.min, args.knee, args.bins/2);
                errflag++;
        }
        if (args.linewid < strlen(cnt_graph_hdr)+1) {
                fprintf(stderr, "Minimum line width is %zd\n", strlen(cnt_graph_hdr)+1);
                errflag++;
        }
        if (args.linewid > strlen(cnt_graph_hdr)+strlen(graph_str)) {
                fprintf(stderr, "Maximum line width is %zd\n",
                strlen(cnt_graph_hdr)+strlen(graph_str));
                errflag++;
        }

        if (errflag) {
                fprintf(stderr, "%s\n%s %s\n", version, argv[0], usage);
                exit(1);
        }

#ifdef  CPU_AFFINITY
        if (args.cpu != NULL)
                set_affinity(args.cpu);
#endif  /* CPU_AFFINITY */

        if (args.outfile!=NULL && args.outbuf!=0) {
                outliers_setup();       /* Set up memory and output file for outliers */
        }

        histo_setup();          /* Set up histogram memory and data structures */

        /*
         * XXX Note that it might get much eaiser to modularize this if in the
         * future if we set up for multiple threads with a per-thread struct here.
         */

        uint64_t timing_ticks = 0;      /* TSC ticks actually spent in timing measurements */
        uint64_t delta_count = 0;       /* Global count of deltas taken */
        uint64_t delta_sum = 0;         /* Global sum of TSC deltas measured */
        min   = UINT64_MAX;
        max   = 0;

        obp = outbuf;
        didwrap = 0;

        /*
         * Variables for computing average and standard deviation.
         * See http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm
         */
        double avg = 0.0;       /* Average delta (ticks) */
        double last_avg;        /* Last average (needed for deviation */
        double svn = 0.0;       /* Standard Variance Numerator */

        rdtsc(start_tsc);
        gettimeofday(&now_gtod, NULL);
        start_us = now_gtod.tv_sec * 1000000 + now_gtod.tv_usec;
        stop_us = start_us + 1000000*args.runtime;

        do {
                dp = deltas;

                if (args.pause)
                        SLEEP_MSEC(args.pause);

                register uint64_t t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10;

                /*
                 * Take a block of 11 timestamps and compute their differences into
                 * a 10-element array.
                 */
                /* Do an "unrolled loop" so there's no branching or other work */
                rdtsc(t0);
                rdtsc(t1);
                rdtsc(t2);
                rdtsc(t3);
                rdtsc(t4);
                rdtsc(t5);
                rdtsc(t6);
                rdtsc(t7);
                rdtsc(t8);
                rdtsc(t9);
                rdtsc(t10);
                *dp++ = t1 -t0;
                *dp++ = t2 -t1;
                *dp++ = t3 -t2;
                *dp++ = t4 -t3;
                *dp++ = t5 -t4;
                *dp++ = t6 -t5;
                *dp++ = t7 -t6;
                *dp++ = t8 -t7;
                *dp++ = t9 -t8;
                *dp++ = t10-t9;

                timing_ticks += t10-t0;

                /*
                 * Now that we're out of the timing loop, we can take all the
                 * CPU we need for analysis.
                 */
                for (dp=deltas; dp<deltas+ARRAY_SIZE(deltas); dp++) {
                        if (*dp < min)
                                min   = *dp;
                        if (*dp > max)
                                max   = *dp;

                        /* Find bin to count this delta */
                        /* Note: no end test is needed because of infinite sentinel */
                        for (bp=histo; *dp>bp->ub; bp++) {}

                        bp->delta_count++;
                        bp->delta_sum += *dp;

                        delta_count++;
                        delta_sum += *dp;

                        last_avg = avg;
                        avg += ((double)*dp-avg)/delta_count;
                        svn += ((double)*dp-avg)*((double)*dp-last_avg);

                        /* If an outlier should be recorded */
                        if (outbuf!=NULL && *dp>args.knee) {
                                /* Assume it happened in middle of block */
                                obp->when = t5;
                                obp->delta = *dp;
                                obp++;
                                /* Wrap around if needed */
                                if (obp-outbuf >= args.outbuf) {
                                        obp = outbuf;
                                        didwrap = 1;
                                }
                        }
                }
                rdtsc(stop_tsc);
                gettimeofday(&now_gtod, NULL);
                now_us = now_gtod.tv_sec * 1000000 + now_gtod.tv_usec;

        } while (now_us < stop_us);

        /* Compute Ticks Per NanoSecond for duration of test */
        double tpns = (stop_tsc-start_tsc)/1000.0/(stop_us-start_us);

        /* Print histogram headers */
        printf("%sGraph ln(Count-e)\n", (args.sum) ? sum_graph_hdr : cnt_graph_hdr);

        /* Find maximum delta count and sum in any histogram bin for scaling graph */
        uint64_t max_count=0, max_sum=0;
        for (bp=histo; bp<histo+args.bins; bp++) {
                if (bp->delta_count > max_count)
                        max_count = bp->delta_count;
                if (bp->delta_sum   > max_sum  )
                        max_sum   = bp->delta_sum  ;
        }

        /* Find a graph scaling value so that the maximum bin is full line width */
        double graph_scale;
        if (args.sum) {
                graph_scale = (double)(args.linewid-strlen(cnt_graph_hdr))/log(((double)max_sum  )-M_E);
        } else {
                graph_scale = (double)(args.linewid-strlen(cnt_graph_hdr))/log(((double)max_count)-M_E);
        }

        /* Print histogram */
        uint64_t c_count = 0;   /* Cumulative delta count as we step through bins */
        uint64_t mid_count = 0; /* Cumulative delta count at histogram midpoint */
        uint64_t c_sum = 0;     /* Cumulative delta sum   as we step through bins */
        uint64_t mid_sum = 0;   /* Cumulative delta sum   at histogram midpoint */
        for (bp=histo; bp<histo+args.bins; bp++) {
                /*
                 * If at midpoint in histogram, record c_count for
                 * knee tuning advice later.
                 */
                if (bp == histo+(args.bins/2)) {
                        mid_count = c_count;
                        mid_sum = c_sum;
                }

                c_count += bp->delta_count;
                c_sum   += bp->delta_sum;

                /* Format bin upper bound nicely into ub_str */
                char *ub_str, ubbuf[99];
                if (bp->ub == UINT64_MAX)
                        ub_str = "Infinite";
                else {
                        sprintf(ubbuf, "%-8" PRIu64, bp->ub);
                        ub_str = ubbuf;
                }

                /*
                 * Compute a logrithmic function on bin delta count or sum
                 * that looks good.
                 */
                int graphwid;
                if (args.sum) {
                        graphwid = graph_scale*log(((double)bp->delta_sum  )-M_E);
                } else {
                        graphwid = graph_scale*log(((double)bp->delta_count)-M_E);
                }

                if (graphwid < 0)
                        graphwid = 0;
                /*
                 * Any nonzero delta count deserves a star, even though floating
                 * point sometimes rounds down to zero stars.
                 */
                if (graphwid==0 && bp->delta_count!=0)
                        graphwid = 1;

                /* Print a row for each bin */
                if (args.sum) {
                        printf("%s  %s %-12d %7.4f%%  %8.4f%%    %*.*s\n",
                            t2ts(bp->ub, tpns), ub_str, bp->delta_sum,
                            100.0*bp->delta_sum/delta_sum, 100.0*c_sum/delta_sum,
                            graphwid, graphwid, graph_str);
                } else {
                        printf("%s  %s %-12d %7.4f%%  %8.4f%%    %*.*s\n",
                            t2ts(bp->ub, tpns), ub_str, bp->delta_count,
                            100.0*bp->delta_count/delta_count, 100.0*c_count/delta_count,
                            graphwid, graphwid, graph_str);
                }

                /* Separate lower 1/2 of histogram from upper 1/2 */
                if (bp-histo+1 == args.bins/2)
                        printf("\n");
        }

        /*
         * Population variance is svn sum computed above over size of population.
         * Population standard deviation is square root of population variance.
         */
        double std_dev = sqrt(svn/delta_count);

        /* Print some useful statistics */
        printf("\nTiming was measured for %s, %5.2f%% of runtime\n",
            t2ts(timing_ticks, tpns), 100.0*timing_ticks/(stop_tsc-start_tsc));
        printf("CPU speed measured  : %7.2f MHz over %" PRIu64 " iterations\n",
            (double)(stop_tsc-start_tsc)/(stop_us-start_us), delta_count);
        printf("Min / Average / Std Dev / Max :   %" PRIu64 "   /   %" PRIu64 "   /  %3.0f   / %" PRIu64 " ticks\n",
            min, delta_sum/delta_count, std_dev, max);
        printf("Min / Average / Std Dev / Max : %s / %s / %s / %s\n",
            t2ts(min, tpns), t2ts(delta_sum/delta_count, tpns),
            t2ts((uint64_t)std_dev, tpns), t2ts(max, tpns));

        /* Analyze histogram to give advice on setting better min and knee */
        if (min<args.min || args.min<0.80*min) {
                printf("Recommend min setting of %3.0f ticks\n", 0.80*min);
        }
        if (outbuf==NULL && 100.0*mid_count/delta_count<90.0) {
                printf("Recommend increasing knee setting from %" PRIu64 " ticks\n",
                    args.knee);
        }
        if (outbuf==NULL && 100.0*mid_count/delta_count>99.0) {
                printf("Recommend decreasing knee setting from %" PRIu64 " ticks\n",
                    args.knee);
        }

        /* Dump log of outliers to outfile */
        /* XXX Why isn't this a compound && test like the above call to outliers_setup()? */
        if (outbuf != NULL) {
                if (didwrap) {
                        printf("Recommend increasing knee setting from %" PRIu64 " ticks\n",
                            args.knee);
                } else if (obp-outbuf < args.outbuf/4) {
                        printf("Recommend decreasing knee setting from %" PRIu64 " ticks\n",
                            args.knee);
                }
                for (obp=outbuf; obp<outbuf+args.outbuf; obp++) {
                        if (obp->when == 0)
                                continue;
                        fprintf(outfile, "%f, %f\n",
                            (obp->when-start_tsc)/tpns/1000000.0,
                            obp->delta/tpns/1000.0);
                }
                fclose(outfile);
        }
        return (0);
}