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