Subj : trying to understand simultaneous wakeup of all threads on pthreads_cond_broadcast()
To   : comp.programming.threads
From : el_bandido
Date : Tue Feb 01 2005 12:01 am

Hello,

I'm reading through linuxthreads and NPTL source code in glibc and I've 
got some difficulties understanding how the simultaneous wakeup of 
waiting threads works in linuxthreads. I'd like to post what I think is 
the relevant piece of code:

int __pthread_cond_broadcast(pthread_cond_t *cond)
{
   pthread_descr tosignal, th;

   __pthread_lock(&cond->__c_lock, NULL);
   /* Copy the current state of the waiting queue and empty it */
   tosignal = cond->__c_waiting;
   cond->__c_waiting = NULL;
   __pthread_unlock(&cond->__c_lock);
   /* Now signal each process in the queue */
   while ((th = dequeue(&tosignal)) != NULL) {
     th->p_condvar_avail = 1;
     WRITE_MEMORY_BARRIER();
     restart(th);
   }
   return 0;
}

static inline pthread_descr dequeue(pthread_descr * q)
{
   pthread_descr th;
   th = *q;
   if (th != NULL) {
     *q = th->p_nextwaiting;
     th->p_nextwaiting = NULL;
   }
   return th;
}

struct _pthread_descr_struct
{
[...]
   pthread_descr p_nextlive, p_prevlive;
                                 /* Double chaining of active threads */
   pthread_descr p_nextwaiting;  /* Next element in the queue holding 
the thr */
   pthread_descr p_nextlock;     /* can be on a queue and waiting on a 
lock */
   pthread_t p_tid;              /* Thread identifier */
   int p_pid;                    /* PID of Unix process */
   int p_priority;               /* Thread priority (== 0 if not 
realtime) */
   struct _pthread_fastlock * p_lock; /* Spinlock for synchronized 
accesses */
   int p_signal;                 /* last signal received */
[...]
}

Somehow it will wake up all waiting threads, however from what I can 
understand only the first waiting thread in the queue will get the lock. 
If we look at the NTPL version it looks rather different and also highly 
more confusing:

int
__pthread_cond_broadcast (cond)
      pthread_cond_t *cond;
{
   /* Make sure we are alone.  */
   lll_mutex_lock (cond->__data.__lock);

   /* Are there any waiters to be woken?  */
   if (cond->__data.__total_seq > cond->__data.__wakeup_seq)
     {
       /* Yes.  Mark them all as woken.  */
       cond->__data.__wakeup_seq = cond->__data.__total_seq;
       cond->__data.__woken_seq = cond->__data.__total_seq;
       cond->__data.__futex = (unsigned int) cond->__data.__total_seq * 2;
       int futex_val = cond->__data.__futex;
       /* Signal that a broadcast happened.  */
       ++cond->__data.__broadcast_seq;

       /* We are done.  */
       lll_mutex_unlock (cond->__data.__lock);

       /* Do not use requeue for pshared condvars.  */
       if (cond->__data.__mutex == (void *) ~0l)
         goto wake_all;

       /* Wake everybody.  */
       pthread_mutex_t *mut = (pthread_mutex_t *) cond->__data.__mutex;
       /* lll_futex_requeue returns 0 for success and non-zero
          for errors.  */
       if (__builtin_expect (lll_futex_requeue (&cond->__data.__futex, 1,
                                                INT_MAX, 
&mut->__data.__lock,
                                                futex_val), 0))
         {
           /* The requeue functionality is not available.  */
         wake_all:
           lll_futex_wake (&cond->__data.__futex, INT_MAX);
         }

       /* That's all.  */
       return 0;
     }

   /* We are done.  */
   lll_mutex_unlock (cond->__data.__lock);

   return 0;
}

And for i386 lll_futex_wake() of course is:

#define lll_futex_wake(futex, nr) \
   do {        \
     int __ignore;        \
     register __typeof (nr) _nr asm ("edx") = (nr);        \
     __asm __volatile (LLL_EBX_LOAD        \
                       LLL_ENTER_KERNEL        \
                       LLL_EBX_LOAD        \
                       : "=a" (__ignore)        \
                       : "0" (SYS_futex), LLL_EBX_REG (futex),        \
                         "c" (FUTEX_WAKE), "d" (_nr),        \
                         "i" (0) /* phony, to align next arg's number 
*/,      \
                         "i" (offsetof (tcbhead_t, sysinfo)));        \
   } while (0)

So how does the linuxthreads implementation guarantee randomness in the 
waiting thread selection? Or does POSIX not require randomness for 
pthreads_cond_broadcast()?

Cheers,
Roberto Nibali, ratz
-- 
echo 
'[q]sa[ln0=aln256%Pln256/snlbx]sb3135071790101768542287578439snlbxq' | dc

.