Ports lock_test to Linux
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 2 Oct 2014 01:43:47 +0000 (18:43 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Thu, 2 Oct 2014 01:49:26 +0000 (18:49 -0700)
Build from your AKAROS_ROOT directory with:

$ gcc -O2 -std=gnu99 -fno-stack-protector -g tests/lock_test.c \
  -lpthread -lm -o linux_lock_test

Linux only has the spin and mcs/mcscas available, so the others are
stubs.  It will attempt to pin the worker threads to physical cores
0..n.  If you do your own tasksetting after the program is running, you
can override that.  That might be useful if you want to fake preemption.

The ugliest thing is #including the lock source code in a .h file.
Doing it with measure.c is only slightly less nastry.  Maybe we can get
some linux make targets or something, and put this compat stuff in one
place.

tests/linux-lock-hacks.h [new file with mode: 0644]
tests/lock_test.c

diff --git a/tests/linux-lock-hacks.h b/tests/linux-lock-hacks.h
new file mode 100644 (file)
index 0000000..cad52a1
--- /dev/null
@@ -0,0 +1,152 @@
+/* basic locking code that compiles on linux.  #included directly into
+ * lock_test.  It's a .h so that make tests doesn't build it. */
+
+#define ARCH_CL_SIZE 64
+#define SPINLOCK_INITIALIZER {0}
+
+typedef struct {
+       int lock;
+} spinlock_t;
+
+void __attribute__((noinline)) spinlock_init(spinlock_t *lock)
+{
+       lock->lock = 0;
+}
+
+int __attribute__((noinline)) spinlock_trylock(spinlock_t *lock) 
+{
+       if (lock->lock)
+               return EBUSY;
+       return __sync_lock_test_and_set(&lock->lock, EBUSY);
+}
+
+void __attribute__((noinline)) spinlock_lock(spinlock_t *lock) 
+{
+       while (spinlock_trylock(lock))
+               cpu_relax();
+}
+
+void __attribute__((noinline)) spinlock_unlock(spinlock_t *lock) 
+{
+       __sync_lock_release(&lock->lock, 0);
+}
+
+#define MCS_LOCK_INIT {0}
+#define MCS_QNODE_INIT {0, 0}
+
+typedef struct mcs_lock_qnode
+{
+       struct mcs_lock_qnode *next;
+       int locked;
+}__attribute__((aligned(ARCH_CL_SIZE))) mcs_lock_qnode_t;
+
+/* included for the dummy init in lock_thread */
+struct mcs_pdro_qnode
+{
+       struct mcs_pdro_qnode *next;
+       int locked;
+       uint32_t vcoreid;
+}__attribute__((aligned(ARCH_CL_SIZE)));
+
+#define MCSPDRO_QNODE_INIT {0, 0, 0}
+#define mcs_pdr_init(args...) {}
+
+typedef struct mcs_lock
+{
+       mcs_lock_qnode_t* lock;
+} mcs_lock_t;
+
+void __attribute__((noinline)) mcs_lock_init(struct mcs_lock *lock)
+{
+       memset(lock, 0, sizeof(mcs_lock_t));
+}
+
+static inline mcs_lock_qnode_t *mcs_qnode_swap(mcs_lock_qnode_t **addr,
+                                               mcs_lock_qnode_t *val)
+{
+       return (mcs_lock_qnode_t*) __sync_lock_test_and_set((void**)addr, val);
+}
+
+void __attribute__((noinline))
+mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
+{
+       qnode->next = 0;
+       cmb();  /* swap provides a CPU mb() */
+       mcs_lock_qnode_t *predecessor = mcs_qnode_swap(&lock->lock, qnode);
+       if (predecessor) {
+               qnode->locked = 1;
+               wmb();
+               predecessor->next = qnode;
+               /* no need for a wrmb(), since this will only get unlocked after they
+                * read our previous write */
+               while (qnode->locked)
+                       cpu_relax();
+       }
+       cmb();  /* just need a cmb, the swap handles the CPU wmb/wrmb() */
+}
+
+void __attribute__((noinline))
+mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
+{
+       /* Check if someone is already waiting on us to unlock */
+       if (qnode->next == 0) {
+               cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
+               /* Unlock it */
+               mcs_lock_qnode_t *old_tail = mcs_qnode_swap(&lock->lock,0);
+               /* no one else was already waiting, so we successfully unlocked and can
+                * return */
+               if (old_tail == qnode)
+                       return;
+               /* someone else was already waiting on the lock (last one on the list),
+                * and we accidentally took them off.  Try and put it back. */
+               mcs_lock_qnode_t *usurper = mcs_qnode_swap(&lock->lock,old_tail);
+               /* since someone else was waiting, they should have made themselves our
+                * next.  spin (very briefly!) til it happens. */
+               while (qnode->next == 0)
+                       cpu_relax();
+               if (usurper) {
+                       /* an usurper is someone who snuck in before we could put the old
+                        * tail back.  They now have the lock.  Let's put whoever is
+                        * supposed to be next as their next one. */
+                       usurper->next = qnode->next;
+               } else {
+                       /* No usurper meant we put things back correctly, so we should just
+                        * pass the lock / unlock whoever is next */
+                       qnode->next->locked = 0;
+               }
+       } else {
+               /* mb()s necessary since we didn't call an atomic_swap() */
+               wmb();  /* need to make sure any previous writes don't pass unlocking */
+               rwmb(); /* need to make sure any reads happen before the unlocking */
+               /* simply unlock whoever is next */
+               qnode->next->locked = 0;
+       }
+}
+
+/* CAS style mcs locks, kept around til we use them.  We're using the
+ * usurper-style, since RISCV doesn't have a real CAS (yet?). */
+void __attribute__((noinline))
+mcs_lock_unlock_cas(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
+{
+       /* Check if someone is already waiting on us to unlock */
+       if (qnode->next == 0) {
+               cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
+               /* If we're still the lock, just swap it with 0 (unlock) and return */
+               if (__sync_bool_compare_and_swap((void**)&lock->lock, qnode, 0))
+                       return;
+               /* We failed, someone is there and we are some (maybe a different)
+                * thread's pred.  Since someone else was waiting, they should have made
+                * themselves our next.  Spin (very briefly!) til it happens. */
+               while (qnode->next == 0)
+                       cpu_relax();
+               /* Alpha wants a read_barrier_depends() here */
+               /* Now that we have a next, unlock them */
+               qnode->next->locked = 0;
+       } else {
+               /* mb()s necessary since we didn't call an atomic_swap() */
+               wmb();  /* need to make sure any previous writes don't pass unlocking */
+               rwmb(); /* need to make sure any reads happen before the unlocking */
+               /* simply unlock whoever is next */
+               qnode->next->locked = 0;
+       }
+}
index 8ae9a6c..10dd978 100644 (file)
@@ -1,8 +1,14 @@
-/* Copyright (c) 2013 The Regents of the University of California
+/* Copyright (c) 2013, 2014 The Regents of the University of California
  * Barret Rhoden <brho@cs.berkeley.edu>
  * See LICENSE for details.
  *
- * lock_test: microbenchmark to measure different styles of spinlocks. */
+ * lock_test: microbenchmark to measure different styles of spinlocks.
+ *
+ * to build on linux: (hacky)
+ * $ gcc -O2 -std=gnu99 -fno-stack-protector -g tests/lock_test.c -lpthread \
+ *    -lm -o linux_lock_test */
+
+#define _GNU_SOURCE /* pthread_yield */
 
 #include <stdio.h>
 #include <pthread.h>
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
-
-#include <tsc-compat.h>
-#include <measure.h>
+#include <assert.h>
+#include <string.h>
 
 /* OS dependent #incs */
+#ifdef __ros__
+
 #include <parlib.h>
 #include <vcore.h>
 #include <timing.h>
 #include <arch/arch.h>
 #include <event.h>
 
+#include <tsc-compat.h>
+#include <measure.h>
+
+#else
+
+#include "../user/parlib/include/tsc-compat.h"
+#include "misc-compat.h"
+#include "linux-lock-hacks.h" /* TODO: have a build system and lib / C file */
+
+#include "../user/benchutil/include/measure.h"
+#include "../user/benchutil/measure.c"
+
+static void os_prep_work(pthread_t *worker_threads, int nr_threads)
+{
+       if (nr_threads > num_vcores())
+               printf("WARNING: %d threads requested, but only %d cores available\n",
+                      nr_threads, num_vcores());
+}
+
+static void os_post_work(pthread_t *worker_threads, int nr_threads)
+{
+       if (nr_threads > num_vcores())
+               return;
+       /* assuming we're taking cores 0..nr_threads, and we never move. */
+       for (int i = 0; i < nr_threads; i++) {
+               cpu_set_t cpuset;
+               CPU_ZERO(&cpuset);
+               CPU_SET(i, &cpuset);
+               pthread_setaffinity_np(worker_threads[i], sizeof(cpu_set_t), &cpuset);
+       }
+}
+
+#define print_preempt_trace(args...) {}
+
+__thread int __vcore_context = 0;
+
+#endif
+
 /* TODO: There's lot of work to do still, both on this program and on locking
  * and vcore code.  For some of the issues, I'll leave in the discussion /
  * answers, in case it comes up in the future (like when I read this in 8
@@ -462,12 +507,6 @@ pthread_barrier_t start_test;
 /* Locking functions.  Define globals here, init them in main (if possible), and
  * use the lock_func() macro to make your thread func. */
 
-spinlock_t spin_lock = SPINLOCK_INITIALIZER;
-struct spin_pdr_lock spdr_lock = SPINPDR_INITIALIZER;
-struct mcs_lock mcs_lock = MCS_LOCK_INIT;
-struct mcs_pdr_lock mcspdr_lock;
-struct mcs_pdro_lock mcspdro_lock = MCSPDRO_LOCK_INIT;
-
 #define lock_func(lock_name, lock_cmd, unlock_cmd)                             \
 void *lock_name##_thread(void *arg)                                            \
 {                                                                              \
@@ -543,6 +582,16 @@ void *lock_name##_thread(void *arg)                                            \
        return (void*)(long)i;                                                     \
 }
 
+#define fake_lock_func(lock_name, x1, x2)                                      \
+void *lock_name##_thread(void *arg)                                            \
+{                                                                              \
+       printf("Lock " #lock_name " not supported!\n");                            \
+       exit(-1);                                                                  \
+}
+
+spinlock_t spin_lock = SPINLOCK_INITIALIZER;
+struct mcs_lock mcs_lock = MCS_LOCK_INIT;
+
 /* Defines locking funcs like "mcs_thread" */
 lock_func(mcs,
           mcs_lock_lock(&mcs_lock, &mcs_qnode);,
@@ -550,6 +599,15 @@ lock_func(mcs,
 lock_func(mcscas,
           mcs_lock_lock(&mcs_lock, &mcs_qnode);,
           mcs_lock_unlock_cas(&mcs_lock, &mcs_qnode);)
+lock_func(spin,
+          spinlock_lock(&spin_lock);,
+          spinlock_unlock(&spin_lock);)
+
+#ifdef __ros__
+struct spin_pdr_lock spdr_lock = SPINPDR_INITIALIZER;
+struct mcs_pdr_lock mcspdr_lock;
+struct mcs_pdro_lock mcspdro_lock = MCSPDRO_LOCK_INIT;
+
 lock_func(mcspdr,
           mcs_pdr_lock(&mcspdr_lock);,
           mcs_pdr_unlock(&mcspdr_lock);)
@@ -559,12 +617,17 @@ lock_func(mcspdro,
 lock_func(__mcspdro,
           __mcs_pdro_lock(&mcspdro_lock, &pdro_qnode);,
           __mcs_pdro_unlock(&mcspdro_lock, &pdro_qnode);)
-lock_func(spin,
-          spinlock_lock(&spin_lock);,
-          spinlock_unlock(&spin_lock);)
 lock_func(spinpdr,
           spin_pdr_lock(&spdr_lock);,
           spin_pdr_unlock(&spdr_lock);)
+#else
+
+fake_lock_func(mcspdr, 0, 0);
+fake_lock_func(mcspdro, 0, 0);
+fake_lock_func(__mcspdro, 0, 0);
+fake_lock_func(spinpdr, 0, 0);
+
+#endif
 
 static int get_acq_latency(void **data, int i, int j, uint64_t *sample)
 {
@@ -602,6 +665,8 @@ static int get_acq_timestamp(void **data, int i, int j, uint64_t *sample)
        return 0;
 }
 
+#ifdef __ros__
+
 /* Lousy event intercept.  build something similar in the event library? */
 #define MAX_NR_EVENT_TRACES 1000
 uint64_t preempts[MAX_NR_EVENT_TRACES] = {0};
@@ -656,7 +721,7 @@ static void print_preempt_trace(uint64_t starttsc, int nr_print_rows)
 }
 
 /* Make sure we have enough VCs for nr_threads, pref 1:1 at the start */
-static void os_prep_work(int nr_threads)
+static void os_prep_work(pthread_t *worker_threads, int nr_threads)
 {
        if (nr_threads > max_vcores()) {
                printf("Too many threads (%d) requested, can't get more than %d vc\n",
@@ -689,6 +754,12 @@ static void os_prep_work(int nr_threads)
        }
 }
 
+static void os_post_work(pthread_t *worker_threads, int nr_threads)
+{
+}
+
+#endif
+
 /* Argument parsing */
 static error_t parse_opt (int key, char *arg, struct argp_state *state)
 {
@@ -851,7 +922,7 @@ int main(int argc, char** argv)
        }
        printf("Record tracking takes %ld bytes of memory\n",
               nr_threads * nr_loops * sizeof(struct time_stamp));
-       os_prep_work(nr_threads);       /* ensure we have enough VCs */
+       os_prep_work(worker_threads, nr_threads);       /* ensure we have enough VCs */
        /* Doing this in MCP ctx, so we might have been getting a few preempts
         * already.  Want to read start before the threads pass their barrier */
        starttsc = read_tsc();
@@ -861,6 +932,7 @@ int main(int argc, char** argv)
                                   (void*)i))
                        perror("pth_create failed");
        }
+       os_post_work(worker_threads, nr_threads);
        if (gettimeofday(&start_tv, 0))
                perror("Start time error...");
        for (int i = 0; i < nr_threads; i++) {