helgrind/tests/tc17_sembar.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <pthread.h>
   5 #include <semaphore.h>
   6 #include <unistd.h>
   7 #if defined(VGO_freebsd)
   8 # include <sys/fcntl.h>
   9 #endif
  10 /* This is really a test of semaphore handling
  11    (sem_{init,destroy,post,wait}).  Using semaphores a barrier
  12    function is created.  Helgrind-3.3 (p.k.a Thrcheck) does understand
  13    the barrier semantics implied by the barrier, as pieced together
  14    from happens-before relationships obtained from the component
  15    semaphores.  However, it does falsely report one race.  Ah well.
  16    Helgrind-3.4 is pure h-b and so reports no races (yay!). */
  17 /* This code is derived from
  18    gcc-4.3-20071012/libgomp/config/posix/bar.c, which is
  19
  20    Copyright (C) 2005 Free Software Foundation, Inc.
  21    Contributed by Richard Henderson <rth@redhat.com>.
  22
  23    and available under version 2.1 or later of the GNU Lesser General
  24    Public License.
  25
  26    Relative to the libgomp sources, the gomp_barrier_t type here has
  27    an extra semaphore field, xxx.  This is not functionally useful,
  28    but it is used to create enough extra inter-thread dependencies
  29    that the barrier-like behaviour of gomp_barrier_t is evident to
  30    Thrcheck.  There is no other purpose for the .xxx field. */
  31 static sem_t* my_sem_init(char*, int, unsigned);
  32 static int my_sem_destroy(sem_t*);
  33 static int my_sem_wait(sem_t*); static int my_sem_post(sem_t*);
  34 typedef struct
  35 {
  36   pthread_mutex_t mutex1;
  37   pthread_mutex_t mutex2;
  38   sem_t* sem1;
  39   sem_t* sem2;
  40   unsigned total;
  41   unsigned arrived;
  42   sem_t* xxx;
  43 } gomp_barrier_t;
  44
  45 typedef long bool;
  46
  47 void
  48 gomp_barrier_init (gomp_barrier_t *bar, unsigned count)
  49 {
  50   pthread_mutex_init (&bar->mutex1, NULL);
  51   pthread_mutex_init (&bar->mutex2, NULL);
  52   bar->sem1 = my_sem_init ("sem1", 0, 0);
  53   bar->sem2 = my_sem_init ("sem2", 0, 0);
  54   bar->xxx  = my_sem_init ("xxx",  0, 0);
  55   bar->total = count;
  56   bar->arrived = 0;
  57 }
  58
  59 void
  60 gomp_barrier_destroy (gomp_barrier_t *bar)
  61 {
  62   /* Before destroying, make sure all threads have left the barrier.  */
  63   pthread_mutex_lock (&bar->mutex1);
  64   pthread_mutex_unlock (&bar->mutex1);
  65
  66   pthread_mutex_destroy (&bar->mutex1);
  67   pthread_mutex_destroy (&bar->mutex2);
  68   my_sem_destroy(bar->sem1);
  69   my_sem_destroy(bar->sem2);
  70   my_sem_destroy(bar->xxx);
  71 }
  72
  73 void
  74 gomp_barrier_reinit (gomp_barrier_t *bar, unsigned count)
  75 {
  76   pthread_mutex_lock (&bar->mutex1);
  77   bar->total = count;
  78   pthread_mutex_unlock (&bar->mutex1);
  79 }
  80
  81 void
  82 gomp_barrier_wait (gomp_barrier_t *bar)
  83 {
  84   unsigned int n;
  85   pthread_mutex_lock (&bar->mutex1);
  86
  87   ++bar->arrived;
  88
  89   if (bar->arrived == bar->total)
  90     {
  91       bar->arrived--;
  92       n = bar->arrived;
  93       if (n > 0)
  94         {
  95           { unsigned int i;
  96             for (i = 0; i < n; i++)
  97               my_sem_wait(bar->xxx); // acquire an obvious dependency from
  98               // all other threads arriving at the barrier
  99           }
 100           // 1 up n times, 2 down once
 101           // now let all the other threads past the barrier, giving them
 102           // an obvious dependency with this thread.
 103           do
 104             my_sem_post (bar->sem1); // 1 up
 105           while (--n != 0);
 106           // and wait till the last thread has left
 107           my_sem_wait (bar->sem2); // 2 down
 108         }
 109       pthread_mutex_unlock (&bar->mutex1);
 110       /* "Resultats professionnels!"  First we made this thread have an
 111          obvious (Thrcheck-visible) dependency on all other threads
 112          calling gomp_barrier_wait.  Then, we released them all again,
 113          so they all have a (visible) dependency on this thread.
 114          Transitively, the result is that all threads leaving the
 115          barrier have a a Thrcheck-visible dependency on all threads
 116          arriving at the barrier.  As required. */
 117     }
 118   else
 119     {
 120       pthread_mutex_unlock (&bar->mutex1);
 121       my_sem_post(bar->xxx);
 122       // first N-1 threads wind up waiting here
 123       my_sem_wait (bar->sem1); // 1 down
 124
 125       pthread_mutex_lock (&bar->mutex2);
 126       n = --bar->arrived; /* XXX see below */
 127       pthread_mutex_unlock (&bar->mutex2);
 128
 129       if (n == 0)
 130         my_sem_post (bar->sem2); // 2 up
 131     }
 132 }
 133
 134
 135 /* re XXX, thrcheck reports a race at this point.  It doesn't
 136    understand that bar->arrived is protected by mutex1 whilst threads
 137    are arriving at the barrier and by mutex2 whilst they are leaving,
 138    but not consistently by either of them.  Oh well. */
 139
 140 static gomp_barrier_t bar;
 141
 142 /* What's with the volatile here?  It stops gcc compiling
 143    "if (myid == 4) { unprotected = 99; }" and
 144    "if (myid == 3) { unprotected = 88; }" into a conditional
 145    load followed by a store.  The cmov/store sequence reads and
 146    writes memory in all threads and cause Thrcheck to (correctly)
 147    report a race, the underlying cause of which is that gcc is
 148    generating non threadsafe code.
 149
 150    (The lack of) thread safe code generation by gcc is currently a
 151    hot topic.  See the following discussions:
 152      http://gcc.gnu.org/ml/gcc/2007-10/msg00266.html
 153      http://lkml.org/lkml/2007/10/24/673
 154    and this is interesting background:
 155      www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
 156 */
 157 static volatile long unprotected = 0;
 158
 159 void* child ( void* argV )
 160 {
 161    long myid = (long)argV;
 162    //   assert(myid >= 2 && myid <= 5);
 163
 164    /* First, we all wait to get to this point. */
 165    gomp_barrier_wait( &bar );
 166
 167    /* Now, thread #4 writes to 'unprotected' and so becomes its
 168       owner. */
 169    if (myid == 4) {
 170       unprotected = 99;
 171    }
 172
 173    /* Now we all wait again. */
 174    gomp_barrier_wait( &bar );
 175
 176    /* This time, thread #3 writes to 'unprotected'.  If all goes well,
 177       Thrcheck sees the dependency through the barrier back to thread
 178       #4 before it, and so thread #3 becomes the exclusive owner of
 179       'unprotected'. */
 180    if (myid == 3) {
 181       unprotected = 88;
 182    }
 183
 184    /* And just to be on the safe side ... */
 185    gomp_barrier_wait( &bar );
 186    return NULL;
 187 }
 188
 189
 190 int main (int argc, char *argv[])
 191 {
 192    long i; int res;
 193    pthread_t thr[4];
 194    fprintf(stderr, "starting\n");
 195
 196    gomp_barrier_init( &bar, 4 );
 197
 198    for (i = 0; i < 4; i++) {
 199       res = pthread_create( &thr[i], NULL, child, (void*)(i+2) );
 200       assert(!res);
 201    }
 202
 203    for (i = 0; i < 4; i++) {
 204       res = pthread_join( thr[i], NULL );
 205       assert(!res);
 206    }
 207
 208    gomp_barrier_destroy( &bar );
 209
 210    /* And finally here, the root thread can get exclusive ownership
 211       back from thread #4, because #4 has exited by this point and so
 212       we have a dependency edge back to the write it did. */
 213    fprintf(stderr, "done, result is %ld, should be 88\n", unprotected);
 214
 215    return 0;
 216 }
 217
 218
 219
 220
 221
 222
 223
 224 static sem_t* my_sem_init (char* identity, int pshared, unsigned count)
 225 {
 226    sem_t* s;
 227
 228 #if defined(VGO_linux) || defined(VGO_solaris) || defined(VGO_freebsd)
 229    s = malloc(sizeof(*s));
 230    if (s) {
 231       if (sem_init(s, pshared, count) < 0) {
 232          perror("sem_init");
 233          free(s);
 234          s = NULL;
 235       }
 236    }
 237 #elif defined(VGO_darwin)
 238    char name[100];
 239    sprintf(name, "anonsem_%s_pid%d", identity, (int)getpid());
 240    name[ sizeof(name)-1 ] = 0;
 241    if (0) printf("name = %s\n", name);
 242    s = sem_open(name, O_CREAT | O_EXCL, 0600, count);
 243    if (s == SEM_FAILED) {
 244       perror("sem_open");
 245       s = NULL;
 246    }
 247 #else
 248 #  error "Unsupported OS"
 249 #endif
 250
 251    return s;
 252 }
 253
 254 static int my_sem_destroy ( sem_t* s )
 255 {
 256    return sem_destroy(s);
 257 }
 258
 259 static int my_sem_wait(sem_t* s)
 260 {
 261   return sem_wait(s);
 262 }
 263
 264 static int my_sem_post(sem_t* s)
 265 {
 266   return sem_post(s);
 267 }