Reworks MCS-PDR locks to avoid preempt storms
authorBarret Rhoden <brho@cs.berkeley.edu>
Sat, 25 May 2013 21:55:56 +0000 (14:55 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Sat, 25 May 2013 22:09:02 +0000 (15:09 -0700)
The old style would aggressively switch to its pred, which made it
extremely unlikely to ever have a vcore outside the MCS chain recover
one of the vcores in the chain.  This means that we would always have a
vcore in the chain that was preempted, leading to at least one syscall
per lock acquisition.  This causes a massive amount of
preemption/change-tos that last until all vcores are given back.

The new style tries to restart the lockholder, instead of pred, only
relying on pred when there is no other way out.  This style recovers
quickly from a preemption, even if the vcores are never given back.

While it might be a little slower than the old PDR locks, it is
significantly safer, and is now the default.

The old style PDR locks are now called mcs_pdro_locks (o for
old).

Note there are a few optimizations that the first version of PDR locks
didn't have that were important.  (First version being the one from over
a year ago).  The lockholder handoff is handed off when we unlock our
qnode->next, which saves a lot on cache line contention.  We use the
qnodes address for pointer arithmetic to determine vcoreid.  And we
properly memalign the qnode storage, ensuring cache line alignment.

As far as cache lines go, some prefetching ruins our "independent" cache
lines.  For now, I turn off things like Adjacent Cacheline Prefetching,
or whatever it's called these days.  Would be nice if we had an
instruction that explicitly didn't trigger a prefetch on a load or
store.

tests/lock_test.c
user/parlib/include/mcs.h
user/parlib/mcs.c
user/pthread/futex.c
user/pthread/pthread.c

index 27bddc5..7eaa691 100644 (file)
  * months).
  *
  * BUGS / COMMENTARY
+ *             Occasional deadlocks when preempting and not giving back!
+ *                     - with the new PDRs style, though that doesn't mean the older styles
+ *                     don't have this problem
+ *                     - shouldn't be any weaker than PDR.  they all check pred_vc to see
+ *                     if they are running, and if not, they make sure someone runs
+ *                     - could be weaker if we have an old value for the lockholder,
+ *                     someone outside the chain, and we made sure they ran, and they do
+ *                     nothing (spin in the 2LS or something?)
+ *                             no, they should have gotten a msg about us being preempted,
+ *                             since whoever we turn into gets the message about us swapping.
+ *                     - anyway, it's not clear if this is with MCSPDR, event delivery,
+ *                     preemption handling, or just an artifact of the test (less likely)
  *             why aren't MCS locks in uth_ctx getting dealt with?
  *                     - because the event is handled, but the lock holder isn't run.  the
  *                     preemption was dealt with, but nothing saved the lock holder
@@ -77,7 +89,6 @@
  *                     ex: 5000 locks/ms = 5 locks/us = 200ns/lock = 500 ticks / lock
  *                     500 ticks * 31 workers (queue) = 15000 ticks
  *                     avg acquire time was around 14K.  seems fine..
- *
  *                     when our MCSPDR throughput tanks (during preempts), it's around
  *                     400-500 locks/ms, which is around 2us/lock.  
  *                             when the locker on a preempted chain shows up, it needs to
@@ -88,7 +99,8 @@
  *                                     such that it is the bottleneck for the actual lock.  2us
  *                                     seems possible
  *
- *             what does it take to get out of a preemption with MCS-PDR?
+ *             what does it take to get out of a preemption with (old) MCS-PDR?
+ *                     - these are now called pdro locks (old)
  *                     - for a single preempt, it will take 1..n-1 changes.  avg n/2
  *                     - for multiple preempts, it's nr_pre * that (avg np/2, worst np)
  *                     - for every unlock/reacquire cycle (someone unlocks, then rejoins
  *                             - mcspdr, d = 2: 4200-5200
  *                             - as you add delay, it cuts down on contention for the
  *                             lock->lock cacheline.  but if you add in too much, you'll tank
- *                             throughput (since there is no contention at all).  sweet spot
- *                             for 31 cores on c89 was around 2-3.
+ *                             throughput (since there is no contention at all).
  *                             - as we increase the delay, we cut down on the chance of the
  *                             preempt storm / preempt-stuck-in-the-chain, though it can still
  *                             happen, even with a delay of 10us
- *                                     - though as we increase the delay, we increase the chance of
- *                                     the preempted vcore not being in the chain, so its not clear
- *                                     that having a higher delay actually helped with MCS-chain
- *                                     preemptions
  *                     - maybe add in the lockholder again? (removed in 73701d6bfb)
- *                             - massively cuts performance, like 2x throughput, without preempts
+ *                             - massively cuts performance, like 2x throughput, without
+ *                             preempts
  *                             - it's ability to help depends on impl:
  *                                     in one version (old style), it didn't help much at all
  *                                     - in another (optimized lockholder setting), i can't even
  *                                     is less time with having "no lockholder".  (there's a brief
  *                                     period where the lockholder says it is the next person, who
  *                                     still spins.  they'll have to make sure their pred runs)
- *                                             - read in lockholder_vcoreid.  if -1 or us, ensure pred,
- *                                             o/w ensure lockholder.  when passing the lock, read
- *                                             their vcoreid and set it.  if unlocked, set to -1, etc.
- *                                     -adj workers doesn't matter either...
- *                                             - the 2LS and preemption handling might be doing this
- *                                             automatically, when handle_preempt() does a
- *                                             thread_paused() on its current_uthread.
- *                                             - adj_workers isn't critical if we're using some locks
- *                                             that check notif_pending.  eventually someone hears
- *                                             about preempted VCs (assuming we can keep up)
- *                     - or spin a bit first, before ensuring?
- *                             ensuring once every 1000 spins, for instance, didn't help break
- *                             out of the chain, and just decreased our speed in resolving
- *                             preempts
- *                     - it's not enough to know that there haven't been any new
- *                     preemptions.  your lockholder could already been preempted.
- *                     - and any mechanism that allows all lockers to know the lockholder
- *                     will cause cache traffic, (every lock acquire is a global cache
- *                     invalidate, which everyone reaquires quickly)
+ *                     -adj workers doesn't matter either...
+ *                             - the 2LS and preemption handling might be doing this
+ *                             automatically, when handle_preempt() does a
+ *                             thread_paused() on its current_uthread.
+ *                             - adj_workers isn't critical if we're using some locks
+ *                             that check notif_pending.  eventually someone hears
+ *                             about preempted VCs (assuming we can keep up)
  *
  *                     What about delays?  both hold and delay should make it easier to get
  *                     the preempted vcore to the end of the chain.  but do they have to be
  *                     too big to be reasonable?
- *                             - yes.  hold doesn't really help much until everything is slower.
- *                             even with a hold of around 1.2us, we still have the
+ *                             - yes.  hold doesn't really help much until everything is
+ *                             slower.  even with a hold of around 1.2us, we still have the
  *                             change_to-storms and lowered throughput.
  *                             - doing a combo helps too.  if you hold for 1ns (quite a bit
  *                             more actually, due to the overhead of ndelay, but sufficient to
  *                                     never really get out.  either we do quickly or never do.
  *                                     depending on the workload, this could be a matter of luck
  *
+ *                     So we could try tracking the lockholder, but only looking at it when
+ *                     we know someone was preempted in the chain - specifically, when our
+ *                     pred is offline.  when that happens, we don't change to them, we
+ *                     make sure the lockholder is running.
+ *                             - tracking takes us from 4200->2800 throughput or so for MCS
+ *                             - 5200 -> 3700 or so for MCS in vc_ctx (__MCSPDR)
+ *                             - main spike seems to be in the hold time.  bimodal distrib,
+ *                             with most below 91 (the usual is everything packed below 70) and
+ *                             a big spike around 320
+ *
  *     Summary:
  *             So we need to have someone outside the chain change_to the one in the
  *             chain o/w, someone will always be in the chain.  Right now, it's always
  *             preemption.  Arguably, if you were worried about the preempt storms and
  *             want scalability, you might want to use mcspdr with lockholders.
  *
+ *             The MCSPDRS (now just callced MCSPDR, these are default) locks can avoid
+ *             the storm, but at the cost of a little more in performance.  mcspdrs
+ *             style is about the same when not getting preempted from uth ctx compared
+ *             to mcspdr (slight drop).  When in vc ctx, it's about 10-20% perf hit
+ *             (PDRS gains little from --vc_ctx). 
+ *
+ *             Turns out there is a perf hit to PDRS (and any non-stack based qnode)
+ *             when running on c89.  The issue is that after shuffling the vcores
+ *             around, they are no longer mapped nicely to pcores (VC0->PC1, VC1->PC2).
+ *             This is due to some 'false sharing' of the cachelines, caused mostly by
+ *             aggressive prefetching (notably the intel adjacent cacheline prefetcher,
+ *             which grabs two CLs at a time!).  Basically, stack-based qnodes are
+ *             qnodes that are very far apart in memory.  Cranking up the padding in
+ *             qnodes in the "qnodes-in-locks" style replicates this.
+ *
+ *             For some info on the prefetching:
+ *                     http://software.intel.com/en-us/articles/optimizing-application-performance-on-intel-coret-microarchitecture-using-hardware-implemented-prefetchers/
+ *                     http://software.intel.com/en-us/forums/topic/341769
+ *
+ *             Here's some rough numbers of the different styles for qnodes on c89.
+ *             'in order' is VCn->PC(n+1) (0->1, 1->2).  Worst order is with even VCs
+ *             on one socket, odds on the other.  the number of CLs is the size of a
+ *             qnode.  mcspdr is the new style (called mcspdrs in some places in this
+ *             document), with lock-based qnodes.  mcspdr2 is the same, but with
+ *             stack-based qnodes.  mcspdro is the old style (bad a recovery), stack
+ *             based, sometimes just called mcs-pdr
+ *
+ *             with prefetchers disabled (MCS and DCU)
+ *                     mcspdr   1CL  4.8-5.4 in order, 3.8-4.2 worst order
+ *                     mcspdr   2CL          in order,         worst order
+ *                     mcspdr   4CL  5.2-6.0 in order, 4.7-5.3 worst order
+ *                     mcspdr   8CL  5.4-6.7 in order, 5.2-6.2 worst order
+ *                     mcspdr  16CL  5.1-5.8 in order, 5.2-6.8 worst order
+ *                     mcspdr2 stck          in order,         worst order
+ *                     mcspdro stck  4-3.4.3 in order, 4.2-4.5 worst order
+ *                     mcspdro-vcctx 4.8-7.0 in order, 5.3-6.7 worst order
+ *                     can we see the 2 humps? 
+ *                             mcspdr 1CL yes but less, varied, etc
+ *                             mcspdr2 no
+ *
+ *             test again with worst order with prefetchers enabled
+ *                     mcspdr   1CL  3.8-4.0 in order, 2.6-2.7 worst order
+ *                     mcspdr   2CL  4.2-4.4 in order, 3.8-3.9 worst order
+ *                     mcspdr   4CL  4.5-5.2 in order, 4.0-4.2 worst order
+ *                     mcspdr   8CL  4.4-5.1 in order, 4.3-4.7 worst order
+ *                     mcspdr  16CL  4.4-4.8 in order, 4.4-5.3 worst order
+ *                     mcspdr2 stck  3.0-3.0 in order, 2.9-3.0 worst order
+ *                     mcspdro stck  4.2-4.3 in order, 4.2-4.4 worst order
+ *                     mcspdro-vcctx 5.2-6.4 in order, 5.0-5.9 worst order
+ *                     can we see the 2 humps?
+ *                             mcspdrs 1CL yes, clearly
+ *                             mcspdr2 no
  *
  * PROGRAM FEATURES
  *             - verbosity?  vcoremap, preempts, the throughput and latency histograms?
@@ -357,7 +415,8 @@ static struct argp_option options[] = {
                                                     "\tmcs\n"
                                                     "\tmcscas\n"
                                                     "\tmcspdr\n"
-                                                    "\t__mcspdr\n"
+                                                    "\tmcspdro\n"
+                                                    "\t__mcspdro\n"
                                                     "\tspin\n"
                                                     "\tspinpdr"},
        {0, 0, 0, 0, "Other options (not mandatory):"},
@@ -389,6 +448,7 @@ struct time_stamp {
        uint64_t pre;
        uint64_t acq;
        uint64_t un;
+       bool valid;
 };
 struct time_stamp **times;
 bool run_locktest = TRUE;
@@ -400,7 +460,8 @@ pthread_barrier_t start_test;
 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 = MCSPDR_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)                                            \
@@ -414,10 +475,10 @@ void *lock_name##_thread(void *arg)                                            \
        uint64_t pre_lock, acq_lock, un_lock;                                      \
        struct time_stamp *this_time;                                              \
        struct mcs_lock_qnode mcs_qnode = MCS_QNODE_INIT;                          \
-       struct mcs_pdr_qnode pdr_qnode = MCSPDR_QNODE_INIT;                        \
+       struct mcs_pdro_qnode pdro_qnode = MCSPDRO_QNODE_INIT;                     \
        /* guessing a unique vcoreid for vcoreid for the __mcspdr test.  if the
         * program gets preempted for that test, things may go nuts */             \
-       pdr_qnode.vcoreid = thread_id - 1;                                         \
+       pdro_qnode.vcoreid = thread_id - 1;                                        \
        /* Wait til all threads are created.  Ideally, I'd like to busywait unless
         * absolutely critical to yield */                                         \
        pthread_barrier_wait(&start_test);                                         \
@@ -445,6 +506,9 @@ void *lock_name##_thread(void *arg)                                            \
                this_time->pre = pre_lock;                                             \
                this_time->acq = acq_lock;                                             \
                this_time->un = un_lock;                                               \
+               /* Can turn these on or off to control which samples we gather */      \
+               this_time->valid = TRUE;                                               \
+               /* this_time->valid = (num_vcores() == max_vcores());  */              \
                                                                                \
                if (delay_time)                                                        \
                        ndelay(delay_time);                                                \
@@ -481,11 +545,14 @@ lock_func(mcscas,
           mcs_lock_lock(&mcs_lock, &mcs_qnode);,
           mcs_lock_unlock_cas(&mcs_lock, &mcs_qnode);)
 lock_func(mcspdr,
-          mcs_pdr_lock(&mcspdr_lock, &pdr_qnode);,
-          mcs_pdr_unlock(&mcspdr_lock, &pdr_qnode);)
-lock_func(__mcspdr,
-          __mcs_pdr_lock(&mcspdr_lock, &pdr_qnode);,
-          __mcs_pdr_unlock(&mcspdr_lock, &pdr_qnode);)
+          mcs_pdr_lock(&mcspdr_lock);,
+          mcs_pdr_unlock(&mcspdr_lock);)
+lock_func(mcspdro,
+          mcs_pdro_lock(&mcspdro_lock, &pdro_qnode);,
+          mcs_pdro_unlock(&mcspdro_lock, &pdro_qnode);)
+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);)
@@ -499,6 +566,12 @@ static int get_acq_latency(void **data, int i, int j, uint64_t *sample)
        /* 0 for initial time means we didn't measure */
        if (times[i][j].pre == 0)
                return -1;
+       /* can optionally throw out invalid times (keep this in sync with the
+        * lock_test macro, based on what you want to meaasure. */
+       #if 0
+       if (!times[i][j].valid)
+               return -1;
+       #endif
        *sample = times[i][j].acq - times[i][j].pre - get_tsc_overhead();
        return 0;
 }
@@ -529,12 +602,15 @@ uint64_t preempts[MAX_NR_EVENT_TRACES] = {0};
 uint64_t indirs[MAX_NR_EVENT_TRACES] = {0};
 atomic_t preempt_idx;
 atomic_t indir_idx;
+atomic_t preempt_cnt;
+atomic_t indir_cnt;
 
 static void handle_preempt(struct event_msg *ev_msg, unsigned int ev_type)
 {
        unsigned long my_slot = atomic_fetch_and_add(&preempt_idx, 1);
        if (my_slot < MAX_NR_EVENT_TRACES)
                preempts[my_slot] = read_tsc();
+       atomic_inc(&preempt_cnt);
        handle_vc_preempt(ev_msg, ev_type);
 }
 
@@ -543,6 +619,7 @@ static void handle_indir(struct event_msg *ev_msg, unsigned int ev_type)
        unsigned long my_slot = atomic_fetch_and_add(&indir_idx, 1);
        if (my_slot < MAX_NR_EVENT_TRACES)
                indirs[my_slot] = read_tsc();
+       atomic_inc(&indir_cnt);
        handle_vc_indir(ev_msg, ev_type);
 }
 
@@ -555,8 +632,11 @@ static void print_preempt_trace(uint64_t starttsc, int nr_print_rows)
                printf("No preempt trace available when faking vc ctx\n");
                return;
        }
+       printf("\n");
+       printf("Nr Preempts: %d\n", atomic_read(&preempt_cnt));
+       printf("Nr Indirs  : %d\n", atomic_read(&indir_cnt));
        if (preempt_rows)
-               printf("\nPreempt/Indir events:\n-----------------\n");
+               printf("Preempt/Indir events:\n-----------------\n");
        for (int i = 0; i < preempt_rows; i++) {
                if (preempts[i])
                        printf("Preempt %3d at %6llu\n", i, tsc2msec(preempts[i]
@@ -579,6 +659,8 @@ static void os_prep_work(int nr_threads)
        }
        atomic_init(&preempt_idx, 0);
        atomic_init(&indir_idx, 0);
+       atomic_init(&preempt_cnt, 0);
+       atomic_init(&indir_cnt, 0);
        pthread_can_vcore_request(FALSE);       /* 2LS won't manage vcores */
        pthread_lib_init();                                     /* gives us one vcore */
        ev_handlers[EV_VCORE_PREEMPT] = handle_preempt;
@@ -659,8 +741,12 @@ static error_t parse_opt (int key, char *arg, struct argp_state *state)
                                pargs->lock_type = mcspdr_thread;
                                break;
                        }
-                       if (!strcmp("__mcspdr", arg)) {
-                               pargs->lock_type = __mcspdr_thread;
+                       if (!strcmp("mcspdro", arg)) {
+                               pargs->lock_type = mcspdro_thread;
+                               break;
+                       }
+                       if (!strcmp("__mcspdro", arg)) {
+                               pargs->lock_type = __mcspdro_thread;
                                break;
                        }
                        if (!strcmp("spin", arg)) {
@@ -716,6 +802,7 @@ int main(int argc, char** argv)
        argp_parse(&argp, argc, argv, 0, 0, &pargs);
        nr_threads = pargs.nr_threads;
        nr_loops = pargs.nr_loops;
+       mcs_pdr_init(&mcspdr_lock);
 
        worker_threads = malloc(sizeof(pthread_t) * nr_threads);
        if (!worker_threads) {
index 2c5d0f5..93170e8 100644 (file)
@@ -57,37 +57,62 @@ void mcs_unlock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
  * The basic idea is that when spinning, vcores make sure someone else is
  * making progress that will lead to them not spinning.  Usually, it'll be to
  * make sure the lock holder (if known) is running.  If we don't know the lock
- * holder, we nsure the end of whatever chain we can see is running, which will
- * make sure its predecessor runs, which will eventually unjam the system.
- *
- * These are memory safe ones.  In the future, we can make ones that you pass
- * the qnode to, so long as you never free the qnode storage (stacks).  */
+ * holder, we ensure the end of whatever chain we can see is running, which
+ * will make sure its predecessor runs, which will eventually unjam the system.
+ * */
+
+/* Old style.  Has trouble getting out of 'preempt/change-to storms' under
+ * heavy contention and with preemption. */
+struct mcs_pdro_qnode
+{
+       struct mcs_pdro_qnode *next;
+       int locked;
+       uint32_t vcoreid;
+}__attribute__((aligned(ARCH_CL_SIZE)));
+
+struct mcs_pdro_lock
+{
+       struct mcs_pdro_qnode *lock;
+};
+
+#define MCSPDRO_LOCK_INIT {0}
+#define MCSPDRO_QNODE_INIT {0, 0, 0}
+
+void mcs_pdro_init(struct mcs_pdro_lock *lock);
+void mcs_pdro_fini(struct mcs_pdro_lock *lock);
+void mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
+void mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
+
+/* Only call these if you have notifs disabled and know your vcore's qnode.
+ * Mostly used for debugging, benchmarks, or critical code. */
+void __mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
+void __mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
+void __mcs_pdro_unlock_no_cas(struct mcs_pdro_lock *lock,
+                             struct mcs_pdro_qnode *qnode);
+
+/* New style: under heavy contention with preemption, they won't enter the
+ * 'preempt/change_to storm' that can happen to PDRs, at the cost of some
+ * performance.  This is the default. */
 struct mcs_pdr_qnode
 {
        struct mcs_pdr_qnode *next;
        int locked;
-       uint32_t vcoreid;
 }__attribute__((aligned(ARCH_CL_SIZE)));
 
 struct mcs_pdr_lock
 {
-       struct mcs_pdr_qnode *lock;
+       struct mcs_pdr_qnode *lock __attribute__((aligned(ARCH_CL_SIZE)));
+       uint32_t lockholder_vcoreid __attribute__((aligned(ARCH_CL_SIZE)));
+       struct mcs_pdr_qnode *qnodes __attribute__((aligned(ARCH_CL_SIZE)));
 };
 
-#define MCSPDR_LOCK_INIT {0}
-#define MCSPDR_QNODE_INIT {0, 0, 0}
+#define MCSPDR_NO_LOCKHOLDER ((uint32_t)-1)
 
 void mcs_pdr_init(struct mcs_pdr_lock *lock);
 void mcs_pdr_fini(struct mcs_pdr_lock *lock);
-void mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode);
-void mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode);
+void mcs_pdr_lock(struct mcs_pdr_lock *lock);
+void mcs_pdr_unlock(struct mcs_pdr_lock *lock);
 
-/* Only call these if you have notifs disabled and know your vcore's qnode.
- * Mostly used for debugging, benchmarks, or critical code. */
-void __mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode);
-void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode);
-void __mcs_pdr_unlock_no_cas(struct mcs_pdr_lock *lock,
-                             struct mcs_pdr_qnode *qnode);
 #ifdef __cplusplus
 }
 #endif
index 5616d33..d820100 100644 (file)
@@ -165,12 +165,14 @@ void mcs_barrier_wait(mcs_barrier_t* b, size_t pid)
 }
 
 /* Preemption detection and recovering MCS locks. */
-void mcs_pdr_init(struct mcs_pdr_lock *lock)
+/* Old style.  Has trouble getting out of 'preempt/change-to storms' under
+ * heavy contention and with preemption. */
+void mcs_pdro_init(struct mcs_pdro_lock *lock)
 {
        lock->lock = 0;
 }
 
-void mcs_pdr_fini(struct mcs_pdr_lock *lock)
+void mcs_pdro_fini(struct mcs_pdro_lock *lock)
 {
 }
 
@@ -184,9 +186,9 @@ void mcs_pdr_fini(struct mcs_pdr_lock *lock)
  * Even if they are no longer the lockholder, they will be checking preemption
  * messages and will help break out of the deadlock.  So long as we don't
  * spin uncontrollably, we're okay. */
-void __mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+void __mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
 {
-       struct mcs_pdr_qnode *predecessor;
+       struct mcs_pdro_qnode *predecessor;
        uint32_t pred_vcoreid;
        /* Now the actual lock */
        qnode->next = 0;
@@ -216,7 +218,7 @@ void __mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
 
 /* Using the CAS style unlocks, since the usurper recovery is a real pain in the
  * ass */
-void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+void __mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
 {
        uint32_t a_tail_vcoreid;
        /* Check if someone is already waiting on us to unlock */
@@ -250,15 +252,15 @@ void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
        }
 }
 
-/* Actual MCS-PDR locks.  Don't worry about initializing any fields of qnode.
+/* Actual MCS-PDRO locks.  Don't worry about initializing any fields of qnode.
  * We'll do vcoreid here, and the locking code deals with the other fields */
-void mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+void mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
 {
        /* Disable notifs, if we're an _M uthread */
        uth_disable_notifs();
        cmb();  /* in the off-chance the compiler wants to read vcoreid early */
        qnode->vcoreid = vcore_id();
-       __mcs_pdr_lock(lock, qnode);
+       __mcs_pdro_lock(lock, qnode);
 }
 
 /* CAS-less unlock, not quite as efficient and will make sure every vcore runs
@@ -271,10 +273,10 @@ void mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
  * but a little more difficult to follow.  Also, I'm adjusting this comment
  * months after writing it originally, so it is probably not sufficient, but
  * necessary. */
-void __mcs_pdr_unlock_no_cas(struct mcs_pdr_lock *lock,
-                             struct mcs_pdr_qnode *qnode)
+void __mcs_pdro_unlock_no_cas(struct mcs_pdro_lock *lock,
+                             struct mcs_pdro_qnode *qnode)
 {
-       struct mcs_pdr_qnode *old_tail, *usurper;
+       struct mcs_pdro_qnode *old_tail, *usurper;
        /* 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() */
@@ -327,9 +329,159 @@ void __mcs_pdr_unlock_no_cas(struct mcs_pdr_lock *lock,
        }
 }
 
-void mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+void mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
 {
-       __mcs_pdr_unlock(lock, qnode);
+       __mcs_pdro_unlock(lock, qnode);
        /* Enable notifs, if we're an _M uthread */
        uth_enable_notifs();
 }
+
+/* New style: under heavy contention with preemption, they won't enter the
+ * 'preempt/change_to storm' that can happen to PDRs, at the cost of some
+ * performance.  This is the default. */
+void mcs_pdr_init(struct mcs_pdr_lock *lock)
+{
+       int ret;
+       lock->lock = 0;
+       lock->lockholder_vcoreid = MCSPDR_NO_LOCKHOLDER;
+       ret = posix_memalign((void**)&lock->qnodes,
+                            __alignof__(struct mcs_pdr_qnode),
+                            sizeof(struct mcs_pdr_qnode) * max_vcores());
+       assert(!ret);
+}
+
+void mcs_pdr_fini(struct mcs_pdr_lock *lock)
+{
+       free(lock->qnodes);
+}
+
+/* Similar to the original PDR lock, this tracks the lockholder for better
+ * recovery from preemptions.  Under heavy contention, changing to the
+ * lockholder instead of pred makes it more likely to have a vcore outside the
+ * MCS chain handle the preemption.  If that never happens, performance will
+ * suffer.
+ *
+ * Simply checking the lockholder causes a lot of unnecessary traffic, so we
+ * first look for signs of preemption in read-mostly locations (by comparison,
+ * the lockholder changes on every lock/unlock).
+ *
+ * We also use the "qnodes are in the lock" style, which is slightly slower than
+ * using the stack in regular MCS/MCSPDR locks, but it speeds PDR up a bit by
+ * not having to read other qnodes' memory to determine their vcoreid.  The
+ * slowdown may be due to some weird caching/prefetch settings (like Adjacent
+ * Cacheline Prefetch).
+ *
+ * Note that these locks, like all PDR locks, have opportunities to accidentally
+ * ensure some vcore runs that isn't in the chain.  Whenever we read lockholder
+ * or even pred, that particular vcore might subsequently unlock and then get
+ * preempted (or change_to someone else) before we ensure they run.  If this
+ * happens and there is another VC in the MCS chain, it will make sure the right
+ * cores run.  If there are no other vcores in the chain, it is up to the rest
+ * of the vcore/event handling system to deal with this, which should happen
+ * when one of the other vcores handles the preemption message generated by our
+ * change_to. */
+void __mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+{
+       struct mcs_pdr_qnode *predecessor;
+       uint32_t pred_vcoreid;
+       struct mcs_pdr_qnode *qnode0 = qnode - vcore_id();
+       seq_ctr_t seq;
+       qnode->next = 0;
+       cmb();  /* swap provides a CPU mb() */
+       predecessor = atomic_swap_ptr((void**)&lock->lock, qnode);
+       if (predecessor) {
+               qnode->locked = 1;
+               pred_vcoreid = predecessor - qnode0;    /* can compute this whenever */
+               wmb();  /* order the locked write before the next write */
+               predecessor->next = qnode;
+               seq = ACCESS_ONCE(__procinfo.coremap_seqctr);
+               /* no need for a wrmb(), since this will only get unlocked after they
+                * read our pred->next write */
+               while (qnode->locked) {
+                       /* Check to see if anything is amiss.  If someone in the chain is
+                        * preempted, then someone will notice.  Simply checking our pred
+                        * isn't that great of an indicator of preemption.  The reason is
+                        * that the offline vcore is most likely the lockholder (under heavy
+                        * lock contention), and we want someone farther back in the chain
+                        * to notice (someone that will stay preempted long enough for a
+                        * vcore outside the chain to recover them).  Checking the seqctr
+                        * will tell us of any preempts since we started, so if a storm
+                        * starts while we're spinning, we can join in and try to save the
+                        * lockholder before its successor gets it.
+                        *
+                        * Also, if we're the lockholder, then we need to let our pred run
+                        * so they can hand us the lock. */
+                       if (vcore_is_preempted(pred_vcoreid) ||
+                           seq != __procinfo.coremap_seqctr) {
+                               if (lock->lockholder_vcoreid == MCSPDR_NO_LOCKHOLDER ||
+                                   lock->lockholder_vcoreid == vcore_id())
+                                       ensure_vcore_runs(pred_vcoreid);
+                               else
+                                       ensure_vcore_runs(lock->lockholder_vcoreid);
+                       }
+                       cpu_relax();
+               }
+       } else {
+               lock->lockholder_vcoreid = vcore_id();
+       }
+}
+
+void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
+{
+       uint32_t a_tail_vcoreid;
+       struct mcs_pdr_qnode *qnode0 = qnode - vcore_id();
+       /* 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 (atomic_cas_ptr((void**)&lock->lock, qnode, 0)) {
+                       /* This is racy with the new lockholder.  it's possible that we'll
+                        * clobber their legit write, though it doesn't actually hurt
+                        * correctness.  it'll get sorted out on the next unlock. */
+                       lock->lockholder_vcoreid = MCSPDR_NO_LOCKHOLDER;
+                       return;
+               }
+               /* Get the tail (or someone who recently was the tail, but could now
+                * be farther up the chain), in prep for our spinning.  Could do an
+                * ACCESS_ONCE on lock->lock */
+               a_tail_vcoreid = lock->lock - qnode0;
+               /* 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) {
+                       /* We need to get our next to run, but we don't know who they are.
+                        * If we make sure a tail is running, that will percolate up to make
+                        * sure our qnode->next is running */
+                       ensure_vcore_runs(a_tail_vcoreid);
+                       cpu_relax();
+               }
+               /* Alpha wants a read_barrier_depends() here */
+               lock->lockholder_vcoreid = qnode->next - qnode0;
+               wmb();  /* order the vcoreid write before the unlock */
+               qnode->next->locked = 0;
+       } else {
+               /* Note we're saying someone else is the lockholder, though we still are
+                * the lockholder until we unlock the next qnode.  Our next knows that
+                * if it sees itself is the lockholder, that it needs to make sure we
+                * run. */
+               lock->lockholder_vcoreid = qnode->next - qnode0;
+               /* 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;
+       }
+}
+
+void mcs_pdr_lock(struct mcs_pdr_lock *lock)
+{
+       uth_disable_notifs();
+       cmb();  /* in the off-chance the compiler wants to read vcoreid early */
+       __mcs_pdr_lock(lock, &lock->qnodes[vcore_id()]);
+}
+
+void mcs_pdr_unlock(struct mcs_pdr_lock *lock)
+{
+       __mcs_pdr_unlock(lock, &lock->qnodes[vcore_id()]);
+       uth_enable_notifs();
+}
index d8319d4..e4d896c 100644 (file)
@@ -12,7 +12,6 @@ struct futex_element {
   TAILQ_ENTRY(futex_element) link;
   pthread_t pthread;
   int *uaddr;
-  struct mcs_pdr_qnode *mcs_qnode;
 };
 TAILQ_HEAD(futex_queue, futex_element);
 
@@ -38,22 +37,20 @@ static void __futex_block(struct uthread *uthread, void *arg) {
        __pthread_generic_yield(e->pthread);
   e->pthread->state = PTH_BLK_MUTEX;
   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
-  mcs_pdr_unlock(&__futex.lock, e->mcs_qnode);
+  mcs_pdr_unlock(&__futex.lock);
 }
 
 static inline int futex_wait(int *uaddr, int val)
 {
-  struct mcs_pdr_qnode qnode;
-  mcs_pdr_lock(&__futex.lock, &qnode);
+  mcs_pdr_lock(&__futex.lock);
   if(*uaddr == val) {
     // We unlock in the body of __futex_block
     struct futex_element *e = kmem_cache_alloc(__futex.element_cache, 0); 
     e->uaddr = uaddr;
-    e->mcs_qnode = &qnode;
     uthread_yield(TRUE, __futex_block, e);
   }
   else {
-    mcs_pdr_unlock(&__futex.lock, &qnode);
+    mcs_pdr_unlock(&__futex.lock);
   }
   return 0;
 }
@@ -61,8 +58,7 @@ static inline int futex_wait(int *uaddr, int val)
 static inline int futex_wake(int *uaddr, int count)
 {
   struct futex_element *e,*n = NULL;
-  struct mcs_pdr_qnode qnode;
-  mcs_pdr_lock(&__futex.lock, &qnode);
+  mcs_pdr_lock(&__futex.lock);
   e = TAILQ_FIRST(&__futex.queue);
   while(e != NULL) {
     if(count > 0) {
@@ -77,7 +73,7 @@ static inline int futex_wake(int *uaddr, int count)
     }
     else break;
   }
-  mcs_pdr_unlock(&__futex.lock, &qnode);
+  mcs_pdr_unlock(&__futex.lock);
   return 0;
 }
 
index 6d8ab93..963b87f 100644 (file)
@@ -65,7 +65,6 @@ static int __pthread_allocate_stack(struct pthread_tcb *pt);
  * event.c (table of function pointers, stuff like that). */
 void __attribute__((noreturn)) pth_sched_entry(void)
 {
-       struct mcs_pdr_qnode qnode;
        uint32_t vcoreid = vcore_id();
        if (current_uthread) {
                run_current_uthread();
@@ -79,14 +78,14 @@ void __attribute__((noreturn)) pth_sched_entry(void)
        do {
                handle_events(vcoreid);
                __check_preempt_pending(vcoreid);
-               mcs_pdr_lock(&queue_lock, &qnode);
+               mcs_pdr_lock(&queue_lock);
                new_thread = TAILQ_FIRST(&ready_queue);
                if (new_thread) {
                        TAILQ_REMOVE(&ready_queue, new_thread, next);
                        TAILQ_INSERT_TAIL(&active_queue, new_thread, next);
                        threads_active++;
                        threads_ready--;
-                       mcs_pdr_unlock(&queue_lock, &qnode);
+                       mcs_pdr_unlock(&queue_lock);
                        /* If you see what looks like the same uthread running in multiple
                         * places, your list might be jacked up.  Turn this on. */
                        printd("[P] got uthread %08p on vc %d state %08p flags %08p\n",
@@ -95,7 +94,7 @@ void __attribute__((noreturn)) pth_sched_entry(void)
                               ((struct uthread*)new_thread)->flags);
                        break;
                }
-               mcs_pdr_unlock(&queue_lock, &qnode);
+               mcs_pdr_unlock(&queue_lock);
                /* no new thread, try to yield */
                printd("[P] No threads, vcore %d is yielding\n", vcore_id());
                /* TODO: you can imagine having something smarter here, like spin for a
@@ -120,7 +119,6 @@ static void __pthread_run(void)
 void pth_thread_runnable(struct uthread *uthread)
 {
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
-       struct mcs_pdr_qnode qnode;
        /* At this point, the 2LS can see why the thread blocked and was woken up in
         * the first place (coupling these things together).  On the yield path, the
         * 2LS was involved and was able to set the state.  Now when we get the
@@ -141,11 +139,11 @@ void pth_thread_runnable(struct uthread *uthread)
        pthread->state = PTH_RUNNABLE;
        /* Insert the newly created thread into the ready queue of threads.
         * It will be removed from this queue later when vcore_entry() comes up */
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        /* Again, GIANT WARNING: if you change this, change batch wakeup code */
        TAILQ_INSERT_TAIL(&ready_queue, pthread, next);
        threads_ready++;
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
        /* Smarter schedulers should look at the num_vcores() and how much work is
         * going on to make a decision about how many vcores to request. */
        if (can_adjust_vcores)
@@ -165,14 +163,13 @@ void pth_thread_runnable(struct uthread *uthread)
 void pth_thread_paused(struct uthread *uthread)
 {
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
-       struct mcs_pdr_qnode qnode;
        /* Remove from the active list.  Note that I don't particularly care about
         * the active list.  We keep it around because it causes bugs and keeps us
         * honest.  After all, some 2LS may want an active list */
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
        /* communicate to pth_thread_runnable */
        pthread->state = PTH_BLK_PAUSED;
        /* At this point, you could do something clever, like put it at the front of
@@ -226,14 +223,13 @@ void pth_thread_blockon_sysc(struct uthread *uthread, void *syscall)
        int old_flags;
        bool need_to_restart = FALSE;
        uint32_t vcoreid = vcore_id();
-       struct mcs_pdr_qnode qnode;
        /* rip from the active queue */
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
        pthread->state = PTH_BLK_SYSC;
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
        /* Set things up so we can wake this thread up later */
        sysc->u_data = uthread;
        /* Register our vcore's syscall ev_q to hear about this syscall. */
@@ -333,7 +329,6 @@ void pthread_lib_init(void)
        uintptr_t mmap_block;
        struct pthread_tcb *t;
        int ret;
-       struct mcs_pdr_qnode qnode;
        /* Some testing code might call this more than once (once for a slimmed down
         * pth 2LS, and another from pthread_create().  Also, this is racy, but the
         * first time through we are an SCP. */
@@ -353,10 +348,10 @@ void pthread_lib_init(void)
        t->joiner = 0;
        assert(t->id == 0);
        /* Put the new pthread (thread0) on the active queue */
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        threads_active++;
        TAILQ_INSERT_TAIL(&active_queue, t, next);
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
        /* Tell the kernel where and how we want to receive events.  This is just an
         * example of what to do to have a notification turned on.  We're turning on
         * USER_IPIs, posting events to vcore 0's vcpd, and telling the kernel to
@@ -459,11 +454,10 @@ int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
  * active queue is keeping us honest.  Need to export for sem and friends. */
 void __pthread_generic_yield(struct pthread_tcb *pthread)
 {
-       struct mcs_pdr_qnode qnode;
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
 }
 
 /* Callback/bottom half of join, called from __uthread_yield (vcore context).
@@ -697,7 +691,6 @@ int pthread_cond_broadcast(pthread_cond_t *c)
        unsigned int nr_woken = 0;      /* assuming less than 4 bil threads */
        struct pthread_queue restartees = TAILQ_HEAD_INITIALIZER(restartees);
        struct pthread_tcb *pthread_i;
-       struct mcs_pdr_qnode qnode;
        spin_pdr_lock(&c->spdr_lock);
        /* moves all items from waiters onto the end of restartees */
        TAILQ_CONCAT(&restartees, &c->waiters, next);
@@ -710,10 +703,10 @@ int pthread_cond_broadcast(pthread_cond_t *c)
                nr_woken++;
        }
        /* Amortize the lock grabbing over all restartees */
-       mcs_pdr_lock(&queue_lock, &qnode);
+       mcs_pdr_lock(&queue_lock);
        threads_ready += nr_woken;
        TAILQ_CONCAT(&ready_queue, &restartees, next);
-       mcs_pdr_unlock(&queue_lock, &qnode);
+       mcs_pdr_unlock(&queue_lock);
        if (can_adjust_vcores)
                vcore_request(threads_ready);
        return 0;
@@ -890,7 +883,6 @@ int pthread_barrier_wait(pthread_barrier_t *b)
        struct pthread_queue restartees = TAILQ_HEAD_INITIALIZER(restartees);
        struct pthread_tcb *pthread_i;
        struct barrier_junk local_junk;
-       struct mcs_pdr_qnode qnode;
        
        long old_count = atomic_fetch_and_add(&b->count, -1);
 
@@ -920,10 +912,10 @@ int pthread_barrier_wait(pthread_barrier_t *b)
                TAILQ_FOREACH(pthread_i, &restartees, next)
                        pthread_i->state = PTH_RUNNABLE;
                /* bulk restart waiters (skipping pth_thread_runnable()) */
-               mcs_pdr_lock(&queue_lock, &qnode);
+               mcs_pdr_lock(&queue_lock);
                threads_ready += nr_waiters;
                TAILQ_CONCAT(&ready_queue, &restartees, next);
-               mcs_pdr_unlock(&queue_lock, &qnode);
+               mcs_pdr_unlock(&queue_lock);
                if (can_adjust_vcores)
                        vcore_request(threads_ready);
                return PTHREAD_BARRIER_SERIAL_THREAD;