File: tc17_sembar.c

package info (click to toggle)
valgrind 1:3.12.0~svn20160714-1
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 120,428 kB
  • ctags: 70,855
  • sloc: ansic: 674,645; exp: 26,134; xml: 21,574; asm: 7,570; cpp: 7,567; makefile: 7,380; sh: 6,188; perl: 5,855; haskell: 195
file content (264 lines) | stat: -rw-r--r-- 7,364 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
/* This is really a test of semaphore handling
   (sem_{init,destroy,post,wait}).  Using semaphores a barrier
   function is created.  Helgrind-3.3 (p.k.a Thrcheck) does understand
   the barrier semantics implied by the barrier, as pieced together
   from happens-before relationships obtained from the component
   semaphores.  However, it does falsely report one race.  Ah well.
   Helgrind-3.4 is pure h-b and so reports no races (yay!). */
/* This code is derived from
   gcc-4.3-20071012/libgomp/config/posix/bar.c, which is

   Copyright (C) 2005 Free Software Foundation, Inc.
   Contributed by Richard Henderson <rth@redhat.com>.

   and available under version 2.1 or later of the GNU Lesser General
   Public License.

   Relative to the libgomp sources, the gomp_barrier_t type here has
   an extra semaphore field, xxx.  This is not functionally useful,
   but it is used to create enough extra inter-thread dependencies
   that the barrier-like behaviour of gomp_barrier_t is evident to
   Thrcheck.  There is no other purpose for the .xxx field. */
static sem_t* my_sem_init(char*, int, unsigned);
static int my_sem_destroy(sem_t*);
static int my_sem_wait(sem_t*); static int my_sem_post(sem_t*);
typedef struct
{
  pthread_mutex_t mutex1;
  pthread_mutex_t mutex2;
  sem_t* sem1;
  sem_t* sem2;
  unsigned total;
  unsigned arrived;
  sem_t* xxx;
} gomp_barrier_t;

typedef long bool;

void
gomp_barrier_init (gomp_barrier_t *bar, unsigned count)
{
  pthread_mutex_init (&bar->mutex1, NULL);
  pthread_mutex_init (&bar->mutex2, NULL);
  bar->sem1 = my_sem_init ("sem1", 0, 0);
  bar->sem2 = my_sem_init ("sem2", 0, 0);
  bar->xxx  = my_sem_init ("xxx",  0, 0);
  bar->total = count;
  bar->arrived = 0;
}

void
gomp_barrier_destroy (gomp_barrier_t *bar)
{
  /* Before destroying, make sure all threads have left the barrier.  */
  pthread_mutex_lock (&bar->mutex1);
  pthread_mutex_unlock (&bar->mutex1);

  pthread_mutex_destroy (&bar->mutex1);
  pthread_mutex_destroy (&bar->mutex2);
  my_sem_destroy(bar->sem1);
  my_sem_destroy(bar->sem2);
  my_sem_destroy(bar->xxx);
}

void
gomp_barrier_reinit (gomp_barrier_t *bar, unsigned count)
{
  pthread_mutex_lock (&bar->mutex1);
  bar->total = count;
  pthread_mutex_unlock (&bar->mutex1);
}

void
gomp_barrier_wait (gomp_barrier_t *bar)
{
  unsigned int n;
  pthread_mutex_lock (&bar->mutex1);

  ++bar->arrived;

  if (bar->arrived == bar->total)
    {
      bar->arrived--;
      n = bar->arrived;
      if (n > 0) 
        {
          { unsigned int i;
            for (i = 0; i < n; i++)
              my_sem_wait(bar->xxx); // acquire an obvious dependency from
              // all other threads arriving at the barrier
          }
          // 1 up n times, 2 down once
          // now let all the other threads past the barrier, giving them
          // an obvious dependency with this thread.
          do
            my_sem_post (bar->sem1); // 1 up
          while (--n != 0);
          // and wait till the last thread has left
          my_sem_wait (bar->sem2); // 2 down
        }
      pthread_mutex_unlock (&bar->mutex1);
      /* "Resultats professionnels!"  First we made this thread have an
         obvious (Thrcheck-visible) dependency on all other threads
         calling gomp_barrier_wait.  Then, we released them all again,
         so they all have a (visible) dependency on this thread.
         Transitively, the result is that all threads leaving the
         barrier have a a Thrcheck-visible dependency on all threads
         arriving at the barrier.  As required. */
    }
  else
    {
      pthread_mutex_unlock (&bar->mutex1);
      my_sem_post(bar->xxx);
      // first N-1 threads wind up waiting here
      my_sem_wait (bar->sem1); // 1 down 

      pthread_mutex_lock (&bar->mutex2);
      n = --bar->arrived; /* XXX see below */
      pthread_mutex_unlock (&bar->mutex2);

      if (n == 0)
        my_sem_post (bar->sem2); // 2 up
    }
}


/* re XXX, thrcheck reports a race at this point.  It doesn't
   understand that bar->arrived is protected by mutex1 whilst threads
   are arriving at the barrier and by mutex2 whilst they are leaving,
   but not consistently by either of them.  Oh well. */

static gomp_barrier_t bar;

/* What's with the volatile here?  It stops gcc compiling
   "if (myid == 4) { unprotected = 99; }" and
   "if (myid == 3) { unprotected = 88; }" into a conditional
   load followed by a store.  The cmov/store sequence reads and
   writes memory in all threads and cause Thrcheck to (correctly)
   report a race, the underlying cause of which is that gcc is
   generating non threadsafe code.  

   (The lack of) thread safe code generation by gcc is currently a
   hot topic.  See the following discussions:
     http://gcc.gnu.org/ml/gcc/2007-10/msg00266.html
     http://lkml.org/lkml/2007/10/24/673
   and this is interesting background:
     www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
*/
static volatile long unprotected = 0;

void* child ( void* argV )
{
   long myid = (long)argV;
   //   assert(myid >= 2 && myid <= 5);

   /* First, we all wait to get to this point. */
   gomp_barrier_wait( &bar );

   /* Now, thread #4 writes to 'unprotected' and so becomes its
      owner. */
   if (myid == 4) {
      unprotected = 99;
   }

   /* Now we all wait again. */
   gomp_barrier_wait( &bar );

   /* This time, thread #3 writes to 'unprotected'.  If all goes well,
      Thrcheck sees the dependency through the barrier back to thread
      #4 before it, and so thread #3 becomes the exclusive owner of
      'unprotected'. */
   if (myid == 3) {
      unprotected = 88;
   }

   /* And just to be on the safe side ... */
   gomp_barrier_wait( &bar );
   return NULL;
}


int main (int argc, char *argv[])
{
   long i; int res;
   pthread_t thr[4];
   fprintf(stderr, "starting\n");

   gomp_barrier_init( &bar, 4 );

   for (i = 0; i < 4; i++) {
      res = pthread_create( &thr[i], NULL, child, (void*)(i+2) );
      assert(!res);
   }

   for (i = 0; i < 4; i++) {
      res = pthread_join( thr[i], NULL );
      assert(!res);
   }

   gomp_barrier_destroy( &bar );

   /* And finally here, the root thread can get exclusive ownership
      back from thread #4, because #4 has exited by this point and so
      we have a dependency edge back to the write it did. */
   fprintf(stderr, "done, result is %ld, should be 88\n", unprotected);

   return 0;
}







static sem_t* my_sem_init (char* identity, int pshared, unsigned count)
{
   sem_t* s;

#if defined(VGO_linux) || defined(VGO_solaris)
   s = malloc(sizeof(*s));
   if (s) {
      if (sem_init(s, pshared, count) < 0) {
	 perror("sem_init");
	 free(s);
	 s = NULL;
      }
   }
#elif defined(VGO_darwin)
   char name[100];
   sprintf(name, "anonsem_%s_pid%d", identity, (int)getpid());
   name[ sizeof(name)-1 ] = 0;
   if (0) printf("name = %s\n", name);
   s = sem_open(name, O_CREAT | O_EXCL, 0600, count);
   if (s == SEM_FAILED) {
      perror("sem_open");
      s = NULL;
   }
#else
#  error "Unsupported OS"
#endif

   return s;
}

static int my_sem_destroy ( sem_t* s )
{
   return sem_destroy(s);
}

static int my_sem_wait(sem_t* s)
{
  return sem_wait(s);
}

static int my_sem_post(sem_t* s)
{
  return sem_post(s);
}