[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Barriers hanging



Hello again,

Since I didn't received any answer to my previous post about hang with
barriers
(http://listman.redhat.com/archives/phil-list/2004-February/msg00059.html),
I kept on searching and below are my findings.

NPTL barriers have a weakness in the pthread_barrier_wait() and
pthread_barrier_destroy() functions.

In NPTL, when you call pthread_barrier_destroy(), this
routine may succeed while some threads have not yet returned from
the pthread_barrier_wait() routine.

This entails, when resuming pthread_barrier_wait(),
that the CURR_EVENT value of the barrier will be read from freed
memory, which can be garbage, resulting in a possible hang for
the thread.


The file maxcrea.c attached to this email demonstrates this hang.
The hang does not appear with maxcrea.c and LinuxThreads on my mono-CPU
PC.

I tried to fix this bug by myself. My proposal is attached in the patch.

This is incomplete since I only worked for i486 arch.
Basically, the patch is based on adding a field in the barrier struct
saying 'busy'. The major drawback of this patch is that it slows things
a little (price for reliability ??) - my testings show #50% overtime for
(pthread_barrier_wait in thousand threads, pthread_barrier_destroy,
pthread_barrier_init) sequence. This is anyway far better than
linuxthreads (# 30x slower).

Please tell me if it is worth keeping on working for other archs? 

Best regards,


-- 
Sébastien DECUGIS
Bull S.A.
/* **************************************************************************************
 *  maxcrea.c
 * 
 * This little sample is designed to test the maximal number of posix threads 
 * that can be created (and kept running) inside a single process, with various
 * parameters. Barriers are also used to synchronize the threads.
 * 
 * ***************************************************************************************/


 #include <errno.h>

 #define __USE_XOPEN2K
 #include <pthread.h>
 #include <features.h>
 #include <stdarg.h>
 #include <stdlib.h>
 #include <unistd.h>
 #include <stdio.h>
 
/********* Configuration ************/
/* #define DEFAULT_MAXTHREADS	(65536) */
 #define DEFAULT_MAXTHREADS	(1024)
 #define DEFAULT_STACKSIZE			(16 * 4096)
/* #define DEFAULT_STACKSIZE			(1024 * 16 * 4096) */
 
/*#define WITH_MAIN_SLEEPS */
/*#define WITH_YIELD */
/*#define DEBOG */
#define WITH_TIMEINFO
#define VERBOSE

/******** End of conf **************/

#ifdef WITH_MAIN_SLEEPS
#define SLEEPTIME    (10000+500*N)
#else
#define SLEEPTIME    0
#endif
#ifdef WITH_TIMEINFO
 #include <sys/time.h>
#endif




 
 typedef enum {ORDER_GO_ON, ORDER_EXIT} order_t;
 
 order_t	control;
 pthread_barrier_t b1, b2;
 pthread_mutex_t m_trace;
 
 
 /********************************* Trace facility *****************************************/
#ifdef DEBOG
 #define MYDEBUG printf("L%03i : ", __LINE__); trace
#else
 #define MYDEBUG notrace
 void notrace( char * format, ...)
 {
    return;
 }
#endif
void trace( char * format, ... )
{
   va_list ap;
/*   int len;
   char * buffer;
*/
   
   pthread_mutex_lock(&m_trace);
   va_start( ap, format );
/*   len = _vscprintf( format, args ) // _vscprintf doesn't count
                                              + 1; // terminating '\0'
   buffer = malloc( len * sizeof(char) );
   vsprintf( buffer, format, args );
   printf( buffer );
   free( buffer );
*/
   vprintf(format, ap);
   va_end(ap);
   pthread_mutex_unlock(&m_trace);
   
}
 /********************************* threads code *******************************************/
  
 void * threaded(void * arg)
 {
 	int rc;
	MYDEBUG ("Thread %lu starting\n", (unsigned long) arg );
 	while (1)
 	{
 	/* Wait for barrier b1 */
		MYDEBUG ("thread %lu  waiting for b1\n", (unsigned long) arg );
 		rc = pthread_barrier_wait(&b1);
		MYDEBUG ("thread %lu  got b1 (rc = %i)\n", (unsigned long) arg , rc);
 		
 	/* wait for barrier b2 */
		MYDEBUG ("thread %lu waiting for b2\n", (unsigned long) arg );
 		rc = pthread_barrier_wait(&b2);
		MYDEBUG ("thread %lu got b2 (rc = %i)\n", (unsigned long) arg , rc);
 		
 	/* read control value */
 		if (control == ORDER_EXIT)
 	/* if control says 'exit' then exit */
 		{
			MYDEBUG ("thread %lu  exiting\n", (unsigned long) arg );
 			return NULL;
 		}
 			
 	/* loop */
 	}
 }

/**************************** MAIN ********************************/
 int main (int argc, char * argv[])
 {
 	/* N = # of thread created so far */
 	unsigned long N=0;
 	pthread_attr_t  thr_attr;
 	pthread_t * threads;
 	int rc=0;
 	
#ifdef WITH_TIMEINFO
 	struct timeval  time_ref, time_cour, time_diff, time_comp, time_wait, time_prec, time_real;
	struct timezone tz;
#endif
	
    char name[128];

 	unsigned long nbmaxthreads = DEFAULT_MAXTHREADS;
 	int stacksize = DEFAULT_STACKSIZE;
 	
 	if (sizeof (unsigned long) != sizeof (void *))
 	{
 		printf("Warning threads # may be corrupted...\n");	
 	}
         
    confstr(_CS_GNU_LIBPTHREAD_VERSION, name, sizeof(name));
 	
#ifdef WITH_TIMEINFO
 	gettimeofday(&time_ref, &tz);
 	gettimeofday(&time_prec, &tz);
 	printf("N; total time; difference; real time\n");
#endif 
 	
	pthread_mutex_init(&m_trace, NULL);

 	control = ORDER_GO_ON;
 	
#ifdef VERBOSE
 	trace ("MaxCrea by Sebastien Decugis: Starting...\n");
    trace ("Pthreads lib: %s\n", name);
#endif

 	/* add parameters parsing here to overwrite nbmaxthreads or stacksize... */
 	
 	/* initialization of pthread_attributes (loop on attributes -> joinable/detached, ...?) */
 	if (rc= pthread_attr_init(&thr_attr))
 	{
 		trace("ERROR(%i): pthread_attr_init returned %d; exiting...\n", __LINE__, rc);
 		return 1;
 	}
 	MYDEBUG ("pthread_attr_init OK\n");
 	
 	if (rc= pthread_attr_setstacksize(&thr_attr, stacksize))
 	{
 		trace("ERROR(%i): pthread_attr_setstacksize(%i) returned %d; exiting...\n",__LINE__,stacksize, rc);
 		pthread_attr_destroy(&thr_attr);
 		return 1;
 	}
 	MYDEBUG ("pthread_attr_setstacksize OK\n");
 	
 	/* initialize thread table */
 	threads = (pthread_t *) malloc(nbmaxthreads * sizeof(pthread_t));
 	if (threads==(pthread_t *)NULL)
 	{
 		trace("ERROR(%i): could not allocate memory for threads handlers, exiting...\n",__LINE__);
 		pthread_attr_destroy(&thr_attr);
 		return 1;
 	}
 	MYDEBUG ("malloc OK\n");
 	
	/* Initialize barrier b2 with value 1 */
  	if (rc= pthread_barrier_init(&b2, NULL, 1 ))
 	{
 		trace("ERROR(%i): pthread_barrier_init (b2, 1) returned %d; exiting...\n",__LINE__, rc);
 		pthread_attr_destroy(&thr_attr);
 		free(threads);
 		return 1;
 	}
 	MYDEBUG ("pthread_barrier_init (b2, 1) OK\n");

    /* Loop */
    while(1)
    {
 	/* |  Initialize barrier b1 with value N+2 */
	  	if (rc= pthread_barrier_init(&b1, NULL, N + 2 ))
	 	{
	 		trace("ERROR(%i): pthread_barrier_init (b1, %d) returned %d; cannot continue...\n",__LINE__, N+2, rc);
	 		break;
	 	}
	 	MYDEBUG ("pthread_barrier_init (b1, %i) OK\n", N+2);
	/* |  if N >= maxthreads => exit */
		if (N >= nbmaxthreads)
		{
			trace("%i threads were created successfully\n", N);
			break;
		}
 	/* |  create new thread */
	  	if (rc= pthread_create(&threads[N], &thr_attr, &threaded, (void *)N))
 	/* |  if thread creation is NOK */
	 	{
 	/* |  | exit loop */
	 		trace("ERROR(%i): the thread #%i could not be created (%i)...\n",__LINE__, N+1, rc);
	 		break;
 	/* |  end if (creation is OK, new thread is waiting on b1) */
	 	}
	 	MYDEBUG ("pthread_create (%i) OK\n", N);
	 	MYDEBUG ("N = %i\n", N);

#ifdef WITH_TIMEINFO
		gettimeofday(&time_cour, &tz);
		timersub(&time_cour, &time_ref, &time_diff);
		
		timersub(&time_cour, &time_prec, &time_comp);
		
		time_wait.tv_sec =  (2 * SLEEPTIME ) / 1000000;
		time_wait.tv_usec =  (2 * SLEEPTIME ) % 1000000;
		
		timersub(&time_comp, &time_wait, &time_real);

		time_prec.tv_sec = time_cour.tv_sec;
		time_prec.tv_usec = time_cour.tv_usec;
		
		printf("%4i; %4i.%06i; %4i.%06i; %4i.%06i \n"
							, N
							, time_diff.tv_sec, time_diff.tv_usec
							, time_comp.tv_sec, time_comp.tv_usec
							, time_real.tv_sec, time_real.tv_usec
							);
		fflush(stdout);
#else
		printf("N = %i\n", N);
#endif 

 	/* |  N = N + 1 */
 		N++;

 	/* |  wait for barrier b2 (then all threads will be waiting on b1) */
 		if ((rc=pthread_barrier_wait(&b2)) && (rc != PTHREAD_BARRIER_SERIAL_THREAD))
 		{
 			trace("ERROR(%i): waiting for barrier b2 (%i)\n",__LINE__, rc);
 			break;
 		}
	 	MYDEBUG ("pthread_barrier_wait(b2) OK\n", N);

#ifdef WITH_MAIN_SLEEPS
	 	MYDEBUG ("Main sleep for %i µsec...\n", SLEEPTIME);
		usleep(SLEEPTIME);
#endif

#ifdef WITH_YIELD
		if (rc = pthread_yield())
		{
			trace("ERROR pthread_yield returned %i\n", rc);
		}
#endif
		

 	/* |  destroy barrier b2 */
	  	if (rc= pthread_barrier_destroy(&b2))
	 	{
	 		trace("ERROR(%i): pthread_barrier_destroy (b2) returned %d\n You will probably lose some resources\n",__LINE__, rc);
	 		break;
	 	}
	 	MYDEBUG ("pthread_barrier_destroy(b2) OK\n", N);
 	
 	/* |  initialize barrier b2 with value N+1 */
	  	if (rc= pthread_barrier_init(&b2, NULL, N + 1 ))
	 	{
	 		trace("ERROR(%i): pthread_barrier_init (b2, %i) returned %d\n You will probably lose some resources\n",__LINE__, N+1, rc);
	 		break;
	 	}
	 	MYDEBUG ("pthread_barrier_init(b2, %i) OK\n", N+1);

 	/* |  wait for barrier b1 (all threads read control then wait for b2) */
 		if ((rc=pthread_barrier_wait(&b1)) && (rc != PTHREAD_BARRIER_SERIAL_THREAD))
 		{
 			trace("ERROR(%i): waiting for barrier b1 (%i)\n",__LINE__, rc);
 			break;
 		}
	 	MYDEBUG ("pthread_barrier_wait(b1) OK\n", N);

#ifdef WITH_MAIN_SLEEPS
	 	MYDEBUG ("Main sleep for %i µsec...\n", SLEEPTIME);
		usleep(SLEEPTIME);
#endif
#ifdef WITH_YIELD
		if (rc = pthread_yield())
		{
			trace("ERROR pthread_yield returned %i\n", rc);
		}
#endif
		
 	/* |  destroy barrier b1 */
	  	if (rc= pthread_barrier_destroy(&b1))
	 	{
	 		trace("ERROR(%i): pthread_barrier_destroy (b1) returned %d\n You will probably lose some resources\n",__LINE__, rc);
	 		break;
	 	}
	 	MYDEBUG ("pthread_barrier_destroy(b1) OK\n", N);

 	/* end loop */
    }

 	/* set control = 'exit' */
 	control = ORDER_EXIT;
 	MYDEBUG ("control = EXIT\n", N);

 	/* wait for barrier b1 (all threads should read control and exit now)*/
	if ((rc=pthread_barrier_wait(&b2)) && (rc != PTHREAD_BARRIER_SERIAL_THREAD))
	{
		trace("ERROR(%i): waiting for barrier b2 (%i)\n",__LINE__, rc);
	}
 	MYDEBUG ("pthread_barrier_wait(b2) OK/NOK\n", N);
 	
 	
 	/* if threads were joinable, join them. */
 	while (N>0)
 	{
	 	--N;
 		if (rc = pthread_join(threads[N], NULL))
 		{
 			trace("Failed to join thread #%i (%i)\n", N, rc);
 		}
	 	MYDEBUG ("pthread_join(%i) OK/NOK\n", N);
	}

	pthread_attr_destroy(&thr_attr);
	free(threads);

#ifdef VERBOSE
	trace ("MaxCrea: See U Space Cowboy...\n", N+1);
#endif
	
	pthread_mutex_destroy(&m_trace);
	
	return 0;
 	
 }
diff -Nur libc/nptl/ChangeLog libcnew/nptl/ChangeLog
--- libc/nptl/ChangeLog	2004-02-13 18:03:54.000000000 +0100
+++ libcnew/nptl/ChangeLog	2004-02-13 18:00:10.000000000 +0100
@@ -1,3 +1,17 @@
+2004-02-13  Sebastien Decugis <sebastien decugis bull net>
+
+	* pthread_barrier_init.c: Added busy initialization.
+
+	* pthread_barrier_destroy.c: loop while busy. busy is true
+	as long as there are waiters testing for curr_event value...
+
+	* sysdeps/unix/sysv/linux/i386/i486/pthread_barrier_wait.S:
+	Added busy increment and decrement.
+
+	* sysdeps/unix/sysv/linux/internaltypes.h: busy field declaration.
+
+	* sysdeps/unix/sysv/linux/lowlevelbarrier.sym: added BUSY.
+
 2004-02-13  Ulrich Drepper  <drepper redhat com>
 
 	* sysdeps/pthread/pthread_cond_timedwait.c
diff -Nur libc/nptl/pthread_barrier_destroy.c libcnew/nptl/pthread_barrier_destroy.c
--- libc/nptl/pthread_barrier_destroy.c	2004-02-13 18:03:54.000000000 +0100
+++ libcnew/nptl/pthread_barrier_destroy.c	2004-02-16 10:12:12.209430792 +0100
@@ -27,18 +27,34 @@
      pthread_barrier_t *barrier;
 {
   struct pthread_barrier *ibarrier;
-  int result = EBUSY;
+  int result = -1;
 
   ibarrier = (struct pthread_barrier *) barrier;
 
+ while (result == -1)
+ {
   lll_lock (ibarrier->lock);
 
   if (__builtin_expect (ibarrier->left == ibarrier->init_count, 1))
+  {
     /* The barrier is not used anymore.  */
-    result = 0;
+    if (ibarrier->busy)
+    {
+        lll_unlock (ibarrier->lock);
+        pthread_yield();
+    }
+    else
+    {
+        result = 0;
+    }
+  }
   else
+  {
     /* Still used, return with an error.  */
     lll_unlock (ibarrier->lock);
-
+    result = EBUSY;
+  }
+ }
   return result;
 }
+
diff -Nur libc/nptl/pthread_barrier_init.c libcnew/nptl/pthread_barrier_init.c
--- libc/nptl/pthread_barrier_init.c	2004-02-13 18:03:54.000000000 +0100
+++ libcnew/nptl/pthread_barrier_init.c	2004-02-13 17:54:51.000000000 +0100
@@ -52,6 +52,7 @@
   ibarrier->left = count;
   ibarrier->init_count = count;
   ibarrier->curr_event = 0;
+  ibarrier->busy = 0;
 
   return 0;
 }
diff -Nur libc/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_barrier_wait.S libcnew/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_barrier_wait.S
--- libc/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_barrier_wait.S	2004-02-13 18:04:20.000000000 +0100
+++ libcnew/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_barrier_wait.S	2004-02-13 17:47:31.000000000 +0100
@@ -50,7 +50,12 @@
 
 	/* One less waiter.  If this was the last one needed wake
 	   everybody.  */
-2:	subl	$1, LEFT(%ebx)
+#if BUSY == 0
+2:	addl	$1, (%ebx)
+#else
+2:	addl	$1, BUSY(%ebx)
+#endif
+	subl	$1, LEFT(%ebx)
 	je	3f
 
 	/* There are more threads to come.  */
@@ -84,6 +89,29 @@
 #endif
 	je,pn	8b
 
+	/* acquire the lock before changing BUSY */
+	/* save %edx */
+	pushl	%edx
+	/* get the mutex */
+	movl	$1, %edx
+	xorl	%eax, %eax
+	LOCK
+	cmpxchgl %edx, MUTEX(%ebx)
+	jnz	9f
+	/* now we have the lock, decrease busy */
+#if BUSY == 0
+10:	subl	$1, (%ebx)
+#else
+10:	subl	$1, BUSY(%ebx)
+#endif
+	/* and finally unlock */
+	LOCK
+	subl	$1, MUTEX(%ebx)
+	jne	11f
+	/* then restore %edx */
+12:	popl	%edx
+	/* and go on exiting */
+
 	/* Note: %esi is still zero.  */
 	movl	%esi, %eax		/* != PTHREAD_BARRIER_SERIAL_THREAD */
 
@@ -110,6 +138,12 @@
 	/* Release the mutex.  We cannot release the lock before
 	   waking the waiting threads since otherwise a new thread might
 	   arrive and gets waken up, too.  */
+#if BUSY == 0
+	subl	$1, (%ebx)
+#else
+	subl	$1, BUSY(%ebx)
+#endif
+
 	LOCK
 	subl	$1, MUTEX(%ebx)
 	jne	4f
@@ -123,10 +157,18 @@
 	call	__lll_mutex_lock_wait
 	jmp	2b
 
+9:	leal	 MUTEX(%ebx), %ecx
+        call    __lll_mutex_lock_wait
+        jmp     10b
+
 4:	leal	MUTEX(%ebx), %eax
 	call	__lll_mutex_unlock_wake
 	jmp	5b
 
+11:     leal    MUTEX(%ebx), %eax
+        call    __lll_mutex_unlock_wake
+        jmp     12b
+
 6:	leal	MUTEX(%ebx), %eax
 	call	__lll_mutex_unlock_wake
 	jmp	7b
diff -Nur libc/nptl/sysdeps/unix/sysv/linux/internaltypes.h libcnew/nptl/sysdeps/unix/sysv/linux/internaltypes.h
--- libc/nptl/sysdeps/unix/sysv/linux/internaltypes.h	2004-02-13 18:06:03.000000000 +0100
+++ libcnew/nptl/sysdeps/unix/sysv/linux/internaltypes.h	2004-02-13 15:55:05.000000000 +0100
@@ -91,6 +91,7 @@
   int lock;
   unsigned int left;
   unsigned int init_count;
+  unsigned int busy;
 };
 
 
diff -Nur libc/nptl/sysdeps/unix/sysv/linux/lowlevelbarrier.sym libcnew/nptl/sysdeps/unix/sysv/linux/lowlevelbarrier.sym
--- libc/nptl/sysdeps/unix/sysv/linux/lowlevelbarrier.sym	2004-02-13 18:06:03.000000000 +0100
+++ libcnew/nptl/sysdeps/unix/sysv/linux/lowlevelbarrier.sym	2004-02-13 16:09:46.000000000 +0100
@@ -9,3 +9,4 @@
 MUTEX			offsetof (struct pthread_barrier, lock)
 LEFT			offsetof (struct pthread_barrier, left)
 INIT_COUNT		offsetof (struct pthread_barrier, init_count)
+BUSY			offsetof (struct pthread_barrier, busy)

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]