Fix dependency on vcoreid in barrier and cond var.
authorDavid Zhu <yuzhu@cs.berkeley.edu>
Sat, 1 May 2010 04:34:04 +0000 (21:34 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:46 +0000 (17:35 -0700)
Bthread used vcoreid to find the unique waiter, but that is incorrect in
pthread, since threads can yield and move to another vcore. For the barrier
and condition variable impelmentation, it only requires a unique waiter.
So we allocate that unique waiter from an array of them.

next slot is just an optimization to give us a better chance of finding
an empty slot quickly. So the race on that is benign.

user/include/pthread.h
user/parlib/pthread.c

index 18c09e7..e3bda01 100644 (file)
@@ -62,26 +62,38 @@ typedef struct
   int lock;
 } pthread_mutex_t;
 
-//TODO: MAX_PTHREADS is arbitrarily defined for now.
-#define MAX_PTHREADS 128
+/* TODO: MAX_PTHREADS is arbitrarily defined for now.
+ * It indicates the maximum number of threads that can wait on  
+   the same cond var/ barrier concurrently. */
+
+#define MAX_PTHREADS 32
 typedef struct
 {
   int local_sense[32*MAX_PTHREADS];
+  int in_use[MAX_PTHREADS];
   volatile int sense;
   int count;
   int nprocs;
+  int next_slot;
   pthread_mutex_t pmutex;
 } pthread_barrier_t;
 
+#define WAITER_CLEARED 0
+#define WAITER_WAITING 1
+#define SLOT_FREE 0
+#define SLOT_IN_USE 1
 typedef struct
 {
   int pshared;
 } pthread_condattr_t;
 
+
 typedef struct
 {
   const pthread_condattr_t* attr;
   int waiters[MAX_PTHREADS];
+  int in_use[MAX_PTHREADS];
+  int next_waiter; //start the search for an available waiter at this spot
 } pthread_cond_t;
 
 typedef int pthread_attr_t;
index e39dd86..6b0bbe8 100644 (file)
@@ -419,6 +419,8 @@ int pthread_cond_init(pthread_cond_t *c, const pthread_condattr_t *a)
 {
   c->attr = a;
   memset(c->waiters,0,sizeof(c->waiters));
+  memset(c->in_use,0,sizeof(c->in_use));
+  c->next_waiter = 0;
   return 0;
 }
 
@@ -436,7 +438,7 @@ int pthread_cond_broadcast(pthread_cond_t *c)
 int pthread_cond_signal(pthread_cond_t *c)
 {
   int i;
-  for(i = 0; i < max_vcores(); i++)
+  for(i = 0; i < MAX_PTHREADS; i++)
   {
     if(c->waiters[i])
     {
@@ -449,12 +451,23 @@ int pthread_cond_signal(pthread_cond_t *c)
 
 int pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m)
 {
-  c->waiters[vcore_id()] = 1;
+  int old_waiter = c->next_waiter;
+  int my_waiter = c->next_waiter;
+  
+  //allocate a slot
+  while (atomic_swap (& (c->in_use[my_waiter]), SLOT_IN_USE) == SLOT_IN_USE)
+  {
+    my_waiter = (my_waiter + 1) % MAX_PTHREADS;
+       assert (old_waiter != my_waiter);  // do not want to wrap around
+  }
+  c->waiters[my_waiter] = WAITER_WAITING;
+  c->next_waiter = (my_waiter+1) % MAX_PTHREADS;  // race on next_waiter but ok, because it is advisary
+
   pthread_mutex_unlock(m);
 
-  volatile int* poll = &c->waiters[vcore_id()];
+  volatile int* poll = &c->waiters[my_waiter];
   while(*poll);
-
+  c->in_use[my_waiter] = SLOT_FREE;
   pthread_mutex_lock(m);
 
   return 0;
@@ -563,6 +576,7 @@ int pthread_once(pthread_once_t* once_control, void (*init_routine)(void))
 int pthread_barrier_init(pthread_barrier_t* b, const pthread_barrierattr_t* a, int count)
 {
   memset(b->local_sense,0,sizeof(b->local_sense));
+  memset(b->in_use,0,sizeof(b->in_use));
 
   b->sense = 0;
   b->nprocs = b->count = count;
@@ -573,9 +587,17 @@ int pthread_barrier_init(pthread_barrier_t* b, const pthread_barrierattr_t* a, i
 int pthread_barrier_wait(pthread_barrier_t* b)
 {
   unsigned int spinner = 0;
-  struct pthread_tcb *t = pthread_self();
+  int id = b->next_slot;
+  int old_id = b->next_slot;
 
-  int id = t->id;
+  //allocate a slot
+
+  while (atomic_swap (& (b->in_use[id]), SLOT_IN_USE) == SLOT_IN_USE)
+  {
+    id = (id + 1) % MAX_PTHREADS;
+       assert (old_id != id);  // do not want to wrap around
+  }
+  b->next_slot = (id + 1) % MAX_PTHREADS;
   int ls = b->local_sense[32*id] = 1 - b->local_sense[32*id];
 
   pthread_mutex_lock(&b->pmutex);