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
gomp_barrier_init(gomp_barrier_t * bar,unsigned count)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
gomp_barrier_destroy(gomp_barrier_t * bar)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
gomp_barrier_reinit(gomp_barrier_t * bar,unsigned count)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
gomp_barrier_wait(gomp_barrier_t * bar)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
child(void * argV)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
main(int argc,char * argv[])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
my_sem_init(char * identity,int pshared,unsigned count)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
my_sem_destroy(sem_t * s)251 static int my_sem_destroy ( sem_t* s )
252 {
253 return sem_destroy(s);
254 }
255
my_sem_wait(sem_t * s)256 static int my_sem_wait(sem_t* s)
257 {
258 return sem_wait(s);
259 }
260
my_sem_post(sem_t * s)261 static int my_sem_post(sem_t* s)
262 {
263 return sem_post(s);
264 }
265