threads/128180: pthread_cond_broadcast() lost wakup

Kurt Miller kurt at intricatesoftware.com
Fri Oct 17 16:50:02 UTC 2008


>Number:         128180
>Category:       threads
>Synopsis:       pthread_cond_broadcast() lost wakup
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    freebsd-threads
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          sw-bug
>Submitter-Id:   current-users
>Arrival-Date:   Fri Oct 17 16:50:01 UTC 2008
>Closed-Date:
>Last-Modified:
>Originator:     Kurt Miller
>Release:        6.3-RELEASE
>Organization:
Intricate Software
>Environment:
FreeBSD fbsd-amd64-63.intricatesoftware.com 6.3-RELEASE FreeBSD 6.3-RELEASE #0: Wed Jan 16 01:43:02 UTC 2008     root at palmer.cse.buffalo.edu:/usr/obj/usr/src/sys/SMP  amd64
>Description:
I've been investigating a deadlock in the jvm that occurs with
the concurrent mark sweep garbage collector. The cause appears
to be due to the kernel failing to wake up all threads waiting
on a condition variable.

I have written a test program that mimics the jvm's underlying
pattern. It reproduces the deadlock quickly and exhibits the
same problem. The general idea is that one thread sends a broadcast
to a group of worker threads. The worker threads perform some tasks,
coordinate their completion and broadcast on the same condition
variable they are done. The design is a bit heavy on the use of
the one condition variable, however it does appear to be valid if
not ideal.

The deadlock occurs with the following system setup:

  6.3-RELEASE SMP amd64 kernel
  libthr
  2 or more cores

I have not yet checked other releases or setups.

The test program outputs periodic printf's indicating
progress is being made. When it stops the process is
deadlocked. The lost wakeup can be confirmed by inspecting
the saved_waiters local var in main(). Each time the
deadlock occurs I see that saved_waiters is 8 which tells
me all eight worker threads were waiting on the condition
variable when the broadcast was sent. Then switch to the
thread that is still waiting on the condition variable,
and you can see that the last_cycle local var is one behind
the cycles global var which indicates it didn't receive the
last wakeup.

>How-To-Repeat:
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

pthread_mutex_t group_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  group_cond_var = PTHREAD_COND_INITIALIZER;

volatile int tickets;
volatile int waiters;
volatile int finished;

int term_count;

volatile unsigned long cycles;

void *thread_main(void * thread_num);

#define NTHREADS 8
#define NYIELDS 1000

inline void atomicinc(volatile int* val) {
  __asm__ __volatile__ ("lock addl $1,(%0)" : : "r" (val) : "cc", "memory");
}

int
main( int argc, char *argv[] )
{
    long t_num;
    pthread_t tid[NTHREADS];
    volatile int saved_waiters;

    /* startup threads */
    for (t_num=0; t_num < NTHREADS; t_num++) {
        pthread_create( &tid[t_num], NULL, thread_main, (void *)t_num );
    }

    for(;;) {
        /* monitor progress on stdout */
        if (cycles % 5000 == 0)
                printf("cycles %lu\n", cycles);

        /* broadcast to workers to work */
        pthread_mutex_lock(&group_mutex);
        cycles++;
        term_count = 0;
        finished = 0;
        tickets=NTHREADS;
        saved_waiters = waiters;
        pthread_cond_broadcast(&group_cond_var);
        pthread_mutex_unlock(&group_mutex);

        /* wait for workers to finish */
        pthread_mutex_lock(&group_mutex);
        while (finished != NTHREADS)
           pthread_cond_wait(&group_cond_var, &group_mutex);
        pthread_mutex_unlock(&group_mutex);
    }
    return 0;
}

void *
thread_main(void *thread_num)
{
    unsigned long yield_count=0;
    unsigned long sleep_count=0;
    u_int32_t i, busy_loop = arc4random() & 0x7FFF;
    u_int32_t dummy = busy_loop;
    pthread_cond_t sleep_cond_var;
    pthread_mutex_t sleep_mutex;
    struct timeval tmptime;
    struct timeval delay = {0, 1};
    struct timespec waketime;
    volatile unsigned long last_cycle;

    pthread_mutex_init(&sleep_mutex, NULL);
    pthread_cond_init(&sleep_cond_var, NULL);

    for (;;) {
        pthread_mutex_lock(&group_mutex);

        waiters++;

        while (tickets == 0)
           pthread_cond_wait(&group_cond_var, &group_mutex);

        waiters--;
        tickets--;
        last_cycle = cycles;

        pthread_mutex_unlock(&group_mutex);

        /* do something busy */
        for (i = 0; i < busy_loop; i++)
                dummy *= i;

        /* sync termination */
        atomicinc(&term_count);

        for(;;) {
            if (term_count == NTHREADS)
                break;

            if (yield_count < NYIELDS) {
                yield_count++;
                sched_yield();
            } else {
                yield_count = 0;
                sleep_count++;
                // 1.6 uses pthread_cond_timedwait for sleeping
                gettimeofday(&tmptime, NULL);
                timeradd(&tmptime, &delay, &tmptime);
                waketime.tv_sec = tmptime.tv_sec;
                waketime.tv_nsec = tmptime.tv_usec * 1000;
                pthread_mutex_lock(&sleep_mutex);
                pthread_cond_timedwait(&sleep_cond_var, &sleep_mutex, &waketime);
                pthread_mutex_unlock(&sleep_mutex);
            }
        }

        /* ok all terminated now let everyone know */
        pthread_mutex_lock(&group_mutex);
        finished++;
        pthread_cond_broadcast(&group_cond_var);
        pthread_mutex_unlock(&group_mutex);
    }
    return NULL;
}

>Fix:


>Release-Note:
>Audit-Trail:
>Unformatted:


More information about the freebsd-threads mailing list