#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);
}