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. */
28static sem_t* my_sem_init(char*, int, unsigned);
29static int my_sem_destroy(sem_t*);
30static int my_sem_wait(sem_t*); static int my_sem_post(sem_t*);
31typedef 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
42typedef long bool;
43
44void
45gomp_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
56void
57gomp_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
70void
71gomp_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
78void
79gomp_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
137static 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*/
154static volatile long unprotected = 0;
155
156void* 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
187int 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
221static sem_t* my_sem_init (char* identity, int pshared, unsigned count)
222{
223   sem_t* s;
224
225#if defined(VGO_linux)
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
251static int my_sem_destroy ( sem_t* s )
252{
253   return sem_destroy(s);
254}
255
256static int my_sem_wait(sem_t* s)
257{
258  return sem_wait(s);
259}
260
261static int my_sem_post(sem_t* s)
262{
263  return sem_post(s);
264}
265