From f58aab44e671bb39b8afb29804a9ca94c238c523 Mon Sep 17 00:00:00 2001 From: rpj Date: Sun, 8 Jul 2001 16:44:06 +0000 Subject: Barriers fixed and tested more extensively. * barrier.c: Fix several bugs in all routines. Now passes tests/barrier5.c which is fairly rigorous. There is still a non-optimal work-around for a race condition between the barrier breeched event signal and event wait. Basically the last (signalling) thread to hit the barrier yields to allow any other threads, which may have lost the race, to complete. tests/ChangeLog: * barrier3.c: Fixed. * barrier4.c: Fixed. * barrier5.c: New; proves that all threads in the group reaching the barrier wait and then resume together. Repeats the test using groups of 1 to 16 threads. Each group of threads must negotiate a large number of barriers (10000). * spin4.c: Fixed. * test.h (error_string): Modified the success (0) value. --- ChangeLog | 22 +++++++++++++ Nmakefile.tests | 18 +++++++++++ attr.c | 2 +- barrier.c | 69 +++++++++++++++++++++++++++-------------- cancel.c | 2 +- condvar.c | 4 +-- implement.h | 2 +- misc.c | 2 +- private.c | 4 +-- tests/ChangeLog | 11 +++++++ tests/GNUmakefile | 3 +- tests/Makefile | 3 +- tests/barrier3.c | 2 +- tests/barrier4.c | 12 ++++++- tests/barrier5.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ tests/spin4.c | 2 +- tests/test.h | 2 +- 17 files changed, 215 insertions(+), 38 deletions(-) create mode 100644 tests/barrier5.c diff --git a/ChangeLog b/ChangeLog index 56c9124..bfb9646 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,25 @@ +2001-07-09 Ross Johnson + + * barrier.c: Fix several bugs in all routines. Now passes + tests/barrier5.c which is fairly rigorous. There is still + a non-optimal work-around for a race condition between + the barrier breeched event signal and event wait. Basically + the last (signalling) thread to hit the barrier yields + to allow any other threads, which may have lost the race, + to complete. + +2001-07-07 Ross Johnson + + * barrier.c: Changed synchronisation mechanism to a + Win32 manual reset Event and use PulseEvent to signal + waiting threads. If the implementation continued to use + a semaphore it would require a second semaphore and + some management to use them alternately as barriers. A + single semaphore allows threads to cascade from one barrier + through the next, leaving some threads blocked at the first. + * implement.h (pthread_barrier_t_): As per above. + * general: Made a number of other routines inlinable. + 2001-07-07 Ross Johnson * spin.c: Revamped and working; included static initialiser. diff --git a/Nmakefile.tests b/Nmakefile.tests index 8e124ab..109a995 100644 --- a/Nmakefile.tests +++ b/Nmakefile.tests @@ -79,6 +79,15 @@ cleanup3:: cleanup3.c priority1:: priority1.c priority2:: priority2.c inherit1:: inherit1.c +spin1:: spin1.c +spin2:: spin2.c +spin3:: spin3.c +spin4:: spin4.c +barrier1:: barrier1.c +barrier2:: barrier2.c +barrier3:: barrier3.c +barrier4:: barrier4.c +barrier5:: barrier5.c exception1:: exception1.c exception2:: exception2.c exception3:: exception3.c @@ -139,6 +148,15 @@ cleanup3 :test: cleanup2 priority1 :test: join1 priority2 :test: priority1 inherit1 :test: join1 +spin1 :test: +spin2 :test: spin1.c +spin3 :test: spin2.c +spin4 :test: spin3.c +barrier1 :test: +barrier2 :test: barrier1.c +barrier3 :test: barrier2.c +barrier4 :test: barrier3.c +barrier5 :test: barrier4.c benchtest1 :test: mutex3 benchtest2 :test: benchtest1 benchtest3 :test: benchtest2 diff --git a/attr.c b/attr.c index c56833c..74c2a59 100644 --- a/attr.c +++ b/attr.c @@ -31,7 +31,7 @@ #include "pthread.h" #include "implement.h" -static int +static INLINE int is_attr(const pthread_attr_t *attr) { /* Return 0 if the attr object is valid, non-zero otherwise. */ diff --git a/barrier.c b/barrier.c index 41bcf07..6a18f25 100644 --- a/barrier.c +++ b/barrier.c @@ -57,25 +57,28 @@ pthread_barrier_init(pthread_barrier_t * barrier, b->nCurrentBarrierHeight = b->nInitialBarrierHeight = count; result = pthread_mutex_init(&(b->mtxExclusiveAccess), NULL); - if (0 != result) - { - goto FAIL0; - } - - result = sem_init(&(b->semBarrierBreeched), pshared, 0); if (0 != result) { goto FAIL1; } - goto DONE; + b->eventBarrierBreeched = CreateEvent(NULL, /* Security attributes */ + TRUE, /* Manual reset */ + FALSE, /* Initially signaled */ + NULL); /* Name */ - FAIL1: + if (NULL != b->eventBarrierBreeched) + { + goto DONE; + } (void) pthread_mutex_destroy(&(b->mtxExclusiveAccess)); + result = ENOMEM; - FAIL0: + FAIL1: (void) free(b); + b = NULL; + FAIL0: DONE: *barrier = b; return(result); @@ -94,7 +97,9 @@ pthread_barrier_destroy(pthread_barrier_t *barrier) b = *barrier; - if (0 == pthread_mutex_trylock(&(b->mtxExclusiveAccess))) + result = pthread_mutex_trylock(&(b->mtxExclusiveAccess)); + + if (0 == result) { /* * FIXME!!! @@ -105,16 +110,24 @@ pthread_barrier_destroy(pthread_barrier_t *barrier) */ *barrier = NULL; - (void) sem_destroy(&(b->semBarrierBreeched)); + result = CloseHandle(b->eventBarrierBreeched); (void) pthread_mutex_unlock(&(b->mtxExclusiveAccess)); - (void) pthread_mutex_destroy(&(b->mtxExclusiveAccess)); - (void) free(b); + if (result == TRUE) + { + (void) pthread_mutex_destroy(&(b->mtxExclusiveAccess)); + (void) free(b); + result = 0; + } + else + { + *barrier = b; + result = EINVAL; + } } return(result); } - int pthread_barrier_wait(pthread_barrier_t *barrier) { @@ -136,8 +149,14 @@ pthread_barrier_wait(pthread_barrier_t *barrier) { b->nCurrentBarrierHeight = b->nInitialBarrierHeight; (void) pthread_mutex_unlock(&(b->mtxExclusiveAccess)); - (void) sem_post_multiple(&(b->semBarrierBreeched), - b->nInitialBarrierHeight); + /* + * This is a work-around for the FIXME below. We + * give any threads that didn't quite get to register + * their wait another quantum. This is temporary + * - there is a better way to do this. + */ + Sleep(0); + (void) PulseEvent(b->eventBarrierBreeched); /* * Would be better if the first thread to return * from this routine got this value. On a single @@ -151,23 +170,25 @@ pthread_barrier_wait(pthread_barrier_t *barrier) pthread_t self; int oldCancelState; - (void) pthread_mutex_unlock(&(b->mtxExclusiveAccess)); - self = pthread_self(); - + /* * pthread_barrier_wait() is not a cancelation point - * so temporarily prevent sem_wait() from being one. + * so temporarily prevent pthreadCancelableWait() from being one. */ if (self->cancelType == PTHREAD_CANCEL_DEFERRED) { pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &oldCancelState); } - if (0 != sem_wait(&(b->semBarrierBreeched))) - { - result = errno; - } + (void) pthread_mutex_unlock(&(b->mtxExclusiveAccess)); + + /* FIXME!!! It's possible for a thread to be left behind at a + * barrier because of the time gap between the unlock + * and the registration that the thread is waiting on the + * event. + */ + result = pthreadCancelableWait(b->eventBarrierBreeched); if (self->cancelType == PTHREAD_CANCEL_DEFERRED) { diff --git a/cancel.c b/cancel.c index e4e8a27..3aacc3c 100644 --- a/cancel.c +++ b/cancel.c @@ -60,7 +60,7 @@ ptw32_cancel_self(void) /* * ptw32_cancel_thread implements asynchronous cancellation. */ -static void +static INLINE void ptw32_cancel_thread(pthread_t thread) { HANDLE threadH = thread->threadH; diff --git a/condvar.c b/condvar.c index 1f2de22..55f0960 100644 --- a/condvar.c +++ b/condvar.c @@ -807,7 +807,7 @@ ptw32_cond_wait_cleanup(void * args) } /* ptw32_cond_wait_cleanup */ -static int +static INLINE int ptw32_cond_timedwait (pthread_cond_t * cond, pthread_mutex_t * mutex, const struct timespec *abstime) @@ -912,7 +912,7 @@ ptw32_cond_timedwait (pthread_cond_t * cond, } /* ptw32_cond_timedwait */ -static int +static INLINE int ptw32_cond_unblock (pthread_cond_t * cond, int unblockAll) /* diff --git a/implement.h b/implement.h index 5a146c0..5b30d1a 100644 --- a/implement.h +++ b/implement.h @@ -189,8 +189,8 @@ struct pthread_spinlock_t_ { struct pthread_barrier_t_ { LONG nCurrentBarrierHeight; LONG nInitialBarrierHeight; - sem_t semBarrierBreeched; pthread_mutex_t mtxExclusiveAccess; + HANDLE eventBarrierBreeched; }; struct pthread_barrierattr_t_ { diff --git a/misc.c b/misc.c index fffbcde..2b7fa7d 100644 --- a/misc.c +++ b/misc.c @@ -265,7 +265,7 @@ pthread_getconcurrency(void) } -static int +static INLINE int ptw32_cancelable_wait (HANDLE waitHandle, DWORD timeout) /* * ------------------------------------------------------------------- diff --git a/private.c b/private.c index 4bc1e38..de560c3 100644 --- a/private.c +++ b/private.c @@ -766,7 +766,7 @@ ptw32_callUserDestroyRoutines (pthread_t thread) #define TIMESPEC_TO_FILETIME_OFFSET \ ( ((LONGLONG) 27111902 << 32) + (LONGLONG) 3577643008 ) -static void +static INLINE void timespec_to_filetime(const struct timespec *ts, FILETIME *ft) /* * ------------------------------------------------------------------- @@ -780,7 +780,7 @@ timespec_to_filetime(const struct timespec *ts, FILETIME *ft) *(LONGLONG *)ft = ts->tv_sec * 10000000 + (ts->tv_nsec + 50) / 100 + TIMESPEC_TO_FILETIME_OFFSET; } -static void +static INLINE void filetime_to_timespec(const FILETIME *ft, struct timespec *ts) /* * ------------------------------------------------------------------- diff --git a/tests/ChangeLog b/tests/ChangeLog index 1c5d766..144454a 100644 --- a/tests/ChangeLog +++ b/tests/ChangeLog @@ -1,3 +1,14 @@ +2001-07-09 Ross Johnson + + * barrier3.c: Fixed. + * barrier4.c: Fixed. + * barrier5.c: New; proves that all threads in the group + reaching the barrier wait and then resume together. Repeats the test + using groups of 1 to 16 threads. Each group of threads must negotiate + a large number of barriers (10000). + * spin4.c: Fixed. + * test.h (error_string): Modified the success (0) value. + 2001-07-07 Ross Johnson * spin3.c: Changed test and fixed. diff --git a/tests/GNUmakefile b/tests/GNUmakefile index f005664..d62e45c 100644 --- a/tests/GNUmakefile +++ b/tests/GNUmakefile @@ -49,7 +49,7 @@ TESTS = loadfree \ cleanup0 cleanup1 cleanup2 cleanup3 \ priority1 priority2 inherit1 \ spin1 spin2 spin3 spin4 \ - barrier1 barrier2 barrier3 barrier4 \ + barrier1 barrier2 barrier3 barrier4 barrier5 \ exception1 exception2 exception3 BENCHTESTS = \ @@ -96,6 +96,7 @@ barrier1.pass: barrier2.pass: barrier1.pass barrier3.pass: barrier2.pass barrier4.pass: barrier3.pass +barrier5.pass: barrier4.pass cancel1.pass: create1.pass cancel2.pass: cancel1.pass cancel2_1.pass: cancel2.pass diff --git a/tests/Makefile b/tests/Makefile index f3a4f91..dba30d3 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -58,7 +58,7 @@ PASSES= loadfree.pass \ cleanup0.pass cleanup1.pass cleanup2.pass cleanup3.pass \ priority1.pass priority2.pass inherit1.pass \ spin1.pass spin2.pass spin3.pass spin4.pass \ - barrier1.pass barrier2.pass barrier3.pass barrier4.pass \ + barrier1.pass barrier2.pass barrier3.pass barrier4.pass barrier5.pass \ exception1.pass exception2.pass exception3.pass BENCHRESULTS = \ @@ -151,6 +151,7 @@ barrier1.pass: barrier2.pass: barrier1.pass barrier3.pass: barrier2.pass barrier4.pass: barrier3.pass +barrier5.pass: barrier4.pass cancel1.pass: create1.pass cancel2.pass: cancel1.pass cancel3.pass: context1.pass diff --git a/tests/barrier3.c b/tests/barrier3.c index 97f6dc2..1fea5a1 100644 --- a/tests/barrier3.c +++ b/tests/barrier3.c @@ -28,7 +28,7 @@ main() assert(pthread_create(&t, NULL, func, NULL) == 0); - assert(pthread_join(t, (void *) &result) == 0); + assert(pthread_join(t, (void **) &result) == 0); assert(result == PTHREAD_BARRIER_SERIAL_THREAD); diff --git a/tests/barrier4.c b/tests/barrier4.c index 8f33e85..dd40b79 100644 --- a/tests/barrier4.c +++ b/tests/barrier4.c @@ -23,14 +23,24 @@ func(void * arg) int result = pthread_barrier_wait(&barrier); assert(pthread_mutex_lock(&mx) == 0); + +// printf("Barrier wait returned %d [%d]\n", result, WAIT_FAILED); +// fflush(stdout); + if (result == PTHREAD_BARRIER_SERIAL_THREAD) { serialThreadCount++; } - else + else if (0 == result) { otherThreadCount++; } + else + { + printf("Barrier wait failed: error = %s\n", error_string[result]); + fflush(stdout); + return NULL; + } assert(pthread_mutex_unlock(&mx) == 0); return NULL; diff --git a/tests/barrier5.c b/tests/barrier5.c new file mode 100644 index 0000000..6576b05 --- /dev/null +++ b/tests/barrier5.c @@ -0,0 +1,93 @@ +/* + * barrier5.c + * + * Declare a single barrier object, set up a sequence of + * barrier points to prove lockstepness, and then destroy it. + * + */ + +#include "test.h" + +enum { + NUMTHREADS = 16, + ITERATIONS = 10000 +}; + +pthread_barrier_t barrier = NULL; +pthread_mutex_t mx = PTHREAD_MUTEX_INITIALIZER; + +int barrierReleases[ITERATIONS + 1]; + +void * +func(void * barrierHeight) +{ + int i; + int result; + + for (i = 1; i < ITERATIONS; i++) + { + result = pthread_barrier_wait(&barrier); + + assert(pthread_mutex_lock(&mx) == 0); + barrierReleases[i]++; + assert(pthread_mutex_unlock(&mx) == 0); + /* + * Confirm the correct number of releases from the previous + * barrier. We can't do the current barrier yet because there may + * still be threads waking up. + */ + if (result == PTHREAD_BARRIER_SERIAL_THREAD) + { + assert(pthread_mutex_lock(&mx) == 0); +//printf("Releases bucket %d = %d\n", i - 1, barrierReleases[i - 1]); +//fflush(stdout); + assert(barrierReleases[i - 1] == (int) barrierHeight); + barrierReleases[i + 1] = 0; + assert(pthread_mutex_unlock(&mx) == 0); + } + else if (result != 0) + { + printf("Barrier failed: result = %s\n", error_string[result]); + fflush(stdout); + return NULL; + } + } + + return NULL; +} + +int +main() +{ + int i, j; + pthread_t t[NUMTHREADS + 1]; + + for (j = 1; j <= NUMTHREADS; j++) + { + printf("Barrier height = %d\n", j); + + barrierReleases[0] = j; + barrierReleases[1] = 0; + + assert(pthread_barrier_init(&barrier, NULL, j) == 0); + + for (i = 1; i <= j; i++) + { + assert(pthread_create(&t[i], NULL, func, (void *) j) == 0); + } + + for (i = 1; i <= j; i++) + { + assert(pthread_join(t[i], NULL) == 0); + } + + assert(barrierReleases[ITERATIONS - 1] == j); + assert(barrierReleases[ITERATIONS] == 0); + + assert(pthread_barrier_destroy(&barrier) == 0); + } + + assert(pthread_mutex_destroy(&mx) == 0); + + return 0; +} diff --git a/tests/spin4.c b/tests/spin4.c index 5f04a27..8f73008 100644 --- a/tests/spin4.c +++ b/tests/spin4.c @@ -59,7 +59,7 @@ main() assert(pthread_spin_unlock(&lock) == 0); - assert(pthread_join(t, (void *) &result) == 0); + assert(pthread_join(t, (void **) &result) == 0); assert(result > 1000); assert(pthread_spin_destroy(&lock) == 0); diff --git a/tests/test.h b/tests/test.h index 018b215..c5b565d 100644 --- a/tests/test.h +++ b/tests/test.h @@ -13,7 +13,7 @@ #include char * error_string[] = { - "ZERO", + "ZERO_or_EOK", "EPERM", "ENOFILE_or_ENOENT", "ESRCH", -- cgit v1.2.3