Barriers hanging
Sebastien Decugis <[email protected]> Mon, 16 Feb 2004 16:19:46 +0100
| Newsgroups | gmane.comp.lib.phil |
|---|---|
| Message-ID | <[email protected]> |
--=-aaO4lgknU5HvnxozYaDo
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
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?=20
Best regards,
--=20
S=E9bastien DECUGIS
Bull S.A.
--=-aaO4lgknU5HvnxozYaDo
Content-Disposition: attachment; filename=maxcrea.c
Content-Type: text/x-c; name=maxcrea.c; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-MIME-Autoconverted: from 8bit to quoted-printable by ecbull20.frec.bull.fr id QAA16686
/* **********************************************************************=
****************
* maxcrea.c
*=20
* This little sample is designed to test the maximal number of posix thr=
eads=20
* that can be created (and kept running) inside a single process, with v=
arious
* parameters. Barriers are also used to synchronize the threads.
*=20
* **********************************************************************=
*****************/
#include <errno.h>
#define __USE_XOPEN2K
#include <pthread.h>
#include <features.h>
#include <stdarg.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
=20
/********* Configuration ************/
/* #define DEFAULT_MAXTHREADS (65536) */
#define DEFAULT_MAXTHREADS (1024)
#define DEFAULT_STACKSIZE (16 * 4096)
/* #define DEFAULT_STACKSIZE (1024 * 16 * 4096) */
=20
/*#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
=20
typedef enum {ORDER_GO_ON, ORDER_EXIT} order_t;
=20
order_t control;
pthread_barrier_t b1, b2;
pthread_mutex_t m_trace;
=20
=20
/********************************* 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;
*/
=20
pthread_mutex_lock(&m_trace);
va_start( ap, format );
/* len =3D _vscprintf( format, args ) // _vscprintf doesn't count
+ 1; // terminating '\0'
buffer =3D malloc( len * sizeof(char) );
vsprintf( buffer, format, args );
printf( buffer );
free( buffer );
*/
vprintf(format, ap);
va_end(ap);
pthread_mutex_unlock(&m_trace);
=20
}
/********************************* threads code ************************=
*******************/
=20
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 =3D pthread_barrier_wait(&b1);
MYDEBUG ("thread %lu got b1 (rc =3D %i)\n", (unsigned long) arg , rc);
=09
/* wait for barrier b2 */
MYDEBUG ("thread %lu waiting for b2\n", (unsigned long) arg );
rc =3D pthread_barrier_wait(&b2);
MYDEBUG ("thread %lu got b2 (rc =3D %i)\n", (unsigned long) arg , rc);
=09
/* read control value */
if (control =3D=3D ORDER_EXIT)
/* if control says 'exit' then exit */
{
MYDEBUG ("thread %lu exiting\n", (unsigned long) arg );
return NULL;
}
=09
/* loop */
}
}
/**************************** MAIN ********************************/
int main (int argc, char * argv[])
{
/* N =3D # of thread created so far */
unsigned long N=3D0;
pthread_attr_t thr_attr;
pthread_t * threads;
int rc=3D0;
=09
#ifdef WITH_TIMEINFO
struct timeval time_ref, time_cour, time_diff, time_comp, time_wait, t=
ime_prec, time_real;
struct timezone tz;
#endif
=09
char name[128];
unsigned long nbmaxthreads =3D DEFAULT_MAXTHREADS;
int stacksize =3D DEFAULT_STACKSIZE;
=09
if (sizeof (unsigned long) !=3D sizeof (void *))
{
printf("Warning threads # may be corrupted...\n");=09
}
=20
confstr(_CS_GNU_LIBPTHREAD_VERSION, name, sizeof(name));
=09
#ifdef WITH_TIMEINFO
gettimeofday(&time_ref, &tz);
gettimeofday(&time_prec, &tz);
printf("N; total time; difference; real time\n");
#endif=20
=09
pthread_mutex_init(&m_trace, NULL);
control =3D ORDER_GO_ON;
=09
#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..=
. */
=09
/* initialization of pthread_attributes (loop on attributes -> joinable=
/detached, ...?) */
if (rc=3D 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");
=09
if (rc=3D 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");
=09
/* initialize thread table */
threads =3D (pthread_t *) malloc(nbmaxthreads * sizeof(pthread_t));
if (threads=3D=3D(pthread_t *)NULL)
{
trace("ERROR(%i): could not allocate memory for threads handlers, exit=
ing...\n",__LINE__);
pthread_attr_destroy(&thr_attr);
return 1;
}
MYDEBUG ("malloc OK\n");
=09
/* Initialize barrier b2 with value 1 */
if (rc=3D 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=3D pthread_barrier_init(&b1, NULL, N + 2 ))
{
trace("ERROR(%i): pthread_barrier_init (b1, %d) returned %d; cannot c=
ontinue...\n",__LINE__, N+2, rc);
break;
}
MYDEBUG ("pthread_barrier_init (b1, %i) OK\n", N+2);
/* | if N >=3D maxthreads =3D> exit */
if (N >=3D nbmaxthreads)
{
trace("%i threads were created successfully\n", N);
break;
}
/* | create new thread */
if (rc=3D 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",__LI=
NE__, N+1, rc);
break;
/* | end if (creation is OK, new thread is waiting on b1) */
}
MYDEBUG ("pthread_create (%i) OK\n", N);
MYDEBUG ("N =3D %i\n", N);
#ifdef WITH_TIMEINFO
gettimeofday(&time_cour, &tz);
timersub(&time_cour, &time_ref, &time_diff);
=09
timersub(&time_cour, &time_prec, &time_comp);
=09
time_wait.tv_sec =3D (2 * SLEEPTIME ) / 1000000;
time_wait.tv_usec =3D (2 * SLEEPTIME ) % 1000000;
=09
timersub(&time_comp, &time_wait, &time_real);
time_prec.tv_sec =3D time_cour.tv_sec;
time_prec.tv_usec =3D time_cour.tv_usec;
=09
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 =3D %i\n", N);
#endif=20
/* | N =3D N + 1 */
N++;
/* | wait for barrier b2 (then all threads will be waiting on b1) */
if ((rc=3Dpthread_barrier_wait(&b2)) && (rc !=3D PTHREAD_BARRIER_SERIA=
L_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 =C2=B5sec...\n", SLEEPTIME);
usleep(SLEEPTIME);
#endif
#ifdef WITH_YIELD
if (rc =3D pthread_yield())
{
trace("ERROR pthread_yield returned %i\n", rc);
}
#endif
=09
/* | destroy barrier b2 */
if (rc=3D 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);
=09
/* | initialize barrier b2 with value N+1 */
if (rc=3D pthread_barrier_init(&b2, NULL, N + 1 ))
{
trace("ERROR(%i): pthread_barrier_init (b2, %i) returned %d\n You wil=
l 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=3Dpthread_barrier_wait(&b1)) && (rc !=3D PTHREAD_BARRIER_SERIA=
L_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 =C2=B5sec...\n", SLEEPTIME);
usleep(SLEEPTIME);
#endif
#ifdef WITH_YIELD
if (rc =3D pthread_yield())
{
trace("ERROR pthread_yield returned %i\n", rc);
}
#endif
=09
/* | destroy barrier b1 */
if (rc=3D 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 =3D 'exit' */
control =3D ORDER_EXIT;
MYDEBUG ("control =3D EXIT\n", N);
/* wait for barrier b1 (all threads should read control and exit now)*/
if ((rc=3Dpthread_barrier_wait(&b2)) && (rc !=3D PTHREAD_BARRIER_SERIAL_=
THREAD))
{
trace("ERROR(%i): waiting for barrier b2 (%i)\n",__LINE__, rc);
}
MYDEBUG ("pthread_barrier_wait(b2) OK/NOK\n", N);
=09
=09
/* if threads were joinable, join them. */
while (N>0)
{
--N;
if (rc =3D 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
=09
pthread_mutex_destroy(&m_trace);
=09
return 0;
=09
}
--=-aaO4lgknU5HvnxozYaDo
Content-Disposition: attachment; filename=nptl_barriers.patch
Content-Type: text/x-patch; name=nptl_barriers.patch; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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 <[email protected]>
+
+ * 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 <[email protected]>
* 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)
--=-aaO4lgknU5HvnxozYaDo--