MCS locks are smaller and don't rely on vcore_id()
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 4 Mar 2011 23:16:48 +0000 (15:16 -0800)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:00 +0000 (17:36 -0700)
If you had a non-irq_save MCS lock, you would have issues with having
multiple threads lock on the same vcore, or a thread locking and
unlocking on different vcores.

Also, this only uses memory for the callers spinning location (the
qnode) when needed, instead of statically allocating it.  The memory for
these should be per-thread (TLS, stack, whatever).  This also gets rid
of the need for the padding.

user/c3po/threads/threadlib.c
user/parlib/bthread.c
user/parlib/include/mcs.h
user/parlib/mcs.c
user/parlib/vcore.c
user/pthread/pthread.c

index b9e9228..cb633bd 100644 (file)
@@ -223,14 +223,15 @@ void main_thread_init()
   sleep_times.first_wake = 0;
 
   // Add main thread to the global list of threads
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   pl_add_tail(threadlist, main_thread);
   num_threads.total++;
   // Update number of running threads
   main_thread->state = RUNNING;
   num_threads.running++;
   num_threads.detached++;
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -353,13 +354,14 @@ void run_next_thread()
  
   // Keep trying to get a thread off of the scheduler queue
   thread_t *t; 
+  struct mcs_lock_qnode local_qn = {0};
   while(1) {
-    mcs_lock_lock(&thread_lock);
+    mcs_lock_lock(&thread_lock, &local_qn);
        // Check to see if we are in the processes of exiting the entire program.
        // If we are, then go ahead and yield this vcore. We are dying, afterall..
        if(gflags.exit_func_done) {
       bool yieldcore = __query_vcore_yield();
-      mcs_lock_unlock(&thread_lock);
+      mcs_lock_unlock(&thread_lock, &local_qn);
       if(yieldcore) vcore_yield();
     }
                
@@ -373,7 +375,7 @@ void run_next_thread()
        // the system if appropriate.
     if(t == NULL) {
       bool yieldcore = __query_vcore_yield();
-      mcs_lock_unlock(&thread_lock);
+      mcs_lock_unlock(&thread_lock, &local_qn);
       if(yieldcore) vcore_yield();
     }
        // Otherwise, if the thread is in the ZOMBIE state, then it must have been
@@ -381,7 +383,7 @@ void run_next_thread()
     // Reap it now, then go and grab the next thread.
     else if(t->state == ZOMBIE) {
       __free_thread_prep(t);
-      mcs_lock_unlock(&thread_lock);
+      mcs_lock_unlock(&thread_lock, &local_qn);
       free_thread(t);
     }
     // Otherwise, we've found a thread to run, so continue.
@@ -392,7 +394,7 @@ void run_next_thread()
   num_threads.runnable--;
   num_threads.running++;
   t->state = RUNNING;
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
  
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -484,7 +486,8 @@ static thread_t* new_thread(char *name, void* (*func)(void *), void *arg, thread
 //  bg_dummy_node->num_here++;
 //  t->curr_stats.node = bg_dummy_node;
 
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   // Up the count of detached threads if this thread should be detached
   if( attr ) {
     t->joinable = attr->joinable;
@@ -500,7 +503,7 @@ static thread_t* new_thread(char *name, void* (*func)(void *), void *arg, thread
   t->state = RUNNABLE;
   num_threads.runnable++;
   bool requestcore = __query_vcore_request();
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -760,7 +763,8 @@ static int __thread_yield(int suspend, unsigned long long timeout)
 //  }
 
   // Decide what to do with the thread
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   // Drop the count of running threads
   num_threads.running--;
   // If we should suspend it, do so for the specified timeout
@@ -778,7 +782,7 @@ static int __thread_yield(int suspend, unsigned long long timeout)
     num_threads.runnable++;
     sched_add_thread(current_thread);
   }
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -914,6 +918,7 @@ void thread_exit(void *ret)
 //  }
     
   // If we are the main thread...
+  struct mcs_lock_qnode local_qn = {0};
   while(unlikely(t == main_thread)) {
     // Check if we really can exit the program now.
     // If so, end of program!
@@ -927,9 +932,9 @@ void thread_exit(void *ret)
       // Return back to glibc and exit the program!
          // First set a global flag so no other vcores try to pull new threads off
          // of any lists (these lists are about to be deallocated...)
-      mcs_lock_lock(&thread_lock);
+      mcs_lock_lock(&thread_lock, &local_qn);
       gflags.exit_func_done = TRUE;
-      mcs_lock_unlock(&thread_lock);
+      mcs_lock_unlock(&thread_lock, &local_qn);
 
       printf("Dying with %d vcores\n", num_vcores());
       printf("Program exiting normally!\n");
@@ -943,7 +948,7 @@ void thread_exit(void *ret)
   }
   // Otherwise...
   // Update thread counts and resume blocked threads
-  mcs_lock_lock(&thread_lock);
+  mcs_lock_lock(&thread_lock, &local_qn);
   num_threads.running--;
   num_threads.zombie++;
   t->state = ZOMBIE;
@@ -975,7 +980,7 @@ void thread_exit(void *ret)
   // Check to see if we now have less threads than we have vcores.  If so,
   // prepare to yield the current core back to the system.
   bool yieldcore = __query_vcore_yield();
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -1005,14 +1010,15 @@ int thread_join(thread_t *t, void **ret)
 
   // Wait for the thread to complete
   tdebug( "thread state: %d\n" ,t->state);
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   if(t->state != ZOMBIE) {
     t->join_thread = current_thread;
-    mcs_lock_unlock(&thread_lock);
+    mcs_lock_unlock(&thread_lock, &local_qn);
        CAP_SET_SYSCALL();
     thread_suspend_self(0);
     CAP_CLEAR_SYSCALL();
-    mcs_lock_lock(&thread_lock);
+    mcs_lock_lock(&thread_lock, &local_qn);
   }
 
   // Set the return value
@@ -1021,7 +1027,7 @@ int thread_join(thread_t *t, void **ret)
 
   // Free the memory associated with the joined thread. 
   __free_thread_prep(t);
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
   free_thread(t);
 
   tdebug("Exit\n");
@@ -1066,10 +1072,11 @@ static void __thread_resume(thread_t *t)
 
 void thread_resume(thread_t *t)
 {
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   __thread_resume(t);
   bool requestcore = __query_vcore_request();
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   // Maybe request a new vcore if we are running low
   if(requestcore) vcore_request(1);
@@ -1080,10 +1087,11 @@ void thread_set_detached(thread_t *t)
   if(!t->joinable)
     return;
   
-  mcs_lock_lock(&thread_lock);
+  struct mcs_lock_qnode local_qn = {0};
+  mcs_lock_lock(&thread_lock, &local_qn);
   t->joinable = 0;
   num_threads.detached++;
-  mcs_lock_unlock(&thread_lock);
+  mcs_lock_unlock(&thread_lock, &local_qn);
 
   tdebug("running: %d, runnable: %d, suspended: %d, detached: %d\n", 
          num_threads.running, num_threads.runnable, 
@@ -1346,6 +1354,7 @@ static void sleepq_check_wakeup(int sync)
   // the last check. If it's greater, update the remaining sleep time
   // and set first_wake to now + the new sleep time.
   linked_list_entry_t *e;
+  struct mcs_lock_qnode local_qn = {0};
   while (interval > 0 && (e = ll_view_head(sleepq))) {
     thread_t *t = (thread_t *)pl_get_pointer(e);
 
@@ -1359,10 +1368,10 @@ static void sleepq_check_wakeup(int sync)
     t->sleep = -1;
     t->timeout = 1;
 
-    mcs_lock_lock(&thread_lock);
+    mcs_lock_lock(&thread_lock, &local_qn);
     ll_free_entry(sleepq, ll_remove_head(sleepq));
     __thread_make_runnable(t);
-    mcs_lock_unlock(&thread_lock);
+    mcs_lock_unlock(&thread_lock, &local_qn);
   }
 
   if (ll_size(sleepq) == 0) {
index ab20bf5..6c045d2 100644 (file)
@@ -37,13 +37,14 @@ bthread_t queue_remove(bthread_t* head, bthread_t* tail)
 
 void vcore_entry()
 {
+  struct mcs_lock_qnode local_qn = {0};
   bthread_t node = NULL;
   while(1)
   {
-    mcs_lock_lock(&work_queue_lock);
+    mcs_lock_lock(&work_queue_lock, &local_qn);
     if(work_queue_head)
       node = queue_remove(&work_queue_head,&work_queue_tail);
-    mcs_lock_unlock(&work_queue_lock);
+    mcs_lock_unlock(&work_queue_lock, &local_qn);
 
     if(node)
       break;
@@ -73,6 +74,7 @@ int bthread_attr_destroy(bthread_attr_t *a)
 int bthread_create(bthread_t* thread, const bthread_attr_t* attr,
                    void *(*start_routine)(void *), void* arg)
 {
+  struct mcs_lock_qnode local_qn = {0};
   bthread_once(&init_once,&_bthread_init);
 
   *thread = (bthread_t)malloc(sizeof(work_queue_t));
@@ -81,14 +83,14 @@ int bthread_create(bthread_t* thread, const bthread_attr_t* attr,
   (*thread)->next = 0;
   (*thread)->finished = 0;
   (*thread)->detached = 0;
-  mcs_lock_lock(&work_queue_lock);
+  mcs_lock_lock(&work_queue_lock, &local_qn);
   {
     threads_active++;
     queue_insert(&work_queue_head,&work_queue_tail,*thread);
     // don't return until we get a vcore
     while(threads_active > num_vcores() && vcore_request(1));
   }
-  mcs_lock_unlock(&work_queue_lock);
+  mcs_lock_unlock(&work_queue_lock, &local_qn);
 
   return 0;
 }
@@ -243,15 +245,16 @@ int bthread_equal(bthread_t t1, bthread_t t2)
 
 void bthread_exit(void* ret)
 {
+  struct mcs_lock_qnode local_qn = {0};
   bthread_once(&init_once,&_bthread_init);
 
   bthread_t t = bthread_self();
 
-  mcs_lock_lock(&work_queue_lock);
+  mcs_lock_lock(&work_queue_lock, &local_qn);
   threads_active--;
   if(threads_active == 0)
     exit(0);
-  mcs_lock_unlock(&work_queue_lock);
+  mcs_lock_unlock(&work_queue_lock, &local_qn);
 
   if(t)
   {
@@ -273,6 +276,7 @@ int bthread_once(bthread_once_t* once_control, void (*init_routine)(void))
 
 int bthread_barrier_init(bthread_barrier_t* b, const bthread_barrierattr_t* a, int count)
 {
+  struct mcs_lock_qnode local_qn = {0};
   memset(b->local_sense,0,sizeof(b->local_sense));
 
   b->sense = 0;
@@ -283,12 +287,13 @@ int bthread_barrier_init(bthread_barrier_t* b, const bthread_barrierattr_t* a, i
 
 int bthread_barrier_wait(bthread_barrier_t* b)
 {
+  struct mcs_lock_qnode local_qn = {0};
   int id = vcore_id();
   int ls = b->local_sense[32*id] = 1 - b->local_sense[32*id];
 
-  mcs_lock_lock(&b->lock);
+  mcs_lock_lock(&b->lock, &local_qn);
   int count = --b->count;
-  mcs_lock_unlock(&b->lock);
+  mcs_lock_unlock(&b->lock, &local_qn);
 
   if(count == 0)
   {
index 0f9c378..7d40af0 100644 (file)
@@ -14,14 +14,11 @@ typedef struct mcs_lock_qnode
 {
        volatile struct mcs_lock_qnode* volatile next;
        volatile int locked;
-       char pad[ARCH_CL_SIZE-sizeof(void*)-sizeof(int)];
 } mcs_lock_qnode_t;
 
-typedef struct
+typedef struct mcs_lock
 {
        mcs_lock_qnode_t* lock;
-       char pad[ARCH_CL_SIZE-sizeof(mcs_lock_qnode_t*)];
-       mcs_lock_qnode_t qnode[MAX_VCORES] __attribute__((aligned(8)));
 } mcs_lock_t;
 
 typedef struct
@@ -43,9 +40,12 @@ typedef struct
 int mcs_barrier_init(mcs_barrier_t* b, size_t nprocs);
 void mcs_barrier_wait(mcs_barrier_t* b, size_t vcoreid);
 
-void mcs_lock_init(mcs_lock_t* lock);
-void mcs_lock_unlock(mcs_lock_t* lock);
-void mcs_lock_lock(mcs_lock_t* l);
+void mcs_lock_init(struct mcs_lock *lock);
+/* Caller needs to alloc (and zero) their own qnode to spin on.  The memory
+ * should be on a cacheline that is 'per-thread'.  This could be on the stack,
+ * in a thread control block, etc. */
+void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
+void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
 
 #ifdef __cplusplus
 }
index e031491..3fb73d7 100644 (file)
@@ -5,32 +5,32 @@
 #include <stdlib.h>
 
 // MCS locks
-void mcs_lock_init(mcs_lock_t* lock)
+void 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)
+static inline mcs_lock_qnode_t *mcs_qnode_swap(mcs_lock_qnode_t **addr,
+                                               mcs_lock_qnode_t *val)
 {
        return (mcs_lock_qnode_t*)atomic_swap((int*)addr,(int)val);
 }
 
-void mcs_lock_lock(mcs_lock_t* lock)
+void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
 {
-       mcs_lock_qnode_t* qnode = &lock->qnode[vcore_id()];
        qnode->next = 0;
        mcs_lock_qnode_t* predecessor = mcs_qnode_swap(&lock->lock,qnode);
        if(predecessor)
        {
                qnode->locked = 1;
                predecessor->next = qnode;
-               while(qnode->locked);
+               while(qnode->locked)
+                       cpu_relax();
        }
 }
 
-void mcs_lock_unlock(mcs_lock_t* lock)
+void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
 {
-       mcs_lock_qnode_t* qnode = &lock->qnode[vcore_id()];
        if(qnode->next == 0)
        {
                mcs_lock_qnode_t* old_tail = mcs_qnode_swap(&lock->lock,0);
index 4da73da..07de9c1 100644 (file)
@@ -132,6 +132,7 @@ vcore_init_fail:
  * 1), since the kernel won't block the call. */
 int vcore_request(size_t k)
 {
+       struct mcs_lock_qnode local_qn = {0};
        int ret = -1;
        size_t i,j;
 
@@ -140,7 +141,7 @@ int vcore_request(size_t k)
 
        // TODO: could do this function without a lock once we 
        // have atomic fetch and add in user space
-       mcs_lock_lock(&_vcore_lock);
+       mcs_lock_lock(&_vcore_lock, &local_qn);
 
        size_t vcores_wanted = num_vcores() + k;
        if(k < 0 || vcores_wanted > max_vcores())
@@ -158,7 +159,7 @@ int vcore_request(size_t k)
        ret = sys_resource_req(RES_CORES, vcores_wanted, 1, 0);
 
 fail:
-       mcs_lock_unlock(&_vcore_lock);
+       mcs_lock_unlock(&_vcore_lock, &local_qn);
        return ret;
 }
 
index c6ea458..0a7fce9 100644 (file)
@@ -59,6 +59,7 @@ static int __pthread_allocate_stack(struct pthread_tcb *pt);
  * main()) */
 struct uthread *pth_init(void)
 {
+       struct mcs_lock_qnode local_qn = {0};
        /* 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
@@ -73,10 +74,10 @@ struct uthread *pth_init(void)
        assert(t->id == 0);
 
        /* Put the new pthread on the active queue */
-       mcs_lock_lock(&queue_lock);
+       mcs_lock_lock(&queue_lock, &local_qn);
        threads_active++;
        TAILQ_INSERT_TAIL(&active_queue, t, next);
-       mcs_lock_unlock(&queue_lock);
+       mcs_lock_unlock(&queue_lock, &local_qn);
        return (struct uthread*)t;
 }
 
@@ -91,7 +92,8 @@ void pth_sched_entry(void)
        }
        /* no one currently running, so lets get someone from the ready queue */
        struct pthread_tcb *new_thread = NULL;
-       mcs_lock_lock(&queue_lock);
+       struct mcs_lock_qnode local_qn = {0};
+       mcs_lock_lock(&queue_lock, &local_qn);
        new_thread = TAILQ_FIRST(&ready_queue);
        if (new_thread) {
                TAILQ_REMOVE(&ready_queue, new_thread, next);
@@ -99,7 +101,7 @@ void pth_sched_entry(void)
                threads_active++;
                threads_ready--;
        }
-       mcs_lock_unlock(&queue_lock);
+       mcs_lock_unlock(&queue_lock, &local_qn);
        /* For now, this dumb logic is done here */
        if (!new_thread) {
                /* TODO: consider doing something more intelligent here */
@@ -148,12 +150,13 @@ struct uthread *pth_thread_create(void (*func)(void), void *udata)
 void pth_thread_runnable(struct uthread *uthread)
 {
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
+       struct mcs_lock_qnode local_qn = {0};
        /* 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_lock_lock(&queue_lock);
+       mcs_lock_lock(&queue_lock, &local_qn);
        TAILQ_INSERT_TAIL(&ready_queue, pthread, next);
        threads_ready++;
-       mcs_lock_unlock(&queue_lock);
+       mcs_lock_unlock(&queue_lock, &local_qn);
 }
 
 /* The calling thread is yielding.  Do what you need to do to restart (like put
@@ -162,15 +165,16 @@ void pth_thread_runnable(struct uthread *uthread)
 void pth_thread_yield(struct uthread *uthread)
 {
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
+       struct mcs_lock_qnode local_qn = {0};
        /* Take from the active list, and put on the ready list (tail).  Don't do
         * this until we are done completely with the thread, since it can be
         * restarted somewhere else. */
-       mcs_lock_lock(&queue_lock);
+       mcs_lock_lock(&queue_lock, &local_qn);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
        threads_ready++;
        TAILQ_INSERT_TAIL(&ready_queue, pthread, next);
-       mcs_lock_unlock(&queue_lock);
+       mcs_lock_unlock(&queue_lock, &local_qn);
 }
 
 /* Thread is exiting, do your 2LS specific stuff.  You're in vcore context.
@@ -178,11 +182,12 @@ void pth_thread_yield(struct uthread *uthread)
 void pth_thread_exit(struct uthread *uthread)
 {
        struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
+       struct mcs_lock_qnode local_qn = {0};
        /* Remove from the active runqueue */
-       mcs_lock_lock(&queue_lock);
+       mcs_lock_lock(&queue_lock, &local_qn);
        threads_active--;
        TAILQ_REMOVE(&active_queue, pthread, next);
-       mcs_lock_unlock(&queue_lock);
+       mcs_lock_unlock(&queue_lock, &local_qn);
        /* Cleanup, mirroring pth_thread_create() */
        __pthread_free_stack(pthread);
        /* TODO: race on detach state */