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
