Home | History | Annotate | Download | only in tests
      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 (at) 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 }
    265