MCS-PDR locks take a *qnode
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 8 May 2013 00:11:48 +0000 (17:11 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Wed, 8 May 2013 00:11:48 +0000 (17:11 -0700)
Futex code can use either spinpdr or mcspdr, up to them.  For the
semaphore code, it was a simpler change to just change the lock style.

user/parlib/include/mcs.h
user/parlib/mcs.c
user/parlib/ucq.c
user/pthread/futex.c
user/pthread/pthread.c
user/pthread/semaphore.c
user/pthread/semaphore.h

index d991d4d..2c5d0f5 100644 (file)
@@ -69,21 +69,18 @@ struct mcs_pdr_qnode
        uint32_t vcoreid;
 }__attribute__((aligned(ARCH_CL_SIZE)));
 
-/* Want to pad out so lock doesn't share a CL with qnodes.  If we align both
- * pointers so that they have their own cache line, this actually performs
- * worse.  Meaning (for some unknown reason), if the lock shares a CL with
- * other random bss/data, the lock tests perf better... */
 struct mcs_pdr_lock
 {
        struct mcs_pdr_qnode *lock;
-       char padding[ARCH_CL_SIZE];
-       struct mcs_pdr_qnode *vc_qnodes;        /* malloc this at init time */
 };
 
+#define MCSPDR_LOCK_INIT {0}
+#define MCSPDR_QNODE_INIT {0, 0, 0}
+
 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);
-void mcs_pdr_unlock(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);
 
 /* Only call these if you have notifs disabled and know your vcore's qnode.
  * Mostly used for debugging, benchmarks, or critical code. */
index 2943904..85d6b03 100644 (file)
@@ -164,27 +164,16 @@ void mcs_barrier_wait(mcs_barrier_t* b, size_t pid)
        localflags->parity = 1-localflags->parity;
 }
 
-/* Preemption detection and recovering MCS locks.  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) */
+/* Preemption detection and recovering MCS locks. */
 void mcs_pdr_init(struct mcs_pdr_lock *lock)
 {
        lock->lock = 0;
-       lock->vc_qnodes = memalign(__alignof(struct mcs_pdr_qnode),
-                                  sizeof(struct mcs_pdr_qnode) * max_vcores());
-       assert(lock->vc_qnodes);
-       memset(lock->vc_qnodes, 0, sizeof(struct mcs_pdr_qnode) * max_vcores());
-       for (int i = 0; i < max_vcores(); i++)
-               lock->vc_qnodes[i].vcoreid = i;
 }
 
 void mcs_pdr_fini(struct mcs_pdr_lock *lock)
 {
-       assert(lock->vc_qnodes);
-       free(lock->vc_qnodes);
 }
 
-
 /* Internal version of the locking function, doesn't care if notifs are
  * disabled.  While spinning, we'll check to see if other vcores involved in the
  * locking are running.  If we change to that vcore, we'll continue when our
@@ -261,18 +250,14 @@ void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
        }
 }
 
-/* Actual MCS-PDR locks.  These use memory in the lock for their qnodes, though
- * the internal locking code doesn't care where the qnodes come from: so long as
- * they are not freed and can stand a random read of vcoreid. */
-void mcs_pdr_lock(struct mcs_pdr_lock *lock)
+/* Actual MCS-PDR 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)
 {
-       struct mcs_pdr_qnode *qnode;
        /* Disable notifs, if we're an _M uthread */
        uth_disable_notifs();
-       /* Get our qnode from the array.  vcoreid was preset, and the other fields
-        * get handled by the lock */
-       qnode = &lock->vc_qnodes[vcore_id()];
-       assert(qnode->vcoreid == vcore_id());   /* sanity */
+       cmb();  /* in the off-chance the compiler wants to read vcoreid early */
+       qnode->vcoreid = vcore_id();
        __mcs_pdr_lock(lock, qnode);
 }
 
@@ -342,10 +327,8 @@ void __mcs_pdr_unlock_no_cas(struct mcs_pdr_lock *lock,
        }
 }
 
-void mcs_pdr_unlock(struct mcs_pdr_lock *lock)
+void mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
 {
-       struct mcs_pdr_qnode *qnode = &lock->vc_qnodes[vcore_id()];
-       assert(qnode->vcoreid == vcore_id());   /* sanity */
 #ifndef __riscv__
        __mcs_pdr_unlock(lock, qnode);
 #else
index 9bcb43b..058105e 100644 (file)
@@ -70,6 +70,7 @@ int get_ucq_msg(struct ucq *ucq, struct event_msg *msg)
        /* Locking stuff.  Would be better with a spinlock, if we had them, since
         * this should be lightly contested.  */
        struct mcs_pdr_lock *ucq_lock = (struct mcs_pdr_lock*)(&ucq->u_lock);
+       struct mcs_pdr_qnode qnode;
 
        do {
 loop_top:
@@ -85,13 +86,13 @@ loop_top:
                if (slot_is_good(my_idx))
                        goto claim_slot;
                /* Slot is bad, let's try and fix it */
-               mcs_pdr_lock(ucq_lock);
+               mcs_pdr_lock(ucq_lock, &qnode);
                /* Reread the idx, in case someone else fixed things up while we
                 * were waiting/fighting for the lock */
                my_idx = atomic_read(&ucq->cons_idx);
                if (slot_is_good(my_idx)) {
                        /* Someone else fixed it already, let's just try to get out */
-                       mcs_pdr_unlock(ucq_lock);
+                       mcs_pdr_unlock(ucq_lock, &qnode);
                        /* Make sure this new slot has a producer (ucq isn't empty) */
                        if (my_idx == atomic_read(&ucq->prod_idx))
                                return -1;
@@ -133,7 +134,7 @@ loop_top:
                }
                /* All fixed up, unlock.  Other consumers may lock and check to make
                 * sure things are done. */
-               mcs_pdr_unlock(ucq_lock);
+               mcs_pdr_unlock(ucq_lock, &qnode);
                /* Now that everything is fixed, try again from the top */
                goto loop_top;
 claim_slot:
index e4d896c..d8319d4 100644 (file)
@@ -12,6 +12,7 @@ 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);
 
@@ -37,20 +38,22 @@ 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);
+  mcs_pdr_unlock(&__futex.lock, e->mcs_qnode);
 }
 
 static inline int futex_wait(int *uaddr, int val)
 {
-  mcs_pdr_lock(&__futex.lock);
+  struct mcs_pdr_qnode qnode;
+  mcs_pdr_lock(&__futex.lock, &qnode);
   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);
+    mcs_pdr_unlock(&__futex.lock, &qnode);
   }
   return 0;
 }
@@ -58,7 +61,8 @@ static inline int futex_wait(int *uaddr, int val)
 static inline int futex_wake(int *uaddr, int count)
 {
   struct futex_element *e,*n = NULL;
-  mcs_pdr_lock(&__futex.lock);
+  struct mcs_pdr_qnode qnode;
+  mcs_pdr_lock(&__futex.lock, &qnode);
   e = TAILQ_FIRST(&__futex.queue);
   while(e != NULL) {
     if(count > 0) {
@@ -73,7 +77,7 @@ static inline int futex_wake(int *uaddr, int count)
     }
     else break;
   }
-  mcs_pdr_unlock(&__futex.lock);
+  mcs_pdr_unlock(&__futex.lock, &qnode);
   return 0;
 }
 
index 722636b..6d8ab93 100644 (file)
@@ -65,6 +65,7 @@ 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();
@@ -78,14 +79,14 @@ void __attribute__((noreturn)) pth_sched_entry(void)
        do {
                handle_events(vcoreid);
                __check_preempt_pending(vcoreid);
-               mcs_pdr_lock(&queue_lock);
+               mcs_pdr_lock(&queue_lock, &qnode);
                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);
+                       mcs_pdr_unlock(&queue_lock, &qnode);
                        /* 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",
@@ -94,7 +95,7 @@ void __attribute__((noreturn)) pth_sched_entry(void)
                               ((struct uthread*)new_thread)->flags);
                        break;
                }
-               mcs_pdr_unlock(&queue_lock);
+               mcs_pdr_unlock(&queue_lock, &qnode);
                /* 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
@@ -119,6 +120,7 @@ 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
@@ -139,11 +141,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);
+       mcs_pdr_lock(&queue_lock, &qnode);
        /* 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);
+       mcs_pdr_unlock(&queue_lock, &qnode);
        /* 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)
@@ -163,13 +165,14 @@ 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);
+       mcs_pdr_lock(&queue_lock, &qnode);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock);
+       mcs_pdr_unlock(&queue_lock, &qnode);
        /* 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
@@ -223,13 +226,14 @@ 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);
+       mcs_pdr_lock(&queue_lock, &qnode);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock);
+       mcs_pdr_unlock(&queue_lock, &qnode);
        /* 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. */
@@ -329,6 +333,7 @@ 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. */
@@ -348,10 +353,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);      /* arguably, we don't need these (_S mode) */
+       mcs_pdr_lock(&queue_lock, &qnode);
        threads_active++;
        TAILQ_INSERT_TAIL(&active_queue, t, next);
-       mcs_pdr_unlock(&queue_lock);
+       mcs_pdr_unlock(&queue_lock, &qnode);
        /* 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
@@ -454,10 +459,11 @@ 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)
 {
-       mcs_pdr_lock(&queue_lock);
+       struct mcs_pdr_qnode qnode;
+       mcs_pdr_lock(&queue_lock, &qnode);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_pdr_unlock(&queue_lock);
+       mcs_pdr_unlock(&queue_lock, &qnode);
 }
 
 /* Callback/bottom half of join, called from __uthread_yield (vcore context).
@@ -691,6 +697,7 @@ 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);
@@ -703,10 +710,10 @@ int pthread_cond_broadcast(pthread_cond_t *c)
                nr_woken++;
        }
        /* Amortize the lock grabbing over all restartees */
-       mcs_pdr_lock(&queue_lock);
+       mcs_pdr_lock(&queue_lock, &qnode);
        threads_ready += nr_woken;
        TAILQ_CONCAT(&ready_queue, &restartees, next);
-       mcs_pdr_unlock(&queue_lock);
+       mcs_pdr_unlock(&queue_lock, &qnode);
        if (can_adjust_vcores)
                vcore_request(threads_ready);
        return 0;
@@ -883,6 +890,7 @@ 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);
 
@@ -912,10 +920,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);
+               mcs_pdr_lock(&queue_lock, &qnode);
                threads_ready += nr_waiters;
                TAILQ_CONCAT(&ready_queue, &restartees, next);
-               mcs_pdr_unlock(&queue_lock);
+               mcs_pdr_unlock(&queue_lock, &qnode);
                if (can_adjust_vcores)
                        vcore_request(threads_ready);
                return PTHREAD_BARRIER_SERIAL_THREAD;
index 5b8751c..0e5e258 100644 (file)
@@ -11,7 +11,7 @@ int sem_init (sem_t *__sem, int __pshared, unsigned int __value)
        }
        __sem->count = __value;
        TAILQ_INIT(&__sem->queue);
-       mcs_pdr_init(&__sem->lock);
+       spin_pdr_init(&__sem->lock);
        return 0;
 }
 
@@ -45,15 +45,15 @@ static void __sem_block(struct uthread *uthread, void *arg)
        __pthread_generic_yield(pthread);
        pthread->state = PTH_BLK_MUTEX;
        TAILQ_INSERT_TAIL(&__sem->queue, pthread, next);
-       mcs_pdr_unlock(&__sem->lock);
+       spin_pdr_unlock(&__sem->lock);
 }
 
 int sem_wait (sem_t *__sem)
 {
-       mcs_pdr_lock(&__sem->lock);
+       spin_pdr_lock(&__sem->lock);
        if(__sem->count > 0) {
                __sem->count--;
-               mcs_pdr_unlock(&__sem->lock);
+               spin_pdr_unlock(&__sem->lock);
        }
        else {
                // We unlock in the body of __sem_block
@@ -65,24 +65,24 @@ int sem_wait (sem_t *__sem)
 int sem_trywait (sem_t *__sem)
 {
        int ret = -1;
-       mcs_pdr_lock(&__sem->lock);
+       spin_pdr_lock(&__sem->lock);
        if(__sem->count > 0) {
                __sem->count--;
                ret = 0;
        }
-       mcs_pdr_unlock(&__sem->lock);
+       spin_pdr_unlock(&__sem->lock);
        return ret;
 }
 
 int sem_post (sem_t *__sem)
 {
-       mcs_pdr_lock(&__sem->lock);
+       spin_pdr_lock(&__sem->lock);
        pthread_t pthread = TAILQ_FIRST(&__sem->queue);
        if(pthread)
                TAILQ_REMOVE(&__sem->queue, pthread, next);
        else
                __sem->count++; 
-       mcs_pdr_unlock(&__sem->lock);
+       spin_pdr_unlock(&__sem->lock);
 
        if(pthread) {
                uthread_runnable((struct uthread*)pthread);
@@ -92,9 +92,9 @@ int sem_post (sem_t *__sem)
 
 int sem_getvalue (sem_t *__restrict __sem, int *__restrict __sval)
 {
-       mcs_pdr_lock(&__sem->lock);
+       spin_pdr_lock(&__sem->lock);
        *__sval = __sem->count;
-       mcs_pdr_unlock(&__sem->lock);
+       spin_pdr_unlock(&__sem->lock);
        return 0;
 }
 
index cbf8af0..028a484 100644 (file)
@@ -30,7 +30,7 @@ typedef struct sem
 {
        unsigned int count;
        struct pthread_queue queue;
-       struct mcs_pdr_lock lock;
+       struct spin_pdr_lock lock;
 } sem_t;
 
 extern int sem_init (sem_t *__sem, int __pshared, unsigned int __value);