Date: Fri, 17 Oct 2008 16:40:59 GMT From: Kurt Miller <kurt@intricatesoftware.com> To: freebsd-gnats-submit@FreeBSD.org Subject: threads/128180: pthread_cond_broadcast() lost wakup Message-ID: <200810171640.m9HGexJ1090893@www.freebsd.org> Resent-Message-ID: <200810171650.m9HGo2ao024160@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>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@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:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200810171640.m9HGexJ1090893>