Add performance counter benchmark.

4 files changed, 427 insertions, 121 deletions

diff --git a/Makefile b/Makefile
index 1a48d8f..f6b865c 100644
--- a/Makefile
+++ b/Makefile
@@ -219,7 +219,7 @@ lib-measure_syscall = -lm
 obj-colortest = colortest.o color.o
 lib-colortest = -static
 
-obj-colorbench = colorbench.o color.o
+obj-colorbench = colorbench.o color.o perfcounters.o common.o
 lib-colorbench = -lpthread -lrt
 
 obj-testcounters = testcounters.o
diff --git a/bin/colorbench.c b/bin/colorbench.c
index cf0b927..de7189a 100644
--- a/bin/colorbench.c
+++ b/bin/colorbench.c
@@ -1,69 +1,83 @@
-#include <stdint.h> /* for uint16_t */
+#include <stdint.h>     /* rt_param needs uint types */
 #include <stdlib.h>
 #include <limits.h>
 #include <pthread.h>
 #include <sched.h>
-#include <sys/mman.h>
 #include <errno.h>
 #include <stdio.h>
-#include <time.h>
 #include <unistd.h>
+#include <sys/mman.h> /* mlockall */
+#include <sys/ioctl.h>
 
 #include <litmus/rt_param.h>
 
+#include "perfcounters.h"
 #include "color.h"
+#include "litmus.h"
 
 #define DEBUG           1
-#define NR_LOOPS        10
-
-/* pick ONE of these */
-#define TIME_MONO       1       /* monotonic time */
-//#define TIME_THREAD   1       /* thread cpu time */
-
-/* Ludwig */
-//#define NR_CPUS               6
-//#define CACHE_SIZE_MB 12
-//#define ASSOC         12
+#define NR_LOOPS        100
 
 /* Pound */
 #define NR_CPUS         4
 #define CACHE_SIZE_MB   8
 #define ASSOC           16
-
-/* VM */
-//#define NR_CPUS               4
-//#define CACHE_SIZE_MB 4
-//#define ASSOC         16
-
 #define LINE_SIZE       64
+
 #define CACHE_SIZE      (CACHE_SIZE_MB * 1024 * 1024)
 #define TOTAL_COLORS    (CACHE_SIZE / ASSOC / PAGE_SIZE)
 
-#define ARENA_PAGES     (arena_size / PAGE_SIZE)
+/* number of colors we actually use */
 #define USE_COLORS      (TOTAL_COLORS >> color_shift)
+
+/* how many adjacent pages of the same color we need to allocate */
 #define CONTIG_COLORS   (ARENA_PAGES / USE_COLORS)
 
+/* number of pages in arena */
+#define ARENA_PAGES     (arena_size / PAGE_SIZE)
+
+/* page offset bit mask */
 #define PAGE_LOWER      ((PAGE_SIZE - 1))
+
+/* number of integers in arena */
 #define ARENA_INTS      (arena_size / sizeof(int))
+
+/* number of pages in arena */
+#define ARENA_PAGES     (arena_size / PAGE_SIZE)
+
+/* number of cache lines in arena */
 #define ARENA_LINES     (arena_size / LINE_SIZE)
 
+/* number of cache lines per page */
+#define PAGE_LINES      (PAGE_SIZE / LINE_SIZE)
+
+/* number of integers in a page */
+#define PAGE_INTS       (PAGE_SIZE / sizeof(int))
+
+/* number of integers in a cache line */
+#define LINE_INTS       (LINE_SIZE / sizeof(int))
+
+/* convert page number and cache line number to an integer index */
+#define PAGE_AND_LINE_TO_IDX(page, line) \
+        (((page) * PAGE_INTS) + ((line) * LINE_INTS))
+
+/* what CPU a thread should run on */
 #define THREAD_CPU(t)   (t * (NR_CPUS / nr_threads))
 
-#define FNAME_LEN 512
 struct pthread_state {
         pthread_t thread;
         int tid;
         int retval;
         struct color_ctrl_page *color_ctrl;
         int *arena;
-        char fname[FNAME_LEN];
-        FILE *file;
 };
 
-static pthread_barrier_t start_barrier, end_barrier;
+static pthread_barrier_t barrier;
 static int nr_threads;
 static int arena_size;
 static int color_shift;
+static int *page_line_order;
+static struct perf_counter perf_counters[NR_CPUS * NR_PERF_COUNTERS];
 
 #ifdef DEBUG
 #define debug_print(fmt, args...) do { \
@@ -77,53 +91,115 @@ static int color_shift;
 #define debug_print_thread(ts, fmt, args...) do {} while (0)
 #endif
 
-static void mk_fname(struct pthread_state *state)
+/*
+ * Get a random number in [0, max). Not really a good way to do this.
+ */
+inline int randrange(const int max)
+{
+        return (rand() / (RAND_MAX / max + 1));
+}
+
+/*
+ * Write 1, 2, ..., n - 1, 0 into items.
+ */
+void sequential(int *items, const int len)
+{
+        int i;
+        for (i = 0; i < len; i++)
+                items[i] = (i + 1) % len;
+}
+
+/*
+ * Sattolo's algorithm makes a random cycle that includes all the elements
+ * in the items array.
+ */
+void sattolo(int *items, const int len)
 {
-        snprintf(state->fname, FNAME_LEN, "cache_size=%d_line=%d_assoc=%d_"
-                        "colors=%d_color-shift=%d_use-colors=%d_arena-size=%d_"
-                        "arena-pages=%d_contig-colors=%d_thread=%d_"
-                        "cpu=%d.dat",
-                        CACHE_SIZE, LINE_SIZE, ASSOC, TOTAL_COLORS,
-                        color_shift, USE_COLORS, arena_size,
-                        ARENA_PAGES, CONTIG_COLORS, state->tid,
-                        THREAD_CPU(state->tid));
+        int i;
+        /* first set up 0, 1, ..., n - 1 */
+        for (i = 0; i < len; i++)
+                items[i] = i;
+        /* note: i is now n */
+        while (1 < i--) {
+                /* 0 <= j < i */
+                int t, j = randrange(i);
+                t = items[i];
+                items[i] = items[j];
+                items[j] = t;
+        }
+}
+
+/*
+ * Write the order to read the arena into the arena. Each page in the arena is
+ * read back, but the page is read in a random order to prevent the prefetcher
+ * from working.
+ *
+ * Starting at position 0 in the page_line_order means the cycle ends with 0.
+ * We use 0 in the arena to signify that we are done reading.
+ */
+static void init_arena_page_line_order(int *arena)
+{
+        int cur_page;
+        for (cur_page = 0; cur_page < ARENA_PAGES; cur_page++) {
+                /* for each page in the arena */
+                int cur_line;
+                for (cur_line = 0; cur_line < PAGE_LINES; cur_line++) {
+                        /* for each line in the page */
+                        const int idx = PAGE_AND_LINE_TO_IDX(cur_page,
+                                        cur_line);
+                        const int next_line = page_line_order[cur_line];
+                        int next_idx = PAGE_AND_LINE_TO_IDX(cur_page,
+                                        next_line);
+
+                        if (0 == next_line) {
+                                /* special case: cycle end */
+                                if (cur_page < ARENA_PAGES - 1) {
+                                        /* arena has more pages: go to next */
+                                        next_idx = PAGE_AND_LINE_TO_IDX(
+                                                        (cur_page + 1), 0);
+                                } else {
+                                        /* the very last element */
+                                        next_idx = 0;
+                                }
+                        }
+                        arena[idx] = next_idx;
+                }
+        }
 }
 
 static void setup_colors(struct pthread_state *state)
 {
-        int i, j;
-        for (i = 0; i < USE_COLORS; i++) {
-                for (j = 0; j < CONTIG_COLORS; j++)
-                        state->color_ctrl->colors[CONTIG_COLORS * i + j] = i;
+        int color, i;
+        for (color = 0; color < USE_COLORS; color++) {
+                /* what color do we use */
+                for (i = 0; i < CONTIG_COLORS; i++) {
+                        /* how many times do we use it */
+                        const int idx = CONTIG_COLORS * color + i;
+                        state->color_ctrl->colors[idx] = color;
+                }
         }
+#if 0
+        for (i = 0; i < ARENA_PAGES; i++)
+                printf("%d: %2d\n", i, state->color_ctrl->colors[i]);
+#endif
 }
 
 static int loop_once(struct pthread_state *state)
 {
-        int i, j = 0;
-        for (i = 0; i < ARENA_INTS; i += 1)
-                j = state->arena[i];
+        int i = 0, j;
+        do {
+                i = state->arena[i];
+                j = i;
+        } while (i);
         return j;
 }
 
 int thread_init(struct pthread_state *state)
 {
         const int cpu = THREAD_CPU(state->tid);
-        cpu_set_t cpu_set;
         int err = 0;
 
-        mk_fname(state);
-
-        state->file = fopen(state->fname, "w");
-        if (!state->file) {
-                debug_print_thread(state, "open file failed\n");
-                err = 1;
-                goto out;
-        }
-
-        CPU_ZERO(&cpu_set);
-        CPU_SET(cpu, &cpu_set);
-        err = sched_setaffinity(0, sizeof(cpu_set_t), &cpu_set);
+        err = be_migrate_to(cpu);
         if (err) {
                 debug_print_thread(state, "set affinity failed\n");
                 goto out;
@@ -144,6 +220,8 @@ int thread_init(struct pthread_state *state)
                 goto out;
         }
 
+        init_arena_page_line_order(state->arena);
+
         err = mlockall(MCL_CURRENT|MCL_FUTURE);
         if (err)
         {
@@ -154,76 +232,39 @@ out:
         return err;
 }
 
-#ifdef DEBUG
-#define CHECKPRINT(func, ...) do { \
-        int err = func(__VA_ARGS__); \
-        if (err) \
-                fprintf(stderr, "T%d: func failed\n", state->tid); \
-} while (0)
-#else
-#define CHECKPRINT(func, ...) func(__VA_ARGS__)
-#endif
-
-static void get_time(struct timespec *ts)
-{
-        int err;
-#if defined(TIME_MONO)
-        err = clock_gettime(CLOCK_MONOTONIC, ts);
-#elif defined(TIME_THREAD)
-        err = clock_gettime(CLOCK_THREAD_CPUTIME_ID, ts);
-#endif
-        if (err)
-                fprintf(stderr, "clock_gettime failed!\n");
-}
-
-static unsigned long ts_to_long(const struct timespec *ts)
+static void change_counters(const int request)
 {
-        unsigned long x = (((unsigned long)ts->tv_sec) * 1e9) +
-                ((unsigned long)ts->tv_nsec);
-        return x;
-}
-
-static unsigned long ts_difference(const struct timespec *start,
-                const struct timespec *end)
-{
-        unsigned long t1 = ts_to_long(start);
-        unsigned long t2 = ts_to_long(end);
-        return (t2 - t1);
+        int cpu;
+        for (cpu = 0; cpu < NR_CPUS; cpu++) {
+                const int ctr_idx = cpu * NR_PERF_COUNTERS;
+                ioctl(perf_counters[ctr_idx].fd, request);
+        }
 }
 
 void * thread_start(void *data)
 {
         struct pthread_state *state = (struct pthread_state*) data;
-        struct timespec start, end;
-        unsigned long time;
         int i;
 
         state->retval = thread_init(state);
         if (state->retval)
                 goto out;
 
-        loop_once(state);
+        pthread_barrier_wait(&barrier);
 
-        for (i = 0; i < NR_LOOPS; ++i) {
-                pthread_barrier_wait(&start_barrier);
+        if (0 == state->tid)
+                change_counters(PERF_EVENT_IOC_ENABLE);
 
-                get_time(&start);
-                loop_once(state);
-                get_time(&end);
-
-                pthread_barrier_wait(&end_barrier);
+        pthread_barrier_wait(&barrier);
 
-                time = ts_difference(&start, &end);
-                fprintf(state->file, "%lu\n", time);
-                state->retval = fflush(state->file);
-                if (state->retval)
-                        goto out;
-                state->retval = fsync(fileno(state->file));
-                if (state->retval)
-                        goto out;
+        for (i = 0; i < NR_LOOPS; ++i) {
+                loop_once(state);
+                pthread_barrier_wait(&barrier);
         }
 
-        fclose(state->file);
+        if (0 == state->tid)
+                change_counters(PERF_EVENT_IOC_DISABLE);
+
 out:
         pthread_exit(&state->retval);
 }
@@ -249,7 +290,40 @@ out:
         return err;
 }
 
-static struct pthread_state *pthread_state;
+static int setup_perf_counters(void)
+{
+        int cpu, ret = 0;
+        for (cpu = 0; cpu < NR_CPUS; cpu++) {
+                const int idx = cpu * NR_PERF_COUNTERS;
+                const int group_leader = -1;
+                ret = setup_cpu_perf(cpu, group_leader, &perf_counters[idx]);
+                if (ret)
+                        goto out;
+        }
+out:
+        return ret;
+}
+
+static void print_perf_counters(void)
+{
+        uint64_t val;
+        int err, cpu, i;
+        const char *name;
+
+        for (cpu = 0; cpu < NR_CPUS; cpu++) {
+                printf("CPU %d\n", cpu);
+                for (i = 0; i < NR_PERF_COUNTERS; i++) {
+                        const int idx = cpu * NR_PERF_COUNTERS + i;
+                        name = get_perf_name(&perf_counters[idx]);
+                        err = read_perf_counter(&perf_counters[idx], &val);
+                        if (err)
+                                printf("%50s: ERROR\n", name);
+                        else
+                                printf("%50s: %10.3f\n", name,
+                                                ((double)val) / NR_LOOPS);
+                }
+        }
+}
 
 #define CHECK(fun, ...) { \
         int err = fun(__VA_ARGS__); \
@@ -263,6 +337,8 @@ int main(int argc, char **argv)
 {
         int ret = 0, err, i;
         long int strtol_val;
+
+        struct pthread_state *pthread_state;
         pthread_attr_t attr;
 
         if (argc < 3) {
@@ -272,11 +348,11 @@ int main(int argc, char **argv)
                 goto out;
         }
 
-        err =  xstrtol(argv[1], &strtol_val);
-        nr_threads = strtol_val;
-        err |=  xstrtol(argv[2], &strtol_val);
-        arena_size = strtol_val;
-        err |= xstrtol(argv[3], &strtol_val);
+        err         = xstrtol(argv[1], &strtol_val);
+        nr_threads  = strtol_val;
+        err         |= xstrtol(argv[2], &strtol_val);
+        arena_size  = strtol_val;
+        err         |= xstrtol(argv[3], &strtol_val);
         color_shift = strtol_val;
         if (err) {
                 debug_print("non-integer argument?\n");
@@ -289,20 +365,25 @@ int main(int argc, char **argv)
                 goto out;
         }
 
-        pthread_state  = malloc(nr_threads * sizeof(*pthread_state));
-        if (!pthread_state) {
-                debug_print("could not malloc for state\n");
+        pthread_state   = malloc(nr_threads * sizeof(*pthread_state));
+        page_line_order = malloc(PAGE_LINES * sizeof(*page_line_order));
+        if (!pthread_state || !page_line_order) {
+                debug_print("could not malloc\n");
                 ret = 1;
                 goto out;
         }
 
+        CHECK(setup_perf_counters);
+
         CHECK(pthread_attr_init, &attr);
         CHECK(pthread_attr_setdetachstate, &attr, PTHREAD_CREATE_JOINABLE);
-        CHECK(pthread_barrier_init, &start_barrier, NULL, nr_threads);
-        CHECK(pthread_barrier_init, &end_barrier, NULL, nr_threads);
+        CHECK(pthread_barrier_init, &barrier, NULL, nr_threads);
+
+        sattolo(page_line_order, PAGE_LINES);
+        //sequential(page_line_order, PAGE_LINES);
 
         for (i = 0; i < nr_threads; i++) {
-                pthread_state[i].tid= i;
+                pthread_state[i].tid = i;
                 CHECK(pthread_create, &pthread_state[i].thread, &attr, thread_start,
                                 (void*)&pthread_state[i]);
         }
@@ -321,10 +402,12 @@ int main(int argc, char **argv)
                 }
         }
 
-        CHECK(pthread_barrier_destroy, &start_barrier);
-        CHECK(pthread_barrier_destroy, &end_barrier);
+        CHECK(pthread_barrier_destroy, &barrier);
         CHECK(pthread_attr_destroy, &attr);
 
+        printf("arena pages: %d\n", ARENA_PAGES);
+        print_perf_counters();
+
 out:
         return ret;
 }
diff --git a/bin/perfcounters.c b/bin/perfcounters.c
new file mode 100644
index 0000000..402e047
--- /dev/null
+++ b/bin/perfcounters.c
@@ -0,0 +1,187 @@
+#include "asm/unistd.h"         /* from kernel source tree */
+#include <unistd.h>             /* for syscall */
+
+#include <sys/ioctl.h>
+
+#include "perfcounters.h"
+
+#define C(x)    (PERF_COUNT_HW_CACHE_##x)
+#define ATTR_CONFIG_CACHE(cache, op, result) \
+        (((C(cache)  & 0xffULL) <<  0) | \
+         ((C(op)     & 0xffULL) <<  8) | \
+         ((C(result) & 0xffULL) << 16))
+
+#define ATTR_CONFIG(event, umask)   \
+        ((((event) & 0xffULL) << 0) | \
+         (((umask) & 0xffULL) << 8))
+
+static struct perf_event_attr perf_event_attr = {
+        .type            = 0,     /* set per initilized event */
+        .size            = 0,     /* set later */
+        .config          = 0,     /* set per initilized event */
+        { .sample_period = 0, },  /* is a counter, so no period */
+        .disabled        = 0,     /* event is enabled */
+        .inherit         = 0,     /* children don't inherit */
+        .pinned          = 0,     /* set per initilized event */
+        .exclusive       = 0,     /* set per initilized event */
+        .exclude_user    = 0,     /* don't count user (when set) */
+        .exclude_kernel  = 0,     /* ditto kernel          */
+        .exclude_hv      = 0,     /* ditto hypervisor      */
+        .exclude_idle    = 0,     /* don't count when idle */
+        .mmap            = 0,     /* include mmap data     */
+        .comm            = 0,     /* include comm data     */
+};
+
+struct perf_counter_setup {
+        char                    *name;
+        enum perf_type_id       type;
+        uint64_t                config;
+};
+
+#if 0
+/* these events are always zero */
+static struct perf_fd perf_fds[] = {
+        {
+                .fd        = -1,
+                .name      = "MEM_UNCORE_RETIRED.REMOTE_CACHE_LOCAL_HOME_HIT",
+                .type      = PERF_TYPE_RAW,
+                .config    = ATTR_CONFIG(0x0f, 0x08),
+                .exclusive = 0,
+                .pinned    = 0,
+        },
+        {
+                .fd     = -1,
+                .name   = "MEM_UNCORE_RETIRED.REMOTE_DRAM",
+                .type   = PERF_TYPE_RAW,
+                .config = ATTR_CONFIG(0x0f, 0x10),
+                .exclusive = 0, /* child events cannot be exclusive */
+                .pinned    = 0, /* child events cannot be pinned */
+        },
+        { },
+};
+#endif
+
+static struct perf_counter_setup perf_setup[NR_PERF_COUNTERS] = {
+#if 0
+        {
+                .name   = "MEM_UNCORE_RETIRED.LOCAL_DRAM",
+                .type   = PERF_TYPE_RAW,
+                .config = ATTR_CONFIG(0x0f, 0x20),
+        },
+#endif
+        {
+                .name   = "L2_RQSTS.PREFETCH_HIT",
+                .type   = PERF_TYPE_RAW,
+                .config = ATTR_CONFIG(0x24, 0x40),
+        },
+        {
+                .name   = "L2_RQSTS.PREFETCH_MISS",
+                .type   = PERF_TYPE_RAW,
+                .config = ATTR_CONFIG(0x24, 0x80),
+        },
+        {
+                .name   = "MEM_LOAD_RETIRED.L3_MISS",
+                .type   = PERF_TYPE_RAW,
+                .config = ATTR_CONFIG(0xcb, 0x10),
+        },
+        {
+                .name      = "Off Core Response Counter",
+                .type      = PERF_TYPE_HW_CACHE,
+                .config    = ATTR_CONFIG_CACHE(LL, OP_READ, RESULT_MISS),
+#if 0
+                /* read misses */
+                .config = ATTR_CONFIG_CACHE(LL, OP_READ, RESULT_MISS),
+                /* write misses */
+                .config = ATTR_CONFIG_CACHE(LL, OP_WRITE, RESULT_MISS),
+                /* prefetch misses */
+                .config = ATTR_CONFIG_CACHE(LL, OP_PREFETCH, RESULT_MISS),
+#endif
+        },
+};
+
+
+/* from kernel tools/perf/perf.h */
+int sys_perf_event_open(struct perf_event_attr *attr, pid_t pid,
+                int cpu, int group_fd, unsigned long flags)
+{
+        attr->size = sizeof(*attr);
+        return syscall(__NR_perf_event_open, attr, pid, cpu, group_fd, flags);
+}
+
+/* make the temporary attributes shadow those in the perf_fd temporarially */
+static void write_global_perf_attr(const struct perf_counter_setup *p)
+{
+                perf_event_attr.type            = p->type;
+                perf_event_attr.config          = p->config;
+                perf_event_attr.pinned          = 0;
+                perf_event_attr.exclusive       = 0;
+}
+
+int setup_cpu_perf(const int cpu, const int group_leader,
+                struct perf_counter *perf_counters)
+{
+        const int perf_pid = -1; /* -1: all tasks */
+        int err = 0, i;
+
+        if (-1 == group_leader) {
+                /* first element determines the group for all others */
+                perf_counters->fd = -1;
+        }
+
+        for (i = 0; i < NR_PERF_COUNTERS; i++) {
+                int perf_group;
+
+                /* setup the attributes to pass in */
+                write_global_perf_attr(&perf_setup[i]);
+
+                if (0 == i && -1 == group_leader) {
+                        /* but group leader is pinned and exclusive */
+                        perf_event_attr.exclusive = 1;
+                        perf_event_attr.pinned = 1;
+                        perf_group = -1;
+                } else if (-1 == group_leader) {
+                        /* not first counter, but no group passed in */
+                        perf_group = perf_counters[0].fd;
+                }
+
+                perf_counters[i].fd = sys_perf_event_open(&perf_event_attr,
+                                perf_pid, cpu, perf_group, 0);
+
+                if (0 > perf_counters[i].fd) {
+                        err = -1;
+                        goto out;
+                }
+
+                /* save the attributes in the user-visible configuration */
+                perf_counters[i].type = perf_setup[i].type;
+                perf_counters[i].config = perf_setup[i].config;
+        }
+out:
+        return err;
+}
+
+static inline int perf_setup_match(const struct perf_counter_setup* ps,
+                const struct perf_counter *pc)
+{
+        return (ps->type == pc->type && ps->config == pc->config);
+}
+
+const char* get_perf_name(const struct perf_counter* perf_counter)
+{
+        char *ret = NULL;
+        int i;
+        
+        for (i = 0; i < NR_PERF_COUNTERS; i++) {
+                if (perf_setup_match(&perf_setup[i], perf_counter)) {
+                        ret = perf_setup[i].name;
+                        break;
+                }
+        }
+        return ret;
+}
+
+int read_perf_counter(const struct perf_counter* perf_counter, uint64_t *val)
+{
+        ssize_t ret = read(perf_counter->fd, val, sizeof(*val));
+        return (ret <= 0);
+}
diff --git a/include/perfcounters.h b/include/perfcounters.h
new file mode 100644
index 0000000..03f94fb
--- /dev/null
+++ b/include/perfcounters.h
@@ -0,0 +1,36 @@
+#ifndef PERFCOUNTERS_H
+#define PERFCOUNTERS_H
+
+#include <stdint.h>
+
+#include "../../litmus-rt/include/linux/perf_event.h"
+
+#define NR_PERF_COUNTERS        4
+
+/*
+ * Retain this information with a performance counter file descriptor.
+ */
+struct perf_counter {
+        int                     fd;
+        enum perf_type_id       type;
+        uint64_t                config;
+};
+
+
+/*
+ * Initialize a set of counters for a CPU.
+ *
+ * This is NOT thread safe!
+ *
+ * @cpu                 CPU
+ * @group_leader        group leader PID or -1 make a new group
+ * @perf_counter        array
+ * @return              0 or error
+ */
+int setup_cpu_perf(const int, const int, struct perf_counter*);
+
+const char* get_perf_name(const struct perf_counter*);
+
+int read_perf_counter(const struct perf_counter*, uint64_t*);
+
+#endif