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